必須コーディング理論 [pdf]

 (cse.buffalo.edu)
16 ポイント 投稿者 GN⁺ 2025-08-31 | 1件のコメント | WhatsAppで共有
  • この本はコーディング理論の中核概念と現代的な発展を包括的に整理している
  • 誤り訂正符号の基本原理、多様な符号の構造と限界、そして実際の応用分野を扱う
  • Shannon理論とHamming符号をはじめ、Reed-Solomon など現実で広く使われている符号を重点的に説明している
  • ハッシュ、集団検査、生体情報保護など、最新のITシステムにおける応用事例も体系的に提供している
  • 各付録、演習問題、参考文献まで含め、学習者と実務者の双方に有効な参考書として構成されている

序文

  • この本は Venkatesan Guruswami、Atri Rudra、Madhu Sudan のコーディング理論講義ノートに基づいている
  • University of Washington、CMU、University at Buffalo SUNY、Harvard、MIT などで行われた講義内容をもとにしている
  • NSF CAREER grant CCF-0844796 の支援を受けている
  • 著者らの見解と結果は NSF の公式見解を意味しない
  • Creative Commons Attribution-NonCommercial-NoDerivs 3.0 Unported License で利用できる

目次の要約

第1章: 根本的な問い

  • コーディング理論の目的、基本定義と符号
  • 誤り訂正と符号の距離概念、Hamming符号と境界
  • 符号族の分類と演習問題、参考文献を含む

第I部: 基礎

  • 線形符号、有限体、ベクトル空間など数学的構造の導入
  • Hamming符号の効率的な復号と双対符号の説明
  • 演習問題および参考文献を含む

第3章: 確率および q-ary エントロピー関数

  • 確率論の基礎、確率的方法、q-ary エントロピー関数の理解
  • 関連する演習問題と参考文献を提供

第II部: 組合せ論

  • Hamming、Gilbert-Varshamov、Singleton、Plotkin など符号境界と限界を説明
  • Reed-Solomon 符号、多項式と有限体の応用
  • Shannon の雑音モデルと情報伝送の限界、Hamming との比較
  • リスト復号、Johnson Bound、リスト復号容量などへの拡張
  • Elias-Bassalygo、線形計画法境界など新たな限界理論

第III部: 多様な符号構造

  • 多項式ベースの符号とバイナリ体への適用、一般的な符号構造
  • 符号連接(concatenation)、Zyablov Bound、高度な連接手法および要約
  • Expander グラフと Expander 符号、距離増幅および応用事例

第IV部: アルゴリズム

  • Reed-Solomon、Reed-Muller、連接符号の効率的な復号方法
  • BSCp チャネル容量の達成方法と内部/外部符号構造
  • Polar 符号、Polarization の原理およびエンコーダ/デコーダ実装、リスト復号能力
  • 線形時間エンコーディングおよびローカル復旧可能な符号の説明

第V部: 応用

  • ハッシュ理論と衝突回避、ほぼユニバーサルなハッシュ関数、データ所有証明
  • 生体認証（指紋）保護のための Fuzzy Vault の概念
  • 集団検査(Group Testing)の定式化、境界およびデータストリームアルゴリズムへの応用
  • コーディング問題の複雑性: 最近接符号語問題、前処理ベースの復号、近似化、最小距離問題など
  • 計算複雑性の関連テーマとして、通信複雑性、乱択化、Pseudorandomness、Hardcore Predicates、平均難易度問題などを扱う

付録

  • 記号表、有用な不等式および等式、漸近記法、アルゴリズムおよび複雑性の基本背景
  • 代数的アルゴリズム、有限体、多項式演算の紹介
  • 情報理論の主要概念: エントロピー、条件付きエントロピー、相互情報量などを整理

特徴と活用価値

  • 現代の情報通信、データ保存、暗号システムなどで不可欠な誤り訂正アルゴリズムについて、理論的背景と実務への適用方法を包括的に提供している
  • 基本概念から最新動向、実際の応用まで整理されており、新人開発者、研究者、IT実務者に幅広い知識を伝える
  • 各章に演習問題と参考文献が含まれており、学習および自律学習に有利である
  • Creative Commons ライセンスに従い、学術的・非商業的目的で自由に活用できる

関連記事

1件のコメント

 
GN⁺ 2025-08-31
Hacker Newsの意見

  • Claude Shannonの"The Mathematical Theory of Communication"は、数学的背景がそれほど深くなくても誰でも読めるほど平易に説明された、情報理論の基本文献であることを強調したい リンク

    • Shannonは、数学的な考え方を始めるうえで本当に最適な人物だと言いたい。彼は情報エントロピーの概念を、当初は特に意味づけせず、ただ必要な性質だけをもとに導いた。驚くべきことに、この偶然生まれた定義は物理学における熱力学的エントロピーとほとんど一致しており、これを指摘して名前を付けたのがVon Neumannだった。数学というのはしばしば「こういう規則を満たさなければならないなら」という論理的展開へと進んでいくので、多くの人が難しく感じる理由の一つでもある。Shannonの論文はコーディング理論の骨格を作ったにすぎず、実際の実装は論文には書かれていない。私は以前、スタートアップでこの論文の書籍版を一緒に読む読書会を運営していたことがあり、情報理論と数学全般を理解するうえで本当に良い経験だったので勧めたい

  • 可逆圧縮の分野は生成AIと密接に関係しているので、さらに内容を加えると面白いはずだ。可逆圧縮と機械学習のつながりをうまく紹介した博士論文を勧めたい リンク

    • これを必ずしも可逆圧縮だけに限定する必要はない。実際、ほぼすべての機械学習は一種の圧縮、主に非可逆圧縮として理解できる。たとえば意味埋め込みだけをチャネル経由で送れば、実際の原文全体がなくても、埋め込み値の中に十分な情報が含まれているので処理が可能だ。データ分類も結局は、データから一般的なカテゴリの潜在表現だけを残して、それ以外を捨てる過程だ。生成AIの場合、私たちが「非可逆圧縮」をしているからこそ、むしろうまく動く。情報をあえて捨て、その隙間を推論しなければ一般化への道が開かれない。可逆なLLMは、実際の用途ではさほど面白いものにはならない。ただし、勧めた論文は機械学習分野でも珍しく可逆圧縮を扱っているので非常に特別だ

  • 最近作られた良い資料として、<i>Information Theory: From Coding to Learning</i>という教科書がある。オンラインPDF版もあるので参考になると思う リンク

    • David MacKayの<i>Information Theory, Inference, and Learning Algorithms</i>も勧めたい リンク

  • 「コーディング」がどういう意味なのかという質問に答えるなら、ここでのコーディングは情報をある表現から別の表現へ変換するエンコード／デコードの行為を意味する。このようなシステムをコードと呼び、情報伝達の際に干渉や変調、あるいは盗聴に耐えられるよう設計されている。つまり、コード（coding）はデータ圧縮、暗号化、誤り検出および訂正、データ伝送および保存など多くの分野で使われている リンク

    • 特に言及されている本は誤り訂正符号（error correcting code）に重点を置いている。メッセージを伝える際、失われた部分を復元できるように追加データを付ける。解決すべき難しさは、最小限のオーバーヘッドと妥当な計算時間の範囲内で、十分な誤りを復旧できる追加データを設計することだ。こうした技術はWiFi、ハードドライブ、QRコード、RAMのように非常に幅広い場所で実際に使われている。たとえばECC RAMのECCがまさに誤り訂正符号だ。最近のDDR5では一部必須化されている技術でもある

  • CSの無料電子書籍を共有する流れなので、Jeff E.のAlgorithms本も強く勧めたい。アルゴリズムを学びたい人や実力を復習したい人には必読書だ リンク

  • 私はこの本を数章読んだが、本当に満足している。これから数週間、あるいは数か月かけてゆっくり読み進めるつもりだ

  • 情報理論とコーディング理論をさらに深く学びたいなら、次の資料も勧めたい。誤り訂正符号については"W. Wesley Peterson and E. J. Weldon, Jr.のError-Correcting Codes"、そして抽象代数、とくに体論については"Oscar Zariski and Pierre SamuelのCommutative Algebra"が参考になる

    • LaTeXコマンドはここでは動かない

  • 入門者に勧めたい本を何冊か挙げるなら、

    1. John R. Pierceの<i>An Introduction to Information Theory, Symbols, Signals and Noise</i> - 概念を理解し直感を養うのに良い古典だ。同じ著者のほかの本も素晴らしい
    2. James V. Stoneの<i>Information Theory: A Tutorial Introduction</i> - わかりやすく良い入門書だ。著者のほかのチュートリアルも有益だ
    3. Stefan MoserとPo-ning chenの<i>A Student's Guide to Coding and Information Theory</i> - 簡潔で明快な案内書であり、同じシリーズのほかの本も勧められる

  • 誰かが「これが必須だ」と言うたびに、学科でそのテーマに少し触れたことしかない私としては、いつも少し身構えてしまう

    • この授業科目でいう「必須」とは、すべてのコンピュータサイエンス学生が必ず知るべき内容というより、コーディング理論のエッセンスが詰まっているという意味だ。本の共著者が私たちの大学で実際に講義しており、この講義は数学的内容が圧倒的に多い上級学年向けの選択科目だ。4年制のコンピュータサイエンス課程では主に最終学年のごく少数しか履修せず、私の周囲で受講していた友人たちはみな数学の証明が好きなタイプだった。彼らはこの科目を楽しんでいた

    • 「必須」や「入門」と書かれているときは、とても密度の高い教科書が待っているという予告だ