誤り訂正符号のおはなし

今回は誤り訂正符号の概略について、はじめて聞く高校生に話すつもりでまとめます。

 

動画や音楽などのデータには通常、符号理論というものが使われています。符号理論を使うことで、多少のノイズなどが入ってしまったようなデータであっても、数学的な計算によって元のデータに戻すことができます。

 

よく知られているように、デジタルデータは究極的には 0 1 の文字列で表すことができます。どんな長さのデータであっても、細かく区切ってしまえば長さの短い文字列の集まりと考えることができますから、今回は4桁の文字列を考えることにしましょう。例えば

  (0101)

というデータがあったとします。このデータを誰かの元へ届ける際に、何らかの理由でノイズが入り、データが次のように変わってしまったとしましょう。

  (1101)  

データを受け取った側から見ると、このデータがノイズ入ってこうなってしまったのか、それとも元からこのようなデータであったのかの判断ができません。

 

そこで、ノイズが入ったかどうかをチェックできるようにするために、符号理論では次のように桁数を追加する、という工夫が行われています。

 

いま考えている4桁の文字列は合計 2^4=16 種類あります。これにそれぞれ3つずつ桁を追加し、次のように7桁の文字列を考えます。

\ \,  c_0=0000000   \  c_1=1000111

 \ \,  c_2=0100101  \  c_3=0010010

 \ \,  c_4=0001001 \   c_5=1100010

 \ \,  c_6=1010101 \   c_7=1001110

 \ \, c_8=0110111  \   c_9=0101100

  c_{10}=0011011  c_{11}=1110000

  c_{12}=1101011  c_{13}=1011100

  c_{14}=0111110  c_{15}=1111001

これらの”数字が並んだもの”は通常,ベクトルとよばれます。この場合は各成分が 0 1の7桁(7次)のベクトルです。ベクトルには足し算や定数(スカラー)倍などの計算が定義されています。今回は足し算や定数倍(とはいっても0倍と1倍しかありませんが)はそれぞれの桁ごとに行う、という規則で定義しています(なお、この16個の中だけで演算が閉じているのでこの集合 C=\{c_0,c_1, \cdots,  c_{15}\} は7次のベクトル空間にある、部分ベクトル空間などといいます。詳しくは下部の(補足)で)

 

3桁の追加により、上の文字列 c_0,c_1, \cdots,  c_{15} は7桁のベクトルに”格上げ”されました。これによって、文字列 c_0,c_1, \cdots,  c_{15} が7桁のベクトルの集合の中にポツンポツンと存在する立場になるわけです。下図の赤に相当するようなイメージ。

 :20180720084933j:plain

このポツンポツンと存在していることがノイズチェックをする上で有効です。

ベクトル間の”距離”は、各成分のうち一致していない桁の個数と定義され、”ハミング距離”と呼ばれます。

ベクトル \displaystyle  x,yのハミング距離を

  \displaystyle  d(x,y)=(相異なる桁の個数)

と定義する。

 

上の例の7桁の文字列 c_0,c_1, \cdots,  c_{15} のハミング距離 \displaystyle d(c_i,c_j) の最小値は3となっています。つまり、何か一つ c_iを選んだときに、それらの桁を少なくとも3個改変しないと別の文字列 c_j\ (i\not= i)にはならないわけです。そこで、ノイズが入るなどして元データと変わってしまった桁が1つ以下と仮定すれば、ベクトルを受け取ったとき、ハミング距離が最も近い(1以下の)符号語がただ一つ決まりますから、それが元のデータだと推測できることになります。

 

もう少し具体的にいうと、例えば符号語

  c_9=(0101100)

で成分が1箇所変わってしまったベクトル

  c_9+(1000000) =\, ( 1101100)

  c_9+(0100000) = (0 001100)

   \vdots

  c_9+(0000001)=(0101101)

はすべて c_9 とのハミング距離が1で、また c_9 以外の符号語とのハミング距離は2以上です。このことから上記の成分が誤ったベクトル

   ( 1101100)

 (0 001100)

   \vdots

 (0101101)

などを受信したとしても、元々は符号語 c_9 だったのだろう、と決定(=誤り訂正)できるのです。次図もあくまでイメージ。

 :20180720102304j:plain

以上のように、情報に多少のノイズが含まれても、多少であれば元に戻すことができるようにした技術が「符号理論」と呼ばれる分野の「誤り訂正符号」というものです。我々がYouTubeで安定して動画が見られるのも!ケータイ電話で通話ができるのも!こうした符号理論の技術があるからなんですね!

 

今回はベクトル空間の定義もろくに言わずに符号理論の概要だけを紹介しました。実際には

・4次元の情報を7次元の符号語にするとき

・受け取ったベクトルが符号語からどれぐらいずれているか

などは行列計算を行いますし、直交補空間の次元など線形代数の理論についての知識があると理解しやすい話題です。高校生に話をする際には大学の数学をきちんと勉強するとそうしたこともわかるようになるぞーなどと伝えてもいいかもしれません。

 

またいつか詳しめに符号理論は扱います。今回はこの辺で。

 

 

(補足)

今回の文字列の集合 c_0,c_1, \cdots,  c_{15}  c_1,c_2,c_3,c_4 を基底とする4次元の(部分)ベクトル空間です。

(再掲)

\ \,  c_0=0000000   \  c_1=1000111

 \ \,  c_2=0100101  \  c_3=0010010

 \ \,  c_4=0001001 \   c_5=1100010

 \ \,  c_6=1010101 \   c_7=1001110

 \ \, c_8=0110111  \   c_9=0101100

  c_{10}=0011011  c_{11}=1110000

  c_{12}=1101011  c_{13}=1011100

  c_{14}=0111110  c_{15}=1111001

 c_1,c_2,c_3,c_4 が基底になっていることと文字列が和に関して閉じていることは次のような規則からわかります(二元体 \displaystyle   F=\{0,1\}の性質上、同じベクトルを足すと c_0=0(ベクトル)になるということに注意するとよいです)

<基底2つの和>

  \displaystyle  c_1+c_2=c_5, c_1+c_3=c_6, c_1+c_4=c_7,

  \displaystyle  c_2+c_3=c_8, c_2+c_4=c_{9}, c_3+c_4=c_{10}

 <基底3つの和>

  \displaystyle  c_{1}+c_2+c_3=c_{11}, c_{1}+c_2+c_4=c_{12},

  \displaystyle  c_{1}+c_3+c_4=c_{13}, c_2+c_3+c_4=c_{14}

<基底4つの和>

  \displaystyle  c_1+c_2+c_3+c_4=c_{15}

 

 Cがベクトル空間だと何が嬉しいの?」と思われる方もいらっしゃるかもしれませんが、 C=\{c_0,c_1, \cdots,  c_{15}\} がベクトル空間である場合、

「ハミング距離の最小値d=\min\{d(c_i, c_j)| c_i, c_j\in C , i\not= j\}

「非零である桁の個数の最小値 d'=\min\{c_l| c_l\in C, c_l\not= 0  \}

と等しいことがわかります。

実際、ハミング距離の最小値d を与えるような異なるベクトルの組 c_m, c_n \in C( d=d(c_m,c_n))に対して,その差c=c_m-c_n  Cに属し、かつ0ベクトルではありません。よって d'が(0ベクトルを除く)非零である桁の個数の最小値であることから d\geqq d'が成立します。一方、0でない桁の個数が最も小さいようなベクトル(ただし0ベクトルは除く)をc_l とすればd'=d(c_l,0) であり、 dがハミング距離の最小値であることからd\leqq d' が得られます。よって d\geqq d'かつd\leqq d' なのだから当然d=d' だろう、というわけです。

 

上の記事の説明の中でC のハミング距離の最小値が 3であるとサラッとかいてありますが、それは一瞬ではわかりにくいはず。しかし「0ベクトル以外で非零である桁の個数」として考えれば簡単に3であることがわかるのです。この一例でも察せされるように、文字列の集合C が(部分)ベクトル空間であることは、計算上いろいろと都合がよいのです。

 

 (参考文献)

誤り訂正符号入門

誤り訂正符号入門

  • 作者: J.ユステセン,T.ホーホルト,阪田省二郎,栗原正純,松井一,藤沢匡哉
  • 出版社/メーカー: 森北出版株式会社
  • 発売日: 2005/09/30
  • メディア: 単行本
  • 購入: 1人 クリック: 12回
  • この商品を含むブログを見る