pith. sign in

arxiv: 2605.20129 · v1 · pith:WX7ZMJHWnew · submitted 2026-05-19 · 💻 cs.IT · math.IT

Stochastic Chase Decoding for BMS Channels via Rate Distortion Theory

Amit Berman , Ariel Doubchak , Uri Erez , Tal Philosof , Ilya Shapir This is my paper

Pith reviewed 2026-05-20 03:15 UTC · model grok-4.3

classification 💻 cs.IT math.IT
keywords stochastic chase decodingrate-distortion theoryBMS channelserror pattern covering codesbit flippingalgebraic codeslist decoding
0
0 comments X

The pith

Rate-distortion theory provides an explicit asymptotically optimal bit-flipping rule for stochastic Chase decoding over BMS channels.

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

This paper shows how to replace heuristic choices in stochastic Chase decoding with rules derived from rate-distortion theory. It reinterprets the decoding process as a random-coding method for covering error patterns in the received word. A reader would care because this gives a principled way to choose which bits to flip and how many attempts to make so that the correct codeword is likely included in the list, leading to better performance on binary memoryless symmetric channels. The work adapts previous ideas from nonbinary erasure decoding to bit flips and validates the approach on short blocks for symmetric channels.

Core claim

We reinterpret stochastic Chase decoding as a random-coding construction for error-pattern covering codes. This yields an explicit characterization of the asymptotically optimal bit-flipping rule, together with the expected list size required to ensure that the transmitted codeword appears in the decoding list with high probability. For binary and quaternary symmetric channels, the optimal bit-flipping rule determined by exhaustive search closely matches the information-theoretic rule even at short block lengths.

What carries the argument

The adaptation of the rate-distortion formulation for generating bit-flip patterns that cover error patterns on BMS channels.

If this is right

  • The bit-flipping probabilities are chosen according to an information-theoretic rule derived from rate distortion.
  • The expected number of decoding attempts (list size) is determined to guarantee the transmitted codeword is covered with high probability.
  • For binary symmetric and quaternary symmetric channels, the theoretical rule agrees with exhaustive optimization even for short block lengths.
  • The approach provides a general method for designing stochastic Chase decoders for algebraic codes over BMS channels.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • This method may extend to other algebraic codes or decoding algorithms beyond Chase decoding.
  • Practical implementations could use the derived rules to improve error correction in communication systems without extensive tuning.
  • Further work might explore the finite-length performance on more general BMS channels.

Load-bearing premise

The rate-distortion formulation for erasure patterns on nonbinary channels can be directly adapted to bit-flip probabilities on BMS channels while preserving asymptotic optimality.

What would settle it

A simulation or calculation on a BMS channel where using the derived bit-flipping probabilities and list size fails to include the transmitted codeword in the list with high probability.

Figures

Figures reproduced from arXiv: 2605.20129 by Amit Berman, Ariel Doubchak, Ilya Shapir, Tal Philosof, Uri Erez.

Figure 1
Figure 1. Figure 1: Geometric view of stochastic Chase decoding. [PITH_FULL_IMAGE:figures/full_fig_p002_1.png] view at source ↗
Figure 2
Figure 2. Figure 2: Example of BMS channel with two reliability classes. [PITH_FULL_IMAGE:figures/full_fig_p004_2.png] view at source ↗
Figure 4
Figure 4. Figure 4: Flip probabilities vs. block length for M = 1 with the specified parameters [PITH_FULL_IMAGE:figures/full_fig_p005_4.png] view at source ↗
Figure 5
Figure 5. Figure 5: Flip probabilities vs. block length for M = 2 with the specified parameters [PITH_FULL_IMAGE:figures/full_fig_p005_5.png] view at source ↗
read the original abstract

This work develops a rate-distortion-based approach to stochastic Chase decoding of algebraic codes over binary memoryless symmetric (BMS) channels, replacing the heuristics traditionally used to determine flip probabilities with information-theoretically grounded flipping rules. In particular, we reinterpret stochastic Chase decoding as a random-coding construction for error-pattern covering codes. Our approach builds on the framework of Nguyen et al., who introduced a rate-distortion formulation of multiple-attempt decoding for Reed-Solomon codes over nonbinary channels. In their formulation, erasure patterns are generated so as to align with, and thereby mask, hard-decision errors. We adapt this framework to the design of bit-flip probabilities for Chase decoding over BMS channels. This yields an explicit characterization of the asymptotically optimal bit-flipping rule, together with the expected list size required to ensure that the transmitted codeword appears in the decoding list with high probability. Moreover, for binary and quaternary symmetric channels, we demonstrate that the optimal bit-flipping rule, determined by exhaustive search, closely matches the information-theoretic rule even at short block lengths.

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

1 major / 2 minor

Summary. The manuscript develops a rate-distortion-theoretic framework for stochastic Chase decoding of algebraic codes over binary memoryless symmetric (BMS) channels. It reinterprets the procedure as a random-coding construction for error-pattern covering codes, adapting the erasure-pattern formulation of Nguyen et al. to bit-flip probabilities. The central claims are an explicit characterization of the asymptotically optimal bit-flipping rule together with the expected list size needed for the transmitted codeword to appear in the list with high probability, plus an empirical demonstration that this rule closely matches the exhaustive-search optimum on binary and quaternary symmetric channels even at short block lengths.

Significance. If the adaptation of the rate-distortion construction is carried through correctly, the work supplies an information-theoretic justification for flip-probability design that replaces ad-hoc heuristics and yields both an asymptotic characterization and a verifiable short-block match. The explicit list-size expression and the reported agreement between the RD rule and exhaustive search constitute concrete, falsifiable contributions.

major comments (1)
  1. [Sections 3–4 (rate-distortion formulation and adaptation)] The central claim rests on a direct adaptation of the Nguyen et al. rate-distortion formulation. The manuscript must explicitly redefine the per-position distortion function and test channel so that a random flip vector f covers the channel error e precisely when the residual e ⊕ f has weight low enough for the algebraic decoder to succeed. If the same set-inclusion distortion is retained without adjustment for the XOR covering metric or for the position-dependent flip probabilities induced by BMS soft information, the resulting flip rule is not guaranteed to achieve the claimed covering probability or minimal list size asymptotically. This issue is load-bearing for both the asymptotic characterization and the short-block empirical match.
minor comments (2)
  1. Notation for the covering probability and the expected list size should be introduced once and used consistently; several passages reuse symbols from Nguyen et al. without redefinition.
  2. The exhaustive-search comparison for short blocks would benefit from an explicit statement of the block lengths, code parameters, and number of trials used to generate the reported match.

Simulated Author's Rebuttal

1 responses · 0 unresolved

We thank the referee for the careful and constructive review of our manuscript. We address the single major comment below and have revised the paper accordingly to strengthen the presentation of the rate-distortion adaptation.

read point-by-point responses

  1. Referee: [Sections 3–4 (rate-distortion formulation and adaptation)] The central claim rests on a direct adaptation of the Nguyen et al. rate-distortion formulation. The manuscript must explicitly redefine the per-position distortion function and test channel so that a random flip vector f covers the channel error e precisely when the residual e ⊕ f has weight low enough for the algebraic decoder to succeed. If the same set-inclusion distortion is retained without adjustment for the XOR covering metric or for the position-dependent flip probabilities induced by BMS soft information, the resulting flip rule is not guaranteed to achieve the claimed covering probability or minimal list size asymptotically. This issue is load-bearing for both the asymptotic characterization and the short-block empirical match.

    Authors: We thank the referee for highlighting this critical aspect of the adaptation. In the revised manuscript we explicitly replace the set-inclusion distortion of Nguyen et al. with a covering distortion defined by the residual error weight after XOR: d(f, e) = 0 if wt(e ⊕ f) ≤ t and d(f, e) = 1 otherwise, where t denotes the correction radius of the algebraic decoder. The test channel is likewise redefined as a non-stationary BMS channel whose per-position crossover probabilities are the flip probabilities p_i induced by the soft information; the rate-distortion function is then minimized over these position-dependent probabilities to obtain the asymptotically optimal flip rule. The expected list size follows directly from the resulting rate-distortion function evaluated at the covering distortion level. These definitions and the ensuing derivations have been added to Sections 3 and 4, together with a short paragraph contrasting the new distortion with the original erasure-pattern formulation. The asymptotic claims and the reported short-block agreement with exhaustive search remain unchanged. revision: yes

Circularity Check

0 steps flagged

No significant circularity; derivation adapts external RD framework to derive independent flip rule

full rationale

The paper explicitly builds on the rate-distortion formulation of Nguyen et al. for erasure patterns on nonbinary channels and adapts the covering construction to bit-flip probabilities on BMS channels. The asymptotically optimal flipping rule and list-size characterization are obtained by solving the adapted rate-distortion problem, not by fitting parameters to the target data or by renaming inputs. No load-bearing self-citation chain exists; the cited framework is external, and the paper validates the derived rule against exhaustive search on short blocks. The derivation therefore remains self-contained and does not reduce to its inputs by construction.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The central claim rests on the transferability of the Nguyen et al. rate-distortion covering construction to binary symmetric channels and on standard random-coding arguments for covering radius. No free parameters or new invented entities are visible in the abstract.

axioms (1)
  • domain assumption The rate-distortion formulation for generating erasure patterns that mask hard-decision errors extends without modification to bit-flip probabilities on BMS channels.
    Invoked when the abstract states that the framework is adapted to BMS channels.

pith-pipeline@v0.9.0 · 5721 in / 1271 out tokens · 31251 ms · 2026-05-20T03:15:20.972730+00:00 · methodology

discussion (0)

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

Lean theorems connected to this paper

Citations machine-checked in the Pith Canon. Every link opens the source theorem in the public Lean library.

What do these tags mean?
matches
The paper's claim is directly supported by a theorem in the formal canon.
supports
The theorem supports part of the paper's argument, but the paper may add assumptions or extra steps.
extends
The paper goes beyond the formal theorem; the theorem is a base layer rather than the whole result.
uses
The paper appears to rely on the theorem as machinery.
contradicts
The paper's claim conflicts with a theorem or certificate in the canon.
unclear
Pith found a possible connection, but the passage is too broad, indirect, or ambiguous to say the theorem truly supports the claim.

Reference graph

Works this paper leans on

23 extracted references · 23 canonical work pages

  1. [1]

    Trends in channel coding for 6G,

    S. Miao, C. Kestel, L. Johannsen, M. Geiselhart, L. Schmalen, A. Balatsoukas-Stimming, G. Liva, N. Wehn, and S. Ten Brink, “Trends in channel coding for 6G,”Proceedings of the IEEE, vol. 112, no. 7, pp. 653–675, 2024

    work page 2024

  2. [2]

    Rajab,Channel and Source Coding for Non-V olatile Flash Memories

    M. Rajab,Channel and Source Coding for Non-V olatile Flash Memories. Springer, 2020

    work page 2020

  3. [3]

    Per- formance comparison of short-length error-correcting codes,

    J. Van Wonterghem, A. Alloum, J. J. Boutros, and M. Moeneclaey, “Per- formance comparison of short-length error-correcting codes,” in2016 Symposium on Communications and V ehicular Technologies (SCVT). IEEE, 2016, pp. 1–6

    work page 2016

  4. [4]

    Soft-decision decoding of linear block codes based on ordered statistics,

    M. P. Fossorier and S. Lin, “Soft-decision decoding of linear block codes based on ordered statistics,”IEEE Transactions on Information Theory, vol. 41, no. 5, pp. 1379–1396, 1995

    work page 1995

  5. [5]

    Efficient maximum likelihood decoding of linear block codes using a trellis,

    J. Wolf, “Efficient maximum likelihood decoding of linear block codes using a trellis,”IEEE Transactions on Information Theory, vol. 24, no. 1, pp. 76–80, 1978

    work page 1978

  6. [6]

    Deep learning methods for improved decoding of linear codes,

    E. Nachmani, E. Marciano, L. Lugosch, W. J. Gross, D. Burshtein, and Y . Be’ery, “Deep learning methods for improved decoding of linear codes,”IEEE Journal of Selected Topics in Signal Processing, vol. 12, no. 1, pp. 119–131, 2018

    work page 2018

  7. [7]

    Algebraic soft-decision decoding of Reed- Solomon codes,

    R. Koetter and A. Vardy, “Algebraic soft-decision decoding of Reed- Solomon codes,”IEEE Transactions on Information Theory, vol. 49, no. 11, pp. 2809–2825, 2003

    work page 2003

  8. [8]

    New list decoding algorithms for Reed–Solomon and BCH codes,

    Y . Wu, “New list decoding algorithms for Reed–Solomon and BCH codes,”IEEE Transactions on Information Theory, vol. 54, no. 8, pp. 3611–3630, 2008

    work page 2008

  9. [9]

    Maximum-likelihood soft decision decoding of BCH codes,

    A. Vardy and Y . Be’ery, “Maximum-likelihood soft decision decoding of BCH codes,”IEEE Transactions on Information Theory, vol. 40, no. 2, pp. 546–554, 1994

    work page 1994

  10. [10]

    Class of algorithms for decoding block codes with channel measurement information,

    D. Chase, “Class of algorithms for decoding block codes with channel measurement information,”IEEE Transactions on Information Theory, vol. 18, no. 1, pp. 170–182, 1972

    work page 1972

  11. [11]

    An efficient maximum-likelihood-decoding algorithm for linear block codes with algebraic decoder,

    T. Kaneko, T. Nishijima, H. Inazumi, and S. Hirasawa, “An efficient maximum-likelihood-decoding algorithm for linear block codes with algebraic decoder,”IEEE Transactions on Information Theory, vol. 40, no. 2, pp. 320–327, 1994

    work page 1994

  12. [12]

    An improvement of soft- decision maximum-likelihood decoding algorithm using hard-decision bounded-distance decoding,

    T. Kaneko, T. Nishijima, and S. Hirasawa, “An improvement of soft- decision maximum-likelihood decoding algorithm using hard-decision bounded-distance decoding,”IEEE Transactions on Information Theory, vol. 43, no. 4, pp. 1314–1319, 1997

    work page 1997

  13. [13]

    Chase-type and GMD coset decodings,

    M. P. Fossorier and S. Lin, “Chase-type and GMD coset decodings,” IEEE Transactions on Communications, vol. 48, no. 3, pp. 345–350, 2000

    work page 2000

  14. [14]

    An efficient interpolation-based Chase BCH decoder,

    X. Zhang, “An efficient interpolation-based Chase BCH decoder,”IEEE Transactions on Circuits and Systems II: Express Briefs, vol. 60, no. 4, pp. 212–216, 2013

    work page 2013

  15. [15]

    On algebraic soft-decision decoding algorithms for BCH codes,

    N. Kamiya, “On algebraic soft-decision decoding algorithms for BCH codes,”IEEE Transactions on Information Theory, vol. 47, no. 1, pp. 45–58, 2001

    work page 2001

  16. [16]

    Limited-trial Chase-like algorithms achieving bounded-distance decoding,

    J. H. Weber and M. P. Fossorier, “Limited-trial Chase-like algorithms achieving bounded-distance decoding,”IEEE Transactions on Informa- tion Theory, vol. 50, no. 12, pp. 3318–3323, 2004

    work page 2004

  17. [17]

    Fast syndrome-based Chase decoding of binary BCH codes through Wu list decoding,

    Y . Shany and A. Berman, “Fast syndrome-based Chase decoding of binary BCH codes through Wu list decoding,”IEEE Transactions on Information Theory, vol. 69, no. 8, pp. 4907–4926, 2023

    work page 2023

  18. [18]

    Stochastic Chase decoding of Reed-Solomon codes,

    C. Leroux, S. Hemati, S. Mannor, and W. J. Gross, “Stochastic Chase decoding of Reed-Solomon codes,”IEEE Communications Letters, vol. 14, no. 9, pp. 863–865, 2010

    work page 2010

  19. [19]

    Stochastic Chase decod- ing of BCH codes,

    L. M. Harada, D. C. Cunha, and C. Pimentel, “Stochastic Chase decod- ing of BCH codes,” inProc. 11th Adv. Int. Conf. Telecommun.(AICT), 2015, pp. 11–13

    work page 2015

  20. [20]

    Selection method of test patterns in soft-decision iterative bounded distance de- coding algorithms,

    H. Tokushige, T. Koumoto, M. P. Fossorier, and T. Kasami, “Selection method of test patterns in soft-decision iterative bounded distance de- coding algorithms,”IEICE transactions on fundamentals of electronics, communications and computer sciences, vol. 86, no. 10, pp. 2445–2451, 2003

    work page 2003

  21. [21]

    On multiple decoding attempts for Reed–Solomon codes: A rate-distortion approach,

    P. S. Nguyen, H. D. Pfister, and K. R. Narayanan, “On multiple decoding attempts for Reed–Solomon codes: A rate-distortion approach,”IEEE Transactions on Information Theory, vol. 57, no. 2, pp. 668–691, 2011

    work page 2011

  22. [22]

    Capacity-achieving guessing random additive noise decoding,

    K. R. Duffy, J. Li, and M. M ´edard, “Capacity-achieving guessing random additive noise decoding,”IEEE Transactions on Information Theory, vol. 65, no. 7, pp. 4023–4040, 2019

    work page 2019

  23. [23]

    Cover and J

    T. Cover and J. Thomas,Elements of Information Theory, 2nd ed. Hoboken, NJ: Wiley-Interscience, 2006

    work page 2006