A {00,01,10,11}-valued function on the vertices of the n-cube is called a t-resilient (n,2)-function if it has the same number of 00s, 01s, 10s and 11s among the vertices of every subcube of dimension t. The Friedman ...
详细信息
ISBN:
(纸本)9781538692912
A {00,01,10,11}-valued function on the vertices of the n-cube is called a t-resilient (n,2)-function if it has the same number of 00s, 01s, 10s and 11s among the vertices of every subcube of dimension t. The Friedman and Fon-Der-Flaass bounds on the correlation immunity order say that such a function must satisfy t <= 2n/3 - 1;moreover, the (2n/3 - 1)-resilient (n,2)-functions correspond to the equitable partitions of the n-cube with the quotient matrix [[0, r, r, r], [r, 0, r, r], [r, r, 0, r], [r, r, r, 0]], r = n/3. We suggest constructions of such functions and corresponding partitions, show connections with Latin hypercubes and binary 1-perfect codes, characterize the non-full-rank and the reducible functions from the considered class, and discuss the possibility to make a complete characterization of the class.
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-resilientfunctions and the rth-order Reed-Muller code RM (r, n). We prove that,...
详细信息
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-resilientfunctions 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.
暂无评论