pith. sign in

arxiv: 2604.15295 · v1 · submitted 2026-04-16 · 💻 cs.IT · math.IT

Reed--Muller Codes Achieve the Symmetric Capacity on Finite-State Channels

Henry D. Pfister , Navin Kashyap , Jean-Francois Chamberland , Galen Reeves This is my paper

Pith reviewed 2026-05-10 09:38 UTC · model grok-4.3

classification 💻 cs.IT math.IT
keywords Reed-Muller codesfinite-state channelssymmetric capacitydoubly-transitive codesinterleavingchannel codinggroup codescapacity achievement
0
0 comments X

The pith

Reed-Muller codes achieve the symmetric capacity of binary-input finite-state channels.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper establishes that sequences of binary Reed-Muller codes, after random scrambling, achieve the symmetric capacity of binary-input indecomposable finite-state channels. It proceeds by first proving a capacity-via-symmetry theorem for doubly-transitive group codes on non-binary discrete memoryless channels under symmetry and puncturing conditions, then reducing the finite-state channel to an almost memoryless non-binary channel through adjacent bit grouping and interleaving, and finally showing that the required non-binary codes arise from a single binary RM code. A sympathetic reader cares because this shows algebraic codes can reach the uniform-input rate limit on channels with memory using symmetry properties alone, extending prior results limited to memoryless settings. The approach avoids explicit state tracking at the encoder while still attaining the target rate.

Core claim

We show that a sequence of binary RM codes (with some random scrambling) can achieve the symmetric capacity (or uniform-input information rate) of a binary-input indecomposable FSC. Our approach has three components. First, we establish a capacity-via-symmetry theorem for doubly-transitive group codes on discrete memoryless channels (DMCs) with non-binary inputs, under some symmetry and puncturing conditions. Then, we reduce a binary-input FSC to an almost memoryless non-binary channel by grouping adjacent input bits into blocks and interleaving non-binary codes onto the channel. Finally, we show that the interleaved non-binary codes can be constructed from a single binary RM code.

What carries the argument

The capacity-via-symmetry theorem for doubly-transitive group codes on non-binary DMCs, applied after reducing the FSC to an almost memoryless channel by bit grouping and interleaving.

Load-bearing premise

The reduction of the binary-input FSC via bit grouping and interleaving preserves the symmetry and puncturing conditions required by the capacity-via-symmetry theorem.

What would settle it

A calculation showing that the error probability of scrambled binary RM codes fails to approach zero at rates approaching the symmetric capacity on a concrete indecomposable FSC such as a first-order Markov channel.

Figures

Figures reproduced from arXiv: 2604.15295 by Galen Reeves, Henry D. Pfister, Jean-Francois Chamberland, Navin Kashyap.

Figure 1
Figure 1. Figure 1: Bits to blocks to interleaves for N = 32 bits grouped into blocks of b = 2h bits (e.g., with h = 1) and d = 2g interleaves (e.g., with g = 2). The last row shows a single representative interleave of 4 protected blocks after decimation by d. is denoted by E[Z], and the probability of event E is P(E). The total-variation distance between distributions P and Q on a finite set Z is ∥P − Q∥TV := 1 2 X z∈Z |P(z… view at source ↗
read the original abstract

We study reliable communication over finite-state channels (FSCs) using Reed--Muller (RM) codes. Building on recent symmetry-based analyses for memoryless channels, we show that a sequence of binary RM codes (with some random scrambling) can achieve the symmetric capacity (or uniform-input information rate) of a binary-input indecomposable FSC. Our approach has three components. First, we establish a capacity-via-symmetry theorem for doubly-transitive group codes on discrete memoryless channels (DMCs) with non-binary inputs, under some symmetry and puncturing conditions. Then, we reduce a binary-input FSC to an almost memoryless non-binary channel by grouping adjacent input bits into blocks and interleaving non-binary codes onto the channel. Finally, we show that the interleaved non-binary codes can be constructed from a single binary RM code.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

2 major / 2 minor

Summary. The manuscript claims that a sequence of binary Reed-Muller codes, augmented with random scrambling, achieves the symmetric capacity (uniform-input mutual information rate) of any binary-input indecomposable finite-state channel. The proof is organized in three steps: (i) a capacity-via-symmetry theorem establishing that doubly-transitive group codes achieve capacity on non-binary DMCs satisfying suitable symmetry and puncturing conditions; (ii) a reduction that converts the original FSC into an approximately memoryless non-binary channel by grouping k consecutive input bits and interleaving; and (iii) a construction showing that the required non-binary interleaved codes can be realized from a single binary RM code.

Significance. If the central claim is established with the necessary error bounds, the result would constitute a meaningful extension of recent symmetry-based achievability theorems from memoryless channels to channels with memory. It supplies an explicit, algebraically structured coding scheme for a broad class of FSCs without relying on random coding arguments, which is of both theoretical and practical interest for modeling channels with intersymbol interference or fading. The three-component strategy cleanly separates the symmetry analysis from the channel reduction and code construction, and the manuscript correctly identifies the indecomposability assumption as the key property that permits the reduction to succeed asymptotically.

major comments (2)
  1. Reduction step (second component of the proof strategy): the claim that bit grouping plus interleaving produces a channel to which the exact DMC symmetry theorem applies requires a quantitative bound showing that the residual memory between successive non-binary symbols vanishes sufficiently fast. Without an explicit rate (e.g., total variation or mutual-information distance to the memoryless limit) and a corresponding continuity argument for the symmetric capacity, it is not immediate that the o(1) gap vanishes; this is load-bearing for transferring the DMC result to the FSC setting.
  2. Construction of interleaved non-binary codes from binary RM codes (third component): the manuscript must verify that the random scrambling and interleaving preserve the doubly-transitive group action and the puncturing conditions required by the symmetry theorem. If the effective group action on the non-binary alphabet is only approximately transitive, the capacity-via-symmetry statement may hold only up to an additional error term that again needs explicit control.
minor comments (2)
  1. The abstract and introduction would benefit from a concise statement of the main theorem (including the precise definition of symmetric capacity for the FSC) before describing the three-component strategy.
  2. Notation for the grouped non-binary channel (e.g., the alphabet size and the precise interleaving map) should be introduced with a short diagram or equation to improve readability.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for the positive evaluation of the manuscript's significance and for the constructive major comments. These highlight the need for more explicit quantitative details in the proof. We will revise the manuscript to incorporate the requested bounds and verifications, strengthening the rigor of the reduction and construction steps without altering the central claims.

read point-by-point responses

  1. Referee: Reduction step (second component of the proof strategy): the claim that bit grouping plus interleaving produces a channel to which the exact DMC symmetry theorem applies requires a quantitative bound showing that the residual memory between successive non-binary symbols vanishes sufficiently fast. Without an explicit rate (e.g., total variation or mutual-information distance to the memoryless limit) and a corresponding continuity argument for the symmetric capacity, it is not immediate that the o(1) gap vanishes; this is load-bearing for transferring the DMC result to the FSC setting.

    Authors: We agree that an explicit quantitative analysis is necessary to make the transfer rigorous. In the revised manuscript we will insert a new lemma in the channel-reduction section that bounds the total-variation distance between the grouped-and-interleaved channel and its memoryless counterpart by O(ρ^k), where k is the grouping length and ρ<1 is the mixing rate guaranteed by indecomposability. We will then prove a continuity statement for the symmetric capacity under this perturbation, showing that the capacity difference is at most a constant multiple of the total-variation distance. Together these establish that the o(1) gap vanishes as k→∞, allowing the DMC symmetry theorem to apply directly in the limit. revision: yes

  2. Referee: Construction of interleaved non-binary codes from binary RM codes (third component): the manuscript must verify that the random scrambling and interleaving preserve the doubly-transitive group action and the puncturing conditions required by the symmetry theorem. If the effective group action on the non-binary alphabet is only approximately transitive, the capacity-via-symmetry statement may hold only up to an additional error term that again needs explicit control.

    Authors: The construction realizes an exact (not approximate) doubly-transitive action on the non-binary alphabet. Random scrambling is performed at the binary level prior to grouping; the subsequent interleaver is a fixed, deterministic permutation that respects the algebraic structure of the Reed-Muller code, thereby inducing a doubly-transitive group action on the grouped symbols. The puncturing conditions required by the symmetry theorem are likewise satisfied exactly because the underlying binary RM code is punctured in a manner compatible with the block grouping. We will expand the construction section with a formal verification of these properties, confirming that no additional error term is introduced. revision: yes

Circularity Check

0 steps flagged

Minor invocation of prior symmetry theorems; no load-bearing self-definition, fitted prediction, or reduction to inputs by construction.

full rationale

The derivation proceeds by first proving a new capacity-via-symmetry theorem for non-binary DMCs under group-transitivity and puncturing conditions, then applying a bit-grouping plus interleaving reduction to convert the indecomposable FSC into an approximately memoryless non-binary channel, and finally embedding the non-binary codewords into a single scrambled binary RM code. None of these steps defines the target symmetric capacity in terms of itself, renames a fitted quantity as a prediction, or relies on a self-citation chain whose only justification is the present paper. The cited prior symmetry results are treated as external inputs rather than derived within the manuscript, and the approximation error in the memoryless reduction is acknowledged as a separate technical step rather than assumed away by definition. This yields only a low-level self-citation score with no circular reduction of the central claim.

Axiom & Free-Parameter Ledger

0 free parameters · 2 axioms · 0 invented entities

The central claim rests on standard information-theoretic assumptions about channel indecomposability and code symmetry without introducing new fitted parameters or postulated entities.

axioms (2)
  • domain assumption The finite-state channel is indecomposable
    Required for the symmetric capacity to be well-defined and for the achievability result to hold.
  • domain assumption Symmetry and puncturing conditions hold for the non-binary DMC obtained by grouping
    Invoked to apply the capacity-via-symmetry theorem to the reduced channel.

pith-pipeline@v0.9.0 · 5450 in / 1183 out tokens · 56338 ms · 2026-05-10T09:38:22.092964+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

52 extracted references · 52 canonical work pages

  1. [1]

    Application of Boolean algebra to switching circuit design and to error detection,

    D. Muller, “Application of Boolean algebra to switching circuit design and to error detection,”IRE Trans. Inform. Theory, vol. EC-3, pp. 6–12, Sept. 1954

    work page 1954

  2. [2]

    A class of multiple-error-correcting codes and the decoding scheme,

    I. Reed, “A class of multiple-error-correcting codes and the decoding scheme,”IRE Trans. Inform. Theory, vol. 4, pp. 38–49, September 1954

    work page 1954

  3. [3]

    Reed-Muller codes for random erasures and errors,

    E. Abbe, A. Shpilka, and A. Wigderson, “Reed-Muller codes for random erasures and errors,”IEEE Trans. Inform. Theory, vol. 61, pp. 5229– 5252, Oct 2015

    work page 2015

  4. [4]

    Reed-Muller codes achieve capacity on erasure channels,

    S. Kudekar, S. Kumar, M. Mondelli, H. D. Pfister, E. ¸ Sa¸ so ˘glu, and R. Urbanke, “Reed-Muller codes achieve capacity on erasure channels,” inProc. of the Annual ACM Symp. on Theory of Comp., 2016

    work page 2016

  5. [5]

    Reed-Muller codes achieve capacity on erasure channels,

    S. Kudekar, S. Kumar, M. Mondelli, H. D. Pfister, E. ¸ Sa¸ so ˘glu, and R. Urbanke, “Reed-Muller codes achieve capacity on erasure channels,” IEEE Trans. Inform. Theory, vol. 63, no. 7, pp. 4298–4316, 2017

    work page 2017

  6. [6]

    Reed-Muller codes polarize,

    E. Abbe and M. Ye, “Reed-Muller codes polarize,”IEEE Trans. Inform. Theory, vol. 66, no. 12, pp. 7311–7332, 2020

    work page 2020

  7. [7]

    On codes decoding a constant fraction of errors on the BSC,

    J. H ˛ azła, A. Samorodnitsky, and O. Sberlo, “On codes decoding a constant fraction of errors on the BSC,” inProc. of the Annual ACM Symp. on Theory of Comp., pp. 1479–1488, 2021

    work page 2021

  8. [8]

    Reed–Muller codes on BMS channels achieve vanishing bit-error probability for all rates below capacity,

    G. Reeves and H. D. Pfister, “Reed–Muller codes on BMS channels achieve vanishing bit-error probability for all rates below capacity,”IEEE Trans. Inform. Theory, 2023

    work page 2023

  9. [9]

    A proof that Reed-Muller codes achieve Shannon capacity on symmetric channels,

    E. Abbe and C. Sandon, “A proof that Reed-Muller codes achieve Shannon capacity on symmetric channels,” inProc. IEEE Symp. on the Found. of Comp. Sci., pp. 177–193, 2023

    work page 2023

  10. [10]

    Achieving capacity on non-binary channels with generalized Reed–Muller codes,

    G. Reeves and H. D. Pfister, “Achieving capacity on non-binary channels with generalized Reed–Muller codes,” inProc. IEEE Int. Symp. Inform. Theory, 2023

    work page 2023

  11. [11]

    Proof of Shannon’s transmission theorem for finite-state indecomposable channels,

    D. Blackwell, L. Breiman, and A. J. Thomasian, “Proof of Shannon’s transmission theorem for finite-state indecomposable channels,”Ann. Math. Stats., vol. 29, pp. 1209–1220, Dec. 1958

    work page 1958

  12. [12]

    The capacity of a class of channels,

    D. Blackwell, L. Breiman, and A. J. Thomasian, “The capacity of a class of channels,”Ann. Math. Stats., pp. 1229–1241, 1959

    work page 1959

  13. [13]

    R. G. Gallager,Information Theory and Reliable Communication. New York, NY, USA: Wiley, 1968

    work page 1968

  14. [14]

    Capacity and coding for Gilbert-Elliott channels,

    M. Mushkin and I. Bar-David, “Capacity and coding for Gilbert-Elliott channels,”IEEE Trans. Inform. Theory, vol. 35, pp. 1277–1290, Nov. 1989

    work page 1989

  15. [15]

    Capacity, mutual information, and coding for finite-state Markov channels,

    A. J. Goldsmith and P. P. Varaiya, “Capacity, mutual information, and coding for finite-state Markov channels,”IEEE Trans. Inform. Theory, vol. 42, pp. 868–886, May 1996

    work page 1996

  16. [16]

    On the achievable information rates of finite state ISI channels,

    H. D. Pfister, J. B. Soriaga, and P. H. Siegel, “On the achievable information rates of finite state ISI channels,” inProc. IEEE Global Telecom. Conf., (San Antonio, TX, USA), pp. 2992–2996, Nov. 2001

    work page 2001

  17. [17]

    Determining and approach- ing achievable rates of binary intersymbol interference channels using multistage decoding,

    J. B. Soriaga, H. D. Pfister, and P. H. Siegel, “Determining and approach- ing achievable rates of binary intersymbol interference channels using multistage decoding,”IEEE Trans. Inform. Theory, vol. 53, pp. 1416– 1429, April 2007

    work page 2007

  18. [18]

    A BCJR-DFE based receiver for achieving near capacity performance on inter symbol interference chan- nels,

    K. R. Narayanan and N. Nangare, “A BCJR-DFE based receiver for achieving near capacity performance on inter symbol interference chan- nels,” inProc. 42nd Annual Allerton Conf. on Commun., Control, and Comp., (Monticello, IL, USA), pp. 763–772, Oct. 2004

    work page 2004

  19. [19]

    Capacity of a burst-noise channel,

    E. N. Gilbert, “Capacity of a burst-noise channel,”The Bell Syst. Techn. J., vol. 39, pp. 1253–1265, Sept. 1960

    work page 1960

  20. [20]

    Estimates of error rates for codes on burst-noise channels,

    E. O. Elliott, “Estimates of error rates for codes on burst-noise channels,” The Bell Syst. Techn. J., vol. 42, pp. 1977–1997, Sept. 1963

    work page 1977

  21. [21]

    Finite-state Markov channel–a useful model for radio communication channels,

    H. S. Wang and N. Moayeri, “Finite-state Markov channel–a useful model for radio communication channels,”IEEE Trans. Vehicular Tech- nology, vol. 44, no. 1, pp. 163–171, 1995

    work page 1995

  22. [22]

    Finite- state Markov modeling of fading channels - a survey of principles and applications,

    P. Sadeghi, R. A. Kennedy, P. B. Rapajic, and R. Shams, “Finite- state Markov modeling of fading channels - a survey of principles and applications,”IEEE Signal Processing Mag., vol. 25, no. 5, pp. 57–80, 2008

    work page 2008

  23. [23]

    Near Shannon limit error-correcting coding and decoding: Turbo-codes,

    C. Berrou, A. Glavieux, and P. Thitimajshima, “Near Shannon limit error-correcting coding and decoding: Turbo-codes,” inProc. IEEE Int. Conf. Commun., vol. 2, (Geneva, Switzerland), pp. 1064–1070, IEEE, May 1993

    work page 1993

  24. [24]

    Iterative correction of intersymbol interference: Turbo equalization,

    C. Douillard, M. Jézéquel, C. Berrou, A. Picart, P. Didier, and A. Glavieux, “Iterative correction of intersymbol interference: Turbo equalization,”Eur. Trans. Telecom., vol. 6, pp. 507–511, Sept. – Oct. 1995

    work page 1995

  25. [25]

    Low density parity check codes for magnetic recording,

    J. L. Fan., A. Friedmann, E. Kurtas, and S. W. McLaughlin, “Low density parity check codes for magnetic recording,” inProc. 37th Annual Allerton Conf. on Commun., Control, and Comp., (Monticello, IL, USA), pp. 1314–1323, Sept. 1999

    work page 1999

  26. [26]

    Turbo decoding for partial response channels,

    T. Souvignier, M. Öberg, P. H. Siegel, R. E. Swanson, and J. K. Wolf, “Turbo decoding for partial response channels,”IEEE Trans. Commun., vol. 48, pp. 1297–1308, Aug. 2000

    work page 2000

  27. [27]

    Binary intersymbol interfer- ence channels: Gallager codes, density evolution and code performance bounds,

    A. Kav ˇci´c, X. Ma, and M. Mitzenmacher, “Binary intersymbol interfer- ence channels: Gallager codes, density evolution and code performance bounds,”IEEE Trans. Inform. Theory, vol. 49, pp. 1636–1652, July 2003

    work page 2003

  28. [28]

    On the information rate of binary-input channels with memory,

    D. Arnold and H. Loeliger, “On the information rate of binary-input channels with memory,” inProc. IEEE Int. Conf. Commun., (Helsinki, Finland), pp. 2692–2695, June 2001

    work page 2001

  29. [29]

    Simulation-based computation of information rates for channels with memory,

    D. Arnold, H. A. Loeliger, P. O. V ontobel, A. Kav ˇci´c, and W. Zeng, “Simulation-based computation of information rates for channels with memory,”IEEE Trans. Inform. Theory, vol. 52, pp. 3498–3508, Aug. 2006

    work page 2006

  30. [30]

    Accumulate–repeat–accumulate codes: Capacity-achieving ensembles of systematic codes for the erasure chan- nel with bounded complexity,

    H. D. Pfister and I. Sason, “Accumulate–repeat–accumulate codes: Capacity-achieving ensembles of systematic codes for the erasure chan- nel with bounded complexity,”IEEE Trans. Inform. Theory, vol. 53, pp. 2088–2115, June 2007

    work page 2088

  31. [31]

    On the capacity of Markov sources over noisy channels,

    A. Kav ˇci´c, “On the capacity of Markov sources over noisy channels,” in Proc. IEEE Global Telecom. Conf., (San Antonio, TX, USA), pp. 2997– 3001, Nov. 2001

    work page 2001

  32. [32]

    On near-capacity coding systems for partial-response channels,

    J. B. Soriaga and P. H. Siegel, “On near-capacity coding systems for partial-response channels,” inProc. IEEE Int. Symp. Inform. Theory, (Chicago, IL, USA), p. 267, June 2004

    work page 2004

  33. [33]

    A generalization of the Blahut–Arimoto algorithm to finite-state channels,

    P. O. V ontobel, A. Kav ˇci´c, D. M. Arnold, and H. A. Loeliger, “A generalization of the Blahut–Arimoto algorithm to finite-state channels,” IEEE Trans. Inform. Theory, vol. 54, no. 5, pp. 1887–1918, 2008

    work page 1918

  34. [34]

    A randomized algorithm for the capacity of finite-state chan- nels,

    G. Han, “A randomized algorithm for the capacity of finite-state chan- nels,”IEEE Trans. Inform. Theory, vol. 61, no. 7, pp. 3651–3669, 2015

    work page 2015

  35. [35]

    A deterministic algorithm for the capacity of finite-state channels,

    C. Wu, G. Han, V . Anantharam, and B. H. Marcus, “A deterministic algorithm for the capacity of finite-state channels,”IEEE Trans. Inform. Theory, vol. 68, no. 3, pp. 1465–1479, 2022

    work page 2022

  36. [36]

    Threshold saturation on channels with memory via spatial coupling,

    S. Kudekar and K. Kasai, “Threshold saturation on channels with memory via spatial coupling,” inProc. IEEE Int. Symp. Inform. Theory, (St. Petersburg, Russia), pp. 2562–2566, July 2011

    work page 2011

  37. [37]

    Threshold saturation of spatially-coupled codes on intersymbol-interference chan- nels,

    P. S. Nguyen, A. Yedla, H. D. Pfister, and K. R. Narayanan, “Threshold saturation of spatially-coupled codes on intersymbol-interference chan- nels,” inProc. IEEE Int. Conf. Commun., (Ottawa, Canada), pp. 2209– 2214, June 2012

    work page 2012

  38. [38]

    Spatially-coupled codes approach symmetric information rate of finite-state Markov fading channels,

    H. Abe and K. Kasai, “Spatially-coupled codes approach symmetric information rate of finite-state Markov fading channels,” inProc. IEEE Int. Symp. Inform. Theory, pp. 2719–2723, 2016

    work page 2016

  39. [39]

    Construction of polar codes for channels with memory,

    R. Wang, J. Honda, H. Yamamoto, R. Liu, and Y . Hou, “Construction of polar codes for channels with memory,” inProc. IEEE Inform. Theory Workshop, pp. 187–191, 2015

    work page 2015

  40. [40]

    Polar coding for processes with memory,

    E. ¸ Sa¸ so˘glu and I. Tal, “Polar coding for processes with memory,” in Proc. IEEE Int. Symp. Inform. Theory, pp. 225–229, 2016

    work page 2016

  41. [41]

    Polar coding for processes with memory,

    E. ¸ Sa¸ so˘glu and I. Tal, “Polar coding for processes with memory,”IEEE Trans. Inform. Theory, vol. 65, no. 4, pp. 1994–2003, 2019

    work page 1994

  42. [42]

    Coding schemes based on Reed- Muller codes for(d,∞)-RLL input-constrained channels,

    V . A. Rameshwar and N. Kashyap, “Coding schemes based on Reed- Muller codes for(d,∞)-RLL input-constrained channels,”IEEE Trans- actions on Information Theory, vol. 69, no. 11, pp. 7003–7024, 2023

    work page 2023

  43. [43]

    Reed–Muller Codes,

    E. Abbe, O. Sberlo, A. Shpilka, and M. Ye, “Reed–Muller Codes,” Foundations and Trends® in Communications and Information Theory, vol. 20, no. 1–2, pp. 1–156, 2023

    work page 2023

  44. [44]

    Capacity on BMS channels via code symmetry and nesting,

    H. D. Pfister and G. Reeves, “Capacity on BMS channels via code symmetry and nesting,” 2025. [Online]. Available: https://arxiv.org/abs/2504.15394

    work page arXiv 2025

  45. [45]

    Capacity- approaching bandwidth-efficient coded modulation schemes based on low-density parity-check codes,

    J. Hou, P. H. Siegel, L. B. Milstein, and H. D. Pfister, “Capacity- approaching bandwidth-efficient coded modulation schemes based on low-density parity-check codes,”IEEE Trans. Inform. Theory, vol. 49, pp. 2141–2155, Sept. 2003

    work page 2003

  46. [46]

    Achieving capacity on non-binary chan- nels with generalized Reed–Muller codes,

    G. Reeves and H. D. Pfister, “Achieving capacity on non-binary chan- nels with generalized Reed–Muller codes,” 2023. [Online]. Available: https://arxiv.org/abs/2305.07779. APPENDIXA PROOF OFLEMMA6 Proof of Lemma 6.Let Φbe the uniform state-transition ma- trix and let E :={(s, s ′)∈ S 2 : Φs,s′ >0} be the directed edge set of its support graph. Note that Φ...

    work page arXiv 2023

  47. [47]

    For (A1), letπbe any permutation automorphism of RM(r, m−h)and consider the matrix representation of a codeword ofI m as described in Definition 35

    Conditions (A1) and (A2) hold forI m. For (A1), letπbe any permutation automorphism of RM(r, m−h)and consider the matrix representation of a codeword ofI m as described in Definition 35. Applyingπ simultaneously to every row of the matrix sends (c(0), . . . ,c(b−1))7→(πc (0), . . . , πc(b−1)), which is again a valid codeword ofI m because eachπc (j) remai...

    work page

  48. [48]

    Thus, if the rows ofxarec (0),

    Applying the affine mapσ A,β :F b 2 →F b 2, defined by σA,β(u) =Au+β, to a codewordx∈ I m symbolwise is equivalent to applying the linear mapAto each column in the matrix representation ofx, followed by adding the constant vectorβ. Thus, if the rows ofxarec (0), . . . ,c(h−1), then the transformed rows are ec(i) = b−1X j=0 Aijc(j) +β i1, i∈[h]. SinceRM(r,...

    work page

  49. [49]

    Assumption(A3)is exactly the standing assumption that the channelW(y|x)is injective

    Condition (A3). Assumption(A3)is exactly the standing assumption that the channelW(y|x)is injective

    work page

  50. [50]

    Take any integer sequenceg m → ∞such that gm =o( √m)

    Condition (A4) forI m. Take any integer sequenceg m → ∞such that gm =o( √m). Using the standard RM affine-subspace restriction argument, puncturingRM(r m, m−h)to a codimension-g m affine sub- space produces RM(rm, m−h−g m). Applying this rowwise toI m gives a punctured codeI ′ m on an index setJ m ⊆[N m]with0∈J m and |Jm| Nm →0. Moreover, the same argumen...

    work page

  51. [51]

    We have verified(A1)–(A4)for the sequence{I m}

    Apply Theorem 34 toI m. We have verified(A1)–(A4)for the sequence{I m}. Since R(Im)→R < C, Theorem 34 implies that the maximal symbol-error rate under symbol-MAP decoding on the channel W ⊗Nm satisfies max i∈[Nm] SERIm(Xi |Y)→0

    work page

  52. [52]

    By Lemma 36, we have Bm ⊆ I m

    Pass fromI m toB m. By Lemma 36, we have Bm ⊆ I m. Hence, by Lemma 38, it follows that max i∈[Nm] SERBm(Xi |Y)≤max i∈[Nm] SERIm(Xi |Y). The right-hand side tends to zero, so the same is true for the blocked RM code. This proves Theorem 23. APPENDIXE EXPONENTIALMIXING OFMARKOVCHAIN Definition 39.A finite-state Markov chain with transition matrixP∈R d×d + i...

    work page