巡回符号 (3)

sys.pdf sys-s.pdf sys.txt 記事一覧

[4-21] ガロア拡大体（α4 = α+1）

#42: 体の拡大

体を代数的に拡大する例は高校でも学んでいます．それは複素数の定義です．すなわち，実数を係数とする多項式 x² + 1 = 0 の解 i を加えたときにも実数と同じ四則演算ができると考えました．i² + 1 = 0 ですから i² を -1 で置換することによって任意の複素数は i の高々１次の式 x + i y で表現できます．

同じことを 2 で割った剰余 {0, 1} の体 GF(2) に対して 0，1 を係数とする n 次の原始多項式の解 α を加えた四則演算で表現できる数の集合として，GF(2) の拡大体 GF(2ⁿ) を作ります．n 次の原始多項式とは GF(2ⁿ) の 0 以外の元が α のべき乗で表現できる多項式で，i² = -1 のときと同様に α のべき乗は α の高々 n - 1 次の多項式で表現できます．

Web 上に多数の分かりやすい説明がありますので詳しくはそちら（例えば [4-21]）を参照してください．

[4-19] 体の拡大 - Wikipedia
  http://ja.wikipedia.org/wiki/%E4%BD%93%E3%81%AE%E6%8B%A1%E5%A4%A7
[4-20] 代数的拡大体と最小多項式 [物理のかぎしっぽ]
  http://hooktail.sub.jp/algebra/AlgebraicExtension/
  代数的拡大とは，あくまでも拡大の仕方に関する概念であって，そこに含まれる元が代数的であるかを規定する概念ではないのです．
[4-21] ガロア体講座
  http://chichiue.hahaue.com/gf.html
  既約であっても周期が最大になるとは限らない。周期が最大になる生成多項式を原始多項式 (primitive polynomial) という。
[4-22] 原始根 - aozoragakuen.sakura
  http://aozoragakuen.sakura.ne.jp/suuron/node36.html
  定理 28：素数 p を法として原始根が存在する．

巡回符号 (2)

sys.pdf sys-s.pdf sys.txt 記事一覧

[4-17] 4を法とする積

#41: 有限体

符号理論の参考書をみると，多項式環，ガロア拡大体等，多くの用語が使われています．伝統的な説明では「群」→「環」→「体」の順に代数的構造を発展させますが，ここでは [4-17] と同様に（群には言及しないで）剰余類から始めます．

整数 x を 3 で割った剰余 x mod 3 を f(x) で表わすと，f(x)∈{0, 1, 2} です．また f(x)，f(y)の和，積を

   f(x) ＋ f(y) ＝ f(x + y)，   f(x)・f(y) ＝ f(x y)

で定義すると加法，乗法の結合法則，交換法則および分配法則が成立し，f(0)＝0，f(1)＝1 が加法，乗法の単位元になっています．さらに，任意の x について

   f(x) ＋ Y ＝ 0，   f(x)・Z ＝ 1

となる {0, 1, 2} の元 Y，Z が存在します．例えば  f(5)＋1＝2＋1＝0， f(5)・2＝2・2＝1 です． したがって整数 x を 3 で割った剰余の集合に対する四則演算が可能，つまり ({0, 1, 2}, ＋, ・) は体になっています．

しかし，整数 x を 4 で割った剰余の場合は，上図のように x y ≠ 0 でも f(x)・f(y) ＝ 0 となることがあります（体になっていない）．多項式の因数分解

   X² ＋ 3・X ＋ 2 ＝ (X ＋ 1)・(X ＋ 2)

も「 X² ＋ 3・X ＋ 2 ＝ 0 」が 「 X ＋ 1 ＝ 0 または X ＋ 2 ＝ 0 」と同値でなければ（体になっていなければ）ほとんど使い物になりません．単純に和，積を

   f(x) ＋ f(y) ＝ f(x + y)，   f(x)・f(y) ＝ f(x y)

で定義しても体になるのは素数で割った剰余の場合だけですが，幸いなことに集合の要素の数が一つの素数のべき乗に等しければ，和，積を適当に定義することにより体にできます．

[4-8] 有限体 - Wikipedia
  http://ja.wikipedia.org/wiki/%E6%9C%89%E9%99%90%E4%BD%93
[4-9] 体 (数学) - Wikipedia
  http://ja.wikipedia.org/wiki/%E4%BD%93_(%E6%95%B0%E5%AD%A6)
[4-10] 代数的構造 - Wikipedia
  http://ja.wikipedia.org/wiki/%E4%BB%A3%E6%95%B0%E7%9A%84%E6%A7%8B%E9%80%A0
[4-11] 標数 - Wikipedia
  http://ja.wikipedia.org/wiki/%E6%A8%99%E6%95%B0
  有限体 F の位数が素数 p の冪 p^f ならば、F の標数は p である。
  逆に、標数 p の有限体の位数は必ず p の冪になる。
[4-12] 剰余類環 - Wikipedia
  http://ja.wikipedia.org/wiki/%E5%89%B0%E4%BD%99%E9%A1%9E%E7%92%B0
[4-13] 合同式 - Wikipedia
  http://ja.wikipedia.org/wiki/%E5%90%88%E5%90%8C%E5%BC%8F
[4-14] 準同型 - Wikipedia
  http://ja.wikipedia.org/wiki/%E6%BA%96%E5%90%8C%E5%9E%8B
[4-15] 核 (数学) - Wikipedia
  http://ja.wikipedia.org/wiki/%E6%A0%B8_(%E6%95%B0%E5%AD%A6)
  余像 Coim(h) は h の像 Im(h) = h(S) と同型であるという命題を準同型定理という。
[4-16] 環・体(群、環、体)
  http://ufcpp.net/study/group/field.html#finite
[4-17] 有限体 - 手抜きLab＠DTPの現場
  http://chuwa.iobb.net/tech/archive/2009/05/post-1.html
  ウィキを見てみたのだけど、余計に分からなくなる罠だったわけだね。
  で、ここからが本番となるんだ。ガロア拡大体というものの説明がひつようになるんだ。
[4-18] 代数学 - [物理のかぎしっぽ]
  http://hooktail.org/misc/index.php?%C2%E5%BF%F4%B3%D8
  ※ 時間に余裕のある人はこちらの各資料をご覧下さい．

巡回符号 (1)

sys.pdf sys-s.pdf sys.txt 記事一覧

[4-7] ユークリッドの互除法

しばらく sys.pdf の第４章に関する Web 上の資料を眺めます．素人なので難しいことは書けません．また，sys.pdf では #13 で用いた一般には通用しない記号 Γ，⊿ （使用例は B2010-11.pdf や FIE2004-1248.pdf を見てください） を多用します．

#40: 素数

math.pdf では素数について全然記述がないので，素数とは何かということ程度の説明を #40 で述べます．Web 上には多くの資料がありますが，Wikipedia のいくつかの項目を挙げるに止めておきます．

[4-1] 素数 - Wikipedia
  http://ja.wikipedia.org/wiki/%E7%B4%A0%E6%95%B0
  素因数分解の一意性； 1は素数であるか； 未解決問題
[4-2] 算術の基本定理 - Wikipedia
  http://ja.wikipedia.org/wiki/%E7%AE%97%E8%A1%93%E3%81%AE%E5%9F%BA%E6%9C%AC%E5%AE%9A%E7%90%86
  ユークリッドの「原論」の7巻に実質的な証明が書かれているが、完全な形での証明はガウスの・・・
[4-3] 数論的関数 - Wikipedia
  http://ja.wikipedia.org/wiki/%E6%95%B0%E8%AB%96%E7%9A%84%E9%96%A2%E6%95%B0
[4-4] 素数定理 - Wikipedia
  http://ja.wikipedia.org/wiki/%E7%B4%A0%E6%95%B0%E5%AE%9A%E7%90%86
[4-5] 素数判定 - Wikipedia
  http://ja.wikipedia.org/wiki/%E7%B4%A0%E6%95%B0%E5%88%A4%E5%AE%9A
[4-6] 最大公約数 - Wikipedia
  http://ja.wikipedia.org/wiki/%E6%9C%80%E5%A4%A7%E5%85%AC%E7%B4%84%E6%95%B0
[4-7] ユークリッドの互除法 - Wikipedia
  http://ja.wikipedia.org/wiki/%E3%83%A6%E3%83%BC%E3%82%AF%E3%83%AA%E3%83%83%E3%83%89%E3%81%AE%E4%BA%92%E9%99%A4%E6%B3%95
  割り算の商は、有理数 n/m の連分数展開になっている。