关于GF(2)上线性函数均为奇偶校验函数的证明问询
关于GF(2)上线性函数均为奇偶校验函数的证明问询
嗨,我最近在看一篇讨论单例函数属性测试算法的文章时,碰到了一个搞不懂的结论,想请教下各位大佬:
首先先明确几个定义:
- 单例函数:一个函数 $f:{0,1}^n \rightarrow{0,1}$ 是单例函数,当且仅当存在某个 $i\in[n]$,使得对任意 $x\in{0,1}^n$,要么 $f(x)=x_i$,要么 $f(x)=\bar x_i$(也就是$x_i$的取反)。
- 奇偶校验函数:文章里说,每个从 $(\mathbb Z_2)^n$ 到 $\mathbb Z_2$ 的线性函数都是奇偶校验函数——具体来说,就是存在一个子集 $S\subset[n]$,使得对任意 $x\in (\mathbb Z_2)^n$,$f(x)=\bigoplus_{i\in S} x_i$(这里的$\bigoplus$是GF(2)域中的加法,也就是我们常说的异或操作,它的结果为1当且仅当输入中1的个数是奇数)。
我目前的困惑是:为什么所有GF(2)上的n元线性函数都能表示成这种奇偶校验的形式?我隐约觉得这和$\mathbb Z_2$域里加减运算的定义(毕竟GF(2)里加法和减法是一回事),还有异或的性质有关,但就是没法梳理出一个严谨的证明过程。
有没有大佬能帮我一步步推导证明这个结论呀?万分感谢!
备注:内容来源于stack exchange,提问作者FAF
相关产品推荐
相关产品推荐

