符号理論

ウィキペディア

符号理論

出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2024/05/25 13:58 UTC 版)

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

ウィキペディア小見出し辞書

符号理論

出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2022/02/14 14:38 UTC 版)

「情報理論」の記事における「符号理論」の解説

詳細は「符号理論」を参照 符号理論は、情報理論の中でも最も重要かつ直接的な応用分野である。その領域は、情報源符号化理論（データ圧縮）と通信路符号化理論（誤り検出訂正）に大別される。データの統計的記述を用いて、符号化に必要とされるビット数（情報源の情報エントロピー）を定量化する。 データ圧縮（情報源符号化）: 圧縮方式は次の2つに分類される:可逆圧縮: データの復元が正確に行われる 非可逆圧縮: 歪関数によって指定された忠実度レベルでデータを再現するために必要なビット数を割り当てる。この情報理論のサブセットをレート歪理論と呼ぶ。 誤り訂正符号（通信路符号化）: データ圧縮によって可能な限り冗長性を排除する一方、誤り訂正符号を付与することで正しい性質の冗長性を導入し、ノイズのある通信路でデータを効率的かつ忠実に転送可能にする。 圧縮と転送に関する符号理論は情報理論に裏打ちされている。ただし、それは1対1の通信に関してのみである。発信者が複数の場合（複数アクセス通信路）、受信者が複数の場合（同報通信路）、仲介者がいる場合（リレー通信路）、それらの複合であるコンピュータネットワークなどについて、転送後の圧縮は最適とは言えないかもしれない。このようなマルチエージェント通信モデルを扱うのはネットワーク情報理論 (Network Information Theory) である。