通信符号理論 07

1 通信符号理論 第7回 伊藤彰則

2 Reed-Solomon (RS) 符号 • 拡大体の上に定義される線形符号の一種 • 広く使われている • CD・DVD、地上デジタル放送、QRコードなど • 最大分離符号である（𝑑 = 𝑛 − 𝑘 + 1）

3 RS符号の検査行列 • 𝐺𝐹(𝑞)上の最小距離3のRS符号の検査行列 𝑛−1 1 𝛼 ⋯ 𝛼 𝐻= 1 𝛼 2 ⋯ 𝛼 2(𝑛−1) • ただし𝛼は原始元、𝑛 = 𝑞 − 1、𝑘 = 𝑛 − 2、𝑑 = 3 • 例：原始多項式𝑧 3 + 𝑧 + 1による𝐺𝐹(23 )の場合 2 3 4 5 6 1 𝛼 𝛼 𝛼 𝛼 𝛼 𝛼 𝐻= 1 𝛼 2 𝛼 4 𝛼 6 𝛼 8 𝛼10 𝛼12 2 3 4 5 6 1 𝛼 𝛼 𝛼 𝛼 𝛼 𝛼 = 2 4 6 3 5 1 𝛼 𝛼 𝛼 𝛼 𝛼 𝛼 2 2 2 2 1 𝛼 𝛼 𝛼 + 1 𝛼 + 𝛼 𝛼 + 𝛼 + 1 𝛼 +1 = 1 𝛼2 𝛼2 + 𝛼 𝛼2 + 1 𝛼 𝛼+1 𝛼2 + 𝛼 + 1

4 一般のRS符号の検査行列 𝐻= 1 𝛼 1 𝛼2 ⋮ ⋮ 1 𝛼 2𝑡 ⋯ 𝛼 𝑛−1 ⋯ 𝛼 2(𝑛−1) ⋱ ⋮ ⋯ 𝛼 2𝑡(𝑛−1) • ただし𝑛 = 𝑞 − 1、1 ≤ 𝑡 ≤ (𝑑 − 1)/2 • 𝑘 = 𝑛 − 2𝑡、𝑑 = 2𝑡 + 1 • 𝑡シンボルの誤りを訂正できる 𝒒 4 8 • 𝑡の最大値は⇒ 16 32 64 𝑛 3 7 15 31 63 max 𝑡 1 3 7 15 31 • ただし𝑡を最大にとると𝑘 = 1なので繰り返し符号になる

5 𝑑 = 3のRS符号の復号 • 誤りが高々1シンボルとする • 誤差ベクトル𝒆の𝑖番目の要素だけが非零であり、その値を𝑒𝑖 とする • 𝒔 = 𝐻𝒚𝑇 = 𝐻𝒆𝑇 = 𝑠0 𝑠1 𝑇 とする • 𝑠0 = 𝛼 𝑖−1 𝑒𝑖 , 𝑠1 = 𝛼 2(𝑖−1) 𝑒𝑖 • したがって • • 𝑠1 𝑠0 𝑠02 𝑠1 = = 𝛼 2(𝑖−1) 𝑒𝑖 𝛼 𝑖−1 𝑒𝑖 𝛼 2(𝑖−1) 𝑒𝑖2 𝛼 𝑖−1 𝑒 𝑖 = 𝛼 𝑖−1 より、どの場所に誤りがあるかがわかる = 𝑒𝑖 より、誤りの値がわかる • ここから誤差ベクトルを求めて受信語に足せばよい

6 復号例 • 先ほどの𝐺𝐹(23 )の例で(1 1 1 1 1 1 1)は符号語 1 𝛼 1 𝛼2 𝛼2 𝛼2 + 𝛼 𝛼 + 1 𝛼2 + 𝛼 𝛼2 + 1 𝛼 𝛼2 + 𝛼 + 1 𝛼2 + 1 𝛼+1 𝛼2 + 𝛼 + 1 2 2 2 2 0 1 + 𝛼 + 𝛼 + 𝛼 + 1 + 𝛼 + 𝛼 + 𝛼 + 𝛼 + 1 + 𝛼 + 1 = = 2 2 2 2 0 1+𝛼 +𝛼 +𝛼+𝛼 +1+𝛼+𝛼+1+𝛼 +𝛼+1 1 1 1 1 1 1 1

7 復号例 • 受信語が (1 1 1 1 𝛼 1 1)だったとすると 1 𝛼 1 𝛼2 𝛼2 𝛼2 + 𝛼 𝛼 + 1 𝛼2 + 𝛼 𝛼2 + 1 𝛼 𝛼2 + 𝛼 + 1 𝛼2 + 1 𝛼+1 𝛼2 + 𝛼 + 1 1 + 𝛼 + 𝛼 2 + 𝛼 + 1 + 𝛼(𝛼 2 + 𝛼) + 𝛼 2 + 𝛼 + 1 + 𝛼 2 + 1 = 1 + 𝛼2 + 𝛼2 + 𝛼 + 𝛼2 + 1 + 𝛼2 + 𝛼 + 1 + 𝛼2 + 𝛼 + 1 2 3 2 1 𝛼 + 𝛼 + 𝛼 + 𝛼 = = 𝛼2 + 𝛼 𝛼2 + 𝛼 1 1 1 1 𝛼 1 1

8 復号例 • 𝑠0 𝑠1 𝑇 = 1 𝛼 2 + 𝛼 𝑇 = 1 𝛼 4 𝑇 • • 𝑠1 𝑠0 𝑠02 𝑠1 = 𝛼 4 より、5番目の要素が誤り = 1 𝛼7 𝛼 𝛼 4 = 3 = 𝛼 = 𝛼 + 1より、誤りベクトルの要素は𝛼 + 1 4 • 誤りベクトルは(0 0 0 0 𝛼 + 1 0 0) • 元の符号語は 1 1 1 1 𝛼 1 1 + 0 0 0 0 𝛼 + 1 0 0 = (1 1 1 1 1 1 1)

9 符号化法 • 生成行列があれば、メッセージベクトルをかけるだけでよい • しかし生成行列は簡単には求まらない • 多項式を使う方法 • 準備 • 符号語 𝒄 = (𝑐0 , 𝑐1 , … , 𝑐𝑛−1 ) とする 𝑖 • 多項式 𝑝 𝑧 = 𝑐0 + 𝑐1 𝑧 + ⋯ + 𝑐𝑛−1 𝑧 𝑛−1 = σ𝑛−1 𝑐 𝑧 とする 𝑖=0 𝑖 • メッセージベクトル 𝒎 = (𝑚0 , … , 𝑚𝑘−1 ) • 符号語が 𝒄 = (𝑅0 , … , 𝑅2𝑡−1 , 𝑚0 , … , 𝑚𝑘−1 ) と表せると仮定する • 検査行列より 𝑝 𝛼 𝑖 = 0 (1 ≤ 𝑖 ≤ 2𝑡)

10 検査行列と多項式 • シンドロームが0になる条件より 𝐻𝒄𝑇 = 1 𝛼 1 𝛼2 ⋮ ⋮ 1 𝛼 2𝑡 𝑝(𝛼) ⋮ = =𝟎 𝑝(𝛼 2𝑡 ) 𝑛−1 ⋯ 𝛼 ⋯ 𝛼 2(𝑛−1) ⋱ ⋮ ⋯ 𝛼 2𝑡(𝑛−1) 𝑛−1 𝑐0 ⋮ 𝑐𝑛−1 ෍ 𝑗=0 = 𝑐𝑗 𝛼 𝑗 ⋮ 𝑛−1 ෍ 𝑗=0 𝑐𝑗 𝛼 2𝑡𝑗

11 符号化法 • 符号語 𝒄 = (𝑅0 , … , 𝑅2𝑡−1 , 𝑚0 , … , 𝑚𝑘−1 ) • 条件 𝑝 𝛼 𝑖 = 0 (1 ≤ 𝑖 ≤ 2𝑡) • どうやってこれを解くか 未知数𝑅0 … 𝑅2𝑡−1 の2𝑡個 方程式2𝑡本 • 𝑝 𝛼 𝑖 = 0より、𝑝(𝑧)は多項式𝑔 𝑧 = 𝑧 − 𝛼 𝑧 − 𝛼 2 ⋯ (𝑧 − 𝛼 2𝑡 )を因数 として持つはず（生成多項式） • 𝑝 𝑧 = 𝑔 𝑧 𝑄(𝑧)と表すことができる。 • メッセージ多項式 𝑚 𝑧 = 𝑚0 + 𝑚1 𝑧 + ⋯ + 𝑚𝑘−1 𝑧 𝑘−1 • 𝑅 𝑧 = 𝑅0 + 𝑅1 𝑧 + ⋯ + 𝑅2𝑡−1 𝑧 2𝑡−1 とおく • 𝑝 𝑧 = 𝑅 𝑧 + 𝑧 2𝑡 𝑚(𝑧) と書ける

12 符号化法 • 前頁の議論から、 • 𝑝 𝑧 = 𝑔 𝑧 𝑄 𝑧 = 𝑅 𝑧 + 𝑧 2𝑡 𝑚(𝑧) • 変形して 𝑧 2𝑡 𝑚 𝑧 = 𝑔 𝑧 𝑄 𝑧 + 𝑅(𝑧) • 𝑔(𝑧)は2𝑡次多項式、𝑅(𝑧)は2𝑡 − 1次多項式なので、 𝑧 2𝑡 𝑚 𝑧 を𝑔 𝑧 で 割った余りが𝑅(𝑧)となる • したがって、メッセージ多項式に𝑧 2𝑡 をかけて生成多項式で割っ た余りの多項式を求めれば、その係数がパリティになる

13 例 • 原始多項式 𝑧 3 + 𝑧 + 1 による 𝐺𝐹(23 )で𝑡 = 1の場合 • 𝑞 = 8, 𝑛 = 7, 𝑑 = 3, 𝑘 = 5 • 生成多項式 𝑔 𝑧 = 𝑧 − 𝛼 𝑧 − 𝛼 2 = 𝑧 2 + 𝛼 2 + 𝛼 𝑧 + 𝛼 3 = 𝑧2 + 𝛼2 + 𝛼 𝑧 + 𝛼 + 1 • 例えばメッセージを (1, 𝛼, 0,0, 𝛼 2 ) とする • 𝑚 𝑧 = 1 + 𝛼𝑧 + 𝛼 2 𝑧 4 • 𝑧 2 𝑚 𝑧 = 𝑧 2 + 𝛼𝑧 3 + 𝛼 2 𝑧 6 • 生成多項式で割った余りを取る

14 例 𝛼2𝑧4 𝑧2 𝛼2 + 𝛼 𝑧 𝛼+1 𝛼2 + 1 𝑧3 𝛼2𝑧2 𝛼2𝑧6 (𝛼 + 1)𝑧 𝛼𝑧 3 𝛼2 + 𝛼 + 1 𝑧2 𝛼2𝑧6 + 𝛼2 + 𝛼 𝛼2𝑧5 + 𝛼 + 1 𝛼2𝑧4 𝛼2 + 1 𝑧5 + 𝛼 + 𝛼2 + 1 𝑧4 𝛼2 + 1 𝑧5 + 𝛼2 + 𝛼 𝛼2 + 1 𝑧4 + 𝛼 + 1 𝛼2 + 1 𝑧3 𝛼 2 𝑧 4 + (𝛼 2 +𝛼)𝑧 3 𝛼2𝑧4 + 𝛼2 𝛼2 + 𝛼 𝑧3 + 𝛼2 𝛼 + 1 𝑧2 (𝛼 + 1)𝑧 3 + 𝛼 2 + 𝛼 𝑧 2 (𝛼 + 1)𝑧 3 + 𝛼 2 + 𝛼 𝛼 + 1 𝑧 2 + 𝛼 + 1 2 𝑧 (𝛼 2 + 𝛼 + 1)𝑧 2 +(𝛼 2 + 1)𝑧 (𝛼 2 + 𝛼 + 1)𝑧 2 + (𝛼 2 + 𝛼 + 1) 𝛼 2 + 𝛼 𝑧 + (𝛼 2 𝑧+𝛼

15 例 • 𝑅 𝑧 = 𝛼 + 𝑧より、 符号語は 𝛼, 1,1, 𝛼, 0,0, 𝛼 2 • 検算 • 1, 𝛼, 𝛼 2 , 𝛼 3 , 𝛼 4 , 𝛼 5 , 𝛼 6 ⋅ 𝛼, 1,1, 𝛼, 0,0, 𝛼 2 = 𝛼 + 𝛼 + 𝛼2 + 𝛼4 + 0 + 0 + 𝛼8 = 𝛼2 + 𝛼4 + 𝛼 = 𝛼2 + 𝛼2 + 𝛼 + 𝛼 = 0 • 1, 𝛼 2 , 𝛼 4 , 𝛼 6 , 𝛼 8 , 𝛼 10 , 𝛼 12 ⋅ 𝛼, 1,1, 𝛼, 0,0, 𝛼 2 = 𝛼 + 𝛼 2 + 𝛼 4 + 𝛼 7 + 𝛼 14 = 𝛼 + 𝛼 2 + 𝛼 2 + 𝛼 + 1 + 1 = 0

16 演習 原始多項式 𝑧 2 + 𝑧 + 1 による𝐺𝐹(22 )で𝑡 = 1の場合 メッセージ 𝑚 = (𝛼)をRS符号化せよ。 ※結果は3シンボル繰り返し符号になるはず

17 一般のRS符号の復号化法 • 𝑑 = 3の場合はシンドロームから直接誤差ベクトルがわかった が、一般の場合はもっと複雑になる • やるべきこと 1. 誤りの個数 𝑣 ≤ 𝑡 を求める。 2. 誤りの位置を求める。 3. 誤差ベクトルの値を求める。 • 𝐺𝐹(2)の場合は「誤っていれば反転」だったが、𝐺𝐹(2𝑚 )の場合 には「どう誤ったか」も調べなければならない • 話の都合上、これを逆順に説明する

18 Peterson–Gorenstein–Zierler 復号法 • 基礎的情報 • 受信語𝒀 = 𝑿 + 𝑬 ここで𝑿は符号語、𝑬は誤差ベクトル • 𝑬 = (𝐸0 , … , 𝐸𝑛−1 )とする（未知） • 𝑬のうち𝑣個の要素が非ゼロ（𝑣 ≤ 𝑡） • 𝑺 = 𝐻𝑬𝑇 = (𝑆1 , … 𝑆2𝑡 ) • 誤り位置に関する式 • 誤り位置を 0 ≤ 𝑗1 < ⋯ < 𝑗𝑣 < 𝑛 とする • 最初は未知だが、これがわかっていたとする • 𝐸𝑗𝑘 ≠ 0 (𝑘 = 1, … 𝑣) • 𝒆 = 𝑒1 , … , 𝑒𝑣 = (𝐸𝑗1 , … , 𝐸𝑗𝑣 )とする • 𝑬のうち0でない要素だけを集めて作ったベクトル。𝑒𝑘 ≠ 0 (𝑘 = 1, … , 𝑣)

19 Peterson–Gorenstein–Zierler 復号法 • 誤り位置に関する式 • 検査行列は 1 𝛼 ⋯ 𝛼 𝑛−1 2 2(𝑛−1) 1 𝛼 ⋯ 𝛼 𝐻= ⋮ ⋮ ⋱ ⋮ 1 𝛼 2𝑡 ⋯ 𝛼 2𝑡(𝑛−1) 𝑇 • 𝐻の𝑘列目（０から数える）は 𝛼 𝑘 , 𝛼 2𝑘 , … , 𝛼 2𝑡𝑘 2 2 𝑇 𝑗𝑘 • 𝑥𝑘 = 𝛼 とおく。 𝐻の𝑗𝑘 列目は 𝑥𝑘 , 𝑥𝑘 , … , 𝑥2𝑡 となる • シンドロームの第𝑘要素 𝑛−1 𝑣 𝑣 𝑆𝑘 = ෍ 𝛼 𝑘𝑖 𝐸𝑖 = ෍ 𝛼 𝑘𝑗𝑖 𝐸𝑗𝑖 = ෍ 𝑥𝑖𝑘 𝑒𝑖 𝑖=0 𝑖=1 𝑖=1 0でない要素だけ加算

誤り個数と位置がわかる状態で 誤りの値を求める • 誤差ベクトルの0じゃないところだけ寄せ集めて作った式 𝑥1 ⋯ 𝑥𝑣 ⋱ ⋮ 𝒆T = 𝑋𝒆𝑻 = 𝑺 𝐻𝑬𝑇 = ⋮ 𝑥12𝑡 ⋯ 𝑥𝑣2𝑡 • これを解けば𝒆がわかり、誤り位置と合わせれば誤りベクトル がわかる 20

21 例 • 先ほどの𝑑 = 3の例で言えば 2 3 4 5 6 1 𝛼 𝛼 𝛼 𝛼 𝛼 𝛼 𝐻= 1 𝛼 2 𝛼 4 𝛼 6 𝛼 8 𝛼10 𝛼12 • 5シンボル目だけが誤っていて𝑆 = 1 𝛼 2 + 𝛼 𝑇 とすると 1 𝛼4 𝑒 = 1 8 𝛼2 + 𝛼 𝛼 𝛼 4 𝑒1 = 1 より 𝑒1 = 𝛼 3 = 𝛼 + 1

22 次回予告 • やるべきこと 1. 誤りの個数 𝑣 ≤ 𝑡 を求める。 2. 誤りの位置を求める。 3. 誤差ベクトルの値を求める。←今ここ • 逆順に説明をしているので、次回は2→1の順に説明する