誤り訂正符号とは
概要
誤り訂正符号とは, 文字列に冗長性を持たせることによって, 通信路上で生じるノイズに対する頑健性を高める手法のことです. データ通信の多くの場面（QRコード, 地上波デジタル放送, データストレージなど）で利用されている実用上重要な技術であるのみならず, 計算量理論の文脈でも重要な定理の証明の道具として使われることが多いです. 近年では量子計算に付随する誤り訂正符号（量子誤り訂正符号）の研究も盛んです. 誤り訂正符号そのものは, 球の最密充填に直結するため, 数学的にも興味深い対象であり組合せ論でも盛んに研究されています.
このページでは符号の組合せ論的な性質についてはそれほど深掘りせず, 代わりに符号の計算量的な性質に焦点を当てます. 私は便宜上これを計算量的符号理論と呼び, 組合せ的符号理論と区別しています. ただ, 組合せ論的な限界の議論（情報論的下界）はそのまま計算量的な限界も示すため, 組合せ的な議論もまた非常に重要であることを留意しておきます. なお, このページでは線形符号と呼ばれる誤り訂正符号の特殊ケースのみを扱うので, 線形符号を指して単に符号と呼ぶことにします.
定義と基本的な概念
定義 (符号)
有限体$\F_q$と自然数$n$に対し, 部分空間$\calC\subseteq \F_q^n$を符号 (code)もしくは線形符号 (linear code)と呼びます. 符号$\calC$の元を符号語 (codeword)と呼び, 符号語の個数を符号長 (code length)と呼びます. また, $\abs{\F_q}=q$をアルファベットサイズといいます.
符号の基本的な概念として, 符号の距離があります. 空間$\F_q^n$に対し, $n$で正規化されたハミング距離を導入します. すなわち, $x,y\in\F_q^n$の間の距離$\dist(x,y)$は
\[\begin{align*} \dist(x,y) = \frac{1}{n}\sum_{i=1}^n \indicator_{x_i\ne y_i} \end{align*}\]で与えられます.
定義 (距離, レート)
符号$\calC\subseteq \F_q^n$の距離 (distance)は
\[\begin{align*} \delta = \min_{x\ne y\in \calC} \dist(x,y) \end{align*}\]で定義されます. 次元$d$の符号$\calC\subseteq\F_q^n$のレート (rate)は$r = d/n$で定義されます.
ここでは線形符号に限定していますが, 一般の符号に対しても同様に定義できます. この際, レートは$\log_q|\calC|/n$として定義されます.
距離は符号語間がどれだけ離れているかを表しているため, 直感的には距離が大きい符号は全体空間$\F_q^n$内に符号語が均等に分散しているような符号です. 一方でレートが大きいとき, 符号語の個数が大きいことを意味します. 従ってレートと距離の間にはトレードオフがあり, その最適なトレードオフを求めることが符号設計の重要な課題です. これらのトレードオフには様々な限界が知られています. なお, 今回は線形符号に限定しているため, 任意に二つの符号語$x,y\in\calC$を選んだときに$x-y\in\calC$となるため, 符号の距離は非ゼロ成分を持つ符号語のうち最小の正規化ハミング重みと等しくなります.
符号化関数
最後に符号化関数(encoding function)の概念を導入します. 数学的には符号とは単なる部分空間$\calC$として定義されますが, 実用では送信したいメッセージと呼ばれる文字列$m$があって, それに冗長性を加え何かしらの変形を行って得られる文字列$\Enc(m)$を符号語と呼びます. これを数学的に捉えると, 何らかの有限集合$\Omega$の元$m\in\Omega$を受けとって$\F_q^n$の元$x\in\F_q^n$に変換する写像$\Enc\colon \Omega\to \F_q^n$を符号化関数と呼び, 符号とは$\calC = \set{ \Enc(x)\colon x\in \Omega }$によって得られる集合として定義することもできます (もちろん, この文脈では符号は部分空間である必然性はありません). このとき, $\abs{\calC}=\abs{\Omega}$なので, 符号のレートは$\log_q\abs{\Omega}/n$として定義されます. ここで$\log_q\abs{\Omega}$は$\Omega$の元を$q$進数で表現するときに必要な桁数なので, レートとは符号化によって長さが何倍になるかを表す指標として理解することができます.
興味の対象
組合せ的には距離とレートのトレードオフを達成する符号を構成することが主な興味の対象ですが, 計算量的な観点では符号化や復号化などにかかる計算量もまた重要な研究対象となります.
ここでは組合せ的/計算量的な興味の対象をそれぞれ簡潔にまとめて紹介します.
組合せ的(情報理論的)な興味の対象
- 距離: 任意の相異なる符号語間の距離を出来るだけ大きくしたい. 距離$\delta$に対して$\delta/2$を復号半径と呼ぶこともある (つまり, 半径が復号半径に等しいボールを出来るだけ詰め込むにはどうすれば良いかを議論する).
- レート: 符号語の個数をできるだけ大きくしたい. 距離とレートにはSingleton限界と呼ばれるトレードオフが存在し, これを達成する符号をMDS符号(maximum distance separate code)と呼びます.
- リスト半径: 任意に半径$R$の(ハミング)ボールを選んだときにその中に含まれる符号語の個数が少ないとき, その符号をリスト復号可能であると言い, ボール内の符号語の(様々にボールの中心を動かしたときの)最大値をリストサイズといいます. リストサイズが小さい(基本的には符号語長$n$に依存しない定数で抑えられる)ような$R$のうち最大のものをリスト復号半径と呼びます. リスト復号半径の下界をその符号の距離とアルファベットサイズを用いて表したものをJohnson限界といいます.
- アルファベットサイズ: 一般にアルファベットサイズが$q$のとき, 二つのベクトル$x,y\sim\F_q^n$を一様ランダムに選んだときはその間の距離はおよそ$\dist(x,y)\approx 1-\frac{1}{q}$となります. 一般にアルファベットサイズが大きいほど符号語間の距離が小さくなるため, アルファベットサイズと上記三つのパラメータとのトレードオフも興味の対象となります.
計算量的な興味の対象
- 符号化の効率性: 符号化関数$\Enc$の計算量が小さいという性質は最も基本的な計算量的性質といえます.
- 復号の効率性: 特に符号語に少しのノイズを加えたときに元の符号語を効率的に復元できるという誤り訂正能力が実用上でも理論計算機科学の理論上でも肝要です. また, 文字列$x\in\F_q^n$と半径$R\in[0,1]$が与えられたとき, ボール$\ball(x,R)$に含まれる符号語を列挙せよというタスクをリスト復号(list decoding)といいます. 詳しくは復号化を参照してください.
- 局所復号可能性: ノイズの乗った符号語の一部だけを見ても元の符号語の特定の文字を効率的に復元できるという性質を局所復号可能性(local decoding)といいます. この性質は特に平均時計算量の文脈で広く応用されており, この性質を持ったままレートをどこまで小さく出来るかは理論計算機科学でのホットな問題の一つです(2020年以降も大きな進展が発見されている). 類似した性質として, ある文字列が符号語に近いかどうかをその文字列のうち数個の文字のみを見て確率的に判定するというタスクを局所検査(local test)といいます. この概念は計算量理論におけるPCP定理の文脈で研究されており, 近年では量子誤り訂正符号にも応用されています.
文献
計算量的誤り訂正符号に関する入門に適した有名な文献を載せておきます.
- Essential Coding Theory, V. Guruswami, A. Rudra, M. Sudan, link
出版はされていない本なのだが, 2023年に著者らがドラフトをwebページで公開している. 誤り訂正符号に関する比較的最近の成果も紹介している. どちらかというと広く浅い知識を得るのに適している.
- List Decoding of Error-Correcting Codes, V. Guruswami, 2005 link
- Algorithmic Results in List Decoding, V. Guruswami, 2006 link
リスト復号に関する詳細な解説がされているGuruswamiのD論(の修正版)と計算量的結果にフォーカスを絞ったサーベイ本. Guruswamiは効率的なリスト復号アルゴリズムの設計において世界的に特に有名な研究者である.
- Error-Correcting Codes in Complexity Theory, L. Trevisan, 2003 link, arXiv
計算量理論における誤り訂正符号の応用に関する解説. 主に符号の局所復号や局所検査と呼ばれる操作が行える符号に焦点を置き, その平均時計算量やPCP定理への応用について解説している.