Question

1. Let C be a binary code of block length 8 that can correct all single errors.

Show that C can have at most 28 code words.

2. Construct, if possible, binary (n, M, d) codes with the following parame- ters: (6,2, 6), (3, 8, 1), (4, 8, 2), (5, 3, 4), (8, 30, 3). When it is not possible, show why it is impossible.

Answer 1

A binary code of block length 8 that can correct all single errors can have a maximum of 128 code words.

Step-by-step explanation:

Let us consider an 8-block binary code that can correct all single errors, where each bit can be either 0 or 1. There are therefore two possible outcomes for every bit. Since there are eight bits, multiplying the number of possibilities for each bit will yield the total number of possible code words. So, 2^8 = 256 is equal to 2 x 2 x 2 x 2 x 2 x 2 x 2 x 2. Every valid code word must, however, be atleast two distances apart from every other valid code word because the code is able to correct all single errors. Consequently, 256 / 2 = 128 is the maximum number of code words that can be generated.