RECORD
Log-logarithmic Time Pruned Polar Coding
Information Theory · Submitted 30 May 2019
abstract compiled · 2026-09-23 · no language-model review
The authors' main claim The given per-bit complexity $\text{bC}$ is log-logarithmic in $N$, in $\text{Capacity}-R$, and in $P$; no known family of codes possesses this property.
The compiled record
The paper's own sentences, arranged. Each label is drawn from a closed vocabulary; the number beside it is the probability the classifier gave that label. Numbers in the tables are the authors', checked by code. No sentence in this record was written by a model.
Open the compiled record
The abstract, sentence by sentence
A pruned variant of polar coding is proposed for binary erasure channels. For sufficiently small $\varepsilon>0$, we construct a series of capacity achieving codes with block length $N=\varepsilon^{-5}$, code rate $R=\text{Capacity}-\varepsilon$, error probability $P=\varepsilon$, and encoding and decoding time complexity $\text{bC}=O(\log\left|\log\varepsilon\right|)$ per information bit. The given per-bit complexity $\text{bC}$ is log-logarithmic in $N$, in $\text{Capacity}-R$, and in $P$; no known family of codes possesses this property. It is also the second lowest $\text{bC}$ after repeat-accumulate codes and their variants. While random codes and classical polar codes are the only two families of capacity-achieving codes whose $N$, $R$, $P$, and $\text{bC}$ were written down as explicit functions, our construction gives the third family. Then we generalize the result to: Fix a prime $q$ and fix a $q$-ary-input discrete symmetric memoryless channel. For sufficiently small $\varepsilon>0$, we construct a series of capacity achieving codes with block length $N=\varepsilon^{-O(1)}$, code rate $R=\text{Capacity}-\varepsilon$, error probability $P=\varepsilon$, and encoding and decoding time complexity $\text{bC}=O(\log\left|\log\varepsilon\right|)$ per information bit. The later construction gives the fastest family of capacity-achieving codes to date on those channels.
background contribution method result interpretation main claim
| # | sentence | role | the authors' own work | states the main conclusion | strength |
|---|---|---|---|---|---|
| s0 | A pruned variant of polar coding is proposed for binary erasure channels. | contribution 1.00 | 0.89 | 0.12 | asserted 1.00 |
| s1 | For sufficiently small $\varepsilon>0$, we construct a series of capacity achieving codes with block length $N=\varepsilon^{-5}$, code rate $R=\text{Capacity}-\varepsilon$, error probability $P=\varepsilon$, and encoding and decoding time complexity $\text{bC}=O(\log\left|\log\varepsilon\right|)$ per information bit. | result 0.88 | 0.95 | 0.59 | asserted 1.00 |
| s2 | The given per-bit complexity $\text{bC}$ is log-logarithmic in $N$, in $\text{Capacity}-R$, and in $P$; no known family of codes possesses this property. | result 0.46 | 0.79 | 0.58 | asserted 1.00 |
| s3 | It is also the second lowest $\text{bC}$ after repeat-accumulate codes and their variants. | result 0.50 | 0.43 | 0.10 | asserted 1.00 |
| s4 | While random codes and classical polar codes are the only two families of capacity-achieving codes whose $N$, $R$, $P$, and $\text{bC}$ were written down as explicit functions, our construction gives the third family. | contribution 0.40 | 0.81 | 0.19 | asserted 1.00 |
| s5 | Then we generalize the result to: Fix a prime $q$ and fix a $q$-ary-input discrete symmetric memoryless channel. | contribution 0.80 | 0.78 | 0.05 | asserted 0.68 |
| s6 | For sufficiently small $\varepsilon>0$, we construct a series of capacity achieving codes with block length $N=\varepsilon^{-O(1)}$, code rate $R=\text{Capacity}-\varepsilon$, error probability $P=\varepsilon$, and encoding and decoding time complexity $\text{bC}=O(\log\left|\log\varepsilon\right|)$ per information bit. | result 0.68 | 0.95 | 0.34 | asserted 1.00 |
| s7 | The later construction gives the fastest family of capacity-achieving codes to date on those channels. | interpretation 0.63 | 0.76 | 0.36 | asserted 1.00 |
What was examined, and what was not
- arXiv listing abstract v1
- full text
- figures and tables
- references and citing sentences
- relations to other papers
- P abstract
- S sections
- T body sentences
- C citations
- R cross-paper relations
The paper
Original abstract
A pruned variant of polar coding is proposed for binary erasure channels. For sufficiently small $\varepsilon>0$, we construct a series of capacity achieving codes with block length $N=\varepsilon^{-5}$, code rate $R=\text{Capacity}-\varepsilon$, error probability $P=\varepsilon$, and encoding and decoding time complexity $\text{bC}=O(\log\left|\log\varepsilon\right|)$ per information bit. The given per-bit complexity $\text{bC}$ is log-logarithmic in $N$, in $\text{Capacity}-R$, and in $P$; no known family of codes possesses this property. It is also the second lowest $\text{bC}$ after repeat-accumulate codes and their variants. While random codes and classical polar codes are the only two families of capacity-achieving codes whose $N$, $R$, $P$, and $\text{bC}$ were written down as explicit functions, our construction gives the third family. Then we generalize the result to: Fix a prime $q$ and fix a $q$-ary-input discrete symmetric memoryless channel. For sufficiently small $\varepsilon>0$, we construct a series of capacity achieving codes with block length $N=\varepsilon^{-O(1)}$, code rate $R=\text{Capacity}-\varepsilon$, error probability $P=\varepsilon$, and encoding and decoding time complexity $\text{bC}=O(\log\left|\log\varepsilon\right|)$ per information bit. The later construction gives the fastest family of capacity-achieving codes to date on those channels.
Human review
How the literature uses it
1 arXiv paper cite this in 1 sentence
Papers citing it
Cites it as background 1 paper
-
Among the chapters: <Ref> was presented in the preprint [ref] . <Ref> was presented in the preprints [ref] and [ref] , the latter of which was later published in IEEE Transactions on Information Theory [ref] . <Ref> was presented in the preprint [ref] . <Ref> was presented in the preprint [ref] , which was later published in IEEE Transactions on Information Theory [ref] .
Complexity and Second Moment of the Mathematical Theory of Communication · Organization of the Dissertation · 0.92
What it cites · 10 sentences without a confident label
Uses the method or tool of 1 paper
-
We want to find constants $μ>0$ and $β>0$ such that the process $I_i$ satisfies [equation] We borrow terminologies and lemmas from [ref] for a head start.
General Strong Polarization · Proof of Theorem [ref] · 0.93
Cites as support 1 paper
-
By [ref] , the process $I_i$ corresponding to $$ is locally polarizing.
General Strong Polarization · Proof of Theorem [ref] · 0.96
Discussion
Know something about this paper? Leave a comment, or highlight any passage above to comment on it.