We introduce finite-precision encoding and decoding methods for energy-based direct arithmetic coding (AC), a newly coined technique that enables fixed-to-fixed invertible distribution matching (DM) in probabilistic amplitude shaping (PAS) systems and approaching the sphere shaping gain. Moreover, we introduce novel methods for determining calibration guarantees to account for computational precision loss due to the finite-precision nature of encoding and decoding, and present methods of finite-precision approximation for estimating key energy-based quantities. As we shall present, our methods enable efficient implementations with a negligible degradation due to the finite-precision computations, thus readily establishing a pragmatic approach to energy-efficient communication from a practical standpoint.

We consider probabilistic amplitude shaping (PAS) of quadrature amplitude modulation (QAM) constellations. Our investigation stems from a consideration of practically achieving optimal shaping gain with very low complexity. In this paper we introduce two new energy-based arithmetic coding (AC) methods, respectively termed direct AC method and constellation selection AC method. Our methods allow for performing fixed-to-fixed and invertible distribution matching (DM) for PAS and are capable of approaching the sphere shaping gain, thereby offering a featured solution to energy-efficient transmission.

We consider approximation of N(n, E) and Nc(n, E), the number of sequences of ASK symbols of length n with energy equal to E and at most equal to E, respectively. These quantities are often encountered in the context of constellation shaping, such as in shell mapping. We provide implementation techniques for our approximation methods. Numerical evaluation shows that approximations based on the techniques are extremely tight even at lengths as short as 16. Our presented approximation formulas for such quantities, theoretically justified, in conjunction with the implementation techniques, establish a new directional and theoretical foundation that can be applied to applications such as probabilistic shaping.

We introduce a technique for the analysis of general spatially coupled systems that are governed by scalar recursions. Such systems can be expressed in variational form in terms of a potential function. We show, under mild conditions, that the potential function is displacement convex and that the minimizers are given by the fixed points (FPs) of the recursions. Furthermore, we give the conditions on the system such that the minimizing FP is unique up to translation along the spatial direction. The condition matches with that of Kudekar et al.[20] for the existence of spatial FPs. Displacement convexity applies to a wide range of spatially coupled recursions appearing in coding theory, compressive sensing, random constraint satisfaction problems, as well as statistical-mechanics models. We illustrate it with applications to low-density parity-check (LDPC) and generalized LDPC codes used for the transmission on the binary erasure channel or general binary memoryless symmetric channels within the Gaussian reciprocal channel approximation as well as compressive sensing.

A liquid system provides durable object storage based on spreading redundantly generated data across a network of hundreds to thousands of potentially unreliable storage nodes. A liquid system uses a combination of a large code , lazy repair , and flow storage organization . We show that a liquid system can be operated to enable flexible and essentially optimal combinations of storage durability, storage overhead, repair bandwidth usage, and access performance.

We consider the effect of log-likelihood ratio saturation on the belief-propagation decoding of low-density parity-check codes. Saturation is commonly done in practice and is known to have a significant effect on the error-floor performance. Our focus is on threshold analysis and the stability of density evolution. We analyze the decoder for standard low-density parity-check code ensembles and show that belief-propagation decoding generally degrades gracefully with saturation. Stability of density evolution is, on the other hand, rather strongly affected by saturation, and the asymptotic qualitative effect of saturation is similar to reduction by one of variable-node degree. We also describe conditions under which the block-error threshold for saturated belief-propagation decoding equals the bit-error threshold.

We study the problem of distributed time and frequency synchronization for device-to-device communication in LTE [1]. LTE is an OFDMA system that crucially uses tight time and frequency synchronization between UEs and the base station for intracell and intercell interference coordination. For consistency with the cyclic prefix length and tone spacing used in LTE, we target an accuracy of a few microseconds for time synchronization and 150 Hz for frequency synchronization. We examine the problem both from a link and a system-level perspective. Link-level challenges involve designing a synchronization signal for computationally and energy efficient receiver algorithms, and system-level challenges involve achieving consistent timing using a distributed algorithm while leveraging the multiuser aspect of the problem to improve performance.

We establish the existence of wave-like solutions to spatially coupled graphical models which, in the large size limit, can be characterized by a 1-D real-valued state. This is extended to a proof of the threshold saturation phenomenon for all such models, which includes spatially coupled irregular low-density parity-check codes over the binary erasure channel (BEC), but also addresses hard-decision decoding for transmission over general channels, the code division multiple access problem, compressed sensing, and some statistical physics models. For traditional uncoupled iterative coding systems with two components and transmission over the BEC, the asymptotic convergence behavior is completely characterized by the EXIT curves of the components. In particular, the system converges to the desired fixed point, which is the one corresponding to perfect decoding, if and only if the two EXIT functions describing the components do not cross. For spatially coupled systems whose state is 1-D a closely related graphical criterion applies. Now the curves are allowed to cross, but not by too much. More precisely, we show that the threshold saturation phenomenon is related to the positivity of the (signed) area enclosed by two EXIT-like functions associated to the component systems, a very intuitive, and easy-to-use graphical characterization. In the spirit of EXIT functions and Gaussian approximations, we also show how to apply the technique to higher dimensional and even infinite-dimensional cases. In these scenarios, the method is no longer rigorous, but it typically gives accurate predictions. To demonstrate this application, we discuss transmission over general channels using both the belief-propagation as well as the min-sum decoder.

Potential functionals have been introduced recently as an important tool for the analysis of coupled scalar systems (e.g. density evolution equations). In this contribution we investigate interesting properties of this potential. Using the tool of displacement convexity we show that, under mild assumptions on the system, the potential functional is displacement convex. Furthermore, we give the conditions on the system such that the potential is strictly displacement convex in which case the minimizer is unique.

We consider the effect of LLR saturation on belief propagation decoding of low-density parity-check codes. Saturation is commonly done in practice and is known to have a significant effect on error floor performance. Our focus is on threshold analysis and the stability of density evolution. We analyze the decoder for certain low-density parity-check code ensembles and show that belief propagation decoding generally degrades gracefully with saturation. Stability of density evolution is, on the other hand, rather strongly affected by saturation and the asymptotic qualitative effect of saturation is similar to reduction of variable node degree by one.

We investigate spatially coupled code ensembles. For transmission over the binary erasure channel, it was recently shown that spatial coupling increases the belief propagation threshold of the ensemble to essentially the maximum a priori threshold of the underlying component ensemble. This explains why convolutional LDPC ensembles, originally introduced by Felström and Zigangirov, perform so well over this channel. We show that the equivalent result holds true for transmission over general binary-input memoryless output-symmetric channels. More precisely, given a desired error probability and a gap to capacity, we can construct a spatially coupled ensemble that fulfills these constraints universally on this class of channels under belief propagation decoding. In fact, most codes in this ensemble have this property. The quantifier universal refers to the single ensemble/code that is good for all channels but we assume that the channel is known at the receiver. The key technical result is a proof that, under belief-propagation decoding, spatially coupled ensembles achieve essentially the area threshold of the underlying uncoupled ensemble. We conclude by discussing some interesting open problems.

This paper proposes FlashLinQ-a synchronous peer-to-peer wireless PHY/MAC network architecture. FlashLinQ leverages the fine-grained parallel channel access offered by OFDM and incorporates an analog energy-level-based signaling scheme that enables signal-to-interference ratio (SIR)-based distributed scheduling. This new signaling mechanism, and the concomitant scheduling algorithm, enables efficient channel-aware spatial resource allocation, leading to significant gains over a CSMA/CA system using RTS/CTS. FlashLinQ is a complete system architecture including: 1) timing and frequency synchronization derived from cellular spectrum; 2) peer discovery; 3) link management; and 4) channel-aware distributed power, data rate, and link scheduling. FlashLinQ has been implemented for operation over licensed spectrum on a digital signal processor/field-programmable gate array (DSP/FPGA) platform. In this paper, we present FlashLinQ performance results derived from both measurements and simulations.

We investigate spatially coupled code ensembles. For transmission over the binary erasure channel, it was recently shown that spatial coupling increases the belief propagation threshold of the ensemble to essentially the maximum a-priori threshold of the underlying component ensemble. This explains why convolutional LDPC ensembles, originally introduced by Felström and Zigangirov, perform so well over this channel. We show that the equivalent result holds true for transmission over general binary-input memoryless output-symmetric channels. More precisely, given a desired error probability and a gap to capacity, we can construct a spatially coupled ensemble which fulfills these constraints universally on this class of channels under belief propagation decoding. In fact, most codes in that ensemble have that property. The quantifier universal refers to the single ensemble/code which is good for all channels if we assume that the channel is known at the receiver. The key technical result is a proof that under belief propagation decoding spatially coupled ensembles achieve essentially the area threshold of the underlying uncoupled ensemble. We conclude by discussing some interesting open problems.

In the analysis of iterative coding systems it is often necessary to compare two densities and to measure how close they are. Sometimes it is convenient to compare their entropy or their Battacharyya parameter. But sometimes a more powerful measure is required. The Wasserstein metric is a convenient choice. We derive some basic properties of the Wasserstein metric which are important in the context of iterative coding. In particular, we will see how the Wasserstein metric compares to some other natural measures (such as the difference of entropies or Battacharyya parameters) and how the Wasserstein metric behaves under “natural” operations, like variable - or check-node convolution or under convex combinations. As an “application” we show how to prove the existence of the belief propagation Generalized EXIT curve for a non-trivial portion of the parameters.

Recent deployments of data-rich smart phones has provided a fresh impetus for designing, deploying and understanding the performance of wide area ad-hoc networks. The most popular medium access mechanism for such ad hoc networks is CSMA/CA with RTS/CTS. In this paper, using tools from stochastic geometry, we study and optimize the throughput performance of such networks. We show that in ad-hoc networks enabled with SIR based scheduling, a simple modification to the transmit power level - setting it to be inversely proportional to the square root of the link gain - leads to large improvements in network throughput. This simple power-level selection is optimal over the class of all ”local” transmit power selection strategies when channels are stationary, and further is at most a factor of two away from optimality in the fading case. Using stochastic geometric techniques, we also provide analytical expressions for the medium access probability in different scenarios.

Convolutional low-density parity-check (LDPC) ensembles, introduced by Felström and Zigangirov, have excellent thresholds and these thresholds are rapidly increasing functions of the average degree. Several variations on the basic theme have been proposed to date, all of which share the good performance characteristics of convolutional LDPC ensembles. We describe the fundamental mechanism that explains why “convolutional-like” or “spatially coupled” codes perform so well. In essence, the spatial coupling of individual codes increases the belief-propagation (BP) threshold of the new ensemble to its maximum possible value, namely the maximum a posteriori (MAP) threshold of the underlying ensemble. For this reason, we call this phenomenon “threshold saturation.” This gives an entirely new way of approaching capacity. One significant advantage of this construction is that one can create capacity-approaching ensembles with an error correcting radius that is increasing in the blocklength. Although we prove the “threshold saturation” only for a specific ensemble and for the binary erasure channel (BEC), empirically the phenomenon occurs for a wide class of ensembles and channels. More generally, we conjecture that for a large range of graphical systems a similar saturation of the “dynamical” threshold occurs once individual components are coupled sufficiently strongly. This might give rise to improved algorithms and new techniques for analysis.

Convolutional LDPC ensembles, introduced by Felström and Zigangirov, have excellent thresholds and these thresholds are rapidly increasing as a function of the average degree. Several variations on the basic theme have been proposed to date, all of which share the good performance characteristics of convolutional LDPC ensembles. We describe the fundamental mechanism which explains why “convolutional-like” or “spatially coupled” codes perform so well. In essence, the spatial coupling of the individual code structure has the effect of increasing the belief-propagation (BP) threshold of the new ensemble to its maximum possible value, namely the maximum-a-posteriori (MAP) threshold of the underlying ensemble. For this reason we call this phenomenon “threshold saturation”. This gives an entirely new way of approaching capacity. One significant advantage of such a construction is that one can create capacity-approaching ensembles with an error correcting radius which is increasing in the blocklength. Our proof makes use of the area theorem of the BP-EXIT curve and the connection between the MAP and BP threshold recently pointed out by Méasson, Montanari, Richardson, and Urbanke. Although we prove the connection between the MAP and the BP threshold only for a very specific ensemble and only for the binary erasure channel, empirically the same statement holds for a wide class of ensembles and channels. More generally, we conjecture that for a large range of graphical systems a similar collapse of thresholds occurs once individual components are coupled sufficiently strongly. This might give rise to improved algorithms as well as to new techniques for analysis.

We investigate the behavior of iteratively decoded low-density parity-check (LDPC) codes over the binary erasure channel in the so-called ldquowaterfall region.rdquo We show that the performance curves in this region follow a simple scaling law. We conjecture that essentially the same scaling behavior applies in a much more general setting and we provide some empirical evidence to support this conjecture. The scaling law, together with the error floor expressions developed previously, can be used for a fast finite-length optimization.

There is a fundamental relationship between belief propagation (BP) and maximuma posterioridecoding. The case of transmission over the binary erasure channel was investigated in detail in a companion paper (C. MEacuteasson, A. Montanari, and R. Urbanke, "Maxwell's construction: The hidden bridge between iterative and maximum a posteriori decoding,"IEEE Transactions on Information Theory, submitted for publication). This paper investigates the extension to general memoryless channels (paying special attention to the binary case). An area theorem for transmission over general memoryless channels is introduced and some of its many consequences are discussed. We show that this area theorem gives rise to an upper bound on the maximuma posteriorithreshold for sparse graph codes. In situations where this bound is tight, the extrinsic soft bit estimates delivered by the BP decoder coincide with the correcta posterioriprobabilities above the maximuma posteriorithreshold. More generally, it is conjectured that the fundamental relationship between the maximuma posterioriprobability (MAP) and the BP decoder which was observed for transmission over the binary erasure channel carries over to the general case. We finally demonstrate that in order for the design rate of an ensemble to approach the capacity under BP decoding the component codes have to be perfectly matched, a statement which is well known for the special case of transmission over the binary erasure channel.

The authors correct a mathematical equation contained in the correspondence "Multiple-antenna signal constellations for fading channels," previously published in the IEEE Transactions on Information Theory

We present a novel method for superposition coding applicable to OFDM systems in which the receivers being transmitted to are one high SNR receiver and one low SNR receiver. The degradation of the high SNR receiver, however, results primarily from channel uncertainty. Thus, we consider the effect of imperfect channel estimates, a ubiquitous problem in mobile wireless, and show that the new scheme performs much better than traditional schemes in such a setting.

Density evolution for LDPC codes predicts asymptotic performance and serves as a practical design tool for designing top performing structures [1]. Many papers advocate the use of exit chart methods and other approximations, proclaiming that density evolution is computationally too intensive. In this paper we show that this is not the case: we present a highly efficient and accurate implementation of density evolution for LDPC codes.

We derive the average weight distribution function and its asymptotic growth rate for low-density parity-check (LDPC) code ensembles. We show that the growth rate of the minimum distance of LDPC codes depends only on the degree distribution pair. It turns out that capacity-achieving sequences of standard (unstructured) LDPC codes under iterative decoding over the binary erasure channel (BEC) known to date have sublinearly growing minimum distance in the block length

We show for a large class of LDPC ensembles, including RA and IRA codes, that the bit iterative decoding threshold is essentially identical to the block iterative decoding threshold

We derive further properties of EXIT and generalized EXIT curves. In particular we present an area theorem for iterative (as compared to MAP) decoding, we show how to compute upper-bounds on the MAP threshold for general channels and we apply these techniques to turbo codes

The behavior of iteratively decoded low-density parity-check (LDPC) codes over the binary erasure channel in the so-called "waterfall region" is investigated and shows that the performance curves in this region follow a very basic scaling law. This scaling law, combined with previously known expressions for the error floor, yields a promising direction for analyzing the performance of irregular LDPC codes of practical lengths.

We show that for the case of the binary-symmetric channel and Gallager's decoding algorithm A the threshold can, in many cases, be determined analytically. More precisely, we show that the threshold is always upper-bounded by the minimum of (1-/spl lambda//sub 2//spl rho/'(1))/(/spl lambda/'(1)/spl rho/'(1)-/spl lambda//sub 2//spl rho/'(1)) and the smallest positive real root /spl tau/ of a specific polynomial p(x) and we observe that for most cases this bound is tight, i.e., it determines the threshold exactly. We also present optimal degree distributions for a large range of rates. In the case of rate one-half codes, for example, the threshold x/sub 0//sup */ of the optimal degree distribution is given by x/sup *//sub 0//spl sim/0.0513663. Finally, we outline how thresholds of more complicated decoders might be determined analytically.

In this paper, we are concerned with the finite-length analysis of low-density parity-check (LDPC) codes when used over the binary erasure channel (BEC). The main result is an expression for the exact average bit and block erasure probability for a given regular ensemble of LDPC codes when decoded iteratively. We also give expressions for upper bounds on the average bit and block erasure probability for regular LDPC ensembles and the standard random ensemble under maximum-likelihood (ML) decoding. Finally, we present what we consider to be the most important open problems in this area.

In this correspondence, we show that the problem of designing efficient multiple-antenna signal constellations for fading channels can be related to the problem of finding packings with large minimum distance in the complex Grassmannian space. We describe a numerical optimization procedure for finding good packings in the complex Grassmannian space and report the best signal constellations found by this procedure. These constellations improve significantly upon previously known results.

Density evolution is an algorithm for computing the capacity of low-density parity-check (LDPC) codes under message-passing decoding. For memoryless binary-input continuous-output additive white Gaussian noise (AWGN) channels and sum-product decoders, we use a Gaussian approximation for message densities under density evolution to simplify the analysis of the decoding algorithm. We convert the infinite-dimensional problem of iteratively calculating message densities, which is needed to find the exact threshold, to a one-dimensional problem of updating the means of the Gaussian densities. This simplification not only allows us to calculate the threshold quickly and to understand the behavior of the decoder better, but also makes it easier to design good irregular LDPC codes for AWGN channels. For various regular LDPC codes we have examined, thresholds can be estimated within 0.1 dB of the exact value. For rates between 0.5 and 0.9, codes designed using the Gaussian approximation perform within 0.02 dB of the best performing codes found so far by using density evolution when the maximum variable degree is 10. We show that by using the Gaussian approximation, we can visualize the sum-product decoding algorithm. We also show that the optimization of degree distributions can be understood and done graphically using the visualization.

We design low-density parity-check (LDPC) codes that perform at rates extremely close to the Shannon capacity. The codes are built from highly irregular bipartite graphs with carefully chosen degree patterns on both sides. Our theoretical analysis of the codes is based on the work of Richardson and Urbanke (see ibid., vol.47, no.2, p.599-618, 2000). Assuming that the underlying communication channel is symmetric, we prove that the probability densities at the message nodes of the graph possess a certain symmetry. Using this symmetry property we then show that, under the assumption of no cycles, the message densities always converge as the number of iterations tends to infinity. Furthermore, we prove a stability condition which implies an upper bound on the fraction of errors that a belief-propagation decoder can correct when applied to a code induced from a bipartite graph with a given degree distribution. Our codes are found by optimizing the degree structure of the underlying graphs. We develop several strategies to perform this optimization. We also present some simulation results for the codes found which show that the performance of the codes is very close to the asymptotic theoretical bounds.

We present a general method for determining the capacity of low-density parity-check (LDPC) codes under message-passing decoding when used over any binary-input memoryless channel with discrete or continuous output alphabets. Transmitting at rates below this capacity, a randomly chosen element of the given ensemble will achieve an arbitrarily small target probability of error with a probability that approaches one exponentially fast in the length of the code. (By concatenating with an appropriate outer code one can achieve a probability of error that approaches zero exponentially fast in the length of the code with arbitrarily small loss in rate.) Conversely, transmitting at rates above this capacity the probability of error is bounded away from zero by a strictly positive constant which is independent of the length of the code and of the number of iterations performed. Our results are based on the observation that the concentration of the performance of the decoder around its average performance, as observed by Luby et al. in the case of a binary-symmetric channel and a binary message-passing algorithm, is a general phenomenon. For the particularly important case of belief-propagation decoders, we provide an effective algorithm to determine the corresponding capacity to any desired degree of accuracy. The ideas presented in this paper are broadly applicable and extensions of the general method to low-density parity-check codes over larger alphabets, turbo codes, and other concatenated coding schemes are outlined.

Low-density parity-check (LDPC) codes can be considered serious competitors to turbo codes in terms of performance and complexity and they are based on a similar philosophy: constrained random code ensembles and iterative decoding algorithms. We consider the encoding problem for LDPC codes. More generally we consider the encoding problem for codes specified by sparse parity-check matrices. We show how to exploit the sparseness of the parity-check matrix to obtain efficient encoders. For the (3,6)-regular LDPC code, for example, the complexity of encoding is essentially quadratic in the block length. However, we show that the associated coefficient can be made quite small, so that encoding codes even of length n/spl sime/100000 is still quite practical. More importantly, we show that "optimized" codes actually admit linear time encoding.

We propose a systematic method for creating constellations of unitary space-time signals for multiple-antenna communication links. Unitary space-time signals, which are orthonormal in time across the antennas, have been shown to be well-tailored to a Rayleigh fading channel where neither the transmitter nor the receiver knows the fading coefficients. The signals can achieve low probability of error by exploiting multiple-antenna diversity. Because the fading coefficients are not known, the criterion for creating and evaluating the constellation is nonstandard and differs markedly from the familiar maximum-Euclidean-distance norm. Our construction begins with the first signal in the constellation-an oblong complex-valued matrix whose columns are orthonormal-and systematically produces the remaining signals by successively rotating this signal in a high-dimensional complex space. This construction easily produces large constellations of high-dimensional signals. We demonstrate its efficacy through examples involving one, two, and three transmitter antennas.

The spectacular performance offered by turbo codes sparked intense interest in them. A considerable amount of research has simplified, formalized, and extended the ideas inherent in the original turbo code construction. Nevertheless, the nature of the relatively simple ad hoc turbo-decoding algorithm has remained something of a mystery. We present a geometric interpretation of the turbo-decoding algorithm. The geometric perspective clearly indicates the relationship between turbo-decoding and maximum-likelihood decoding. Analysis of the geometry leads to new results concerning existence of fixed points, conditions for uniqueness, conditions for stability, and proximity to maximum-likelihood decoding.

A planar shape distorted by a projective viewing transformation can be recognized under partial occlusion if an invariant description of its boundary is available. Research in this area has provided a theory for invariant boundary descriptions based on an interplay of differential, local, and global invariants. Differential invariants require high-order derivatives. The use of global invariants and point matches on the distorting transformations enables one to reduce the order. Trade-offs between the highest order derivatives required and the quantity of additional information constraining the distorting viewing transformations are made explicit.>