UCLA

This dissertation mainly focuses on two different branches of coding theory and its applications:1) coding to approach capacity in short blocklengths using feedback and 2) LDPC coding for Flash memory systems. In the first area, we study the benefits that feedback with incremental redundancy can provide to increase the maximum achievable rate in communication systems, using carefully designed adaptive non-binary LDPC codes. We show how to achieve over 90% of the idealized throughput of rate-compatible sphere-packing with maximum-likelihood decoding (RCSP-ML) for average blocklengths of 150-450 bits. This is important because it illustrates that feedback greatly reduces the number of transmitted symbols required to achieve near-capacity performance.

We then extend these ideas to feedback systems where the number of incremental transmissions is limited. In order to optimize the blocklengths for each incremental transmission we formulate an integer optimization problem involving an approximation based on the inverse-Gaussian p.d.f., the distribution of the blocklength required for successful decoding. The brute-force approach to solve this computationally complex optimization problem quickly becomes infeasible. In order to solve this problem efficiently, we introduce sequential differential optimization (SDO) algorithm that has only linear complexity to identify optimal incremental transmission lengths. The results obtained from SDO are negligibly different from the exponentially complex exhaustive-search solution. By using the optimized incremental transmission lengths (with an average blocklength of less than 500 bits), non-binary LDPC codes achieve a throughput greater than 90% of the capacity with a

two-phase scheme. Furthermore, we extend these ideas to the case of using cyclic redundancy checks (CRC). With CRC, even better performance in the blocklength range of about 500 bits is obtainable. The overhead associated with a CRC prevents great performance in short blocklength regime (fewer than 400 bits). We also extend these ideas to systems with larger constellations operating at a higher signal-to-noise ratio (SNR).

Another incremental transmission coding scheme studied in this dissertation focuses on de- sign and use of rate-compatible protograph-based raptor-like (PBRL) LDPC codes with various blocklengths and rates that can be used in feedback systems over additive-white Gaussian noise (AWGN) channels. The codes proposed in this work use X-OR operations and density evolution to produce additional degree-one parity bits providing extensive rate compatibility. The protographs are also carefully lifted to avoid undesirable graphical structures such as problematic stopping sets. For a target frame error rate of 10−5, at each rate the k = 1032 and k = 16384 code families perform within 1 dB and 0.4 dB, respectively, of both the Gallager bound and the normal approximation. The k = 16384 code family outperforms the best known standardized code family, the AR4JA and longer DVB-S2 codes.

We extend the ideas in design of PBRL codes from AWGN channels to binary symmetric channels (BSC) and binary erasure channels (BEC). We introduce two fast and efficient algorithms to calculate the threshold of LDPC codes used over BSC. These algorithms serve as alternatives to the quite complex density evolution algorithm. Since these new algorithms are quite fast, we use them to design PBRL LDPC codes for BSC.

To explore the advantage of feedback in conjunction with other modern coding schemes, in this work we use an extension of reciprocal channel approximation (RCA) to accurately and effi- ciently predict the frame error rate (FER) performance of polar codes by analyzing the probability density function (p.d.f.) of the log-likelihood ratio (LLR) values associated with information bits. The preliminary results show that a feedback scheme in conjunction with a repetition coding sys- tem significantly reduces the blocklength required to achieve a target FER. For example, using a rate-0.5 128-bit polar code as the initially transmitted code, the theoretical analysis verified by simulation shows a 16-fold reduction in blocklength with only about 7.4% of overhead in forward channel transmissions. We also make an improvement to this feedback coding scheme which reduces the overhead to almost 3% for a similar FER performance gain.

The second part of this dissertation focuses on design of binary and non-binary LDPC codes for Flash memory systems. Usually the FER requirements in Flash memory systems is more strict than wireless communication systems. In order to improve the error correction capability of the codes used in Flash memory systems, sometimes the same memory cell is read multiple times. In this dissertation, we study the coding gain from multiple reads of the same Flash memory cell with distinct word-line voltages. The subsequent additional reads provide enhanced precision for LDPC decoding. We identify a trade-off in LDPC code design when decoding is performed with multiple precision levels and conclude that the best code at one level of precision is typically not be the best code at a different level of precision.

By studying the trade-off in LDPC code design by using extrinsic-information-transfer (EXIT)- function analysis employing the reciprocal channel approximation (RCA), we obtain the optimal LDPC code degree distributions for initial hard decoding (one-bit quantization of the channel out- put) and for decoding with the soft information provided by subsequent additional reads in both SLC (two-level cell) and MLC (four-level-cell) Flash memory. The results indicate that design for hard decoding can provide irregular degree distributions that have good thresholds across a range of possible decoding precisions. Finally, we illustrate that the MMI optimization of word-line voltages for five reads is a quasi-convex problem for the Gaussian model of SLC Flash.