Доказать, что коэффициенты Фурье булевых функций f,g,h, где $$f=g\cdot h $$, связаны соотношениями:
$$c_{a}^{f}=2^{-n}\cdot\sum\limits_{b \in V_{n} }c_{b}^{g}\cdot c_{ a\bigoplus b}^{h}, a\in V_{n}$$
Необходимая справка по спектру Фурье:
$$f(x_{1}..x_{n})=\frac{ 1 }{ 2^{n} }\sum\limits_{a \in V_{n} } c_{a}^{f}(-1)^{(a,x)} $$
$$c_{a}^{f}=\sum\limits_{x \in V_{n}} f(x)\cdot (-1)^{(a,x)}=\sum\limits_{x \in V_{n}, f(x)=1}(-1)^{(a,x)} $$
$$ (a,x)=a_{1}x_{1} \bigoplus a_{2}x_{2} \bigoplus… \bigoplus a_{n}x_{n} — линейная функция $$
$$\left| L(n) \right|=2^{n} для a_{1}..a_{n}$$
$$c_{0..0}^{f}=\left\| f \right\|$$
$$\sum\limits_{a \in V_{n} }c_{a}^{f}=2^{n} \cdot f(0..0)$$
P.S. Внутри знаков $$ заключены формулы
|
|
|
Похожие вопросы |