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 + 4N +4N². Tabulating some N values:

     N     8 + 4N + 4N²     2N

     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