Ph.D Thesis


Ph.D StudentRam Eshed
SubjectLDPC Codes with Sub-Block Locality
DepartmentDepartment of Electrical and Computers Engineering
Supervisor ASSOCIATE PROF. Yuval Cassuto
Full Thesis textFull thesis text - English Version


Abstract

The growing demand for denser storage devices leads to an increase in their error rates. In order to fulfill the increasing requirements for information reliability and density, state-of-the-art error-correcting codes should be employed. One of the most promising error-correcting codes known nowadays is the family of graph codes called LDPC (Low-Density Parity-Check) codes, which presents outstanding noise resilience with high rates and low-complexity decoding algorithms.


In contrast to communication applications, where information is transmitted from one point in space to another, in storage systems information is transferred through time: the user writes information to the device, and reads it in some time in the future, possibly after the device suffered some errors/erasures. This fundamental difference leads to important engineering implications. Such is the need for extremely reliable storage systems; while in communication protocols the receiver can (and does!) ask the transmitter to re-transmit its message in case of a decoding failure, in storage applications every decoding failure implies data loss. Hence, error-correcting codes used in storage devices need to provide extreme low failure probabilities compared to those used in communication applications. On the other hand, this noise resilience comes with a price in the form of very large block sizes and complex decoding, both impeding the read-access speed.


This PhD thesis's objective is to solve the access vs. reliability conflict by introducing multi-sub-block LDPC codes. The main observation we make is that one can enjoy both worlds: small sub-blocks for fast access, and large blocks to prevent data losses in case of extreme error events. The solution includes novel code constructions that enable local decoding of small sub-blocks and global decoding of large blocks. Local decoding is fast and its noise-resilience is lower than the worst-case requirements; in case of a local failure, a "safety-net" code on the large block provides the information-reliability needed; we call codes in this framework LDPCL codes (suffix 'L' stands for locality).

We construct LDPCL codes and spatially coupled (SC) LDPCL codes, and analyze the belief-propagation decoding algorithm on them. We enhance LDPC structures to offer sub-block locality properties, prove that it is possible to approach capacity both in the local and global codes, and show how to efficiently combine between a simpler local code and a strong global code.


One of the contributions of this thesis is a new BP-based decoding strategy we call semi-global decoding, in which in addition to the requested sub-block, the decoder has access to some prescribed number of sub-blocks around it. We study and analyze the performance of semi-global decoding, and show that it exhibits a significant complexity reduction compared to global decoding, while costing only a small fraction in the correction capabilities. We consider practically motivated data-storage models in which variability is introduced to the channel quality, and show that semi-global decoding is highly motivated by these models.