HPに行く
manabaに行く
今回は、宿題に出した Matousek のMiniature 5の発表でした。
内容として理解できるか心配でしたが、その点、大丈夫だったようです。
ただ、多くの人がそうだったように、途中で言っていることがわからなかったところが
いくつかあったようです。
ハミングの誤り訂正符号の理論
この説明をしてもらいました。
目標は、この理論を説明とその理論的な裏付け、そして例の説明をするということ
です。
この理論について全く知らない人向けた発表を意識してみると良いと思います。
以下、説明して欲しい項目です。
- 符号とは何か？
- 誤りを訂正するとはどういうことか？
- そのとき、ハミングはどのような方法をとったのか？
の、理論のアウトラインと、
- ハミング距離の定義
- その性質(ハミング距離とエラー訂正に関する関係(不等式))
に関する理論的な説明です。
誤り訂正をすることをなんとなく説明もすることはできますが、
数学を使って説明をすることもできます。
その説明のために、
- 符号とはなにか？
- そもそもメッセージとはなにか？
についての基礎理論から入る必要があります。
符号についての基礎理論
メッセージとは、アルファベット(文字)の集合 $S$ に対して、その $S$ を一列に
並べた集合 $S^n=\{(s_1,s_2,\cdots,s_n)|s_n\in S\} $ を $n$ 文字のメッセージ
(もしくは $n$ 文字のワード)といいます。
まず、メッセージとはそうした$n$ 文字のワードのことです。
あるメッセージを伝達するということは、$S^n$ の元 ${\bf v}$ のコピーを
離れた相手にことを伝えることをいいます。伝送すること自体は数学的には
何も意味はありません。
並べた集合 $S^n=\{(s_1,s_2,\cdots,s_n)|s_n\in S\} $ を $n$ 文字のメッセージ
(もしくは $n$ 文字のワード)といいます。
まず、メッセージとはそうした$n$ 文字のワードのことです。
あるメッセージを伝達するということは、$S^n$ の元 ${\bf v}$ のコピーを
離れた相手にことを伝えることをいいます。伝送すること自体は数学的には
何も意味はありません。
このとき、${\bf v}\in S^n$ を伝える時に、その情報のコピーではなく、それが
一部誤りを持って伝わったとします。
このとき、${\bf v}$ に対して ${\bf v}’\in S^n$ を受信する場合があります。
このとき、いかに、${\bf v}’$ から正しい ${\bf v}$ を復元できるか？
ということを考えることに意味があり、
それを誤り訂正符号理論(error-correcting code theory)です。
この英語の名前を見るとわかるように、error-correcting(誤りを訂正できるような)
という形容詞です。つまり、codeに誤りを訂正できるようなシステムが存在する、
つまり、コードは単なるメッセージを表す以外に、訂正する仕組みも
導入されています。
どのようにしてコードが誤りを訂正できるか？というと、
オリジナルのメッセージ(伝えたいメッセージ)と送るメッセージの間に
ギャップをつけることです。このことは、前回のblog(リンク)にも書きました。
オリジナルのメッセージの集合を $S^k$ (この部分集合かもしれない)としたら、
送信するメッセージは、$S^n$ の元となります。(一般に、$k<n$ となります。
つまり、単射な写像
$$S^k\to C\subset S^n$$
なる写像と見なせます。$S^n$ は送信するメッセージの集合となります。
単射である理由は、送った後に、再びオリジナルのメッセージが復元できないといけないからです。つまり送った像から、$S^k$ のもとの元に戻る操作が存在しなければ
ならないからです。
このとき、このメッセージの部分集合 $C\subset S^n$ をコードと言います。
よって、コードとは、メッセージの集合の部分集合となります。
一部誤りを持って伝わったとします。
このとき、${\bf v}$ に対して ${\bf v}’\in S^n$ を受信する場合があります。
このとき、いかに、${\bf v}’$ から正しい ${\bf v}$ を復元できるか？
ということを考えることに意味があり、
それを誤り訂正符号理論(error-correcting code theory)です。
この英語の名前を見るとわかるように、error-correcting(誤りを訂正できるような)
という形容詞です。つまり、codeに誤りを訂正できるようなシステムが存在する、
つまり、コードは単なるメッセージを表す以外に、訂正する仕組みも
導入されています。
どのようにしてコードが誤りを訂正できるか？というと、
オリジナルのメッセージ(伝えたいメッセージ)と送るメッセージの間に
ギャップをつけることです。このことは、前回のblog(リンク)にも書きました。
オリジナルのメッセージの集合を $S^k$ (この部分集合かもしれない)としたら、
送信するメッセージは、$S^n$ の元となります。(一般に、$k<n$ となります。
つまり、単射な写像
$$S^k\to C\subset S^n$$
なる写像と見なせます。$S^n$ は送信するメッセージの集合となります。
単射である理由は、送った後に、再びオリジナルのメッセージが復元できないといけないからです。つまり送った像から、$S^k$ のもとの元に戻る操作が存在しなければ
ならないからです。
このとき、このメッセージの部分集合 $C\subset S^n$ をコードと言います。
よって、コードとは、メッセージの集合の部分集合となります。
$S^n$ を線形空間とし、$C$ をその線形部分空間としたときに、そのようなコードを
線形コード(linear code)といいます。
例えば、$S$ を2元体 ${\mathbb F}_2$ とする場合が一般的です。
例えば、メッセージを送った時に、$C$ から外れてしまったメッセージを受信側で
受け取ったとすると、その時点でエラーが発生しているとわかります。
もちろん、$C$ から外れていなくてもエラーがないとは言えませんが、
この場合、外れたものは少なくとも修正ができるということです。
このとき、さらに、外れたコードから正しいと推定されるコードを
ただ一つ見つけることができます(正しくはそのようなコードを作ることができます)。
ハミングの考えは、外れたものから最短のものをみつけることでそれを行うことができる
ということです。
ハミング距離とは、エラーをしている部分を数えることで定義されます。
つまり、ハミング距離とは、
${\bf v}=(k_1,\cdots,k_n)$ ${\bf w}=(l_1,\cdots,l_n)$ とするときに、
$$d({\bf v},{\bf w})=|\{i\in\{1,2,\cdots,n\}|k_i\neq l_i\}|$$
線形コード(linear code)といいます。
例えば、$S$ を2元体 ${\mathbb F}_2$ とする場合が一般的です。
例えば、メッセージを送った時に、$C$ から外れてしまったメッセージを受信側で
受け取ったとすると、その時点でエラーが発生しているとわかります。
もちろん、$C$ から外れていなくてもエラーがないとは言えませんが、
この場合、外れたものは少なくとも修正ができるということです。
このとき、さらに、外れたコードから正しいと推定されるコードを
ただ一つ見つけることができます(正しくはそのようなコードを作ることができます)。
ハミングの考えは、外れたものから最短のものをみつけることでそれを行うことができる
ということです。
ハミング距離とは、エラーをしている部分を数えることで定義されます。
つまり、ハミング距離とは、
${\bf v}=(k_1,\cdots,k_n)$ ${\bf w}=(l_1,\cdots,l_n)$ とするときに、
$$d({\bf v},{\bf w})=|\{i\in\{1,2,\cdots,n\}|k_i\neq l_i\}|$$
とすることでそのハミング距離とします。
今回の授業では、このハミング距離が、一般的な距離空間の距離として定義されている
ということを示してもらいました。ちなみに、この絶対値は集合の要素の数です。
${\bf v}$ をおくったのに、外れてしまった ${\bf v}’$ に対して、ハミング距離が最短の
$C$ の元 ${\bf w}$ をみつけてやれば、コードの元として正しいと推定される元を
みつけることができますが....
コード $C\subset S^n$ を指定した時に、そのコードにかなり高確率で修正することができる
距離が存在します。それが、correct $t$ error とよばれる $t$ です。
$C$ から、$t$ なる距離は、$d(C)\ge 2t+1$ となります。$d(C)$ は $C$ に含まれる相異なる２元の最小距離です。つまり、${\bf w}$ と ${\bf v}’$ の距離が $t$ 以下であれば、
そのような ${\bf w}$ はただ一つ $C$ の中に存在し、${\bf v}$ と ${\bf w}$ かなりの
確率で同じメッセージといえます。
今回の授業では、このハミング距離が、一般的な距離空間の距離として定義されている
ということを示してもらいました。ちなみに、この絶対値は集合の要素の数です。
${\bf v}$ をおくったのに、外れてしまった ${\bf v}’$ に対して、ハミング距離が最短の
$C$ の元 ${\bf w}$ をみつけてやれば、コードの元として正しいと推定される元を
みつけることができますが....
コード $C\subset S^n$ を指定した時に、そのコードにかなり高確率で修正することができる
距離が存在します。それが、correct $t$ error とよばれる $t$ です。
$C$ から、$t$ なる距離は、$d(C)\ge 2t+1$ となります。$d(C)$ は $C$ に含まれる相異なる２元の最小距離です。つまり、${\bf w}$ と ${\bf v}’$ の距離が $t$ 以下であれば、
そのような ${\bf w}$ はただ一つ $C$ の中に存在し、${\bf v}$ と ${\bf w}$ かなりの
確率で同じメッセージといえます。
0 件のコメント:
コメントを投稿