符号理論

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