符号理論

符号理論︵ふごうりろん、英: Coding theory︶は、情報を符号化して、通信を行う際の効率と信頼性についての情報学基礎論である。符号は、データ圧縮・暗号化・誤り訂正・ネットワーキングのために使用される。符号理論は、効率的で信頼できるデータ伝送方法を設計するために、情報理論・情報科学・数学・言語学・計算機科学・遺伝学などの様々な分野で研究されている。関係する純粋数学の分野としてグラフ理論等の離散数学、有限体理論を中心とした代数学、表現論が挙げられる。また、近年は量子もつれを加味した量子符号の原理について工学︵ここでは専ら復号アルゴリズムの記述を意味する︶および数学の観点から活発に研究されている。通常、符号理論には、情報源符号化定理を背景とする冗長性の除去の方法論と、冗長性を付与した上での送信されたデータの誤りの検出・訂正を研究対象とする、通信路符号化定理により存在を保証された性能の良い符号構成を目的とする誤り訂正符号理論が含まれる。BCH符号・Reed-Solomon符号やLDPC符号による符号化が産業活用の面では主流である一方で、有限射影幾何学および代数幾何学や計算量理論との関わりやDNAストレージ、不揮発性レーストラックメモリの数学解析への応用も認められている学際的な分野である。主要な符号はすでに発見され、かつ符号の重み多項式、重み分布も多くは把握されているが、チョムスキーの言語理論が認知機能の数理構造化を念頭に形式化されたがその後もプログラム言語論、本理論との関係が見出され、正規表現や自由言語認識アルゴリズムの応用が系列解析の研究に役立つ例など、分野横断的な発展が今なお続いている。ビット列全体は多重集合として表現されることがあり、このことからも素朴な有限集合に対する数学的操作の扱いが要求される。計算量の改善および評価は些細なものであっても山積すると目に見えて効率化が図られる為に重要な研究指標であり、O(k^2logklogn)の冗長性︵redundancy)をもつinsdel-codesがO(klogn)に高速化された例などが高く評価される傾向にある。また符号化率という指標も存在し、これは1に漸近するほど良いとされるが、︵計算量のオーダーに注意して︶1-Θ(εlog(1/ε))の符号化率を有するedit-eccが必ず存在することの数学証明を書き下す、あるいはそのような符号を実例してみせるといった研究方針も重要である。

ハミング距離を2次元で視覚化した図

符号化は、以下の4種類に分類できる^[1]。 (一)情報源符号化 (source coding) : データ圧縮 (二)通信路符号化 (channel coding) : 誤り検出訂正 (三)暗号符号化 (cryptographic coding) (四)伝送路符号化 (line coding) 情報源符号化︵データ圧縮︶は、データをより効率的に送信するために、情報源からデータを圧縮しようとする。例えば、ZIPデータ圧縮では、データファイルを小さくしてインターネットトラフィックを削減する。データ圧縮と誤り訂正は、組み合わせて検討することができる。通信路符号化︵誤り検出訂正︶は、通信路上に存在する雑音などの障害への耐性を強化するために、余分なデータビット︵冗長ビット︶を追加する。この技術はあまり目立たないが、例えば音楽CDではリード・ソロモン符号を使って傷や埃による誤りを訂正している。この場合の通信路はCD自体である。携帯電話も高周波転送におけるノイズや減衰による誤りを検出訂正する技術を使っている。一般にデジタル信号による通信には、必ず何らかの誤り検出訂正技術が使われている。

符号理論の歴史

1948年、クロード・シャノンは論文﹁通信の数学的理論﹂を、Bell System Technical Journalの7月号と10月号の2つの記事で発表した。この論文は、送信者が送信したい情報を最適に符号化する方法の問題に焦点を当てている。この論文では、ノーバート・ウィーナーが開発した確率論を使用した。当時、確率論は通信理論にはほとんど適用されていなかった。シャノンは、メッセージの不確実性の尺度として情報エントロピーを開発し、情報理論の分野を本質的に創始した。 1949年に二元ゴレイ符号が開発された。これは、24ビットワードごとに最大3つの誤りを訂正し、4つ目を検出することができる誤り訂正符号である。 1968年、リチャード・ハミングは、ベル研究所在籍中の成果である数値計算方法、自動符号化システム、誤り検出訂正符号でチューリング賞を受賞した。彼は、ハミング符号、ハミング窓、ハミング数︵英語版︶、ハミング距離という概念を発明した。また符号を構成するために、誤りを定義する距離概念としてリー距離、ウラム距離などが考案されている。

情報源符号化

詳細は「データ圧縮」を参照

情報源符号化の目的は、情報源におけるデータをより小さくすることである。

定義

データは確率変数

X:\Omega \rightarrow {\mathcal {X}}

として見ることができる。ここで、

x\in {\mathcal {X}}

は確率

\mathbb {P} [X=x]

で現れるものとする。データはアルファベット

\Sigma

からなる文字列︵単語︶で表されるものとする。符号は以下の関数である。

C:{\mathcal {X}}\rightarrow \Sigma ^{*}

︵空文字列がアルファベットの一部でない場合は

\Sigma ^{+}

︶

{\displaystyle C(

は

x

と関連する符号語である。符号語の長さは以下で書き表される。

{\displaystyle l(C(

期待される符号の長さは以下で書き表される。

{\displaystyle l(

符号語の連結は

C(x_{1},...,x_{k})=C(x_{1})C(x_{2})...C(x_{k})

である。空文字列の符号語は、空文字列そのものである。

C(\epsilon )=\epsilon

特性

$C:{\mathcal {X}}\rightarrow \Sigma ^{*}$ は非特異である（単射の場合）
$C:{\mathcal {X}}^{*}\rightarrow \Sigma ^{*}$ は一意復号可能である（単射の場合）
$C:{\mathcal {X}}\rightarrow \Sigma ^{*}$ は瞬時復号可能である（ $C(x_{1})$ が $C(x_{2})$ の接頭辞でない場合（逆もまた同様））

原理

情報源のエントロピーは情報量の尺度である。基本的に情報源符号化では情報源に存在する冗長性をなるべく排除しようとし、より少ないビット数でより多くの情報を格納しようとする。データ圧縮の手法として、特定の確率モデルに従ってメッセージのエントロピーを最小化する手法をエントロピー符号と呼ぶ。情報源符号化として情報源のエントロピーの限界を達成しようとする各種技法がある。ただし、理論上限界とされる以上の効率は達成できない。

例

ファクシミリ伝送では、単純な連長圧縮符号が使われている。情報源符号は、送信には必要でない余分なデータを削除し、送信に必要な帯域幅を減少させる。

通信路符号化

詳細は「誤り検出訂正」を参照

通信路符号化の目的は、なるべく高速に転送でき、なるべく多くの符号語を含み、誤り検出訂正可能な符号を見出すことである。これらの目的は互いに相反するため、用途によって適切な符号体系は異なる。符号に求められる特性は、転送中に発生するエラーの確率に依存する。例えば、CDでは埃や傷による誤りを訂正することを主に考慮している。従って符号はインターリーブされた形式となり、データはディスク面のあちこちに分散される。よい符号とは言えないが、単純な繰り返し符号を例として考える。例えば、何らかの︵音声のような︶データのブロックを3回送信するとする。受信側は3回受信したデータブロックをビット毎に比較し、多数決で正しいデータを決定する。これを少しひねって、ビットの送信順を変えてインターリーブさせる。データを4つの小さいブロックに分割し、1つめのブロックの1ビット目の次に2つめのブロックの1ビット目という順に送信するのである。これをディスク面全体に分散するよう3回繰り返す。このような単純な繰り返し符号ではあまり効率的ではないが、実際にはもっと効率的な符号を使って情報をインターリーブし、ディスク面の一部に傷があっても誤り訂正できるようにしている。別の用途にはもっと適した符号が別に存在する。宇宙空間での通信は受信機の熱雑音の影響が大きく、これはCDの傷などとは異なり、連続的なノイズである。電話回線を使ったモデムではノイズがあるために転送速度が制限されるが、それと同様である。携帯電話は減衰が問題となる。高周波では受信機がほんの数センチ動いただけでも減衰により信号が捕らえられなくなる。このような減衰に対処する通信路符号化の技法も存在する。 代数的符号理論(Algebraic coding theory)とは、符号の特性を代数学的に表現し研究する分野である。代数的符号理論は基本的に以下の2つの符号に分類される。 (一)線型ブロック符号 (二)畳み込み符号主に符号の以下の特性を分析する。

符号語の長さ
正しい符号語の総数
2つの正しい符号語間の最小ハミング距離

線型ブロック符号

線型ブロック符号は線型性を有している。すなわち、任意の2つの符号語の総和も符号語であり、情報源のビット列のブロックにもそれが適用される︵そのため線型ブロック符号と呼ぶ︶。線型でないブロック符号も存在するが、それでよいかどうかを証明することは困難である。線型ブロック符号は (n,m,d_min) で表され、それぞれ以下のような意味を持つ。 (一)nは符号語の長さ︵シンボル数︶ (二)mは一度に符号化されるシンボル数 (三)d_min は符号間の最小ハミング距離線型ブロック符号に属する符号として以下のようなものがある。 (一)巡回符号︵ハミング符号は巡回符号のサブセット︶ (二)反復符号 (三)パリティ符号 (四)リード・ソロモン符号 (五)BCH符号 (六)代数幾何符号 (七)リード・マラー符号 (八)Polar符号 (九)完全符号ブロック符号は、硬貨を敷き詰める問題と関係している。これは2次元で考えると分かりやすい。硬貨を何枚もテーブルの上に並べ、なるべく稠密に敷き詰める。すると、ちょうど蜂の巣のように正六角形状に敷き詰められる。しかし、ブロック符号はもっと高次元であり、容易に視覚化できない。宇宙空間での通信に使われた強力なゴレイ符号では24次元を使っている。一般的な2進数の符号では次元は符号語の長さとなる。符号理論では、N次元球モデルを使う。例えば、テーブル上の円に何枚の硬貨を敷き詰められるか、あるいは3次元では球体の中にどれだけビー玉を詰められるかという問題と同じである。別の考慮として、符号の選択がある。例えば、正六角形を四角形の枠に敷き詰めようとしても、角に隙間ができてしまう。次元を大きくすると、隙間となる空間の割合は小さくなる。しかし、ある次元で符号が隙間無く敷き詰められるようになり、それを完全符号と呼ぶ。そのような符号の例は非常にまれである︵ハミング

[n,k,3]

、ゴレイ

[24,12,8],[23,12,7],[12,6,6]

︶。もうひとつ、よく見逃される点として、1つの符号語が持つ近傍の数がある。再び硬貨を例にすると、最初に硬貨を方形の格子に詰める。この場合、各硬貨には4つの近傍がある。正六角形では、各硬貨は6つの近傍を持つ。次元を大きくすると、近傍の数は急速に増加する。結果として、ノイズによってある符号語を近傍の別の符号語と間違う可能性も大きくなる。これはブロック符号の基本的制限であり、実際すべての符号に言えることである。ある近傍に間違う可能性は低くても、近傍が増えれば全体としての誤り率は問題となる。

畳み込み符号

畳み込み符号は電話回線用モデム(ITU-T V.32、V.17、V.34)や GSM 携帯電話、さらには衛星通信や軍事通信機器にも使われている。ここでのアイデアは、入力となるメッセージ群のシンボル列の重み付き総和として各符号語のシンボルを作成するということである。これは線形時不変系において入力とインパルス応答が判っているときに出力を求める畳み込みに似ている。従って、畳み込みエンコーダの出力は一般に、畳み込みエンコーダとレジスタの状態に対する入力ビットの畳み込みである。基本的に畳み込み符号は同等なブロック符号以上のノイズ耐性を保証しないが、多くの場合、同程度のブロック符号よりも実装が大幅に単純化される。エンコーダは大抵の場合、状態メモリとフィードバック論理︵通常 XORゲート︶を持つ単純な回路である。デコーダはファームウェアやソフトウェアで実装される。畳み込み符号のデコードに最適なアルゴリズムとしてビタービ・アルゴリズムがある。その計算負荷を減らす単純化手法もあり、最も可能性の高い経路だけを探索する。これは最適ではないが、低ノイズの環境ではよい結果となることがわかっている。最近のマイクロプロセッサでは、この縮小された探索アルゴリズムで平均毎秒4,000符号語以上のデコードが可能である。

暗号符号化

詳細は「暗号理論」を参照

暗号および暗号符号化は、第三者︵敵対者︵英語版︶︶の存在下で安全な通信を行うための技術である^[2]。より一般的には、敵対者をブロックする通信プロトコルの構築と分析に関するものである^[3]。データの機密性と完全性、認証、否認防止^[4]などの情報セキュリティのさまざまな側面が、現代の暗号の中心である。現代の暗号は、数学、コンピュータ科学、電気工学の分野の境界上に存在する。暗号化を応用したものには、ATMカード、コンピュータパスワード、電子商取引などがある。

伝送路符号化

詳細は「伝送路符号」を参照

伝送路符号︵デジタルベースバンド変調またはデジタルベースバンド送信方法とも呼ばれる︶は、データ伝送路を介してデジタル信号を伝送する際に、デジタル信号をデータ伝送路の特性に適した電圧・電流または光子のパルス波形に変換するための符号である^[5]。伝送路符号は、デジタルデータ転送によく使用される。伝送路符号は、搬送されるデジタル信号を、物理チャネルおよび受信装置の特性に応じて最適に調整された振幅および時間離散信号によって表すことからなる。デジタルデータの1と0を表すために使用される電圧または電流の波形パターンを、伝送路符号という。伝送路符号の一般的なタイプは、単極符号︵英語版︶・両極符号︵英語版︶・マンチェスタ符号である。

符号理論の応用

符号理論におけるもう1つの課題は、同期を可能とする符号の設計である。例えば、位相変移(phase shift)を容易に検出・訂正できるよう符号を設計すれば、複数の信号を同じ通信路で同時に送ることができる。例えば、携帯電話で使われている符号分割多元接続(CDMA)符号がある。その詳細は本項目の範囲外だが、大まかに言えば、各携帯電話に特別な符号語が割り当てられる。転送時、その符号語を使って音声を表すビット列をスクランブル︵暗号化︶する。受信機では、その逆を行って暗号解読する。このような符号語の特性により、同時に複数の携帯電話がそれぞれ個別の符号語を割り当てられ、通話可能となる。1つの受信機から見れば、他の通話の信号は低レベルなノイズとしか認識されない。もう1つの一般的な符号のクラスとして、自動再送制御(ARQ)符号がある。この場合、送信機は長いメッセージにパリティビットを付与する。受信機はメッセージとパリティビットが一致するかを調べ、一致しない場合に送信機にメッセージの再送を要求する。ごく単純なものを除いて、Wide Area Networkで使用されるプロトコルには必ず ARQ が使われている。例えば、SDLC (IBM)、TCP、X.25 などである。この分野では、拒絶されたパケットと新たなパケットの一致問題という部分でも研究が進んでいる。つまり、新たに受信したパケットが再送されたものか、それとも別の新しいパケットなのかを識別する問題である。一般にパケットに番号を振ることで対処するが、プロトコルスタックがある場合、再送を制御する階層が異なる場合がある。TCP/IPは両方の技法を採用している好例である。コネクションのある場合、TCP/IPはARQ符号による再送を行う。しかし、コネクションがない場合、ARQ は使われず、アプリケーション層で︵必要に応じて︶再送を制御しなければならない。

脚注

[脚注の使い方]

^ James Irvine; David Harle (2002). “2.4.4 Types of Coding”. Data Communications and Networks. p. 18. "There are four types of coding"
^ Rivest, Ronald L. (1990). “Cryptology”. In J. Van Leeuwen. Handbook of Theoretical Computer Science. 1. Elsevier
^ Bellare, Mihir; Rogaway, Phillip (21 September 2005). “Introduction”. Introduction to Modern Cryptography. p. 10
^ Menezes, A. J.; van Oorschot, P. C.; Vanstone, S. A.. Handbook of Applied Cryptography. ISBN 0-8493-8523-7
^ JIS X 0009:1997 情報処理用語（データ通信） 09.05.01

参考文献

Elwyn R. Berlekamp (2014), Algebraic Coding Theory, World Scientific Publishing (revised edition), ISBN 978-9-81463-589-9.
MacKay, David J. C.（英語版）. Information Theory, Inference, and Learning Algorithms Cambridge: Cambridge University Press, 2003. ISBN 0-521-64298-1
Vera Pless（英語版） (1982), Introduction to the Theory of Error-Correcting Codes, John Wiley & Sons, Inc., ISBN 0-471-08684-3.
Randy Yates, A Coding Theory Tutorial.
今井秀樹：「符号理論」、電子通信情報学会、ISBN 978-4885520907（1990年3月）。
J.ユステセン, T.ホーホルト：「誤り訂正符号入門」、森北出版、ISBN 978-4627817111（2005年9月30日）。
先名健一：「例題で学ぶ符号理論入門」、森北出版、ISBN 978-4-627-81741-8（2011年7月）。
Henning Stichtenoth、新妻弘（訳）：「代数関数体と符号理論」、共立出版、ISBN 978-4-320-11045-8（2013年8月25日）。
楫勇一(編著）：「情報・符号理論」、オーム社、ISBN 978-4-274-21317-5（2013年10月）。
萩原学(編著)：「進化する符号理論」、日本評論社、ISBN 978-4535787971（2016年9月9日）。

[1] James Irvine; David Harle (2002). “2.4.4 Types of Coding”. Data Communications and Networks. p. 18. "There are four types of coding"

[rivest90-2] Rivest, Ronald L. (1990). “Cryptology”. In J. Van Leeuwen. Handbook of Theoretical Computer Science. 1. Elsevier

[modern-crypto-3] Bellare, Mihir; Rogaway, Phillip (21 September 2005). “Introduction”. Introduction to Modern Cryptography. p. 10

[hac-4] Menezes, A. J.; van Oorschot, P. C.; Vanstone, S. A.. Handbook of Applied Cryptography. ISBN 0-8493-8523-7

[5] JIS X 0009:1997 情報処理用語（データ通信） 09.05.01

[1]

[2]

[3]

[4]

[5]