2001年度情報数学

レポート提出者のリスト
 次の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値を計算
し、フレームチェックシーケンスの値と異なった
場合には、終端装置でフレーム誤りとして破棄。
 「ワイドLANサービスのインタフェース 第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 

2×2の実行列の集合は、積の演算に関してモノ
イド。可換ではない。正則行列の集合は群をなす。
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).

環の例:2×2の実行列の集合は、行列の和と積
に関して環をなす。行列の積は可換ではない。
11
可換環、単位的環

環 R において「・」が可換であるとき R を可換環
という。

環 R において 「・」に関する単位元が存在すると
きR を単位的環という。( <R,・,1> がモノイド)
モノイドであるから「・」の
逆元は存在しなくても良い。

単位的可換環の例:
整数環 <Z, +,・>、単位元は1。
Q, R, C (複素数)も単位的可換環である。
 {0,1}, ,   は単位元1を持つ可換環。ここに
x  y  ( x  y) mod 2, x  y  ( x  y) mod 2.
12
体


R が次の条件を満たすとき、体 (field) という。
 Rは「+」に関してアーベル群である。
 Rの「・」は結合律を満たす。(半群)
環
 R の「+」と「・」は分配律を満たす。
 Rー{ 0 } が「・」に関して群になる。
 Rの「・」の単位元1が存在する。
この「・」の単位元1と 0 とは異なる。
体の例:Q, R, C はいずれも体である。
要素が少なくとも
二つある。
簡単な体であるが符号理論に
おいて重要な役割を果たす。
体の例


13
Z 2   {0,1}, ,   は単位元1を持つ可換環であ
るが、体でもある。
x  y  ( x  y) mod 2, x  y  ( x  y) mod 2.

0
1

0
1
0
0
1
0
0
0
1
1
0
1
0
1
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
0
1
2
4
0
1
2
3
0
0
0
0
0
0
0
0
0
1
0
1
2
1
0
1
2
3
2
0
2
1
2
0
2
0
2
3
0
3
2
1
Z4 の2には逆元が存在しない。
もし 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)
送信ビット列を多項式と見なしたものP(X)、生成
多項式G(X)、生成多項式の最高次数をnとした時、
P(X)・Xn / G(X) の余りをCRC符号とする。
【例】
送信ビット列 11001000 (P(X)=X7+X6+X3)
生成多項式G(X)=X6+X2
P(X)・X6 / G(X) = X7+X6+X2
必ず5次以下になる
余り X4
このとき、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
問5:
2006年度定期試験問題
 整数の集合
Z は、加算(+)という演算に
関して0を単位元 (unit element)とする 群
(group)をなす。この理由を丁寧に説明せよ。
次の3つのことが成立つので、整数の集
合 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 は単位元である。
(注:この群はアーベル群となる。その点につ
いては解答の中で触れなくても良いとし
た。)