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

On the list and bounded distance decodability of Reed-Solomon codes

SIAM JOURNAL ON COMPUTING 2007年第1期37卷 195-209页

作者： Cheng, Qi Wan, Daqing Univ Oklahoma Sch Comp Sci Norman OK 73019 USA Univ Calif Irvine Dept Math Irvine CA 92697 USA Chinese Acad Sci Inst Math Beijing 100080 Peoples R China

For an error-correcting code and a distance bound, the list decoding problem is to compute all the codewords within a given distance to a received message. The bounded distance decoding problem is to find one codeword if there is at least one codeword within the given distance, or to output the empty set if there is not. Obviously the bounded distance decoding problem is not as hard as the list decoding problem. For a Reed-Solomon code [n, k](q), a simple counting argument shows that for any integer 0 < g < n, there exists at least one Hamming ball of radius n-g, which contains at least ((n)(g))/q(g-k) many codewords. Let (g) over cap (n, k, q) be the smallest positive integer g such that (g(n))/q(g-k) <= 1. One knows that k - 1 <= (g) over bar (n, k, q) <= root n(k-1) <= n. For the distance bound up to n - root n(k - 1), it is known that both the list and bounded distance decoding can be solved e. ciently. For the distance bound between n- root n(k - 1) and n-(g) over bar (n, k, q), we do not know whether the Reed - Solomon code is list or bounded distance decodable;nor do we know whether there are polynomially many codewords in all balls of the radius. It is generally believed that the answer to both questions is no. In this paper, we prove the following: ( 1) List decoding cannot be done for radius n-(g) over cap (n, k, q) or larger, unless the discrete logarithm over F-q (g) double under bar (n,F- k,F- q)- k is easy. (2) Let h and g be positive integers satisfying q >= max(g(2), (h - 1)(2+is an element of)) and g = (4/is an element of + 2)(h+1) for a constant is an element of > 0. We show that the discrete logarithm problem over F-q(h) can be e. ciently reduced by a randomized algorithm to the bounded distance decoding problem of the Reed-Solomon code [q, g-h](q) with radius q - g. These results show that the decoding problems for the Reed-Solomon code are at least as hard as the discrete logarithm problem over certain finite fields. For the list decoding proble

关键词： list decoding algorithm bounded distance decoding algorithm Reed-Solomon codes discrete logarithm problem

来源：评论

学校读者我要写书评

暂无评论

On the list and bounded distance decodability of Reed-Solomon codes

On the list and bounded distance decodability of Reed-Solomo...

引用

45th Annual IEEE Symposium on Foundations of Computer Science

作者： Cheng, Qi Wan, Daqing Univ Oklahoma Sch Comp Sci Norman OK 73019 USA Univ Calif Irvine Dept Math Irvine CA 92697 USA Chinese Acad Sci Inst Math Beijing 100080 Peoples R China

关键词： list decoding algorithm bounded distance decoding algorithm Reed-Solomon codes discrete logarithm problem

来源：评论

学校读者我要写书评

暂无评论

Estimates of the bit error probabilities for linear block codes and symmetric binary-input memoryless channels

Estimates of the bit error probabilities for linear block co...

引用

IEEE Information Theory Workshop

作者： Balakirsky, VB Tech Univ Eindhoven EIDMA NL-5600 MB Eindhoven Netherlands

ISBN: (纸本)0780376293

A coset representation of the bit error probabilities for binary linear block codes and arbitrary symmetric memoryless channels is derived. Such a representation leads to simple upper bounds on the bit error probabilities for code components expressed via 2n code spectra, where n is the code length, and to a "bounded distance decoding" algorithm. The performance of the algorithm is illustrated for the (23,12) Golay code and a particular channel having non-binary output alphabet where it attains a sub-optimum performance.

关键词： linear codes block codes binary codes error statistics decoding Golay codes channel coding memoryless systems coset representation bit error probabilities binary linear block codes upper bounds bounded distance decoding algorithm Golay c Golay codes bit error probability Block codes memoryless systems linear block code binary code linear codes Upper bound Channel coding Memoryless channel decoding code length

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：