VI. Appendix

A. Ensuring Data Integrity with Hamming Codes
In mission critical applications when there is only one opportunity to exchange data, it is common to employ Forward Error Correction, or FEC. One application of this technique is for the data sent from a distant satellite – because of the time delays inherent with the great distances between a space probe and ground station, it is more efficient to encode the transmitted data with Forward Error Correction than to request a retransmission. FEC is accomplished by transmitting extra bits with an n-bit sequence so that errors can be detected and corrected by the receiver. One common implementation of FEC is through the use of Hamming codes.

In our application, the basic data block consists of a 10-bit A/D value. By adding four parity bits for the Hamming code, we increase our block size to 14 bits but with the added benefit of being able to detect and correct a single bit error. Consider the following data arrangement:

Position

1

2

3

4

5

6

7

8

9

10

11

12

13

14

Contents

P1

P2

D9

P4

D8

D7

D6

P8

D5

D4

D3

D2

D1

D0



P1, P2, P3, and P4 are our parity bits while D9-D0 are our A/D reading. To calculate each of the parity bits, we use modulo-1 arithmetic. With modul0-1 arithmetic, the sum of an even number of 1’s results in a zero while the sum of an odd number of 1’s results in a 1.

Each of the parity bits is calculated using the equations below:

P1=D9+D8+D6+D5+D3+D1

P2=D9+D7+D6+D4+D3+D0

P4=D8+D7+D6+D2+D1+D0

P8=D5+D4+D3+D2+D1+D0

On the receive side, the Check bits are calculated from:

C1=P1+D9+D8+D6+D5+D3+D1

C2=P2+D9+D7+D6+D4+D3+D0

C4=P4+D8+D7+D6+D2+D1+D0

C8=P8+D5+D4+D3+D2+D1+D0

If there are no errors in the data, the value of the nibble formed by C8-C4-C2-C1 will be zero. If there is an error, the value of C8-C4-C2-C1 will contain the bit location that requires correction. To correct the bit, just invert its value!

Examples:

Let’s assume that we have an A/D value of 3A8h or 1111001000b. Our transmitted Hamming code for this block becomes:

Position

1

2

3

4

5

6

7

8

9

10

11

12

13

14

Contents

P1

P2

D9

P4

D8

D7

D6

P8

D5

D4

D3

D2

D1

D0

Value

0

0

1

1

1

1

1

1

0

0

1

0

0

0



On the receive side we might receive the following:

Position

1

2

3

4

5

6

7

8

9

10

11

12

13

14

Contents

P1

P2

D9

P4

D8

D7

D6

P8

D5

D4

D3

D2

D1

D0

No Error

0

0

1

1

1

1

1

1

0

0

1

0

0

0

Error in bit 9

0

0

1

1

1

1

1

1

1

0

1

0

0

0

Error in bit 3

0

0

0

1

1

1

1

1

0

0

1

0

0

0



When the data is received correctly, the code values are:

C8=1+0+0+1+0+0+0=0

C4=1+1+1+1+0+0+0=0

C2=0+1+1+1+0+1+0=0

C1=0+1+1+1+0+1+0=0

Thus the check code, C8C4C2C1, is equal to 0000b when the data is correctly received.

When an error occurs in the ninth bit, the check code values are:

C8=1+1+0+1+0+0+0=1

C4=1+1+1+1+0+0+0=0

C2=0+1+1+1+0+1+0=0

C1=0+1+1+1+1+1+0=1

C8C4C2C1=1001 indicates the erroneous bit position of 9.

Finally if an error occurs in the third bit, we get:

C8=1+0+0+1+0+0+0=0

C4=1+1+1+1+0+0+0=0

C2=0+0+1+1+0+1+0=1

C1=0+0+1+1+0+1+0=1

C8C4C2C1=0011 confirms the erroneous bit position of 3.

B. Images - click for a larger view



C. Source and design Files

Paging Previous 1 2 3 4 5



Back to Top