[場所1E501（月曜日5限）]
HPに行く
manabaに行く
今回もハミングの誤り訂正符号の話をしてもらいました。
$S$ をアルファベットの集合とします。
$S^n$ の元のことを $n$ 文字のメッセージということにします。
$C\subset S^n$ を符号とします。符号とはメッセージ全体のある部分集合のことを
いうのでした。
$d$ をハミング距離とします。
(これが本当に距離であることは先週確かめてもらいました。)
このとき、$d(C)=\min\{d(x,y)|x, y\in C\text{かつ}x\neq y\}$ と定義します。
また、$C$ が $t$ 個の誤りを直す ($C$ corrects $t$ errors)とは、
任意の $v\in C$ に対して、$d(u,v)\le t$ となる $u\in C$ はたかだか一つである。
ことと定義します。
今日解説してもらったところは、
$C$ が $t$ 個の誤りを直すことと $d(C)\ge 2t+1$ であることは同値
の部分です。
筆者によれば、「この証明は簡単にチェックできる」とのことですので、
やってもらいました。
数学の本で、簡単にチェックできると書いてあるところは、
証明することはもちろん簡単にできるので、読者が埋めて読みなさい
ということです。一から全て書いてあるようなきっちりとした教科書でしたら
全て書いてありますが、今回のような本は、基礎を目的とした本ではないので、
証明を書いてしまいますと、本題になかなか入れず、だらだらしてしまいます。
証明は、もちろん、イメージだけで証明するのではなく、定義にあるもののみを
用いて証明を作ります。
(証明)
(必要性)
$C$ が $t$ 個の誤りを直すとします。
そのとき、$d(C)\le 2t$ と仮定します。
$u,v\in C$ で、$d(u,v)=s\le 2t$ であるものをとります。
このとき、$u$ と $v$ の違うDigit のうち、$\left\lfloor\frac{s}{2}\right\rfloor$ を直し
たメッセージを $w$ とします。$s-\left\lfloor\frac{s}{2}\right\rfloor$ は間違えたままです。
よって、$d(u,w)=\left\lfloor\frac{s}{2}\right\rfloor\le \frac{s}{2}\le t$ であり、
$d(w,v)=s-\left\lfloor\frac{s}{2}\right\rfloor\le s-\frac{s+1}{2}=\frac{s-1}{2}< t$
となります。
しかし、$C$ が $t$ 個の誤りを直すはずなのに、$w\in S^n$ は $d(w,v),d(w,u)\le t$
となってしまい、矛盾。よって、背理法から $d(C)\ge 2t+1$ が成り立つ。
(十分性)
$d(C)\ge 2t+1$ であるとします。
そのとき、$C$ が $t$ 個の誤りを直さないと仮定します。
このとき、ある $u\in S^n$ に対して、$v,w\in C$ ($u\neq w$)が存在して、
$d(u,v)\le t$ かつ $d(u,w)\le t$ が成り立つ。
このとき、距離空間の三角不等式を用いて、$d(v,w)\le d(v,u)+d(u,w)\le t+t=2t$ となります。
よって、$d(C)$ の定義から、$d(C)\le 2t$ となり矛盾。
よって、背理法から $C$ は $t$ 個の誤りを直すということになります。
これにより、命題が証明されたことになります。
また、$C$ が線形コードである場合には、
$$d(C)=\min\{d(0,w)|w\neq 0\}$$
であることも証明してもらいました。
また、ハミングの線形コードに入る前に、
線形代数の重要な話が書いてありました。
ベクトル空間 $V$ に対して、その部分ベクトル空間 $W$ を表す方法は
２通りあり、それは、
そのような ${\bf x}$ をいくつかのベクトルの線形和の形に表すことを意味します。
つまり、部分ベクトル空間の元を
33-Miniatures のこれ以降のハミングの理論の内容に入っていくのですが、
例題を通して理解していきましょう。
HPに行く
manabaに行く
今回もハミングの誤り訂正符号の話をしてもらいました。
$S$ をアルファベットの集合とします。
$S^n$ の元のことを $n$ 文字のメッセージということにします。
$C\subset S^n$ を符号とします。符号とはメッセージ全体のある部分集合のことを
いうのでした。
$d$ をハミング距離とします。
(これが本当に距離であることは先週確かめてもらいました。)
このとき、$d(C)=\min\{d(x,y)|x, y\in C\text{かつ}x\neq y\}$ と定義します。
また、$C$ が $t$ 個の誤りを直す ($C$ corrects $t$ errors)とは、
任意の $v\in C$ に対して、$d(u,v)\le t$ となる $u\in C$ はたかだか一つである。
ことと定義します。
今日解説してもらったところは、
$C$ が $t$ 個の誤りを直すことと $d(C)\ge 2t+1$ であることは同値
の部分です。
筆者によれば、「この証明は簡単にチェックできる」とのことですので、
やってもらいました。
数学の本で、簡単にチェックできると書いてあるところは、
証明することはもちろん簡単にできるので、読者が埋めて読みなさい
ということです。一から全て書いてあるようなきっちりとした教科書でしたら
全て書いてありますが、今回のような本は、基礎を目的とした本ではないので、
証明を書いてしまいますと、本題になかなか入れず、だらだらしてしまいます。
証明は、もちろん、イメージだけで証明するのではなく、定義にあるもののみを
用いて証明を作ります。
(証明)
(必要性)
$C$ が $t$ 個の誤りを直すとします。
そのとき、$d(C)\le 2t$ と仮定します。
$u,v\in C$ で、$d(u,v)=s\le 2t$ であるものをとります。
このとき、$u$ と $v$ の違うDigit のうち、$\left\lfloor\frac{s}{2}\right\rfloor$ を直し
たメッセージを $w$ とします。$s-\left\lfloor\frac{s}{2}\right\rfloor$ は間違えたままです。
よって、$d(u,w)=\left\lfloor\frac{s}{2}\right\rfloor\le \frac{s}{2}\le t$ であり、
$d(w,v)=s-\left\lfloor\frac{s}{2}\right\rfloor\le s-\frac{s+1}{2}=\frac{s-1}{2}< t$
となります。
しかし、$C$ が $t$ 個の誤りを直すはずなのに、$w\in S^n$ は $d(w,v),d(w,u)\le t$
となってしまい、矛盾。よって、背理法から $d(C)\ge 2t+1$ が成り立つ。
(十分性)
$d(C)\ge 2t+1$ であるとします。
そのとき、$C$ が $t$ 個の誤りを直さないと仮定します。
このとき、ある $u\in S^n$ に対して、$v,w\in C$ ($u\neq w$)が存在して、
$d(u,v)\le t$ かつ $d(u,w)\le t$ が成り立つ。
このとき、距離空間の三角不等式を用いて、$d(v,w)\le d(v,u)+d(u,w)\le t+t=2t$ となります。
よって、$d(C)$ の定義から、$d(C)\le 2t$ となり矛盾。
よって、背理法から $C$ は $t$ 個の誤りを直すということになります。
これにより、命題が証明されたことになります。
また、$C$ が線形コードである場合には、
$$d(C)=\min\{d(0,w)|w\neq 0\}$$
であることも証明してもらいました。
また、ハミングの線形コードに入る前に、
線形代数の重要な話が書いてありました。
ベクトル空間 $V$ に対して、その部分ベクトル空間 $W$ を表す方法は
２通りあり、それは、
- 一次独立なベクトル ${\bf v}_1\cdots,{\bf v}_n\in V$ で生成される線形空間として、 $W$ を表す。
- $A{\bf x}={\bf 0}$ なる連立一次方程式の解全体として $W$ を表す。
そのような ${\bf x}$ をいくつかのベクトルの線形和の形に表すことを意味します。
つまり、部分ベクトル空間の元を
方程式による表示を基底による生成表示に変えなさい。
という表示の変換問題だということになります。
なので、反対に、生成表示からベクトル全体を解にもつ方程式表示に変えなさい。
という問題もあります。そのような問題は、双対空間の基底を求める問題となるので
一年生の線形代数ではあまりやられていないような気がします。
33-Miniatures のこれ以降のハミングの理論の内容に入っていくのですが、
例題を通して理解していきましょう。
0 件のコメント:
コメントを投稿