Coding theory

thumb |コーディング理論の重要な尺度である[Hamming distance]の2次元視覚化]

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

コーディングには次の4つのタイプがあります。

＃データ圧縮（または、 'ソースコーディング'）＃誤り訂正（または「チャネル符号化」）＃暗号化コーディング＃ラインコーディング

データ圧縮は、データをより効率的に送信するために、ソースからデータを圧縮しようとします。たとえば、 Zipデータ圧縮は、インターネットトラフィックを減らすためにデータファイルを小さくします。データ圧縮と誤り訂正は、組み合わせて検討されるかもしれません。

誤り訂正は、伝送チャネル上に存在する外乱に対してデータの伝送をより頑強にするために余分なデータビットを追加する。通常のユーザは、エラー訂正を使用して多くのアプリケーションを認識していない可能性があります。典型的な音楽CDは、Reed-Solomon codeを使って傷や埃を修正します。このアプリケーションでは、伝送チャネルはCD自体です。携帯電話はまた、高周波無線送信のフェージングおよびノイズを補正するために符号化技術を使用する。データモデム、電話伝送、[NASA]はすべて、turbo codeやLDPC codeなどのビットを取得するためにチャネルコーディング技術を採用しています。

1 コーディング理論の歴史
2 ソースコーディング
3 チャネルコーディング
- 3.1 線形コード
  - 3.1.1 線形ブロックコード
  - 3.1.2 畳み込み符号
4 暗号コーディング
5 ラインコーディング
6 コーディング理論の他の応用
- 6.1 グループテスト
- 6.2 アナログコーディング
7 ニューラルコーディング
8 関連項目
9 Notes
10 ソース

コーディング理論の歴史[編集]

1948年に、Claude Shannonは、ベルシステムテクニカルジャーナルの7月号と10月号の2つの記事「[数学的通信理論]」を発表しました。この作業は、送信者が送信したい情報をどのようにエンコードするのが最適かという問題に焦点を当てています。この基本的な作業では、当時の通信理論に応用されている初期の段階であったNorbert Wienerによって開発された確率論のツールを使用しました。 Shannonは[[情報理論]の分野を本質的に発明しながら、メッセージ内の不確実性の尺度として[情報エントロピー]を開発しました。

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

Richard Hammingは、1968年に[ベル研究所]での数値計算、自動コーディングシステム、エラー検出とエラー訂正のコードで[チューリング賞]を受賞しました。彼は、Hamming code、Hamming window、Hamming numbers、Hamming distanceとして知られる概念を発明しました。

ソースコーディング[編集]

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

定義[編集]

データは、[ランダム変数]と見なすことができる。ここで、<math> x \ in \ mathcal {X}＆lt; / math＆gt; ;確率mathbb {P} [X = x] / mathで現れる。

データは、アルファベット <math> \ Sigma </ math>上の文字列（単語）によってコード化される。

コードは関数です

<math> C：\ mathcal {X} \ rightarrow \ Sigma ^ *＆lt; / math＆gt; （空の文字列がアルファベットの一部でない場合には、\＆\ sigma ^ +＆lt; / math＆gt;

<数学> C（x）</ math>は、<math> x </ math>に関連付けられたコードワードである。

コードワードの長さは

（C（x））/ mathである。

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

【数1】【数2】【数3】【数4】【数5】【数6】【数7】【数8】は、

符号語C（x_1、...、x_k）= C（x_1）C（x_2）... C（x_k）</ math>の連結。

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

（ε）=ε（ε）/ math

プロパティ[編集]

＃mathcal {X} \ rightarrow \ Sigma ^ *＆lt; / math＆gt; injectiveの場合、非単項式です。【数1】【数2】【数3】【数4】【数5】【数6】は、一意に解読可能です。＃mathcal {X} \ rightarrow \ Sigma ^ *＆lt; / math＆gt; <math> C（x_1）</ math>の場合、瞬間である。は、<math> C（x_2）</ math>の接頭辞ではない。（およびその逆）。

原則[編集]

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

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

ソース符号化方式によって使用される様々な技術は、ソースのエントロピーの限界を達成しようとする。 'はソースのエントロピー（ビットレート）であり、' ' C （ x ）は圧縮後のビットレートです。特に、ソース符号化方式は、ソースのエントロピーよりも優れていない可能性がある。

例[編集]

ファクシミリ送信は簡単なランレングス符号を使用します。送信元コーディングは、トランスミッタの必要性に余計なすべてのデータを削除し、伝送に必要な帯域幅を減少させる。

チャネルコーディング[編集]

チャネル符号化理論の目的は、迅速に送信し、多くの有効なcode wordを含み、多くのエラーを訂正するか、少なくとも[エラー検出|検出する]コードを見つけることです。互いに排他的ではありませんが、これらの分野でのパフォーマンスはトレードオフです。したがって、異なるコードが異なるアプリケーションに最適です。このコードの必要なプロパティは、主に、送信中に発生するエラーの確率に依存します。典型的なCDでは、損傷は主にほこりまたは傷である。

CDはクロスインターリーブされたリードソロモン符号化を使用してディスク上にデータを広げます。

非常に良いコードではありませんが、単純なリピートコードはわかりやすい例として役立ちます。データビット（サウンドを表す）をブロックして3回送信するとします。受信機では、3回の繰り返しを少しずつ検討し、多数決をとる。これのひねりは、ビットを順番に送るだけではないということです。我々はそれらをインターリーブする。データビットのブロックは、まず4つのより小さいブロックに分割される。次に、ブロックを循環して、最初のビットから1ビット、次に2番目のビットなどを送ります。これは3回実行され、ディスクの表面にデータを広げます。簡単なリピートコードの文脈では、これは有効に見えないかもしれません。しかしながら、このインターリービング技術が使用されるときにスクラッチまたはダストスポットの「バースト」エラーを修正するのに非常に有効な、より強力なコードが知られている。

他のコードは、異なるアプリケーションに適しています。ディープスペース通信は、受信機の熱雑音によって制限され、バースト性よりも連続性が高い。同様に、狭帯域モデムは、電話ネットワークに存在する雑音によって制限され、また、連続妨害として良好にモデル化される。携帯電話は急速に退色する。使用される高い周波数は、受信機が数インチ動いても、信号の急速なフェーディングを引き起こす可能性があります。再び、フェージングに対抗するように設計されたチャネルコードのクラスが存在する。

線形コード[編集]

「代数的コーディング理論」という用語は、コードの性質が代数的に表現され、さらに研究されるコーディング理論のサブ分野を意味します。

代数的コーディング理論は基本的に2つの主要なタイプのコードに分けられます：

＃リニアブロックコード＃畳み込み符号

主に以下の3つのコードの特性を分析します。

コードワード長
有効なコードワードの総数
主にハミング距離を使用する2つの有効なコードワード間の最小距離、時には距離のような他の距離

線形ブロックコード[編集]

線形ブロック符号は線形性の特性を有し、すなわち、任意の2つの符号語の和も符号語であり、それらはブロック内のソースビットに適用され、したがって名前は線形ブロック符号である。線形ではないブロックコードがありますが、このプロパティがないコードが優れていることを証明することは困難です。

別のコードプロパティは、単一のコードワードが持つ可能性のある近隣の数です。ここでも例としてペニーを考えてみましょう。最初に、ペニーを長方形のグリッドにパックします。それぞれのペニーには、4つの近所の人がいます（さらに遠くにあるコーナーでは4人）。六角形では、各ペニーは6近傍になります。寸法を大きくすると、近傍の数が非常に急激に増加します。その結果、雑音が受信者に隣接（したがってエラー）を選択させる方法の数も増えます。これは、ブロックコード、そして実際にはすべてのコードの基本的な制限です。単一のネイバーにエラーを発生させるのは難しいかもしれませんが、ネイバーの数は十分に大きくて、実際には合計エラー確率は低下します。最もよく知られている[成形コード]の一つです。この同じ特性は、センサネットワークで分散ソースコード

畳み込み符号[編集]

畳み込み符号の背後にあるアイデアは、あらゆる符号語シンボルを様々な入力メッセージシンボルの加重和とすることである。入力とインパルス応答を知っているとき、システムの出力を見つけるために LTIシステムで使われる畳み込みのようなものです。

したがって、システムの畳み込みエンコーダの出力は、入力ビットの畳み込みであり、畳み込みエンコーダのレジスタの状態と比較して一般に求められます。

根本的に、畳み込み符号は等価ブロック符号よりもノイズに対する保護が大きくない。多くの場合、それらは一般に等しい電力のブロックコードよりも実装が簡単です。エンコーダは通常、状態メモリといくつかのフィードバックロジック、通常はXORゲートを持つ簡単な回路です。 decoderは、ソフトウェアやファームウェアで実装することができます。

ビタビアルゴリズムは、畳み込み符号を復号するのに使用される最適なアルゴリズムである。計算負荷を軽減するための単純化があります。彼らは最も可能性の高いパスのみを検索することに頼っています。最適ではありませんが、低ノイズ環境で良好な結果が得られることが一般的に判明しています。

畳み込み符号は、音声帯域モデム（V.32、V.17、V.34）およびGSM携帯電話、ならびに衛星通信および軍事通信装置で使用される。

暗号コーディング[編集]

[暗号化]または暗号化コーディングは、第三者（「敵対者（暗号）|敵対者」と呼ばれる）の存在下での[安全な通信]のための技術の実践と研究である。より一般的には、敵をブロックするプロトコルを構築して分析することです。データ[機密性]、データの整合性、認証、否認不可能など、情報セキュリティのさまざまな側面は、現代の暗号の中心です。現代の暗号は、数学、コンピュータサイエンス、電気工学の分野の交差点に存在します。暗号化のアプリケーションには、[ATM（Automated Teller Machine）| ATMカード]、コンピュータパスワード、電子商取引などがあります。

現代に至る前の暗号は、情報の読み取り可能な状態から見かけの[[ナンセンス]への変換である] 暗号化 'と実質的に同義でした。暗号化されたメッセージの発信者は、意図された受信者だけが元の情報を回復するために必要な復号化技術を共有し、それによって不要な人物が元の情報を元に戻すことを排除します。 [第一次世界大戦]と[コンピュータ]の到来以来、暗号を実行するために使われた方法はますます複雑になり、そのアプリケーションはより広範になりました。

現代の暗号は、数学理論とコンピュータサイエンスの実践に大きく基づいています。暗号アルゴリズムは計算硬度仮定を中心に設計されているため、実際にはどんな敵によっても破壊されにくい。理論的には、このようなシステムを壊すことは可能ですが、実際の既知の方法で実行することは不可能です。したがって、これらのスキームは計算上安全と呼ばれます。理論的進歩、例えば整数分解アルゴリズムの改良、およびより高速のコンピューティング技術は、これらの解決策が絶えず適応されることを必要とする。無制限のコンピューティングパワーでも破られない[情報理論的安全性|情報理論的安全性]スキームが存在します - 例はワンタイムパッドですが、これらのスキームは理論的に最も優れたもの解読可能であるが計算上安全なメカニズムである。

ラインコーディング[編集]

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

ラインコーディングは、物理チャネル（および受信装置）の特定の特性に対して最適に調整された振幅および時間離散信号によって伝送される[[デジタル信号（電子機器）|デジタル信号]を表すことからなる。伝送リンク上のデジタルデータの1と0を表すために使用される電圧または電流の[波形]パターンは、「ラインエンコーディング」と呼ばれます。ラインエンコーディングの一般的なタイプは、ユニポーラ、ポーラ、バイポーラ、マンチェスターエンコーディングです

コーディング理論の他の応用[編集]

コーディング理論のもう一つの関心事は、同期を助けるコードを設計することです。コードは、位相シフトを容易に検出して補正することができ、複数の信号を同じチャネル上で送信できるように設計することができる。

一部の携帯電話システムで使用されるコードの別のアプリケーションは、コード分割多重アクセス（CDMA）です。各電話機には、他の電話機のコードとほぼ無相関なコードシーケンスが割り当てられています。送信時には、コードワードは、音声メッセージを表すデータビットを変調するために使用される。受信機では、復調処理が行われてデータが復元される。このクラスのコードの特性は、（異なるコードを有する）多くのユーザが同じ無線チャネルを同時に使用することを可能にする。受信機には、他のユーザの信号は、低レベルノイズとしてのみ復調器に現れる。

別の一般的なコードのクラスは、automatic repeat-request（ARQ）コードです。これらのコードでは、送信者は通常、チェックビットを追加することによってエラーチェックのために各メッセージに冗長性を追加します。チェックビットが到着したときに残りのメッセージと一致しない場合、受信者は送信者にメッセージの再送信を要求します。最も単純な広域ネットワークプロトコルを除くすべてのプロトコルはARQを使用します。一般的なプロトコルには、 SDLC（IBM）、[Transmission Control Protocol | TCP]（インターネット）、[X.25]（International）などがあります。拒否されたパケットと新しいパケットとを照合する問題のために、このトピックに関する広範な研究分野が存在する。それは新しいものなのですか、それとも再送信ですか？通常、TCPのように番号付け方式が使用されます。

グループテスト[編集]

グループテストではコードを別の方法で使用します。特定の方法（例えば、欠陥のある製品や感染したテスト対象）で非常に少数のアイテムが異なる大きなグループのアイテムを考えてみましょう。グループテストの考え方は、可能な限りいくつかのテストを使用してどの項目が「異なっているか」を判断することです。問題の起源は、第2次世界大戦に根ざしています。[米国陸軍空軍]が兵士の[梅毒]検査を必要とした時です。それはRobert Dorfmanの画期的な論文に由来しています。

アナログコーディング[編集]

情報は[脳]の[神経回路網]、[アナログ信号処理]、アナログエレクトロニクスで同様に符号化されます。アナログ符号化の態様には、アナログ誤り訂正、アナログ・データ圧縮とアナログ暗号化。

ニューラルコーディング[編集]

Neural codingはneuronsの networksによってどのように感覚や他の情報が表現されているかに関する[neuroscience]関連分野です。神経コードを研究する主な目的は、[刺激（生理）|刺激]と個体またはアンサンブルニューロンの反応とアンサンブルにおけるニューロンの電気的活動の関係との関係を特徴付けることである。ニューロンはデジタルとアナログ情報の両方を符号化することができ、ニューロンは情報理論の原則に従って情報を圧縮し、脳およびより広い神経系全体に送信される信号のエラー。

Notes[編集]

ソース[編集]

http://wikipedia.org/