Low-density parity check (LDPC) codes have experienced tremendous popularity due to their capacity-achieving performance. In this dissertation, several different aspects of LDPC coding and its applications to magnetic storage are investigated. One of the most significant issues that impedes the use of LDPC codes in many systems is the error-rate floor phenomenon associated with their iterative decoders. By delineating the fundamental principles, we extend to partial response channels algorithms for predicting the error rate performance in the floor region for the binary-input AWGN channel. We develop three classes of decoding algorithms for mitigating the error floor by directly tackling the cause of the problem: trapping sets. In our experiments, these algorithms provide multiple orders of improvement over conventional decoders at the cost of various implementation complexity increases.Product codes are widely used in magnetic recording systems where errors are both isolated and bursty. A dual-mode decoding technique for Reed-Solomon-code-based product codes is proposed, where the second decoding mode involves maximum-likelihood erasure decoding of the binary images of the Reed-Solomon codewords. By exploring a tape storage application, we demonstrate that this dual-mode decoding system dramatically improves the performance of product codes. Moreover, the complexity added by the second decoding mode is manageable. We also show the performance of this technique on a product code which has an LDPC code in the columns.Run-length-limited (RLL) codes are ubiquitous in today's disk drives. Using RLL codes has enabled drive designers to pack data very efficiently onto the platter surface by ensuring stable symbol-timing recovery. We consider a concatenation system design with an LDPC code and an RLL code as components to simultaneously achieve desirable features such as: soft information availability to the LDPC decoder, the preservation of the LDPC code's structure, and the capability of correcting long erasure bursts.We analyze the performance of LDPC-coded magnetic recording channel in the presence of media noise. We employ advanced signal processing for the pattern-dependent-noise-predictive channel detectors, and demonstrate that a gain of over 1 dB or a linear density gain of about 8% relative to a comparable Reed-Solomon is attainable by using an LDPC code.

The Low-Density Parity-Check (LDPC) codes, which were invented by Gallager back in 1960s, have attracted considerable attentions recently. Compared with other error correction codes, LDPC codes are well suited for wireless, optical, and magnetic recording systems due to their near- Shannon-limit error-correcting capacity, high intrinsic parallelism and high-throughput potentials. With these remarkable characteristics, LDPC codes have been adopted in several recent communication standards such as 802.11n (Wi-Fi), 802.16e (WiMax), 802.15.3c (WPAN), DVB-S2 and CMMB. This dissertation is devoted to exploring efficient VLSI architectures for high-performance LDPC decoders and LDPC-like detectors in sparse inter-symbol interference (ISI) channels. The performance of an LDPC decoder is mainly evaluated by area efficiency, error-correcting capability, throughput and rate flexibility. With this work we investigate tradeoffs between the four performance aspects and develop several decoder architectures to improve one or several performance aspects while maintaining acceptable values for other aspects. Firstly, we present a high-throughput decoder design for the Quasi-Cyclic (QC) LDPC codes. Two new techniques are proposed for the first time, including parallel layered decoding architecture (PLDA) and critical path splitting. Parallel layered decoding architecture enables parallel processing for all layers by establishing dedicated message passing paths among them. The decoder avoids crossbar-based large interconnect network. Critical path splitting technique is based on articulate adjustment of the starting point of each layer to maximize the time intervals between adjacent layers, such that the critical path delay can be split into pipeline stages. Furthermore, min-sum and loosely coupled algorithms are employed for area efficiency. As a case study, a rate-1/2 2304-bit irregular LDPC decoder is implemented using ASIC design in 90 nm CMOS process. The decoder can achieve an input throughput of 1.1 Gbps, that is, 3 or 4 times improvement over state-of-art LDPC decoders, while maintaining a comparable chip size of 2.9 mm^2. Secondly, we present a high-throughput decoder architecture for rate-compatible (RC) LDPC codes which supports arbitrary code rates between the rate of mother code and 1. While the original PLDA is lack of rate flexibility, the problem is solved gracefully by incorporating the puncturing scheme. Simulation results show that our selected puncturing scheme only introduces the BER performance degradation of less than 0.2dB, compared with the dedicated codes for different rates specified in the IEEE 802.16e (WiMax) standard. Subsequently, PLDA is employed for high throughput decoder design. As a case study, a RC- LDPC decoder based on the rate-1/2 WiMax LDPC code is implemented in CMOS 90 nm process. The decoder can achieve an input throughput of 975 Mbps and supports any rate between 1/2 and 1. Thirdly, we develop a low-complexity VLSI architecture and implementation for LDPC decoder used in China Multimedia Mobile Broadcasting (CMMB) systems. An area-efficient layered decoding architecture based on min-sum algorithm is incorporated in the design. A novel split-memory architecture is developed to efficiently handle the weight-2 submatrices that are rarely seen in conventional LDPC decoders. In addition, the check-node processing unit is highly optimized to minimize complexity and computing latency while facilitating a reconfigurable decoding core. Finally, we propose an LDPC-decoder-like channel detector for sparse ISI channels using belief propagation (BP). The BP-based detection computationally depends on the number of nonzero interferers only and are thus more suited for sparse ISI channels which are characterized by long delay but a small fraction of nonzero interferers. Layered decoding algorithm, which is popular in LDPC decoding, is also adopted in this paper. Simulation results show that the layered decoding doubles the convergence speed of the iterative belief propagation process. Exploring the special structure of the connections between the check nodes and the variable nodes on the factor graph, we propose an effective detector architecture for generic sparse ISI channels to facilitate the practical application of the proposed detection algorithm. The proposed architecture is also reconfigurable in order to switch flexible connections on the factor graph in the time-varying ISI channels.

Recent advancements in iterative processing have allowed communication systems to perform close to capacity limits withmanageable complexity.For manychannels such as the AWGN and flat fading channels, codes that perform only a fraction of a dB from the capacity have been designed in the literature. In this dissertation, we will focus on the design and analysis of near-capacity achieving codes for another important class of channels, namely inter-symbol interference (ISI)channels. We propose various coding schemes such as low-density parity-check (LDPC) codes, parallel and serial concatenations for ISI channels when there is no spectral shaping used at the transmitter. The design and analysis techniques use the idea of extrinsic information transfer (EXIT) function matching and provide insights into the performance of different codes and receiver structures. We then present a coding scheme which is the concatenation of an LDPC code with a spectral shaping block code designed to be matched to the channel??s spectrum. We will discuss how to design the shaping code and the outer LDPC code. We will show that spectral shaping matched codes can be used for the parallel concatenation to achieve near capacity performance. We will also discuss the capacity of multiple antenna ISI channels. We study the effects of transmitter and receiver diversities and noisy channel state information on channel capacity.

In this thesis, we present an FPGA implementation of parallel-node low-density-parity-check convolutional-code (PN-LDPC-CC) encoder and decoder. A 2.4 Gbit/s rate-1/2 (3, 6) PN-LDPC-CC encoder and decoder were implemented on an Altera development and education board (DE4). Detailed power measurements of the FPGA board for various configurations of the design have been conducted to characterize the power consumption of the decoder module. For an Eb/N0 of 5 dB, the decoder with 9 processor cores (pipelined decoder iteration stages) has a bit-error-rate performance of 10E-10 and achieves an energy-per-coded-bit of 1.683 nJ based on raw power measurement results. The increase in Eb/N0 can effectively reduce the decoder power and energy-per-coded-bit for configurations with 5 or more processor cores for Eb/N0 < 5 dB. The incremental decoder power cost and incremental energy-per-coded-bit also hold a linearly decreasing trend for each additional processor core. Additional experiments are performed to account for the effect of the efficiency of the DC/DC converter circuitry on the raw power measurement data. Further experiments have also been conducted to quantify the effect of clipping thresholds, bit width for each processor core on bit-error-rate (BER) performance, power consumption, and logic utilization of the decoder. A “6Core" decoder with growing bit-width log-likelihood ratios (LLRs) has been found to have a BER performance near that of a “6Core" 6-bit decoder while consuming similar power, and logic utilization to that of a 5-bit “6Core" decoder.

The VLSI implementation complexity of a low density parity check (LDPC) decoder is largely influenced by the interconnect and the storage requirements. This dissertation presents the decoder architectures for regular and irregular LDPC codes that provide substantial gains over existing academic and commercial implementations. Several structured properties of LDPC codes and decoding algorithms are observed and are used to construct hardware implementation with reduced processing complexity. The proposed architectures utilize an on-the-fly computation paradigm which permits scheduling of the computations in a way that the memory requirements and re-computations are reduced. Using this paradigm, the run-time configurable and multi-rate VLSI architectures for the rate compatible array LDPC codes and irregular block LDPC codes are designed. Rate compatible array codes are considered for DSL applications. Irregular block LDPC codes are proposed for IEEE 802.16e, IEEE 802.11n, and IEEE 802.20. When compared with a recent implementation of an 802.11n LDPC decoder, the proposed decoder reduces the logic complexity by 6.45x and memory complexity by 2x for a given data throughput. When compared to the latest reported multi-rate decoders, this decoder design has an area efficiency of around 5.5x and energy efficiency of 2.6x for a given data throughput. The numbers are normalized for a 180nm CMOS process. Properly designed array codes have low error floors and meet the requirements of magnetic channel and other applications which need several Gbps of data throughput. A high throughput and fixed code architecture for array LDPC codes has been designed. No modification to the code is performed as this can result in high error floors. This parallel decoder architecture has no routing congestion and is scalable for longer block lengths. When compared to the latest fixed code parallel decoders in the literature, this design has an area efficiency of around 36x and an energy efficiency of 3x for a given data throughput. Again, the numbers are normalized for a 180nm CMOS process. In summary, the design and analysis details of the proposed architectures are described in this dissertation. The results from the extensive simulation and VHDL verification on FPGA and ASIC design platforms are also presented.

This dissertation deals with the design of bandwidth-efficient coding schemes with Low-Density Parity-Check (LDPC) for reliable wireless communications. Code design for wireless channels roughly falls into three categories: (1) when channel state information (CSI) is known only to the receiver (2) more practical case of partial CSI at the receiver when the channel has to be estimated (3) when CSI is known to the receiver as well as the transmitter. We consider coding schemes for all the above categories. For the first scenario, we describe a bandwidth efficient scheme which uses highorder constellations such as QAM over both AWGN as well as fading channels. We propose a simple design with LDPC codes which combines the good properties of Multi-level Coding (MLC) and bit-interleaved coded-modulation (BICM) schemes. Through simulations, we show that the proposed scheme performs better than MLC for short-medium lengths on AWGN and block-fading channels. For the first case, we also characterize the rate-diversity tradeoff of MIMO-OFDM and SISO-OFDM systems. We design optimal coding schemes which achieve this tradeoff when transmission is from a constrained constellation. Through simulations, we show that with a sub-optimal iterative decoder, the performance of this coding scheme is very close to the optimal limit for MIMO (flat quasi-static fading), MIMO-OFDM and SISO OFDM systems. For the second case, we design non-systematic Irregular Repeat Accumulate (IRA) codes, which are a special class of LDPC codes, for Inter-Symbol Interference (ISI) fading channels when CSI is estimated at the receiver. We use Orthogonal Frequency Division Multiplexing (OFDM) to convert the ISI fading channel into parallel flat fading subchannels. We use a simple receiver structure that performs iterative channel estimation and decoding and use non-systematic IRA codes that are optimized for this receiver. This combination is shown to perform very close to a receiver with perfect CSI and is also shown to be robust to change in the number of channel taps and Doppler. For the third case, we look at bandwidth efficient schemes for fading channels that perform close to capacity when the channel state information is known at the transmitter as well as the receiver. Schemes that achieve capacity with a Gaussian codebook for the above system are already known but not for constrained constellations. We derive the near-optimum scheme to achieve capacity with constrained constellations and then propose coding schemes which perform close to capacity. Through linear transformations, a MIMO system can be converted into non-interfering parallel subchannels and we further extend the proposed coding schemes to the MIMO case too.

This dissertation is mainly focused on the analysis, design and optimization of Low-density parity-check (LDPC) codes over channels with large alphabet sets and the applications on compressed sensing (CS) and flash memories. Compared to belief-propagation (BP) decoding, verification-based (VB) decoding has significantly lower complexity and near optimal performance when the channel alphabet set is large. We analyze the verification-based decoding of LDPC codes over the q-ary symmetric channel (q-SC) and propose the list-message-passing (LMP) decoding which off ers a good tradeoff between complexity and decoding threshold. We prove that LDPC codes with LMP decoding achieve the capacity of the q-SC when q and the block length go to infinity. CS is a newly emerging area which is closely related to coding theory and information theory. CS deals with the sparse signal recovery problem with small number of linear measurements. One big challenge in CS literature is to reduce the number of measurements required to reconstruct the sparse signal. In this dissertation, we show that LDPC codes with verification-based decoding can be applied to CS system with surprisingly good performance and low complexity. We also discuss modulation codes and error correcting codes (ECC’s) design for flash memories. We design asymptotically optimal modulation codes and discuss their improvement by using the idea from load-balancing theory. We also design LDPC codes over integer rings and fields with large alphabet sets for flash memories.

Consider a piece of information printed on paper and scanned in the form of an image. The printer, scanner, and the paper naturally form a communication channel, where the printer is equivalent to the sender, scanner is equivalent to the receiver, and the paper is the medium of communication. The channel created in this way is quite complicated and it maps 2D input patterns to 2D output patterns. Inter-symbol interference is introduced in the channel as a result of printing and scanning. During printing, ink from the neighboring pixels can spread out. The scanning process can introduce interference in the data obtained because of the finite size of each pixel and the fact that the scanner doesn't have infinite resolution. Other degradations in the process can be modeled as noise in the system. The scanner may also introduce some spherical aberration due to the lensing effect. Finally, when the image is scanned, it might not be aligned exactly below the scanner, which may lead to rotation and translation of the image. In this work, we present a coding scheme for the channel, and possible solutions for a few of the distortions stated above. Our solution consists of the structure, encoding and decoding scheme for the code, a scheme to undo the rotational distortion, and an equalization method. The motivation behind this is the question: What is the information capacity of paper. The purpose is to find out how much data can be printed out and retrieved successfully. Of course, this question has potential practical impact on the design of 2D bar codes, which is why encodability is a desired feature. There are also a number of other useful applications however. We could successfully decode 41.435 kB of data printed on a paper of size 6.7 X 6.7 inches using a Xerox Phasor 550 printer and a Canon CanoScan LiDE200 scanner. As described in the last chapter, the capacity of the paper using this channel is clearly greater than 0.9230 kB per square inch. The main contribution of the thesis lies in constructing the entire system and testing its performance. Since the focus is on encodable and practically implementable schemes, the proposed encoding method is compared with another well known and easily encodable code, namely the repeat accumulate code.

Recent advancements in iterative processing have allowed communication systems to perform close to capacity limits withmanageable complexity.For manychannels such as the AWGN and &#64258;at fading channels, codes that perform only a fraction of a dB from the capacity have been designed in the literature. In this dissertation, we will focus on the design and analysis of near-capacity achieving codes for another important class of channels, namely inter-symbol interference (ISI)channels. We propose various coding schemes such as low-density parity-check (LDPC) codes, parallel and serial concatenations for ISI channels when there is no spectral shaping used at the transmitter. The design and analysis techniques use the idea of extrinsic information transfer (EXIT) function matching and provide insights into the performance of di&#64256;erent codes and receiver structures. We then present a coding scheme which is the concatenation of an LDPC code with a spectral shaping block code designed to be matched to the channel??s spectrum. We will discuss how to design the shaping code and the outer LDPC code. We will show that spectral shaping matched codes can be used for the parallel concatenation to achieve near capacity performance. We will also discuss the capacity of multiple antenna ISI channels. We study the effects of transmitter and receiver diversities and noisy channel state information on channel capacity.

A family of low-density lattice codes (LDLC) is studied based on Construction-A for lattices. The family of Construction-A codes is already known to contain a large capacity-achieving subset. Parallels are drawn between coset non-binary low-density parity-check (LDPC) codes and nested low-density Construction-A lattices codes. Most of the related research in LDPC domain assumes optimal power allocation to encoded codeword. The source coding problem of mapping message to power optimal codeword for any LDPC code is in general, NP-hard. In this thesis, we present a novel method for encoding and decoding lattice based on non-binary LDPC codes using message-passing algorithms. / text