Some properties of the minimal interpolation problemare investigated, from which a simple proof of the validity of theWelch-Berlekamp algorithm is presented. A new key equation is derived,which is closely related to the classical key equation of syndrome-decodingalgorithm and can be solved by the Welch–Berlekamp algorithm.

We study the limits of performance of Gallager codes(low-density parity-check (LDPC) codes) over binary linear intersymbolinterference (ISI) channels with additive white Gaussiannoise (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 expandon previous work by handling complications introduced by thechannel memory. We circumvent these problems by consideringnot just linear Gallager codes but also their cosets and by distinguishingbetween different types of message flow neighborhoodsdepending on the actual transmitted symbols. We compute thenoise tolerance threshold using a suitably developed densityevolution algorithm and verify, by simulation, that the thresholdsrepresent accurate predictions of the performance of the iterativesum-product algorithm for finite (but large) block lengths. Wealso demonstrate that for high rates, the thresholds are very closeto the theoretical limit of performance for Gallager codes overISI channels. If C denotes the capacity of a binary ISI channeland if Ci i d denotes the maximal achievable mutual informationrate when the channel inputs are independent and identicallydistributed (i.i.d.) binary random variables (Ci i d C), weprove that the maximum information rate achievable by thesum-product decoder of a Gallager (coset) code is upper-boundedby Ci i d . The last topic investigated is the performance limit ofthe decoder if the trellis portion of the sum-product algorithm isexecuted only once; this demonstrates the potential for tradingoff the computational requirements and the performance of thedecoder.

In this letter, we investigate the iterative detection/decoding algorithms for two-track partial response channels.We first describe the iterative algorithm as an iterative message-passing/processing algorithm over a high-level normal graphand then propose two trellis-based detection algorithms. Thenatural one is based on a joint trellis, which can be implementedfor low-order channels. For moderate-order channels, we proposea separated detection, which is based on two single-track trellises.Compared with the joint detection, the separated detection issimpler in most cases. Simulation results show that, for two-trackEPR4 channels with minor intertrack interferences, the separateddetection causes only marginal degradation in performance.

In this paper we design capacity-approaching codes for partial response channels. The codesare constructed as concatenations of inner trellis codes and outer low-density parity-check (LDPC)codes. Unlike previous constructions of trellis codes for partial response channels, we disregardany algebraic properties (e.g., the minimum distance or the run-length limit) in our design of thetrellis code. Our design is purely probabilistic in that we construct the inner trellis code to mimicthe transition probabilities of a Markov process that achieves a high (capacity-approaching) informationrate. Hence, we name it a matched information rate (MIR) design. We provide a set of5 design rules for constructions of capacity-approaching MIR inner trellis codes. We optimizethe outer LDPC code using density evolution tools specially modified to fit the superchannelconsisting of the inner MIR trellis code concatenated with the partial response channel. Usingthis strategy, we design degree sequences of irregular LDPC codes whose noise tolerance thresholdsare only fractions of a decibel away from the capacity. Examples of code constructions areshown for channels both with and without spectral nulls.

This is a semi-tutorial paper on trellis-based algorithms.We argue that most decoding/detection algorithms describedon trellises can be formulated as path-partitioning algorithms,with proper definitions of mappings from subsets of pathsto metrics of subsets. Thereby, the only two operations neededare path-concatenation and path-collection, which play the roles ofmultiplication and addition, respectively. Furthermore, we showthat the trellis structure permits the path-partitioning algorithmsto be formulated as forward-only algorithms (with structures resemblingthe Viterbi algorithm), thus eliminating the need forbackward computations regardless of what task needs to be performedon the trellis. While all of the actual decoding/detectionalgorithms presented here are rederivations of variations of previouslyknown methods, we believe that the exposition of the algorithmsin a unified manner as forward-only path-partitioningalgorithms is the most intuitive manner in which to generalize theViterbi algorithm. We also believe that this approach may in factinfluence the practical implementation of the algorithms as well asinfluence the construction of other forward-only algorithms (e.g.,byte-wise forward-only detection algorithms).