pith. sign in

arxiv: 2605.21727 · v1 · pith:A4Q36SJBnew · submitted 2026-05-20 · 💻 cs.IT · math.IT

Reed-Muller Codes for Joint Random and Stuck-At Error Correction

Ivana Djurdjevic , Robert Mateescu , Cyril Guyot This is my paper

Pith reviewed 2026-05-22 07:58 UTC · model grok-4.3

classification 💻 cs.IT math.IT
keywords Reed-Muller codesstuck-at errorsrandom errorsmemory reliabilityrecursive constructionnonlinear codesside informationerror correction
0
0 comments X

The pith

A recursive construction produces masks that are Reed-Muller RM(s-1, m) codewords for correcting s stuck-at defects while supporting random error correction.

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

The paper presents a recursive method to build a compact set of masks that together handle every possible pattern of s stuck-at defects in a block of 2^m bits when s is at most m. It proves that every mask generated by the recursion is a codeword of the Reed-Muller code of order s-1. The same algebraic structure then lets the scheme also correct random errors on top of the defects by embedding the nonlinear stuck-at code inside a larger Reed-Muller code of order at least s-1. Encoding uses the known defect locations to select the mask directly from the recursion, and decoding finishes in one pass with little extra work.

Core claim

The authors give a recursive construction that yields a set of at most 2^s m^{s-1} masks capable of correcting any s stuck-at errors in a 2^m sequence. They prove these masks are exactly the codewords of the Reed-Muller code RM(s-1, m). The resulting stuck-at code is nonlinear yet forms a subcode of an RM(r, m) code with r at least s-1, so the same code can correct additional random errors. Encoding follows the recursion without search, and decoding requires only a single attempt.

What carries the argument

The recursive construction of masks that are proven to belong to the Reed-Muller code RM(s-1, m) and together cover all s stuck-at patterns.

If this is right

  • Encoding requires no search over masks and follows directly from the recursive description.
  • Decoding runs in a single attempt with almost no added complexity or latency.
  • Explicit lower and upper bounds are obtained on the number of stuck-at redundancy bits.
  • The overall code corrects random errors in addition to the s stuck-at defects by using the containing RM(r, m) code with r at least s-1.

Where Pith is reading between the lines

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

  • The recursive structure may suggest similar mask constructions inside other algebraic code families.
  • The joint correction of two error types inside one Reed-Muller code could lower total redundancy compared with handling each error type separately.
  • As m increases, the stated size bound 2^s m^{s-1} indicates how the redundancy scales with block length.

Load-bearing premise

The encoder knows exactly which cells are stuck and to what value, while the decoder has no such information and s is at most m.

What would settle it

For small parameters such as m=3 and s=2, generate the masks by the recursion and check whether every possible pair of stuck-at defects is corrected by exactly one mask from the set; a mismatch would falsify the coverage claim.

Figures

Figures reproduced from arXiv: 2605.21727 by Cyril Guyot, Ivana Djurdjevic, Robert Mateescu.

Figure 2
Figure 2. Figure 2: Block diagram of a decoder for joint random error correction and [PITH_FULL_IMAGE:figures/full_fig_p002_2.png] view at source ↗
Figure 1
Figure 1. Figure 1: Block diagram of an encoder for joint random error correction and [PITH_FULL_IMAGE:figures/full_fig_p002_1.png] view at source ↗
Figure 3
Figure 3. Figure 3: A set of 8 masks that can correct any 2 stuck-at defects in a message [PITH_FULL_IMAGE:figures/full_fig_p003_3.png] view at source ↗
Figure 4
Figure 4. Figure 4: Recursive construction of masks of length 8 that can cover any [PITH_FULL_IMAGE:figures/full_fig_p003_4.png] view at source ↗
Figure 5
Figure 5. Figure 5: Fractal structure of the recursively constructed mask set, shown in [PITH_FULL_IMAGE:figures/full_fig_p007_5.png] view at source ↗
Figure 6
Figure 6. Figure 6: Relationship between a set of masks of length [PITH_FULL_IMAGE:figures/full_fig_p008_6.png] view at source ↗
read the original abstract

Block codes are considered for improving the reliability of messages stored in a computer memory with both stuck-at defects and random errors. It is assumed that the side information about the state of the defects is available to the encoder, but not to the decoder. A novel recursive construction of a set of masks is developed such that it can satisfy any $s$ stuck-at errors in a $2^m$ binary sequence, when $s \leq m$. We prove that the masks generated in this way are codewords in a Reed-Muller $RM(s-1, m)$ code. The constructed set contains no more than $2^s m^{s-1}$ masks. We provide the lower and the upper bound on the size of the stuck-at redundancy, a fixed subset of mask bits that uniquely represents each mask in the set. The stuck-at code constructed in this way is a non-linear code. It is also a subcode of an $RM(r,m)$ code, with $ r \geq s-1$, that can be used for additional random error correction. The encoding requires no mask search and is straightforward based on the description of the recursive construction. The decoding is done in a single attempt and requires almost no additional complexity or latency.

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 describes a recursive construction for generating a set of masks to correct any combination of s stuck-at defects in a binary sequence of length 2^m, assuming s ≤ m and with defect state information available only at the encoder. The authors prove that these masks are codewords of the Reed-Muller code RM(s-1, m), bound the number of such masks by 2^s m^{s-1}, derive bounds on the stuck-at redundancy (a fixed subset of bits uniquely identifying each mask), and show that the resulting nonlinear stuck-at code is a subcode of an RM(r, m) code with r ≥ s-1, enabling additional random error correction. Encoding follows directly from the recursive description without search, and decoding is performed in one attempt with negligible extra complexity.

Significance. If the central claims hold, the paper offers a structured algebraic approach to joint stuck-at and random error correction in memory systems using Reed-Muller codes. The recursive construction and explicit size bound of 2^s m^{s-1} provide a concrete, scalable method for small s, while the subcode property allows seamless integration with RM-based random error correction. This could be significant for practical memory reliability applications where defect side information is encoder-only. The work builds on known properties of RM codes and their recursive decompositions.

major comments (1)
  1. The abstract states a proof that the generated masks are RM(s-1, m) codewords via the recursive construction and gives the size bound 2^s m^{s-1}, but the full inductive argument establishing that each recursive step preserves membership in RM(s-1, m) (leveraging the Plotkin-style decomposition) is central to the claim and requires explicit verification in the manuscript.
minor comments (2)
  1. The lower and upper bounds on stuck-at redundancy size are stated but not derived explicitly; including the expressions or a short derivation would clarify the redundancy overhead.
  2. Specify the precise range or choice of r (r ≥ s-1) used for the encompassing RM(r, m) code and how the random-error correction radius is determined from it.

Simulated Author's Rebuttal

1 responses · 0 unresolved

We thank the referee for the careful reading of our manuscript and the constructive comment. We agree that the inductive argument merits fuller explicit presentation and will revise the paper to address this point.

read point-by-point responses

  1. Referee: The abstract states a proof that the generated masks are RM(s-1, m) codewords via the recursive construction and gives the size bound 2^s m^{s-1}, but the full inductive argument establishing that each recursive step preserves membership in RM(s-1, m) (leveraging the Plotkin-style decomposition) is central to the claim and requires explicit verification in the manuscript.

    Authors: We agree that the full inductive verification is central and should be stated explicitly. In the revised manuscript we will expand the relevant proof section to include a complete induction: the base case for s = 1 is verified directly from the definition of RM(0, m); assuming the claim holds after k recursive steps, we then show that the (k+1)-st step, which applies the Plotkin-style decomposition of RM(s-1, m) into two copies of RM(s-2, m-1), maps the newly generated masks into the required codewords while preserving the overall bound of 2^s m^{s-1}. The revised text will contain the detailed algebraic steps rather than relying on the recursive description alone. revision: yes

Circularity Check

0 steps flagged

No significant circularity; derivation is self-contained

full rationale

The paper introduces an explicit recursive construction of a mask set for correcting s stuck-at defects (with s ≤ m) in a 2^m sequence, then proves by direct argument that the generated masks are codewords of the known Reed-Muller code RM(s-1, m) while bounding the set size by 2^s m^{s-1}. The size bound and membership follow immediately from the construction parameters and the standard algebraic definition of RM codes; no equation reduces a claimed result to a fitted parameter, a self-referential definition, or a load-bearing self-citation. The encoder-only side-information model and the subcode property for joint random-error correction are standard modeling choices that do not create circular dependence on the target claims.

Axiom & Free-Parameter Ledger

0 free parameters · 2 axioms · 0 invented entities

The work rests on standard algebraic properties of Reed-Muller codes and the modeling assumption that defect side information reaches only the encoder. No free parameters are introduced and no new entities are postulated.

axioms (2)
  • standard math Reed-Muller codes RM(r,m) have the algebraic structure and minimum-distance properties stated in standard coding-theory references.
    Invoked when the paper asserts that the constructed masks are codewords of RM(s-1,m) and that the overall code is a subcode of RM(r,m) for r ≥ s-1.
  • domain assumption Side information on stuck-at defect locations and values is known to the encoder but unavailable to the decoder.
    Stated explicitly in the abstract as the operating model that enables the mask-based correction.

pith-pipeline@v0.9.0 · 5753 in / 1271 out tokens · 44769 ms · 2026-05-22T07:58:58.371274+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

11 extracted references · 11 canonical work pages

  1. [1]

    A. V. Kuznetsov and B. S. Tsybakov. Coding in a Memory with Defective Cells. Problems Inform. Transmission. 1974

    work page 1974

  2. [2]

    2024 , eprint=

    One Code Fits All: Strong stuck-at codes for versatile memory encoding , author=. 2024 , eprint=

    work page 2024

  3. [3]

    Ivana Djurdjevic and Robert Mateescu and Cyril Guyot , year=. Reed -. xxxx.xxxxx , archivePrefix=

    work page

  4. [4]

    A. V. Kuznetsov and T. Kasami and S. Yamamura. An Error Corrective Scheme for Defective Memory. IEEE Transactions on Information Theory. 1978

    work page 1978

  5. [5]

    Stuck-at

    C. Heegard. Partitioned Linear Block Codes for Computer Memory with “ Stuck-at” Defects. IEEE Transactions on Information Theory. 1983

    work page 1983

  6. [6]

    Asymptotically optimal linear codes for correcting defects of linearly increasing multiplicity , volume =

    Dumer, Ilya , year =. Asymptotically optimal linear codes for correcting defects of linearly increasing multiplicity , volume =

    work page

  7. [7]

    Borden and A

    J. Borden and A. Vinck. On coding for stuck-at defects. IEEE Transactions on Information Theory. 1987

    work page 1987

  8. [8]

    Gabrys, R

    R. Gabrys, R. Sala, L. Dolecek. Coding for unreliable flash memory cells. IEEE Communications Letters. 2014

    work page 2014

  9. [9]

    Wachter-Zeh and E

    A. Wachter-Zeh and E. Yaakobi. Codes for Partially Stuck-at Memory Cells. Int. ITG Conf. on Systems, Communications and Coding (SCC). 2015

    work page 2015

  10. [10]

    Motwani and Z

    R. Motwani and Z. S. Kwok and P. M. Palangappa. Combating Bit Errors From Stuck Cells in Flash Memory Using Novel Information Theory Techniques. Proc. Workshop on Computing, Networking and Communications (CNC). 2018

    work page 2018

  11. [11]

    Coding and Bounds for Partially Defective Memory Cells

    Haider Al Kim and Sven Puchinger and Ludo Tolhuizen and Antonia Wachter-Zeh. Coding and Bounds for Partially Defective Memory Cells. 2022. arXiv:2202.07541

    work page arXiv 2022