Reed--Muller Codes Achieve the Symmetric Capacity on Finite-State Channels
This provides a theoretical foundation for using RM codes in channels with memory, which is a significant step for coding theory.
The paper proves that Reed-Muller codes with random scrambling achieve the symmetric capacity of binary-input indecomposable finite-state channels, extending prior results from memoryless channels.
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.