For applications in concatenated coding for optical communications systems, we examine soft-demapping of short spherical codes constructed as constant-energy shells of the Cartesian power of pulse amplitude modulation constellations. These are unions of permutation codes having the same average power. We construct a list decoder for permutation codes by adapting Murty’s algorithm, which is then used to determine mutual information curves for these permutation codes. In the process, we discover a straightforward expression for determining the likelihood of large subcodes of permutation codes. We refer to these subcodes, obtained by all possible sign flips of a given permutation codeword, as orbits. We introduce a simple process, which we call orbit demapping with frozen symbols, that allows us to extract soft information from noisy permutation codewords. In a sample communication system with probabilistic amplitude shaping protected by a standard low-density parity-check code that employs short permutation codes, we demonstrate that orbit demapping with frozen symbols provides a gain of about 0.3 dB in signal-to-noise ratio compared to the traditional symbol-by-symbol demapping. By using spherical codes composed of unions of permutation codes, we can increase the input entropy compared to using permutation codes alone. In one scheme, we consider a union of a small number of permutation codes. In this case, orbit demapping with frozen symbols provides about 0.2 dB gain compared to the traditional method. In another scheme, we use all possible permutations to form a spherical code that exhibits a computationally feasible trellis representation. The soft information obtained using the BCJR algorithm outperforms the traditional symbol-by-symbol method by 0.1 dB. Overall, using the spherical codes containing all possible permutation codes of the same average power and the BCJR algorithm, a gain of 0.5 dB is observed compared with the case of using one permutation code with the symbol-by-symbol demapping. Comparison of the achievable information rates of bit-metric decoding verifies the observed gains.

Automorphism-ensemble decoding is applied to the Plotkin constituents of Reed-Muller codes, resulting in a new soft-decision decoding algorithm with state-of-the-art performance versus complexity trade-offs.

We generalize staircase codes and tiled diagonal zipper codes, preserving their key properties while allowing each coded symbol to be protected by arbitrarily many component codewords rather than only two. This generalization which we term “higher-order staircase codes” arises from the marriage of two distinct combinatorial objects: difference triangle sets and finite-geometric nets, which have typically been applied separately to code design. We demonstrate one possible realization of these codes, obtaining powerful, high-rate, low-error-floor, and low-complexity coding schemes based on simple iterative syndrome-domain decoding of coupled Hamming component codes. We anticipate that the proposed codes could improve performance–complexity–latency tradeoffs in high-throughput communications applications, most notably fiber-optic, in which classical staircase codes and zipper codes have been applied. We consider the construction of difference triangle sets having minimum scope and sum-of-lengths, which lead to memory-optimal realizations of higher-order staircase codes. These results also enable memory reductions for early families of convolutional codes constructed from difference triangle sets.

This paper considers data secrecy in distributed storage systems (DSSs) using maximally recoverable locally repairable codes (MR-LRCs). Conventional MR-LRCs are in general not secure against eavesdroppers who can observe the transmitted data during a global repair operation. This work enables nonzero secrecy dimension of DSSs encoded by MR-LRCs through a new repair framework. The key idea is to associate each local group with a central processing unit (CPU), which aggregates and transmits the contribution from the intact nodes of their group to the CPU of a group needing a global repair. The aggregation is enabled by so-called local polynomials that can be generated independently in each group. Two different schemes - direct repair and forwarded repair - are considered, and their secrecy dimension using MR-LRCs is derived. Positive secrecy dimension is enabled for several parameter regimes.

We introduce a formal framework to study the multiple unicast problem for a coded network in which the network code is linear over a finite field and fixed. We show that the problem corresponds to an interference alignment problem over a finite field. In this context, we establish an outer bound for the achievable rate region and provide examples of networks where the bound is sharp. We finally give evidence of the crucial role played by the field characteristic in the problem.

We present two strategies to reduce the complexity of the alternating direction method of multipliers when applied to linear programming (ADMM-LP) decoding of low-density parity-check codes. First, to address the high complexity of computing a projection onto the parity polytope, the complexity bottleneck of ADMM-LP decoding, we propose the sparse affine projection algorithm (SAPA). SAPA projects onto the affine hull of χ ≤dnearby local codewords where the check degree isdand where χ can be significantly smaller thand. Unlike exact projection, SAPA does not require a water-filling process, and thus can be implemented with lower per-iteration complexity. Second, to reduce the number of effective iterations needed for ADMM-LP decoding, we propose a randomized layered scheduling framework. Rather than updating checks in round-robin fashion in each iteration, more “problematic” checks have a higher probability of being updated. The probability mass function that governs the selection of which checks to update is based upon the location of replica vectors inside (or on) the parity polytope. The resultant decoder converges significantly faster under this randomized scheduling than under round-robin scheduling. This makes it well suited for use in applications that limit the number of iterations.

Using a generating function approach, a computationally tractable expression is derived to predict the frame error rate arising at the output of the binary symmetric channel when a number of outer Reed–Solomon codes are concatenated with a number of inner Bose–Ray-Chaudhuri–Hocquenghem codes, thereby obviating the need for time-consuming Monte Carlo simulations. Measuring (a) code performance via the gap to the Shannon limit, (b) decoding complexity via an estimate of the number of operations per decoded bit, and (c) decoding latency by the overall frame length, a code search is performed to determine the Pareto frontier for performance-complexity-latency trade-offs.

We present a randomized schedule for alternating direction method of multipliers with linear programming (ADMM-LP) decoding of low-density parity check (LDPC) codes. The randomized schedule is based on horizontal layered decoding, where nodes are updated sequentially. Unlike existing layered decoding frameworks where all check nodes are updated exactly once per iteration, we propose a randomized schedule where more problematic nodes are updated more frequently. To do so, we sample from a probability mass function (PMF) over all check nodes and the check with sampled index is updated. The probability of each check to be updated is determined by its state. The PMF is constructed based on the distribution of replica (check) vectors inside or on the parity polytope. The randomized decoder usually converges faster than both standard and horizontal layered decoders, making it suitable for limited-iteration decoding in high-throughput applications.

Just as rank-metric or Gabidulin codes may be used to construct rate–diversity tradeoff optimal space–time codes, a recently introduced generalization for the sum-rank metric—linearized Reed–Solomon codes—accomplishes the same in the case of multiple fading blocks. In this paper, we provide the first explicit construction of minimal delay rate–diversity optimal multiblock space–time codes as an application of linearized Reed–Solomon codes. We also provide sequential decoders for these codes and, more generally, space–time codes constructed from finite field codes. Simulation results show that the proposed codes can outperform full diversity codes based on cyclic division algebras at low SNRs as well as utilize significantly smaller constellations.

The nondispersive per-sample channel model for the optical fiber channel is considered. Under certain smoothness assumptions, the problem of finding the minimum amount of noise energy that can render two different input points indistinguishable is formulated. This minimum noise energy is then taken as a measure of distance between the points in the input alphabet. Using the machinery of optimal control theory, necessary conditions that describe the minimum-energy noise trajectories are stated as a system of nonlinear differential equations. It is shown how to find the distance between two input points by solving this system of differential equations. The problem of designing signal constellations with the largest minimum distance subject to a peak power constraint is formulated as a clique-finding problem. As an example, a 16-point constellation is designed and compared with conventional quadrature amplitude modulation. A computationally efficient approximation for the proposed distance measure is provided. It is shown how to use this approximation to design large constellations with large minimum distances. Based on the control-theoretic viewpoint of this paper, a new decoding scheme for such nonlinear channels is proposed.

Resistive memories store information in a crossbar arrangement of two-terminal devices that can be programmed to patterns of high or low resistance. While extremely compact, this technology suffers from the “sneak-path” problem: certain information patterns cannot be recovered, as multiple low resistances in parallel make a high resistance indistinguishable from a low resistance. In this paper, a multi-layer device is considered, and the number of bits it can store is derived exactly and asymptotic bounds are developed. The information density of a series of isolated arrays with extreme aspect ratios is derived in the single- and multi-layer cases with and without peripheral selection circuitry. This density is shown to be non-zero in the limit, unlike that of the arrays with moderate aspect ratios previously considered. A simple encoding scheme that achieves capacity asymptotically is presented.

Just as rank-metric or Gabidulin codes may be used to construct rate-diversity tradeoff optimal space-time codes, a recently introduced generalization for the sum-rank metric, linearized Reed-Solomon codes, accomplishes the same in the case of multiple fading blocks. We provide the first explicit construction of minimal-delay rate-diversity optimal multiblock space-time codes as an application of linearized Reed-Solomon codes. We then demonstrate in simulation an example of a 2-block 2-by-2 code which, with a small performance penalty-less than 1 dB at a codeword error rate of 1e-4-matches the bit rate of a full diversity alternative while using a much smaller transmitted constellation. A stack decoder for this code is then suggested.

Capacity bounds for waveform channels under square-law detection of time-limited complex-valued signals are derived. The upper bound is the capacity of the channel under (complex-valued) coherent detection. The lower bound is one bit less, per dimension, than the upper bound.

The nondispersive per-sample channel model for the optical fiber channel is considered. Under some smoothness assumptions, the problem of finding the minimum amount of noise energy that can render two different input points indistinguishable is formulated. The necessary conditions for the noise trajectory that has the minimum energy are described as a system of nonlinear differential equations. It is suggested that this model can be generalized to consider dispersion and to design new communication schemes for fiber-optic communication systems.

The maximum likelihood detection rule for a four-dimensional direct-detection optical front-end is derived. The four dimensions are two intensities and two differential phases. Three different signal processing algorithms, composed of symbol-by-symbol, sequence, and successive detection, are discussed. To remedy dealing with special functions in the detection rules, an approximation for high signal-to-noise ratios (SNRs) is provided. Simulation results show that, despite the simpler structure of the successive algorithm, the resulting performance loss, in comparison with the other two algorithms, is negligible. For example, for an 8-ring/8-ary phase constellation, the complexity of detection reduces by a factor of 8, while the performance, in terms of the symbol error rate, degrades by 0.5 dB. It is shown that the high-SNR approximation is very accurate, even at low SNRs. The achievable rates for different constellations are computed and compared by the Monte Carlo method. For example, for a 4-ring/8-ary phase constellation, the achievable rate is 10 bits per channel use at an SNR of 25 dB, while by using an 8-ring/8-ary phase constellation and an error correcting code of rate 5/6, this rate is achieved at an SNR of 20 dB.

Using the Thompson circuit complexity model, it is shown that fully parallel encoding and decoding schemes with asymptotic block error probability that scales as O( f (n)) have energy that scales as Ω(n- ln f (n)1/2). In addition, it is shown that the number of clock cycles [T(n)] required for any encoding or decoding scheme that reaches this bound must scale as T(n) ≥ - ln f (n)1/2. Similar scaling results are extended to serialized computation. A similar approach is extended to three dimensions by generalizing the Grover information-friction energy model. Within this model, it is shown that encoding and decoding schemes with probability of block error Pe(n) consume at least Ω(n(- ln Pe(n))(1/3)) energy.

It is shown that all polar encoding schemes using a standard encoding matrix with rate R>1/2 and block length N have energy within the Thompson circuit model that scales at least as E ≥ Ω (N3/2). This lower bound is achievable up to polylogarithmic factors using a mesh network topology defined by Thompson and the encoding algorithm defined by Arıkan. A general class of circuits that compute successive cancellation decoding adapted from Arıkan's butterfly network algorithm is defined. It is shown that such decoders implemented on a rectangle grid for codes of rate R > 2/3 must take energy E ≥ Ω (N3/2). The energy of a Mead memory architecture and a mesh network memory architecture are analyzed and it is shown that a processor architecture using these memory elements can reach the decoding energy lower bounds to within a polylogarithmic factor. Similar scaling rules are derived for polar list decoders and belief propagation decoders. Capacity approaching sequences of energy optimal polar encoders and decoders, as a function of reciprocal gap to capacity χ = (1- R/C)-1(where R is rate C and is channel capacity), have energy that scales as Ω (χ5.3685) ≤ E ≤ O (χ7.071log4(χ)). Known results in constant depth circuit complexity theory imply that no polynomial size classical circuits can compute polar encoding, but this is possible in quantum circuits that include a constant depth quantum fan-out gate.

Multishot network coding is considered in a worst-case adversarial setting in which an omniscient adversary with unbounded computational resources may inject erroneous packets in up to t links, erase up to p packets, and wire-tap up to μ links, all throughout I shots of a linearly-coded network. Assuming no knowledge of the underlying linear network code (in particular, the network topology and underlying linear code may be random and change with time), a coding scheme achieving zero-error communication and perfect secrecy is obtained based on linearized Reed-Solomon codes. The scheme achieves the maximum possible secret message size of ℓn' -2t -p -μ packets for coherent communication, where n' is the number of outgoing links at the source, for any packet length m ≥ n' (largest possible range). By lifting this construction, coding schemes for non-coherent communication are obtained with information rates close to optimal for practical instances. The required field size is qm, where q > ℓ, thus qm≈ ℓn', which is always smaller than that of a Gabidulin code tailored for I shots, which would be at least 2ℓn'. A Welch-Berlekamp sum-rank decoding algorithm for linearized Reed-Solomon codes is provided, having quadratic complexity in the total length n = ℓn', and which can be adapted to handle not only errors but also erasures, wiretap observations and non-coherent communication. Combined with the obtained field size, the given decoding complexity is of O(n'4ℓ2log(ℓ)2) operations in F2, whereas the most efficient known decoding algorithm for a Gabidulin code has a complexity of O(n'3.69ℓ3.69log(ℓ)2) operations in F2, assuming a multiplication in a finite field F costs about log(|F|)2operations in F2.

Locally repairable codes (LRCs) are considered with equal or unequal localities, local distances, and local field sizes. An explicit two-layer architecture with a sum-rank outer code is obtained, having disjoint local groups and achieving maximal recoverability (MR) for all families of local linear codes (MDS or not) simultaneously, up to a specified maximum locality$r $. Furthermore, the local linear codes (thus the localities, local distances, and local fields) can be efficiently and dynamically modified without global recoding or changes in architecture or outer code, while preserving the MR property, easily adapting to new configurations in storage or new hot and cold data. In addition, local groups and file components can be added, removed or updated without global recoding. The construction requires global fields of size roughly$g^{r} $, for$g $local groups and maximum or specified locality$r $. For equal localities, these global fields are smaller than those of previous MR-LRCs when$r \leq h $(global parities). For unequal localities, they provide an exponential field size reduction on all previous best known MR-LRCs. For bounded localities and a large number of local groups, the global erasure-correction complexity of the given construction is comparable to that of Tamo–Barg codes or Reed–Solomon codes with local replication, while local repair is as efficient as for the Cartesian product of the local codes. Reed–Solomon codes with local replication and Cartesian products are recovered from the given construction when$r=1 $and$h = 0 $, respectively. The given construction can also be adapted to provide hierarchical MR-LRCs for all types of hierarchies and parameters. Finally, subextension subcodes and sum-rank alternant codes are introduced to obtain further exponential field size reductions, at the expense of lower information rates.

A combinatorial framework for adversarial network coding is presented. Channels are described by specifying the possible actions that one or more (possibly coordinated) adversaries may take. Upper bounds on three notions of capacity-the one-shot capacity, the zero-error capacity, and the compound zero-error capacity-are obtained for point-to-point channels, and generalized to corresponding capacity regions appropriate for multi-source networks. A key result of this paper is a general method by which bounds on these capacities in point-to-point channels may be ported to networks. This technique is illustrated in detail for Hamming-type channels with multiple adversaries operating on specific coordinates, which correspond, in the context of networks, to multiple adversaries acting on specific network edges. Capacity-achieving coding schemes are described for some of the considered adversarial models.

The recipients of the 2018 IEEE Information Theory Society Paper Award are Mansoor I. Yousefi and Frank R. Kschischang for the three-part paper “Information Transmission Using the Nonlinear Fourier Transform, I, II, III” which appeared in the IEEE Transactions on Information Theory, vol. 60, no. 7, pp. 4312–4328 (Part I), pp. 4329–4345 (Part II), and pp. 4346–4369 (Part III), July 2014.

This paper proposes a “quasi-synchronous” design approach for signal processing circuits, in which timing violations are permitted, but without the need for a hardware compensation mechanism. The case of a low-density parity-check (LDPC) decoder is studied, and a method for accurately modeling the effect of timing violations at a high level of abstraction is presented. The error-correction performance of code ensembles is then evaluated using density evolution, while taking into account the effect of timing faults. Following this, several quasi-synchronous LDPC decoder circuits based on the offset min-sum algorithm are optimized, providing a 23%-40% reduction in energy consumption or energy-delay product, while achieving the same performance and occupying the same area as conventional synchronous circuits.

We analyze a class of high performance, low decoding-data-flow error-correcting codes suitable for high bit-rate optical-fiber communication systems. A spatially coupled split-component ensemble is defined, generalizing from the most important codes of this class, staircase codes and braided block codes, and preserving a deterministic partitioning of component-code bits over code blocks. Our analysis focuses on low-complexity iterative algebraic decoding, which, for the binary erasure channel, is equivalent to a generalization of the peeling decoder. Using the differential equation method, we derive a vector recursion that tracks the expected residual graph evolution throughout the decoding process. The threshold of the recursion, for asymptotically long component codes, is found using potential function analysis. We generalize the analysis to mixture ensembles consisting of more than one type of component code. We give an example of a mixture ensemble consisting of two component codes, which has better performance than spatially-coupled split-component ensembles consisting of only one component code. The analysis extends to the binary symmetric channel by assuming miscorrection-free component-code decoding. Simple upper bounds on the number of errors correctable by the ensemble are derived. Finally, we analyze the threshold of spatially coupled split-component ensembles under beyond bounded-distance component decoding.

A concatenated soft-decision channel coding scheme consisting of an inner LDGM code and an outer staircase code is proposed. The soft-decision LDGM code is used for error reduction while the majority of bit errors are corrected by the low complexity hard-decision staircase code. Decoding complexity of the concatenated code is quantified by a score based on the number of edges in the LDGM code Tanner graph, the number of decoding iterations, and the number of staircase code decoding operations. The inner LDGM ensemble is designed by solving an optimization problem, which minimizes the product of the average node degree and an estimate of the required number of decoding iterations. A search procedure is used to find the inner and outer code pair with lowest complexity. The design procedure results in a Pareto-frontier characterization of the trade-off between net coding-gain and complexity for the concatenated code. Simulations of code designs at rate 5/6 show that the proposed scheme achieves net coding-gains equivalent to existing soft-decision codes, with up to 57% reduction in complexity.

Sequences of randomly generated bipartite configurations are analyzed; under mild conditions almost surely such configurations have minimum bisection width proportional to the number of vertices. This implies an almost sure Ω(n2/dmax2) scaling rule for the energy of directlyimplemented low-density parity-check (LDPC) decoder circuits for codes of block length n and maximum node degree dmax. It also implies an Ω(n3/2/dmax) lower bound for serialized LDPC decoders. It is also shown that all (as opposed to almost all) capacity-approaching, directly-implemented non-split-node LDPC decoding circuits, have energy, per iteration, that scales as Ω(χ2ln3χ), where χ = (1 - R/C)-1is the reciprocal gap to capacity, R is code rate, and C is channel capacity.

Sequences of VLSI circuits implemented according to the Thompson VLSI model that compute encoding and decoding functions, called coding schemes, are classified according to the rate at which their associated block error probability scales with block length N. It is shown that coding schemes for binary symmetric channels with probability of error that scales as O(f(N)) must have encoding and decoding energy that scales at least as Ω(N√(-ln f (N))). Polar coding schemes of rate greater than 1/2 are shown to have encoding and decoding energy that scales at least as Ω(N3/2). This lower bound is achievable up to polylogarithmic factors on a mesh-network.

We consider an asymptotic iterative decoding analysis of spatially-coupled split-component codes used for communication over binary symmetric channel (BSC) with hard-decision decoding at the receiver. The proposed analysis takes into account the impact of mis-corrections that occur in component code decoding. The analysis technique models flows of corrections and mis-corrections that occur throughout the decoding process in the entire coupled code chain. The results for spatially-coupled split-component codes with BCH component codes demonstrate that the analysis provides significantly more accurate estimates of the iterative decoding threshold values.

Compute-and-forward (C&F) is a promising new approach to interference management, enjoying several advantages over other information-theoretic schemes. C&F usually requires channel state information (CSI) at the receivers so that an “optimal” scaling factor can be computed for the purposes of decoding. In this paper, a blind C&F scheme-i.e., one not requiring CSI-is developed. Rather than attempting to compute the optimal scaling factor, this new scheme seeks one or more “good” scalars, i.e., scalars that allow correct decoding despite possibly being suboptimal. The region of all such good scalars is characterized. To find a good scalar, a computationally efficient scheme is proposed which involves error-detection, a hierarchically organized list, as well as a use of the smoothing lemma from lattice theory. Simulation results show that our blind C&F scheme achieves-for a class of nested lattice codes-the same throughput as its CSI-enabled counterpart at the expense of, approximately, a two-fold increase in computational complexity in the high-throughput region. Moreover, our blind C&F scheme can be applied to multisource multirelay networks with a good performance/complexity tradeoff.

This paper presents a quasi-synchronous design approach for signal processing circuits, in which timing violations are permitted, but without the need for a hardware compensation mechanism. A quasi-synchronous low-density parity-check decoder processing circuit based on the offset min-sum algorithm is designed, achieving the same performance and occupying the same area as a conventional synchronous circuit, but using up to 28% less energy.

The benefit of applying compute-and-forward (C&F) to slotted ALOHA (S-ALOHA) systems is studied. A Markov chain model is introduced, and an approximate stability region is given. It is shown that the approximate region is asymptotically exact as the number of users tends to infinity. It is also shown that the approximate region is very accurate even for systems with a small number of users. Further, based on the approximate region, simple expressions for the throughput and delay performance of S-ALOHA with C&F are derived, demonstrating the significant advantages offered by C&F.

A standard VLSI model is used to derive universal lower bounds on the energy of decoder circuits. In the circuit model used, the product of the circuit area and number of clock cycles, or the area-time complexity is proportional to the energy of computation. Lower bounds as a function of block length n are presented for three different circuit paradigms. Firstly, for circuits that compute in parallel, an Ω(n(logn)1/2) scaling rule is shown. Secondly, for circuits that compute serially, an Ω(nlogn) lower bound is presented. Thirdly, for a sequence of decoding circuits in which the number of output pins grows arbitrarily with block length, the energy is shown to grow as Ω(n(logn)1/5). In addition, it is shown that the energy complexity of almost all LDPC decoders that can get close to capacity and whose Tanner graphs are generated according to a uniform standard configuration model must take Ω(n2) area to implement directly.

We analyze a class of high performance, low decoding data-flow codes suitable for high bit-rate optical-fiber communication systems. A spatially-coupled split-component ensemble is defined, encompassing the most representative codes in this class, staircase codes and braided block codes. Our definition preserves two important properties of this class of codes: deterministic partitioning of component-code bits over code blocks and simple iterative algebraic component-code decoding. For the binary erasure channel, we derive a vector recursion for the decoding process and determine its threshold using potential function analysis. We generalize the analysis to mixture ensembles consisting of more than one type of component code. The analysis extends to the binary symmetric channel by assuming mis-correction-free component-code decoding. An intuitive upper-bound on the number of errors correctable by the ensemble is derived. Finally, we analyze the threshold of spatially-coupled split-component ensembles under beyond bounded-distance component decoding.

An upper bound on the capacity of a cascade of nonlinear and noisy channels is presented. The cascade mimics the split-step Fourier method for computing waveform propagation governed by the stochastic generalized nonlinear Schrödinger equation. It is shown that the spectral efficiency of the cascade is at most log(1+SNR), where SNR is the receiver signal-to-noise ratio. The results may be applied to optical fiber channels. However, the definition of bandwidth is subtle and leaves open interpretations of the bound. Some of these interpretations are discussed.

Thompson's model of very large scale integration computation relates the energy of a computation to the product of the circuit area and the number of clock cycles needed to carry out the computation. It is shown that for any sequence of increasing block-length decoder circuits implemented according to this model, if the probability of block error is asymptotically less than 1/2 then the energy of the computation scales at least as Ω(n(log n)1/2), and so the energy of decoding per bit must scale at least as Ω(log n)1/2. This implies that the average energy per decoded bit must approach infinity for any sequence of decoders that approaches capacity. The analysis techniques used are then extended to show that for any sequence of increasing block-length serial decoders, if the asymptotic block error probability is less than 1/2 then the energy scales at least as fast as Ω(n log n). In a very general case that allows for the number of output pins to vary with block length, it is shown that the energy must scale as Ω(n(log n)1/5). A simple example is provided of a class of circuits performing low-density parity-check decoding whose energy complexity scales as O(n2loglogn).

Though network coding is traditionally performed over finite fields, recent work on nested-lattice-based network coding suggests that, by allowing network coding over certain finite rings, more efficient physical-layer network coding schemes can be constructed. This paper considers the problem of communication over a finite-ring matrix channel Y = AX + BE, where X is the channel input, Y is the channel output, E is random error, and A and B are random transfer matrices. Tight capacity results are obtained and simple polynomial-complexity capacity-achieving coding schemes are provided under the assumption that A is uniform over all full-rank matrices and BE is uniform over all rank-t matrices, extending the work of Silva, Kschischang, and Kötter (2010), who handled the case of finite fields. This extension is based on several new results, which may be of independent interest, that generalize concepts and methods from matrices over finite fields to matrices over finite chain rings.

The nonlinear Fourier transform (NFT), a powerful tool in soliton theory and exactly solvable models, is a method for solving integrable partial differential equations governing wave propagation in certain nonlinear media. The NFT decorrelates signal degrees-of-freedom in such models, in much the same way that the Fourier transform does for linear systems. In this three-part series of papers, this observation is exploited for data transmission over integrable channels, such as optical fibers, where pulse propagation is governed by the nonlinear Schrödinger equation. In this transmission scheme, which can be viewed as a nonlinear analogue of orthogonal frequency-division multiplexing commonly used in linear channels, information is encoded in the nonlinear frequencies and their spectral amplitudes. Unlike most other fiber-optic transmission schemes, this technique deals with both dispersion and nonlinearity directly and unconditionally without the need for dispersion or nonlinearity compensation methods. This paper explains the mathematical tools that underlie the method.

In this paper, numerical methods are suggested to compute the discrete and the continuous spectrum of a signal with respect to the Zakharov-Shabat system, a Lax operator underlying numerous integrable communication channels including the nonlinear Schrödinger channel, modeling pulse propagation in optical fibers. These methods are subsequently tested and their ability to estimate the spectrum are compared against each other. These methods are used to compute the spectrum of various signals commonly used in the optical fiber communications. It is found that the layer peeling and the spectral methods are suitable schemes to estimate the nonlinear spectra with good accuracy. To illustrate the structure of the spectrum, the locus of the eigenvalues is determined under amplitude and phase modulation in a number of examples. It is observed that in some cases, as signal parameters vary, eigenvalues collide and change their course of motion. The real axis is typically the place from which new eigenvalues originate or, are absorbed into after traveling a trajectory in the complex plane.

Motivated by the looming capacity crunch in fiber-optic networks, information transmission over such systems is revisited. Among numerous distortions, interchannel interference in multiuser wavelength-division multiplexing (WDM) is identified as the seemingly intractable factor limiting the achievable rate at high launch power. However, this distortion and similar ones arising from nonlinearity are primarily due to the use of methods suited for linear systems, namely WDM and linear pulse-train transmission, for the nonlinear optical channel. Exploiting the integrability of the nonlinear Schrödinger (NLS) equation, a nonlinear frequency-division multiplexing (NFDM) scheme is presented, which directly modulates noninteracting signal degrees-of-freedom under NLS propagation. The main distinction between this and previous methods is that NFDM is able to cope with the nonlinearity, and thus, as the signal power or transmission distance is increased, the new method does not suffer from the deterministic crosstalk between signal components, which has degraded the performance of previous approaches. In this paper, emphasis is placed on modulation of the discrete component of the nonlinear Fourier transform of the signal and some simple examples of achievable spectral efficiencies are provided.

Though network coding is traditionally performed over finite fields, recent work on nested-lattice-based network coding suggests that, by allowing network coding over finite rings, more efficient physical-layer network coding schemes can be constructed. This paper considers the problem of communication over a finite-chain-ring matrix channel Y = AX + BZ, where X is the channel input, Y is the channel output, Z is random noise, and A and B are random transfer matrices. Tight capacity results are obtained and simple polynomial-complexity capacity-achieving coding schemes are provided under certain distributions of A, B, and Z, extending the work of Silva, Kschischang and Kötter (2010), who handled the case of finite fields. This extension is based on several new results that generalize concepts and methods from matrices over finite fields to matrices over finite chain rings.

This paper considers the transmission of information over integrable channels, a class of (mainly nonlinear) channels described by a Lax operator-pair. For such channels, the nonlinear Fourier transform, a powerful tool in soliton theory and exactly solvable models, plays the same role in “diagonalizing” the channel that the ordinary Fourier transform plays for linear convolutional channels. A transmission strategy encoding information in the nonlinear Fourier spectrum, termed nonlinear frequency-division multiplexing, is proposed for integrable channels that is the nonlinear analogue of orthogonal frequency-division multiplexing commonly used in linear channels. A central and motivating example is fiber-optic data transmission, for which the proposed transmission technique deals with both dispersion and nonlinearity directly and unconditionally without the need for dispersion or nonlinearity compensation methods.

Motivated by the looming “capacity crunch” in current fiber-optic systems, we recently suggested using the nonlinear Fourier transform (NFT) to transmit information over integrable communication channels such as the optical fiber channel, which is governed by the generalized nonlinear Schrödinger equation. In this transmission scheme information is encoded in the nonlinear Fourier transform of the signal, consisting of two components: a discrete and a continuous spectral function. In this paper, we restrict to discrete spectrum modulation and provide some simple examples of achievable spectral efficiencies. With this new method, deterministic distortions arising from the dispersion and nonlinearity, such as inter-symbol and interchannel interference are zero for a single user channel or all users of a multiple user network.

A method of designing low-density parity-check codes for bandwidth-efficient high-order modulation is proposed. A multi-edge-type LDPC code ensemble is used to improve the correspondence between modulation bit-channel capacity and bit-level protection in a bit-interleaved coded modulation system. A key innovation is the development of a multi-dimensional extrinsic information transfer (EXIT) vector field technique for the analysis and design of multi-edge-type codes. A condition, sufficient for the decoder to converge, is derived on the multi-dimensional EXIT vector field, and this condition is used as a constraint in code optimization. Code designs indicate that the proposed method produces codes matching the performance of codes designed using best available methods in ensemble threshold, and is capable of achieving identical finite-length error rates with shorter block-lengths. In addition to simplified design complexity, the resulting codes allow for low-complexity implementation and rate-adaptivity, and hence are well-suited for adaptive modulation systems.

The problem of designing physical-layer network coding (PNC) schemes via nested lattices is considered. Building on the compute-and-forward (C&F) relaying strategy of Nazer and Gastpar, who demonstrated its asymptotic gain using information-theoretic tools, an algebraic approach is taken to show its potential in practical, nonasymptotic, settings. A general framework is developed for studying nested-lattice-based PNC schemes-called lattice network coding (LNC) schemes for short-by making a direct connection between C&F and module theory. In particular, a generic LNC scheme is presented that makes no assumptions on the underlying nested lattice code. C&F is reinterpreted in this framework, and several generalized constructions of LNC schemes are given. The generic LNC scheme naturally leads to a linear network coding channel over modules, based on which noncoherent network coding can be achieved. Next, performance/complexity tradeoffs of LNC schemes are studied, with a particular focus on hypercube-shaped LNC schemes. The error probability of this class of LNC schemes is largely determined by the minimum intercoset distances of the underlying nested lattice code. Several illustrative hypercube-shaped LNC schemes are designed based on Constructions A and D, showing that nominal coding gains of 3 to 7.5 dB can be obtained with reasonable decoding complexity. Finally, the possibility of decoding multiple linear combinations is considered and related to the shortest independent vectors problem. A notion of dominant solutions is developed together with a suitable lattice-reduction-based algorithm.

We show that the broadcast capacity of an infinite-depth tree-structured network of error-free half-duplex-constrained relays can be achieved using constrained coding at the source and symbol forwarding at the relays.

Compute-and-forward (C&F) relaying usually requires channel state information (CSI) at the receivers so that an “optimal” scale factor can be computed for the purposes of decoding. In this paper, a blind C&F scheme - i.e., one not requiring CSI - is developed. Rather than attempting to compute the optimal scale factor, this new scheme seeks one (or more) “good” scalars, i.e., scalars which allow correct decoding despite possibly being sub-optimal. The region of all such good scalars is characterized. To find a good scalar, a computationally efficient scheme, involving error-detection and a hierarchically organized list, is proposed. Simulation results show that this blind C&F scheme achieves - for a class of lattices admitting an efficient trellis decoder - the same throughput as its CSI-enabled counterpart, at the expense of, approximately, a ten-fold increase in computational complexity in the high-throughput region.

Multipulse pulse position modulation (MPPM) has been widely proposed to improve data rate over traditional pulse position modulation (PPM) in free-space optical communication systems. Encoders for MPPM are typically lookup-table-based, thus restricting the practical size of MPPM codebooks. Power-of-two-sized MPPM codebooks typically do not have an efficient soft-in soft-out decoder, making them poorly suited for concatenation with an outer code under iterative decoding. In this paper, a new coding technique based on constrained coding is introduced that allows construction of codes which have an efficient encoding algorithm. More importantly, these new codes are suitable for iterative soft-decision decoding in concatenation with an outer error-correcting code. Simulation results for both the Gaussian and Poisson channels show that a serial concatenation with an outer low-density parity-check code (LDPC) can achieve between 2 to 3 dB coding gain over comparable Reed-Solomon and LDPC-coded MPPM systems.

The construction of lattice network coding schemes through signal codes is revisited. First, it is shown that the nominal coding gain of signal codes can be carried over from AWGN channels to lattice network coding. This demonstrates the potential of using signal codes in lattice network coding. However, in order to achieve the promised performance gain, all the side information related to shaping should be transmitted to the receiver. Second, the problem of delivering the side information to the receiver is considered. In particular, a generic scheme is proposed which can be optimized by solving a lattice design problem. Finally, two solutions to the lattice design problem are presented and the simulation results suggest that-with a reasonable overhead-the promised performance gain can be achieved by using our proposed scheme.

The problem of securing a network coding communication system against an eavesdropper is considered. The network implements linear network coding to deliver n packets from source to each receiver, and the adversary can eavesdrop on μ arbitrarily chosen links. The objective is to provide reliable communication to all receivers, while guaranteeing that the source information remains information-theoretically secure from the adversary. A coding scheme is proposed that can achieve the maximum possible rate of n - μ packets. The scheme, which is based on rank-metric codes, has the distinctive property of being universal: it can be applied on top of any communication network without requiring knowledge of or any modifications on the underlying linear network code. The only requirement of the scheme is that the packet length be at least n, which is shown to be strictly necessary for universal communication at the maximum rate. A further scenario is considered where the adversary is allowed not only to eavesdrop but also to inject up to t erroneous packets into the network, and the network may suffer from a rank deficiency of at most ρ. In this case, the proposed scheme can be extended to achieve the rate of n - ρ - 2t - μ packets. This rate is shown to be optimal under the assumption of zero-error communication.

The capacity of the channel defined by the stochastic nonlinear Schrödinger equation, which includes the effects of the Kerr nonlinearity and amplified spontaneous emission noise, is considered in the case of zero dispersion. In the absence of dispersion, this channel behaves as a collection of parallel per-sample channels. The conditional probability density function of the nonlinear per-sample channels is derived using both a sum-product and a Fokker-Planck differential equation approach. It is shown that, for a fixed noise power, the per-sample capacity grows unboundedly with input signal. The channel can be partitioned into amplitude and phase subchannels, and it is shown that the contribution to the total capacity of the phase channel declines for large input powers. It is found that a 2-D distribution with a half-Gaussian profile on the amplitude and uniform phase provides a lower bound for the zero-dispersion optical fiber channel, which is simple and asymptotically capacity-achieving at high signal-to-noise ratios (SNRs). A lower bound on the capacity is also derived in the medium-SNR region. The exact capacity subject to peak and average power constraints is numerically quantified using dense multiple ring modulation formats. The differential model underlying the zero-dispersion channel is reduced to an algebraic model, which is more tractable for digital communication studies, and, in particular, it provides a relation between the zero-dispersion optical channel and a 2 × 2 multiple-input multiple-output Rician fading channel. It appears that the structure of the capacity-achieving input distribution resembles that of the Rician fading channel, i.e., it is discrete in amplitude with a finite number of mass points, while continuous and uniform in phase.

The problem of designing new physical-layer network coding (PNC) schemes via lattice partitions is considered. Building on a recent work by Nazer and Gastpar, who demonstrated its asymptotic gain using information-theoretic tools, we take an algebraic approach to show its potential in non-asymptotic settings. We first relate Nazer-Gastpar's approach to the fundamental theorem of finitely generated modules over a principle ideal domain. Based on this connection, we generalize their code construction and simplify their encoding and decoding methods. This not only provides a transparent understanding of their approach, but more importantly, it opens up the opportunity to design efficient and practical PNC schemes. Finally, we apply our framework for PNC to a Gaussian relay network and demonstrate its advantage over conventional PNC schemes.

We study a non-multicast secure network coding problem with two receivers. First we study a linear-deterministic channel model with two receivers and a collection of eavesdroppers, which generalizes the Ozarow-Wyner wiretap channel II. The secrecy capacity region for independent and common messages is characterized and is achieved by concatenating a coset-coding scheme based on maximum rank distance codes with a repetition code. By applying our coding scheme at the source node of a network that uses an underlying generic network code we also establish the secrecy capacity region of a network coding problem with two sinks and one sender node.

This paper considers the problem of securing a linear network coding system against an adversary that is both an eavesdropper and a jammer. The network is assumed to transport n packets from source to each receiver, and the adversary is allowed to eavesdrop on μ arbitrarily chosen links and also to inject up to t erroneous packets into the network. The goal of the system is to achieve zero-error communication that is information-theoretically secure from the adversary. Moreover, this goal must be attained in a universal fashion, i.e., regardless of the network topology or the underlying network code. An upper bound on the achievable rate under these requirements is shown to be n - μ - 2t packets per transmission. A scheme is proposed that can achieve this maximum rate, for any n and any field size q, provided the packet length m is at least n symbols. The scheme is based on rank-metric codes and admits low-complexity encoding and decoding. In addition, the scheme is shown to be optimal in the sense that the required packet length is the smallest possible among all universal schemes that achieve the maximum rate.

Optical fiber channels modeled by the stochastic nonlinear Schrödinger equation and operating at zero dispersion are considered in this paper. As a result of the Kerr nonlinearity and its interaction with amplified spontaneous emission noise, the amplitude and phase channels correlate with each other and the statistics of the received signal are non-Gaussian. In order to find the capacity of such a nonlinear channel, one must find the conditional probability density function (PDF) of the channel output given channel input. The complex zero-dispersion channel (viewed as an instance of the Langevin equation) is transformed to polar coordinates using Itô calculus, where the cubic nonlinearity appears to be more tractable. A method is introduced based on the Fokker-Planck differential equation, known in the statistical physics, to describe the PDF of the received signal.

The optimal performance-complexity tradeoff for error-correcting codes at rates strictly below the Shannon limit is a central question in coding theory. This paper proposes a numerical approach for the minimization of decoding complexity for long-block-length irregular low-density parity-check (LDPC) codes. The proposed design methodology is applicable to any binary-input memoryless symmetric channel and any iterative message-passing decoding algorithm with a parallel-update schedule. A key feature of the proposed optimization method is a new complexity measure that incorporates both the number of operations required to carry out a single decoding iteration and the number of iterations required for convergence. This paper shows that the proposed complexity measure can be accurately estimated from a density-evolution and extrinsic-information transfer chart analysis of the code. A sufficient condition is presented for convexity of the complexity measure in the variable edge-degree distribution; when it is not satisfied, numerical experiments nevertheless suggest that the local minimum is unique. The results presented herein show that when the decoding complexity is constrained, the complexity-optimized codes significantly outperform threshold-optimized codes at long block lengths, within the ensemble of irregular codes.

This paper is motivated by the problem of error control in network coding when errors are introduced in a random fashion (rather than chosen by an adversary). An additive-multiplicative matrix channel is considered as a model for random network coding. The model assumes thatnpackets of lengthmare transmitted over the network, and up toterroneous packets are randomly chosen and injected into the network. Upper and lower bounds on capacity are obtained for any channel parameters, and asymptotic expressions are provided in the limit of large field or matrix size. A simple coding scheme is presented that achieves capacity in both limiting cases. The scheme has decoding complexityO(n2m) and a probability of error that decreases exponentially both in the packet length and in the field size in bits. Extensions of these results for coherent network coding are also presented.

While network coding can be an efficient means of information dissemination in networks, it is highly susceptible to “pollution attacks,” as the injection of even a single erroneous packet has the potential to corrupt each and every packet received by a given destination. Even when suitable error-control coding is applied, an adversary can, in many interesting practical situations, overwhelm the error-correcting capability of the code. To limit the power of potential adversaries, a broadcast transformation is introduced, in which nodes are limited to just a single (broadcast) transmission per generation. Under this broadcast transformation, the multicast capacity of a network is changed (in general reduced) from the number of edge-disjoint paths between source and sink to the number of internally disjoint paths. Exploiting this fact, a family of networks is proposed whose capacity is largely unaffected by a broadcast transformation. This results in a significant achievable transmission rate for such networks, even in the presence of adversaries.

Gabidulin codes are the rank-metric analogs of Reed-Solomon codes and have a major role in practical error control for network coding. This paper presents new encoding and decoding algorithms for Gabidulin codes based on low-complexity normal bases. In addition, a new decoding algorithm is proposed based on a transform-domain approach. Together, these represent the fastest known algorithms for encoding and decoding Gabidulin codes.

This paper considers the problem of secure network coding under the weak (and practically appealing) security requirements of Bhattad and Narayanan. Weak security allows communication at maximum rate while ensuring that only meaningless information is leaked to a wiretapper. Differently from the approach of Bhattad and Narayanan, which requires a joint design of the underlying network code and the outer security scheme, we propose a universal approach that is completely independent of the network code. In particular, the field size for linear network coding operations does not need to be enlarged. The scheme is also compatible with random network coding.

Rateless coding has recently been the focus of much practical as well as theoretical research. In this paper, rateless codes are shown to find a natural application in channels where the channel law varies unpredictably. Such unpredictability means that to ensure reliable communication block codes are limited by worst case channel variations. However, the dynamic decoding nature of rateless codes allows them to adapt opportunistically to channel variations. If the channel state selector is not malicious, but also not predictable, decoding can occur earlier, producing a rate of communication that can be much higher than the worst case. The application of rateless or ldquofountainrdquo codes to the binary erasure channel (BEC) can be understood as an application of these ideas. Further, this sort of decoding can be usefully understood as an incremental form of erasure decoding. The use of ideas of erasure decoding result in a significant increase in reliability.

The problem of error correction in both coherent and noncoherent network coding is considered under an adversarial model. For coherent network coding, where knowledge of the network topology and network code is assumed at the source and destination nodes, the error correction capability of an (outer) code is succinctly described by the rank metric; as a consequence, it is shown that universal network error correcting codes achieving the Singleton bound can be easily constructed and efficiently decoded. For noncoherent network coding, where knowledge of the network topology and network code is not assumed, the error correction capability of a (subspace) code is given exactly by a new metric, called theinjection metric, which is closely related to, but different than, the subspace metric of KOumltter and Kschischang. In particular, in the case of a non-constant-dimension code, the decoder associated with the injection metric is shown to correct more errors then a minimum-subspace-distance decoder. All of these results are based on a general approach to adversarial error correction, which could be useful for other adversarial channels beyond network coding.

The problem of securing a network coding communication system against a wiretapper adversary is considered. The network implements linear network coding to deliver n packets from source to each receiver, and the wiretapper can eavesdrop on mu arbitrarily chosen links. A coding scheme is proposed that can achieve the maximum possible rate of k = n - mu packets that are information-theoretically secure from the adversary. A distinctive feature of our scheme is that it is universal: it can be applied on top of any communication network without requiring knowledge of or any modifications on the underlying network code. In fact, even a randomized network code can be used. Our approach is based on Rouayheb-Soljaninpsilas formulation of a wiretap network as a generalization of the Ozarow-Wyner wiretap channel of type II. Essentially, the linear MDS code in Ozarow-Wynerpsilas coset coding scheme is replaced by a maximum-rank-distance code over an extension of the field in which linear network coding operations are performed.

This paper demonstrates that the transmission distance of an ON-OFF-keyed high-speed pseudolinear optical communication system can be dramatically improved by means of runlength-limited coding. The key idea is to impose constraints on transmitted sequences such that the minimum interpulse spacing increases, and the average transmission power decreases. Both effects help suppress intrachannel four-wave mixing, a major nonlinear penalty in pseudolinear long-haul links. Several coding schemes with different properties are designed for various constraints and compared against a prototypical reference system. Finally, numerical simulations are performed for a benchmark system employing differential phase-shift keying. The results obtained indicate that the runlength-limited coding approach can be considered a legitimate alternative to this more advanced modulation format.

The problem of error-control in random linear network coding is considered. A “noncoherent” or “channel oblivious” model is assumed where neither transmitter nor receiver is assumed to have knowledge of the channel transfer characteristic. Motivated by the property that linear network coding is vector-space preserving, information transmission is modeled as the injection into the network of a basis for a vector space$V$and the collection by the receiver of a basis for a vector space$U$. A metric on the projective geometry associated with the packet space is introduced, and it is shown that a minimum-distance decoder for this metric achieves correct decoding if the dimension of the space$V \cap U$is sufficiently large. If the dimension of each codeword is restricted to a fixed integer, the code forms a subset of a finite-field Grassmannian, or, equivalently, a subset of the vertices of the corresponding Grassmann graph. Sphere-packing and sphere-covering bounds as well as a generalization of the Singleton bound are provided for such codes. Finally, a Reed–Solomon-like code construction, related to Gabidulin's construction of maximum rank-distance codes, is described and a Sudan-style “list-1” minimum-distance decoding algorithm is provided.

The problem of error control in random linear network coding is addressed from a matrix perspective that is closely related to the subspace perspective of KÖtter and Kschischang. A large class of constant-dimension subspace codes is investigated. It is shown that codes in this class can be easily constructed from rank-metric codes, while preserving their distance properties. Moreover, it is shown that minimum distance decoding of such subspace codes can be reformulated as a generalized decoding problem for rank-metric codes where partial information about the error is available. This partial information may be in the form of erasures (knowledge of an error location but not its value) anddeviations(knowledge of an error value but not its location). Taking erasures and deviations into account (when they occur) strictly increases the error correction capability of a code: if$\mu$erasures and$\delta$deviations occur, then errors of rank$t$can always be corrected provided that$2t \leq d - 1 + \mu + \delta$, where$d$is the minimum rank distance of the code. For Gabidulin codes, an important family of maximum rank distance codes, an efficient decoding algorithm is proposed that can properly exploit erasures and deviations. In a network coding application, where$n$packets of length$M$over$\BBF _{q}$are transmitted, the complexity of the decoding algorithm is given by$O(dM)$operations in an extension field$\BBF _{q^{n}}$.

The problem of error-control in a "noncoherent" random network coding channel is considered. Information transmission is modelled as the injection into the network of a basis for a vector space V and the collection by the receiver of a basis for a vector space U. A suitable coding metric on subspaces is defined, under which a minimum distance decoder achieves correct decoding if the dimension of the space V U is large enough. When the dimension of each codeword is restricted to a fixed integer, the code forms a subset of the vertices of the Grassmann graph. Sphere-packing, sphere-covering bounds and a Singleton bound are provided for such codes. A Reed-Solomon-like code construction is provided and decoding algorithm given.

It is shown that the error correction problem in random network coding is closely related to a generalized decoding problem for rank-metric codes. This result enables many of the rich tools devised for the rank metric to be naturally applied to random network coding. The generalized decoding problem introduced in this paper allows partial information about the error to be supplied. This partial information can be either in the form of erasures (knowledge of an error location but not its value) or deviations (knowledge of an error value but not its location). For Gabidulin codes, an efficient decoding algorithm is proposed that can correct e errors, mu erasures and v deviations, provided 2isin + mu + v les d - 1, where d is the minimum distance of the code.

This paper presents a new sub-optimal lattice decoder based on decomposition of the detection lattice into cosets and iterative application of LLL reduction to its primal and dual representations. From each coset, a candidate solution is chosen using linear equalization followed by integer quantization. These candidates are then compared and the best amongst them is returned. Because the cosets are identical save for distinct translation vectors, their sub-lattice decoders share common preprocessing and can operate very efficiently in parallel. Exclusive of pre-processing, the computational complexity of the proposed decoder is quadratic in the problem dimension and linear in the number of cosets. Simulation results demonstrate the near-ML bit error rate performance offered by the new decoder in the context of existing QAM-modulated MIMO detection schemes.

The problem of error control in random network coding is considered, and a formulation of the problem is given in terms of rank-metric codes. This formulation allows many of the tools developed for rank-metric codes to be applied to random network coding. A random network code induces a generalized decoding problem for rank-metric codes in which the channel may supply partial information about the error in the form of erasures (knowledge of an error location not its values) and deviations (knowledge of an error value but not its location).

The message-passing approach to model-based signal processing is developed with a focus on Gaussian message passing in linear state-space models, which includes recursive least squares, linear minimum-mean-squared-error estimation, and Kalman filtering algorithms. Tabulated message computation rules for the building blocks of linear models allow us to compose a variety of such algorithms without additional derivations or computations. Beyond the Gaussian case, it is emphasized that the message-passing approach encourages us to mix and match different algorithmic techniques, which is exemplified by two different approaches—steepest descent and expectation maximization—to message passing through a multiplier node.

This paper presents a reduced-complexity approximate density evolution (DE) scheme for low-density parity-check (LDPC) codes in channels with memory in the form of a hidden Markov chain. This approximation is used to design degree sequences representing some of the best known LDPC code ensembles for the Gilbert-Elliott channel, and example optimizations are also given for other Markov channels. The problem of approximating the channel estimation is addressed by obtaining a specially constructed message-passing schedule in which the channel messages all approach their stable densities. It is shown that this new schedule is much easier to approximate than the standard schedule, but has the same ultimate performance in the limits of long block length and many decoding iterations. This result is extended to show that all message-passing schedules that satisfy mild conditions will have the same threshold under density evolution

A partial ordering on general finite-state Markov channels is given, which orders the channels in terms of probability of symbol error under iterative estimation decoding of a low-density parity-check (LDPC) code. This result is intended to mitigate the complexity of characterizing the performance of general finite-state Markov channels, which is difficult due to the large parameter space of this class of channel. An analysis tool, originally developed for the Gilbert-Elliott channel, is extended and generalized to general finite-state Markov channels. In doing so, an operator is introduced for combining finite-state Markov channels to create channels with larger state alphabets, which are then subject to the partial ordering. As a result, the probability of symbol error performance of finite-state Markov channels with different numbers of states and wide ranges of parameters can be directly compared. Several examples illustrating the use of the techniques are provided, focusing on binary finite-state Markov channels and Gaussian finite-state Markov channels. Furthermore, this result is used to order Gilbert-Elliott channels with different marginal state probabilities, which was left as an open problem by previous work.

In a system utilizing multiuser diversity, regular feedback of channel-quality predictions to the base station is required for each user. Typically, the measure of channel quality must be quantized at each mobile station before it can be sent back. In this paper, we present two distributed scalar quantization schemes that optimize two different performance criteria: a) the minimization of the probability Peof incorrectly identifying the user with the best channel quality and b) maximization of the resulting throughput R. For a typical Rayleigh-fading system with 30 users per sector, numerical optimization results show that the Peand R realized by the uniform quantization strategy with 16 quantization levels for each user can be achieved by only three quantization levels using the two proposed strategies. A practical approximation of the proposed schemes is studied and is shown to provide near-optimal performance for both performance criteria as the number of quantization levels becomes large

Reed-Solomon codes are powerful error-correcting codes that can be found in many digital communications standards. Recently, there has been an interest in soft-decision decoding of Reed-Solomon codes, incorporating reliability information from the channel into the decoding process. The Koetter-Vardy algorithm is a soft-decision decoding algorithm for Reed-Solomon codes which can provide several dB of gain over traditional hard-decision decoders. The algorithm consists of a soft-decision front end to the interpolation-based Guruswami-Sudan list decoder. The main computational task in the algorithm is a weighted interpolation of a bivariate polynomial. We propose a parallel architecture for the hardware implementation of bivariate interpolation for soft-decision decoding. The key feature is the embedding of both a binary tree and a linear array into a 2-D array processor, enabling fast polynomial evaluation operations. An field-programmable gate array interpolation processor was implemented and demonstrated at a clock frequency of 23 MHz, corresponding to decoding rates of 10-15 Mb/s

We propose a bit-serial LDPC decoding scheme to reduce interconnect complexity in fully-parallel low-density parity-check decoders. Bit-serial decoding also facilitates efficient implementation of wordlength-programmable LDPC decoding which is essential for gear shift decoding. To simplify the implementation of bit-serial decoding we propose a new approximation to the check update function in the min-sum decoding algorithm. The new check update rule computes only the absolute minimum and applies a correction to outgoing messages if required. We present a 650-Mbps bit-serial (480, 355) RS-based LDPC decoder implemented on a single Altera Stratix EP1S80 FPGA device. To our knowledge, this is the fastest FPGA-based LDPC decoder reported in the literature

This paper considers a class of iterative message-passing decoders for low-density parity-check codes in which the decoder can choose its decoding rule from a set of decoding algorithms at each iteration. Each available decoding algorithm may have different per-iteration computation time and performance. With an appropriate choice of algorithm at each iteration, overall decoding latency can be reduced significantly, compared with standard decoding methods. Such a decoder is called a gear-shift decoder because it changes its decoding rule (shifts gears) in order to guarantee both convergence and maximum decoding speed (minimum decoding latency). Using extrinsic information transfer charts, the problem of finding the optimum (minimum decoding latency) gear-shift decoder is formulated as a computationally tractable dynamic program. The optimum gear-shift decoder is proved to have a decoding threshold equal to or better than the best decoding threshold among those of the available algorithms. In addition to speeding up software decoder implementations, gear-shift decoding can be applied to optimize a pipelined hardware decoder, minimizing hardware cost for a given decoder throughput.

This paper considers a class of iterative message-passing decoders for low-density parity-check codes in which the decoder can choose its decoding rule from a set of decoding algorithms at each iteration. Each available decoding algorithm may have a different per-iteration computation time and performance. With an appropriate choice of algorithm at each iteration, overall decoding latency can be reduced significantly, compared with standard decoding methods. Such a decoder is called a gear-shift decoder because it changes its decoding rule (shifts gears) in order to guarantee both convergence and maximum decoding speed (minimum decoding latency). Using extrinsic information transfer charts, the problem of finding the optimum (minimum decoding latency) gear-shift decoder is formulated as a computationally tractable dynamic program. The optimum gear-shift decoder is proved to have a decoding threshold equal to or better than the best decoding threshold among those of the available algorithms. In addition to speeding up software decoder implementations, gear-shift decoding can be applied to optimize a pipelined hardware decoder, minimizing hardware cost for a given decoder throughput

Efficient soft-decision decoding of Reed–Solomon codes is made possible by the Koetter–Vardy (KV) algorithm which consists of a front-end to the interpolation-based Guruswami–Sudan list decoding algorithm. This paper approaches the soft-decision KV algorithm from the point of view of a communications systems designer who wants to know what benefits the algorithm can give, and how the extra complexity introduced by soft decoding can be managed at the systems level. We show how to reduce the computational complexity and memory requirements of the soft-decision front-end. Applications to wireless communications over Rayleigh fading channels and magnetic recording channels are proposed. For a high-rate (RS 9225,239) Reed–Solomon code, 2–3 dB of soft-decision gain is possible over a Rayleigh fading channel using 16-quadrature amplitude modulation. For shorter codes and at lower rates, the gain can be as large as 9 dB. To lower the complexity of decoding on the systems level, the redecoding architecture is explored which uses only the appropriate amount of complexity to decode each packet. An error-detection criterion based on the properties of the KV decoder is proposed for the redecoding architecture. Queuing analysis verifies the practicality of the redecoding architecture by showing that only a modestly sized RAM buffer is required.

Efficient soft-decision decoding of Reed-Solomon (RS) codes is made possible by the Koetter-Vardy (KV) algorithm which consists of a front-end to the interpolation-based Guruswami-Sudan (GS) list decoding algorithm. This paper approaches the soft-decision KV algorithm from the point of view of a communications systems designer who wants to know what benefits the algorithm can give, and how the extra complexity introduced by soft decoding can be managed at the systems level. We show how to reduce the computational complexity and memory requirements of the soft-decision front-end. Applications to wireless communications over Rayleigh fading channels and magnetic recording channels are proposed. For a high-rate RS(255,239) code, 2-3 dB of soft-decision gain is possible over a Rayleigh fading channel using 16-quadrature amplitude modulation. For shorter codes and at lower rates, the gain can be as large as 9 dB. To lower the complexity of decoding on the systems level, the redecoding architecture is explored, which uses only the appropriate amount of complexity to decode each packet. An error-detection criterion based on the properties of the KV decoder is proposed for the redecoding architecture. Queueing analysis verifies the practicality of the redecoding architecture by showing that only a modestly sized RAM buffer is required

We consider an iterative message-passing decoder that can choose its decoding rule among a group of decoding algorithms at each iteration (for example: a software decoder). Each available decoding algorithm may have a different computation time and performance. We first show that with proper choice of algorithm at each iteration, decoding latency can significantly be reduced. We call such a decoder a gear-shift decoder because it changes its decoding rule (shifts gear) in order to guarantee both convergence and minimum decoding-latency. We also prove that the optimum gear-shift decoder (the one with the minimum decoding-latency) has a decoding threshold equal to or better than the best decoding threshold of the available algorithms. We use extrinsic information transfer charts and dynamic programming to find the optimum gear-shift decoder.

The complexity-rate tradeoff for error-correcting codes below the Shannon limit is a central question in coding theory. This paper makes progress in this area by presenting a joint numerical optimization of rate and decoding complexity for low-density parity-check codes. The focus of this paper is on the binary symmetric channel and on a class of decoding algorithms for which an exact extrinsic information transfer (EXIT) chart analysis is possible. This class of decoding algorithms includes the Gallager decoding algorithm B. The main feature of the optimization method is a complexity measure based on the EXIT chart that accurately estimates the number of iterations required for the decoding algorithm to reach a target error rate. Under a fixed check-degree distribution, it is shown that the proposed complexity measure is a convex function of the variable-degree distribution in a region of interest. This allows us to numerically characterize the complexity-rate tradeoff. We show that for the Gallager B decoding algorithm on binary symmetric channels, the optimization procedure can produce complexity savings of 30-40% as compared to the conventional code design method

The highly stochastic nature of wireless environments makes it desirable to monitor link loss rates in wireless sensor networks. In a wireless sensor network, link loss monitoring is particularly supported by the data aggregation communication paradigm of network traffic: the data collecting node can infer link loss rates on all links in the network by exploiting whether packets from various sensors are received, and there is no need to actively inject probing packets for inference purposes. In this paper, we present a low complexity algorithmic framework for link loss monitoring based on the recent modeling and computational methodology of factor graphs. The proposed algorithm iteratively updates the estimates of link losses upon receiving (or detecting the loss of) recently sent packets by the sensors. The algorithm exhibits good performance and scalability, and can be easily adapted to different statistical models of networking scenarios. In particular, due to its low complexity, the algorithm is particularly suitable as a long-term monitoring facility.

We consider a class of message-passing decoders for low-density parity-check (LDPC) codes whose messages are binary valued. We prove that if the channel is symmetric and all codewords are equally likely to be transmitted, an optimum decoding rule (in the sense of minimizing message error rate) should satisfy certain symmetry and isotropy conditions. Using this result, we prove that Gallager's Algorithm B achieves the optimum decoding threshold among all binary message-passing decoding algorithms for regular codes. For irregular codes, we argue that when the nodes of the message-passing decoder do not exploit knowledge of their decoding neighborhood, optimality of Gallager's Algorithm B is preserved. We also consider the problem of designing irregular LDPC codes and find a bound on the achievable rates with Gallager's Algorithm B. Using this bound, we study the case of low error-rate channels and analytically find good degree distributions for them.

A conditionally Gaussian channel is a vector channel in which the channel output, given the channel input, has a Gaussian distribution with (well-behaved) input-dependent mean and covariance. We study the capacity-achieving probability measure for conditionally Gaussian channels subject to bounded-input constraints and average cost constraints. Many practical communication systems, including additive Gaussian noise channels, certain optical channels, fading channels, and interference channels fall within this framework. Subject to bounded-input constraint (and average cost constraints), we show that the channel capacity is achievable and we derive a necessary and sufficient condition for a probability measure to be capacity achieving. Under certain conditions, the capacity-achieving measure is proved to be discrete.

Density evolution analysis of low-density parity-check (LDPC) codes in memoryless channels is extended to the Gilbert-Elliott (GE) channel, which is a special case of a large class of channels with hidden Markov memory. In a procedure referred to as estimation decoding, the sum-product algorithm (SPA) is used to perform LDPC decoding jointly with channel-state detection. Density evolution results show (and simulation results confirm) that such decoders provide a significantly enlarged region of successful decoding within the GE parameter space, compared with decoders that do not exploit the channel memory. By considering a variety of ways in which a GE channel may be degraded, it is shown how knowledge of the decoding behavior at a single point of the GE parameter space may be extended to a larger region within the space, thereby mitigating the large complexity needed in using density evolution to explore the parameter space point-by-point. Using the GE channel as a straightforward example, we conclude that analysis of estimation decoding for LDPC codes is feasible in channels with memory, and that such analysis shows large potential gains.

We introduce the concept of convolutional factor graphs, which represent convolutional factorizations of multivariate functions, just as conventional (multiplicative) factor graphs represent multiplicative factorizations. Convolutional and multiplicative factor graphs arise as natural Fourier transform duals. In coding theory applications, algebraic duality of group codes is essentially an instance of Fourier transform duality. Convolutional factor graphs arise when a code is represented as a sum of subcodes, just as conventional multiplicative factor graphs arise when a code is represented as an intersection of supercodes. With auxiliary variables, convolutional factor graphs give rise to "syndrome realizations" of codes, just as multiplicative factor graphs with auxiliary variables give rise to "state realizations." We introduce normal and co-normal extensions of a multivariate function, which essentially allow a given function to be represented with either a multiplicative or a convolutional factorization, as is convenient. We use these function extensions to derive a number of duality relationships among the corresponding factor graphs, and use these relationships to obtain the duality properties of Forney graphs as a special case.

We propose a parallel architecture for implementing the interpolation step in the Koetter-Vardy soft-decision Reed-Solomon decoding algorithm. The key feature is the embedding of both a binary tree and a linear array into a two-dimensional array processor, enabling fast polynomial evaluation operations. An FPGA interpolation processor was implemented and demonstrated at a clock frequency of 23 MHz, corresponding to decoding rates of 10-15 Mbps.

Short-range wireless optical channels provide high-data rate indoor links free of spectral licensing issues. In this work, we present a point-to-point, multiple-input/multiple output (MIMO) optical channel, termed the pixelated wireless optical channel, which exploits the inherent spatial diversity of the channel to achieve gains in spectral efficiency. Information is conveyed through the transmission of a series of pixelated images to a receiver array. An experimental prototype point-to-point link is constructed using a 512 /spl times/ 512 pixel LCD panel and 154 /spl times/ 154 pixels of a CCD camera. Based on channel measurements, a channel model amenable to computer simulation is developed. Spatial discrete multitone modulation is proposed for this MIMO wireless optical channel to combat the low pass spatial response of the channel. The capacity of a given channel realization is estimated by way of the water-pouring spectrum. Multi-level coding and multi-stage decoding over the spatial frequency bins is shown to yield spectral efficiencies of approximately 1.7 kbit/s/Hz over a range of 2 m.

A conditional Gaussian (CG) channel is a discrete-time memoryless channel such that an admissible channel input gives rise to a channel output that is Gaussian distributed with an expectation vector and a covariance matrix. In this paper, closed and bounded subset of receiver, and the channel constraint is called the bounded-input constraint is presented. The mutual information between the channel input and output with an input probability measure which satisfies the channel input constraints is maximized. An input probability measure is said to be discrete in amplitude and uniform in phase (DAUP) if the probability distribution of the amplitude is discrete with a finite number of probability mass points, and the phase is uniformly distributed

In multiuser communication systems the exchange of some number of rate-limited messages both between encoders, and between decoders, can enlarge the achievable rate region. We consider interaction between a pair of Slepian-Wolf encoders, and a pair of deterministic broadcast channel decoders. For these systems, a single one-way message is sufficient. More generally, we make connections to relay channels and consider how to quantize data for relaying.

We present a strategy for the reliable communication of a message, in a variable number of channel uses, over an unknown discrete memoryless channel (DMC). The decoder periodically tests the received sequence and, when it can decode, sends an acknowledgment to the transmitter, which then stops transmitting. By choosing the size of the codebook large enough, the rate that is reliably realized by the strategy can be made to approach arbitrarily closely the mutual information between channel input and output induced by the user-chosen input distribution. The strategy presented can be considered as a generalization to arbitrary unknown DMCs of earlier variable length coding schemes, such as digital fountain codes for binary erasure channels (BECs), and a coding strategy for binary symmetric channels (BSCs) presented by Tchamkerten and Telatar

We present a reduced-complexity approximate density evolution scheme that is particularly suitable for Markov-modulated channels, based on the semiGaussian approximation. We propose a design algorithm whose complexity is comparable to the memoryless case, assuming unlimited precomputation is allowed. We also present degree sequences representing some of the best known codes in the GE channel which were designed using this technique. This design tool can be easily extended to more complicated Markov-modulated channels

We apply irregular low-density parity-check (LDPC) codes to the design of multilevel coded quadrature amplitude modulation (QAM) schemes for application in discrete multitone systems in frequency-selective channels. A combined Gray/Ungerboeck scheme is used to label each QAM constellation. The Gray-labeled bits are protected using an irregular LDPC code with iterative soft-decision decoding, while other bits are protected using a high-rate Reed-Solomon code with hard-decision decoding (or are left uncoded). The rate of the LDPC code is selected by analyzing the capacity of the channel seen by the Gray-labeled bits and is made adaptive by selective concatenation with an inner repetition code. Using a practical bit-loading algorithm, we apply this coding scheme to an ensemble of frequency-selective channels with Gaussian noise. Over a large number of channel realizations, this coding scheme provides an average effective coding gain of more than 7.5 dB at a bit-error rate of 10/sup -7/ and a block length of approximately 10/sup 5/ b. This represents a gap of approximately 2.3 dB from the Shannon limit of the additive white Gaussian noise channel, which could be closed to within 0.8-1.2 dB using constellation shaping.

We introduce a new one-dimensional (1-D) analysis of low-density parity-check (LDPC) codes on additive white Gaussian noise channels which is significantly more accurate than similar 1-D methods. Our method assumes a Gaussian distribution in message-passing decoding only for messages from variable nodes to check nodes. Compared to existing work, which makes a Gaussian assumption both for messages from check nodes and from variable nodes, our method offers a significantly more accurate estimate of convergence behavior and threshold of convergence. Similar to previous work, the problem of designing irregular LDPC codes reduces to a linear programming problem. However, our method allows irregular code design in a wider range of rates without any limit on the maximum variable-node degree. We use our method to design irregular LDPC codes with rates greater than 1/4 that perform within a few hundredths of a decibel from the Shannon limit. The designed codes perform almost as well as codes designed by density evolution.

We determine upper and lower bounds on the channel capacity of power- and bandwidth-constrained optical intensity channels corrupted by white Gaussian noise. These bounds are shown to converge asymptotically at high optical signal-to-noise ratios (SNRs). Unlike previous investigations on low-intensity Poisson photon counting channels, such as some fiber optic links, this channel model is realistic for indoor free space optical channels corrupted by intense ambient light. An upper bound on the capacity is found through a sphere-packing argument while a lower bound is computed through the maxentropic source distribution. The role of bandwidth is expressed by way of the effective dimension of the set of signals and, together with an average optical power constraint, is used to determine bounds on the spectral efficiency of time-disjoint optical intensity signaling schemes. The bounds show that, at high optical SNRs, pulse sets based on raised-quadrature amplitude modulation (QAM) and prolate spheroidal wave functions have larger achievable maximum spectral efficiencies than traditional rectangular pulse basis sets. This result can be considered as an extension of previous work on photon counting channels which closely model low optical intensity channels with rectangular pulse shapes.

Traditional approaches to constructing constellations for electrical channels cannot be applied directly to the optical intensity channel. This work presents a structured signal space model for optical intensity channels where the nonnegativity and average amplitude constraints are represented geometrically. Lattice codes satisfying channel constraints are defined and coding and shaping gain relative to a baseline are computed. An effective signal space dimension is defined to represent the precise impact of coding and shaping on bandwidth. Average optical power minimizing shaping regions are derived in some special cases. Example lattice codes are constructed and their performance on an idealized point-to-point wireless optical link is computed. Bandwidth-efficient schemes are shown to have promise for high data-rate applications, but require greater average optical power.

We develop a Tanner graph (TG) construction for an Abelian group block code L with arbitrary alphabets at different coordinates, an important application of which is the representation of the label code of a lattice. The construction is based on the modular linear constraints imposed on the code symbols by a set of generators for the dual code L*. As a necessary step toward the construction of a TG for L we devise an efficient algorithm for finding a generating set for L*. In the process, we develop a construction for lattices based on an arbitrary Abelian group block code, called generalized Construction A (GCA), and explore relationships among a group code, its GCA lattice, and their duals. We also study the problem of finding low-complexity TGs for Abelian group block codes and lattices; and derive tight lower bounds on the label-code complexity of lattices. It is shown that for many important lattices, the minimal label codes which achieve the lower bounds cannot be supported by cycle-free Tanner graphs.

In the 50 years since Shannon determined the capacity of ergodic channels, the construction of capacity-approaching coding schemes has been the supreme goal of coding research. Finally today, we know of practical codes and decoding algorithms that can closely approach the channel capacity of some classical memoryless channels. It is a remarkable fact motivating this special issue that all known practical, capacity-approaching coding schemes are now understood to be codes defined on graphs, together with the associated iterative decoding algorithms.

Algorithms that must deal with complicated global functions of many variables often exploit the manner in which the given functions factor as a product of "local" functions, each of which depends on a subset of the variables. Such a factorization can be visualized with a bipartite graph that we call a factor graph, In this tutorial paper, we present a generic message-passing algorithm, the sum-product algorithm, that operates in a factor graph. Following a single, simple computational rule, the sum-product algorithm computes-either exactly or approximately-various marginal functions derived from the global function. A wide variety of algorithms developed in artificial intelligence, signal processing, and digital communications can be derived as specific instances of the sum-product algorithm, including the forward/backward algorithm, the Viterbi algorithm, the iterative "turbo" decoding algorithm, Pearl's (1988) belief propagation algorithm for Bayesian networks, the Kalman filter, and certain fast Fourier transform (FFT) algorithms.

In-building power lines have been considered as a medium for high speed data transmission for applications like home networking and Internet access. Frequency selectivity and time variation of this medium in addition to the high level of narrow-band and impulsive interference makes multi-carrier modulation, and especially its popular variant discrete multitone (DMT), an attractive modulation candidate for this application. This paper presents the results of our measurements of the high frequency characteristics of ordinary in-building power lines, as well as simulation results of a DMT transceiver system in an in-building power line environment.

We focus on applications of low-rate Gallager (1963) (low-density parity-check) codes in code-division multiple-access schemes. The codes that we present here achieve good performance with relatively short frame-lengths in additive white Gaussian noise channels and, perhaps more importantly, in fading channels. These codes can be decoded with low complexity by using iterative decoding procedures. We present a construction that yields good short frame-length Gallager codes. Bounds on the frame-error probability for a maximum-likelihood decoder are obtained.

We focus our attention on Gallager codes with parameters compatible with the IS-95 cellular radio standard. We discuss low complexity software and hardware implementations of an iterative decoder for {N,-,3} Gallager codes. We estimate that by using Gallager codes, a factor of five improvement in the code-division multiple-access system capacity relative to an uncoded system can be achieved, equivalent to a factor of two improvement relative to state-of-the art orthogonal convolutional codes. Simulation results demonstrate the good performance of short-frame Gallager codes in the additive white Gaussian noise and certain fading channels.

Cellular transmission standards such as GSM and IS-54 produce data streams with varying degrees of significance at the source encoder level. We propose an unequal error protection scheme based on a non-uniform signal set which provides the more important data with a preferential Euclidean distance. The unequal error protection is partly accomplished by the modulator in contrast to the conventional systems where the channel encoder is solely responsible. The coding gain resulting from the asymmetric modulation can be translated into a reduction in the complexity of the channel encoder; specifically a reduction by more than half in the number of encoder states can be expected. We study the interaction between the code complexity and the modulation asymmetry in quantitative terms. For differentially coherent systems, a /spl pi//6-shifted differential embedded QPSK is proposed. Decentralizing the bit protection culminates in an extra degree of freedom which in turn introduces more flexibility into the system design.

It is known that spread-spectrum (SS) communications in general, and code-division multiple access (CDMA) in particular, gain certain advantages in performance, if powerful low-rate error-correcting codes are used for error-protection in such systems. We propose an innovative coding scheme for SS systems based on Gallager (low-density parity-check) codes that can be iteratively decoded with relatively low complexity. Consequently, this scheme is readily implementable in both base station and subscriber side receivers. We focus our attention on Gallager codes with parameters compatible with the IS-95 cellular radio standard. We discuss soft- and hardware implementations of iterative decoding for Gallager codes. We estimate that by using Gallager codes, a factor of five improvement in CDMA cell capacity relative to the uncoded system can be achieved, equivalent to a factor of two improvement relative to the state-of-the art orthogonal convolutional codes.

The bit-error rate (BER) performance of new iterative decoding algorithms (e,g,, turbodecoding) is achieved at the expense of a computationally burdensome decoding procedure. We present a method called early detection that can be used to reduce the computational complexity of a variety of iterative decoders. Using a confidence criterion, some information symbols, state variables, and codeword symbols are detected early on during decoding. In this way, the computational complexity of further processing is reduced with a controllable increase in the BER. We present an easily implemented instance of this algorithm, called trellis splicing, that can be used with turbodecoding. For a simulated system of this type, we obtain a reduction in the computational complexity of up to a factor of four, relative to a turbodecoder that obtains the same increase in the BER by performing fewer iterations.

We present a unified graphical model framework for describing compound codes and deriving iterative decoding algorithms. After reviewing a variety of graphical models (Markov random fields, Tanner graphs, and Bayesian networks), we derive a general distributed marginalization algorithm for functions described by factor graphs. From this general algorithm, Pearl's (1986) belief propagation algorithm is easily derived as a special case. We point out that iterative decoding algorithms for various codes, including "turbo decoding" of parallel-concatenated convolutional codes, may be viewed as probability propagation in a graphical model of the code. We focus on Bayesian network descriptions of codes, which give a natural input/state/output/channel description of a code and channel, and we indicate how iterative decoders can be developed for parallel-and serially concatenated coding systems, product codes, and low-density parity-check codes.

A sequential decoder for linear block codes that performs maximum-likelihood soft-decision decoding is described. The decoder uses a metric computed from a lower bound on the cost of the unexplored portion of the code tree. It is shown that for certain block codes the average computational complexity of this metric is superior to that of the Fano metric. A new function, the cumulative column distance function, is introduced for linear block codes. This function is an important factor that determines the average computational effort of a sequential decoder for a linear block code with an arbitrary maximum-likelihood metric. Simulation results show that a sequential decoder for linear block codes with a fast growing cumulative column distance function achieves a low computational complexity, a result analogous to that for convolutional codes.

An important problem in the theory and application of block code trellises is to find a coordinate permutation of a given code to minimize the trellis complexity. We show that the problem of finding a coordinate permutation that minimizes the number of vertices at a given depth in the minimal trellis for a binary linear block code is NP-complete.

We show that the family of maximal fixed-cost (MFC) codes, with codeword costs defined in a right-cancellative semigroup, are rectangular, and hence admit biproper trellis presentations. Among all possible trellis presentations for a rectangular code, biproper trellises minimize a wide variety of complexity measures, including the Viterbi decoding complexity. Examples of MFC codes include such "nonlinear" codes as permutation codes and shells of constant norm in the integer lattice, as well as linear codes over a finite field. The intersection of two rectangular codes is another rectangular code; therefore, "nonlinear" codes such as lattice shells or words of constant weight in a linear code have biproper trellis presentations. We show that every rectangular code can be interpreted as an MFC code. Applications of these results include error detection, trellis-based indexing, and soft-decision decoding.

We prove a conjecture of McEliece, establishing that for each fixed order of positions of a linear code C, the minimal trellis minimizes the quantity |E|-|V|+1, where |E| and |V| stand for the number of edges and vertices in the trellis, respectively. As a consequence, it follows that the minimal trellis uniquely minimizes the total number of operations required for Viterbi decoding of a given code. Moreover, we show that these results extend to the general class of rectangular codes (namely, the class of codes that admit a biproper trellis presentation), which includes all group codes and many other useful nonlinear codes.

The problem of minimizing the vertex count at a given time index in the trellis for a general (nonlinear) code is shown to be NP-complete. Examples are provided that show that (1) the minimal trellis for a nonlinear code may not be observable, i.e. some codewords may be represented by more than one path through the trellis and (2) minimizing the vertex count at one time index may be incompatible with minimizing the vertex count at another time index. A trellis produce is defined and used to construct trellises for sum codes. Minimal trellises for linear codes are obtained by forming the product of elementary trellises corresponding to the one-dimensional subcodes generated by atomic codewords. The structure of the resulting trellis is determined solely by the spans of the atomic codewords. A correspondence between minimal linear block code trellises and configurations of nonattacking rooks on a triangular chess board is established and used to show that the number of distinct minimal linear block code trellises is a Stirling number of the second kind. Various bounds on trellis size are reinterpreted in this context.

Multidimensional constellation shaping with a family of regions called truncated polydiscs is studied. This family achieves maximum shaping gain for a given two-dimensional peak-to-average energy ratio or a given two-dimensional constellation expansion ratio. An efficient algorithm for mapping data words to constellation points is described that requires O(N log N) arithmetic operations and O(N/sup 2/) lookup table space. Truncated polydisc shaping can easily be incorporated into standard coded modulation schemes.>

Variable-rate data transmission schemes in which constellation points are selected according to a nonuniform probability distribution are studied. When the criterion is one of minimizing the average transmitted energy for a given average bit rate, the best possible distribution with which to select constellations points is a Maxwell-Boltzmann distribution. In principle, when constellation points are selected according to a Maxwell-Boltzmann distribution, the ultimate shaping gain ( pi e/6 or 1.53 dB) can be achieved in any dimension. Nonuniform signaling schemes can be designed by mapping simple variable-length prefix codes onto the constellation. Using the Huffman procedure, prefix codes can be designed that approach the optimal performance. These schemes provide a fixed-rate primary channel and a variable-rate secondary channel, and are easily incorporated into standard lattice-type coded modulation schemes.>

Tables of good ternary and quaternary codes are presented, and they are used in the construction of dense sphere packings. Results include (1) tables of the best ternary and quaternary constacyclic codes (including cyclic codes) up to block length 50; (2) a class of optimal (n, 2) codes over GF(q); (3) the (u+v+w mod 2u+v mod u) construction, a new ternary code construction technique that can be used to construct the ternary Reed-Muller codes (and others); and (4) tables of linear ternary and quaternary codes obtained by modifying and combining various codes here and in the literature. Packings are generated in even dimensions up to 100 using these codes and a sphere-packing construction. In dimensions 36 and 60, new record densities appear to have been achieved.>

Construction of efficient block-encoded M-ary phase-shift-keying (M-PSK) schemes is investigated. An algebraic approach is adopted in which the basic modulation signals are associated with the elements of a finite group. Using some of the properties of group partition chains, the algebraic properties of the linear codes are studied. From this analysis, a class of codes called blocked coset codes is obtained. Distance properties of the block coset codes are obtained in terms of the distance properties of the underlying group partition chain. A particular choice of coset representations yields the standard block coset code construction, which is applicable to M-PSK for M of the form 2/sup k/*3/sup l/. The standard block coset code construction is seen to be equivalent to block code constructions previously reported in the literature, and it is modified to account for the fact that the 4-PSK constellation forms a Hamming space. The modification results in substantial improvements in some cases. A table of some examples of 2/sup k/*3/sup l/ PSK block coset codes is included.>

An access rule for token ring local-area networks called the helical-window token-ring protocol is introduced. It features the use of a window that limits the allowable messages a token-holding station can send. With the window, the operation of the protocol approaches that of a central single-server queuing system in the sense that messages are delivered in near first-come-first-served order on a network-wide basis. The introduction of the window also makes analysis of the networks tractable. Exact analytical formulas for the capacity and for the mean, variance, and moment-generating function of the message waiting time are derived. Numerical simulation is used to verify the results. Comparisons with continuous polling systems show that the imposition of the windowed access rule can lead to significant reductions in the delay variance (at the cost of increasing the mean system time) when the traffic is heavy and/or the message transmission time is large with respect to the walk time of the ring.>