How many redundant bits are required for 2-bit correction of 8 different messages?
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.