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.