第10回の教材(1)   講義編 誤り訂正技術

アナログ信号の宿命

信号 雑音
信号と雑音は分離できない

デジタル信号が雑音に強い理由 その1

信号 雑音
0 か 1 かだけ判れば良いので復元できる

それでもビット誤りは起こる

信号 大きい雑音
ここまで雑音が大きいと、デジタルでも復元できない

デジタル信号が雑音に強い理由 その2: 誤り訂正技術

  • 信号の符号化に工夫を加えれば、一定範囲のビット誤りは完全に訂正できる。

シンプルな誤り訂正符号

  • ビットを3回ずつ繰り返して送信(記録)してみよう。たとえば
    • 元のデータ 1011 → 信号は 111 000 111 111

  • もし受信(読み出)した信号が
    • 111 000 110 111 
    であったなら、赤い部分にビット誤りが生じていることが判る。

  • 更に、
    • 111 000 000 111  から2ビット誤った
    と考えるより
    • 111 000 111 111  から1ビット誤った
    と考える方がもっともらしい(確率が高い)。

  • つまり送信された信号は
    • 111 000 111 111 
    であり、元のデータは
    • 1011 
    であったと判定する。

  • この方法を用いれば、3ビット中1ビットの誤りは必ず修正できる。

誤り訂正符号のアイデア

  • 必要最小限のデジタルデータを送信するのではなくおまけ(正式名「検査ビット」)を付けてから送信する。

  • おまけのつけ方を工夫して
    • 誤りの検出
    • 誤り位置の検出
    ができるようにする。

誤り訂正符号のいろいろ

  • 線形符号
  • 巡回符号
  • 有限幾何符号
  • たたみ込み符号 etc.
それぞれ、有限体上の線形代数、環論、代数幾何学、ブロック・デザイン etc. の数学を用いて設計されている。

教訓

  • 誤りは必ず起こる。
  • 誤りが生じてからどうするかで、人間の真価が問われる。