Constant weight codes can arise from an input process sampled from a periodic Markov chain. A previous result showed that, in general, polarization does not occur for inputoutput processes with an underlying periodic Markov chain. In this work, we show that if we fix the initial state of an underlying periodic Markov chain, polarization does occur. Fixing the initial state is aligned with ensuring a constant weight code.

A transform that is universally polarizing over a set of channels with memory is presented. Memory may be present in both the input to the channel and the channel itself. Both the encoder and the decoder are aware of the input distribution, which is fixed. However, only the decoder is aware of the actual channel being used. The transform can be used to design a universal code for this scenario. The code is to have vanishing error probability when used over any channel in the set, and achieve the infimal information rate over the set. The setting considered is, in fact, more general: we consider a set of processes with memory. Universal polarization is established for the case where each process in the set: (a) has memory in the form of an underlying hidden Markov state sequence that is aperiodic and irreducible, and (b) satisfies a ’forgetfulness’ property. Forgetfulness, which we believe to be of independent interest, occurs when two hidden Markov states become approximately independent of each other given a sufficiently long sequence of observations between them. We show that aperiodicity and irreducibility of the underlying Markov chain is not sufficient for forgetfulness, and develop a sufficient condition for a hidden Markov process to be forgetful.

Polar codes were originally specified for codelengths that are powers of two. In many applications, it is desired to have a code that is not restricted to such lengths. Two common strategies of modifying the length of a code are shortening and puncturing. Simple and explicit schemes for shortening and puncturing were introduced by Wang and Liu, and by Niu, Chen, and Lin, respectively. In this paper, we prove that both schemes yield polar codes that are capacity achieving. Moreover, the probability of error for both the shortened and the punctured polar codes decreases to zero at the same exponential rate as seminal polar codes. These claims hold for all codelengths large enough.

A list decoding scheme for universal polar codes is presented. Our scheme applies to the universal polar codes first introduced by ŗaşoğlu and Wang, and generalized to processes with memory by the authors. These codes are based on the concatenation of different polar transforms: a sequence of "slow" transforms and Arıkan's original "fast" transform. List decoding of polar codes has been previously presented in the context of the fast transform. However, the slow transform is markedly different and requires new techniques and data structures. We show that list decoding is possible with space complexity O(L·N) and time complexity O(L·Nlog N), where N is the overall blocklength and L is the list size.

A transform that is universally polarizing over a set of channels with memory is presented. Memory may be present in both the channel and its input. Both the encoder and the decoder are aware of the input distribution, which is fixed. Only the decoder is aware of the actual channel being used. The transform is used to design a universal code for this scenario. The code is to have vanishing error probability when used over any channel in the set, and achieve the infimal information rate over the set. Universal polarization is established under two key properties: memory in the form of an underlying hidden Markov state sequence that is aperiodic and irreducible and a new property: forgetfulness.

Fast polarization is crucial for the performance guarantees of polar codes. In the memoryless setting, the rate of polarization is known to be exponential in the square root of the block length. A complete characterization of the rate of polarization for models with memory has been missing. Namely, previous works have not addressed fast polarization of the high entropy set under memory. We consider polar codes for processes with memory that are characterized by an underlying ergodic finite-state Markov chain. We show that the rate of polarization for these processes is the same as in the memoryless setting, both for the high and for the low entropy sets.

Polar codes are a family of capacity-achieving codes that have explicit and low-complexity construction, encoding, and decoding algorithms. Decoding of polar codes is based on the successive-cancellation decoder, which decodes in a bit-wise manner. A decoding error occurs when at least one bit is erroneously decoded. The various codeword bits are correlated, yet performance analysis of polar codes ignores this dependence: the upper bound is based on the union bound, and the lower bound is based on the worst-performing bit. Improvement of the lower bound is afforded by considering error probabilities of two bits simultaneously. These are difficult to compute explicitly due to the large alphabet size inherent to polar codes. In this paper, we propose a method to lower-bound the error probabilities of bit pairs. We develop several transformations on pairs of synthetic channels that make the resultant synthetic channels amenable to alphabet reduction. Our method yields lower bounds that significantly improve upon currently known lower bounds for polar codes under successive-cancellation decoding.

Fast polarization is crucial for the performance guarantees of polar codes. In the memoryless setting, the rate of polarization is known to be exponential in the square root of the block length. A complete characterization of the rate of polarization for models with memory has been missing. We consider polar codes for processes with memory that are characterized by an underlying aperiodic and irreducible finite state Markov chain. We show that the rate of polarization for these processes is the same as in the memoryless setting, both to the high and to the low-entropy sets. Thus, polar codes achieve the Markov capacity in many information-theoretic applications.

Consider a polar code designed for some binary memoryless symmetric channel. We develop a lower bound on the probability of error of this polar code under successive-cancellation decoding. The bound exploits the correlation between the various codeword bits and improves upon existing lower bounds.

A design of robust error-correcting codes that achieve reliable communication over various channels is of great theoretical and practical interest. Such codes are termed universal. This paper considers the universality of low-density parity-check (LDPC) code ensembles over families of memoryless binary-input output-symmetric (MBIOS) channels. Universality is considered both under belief-propagation (BP) and maximum-likelihood (ML) decoding. For the BP decoding case, we derive a density-evolution-based analytical method for designing LDPC code ensembles that are universal over various families of MBIOS channels. We also derive a necessary condition for universality of LDPC code ensembles under BP decoding; this condition is used to provide bounds on the universally achievable fraction of capacity. These results enable us to provide conditions for reliable/unreliable communications under BP decoding that are based on the Bhattacharyya parameter of the channel. For the ML decoding case, we prove that properly selected regular LDPC code ensembles are universally capacity-achieving for the set of equi-capacity MBIOS channels and extend this result to punctured regular LDPC code ensembles.

A universal design of low-density parity-check (LDPC) code ensembles which enables to operate reliably over various channels is of great theoretical and practical interest. This paper considers the universality of LDPC code ensembles over multitude memoryless binary-input output-symmetric (MBIOS) channels, addressing their universality under belief-propagation (BP) decoding. Based on the density evolution approach, analytical results related to the universality of LDPC code ensembles under BP decoding are derived; these results are expressed in closed form, and are easy to calculate. The full paper version related to this work provides further results, full proofs, additional discussions on the theorems, and it also considers the universality issue under ML decoding.