Skip to main content

Section 19.5 Codes from designs

An error-correcting code can be constructed from any BIBD\((v,k,\lambda)\) for which \(\lambda=1\text{.}\) More precisely, from each block of the design, create a binary string of length \(v\text{,}\) by placing a \(1\) in each of the positions that correspond to points in the design, and place \(0\)s everywhere else. (The resulting code will not usually have a generator matrix, so it is not a binary linear code. In fact, it is encoding the blocks of the design rather than all binary strings of some length \(r\text{,}\) so unlike binary linear codes the total number of code words will not always be a power of \(2\text{.}\))

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

\begin{equation*} \{1,2,3\},\{1,4,5\},\{1,6,7\},\{2,4,6\},\{2,5,7\},\{3,4,7\},\{3,5,6\}\text{,} \end{equation*}

the corresponding code is

\begin{equation*} \code = \{ 1110000, 1001100, 1000011, 0101010, 0100101, 0011001, 0010110 \}\text{.} \end{equation*}

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\text{.}\) If the blocks have \(1\) entry in common, then

\begin{equation*} d(b,b')=2(k-1) \end{equation*}

(the strings differ in the \(k-1\) positions corresponding to points that are in \(B\) but not in \(B'\text{,}\) and in the \(k-1\) positions corresponding to points that are in \(B'\) but not in \(B\)). Since \(\lambda=1\text{,}\) the blocks cannot have more than one point in common. So in any case,

\begin{equation*} d(b,b')\ge 2(k-1)\text{.} \end{equation*}

Since \(b\) and \(b'\) were arbitrary output words of the code (because \(B\) and \(B'\) were arbitrary blocks), this means that \(d(\code) \ge 2(k-1)\text{.}\) This is greater than \(2(k-2)\text{,}\) so Theorem 19.2.12 tells us that the code can correct any \(k - 2\) errors.

⬛

  1. Suppose that you use a BIBD to create a code whose words have length \(10\text{,}\) 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)\text{?}\)

  3. Recall the \(2\)-\((8,4,3)\) design given in Exercise 17.2.8.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?