Question

Question: This Exercise examines the single error correcting, double error detecting (SEC/DED) Hamming code.

(5.9.1) What is the minimum number of parity bits required to protect a 128-bit word using the SEC/DED code?

(5.9.2) Section 5.5 states that modern server memory modules (DIMMs) employ SEC/DED ECC to protect each 64 bits with 8 parity bits. Compute the cost/performance ratio of this code to the code from 5.9.1. In this case, cost is the relative number of parity bits needed while performance is the relative number of errors that can be corrected. Which is better?

(5.9.3) Consider a SEC code that protects 8-bit words with 4 parity bits. If we read the value 0x375, is there an error? If so, correct the error.

Short answer

(5.9.1)

The minimum number of parity bits is 9 for 128-bit words.

(5.9.2)

The cost/performance ratio of 64 bit with 8 parity bits is 9.057 and for 128 bit with 9 parity bits is 9.72. The code with 64 bits and 8 parity bits is better.

(5.9.3)

There is an error in bit 8 of the value. The correct value is 0x365.

Step-by-step solution

Define single error-correcting, double error detecting (SEC/DED) Hamming code

Hamming code provides a technique to detect errors in the data and correct single-bit errors. In this method, redundant bits are added at specific locations within the data. These redundant bits are data bits. The value for these bits is calculated and inserted into the data for error detection and correction. On the receiver side, recalculation is performed to detect errors in the data.

Formula to calculate the number of parity bits in hamming code

(5.9.1)

Let be the number of data bits and be the number of parity bits. To calculate the number of parity bits to apply Hamming code, the following equation should be satisfied:

In another form, it can be written as:

Calculate the number of parity bits for a 128-bit word

In the given problem, the number of data bits is 128. Using the formula given in the above step, the following condition should be satisfied:

Putting the value of 8 for , the equation is satisfied. That is,

Adding an extra 1 bit to the value of gives the number of parity bits equal to 9.

Define cost/performance ratio

(5.9.2)

The cost/performance ratio is the ability to perform for the given cost. The cost in the given problem is a relative number of parity bits used and performance is a relative number of errors that can be corrected. The method with a lower cost/performance ratio is better.

Calculate the cost/performance ratio

The modern server memory module has 64 data bits and 8 parity bits. The code from 5.9.1 has 128 data bits and 9 parity bits.

The cost rate for 64-bit data with 8 parity bits is calculated as:

The cost rate for 128-bit data with 9 parity bits is calculated as:

With 64-bit data and 8 parity bits, the total number of bits is 72. Hamming code can correct one-bit errors in these data bits. So, the performance rate for 64-bit data with 8 parity bits is calculated as:

With 128-bit data and 9 parity bits, the total number of bits are 137. Hamming code can correct one-bit errors in these data bits. So, the performance rate is calculated as:

The cost/performance ratio for 64-bit data is 9.057 and for 128-bit data is 9.72. Thus, 64-bit data with 8 parity bits is better because it has a low cost/performance ratio.

Detecting the error in 0x375

(5.9.3)

The received message is 0x375. The binary representation of the message is 0011 0111 0101. It has 8 data bits and 4 parity bits as below:

Bit 1	Bit 2	Bit 3	Bit 4	Bit 5	Bit 6	Bit 7	Bit 8	Bit 9	Bit 10	Bit 11	Bit 12
Parity bit 1	Parity bit 2	Data bit 1	Parity bit 3	Data bit 2	Data bit 3	Data bit 4	Parity bit 4	Data bit 5	Data bit 6	Data bit 7	Data bit 8
0	0	1	1	0	1	1	1	0	1	0	1

Parity bit 1 check bits 1,3,5,7,9, and 11. These bit positions have values 010100. It has two 1s. So even parity.

Parity bit 2 checks bits 2,3,6,7,10, and 11. These bit positions have values 011110. It has four 1s. So even parity.

Parity bit 3 checks bits 4,5,6,7, and 12. These bit positions have values 10111. It has four 1s. So even parity.

Parity bit 4 checks bits 8,9,10,11, and 12. These bit positions have values 10101. It has three 3s. So odd parity. There is an error.

Correcting error

Parity 4 contains an error. So, bit 8 has an error. This bit is wrong. It is changed to 0. The correct data is

0011 0110 0101

In hexadecimal, the correct value is 0x365.