19.5: Codes From Designs

Last updated
Save as PDF

Page ID: 75515

\( \newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } \) \( \newcommand{\vecd}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}} \)\(\newcommand{\id}{\mathrm{id}}\) \( \newcommand{\Span}{\mathrm{span}}\) \( \newcommand{\kernel}{\mathrm{null}\,}\) \( \newcommand{\range}{\mathrm{range}\,}\) \( \newcommand{\RealPart}{\mathrm{Re}}\) \( \newcommand{\ImaginaryPart}{\mathrm{Im}}\) \( \newcommand{\Argument}{\mathrm{Arg}}\) \( \newcommand{\norm}[1]{\| #1 \|}\) \( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\) \( \newcommand{\Span}{\mathrm{span}}\) \(\newcommand{\id}{\mathrm{id}}\) \( \newcommand{\Span}{\mathrm{span}}\) \( \newcommand{\kernel}{\mathrm{null}\,}\) \( \newcommand{\range}{\mathrm{range}\,}\) \( \newcommand{\RealPart}{\mathrm{Re}}\) \( \newcommand{\ImaginaryPart}{\mathrm{Im}}\) \( \newcommand{\Argument}{\mathrm{Arg}}\) \( \newcommand{\norm}[1]{\| #1 \|}\) \( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\) \( \newcommand{\Span}{\mathrm{span}}\)\(\newcommand{\AA}{\unicode[.8,0]{x212B}}\)

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}\)

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?
How many errors can be corrected by a code that comes from a BIBD\((21, 4, 1)\)?
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?