On the covering radii of binary Reed-Muller codes in the set of resilient Boolean functions

被引：15
作者：
Borissov, Y [1 ]
Braeken, A
Nikova, S
Preneel, B
机构：
[1] Bulgarian Acad Sci, Inst Math & Informat, BU-1113 Sofia, Bulgaria
[2] Katholieke Univ Leuven, ESAT, COSIC, Dept Elect Engn, B-3001 Heverlee, Belgium
来源：
IEEE TRANSACTIONS ON INFORMATION THEORY | 2005年 / 51卷 / 03期
关键词：
binary Reed-Muller codes; covering radius; resilient Boolean functions;
D O I：
10.1109/TIT.2004.842779
中图分类号：
TP [自动化技术、计算机技术];
学科分类号：
0812 ;
摘要：
Let R-t,R-n be the set of t-resilient Boolean functions in n variables, and let (p) over cap (t, r, n) be the maximum distance between t-resilient functions and the rth-order Reed-Muller code RM (r, n). We prove that,6(t, 2, 6) = 16 for t = 0, 1, 2 and)5(3, 2, 7) = 32, from which we derive the lower bound (p) over cap (t, 2, n) greater than or equal to 2(n-2) with t less than or equal to n - 4. Using a result from coding theory on the covering radius of (n - 3) th- and (n - 4)th-order Reed-Muller codes, we establish exact values of the covering radius of RM (n - 3, n) in the set of 1-resilient Boolean functions in n variables, when \n/2\ = 1 mod 2 and lower bounds of RM (n - 4, n) in the set of t-resilient Boolean functions in n variables. This result leads again to different lower bounds for general dimensions n and r = 0 or 3 mod 4.
引用
收藏
页码：1182 / 1189
页数：8
相关论文
共 28 条
[11]   GL(m,2) acting on R(r,m)/R(r-1,m) [J].
Hou, XD .
DISCRETE MATHEMATICS, 1996, 149 (1-3) :99-122
[12]  
HOU XD, 1993, IEEE INF THEORY, V39
[13]  
KUROSAWA K, 2001, LNCS, V2259, P75
[14]  
Mac Williams F., 1977, THEORY ERROR CORRECT
[15]   Further constructions of resilient Boolean functions with very high nonlinearity [J].
Maitra, S ;
Pasalic, E .
IEEE TRANSACTIONS ON INFORMATION THEORY, 2002, 48 (07) :1825-1834
[16]   COVERING RADIUS OF THE (M-3)RD ORDER REED MULLER CODES AND A LOWER BOUND ON THE (M-4)TH ORDER REED MULLER CODES [J].
MCLOUGHLIN, AM .
SIAM JOURNAL ON APPLIED MATHEMATICS, 1979, 37 (02) :419-422
[17]  
Meier W, 2004, LECT NOTES COMPUT SC, V3027, P474
[18]  
PRENEEL B, 1991, LECT NOTES COMPUT SC, V473, P161
[19]  
Sarkar P, 2000, LECT NOTES COMPUT SC, V1880, P515
[20]   THE 2ND ORDER REED-MULLER CODE OF LENGTH 64 HAS COVERING RADIUS-18 [J].
SCHATZ, JR .
IEEE TRANSACTIONS ON INFORMATION THEORY, 1981, 27 (04) :529-530
123