Asea Brown Boveri Ltd. (ABB) Award 2018 – Mani Bastani Parizi
Coding for Communications and Secrecy
EPFL thesis n°7751 (2017)
Thesis director: Prof. E. Telatar
"For contributions to the theory and practice of polar codes, and to the theory of covert communications."
Shannon, in 1948, showed that reliable communication over a channel is possible at any rate below its capacity. In 2008, Arikan discovered polar codes; the first class of explicitly constructed low-complexity codes that achieve the capacity of any binary-input memoryless symmetric-output channel.
We derive a lower bound on the block-error probability of polar codes when used for communication over an erasure channel, and consequently, prove the tightness of the known upper bound. We study list decoding of polar codes and give a numerically stable formulation of the method. In hardware implementation, our formulation increases the decoding throughput by 53% and reduces the decoder's size by about 33%.
Based on Shannon's framework, Wyner, in 1975, considered communications in the presence of an eavesdropper. We derive the exact exponential decay rate of the information leaked to the eavesdropper in Wyner's model when a randomly constructed code is used for secure communications.
The key to securing messages against an eavesdropper is ensuring that her observations are approximations to pure noise. We show that the presence of feedback does not reduce the minimum entropy rate required for this approximation, but there are examples where feedback allows for much larger exponents.