前回は誤り訂正を行う固まりのサイズについて簡単に説明しました。サイズが大きければ大きいほど連続したエラーに対する訂正能力は上がりますが、その分最初のデータの頭出しに時間が掛かるという分けです。媒体の性質、伝達情報の性質によって最適化しなくてはいけないと云うことです。
さてここで取り上げる DVD はどうなっているかというと、データサイズは 32,768 byte と説明しましたが、こんな風なデータの固まりを一誤り訂正ブロック ECC block としています。
前にエラーの位置情報があればチェックバイトの数だけ訂正できる、そのためにはデータを転送方向にチェックするだけではなく、マトリックスに並べて縦方向でもチェックを出来るようにすればよい、という例を挙げましたが、まさにそんな風な構造になっています。
簡単に見てみます。
データをやりとりする方向は横方向です（実際には縦でも横でも関係ない）。横方向は 172 byte のデータと 10 byte のチェックデータ（パリティデータ）で構成されています。これを 192 行縦に並べてマトリックス構造にします。
縦方向に見るとデータが 192 byte あるわけですが、この 192 byte に対して 16 byte のチェックデータを付けます。ついでとばかりに縦方向につけた 172 byte x 10 行のチェックデータにも同じようにチェックデータを付けます。
実際の DVD book に記載されている手順は最初に縦につけて、その後横に付けることになっていますが結果は同じです。右下の角の部分 10 byte x 16 行はどうなっているんだと思うかも知れませんが、縦からチェックデータを付けようが横から付けようがこれも結果は同じです。証明が必要かも知れませんがここでは省略します。線型符号であってチェックデータを作るもとのデータが同じなので、計算手順を変えても結果は同じだという程度で理解しておいて下さい。
ちなみにデータの部分は 172 byte x 192 行ですので、データサイズは 33,024 byte あり、32,768 byte より 256 byte 多いです。この余剰分はアドレス情報や誤り訂正した後にさらにデータをチェックするデータが入っています。ここではこれ以上は触れないことにします。
さてこんな構造でデータとチェックデータを並べてみたのですが、どんな手順で誤り訂正を行うのかを書いてみます。まだ数学的計算方法はまだ触れません。ちなみにこういう構造を積符号と呼びます。
データが訂正できる条件とは、
・チェックデータの半分の数までなら、位置情報がなくても訂正できる。
・誤り位置が分かっていればチェックデータの数まで訂正できる。
でした。
さてこの構造によりどんな手順で訂正が行われるのか考えてみます。実際とは違うかも知れませんが、どんなことが出来るのか自分なりに考えておくと後で理解が深まると思います。
まずわかりやすく横方向にデータをチェックします。エラーがなければ次の行へスルーです。あった場合は 5 byte までの訂正を試みます。やってみたら訂正できたということで、データを修正して次の行に行きます。訂正を試みたがダメだった場合は「この行にはどこにいくつかは不明だがとにかくエラーが 6 byte 以上ある」ということでエラー行フラグを立てます。
208 行（192 + 6）すべて終えたら今度は縦方向にデータをチェックします。仮にエラー行フラグが 16 以下の場合はその行すべてがエラーだと云うことにして、すべての列に対して「この場所にエラーがある」という前提でエラー位置情報が整っていると云うことでエラー訂正を行います。この時正しいエラーに対してエラーがあっても「エラーがある、差分は 0」ということで大丈夫です。
そうやってすべての列をチェック～訂正を行えば、上述の範囲内であればすべてのデータが修正できます。すなわち横縦の 2 回の訂正動作ですべて訂正できたと云うことです。
エラー行フラグが 16 を越えていたとします。
この場合はエラー位置情報が使えませんから、一列ずつ 8 byte（16 / 2）までの訂正を試みます。これで少しも進展がなかったら訂正不可になってしまいますが、いくつか訂正できれば訂正できなかった列に対してエラー列フラグを立てます。
再び横方向に訂正を行います。今度は先ほどと違ってエラー列フラグという位置情報があるので、その値が 10 以下ならすべて訂正できてしまいます。11 以上ならば、5 byte までの訂正を行います。先ほどの縦方向の訂正が行われたときいくつかでも訂正がされていれば、訂正可能な行が増えているかも知れません。出来なかったものはエラー行フラグを立てます。
そして今度は縦方向にデータをチェックして、以下同。
実際には相当エラーが多くても横縦横（縦横縦でもよい）の 3 回で片付くようです。
2 回が普通かも知れません。
ではどんなエラーパターンが訂正できるのかというと、
たとえばこれだけエラーがあっても横縦の 2 回で訂正できてしまいます。これは最初にディスク上に欠陥があったとして 182 x 16 のエラーがあってさらにランダムにポツポツとエラーがあるような状況が想定されています。
固まりの部分のデータ数は 2,912 byte で、さらにいくらかのランダムエラーがあったとしても訂正できるわけですから、チェックデータを含むデータ数 37,856 byte に対して 8% = 8 x 10^(-2) ぐらいのエラーレートでも訂正できると云うことになります。
逆にデータエラーが少ないのに運悪く訂正できないというパターンも存在します。詳しい説明はしませんがエラーレートは 1 x 10^(-3) よりは大きいです。
DVD の誤り訂正のデータ構造は、ユーザデータ（転送すべきデータ）32,768 byte に対して、チェックデータのなどを入れて 37,856 byte のデータをディスク上に書き込んであるわけですが、データ効率としては 32,768 / 37,856 = 86.6% ということになります。これで上述のような訂正能力を手に入れたわけです。この数値が妥当かどうかはあくまでも転送媒体によります。
今回は条件を提示してその条件ならこういった流れで誤り訂正できるとしましたが、そのためには最初に戻って数学的なカラクリが必要になります。次回はその辺りに進んでいこうと思います。
さてここで取り上げる DVD はどうなっているかというと、データサイズは 32,768 byte と説明しましたが、こんな風なデータの固まりを一誤り訂正ブロック ECC block としています。
前にエラーの位置情報があればチェックバイトの数だけ訂正できる、そのためにはデータを転送方向にチェックするだけではなく、マトリックスに並べて縦方向でもチェックを出来るようにすればよい、という例を挙げましたが、まさにそんな風な構造になっています。
簡単に見てみます。
データをやりとりする方向は横方向です（実際には縦でも横でも関係ない）。横方向は 172 byte のデータと 10 byte のチェックデータ（パリティデータ）で構成されています。これを 192 行縦に並べてマトリックス構造にします。
縦方向に見るとデータが 192 byte あるわけですが、この 192 byte に対して 16 byte のチェックデータを付けます。ついでとばかりに縦方向につけた 172 byte x 10 行のチェックデータにも同じようにチェックデータを付けます。
実際の DVD book に記載されている手順は最初に縦につけて、その後横に付けることになっていますが結果は同じです。右下の角の部分 10 byte x 16 行はどうなっているんだと思うかも知れませんが、縦からチェックデータを付けようが横から付けようがこれも結果は同じです。証明が必要かも知れませんがここでは省略します。線型符号であってチェックデータを作るもとのデータが同じなので、計算手順を変えても結果は同じだという程度で理解しておいて下さい。
ちなみにデータの部分は 172 byte x 192 行ですので、データサイズは 33,024 byte あり、32,768 byte より 256 byte 多いです。この余剰分はアドレス情報や誤り訂正した後にさらにデータをチェックするデータが入っています。ここではこれ以上は触れないことにします。
さてこんな構造でデータとチェックデータを並べてみたのですが、どんな手順で誤り訂正を行うのかを書いてみます。まだ数学的計算方法はまだ触れません。ちなみにこういう構造を積符号と呼びます。
データが訂正できる条件とは、
・チェックデータの半分の数までなら、位置情報がなくても訂正できる。
・誤り位置が分かっていればチェックデータの数まで訂正できる。
でした。
さてこの構造によりどんな手順で訂正が行われるのか考えてみます。実際とは違うかも知れませんが、どんなことが出来るのか自分なりに考えておくと後で理解が深まると思います。
まずわかりやすく横方向にデータをチェックします。エラーがなければ次の行へスルーです。あった場合は 5 byte までの訂正を試みます。やってみたら訂正できたということで、データを修正して次の行に行きます。訂正を試みたがダメだった場合は「この行にはどこにいくつかは不明だがとにかくエラーが 6 byte 以上ある」ということでエラー行フラグを立てます。
208 行（192 + 6）すべて終えたら今度は縦方向にデータをチェックします。仮にエラー行フラグが 16 以下の場合はその行すべてがエラーだと云うことにして、すべての列に対して「この場所にエラーがある」という前提でエラー位置情報が整っていると云うことでエラー訂正を行います。この時正しいエラーに対してエラーがあっても「エラーがある、差分は 0」ということで大丈夫です。
そうやってすべての列をチェック～訂正を行えば、上述の範囲内であればすべてのデータが修正できます。すなわち横縦の 2 回の訂正動作ですべて訂正できたと云うことです。
エラー行フラグが 16 を越えていたとします。
この場合はエラー位置情報が使えませんから、一列ずつ 8 byte（16 / 2）までの訂正を試みます。これで少しも進展がなかったら訂正不可になってしまいますが、いくつか訂正できれば訂正できなかった列に対してエラー列フラグを立てます。
再び横方向に訂正を行います。今度は先ほどと違ってエラー列フラグという位置情報があるので、その値が 10 以下ならすべて訂正できてしまいます。11 以上ならば、5 byte までの訂正を行います。先ほどの縦方向の訂正が行われたときいくつかでも訂正がされていれば、訂正可能な行が増えているかも知れません。出来なかったものはエラー行フラグを立てます。
そして今度は縦方向にデータをチェックして、以下同。
実際には相当エラーが多くても横縦横（縦横縦でもよい）の 3 回で片付くようです。
2 回が普通かも知れません。
ではどんなエラーパターンが訂正できるのかというと、
たとえばこれだけエラーがあっても横縦の 2 回で訂正できてしまいます。これは最初にディスク上に欠陥があったとして 182 x 16 のエラーがあってさらにランダムにポツポツとエラーがあるような状況が想定されています。
固まりの部分のデータ数は 2,912 byte で、さらにいくらかのランダムエラーがあったとしても訂正できるわけですから、チェックデータを含むデータ数 37,856 byte に対して 8% = 8 x 10^(-2) ぐらいのエラーレートでも訂正できると云うことになります。
逆にデータエラーが少ないのに運悪く訂正できないというパターンも存在します。詳しい説明はしませんがエラーレートは 1 x 10^(-3) よりは大きいです。
DVD の誤り訂正のデータ構造は、ユーザデータ（転送すべきデータ）32,768 byte に対して、チェックデータのなどを入れて 37,856 byte のデータをディスク上に書き込んであるわけですが、データ効率としては 32,768 / 37,856 = 86.6% ということになります。これで上述のような訂正能力を手に入れたわけです。この数値が妥当かどうかはあくまでも転送媒体によります。
今回は条件を提示してその条件ならこういった流れで誤り訂正できるとしましたが、そのためには最初に戻って数学的なカラクリが必要になります。次回はその辺りに進んでいこうと思います。