誤り訂正符号とは
概要
誤り訂正符号とは、文字列に冗長性を持たせることによって、通信路上で生じるノイズに対する頑健性を高める手法のことである。 データ通信の多くの場面（QRコード、地上波デジタル放送、データストレージなど）で利用されている実用上重要な技術であるのみならず、計算量理論の文脈でも重要な定理の証明の道具として使われることが多い。
このページでは符号の組合せ論的な性質についてはそれほど深掘りせず、代わりに符号の計算量的な性質に焦点を当てる。 なお、このページでは線形符号と呼ばれる誤り訂正符号の特殊ケースのみを扱うので、線形符号を指して単に符号と呼ぶことにする。
定義と基本的な概念
定義 (符号)
有限体 $\F_q$ と自然数 $n$ に対し、部分空間 $\calC\subseteq \F_q^n$ を 符号 もしくは 線形符号 と呼ぶ。 符号 $\calC$ の元を 符号語 と呼び、符号語の個数を 符号長 と呼ぶ。また、 $\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$ の 距離 は
\[\begin{align*} \delta = \min_{x\ne y\in \calC} \dist(x,y) \end{align*}\]で定義される。 次元 $d$ の符号 $\calC\subseteq\F_q^n$ の レート は $r = d/n$ で定義される。
ここでは線形符号に限定しているが、一般の符号に対しても同様に定義できる。 この際、レートは $\log_q|\calC|/n$ として定義される。
距離は符号語間がどれだけ離れているかを表しているため、直感的には距離が大きい符号は全体空間 $\F_q^n$ 内に符号語が均等に分散しているような符号である。 一方でレートが大きいとき、符号語の個数が大きいことを意味する。 従ってレートと距離の間にはトレードオフがあり、その最適なトレードオフを求めることが符号設計の重要な課題である。 これらのトレードオフには様々な限界が知られている。 なお、今回は線形符号に限定しているため、任意に二つの符号語 $x,y\in\calC$ を選んだときに $x-y\in\calC$ となるため、符号の距離は 非ゼロ成分を持つ符号語のうち最小の正規化ハミング重み と等しくなる。
符号化関数
最後に 符号化関数 の概念を導入する。数学的には符号とは単なる部分空間 $\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）符号と呼ぶ。
- リスト半径: 任意に半径 $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)$ に含まれる符号語を列挙せよというタスクを リスト復号 という。詳しくは復号化を参照されたい。
- 局所復号可能性: ノイズの乗った符号語の一部だけを見ても元の符号語の特定の文字を効率的に復元できるという性質を 局所復号可能性 という。この性質は特に平均時計算量の文脈で広く応用されており、この性質を持ったままレートをどこまで小さく出来るかは理論計算機科学でのホットな問題の一つである(2020年以降も大きな進展が発見されている)。類似した性質として、ある文字列が符号語に近いかどうかをその文字列のうち数個の文字のみを見て確率的に判定するというタスクを 局所検査 という。この概念は計算量理論における 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定理への応用について解説している。