通信符号理論 05

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

2 複数ビットを1つのシンボルにする • これまでは 0/1 が1つのシンボルになっていた • 0/1 の系列はシンボルが並んだもの（ベクトル） • 誤りはシンボルごとに起きる • 複数のビットが誤る場合には、複数のシンボルに個別に誤りが起きる と考える • 問題点 • ビット誤りは完全にランダムでなく、ある時点で集中的に起きること がある（バースト誤り） • 長時間ではBERが低くても、バースト誤りが起きると訂正できない • 解決法 • ビットの列を1つのシンボルとする

3 複数ビットを1つのシンボルにする • 例えば4ビットを1つのシンボルとすると • 10110110 → 10000110 に誤った場合 • 1ビット1シンボル： 1 0 0 0 0 1 1 0 2シンボルの誤り • 4ビット1シンボル： 1000 0110 1シンボルの誤り 誤りとしては より軽微 • どのようにして複数のビットを1シンボルとして扱うか • 4ビットのシンボルは16種類あるが、GF(16)みたいなものは作れない。 シンボルの種類は素数である必要がある • 拡大体というものを使う

4 有限体と体の拡大 • GF(p): p元有限体 pは素数でなければならない • 𝑎 + 𝑏 = 𝑎 + 𝑏 mod 𝑝, 𝑎𝑏 = 𝑎𝑏 mod 𝑝 ただし右辺は通常の整数環での演算 • 体の拡大とは • ある体の中で方程式 𝑓 𝑧 = 0 が根を持たない時、その根を形式的に適 当な要素 𝛼 とおいて、それを集合に加えることで新たな体を作ること • 例：実数体を複素数体に拡大する • 𝑥 2 + 1 = 0 は実数体で根を持たないので、その根を形式的に 𝑖 とする • 実数 R に𝑖 のスカラ倍と実数との和を加えると複素数 C になる • C は加算と乗算に関して体となる • これと同じ考え方で有限体を拡大する

5 既約多項式 • これ以上因数分解できない多項式のこと • GF(p)上の2次以上の既約多項式 𝑓(𝑧)は、GF(p)上に根を持たな い • 𝑓 𝑎 = 0だとすれば、因数定理により𝑓(𝑧)は𝑧 − 𝑎を因数として持つた め、既約であるという仮定に反する • 例：GF(2) 上で 𝑓 𝑧 = 𝑧 2 + 𝑧 + 1 は既約多項式である。 • 𝑓 0 = 0 + 0 + 1 = 1, 𝑓 1 = 1 + 1 + 1 = 1

6 拡大体 • GF(p)上の既約多項式𝑓 𝑧 = 0の根を形式的に𝛼とおいて、これ をGF(p)に付け加えて新たな体を構成する • 𝑓 𝑧 = 𝑧 2 + 𝑧 + 1 の場合、𝑓 𝛼 = 𝛼 2 + 𝛼 + 1 = 0 • 𝛼 2 + 𝛼 + 1 = 0 より、𝛼 2 = 𝛼 + 1 • 0,1, 𝛼, 𝛼 + 1 が新たな集合となる • 𝛼 2 = 𝛼 + 1なので、 0,1, 𝛼, 𝛼 2 でもよい • GF(p)上のm次既約多項式の根𝛼を付加することで構成される体 ⇒𝐺𝐹(𝑝𝑚 ) • 加算・乗算は通常の多項式の演算と同じ （ただし係数はGF(p)）

7 拡大体の例 • 既約多項式 𝑧 2 + 𝑧 + 1 による 𝐺𝐹(22 ) • 集合は{0,1, 𝛼, 𝛼 + 1} • 加算は通常の多項式の加算（係数はGF(2)） • 乗算 • 𝛼 × 𝛼 = 𝛼 2 = 𝛼 + 1, 𝛼 × 𝛼 + 1 = 𝛼 2 + 𝛼 = 𝛼 + 1 + 𝛼 = 1 • 𝛼 + 1 × 𝛼 + 1 = 𝛼2 + 𝛼 + 𝛼 + 1 = 𝛼 + 1 + 1 = 𝛼 + 0 1 𝜶 𝜶+𝟏 × 0 1 𝜶 𝜶+𝟏 0 0 1 𝛼 𝛼+1 0 0 0 0 0 1 1 0 𝛼+1 𝛼 1 0 1 𝛼 𝛼+1 𝜶 𝛼 𝛼+1 0 1 𝜶 0 𝛼 𝛼+1 1 𝜶+𝟏 𝛼+1 𝛼 1 0 𝜶+𝟏 0 𝛼+1 1 𝛼

8 拡大体と複数ビットシンボル • 𝛼を含む元と「複数ビットからなるシンボル」の関係 • 2ビットのシンボルを考え、次のように対応させる 拡大体 0 1 𝜶 𝜶+𝟏 2ビット 00 01 10 11 + 00 01 10 11 × 00 01 10 11 00 00 01 10 11 00 00 00 00 00 01 01 00 11 10 01 00 01 10 11 10 10 11 00 01 10 00 10 11 01 11 11 10 01 00 11 00 11 01 10

9 拡大体の例その２ • 3次の既約多項式 𝑓 𝑧 = 𝑧 3 + 𝑧 + 1 • 既約多項式ならば、定数1を含み、項の数が奇数になる • 定数1を含まないと𝑓 0 = 0、項数が偶数だと𝑓 1 = 0となる • 逆は成り立たない • 上記𝑓(𝑧)による𝐺𝐹(23 ) • 𝛼 3 + 𝛼 + 1 = 0より𝛼 3 = 𝛼 + 1 • 𝛼 2 はこれ以上簡単にならない • 集合は{0,1, 𝛼, 𝛼 + 1, 𝛼 2 , 𝛼 2 + 1, 𝛼 2 + 𝛼, 𝛼 2 + 𝛼 + 1} • 乗算の例 • 𝛼 + 1 𝛼2 + 1 = 𝛼3 + 𝛼2 + 𝛼 + 1 = 𝛼 + 1 + 𝛼2 + 𝛼 + 1 = 𝛼2

10 3次の拡大体の演算例 + 0 1 𝜶 𝜶+𝟏 𝜶𝟐 𝜶𝟐 + 𝟏 𝜶𝟐 + 𝜶 𝜶𝟐 + 𝜶 + 𝟏 0 0 1 𝜶 𝜶+𝟏 𝜶𝟐 𝜶𝟐 + 𝟏 𝜶𝟐 + 𝜶 𝜶𝟐 + 𝜶 + 𝟏 1 1 0 𝜶+𝟏 𝜶 𝜶𝟐 + 𝟏 𝜶𝟐 𝜶𝟐 + 𝜶 + 𝟏 𝜶𝟐 + 𝜶 𝜶 𝜶 𝜶+𝟏 0 1 𝜶𝟐 + 𝜶 𝜶𝟐 + 𝜶 + 𝟏 𝜶𝟐 𝜶𝟐 + 𝟏 𝜶+𝟏 𝜶+𝟏 𝜶 1 0 𝜶𝟐 + 𝜶 + 𝟏 𝜶𝟐 + 𝜶 𝜶𝟐 + 𝟏 𝜶𝟐 𝜶𝟐 𝜶𝟐 𝜶𝟐 + 𝟏 𝜶𝟐 + 𝜶 𝜶𝟐 + 𝜶 + 𝟏 0 1 𝜶 𝜶+𝟏 𝜶𝟐 + 𝟏 𝜶𝟐 + 𝟏 𝜶𝟐 𝜶𝟐 + 𝜶 + 𝟏 𝜶𝟐 + 𝜶 1 0 𝜶+𝟏 𝜶 𝜶𝟐 + 𝜶 𝜶𝟐 + 𝜶 𝜶𝟐 + 𝜶 + 𝟏 𝜶𝟐 𝜶𝟐 + 𝟏 𝜶 𝜶+𝟏 0 1 𝜶𝟐 + 𝜶 𝜶𝟐 + 𝟏 𝜶𝟐 𝜶+𝟏 𝜶 1 0 𝜶𝟐 + 𝜶 + 𝟏 𝜶𝟐 + 𝜶 + 𝟏

11 3次の拡大体の演算例 × 0 1 𝜶 𝜶+𝟏 𝜶𝟐 𝜶𝟐 + 𝟏 𝜶𝟐 + 𝜶 𝜶𝟐 + 𝜶 + 𝟏 0 0 0 0 0 0 0 0 0 1 0 1 𝜶 𝜶+𝟏 𝜶𝟐 𝜶𝟐 + 𝟏 𝜶𝟐 + 𝜶 𝜶𝟐 + 𝜶 + 𝟏 𝜶 0 𝜶 𝜶𝟐 𝜶𝟐 + 𝜶 𝜶+𝟏 1 𝜶𝟐 + 𝜶 + 𝟏 𝜶𝟐 + 𝟏 𝜶+𝟏 0 𝜶+𝟏 𝜶𝟐 + 𝜶 𝜶𝟐 + 𝟏 𝜶𝟐 + 𝜶 + 𝟏 𝜶𝟐 1 𝜶 𝜶𝟐 0 𝜶𝟐 𝜶+𝟏 𝜶𝟐 + 𝜶 + 𝟏 𝜶𝟐 + 𝜶 𝜶 𝜶𝟐 + 𝟏 1 𝜶𝟐 + 𝟏 0 𝜶𝟐 + 𝟏 1 𝜶𝟐 𝜶 𝜶𝟐 + 𝜶 + 𝟏 𝜶+𝟏 𝜶𝟐 + 𝜶 𝜶𝟐 + 𝜶 0 𝜶𝟐 + 𝜶 𝜶𝟐 + 𝜶 + 𝟏 1 𝜶𝟐 + 𝟏 𝜶+𝟏 𝜶 𝜶𝟐 𝜶𝟐 + 𝜶 + 𝟏 0 𝜶𝟐 + 𝜶 + 𝟏 𝜶𝟐 + 𝟏 𝜶 1 𝜶𝟐 + 𝜶 𝜶𝟐 𝜶+𝟏

12 原始元と原始多項式 • 𝐺𝐹(𝑝𝑚 )におけるm次原始多項式𝑓(𝑧)とは 𝑝𝑚 −1 • 𝑓 𝑧 = 0の根を𝛼とするとき、𝛼 = 1であり、 0 < 𝑘 < 𝑝𝑚 − 1ならば𝛼 𝑘 ≠ 1 となるもの • この時の𝛼を原始元という • 𝑓 𝑧 = 𝑧 2 + 𝑧 + 1は原始多項式 • 𝛼 22 −1 = 𝛼3 = 𝛼 𝛼 + 1 = 𝛼2 + 𝛼 = 𝛼 + 1 + 𝛼 = 1 • 𝑓 𝑧 = 𝑧 3 + 𝑧 + 1は原始多項式 • 𝛼 23 −1 = 𝛼7 = 𝛼3𝛼3𝛼 = 𝛼 + 1 𝛼 + 1 𝛼 = 𝛼2 + 1 𝛼 = 𝛼3 + 𝛼 = 𝛼 + 1 + 𝛼 = 1 • 𝑓 𝑧 = 𝑧 3 + 𝑧 2 + 1も原始多項式 𝛼1 ~𝛼 6 が1でない ことも示す必要が ある。

13 既約だけど原始多項式じゃない場合 • 𝑓 𝑧 = 𝑧4 + 𝑧3 + 𝑧2 + 𝑧 + 1 • 𝛼 15 = ⋯ = 1 • しかし 𝛼 5 = 𝛼 𝛼 3 + 𝛼 2 + 𝛼 + 1 = 𝛼 4 + 𝛼 3 + 𝛼 2 + 𝛼 = 1 C.f. 𝛼 4 + 𝛼 3 + 𝛼 2 + 𝛼 + 1 = 0 • 𝑓 𝑧 = 𝑧 4 + 𝑧 3 + 1と𝑓 𝑧 = 𝑧 4 + 𝑧 + 1は既約かつ原始多項式 • 𝑓 𝑧 = 𝑧 4 + 𝑧 2 + 1は既約でない • 𝑧2 + 𝑧 + 1 2 = 𝑧4 + 𝑧2 + 1

14 原始元のべき乗 𝑚 0 • 原始多項式による拡大体𝐺𝐹(2 )では、𝛼 から𝛼 でが0以外の異なる値に対応する 2𝑚 −2 ま • 原始多項式𝑓 𝑧 = 𝑧 2 + 𝑧 + 1による拡大体𝐺𝐹(22 )の原始元𝛼 • 𝛼 0 = 1, 𝛼 1 = 𝛼, 𝛼 2 = 𝛼 + 1 • 原始多項式𝑓 𝑧 = 𝑧 3 + 𝑧 + 1による拡大体𝐺𝐹(23 )の原始元𝛼 • 𝛼 0 = 1, 𝛼 1 = 𝛼, 𝛼 2 = 𝛼 2 , 𝛼 3 = 𝛼 + 1, 𝛼 4 = 𝛼 2 + 𝛼, • 𝛼 5 = 𝛼 2 + 𝛼 + 1, 𝛼 6 = 𝛼 2 + 1

15 べき表現、多項式表現、ベクトル表現 𝑚 • 𝐺𝐹(2 )の元は、下記の3つの形式で表現できる 2 2𝑚 −2 • 0, 1, 𝛼, 𝛼 , … , 𝛼 : べき表現 • 𝑚 − 1次多項式：多項式表現 • 𝑚次元の{0,1}のベクトル：ベクトル表現

16 べき表現、多項式表現、ベクトル表現 • 例 𝐺𝐹 22 𝑓 𝑧 = 𝑧 2 + 𝑧 + 1 べき表現 0 1 𝛼 𝛼2 多項式表現 0 1 𝛼 𝛼+1 ベクトル表現 00 01 10 11 • 例 𝐺𝐹 23 𝑓 𝑧 = 𝑧 3 + 𝑧 + 1 べき表現 0 1 𝛼 𝛼3 𝛼2 𝛼6 𝛼4 𝛼5 多項式表現 0 1 𝛼 𝛼+1 𝛼2 𝛼2 + 1 𝛼2 + 𝛼 𝛼2 + 𝛼 + 1 ベクトル表現 000 001 010 011 100 101 110 111

17 べき表現、多項式表現、ベクトル表現 • べき表現は乗算がやりやすい • 例：𝐺𝐹(23 )では𝛼 7 = 1なので、𝛼 20 = 𝛼 20 mod 7 = 𝛼 6 • 加算は多項式表現に変換して行う • 多項式表現は加算がやりやすい • 複雑な乗算はいったんべき表現にした方が簡単 • 𝐺𝐹(2𝑚 )のベクトル表現と𝐺𝐹(2)の𝑚次元ベクトルは何が違う？ • 加算は同じ、乗算が異なる • 「𝐺𝐹(2)の𝑚次元ベクトルの乗算」を「ビットごとの乗算」とすると、 乗算に逆元が定義できない

18 乗算 𝐺𝐹(22 )の乗算 𝐺𝐹(2)のビットごとの積 00 01 10 11 00 01 10 11 00 00 00 00 00 00 00 00 00 00 01 00 01 10 11 01 00 01 00 01 10 00 10 11 01 10 00 00 10 10 11 00 11 01 10 11 00 01 10 11 0でない要素同士の積が0になる 10に逆元がない 01に逆元が複数ある ⇒この定義の「積」は群にならない

19 演習 既約多項式𝑓 𝑧 = 𝑧 3 + 𝑧 2 + 1 について、 1. 𝑓(𝑧)が原始多項式であることを示せ。 2. 𝑓(𝑧)の原始根を𝛼とするとき、 𝑓(𝑧)によって定義される 𝐺𝐹(23 )のすべての元のべき表現、多項式表現、ベクトル表現 の対応を示せ。 3. 𝛼1234 を多項式表現で示せ。

20 拡大体での線形符号 • 考え方はGF(2)の線形符号と同じ • メッセージベクトル 𝒎、生成行列 𝐺 について符号語は 𝒄 = 𝒎𝐺 • 符号語 𝒄、検査行列 𝐻 について 𝐻𝒄𝑇 = 𝟎 • 3シンボルの繰り返し符号 1 0 1 0 1 1 • 𝒎 = (𝛼) のとき 𝒄 = 𝒎𝐺 = (𝛼 𝛼 𝛼) 𝛼 𝛼+𝛼 1 0 1 𝛼 0 • 𝐻𝒄𝑇 = = = 𝛼+𝛼 0 1 1 𝛼 0 • 𝐺 = (1 1 1)、𝐻 =