Repetition Codes

Repetition Code Definition

A repetition code is a block code that maps each input bit to a fixed sequence of identical symbols. It is a basic form of Forward Error Correction (FEC), because the receiver uses the repeated symbols to estimate the original bit without requesting a retransmission.

For a repetition factor $n$, the encoder transmits each input bit $n$ times. This introduces redundancy. With an odd $n$ and hard decisions, the decoder selects the majority value in each block, while the code rate is $R = 1/n$.

R3 Repetition Code: Encoding and Decoding

A common example is the R3 code, also called the (3,1) repetition code. It maps one information bit to a block of three transmitted bits.

• To send a logical '0', the transmitter sends the sequence 000.
• To send a logical '1', the transmitter sends the sequence 111.

Majority Decoding

The decoder counts the symbols in each three-bit block and outputs the value that occurs at least twice:

Correction Capability and Limits

R3 corrects one flipped bit in a three-bit block when the decoder uses majority decisions. If two bits in the same block are flipped, the received block has the wrong majority and the original bit is not recovered.

Example of successful correction:
1. Sender wants to send: 1
2. Encoded and transmitted signal: 111
3. Noise corrupts the signal. Received signal: 101
4. Decoder's majority vote (two 1s, one 0) → Decodes to the correct value: 1.

Example of failure:
Two flipped bits reverse the majority decision.
1. Transmitted signal: 111
2. Two bit flips change the signal. Received signal: 001
3. Decoder's majority vote (one 1, two 0s) → Decodes incorrectly to: 0.

Formal Properties: Hamming Distance

The error-handling capabilities of a code are determined by its minimum Hamming distance ($d_{min}$). For the R3 code, the only valid codewords are $000$ and $111$, and they differ in 3 positions, so $d_{min}=3$.

• A code with minimum distance $d_{min}$ can detect up to $d_{min} - 1$ errors when the received word is checked for validity. For R3, this bound is $3 - 1 = 2$ errors.
• The guaranteed correction bound is $t = \lfloor \frac{d_{min} - 1}{2} \rfloor$. For R3, it is $\lfloor \frac{3 - 1}{2} \rfloor = 1$ error.

For an independent binary symmetric channel with bit-flip probability $p$, hard-decision R3 has decoded-bit error probability $P_e = 3p^2(1-p) + p^3 = 3p^2 - 2p^3$. This expression assumes independent flips and majority decoding.

Advantages and Disadvantages

Advantages

• Simplicity: They are easy to understand, implement in hardware, and analyze.

Disadvantages

• Low Code Rate: The code rate is the ratio of information bits to transmitted bits. For R3, the rate is $\frac{1}{3}$, so two-thirds of the transmission is redundant overhead. Sending a 1 MB file requires transmitting 3 MB of encoded data.
• Limited Correction: R3 corrects one error per block under majority decoding. A burst can flip two or more bits in one block and exceed that guaranteed bound.
• Increased Delay and Bandwidth: Sending three bits for each information bit triples the transmission time at a fixed bit duration or requires three times the physical bit rate for the same effective data rate.