Many error-correcting codes (ECCs) are proposed in the industry’s literature for correcting bit errors present in the received data. We will discuss Hamming codes that are used to correct singlebit errors and detect all double-bit errors that could occur during data transmission or residing in the memory. How much improvement we can get in the bit-errorrate (BER) performance curves using onebit error correction depends on the raw BER (RBER) without error correction and the codeword length used with the singlebit error-correction coder.
In Figure 1, the BER performance curves illustrate the improvement (i.e., UBER (uncorrectable BER)) with 0- to 6-bit error correction for given raw BER values. The codeword length used to generate the BER curves is 2048 bits. For example, with the given BER = 10-7, we can achieve an UBER of 10-11 with singlebit error correction. For a given RBER, a shorter codeword will provide better error-correcting capability or a higher UBER (Fig. 2).
Given the RBER (P), codeword length (N), and the number of error bits (n), we get the UBER with onebit error correction using the equation shown at the bottom of the page.
MEMORY ERROR CORRECTION
In automotive applications, software integrity level, or ASIL (memory with error-correction capabilities), is one of the most important issues when choosing embedded processors. Software-based Hamming codes can be used to improve the reliability of the most important sections of memory, thus improving the ASIL metric. Memory is used to store information of various types. Some types of information require strong protection against errors, while other types do not.
For example, application software code, data structures, parameters, lookup tables, etc., are very sensitive and any content alteration may end up with catastrophic errors. On the other hand, information such as data samples, image pixels, etc., isn’t as sensitive and may not require error protection.
A typical automotive application can be broken into different sections of memory consisting of different types of information: constant data such as software code, lookup tables, etc.; slowly varying data such as application parameters, data, etc.; and continuously varying data such as audio/video data, navigation data, etc. (Fig. 3). Therefore, a software ROMbased error-correction approach that uses Hamming code to correct the single-bit errors in the first two sections of memory can be implemented using a very small percentage of processor resources.
In the first case, since the data is constant, the extra error-correction information is constant and can be generated once. Every time information is retrieved from this memory section, an ECC decoder is applied to correct the possible errors. In the second case, we call the decoder for each memory load, and the encoder is called to update the error-correction information only when the new data is ready for storing to memory. In these two cases, a software-based single-bit error correction can be implemented using a very small percentage of processor resources.
Figure 4 illustrates a schematic diagram of the software-based memory error correction. With a Hamming (n, k) coder, we divide the data into k bits long, compute the n-k parity bits, and store the n-bits long block to memory area. The parity overhead percentage with respect to data length can be computed as (n-k)*100/k.
When the data is retrieved, the decoder uses the n-k parity bits to detect and correct errors that corrupted during the time when data was residing in memory. We verify the computed parity with the received parity data. If the parity data matches, then no error bits are present in the received data, otherwise there will be error bits in the received data. The Hamming decoder can detect and correct all single-bit errors or detect all double-bit errors.
Because error-correction software is permanently stored in the ROM and uses the core resources whenever memory is accessed, an ECC solution that employs a very small amount of memory and processor cycles is the preferable scenario.
THE HAMMING(2072, 2048) ENCODER
The Hamming(2072, 2048) coder divides the input data stream into 256-byte blocks and computes 24 bits of parity that are used to correct all single-bit errors, detect all double-bit errors, and detect singlebit errors in the parity data. To compute the parity, the 256 bytes of input data are arranged as shown in Figure 5. The bits xP0 to xP15 represent the parity computed row-wise, and bits yP0 to yP5 represent the parity computed column-wise. And, bit dP6 is XOR of all bits of 256 bytes of input data, while bit dP7 is XOR of all 22 parity bits xP0 to xP15, yP0 to yP5, and dP6.
THE HAMMING(2072, 2048) DECODER
The Hamming decoder computes all parity bits for the retrieved data bits in the same way as the encoder using Figure 5. Before computing these parity bits, the decoder checks the parity of the retrieved 24 parity bits computed at the encoder. If this parity fails, then decoding is skipped because there are errors in the retrieved parity data itself. Otherwise, the decoder proceeds to compute the 23 parity bits xP0 to xP15, yP0 to yP5, and dP6. After computing the parity at the decoder, the decoder parity bits are XORed with the retrieved encoder parity bits. Then, it performs the error-correction process using the decoder flow chart (Fig. 6).
The single-bit errors are corrected using the following steps. Allow P0 to P15 to represent the XORed row parity bits and C0 to C5 represent the XORed column parity bits. Subsequently, correct the single-bit errors. This is accomplished by locating the byte address and bit position in the byte using the row and column parity bits.
The byte address is given by the offset obtained from the eight bits “P15 P13 P11 P9 P7 P5 P3 P1,” and the bit position is obtained from the three bits “C5 C3 C1.” Once the decoder comes to know the error bit’s exact location, it corrects the bit value by toggling that bit.
HAMMING(2072, 2048) CODER IMPLEMENTATION
The costliest part of the Hamming coder is the computation of row and column parity bits. The parity bits of the Hamming(2072, 2048) coder are computed by arranging the data as shown in Figure 5. It will be very expensive if one parity bit is computed at a time in a loop covering all the 256 data bytes.
Continue to page 2