ترغب بنشر مسار تعليمي؟ اضغط هنا

The Bethe Free Energy Allows to Compute the Conditional Entropy of Graphical Code Instances. A Proof from the Polymer Expansion

48   0   0.0 ( 0 )
 نشر من قبل Marc Vuffray
 تاريخ النشر 2013
  مجال البحث الهندسة المعلوماتية
والبحث باللغة English




اسأل ChatGPT حول البحث

The main objective of this paper is to explore the precise relationship between the Bethe free energy (or entropy) and the Shannon conditional entropy of graphical error correcting codes. The main result shows that the Bethe free energy associated with a low-density parity-check code used over a binary symmetric channel in a large noise regime is, with high probability, asymptotically exact as the block length grows. To arrive at this result we develop new techniques for rather general graphical models based on the loop sum as a starting point and the polymer expansion from statistical mechanics. The true free energy is computed as a series expansion containing the Bethe free energy as its zero-th order term plus a series of corrections. It is easily seen that convergence criteria for such expansions are satisfied for general high-temperature models. We apply these general results to ensembles of low-density generator-matrix and parity-check codes. While the application to generator-matrix codes follows standard high temperature methods, the case of parity-check codes requires non-trivial new ideas because the hard constraints correspond to a zero-temperature regime. Nevertheless one can combine the polymer expansion with expander and counting arguments to show that the difference between the true and Bethe free energies vanishes with high probability in the large block

قيم البحث

اقرأ أيضاً

The paper establishes the equality condition in the I-MMSE proof of the entropy power inequality (EPI). This is done by establishing an exact expression for the deficit between the two sides of the EPI. Interestingly, a necessary condition for the eq uality is established by making a connection to the famous Cauchy functional equation.
The lattice $A_n^*$ is an important lattice because of its covering properties in low dimensions. Clarkson cite{Clarkson1999:Anstar} described an algorithm to compute the nearest lattice point in $A_n^*$ that requires $O(nlog{n})$ arithmetic operatio ns. In this paper, we describe a new algorithm. While the complexity is still $O(nlog{n})$, it is significantly simpler to describe and verify. In practice, we find that the new algorithm also runs faster.
In this paper we are concerned with the asymptotic analysis of nonbinary spatially-coupled low-density parity-check (SC-LDPC) ensembles defined over GL$left(2^{m}right)$ (the general linear group of degree $m$ over GF$left(2right)$). Our purpose is t o prove threshold saturation when the transmission takes place on the binary erasure channel (BEC). To this end, we establish the duality rule for entropy for nonbinary variable-node (VN) and check-node (CN) convolutional operators to accommodate the nonbinary density evolution (DE) analysis. Based on this, we construct the explicit forms of the potential functions for uncoupled and coupled DE recursions. In addition, we show that these functions exhibit similar monotonicity properties as those for binary LDPC and SC-LDPC ensembles over general binary memoryless symmetric (BMS) channels. This leads to the threshold saturation theorem and its converse for nonbinary SC-LDPC ensembles on the BEC, following the proof technique developed by S. Kumar et al.
143 - Tiben Che , Gwan Choi 2016
This paper proposes a polar code construction scheme that reduces constituent-code supplemented decoding latency. Constituent codes are the sub-codewords with specific patterns. They are used to accelerate the successive cancellation decoding process of polar code without any performance degradation. We modify the traditional construction approach to yield increased number of desirable constituent codes that speeds the decoding process. For (n,k) polar code, instead of directly setting the k best and (n-k) worst bits to the information bits and frozen bits, respectively, we swap the locations of some information and frozen bits carefully according to the qualities of their equivalent channels. We conducted the simulation of 1024 and 2048 bits length polar codes with multiple rates and analyzed the decoding latency for various length codes. The numerical results show that the proposed construction scheme generally is able to achieve at least around 20% latency deduction with an negligible loss in gain with carefully selected optimization threshold.
114 - Chih-Chun Wang 2005
Density evolution (DE) is one of the most powerful analytical tools for low-density parity-check (LDPC) codes on memoryless binary-input/symmetric-output channels. The case of non-symmetric channels is tackled either by the LDPC coset code ensemble ( a channel symmetrizing argument) or by the generalized DE for linear codes on non-symmetric channels. Existing simulations show that the bit error rate performances of these two different approaches are nearly identical. This paper explains this phenomenon by proving that as the minimum check node degree $d_c$ becomes sufficiently large, the performance discrepancy of the linear and the coset LDPC codes is theoretically indistinguishable. This typicality of linear codes among the LDPC coset code ensemble provides insight into the concentration theorem of LDPC coset codes.
التعليقات
جاري جلب التعليقات جاري جلب التعليقات
سجل دخول لتتمكن من متابعة معايير البحث التي قمت باختيارها
mircosoft-partner

هل ترغب بارسال اشعارات عن اخر التحديثات في شمرا-اكاديميا