A Method to Design Single Error Correction Codes with Fast Decoding for a Subset of Critical Bits
Abstract:
Single error correction (SEC) codes are widely used to protect data stored in memories and registers. In some applications, such as networking, a few control bits are added to the data to facilitate their processing. For example, flags to mark the start or the end of a packet are widely used. Therefore, it is important to have SEC codes that protect both the data and the associated control bits. It is attractive for these codes to provide fast decoding of the control bits, as these are used to determine the processing of the data and are commonly on the critical timing path. In this brief, a method to extend SEC codes to support a few additional control bits is presented. The derived codes support fast decoding of the additional control bits and are therefore suitable for networking applications.The proposed architecture of this paper analysis the logic size, area and power consumption using Xilinx 14.2.
Existing System:
Packet data must frequently be stored in RAMs, e.g., inFIFOs for adapting processing rates. When storing packet data,it is necessary to delineate the packet boundaries. In the absolute simplest case, each segment on the bus can be delineatedwith a single EOP marker. The next valid segment is thenassumed to be the start of the following packet. In practice,designers also use a SOP marker to explicitly mark the start ofpackets. There are also many cases in packet processing wherea packet is in error and it must be dropped. To mark such erroredpackets, an additional control signal (ERR) may be required.As mentioned in the introduction, from an error protectionperspective, it is attractive to store the data and the markers in asingle wide memory, as shown in Fig. 1. In this way, relativelyfewer ECC bits are required. The problem with this approach iswhen the data are read out. Typically, the markers feed into astate machine that controls the reading of the subsequent data.For example, the state machine may need to read out a singlepacket (up to an EOP), or it may need to read out a fixednumber of bytes of data (e.g., deficit round robin scheduler).The critical timing path then consists of the ECC correctionlogic, followed by the state machine logic, as shown in red.With a traditional Hamming SEC code, as the data bus increasesin width, the number of layers of logic required to decodethe syndrome and perform correction also increases. Circuitdesigners frequently observe critical timing on the signal pathsrelated to the correction of the markers which feed downstreamstate machines. For this reason, special ECC codes which canprovide a fast decode of the small number of marker bits areextremely attractive.
Disadvantages:
- Area coverage is high
- Speed is low
Proposed System:
The goal is to design SEC codes that can protect a data block plus a few control bits such that the control bits can be decoded with low delay. As mentioned before, the data blocks to be protected have a size that is commonly a power of two, e.g., 64 or 128 bits. To protect a 64-bit data block with a SEC code, 7 parity check bits are needed, while 8 are enough to protect 128 bits. In the first case, there are27= 128possible syndromes, and therefore, the SEC code can be extended to cover a few additional control bits. The same is true for 128 bits and, in general, for a SEC code that protects a data block that is a power of two. This means that the control bits can also be protected with no additional parity check bits. This is more efficient than using two separate SEC codes (one for the data bits and the other for the control bits) as this requires additional parity check bits. The main problem in using an extended SEC code is that the decoding of the control bits is more complex. To illustrate this issue, let us consider a 128-bit data block and 3 control bits. The initial SEC code for the 128-bit data block has the parity check matrix shown in Fig. 1. This code has a parity check matrix with minimum total weight and balanced row weights to minimize encoding and decoding delay. Three additional data columns can be easily added to obtain a code that protects the additional control bits. For example, the matrix in Fig. 4 can be used, in which three additional columns (marked as control bits) have been added to the left.
Figure 1: Parity check matrix for a minimum-weightSEC code that protects 128 data and 3 control bits
To do so, the parity check bits can be divided in two groups: a first group that is shared by both data and control bits and a second that is used only for the data bits. Then, the decoding of the control bits only requires the recomputation of the first group of parity check bits. This scheme is better illustrated with an example. Let us consider a 128-bit data block and 3 control bits protected with 8 parity check bits. Those 8 bits are divided in a group of 3 shared between data and control bits and a second group of 5 that is used only for the data bits. To protect the control bits, the first three parity check bits can be assigned different values for each control bit, and the remaining parity check bits are not used to protect the control bits. The rest of the values are used to protect the data bits, and for each value, different values of the remaining five parity check bits can be used. In this example, the first group has 3 bits that can take 8 values, and three of them are used for the columns that correspond to the control bits. This leaves 5 values that can be used to protect the data bits. The second group of parity check bits has 5 bits that can be used to code 32 values for each of the 5 values on the first group.
Advantages:
- Area coverage is low
- Speed is increased
Software implementation:
- Modelsim
- Xilinx ISE