In a seven-bit codeword carrying four data bits, how do the three parity-check bits tell a decoder which bit flipped?

middlemust knowfreq 55%

answer

checks sit at the powers of two
a position's index lists its checks
recomputed checks form one binary number
zero means clean, otherwise it points
no table lookup, no codeword search

basics

~20 s

Each check covers a fixed subset of positions, chosen so the three recomputed checks read as a binary number equal the index of the flipped bit. That number is the syndrome; zero means no single flip was seen.

solid answer

~50 s

Number the seven positions 1 to 7 and put the check bits at the powers of two - positions 1, 2 and 4 - leaving positions 3, 5, 6 and 7 for data. The check at position 2^i covers every position whose index has bit i set, and its value is chosen so that the covered set has even parity. On a read the decoder recomputes all three checks. Reading them as a three-bit number, low check first, gives the syndrome: 000 means no single flip, and any other value is the index of the position that flipped. A flip at position 5 fails the checks at 1 and 4 but not the one at 2, giving 101 - five. The decoder inverts that bit and the word is repaired, with no search and no comparison against a table of codewords.

Number the seven positions 1 to 7 and put the check bits at the powers of two - positions 1, 2 and 4 - leaving positions 3, 5, 6 and 7 for data. The check at position `2^i` covers every position whose index has bit `i` set, and its value is chosen so that the covered set has even parity. On a read the decoder recomputes all three checks. Reading them as a three-bit number, low check first, gives the **syndrome**: `000` means no single flip, and any other value is the index of the position that flipped. A flip at position 5 fails the checks at 1 and 4 but not the one at 2, giving `101` - five. The decoder inverts that bit and the word is repaired, with no search and no comparison against a table of codewords.

code

pseudocode · 15 lines

pseudocode

// bit[1..7]; check bits live at positions 1, 2 and 4
syndrome = 0
for each i in {1, 2, 4}:
    parity = 0
    for each position p in 1..7:
        if (p bitwise-and i) is nonzero:      // check i covers position p
            parity = parity xor bit[p]
    if parity is not 0:
        syndrome = syndrome + i

if syndrome is 0:
    accept word                               // no single flip seen
else:
    bit[syndrome] = bit[syndrome] xor 1       // syndrome names the position
    accept repaired word

go deeper

for a junior

Remember the shape: three check bits, four data bits, seven positions, and a three-bit result that is either zero or the number of the bad position. The count is not a coincidence - three checks can name seven positions plus one clean case.

for a middle

Explain the covering rule and work an example end to end: which checks fail for a flip at a given position, what number they form, and why the check bits sit at powers of two. Then state where the pointer stops being trustworthy.

for a senior

Show that you know the failure mode: at this distance a double flip produces a syndrome that names an innocent position, so the decoder returns wrong data and reports success. Say how a system would notice that class of event at all.

for a principal

The judgement is whether transparent in-place repair is the right behaviour for the data in question, or whether a report-and-refuse decoder that never returns a possibly wrong word is the safer contract for the layer above.

The construction

This is a block code with n = 7 total bits, k = 4 data bits and r = 3 check bits - a code rate of 4/7. Its minimum distance is 3, so it corrects one flipped bit per word. What makes it worth studying is not the distance but the decoder: the checks are arranged so that repairing a word costs three parity computations and one bit inversion, with no lookup of the full codeword set.

The arrangement is a counting argument turned into a layout:

Three checks produce 2^3 = 8 possible outcome patterns.
One pattern, all-zero, has to mean "nothing wrong".
The remaining 7 patterns are exactly enough to name 7 positions - which is why the codeword is 7 bits long.

Place the checks at positions 1, 2 and 4 so that each check bit is covered by exactly one check - itself. Data bits land at 3, 5, 6 and 7, each covered by two or three checks. Every position's index, read in binary, is the list of checks that cover it.

check bit	position	covers positions	binary reason
c1	1	1, 3, 5, 7	indexes with the 1s bit set
c2	2	2, 3, 6, 7	indexes with the 2s bit set
c4	4	4, 5, 6, 7	indexes with the 4s bit set

On write, each check bit is set so that the parity of its covered set is even. Because a check bit belongs to its own set and to no other, the three can be computed independently, in any order.

Decoding: the syndrome names the position

On read, recompute all three parities over the received bits. Assemble the results as a binary number with c1 as the least significant digit. That value is the syndrome:

Syndrome 0. Every covered set still has even parity - the word is accepted.
Syndrome s, nonzero. Exactly the checks whose index bit is set in s failed. The only single position covered by precisely that combination of checks is position s. Invert bit s.

Work the case of a flip at position 5. Five is 101 in binary, so position 5 is covered by the checks at 4 and 1 and not by the one at 2. The check at 1 fails, the check at 2 passes, the check at 4 fails, and the syndrome reads 101 = 5. Invert bit 5 and the word is legal again.

A flip in a check bit is handled by the same rule with no special case: a flip at position 2 fails only the check at 2, giving syndrome 010 = 2, which names the check bit itself. Data is untouched and the check bit is restored.

Why this is the interesting part

Decoding is arithmetic, not search. The naive decoder compares the received word against every codeword and picks the nearest - that is exponential in the data width. Here the syndrome hands you the answer directly.
The checks are self-protecting. Because check bits sit in covered positions too, corruption of a check is corrected like any other flip rather than being mistaken for data corruption.
The layout is the point. Put the checks at the end of the word instead and the code still has distance 3, but the syndrome no longer reads off as an index; you need a translation table from syndrome to position. The powers-of-two placement is what removes that table.

Where it stops working

The syndrome is a faithful pointer only inside the code's guarantee of one flipped bit:

Two flips produce a nonzero syndrome that names a third position. The decoder inverts an innocent bit and returns a word that is legal and wrong. Nothing in the syndrome distinguishes this from the single-flip case, which is the direct motivation for extending the code.
A syndrome of zero is not proof of an intact word. A pattern of flips that happens to form another codeword - three flips can do it here - passes every check silently.
The scheme addresses positions, not magnitudes. It assumes the corruption is a flipped bit at a known-width position; corruption that loses or shifts whole positions is a different model entirely.

The overhead is honest to state: 3 check bits for 4 data bits is 75 percent on top of the payload, or 43 percent of the transmitted word. That ratio is brutal at this width and is the reason real protection is applied to much wider words.

## The construction This is a block code with `n = 7` total bits, `k = 4` data bits and `r = 3` check bits - a code rate of 4/7. Its minimum distance is 3, so it corrects one flipped bit per word. What makes it worth studying is not the distance but the *decoder*: the checks are arranged so that repairing a word costs three parity computations and one bit inversion, with no lookup of the full codeword set. The arrangement is a counting argument turned into a layout: - Three checks produce `2^3 = 8` possible outcome patterns. - One pattern, all-zero, has to mean "nothing wrong". - The remaining 7 patterns are exactly enough to name 7 positions - which is why the codeword is 7 bits long. Place the checks at positions 1, 2 and 4 so that each **check bit is covered by exactly one check** - itself. Data bits land at 3, 5, 6 and 7, each covered by two or three checks. Every position's index, read in binary, *is* the list of checks that cover it. | check bit | position | covers positions | binary reason | |---|---|---|---| | c1 | 1 | 1, 3, 5, 7 | indexes with the 1s bit set | | c2 | 2 | 2, 3, 6, 7 | indexes with the 2s bit set | | c4 | 4 | 4, 5, 6, 7 | indexes with the 4s bit set | On write, each check bit is set so that the parity of its covered set is even. Because a check bit belongs to its own set and to no other, the three can be computed independently, in any order. ## Decoding: the syndrome names the position On read, recompute all three parities over the received bits. Assemble the results as a binary number with `c1` as the least significant digit. That value is the **syndrome**: 1. **Syndrome 0.** Every covered set still has even parity - the word is accepted. 2. **Syndrome s, nonzero.** Exactly the checks whose index bit is set in `s` failed. The only single position covered by precisely that combination of checks is position `s`. Invert bit `s`. Work the case of a flip at position 5. Five is `101` in binary, so position 5 is covered by the checks at 4 and 1 and not by the one at 2. The check at 1 fails, the check at 2 passes, the check at 4 fails, and the syndrome reads `101` = 5. Invert bit 5 and the word is legal again. A flip in a check bit is handled by the same rule with no special case: a flip at position 2 fails only the check at 2, giving syndrome `010` = 2, which names the check bit itself. Data is untouched and the check bit is restored. ## Why this is the interesting part - **Decoding is arithmetic, not search.** The naive decoder compares the received word against every codeword and picks the nearest - that is exponential in the data width. Here the syndrome hands you the answer directly. - **The checks are self-protecting.** Because check bits sit in covered positions too, corruption of a check is corrected like any other flip rather than being mistaken for data corruption. - **The layout is the point.** Put the checks at the end of the word instead and the code still has distance 3, but the syndrome no longer reads off as an index; you need a translation table from syndrome to position. The powers-of-two placement is what removes that table. ## Where it stops working The syndrome is a faithful pointer only inside the code's guarantee of one flipped bit: - **Two flips produce a nonzero syndrome that names a third position.** The decoder inverts an innocent bit and returns a word that is legal and wrong. Nothing in the syndrome distinguishes this from the single-flip case, which is the direct motivation for extending the code. - **A syndrome of zero is not proof of an intact word.** A pattern of flips that happens to form another codeword - three flips can do it here - passes every check silently. - **The scheme addresses positions, not magnitudes.** It assumes the corruption is a flipped bit at a known-width position; corruption that loses or shifts whole positions is a different model entirely. The overhead is honest to state: 3 check bits for 4 data bits is 75 percent on top of the payload, or 43 percent of the transmitted word. That ratio is brutal at this width and is the reason real protection is applied to much wider words.

What does a syndrome of zero actually prove about the received word?
Only that the word is a legal codeword, not that it is the one that was sent. Zero rules out any single flip, since every single flip produces its own nonzero syndrome. But a flip pattern that walks the word onto a different codeword - three flips suffice in this code - also yields zero, and the decoder accepts it silently.
What happens when two bits flip in the same seven-bit word?
The two syndromes combine, and the result is the nonzero syndrome of some third position. The decoder cannot tell it from a single flip, so it inverts that innocent bit and returns a legal but wrong word - now three bits away from the original. This is the failure that the extended, distance-4 version exists to catch.
Why does a flipped check bit need no special handling?
Because the check bits occupy covered positions like any other bit. A flip at position 2 fails only the check at position 2, so the syndrome reads 2 and the decoder inverts that bit. The data bits were never involved, and the repaired word is correct without the decoder ever knowing the position was a check.

saying these in an interview costs you the question

Reads the syndrome as a count of corrupted bits
Thinks each check bit protects only the data bits
Says a zero syndrome proves the word is intact
Believes the decoder compares the word against all codewords
Assumes two flips still produce a usable syndrome
Puts the check bits at the end and still expects an index

In a seven-bit codeword carrying four data bits, how do the three parity-check bits tell a decoder which bit flipped?

§ answer

basics

solid answer

code

§ go deeper

▾level notes4 levels

▾deep dive~4 min

The construction

Decoding: the syndrome names the position

Why this is the interesting part

Where it stops working

▾common follow-ups3 questions

▾red flags6 flags

The construction

Decoding: the syndrome names the position

Why this is the interesting part

Where it stops working

answer

go deeper