| Description |
Speaker: Satish Korada, Stanford University -- Faculty Host: Venkatesh Saligrama -- In the past decade we have seen significant advances in the field of coding. However, achieving the fundamental performance limit with low-complexity schemes still remained an unsolved problem. Polar codes, recently introduced by Arikan, have changed that picture. These are the first "practical" codes that achieve the capacity for a large class of channels. The code construction is based on a phenomenon called channel polarization. The encoding as well as the decoding operation of polar codes can be implemented with O(N log N) complexity, where 'N' is the block length of the code. In this talk I will show that the principle of polarization has applications to many problems beyond channel coding. The most fundamental among them is the lossy data compression problem. Like the channel coding problem, achieving the Shannon's rate-distortion tradeoff with "low complexity" has been a long-standing open problem. We construct polar codes that asymptotically (in the block length) approach Shannon's rate-distortion tradeoff for a large class of sources. Further, thinking from the polar coding perspective, we construct codes for other problems including video compression (Wyner-Ziv), watermarking (Gelfand-Pinsker), distributed source coding (Slepian-Wolf), multiple access channels, and degraded broadcast channels. For each of these problems, our constructions are the first known "practical" schemes that approach the optimal performance. In spite of the strong theoretical guarantees at large block lengths, at practical lengths polar codes are not record-breaking. I will discuss our attempts to improve their performance. I will end with a perspective of the challenges that lie ahead before we can place polar codes in our cell phones. |
