符号理論のソースを表示

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

符号化は、以下の4種類に分類できる<ref>{{cite book 
|author1=James Irvine |author2=David Harle
|url=https://books.google.com/books?id=ZigejECe4r0C |title=Data Communications and Networks
|date=2002
|page=18
|section=2.4.4 Types of Coding
|quote=There are four types of coding}}
</ref>。

# 情報源符号化 (''source coding'') : [[データ圧縮]]
# 通信路符号化 (''channel coding'') : [[誤り検出訂正]]
# [[暗号理論|暗号符号化]] (''cryptographic coding'')
# [[伝送路符号|伝送路符号化]] (''line coding'')

情報源符号化（データ圧縮）は、データをより効率的に送信するために、情報源からデータを圧縮しようとする。例えば、[[ZIP (ファイルフォーマット)|ZIPデータ圧縮]]では、データファイルを小さくしてインターネットトラフィックを削減する。データ圧縮と誤り訂正は、組み合わせて検討することができる。

通信路符号化（誤り検出訂正）は、[[通信路]]上に存在する雑音などの障害への耐性を強化するために、余分なデータビット（冗長ビット）を追加する。この技術はあまり目立たないが、例えば音楽[[コンパクトディスク|CD]]では[[リード・ソロモン符号]]を使って傷や埃による誤りを訂正している。この場合の通信路はCD自体である。[[携帯電話]]も高周波転送における[[ノイズ]]や減衰による誤りを検出訂正する技術を使っている。一般に[[デジタル信号]]による通信には、必ず何らかの[[誤り検出訂正]]技術が使われている。

==符号理論の歴史==
1948年、[[クロード・シャノン]]は論文「[[通信の数学的理論]]」を、[[Bell System Technical Journal]]の7月号と10月号の2つの記事で発表した。この論文は、送信者が送信したい[[情報]]を最適に符号化する方法の問題に焦点を当てている。この論文では、[[ノーバート・ウィーナー]]が開発した[[確率論]]を使用した。当時、確率論は通信理論にはほとんど適用されていなかった。シャノンは、メッセージの不確実性の尺度として[[情報エントロピー]]を開発し、[[情報理論]]の分野を本質的に創始した。

[[1949年]]に[[ゴレイ符号|二元ゴレイ符号]]が開発された。これは、24ビットワードごとに最大3つの誤りを訂正し、4つ目を検出することができる誤り訂正符号である。

[[1968年]]、[[リチャード・ハミング]]は、[[ベル研究所]]在籍中の成果である数値計算方法、自動符号化システム、誤り検出訂正符号で[[チューリング賞]]を受賞した。彼は、[[ハミング符号]]、[[ハミング窓]]、{{仮リンク|ハミング数|en|Regular number}}、[[ハミング距離]]という概念を発明した。また符号を構成するために、誤りを定義する距離概念として[[リー距離]]、[[ウラム距離]]などが考案されている。

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

===定義===
データは[[確率変数]] <math>X:\Omega\rightarrow\mathcal{X}</math> として見ることができる。ここで、 <math>x \in \mathcal{X}</math> は確率 <math>\mathbb{P}[X=x]</math> で現れるものとする。

データは[[アルファベット (計算機科学)|アルファベット]] <math>\Sigma</math> からなる文字列（単語）で表されるものとする。

符号は以下の関数である。

<math>C:\mathcal{X}\rightarrow\Sigma^*</math> （空文字列がアルファベットの一部でない場合は <math>\Sigma^+</math> ）

<math>C(x)</math> は <math>x</math> と関連する符号語である。

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

<math>l(C(x))</math>

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

<math>l(C) = \sum_{x\in\mathcal{X}}l(C(x))\mathbb{P}[X=x]</math>

符号語の連結は <math>C(x_1,...,x_k) = C(x_1)C(x_2)...C(x_k)</math> である。

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

<math>C(\epsilon) = \epsilon</math>

===特性===
# <math>C:\mathcal{X}\rightarrow\Sigma^*</math> は[[可変長符号#非特異符号|非特異]]である（[[単射]]の場合）
# <math>C:\mathcal{X}^*\rightarrow\Sigma^*</math> は[[可変長符号#一意復号可能な符号|一意復号可能]]である（単射の場合）
# <math>C:\mathcal{X}\rightarrow\Sigma^*</math> は[[可変長符号#接頭符号|瞬時復号可能]]である（<math>C(x_1)</math> が <math>C(x_2)</math> の接頭辞でない場合（逆もまた同様））

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

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

== 通信路符号化 ==
{{main|誤り検出訂正}}

通信路符号化の目的は、なるべく高速に転送でき、なるべく多くの[[符号語]]を含み、[[誤り検出訂正]]可能な符号を見出すことである。これらの目的は互いに相反するため、用途によって適切な符号体系は異なる。符号に求められる特性は、転送中に発生するエラーの確率に依存する。例えば、CD では埃や傷による誤りを訂正することを主に考慮している。従って符号は[[インターリーブ]]された形式となり、データはディスク面のあちこちに分散される。よい符号とは言えないが、単純な繰り返し符号を例として考える。例えば、何らかの（音声のような）データのブロックを3回送信するとする。受信側は3回受信したデータブロックをビット毎に比較し、多数決で正しいデータを決定する。これを少しひねって、ビットの送信順を変えてインターリーブさせる。データを4つの小さいブロックに分割し、1つめのブロックの1ビット目の次に2つめのブロックの1ビット目という順に送信するのである。これをディスク面全体に分散するよう3回繰り返す。このような単純な繰り返し符号ではあまり効率的ではないが、実際にはもっと効率的な符号を使って情報をインターリーブし、ディスク面の一部に傷があっても誤り訂正できるようにしている。

別の用途にはもっと適した符号が別に存在する。[[宇宙空間]]での通信は受信機の[[熱雑音]]の影響が大きく、これはCDの傷などとは異なり、連続的なノイズである。[[電話回線]]を使った[[モデム]]ではノイズがあるために転送速度が制限されるが、それと同様である。携帯電話は減衰が問題となる。高周波では受信機がほんの数センチ動いただけでも減衰により信号が捕らえられなくなる。このような減衰に対処する通信路符号化の技法も存在する。

'''代数的符号理論'''({{Lang|en|Algebraic coding theory}})とは、符号の特性を代数学的に表現し研究する分野である。

代数的符号理論は基本的に以下の2つの符号に分類される。
# 線型ブロック符号
# 畳み込み符号

主に符号の以下の特性を分析する。
* 符号語の長さ
* 正しい符号語の総数
* 2つの正しい符号語間の最小[[ハミング距離]]

=== 線型ブロック符号 ===
[[線型ブロック符号]]は[[線型性]]を有している。すなわち、任意の2つの符号語の総和も符号語であり、情報源のビット列のブロックにもそれが適用される（そのため線型ブロック符号と呼ぶ）。線型でないブロック符号も存在するが、それでよいかどうかを証明することは困難である。

線型ブロック符号は (''n'',''m'',''d<sub>min</sub>'') で表され、それぞれ以下のような意味を持つ。

# n は符号語の長さ（シンボル数）
# m は一度に符号化されるシンボル数
# ''d<sub>min</sub>'' は符号間の最小ハミング距離

線型ブロック符号に属する符号として以下のようなものがある。

# [[巡回符号]]（[[ハミング符号]]は巡回符号のサブセット）
# [[反復符号]]
# [[パリティビット|パリティ符号]]
# [[リード・ソロモン符号]] 
# [[BCH符号]]
# [[代数幾何符号]]
# [[リード・マラー符号]]
# Polar符号
# [[ハミング限界|完全符号]]

ブロック符号は、'''[[球充填|硬貨を敷き詰める問題]]'''と関係している。これは[[2次元]]で考えると分かりやすい。硬貨を何枚もテーブルの上に並べ、なるべく稠密に敷き詰める。すると、ちょうど蜂の巣のように正六角形状に敷き詰められる。しかし、ブロック符号はもっと高次元であり、容易に視覚化できない。宇宙空間での通信に使われた強力な[[ゴレイ符号]]では24次元を使っている。一般的な2進数の符号では次元は符号語の長さとなる。

符号理論では、''N''次元球モデルを使う。例えば、テーブル上の円に何枚の硬貨を敷き詰められるか、あるいは3次元では球体の中にどれだけビー玉を詰められるかという問題と同じである。別の考慮として、符号の選択がある。例えば、正六角形を四角形の枠に敷き詰めようとしても、角に隙間ができてしまう。次元を大きくすると、隙間となる空間の割合は小さくなる。しかし、ある次元で符号が隙間無く敷き詰められるようになり、それを完全符号と呼ぶ。そのような符号の例は非常にまれである（ハミング <math>[n,k,3]</math>、ゴレイ <math>[24,12,8],[23,12,7],[12,6,6]</math>）。

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

=== 畳み込み符号 ===
[[畳み込み符号]]は電話回線用[[モデム]]([[ITU-T]] V.32、V.17、V.34)や [[GSM]] 携帯電話、さらには衛星通信や軍事通信機器にも使われている。

ここでのアイデアは、入力となるメッセージ群のシンボル列の重み付き総和として各符号語のシンボルを作成するということである。これは[[線形時不変系]]において入力と[[インパルス応答]]が判っているときに出力を求める[[畳み込み]]に似ている。

従って、畳み込みエンコーダの出力は一般に、畳み込みエンコーダとレジスタの状態に対する入力ビットの畳み込みである。

基本的に畳み込み符号は同等なブロック符号以上のノイズ耐性を保証しないが、多くの場合、同程度のブロック符号よりも実装が大幅に単純化される。エンコーダは大抵の場合、状態メモリとフィードバック論理（通常 [[排他的論理和|XOR]]ゲート）を持つ単純な回路である。デコーダはファームウェアやソフトウェアで実装される。

畳み込み符号のデコードに最適なアルゴリズムとして[[ビタービ・アルゴリズム]]がある。その計算負荷を減らす単純化手法もあり、最も可能性の高い経路だけを探索する。これは最適ではないが、低ノイズの環境ではよい結果となることがわかっている。最近の[[マイクロプロセッサ]]では、この縮小された探索アルゴリズムで平均毎[[秒]]4,000符号語以上のデコードが可能である。

== 暗号符号化 ==
{{main|暗号理論}}
[[暗号]]および暗号符号化は、第三者（{{仮リンク|敵対者|en|Adversary (cryptography)}}）の存在下で[[セキュア通信|安全な通信]]を行うための技術である<ref name="rivest90">{{cite book|first=Ronald L.|last=Rivest|authorlink=Ron Rivest|editor=J. Van Leeuwen|title=Handbook of Theoretical Computer Science|chapter=Cryptology|volume=1|publisher=Elsevier|year=1990}}</ref>。より一般的には、敵対者をブロックする[[通信プロトコル]]の構築と分析に関するものである<ref name="modern-crypto">{{Cite book|first1=Mihir|last1=Bellare|first2=Phillip|last2=Rogaway|title=Introduction to Modern Cryptography|chapter=Introduction|page=10|date=21 September 2005}}</ref>。データの[[機密性]]と[[データ完全性|完全性]]、[[認証]]、[[否認不可|否認防止]]<ref name="hac">{{cite book |first=A. J. |last=Menezes |first2=P. C. |last2=van Oorschot |first3=S. A. |last3=Vanstone |url=https://web.archive.org/web/20050307081354/www.cacr.math.uwaterloo.ca/hac/ |title=Handbook of Applied Cryptography |publisher= |isbn=0-8493-8523-7}}</ref>などの[[情報セキュリティ]]のさまざまな側面が、現代の暗号の中心である。現代の暗号は、[[数学]]、[[コンピュータ科学]]、[[電気工学]]の分野の境界上に存在する。暗号化を応用したものには、ATMカード、[[パスワード|コンピュータパスワード]]、[[電子商取引]]などがある。

== 伝送路符号化 ==
{{main|伝送路符号}}

[[伝送路符号]]（デジタルベースバンド変調またはデジタルベースバンド送信方法とも呼ばれる）は、データ伝送路を介して[[デジタル信号]]を[[伝送]]する際に、デジタル信号をデータ伝送路の特性に適した[[電圧]]・[[電流]]または[[光子]]のパルス[[波形]]に変換するための[[符号]]である<ref>JIS X 0009:1997 情報処理用語（データ通信） 09.05.01</ref>。伝送路符号は、デジタルデータ転送によく使用される。

伝送路符号は、搬送されるデジタル信号を、物理チャネルおよび受信装置の特性に応じて最適に調整された振幅および時間離散信号によって表すことからなる。デジタルデータの1と0を表すために使用される電圧または電流の波形パターンを、伝送路符号という。伝送路符号の一般的なタイプは、{{仮リンク|単極符号|en|Unipolar encoding}}・{{仮リンク|両極符号|en|Bipolar encoding}}・[[マンチェスタ符号]]である。

== 符号理論の応用 ==
符号理論におけるもう1つの課題は、[[同期 (計算機科学)|同期]]を可能とする符号の設計である。例えば、位相変移({{Lang|en|phase shift}})を容易に検出・訂正できるよう符号を設計すれば、複数の信号を同じ通信路で同時に送ることができる。例えば、携帯電話で使われている[[符号分割多元接続]](CDMA)符号がある。その詳細は本項目の範囲外だが、大まかに言えば、各携帯電話に特別な符号語が割り当てられる。転送時、その符号語を使って音声を表すビット列をスクランブル（暗号化）する。受信機では、その逆を行って暗号解読する。このような符号語の特性により、同時に複数の携帯電話がそれぞれ個別の符号語を割り当てられ、通話可能となる。1つの受信機から見れば、他の通話の信号は低レベルなノイズとしか認識されない。

もう1つの一般的な符号のクラスとして、[[自動再送制御]](ARQ)符号がある。この場合、送信機は長いメッセージに[[パリティビット]]を付与する。受信機はメッセージとパリティビットが一致するかを調べ、一致しない場合に送信機にメッセージの再送を要求する。ごく単純なものを除いて、[[Wide Area Network]]で使用されるプロトコルには必ず ARQ が使われている。例えば、[[Synchronous Data Link Control|SDLC]] ([[IBM]])、[[Transmission Control Protocol|TCP]]、[[X.25]] などである。この分野では、拒絶された[[パケット]]と新たなパケットの一致問題という部分でも研究が進んでいる。つまり、新たに受信したパケットが再送されたものか、それとも別の新しいパケットなのかを識別する問題である。一般にパケットに[[シリアル番号|番号]]を振ることで対処するが、[[プロトコルスタック]]がある場合、再送を制御する階層が異なる場合がある。[[インターネット・プロトコル・スイート|TCP/IP]]は両方の技法を採用している好例である。コネクションのある場合、TCP/IPはARQ符号による再送を行う。しかし、コネクションがない場合、ARQ は使われず、アプリケーション層で（必要に応じて）再送を制御しなければならない。

== 関連項目 ==
{{Commons-inline}}
* [[情報理論]]
* [[符号化方式]]
* [[誤り検出訂正]]
* [[データ圧縮]]

== 脚注 ==
{{脚注ヘルプ}}
{{reflist|2}}

== 参考文献 ==
* [[エルウィン・バーレカンプ|Elwyn R. Berlekamp]] (2014), ''Algebraic Coding Theory'', World Scientific Publishing (revised edition), {{ISBN2|978-9-81463-589-9}}.
* {{仮リンク|デイヴィッド・J・C・マッカイ|en|David J. C. MacKay|label=MacKay, David J. C.}}. ''[http://www.inference.phy.cam.ac.uk/mackay/itila/book.html Information Theory, Inference, and Learning Algorithms]'' Cambridge: Cambridge University Press, 2003. {{ISBN2|0-521-64298-1}}
* {{仮リンク|ヴェラ・プレス|en|Vera Pless|label=Vera Pless}} (1982), ''Introduction to the Theory of Error-Correcting Codes'', John Wiley & Sons, Inc., {{ISBN2|0-471-08684-3}}.
* Randy Yates, ''[http://www.digitalsignallabs.com/tutorial.pdf A Coding Theory Tutorial]''.
* 今井秀樹：「符号理論」、電子通信情報学会、ISBN 978-4885520907（1990年3月）。
* 植松友彦：「現代シャノン理論：タイプによる情報理論」、培風館、ISBN 4-563-01522-9（1998年7月21日）.
* J.ユステセン, T.ホーホルト：「誤り訂正符号入門」、森北出版、ISBN 978-4627817111（2005年10月11日）。
* 植松友彦：「代数系と符号理論」、オーム社、ISBN 978-4-274-50274-3 (2010年4月10日).
* 坂庭好一、渋谷智治：「代数系と符号理論入門」、コロナ社、ISBN 978-4-339-02446-3 (2010年4月30日).
* 和田山正：「誤り訂正技術の基礎」、森北出版、ISBN978-4-627-81731-9 (2010年7月6日）．
* 西村芳一：「［改訂新版］データの符号化技術と誤り訂正の基盤」、CQ出版、ISBN 978-4-7898-4640-0 (2010年8月1日)．
* 先名健一：「例題で学ぶ符号理論入門」、森北出版、ISBN 978-4-627-81741-8（2011年7月）。
* 萩原学：「符号理論：デジタルコミュニケーションにおける数学」、日本評論社、ISBN 978-4-535-78664-6 (2012年8月10日）．
* 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日）。
{{Authority control}}

{{DEFAULTSORT:ふこうりろん}}
[[Category:符号理論|*ふこうりろん]]
[[Category:誤り検出訂正]]
[[Category:数学に関する記事]]