From Bit to Block: Capacity Achievement via Product Coding

Jul 16, 2026

Upload by Levi

From bit-level reliability to block-level reliability at the same asymptotic rate, this paper proves a capacity-transfer mechanism for any binary memoryless symmetric (BMS) channel. A product-coding scheme combines a row code of target rate with vanishing bit-error probability and a high-rate column code with bounded-distance correction. Row-column decoding purifies errors into a sparse residual pattern, then eliminates residual errors column-wise. When the column correction radius exceeds the residual bit-error probability and column length is large enough for a binomial large-deviation bound, block-error probability vanishes. As an application, RM–BCH product codes achieve the capacity of arbitrary fixed BMS channels.

LanguageEnglish

CategoryResearch & Report

FormatPDF

Pages6

Reading Time15 min

Introduction

Preliminaries

From Bit to Block: Capacity Achievement via Product Coding Bin Zhang Dept. of Electronic and Information Engineering Beihang university Beijing, China [binzhang.it@gmail.com](binzhang.it@gmail.com) arXiv :2607 .058 16v 1 [ cs .IT] 7 Jul 2026 Abstract—This paper shows that product coding can convert bit-level reliability into block-level reliability at the same asymptotic rate. The encoding process combines a row code of the target rate with vanishing bit-error probability and a high-rate column code with bounded-distance correction capability. The decoding process first decodes rows, thereby purifying the channel output into a sparse residual error pattern, and then decodes columns to clean the residual errors. We prove that, if the column correction radius exceeds the residual bit-error probability and the column length is large enough for a binomial large-deviation bound to overcome the union bound over columns, then the product code has vanishing block-error probability. Thus a bit-level capacityachieving family can be converted into a block-level capacityachieving product-code family. As an application, we construct an RM–BCH product-code family that achieves the capacity of any fixed BMS channel. Index Terms—Capacity-achieving codes, binary memoryless symmetric channels, product codes, Reed–Muller codes, BCH codes. I. INTRODUCTION Shannon introduced channel capacity as the largest rate at which messages can be transmitted over a noisy channel with vanishing block-error probability [1] . Since then, a central goal of coding theory has been to find explicit code families that achieve this limit. Polar codes, introduced by Arikan, were the first explicit codes proved to achieve the capacity of binary memoryless symmetric (BMS) channels [2] . On the binary erasure channel (BEC), Kudekar, Kumar, Mondelli, Pfister, Sasoglu, and Urbanke proved that doubly transitive linear codes achieve capacity under bit-MAP decoding; this includes RM codes and affine-invariant examples [3] . For general BMS channels, the capacity-achieving behavior of RM codes was established through the bit-error result of Reeves and Pfister [5] and the block-error result of Abbe and Sandon [4] . Related highly symmetric algebraic code families have also been studied for erasure channels: Natarajan and Krishnan showed that certain Abelian codes achieve BEC capacity [6] and later introduced Berman codes, a generalization of RM codes that achieves BEC capacity [7] . More recently, Abbe, Li, and Sly introduced Tensor Reed–Muller codes as a tensorproduct variant of RM codes and showed that they achieve capacity [9] . In several capacity-achievement results, bit-level reliability appears before block-level reliability. For example, the BEC result above first establishes capacity achievement under bitMAP decoding for doubly transitive linear codes. For BMS channels, Reeves and Pfister proved that RM codes have vanishing bit-error probability below capacity before Abbe and Sandon established the corresponding block-error statement. A direct union bound can convert bit-error reliability 1 − ϵn into block-error reliability only when nϵn → 0. This raises a natural question: how can bit-level reliability be converted into block-level reliability when the bit-error decay is too slow for the union bound? This bit-to-block question has recently been studied explicitly on erasure channels. Pfister, Sprumont, and Zemor developed a framework for bounding the block-error threshold of a linear code on the BEC in terms of its bit-error threshold and subcode-support growth [8] . This paper shows that, for any BMS channel W , bit-level reliability can be converted into block-level reliability through the product-coding framework introduced by Forney [10] . It combines a row component ofrate R−o(1) with vanishing biterror probability and a column component of rate 1−o(1) with bounded-distance correction capability. The resulting product code still has ra

FAQs

What problem does the paper address?

It addresses how to convert bit-level reliability into block-level reliability when bit-error decay is too slow for a direct union-bound argument.

How does the product-coding framework achieve bit-to-block conversion?

It uses row-column decoding: first decodes rows to purify the channel output into a sparse residual error pattern, then decodes columns to correct the remaining errors.

Under what conditions does the product code achieve vanishing block-error probability?

When the column correction radius exceeds the residual bit-error probability and the column length is sufficiently large so a binomial large-deviation bound dominates the union bound over columns.

Jul 16, 2026

Upload by Levi