Codes

Why Errors Need Detecting

In Cryptosystems the whole point was privacy; we wanted a message that an eavesdropper could not read. Sometimes we are much less worried about privacy and much more worried about the message arriving intact. Wires pick up noise, discs get scratched, satellites get hit by cosmic rays; digits flip. What we want is a way of writing the message down so that a flipped digit is at least noticeable, and ideally repairable.

To see why this is a genuine problem, take the standard letter-to-number conversion $A\to 1$, $B\to 2$, $C\to 3,\dots$ and send the letter $M$. Then $M\to 13$, and (recalling Base Number Systems) $13$ in binary is

$$13=8+4+1=(1101{)}_2,$$

so we transmit the string $1101$. Now suppose the leading digit gets knocked from $1$ to $0$ in transit, so the receiver sees $0101$. They decode this perfectly happily:

$$(0101{)}_2=4+1=5\to E.$$

The receiver reads $E$, believes it, and has absolutely no reason to suspect anything went wrong. This is the failure mode we are trying to design away. The problem is not that an error occurred; the problem is that every one of the sixteen $4$-digit strings is a legal message, so a corrupted string is still a legal message.

The fix, in every code in this lecture, is the same idea: deliberately send more digits than the message needs, arranged so that only some of the strings are legal. Then a single flip drops you off the list of legal strings and the receiver can see it. Codes come in two strengths:

• an error-detecting code lets the receiver tell that something has gone wrong (so they can ask for a retransmission);
• an error-correcting code lets the receiver work out which digit is wrong and repair it without asking for anything.

All the arithmetic in this lecture happens in ${\mathbb{Z}}_2=\{0,1\}$, which by Rings and Fields is a field, and in which the only rules you need are

$$0+0=0,0+1=1+0=1,1+1=0.$$

Basically, addition in ${\mathbb{Z}}_2$ is "flip the digit if you add $1$, leave it alone if you add $0$", and it is its own inverse: $-1=1$, so in ${\mathbb{Z}}_2$ there is no difference between adding and subtracting, and you never have to worry about signs. That single fact makes every calculation below shorter than it looks.

Parity Check Codes

The cheapest possible thing you can do is add one extra digit that records whether the message had an even or odd number of $1$​s.

Basically, the check digit is chosen to make the total number of $1$​s even; so if the receiver ever counts an odd number of $1$​s, a digit must have flipped. Said in ${\mathbb{Z}}_2$, if the message digits are $m_1,m_2,\dots ,m_k$ then the check digit is simply

$$m_{k+1}=m_1+m_2+\cdots +m_k\text{ in }{\mathbb{Z}}_2,$$

and a legal encoded word is exactly one satisfying $m_1+m_2+\cdots +m_k+m_{k+1}=0$ in ${\mathbb{Z}}_2$. Keep that phrasing in mind; every code in this lecture will turn out to be "the strings satisfying some system of ${\mathbb{Z}}_2$ equations".

Example. Encode the letter $M$ with a simple parity check, and show what happens when the leading digit is flipped in transit.
As above, $M\to 13\to 1101$. The original message $1101$ contains three $1$​s, which is odd, so the check digit is $1$ and the transmitted word is

$$11011.$$

Suppose the leading digit is flipped, so the receiver gets $01011$. Counting,

$$\begin{array}{rl}0+1+0+1+1& =3,\end{array}$$

which is odd; therefore the receiver knows that at least one error has occurred and can request a retransmission. Contrast this with the bare $4$-digit code, where the same flip silently turned $M$ into $E$; one extra digit bought us the ability to notice.

Example. The same word $11011$ is sent, but this time the first two digits are flipped, so the receiver gets $00011$. What happens?
Counting the $1$​s,

$$\begin{array}{rl}0+0+0+1+1& =2,\end{array}$$

which is even, so the parity check passes and the receiver suspects nothing. They discard the final digit and read $0001=1\to A$. Therefore, the parity check completely misses this pair of errors and silently reports the letter $A$ instead of $M$. A parity check detects exactly an odd number of errors; any even number of errors cancels out and slips through unnoticed.

It is worth being blunt about the other limitation as well. Even when the check does fire, all it tells you is "somewhere in these five digits, an odd number of things are wrong". It does not tell you where, and it does not tell you how many, so there is nothing you can do except ask for the message again. The simple parity check is a pure error-detecting code; it can never correct anything.

The cost of the code is one extra digit per chunk. If we parity-check in chunks of $4$ information digits, then $5$ digits get transmitted for every $4$ digits of actual message, so $\frac{4}{5}$ of the traffic is useful; we will call this proportion the rate of the code. A rate of $\frac{4}{5}$ is excellent value, which is precisely why parity bits are everywhere in real hardware. The trouble is that we got what we paid for: cheap code, weak guarantees.

Reduplication Codes

The obvious way to buy more protection is brute force; just say everything twice.

Basically, the legal pairs are $00$ and $11$; anything else is a red flag, and it even tells you which pair went wrong. This is strictly better than a parity check in one respect and strictly worse in another, so it is worth being careful about exactly what it gives you.

Example. Encode $M\to 1101$ under double reduplication, and decode the received word $11100011$.
Repeating each digit twice, the transmitted word is

$$1101⟶11110011.$$

The receiver gets $11100011$. Splitting into pairs and reading them off,

$$\begin{array}{rl}11& \to 1,\\ 10& \to \text{error in this position},\\ 00& \to 0,\\ 11& \to 1.\end{array}$$

Therefore, the receiver knows that an error occurred, and knows it happened in the second digit of the message — but that is as far as it goes. The true second digit could have been a $1$ (with the second copy flipped) or a $0$ (with the first copy flipped), and nothing in the received word distinguishes those two stories. Double reduplication detects and locates an error, but it still cannot correct one.

Notice also that multiple errors are often, but not always, caught: two errors in different pairs both show up, whereas two errors inside the same pair turn $11$ back into $00$ and are invisible. In exchange for all this we have doubled the length of the message, so the rate has crashed from $\frac{4}{5}$ to $\frac{1}{2}$. That is a lot of bandwidth for a code that still cannot fix anything.

If saying everything twice does not let you correct, the natural next move is to say everything three times and take a vote.

Basically, this is majority rule: each digit gets three votes, and the minority is assumed to be the mistake. The correction is only valid under the assumption that there is at most one error per triple; if two digits inside the same triple flip, the majority vote confidently returns the wrong answer, which is worse than not correcting at all.

Example. Encode $M\to 1101$ under triple reduplication, and decode the received word $111101000011$.
Repeating each digit three times, the transmitted word is

$$1101⟶111111000111,$$

which is $12$ digits long. Splitting the received word into triples and taking a majority vote in each,

$$\begin{array}{rl}111& \to 1(\text{unanimous}),\\ 101& \to 1(\text{two }1\text{s, so the middle digit was flipped}),\\ 000& \to 0(\text{unanimous}),\\ 011& \to 1(\text{two }1\text{s, so the first digit was flipped}).\end{array}$$

Therefore, the decoded message is $1101=13\to M$, recovered correctly despite two transmission errors, and the receiver can even point at exactly which two digits were wrong. This is a genuine error-correcting code.

Example. Under the same code, what does the receiver make of the received triple $110$?
Majority vote gives $1$, since two of the three digits are $1$. If exactly one error occurred, this is right. But if the sent triple was $000$ and two digits flipped, the true digit was $0$ and the decoder has just committed confidently to the wrong value; and if the sent triple was $111$ with one flip, it is right. Therefore, the answer the code returns is $1$, but that answer is only trustworthy under the at-most-one-error-per-triple assumption. Every error-correcting code in this course carries an assumption of that kind; quoting the answer without quoting the assumption is only half the answer.

The price is brutal: the rate has fallen to $\frac{1}{3}$, so two out of every three digits you transmit are pure redundancy, and all of that only buys you one correctable error per three digits. Compare the three codes so far:

The obvious question is whether we can get the correcting power of the third row at anything like the rate of the first. The answer is yes, and it comes from linear algebra.

Vectors and Matrices

Before building the good codes, we need a little machinery. Nothing here is deep; it is just a compact language for saying "this collection of digits satisfies this collection of ${\mathbb{Z}}_2$ equations".

Sizes are always quoted as (rows) $\times$ (columns), in that order; getting this backwards is the single most common slip in matrix questions, and it makes every subsequent product illegal.

The transpose is mostly a typographical convenience here: our codewords are naturally written left-to-right as row vectors, but matrices multiply column vectors, so $x^T$ is how a codeword $x$ gets fed into a matrix.

Multiplication is defined by "row against column". The product of a $1\times k$ row vector $u$ with a $k\times 1$ column vector $v$ is the single number

$$uv=(u_1,u_2,\dots ,u_k)(v_1,v_2,\dots ,v_k{)}^T=\sum _{i=1}^k{u}_i{v}_i=u_1{v}_1+u_2{v}_2+\cdots +u_k{v}_k,$$

and to multiply two matrices $A$ and $B$ we create a new matrix $AB$ whose $(i,j)$​th entry is the product of the $i$​th row of $A$ with the $j$​th column of $B$. The case we actually use is a matrix times a column vector: the product of an $a\times b$ matrix $M$ with a $b\times 1$ column vector $v$ is an $a\times 1$ vector $Mv$ whose $k$​th entry is ${\sum }_{i=1}^b{m}_{k,i}{v}_i$. Written out for a $2\times 3$ matrix,

$$\left(\begin{array}{ccc}{m}_{1,1}& m_{1,2}& m_{1,3}\\ m_{2,1}& m_{2,2}& m_{2,3}\end{array}\right)\left(\begin{array}{c}{v}_1\\ v_2\\ v_3\end{array}\right)=\left(\begin{array}{c}{m}_{1,1}{v}_1+m_{1,2}{v}_2+m_{1,3}{v}_3\\ m_{2,1}{v}_1+m_{2,2}{v}_2+m_{2,3}{v}_3\end{array}\right).$$

Basically, each row of the matrix eats the whole vector and produces one number, so the answer has as many entries as $M$ has rows.

Example. What is the product of $\left(\begin{array}{ccc}1& 2& 3\\ 4& 2& 0\end{array}\right)$ and $(1,3,2{)}^T$?
This is a $2\times 3$ matrix times a $3\times 1$ column vector, so the answer is $2\times 1$. Taking each row against the column in turn,

$$\begin{array}{rl}\left(\begin{array}{ccc}1& 2& 3\\ 4& 2& 0\end{array}\right)\left(\begin{array}{c}1\\ 3\\ 2\end{array}\right)& =\left(\begin{array}{c}1(1)+2(3)+3(2)\\ 4(1)+2(3)+0(2)\end{array}\right)\\ & =\left(\begin{array}{c}1+6+6\\ 4+6+0\end{array}\right)\\ & =\left(\begin{array}{c}13\\ 10\end{array}\right).\end{array}$$

Therefore, the product is $(13,10{)}^T$.

For codes we do exactly this arithmetic but in ${\mathbb{Z}}_2$, which is much easier: every entry of the matrix is $0$ or $1$, so a row against a column is just "add up the entries of the vector sitting underneath a $1$, then reduce mod $2$". In other words, the $k$​th entry of $Mv$ over ${\mathbb{Z}}_2$ is $0$ if the positions where row $k$ has a $1$ contain an even number of $1$​s in $v$, and $1$ if they contain an odd number. Every Hamming calculation below is really a stack of parity checks in disguise.

Example. Compute $Mv$ over ${\mathbb{Z}}_2$, where $M=\left(\begin{array}{cccc}1& 0& 1& 1\\ 0& 1& 1& 0\\ 1& 1& 0& 1\end{array}\right)$ and $v=(1,1,0,1{)}^T$.
Reading off which positions of $v$ each row selects,

$$\begin{array}{rl}\text{row }1& :v_1+v_3+v_4=1+0+1=0,\\ \text{row }2& :v_2+v_3=1+0=1,\\ \text{row }3& :v_1+v_2+v_4=1+1+1=1,\end{array}$$

all in ${\mathbb{Z}}_2$. Therefore, $Mv=(0,1,1{)}^T$. Notice that no multiplication was ever performed; over ${\mathbb{Z}}_2$ you only ever count $1$​s and ask whether the count is even or odd.

The Hamming (7,4) Code

A Hamming code is a very efficient type of error-correcting code, in the sense that it minimises the number of check digits required per message while maximising the number of errors that can be detected or corrected. The smallest useful one squeezes $4$ information digits into $7$ transmitted digits, so it corrects a single error at a rate of $\frac{4}{7}$ — compare that with triple reduplication, which needs $12$ digits to protect the same $4$.

Everything is controlled by one matrix.

That last sentence is the whole trick, so make sure you can see it. Reading each column upwards gives a $3$-digit binary string, and those strings run through $1,2,\dots ,7$ in order:

The columns are written bottom-to-top, not top-to-bottom; if you read them the wrong way round every position you report will be the bit-reversal of the truth. A quick way to remember it: the top row is the $1$​s bit, the middle row is the $2$​s bit, the bottom row is the $4$​s bit — the same order as an ordinary binary expansion once you turn your head sideways.

Notice that the columns in positions $1,2$ and $4$ are exactly the standard basis vectors $e_1,e_2,e_3$. Those are the positions that will hold the check digits, and it is no accident; a check digit whose column is $e_j$ appears in the $j$​th equation and no other, so each check digit can be solved for on its own.

Encoding

Basically, the information digits $a,b,c,d$ are dropped into positions $3,5,6,7$ untouched, and the three check digits at positions $1,2,4$ are each a parity check over a carefully chosen subset of them. The rule is not arbitrary; each check digit exists to make one row of $H$ sum to zero. Reading the equation $H{x}^T=0$ row by row with $x_3=a$, $x_5=b$, $x_6=c$, $x_7=d$,

$$\begin{array}{rlrl}\text{row }1& :x_1+x_3+x_5+x_7=0& & ⟹x_1=a+b+d,\\ \text{row }2& :x_2+x_3+x_6+x_7=0& & ⟹x_2=a+c+d,\\ \text{row }3& :x_4+x_5+x_6+x_7=0& & ⟹x_4=b+c+d,\end{array}$$

where we used that $-1=1$ in ${\mathbb{Z}}_2$ so moving a term across the equals sign changes nothing. That derivation is worth internalising, because it is exactly what you repeat when the matrix changes.

Example. Using the standard Hamming $(7,4)$ code, encode the message $(1,1,0,1)$.
Here $a=1$, $b=1$, $c=0$, $d=1$, so the three check digits are

$$\begin{array}{rl}a+b+d& =1+1+1\\ & =1,\\ a+c+d& =1+0+1\\ & =0,\\ b+c+d& =1+0+1\\ & =0,\end{array}$$

all in ${\mathbb{Z}}_2$. Slotting these into positions $1,2,4$ and the information digits into positions $3,5,6,7$,

$$x=(1,0,1,0,1,0,1).$$

As a check, $H{x}^T$ should be the zero vector; row $1$ selects positions $1,3,5,7$ giving $1+1+1+1=0$, row $2$ selects positions $2,3,6,7$ giving $0+1+0+1=0$, and row $3$ selects positions $4,5,6,7$ giving $0+1+0+1=0$. Therefore, the encoded message is $(1,0,1,0,1,0,1)$, and it is a legal codeword.

Example. Using the standard Hamming $(7,4)$ code, encode the message $(1,0,1,0)$.
Now $a=1$, $b=0$, $c=1$, $d=0$, so

$$\begin{array}{rl}a+b+d& =1+0+0=1,\\ a+c+d& =1+1+0=0,\\ b+c+d& =0+1+0=1,\end{array}$$

in ${\mathbb{Z}}_2$. Therefore, the encoded message is $(1,0,1,1,0,1,0)$. Checking against $H$ once more: positions $1,3,5,7$ give $1+1+0+0=0$; positions $2,3,6,7$ give $0+1+1+0=0$; positions $4,5,6,7$ give $1+0+1+0=0$, so $H{x}^T=0$ as required. Always run this check; it costs three additions and catches every arithmetic slip you could have made in the encoding.

Decoding

Basically, $z$ is a three-digit binary number that is the position of the broken digit, spelled out bottom-to-top. That is why the columns of $H$ were arranged in counting order in the first place; the matrix is designed so that the error announces its own address.

Example. Using the standard Hamming $(7,4)$ code, decode the received message $(1,0,1,1,0,0,1)$, assuming there is at most one error.
Write $y=(1,0,1,1,0,0,1)$ and compute $z=H{y}^T$ one row at a time, remembering that each row just adds up the entries of $y$ in the positions where that row of $H$ has a $1$:

$$\begin{array}{rl}{z}_1& =y_1+y_3+y_5+y_7\\ & =1+1+0+1\\ & =1,\\ z_2& =y_2+y_3+y_6+y_7\\ & =0+1+0+1\\ & =0,\\ z_3& =y_4+y_5+y_6+y_7\\ & =1+0+0+1\\ & =0,\end{array}$$

all in ${\mathbb{Z}}_2$, so

$$z=\left(\begin{array}{c}1\\ 0\\ 0\end{array}\right)\ne 0.$$

Since $z\ne 0$ there is an error, and $z=(1,0,0{)}^T$ is the first column of $H$; equivalently, reading $z$ from bottom to top gives $001=1$. So the error is in position $1$. Flipping that digit gives the corrected codeword

$$(0,0,1,1,0,0,1),$$

and extracting positions $3,5,6,7$ gives the message digits $(1,0,0,1)$. Therefore, the decoded message is $(1,0,0,1)$. As a sanity check, encoding $(1,0,0,1)$ gives check digits $a+b+d=1+0+1=0$, $a+c+d=1+0+1=0$ and $b+c+d=0+0+1=1$, i.e. the codeword $(0,0,1,1,0,0,1)$ — exactly the corrected word, so everything is consistent.

Example. Assuming there is at most one error, decode $(1,1,0,1,0,1,1)$ using the standard Hamming $(7,4)$ code.
Computing $z=H{y}^T$ over ${\mathbb{Z}}_2$,

$$\begin{array}{rl}{z}_1& =y_1+y_3+y_5+y_7=1+0+0+1=0,\\ z_2& =y_2+y_3+y_6+y_7=1+0+1+1=1,\\ z_3& =y_4+y_5+y_6+y_7=1+0+1+1=1,\end{array}$$

so $z=(0,1,1{)}^T$. Reading bottom to top, $110=6$, and indeed $(0,1,1{)}^T$ is the sixth column of $H$; the error is in position $6$. Flipping it gives $(1,1,0,1,0,0,1)$, whose digits in positions $3,5,6,7$ are $(0,0,0,1)$. Therefore, the decoded message is $(0,0,0,1)$. Checking: encoding $(0,0,0,1)$ gives $a+b+d=1$, $a+c+d=1$, $b+c+d=1$, i.e. $(1,1,0,1,0,0,1)$, which matches.

Example. Assuming there is at most one error, decode $(1,0,1,0,1,0,1)$.
Computing the three parities,

$$\begin{array}{rl}{z}_1& =1+1+1+1=0,\\ z_2& =0+1+0+1=0,\\ z_3& =0+1+0+1=0,\end{array}$$

so $z=0$. Therefore, no error occurred, and the message is read straight off positions $3,5,6,7$ as $(1,1,0,1)$ — which is exactly the message we encoded in the first example of this section, as it should be. When $z=0$ you do not "correct" anything; you read the message off the received word unchanged.

Non-Standard Hamming Codes

Why does the decoding rule work at all? The argument is short and it is the most important paragraph in the lecture, because it tells you exactly how much freedom you have in choosing $H$.

Suppose a single error occurs at position $i$. Over ${\mathbb{Z}}_2$, flipping the $i$​th digit is the same as adding $1$ to it, so the received word $y$ is related to the sent word $x$ by

$$y^T=x^T+e_i\text{ over }{\mathbb{Z}}_2,$$

where $e_i$ is the $i$​th standard basis vector. Then, using that matrix multiplication distributes over addition and that $H{x}^T=0$ for every codeword,

$$\begin{array}{rl}H{y}^T& =H(x^T+e_i)\\ & =H{x}^T+H{e}_i\\ & =0+H{e}_i\\ & =H{e}_i,\end{array}$$

and $H{e}_i$ is precisely the $i$​th column of $H$ (multiplying by $e_i$ picks out column $i$ and kills everything else). So:

$$\boxed{z=H{y}^T\text{ is exactly the column of }H\text{ sitting at the position of the error.}}$$

Basically, the syndrome $z$ does not know or care what the message was; it only sees the error. And notice what the argument never used: it never used the fact that the columns of $H$ were the numbers $1$ through $7$ in order. All it needs is that the columns are distinct and nonzero, so that "the column matching $z$" picks out a unique position.

This tells us that the decoding method will work regardless of the matrix $H$ used, implying that variations of the standard Hamming $(7,4)$ code exist where a different matrix $H^{\prime }$ uses some permutation of the original columns. With such an $H^{\prime }$ we still calculate $z=H^{\prime }{y}^T$, and (assuming at most one error) if $z=0$ then there are no errors, while otherwise there is one error at the position corresponding with the column in $H^{\prime }$ that matches $z$.

The error-checking method is unchanged, but the encoding rule certainly is not. The check digits are always determined by insisting that $H^{\prime }{x}^T=0$, and you have to redo the row-by-row solve to find out what they are. The other feature that may change is where the check and information digits sit: typically the check digits are placed so that their corresponding columns in $H^{\prime }$ are the standard basis vectors $e_i$, because then each check digit appears in exactly one of the three equations and can be read off immediately. If you put a check digit somewhere else, the three equations tangle together and you have to solve a genuine simultaneous system.

Example. Consider the non-standard Hamming matrix

$$H^{\prime }=\left(\begin{array}{ccccccc}1& 0& 0& 1& 1& 1& 0\\ 0& 1& 0& 1& 1& 0& 1\\ 0& 0& 1& 1& 0& 1& 1\end{array}\right).$$

Supposing that the information digits are in the last four positions, decode the received message $y=(1,0,1,1,1,0,1)$, assuming at most one error.
First read off which positions each row of $H^{\prime }$ selects: row $1$ has $1$​s in positions $1,4,5,6$; row $2$ in positions $2,4,5,7$; row $3$ in positions $3,4,6,7$. Computing $z=H^{\prime }{y}^T$ over ${\mathbb{Z}}_2$,

$$\begin{array}{rl}{z}_1& =y_1+y_4+y_5+y_6\\ & =1+1+1+0\\ & =1,\\ z_2& =y_2+y_4+y_5+y_7\\ & =0+1+1+1\\ & =1,\\ z_3& =y_3+y_4+y_6+y_7\\ & =1+1+0+1\\ & =1,\end{array}$$

so $z=(1,1,1{)}^T\ne 0$ and an error has occurred. Now hunt for the column of $H^{\prime }$ equal to $(1,1,1{)}^T$; scanning across, the only all-ones column is the fourth. Do not convert $z$ to a number here — with a non-standard matrix the columns are not in counting order, so position $4$ has nothing to do with $z$ "being" $7$ in binary; you must physically match the column. Flipping digit $4$ of $y$ gives the corrected codeword

$$(1,0,1,0,1,0,1),$$

and since the information digits live in the last four positions, the message is $(0,1,0,1)$. Therefore, the decoded message is $(0,1,0,1)$.

Example. Find the encoding rule for the previous Hamming code, using the same non-standard Hamming matrix $H^{\prime }$, where the information digits are placed in the last four positions.
Write the codeword as $x=(x_1,x_2,x_3,a,b,c,d)$, so that $x_1,x_2,x_3$ are the check digits and $a,b,c,d$ are the information digits. Notice first that the columns in positions $1,2,3$ of $H^{\prime }$ are $e_1,e_2,e_3$, so each check digit appears in exactly one equation; this is the situation we wanted. Now impose $H^{\prime }{x}^T=0$ row by row:

$$\begin{array}{rlrl}\text{row }1& :x_1+a+b+c=0& & ⟹x_1=a+b+c,\\ \text{row }2& :x_2+a+b+d=0& & ⟹x_2=a+b+d,\\ \text{row }3& :x_3+a+c+d=0& & ⟹x_3=a+c+d,\end{array}$$

where again we used $-1=1$ in ${\mathbb{Z}}_2$, so rearranging never introduces a minus sign. Therefore, the encoding rule is

$$x=(a+b+c,a+b+d,a+c+d,a,b,c,d),$$

with all entries computed in ${\mathbb{Z}}_2$.

As a sanity check, run the message $(a,b,c,d)=(0,1,0,1)$ recovered in the previous example through this rule:

$$\begin{array}{rl}a+b+c& =0+1+0=1,\\ a+b+d& =0+1+1=0,\\ a+c+d& =0+0+1=1,\end{array}$$

giving $x=(1,0,1,0,1,0,1)$, which is exactly the corrected codeword we obtained. Two independent calculations agreeing like this is the best evidence you will get in an exam that both of them are right.

Example. Consider the non-standard Hamming matrix

$$H^{\prime \prime }=\left(\begin{array}{ccccccc}1& 1& 1& 0& 1& 0& 0\\ 0& 1& 1& 1& 0& 1& 0\\ 1& 1& 0& 1& 0& 0& 1\end{array}\right)$$

over ${\mathbb{Z}}_2$, where the last three entries of an encoded message are the check digits.
(a) Find the encoding rule.
(b) Assuming there is at most one error, decode the message $(0,0,0,1,1,1,0)$.

(a) The columns in positions $5,6,7$ are $e_1,e_2,e_3$, which is consistent with the check digits being placed there. Write $x=(a,b,c,d,x_5,x_6,x_7)$. Row $1$ has $1$​s in positions $1,2,3,5$; row $2$ in positions $2,3,4,6$; row $3$ in positions $1,2,4,7$. Imposing $H^{\prime \prime }{x}^T=0$,

$$\begin{array}{rlrl}\text{row }1& :a+b+c+x_5=0& & ⟹x_5=a+b+c,\\ \text{row }2& :b+c+d+x_6=0& & ⟹x_6=b+c+d,\\ \text{row }3& :a+b+d+x_7=0& & ⟹x_7=a+b+d.\end{array}$$

Therefore, the encoding rule is $x=(a,b,c,d,a+b+c,b+c+d,a+b+d)$.

(b) With $y=(0,0,0,1,1,1,0)$, computing $z=H^{\prime \prime }{y}^T$ over ${\mathbb{Z}}_2$,

$$\begin{array}{rl}{z}_1& =y_1+y_2+y_3+y_5\\ & =0+0+0+1\\ & =1,\\ z_2& =y_2+y_3+y_4+y_6\\ & =0+0+1+1\\ & =0,\\ z_3& =y_1+y_2+y_4+y_7\\ & =0+0+1+0\\ & =1,\end{array}$$

so $z=(1,0,1{)}^T$, which matches the first column of $H^{\prime \prime }$. Flipping digit $1$ gives the corrected codeword $(1,0,0,1,1,1,0)$, and the information digits are the first four, namely $(1,0,0,1)$. Therefore, the decoded message is $(1,0,0,1)$. Checking against part (a) with $a=1,b=0,c=0,d=1$: $x_5=1+0+0=1$, $x_6=0+0+1=1$, $x_7=1+0+1=0$, giving $(1,0,0,1,1,1,0)$ as required.

Notice how in both non-standard examples the answer came out of the same three-step routine, and the matrix never had to be memorised:

• Identify which positions hold check digits (look for the columns that are $e_1,e_2,e_3$).
• For the encoding rule, read each row of $H^{\prime }$ as "the sum of the digits in these positions is $0$", and solve each row for its check digit.
• For decoding, compute $z=H^{\prime }{y}^T$ by the same row-selects-positions rule, then match $z$ against the columns of $H^{\prime }$ by eye.

Larger Hamming Codes

The Hamming $(7,4)$ code is so-called because it encodes messages of length $4$ as messages of length $7$; that is, it introduces $3$ check digits. Hamming codes of other sizes are designed in exactly the same fashion, and the pattern is driven entirely by the columns.

With $r$ rows, the columns of $H$ can be any nonzero binary strings of length $r$, and there are $2^r-1$ of those; so the longest codeword we can protect with $r$ check digits has $2^r-1$ digits, of which $2^r-1-r$ carry information. This gives the family

$$\boxed{\text{Hamming }(2^r-1,2^r-1-r)\text{ for }r=2,3,4,\dots }$$

so $r=3$ gives $(7,4)$, $r=4$ gives $(15,11)$, $r=5$ gives $(31,26)$, and so on. Notice what happens to the rate: $\frac{4}{7}\approx 0.57$, then $\frac{11}{15}\approx 0.73$, then $\frac{26}{31}\approx 0.84$. Bigger Hamming codes are much more efficient, but they still only correct one error per block; a long block is a bigger target, so the single-error assumption gets harder to justify as $r$ grows. That trade-off is the whole design problem.

The next one up uses the standard Hamming $(15,11)$ matrix

$$H=\left(\begin{array}{ccccccccccccccc}1& 0& 1& 0& 1& 0& 1& 0& 1& 0& 1& 0& 1& 0& 1\\ 0& 1& 1& 0& 0& 1& 1& 0& 0& 1& 1& 0& 0& 1& 1\\ 0& 0& 0& 1& 1& 1& 1& 0& 0& 0& 0& 1& 1& 1& 1\\ 0& 0& 0& 0& 0& 0& 0& 1& 1& 1& 1& 1& 1& 1& 1\end{array}\right),$$

whose columns are the integers $1$ through to $15$ in binary, reading from bottom to top. The rows are exactly the $1$​s bit, the $2$​s bit, the $4$​s bit and the $8$​s bit of the column number, which is why each row looks like a doubling of the pattern above it: alternate singles, then pairs, then fours, then eights.

You do not have to memorise those four formulas, and you should not try; they are just the same row-by-row solve applied to a bigger matrix. The check digits sit at positions $1,2,4,8$ (the powers of $2$, which are exactly the positions where the column of $H$ is a standard basis vector), and $c_j$ is the sum of every information digit whose position has a $1$ in the $j$​th bit. For instance row $1$ of $H$ has $1$​s at the odd positions $1,3,5,7,9,11,13,15$, and dropping $x_1=c_1$ out of that list leaves positions $3,5,6,\dots$ holding $a_1,a_2,a_4,a_5,a_7,a_9,a_{11}$ — which is precisely the formula for $c_1$.

Example. Using the standard Hamming $(15,11)$ code, encode the message $(1,0,1,0,1,0,1,0,1,0,1)$.
Here $a_1=1,a_2=0,a_3=1,a_4=0,a_5=1,a_6=0,a_7=1,a_8=0,a_9=1,a_{10}=0,a_{11}=1$. Computing the four check digits in ${\mathbb{Z}}_2$,

$$\begin{array}{rl}{c}_1& =a_1+a_2+a_4+a_5+a_7+a_9+a_{11}\\ & =1+0+0+1+1+1+1\\ & =1,\\ c_2& =a_1+a_3+a_4+a_6+a_7+a_{10}+a_{11}\\ & =1+1+0+0+1+0+1\\ & =0,\\ c_3& =a_2+a_3+a_4+a_8+a_9+a_{10}+a_{11}\\ & =0+1+0+0+1+0+1\\ & =1,\\ c_4& =a_5+a_6+a_7+a_8+a_9+a_{10}+a_{11}\\ & =1+0+1+0+1+0+1\\ & =0.\end{array}$$

Slotting the check digits into positions $1,2,4,8$ and the information digits into the rest,

$$x=(1,0,1,1,0,1,0,0,1,0,1,0,1,0,1).$$

Therefore, the encoded message is $(1,0,1,1,0,1,0,0,1,0,1,0,1,0,1)$. (Counting $1$​s in the odd positions gives $1+1+0+0+1+1+1+1=6$, which is even, so row $1$ of $H$ checks out; the other three rows check the same way.)

Example. Assuming there is at most one error, decode $(1,1,0,1,1,0,1,1,0,1,1,0,1,1,0)$ using the standard Hamming $(15,11)$ code.
Each row of $H$ selects the positions where that row has a $1$, so

$$\begin{array}{rl}{z}_1& =y_1+y_3+y_5+y_7+y_9+y_{11}+y_{13}+y_{15}\\ & =1+0+1+1+0+1+1+0\\ & =1,\\ z_2& =y_2+y_3+y_6+y_7+y_{10}+y_{11}+y_{14}+y_{15}\\ & =1+0+0+1+1+1+1+0\\ & =1,\\ z_3& =y_4+y_5+y_6+y_7+y_{12}+y_{13}+y_{14}+y_{15}\\ & =1+1+0+1+0+1+1+0\\ & =1,\\ z_4& =y_8+y_9+y_{10}+y_{11}+y_{12}+y_{13}+y_{14}+y_{15}\\ & =1+0+1+1+0+1+1+0\\ & =1,\end{array}$$

all in ${\mathbb{Z}}_2$, so $z=(1,1,1,1{)}^T$. Reading bottom to top gives $1111=15$, so the error is in position $15$. Flipping that digit gives the corrected codeword

$$(1,1,0,1,1,0,1,1,0,1,1,0,1,1,1),$$

and deleting the check digits at positions $1,2,4,8$ leaves the information digits at positions $3,5,6,7,9,10,\dots ,15$:

$$(0,1,0,1,0,1,1,0,1,1,1).$$

Therefore, the decoded message is $(0,1,0,1,0,1,1,0,1,1,1)$. (Recomputing $z$ on the corrected word gives $(0,0,0,0{)}^T$, confirming that it is now a legal codeword.)

Codes that can correct multiple errors do exist, but they need more machinery than we have; that idea gets picked up again in Topic 9.

What Hamming Codes Can and Cannot Do

It is worth being very precise about the guarantee, because the phrasing "assuming there is at most one error" is doing enormous work.

If exactly one error occurs, the code always corrects it: we proved above that $z=H{e}_i$ is column $i$, the columns are distinct, so the position is pinned down uniquely and flipping it restores the sent word. If no error occurs, $z=0$ and nothing is touched. So far so good.

Now suppose two errors occur, at positions $i$ and $j$. The same computation gives

$$\begin{array}{rl}H{y}^T& =H(x^T+e_i+e_j)\\ & =0+H{e}_i+H{e}_j\\ & =(\text{column }i)+(\text{column }j),\end{array}$$

which is nonzero (the columns are distinct, so their ${\mathbb{Z}}_2$ sum cannot be zero). The receiver therefore does see that something is wrong — but the sum of two columns is itself a column, so the decoder happily concludes "one error, at position $k$", flips a third perfectly good digit, and hands over a legal-looking codeword that is not the one you sent.

Example. The codeword $x=(1,0,1,0,1,0,1)$ (the encoding of $(1,1,0,1)$) is sent and the first two digits are flipped, so $y=(0,1,1,0,1,0,1)$ arrives. What does the standard decoder report?
Computing $z=H{y}^T$,

$$\begin{array}{rl}{z}_1& =y_1+y_3+y_5+y_7=0+1+1+1=1,\\ z_2& =y_2+y_3+y_6+y_7=1+1+0+1=1,\\ z_3& =y_4+y_5+y_6+y_7=0+1+0+1=0,\end{array}$$

so $z=(1,1,0{)}^T$, which is column $3$ of $H$ (bottom to top, $011=3$). The decoder therefore "corrects" position $3$, producing $(0,1,0,0,1,0,1)$, and reads the message off positions $3,5,6,7$ as $(0,1,0,1)$. Therefore, the decoder confidently returns $(0,1,0,1)$ when the true message was $(1,1,0,1)$; it has flagged an error, mis-located it, and made the word more wrong. The plain Hamming $(7,4)$ code corrects one error, but it does not reliably detect two; with two errors it will silently mis-correct into a different valid codeword. (Real systems fix this by appending one extra overall parity digit, giving a code that corrects one error and detects two — but that is not the code you are given here, so do not claim double-error detection in an exam.)

The standard traps, collected in one place:

• Reading the columns of $H$ top-to-bottom instead of bottom-to-top. Position $3$ has column $(1,1,0{)}^T$, not $(0,1,1{)}^T$; getting this backwards swaps positions $3\leftrightarrow 6$ and $1\leftrightarrow 4$ and gives a wrong answer that still "looks" plausible.
• Converting $z$ to a decimal number when the matrix is non-standard. The "read $z$ as a binary number" shortcut is a coincidence of the standard matrix having its columns in counting order; for any $H^{\prime }$ you must match $z$ against the columns physically.
• Forgetting to correct before extracting. The message digits come from the corrected word, not the received one. If $z\ne 0$ and the flagged position happens to be an information digit, extracting from $y$ directly gives the wrong message.
• Forgetting where the information digits live. For the standard $(7,4)$ code they are at positions $3,5,6,7$; for a non-standard code they can be anywhere, and the question will tell you. Read that sentence twice.
• Doing the arithmetic over $\mathbb{Z}$ instead of ${\mathbb{Z}}_2$. A check digit is never $2$ or $3$; reduce mod $2$ at every step (see Modular Rings and Units if you want the general story).
• Quoting the encoding rule of the standard code for a non-standard matrix. The decoding method is matrix-independent by the $H{e}_i$ argument; the encoding rule is not, and must be re-derived from $H^{\prime }{x}^T=0$ every single time.

Stepping back, the whole lecture is one idea repeated at increasing levels of cleverness. A parity check imposes one linear equation on the transmitted digits and buys you detection of an odd number of errors for one extra digit. Reduplication imposes many equations and buys correction, but at a rate of $\frac{1}{2}$ or $\frac{1}{3}$. Hamming codes impose $r$ carefully chosen equations — one per row of $H$ — and arrange the columns so that the failed equations spell out the address of the broken digit in binary; that gets you single-error correction at a rate of $\frac{2^r-1-r}{2^r-1}$, which tends to $1$ as $r$ grows. Redundancy is the price of reliability, and Hamming's contribution was working out how little of it you actually have to pay.