Coupled graphical models and their thresholds
Coupled graphical models and their thresholds
复制标题
耦合图形模型及其阈值
DOI：
10.1109/cig.2010.5592881
复制
发表时间：
2010
期刊：
影响因子：
--
通讯作者：
R. Urbanke
中科院分区：
文献类型：
--
作者：
Seyed Hamed Hassani;N. Macris;R. Urbanke
卷积低密度奇偶校验码的优异性能是各个底层码跨越不断增长的大小但远远小于各个码的长度的窗口的空间耦合的结果。值得注意的是，耦合集成的信任传播阈值被提高到单个系统的最大后验概率阈值。除了编码理论之外，我们还研究了这种现象的普遍性：我们将一般的图形模型耦合到一个由大型独立系统组成的一维链中。对于后者，我们采用了居里-魏斯模型、随机场居里-魏斯模型、IF-可满足性模型和Q-染色模型。我们总是发现，基于解析和数值计算，耦合系统的消息传递阈值非常接近于单个模型的静态阈值。卷积低密度奇偶校验码的显著特性就是这种非常普遍的现象的一种表现。
The excellent performance of convolutional low-density parity-check codes is the result of the spatial coupling of individual underlying codes across a window of growing size, but much smaller than the length of the individual codes. Remarkably, the belief-propagation threshold of the coupled ensemble is boosted to the maximum-a-posteriori one of the individual system. We investigate the generality of this phenomenon beyond coding theory: we couple general graphical models into a one-dimensional chain of large individual systems. For the later we take the Curie-Weiss, random field Curie-Weiss, If-satisfiability, and Q-coloring models. We always find, based on analytical as well as numerical calculations, that the message passing thresholds of the coupled systems come very close to the static ones of the individual models. The remarkable properties of convolutional low-density parity-check codes are a manifestation of this very general phenomenon.