[場所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 件のコメント:
コメントを投稿