誤り訂正符号入門 (第 2 版)

誤り訂正符号の理論的な基礎をまとめた, 定評のあるテキスト“A Course In Error-Correcting Codes”の改訂版

〈本書の特長〉
■最も基本的な 2 元符号から始めて, リード・ソロモン符号, 巡回符号, 畳込み符号, LDPC 符号などを, 例を交えて解説
■リスト復号や代数幾何符号といった, 実用化が期待される発展的な内容についてもカバー
■基礎事項の確認からプログラミングの課題まで含んだ, 豊富な演習問題

初版発行から約 10 年, 第 2 版ではこの間の進歩を踏まえて内容をアップデートし, さらに構成から全面的に見直して整理したことで, より一層学びやすくなりました.
第 1 章 ブロック誤り訂正符号
第 2 章 有限体
第 3 章 通信路と誤り確率
第 4 章 リード・ソロモン符号とその復号
第 5 章 巡回符号
第 6 章 フレーム
第 7 章 最尤復号と畳込み符号
第 8 章 符号の組合せ
第 9 章 リード・ソロモン符号と BCH 符号の復号
第 10 章 反復的復号
第 11 章 代数幾何符号

付録 A 線形代数のいくつかの結果
付録 B 通信路
付録 C 最小多項式の表
付録 D 問題の解答
付録 E 訳者補遺: 拡張リスト復号と積和アルゴリズム
付録 F 訳者による文献紹介

誤り訂正符号の理論を、最も基本的な 2 元符号から代数幾何符号まで一冊で見通したい人に向けた教科書が『誤り訂正符号入門 (第 2 版)』 (イエルン・ユステセン、トム・ホーホルト原著、阪田 省二郎、栗原 正純、松井 一、藤沢 匡哉 訳、森北出版、2019 年 4 月刊) です。版元の紹介文は、誤り訂正符号の理論的な基礎をまとめた定評のあるテキスト A Course In Error-Correcting Codes の改訂版と位置づけており、NDL の書誌にも原著第 2 版の翻訳と記録されています。通信や記録で生じる誤りを数学の言葉で扱う道筋を、例と演習問題を通して身につけたい読者のための一冊です。

全 11 章の構成、2 元符号から代数幾何符号まで

目次は第 1 章「ブロック誤り訂正符号」から始まり、第 2 章「有限体」と第 3 章「通信路と誤り確率」で道具立てを整えたのち、第 4 章「リード・ソロモン符号とその復号」、第 5 章「巡回符号」、第 6 章「フレーム」へ進みます。続いて第 7 章「最尤復号と畳込み符号」、第 8 章「符号の組合せ」、第 9 章「リード・ソロモン符号と BCH 符号の復号」、第 10 章「反復的復号」と、復号の方法を章題に掲げる章が並び、第 11 章「代数幾何符号」で本文が終わります。巻末には付録 A「線形代数のいくつかの結果」、付録 B「通信路」、付録 C「最小多項式の表」、付録 D「問題の解答」に加え、付録 E「訳者補遺: 拡張リスト復号と積和アルゴリズム」と付録 F「訳者による文献紹介」が収められています。

版元が挙げる特長は 3 点です。2 元符号から始めてリード・ソロモン符号、巡回符号、畳込み符号、LDPC 符号などを例を交えて解説すること、リスト復号や代数幾何符号といった発展的な内容までカバーすること、そして基礎事項の確認からプログラミングの課題まで含んだ演習問題です。第 2 版については、初版発行から約 10 年の進歩を踏まえて内容を更新し、構成から全面的に見直して整理したと案内されています。

有限体と復号アルゴリズムが符号理論の両輪になる理由

誤り訂正符号の出発点は、送りたい情報に冗長な記号を加え、受け取った語が正しい符号語からどれだけ離れているかを測れるようにすることです。符号語どうしの最小距離が大きいほど多くの誤りを見分けられ、最小距離の半分未満の個数の誤りであれば一意に訂正できます。ただし距離の大きな符号を作るだけでは足りず、受信のたびに全部の符号語と比べるような復号は現実の長さの符号では成り立ちません。そこで符号語の集合に代数的な構造を持たせ、その構造を使って速く復号する工夫が要になります。リード・ソロモン符号は有限体の上の多項式を土台にした符号で、記号の単位で誤りを扱うため連続して起きるビットの誤りに強く、CD や QR コードのような記録と読み取りの場面で使われてきました。一方、疎な検査行列を持つ LDPC 符号は、確率的な情報を繰り返し受け渡す反復的な復号によって理論上の限界に近い性能を出せることで知られ、無線通信や衛星放送の規格に採り入れられています。リスト復号は、最小距離の半分を超える誤りに対しても候補の符号語を複数返すことで訂正できる範囲を広げる考え方です。本書の目次には、有限体の章と、復号を題に掲げる章がそろっています。

線形代数を下地に読む理論書、向く読者と向かない読者

付録 A には線形代数の結果がまとめられています。第 3 章で通信路と誤り確率を扱うため、確率の基本的な計算にも慣れていると読み進めやすくなります。演習問題にはプログラミングの課題も含まれるので、式を追うだけでなく、小さな符号器や復号器を自分で書いて結果を確かめる読み方ができます。反対に、特定の通信規格やストレージ製品での実装手順、既存のライブラリの使い方を知りたい人にとっては、目次が規格名ではなく符号の種類と復号の方法で組まれている本書は遠回りになります。

通信、ストレージ、放送などで誤り訂正の仕組みに触れ、手元の符号器や復号器が何をしているのかを原理から説明できるようになりたい技術者や、情報理論を学んだあとに符号理論を体系立てて押さえたい学生に向けて、本書は主要な符号と復号法を一続きに扱う教科書です。訳者 4 名は刊行時のプロフィールで電気通信大学、豊田工業大学、東京理科大学の研究者と紹介されており、付録 E に訳者補遺、付録 F に文献紹介が収められています。