Multiprocessor architectures have become commonplace embedded applications these days. The processors often are interconnected via simple asynchronous serial links. These links employ UARTs that don’t offer any built-error control other than simple onebit error detection using parity. Many designers (except for communication specialists) are unaware that it’s not difficult to incorporate reasonably powerful error correction in software.
The performance overheads are quite tolerable in most applications. In fact, this error-correction method can be reduced to simple table lookups.
The method described here, based on the well-known Hamming code technique, enables correction of single-bit errors. The method also can be extended to burst errors as explained below. This forward-error-correction method is useful in applications where data integrity is important. In addition, it’s beneficial in simplex systems or long transmission delay systems which error detection, acknowledgements, and retransmission aren’t feasible. One good example is an underwater acoustic data-communication system.
The technique illustrated here uses 4-bit data characters. Three parity bits are added to this data character to form the 7-bit character that’s transmitted. This character size very convenient, since it’s supported by most UARTs and other communication devices.
Let the Hamming-encoded data bits be numbered as shown below, where B1 is the LSB:
B1 B2 B3 B4 B5 B6 B7
P1 P2 D1 P3 D2 D3 D4
The corresponding bits Pn and Dn indicate how this character is assembled. P1 to P3 are the inserted parity bits, which are computed as shown below, while D1 to D4 are the data Note that the Pn bits occur at positions corresponding to powers Representing each Bn in terms Bms, which correspond to powers one can write:
B3 = B1 + B2
B5 = B1 + B4
B6 = B2 + B4
B7 = B1 + B2 + B4
B1 occurs in the expansions for B3, and B7; B2 in B3, B6, and B7; and B4 B5, B6, and B7.
Using this information, the Hamming coding requires that B1 be represented as the parity of bits B3, and B7, and so on. Thus, the parity bits are computed in terms of the bits as:
P1 = D1 + D2 + D4
P2 = D1 + D3 + D4
P3 = D2 + D3 + D4
where + indicates the Exclusive-OR operation.
On the receive side, the values of the P1, P2, and P3 bits are recomputed and compared with the received values of P1, P2, and P3. The result is then assigned to R1-R3 such that if the received and computed P1 match, then R1 = 0. Otherwise, R1 = 1; likewise for R2 and R3. If R1-3 is treated as a 3-bit number, it will indicate the bit in error as shown (Table 1).
The erroneous bit is then corrected by inverting it. The attached C program implements the technique described (see the listing). Because 8-bit data is typically used, the program takes each 8-bit character, splits it into two 4-bit nibbles, then encodes and transmits each nibble as a 7-bit character. The 8-bit character is reassembled on the receive side after error correction.
This technique also can be extended to correct burst errors. For correction of burst errors up to seven bits in length, seven characters are assembled and stacked as shown to form a block (Table 2).
The vertical slices corresponding to each bit position (A1 to G1) are then taken to form a 7-bit character and transmitted without any further encoding. All seven such characters are thus transmitted. On the receive side, they are again reassembled in a block. The error correction consequently is carried out on each reassembled character (Char 1-7).
In the event of burst errors, at most one bit of each character (Char 1 to Char 7) will be corrupted and can be corrected. For this format, data must be available in blocks of seven characters, which may not be the case in many applications. In such instances, the first character, Char 1, can be used to indicate the actual number of data characters that follow in the block. The rest of the characters, which are dummy characters inserted to make up the seven-character block, can be ignored. The block data count also is protected by the error correction. Note that there are a number of ways of marking packet boundaries in asynchronous communication systems.
The demo C program takes the data character input by the user and splits it into two 4-bit nibbles. Each nibble then is encoded by adding three parity bits for error correction, thus forming the 7-bit hamming code. A single-bit error can be simulated on these codes at a user-specified bit position by inverting the bit concerned. On the receive side, the error is corrected and the original 8-bit character is reassembled from the two data nibbles extracted from the encoded characters.
The encoding table is generated by applying the encoding algorithm to each of the 16 4-bit patterns (0000-1111), resulting in a 16-entry table with each entry containing a 7-bit encoded value. The encoded value for the data nibble xxxx is given by the 7-bit pattern at the xxxx table position.
The decoding table is generated by applying the decoding algorithm to each of the 7-bit patterns (0000000-1111111), representing the possible received values of encoded data. This creates a 128-entry table with 7-bit entry values. If the received bit pattern is xxxxxxx, the 7-bit entry at index xxxxxxx represents the corrected data character.
The two tables are generated once and then used for all subsequent encoding/decoding activity.
The program was compiled and tested in Borland C 4.5 on a PC. The encode and decode routines can be easily ported to almost any C environment, including cross compilers for microcontrollers. The encoding and decoding tables can be generated and stored in PROM memory.
A note on the program listing: The data and parity bits have been interleaved in the above discussion for simplicity. This isn’t a requirement. In the program listing, the four data bits and three parity bits are conveniently packed together as shown below to form the 7-bit data:
B1 B2 B3 B4 B5 B6 B7
P1 P2 P3 D1 D2 D3 D4
The only effect of this rearrangement is that the “Bit In Error” designations shown in Table 1 must be adjusted to indicate the new bit positions.