Introduction
The binary Hamming code corrects any single bit flip. Its minimum distance is , so it cannot reliably distinguish one flip from two. A double flip produces the same kind of syndrome as a single flip, and a decoder that "corrects" it makes the word worse.
Appending one overall parity bit fixes this problem. The result is the extended Hamming code . With an explicit promise about how many bits may flip, its decoder can do three things:
- correct any single flip;
- recognize any double flip as uncorrectable;
- never confuse a single flip with a double flip.
This behavior is called SECDED: single-error correction, double-error detection.
This note builds that decoder end to end. It also states precisely what the decoder does not promise. Every actual single-bit error is corrected and every actual double-bit error is flagged. The promise of at most two flips lets us infer which of those cases occurred from the syndrome. Without that promise, the same decoder can return a valid codeword that is wrong.
Throughout, all arithmetic is in , so . Words are row vectors indexed by positions , read from left to right.
The parity-check matrix
We label each position by a vector :
The first seven labels are exactly the seven nonzero vectors of . The eighth label is the zero vector. All eight labels are therefore distinct. This single fact drives most of what follows.
Definition 1.2.1
(Extended Hamming parity-check matrix)
Let be the matrix over defined as follows:
- column has (written as a column) in its first three entries;
- every column has in its fourth entry.
Explicitly,
Here is the Hamming parity-check matrix with columns , and is the all-ones row of length .
The extended Hamming code is
It is useful to record which positions each row checks. Row 1 checks positions . Row 2 checks . Row 3 checks . Row 4 checks all eight positions.
Theorem 1.2.2
(Rank and dimension)
The matrix has rank . Consequently is a linear code of length and dimension , so it has codewords.
Proof
(Four columns forming a triangular matrix)
Consider columns of :
Placed side by side, they form a lower-triangular matrix with every diagonal entry equal to . Its determinant is therefore , so these four columns are linearly independent.
This shows that has rank at least . It cannot exceed , because has only four rows. By rank–nullity, .
What the four checks mean
Write and . The condition splits into two parts:
The first three rows involve only the first seven positions, because the eighth column begins with . These rows say exactly that is a Hamming codeword. The fourth row says that the full word has even weight.
So, given a Hamming codeword , there is exactly one bit such that , namely
This bit is when has even weight and when has odd weight. It follows that is precisely the parity extension of the Hamming code. This agrees with the dimension count: the Hamming code has codewords, and each extends uniquely.
Concept lensAlgebraic
The check matrix also generates the code
Each row of has even weight, and any two rows share an even number of positions: rows 1 to 3 pairwise share two, and each shares four with row 4. Hence every row passes all four checks and lies in . Since has rank , its rows form a basis, so equals its own dual. Moreover , and orthogonal words share an even number of ones, so weights divisible by four stay so under sums. Starting from row weights , every codeword weight is , or , which gives again.
Minimum distance four
Theorem 1.2.3
(Minimum distance)
The code has minimum distance exactly .
Proof
(Why no nonzero codeword has weight one, two or three)
Reduction. is linear. The distance between codewords and equals the weight of , which is again a codeword. So the minimum distance equals the minimum weight of a nonzero codeword.
Key identity. If has support , then . Hence
Odd weights are excluded. If is odd, the last entry is , so . This rules out weight and weight in one step. It is the work done by the all-ones row.
Weight two is excluded. If with , the first three entries are . In , holds exactly when , and the labels are distinct. So and . This is the work done by the distinct column labels. The case is included: then , which is nonzero for .
Weight four is attained. Take , which has support . Then
and is even. So and is a codeword of weight .
Proof X-ray
One job for each part of the matrix
The key move is the identity that splits a syndrome into the sum of the labels on the support and the parity of the support size. After it, each part of does one job. The parity row excludes all odd weights in a single step. The distinctness of the eight labels, including the zero label , excludes weight two. Neither part alone gives distance : the Hamming matrix alone allows the weight-3 word , and the parity row alone allows the weight-2 word . The final step is not optional: excluding weights one to three only shows , and the explicit codeword closes the argument by showing .
The same split of the syndrome into a label part and a parity part is what the decoder reads below.
Syndromes and detection
Definition 1.2.4
(Syndrome)
For a received word , the syndrome is
Suppose , where was transmitted and is the error pattern. Then . The syndrome depends only on the error, never on the codeword. By the key identity, an error with support has
Theorem 1.2.5
(Distance d detects up to d−1 errors)
Let be a linear code with minimum distance , and let satisfy . Then for every , the word is not a codeword.
Proof
(A detected error would itself be a light codeword)
Suppose . Then by linearity. But is nonzero with weight less than , which contradicts the definition of .
For our code, . So every error of weight , or produces a nonzero syndrome. The membership test "is ?" therefore fails for all such errors.
This is a statement about detection before any correction is attempted. It says nothing about what a correcting decoder will then do with the word.
The SECDED decoder and its promise
Theorem 1.2.6
(Exact classification under the promise of at most two flips)
Assume that with and . Then the syndrome determines the error weight, and the following rules are exhaustive.
- . No error occurred, and .
- . Exactly one bit flipped. Its position is the unique with . In particular, identifies the parity bit, position . Flipping recovers .
- . Exactly two bits flipped. The decoder must declare the word uncorrectable. It must not attempt to identify the pair.
Proof
(The three syndrome cases are disjoint)
Consider each possible error weight.
- Weight . The syndrome is .
- Weight , position . The syndrome is . Every is the label of exactly one position, because the eight labels are distinct and . So is determined by .
- Weight , positions . The syndrome is . We showed above that , so .
The three outcome sets , and are pairwise disjoint. Under the promise, the observed case therefore pins down the weight of .
Why the pair cannot be identified. There are two-position errors but only nonzero values of . Each nonzero is the sum of exactly pairs: for each position the partner is forced by , which gives ordered and hence unordered pairs. So rule 3 always faces a fourfold ambiguity.
Common mistake
(Ignoring the parity bit and decoding with the label alone)
A decoder that reads only and flips the position labeled , as the Hamming decoder would, turns a double error into a triple error. From with flips at and , the received word has . Flipping position gives , whose first seven bits form the Hamming codeword , so the data part is now confidently wrong. Rule 3 exists precisely to stop this: when and , nothing is flipped.
Common mistake
(Distance four does not correct two errors)
Correcting every pattern of errors requires , so gives , not . Concretely, is a codeword (support , labels summing to zero, even size), and the received word is at distance from both and . The fourth unit of distance buys detection of the second error, not its correction.
Worked traces
In all three traces the transmitted word is .
Worked example 1.2.7
(Single flip at position 5)
The received word is . Row by row:
- Row 1 checks and contains one , so the bit is .
- Row 2 checks and contains no , so the bit is .
- Row 3 checks and contains one , so the bit is .
- Row 4 counts one in total, so the bit is .
The syndrome is . Since , rule 2 applies, and . The decoder flips position and outputs , which is correct.
Worked example 1.2.8
(Double flip at positions 1 and 2)
The received word is . Row 1 gives (position 1). Row 2 gives (position 2). Row 3 gives . Row 4 counts two ones, so it gives .
The syndrome is . Since and , rule 3 applies, and the decoder flags the word as uncorrectable.
Now compare the error at positions and , which gives . Its syndrome is , with . So produces the same syndrome .
In fact, four pairs produce : , , and . The syndrome alone cannot choose among them.
Worked example 1.2.9
(Triple flip at positions 1, 2 and 4)
The received word is . Row 1 sees positions and , so it gives . Row 2 sees positions and , so it gives . Row 3 gives . Row 4 counts three ones, so it gives .
The syndrome is . This is nonzero, so the error is detected: .
A decoder applying the rules, however, reads and . It flips position and outputs . That is a genuine nonzero codeword, but it is not the codeword that was transmitted. This is a miscorrection.
The explorer below lets you flip any bits of a chosen codeword and shows the syndrome (u, z), the rule applied and the decoder output, so you can see single flips corrected, double flips flagged and triple flips miscorrected.
Outside the promise
Counterexample mode
A valid output is not a correct output
Tempting claim. "SECDED corrects every single error and detects every double error, so whenever it returns a codeword without raising a flag, the message is right."
Counterexample. The third trace refutes this. Three flips produced the syndrome , which is identical to the syndrome of a single flip at position . The decoder returned the valid codeword and raised no flag, yet the message was wrong.
A stronger failure. The error is itself a codeword. Hence , and passes as error-free. The decoder outputs the wrong codeword with no warning of any kind.
The third trace is not a rare accident. The next theorem shows it happens for every triple error.
Theorem 1.2.10
(Every triple error is miscorrected)
Let . Then the syndrome of has . The rule-based decoder flips one position and outputs a codeword different from .
Proof
(The flip lands on a codeword at distance four)
Odd weight gives . The decoder flips the position with . After the flip, the syndrome becomes
so the output is a codeword . Hence . Moreover, is nonzero, because a weight-3 vector cannot equal a weight-1 vector. Therefore the output differs from . Since has no nonzero codewords of weight below and has weight at most , its weight is exactly .
The precise promises are therefore these:
- Without any promise. Every error of weight to is detected by the membership test before correction. Every single-bit error is corrected, but the syndrome alone cannot certify the true error weight. Some weight-4 errors, namely those that are codewords such as , are not detected at all.
- Under the promise . Single flips are corrected, and double flips are flagged. No specific double-error pattern is ever identified.
Claiming "detects two, corrects one" without stating the promise invites a false conclusion. In a model where three flips are possible, the correcting rule converts every detectable triple error into a silent wrong answer. This note makes no claim about how likely any error pattern is in physical hardware, and none about security against an adversary who chooses errors deliberately.
Quick check
(Under the promise of at most two flips, the syndrome is . What does the decoder do?)
Solution · Answer
Since , exactly one bit flipped. The label equals , so the decoder flips position .
Exercises
Quick check
(The word is a Hamming codeword. Find its extended codeword and verify it with .)
Solution · Guided solution
The bits are . First check that is a Hamming codeword: its support is , and , as required.
The weight of is , which is odd, so the parity bit is . The extended word is .
Verification with :
- Row 1 checks . Positions and hold ones, so the sum is .
- Row 2 checks . Positions and hold ones, so the sum is .
- Row 3 checks . None of these hold ones, so the sum is .
- Row 4 counts four ones in total, so the sum is .
Hence and .
Quick check
(The codeword is sent, and only the parity bit flips. Compute the syndrome and decode under the promise of at most two flips.)
Solution · Guided solution
The received word is . Since , the syndrome is . Row by row:
- Row 1: positions and hold ones, so the bit is .
- Row 2: positions and hold ones, so the bit is .
- Row 3: no ones, so the bit is .
- Row 4: three ones, so the bit is .
Rule 2 applies with , so the decoder flips position and recovers , which is correct.
This received word is identical to the one in the triple-error trace. The same can arise from a single flip of or from three flips of . Only the promise selects the first interpretation.
Quick check
(Starting from , show that the errors at and at give the same syndrome. Explain what the decoder must do.)
Solution · Guided solution
For the pair : , and .
For the pair : , and .
Both errors give the syndrome . The pairs and give it too.
Since and , rule 3 applies. Under the promise, the decoder knows that exactly two bits flipped but cannot tell which two. It must flag the word as uncorrectable. Flipping any one of the four syndrome-compatible candidate pairs would produce a wrong codeword in three of those four cases.
Quick check
(Starting from , flip positions , , and . What does the receiver observe?)
Solution · Guided solution
The received word is . Row 1 sees positions , giving . Row 2 sees , giving . Row 3 sees nothing, giving . Row 4 counts four ones, giving .
The syndrome is . The receiver accepts as error-free.
This error is undetectable because it is itself a nonzero codeword. The detection theorem covers only weights up to , so it gives no protection here.
Quick check
(Under the promise of at most two flips, explain why the decoder corrects a single flip and flags a double flip. If the promise fails and three bits flip, explain why the same rule miscorrects.)
Solution · Guided solution
Single flips. A single flip at position gives the syndrome . The eight labels are distinct and cover all of , so names exactly one position. Flipping that position restores .
Double flips. A double flip at gives . Because , the vector is nonzero, so the syndrome is neither nor of the form . Rule 3 therefore triggers, and the decoder flags the word. The pair cannot be recovered, because each nonzero arises from four different pairs.
Triple flips. A triple flip has odd weight, so . This is indistinguishable from a single flip. The decoder flips the position whose label is and lands on a codeword . Here is a nonzero codeword of weight , so the output is wrong. For example, the error at gives , and the decoder outputs instead of .
The guarantee is conditional on the promise. Without the promise, a syndrome with does not certify that only one bit flipped.