連接符号

概要

誤り訂正符号にはさまざまな指標があり、ある一つの指標については非常に良いパラメータを達成するものの 別の指標については悪いパラメータを持つ符号が構成される、というのは非常によくある話である。 例えばReed-Solomon符号は次数のパラメータを適切にとると距離やレートは非常に良い値を達成する一方、 必然的にアルファベットサイズが大きくなってしまうという欠点がある。 このように、ある意味で「尖った」符号に対して何かしらの操作を施して、他の指標についても良い値を達成するようにすることができれば、その符号は非常に有用であると言える。

符号の連接とは、アルファベットサイズの大きな符号 $\Cout$ とアルファベットサイズの小さな符号 $\Cin$ を組み合わせることによって、 $\Cout$ の誤り訂正能力をある程度保ちつつ アルファベットサイズを下げることができるという手法である。

定義 (連接符号)

二つの符号 $\Cout\subseteq\F_Q^N$、 $\Cin\subseteq\F_q^n$ であって、 $\abs{\Cin}=Q$ となるものを考える。 このとき、連接符号 $\Cout\circ \Cin\subseteq\F_q^{Nn}$ を以下の手続きで符号化される符号として定義する：

  1. メッセージを符号 $\Cout$ で符号化して得られる符号語を $y\in\F_Q^N$ とし、各成分を $y=(y_1,\dots,y_N)$ で表す。
  2. 各 $y_i$ を符号 $\Cin$ で符号化して得られる符号語を $x_i\in\F_q^n$ とする。ただしここでは $\Cin$ の符号化関数は $\Cin$ から $\F_q^n$ への単射であるとする。
  3. これらの $x_i$ を繋げて得られるベクトル $x=(x_1,\dots,x_N)\in\F_q^{Nn}$ を符号語として出力する。

text

説明の簡単のため、外側の符号 $\Cout$ の符号語 $y\in\F_Q^N$ の各成分 $y_i\in\F_Q$ をブロックと呼び、 内側の符号 $\Cin$ の符号語 $x_i\in\F_q^n$ の各成分をブロックの要素（または成分）と呼ぶ。

証明

まずはレートについて考える。 直感的には外側の符号 $\Cout$ は長さを $r_\tout$ 倍し、それぞれのブロック長は内側の符号 $\Cin$ によって長さが $r_\tin$ 倍されるため、全体では文字列長は $r_\tout r_\tin$ 倍されるためレートが $r_\tout r_\tin$ となる。以下ではこの議論をフォーマルに示している。 外側の符号 $\Cout$ のレートが $r_\tout$ なので、元のメッセージ長は $r_\tout N$ となるため、 ありうるメッセージの全体を $\Omega$ とすると、 $\abs{\Omega}=Q^{r_\tout N}$ である。 また、内側の符号 $\Cin$ の符号化関数は $\Cin$ から $\F_q^n$ への単射であるため、そのレートは $r_{\tin} = \frac{\log_q Q}{n}$ で表せる。 従って連接符号の符号化関数 $\Omega\to\F_q^{nN}$ のレートは

\[\begin{align*} \frac{\log_q \abs{\Omega}}{nN} &= \frac{\log_q Q^{r_\tout N}}{nN} = \frac{r_\tout N \log_q Q}{nN} = r_\tout r_{\tin} \end{align*}\]

となる。

次に連接符号 $\Cout\circ\Cin$ の距離を考えるために、非ゼロの符号語 $x\in\Cout\circ\Cin\setminus\set{0}$ の非ゼロ成分の個数を考える。 外側の符号 $\Cout$ の符号語は少なくとも $\delta_\tout N$ 個の非ゼロのブロックを持つ。 これらの非ゼロブロックのそれぞれを内側の符号 $\Cout$ で符号化すると、それぞれのブロックの非ゼロ成分の個数は少なくとも $\delta_\tin n$ 個となる。 従って、連接符号 $\Cout\circ\Cin$ の非ゼロ成分の個数は少なくとも $\delta_\tout N \delta_\tin n$ 個となるため、 連接符号 $\Cout\circ\Cin$ の距離は $\delta_\tout \delta_\tin$ となる。

基本的な性質

二つの符号$\Cout\subseteq\F_Q^N$, $\Cin\subseteq\F_q^n$に対して, それぞれのレートと距離が$r_\tout, r_\tin$と$\delta_\tout, \delta_\tin$であるとき, 連接符号$\Cout\circ\Cin$のレートと距離はそれぞれ$r_\tout r_\tin$と$\delta_\tout \delta_\tin$で与えられる.

連接符号の復号

簡単な観察として, 符号$\Cout,\Cin$それぞれが半径$R_{\tout},R_{\tin}$で復号できるならば, 連接符号$\Cout\circ\Cin$は半径$R_{\tout}R_{\tin}$で復号できます.

連接符号の応用

  • Guruswami and Sudan(2000)は$\Cout$としてReed-Solomon符号, $\Cin$としてHadamard符号を連接して得られる符号がリスト復号可能であることを証明した.1

  1. V. Guruswami and M. Sudan, “List decoding algorithms for certain concatenated codes,” STOC, 2000. ↩