Pith. sign in

REVIEW 3 major objections 4 minor 15 references

Error-Building Decoding of Linear Block Codes

T0 review · 3 major / 4 minor · reviewed 2026-08-03 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read This paper claims a maximum-likelihood decoding framework, error-building decoding (EBD), that needs no trellis or code list—only the parity-check matrix—and for extended Hamming codes runs at roughly a tenth of trellis Viterbi's floating-p

desk verdict Core EBD recursion is sound but the optimized decoder's ML guarantee rests on unproved claims in Appendix B, leaving Table I's 10x reduction conditional. read the letter →

arxiv 2601.02330 v2 pith:3KGGQVEZ submitted 2026-01-05 cs.IT math.IT

Guoda Qiu , Ling Liu , Yuejun Wei , Liping Li This is my paper · ORCID
classification cs.ITmath.IT
keywords error-buildingdecodingmaximum-likelihoodsoft-decisionlinearblockcodesparity-checkmatrixextendedHammingrecursiveconstructionsyndromecomplexity
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

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

The reading

The paper tries to establish that maximum-likelihood soft-decision decoding of any linear block code can be done using only the parity-check matrix, with no precomputed trellis, codebook, or error-pattern list. It does this by recasting ML decoding as the search for a globally optimal "error-building block": a multiset of parity-check column indices whose XOR gives the received syndrome, with cost equal to the sum of absolute LLRs of those positions. A recursive theorem lets larger optimal blocks be built from smaller ones, and a customized version for extended Hamming codes adds offline and online pruning that the paper claims preserves the ML guarantee. If correct, the fully optimized decoder needs on average only about 10% of the floating-point operations of minimum-edge trellis Viterbi decoding for extended Hamming codes of lengths 64, 128, and 256 at FER 10^-3. A sympathetic reader would care because it promises near-universal, parameter-light ML decoding with a complexity profile that improves as the channel improves.

What carries the argument

The load-bearing object is the error-building block: a multiset of indices of parity-check matrix columns whose modulo-2 sum equals a target syndrome, with block penalty equal to the sum of the absolute LLRs of its elements. The recursive theorem (Theorem 2) is the engine: it constructs a locally optimal block of size t1+t2 by combining locally optimal blocks of sizes t1 and t2 for a decomposition vector chosen to minimize total penalty, turning ML decoding into a dynamic-programming-like search over at most Q block sizes. The optimized version replaces locally optimal blocks O_t(v) with pruned target blocks Z_t(v), whose construction is governed by offline exclusions (algebraically empty bl

What would settle it

Run an exhaustive syndrome-coset search for a small extended Hamming code, say (64,57,4), on random LLR vectors: compute the minimum penalty over all error patterns for each syndrome and compare it with the penalty returned by EBD-FullOpt; any mismatch disproves O(s)=Z_Q(s). A more direct check is to enumerate all error-building blocks of size t for a fixed received vector and test whether Claim 3—that the pruned target block penalty never falls below the locally optimal block penalty—is ever violated.

Watch

Extended reading notes

Core claim

The central claim is that ML soft-decision decoding reduces to finding the globally optimal error-building block O(s) for the syndrome s of the hard-decision vector: the decoded codeword is c_ML = b XOR e_ML, where e_ML is the error pattern whose support is the reduced form of O(s). Theorem 1 bounds the search to the first Q locally optimal block sizes, where Q is the number of parity bits. Theorem 2 gives a recursive construction: an optimal (t1+t2)-block is obtained by combining optimal t1- and t2-blocks for a decomposition vector that minimizes the sum of their penalties. For extended Hamming codes, the paper defines pruned "target" blocks Z_t(v) via offline exclusion (blocks fixed empty

Load-bearing premise

The optimized decoder's ML guarantee rests on unproved structural claims—chiefly that pruned target blocks never discard a block needed for optimality and that every even-sized zero-syndrome block is safely excludable—so if any of those assertions fails, EBD-FullOpt is no longer provably maximum-likelihood.

Editorial extensions

If this is right

  • If Theorem 3 holds, any linear block code can be soft-decision ML decoded from its parity-check matrix alone, without trellis diagrams or precomputed error-pattern lists.
  • For extended Hamming codes, the fully optimized EBD claims average FLOP counts of about 11.1%, 10.3%, and 10.3% of minimum-edge trellis Viterbi for (64,57,4), (128,120,4), and (256,247,4) at FER 10^-3.
  • Because online exclusion prunes using the best-so-far syndrome block, average decoding cost decreases as Eb/N0 increases, so the decoder becomes cheaper precisely when the channel is good.
  • The recursive construction is general, and the paper shows that codes with exploitable parity-check structure—such as extended Hamming's all-ones row—can be customized for substantial additional complexity reduction.
  • The framework opens a route to ML decoding for code families where trellis construction is expensive, as long as the redundancy Q is small enough to keep the 2^Q search space manageable.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • The block-multiset view suggests a natural connection to reliability-ordered syndrome decoding: EBD's recursion can be read as an adaptive search over column dependencies of the parity-check matrix, which may yield comparable ML guarantees for other algebraic code families beyond extended Hamming codes.
  • The sharpest testable extension is exhaustive enumeration on small codes: comparing pruned Z_Q(s) against the true minimum penalty over all error patterns for each syndrome would either upgrade the unproved Appendix B claims into verified theorems or produce a concrete counterexample.
  • The FLOP comparisons are algorithmic and averaged over syndromes; a hardware-oriented implementation would face additional overheads and data-dependent control flow, so practical speedups may differ from the claimed ratios even if the ML guarantee is correct.
  • Because online exclusion makes cost depend on the received reliabilities, EBD could be adapted as an anytime or early-exit decoder whose average energy consumption scales with channel quality, a property not explored in the paper.
Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

3 major / 4 minor

Summary. The paper proposes error-building decoding (EBD), a soft-decision ML decoding framework that operates only from the parity-check matrix. Error patterns are represented as multisets of columns of the parity-check matrix (error-building blocks), and the optimal error pattern is found by searching for the globally optimal block for the syndrome. Theorem 1 restricts the search to blocks of size at most Q, and Theorem 2 gives a recursive min-plus construction of larger locally optimal blocks. The authors then specialize EBD to extended Hamming codes, using offline and online exclusion mechanisms (EBD-OffOpt and EBD-FullOpt), and claim that the optimized decoder is still ML, with average FLOPs about 10% of minimum-edge trellis Viterbi decoding at FER=10^{-3} for lengths 64, 128, and 256. The main technical burden is the proof that the optimized construction still finds a globally optimal block.

Significance. If the ML guarantee for the optimized EBD holds, the paper offers a genuinely different route to ML soft-decision decoding: a syndrome-space dynamic program that needs no trellis or precomputed error-pattern list, and whose optimized version for extended Hamming codes has an order-of-magnitude lower average complexity than a standard trellis decoder. Theorems 1 and 2 are clearly stated, and the recursive construction is plausible and appears correct. The complexity analysis is detailed and the FER curves are consistent with an ML decoder. However, the central proof for the optimized decoder is not complete: Appendix B rests on unproved Claims 1–3, and Section IV-A contains a demonstrably false statement about even-sized blocks for syndrome zero. The significance of the paper is therefore contingent on a repaired proof that the exclusion mechanisms never discard the globally optimal block.

major comments (3)
  1. [Appendix B, Claims 1–3 and Proposition 1] The proof of O(s)=Z_Q(s), which is the ML guarantee for EBD-FullOpt, is incomplete. Claims 1–3 are stated without proof, and the induction for Proposition 1 uses them as black boxes. In particular, Claim 2 is load-bearing: inequality (14) requires that a subblock of a minimal flipping block is itself optimal for its own syndrome. This is true by a replacement argument (if a subblock could be replaced by a cheaper block with the same syndrome, the whole block would not be globally optimal), but that argument is absent. Claim 3 is also not proved, although it can be argued because every constructed Z is either empty or a valid block for its vector. As written, the appendix does not establish the ML guarantee, and Table I's comparison would only describe a heuristic if any of these claims fail. Please provide complete proofs of Claims 1–3 and make the induction fully explicit.
  2. [Section IV-A, offline exclusion of even-sized Z_t(0)] The statement 'even-sized locally optimal blocks for v=0 must consist of repeated elements with the least reliability' is false. For the (8,4,4) extended Hamming code, the four distinct columns (1,0), (1,1), (1,2), (1,3) in F_2^3 sum to zero; for any extended Hamming code of length at least 8, a weight-4 codeword in the code corresponds to four distinct columns of H summing to zero. Thus an even-sized optimal block for v=0 need not contain repeated elements. The offline exclusion of all even-sized Z_t(0) may be salvageable for decoding nonzero syndromes (a minimal flipping block for s≠0 cannot contain a zero-syndrome subblock, since removing it would lower the penalty), but that argument is not given. The stated justification is therefore wrong and needs to be replaced.
  3. [Section III-C, Eq. (11) and Appendix B] The notation for the online threshold is ambiguous and inconsistent. Section III-C defines a block that is 'the block with the minimum penalty among {Z_1(s),...,Z_t(s)}', which should be written as \bar Z_t(s), but Eq. (11) and the proof in Appendix B write M(Z_{t-1}(s)) without any bar. If the threshold in (11) is the single (t-1)-block rather than the running minimum over all previous target blocks, the online exclusion can discard a subblock whose penalty is below the current best but above the penalty of the (t-1)-block, breaking the ML guarantee. The Appendix B induction implicitly uses the running-minimum interpretation. Please define the threshold unambiguously and use one notation throughout.
minor comments (4)
  1. [Appendix C, optimized construction strategy] The optimized iterative construction in Appendix C is described algorithmically, but the general claim that it 'ensures that all even-sized or odd-sized Z_t(s) with t≤Q can be obtained' is not proved. For the specific lengths in Table I the schedules are listed, but a formal coverage argument would make the general claim (and Remark 1) verifiable.
  2. [Theorem 1 proof] The reduction argument for t'>Q does not explicitly treat the case v=0, where deleting a dependent subset could in principle remove all elements and leave the empty block. Since the decoder exits for s=0 and the argument is only needed for s≠0, this is a minor gap, but it should be stated.
  3. [Notation and typos] The notation 'Z t(s)' in Section III-C appears to be a missing overline; the text also alternates between 'Z_t(s)' as a specific t-block and as the minimum over previous blocks. Please clean up the notation and ensure definitions of W and Y are stated before they are used in Section IV-A.
  4. [Example in Section III-B] In the (15,11,3) example, the block J6,6,2K in B_3(3) is written with square brackets in one place ('[ [6,6,2] ]'), a typographical artifact. Also, the statement 'the total number of operations is 302' should clarify whether this counts additions and comparisons including +∞, since the subsequent sentence says the actual count is 268.

Circularity Check

0 steps flagged · score 0.0 of 10

No circular derivation chain: EBD's core claims are proven from external syndrome-decoding results and code-theoretic properties, not from fitted parameters or self-citation.

full rationale

The derivation chain is not circular. Lemma 1 (ML decoding as minimum-penalty error pattern search) is explicitly attributed to the independent result [5] and is not re-derived from the paper's own machinery. Theorem 1 follows from the rank constraint of the parity-check matrix; Theorem 2 is a recursive optimality argument whose proof compares an arbitrary composite block with sums of locally optimal subblocks; Theorem 3 is proved in Appendix A using Lemma 1 and the two-way relation between error-building blocks and error patterns. These are standard proof obligations rather than fitted-input predictions. The optimized decoder's claim O(s)=Z_Q(s) in Appendix B does rely on Claims 1–3, but Claim 3 is not an assumed version of the conclusion: it is a lower-bound statement that holds by Definition 3 whenever Z_t(v) is a valid t-error-building block (if Z_t(v) is empty its penalty is +∞, also no smaller than the locally optimal penalty). Claim 2 is asserted without proof, and a rigorous proof would be desirable—it is essentially a subblock-minimality fact derivable from global optimality—but an unproved lemma is a proof gap, not a circular equivalence. The FER/complexity comparisons are measured against external baselines: trellis Viterbi from [14] and Chase-II from [15]. No parameter is fitted to the reported FER values and then renamed a prediction; Table I reports simulated operation counts for fixed codes and SNR targets. The only mildly self-referential element, reference to the authors' own optimization strategy in Appendices C and D, is not load-bearing in the ML proof and does not substitute for an external result. Thus the central derivation is self-contained against independent benchmarks, and any concern about unproved Claims 1–3 in Appendix B belongs to correctness/completeness risk, not circularity.

Assumptions & free parameters 0 free parameters · 7 assumptions · 0 invented entities

The algorithm rests on standard linear algebra and the standard ML-to-syndrome formulation. The load-bearing non-standard assumptions are the unproved Claims 1-3 in Appendix B and the v=0 exclusion assertion in Section IV-A. There are no fitted numerical parameters and no invented physical entities.

assumptions (7)
  • domain assumption Lemma 1: minimizing pattern penalty Σ e[k]|λ[k]| is equivalent to ML decoding on the BPSK-AWGN channel.
    Invoked in Section II and used by every subsequent theorem; it is an external result cited to [5], not re-derived.
  • standard math The syndrome map s=H e^T = XOR of selected columns is a homomorphism; any error pattern for syndrome s corresponds to a subset of columns summing to s.
    Basis of the error-building block definition in Definition 1.
  • standard math Rank(H) ≤ Q=N-K, so any multiset of more than Q columns is linearly dependent over F2.
    Used in Theorem 1 to reduce the global search to t≤Q.
  • standard math Block penalties are nonnegative (sums of |λ[k]|), so removing a zero-sum submultiset cannot increase the penalty.
    Used in Theorem 1 and Appendix A to justify reduction from repeated-element blocks to distinct support sets.
  • domain assumption For extended Hamming codes, the first row of H is all ones, so v[0] gives the parity of the number of columns in any block for v.
    Drives the offline exclusion in Section IV-A: only even sizes for v[0]=0 and odd sizes for v[0]=1.
  • ad hoc to paper Claim 3 in Appendix B: M(Z_{\bar t}(v)) ≥ M(O_{\bar t}(v)) for all v and \bar t, and Claims 1-2 about minimal flipping blocks.
    Stated without proof in Appendix B and used to prove O(s)=Z_Q(s); if false, the optimized decoder may lose ML optimality.
  • ad hoc to paper All even-sized locally optimal blocks for v=0 are offline-excludable because they 'must consist of repeated elements with the least reliability'.
    Section IV-A, asserted without proof; not obviously true when weight-4 codewords give distinct-element blocks summing to zero.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Error-Building Decoding of Linear Block Codes." pith.science (2026). https://pith.science/paper/3KGGQVEZ

@misc{pith2026260102330,
  author       = {Pith},
  title        = {Pith review of: Error-Building Decoding of Linear Block Codes},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/3KGGQVEZ}},
  note         = {Machine review of arXiv:2601.02330}
}
abstract

This paper proposes a novel maximum-likelihood (ML) soft-decision decoding framework for linear block codes, termed error-building decoding (EBD). The complete decoding process can be performed using only the parity-check matrix, without requiring any other pre-constructed information (such as trellis diagrams or error-pattern lists), and it has the potential to be further customized if specific properties of the code can be exploited. We formally define error-building blocks, and derive a recursive theorem that allows efficient construction of larger locally optimal blocks from smaller ones, thereby effectively searching for the block associated with the most likely error pattern. The EBD framework is further optimized for extended Hamming codes as an example, through offline and online exclusion mechanisms, leading to a substantial complexity reduction without loss of ML performance. Complexity analysis shows that, for extended Hamming codes of lengths 64, 128, and 256, the fully optimized EBD requires approximately an order of magnitude fewer floating-point operations on average than minimum-edge trellis Viterbi decoding at a frame error rate (FER) of $10^{-3}$.

Figures

Figures reproduced from arXiv: 2601.02330 by the authors.

Figure 1
Figure 1. An example of decoding the (15, 11, 3) Hamming code using EBD. of any Ot(v) requiring evaluation with that of Zt(v), where Zt(v) denotes the target t-error-building block for v. Let Z t (s) denote the block with the minimum penalty among {Z1(s), Z2(s), . . . , Zt(s)}. Now, the decoding goal becomes selecting Z Q(s). The decoding process is detailed as follows. For any t and v, if Ot(v) can be determined prior to dec… view at source ↗
Figure 2
Figure 2. FER performance of extended Hamming codes of lengths 64, 128, [PITH_FULL_IMAGE:figures/full_fig_p005_2.png] view at source ↗
Figure 3
Figure 3. Decoding of the [PITH_FULL_IMAGE:figures/full_fig_p009_3.png] view at source ↗

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

15 extracted references

  1. [12]

    Optimal soft decision block decoders based on fast hadamard transform,

    Y . Be’ery and J. Snyders, “Optimal soft decision block decoders based on fast hadamard transform,”IEEE Transactions on Information Theory, vol. 32, no. 3, pp. 355–364, 1986

    1986

  2. [1]

    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

    1978

  3. [2]

    Minimal trellises for block codes,

    D. Muder, “Minimal trellises for block codes,”IEEE Transactions on Information Theory, vol. 34, no. 5, pp. 1049–1053, 1988

    1988

  4. [3]

    Coset codes. ii. binary lattices and related codes,

    G. Forney, “Coset codes. ii. binary lattices and related codes,”IEEE Transactions on Information Theory, vol. 34, no. 5, pp. 1152–1187, 1988

    1988

  5. [4]

    On the optimum bit orders with respect to the state complexity of trellis diagrams for binary linear codes,

    T. Kasami, T. Takata, T. Fujiwara, and S. Lin, “On the optimum bit orders with respect to the state complexity of trellis diagrams for binary linear codes,”IEEE Transactions on Information Theory, vol. 39, no. 1, pp. 242–245, 1993

    1993

  6. [5]

    Maximum likelihood soft decoding of binary block codes and decoders for the golay codes,

    J. Snyders and Y . Be’ery, “Maximum likelihood soft decoding of binary block codes and decoders for the golay codes,”IEEE Transactions on Information Theory, vol. 35, no. 5, pp. 963–975, 1989

    1989

  7. [6]

    On survivor error patterns for maximum likelihood soft decoding,

    J. Snyders, “On survivor error patterns for maximum likelihood soft decoding,” inProceedings. 1991 IEEE International Symposium on Information Theory, 1991, pp. 192–192

    1991

  8. [7]

    Reduced lists of error patterns for maximum likelihood soft decoding,

    ——, “Reduced lists of error patterns for maximum likelihood soft decoding,”IEEE Transactions on Information Theory, vol. 37, no. 4, pp. 1194–1200, 1991

    1991

Show all 15 references
  1. [8]

    Further results on survivor error patterns for maximum likelihood decoding,

    ——, “Further results on survivor error patterns for maximum likelihood decoding,” in2007 International Symposium on Signals, Systems and Electronics, 2007, pp. 331–334

    2007

  2. [9]

    Guessing noise, not code-words,

    K. R. Duffy, J. Li, and M. Médard, “Guessing noise, not code-words,” in2018 IEEE International Symposium on Information Theory (ISIT), 2018, pp. 671–675

    2018

  3. [10]

    Capacity-achieving guessing random additive noise decoding,

    ——, “Capacity-achieving guessing random additive noise decoding,” IEEE Transactions on Information Theory, vol. 65, no. 7, pp. 4023– 4040, 2019

    2019

  4. [11]

    Soft maximum likelihood decoding using grand,

    A. Solomon, K. R. Duffy, and M. Médard, “Soft maximum likelihood decoding using grand,” inICC 2020 - 2020 IEEE International Confer- ence on Communications (ICC), 2020, pp. 1–6

    2020

  5. [13]

    F. J. MacWilliams and N. J. A. Sloane,The Theory of Error-Correcting Codes, ser. North-Holland Mathematical Library. Amsterdam, The Netherlands: North-Holland, 1977, vol. 16

    1977

  6. [14]

    Extended hamming and bch soft decision decoders for mobile data applications,

    T. Tapp, A. Luna, X.-A. Wang, and S. Wicker, “Extended hamming and bch soft decision decoders for mobile data applications,”IEEE Transactions on Communications, vol. 47, no. 3, pp. 333–337, 1999

    1999

  7. [15]

    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. APPENDIXA PROOF OFTHEOREM3 We first prove the first part. Given a syndromes, each error patterne j satisfie...

    1972

Pith tools

Reviewed August 3, 2026 · model on record in the stance chip above.