Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userCapacity-Achieving Rate-Compatible Polar Codes for General Channels
147
0
0.0
(
0
)
Added by
Marco Mondelli
Publication date
2016
fields
Informatics Engineering
and research's language is
English
Ask ChatGPT about the research
No Arabic abstract
We present a rate-compatible polar coding scheme that achieves the capacity of any family of channels. Our solution generalizes the previous results [1], [2] that provide capacity-achieving rate-compatible polar codes for a degraded family of channels. The motivation for our extension comes from the fact that in many practical scenarios, e.g., MIMO systems and non-Gaussian interference, the channels cannot be ordered by degradation. The main technical contribution of this paper consists in removing the degradation condition. To do so, we exploit the ideas coming from the construction of universal polar codes. Our scheme possesses the usual attractive features of polar codes: low complexity code construction, encoding, and decoding; super-polynomial scaling of the error probability with the block length; and absence of error floors. On the negative side, the scaling of the gap to capacity with the block length is slower than in standard polar codes, and we prove an upper bound on the scaling exponent.
rate research
Read More
Polar codes are the first class of constructive channel codes achieving the symmetric capacity of the binary-input discrete memoryless channels. But the corresponding code length is limited to the power of two. In this paper, we establish a systematic framework to design the rate-compatible punctured polar (RCPP) codes with arbitrary code length. A new theoretic tool, called polar spectra, is proposed to count the number of paths on the code tree with the same number of zeros or ones respectively. Furthermore, a spectrum distance SD0 (SD1) and a joint spectrum distance (JSD) are presented as performance criteria to optimize the puncturing tables. For the capacity-zero puncturing mode (punctured bits are unknown to the decoder), we propose a quasi-uniform puncturing algorithm, analyze the number of equivalent puncturings and prove that this scheme can maximize SD1 and JSD. Similarly, for the capacity-one mode (punctured bits are known to the decoder), we also devise a reversal quasi-uniform puncturing scheme and prove that it has the maximum SD0 and JSD. Both schemes have a universal puncturing table without any exhausted search. These optimal RCPP codes outperform the performance of turbo codes in LTE wireless communication systems.
Polar codes are introduced for discrete memoryless broadcast channels. For $m$-user deterministic broadcast channels, polarization is applied to map uniformly random message bits from $m$ independent messages to one codeword while satisfying broadcast constraints. The polarization-based codes achieve rates on the boundary of the private-message capacity region. For two-user noisy broadcast channels, polar implementations are presented for two information-theoretic schemes: i) Covers superposition codes; ii) Martons codes. Due to the structure of polarization, constraints on the auxiliary and channel-input distributions are identified to ensure proper alignment of polarization indices in the multi-user setting. The codes achieve rates on the capacity boundary of a few classes of broadcast channels (e.g., binary-input stochastically degraded). The complexity of encoding and decoding is $O(n*log n)$ where $n$ is the block length. In addition, polar code sequences obtain a stretched-exponential decay of $O(2^{-n^{beta}})$ of the average block error probability where $0 < beta < 0.5$.
A method is proposed, called channel polarization, to construct code sequences that achieve the symmetric capacity $I(W)$ of any given binary-input discrete memoryless channel (B-DMC) $W$. The symmetric capacity is the highest rate achievable subject to using the input letters of the channel with equal probability. Channel polarization refers to the fact that it is possible to synthesize, out of $N$ independent copies of a given B-DMC $W$, a second set of $N$ binary-input channels ${W_N^{(i)}:1le ile N}$ such that, as $N$ becomes large, the fraction of indices $i$ for which $I(W_N^{(i)})$ is near 1 approaches $I(W)$ and the fraction for which $I(W_N^{(i)})$ is near 0 approaches $1-I(W)$. The polarized channels ${W_N^{(i)}}$ are well-conditioned for channel coding: one need only send data at rate 1 through those with capacity near 1 and at rate 0 through the remaining. Codes constructed on the basis of this idea are called polar codes. The paper proves that, given any B-DMC $W$ with $I(W)>0$ and any target rate $R < I(W)$, there exists a sequence of polar codes ${{mathscr C}_n;nge 1}$ such that ${mathscr C}_n$ has block-length $N=2^n$, rate $ge R$, and probability of block error under successive cancellation decoding bounded as $P_{e}(N,R) le bigoh(N^{-frac14})$ independently of the code rate. This performance is achievable by encoders and decoders with complexity $O(Nlog N)$ for each.
This paper presents a coding scheme for an insertion deletion substitution channel. We extend a previous scheme for the deletion channel where polar codes are modified by adding guard bands between segments. In the new scheme, each guard band is comprised of a middle segment of 1 symbols, and left and right segments of 0 symbols. Our coding scheme allows for a regular hidden-Markov input distribution, and achieves the information rate between the input and corresponding output of such a distribution. Thus, we prove that our scheme can be used to efficiently achieve the capacity of the channel. The probability of error of our scheme decays exponentially in the cube-root of the block length.
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 blocklength 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.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
