コーディング理論

符号理論は、符号の特性と、特定のアプリケーションに対するそれぞれの適合性を研究する学問です。符号は、データ圧縮、暗号化、誤り検出と訂正、データ伝送、データ保存に使用されます。符号は、情報理論、電気工学、 数学、言語学、コンピュータサイエンスなど、さまざまな科学分野で、効率的で信頼性の高いデータ伝送方法を設計する目的で研究されています。これには通常、冗長性の除去と、伝送されたデータの誤りの訂正または検出が含まれます。

コーディングには4つの種類があります: ^[1]

1. データ圧縮（またはソースコーディング）
2. 誤り制御（またはチャネル符号化）
3. 暗号コーディング
4. ラインコーディング

データ圧縮は、ソースからのデータから不要な冗長性を取り除き、データをより効率的に送信しようとします。たとえば、DEFLATEデータ圧縮は、インターネット トラフィックの削減などの目的でファイルを小さくします。データ圧縮とエラー訂正は、組み合わせて研究されることがあります。

エラー訂正は、ソースからのデータに有用な冗長性を追加し、伝送チャネルに存在する障害に対して伝送をより堅牢にします。一般ユーザーは、エラー訂正を使用している多くのアプリケーションに気付かないかもしれません。一般的な音楽コンパクト ディスク(CD) は、傷やほこりを訂正するためにリード ソロモン コードを使用します。このアプリケーションでは、伝送チャネルは CD 自体です。携帯電話も、高周波無線伝送のフェーディングとノイズを訂正するためにコーディング技術を使用します。データ モデム、電話伝送、およびNASA 深宇宙ネットワークはすべて、ターボ コードやLDPC コードなどのチャネル コーディング技術を使用してビットを送信します。

1948 年、クロード・シャノンは、ベルシステム技術ジャーナルの 7 月号と 10 月号に 2 部構成の記事「通信の数学的理論」を発表しました。この研究は、送信者が送信したい情報をどのように符号化するのが最善かという問題に焦点を当てています。この基礎研究で、シャノンは、当時通信理論への応用の初期段階にあった、ノーバート・ウィーナーが開発した確率論のツールを使用しました。シャノンは、メッセージの不確実性の尺度として情報エントロピーを開発し、情報理論という分野を本質的に発明しました。

バイナリゴレイ コードは1949 年に開発されました。これは、24 ビット ワードごとに最大 3 つのエラーを訂正し、4 つ目のエラーを検出できるエラー訂正コードです。

リチャード・ハミングは、ベル研究所での数値計算法、自動コーディングシステム、誤り検出および誤り訂正コードに関する研究で、1968 年にチューリング賞を受賞しました。彼は、ハミング コード、ハミング ウィンドウ、ハミング数、ハミング距離と呼ばれる概念を発明しました。

1972年、Nasir Ahmedは離散コサイン変換（DCT）を提案し、 1973年にT. NatarajanおよびKR Raoと共同で開発しました。 ^[2] DCTは最も広く使用されている非可逆圧縮アルゴリズムであり、 JPEG、MPEG、MP3などのマルチメディア形式の基礎となっています。

ソースコーディングの目的は、ソースデータを取得してそれを小さくすることです。

データは確率 で出現するランダム変数 として見ることができます。 ${\displaystyle X:\Omega \to {\mathcal {X}}}$${\displaystyle x\in {\mathcal {X}}}$${\displaystyle \mathbb {P} [X=x]}$

データはアルファベット 上の文字列（単語）によってエンコードされます。 ${\displaystyle \Sigma }$

コードは関数である

${\displaystyle C:{\mathcal {X}}\to \Sigma ^{*}}$(または空の文字列がアルファベットの一部ではない場合)。${\displaystyle \Sigma ^{+}}$

${\displaystyle C(x)}$に関連付けられたコードワードです。 ${\displaystyle x}$

コードワードの長さは次のように表される。

${\displaystyle l(C(x)).}$

予想されるコードの長さは

${\displaystyle l(C)=\sum _{x\in {\mathcal {X}}}l(C(x))\mathbb {P} [X=x].}$

コードワードの連結。 ${\displaystyle C(x_{1},\ldots ,x_{k})=C(x_{1})C(x_{2})\cdots C(x_{k})}$

空文字列のコードワードは空文字列そのものです。

${\displaystyle C(\epsilon )=\epsilon }$

1. ${\displaystyle C:{\mathcal {X}}\to \Sigma ^{*}}$単射であれば特異ではない。
2. ${\displaystyle C:{\mathcal {X}}^{*}\to \Sigma ^{*}}$単射であれば一意にデコード可能です。
3. ${\displaystyle C:{\mathcal {X}}\to \Sigma ^{*}}$が の接頭辞でない場合は瞬時に発生します(逆も同様)。${\displaystyle C(x_{1})}$${\displaystyle C(x_{2})}$

ソースのエントロピーは情報の尺度です。基本的に、ソース コードはソースに存在する冗長性を削減し、より多くの情報を運ぶより少ないビットでソースを表現しようとします。

特定の想定確率モデルに従ってメッセージの平均長を明示的に最小化しようとするデータ圧縮は、エントロピー符号化と呼ばれます。

ソース コーディング方式で使用されるさまざまな手法は、ソースのエントロピーの限界を達成しようとします。C ( x ) ≥ H ( x )、ここでH ( x ) はソースのエントロピー (ビットレート)、 C ( x ) は圧縮後のビットレートです。特に、ソース コーディング方式はソースのエントロピーよりも優れたものはありません。

ファクシミリ送信では、単純なランレングス コードが使用されます。ソース コーディングにより、送信側で不要なデータがすべて削除され、送信に必要な帯域幅が減少します。

チャネル コーディング理論の目的は、高速で送信でき、有効なコード ワードを多数含み、多くのエラーを修正または少なくとも検出できるコードを見つけることです。これらの領域のパフォーマンスは相互に排他的ではありませんが、トレードオフの関係にあります。したがって、さまざまなアプリケーションにはさまざまなコードが最適です。このコードに必要な特性は、主に送信中にエラーが発生する確率によって決まります。一般的な CD の場合、障害は主にほこりや傷です。

CDはクロスインターリーブリードソロモン符号を使用してデータをディスク上に分散させます。^[3]

あまり良いコードではありませんが、単純な繰り返しコードはわかりやすい例として役立ちます。データ ビットのブロック (サウンドを表す) を 3 回送信するとします。受信側では、3 回の繰り返しをビットごとに調べ、多数決をとります。このコードの特徴は、ビットを単に順番に送信するのではなく、インターリーブすることです。データ ビットのブロックは、まず 4 つの小さなブロックに分割されます。次に、ブロックを循環して、最初の 1 ビット、次に 2 番目の 1 ビットを送信します。これを 3 回実行して、データをディスクの表面に分散させます。単純な繰り返しコードでは、これは効果的ではないように見えるかもしれません。ただし、このインターリーブ手法を使用すると、傷やほこりの「バースト」エラーを修正するのに非常に効果的な、より強力なコードが知られています。

他のコードは、さまざまな用途に適しています。深宇宙通信は、受信機の熱雑音によって制限されますが、これはバースト性よりも連続性です。同様に、狭帯域モデムは、電話ネットワークに存在する雑音によって制限され、連続的な妨害としてより適切にモデル化されます。 ^{[引用が必要]}携帯電話は急速なフェージングの影響を受けます。使用される高周波は、受信機が数インチ移動しただけでも、信号の急速なフェージングを引き起こす可能性があります。ここでも、フェージングに対抗するように設計されたチャネル コードのクラスがあります。^{[引用が必要]}

代数的符号理論という用語は、符号の特性が代数的に表現され、さらに研究される符号理論のサブフィールドを指します。^{[引用が必要]}

代数的符号理論は基本的に2つの主要なタイプの符号に分けられます: ^{[引用が必要]}

• 線形ブロックコード
• 畳み込み符号

主に次の3つのコードのプロパティを分析します: ^{[引用が必要]}

• コードワードの長さ
• 有効なコードワードの総数
• 2つの有効なコードワード間の最小距離。主にハミング距離を使用するが、リー距離などの他の距離も使用することがある。

線形ブロック符号は線形性という性質を持っています。つまり、任意の2つの符号語の合計も符号語であり、ブロック内のソースビットに適用されるため、線形ブロック符号と呼ばれます。線形ではないブロック符号もありますが、この性質を持たない符号が優れたものであることを証明することは困難です。^[4]

_{線形ブロック符号は、記号アルファベット（例えば、2進数または3進数}）とパラメータ（n、m、dmin）によって要約される^[5]。ここで

1. nは符号語の長さ（シンボル単位）である。
2. mは一度にエンコードに使用されるソースシンボルの数です。
3. d _{min は}コードの最小ハミング距離です。

線形ブロックコードには多くの種類があり、例えば

1. 巡回符号（例：ハミング符号）
2. 繰り返しコード
3. パリティコード
4. 多項式コード（例：BCHコード）
5. リード・ソロモン符号
6. 代数幾何学コード
7. リード・ミュラー符号
8. 完璧なコード

ブロック コードは、長年にわたって注目されてきた球体パッキング問題と結びついています。2 次元では、簡単に視覚化できます。テーブルの上に平らに置いたペニー硬貨の束を一緒に押し付けます。結果は、蜂の巣のような六角形のパターンになります。ただし、ブロック コードは、簡単に視覚化できないより多くの次元に依存します。深宇宙通信で使用される強力な (24,12) Golay コードは、 24 次元を使用します。バイナリ コードとして使用される場合 (通常はバイナリ コードとして使用されます)、次元は、上記で定義したコードワードの長さを指します。

符号化の理論では、N次元球モデルが使用される。たとえば、テーブル上の円にペニーを何枚詰め込めるか、または 3 次元では、地球儀にビー玉を何個詰め込めるかなどである。コードの選択には他の考慮事項も含まれる。たとえば、長方形のボックスの制約に六角形を詰め込むと、角に空きスペースが残る。次元が大きくなるにつれて、空きスペースの割合は小さくなる。しかし、ある次元では、詰め込みがすべてのスペースを使用するため、これらのコードはいわゆる「完全な」コードとなる。唯一の非自明で有用な完全なコードは、(2 ^r – 1、2 ^r – 1 – r、3) を満たすパラメータを持つ距離 3 ハミング コードと、[23,12,7] バイナリ ゴレイ コード、[11,6,5] 3 進ゴレイ コードである。^{[4] [5]}

コードのもう 1 つの特性は、1 つのコードワードが持つ可能性のある近傍の数です。^[6] ここでも、ペニーを例に考えてみましょう。まず、ペニーを長方形のグリッドに詰めます。各ペニーには 4 つの近傍があります (さらに遠い角にも 4 つあります)。六角形の場合、各ペニーには 6 つの近傍があります。次元を増やすと、近傍の数は非常に急速に増加します。その結果、ノイズによって受信機が近傍を選択させる方法の数 (つまりエラー) も増えます。これは、ブロック コード、そして実際にはすべてのコードの基本的な制限です。1 つの近傍にエラーを引き起こすことは難しいかもしれませんが、近傍の数が多くなると、合計エラー確率が実際に低下します。^[6]

線形ブロック符号の特性は多くのアプリケーションで使用されています。たとえば、線形ブロック符号のシンドローム剰余類の一意性は、最もよく知られているシェーピング符号の1つであるトレリスシェーピング^[7]で使用されています。

畳み込み符号の背後にある考え方は、すべてのコードワード シンボルをさまざまな入力メッセージ シンボルの加重合計にすることです。これは、入力とインパルス応答がわかっている場合に、システムの出力を見つけるためにLTIシステム で使用される畳み込みに似ています。

したがって、一般的には、畳み込みエンコーダ レジスタの状態に対する入力ビットの畳み込みであるシステム畳み込みエンコーダの出力が見つかります。

基本的に、畳み込み符号は同等のブロック符号よりもノイズに対する保護力が高くありません。多くの場合、畳み込み符号は同等のパワーのブロック符号よりも実装が簡単です。エンコーダは通常、状態メモリとフィードバック ロジック (通常はXOR ゲート)を備えた単純な回路です。デコーダはソフトウェアまたはファームウェアで実装できます。

ビタビ アルゴリズムは、畳み込みコードのデコードに使用される最適なアルゴリズムです。計算負荷を軽減するために簡略化されています。最も可能性の高いパスのみを検索します。最適ではありませんが、低ノイズ環境では一般に良好な結果が得られることがわかっています。

畳み込み符号は、音声帯域モデム (V.32、V.17、V.34)、GSM 携帯電話、衛星通信デバイス、軍事通信デバイスで使用されます。

暗号化または暗号コーディングは、第三者（敵対者と呼ばれる）がいる状況で安全な通信を行うための技術の実践と研究です。 ^[8]より一般的には、敵対者をブロックするプロトコルの構築と分析です。 ^{[9]データの}機密性、データの整合性、認証、否認防止など、情報セキュリティのさまざまな側面^{[10]は、現代の暗号化の中心です。現代の暗号化は}、数学、コンピューターサイエンス、電気工学の分野の交差点に存在します。暗号化の用途には、 ATMカード、コンピューターのパスワード、電子商取引などがあります。

近代以前の暗号学は、事実上、暗号化、つまり、情報を判読可能な状態から意味不明な状態に変換することと同義でした。暗号化されたメッセージの発信者は、元の情報を復元するために必要な復号化技術を、意図した受信者とのみ共有し、それによって、望まない人が同じことをするのを防いでいました。第一次世界大戦とコンピューターの出現以来、暗号学を実行するために使用される方法はますます複雑になり、その応用はより広範になりました。

現代の暗号は、数学理論とコンピュータサイエンスの実践に大きく基づいています。暗号アルゴリズムは計算困難性の仮定に基づいて設計されているため、実際にはいかなる敵対者も解読することが困難です。理論的にはこのようなシステムを解読することは可能ですが、既知の実際的な手段では実行不可能です。したがって、これらの方式は計算上安全と呼ばれます。理論的進歩、たとえば、素因数分解アルゴリズムの改善やコンピューティング技術の高速化には、これらのソリューションを継続的に適応させることが必要です。無制限のコンピューティング能力をもってしても破られないことが証明できる情報理論的に安全な方式も存在しますが (ワンタイムパッドがその一例です)、これらの方式は、理論的には解読可能だが計算上安全な最良のメカニズムよりも実装が困難です。

ラインコード(デジタル ベースバンド変調またはデジタルベースバンド伝送方式とも呼ばれる) は、通信システム内でベースバンド伝送の目的で使用するコードです。ライン コーディングは、デジタル データ転送によく使用されます。

ライン コーディングは、物理チャネル (および受信装置) の特定の特性に合わせて最適に調整された振幅および時間の離散信号によって伝送されるデジタル信号を表すものです。伝送リンク上のデジタル データの 1 と 0 を表すために使用される電圧または電流の波形パターンは、ライン エンコーディングと呼ばれます。一般的なライン エンコーディングの種類は、単極、極性、双極、およびマンチェスター エンコーディングです。

符号理論のもう一つの関心事は、同期を助ける符号の設計です。位相シフトを簡単に検出して修正でき、複数の信号を同じチャネルで送信できるように符号を設計することができます。 ^[要出典]

一部の携帯電話システムで使用されているコードの別の用途は、コード分割多重アクセス(CDMA) です。各電話には、他の電話のコードとほぼ相関のないコード シーケンスが割り当てられます。^{[引用が必要]}送信時に、コード ワードを使用して音声メッセージを表すデータ ビットを変調します。受信機では、データを復元するために復調プロセスが実行されます。このクラスのコードの特性により、多くのユーザー (異なるコードを持つ) が同時に同じ無線チャネルを使用できます。受信機では、他のユーザーの信号は復調器に低レベルのノイズとしてのみ表示されます。^{[引用が必要]}

コードのもう 1 つの一般的なクラスは、自動再送要求(ARQ) コードです。これらのコードでは、送信側がエラー チェック用に各メッセージに冗長性を追加します。通常はチェック ビットを追加します。メッセージが到着したときにチェック ビットがメッセージの残りの部分と一致しない場合、受信側は送信側にメッセージの再送信を要求します。最も単純なものを除くすべての広域ネットワークプロトコルは ARQ を使用します。一般的なプロトコルには、 SDLC (IBM)、TCP (インターネット)、X.25 (国際) などが含まれます。拒否されたパケットを新しいパケットと照合する問題があるため、このトピックに関する広範な研究分野があります。新しいパケットですか、それとも再送信ですか。通常は、TCP のように番号付けスキームが使用されます。「RFC793」。RFCS。インターネット技術特別調査委員会(IETF)。1981 年 9 月。

グループテストでは、コードが別の方法で使用されます。特定の方法で異なるアイテムがごく少数存在する大規模なアイテムのグループを考えてみましょう (例: 欠陥のある製品や感染した被験者)。グループテストの考え方は、できるだけ少ないテストを使用して、どのアイテムが「異なる」かを判断することです。この問題の起源は、第二次世界大戦中に米国陸軍航空隊が兵士の梅毒検査を必要としたことに遡ります。^[11]

情報は、脳の神経ネットワーク、アナログ信号処理、アナログ電子機器でアナログ的に符号化されます。アナログ符号化には、アナログ誤り訂正^[12]、 アナログデータ圧縮^{[13] 、アナログ暗号化[14]}などがあります。

神経符号化は神経科学に関連した分野であり、感覚情報やその他の情報がニューロンのネットワークによって脳内でどのように表現されるかに関係しています。神経符号化を研究する主な目的は、刺激と個々のまたは集団のニューロン応答との関係、および集団内のニューロンの電気的活動間の関係を特徴付けることです。 ^{[15]ニューロンは}デジタル情報とアナログ情報の両方を符号化でき、^[16]ニューロンは情報理論の原理に従って情報を圧縮し、^[17] 脳やより広い神経系全体に送信される信号のエラーを 検出して修正する^{[18]と考えられています。}

• コーディングゲイン
• カバーコード
• エラー訂正コード
• 折り畳みリード・ソロモン符号
• グループテスト
• ハミング距離、ハミング重み
• リー距離
• 代数符号理論のトピックのリスト
• 複数アンテナ研究における 空間符号化とMIMO
  • 空間ダイバーシティ符号化は、データ伝送の信頼性を高めるために、情報信号のレプリカを異なる空間パスに沿って伝送する空間符号化です。
  • 空間干渉除去コーディング
  • 空間多重符号化
• 情報理論、データ圧縮、誤り訂正符号のタイムライン

• Elwyn R. Berlekamp (2014)、「Algebraic Coding Theory」、World Scientific Publishing (改訂版)、ISBN 978-9-81463-589-9。 
• MacKay, David JC 情報理論、推論、学習アルゴリズムケンブリッジ: ケンブリッジ大学出版局、2003年。ISBN 0-521-64298-1 
• Vera Pless (1982)、「誤り訂正符号理論入門」、John Wiley & Sons, Inc.、ISBN 0-471-08684-3。 
• Randy Yates、コーディング理論チュートリアル。