Optimized low-density parity-check codes for partial response channels

We optimize irregular low-density parity-check (LDPC) codes to closely approach the independent and uniformly distributed (i.u.d.) capacities of partial response channels. In our approach, we use the degree sequences optimization method for memoryless channels proposed by Richardson, Shokrollahi, and Urbanke and appropriately modify it for channels with memory. With this optimization algorithm we construct codes whose noise tolerance thresholds are within 0.15 dB of the i.u.d. channel capacities. Our simulation results show that irregular LDPC codes with block lengths 10/sup 6/ bits yield bit error rates 10/sup -6/ at signal-to-noise ratios 0.22 dB away from the channel capacities.     

Correlation-sensitive adaptive sequence detection

In high density magnetic recording, noise samples corresponding to adjacent signal samples are heavily correlated as a result of front-end equalizers, media noise, and signal nonlinearities combined with nonlinear filters to cancel them. This correlation significantly deteriorates the performance of detectors at high densities. In this paper, we propose a novel sequence detector that is correlation sensitive and adaptive to the nonstationary signal sample statistics. We derive the correlation-sensitive maximum likelihood detector. It can be used with any Viterbi-like receiver (e.g., partial response maximum likelihood, fixed delay tree search, multilevel decision feedback equalization) that relies on a tree/trellis structure. Our detector adjusts the metric computation to the noise correlation statistics. Because these statistics are nonstationary, we develop an adaptive algorithm that tracks the data correlation matrices. Simulation results are presented that show the applicability of the new correlation-sensitive adaptive sequence detector     

Path partitions and forward-only trellis algorithms

This is a semitutorial paper on trellis-based algorithms. We argue that most decoding/detection algorithms described on trellises can be formulated as path-partitioning algorithms, with proper definitions of mappings from subsets of paths to metrics of subsets. Thereby, the only two operations needed are path-concatenation and path-collection, which play the roles of multiplication and addition, respectively. Furthermore, we show that the trellis structure permits the path-partitioning algorithms to be formulated as forward-only algorithms (with structures resembling the Viterbi (1967) algorithm), thus eliminating the need for backward computations regardless of what task needs to be performed on the trellis. While all of the actual decoding/detection algorithms presented here are rederivations of variations of previously known methods, we believe that the exposition of the algorithms in a unified manner as forward-only path-partitioning algorithms is the most intuitive manner in which to generalize the Viterbi algorithm. We also believe that this approach may, in fact, influence the practical implementation of the algorithms as well as influence the construction of other forward-only algorithms (e.g., byte-wise forward-only detection algorithms).     

Binary intersymbol interference channels: Gallager codes, density evolution, and code performance bounds

We study the limits of performance of Gallager codes (low-density parity-check (LDPC) codes) over binary linear intersymbol interference (ISI) channels with additive white Gaussian noise (AWGN). Using the graph representations of the channel, the code, and the sum-product message-passing detector/decoder, we prove two error concentration theorems. Our proofs expand on previous work by handling complications introduced by the channel memory. We circumvent these problems by considering not just linear Gallager codes but also their cosets and by distinguishing between different types of message flow neighborhoods depending on the actual transmitted symbols. We compute the noise tolerance threshold using a suitably developed density evolution algorithm and verify, by simulation, that the thresholds represent accurate predictions of the performance of the iterative sum-product algorithm for finite (but large) block lengths. We also demonstrate that for high rates, the thresholds are very close to the theoretical limit of performance for Gallager codes over ISI channels. If C denotes the capacity of a binary ISI channel and if C/sub i.i.d./ denotes the maximal achievable mutual information rate when the channel inputs are independent and identically distributed (i.i.d.) binary random variables (C/sub i.i.d.//spl les/C), we prove that the maximum information rate achievable by the sum-product decoder of a Gallager (coset) code is upper-bounded by C/sub i.i.d./. The last topic investigated is the performance limit of the decoder if the trellis portion of the sum-product algorithm is executed only once; this demonstrates the potential for trading off the computational requirements and the performance of the decoder.     

Error exponents for finite-hypothesis channel identification

We consider the problem of designing optimal probing signals for finite-hypothesis testing. Equivalently, we cast the problem as the design of optimal channel input sequences for identifying a discrete channel under observation from a finite set of known channels. The optimality criterion that we employ is the exponent of the Bayesian probability of error. In our study, we consider a feedforward scenario where there is no feedback from the channel output to the signal selector at the channel input and a feedback scenario where the past channel outputs are revealed to the signal selector. In the feedforward scenario, only the type of the input sequence matters and our main result is an expression for the error exponent in terms of the limiting distribution of the input sequence. In the feedback case, we show that when discriminating between two channels, the optimal scheme in the first scenario is simultaneously the optimal time-invariant Markov feedback policy of any order.     

Guest Editorial Data Communication Techniques for Storage Channels and Networks

Since the inception of direct access magnetic storage about 55 years ago, data storage has both benefited from and given rise to extraordinary progress in many technological areas, including materials science, tribology, servo control and actuation, and signal processing and coding. The number of data bits that can be stored in a unit area ? the areal recording density ? has increased by eight orders of magnitude for harddisk magnetic storage, with compound annual growth rates at times exceeding 100%. Moreover, the cost of this form of storage has dropped by about seven orders of magnitude. For this reason, data storage has been one of the main enablers of the information technology revolution. According to a recent estimation by the technology analysis firm IDC, the amount of data created worldwide has now started to exceed the capacity of storage that is physically available. This so-called digital universe is forecasted to grow explosively and reach more than 10²¹ bytes (1 ZB) in 2011.     

Simulation-Based Computation of Information Rates for Channels With Memory

The information rate of finite-state source/channel models can be accurately estimated by sampling both a long channel input sequence and the corresponding channel output sequence, followed by a forward sum-product recursion on the joint source/channel trellis. This method is extended to compute upper and lower bounds on the information rate of very general channels with memory by means of finite-state approximations. Further upper and lower bounds can be computed by reduced-state methods     

On the Performance of Short Forward Error-Correcting Codes

This letter investigates the performance of short forward error-correcting (FEC) codes. Reed-Solomon (RS) codes and concatenated zigzag codes are chosen as representatives of classical algebraic codes and modern simple iteratively decodable codes, respectively. Additionally, random binary linear codes are used as a baseline reference. Our main results (demonstrated by simulations and ensemble distance spectrum analysis) are as follows: 1) Short RS codes are as good as random binary linear codes; 2) Carefully designed short low-density parity-check (LDPC) codes are almost as good as random binary linear codes; 3) Low complexity belief propagation decoders incur considerable performance loss at short coding lengths. Thus, future work could focus on developing low-complexity (near) optimal decoders for RS codes and/or LDPC codes.     

Statistical study of zig-zag transition boundaries in longitudinaldigital magnetic recording

In this paper, we study the statistics of zig-zag transition walls in digital magnetic recording and their relationship to transition noise defining quantities. We provide analytic results that link the statistics of zig-zag transitions to media/recording parameters. The basis of our study is the triangle zig-zag transition (TZ-ZT) model due to its well-defined triangle zig-zag shape and its cross-track stability. The results we derive here, however, are of a general nature, and given the right interpretation, apply to other zig-zag models as well, as we show in the paper. We also provide an interpretation of the cross-track correlation width, linking this quantity to the statistics of magnetized clusters in thin-film magnetic media. The paper concludes by showing how these results can be used in media noise modeling