Reed--Muller Codes Achieve the Symmetric Capacity on Finite-State Channels
Fuente:
arXiv
Saved in:
| Main Authors: | , , , |
|---|---|
| Format: | Preprint |
| Published: |
2026
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866914480370221056 |
|---|---|
| author | Pfister, Henry D. Kashyap, Navin Chamberland, Jean-Francois Reeves, Galen |
| author_facet | Pfister, Henry D. Kashyap, Navin Chamberland, Jean-Francois Reeves, Galen |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2604_15295 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | Reed--Muller Codes Achieve the Symmetric Capacity on Finite-State Channels Pfister, Henry D. Kashyap, Navin Chamberland, Jean-Francois Reeves, Galen Information Theory 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. |
| title | Reed--Muller Codes Achieve the Symmetric Capacity on Finite-State Channels |
| topic | Information Theory |
| url | https://arxiv.org/abs/2604.15295 |