Polar codes, introduced by Arıkan in 2009, gave the first solution to the problem of
designing explicit coding schemes that attain Shannon capacity of several basic models
of communication channels. This discovery made it possible to attain theoretical limits
of communication in a number of other problems of data compression and multi-user
communication as well as provided new perspectives on extremal configurations of some
discrete-time random walks.
This thesis is devoted to the design of communication protocols for several basic
information-theoretic problems as well to the problem of efficient construction of polar
codes.
In the first part we consider the problem of optimizing the amount of data transmitted
between two terminals performing interactive computation of a function. Informationtheoretic
limits for one model of interactive computation were found in recent literature.
We consider the distributed source coding problem that arises in the analysis of this model,designing a polar coding scheme that serves the basis for the distributed computation. As
a result, it becomes possible to attain the smallest possible rate of data exchange between
the terminals using an explicit protocol of encoding and data exchange that supports reliable
computation of the function by both parties. We also extend our considerations to a
multi-terminal variation of this problem.
Secondly, we turn to the problem of communication between two parties over a link
observed by an adversary, known as the "wiretap channel." Explicit capacity-achieving
schemes for various models of the wiretap channel have received significant attention in
recent literature. In this work, we address the general model of the channel, removing the
constraints on the channels adopted in the earlier works. We show that secrecy capacity
of the wiretap channel under a "strong secrecy constraint" can be achieved using an explicit
scheme based on polar codes. We also extend our construction to the case of the
broadcast channel with confidential messages due to Csisz´ar and K¨orner, achieving the
entire capacity region of this communication model.
In the last part of the thesis we consider the problem of efficient construction of
polar codes. While Arıkan's scheme is explicit, his original proposal suffers from high
construction complexity which grows exponentially with the number of evolution steps.
An approximation procedure for binary-input channels was proposed and analyzed in
the literature. Here we propose and study a construction algorithm for polar codes with
arbitrarily-sized input alphabets. We establish a complexity estimate of the algorithm and
derive an estimate of the approximation error that ensues from its use. The approximation
error reduces the gap to the recently established lower bound for this type of algorithms.
The validity of the proposed algorithm is supported by experimental results. |