Fast Decoding of Expander Codes
Fast Decoding of Expander Codes
复制标题
扩展码的快速解码
DOI：
10.1109/tit.2017.2726064
复制
发表时间：
2018
影响因子：
2.5
通讯作者：
Shuhong Gao
中科院分区：
文献类型：
--
作者：
Michael C. Dowling;Shuhong Gao
扩展器代码是在具有良好膨胀属性的稀疏图上定义的坦纳代码。 Sipser and Spielman（1996）表明，当顶点扩展至少为3/4时，存在一个线性时间解码算法，而纠正的错误数量是代码长度的恒定分数。后来，Feldman <italic> et al。</italic>（2007）给出了一种解码算法，允许扩展为2/3 + 1/（3c），其中<inline-formula> <tex-math note =' “> $ c $ </tex-math> </inline-formula>是基础两部分图的左度，以多项式解码为代价复杂性。最近，Viderman（2013）将扩展参数进一步提高到<inline-formula> <tex-Math notegy =“ latex”> $ 2/3-1/（6c）$ </tex-math> </inline-formula>，并且解码算法以线性时间运行。这些结果是针对内部代码的扩展器代码。通过使用更强的内部代码，Chilappagari等人。 （2010年）表明，每个顶点扩展大于1/2的线性解码算法。在本文中，显示出每个顶点扩展，都有一种用于扩展器代码的线性时间解码算法（使用最小距离的内部代码，取决于顶点的扩展），并且纠正的错误数量是恒定的分数代码长度。
Expander codes are Tanner codes defined on sparse graphs that have good expansion properties. Sipser and Spielman (1996) showed that there is a linear-time decoding algorithm for expander codes when the vertex expansion is at least 3/4 and the number of errors corrected is a constant fraction of the code length. Later, Feldman <italic>et al.</italic> (2007) gave a decoding algorithm that allows the expansion to be 2/3 + 1/(3c), where <inline-formula> <tex-math notation="LaTeX">$c$ </tex-math></inline-formula> is the left degree of the underlying bipartite graph, at the expense of polynomial-time decoding complexity. Recently, Viderman (2013) further improved the expansion parameter to <inline-formula> <tex-math notation="LaTeX">$2/3 - 1/(6c)$ </tex-math></inline-formula>, and the decoding algorithm runs in linear time. These results are for expander codes whose inner codes are parity-check codes. By using stronger inner codes, Chilappagari et al. (2010) showed that there is a linear-time decoding algorithm for every vertex expansion greater than 1/2. In this paper, it is shown that for every vertex expansion, there is a linear-time decoding algorithm for expander codes (using inner codes with minimum distance depending on the vertex expansion), and that the number of errors corrected is a constant fraction of the code length.