|
|
|
|
|
|
|
Thus, the message has 16 + 5 = 21 bits. The five correction bits will be defined by parity on the following groups, defined by base 2 hypercubes: |
|
|
|
|
| | | | | |
|
|
|
|
bits 4 7 and 12 15 and 20 21. |
|
|
|
| | |
|
|
|
|
bits 2 3 and 6 7 and 10 11 and 14 15 and 18 19. |
|
|
|
| | |
|
|
|
|
|
|
In other words, the 21-bit formatted message bits f1-f21 consist of original message bits m1-m16 and correction bits k1-k5. Each correction bit is sited in a location within the group it checks. |
|
|
|
|
|
|
|
|
Suppose the message consists of f1-f21 and m1-m16 = 0101010101010101. For simplicity of decoding, let us site the correction bits at locations that are covered only by the designated correction bit (e.g., only k5 covers bit 16): |
|
|
|
|
|
|
|
|
Now we have m1 is at f3, m2 at f5, etc.): |
|
|
|
 |
|
|
|
|
f1f2f3f4f5f6f7f8f9f10f11f12f13f14f15f16f17f18f19f20f21 |
|
|
|
|
|
|
|
|
k1k2 0 k3 1 0 1 k4 0 1 0 1 0 1 0 k5 1 0 1 0 1. |
|
|
|
|
|
|
|
|
Suppose this message is sent but received with f8 = 0 (when it should be f<CS:"Subscript">8 = k4 = 1). When parity is recomputed at the receiver for each of the five correction groups, only one group covers f8. |
|
|
|
|
|
|
|
|
In recomputing parity across the groups, we get: |
|
|
|
|
| | |
|
|
|
|
0 (i.e., there is no error in bits 1621). |
|
|
|
| | | | | | | | | | | | |
|
|
|
|
|
|
The failure pattern 01000 is the binary representation for the incorrect bit (bit 8), which must be changed to correct the message. |
|
|
|
|
|