# A Forward Error-Correction Example

###### © Copyright University of New Haven 1999

### Question:

How many redundant bits are required for 2-bit correction of 8 different messages?

### Solution:

Let *N* = (message bits + redundant bits) be the required total number of bits.
3 message bits are required for 8 messages.
1 code is required for a correct message.
There are *N* ways to make a 1-bit change to a correct code (i.e. a 1-bit error).
There are ½*N*×(*N*-1) ways to make a 2-bit change to a correct code (i.e. a 2-bit error).
Total number of codes required per message = 1 + *N* + ½*N*×(*N*-1) = 1 + ½*N* + ½*N*².
Thus total number of codes required for all 8 messages = 8 × (1 + ½*N* + ½*N*²) = 8 + 4*N* +4*N*².
Tabulating some *N* values:

N 8 + 4N + 4N² 2^{N}
4 8+16+64=88 16
7 8+28+196=232 128
8 8+32+256=296 256
9 8+36+324=368 512

Thus *N*=9 yields sufficient bits to create the required number of codes, giving 9-3 = 6 redundant bits required.
CS447/CS642 Home Page