符号理論
符号理論(ふごうりろん、英: Coding theory)は、情報を符号化して、通信を行う際の効率と信頼性についての情報学基礎論である。符号は、データ圧縮・暗号化・誤り訂正・ネットワーキングのために使用される。符号理論は、効率的で信頼できるデータ伝送方法を設計するために、情報理論・情報科学・数学・言語学・計算機科学・遺伝学などの様々な分野で研究されている。関係する純粋数学の分野としてグラフ理論等の離散数学、有限体理論を中心とした代数学、表現論が挙げられる。また、近年は量子もつれを加味した量子符号の原理について工学(ここでは専ら復号アルゴリズムの記述を意味する)および数学の観点から活発に研究されている。通常、符号理論には、情報源符号化定理を背景とする冗長性の除去の方法論と、冗長性を付与した上での送信されたデータの誤りの検出・訂正を研究対象とする、通信路符号化定理により存在を保証された性能の良い符号構成を目的とする誤り訂正符号理論が含まれる。BCH符号・Reed-Solomon符号やLDPC符号による符号化が産業活用の面では主流である一方で、有限射影幾何学および代数幾何学や計算量理論との関わりやDNAストレージ、不揮発性レーストラックメモリの数学解析への応用も認められている学際的な分野である。
1948年、クロード・シャノンは論文「通信の数学的理論」を、Bell System Technical Journalの7月号と10月号の2つの記事で発表した。この論文は、送信者が送信したい情報を最適に符号化する方法の問題に焦点を当てている。この論文では、ノーバート・ウィーナーが開発した確率論を使用した。当時、確率論は通信理論にはほとんど適用されていなかった。シャノンは、メッセージの不確実性の尺度として情報エントロピーを開発し、情報理論の分野を本質的に創始した。
1949年に二元ゴレイ符号が開発された。これは、24ビットワードごとに最大3つの誤りを訂正し、4つ目を検出することができる誤り訂正符号である。
1968年、リチャード・ハミングは、ベル研究所在籍中の成果である数値計算方法、自動符号化システム、誤り検出訂正符号でチューリング賞を受賞した。彼は、ハミング符号、ハミング窓、ハミング数(英語版)、ハミング距離という概念を発明した。また符号を構成するために、誤りを定義する距離概念としてリー距離、ウラム距離などが考案されている。
このような単純な繰り返し符号ではあまり効率的ではないが、実際にはもっと効率的な符号を使って情報をインターリーブし、ディスク面の一部に傷があっても誤り訂正できるようにしている。
別の用途にはもっと適した符号が別に存在する。宇宙空間での通信は受信機の熱雑音の影響が大きく、これはCDの傷などとは異なり、連続的なノイズである。電話回線を使ったモデムではノイズがあるために転送速度が制限されるが、それと同様である。携帯電話は減衰が問題となる。高周波では受信機がほんの数センチ動いただけでも減衰により信号が捕らえられなくなる。このような減衰に対処する通信路符号化の技法も存在する。
代数的符号理論(Algebraic coding theory)とは、符号の特性を代数学的に表現し研究する分野である。
代数的符号理論は基本的に以下の2つの符号に分類される。
線型ブロック符号
畳み込み符号
主に符号の以下の特性を分析する。
符号語の長さ
正しい符号語の総数
2つの正しい符号語間の最小ハミング距離