NAND Flash ECC Check Based on FPGA

In the field of mobile product applications, NAND Flash devices have become a dedicated method for people to solve high-density solid-state storage. With the rapid development of information technology, people's demand for information is also increasing. Therefore, when a large amount of data is stored and transmitted within the system and between networks, it is particularly important to detect and correct possible errors in the data. Error Correction Code (ECC) meets this demand. It is called ECC check and is a check code commonly used in NAND Flash read and write controllers.

ECC checking is responsible for detecting errors, maintaining ECC information, and correcting single-bit errors that have been changed from the original value. All ECC operations can be controlled by an ECC module, which is placed between the NAND device and the processor interface as a simple storage-mapping interface. This module generally includes a Hamming code generation module and an error location module, which are used to generate ECC check codes and calculate error locations, respectively.

1Haremina Encoding

Hamming coding is simple to calculate. The Hamming algorithm widely used in NAND Flash obtains two ECC values ​​by calculating the data packets on the block. To calculate the ECC value, the bit data in the data packet must first be divided, such as 1/2 group, 1/4 group, 1/8 group, etc., until its accuracy reaches a single bit. Take an 8-bit or 1-Byte data packet as an example, as shown in Figure 1.

The data is bit-segmented as shown in Figure 1, and the upper even check value ECCe and the lower odd check value ECCo are obtained. Among them, the 1/2 check value is used to form the most significant bit of the ECC check after the "XOR" operation. Similarly, the 1/4 check value forms the second most significant bit of the ECC check, and the least significant bit is filled by the bit-specific check value. Figure 2 shows the calculation process of the two ECC check values.

That is, the even parity check value ECCe is "101", and the odd parity check value ECCo is "010". Figure 1 shows a data packet with only 1 Byte of data. Larger data packets require more ECC values. In fact, the ECC value of each nbit can meet the parity check requirement of a 2nbit data packet. Since this Hamming code algorithm requires a pair of ECC data (odd and even), a total of 2nbit of ECC check data is required to process a 2nbit data packet.

After calculation, both the original data packet and the ECC value are written to the NAND device. Later, the original data packet is read from the NAND device and the ECC value is recalculated. If the newly calculated ECC is different from the ECC previously programmed into the NAND device, then an error has occurred in the data read or written.

For example, if there is a single bit error in the original data 01010001, the data after the error is 01010101. As shown in FIG3 , the two new ECC values ​​are different from the original ECC values ​​due to the change in data calculated by the method shown above.

At this time, all 4 ECC values ​​are bit-wise "XORed" to determine whether a single-bit error or a multi-bit error has occurred. If the calculation result is all "0", it means that the data has not changed during the reading and writing process. If the calculation result is all "1", it indicates that a 1-bit error has occurred, as shown in Figure 4. If the calculation result is any case other than all "0" and all "1", then it is a 2-bit error. 2-bit errors can always be detected, however, the Hamming code algorithm can only guarantee the correction of single-bit errors. If two or more bits are wrong, the erroneous data packet cannot be modified. In this case, the Hamming algorithm may not be able to indicate that an error has occurred. However, considering the bit error situation of SLC NAND devices, the possibility of 2 or 3-bit errors is very low.

For a 1-bit error, the error address can be identified by performing bit-wise XOR on the original ECCo value and the new ECCo value. The result of the calculation in Figure 5 is 2, indicating that there is a problem with the second bit of the original data. This calculation uses odd parity data ECCo because they can directly reflect the location of the error bit.

After finding the error bit, the data packet can be repaired by simply flipping its state, which is to perform an XOR operation on the bit with "1", as shown in Figure 6.

2 Extended Data Packet

In the above example, 6 bits of ECC data are required to verify an 8-bit data packet. In this case, the amount of data to be verified reaches 75% of the original data packet, which does not seem satisfactory. However, as the size of the data packet increases, the Hamming algorithm will become more and more efficient. From the previous relationship that 2nbit data requires 2nbit ECC verification, it can be inferred that each doubling of data requires two additional ECC information bits. In this way, when the data increases to, for example, 512Byte, only 24bit ECC is generated, and the proportion of data used for verification in the original data is reduced to 0.06%, which is more efficient. Below, an 8-Byte data packet is used as an example to illustrate the verification of the extended data packet. [page]

Here, since the XOR operation satisfies the commutative law, a more effective method is used for verification. As shown in Figure 7, the 8-Byte data is first arranged in the form of a matrix, with each row being 1 Byte-wise. The XOR result of each bit in each row is calculated separately and recorded as a byte check code (Byte-Wise), and the XOR result of each bit in each column is calculated as a bit check code (Bit-Wise). Next, the two check codes are divided and calculated according to the above method to obtain the ECC check code, and the ECC result of the byte check code is used as the high significant bit (MSB) of ECCe and ECCo, and the ECC result of the bit check code is used as the low significant bit (LSB) to combine, and finally the ECC check code of the 8-Byte data packet is obtained.

When an error occurs in a data packet, the error detection and correction method used is similar to the method described previously. Here, the verification process is still explained using a 1-bit error, as shown in FIG8 .

After calculations in steps 1 to 4, the new data packet has an error and the error position is "110010". Since the byte check code is set to the high bit of the ECC value and the bit check code is set to the low bit, the high significant bit of "110010" represents the erroneous byte address, and the low significant bit represents the erroneous bit address, that is, the data with byte address 6 and bit address 2 has an error, which is consistent with the set error situation. At this time, the data bit of this position only needs to be XORed with "1" to complete the correction of the data packet.

Expanding the 8-byte data packet to a 512-byte data packet, although the amount of data has greatly increased, only the case of data segmentation has been added, and the algorithm remains the same. The calculated parity ECC data is 12 bits long, of which the 3 low-significant bits represent the bit address (7 to 0) and the 9 high-significant bits represent the 512-byte address (255 to 0).

3 Experimental analysis

This experiment processes a 256-byte data packet, and performs ECC check on it to generate a total of 22 bits of check data. For easy reading, two bits can be added at the end to form a complete 3-byte check data. These 3 bytes are 24 bits in total, divided into two parts: 6 bits of bit check and 16 bits of byte check. The extra two bits are set to 1 and placed in the lowest bit of the check code. These two bits are ignored when performing XOR operations.

When writing data to a NAND Flash page, an ECC checksum is generated for every 256 bits, called the original ECC checksum, and saved in the OOB data area of ​​the page; when reading data from NAND Flash, a new ECC checksum is generated for every 256 bits, called the new ECC checksum. During the check, the original ECC checksum read from the OOB area is subjected to a bitwise XOR operation with the new ECC checksum. If the result is all "0", it indicates that there is no error, and the error status variable errSTATUS is assigned to "00"; if the result is all "1", it indicates that a 1-bit error has occurred, and errSTATUS is assigned to "01" and corrected; in other cases except all "0" and all "1", errSTATUS is assigned to "10" to indicate that an uncorrectable 2-bit error has occurred, as shown in Table 1.

The experimental simulation environment is Altera Quartus II 7.0, and the programming language is VHDL. VHDL is a hardware programming language with the characteristics of parallel processing. There are a large number of XOR operations that need to be processed in parallel in the original program, so the program execution efficiency is high, which is very conducive to hardware implementation.

Figure 9 shows the verification of a 1-bit error in a data packet. Among them, DATAin represents the data to be read, HammingCALC represents the original ECC calculated when writing the NANDFlash page, HAMMINGout represents the new ECC calculated when reading the DATAin data later, errSTATUS is the error status, and ERRIoc is the calculated error position. In order to meet the conditions of a 1-bit error and make it easy to observe, the last Byte of the 256-Byte data (0-255) is changed from "11110110" to "11111110", as shown in the shaded part of Figure 9. At this time, the errSTATUS result is "01", indicating that the program has detected the 1-bit error, and the ERRloc output is "111111111O11", that is, the error position is bit 3 of the 255th Byte. To correct the error, at this time, just invert the bit at this position and output it.

In the case of the original 1-bit error, the adjacent 254-bit data is changed from "11110101" to "01110101", as shown in the shaded part of Figure 10. Two bits of the entire data packet have changed. At this time, the errSTATUS result is displayed as "10", which means that a 2-bit error has been detected. However, ERRloe is invalid at this time and cannot represent the two error locations. This is why the ECC check can only detect a 2-bit error but cannot correct it.

Of course, if there is no error in the data packet, that is, if the read data is exactly the same as the previously written data, the ECC check can also ensure detection. As shown in Figure 11, when no error occurs, errSTATUS is "00", verifying the consistency of the data. At this time, ERPloe is meaningless.

It is worth noting that if the packet has more than 2 bits of error, the algorithm is not suitable. The case of more bits (≥3) being wrong was measured, and the results showed that the result of errSTATUS could be any one of "00", "01", and "10", that is, in this case, the algorithm is likely to make a false detection. Therefore, here, we can draw a conclusion consistent with the ECC verification principle: ECC can guarantee the correction of 1-bit errors and the detection of 2-bit errors, but it cannot correct errors above 1 bit, and it cannot guarantee the detection of errors above 2 bits.

4 Conclusion

This paper uses the hardware programming language VHDL to perform post-simulation testing on the ECC check algorithm in the AheraQuanusⅡ7.0 development environment, and realizes the ECC check function of NAND Flash. This program can generate 3-byte ECC check data for every 256-byte data, and by comparing with the original ECC data, it can ensure the detection of 1-bit errors and their error locations. Further combined with the correction of this error, it can be applied to the FPGA design of NAND Flash read-write controllers to realize ECC check of data and ensure that data is ready for effective transmission. According to the feedback from the hardware experimental results, the algorithm has good hardware adaptability.

ECC is a special checksum used in NAND Flash processing. Its principle is simple, easy to execute, fast in calculation, and the larger the amount of data, the more effective its algorithm is. However, such an efficient algorithm still has a flaw, that is, its limited error correction capability. This article also verifies that it is ineffective for errors above 2 bits. Although the probability of this happening in Flash is very low, in terms of the checksum principle, whether there is an improved algorithm that can be used to correct multi-bit errors needs further research and verification.