From Bit to Block: Decoding on Erasure Channels

Henry D. Pfister ∗, Oscar Sprumont †, Gilles Zémor ‡ · 2025

Read From Bit to Block: Decoding on Erasure Channels by Henry D. Pfister ∗, Oscar Sprumont †, Gilles Zémor ‡ (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2501-05748.txt.

Introduction

Henry Pfister and co-authors give a general frame for bounding when a code fails as a whole block on an erasure channel, based on when single bits fail. Erasure channels drop symbols outright, a clean model for lost data. Their 2025 frame turns on the support weights of small subcodes inside the code.

For each small dimension, they study the least support weight among subcodes of that size. Those numbers link the bit level threshold to the block level one. As a proof of concept, they use the frame to re-derive a famed result: Reed-Muller codes reach channel capacity on the erasure channel for block error. The method may serve other code families too.

Catalog record

CREATORHenry D. Pfister ∗, Oscar Sprumont †, Gilles Zémor ‡
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE30 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2501-05748

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

From Bit to Block: Decoding on Erasure Channels Henry D. Pfister ∗, Oscar Sprumont †, Gilles Zémor ‡ Abstract . We provide a general framework for bounding the block error threshold of a linear code C ⊆ 𝔽 2 N C\subseteq\mathbb{F}_{2}^{N} over the erasure channel in terms of its bit error threshold. Our approach relies on understanding the minimum support weight of any r r -dimensional subcode of C C , for all small values of r r . As a proof of concept, we use our machinery to obtain a new proof of the celebrated result that Reed–Muller codes achieve capacity on the erasure channel with respect to block error probability. 1. Introduction We will be interested in the performance of linear codes over noisy communication channels. Ever since Shannon’s seminal paper [ Sha48 ] , information theorists have spent considerable time and effort designing codes that achieve capacity , i.e. codes C\subseteq\mathbb{F}_{2}^{N} that approach the optimal tradeoff between their rate R:=\frac{\log_{2}|C|}{N} and the amount of noise they can tolerate. Shannon’s probabilistic argument [ Sha48 ] established that uniform random codes achieve capacity on both the binary symmetric channel and the erasure channel. The first explicit families of codes to provably achieve capacity were only obtained decades later, when Forney introduced concatenated codes [ For66 ] . More recently, Arikan showed that polar codes - which have both a deterministic construction and efficient encoding and decoding algorithms - achieve capacity on all memoryless channels [ Ari09 ] . This brought renewed attention to the closely related Reed–Muller codes, which were shown to achieve capacity on the binary symmetric channel and the erasure channel in [ ASW15 , KKM+17 , KKM+16 , RP24 , AS23b , AS23a ] . The proof that Reed–Muller codes of constant rate achieve capacity on the erasure channel [ KKM+17 , KKM+16 ] relies heavily on the double transitivity of their automorphism group. In fact, Kudekar, Kumar, Mondelli, Pfister, Şaşoğlu and Urbanke showed in [ KKM+17 ] that any doubly transitive linear code achieves capacity under bit-MAP decoding. A very natural question is then to understand whether or not the bit and block error thresholds of doubly transitive codes are asymptotically equal. (By the result of [ KKM+17 ] , this is equivalent to asking whether or not every doubly transitive code achieves capacity on the erasure channel under block-MAP decoding.) 1.1. Main Results Our main contribution is to develop a framework for bounding the gap between a code’s bit and block error thresholds on the erasure channel. Let C\subseteq\mathbb{F}_{2}^{N} be any linear code. We show that if, for all integers r<r_{0} (where r_{0} depends on the sharpness of the bit threshold of C ), any r -dimensional subcode of C has support 1 1 1 The support of a subcode S\subseteq C is the set of indices j\in[N] where at least one codeword c\in S has c_{j}=1 . growing faster than r\log N , then the block error threshold of C is close to its bit error threshold. An informal version of our main result is stated below. For the formal version, see Theorem 7 . Theorem 1 (Informal) . Consider any linear code C\subseteq\mathbb{F}_{2}^{N} and suppose that a uniform random codeword c\in C is sent over the erasure channel with erasure probability p\in[0,1] . Let \delta\in[0,1] be such that, for every i\in[N] , the probability we fail to decode the i^{\textnormal{th}} coordinate of c is bounded by \displaystyle\Pr_{p\textnormal{-erasures}}\Big[\textnormal{cannot recover }c_{i}\Big]\leq\delta. Suppose additionally that for all r=1,2,\dotsc,\sqrt{\delta}N , the support of any r -dimensional subcode of C has size \omega(r\log N). Then there exists p^{\prime}=p-o(1) such that the probability we fail to decode the codeword c from erasures with probability p^{\prime} is bounded by \displaystyle\Pr_{p^{\prime}\textnormal{-erasures}}\Big[\textnormal{cannot recover }c\Big]\leq\sqrt{\delta}+o(1). As a proof of concept, we show in Section 5 that Reed–Muller codes of constant rate satisfy the conditions of Theorem 1 . Our analysis relies on the work of Wei, who obtained in [ Wei91 ] exact expressions for the minimum support weight of any r -dimensional subcode of a Reed–Muller code. Bounding these expressions appropriately and combining them with Theorem 1 gives an alternative proof that Reed–Muller codes achieve capacity on the erasure channel under block-MAP decoding, a fact that was shown by Kudekar, Kumar, Mondelli, Pfister, Şaşoğlu and Urbanke in [ KKM+17 , KKM+16 ] . See Theorem 11 . We note that one key argument in the proof of [ KKM+16 ] is the claim that the low-weight codewords of Reed-Muller codes do not contribute much to the decoding error probability, and thus one only needs to worry about codewords of high weight. In order to prove this claim, [ KKM+16 ] relies on a very careful analysis of Reed–Muller codes’ weight enumerator, which may be difficult to generalize to other codes. In contrast, our approach only requires somewhat loose bounds on the minimum support weight of any subcode. For r<N^{1-o(1)} , we need any r -dimensional subcode to have support weight larger than r\log N ; for constant-rate Reed–Muller codes, it turns out that any such subcode has support weight larger than r2^{(\log N)^{0.99}} (see Corollary 10 ). 1.2. Techniques Our proof of Theorem 1 is based on a well-known work of Tillich and Zémor [ TZ00 ] , who established sharp threshold results for the symmetric and erasure channels. For a linear code C\subseteq\mathbb{F}_{2}^{N} and a string x\in\{0,1\}^{N} , we define (1) \displaystyle S_{C}(x):=\Big\{c\in C:c_{i}\leq x_{i}\textnormal{ for all }i\in[N]\Big\} to be the set of codewords that are indistinguishable from the 0 -vector once you erase all coordinates i\in[N] where x_{i}=1 . Note that S_{C}(x) is a subcode of C . Tillich and Zémor showed in [ TZ00 ] that for any fixed r\in\{1,2,\dotsc,\textnormal{dim }C\} , the function (2) \displaystyle f_{r}(p):=\Pr_{x\sim p}\Big[\textnormal{dim }S_{C}(x)\geq r\Big] transitions rapidly from \approx 0 to \approx 1 as a function of p , where x\sim p denotes a p -noisy random string x\in\{0,1\}^{N}. They also showed that for any r , the curves f_{r}(p) and f_{r+1}(p) stay within a distance of about \frac{1}{\sqrt{d_{r}(C)}} from each other, where d_{r}(C) denotes the minimum support weight of any r -dimensional subcode of C . In this work, we first strengthen their result to show that the curves f_{r}(p) and f_{r+1}(p) in fact stay within a distance of about \frac{1}{d_{r}(C)} from each other (see the proof of Theorem 6 ). We then leverage the fact that every doubly transitive code achieves capacity under bit-MAP decoding to prove that for some r_{0}=N^{1-o(1)} , the function f_{r_{0}} corresponding to any doubly transitive code C\subseteq\mathbb{F}_{2}^{N} satisfies \displaystyle f_{r_{0}}\Big(1-\textnormal{rate}(C)-o(1)\Big)=o(1). Since the distance between the curves f_{r}(p) and f_{r+1}(p) can be bounded in terms of the minimum support weight d_{r}(C) , we are then able to prove (see Theorem 8 ) that the function f_{1}(p) corresponding to any doubly transitive code C\subseteq\mathbb{F}_{2}^{N} with large enough minimum support weights satisfies (3) \displaystyle f_{1}\Big(1-\textnormal{rate}(C)-o(1)\Big)=o(1). But the left hand side above is exactly the probability that a sent codeword c\in C can be uniquely recovered from random erasures of probability 1-\textnormal{rate}(C)-o(1) , so equation ( 3 ) shows that any doubly transitive linear code C\subseteq\mathbb{F}_{2}^{N} with large enough minimum support weights \{d_{r}(C)\} achieves capacity on the erasure channel under

Read the complete text