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
- Remote Station Assembly. Note Transmitter board on left
- Remote Station, Antenna, and Solar Cell
- Base Station Assembly
C. Source and design Files
advertisement
advertisement