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.

This thesis consists of two main sections investigating the performance of cyclic-redundancy-check-aided (CRC-aided) list decoding on short block codes. The first section analyzes the performance of tail biting convolutional codes with CRC (CRC-TBCCs) and polar codes with CRC (CRC-Polar) with an eye toward the 5G standard. The second section concerns designing optimal CRC-convolutional codes for nonbinary orthogonal noncoherent signaling.

The first section focuses on designing a code for the physical broadcast channel of the 5G standard. The 5G standard encodes a 32-bit message with a 24-bit CRC and a (512, 32+24) polar code, with bit repetition to arrive at a final blocklength of 864 bits. We design shorter CRCs for this polar code in order to improve its performance. We also design low rate CRC-TBCCs with 32 bit messages as an alternative to the CRC-Polar in the 5G PBCH. CRCs are designed to optimize the distance spectrum of the concatenated CRC-Polar or CRC-TBCC. We call these CRCs distance-spectrum-optimal (DSO). We consider both adaptive and nonadaptive list decoders for these codes and compare their performance and complexity. Simulation results show that our CRC-TBCC and CRC-Polar designs significantly outperform the polar code in the 5G standard, with some CRC-TBCC designs closely approaching the random coding union (RCU) bound.

The second section presents designs for CRC-TBCCs and zero-terminated convolutional codes with CRC (CRC-ZTCCs) for communication with noncoherent orthogonal signaling. We design Q-ary convolutional codes to maximize the minimum distance, and then design Q-ary DSO CRCs for these convolutional codes, extending the work of Lou et. al. and Yang et. al. to nonbinary fields. The Q-ary code symbols are mapped to a Q-ary orthogonal signal set and sent over an AWGN channel with noncoherent reception. We consider cases where Q is a power of 2. We also derive a saddlepoint approximation for the calculation of the RCU bound for this channel. The RCU bound is a useful benchmark for the performance of CRC-convolutional codes, and we compare the performance of our codes to this bound.

This dissertation proposes mathematical algorithms for improving Flash-based storage system's four key performance metrics: lifetime, reliability, latency and throughput.

The first part of the dissertation presents the novel concept of dynamically voltage allocation (DVA) for Flash memory. Flash memory suffers reduced reliability as the number of program/erase (P/E) cycles increases, thus has a limited lifetime. DVA scales the write threshold voltages of Flash memory adaptively, using lower voltages at the beginning of the lifetime, and gradually increases the scaling to combat the effect of accumulated wear-out from P/E cycling. The proposed algorithm significantly increases the lifetime of the device.

The second part of the dissertation introduces the novel design of error correction using incremental redundancy without feedback. Modern storage systems often require high throughput, high reliability and low latency. Traditional variable-length (VL) codes with feedback have demonstrated to provide high throughput and reliability. The new design reinterprets the results for VL codes with feedback using ergodicity, by encoding the incremental redundancy of multiple VL codewords to a common pool of redundancy. The removal of feedback allows storage systems to benefit from the performance of a feedback scheme with a feedforward design. The decoder of the new design exploits the low complexity of short-blocklength decoders and the parallelization structure to reduce latency. The proposed error correction scheme approaches the throughput of corresponding VL codes with feedback.

Relying on information theory and coding theory, the proposed algorithms provide new approaches to optimize the Flash-based storage systems.

Feedback links are ubiquitous in modern communication systems. This dissertation is focused on the short-blocklength performance of coded communication systems with feedback and is organized in three main parts. The first section presents a novel reliability-output decoding algorithm for tail-biting convolutional codes, based on Raghavan and Baum's Reliability-Output Viterbi Algorithm (ROVA) for terminated convolutional codes. Whereas terminated convolutional codes suffer from a rate penalty at short blocklengths, tail-biting convolutional codes do not suffer from rate loss, making them throughput-efficient and suitable for used in reliability-based retransmission schemes with short blocklengths.

The second portion of the dissertation analyzes the performance of deterministic variable-length feedback coding schemes, focusing on blocklengths less than 300 symbols. In both the decision-feedback and information-feedback settings, we demonstrate that tail-biting convolutional codes can deliver rates surpassing the random-coding lower bound at blocklengths less than 100 symbols. The decision-feedback scheme uses the tail-biting ROVA to determine when to stop transmission, which requires only a single bit of feedback (ACK/NACK) after each decoding attempt. In contrast, the information-feedback scheme employs two-phase incremental redundancy and uses feedback of the received symbols to confirm or reject the decoder's tentative estimate. Finally, we discuss implications of these schemes when used in practical systems, namely the performance when decoding is limited to packets instead of individual symbols.

Finally, using the information-theoretic framework of the second section, the third part of this dissertation investigates the energy efficiency of variable-length feedback codes compared to that of fixed-length block codes without feedback. While the latency reduction obtained with feedback can decrease transmitter power consumption, attempting decoding after every received symbol significantly increases receiver power consumption. Care must be taken to choose decoding intervals that balance the competing interests of transmitter and receiver power.

The reliable communication of short messages provides a foundation for today's information ecosystem. Text messages, control messages that initiate and manage calls on the cellular network, and messages from millions of sensors in the internet of things all need to communicate short messages promptly and reliably. For short messages, list Viterbi decoding (LVD) of tail-biting convolutional codes (TBCCs) aided by a cyclic redundancy check (CRC) has been shown to approach the random-coding union bound on frame error rate. There are two alternative approaches to LVD, serial LVD (S-LVD) and parallel LVD (P-LVD). Both S-LVD and P-LVD approach maximum-likelihood (ML) decoding performance as the maximum list size is increased. While several recent papers have focused on serial LVD, parallel LVD offers significant structural advantages for an implementation on a field-programmable gate-array (FPGA) board. This thesis presents a complete FPGA implementation of P-LVD and analyzes its performance. The thesis begins by introducing the general LVD paradigm and comparing P-LVD with S-LVD in terms of throughput and computational complexity. An adaptive version of P-LVD allows the list size to grow as with S-LVD. The thesis investigates various hardware architectures, culminating with selection of the best trade-off between throughput and FPGA resource requirements. The conclusion describes several directions for future work on this exciting and relevant area at the crossroads of cutting edge communication theory and practical communication system implementation.

This dissertation investigates communication over the binary symmetric channel with noiseless feedback of the received symbols from the decoder to the encoder. The binary symmetric channel receives as input a binary symbol, and produces as output also a binary symbol, that may be different to the input symbol. The channel is symmetric in the sense that the probability that the output symbol is not equal to the input symbol is the same for both input symbols. The general communication problem consists of reliably relaying a message from a source (where it is generated) to a destination (where it is needed) while using the least possible system resources. Reliability in this case is defined as a small error probability--the probability that the message at the destination differs from that at the source. System resources include forward channel symbol transmissions, encoder and decoder complexity, and possibly other resources that may be associated with a cost, like the number of times the feedback channel is accessed for a feedback transmission. The system operates as follows: the source delivers its message to an encoder, that computes channel input symbols; the channel produces output symbols that are noisy versions of the input symbols; a decoder uses channel output symbols to compute an estimate of the message at the encoder; and a noiseless feedback channel delivers the output symbols to the encoder, which affords the encoder all the information available to the decoder.The objectives of this dissertations are (1) to design encoding methods that can be implemented in simulations; (2) explore simplifications that make the implementations more efficient; (3) analyze the expected rate that can be achieved with all the proposed encoding methods, including the simplifications; (4) analyze converse bounds, the lowest rates that cannot be achieved with the system while satisfying an error probability constraint; and (5) explore communication with additional constraints, like source causality constraints and feedback sparsity constraints.

Chapter 1 lays out the background and motivation of the research problems studied in this dissertation, and summarizes previous results and about related problems. Then, Chapter 1 briefly summarizes the contents of each Chapter.

Chapter 2 provides efficient algorithms and a simulation framework that implements previously proposed encoders as well as new ones. Simulation results validate previous achievability bounds and motivate tighter achievability bounds. Chapter 2 also proposes a simpler encoding rule, that greatly lowers the runtime and memory complexity, and exhibits a rate performance indistinguishable from the encoders with the highest existing achievability bounds. The performance of the new encoder is further analyzed in Chapter 3.

Chapter 3 demonstrates a new analysis of the expected blocklength needed to transmit a fixed length information sequence with bounded error probability. The new analysis relaxes the sufficient encoding constraints that guarantee an expected rate performance above the highest achievability bounds previously developed for the model. To tighten an upper bound on expected time, analyzed for the first phase of a two-phase process, this chapter proposes an analysis of a ``surrogate process,'' for which a tighter bound can be shown. The ``surrogate process'' is carefully constructed from the original process, so that its decoding time upper bounds that of the original process. This property guarantees that the tighter bound on the ``surrogate process'' applies to the original, and results in a significantly higher achievability bound. The bounds are tightened further by jointly optimizing both phases of the two-phase analysis used to obtain the original bounds. A proof that the simple encoder of Ch. 2 satisfies the relaxed constraints is provided. Chapter 3 then proposes a converse bound, an upper bound on the highest expected rate that is achievable by an encoder that enforces the stopping rule used by the proposed encoders.

Chapter 4 extends the study of feedback codes over the binary symmetric channel to the ``causal encoding'' setting, where the source information sequence becomes progressively available during transmission instead of the traditional setting where the entire source sequence is available before transmission begins. In ``causal encoding'' the encoder seeks to minimize the average decoding delay under the same frame error rate constraint considered in Ch. 2 and Ch. 3. The sub-block combining algorithm is proposed as a ``causal encoder,'' that starts the transmission with a segment of the information sequence, and adds new segments as they become available. The chapter identifies lower bounds on expected decoding times imposed by the channel and the source, as well as the region where a causal encoder may outperform existing non-causal encoders. Simulation results are provided to show that the sub-block combining algorithm outperforms, in average decoding time, non-causal encoders, in their original form, and with natural modifications that make them better ``causal encoders'' under certain conditions. The performance of the sub-block combining algorithm is further improved using a method that analyzes optimized block sizes for the specific operating point, set by the source and channel symbol rates.

Chapter 5 studies the ``sparse feedback'' setting where feedback symbols are only available to the transmitter at sparse time instances, instead of being available before the transmission of each symbol. A new encoding rule is introduced, that also satisfies the relaxed constraints proposed in Ch. 3. Then the ``look-ahead algorithm'' is proposed, to satisfy the encoding constraints for a few transmissions in advance, without additional feedback. Simulation results show that the ``look-ahead algorithm'' admits average feedback delay that increases with message length, from slightly above one transmission at a message length of about ten bites, to about five to six when the message size reaches 80 bits. The sub-block combining algorithm of Ch. 4 is modified to operate on several blocks simultaneously and used as a sparse feedback encoder. This algorithm exhibits much lower complexity, which makes it suitable for message sizes of up to a few hundred bits, that are not possible with the look-ahead algorithm.

Chapter 6 provides the conclusions of this dissertation, and highlights future research directions.

This dissertation consists of three parts. The first part considers the archetypical multiterminal source coding problem with logarithmic loss distortion constraints. A single-letter description of the achievable rate distortion region is given for finite-alphabet sources. In the course of doing so, the rate distortion region for the m-encoder CEO problem is also characterized. Several applications and examples are given, and a variety of related problems are discussed.

The second part of this dissertation considers the combinatorial problem of Coded Cooperative Data Exchange. In this problem, data which is originally distributed in a network is exchanged among nodes until universal recovery is achieved (i.e., all terminals recover all data initially present in the network). This dissertation characterizes the minimum number of exchanges which must take place in order to permit universal recovery. Explicit algorithms and tight concentration results are given for several special cases of interest.

Finally, three new lemmas are provided, each of which is interesting in its own right. Applications to multiterminal information theory are discussed.

This thesis consists of an introduction, four main sections, and conclusion. The introduction gives a quick overview of communication channels and the basics of message passing algorithms. The first section focuses on the challenges of communicating over a fading channel using optical transmitters and receivers. Recognizing the limitations of a purely optical transmission system during environmental fades, the section proposes a hybrid RF-Optical system. The hybrid system consists of a high-throughput optical link closed by a Low Density Parity Check (LDPC) code alongside a separate RF link. The section proposes two different architectures for a hybrid system with varying degrees of mixing between the two links. For each architecture, their performance was evaluated during on a simulated fading channel and Additive White Gaussian Noise (AWGN) channel.The second section of this thesis capitalizes on the recent advancements in deep learning and applies it to the most popular LDPC decoding process known as message passing. The section first deconstructs the steps of message passing into nodes that can be interpreted as a type of Neural Network. Then, utilizing gradient descent methods including Adaptive Movement Estimation (ADAM), multiplicative weights for message passing are found and optimized. The key contribution of the section is the connection between these multiplicative weights and properties intrinsic to the LDPC code structure. By exploiting this relationship, a weight-sharing paradigm based on node degree is proposed, resulting in a Neural-Normalized MinSum (N-NMS) decoder which dramatically reduces the complexity of both training and implementation compared to typical neural network based decoders. The third section discusses a unique case study involving the Consultative Committee for Space Data Systems (CCSDS) 141.11-O-1 Line Product Code (LPC). Being such a short block-length code, two Maximum Likelihood (ML) decoders were evaluated against message passing decoders including MinSum (MS), Belief Propagation (BP), and Neural-Normalized MinSum (N-NMS). Analysis was carried out considering both the decoding performance and resulting hardware complexity of the decoders. Continuing on this, the fourth and final section aims to give additional insight as to why the N-NMS decoder performed so well on the LPC. This section proposes that the unique graph structure of the LPC allowed for key optimizations such as breaking length-4 cycles that the N-NMS training process capitalized on during its training.

Focusing on the analysis and system design for single-user communication with noiseless feedback, this dissertation consists of two parts. The first part explores the analysis of feedback systems using incremental redundancy (IR) with noiseless transmitter confirmation (NTC). For IR-NTC systems based on finite-length codewords and decoding attempts only at certain specified decoding times, this dissertation studies the asymptotic expansion achieved by random coding, provides rate-compatible sphere-packing (RCSP) performance approximations, and presents simulation results of tail-biting convolutional codes. The RCSP approximations show great agreement with the convolutional code simulations. Both the approximations and the simulations yield expected throughputs significantly higher than random codes at short latencies.

Motivated by the analyses and optimizations in the first part, the second part of this dissertation proposes a new class of rate-compatible low-density parity-check codes, called Protograph-Based Raptor-Like (PBRL) codes. Similar to Raptor codes, PBRL codes can efficiently produce incremental redundancy, providing extensive rate compatibility. The construction and optimization of PBRL codes suitable for both long-blocklength and short-blocklength applications are discussed. Finally, this dissertation provides examples of constructing PBRL codes with different blocklengths. Extensive simulation results of the PBRL code examples and three other standardized channel codes (3GPP-LTE, CCSDS and DVB-S2) are presented and compared.

This dissertation consists of three parts. The first part focuses on a class of modern channel codes known as protograph-based low-density parity-check (LDPC) codes. Also known as protograph LDPC codes, these powerful error-correcting codes have enabled communication systems of the past fifteen years to achieve very high throughputs. The first part of the dissertation presents a new design method based on an upper bound on minimum distance to obtain rate-compatible, protograph quasi-cyclic (QC) LDPC codes called Protograph-based Raptor-like LDPC codes (PBRL codes). A major contribution here is a very-low-complexity PBRL design algorithm that is provably efficient.

The second part of the dissertation continues the focus on protograph LDPC codes, first exploring how the decoding complexity of PBRL codes can be reduced and whether the extending structure that provides rate-compatibility to a PBRL code is optimal or not. Then, this part considers the problem of design of PBRL codes for any increment ordering. The degree-1 extending structure yields naturally to the design of PBRL codes that decode efficiently even when increments arrive out-of-order. This part finally considers the following question: What is the shortest block-length required to obtain a protograph QC-LDPC code with a girth of at least 6 or 8 from a (3, L) complete protograph? An affirmative answer is given for girth of at least 6 and directions are explored for girth of at least 8.

Finally, the dissertation turns to communication theory and tackles a rate allocation problem previously studied in literature, but with an important twist. Consider a cross-layer coding scheme with packet-level erasure coding and physical-layer channel coding. It is known from previous work that some erasure coding is necessary even in the limit of large physical-layer codeword block-lengths if the physical-layer fading channel does not provide diversity that grows with block-length. However, is erasure coding still required in the limit of large block-lengths if the physical layer allows for diversity to grow with block-length? The theoretical answer turns out to be a resounding “no” in the case of Rayleigh fading that allows diversity to increase linearly with block-length.