Error-correcting codes are widely used for data transmission. A message consisting of N binary bits is partitioned into blocks of k bits, and each block is transmitted with some additional parity bits, giving a total of n bits per block. The parity bits are used at the receiving end to correct any errors that occur in transmission (bits that get inverted, including the parity bits themselves). Some error-correcting codes can correct only a single error per block; others can correct up to two errors. The number n – k of parity bits is chosen as small as possible to satisfy the relationship

(a) Suppose that transmission errors occur independently at an average rate of 1% of bits transmitted. For data blocks k of 4, 8, 16, 32 and 64 bits, find the value of n and the probability of more errors occurring than the code can correct. Do this for single- and double-error-correcting codes.

(b) Find for each type of code the largest block size k that allows a total of N = 64 data bits to be transmitted with at least 95% probability of correct overall interpretation at the receiving end. Compare the total numbers of bits transmitted in each case.

Transcribed Image Text:

or 2n-kn + 1 (single-error-correcting code) 2-kn+1 (double-error-correcting code)