(57)【特許請求の範囲】
【請求項１】
（ｎ×ｈ１×ｗ１）シンボルの原始データに対して冗長データを付加して誤り訂正符号化を行い、（ｎ×ｈ２×ｗ２）シンボルの誤り訂正符号を送出する符号化方法であって、ｎ個のｈ１行ｗ１列に行列配置された（ｎ×ｈ１×ｗ１）シンボルの原始データに対し、ｈ１行ｗ１列に行列配置された（ｈ１×ｗ１）シンボル毎に、行方向を（ｗ２，ｗ１）誤り訂正符号によって誤り訂正符号化を行うと共に、列方向を（ｈ２，ｈ１）誤り訂正符号によって誤り訂正符号化を行って、ｎ個のｈ２行ｗ２列の積符号を生成するステップと、前記ｎ個のｈ２行ｗ２列の積符号について、各積符号１行ｗ２シンボルずつを連結した（ｎ×ｗ２）シンボルの連結行に対し、各連結行毎の所定のインタリーブ規則に基づいて、各連結行内でシンボル単位にインタリーブを行って、ｈ２個の（ｎ×ｗ２）シンボルの連結行を生成するステップと、前記ｈ２個の行内シンボル単位インタリーブされた（ｎ×ｗ２）シンボルの連結行を順に送出するステップとを有することを特徴とする符号化方法。
【請求項２】
前記各連結行毎の所定のインタリーブ規則は、行内シンボル単位インタリーブ前のある２つの列の同一行の２つのシンボルが、行内シンボル単位インタリーブ後に、そのシンボル間隔が、行に対して複数種類存在するようにさせるものであることを特徴とする請求項１記載の符号化方法。
【請求項３】
前記ｎ個の積符号を生成するステップの後、前記ｈ２個の行内シンボル単位にインタリーブされた連結行を送出するステップの前に、前記ｎ個の積符号あるいは行内シンボル単位インタリーブされた積符号に対し、各積符号毎の所定のインタリーブ規則に基づいて、各積符号内で行単位にインタリーブを行うステップを有することを特徴とする請求項１または２記載の符号化方法。
【請求項４】
前記各積符号内で行単位インタリーブを行うステップと、前記連結行に対し連結行内でシンボル単位インタリーブを行うステップと、前記連結行を送出するステップとの３個のステップのうち、いずれか２個のステップあるいは３個全てのステップは、メモリ上に存在するシンボルを適当な順序で読み出す単一のステップからなることを特徴とする請求項１、２または３記載の符号化方法。
【請求項５】
前記原始データに識別情報が存在する場合、識別情報が存在する連結行に対する前記インタリーブ規則は、行内シンボル単位インタリーブ後に識別情報を所定位置へ配置する規則であることを特徴とする請求項１ないし４のうちいずれか１記載の符号化方法。
【請求項６】
前記各連結行内のシンボル単位インタリーブは、実質的に各積符号毎のｗ２シンボルの行内でシンボル単位にインタリーブを行うものであることを特徴とする請求項１ないし５のうちいずれか１記載の符号化方法。
【請求項７】
前記各連結行内のシンボル単位インタリーブは、実質的に各同期フレーム内でシンボル単位にインタリーブを行うものであることを特徴とする請求項１ないし６のうちいずれか１記載の符号化方法。
【請求項８】
前記各連結行毎のインタリーブ規則、あるいは、前記各連結行各部分毎のインタリーブ規則は、ランダムインタリーバあるいは亜ランダムインタリーバに基づくものであることを特徴とする請求項１ないし７のうちいずれか１記載の符号化方法。
【請求項９】
前記各連結行毎のインタリーブ規則、あるいは前記各連結行各部分毎のインタリーブ規則は、等間隔インタリーバであることを特徴とする請求項１〜７いずれか１記載の符号化方法。
【請求項１０】
前記シンボルは８ビットであり、ｈ１＝１９２，ｗ１＝１７２，ｈ２＝２０８，ｗ２＝１８２であり、前記（ｗ２，ｗ１）誤り訂正符号及び前記（ｈ２，ｈ１）誤り訂正符号は、それぞれ、ＤＶＤで用いられている（１８２，１７２）Ｒｅｅｄ−Ｓｏｌｏｍｏｎ符号及び（２０８，１９２）Ｒｅｅｄ−Ｓｏｌｏｍｏｎ符号であることを特徴とする請求項１ないし９のうちいずれか１記載の符号化方法。
【請求項１１】
（ｎ×ｈ１×ｗ１）シンボルの原始データに対して冗長データを付加して誤り訂正符号化を行い、（ｎ×ｈ２×ｗ２）シンボルの誤り訂正符号を送出する符号化回路であって、ｎ個のｈ１行ｗ１列に行列配置された（ｎ×ｈ１×ｗ１）シンボルの原始データに対し、ｈ１行ｗ１列に行列配置された（ｈ１×ｗ１）シンボル毎に、行方向を（ｗ２，ｗ１）誤り訂正符号によって誤り訂正符号化を行うと共に、列方向を（ｈ２，ｈ１）誤り訂正符号によって誤り訂正符号化を行って、ｎ個のｈ２行ｗ２列の積符号を生成する手段と、前記ｎ個のｈ２行ｗ２列の積符号について、各積符号１行ｗ２シンボルずつを連結した（ｎ×ｗ２）シンボルの連結行に対し、各連結行毎の所定のインタリーブ規則に基づいて、各連結行内でシンボル単位にインタリーブを行って、ｈ２個の（ｎ×ｗ２）シンボルの連結行を生成する手段と、前記ｈ２個の行内シンボル単位インタリーブされた（ｎ×ｗ２）シンボルの連結行を順に送出する手段とを有することを特徴とする符号化回路。
【請求項１２】
（ｎ×ｈ１×ｗ１）シンボルの原始データに対して冗長データを付加して誤り訂正符号化を行った（ｎ×ｈ２×ｗ２）シンボルの誤り訂正符号の誤り訂正を行う復号方法であって、ｈ２個の行内シンボル単位インタリーブされた（ｎ×ｗ２）シンボルの連結行を順に受入するステップと、前記ｈ２個の（ｎ×ｗ２）シンボルの連結行に対し、各連結行毎の所定のインタリーブ規則に基づいて、各連結行内でシンボル単位にデインタリーブを行って、ｎ個のｈ２行ｗ２列の積符号を生成するステップと、前記ｎ個のｈ２行ｗ２列の積符号に対し、各積符号毎に行方向の（ｗ２，ｗ１）誤り訂正符号及び列方向の（ｈ２，ｈ１）誤り訂正符号に対して誤り訂正を行うステップとを有することを特徴とする復号方法。
【請求項１３】
前記各連結行毎の所定のインタリーブ規則は、行内シンボル単位インタリーブ前のある２つの列の同一行の２つのシンボルが、行内シンボル単位インタリーブ後に、そのシンボル間隔が、行に対して複数種類存在するようにさせるものであることを特徴とする請求項１２記載の復号方法。
【請求項１４】
前記ｈ２個の行内シンボル単位にインタリーブされた連結行を受入するステップの後、前記ｎ個の積符号に対し誤り訂正を行うステップの前に、前記ｎ個の積符号あるいは行内シンボル単位にインタリーブされた積符号に対し、各積符号毎の所定のインタリーブ規則に基づいて、各積符号内で行単位にデインタリーブを行うステップを有することを特徴とする請求項１２または１３記載の復号方法。
【請求項１５】
前記各積符号内で行単位にデインタリーブを行うステップと、前記連結行を受入するステップと、前記連結行に対し連結行内でシンボル単位デインタリーブを行うステップのうち、いずれか２個のステップあるいは３個の全てのステップは、メモリ内へシンボルを適当な順序で書き込む単一のステップから成ることを特徴とする請求項１２、１３または１４記載の復号方法。
【請求項１６】
前記原始データに識別情報が存在する場合、識別情報が存在する連結行に対する前記インタリーブ規則は、行内シンボル単位インタリーブ後に識別情報を所定位置へ配置する規則であることを特徴とする請求項１２ないし１５のうちいずれか１記載の復号方法。
【請求項１７】
前記各連結行内のシンボル単位デインタリーブは、実質的に各積符号毎のｗ２シンボルの行内でシンボル単位にデインタリーブを行うものであることを特徴とする請求項１２ないし１６のうちいずれか１記載の復号方法。
【請求項１８】
前記各連結行内のシンボル単位デインタリーブは、実質的に各同期フレーム内でシンボル単位デインタリーブを行うものであることを特徴とする請求項１２ないし１７のうちいずれか１記載の復号方法。
【請求項１９】
前記各連結行毎のインタリーブ規則あるいは前記各連結行各部分毎のインタリーブ規則は、ランダムインタリーバあるいは亜ランダムインタリーバに基づくものであることを特徴とする請求項１２ないし１８のうちいずれか１記載の復号方法。
【請求項２０】
前記各連結行毎のインタリーブ規則あるいは前記各連結行各部分毎のインタリーブ規則は、等間隔インタリーバであることを特徴とする請求項１２ないし１８のうちいずれか１記載の復号方法。
【請求項２１】
前記シンボルは８ビットであり、ｈ１＝１９２，ｗ１＝１７２，ｈ２＝２０８，ｗ２＝１８２であり、前記（ｗ２，ｗ１）誤り訂正符号及び前記（ｈ２，ｈ１）誤り訂正符号は、それぞれ、ＤＶＤで用いられている（１８２，１７２）Ｒｅｅｄ−Ｓｏｌｏｍｏｎ符号及び（２０８，１９２）Ｒｅｅｄ−Ｓｏｌｏｍｏｎ符号であることを特徴とする請求項１２ないし２０のうちいずれか１記載の復号方法。
【請求項２２】
（ｎ×ｈ１×ｗ１）シンボルの原始データに対して冗長データを付加して誤り訂正符号化を行った（ｎ×ｈ２×ｗ２）シンボルの誤り訂正符号の誤り訂正を行う復号回路であって、ｈ２個の行内シンボル単位インタリーブされた（ｎ×ｗ２）シンボルの連結行を順に受入する手段と、前記ｈ２個の（ｎ×ｗ２）シンボルの連結行に対し、各連結行毎の所定のインタリーブ規則に基づいて、各連結行内でシンボル単位にデインタリーブを行って、ｎ個のｈ２行ｗ２列の積符号を生成する手段と、前記ｎ個のｈ２行ｗ２列の積符号に対し、各積符号毎に行方向の（ｗ２，ｗ１）誤り訂正符号及び列方向の（ｈ２，ｈ１）誤り訂正符号に対して誤り訂正を行う手段とを有することを特徴とする復号回路。
【請求項２３】
請求項１１記載の符号化回路を備えて構成されることを特徴とする記録装置。
【請求項２４】
請求項２２記載の復号回路を備えて構成されることを特徴とする再生装置。
【請求項２５】
請求項１１記載の符号化回路から送出される誤り訂正符号が記録されていることを特徴とする記憶媒体。
【請求項２６】
請求項１１記載の符号化回路を備えて構成されることを特徴とする送信装置。
【請求項２７】
請求項２２記載の復号回路を備えて構成されることを特徴とする受信装置。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、符号化方法、復号方法、符号化回路、復号回路、記憶装置、記憶媒体、通信装置に係り、特に、誤り訂正符号として積符号を用い、比較的短いバースト誤りに対して訂正能力が高いｎ個の積符号を誤り訂正符号として用いる符号化方法、復号方法、符号化回路、復号回路、記憶装置、記憶媒体、通信装置に関する。
【０００２】
【従来の技術】
従来から記憶媒体にデータを記憶する磁気テープ装置、磁気ディスク装置、光ディスク装置のような記憶装置や、通信回線を用いてあるいは無線によってデータを伝送する通信装置は、データの信頼性を確保するための技術として誤り訂正符号が用いられている。すなわち、例えば、記憶装置は、原始データを誤り訂正符号化することによって冗長度を持たせることにより、記憶媒体を介してデータ中に幾らかの誤りが発生した場合であっても、再生データの誤りを訂正することにより原始データを無事に得ることができるように構成されている。
【０００３】
この明細書の以後の説明において、１ビットあるいは２ビット以上のビット群の誤り訂正符号で扱うデータの所定のサイズの単位をシンボルということとする。そして、（ｎ，ｋ）誤り訂正符号は、ｋ個のシンボルの原始データをｎ個のシンボルの符号語へ誤り訂正符号化するものである。
【０００４】
記憶媒体や通信路を介することによって発生する誤りには、一般に、ランダム誤りとバースト誤りとの２種類がある。ランダム誤りは、データのシンボル位置に独立に発生する誤りであり、一方、バースト誤りは、データ中の連続したシンボルに発生する誤りである。ランダム誤りは、例えば、記憶媒体に存在する比較的小さな局部的な欠陥等により発生し、一方、バースト誤りは、例えば、記憶媒体に存在する比較的大きな傷やごみ等により発生する。
【０００５】
前述したようなランダム誤りとバースト誤りとの両方に対して良好な訂正能力を持つ誤り訂正符号として、積符号が知られている。
【０００６】
図１は従来技術による積符号のデータ配置及び送信順を説明する図、図２は従来技術による積符号での誤りが発生した場合の積符号のデータ配置例について説明する図であり、以下、図１、図２を参照して、従来技術による積符号を用いる誤り訂正符号について説明する。図１、図２において、１０１、２０１は積符号、１０２は原始データ、１０３〜１０５は冗長データ、２０２〜２０６はバースト誤りである。
【０００７】
図１に示す従来技術による積符号は、１９２行１７２列に行列配置された３３０２４シンボルの原始データ１０２に対し、行方向を（１８２，１７２）誤り訂正符号によって誤り訂正符号化を行うと共に、列方向を（２０８，１９２）誤り訂正符号によって誤り訂正符号化を行った、２０８行１８２列の積符号１０１の例である。そして、図１に示す矢印は、データの送出順を示している。すなわち、図１に示す積符号は、原始データに対して、各行毎に（１８２，１７２）誤り訂正符号で誤り訂正符号化を行って１０シンボルの冗長データ１０３を付加すると共に、各列毎に（２０８，１９２）誤り訂正符号で誤り訂正符号化を行って１６シンボルの冗長データ１０４を付加している。さらに、図示例は、冗長データ１０４に対して、各行毎に（１８２，１７２）誤り訂正符号で誤り訂正符号化を行って１０シンボルの冗長データ１０５を付加している。冗長データ１０５は、冗長データ１０３に対して、各列毎に（２０８，１９２）誤り訂正符号で誤り訂正符号化を行って１６シンボルの冗長データ１０５を付加して生成してもよい。
【０００８】
図１に示す積符号は、光ディスク装置の１つであるＤＶＤに対する記録データの誤り訂正符号であり、ＤＶＤの記録データは、１シンボルが８ビットで、行方向及び列方向共に誤り訂正符号としてＧＦ（２8 ）のReed-Solomon符号が用いられている。ＤＶＤの記録データは、この積符号の２０８個存在する行を積符号内で行単位にインタリーブを行って記憶媒体に記録され、各行の１８２シンボルは図の中に矢印で示す送出順の方向に順に記録される。
【０００９】
前述した図１に示す積符号は、各行及び各列に、それぞれ１０シンボル及び１６シンボルの冗長データが存在するため、それぞれ５シンボル及び８シンボルの誤り訂正が可能である。また、図１に示す積符号は、誤り位置が既知の場合、消失フラグを用いた消失訂正によって、各行及び各列で、それぞれ最大１０シンボル及び最大１６シンボルの誤り訂正が可能である。積符号は、ある行（列）が訂正不能となった場合、続いて行う列（行）方向の誤り訂正において訂正不能の行（列）のシンボルに消失フラグを立てることによって、消失訂正を行うことができる。
【００１０】
図１に示す積符号は、消失訂正を行うことによって、長さ１６行分すなわち３０００シンボル弱のバースト誤りを訂正することが可能である。また、積符号は、行方向及び列方向の誤り訂正を繰り返し行う反復訂正が有効となる場合があり、この場合、訂正不能の行（列）が存在してもさらに列（行）方向の誤り訂正を行い、これを繰り返すことで、積符号全体の誤りの数を徐々に減らしていき、最終的に全てを訂正することができる場合がある。この反復訂正の間に前述した消失訂正を用いれば、さらに信頼性を向上させることができる。
【００１１】
なお、誤り訂正符号の詳細に関しては、今井秀樹著「符号理論」（電子情報通信学会編、１９９０）等に記述されており、また、ＤＶＤの誤り訂正符号の詳細については、ＥＣＭＡ−２７２「120mm Rewritable Disk(DVD-RAM)」、ＩＳＯ／ＩＥＣ  １６８２４「120mm Rewritable Disk(DVD-RAM)」等の規格書に記述されている。
【００１２】
記憶媒体の高密度化や通信における転送速度の高速化は、データに発生するバースト誤りを長くする傾向にある。例えば、記憶媒体上に存在するあるごみがデータに５シンボル相当の誤りを発生させるとき、この記憶媒体の線密度を２倍に高密度化した場合、同様のごみがデータにおよそ１０シンボル相当の誤りを発生させるようになる。このため、通信における転送速度の高速化、あるいは、記憶媒体の線密度の高密度化は、いままで長さ数シンボル程度の極めて短いバースト誤りであったものが、長さ１０シンボル前後の比較的短いバースト誤りになっていくことになる。
【００１３】
しかし、積符号は、比較的短いバースト誤りに対して比較的訂正能力が弱いという問題がある。図２に示す例により、これについて説明する。
【００１４】
図２に示す例は、行方向、列方向共に２シンボルの誤り訂正が可能（消失訂正では最大４シンボルの誤り訂正が可能）な１５行１５列の積符号２０１を示している。この例において、５個の長さ５シンボルのバースト誤り２０２〜２０６が発生し、これらが図２に示すような位置に発生した場合、これら誤りは訂正不能となってしまう。
【００１５】
【発明が解決しようとする課題】
前述したように従来技術による積符号は、比較的短いバースト誤りに対して比較的訂正能力が弱く、比較的短いバースト誤りの発生の状況によっては誤り訂正を行うことができなくなる場合があるという問題点を有している。この問題点は、今後、通信における転送速度の高速化、記録媒体の線密度の高密度化が進められていくと、顕著な問題点になってくる。
【００１６】
本発明の目的は、比較的短いバースト誤りに対して訂正能力が強いｎ個の積符号を誤り訂正符号として送出する符号化方法及び符号化回路を提供することにある。
【００１７】
また、本発明の目的は、前述の誤り訂正符号を送出する符号化方法及び符号化回路において、原始データに識別情報が存在する場合であって、この識別情報が所定位置に配置された誤り訂正符号を送出する符号化方法及び符号化回路を提供することにある。
【００１８】
また、本発明の目的は、前述の誤り訂正符号を送出する符号化方法及び符号化回路において、ＤＶＤの誤り訂正符号との違いが少ない、すなわち、ＤＶＤの誤り訂正符号との互換が容易な誤り訂正符号を送出する符号化方法及び符号化回路を提供することにある。
【００１９】
さらに、本発明の目的は、前述の誤り訂正符号の復号を行う復号方法及び復号回路を提供することにある。
【００２０】
また、本発明の目的は、前述の誤り訂正符号を送出する符号化方法あるいは符号化回路、また、この復号を行う復号方法あるいは復号回路を用いた記憶装置及び記憶媒体及び通信装置を提供することにある。
【００２１】
【課題を解決するための手段】
前述の目的を達成するため、本発明による符号化方法及び符号化回路は、ｎ個の積符号を生成し、各積符号１行ずつを連結した連結行に対し、各連結行毎の所定のインタリーブ規則に基づいて、各連結行内でシンボル単位にインタリーブを行い、行内シンボル単位にインタリーブされた連結行を送出する。各連結行のインタリーブ規則は、行内シンボル単位インタリーブ前のある２つの列の同一行の２つのシンボルが、行内シンボル単位インタリーブ後に、そのシンボル間隔が、行に対して複数種類存在するようにさせるものである。
【００２２】
また、本発明による符号化方法及び符号化回路は、原始データに識別情報が存在する場合、識別情報が存在する行あるいは連結行のインタリーブ規則として、識別情報を連結行内の固定位置に配置するものを使用する。
【００２３】
さらに、本発明による符号化方法及び符号化回路は、原始データ構造や、積符号のデータサイズをＤＶＤと同一とする。
【００２４】
また、前述の目的を達成するために、本発明による復号方法及び復号回路は、受入データに対して各行あるいは各連結行のインタリーブ規則に基づき行内シンボル単位にデインタリーブを行い、得られる積符号を誤り訂正する。
【００２５】
さらに、本発明の記憶装置及び通信装置（送信装置、受信装置）は、本発明の符号化方法あるいは符号化回路または復号方法あるいは復号回路を具備し、また本発明による記憶媒体は、本発明の符号化方法あるいは符号化回路によって送出された誤り訂正符号が記録されている。
【００２６】
【発明の実施の形態】
以下、本発明による符号化方法、復号方法、符号化回路、復号回路、記憶装置、記憶媒体、通信装置の実施形態を図面により詳細に説明する。なお、以下に説明する本発明の実施形態に使用する図において、同一の機能を有するものには同一符号を付け、その繰り返しの説明は省略する。また、以下の説明では、主に２個の積符号を単位として説明するが、本発明は、ｎ個の積符号を単位として適用することができるものであり、１個の積符号（ｎ＝１）であっても３個以上の積符号（ｎ≧３）であっても適用することができる。１個の積符号に本発明を適用した場合、説明の中での連結行の意味は積符号の行そのものとなる。
【００２７】
図３は本発明の一実施形態による符号化方法の処理動作を説明するフローチャート、図４は図３に示すフローのステップ３０１の処理で生成される２個の積符号のデータ配置を説明する図、図５は本発明の一実施形態による符号化方法のインタリーブ規則を説明する図、図６は本発明の実施形態による積符号での誤りが発生した場合の積符号のデータ配置例について説明する図である。図４〜図６において、４０１、４０２は積符号、４０３、４０４は原始データ、４０５〜４１０は冗長データ、５０１はインタリーブ規則、５０２はインタリーブ前の積符号データ、５０３はインタリーブ後の積符号データ、６０１はインタリーブを解いた後の積符号である。
【００２８】
図３に示すフローにおける積符号を生成するステップ３０１の処理は、公知の１個の積符号を生成する方法を繰り返し実行してｎ個のｈ２行ｗ２列の積符号を生成する処理である。すなわち、ここでの処理は、（ｈ１×ｗ１）シンボルの原始データに対し、行方向を（ｗ２，ｗ１）誤り訂正符号によって誤り訂正符号化を行うと共に、列方向を（ｈ２，ｈ１）誤り訂正符号によって誤り訂正符号化を行って、ｈ２行ｗ２列の積符号を生成し、これをｎ個の（ｈ１×ｗ１）シンボルの原始データ毎に行うことにより、ｎ個のｈ２行ｗ２列の積符号を生成する。
【００２９】
図４に示す積符号の例は、ｎ＝２の場合に、積符号を生成するステップ３０１で生成される積符号のデータ配置例の概念を示すものである。すなわち、図４に示す積符号は、ｈ１行ｗ１列に行列配置された原始データ４０３に対して、各行毎に（ｗ２，ｗ１）誤り訂正符号で誤り訂正符号化を行って冗長データ４０５を付加すると共に、各列毎に（ｈ２，ｈ１）誤り訂正符号で誤り訂正符号化を行って冗長データ４０７を付加し、さらに、冗長データ４０７に対して各行毎に（ｗ２，ｗ１）誤り訂正符号で誤り訂正符号化を行って冗長データ４０９を付加することにより、ｈ２行ｗ２列の１つの積符号４０１を生成し、同様に、ｈ１行ｗ１列の原始データ４０４に対し、冗長データ４０６、冗長データ４０８、冗長データ４１０を付加して、ｈ２行ｗ２列の積符号４０２を生成して連結したものである。前述の冗長データ４０９は、冗長データ４０５に対して各列毎に（ｈ２，ｈ１）誤り訂正符号で誤り訂正符号化を行って生成してもよい。同様に、冗長符号４１０は、冗長データ４０８に対して各行毎に（ｗ２，ｗ１）誤り訂正符号で誤り訂正符号化を行って生成しても、冗長データ４０６に対して各列毎に（ｈ２，ｈ１）誤り訂正符号で誤り訂正符号化を行って生成してもよい。
【００３０】
図３に示すフローにおけるステップ３０２の行内のシンボル単位にインタリーブを行う処理は、各積符号１行ずつを連結した連結行に対して、各連結行毎の所定のインタリーブ規則に基づいて、各連結行内でシンボル単位にインタリーブを行う処理である。
【００３１】
ここで、図５を参照して、ｎ＝２，ｈ２＝５，ｗ２＝５の場合の例について、インタリーブ規則の一例と、この規則を使用してステップ３０２の処理によりインタリーブを行ったデータ配置例とについて説明する。図５において、１≦ｉ≦ｈ２，１≦ｊ≦（ｎ×ｗ２）であるとし、π［ｉ］［ｊ］は、インタリーブ規則５０１の第ｉ行第ｊシンボルに対するものであり、Ｄ［ｉ］［ｊ］は、行内シンボル単位インタリーブ前のデータ５０２の第ｉ行第ｊシンボル、またＤ’［ｉ］［ｊ］は、行内シンボル単位インタリーブ後のデータ５０３の第ｉ行第ｊシンボルである。
【００３２】
図５に示すインタリーブ規則の例は、π［１］［１］＝１，π［１］［２］＝２，π［１］［３］＝４，……であり、π［２］［１］＝２，π［３］［１］＝３，……である。また、行内のシンボル単位のインタリーブ前のデータ５０２には、仮に１〜５０のインデックスを付けて示している。行内のシンボル単位のインタリーブ前のデータは、２個の積符号から成っており、Ｄ［１］［１］〜Ｄ［１］［５］，Ｄ［２］［１］〜Ｄ［２］［５］，Ｄ［３］［１］〜Ｄ［３］［５］，Ｄ［４］［１］〜Ｄ［４］［５］，Ｄ［５］［１］〜Ｄ［５］［５］の各シンボルが１個の積符号を構成しており、残りのシンボルが他方の積符号を構成している。また、連結行とは、各積符号の１行ずつを連結したものであり、例えば、図の左方の積符号の第２行のシンボルＤ［２］［１］〜Ｄ［２］［５］と右方の積符号の第２行のシンボルＤ［２］［６］〜Ｄ［２］［１０］を連結したＤ［２］［１］〜Ｄ［２］［１０］が１つの連結行である。
【００３３】
そして、ステップ３０２の処理では、インタリーブ規則５０１のπ［ｉ］［ｊ］に基づいて、インタリーブ前のデータ５０２のＤ［ｉ］［ｊ］を、インタリーブ後のデータ５０３のＤ’［ｉ］［π［ｉ］［ｊ］］へとインタリーブする。すなわち、この処理は、インタリーブ前のデータ５０２のｉ行、ｊ列のデータを、同一行であるｉ行の、インタリーブ規則５０１のｉ行、ｊ列に記述されている値の列にインタリーブする処理である。例えば、π［２］［６］＝９であるから、インタリーブ前のＤ［２］［６］のインデックス値“１６”がインタリーブ後のデータ５０３のＤ’［２］［９］の位置にインタリーブされることになり、Ｄ’［２］［９］＝Ｄ［２］［６］である。
【００３４】
本発明の実施形態によるインタリーブ規則は、行内シンボル単位インタリーブ前のある２つの列の同一行の２つのシンボルが、行内シンボル単位インタリーブ後に、そのシンボル間隔が、行に対して複数種類存在するようにさせるものである。すなわち、図５に示すインタリーブ規則の例は、例えば、行内シンボル単位インタリーブ前の第１行の第１列と第２列のシンボル（インデックス値「１」、「２」）は、行内シンボル単位インタリーブ後に第１列及び第２列に配置され、シンボル間隔が１となるが、行内シンボル単位インタリーブ前の第２行の第１列と第２列のシンボル（インデックス値「１１」、「１２」）は、行内シンボル単位インタリーブ後に第２列と第４列に配置され、シンボル間隔が２とされる。なお、インタリーブ規則の作成の詳細については、後述する。
【００３５】
図３に示すフローにおけるステップ３０３の行内シンボル単位インタリーブされた各連結行を順に送出する処理は、行内シンボル単位インタリーブされた後のデータ５０３の各連結行を順に送出する処理であり、Ｄ’［１］［１］〜Ｄ’［１］［ｎ×ｗ２］〜Ｄ’［ｈ２］［１］〜Ｄ’［ｈ２］［ｎ×ｗ２］が順に送出される。
【００３６】
前述で説明した本発明の実施形態による符号化方法によれば、比較的短いバースト誤りに対して訂正能力が強い誤り訂正符号を送出することができる。
【００３７】
図６に誤りが存在した場合の本発明における誤り訂正符号（積符号）のデータ配置の一例を示している。例えば、図２により説明した場合と同様に、積符号に行方向列方向共に２シンボル誤り訂正可能（消失訂正では最大４シンボル誤り訂正可能）の積符号６０１で、５個の長さ５シンボルのバースト誤りが発生した場合であっても、本発明の誤り訂正符号（積符号）の場合、これら誤りは、図６に示すような位置に各行内に分散するようになり、各列を誤り訂正することによりこれらの誤りを訂正することができる。また、積符号の幾つかの行あるいは列が誤り訂正できなかったとしても、反復訂正を行うことにより、最終的に全ての誤りを訂正できる場合がある。
【００３８】
次に、本発明で使用する行内シンボル単位インタリーブを行うインタリーブ規則を詳細に説明する。
【００３９】
図３により説明したフローの行内シンボル単位インタリーブを行うステップ３０２の処理で、ｈ２個の（ｎ×ｗ２）シンボルの連結行に対し全ての連結行で異なるインタリーブ規則を用いる場合、インタリーブ規則としては、ｈ２個のサイズ（ｎ×ｗ２）の規則が必要である。また、図５の例で説明したように、行内シンボル単位インタリーブ前のある２つの列の同一行の２つのシンボルが、行内シンボル単位インタリーブ後に、そのシンボル間隔が、行に対して複数種類存在するようにさせるインタリーブ規則は、少なくとも２個のサイズ（ｎ×ｗ２）の規則があればよい。行数に比べインタリーブ規則の数が少なければ、これを補うために複数行で同一のインタリーブ規則を用いることができる。後述する図７で説明するインタリーブ規則７０１は、第１行と第５行が同一のインタリーブ規則である。
【００４０】
前述で説明した図５に示すインタリーブ規則の例は、ｎ個の積符号で積符号間にまたがって連結行内でシンボル単位インタリーブを行うものであるが、本発明に用いるインタリーブ規則は、実質的に、各積符号の行内だけでシンボル単位インタリーブを行うものであってもよい。
【００４１】
図７は各積符号の行内でシンボル単位インタリーブを行うインタリーブ規則の一例と、この規則を使用してインタリーブを行ったデータ配置例とについて説明する図である。ここで説明する例は、ｎ＝２，ｈ２＝５，ｗ２＝５の場合の例である。図７において、７０１はインタリーブ規則、７０２は行内シンボル単位インタリーブ前のデータ、７０３は行内シンボル単位インタリーブ後のデータである。
【００４２】
図７に示すインタリーブ規則７０１は、行内シンボル単位インタリーブ前のデータ７０２を、行内シンボル単位インタリーブ後のデータ７０３へインタリーブする。行内シンボル単位インタリーブ後のデータ７０３は、Ｄ’［１］［１］〜Ｄ’［１］［５］，Ｄ’［２］［１］〜Ｄ’［２］［５］，Ｄ’［３］［１］〜Ｄ’［３］［５］，Ｄ’［４］［１］〜Ｄ’［４］［５］，Ｄ’［５］［１］〜Ｄ’［５］［５］が、順不同（インタリーブ規則７０１に従う）で、インタリーブ前のデータＤ［１］［１］〜Ｄ［１］［５］，Ｄ［２］［１］〜Ｄ［２］［５］，Ｄ［３］［１］〜Ｄ［３］［５］，Ｄ［４］［１］〜Ｄ［４］［５］，Ｄ［５］［１］〜Ｄ［５］［５］に対応しており、これらは、１個の積符号を構成している。このようなインタリーブ規則によれば、行内シンボル単位インタリーブを実質的に各積符号の行内で行うことになる。
【００４３】
また、本発明は、記憶システムや通信システム等に適用することができるものであるが、そのようなシステムは、データの再生時や受信時にシンボル同期を行うために、シンボル同期用データを周期的に付加して記録あるいは送信する等を行っている。すなわち、これらのシステムは、いわゆる同期フレームと呼ばれる所定長のデータ毎にシンボル同期を行っており、本発明のインタリーブ規則は、そのようなシステムに対して、実質的に各同期フレーム内でシンボル単位インタリーブを行うものであってもよい。
【００４４】
本発明の効果をより高めるためには、各連結行毎のインタリーブ規則は、異なることが好ましいが、各積符号の行内や各同期フレーム内のように連結行の各部分内でシンボル単位インタリーブを行う場合、各部分のインタリーブ規則は、列方向に異なれば実質的に同一のものでよい。
【００４５】
図８は列方向に異なる部分が実質的に同一であるインタリーブ規則の一例と、この規則を使用してインタリーブを行ったデータ配置例とについて説明する図である。図８に示す例は、ｎ＝２，ｈ２＝５，ｗ２＝５の場合の例であり、また、図８のインタリーブ規則は、実質的に各積符号の行内でシンボル単位インタリーブを行うものである。図８において、８０１はインタリーブ規則、８０２は行内シンボル単位インタリーブ前のデータ、８０３は行内シンボル単位インタリーブ後のデータである。
【００４６】
図８に示すインタリーブ規則８０１は、π［ｉ］［ｊ］＋５＝π［ｉ］［ｊ＋５］であり、インタリーブ前のデータ８０２のＤ［ｉ］［ｊ］をインタリーブ後のデータ８０３のＤ’［ｉ］［π［ｉ］［ｊ］］へ、また、Ｄ［ｉ］［ｊ＋５］をＤ’［ｉ］［π［ｉ］［ｊ］＋５］へインタリーブする。これは、列方向に異なる部分でインタリーブ規則が実質的に同一であることを意味している。
【００４７】
（ｎ×ｗ２）シンボルの連結行内でシンボル単位インタリーブを行う場合には、サイズ（ｎ×ｗ２）のインタリーブ規則が、また、連結行の部分内でシンボル単位インタリーブを行う場合には、そのサイズに対するインタリーブ規則が必要である。次に、サイズｓのインタリーブ規則の定義法について説明する。
【００４８】
いま、サイズｓが素数ｐのｑ乗よりも１少ない場合（ｓ＝ｐq −１）、公知のランダムインタリーバと呼ばれるインタリーブ規則を用いて本発明のインタリーブ規則を定義することができる。ＧＦ（ｐq ）に基づくランダムインタリーバは、ＧＦ（ｐq ）上のある非零元を初期値としこれに原始元を逐次的に乗じていった場合に、各ｐ元ｑ次多項式（あるいは、各桁がｐ値を持つｑ桁のレジスタの各値）をｑ桁のｐ進数と見なした、１〜（ｐq −１）の数を１回ずつとる（ｐq −１）個の数から成る。例えば、図５の第１行に対するインタリーブ規則は、１，２，４，８，５，１０，９，７，３，６であるが、ＧＦ（１１）上で１を初期値としこれに２を逐次的に乗じていった場合の１０個の数であり、これはサイズ１０のランダムインタリーバである。本発明の各列のインタリーブ規則は、このランダムインタリーバを巡回シフトしたものとして定義できる。例えば、図５の第２行に対するインタリーブ規則は、第１行に対するインタリーブ規則を左方に１巡回シフトしたものであり、さらに、ＧＦ（１１）上で２を初期値としこれに２を逐次的に乗じていった場合の１０個の数である。
【００４９】
任意の素数ｐに対してｓ≠ｐq −１であるような場合、公知のランダムインタリーバをそのまま用いることはできない。この場合、まずｓ＜ｐq −１であるような素数ｐ及びｑを用いてランダムインタリーバを定義する。ＧＦ（ｐq ）に基づくランダムインタリーバは、前述で説明したように、１〜（ｐq −１）の数を１回ずつとる（ｐq −１）個の数である。従って、ランダムインタリーバからｓを超える数を除くと、１〜ｓの数を１回ずつとるｓ個の数が得られ、これがサイズｓのインタリーブ規則となる。このインタリーブ規則を、この明細書の中では亜ランダムインタリーバと呼ぶこととする。本発明の各列のインタリーブ規則は、亜ランダムインタリーバを巡回シフトしたものとして定義することができる。
【００５０】
また、インタリーブ規則のサイズｓに対し、ｓよりも小さくｓとは互いに素である数（１を含む）を幾つか準備できる場合、この明細書の中で等間隔インタリーバと呼ぶインタリーブ規則を定義することができる。このインタリーブ規則は、ｓよりも小さくｓとは互いに素である数を（重複を許して）ｈ２個選び、これをｕ［１］，ｕ［２］，……，ｕ［ｈ２］としたときに定義することができる。等間隔インタリーバにおける第ｉ行第ｊシンボルに対するインタリーブ規則は、π［ｉ］［ｊ］＝（ｕ［ｉ］×（ｊ−１））％ｓ＋１として定義される。なお、演算子‘％’は、剰余演算を表す。このようにして、各行においては行内シンボル単位インタリーブ前の隣り合う（あるいは一定間隔離れた）シンボルは、行内シンボル単位インタリーブ後にシンボル間隔が等間隔に離れることになる。
【００５１】
また、行内シンボル単位インタリーブ前のデータに識別情報が含まれる場合等に、このような特定のシンボルを行内シンボル単位インタリーブ後に所定のシンボル位置に配置したい場合がある。これは、特に記憶システムにおける再生時や通信システムにおける受信時に、再生（受信）データに含まれる識別情報を利用して、誤り訂正符号中の位置を知りたい場合である。この場合、もし、複数存在する識別情報が所定の位置に無い場合、再生（受信）時に行う行内シンボル単位デインタリーブの規則が定まらないため、結果として再生（受信）システムの実現が困難となる。
【００５２】
次に、前述のような場合の例として、行内シンボル単位インタリーブ前のデータの第１〜ｋシンボルを、行内シンボル単位インタリーブ後のデータの第１〜ｋシンボルに順に配置し、他のシンボルを様々にインタリーブする場合について説明する。この場合、１，２，…，ｋと、サイズｓのインタリーブ規則からｋ以下の数を除いて得られるｋ＋１〜ｓの数を１回ずつとる（ｓ−ｋ）個の数を連結することにより、行内シンボル単位インタリーブ前の第１〜ｋシンボルを行内シンボル単位インタリーブ後に第１〜ｋシンボルに順に配置するインタリーブ規則を定義することができる。このインタリーブ規則を、この明細書の中ではｋシンボル固定位置配置インタリーバと呼ぶこととする。
【００５３】
前述までで、本発明で使用するいくつかのインタリーブ規則の例を説明したが、本発明で使用するインタリーブ規則は、行内シンボル単位インタリーブ前のある２つの列の同一行の２つのシンボルが、行内シンボル単位インタリーブ後に、そのシンボル間隔が、行に対して複数種類存在するようにさせるものであれば、どのような規則であってもよい。
【００５４】
本実施の形態の符号化方法は、積符号を生成する処理ステップの後、データの送出を行うステップの前に、各積符号あるいは行内シンボル単位インタリーブされた積符号に対し、各積符号内で行単位インタリーブを行っても構わない。また、積符号内を行単位にインタリーブするステップ、行内シンボル単位にインタリーブするステップ、及び、データを送出するステップのうち、いずれか２個のステップ、あるいは、３個全てのステップは、メモリ上に存在するシンボルを適当な順序で読み出す単一のステップとして実施することも可能である。
【００５５】
次に、前述で説明した本発明の実施形態において、１個の積符号のサイズをＤＶＤのそれに合わせ、ｈ１＝１９２，ｗ１＝１７２，ｈ２＝２０８，ｗ２＝１８２とし、また、１シンボル＝８ビット，ｎ＝２として、ＤＶＤとの互換が容易な誤り訂正符号を送出する符号化方法の例を説明する。
【００５６】
図９は本発明の実施形態における積符号生成ステップで生成されるＤＶＤとの互換が容易な積符号のデータ配置の一例を示す図、図１０はＤＶＤにおける１個のセクタのデータのデータ配置を説明する図である。９０１、９０２は積符号、９０３、９０４は原始データ、９０５〜９１０は冗長データ、９１１〜９１６、１００１はセクタデータ、１００２は識別情報、１００３はＲＳＶ、１００４はＥＤＣである。
【００５７】
図１０に示すように、１個のセクタのデータ１００１は、１２行１７２列の２０６４シンボルから成っており、そのうちの６シンボルは識別情報１００２、６シンボルはＲＳＶ１００３、４シンボルはＥＤＣ１００４、残り２０４８シンボルがメインデータ（ユーザーデータ）として図に示すように配置されて構成されている。
【００５８】
そして、ＤＶＤとの互換が容易な積符号の原始データは、図９に示すように、前述した図１０に示す構成を有するセクタデータ１００１をセクタ１データ９０１〜セクタ３２データ９１６として、積符号９０１の原始データが、セクタ１データ９１１、セクタ３データ９１３、……、セクタ３１データ９１５から構成され、一方、積符号９０２の原始データが、セクタ２データ９１２、セクタ４データ９１４、……、セクタ３２データ９１６から構成されており、各積符号の原始データが１６個のセクタのデータから構成される。各積符号の原始データは、１９２列１７２行の３３０２４シンボルから成っている。セクタの論理アドレス順は、セクタ１、セクタ２、セクタ３、セクタ４、……、セクタ３１、セクタ３２に順に対応してもよいし、セクタ１、セクタ３、……、セクタ３１、セクタ２、セクタ４、……、セクタ３２に順に対応してもよく、どのようであっても構わない。
【００５９】
積符号生成のステップでの処理は、１９２行１７２列の原始データ９０３に対して、各行毎にＧＦ（２8 ）の（１８２，１７２）Reed-Solomon符号により誤り訂正符号化を行うと共に、各列毎にＧＦ（２8 ）の（２０８，１９２）Reed-Solomon符号で誤り訂正符号化を行って、冗長データ９０５、冗長データ９０７及び冗長データ９０９を付加して、２０８行１８２列の積符号９０１を生成する。ＧＦ（２8 ）の（１８２，１７２）Reed-Solomon符号及びＧＦ（２8 ）の（２０８，１９２）Reed-Solomon符号は、ＤＶＤで用いられているものと同じものである。同様に、積符号生成のステップでの処理は、１９２行１７２列の原始データ９０２に対し、冗長データ９０６、冗長データ９０８及び冗長データ９１０を付加して、２０８行１８２列の積符号９０２を生成する。
【００６０】
積符号生成のステップの後、積符号内の行単位にインタリーブを行う処理のステップが行われる。積符号内の行単位にインタリーブを行うステップの処理は、原始データに含まれる識別情報を、誤り訂正符号上で等間隔に存在させるために行うもので、以下、これについて説明する。
【００６１】
図１１は図９に示したものと同一の本発明の実施形態における積符号生成ステップで生成されるＤＶＤとの互換が容易な積符号のデータ配置の一例を示す図、図１２は図１１に示す積符号を各積符号内で行単位にインタリーブした後のデータ配置の一例を示す図、図１３は図１１に示す積符号を各積符号内内で行単位にインタリーブした後のデータ配置の図１２に示す例とは異なる例を示す図である。
【００６２】
図１１に示す積符号は、１≦ｉ≦１６に対して各積符号の第（１２×（ｉ−１）＋１）行に識別情報を含んでいる。行単位にインタリーブする処理は、図１１に示す積符号内の行単位インタリーブ前のデータを、図１２あるいは図１３に示すように積符号内で行単位にインタリーブを行い、積符号９０１及び９０２から積符号内で行単位にインタリーブされた積符号１２０１及び１２０２、あるいは、積符号１３０１及び１３０２を得る。このインタリーブにより、識別情報を含んでいる例えば第１積符号第１行と第２積符号第１行との間には、第２積符号第７行、第１積符号第２行、第２積符号第８行、第１積符号第３行、第２積符号第９行、第１積符号第４行、第２積符号第１０行、第１積符号第５行、第２積符号第１１行、第１積符号第６行、第２積符号第１２行、図１２の例では第１積符号第１９３行あるいは図１３の一例では第１積符号第７行の、合計１２個の積符号の行が順に存在し、積符号の行１３個について１個の識別情報を含む積符号の行が周期的に存在するようになる。
【００６３】
すなわち、図１２、図１３に示す積符号内行単位インタリーブされた積符号１２０１あるいは１３０１は、１≦ｉ≦１６に対して、第（１３×（ｉ−１）＋１）行が識別情報を含んでおり、積符号内行単位インタリーブされた積符号１２０２あるいは１３０２は、１≦ｉ≦１６に対して、第（１３×（ｉ−１）＋７）行が識別情報を含んでいる。
【００６４】
積符号内を行単位にインタリーブする処理の後、行内シンボル単位にインタリーブする処理を行う。ここでは、３６４シンボルの連結行の行内シンボル単位にインタリーブを行う際、サイズ９１のインタリーブ規則を用いて、実質的に９１シンボルの部分内でシンボル単位インタリーブを行う例を説明する。なお、ＤＶＤでは、１個の同期フレームに含まれるデータは９１シンボルである。
【００６５】
図１４は図１２あるいは図１３に示したものと同一の積符号内を行単位にインタリーブした後のデータ配置の一例を示す図、図１５は図１４に示す積符号を行内でシンボル単位にインタリーブした後のデータ配置の一例と送出順を示す図である。
【００６６】
サイズ９１のインタリーブ規則の一例として、ｐ＝２，ｑ＝７としＧＦ（２7 ）に基づく亜ランダムインタリーバを定義することができる。この亜ランダムインタリーバに基づくと、第１行の基本インタリーブ規則には、初期値を１とした（π［１］［１］，π［１］［２］，…，π［１］［９１］）＝（１，２，４，８，１６，３２，６４，３，６，１２，２４，４８，６７，５，１０，２０，４０，８０，３５，７０，１５，３０，６０，７３，１７，３４，６８，１１，２２，４４，８８，５１，７９，２９，５８，８５，４１，８２，３９，７８，３１，６２，８１，３３，６６，７，１４，２８，５６，６９，９，１８，３６，７２，１９，３８，７６，２７，５４，９１，５３，８７，４５，９０，５５，６１，８９，４９，７１，１３，２６，５２，８３，３７，７４，２３，４６，５９，５７，７７，２５，５０，７５，２１，４２，８４，４３，８６，４７，６３，６５）を用い、第２行の基本インタリーブ規則には、初期値を２とした（π［２］［１］，π［２］［１］，…，π［２］［９１］）＝（２，４，８，１６，３２，６４，３，６，１２，２４，４８，６７，５，１０，２０，４０，８０，３５，７０，１５，３０，６０，７３，１７，３４，６８，１１，２２，４４，８８，５１，７９，２９，５８，８５，４１，８２，３９，７８，３１，６２，８１，３３，６６，７，１４，２８，５６，６９，９，１８，３６，７２，１９，３８，７６，２７，５４，９１，５３，８７，４５，９０，５５，６１，８９，４９，７１，１３，２６，５２，８３，３７，７４，２３，４６，５９，５７，７７，２５，５０，７５，２１，４２，８４，４３，８６，４７，６３，６５，１）を用いることになる。
【００６７】
同様に、１≦ｉ≦２０８に対して、第ｉ行の基本インタリーブ規則には、初期値を（（ｉ−１）％９１＋１）としたものを用いる。なお、演算子‘％’は剰余演算を表し、例えば、１８５％９１＝３である。また、第ｉ行の基本インタリーブ規則には、第１行の基本インタリーブ規則を（ｉ−１）回巡回シフトしたものを用いてもよい。いずれにしても、各行の基本インタリーブ規則は、第１行の基本インタリーブ規則を適当に巡回シフトしたものであり、１≦ｉ≦１１７に対して第ｉ行と第（ｉ＋９１）行の基本インタリーブ規則は同一である。ここでのインタリーブの処理は、識別情報を含まない各部分に対して、基本インタリーブ規則を用いて行内シンボル単位のインタリーブを行う。
【００６８】
また、ここでのインタリーブの処理は、６シンボルの識別情報を含む各部分、すなわち、図１４において、１≦ｉ≦１６に対する第（１３×（ｉ−１）＋１）行第１部分及び第（１３×（ｉ−１）＋７）行第３部分に対して、亜ランダムインタリーバに対する６シンボル固定位置配置インタリーバ（ρ［ｉ］［１］，ρ［ｉ］［２］，…，ρ［ｉ］［９１］）を用いて行内シンボル単位にインタリーブを行う処理である。
【００６９】
具体的には、このインタリーブの処理は、１≦ｉ≦１６に対して、第（１３×（ｉ−１）＋１）行第１部分及び第（１３×（ｉ−１）＋７）行第３部分には、例えば、初期値（２×（ｉ＋２２））とした亜ランダムインタリーバに対する６シンボル固定位置配置インタリーバを用いる。例えば、第１行第１部分及び第７行第３部分の固定位置配置インタリーブ規則には、（ρ［１］［１］，ρ［１］［２］，…，ρ［１］［９１］）＝（１，２，３，４，５，６，４６，５９，５７，７７，２５，５０，７５，２１，４２，８４，４３，８６，４７，６３，６５，８，１６，３２，６４，１２，２４，４８，６７，１０，２０，４０，８０，３５，７０，１５，３０，６０，７３，１７，３４，６８，１１，２２，４４，８８，５１，７９，２９，５８，８５，４１，８２，３９，７８，３１，６２，８１，３３，６６，７，１４，２８，５６，６９，９，１８，３６，７２，１９，３８，７６，２７，５４，９１，５３，８７，４５，９０，５５，６１，８９，４９，７１，１３，２６，５２，８３，３７，７４，２３）を用い、第１９６行第１部分及び第２０２行の固定位置配置インタリーブ規則には、（ρ［１６］［１］，ρ［１６］［２］，…，ρ［１６］［９１］）＝（１，２，３，４，５，６，７６，２７，５４，９１，５３，８７，４５，９０，５５，６１，８９，４９，７１，１３，２６，５２，８３，３７，７４，２３，４６，５９，５７，７７，２５，５０，７５，２１，４２，８４，４３，８６，４７，６３，６５，８，１６，３２，６４，１２，２４，４８，６７，１０，２０，４０，８０，３５，７０，１５，３０，６０，７３，１７，３４，６８，１１，２２，４４，８８，５１，７９，２９，５８，８５，４１，８２，３９，７８，３１，６２，８１，３３，６６，７，１４，２８，５６，６９，９，１８，３６，７２，１９，３８）を用いる。あるいは、前述したようなインタリーブ規則に代わって、第１行第１部分のインタリーブ規則の、最初の６シンボル分を除いて（ｉ−１）回巡回シフトしたものを固定位置配置インタリーブ規則として用いてもよい。
【００７０】
本発明の実施形態でのインタリーブの処理は、前述したような基本インタリーブ規則及び固定位置配置インタリーブ規則を用いて、行内シンボル単位インタリーブを行う。すなわち、同一部分に識別情報が含まれていなければ、１≦ｉ≦２０８，１≦ｊ≦９１，１≦ｋ≦４に対して、図１４における行内シンボル単位インタリーブ前のデータの第ｉ行第ｋ部分第ｊ番目（第ｉ行第（９１×（ｋ−１）＋ｊ）列）のシンボルＤ［ｉ］［ｊ］を、基本インタリーブ規則を用いて、図１５に示すように行内シンボル単位インタリーブ後のデータの第ｉ行第ｋ部分第π［ｉ］［ｊ］番目（第ｉ行第（９１×（ｋ−１）＋π［ｉ］［ｊ］）列）のシンボルＤ’［ｉ］［９１×（ｋ−１）＋π［ｉ］［ｊ］］として配置する。
【００７１】
また、同一部分に識別情報が含まれている場合、すなわち、１≦ｉ≦１６に対する第（１３×（ｉ−１）＋１）行第１部分及び第（１３×（ｉ−１）＋７）行第３部分では、固定位置配置インタリーブ規則を用いる。すなわち、１≦ｊ≦９１に対して、行内シンボル単位インタリーブ前のデータの第（１３×（ｉ−１）＋１）行第１部分第ｊ番目（第（１３×（ｉ−１）＋１）行第ｊ列）のシンボルＤ［１３×（ｉ−１）＋１］［ｊ］を、行内シンボル単位インタリーブ後のデータの第（１３×（ｉ−１）＋１）行第１部分第ρ［ｉ］［ｊ］番目（第（１３×（ｉ−１）＋１）行第ρ［ｉ］［ｊ］列）のシンボルＤ’［１３×（ｉ−１）＋１］［ρ［ｉ］［ｊ］］として配置し、また、行内シンボル単位インタリーブ前のデータの第（１３×（ｉ−１）＋７）行第３部分第ｊ番目（第（１３×（ｉ−１）＋７）行第（ｊ＋１８２）列）のシンボルＤ［１３×（ｉ−１）＋７］［ｊ＋１８２］を、行内シンボル単位インタリーブ後のデータの第（１３×（ｉ−１）＋７）行第３部分第ρ［ｉ］［ｊ］番目（第（１３×（ｉ−１）＋７）行第（ρ［ｉ］［ｊ］＋１８２）列）のシンボルＤ’［１３×（ｉ−１）＋７］［ρ［ｉ］［ｊ］＋１８２］として配置する。
【００７２】
本発明の実施形態でのインタリーブの処理は、前述のようにして、積符号内行単位インタリーブされた積符号１４０１及び１４０２を、それらの各部分１４０３〜１４０６内でシンボル単位にインタリーブを行い、行内（部分内）シンボル単位インタリーブされた部分１５０３〜１５０６を得て、全体として積符号内行単位インタリーブ及び行内シンボル単位インタリーブされた積符号１５０１及び１５０２を得る。
【００７３】
行内シンボル単位にインタリーブした後、送出する処理が実行される。送出の処理は、図１５に示すデータ配置を図内に矢印で示すように送出順に送出する。すなわち、１≦ｉ≦２０８，１≦ｊ≦３６４に対するシンボルＤ’［ｉ］［ｊ］は、Ｄ［１］［１］，Ｄ［１］［２］，……，Ｄ［１］［３６４］，Ｄ［２］［１］，Ｄ［２］［２］，……，Ｄ［２］［３６４］，……，Ｄ［２０８］［１］，Ｄ［２０８］［２］，……，Ｄ［２０８］［３６４］の順に送出される。
【００７４】
前述までで説明した本発明の実施形態による符号化方法の例によれば、比較的短いバースト誤りに対して訂正能力が強く、識別情報が周期的に存在し、ＤＶＤとの互換が容易な誤り訂正符号を送出することができる。
【００７５】
以上、本発明の実施形態を具体的に説明したが、１シンボルのビット数、原始データのサイズｈ１及びｗ１、原始データの中のセクタのデータ配置、セクタの中のデータ配置、各積符号のサイズｈ２及びｗ２、積符号を構成する誤り訂正符号、積符号の個数ｎ、積符号内行単位インタリーブを行うインタリーブ規則、行内シンボル単位インタリーブを行うインタリーブ規則、各処理ステップの順序等は、任意に変更することができる。例えば、前述で説明した実施形態は、原始データにおけるセクタのデータ配置を図９に示したものとして説明したが、本発明は、送出データにおいて同一のセクタのデータの間に他のセクタのデータが存在しないように、原始データにおいて、各セクタのデータを各積符号の原始データとして（等サイズで）分配し、送出時に、同一のセクタのデータの間に他のセクタのデータが存在しないように送出するようにすることもできる。
【００７６】
図１６は本発明の一実施形態による符号化回路の回路構成の一例を示すブロック図、図１７は行内シンボル単位インタリーバの回路構成の一例を示すブロック図である。図１６、図１７において、１６０１は符号化回路、１６０２はメモリ、１６０３はメモリ制御部、１６０４は積符号生成部、１６０５は（ｗ２，ｗ１）符号化部、１６０６は（ｈ２，ｈ１）符号化部、１６０７は行内シンボル単位インタリーバ、１７０２はインタリーブ規則生成部、１７０３は行カウンタ、１７０４は列カウンタ、１７０５はテーブル、１７０６は入力バス制御部、１７０７〜１７０９、１７１１〜１７１３はレジスタ、１７１０は出力バス制御部である。
【００７７】
ここで説明する符号化回路の実施形態は、前述で説明した誤り訂正符号の符号化を行うものである。図１６に示す符号化回路１６０１において、メモリ制御部１６０３は、メモリ１６０２上に格納されている（ｎ×ｈ１×ｗ１）シンボルの原始データを積符号生成部１６０４へ送る。次に、積符号生成部１０６４は、（ｎ×ｈ１×ｗ１）シンボルの原始データに対して、その内部の（ｗ２，ｗ１）符号化部１６０５及び（ｈ２，ｈ１）符号化部１６０６を用いて、（ｈ１×ｗ１）シンボル毎に、行方向を（ｗ２，ｗ１）誤り訂正符号によって誤り訂正符号化を行うと共に、列方向を（ｈ２，ｈ１）誤り訂正符号によって誤り訂正符号化を行って、ｎ個のｈ２行ｗ２列の積符号を生成しメモリ制御部１６０３へ送り、メモリ制御部１６０３はこれをメモリ１６０２上に格納する。
【００７８】
さらに、メモリ制御部１６０３は、メモリ１６０２上に格納されているｎ個の積符号に対するｈ２個の（ｎ×ｗ２）シンボルの連結行を、行内シンボル単位インタリーバ１６０７へ送る。行内シンボル単位インタリーバ１６０７は、各連結行毎の所定のインタリーブ規則に基づいて、各連結行内でシンボル単位インタリーブを行う。符号化回路１６０１は、前述野用にして得られる行内シンボル単位インタリーブされた各連結行を送出データ１６０８として送出する。
【００７９】
前述で説明した本発明の実施形態による符号化回路は、比較的短いバースト誤りに対して訂正能力が強い誤り訂正符号を生成することができ、その誤り訂正符号を送出することができる。
【００８０】
前述した符号化回路の実施形態は、各ブロック間のデータ転送の単位を限定するものではなく、例えば、１シンボル単位や複数シンボル単位のデータ転送を行ってもよい。さらに、ｎ個の積符号の生成の完了を待たず、メモリ上に十分なデータが格納されれば、行内シンボル単位に順次インタリーブを行って送出するようにすることもできる。また、符号化回路は、図１６にに示す一例に限らず、メモリやメモリ制御部を複数有し働きを分担させたり、共用できるブロック（例えば、（ｈ２，ｈ１）符号化部及び（ｗ２，ｗ１）符号化部）を共用化して構成することもできる。
【００８１】
前述した符号化回路１６０１内の行内シンボル単位インタリーバ１６０７は、図１７に示すような回路構成を備えて構成されており、連結行内あるいは連結行の部分内のｓシンボル毎に行内シンボル単位にインタリーブを行う回路である。行内シンボル単位インタリーバ１６０７は、行内シンボル単位インタリーブ前データ１７０１としてｓシンボルを順に受け取ると、インタリーブ規則生成部１７０２内の行カウンタ１７０３及び列カウンタ１７０４が、受け取るデータに対応して値を動かす。符号化方法の実施形態で説明したように、インタリーブ規則は、各行（第ｉ行）各列（第ｉシンボル）毎に、π［ｉ］［ｊ］が定義されており、この定義は、テーブル１７０５内に実現することができる。行内シンボル単位インタリーブ前データ１７０１の各シンボル及びそれに対応するインタリーブ規則を受けた入力バス制御部１７０６は、各シンボルをインタリーブ規則に従ってレジスタＡ［１］１７０７，レジスタＡ［２］１７０８，…，レジスタＡ［ｓ］１７０９へ格納していく。ｓシンボル全てのレジスタＡ［１］，レジスタＡ［２］，…，レジスタＡ［ｓ］への格納が完了すると、出力バス制御部１７１０は、レジスタＡ［１］，レジスタＡ［２］，…のシンボルを順に送出データとして出力していく。
【００８２】
前述において、行内シンボル単位インタリーバ１６０７は、出力バス制御部１７１０がレジスタＡ［１］，レジスタＡ［２］，…，レジスタＡ［ｓ］のシンボルを出力し終えるのを待たずに、次の行内シンボル単位インタリーブ前データ１７０１のｓシンボルを受け取ることができる。この場合、入力バス制御部１７０６が各シンボル及びそれに対応するインタリーブ規則を受けるのは前述と同様であり、入力バス制御部１７１０は、各シンボルをインタリーブ規則に従ってレジスタＢ［１］１７１１，レジスタＢ［２］１７１２，…，レジスタＢ［ｓ］１７１３へ格納していく。出力バス制御部１７１０は、入力バス制御部１７０６がｓシンボル全てをレジスタＢ［１］，レジスタＢ［２］，…，レジスタＢ［ｓ］へ格納し終わり、出力バス制御部１７１０がレジスタＡ［１］，レジスタＡ［２］，…，レジスタＡ［ｓ］のシンボルを出力し終えると、レジスタＢ［１］，レジスタＢ［２］，…，レジスタＢ［ｓ］のシンボルを順に送出データとして出力していく。行内シンボル単位インタリーバ１６０７は、出力バス制御部１７１０がレジスタＢ［１］，レジスタＢ［２］，…，レジスタＢ［ｓ］のシンボルを出力し終えるのを待たずに、次の行内シンボル単位インタリーブ前データ１７０１のｓシンボルを受け取ることができ、入力バス制御部１７０６は、これをレジスタＡ［１］，レジスタＡ［２］，…，レジスタＡ［ｓ］へ格納していく。前述のようにして、図１７に示す行内シンボル単位インタリーバ１６０７は、連続的な行内シンボル単位インタリーブを行うことができる。
【００８３】
前述したテーブル１７０５は、一般にそう呼ばれる（あるいは一般にランダムロジックやＲＯＭと呼ばれる）ものと同様に、比較的小さな行数及び列数のインタリーブ規則を格納する場合に有効であるが、比較的大きな行数や列数のインタリーブ規則を格納するには、入力ビット数が大きくなり実現が困難となる。このような場合、符号化方法の実施形態で説明した、（ｎ×ｗ２）シンボルの連結行内のシンボル単位インタリーブにおいて、連結行内のｓシンボルの各部分内で、列方向に異なる部分では実質的に同一のインタリーブ規則を定義すれば、テーブルの回路規模を低減することができる。例えば、ｓ＜（ｎ×ｗ２），ｓ｜（ｎ×ｗ２）とすればよい（なお、“ａ｜ｂ”は、ａがｂの約数であることを意味する。）また、行数ｈ２に対しｔ行毎に同一のインタリーブ規則となるものを定義しても、同様にテーブルの回路規模を低減することができる。この場合、ｔ＜ｈ２であるとする。
【００８４】
図１８はインタリーブ規則生成部の他の回路構成の一例を示すブロック図である。図１８において、１８０１は行番号剰余演算器、１８０２は列番号剰余演算器であり、他の符号は図１７の場合と同一である。
【００８５】
前述で説明した行内シンボル単位インタリーバ１６０７内のインタリーブ規則生成部１７０２の他の構成例は、図１８に示すような回路構成を備えて構成されている。図１８において、行カウンタ１７０３は、保持している行番号の値（１〜ｈ２）を行番号剰余演算器１８０１へ出力する。行番号剰余演算器１８０１は、演算「（｛行番号｝−１）％ｔ＋１」を行い、この結果をテーブル１８０３に出力する。また、列カウンタ１７０４は、保持している列番号の値（１〜（ｎ×ｗ２））を列番号剰余演算器１８０２へ出力する。列番号剰余演算器１８０２は、演算「（｛列番号｝−１）％ｓ＋１」を行い、この結果をテーブル１８０３に出力する。２つの入力を受けたテーブル１８０３は、対応する内容をインタリーブ規則として出力する。
【００８６】
図１８に示すインタリーブ規則生成部のテーブル１８０３のサイズは、図１７内に示すテーブル１７０５のサイズが、（ｎ×ｈ２×ｗ２）に対応したものであるのに対して（ｓ×ｔ）に対応したものとなり（（ｓ×ｔ）＜（ｎ×ｈ２×ｗ２））、テーブル１７０５のサイズより小さなものとすることができる。
【００８７】
また、ランダムインタリーバ、あるいは、亜ランダムインタリーバに基づく本発明に使用するインタリーブ規則は、組合せ回路であるテーブルを用いるのではなく、順序回路を用いることにより実現がより容易になることがある。
【００８８】
図１９は亜ランダムインタリーバに基づくインタリーブ規則生成部の回路構成の一例を示すブロック図である。図１９において、１９０１、１９０６は比較器、１９０２、１９０７はセレクタ、１９０３は現時点保持回路、１９０４は１時点後計算部、１９０５は２時点後計算部であり、他の符号は図１７、図１８の場合と同一である。
【００８９】
図１９に示すインタリーブ規則生成部１７０２は、まず、インタリーブ規則の出力に先立ち、図示していない列カウンタ等から生成することができる条件を比較器１９０１が検出すると、その行番号がセレクタ１９０２を経由して現時点保持回路１９０３に初期値として格納される。インタリーブ規則生成部は、第１のインタリーブ規則として行番号を出力する。次に、１時点後計算部１９０４は、現時点保持回路が保持している値（元）に原始元を乗じ、また、２時点後計算部１９０５は、現時点保持回路１９０４が保持している値（元）に原始元の２乗を乗じる。条件を比較する比較器１９０６及びセレクタ１９０７は、１時点後計算部の出力がｓ以下であればこれを選択し、そうでなければ２時点後計算部の出力を選択し、現時点保持回路１９０３は、選択されたものを保持する。前述のようにして、図１９に示すインタリーブ規則生成部が出力するインタリーブ規則は、順に、行番号，行番号に原始元を乗じたもの（これがｓを超える場合は行番号に原始元の２乗を乗じたもの），……となる。
【００９０】
前述した例は、２時点後計算部１９０５を用いて１時点先見を行いｓ以下であるインタリーブ規則を除いているが、このような先見を行わなければ、インタリーブ規則生成部は、ランダムインタリーバに基づくインタリーブ規則を出力することになる。また、図示していないが３時点後計算部等を具備させることもでき、これにより２時点先見等を行う亜インタリーバに基づいてインタリーブ規則生成部を構成することもできる。さらに、亜ランダムインタリーバに基づくインタリーブ規則を、そのような先見を僅かしか必要としないものを選んで定義することもできる。すなわち、符号化方法の実施形態で説明したｐ及びｑやＧＦ（ｐq ）を適切に選べば、回路規模の増大を抑えることができる。さらに、符号化方法の実施形態で説明した等間隔インタリーバと呼ぶインタリーブ規則は、回路規模の観点から実現が容易である。
【００９１】
図２０は等間隔インタリーバのためのインタリーブ規則生成部の回路構成の一例を示すブロック図である。図２０において、２００１はテーブル、２００２は乗算器、２００３は剰余演算器であり、他の符号は図１７の場合と同一である。
【００９２】
図２０に示すインタリーブ規則生成部１７０２において、テーブル２００１は、符号化方法の実施形態で説明したｕ［１］，ｕ［２］，…，ｕ［ｈ２］、すなわち、各行の行内シンボル単位インタリーブ前の隣り合うシンボルに対する行内シンボル単位インタリーブ後のシンボル間隔を保持しており、行カウンタ１７０３から行番号ｉを受けるとこれに対応する値ｕ［ｉ］を出力する。ｕ［ｉ］及び列番号ｊを受けた乗算器２００２は、演算「ｕ［ｉ］×（ｊ−１）」を行い、この結果であるｖ＝ｕ［ｉ］×（ｊ−１）を出力する。乗算器２００２からの結果ｖを受けた剰余演算器２００３は、演算「ｖ％ｓ＋１」を行い、この結果をインタリーブ規則生成部１７０２の出力１８０４として出力する。この例におけるテーブル２００１は、せいぜいサイズｈ２に対応した程度の大きさである。
【００９３】
前述した本発明の実施形態による符号化回路は、各積符号あるいは行内シンボル単位インタリーブされた積符号に対し、各積符号内で行単位にインタリーブを行う手段を有してもよい。これは、例えば、図１６において、メモリ制御部１６０３がメモリ１６０２上のデータを適当な順序で読み出すようにすることにより実現することができる。また、積符号内行単位インタリーブを行う手段、行内シンボル単位インタリーブを行う手段、及び、送出する手段のうち、いずれか２個の手段、あるいは、３個全ての手段は、メモリ上に存在するシンボルを適当な順序で読み出す単一の手段として実施することも可能である。
【００９４】
次に、前述した本発明の実施形態による符号化回路において、ＤＶＤとの互換が容易な図１５に示した誤り訂正符号を送出する本発明の実施形態による符号化回路の、特に、インタリーブ規則生成部の一例について説明する。
【００９５】
図２１はＤＶＤとの互換が容易な図１５に示した誤り訂正符号を送出する本発明の実施形態による符号化回路のインタリーブ規則生成部の回路構成の一例を示すブロック図である。図２１において、２１０１、２１０２はテーブル、２１０３、２１０６は加算器、２１０４、２１０７は剰余演算器、２１０５は除算器、２１０８、２１１０は比較器、２１０９、２１１１はセレクタであり、他の符号は図１７の場合と同一である。
【００９６】
前述で説明した図１６に示す符号化回路、図１７に示すインタリーブ規則生成部を除く行内シンボル単位インタリーバ、または、図２１に示すインタリーブ規則生成部を有する符号化回路は、図１５により説明した構成の誤り訂正符号を送出する。すなわち、まず、図１６におけるメモリ、メモリ制御部、及び積符号生成部が連携して図９に示した２個の積符号を生成し、メモリ上にこれを格納する。次に、メモリ及びメモリ制御部が連携して、積符号内行単位インタリーブを行い、メモリ上に図１４に示したデータ配置を格納し、このデータ配置における９１シンボルの各部分毎に行内シンボル単位インタリーバへ送る。あるいは、メモリ及びメモリ制御部が連携して、メモリ上の２個の積符号の各部分を適切な順序で読み出し、積符号内行単位インタリーブを行った場合と同じ順で行内シンボル単位インタリーバへ送る。積符号内行単位インタリーブされた積符号の各部分を受けた行内シンボル単位インタリーバは、各部分に対応するサイズ９１のインタリーブ規則により各部分内シンボル単位インタリーブを行った後、これを送出データとして送出し、結果として符号化回路は、図１５に示した誤り訂正符号を送出する。
【００９７】
各部分内のシンボル単位インタリーブのインタリーブ規則を生成する図２１に示すインタリーブ規則生成部１７０２において、行カウンタ１７０３及び列カウンタ１７０４は、積符号内行単位インタリーブされたデータ配置（図１４）に対応して、それぞれ１〜２０８及び１〜３６４の値をとる。テーブル２１０１は、第１行に対するサイズ９１の基本インタリーブ規則π１［１］〜π１［９１］を保持している。また、テーブル２１０２は、第１行第１部分に対するサイズ９１の６シンボル固定位置配置インタリーブ規則の、最初の６シンボル分（固定位置配置分）を除いた８５シンボル分の規則ρ１［７］〜ρ１［９１］を保持している。
【００９８】
行カウンタ１７０３の値ｉ及び列カウンタ１７０４の値ｊに対し、加算器２１０３は、演算「（ｉ−１）＋（ｊ−１）」を行い、この結果であるａ１＝（ｉ−１）＋（ｊ−１）を出力する。演算結果ａ１を受けた剰余演算器２１０４は、演算「ａ１％９１＋１」を行い、この結果であるｒ１＝ａ１％９１＋１を出力する。この演算結果ｒ１に対し、テーブル２１０１は、π１［ｒ１］を出力する。このようにして、テーブル２１０１は、基本インタリーブ規則を出力する。このインタリーブ規則は、各行に対しては巡回シフトしたものであり、同一行のサイズ９１の各部分に対しては同一のものである。
【００９９】
さらに、除算器２１０５は、ｉに対し、演算「ｉ÷１３」を行い、この結果ｄ２＝ｉ÷１３を出力する。（ここで‘÷’は商演算を表し、例えば、７÷１３＝０である。）演算結果ｄ２を受けた加算器２１０６は、演算「ｄ２＋（ｊ−１）」を行い、この結果ａ２＝ｄ２＋（ｊ−１）を出力する。演算結果ａ２を受けた剰余演算器２１０７は、演算「（（ａ２％９１）−６）％８５＋７」を行い、この結果ｒ２＝（（ａ２％９１）％８５＋７を出力する。演算結果ｒ２に対して、テーブル２１０２は、ρ１［ｒ２］を出力する。また、条件を比較する比較器２１０８は、（ｊ−１）％９１＋１の値が６以下か、６を超えるかを見ており、この出力によって、セレクタ２１０９は、（ｊ−１）％９１＋１≦６であればｊの値を、（ｊ−１）％９１≧７であればρ１［ｒ２］を出力する。このようにして、セレクタ２１０９は、６シンボル固定位置配置インタリーブ規則を出力する。このインタリーブ規則は、各行に対しては最初の６シンボル分を除いて巡回シフトしたものであり、同一行のサイズ９１の各部分に対しては同一のものであり、さらに行番号ｉに対してｉ÷１３が同じである行に対しては同一のものである。
【０１００】
条件を比較する比較器２１１０は、行番号ｉ及び列番号ｊに対し、基本インタリーブと固定位置配置インタリーブとのどちらを用いるのかを判断する。すなわち、（ｉ−１）％１３＝０かつ１≦ｊ≦９１あるいは（ｉ−７）％１３＝０かつ１８３≦ｊ≦２７３の場合に固定位置配置インタリーブを、それ以外の場合には基本インタリーブを用いるように判断し、セレクタ２１１１は、その通りに出力する。このようにして、インタリーブ規則生成部は、図１４に示した積符号内行単位インタリーブされたデータを、図１５に示した送出データへ行内シンボル単位にインタリーブするインタリーブ規則を出力する。
【０１０１】
以上説明した符号化回路によれば、比較的短いバースト誤りに対して訂正能力が強く、識別情報が周期的に存在するＤＶＤとの互換が容易な誤り訂正符号を送出することができる。
【０１０２】
図２２は本発明の一実施形態による複合方法の処理動作を説明するフローチャートである。ここで説明する複合方法の実施形態は、前述で説明した符号化方法の実施形態で作成されて送出される誤り訂正符号に対する復号方法である。
【０１０３】
記憶システムの再生データや通信システムの受信データには、一般に誤りが存在するため、例えば、送出データとして積符号（符号語）を送出した場合であっても、受入データは、一般に積符号（符号語）とはならないが、この明細書の中では受入データの各単位（区切り）を、送出データに対応したものに合わせて呼ぶこととする。また、この明細書の中では、符号化方法における“送出”と反対の意味の、復号方法における入力あるいは受け取りという意味の語句を“受入”と記すこととする。
【０１０４】
図２２において、受入ステップ２２０１は、符号化方法の実施形態における送出ステップに対応するもので、誤りを含んでいるかもしれない受入データを、行内シンボル単位インタリーブされた各連結行として、メモリ内に保持する。
【０１０５】
行内シンボル単位にデインタリーブを行うステップ２２０２は、符号化方法の実施形態における行内シンボル単位にインタリーブを行うステップに対応するもので、各連結行毎の所定のインタリーブ規則に基づいて、各連結行内でそのシンボル単位にデインタリーブを行って、ｎ個の積符号を生成する。
【０１０６】
積符号誤り訂正ステップ２２０３は、符号化方法の実施形態における積符号生成ステップに対応するもので、各積符号毎に行方向の（ｗ２，ｗ１）誤り訂正符号及び列方向の（ｈ２，ｈ１）誤り訂正符号に対して誤り訂正を行い、誤りの無い原始データを得る。このステップにおける各積符号の誤り訂正の処理は、公知の１個の積符号の誤り訂正を各積符号毎に行うことにより実行することができ、反復訂正や消失訂正を用いてもよい。
【０１０７】
本発明の実施形態による復号方法は、受入ステップの後、積符号誤り訂正ステップの前に、各積符号毎に各積符号内で、符号化方法の実施形態で説明したような積符号内行単位インタリーブに対する積符号内行単位デインタリーブを行ってもよい。また、積符号内行単位デインタリーブステップ、受入ステップ、及び、行内シンボル単位デインタリーブステップのうち、いずれか２個のステップ、あるいは３個全てのステップは、シンボルをメモリ上の適当な箇所に格納する単一のステップとして実施することも可能である。
【０１０８】
前述で説明した本発明の実施形態による復号方法によれば、比較的短いバースト誤りに対して訂正能力が強い誤り訂正符号を受入れて、誤り訂正を行うことができる。
【０１０９】
図２３は本発明の実施形態による復号回路の回路構成の一例を示すブロック図である。図２３において、２３０１は復号回路、２３０２は行内シンボル単位デインタリーバ、２３０４はメモリ制御部、２３０５はメモリ、２３０６は積符号訂正部、２３０７は（ｗ２，ｗ１）符号訂正部、２３０８は（ｈ２，ｈ１）符号訂正部である。この実施形態による複合回路は、前述で説明した本発明の実施形態による符号化回路が送出する誤り訂正符号に対する復号回路である。
【０１１０】
図２３に示す復号回路２３０１において、行内シンボル単位デインタリーバ２３０２は、誤りを含んでいるかもしれない受入データ２３０３を、行内シンボル単位にインタリーブされた各連結行として受け、その内部のレジスタに格納する。そして、行内シンボル単位デインタリーバ２３０２は、行内シンボル単位インタリーブされた各連結行に対し、各連結行毎の所定のインタリーブ規則に基づいて、各連結行内でそのシンボル単位にデインタリーブを行う。メモリ制御部２３０４は、得られた各連結行をメモリ２３０５上に格納する。この結果、メモリ２３０５内には、ｎ個のｈ２行ｗ２列の積符号が格納される。
【０１１１】
また、メモリ制御部２３０４は、メモリ上の各積符号を積符号訂正部２３０６へ送り、積符号訂正部は、その内部の（ｗ２，ｗ１）符号訂正部２３０７及び（ｈ２，ｈ１）符号訂正部２３０８を用いて、各積符号毎に行方向の（ｗ２，ｗ１）誤り訂正符号及び列方向の（ｈ２，ｈ１）誤り訂正符号に対して誤り訂正を行う。メモリ制御部２３０４は、誤り訂正結果をメモリ２３０５内に格納する。
【０１１２】
復号回路２３０１は、前述のようにして、メモリ２３０５内に誤りの無い原始データを得ることができる。なお、積符号訂正部２３０６は、積符号の反復訂正や消失訂正を行ってもよい。
【０１１３】
図２４は復号回路２３０１内の行内シンボル単位デインタリーバ２３０２の回路構成の一例を示すブロック図であり、以下、行内シンボル単位デインタリーバの詳細を説明する。図２４において、２４０１はデインタリーブ規則生成部、２４０５は入力バス制御部、２４０６〜２４１１はレジスタ、２４１２は出力制御部である。図２４に示す行内シンボル単位デインタリーバ２３０２は、行内シンボル単位にインタリーブされた連結行内あるいはその部分内のｓシンボル毎に、行内シンボル単位にデインタリーブを行う回路である。
【０１１４】
本発明において、前述までに説明した全てのインタリーブ規則は、それに対するデインタリーブ規則を定義するために使用することができる。すなわち、１≦ｉ≦ｈ２，１≦ｊ≦（ｎ×ｗ２）に対して、インタリーブ規則π［ｉ］［ｊ］が定義されている（第ｉ行第ｊ列のシンボルを第ｉ行第π［ｉ］［ｊ］列へ行内シンボル単位インタリーブする）とき、対応するデインタリーブ規則は、ｉｎｖπ［ｉ］［π［ｉ］［ｊ］］＝ｊである（第ｉ行第π［ｉ］［ｊ］列のシンボルを第ｉ行第ｊ列へ行内シンボル単位デインタリーブする）。
【０１１５】
デインタリーブ規則生成部２４０１は、行内シンボル単位デインタリーブ前データの各シンボルに対するデインタリーブ規則を生成する。行内シンボル単位デインタリーバ２３０２は、行内シンボル単位デインタリーブ前データ２３０３としてｓシンボルを順に受けると、入力バス制御部２４０５が、各シンボルをデインタリーブ規則に従ってレジスタＡ［１］２４０６，レジスタＡ［２］２４０７，……，レジスタＡ［ｓ］２４０８へ格納していく。ｓシンボルの全てについてレジスタへの格納が完了すると、出力バス制御部２４１２は、レジスタＡ［１］，レジスタＡ［２］，……のシンボルを順に、行内シンボル単位デインタリーブ後データ２４１３として出力していく。また、行内シンボル単位デインタリーバ２３０２は、レジスタＢ［１］２４０９，レジスタＢ［２］２４１０，……，レジスタＢ［ｓ］２４１１を備えており、レジスタＡ［１］，レジスタＡ［２］，……，レジスタＡ［ｓ］とパイプラインで用いることにより、連続的な行内シンボル単位デインタリーブを行うことができる。このような処理は、前述した本発明の実施形態による符号化回路における行内シンボル単位インタリーバの場合と同様である。
【０１１６】
図２５は復号回路２３０１内の行内シンボル単位デインタリーバ２３０２の回路構成の他の例を示すブロック図である。この例は、デインタリーブ規則を生成する回路を備えることなく、行内シンボル単位にデインタリーブを行うことを可能にした例である。すなわち、図２５に示す行内シンボル単位デインタリーバ２３０２の例は、図１６、図１７により説明した符号化回路のインタリーブ規則生成部１７０２を用いて行内シンボル単位デインタリーバの回路を構成した例である。
【０１１７】
図２５に示す行内シンボル単位デインタリーバ２３０２において、入力バス制御部２５０１は、行内シンボル単位インタリーブ前データのｓシンボルを、順にレジスタＡ［１］，レジスタＡ［２］，……，レジスタＡ［ｓ］へ格納していく。そして、図１７により説明したインタリーブ規則を生成するインタリーブ規則生成部１７０２は、出力データ（行内シンボル単位デインタリーブ後データ）に同期して、それに対するインタリーブ規則を生成する。出力バス制御部２５０２は、レジスタＡ［１］，レジスタＡ［２］，……，レジスタＡ［ｓ］のシンボルを、インタリーブ規則に従って行内シンボル単位デインタリーブ後データとして出力する。
【０１１８】
この例の行内シンボル単位デインタリーバは、図１７により説明したインタリーブ規則生成部と合わせて、デインタリーブ規則生成部の回路の複雑さを低減できるようなインタリーブ規則を定義して使用して構成してももよい。
【０１１９】
前述した本発明の実施形態による復号回路は、前述した符号化回路の実施の形態における積符号内行単位インタリーブに対する積符号内行単位デインタリーブを行う手段を備えて構成してもよく、この構成は、例えば、図２３において、メモリ制御部２３０４がデータを適当な順序でメモリ２３０５上に書き込むことによりで実現することができる。また、積符号内行単位デインタリーブを行う手段、データを受入する手段、及び、行内シンボル単位デインタリーブを行う手段のうち、いずれか２個の手段、あるいは３個の全ての手段は、シンボルをメモリあるいはレジスタに適当な順序で格納する単一の手段として実現することも可能である。
【０１２０】
前述で説明した本発明の実施形態による復号回路によれば、比較的短いバースト誤りに対して訂正能力が強い誤り訂正符号を受入して、誤り訂正を行うことができる。
【０１２１】
前述した本発明による符号化方法、符号化回路、復号方法、あるいは、復号回路は、データの信頼性を確保するために誤り訂正の技術を用いており、記憶装置や記憶媒体及び通信装置に適用することができるものである。また、本発明は、記録手段（送信手段）及び再生手段（受信手段）を合わせ持った、記録再生装置等に適用することができることはいうまでもない。さらに、本発明の符号化回路及び復号回路の両者を備えて構成される装置は、例えば、積符号生成部及び積符号訂正部、メモリ、メモリ制御部、あるいは、行内シンボル単位インタリーバ及び行内シンボル単位デインタリーバの共用化できる部分を共用化して実現することができる。
【０１２２】
図２６は本発明の実施形態による光ディスクを用いた記録再生装置の概略構成の一例を示すブロック図であり、以下、これについて説明する。図２６において、２６０１は記録再生装置、２６０２はインタフェース、２６０３は符号化復号回路、２６０４はメモリ制御部及びメモリ、２６０５は積符号生成訂正部、２６０６は行内シンボル単位インタリーバ・デインタリーバ、２６０７は記録符号化復号部、２６０８は信号処理部、２６０９は光ディスク、２６１０はトラックである。
【０１２３】
まず、図２６に示す記録再生装置２６０１の記録時の動作について説明する。最初に、インタフェース２６０２は、記録再生装置２６０１外の図示していないホスト、あるいは、記録再生装置２６０１内の図示していないアプリケーション回路（例えば、動画像音声圧縮回路）等から、ユーザーデータを受け、これを符号化復号回路２６０３へ送る。符号化復号回路２６０３は、ユーザーデータに対して、図示していない内部回路が、識別情報の付加や、ユーザーデータ等に対する誤り検出符号の付加等を行う。これらを原始データとして、メモリ制御部及びメモリ２６０４、積符号生成訂正部２６０５及び行内シンボル単位インタリーバデインタリーバ２６０６は、連携して本発明の実施形態で説明した誤り訂正符号を送出する。これを受けた記録符号化復号部２６０７は、このビット列を記録に供するビット列へ変換して信号処理部２６０８へ送り、信号処理部２６０８は、図示していない光ピックアップを用いて光ディスク２６０９に記録する。光ディスクは、図示していない記録再生装置のスピンドルモータやサーボ制御部等によって制御されており、前述した誤り訂正符号が光ディスク２６０９上のトラック２５１０上に順に記録される。
【０１２４】
次に、再生時の動作について説明する。信号処理部２６０８は、光ピックアップを用いて光ディスク２６０９のトラック２６１０上に記録されているデータを読み取り、読み取ったデータを順に復調しこれを記録符号化復号部２６０７に送る。記録符号化復号部２６０７は、これに対して記録時に記録に供させる変換の逆変換を行う。信号処理部２６０８や記録符号化復号部２６０７は、光ディスクの位置認識（再生データの位置認識）のために、データの所定位置に存在する識別情報を用いることができる。記録符号化復号部２６０７によって再生されたデータは、符号化復号回路２６０３内で誤り訂正が行われ、誤りの無いユーザーデータをインタフェースから出力することができる。
【０１２５】
前述した本発明の実施形態による記録再生装置によれば、比較的短いバースト誤りに対して訂正能力が強い誤り訂正符号を用いた記憶システム（通信システム）を構築することができる。また、図示記録再生装置は、１個の積符号のサイズをＤＶＤのそれに合わせることにより、ＤＶＤ記録再生装置からの大きな変更は行内シンボル単位インタリーバ・デインタリーバだけとなり、ＤＶＤ記録再生装置との互換が容易なものとすることができる。
【０１２６】
なお、前述した本発明の実施形態による記録再生装置は、図２６において行内シンボル単位インタリーバ・デインタリーバと記録符号化復号部との位置を交換して、記録時には記録に供するビット列に変換した後で行内シンボル単位インタリーブを、あるいは、再生時には行内シンボル単位デインタリーブを行った後で記録に供させる変換の逆変換を行うように構成することもできる。
【０１２７】
以上、本発明の具体的な実施形態について説明したが、本発明は、前述した実施形態に限定されるものではなく、適用分野に関わらず、要旨を逸脱しない範囲で変更して実施することができる。
【０１２８】
【発明の効果】
以上制御したように本発明によれば、積符号と同じ符号化率で、比較的短いバースト誤りに対して積符号よりも強い誤り訂正符号を送出及び復号することが可能となる。また、本発明によれば、そのような誤り訂正符号において、原始データに識別情報を含む場合、識別情報を所定位置に含んだ誤り訂正符号を送出及び復号することが可能となり、そのような誤り訂正符号において、ＤＶＤとの互換が容易となる誤り訂正符号を送出及び復号することが可能となる。
【図面の簡単な説明】
【図１】従来技術による積符号のデータ配置及び送信順を説明する図である。
【図２】従来技術による積符号での誤りが発生した場合の積符号のデータ配置例について説明する図である。
【図３】本発明の一実施形態による符号化方法の処理動作を説明するフローチャートである。
【図４】図３に示すフローのステップ３０１の処理で生成される２個の積符号のデータ配置を説明する図である。
【図５】本発明の一実施形態による符号化方法のインタリーブ規則を説明する図である。
【図６】本発明の実施形態による積符号での誤りが発生した場合の積符号のデータ配置例について説明する図である。
【図７】各積符号の行内でシンボル単位インタリーブを行うインタリーブ規則の一例と、インタリーブを行ったデータ配置例とについて説明する図である。
【図８】列方向に異なる部分が実質的に同一であるインタリーブ規則の一例と、インタリーブを行ったデータ配置例とについて説明する図である。
【図９】本発明の実施形態における積符号生成ステップで生成されるＤＶＤとの互換が容易な積符号のデータ配置の一例を示す図である。
【図１０】ＤＶＤにおける１個のセクタのデータのデータ配置を説明する図である。
【図１１】図９に示したものと同一の本発明の実施形態における積符号生成ステップで生成されるＤＶＤとの互換が容易な積符号のデータ配置の一例を示す図である。
【図１２】図１１に示す積符号を各積符号内で行単位にインタリーブした後のデータ配置の一例を示す図である。
【図１３】図１１に示す積符号を各積符号内内で行単位にインタリーブした後のデータ配置の図１２に示す例とは異なる例を示す図である。
【図１４】図１２あるいは図１３に示したものと同一の積符号内を行単位にインタリーブした後のデータ配置の一例を示す図である。
【図１５】図１４に示す積符号を行内でシンボル単位にインタリーブした後のデータ配置の一例と送出順を示す図である。
【図１６】本発明の一実施形態による符号化回路の回路構成の一例を示すブロック図である。
【図１７】図１７は行内シンボル単位インタリーバの回路構成の一例を示すブロック図である。
【図１８】インタリーブ規則生成部の他の回路構成の一例を示すブロック図である。
【図１９】亜ランダムインタリーバに基づくインタリーブ規則生成部の回路構成の一例を示すブロック図である。
【図２０】図２０は等間隔インタリーバのためのインタリーブ規則生成部の回路構成の一例を示すブロック図である。
【図２１】ＤＶＤとの互換が容易な誤り訂正符号を送出する符号化回路のインタリーブ規則生成部の回路構成の一例を示すブロック図である。
【図２２】本発明の一実施形態による複合方法の処理動作を説明するフローチャートである。
【図２３】本発明の実施形態による復号回路の回路構成の一例を示すブロック図である。
【図２４】復号回路内の行内シンボル単位デインタリーバの回路構成の一例を示すブロック図である。
【図２５】復号回路内の行内シンボル単位デインタリーバの回路構成の他の例を示すブロック図である。
【図２６】本発明の実施形態による光ディスクを用いた記録再生装置の概略構成の一例を示すブロック図である。
【符号の説明】
１０１、２０１、４０１、４０２  積符号
１０２、４０３、４０４  原始データ
１０３〜１０５、４０５〜４１０  冗長データ
２０２〜２０６  バースト誤り
５０１  インタリーブ規則
５０２  インタリーブ前の積符号データ
５０３  インタリーブ後の積符号データ
６０１  インタリーブを解いた後の積符号
１６０１  符号化回路
１６０２、２３０５  メモリ
１６０３、２３０４  メモリ制御部
１６０４  積符号生成部
１６０５  （ｗ２，ｗ１）符号化部
１６０６  （ｈ２，ｈ１）符号化部
１６０７  行内シンボル単位インタリーバ
１７０２  インタリーブ規則生成部
１７０３  行カウンタ
１７０４  列カウンタ
１７０５、２００１、２１０１、２１０２  テーブル
１７０６  入力バス制御部
１７０７〜１７０９、１７１１〜１７１３、２４０６〜２４１１  レジスタ
１７１０  出力バス制御部
１８０１  行番号剰余演算器
１８０２  列番号剰余演算器
１９０１、１９０６  比較器
１９０２、１９０７、２１０９、２１１１  セレクタ
１９０３  現時点保持回路
１９０４  １時点後計算部
１９０５  ２時点後計算部
２００２  乗算器
２００３、２１０７  剰余演算器
２１０３、２１０６  加算器
２１０５  除算器
２１０８、２１１０  比較器
２３０１  復号回路
２３０２  行内シンボル単位デインタリーバ
２３０６  積符号訂正部
２３０７  （ｗ２，ｗ１）符号訂正部
２３０８  （ｈ２，ｈ１）符号訂正部
２４０１  デインタリーブ規則生成部
２４０５  入力バス制御部
２４１２  出力制御部
２６０１  記録再生装置
２６０２  インタフェース
２６０３  符号化復号回路
２６０４  メモリ制御部及びメモリ
２６０５  積符号生成訂正部
２６０６  行内シンボル単位インタリーバ・デインタリーバ
２６０７  記録符号化復号部
２６０８  信号処理部
２６０９  光ディスク
２６１０  トラック
【図１】
0003992443.tif 000002
【図２】
0003992443.tif 000003
【図３】
0003992443.tif 000004
【図４】
0003992443.tif 000005
【図５】
0003992443.tif 000006
【図６】
0003992443.tif 000007
【図７】
0003992443.tif 000008
【図８】
0003992443.tif 000009
【図９】
0003992443.tif 000010
【図１０】
0003992443.tif 000011
【図１１】
0003992443.tif 000012
【図１２】
0003992443.tif 000013
【図１３】
0003992443.tif 000014
【図１４】
0003992443.tif 000015
【図１５】
0003992443.tif 000016
【図１６】
0003992443.tif 000017
【図１７】
0003992443.tif 000018
【図１８】
0003992443.tif 000019
【図１９】
0003992443.tif 000020
【図２０】
0003992443.tif 000021
【図２１】
0003992443.tif 000022
【図２２】
0003992443.tif 000023
【図２３】
0003992443.tif 000024
【図２４】
0003992443.tif 000025
【図２５】
0003992443.tif 000026
【図２６】
0003992443.tif 000027