符号理論

ウィキペディア

符号理論

出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2025/06/20 06:42 UTC 版)

ハミング距離を2次元で視覚化した図

符号理論（ふごうりろん、英: Coding theory）は、情報を符号化して、通信を行う際の効率と信頼性についての情報学基礎論である。符号は、データ圧縮・暗号化・誤り訂正・ネットワーキングのために使用される。符号理論は、効率的で信頼できるデータ伝送方法を設計するために、情報理論・情報科学・数学・言語学・計算機科学・遺伝学などの様々な分野で研究されている。関係する純粋数学の分野としてグラフ理論等の離散数学、有限体理論を中心とした代数学、表現論が挙げられる。また、近年は量子もつれを加味した量子符号の原理について工学（ここでは専ら復号アルゴリズムの記述を意味する）および数学の観点から活発に研究されている。通常、符号理論には、情報源符号化定理を背景とする冗長性の除去の方法論と、冗長性を付与した上での送信されたデータの誤りの検出・訂正を研究対象とする、通信路符号化定理により存在を保証された性能の良い符号構成を目的とする誤り訂正符号理論が含まれる。BCH符号・Reed-Solomon符号やLDPC符号による符号化が産業活用の面では主流である一方で、有限射影幾何学および代数幾何学や計算量理論との関わりやNAND型フラッシュメモリ、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自体である。携帯電話も高周波転送におけるノイズや減衰による誤りを検出訂正する技術を使っている。一般にデジタル信号による通信には、必ず何らかの誤り検出訂正技術が使われている。

符号理論の歴史

1948年、クロード・シャノンは論文「通信の数学的理論」を、Bell System Technical Journalの7月号と10月号の2つの記事で発表した。この論文は、送信者が送信したい情報を最適に符号化する方法の問題に焦点を当てている。この論文では、ノーバート・ウィーナーが開発した確率論を使用した。当時、確率論は通信理論にはほとんど適用されていなかった。シャノンは、メッセージの不確実性の尺度として情報エントロピーを開発し、情報理論の分野を本質的に創始した。

1949年に二元ゴレイ符号が開発された。これは、24ビットワードごとに最大3つの誤りを訂正し、4つ目を検出することができる誤り訂正符号である。

1968年、リチャード・ハミングは、ベル研究所在籍中の成果である数値計算方法、自動符号化システム、誤り検出訂正符号でチューリング賞を受賞した。彼は、ハミング符号、ハミング窓、ハミング数、ハミング距離という概念を発明した。また符号を構成するために、誤りを定義する距離概念としてリー距離、ウラム距離などが考案されている。

情報源符号化

情報源符号化の目的は、情報源におけるデータをより小さくすることである。

定義

データは確率変数 $X:\Omega \rightarrow {\mathcal {X}}$ ウィキメディア・コモンズには、符号理論に関するメディアがあります。

• 情報理論
• 符号化方式
• 誤り検出訂正
• データ圧縮

参考文献

• Elwyn R. Berlekamp (2014), Algebraic Coding Theory, World Scientific Publishing (revised edition), ISBN 978-9-81463-589-9.
• MacKay, David J. C.. Information Theory, Inference, and Learning Algorithms Cambridge: Cambridge University Press, 2003. ISBN 0-521-64298-1
• Vera Pless (1982), Introduction to the Theory of Error-Correcting Codes, John Wiley & Sons, Inc., ISBN 0-471-08684-3.
• Randy Yates, A Coding Theory Tutorial.
• 今井秀樹：「符号理論」、電子通信情報学会、ISBN 978-4-88552090-7（1990年3月）。
• 植松友彦：「現代シャノン理論：タイプによる情報理論」、培風館、ISBN 4-563-01522-9（1998年7月21日）.
• J.ユステセン, T.ホーホルト：「誤り訂正符号入門」、森北出版、ISBN 978-4627817111（2005年10月11日）。
• 植松友彦：「代数系と符号理論」、オーム社、ISBN 978-4-274-50274-3 (2010年4月10日).
• 坂庭好一、渋谷智治：「代数系と符号理論入門」、コロナ社、ISBN 978-4-339-02446-3 (2010年4月30日).
• 和田山正：「誤り訂正技術の基礎」、森北出版、ISBN978-4-627-81731-9 (2010年7月6日）．
• 西村芳一：「［改訂新版］データの符号化技術と誤り訂正の基盤」、CQ出版、ISBN 978-4-7898-4640-0 (2010年8月1日)．
• 先名健一：「例題で学ぶ符号理論入門」、森北出版、ISBN 978-4-627-81741-8（2011年7月）。
• 萩原学：「符号理論：デジタルコミュニケーションにおける数学」、日本評論社、ISBN 978-4-535-78664-6 (2012年8月10日）．
• Henning Stichtenoth、新妻 弘（訳）：「代数関数体と符号理論」、共立出版、ISBN 978-4-320-11045-8（2013年8月25日）。
• 楫勇一(編著）：「情報・符号理論」、オーム社、ISBN 978-4-274-21317-5（2013年10月）。
• 萩原学(編著)：「進化する符号理論」、日本評論社、ISBN 978-4-535-78797-1（2016年9月9日）。
• 桂利行：「符号理論の数理」、東京大学出版会、ISBN 978-4-13-061319-4 (2025年5月26日)。