(57)【特許請求の範囲】
【請求項１】
互いに直交する異なる方向の誤り訂正符号を付加することによって積符号ブロック化されたデータに対し、各方向の誤り訂正をラインごとに順次行なう誤り訂正装置であって、
第１の方向の誤り訂正において誤りを訂正できなかった符号のライン番号を記憶するライン番号記憶手段と、
前記ライン番号記憶手段に記憶されたライン番号を消失情報として第２の方向の所定ラインについて消失位置多項式の係数を算出する消失位置多項式算出手段と、
当該所定ライン上の符号に対するシンドローム多項式を求めるシンドローム多項式算出手段と、
前記シンドローム多項式と前記消失情報とに基づいて、消失数値多項式の係数を算出する消失数値多項式算出手段と、
代入する係数と変数とを切換えることにより、前記消失位置多項式の消失位置パターンおよび前記消失数値多項式の消失数値パターンを選択的に算出する多項式演算手段と、
前記消失位置多項式算出手段によって算出された係数を当該多項式算出手段に代入して得られた消失位置パターンを記憶する記憶手段と、
前記消失数値多項式算出手段によって算出された係数を前記多項式算出手段に代入して得られた消失数値パターンと当該記憶手段に記憶された消失位置パターンとに基づいて消失パターンを算出する消失パターン演算手段とを備えた、誤り訂正装置。
【請求項２】
前記ライン番号記憶手段によって記憶されるライン番号は、誤りを訂正できなかった確率の高い符号のライン番号を含むことを特徴とする、請求項１に記載の誤り訂正装置。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
この発明は誤り訂正装置に関し、特に、デジタルデータの受信再生システムにおいて、積符号ブロック化された受信再生データに対して各方向の符号の誤り訂正を順次行なう誤り訂正装置に関する。
【０００２】
【従来の技術】
デジタル伝送システムやコンピュータの周辺装置においては、デジタルデータの信頼性を上げるため、誤り訂正符号が用いられる。最近では、受信再生側の処理能力の向上とともに、符号長・冗長度の大きいロングディスタンスコードの積符号といった高度な訂正能力を持つ符号が使われるようになってきた。
【０００３】
図７はこのような積符号がデジタルデータ（情報シンボル）に付加される態様を模式的に示す図である。図７を参照して、積符号は一般に、縦横の異なる方向の誤り訂正符号を組合せたものであり、より特定的には、情報シンボルの縦方向に対して付加された外符号のパリティＰＯと、情報シンボルおよびＰＯの横方向に対して付加された内符号のパリティＰＩとから構成される。
【０００４】
それぞれの誤り訂正符号としては、バイト単位の誤り訂正が可能なリード・ソロモン（ＲＳ）が符号が用いられることが多く、図７の例では、ＰＯ方向の誤り訂正符号は、符号長ｎ０  ，情報長ｋ０  ，最小距離ｄ０  のＲＳ符号であり、ＰＩ方向の誤り訂正符号は、符号長ｎｉ  ，情報長ｋｉ  ，最小距離ｄｉ  のＲＳ符号である。
【０００５】
なお、ここでｄｉ  ＝２ｔｉ  ＋１，ｄ０  ＝２ｔ０  ＋１の関係が成り立っているものとする。
【０００６】
このように２つの方向のＲＳ誤り訂正符号が付加されて積符号ブロック化されたデータの受信再生側でのデコード（誤り訂正）は、一般に、各方向の符号の誤り訂正を繰返すことにより行なわれる。誤り訂正そのものの方式としては、以下に説明する検出訂正および消失訂正の２種類の方式が存在する。
【０００７】
検出訂正は、大きくは以下のステップから構成される：
（１）  受信再生した符号からシンドローム多項式を求める；
（２）  シンドローム多項式から誤り位置多項式および誤り数値多項式を求める；
（３）  誤り位置多項式からチェーンサーチ法により誤り位置を求め、その位置に対する誤りパターンを求めて誤り訂正を行なう；
（４）  （３）により求めた誤り位置に対する誤りパターンを求めて訂正を行なう。
【０００８】
（２）の検出訂正時における誤り位置多項式および誤り数値多項式は符号のパリティ長を２ｔとすると、それぞれ次式となる。
【０００９】
【数１】
0003583905.tif 000002
【００１０】
ただし、それぞれ最大次数の場合を示してある。
（１），（２）式から（４）の誤りパターンは、（３）式で求まる。
【００１１】
【数２】
0003583905.tif 000003
【００１２】
ここでαはガロア体の元であり、Ｌｉ  はｉ番目の誤り位置であるので、次式を満足する。
【００１３】
【数３】
0003583905.tif 000004
【００１４】
積符号では一方の符号をデコードした結果、訂正不能であった場合、その符号と他方の符号が共有するシンボルの位置を消失位置とすることで、検出訂正の２倍の訂正能力がある消失訂正を行なうことも可能である。
【００１５】
このような消失訂正は、大きくは次のステップから構成される：
（１）  受信再生した符号からシンドローム多項式を求める；
（２）  消失位置から得られる消失位置多項式を用いて、シンドローム多項式を修正し、消失数値多項式を求める；
（３）  消失位置に対して消失パターンを求めて誤り訂正を行なう。
【００１６】
（２）の消失訂正における消失位置多項式は最大で２ｔ次の多項式となるので、次の（４）式となり、消失数値多項式は最大で２ｔ−１次の多項式であるので、（５）式となる。
【００１７】
【数４】
0003583905.tif 000005
【００１８】
（４），（５）式より、消失パターンは（６）式で求まる。
【００１９】
【数５】
0003583905.tif 000006
【００２０】
ここでＬｉ  はｉ番目の消失位置であり、次式を満足する。
【００２１】
【数６】
0003583905.tif 000007
【００２２】
これらの処理により、ＲＳ・ロングディスタンス符号の誤り訂正を行なうことができる。
【００２３】
【発明が解決しようとする課題】
しかしながら、積符号の誤り訂正では、両方向とも検出訂正を行なってもよいが、より訂正能力の高い消失訂正を用いることが要求される。しかし、検出訂正に比べて消失訂正を用いると、より次数の高い多項式の演算を行なう必要があるため、回路規模が増大するという問題点があった。
【００２４】
それゆえに、この発明の主たる目的は、積符号デコード時に消失訂正を実行可能としながらも、回路規模を抑えることのできるような誤り訂正装置を提供することである。
【００２５】
【課題を解決するための手段】
請求項１に係る発明は、互いに直交する異なる方向の誤り訂正符号を付加することによって積符号ブロック化されたデータに対し、各方向の誤り訂正をラインごとに順次行なう誤り訂正装置であって、第１の方向の誤り訂正において誤りを訂正できなかった符号のライン番号を記憶するライン番号記憶手段と、この記憶されたライン番号を消失情報として第２の方向の所定のラインについて消失位置多項式の係数を算出する消失位置多項式算出手段と、当該所定ライン上の符号に対するシンドローム多項式を求めるシンドローム多項式算出手段と、シンドローム多項式と消失情報とに基づいて、消失数値多項式の係数を算出する消失数値多項式算出手段と、代入する係数と変数を切換えることにより、消失位置多項式の消失位置パターンおよび消失数値多項式の消失数値パターンを選択的に導出する多項式演算手段と、算出された係数を当該多項式算出手段に代入して得られた消失位置パターンを記憶する記憶手段と、算出された係数を多項式算出手段に代入して得られた消失数値パターンと記憶された消失位置パターンとに基づいて、消失パターンを算出する消失パターン演算手段とを備えて構成される。
【００２６】
請求項２に係る発明では、請求項１のライン番号記憶手段によって記憶されるライン番号は、誤りを訂正できなかった確率の高い符号のライン番号を含む。
【００２７】
【発明の実施の形態】
図１はこの発明による誤り訂正装置を用いた情報受信再生システムの一例としての光ディスク再生システムの構成を示す概略ブロック図である。
【００２８】
図１を参照して、光ディスク１から読み出された信号は、読み出し二値化回路２によってデジタル信号に変換された後、復調・デフォーマット回路４に与えられ、前述の図７に示した形態の積符号ブロック化されたデータに復調される。この図７に示す形態の１ブロック分のデータはバッファメモリ５に格納される。
【００２９】
一方、サーボ制御回路３は、復調・デフォーマット回路４の出力に基づいて、光ディスク１のドライブ機構（図示せず）をサーボ制御する。復調・デフォーマット回路４およびサーボ制御回路３の動作はコントローラ８によって制御される。
【００３０】
コントローラ８はさらにバッファメモリ５に格納された１ブロック分のデータに対するデコード（誤り訂正）命令を誤り訂正装置６に与える。誤り訂正装置６は、この命令に応じて、以下に述べるような誤り訂正をバッファメモリ５に格納されているデータに施す。誤り訂正が施されたデータは、コントローラ８によって制御される出力インタフェース回路７を介してバッファメモリ５から読み出される。
【００３１】
図２は図１に示した誤り訂正装置６の構成を示す具体的なブロック図である。次に、誤り訂正装置６によるＰＩ方向のＲＳ系列に対する誤り訂正（検出訂正）について説明する。ＲＡＭ２０１は図１に示したバッファメモリ３０５から読み出されたＰＩ系列のデータ１ライン分を記憶するバッファである。シンドローム演算回路２０２はＲＡＭ２０１からデータを読み出し、次式で定義されるシンドローム多項式Ｓ（ｘ）の係数Ｓｊ  を演算する。
【００３２】
【数７】
0003583905.tif 000008
【００３３】
ここて、αはガロア体ＧＦ（２８  ）の元であり、ｒｉ  はＰＩ系列のシンボルを示す。シンドローム演算回路２０２は（７），（８）式に従って演算を行ない、演算結果Ｓｊ  ｛Ｓ０  ，…，Ｓ２ｔ−１｝をシンドローム演算回路２０２内のレジスタに記憶する。
【００３４】
次に、誤り位置多項式・誤り数値多項式生成回路２０３によってシンドローム多項式の係数Ｓｊ  を元に次式により誤り位置多項式のσ（ｘ）および誤り数値多項式ω（ｘ）の係数を求める。
【００３５】
【数８】
0003583905.tif 000009
【００３６】
ここで、（９），（１０）式は誤り位置多項式σ（ｘ）を表わし、（１１），（１２）式は誤り数値多項式ω（ｘ）を表わしている。ただし、Ｅは誤りの集合を表わし、Ｌｉ  は符号上の誤り位置を示している。これらの多項式の係数とは、具体的には次式で示すものである。
【００３７】
【数９】
0003583905.tif 000010
【００３８】
誤り位置多項式・誤り数値多項式生成回路２０３は、（９），（１０），（１１），（１２）式に従って演算を行ない、演算結果σ（ｘ）｛σ（０），…，σ（ｔ）｝，ω（ｘ）｛ω（０），…，ω（ｔ−１）｝を誤り位置多項式・誤り数値多項式生成回路２０３内のレジスタに記憶する。
【００３９】
このとき、シンドローム多項式の係数から誤り位置多項式，誤り数値多項式の係数を導出するための方法として、ピーターンアルゴリズム，ユークリッドアルゴリズムなどがあるが、いずれの方法を用いて回路を構成してもよい。
【００４０】
誤り位置多項式・誤り数値多項式生成回路２０３は、求めた値σ（ｘ），ω（ｘ）を次数回路２０４に送る。次数回路２０４では、各多項式の係数が０，非０かをチェックし、非０のときの次数を出力する。
【００４１】
次に、誤りパターン生成訂正回路２０６は誤りのパターンを求める。誤りのパターンは次式のように求められる。
【００４２】
【数１０】
0003583905.tif 000011
【００４３】
ここで、（１３）式を満たすＬｉ  はｉ番目の誤り位置を表わしており、このＬｉ  に対して（１４）式を計算することにより、誤りパターンｅｉ  が求められる。このように（１３）式が成り立つか否かを判定してＬｉ  を求める方法はチェーンサーチ法として知られている。
【００４４】
一方、（１４）式におけるσ′（ｘ）はσ（ｘ）の形式微分を表わし、次式によって定義される。
【００４５】
【数１１】
0003583905.tif 000012
【００４６】
上記の（１３），（１４）および（１５）式における、次式に列挙する要素は、多項式演算回路２０５により各多項式の係数を用いて算出される。
【００４７】
【数１２】
0003583905.tif 000013
【００４８】
これらの多項式演算は、たとえばσ（ｘ）に対して、次の（１６）式〜（２０）式となる。
【００４９】
【数１３】
0003583905.tif 000014
【００５０】
図３は図２に示した多項式演算回路２０５の具体例を示す図である。図３において、多項式演算回路２０５は８ビットのレジスタ３０１〜３０５と、線形帰還回路３１１〜３１４とセレクタ３２１〜３２４とＥＸＯＲゲート３１０とから構成される。セレクタ３２１〜３２４は、初期値σｔ１，ｂｔｉ−１  …σ１  ，σ０  と線形帰還回路３１１〜３１４の出力を選択するものであり、初期値を選択すると、（１６）式の右辺の各係数がレジスタ３０１〜３０４にストアされて初期化され、ＥＸＯＲゲート３１０の出力には（１６）式の左辺のσ（α０  ）が得られる。
【００５１】
その後、１クロックサイクルでセレクタ３２１〜３２４が帰還回路３１１〜３１４側に切換えられ、各レジスタ３０１〜３０４の内容に帰還回路３１１〜３１４の出力が乗算され、各レジスタ３０１〜３０４には（１７）式の右辺の係数がストアされ、ＥＸＯＲゲート３１０の出力から（１７）式の左辺のσ（α１  ）が得られる。
【００５２】
以下、同様にして、１クロックサイクルごとに各レジスタ３０１〜３０４の内容に、線形帰還回路３１１〜３１４の出力が乗算され、（１８）式〜（２０）式のσ（α２  ）…σ（α２５５  ）がＥＸＯＲゲート３１０から出力される。
【００５３】
検出訂正のみを考える場合、ｔｉ  ＜ｔ０  であるので、図３に示した多項式演算回路２０５内の演算回路に使われるレジスタはσ（ｘ）の次数がｔ０  次なのでｔ０  個，ω（ｘ）の次数がｔ０  −１次なのでｔ０  −１個必要となる。また、σ′（ｘ）の演算は、上述の定義式からσ（ｘ）の奇数番目のレジスタの出力をＥＸＯＲすればよい。そして、多項式演算回路２０５で求められた各値が誤りパターン生成・訂正回路２０６へ送られる。
【００５４】
誤りパターン生成・訂正回路２０６は多項式演算回路２０５から出力される次式を用いて誤りのパターンｅｉ  を求める。
【００５５】
【数１４】
0003583905.tif 000015
【００５６】
誤りパターンｅｉ  は誤りパターン生成・訂正回路２０６内のガロア体除算器により算出される。σ（α−Ｌｉ  ）＝０となるときのシンボルを訂正するため、一旦ＲＡＭ２０１から相当するシンボルを読み出して、訂正してＲＡＭ２０１に書き戻される。このようにして、検出訂正処理を行ない、誤っているシンボルが訂正される。
【００５７】
上記のように誤り訂正処理が行なわれるが、必ずしも訂正ができているとは限らない。訂正の信頼性を図るため、信頼性を数値で表わす手段と、フラグで示す手段が設けられている。これについて説明する。チェーンサーチ法で検出された誤りの個数は、誤り数カウンタ２０７によって計数される。誤り位置多項式・誤り数値多項式生成回路２０３によって求められた誤り位置多項式が正確なものであれば、検出される誤りの個数と誤り位置多項式の次数は一致する。訂正の正誤は、符号長ｎｉ  に対してチェーンサーチ終了後、訂正ステータス回路２０８で誤り位置多項式の次数と誤り数カウンタ２０７の出力を比較回路２１５で比較することによって判定される。
【００５８】
訂正ステータス回路２０８は、訂正の正誤を示すフラグと行なわれた訂正が符号語の能力を限界まで使った訂正なのかどうかを示すフラグを出力する。たとえば、ＰＩ系列の符号の場合、ｔｉ  個の訂正が行なわれたときが限界訂正である。能力を限界まで使った訂正では、それ以外の場合に比べ、誤訂正の確率が高くなることが知られている。
【００５９】
消失ラインカウンタ２０９は、訂正ステータス回路２０８の出力フラグが訂正の誤りを示したり、限界訂正を示す度に、誤りの可能性を示すカウンタの値を指定した数値分加算する。また、ラインカウンタ２１０はデコードが終了したライン数を計数している。そのラインに対する訂正ステータスが誤りおよび限界訂正であったときには、そのライン数に相当するラインカウンタ２１０の値がＲＡＭ２１１に格納される。これはＰＯ系列の訂正を行なう際の消失ライン情報として用いられる。
【００６０】
このようにして、訂正の信頼性を、消失ラインカウンタ２０９の数値と、訂正ステータス回路２０８のフラグで表現している。１ラインの訂正が終了した後、訂正ステータスが正しいと判断された場合、ＲＡＭ２０１の訂正済符号語がバッファメモリ３０５へ書き戻される。
【００６１】
以上の動作を繰返し、ＰＩ方向の各符号語に対する誤り訂正が実行される。ＰＩ方向の訂正終了後、消失ラインカウンタ２０９の出力が消失数レジスタ２１２に格納される。なお、各演算回路の動作制御は、シーケンスコントローラ２１３によって行なわれる。
【００６２】
次に、ＰＯ方向の符号語に対する訂正動作について説明する。ＰＯ方向ではＰＩ方向と同様な検出訂正の他に、ＲＡＭ２１１に格納されている消失ライン情報を用いた訂正方法もある（消失訂正）。消失訂正では予めＰＯ系列の符号語上の誤り位置が、消失位置として検出されているので誤り（消失）位置多項式も次式により前記消失位置より求めることができる。
【００６３】
【数１５】
0003583905.tif 000016
【００６４】
このため、誤り（消失）数値多項式のみを求めれば訂正処理が行なえる。たとえばユークリッドアルゴリズムでは、消失数値多項式はシンドローム多項式および消失位置多項式を用いて、（２２）式により求まる。
【００６５】
【数１６】
0003583905.tif 000017
【００６６】
このとき、消失パターンは（２３）式となり、最大で２ｔ０  個のシンボルの訂正が可能となる。
【００６７】
【数１７】
0003583905.tif 000018
【００６８】
ここで、消失訂正の場合、（２１）式の次数は２ｔ０  ，（２２）式の次数は２ｔ０  −１次であり、多項式演算回路２０５によって両多項式の演算を同時に行なうためには、図６に示した回路において、４ｔ０  −１の線形帰還シフトレジスタが必要となる。しかし、ＰＩ系列の符号とＰＯ系列の符号が図７に示すように直交している場合は、ＰＯ系列の符号上の消失位置はどの符号でも同じなる。たとえば、図７において、ＰＩ系列の７ライン目の符号が訂正不能となった場合、すべてのＰＯ系列の符号上で７番目のシンボルが消失位置となる。すなわち、どの符号を訂正する場合でも（２１）式は同一の多項式となり、（２３）式の分母の値は毎回同じになる。したがって、（２１）式の係数の算出と（２３）式の分母の値は一度演算した後に記憶すれば再度計算する必要がない。
【００６９】
図４はＰＯ消失訂正時の動作を説明するためのフローチャートである。次に、図２および図４を参照して、消失訂正時の動作について説明する。まず、消失位置多項式生成回路２１４は、ステップＳ１においてＲＡＭ２１１に格納されている消失ライン情報を用いて（２１）式の係数を算出する。次に、多項式演算回路２０５はステップＳ２において、消失位置に対する（２３）式の分母の値（消失位置パターン）を算出してＲＡＭ２１１へ格納する。
【００７０】
次に、各ラインに対する訂正処理について説明する。ＰＯ方向の消失訂正では、ステップＳ３において、バッファメモリ３０５からＰＯ系列の符号語１ライン分が読み出されてＲＡＭ２０１に格納される。次に、シンドローム演算回路２０５はステップＳ４において、シンドローム多項式の係数Ｓｊ  ，（ｊ＝０…２ｔ０  −１）を算出する。次に、消失数値多項式生成回路２１７は、ステップＳ５において、シンドローム多項式の係数およびＲＡＭ２１１に格納されている消失ライン情報を用いて（２２）式の消失数値多項式を算出する。そして、多項式演算回路２０５はステップＳ６において、消失位置に対する消失数値パターンすなわち次式を算出する。
【００７１】
【数１８】
0003583905.tif 000019
【００７２】
ここで、多項式演算回路２０５は消失位置多項式と消失数値多項式に対する演算を同時にする必要がないため、初期化する係数の値を変えることで、各演算で回路を共用化できる。したがって、図６に示すように、同時に演算するとした場合に４ｔ０  −１個の線形帰還シフトレジスタが必要であったのに対して、図５に示すように２ｔ０  個の線形帰還シフトレジスタで回路を構成できる。図５は消失位置多項式と消失数値多項式の演算を共用した場合の多項式演算回路のブロック図であり、この図５は図６に比べて簡略化できることは明らかである。
【００７３】
さらに、多項式演算回路２０５による消失位置に対する演算と同時にＲＡＭ２１１からその位置に対する（２３）式の分母の値が読み出され、ステップＳ７において、誤りパターン生成訂正回路２０６によって消失のパターンが生成される。そのパターンによってＲＡＭ２０１内のシンボルが訂正され、ステップＳ８においてＲＡＭ２０１の符号語がバッファメモリ３０５に書き戻される。以上ステップＳ３からＳ７の処理がＰｏ系列のすべてのラインに対して行なわれる。このようにして、検出した消失ライン情報を用いて消失訂正処理を行ない、誤っているシンボルが訂正される。
【００７４】
【発明の効果】
以上のように、この発明によれば、第１の方向に対して検出訂正を行なった後、第２の符号語の消失位置に対する消失位置パターンを予め演算して記憶しておき、各符号の訂正を行なう際には消失数値パターンのみを演算し、消失位置パターンは記憶されている値を用いて訂正を行なうようにしたので、消失位置多項式の演算回路と消失数値多項式の演算回路を多項式演算回路として共用化できるため、回路規模を縮小できる。
【図面の簡単な説明】
【図１】この発明による誤り訂正装置を用いた光ディスク再生システムの構成を示す概略ブロック図である。
【図２】図１に示した誤り訂正装置の構成を示すブロック図である。
【図３】図２に示した多項式演算回路のブロック図である。
【図４】消失訂正動作を説明するためのフローチャートである。
【図５】多項式演算回路のブロック図である。
【図６】消失位置多項式と消失数値多項式の演算を共用化しない場合の多項式演算回路のブロック図である。
【図７】積符号がデジタルデータに付加される態様を模式的に示す図である。
【符号の説明】
１  光ディスク
２  読み出し二値化回路
３  サーボ制御回路
４  復調デフォーマット回路
５  バッファメモリ
６  誤り訂正装置
７  出力インタフェース回路
８  コントローラ
２０１，２１１  ＲＡＭ
２０２  シンドローム演算回路
２０３  誤り位置多項式・誤り数値多項式生成回路
２０４  次数回路
２０５  多項式演算回路
２０６  誤りパターン生成訂正回路
２０７  誤り数カウンタ
２０８  訂正ステータス回路
２０９  消失ラインカウンタ
２１０  ラインカウンタ
２１２  消失数レジスタ
２１３  シーケンスコントローラ
２１４  消失位置多項式生成回路
２１５  比較回路
２１６  設定レジスタ
２１７  消失数値多項式生成回路
３０１〜３０５  レジスタ
３１１〜３１４  帰還回路
３２１〜３２４  セレクタ
【図１】
0003583905.tif 000020
【図２】
0003583905.tif 000021
【図３】
0003583905.tif 000022
【図４】
0003583905.tif 000023
【図５】
0003583905.tif 000024
【図６】
0003583905.tif 000025
【図７】
0003583905.tif 000026