On the degradations of Binary-Input Discrete Memoryless Channels

Ming Xu; Xiaoyan Cheng; Yadong Jiao; Yuansheng Tang

arxiv: 2604.25552 · v1 · submitted 2026-04-28 · 💻 cs.IT · math.IT

On the degradations of Binary-Input Discrete Memoryless Channels

Yadong Jiao , Xiaoyan Cheng , Yuansheng Tang , Ming Xu This is my paper

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

classification 💻 cs.IT math.IT

keywords degradationsbinary-input discrete memoryless channelssymmetric capacityprobability of errorpolar codesoutput alphabet reductionchannel reliability

0 comments

The pith

For symmetric binary-input discrete memoryless channels, all degradations that minimize decoding error probability are fully determined, and a necessary condition identifies those that maximize symmetric capacity.

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

The paper examines how to degrade symmetric binary-input discrete memoryless channels by reducing the size of their output alphabets while preserving symmetry and the binary-input property. This matters for polar codes, where synthetic channels produced during construction have output alphabets that grow exponentially and become impossible to evaluate directly. The authors completely characterize every degradation that achieves the lowest possible probability of error when decoding. They also derive a necessary condition that any degradation maximizing symmetric capacity must satisfy and convert that condition into an efficient algorithm for locating the best such schemes.

Core claim

The authors determine all the degradations with the minimum probability of error decoding and give a necessary condition for the degradations with the maximum symmetric capacity. Based on this necessary condition, they propose an efficient algorithm for finding degradation schemes that maximize the symmetric capacity.

What carries the argument

Output-symbol merging operations that preserve symmetry and binary input while shrinking the alphabet of a symmetric binary-input discrete memoryless channel.

If this is right

Every minimum-error-probability degradation of a symmetric BIDMC can be listed explicitly.
Any degradation that maximizes symmetric capacity must obey the derived necessary condition on output merging.
An efficient algorithm locates the symmetric-capacity-maximizing degradation for a given channel.
These results support direct approximation of synthetic-channel reliability during polar-code construction.

Where Pith is reading between the lines

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

The necessary condition may serve as a starting point for algorithms that optimize other channel metrics such as mutual information.
Embedding the algorithm inside polar-code design tools could improve finite-length performance estimates by allowing larger code lengths.
The same merging logic might extend to asymmetric or non-binary channels once symmetry preservation is relaxed.

Load-bearing premise

The channels are symmetric and any allowed degradation must keep both the symmetry and the binary-input property intact.

What would settle it

An explicit output-merging rule applied to a symmetric BIDMC that produces a strictly lower decoding error probability than the paper's full list, or that attains a higher symmetric capacity while violating the stated necessary condition.

Figures

Figures reproduced from arXiv: 2604.25552 by Ming Xu, Xiaoyan Cheng, Yadong Jiao, Yuansheng Tang.

**Figure 1.** Figure 1: ki ′ ,j′ ̸= 0 with σi ′ ≥ εj ′+1 view at source ↗

**Figure 2.** Figure 2: ki ′′,j′′ ̸= 0 with σi ′′ ≤ εj ′′−1. p ∗ j = X i∈[m] k ∗ i,j , ε∗ j = 1 p ∗ j X i∈[m] k ∗ i,jσi , where δ = min{ki∗,j∗ , ki ∗,j∗ }. Then, W ≼P W∗ = P j∈[n] p ∗ jB(ε ∗ j ) ≼P Q. Proof. The proof is given in Appendix B. Remark 1. The first conclusion in Lemma 6 implies: if ki ′ ,j′ ̸= 0 for some i ′ , j′ with σi ′ ≥ εj ′+1, then a better P-degradation may be obtained from W by replacing pj ′B(εj ′) with the … view at source ↗

**Figure 3.** Figure 3: ki∗,j∗ ki ∗,j∗ ̸= 0 with εj∗ ≤ σi∗ < σi ∗ ≤ εj ∗ . obtained from W by replacing pj∗B(εj∗ ) with the particle compounded from those in {(ki∗,j∗ + δ)B(σi∗ ),(ki ∗,j∗ − δ)B(σi ∗ )} ∪ {ki,j∗B(σi) : i ∈ [m] \ {i∗, i∗ }}, and replacing pj ∗B(εj ∗ ) with the particle compounded from those in {(ki∗,j∗ − δ)B(σi∗ ),(ki ∗,j∗ + δ)B(σi ∗ )} ∪ {ki,j∗B(σi) : i ∈ [m] \ {i∗, i∗ }}, respectively, as depicted in view at source ↗

**Figure 4.** Figure 4: Runtime comparison of Algorithm 2 and SMAWK[18] . greatly narrowing the search range. Its time complexity can be approximately expressed as O(n ′ ), where n ′ represents the scale of elements within the valid search range and satisfies n ′ < m−n+1. Especially when the value of m −n + 1 is large, n ′ << m −n + 1, which significantly reduces the actual computational overhead of the algorithm. Therefore, the… view at source ↗

read the original abstract

For the polar codes introduced by Arikan in 2009, the first code family achieving the capacity of binary-input discrete memoryless channels (BIDMCs) with low-complexity encoding and decoding, it is crucial to evaluate the reliability of the synthetic channels resulted in the code construction. Since the synthetic channels have an output alphabet that grows exponentially with the code length, an effective method for faithfully evaluating their reliability is to replace them with degradations of manageable alphabet size. The main aim of this paper is to find the optimal degradations of symmetric BIDMCs. We determine all the degradations with the minimum probability of error decoding and give a necessary condition for the degradations with the maximum symmetric capacity. Finally, based on this necessary condition, we propose an efficient algorithm for finding degradation schemes that maximize the symmetric capacity.

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

The paper fully lists the minimum-error degradations for symmetric BIDMCs and states a necessary condition plus algorithm for maximum symmetric capacity, but the algorithm's optimality is not established.

read the letter

This paper pins down exactly which merges of output symbols minimize the decoding error probability for symmetric binary-input discrete memoryless channels. It also gives a necessary condition on merges that achieve maximum symmetric capacity and turns that condition into an efficient algorithm for finding such degradations. Both results are stated directly in terms of the channel transition probabilities and standard mutual-information quantities, with no hidden fitting parameters or circular reductions to prior fitted values. The min-error enumeration appears complete and new relative to the polar-code degradation literature. The necessary condition is clean enough that the algorithm follows immediately from it. That is the concrete advance for anyone who needs to approximate synthetic channels in polar-code construction with smaller alphabets while preserving symmetry and the binary-input property. The central limitation is that the algorithm rests only on a necessary condition. Nothing in the paper shows that every capacity-maximizing degradation must obey the condition, so the procedure could miss higher-capacity schemes that violate it. For polar-code reliability bounds, where the degradation is meant to give a faithful upper bound on synthetic-channel quality, any gap between the algorithm output and the true maximum symmetric capacity would weaken the evaluation. The authors do not supply exhaustive verification on small alphabets that would confirm the algorithm always reaches the global maximum. The work is aimed at researchers who already work with polar codes or channel degradation routines and need a sharper tool for that narrow sub-task. A reader who wants explicit characterizations rather than another heuristic will find the min-error part immediately usable. The paper deserves a serious referee because the claims are specific, the application is concrete, and the math is grounded in standard information measures; the optimality question is the obvious point for revision.

Referee Report

2 major / 2 minor

Summary. The paper claims to fully characterize all degradations of symmetric binary-input discrete memoryless channels (BIDMCs) that achieve the minimum probability of error, to derive a necessary condition on output-symbol merging for degradations that maximize symmetric capacity I_s, and to give an efficient algorithm that uses this condition to produce candidate optimal degradations. The work is motivated by the need to approximate the reliability of synthetic channels arising in polar-code constructions, where the output alphabet size must be reduced while preserving symmetry and the binary-input property.

Significance. If the necessary condition is tight and the algorithm returns a global maximizer of I_s, the results would supply a practical, theoretically grounded tool for bounding synthetic-channel reliability in polar-code analysis and design. The explicit characterization of minimum-error degradations and the reduction to a merging rule that can be checked in polynomial time would be concrete strengths.

major comments (2)

[Section stating the necessary condition and the algorithm] The central algorithmic claim rests on a necessary condition for maximum I_s (stated after the minimum-error characterization). No proof is given that the condition is also sufficient, nor that every global maximizer satisfies it; therefore the algorithm may miss higher-I_s degradations that violate the merging rule.
[Discussion of polar-code application] For the polar-code application, any gap between the algorithm’s output and the true maximum I_s directly weakens the upper bound on synthetic-channel reliability. The manuscript does not quantify this gap or provide a worst-case example where the necessary condition fails to recover the optimum.

minor comments (2)

[Abstract] The abstract asserts that “all the degradations with the minimum probability of error decoding” are determined; the corresponding theorem should be explicitly cross-referenced so readers can locate the complete list.
[Preliminaries and later sections] Notation for the symmetric capacity I_s and the probability of error P_e should be introduced once in the preliminaries and used consistently; several later sections re-define them inline.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for the thorough review and insightful comments. We address each major comment point by point below, acknowledging the limitations of our current results where appropriate. We will revise the manuscript to clarify the scope of our claims and strengthen the discussion of the polar-code application.

read point-by-point responses

Referee: [Section stating the necessary condition and the algorithm] The central algorithmic claim rests on a necessary condition for maximum I_s (stated after the minimum-error characterization). No proof is given that the condition is also sufficient, nor that every global maximizer satisfies it; therefore the algorithm may miss higher-I_s degradations that violate the merging rule.

Authors: We agree that the condition is presented as necessary but not shown to be sufficient, and that the algorithm therefore optimizes only within the subclass of degradations obeying the merging rule. The manuscript does not claim that every global maximizer satisfies the condition. In the revision we will explicitly rephrase the abstract and the relevant sections to state that the algorithm returns the maximum-I_s degradation among those satisfying the necessary condition. We will also add a new subsection with exhaustive-search comparisons on small channels (where the true optimum is computable) to illustrate how often the condition recovers the global optimum in practice. revision: partial
Referee: [Discussion of polar-code application] For the polar-code application, any gap between the algorithm’s output and the true maximum I_s directly weakens the upper bound on synthetic-channel reliability. The manuscript does not quantify this gap or provide a worst-case example where the necessary condition fails to recover the optimum.

Authors: We concur that the absence of a gap quantification limits the strength of the reliability bounds. Because computing the exact maximum I_s is intractable for large alphabets, we cannot supply a general worst-case gap or a concrete counter-example without solving the original problem. In the revision we will (i) add numerical comparisons against brute-force optima for all symmetric BIDMCs with output size up to 8, (ii) include a dedicated paragraph in the polar-code section that states the obtained I_s values are lower bounds on the true maximum and therefore yield valid (but possibly loose) upper bounds on synthetic-channel reliability, and (iii) note the computational limitation as an open direction for future work. revision: partial

Circularity Check

0 steps flagged

No circularity: derivations are direct from channel definitions and information measures

full rationale

The paper states characterizations of minimum-error degradations and a necessary condition for maximum symmetric capacity directly in terms of transition probabilities and mutual information quantities (standard definitions of degradation and I_s). No step reduces a claimed result to a fitted parameter, self-citation chain, or renamed input; the algorithm enumerates merges satisfying the derived necessary condition without claiming sufficiency or optimality via construction. The derivation chain remains self-contained against external channel models.

Axiom & Free-Parameter Ledger

0 free parameters · 2 axioms · 0 invented entities

The work rests on the standard definition of channel degradation, symmetry of the channel, and the usual information-theoretic quantities (error probability, symmetric capacity). No new free parameters, ad-hoc axioms, or invented entities are introduced.

axioms (2)

standard math A degradation of a channel is a channel whose output is a (possibly randomized) function of the original output.
Invoked in the opening paragraphs to define the objects under study.
domain assumption Symmetric BIDMCs admit a natural notion of symmetric capacity and minimum error probability that are preserved or reduced under degradation.
Used throughout to compare degradations.

pith-pipeline@v0.9.0 · 5436 in / 1312 out tokens · 76322 ms · 2026-05-07T14:37:10.589510+00:00 · methodology

discussion (0)

Reference graph

Works this paper leans on

28 extracted references · 28 canonical work pages

[1]

A mathematical theory of communication,

C. E. Shannon, “A mathematical theory of communication,”Bell Syst. Tech. J.,vol. 27, pp. 379-423 and 623-656, July and Oct. 1948. 29

work page 1948
[2]

Equivalent comparisons of experiments,

D. Blackwell, “Equivalent comparisons of experiments,”Ann. Math. Statist., vol. 24, pp. 265-272, 1953

work page 1953
[3]

Geometic applications of a matrix-searching algorithm,

A. Aggarwal, M. M. Klawe, S. Moran, P. W. Shor, and R. E. Wilber, “Geometic applications of a matrix-searching algorithm,”Algorithmica, vol. 2, no. 2, pp. 195-208, Nov. 1987

work page 1987
[4]

Optimal partitioning for classification and regression trees,

P. A. Chou, “Optimal partitioning for classification and regression trees,”IEEE Trans. Pattern Anal. Mach. Intell., vol. 13, no. 4, pp. 340-354, Apr. 1991

work page 1991
[5]

C. M. Bishop, Pattern Recognition and Machine Learning. New York, NY, USA: Springer-Verlag, 2006

work page 2006
[6]

Richardson and R

T. Richardson and R. Urbanke, Modern Coding Theory. Cambridge, U.K.: Cambridge Univ. Press, 2008

work page 2008
[7]

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

E. Arikan, “Channel polarization: A method for constructing capacity- achieving codes for symmetric binary-input memoryless channels,”IEEE Trans. Inf. Theory,vol. 55, no. 7, pp. 3051-3073, Jul. 2009

work page 2009
[8]

Secrecy-achieving polar-coding for binary-input memoryless symmetric wire-tap channels

E. Hof and S. Shamai (Shitz),“Secrecy-achieving polar-coding for binary-input memoryless symmetric wire-tap channels.”arXiv: 1005. 2759v2,2010

work page 2010
[9]

Nested polar codes for wiretap and relay channels,

M. Andersson, V. Rathi, R. Thobaben, J. Kliewer, and M. Skoglund, “Nested polar codes for wiretap and relay channels,”IEEE Commun. Lett.,vol. 14, no. 8, pp. 752-754, Aug. 2010

work page 2010
[10]

Achieving the secrecy capacity of wiretap channels using polar codes,

H. Mahdavifar and A. Vardy, “Achieving the secrecy capacity of wiretap channels using polar codes,”IEEE Trans. Inf. Theory,vol. 57, no. 10, pp. 6428-6443, Oct. 2011

work page 2011
[11]

On the construction of polar codes,

R. Pedarsani, S. H. Hassani, I. Tal, and E. Telatar, “On the construction of polar codes,”in Proc. IEEE Int. Symp. Inf. Theory (ISIT), Saint Petersburg, Russia, pp. 11-15, Jul. 2011

work page 2011
[12]

Polar coding for secure transmission and key agreement,

O. O. Koyluoglu and H. El Gamal, “Polar coding for secure transmission and key agreement,”IEEE Trans. Inf. Forensics Security,vol. 7, no. 5, pp. 1472-1483, Oct. 2012. 30

work page 2012
[13]

Channel quantizers that maximize random coding exponents for binary-input memoryless channels,

H. Yagi and B. M. Kurkoski, “Channel quantizers that maximize random coding exponents for binary-input memoryless channels,”in Proc. 2012 IEEE Int. Conf. Commum. (ICC’2012),Ottawa, Canada, pp. 2228- 2232, June 2012

work page 2012
[14]

Constructing polar codes for non- binary alphabets and MACs,

I. Tal, A. Sharov, and A. Vardy, “Constructing polar codes for non- binary alphabets and MACs,”in Proc. IEEE Int. Symp. Inf. Theory, Boston, MA, USA, pp. 2132-2136, Jul. 2012

work page 2012
[15]

Channel upgrading for semantically-secure en- cryption on wiretap channels,

I. Tal and A. Vardy, “Channel upgrading for semantically-secure en- cryption on wiretap channels,”in Proc. IEEE Int. Symp. Inf. Theory (ISIT),pp. 1561-1565, Jul. 2013

work page 2013
[16]

How to construct polar codes,

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

work page 2013
[17]

Quantization of binary-input discrete memo- ryless channels,

M. Kurkoski and H. Yagi, “Quantization of binary-input discrete memo- ryless channels,”IEEE Trans. Inf. Theory,vol. 60, no. 8, pp. 4544-4552, Aug. 2014

work page 2014
[18]

Quantizer design for outputs of binary- input discrete memoryless channels using SMAWK algorithm,

K. I. Iwata and S. Y. Ozawa, “Quantizer design for outputs of binary- input discrete memoryless channels using SMAWK algorithm,”in Proc. IEEE Int. Symp. Inf. Theory,pp. 191-195, Jun. 2014

work page 2014
[19]

Optimal quantization of B-DMCs maximizing α-mutual information with Monge property,

Y. Sakai and K.-I. Iwata, “Optimal quantization of B-DMCs maximizing α-mutual information with Monge property,”in Proc. IEEE Int. Symp. Inf. Theory (ISIT),pp. 25-30, Jun. 2017

work page 2017
[20]

On the construction of polar codes for channels with moderate input alphabet sizes,

I. Tal, “On the construction of polar codes for channels with moderate input alphabet sizes,”IEEE Trans. Inf. Theory,vol. 63, no. 3, pp. 1501- 1509, Mar. 2017

work page 2017
[21]

Construction of polar codes for arbitrary discrete memoryless channels,

T. C. Gulcu, M. Ye, and A. Barg, “Construction of polar codes for arbitrary discrete memoryless channels,”IEEE Trans. Inf. Theory,vol. 64, no. 1, pp. 309-321, Jan. 2018

work page 2018
[22]

Greedy-Merge degrading has optimal power- law,

A. Kartowsky and I. Tal, “Greedy-Merge degrading has optimal power- law,”IEEE Trans. Inf. Theory,vol. 65, no. 2, pp. 917-934, Feb. 2019

work page 2019
[23]

Channel polarization through the lens of Blackwell measures,

N. Goela and M. Raginsky, “Channel polarization through the lens of Blackwell measures,”IEEE Trans. Inf. Theory,vol. 66, no. 10, pp. 6222- 6241, July 2020. 31

work page 2020
[24]

An upgrading algorithm with optimal power law,

O. Ordentlich and I. Tal, “An upgrading algorithm with optimal power law,”IEEE Trans. Inf. Theory,vol. 67, no. 12, pp. 7822-7836, Dec. 2021

work page 2021
[25]

The polarization of hybrid multi-kernel polar codes,

R. Song, M. Xu and Y. Tang, “The polarization of hybrid multi-kernel polar codes,”Journal of Guangxi Normal University (Natural Science Edition),vol. 39, no. 3, pp. 69-82, May. 2021

work page 2021
[26]

On the synthetic channels in polar codes over binary-input discrete memoryless channels,

Y. Jiao, X. Cheng, Y. Tang and M. Xu, “On the synthetic channels in polar codes over binary-input discrete memoryless channels,”in arXiv preprint arXiv: 2506. 04163,2025. 9 Appendices 9.1 Appendix A: Proof of Theorem 1 Proof.Assume thatWis a degradation ofQwith intermediate channelP. With respect to (4), we see that, by ordering the outputs properly, the ...

work page 2025
[27]

decreasing on(a, c]iff ′(c)≤0, 38

work page
[28]

Now we give a proof for Lemma 7

increasing on[c, b)iff ′(c)≥0. Now we give a proof for Lemma 7. Proof.Fora, t∈(0,1/2), let ga(t) =aln ta at −ln t a. Then, we haveg ′ a(t) = (t−a)/( tt) and thusg a(t) is decreasing on (0, a] and increasing on [a,1/2). Hence, we haveg a(t)> g a(a) = 0 fort∈(0,1/2)\ {a}. Then, from ln(( ε1ε2)/(ε2ε1))>0 we see ϕ(ε1, ε2)−ε 2 = ln(ε1/ε2)−ε 2 ln((ε1ε2)/(ε2ε1))...

work page

[1] [1]

A mathematical theory of communication,

C. E. Shannon, “A mathematical theory of communication,”Bell Syst. Tech. J.,vol. 27, pp. 379-423 and 623-656, July and Oct. 1948. 29

work page 1948

[2] [2]

Equivalent comparisons of experiments,

D. Blackwell, “Equivalent comparisons of experiments,”Ann. Math. Statist., vol. 24, pp. 265-272, 1953

work page 1953

[3] [3]

Geometic applications of a matrix-searching algorithm,

A. Aggarwal, M. M. Klawe, S. Moran, P. W. Shor, and R. E. Wilber, “Geometic applications of a matrix-searching algorithm,”Algorithmica, vol. 2, no. 2, pp. 195-208, Nov. 1987

work page 1987

[4] [4]

Optimal partitioning for classification and regression trees,

P. A. Chou, “Optimal partitioning for classification and regression trees,”IEEE Trans. Pattern Anal. Mach. Intell., vol. 13, no. 4, pp. 340-354, Apr. 1991

work page 1991

[5] [5]

C. M. Bishop, Pattern Recognition and Machine Learning. New York, NY, USA: Springer-Verlag, 2006

work page 2006

[6] [6]

Richardson and R

T. Richardson and R. Urbanke, Modern Coding Theory. Cambridge, U.K.: Cambridge Univ. Press, 2008

work page 2008

[7] [7]

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

E. Arikan, “Channel polarization: A method for constructing capacity- achieving codes for symmetric binary-input memoryless channels,”IEEE Trans. Inf. Theory,vol. 55, no. 7, pp. 3051-3073, Jul. 2009

work page 2009

[8] [8]

Secrecy-achieving polar-coding for binary-input memoryless symmetric wire-tap channels

E. Hof and S. Shamai (Shitz),“Secrecy-achieving polar-coding for binary-input memoryless symmetric wire-tap channels.”arXiv: 1005. 2759v2,2010

work page 2010

[9] [9]

Nested polar codes for wiretap and relay channels,

M. Andersson, V. Rathi, R. Thobaben, J. Kliewer, and M. Skoglund, “Nested polar codes for wiretap and relay channels,”IEEE Commun. Lett.,vol. 14, no. 8, pp. 752-754, Aug. 2010

work page 2010

[10] [10]

Achieving the secrecy capacity of wiretap channels using polar codes,

H. Mahdavifar and A. Vardy, “Achieving the secrecy capacity of wiretap channels using polar codes,”IEEE Trans. Inf. Theory,vol. 57, no. 10, pp. 6428-6443, Oct. 2011

work page 2011

[11] [11]

On the construction of polar codes,

R. Pedarsani, S. H. Hassani, I. Tal, and E. Telatar, “On the construction of polar codes,”in Proc. IEEE Int. Symp. Inf. Theory (ISIT), Saint Petersburg, Russia, pp. 11-15, Jul. 2011

work page 2011

[12] [12]

Polar coding for secure transmission and key agreement,

O. O. Koyluoglu and H. El Gamal, “Polar coding for secure transmission and key agreement,”IEEE Trans. Inf. Forensics Security,vol. 7, no. 5, pp. 1472-1483, Oct. 2012. 30

work page 2012

[13] [13]

Channel quantizers that maximize random coding exponents for binary-input memoryless channels,

H. Yagi and B. M. Kurkoski, “Channel quantizers that maximize random coding exponents for binary-input memoryless channels,”in Proc. 2012 IEEE Int. Conf. Commum. (ICC’2012),Ottawa, Canada, pp. 2228- 2232, June 2012

work page 2012

[14] [14]

Constructing polar codes for non- binary alphabets and MACs,

I. Tal, A. Sharov, and A. Vardy, “Constructing polar codes for non- binary alphabets and MACs,”in Proc. IEEE Int. Symp. Inf. Theory, Boston, MA, USA, pp. 2132-2136, Jul. 2012

work page 2012

[15] [15]

Channel upgrading for semantically-secure en- cryption on wiretap channels,

I. Tal and A. Vardy, “Channel upgrading for semantically-secure en- cryption on wiretap channels,”in Proc. IEEE Int. Symp. Inf. Theory (ISIT),pp. 1561-1565, Jul. 2013

work page 2013

[16] [16]

How to construct polar codes,

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

work page 2013

[17] [17]

Quantization of binary-input discrete memo- ryless channels,

M. Kurkoski and H. Yagi, “Quantization of binary-input discrete memo- ryless channels,”IEEE Trans. Inf. Theory,vol. 60, no. 8, pp. 4544-4552, Aug. 2014

work page 2014

[18] [18]

Quantizer design for outputs of binary- input discrete memoryless channels using SMAWK algorithm,

K. I. Iwata and S. Y. Ozawa, “Quantizer design for outputs of binary- input discrete memoryless channels using SMAWK algorithm,”in Proc. IEEE Int. Symp. Inf. Theory,pp. 191-195, Jun. 2014

work page 2014

[19] [19]

Optimal quantization of B-DMCs maximizing α-mutual information with Monge property,

Y. Sakai and K.-I. Iwata, “Optimal quantization of B-DMCs maximizing α-mutual information with Monge property,”in Proc. IEEE Int. Symp. Inf. Theory (ISIT),pp. 25-30, Jun. 2017

work page 2017

[20] [20]

On the construction of polar codes for channels with moderate input alphabet sizes,

I. Tal, “On the construction of polar codes for channels with moderate input alphabet sizes,”IEEE Trans. Inf. Theory,vol. 63, no. 3, pp. 1501- 1509, Mar. 2017

work page 2017

[21] [21]

Construction of polar codes for arbitrary discrete memoryless channels,

T. C. Gulcu, M. Ye, and A. Barg, “Construction of polar codes for arbitrary discrete memoryless channels,”IEEE Trans. Inf. Theory,vol. 64, no. 1, pp. 309-321, Jan. 2018

work page 2018

[22] [22]

Greedy-Merge degrading has optimal power- law,

A. Kartowsky and I. Tal, “Greedy-Merge degrading has optimal power- law,”IEEE Trans. Inf. Theory,vol. 65, no. 2, pp. 917-934, Feb. 2019

work page 2019

[23] [23]

Channel polarization through the lens of Blackwell measures,

N. Goela and M. Raginsky, “Channel polarization through the lens of Blackwell measures,”IEEE Trans. Inf. Theory,vol. 66, no. 10, pp. 6222- 6241, July 2020. 31

work page 2020

[24] [24]

An upgrading algorithm with optimal power law,

O. Ordentlich and I. Tal, “An upgrading algorithm with optimal power law,”IEEE Trans. Inf. Theory,vol. 67, no. 12, pp. 7822-7836, Dec. 2021

work page 2021

[25] [25]

The polarization of hybrid multi-kernel polar codes,

R. Song, M. Xu and Y. Tang, “The polarization of hybrid multi-kernel polar codes,”Journal of Guangxi Normal University (Natural Science Edition),vol. 39, no. 3, pp. 69-82, May. 2021

work page 2021

[26] [26]

On the synthetic channels in polar codes over binary-input discrete memoryless channels,

Y. Jiao, X. Cheng, Y. Tang and M. Xu, “On the synthetic channels in polar codes over binary-input discrete memoryless channels,”in arXiv preprint arXiv: 2506. 04163,2025. 9 Appendices 9.1 Appendix A: Proof of Theorem 1 Proof.Assume thatWis a degradation ofQwith intermediate channelP. With respect to (4), we see that, by ordering the outputs properly, the ...

work page 2025

[27] [27]

decreasing on(a, c]iff ′(c)≤0, 38

work page

[28] [28]

Now we give a proof for Lemma 7

increasing on[c, b)iff ′(c)≥0. Now we give a proof for Lemma 7. Proof.Fora, t∈(0,1/2), let ga(t) =aln ta at −ln t a. Then, we haveg ′ a(t) = (t−a)/( tt) and thusg a(t) is decreasing on (0, a] and increasing on [a,1/2). Hence, we haveg a(t)> g a(a) = 0 fort∈(0,1/2)\ {a}. Then, from ln(( ε1ε2)/(ε2ε1))>0 we see ϕ(ε1, ε2)−ε 2 = ln(ε1/ε2)−ε 2 ln((ε1ε2)/(ε2ε1))...

work page