1 Forward Error Correction

Information is subject to random bit errors in storage and transmission. Forward error correction (FEC) adds redundant data to a message to allow for the detection and correction of limited numbers of such errors. Here’s how it works: An (n,k) FEC encoding function E maps a k-bit data block x to an n-bit code word y = E(x). A noisy channel or storage device changes y into a corrupted word y′ of the same length.¹ An FEC decoding function D maps y′ back to a k-bit word x′ = D(y′), which becomes the output of the process. The transmission is successful if x′ = x. In order for decoding to be successful in the absence of errors, we must have n ≥ k. The n - k “extra” bits supply the needed redundancy to allow successful decoding even in the presence of a limited number of transmission errors.

2 Hamming Code

There are many different FEC codes, some of which involve rather sophisticated mathematics. The Hamming Code that we present here can be understood relatively easily. It can correct any single bit error.

2.1 Encoding Function

We look at the special case of a (31, 26) Hamming code, so 26 data bits x are augmented with 5 parity bits to produce a 31-bit code word y = E(x). For reasons that will become apparent, it is convenient to number the bits of our bit strings starting with 1 (rather than 0) and to intermix the data bits and the parity bits. The parity bits are placed at positions of y which are powers of 2. Thus, p₁,…p₅ go into positions 1, 2, 4, 8, and 16 of the code word y, respectively. The data bits x go into the remaining positions of y as shown in Table 1.

---

Table 1: Interleaving of parity and data bits.

---

Each parity bit p_i checks a certain subset C_i of the bits of y. Set C_j contains exactly those bits y_i such that bit j in the binary representation of i is 1, as shown in Table 2. Since p_i = y_2^i-1, it follows that p_i C_i. For example, C₂ contains those y_i for which there are 1’s in the p₂ column, i.e., C₂ = {y₂ = p₂,y₃,y₆,y₇,y₁₀,…,y₃₁}.

Similarly, to find the sets that contain a bit y_i, write i in binary. The 1’s in the binary representation of i correspond to the sets C_j that contain y_i. For example, to see which parity bits check y₁₉, we first write 19 in binary to get 19 = (10011)₂. Since bits 1, 2, and 5 (reading from right to left) are 1’s, then y₁₉ is contained in sets C₁, C₂, and C₅.

The parity bits are set so as to make the number of 1-bits in the sets they check even. This is always possible since each parity bit is in the set it checks and no other parity bit is in that set. (This follows from the fact that the parity bits are placed at bit positions of y that are powers of 2.)

---

Table 2: Bit coverage of parity bits.

---

2.2 Decoding Function

The decoding function D(y′) returns a bit string x′{0,1}²⁶. If y = E(x) and and y and y′ differ in at most one bit position, then it will be the case that x′ = x. Otherwise, x′ might or might not equal x.

The decoding function D(y′) proceeds as follows. First, we check all of the parity bits. That is, we compute c_j = parity(C_j) for each j. Let e = (c₅…c₁)₂ be the number represented in binary by the c_j bits. If e≠0, we assume that bit y′_e is incorrect, so we flip it to obtain y′′. Otherwise, we assume no errors and take y′′ = y′. We then extract the data bits x′ from the positions of y′′ that are not powers of 2 and return x′.

To see why this works, suppose for example that bit y₁₉ did in fact get flipped in transmission, so y′₁₉≠y₁₉. Table 2 shows that bit y₁₉ is checked by p₅, p₂, and p₁, so flipping y₁₉ will cause the parity of each of the sets C₅, C₂, and C₁ to change from even to odd. Hence, c₅ = c₂ = c₁ = 1. However, c₄ = c₃ = 0 since the sets C₄ and C₃ do not contain y₁₉ and their parity remains even. The number e described by the c’s is 19, so the y′′ that results from flipping bit y′₁₉ is indeed the original code word y.

3 Assignment

You are to implement the following two functions

These functions should compute the Hamming functions E(x) and D(y) described above. The bit strings are assumed to be placed into the unsigned int variables in left-to-right order and right-justified. Thus, the low order bit of data corresponds to data bit x₂₆, and the low order bit of codeword corresponds to code word bit y₃₁.

I have supplied an interface file hamming.h in the Zoo assignment directory

that contains these prototypes. Your implementation file should be called (surprise!) hamming.c. You should also produce a main program to test your functions. Your main program should test that the decoder correctly inverts the encoder when there are no errors present, as well as testing that the decoder successfully corrects each of the possible 31 one-bit errors. It’s also important to test your code against several different data strings since it might work on some just be chance even if it has bugs.

4 Deliverables

You should submit source code for your module and test program and a Makefile. You should also submit your test results showing what tests you performed on it and what the results of those tests were.