Polar Codes' Simplicity, Random Codes' Durability

Hsin Po Wang, Iwan M. Duursma

Research output: Contribution to journalArticlepeer-review


Over any discrete memoryless channel, we offer error correction codes such that: for one, their block error probabilities and code rates scale like random codes'; and for two, their encoding and decoding complexities scale like polar codes'. Quantitatively, for any constants pi,rho >0 such that pi +2rho < 1 , we construct a sequence of block codes with block length {N} approaching infinity, block error probability exp (-{N}pi) , code rate {N}{-rho } less than the Shannon capacity, and encoding and decoding complexity {O}({N}log {N}) per code block. The core theme is to incorporate polar coding (which limits the complexity to polar's realm) with large, random, dynamic kernels (which boosts the performance to random's realm). The putative codes are optimal in the following manner: Should pi +2rho >1 , no such codes exist over generic channels regardless of complexity.

Original languageEnglish (US)
Article number9274521
Pages (from-to)1478-1508
Number of pages31
JournalIEEE Transactions on Information Theory
Issue number3
StatePublished - Mar 2021


  • Capacity-achieving codes
  • low-complexity codes
  • polar codes
  • random codes

ASJC Scopus subject areas

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


Dive into the research topics of 'Polar Codes' Simplicity, Random Codes' Durability'. Together they form a unique fingerprint.

Cite this