{"id":"ef1f1095-16de-4755-8241-12e090c9dd68","arxiv_id":"2601.02330","paper_version":2,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":5.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"A recursive 'error-building' dynamic program over the syndrome space decodes any binary linear block code to maximum likelihood using only the parity-check matrix, and code-specific pruning cuts its cost by roughly 10x on extended Hamming codes.","lead":"This paper describes a new maximum-likelihood decoding method for binary linear block codes that builds candidate error patterns recursively using only the parity-check matrix. For short extended Hamming codes, it reports about ten times fewer floating-point operations than trellis Viterbi decoding at a frame error rate of 10^-3.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Optimized EBD's ML guarantee rests on unproved Claims 1–3 in Appendix B; if any fail, pruning can discard the ML block and Table I's complexity is for a heuristic decoder.","rationale":"The reader's weakest assumption points to the unproved Claims 1–3 in Appendix B, which is exactly the main load-bearing gap. I agree that the optimized decoder's ML guarantee is not rigorously established. However, I do not see a demonstrated counterexample, and the Section IV-A assertion about v=0 may be a red herring for the tested code lengths: for (64,57,4) and longer, the dual code's minimum distance exceeds Q, so no distinct even-sized zero-XOR block can appear in the recursion; and in any case an optimal block for nonzero s cannot contain a zero-XOR subblock. The genuine issue is the missing proof of Claims 1–3, not the specific (8,4,4) edge case. The general EBD recursion (Theorems 1–3) appears mathematically sound, and the complexity reduction is plausible if the pruning proof can be completed. Thus the appropriate verdict remains CONDITIONAL: the paper should provide a complete proof or an independent computational verification before the ML claim for EBD-FullOpt is accepted.","tokens_in":15012,"tokens_out":25462,"duration_ms":250532,"concrete_test":"Implement EBD-FullOpt per §IV and Appendices C–D for the (64,57,4) code and compare its decoded output against a reference ML decoder (e.g., the FHT-based Be'ery–Snyders decoder) on at least 10^6 random AWGN frames at Eb/N0 values spanning FER=10^-3. If any frame yields c_EBD ≠ c_ML, or if for any syndrome M(Z_Q(s)) exceeds the true minimum pattern penalty, then pruning discarded an ML block and the central claim is refuted. As a smaller exhaustive check, enumerate all reliability orders for the (16,11,4) code and verify Claim 3 and O(s)=Z_Q(s) in every case.","verdict_should_be":"CONDITIONAL","load_bearing_attack":"The central claim—that EBD-FullOpt is ML and needs only ~10% of trellis Viterbi FLOPs—depends on the proof of O(s)=Z_Q(s) in Appendix B. That proof asserts Claims 1–3 without proving them. Claim 3 (M(Z_\\bar t(v)) ≥ M(O_\\bar t(v))) is not immediate under offline exclusion (blocks fixed to ∅) and online exclusion (blocks with penalty ≥ M(Z_{t−1}(s)) are set to ∅); a correct induction would need to show that every subblock of a minimal flipping block survives the online threshold, which in turn requires a replacement argument for Claim 2 that the paper omits. Claim 2 is simply stated, yet without it inequality (14) has no basis and the induction for Proposition 1 collapses. Section IV-A adds a second unproved assertion: even-sized locally optimal blocks for v=0 'must consist of repeated elements with the least reliability.' This is literally false for the (8,4,4) code, where distinct weight-4 zero-XOR blocks exist; for lengths 64+ it is true up to size Q only because the dual code has minimum distance 32, an argument the paper does not give. The exclusion may be salvageable (an optimal block for a nonzero syndrome cannot contain a zero-XOR subblock, since removing it would yield a lower-penalty block), but that argument is absent. As written, the appendix claims a rigorous proof yet leaves the key lemmas unproved, so the ML guarantee is not established; if any claim fails, EBD-FullOpt is a heuristic and Table I loses its ML justification.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","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.","tokens_in":15490,"tokens_out":16227,"duration_ms":171675,"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":[{"comment":"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.","section":"Appendix B, Claims 1–3 and Proposition 1"},{"comment":"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.","section":"Section IV-A, offline exclusion of even-sized Z_t(0)"},{"comment":"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.","section":"Section III-C, Eq. (11) and Appendix B"}],"minor_comments":[{"comment":"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.","section":"Appendix C, optimized construction strategy"},{"comment":"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.","section":"Theorem 1 proof"},{"comment":"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.","section":"Notation and typos"},{"comment":"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.","section":"Example in Section III-B"}],"recommendation":"major_revision","confidential_remarks":"The core DP idea (Theorems 1 and 2) is sound and potentially useful, but the manuscript's main claim — that the optimized EBD is ML with the complexity reported in Table I — is not adequately proved. The unproved Claims 1–3 in Appendix B and the false statement about even-sized zero-syndrome blocks in Section IV-A are serious enough that the paper should not be accepted in its current form. The issues appear fixable within the scope of the paper: Claims 1–3 can be proved in a few lines, and the v=0 exclusion can be justified by a zero-syndrome-subblock removal argument. I recommend major revision rather than rejection."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Quick take: the general EBD recursion is mathematically sound, but the novelty is modest; the headline claim of a ~10x FLOP reduction for extended Hamming codes with exact ML depends on a proof that is not actually there. I would not cite Table I as an ML result until Appendix B is repaired.\n\nWhat is genuinely good: The error-building block formalism is a clean repackaging of min-plus convolution over the syndrome group. Theorems 1 and 2 are proved correctly, and the worked (15,11,3) example makes the recursion intuitive. The extended-Hamming offline/online pruning strategy appears to be new, and the potential to use just the parity-check matrix in a DP framework is a nice perspective.\n\nThe soft spot is exactly where the stress-test note points. Appendix B claims to prove O(s)=Z_Q(s), then lists Claims 1-3 without proof and builds the induction on them. Claim 3 is the load-bearing one: it says the target block penalty never falls below the locally optimal penalty, which is precisely what the online exclusion rule in (11) can violate. A correct proof would need to show that no subblock of a minimal flipping block is ever discarded by the online threshold; that replacement argument is absent. The other unproved assertion, that even-sized locally optimal blocks for v=0 are always repeated elements with least reliability, fails for (8,4,4) and needs the dual distance argument for longer codes; the paper just states it. So the optimized decoder's ML guarantee is not established.\n\nThe complexity comparison is also a bit narrow. The baseline is trellis Viterbi, but not the FHT decoder from [12], and the reported FLOPs are averaged over different FER points, with no code or data to reproduce them. I suspect the general EBD without pruning is correct but exponential in Q; the interesting numbers in Table I are all about the pruning, which is the unproved part.\n\nThis paper deserves a serious referee. The core DP is correct, the idea is relevant for short high-rate codes, and the proof gaps are fixable in principle. I would not desk reject it, but I would ask for a complete proof of Proposition 1, or a clear statement of which parts of the algorithm are ML and which are heuristic. As it stands, the headline result should be read as conditional.","headline":"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.","tokens_in":15935,"tokens_out":2900,"would_cite":false,"duration_ms":32750,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":[],"pacs":[],"model":"deepseek-v4-flash","headline":"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","keywords":["error-building decoding","maximum-likelihood soft-decision decoding","linear block codes","parity-check matrix","extended Hamming codes","recursive construction","syndrome decoding","decoding complexity"],"falsifier":"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.","tokens_in":14925,"feed_emoji":"📡","tokens_out":3815,"duration_ms":42587,"temperature":0.7,"pith_summary":"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.","feed_headline":"Error-building decoding achieves ML from parity-check matrix alone","feed_subtitle":"Recursive block search finds the likeliest error pattern, cutting extended-Hamming cost to about a tenth of trellis Viterbi.","key_machinery":"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","core_discovery":"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","pith_inferences":["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."],"forward_implications":["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."],"fun_headline_variants":["ML decoding from parity-check matrix alone, no trellis","Error-building blocks cut Hamming decoding to 1/10 Viterbi cost","Recursive error-building finds ML without pre-built tables","Parity-check-only ML soft-decision for linear block codes"],"cache_read_input_tokens":2304,"weakest_assumption_plain":"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.","fun_headline_variants_meta":{"raw":{"variants":["ML decoding from parity-check matrix alone, no trellis","Error-building blocks cut Hamming decoding to 1/10 Viterbi cost","Recursive error-building finds ML without pre-built tables","Parity-check-only ML soft-decision for linear block codes"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000799,"raw_usage":{"total_tokens":3350,"prompt_tokens":740,"completion_tokens":2610,"prompt_tokens_details":{"cached_tokens":256},"prompt_cache_hit_tokens":256,"prompt_cache_miss_tokens":484,"completion_tokens_details":{"reasoning_tokens":2549}},"tokens_in":484,"tokens_out":2610,"duration_ms":19790,"temperature":1.0,"reasoning_tokens":2549,"cache_read_input_tokens":256,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-03T12:32:34.583257+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"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.","supporting_citations":[],"review_version":1}