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

アナログ信号の宿命

 アナログ信号に雑音が加わると、もはや信号と雑音は分離することができません。
信号 雑音

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

 これに対し、デジタル信号は矩形波として表現されますので、 0か1かが判別できればよく、小さな雑音は完全に取り除くことができます。
信号 雑音

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

 とは言え、雑音が大きければデジタル信号といえども正確には復元できず、 ビット誤り(0か1かの読み取りミス)が起こります。
信号 大きい雑音

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

 CD や DVD は多少擦り傷がついても雑音なく再生されます。 擦り傷がついていればビット誤りは生じているのですが、 それを自動的に訂正する工夫が符号化の段階で施されているのです。 この技術を誤り訂正符号と言います。

シンプルな誤り訂正符号の例

  • 例えばビットを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.
    などと呼ばれる様々な種類があり、 大学で習う数学 ― 線形代数、代数学、代数幾何学、離散幾何学など ― の知識を用いて設計されています。
  • それぞれ、データの冗長度、計算時間、誤り訂正能力等に違いがあり、 使用目的にふさわしいものが使われています。たとえば
    • CD では高速に計算できること
    • 惑星探査衛星では誤り訂正能力が高いこと
    が優先されます。

教訓

 この話は人の生き方に通じています。 長い人生でただの一つも誤りを犯さずに生きられる人はいません。 誤りを犯した人をすぐ非難して叩いて人格否定するのではなくて、 誤りが起こることを認め、 誤りを犯してからそれをどう修正するかでその人の真価を問いましょう。