SSブログ

CIRCの復号法と訂正,補正確立 特集CD-ROM(5)(月刊ASCII 1986年6月号10) [月刊アスキー廃棄(スクラップ)]

特集記事「CD-ROM 徹底研究 CD-ROMのすべて 第3回 デジタル信号処理」をスクラップして読み返す。難しい数式が出てきて手ごわい記事だ。理解できないのは分かっているがスクラップせずにはいられない。
CIRCの復号法と訂正,補正確立
 CIRCの復号法は,C1,C2の復号でどれだけの能力を持たせるかによって種々の方法が考えられる.その中で,C1,C2ともに2重誤り訂正を行い,C2においてC1のポインタ情報を有効に使用する方法をスーパーストラテジーといい,信頼性の高い復号法として知られている.
 図9にスーパーストラテジーのC1,C2復号法を示す.基本的な考え方は次のとおりである.

ASCII1986(06)c09CD-ROM_図09W829.jpg
 ○1重エラーのみ無条件で訂正する
 ○2重エラーの時には基本的にミス訂正の可能性があるものとして対処する

・C1系列:2重エラー訂正を行い,シンボルはすべて誤りありのフラグを立てる
・C2系列:C2系列から見たエラーの大きさをいつもチェックし,かつC1のシンボル単位のフラグをチェックする
 エラー訂正,検出能力の評価は次のようにして行う.ただし,エラーは各シンボル単位で完全ランダムに発生するものとする.また計算上,エラーレートが比較的良い状態であると仮定する.復号法はCIRCスーパーストラテジーであり,C1,C2とも2重誤り訂正を行う。
 (1)訂正能力
 あるシンボルが訂正不能になる場合を調べ,その確率を計算すれば簡易訂正不能確率が計算される.ここで,
Psi:訂正不能確率
Sc1,Sc2:C1,C2系列でのシンドロームによるエラーの大きさ
Nc1:C2複合器で受信したC1ポインタの数
 スーパーストラテジーにおいて訂正不能になるケースは2種類ある。
ASCII1986(06)c07CD-ROM_数式図(i)Psi(1)_W220.jpg (i) Psi
注目シンボルは1種であり
S c1 ≧ "3", S c1 ≧ "3"

 すなわち,C1系列でみて3シンボル以上のエラーで訂正不能であり,C2系列でみても3シンボル以上のエラーで訂正不能の場合である.この時,

Ps1 (1) C 2 27 × ( C 2 31 ) 3 · Ps 9 3.53× 10 10 · P s 9

 すなわち,C1系列でみて3シンボル以上のエラーの場合と,2シンボルエラーの場合があり,C2系列では2シンボルエラー(3シンボル以上のエラーは(i)に含まれる)だが,ポインタが5以上立っていて訂正不能の場合である。
ASCII1986(06)c08CD-ROM_数式図(ii)P_W136.jpg (ii) P
注目シンボルは2種あり
S c1 ≧ "3" or = "2"
S c2 = "2", N c1 5
 すなわち,C1系列でみて3シンボル以上のエラーの場合と,2シンボルエラーの場合があり,C2系列では2シンボルエラー(3シンボル以上のエラーは(i)に含まれる)だが,ポインタが5以上立っていて訂正不能の場合である。
Ps1 (2) ( 27× C 3 26 + C 2 27 × C 2 25 ) × ( C 2 31 ) 2 × ( C 2 32 ) 3 × Ps 12 4.63× 1018 · Ps 12
 よって,
Psi Psi (1) + Psi (2) 3.53× 1010 · Ps 9 + 4.63× 1018 · Ps 12
(2)検出能力
 Reed-Solomon符号*1が検出ミス(見逃し,誤訂正など)する場合は,最小距離*2 5であるから次のようなケースである.
 ○3シンボルエラーを2シンボルエラーと見誤る
 ○4シンボルエラーを1シンボルエラーと見誤る
 ○5シンボルエラーをエラーなしと見誤る
 例として,どういう場合に4シンボルエラーを1シンボルエラ--と見誤るかを考察してみよう.
 今,4シンボルエラー(ea,eb,ec,ed)を1シンボルエラー(ei)とみなす時,
S0 = ( α0 ) a e a + ( α0 ) b e b + ( α0 ) c e c + ( α0 ) d e d = ( α0 ) i e i
S1 = ( α1 ) a e a + ( α1 ) b e b + ( α1 ) c e c + ( α1 ) d e d = ( α1 ) i e i
S2 = ( α2 ) a e a + ( α2 ) b e b + ( α2 ) c e c + ( α2 ) d e d = ( α2 ) i e i
S3 = ( α3 ) a e a + ( α3 ) b e b + ( α3 ) c e c + ( α3 ) d e d = ( α3 ) i e i

 この連立方程式から次の関係が導かれる.
eb = ( αi + αa ) ( αa + αc ) ( αa + αd ) ( αi + αb ) ( αb + αc ) ( αb + αd ) · α l ( a-b ) · ea = αx · ea
ec = ( αi + αa ) ( αa + αb ) ( αa + αd ) ( αi + αc ) ( αc + αb ) ( αc + αd ) · α l ( a-c ) · ea = αy · ea
ed = ( αi + αa ) ( αa + αb ) ( αa + αc ) ( αi + αd ) ( αd + αb ) ( αd + αc ) · α l ( a-d ) · ea = αz · ea
ただしx,y,zはa,b,c,d,iにより決定
 a,b,c,d,iの位置を決めると,eb,ec,edはeaにより決定される.すなわち,検出ミスが出るのは任意のea(=0)が与えられた時,eb,ec,edが,それぞれa0~a254のうち1通りしかない.従って、a,b,c,d,iの位置を決めた時,4シンボルエラー(ea,eb,ec,ed)を1シンボルエラー(ei)と見誤る確率は,
約1/2553  である.
 同様に,3シンボルエラーを2シンボルエラーと見誤る確率は
約1/2552
 である。
 さらに,5シンボルエラーが発生した時,それをエラーなしと見誤る確率は,
約1/2554
 である.
 CIRCの種々のデコード法において,検出ミスとなるのは次・のとおりである.
 ○Ciで検出ミスし,C2で訂正あるいは検出できない
 ○C2で検出ミスをする
 ○C1,C2デコードともに検出ミスは4シンボルエラーを1シンボルエラーと見なす場合が圧倒的に多い
 以上のもとに,検出ミスの確率を考察しよう.ここで
Psu : 検出ミス確率 Psu (1) : C1で検出ミスし,C2で訂正あるいは検出できない確率 Psu (2) : C2で検出ミスする確率
とすると,Psu(1)が2種類考えられる.
Psu (1) ―――― N c1 3 (内,エラー2) Psu (1') ―――― N c1 4 (内,エラー1)
ともにC1で検出ミスしたシンボルのみがエラーとなる.
(i) Psu(1)
Psu (1) C 2 27 × 25 × ( C 2 31 ) 2 × C 2 32 × ( C 4 31 + 31 × C 3 30 ) Ps 12 × 255-3 8.93× 109 · Ps 12 ASCII1986(06)c08CD-ROM_数式図(i)Psu(1)_W150.jpg
(ii) Psu(1')
Psu (1') 27 × C 3 26 × C 2 31 × ( C 2 32 ) 3 × ( C 4 31 + 31 × C 3 30 ) Ps 13 × 255-3 3.78× 1013 · Ps 13
ASCII1986(06)c08CD-ROM_数式図(ii)Psu(1')_W150.jpg

(iii) Psu(2)
Psu (2) ( C 4 27 + 27 × C 3 26 ) × ( C 2 31 ) 4 × Ps 12 × 255-3 2.47× 108 · Ps 12
 よって,検出ミス確率は,
Psu = (i)+(ii)+(iii) = Psu (1) + Psu (1') + Psu (2) = 9.18 × 109 · Ps 12 + 3.78 × 1013 · Ps 13
 そこで,1ワードは2シンボルであるから,ワード補間確率をPwi,ワード検出ミス確率をPwuとすると,
Psi  ,  Psu  ≪  1
では,
Pwi = 2 Psi
Pwu = 2 Psu
 となり,これを図示すると図10のようになる.

ASCII1986(06)c10CD-ROM_図10W520.jpg
 横軸に示された光ディスクのもともとのデータが,CIRCによって,縦軸に示されるデータ品質に高められるわけである.結果的に,かなり劣悪なディスクであっても,CIRCによってほとんど完全なデータに訂正される。
 図中、ミドルコレクションストラテジーは,C1で単一誤り訂正,C2で2消失訂正を行うものであり,シングルコレクションストラテジーはC1,C2ともに単一誤り訂正を行うものである.

この連載は、「マイクロコンピュータ総合誌」と銘打っている月刊アスキーでは自分にとってかなり浮いている記事だった。こうして35年後にやっと読んでいる位だ。理解できなくともスクラップする面白さがある。
nice!(0)  コメント(0) 
共通テーマ:パソコン・インターネット

nice! 0

コメント 0

コメントを書く

お名前:[必須]
URL:[必須]
コメント:
画像認証:
下の画像に表示されている文字を入力してください。

この広告は前回の更新から一定期間経過したブログに表示されています。更新すると自動で解除されます。