Complexity and second moment of the mathematical theory of communication

The performance of an error correcting code is evaluated by its block error probability, code rate, and encoding and decoding complexity. The performance of a series of codes is evaluated by, as the block lengths approach infinity, whether their block error probabilities decay to zero, whether their code rates converge to channel capacity, and whether their growth in complexities stays under control. Over any discrete memoryless channel, I build 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 π, ρ > 0 such that π+2ρ < 1, I construct a series of error correcting codes with block length N approaching infinity, block error probability exp(−Nπ), code rate N−ρ less than the channel capacity, and encoding and decoding complexity O(N logN) per code block. Over any discrete memoryless channel, I also build codes such that: for one, they achieve channel capacity rapidly; and for two, their encoding and decoding complexities outperform all known codes over non-BEC channels. Quantitatively, for any constants τ, ρ > 0 such that 2ρ < 1, I construct a series of error correcting codes with block length N approaching infinity, block error probability exp(−(logN)τ ), code rate N−ρ less than the channel capacity, and encoding and decoding complexity O(N log(logN)) per code block. The two aforementioned results are built upon two pillars—a versatile framework that generates codes on the basis of channel polarization, and a calculus–probability machinery that evaluates the performances of codes. The framework that generates codes and the machinery that evaluates codes can be extended to many other scenarios in network information theory. To name a few: lossless compression with side information, lossy compression, Slepian–Wolf problem, Wyner–Ziv Problem, multiple access channel, wiretap channel of type I, and broadcast channel. In each scenario, the adapted notions of block error probability and code rate approach their limits at the same paces as specified above.

Name thesis:degree_name

Ph.D.

Level thesis:degree_level

Dissertation

Discipline thesis:degree_discipline

Mathematics

Grantor

University of Illinois at Urbana-Champaign

Year dc:date

2022

Author dc:creator

• Wang, Hsin-Po

Contributors dc:contributor

• Duursma, Iwan M
• Dey, Partha S
• Balogh, József
• Junge, Marius

• information theory
• coding theory
• polar code
• random code

Statement dc:rights

• Copyright 2021 Hsin-Po Wang

Language dc:language

en

Handle dc:identifier

http://hdl.handle.net/2142/113027

OAI identifier oai:identifier

oai:www.ideals.illinois.edu:2142/113027