符号理論

ウィキペディアから、無料の百科事典
ナビゲーションにジャンプ 検索にジャンプ
符号理論の重要な尺度であるハミング距離の2次元可視化。

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

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

  1. データ圧縮(またはソースコーディング
  2. エラー制御(またはチャネルコーディング
  3. 暗号コーディング
  4. ラインコーディング

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

エラー訂正は、余分なデータビットを追加して、伝送チャネルに存在する外乱に対してデータの伝送をより堅牢にします。通常のユーザーは、エラー訂正を使用する多くのアプリケーションに気付いていない可能性があります。一般的な音楽用コンパクトディスク(CD)は、リードソロモンコードを使用して傷やほこりを修正します。このアプリケーションでは、伝送チャネルはCD自体です。携帯電話はまた、コーディング技術を使用して、高周波無線伝送のフェージングとノイズを補正します。データモデム、電話伝送、およびNASA Deep Space Networkはすべて、チャネルコーディング技術を使用して、ビットを通過させます。たとえば、ターボコードLDPCコードなどです。

符号理論の歴史

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

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

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

1972年、ナシルアフマドは、1973年にT.ナタラジャンとKRラオと共に開発した離散コサイン変換(DCT)を提案しました。 [2] DCTは、最も広く使用されている非可逆圧縮アルゴリズムであり、 JPEGなどのマルチメディア形式の基礎ですMPEGおよびMP3

ソースコーディング

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

定義

データは確率変数と見なすことができます 、 どこ確率で現れる

データはアルファベット上の文字列(単語)でエンコードされます

コードは関数です

(また空の文字列がアルファベットの一部でない場合)。

に関連付けられているコードワードです

コードワードの長さは次のように記述されます

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

コードワードの連結

空の文字列のコードワードは、空の文字列自体です。

プロパティ

  1. 単射の場合非特異です。
  2. 単射の場合は一意にデコード可能です。
  3. 次の場合瞬時ですのプレフィックスではありません(およびその逆)。

原則

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

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

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

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

チャネルコーディング

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

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

あまり良いコードではありませんが、単純な繰り返しコードは理解しやすい例として役立ちます。データビット(音を表す)のブロックを取得し、それを3回送信するとします。受信者では、3回の繰り返しを少しずつ調べて、多数決を行います。これのひねりは、単にビットを順番に送信するだけではないということです。それらをインターリーブします。データビットのブロックは、最初に4つの小さなブロックに分割されます。次に、ブロックを循環して、最初のビットから1ビット、次に2番目のビットを送信します。これは、データをディスクの表面全体に広げるために3回実行されます。単純な繰り返しコードのコンテキストでは、これは効果的ではないように見える場合があります。ただし、このインターリーブ技術を使用すると、引っかき傷やほこりの「バースト」エラーを修正するのに非常に効果的な、より強力なコードが知られています。

他のコードは、さまざまなアプリケーションに適しています。深宇宙通信は、バースト性よりも連続性の高い受信機の熱雑音によって制限されます。同様に、狭帯域モデムは、電話網に存在するノイズによって制限され、継続的な外乱としてより適切にモデル化されます。[要出典]携帯電話は急速に衰退します。使用される高周波は、受信機が数インチ動かされた場合でも、信号の急速なフェージングを引き起こす可能性があります。ここでも、フェージングと戦うように設計されたチャネルコードのクラスがあります。[要出典]

線形コード

代数的符号理論という用語は、コードの特性が代数的用語で表現され、さらに研究される符号理論のサブフィールドを意味します。[要出典]

代数的符号理論は、基本的に2つの主要なタイプのコードに分けられます。[要出典]

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

コードの次の3つのプロパティを分析します–主に:[要出典]

線形ブロックコード

線形ブロックコードには線形性の特性があります。つまり、任意の2つのコードワードの合計もコードワードであり、ブロック内のソースビットに適用されるため、線形ブロックコードと呼ばれます。線形ではないブロックコードがありますが、このプロパティがないとコードが優れていることを証明するのは困難です。[4]

線形ブロックコードは、シンボルのアルファベット(たとえば、バイナリまたはターナリ)とパラメータ(nmd min)によって要約されます[5]

  1. nはコードワードの長さで、記号で表されます。
  2. mは、一度にエンコードに使用されるソースシンボルの数です。
  3. d minは、コードの最小ハミング距離です。

線形ブロックコードには、次のような多くの種類があります。

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

ブロックコードは、球充填の問題に関連しています。球充填の問題は、長年にわたって注目を集めています。2次元では、視覚化が容易です。たくさんのペニーをテーブルの上に平らに置き、それらを一緒に押します。その結果、蜂の巣のような六角形のパターンになります。しかし、ブロックコードは、簡単に視覚化できないより多くの次元に依存しています。深宇宙通信で使用される強力な(24,12)ゴレイ符号は24次元を使用します。バイナリコード(通常はそうです)として使用される場合、寸法は上記で定義されたコードワードの長さを指します。

符号理論は、N次元の球モデルを使用します。たとえば、卓上で1セント硬貨を円に詰めることができる数や、3次元で、地球儀にビー玉をいくつ詰めることができるかなどです。その他の考慮事項は、コードの選択を入力します。たとえば、長方形のボックスの拘束に六角形のパッキングを入れると、コーナーに空きスペースが残ります。寸法が大きくなると、空きスペースの割合は小さくなります。しかし、特定の寸法では、パッキングはすべてのスペースを使用し、これらのコードはいわゆる「完璧な」コードです。唯一の重要で有用な完全なコードは、(2 r – 1、2 r – 1 – r、3)を満たすパラメーターを持つ距離3ハミングコードと、[23,12,7]バイナリおよび[11,6,5]です。 ]三元ゴレイ符号。[4][5]

もう1つのコードプロパティは、単一のコードワードが持つ可能性のあるネイバーの数です。[6] 繰り返しになりますが、例として1セント硬貨を考えてみましょう。まず、ペニーを長方形のグリッドに詰めます。各ペニーには、4つの近くの隣人がいます(そして4つは遠くの角にあります)。六角形では、各ペニーには6つの近くの隣人がいます。次元を増やすと、近傍の数が非常に急速に増加します。その結果、ノイズが受信機にネイバーを選択させる(したがってエラーが発生する)方法の数も増えます。これは、ブロックコード、そして実際にはすべてのコードの基本的な制限です。単一のネイバーにエラーを発生させるのは難しいかもしれませんが、ネイバーの数が十分に多い可能性があるため、合計エラー確率が実際に低下します。[6]

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

畳み込み符号

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

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

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

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

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

暗号コーディング

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

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

現代の暗号化は、数学的理論とコンピューターサイエンスの実践に大きく基づいています。暗号化アルゴリズムは、計算難度の仮定に基づいて設計されているため、このようなアルゴリズムを実際に攻撃者が破ることは困難です。このようなシステムを破壊することは理論的には可能ですが、既知の実用的な手段で破壊することは不可能です。したがって、これらのスキームは計算上安全と呼ばれます。理論の進歩、たとえば、素因数分解アルゴリズムの改善、およびより高速なコンピューティングテクノロジーでは、これらのソリューションを継続的に適応させる必要があります。情報理論的に安全なスキームが存在し、無制限のコンピューティング能力があっても破ることはできません。例としては、ワンタイムパッドがあります。—しかし、これらのスキームは、理論的には壊れやすいが計算上安全な最高のメカニズムよりも実装が困難です。

ラインコーディング

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

ラインコーディングは、物理チャネル(および受信機器)の特定のプロパティに最適に調整された振幅および時間離散信号によって転送されるデジタル信号を表すことで構成されます。伝送リンク上のデジタルデータの1と0を表すために使用される電圧または電流波形パターンは、ラインエンコーディングと呼ばれます。ラインエンコーディングの一般的なタイプは、ユニポーラポーラバイポーラ、およびマンチェスターエンコーディングです。

符号理論の他の応用

コーディング理論のもう1つの懸念は、同期に役立つコードを設計することです。位相シフトを簡単に検出して修正でき、同じチャネルで複数の信号を送信できるように、コードを設計できます。[要出典]

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

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

グループテスト

グループテストでは、コードを別の方法で使用します。非常に少数が特定の方法で異なるアイテムの大規模なグループを考えてみてください(たとえば、欠陥のある製品や感染した被験者)。グループテストの考え方は、可能な限り少ないテストを使用して、どの項目が「異なる」かを判断することです。問題の原因は、第二次世界大戦米陸軍航空軍が兵士の梅毒検査を行う必要があったことに端を発しています。[11]

アナログコーディング

情報は、脳のニューラルネットワークアナログ信号処理、およびアナログ電子機器で同様にエンコードされますアナログコーディングの側面には、アナログエラー訂正、[12] アナログデータ圧縮[13]、およびアナログ暗号化が含まれます。[14]

ニューラルコーディング

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

も参照してください

メモ

  1. ^ ジェームズアーバイン; デビッドハール(2002)。「2.4.4コーディングの種類」。データ通信とネットワークp。18. ISBN 9780471808725コーディングには4つのタイプがあります
  2. ^ ナシル・アフマド「離散コサイン変換をどうやって思いついたのか」デジタル信号処理、Vol。1、Iss。1、1991、pp.4-5。
  3. ^ トッドキャンベル。 「AnswerGeek:エラー訂正ルールCD」
  4. ^ a b Terras、オードリー(1999)。有限群とアプリケーションのフーリエ解析ケンブリッジ大学出版局p。 195ISBN  978-0-521-45718-7
  5. ^ a b Blahut、Richard E.(2003)。データ伝送のための代数コードケンブリッジ大学出版局。ISBN 978-0-521-55374-2
  6. ^ ab クリスチャンシュレーゲル; ランスペレス(2004)。トレリスとターボコーディングWiley-IEEE。p。73. ISBN  978-0-471-22755-7
  7. ^ Forney、GD、Jr。(1992年3月)。「トレリスシェーピング」。情報理論に関するIEEEトランザクション38(2 Pt 2):281–300。土井10.1109 /18.119687
  8. ^ Rivest、Ronald L.(1990)。「暗号学」。J. Van Leeuwen(ed。)理論計算機科学ハンドブック1.エルゼビア。
  9. ^ ベラレ、ミヒル; フィリップ・ロガウェイ(2005年9月21日)。"序章"。現代暗号の紹介p。10.10。
  10. ^ メネゼス、AJ; van Oorschot、PC; ヴァンストーン、SA(1997)。応用暗号化ハンドブックISBN 978-0-8493-8523-0
  11. ^ ドーフマン、ロバート(1943)。「大規模な集団の欠陥のあるメンバーの検出」数学的統計の年報14(4):436–440。土井10.1214 / aoms / 1177731363
  12. ^ チェン、ブライアン; グレゴリー・ワーネル、グレゴリー・W(1998年7月)。「カオス力学系に基づくアナログ誤り訂正符号」(PDF)通信に関するIEEEトランザクション46(7):881–890。CiteSeerX10.1.1.30.4093_ 土井10.1109 /26.7013122001年9月27日にオリジナル(PDF)からアーカイブされました2013年6月30日取得  
  13. ^ Novak、Franc; Hvala、Bojan; Klavžar、Sandi(1999)。「アナログ署名分析について」。ヨーロッパでの設計、自動化、テストに関する会議の議事録CiteSeerX10.1.1.142.5853_ ISBN   1-58113-121-6
  14. ^ Shujun Li; Chengqing Li; Kwok-Tung Lo; Guanrong Chen(2008年4月)。「ブラインドソース分離に基づく暗号化スキームの暗号分析」(PDF)回路およびシステムに関するIEEEトランザクションI。55(4):1055–63。arXivcs / 0608024土井10.1109 /TCSI.2008.916540
  15. ^ Brown EN、Kass RE、Mitra PP(2004年5月)。「複数の神経スパイクトレインデータ分析:最先端および将来の課題」(PDF)ネイチャーニューロサイエンス7(5):456–461。土井10.1038 / nn1228PMID15114358_  
  16. ^ ソープ、SJ(1990)。「スパイクの到着時間:ニューラルネットワークの非常に効率的なコーディングスキーム」(PDF)Eckmiller、R。; Hartmann、G。; Hauske、G。(編)。ニューラルシステムとコンピューターでの並列処理(PDF)北ホラント。pp。91–94。ISBN  978-0-444-88390-22013年6月30日取得
  17. ^ Gedeon、T。; パーカー、AE; ディミトロフ、AG(2002年春)。「情報の歪みとニューラルコーディング」カナダの応用数学四半期ごと10(1) 10。CiteSeerX10.1.1.5.6365 
  18. ^ Stiber、M。(2005年7月)。「スパイクタイミングの精度と神経エラー訂正:局所的な振る舞い」。ニューラル計算17(7):1577–1601。arXivq-bio / 0501021土井10.1162 / 0899766053723069PMID15901408_  

参考文献