|
サイズ: 3903
コメント:
|
← 2011-01-26 21:13:57時点のリビジョン12 ⇥
サイズ: 5066
コメント:
|
| 削除された箇所はこのように表示されます。 | 追加された箇所はこのように表示されます。 |
| 行 11: | 行 11: |
| kに関する帰納法。 x ≦ (y_1∨……∨y_(i-1)∨y_(i+1)+∨……∨y_k) ∨ y_i に対してxが既約であることを用いる。 x=y ⇒ x≦y を用いて帰納法の仮定を適用。 |
''k'' に関する帰納法。 ''x'' ≦ (''y'',,1,,∨……∨''y'',,i-1,,∨''y'',,i+1,,+∨……∨''y'',,k,,) ∨ ''y'',,i,, に対して ''x'' が既約であることを用いる。 ''x'' = ''y'' ⇒ ''x'' ≦ ''y'' を用いて帰納法の仮定を適用。 |
| 行 16: | 行 16: |
| 加法+と乗法*が定義された集合Xが体であるとき、以下に示す条件を満たす。 1. Xは+について可換群をなす。すなわち、 |
加法+と乗法*が定義された集合'''X'''が体であるとき、以下に示す条件を満たす。 1. '''X'''は+について可換群をなす。すなわち、 |
| 行 22: | 行 22: |
| 1. X-{0}は*について可換群をなす。すなわち、 | 1. '''X'''-{0}は*について可換群をなす。すなわち、 |
| 行 24: | 行 24: |
| (a+b√2)*(c+d√2)を具体的に計算。 | (''a'' + ''b''√2)*(''c'' + ''d''√2)を具体的に計算。 |
| 行 28: | 行 28: |
| 1/(a*b√2)がQ(√2)の元であることを示す。分母を有理化。 | 1/(''a'' * ''b''√2)がQ(√2)の元であることを示す。分母を有理化。 |
| 行 35: | 行 35: |
| w,x∈Bとy,z∈Aを考える。 w*(x*y) = w*(x*z) ⇒ x*y = x*z ⇒ y = z とy,zが先頭にきている場合を考えることによりw*x∈Bが示せる。x*wも同様。 |
''w'' ,''x'' ∈'''B'''と''y'' ,''z'' ∈'''A'''を考える。 ''w'' * ( ''x'' * ''y'' ) = ''w'' * ( ''x'' * ''z'' ) ⇒ ''x'' * ''y'' = ''x'' * ''z'' ⇒ ''y'' = ''z'' と''y'' ,''z'' が先頭にきている場合を考えることにより ''w'' * ''x'' ∈'''B'''が示せる。''x'' * ''w'' も同様。 |
| 行 38: | 行 38: |
| Aが半群であることから従う。 | '''A'''が半群であることから従う。 |
| 行 45: | 行 45: |
| x,x',x~ ∈A,y,y',y~ ∈Cに対して(x,y)R(x',y'),(x',y')R(x~,y~)とする。<<BR>> x*y' = x'*y <<BR>> x'*y~ = x~*y' <<BR>> 右からそれぞれy~,yを掛けて、<<BR>> x*y'*y~ = x'*y*y~ <<BR>> x'*y~*y = x~*y'*y <<BR>> x'*y~*yに注目すると <<BR>> x*y'*y~ = x~*y'*y <<BR>> y'の正則性よりx*y~ = x~*y なので(x,y)R(x~,y~) |
''x'',,1,, , ''x'',,2,, , ''x'',,3,, ∈'''A''' , ''y'',,1,, , ''y'',,2,, , ''y'',,3,, ∈'''C'''に対して( ''x'',,1,, , ''y'',,1,, ) '''R''' ( ''x'',,2,, , ''y'',,2,, ) , ( ''x'',,2,, , ''y'',,2,, ) '''R''' ( ''x'',,3,, , ''y'',,3,, )とする。<<BR>> ''x'',,1,, * ''y'',,2,, = ''x'',,2,, * ''y'',,1,, <<BR>> ''x'',,2,, * ''y'',,3,, = ''x'',,3,, * ''y'',,2,, <<BR>> 右からそれぞれ ''y'',,3,, , ''y'',,1,, を掛けて、<<BR>> ''x'',,1,, * ''y'',,2,, * ''y'',,3,, = ''x'',,2,, * ''y'',,1,, * ''y'',,3,, <<BR>> ''x'',,2,, * ''y'',,3,, * ''y'',,1,, = ''x'',,3,, * ''y'',,2,, * ''y'',,1,, <<BR>> ''x'',,2,, * ''y'',,3,, * ''y'',,1,, に注目すると <<BR>> ''x'',,1,, * ''y'',,2,, * ''y'',,3,, = ''x'',,3,, * ''y'',,2,, * ''y'',,1,, <<BR>> ''y'',,2,, の準正則性より ''x'',,1,, * ''y'',,3,, = ''x'',,3,, * ''y'',,1,, なので ( ''x'',,1,, , ''y'',,1,, ) '''R''' ( ''x'',,3,, , ''y'',,3,, ) |
| 行 60: | 行 60: |
| Xからd-1個以下のベクトルを組み合わせて生成できるベクトルの種類はi個の中からd-1個以下を組み合わせるので不等式の左辺となる。 GF(2)上のm次列ベクトルは零ベクトル以外全部で2^m -1個（不等式の右辺）ある。 よって、不等式が成り立つならばxからd-1個以下のベクトルを組み合わせて生成できないベクトルが存在するのでこれをx_i+1とすればよい。 あとはx_i+1とd-1個のベクトルの一次独立性を示せば終わり。 |
'''X'''から ''d'' -1個以下のベクトルを組み合わせて生成できるベクトルの種類は ''i'' 個の中から ''d'' -1個以下を組み合わせるので不等式の左辺となる。<<BR>> '''GF'''(2) 上の ''m'' 次列ベクトルは零ベクトル以外全部で 2^m^ -1個（不等式の右辺）ある。<<BR>> よって、不等式が成り立つならば'''X'''から ''d'' -1個以下のベクトルを組み合わせて生成できないベクトルが存在するのでこれを ''x'',,i+1,,とすればよい。<<BR>> あとは ''x'',,i+1,, と'''X'''の ''d'' -1個のベクトルの一次独立性を示せば終わり。 |
| 行 65: | 行 65: |
| 左辺の1を移項して(1)の結果を利用する。i=n-1。 検査行列Hとして、(1)の条件を満たすように作られた列ベクトルx_iを並べたものを考える。符号語p = (p_1, ……, p_n)を検査すると、 p*H^T = p_1*x_1 + p_2*x_2 + …… + p_n*x_n = 0 （符号語ならば検査結果は0） これと任意のd個のベクトルが一次独立であることを用いるとp_iのうちd+1個以上は0でないことがわかる。したがって最小重みd+1の線形符号なので命題は成り立つ。 |
左辺の1を移項して(1)の結果を利用する。''i'' = ''n'' -1。<<BR>> 検査行列Hとして、(1)の条件を満たすように作られた列ベクトル ''x'',,i,, を並べたものを考える。符号語 ''p'' = ( ''p'',,1,, , ……, ''p'',,n,, ) を検査すると、<<BR>> ''p'' * H^T^ = ''p'',,1,, * ''x'',,1,, + ''p'',,2,, * ''x'',,2,, + …… + ''p'',,n,, * ''x'',,n,, = 0 （符号語ならば検査結果は0）<<BR>> これと任意の ''d'' 個のベクトルが一次独立であることを用いると ''p'',,i,, のうち ''d'' +1個以上は0でないことがわかる。したがって最小重み ''d'' +1の線形符号なので命題は成り立つ。 |
| 行 70: | 行 70: |
| * GF(2)上の線形符号において最小重みd ⇒ 最小距離d の略証<<BR>> 線形符号は群符号なので符号語は群をなす。したがって各符号語ごとの差は別の符号語で表される。式で書くと任意のx,yを符号語としてある符号語zがあり x-y = z. 従ってxとyの距離はzの重みとなるが、最小重みdなのでx-yの距離は最小d。 |
* '''GF'''(2)上の線形符号において最小重み ''d'' ⇒ 最小距離 ''d'' の略証<<BR>> 線形符号は群符号なので符号語は群をなす。したがって各符号語ごとの差は別の符号語で表される。式で書くと任意の ''x'' , ''y'' を符号語としてある符号語 ''z'' があり ''x'' - ''y'' = ''z''。従って ''x'' と ''y'' の距離は ''z'' の重みとなるが、最小重み ''d'' なので ''x'' - ''y'' の距離は最小 ''d''。 |
2010年度 情報数学期末試験略解
単位がヤバいと思う人はこれを参考に須田先生にお願いするといいことがあるかもしれませんが、正しさは保証しません。
- 問題1A
- 1,2,3,2,1の形になった
- 辞書順一直線
- 問題1B
k に関する帰納法。 x ≦ (y1∨……∨yi-1∨yi+1+∨……∨yk) ∨ yi に対して x が既約であることを用いる。 x = y ⇒ x ≦ y を用いて帰納法の仮定を適用。
- 問題2A
加法+と乗法*が定義された集合Xが体であるとき、以下に示す条件を満たす。
Xは+について可換群をなす。すなわち、
- 演算+について閉じている
- 結合律が成り立つ
- 単位元0が存在
- 任意の元に対して逆元（-1倍）が存在
X-{0}は*について可換群をなす。すなわち、
- 演算*について閉じている
(a + b√2)*(c + d√2)を具体的に計算。
- 結合律が成り立つ
- 単位元1が存在
- 任意の元に対して逆元（逆数）が存在
1/(a * b√2)がQ(√2)の元であることを示す。分母を有理化。
- 演算*について閉じている
- 分配律が成り立つ
- 詳しく書いていないものはほぼ自明か実数体の性質から従う。
- 問題2B
- 半群は演算について閉じていることと結合律を示せばよい。
- 演算が閉じているか
w ,x ∈Bとy ,z ∈Aを考える。 w * ( x * y ) = w * ( x * z ) ⇒ x * y = x * z ⇒ y = z とy ,z が先頭にきている場合を考えることにより w * x ∈Bが示せる。x * w も同様。
- 結合律
Aが半群であることから従う。
- 演算が閉じているか
- 反射律，対称律，推移律を示せばよい。可換であることに注意。
- 反射律
- 自明。
- 対称律
- これも自明。
- 推移律
x1 , x2 , x3 ∈A , y1 , y2 , y3 ∈Cに対して( x1 , y1 ) R ( x2 , y2 ) , ( x2 , y2 ) R ( x3 , y3 )とする。
x1 * y2 = x2 * y1
x2 * y3 = x3 * y2
右からそれぞれ y3 , y1 を掛けて、
x1 * y2 * y3 = x2 * y1 * y3
x2 * y3 * y1 = x3 * y2 * y1
x2 * y3 * y1 に注目すると
x1 * y2 * y3 = x3 * y2 * y1
y2 の準正則性より x1 * y3 = x3 * y1 なので ( x1 , y1 ) R ( x3 , y3 )
- 反射律
- 半群は演算について閉じていることと結合律を示せばよい。
- 問題3A
- 解けませんでした……
- 問題3B
Xから d -1個以下のベクトルを組み合わせて生成できるベクトルの種類は i 個の中から d -1個以下を組み合わせるので不等式の左辺となる。
GF(2) 上の m 次列ベクトルは零ベクトル以外全部で 2m -1個（不等式の右辺）ある。
よって、不等式が成り立つならばXから d -1個以下のベクトルを組み合わせて生成できないベクトルが存在するのでこれを xi+1とすればよい。
あとは xi+1 とXの d -1個のベクトルの一次独立性を示せば終わり。
左辺の1を移項して(1)の結果を利用する。i = n -1。
検査行列Hとして、(1)の条件を満たすように作られた列ベクトル xi を並べたものを考える。符号語 p = ( p1 , ……, pn ) を検査すると、
p * HT = p1 * x1 + p2 * x2 + …… + pn * xn = 0 （符号語ならば検査結果は0）
これと任意の d 個のベクトルが一次独立であることを用いると pi のうち d +1個以上は0でないことがわかる。したがって最小重み d +1の線形符号なので命題は成り立つ。GF(2)上の線形符号において最小重み d ⇒ 最小距離 d の略証
線形符号は群符号なので符号語は群をなす。したがって各符号語ごとの差は別の符号語で表される。式で書くと任意の x , y を符号語としてある符号語 z があり x - y = z。従って x と y の距離は z の重みとなるが、最小重み d なので x - y の距離は最小 d。