Flash Controllers Get Better Efficiency With Low Density Parity Check (LDPC)

What does satellite communication and flash storage have in common? They are both prone to errors and they need error correcting codes to provide reliable data exchange. They are also increasingly taking advantage of low density parity check (LDPC) code technology.

Related Articles

In the past, parity, CRC and other error detection and correction technologies were employed because they were easier to implement and the amount of data was smaller. Flash storage has grown dramatically as has satellite communication bandwidth. Other data storage and transmission areas have grown as well requiring more efficient encoding schemes.

Turbo codes are one answer to the problem of forward error correction (FEC). Turbo codes were developed in 1993 but prior to this, Robert G. Gallager developed LDPC. The concept was in his 1960 MIT doctoral dissertation that he developed further. Wikipedia's low-density parity-check code article is a good starting point for understanding how LDPC works.

Essentially LDPC codes are a class of FEC codes that are based on a sparse matrix parity check. The challenge is that optimal decoding of LDPC is an NP-complete problem. This is one reason LDPC and turbo codes were not employed earlier because the logic overhead is higher than other FEC codes like Reed-Solomon and BCH (initials of inventors Raj Bose, D. K. Ray-Chaudhuri and Alexis Hocquenghem). High density logic has made support of these codes practical.

The other issue with LDPC decoding is that it can be done in an iterative fashion with approximations that may provide sufficient information about errors or error corrections. This allows fast operation when the error rate is lower with increasing delay and overhead as the error rate increases.

The iterative nature and hardware support of LDPC is why LDPC was used in the DVB-S2 standard for the satellite transmission of digital television over multiple turbo code options. This was also the case for the ITU-T G.hn standard. It is also why high density flash memory controllers are employing this technology.

LSI's Shield error correction technology utilizes LSI's advanced LDPC approach in their SandForce flash controller. Other flash memory controller vendors have taken a similar approach using different LDPC implementations. The lack of patents in this area has fueled the growth and adoption of LDPC in general.

Shield employs a hierarchical combination of hard-decision LDPC (HLDPC) and soft-decision LDPC (SLDPC). HLDPC is the initial error check that can operate at hardware line rates even for very high speed transfers. The implementation tends to be the same for most vendors in this space. SLDPC is where there is more implementation variance and more options.

LSI employs multiple SLDPC decoding engines that operate in parallel including DSP-aided SLDPC support and intelligent noise handling support in multi-level error correction scheme. Unlike a simple CRC that has a fixed computation overhead, this approach may find a solution quickly or take much longer but it can handle more errors. In general, fewer errors will result in faster operation.

LSI's adaptive approach has some interesting when it comes to flash storage. In general, data storage is divided into usable data space and error detection/correction space. Normally a user does not see the latter assuming that the data is correct based on this information. Basic parity or ECC techniques have a fixed overhead that is normally applied at the word level.

NAND flash operates at the block level and in the past this error correction overhead was also fixed but LDPC changes this because its size is based on the error rate. NAND flash error rates increase over time as the flash is repeatedly written. Techniques like wear leveling increase the overall lifetime of this storage but the error rate also increases. This means the initial LDPC overhead can be lower at the start.

Likewise, over provisioning (OP) is a technique to push back the end-of-life (EOL) of a device. Combine OP with LDPC and the result is a more dynamic management scheme that can move back EOL while increasing the virtual memory capacity which is what LSI calls DuraWrite Virtual Capacity (DVC). DVC provides a more dynamic utilization of NAND flash for data and ECC (Fig. 1). DVC also adds a SMART (Self-Monitoring Analysis and Reporting Technology) attribute so the applications can track the underlying disk availability and lifetime.

Figure 1. LSI's Shield technology combines LDPC and dynamic memory management to transparently provide more storage and longer device lifetime.

DVC has the largest advantage for low entry workloads such as boot or caching drives. LSI's new SF-2000 flash controller family support Toshiba’s 19-nm NAND flash memory (A19nm).