Reed--Muller Codes Achieve the Symmetric Capacity on Finite-State Channels
2026-04-16 • Information Theory
Information Theory
AI summaryⓘ
The authors study how to send information reliably over special channels called finite-state channels using Reed–Muller codes. They build on previous work with simpler channels and show that with some random mixing, these codes can reach the maximum possible reliable transmission rate for these channels. Their method involves proving a new theorem for certain codes on memoryless channels, transforming the complex channel into a simpler one with bigger symbols, and then relating everything back to Reed–Muller codes. This approach helps understand how Reed–Muller codes work well even when the communication channel has memory.
Reed–Muller codesfinite-state channelscapacitysymmetrydoubly-transitive group codesdiscrete memoryless channelsnon-binary codesinterleavingpuncturing
Authors
Henry D. Pfister, Navin Kashyap, Jean-Francois Chamberland, Galen Reeves
Abstract
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.