{'fraction_non_alphanumeric': 0.025848142164781908, 'fraction_numerical': 0.0032310177705977385, 'mean_word_length': 4.855791962174941, 'pattern_counts': {'":': 0, '<': 0, '<?xml version=': 0, '>': 0, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Low-density parity-check codes: constructions and bounds

Low-density parity-check (LDPC) codes were introduced in 1962, but were almost forgotten. The introduction of turbo-codes in 1993 was a real breakthrough in communication theory and practice, due to their practical effectiveness. Subsequently, the connections between LDPC and turbo codes were considered, and it was shown that the latter can be described in the framework of LDPC codes. In recent years, low-density parity-check codes have been a subject of much experimentation and analysis. It was shown that, in practice, LDPC codes perform extremely well. The most common approach to the analysis of LDPC codes is based on probabilistic methods, which consider so-called ‘average LDPC codes’. This approach led to remarkable results on the performance of LDPC codes. However, there is still a gap between our understanding of LDPC code ensembles and characteristics of specific LDPC codes. One promising approach for constructing specific LDPC codes is based on using expander graphs. Some of these codes (called expander codes) allow both linear-time encoding and decoding. Recently, it was shown that such codes can attain capacity of a variety of channels, while the error probability decreases exponentially with the code length. One of the main characteristics of any code family is a trade-off between its rate and its relative minimum distance: it was recently shown for the binary expander codes that this trade-off surpasses the Zyablov bound, which was used as a benchmark for evaluating the parameters of codes for many years. In this thesis, we present improvements on the known bounds on the parameters of expander codes. We (slightly) improve the lower bound on the minimum distance of expander codes. We show that these codes can be viewed as a concatenation of a nearly-MDS expander code with an appropriate inner code. We suggest that GMD-decoding can be efficiently used for these codes. Thus, those nearly-MDS codes admit a linear-time encoding and decoding. Their alphabet size is smaller than the alphabet size of similar known codes. By employing this approach, we are able to present a new decoding algorithm for expander codes together with a novel analysis. We show that our algorithm can correct (slightly) more errors than any known decoding algorithm for expander codes. Moreover, the decoding time of our algorithm has only polynomial dependence on the degree of the underlying graph.