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