Checksum in Data Structure And Algorithm : Practice MCQ Questions & Answers with Explanations

For m=8: total bits = 255, data bits = 247. Rate = 247/255 = 0.969 ≈ 0.97.

Total bits = 2^m - 1 = 2^8 - 1 = 255. Data bits = 2^m - m - 1 = 256 - 8 - 1 = 247. So the answer is (255, 247).

The code rate is the second number divided by the first number. For (3, 1), the rate = 1/3.

An Extended Hamming code is called SECDED (Single Error Correction Double Error Detection). The most popular codes are (72, 64) and (127, 120).

Repetition involves sending the same data bits multiple times. For example, with n=3 repetition, a bit '1' is sent as '111'. If the received bits differ, an error has occurred.

If an error occurs in the data string, parity changes to indicate it. However, if the error occurs in the parity bit itself, the error goes undetected.

A two-out-of-five code consists of three 0s and two 1s, giving ten possible combinations to represent digits 0–9.

Rate of a hamming code = message length / block length = (2^r - r - 1) / (2^r - 1) = 1 - r/(2^r - 1). It is the highest rate for a minimum distance of 3.

For a Hamming(7, 4) code, the message length k = 2^r - r - 1, where r is the number of parity bits. Here r = 3, so k = 4.

For a Hamming(7, 4) code, the block length n = 2^r - 1, where r is the number of parity bits. Here r = 3, so n = 7.

Richard W. Hamming invented hamming codes at Bell Telephone Laboratory to minimize errors in punched card readers. Huffman invented Huffman codes. Shannon invented Shannon-Fano codes.

Hamming codes are suitable only for single-bit error detection and correction, and two-bit error detection. They are very unlikely to detect burst errors.

Hamming codes are used for error detection and correction, channel encoding and decoding. They are linear-error correcting codes.

Since we use a generalized version of Hamming(7, 4) code, the minimal hamming distance is 3. It cannot correct burst errors.

The most common hamming codes generalize to form Hamming(7, 4) code. It encodes four bits of data into seven bits by adding three parity bits.