2015/04/22 by Erdal Arıkan, Arıkan, Erdal · 1 citation
Biochemistry, Genetics and Molecular Biology · Computer Science · Mathematics · #Cooperative Communication and Network Coding #DNA and Biological Computing #Error Correcting Code Techniques #FOS: Computer and information sciences #Information Theory (cs.IT) #cs.IT #math.IT
paper · pdf · doi:10.48550/arxiv.1504.05793
5 pages. To be presented at 2015 IEEE International Symposium on Information Theory, June 14-19, 2015, Hong Kong. Minor corrections to v2
openalex publication_date 2015/04/22 · arxiv created 2015/05/02 · arxiv updated 2015/05/05 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
A packing lemma is proved using a setting where the channel is a binary-input discrete memoryless channel (X,w(y|x),Y), the code is selected at random subject to parity-check constraints, and the decoder is a joint typicality decoder. The ensemble is characterized by (i) a pair of fixed parameters (H,q) where H is a parity-check matrix and q is a channel input distribution and (ii) a random parameter S representing the desired parity values. For a code of length n, the constraint is sampled from pS(s) = ∑_xn∈ Xn ϕ(s,xn)qn(xn) where ϕ(s,xn) is the indicator function of event \s = xn HT\ and qn(xn) = ∏i=1nq(xi). Given S=s, the codewords are chosen conditionally independently from pXn|S(xn|s) ∝ ϕ(s,xn) qn(xn). It is shown that the probability of error for this ensemble decreases exponentially in n provided the rate R is kept bounded away from I(X;Y)-(1)/(n)I(S;Yn) with (X,Y)∼ q(x)w(y|x) and (S,Yn)∼ pS(s)∑xn pXn|S(xn|s) ∏i=1n w(yi|xi). In the special case where H is the parity-check matrix of a standard polar code, it is shown that the rate penalty (1)/(n)I(S;Yn) vanishes as n increases. The paper also discusses the relation between ordinary polar codes and random codes based on polar parity-check matrices.