第 章 誤り検出 訂正の原理 その ブロック符号とその復号 安達文幸 目次 誤り訂正符号化を用いる伝送系誤り検出符号誤り検出 訂正符号 7, ハミング符号, ハミング符号生成行列, パリティ検査行列の一般形符号の生成行列符号の生成行列とパリティ検査行列の関係符号の訂正能力符号多項式 安達 : コミュニケーション符号理論 安達 : コミュニケーション符号理論 誤り訂正符号化を用いる伝送系 伝送システム 送信側情報源から出た 値情報系列を符号化する. 組織符号を考えるディジタル変調波に変換して伝送受信側ディジタル変調波を復調して 値系列に変換送信された情報ビット系列に復号 R 情報源 通信路符号器 ディジタル変調器 通信路 ディジタル復調器 通信路復号器 R 受け取り 安達 : コミュニケーション符号理論 安達 : コミュニケーション符号理論
誤り検出符号 奇数誤りを検出する誤り検出符号 ビットの情報にビットの検査ビットを付け加え, +ビットの符号語に生じた奇数ビットの誤りを検出する検査ビットの生成 = + + + odの加法 符号語 安達 : コミュニケーション符号理論 7 安達 : コミュニケーション符号理論 8 検査ビットの生成 偶数パリティの法則を表わす行列 誤りの表現 誤りベクトル 送信受信 これをodの加法で表現すると + = + = 誤りベクトル = 桁目が誤りのとき =, 正しいときは =. 安達 : コミュニケーション符号理論 9 誤り検出 = + + + od の加法 であるから + + + + =である. この性質を利用すると奇数ビットの誤りを検出できる. ただし, 偶数ビット誤りは検出できない誤りベクトル= のときの受信符号語 R= =+ 誤り検出法を表わす誤り検査ベクトル ここで, とすると,, なので 偶数ビットの誤りが発生 奇数ビットの誤りが発生 安達 : コミュニケーション符号理論
安達 : コミュニケーション符号理論 = の例情報ベクトルが = のとき検査ビット = 符号語 = = 誤りベクトル = = のとき受信符号語 R=+= の数が奇数個であるから, 誤りが発生したことを検出可能 誤り検出 訂正符号 7, ハミング符号安達 : コミュニケーション符号理論 安達 : コミュニケーション符号理論 7 7, ハミング符号は, 情報ビットを ビット, 検査ビットを ビットとする符号検査ビットの生成 安達 : コミュニケーション符号理論 8 符号化符号生成の行列表現 : 符号生成行列 : 情報ベクトルここで 検査ビットの生成 7, ハミング符号
安達 : コミュニケーション符号理論 誤りベクトル誤りの表現送信受信 これを od の加法で表現すると + = + = 誤りベクトル = 桁目が誤りのとき =, 正しいときは =. 安達 : コミュニケーション符号理論 受信ベクトル,,,,,, であったとするとが 誤りベクトルとなるのとき 送信情報ベクトル 受信ベクトル R R 安達 : コミュニケーション符号理論 シンドロームパリティ検査行列 パリティ検査行列 py 符号語 符号語の集合 : 符号行列表現すると 安達 : コミュニケーション符号理論 誤りの検出 R であることから を計算する
安達 : コミュニケーション符号理論 ならば誤りありならば誤りなし 以上より, 次の誤り検出法が得られる. であるので 誤りがなければであるから 安達 : コミュニケーション符号理論 シンドロームならば誤りありならば誤りなし 従ってで表わすとベクトル シンドロームとは病気の兆候. これをとよばれる. はシンドローム ydo ビット誤りの位置誤り位置に対応する列ベクトル 安達 : コミュニケーション符号理論 7 シンドローム誤り位置に対応する検査行列の列ベクトルがシンドロームベクトルになって現れる全ての単一誤りベクトルに対してシンドロームベクトルが互いに異なるから, 単一誤りの位置が判別できて訂正可能となる第 番目のビットに誤りがあるときの例安達 : コミュニケーション符号理論 9 ビット誤りの訂正,,,,,, R シンドロームはであったとするとが 誤りベクトルのとき 送信情報同じ
安達 : コミュニケーション符号理論 単一誤りに対するシンドロームパターン 誤りベクトルシンドローム安達 : コミュニケーション符号理論 復号 への復号 送信符号語で表わす. 推定した誤りベクトルをを推定より誤りベクトル シンドロームベクトル安達 : コミュニケーション符号理論 = の証明受信信号から検査ビットを生成 : 転値 C の生成 C の生成 C の生成安達 : コミュニケーション符号理論 別の証明
安達 : コミュニケーション符号理論 7 まとめ符号生成行列, パリティ検査行列を用いた表現符号生成とシンドローム ここで情報 ビット 検査ビット ビット の生成情報 ビット から検査ビットの生成受信した検査ビット ビット R ここで安達 : コミュニケーション符号理論 個以上のビット誤り ビット誤りがあるときの復号結果 次のようにビット誤りを引き起こしてしまう. 実際の誤りベクトルから推定した誤りベクトル シンドローム ビット誤りの位置に対応する列第 ビット位置に ビット誤りがあったと誤判定安達 : コミュニケーション符号理論 でそれ以外は で ビット目に発生した時ビット目と第 しかし, ビットの誤りが第となるから誤りベクトルを正しく推定できる. でそれ以外は ビット目に発生した時 もし, ビットの誤りが第 シンドロームベクトル パリティ検査行列 安達 : コミュニケーション符号理論 結局, 次のようにビット誤りを引き起こしてしまう. したがって, 第ビットを誤って訂正 誤訂正という してしまう. になる. であるので, に等しいとすると 例えば,
安達 : コミュニケーション符号理論 8 パリティ検査行列 に要求される条件 7, ハミング符号のシンドロームベクトルパリティ検査行列 は任意に選べるわけではない. 安達 : コミュニケーション符号理論 9 行列の各列が全て違わないといけないもし, 行列の 列と 列 と は異なる が等しければ, 受信語の 桁と 桁に生じた誤りが共に同じシンドロームを与えることになるその結果, 受信語の 桁と 桁のどちらが誤ったのか区別できない 行列の列のなかに, 全て の列があってはならないもし, 行列の 列が全て の系列であったとすると, 第 桁に誤りがあっても, そのシンドロームは全て の系列となるその結果, 誤りがなかったと判断してしまう安達 : コミュニケーション符号理論 7, ハミング符号の例 シンドロームベクトル 安達 : コミュニケーション符号理論 符号生成 行列の各列を, 全て でない, 互いに異なる 元ベクトルに選べば, ビット誤りを訂正する符号が構成される次の 8 個の ビット系列 = のなかの全てが の系列を除いた 7 個の系列から作った行列 で定められる符号は, 符号長 = -=7 ビット, 情報 =-= ビットを持ち, 符号語中の ビット誤りを訂正する 7, ハミング符号である 単位行列 単位行列
誤り検出 訂正符号, ハミング符号安達 : コミュニケーション符号理論 安達 : コミュニケーション符号理論 符号生成 行列の各列を, 全て でない, 互いに異なる 元ベクトルに選べば, ビット誤りを訂正する符号が構成される次の 個の ビット系列 = のなかの全てが の系列を除いた 個の系列から作った行列 で定められる符号は, 符号長 = -= ビット, 情報 =-= ビットを持ち, 符号語中の ビット誤りを訂正する符号である 安達 : コミュニケーション符号理論 7 検査行列組織符号の検査行列各列を入れ替えて, 同じ誤り訂正能力を保ったまま組織符号にすることができる 受信したパリティ検査ビットを出力するための単位行列安達 : コミュニケーション符号理論 8 符号生成 パリティ検査ビットの生成
安達 : コミュニケーション符号理論 9 誤りの検出 R であるので 誤りがなければ, だけに依存する. は誤りベクトルしたがって, よりであるので, であるが, ところでであることからの計算 安達 : コミュニケーション符号理論 7 ならば誤りありならば誤りなしで表わす. とよばれ, これをベクトルはシンドローム ならば誤りありならば誤りなし 以上より ydo = であることを確かめよ安達 : コミュニケーション符号理論 7 安達 : コミュニケーション符号理論 7 単一誤りに対するシンドロームパターン誤りの生じた位置に対応する, 検査行列の列ベクトルが現れる
誤りベクトル シンドローム 7 8 9 生成行列, パリティ検査行列の一般形 安達 : コミュニケーション符号理論 7 安達 : コミュニケーション符号理論 79 情報系列が符号語内に現れる組織符号を考える.. R 情報伝送速度をとすると, 符号化系列の伝送速度は 次式のようになる. 情報源符号器 odd 通信路符号器 変調器通信路復調器 通信路復号器 R 情報源復号器 安達 : コミュニケーション符号理論 8 線形符号 符号は, 符号長を としたとき, 次のような 個 < の線形方程式を満たす符号語の集合として定義される.,,,,, ただし, 係数,,,,, および符号語の各要素 はまたはとし, 方程式の加法と乗法はod の演算によるものとする od の加法,, od の乗法,, 安達 : コミュニケーション符号理論 8
ハミング符号の例 ハミング符号,, 7, 7, 安達 : コミュニケーション符号理論 8 パリティ検査行列.... py quo,,,,,,,,, または行列を転置させてパリティ検査方程式を行列とベクトルで表現するとといわれ, 係数行列をパリティ検査行列という. 次線形方程式はパリティ検査方程式先の 次元安達 : コミュニケーション符号理論 8 符号の生成行列線形ベクトル空間符号は線形ベクトル空間を構成する L L L L L L v u v u u u ならばならば任意の定数に対してを線形ベクトル空間というがあり, 次の性質を満たすとき, ベクトルの集合, 従って, 符号は線形ベクトル空間になるもまた符号語であるであるので, なら, また, もまた符号語になるであり, を満たすならが 符号語 v u v u v u v u u u u u u 安達 : コミュニケーション符号理論 8 ベクトル空間は基底ベクトルの線形結合として構成される符号は, 線形ベクトル空間を張る任意の線形独立なベクトル 基底ベクトル の線形結合として表わすことができる基底ベクトルを書き並べたものを符号 の生成行列 という 行列 は符号を定める行列であるが, 生成行列 も符号を定める行列となる 安達 : コミュニケーション符号理論 8 7, ハミング符号の例ベクトル空間を張る基底ベクトルになる. もまた, 右側ビット中のの位置が異なるから, やはり線形独立であり, で求められる符号ベクトルハミング符号の検査ビットの生成式である. の個のベクトルはそれぞれの位置が異なり, 明らかに線形独立ビットの情報ビットで構成されるベクトル空間を考える.,,, 7,,,,
安達 : コミュニケーション符号理論 8 の第行と第行の線形結合になっている. これはであるが, はに対応する符号語例えば, 線形結合で与えられる. の各行のこうして生成された全ての符号語 ベクトル表現 はは次のように生成できる. そして, 符号語符号の生成行列という. つまりを個のベクトルを行列を用いて表わした行列これら 安達 : コミュニケーション符号理論 87 符号の生成行列とパリティ検査行列の関係組織符号 y od 符号化されたビット系列に ビットの情報がそのまま現れる符号を組織符号という.,,...,, od,,,,,,,, 加算で表せる. は次式のような はパリティビット数. 上式の行列演算で得られる ただし, を生成する. から符号語を用いて, 送信情報ベクトル組織符号では, 生成行列 復号生成行列 o は, 検査行列 py は である. シンドローム 安達 : コミュニケーション符号理論 88 を計算する. を用いてシンドローム検査行列,,,,,,,,, 受信した ビット情報からパリティ検査ビットを生成するための行列受信したパリティ検査ビットを出力するための単位行列,, ハミング符号の例 安達 : コミュニケーション符号理論 89 生成行列 とパリティ検査行列 との関係 I I I I I I I I 次の関係が成り立つ. であるから 演算の場合, はこのとき, ははパリティビット数, の単位行列はここで, 行列 は次式のように表わせる. od,,,,,,,,,,,,
補足 誤り検出 誤りベクトルをとすると である. ここで, 従って, 次のことが分かる. 行列の各列は全ての系列を含んではならない. ビット誤りが特定できる 訂正できる のはの各列ベクトルが全て異なる ときである. であるから ビット誤りが特定できるのはの任意のつの列ベクトルの od 加算が 互いに異なる場合である. 安達 : コミュニケーション符号理論 9 の別証明 の第 要素は, 復号器で新たに生成した 番目の検査ビット と, 符号器で生成した検査ビット とのod加算であるからになる. ただし,,,..,. 復号器で生成すなわちした検査ビット これより, 直ちに,, fo,,.., 安達 : コミュニケーション符号理論 9 最小ハミング距離 符号の訂正能力 つのベクトルのハミング重みはそのベクトルのでない要素の数として定義される. つのベクトル と との間のハミング距離は, - の重さで与えられる. と とが線形符号の符号ベクトルなら, これらのベクトルはベクトル空間を構成するから, - もまた, 符号ベクトルになる. つまり,つの符号ベクトル間のハミング距離は, 第 の符号ベクトルのハミング重みに等しい. 従って, 線形符号の最小距離は, その線形符号の全て要素がのベクトルを除くベクトルの最小のハミング重みに等しい. 安達 : コミュニケーション符号理論 9 安達 : コミュニケーション符号理論 9
誤り検出と訂正 誤り検出符号語間のハミング距離とは, つの符号語の間の互いに相異なるビット数である. d 個またはそれ以下の誤りを検出するためには, 各符号間のハミング距離が d+ であればよい.d 個の誤りによって つの符号語が他の符号語に変わることがないから, 誤りがあったと検出できる. 誤り訂正もし, 各符号間のハミング距離が + であれば, =< 個の誤りが生じた受信符号語は送信符号語より 個の位置で異なる. しかし, 他の符号語からは +- > 個の位置で異なる. 従って, その符号語を選ぶことにより送信符号語が復元される. すなわち, =< 個の誤りを訂正できる. 符号語の最小ハミング距離が d のとき d / 個の誤りまで訂正できる. d 安達 : コミュニケーション符号理論 9 安達 : コミュニケーション符号理論 9 補足 V を線形符号とし, 行列 の零空間を張るものとする. そのとき, 重さ d の各符号語に対し, の d 個の列の間に線形従属の関係がある. 又, 逆に の d 個の列を含む線形従属関係に対応した重さ d の符号語がある 証明 ベクトルv は v が成立するとき, かつそのときのみ符号語である. すなわち 行列 の第 番目の列ベクトルをで表わすと となる. つまり, 上式は, の列間の線形従属関係そのものである. 零でない係数とともに現れるの列の数は, vの中の零でない要素 の数だけあり, これはvの重さdそのものである. 同様にの列の線形従属関係の係数は, の零空間のベクトルの要素となる. 安達 : コミュニケーション符号理論 9 を検査行列 の第 番目の列ベクトルとする. つまり, このとき, ここで したがって, 次式を得る., 安達 : コミュニケーション符号理論 97
安達 : コミュニケーション符号理論 98 補足 7, v 結局, 次式を得る. であるから このとき, ハミング符号のときを考える. 安達 : コミュニケーション符号理論 99 行列 の零空間となる符号は, のすべての d- またはそれ以下の列の組み合わせが線形独立であるとき, かつそのときのみ, 少なくとも d の最小の重さ つまり, 最小ハミング重み を持つ を持つ. ハミング符号は最小距離 したがって, このそれ以下の列の線形結合がになることはない. 個の列またはの行列の各列は非零で互いに異なるから になるので, 個の列の和ではにならない. 個の列の和でになる. 列の線形結合はの第を持つ. このとき行列で重さはに対する符号語ハミング符号では, 情報ビット系列 7,,, 7, d d d 安達 : コミュニケーション符号理論 第 章 誤り訂正の効果その _ 代数的復号法を用いるときの誤り率 予定. 誤り訂正符号化を用いる伝送系. 代数的復号法による訂正能力. 代数的復号法による復号後のビット誤り率