{"id":"741298dc-b30d-422d-9a2a-c01406646945","arxiv_id":"1908.06652","paper_version":3,"verdict":"ACCEPT","confidence":"MODERATE","novelty_score":7.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"For polar codes, this paper gives a recursive algorithm and closed-form formulas for the weight distributions seen by successive cancellation decoding, plus a minimal-distance result for two-error paths.","lead":"Polar codes are decoded stage by stage, and at each stage the decoder compares two sets of possible codewords. This paper computes exactly how many codewords of each weight appear in those sets, which helps predict decoding errors and opens a path to analyzing list decoding.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Theorem 5's stated formula (11) for wt(gi+gj) is inconsistent with the proof and with direct computation, indicating a missing exponent in the printed formula.","rationale":"The paper's primary contributions are the exact SC weight-distribution algorithm (Algorithm 1 / Theorem 1), the explicit first-nonzero-component formula (Theorem 2), and the minimal-distance result for paths differing in two positions (Theorem 5). The reader accepted the paper, correctly noting that Algorithm 1 and Theorem 2 check out against examples and have no circularity. However, the stress-test found a concrete correctness defect in Theorem 5 as printed: Eq. (11) gives wrong numerical values (e.g., N=8, i=1, j=3 yields 6 instead of 2), and the proof's assertion 'Ti,j = 2 ti,j' is inconsistent with its own inductive calculation, which establishes T_{i,j}=2^{t_{i,j}}. The likely cause is a typesetting loss of exponent braces, since the corrected formula wt(gi)+wt(gj)-2^{t_{i,j}+1} matches all checked cases and the induction. Because Theorem 5 is explicitly advertised in the abstract as a main result, the published statement must be fixed before the claim is accepted as stated. The underlying inequality wt(x) >= wt(gi+gj) appears to survive the correction, so the appropriate disposition is a conditional acceptance: require the authors to correct Eq. (11) and the supporting T_{i,j} equality, and to re-verify the examples. Algorithm 1 and Theorem 2 are not implicated by this concern.","tokens_in":125,"tokens_out":13683,"duration_ms":183034,"concrete_test":"For N=8, compute g1 and g3 via the Kronecker-product formula (12), form their sum, and compare wt(g1+g3) with Eq. (11) as printed (using t_{1,4}) and with the corrected expression wt(g1)+wt(g3)-2^{t_{1,3}+1}. Also compute |supp(g1)∩supp(g3)| and check whether it equals 2^{t_{1,3}} or 2 t_{1,3}.","verdict_should_be":"CONDITIONAL","load_bearing_attack":"Theorem 5 states that for any i<j and any x in C^(n)(i,j), wt(x) >= wt(gi+gj), and gives the closed form wt(gi+gj)=wt(gi)+wt(gj)-2 t_{i,j+1} in Eq. (11), with t_{i,j} defined as the dot product of the binary expansions of i and j. This formula is false as printed. For N=8, i=1, j=3: g1=(1,1,0,0,0,0,0,0) and g3=(1,1,1,1,0,0,0,0), so wt(g1+g3)=wt(0,0,1,1,0,0,0,0)=2. Yet wt(g1)=2, wt(g3)=4, and t_{1,4}=0, giving RHS=6. The proof itself contains the supporting claim 'Ti,j = 2 ti,j' in Section IV, but the induction actually shows T_{i,j}=|supp(gi)∩supp(gj)|=2^{t_{i,j}} (a power, not a product), as is evident from the step T_{i,j}=2^{b_{n-1}(i)b_{n-1}(j)} T_{f(i),f(j)}. With the exponent, wt(gi+gj)=wt(gi)+wt(gj)-2^{t_{i,j}+1}, which gives 2+4-4=2 for the example. The core inequality wt(x) >= wt(gi+gj) is proved independently of Eq. (11) and likely remains valid; however, the theorem's explicit minimal-distance formula is part of the stated central result and is incorrect as written.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","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.","tokens_in":14774,"tokens_out":6991,"duration_ms":71431,"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":[{"comment":"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":"Theorem 5, Eq. (11)"},{"comment":"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).","section":"Section IV, proof of Theorem 5"}],"minor_comments":[{"comment":"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.","section":"Section III-A, after Eq. (5)"},{"comment":"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.","section":"Theorem 2, Eq. (7)"},{"comment":"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.","section":"Figure 1 and Figure 2"}],"recommendation":"major_revision","confidential_remarks":"The paper is technically sound in its main derivations, and the error in Eq. (11) appears to be a correctable typesetting problem rather than a fundamental flaw. I recommend major revision so that the authors fix the formula and its proof display, then the paper could become acceptable. The manuscript is within the scope of the journal."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","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.\n\nWhat'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.\n\nThe 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.\n\nOther 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.\n\nWho 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.","headline":"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.","tokens_in":15283,"tokens_out":3198,"would_cite":true,"duration_ms":29357,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["94B05","94B35"],"pacs":[],"model":"deepseek-v4-flash","headline":"Exact formula found for first nonzero weight in polar SC decoding","keywords":["polar codes","weight distribution","successive cancellation decoding","coset decoding","partial order","list decoding","first nonzero component","|u|u+v| construction"],"falsifier":"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.","tokens_in":14222,"feed_emoji":"🧮","tokens_out":2855,"duration_ms":28422,"temperature":0.7,"pith_summary":"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.","feed_headline":"Exact formula found for first nonzero weight in polar SC decoding","feed_subtitle":"A recursive algorithm and a closed form tie coset weights to the partial order of synthetic channels.","key_machinery":"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.","core_discovery":"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$.","pith_inferences":["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."],"forward_implications":["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."],"supporting_citations":[{"why":"Introduces polar codes, the generator matrix $G_N$, and successive cancellation decoding, providing the fundamental setting and the bit-reversal discussion that allows dispensing with $B_N$.","marker":"[1]"},{"why":"Supplies the $|u|u+v|$ weight-distribution method that Algorithm 1 adapts to polar codes.","marker":"[11]"},{"why":"Establishes the previously known minimal distance for SC decoding, which the paper later generalizes in Theorem 5.","marker":"[6]"},{"why":"Defines the partial order on synthetic channels used in Theorem 3 and Theorem 4.","marker":"[12]"},{"why":"Provides the closest coset decoding viewpoint that frames SC decoding as selecting a coset, the setting for weight distributions.","marker":"[14]"},{"why":"Gives the union bound equations used in the approximate upper bound on error probability.","marker":"[15]"},{"why":"Introduces successive cancellation list decoding, the target context for Theorem 5's minimal distance result.","marker":"[8]"}],"fun_headline_variants":["Exact weights for each stage of polar SC decoding","First nonzero weight formula for polar SC decoding","Recursive and closed form for SC decoding weights","Link between weights and partial order in polar SC"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"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.","fun_headline_variants_meta":{"raw":{"variants":["Exact weights for each stage of polar SC decoding","First nonzero weight formula for polar SC decoding","Recursive and closed form for SC decoding weights","Link between weights and partial order in polar SC"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000193,"raw_usage":{"total_tokens":1368,"prompt_tokens":978,"completion_tokens":390,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":594,"completion_tokens_details":{"reasoning_tokens":331}},"tokens_in":594,"tokens_out":390,"duration_ms":4012,"temperature":1.0,"reasoning_tokens":331,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-14T12:38:44.222775+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"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.","supporting_citations":[{"cited_title":"Channel polarization: A method for construc ting capacity-achieving codes for symmetric binary-input memoryless channels,","cited_arxiv_id":null,"evidence_quote":"Introduces polar codes, the generator matrix $G_N$, and successive cancellation decoding, providing the fundamental setting and the bit-reversal discussion that allows dispensing with $B_N$."},{"cited_title":"Weight distribution for clo sest coset decoding of |u|u + v| constructed codes,","cited_arxiv_id":null,"evidence_quote":"Supplies the $|u|u+v|$ weight-distribution method that Algorithm 1 adapts to polar codes."},{"cited_title":"Polar codes for channel and source coding,","cited_arxiv_id":null,"evidence_quote":"Establishes the previously known minimal distance for SC decoding, which the paper later generalizes in Theorem 5."},{"cited_title":"A partial order for the synthesized chann els of a polar code,","cited_arxiv_id":null,"evidence_quote":"Defines the partial order on synthetic channels used in Theorem 3 and Theorem 4."},{"cited_title":"Closest coset decoding of |u|u + v| codes,","cited_arxiv_id":null,"evidence_quote":"Provides the closest coset decoding viewpoint that frames SC decoding as selecting a coset, the setting for weight distributions."},{"cited_title":"Principles of communic ation engineering","cited_arxiv_id":null,"evidence_quote":"Gives the union bound equations used in the approximate upper bound on error probability."}],"review_version":1}