Non-binary LDPC codes and EXIT like functions
Non-binary LDPC codes and EXIT like functions
复制标题
DOI：
10.5075/epfl-thesis-4111
复制
发表时间：
2008
期刊：
影响因子：
--
通讯作者：
Vishwambhar Rathi
中科院分区：
文献类型：
--
作者：
Vishwambhar Rathi
在本文的第一部分中，我们对通过次优信念传播（BP）解码器和最优最大后验（MAP）解码器解码的二进制擦除信道（BEC）上的非二进制低密度奇偶校验（NBLDPC）码的渐近性能分析感兴趣。以前，在文献中已经研究了关于有限域的NBLDPC码。不幸的是，对于这些码，BP解码器在密度演化方面的渐近分析是繁琐的，因为所涉及的密度“活”在高维空间中。为了解决这个问题，我们引入了关于一般线性群的系综。对于这些系综，密度演化方程可以写成紧致形式。我们计算了各种NBLDPC集成的不同字母大小的阈值。令人惊讶的是，阈值并不是字母大小的单调函数。我们还推测了在任意二进制无记忆对称信道上由有限域定义的NBLDPC系综的稳定性条件。然后，我们考虑了在MAP解码下NBLDPC码在BEC上传输时的性能。为了实现这一目标，我们将剥离解码器和停止集的概念推广到NBLDPC码。利用这些概念，我们给出了通过BP解码器解码NBLDPC码的解码失败的组合表征。利用解码失效准则和密度演化分析计算了NBLDPC码的渐近残差度分布。残差集成的速率给出了NBLDPC码的条件熵。为了计算剩余集成的率，我们将[1]准则推广到非二进制设置，当满足该准则时，保证集成中的几乎每个码都具有等于设计率的率。我们观察到，在NBLDPC码的设置下，通过扩展BP GEXIT （EBP GEXIT[2]）函数关联MAP和BP解码性能的[1]的Maxwell构造是成立的。码的权值和停止集分布分别与码在MAP和BP解码器下的性能有关。我们首先关注规则NBLDPC系统的重量分布。导出了规则NBLDPC系统的平均重量分布。在此基础上，导出了正则NBLDPC系综等效二元权分布的平均值。我们证明了随着字母表大小的增大，等效二进制权分布收敛于Gallager随机奇偶校验集合的权分布。二元LDPC系综的平均重量分布在文献中得到了广泛的研究。我们对这个量的概率分布知之甚少。特别是，还没有解决总平均值周围的权重分布集中的问题。我们计算了二元规则LDPC系综的权重分布的方差。利用这种方法和第二矩方法，我们得到了随机选择的代码的权值分布接近集合平均值的概率界。我们发现，代码总数中有很大一部分的权重分布接近平均值。我们将同样的技术应用于二元正则LDPC系综的停止集分布。我们再次表明，大部分编码的停止集分布接近于集合平均值。在本文的最后一部分，我们讨论了EBP GEXIT函数的存在性问题。EBP GEXIT函数在稀疏图码的渐近分析中起着重要的作用。对于使用二进制LDPC码在BEC上传输，EBP GEXIT函数的解析性质相对简单且易于理解。一般BMS信道的情况就困难得多，一般情况下甚至不知道曲线的存在。我们从非线性分析中引入了一些工具来证明类出口曲线在某些情况下的存在性。主要的工具是Krasnoselskii-Rabinowitz （KR）分岔定理。
In the first part of this thesis we are interested in the asymptotic performance analysis of Non-Binary Low-Density Parity-Check (NBLDPC) codes over the Binary Erasure Channel (BEC) decoded via the suboptimal Belief Propagation (BP) decoder as well as the optimal Maximum-A-Posteriori (MAP) decoder. Previously, NBLDPC codes defined with respect to a finite field have been studied in the literature. Unfortunately, for these codes the asymptotic analysis of the BP decoder in terms of density evolution is cumbersome since the involved densities "live" in a high dimensional space. To alleviate this problem, we introduce ensembles defined with respect to the general linear group. For these ensembles the density evolution equations can be written in a compact form. We compute thresholds for different alphabet sizes for various NBLDPC ensembles. Surprisingly, the threshold is not a monotonic function of the alphabet size. We also conjecture the stability condition for NBLDPC ensembles defined with respect to finite fields over any binary memoryless symmetric channel. We then consider the performance of NBLDPC codes under MAP decoding when transmission takes place over the BEC. Towards this goal, we generalize the concepts of the peeling decoder and stopping sets to NBLDPC codes. Using these concepts, we give a combinatorial characterization of decoding failures for NBLDPC codes decoded via the BP decoder. We use the decoding failure criterion and the density evolution analysis to compute the asymptotic residual degree distribution for NBLDPC codes. The rate of this residual ensemble gives the conditional entropy of the NBLDPC code. To compute the rate of the residual ensemble we generalize the criterion of [1] to the non-binary setting, which, when satisfied, guarantees that almost every code in the ensemble has a rate equal to the design rate. We observe that the Maxwell construction of [1], relating the performance of MAP and BP decoding via the Extended BP GEXIT (EBP GEXIT [2]) function, holds in the setting of NBLDPC codes. The weight and stopping set distribution of a code are related to its performance under the MAP and the BP decoder respectively. We first concentrate on the weight distribution of regular NBLDPC ensembles. We derive the average weight distribution of regular NBLDPC ensembles. Using this, we derive the average of equivalent binary weight distribution of regular NBLDPC ensembles. We show that as the alphabet size becomes larger the equivalent binary weight distribution converges to the weight distribution of Gallager's random parity check ensemble. The average weight distribution of binary LDPC ensembles has been extensively studied in the literature. Much less is known about the probability distribution of this quantity. In particular, the question of the concentration of the weight distribution around the ensemble average has not been addressed. We compute the variance of the weight distribution of binary regular LDPC ensembles. Using this and the second moment method we obtain bounds on the probability that a randomly chosen code has its weight distribution close to the ensemble average. We show that a large fraction of the total number of codes have their weight distribution close to the average. We apply the same technique for the stopping set distribution of binary regular LDPC ensembles. Again we show that a large fraction of total number of codes have their stopping set distribution close to the ensemble average. In the last part of this thesis we address the question of the existence of the EBP GEXIT function. The EBP GEXIT function plays a fundamental role in the asymptotic analysis of sparse graph codes. For transmission over the BEC using binary LDPC codes, the analytic properties of the EBP GEXIT function are relatively simple and well understood. The case of general BMS channel is much harder and even the existence of the curve is not known in general. We introduce some tools from non-linear analysis which can be useful to prove the existence of EXIT like curves in some cases. The main tool is the Krasnoselskii-Rabinowitz (KR) bifurcation theorem.