# ノート
## 9/16 ソフトウェア
mail:[e-mail]
## 9/17 情報理論2
代数系と符号理論 植松友彦
## 9/23 代数学
1. 多変数多項式環

定義1.1
$K$:体 に対して$\bar{X}=x_1,\cdots,x_n$ $K[\bar{X}]=K$の要素を係数とし$\bar{X}$を変数とする多項式全体の集合
これは環になるので多項式環と呼ばれる

定義1.2
$f_1,\cdots,f_l\in K[\bar{X}]$に対して$<f_1,\cdots,f_l>=_{def} \{h_1f_1+\cdots+h_lf_l|h_1,\cdots,h_l\in K[\bar{X}]\}$

定理1.1
$I=<f_1,\cdots,f_l>$に対して以下が成り立つ
(1) $0\in I$
(2) $p,q\in I\Rightarrow p+q\in I$
(3) $p\in I\Rightarrow \forall h\in K[\bar{X}], hp\in I$

定義1.3
一般に定理1.1の性質をもつKの部分集合Iのことをイデアルと呼ぶ

定理1.2
$<f_1,\cdots,f_l>=K[\bar{X}]\Leftrightarrow <f_1,\cdots,f_l>\ni 1$
証. $Rightarrow$は明らか
$Leftarrow$ 勝手な$h\in K[\bar{X}]$に対し$p=1$として
定理1.1(3)より $h=h1\in <f_1,\cdots,f_l>$

定理1.3
勝手な部分集合$S\subset K[\bar{X}]$に対して
$\bf{V}_K(S) =_{def}\{(c_1,...,c_n)\in K^n|\forall f\in S, f(c_1,...,c_n)=0\}$
と定める(Sの)多様体と呼ばれる

例1.
$S=\{f_1,\cdots,f_l\}$なら
$\bm{V}_K(S)=f_i(X_1,...,X_n)=0
のKの中の根全体の集合
例2.
$x^2+y^2\in \bf{Q}[X,Y] (R[X,Y]orC[X,Y])$
$\bf{V}_Q(\{X^2+Y^2\})=\{(0,0)\}

定理1.3
$\bf{V}_K(\{f_1,\cdots,f_l\}=\bf{V}_K(<f_1,\cdots,f_l>)$
証. $\{f_1,\cdots,f_l\}\subset <f,...,f>$なので($\because f_i=0f_1+\cdots+0f_{i-1}+0f_i+0f_{i+1}$+0f_l$)
$\supset$が成り立つ

$\subset$
$\bar{c}=c_1\cdots,c_n$に対して
$\bar{c}=\bar{V}_K({f...f})$とすると
$f_i(\bar{c})=0$
$g\in<f_1,...,f_l>$に対して$g=h_1f_1+...+h_lf_l$とかけるので
$h(\bar{c})f(\bar{c})+...+h()f()=0$
よって$\bar{c}\in\bm{V}_K(<f...f>)

系1
$<f...f_l>=<g...g_s>$なら$f_i=0$の解は$g_i=0$に等しい
$f_i(X_1,...,X_n)\Rightarrow g_i(X_1,...,X_i)$

系2
$<f...f>\ni 1\Rightarrow\bf{V}_K(\{f_1\cdots f_l\})=\phi$

Hilbertの零点定理(弱形)
Kが代数的閉体のとき系2の逆も成り立つ
注) Kが代数的閉体出ないときは成り立たない
例. $f=X^2+1$とする
$I=<X^2+1>\subset \bf{R}[X]$
$\bf{V}_R(\{f\})=\phi$but$1\notin<X^2+1>$
すなわち$1=h(x)(x^2+1)$となる$h(x)$は存在しない

Hilbertの基底定理
勝手なイデアル$I\subset K[\bar{X}]$は有限生成元をもつ
すなわち$I=<f_1,\cdots,f_l>$となる$f_1,\cdots,f_l\in　K[\bar{X}]$が存在する

零点定理より簡単に証明できる

## 6/23 マルチメディア
テスト
マルチメディアとは...

## 6/24 情報理論
1. 線形代数と線形符号

3.3 有限体上のベクトル空間
体:四則演算ができる集合
有限体
例.$\bf F_p = \{0,1,\cdots,p-1\}$

## 6/30 代数学
2.終結式
定義2.1 終結式
$f(x)=a_0X^m+a_1X^{m-1}+\cdots+a_m(a_0+0)~(a_0\neq 0)$
$g(x)=b_0X^m+b_1X^{m-1}+\cdots+b_m(b_0+0)~(b_0\neq 0)~\in K[X]$
に対して
$R(f,g)=|画像|$
を$f,g$の終結式と呼ぶ

またこの行列をシルベスター行列という

定理2.1
$f(X)$と$g(X)$が共通因子をもつ$\Leftrightarrow R(f,g)=0$
証.
$f(X)$と$g(X)$が共通因子をもつ
$\Leftrightarrow ^\exists h(X),t(X)\in K[X],~degh<degg,degt<degf,~f(X)h(X)=g(X)t(X)$
$\because f(X)=t(X)p(X)~g(X)=h(X)p(X)$とすると$degp>1,degt<degf,degh<degg$
$\Leftrightarrow ^\exists h(X)=C_0X^{n-1}+\cdots+C_{n-1},~t(X)=d_0X^{n-1}+\cdots+d_{n-1}~(h(x)\neq0かつt(X)\neq0),$
$f(X)h(X)=g(X)t(X)$
$\Leftrightarrow ^\exists h(X)=\cdots,~f(X)=\cdots(h(X)\neq0またはf(X)\neq0)$
$\hdots$
$\Leftrightarrow ^\exists (c_0,\cdots,c_{n-1},d_0,\cdots,d_{n-1})\neq0$
$a_0c_0=b_0d_0~x^{n+n-1}の係数$
$a_1c_0+a_0c_1=b_1d_0+b_0d_1~x^{n+n-1}の係数$
$a_2c_0+a_1c_1+a_0c_2=b_2d_0+b_1d_1+b_0d_2~x^{n+n-3}の係数$
$\hdots$
$a_nc_{n-2}+a_{n-1}c_n=b_nd_{n-2}+b_{n-2}d_n~x^1の係数$
$a_nc_{n-1}=b_{n-1}d_n~x^0の係数$
$\Leftrightarrow ^\exists (c_0,\cdots,c_{n-1},d_0,\cdots,d{n-1}\neq0)$
画像2
$\Leftrightarrow R(f,g)=0$

定理2.2
$R(f,g)\in <f,g>$
つまり$R(f,g)=h(X)f(X)+t(X)g(X)$なる$h(X),t(X)\in K[X]$が存在する
さらに$h(X),t(X)$の各係数は$a_0,\cdots,a_m,b_0,\cdots,b_n$の整式(整数係数の多項式)として表される
証.
もし$R(f,g)=0$なら$h(X)=0,t(X)=0$とおけば良い
$R(f,g)\neq0$とする
画像3
の解$(c_0,\cdots,c_{n-1},d_0,\cdots,d_{n-1})$に対して
$h'(X)=c_0X^{n-1}+\cdots+c_{n-1}$
$t'(X)=d_0X^{n-1}+\cdots+d_{n-1}$と置くと
$h'(X)f(X)+t'(X)g(X)=1$
$R(f,g)\neq0$なので解は唯一つ存在しそれはclamerの公式($$)によって

飽きた

## 10/1 情報理論
1.4 ブロック符号と線形符号
定義1.1
体$F$上のブロック符号$C$とは$F^n$の部分集合のことをいう
ここで$C=\{c_1,c_2,\cdots,c_M\}\subseteq F^n$
である時$c_1,c_2,\cdots,c_M$のそれぞれを符号語といい$n$を符号長という
また$K=\frac{\log_q{M}}{n}$を伝送速度(伝送レート)という
ただし$q=|F|$とする

定義1.2
$C$が体$F$上の$(n,k)$線形符号$\Leftrightarrow C$が$F^n$の$k$次元部分空間

性質
(1) $^\forall c_1,c_2\in C,c_1+c_2\in C$
(2) $^\forall c\in C, ^\forall a\in F,ac\in C$
(3) $0\in C$
(4) $(n,k)$線形符号の符号語数$M=q^k$

## 10/8 情報理論
2 線形符号の特徴
2.1 生成行列と組織符号
定義2.1
Cを体F上の(n,k)線形符号とするとき行ベクトルがCの基底をなすようなk×n行列 をCの生成行列という

例.
$C=\{(0000),(1100),(0011),(1111)\}$は$F_2$上の(4,2)線形符号であり(1100),(0011)はCの基底であるので
$\begin{align}
\left(\begin{matrix}
1100\\
0011
\end{matrix}\right)
\end{align}$はCの生成行列
(1111)を生成行列で表すと
$\begin{align}
(1111)=(11)
\left(\begin{matrix}
1100\\
0011
\end{matrix}\right)
\end{align}$

符号化規則
F上の(n,k)線形符号Cの生成行列をGとするとき情報ベクトル$u\in F^k$は符号語$uG\in F^n$に符号化される

つまり$C=\{uG|u\in F^k\}$
また、Gの階数はkであるのでGに行基本変形と列の入れ替えを行うことで
$G'=(I_kP)$の形に変形できる
このときG'もまたCの生成行列であり
$\begin{align}
uG'&=u(I_kP)\\
&=(uI_k uP)
\end{align}$
となるのでuに対応する符号の先頭のk文字が情報ベクトルと一致する
このような先頭が情報ベクトルとなる符号を組織符号という
また情報ベクトル部分以外のところを検査ベクトルという

2.2 双対$_{そうつい}$符号とパリティ検査行列
(a) 双対符号

定義2.2 $x=(x_1,x_2,\cdots, x_n),y=(y_1,y_2,\cdots, y_n)\in F^n$に対して
$x\cdot y=x_1y_1+\cdots+x_ny_n(\in F)$をxとyの内積という

xとyは直行$\Leftrightarrow x\cdot y=0$

## 10/15 情報理論

性質
$a,b,c\in F^n,\alpha\in F$に対して
$a\cdot b=b\cdot a$
$(a+b)\cdot c=a\cdot c+b\cdot c$
$(\alpha a)\cdot b = \alpha(a\cdot b)$

定義2.3
CをF上の(n,k)線形符号とするとき
$C^\perp=\left\{v\in F^n|v\cdot c=0~^\forall c\in C\right\}$
をCの双対符号という

※Cの規定を$\{e_1,\cdots e_k\}$とするとき$v\in F^n\}$に対して
$\begin{align}
v\in C^\perp &\Leftrightarrow v\cdot c~^\forall c\in C \\
&\Leftrightarrow v\cdot e_1 + \cdot + v\cdot e_k=0 \\
&\Leftrightarrow (ve_1^T~\cdots~ve_k^T)=(0~\cdots~0) \\
&\Leftrightarrow vG^T=0
\end{align}$
以上から
$C^\perp = \left\{v\in F^n|vG^T=0\right\}$
ただしGはCの生成行列
※F上の(n,k)線形符号Cに対して$C^\perp$はF上の(n,n-k)線型符号
※線形符号Cに対して$(C^\perp)^\perp=C$

(b) パリティ検査行列
定義2.4
線形符号Cのパーリーピーポー検査行列Hとは$C^\perp$の生成行列
つまり
$C=\{v\in F^n|vH^T=0\}$
※CをF上の(n,k)線形符号とする
GをCの生成行列とするとき、F上の(n-k)×k行列Hについて
Hがパーリーピーポー検査行列$\Leftrightarrow$Hの行ベクトルが線形独立かつ$GH^T=O$

※$G=(I_k~P)$であるとき$H=(-P^T~I_{n-k})$とすればHの行ベクトルは線形独立で、
$\begin{align}
GH^T&=(I_k~P)(-P~I_{n-k})^T \\
&=-P+P\\
&=O
\end{align}$
よってHはCのパリティ検査行列

## 10/22

$GH^T=O$より
$G=(I_k~P)$の時
$H=(-P^T~I_{n-k})$

2.3 符号の最小距離
定義2.5
$\begin{align}
x=(x_1,\cdots,x_n)\\
y=(y_1,\cdots,y_n)
\end{align}$
に対し
$d_H(x,y)=\sum^n_{i=1}d(x_i,y_i)$
ただし
$\begin{align}
d(x,y)=\begin{cases}
0~(x=y)\\
1~(x≠y)
\end{cases}
\end{align}$
をx,yのハミング距離という

このとき
任意の$x,y,z\in F^n$に対し
(1)$d_H(x,y)\geq0$
$d_H(x,y)=0\Leftrightarrow x=y$
(2)$d_H(x,y)=d_H(y,x)$
(3)$d_H(x,z)\leq d_H(x,y)+d_H(y,z)$
より距離の公理を満たす

定義2.6
$x=(x_1,\cdots,x_n)\in F^n$に対して
$\begin{align}
w_H(x)&=d_H(x,o)\\
&=\sum^n_{i=1}d(x_i,0)
\end{align}$
をxのハミング重みという

定義2.7
ブロック符号C($\subset F^n$)に対し
$d_{min}(C)=min_{x,y\in C~x≠y}d_H(x,y)$
をCの最小距離といい
$w_{min}(C)=min_{x\in C~x≠0}w_H(x)$
をCの(非零の)最小重み

定理2.1
Cが線形符号の時
$d_{min}(C)=w_{min}(C)$
証明
$\begin{align}
d_{min}(C)&=min_{x,y\in C~x≠y}d_H(x,y) \\
&=min_{x,y\in C~x≠y}w_H(x-y) \\
&\geq min_{x\in C~x≠o}w_H(x) \\
&=w_{min}(C)
\end{align}$
$\begin{align}
w_{min}(C)&=min_{x\in C~x≠o}w_H(x) \\
&=min_{x\in C~x≠o}d_H(x,o) \\
&\geq min_{x,y\in C~x≠y}d_H(x,y) \\
&= d_{min}(C)
\end{align}$
証明終了

## 10/29
3 線形符号の最小距離と誤り訂正能力
3.1 通信路のモデル
省略

3.2 符号の最小距離と誤り訂正能力
定義3.1
$C$をブロック符号とし
$d_{min}(C)=d$とおく
このときCがt個以下の全ての誤りを訂正可能$\Leftrightarrow t<\frac{d}{2}$
つまり
$C$は$\left[\frac{d-1}{2}\right]$個以下の全ての誤りを訂正可能

証明
Cを体F上のブロック符号とし、$C={c_1,\cdots,c_n}$とする
ここで$S(c_i)=\{y\in F^n|d_H(c_i,y)<\frac{d}{2}\}$
とおくと
$S(c_i)\cap S(c_j)=\phi~~~~(i≠j)$
が成り立つ

$\because$ 成り立たたないと仮定すると
$x\in S(c_i)\cap S(c_j)$なる$x\in F^n$が存在するが
このとき
$\begin{align}
d_H(c_i,c_j)&\leq d_H(c_i,x)+d_H(x,c_j) \\
&=d_H(c_i,x)+d_H(c_j,x) \\
&<\frac{d}{2}+\frac{d}{2} \\
&=d
\end{align}$
となり矛盾する

符号Cのある符号語$c_i$を送信したとき$\frac{d}{2}$より少ない個数の誤りが発生したとすると受信する記号列rは$S(c_i)$に属することになる
ここまでの議論から$r\in S(c_i)\Leftrightarrow j=i$であるのでrは$c_i$に復号される

3.3 パリティ検査行列と最小距離との関係
定理3.2
C:体F上の線形符号
H:Cのパリティ検査行列
とすると
$C=\{c\in F^n|cH^T=o\}$
このとき
Hのj個の列ベクトルが線形従属
$~\Rightarrow$Cはこれらの列のいくつかに対応する成分が0でない符号語を持つ
Cが重みjの符号語を持つ
$~\Rightarrow$Hのあるj個の列ベクトルは線形従属
証明
$H=(h_1,\cdots,h_n)$とする
(1)$h_1,\cdots,h_j$が線形従属であるとすると
$a_1h_1+\cdots+a_jh_j=o$かつ$(a_1,\cdots,a_j)≠(0,\cdots,0)$なる$a_1,\cdots,a_j\in F$が存在する
このとき
$\begin{align}
(a_1,\cdots,a_j,0,\cdots,0)H^T&=a_1h_1+\cdots+a_jh_j+0h_{j+1}+\cdots+0h_n \\
&=0
\end{align}$
よって$(a_1,\cdots,a_j,0,\cdots,0)\in C$

(2)$(a_1,\cdots,a_j,0,\cdots,0)\in C~(a_i≠0)$とすると
$\begin{align}
o&=(a_1,\cdots,a_j,0,\cdots,0)H^T \\
&=a_1h_1+\cdots+a_jh_j+0h_{j+1}+\cdots+0h_n \\
&=a_1h_1+\cdots+a_jh_j
\end{align}$
よって$h_1,\cdots,h_j$は線形従属

定理3.3
C:F上の線形符号
H:Cのパリティ検査行列
$(Cの最小距離(=最小重み))=d\Leftrightarrow \begin{cases}
Hのどの(d-1)個の列ベクトルも線形独立\\
かつ\\
Hのあるd個の列ベクトルは線形従属
\end{cases}$

文末