Counting in Graph Covers: A Combinatorial Characterization of the Bethe Entropy Function
Counting in Graph Covers: A Combinatorial Characterization of the Bethe Entropy Function
复制标题
图覆盖计数：Bethe 熵函数的组合表征
DOI：
10.1109/tit.2013.2264715
复制
发表时间：
2010
影响因子：
2.5
通讯作者：
P. Vontobel
中科院分区：
文献类型：
--
作者：
P. Vontobel
我们提出了一个组合表征的贝特熵函数的因子图，这样的表征是在相反的原始，分析，定义这个功能。我们实现了这一组合的特征，通过计数有效的配置，在有限的图形覆盖的因子图。类似地，我们给出了贝特配分函数，其原始定义也是一个分析性质的组合表征。正如我们所指出的，我们的方法与复制方法有相似之处，但也有明显的不同。上述发现是引入基于图的代码的解码器的自然背景，我们将称之为符号图覆盖解码，该解码器扩展了我们早期关于块图覆盖解码的工作。这两个图覆盖解码器的理论工具，有助于更好地理解的消息传递迭代解码，即块图覆盖解码链接最大积（最小和）算法解码与线性规划解码，和符号图覆盖解码链接和积算法解码与贝特自由能函数最小化在温度1。吉布斯熵函数是一个凹函数，而贝特熵函数一般不是处处凹的。特别是，我们表明，每一个代码从一个合奏的定期低密度奇偶校验码的最小汉明距离增长（高概率）与块长度线性具有Bethe熵函数，在其域的某些区域凸。
We present a combinatorial characterization of the Bethe entropy function of a factor graph, such a characterization being in contrast to the original, analytical, definition of this function. We achieve this combinatorial characterization by counting valid configurations in finite graph covers of the factor graph. Analogously, we give a combinatorial characterization of the Bethe partition function, whose original definition was also of an analytical nature. As we point out, our approach has similarities to the replica method, but also stark differences. The above findings are a natural backdrop for introducing a decoder for graph-based codes that we will call symbolwise graph-cover decoding, a decoder that extends our earlier work on blockwise graph-cover decoding. Both graph-cover decoders are theoretical tools that help toward a better understanding of message-passing iterative decoding, namely blockwise graph-cover decoding links max-product (min-sum) algorithm decoding with linear programming decoding, and symbolwise graph-cover decoding links sum-product algorithm decoding with Bethe free energy function minimization at temperature one. In contrast to the Gibbs entropy function, which is a concave function, the Bethe entropy function is in general not concave everywhere. In particular, we show that every code picked from an ensemble of regular low-density parity-check codes with minimum Hamming distance growing (with high probability) linearly with the block length has a Bethe entropy function that is convex in certain regions of its domain.