Hadamard符号

• Hadamard符号
  • 概要
  • 定義と基本的な性質
  • 復号
  • リスト復号

概要

Hadamard符号は計算量的誤り訂正符号の一つであり、計算量理論の文脈では符号のアルファベットサイズを下げるために用いられることが多い。

定義と基本的な性質

$\F_2^k$ 上の内積を $\inprod{a,b}=\sum_{i\in[k]}a_i b_i$ で定義し、関数 $f\colon\F_2^k\to\F_2$ は、ある $c\in\F_2^k$ に対して $f\colon x\mapsto \inprod{c,x}$ で表されるとき、線形関数であるという。

定義 (Hadamard符号)

パラメータ $k\in\Nat$ に対し、 $\F_2^k$ を $\F_2$ に写す線形関数全体の集合 $\calC$ を Hadamard符号 という。すなわち $\calC$ とは、ある $c\in\F_2^k$ を用いて、 $f\colon x \mapsto \inprod{c,x}$ と表せる関数 $f\colon \F_2^k\to\F_2$ の全体であり、関数 $f$ を長さ $2^k$ のベクトルとみなすことによって $\calC\subseteq \F_2^{2^k}$ として扱う。

線形関数全体は加算と乗算で閉じているため $\F_2^{2^k}$ の部分空間をなす。符号長は $2^k$ であり、 $\calC$ のランクは $k$ なので $\calC$ のレートは $k/2^k$ となる。符号長を $n=2^k$ を用いて表すとレートは $\log n/n$ となり小さい。

距離は $1/2$ である。これは、任意の二つの相異なる線形関数 $f(x)=\langle c_1,x\rangle,g(x)=\langle c_2,x\rangle$ がハミング距離の意味で離れていることを言えば示せる。相異なる二つの関数の（正規化された）ハミング距離は

\[\begin{align*} \dist(f,g)=\frac{1}{2^n}\sum_{x\in\F_2^n}\indicator_{f(x)\neq g(x)} = \Pr_{x\sim\F_2^n}[f(x)\neq g(x)] = \Pr_x[\langle c_1-c_2,x\rangle\neq 0] = \frac{1}{2} \end{align*}\]

を満たす。最後の等式では $c_1\neq c_2$ を利用した。

復号

距離 $1/4$ 以内のHadamard符号 $\calC$ の復号は簡単である。すなわち、関数 $f\in\F_2^{k} \to \F_2$ が与えられたとき、線形関数 $h\in \calC$ であって $\dist(f,h)<1/4$ を満たすものは高々一つ存在し、存在するならば簡単に見つけることができる。ここで、「関数が $f\colon\F_2^k\to\F_2$ が与えられた」といった場合は、 $f$ を長さ $2^k$ のベクトルとみなしてこれが与えられたということを意味する。

もし $\dist(f,h)<1/4$ を満たす $h$ が二つ以上存在する場合、そのうちの二つの間の距離は三角不等式より $1/2$ より真に小さいため、Hadamard符号の距離が $1/2$ であることに矛盾する。

さて、関数 $f$ が与えられた時に $\dist(f,h)<1/4$ を満たす線形関数 $h$ を見つけるアルゴリズムを述べる。アルゴリズムを記述する前に、そのアイデアを説明する。簡単のため、 $\dist(f,h)<1/4-\varepsilon$ を満たす $h$ が存在すると仮定する。一様ランダムな点 $x,y\sim\F_2^k$ を二つ選んだとき、

\[\begin{align*} \Pr_{x,y}[f(x)= h(x) \or f(y)= h(y)] &=1- \Pr_{x,y}[f(x)\ne h(x) \or f(y)\ne h(y)] \\ &\ge 1-\Pr_{x,y}[f(x)\ne h(x)]-\Pr_{x,y}[f(y)\ne h(y)] \\ &\ge 1/2+2\varepsilon \end{align*}\]

を満たします. なお, ここの不等式評価では二つのランダムな点$x,y$はそれぞれの分布が一様ランダムであればよく, 特に独立でなくても成り立ちます.

従って, 任意に固定した点$z\in \F_2^k$における$h(z)$の値を求めるには, 一様ランダムに点$y\sim\F_2^k$を選び, $x=z+y$とした上で$f(x)-f(y)$とすれば良いです. 点$y,x=z+y$それぞれの分布は($y$のランダムネスに関して)一様分布となるので, 上記の解析から確率$1/2+2\varepsilon$で$f(y)=h(y)$かつ$f(x)=h(x)$となり, これが成り立つとき,

\[\begin{align*} f(x)-f(y) &= f(y+z) - f(y) \\ &= h(y+z) - h(y) \\ &= h(z) \end{align*}\]

より$h(z)$が計算できます. 任意に固定した点$z$における$h(z)$の値が$1/2+2\varepsilon$の確率で得られるため, 何度も同じことを繰り返して多数決をとることによってこの確率を任意に高くすることができます. 特に, $O(k/\varepsilon^2)$回繰り返すことによって成功確率を$> 1- 2^{-k}$とすることができ, $2^k$個の点に関するunion boundを用いると全ての$z\in\F_2^k$に対して$h(z)$を求めることができます.

リスト復号

リスト復号では, パラメータ$\varepsilon>0$と関数$f\in\F_2^{2^k}$が与えられたとき, $\dist(f,h)<1/2-\varepsilon$を満たす線形関数$h$を全て列挙する問題を考えます. そのような関数$h$は$O(1/\varepsilon^2)$個しか存在しないことが知られています. Goldreich-Levinの定理により, この問題は符号長$n=2^k$に関して多項式時間で解けることが知られています.