Low-density parity-check (LDPC) codes have higher coding gains compared to algebraic codes in several configurations. However, unlike algebraic codes whose performance can be easily determined generally, the block error rate performance of an LDPC code needs to be obtained by simulations. While there are analytical methods for some structured LDPC codes that predict this performance in the low error rate regime, these provide little insight into the error floor of other (less structured) LDPC codes. In this article, we present a simple method to upper bound the error floor of LDPC codes based on a certain monotonicity assumption on the decoder. This upper bound is general enough so that under the monotonicity assumption it is valid for any error-correcting code. This upper bounding technique is useful when projecting very low block error rates (such as below 1E-14) for LDPC codes and there is no knowledge of the trapping sets.

We introduce a new approach to proving that a sequence of deterministic linear codes achieves capacity on an erasure channel under maximum a posteriori decoding. Rather than relying on the precise structure of the codes, our method exploits code symmetry. In particular, the technique applies to any sequence of linear codes where the blocklengths are strictly increasing, the code rates converge, and the permutation group of each code is doubly transitive. In other words, we show that symmetry alone implies near-optimal performance. An important consequence of this result is that a sequence of Reed-Muller codes with increasing block length and converging rate achieves capacity. This possibility has been suggested previously in the literature but it has only been proven for cases where the limiting code rate is 0 or 1. Moreover, these results extend naturally to all affine-invariant codes and, thus, to extended primitive narrow-sense BCH codes. This also resolves, in the affirmative, the existence question for capacity-achieving sequences of binary cyclic codes. The primary tools used in the proof are the sharp threshold property for symmetric monotone Boolean functions and the area theorem for extrinsic information transfer functions.

The question whether RM codes are capacity-achieving is a long-standing open problem in coding theory that was recently answered in the affirmative for transmission over erasure channels [1], [2]. Remarkably, the proof does not rely on specific properties of RM codes, apart from their symmetry. Indeed, the main technical result consists in showing that any sequence of linear codes, with doubly-transitive permutation groups, achieves capacity on the memoryless erasure channel under bit-MAP decoding. Thus, a natural question is what happens under block-MAP decoding. In [1], [2], by exploiting further symmetries of the code, the bit-MAP threshold was shown to be sharp enough so that the block erasure probability also converges to 0. However, this technique relies heavily on the fact that the transmission is over an erasure channel. We present an alternative approach to strengthen results regarding the bit-MAP threshold to block-MAP thresholds. This approach is based on a careful analysis of the weight distribution of RM codes. In particular, the flavor of the main result is the following: assume that the bit-MAP error probability decays as N−δ, for some δ > 0. Then, the block-MAP error probability also converges to 0. This technique applies to transmission over any binary memoryless symmetric channel. Thus, it can be thought of as a first step in extending the proof that RM codes are capacity-achieving to the general case.

The quantum erasure channel is the simplest example of a quantum communication channel and its information capacity is known precisely. The subclass of quantum error-correcting codes called stabilizer codes is known to contain capacity-achieving sequences for the quantum erasure channel, but no efficient method is known to construct these sequences. In this article, we explicitly describe a capacity-achieving code sequence for the quantum erasure channel. In particular, we show that Calderbank-Shor-Steane (CSS) stabilizer codes constructed from self-orthogonal binary linear codes are capacity-achieving on the quantum erasure channel if the binary linear codes are capacity-achieving on the binary erasure channel. Recently, Reed-Muller codes were shown to achieve capacity on classical erasure channels. Using this, we show that CSS codes constructed from binary Reed-Muller codes achieve the capacity of the quantum erasure channel. The capacity-achieving nature of these CSS codes is also explained from a GF(4) perspective.

Recently, sequences of error-correcting codes with doubly-transitive permutation groups were shown to achieve capacity on erasure channels under symbol-wise maximum a posteriori (MAP) decoding. From this, it follows that Reed-Muller and primitive narrow-sense BCH codes achieve capacity in the same setting. In this article, we extend this result to a large family of cyclic codes by considering codes whose permutation groups satisfy a condition weaker than double transitivity. The article combines two simple technical contributions. First, we show that the transition width of a monotone boolean function is O(1/log k), where k is the size of the smallest orbit induced by its symmetry group. The proof is based on Talagrand's lower bound on influences for monotone boolean functions. Second, we consider the extrinsic information transfer (EXIT) function of an Fq-linear cyclic code whose blocklength N divides qt- 1 and is coprime with q - 1. We show that this EXIT function is a monotone boolean function whose symmetry group contains no orbits of size smaller than the smallest prime divisor of t. Combining these, we show that sequences of cyclic codes, whose blocklengths satisfy the above conditions, achieve capacity on the q-ary erasure channel if all prime divisors of t tend to infinity.

We introduce a new approach to proving that a sequence of deterministic linear codes achieves capacity on an erasure channel under maximum a posteriori decoding. Rather than relying on the precise structure of the codes, our method exploits code symmetry. In particular, the technique applies to any sequence of linear codes where the block lengths are strictly increasing, the code rates converge, and the permutation group of each code is doubly transitive. In a nutshell, we show that symmetry alone implies near-optimal performance.

For compound LDGM/LDPC codes with maximum a posteriori (MAP) processing, Wainwright and Martinian showed that the information-theoretic rate regions of the Wyner-Ziv (WZ) and Gelfand-Pinsker (GP) problems are achievable. For the same ensemble, these rates do not appear to be achievable with message-passing guided decimation (GD). Fortunately, spatially-coupled (SC) codes seem to provide an elegant remedy when iterative decoding falls short of MAP decoding. In particular, Aref et al. recently introduced SC LDGM codes that approach the rate-distortion region with belief-propagation guided decimation (BPGD). In this paper, we show that SC compound LDGM/LDPC codes with BPGD can approach the rate regions of the WZ and GP problems.

This article considers the performance of wireless communication systems that utilize reconfigurable or pattern-dynamic antennas. The focus is on finite-state channels with memory and performance is assessed in terms of real-time behavior. In a wireless setting, when a slow fading channel enters a deep fade, the corresponding communication system faces the threat of successive decoding failures at the destination. Under such circumstances, rapidly getting out of deep fades becomes a priority. Recent advances in fast reconfigurable antennas provide new means to alter the statistical profile of fading channels and thereby reduce the probability of prolonged fades. Fast reconfigurable antennas are therefore poised to improve overall performance, especially for delay-sensitive traffic in slow-fading environments. This potential for enhanced performance motivates this study of the temporal behavior of point-to-point communication systems with reconfigurable antennas. Specifically, agile wireless communication schemes over erasure channels are analyzed; situations where using reconfigurable antennas yield substantial performance gains in terms of throughput and average delay are identified. Scenarios where only partial state information is available at the receiver are also examined, naturally leading to partially observable decision processes.

Spatially-coupled low-density parity-check (LDPC) codes, which were first introduced as LDPC convolutional codes, have been shown to exhibit excellent performance under low-complexity belief-propagation decoding. This phenomenon is now termed threshold saturation via spatial coupling. Spatially-coupled codes have been successfully applied in numerous areas. In particular, it was proven that spatially-coupled regular LDPC codes universally achieve capacity over the class of binary memoryless symmetric (BMS) channels under belief-propagation decoding. Recently, potential functions have been used to simplify threshold saturation proofs for scalar and vector recursions. In this paper, potential functions are used to prove threshold saturation for irregular LDPC and low-density generator-matrix codes on BMS channels, extending the simplified proof technique to BMS channels. The corresponding potential functions are closely related to the average Bethe free entropy of the ensembles in the large-system limit. These functions also appear in statistical physics when the replica method is used to analyze optimal decoding.

This paper considers the performance of digital communication systems transmitting messages over finite-state erasure channels with memory. Information bits are protected from channel erasures using error-correcting codes; successful receptions of codewords are acknowledged at the source through instantaneous feedback. The primary focus of this research is on delay-sensitive applications, codes with finite block lengths, and, necessarily, nonvanishing probabilities of decoding failure. The contribution of this paper is twofold. A methodology to compute the distribution of the time required to empty a buffer is introduced. Based on this distribution, the mean hitting time to an empty queue and delay-violation probabilities for specific thresholds can be computed explicitly. The proposed techniques apply to situations where the transmit buffer contains a predetermined number of information bits at the onset of the data transfer. Furthermore, as additional performance criteria, large deviation principles are obtained for the empirical mean service time and the average packet-transmission time associated with the communication process. This rigorous framework yields a pragmatic methodology to select code rate and block length for the communication unit as functions of the service requirements. Examples motivated by practical systems are provided to further illustrate the applicability of these techniques.

In this paper, we analyze the coexistence of a primary and a secondary (cognitive) network when both networks use the IEEE 802.11 based distributed coordination function for medium access control. Specifically, we consider the problem of channel capture by a secondary network that uses spectrum sensing to determine the availability of the channel, and its impact on the primary throughput. We integrate the notion of transmission slots in Bianchi's Markov model with the physical time slots, to derive the transmission probability of the secondary network as a function of its scan duration. This is used to obtain analytical expressions for the throughput achievable by the primary and secondary networks. Our analysis considers both saturated and unsaturated networks. By performing a numerical search, the secondary network parameters are selected to maximize its throughput for a given level of protection of the primary network throughput. The theoretical expressions are validated using extensive simulations carried out in the Network Simulator 2. Our results provide critical insights into the performance and robustness of different schemes for medium access by the secondary network. In particular, we find that the channel captures by the secondary network does not significantly impact the primary throughput, and that simply increasing the secondary contention window size is only marginally inferior to silent-period based methods in terms of its throughput performance.