いつ、そしてなぜ符号理論が生まれたのか。コーディングの理論。コーディングの種類。コーディング。基本概念

コーディング理論-コードの特性と、特定の目標を達成するためのコードの適合性の研究。情報のエンコードは、直接使用するのに便利な形式から、送信、保存、自動処理、および不正アクセスからの保存に便利な形式に変換するプロセスです。コーディング理論の主な問題には、1対1のコーディングの問題と、特定の条件下での通信チャネルの実装の複雑さが含まれます。この点で、符号理論は主に次の領域を考慮します：データ圧縮、前方誤り訂正、暗号化、物理符号化、誤り検出および訂正。

フォーマット

コースは10アカデミックウィークで構成されています。テストのほとんどの課題をうまく解決するには、講義で語られた資料をマスターするだけで十分です。セミナーでは、基本に精通しているリスナーが興味を持つ可能性のある、より複雑なタスクも扱います。

コースプログラム

アルファベット順のコーディング。明確なデコードのための十分条件：均一性、プレフィックス、サフィックス。独自性の認識：マルコフの基準。あいまいにデコード可能な単語の長さの見積もり。
クラフトの不等式; 与えられた単語の長さのセットを持つプレフィックスコードの存在。プレフィックスコードの普遍性の結果。
最小冗長性コード：問題ステートメント、ハフマンの削減定理。
エラーを修正および検出するタスク。幾何学的解釈。エラーの種類。ハミングとレーベンシュタインのメトリック。コード距離。エラー訂正コードの理論の主なタスク。
Varshamov-Tenengoltsコード、シンボルのドロップアウトと挿入の単一エラーを修正するためのアルゴリズム。
置換エラー訂正コードのパラメーターの最も単純な限界：球充填限界、シングルトン限界、プロトキン限界。
距離空間の埋め込み。ユークリッド空間のベクトル数に関する補題。エリアス-バサリゴ国境。
ラインコード。定義。行列の生成とチェック。コード距離とチェックマトリックスの関係。バルシャモフ-ギルバート境界。体系的なコーディング。症候群のデコード。ハミングコード。
残りのコード。グライスマー-ソロモン-スティフラー境界。
線形コードのデコードの問題の複雑さ：NCP問題（最も近いコードワードに関する問題）。
リードソロモンコード。 Berlekamp-Welchデコードアルゴリズム。
リードマラーコード：コード距離、多数決デコードアルゴリズム。
リードマラー構造の一般化の変形。リプトンの見出語-DeMillo-Schwartz-Zippel。代数幾何学的コードの概念。
エクステンダーグラフ。エキスパンダーの存在の確率的証明。 2部グラフに基づくコード。エキスパンダーに基づくコードのコード距離。 Sipser-Spielmanデコードアルゴリズム。
確率的チャネルモデルに対するシャノンの定理。
エラー訂正コードアプリケーション。通信の複雑さにおけるランダム化されたプロトコル。マックエリス暗号。コードに基づく均質な（疑似ランダム）セット、MAX-SAT問題での非ランダム化へのそれらのアプリケーション。

ウィキペディアから、無料の百科事典

符号理論-コードの特性と目標を達成するためのそれらの適合性の科学。

一般情報

エンコーディングとは、データを直接使用するのに便利な形式から、送信、保存、自動処理、および不正アクセスからの保存に便利な形式に変換するプロセスです。コーディング理論の主な問題には、1対1のコーディングの問題と、特定の条件下での通信チャネルの実装の複雑さが含まれます。この点で、符号理論は主に次の領域を考慮します。

データ圧縮

前方誤り訂正

暗号化

暗号化（他のギリシャ語から。 κρυπτός -隠されて γράφω -私は書きます）、これは機密性（部外者に情報を読み取ることができない）、データの整合性（情報を知覚できないほど変更することができない）、認証（オブジェクトの作成者またはその他のプロパティの認証）を保証する方法に関する知識の分野です。だけでなく、著者を拒否することの不可能性

2006年4月4日LeonidChernyak カテゴリ：テクノロジー

「オープンシステム」コンピュータの出現と同時に、信号コーディングの理論が作成されていなければ、コンピュータの作成は不可能です。コーディング理論は、コンピューティングの開発に大きな影響を与えた数学の分野の1つです。

「オープンシステム」

コンピュータの出現と同時に、信号コーディングの理論が作成されていなかったとしたら、コンピュータの作成は不可能だったでしょう。

符号理論は、コンピューティングの発展に著しく影響を与えた数学の分野の1つです。その範囲は、実際の（またはノイズの多い）チャネルを介したデータ送信にまで及び、送信された情報の正確性を保証することが目的です。言い換えれば、シグナリング後に有用な情報をデータから確実かつ簡単に抽出できるように、データをパックする最善の方法を研究します。コーディング理論が暗号化と混同されることもありますが、これは真実ではありません。暗号化は逆問題を解決し、その目標はデータから情報を抽出することを困難にすることです。

データをエンコードする必要性は、電信の発明の直後、150年以上前に最初に遭遇しました。チャネルは高価で信頼性が低いため、コストを最小限に抑え、電報送信の信頼性を高めることが急務でした。この問題は、大西洋横断ケーブルの敷設によって悪化しています。 1845年以来、特別なコードブックが使用されるようになりました。彼らの助けを借りて、通信士は手動でメッセージを「圧縮」し、一般的な単語シーケンスをより短いコードに置き換えました。同時に、転送の正確さをチェックするために、パリティが使用されるようになりました。これは、第1世代および第2世代のコンピューターでパンチカードの入力の正確さをチェックするためにも使用された方法です。これを行うために、チェックサム付きの特別に準備されたカードが最後の入力デッキに挿入されました。入力デバイスの信頼性が低い場合（またはデッキが大きすぎる場合）、エラーが発生する可能性があります。これを修正するために、計算されたチェックサムがカードに保存されている金額と一致するまで、入力手順が繰り返されました。このスキームは不便であるだけでなく、二重の障害も見逃します。通信チャネルの開発に伴い、より効果的な制御メカニズムが必要になりました。

ノイズの多いチャネルを介したデータ伝送の問題に対する最初の理論的解決策は、統計情報理論の創設者であるクロード・シャノンによって提案されました。シャノンは彼の時代のスターであり、彼は米国の学術エリートの一人でした。ヴァネヴァー・ブッシュの大学院生として、1940年に彼は30歳未満の科学者に授与されるノーベル賞（ノーベル賞と混同しないでください！）を受賞しました。ベル研究所にいる間、シャノンは「メッセージ伝送の数学的理論」（1948）を書き、チャネルの帯域幅がメッセージソースのエントロピーよりも大きい場合、メッセージは次のようにエンコードできることを示しました。過度の遅延なしに送信されます。この結論は、シャノンによって証明された定理の1つに含まれています。その意味は、十分な帯域幅を持つチャネルがあれば、メッセージをある程度の時間遅延で送信できるという事実に要約されます。さらに、彼はチャネル内のノイズの存在下で信頼できる伝送の理論的可能性を示しました。ミシガン州の故郷に設置されたシャノンのささやかな記念碑に刻まれた式C = W log（（P + N）/ N）は、アルバートアインシュタインの式E = mc2と値が比較されます。

シャノンの研究は、情報理論の分野で多くのさらなる研究を生み出しましたが、それらには実用的な工学的応用はありませんでした。理論から実践への移行は、ベル研究所のシャノンの同僚であるリチャード・ハミングの努力によって可能になりました。彼は、「ハミングコード」と呼ばれるようになったコードのクラスを発見したことで有名になりました。 40年代半ばにベルモデルVリレー計算機でパンチカードを使用することの不便さが彼らのハミングコードの発明を促したという伝説があります。彼は、オペレーターがいない週末にマシンで作業する時間を与えられ、彼自身が入力をいじる必要がありました。それはそうかもしれませんが、ハミングは、主にプロセッサとメモリの間のコンピュータのデータ伝送ラインを含む、通信チャネルのエラーを修正できるコードを提案しました。ハミングコードは、シャノンの定理によって示される可能性が実際にどのように実現されるかを示す証拠になりました。

ハミングは1950年に彼の論文を発表しましたが、内部の報告では彼の符号理論は1947年にさかのぼります。したがって、シャノンではなくハミングが符号理論の父と見なされるべきであると考える人もいます。しかし、技術の歴史の中で、最初のものを探すことは無意味です。

「エラー訂正コード」（エラー訂正コード、ECC）を最初に提案したのはハミングであったことは確かです。これらのコードの最新の変更は、すべてのデータストレージシステムで、およびプロセッサとRAM間の交換に使用されます。それらの変形の1つであるリードソロモンコードはCDで使用され、傷やほこりの粒子を引き起こす可能性のあるきしみ音やノイズなしで録音を再生できます。ハミングに基づくコードには多くのバージョンがあり、コーディングアルゴリズムとチェックビット数が異なります。このようなコードは、惑星間ステーションとの深宇宙通信の開発に関連して特に重要になっています。たとえば、7つの情報ビットに対して32の制御ビット、または6つの情報ビットに対して26の制御ビットがあるリードマラーコードがあります。

最新のECCコードの中で、LDPC（低密度パリティチェックコード）コードに言及する必要があります。実際、それらは約30年前から知られていましたが、高解像度テレビが開発され始めた近年、それらに対する特別な関心が正確に発見されました。 LDPCコードは100％信頼できるわけではありませんが、チャネル帯域幅を最大限に活用しながら、エラーレートを目的のレベルに調整できます。「ターボ符号」はそれらに近く、深宇宙にあり、チャネル帯域幅が制限されているオブジェクトを操作する場合に効果的です。

ウラジーミル・アレクサンドロヴィッチ・コテルニコフの名前は、符号理論の歴史にしっかりと刻まれています。 1933年、「通信の技術的再構築に関する最初の全組合会議のための無線通信に関する資料」で、彼は「帯域幅について？エーテル？」という作品を発表しました。と？ワイヤー？コテルニコフの名前は、同等として、符号理論で最も重要な定理の1つの名前に含まれています。この定理は、情報を失うことなく送信信号を復元できる条件を定義します。

この定理は、「WKS定理」（略語WKSはWhittaker、Kotelnikov、Shannonから取られています）を含め、さまざまに呼ばれています。一部の情報源では、ナイキスト-シャノンのサンプリング定理とウィッタカー-シャノンのサンプリング定理の両方が使用されており、国内の大学の教科書では、単に「コテルニコフの定理」が最もよく見られます。実際、定理には長い歴史があります。その最初の部分は、1897年にフランスの数学者エミールボレルによって証明されました。エドマンドウィッタカーは1915年に貢献しました。 1920年に日本のKinnosukiOguraはWhittakerの研究に対する修正を発表し、1928年にアメリカのHarryNyquistはデジタル化とアナログ信号再構成の原理を洗練しました。

クロード・シャノン（1916年-2001年）彼の学生時代から、数学と電気工学に同等の関心を示しました。 1932年に、彼は1936年にミシガン大学に入学しました。マサチューセッツ工科大学で1940年に卒業し、電気工学の修士号と数学の博士号の2つの学位を取得しました。 1941年、シャノンはベル研究所に加わりました。ここで彼は後に情報理論をもたらすアイデアを開発し始めました。 1948年、シャノンは「コミュニケーションの数学的理論」という記事を発表しました。この記事では、科学者の基本的な考え方、特にエントロピーによる情報量の決定が定式化され、2つの選択を決定する情報の単位も提案されました。同様に可能性の高いオプション、つまり、後でビットと呼ばれるもの。 1957- 1961年に、シャノンはノイズの多い通信チャネルのスループット定理を証明する作品を発表しました。これは現在彼の名前を冠しています。 1957年、シャノンはマサチューセッツ工科大学の教授になり、21年後に引退しました。「当然の休息」で、シャノンはジャグリングに対する彼の古い情熱に完全に専念しました。彼はいくつかのジャグリングマシンを構築し、ジャグリングの一般的な理論さえ作成しました。

リチャードハミング（1915年-1998年）シカゴ大学で教育を開始し、1937年に学士号を取得しました。 1939年、彼はネブラスカ大学で修士号を取得し、イリノイ大学で数学の博士号を取得しました。 1945年、ハミングは、原子爆弾を製造するための大規模な政府の研究活動であるマンハッタン計画に取り組み始めました。 1946年、ハミングはベル研究所に加わり、クロードシャノンと協力しました。 1976年、ハミングはカリフォルニア州モントレーの海軍大学院で議長を務めました。

彼を有名にした作品、エラー検出および訂正コードの基礎研究は、1950年にハミングによって出版されました。 1956年、彼は初期のIBM 650メインフレームの1つに携わり、後に高水準プログラミング言語に進化したプログラミング言語の基礎を築きました。コンピュータサイエンスの分野へのハミングの貢献を認めて、IEEEは彼にちなんで名付けられたコンピュータサイエンスとシステム理論のためのDistinguished ServiceMedalを制定しました。

ウラジーミル・コテルニコフ（1908-2005）1926年に彼はNEバウマン（MVTU）にちなんで名付けられたモスクワ高等技術学校の電気工学部に入学しましたが、独立した研究所としてMVTUから分離したモスクワ電力工学研究所（MPEI）の卒業生になりました。コテルニコフは大学院（1931-1933）で勉強している間、数学的に正確に定式化され、後に彼にちなんで名付けられた「参照定理」を証明しました。 1933年に大学院を卒業した後、モスクワ電力工学研究所で教鞭をとったコテルニコフは、中央通信研究所（TsNIIS）に勤務しました。 1941年、V。A。Kotelnikovは、数学的に解読できないシステムが満たすべき要件について明確な立場を確立し、それを解読できないことの証明が与えられました。 1944年、コテルニコフは教授、MPEIの無線工学部の学部長に就任し、1980年まで勤務しました。 1953年、45歳で、コテルニコフはすぐにソ連科学アカデミーの正会員に選出されました。 1968年から1990年まで、V。A。コテルニコフは教授であり、モスクワ物理技術研究所の学部長でもありました。

符号理論の誕生

コーディングの理論。コーディングの種類コーディング理論の基本概念以前は、コーディングツールは補助的な役割を果たし、数学研究の個別の主題とは見なされていませんでしたが、コンピューターの出現により、状況は根本的に変化しました。コーディングは文字通り情報技術に浸透しており、さまざまな（実質的にすべての）プログラミングタスクを解決する上で中心的な問題です。 ۞不正アクセスからの情報の保護。 ۞通信チャネルを介したデータ送信中のノイズ耐性の確保。 ۞データベース内の情報の圧縮。符号理論は、メッセージを表す信号でメッセージを識別する方法を研究する情報理論の一分野です。タスク：情報源を通信チャネルと調整します。オブジェクト：情報ソースを通じて消費者に提供される個別または継続的な情報。エンコーディングとは、特定の通信チャネルを介した送信に便利な式に情報を変換することです。数学でのコーディングの例は、デカルトによって導入された座標法です。これにより、数字、文字、およびそれらの組み合わせ（数式）の形式での分析式を通じて幾何学的オブジェクトを研究することが可能になります。コーディングの概念は、特定の通信チャネルを介した送信に便利な形式に情報を変換することを意味します。デコードとは、受信したメッセージをエンコードされたフォームからコンシューマーがアクセスできるフォームに復元することです。

トピック5.2。アルファベット順のコーディング一般的なケースでは、コーディングの問題は次のように表すことができます。有限数の文字で構成される2つのアルファベットAとBを指定します：と。アルファベットの要素は文字と呼ばれます。アルファベットAの順序集合は単語と呼ばれます。ここでn = l（）= | |。、数字nは単語内の文字数を示し、単語の長さと呼ばれます。空の単語は次のように表されます。単語の場合、文字a1は単語の先頭または接頭辞、文字anと呼ばれます。単語の末尾または接尾辞です。、および単語を組み合わせることができます。これを行うには、2番目の単語の接頭辞が最初の単語の接尾辞の直後に続く必要がありますが、新しい単語では、単語の1つが空でない限り、自然にステータスが失われます。さらに、単語の複合語とが示され、n個の同一の単語の複合語が示されます。アルファベットAのすべての空でない単語のセットはA *で示されます。セットAはメッセージアルファベットと呼ばれ、セットBはコーディングアルファベットと呼ばれます。アルファベットBで構成された単語のセットはB *で示されます。

アルファベットAからアルファベットBへの単語のマッピングをFで示します。この場合、その単語は単語のコードと呼ばれます。コーディングは、メッセージ要素とこれらの要素を固定できる信号との間の対応システムの形で、情報の保存、送信、および処理中に情報を表示する普遍的な方法です。したがって、コードは、通常は情報を失うことなく、ある記号表現形式（元のアルファベットA）から別の記号表現形式（オブジェクトアルファベットB）へのメッセージの明確な変換（つまり、機能）のルールです。 F：A * B *→元のアルファベットAの単語をアルファベットBに変換するプロセスは、情報コーディングと呼ばれます。単語を逆変換するプロセスは、デコードと呼ばれます。したがって、デコードはFの逆です。 F1。一言で言えば、どのエンコーディングでもデコード操作を実行する必要があるため、マッピングは反転可能（全単射）である必要があります。 | B | = mの場合、Fは模倣コーディングと呼ばれ、最も一般的なケースはB =（0、1）バイナリコーディングです。以下で検討するのはこの場合です。すべてのコードワードの長さが同じである場合、そのコードはユニフォームまたはブロックと呼ばれます。アルファベット（または文字ごと）のコーディングは、コードテーブルで指定できます。一部の置換は、コードまたはエンコーディング関数として機能します。さて、どこ、。このような文字ごとのコーディングは、基本コードのセットとして示されます。アルファベット順のエンコーディングは、メッセージの任意のセットに使用できます。したがって、アルファベットのエンコードは最も単純で、空でないアルファベットでいつでも入力できます。。多くの文字コード

例アルファベットA =（0、1、2、3、4、5、6、7、8、9）B =（0、1）が与えられているとします。次に、コーディングテーブルを置換することができます。これはBCDエンコーディングであり、1対1であるため、デコード可能です。ただし、スキーマは1対1ではありません。たとえば、6つの111111のセットは、単語333と77の両方、および111111、137、3311、または7111に加えて任意の順列に一致する可能性があります。ある文字の基本コードが別の文字の基本コードのプレフィックスでない場合、アルファベットのコーディングスキームはプレフィックスと呼ばれます。アルファベットのコーディングスキームは、基本コードで構成される単語が独自の方法で基本コードに分解される場合に分離可能であると言われます。分離可能なスキームを使用したアルファベット順のエンコードにより、デコードが可能になります。プレフィックススキームが分離可能であることを証明できます。アルファベットのコーディングスキームを分離可能にするには、基本コードの長さがマクミランの不等式として知られる関係を満たす必要があります。マクミランの不等式アルファベットのコーディングスキームの場合

が分離可能である場合、次の不等式が成り立ちます。文字aの基本コードは、文字bの基本コードのプレフィックスです。トピック5.3。最小限の冗長コーディング実際には、メッセージコードをできるだけ短くすることが重要です。アルファベットのコーディングはどのメッセージにも適していますが、アルファベットAのすべての単語のセットについて何も知られていない場合、最適化問題を正確に定式化することは困難です。ただし、実際には、追加情報が利用できることがよくあります。たとえば、自然言語で表示されるメッセージの場合、そのような追加情報は、メッセージ内の文字の出現の確率分布である可能性があります。次に、最適なコードを構築するという問題により、正確な数学的定式化と厳密な解が得られます。

いくつかの分離可能なアルファベットのコーディングスキームを与えましょう。次に、順序集合が順序集合の順列であるスキームも分離可能になります。この場合、コードの基本セットの長さが等しい場合、スキーム内のそれらの順列は、エンコードされたメッセージの長さに影響を与えません。基本コードの長さが異なる場合、メッセージコードの長さは、どの基本コードがどの文字に対応するか、およびメッセージ内の文字の構成に直接依存します。特定のメッセージと特定のコーディングスキームが与えられると、メッセージコードの長さが最小になるようなコードの順列を選択することが可能です。基本コードを割り当てるためのアルゴリズム。固定メッセージコードSの長さは、固定スキームでは最小になります。۞出現回数の降順で文字を並べ替えます。 ۞基本コードを長さの昇順で並べ替えます。 ۞所定の順序で文字に従ってコードを配置します。メッセージ内のアルファベットと文字の出現確率を指定します。

ここで、piは文字aiの出現確率であり、メッセージに出現する確率がゼロの文字は除外され、文字は出現確率の降順で並べ替えられます。これは、EXAMPLEとして指定および定義されています。分離可能なアルファベットのコーディングスキームA =（a、b）、B =（0,1）の場合、確率分布ではコーディングコストは、確率分布ではコーディングコストは次のようになります。

トピック5.4。ハフマン符号化このアルゴリズムは、1952年にDavidHuffmanによって発明されました。トピック5.5。算術符号化ハフマンアルゴリズムと同様に、すべては元素の表と対応する確率から始まります。入力アルファベットがa1、a2、a3の3つの要素のみで構成され、同時にP（a1）= 1/2 P（a2）= 1/3 P（a3）= 1/6であるとします。シーケンスa1、a1、a2、a3をエンコードします。区間を分割してみましょう。ここで、pは固定数0です。<р<(r1)/2r, а "мощностная" граница где Tr(p)=p logr(p/(r 1))(1р)logr(l p), существенно улучшена. Имеется предположение, чт о верхняя граница полученная методом случайного выбора кода, является асимптотически точной, т. е. Ir(п,[ рп])~пТ r(2р).Доказательство или опровержение этого предположения одна из центральны х задач теории кодирования. Большинство конструкций помехоустойчивых кодов являются эффективными, когда длин а пкода достаточновелика. В связи с этим особое значение приобретают вопросы, связанны е со сложностью устройств,осуществляющих кодирование и декодирование (кодера и деко дера). Ограничения на допустимый типдекодера или его сложность могут приводить к увел ичению избыточности, необходимой для обеспечениязаданной помехоустойчивости. Напр., минимальная избыточность кода в В n 2, для крого существует декодер,состоящий из регист

raシフトと1つの多数決要素、および1つのエラーの修正には、次数があります（（2）と比較してください）。数学としてエンコーダーとデコーダーのモデルは通常、機能要素の回路から考慮され、複雑さは回路内の要素の数として理解されます。既知のクラスのエラー訂正コードについて、K。とD.の可能なアルゴリズムについて調査が行われ、エンコーダーとデコーダーの複雑さの上限が取得されました。コーディングの速度、コーディングのノイズ耐性、およびデコーダーの複雑さの間にもいくつかの関係が見られます（を参照）。符号理論の別の研究の方向性は、多くの結果（たとえば、シャノンの定理と束縛（3））が「建設的」ではなく、（Kn）コードの無限シーケンスの存在に関する定理であるという事実に関連しています。このような（Kn）コードのシーケンスのクラスでこれらの結果を証明するために、努力が払われています。kpの場合、長さlの任意の単語が遅い時間のセットに属することを認識するチューリングマシンが存在します。 lに関する成長の順序（例：llog l）。符号理論で開発された境界を導出するためのいくつかの新しい構造と方法は、一見、符号理論の従来の問題からはかけ離れている質問に大きな進歩をもたらしました。ここで、症状の1つのエラーを修正した最大コードの使用を指摘する必要があります-接触回路によって論理の代数の関数を実現する最適な方法;パッキング密度の上限の根本的な改善等しいボールによるユークリッド空間の再次元化。論理代数の関数の1つのクラスの式によって実装の複雑さを推定する際の不等式（1）の使用について。符号理論のアイデアと結果は、信頼性の低い要素からの自己修正回路と信頼性の高い回路の合成の問題でさらに発展します。点灯：シャノンK.、情報理論とサイバネティックスの研究、トランス。英語から、M.、1963; Berlekamp E.、代数的コーディング理論、トランス。英語から、M.、1971; Peterson、W.、Weldon、E。、エラー訂正コード、trans。英語から、第2版、M.、1976; Discrete Mathematics and Mathematical Questions of Cybernetics、vol。1、M。、1974、section 5; Bassalygo L. A.、Zyablov V. V.、Pinsker M. S.、「情報伝達の問題」、1977年、第13巻、第3号、p。 517; [In] V. M. Sidelnikov、 "Mat。Sat。"、1974、v。95、c。 1、p。 148 58. V.I.レーベンシュタイン。

数学的百科事典。 -M .:ソビエト百科事典。 I.M.ヴィノグラドフ。 1977-1985。 アルファベットコーディングCOEUCLIDANSPACE他の辞書も参照してください。DECODING-コーディングとデコードを参照...数学百科事典オーディオコーディング-この記事は、わかりやすく説明する必要があります。記事のフォーマット規則に従ってフォーマットしてください。 PCを使用したサウンドコーディングの基本は、空気の振動を電気の振動に変換するプロセスです...ウィキペディアのコード画像）、定義に従って実行されます。ルール、k ryhnazの全体。暗号K。、... ...哲学百科事典情報のコーディング-メッセージ要素と信号の間の対応を確立し、これらの要素を修正することができます。 Bをメッセージ要素のセット、Aを記号付きのアルファベット、有限の記号シーケンスを呼び出すとします。一言で言えば......物理百科事典最適なコーディング-（工学心理学）（最適なコーディング）人間のオペレーターによって制御されるオブジェクトに関する情報の受信と処理の最大速度と信頼性を保証するコードの作成（情報の受信、デコードを参照）。 K. o。の問題......大きな心理学百科事典DECODING（工学心理学）-（英語の解読）人間のオペレーターが情報を受け取るプロセスの最終操作であり、特徴的なパラメーターの再暗号化で構成されます。制御オブジェクトの状態、およびそれらを制御オブジェクトのイメージに変換します（コーディングを参照してください......偉大な心理百科事典

デコード-送受信された信号によってエンコードされたメッセージの復元（コーディングを参照）...経済学と数学の辞書コーディング-コーディング。音声生成の段階の1つである「デコード」は、音声メッセージを理解するプロセスである受信と解釈です。心理言語学を参照してください...方法論の用語と概念の新しい辞書（言語教育の理論と実践）コーディング-（英語のコーディング）。 1.あるエネルギー形式から別のエネルギー形式への信号の変換。2。信号または記号の1つのシステムから別のシステムへの変換。これは、「トランスコーディング」、「コード変更」（音声の場合は「翻訳」）とも呼ばれます。 3. K.（ニーモニック）... ...大きな心理百科事典デコード-この記事は情報理論のコードに関するものです。この単語の他の意味については、コード（曖昧さ回避）を参照してください。コードは、特定の各メッセージを、厳密に定義された記号（文字）（または信号）の組み合わせに一致させるための規則（アルゴリズム）です。コードとも呼ばれます......最適なエンコード同じメッセージをさまざまな方法でエンコードできます。最適にエンコードされたコードは、メッセージの送信に最小限の時間が費やされるコードです。各基本文字（0または1）の送信に同じ時間がかかる場合、最適なコードは可能な限り最小の長さのコードになります。例1.確率分布を持つ8つの状態を持つ確率変数X（x1、x2、x3、x4、x5、x6、x7、x8）があるとします。均一なバイナリコードで8文字のアルファベットをエンコードするには、3つ必要です。文字：この000、001、010、011、100、101、110、111このコードが適切かどうかを判断するには、最適値と比較する、つまりエントロピーを決定する必要があります。

式L = 1H / H0 = 12.75 / 3 = 0.084によって冗長性Lを決定すると、コード長を8.4％短縮できることがわかります。問題が発生します。平均して、1文字あたりの基本文字が少なくなるコードを作成することは可能ですか。そのようなコードが存在します。これらはShannonFanoおよびHuffmanコードです。最適なコードを構築する原則：1。各基本文字は、最大量の情報を伝達する必要があります。このため、エンコードされたテキストの基本文字（0と1）は平均して同じ頻度で出現する必要があります。この場合のエントロピーは最大になります。 2.確率の高い一次アルファベットの文字には、二次アルファベットの短いコード語を割り当てる必要があります。

さまざまな情報源とその送信チャネルを分析するには、メッセージに含まれ、信号によって運ばれる情報の量を推定できる定量的な測定が必要です。このような措置は、1946年にアメリカの科学者C.シャノンによって導入されました。

さらに、情報源が離散的であると仮定し、一連の基本メッセージ（i、）を出力します。各メッセージは、離散的アンサンブル（アルファベット）a、a 2、...、dAから選択されます。に情報源のアルファベットの音量です。

各基本メッセージには、問題の情報ソースの状態に関する一連の情報（検討中の例）として特定の情報が含まれています。この情報の測定値を定量化するために、そのセマンティックコンテンツ、および受信者にとってのこの情報の重要度は重要ではありません。メッセージを受信する前に、受信者は私がどのメッセージであるかについて常に不確実であることに注意してください。可能な限りの中で彼に与えられます。この不確実性は、メッセージi、の送信の事前確率P（i、）を使用して推定されます。個別のソースの基本メッセージに含まれる情報の客観的な定量的尺度は、特定のメッセージを選択する確率によって設定され、この確率の関数としてccを決定すると結論付けます。同じ関数は、情報の受信者が個別のソースの状態に関して持つ不確実性の程度を特徴づけます。期待される情報に関する不確実性の程度が、情報伝送チャネルの要件を決定すると結論付けることができます。

一般的に、確率 P（a、）いくつかの基本メッセージiのソースの選択（以下、これをシンボルと呼びます）は、前に選択したシンボルに依存します。は条件付き確率であり、そのような選択の事前確率とは一致しません。

ティムその^ P（a:) = 1、すべてのiがイベントの完全なグループを形成するため

gyi）、およびこれらの記号の選択は、いくつかの関数従属性を使用して実行されます J（a、）= P（a、）= 1、ソースによるシンボルの選択が事前に決定されている場合、 J（a、）= a„ a P（a t、a）-そのような選択の確率、シンボルのペアに含まれる情報の量は、シンボルiとiのそれぞれに含まれる情報の量の合計に等しくなります。情報の定量的尺度のこの特性は、加法性と呼ばれます。

私たちは、と信じています P（a、）-前のすべての文字の後に文字iを選択する条件付き確率、および P（a、、i、）は、シンボルiを選択する条件付き確率です。私の後、そしてすべての前のもの、しかし、それを考えると P（a 1、a 1）\ u003d P（a） P（i、| i y）、加法性条件を書くことができます

表記を紹介します P（a） = P p P（ar）\ u003d Qおよび書き換え条件（5.1）：

私たちは、と信じています R、O* 0.式（5.2）を使用して、関数（p （R）。微分することにより、乗算する R * 0とは RO = R、書き留める

関係（5.3）は、 R f O u ^^ O。ただし、この要件により、（5.3）の右側と左側が一定になります。 Pq> "（P）= Ar "（/？） - に - const。次に、方程式に到達します Pc> "（P） = に統合後、

書き直すことを考慮に入れましょう

その結果、J（a、）の特性に関する2つの条件が満たされると、関数従属性の形式が判明しました。 J（a、）シンボルを選択する確率についてで一定の係数までに一意に定義

係数にスケールのみに影響し、情報量を測定するための単位系を決定します。 ln [P]以降 F 0の場合、選択するのは理にかなっています 情報量の測定ができるようにOsに J（a）ポジティブでした。

受け入れた K =-1、書き留める

したがって、情報量の単位は、イベントが発生した情報に等しく、その確率は次のようになります。 自分。このような情報量の単位は自然単位と呼ばれます。多くの場合、に=-、次に

したがって、2つの同じように発生する可能性のあるイベントの1つに関するメッセージを含み、「ビット」と呼ばれる情報量のバイナリ単位に到達しました。このユニットは、通信技術でバイナリコードを使用しているために普及しています。一般的な場合の対数の底を選択すると、次のようになります。

ここで、対数は任意の基数にすることができます。

情報の定量的尺度の加法性により、式（5.9）に基づいて、一連の記号で構成されるメッセージ内の情報量を決定できます。ソースがそのようなシーケンスを選択する確率は、以前に利用可能なすべてのメッセージを考慮に入れて考慮されます。

基本メッセージに含まれる情報の定量的測定a（、情報の平均量のアイデアを与えません J（A）1つの基本メッセージが選択されたときにソースによって発行されます a d

情報の平均量は、情報源全体の特徴であり、通信システムの最も重要な特徴の1つです。

アルファベットを使用して、独立したメッセージの個別のソースに対してこの特性を定義しましょう。に。で表す オンザ）文字ごとの情報の平均量であり、確率変数Lの数学的な期待値です-ランダムに選択された文字に含まれる情報の量 a

シンボルごとの情報の平均量は、独立したメッセージのソースのエントロピーと呼ばれます。エントロピーは、次の文字を選択する際の平均的な先験的不確実性の指標です。

式（5.10）から、確率の1つが P（a）が1に等しい（したがって、他のすべてがゼロに等しい）場合、情報ソースのエントロピーはゼロに等しくなります-メッセージは完全に定義されます。

可能なすべてのシンボルの事前確率が等しい場合、エントロピーは最大になりますに、つまり R（a（） = 1 /に、それから

ソースが確率Pのバイナリシンボルを独立して選択する場合、= P（a x）およびP2 \ u003d 1-Pの場合、文字ごとのエントロピーは次のようになります。

イチジクに 16.1は、バイナリソースのエントロピーが2つのバイナリシンボルから選択する事前確率に依存していることを示しています。この図は、エントロピーがR、=で最大であることも示しています。 R 2 = 0,5

1 o 1dvd-およびバイナリ単位でlog2 2 = 1-

米。 5.1。でのエントロピー依存性 K =それらの1つを選択する確率について2

シンボルの選択が同等であるが、アルファベットのサイズが異なるソースのエントロピーに、成長とともに対数的に増加しますに。

シンボルを選択する確率が異なる場合、ソースのエントロピーは低下します I（A）可能な最大値に対して H（A）psh =ログに。

シンボル間の相関が大きいほど、後続のシンボルを選択する自由度が低くなり、新しく選択されたシンボルの情報が少なくなります。これは、条件付き分布の不確実性が無条件分布のエントロピーを超えることができないという事実によるものです。ソースのエントロピーをメモリとアルファベットで示しますに横切って H（AA "）、そして、メモリのないソースのエントロピーですが、同じアルファベットで-から オンザ）不平等を証明します

表記法を導入することにより P（aa "）記号a、（/を選択する条件付き確率の場合 = 1, 2, に）シンボルが以前に選択されていると仮定します ajij =1,2,に）変換を省略して、証明なしで書きます

これは不等式を証明します（5.13）。

（5.13）または（5.14）の等式は、次の場合に達成されます。

これは、シンボルを選択する条件付き確率が、シンボルを選択する無条件の確率と等しいことを意味します。これは、メモリのないソースでのみ可能です。

興味深いことに、ロシア語のテキストのエントロピーは1文字あたり1.5バイナリ単位です。同時に、同じアルファベットで K =独立した等確率のシンボルの条件で32 H（A）tp = 1文字あたり5つのバイナリ。したがって、内部リンクの存在により、エントロピーが約3.3分の1に減少しました。

ディスクリートソースの重要な特性は、その冗長性pと次のとおりです。

情報源の冗長性は、内の無次元量です。当然、冗長性がない場合はp u = 0です。

すべてのシンボルの確率が等しい、シンボル間に相関関係がないソースから一定量の情報を送信するには、送信されるシンボルの最小数/ 7分：/ r 0（/ 7 0 R（L max））必要とされている。エントロピーを使用してソースから同じ量の情報を送信するには（シンボルは相互接続されており、確率が等しくない）、平均数のシンボルが必要です。 n = n„ H（A）m JH（A）。

ディスクリートソースは、パフォーマンスによっても特徴付けられます。パフォーマンスは、単位時間あたりのシンボル数vHによって決定されます。

パフォーマンスの場合 I（A）バイナリ単位で定義し、時間を秒で定義し、次に オンザ）- 1秒あたりのバイナリユニットの数です。十分に長い長さ/？の静止文字シーケンスを生成する離散ソースの場合、次の概念が導入されます。ソース文字の典型的および非典型的なシーケンス。すべての長さのシーケンスが含まれます。 P。すべての典型的なシーケンス NlMl（A）ソースで P-»ooの発生確率はほぼ同じです

すべての非定型シーケンスの発生の合計確率はゼロになる傾向があります。平等（5.11）に従って、典型的なシーケンスの確率を仮定します / N rm（A）、ソースのエントロピーはlogNTIin（、4）であり、

ノイズのあるディスクリートチャネルを介した情報伝送の量と速度を考慮してください。以前は、文字（i、）のシーケンスの形式で個別のソースによって生成された情報を検討していました。

ここで、ソース情報がエンコードされ、一連のコードシンボルを表すとします。 （b、 (/ = 1,2、.. T-コードベース）は、一連のシンボルが出力される個別の情報伝送チャネルと一致しています。

エンコード操作は1対1であると想定しています-文字のシーケンスによって （b、）シーケンス（i、）を一意に復元できます。コードシンボルにより、ソース情報を完全に復元することができます。

ただし、エスケープ文字を考慮すると|?。 jと入力記号（/>、）の場合、情報伝送チャネルに干渉があるため、回復できません。出力シーケンスのエントロピー//（/？）

入力シーケンスのエントロピーよりも大きい場合があります H（B）が、受信者の情報量は増加しませんでした。

最良の場合、入力と出力の1対1の関係が可能であり、有用な情報が失われることはありません。最悪の場合、情報伝送チャネルの出力シンボルからの入力シンボルについては何も言えません。有用な情報はチャネルで完全に失われます。

ノイズの多いチャネルでの情報の損失と、ノイズの多いチャネルを介して送信される情報の量を見積もりましょう。送信された文字6で受信された場合、文字は正しく送信されたと見なします。

シンボル bj同じ番号（/ = j）。次に、ノイズのない理想的なチャネルの場合、次のように記述します。

記号による bj-不等式によるチャネル出力で（5.21）

不確実性は避けられません。シンボル内の情報は b i完全には送信されず、干渉のためにその一部がチャネルで失われます。情報の定量的測定の概念に基づいて、シンボルftを受信した後にチャネルの出力で発生する不確実性の数値表現を想定します。：

そしてそれは送信の間にチャネルで失われた情報の量を決定します。

固定フィート。可能なすべてのシンボルの平均（5.22）を計算すると、合計が得られます。

これは、シンボルを受信するときにメモリのないチャネルを介して基本シンボルを送信するときにチャネルで失われる情報の量を決定します bj（t）。

すべてのフィートにわたって合計（5.23）を平均すると、値Z？）が得られます。これは、次のように表されます。 n（in / in-これは、メモリレスチャネルを介して1文字を送信するときに失われる情報の量を決定します。

どこ P ^ bjbjj-送信されたときに発生するイベントの同時確率

シンボル b。それはシンボルを取ります b t。

H [w /情報源の特性に依存します

チャネル入力 Vそして、通信チャネルの確率的特性について。統計通信理論のシャノンによると n（in / inチャネルの信頼性の欠如と呼ばれます。

条件付きエントロピー HB / B、離散ソースのエントロピー

チャネル入力で H（W）とエントロピー AND ^ B）その出力ですることはできません

ネガティブ。干渉のないチャネルでは、チャネルの信頼性が低くなります

n（v / v = 0.（5.20）に従って、次のことに注意してください。 H ^ v / v ^

平等は、チャネルの入力と出力が統計的に独立している場合にのみ発生します。

出力シンボルは入力シンボルに依存しません-壊れたチャネルまたは非常に強い干渉の場合。

前と同じように、典型的なシーケンスについては、次のように書くことができます。

干渉がない場合、その信頼性は低いと言えます

チャネルを介して平均して送信される情報の下で J [b /シンボルごとに、チャネル入力での情報量の違いを理解します J（B）および/？チャネルで失われた情報）。

情報源とチャネルにメモリがない場合は、

式（5.27）は、チャネルの出力シンボルのエントロピーを決定します。チャネルの出力にある情報の一部は有用であり、残りはチャネル内の干渉によって生成されるため、誤りです。そのことに注意しましょう n [v / 2？）は、チャネル内の干渉に関する情報、および差i（d）-I（d / d）-チャネルを通過した有用な情報を表します。

チャネルの出力で形成されるシーケンスの大部分は非定型であり、合計確率が非常に小さいことに注意してください。

原則として、最も一般的なタイプの干渉、つまり加法性ノイズが考慮されます。 N（t）;チャネルの出力での信号の形式は次のとおりです。

離散信号の場合、（5.28）に続く等価ノイズは離散構造になります。ノイズは、入力信号と出力信号のシーケンスに似た、離散的なランダムシーケンスです。離散チャネルの加法性ノイズのアルファベットの記号をC1 = 0、1,2、 T- 1）。そのようなチャネルの条件付き遷移確率

なぜなら AND（^ B/？）そして（B）その結果、入力に対する離散チャネル＃（/）の出力シーケンスの情報 B（t）またはその逆 そして（B）-H ^ in / in）（5）。

つまり、チャネルを介して送信される情報は、入力の情報を超えることはできません。

チャネル入力が平均を受け取った場合 Xのk 1秒間にシンボルを表示すると、ノイズのあるチャネルでの平均情報転送速度を決定できます。

どこ Н（В）= V k J（B、B ^-チャネル入力でのソースパフォーマンス。 n（in / in）\ u003d Uからn（in、in）〜単位時間あたりのチャネルの信頼性の低さ。 H（B）= V k H ^ B ^-チャネルの出力によって形成されるソースのパフォーマンス（有用な情報の一部と誤った情報の一部を提供する）。 H ^ in / B ^ \ u003d U to 1 /（in / in）-虚偽の情報の量、

単位時間あたりにチャネルに干渉が発生しました。

チャネルを介した情報送信の量と速度の概念は、通信チャネルのさまざまなセクションに適用できます。これは「エンコーダ入力-デコーダ出力」セクションである可能性があります。

検討中のチャネルのセクションを拡張することにより、その構成部品の速度を超えることは不可能であることに注意してください。不可逆的な変換は、情報の損失につながります。不可逆的な変換には、干渉の影響だけでなく、検出、冗長性のあるコードによるデコードも含まれます。受信損失を減らす方法があります。これが「レセプション全般」です。

離散チャネルの帯域幅と最適なコーディング定理を検討してください。シャノンは、入力信号のアンサンブルに対するいくつかの制限の下で、既知のプロパティ（ノイズ）を持つチャネル上で可能な最大の情報転送速度を決定する特性を導入しました。これはチャネルCの帯域幅です。ディスクリートチャネルの場合

最大値は可能な入力ソースによって保護されています V与えられた Vkと入力文字のアルファベットの音量 T。

ディスクリートチャネルのスループットの定義に基づいて、次のように記述します。

独立した入力と出力（チャネルのノイズレベルが高い）でC = 0であることに注意してください。したがって、

信号に干渉干渉がない場合。

メモリのない2元対称通信路の場合

米。 5.2。

バイナリチャネルの容量のパラメータ依存性のグラフ R図に示す 5.2。で R= 1/2チャネル帯域幅 C = 0、条件付きエントロピー

//（/？//？）= 1。実用的な関心

グラフは0で表されます

最適なコーディングに関するシャノンの基本的な定理は、容量の概念に関連しています。ディスクリートチャネルの定式化は次のとおりです。メッセージソースのパフォーマンスが オンザ）チャネルCの帯域幅未満：

最適なコーディングとデコードの方法があり、その下では、チャネルのエラーまたは信頼性の欠如の確率があります。 n [a！Ajは任意に小さくすることができます。もしも

そのような方法はありません。

シャノンの定理に従って、有限値とチャネル上でのエラーのない情報転送速度の限界値です。ただし、ノイズの多いチャネルの場合、最適なコードを見つける方法は示されていません。しかし、この定理は、情報伝送技術の基本的な可能性に関する見方を根本的に変えました。シャノン以前は、ノイズの多いチャネルでは、情報転送速度をゼロにすることで、任意の小さなエラー確率を得ることができると考えられていました。これは、たとえば、メモリレスチャネルでの文字の繰り返しの結果としての通信忠実度の向上です。

シャノンの定理のいくつかの厳密な証明が知られています。この定理は、ランダムコーディングによって離散メモリレスチャネルに対して証明されました。この場合、特定のソースおよび特定のチャネルに対してランダムに選択されたすべてのコードのセットが考慮され、すべてのコードにわたる誤ったデコードの平均確率のゼロへの漸近的アプローチの事実が、メッセージシーケンス。したがって、エラーのない復号化の可能性を提供するコードの存在の事実のみが証明され、明確な符号化方法は提案されていない。同時に、証明の過程で、メッセージシーケンスのアンサンブルと送信に使用される1対1の対応するコードワードのセットのエントロピーの同等性を維持しながら、アンサンブルが明らかになります。 Vコードシンボルのシーケンスの相互依存性を高めるために、追加の冗長性を導入する必要があります。これは、コードワードが選択されるコードシーケンスのセットを拡張することによってのみ実行できます。

ノイズの多いチャネルの主なコーディング定理は、特定のコードを選択する明確な方法を示しておらず、定理の証明にも存在しないという事実にもかかわらず、十分に長いメッセージをエンコードする場合、ランダムに選択されたコードのほとんどが示されます。シーケンスは、誤ったデコードの平均確率をわずかに超えています。しかし、メモリシステムの実装や膨大な数のコード要素のシーケンスの論理処理の難しさ、および情報の送信と処理の遅延の増加により、長いブロックでのコーディングの実際的な可能性は限られています。実際、特に興味深いのは、期間の有限値の誤ったデコードの確率を決定することを可能にする結果です P使用されたコードブロック。実際には、それらは中程度の遅延値に制限されており、チャネル帯域幅の不完全な使用で送信確率の増加を達成します。

いつ、そしてなぜ符号理論が生まれたのか。 コーディングの理論。 コーディングの種類。 コーディング。 基本概念