Polar Codes for Channel and Source Coding
Polar Codes for Channel and Source Coding
复制标题
DOI：
10.5075/epfl-thesis-4461
复制
发表时间：
2009-01
期刊：
影响因子：
--
通讯作者：
Nadine Hussami;Satish Babu Korada;R. Urbanke
中科院分区：
文献类型：
--
作者：
Nadine Hussami;Satish Babu Korada;R. Urbanke
信息理论的两个主要主题是数据的压缩和传输。香农在他的开创性工作中正式化了这两个问题并确定了它们的基本限制。从那时起，编码理论的主要目标是找到实现这些限制的实用方案。最近由阿里坎（Arikan）发明的极地代码是第一个已知实现大量渠道能力的“实用”代码。他们的代码构建基于一种称为“通道极化”的现象。可以使用O（n log n）复杂性来实现极地代码的编码和解码操作，其中n是代码的块长度。我们表明，极地代码不仅适用于通道编码，而且还适用于信息理论中其他几个重要问题的最佳性能。我们认为的第一个问题是有损源压缩。我们构建了极地代码，该代码渐近地接近了香农的速率延伸，以大量来源约束。我们通过根据“测试通道”设计极地代码来实现这一性能，该代码自然出现在香农的速率函数的表述中。编码操作结合了Arikan的连续取消算法和称为“随机舍入”的关键新成分。至于通道编码，可以使用O（n log n）复杂性实现编码以及解码操作。这是第一个接近最佳利率差异权衡的已知“实用”计划。我们还构建了极地代码，以实现Wyner-Ziv和Gelfand-Pinsker问题的最佳性能。这两个问题都可以使用“嵌套”代码解决，并且极地代码自然适合于此目的。我们进一步表明，极地代码达到了不对称通道，多末端场景（如多个访问通道）的容量以及降级的广播通道。对于这些问题，我们的构造是第一个已知的“实用”方案，可实现最佳性能。 Arikan的原始极性代码在块长度的平方根上实现了块误差概率衰减。对于源编码，所达到的失真与限制失真之间的缝隙在区块长的平方根中呈指数级消失。我们探索其他类似极地的代码结构，并具有更高的衰减速率。通过这种概括，我们表明可以为通道和源编码获得接近指数衰减。新的结构模仿了阿里坎的递归结构，因此，它们继承了相同的编码和解码复杂性。我们还提出了基于消息通话的算法，以提高极地代码的有限长度性能。在本文的最后两章中，我们解决了与通信相关的图形模型中的两个重要问题。第一个问题是在低密度平价检查代码（LDPC）的区域中。对于实用的长度，使用消息传播解码的LDPC代码仍然是要击败的代码。当前的分析使用密度演化，评估了树上这些算法的性能。树假设对应于使用无限长度代码。但是实际上，这些代码的长度有限。我们为此方案分析了通讯算法。不存在树假设会引入各种消息之间的相关性。我们表明，尽管存在这种相关性，但树木分析的预测是准确的。我们考虑的第二个问题与使用随机扩散的代码分区多访问（CDMA）通信有关。当前的分析主要集中于信息理论限制，即使用高斯输入分布。但是，在实践中，我们使用的调制方案等二进制相移键合（BPSK），远非高斯。调制方案的效果无法使用基于大型随机矩阵的传统工具来分析。我们遵循一种新方法，使用用于统计力学中随机旋转系统的工具。当用户输入为bpsk时，我们证明了系统容量的紧密上限。我们还表明，容量仅取决于扩散序列的力量，并且独立于其确切分布。
The two central topics of information theory are the compression and the transmission of data. Shannon, in his seminal work, formalized both these problems and determined their fundamental limits. Since then the main goal of coding theory has been to find practical schemes that approach these limits. Polar codes, recently invented by Arikan, are the first "practical" codes that are known to achieve the capacity for a large class of channels. Their 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 blocklength of the code. We show that polar codes are suitable not only for channel coding but also achieve optimal performance for several other important problems in information theory. The first problem we consider is lossy source compression. We construct polar codes that asymptotically approach Shannon's rate-distortion bound for a large class of sources. We achieve this performance by designing polar codes according to the "test channel", which naturally appears in Shannon's formulation of the rate-distortion function. The encoding operation combines the successive cancellation algorithm of Arikan with a crucial new ingredient called "randomized rounding". As for channel coding, both the encoding as well as the decoding operation can be implemented with O(N log N) complexity. This is the first known "practical" scheme that approaches the optimal rate-distortion trade-off. We also construct polar codes that achieve the optimal performance for the Wyner-Ziv and the Gelfand-Pinsker problems. Both these problems can be tackled using "nested" codes and polar codes are naturally suited for this purpose. We further show that polar codes achieve the capacity of asymmetric channels, multi-terminal scenarios like 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. The original polar codes of Arikan achieve a block error probability decaying exponentially in the square root of the block length. For source coding, the gap between the achieved distortion and the limiting distortion also vanishes exponentially in the square root of the blocklength. We explore other polar-like code constructions with better rates of decay. With this generalization, we show that close to exponential decays can be obtained for both channel and source coding. The new constructions mimic the recursive construction of Arikan and, hence, they inherit the same encoding and decoding complexity. We also propose algorithms based on message-passing to improve the finite length performance of polar codes. In the final two chapters of this thesis we address two important problems in graphical models related to communications. The first problem is in the area of low-density parity-check codes (LDPC). For practical lengths, LDPC codes using message-passing decoding are still the codes to beat. The current analysis, using density evolution, evaluates the performance of these algorithms on a tree. The tree assumption corresponds to using an infinite length code. But in practice, the codes are of finite length. We analyze the message-passing algorithms for this scenario. The absence of tree assumption introduces correlations between various messages. We show that despite this correlation, the prediction of the tree analysis is accurate. The second problem we consider is related to code division multiple access (CDMA) communication using random spreading. The current analysis mainly focuses on the information theoretic limits, i.e., using Gaussian input distribution. However in practice we use modulation schemes like binary phase-shift keying (BPSK), which is far from being Gaussian. The effects of the modulation scheme cannot be analyzed using traditional tools which are based on spectrum of large random matrices. We follow a new approach using tools developed for random spin systems in statistical mechanics. We prove a tight upper bound on the capacity of the system when the user input is BPSK. We also show that the capacity depends only on the power of the spreading sequences and is independent of their exact distribution.