「誤り訂正技術の基礎」
サンプルページ
この本の定価・判型などは，以下の URL からご覧いただけます．
http://www.morikita.co.jp/books/mid/081731
下記のアドレスにアクセスし，ご確認ください． http://www.morikita.co.jp/support/ ●本書の内容に関するご質問は，森北出版 出版部「（書名を明記）」 係宛に書面にて，もしくは下記のe-mailアドレスまでお願いします． なお，電話でのご質問には応じかねますので，あらかじめご了承く ださい． editor@morikita.co.jp ●本書により得られた情報の使用から生じるいかなる損害について も，当社および本書の著者は責任を負わないものとします． ■本書に記載されている製品名，商標および登録商標は，各権利者 に帰属します． ■本書の無断複写は著作権法上での例外を除き禁じられています． 複写される場合は，そのつど事前に（社）出版者著作権管理機構 （電話 03-3513-6969，FAX 03-3513-6979，e-mail：info@jcopy.or.jp） の許諾を得てください．
i
はじめに
誤り訂正技術は，人目にはつかずにそっと私たちの身の回りで働いている．私たち がリラックスして音楽を聴いているとき，CD プレーヤーは CD 表面の傷のために生 じた誤りを訂正するために，ある種の代数方程式をリアルタイムで解き続けている． 携帯電話の中では，雑音から正しい信号を取り出すために，グラフの最小コストパス を求めるアルゴリズムが四六時中動いている． 最近の身の回りにあるディジタル機器を考えれば，情報の伝送・蓄積を行わない機 器はまずない．近年の携帯電話に代表される無線通信システムの伝送速度は，わずか 10年ほどの間に飛躍的に高速化されてきた．また，ハードディスクなどの大容量記憶 装置の高密度化（単位面積あたりの記録ビット数の増加）も，めざましいペースで進行 中である． 通信・記録のどちらにおいても，高速化，高密度化が進めば進むほど，通信媒体を 通る信号が雑音の中にほとんど埋もれてしまうような状況が生じる．そのような状況 下で高い信頼性を確保するためには，情報の受け手側で雑音の影響を取り除き，送信 者の意図した情報を可能な限り正確に取り出すための技術が必要となる． 大雑把にいってしまうと，誤り訂正技術は，何もしなければ誤って情報を受け取っ てしまう場面で，通信路において生じた誤りを訂正するためのしくみである．送信側 で情報を符号化という操作により冗長を追加したのちに，通信媒体に伝送することに より，受信側で行う送信信号の推定において誤って情報を受け取ってしまう確率（誤 り率）を大幅に下げることが可能となる．騒がしい雑踏のなかで，「これ＿としました よ」と聞こえてきたときに，私たちは言語の冗長性を利用1）して，「これおとしました よ」だと正しく未知の部分を推測することができる．これに似たことを，ディジタル 信号に対して系統的に行うしくみだといまの時点では思っていただいていてもよい． 誤り訂正技術は，代数的な側面と確率的な側面の両方をもつ．たとえば，CD や DVD，ハードディスクにおいて，誤り訂正を担っているリード・ソロモン符号とよ ばれる誤り訂正符号は，有限体と線形代数などの数学に基づいて構成されている．そ の代数的な性質は，代数的な復号法を可能としており，冒頭で述べたように，代数的 な方程式の求解が復号操作の要となる．一方，最近，実用化された衛星放送システム 1）むろん，今の自分のいる状況も加味して推論を行っているものと考えられるDVB-S2においては，LDPC 符号とよばれる非常に疎なグラフに基づく誤り訂正符号 が用いられており，受信器では，数万ノードにもなるグラフ上で，メッセージパッシ ングに基づく確率推論計算が行われている． このような誤り訂正技術の理論体系は符号理論とよばれる．本書は，符号理論の基 礎の解説を目的としており，大きく分けて 2 部に分かれる． 本書の前半部では，2 元線形符号の基礎，有限体，線形符号などを扱う．また，実 用的に重要なリード・ソロモン符号に説明の重点を置く．リード・ソロモン符号は， その性質だけではなく，その代数的構造を利用した代数的復号法のひとつであるピー ターソン復号法について解説する． 後半は，とくに符号理論の確率的な側面に注目する．確率推論としての復号法につ いて概観した後に，ビタビアルゴリズムと sum-product アルゴリズムの原理を学ぶ． sum-productアルゴリズムに関する知識は，符号理論にとどまらず，無線通信，信号 処理，人工知能，確率推論などの諸分野の学習においても有益であると考えている． sum-productアルゴリズムを復号法として利用する LDPC 符号は，リード・ソロモン 符号と並んで，次世代の主力を担う誤り訂正符号である．本書の最後の部分では，通 信路符号化定理について述べる．誤り訂正符号の理論的可能性は，シャノンの打ち立 てた情報理論により数学的に裏付けられている． 本書は網羅的であるよりも，筆者が現代的な符号理論の基礎として重要であると考 えるエッセンスについて，それらがストーリーをもって繋がるよう心がけて執筆を 行った．また図と具体例をふんだんに盛り込み，直感的な理解を助けるように工夫す るとともに，紙幅の許す限り必要な事柄を述べたつもりである． 符号理論の面白さのひとつに，周辺諸分野との繋がりがある．著者は符号理論の研 究を行ってきているが，その過程において，情報理論と通信理論はもとより，確率推 論，動的計画法，コンピュータサイエンスの基礎的なトピックス（ランダマイズドア ルゴリズムや確率的手法），格子理論，組み合わせ最適化，最適化，代数学，統計力学 などのさまざまな情報科学，数学や物理の諸分野に出会う機会を得た．この学際的な 幅広さが符号理論の大きな魅力であるように感じている． 符号理論の分野では，数理的な理論と実用面における工学的応用がきわめて近いと ころに位置するという特徴がある．鋭い数理的センスによって，長年に渡り解決が困 難であった工学的問題が，比較的キャリアの浅い研究者や近隣分野の研究者により見 事に解決されるという例も珍しくない．本書の読者の中から，符号理論の研究に興味 をもつ方が出るとすれば著者として望外の喜びである． 本書の執筆に関して謝辞を述べたい．入門書ということで本書に登場する重要な結 果や概念について，多くの場合，その原論文を参照していない．しかし，本書がそれ
はじめに iii らの先人の努力とひらめきの結晶の上に成り立っている点について，重要な結果を残 した先達へ感謝の意とともに畏敬の意を表したい．本書の編集を担当してくださった 森北出版の水垣偉三夫氏，加藤義之氏には，脱稿が当初の予定よりも大幅に遅れてい るなか根気強く待ってくださるとともに，本書を改良するために有用なコメントの 数々を頂戴した．原稿を通して丁寧に見てくださった名古屋工業大学 和田幸一先生か らは，本書を改良する上で貴重なコメントを頂戴した．福井大学 岩田賢一先生から は，旧原稿の不備について数々の鋭いご指摘をいただいた．千葉大学 中村勝洋先生か らは，励ましとともに旧原稿のいくつかの問題点に関してコメントを頂戴した．名古 屋工業大学大学院 情報工学専攻 八木田将之君，三輪誠君は，本書の校正に手を貸し ていただいた．以上の方々，ならびに本書の原稿にコメントを寄せてくれた学生諸氏 （千葉大学, 名古屋工業大学）に厚くお礼を述べさせていただきたい．なお，本書の内 容に不適切な点が残っているとすれば，無論すべて著者の責任であり，読者からのご 指摘を歓迎したい．最後ではあるが，長期となった本書の執筆をさまざまな面から励 ましてくれた家族（妻と二人の子供たち）に感謝する． 2010年 6 月 和田山 正
目 次
第 1 章 誤り訂正技術のしくみ 1 1.1 符号化に基づく通信 1 1.2 繰り返し符号による誤り訂正 4 1.3 シャノンの符号化定理 10 1.4 誤り訂正符号の必要性 11 演習問題 12 第 2 章 符号化と復号 13 2.1 符号 13 2.2 符号化 15 2.3 復号 16 2.4 実用化されている符号 21 演習問題 23 第 3 章 2 元線形符号の基礎 24 3.1 2元有限体とベクトル空間 24 3.2 2元線形符号 25 3.3 コセットとシンドローム表復号法 32 演習問題 36 第 4 章 いくつかの 2 元線形符号と 2 元線形符号に関する限界式 38 4.1 単一パリティ符号 38 4.2 ハミング符号 39 4.3 リード・マラー符号 42 4.4 符号の限界式 45 演習問題 49 第 5 章 有限体 51 5.1 有限体 51 5.2 拡大体のベキ表現 55 5.3 共役根 57 演習問題 59目 次 v 第 6 章 Fq上で定義される線形符号 60 6.1 線形符号 60 6.2 生成行列と符号化 62 6.3 検査行列 67 6.4 生成行列と検査行列の関係 68 演習問題 70 第 7 章 リード・ソロモン符号（I） 71 7.1 リード・ソロモン符号の性質と代数的誤り訂正手法 71 7.2 行列式に関する基礎事項 73 7.3 リード・ソロモン符号の定義 75 7.4 リード・ソロモン符号の復号法 76 演習問題 83 第 8 章 リード・ソロモン符号（II） 85 8.1 巡回符号としてのリード・ソロモン符号 85 8.2 リード・ソロモン符号を用いた消失訂正 88 8.3 リード・ソロモン符号を基礎とする組み合わせ型符号 89 8.4 BCH符号 92 演習問題 95 第 9 章 確率推論と復号 97 9.1 確率に関する表記と確率計算の基本則 97 9.2 最大事後確率復号法と最尤復号法 100 9.3 通信路モデルと最尤復号則 103 9.4 ブロック誤り率とシンボル誤り率 108 9.5 最尤復号法の最適性 110 演習問題 112 第 10 章 ビタビアルゴリズムによる最尤復号 114 10.1 線形符号のトレリス 114 10.2 ビタビアルゴリズムに基づく最小距離復号法 117 10.3 畳み込み符号 123 演習問題 128 第 11 章 ファクターグラフと sum-product アルゴリズム 129 11.1 ファクターグラフ 129 11.2 sum-productアルゴリズム 132
演習問題 143 第 12 章 シンボル MAP 復号法と前向き・後ろ向きアルゴリズム 144 12.1 シンボル MAP 復号法 144 12.2 前向き・後ろ向き (FB) アルゴリズム 147 12.3 FBアルゴリズムによるシンボル MAP 復号法 151 12.4 ターボ符号とターボ復号法 155 演習問題 157 第 13 章 LDPC 符号（I） 159 13.1 LDPC符号に関する基礎事項 159 13.2 LDPC符号による消失訂正 165 演習問題 171 第 14 章 LDPC 符号（II） 172 14.1 周辺事後確率計算の関数周辺化問題への帰着 172 14.2 確率領域 sum-product 復号法 174 14.3 対数領域 sum-product 復号法 178 14.4 対数尤度比の計算 183 演習問題 184 第 15 章 符号の性能評価 185 15.1 符号の重み分布 185 15.2 検査行列アンサンブルにおける平均重み分布 188 15.3 誤り検出法における見逃し誤り率 193 15.4 2元対称通信路における符号化定理 196 演習問題 201 関連図書 203 演習問題解答 205 索 引 221
vii ■本書で利用する記法 I[condition] conditionが真のとき 1，偽のときに 0 を値としてとる関数 [a, b] aから b までの連続した整数の集合 = 左辺を右辺により定義する := 右辺の値を左辺の変数に代入する |A| Aが有限集合の場合 A のサイズ（要素数）, A が行列の場合は A の行列式 A∪ B 集合 A と集合 B の合併集合 A∩ B 集合 A と集合 B の共通集合 A\B 集合 A から集合 B の要素をとり除いて得られる差集合 a∈ A aは集合 A の要素 B⊂ A 集合 B は集合 A に含まれる部分集合 左辺と右辺は十分に近い値をもつ ∝ 左辺と右辺は比例関係にある O(g(n)) す べ て の n で|f(n)| ≤ C|g(n)| を満たす定数 C が存在するとき， f (n) = O(g(n))と表記する dh(a, b) a, b 間のハミング距離 wh(a) a のハミング重み ln(x) 自然対数 F2 2元有限体 Fq q元有限体（q は素数のベキ） R 実数体 tanh ハイパボリックタンジェント At 行列 A の転置行列 Z(n,w) 長さ n，重み w の 2 元ベクトルの集合 P rob[event] 事象 event の生じる確率 arg maxx∈Df (x) 関数 f (x) を最大化する値 x∗∈ D（複数ある場合は集合を意味する） arg minx∈Df (x) 関数 f (x) を最小化する値 x∗∈ D（複数ある場合は集合を意味する） x フロア関数（x を超えない最大の整数） A mod B Aを B で割った余り（A, B は整数の場合と多項式の場合がある） 注意 • 一般的な表記ではないが，本書の後半におけるアルゴリズムの記述を簡単化するため に，集合 A から要素 b∈ A をとり除いて得られる集合を（本来ならば A\{b} と書くべ きところを）A\b とを表す場合もある． • 本書では，実数体の 2 項演算と有限体の 2 項演算では同じ記号（+, · など）を利用して いる（すなわち，1 + 1 = 2 となる場合と 1 + 1 = 0 となる場面がある）．文脈によりど ちらの演算を使うか明らかになるので混乱が生じることはないと思うが，念のためこ こに特記しておく． • 太文字の変数は行ベクトルを表す．ゼロベクトルは太字の 0 で表す．
13
第
2
章
符号化と復号
本章では，誤り訂正技術の基礎となる符号化と復号についてその概要を述べる．符 号化とは，送りたい情報を表しているメッセージベクトルを通信路に送り出す前に， 「通信路の雑音に負けない」ようにメッセージベクトルに施す変換操作である．また， 復号とは，受け取った信号から送られたであろうメッセージを推定する操作である． 許された計算量の範囲内で，受け手側での誤り率を可能な限り小さくする符号化と復 号の組を構成することが求められる．本章の最後に，実用化されている誤り訂正符号 を簡単に紹介する．2.1 符号
まず，符号（誤り訂正符号）を定義する．いま，通信路アルファベット（通信路へと 送信される信号の集合）をX とする．たとえば，2 元対称通信路の場合，X = {0, 1} である．符号とは，長さ n のX 上の系列の集合である． 符号（code） Xnの部分集合 C をX 上の符号とよび，符号 C に含まれる長さ n の系列を符号 C の 符号語（codeword）とよぶ．また，系列の長さ n を C の符号長（code length）とよぶ．第 1 章で紹介した符号化通信システムでは，送りたいメッセージを符号語のいずれ かに変換（符号化）し，それを通信路に送り出すことになる． 符号の例を次に示そう．X = {0, 1} とすると， X3={000, 001, 010, 011, 100, 101, 110, 111} である．この中から C ={000, 011, 101, 110} と選ぶと，C は符号長 3，符号語数 4 の 符号となる．長さ 3 の繰り返し符号は C={000, 111} と表すことができ，符号長 3， 符号語数 2 の符号である． 2元アルファベット上（X = {0, 1} の場合）で定義される符号を，2 元符号とよぶ．よ り一般の通信路アルファベット（q 個（q は 2 以上の整数）のアルファベット）上で定義
される重要な誤り訂正符号も多い1）．前章で，符号化通信／記録システムにおいては， その伝送速度・記録密度が符号化率により決まることをみた．より一般的な符号化率 の定義は次のとおりである． 符号化率（code rate） 符号 C の符号化率 R は， R= log2|C| log2|Xn| (2.1) により定義される． とくに重要な場合として，符号語数が|C| = 2k（k は正の整数）で与えられ，かつ X = {0, 1} の場合（2 元符号）の符号化率を考える．この場合，log22 = 1であること に注意すると，式（2.1）より符号化率 R は， R = log2|C| log2|Xn|= log22k log22n = k n (2.2) と与えられる2）．この式は前章で定義した符号化率の定義とも合致している．符号化率 は n シンボルを通信路に送ることにより，誤りが生じなかった場合に受信者が R× n ビットの情報を受け取ることを意味している． 符号の誤り訂正能力（復号後のブロック誤り率）を決める重要な要因として，符号 C に含まれる符号語が互いにどの程度離れているかという尺度が重要となる．その尺度 が次に定義される最小距離である． 最小距離（minimum distance） 符号 C の最小距離は，符号 C に含まれる相異なる二つの符号語のハミング距離の最小値 d= min{dh(a, b) : a, b∈ C, a = b} (2.3) である． 長さ 3 の符号 C ={000, 011, 101, 110} を再び考える．この符号の最小距離は 2 で ある．長さ 3 の繰り返し符号の場合，符号語は{000, 111} の二つであるので d = 3 と なる． 最小距離が大きいことは，C の符号語が空間Xnの中で互いにハミング距離の意味 1）たとえば，第 7 章で学ぶリード・ソロモン符号は，有限体F q上で定義される非 2 元符号である． 2）たとえば，長さ 3 の繰り返し符号の場合，k = 1 で n = 3 であることから，その符号化率は 1/3 である．
2.2 符号化 15 で離れて位置することを意味しており，後に述べるように，最小距離が大きいほどそ の符号の誤り訂正能力は高くなる．しかし，最小距離と符号化率の間には，符号化率 が高くなると最小距離は小さくなり，符号化率が低くなると最小距離が大きくなると いうトレードオフの関係がある（第 4 章の限界式の議論を参照のこと）．
2.2 符号化
符号化とは，送信者が送信したいメッセージに対応する符号語を生成する操作を意 味する．長さ 3 の符号 C ={000, 011, 101, 110} を仮定しよう．この符号を通信に利用 する場合には，4 種のメッセージ{0, 1, 2, 3} を符号語に対応づける操作が符号化とな る．たとえば， 0→ 000, 1 → 011, 2 → 101, 3 → 110 という対応づけにより，メッセージを符号化することができる． 符号化器（encoder） M をサイズが L のメッセージの集合とする（たとえば，M= [1, L]）．また，符号 C は L個の相異なる符号語をもつものとする．符号化器とは，全単射（bijection）の符号化写 像 φ :M → C を実現する装置である． 符号化写像 φ は全単射であると仮定しているので，φ は相異なるメッセージを相 異なる符号語に対応させる（単射性）．すなわち，m1 = m2(m1, m2 ∈ M) ならば， φ(m1)= φ(m2)である．さらに任意の c∈ C に対して，φ(m) = c となる m ∈ M が 存在する（全射性）． 符号化写像 φ は全単射3）なので，逆写像 φ−1が存在し，これを符号化逆写像とよぶ． 符号化逆写像 φ−1は，任意の m∈ M に対して，等式 m = φ−1(φ(m))を満たす．符 号化逆写像は復号器において得られる推定符号語 ˆX から推定メッセージ ˆMを求める ときに利用される． 長さ 3 の繰り返し符号の符号化写像を φ(m)= ⎧ ⎨ ⎩ 000, m = 0 111, m = 1 (2.4) 3）記法 φ：M → C は写像 φ の始域が M であり，終域が C であることを意味している．また，写像 f : X→ Y が全射性：∀y ∈ Y, ∃x ∈ X, f(x) = y と単射性：∀a, b ∈ X(a = b), f(a) = f(b) をもつと き，f は全単射であるという．としよう．すなわち，メッセージ m が 0 のときは対応する符号語が 000 であり，一 方，m = 1 の場合は 111 が符号化器の出力となる． 図 2.1 に符号化の様子を示す．ここでは，M = {0, 1}kとしている．集合{0, 1}nに 含まれる 2 元系列の個数は 2nであるが，そのうちの 2k個が符号 C の符号語（図 2.1 において黒丸で示されている系列）となる．すなわち，可能なすべての 2 元系列の一 部のみを符号語として利用しているものと考えられる． 図 2.1 符号化写像 φ(m) 符号化写像に対応する変換表（メッセージ→符号語）を符号化器においてもつとする と，任意の符号化写像を実現することができる．しかし，符号語数が多い場合（実用的 に使われている符号では，符号語数が 2500を超えることも珍しくない），その表を符 号化器内に保持するのは現実的ではない．符号が実用的に使えるためには，何らかの 方法により符号化写像が符号化器として実際に実装できるようなものでなくてはなら ない4）．
2.3 復号
受信語 Y はYnに含まれているものとする．ここで，Y を受信値のとりうる値の集 合とし，受信アルファベットとよぶ．復号器の役目は，受信語 Y から送信符号語の推 定値 ˆXを与えられた復号則に基づいて決定することである． ˆXが定まれば，符号化 逆写像を利用し， ˆM = φ−1( ˆX)として推定メッセージを得ることができる． 2.3.1 復号領域と復号写像 復号則とは，受信語 Y から推定符号語 ˆXを算出するためのルールである．いま， M個の符号語からなる符号 C を考え，その符号語を{c1, c2, . . . , cM} としよう．そ 4）この問題は次章で登場する線形符号により解決されている．2.3 復 号 17
れぞれの符号語に対応する復号領域を R(ci) (i ∈ [1, M]) とする．ここで，R(ci)は Ynの部分集合である．
復号領域 R(ci) (i∈ [1, M]) に基づく復号則は，次のようになる．
復号領域 R(ci)に基づく復号則（decoding rule） 次の三つの場合について処理を行う． （1）Y ∈ R(ci)かつ i とは異なる任意の j ∈ [1, M] について Y /∈ R(cj)が成り立つ 場合， ˆ X = ci とする． （2）Y がどの R(ci)にも属さない場合には， ˆ X =∗ とする．ここで，“∗” は誤り検出を表すシンボルである． （3）Y が複数の復号領域に属する場合，すなわち， Y ∈ R(cj1), Y ∈ R(cj2), . . . , Y ∈ R(cjs) となる場合には，推定語として cj1, cj2, . . . , cjsの中から何らかのルールに基づき 符号語を一つ選択する5）．この選択ルールをタイブレークルールとよぶ． 復号領域 R(ci)は，符号語 ciの守備範囲と考えることができる．復号器にやってき た受信語が R(ci)に含まれれば，推定語を ciにするというのが上の復号則の意味で ある．もし，どの符号語の復号領域にも受信語が属さない場合は，誤りが生じたとい うことだけが復号時にわかるので，推定語の代わりに誤り検出シンボルを出力する． たとえば，第 1 章で登場した長さ 3 の繰り返し符号に対する復号則 D1 に対応する 復号領域は，次のように与えられる． R(000)={000, 001, 010, 100}, R(111)={111, 110, 101, 011} 上で定義された復号領域に基づく復号ルールを写像の形に表したのが，復号写像 ψ :Yn → C ∪ {∗} である．ψ は与えられた受信語 Y から，推定符号語を ˆX = ψ(Y ) として算出する．図 2.2 に復号領域と復号写像を示す．折れ線で区切られた領域が各 符号語の復号領域を表しており，一つの復号領域が一つの推定符号語に対応する． なお，復号則を実現する手順・アルゴリズムのことを復号法とよぶ． 5）たとえば，インデックスのもっとも小さいものを選ぶ，または，乱数に基づいてランダムに選ぶなど．
図 2.2 復号写像 ψ(Y ) 2.3.2 誤りイベント 前項の復号法による復号結果について， （1）正訂正： ˆX = X が成り立つ場合 （2）誤訂正： ˆX= X の場合 （3）誤り検出： ˆX =∗ の場合 という三つの状態が考えられる． 誤訂正は，ciを送ったときに，Y が誤りの影響で R(ci)以外の復号領域 R(cj)に 入ってしまうために生じる．正訂正の生じる確率を Pc，誤訂正の生じる確率を Pe，誤 り検出の生じる確率を Pdとすると，当然 Pc+ Pe+ Pd= 1が成り立つ．誤訂正確率 と誤り検出確率の和をブロック誤り率とよぶ6）．復号領域のとり方は，符号のブロッ ク誤り率に強く影響する．符号，復号器の設計の際には，ブロック誤り率がその設計 指標として利用されることが多い．すなわち，ブロック誤り率がより小さい符号，復 号器が優れているということになる． 2.3.3 最小距離復号則 符号長 n の符号 C を利用するものと仮定する．2 元対称通信路の場合，n シンボル の中で生じる誤りの確率について，1 シンボルに誤りが生じる確率 > 2 シンボルに誤 りが生じる確率 > 3 シンボルに誤りが生じる確率· · · という関係が成り立つ．生起確 率の高い誤りパターンを訂正するためには，符号語の（ハミング距離における）近傍を その符号語の復号領域にするのが合理的である． 2元対称通信路においてブロック誤り率を最小とする復号則は，次の最小距離復号 則である． 6）ブロック誤り率の詳細な定義は第 9 章を参照のこと．
2.3 復 号 19
最小距離復号則（minimum distance decoding rule）
符号 C ={c1, c2, . . . , cM} について，次の復号領域に基づく復号則を最小距離復号則と よぶ．他の符号語に比べて，符号語 ci∈ C にもっとも近い点（系列）の集合が符号語 ci の復号領域 R(ci)となる．すなわち， R(ci)={y ∈ {0, 1}n:任意のc∈ C\{ci} に対して dh(y, ci)≤ dh(y, c)} (2.5) となる（i∈ [1, M]）（幾何の分野では，このような領域はボロノイ領域とよばれる）．ここ で，C\{ci} は集合 C から集合 {ci} をとり除いて得られる集合を意味している． 次の図 2.3(a) に最小距離復号則における復号領域を示す．図では符号語が黒丸で表 されており，復号領域の境界が実線で示されている．なお，最小距離復号則を利用す る場合には，誤り検出となる可能性はない． 最小距離復号則では，推定符号語 ˆXを受信語 Y から ˆ X = arg min X∈Cdh(Y, X) (2.6) として求めるものと考えてもよい．この式に現れる arg min は最小値を与える X∈ C を意味している．ただし，受信語 Y から等距離のところに複数の符号語がある場合に は，何らかの規則（タイブレークルール）に基づいて一つの符号語が選ばれる． 最小距離復号則を利用する場合，符号語間の位置関係が復号領域分割を決定してい る．さらに，そのときの各復号領域の形状が誤り率を決定している． 高い誤り訂正能力をもつ（もしくは低い復号誤り率を与える）符号を構成するために は，符号に含まれる符号語どうしをハミング距離の意味で互いに離して配置するのが 望ましい．これは，各符号語が離れて配置している場合，各々の符号語に対応する復 号領域を広くとることができるためである． 図 2.3 最小距離復号則と限界距離復号則の復号領域
2.3.4 限界距離復号則
限界距離復号則は，代数的符号である巡回符号やリード・ソロモン符号の復号の際 によく用いられる．限界距離復号則の場合，各符号語に対応する復号領域は，半径 r のハミング球（符号語からハミング距離で r 以内の 2 元系列の集合．正確な定義は第 4 章のハミング限界式の部分を参照のこと）となる．
限界距離復号則（bounded distance decoding rule） 符号 C ={c1, c2, . . . , cM} について，復号領域を R(ci)={y ∈ {0, 1}n: dh(ci, y)≤ r}, i ∈ [1, M] (2.7) と定める．ここで，r は， r≤ d− 1 2 を満たす正整数である．ただし，d は符号 C の最小距離である．記法 x はフロア関数 であり，x を超えない最大の整数を意味している．これらの復号領域で定義される復号 則を限界距離復号則とよぶ． 図 2.3(b) に限界距離復号則における復号領域を示す．符号語が黒丸で，黒丸を囲む 形で各復号領域が示されている． ここで，条件 r≤ (d − 1)/2 より， 2r≤ 2 d− 1 2 ≤ 2 × d− 1 2 = d− 1 (2.8) が成り立つ．任意の二つの符号語は少なくともハミング距離で d は離れているため， 任意の二つの復号領域が重ならないことがわかる．互いの復号領域が重ならないため， 限界距離復号則により通信路において生じた r(≤ (d − 1)/2 ) シンボルの誤りが必ず 訂正できる． 2.3.5 復号の計算量 符号化通信システムを実現するためには，以上でみてきたように，符号化写像を実 現する符号化器，復号写像を実現するための復号器を，実際に電子回路，または計算 機上で動くプログラムなどとして実現しなくてはならない．以下では，復号器の実装 可能性を計算量の観点から議論する． 復号法として最小距離復号法を例にとって考える．最小距離復号法の場合，得られ た受信語に対してもっともハミング距離の意味で近い符号語をみつける処理が必要と なる．符号語を順にすべて生成し，受信語との距離を逐一計算していくという手法を
2.4 実用化されている符号 21 とった場合，その復号法にかかる計算量は符号語数に比例することになる． たとえば，いま，符号長 n = 1000，符号語数 2800の 2 元符号 C を使った符号化 システムの設計をするものとしよう7）．この符号の符号化率は R = 800/1000 = 4/5 である．この符号の最小距離復号法の計算量（加算，乗算などの基本演算の回数）は， 2800の定数倍になる．このような計算量は，現時点の最速のスーパーコンピュータで 何万年という計算時間をかけても計算できるものではない．符号長 n，符号化率 R の 2元符号の場合，すべての符号語生成に基づく最小距離復号法の計算量は O(n2n)と なり8），n について指数時間アルゴリズムとなる． 符号化定理により保証された通信の信頼性を，現実的な時間計算量，空間計算量の 制限のもとに達成する，もしくは近似的に実現することは容易なことではない．数学 的構造をもつ符号を利用し，符号長 n に関して多項式時間（実用的には O(n)，O(n2) であることが必要）の時間計算量，空間計算量をもつ符号化器，復号器（復号法）を用 いて信頼性の高い通信を実現することが，符号理論におけるもっとも重要な研究テー マである．
2.4 実用化されている符号
誤り訂正符号は，身の回りのさまざまなディジタル機器において，通信・記録の信 頼性を向上させるために広く利用されている．現在，実用的に利用されている符号を 大別すると，表 2.1 のようになる．それぞれの特徴を簡単に述べる． 表 2.1 広く利用されている符号のクラス クラス 代表的な符号 利用例 代数的符号 リード・ソロモン符号 HDD，CD，DVD トレリス符号 畳み込み符号 携帯電話，モデム 疎グラフに基づく符号 ターボ符号，LDPC 符号 携帯電話，衛星放送 組み合わせ型符号 積符号，連接符号 衛星放送 2.4.1 代数的符号 代数的符号は，代数的な手法（たとえば，多項式環とそのイデアル，代数幾何的な手 法など）を利用して構成される符号のことである．代数的符号の代表的な符号として， 7）このようなパラメータは決して非現実的な数字ではなく，実際に実用的な通信システムにおいて利用されて いる．場合によっては符号長 1 万を超える符号が利用されることもある． 8）ランダウのオーダ記法：ある関数 f (n) について，正の定数 C と関数 g(n) が存在し，|f(n)| ≤ C|g(n)| が任意の n について成立する場合，f (n) = O(g(n)) と書く．詳細については，[10] を参照のこと．リード・ソロモン符号がある．リード・ソロモン符号は非常に優れた誤り訂正能力を もつため，広く実用的に利用されている．たとえば，HDD（ハードディスク），CD， DVDなどの記録システムにおいて，システムの信頼性を高めるためにリード・ソロ モン符号が利用されている．一般に代数的符号は，符号のもつ代数的な特性をうまく 利用した代数的復号法により復号される．代数的符号とその復号法については，第 7， 8章においてリード・ソロモン符号とその復号法を中心に解説する． 2.4.2 トレリス符号 すべての線形符号は，トレリスとよばれるグラフにより表現することができるが， とくに，簡単なトレリスにより表現できる符号をトレリス符号とよぶ．簡単なトレリ スをもつ符号の長所は，最尤復号（第 9 章を参照）にビタビアルゴリズムが利用できる ことにある．符号の状態数が少ない場合，ビタビアルゴリズムにより現実的な時間に おいて，最尤復号が可能であることから畳み込み符号はさまざまな場面で利用されて いる．トレリス符号とその復号法であるビタビ復号法については，第 10 章において 詳しく解説する． 2.4.3 疎グラフに基づく符号 現時点で知られるもっとも高い復号性能をもつ符号のクラスである．ターボ符号 （第 12 章），LDPC（低密度パリティ検査）符号（第 13 章）などの疎なグラフにより定義 される符号がこのクラスに含まれる．これらの符号では，確率推論計算に基づく反復 復号を利用することが特徴である．このクラスの符号は，その復号性能の高さから， 今後，さらに応用範囲の広がりが期待されている．本書では，このクラスの符号の代 表例として，LDPC 符号とその復号法である sum-product 復号法について第 13，14 章において詳しく論じる． 2.4.4 組み合わせ型符号 誤り訂正能力が高く，かつ複合計算量の小さい符号化方式を実現するための現実的 な符号化手法として，複数の符号を組み合わせた組み合わせ型符号が広く利用されて いる．たとえば，CD や DVD などの光記憶デバイスにおいては，二つのリード・ソ ロモン符号を組み合わせた積符号（product code）を利用することにより，バースト性 の強い誤りの効率良い訂正を実現している．また，ディジタル衛星放送の信頼性確保 のために，リード・ソロモン符号と畳み込み符号の連接符号が重要な役割を果たして いる．
演習問題 23
演習問題
2.1 2元符号 C={0000, 1010, 0101, 1111} について次の問いに答えよ． （1）符号 C の最小距離を求めよ． （2）C の符号化率を求めよ． 2.2 2元符号 C ={00000, 11100, 00111, 11011} を利用するものと仮定する．受信語 10111 を受信したとき，最小距離復号則に基づき推定符号語を求めよ． 2.3 長さ 5 の繰り返し符号を C とする．すなわち，C ={00000, 11111} である．この符号 Cに r = 1 の限界距離復号則を適用したものとする．次の問いに答えよ． （1）符号 C の各符号語の復号領域に含まれるベクトルを列挙せよ． （2）通信路として反転確率 p の 2 元対称通信路を仮定する．この場合の正訂正確率 Pc，誤 り検出確率 Pd，誤訂正確率 Peを求めよ（符号語の対称性より，ゼロ符号語（オールゼロ ベクトル）を送信した場合のそれぞれの確率を評価すればよい）． （3）Pc+ Pd+ Pe= 1となることを確認せよ． 2.4 次のような通信路を考える．2 ビットの通信路入力 (a, b)(a, b∈ {0, 1}) をその通信路に 入力するとその出力として，(a, b)，または (¯a, ¯b)のいずれかが受信されるという．ここで， ¯ a, ¯bはそれぞれ，a, b のビット反転を意味する．符号 C ={00, 01} の符号語をこの通信路 を通して送信することを考える．すなわち，(a, b) = (0, 0) または (a, b) = (0, 1) とする． この場合，各符号語の判定領域をどのように定義するのが望ましいかを述べよ．71
第
7
章
リード・ソロモン符号（I）
本章と次章では，Fq上で定義されるリード・ソロモン符号（Reed-Solomon code）に ついて説明する．リード・ソロモン符号は，優れた符号化率・最小距離のトレードオ フ関係をもつ符号であり，最大距離分離符号（MDS 符号）の一種である．リード・ソ ロモン符号の代数的な特長を生かした効率の良い代数的復号法がいくつも知られてい る．リード・ソロモン符号は CD，DVD における誤り訂正技術として利用されるな ど，非常に広い分野で活用されている． 本章では，リード・ソロモン符号の定義とその復号法を説明する．リード・ソロモ ン符号の最小距離の評価，復号法の理解に欠かせない行列式に関する基礎事項につい ても本章の前半部で簡単に述べる．7.1 リード・ソロモン符号の性質と代数的誤り訂正手法
リード・ソロモン符号の詳細をみていく前に，例を通してその性質と代数的誤り訂 正手法についてみていこう． 7.1.1 最小距離 3 のリード・ソロモン符号 下記に，最小距離 3 のリード・ソロモン符号を定義する検査行列を示す． 最小距離 3 のリード・ソロモン符号 有限体Fq（q は素数のベキ）上で定義される次の検査行列（n= q− 1 とする） H = α0 α1 α2 · · · αq−2 (α0)2 (α1)2 (α2)2 · · · (αq−2)2 = 1 α α2 · · · αn−1 1 α2 α4 · · · α2(n−1) (7.1) で定義されるFq上の線形符号 C={x ∈ Fn q : Hxt= 0} (7.2) を考える．ここで，α はFqにおける原始元である．符号 C は，符号長 n = q− 1，次元k = n− 2，最小距離 d = 3 というパラメータをもつ． たとえば，F28の場合，n = 255, k = 253, d = 3 という符号が得られる．この符号 C は，符号語内に生じた任意の 1 シンボル誤りを訂正することができる． まず，C の最小距離を求めてみよう．この検査行列の相異なる任意の 2 列を取り出 して作られる行列の行列式は， α i αj α2i α2j = αi× α2j− αj× α2i
= αi+2j− αj+2i= αi+j(αj− αi) (7.3) となる．ここで，i, j∈ [0, q −2] (i = j) である．αi+j = 0 であり，仮定より αj−αi= 0 であるので，上記の行列式は 0 とはならない．したがって，列 (αi, α2i)tと (αj, α2j)t は一次独立である．H からとり出した任意の 2 列が一次独立であり，一方，一次従属 となる 3 列が存在することから，第 4 章の議論を思い出すと，C の最小距離は 3 とな ることがわかる． 7.1.2 最小距離 3 のリード・ソロモン符号に対する代数的復号法 符号 C は最小距離 3 をもつことから，任意の 1 シンボルの誤りが訂正可能である． ここでは，次のような状況を考える．送信側は C の符号語 X∈ Fn qを送信したものと する．受信側は受信語 Y = X + E を受け取る．ここで，E は長さ n のFq上のベク
トルであり，その第 i 成分（i∈ [1, n]）だけが誤り値 (error magnitude) e ∈ Fqをもち，
他の成分はゼロであるものと仮定する． 以下では，受信語 Y から元の符号語を推定する手順（復号手順）を説明する．まず， 受信語に対してシンドロームを S = HYtと計算する．符号語 X について HXt= 0 が成り立つことから S = HYt= H(X + E)t= HEt となる．シンドローム HEtを計算すると， S = ⎛ ⎝ s1 s2 ⎞ ⎠ = ⎛ ⎝ eαi−1 eα2(i−1) ⎞ ⎠ (7.4) となる．このシンドロームから s2/s1を計算すると， s2 s1 = eα2(i−1) eαi−1 = α i−1 (7.5) が得られる．この結果から第 i シンボルに誤りが生起したことが明らかになる．一方，
7.2 行列式に関する基礎事項 73 s21/s2を計算すると， s21 s2 = e2α2(i−1) eα2(i−1) = e (7.6) となるため，誤り位置に加えて誤り値も計算することができた．これらの情報を総合 すると，第 i シンボルに誤り e が生じたことがわかり，E が正しく推定できたことが わかる．あとは，得られた推定誤り ˆE を受信語から引くことにより，（ ˆX = Y − ˆE） 推定語 ˆX を得る．このようにして，C はブロック中に生じた任意の 1 シンボルの誤 りを代数的な計算により効率よく訂正できる．
7.2 行列式に関する基礎事項
本節では，行列式に関する性質をいくつか述べたのち，リード・ソロモン符号の性 質を議論する際に必要となるヴァンデルモンドの行列式について説明する． 7.2.1 行列式とその性質 本章の議論では，さまざま場面で行列式に関する知識が必要とされる．ここでは， 簡単に行列式の定義と性質を復習してから先に進む． 行列式（determinant） 有限体Fqを要素としてもつ n× n 行列 A = {aij} (i ∈ [1, n], j ∈ [1, n]) について，そ の行列式を |A|= n i=1(−1)i+jaij|Aij|, n > 1 a11, n = 1 (7.7) と定義する．ここで，j∈ [1, n] はあらかじめ与えられた任意の列番号であるものとし， Aijは行列 A から第 i 行と第 j 列をとり除いて得られる (n− 1) × (n − 1) 行列である． 以上の定義1）から，たとえば，有限体Fqを要素としてもつ 2× 2 行列 A= ⎛ ⎝ a b c d ⎞ ⎠ について行列式|A| は，|A| = ad − bc となることがわかる． 本章の議論で必要とされる行列式の性質を簡潔に以下にまとめる． 1）通常の線形代数の教科書では，この式は行列式の行展開とよばれる定理として紹介されることが多いが，本 書ではこの式を行列式の再帰的定義式として用いている．行列式の性質
性質 1 Fq上の n× n 行列（a1a2· · · an）（aiは第 i 列ベクトル）に対して，
|a1a2· · · aai· · · an| = a|a1a2· · · ai· · · an| が成り立つ．ここで，i∈ [1, n] であり，a ∈ Fqである． 性質 2 Fq上の n× n 行列（a1a2· · · an）について，
|a1a2· · · ai+ aj· · · an| = |a1a2· · · ai· · · an| + |a1a2· · · aj· · · an| が成り立つ．
性質 3 Fq上の n× n 行列の転置行列の行列式は，元の行列式の行列式と等しい．すな わち，|At| = |A| が成り立つ．
性質 4 Fq上の二つの n× n 行列の積の行列式は，それぞれの行列の行列式の積に等し い．すなわち，|AB| = |A||B| が成り立つ．
性質 5 Fq上の n× n 行列（a1a2· · · an）について，|a1a2· · · an| = 0 は，a1a2· · · an が一次独立であるための必要十分条件である． 性質 6 対角成分（b1, b2, . . . , bn）のFq上対角行列 B（対角成分以外は 0）の行列式は， |B| = n i=1biとなる． 7.2.2 ヴァンデルモンドの行列式 リード・ソロモン符号に関する議論には，次の形をした行列が頻繁に登場する． X= ⎛ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎝ 1 1 1 · · · 1 x1 x2 x3 · · · xn x21 x22 x23 · · · x2n .. . ... ... ... ... xn−11 xn−12 xn−13 · · · xn−1n ⎞ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎠ (7.8) この形の行列をヴァンデルモンド行列とよぶ．とくに今後の議論では，ヴァンデルモ ンド行列の列の一次独立性を調べる必要があるときが多い．そのような場合に威力を 発揮するのが次のヴァンデルモンドの行列式である． ヴァンデルモンド（Vandermonde）の行列式 行列 X の行列式について，下記の等式が成り立つ． 1 1 1 · · · 1 x1 x2 x3 · · · xn x21 x22 x23 · · · x2n . . . . . . . . . . . . . . . xn−11 xn−12 xn−13 · · · xn−1 n = i>j (xi− xj) (7.9)
7.3 リード・ソロモン符号の定義 75 式（7.9）の左辺は i > j を満たす i, j∈ [1, n] のすべての組について積をとるという意 味である．もし，相異なる任意の i, j について xi= xjならば，式（7.9）の右辺はゼロ ではない2）．その場合，行列式の性質 5 より行列 X の列ベクトルは一次独立となり， Xは正則行列となる．
7.3 リード・ソロモン符号の定義
リード・ソロモン符号を次のように定義する． リード・ソロモン符号（Reed-Solomon code） Fq上の検査行列 H= ⎛ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎝ 1 α α2 · · · αn−1 1 α2 α4 · · · α2(n−1) 1 α3 α6 · · · α3(n−1) . . . . . . . . . . . . . . . 1 α2t α4t · · · α2t(n−1) ⎞ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎠ (7.10) で定義されるFq上の線形符号 C={c ∈ Fnq : Hct= 0} (7.11) をリード・ソロモン符号とよぶ．ここで，n= q− 1 であり， t∈ [1, (q − 2)/2] (7.12) である． いま，検査行列 H の任意の 2t 列を取り出して得られる行列を Hsubとする． Hsub= ⎛ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎝ αj1 αj2 · · · αj2t α2j1 α2j2 · · · α2j2t .. . ... ... ... α2tj1 α2tj2 · · · α2tj2t ⎞ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎠ (7.13) ここで，ji ∈ [0, n − 1] (i ∈ [1, 2t]) であり，jk= jl (k, l∈ [1, 2t], k = l) である．この Hsubの行列式を考えると， 2）有限体では，非ゼロの元どうしの積がゼロになることはない．|Hsub| = αj1 αj2 · · · αj2t α2j1 α2j2 · · · α2j2t .. . ... ... ... α2tj1 α2tj2 · · · α2tj2t = αj1· · · αj2t 1 1 · · · 1 αj1 αj2 · · · αj2t .. . ... ... ... α(2t−1)j1 α(2t−1)j2 · · · α(2t−1)j2t (7.14) を得る．この変形では，行列式の性質 1 を利用した．最後の等式の左辺に現れた行 列はヴァンデルモンド行列なので，ヴァンデルモンドの行列式の性質を利用すると |Hsub| = 0 となる．すなわち，Hsubは正則であり（行列式の性質 5），この結果は H の ランクが 2t であることを示している．したがって，C の次元 k は k = n− 2t となる． また，H の任意の 2t 列が一次独立となるため，C の最小距離 d について，d≥ 2t + 1 が成り立つ．一方，シングルトン限界式より， d≤ n − k + 1 = n − n + 2t + 1 = 2t + 1 となる．以上の二つの不等式から，d = 2t + 1 という結果が得られる． リード・ソロモン符号のパラメータ Fq上の検査行列 H により定義されるFq上のリード・ソロモン符号は，符号長 n = q−1， 次元 k = n− 2t，最小距離 d = n − k + 1 = 2t + 1 というパラメータをもつ． このパラメータをみてわかるように，リード・ソロモン符号はシングルトン限界を 等号で満足する．そのため，リード・ソロモン符号は最大距離分離符号である．
7.4 リード・ソロモン符号の復号法
本節では，リード・ソロモン符号の代数的な性質を利用した代数的復号法の一つで あるピーターソン復号法を紹介する．ピーターソン3）復号法は，リード・ソロモン符 号の符号長を n とするとき，O(n3)の計算量で t 個までの誤りが訂正できる復号アル3）W.W.Peterson：1960 年代の彼の著書“Error-Correcting Codes”により巡回符号の理論，代数的復号 法の基礎が確立された．
7.4 リード・ソロモン符号の復号法 77 ゴリズムである．現在知られているさまざまな代数的復号法4）の先駆けとして 1960 年 代に登場した． 7.4.1 シンドローム 送信器では，符号長 n = q−1 のリード・ソロモン符号 C の符号語 X = (X0, . . . , Xn−1)∈ Cを送信するものとする．本章の議論では，説明を簡略にするためにベクトルの要素 のインデックスを 0 から開始する．受信器では，受信語 Y = (Y0, . . . , Yn−1)∈ Fnq を受け取る．ここで，受信語は Y = X+E と与えられる．ベクトル E = (E0, . . . , En−1)∈ Fn q は通信路を誤りを表すベクトルである．以下の議論では，誤りベクトルのハミン グ重みについて wh(E) = νと表記する．また下記の議論では，1≤ ν ≤ t が成り立っ ているものと仮定する． 受信語 Y を受け取った受信器の最初の仕事は，シンドロームの計算である．シン ドローム S = (S1, S2,· · · , S2t)は，S= HYtで定義される．2 元線形符号のシンド ロームにおける議論と同様に， S = HYt= H(X + E)t= HEt が成り立つ．すなわち，i∈ [1, 2t] について， Si= 1 αi α2i · · · α(n−1)i ⎛ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎝ E0 E1 .. . En−1 ⎞ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎠ (7.15) となる．ここでの誤り訂正処理の目標は，このように計算されたシンドローム S か ら，誤りベクトル E を正しくみいだすことにある．すなわち， HQT = S (7.16) を満たす Q∈ Fn q を求めればよいが，この方程式は不定方程式（未知変数のほうが独 立な式よりも多い方程式）なので，付加的な条件がなければ，この問題は不良設定問 題5）となる．しかし，|E| ≤ t という条件がある場合，方程式（7.16）は唯一の解をもつ 4）リード・ソロモン符号，ならびに代数幾何符号の代数的復号法には，さまざまな手法が知られている．たとえ ば，Berlekamp-Massey-Sakata 復号法，Euclid 復号法（Sugiyama-Kasahara-Hirasawa-Namekawa）， Welch-Berlekamp復号法，Feng-Rao 復号法，Sudan によるリスト復号法など．たとえば，Euclid 復号 法などでは，O(n2)の計算量で t 個までの誤りが訂正できる．
ことを示すことができる． 条件|E| ≤ t より，ハミング重み t 以下のすべてのベクトルを生成し，そのシンド ロームを調べて S と一致するベクトルを探すという総探索的アプローチも考えるこ とができるが，その手続きに必要とされる計算量は，符号長に対して指数的に増大す る．以下では，リード・ソロモン符号の代数的な性質を有効に活用することにより， |E| ≤ t という条件下における式（7.16）の求解が非常に効率的に（多項式時間で）実行で きることをみていこう． 誤りベクトル E について誤り位置集合EE を EE ={i ∈ [0, n − 1] : Ei= 0} (7.17) と定義する．仮定より|EE| = ν ≤ t である．ここで，ν 個ある EE の要素を EE = {j1, j2, . . . , jν} と表記しよう．また，以下の議論における表記を簡単にするために xk= α jk(k∈ [1, ν])，そして e k= Ejk (k∈ [1, ν]) とおく．このとき，j /∈ EE につい て Ej= 0となることに注意すると，式（7.15）は， Si= ν k=1 ekxik, i∈ [1, 2t] (7.18) と簡単化できる．この式を行列形式に書くと関係式 ⎛ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎝ S1 S2 .. . S2t ⎞ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎠ = ⎛ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎝ x1 x2 x3 · · · xν−1 xν x21 x22 x23 · · · x2ν−1 x2ν .. . ... ... ... ... x2t1 x2t2 x2t3 · · · x2tν−1 x2tν ⎞ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎠ ⎛ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎝ e1 e2 .. . eν ⎞ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎠ (7.19) が得られる．ここで，xk (k∈ [1, ν]) は誤り位置に対応し，ek (k∈ [1, ν]) は誤り値に 対応する． 7.4.2 誤り位置多項式 誤り位置多項式 σ(z) は，与えられた誤りベクトル E について，ν 個の根{x−11 , x−12 , . . . , x−1ν } をもつ ν 次の多項式である．その係数を σ1, . . . , σνとすると， σ(z) = 1 + ν k=1 σkzk (7.20) と表記される．定義より，σ(z) に誤り位置に対応する x−1j (j∈ [1, ν]) を代入すると， σ(x−1j ) = 1 + ν k=1 σkx−kj = 0 (7.21)
7.4 リード・ソロモン符号の復号法 79 が成り立つ．いま，νj=1ejxi+νj σ(x−1j ) (i∈ [1, ν]) という量を考えることにより， ν j=1 ejxi+νj σ(x−1j ) = ν j=1 ejxi+νj 1 + ν k=1 σkx−kj (7.22) = ν j=1 ejxi+νj + ν k=1 σk ν j=1 ejxν+i−kj (7.23) = Sν+i+ ν k=1 σkSν+i−k (7.24) = 0 (7.25) なる等式を得る．式（7.22）は誤り位置多項式の定義式（7.21）より導かれる．また，式 （7.24）はシンドロームに関する式（7.18）に基づいている．最後の等式は，σ(x−1j ) = 0 (j∈ [1, ν]) による．最後の等式を変形して得られる −Sν+i= ν k=1 σkSν+i−k, i∈ [1, ν] (7.26) を行列形式に書き直すと，次のようになる． シンドロームと誤り位置多項式の係数の関係 ⎛ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎝ S1 S2 S3 · · · Sν−1 Sν S2 S3 S4 · · · Sν Sν+1 S3 S4 S5 · · · Sν+1 Sν+2 S4 S5 S6 · · · Sν+2 Sν+3 . . . . . . . . . . . . . . . . . . Sν−1 Sν Sν+1 · · · S2ν−3 S2ν−2 Sν Sν+1 Sν+2 · · · S2ν−2 S2ν−1 ⎞ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎠ ⎛ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎝ σν σν−1 σν−2 σν−3 . . . σ2 σ1 ⎞ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎠ =− ⎛ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎝ Sν+1 Sν+2 Sν+3 Sν+4 . . . S2ν−1 S2ν ⎞ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎠ (7.27) 式（7.27）は シ ン ド ロ ー ム 間 の 再 帰 関 係 を 表 し て い る ．バ ー レ カ ン プ-マ ッ シ ィ （Berlekamp-Massey）アルゴリズムのように，シンドロームから直接に最小次数の再帰 関係を求めるアルゴリズムもある．また，ユークリッドの互除法に基づく Sugiyama らのユークリッド復号法もリード・ソロモン符号の復号法として有名である． いま，受信器が誤り個数 ν を知っているものと仮定する（実際には，ν を受信側で知 ることができないことに注意しよう．ν を知るための方法は後に議論する）．受信器は 受信語 Y よりシンドローム Si (i∈ [1, 2t]) を計算できる．また，仮定 ν ≤ t より式 （7.27）に現れる S1, S2, . . . , S2νは受信器にとってすべて既知である． 後に示すように，式（7.27）の左辺のシンドローム行列はフルランクの行列となるた め，式（7.27）の連立一次方程式を解くことにより，(σ1, σ2, . . . , σν)が一意に定まる．こ
の連立一次方程式を解くには，ガウス消去法に基づく手法などを用いることができる． 次に求まった係数（σ1, σ2, . . . , σν）から誤り位置多項式 σ(z) を定め，σ(z) に 0 以外 のFqの元を順次代入することで根を探す．この根の探索手順は，チェン探索（Chien search）とよばれる．求まった根の逆数を計算する（式（7.21）参照）ことにより，誤り位 置（x1, x2, . . . , xν）を得る． 7.4.3 誤り値の算出 次に誤り位置（x1, x2, . . . , xν）が正しくわかっているという状況で，誤り値（e1, e2, . . . , eν） の算出について説明する． シンドロームと誤り値との関係を表す式（7.18）より，等式 ⎛ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎝ S1 S2 .. . Sν ⎞ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎠ = ⎛ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎝ x1 x2 x3 · · · xν−1 xν x21 x22 x23 · · · x2ν−1 x2ν .. . ... ... ... ... ... xν1 xν2 xν3 · · · xνν−1 xνν ⎞ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎠ ⎛ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎝ e1 e2 .. . eν ⎞ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎠ (7.28) が成り立つ．この式の右辺の行列の行列式を考えると， x1 x2 · · · xν x21 x22 · · · x2ν .. . ... ... ... xν1 xν2 · · · xνν = x1x2· · · xν 1 1 · · · 1 x1 x2 · · · xν .. . ... ... ... xν−11 xν−12 · · · xν−1ν = 0 (7.29) が成り立つ．以上の変形においては，行列式の性質 1 とヴァンデルモンド行列式の性 質を利用した．したがって，式（7.28）は唯一の解をもち，その解はこの連立一次方程 式を解くことにより得られる．この場合もガウス消去法などの手法を利用することで 誤り値（e1, e2, . . . , eν）が得られる． 7.4.4 誤り個数の算出 残る問題は，誤り個数 ν をどのようにして求めるか，である．受信側は当然ながら， 通信路で生じた誤り個数を知ることはできない．ここまでの議論は誤り個数を知った 上での議論であり，実際にはまず何らかの方法により ν を算出する必要がある．次の 性質は誤り個数 ν の算出に有用であり，後に述べるピーターソン復号法の基礎となる． 誤り個数の算出に利用できる性質 1≤ τ ≤ t とする．また，
7.4 リード・ソロモン符号の復号法 81 Dτ = S1 S2 · · · Sτ S2 S3 · · · Sτ +1 . . . . . . . . . . . . Sτ Sτ +1 · · · S2τ−1 (7.30) とおく．このとき，τ = ν ならば Dτ = 0 が成り立つ．一方，τ > ν ならば Dτ = 0が 成り立つ． この性質の成立する理由を下記に示す．k∈ [ν + 1, t] について，ek= 0, xk= 0とお く．また， T = ⎛ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎝ 1 1 · · · 1 x1 x2 · · · xτ .. . ... ... ... xτ −11 xτ −12 · · · xτ −1τ ⎞ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎠ , Q= ⎛ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎝ e1x1 0 · · · 0 0 e2x2 · · · 0 .. . ... ... ... 0 0 · · · eτxτ ⎞ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎠ とするとき，Dτは， Dτ =|T QTt| = |T ||Q||Tt| (7.31) のように分解ができる（演習問題 7.5 参照）． τ > νのときには，対角行列 Q の対角要素に 0 が入ることになるため，|Q| = 0（行 列式の性質 6）である．したがって，式（7.31）により Dτ = 0となる．一方，τ = ν の 場合，Q の対角成分には非ゼロ要素が並ぶため，その行列式は非ゼロとなる（行列式 の性質 6）．一方，（x1, x2, . . . , xτ）は相異なるFqの元であるため，ヴァンデルモンド行 列式の性質から|T | = 0 である．したがって，Dτ= 0 が結論される． この性質を利用することにより，受信側で ν の値を決定することができる．まず τ = tと設定し，順に τ を小さくしながら Dτの値を調べていく．Dτ = 0 となったと きに τ = ν が成り立つ． 7.4.5 ピーターソン復号法 前項までの説明で，ピーターソン復号法を述べるための準備はすべて整った．下記 がピーターソン復号法の詳細である． ピーターソン復号法（Peterson algorithm） 入力：受信語 Y ，出力：推定語 ˆX ステップ 1（シンドローム計算） 式（7.15）に従い，受信語 Y からシンドローム（S1, S2, . . . , S2t）を計算する．また，τ := t とする．
ステップ 2（誤り数の算出） Dτ を算出する（式（7.30）参照）．もし Dτ = 0 ならば， τ := τ− 1 として，本ステップを再度繰り返す． ステップ 3（誤り位置多項式の算出） ν := τとした上で，連立方程式（7.27）を解き，誤 り位置多項式の係数（σ1, σ2, . . . , σν）を得る． ステップ 4（チェン探索） 誤 り 位 置 多 項 式 σ(z) か ら ，チ ェ ン 探 索に よ り 誤 り 位 置 （x1, x2, . . . , xν）を算出する． ステップ 5（誤り値の算出） 連立方程式（7.28）を解き，誤り値 ˆ E = (e1, e2, . . . , eν) を得る． ステップ 6（推定語の出力） 得られた推定誤り語 ˆE を Y から引き，推定語 ˆ X = Y − ˆE を得る． 仮定 ν≤ t のもとに上記の手続きにおいて，シンドロームから唯一の誤りベクトル が正しく定まることから，ピーターソン復号法は，t 個以下の任意の誤りパターンを 正しく訂正できる能力をもつことがわかる． 7.4.6 ピーターソン復号法の実行例 以下にピータソン復号法の実行例を示す．F2（表 5.3 参照）上の検査行列3 H= ⎛ ⎜ ⎜ ⎜ ⎜ ⎜ ⎝ 1 α α2 α3 α4 α5 α6 1 α2 α4 α6 α8 α10 α12 1 α3 α6 α9 α12 α15 α18 1 α4 α8 α12 α16 α20 α24 ⎞ ⎟ ⎟ ⎟ ⎟ ⎟ ⎠ (7.32) で定義されるリード・ソロモン符号 C を考える．等式 α7= 1を利用すると， H = ⎛ ⎜ ⎜ ⎜ ⎜ ⎜ ⎝ 1 α α2 α3 α4 α5 α6 1 α2 α4 α6 α1 α3 α5 1 α3 α6 α2 α5 α α4 1 α4 α α5 α2 α6 α3 ⎞ ⎟ ⎟ ⎟ ⎟ ⎟ ⎠ (7.33) が得られる．符号 C は 2 個までの誤りを訂正できる． いま誤りベクトル E = (0, 0, 0, α5, 0, α2, 0)を仮定して，誤り訂正手順をみていこう． また，送信符号語を X∈ C とし，受信語を Y = X + E とする． まずはシンドロームの計算である．HYt= H(X + Y )t= HEtを計算することに より，
