布尔函数的局部最优仿射逼近和分块仿射逼近及其应用

Loca Optima Affine Approximation and Block Affine Approxima-tion of Boolean Functions and their Applications

本文定义了布尔函数在ＤＧＦ￣ｎ（２）上的Ｗａｌｓｈ变换，考察了此类Ｗａｌｓｈ变换的性质，在此基础上提出了对布尔函数进行局部最优仿射逼近和分块仿射逼近的方法，并将有关结果应用于随机线性方程组的求解问题。

This paper defines the Walsh transformation over a nonempty subset D of GF￣n(2) of aBoolean function and gives some properties of such Walsh transformation. And the cyclicWalsh spectrum over D of a Boolean function is simultaneously considered.Based on it,nethods of local optimal affine approximation and block affine approximation to Booleanfunctions are proposed. A simple example in this paper serves to illustrate the effectivenessof the methods. The results indicate that mth-order correlation-immune Boolean func-tions can be attacked by kth order block affine approximation(k<m).As an applicationof the resuIts concerned, tlie problem of solving random linear equation system isdiscussed. An equivalent solution is then deduced. From Theorems 3-4 in the paper, weknow that the problem of finding the best solution of the random linear equation system isreduced to that of calculating local cyclic Walsh 8pectrum and searching for the optimal val-t1e. How to make good use ofthe probability p>0.5:and the information attached to D inpractical problem remains to be studied.