An improved list decoding algorithm for the second order Reed-Muller codes and its applications

被引：22

作者：

Fourquet, Rafael ^{[1
]}

Tavernier, Cedric ^{[2
]}

机构：

[1] Univ Paris 8 St Denis MAATICAH, Dept Math, F-93526 St Denis, France

[2] THALES Commun, Colombes, France

来源：

DESIGNS CODES AND CRYPTOGRAPHY | 2008年 / 49卷 / 1-3期

关键词：

list decoding; Reed-Muller codes; covering radius; Boolean functions; cryptography;

D O I：

10.1007/s10623-008-9184-8

中图分类号：

TP301 [理论、方法];

学科分类号：

081202 ;

摘要：

We propose an algorithm which is an improved version of the Kabatiansky-Tavernier list decoding algorithm for the second order Reed-Muller code RM(2, m), of length n = 2(m), and we analyse its theoretical and practical complexity. This improvement allows a better theoretical complexity. Moreover, we conjecture another complexity which corresponds to the results of our simulations. This algorithm has the strong property of being deterministic and this fact drives us to consider some applications, like determining some lower bounds concerning the covering radius of the RM(2, m) code.

引用

页码：323 / 340

页数：18

共 16 条

[1] CARLET C, 2006, DAGST SEM COMPL BOOL
[2] Improving the upper bounds on the covering radii of binary Reed-Muller codes
Carlet, Claude
Mesnager, Sihem
[J]. IEEE TRANSACTIONS ON INFORMATION THEORY, 2007, 53 (01) : 162 - 173
[3] Cohen G, 1997, COVERING CODES
[4] Recursive decoding and its performance for low-rate Reed-Muller codes
Dumer, I
[J]. IEEE TRANSACTIONS ON INFORMATION THEORY, 2004, 50 (05) : 811 - 823
[5] DUMER I, 2006, P ISIT 2006 SEATTL U
[6] ELIAS P, 1957, IRE WESCON CONV REC, V2, P94
[7] Goldreich O., 1989, Proceedings of the Twenty First Annual ACM Symposium on Theory of Computing, P25, DOI 10.1145/73007.73010
[8] Goldreich O, 1995, AN S FDN CO, P294, DOI 10.1109/SFCS.1995.492485
[9] Improved decoding of Reed-Solomon and algebraic-geometry codes
Guruswami, V
Sudan, M
[J]. IEEE TRANSACTIONS ON INFORMATION THEORY, 1999, 45 (06) : 1757 - 1767
[10] SOME RESULTS ON THE COVERING RADII OF REED-MULLER CODES
HOU, XD
[J]. IEEE TRANSACTIONS ON INFORMATION THEORY, 1993, 39 (02) : 366 - 378

← 1 2 →