An Efficient Single and Double-Adjacent Error Correcting Parallel Decoder for the (24,12) Extended Golay Code
Memories that operate in harsh environments, like for example space, suffer a significant number of errors. The error correction codes (ECCs) are routinely used to ensure that those errors do not cause data corruption. However, ECCs introduce overheads both in terms of memory bits and decoding time that limit speed. In particular, this is an issue for applications that require strong error correction capabilities. A number of recent works have proposed advanced ECCs, such as orthogonal Latin squares or difference set codes that can be decoded with relatively low delay. The price paid for the low decoding time is that in most cases, the codes are not optimal in terms of memory overhead and require more parity check bits. On the other hand, codes like the (24,12) Golay code that minimize the number of parity check bits have a more complex decoding. A compromise solution has been recently explored for Bose–Chaudhuri–Hocquenghem codes. The idea is to implement a fast parallel decoder to correct the most common error patterns (single and double adjacent) and use a slower serial decoder for the rest of the patterns. In this brief, it is shown that the same scheme can be efficiently implemented for the (24,12) Golay code. In this case, the properties of the Golay code can be exploited to implement a parallel decoder that corrects single- and double-adjacent errors that is faster and simpler than a single-error correction decoder. The evaluation results using a 65-nm library show significant reductions in area, power, and delay compared with the traditional decoder that can correct single and double-adjacent errors. In addition, the proposed decoder is also able to correct some triple-adjacent errors, thus covering the most common error patterns. The proposed architecture of this paper analysis the logic size, area and power consumption using Xilinx 14.2.
Research for multibit ECCs has focused on reducing the decoding latency as in many cases, the traditional decoders are serial and require several clock cycles. To some extent this can be done for some traditional ECCs by using a parallel syndrome decoder but the decoder complexity explodes as the error correction capability or the word size increases. Another approach is to use codes that can be decoded with low delay, such as orthogonal Latin squares (OLSs) or difference set (DS) codes. In the case of OLS codes, the main issue is that they are not optimal in terms of the number of parity check bits and thus require more memory overhead. The DS codes are more competitive in terms of parity check bits but are still not optimal for some word lengths. For example, the (21, 10) DS code can correct 2-bit errors while a code with a similar block size and code rate, and the (24,12) extended Golay code can correct 3-bit errors. However, the Golay code requires a more complex decoder that needs several clock cycles.
Namba et al. have proposed a compromise solution for Bose–Chaudhuri–Hocquenghem codes. The idea is that the most common error patterns are decoded in parallel and the rest serially. In particular, single and double-adjacent errors are corrected in a single clock cycle. This means that the most memory accesses can be completed in a single clock cycle, and only a small percentage of the words in error require a full serial decoding. This can enable the use of traditional ECCs that do not support fast parallel decoding to protect SRAM memories. In this brief, the use of the scheme in is considered for the (24,12) Golay code.
In more detail, an efficient parallel decoder capable of correcting the single and double-adjacent errors is presented. The decoder exploits the properties of the Golay code to reduce the implementation cost. This result in a decoder that is simpler than a traditional SEC decoder but that can also correct all double-adjacent errors and some triple-adjacent errors. The proposed decoder has been implemented in hardware description language and mapped to a 65- nm technology to show its benefits. The main contribution of this brief is to enable a fast and efficient parallel correction of the single and double-adjacent errors in the (24,12) Golay code.
- high area coverage
- high delay
- power consumption is high
EXTENDED GOLAY CODE
The parity check matrix of the (24, 12) Golay code is shown in Fig. 1. The 12 first bits correspond to the parity check bits and last 12 to the data bits. A single-error correcting parallel decoder can be implemented by computing the syndrome and comparing in parallel with the 12 data bit and the 12 check bit columns. When there is a match that bit is corrected.
Fig. 1. Parity check matrix of the (24,12) Golay code.
The requirement for SEC is that the columns must be different. Therefore, it would seem possible to use a subset of the parity bits to decode single errors. However, since the code can correct three errors, we need to ensure that the single-error parallel decoder does not introduce erroneous corrections in the presence of multiple bit errors.
SEC-DAEC PARALLEL DECODER
The existing SEC-DAEC decoders are similar to SEC decoders but they need to check also the syndrome values that correspond doubleadjacent errors. This requires roughly doubling the number of comparisons. Then, the correction of each bit is triggered by three syndrome values (the single bit and the two double adjacent). This results in a decoder that is significantly more complex than a simple SEC decoder.
Fig. 2. Parity check matrix of the (24,12) Golay code with the proposed bit placement.
The proposed parallel decoder as discussed before has the objective of correcting single and double-adjacent bit errors. The first step is to place the bits in the memory such that data and parity bits are interleaved, as shown in Fig. 2. This interleaving has no impact on memory performance, as it is a simple remapping of the bits when they are read from or written to the memory.
Let us now consider the syndrome values for an error on the second bit (first data bit), a double adjacent on bits one and two, a double adjacent on bits two and three, and a triple adjacent on bits one, two, and three. In all those cases, bit two should be corrected. The syndrome values for those error patterns are shown in Fig. 3. The interesting observation is that the first two rows are the only ones hat change from one pattern to another and that the values cover the four possible combinations of the first two bits. This means that the decoding can be done by simply comparing the remaining ten bits with the last ten bits of the syndrome. If they match, then the second bit (first data bit) has to be corrected. It can be observed that the same reasoning applies to the rest of the data bits, except the last one. For the last bit, there are only two values to check (single and double adjacent with bit 23). In this case, it is easy to see that this can be done by checking the first 11 bits only.
Fig. 3. Example of syndrome values for errors that affect the first data bit in the proposed bit placement.
The proposed parallel decoder also has to detect errors that it cannot correct. In those cases, the serial decoder must be used to correct the error. The logic needed to detect those errors is simply a check for a no zero syndrome and a check that none of the comparators has detected a match. The first part can be implemented with a 12-input OR gate and the second with another 24-input OR gate.
- Reduce the area
- Reduce the delay
- Reduce the power
- Xilinx ISE