レポート提出者のリスト  次のURLに掲載 http://www.goto.info.waseda.ac.jp/ ~goto/infomath.html  学内のIPアドレスからのみ閲覧 (133.9.0.0)  レポートを提出した筈なのに、学籍番号のページに掲載されない場合は、前期の授業の終了日までに、学籍番号と氏名を明記して後藤宛にメールで連絡をください。 1 Ver.2 イーサネットによる通信の基礎代数入門 algebra 2  FCS (Frame Check Sequence) 4オクテット誤り検出のために使用。生成多項式は以下の通り。 G( x)  x 32  x 26  x 23  x 22  x16  x12  x11  x  x  x  x  x  x  x 1 10 8 7 5 4 2  受信側で同様のアルゴリズムによりCRC値を計算し、フレームチェックシーケンスの値と異なった場合には、終端装置でフレーム誤りとして破棄。  「ワイドＬＡＮサービスのインタフェース第1 版」西日本電信電話株式会社 p.43 より引用 3 半群とモノイド  集合Aの上の二項演算「・」が次の性質（結合律）を満たすとき、<A,・>を半群 (semigroup) という a  (b  c)  (a  b)  c  半群<A,・>の要素 e が、すべての a∈A に対して次の性質を満たすとき、e を単位元という(1とも書く） ae  ea  a  単位元を持つ半群のことを単位半群、モノイド monoid という。 eを明示する場合の表記 <A,・, e> 4 半群とモノイドの性質  モノイドの単位元は一意に定まる。もし e と e’ とが単位元であるとすると e=e’ となる。 e  e  e'  e'  次の性質を満たす元 0 を半群の零元という。 a  A (0  a  a  0  0) 零元が存在するときは唯一である。 0  0  0'  0'0  0' 5 半群とモノイドの例  半群 <A,・> が可換 (交換可能) とは次の性質を満たすことである。 a, b  A (a  b  b  a) 例： <N,＋> は可換なモノイド。単位元は 0。 <N,×> は可換なモノイド。単位元は 1。零元が0。  T  { 0, 1, 2 } の上の演算 x  y  ( x  y mod 3) を考える  T ,,0  は可換なモノイドである。 6 文字列の作るモノイド  形式言語理論の基礎 ∑ は空でない有限集合。∑ 上の語 (word)または文字列 (string) とは、∑ の有限個の要素を並べたものである。 a1a2a3 an x  a1a2a3 an の長さは l ( x)  n である。  長さ 0 の語を空語という。空語を  と表す。  二つの語の連接 (concatenation) を下のように定義。  x  y  a1a2a3 anb1b2b3 bm  ∑ 上の語の集合を ∑＊と書く。  *, ,   はモノイドである。可換ではない。 7 群とアーベル群  モノイド<A,・,e>の要素 a に対して、Aの要素 a-1が存在して、次の性質を満たすときに、a-1を a の逆元という 1 1 aa  a a  e  モノイド A の任意の要素に逆元が存在するとき、 Aを群 (group) という。逆元は一意に定まる。 1 1 1 1 a  a  e  a  (a  a*)  (a  a)  a*  e  a*  a *  可換である群を、可換群またはアーベル群という。可換群の時には、演算「・」の代りに「＋」を使う。可換群の時には、逆元を－a と書く。 8 群とアーベル群の例  <Z, ＋, 0> はアーベル群。nの逆元はーn  <Qー{0}, ×, 1> はアーベル群。qの逆元は 1/q  平面上の点を原点を中心としてθ度回転させる操作を考える。<回転, 回転の合成, 0度回転> はアーベル群。θ度回転の逆元はーθの回転。  回転の操作を行列で表現する。単位元は単位行列。  x'   cos  sin   x        線形代数の基礎  y'   sin  cos  y   ２×２の実行列の集合は、積の演算に関してモノイド。可換ではない。正則行列の集合は群をなす。 9 中間まとめ（半群、モノイド、群）半群モノイド群結合律単位元逆元 a  (b  c)  (a  b)  c e 可換な場合もある x 1 アーベル群 10 環  集合 R の上に二つの二項演算「＋」と「・」があり、次の性質を満たすとき、R は環 (ring) である  R の要素 0 に関して <R,＋,0> はアーベル群  <R,・> は半群可換とは限らない  R の任意の要素 a, b, c に対して分配律が成立つ a  (b  c)  (a  b)  (a  c), (b  c)  a  (b  a)  (c  a).  環の例：２×２の実行列の集合は、行列の和と積に関して環をなす。行列の積は可換ではない。 11 可換環、単位的環  環 R において「・」が可換であるとき R を可換環という。  環 R において「・」に関する単位元が存在するときR を単位的環という。（ <R,・,1> がモノイド）モノイドであるから「・」の逆元は存在しなくても良い。  単位的可換環の例：整数環 <Z, +,・>、単位元は１。 Q, R, C (複素数)も単位的可換環である。  {0,1}, ,   は単位元１を持つ可換環。ここに x  y  ( x  y) mod 2, x  y  ( x  y) mod 2. 12 体   R が次の条件を満たすとき、体 (field) という。  Rは「＋」に関してアーベル群である。  Rの「・」は結合律を満たす。（半群）環  R の「＋」と「・」は分配律を満たす。  Rー{ 0 } が「・」に関して群になる。  Rの「・」の単位元１が存在する。この「・」の単位元１と 0 とは異なる。体の例：Q, R, C はいずれも体である。要素が少なくとも二つある。簡単な体であるが符号理論において重要な役割を果たす。体の例   13 Z 2   {0,1}, ,   は単位元１を持つ可換環であるが、体でもある。 x  y  ( x  y) mod 2, x  y  ( x  y) mod 2.  ０１  ０１００１０００１１０１０１ Z p   {0,1,, ( p 1)}, ,   は p が素数ならば体。 x  y  ( x  y) mod p, x  y  ( x  y) mod p. 14 演習問題剰余環 Zp が体になるとき Zp が体になるのは、pが素数のときに限る。  Zp は剰余環と呼ばれる環である。（証明略）  3 ０１２ 4 ０１２３０００００００００１０１２１０１２３２０２１２０２０２３０３２１ Z4 の２には逆元が存在しない。もし 2x≡1 mod 4 となる x が存在したと仮定すると、2x-1=4y, 2(x-2y)=1 となるが、2倍して（modでなく）本当に1になるような整数 (x-2y)は存在しない。 15 中間まとめ（環、体）環単位的環体「＋」アーベル群「・」半群「・」単位元 Rー{0} 群分配律可換な場合もある  可換でない場合に特に斜体と呼ぶことがある環Rの零因子でない要素の集合は「・」に関して半群をなす。環Rにおいて0以外に零因子がない場合に、Rは整域という。体は整域の一種である。体は単位的環でもある。 16 多項式環  F が体であり、x が変数であるとする。 an x  an1 x n n 1    a1 x  a0 , an , an 1 ,, a0  F . 上の形の式を F 上の変数 x の多項式という。この全体の集合を F[x] と書く。  F[x] の上に和と積を定義することができる。F[x]は零元として定数 0, 単位元として定数 1 を持つ単位的可換環となる。これを多項式環という。多項式の逆数が多項式となるとは限らない。 17 多項式の除法定理  多項式の次数 (degree)： f ( x)  an x  an1x n  n1 deg( f (x) ) ＝ n   a1x  a0 , an  0 f(x)および g(x) が体 F 上の多項式とする。さらに 0deg(g(x)) とする。この時、F 上の多項式 q(x)と r(x) が存在して下が成立つ。多項式の積 f ( x)  g ( x) q ( x)  r ( x)  r(0) は 0 であるか 0deg(r(x))<deg(g(x)) 条件を満たす商 q(x) と剰余 r(x) は一意に定まる。桁数が少ない例題 18 CRC (Cyclic Redundancy Check) 送信ビット列を多項式と見なしたものＰ(Ｘ)、生成多項式Ｇ(Ｘ)、生成多項式の最高次数をnとした時、Ｐ(Ｘ)・Ｘn / Ｇ(Ｘ) の余りをCRC符号とする。【例】送信ビット列 11001000 (Ｐ(Ｘ)＝Ｘ7＋Ｘ6＋Ｘ3) 生成多項式Ｇ(Ｘ)＝Ｘ6＋Ｘ2 Ｐ(Ｘ)・Ｘ6 / Ｇ(Ｘ) ＝Ｘ7＋Ｘ6＋Ｘ2 必ず5次以下になる余りＸ4 このとき、CRC符号は 010000 となる。  6ビットで表現可能引用） http://www.netlaputa.ne.jp/~hijk/study/nw/glossary.htm 「ネットワーク・スペシャリスト・用語集」を一部修正して引用した。 19 イーサネットの CRC の計算法    CRC-32で33bitの定数ビット列から32bitのCRCを得るビット列– 100000100110000010001110110110111 生成多項式 (Generation Polynomial ) で書けば下記の通り G( x)  x 32  x 26  x 23  x 22  x16  x12  x11    x10  x8  x 7  x 5  x 4  x 2  x  1 計算の手順  生成多項式を G(x) とする  送信するデータに32ビットの0をパディングして多項式表現したもの M(x)  CRC値は割算 R(x) = M(x)÷G(x) の剰余である  送信するフレームは F(x) = M(x) + R(x) 誤りの検出  正しい受信データでは、F(x)がG(x)で割り切れる 20 問５：２００６年度定期試験問題  整数の集合 Z は、加算（+）という演算に関して0を単位元 (unit element)とする群 (group)をなす。この理由を丁寧に説明せよ。次の３つのことが成立つので、整数の集合 Z は可算(+)に関して0を単位元 (unit element)とする群 (group)をなす。  [解答] (続く) (1) 整数の集合 Z は加算(+)という演算に関して結合律を満たす。すなわち、任意の整数 a, b, c ∈Z に対して a+(b+c)=(a+b)+c が成り立つ。 (2) 0が加算の単位元となる。すなわち、任意の整数 a∈Z に対して a+0=0+a=a が成り立つ。 (3) 任意の整数に対して逆元が存在する。すなわち、任意の整数 a∈ Z に対して－a が存在して次の性質を満たす。a+(－a)=(－a)+a=0、ここに 0 は単位元である。（注：この群はアーベル群となる。その点については解答の中で触れなくても良いとした。）