19.5: Codes From Designs

An error-correcting code can be constructed from any design BIBD$(v, k, λ)$ for which $λ = 1$. Namely, from each block of the design, create a binary string of length $v$, by placing a $1$ in each of the positions that correspond to points in the design, and $0$s everywhere else. (However, this will not usually have a generator matrix, so it is not a binary linear code.)

Example $\PageIndex{1}$

For the BIBD$(7, 3, 1)$ that has arisen in previous examples, with blocks

$\{1, 2, 3\}, \{1, 4, 5\}, \{1, 6, 7\}, \{2, 4, 6\}, \{2, 5, 7\}, \{3, 4, 7\}, \{3, 5, 6\},$

the corresponding code is

$C = \{1110000, 1001100, 1000011, 0101010, 0100101, 0011001, 0010110\}.$

Proposition $\PageIndex{1}$

A BIBD$(v, k, 1)$ can be used to produce a code that can correct up to $k − 2$ errors.

Proof

Let $B$ and $B'$ be blocks of the design, and let $b$, $b'$ be the corresponding binary strings of length $k$ as described at the start of this section. If the blocks have no points in common, then $d(b, b') = 2k$. If the blocks have $1$ entry in common, then

$d(b, b') = 2(k − 1)$

(the strings differ in the $k − 1$ positions corresponding to points that are in $B$ but not in $B'$, and in the $k − 1$ positions corresponding to points that are in $B'$ but not in $B$). Since $λ = 1$, the blocks cannot have more than one point in common. So in any case,

$d(b, b') ≥ 2(k − 1).$

Since $b$ and $b'$ were arbitrary output words of the code (because $B$ and $B'$ were arbitrary blocks), this means that $d(C) ≥ 2(k − 1)$. This is greater than $2(k − 2)$, so Theorem 19.2.2 tells us that the code can correct any $k − 2$ errors.

Exercise $\PageIndex{1}$

1. If you use a BIBD to create a code whose words have length $10$, that is $4$-error-correcting. How many words will your code have?
2. How many errors can be corrected by a code that comes from a BIBD$(21, 4, 1)$?
3. Recall the $2$-$(8, 4, 3)$ design given in Exercise 17.2.1(2). It is possible to show that this is also a $3$-$(8, 4, 1)$ design; for the purposes of this problem, you may assume that this is true. If we convert these blocks to binary strings to form code words for a code, how many errors can this code correct?