arxiv: 2603.19938 · v2 · submitted 2026-03-20 · 💻 cs.IT · math.IT

Recognition: no theorem link

Capacity-Achieving BBT Polar Codes with Interleaver-Assisted BP Decoding

Xinyuanmeng Yao , Xiao Ma

Authors on Pith no claims yet

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

classification 💻 cs.IT math.IT

keywords polar codeschannel polarizationbinary balanced treebelief propagationcapacity achieving codesfinite length performanceinterleaver decoding

0 comments

The pith

Binary balanced tree transformation lets polar codes achieve capacity at any block length.

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

The paper introduces a binary balanced tree channel transformation that generalizes Arıkan's recursive combining step to block lengths that are not powers of two. It proves that this transformation still produces channel polarization, which establishes that the resulting BBT polar codes achieve the capacity of binary-input memoryless symmetric channels. The authors also develop a tree-based method to estimate the weight spectrum, derive analytical bounds on frame error rate under maximum-likelihood decoding, and present an interleaved variant with a modified belief-propagation decoder that lowers latency. A sympathetic reader would care because the power-of-two length restriction has long limited polar codes in practical systems that need flexible packet sizes.

Core claim

The central claim is that the binary balanced tree (BBT) channel transformation induces channel polarization for arbitrary block lengths. The transformation is constructed recursively on a balanced tree so that the mutual information of synthesized channels still tends to zero or one. This directly implies that BBT polar codes achieve the capacity of BMS channels. The hierarchical structure further supports an efficient weight-spectrum estimator and closed-form upper and lower bounds on frame error rate under ML decoding.

What carries the argument

The binary balanced tree (BBT) channel transformation, a recursive balanced-tree extension of Arıkan's combining operation that preserves polarization for any block length.

If this is right

BBT polar codes achieve the capacity of BMS channels for every block length.
The hierarchical tree structure yields an efficient estimator for the weight spectrum.
Analytical upper and lower bounds on frame error rate are available under maximum-likelihood decoding.
Interleaving between adjacent layers improves the convergence speed of belief-propagation decoding.
Replacing some message-passing modules with a-posteriori-probability calculations on a sub-normal graph reduces the number of steps per iteration.

Where Pith is reading between the lines

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

Polar coding could now be used directly in systems with arbitrary packet sizes without padding or rate loss.
The interleaving schedule and sub-normal-graph reduction may transfer to other graph-based decoders to cut latency.
The same balanced-tree idea could be tested on non-symmetric channels to see whether capacity achievement survives the relaxation of the BMS assumption.

Load-bearing premise

The binary balanced tree transformation preserves the recursive polarization property when the block length is not a power of two.

What would settle it

A direct computation for block length three or five showing that the mutual information of at least one synthesized channel stays strictly between zero and one after many levels of the BBT transformation would disprove the polarization claim.

Figures

Figures reproduced from arXiv: 2603.19938 by Xiao Ma, Xinyuanmeng Yao.

**Figure 1.** Figure 1: According to the above definition, for any code length 𝑁, the corresponding BBT can be constructed recursively starting from the root by splitting each node with ℓ ≥ 2 into two children. The resulting BBT has 𝑛 + 1 levels and exactly 𝑁 leaf nodes, where 𝑛 ≜ ⌈log2 𝑁⌉. An example of the BBT for 𝑁 = 6 is shown in [PITH_FULL_IMAGE:figures/full_fig_p004_1.png] view at source ↗

**Figure 1.** Figure 1: The parent-child relationship in a BBT. 6 3 3 2 1 2 1 1 1 1 1 (3,0) (3,1) (3,4) (3,5) (2,0) (2,1) (2,2) (2,3) (1,1) (0,0) (1,0) [PITH_FULL_IMAGE:figures/full_fig_p005_1.png] view at source ↗

**Figure 3.** Figure 3: Tree-graph representation of the BBT channel transformation for [PITH_FULL_IMAGE:figures/full_fig_p006_3.png] view at source ↗

**Figure 4.** Figure 4: Transformation from the tree graph to the normal graph for the BBT channel transformation with [PITH_FULL_IMAGE:figures/full_fig_p007_4.png] view at source ↗

**Figure 5.** Figure 5: The BBT polar encoding for 𝑁 = 6 and 𝐾 = 2, where the blue leaf nodes are frozen and red leaf nodes are active. (𝑠 +1, 2𝑡 +1), with lengths ⌈ℓ/2⌉ and ⌊ℓ/2⌋, respectively. The parent code vector 𝒗 (𝑠,𝑡) ∈ F ℓ 2 and the corresponding child code vectors 𝒗 (𝑠+1,2𝑡) ∈ F ⌈ℓ/2⌉ 2 and 𝒗 (𝑠+1,2𝑡+1) ∈ F ⌊ℓ/2⌋ 2 are related by 𝒗 (𝑠,𝑡) = 𝒗 (𝑠+1,2𝑡) ⊞ 𝒗 (𝑠+1,2𝑡+1) , 𝒗 (𝑠+1,2𝑡+1) , (6) where “⊞” denotes a length-dep… view at source ↗

**Figure 6.** Figure 6: Sorted bit-channel error rates for BBT polar codes with [PITH_FULL_IMAGE:figures/full_fig_p014_6.png] view at source ↗

**Figure 7.** Figure 7: Average WEFs of BBT tree nodes for CBBT [6, 2, {4, 5}] [PITH_FULL_IMAGE:figures/full_fig_p015_7.png] view at source ↗

**Figure 8.** Figure 8: FER performance of BBT polar codes with 𝑁 = 50 and 𝐾 = 10, 20, 30, and 40 under ML decoding. further develop a BP decoding algorithm that operates on a sub-graph of the IBBT normal graph. A. IBBT Normal Graph Recall that the normal graph representation of the BBT channel transformation can also be used to describe BBT polar codes. Motivated by this representation, we introduce a modified construction in wh… view at source ↗

**Figure 9.** Figure 9: Normal graphs of the IBBT polar code CIBBT [6, 3, {4, 5}]. Left: the original normal graph, where blue variable nodes correspond to frozen bits fixed to zero and the remaining nodes are active. Right: the sub-normal graph with ℓmax = 2, where iterative message passing is restricted to layers 0 to 2, and the APP calculation is performed at layer 2. Remark 3. The proposed BP decoding algorithm does not modif… view at source ↗

**Figure 10.** Figure 10: FER performance comparison between conventional BBT polar codes and IBBT polar codes under BP decoding for [PITH_FULL_IMAGE:figures/full_fig_p027_10.png] view at source ↗

**Figure 11.** Figure 11: Comparison between BP decoding on the full normal graph and the sub-normal graph in terms of error-rate performance [PITH_FULL_IMAGE:figures/full_fig_p027_11.png] view at source ↗

**Figure 12.** Figure 12: Comparison between BP decoding on the full normal graph and the sub-normal graph in terms of computational [PITH_FULL_IMAGE:figures/full_fig_p028_12.png] view at source ↗

**Figure 13.** Figure 13: Illustration of the BBT polar transformation for [PITH_FULL_IMAGE:figures/full_fig_p031_13.png] view at source ↗

read the original abstract

In this paper, we introduce a binary balanced tree (BBT) channel transformation that extends Ar{\i}kan's channel transformation to arbitrary block lengths. We prove that the proposed transformation induces channel polarization, thereby establishing that BBT polar codes achieve the capacity of binary-input memoryless symmetric (BMS) channels. To characterize the finite-length performance of BBT polar codes, we further develop an efficient method for estimating the weight spectrum by exploiting the hierarchical tree structure, and derive analytical upper and lower bounds on the frame error rate (FER) under maximum-likelihood (ML) decoding. For practical low-latency implementations, we propose interleaved BBT (IBBT) polar codes together with a belief-propagation (BP) decoding algorithm. Specifically, based on the normal-graph representation of BBT polar codes, interleavers are introduced between adjacent layers to modify the message-passing schedule. In addition, we propose to perform BP decoding on an IBBT sub-normal graph and replace partial BP processing modules with a posteriori probability (APP) calculation modules, thereby reducing the number of message-passing steps required per iteration. Numerical results demonstrate that the proposed interleaving strategy improves decoding convergence, while the sub-normal-graph-based BP decoding algorithm significantly reduces decoding latency while maintaining comparable error-rate performance.

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.

Desk Editor's Note private letter to a colleague

BBT polar codes extend polarization to arbitrary lengths via a balanced tree transform, but the induction in the proof needs verification for unequal subtree depths.

read the letter

The paper's main contribution is a binary balanced tree channel transformation that aims to polarize BMS channels for any block length N, not just powers of two. They claim a proof of this, plus an analytical weight spectrum estimator that exploits the tree hierarchy to bound FER under ML decoding. On the practical side, the interleaved BBT construction with a modified BP schedule on the normal graph and partial replacement by APP modules looks like a concrete way to cut decoding steps while keeping error rates close to standard BP. That interleaver tweak and sub-graph approach are the parts that feel immediately usable for low-latency implementations. The numerical results are only summarized in the abstract, but they apparently show faster convergence from the interleaving. The polarization claim is the load-bearing piece. The stress-test concern is worth checking: Arıkan's original argument leans on uniform 2-kernel recursion and equal-depth subtrees to get the martingale and extremal behavior. BBT allows depths to differ by at most one, so the induction step has to show that intermediate leaves still polarize properly without new fixed points. If the write-up handles the variable-depth case explicitly, the result stands; if it glosses over it, the capacity claim weakens. No other red flags jump out from the abstract or the described construction. This is the kind of work that matters for people building polar-code systems with flexible packet sizes. It deserves a serious referee who can walk through the polarization proof line by line and check the BP latency numbers against existing schedules. I would send it to review rather than desk-reject.

Referee Report

1 major / 2 minor

Summary. The paper introduces a binary balanced tree (BBT) channel transformation extending Arıkan's construction to arbitrary block lengths N. It claims to prove that this transformation induces channel polarization for binary-input memoryless symmetric channels, thereby showing BBT polar codes achieve capacity. The work also develops an efficient weight-spectrum estimation method exploiting the tree hierarchy, derives analytical upper/lower FER bounds under ML decoding, and proposes interleaved BBT (IBBT) polar codes with a modified BP decoder using interleavers between layers and sub-normal-graph APP modules to reduce latency while preserving error-rate performance.

Significance. If the polarization proof holds rigorously, the result is significant: it removes the dyadic-length restriction from capacity-achieving polar codes while retaining the recursive structure, supplies concrete finite-length analysis tools (hierarchical spectrum estimation and closed-form FER bounds), and demonstrates a practical low-latency BP variant. These elements together advance both the theoretical reach and implementability of polar codes for non-power-of-two block lengths.

major comments (1)

[Polarization theorem / BBT transformation definition] The polarization proof (central claim in the abstract and the section deriving the BBT recursion) must explicitly verify that the martingale property and extremal polarization (I(W)→0 or 1) continue to hold when the balanced binary tree has leaves whose depths differ by at most one. If the induction step implicitly relies on equal-depth subtrees as in the classical 2-kernel case, the argument does not yet cover arbitrary N and the capacity-achieving statement remains conditional.

minor comments (2)

[IBBT BP decoding section] The normal-graph representation and the precise placement of interleavers in the IBBT construction would benefit from an explicit small-N example (e.g., N=6 or N=10) showing the modified message-passing schedule.
[Notation and definitions] Notation for the synthetic-channel mutual informations after each BBT layer should be introduced once and used consistently; the current text occasionally redefines I(W_N^{(i)}) without cross-reference.

Simulated Author's Rebuttal

1 responses · 0 unresolved

We thank the referee for the careful reading and constructive feedback on our manuscript. We address the major comment on the polarization proof below and will revise the manuscript accordingly to strengthen the presentation.

read point-by-point responses

Referee: [Polarization theorem / BBT transformation definition] The polarization proof (central claim in the abstract and the section deriving the BBT recursion) must explicitly verify that the martingale property and extremal polarization (I(W)→0 or 1) continue to hold when the balanced binary tree has leaves whose depths differ by at most one. If the induction step implicitly relies on equal-depth subtrees as in the classical 2-kernel case, the argument does not yet cover arbitrary N and the capacity-achieving statement remains conditional.

Authors: The BBT transformation is defined for arbitrary N by constructing a balanced binary tree in which leaf depths differ by at most one; the recursion combines channels level-by-level while respecting this balance. The polarization proof proceeds by induction on the number of combining levels. The martingale property follows directly from the chain rule for mutual information applied to each combining step, which holds irrespective of whether the two subtrees have identical depth (the average I(W) is preserved at every step). Extremal polarization is established by showing that the variance of the conditional entropies (or equivalently the Bhattacharyya parameters) strictly increases at each level; the induction hypothesis applies recursively to the possibly shallower subtree without requiring equal depths. We agree that an explicit lemma verifying these two properties under the depth-difference-at-most-one condition would improve clarity and will add it in the revised manuscript. revision: yes

Circularity Check

0 steps flagged

No circularity in BBT polarization proof or capacity claim

full rationale

The derivation introduces a new BBT transformation for arbitrary block lengths and claims to prove it induces polarization (hence capacity achievement) by extending Arıkan's recursive construction. No step reduces by construction to a fitted parameter, self-definition, or load-bearing self-citation; the polarization argument is presented as a direct proof from the tree structure's properties (balanced depths, martingale behavior of mutual information) without renaming known results or smuggling ansatzes via prior author work. The finite-length bounds and BP decoding proposals are separate engineering contributions that do not underpin the capacity result. The chain is therefore self-contained against external benchmarks.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 2 invented entities

The central claim rests on the newly introduced BBT transformation and the assumption that it inherits polarization from Arıkan's construction. No numerical free parameters are introduced. The interleaver placement is a design choice rather than a fitted constant.

axioms (1)

domain assumption The underlying channel is binary-input memoryless symmetric (BMS)
Standard assumption required for all polarization arguments in the polar coding literature.

invented entities (2)

Binary balanced tree (BBT) channel transformation no independent evidence
purpose: Extend Arıkan's recursive transform to arbitrary block lengths while preserving polarization
Newly defined structure whose properties are proved in the paper.
Interleaved BBT (IBBT) normal graph no independent evidence
purpose: Enable modified message-passing schedule for lower-latency BP decoding
New graph construction introduced for the practical decoder.

pith-pipeline@v0.9.0 · 5527 in / 1247 out tokens · 49187 ms · 2026-05-15T07:15:12.135465+00:00 · methodology

discussion (0)

Reference graph

Works this paper leans on

30 extracted references · 30 canonical work pages · 1 internal anchor

[1]

Channel polarization: A method for constructing capacity-achieving codes for symmetric binary-input memoryless channels,

E. Arıkan, “Channel polarization: A method for constructing capacity-achieving codes for symmetric binary-input memoryless channels,”IEEE Transactions on Information Theory, vol. 55, no. 7, pp. 3051–3073, 2009

work page 2009
[2]

CRC-aided decoding of polar codes,

K. Niu and K. Chen, “CRC-aided decoding of polar codes,”IEEE Communications Letters, vol. 16, no. 10, pp. 1668–1671, 2012

work page 2012
[3]

List decoding of polar codes,

I. Tal and A. Vardy, “List decoding of polar codes,”IEEE Transactions on Information Theory, vol. 61, no. 5, pp. 2213– 2226, 2015

work page 2015
[4]

5G NR: Multiplexing and channel coding,

3GPP, “5G NR: Multiplexing and channel coding,” 3rd Generation Partnership Project, Tech. Rep. TS 38.212, 2018

work page 2018
[5]

A practical approach to polar codes,

A. Eslami and H. Pishro-Nik, “A practical approach to polar codes,” inIEEE International Symposium on Information Theory (ISIT), St. Petersburg, Russia, Jul. 2011, pp. 16–20

work page 2011
[6]

Beyond turbo codes: Rate-compatible punctured polar codes,

K. Niu, K. Chen, and J. Lin, “Beyond turbo codes: Rate-compatible punctured polar codes,”IEEE Transactions on Signal Processing, vol. 61, no. 6, pp. 1619–1633, 2013

work page 2013
[7]

A novel puncturing scheme for polar codes,

R. Wang and R. Liu, “A novel puncturing scheme for polar codes,”IEEE Communications Letters, vol. 18, no. 12, pp. 2081–2084, 2014

work page 2081
[8]

Shortened polar codes,

V . Miloslavskaya, “Shortened polar codes,”IEEE Transactions on Information Theory, vol. 61, no. 9, pp. 4852–4865, 2015

work page 2015
[9]

Design of length-compatible polar codes based on the reduction of polarizing matrices,

D.-M. Shin, S.-C. Lim, and K. Yang, “Design of length-compatible polar codes based on the reduction of polarizing matrices,”IEEE Transactions on Communications, vol. 61, no. 7, pp. 2593–2599, Jul. 2013

work page 2013
[10]

Rate matching for polar codes based on binary domination,

M. Jang, S.-K. Ahn, H. Jeong, K.-J. Kim, S. Myung, S.-H. Kim, and K. Yang, “Rate matching for polar codes based on binary domination,”IEEE Transactions on Communications, vol. 67, no. 10, pp. 6668–6681, Oct. 2019

work page 2019
[11]

A novel puncturing scheme of low rate polar codes based on fixed information set,

J. Zhao, W. Zhang, and Y . Liu, “A novel puncturing scheme of low rate polar codes based on fixed information set,”IEEE Communications Letters, vol. 25, no. 7, pp. 2104–2108, Jul. 2021

work page 2021
[12]

Rate-compatible punctured polar codes,

S. Han, B. Kim, and J. Ha, “Rate-compatible punctured polar codes,”IEEE Communications Letters, vol. 26, no. 4, pp. 753–757, Apr. 2022

work page 2022
[13]

A hybrid ARQ scheme based on polar codes,

K. Chen, K. Niu, and J. Lin, “A hybrid ARQ scheme based on polar codes,”IEEE Communications Letters, vol. 17, no. 10, pp. 1996–1999, 2013

work page 1996
[14]

An incremental redundancy hybrid ARQ scheme via puncturing and extending of polar codes,

H. Saber and I. Marsland, “An incremental redundancy hybrid ARQ scheme via puncturing and extending of polar codes,” IEEE Transactions on Communications, vol. 63, no. 11, pp. 3964–3973, 2015

work page 2015
[15]

An Incremental Redundancy HARQ Scheme for Polar Code

L. Ma, Y . Weiet al., “An incremental redundancy HARQ scheme for polar codes,”arXiv preprint arXiv:1708.09679, 2017

work page internal anchor Pith review Pith/arXiv arXiv 2017
[16]

An adaptive IR-HARQ scheme for polar codes by polarizing matrix extension,

M.-M. Zhao, G. Zhang, C. Xu, H. Zhang, R. Li, and J. Wang, “An adaptive IR-HARQ scheme for polar codes by polarizing matrix extension,”IEEE Communications Letters, vol. 22, no. 7, pp. 1306–1309, Jul. 2018. DRAFT March 23, 2026 33

work page 2018
[17]

Structural extension of polar codes via simplex kernels,

M. Jang, J.-H. Kim, S. Myung, H. Yang, and S.-H. Kim, “Structural extension of polar codes via simplex kernels,”IEEE Transactions on Communications, vol. 68, no. 12, pp. 7337–7351, Dec. 2020

work page 2020
[18]

Multi-kernel polar codes: Concept and design principles,

V . Bioglio, F. Gabry, I. Land, and J. Belfiore, “Multi-kernel polar codes: Concept and design principles,”IEEE Transactions on Communications, vol. 68, no. 9, pp. 5350–5362, 2020

work page 2020
[19]

Randomized chained polar subcodes,

P. Trifonov, “Randomized chained polar subcodes,” inIEEE Wireless Communications and Networking Conference Workshops (WCNCW), Barcelona, Spain, Apr. 2018, pp. 25–30

work page 2018
[20]

Asymmetric construction of low-latency and length-flexible polar codes,

A. Cavatassi, T. Tonnellier, and W. J. Gross, “Asymmetric construction of low-latency and length-flexible polar codes,” in IEEE International Conference on Communications (ICC), Shanghai, China, May 2019, pp. 1–6

work page 2019
[21]

A balanced tree approach to construction of length-flexible polar codes,

X. Yao and X. Ma, “A balanced tree approach to construction of length-flexible polar codes,”IEEE Transactions on Communications, vol. 72, no. 2, pp. 665–674, 2024

work page 2024
[22]

A simple proof of polarization and polarization for non-stationary channels,

M. Alsan and E. Telatar, “A simple proof of polarization and polarization for non-stationary channels,” inIEEE International Symposium on Information Theory (ISIT), Honolulu, HI, USA, Aug. 2014, pp. 301–305

work page 2014
[23]

Interleaved polar (I-polar) codes,

M. Chiu, “Interleaved polar (I-polar) codes,”IEEE Transactions on Information Theory, vol. 66, no. 4, pp. 2430–2442, 2020

work page 2020
[24]

Tenenbaum, Y

A. Tenenbaum, Y . Langsam, and M. Augenstein,Data Structures Using C. Prentice-Hall, 1990

work page 1990
[25]

On the weight distribution of concatenated code ensemble based on the Plotkin construction,

X. Ma, “On the weight distribution of concatenated code ensemble based on the Plotkin construction,” 2025. [Online]. Available: https://arxiv.org/abs/2508.21515

work page arXiv 2025
[26]

New techniques for upper-bounding the ML decoding performance of binary linear codes,

X. Ma, J. Liu, and B. Bai, “New techniques for upper-bounding the ML decoding performance of binary linear codes,” IEEE Transactions on Communications, vol. 61, no. 3, pp. 842–851, 2013

work page 2013
[27]

A lower bound on the probability of a finite union of events,

H. Kuai, F. Alajaji, and G. Takahara, “A lower bound on the probability of a finite union of events,”Discrete Mathematics, vol. 215, no. 1, pp. 147–158, 2000

work page 2000
[28]

An efficient algorithmic lower bound for the error rate of linear block codes,

F. Behnamfar, F. Alajaji, and T. Linder, “An efficient algorithmic lower bound for the error rate of linear block codes,” IEEE Transactions on Communications, vol. 55, no. 6, pp. 1093–1098, 2007

work page 2007
[29]

Soft-decision decoding of linear block codes based on ordered statistics,

M. P. C. Fossorier and S. Lin, “Soft-decision decoding of linear block codes based on ordered statistics,”IEEE Transactions on Information Theory, vol. 41, no. 5, pp. 1379–1396, 1995

work page 1995
[30]

A new chase-type soft-decision decoding algorithm for Reed–Solomon codes,

S. Tang, S. Cai, and X. Ma, “A new chase-type soft-decision decoding algorithm for Reed–Solomon codes,”Alexandria Engineering Journal, vol. 61, no. 12, pp. 13 067–13 077, 2022. March 23, 2026 DRAFT

work page 2022