Parity and Hamming Codes

Detect a flipped bit with parity and correct it with a Hamming code. See why the minimum distance of a code sets what it can do.

You Will Be Able To

  • Compute an even or odd parity bit with an XOR tree, and say which errors it misses.
  • State what a code of minimum distance d can detect and correct.
  • Encode Hamming(7,4) and use the syndrome to find and flip a single wrong bit.
  • Add one bit for SECDED, and locate an error with two-dimensional parity.
Lesson
G1.9
Time
30 min
Runs on
Your browser
Check
5 questions

A memory cell is struck by a particle and one bit of a stored word flips. With one parity bit the memory knows the word is bad, but not which bit. With three check bits it knows exactly which one, and it flips it back.

Inject an Error, Watch the Syndrome
23
22
21
20

Weights show bit magnitudes. For signed values, the leftmost bit has a negative weight.

Unsigned
11

Hamming(7,4), even parity. Positions 1, 2 and 4 hold parity (P); 3, 5, 6 and 7 hold data (D).

P1
P2
D3
P4
D5
D6
D7
  • Parity 1: positions 1, 3, 5, 7
  • Parity 2: positions 2, 3, 6, 7
  • Parity 4: positions 4, 5, 6, 7

Syndrome: 000 — all parity checks pass.

This locates a single flipped bit. Multiple flips can give a misleading syndrome.

  1. The data 1011. The four data bits go to positions 3, 5, 6 and 7. Positions 1, 2 and 4 hold parity. With no error the syndrome is 000.
  2. Flip a bit. Click any received bit. The parity groups that contain it fail, and the syndrome spells out its position in binary.

The widget lists position 1 first, left to right; the lab prints position 7 first. One flipped bit is always found; two flipped bits point the syndrome at a third bit.

Parity: One Bit That Counts the 1s

An even parity bit makes the number of 1s in a word even. It is the XOR of all the data bits. Odd parity is its inverse. The receiver XORs everything again: a 1 means an odd number of bits flipped.

A Parity Tree for Four Bits
A Parity Tree for Four Bitsx01 · XORa=1x23 · XORb=1xp · XORp=0d0=0d1=1d2=0d3=1
d0=0 d1=1 d2=0 d3=1
x01 · XORd0=0, d1=1 → a=1
x23 · XORd2=0, d3=1 → b=1
xp · XORa=1, b=1 → p=0
Read the connections
GateKindInputsOutput
x01XORd0, d1a
x23XORd2, d3b
xpXORa, bp

Outputs: p. MUX inputs: d0, d1, select. Latch/flip-flop inputs: data, enable/clock. Unknown values are marked x; high impedance is folded into x in this model.

Gate delay 6. Settled after 6 gate delays from t = 0.

Output values at each gate delay0123456pxx11110
Scroll horizontally ↔
Every computed frame
Timep
0x
1x
21
31
41
51
60

  1. Step 2. 1011 has three 1s. Two levels of XOR give p = 1, which makes the count even.
  2. Step 6. Bit 0 changes, so the count is two. After two gate delays p is 0.

A tree of XOR gates computes parity in log2(n) levels. In SystemVerilog the reduction operator ^data builds the same thing.

Distance Decides What a Code Can Do

Lesson G1.8 measured distance as the number of bits two words differ in. The minimum distance d of a code is the smallest distance between two of its codewords.

With d = 2, one flipped bit always lands on a non-codeword, so it is detected. With d = 3, a word one flip away from a codeword is two flips from every other one. The receiver can pick the nearest codeword: it corrects the error.

CodeMinimum distance (measured)Detects up toCorrects up to
4 data bits + 1 parity bit21 errornone
Hamming(7,4)32 errors, if it does not correct1 error
SECDED: Hamming(7,4) + 1 bit42 errors while it corrects 11 error

The rule: distance d detects d - 1 errors and corrects (d - 1)/2 of them, rounded down. The distances are measured on the simulator.

Hamming(7,4): The Syndrome Points at the Error

Number the seven bits 1 to 7. Put parity bits at the powers of two, 1, 2 and 4, and data in 3, 5, 6 and 7. Parity bit 1 checks every position whose binary number has bit 0 set. Parity bit 2 checks bit 1, and parity bit 4 checks bit 2.

Parity bitChecks positionsRule in the lab
11, 3, 5, 7c[1] = c[3] ^ c[5] ^ c[7]
22, 3, 6, 7c[2] = c[3] ^ c[6] ^ c[7]
44, 5, 6, 7c[4] = c[5] ^ c[6] ^ c[7]

Every position is checked by a different set of parity bits, and that set is its binary number.

The receiver recomputes the three checks. The failing checks form a 3-bit number, the syndrome. Zero means no error. Any other value is the position of the flipped bit.

Each Single Error and Its SyndromeThe data 1011 is encoded once. Each column flips one position, from none to 7.
01234567flipped01234567received11001101100111110010011000101101110111011010001100100110syndrome01234567
Scroll horizontally ↔
  1. Cycle 0

    No bit flipped: every check passes and the syndrome is 0.

  2. Cycle 4

    Position 4 is a parity bit. Only its own check fails, so the syndrome is 4.

  3. Cycle 7

    Position 7 is in all three groups, so all three checks fail: syndrome 111, which is 7.

Measured on the simulator. The syndrome equals the flipped position every time, parity positions included.

A Hamming(7,4) DecoderArrows show data. The decoder needs no search: the syndrome is the position to flip.
  • I/O
  • Datapath
  • Control / FSM
  • Data
  • Control
A Hamming(7,4) decoderArrows show data. The decoder needs no search: the syndrome is the position to flip. io Received word positions 1 to 7 datapath Three paritychecks groups 1, 2 and 4 control Syndrome 3 bits: 0 to 7 datapath Flip one bit the position thesyndrome names io Data positions 3, 5, 6, 7 seven bitsone bit per failingcheckwhich positionthe word itselfcorrected word
  1. io Received wordpositions 1 to 7
    • seven bits → Three parity checks
    • the word itself → Flip one bit
  2. datapath Three parity checksgroups 1, 2 and 4
    • one bit per failing check → Syndrome
  3. control Syndrome3 bits: 0 to 7
    • which position → Flip one bit
  4. datapath Flip one bitthe position the syndrome names
    • corrected word → Data
  5. io Datapositions 3, 5, 6, 7
  1. Check

    Each check XORs the four positions of its group. A check that sees an odd count fails.

  2. Syndrome

    The failing checks form a 3-bit number. Check 1 is its bit 0, check 2 its bit 1, check 4 its bit 2.

  3. Correct

    Flip the bit at that position; syndrome 0 flips nothing. Then read the data from positions 3, 5, 6 and 7.

Read the diagram as text
  • Received word: positions 1 to 7
  • Three parity checks: groups 1, 2 and 4
  • Syndrome: 3 bits: 0 to 7
  • Flip one bit: the position the syndrome names
  • Data: positions 3, 5, 6, 7
  • Received word → Three parity checks: seven bits
  • Three parity checks → Syndrome: one bit per failing check
  • Syndrome → Flip one bit: which position
  • Received word → Flip one bit: the word itself
  • Flip one bit → Data: corrected word

An error in a parity position is flipped back too; the data bits were already right.

SECDED: One More Bit

Two errors fool Hamming(7,4): their syndrome names a third bit. One more parity bit over the whole word fixes this. The code is SECDED: single error correction, double error detection.

ReceivedSyndromeOverall parityDecision
as sent0okno error
flip 55brokenone error at position 5, corrected
flip 00brokenone error at position 0, corrected
flip 1 and 23oktwo errors, detected only
flip 3 and 74oktwo errors, detected only

Measured on the simulator for the data 1011. One error breaks the overall parity; two errors leave it intact.

The rule has four cases. Syndrome 0 and parity intact: no error. Parity broken: one error, at the syndrome position, or in the extra bit when the syndrome is 0. Syndrome not 0 and parity intact: two errors, report them and do not correct.

Two-Dimensional Parity

Arrange data bits in a grid and add a parity bit to every row and every column. One flipped bit fails exactly one row and one column, and their crossing is the bit. So 2-D parity also corrects a single error in a data bit.

Bits flippedWhereFailing rows (3..0)Failing columns (3..0)
no errornone00000000
one bitrow 1, column 200100100
two in a rowrow 1, columns 2 and 000000101
two apartrow 1 column 2, row 3 column 010100101
a rectanglerows 1 and 3, columns 2 and 000000000

Measured on the simulator on a 4 x 4 block. Four flips on the corners of a rectangle pass every check.

col 0col 1col 2col 3row parity
row 011011
row 101000 fails
row 201111
row 310001
column parity010 fails0

One flipped bit (red): row 1 and column 2 fail (yellow), and their crossing is the bit to flip back.

col 0col 1col 2col 3row parity
row 011011
row 111000
row 201111
row 310001
column parity0 fails10 fails0

Two flips in row 1: the row parity still holds, but columns 0 and 2 fail. The error is seen, not located.

col 0col 1col 2col 3row parity
row 011011
row 111000
row 201111
row 300101
column parity0100

Four flips on a rectangle: every row and every column keeps its parity, so nothing fails.

A flipped row or column parity bit fails one line only, and no data bit sits under a single failing line. The receiver then knows the data is right.

Two flips in one row are still detected, by their columns, but not located. Four flips on a rectangle are not detected at all. With its row and column bits counted, the code has minimum distance 3, like Hamming(7,4).

Asked in interviews
  1. Which errors does a parity bit miss?

    Any even number of flipped bits. Each pair of flips leaves the count of 1s even, so the check passes.

  2. How does a Hamming code find the wrong bit?

    Each position is covered by the parity checks that match its binary number. The failing checks therefore spell out the position: that is the syndrome.

  3. Why add one more bit to Hamming(7,4)?

    To tell one error from two. One error breaks the overall parity and can be corrected. Two errors leave it intact with a nonzero syndrome, so the decoder reports them.

Try It

The data 1011 becomes the codeword 1100110 with three parity bits. Unchanged, it gives syndrome 0.

Each later line flips one position. The syndrome is the XOR of the positions that hold a 1, and it always equals the flipped position.

Flip two bits at once: add r[2] = ~r[2]; after the first flip. The syndrome now names a third position.

RUNIcarus Verilog · in your browser
Edit the code, then run it
Expected: codeword (positions 7..1): 1100110 flip 0: received 1100110 syndrome 0 flip 1: received 1100111 syndrome 1 flip 2: received 1100100 syndrome 2 flip 3: received 1100010 syndrome 3 flip 4: received 1101110 syndrome 4 flip 5: received 1110110 syndrome 5 flip 6: received 1000110 syndrome 6 flip 7: received 0100110 syndrome 7

Check Yourself

Predict the outputThe program flips two bits of a Hamming(7,4) codeword, at positions 2 and 5. What exact line does it print?
module tb;
  logic [7:1] c, r;
  logic [2:0] s;
  initial begin
    {c[3], c[5], c[6], c[7]} = 4'b0110;
    c[1] = c[3] ^ c[5] ^ c[7];
    c[2] = c[3] ^ c[6] ^ c[7];
    c[4] = c[5] ^ c[6] ^ c[7];
    r = c;
    r[2] = ~r[2];
    r[5] = ~r[5];                   // two bits flipped
    s = 0;
    for (int p = 1; p <= 7; p++) if (r[p]) s = s ^ 3'(p);
    $display("%0d", s);
  end
endmodule
Spot the bugEach option sets the parity bit at position 4. The bench flips each of the 7 bits of all 16 codewords and checks that the syndrome names the flipped bit. Which option fails?
ConceptFour bits flip on the corners of a rectangle in a block with row and column parity. What does the receiver see?
ConceptA SECDED decoder sees a nonzero syndrome and an intact overall parity. What does it do?
ConceptA received word with one parity bit fails the parity check. What does the receiver know?

Common Mistakes

Wrong Believe that parity catches every error.

Two flipped bits leave the count of 1s even, so the parity check still passes.

Fix Parity detects an odd number of errors. Use a code with more distance for more.

Wrong Mix bit positions that start at 0 with positions that start at 1.

The Hamming syndrome names positions 1 to 7. A vector indexed from 0 shifts every correction by one bit.

Fix Declare the codeword as logic [7:1], or add 1 before you compare with the syndrome.

Before
logic [6:0] r;  // r[s] is position s + 1
After
logic [7:1] r;  // r[s] is position s

Wrong Correct whatever the syndrome points at, even after two errors.

Two errors give the syndrome of a third position. Measured: flips at 2 and 5 give syndrome 7, so a third bit gets broken.

Fix Add the overall parity bit (SECDED). Correct only when that parity is broken.

Wrong Forget that the parity bits can be hit too.

An error in a check bit gives a nonzero syndrome like any other.

Fix Treat every position the same: flip the one the syndrome names, then read the data bits.

Remember

  • Even parity is the XOR of the data bits; it detects any odd number of flips.
  • Minimum distance d detects d - 1 errors and corrects (d - 1)/2 of them, rounded down.
  • Hamming(7,4) puts parity at 1, 2 and 4; the syndrome is the position of a single error.
  • SECDED adds an overall parity bit: one error is corrected, two are detected.
  • 2-D parity locates one error by its row and column, and misses four flips on a rectangle.

Practice

Report a problem with this page