检索结果-内蒙古大学图书馆

IEEE TRANSACTIONS ON INFORMATION THEORY 2018年第2期64卷 972-978页

作者： Dowling, Michael Gao, Shuhong Clemson Univ Dept Elect & Comp Engn Clemson SC 29634 USA Clemson Univ Dept Math Sci Clemson SC 29634 USA

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 et al. (2007) gave a decoding algorithm that allows the expansion to be 2/3 + 1/(3c), where c 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 2/3 - 1/(6c), 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.

关键词： Expander codes expander graphs asymptotically good codes decoding complexity linear-time decoding low-density parity check (LDPC) codes

来源：评论

学校读者我要写书评

暂无评论

Improved nearly-MDS expander codes

引用

IEEE TRANSACTIONS ON INFORMATION THEORY 2006年第8期52卷 3650-3661页

作者： Roth, Ron M. Skachek, Vitaly Technion Israel Inst Technol Dept Comp Sci IL-32000 Haifa Israel

A construction of expander codes is presented with the following three properties: i) the codes lie close to the Singleton bound, ii) they can be encoded in time complexity that is linear in their code length, and iii) they have a linear-time bounded-distance decoder. By using a version of the decoder that corrects also erasures, the codes can replace maximum-distance separable (MDS) outer codes in concatenated constructions, thus resulting in linear-time encodable and decodable codes that approach the Zyablov bound or the capacity of memoryless channels. The presented construction improves on an earlier result by Guruswami and Indyk in that any rate and relative minimum distance that lies below the Singleton bound is attainable for. a significantly smaller alphabet size.

关键词： concatenated codes expander codes graph codes iterative decoding linear-time decoding linear-time encoding maximum-distance separable (MDS) codes

来源：评论

学校读者我要写书评

暂无评论

decoding of expander codes at rates close to capacity

引用

IEEE TRANSACTIONS ON INFORMATION THEORY 2006年第12期52卷 5475-5485页

作者： Ashikhmin, Alexei Skachek, Vitaly Lucent Technol Bell Labs Math Commun Dept Murray Hill NJ 07974 USA Technion Israel Inst Technol Dept Comp Sci IL-32000 Haifa Israel

The decoding error probability of codes is studied as a function of their block length. It is shown that the existence of codes with a polynomially small decoding error probability implies the existence of codes with an exponentially small decoding error probability. Specifically, it is assumed that there exists a family of codes of length N and rate R = (1 - epsilon)C (C is a capacity of a binary-symmetric channel), whose decoding probability decreases inverse polynomially in N. It is shown that if the decoding probability decreases sufficiently fast, but still only inverse polynomially fast in N, then there exists another such family of codes whose decoding error probability decreases exponentially fast in N. Moreover, if the decoding time complexity of the assumed family of codes is polynomial in N and 1/epsilon, then the decoding time complexity of the presented family is linear in N and polynomial in 1/epsilon. These codes are compared to the recently presented codes of Barg and Zemor, "Error Exponents of Expander Codes," IEEE Transactions on Information Theory, 2002, and "Concatenated Codes: Serial and Parallel," 11 IEEE Transactions on Information Theory, 2005. It is shown that the latter families cannot be tuned to have exponentially decaying (in N) error probability, and at the same time to have decoding time complexity linear in N and polynomial in 1/epsilon.

关键词： concatenated codes decoding complexity decoding error probability error exponent expander codes irregular repeat accumulative (IRA) codes iterative decoding linear-time decoding low-density paritycheck (LDPC) codes

来源：评论

学校读者我要写书评

暂无评论

decoding of expander codes at rates close to capacity

Decoding of expander codes at rates close to capacity

引用

IEEE International Symposium on Information Theory and Its Applications

作者： Ashikhmin, Alexei Skachek, Vitaly Lucent Technol Bell Labs Math Commun Dept Murray Hill NJ 07974 USA Technion Israel Inst Technol Dept Comp Sci IL-32000 Haifa Israel

ISBN: (纸本)0780391519

来源：评论

学校读者我要写书评

暂无评论

Expanderové kódy

Expanderové kódy

引用

作者： Calábková, Markéta Charles University of Prague

Wherever information is transmitted we can find error-correcting codes. LDPC (low density parity check) codes are one of frequently used classes of codes and expander codes are promising members of this class. In this work, we explain what expander code are. We also show that expander codes simulta- neously have both asymptotically optimal parameters and linear-time encoding and decoding. Unfortunately, our constructions grant us codes, which are too big for regular use, for example for packet transmission. However, we believe that with better construction of expander graphs we will be able to construct short codes with significant practical applications. 1

关键词： expander error-correcting code linear-time decoding

来源：评论

学校读者我要写书评

暂无评论

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

建议与咨询 留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案： 新增检索档案 确定 取消

请选择收藏分类： 新增自定义分类 确定 取消

通借通还

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

请选择保存的检索档案：

请选择收藏分类：