Weight Distributions for Successive Cancellation Decoding of Polar Codes

Mars Davletshin; Nikita Polyanskii; Rina Polyanskaya

REVIEW 2 major objections 3 minor 17 references

Weight Distributions for Successive Cancellation Decoding of Polar Codes

T0 review · 2 major / 3 minor · reviewed 2026-08-14 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read Exact formula found for first nonzero weight in polar SC decoding

desk verdict Solid combinatorial weight-distribution results for SC decoding of polar codes, but Theorem 5's closed-form formula for wt(gi+gj) is misprinted and needs correction. read the letter →

arxiv 1908.06652 v3 pith:QXIBX3VA submitted 2019-08-19 cs.IT math.IT

Rina Polyanskaya , Mars Davletshin , Nikita Polyanskii This is my paper · ORCID

classification cs.ITmath.IT MSC 94B0594B35

keywords polarcodesweightdistributionsuccessivecancellationdecodingcosetpartialorderlistfirstnonzerocomponent|u|u+v|construction

verification ladder T0 review T1 audit T2 compute T3 formal

The pith

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

The reading

This paper tries to establish that the weight distributions arising at every stage of successive cancellation (SC) decoding of polar codes can be computed exactly by a simple recursive algorithm. It further claims that the first nonzero component of each such distribution has a closed-form expression determined by the binary expansion of the synthetic channel index. If true, these results give a new tool for estimating the error probability of SC decoding without simulating the decoder. The paper also attempts to prove a lower bound on the minimal distance between cosets corresponding to two paths that differ in two positions, a step toward analyzing list decoding.

What carries the argument

The central object is the recursive structure of the polar code generator matrix $G_N=G_2^{\otimes n}$, whose rows can be written as Kronecker products. Algorithm 1 computes the weight distributions stage by stage using the identity that any vector in $C^{(n)}(0^{i-1},1)$ for $i<N/2$ has the unique form $(x_1,0)+(x_2,x_2)$ with $x_1$ in the corresponding coset of $C^{(n-1)}$ and $x_2$ arbitrary. The proof of Theorem 2 derives the closed form for the first nonzero component by induction on $n$, showing how the formula transforms under the two cases $i<N$ and $i\ge N$. Theorem 5 uses projections onto coordinate subsets defined by the bits of indices, together with an induction on $n$, to reduce the minimal weight problem to lower-dimensional cosets.

What would settle it

Compute the weight distribution for a small polar code, say $N=8$ or $N=16$, by exhaustive enumeration of the coset $C^{(n)}(0^{i-1},1)$ for all $i$ and compare with Algorithm 1 and with Theorem 2's closed form for the first nonzero component; any mismatch in the first nonzero weight or its multiplicity would disprove the central claim.

Watch

Extended reading notes

Core claim

For a polar code of length $N=2^n$, the weight distribution $S_i^{(n)}$ of the coset $C^{(n)}(0^{i-1},1)$ at each SC decoding stage is exactly computable by Algorithm 1, which recursively applies the $|u|u+v|$ construction. The first nonzero component $s_i^{(n)}$ of this distribution occurs at weight $\mathrm{wt}(g_i)=2^{p_{n-1}(i)}$ and satisfies $\log_2 s_i^{(n)}=\sum_{j=0}^{n-1}(1-b_j(i))2^{p_j(i)}$, where $b_j(i)$ is the $j$-th bit of $i$ and $p_j(i)$ is the partial sum of the first $j+1$ bits (Theorem 2). The paper also establishes that if synthetic channel $W_N^{(i)}$ is stochastically degraded by $W_N^{(j)}$ with $i<j$, then either the first nonzero component of $S_j^{(n)}$ has larger weight than that of $S_i^{(n)}$, or they have equal weight and the multiplicity satisfies $s_i^{(n)}>s_j^{(n)}$ (Theorem 4). Finally, Theorem 5 proves that for any two positions $i<j$, the minimal Hamming weight of any vector in the coset $C^{(n)}(i,j)$ equals $\mathrm{wt}(g_i+g_j)=\mathrm{wt}(g_i)+\mathrm{wt}(g_j)-2t_{i,j+1}$, where $t_{i,j}$ is the number of common ones in the binary representations of $i$ and $j$.

Load-bearing premise

The recursive derivation assumes that when $i<N/2$, every vector in $C^{(n)}(0^{i-1},1)$ has a unique representation as $(x_1,0)+(x_2,x_2)$ with $x_1$ in the corresponding lower-dimensional coset and $x_2$ arbitrary, which relies on $G_{N/2}$ being full rank and on the chosen row order without the bit-reversal permutation.

Editorial extensions

If this is right

The exact weight distributions and the formula for the first nonzero component can be used to compute approximate union bounds on the error probability of SC decoding for all synthetic channels in $O(N)$ time when only a constant number of terms is kept.
The link with the partial order of synthetic channels means that the first nonzero component of the weight distribution is monotone with respect to channel degradation: degraded channels have either larger minimal weight or smaller multiplicity.
The minimal distance result for two-bit differences, Theorem 5, gives a concrete lower bound on the distance between two paths in successive cancellation list decoding, which can help in analyzing path pruning.
The recursive algorithm extends the classical $|u|u+v|$ weight distribution technique to polar codes, providing a practical tool for code construction and performance estimation.
If the formula for $s_i^{(n)}$ holds for all $i$, it implies that the first nonzero component is determined entirely by the binary representation of the synthetic channel index, making it easy to rank channels by their error floor characteristics.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

The formula for the first nonzero component might be extended to zero cosets $C^{(n)}(0^{i-1},0)$ by a similar recursive analysis, potentially yielding more accurate error-probability bounds than the one-sided approximation used in the paper.
The minimal distance result for two bit errors could be generalized to paths differing in more than two positions, which would be a direct step toward a full distance spectrum for successive cancellation list decoding.
The explicit dependence of the first nonzero component on the bits of $i$ suggests a possible connection to the partial order beyond what the paper proves: the equality case in Theorem 4 might correspond to a finer ordering of synthetic channels by multiplicity.
A testable extension would be to compare the computed weight distributions with exhaustive enumeration for medium block lengths (e.g., $N=32$ or $64$) to confirm that the recursive algorithm and closed form agree for all weights, not just the first nonzero component.

Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Desk Editor's Note

read the letter

Short take: this is a genuinely useful paper for the polar-coding subfield. It gives the first exact per-stage weight distributions for SC decoding, and the main formula (Theorem 2) is correct and nice. The paper deserves a serious referee, though one equation in Theorem 5 is wrong as printed.

What's new: Algorithm 1 computes the weight distributions S_i^(n) recursively, adapting Fossorier-Lin's |u|u+v| technique. That is not a radically new method, but nobody had applied it to SC decoding of polar codes before, and the recursive decomposition of the coset C^(n)(0^{i-1},1) is clean. Theorem 2's closed form for the first nonzero component, log2 s_i^(n) = sum (1-b_j(i)) 2^{p_j(i)}, is the strongest result in the paper. I checked it against Table I for n=3 and it works. The link to the partial order in Theorem 4 is a nice observation, though not deep. Theorem 5's inequality — every word in C^(n)(i,j) has weight at least wt(g_i+g_j) — is proved by a careful induction and appears valid.

The soft spot is real and localized. Equation (11) in Theorem 5, as typeset, is false. The paper states wt(g_i+g_j) = wt(g_i)+wt(g_j)-2 t_{i,j+1}; for N=8, i=1, j=3 this gives 6 instead of the correct value 2. The proof itself shows T_{i,j} = |supp(g_i)∩supp(g_j)| = 2^{t_{i,j}}, so the formula should read wt(g_i)+wt(g_j)-2^{t_{i,j}+1}. This is a typographical/exponent error, not a flaw in the induction, and the inequality wt(x) ≥ wt(g_i+g_j) does not depend on the formula. But Eq (11) is part of the stated theorem, so it needs a straightforward correction.

Other notes. The approximate union bound of Section II-C is acknowledged by the authors as an approximation; I would not treat it as a rigorous result. The row-ordering assumption (dropping the bit-reversal permutation) is fine because they define the code by G_N directly. The citation pattern is fair: Fossorier-Lin for the technique, Schürch for the partial order, no self-citation inflation.

Who is this for? Researchers working on polar codes, especially on SC/SCL decoding and distance spectra. It is a solid combinatorial contribution that others will want to use. I would send it to review. The fix to Eq (11) is mandatory but trivial.

Referee Report

2 major / 3 minor

Summary. The paper studies the weight distributions of the cosets used at each stage of successive cancellation (SC) decoding of polar codes. It gives a recursive algorithm, Algorithm 1, for computing these distributions, together with an explicit formula for the first nonzero component of each distribution and a connection between that component and the partial order on synthetic channels. It also analyzes the case of two decoding paths that differ in two positions, proving a lower bound on the weight of the corresponding coset and stating a closed-form expression for the minimal such weight. The paper positions these results as a step toward the analysis of successive cancellation list decoding.

Significance. Theorems 1 and 2 are clean and self-contained, and the Algorithm 1 recursion is a natural and useful contribution: it gives an exact, polynomial-cost way to access the relevant weight distributions without enumerating codewords. The verification against Table I for n=3 is consistent with the formulas. The connection with the partial order is interesting and correctly ties the first nonzero components to a known structural property of polar codes. The proof of Theorem 5 is intricate, and the inequality part appears valid. If the displayed formula in Theorem 5 is corrected as detailed below, the paper makes a solid contribution to the understanding of SC and SCL decoding. The paper contains no fitted parameters or circular derivations, and the main claims are stated in falsifiable, checkable form.

major comments (2)

[Theorem 5, Eq. (11)] Equation (11) is false as typeset. With N=8, i=1, and j=3, the rows are g1=(1,1,0,0,0,0,0,0) and g3=(1,1,1,1,0,0,0,0), so wt(g1+g3)=2. The printed formula gives wt(g1)+wt(g3)-2 t_{1,4}=2+4-0=6, since t_{1,4}=0. The proof itself shows that the correct quantity is T_{i,j}=|supp(gi) cap supp(gj)|=2^{t_{i,j}}, so the closed form should read wt(gi+gj)=wt(gi)+wt(gj)-2^{t_{i,j}+1}. This is a load-bearing error because the corrected formula is part of the statement of Theorem 5, not merely a typographical detail in a remark; please correct Eq. (11) and make the exponent notation uniform throughout the proof.
[Section IV, proof of Theorem 5] The displayed chain at the end of the proof of Theorem 5 is affected by the same exponent typo: the proof states 'Ti,j = 2 ti,j' and '= 2^{sum ...}', which are inconsistent unless the first is read as 2^{t_{i,j}}. The inductive step explicitly shows T_{i,j}=2^{b_{n-1}(i)b_{n-1}(j)} T_{f(i),f(j)}, which is an exponential relation, not a product. Please rewrite this portion with explicit superscripts so that the proof matches the corrected Eq. (11).

minor comments (3)

[Section III-A, after Eq. (5)] In the sentence defining the unique representation for i < 2^{n-1}, the set is written as C^{(n)}(0^{i-1}_1, 1); this should likely be C^{(n)}(0^{i-1}_0, 1), with the subscript 0, to match the definition in Section II-B.
[Theorem 2, Eq. (7)] The notation p_j(i) is defined as the partial sum of the first j+1 bits, but in Theorem 2 the quantity wt(gi)=2^{p_{n-1}(i)} is used; it would help to explicitly state that the exponent is the Hamming weight of the binary representation of i, since this is not immediately obvious from the definition.
[Figure 1 and Figure 2] The captions and axis labels are understandable, but the difference between the approximate union bound P_ub and the exact error probability P_e would be clearer if the figures explicitly indicated the SNR values or the code construction used for the information set.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: the weight-distribution derivations follow directly from the recursive generator-matrix structure and external cited results; no fitted input is relabeled as a prediction.

full rationale

The paper's central derivation chain is self-contained. Algorithm 1 is built directly from the recursive block structure G_N = [[G_{N/2}, 0], [G_{N/2}, G_{N/2}]], using the unique representation x = (x1,0) + (x2,x2) in Section III-A; the theorem about the contribution 2^{w'} * C(N/2 - w', t) is proved by counting choices for x2, and no parameter is fitted. Theorem 2 is proved by induction on n using Algorithm 1's two recursive cases, with the base case S_0^{(0)} = (0,1) matching the definition of the one-row code; the claim that the first nonzero component occurs at weight wt(g_i) is taken from the external reference [6], while the count s_i^{(n)} itself is derived. The partial-order connection in Theorem 4 uses Theorem 3 imported from Schürch [12] as an external input and derives a one-way implication from that partial order to the weight-distribution quantity; the cited partial order is not equivalent to the paper's conclusion, so this is not circular. Theorem 5's minimal-distance inequality is proved by induction with Lemmas 6 and 7, projecting onto coordinate sets I_l and I_l^c and applying the inductive hypothesis or Theorem 2 to the projected cosets; no step assumes the conclusion. The only text-level issue is the apparent typesetting defect in Eq. (11): the proof shows T_{i,j} = |supp(g_i) intersect supp(g_j)| = 2^{t_{i,j}}, which would give wt(g_i+g_j) = wt(g_i)+wt(g_j)-2^{t_{i,j}+1}, whereas the printed formula reads '2t_{i,j+1}'. That is a correctness/typographical concern, not circularity. There are no load-bearing self-citations, no fitted inputs renamed as predictions, and no ansatz smuggled in via citation; the derivation is independent of the quantities it claims to compute.

Assumptions & free parameters 0 free parameters · 5 assumptions · 0 invented entities

The paper's results rest on standard properties of the Arıkan polar transform, the B-MSC symmetry assumption, and a cited partial-order theorem. No free parameters are fitted and no new entities are postulated.

assumptions (5)

standard math G_N = G_2^{⊗n} has the block form [[G_{N/2}, 0], [G_{N/2}, G_{N/2}]] and G_{N/2} is full rank over GF(2).
Used in Section III-A to derive the recursive decomposition (5) that underlies Algorithm 1.
standard math The bit-reversal permutation B_N commutes with G_N (B_N G_N = G_N B_N), so the mapping x = u G_N in (1) is equivalent up to a fixed coordinate permutation to the standard polar transform.
Invoked in Section II to justify dropping B_N, which fixes the row ordering used by all theorems.
domain assumption The channel is a binary-input memoryless symmetric channel (B-MSC), so transmitting the all-zero codeword is without loss of generality for error-probability analysis.
Section II-B uses this to define weight distributions relative to the all-zero codeword.
domain assumption The partial order theorem for synthetic channels [12, Definition 8] is valid for any B-MSC and is used as a black box.
Theorem 3 restates this theorem and Theorem 4 relies on it for the monotonicity conclusion.
domain assumption SC decoding at stage i is equivalent to closest-coset decoding according to (3).
Defines the cosets C^{(n)}(0^{i-1},u_i) whose weight distributions are the object of study; Section II-A.

how reviews work

0 comments

Cite this review

Pith. "Pith review of Weight Distributions for Successive Cancellation Decoding of Polar Codes." pith.science (2026). https://pith.science/paper/QXIBX3VA

@misc{pith2026190806652,
  author       = {Pith},
  title        = {Pith review of: Weight Distributions for Successive Cancellation Decoding of Polar Codes},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/QXIBX3VA}},
  note         = {Machine review of arXiv:1908.06652}
}

read the original abstract

In this paper, we derive the exact weight distributions that emerge during each stage of successive cancellation decoding of polar codes. Though we do not compute the distance spectrum of polar codes, the results allow us to get an estimate of the decoding error probability and to show a link between the first nonzero components of the weight distribution and the partial order between the synthetic channels. Also, we establish the minimal distance between two cosets associated with two paths that differ in two positions. This can be regarded as a first step toward analyzing the weight distributions for the successive cancellation list decoding.

Figures

Figures reproduced from arXiv: 1908.06652 by the authors.

**Figure 1.** The approximate union bound Pub(i) and the bit-channel probabilities of error Pe(i). Only those pairs (Pe(i), Pub(i)) for which the error probability Pe(i) is greater than 10−10 threshold are shown. Additionally, the dashed line (x, x) for x ∈ [10−10 , 100 ] is plotted. 3 4 5 6 7 8 10−5 10−4 10−3 10−2 10−1 100 Signal-to-noise ratio [dB] Bit Error Rate DE UB [PITH_FULL_IMAGE:figures/full_fig_p007_1.png] view at source ↗

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

17 extracted references · 16 canonical work pages

[1]

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

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

work page 2009
[2]

Multilevel codes based on p artitioning,

G. J. Pottie and D. P . Taylor, “Multilevel codes based on p artitioning,” IEEE Trans. Inf. Theory , vol. 35, no. 1, pp. 87–98, 1989

work page 1989
[3]

Efﬁcient design and decoding of polar code s,

P . Trifonov, “Efﬁcient design and decoding of polar code s,” IEEE Trans. Commun. , vol. 60, no. 11, pp. 3221–3227, 2012

work page 2012
[4]

A performance comparison of polar codes and r eed-muller codes,

E. Arıkan, “A performance comparison of polar codes and r eed-muller codes,” IEEE Commun. Lett. , vol. 12, no. 6, pp. 447–449, 2008

work page 2008
[5]

On the spectrum of distances of a multileve l code, decoded by a multistage decoder,

H. Herzberg, “On the spectrum of distances of a multileve l code, decoded by a multistage decoder,” IEEE Trans. Inf. Theory , vol. 43, no. 5, pp. 1736–1740, 1997

work page 1997
[6]

Polar codes for channel and source coding,

S. B. Korada, “Polar codes for channel and source coding, ” Ph.D. dissertation, Lausanne, 2009

work page 2009
[7]

Distance spectrum anal ysis of polar codes,

Z. Liu, K. Chen, K. Niu, and Z. He, “Distance spectrum anal ysis of polar codes,” in 2014 IEEE Wireless Commun. Netw. Conf. (WCNC). IEEE, 2014, pp. 490–495

work page 2014
[8]

List decoding of polar codes,

I. Tal and A. V ardy, “List decoding of polar codes,” IEEE Trans. Inf. Theory , vol. 61, no. 5, pp. 2213–2226, 2015

2015

Show all 17 references

[9]

On probabilistic weight dist ribution of polar codes,

M. V alipour and S. Y ouseﬁ, “On probabilistic weight dist ribution of polar codes,” IEEE Commun. Lett. , vol. 17, no. 11, pp. 2120–2123, 2013

2013
[10]

An enhanced probabilistic computation method for the weight distribution of polar cod es,

Q. Zhang, A. Liu, and X. Pan, “An enhanced probabilistic computation method for the weight distribution of polar cod es,” IEEE Commun. Lett. , vol. 21, no. 12, pp. 2562–2565, 2017

2017
[11]

Weight distribution for clo sest coset decoding of |u|u + v| constructed codes,

M. P . Fossorier and S. Lin, “Weight distribution for clo sest coset decoding of |u|u + v| constructed codes,” IEEE Trans. Inf. Theory , vol. 43, no. 3, pp. 1028–1030, 1997

1997
[12]

A partial order for the synthesized chann els of a polar code,

C. Sch¨ urch, “A partial order for the synthesized chann els of a polar code,” in Proc. IEEE Int. Symp. Inf. Theory (ISIT) , 2016, pp. 220–224

2016
[13]

Alg ebraic properties of polar codes from a new polynomial forma lism,

M. Bardet, V . Dragoi, A. Otmani, and J.-P . Tillich, “Alg ebraic properties of polar codes from a new polynomial forma lism,” in Proc. IEEE Int. Symp. Inf. Theory (ISIT) , 2016, pp. 230–234

2016
[14]

Closest coset decoding of |u|u + v| codes,

F. Hemmati, “Closest coset decoding of |u|u + v| codes,” IEEE J. Sel. Areas Commun. , vol. 7, no. 6, pp. 982–988, 1989

1989
[15]

Principles of communic ation engineering

I. M. Jacobs and J. Wozencraft, “Principles of communic ation engineering.” 1965

1965
[16]

Performance and construction of polar codes on symmetric binary-input memoryless channels ,

R. Mori and T. Tanaka, “Performance and construction of polar codes on symmetric binary-input memoryless channels ,” in Proc. IEEE Int. Symp. Inf. Theory (ISIT) . IEEE, 2009, pp. 1496–1500

2009
[17]

How to construct polar codes,

I. Tal and A. V ardy, “How to construct polar codes,” IEEE Trans. Inf. Theory , vol. 59, no. 10, pp. 6562–6582, 2013

2013

Pith tools

Reviewed August 14, 2026 · model on record in the stance chip above.

[1] [1]

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

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

work page 2009

[2] [2]

Multilevel codes based on p artitioning,

G. J. Pottie and D. P . Taylor, “Multilevel codes based on p artitioning,” IEEE Trans. Inf. Theory , vol. 35, no. 1, pp. 87–98, 1989

work page 1989

[3] [3]

Efﬁcient design and decoding of polar code s,

P . Trifonov, “Efﬁcient design and decoding of polar code s,” IEEE Trans. Commun. , vol. 60, no. 11, pp. 3221–3227, 2012

work page 2012

[4] [4]

A performance comparison of polar codes and r eed-muller codes,

E. Arıkan, “A performance comparison of polar codes and r eed-muller codes,” IEEE Commun. Lett. , vol. 12, no. 6, pp. 447–449, 2008

work page 2008

[5] [5]

On the spectrum of distances of a multileve l code, decoded by a multistage decoder,

H. Herzberg, “On the spectrum of distances of a multileve l code, decoded by a multistage decoder,” IEEE Trans. Inf. Theory , vol. 43, no. 5, pp. 1736–1740, 1997

work page 1997

[6] [6]

Polar codes for channel and source coding,

S. B. Korada, “Polar codes for channel and source coding, ” Ph.D. dissertation, Lausanne, 2009

work page 2009

[7] [7]

Distance spectrum anal ysis of polar codes,

Z. Liu, K. Chen, K. Niu, and Z. He, “Distance spectrum anal ysis of polar codes,” in 2014 IEEE Wireless Commun. Netw. Conf. (WCNC). IEEE, 2014, pp. 490–495

work page 2014

[8] [8]

List decoding of polar codes,

I. Tal and A. V ardy, “List decoding of polar codes,” IEEE Trans. Inf. Theory , vol. 61, no. 5, pp. 2213–2226, 2015

2015