符号理論
1
始めに
1.1
情報伝送モデル
情報理論における情報伝送のモデルを図に示す。 情報記号系列 → 符号語系列 → 伝送路 → 受信記号系列 → 復号記号系列 → 情報記号系列 ↑ 誤り記号系列 文章，静止画，動画，音声等の伝達したい情報のバイナリ化した情報記号系列に冗長符号を追加して符号語 系列に変換する。符号語が伝達される際にノイズやハードウェアのエラーにより誤り記号系列が付け加わっ たものが先方へ伝わる。受信された記号列は受信記号系列といわれ，これより誤り記号系列を推定して修 正された復号記号系列を得て伝達したい情報を取り出す。1.2
アナログ通信での工夫
放送のように one–way の通信と，電話のように two–way の通信では誤りへの対策は異なるであろうが， 聞き取りにくい電話で会話するには次のような対策が考えられる。 • 大声で話す • ゆっくり話す • 繰り返す • 復唱する (talk back) • 言い換えて話す • 符号化して伝える (新聞の “し”，濁点，ヨットの “よ”，上野の “う”，. . . )1.3
符号理論の歴史
アナログ通信の時の考えから，ゆっくり伝送すれば伝送誤りは 0 に近づくことが分かるが，それでは大 量の情報を伝えるにはコストが大きくなる。この問題に対し C.E.Shannon が 1948 年に “A Mathematical theory of communication .” で今日 通信路符号化定理と呼ばれる次の定理を発表した。この定理はシャノ ンの発表した情報理論の基本定理の内の一つである。 定理 1 (シャノン) 伝送速度がこの通信容量を越えない限り，伝送速度を 0 に近づけることなく一定にし たままで ( 冗長度を一定にしたままで )，符号化と復号化を工夫すれば誤り率はいくらでも小さくできる。 ここで「通信容量」とは通信路の物理定数で，通信電力や通信周波数などで決まる。また，「冗長度」とは これから先に説明する情報源の信号以外に付け加えられる誤り検出・修正符号を意味する。この定理に触発されて色々な符号化の理論 (符号理論 (coding theory)) が研究されることとなった。基本 になる数学の理論は代数学であるが，妥当性の検証に統計学も利用される。符号理論の研究の成果として 今日の光ディスクや深宇宙通信が成立しているのである。
2
定義，概念，実例
2.1
符号の概念
符号の種類 ディジタル通信では，放送や電話のようなアナログ通信と違って，情報源から送り出された信 号は直接変調されて通信路へ送り出されるわけではない。情報源の信号を連続的に符号化して送出する場 合と，ある程度まとまったものを符号化して送出する場合とに分けられる。連続的に符号化される符号系を 合流符号 (convolution code) といい，ある程度まとまったものを符号化する符号系をブロック符号 (block code) という。 合流符号では木構造グラフが符号化の表現に使用されるために，木符号とも呼ばれる。この方式の符号を 復号する原理では, 復号する信号列がそれまで受信した信号と係わり合っているので，合流の名前がある。 一方のブロック符号は次のような特徴がある。 • 情報記号系列は一定の長さ毎にまとめられ，ブロック化される。これを情報記号ベクトルともいう。 • 情報記号ブロックに冗長記号が追加されて一定の長さの記号系列に変換される。変換された記号列を 符号語ベクトルという。 • 復号は原則としてブロック単位で行われる。即ち，木符号と異なりブロック符号では，復号は互いに 独立に行われる。 どちらの方式も何らかのアルゴリズムにより復号するのであるが，この講義ではブロック符号について説 明する。3
ブロック符号
3.1
ハミング距離
Q を q 個の記号の集合とする。Qn を Q の元を要素とする n 次元の横ベクトルとする。 定義 1 Qn3 x, y を x = (x 1x2. . . xn), y = (y1y2. . . yn) とするとき dH(x, y) = n X i=1 δ(xi, yi) ただし δ(xi, yi) = 1 xi 6= yi 0 xi = yi dH(x, y) を x, y の ハミング距離 (Hamming distance) という。 w(x) = dH(x, 0)を x の重み (weight) という。ただし，0 はゼロベクトルである。 ハミング距離は x, y の成分の異なるものの個数を表す。ウェイトは 0 でない成分の個数を表す。また， Bρ(x) = {y ∈ Qn| dH(x, y) ≤ ρ} を中心 x，半径 ρ の超球 (sphere) と呼ぶ。球という言い方は次の定理 からも妥当である。 定理 2 ハミング距離は距離の公理をみたす。 略証 反射律と対称律は明らかだから，三角不等式だけ証明すればよい。また，三角不等式は δ(xi, yi) に 対していえればよい。 x, y, z ∈ Q を任意に取る。δ(x, z) = 0 ならば明らか。δ(x, z) = 1 ならば x 6= z，このとき y と x, z との関係 は x = y, z 6= y または x 6= y, z = y または x 6= y 6= z であるから，どの場合も δ(x, y)+δ(y, z) ≥ 1 = δ(x, z) となる。
3.2
ブロック符号
定義 2 Qn の部分集合 C をブロック符号 (block code)，その元を符号語 (codeword)，n を 符号長 (code
length) という。また， d(C) = min{dH(x, y) | x, y ∈ C} を最小距離 (minimum distance)， w(C) = min{w(x) | x ∈ C} を最小重み (minimum weight)，q = |Q| として r(C) = logq|C| n
を符号化率 (information rate, rate of code)，
ρ(C) = max{min{dH(x, c) | c ∈ C} | x ∈ Qn}
を被覆半径 (covering radius) という。被覆半径 ρ は各 x ∈ Qn から C の元までの最小距離の x ∈ Qn 全体 の最大値であるから，被覆半径 ρ は球の集合 {Bρ(c) | c ∈ C} が Qn 全体を覆うための最小距離である。
3.3
完全符号，ECC，EDC
定義 3 受信語の s 個以下の間違いを検出できる符号系を s–誤り検出符号 (s–error detecting code)，t 個 以下の間違いを正しい符号に訂正できる符号系を t–誤り訂正符号 (t–error cerrecting code) という。 最小距離が d(C) のブロック符号は d(C) ≥ 2s のとき s–誤り検出符号，d(C) ≥ 2t + 1 とするとき，t–誤り 訂正符号である。
定義 4 最小距離が 2t + 1 の符号 C ⊂ Qn が完全符号 (perfect code) とは，全ての x ∈ Qn が距離が t 以 下の範囲に唯一つの符号語がある場合をいう。
完全符号は最小距離が 2t + 1 で，被覆半径が t であることと同値であるから，t 個までの誤りを含む受信 語を正確に誤り訂正できる。即ち，t–eror correcting code である。
定義 5 受話語から最小距離にある符号語を見つけ出す方法を最小距離復号法：MDD 法 (minimum distance decoding) という。 例 1 反復符号 (repetition code) Q = {0, 1}, n を奇数として，情報記号系列が 0 または 1，それぞれを n 回繰り返した信号列を符合とす るブロック符合を反復符号という。このブロック符号の最小距離は n，符号化比率は 1/n である。 符号長を 5 とすると C = {x = (00000), y = (11111)} で，最小距離は 5 である。したがって， 5 ≥ 2e + 1 より 2 個までの誤りは全て正しく訂正できることになるが，この場合，正しい送信符号の決定に MDD 法 の他に，受信語の 0, 1 の個数を比べて，多い方を復号語とする多数決法が考えられる。これは MDD 法と 同じ結果を得るが復号アルゴリズムはより簡単である。 x, y と距離が 1 にある Q5 の元は各 5 個，距離が 2 なるものは各 Ã 5 2 ! = 10 であるから，合計 30，し たがって，被覆半径は 2 で反復符号は完全符号である。(n が一般の場合も同様に証明できる)
例 2 パリティ検査符号 (parity check code))
Q = {0, 1}，Qk を情報記号系列全体とする。情報記号ベクトルの最後に 0 または 1 を付け加えて，ベ クトル (∈ Qk+1) の 1 の個数が偶数になるようにしたものを符号語としたブロック符号を考える。最後に付 け加えられる成分を (パリティ) 検査部ということにする。 情報記号系列は最低 1 箇所は，成分が異なる。さらに，1 箇所成分が異なると (パリティ) 検査部の値も 異なってくるので，この符号の最小距離は 2，従って 1–EDC，符号化率は k/(k + 1) である。 この符号は受信語の 1 の個数が奇数個であったら受信語に誤りがあることが分かるが訂正はできない。 この符号は計算機本体とキーボード間や LAN 内での通信に広く使用されている。間違いが検出されたら 再送信を依頼すれば誤りが少なくなる。 誤り確率を考慮した場合 伝送の際にビット落ちを起こす場所が確定している場合はエラーの検出は容易 である。現実にはノイズの混入はランダムに起きるので，現象解析には統計的な考慮も必要である。 Q = {0, 1} のとき 2 元符号といい，0, 1 の 2 つの信号が伝送の際に同じ確率 ε でそれぞれ 1, 0 と読み誤 られる通信路を 2 元対称通信路，同じ確率で信号が消えてしまう通信路を 2 元対称消失通信路という。 受信語から送信された正しい符号語を推定するのに，統計的推定を利用する方法があるが，“n1> n2 に 対し n1個のエラーのあるエラーパターンより，n2 個のエラーのあるエラーパターンの方が真実に近い” と
いう考えで元のパターンを推定する方法を最尤復号法：MLD(maximum likekihood decoding) という。 誤り確率 ε の 2 元対称通信路の場合は，受信語 y，符号語 x に対し dH(x, y) = e とすると x を y と受信される確率は P (x | y) = εe(1 − ε)n−e であるから，e が最小のものが最も送信語に近いと推定することにすると，これは MDD 法と同じ結果を 得る。
復号アルゴリズムの複雑さ アルゴリズムの良さを判定する指標として，アルゴリズムの時間的複雑さとい う考えがある。これは，長さが n の入力に対して問題解決までに主要なループを何回通るかを表したもの である。解析学で 2 つの関数 f (x), g(x) を考え，limx→∞f (x)/g(x) が 0 でない定数のとき “f(x) と g(x) は同位” であるという。あるアルゴリズムの時間的複雑さを f (n) としたとき，f (n) が n, log n の多項式と 同位ならば多項式時間のアルゴリズムであるといい，n の指数関数や n! と同位ならば指数関数時間のアル ゴリズムであるという。指数関数時間のアルゴリズムは計算機がどんなに早くなっても，入力データが大き くなると問題解決に非現実的な時間を要する。即ち，計算機で解けない問題になってしまうのである。 復号のアルゴリズムに関しては MDD 法でも，MLD 法でも，受信語に対して，ブロック符号 C の全て の要素と比較しなければならないので，指数関数的時間がかかる。 良い符号 以上のことを考慮して良い符号とは最低次のような条件を満たさなければならないことが分か るであろう。 • 信頼性：復号誤り確率が小さいこと • 効率： 符号化比率が大きいこと • 復号の複雑さ： 復号のアルゴリズムの時間的複雑さが小さいこと
4
数学の準備
(1)
符号を何らかの数学的構造を持って定義することを考える。ここでは，有限体と有限群について符号理論 で利用する定義と概念を説明する。以下で特に節を設けて説明する数学的準備の他に線形代数特に行列に 関する定理を頻繁に利用するがそれらについては特に節を設けて説明しない。4.1
有限体
• 符号の要素 Q は有限体とする (殆どの場合は Q = {0, 1} の 2 元体である)。Q は GF (q) または Fq と表されガロア体と呼ばれる。 • 有限体 Q の元の個数を |Q| = q とすると，q はある素数 p のべき乗 q = prである。p を体 Q の標 数という。 • 有限体 Q の乗法群 Q∗ = Q − {0} は Q のある要素 α(原始元という) の巡回群で表される。即ち， Q = {0, 1, α, α2, α3, . . . , αq−2} p が素数のとき，有限体 Fp は整数の有限集合 Q = {0, 1, 2, . . . , p − 1} に p を法とした四則計算を考えれ ばよい。この場合は 0, 1 以外の任意の Q の元が原始元である。また，q = pr (p : prime) のとき有限体 Fq は Fp を係数とする多項式環 Fp[x] の r 次の既約多項式 p(x) による剰余多項式全体の集合 Fp[x]/(p(x)) に p(x) を法とした四則計算を考えればよい。この場合は，一次式 x が一つの原始元である。4.2
有限群とコセット分解
有限群 G とその部分群 H を考える。g1 ∼ g2 ⇐⇒ ∃h ∈ H(g1= g2h) とすると，この関係は同値関係 である。この同値類を G の H による (左) コセット分解という。コセット分解を具体的行うには次のよう に行う。 (1) H = {h1= e, h2, h3, . . . , hm} を H の要素とする。ここで e は群の単位元で，h2 以降は任意に並べ てよい。 (2) g2∈ G を g26∈ H に任意に取り g2H = {g2h1= g2, g2h2, g2h3, . . . , g2hm} を考える。 (3) g3∈ G を g36∈ H ∪ g2H に任意に取り，g3H = {g3h1= g3, g3h2, g3h3, . . . , g3hm} を考える。 (4) 同じ要領で繰り返すと表に現れる元は全て異なり，G の元は有限だから，有限回の操作で終了する。 (6) 同値類の個数を l とすると |G| = |H| × l の関係にある。 この操作の結果を G = H ∪ g2H ∪ g3∪ · · · ∪ glH と表すことができる。コセット類を表すのに G/H と 記す。この分解で {e, g2, g3, , . . . , gl} をコセットリーダという。数学では同値類の代表元とよんでいる。コ セットリーダーの選び方は一意ではない。同じ同値類の任意の元がコセットリーダになる。5
線形符号
5.1
諸定義
定義 6 Q の元を要素とする長さが n の符号 C が q 元線形符号 (但し q = |Q|) であるとは，C が Qn の線 形部分空間を作るものをいう。C の次元が k のとき C は (n, k) 符号，また，最小距離が d を付け加えて (n, k, d) 符号であると呼ばれる。 線形部分空間であるとは x, y ∈ C ならば x − y ∈ C であることを意味する。ここで，x − y は成分ごと の引き算を行う。ただし，引き算は有限体の規則で行われる。線形部分空間のもう一つの計算であるスカ ラー倍は表面的には使われない。 線形符号は符号のクラスの中で基本的なものであり，殆どの符号が線形符号を基にして構成されている。 定理 3 線形符号においては最小距離は最小重みと同じである。 略証 線形符号 C において，任意の符号語 x, y をとると線形性より x − y ∈ C であるから dH(x, y) = dH(x − y, 0) = w(x − y) 生成行列 C が k 次元の線形空間であるから，C には k 個の一次独立なベクトル (基底) がある。その一組 を {x1, x2, . . . , xk} (注：横ベクトル) とすると， c ∈ C ⇐⇒ (c1c2. . . ck)(c = c1x1+ c2x2+ · · · + ckxk)が成立する。そこで k 行 n 列の行列 G を G = x1 x2 .. . xk とおくと C = {aG | a ∈ Qk} が成り立つ。この性質から G を C の生成行列という。基底の選び方は一意的 でないので，生成行列も一意的でないが，G = (Ik, P ) 形の生成行列を標準形の生成行列という。ここで Ik は k 次の単位行列で P は k 行 n − k 列の行列である。線形符号の特徴は行列 P により表される。 生成行列が標準形のとき，情報記号ベクトル w ∈ Qkに対して生成される符号語ベクトルは wG = (w, p) (p は n − k 次のベクトル) であるから，符号語の先頭から k 個の記号を情報記号列 (information symbols)， 残りの記号をパリティ検査記号列 (parity check symbols) という。情報記号列の部分は任意に定められる が，パリティ検査記号列は情報記号列に依存している。 例 3 反復符号は符号長を 5 とすると {(11111), (00000)} であるから生成行列は G = (11111) である。 また，情報記号系列長が 7 のパリティチェック符号は，その一組の基底が {(ei 1) | i = 1, 2, . . . , 7, ei= (0 . . . 010 . . . 0) 自然基底 } であることを考えると生成行列は G = (I7 1T7) ここで 17= (1111111) で 1T7 はそれを転置した縦ベクトルを表す。また，パリティ検査符号は先頭の 7 ビッ ト分の和が偶数ならば 8 ビット目は 0，奇数ならば 1 であり，偶数は 2 元体では 0, 奇数は 1 であること を考慮すると C = {(c1c2. . . c8) | c1+ c2+ · · · + c8= 0} とも表されることからも生成行列が得られる。 定義 7 2 つの線形符号 C1, C2はその生成行列が行基本変形と列置換で一致するときに等価 (equivalent) と いう。 行列の一般論から k × n 行列は階数が k ならば，行基本変形と列の置換だけで G = (Ik, P ) の形に変 形できるできるから，等価であることは生成行列の標準形が行列 P の列の置換で一致することと同じであ る。C1, C2が等価ならば，そのベクトルはある一つの置換で成分を入れ替えると一致することが分かる。こ のことより，等価な符号ならば誤り訂正能力は同じである。
定義 8 一般に符号 C が k 個の位置で 組織的 (systematic) とは，|C| = qk でその k 個の位置の値が丁 度一つの情報記号列に対応しているものをいう。この場合その k 個の場所にある記号は情報記号と呼ばれ る。また，この場合のように情報記号と冗長記号が区別できるような符号は分離的 (separable) であると呼 ばれる。 標準形の生成行列から生成される線形符号は組織的で，分離的である。 定義 9 C が (n, k) 符号のとき，次の符号を C の双対符号 (dual code) という。 C⊥= {y ∈ Qk| ∀x ∈ C (< x, y >= 0)} ただし < x, y > は内積 直交補空間は線形空間であるから双対符号も線形符号である。即ち，C⊥ は (n, n − k) 符号である。ここで 係数体は有限体であるから，実数上のベクトル空間と異なり C ∩ C⊥= {0} とは限らないないことに注意す ると，C = C⊥ のとき，C は自己双対 (self–dual) 符号であると呼ばれる。 G を C の生成行列とするとき，n − k 行，n 列の行列 H を GHT = O を満たす最大のランク (n − k) の ものとすると，H は C⊥ の生成行列である。何故ならば，< x, y >= xyT であって，任意の a, b ∈ Qk に 対して x = aG, y = bH とおくと < x, y >= aG(bH)T = aGHTbT より < x, y >= 0，さらに， H のラ ンクが n − k であることより dim{bH | b ∈ Qk} = n − k. したがって， C⊥ = {bH | b ∈ Qk}. この H を使って次のことがいえる。 x ∈ C ⇐⇒ xHT = O 定義 10 (1) y ∈ C⊥ に対し，任意の x ∈ C に対し成立する方程式 < x, y >= 0 をパリティ検査 (方程式)，C⊥ の 生成行列 H を C のパリティ検査行列という。 (2) 線形符号 C のパリティ検査行列が H のとき，任意の x ∈ Qn に対して xHT を x の シンドロム (syndrome) という。 G = (Ik P ) を C の標準形の生成行列とすると H は次のように求められる。 G = (Ik P ) のとき GHT = O ⇐⇒ H = (−PT In−k) 例 4 反復符号，パリティ検査符号のパリティ検査行列 HR, HP は定義から求めればよい。これらの生成 行列は例 3 に求めてある。 HR= (1T4 I4) HP = (11111111) ただし，14= (1111)
5.2
線形符号の復号
シンドロムの構成 ベクトル空間 Qnと部分空間 C を加法群と部分群の関係と見たコセット分解とシンド ロムの関係を考える。 xHT = yHT ⇐⇒ (x − y)HT = 0 ⇐⇒ x ∈ y + C であるからコセット類とシンドロムは一対一に対応する。(1) コセット分解の手順を繰り返しておくと e0 = 0，次に e1 = (10 . . . 0)，次は e2 6∈ C ∪ (e1+ C)， e3 6∈ C ∪ (e1+ C) ∪ (e2+ C) , . . . と続ける。C ⊂ Qn を (n, k) 符号とすると，必要なシンドロムは qn−k 個 (ただし (q = |Q|) である。 (2) 符号の復号の場合はコセットリーダはウェイトの小さいものから選ぶ。始めはウェイト 1 のものから e1= (10 . . . 0), e2= (010 . . . 0), . . . , en = (0 . . . 01) の順に選ぶのが通常の方法である。C の最小ウェ イトが 1 の場合はコセットリーダーに自然な基底を選んでいるうちにコセットリーダの選出が終わっ てしまうが，2 以上の場合は少なくとも自然な基底はすべて選出される。 (3) 続いて en+1= (110 . . . 0), en+2= (0110 . . . 0) などとウェイトが 2 のものからコセットリーダを選ぶ。 (4) C の最小ウェイトが大きいときは，更に，ウェイトが 3 のベクトルというように続き， qn−k 個のコ セットリーダが得られるまで実行する。 (5) 得られた一組のコセットリーダ {e1, e2, . . . er} を用いて一組のシンドロムを次により得る。 {si= eiHT | i = 1, . . . , r} (r = qn−k) 以上に説明した方法でコセットリーダを選ぶことができる場合は，シンドロム s1, s2, . . . , sn はパリティ検 査行列 H の転置したものの行成分に次のように現れる。 s1 s2 .. . sn .. . = HT シンドロムによる復号 線形符号 C のパリティ検査行列を H とする。パリティ検査行列やシンドロムの 定義 10 から，符号語 x ∈ C に誤りベクトル e が付け加わって w = x + e を受信したとすると wHT = (x + e)HT = eHT であるから受話語のシンドロームを求めて，同じシンドロムのコセットリーダを誤りベ クトルであると推定することは妥当な方法である。コセットリーダの選び方を上で説明したようにウェイト の小さいものから選ぶようにするとシンドロムを用いた復号は次のように行われる。 (1) 受話語 w のシンドロム s = wHT を求める。 (2) 上で求めたシンドロムの一覧から s と同じものを求める。それを s = sj とする。 (3) sj に対応するコセットリーダ ej を求め，x = w − ej を復号符号語と推定する。 コセットリーダはウェイトの小さいものから選んでいるので，この復号法は MDD 法と等価である。コセッ トリーダのウェイトが大きい所では，同じシンドロムに対して同じウェイトのコセットリーダの候補は複数 ある可能性があるので，この場合は復号語候補が複数あることを意味するが，復号は固定したコセットリー ダを用いて行う。 復号誤り率 定理 4 2 元対称通信路において 2 元 (n, k, d) 線形符号 C のシンドロムによる復号を考えると，正しく復号 される確率 P (C) は P (C) = d X w=0 hwεw(1 − ε)n−w
である。ここで，和は 0 から d までのウェイトに関するもので，hw はウェイトが w のコセットリーダの 個数で，ε は 0 → 1 または 1 → 0 の読み誤り確率である。但し，符号語の全文書中の使用割合は同じと する。 証明 {ej| j = 1, . . . , r} を一組のコセットリーダとするとシンドロムによる復号法から，一つの符号語を 正しく伝達できる受話語は一つの符号語 xi に対して {xi+ ej| j = 1, . . . , r} に限られるから，その語に読 み誤られる確率を求めればよい。ej のウェイトが w のとき xi を xi+ ej に読み誤る確率は εw(1 − ε)n−w である。したがって，ウェイトが w のコセットリーダが hw個あれば，これらに誤って伝送される確率は hwεw(1 − ε)n−w である。これより符号語 xiの通信文中に占める割合を P (xi) とすると符号 C の全文の正 しく復号される確率は P (C) = 2k X i=1 P (xi) d X w=0 hwεw(1 − ε)n−w 仮定から P (xi) = 1/2k であるから定理の式を得る。実際の和は C の最小ウェイトを越えたところにはシン ドロムはない。
6
ハミング符号
重要な例であるハミング符号の説明をする。 定義 11 生成行列が G の有限体 Fq 上の (n, k) 線形符号 C を考える。G は k 行 n 列の行列であるが， G の任意の 2 つの縦ベクトルが一次独立 (即ち，一方が他方のスカラー倍でない) のとき，C を射影符号 (projective code) という。 一般に， G は双対符号 C⊥ のパリティ検査行列になり，任意の x とウェイト 1 のエラーベクトル e(具体的 には e = aej= (0 . . . 0a0 . . . 0)) に対し，シンドロム (x + e)GT は G の縦ベクトルのスカラー倍 (具体例で は j 列の縦ベクトルのスカラー倍) になる。G に上記の制限が付くとシンドロムから G のどの列に対応し ているか直読できることから，エラーベクトルが直ちに分かる。即ち，C⊥ は少なくとも 1 個のエラーは訂 正できる符号である。C と C⊥ を入れ替えて，この性質を一杯に使用したものが次のハミング符号である。 まず，一般に有限体 Q = Fq 上の k 次元ベクトル空間 Qk のベクトルの集合で任意の 2 本が一次独立 である最大のものの元の個数を調べてみる。始めに任意のベクトル f1 6= 0 を取り Qk からそのスカラー 倍を一つにまとめた Qk の部分集合を s1 とすると，Q の非ゼロ元は q − 1 個であるから |s1| = q − 1 で ある。s1 に属さない任意のベクトルを f2 6= 0 として，その非ゼロスカー倍をまとめたものを s2 とする と同様に |s2| = q − 1，これを続けて l 個の部分集合ができたとすると si∩ sj = Ø (i 6= j) であるから l ×(q −1) = qk−1，右辺で −1 したのはゼロベクトルを除いたためである。したがって，l = (qk−1)/(q −1). 定義 12 n = (qk− 1)/(q − 1) とする。有限体 F q 上の (n, n − k)ハミング符号 (Hamming code) とは，そ のパリティ検査行列の縦ベクトルの任意の 2 本が Fq 上一次独立のものをいう。 ハミング符号は Fq 上の k 次元の縦ベクトルで互いに一次独立な最大の集合 {f1, f2, . . . , fn} を選んで， H = (f1, f2, . . . , fn) をパリティ検査行列とする符号である。符号語の集合 C は，方程式 cHT = O の解ベクトルの集合である。さらに，ハミング符号では上記で説明したようにシンドロムがパリティ検査行列の列 番号に対応しているから，任意の 1 個のエラーが簡単に訂正できることもいえる。 定理 5 ハミング符号は最小距離が 3，1–ECC の完全符号である。 証明 ハミング符号 C のパリティ検査符号を H = (f1f2. . . fn) とする。但し，fj は長さ k の縦ベクトルと，任意の 2 つは一次独立，である。符号語 c(成分 n 個の横ベ クトル) は方程式 cHT = 0 で定められる。解を c = (c1c2. . . cn) とすると， c1f1+ c2f2+ · · · + cnfn= 0 をみたす。自明な解を除いて，この関係を満たす最小ウェイトの解を求めると，∀fj6= 0 であるから一つを除 いて残りが全て 0 という解はない。また，2 つを除いて残りが全てゼロという解を cicj 6= 0, ck= 0(k 6= i, j) とすると，これは cifi+ cjfj= 0 となり，これは fi, fj が一次従属であることを表すからハミング符号のパ リティ検査行列の選び方に反する。これより，最小距離，最小ウェイトは 3 以上であり，実際に 3 個のベ クトルが一次従属でハミング符号の条件を満たすパリティ検査行列ができる。 次に C を (n, n − k) ハミング符号とすると n = (qk− 1)/(q − 1) である。c に対し，この符号語を中心 にして半径が 1 の球内の Qn の個数は |B1(c)| = 1 + n(q − 1) = 1 + (qk− 1)/(q − 1) × (q − 1) = qk 一方，|C| = qn−k であるから qn−k× qk= qn = |Qn|. したがって，C の元から長さが 1 の球を描くと Qn の元が全て数え上げられるのでこの符号は完全符号である。 これらのことを合わせるとハミング符号は全ての受信語が訂正できる 1–ECC であることがいえる。 例 5 (1) q = 2 の場合 ア k = 2 ならば n = (22− 1)/(2 − 1) = 3 したがって (n, n − k, 3) = (3, 1, 3) であるから非実用的 イ k = 3 ならば n = (23− 1)/(2 − 1) = 7 したがって 2 元 (n, n − k, 3) = (7, 4, 3) ハミング符号が 存在する。よく使用されるパリティ検査行列は H = 0001 111 0110 011 1010 101 HT = 001 010 011 100 101 110 111
上で説明したようにウェイト 1 の誤り系列ベクトル ejに対し，シンドロム eHT は H の第 j 列 ベクトルの転置ベクトル (行ベクトル) のスカラー倍が現れるが，q = 2 であるから列ベクトルが そのまま現れる。さらに，成分の個数が 3，成分が 2 元数の一次独立は 23= 8 でゼロベクトルを 除くと 1 から 7 までの 2 進数表示と一致する。このことを利用して 1 から 7 までの列ベクトルを 順に並べてパリティ検査行列を作ると， ウェイト 1 のシンドロムの 1 の位置が 2 進数で表示さ れるようになっている。例えば，e = (0001 000) のとき s = eHT = (100)，これは 2 進数の 4. 他のパリティ検査行列 H と対応する生成行列 G の例は H = 0111 100 1011 010 1101 001 G = 1000 011 0100 101 0010 110 0001 111 これは組織的なハミング符号を与える。さらに H = 1001 110 0100 111 0011 101 により巡回ハミング符号を作ることができる。なお，これらのハミング符号はいずれも等価で ある。 ウ k = 4 ならば n = (24− 1)/(2 − 1) = 15 であるから 2 元 (15, 11, 3) ハミング符号が存在する。 検査行列の列ベクトルは 1 から 15 までの 2 進数に対応している。 (2) q = 3 即ち Q = {0, 1, 2} の場合 k = 3 とすると n = (33− 1)/(3 − 1) = 13 であるから 3 元 (n, n − k, 3) = (13, 10, 3) ハミング符号が存在する。パリティ検査行列を H = 11111 11100 100 00111 22211 010 12012 01212 001 とすると対応する生成行列 G は組織的なハミング符号を与える標準形をしている。 G = 10000 00000 202 01000 00000 201 00100 00000 220 00010 00000 222 00001 00000 221 00000 10000 210 00000 01000 212 00000 00100 211 00000 00010 022 00000 00001 021
定義 13 d を奇数として (n, k, d) 線型符号 C がのパリティ検査行列を H(n − k 行 n 列) とするとき， n − k + 1 行 n + 1 列の行列 H0= H 0 .. . 0 1 . . . 1 1 H0T = HT 1 .. . 1 0 . . . 0 1 をパリティ検査行列とする (n + 1, k) 線型符号 C0 を C の拡大線型符号という。C と C0 の違いを成分で表 示すると C0= {(c 1c2 . . . cncn+1) | (c1c2 . . . cn) ∈ C かつ n+1 X j=1 cj = 0} 定理 6 d を奇数とするとき，2 元 (n, k, d) 線形符号 C の拡大線型符号 C0 は (n + 1, k, d + 1) 符号である。 証明 C0 のウェイトは偶数で，従って最小距離も偶数である。C の最小距離 d は奇数であるから，C0 の最 小距離 d0 は偶数である。成分を 1 個付け加えても距離は最大 1 しか増えないので d0= d + 1 である。 系 1 拡大ハミング符号は 1–ECC，2–EDC 符号である。 例 6 パリティ検査行列 H0 = 100 11100 010 01110 001 11010 111 11111 による (7, 4, 3) ハミング符号と (8, 4, 4) 拡大ハミング符号の符号語は次の通り (7, 4, 3) ハミング符号 (8, 4, 4) 拡大ハミング符号 0000000 1111111 00000000 11111111 1110100 0001011 11101000 11111111 0111010 1000101 01110100 10001011 0011101 1100010 00111010 11000101 1001110 0110001 10011100 01100011 0100111 1011000 01001110 10110001 1010011 0101100 10100110 01011001 1101001 0010110 11010010 00101101 ここに示した (7, 4, 3) ハミング符号はこの後に説明する巡回符号の例でもある。(8, 4, 4) 拡大ハミング符号 は巡回符号ではない。
7
多数決論理による復号
多くの線形符号に対して有効な復号法 (多数決論理による復号法 majority logic decoding) について簡単 に説明しておく。この方法は単純な方法であるが予想以上の訂正能力を発揮する場合がある。
定義 14 線形符号 C の r 個のパリティ検査方程式系 < x, y(ν)>= 0 (x ∈ C, y(ν)∈ C⊥, 1 ≤ ν ≤ r) が位置 i に関する直交系 (orthgonal system with respect to position i) であるとは次の条件を満たすものをいう。
(i) y(ν)= (y(ν) 1 y (ν) 2 . . . y (ν) n ) とするとき y(ν)i = 1 (ν = 1, 2, . . . , r) (ii) j 6= i (1 ≤ j ≤ n) のとき y(ν)j 6= 0 となる ν (1 ≤ ν ≤ r) は高々一つしかない。 判定法 このような系があったとき，受話語 x = (x1x2. . . xn) が t 個の誤りを含んでいたとする。ただ し， t ≤ r/2 とする。x に含まれる誤りベクトルを e = (e1e2. . . en) とすると，< x, y(ν)>=< e, y(ν)>6= 0 (1 ≤ ν ≤ r) であるが，xi が正しいとすると ei= 0，従って ej 6= 0 となる j は t 個あるが，この系の (ii) より < x, y(ν)>=< e, y(ν)>6= 0 となる ν (1 ≤ ν ≤ r) は最大 t 個である。 一方，もし xi が誤っているとすると ei6= 0 であるから ei× y(ν)i = ei6= 0 (1 ≤ ν ≤ r)。しかし，ej6= 0 となる j は t − 1 個あり < e, y(ν)>= ei+ ej× y(ν) が 0 になる可能性を考慮すると < x, y(ν)>6= 0 にな る ν (1 ≤ ν ≤ r) は最小 r − (t − 1) 個である。 ここで t ≤ r/2 より r − (t − 1) > r であるから¯¯{ν |< x, y(ν)>= 0}¯¯ >¯¯{ν |< x, y(ν)>6= 0}¯¯ ならば xi は正しいし，そうでないときは xi は誤っていると判定ができることになる。さらに 2–元符号ならば誤り の訂正もできてしまう。このような直交検査系を各 i (1 ≤ i ≤ n) に対して用意できるならば，各位置に対 して一つずつ検査をしていけば良いことが言える。 例 7 例 5 のハミング符号の双対符号を例にする。即ち，この例の H を生成行列とする符号を考えると， 次の方程式系はパリティ検査方程式で，位置 1 に関する直交系である。 x1+ x2+ x3 = 0 x1+ x4+ x5 = 0 x1+ x6+ x7 = 0 もし，受話語 x が 1 個の誤りを含んでいたとして，x1 が誤りならば，この方程式の左辺の値は 1, 1, 1 と なる。一方，x1 が誤りでなければ，この方程式の左辺の値は 2 個の 0 と 1 個の 1 になる。さらに，もし 2 個の 1 が得られるようならば 2 個以上の誤りが含まれることが言える。(この符号は 2-EDC である)
8
数学の準備
(2)
ここでは環論に関する概念と定理を説明する。 定義 15 (1) 集合 R が加法に関して群，乗法に関して半群で加法と乗法に関して分配法則が成立するとき環 (ring) という。 (2) 環 R の部分集合が I イデアル (ideal) とは，加法に関して部分群で，RI ⊂ I であるものをいう。 例 8(1) 整数の集合 Z，正方行列の集合，F を体として F 係数の多項式 F[x] 等は環である。それぞれ有理整 数環，行列環，多項式環と呼ばれる。 (2) Z の部分集合で n ∈ Z に対して {0, ±n, ±2n, ±3n, . . . } はイデアルである。このイデアルは nZ また は (n) と表される。 (3) 多項式環 F[x] の部分集合で f(x) ∈ F[x] に対して f(x) で割り切れるもの全体はイデアルである。こ のイデアルは (f (x)) と表される。 定義 16 (1) 上の例のように環 R の要素 p ∈ R の倍数の集合 pR = {px | x ∈ R} で作られるイデアルを単項イデ アルまたは主イデアル (principal ideal) という。
(2) 環 R の任意のイデアルが単項イデアルのときに R は単項イデアル環 (pricipal ideal ring) であると いう。
(3) イデアル I において ab ∈ I =⇒ (a ∈ I or b ∈ I) が成り立つとき素イデアル (prime ideal) という。 (4) 環 R のイデアル I が極大イデアル (maximal ideal) とは，I ⊂ S ⊂ R となるイデアル S があれば
S = I または S = R となるものをいう。
(5) 極大イデアルが唯一つしかない環を局所環 (local ring) という。
例 17 有理整数環 Z の元 p ∈ Z を取り {0, 1, 2, . . . , p − 1} において a + b ≡ c (mod p), ab ≡ d (mod p) と する演算により環を作る。この環を Z/pZ または Z/(p) と表し，剰余 (類) 環 (residual (class) ring) という。 多項式環においても，g(x) ∈ F[x] を一つ定め，g(x) より次数の低い F[x] の元全体の集合に a(x)+b(x) ≡ c(x) (mod g(x))，a(x)b(x) ≡ d(x) (mod g(x)) により和と積を定義したものを F[x]/(g(x)) と表し，剰余多項式 環 (residual polynomial ring) という。
定理 7 Z, Z/(p), F[x], F[x]/(g(x)) は単項イデアル環である。 略証 Z の場合だけ証明しておく。他の場合も同様にできる。 Z の任意のイデアル I を考え，その元で正数のもので最小のものを p とする。∀s ∈ I に対し s = pq + r (0 ≤ r < p) となる q, r が存在する。イデアルの定義より r = s − pq ∈ I がいえるが p は I の元で 正数のもので最小のものであったから r = 0 即ち s = pq が成り立つ。
9
巡回符号
9.1
定義
バースト誤りに強い符号の説明をする。 定義 18 線形符号 C が次の性質を持つとき巡回符号という。 ∀(c0c1. . . cn−1) ∈ C =⇒ (cn−1c0. . . cn−2) ∈ Cシフトを続けると (cici+1. . . ci−1) ∈ C (i = 0, 1, . . . , n − 1) がいえる。巡回符号の場合は生成行列でその性 質を考えると少し表現が煩雑になるので別の表現方法を考える。
9.2
符号の多項式表現
次の対応によりベクトルと多項式を関連づける。 (c0c1. . . cn−1) ∈ Fnq ⇐⇒ c0+ c1x + c2x2+ · · · + cn−1xn−1∈ Fq[x]/(xn− 1) この対応で符号 C に対応させた多項式全体の集合も同じ記号 C で表す。 定理 8 Fnq の中の線形符号 C が巡回符号であるための必要十分条件は，C が剰余多項式環 Fq[x]/(xn− 1) の中で，イデアルであることである。 証明 (i) 多項式 C が Fq[x]/(xn− 1) のイデアルであるとすると，まず加法部分群という条件から C ⊂ Fnq は線 形部分空間であることが分かる。次に c(x) = c0+ c1x + c2x2+ cn−1xn−1∈ C と任意の多項式の積が C に入ることから xc(x) = c0x + c1x2+ · · · + cn−2xn−1+ cn−1xn≡ cn−1+ c0x + c1x2+ · · · + cn−2xn−1 (mod xn− 1) ∈ C であるから (c n−1c0c1. . . cn−2) ∈ C. よって C は巡回符号である。 (2) 逆に C ⊂ Fn q が巡回符号であるとすると，c(x) ∈ C に対し xc(x) ∈ C. 繰り返して xic(x) ∈ C (i = 1, 2, . . . )，この性質と線形性から任意の多項式 a(x) に対し a(x)c(x) ∈ C であるから C はイデアルで ある。 Fq[x]/(xn− 1) は単項イデアル環であることから C はある多項式 g(x) の倍数となっている。この多項式 は巡回符号の多項式の中で最高次の項の係数が 1 のものを選べば良い。この多項式を巡回符号の生成多項 式 (generator polynomial) とよぶ。 生成多項式 g(x) は xn − 1 の因子である。何故ならば，xn− 1 = g(x)q(x) + r(x) (0 ≤ deg(r(x)) < deg(g(x))) において xn− 1 を法として考えると r(x) ∈ C であり，g(x) の次数は C の中で最低次のもので あったから r(x) = 0 これ以降は既約因子による因数分解 xn− 1 = f1(x)f2(x) . . . ft(x) において重複する因子がないものとす る。この条件から n, k, q の任意の組み合わせに対して巡回符号が存在するとは限らないことに注意しよう。 既約因子による因数分解 xn− 1 = f1(x)f2(x) . . . ft(x) の因子 {f1(x), f2(x), . . . , ft(x)} から (重複無し に) 適当に選んで巡回符号の生成多項式 g(x) = fi1(x)fi2(x) . . . fis(x) を考える。deg(g(x)) = n − k とし て g(x) を生成多項式として，長さ k の情報記号系列を長さ n の符号語に変換するには次のようにすれば 良い。 (1) a = (a0a1. . . ak−1) を情報記号系列とする。 (2) a に対し k − 1 次の多項式 a(x) = a0+ a1x + · · · + ak−1xk−1 を対応させる。 (3) a(x) に対し a(x)g(x) = c0+ c1x + · · · + cn−1xn−1 を計算し c = (c0c1. . . cn−1) を符号語とすれば よい。例 9 2 元 (7, 4) 巡回符号を考える。2 元体における既約因子への因数分解 x7− 1 = (x + 1)(x3+ x2+ 1)(x3+ x + 1) から g(x) = (x3+ x2+ 1) を生成多項式とすると，情報記号系列 a = (a 0a1a2a3) に対する 符号 c は (a0+ a1x + a2x2+ a3x3)(1 + x2+ x3) = a0+ a1x + (a0+ a2)x2+ · · · + (a2+ a3)x5+ a3x6 より c = (a0a1(a0+ a2) . . . (a2+ a3)a3) となる。この式より分かるように，得られた符号語は非組織的であり， これから情報信号系列を見るのは容易でないので次のように生成多項式を変更する。 組織的巡回符号の生成多項式 符号語を組織的にするアイデアは生成多項式が n − k 次の多項式で，情報 記号系列の多項式が k − 1 次の多項式であるから，n − k 次から n − 1 次の項まで k 個の項が空いている ことを利用して情報記号系列を空いているところへシフトしてしまおうというものである。詳しい計算は 次のようにする。 (1) 情報記号系列の多項式を a(x) に xn−k をかける。この演算で情報記号系列は xn−k 次以上の項へシ フトされる。 (2) a(x)xn−k を g(x) で割り，商と余りを q(x), r(x) とすると a(x)xn−k= g(x)q(x) + r(x). r(x) を右辺 へ移項して d(x) = a(x)xn−k− r(x) = g(x)q(x). (3) 巡回符号の性質から d(x) は巡回符号で，余りの性質から deg(r(x)) < deg(g(x)) = n − k. したがっ て，左辺の n − k 次以上の項は a(x)xn−k の n − k 次以上の項と同じであるから，情報記号系列が保 存されている。 例 10 上の例で続けると a(x)x7−4 = (a0+ a1x + a2x2+ a3x3)x3 = a0x3+ a1x4+ a2x5+ a3x6 これを g(x) = x3+ x2+ 1 で割ると r(x) = (a 0+ a1+ a3)x2+ (a1+ a2+ a3)x + (a0+ a1+ a2) となるから従って
符号語は d = ((a0+ a1+ a3)(a1+ a2+ a3)(a0+ a1+ a2) a0a1a2a3) で後の 4 桁が情報記号系列，前の 3
桁がパリティ検査部を表している。(最後の計算は mod 2 で行っている。)
9.3
生成行列と検査行列
(n, k) 符号 C の生成多項式を g(x) = g0+g1x+· · ·+gn−kxn−kとする。情報記号系列 a = (a0a1. . . ak−1) の
情報記号多項式 a(x) = a0+a1x+· · ·+ak−1xk−1に対して符号語多項式が a(x)g(x) =
Pn−1 l=0( Pl i=0aigl−i)xl, 従って符号語は w = (a0g0(a1g0+ a0g1) . . . ak−1gn−k) であるから w = aG の生成行列は G = g0 g1 . . . gn−k 0 0 . . . 0 0 g0 . . . gn−k−1 gn−k 0 . . . 0 0 0 . . . . . . 0 0 0 . . . g0 g1 . . . gn−k g(x) は xn− 1 の因子であるから h(x) = h 0+ h1x + · · · + hkxk で h(x)g(x) = xn− 1 (in Fq[x]) となる ものがある。このとき g0hl+ g1hl−1+ · · · + gn−khl−n+k= 0 (for l = 0, 1, . . . , n − 1). H = 0 0 . . . 0 hk . . . h1 h0 0 0 . . . hk . . . h1 h0 0 .. . ... hk . . . h1 h0 0 . . . 0
とおくと GHT = O となる。従って，符号語 w = aG に対し wHT = O. 即ち，H は符号 C のパリティ 検査行列である。
これを多項式に置き換えると，w(x)h(x) = a(x)g(x)h(x) = 0 が成立する。従って，h(x) をパリティ検 査多項式 (parity check polynomial) という。
10
BCH
符号
巡回符号の中で実用上重要な符号が Bose と Ray–Chaudhurui(1960)，それとは別に Hocquenghem(1959) により発見された。彼らに因んで BCH 符号と呼ばれる。 パリティ検査行列とウェイト パリティ検査行列とウェイトの関係を調べよう。パリティ検査行列を H = (h1h2. . . hn) とする。ただし，hi は H の第 i 列ベクトル (n − k 次ベクトル) を表す。このとき c = (c1c2. . . cn) ∈ C ⇐⇒ cHT = 0 ⇐⇒ c1h1T+ c2hT2 + · · · + cnhTn = 0 この式は H の列ベクトルに関する一次従属関係を表している。 定理 9 (n, k, d) 線形符号 C のパリティ検査行列 H の列ベクトルの d − 1 個の任意の組み合わせは一次独 立であり，d 個の組み合わせで一次従属となるものがある。 証明 w(C) = d とすると，∀x ∈ Qn with (w(x) < d) であれば x 6∈ C であるから，{h 1, h2, . . . , hn} の任 意の d − 1 個の組み合わせは一次独立であることと同値である。 一方，条件から ∃c ∈ C (with w(c) = d) であるから c 6= 0 の成分を用いて H の列ベクトルの一次従属 の関係式が得られるので，定理がいえる。 ウェイトが d のベクトルが全て符号語であるとは限らないから，この定理で等号はいえない。一方，パリ ティ検査行列からウェイトを考えると次のようになる。 定理 10 H の列ベクトル {h1, h2, . . . , hn} の d − 1 個以下の列ベクトルの任意の組み合わせが常に一次独 立で，ある d 個の組み合わせで一次従属になるならば，w(C) = d である。 証明 d−1 個の組み合わせが一次独立ならば上の関係を成立させる組み c = (c1c2. . . cn) が存在しない。即ち， w(x) = d−1 ならば x 6∈ C. もし，d 個の組み合わせで一次従属になる関係式を ci1h T i1+ci2h T i2+· · ·+cidh T id= 0 とすると c = (0, . . . , 0, ci1, 0 . . . , 0, ci2, . . . , 0) とすれば cH T = O 即ち c ∈ C with w(c) = d である。 この定理の条件で Rank(H) ≥ d − 1 まではいえるが，d 個のある組み合わせが一次従属でも全て d 個の組 み合わせが一次従属とは限らないので，等号はいえない。
定義 19 自然数 n, l に対して 1 の原始 n 乗根を β とし βl, βl+1, . . . , βl+δ−2の最小多項式を ml(x), ml+1(x), . . . , ml+δ−2(x) とする。多項式
G(x) = L.C.M.(ml(x), ml+1(x), . . . , ml+δ−2(x))
を生成多項式とする Fq 上の長さ n の巡回符号を設計距離 δ の BCH 符号 (BCH code of designed distance δ) という。 通常は l = 1 とするが，強調する場合は狭義の (narrow–sense)BCH 符号という。 n = qm− 1 (i.e β が F qm の原始根) であるとき，原始 BCH 符号 (primitive BCH code) という。 定理 11 符号長 n，設計距離 δ の q 元 BCH 符号のパリティ検査行列は H = 1 βl ¡βl¢2 . . . ¡βl¢n−1 1 βl+1 ¡βl+1¢2 . . . ¡βl+1¢n−1 .. . ... ... . .. ... 1 βl+δ−2 ¡βl+δ−2¢2 . . . ¡βl+δ−2¢n−1 で与えられる。 証明 符号語 w(x) は情報記号系列多項式 v(x) に対し w(x) ≡ v(x)G(x) (mod xn− 1) で与えられる。 w(x) = w0+ w1x + w2x2+ · · · + wn−1xn−1 と置くと定義から w(βi) = w 0+ w1βi+ w2 ¡ βi¢2+ · · · + w n−1 ¡ βi¢n−1= v(βi)G(βi) = 0 したがって (w0w1w2. . . wn−1)(1βi ¡ βi¢2. . .¡βi¢n−1)T = 0 が i = l, l + 1, . . . , l + δ − 2 に対して成立する。行列 H を定理のように定めると，この関係は次のように なる。 (w0w1. . . wn−1)HT = 0 したがって，H がパリティ検査行列である。 定理 12 設計距離 δ の BCH 符号の最小距離は δ 以上である。 証明 定理 10 から，定理 11 で求めた δ − 1 行 n 列のパリティ検査行列から任意の δ − 1 列 を取り出してそ の組みの一次独立性をいえば良い。正方行列の一次独立性はその行列式の値が 0 でないことをいえばよい。
D(j1j2. . . jδ−1) = ¯ ¯ ¯ ¯ ¯ ¯ ¯ ¯ ¯ ¯ ¯ ¡ βl¢j1 ¡ βl¢j2 . . . ¡βl¢jδ−1 ¡ βl+1¢j1 ¡ βl+1¢j2 . . . ¡βl+1¢jδ−1 .. . ... . .. ... ¡ βl+δ−2¢j1 ¡ βl+δ−2¢j2 . . . ¡βl+δ−2¢jδ−1 ¯ ¯ ¯ ¯ ¯ ¯ ¯ ¯ ¯ ¯ ¯ = βl(j1+j2+···+jδ−1) ¯ ¯ ¯ ¯ ¯ ¯ ¯ ¯ ¯ ¯ 1 1 . . . 1 βj1 βj2 . . . βjδ−1 .. . ... . .. ... ¡ βj1¢δ−2 ¡βj2¢δ−2 . . . ¡βjδ−1¢δ−2 ¯ ¯ ¯ ¯ ¯ ¯ ¯ ¯ ¯ ¯ = βl(j1+j2+···+jδ−1)Y s>t ¡ βjs− βjt¢ 6= 0 最後の行列式は Vandermonde の行列式と呼ばれている。 例 11 F26 上の原始元 α の最小多項式を m1(x) = 1 + x + x6 としたとき，符号長が 63 の全ての 2 元 BCH 符号の生成多項式を次の表にあげる。この表より，例えば，(63, 45, 7) 原始 BCH 符号の生成多項式 G3(x) は G3(x) = L.C.M.(m1(x), m3(x), m5(x)) = (1 + x + x6)(1 + x + x2+ x4+ x6)(1 + x + x2+ x5+ x6) = 1 + x + x2+ x3+ x6+ x7+ x9+ x15+ x16+ x17+ x18 符号長 63 のすべての 2 元原始 BCH 符号の生成多項式 n k t G(x) 63 57 1 G1(x) = 1 + x + x6 51 2 G2(x) = G1(x)(1 + x + x2+ x4+ x6) 45 3 G3(x) = G2(x)(1 + x + x2+ x5+ x6) 39 4 G4(x) = G1(x)G3(x) 36 5 G5(x) = G4(x)(1 + x2+ x3) 30 6 G6(x) = G5(x)(1 + x2+ x3+ x5+ x6) 24 7 G7(x) = G6(x)(1 + x +3+x4+ x6) 18 10 G10(x) = G7(x)(1 + x2+ x4+ x5+ x6) 16 11 G11(x) = G10(x)(1 + x + x2) 10 13 G13(x) = G11(x)(1 + x + x4+ x5+ x6) 7 15 G15(x) = G13(x)(1 + x + x3) F26 の元の最小多項式
共役元 最小多項式 m(x) α, α2, α4, α8, α16, α32 m 1(x) = 1 + x + x6 α3, α6, α12, α24, α48, α33 m 3(x) = 1 + x + x2+ x4+ x6 α5, α10, α20, α40, α17, α34 m 5(x) = 1 + x + x2+ x5+ x6 α7, α14, α28, α56, α49, α35 m 7(x) = 1 + x3+ x6 α9, α18, α36 m 9(x) = 1 + x2+ x3 α11, α22, α44, α25, α50, α37 m 11(x) = 1 + x2+ x3+ x5+ x6 α13, α26, α52, α41, α19, α38 m 13(x) = 1 + x + x3+ x4+ x6 α15, α30, α60, α57, α51, α39 m 15(x) = 1 + x2+ x4+ x5+ x6 α21, α42 m 21(x) = 1 + x + x2 α23, α46, α29, α58, α53, α43 m 23(x) = 1 + x + x4+ x5+ x6 α27, α54, α45 m 27(x) = 1 + x + x3 α31, α62, α61, α59, α55, α47 m 31(x) = 1 + x5+ x6
11
代数的復号法
復号法には最小距離復号法の他，確率的復号法と代数的復号法がある。最小距離復号法や確率的復号法は 全数検査が必要なので短い計算ではあるが指数関数の計算回数を必要とするが，代数的復号法は，例えば 2 元 BCH 符号では O(n log22n) の演算回数ですむ。ただし，計算そのものはやや複雑である。以下において 代数的復号法を説明する。その要点は次の通りである。 (1) 受信語系列よりシンドロム多項式 S(x) を計算する。 (2) シンドロム多項式 S(x) より誤り位置多項式 σ(x) と誤り数値多項式 η(x) を求める。 (3) σ(x) より誤り位置を求める。 (4) σ(x) と η(x) より誤り数値を求める。2 元符号の場合はこの計算はいらないのであるが，q 元符号 (q > 2) を使用することによりバースト誤りの復号ができる。 以下において Fq上の長さ n，設計距離 2t + 1 の BCH 符号 (l = 1 とする)，β を 1 の原始 n 乗根，生成多 項式 G(x) とする。次の記号を使う。 符号語系列 v = (v0v1. . . vn−1) ↔ 符号語多項式 v(x) = v0+ v1x + v2x2+ · · · + vn−1xn−1 受信語系列 w = (w0w1. . . wn−1) ↔ 受信語多項式 w(x) = w0+ w1x + w2x2+ · · · + wn−1xn−1 誤り信号系列 e = (e0e1. . . en−1) ↔ 誤り多項式 e(x) = e0+ e1x + e2x2+ · · · + en−1xn−1 E = {i1, i2, . . . , is| eij 6= 0} (s ≤ t) 誤り位置の集合 σ(x) =Qi∈E(1 − βix) 誤り位置多項式 η(x) =Pi∈Eeiβix Q j∈E−{i}(1 − βjx) 誤り数値多項式1. シンドロム多項式の計算 w(x) = v(x) + e(x) に対して
w(βj) = v(βj) + e(βj) = c(βj)G(β) + e(βj) = e(βj) (j = 1, 2, . . . , 2t) であるからこの値は誤り系列にのみ依存しているのでシンドロムと名づけて良い。 Sj= w(βj) = e(βj) (j = 1, 2, . . . , 2t) とおくと誤り位置が E = {i1, i2, . . . , is} (s < t) なのでこの値は Sj= ei1(β j)i1+ e i2(β j)i2+ · · · + e is(β j)is =X i∈E ei(βj)i 以下の計算で Yl= eil Xl= β il (l = 1, 2, . . . , s) とおくとシンドロムは Sj = s X l=1 YlXlj (j = 1, 2, . . . , 2t) 次の式をシンドロム多項式という。 S(x) = S1+ S2x + S3x2+ · · · + S2tx2t−1 = 2t X j=1 Ã X i∈E ei(βj)i ! xj−1=X i∈E ei 2t X j=1 (βi)jxj−1 = s X l=1 Yl 2t X j=1 Xljxj−1 ここで次の形式的べき級数展開 1 1 − αx = ∞ X j=0 (αx)j を利用して S(x) =X i∈E eiβi 1 − βix (mod x 2t) = s X l=1 YlXl 1 − Xlx (mod x 2t) 2. 基本方程式の計算 誤り位置 E = {i1, i2, . . . , is} を用いて次の式を定義する。 σ(x) = (1 − βi1x)(1 − βi2x) . . . (1 − βisx) = (1 − X1x)(1 − X2x) . . . (1 − Xsx)
この式を誤り位置多項式と呼ぶ理由は σ(x) = 0 になる x は x = Xl−1= (βil)−1 (l = 1, 2, . . . , s) であるか ら，これより誤り位置が分かるからである。σ(x) をシンドロム多項式 S(x) より求める方法を考える。 σ(x)S(x) = (1 − X1x)(1 − X2x) . . . (1 − Xsx) s X l=1 YlXl 1 − Xlx (mod x 2t) = (1 − X2x)(1 − X3x) . . . (1 − Xsx)Y1X1 +(1 − X1x)(1 − X3x) . . . (1 − Xsx)Y2X2 .. . +(1 − X1x)(1 − X2x) . . . (1 − Xs−1x)YsXs (mod x2t) = s X l=1 YlXl s Y l=1 j6=l (1 − Xjx) (mod x2t) 最後の式を η(x) とおき，誤り数値多項式と呼ぶことにする。 η(x) = s X l=1 YlXl s Y l=1 j6=l (1 − Xjx) (mod x2t) 上の関係式 σ(x)S(x) = η(x) (mod x2t) はある多項式 φ(x) で次の様に表すことができる。 σ(x)S(x) + φ(x)x2t = η(x) この関係式で S(x) と x2t が既知で，σ(x), φ(x), η(x) は未知の多項式であるが，この関係式は S(x) と x2t の最大公約多項式が η(x) であることを表していて，これはユークリッド互除法 (または互減法) アルゴリズ ムを多項式に拡張した方法で高速に計算が可能である。 3. 誤り位置の計算 基本方程式の計算により得られた σ(x) のゼロ点を求めれば，その逆数が誤り位置を 示している。一般に方程式のゼロ点を求めることは非常に難しい問題であるが，今扱っている係数体は有限 体で β が 1 の原始 n 乗根であるから，β, β2, . . . , βn−1を順に代入して行けば有限回で解を求めることが
できる。解は一つとは限らないから全てを試す必要がある。これを Chien探索 (Chien search) という。 4. 誤り数値の計算 最後に誤り数値を計算する。この計算は 2 元符号のときは不要であるが，q > 2 の符 号を使用することによりバースト誤りに強い符号が得られることになり，実用上も使用されている。 定理 13 (Forney のアルゴリズム) 誤り数値は次の式で計算される。 eil = Yl= − η(Xl−1) σ0(X−1 l ) ただし，Xl= αil は誤り位置で Chien 探索でで求めた。また，σ0(x) は σ(x) の形式微分を表す。
略証 誤り数値多項式は η(x) = s X l=1 YlXl s Y j=1 j6=l (1 − Xjx) (mod x2t) でこれに x = Xl−1 を代入して η(Xl−1) = YlXl s Y j=1 j6=l (1 − XjXl−1) (mod x2t) したがって Yl= η(X −1 l ) Xl s Y j=1 j6=l (1 − XjXl−1) (mod x2t) (1) 一方，σ(x) を x で形式微分して σ0(x) = (−X 1)(1 − X2x)(1 − X3x) . . . (1 − Xsx) +(1 − X1x)(−X2)(1 − X3x) . . . (1 − Xsx) .. . +(1 − X1x) . . . (1 − Xs−1x)(−Xs) = − s X l=1 Xl s Y j=1 j6=l (1 − Xjx) この式に x = Xl−1 を代入して σ0(X−1 l ) = −Xl s Y j=1 j6=l (1 − XjXl−1) (mod x2t) (2) 式 (2) を式 (1) に代入して定理の式を得る。
12
Reed–Solomon
符号
BCH 符号の特別のものが Reed–Solomon 符号で CD や DVD の符号に用いられている。 定義 20 Fq (q = pr, p : prime) 上の長さ n = q − 1 の原始 BCH 符号を Reed–Solomon 符号とい う。簡単にするために l = 1 として説明すると，n の原始 n 乗根の一つを α とするとき，生成多項式は g(x) =Qd−1i=1(x − αi) になる。 定理 14 Reed–Solomon 符号の定数を (n, k, d) とすると d = n − k + 1 が成り立つ。証明 巡回符号の生成多項式の所で，情報ベクトルの長さ，符号語ベクトルの長さをそれぞれ k, n とする と，生成多項式 g(x) の次数は n − k ，符号空間は g(x), xg(x), x2g(x), . . . , xk−1g(x) を基底に持つことが
説明されている。Reed–Solomon 符号の場合，g(x) の次数は d − 1 であるから d − 1 = n − k が成立する。 定義 21 (n, k, d) 符号で d = n − k + 1 の関係が成り立つときに最大距離分離符号 (MDS:Maximum Distance Separable Code) という。MDS 符号では同一最小距離を有する符号の中で最小の検査記号数を持 つ符号である。 例 12 (15, 11, 5) RS 符号を考える。生成多項式は g(x) = (x − α)(x − α2)(x − α3)(x − α4) = α10+ α3x + α6x2+ α13x3+ x4 情報多項式を u(x) = α5+ αx2+ α3x10 とすると，符号語多項式 w(x) は v(x) = u(x)g(x) = 1 + α8x + α7x3+ α13x4+ α14x5+ αx6+ α13x10+ α6x11+ α9x12+ αx13+ α3x14 即ち，情報記号系列 u = (α50α00 00000 α3) に対して符号語系列が v = (1α80α7α13α14α000 α13α6α9αα3) となる。所で，実際のディジタル信号は Q = {0, 1} で成り立っているのであるから，F24 の元を 2 元ベク トルで表示すると次の表になる。即ち，α, α2, . . . は実際は (0010), (0100), . . . の列に置き換えられて送信 される。従って，実際に送信される信号にバーストエラーが起きても RS 符号系列の方では，一つか二つの 符号語が失われただけを意味し，バーストエラーに強い符号ということになる。 F24 の元の表現 (最小多項式 x4+ x + 1) ベキ表現 多項式による展開 ベクトル表現 0 0 0000 1 1 0001 α x 0010 α2 x2 0100 α3 x3 1000 α4 x4≡ x + 1 0011 α5 x2+ x 0110 α6 x3+ x2 1100 α7 x3+ x + 1 1011 α8 x2+ 1 0101 α9 x3+ x 1010 α10 x2+ x + 1 0111 α11 x3+ x2+ x 1110 α12 x3+ x2+ x + 1 1111 α13 x3+ x2+ 1 1101 α14 x3+ 1 1001
