Raptor codes on binary memoryless symmetric channels

In this paper, we will investigate the performance of Raptor codes on arbitrary binary input memoryless symmetric channels (BIMSCs). In doing so, we generalize some of the results that were proved before for the erasure channel. We will generalize the stability condition to the class of Raptor codes. This generalization gives a lower bound on the fraction of output nodes of degree 2 of a Raptor code if the error probability of the belief-propagation decoder converges to zero. Using information-theoretic arguments, we will show that if a sequence of output degree distributions is to achieve the capacity of the underlying channel, then the fraction of nodes of degree 2 in these degree distributions has to converge to a certain quantity depending on the channel. For the class of erasure channels this quantity is independent of the erasure probability of the channel, but for many other classes of BIMSCs, this fraction depends on the particular channel chosen. This result has implications on the "universality" of Raptor codes for classes other than the class of erasure channels, in a sense that will be made more precise in the paper. We will also investigate the performance of specific Raptor codes which are optimized using a more exact version of the Gaussian approximation technique.     

Zero-error list capacities of discrete memoryless channels

We define zero-error list capacities for discrete memoryless channels. We find lower bounds to, and a characterization of these capacities. As is usual for such zero-error problems in information theory, the characterization is not generally a single-letter one. Nonetheless, we exhibit a class of channels for which a single letter characterization exists. We also show how the computational cutoff rate relates to the capacities we have defined     

Rate-splitting multiple access for discrete memoryless channels

It is shown that the encoding/decoding problem for any asynchronous M-user discrete memoryless multiple-access channel can be reduced to corresponding problems for at most 2M-1 single-user discrete memoryless channels. This result, which extends a similar result for Gaussian channels, reduces the seemingly hard task of finding good multiple-access codes to the much better understood task of finding good codes for single-user channels. As a by-product, some interesting properties of the capacity region of M-user asynchronous discrete memoryless channels are derived     

A construction of codes with exponential error bounds on arbitrarydiscrete memoryless channels

This correspondence proposes an explicit construction of codes achieving capacity for arbitrary discrete memoryless channels. The proposed code is obtained by concatenating variable inner codes and an algebraic geometry code. Further, we clarify that the proposed code achieves the error exponent obtained by Forney for concatenated codes     

Error-correcting capabilities of concatenated codes with MDS outer codes on memoryless channels with maximum- likelihood decoding

Error-correcting capabilities of concatenated codes with maximum distance separable (MDS) outer codes and time-varying inner codes, used on memoryless discrete channels with maximum-likelihood decoding, are investigated. It is proved that, asymptotically, the Gallager random coding theorem can be obtained for all rates by such codes. Further, the expurgated coding theorem, as well, is proved to be valid for all rates on regular channels. The latter result implies that the Gilbert-Varshamov bound for block codes over any finite field can be obtained asymptotically for all rates by linear concatenated codes.     

Asymptotic bounds on quantum codes from algebraic geometry codes

We generalize a characterization of p-ary (p is a prime) quantum codes given by Feng and Xing to q-ary (q is a prime power) quantum codes. This characterization makes it possible to convert an asymptotic bound of Stichtenoth and Xing for nonlinear algebraic geometry codes to a quantum asymptotic bound. Besides, we also investigate the asymptotic behavior of quantum codes.     

An improved achievable region for the discrete memoryless two-user multiple-access channel with noiseless feedback

An achievable region for the two-user discrete memoryless multiple-access channel (DMMAC) with noiseless feedback is proposed. The proposed region includes the Cover-Leung region, with the inclusion being, for some channels, strict. This inner bound is demonstrated for the ideal two-user Poisson multiple-access channel with noiseless feedback, in which case it is shown to improve on the Cover-Leung rate-sum.     

Bounds on the achievable rates of block coding for a memoryless multiple-access channel

Block coding for a memoryless two-input single-output multiple-access channel, called a two-user adder channel, is studied. Techniques for constructing codes for this particular channel are presented. Upper and lower bounds on the achievable rates of these codes are derived. These bounds define various two-dimensional regions for the achievable rates of codes for the two-user adder channel.     

Turbo codes for nonuniform memoryless sources over noisy channels

This work addresses the problem of designing turbo codes for nonuniform binary memoryless or independent and identically distributed (i.i.d.) sources over noisy channels. The extrinsic information in the decoder is modified to exploit the source redundancy in the form of nonuniformity; furthermore, the constituent encoder structure is optimized for the considered nonuniform i.i.d. source to further enhance the system performance. Some constituent encoders are found to substantially outperform Berrou's (1996) (37, 21) encoder. Indeed, it is shown that the bit error rate (BER) performance of the newly designed turbo codes is greatly improved as significant coding gains are obtained     

Computation of total capacity for discrete memoryless multiple-access channels

The Arimoto-Blahut (1972) algorithm is generalized for computation of the total capacity of discrete memoryless multiple-access channels (MAC). In addition, a class of MAC is defined with the property that the uniform distribution achieves the total capacity. These results are based on the specialization of the Kuhn-Tucker condition for the total capacity of the MAC, and an extension of a known symmetry property for single-user channels.     

A hierarchy of codes for memoryless channels (Corresp.)

Channel block codes are shown to have a fine hierarchical structure with respect to the expurgated exponent. Another hierarchy with respect to the random coding exponent is also discussed.     

A low-rate bound on the reliability of a quantum discrete memoryless channel

We extend a low-rate improvement of the random coding bound on the reliability of a classical discrete memoryless channel (DMC) to its quantum counterpart. The key observation that we make is that the problem of bounding below the error exponent for a quantum channel relying on the class of stabilizer codes is equivalent to the problem of deriving error exponents for a certain symmetric classical channel.     

Bounds on achievable rates of LDPC codes used over the binary erasure channel

We derive upper bounds on the maximum achievable rate of low-density parity-check (LDPC) codes used over the binary erasure channel (BEC) under Gallager's decoding algorithm, given their right-degree distribution. We demonstrate the bounds on the ensemble of right-regular LDPC codes and compare them with an explicit left-degree distribution constructed from the given right degree.     

Parity-check density versus performance of binary linear block codes over memoryless symmetric channels

We derive lower bounds on the density of parity-check matrices of binary linear codes which are used over memoryless binary-input output-symmetric (MBIOS) channels. The bounds are expressed in terms of the gap between the rate of these codes for which reliable communications is achievable and the channel capacity; they are valid for every sequence of binary linear block codes if there exists a decoding algorithm under which the average bit-error probability vanishes. For every MBIOS channel, we construct a sequence of ensembles of regular low-density parity-check (LDPC) codes, so that an upper bound on the asymptotic density of their parity-check matrices scales similarly to the lower bound. The tightness of the lower bound is demonstrated for the binary erasure channel by analyzing a sequence of ensembles of right-regular LDPC codes which was introduced by Shokrollahi, and which is known to achieve the capacity of this channel. Under iterative message-passing decoding, we show that this sequence of ensembles is asymptotically optimal (in a sense to be defined in this paper), strengthening a result of Shokrollahi. Finally, we derive lower bounds on the bit-error probability and on the gap to capacity for binary linear block codes which are represented by bipartite graphs, and study their performance limitations over MBIOS channels. The latter bounds provide a quantitative measure for the number of cycles of bipartite graphs which represent good error-correction codes.     

Permutation codes for discrete channels (Corresp.)

A class of nonlinear codes for discrete channels is defined with the use of permutation groups. Several examples of such codes are given; their parameters are similar to those for Reed-Solomon codes in some cases. Decoding algorithms are discussed.     

Lower bounds on the quantum capacity and highest error exponent of general memoryless channels

Tradeoffs between the information rate and fidelity of quantum error-correcting codes are discussed. Quantum channels to be considered are those subject to independent errors and modeled as tensor products of copies of a general completely positive (CP) linear map, where the dimension of the underlying Hilbert space is a prime number. On such a quantum channel, the highest fidelity of a quantum error-correcting code of length n and rate R is proven to be lower-bounded by 1-exp[-nE(R)+o(n)] for some function E(R). The E(R) is positive below some threshold R/sub 0/, a direct consequence of which is that R/sub 0/ is a lower bound on the quantum capacity. This is an extension of the author's earlier result. While the earlier work states the result for the depolarizing channel and a slight generalization of it (Pauli channels), the result of this work applies to general discrete memoryless channels, including channel models derived from a physical law of time evolution.     

The discrete memoryless multiple-access channel with cribbing encoders

The capacity regions are determined for various communication situations in which one or both encoders for a multiple access channel crib from the other encoder and learn the channel input(s) (to be) emitted by this encoder. Most of the achievability proofs in this paper hinge upon the new concept of backward decoding. Also, the notion of Shannon strategies seems to be of crucial importance. It is demonstrated that in some situations parts of the total cooperation line are achievable. Moreover, it is proved that if the encoders and the decoder are allowed to be nondeterministic, the capacity regions are not increased.     

On the converse to the coding theorem for discrete memoryless channels (Corresp.)

A new lower bound on the probability of decoding error for the case of rates above capacity is presented. It forms a natural companion to Gallager's random coding bound for rates below capacity. The strong converse to the coding theorem follows immediately from the proposed lower bound.     

获取高斯MIMO广播信道和容量域的一种方法

针对脏纸编码方法很难直接计算广播信道和容量域边界值问题,提出了一种计算多接入信道和容量的迭代注水算法以及获取最大和容量的次优传输策略,利用广播信道与多接入信道的对偶性,将该和容量结果和传输策略通过简单的映射关系转换成广播信道和容量的边界值和优化传输策略。数值结果表明所提的迭代算法简单有效,给出的传输策略可以有效逼近广播信道理论和容量边界,在MIMO下行链路中可得到应用。     

On the design of algebraic space-time codes for MIMO block-fading channels

The availability of multiple transmit antennas allows for two-dimensional channel codes that exploit the spatial transmit diversity. These codes were referred to as space-time codes by Tarokh et al. (see ibid., vol.44, p.744-765, Mar. 1998) Most prior works on space-time code design have considered quasi-static fading channels. We extend our earlier work on algebraic space-time coding to block-fading channels. First, we present baseband design criteria for space-time codes in multi-input multi-output (MIMO) block-fading channels that encompass as special cases the quasi-static and fast fading design rules. The diversity advantage baseband criterion is then translated into binary rank criteria for phase shift keying (PSK) modulated codes. Based on these binary criteria, we construct algebraic space-time codes that exploit the spatial and temporal diversity available in MIMO block-fading channels. We also introduce the notion of universal space-time codes as a generalization of the smart-greedy design rule. As a part of this work, we establish another result that is important in its own right: we generalize the full diversity space-time code constructions for quasi-static channels to allow for higher rate codes at the expense of minimal reductions in the diversity advantage. Finally, we present simulation results that demonstrate the excellent performance of the proposed codes.