The Poltyrev bound provides a very tight upper bound on the decoding error probability when using binary linear codes for transmission over the binary symmetric channel and the additive white Gaussian noise channel, making use of the code's weight spectrum. In the present work, the bound is extended to symmetric binary-input memoryless channels with a discrete output alphabet. The derived bound is demonstrated on a hybrid BSC-BEC channel. Additionally, a reduced-complexity bound is introduced at the cost of some loss in tightness.

We propose a novel transmission scheme for ultra-reliable multi-hop multiple-antenna communication where relays perform only universal linear operations on the received signals. In particular, the operations are channel-oblivious, and no detection takes place in intermediate relaying nodes. The processing at each relay may be viewed as a concatenation of a dimension-reduction operation, i.e., a universal combining, and orthogonal space-time block coding, i.e., a universal transmission operation. It is demonstrated that the developed transmission-combining relaying technique guarantees reliable communication in a very strong sense: so long as all relay-to-relay links have a non-vanishing capacity, reliable communication is possible. The proposed schemes are derived by establishing a certain operational equivalence relationship between the true channel and an associated multiple-input single-output channel.

It has been known for a long time that the mutual information between the input sequence and output sequence of a binary symmetric channel (BSC) is upper bounded by the mutual information between the same input sequence and the output sequence of a binary erasure channel (BEC) with the same capacity. Recently, Samorodnitsky discovered that one may also lower bound the BSC mutual information in terms of the mutual information between the same input sequence and a more capable BEC. In this paper, we strengthen Samorodnitsky's bound for the special case where the input to the channel is distributed uniformly over a linear code. Furthermore, for a general (not necessarily binary) input distribution$P_{X}$and channel$W_{Y\vert X}$, we derive a new lower bound on the mutual information$I(X;Y^{n})$for$n$transmissions of$X\sim P_{X}$through the channel$W_{Y\vert X}$.

It is well known that independent (separate) encoding of$K$correlated sources may incur some rate loss compared to joint encoding, even if the decoding is done jointly. This loss is particularly evident in the multiple descriptions problem, where it is the same source that is encoded in each description. We observe that under mild conditions about the source and distortion measure, the sum-rate of$K$separately encoded individually good descriptions tends to the rate-distortion function of the joint decoder in the limit of vanishing small coding rates of the descriptions. Moreover, we then propose to successively encode the source into$K$independent descriptions in each round in order to achieve a final distortion$D$after$M$rounds. We provide two examples – a Gaussian source with mean-squared error and an exponential source with one-sided error – for which the excess rate vanishes in the limit as the number of rounds$M$goes to infinity, for any fixed$D$and$K$. This result has an interesting interpretation for a multi-round variant of the multiple descriptions problem, where after each round the encoder gets a (block) feedback regarding which of the descriptions arrived: In the limit as the number of rounds$M$goes to infinity (i.e., many incremental rounds), the total rate of received descriptions approaches the rate-distortion function. We provide theoretical and experimental evidence showing that this phenomenon is in fact more general than in the two examples above.

This work addresses general multiple-input multiple-output systems and develops combined diversity transmission and combining schemes that achieve rate one and full diversity with reduced decoding complexity, while being universal in the sense that the operations performed at both transmission ends are channel independent. Such schemes may be useful in a scenario where a multiple-antenna source node communicates with the cloud via a multiple-antenna "dumb relay" that forwards the received vector over a rate-constrained digital front-haul link or serves as relay performing an amplify-forward operation over the air. The proposed schemes are derived by establishing an operational equivalence relation between the true channel and an associated multiple-input single-output channel.

Motivated by multiple-description source coding with feedback, it was recently proposed to encode the one-sided exponential source$X$via$K$parallel channels,$Y_{1}, \ldots, Y_{K}$, such that the error signals$X-Y_{i}, i=1, \ldots, K$, are one-sided exponential and mutually independent given$X$. Moreover, it was shown that the optimal estimator$\hat{Y}$of the source$X$with respect to the one-sided error criterion, is simply given by the maximum of the outputs, i.e.,$\hat{Y}=\max\{Y_{1},\ldots, Y_{K}\}$. In this paper, we show that the distribution of the resulting estimation error$X-\hat{Y}$, is equivalent to that of the optimum noise in the backward test-channel of the one-sided exponential source, i.e., it is one-sided exponentially distributed and statistically independent of the joint output$Y_{1}, \ldots, Y_{K}$.

Precoded integer-forcing equalization is a low-complexity transmission and reception scheme, primarily designed for open-loop communication. The data is encoded into independent streams, all using the same linear code, after which linear precoding is applied, while integer-forcing equalization is applied at the receiver side. Previous works have established that this architecture achieves channel capacity up to a finite gap for general multiple-input multiple-output Gaussian channels, as well as obtained tighter bounds for the special case of diagonal (parallel) channels. The present work provides a precise performance characterization when integer-forcing equalization is applied to two parallel channels and where precoding is done using the full-diversity rotation matrix cyclo2. It is shown that this scheme achieves capacity up to a gap bounded by$\log _{2}({\scriptstyle ^{\scriptstyle 9}}\hspace {-0.224em}/\hspace {-0.112em}{\scriptstyle 5})$bits per complex channel use when the standard integer-forcing receiver is used, and the gap is reduced to$\log _{2}({\scriptstyle ^{\scriptstyle 5}}\hspace {-0.224em}/\hspace {-0.112em}{\scriptstyle 4})$bits per complex channel use when its successive decoding variant is applied. In addition, a full characterization of the basis transformation matrices used by the integer-forcing receiver is derived. These turn out to consist only of Fibonacci numbers and are explicitly determined as a function of the condition number. The results obtained are also highly relevant to lattice-reduction detection schemes.

In this paper, we consider the rate-distortion problem where a source X is encoded into k parallel descriptions Y1, . . ., Yk, such that the error signals X - Yi, i = 1, . . ., k, are mutually independent given X. We show that if X is one-sided exponentially distributed, the optimal decoder (estimator) under the one-sided absolute error criterion, is simply given by the maximum of the outputs Y1, . . ., Yk. We provide a closed-form expression for the rate and distortion for any k number of parallel descriptions and for any coding rate. We furthermore show that as the coding rate per description becomes asymptotically small, encoding into k parallel descriptions and using the maximum output as the source estimate, is rate-distortion optimal.

Wireless cellular communication networks are bandwidth and interference limited. An important means to overcome these resource limitations is the use of multiple antennas. Base stations equipped with a very large (massive) number of antennas have been the focus of recent research. A bottleneck in such systems is the cost of a large number of transmit/receive chains requiring ADCs, low noise amplifiers and power amplifiers. The present work considers a line-of-sight channel model. It is shown that given a sufficiently large antenna array, it suffices that the number of transmit/receive chains exceeds the number of desired users by one in order to reduce the interference to any desired level by judiciously selecting the antenna elements.

Integer-forcing source coding has been proposed as a low-complexity method for compression of distributed correlated Gaussian sources. In this scheme, each encoder quantizes its observation using the same fine lattice and reduces the result modulo a coarse lattice. Rather than directly recovering the individual quantized signals, the decoder first recovers a full-rank set of judiciously chosen integer linear combinations of the quantized signals, and then inverts it. It has been observed that the method works very well for “most” but not all source covariance matrices. The present work quantifies the measure of bad covariance matrices by studying the probability that integer-forcing source coding fails as a function of the allocated rate, where the probability is with respect to a random orthonormal transformation that is applied to the sources prior to quantization. For the important case where the signals to be compressed correspond to the antenna inputs of relays in an i.i.d. Rayleigh fading environment, this orthonormal transformation can be viewed as being performed by nature. The scheme is also studied in the context of a non-distributed system. Here, the goal is to arrive at a universal, yet practical, compression method using equal-rate quantizers with provable performance guarantees. The scheme is universal in the sense that the covariance matrix need only be learned at the decoder but not at the encoder. The goal is accomplished by replacing the random orthonormal transformation by transformations corresponding to number-theoretic space-time codes.

Communication over the i.i.d. Rayleigh slow-fading MAC is considered, where all terminals are equipped with a single antenna. Further, a communication protocol is considered where all users transmit at (just below) the symmetric capacity (per user) of the channel, a rate which is fed back (dictated) to the users by the base station. Tight bounds are established on the distribution of the rate attained by the protocol. In particular, these bounds characterize the probability that the dominant face of the MAC capacity region contains a symmetric rate point, i.e., that the considered protocol strictly attains the sum capacity of the channel. The analysis provides a non-asymptotic counterpart to the diversity-multiplexing tradeoff of the multiple access channel. We then extend this analysis to general multiple-input multiple-output MAC and finally, a practical scheme based on integer-forcing and space-time precoding is shown to be an effective coding architecture for this communication scenario.

The maximal correlation coefficient is a well-established generalization of the Pearson correlation coefficient for measuring non-linear dependence between random variables. It is appealing from a theoretical standpoint, satisfying Rényi's axioms for measures of dependence. It is also attractive from a computational point of view due to the celebrated alternating conditional expectation algorithm, allowing to compute its empirical version directly from observed data. Nevertheless, from the outset, it was recognized that the maximal correlation coefficient suffers from some fundamental deficiencies, limiting its usefulness as an indicator of estimation quality. Another well-known measure of dependence is the correlation ratio but it too suffers from some drawbacks. Specifically, the maximal correlation coefficient equals one too easily whereas the correlation ratio equals zero too easily. The present work recounts some attempts that have been made in the past to alter the definition of the maximal correlation coefficient in order to overcome its weaknesses and then proceeds to suggest a natural variant of the maximal correlation coefficient. The proposed dependence measure at the same time resolves the major weakness of the correlation ratio measure and may be viewed as a bridge between the two classical measures.

It is shown that a receiver equipped with two antennas may null an arbitrary large number of spatial directions to any desired level, while maintaining the interference-free signal-to-noise ratio, by judiciously adjusting the distance between the antenna elements. The main theoretical result builds on ergodic theory. The practicality of the scheme for systems operating at a moderate signal-to-noise ratio is demonstrated for a scenario where each transmitter is equipped with a single antenna and each receiver has two antenna elements, the separation of which can be arbitrarily set. As an example, for a five-user planar line-of-sight interference channel, with the directions of users being uniformly distributed, at a signal-to-noise ratio of 10 dB, a near interference-free average transmission rate is achievable. This amounts to roughly doubling the average rate attained by non-naive time-division multiple access.

Receiver diversity combining methods play a key role in combating the detrimental effects of fading in wireless communication and other applications. A novel diversity combining method is proposed, where a universal, i.e., channel independent, orthogonal dimension-reducing space-time transformation is applied prior to quantization of the signals. The scheme may be considered as the counterpart of Alamouti modulation, and more generally of orthogonal space-time block codes.

Sampling above the Nyquist rate is at the heart of sigma-delta modulation, where the increase in sampling rate is translated to a reduction in the overall (mean-squared-error) reconstruction distortion. This is attained by using a feedback filter at the encoder, in conjunction with a low-pass filter at the decoder. The goal of this paper is to characterize the optimal trade-off between the per-sample quantization rate and the resulting mean-squared-error distortion under various restrictions on the feedback filter. To this end, we establish a duality relation between the performance of sigma-delta modulation and the performance of differential pulse-code modulation when applied to (discrete-time) band-limited inputs. As the optimal trade-off for the latter scheme is fully understood, the full characterization for sigma-delta modulation, as well as the optimal feedback filters, immediately follows.

Receiver diversity combining methods play a key role in combating the detrimental effects of fading in wireless communication and other applications. Commonly used linear diversity combining methods include maximal-ratio combining, equal-gain combining and antenna selection. A novel linear combining method is proposed where a universal, i.e., channel independent, orthogonal dimension-reducing space-time transformation is applied prior to quantization of the signals. The scheme may be considered as the counterpart of Alamouti modulation, and more generally of orthogonal space-time block codes.

Communication over the i.i.d. Rayleigh slow-fading MAC is considered, where all terminals are equipped with a single antenna. Further, a communication protocol is considered where all users transmit at (just below) the symmetric capacity (per user) of the channel, a rate which is fed back (dictated) to the users by the base station. Tight bounds are established on the distribution of the rate attained by the protocol. In particular, these bounds characterize the probability that the dominant face of the MAC capacity region contains a symmetric rate point, i.e., that the considered protocol strictly attains the sum capacity of the channel. The analysis provides a non-asymptotic counterpart to the diversity-multiplexing tradeoff of the multiple access channel. Finally, a practical scheme based on integer-forcing and space-time precoding is shown to be an effective coding architecture for this communication scenario.

Constellation shaping is necessary to approach channel capacity for information rates above 1 bit/dim. Probabilistic shaping shows a small gap to capacity, however a complex distribution matcher is required to modify the source distribution. Spherical shaping of lattice constellations also reduces the gap to capacity, but practical Voronoi shaping is feasible in small dimensions only. In this paper, our codebook is a real geometrically non-uniform Gaussian-like constellation. We prove that this discrete codebook achieves channel capacity when the number of points goes to infinity. Then we build a special mapping to interface between non-binary low-density codes and the codebook, allowing the code alphabet size to be equal to the square root of the codebook size. Excellent performance is shown with fast-encoding and practical iterative probabilistic decoding, e.g. 0.7 dB gap to capacity at 6 bits/s/Hz with a code defined over the ring Z/8Z.

Integer forcing is an equalization scheme for the multiple-input multiple-output communication channel that has been demonstrated to allow operating close to capacity for “most” channels. In this paper, the measure of “bad” channels is quantified by considering a compound channel setting, where the transmitter communicates over a fixed channel but knows only its mutual information. The transmitter encodes the data into independent streams, all taken from the same linear code. The coded streams are transmitted after applying a unitary transformation. At the receiver side, integer-forcing equalization is applied, followed by standard single-stream decoding. Considering pre-processing matrices drawn from a random ensemble, outage corresponds to the event that the target rate exceeds the achievable rate of integer forcing for a given channel matrix. For the case of the circular unitary ensemble, an explicit universal bound on the outage probability for a given target rate is derived that holds for any channel in the compound class. The derived bound depends only on the gap-to-capacity and the number of transmit antennas. The results are also applied to obtain universal bounds on the gap-to-capacity of multiple-antenna closed-loop multicast, achievable via linear pre-processed integer forcing.

Upper bounds on the error probability of channel coding are derived for codebooks drawn from random codebook ensembles with various independence and symmetry assumptions. For regular decoding (without an erasure option), the random coding union bound of Polyanskiy et al. is improved by carefully taking ties (equal likelihood scores) into account. It is shown that the improved bound is always better than threshold-decoding based bounds. The framework is extended to the case of decoding with an erasure option, deriving several achievability bounds in the same spirit. In order to exemplify the merits of the approach, the bounds are evaluated for the case of pairwise-independent uniformly-distributed ensembles (e.g., shifted random linear codes).

The performance of integer-forcing equalization for communication over the compound multiple-input multiple-output channel is investigated. An upper bound on the resulting outage probability as a function of the gap to capacity has been derived previously, assuming a random precoding matrix drawn from the circular unitary ensemble is applied prior to transmission. In the present work a simple and explicit lower bound on the worst-case outage probability is derived for the case of a system with two transmit antennas and two or more receive antennas, leveraging the properties of the Jacobi ensemble. The derived lower bound is also extended to random space-time precoding, and may serve as a useful benchmark for assessing the relative merits of various algebraic space-time precoding schemes.

Integer-forcing source coding has been proposed as a low complexity method for compression of distributed correlated Gaussian sources. In this scheme, each encoder quantizes its observation using the same fine lattice and reduces the result modulo the coarse lattice. Rather than directly recovering the individual quantized signals, the decoder first recovers a full-rank set of judiciously chosen integer linear combinations of the quantized signals, and then inverts it. It has been observed that the method works very well for “most” but not all source covariance matrices. The present work quantifies the measure of bad covariance matrices by studying the probability that integer forcing source coding fails as a function of the rate allocated in excess of the Berger-Tung benchmark, where the probability is with respect to a random orthogonal transformation that is applied to the sources prior to quantization. For the important case where the signals to be compressed correspond to the antenna inputs of relays in an i.i.d. Rayleigh fading environment, this orthogonal transformation can be viewed as if it is performed by nature. Hence, the results provide performance guarantees for distributed source coding via integer forcing in this scenario.

In this paper, we obtain an improved lower bound on the error exponent of the memoryless multiple-access channel via the use of linear codes, thus demonstrating that structure can be beneficial even when capacity may be achieved via random codes. We show that if the multiple-access channel is additive over a finite field, then any error probability, and hence any error exponent, achievable by a linear code for the associated single-user channel, is also achievable for the multiple-access channel. In particular, linear codes allow to attain joint expurgation, and hence, attain the single-user expurgated exponent of the single-user channel, whenever the latter is achieved by a uniform distribution. Thus, for additive channels, at low rates, where expurgation is needed, our approach strictly improves performance over previous results, where expurgation was used for at most one of the users. Even when the multiple-access channel is not additive, it may be transformed into such a channel. While the transformation is information-lossy, we show that the distributed structure gain in some “nearly additive” cases outweighs the loss. Finally, we apply a similar approach to the Gaussian multiple-access channel. While we believe that due to the power constraints, it is impossible to attain the singleuser error exponent, we do obtain an improvement over the best known achievable error exponent, given by Gallager, for certain parameters. This is accomplished using a nested lattice triplet with judiciously chosen parameters.

In the scalar dirty multiple-access channel, in addition to Gaussian noise, two additive interference signals are present, each known non-causally to a single transmitter. It was shown by Philosof et al. that for strong interferences, an independent identically distributed ensemble of codes does not achieve the capacity region. Rather, a structured-codes approach was presented that was shown to be optimal in the limit of high signal-to-noise ratios, where the sum capacity is dictated by the minimal (“bottleneck”) channel gain. In this paper, we consider the multiple-input multiple-output (MIMO) variant of this setting. In order to incorporate structured codes in this case, one can utilize matrix decompositions that transform the channel into effective parallel scalar dirty multiple-access channels. This approach, however, suffers from a “bottleneck” effect for each effective scalar channel and, therefore, the achievable rates strongly depend on the chosen decomposition. It is shown that a recently proposed decomposition, where the diagonals of the effective channel matrices are equal up to a scaling factor, is optimal at high signal-to-noise ratios, under an equal rank assumption. This approach is then extended to any number of transmitters. Finally, an application to physical-layer network coding for the MIMO two-way relay channel is presented.

Integer forcing is an equalization scheme for the multiple-input multiple-output communication channel that is applicable when all data streams are encoded using a common linear code. The scheme has been demonstrated to allow operating close to capacity for “most” channel matrices. In this work, the measure of “bad” channels is quantified by considering the outage probability of integer forcing, where random unitary precoding is applied at the transmitter side, and where the transmitter only knows the mutual information of the channel.

In the scalar dirty multiple-access channel, in addition to Gaussian noise, two additive interference signals are present, each known non-causally to a single transmitter. It was shown by Philosof et al. that for strong interferences, an i.i.d. ensemble of codes does not achieve the capacity region. Rather, a structured-codes approach was presented, which was shown to be optimal in the limit of high signal-to-noise ratios (SNRs), where the sum-capacity is dictated by the minimal (“bottleneck”) channel gain. In the present work, we consider the multiple-input multiple-output (MIMO) variant of this setting. In order to incorporate structured codes in this case, one can utilize matrix decompositions, which transform the channel into effective parallel scalar dirty multiple-access channels. This approach however suffers from a “bottleneck” effect for each effective scalar channel and therefore the achievable rates strongly depend on the chosen decomposition. It is shown that a recently proposed decomposition, where the diagonals of the effective channel matrices are equal up to a scaling factor, is optimal at high SNRs, under an equal rank assumption.

A framework is developed for decode-and-forward-based relaying using standard coding and decoding that are good for the single-input single-output (SISO) additive white Gaussian noise channel. The framework is applicable to various scenarios and is demonstrated for several important cases. Each of these scenarios is transformed into an equivalent Gaussian multiple-input multiple-output (MIMO) common-message broadcast problem, which proves useful even when all links are SISO ones. Over the effective MIMO broadcast channel, a recently developed Gaussian MIMO common-message broadcast scheme is applied. This scheme transforms the MIMO links into a set of parallel SISO channels with no loss of mutual information, using linear pre- and post-processing combined with successive decoding. Over these resulting SISO channels, off-the-shelf scalar codes may be used.

This paper provides a simplified proof for the existence of nested lattice codebooks allowing to achieve the capacity of the additive white Gaussian noise channel, as well as the optimal rate-distortion tradeoff for a Gaussian source. The proof is self-contained and relies only on basic probabilistic and geometrical arguments. An ensemble of nested lattices that is different, and more elementary, than the one used in the previous proofs is introduced. This ensemble is based on lifting different subcodes of a linear code to the Euclidean space using Construction A. In addition to being simpler, the analysis is less sensitive to the assumption that the additive noise is Gaussian. In particular, for additive ergodic noise channels, it is shown that the achievable rates of the nested lattice coding scheme depend on the noise distribution only via its power. Similarly, the nested lattice source coding scheme attains the same rate-distortion tradeoff for all ergodic sources with the same second moment.

A long-standing question in coding theory is whether code ensembles having a low-density parity check (LDPC) matrix can attain capacity under belief propagation (BP) decoding. An affirmative answer to this problem was recently given by the special class of spatially-coupled LDPC code ensemble. In this work, we provide a simple derivation of a different LDPC code ensemble that approaches capacity under BP decoding, following the classical approach of serial concatenation. This LDPC code ensemble is constructed by concatenating a high-rate outer LDPC code with an inner random convolutional one. The analysis of the concatenated-coding framework takes a particularly simple - “black box” - form. Specifically, the joint effect of the particular inner code and the binary-input memoryless output-symmetric (BMS) channel is encapsulated in a single parameter - the Bhattacharyya parameter, which is maximal for the binary symmetric channel (BSC). This implies that an inner convolutional code designed for the BSC achieves good performance over all BMS channels with a given capacity. Moreover, the performance guarantee of the outer LDPC code under BP decoding is dictated solely by this parameter. This, in turn, implies that the overall concatenated code approaches capacity under BP decoding for all BMS channels with a given capacity, simultaneously.

Sampling above the Nyquist-rate is at the heart of sigma-delta modulation, where the increase in sampling rate is translated to a reduction in the overall (minimum mean-squared-error) reconstruction distortion. This is attained by using a feedback filter at the encoder, in conjunction with a low-pass filter at the decoder. The goal of this work is to characterize the optimal trade-off between the per-sample quantization rate and the resulting mean-squared-error distortion, under various restrictions on the feedback filter. To this end, we establish a duality relation between the performance of sigma-delta modulation, and that of differential pulse-code modulation when applied to (discrete-time) band-limited inputs. As the optimal trade-off for the latter scheme is fully understood, the full characterization for sigma-delta modulation, as well as the optimal feedback filters, immediately follow.

We consider a Gaussian multiple-access channel where each user's message is identified with a vector of elements from a finite field, and the receiver's goal is to decode a linear combination of these finite field vectors. It is further assumed that each transmitter can causally observe the channel's output through a clean feedback link. We propose a novel coding scheme for this setup, which can be seen as an extension of the Cover-Leung scheme for the computation problem. This scheme is shown to achieve computation rates higher than the best known computation rates for the same scenario without feedback. In particular, for the symmetric two-user Gaussian multiple-access channel, the proposed scheme attains a symmetric computation rate greater than 1/2 log(3/4 + SNR).

The problem of transmitting a common message to multiple users over the Gaussian multiple-input multiple-output broadcast channel is considered, where each user is equipped with an arbitrary number of antennas. A closed-loop scenario is assumed, for which a practical capacity-approaching scheme is developed. By applying judiciously chosen unitary operations at the transmit and receive nodes, the channel matrices are triangularized so that the resulting matrices have equal diagonals, up to a possible multiplicative scalar factor. This, along with the utilization of successive interference cancellation, reduces the coding and decoding tasks to those of coding and decoding over the single-antenna additive white Gaussian noise channel. Over the resulting effective channel, any off-the-shelf code may be used. For the two-user case, it was recently shown that such joint unitary triangularization is always possible. In this paper, it is shown that for more than two users, it is necessary to carry out the unitary linear processing jointly over multiple channel uses, i.e., space-time processing is employed. It is further shown that exact triangularization, where all resulting diagonals are equal, is still not always possible, and appropriate conditions for the existence of such are established for certain cases. When exact triangularization is not possible, an asymptotic construction is proposed, that achieves the desired property of equal diagonals up to edge effects that can be made arbitrarily small, at the price of processing a sufficiently large number of channel uses together.

Recently, an open-loop transmission scheme for multiple-input multiple-output Gaussian channels based on precoded integer-forcing was proposed. The transmitter encodes the data into independent streams, all taken from the same linear code. The coded streams are then linearly precoded using a unitary matrix. At the receiver side, integer-forcing equalization is applied, followed by single-stream decoding. It was shown that this communication architecture achieves capacity up to a finite gap. In the present work we consider precoded integer-forcing for parallel Gaussian channels. We derive tighter bounds for this class of channels, which are related to the minimum product distance figure of merit. We further suggest a practical scheme that is applicable for all transmission rates, where the precoding matrix is capacity-dependent, chosen so as to maximize the achievable rate for a given value of capacity. For example, it is shown that for the case of two and three parallel channels, the scheme universally (for any value of capacity) achieves 94% and 82% of capacity, respectively.

Integer-Forcing (IF) is a new framework, based on compute-and-forward, for decoding multiple integer linear combinations from the output of a Gaussian multiple-input multiple-output channel. This paper applies the IF approach to arrive at a new low-complexity scheme, IF source coding, for distributed lossy compression of correlated Gaussian sources under a minimum mean squared error distortion measure. All encoders use the same nested lattice codebook. Each encoder quantizes its observation using the fine lattice as a quantizer and reduces the result modulo the coarse lattice, which plays the role of binning. Rather than directly recovering the individual quantized signals, the decoder first recovers a full-rank set of judiciously chosen integer linear combinations of the quantized signals, and then inverts it. In general, the linear combinations have smaller average powers than the original signals. This allows to increase the density of the coarse lattice, which in turn translates to smaller compression rates. We also propose and analyze a one-shot version of IF source coding that is simple enough to potentially lead to a new design principle for analog-to-digital converters that can exploit spatial correlations between the sampled signals.

The integer-forcing receiver architecture has recently been proposed as a high-performance, yet low-complexity, equalization scheme, that is applicable when all data streams are encoded with the same linear code. It was further shown in [1], that this receiver architecture, when coupled with space-time linear precoding is able to achieve the capacity of the open-loop multiple-input multiple-output channel, up to a constant gap that depends only on the number of transmit antennas. The gap, however, is quite large and thus provides performance guarantees that are useful only for high values of capacity. In this work, we consider the problem of multicast over multiple-input multiple-output channels to a modest number of users, and with space-only linear precoding. It is assumed that channel state information is available to the transmitter, allowing it to optimize the precoding matrix so as to maximize the achievable transmission rate. It is numerically demonstrated that this architecture allows to very closely approach the multicast capacity at all transmission rates regimes.

The Gaussian parallel relay network, introduced by Schein and Gallager, consists of a concatenation of a Gaussian additive broadcast channel from a single encoder to a layer of relays followed by a Gaussian multiple-access channel from the relays to the final destination (decoder), where all noises are independent. This setup exhibits an inherent conflict between digital and analog relaying; while analog relaying [known as amplify-and-forward (A&F)] suffers from noise accumulation, digital relaying (known as decode-and-forward) looses the potential coherence gain in combining the relay noises at the decoder. For a large number of relays, the coherence gain is large, and thus analog relaying has better performance; however, it is limited to white channels of equal bandwidth. In this paper, we present a generalization of the analog approach to the case of bandwidth mismatch. Our strategy, coined rematch and forward (R&F), is based upon applying joint source-channel coding techniques that belong to a certain class of maximally analog schemes. Using such techniques, R&F converts the bandwidth of the broadcast section to that of the multiple-access section, creating an equivalent matched-bandwidth network over which A&F is applied. It is shown that this strategy exploits the full bandwidth of the individual channels, without sacrificing the coherence gain offered by A&F. Specifically, for given individual-link capacities, R&F remains within a constant gap from the network capacity for any number of relays and any bandwidth ratio between the sections. Finally, the approach is extended to the case of colored channels.

Interference alignment has emerged as a powerful tool in the analysis of multiuser networks. Despite considerable recent progress, the capacity region of the Gaussian K-user interference channel is still unknown in general, in part due to the challenges associated with alignment on the signal scale using lattice codes. This paper develops a new framework for lattice interference alignment, based on the compute-and-forward approach. Within this framework, each receiver decodes by first recovering two or more linear combinations of the transmitted codewords with integer-valued coefficients and then solving these linear combinations for its desired codeword. For the special case of symmetric channel gains, this framework is used to derive the approximate sum capacity of the Gaussian interference channel, up to an explicitly defined outage set of the channel gains. The key contributions are the capacity lower bounds for the weak through strong interference regimes, where each receiver should jointly decode its own codeword along with part of the interfering codewords. As part of the analysis, it is shown that decoding K linear combinations of the codewords can approach the sum capacity of the K-user Gaussian multiple-access channel up to a gap of no more than K/2 log K bits.

Linear receivers are often used to reduce the implementation complexity of multiple-antenna systems. In a traditional linear receiver architecture, the receive antennas are used to separate out the codewords sent by each transmit antenna, which can then be decoded individually. Although easy to implement, this approach can be highly suboptimal when the channel matrix is near singular. This paper develops a new linear receiver architecture that uses the receive antennas to create an effective channel matrix with integer-valued entries. Rather than attempting to recover transmitted codewords directly, the decoder recovers integer combinations of the codewords according to the entries of the effective channel matrix. The codewords are all generated using the same linear code, which guarantees that these integer combinations are themselves codewords. Provided that the effective channel is full rank, these integer combinations can then be digitally solved for the original codewords. This paper focuses on the special case where there is no coding across transmit antennas and no channel state information at the transmitter(s), which corresponds either to a multiuser uplink scenario or to single-user V-BLAST encoding. In this setting, the proposed integer-forcing linear receiver significantly outperforms conventional linear architectures such as the zero forcing and linear minimum mean-squared error receiver. In the high signal-to-noise ratio regime, the proposed receiver attains the optimal diversity-multiplexing tradeoff for the standard multiple-input multiple-output (MIMO) channel with no coding across transmit antennas. It is further shown that in an extended MIMO model with interference, the integer-forcing linear receiver achieves the optimal generalized degrees of freedom.

Upper bounds on the error probability in channel coding are considered, improving the RCU bound by taking into account events, where the likelihood of the correct codeword is tied with that of some competitors. This bound is compared to various previous results, both qualitatively and quantitatively; it is shown to be the tightest bound with respect to previous bounds with the same computational complexity. With respect to maximal error probability of linear codes, it is observed that when the channel is additive, the derivation of bounds, as well as the assumptions on the admissible encoder and decoder, simplify considerably.

An open-loop single-user multiple-input multiple-output communication scheme is considered where a transmitter, equipped with multiple antennas, encodes the data into independent streams all taken from the same linear code. The coded streams are then linearly precoded using the encoding matrix of a perfect linear dispersion space-time code. At the receiver side, integer-forcing equalization is applied, followed by standard single-stream decoding. It is shown that this communication architecture achieves the capacity of any Gaussian multiple-input multiple-output channel up to a gap that depends only on the number of transmit antennas.

A static (constant channel gains) realK-user interference channel is considered, where all interference (cross) channel gains are integers. For such channels, previous results demonstrate that the number of degrees of freedom is very sensitive to slight variations in the direct channel gains. In this paper, we derive an achievable rate region for such channels that is valid for finite SNR. At moderate values of SNR, the derived rate region is robust to slight variations in the direct channel gains. At asymptotic high SNR conditions, known results on the degrees of freedom are recovered. The new rate region is based on lattice interference alignment. The result is established via a new coding theorem for the two-user Gaussian multiple-access channel where both users use a single linear code.

We consider the error exponent of the memoryless multiple-access (MAC) channel. We show that if the MAC channel is modulo-additive, then any error probability, and hence any error exponent, achievable by a linear code for the corresponding single-user channel, is also achievable for the MAC channel. Specifically, for an alphabet of prime cardinality, where linear codes achieve the best known exponents in the single-user setting (and the optimal exponent above the critical rate), this performance carries over to the MAC setting. At least at low rates, where expurgation is needed, our approach strictly improves performance over previous results, where expurgation was used at most for one of the users. Even when the MAC channel is not additive, it may be transformed into such a channel. While the transformation is lossy, we show that the distributed structure gain in some “nearly additive” cases outweighs the loss, and thus we can improve upon the best known exponent for these cases as well. This approach is related to that previously proposed for the Gaussian MAC channel, and is based on “distributed structure”.

It has long been known that linear codes achieve the capacity of additive channels over finite fields. Much less has been known about the performance of linear codes over Zm, when used for communication over channels that are additive with respect to this group. Further, linear codes over Zmplay an important role in construction of lattices in Euclidean space. When a construction-A lattice is used for communication over an additive white Gaussian noise channel, a modulo-MZ additive channel with unimodal noise is induced at the receiver. In this paper it is shown that linear codes over Zmachieve the capacity of such channels when the cardinality of the alphabet is a power of a prime.

We address the problem of communication over arbitrarily permuted parallel Gaussian channels, where the permutation is known only to the receiver. We present a practical transmission scheme, that allows to transmit over this channel using off-the-shelf codes, in conjunction with linear processing and successive interference cancellation. The scheme is based on the approach of joint matrix triangularization. Explicit precoding matrices are derived for up to six parallel channels.

Multicasting is the general method of conveying the same information to multiple users over a broadcast channel. In this work, the Gaussian MIMO broadcast channel is considered, with multiple users and any number of antennas at each node. A “closed loop” scenario is assumed, for which a practical capacity-achieving multicast scheme is constructed. In the proposed scheme, linear modulation is carried over time and space together, which allows to transform the problem into that of transmission over parallel scalar sub-channels, the gains of which are equal, except for a fraction of sub-channels that vanishes with the number of time slots used. Over these sub-channels, off-the-shelf fixed-rate AWGN codes can be used to approach capacity.

We derive a new achievable sum rate for the symmetric Gaussian K-user interference channel. This sum rate is shown to be within a constant gap of the outer bound on the sum capacity of this channel for all values of interference level outside some outage set. The result is established through the use of lattice interference alignment. A new lattice-based extension to the Han-Kobayshi scheme is also introduced.

We derive an achievable rate region for the Gaussian K-user multiple-access channel (MAC) where all users transmit codewords from a chain of nested lattices. For any set of channel coefficients, this rate region contains points within a constant gap from the sum capacity boundary of the MAC. The main tool used is the recently proposed compute-and-forward framework. A new transformation of a MAC to a modulo-lattice multiple-input multiple-output (MIMO) channel is introduced based on this framework. Specifically, from one noisy linear combination of the transmitted signals the receiver attempts to decode K linearly independent equations with integer-valued coefficients. While the individual rates at which these equations can be decoded are highly sensitive to the exact channel gains, their sum is always within a constant gap from the sum capacity boundary of the MAC. The transformation is then utilized for establishing the desired rate region.

This work considers practical implementation of the decode-and-forward relaying protocol for the full-duplex Gaussian relay channel. Unlike previous works which developed coding techniques tailored to this protocol, it is shown that standard codes which are good for the Gaussian scalar channel of fixed signal-to-noise ratio suffice to approach the theoretical performance promised by this protocol. The proposed technique employs only linear operations and successive interference cancelation in conjunction with fixed signal-to-noise ratio base codes, and the achievable rate is solely dictated by the performance of these base codes. The same approach and results carry over to the multiple-antenna case as well.

A rateless code-i.e., a rate-compatible family of codes-has the property that codewords of the higher rate codes are prefixes of those of the lower rate ones. A perfect family of such codes is one in which each of the codes in the family is capacity-achieving. We show by construction that perfect rateless codes with low-complexity decoding algorithms exist for additive white Gaussian noise channels. Our construction involves the use of layered encoding and successive decoding, together with repetition using time-varying layer weights. As an illustration of our framework, we design a practical three-rate code family. We further construct rich sets of near-perfect rateless codes within our architecture that require either significantly fewer layers or lower complexity than their perfect counterparts. Variations of the basic construction are also developed, including one for time-varying channels in which there is no a priori stochastic model.

A discrete-time intersymbol interference (ISI) channel with additive Gaussian noise is considered, where only the receiver has knowledge of the channel impulse response. An approach for combining decision-feedback equalization with channel coding is proposed, where decoding precedes the removal of ISI. The proposed approach involves equalizing the channel impulse response to a response with integer-valued coefficients in conjunction with utilizing cyclic block codes. Leveraging the property that a cyclic code is closed under cyclic integer-valued convolution allows us to perform decoding prior to applying decision feedback. Explicit bounds on the performance of the proposed scheme are derived.

This work considers the joint source-channel problem of transmitting a Gaussian source over a two-user multiple-input multiple-output (MIMO) broadcast channel. We show the existence of non-trivial channels, where the optimal distortion pair (which for high signal-to-noise ratios equals the point-to-point distortions of the individual users) may be achieved. A condition for existence of a joint triangularization of the MIMO channels which shapes the ratio of the diagonals to a desired form is derived. Whenever possible, all diagonal elements but one are made equal. We then employ a hybrid digital-analog scheme to the source, where the digital part is sent over the equal subchannels and the analog refinement is sent over the remaining one.

Structured codes have been utilized in deriving the best known achievable rate regions in certain network scenarios. In this paper we demonstrate that structure can be also beneficial in terms of error exponents even in cases where there is no capacity gain. We use distributed structure, i.e., different users use codes which satisfy a nesting condition. Specifically, for the scalar Gaussian multiple-access channel we obtain an improvement over the best known achievable exponent, given by Gallager, for certain rate pairs.

In a recent work, a capacity-achieving scheme for the common-message two-user MIMO broadcast channel, based on single-stream coding and decoding, was described. This was obtained via a novel joint unitary triangularization which is applied to the corresponding channel matrices. In this work, the triangularization is generalized, to any (finite) number of matrices, allowing multi-user applications. To that end, multiple channel uses are jointly treated, in a manner reminiscent of space-time coding. As opposed to the two-user case, in the general case there does not always exist a perfect (capacity-achieving) solution. However, a nearly optimal scheme (with vanishing loss in the limit of large blocks) always exists. Common-message broadcasting is but one example of communication networks with MIMO links which can be solved using an approach coined “Network Modulation”; the extension beyond two links carries over to these problems.

The physical-layer network coding (PNC) approach provides improved performance in many scenarios over “traditional” relaying techniques or network coding. This work addresses the generalization of PNC to wireless scenarios where network nodes have multiple antennas. We use a recent matrix decomposition, which allows, by linear pre- and post-processing, to simultaneously transform both channel matrices to triangular forms, where the diagonal entries, corresponding to both channels, are equal. This decomposition, in conjunction with precoding, allows to convert any two-input multiple-access channel (MAC) into parallel MACs, over which single-antenna PNC may be used. The technique is demonstrated using the two-way relay channel with multiple antennas. For this case it is shown that, in the high signal-to-noise regime, the scheme approaches the cut-set bound, thus establishing the asymptotic network capacity.

The Compute-and-Forward approach has been proven to be very beneficial for communication over Gaussian networks. While the theoretical results are promising, it is still not completely understood how to best apply this scheme in practice. The objective of this work is to provide a low complexity scheme suitable for Compute-and-Forward. The scheme is based on utilizing linear codes over ℤqwhere q is not restricted to be prime and allows to achieve high transmission rates following Ungerboeck's set partitioning principle.

We show that the recently proposed integer-forcing linear receiver provides an attractive approach to the problem of mitigating external interference in MIMO channels. The integer-forcing receiver proceeds by first decoding a set of full rank integer linear combinations of the data streams. The resulting full rank equations are then inverted to find the original data. By selecting equation coefficients in a direction that depends on both the interference space and the channel matrix, the impact of external interference can be effectively reduced. We show that this technique attains a non-trivial gain over traditional linear receivers. Furthermore, the integer-forcing linear receiver achieves the same generalized degrees of freedom for the M×M MIMO channel with K dimensional external interference as the joint decoder.

State-dependent channels have received much attention over the years, due to their relevance in many different network and multi-user communication scenarios. Nonetheless, previous treatments of this problem assumed that all of the state is available in the same manner: causally, non-causally or non-causally with a finite look-ahead. Yet, in many realistic situations, different parts of the state are known in a different manner. We consider the case where the state is composed of several parts, where each part is known with a different look-ahead. Specifically, we derive the capacity for the case where part of the state is known non-causally to the transmitter, whereas the other part is known only causally, and demonstrate that there are cases in which this capacity can be strictly larger that the capacity of the case where the state is known in a causal fashion, and strictly smaller than the capacity of the same channel, where the state is available non-causally. We note that the treatment in this work provides a unified framework for treating the causal state-information case, the non-causal state-information case, as well as a mixture of the two.

The problem of multicasting common data to several users over multiple-input multiple-output (MIMO) Gaussian channels is studied. A closed-loop setup is considered where the channel matrices are known to the transmitter and respective receivers. An incremental-redundancy (rateless) scenario is considered, where the effective rate is measured by the time that each user needs to stay online until it is able to decode the message. A practical transmission scheme for the two-user case is proposed which, by linear pre - and post-processing combined with successive decoding and interference cancellation, transforms the two MIMO channels into a set of parallel channels with no loss of mutual information, where each user needs to tune in for a duration of time proportional to its individual capacity. This scheme is used for designing a practical transmission scheme for the Gaussian MIMO half-duplex relay channel. We then turn to the related scenario of transmission to a single user over a MIMO channel with unknown but constant signal-to-noise ratio (SNR), for which we develop an optimal low-complexity hybrid ARQ coding scheme, which is optimal for two SNRs and propose a scheme for more SNRs, the loss of which vanishes when the SNRs are high. Finally, we show that even when applied to single-input single-output (“scalar”) channels, the scheme provides a practical solution for cases not covered by previous work.

A time-invariant (constant channel gains) K-user interference channel is considered, where all interference (cross) channel gains are integers. For such channels, previous results demonstrate that the number of degrees of freedom is very sensitive to slight variations in the direct channel gains. In this paper we derive an achievable rate region for such channels which is valid for finite SNR. At moderate values of SNR the derived rate region is robust to slight variations in the direct channel gains. At asymptotic high SNR conditions, the known results on the degrees of freedom are recovered. The new rate region is based on lattice interference alignment. The result is established via a new coding theorem for the two-user Gaussian multiple-access channel where both users use a single linear code.

A bound on the capacity of the causal dirty-paper channel with arbitrary interference and general independent identically distributed additive noise is derived. In particular, it is shown that for the case of Gaussian noise, the capacity is upper bounded by log2(1+SNR/e) bits per real dimension. This bound is useful for SNR ≤e(e-2) .

In Costa's dirty-paper channel, Gaussian random binning is able to eliminate the effect of interference which is known at the transmitter, and thus achieve capacity. We examine a generalization of the dirty-paper problem to a multiple access channel (MAC) setup, where structured (lattice-based) binning seems to be necessary to achieve capacity. In the dirty-MAC, two additive interference signals are present, one known to each transmitter but none to the receiver. The achievable rates using Costa's Gaussian binning vanish if both interference signals are strong. In contrast, it is shown that lattice-strategies (“lattice precoding”) can achieve positive rates, independent of the interference power. Furthermore, in some cases-which depend on the noise variance and power constraints-high-dimensional lattice strategies are in fact optimal. In particular, they are optimal in the limit of high SNR-where the capacity region of the dirty MAC with strong interference approaches that of a clean MAC whose power is governed by the minimum of the users' powers rather than their sum. The rate gap at high SNR between lattice-strategies and optimum (rather than Gaussian) random binning is conjectured to be1/2log2(πe/6) ≈ 0.254 bit. Thus, the doubly dirty MAC is another instance of a network setting, like the Körner-Marton problem, where (linear) structured coding is potentially better than random binning.

A bound on the capacity of the causal dirty paper problem with arbitrary interference and general independent identically distributed additive noise is derived. In particular, it is shown that for the case of Gaussian noise the capacity is upper bounded by log2(1 + (SNR)/e) bits per real dimension. This bound is useful for SNR ≤ e(e - 2).

Linear receivers are often used to reduce the implementation complexity of multiple antenna systems. In a traditional linear receiver architecture, the receive antennas are used to separate out the codewords sent by each transmit antenna, which can then be decoded individually. Although easy to implement, this approach can be highly sub-optimal when the channel matrix is near singular. In this paper, we develop a new linear architecture that uses the receive antennas to create an effective channel matrix with integer-valued entries. Instead of attempting to recover a transmitted codeword directly, each decoder recovers a different integer combination of the codewords according to the effective channel matrix. If the effective channel is full rank, these linear equations can be digitally solved for the original codewords. By allowing the receiver to equalize the channel to any matrix with integer entries, this scheme can outperform traditional linear architectures such as decorrelators and MMSE receivers while maintaining a similar complexity. Furthermore, in the case where each transmit antenna encodes an independent data stream, the proposed receiver attains the optimal diversity multiplexing tradeoff.

We propose a new framework for MIMO decoding based on a recently developed technique for reliably conveying linear equations over wireless channels. Each transmit antenna sends an independent data stream using the same linear code. As a result, any integer combination of the codewords is itself a codeword. Each receive antenna observes a random complex-valued combination of the codewords according to the fading coefficients. We use a linear pre-processing step at the receiver to transform the effective channel into a (full-rank) integer matrix. A single stream decoder is then used to recover integer combinations of the codewords. These equations of codewords are then translated into equations of the transmitted data streams over a finite field which can be easily solved for the original data. We examine the performance of our scheme in terms of the probability of outage and show that significant gains are possible over standard linear architectures for both i.i.d. and correlated Rayleigh fading.

A binary erasure channel with erasure probability which can take one of two values is considered. Transmission is done by using a low density parity-check code under the requirement that completely successful decoding is possible when the channel is in its better state, while tolerating some predetermined residual erasure fraction when the channel is in its worse state. Upper bounds on the achievable design rate under iterative decoding are derived for this setting. These bounds are compared to rates obtained by practical code profiles. It is also observed that when exceeding the capacity of the erasure channel, the performance of such codes exhibits graceful degradation as measured by the residual erasure fraction.

A dirty-paper channel is considered, where the transmitter knows the interference sequence up to a constant multiplicative factor, known only to the receiver. Lower bounds on the achievable rate of communication are derived by proposing a coding scheme that partially compensates for the imprecise channel knowledge.We focus on a communication scenario where the signal-to-noise ratio is high. Our approach is based on analyzing the performance achievable using lattice-based coding schemes. When the power of the interference is finite, we show that the achievable rate of this lattice-based coding scheme may be improved by a judicious choice of the scaling parameter at the receiver. We further show that the communication rate may be improved, for finite as well as infinite interference power, by allowing randomized scaling at the transmitter.

We consider the problem of obtaining channel state information (CSI) via a fast feedback link for transmission on the downlink of a multiuser MIMO system. We examine the relative merits of channel feedback schemes based on Shannon's source-channel separation principle (digital schemes) and non-separation based schemes and show that the latter are preferable in this application when small to moderate bandwidth expansion ratios are used as in many current cellular systems. For comparison, we first compute upper-bounds on the performance of the system as a function of SNR. For the non-separation based schemes, we first consider a simple analog transmission and then develop a hybrid digital-analog transmission scheme which quantizes the CSI using a few bits and sends these bits and also the quantization error using analog transmission. We show that the hybrid scheme achieves a higher throughput compared to both analog and digital transmissions and has a much lower computational complexity compared to a digital scheme.

In many network communication scenarios, a relay in the network may only need to recover and retransmit an equation of the transmitted messages. In previous work, it has been shown that if each transmitter employs the same lattice code, the interference structure of the channel can be exploited to recover an equation much more efficiently than possible with standard multiple-access strategies. Here, we generalize this compute-and-forward framework to the multiple antenna setting. Our results show that it is often beneficial to use extra antennas at the receiver to rotate the channel coefficients towards the nearest integer vector instead of separating out the transmitted signals. We also demonstrate that in contrast to classical strategies, the multiplexing gain of compute-and-forward increases if the transmitters have channel state information. Finally, we apply our scheme to the two way relay network and observe performance gains over traditional strategies.

We consider the problem of channel state information (CSI) transmission on a fast feedback link for a multiuser MIMO system.We examine the relative merits of channel feedback schemes based on Shannon's source-channel separation theorem and non-separation based schemes and show that the latter are preferable in this application. For the non-separation based schemes, we first consider a simple analog transmission and then develop a hybrid digital-analog transmission scheme which quantizes the CSI using a few bits and sends these bits and also the quantization error using analog transmission. We show that the hybrid scheme achieves a higher throughput compared to both analog and digital transmissions and has a much lower computational complexity compared to a digital scheme.

Two rateless code constructions are developed for efficient communication over multi-input multi-output (MIMO) Gaussian channels. The key ingredients in both architectures are layering, dithering, and repetition. Both employ successive cancellation decoding along with minimum mean-square error (MMSE) combining and convert the MIMO channel into a scalar channel to which classical Gaussian base codes can be applied. The first construction based on simple layering induces an additive white Gaussian noise (AWGN) scalar channel and with perfect base codes achieves a substantial efficiency gain over a baseline repetition scheme. At typical spectral efficiencies, this scheme can achieve better than 85% of capacity for a rateless construction with two effective rates. The second construction which uses a diagonal layering (DL) structure is capacity achieving at any SNR and induces a particular time-varying scalar channel. This holds even if the MIMO channel is block constant but time-varying.

A binary erasure channel with erasure probability which can take one of two values is considered. Transmission is done by using a low density parity-check code under the requirement that completely successful decoding is possible when the channel is in its better state, while tolerating some predetermined residual erasure fraction when the channel is in its worse state. Upper bounds on the achievable design rate under iterative decoding are derived for this setting. These bounds are compared to rates obtained by practical code profiles. It is also observed that when exceeding the capacity of the erasure channel, the performance of such codes exhibits graceful degradation as measured by the residual erasure fraction.

The problem of constructing lattices such that their quantization noise approaches a desired distribution is studied. It is shown that asymptotically is the dimension, lattice quantization noise can approach a broad family of distribution functions with independent and identically distributed components.

The Gaussian parallel relay network problem consists of transmitting a message from a single source node to a single destination node, through a layer of parallel relay nodes. The source is connected to the relays by a Gaussian broadcast channel, while the relays are connected to the destination by a Gaussian multiple access channel. When the channels are all white with the same bandwidth, and the relays cannot decode the message, the best known strategy is "amplify and forward", which achieves the coherence gain of multiple relays. We propose a strategy which achieves this gain even when the noises are colored or the channels have different bandwidths. To that end we use analog modulo-lattice modulation of the codewords in the BC, and then forward the estimated codeword by each of the relays to the MAC. This modulation allows the relays to re-match the signal to the optimal spectrum of the MAC, thus demonstrating how a channel problem can gain from a joint source/channel approach. We show that this strategy is asymptotically optimal in some limiting cases, and that it outperforms the known alternatives in most other cases, where the optimum is unknown. We also demonstrate how to improve the achievable rate in the original white problem, for some signal to noise ratio values.

A coding scheme for a MIMO channel, based on superposition of dithered orthogonal design space-time block codes, is presented, building on and extending recent work of Erez, Wornell and Trott. When used in conjunction with successive decoding, the MIMO channel is converted into a set of AWGN scalar channels, allowing for standard coding and decoding techniques to be employed. By superimposing multiple layers of orthogonal-design codes, the well known drawback of loss of degrees of freedom of the latter is alleviated. When used in a closed-loop mode, the scheme allows to approach the white-input capacity of a MIMO channel with limited feedback, i.e., with feedback of the eigenvalues of the channel matrix. When used in an open-loop mode, the scheme exhibits good performance in terms of the diversity-multiplexing tradeoff. Further, the computational complexity is linear in the transmission rate.

Two time-invariant rateless code constructions are developed for efficient communication over multi-input multi- output (MIMO) Gaussian channels. Both architectures employ layering, dithering, and repetition as key ingredients, and convert the MIMO channel into a scalar channel to which classical Gaussian base codes can be applied. Both constructions are convolutionally structured - one is based on faster-than-Nyquist (ftN) signaling, while the other on a diagonal layering (DL) structure. Moreover, both employ successive cancellation decoding. We show that ftN rateless codes are asymptotically capacity achieving at any signal-to-noise ratio (SNR) and induce a time-invariant scalar channel. We also show that DL codes are capacity achieving at any SNR, and induce a particular time-varying scalar channel to which standard LDPC base codes can be applied without significantly sacrificing performance.

A dirty paper channel is considered, where the transmitter knows the interference sequence up to a constant multiplicative factor, known only to the receiver. We derive lower bounds on the achievable rate of communication by proposing a coding scheme that partially compensates for the imprecise channel knowledge.We focus on a communication scenario where the Gaussian noise is small while the interference is strong. Our approach is based on analyzing the performance achievable using extended Tomlinson-Harashima like coding schemes. When the power of the interference is finite, we show that this may be achieved by a judicious choice of the scaling parameter at the receiver. We further show that the communication rate may be improved, for finite as well as infinite interference power, by allowing randomized scaling at the transmitter.

The ldquowater-fillingrdquo solution for the quadratic rate-distortion function of a stationary Gaussian source is given in terms of its power spectrum. This formula naturally lends itself to a frequency domain ldquotest-channelrdquo realization. We provide an alternative time-domain realization for the rate-distortion function, based on linear prediction. The predictive test channel has some interesting implications, including the optimality at all distortion levels of pre/post filtered vector-quantized differential pulse-code modulation (DPCM), and a duality relationship with decision-feedback equalization (DFE) for intersymbol interference (ISI) channels.

We study a dirty paper channel model where the input is constrained to belong to a PAM constellation. In particular, we provide lower bounds on the capacity as well as explicit coding schemes for the binary-input dirty- paper channel. We examine the case of causal as well as non-causal side information.

We consider a generalization of the Gaussian dirty- paper problem to a multiple access setup. There are two additive interferences, one known to each transmitter but none to the receiver. The rates achievable using random binning schemes (i.e. schemes based on Costa's auxiliary random variables) vanish in the limit when the interferences are strong. In contrast, we show that lattice strategies ("lattice preceding") can achieve positive rates independent of the interferences. Furthermore, we derive an outer bound for the capacity region for arbitrary interferences, which is strictly smaller than the clean MAC capacity region. We then show that lattice strategies meet this outer bound for some combinations of noise variance and power constraints. In particular, lattice strategies are optimal in the limit of high SNR. Thus, the dirty MAC is another instance of a network setup, like the Korner-Marton modulo-two sum problem, where linear coding is better than random binning. We also derive lattice transmission schemes and conditions for optimality for the asymmetric case, where there is only one interference which is known to one of the users, and in particular for the helper problem, where the user which knows the interference does not have a message it wishes to transmit.

A generalization of the problem of writing on dirty paper is considered in which one transmitter sends a common message to multiple receivers. Each receiver experiences on its link an additive interference (in addition to the additive noise), which is known noncausally to the transmitter but not to any of the receivers. Applications range from wireless multiple-antenna multicasting to robust dirty paper coding. We develop results for memoryless channels in Gaussian and binary special cases. In most cases, we observe that the availability of side information at the transmitter increases capacity relative to systems without such side information, and that the lack of side information at the receivers decreases capacity relative to systems with such side information. For the noiseless binary case, we establish the capacity when there are two receivers. When there are many receivers, we show that the transmitter side information provides a vanishingly small benefit. When the interference is large and independent across the users, we show that time sharing is optimal. For the Gaussian case, we present a coding scheme and establish its optimality in the high signal-to-interference-plus-noise limit when there are two receivers. When the interference power is large and independent across all the receivers, we show that time-sharing is again optimal. Connections to the problem of robust dirty paper coding are also discussed

We consider communication over the Gaussian multiple access channel (MAC) with unknown set of active users. The proposed multiple access strategy is distributed and achieves a maximum sum rate point on the boundary of the capacity region for this channel for any set of active users S simultaneously, as if S were known at the transmitters. The proposed coding scheme splits each user into a set of virtual users, each of which can be decoded using a single-user decoder at the receiver instead of having to decode all users jointly. We also present a generalization of this scheme to the case where the channel gains differ between users and each user only knows its own channel gain.

A rateless code, or a rate-compatible family of codes, has the property that the higher rate codes have codewords that are prefixes of those of the lower rate ones. A perfect family of such codes is one in which each of the codes in the family is capacity-achieving. We show by construction that perfect rateless codes with low-complexity decoding algorithms exist for additive white Gaussian noise channels. As an illustration of our framework, we design a practical three-rate code family. We further demonstrate that a rich set of perfect or near-perfect rateless codes may be found via numerical optimization

The "water-filling" solution for the quadratic rate-distortion function of a stationary Gaussian source is given in terms of its power spectrum. This formula naturally lends itself to a frequency domain "test-channel" realization. We provide an alternative time-domain realization for the rate-distortion function, based on linear prediction. This solution has some interesting implications, including the optimality at all distortion levels of pre/post filtered vector-quantized differential pulse code modulation (DPCM), and a duality relationship with decision-feedback equalization (DFE) for inter-symbol interference (ISI) channels

A framework is developed for analyzing capacity gains from user cooperation in slow-fading wireless networks when the number of nodes (network size) is large. The framework is illustrated for the case of a simple multipath-rich Rayleigh-fading channel model. Both unicasting (one source and one destination) and multicasting (one source and several destinations) scenarios are considered. We introduce a meaningful notion of Shannon capacity for such systems, evaluate this capacity as a function of signal-to-noise ratio (SNR), and develop a simple two-phase cooperative network protocol that achieves it. We observe that the resulting capacity is the same for both unicasting and multicasting, but show that the network size required to achieve any target error probability is smaller for unicasting than for multicasting. Finally, we introduce the notion of a network "scaling exponent" to quantify the rate of decay of error probability with network size as a function of the targeted fraction of the capacity. This exponent provides additional insights to system designers by enabling a finer grain comparison of candidate cooperative transmission protocols in even moderately sized networks.

Rateless codes are good codes of infinite length that have the property that prefixes of such codes are themselves good codes. This makes them attractive for applications in which the channel quality is uncertain, where systems transmit as much of a codeword as necessary for decoding to be possible. In particular, rateless codes are potentially attractive for wireless communication. In a recent work, a rateless coding scheme was proposed for the AWGN channel, based on layering, repetition and random dithering. We extend this scheme to multiple-input single-output (MISO) Gaussian channels. We show that the rate loss associated with orthogonal design space-time codes may be alleviated by layering and dithering, very similar to the rateless approach for the AWGN channel. We then combine the two schemes and arrive at a close-to-capacity rateless code for MISO channels. The required complexity depends on the fraction of capacity that is targeted, is linear in the capacity of the channel and does not depend on the number of transmit antennas. Furthermore, the coding scheme uses only one base AWGN code

The "writing on dirty paper"-channel model offers an information-theoretic framework for precoding techniques for canceling arbitrary interference known at the transmitter. It indicates that lossless precoding is theoretically possible at any signal-to-noise ratio (SNR), and thus dirty-paper coding may serve as a basic building block in both single-user and multiuser communication systems. We design an end-to-end coding realization of a system materializing a significant portion of the promised gains. We employ multidimensional quantization based on trellis shaping at the transmitter. Coset decoding is implemented at the receiver using "virtual bits." Combined with iterative decoding of capacity-approaching codes we achieve an improvement of 2dB over the best scalar quantization scheme. Code design is done using the EXIT chart technique.

We define an ensemble of lattices, and show that for asymptotically high dimension most of its members are simultaneously good as sphere packings, sphere coverings, additive white Gaussian noise (AWGN) channel codes and mean-squared error (MSE) quantization codes. These lattices are generated by applying Construction A to a random linear code over a prime field of growing size, i.e., by "lifting" the code to /spl Ropf//sup n/.

We derive the asymptotic spectra of low-density parity-check (LDPC) ensembles over Z/sub q/. We consider two ensembles of LDPC matrices, one is binary and the other q-ary. We also show that for modulo-additive noise channels, both ensembles achieve the random coding error exponent, for graphs with sufficiently large connectivity.

We consider the generalized dirty-paper channel Y=X+S+N,E{X/sup 2/}/spl les/P/sub X/, where N is not necessarily Gaussian, and the interference S is known causally or noncausally to the transmitter. We derive worst case capacity formulas and strategies for "strong" or arbitrarily varying interference. In the causal side information (SI) case, we develop a capacity formula based on minimum noise entropy strategies. We then show that strategies associated with entropy-constrained quantizers provide lower and upper bounds on the capacity. At high signal-to-noise ratio (SNR) conditions, i.e., if N is weak relative to the power constraint P/sub X/, these bounds coincide, the optimum strategies take the form of scalar lattice quantizers, and the capacity loss due to not having S at the receiver is shown to be exactly the "shaping gain" 1/2log(2/spl pi/e/12)/spl ap/ 0.254 bit. We extend the schemes to obtain achievable rates at any SNR and to noncausal SI, by incorporating minimum mean-squared error (MMSE) scaling, and by using k-dimensional lattices. For Gaussian N, the capacity loss of this scheme is upper-bounded by 1/2log2/spl pi/eG(/spl Lambda/), where G(/spl Lambda/) is the normalized second moment of the lattice. With a proper choice of lattice, the loss goes to zero as the dimension k goes to infinity, in agreement with the results of Costa. These results provide an information-theoretic framework for the study of common communication problems such as precoding for intersymbol interference (ISI) channels and broadcast channels.

An information theoretic framework for the study of efficient known interference cancellation technique is presented in this paper. The dirty paper channel model is given where the arbitrary interference is known at the transmitter is a statistically independent Gaussian random variable with variance. The link to precoding was made and it was shown that the full capacity might be achieved using lattices and MMSE scaling for arbitrary interference. A BCJR detector computes the a posteriori probability (APP) values of the channel code bits, summing over the corresponding coset. Extrinsic information is iteratively passed between BCJR detector and channel decoder. Code design is done using the EXIT chart, achieving an improvement over optimal scalar quantization (SQ).

We study the problem of sending a common message to several users on a channel with side information. Specifically, each user experiences an additive interference which is known only to the sender. The sender has to simultaneously adapt its transmitted signal to all the interferences. We derive upper and lower bounds for the special case of binary channels and derive some optimality conditions.

We address an open question, regarding whether a lattice code with lattice decoding (as opposed to maximum-likelihood (ML) decoding) can achieve the additive white Gaussian noise (AWGN) channel capacity. We first demonstrate how minimum mean-square error (MMSE) scaling along with dithering (lattice randomization) techniques can transform the power-constrained AWGN channel into a modulo-lattice additive noise channel, whose effective noise is reduced by a factor of /spl radic/(1+SNR/SNR). For the resulting channel, a uniform input maximizes mutual information, which in the limit of large lattice dimension becomes 1/2 log (1+SNR), i.e., the full capacity of the original power constrained AWGN channel. We then show that capacity may also be achieved using nested lattice codes, the coarse lattice serving for shaping via the modulo-lattice transformation, the fine lattice for channel coding. We show that such pairs exist for any desired nesting ratio, i.e., for any signal-to-noise ratio (SNR). Furthermore, for the modulo-lattice additive noise channel lattice decoding is optimal. Finally, we show that the error exponent of the proposed scheme is lower bounded by the Poltyrev exponent.

We consider the problem of choosing a robust input for communicating over an input constrained additive-noise channel where the noise distribution is arbitrary. We show that the mutual information rate achievable using a white Gaussian input never incurs a loss of more than half a bit per sample with respect to the power constrained capacity. For comparison, for the family of colored Gaussian noise channels a white Gaussian input loses at most log(e)/2e/spl ap/0.265 bit per sample with respect to the optimum water-pouring solution. For general input constraints, we derive a formula for choosing the best input in the min-max capacity loss (bound) sense. The bound on the capacity loss is tight for pulse position modulation (PPM) in the presence of a bursty jammer.

Using random coding techniques, we show that, in high dimensions, there exist lattices which are simultaneously good as sphere packings, sphere coverings, AWGN channel and MSE quantization codes. These lattices are produced by a construction, similar to construction A (Conway, J.H. and Sloane, N.J.A., 1988), and a randomly chosen set of generating vectors.

Network information theory promises high gains over simple point-to-point communication techniques, at the cost of higher complexity. However, lack of structured coding schemes limited the practical application of these concepts so far. One of the basic elements of a network code is the binning scheme. Wyner (1974, 1978) and other researchers proposed various forms of coset codes for efficient binning, yet these schemes were applicable only for lossless source (or noiseless channel) network coding. To extend the algebraic binning approach to lossy source (or noisy channel) network coding, previous work proposed the idea of nested codes, or more specifically, nested parity-check codes for the binary case and nested lattices in the continuous case. These ideas connect network information theory with the rich areas of linear codes and lattice codes, and have strong potential for practical applications. We review these developments and explore their tight relation to concepts such as combined shaping and precoding, coding for memories with defects, and digital watermarking. We also propose a few novel applications adhering to a unified approach.

Consider the optimum strategy for using channel state ("side") information in transmission over a modulo-additive noise channel, with state-dependent noise, where the receiver does not have access to the side information (SI). Previous work showed that capacity-wise, the optimum transmitter shifts each code letter by a "prediction" of the noise sample based on the SI. We show that this structure achieves also the random-coding error exponent, and, therefore, is optimum at some range of rates below capacity. Specifically, the optimum transmitter predictor minimizes the Renyi entropy of the prediction error; the Renyi order depends on the rate, and goes to one (corresponding to Shannon entropy) for rates close to capacity. In contrast, it is shown that this "prediction strategy" may not be optimal at low transmission rates.

The computation of channel capacity with side information at the transmitter side (but not at the receiver side) requires, in general, extension of the input alphabet to a space of "strategies", and is often hard. We consider the special case of a discrete memoryless module-additive noise channel Y=X+Z/sub s/, where the encoder observes causally the random state S/spl isin/S that governs the distribution of the noise Z/sub s/. We show that the capacity of this channel is given by C=log|/spl chi/|-min/sub t:S/spl rarr//spl chi//H(Z/sub S/-t(S)). This capacity is realized by a state-independent code, followed by a shift by the "noise prediction" t/sub min/(S) that minimizes the entropy of Z/sub s/-t(S). If the set of conditional noise distributions {p(z|s),s/spl isin/S} is such that the optimum predictor t/sub min/(/spl middot/) is independent of the state weights, then C is also the capacity for a noncausal encoder, that observes the entire state sequence in advance. Furthermore, for this case we also derive a simple formula for the capacity when the state process has memory.