Appendix F - Classical Error Correcting Codes

Introduction

Classical error correcting codes are in use in a wide variety of digital electronics and other classical information systems. It is a good idea to learn some of the basic definitions, ideas, methods, and simple examples of classical error correcting codes in order to understand the (slightly) more complicated quantum error correcting codes. There are many good introductions to classical error correction. Here we follow a few sources which also discuss quantum error correcting codes: the book by Loepp and Wootters, an article in Lo, Popescu, and Spiller by Steane, Gottesman's Thesis, and Gaitan's Book on quantum error correction, which also discusses classical error correction.

Binary Operations

The set Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \{0,1\} \,\!} is a group under addition. (See Section D.2.8 of Appendix D.) The way this is achieved is by deciding that we will only use these two numbers in our language and using addition modulo 2, meaning, $0+0=0,1+0=0+1=1,\,\!$ and Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle 1+1 =0\,\!} . If we also include the operation of multiplication, the set, with the two operations, becomes a field (a Galois Field) and that field is denoted GFFailed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle (2)\,\!} . Since one often works with strings of bits, it is very useful to consider the string of bits to be a vector and use vector addition (which is component-wise addition) and a vector multiplication which is the inner product. For example, the addition of the vector Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle (0,0,1)\,\!} and Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle (0,1,1)\,\!} is Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle (0,0,1) + (0,1,1) = (0,1,0)\,\!} . The inner product between these two vectors is $(0,0,1)\cdot (0,1,1)=0\cdot 0+0\cdot 1+1\cdot 1=0+0+1=1\,\!$.

Definitions and Basics

Definition 1

The inner product is also called a checksum or parity check since it shows whether or not the first and second vectors agree have an even number of 1's at the positions specified by the ones in the other vector. We may say that the first vector satisfies the parity check of the first vector, or vice versa.

Definition 2

The weight or Hamming weight is the number of non-zero components of a vector or string. The weight of a vector Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle v\,\!} is denoted wt(Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle v\,\!} ).

Definition 3

The Hamming distance is the number of places where two vectors differ. Let the two vectors be Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle v\,\!} and $w\,\!$, then the Hamming distance is also equal to wt(Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle v+w\,\!} ). The Hamming distance between Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle v\,\!} and Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle w\,\!} will be denoted $d_{H}(v,w)\,\!$.

Definition 4

We use Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \{0,1\}^n\,\!} denote the set of all binary vectors of length Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle n\,\!} . A code Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle C\,\!} of length Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle n\,\!} is any subset of that set. The set of all elements of Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle C\,\!} is called the set of codewords. We also say there are $2^{n}\,\!$ $n\,\!$-bit words in the space.

Suppose $n\,\!$ bits are used to encode $k\,\!$ logical bits. We use the notation $[n,k]\,\!$ do denote such a code.

Definition 5

The minimum distance of a code is the smallest Hamming distance between any two non-equal vectors in a code. This can be written

	$d_{Hmin}(C)={\underset {v,w\in C,v\neq w}{\mbox{min}}}d_{H}(v,w).\,\!$	(F.1)

For shorthand, we also use $d(C)\,\!$ or $d\,\!$ if $C\,\!$ is understood.

When that code has a distance Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle d\,\!} , the notation $[n,k,d]\,\!$ is used.

Example 1

It is interesting to note that if we encode redundantly using Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle 0_L=00 \,\!} and $1_{L}=11\,\!$ as our logical zero and logical one respectively, then we could detect single bit errors, but not correct them. For example, if we receive $01\,\!$, we know this cannot be one of our encoded states. So an error must have occurred. However, we don't know whether the sender sent $0_{L}=00\,\!$ or $1_{L}=11\,\!$. We do know that an error has occurred though, as long as we know only one error has occurred. Such an encoding can be used as an error detecting code. In this case there are two code words, $0_{L}=00\,\!$ and Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle 1_L=11\,\!} , but four words in the space. The minimum distance is 2 which is the distance between the two code words.

Example 2

The three-bit redundant encoding was already given in Chapter 7. One takes logical zero and logical one states to be the following

	Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle 0_L = 000, \;\;\; \mbox{ and } \;\;\; 1_L = 111, \,\!}	(F.2)

where the subscript Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle L \,\!} is used to denote a "logical" state, that is, one which is encoded. Recall that this code is able to detect and correct one error. In this case there are two code words out of eight possible words and the minimal distance is 3.

Definition 6

The rate of a code is given by the ration of the number of logical bits to the number of bits, Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle k/n\,\!} .

Definition 7

A linear code $C_{l}\,\!$ is a code which is closed under addition.

Linear Codes

Linear codes are particularly simple codes with extra features. These codes are important for their simplicity as well as the added structure.

Generator Matrix

For linear codes, any linear combination of codewords is a codeword. One key feature of a linear code is that it can be specified by a ''generator matrix'' Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle G\,\!} . For an Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle [n,k]\,\!} code, the generator matrix is an Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle n\times k\,\!} matrix with columns that form a basis for the $k\,\!$-dimensional coding sub-space of the Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle n\,\!} -dimensional binary vector space. In other words, the vectors comprising the rows form a basis which will span the code space. (Note that one may also use the transpose of this matrix as the definition for Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle G\,\!} .) Any code word Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle w\,\!} , described by a vector Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle v\,\!} can be written in terms of the generator matrix as $w=Gv\,\!$. Note that $G\,\!$ is independent of the input and output vectors. In addition, $G\,\!$ is not unique. If columns are switched, or even added to produce a new vector which replaces a column, the generator matrix is still valid for the code. This is due to the requirement that the columns be linearly independent which is still satisfied if these operations are performed.

Parity Check Matrix

Once $G\,\!$ is obtained, one can calculate another useful matrix $P\,\!$. $P\,\!$ is an $(n\times k)\times n\,\!$ matrix which has the property that

	$PG=0.\,\!$	(F.3)

The matrix $P\,\!$ is called the parity check matrix or dual matrix. The rank of $P\,\!$ is at most $n-k\,\!$ and has the property that it annihilates any code word. To see this, recall any code word is written as $Gv\,\!$, so Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle PGv =0\,\!} since Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle PG =0\,\!} . Also, due to the rank of Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle P\,\!} , it can be shown that $Pw=0\,\!$ only if Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle w\,\!} is a code word. That is to say, Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle Pw=0\,\!} if and only if Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle w\,\!} is a code word. This means that $P\,\!$ can be used to test whether or not a word is in the code.

Suppose an error occurs on a code word $w\,\!$ to produce Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle w^\prime = w + e\,\!} . Now consider

	Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle Pw^\prime = P(w+e) = Pe, \,\!}	(F.4)

since Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle Pw=0\,\!} . This result, $Pe\,\!$ is called the error syndrome and the measurement to identify Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle Pe\,\!} is called the syndrome measurement. Therefore, the result depends only on the error and not on the original code word. If the error can be determined from this result, then it can be corrected independent of the code word. However, in order to have Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle Pe\,\!} be unique, two different results Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle Pe_1\,\!} and $Pe_{2}\,\!$ must not be equal. This is possible if a distance Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle d\,\!} code is constructed such that the parity check matrix has Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle d-1=2t\,\!} linearly independent columns. This enables the errors to be identified and thus corrected.

Errors

For any classical error correcting code, there are general conditions which must be satisfied in order for the code to be able to detect and correct errors. The two examples above show how the error can be detected, but here the objective is to give some general conditions.

Note that any state containing an error may be written as the sum of the original state (logical or encoded state) Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle w \,\!} and another vector $e\,\!$. The error vector Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle e \,\!} has ones are in the places where errors are present and zeroes everywhere else. To ensure that the error may be corrected, the following condition must be satisfied for two states with errors occurring

	Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle w_1 + e_1 \neq w_2 + e_2. \,\!}	(F.5)

This condition is called the disjointness condition. This condition means that an error on one state cannot be confused with an error on another state. If it could, then the state including the error could not be uniquely identified with an encoded state and the state could not be corrected to its original state before the error occurred. More specifically, for a code to correct $t\,\!$ single-bit errors, it must have distance at least Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle 2t + 1 \,\!} between any two codewords, i.e., it must be a distance Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle 2t + 1 \,\!} code, i.e., it must be true that Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle d(C) \geq 2t + 1 \,\!} . An Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle [n,k]\,\!} code with minimal distance $d\,\!$ is denoted Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle [n,k,d]\,\!} .

Example 3

An important example of an error correcting code is called the $[7,4,3]$ Hamming code. This code, as the notation indicates, encodes Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle k=4} bits of information into Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle n=7} bits. It also does it in such a way that one error can be detected and corrected since it has a distance of Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle 3} . The generator matrix for this code can be taken to be (see Loepp and Wootters)

	Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle G^T = \left(\begin{array}{ccccccc} 1 & 0 & 0 & 0 & 1 & 1 & 0 \\ 0 & 1 & 0 & 0 & 1 & 1 & 1 \\ 0 & 0 & 1 & 0 & 1 & 0 & 1 \\ 0 & 0 & 0 & 1 & 0 & 1 & 1 \end{array}\right). \,\!}	(F.6)

From this the parity check matrix, Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle P\,\!} can be calculated by finding a set of Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle n-k\,\!} mutually orthogonal vectors which are also orthogonal to the code space defined by the generator matrix. Alternatively, one could find the generator matrix from the parity check matrix. A method for doing this can be found in Steane's article in Lo, Popescu, and Spiller. One first puts Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle G^T\,\!} in the form Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle (I_k,A),\,\!} where Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle I_k\,\!} is the $k\times k\,\!$ identity matrix. Then the parity check matrix Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle P = (A^T,I_{n-k}).\,\!} In either case, one can arrive at the following parity check matrix for this code:

	Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle P = \left(\begin{array}{ccccccc} 1 & 1 & 1 & 0 & 1 & 0 & 0 \\ 1 & 1 & 0 & 1 & 0 & 1 & 0 \\ 0 & 1 & 1 & 1 & 0 & 0 & 1 \end{array}\right). \,\!}	(F.7)

It is useful to note that the code can also be defined by the parity check matrix. The codewords are annihilated by the parity check matrix and only the codewords are annihilated by that matrix.

The Disjointness Condition and Correcting Errors

The motivation for the disjointness condition, Eq.(F.5), is to associate each vector in the space with a particular code word. That is, assuming that only certain errors occur, each error vector should be associated to a particular vector in the code space when the error is added to the original code word. This partitions the set into disjoint subsets each of which contains only one code vector. A message is decoded correctly if the vector (the one containing the error) is in the subset which is associated with the original vector (the one with no error). For example, if one vector is sent, say Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle v_1 \,\!} and an error occurs during transmission to produce $v_{2}=v_{1}+e\,\!$, this vector must be in the subset containing Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle v_1 \,\!} .

A way to decode is to record an array of possible code words, possible errors, and the combinations of those errors and code words. The array can be set up as a top row of the code word vectors and a leftmost column of errors with the element of the first row and the first column being the zero vector and all subsequent entries in the column being errors. Then the element at the top of a column (say the jth column) is added to the error in the corresponding row (say the kth row) to get the j,k entry of the array. With this array one can associate a column with a subset that is disjoint with the other sets. Then identifying the erred code word in a column associates it with a code word and thus corrects the error.

The Hamming Bound

The Hamming bound is a bound that restricts the rate of the code. Due to the disjointness condition, a certain number of bits are required to ensure our ability to detect and correct errors. Suppose there is a set of Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle n\,\!} bit vectors for encoding Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle k\,\!} bits of information. There is a set of error vectors of weight $t\,\!$ that has Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle C(n,t)\,\!} elements. So the number of error vectors, including errors of weight up to Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle t \,\!} , is Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \sum_{i=0}^t C(n,i). \,\!} (Note that no error is also part of the set of error vectors. The objective is to be able to design a code which can correct all errors up to those of weight Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle t \,\!} and this includes no error at all.) Since there are Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle 2^n\,\!} vectors in the whole space of $n\,\!$ bits, and assuming Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle m\,\!} vectors are used for the encoding, the Hamming bound is

	$m\sum _{i=0}^{t}C(n,i)\leq 2^{n}.\,\!$	(F.8)

For linear codes, Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle m=2^k,\,\!} so

	Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle 2^k\sum_{i=0}^t C(n,i) \leq 2^n. \,\!}	(F.9)

Taking the logarithm,

	Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle k \leq n - \log_2\left(\sum_{i=0}^t C(n,i)\right). \,\!}	(F.10)

For large $n,k\,\!$ and Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle t \,\!} , we can use Stirling's formula to show that

	Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \frac{k}{n} \leq 1 - H\left(\frac{t}{n}\right), \,\!}	(F.10)

where Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle H(x) = -x\log x -(1-x)\log (1-x) \,\!} and we have neglected an overall multiplicative constant which goes to 1 as $n\rightarrow \infty .\,\!$ (Again, see the article in Lo, Popescu, and Spiller by Steane.)

NOTES

As can be seen from the Hamming bound, there is a limit to rate of an error correcting code. This does not indicate whether or not codes satisfying these bounds exists, but it does tell us that no codes exist which do not satisfy these bounds. Encoding decoding and error detection and correction are all problems which can be difficult to solve in general. One of the advantages of the linear codes is that they provide a systematic method for identifying errors on a code through the use of the parity check operation. More generally, checking to see whether or not a bit string (vector) is in the code space would require a lookup table. This would be much more time-consuming that using the parity check matrix where matrix multiplication is quite efficient relative to the lookup table.

Many of these ideas and definitions will be utilized in Chapter 7 on quantum error correction. Some linear codes, including the Hamming code above, will have quantum analogues as do many quantum error correcting codes. In quantum computers, as will be discussed, error correction is necessary since the quantum information is delicate. Such discussions will be taken up in Chapter 7.