## Abstract

A pruned variant of polar coding is proposed for binary erasure channel (BEC). Fix any BEC. For sufficiently small varepsilon >{0} , we construct a series of capacity achieving codes with block length text {N}=varepsilon {-{4.9}} , code rate text {R}=text {Capacity}-text {O}(varepsilon) , block error probability text {P}=varepsilon , and encoding and decoding time complexity mathop {mathrm {bC}} =text {O}(log lvert log varepsilon rvert) per information bit. The given per-bit complexity mathop {mathrm {bC}} is log-logarithmic in N, in text {Capacity}-text {R} , and in P. Beyond BEC, there is a generalization: Fix a prime q and fix a symmetric, q-ary-input, discrete-output memoryless channel. For sufficiently small varepsilon >0 , we construct a series of error correction codes with block length text {N}=varepsilon {-text {constant}} , code rate text {R}=text {Capacity}-text {O}(varepsilon) , block error probability text {P}=varepsilon , and encoding and decoding time complexity mathop {mathrm {bC}} =text {O}(log lvert log varepsilon rvert) per information bit. Over general channels, this family of codes has the lowest per-bit time complexity among all capacity-achieving codes known to date.

Original language | English (US) |
---|---|

Article number | 9274497 |

Pages (from-to) | 1509-1521 |

Number of pages | 13 |

Journal | IEEE Transactions on Information Theory |

Volume | 67 |

Issue number | 3 |

DOIs | |

State | Published - Mar 2021 |

## Keywords

- Capacity-achieving codes
- low-complexity codes
- polar codes
- tree pruning

## ASJC Scopus subject areas

- Information Systems
- Computer Science Applications
- Library and Information Sciences