符号化装置、復号化装置および誤り訂正装置
【課題】符号化訂正能力が飛躍的に向上された復号化装置を提供する。
【解決手段】本発明の符号化装置は符号化された符号化データを復号するものであり、入力された符号化データに対してＬＤＰＣ復号化を行うＬＤＰＣ符号化部３１と、ＬＤＰＣ復号化部３１により復号されたデータに対してリードソロモン復号化を行うＲＳ復号化部３２とを具備する。従って、データブロックを構成するページの内部に於いてはＬＤＰＣ符号化を行い、ページ間に於いてはリードソロモン符号化を行うことができる。従って、両復号方法を組み合わせることにより、復号化装置の符号訂正能力を向上させることができる。
【解決手段】本発明の符号化装置は符号化された符号化データを復号するものであり、入力された符号化データに対してＬＤＰＣ復号化を行うＬＤＰＣ符号化部３１と、ＬＤＰＣ復号化部３１により復号されたデータに対してリードソロモン復号化を行うＲＳ復号化部３２とを具備する。従って、データブロックを構成するページの内部に於いてはＬＤＰＣ符号化を行い、ページ間に於いてはリードソロモン符号化を行うことができる。従って、両復号方法を組み合わせることにより、復号化装置の符号訂正能力を向上させることができる。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は符号化装置、復号化装置および誤り訂正装置に関し、特に、ＬＤＰＣ（Ｌｏｗ Ｄｅｎｓｉｔｙ Ｐａｒｉｔｙ Ｃｈｅｃｋ）符号を用いた符号化装置、復号化装置および誤り訂正装置に関する。
【背景技術】
【０００２】
デジタルデータの通信や記録を行う際には、外部のノイズ等によりデジタルデータに誤りが発生している。従来から、このような誤りを検出・訂正するための技術として、誤り訂正符号を用いる技術が知られている。誤り訂正符号では、符号化の際にデータに対して冗長データを付加し、復号化の際にはこの冗長データを基にデータの誤りを訂正する。通信や記録されるのは、冗長データが付加されたデータである。
【０００３】
この誤り訂正符号としては、リードソロモン符号やＬＤＰＣ符号がある。誤りを含むデータに対して、訂正符号を用いた誤り訂正処理を施すことで、データに含まれる誤りの値が一定以下であれば、その誤りを訂正することができる。
【０００４】
リードソロモン符号は、複数個の連続したビット単位(シンボル)の誤りを訂正する符号であり、数ある訂正符号化の中でも高度な訂正能力を具備すると考えられている。具体的には、リードソロモン符号の訂正処理は、シンドロームを生成して消失位置を検出するステップと、誤り位置および誤り値の算出・訂正と訂正結果をチェックするステップと、訂正結果の出力ステップとを主要に具備している（例えば下記特許文献１を参照）。
【０００５】
ＬＤＰＣ符号とは、疎な検査行列によって定義されるブロック符号であり、反復号処理によって復号されるものである。ＬＤＰＣ符号の利点を列挙すると、例えば、検査行列が低密度であり、優れた最尤復号性能を持ち、ランダム性を有し、復号に適した構造を持ち、シャノン限界に近い復号性能を備えることである。更に、ＬＤＰＣ符号は、様々な符号長、符号化率の符号を容易に構成できる柔軟性を持っており、エラーフロア現象が殆ど生じない利点もある（例えば下記特許文献２を参照）。
【特許文献１】特開平５−３１５９７４号公報
【特許文献２】特開２００６−１３７１４号公報
【発明の開示】
【発明が解決しようとする課題】
【０００６】
しかしながら、最近の記録媒体に記録されるデータの情報量は極めて増加しており、例えば１テラバイト以上のデータが書き込み可能な情報記録ディスクが出現しつつある。このような状況を鑑みると、上記したリードソロモン符号を用いても、符号化能力が必ずしも充分とは言えない問題があった。
【０００７】
更に、ＬＤＰＣ符号を用いると符号訂正能力を格段に向上させることができるが、符号訂正能力が高いＬＤＰＣ符号を実現するためには、大規模な電気回路が必要とされる問題があった。
【０００８】
この問題の対処方法として、例えば、リードソロモン符号を２重に組み合わせて符号化処理を行う手法も存在し、この方法によると符号訂正能力を向上させることができる。しかしながら、この組み合わせによる方法によっても符号訂正能力が不十分である問題があった。更にまた、他の誤り訂正方法を２重以上に組み合わせることによっても、符号訂正能力の向上は図れるが、この方法によると回路規模が巨大なものになってしまい、誤り訂正にかかるコストが高くなってしまう問題も予測される。
【０００９】
本発明は上述した問題点を鑑みて成されたものである。本発明の主な目的は、符号化訂正能力が飛躍的に向上された符号化装置、復号化装置および誤り訂正装置を提供することにある。
【課題を解決するための手段】
【００１０】
本発明の符号化装置は、入力された入力データを符号化する符号化装置であり、前記入力データに対してＲＳ符号化を行って第１符号化データを生成するＲＳ符号部と、前記第１符号化データに対してＬＤＰＣ符号化を行って第２符号化データを生成するＬＤＰＣ符号部と、を具備することを特徴とする。
【００１１】
本発明の復号化装置は、符号化データを復号化して復号化データを生成する復号化装置であり、前記符号化データに対してＬＤＰＣ復号化を行って第１復号化データを生成するＬＰＤＣ復号部と、前記第１復号化データに対してＲＳ復号化を行って第２復号化データを生成するＲＳ復号部と、を備えることを特徴とする。
【００１２】
本発明の誤り訂正装置は、入力されたデータを符号化して符号化データを生成する符号化装置と、前記符号化データを復号化して復号化データを生成する復号化装置と、を具備し、前記符号化装置は、前記入力データに対してＲＳ符号化を行って第１符号化データを生成するＲＳ符号部と、前記第１符号化データに対してＬＤＰＣ符号化を行って第２符号化データを生成するＬＤＰＣ符号部と、を備え、前記復号化装置は、前記第２復号化データに対してＬＤＰＣ復号化を行って第１復号化データを生成するＬＤＰＣ復号部と、前記第１復号化データに対してＲＳ復号化を行って第２復号化データを生成するＲＳ復号部と、を備えることを特徴とする。
【００１３】
本発明の符号化装置は、多数のシンボルから構成される入力データを符号化する符号化装置であり、前記入力データに含まれる前記シンボルのビット数を多くするデータ変換部と、前記入力データに対してＬＤＰＣ符号化を行って符号化データを生成するＬＤＰＣ符号化部と、を具備することを特徴とする。
【００１４】
本発明の復号化装置は、符号化データを復号化して復号化データを生成する復号化装置であり、前記符号化データに対してＬＤＰＣ復号化を行って前記復号化データを生成するＬＤＰＣ復号部と、前記復号化データに含まれるシンボルのビット数を少なくするデータ変換部と、を具備することを特徴とする。
【００１５】
本発明の誤り訂正装置は、入力された入力データを符号化して符号化データを生成する符号化装置と、前記符号化データを復号化して復号化データを生成する復号化装置、と具備し、前記符号化装置は、前記入力データに含まれるシンボルのビット数を多くする符号側データ変換部と、前記入力データに対してＬＤＰＣ符号化を行って符号化データを生成するＬＤＰＣ符号部と、を備え、前記復号化装置は、前記符号化データに対してＬＤＰＣ復号化を行って復号化データを生成するＬＤＰＣ復号部と、前記復号化データに含まれるシンボルのビット数を少なくする復号側データ変換部と、を備えることを特徴とする。
【００１６】
本発明の復号化装置は、アルファ係数とベータ係数とを用いるＳｕｍ−ｐｒｏｃｕｃｔアルゴリズムを含む復号化を演算部により行う復号化装置に於いて、前記アルファ係数を算出する演算部と、前記ベータ係数を算出する演算部とを、少なくとも一部共用することを特徴とする。
【００１７】
本発明の誤り訂正装置は、入力された入力データをＬＤＰＣ符号により符号化して符号化データを生成する符号化装置と、前記符号化データを復号化して復号化データを生成する復号化装置と、を具備し、前記復号化装置は、アルファ係数とベータ係数とを用いるＳｕｍ−Ｐｒｏｄｕｃｔアルゴリズムを含む復号化を演算部により行い、前記アルファ係数を算出する演算部と、前記ベータ係数を算出する演算部とを、少なくとも一部共有することを特徴とする。
【発明の効果】
【００１８】
本発明の復号化装置では、ＬＤＰＣ復号部とリードソロモン復号部の２つの復号部を具備しているので、復号化性能を極めて高くすることができる。具体的には、データブロック内部のページ全体が破損するページ抜け（Ｐａｇｅ Ｆａｌｌ）が発生しても、ページ間の符号化を行うリードソロモン復号部により、破損したページを正しく復号することができる。更に、ＬＤＰＣ符号部を用いることにより、復号に失敗した情報を特定した後に、正しくデータを復号することができる。
【００１９】
また、本発明の復号化装置では、ＬＤＰＣ復号化に失敗したシンボルを無効シンボルとした後に、このシンボルの位置を示すイレージャー信号を生成して、これらを用いてリードソロモン符号の復号化を行っている。従って、後段の処理であるリードソロモン符号の誤り訂正能力を向上させることができる。
【００２０】
更にまた、本発明の符号化装置に依れば、ＬＤＰＣ符号化を行う前に、符号化の対象となるデータに含まれるシンボルのサイズを大きくしている。従って、ＬＤＰＣ符号化の誤り訂正性能を向上させることができる。
【００２１】
更にまた、本発明の復号化装置に依れば、共通の計算セル（演算部）で、Ｓｕｍ−ｐｒｏｄｕｃｔに使用されるアルファ係数とベータ係数とを演算している。従って、Ｓｕｍ−ｐｒｏｄｕｃｔアルゴリズムを構成するのに必要とされる回路の規模を縮小することができる。
【発明を実施するための最良の形態】
【００２２】
＜第１の実施の形態：誤り訂正装置の概要＞
本形態では、本発明の一実施形態に係る符号化装置および復号化装置を具備する誤り訂正装置の構成および符号訂正方法を説明する。なお、以下の説明では、符号化装置または復号化装置の内部にてデータを構成する単位要素をシンボルと称し、これらの装置の外部にて伝送、書き込み、保存または読み出しされる情報を構成する単位要素をデータと称する場合もある。
【００２３】
図１を参照して、先ず、本形態の誤り訂正装置１０の概略的構成を説明する。図１（Ａ）は誤り訂正装置１０の概略的構成を示すブロック図であり、図１（Ｂ）〜図１（Ｅ）はＥｒｒｏｒ Ｃｏｒｒｅｃｔｉｎｇ Ｃｏｄｅブロック（ＥＣＣブロック）の構成を示す平面図である。
【００２４】
図１（Ａ）を参照して、本形態の誤り訂正装置１０は、入力された入力データを符号化する符号化装置２０と、伝送経路４０を経由して入力された符号化データを復号する復号化装置３０とを具備している。
【００２５】
ここで、伝送経路４０とは、有線または無線を経由した経路が考えられ、例えばデジタル放送や移動体通信がある。また、伝送経路４０の代替として記録媒体が用いられても良い。例えば、符号化装置２０により生成された符号化データを記録媒体（磁気ディスクや光学ディスク）に記録して、記録媒体から読み出した符号化データを復号化装置３０により復号しても良い。ここで、記録媒体としては、例えばＤＶＤ（Ｄｉｇｉｔａｌ Ｖｅｒｓａｔｉｌｅ Ｄｉｓｃ）やＣＤ（Ｃｏｍｐａｃｔ Ｄｉｓｃ）等のように脱着式のディスクで良いし、ＨＤＤ（Ｈａｒｄ Ｄｉｓｋ Ｄｒｉｖｅ）等のように固定式のディスクでも良い。更に、上記記憶媒体として、フラッシュメモリ等の半導体記憶装置も採用できる。また、ＨＤＶ（Ｈｉｇｈ−Ｄｅｆｉｎｉｔｉｏｎ Ｄｉｇｉｔａｌ Ｖｉｄｅｏ）で使用されるフォログラムディスクが記憶媒体として採用されても良い。更にまた、記憶媒体としては、ブルーレイディスク（Ｂｌｕ−ｒａｙ Ｄｉｓｃ：ＢＤ）やＨＤ ＤＶＤ（Ｈｉｇｈ−Ｄｅｆｉｎｉｔｉｏｎ Ｄｉｇｉｔａｌ Ｖｅｒｓａｔｉｌｅ Ｄｉｓｃ）を採用することもできる。
【００２６】
さらに、符号化装置２０のみが個別に使用者に利用されても良いし、復号化装置３０のみが個別に使用者に利用されても良い。また、本形態の誤り訂正装置１０、符号化装置２０または復号化装置３０は、ハードウェアとして構成されても良いし、ソフトウェアとしてプログラムにより実現されても良い。更には、これらは一部がハードウェアにより構成され、残りの部分がソフトウェアにより実現されても良い。
【００２７】
符号化装置２０は、ＲＳ符号化部２１と、データ変換部２３と、ＬＤＰＣ符号化部２２と、データ変換部２４とを主要に具備している。
【００２８】
ＲＳ（Ｒｅｅｄ Ｓｏｌｏｍｏｎ）符号化部２１では、入力されるデジタルデータである入力データ４２に対してリードソロモン（ＲＳ）符号化が施され、結果として第１符号化データ４３が生成される。具体的には、図１（Ｂ）を参照して、入力データ４２を構成する一単位要素であるＥＣＣブロックは、不図示の複数のページから成り、異なるページに含まれるシンボルに対して、ＲＳ符号化が施され、ページ間冗長データが生成される。図では、ページ間冗長データをＰＯが付された領域で示している。そして、符号化を行う方向は図中で矢印にて示されている。ここで生成される第１符号化データ４３は、実質的な意味を持ち複数のページから成る情報と、この情報から生成されたページ間冗長データ（ＰＯ）から成る。この第１符号化データ４３は、データ変換部２３に転送される。なお、ＥＣＣブロックの詳細は、図２等を参照して後述する。
【００２９】
データ変換部２３では、所定の規則に従って、ＥＣＣブロックに含まれる各シンボルのビット数を増大させる。ここでは、シンボルの情報量が８ビット（ｂｉｔ）から１６ビットに変換されている。シンボルをこのように変換することは本発明の特徴の一つであり、このことによりＬＤＰＣ符号化の誤り訂正率を向上させることができる。ここで、シンボルは必ずしも１６ビットに変換される必要は無く、例えば９ビット〜１５ビット程度でも良く、変換前よりも大きいビット数であればよい。しかしながら、後述するパターンマッチングの工程を考慮すると、シンボルは１６ビットに変換されることが望ましい。ここで、シンボルとは、ＥＣＣブロックに含まれるページを構成する単位要素であり、後述するパターンマッチング等はシンボル毎に行われる。各シンボルのビット数が増大された第１符号化データ４３は、ＬＤＰＣ符号化部２２に転送される。
【００３０】
ＬＤＰＣ符号化部２２は、ＲＳ符号化が施された第１符号化データ４３に対してＬＤＰＣ符号化を施す部位である。上記したＲＳ符号化部２１がページ間の符号化を行ったのに対して、ＬＤＰＣ符号化部２２はページ内の符号化を行う。具体的には、図１（Ｃ）を参照して、ＥＣＣブロックに含まれる全てのページに対して、ＬＤＰＣ符号化が施される。図では、ＬＤＰＣ符号化を行う方向が矢印にて示されている。ＬＤＰＣ符号化によって生成されたページ内冗長データは実質的な情報に付加される。図では、付加されるページ内冗長データをＰＩが付された領域で示している。ここで、生成される第２符号化データは、実質的な意味を有し複数のページから成る情報と、ページ間冗長データ（Ｐ０）と、ページ内冗長データ（ＰＩ）から成る。生成された第２符号化データ４４は、データ変換部２４に転送される。
【００３１】
データ変換部２４では、ＥＣＣブロックを構成する各シンボルの情報量を変換して、情報量を少なくする。例えば、上述したデータ変換部２３にてシンボルが８ビットから１６ビットに変換された場合は、この部位にて１６ビットから８ビットに戻す。更に、戻すための変換を行う際には、データ変換部２３で適用された規則とは逆の規則を用いることもできる。データを元に戻す変換を行わずに符号化装置２０から復号化データを出力することも可能であるが、そうすると伝送するべき情報量が増大してしまう等の問題が発生する。従って、シンボルの情報量を元に戻してから出力することが好適である。シンボルの情報量が元に変換された第２符号化データ４４は、符号化装置２０から出力される。また、この部位の主たる役割は情報量の削減であるので、一般的な情報圧縮技術（即ち、上記した情報変換方法とは異なる方法）により符号化データを圧縮して、各シンボルのビット数を減少させても良い。
【００３２】
第２符号化装置２０から出力された第２符号化データ４４は、伝送経路４０を経由して復号化装置３０に伝送され、後述する復号化装置３０に入力される。ここで、第２符号化データ４４を転送する際には、外部のノイズ等に起因して誤りが発生する。即ち、復号化装置３０に入力される第２符号化データ４４は、符号化装置２０から出力されたものとは異なっている。復号化装置３０では、この誤りを訂正して正しい情報を得る。
【００３３】
復号化装置３０は、データ変換部３３と、ＬＤＰＣ復号化部３１と、データ変換部３４と、ＲＳ復号化部３２とを主要に具備している。
【００３４】
データ変換部３３では、復号化装置に入力された復号化データ（符号化装置２０により生成された第２符号化データ４４）に含まれるシンボルの情報量を変換する。ここでは、シンボルの情報量を８ビットから１６ビットに変換している。ここでの変換は、符号化装置２０のデータ変換部２４に於ける変換と等価（即ち、真逆の変換規則あるいは、可逆変換）である必要がある。
【００３５】
ＬＤＰＣ復号化部３１では、１６ビットのシンボルから構成される第２符号化データ４４に対してＬＤＰＣ復号化を行い、第１復号化データを生成する。具体的には、図１（Ｄ）を参照して、ＥＣＣブロックを構成する各ページに対してページ内の復号化を行う。同図では、復号化を行う方向を矢印にて示している。ここでは、各ページ内に含まれるページ内冗長データを用いて、そのページを復号している。また、ページ間冗長データ（ＰＯ）に対しても、ＬＤＰＣ復号化が行われる。生成された第１復号化データ４５は、データ変換部３４に伝送される。
【００３６】
データ変換部３４では、ＥＣＣブロックを構成する各シンボルのデータを、１６ビットから８ビットに変換する。この変換は、詳細を後述するパターンマッチングにより行い、マッチングしたシンボルには、対応する８ビットのシンボルが割り当てられる。一方、マッチングしないシンボルには、エラーであることを示す８ビットのシンボルが割り当てられ、更に、このシンボルの位置を指し示す別のデータ（Ｅｒａｓｕｒｅ Ｆｌａｇ：イレージャー・フラッグ）が生成される。このイレージャー・フラッグ（イレージャー信号）は、データ変換された第１復号化データ４５と共に、ＲＳ復号化部３２に伝送される。
【００３７】
ＲＳ復号化部３２では、データ変換された第１復号化データ４５に対して、リードソロモン復号化（ＲＳ復号化）を行い、復号化された第２復号化データ４６を生成する。ここで生成される第２復号化データ４６は、入力データ４２と等価である。図１（Ｅ）を参照すると、ＲＳ復号化はページ間のシンボルに対して行われ、ＲＳ復号の方向は矢印にて示されている。
【００３８】
上述したように、本発明では、ページ内の誤り訂正にＬＤＰＣ符号を用いて、ページ間の誤り訂正にリードソロモン符号（ＲＳ符号）を用いている。この組み合わせにより、訂正能力を極めて高くすることができる。ＬＤＰＣ符号とＲＳ符号とを組み合わせた本実施の形態の誤り訂正方法は、ＲＳ符号を２重に組み合わせた誤り訂正方法よりも訂正能力が高くなると共に、回路規模を小さく留められる。
【００３９】
図２を参照して、次に、本発明で用いられるＥＣＣブロックの一例を説明する。図２はＥＣＣブロックの概要を示す図である。
【００４０】
図２を参照して、ＥＣＣブロック１１は、実質的な意味を有するデータ（使用者が使用するデータであり、例えば画像データや文書データ）である情報領域１３と、ページ１２内の誤り訂正を行うために用いられるページ内冗長データ１４と、ページ１２の間の誤り訂正を行うために用いられるページ間冗長データ１５とから成る。１つのＥＣＣブロック１１は、トータルで２０８個（ｒｏｗ）のページ１２から成る。また、１つのページ１２は、実質的な意味を有する情報である１０７２バイトと、その情報の冗長データである５６０バイトから成る。更に、最後の２０個（ｒｏｗ）のページでは、１０７２バイトのページ間冗長データ１５に、５６０バイトのページ内冗長データが付加されている。本発明では、ページ内冗長データ１４はＬＤＰＣ符号であり、ページ間冗長データ１５はＲＳ符号である。
【００４１】
ここで、ページ１２の先頭の数バイト（例えば４バイト）がページ数を示す場合があり、この場合は各ページの先頭の数バイトについては、ＲＳ符号化は行われずにページ間冗長データ１５が生成されなくても良いし、この部分も含めた全体に対してページ間冗長データ１５が生成されても良い。一方、ページ数がページ１２の先頭に挿入されない場合は、ページ１２全体に渡ってＲＳ符号化が行われて、ページ間冗長データ１５が生成される。
【００４２】
図３および図４を参照して、図１に示した符号化装置２０に於けるデータの詳細を説明する。図３および図４の各図は、符号化装置２０の内部に於けるデータの変遷を示す概念図である。
【００４３】
図３（Ａ）を参照して、上述したように、符号化装置２０（図１参照）にて生成されるＥＣＣブロック１１は複数のページから成り、情報領域１３と、ページ内冗長データ１４と、ページ間冗長データ１５とから成る。符号化装置２０では、ユーザーデータである情報領域１３に、ページ内冗長データ１４とページ間冗長データ１５とを付加する。従って、符号化装置２０に入力されるデータ（符号化処理が行われる前のデータ）は、情報領域１３のみから成る。ここで、ページ間冗長データ１５は、ＬＤＰＣ符号化に先行して生成して付与されている。ページ間冗長データ１５はリードソロモン符号化により生成される。
【００４４】
図３（Ｂ）を参照して、情報領域１３の内部の１つのページ１２は、１０７２バイトの情報量を有する。本発明では、先ず、１つのページ１２を８個のデータブロックに分割している。ここで、１つのブロックの情報量は１３４バイト（１０７２ビット）である（図３（Ｃ）および図３（Ｄ）参照）。
【００４５】
図３（Ｅ）を参照して、次に、各データブロックに含まれる８ビットのシンボルを１６ビットに変換する。ここでは、予め用意されたテーブル（表）を用いて、シンボルのビット数を変換する。この変換は、ただ単にシンボルの前後に００００等のデータを付加するのではなく、ＬＤＰＣ符号の誤り訂正能力が向上されるように、ハミング距離が考慮される。この変換により、１つのデータブロックの情報量は、１３４バイト（１０７２ビット）から、２６８バイト（２１４４ビット）に変換される。
【００４６】
図４（Ａ）を参照して、次に、各々のデータブロックに対してＬＤＰＣ符号化を施し、ページ内冗長データ１４（Ｒｅｄｕｎｄａｎｃｙ Ｂｌｏｃｋ）を生成する。本発明では、１つの処理単位であるシンボルを８ビットから１６ビットに変換した後に、ＬＤＰＣ符号化を行っているので、より高度な誤り訂正を行うことができる。
【００４７】
ＬＤＰＣ符号化が終了した後は、データブロックに含まれるシンボルを１６ビットから８ビットに再び変換する。この変換も上述したテーブルを逆に用いて（即ち、所定の規則に従って）行われる。この変換を終えた後のページを図４（Ｂ）に示す。ここでは、１３４バイトのデータブロックに、７０バイトのページ内冗長データ（Ｒｅｄｕｎｄａｎｎｃｙ）が付与されている。
【００４８】
図４（Ｃ）を参照して、ここでは、各々が１３４バイトである８個のデータブロックＭ１〜Ｍ８のそれぞれに対して、７０バイトのページ内冗長データＲ１〜Ｒ８が生成される。従って、ここでは、１つのページの情報量は、これらのデータを積算して１６３２バイトとなる。
【００４９】
上記した行程により、図３（Ａ）に示すページ内冗長データ１４が生成され、ＥＣＣブロック１１が完成する。ＥＣＣブロック１１は、伝送路等を介して復号化装置に伝送される。または、ＣＤ等の記録媒体にＥＣＣブロック１１は書き込まれる。
【００５０】
図５および図６を参照して次に、復号化装置を用いて、符号化された情報を復号化する際のデータの変遷を説明する。
【００５１】
図５（Ａ）を参照して、復号化装置に入力される情報は冗長データが付加されたものであり、具体的には、情報領域１３と、ページ内冗長データ１４と、ページ間冗長データ１５とから成る。このＥＣＣブロック１１は、伝送路等を経て復号装置に入力されるので、エラーが発生し、符号化装置により生成されたものとは異なる場合がある。そこで、復号化装置では、ページ内冗長データ１４とページ間冗長データ１５を用いて、このエラーを訂正する。
【００５２】
図５（Ｂ）および図５（Ｃ）を参照して、ページ内冗長データ１４を含む１ページの情報量は、１６３２バイトであり、各々が２０４バイトである８個のデータブロックに１つのページは分割することができる。
【００５３】
図５（Ｄ）を参照して、１つのデータブロックは、１３４バイトの情報領域と、７０バイトのページ間冗長データから成る。このページ間冗長データは、ＬＤＰＣ符号化により生成されたものである。
【００５４】
図５（Ｅ）および図５（Ｆ）を参照して、１つのページに含まれるデータ（実質的に意味を有している情報）は１３４個のシンボルから成り、各々のシンボルは８ビットの情報量を具備している。
【００５５】
ここで、図５（Ｂ）に示すページ１２の構成は、図４（Ｃ）に示すとおりであり、最初の１０７２バイト（１３４バイト×８個）がユーザーデータであり、その後の５６０バイト（７０バイト×８個）が冗長データである。そしてユーザーデータと冗長データとは、各々が集合して配置されている。図５（Ｃ）および図５（Ｄ）を参照して、ページ内のデータは並べ替えられ、各ユーザーデータにその冗長データが隣接する。即ち、ユーザーデータ（１３４バイト）とそれに隣接した冗長データ（７０バイト）から成るセットが、８個集合して１つのページが構成される。
【００５６】
本発明では、各々のシンボルを８ビットから１６ビットに変換している。この変換は、上述した復号化と同様に、変換のためのテーブルを用いて行われる。従って、各々のデータブロックに含まれる情報量は、１０７２ビットから２１４４ビットとなる。
【００５７】
図６（Ａ）および図６（Ｂ）を参照して、５６０ビットのページ間冗長データを用いて、２１４４ビットの情報に対してＬＤＰＣ復号化を行い、２１４４ビットの復号化データを得る。ここで、ＬＤＰＣ符号が行われても、元の情報に完全に復号されるのではなく、復号化に失敗しているシンボルも存在すると考えられる。そこで、本発明では、後に詳述するパターンマッチングを行って、伝送経路にてデータの欠損が発生したか否かを判断している。更にこの作業は、シンボルのビット数の変換も兼ねている。
【００５８】
図６（Ｃ）に変換された後の８ビットの復号化データを示す。この図を参照して、上記パターンマッチングの結果、正しくマッチングしたものは、テーブル中にて対応する８ビットのシンボルに変換される。一方、正しくマッチングしないシンボルは、正しくマッチングしなかったものに割り当てられるべき８ビットのシンボルが割り当てられる。ここでは、マッチングしなかったシンボルに、「０」を指し示す８ビットのシンボルが割り当てられる。更に、図６（Ｄ）を参照して、イレージャー信号（Ｅｒａｓｕｒｅ Ｐａｔｔｅｒｎ）が生成される。このイレージャー信号は、上記したマッチングの結果、マッチングしなかった（即ち、伝送経路にてデータが破損した）シンボルの位置を指し示す信号である。
【００５９】
上記した復号化データとイレージャー信号を用いて、ＲＳ復号化が行われて、完全な復号化が行われた情報が得られる。イレージャー信号を利用することにより、誤りが生じたシンボルの位置を容易に知ることができるので、ＲＳ復号化により誤り訂正の性能を向上させることができる。
【００６０】
＜第２の実施の形態：符号化方法＞
本形態では、リードソロモン符号化およびＬＤＰＣ符号化を組み合わせた符号化方法を詳述する。
【００６１】
図７のフローチャートを参照して、本形態の復号化方法は、入力された入力データに対してリードソロモン符号化を行って第１符号化データを生成する第１ステップＳ１と、第１符号化データのビット数を変換する第２ステップＳ２と、第１符号化データに対してＬＤＰＣ変換を行って第２符号化データを生成する第３ステップＳ３と、第２符号化データのビット数を変換する第４ステップＳ４とを主要に具備する。
【００６２】
第１ステップ：ＲＳ符号化を行うステップ
図８を参照して、入力されたデータに対してリードソロモン符号化を行うステップを説明する。図８（Ａ）は本ステップで生成されるＥＣＣブロック１１を示す図であり、図８（Ｂ）はＥＣＣブロックの一部を示す図である。
【００６３】
図８（Ａ）を参照して、実質的な意味を有するユーザーデータである情報領域１３は、１８８個（ｒｏｗ）のページ１２から成り、１つのページ１２は、１０７２個のシンボル（１つのシンボルは８ビット）から成る。本ステップでは、異なるページに含まれるシンボルに対してリードソロモン符号化を行い、ページ間冗長データを生成する。従って、本工程で生成されるＥＣＣブロックは、ユーザーデータである情報領域１３と、情報領域に含まれるページ間の冗長であるページ間冗長データ１５から成る。
【００６４】
図８（Ｂ）を参照して、各ページに含まれるシンボルを最上段から、Ｂ［０、ｊ］、Ｂ［１、ｊ］、Ｂ［２、ｊ］、・・・・Ｂ［１８７、ｊ］とした場合、多項式（Ｒｅｍａｉｎｄｅｒ Ｐｏｌｙｎｏｍｉａｌ）Ｒｊは以下の式（１）により計算される。更にここでは、１８８列の実質的な情報に、４７列分のゼロ成分を加えて演算を行い、合計で２３５列としている。この様にゼロの列を加算するのは、リードソロモンコアに、処理されるデータのフォーマットを一致させるためである。この様な処理はパディングと称される。
【００６５】
【数１】
また、上記式（１）は下記式（２）により表現することもできる。
【００６６】
【数２】
更に、上記式（２）中のαは、下記式（３）に示す原始多項式の原始根である。
【００６７】
【数３】
上記計算を、ページ１２間の各々のシンボルに対して行い、ページ間冗長データ１５が生成され、第１符号化データが生成される。
【００６８】
第２ステップ：第１符号化データのビット数を変換するステップ
本ステップでは、ステップ１にて生成された第１符号化データに含まれるシンボルのビット数を変換する。第１ステップにて生成されるデータでは、１つのシンボルのビット数は８ビットである。本工程では、データの含まれるシンボルのビット数を８ビットから１６ビットに変換する。
【００６９】
本ステップでは、シンボルのビット数を８ビットから１６ビットに変換するが、この変換はただ単に変換前のシンボルの前または後に「００００００００」等の情報を付与するのではなく、ＬＤＰＣ符号化の効率が高くなるような変換が行われる。即ち、シンボル内部で情報が分散された疎な状態になるように、シンボルの情報量が１６ビットに変換される。このように疎なシンボルを生成することで、ＬＤＰＣ符号の符号訂正能力を向上させることができる。また、ここで、ビット数を１６ビットに変換しても、シンボルが取り得る値のバリエーションは２５６通りであり８ビットの場合と変わらない。従って、シンボルを増加させることによる計算量の増加は抑制されている。
【００７０】
図９に、本工程で使用されるマッピングテーブルを示す。ここでは、左側の列に１６ビットのシンボルが示され、右側の列にそれに対応する８ビットシンボルが示されている。このテーブルを使用して、ＥＣＣブロックに含まれる全てのシンボルは８ビットから１６ビットに変換される。例えば、１６ビットのシンボルに於ける最下段のシンボル２５５は、それに対応する８ビットシンボル２５５（１１１１＿１１１１）に変換する（割り当てられる）。
【００７１】
次に、図１０および図１１を参照して、上記したテーブル（マッピングテーブル）の生成方法を説明する。図１０（Ａ）は確率分布を示すグラフであり、図１０（Ｂ）はそのグラフを数値化した表であり、図１０（Ｃ）は８ビットシンボルのハミング距離を示す表であり、図１０（Ｄ）はマッピングテーブルである。
【００７２】
先ず、ＬＤＰＣアルゴリズムはＲａｗ Ｄａｔａ Ｆｏｒｍａｔ（１６ビット）を使用することで実現される。この変換テーブルの主たる目的は、８ビットデータを適切な（即ち、変換前よりも疎な状態な）１６ビットデータのシンボルに割り当てることにある。
【００７３】
以下に、上記マッピングテーブルを構築する方法を説明する。最初に、顧客から提供されたデータを利用して、伝送路のノイズを解析する。図１０（Ａ）は、このノイズの性質を可視化したものである。紙面上にて手前側の横軸は伝送路にインプットされるデータを示し、奥行き側に伸びる軸は伝送路から出力されるデータを示し、縦方向の軸はインプット情報とアウトプット情報にエラーが生じる確率であるエラー確率を示している。この解析は、１６ビットシンボル（合計で２５６個）を使用したエラー確率マトリックスを構築することを可能とする。
【００７４】
図１０（Ｃ）を参照して、８ビットバイナリデータのハミング距離が構築される。バイナリＡｄａｔａとバイナリＢｄａｔａとのハミング距離は、ＡｄａｔａとＢｄａｔａとのバイナリ値を比較することにより、簡単に計算できる。例えば、以下の２つの値が有ると仮定した場合、
第１の値：１０００＿００００
第２の値：０００１＿１０１１
第１の値と第２の値とのハミング距離Ｈｄは５である。
【００７５】
図１０（Ｃ）には、８ビットデータの、全ての組合せのハミング距離が示されている。そして、上記した２つのマトリックスは、８ビットデータを１６ビットシンボル（４×４）に割り当てるマッピングテーブルによりリンクされる。
【００７６】
上記した各表（テーブル）を基に、図１０（Ｄ）に示すマッピングテーブルが生成される。このテーブルは、８ビットシンボルを１６ビットシンボルに変換されるときに使用されると共に、逆に、１６ビットシンボルを８ビットシンボルに変換（逆変換）する際にも同じように適用される。
【００７７】
更に、上記マッピングテーブルは、次のような理念に基づいて、生成される。即ち、「インプットされた１６ビットシンボルが、出力されるシンボルよりも高い確率を有している場合は、対応するハミング距離Ｈｄ（Ａ、Ｂ）が可能な限り低くなる。」という基本的考えの基にマッピングテーブルは生成される。
【００７８】
図１１を参照して、次に、効率的にマッピングテーブルを構築する為のアルゴリズムを説明する。図１１（Ａ）はマッチングテーブルの生成方法を示すフローチャートであり、図１１（Ｂ）は最適化を行う前のマッピングテーブルであり、図１１（Ｃ）は最適化を行った後のマッピングテーブルである。このアルゴリズムの主たる目的は、下記式（５）に示される式に示されるハミング比を可能な限り小さくすることにある。
【００７９】
【数５】
図１１（Ａ）に示された各フローチャートの各ステップの具体的処理は以下の通りである。
【００８０】
先ず、ステップＳ１では、８ビットを１６ビットに変換するテーブルを初期化する。８ビットデータと１６ビットデータとは、両方とも昇順にソートされる。そして、上記式（５）に示された式によりハミング平均値を計算する。この式により算出された値を以後、Ｈ参照値と称する。
【００８１】
ステップＳ２では、マッピングテーブルを２つの列になるように置換する。この置換の一例を図１１（Ｂ）および図１１（Ｃ）に示す。置換が終了すると、１６ビットシンボルの０は８ビットデータの１に対応し、１６ビットシンボルの１は、８ビットデータの０に対応する（図１１（Ｃ）参照）。
【００８２】
ステップＳ３では、次に、アップデートされた（置換された）マッピングテーブルを使用して、ハミング平均値を上記式（５）に示された式を使用して計算する。この値をＨｕｐ値と称する。
【００８３】
ステップＳ４では、続いて、Ｈｕｐ値とＨ参照値（Ｈｒｅｆ値と以下にて称する場合もある）とを比較する。
【００８４】
上記ステップＳ４にて、Ｈｕｐ値がＨｒｅｆ値よりも低い場合、（換言すると、この状態のマッピングテーブルが参照のマッピングテーブルよりも適している場合）は、ステップＳ５に移行して、次のような処置をする。即ち、ステップＳ２における置換が記憶されると共に、参照ハミング平均値比がＨｕｐ値としてセットされる（Ｈｒｅｆ値をＨｕｐ値に割り当てる）。
【００８５】
一方、上記ステップＳ４にて、Ｈｕｐ値がＨｒｅｆ値よりも大きい場合、（換言すると、この状態のマッピングテーブルが参照のマッピングテーブルよりも適切でない場合）は、ステップＳ６に移行して、次のような処置をする。即ち、ステップＳ３での置換は記憶されずに、参照のマッピングテーブルを復帰させる（即ち、そのままの状態にしておく）。
【００８６】
上記プロセスは、マッピングテーブルの全ての２列置換に対して行われる。このことによって、本実施の形態の目的に沿った最適なマッピングテーブルが生成される。
【００８７】
第３ステップ：第１符号化データに対してＬＤＰＣ変換を行うステップ
本ステップでは、上記工程により個々のシンボルが８ビットから１６ビットに変換された第１符号化データに対してＬＤＰＣ符号化を行い、ページ内の冗長データを生成して、第２符号化データを生成する。
【００８８】
図１２（Ａ）に本ステップで用いるパリティ検査行列６０を示し、図１２（Ｂ）に本ステップにて生成される第２符号化データを構成するＥＣＣブロック１１を示す。
【００８９】
図１２（Ａ）に示すパリティ検査行列６０は、例えば、５６０行・２７０４列の構成となっている。本形態では、符号化単位となる１ページ分の情報は２１４４ビットであり、５６０個のパリティビットを生成するために更に５６０ビットが付け加えられ、パリティ検査行列６０の列数は２７０４列となる。また、検査行列の右端部には正方形の領域が必要となるので、パリティ検査行列６０の行数は５６０行と成っている。なお、この正方形領域では、対角線の沿った成分は全てが１となっており、対角線より右側は０となっている。更に、この対角線より左側の領域は１が疎に配置されている。
【００９０】
次に、上記したパリティ検査行列６０を各々のページを構成する各ビットと演算して、パリティビットを算出する。このことを換言すれば、各ページについて５６０元の連立方程式を解くことで、各ページに付加されるページ内冗長データが生成される。
【００９１】
このようなパリティ検査行列を用いたページ間冗長データの生成は、ＥＣＣブロックを構成する各ページについて行われる。また、ＲＳ符号化により生成されたページ間冗長データ１５に関しても、ＬＤＰＣ符号化によるページ内冗長データ１４が生成される。
【００９２】
上記ステップにより、図１２（Ｂ）に示す構成のＥＣＣブロック１１が生成される。ＥＣＣブロック１１の構成の詳細は、第１の実施の形態にて上記した。ここでは、ページ１２毎にページ内冗長データ１４が生成され、１つのページに５６０バイトのページ内冗長データ１４が付加される。
【００９３】
本発明の特徴の一つは、ハミング距離が考慮されてビット数が変換された情報に対して、ＬＤＰＣ符号変換を行う点にある。このことにより、冗長データおよび計算量の増大を抑制しつつ、ＬＤＰＣ符号化の誤り訂正能力を向上させることができる。一般的に、誤り訂正のための符号化技術では、符号化の為の冗長データを長くするほど、誤り訂正能力を高めることができる。しかしながら、冗長データを長くすると、伝送又は記録されるべきトータルな情報量が増大してしまい、誤り訂正の為の計算量（計算時間）も長くなってしまう等の問題もある。そこで本形態では、シンボルの情報量を８ビットから１６ビットに変換した後に、このシンボルに対してＬＤＰＣ符号化を行っている。このことにより、シンボルが疎な状態になるので、ＬＤＰＣ符号化の誤り訂正能力が向上される。更に、８ビットのシンボルに適用されるテーブルを用いることができるので、シンボルの情報量が増加することに依る符号化の計算量の増大が抑制される。
【００９４】
第４ステップ：第２符号化データのビット数を変換するステップ
図１３（Ａ）を参照して、本ステップでは、ＬＤＰＣ符号化が行われた第２符号化データの構成するシンボルを、１６ビットから８ビットに変換して、全体の情報量を削減する。具体的には、ＥＣＣブロック１１の中の情報領域１３とページ間冗長データ１５に含まれるシンボルの情報量が、１６ビットから８ビットに変換される。本ステップの情報量の変換が行われた結果、１ページに含まれる情報領域１３の情報量は、２１４４ビットから１０７２ビットに変換される。また、この変換は、ページ間冗長データ１５に対しても行われる。ここでは、各ページに含まれるシンボルの情報量を１６ビットから８ビットに変換しているが、８ビットに以外の情報量（例えば９ビット〜１５ビット）にシンボルが変換されても良い。しかしながら、電気信号が伝送される一般的な伝送路では、８ビットまたは１６ビットの情報が通過することを前提として設計されている場合が多いので、このステップで生成されるシンボルの情報量は８ビットが好適である。
【００９５】
本ステップで、シンボルの情報量を削減することにより、伝送または記録されるべき情報の全体的な量が小さくなる。従って、本形態の符号化装置により生成された符号化データを伝送する場合は、本ステップにてトータルな情報量が削減された結果、伝送路に与える負荷が軽減される。また、生成された符号化データが記憶媒体に記録される場合は、記憶媒体に記録可能な実質的な情報量を増大させることができる。
【００９６】
本ステップの情報量の変換は、上述した第２ステップの情報量の変換とは性質が異なる。上記第２ステップでは、ＬＤＰＣ符号化の誤り訂正能力を向上させるために、シンボルの情報量を８ビットから１６ビットにして疎な状態にした。本ステップでは、情報量の削減が目的であるので、ビット数を変換する表を用意して、この表に従ってシンボルの８ビットを１６ビットに変換すればよい。図１１（Ｂ）にこの変換に用いられる表の一例を示す。
【００９７】
＜第３の実施の形態：復号化方法＞
本形態では、上記第２の実施の形態にて説明した方法により生成された符号化データを復号化して基のデータを得る方法を説明する。
【００９８】
本形態の復号化方法は、図１４に示すフローチャートを参照して、入力された入力データ（符号化データ）を構成するシンボルの情報量を変換する第１ステップＳ１１と、変換されたデータに対してＬＤＰＣ変換を行って第１復号化データを生成する第２ステップＳ１２と、第１復号化データに含まれるシンボルの情報量を変換する第３ステップＳ１３と、第１復号化データに対してＲＳ復号化を行って第２復号化データを生成する第４ステップＳ１４とを具備している。
【００９９】
第１ステップ：入力されたデータのビット数を変換するステップ
本ステップでは、入力された入力データ４９を構成するシンボルのデータ量を変換する。ここで、入力データとは、上述した第２の実施の形態で説明した方法により符号化されたデータである。
【０１００】
本ステップのデータ変換は、上述した第２の実施の形態に於ける第４ステップで行われたデータ変換の逆である。従って、上述した第４ステップのデータ変換がシンボルのデータ量を８ビットから１６ビットに変換するものであった場合は、本ステップではシンボルのデータ量を１６ビットから８ビットに変換する。また、変換に用いるテーブルも、上述した第４ステップと同じものを用いる。図１５に、本ステップのデータ変換に用いるテーブルの一例を示す。
【０１０１】
第２ステップ：ＬＤＰＣ復号化を行うステップ
本ステップでは、上述ステップによりシンボルのビット数が変換された符号化データに対して、ＬＤＰＣ復号化を行い、第1復号化データ４５を生成する。具体的には、Ｓｕｍ−Ｐｒｏｄｕｃｔアルゴリズムに基づく繰り返し復号を行い、推定結果である復号化データを得る。
【０１０２】
本ステップでは対数尤度比（ｌｏｇ ｌｉｋｅｌｉｈｏｏｄ ｒａｔｉｏ）に基づくＳｕｍ−Ｐｒｏｄｕｃｔ復号法を行うので、Ｓｕｍ−Ｐｒｏｄｕｃｔアルゴリズムに入力される入力情報は、入力データ４９自身ではない。
【０１０３】
ここで、図１６（Ａ）に示すようなデータの伝送路（Ｃｈａｎｎｅｌ）を想定し、伝送路に入力されるデータをＸｎとし、伝送路を経由して受信されるデータをＹｎとする。このように仮定した場合、本ステップでは、以下に示す式（４）により算出されるλｎがＳｕｍ−Ｐｒｏｄｕｃｔアルゴリズムに入力される。
【０１０４】
【数４】
上記λｎの値は伝送路の統計学的性質による。即ち、伝送路の種類や状況によってエラーの発生する状況は様々であり、このことがλｎの値に影響するので、その値を求めることは容易ではない。そこで、本発明では、伝送路に発生するエラーの統計学的性質を予め解析し、この解析の結果に基づいて対数尤度比を求めている。
【０１０５】
図１６（Ｂ）に上記解析に基づく結果の一例を示す。この表では、００〜１１の入力に対応して、００〜１１が出力される確率を示している。例えば、００が入力されたときに、００が出力される確率は０．８（８０％）であり、００が入力されたときに１１が出力される確率は０．０（０％）である。
【０１０６】
上記解析結果に基づく対数尤度比の算出方法は次の通りである。先ず、それぞれの出力値に関して、入力値が０である確率（Ｐ０）と、入力値が１である確率（Ｐ１）を算出する。次に、Ｐ１／Ｐ０を算出した後に、ｌｏｇ（Ｐ１／Ｐ０）を算出してλを求める。ここで、Ｐ１がＰ０よりも大きかったらλの値は正となり、Ｐ１がＰ０よりも小さかったらλの値は負となる。
【０１０７】
更に図１６（Ｂ）を参照して、上記算出方法の一例を説明すると、例えば出力値が１０であった場合、入力値が１である確率Ｐ１は、Ｐ１＝０．６＋０．１＝０．７と算出される。また、入力値が０である確率Ｐ０は、Ｐ０＝０．２＋０．１＝０．３と算出される。従って、λ＝ｌｏｇ（０．７／０．３）＝０．３６となる。
【０１０８】
またＬＤＰＣ復号処理では、図１７に示すようなＧａｌｌａｇｅｒ Ｆｕｎｃｔｉｏｎ を用いて計算をしている。ここで、ＲＴＬ（Ｒｅｇｉｓｔｅｒ Ｔｒａｎｓｆｅｒ Ｌｅｖｅｌ）等で復号化装置を構成した場合は、対数の計算にかかるコストは大きくなり、計算時間も長くなる。そこで本形態では、この対数の計算を予め行い、計算結果に基づくルックアップテーブルを生成し、このルックアップテーブルを参照することにより対数を計算している。ルックアップテーブルを用いることにより、復号化に必要とされる計算量を低減させ、計算速度を高速にすると共に回路規模を削減することができる。
【０１０９】
上記方法によりＬＤＰＣ復号化が行われる。係る復号化の他の部分の詳細は、例えば、「低密度パリティ検査符号とその復号法：和田山正著：トリケップス」に記載されている。
【０１１０】
第３ステップ：第1復号化データを変換するステップ
本ステップでは、図１８を参照して、先ステップにて復号された第１復号化データを変換する。図１８（Ａ）は、本ステップに手処理される第１復号化データの一部を示す図であり、図１８（Ｂ）はデータ変換のためのパターンマッチングを示す図であり、図１８（Ｃ）は本ステップの手順を示すフローチャートである。
【０１１１】
本ステップでは、先ステップにて復号化処理されたデータに含まれるシンボルのビット数を変化させる。具体的には、シンボルのビット数を１６ビットから８ビットに変換させる。この処理は、次ステップであるＲＳ復号化のために必要とされる処理である。更に、本ステップでは、先ステップであるＬＤＰＣアルゴリズムにてエラーが発生したエラーを検出している。即ち、ここでは、パターンマッチングを行うことにより、これらの２つの処理を行っている。
【０１１２】
図１８（Ａ）を参照して、ＬＤＰＣ復号化が施されたデータは、１ページが２１４４ビットの情報量を有し、このページに含まれる１シンボルのビット数は１６ビットである。１６ビットの１シンボルは、４×４のマスクシンボルと等価である。このマスクシンボルは、先実施の形態にて、ＬＤＰＣ符号化の前に行われるデータ変換の際に用いられたものと同様なものである。
【０１１３】
図１８（Ｂ）を参照して、本ステップでは、ＬＤＰＣ復号化により得られた第１復号化データに含まれるシンボルと、マスクシンボルとを逐次比較している。即ち、両シンボルのパターンが一致するか否かを確認しており、この作業はパターンマッチングと称されている。このパターンマッチングは、第１復号化データに含まれる全てのシンボルに対して行われる。このマスクシンボルは、８ビットのデータに対応して設けられているので、全部で２５６個存在する。
【０１１４】
図１８（Ｃ）を参照して、上記パターンマッチングの詳細を説明する。本ステップのパターンマッチングでは、先ず、ＬＤＰＣ復号化された第１復号化データに含まれる１６ビットのシンボルを、２５６個存在するマスクシンボルと順次比較する（Ｓ１）。この図に示すパターンマッチングは、第１復号化データを構成する全てのシンボルに対して順次行われる。
【０１１５】
次に、シンボルが多数存在するマスクシンボルの中の一つとマッチするか否かが判断される（Ｓ２）。即ち、Ｓ２では、ＬＤＰＣ復号化により生成された第１復号化データに含まれるシンボルと同一のものが、２５６個存在するマスクシンボルセットの中に存在するか否かが調べられる。
【０１１６】
そして、一致するマスクシンボルが存在したら（Ｓ２のＹＥＳ）、一致したマスクシンボルに対応する８ビットデータが、そのシンボルに割り当てられる（Ｓ３）。このステップを踏むことにより、先工程のＬＤＰＣ復号化にてエラーが発生していないことが確認されると共に、第１復号化データを構成するシンボルのビット数が、１６ビットから８ビットに変換される。
【０１１７】
一方、一致するマスクシンボルが存在しなければ（Ｓ２のＮＯ）、その旨を示す８ビットデータが割り当てられる（Ｓ４）。例えば、「００００００００」が処理対象の１６ビットのシンボルに割り当てられる。ＬＤＰＣ復号化が正常に行われたら（即ち、誤り訂正が正しく行われたら）、２５６個存在するマスクシンボルのいずれか一つとマッチするはずである。従って、処理対象のシンボルとマッチングする（一致する）マスクシンボルが存在しないと云うことは、ＬＤＰＣ復号化が失敗していることを意味している。このことから、ステップＳ４では、復号化に失敗したシンボルの存在および位置を指し示す信号であるイレージャー信号を発生させて、次ステップにてこの信号を利用する。
【０１１８】
以上述べたように、本ステップは、ＬＤＰＣ復号化が施されたデータに対してパターンマッチングを行うことにより、第１復号化データを構成する１６ビットのシンボルが８ビットに変換される。更に、復号化に失敗したシンボルにはその旨を示す８ビットのシンボルが割り当てられ、更に、このシンボルの存在とその位置を示すイレージャー信号が生成される。そして、これらのデータおよび信号は、次ステップにて活用される。
【０１１９】
本ステップのマッチングにより、シンボルのビット数が変換されると共に、復号化の妥当さの是非も判断される。従って、１つの処理によりデータ数変換と復号化の検証が行われるので、処理の複雑化を回避しつつ高度な誤り訂正を行うことができる。
【０１２０】
第４ステップ：第１復号化データをＲＳ復号化するステップ
図１９を参照して、ＲＳ復号化を行うステップを、ＲＳ復号化部３２の構成と共に説明する。このステップの原理と使用される数式は、第１の実施の形態にて説明したので、重複する部分は割愛する。なお、本実施の形態のＲＳ復号方法およりＲＳ復号装置は、通常使用されるものと基本的には同様である。
【０１２１】
本ステップにて用いられるＲＳ復号装置３２は、シンドローム演算部５０と、多項式演算部５１と、シンドローム演算部５２と、Ｅｕｃｉｄｅ演算部５３と、Ｃｈｉｅｎ演算部５４と、エラー訂正部５５とを主要に具備している。
【０１２２】
先ステップにて生成された第１復号化データ４５は、シンドローム演算部５０に入力され、シンドローム演算部５０にてシンドロームが算出される。ここで、シンドロームとは、第１復号化データ４５に、パリティ検査行列を乗じたものである。更に、多項式演算部５１では、入力されたイレージャー信号４７を基に、消失位置を演算する。シンドローム演算部５０および多項式演算部５１の算出結果は、シンドローム演算部５２に伝達される。
【０１２３】
そして、これらの出力結果を利用して、シンドローム演算部５２にて演算を行うことにより、誤りが発生したシンボルの位置とが算出される。
【０１２４】
更に、Ｅｕｃｌｉｄｅ演算部５３およびＣｈｉｅｎ演算部５４では、シンドローム演算部５２の出力結果を利用して、誤り値が演算されると共に演算値がチェックされる。
【０１２５】
最後に、エラー訂正部５５では、前段で算出した値を、誤りが発生している箇所の第１復号化４５に加える。このことにより、誤りが訂正された第２復号化データ４６が生成されて、ＲＳ復号化部３２から外部に出力される。
【０１２６】
＜第４の実施の形態：Ｓｕｍ−ｐｒｏｄｕｃｔアルゴリズムの詳細＞
本実施の形態では、ＬＤＰＣ復号化装置の一部であるＳｕｍ−ｐｒｏｄｕｃｔアルゴリズムの詳細を説明する。通常のＳｕｍ−ｐｒｏｄｕｃｔアルゴリズムと本実施の形態との大きな相違点は、本実施の形態では、Ｓｕｍ−ｐｒｏｄｕｃｔアルゴリズムで使用されるα係数の演算処理と、β計数の演算処理とを合成して行っている点にある。ここで、α係数およびβ係数は、復元されたデータの確かさを示す係数である。
【０１２７】
Ｓｕｍ−ｐｒｏｄｕｃｔアルゴリズムを図２０乃至図２３を参照しつつ説明する。ここで、図２０はＳｕｍ−ｐｒｏｄｕｃｔアルゴリズムの為の回路を示すブロック図であり、図２１はＣＭＰフォーマットおよびＡＢＳフォーマットの詳細を示す表であり、図２２（Ａ）および図２２（Ｂ）はＳＵＭ ＧＡＬＬＡＧＥＲの算出プロセスを示す図であり、図２２（Ｃ）はαｍｎ係数の算出方法を示す図であり、図２３はβ係数の算出方法を示す図である。
【０１２８】
図２０を参照して、Ｓｕｍ−ｐｒｏｄｕｃｔアルゴリズムを実現する回路図は、以下の各ブロックから構成されている。
（１）ＣＯＶ．ＦＭＴ−１
（２）ＧＡＬＬＡＧＥＲ ＦＵＮＣＴＩＯＮ
（３）ＣＡＬＣ．ＳＩＧＮ
（４）ＳＵＭ ＧＡＬＬＡＧＥＲ
（５）ＡＬＰＨＡ ＣＡＬＣＵＬＡＴＩＯＮ
（６）ＣＯＮＶ．ＦＭＴ−２
（７）ＣＡＬＣ．ＢＥＴＡ
（８）ＬＡＭＤＡ ＧＥＮＥＲＡＴＯＲ
（９）ＯＵＴＰＵＴ ＥＳＴＩＭＡＴＩＯＮ
上記各ブロックの機能を以下にて詳述する。
【０１２９】
（１）ＣＯＶ．ＦＭＴ−１
このブロックは、データのフォーマットの変換装置である。入力されるデータ（Ｔｗｏ’Ｓ Ｃｏｍｐｌｅｍｅｎｔ Ｆｏｒｍａｔ（以降ＣＭＰと称する）は、Ｓｉｇｎ−Ａｎｄ−Ｍａｇｎｉｔｕｄｅ Ｆｏｒｍａｔ(以降、ＡＢＳと略称する）に変換される。
【０１３０】
ここで、Ｓｉｇｎ−Ａｎｄ−Ｍａｇｎｉｔｕｄｅ Ｆｏｒｍａｔとは、次の通りである。先ず、ＭＳＢ（Ｍｏｓｔ Ｓｉｇｎｉｆｉｃａｎｔ Ｂｉｔ（最上位のビット）)は記号であり、この記号が０の場合は正であり、この記号が負の場合は負である。そして、残りのビット群は大きさを示している。
【０１３１】
一例として、ＣＭＰフォーマットからＡＢＳフォーマットに変換された５ビットデータのテーブルを、図２１に示す。
【０１３２】
このブロックは、Ｓｕｍ−Ｐｒｏｄｕｃｔ Ａｌｇｏｒｉｔｈｍに適用され、パリティチェックマトリックスの各ラインに於いて、（λｎ’＋βｍｎ’）の値をＡＢＳフォーマットへの変換に使用される。
【０１３３】
（２）ＧＡＬＬＡＧＥＲ ＦＵＮＣＴＩＯＮ
このブロックでは、当該ブロックに入力された情報に対応するＧａｌｌａｇｅｒ Ｆｕｎｃｔｉｏｎの値を算出する。Ｇａｌｌａｇｅｒ Ｆｕｎｃｔｉｏｎの詳細は、下記式（６）に示されている。
【０１３４】
【数６】
このブロックは、ＬＤＰＣデコーダの一部として実施され、Ｓｕｍ−Ｐｒｏｄｕｃｔアルゴリズムに含まれる以下の２つのステップを逐次実行している。
【０１３５】
第１に、アルファ計数の算出プロセスの間、パリティチェックマトリックスＨの各ラインに於いて、ｆ（｜λｎ’＋βｍｎ’｜）の値を算出する。
【０１３６】
第２に、パリティチェックマトリックスＨに含まれるアルファ係数の絶対値を算出する。
【０１３７】
（３）ＣＡＬＣ．ＳＩＧＮ
このブロックに入力される情報は、パリティチェックマトリックスＨを構成する各ラインに含まれる（λｎ’＋βｍｎ’）の値のサイン（符号）である。そして、このブロックの主たる機能は、下記式（７）を計算することにある。
【０１３８】
【数７】
（４）ＳＵＭ ＧＡＬＬＡＧＥＲ
このブロックの構成は、基本的には下記する「（７）ＣＡＬＣ．ＢＥＴＡ」と類似している。
【０１３９】
パリティチェックマトリックスＨに含まれる各々のラインに関して、下記式（８）を実行する。
【０１４０】
【数８】
例えば、パリティチェックマトリックスのある列の重みが３の場合、Ｓｕｍ ｇａｌｌａｇｅｒの計算プロセスは図２２（Ａ）および図２２（Ｂ）に示すようになる。
【０１４１】
（５）ＡＬＰＨＡ ＣＡＬＣＵＬＡＴＩＯＮ
このブロックでは、（３）ＣＡＬＣ．ＳＩＧＮブロックにより算出されたアルファ係数のサインと、それらの絶対値が、第２のＧａｌｌａｇｅｒ Ｆｕｎｃｔｉｏｎ Ｂｌｏｃｋから算出される。
【０１４２】
このブロックの主たる目的は、アルファ係数の各々のサインと絶対値とを集めることにある。５ビット幅のデータの場合の処理方法の一例を、図２２（Ｃ）に示す。
【０１４３】
図２２（Ｃ）を参照すると、ＡＬＰＨＡ ＣＡＬＣＵＬＡＴＩＯＮブロックにより、１ビットのサイン（アルファ係数がプラスかマイナスかを示している）と、４ビットの絶対値（アルファ係数の大きさを示している）とが結合されて、アルファ係数が生成されている。
【０１４４】
（６）ＣＯＮＶ．ＦＭＴ−２
このブロックは、基本的にはデータフォーマットを変換する部位である。ｓｉｇｎ−ａｎｄ−ｍａｇｎｉｔｕｄｅフォーマットの入力情報は、ｔｗｏ’ｓ ｃｏｍｐｌｅｍｅｎｔ ｆｏｒｍａｔ（ＣＭＰ）に変換される。
【０１４５】
このブロックは、Ｓｕｍ−Ｐｒｏｄｕｃｔ ａｌｇｏｒｉｔｈｍに於いて、パリティチェックマトリックスＨの各ｃｏｌｕｍｎに関して、アルファ係数をＣＭＰフォーマットに変換する。
【０１４６】
（７）ＣＡＬＣ．ＢＥＴＡ
このブロックでは、パリティチェックマトリックスＨの各ｃｏｌｕｍｎに関して、β係数を算出すると共に、Ｓｕｍ−ｐｒｏｄｕｃｔ ａｌｇｏｒｉｔｈｍの推定出力値を生成する。
【０１４７】
パリティチェックマトリックスの各ｃｏｌｕｍｎに関して、基本的にこのブロックでは、λ係数とアルファ係数とを加算している。そして、それぞれの（λｋ＋βｍｎ）係数は、これらの値から計算される。
【０１４８】
例えば、図２３には、ｃｏｌｕｍｎ重みが４（４つのアルファ係数のみ）の場合のベータ係数の算出プロセスが示されている。
【０１４９】
（８）ＬＡＭＤＡ ＧＥＮＥＲＡＴＯＲ
このブロックの機能は、Ｓｕｍ−ｐｒｏｄｕｃｔ ａｌｇｏｒｉｔｈｍの入力値から、λ＝〔λ１・・・・・・λＮ〕の値を算出する部位である。この値は、Ｌｏｇ−Ｌｉｋｅｈｏｏｄ Ｒａｔｉｏ（ＬＬＲ）の名称で知られている。
【０１５０】
（９）ＯＵＴＰＵＴ ＥＳＴＩＭＡＴＩＯＮ
先ず、Ｃ＝（Ｃ１、・・・・、ＣＮ）とＳｕｍ−Ｐｒｏｄｕｃｔ Ａｌｇｏｒｉｔｈｍの出力推定値を定義する。この出力推定値は、下記式（９）により実現される。
【０１５１】
【数９】
最後に、出力推定値の吟味が行われる。パリティチェックマトリックスＨを置換した出力であるＣ＝（Ｃ１、・・・・、ＣＮ）のマトリックス乗算を含む。
【０１５２】
この結果がゼロマトリックスであれば、上記推定は正しいことになる。一方、一つでもゼロでないデータがマトリックスに含まれれば、推定出力値は正しくないことを示している。
【０１５３】
上記した各部位の中でも、アルファ係数の算出に寄与する部位は、（１）、（２）、（３）、（４）および（５）であり、ベータ係数の算出に寄与する部位は（６）および（７）である。
【０１５４】
本実施の形態では、演算部（例えば、ＬＳＩの上面に組み込まれた電気回路からなる）により、上記したＳｕｍ−Ｐｒｏｄｕｃｔアルゴリズムを実行している。上記したアルファ係数を演算する演算部と、ベータ係数を演算する演算部とは一部が共用されている。
【０１５５】
具体的には、上記演算部は、入力された入力データに対して加算処理を行う加算部と、加算部から入力されたデータに対して減算処理を行う減算部と、ＣＭＰフォーマットとＡＢＳフォーマットとの変換を行う変換部と、Ｇａｌｌａｇｅｒ Ｆｕｎｃｔｉｕｏｎを演算する変数演算部とを含む。そして、これらの中でも演算部と変数演算部が、ベータ係数算出およびアルファ係数算出に共用される。
【０１５６】
即ち、ベータ係数を算出する際には、加算部、減算部、変換部、変数算出部の順番でデータ処理が行われる。一方、アルファ係数を算出する際には、加算部、減算部、変数算出部、変換部の順番でデータ処理が行われる。
【０１５７】
上記のように、ベータ係数算出およびアルファ係数算出に使用される演算部を共用することにより、個別に演算部を構成した場合と比較して、Ｓｕｍ−Ｐｒｏｄｕｃｔアルゴリズムに必要とされる回路の規模を小さくすることができる。従って、復号化装置や誤り訂正装置の大きさ（即ち、これらの装置が構成されたＬＳＩの大きさ）を小さくすることができる。
【図面の簡単な説明】
【０１５８】
【図１】本発明の符号化装置および復号化装置を説明するための図であり、（Ａ）はブロック図であり、（Ｂ）−（Ｅ）はＥＣＣブロックの概要を示す図である。
【図２】本発明に用いられるＥＣＣブロックの構成を示す図である。
【図３】（Ａ）−（Ｅ）は本発明の符号化の際のデータの構成を示す図である。
【図４】（Ａ）−（Ｃ）は本発明の符号化の際のデータの構成を示す図である。
【図５】（Ａ）−（Ｆ）は本発明の復号化の際のデータの構成を示す図である。
【図６】（Ａ）−（Ｄ）は本発明の復号化の際のデータの構成を示す図である。
【図７】本発明の符号化方法を示すフローチャートである。
【図８】（Ａ）および（Ｂ）は、本発明のＲＳ符号化が施された後のＥＣＣブロックの構成を示す図である。
【図９】本発明のマッピングテーブルを示す表（テーブル）である。
【図１０】本発明の上記マッピングテーブルの生成方法を示す図であり、（Ａ）は確率分布を示す３次元のグラフであり、（Ｂ）はエラーが発生する確率を示す表であり、（Ｃ）はハミング距離を示す表であり、（Ｄ）はマッピングテーブルである。
【図１１】本発明の上記マッピングテーブルの生成方法を示す図であり、（Ａ）はフローチャートであり、（Ｂ）は置換前のマッピングテーブルであり、（Ｃ）は置換後のマッピングテーブルである。
【図１２】本発明のＬＤＰＣ符号化を示す図であり、（Ａ）はパリティ検査行列を示す図であり、（Ｂ）はＥＣＣブロックの構成を示す図である。
【図１３】（Ａ）はＥＣＣブロックの構成を示す図であり、（Ｂ）はマッピングテーブルを示す表である。
【図１４】本発明の復号化方法を示すフローチャートである。
【図１５】本発明のマッピングテーブルを示す表である。
【図１６】本発明のＬＤＰＣ復号化方法を示す図であり、（Ａ）は概念図であり、（Ｂ）は解析結果を示す表である。
【図１７】ＬＤＰＣ復号処理に用いられるＧａｌｌａｇｅｒ Ｆｕｎｃｔｉｏｎを示すグラフである。
【図１８】（Ａ）および（Ｂ）はパターンマッチングを示す図であり、（Ｃ）はこのプロセスを示すフローチャートである。
【図１９】ＲＳ復号化を示すブロック図である。
【図２０】Ｓｕｍ−ｐｒｏｄｕｃｔに用いられる回路を示すブロック図である。
【図２１】ＣＭＰ ｆｏｒｍａｔとＡＢＳ ｆｏｒｍａｔとの関連を示す表である。
【図２２】Ｓｕｍ−ｐｒｏｄｕｃｔの詳細を示す図であり、（Ａ）はパリティチェックマトリックスを示す図であり、（Ｂ）および（Ｃ）はフローチャートである。
【図２３】Ｓｕｍ−ｐｒｏｄｕｃｔの詳細を示す図であり、（Ａ）はパリティチェックマトリックスを示す図であり、（Ｂ）および（Ｃ）はフローチャートである。
【符号の説明】
【０１５９】
１０ 誤り訂正装置
１１ ＥＣＣブロック
１２ ページ
１３ 情報領域
１４ ページ内冗長データ
１５ ページ間冗長データ
２０ 符号化装置
２１ ＲＳ符号化部
２２ ＬＤＰＣ符号化部
２３ データ変換部
２４ データ変換部
３０ 復号化装置
３１ ＬＤＰＣ復号化部
３２ ＲＳ復号化部
３３ データ変換部
３４ データ変換部
４０ 伝送経路
４２ 入力データ
４３ 第１符号化データ
４４ 第２符号化データ
４５ 第１復号化データ
４６ 第２復号化データ
４７ イレージャー信号
４８ 出力データ
４９ 入力データ
５０ シンドローム演算部
５１ 多項式演算部
５２ シンドローム演算部
５３ Ｅｕｃｌｉｄｅ演算部
５４ Ｃｈｅｉｎ演算部
５５ エラー訂正部
６０ パリティ検査行列
【技術分野】
【０００１】
本発明は符号化装置、復号化装置および誤り訂正装置に関し、特に、ＬＤＰＣ（Ｌｏｗ Ｄｅｎｓｉｔｙ Ｐａｒｉｔｙ Ｃｈｅｃｋ）符号を用いた符号化装置、復号化装置および誤り訂正装置に関する。
【背景技術】
【０００２】
デジタルデータの通信や記録を行う際には、外部のノイズ等によりデジタルデータに誤りが発生している。従来から、このような誤りを検出・訂正するための技術として、誤り訂正符号を用いる技術が知られている。誤り訂正符号では、符号化の際にデータに対して冗長データを付加し、復号化の際にはこの冗長データを基にデータの誤りを訂正する。通信や記録されるのは、冗長データが付加されたデータである。
【０００３】
この誤り訂正符号としては、リードソロモン符号やＬＤＰＣ符号がある。誤りを含むデータに対して、訂正符号を用いた誤り訂正処理を施すことで、データに含まれる誤りの値が一定以下であれば、その誤りを訂正することができる。
【０００４】
リードソロモン符号は、複数個の連続したビット単位(シンボル)の誤りを訂正する符号であり、数ある訂正符号化の中でも高度な訂正能力を具備すると考えられている。具体的には、リードソロモン符号の訂正処理は、シンドロームを生成して消失位置を検出するステップと、誤り位置および誤り値の算出・訂正と訂正結果をチェックするステップと、訂正結果の出力ステップとを主要に具備している（例えば下記特許文献１を参照）。
【０００５】
ＬＤＰＣ符号とは、疎な検査行列によって定義されるブロック符号であり、反復号処理によって復号されるものである。ＬＤＰＣ符号の利点を列挙すると、例えば、検査行列が低密度であり、優れた最尤復号性能を持ち、ランダム性を有し、復号に適した構造を持ち、シャノン限界に近い復号性能を備えることである。更に、ＬＤＰＣ符号は、様々な符号長、符号化率の符号を容易に構成できる柔軟性を持っており、エラーフロア現象が殆ど生じない利点もある（例えば下記特許文献２を参照）。
【特許文献１】特開平５−３１５９７４号公報
【特許文献２】特開２００６−１３７１４号公報
【発明の開示】
【発明が解決しようとする課題】
【０００６】
しかしながら、最近の記録媒体に記録されるデータの情報量は極めて増加しており、例えば１テラバイト以上のデータが書き込み可能な情報記録ディスクが出現しつつある。このような状況を鑑みると、上記したリードソロモン符号を用いても、符号化能力が必ずしも充分とは言えない問題があった。
【０００７】
更に、ＬＤＰＣ符号を用いると符号訂正能力を格段に向上させることができるが、符号訂正能力が高いＬＤＰＣ符号を実現するためには、大規模な電気回路が必要とされる問題があった。
【０００８】
この問題の対処方法として、例えば、リードソロモン符号を２重に組み合わせて符号化処理を行う手法も存在し、この方法によると符号訂正能力を向上させることができる。しかしながら、この組み合わせによる方法によっても符号訂正能力が不十分である問題があった。更にまた、他の誤り訂正方法を２重以上に組み合わせることによっても、符号訂正能力の向上は図れるが、この方法によると回路規模が巨大なものになってしまい、誤り訂正にかかるコストが高くなってしまう問題も予測される。
【０００９】
本発明は上述した問題点を鑑みて成されたものである。本発明の主な目的は、符号化訂正能力が飛躍的に向上された符号化装置、復号化装置および誤り訂正装置を提供することにある。
【課題を解決するための手段】
【００１０】
本発明の符号化装置は、入力された入力データを符号化する符号化装置であり、前記入力データに対してＲＳ符号化を行って第１符号化データを生成するＲＳ符号部と、前記第１符号化データに対してＬＤＰＣ符号化を行って第２符号化データを生成するＬＤＰＣ符号部と、を具備することを特徴とする。
【００１１】
本発明の復号化装置は、符号化データを復号化して復号化データを生成する復号化装置であり、前記符号化データに対してＬＤＰＣ復号化を行って第１復号化データを生成するＬＰＤＣ復号部と、前記第１復号化データに対してＲＳ復号化を行って第２復号化データを生成するＲＳ復号部と、を備えることを特徴とする。
【００１２】
本発明の誤り訂正装置は、入力されたデータを符号化して符号化データを生成する符号化装置と、前記符号化データを復号化して復号化データを生成する復号化装置と、を具備し、前記符号化装置は、前記入力データに対してＲＳ符号化を行って第１符号化データを生成するＲＳ符号部と、前記第１符号化データに対してＬＤＰＣ符号化を行って第２符号化データを生成するＬＤＰＣ符号部と、を備え、前記復号化装置は、前記第２復号化データに対してＬＤＰＣ復号化を行って第１復号化データを生成するＬＤＰＣ復号部と、前記第１復号化データに対してＲＳ復号化を行って第２復号化データを生成するＲＳ復号部と、を備えることを特徴とする。
【００１３】
本発明の符号化装置は、多数のシンボルから構成される入力データを符号化する符号化装置であり、前記入力データに含まれる前記シンボルのビット数を多くするデータ変換部と、前記入力データに対してＬＤＰＣ符号化を行って符号化データを生成するＬＤＰＣ符号化部と、を具備することを特徴とする。
【００１４】
本発明の復号化装置は、符号化データを復号化して復号化データを生成する復号化装置であり、前記符号化データに対してＬＤＰＣ復号化を行って前記復号化データを生成するＬＤＰＣ復号部と、前記復号化データに含まれるシンボルのビット数を少なくするデータ変換部と、を具備することを特徴とする。
【００１５】
本発明の誤り訂正装置は、入力された入力データを符号化して符号化データを生成する符号化装置と、前記符号化データを復号化して復号化データを生成する復号化装置、と具備し、前記符号化装置は、前記入力データに含まれるシンボルのビット数を多くする符号側データ変換部と、前記入力データに対してＬＤＰＣ符号化を行って符号化データを生成するＬＤＰＣ符号部と、を備え、前記復号化装置は、前記符号化データに対してＬＤＰＣ復号化を行って復号化データを生成するＬＤＰＣ復号部と、前記復号化データに含まれるシンボルのビット数を少なくする復号側データ変換部と、を備えることを特徴とする。
【００１６】
本発明の復号化装置は、アルファ係数とベータ係数とを用いるＳｕｍ−ｐｒｏｃｕｃｔアルゴリズムを含む復号化を演算部により行う復号化装置に於いて、前記アルファ係数を算出する演算部と、前記ベータ係数を算出する演算部とを、少なくとも一部共用することを特徴とする。
【００１７】
本発明の誤り訂正装置は、入力された入力データをＬＤＰＣ符号により符号化して符号化データを生成する符号化装置と、前記符号化データを復号化して復号化データを生成する復号化装置と、を具備し、前記復号化装置は、アルファ係数とベータ係数とを用いるＳｕｍ−Ｐｒｏｄｕｃｔアルゴリズムを含む復号化を演算部により行い、前記アルファ係数を算出する演算部と、前記ベータ係数を算出する演算部とを、少なくとも一部共有することを特徴とする。
【発明の効果】
【００１８】
本発明の復号化装置では、ＬＤＰＣ復号部とリードソロモン復号部の２つの復号部を具備しているので、復号化性能を極めて高くすることができる。具体的には、データブロック内部のページ全体が破損するページ抜け（Ｐａｇｅ Ｆａｌｌ）が発生しても、ページ間の符号化を行うリードソロモン復号部により、破損したページを正しく復号することができる。更に、ＬＤＰＣ符号部を用いることにより、復号に失敗した情報を特定した後に、正しくデータを復号することができる。
【００１９】
また、本発明の復号化装置では、ＬＤＰＣ復号化に失敗したシンボルを無効シンボルとした後に、このシンボルの位置を示すイレージャー信号を生成して、これらを用いてリードソロモン符号の復号化を行っている。従って、後段の処理であるリードソロモン符号の誤り訂正能力を向上させることができる。
【００２０】
更にまた、本発明の符号化装置に依れば、ＬＤＰＣ符号化を行う前に、符号化の対象となるデータに含まれるシンボルのサイズを大きくしている。従って、ＬＤＰＣ符号化の誤り訂正性能を向上させることができる。
【００２１】
更にまた、本発明の復号化装置に依れば、共通の計算セル（演算部）で、Ｓｕｍ−ｐｒｏｄｕｃｔに使用されるアルファ係数とベータ係数とを演算している。従って、Ｓｕｍ−ｐｒｏｄｕｃｔアルゴリズムを構成するのに必要とされる回路の規模を縮小することができる。
【発明を実施するための最良の形態】
【００２２】
＜第１の実施の形態：誤り訂正装置の概要＞
本形態では、本発明の一実施形態に係る符号化装置および復号化装置を具備する誤り訂正装置の構成および符号訂正方法を説明する。なお、以下の説明では、符号化装置または復号化装置の内部にてデータを構成する単位要素をシンボルと称し、これらの装置の外部にて伝送、書き込み、保存または読み出しされる情報を構成する単位要素をデータと称する場合もある。
【００２３】
図１を参照して、先ず、本形態の誤り訂正装置１０の概略的構成を説明する。図１（Ａ）は誤り訂正装置１０の概略的構成を示すブロック図であり、図１（Ｂ）〜図１（Ｅ）はＥｒｒｏｒ Ｃｏｒｒｅｃｔｉｎｇ Ｃｏｄｅブロック（ＥＣＣブロック）の構成を示す平面図である。
【００２４】
図１（Ａ）を参照して、本形態の誤り訂正装置１０は、入力された入力データを符号化する符号化装置２０と、伝送経路４０を経由して入力された符号化データを復号する復号化装置３０とを具備している。
【００２５】
ここで、伝送経路４０とは、有線または無線を経由した経路が考えられ、例えばデジタル放送や移動体通信がある。また、伝送経路４０の代替として記録媒体が用いられても良い。例えば、符号化装置２０により生成された符号化データを記録媒体（磁気ディスクや光学ディスク）に記録して、記録媒体から読み出した符号化データを復号化装置３０により復号しても良い。ここで、記録媒体としては、例えばＤＶＤ（Ｄｉｇｉｔａｌ Ｖｅｒｓａｔｉｌｅ Ｄｉｓｃ）やＣＤ（Ｃｏｍｐａｃｔ Ｄｉｓｃ）等のように脱着式のディスクで良いし、ＨＤＤ（Ｈａｒｄ Ｄｉｓｋ Ｄｒｉｖｅ）等のように固定式のディスクでも良い。更に、上記記憶媒体として、フラッシュメモリ等の半導体記憶装置も採用できる。また、ＨＤＶ（Ｈｉｇｈ−Ｄｅｆｉｎｉｔｉｏｎ Ｄｉｇｉｔａｌ Ｖｉｄｅｏ）で使用されるフォログラムディスクが記憶媒体として採用されても良い。更にまた、記憶媒体としては、ブルーレイディスク（Ｂｌｕ−ｒａｙ Ｄｉｓｃ：ＢＤ）やＨＤ ＤＶＤ（Ｈｉｇｈ−Ｄｅｆｉｎｉｔｉｏｎ Ｄｉｇｉｔａｌ Ｖｅｒｓａｔｉｌｅ Ｄｉｓｃ）を採用することもできる。
【００２６】
さらに、符号化装置２０のみが個別に使用者に利用されても良いし、復号化装置３０のみが個別に使用者に利用されても良い。また、本形態の誤り訂正装置１０、符号化装置２０または復号化装置３０は、ハードウェアとして構成されても良いし、ソフトウェアとしてプログラムにより実現されても良い。更には、これらは一部がハードウェアにより構成され、残りの部分がソフトウェアにより実現されても良い。
【００２７】
符号化装置２０は、ＲＳ符号化部２１と、データ変換部２３と、ＬＤＰＣ符号化部２２と、データ変換部２４とを主要に具備している。
【００２８】
ＲＳ（Ｒｅｅｄ Ｓｏｌｏｍｏｎ）符号化部２１では、入力されるデジタルデータである入力データ４２に対してリードソロモン（ＲＳ）符号化が施され、結果として第１符号化データ４３が生成される。具体的には、図１（Ｂ）を参照して、入力データ４２を構成する一単位要素であるＥＣＣブロックは、不図示の複数のページから成り、異なるページに含まれるシンボルに対して、ＲＳ符号化が施され、ページ間冗長データが生成される。図では、ページ間冗長データをＰＯが付された領域で示している。そして、符号化を行う方向は図中で矢印にて示されている。ここで生成される第１符号化データ４３は、実質的な意味を持ち複数のページから成る情報と、この情報から生成されたページ間冗長データ（ＰＯ）から成る。この第１符号化データ４３は、データ変換部２３に転送される。なお、ＥＣＣブロックの詳細は、図２等を参照して後述する。
【００２９】
データ変換部２３では、所定の規則に従って、ＥＣＣブロックに含まれる各シンボルのビット数を増大させる。ここでは、シンボルの情報量が８ビット（ｂｉｔ）から１６ビットに変換されている。シンボルをこのように変換することは本発明の特徴の一つであり、このことによりＬＤＰＣ符号化の誤り訂正率を向上させることができる。ここで、シンボルは必ずしも１６ビットに変換される必要は無く、例えば９ビット〜１５ビット程度でも良く、変換前よりも大きいビット数であればよい。しかしながら、後述するパターンマッチングの工程を考慮すると、シンボルは１６ビットに変換されることが望ましい。ここで、シンボルとは、ＥＣＣブロックに含まれるページを構成する単位要素であり、後述するパターンマッチング等はシンボル毎に行われる。各シンボルのビット数が増大された第１符号化データ４３は、ＬＤＰＣ符号化部２２に転送される。
【００３０】
ＬＤＰＣ符号化部２２は、ＲＳ符号化が施された第１符号化データ４３に対してＬＤＰＣ符号化を施す部位である。上記したＲＳ符号化部２１がページ間の符号化を行ったのに対して、ＬＤＰＣ符号化部２２はページ内の符号化を行う。具体的には、図１（Ｃ）を参照して、ＥＣＣブロックに含まれる全てのページに対して、ＬＤＰＣ符号化が施される。図では、ＬＤＰＣ符号化を行う方向が矢印にて示されている。ＬＤＰＣ符号化によって生成されたページ内冗長データは実質的な情報に付加される。図では、付加されるページ内冗長データをＰＩが付された領域で示している。ここで、生成される第２符号化データは、実質的な意味を有し複数のページから成る情報と、ページ間冗長データ（Ｐ０）と、ページ内冗長データ（ＰＩ）から成る。生成された第２符号化データ４４は、データ変換部２４に転送される。
【００３１】
データ変換部２４では、ＥＣＣブロックを構成する各シンボルの情報量を変換して、情報量を少なくする。例えば、上述したデータ変換部２３にてシンボルが８ビットから１６ビットに変換された場合は、この部位にて１６ビットから８ビットに戻す。更に、戻すための変換を行う際には、データ変換部２３で適用された規則とは逆の規則を用いることもできる。データを元に戻す変換を行わずに符号化装置２０から復号化データを出力することも可能であるが、そうすると伝送するべき情報量が増大してしまう等の問題が発生する。従って、シンボルの情報量を元に戻してから出力することが好適である。シンボルの情報量が元に変換された第２符号化データ４４は、符号化装置２０から出力される。また、この部位の主たる役割は情報量の削減であるので、一般的な情報圧縮技術（即ち、上記した情報変換方法とは異なる方法）により符号化データを圧縮して、各シンボルのビット数を減少させても良い。
【００３２】
第２符号化装置２０から出力された第２符号化データ４４は、伝送経路４０を経由して復号化装置３０に伝送され、後述する復号化装置３０に入力される。ここで、第２符号化データ４４を転送する際には、外部のノイズ等に起因して誤りが発生する。即ち、復号化装置３０に入力される第２符号化データ４４は、符号化装置２０から出力されたものとは異なっている。復号化装置３０では、この誤りを訂正して正しい情報を得る。
【００３３】
復号化装置３０は、データ変換部３３と、ＬＤＰＣ復号化部３１と、データ変換部３４と、ＲＳ復号化部３２とを主要に具備している。
【００３４】
データ変換部３３では、復号化装置に入力された復号化データ（符号化装置２０により生成された第２符号化データ４４）に含まれるシンボルの情報量を変換する。ここでは、シンボルの情報量を８ビットから１６ビットに変換している。ここでの変換は、符号化装置２０のデータ変換部２４に於ける変換と等価（即ち、真逆の変換規則あるいは、可逆変換）である必要がある。
【００３５】
ＬＤＰＣ復号化部３１では、１６ビットのシンボルから構成される第２符号化データ４４に対してＬＤＰＣ復号化を行い、第１復号化データを生成する。具体的には、図１（Ｄ）を参照して、ＥＣＣブロックを構成する各ページに対してページ内の復号化を行う。同図では、復号化を行う方向を矢印にて示している。ここでは、各ページ内に含まれるページ内冗長データを用いて、そのページを復号している。また、ページ間冗長データ（ＰＯ）に対しても、ＬＤＰＣ復号化が行われる。生成された第１復号化データ４５は、データ変換部３４に伝送される。
【００３６】
データ変換部３４では、ＥＣＣブロックを構成する各シンボルのデータを、１６ビットから８ビットに変換する。この変換は、詳細を後述するパターンマッチングにより行い、マッチングしたシンボルには、対応する８ビットのシンボルが割り当てられる。一方、マッチングしないシンボルには、エラーであることを示す８ビットのシンボルが割り当てられ、更に、このシンボルの位置を指し示す別のデータ（Ｅｒａｓｕｒｅ Ｆｌａｇ：イレージャー・フラッグ）が生成される。このイレージャー・フラッグ（イレージャー信号）は、データ変換された第１復号化データ４５と共に、ＲＳ復号化部３２に伝送される。
【００３７】
ＲＳ復号化部３２では、データ変換された第１復号化データ４５に対して、リードソロモン復号化（ＲＳ復号化）を行い、復号化された第２復号化データ４６を生成する。ここで生成される第２復号化データ４６は、入力データ４２と等価である。図１（Ｅ）を参照すると、ＲＳ復号化はページ間のシンボルに対して行われ、ＲＳ復号の方向は矢印にて示されている。
【００３８】
上述したように、本発明では、ページ内の誤り訂正にＬＤＰＣ符号を用いて、ページ間の誤り訂正にリードソロモン符号（ＲＳ符号）を用いている。この組み合わせにより、訂正能力を極めて高くすることができる。ＬＤＰＣ符号とＲＳ符号とを組み合わせた本実施の形態の誤り訂正方法は、ＲＳ符号を２重に組み合わせた誤り訂正方法よりも訂正能力が高くなると共に、回路規模を小さく留められる。
【００３９】
図２を参照して、次に、本発明で用いられるＥＣＣブロックの一例を説明する。図２はＥＣＣブロックの概要を示す図である。
【００４０】
図２を参照して、ＥＣＣブロック１１は、実質的な意味を有するデータ（使用者が使用するデータであり、例えば画像データや文書データ）である情報領域１３と、ページ１２内の誤り訂正を行うために用いられるページ内冗長データ１４と、ページ１２の間の誤り訂正を行うために用いられるページ間冗長データ１５とから成る。１つのＥＣＣブロック１１は、トータルで２０８個（ｒｏｗ）のページ１２から成る。また、１つのページ１２は、実質的な意味を有する情報である１０７２バイトと、その情報の冗長データである５６０バイトから成る。更に、最後の２０個（ｒｏｗ）のページでは、１０７２バイトのページ間冗長データ１５に、５６０バイトのページ内冗長データが付加されている。本発明では、ページ内冗長データ１４はＬＤＰＣ符号であり、ページ間冗長データ１５はＲＳ符号である。
【００４１】
ここで、ページ１２の先頭の数バイト（例えば４バイト）がページ数を示す場合があり、この場合は各ページの先頭の数バイトについては、ＲＳ符号化は行われずにページ間冗長データ１５が生成されなくても良いし、この部分も含めた全体に対してページ間冗長データ１５が生成されても良い。一方、ページ数がページ１２の先頭に挿入されない場合は、ページ１２全体に渡ってＲＳ符号化が行われて、ページ間冗長データ１５が生成される。
【００４２】
図３および図４を参照して、図１に示した符号化装置２０に於けるデータの詳細を説明する。図３および図４の各図は、符号化装置２０の内部に於けるデータの変遷を示す概念図である。
【００４３】
図３（Ａ）を参照して、上述したように、符号化装置２０（図１参照）にて生成されるＥＣＣブロック１１は複数のページから成り、情報領域１３と、ページ内冗長データ１４と、ページ間冗長データ１５とから成る。符号化装置２０では、ユーザーデータである情報領域１３に、ページ内冗長データ１４とページ間冗長データ１５とを付加する。従って、符号化装置２０に入力されるデータ（符号化処理が行われる前のデータ）は、情報領域１３のみから成る。ここで、ページ間冗長データ１５は、ＬＤＰＣ符号化に先行して生成して付与されている。ページ間冗長データ１５はリードソロモン符号化により生成される。
【００４４】
図３（Ｂ）を参照して、情報領域１３の内部の１つのページ１２は、１０７２バイトの情報量を有する。本発明では、先ず、１つのページ１２を８個のデータブロックに分割している。ここで、１つのブロックの情報量は１３４バイト（１０７２ビット）である（図３（Ｃ）および図３（Ｄ）参照）。
【００４５】
図３（Ｅ）を参照して、次に、各データブロックに含まれる８ビットのシンボルを１６ビットに変換する。ここでは、予め用意されたテーブル（表）を用いて、シンボルのビット数を変換する。この変換は、ただ単にシンボルの前後に００００等のデータを付加するのではなく、ＬＤＰＣ符号の誤り訂正能力が向上されるように、ハミング距離が考慮される。この変換により、１つのデータブロックの情報量は、１３４バイト（１０７２ビット）から、２６８バイト（２１４４ビット）に変換される。
【００４６】
図４（Ａ）を参照して、次に、各々のデータブロックに対してＬＤＰＣ符号化を施し、ページ内冗長データ１４（Ｒｅｄｕｎｄａｎｃｙ Ｂｌｏｃｋ）を生成する。本発明では、１つの処理単位であるシンボルを８ビットから１６ビットに変換した後に、ＬＤＰＣ符号化を行っているので、より高度な誤り訂正を行うことができる。
【００４７】
ＬＤＰＣ符号化が終了した後は、データブロックに含まれるシンボルを１６ビットから８ビットに再び変換する。この変換も上述したテーブルを逆に用いて（即ち、所定の規則に従って）行われる。この変換を終えた後のページを図４（Ｂ）に示す。ここでは、１３４バイトのデータブロックに、７０バイトのページ内冗長データ（Ｒｅｄｕｎｄａｎｎｃｙ）が付与されている。
【００４８】
図４（Ｃ）を参照して、ここでは、各々が１３４バイトである８個のデータブロックＭ１〜Ｍ８のそれぞれに対して、７０バイトのページ内冗長データＲ１〜Ｒ８が生成される。従って、ここでは、１つのページの情報量は、これらのデータを積算して１６３２バイトとなる。
【００４９】
上記した行程により、図３（Ａ）に示すページ内冗長データ１４が生成され、ＥＣＣブロック１１が完成する。ＥＣＣブロック１１は、伝送路等を介して復号化装置に伝送される。または、ＣＤ等の記録媒体にＥＣＣブロック１１は書き込まれる。
【００５０】
図５および図６を参照して次に、復号化装置を用いて、符号化された情報を復号化する際のデータの変遷を説明する。
【００５１】
図５（Ａ）を参照して、復号化装置に入力される情報は冗長データが付加されたものであり、具体的には、情報領域１３と、ページ内冗長データ１４と、ページ間冗長データ１５とから成る。このＥＣＣブロック１１は、伝送路等を経て復号装置に入力されるので、エラーが発生し、符号化装置により生成されたものとは異なる場合がある。そこで、復号化装置では、ページ内冗長データ１４とページ間冗長データ１５を用いて、このエラーを訂正する。
【００５２】
図５（Ｂ）および図５（Ｃ）を参照して、ページ内冗長データ１４を含む１ページの情報量は、１６３２バイトであり、各々が２０４バイトである８個のデータブロックに１つのページは分割することができる。
【００５３】
図５（Ｄ）を参照して、１つのデータブロックは、１３４バイトの情報領域と、７０バイトのページ間冗長データから成る。このページ間冗長データは、ＬＤＰＣ符号化により生成されたものである。
【００５４】
図５（Ｅ）および図５（Ｆ）を参照して、１つのページに含まれるデータ（実質的に意味を有している情報）は１３４個のシンボルから成り、各々のシンボルは８ビットの情報量を具備している。
【００５５】
ここで、図５（Ｂ）に示すページ１２の構成は、図４（Ｃ）に示すとおりであり、最初の１０７２バイト（１３４バイト×８個）がユーザーデータであり、その後の５６０バイト（７０バイト×８個）が冗長データである。そしてユーザーデータと冗長データとは、各々が集合して配置されている。図５（Ｃ）および図５（Ｄ）を参照して、ページ内のデータは並べ替えられ、各ユーザーデータにその冗長データが隣接する。即ち、ユーザーデータ（１３４バイト）とそれに隣接した冗長データ（７０バイト）から成るセットが、８個集合して１つのページが構成される。
【００５６】
本発明では、各々のシンボルを８ビットから１６ビットに変換している。この変換は、上述した復号化と同様に、変換のためのテーブルを用いて行われる。従って、各々のデータブロックに含まれる情報量は、１０７２ビットから２１４４ビットとなる。
【００５７】
図６（Ａ）および図６（Ｂ）を参照して、５６０ビットのページ間冗長データを用いて、２１４４ビットの情報に対してＬＤＰＣ復号化を行い、２１４４ビットの復号化データを得る。ここで、ＬＤＰＣ符号が行われても、元の情報に完全に復号されるのではなく、復号化に失敗しているシンボルも存在すると考えられる。そこで、本発明では、後に詳述するパターンマッチングを行って、伝送経路にてデータの欠損が発生したか否かを判断している。更にこの作業は、シンボルのビット数の変換も兼ねている。
【００５８】
図６（Ｃ）に変換された後の８ビットの復号化データを示す。この図を参照して、上記パターンマッチングの結果、正しくマッチングしたものは、テーブル中にて対応する８ビットのシンボルに変換される。一方、正しくマッチングしないシンボルは、正しくマッチングしなかったものに割り当てられるべき８ビットのシンボルが割り当てられる。ここでは、マッチングしなかったシンボルに、「０」を指し示す８ビットのシンボルが割り当てられる。更に、図６（Ｄ）を参照して、イレージャー信号（Ｅｒａｓｕｒｅ Ｐａｔｔｅｒｎ）が生成される。このイレージャー信号は、上記したマッチングの結果、マッチングしなかった（即ち、伝送経路にてデータが破損した）シンボルの位置を指し示す信号である。
【００５９】
上記した復号化データとイレージャー信号を用いて、ＲＳ復号化が行われて、完全な復号化が行われた情報が得られる。イレージャー信号を利用することにより、誤りが生じたシンボルの位置を容易に知ることができるので、ＲＳ復号化により誤り訂正の性能を向上させることができる。
【００６０】
＜第２の実施の形態：符号化方法＞
本形態では、リードソロモン符号化およびＬＤＰＣ符号化を組み合わせた符号化方法を詳述する。
【００６１】
図７のフローチャートを参照して、本形態の復号化方法は、入力された入力データに対してリードソロモン符号化を行って第１符号化データを生成する第１ステップＳ１と、第１符号化データのビット数を変換する第２ステップＳ２と、第１符号化データに対してＬＤＰＣ変換を行って第２符号化データを生成する第３ステップＳ３と、第２符号化データのビット数を変換する第４ステップＳ４とを主要に具備する。
【００６２】
第１ステップ：ＲＳ符号化を行うステップ
図８を参照して、入力されたデータに対してリードソロモン符号化を行うステップを説明する。図８（Ａ）は本ステップで生成されるＥＣＣブロック１１を示す図であり、図８（Ｂ）はＥＣＣブロックの一部を示す図である。
【００６３】
図８（Ａ）を参照して、実質的な意味を有するユーザーデータである情報領域１３は、１８８個（ｒｏｗ）のページ１２から成り、１つのページ１２は、１０７２個のシンボル（１つのシンボルは８ビット）から成る。本ステップでは、異なるページに含まれるシンボルに対してリードソロモン符号化を行い、ページ間冗長データを生成する。従って、本工程で生成されるＥＣＣブロックは、ユーザーデータである情報領域１３と、情報領域に含まれるページ間の冗長であるページ間冗長データ１５から成る。
【００６４】
図８（Ｂ）を参照して、各ページに含まれるシンボルを最上段から、Ｂ［０、ｊ］、Ｂ［１、ｊ］、Ｂ［２、ｊ］、・・・・Ｂ［１８７、ｊ］とした場合、多項式（Ｒｅｍａｉｎｄｅｒ Ｐｏｌｙｎｏｍｉａｌ）Ｒｊは以下の式（１）により計算される。更にここでは、１８８列の実質的な情報に、４７列分のゼロ成分を加えて演算を行い、合計で２３５列としている。この様にゼロの列を加算するのは、リードソロモンコアに、処理されるデータのフォーマットを一致させるためである。この様な処理はパディングと称される。
【００６５】
【数１】
また、上記式（１）は下記式（２）により表現することもできる。
【００６６】
【数２】
更に、上記式（２）中のαは、下記式（３）に示す原始多項式の原始根である。
【００６７】
【数３】
上記計算を、ページ１２間の各々のシンボルに対して行い、ページ間冗長データ１５が生成され、第１符号化データが生成される。
【００６８】
第２ステップ：第１符号化データのビット数を変換するステップ
本ステップでは、ステップ１にて生成された第１符号化データに含まれるシンボルのビット数を変換する。第１ステップにて生成されるデータでは、１つのシンボルのビット数は８ビットである。本工程では、データの含まれるシンボルのビット数を８ビットから１６ビットに変換する。
【００６９】
本ステップでは、シンボルのビット数を８ビットから１６ビットに変換するが、この変換はただ単に変換前のシンボルの前または後に「００００００００」等の情報を付与するのではなく、ＬＤＰＣ符号化の効率が高くなるような変換が行われる。即ち、シンボル内部で情報が分散された疎な状態になるように、シンボルの情報量が１６ビットに変換される。このように疎なシンボルを生成することで、ＬＤＰＣ符号の符号訂正能力を向上させることができる。また、ここで、ビット数を１６ビットに変換しても、シンボルが取り得る値のバリエーションは２５６通りであり８ビットの場合と変わらない。従って、シンボルを増加させることによる計算量の増加は抑制されている。
【００７０】
図９に、本工程で使用されるマッピングテーブルを示す。ここでは、左側の列に１６ビットのシンボルが示され、右側の列にそれに対応する８ビットシンボルが示されている。このテーブルを使用して、ＥＣＣブロックに含まれる全てのシンボルは８ビットから１６ビットに変換される。例えば、１６ビットのシンボルに於ける最下段のシンボル２５５は、それに対応する８ビットシンボル２５５（１１１１＿１１１１）に変換する（割り当てられる）。
【００７１】
次に、図１０および図１１を参照して、上記したテーブル（マッピングテーブル）の生成方法を説明する。図１０（Ａ）は確率分布を示すグラフであり、図１０（Ｂ）はそのグラフを数値化した表であり、図１０（Ｃ）は８ビットシンボルのハミング距離を示す表であり、図１０（Ｄ）はマッピングテーブルである。
【００７２】
先ず、ＬＤＰＣアルゴリズムはＲａｗ Ｄａｔａ Ｆｏｒｍａｔ（１６ビット）を使用することで実現される。この変換テーブルの主たる目的は、８ビットデータを適切な（即ち、変換前よりも疎な状態な）１６ビットデータのシンボルに割り当てることにある。
【００７３】
以下に、上記マッピングテーブルを構築する方法を説明する。最初に、顧客から提供されたデータを利用して、伝送路のノイズを解析する。図１０（Ａ）は、このノイズの性質を可視化したものである。紙面上にて手前側の横軸は伝送路にインプットされるデータを示し、奥行き側に伸びる軸は伝送路から出力されるデータを示し、縦方向の軸はインプット情報とアウトプット情報にエラーが生じる確率であるエラー確率を示している。この解析は、１６ビットシンボル（合計で２５６個）を使用したエラー確率マトリックスを構築することを可能とする。
【００７４】
図１０（Ｃ）を参照して、８ビットバイナリデータのハミング距離が構築される。バイナリＡｄａｔａとバイナリＢｄａｔａとのハミング距離は、ＡｄａｔａとＢｄａｔａとのバイナリ値を比較することにより、簡単に計算できる。例えば、以下の２つの値が有ると仮定した場合、
第１の値：１０００＿００００
第２の値：０００１＿１０１１
第１の値と第２の値とのハミング距離Ｈｄは５である。
【００７５】
図１０（Ｃ）には、８ビットデータの、全ての組合せのハミング距離が示されている。そして、上記した２つのマトリックスは、８ビットデータを１６ビットシンボル（４×４）に割り当てるマッピングテーブルによりリンクされる。
【００７６】
上記した各表（テーブル）を基に、図１０（Ｄ）に示すマッピングテーブルが生成される。このテーブルは、８ビットシンボルを１６ビットシンボルに変換されるときに使用されると共に、逆に、１６ビットシンボルを８ビットシンボルに変換（逆変換）する際にも同じように適用される。
【００７７】
更に、上記マッピングテーブルは、次のような理念に基づいて、生成される。即ち、「インプットされた１６ビットシンボルが、出力されるシンボルよりも高い確率を有している場合は、対応するハミング距離Ｈｄ（Ａ、Ｂ）が可能な限り低くなる。」という基本的考えの基にマッピングテーブルは生成される。
【００７８】
図１１を参照して、次に、効率的にマッピングテーブルを構築する為のアルゴリズムを説明する。図１１（Ａ）はマッチングテーブルの生成方法を示すフローチャートであり、図１１（Ｂ）は最適化を行う前のマッピングテーブルであり、図１１（Ｃ）は最適化を行った後のマッピングテーブルである。このアルゴリズムの主たる目的は、下記式（５）に示される式に示されるハミング比を可能な限り小さくすることにある。
【００７９】
【数５】
図１１（Ａ）に示された各フローチャートの各ステップの具体的処理は以下の通りである。
【００８０】
先ず、ステップＳ１では、８ビットを１６ビットに変換するテーブルを初期化する。８ビットデータと１６ビットデータとは、両方とも昇順にソートされる。そして、上記式（５）に示された式によりハミング平均値を計算する。この式により算出された値を以後、Ｈ参照値と称する。
【００８１】
ステップＳ２では、マッピングテーブルを２つの列になるように置換する。この置換の一例を図１１（Ｂ）および図１１（Ｃ）に示す。置換が終了すると、１６ビットシンボルの０は８ビットデータの１に対応し、１６ビットシンボルの１は、８ビットデータの０に対応する（図１１（Ｃ）参照）。
【００８２】
ステップＳ３では、次に、アップデートされた（置換された）マッピングテーブルを使用して、ハミング平均値を上記式（５）に示された式を使用して計算する。この値をＨｕｐ値と称する。
【００８３】
ステップＳ４では、続いて、Ｈｕｐ値とＨ参照値（Ｈｒｅｆ値と以下にて称する場合もある）とを比較する。
【００８４】
上記ステップＳ４にて、Ｈｕｐ値がＨｒｅｆ値よりも低い場合、（換言すると、この状態のマッピングテーブルが参照のマッピングテーブルよりも適している場合）は、ステップＳ５に移行して、次のような処置をする。即ち、ステップＳ２における置換が記憶されると共に、参照ハミング平均値比がＨｕｐ値としてセットされる（Ｈｒｅｆ値をＨｕｐ値に割り当てる）。
【００８５】
一方、上記ステップＳ４にて、Ｈｕｐ値がＨｒｅｆ値よりも大きい場合、（換言すると、この状態のマッピングテーブルが参照のマッピングテーブルよりも適切でない場合）は、ステップＳ６に移行して、次のような処置をする。即ち、ステップＳ３での置換は記憶されずに、参照のマッピングテーブルを復帰させる（即ち、そのままの状態にしておく）。
【００８６】
上記プロセスは、マッピングテーブルの全ての２列置換に対して行われる。このことによって、本実施の形態の目的に沿った最適なマッピングテーブルが生成される。
【００８７】
第３ステップ：第１符号化データに対してＬＤＰＣ変換を行うステップ
本ステップでは、上記工程により個々のシンボルが８ビットから１６ビットに変換された第１符号化データに対してＬＤＰＣ符号化を行い、ページ内の冗長データを生成して、第２符号化データを生成する。
【００８８】
図１２（Ａ）に本ステップで用いるパリティ検査行列６０を示し、図１２（Ｂ）に本ステップにて生成される第２符号化データを構成するＥＣＣブロック１１を示す。
【００８９】
図１２（Ａ）に示すパリティ検査行列６０は、例えば、５６０行・２７０４列の構成となっている。本形態では、符号化単位となる１ページ分の情報は２１４４ビットであり、５６０個のパリティビットを生成するために更に５６０ビットが付け加えられ、パリティ検査行列６０の列数は２７０４列となる。また、検査行列の右端部には正方形の領域が必要となるので、パリティ検査行列６０の行数は５６０行と成っている。なお、この正方形領域では、対角線の沿った成分は全てが１となっており、対角線より右側は０となっている。更に、この対角線より左側の領域は１が疎に配置されている。
【００９０】
次に、上記したパリティ検査行列６０を各々のページを構成する各ビットと演算して、パリティビットを算出する。このことを換言すれば、各ページについて５６０元の連立方程式を解くことで、各ページに付加されるページ内冗長データが生成される。
【００９１】
このようなパリティ検査行列を用いたページ間冗長データの生成は、ＥＣＣブロックを構成する各ページについて行われる。また、ＲＳ符号化により生成されたページ間冗長データ１５に関しても、ＬＤＰＣ符号化によるページ内冗長データ１４が生成される。
【００９２】
上記ステップにより、図１２（Ｂ）に示す構成のＥＣＣブロック１１が生成される。ＥＣＣブロック１１の構成の詳細は、第１の実施の形態にて上記した。ここでは、ページ１２毎にページ内冗長データ１４が生成され、１つのページに５６０バイトのページ内冗長データ１４が付加される。
【００９３】
本発明の特徴の一つは、ハミング距離が考慮されてビット数が変換された情報に対して、ＬＤＰＣ符号変換を行う点にある。このことにより、冗長データおよび計算量の増大を抑制しつつ、ＬＤＰＣ符号化の誤り訂正能力を向上させることができる。一般的に、誤り訂正のための符号化技術では、符号化の為の冗長データを長くするほど、誤り訂正能力を高めることができる。しかしながら、冗長データを長くすると、伝送又は記録されるべきトータルな情報量が増大してしまい、誤り訂正の為の計算量（計算時間）も長くなってしまう等の問題もある。そこで本形態では、シンボルの情報量を８ビットから１６ビットに変換した後に、このシンボルに対してＬＤＰＣ符号化を行っている。このことにより、シンボルが疎な状態になるので、ＬＤＰＣ符号化の誤り訂正能力が向上される。更に、８ビットのシンボルに適用されるテーブルを用いることができるので、シンボルの情報量が増加することに依る符号化の計算量の増大が抑制される。
【００９４】
第４ステップ：第２符号化データのビット数を変換するステップ
図１３（Ａ）を参照して、本ステップでは、ＬＤＰＣ符号化が行われた第２符号化データの構成するシンボルを、１６ビットから８ビットに変換して、全体の情報量を削減する。具体的には、ＥＣＣブロック１１の中の情報領域１３とページ間冗長データ１５に含まれるシンボルの情報量が、１６ビットから８ビットに変換される。本ステップの情報量の変換が行われた結果、１ページに含まれる情報領域１３の情報量は、２１４４ビットから１０７２ビットに変換される。また、この変換は、ページ間冗長データ１５に対しても行われる。ここでは、各ページに含まれるシンボルの情報量を１６ビットから８ビットに変換しているが、８ビットに以外の情報量（例えば９ビット〜１５ビット）にシンボルが変換されても良い。しかしながら、電気信号が伝送される一般的な伝送路では、８ビットまたは１６ビットの情報が通過することを前提として設計されている場合が多いので、このステップで生成されるシンボルの情報量は８ビットが好適である。
【００９５】
本ステップで、シンボルの情報量を削減することにより、伝送または記録されるべき情報の全体的な量が小さくなる。従って、本形態の符号化装置により生成された符号化データを伝送する場合は、本ステップにてトータルな情報量が削減された結果、伝送路に与える負荷が軽減される。また、生成された符号化データが記憶媒体に記録される場合は、記憶媒体に記録可能な実質的な情報量を増大させることができる。
【００９６】
本ステップの情報量の変換は、上述した第２ステップの情報量の変換とは性質が異なる。上記第２ステップでは、ＬＤＰＣ符号化の誤り訂正能力を向上させるために、シンボルの情報量を８ビットから１６ビットにして疎な状態にした。本ステップでは、情報量の削減が目的であるので、ビット数を変換する表を用意して、この表に従ってシンボルの８ビットを１６ビットに変換すればよい。図１１（Ｂ）にこの変換に用いられる表の一例を示す。
【００９７】
＜第３の実施の形態：復号化方法＞
本形態では、上記第２の実施の形態にて説明した方法により生成された符号化データを復号化して基のデータを得る方法を説明する。
【００９８】
本形態の復号化方法は、図１４に示すフローチャートを参照して、入力された入力データ（符号化データ）を構成するシンボルの情報量を変換する第１ステップＳ１１と、変換されたデータに対してＬＤＰＣ変換を行って第１復号化データを生成する第２ステップＳ１２と、第１復号化データに含まれるシンボルの情報量を変換する第３ステップＳ１３と、第１復号化データに対してＲＳ復号化を行って第２復号化データを生成する第４ステップＳ１４とを具備している。
【００９９】
第１ステップ：入力されたデータのビット数を変換するステップ
本ステップでは、入力された入力データ４９を構成するシンボルのデータ量を変換する。ここで、入力データとは、上述した第２の実施の形態で説明した方法により符号化されたデータである。
【０１００】
本ステップのデータ変換は、上述した第２の実施の形態に於ける第４ステップで行われたデータ変換の逆である。従って、上述した第４ステップのデータ変換がシンボルのデータ量を８ビットから１６ビットに変換するものであった場合は、本ステップではシンボルのデータ量を１６ビットから８ビットに変換する。また、変換に用いるテーブルも、上述した第４ステップと同じものを用いる。図１５に、本ステップのデータ変換に用いるテーブルの一例を示す。
【０１０１】
第２ステップ：ＬＤＰＣ復号化を行うステップ
本ステップでは、上述ステップによりシンボルのビット数が変換された符号化データに対して、ＬＤＰＣ復号化を行い、第1復号化データ４５を生成する。具体的には、Ｓｕｍ−Ｐｒｏｄｕｃｔアルゴリズムに基づく繰り返し復号を行い、推定結果である復号化データを得る。
【０１０２】
本ステップでは対数尤度比（ｌｏｇ ｌｉｋｅｌｉｈｏｏｄ ｒａｔｉｏ）に基づくＳｕｍ−Ｐｒｏｄｕｃｔ復号法を行うので、Ｓｕｍ−Ｐｒｏｄｕｃｔアルゴリズムに入力される入力情報は、入力データ４９自身ではない。
【０１０３】
ここで、図１６（Ａ）に示すようなデータの伝送路（Ｃｈａｎｎｅｌ）を想定し、伝送路に入力されるデータをＸｎとし、伝送路を経由して受信されるデータをＹｎとする。このように仮定した場合、本ステップでは、以下に示す式（４）により算出されるλｎがＳｕｍ−Ｐｒｏｄｕｃｔアルゴリズムに入力される。
【０１０４】
【数４】
上記λｎの値は伝送路の統計学的性質による。即ち、伝送路の種類や状況によってエラーの発生する状況は様々であり、このことがλｎの値に影響するので、その値を求めることは容易ではない。そこで、本発明では、伝送路に発生するエラーの統計学的性質を予め解析し、この解析の結果に基づいて対数尤度比を求めている。
【０１０５】
図１６（Ｂ）に上記解析に基づく結果の一例を示す。この表では、００〜１１の入力に対応して、００〜１１が出力される確率を示している。例えば、００が入力されたときに、００が出力される確率は０．８（８０％）であり、００が入力されたときに１１が出力される確率は０．０（０％）である。
【０１０６】
上記解析結果に基づく対数尤度比の算出方法は次の通りである。先ず、それぞれの出力値に関して、入力値が０である確率（Ｐ０）と、入力値が１である確率（Ｐ１）を算出する。次に、Ｐ１／Ｐ０を算出した後に、ｌｏｇ（Ｐ１／Ｐ０）を算出してλを求める。ここで、Ｐ１がＰ０よりも大きかったらλの値は正となり、Ｐ１がＰ０よりも小さかったらλの値は負となる。
【０１０７】
更に図１６（Ｂ）を参照して、上記算出方法の一例を説明すると、例えば出力値が１０であった場合、入力値が１である確率Ｐ１は、Ｐ１＝０．６＋０．１＝０．７と算出される。また、入力値が０である確率Ｐ０は、Ｐ０＝０．２＋０．１＝０．３と算出される。従って、λ＝ｌｏｇ（０．７／０．３）＝０．３６となる。
【０１０８】
またＬＤＰＣ復号処理では、図１７に示すようなＧａｌｌａｇｅｒ Ｆｕｎｃｔｉｏｎ を用いて計算をしている。ここで、ＲＴＬ（Ｒｅｇｉｓｔｅｒ Ｔｒａｎｓｆｅｒ Ｌｅｖｅｌ）等で復号化装置を構成した場合は、対数の計算にかかるコストは大きくなり、計算時間も長くなる。そこで本形態では、この対数の計算を予め行い、計算結果に基づくルックアップテーブルを生成し、このルックアップテーブルを参照することにより対数を計算している。ルックアップテーブルを用いることにより、復号化に必要とされる計算量を低減させ、計算速度を高速にすると共に回路規模を削減することができる。
【０１０９】
上記方法によりＬＤＰＣ復号化が行われる。係る復号化の他の部分の詳細は、例えば、「低密度パリティ検査符号とその復号法：和田山正著：トリケップス」に記載されている。
【０１１０】
第３ステップ：第1復号化データを変換するステップ
本ステップでは、図１８を参照して、先ステップにて復号された第１復号化データを変換する。図１８（Ａ）は、本ステップに手処理される第１復号化データの一部を示す図であり、図１８（Ｂ）はデータ変換のためのパターンマッチングを示す図であり、図１８（Ｃ）は本ステップの手順を示すフローチャートである。
【０１１１】
本ステップでは、先ステップにて復号化処理されたデータに含まれるシンボルのビット数を変化させる。具体的には、シンボルのビット数を１６ビットから８ビットに変換させる。この処理は、次ステップであるＲＳ復号化のために必要とされる処理である。更に、本ステップでは、先ステップであるＬＤＰＣアルゴリズムにてエラーが発生したエラーを検出している。即ち、ここでは、パターンマッチングを行うことにより、これらの２つの処理を行っている。
【０１１２】
図１８（Ａ）を参照して、ＬＤＰＣ復号化が施されたデータは、１ページが２１４４ビットの情報量を有し、このページに含まれる１シンボルのビット数は１６ビットである。１６ビットの１シンボルは、４×４のマスクシンボルと等価である。このマスクシンボルは、先実施の形態にて、ＬＤＰＣ符号化の前に行われるデータ変換の際に用いられたものと同様なものである。
【０１１３】
図１８（Ｂ）を参照して、本ステップでは、ＬＤＰＣ復号化により得られた第１復号化データに含まれるシンボルと、マスクシンボルとを逐次比較している。即ち、両シンボルのパターンが一致するか否かを確認しており、この作業はパターンマッチングと称されている。このパターンマッチングは、第１復号化データに含まれる全てのシンボルに対して行われる。このマスクシンボルは、８ビットのデータに対応して設けられているので、全部で２５６個存在する。
【０１１４】
図１８（Ｃ）を参照して、上記パターンマッチングの詳細を説明する。本ステップのパターンマッチングでは、先ず、ＬＤＰＣ復号化された第１復号化データに含まれる１６ビットのシンボルを、２５６個存在するマスクシンボルと順次比較する（Ｓ１）。この図に示すパターンマッチングは、第１復号化データを構成する全てのシンボルに対して順次行われる。
【０１１５】
次に、シンボルが多数存在するマスクシンボルの中の一つとマッチするか否かが判断される（Ｓ２）。即ち、Ｓ２では、ＬＤＰＣ復号化により生成された第１復号化データに含まれるシンボルと同一のものが、２５６個存在するマスクシンボルセットの中に存在するか否かが調べられる。
【０１１６】
そして、一致するマスクシンボルが存在したら（Ｓ２のＹＥＳ）、一致したマスクシンボルに対応する８ビットデータが、そのシンボルに割り当てられる（Ｓ３）。このステップを踏むことにより、先工程のＬＤＰＣ復号化にてエラーが発生していないことが確認されると共に、第１復号化データを構成するシンボルのビット数が、１６ビットから８ビットに変換される。
【０１１７】
一方、一致するマスクシンボルが存在しなければ（Ｓ２のＮＯ）、その旨を示す８ビットデータが割り当てられる（Ｓ４）。例えば、「００００００００」が処理対象の１６ビットのシンボルに割り当てられる。ＬＤＰＣ復号化が正常に行われたら（即ち、誤り訂正が正しく行われたら）、２５６個存在するマスクシンボルのいずれか一つとマッチするはずである。従って、処理対象のシンボルとマッチングする（一致する）マスクシンボルが存在しないと云うことは、ＬＤＰＣ復号化が失敗していることを意味している。このことから、ステップＳ４では、復号化に失敗したシンボルの存在および位置を指し示す信号であるイレージャー信号を発生させて、次ステップにてこの信号を利用する。
【０１１８】
以上述べたように、本ステップは、ＬＤＰＣ復号化が施されたデータに対してパターンマッチングを行うことにより、第１復号化データを構成する１６ビットのシンボルが８ビットに変換される。更に、復号化に失敗したシンボルにはその旨を示す８ビットのシンボルが割り当てられ、更に、このシンボルの存在とその位置を示すイレージャー信号が生成される。そして、これらのデータおよび信号は、次ステップにて活用される。
【０１１９】
本ステップのマッチングにより、シンボルのビット数が変換されると共に、復号化の妥当さの是非も判断される。従って、１つの処理によりデータ数変換と復号化の検証が行われるので、処理の複雑化を回避しつつ高度な誤り訂正を行うことができる。
【０１２０】
第４ステップ：第１復号化データをＲＳ復号化するステップ
図１９を参照して、ＲＳ復号化を行うステップを、ＲＳ復号化部３２の構成と共に説明する。このステップの原理と使用される数式は、第１の実施の形態にて説明したので、重複する部分は割愛する。なお、本実施の形態のＲＳ復号方法およりＲＳ復号装置は、通常使用されるものと基本的には同様である。
【０１２１】
本ステップにて用いられるＲＳ復号装置３２は、シンドローム演算部５０と、多項式演算部５１と、シンドローム演算部５２と、Ｅｕｃｉｄｅ演算部５３と、Ｃｈｉｅｎ演算部５４と、エラー訂正部５５とを主要に具備している。
【０１２２】
先ステップにて生成された第１復号化データ４５は、シンドローム演算部５０に入力され、シンドローム演算部５０にてシンドロームが算出される。ここで、シンドロームとは、第１復号化データ４５に、パリティ検査行列を乗じたものである。更に、多項式演算部５１では、入力されたイレージャー信号４７を基に、消失位置を演算する。シンドローム演算部５０および多項式演算部５１の算出結果は、シンドローム演算部５２に伝達される。
【０１２３】
そして、これらの出力結果を利用して、シンドローム演算部５２にて演算を行うことにより、誤りが発生したシンボルの位置とが算出される。
【０１２４】
更に、Ｅｕｃｌｉｄｅ演算部５３およびＣｈｉｅｎ演算部５４では、シンドローム演算部５２の出力結果を利用して、誤り値が演算されると共に演算値がチェックされる。
【０１２５】
最後に、エラー訂正部５５では、前段で算出した値を、誤りが発生している箇所の第１復号化４５に加える。このことにより、誤りが訂正された第２復号化データ４６が生成されて、ＲＳ復号化部３２から外部に出力される。
【０１２６】
＜第４の実施の形態：Ｓｕｍ−ｐｒｏｄｕｃｔアルゴリズムの詳細＞
本実施の形態では、ＬＤＰＣ復号化装置の一部であるＳｕｍ−ｐｒｏｄｕｃｔアルゴリズムの詳細を説明する。通常のＳｕｍ−ｐｒｏｄｕｃｔアルゴリズムと本実施の形態との大きな相違点は、本実施の形態では、Ｓｕｍ−ｐｒｏｄｕｃｔアルゴリズムで使用されるα係数の演算処理と、β計数の演算処理とを合成して行っている点にある。ここで、α係数およびβ係数は、復元されたデータの確かさを示す係数である。
【０１２７】
Ｓｕｍ−ｐｒｏｄｕｃｔアルゴリズムを図２０乃至図２３を参照しつつ説明する。ここで、図２０はＳｕｍ−ｐｒｏｄｕｃｔアルゴリズムの為の回路を示すブロック図であり、図２１はＣＭＰフォーマットおよびＡＢＳフォーマットの詳細を示す表であり、図２２（Ａ）および図２２（Ｂ）はＳＵＭ ＧＡＬＬＡＧＥＲの算出プロセスを示す図であり、図２２（Ｃ）はαｍｎ係数の算出方法を示す図であり、図２３はβ係数の算出方法を示す図である。
【０１２８】
図２０を参照して、Ｓｕｍ−ｐｒｏｄｕｃｔアルゴリズムを実現する回路図は、以下の各ブロックから構成されている。
（１）ＣＯＶ．ＦＭＴ−１
（２）ＧＡＬＬＡＧＥＲ ＦＵＮＣＴＩＯＮ
（３）ＣＡＬＣ．ＳＩＧＮ
（４）ＳＵＭ ＧＡＬＬＡＧＥＲ
（５）ＡＬＰＨＡ ＣＡＬＣＵＬＡＴＩＯＮ
（６）ＣＯＮＶ．ＦＭＴ−２
（７）ＣＡＬＣ．ＢＥＴＡ
（８）ＬＡＭＤＡ ＧＥＮＥＲＡＴＯＲ
（９）ＯＵＴＰＵＴ ＥＳＴＩＭＡＴＩＯＮ
上記各ブロックの機能を以下にて詳述する。
【０１２９】
（１）ＣＯＶ．ＦＭＴ−１
このブロックは、データのフォーマットの変換装置である。入力されるデータ（Ｔｗｏ’Ｓ Ｃｏｍｐｌｅｍｅｎｔ Ｆｏｒｍａｔ（以降ＣＭＰと称する）は、Ｓｉｇｎ−Ａｎｄ−Ｍａｇｎｉｔｕｄｅ Ｆｏｒｍａｔ(以降、ＡＢＳと略称する）に変換される。
【０１３０】
ここで、Ｓｉｇｎ−Ａｎｄ−Ｍａｇｎｉｔｕｄｅ Ｆｏｒｍａｔとは、次の通りである。先ず、ＭＳＢ（Ｍｏｓｔ Ｓｉｇｎｉｆｉｃａｎｔ Ｂｉｔ（最上位のビット）)は記号であり、この記号が０の場合は正であり、この記号が負の場合は負である。そして、残りのビット群は大きさを示している。
【０１３１】
一例として、ＣＭＰフォーマットからＡＢＳフォーマットに変換された５ビットデータのテーブルを、図２１に示す。
【０１３２】
このブロックは、Ｓｕｍ−Ｐｒｏｄｕｃｔ Ａｌｇｏｒｉｔｈｍに適用され、パリティチェックマトリックスの各ラインに於いて、（λｎ’＋βｍｎ’）の値をＡＢＳフォーマットへの変換に使用される。
【０１３３】
（２）ＧＡＬＬＡＧＥＲ ＦＵＮＣＴＩＯＮ
このブロックでは、当該ブロックに入力された情報に対応するＧａｌｌａｇｅｒ Ｆｕｎｃｔｉｏｎの値を算出する。Ｇａｌｌａｇｅｒ Ｆｕｎｃｔｉｏｎの詳細は、下記式（６）に示されている。
【０１３４】
【数６】
このブロックは、ＬＤＰＣデコーダの一部として実施され、Ｓｕｍ−Ｐｒｏｄｕｃｔアルゴリズムに含まれる以下の２つのステップを逐次実行している。
【０１３５】
第１に、アルファ計数の算出プロセスの間、パリティチェックマトリックスＨの各ラインに於いて、ｆ（｜λｎ’＋βｍｎ’｜）の値を算出する。
【０１３６】
第２に、パリティチェックマトリックスＨに含まれるアルファ係数の絶対値を算出する。
【０１３７】
（３）ＣＡＬＣ．ＳＩＧＮ
このブロックに入力される情報は、パリティチェックマトリックスＨを構成する各ラインに含まれる（λｎ’＋βｍｎ’）の値のサイン（符号）である。そして、このブロックの主たる機能は、下記式（７）を計算することにある。
【０１３８】
【数７】
（４）ＳＵＭ ＧＡＬＬＡＧＥＲ
このブロックの構成は、基本的には下記する「（７）ＣＡＬＣ．ＢＥＴＡ」と類似している。
【０１３９】
パリティチェックマトリックスＨに含まれる各々のラインに関して、下記式（８）を実行する。
【０１４０】
【数８】
例えば、パリティチェックマトリックスのある列の重みが３の場合、Ｓｕｍ ｇａｌｌａｇｅｒの計算プロセスは図２２（Ａ）および図２２（Ｂ）に示すようになる。
【０１４１】
（５）ＡＬＰＨＡ ＣＡＬＣＵＬＡＴＩＯＮ
このブロックでは、（３）ＣＡＬＣ．ＳＩＧＮブロックにより算出されたアルファ係数のサインと、それらの絶対値が、第２のＧａｌｌａｇｅｒ Ｆｕｎｃｔｉｏｎ Ｂｌｏｃｋから算出される。
【０１４２】
このブロックの主たる目的は、アルファ係数の各々のサインと絶対値とを集めることにある。５ビット幅のデータの場合の処理方法の一例を、図２２（Ｃ）に示す。
【０１４３】
図２２（Ｃ）を参照すると、ＡＬＰＨＡ ＣＡＬＣＵＬＡＴＩＯＮブロックにより、１ビットのサイン（アルファ係数がプラスかマイナスかを示している）と、４ビットの絶対値（アルファ係数の大きさを示している）とが結合されて、アルファ係数が生成されている。
【０１４４】
（６）ＣＯＮＶ．ＦＭＴ−２
このブロックは、基本的にはデータフォーマットを変換する部位である。ｓｉｇｎ−ａｎｄ−ｍａｇｎｉｔｕｄｅフォーマットの入力情報は、ｔｗｏ’ｓ ｃｏｍｐｌｅｍｅｎｔ ｆｏｒｍａｔ（ＣＭＰ）に変換される。
【０１４５】
このブロックは、Ｓｕｍ−Ｐｒｏｄｕｃｔ ａｌｇｏｒｉｔｈｍに於いて、パリティチェックマトリックスＨの各ｃｏｌｕｍｎに関して、アルファ係数をＣＭＰフォーマットに変換する。
【０１４６】
（７）ＣＡＬＣ．ＢＥＴＡ
このブロックでは、パリティチェックマトリックスＨの各ｃｏｌｕｍｎに関して、β係数を算出すると共に、Ｓｕｍ−ｐｒｏｄｕｃｔ ａｌｇｏｒｉｔｈｍの推定出力値を生成する。
【０１４７】
パリティチェックマトリックスの各ｃｏｌｕｍｎに関して、基本的にこのブロックでは、λ係数とアルファ係数とを加算している。そして、それぞれの（λｋ＋βｍｎ）係数は、これらの値から計算される。
【０１４８】
例えば、図２３には、ｃｏｌｕｍｎ重みが４（４つのアルファ係数のみ）の場合のベータ係数の算出プロセスが示されている。
【０１４９】
（８）ＬＡＭＤＡ ＧＥＮＥＲＡＴＯＲ
このブロックの機能は、Ｓｕｍ−ｐｒｏｄｕｃｔ ａｌｇｏｒｉｔｈｍの入力値から、λ＝〔λ１・・・・・・λＮ〕の値を算出する部位である。この値は、Ｌｏｇ−Ｌｉｋｅｈｏｏｄ Ｒａｔｉｏ（ＬＬＲ）の名称で知られている。
【０１５０】
（９）ＯＵＴＰＵＴ ＥＳＴＩＭＡＴＩＯＮ
先ず、Ｃ＝（Ｃ１、・・・・、ＣＮ）とＳｕｍ−Ｐｒｏｄｕｃｔ Ａｌｇｏｒｉｔｈｍの出力推定値を定義する。この出力推定値は、下記式（９）により実現される。
【０１５１】
【数９】
最後に、出力推定値の吟味が行われる。パリティチェックマトリックスＨを置換した出力であるＣ＝（Ｃ１、・・・・、ＣＮ）のマトリックス乗算を含む。
【０１５２】
この結果がゼロマトリックスであれば、上記推定は正しいことになる。一方、一つでもゼロでないデータがマトリックスに含まれれば、推定出力値は正しくないことを示している。
【０１５３】
上記した各部位の中でも、アルファ係数の算出に寄与する部位は、（１）、（２）、（３）、（４）および（５）であり、ベータ係数の算出に寄与する部位は（６）および（７）である。
【０１５４】
本実施の形態では、演算部（例えば、ＬＳＩの上面に組み込まれた電気回路からなる）により、上記したＳｕｍ−Ｐｒｏｄｕｃｔアルゴリズムを実行している。上記したアルファ係数を演算する演算部と、ベータ係数を演算する演算部とは一部が共用されている。
【０１５５】
具体的には、上記演算部は、入力された入力データに対して加算処理を行う加算部と、加算部から入力されたデータに対して減算処理を行う減算部と、ＣＭＰフォーマットとＡＢＳフォーマットとの変換を行う変換部と、Ｇａｌｌａｇｅｒ Ｆｕｎｃｔｉｕｏｎを演算する変数演算部とを含む。そして、これらの中でも演算部と変数演算部が、ベータ係数算出およびアルファ係数算出に共用される。
【０１５６】
即ち、ベータ係数を算出する際には、加算部、減算部、変換部、変数算出部の順番でデータ処理が行われる。一方、アルファ係数を算出する際には、加算部、減算部、変数算出部、変換部の順番でデータ処理が行われる。
【０１５７】
上記のように、ベータ係数算出およびアルファ係数算出に使用される演算部を共用することにより、個別に演算部を構成した場合と比較して、Ｓｕｍ−Ｐｒｏｄｕｃｔアルゴリズムに必要とされる回路の規模を小さくすることができる。従って、復号化装置や誤り訂正装置の大きさ（即ち、これらの装置が構成されたＬＳＩの大きさ）を小さくすることができる。
【図面の簡単な説明】
【０１５８】
【図１】本発明の符号化装置および復号化装置を説明するための図であり、（Ａ）はブロック図であり、（Ｂ）−（Ｅ）はＥＣＣブロックの概要を示す図である。
【図２】本発明に用いられるＥＣＣブロックの構成を示す図である。
【図３】（Ａ）−（Ｅ）は本発明の符号化の際のデータの構成を示す図である。
【図４】（Ａ）−（Ｃ）は本発明の符号化の際のデータの構成を示す図である。
【図５】（Ａ）−（Ｆ）は本発明の復号化の際のデータの構成を示す図である。
【図６】（Ａ）−（Ｄ）は本発明の復号化の際のデータの構成を示す図である。
【図７】本発明の符号化方法を示すフローチャートである。
【図８】（Ａ）および（Ｂ）は、本発明のＲＳ符号化が施された後のＥＣＣブロックの構成を示す図である。
【図９】本発明のマッピングテーブルを示す表（テーブル）である。
【図１０】本発明の上記マッピングテーブルの生成方法を示す図であり、（Ａ）は確率分布を示す３次元のグラフであり、（Ｂ）はエラーが発生する確率を示す表であり、（Ｃ）はハミング距離を示す表であり、（Ｄ）はマッピングテーブルである。
【図１１】本発明の上記マッピングテーブルの生成方法を示す図であり、（Ａ）はフローチャートであり、（Ｂ）は置換前のマッピングテーブルであり、（Ｃ）は置換後のマッピングテーブルである。
【図１２】本発明のＬＤＰＣ符号化を示す図であり、（Ａ）はパリティ検査行列を示す図であり、（Ｂ）はＥＣＣブロックの構成を示す図である。
【図１３】（Ａ）はＥＣＣブロックの構成を示す図であり、（Ｂ）はマッピングテーブルを示す表である。
【図１４】本発明の復号化方法を示すフローチャートである。
【図１５】本発明のマッピングテーブルを示す表である。
【図１６】本発明のＬＤＰＣ復号化方法を示す図であり、（Ａ）は概念図であり、（Ｂ）は解析結果を示す表である。
【図１７】ＬＤＰＣ復号処理に用いられるＧａｌｌａｇｅｒ Ｆｕｎｃｔｉｏｎを示すグラフである。
【図１８】（Ａ）および（Ｂ）はパターンマッチングを示す図であり、（Ｃ）はこのプロセスを示すフローチャートである。
【図１９】ＲＳ復号化を示すブロック図である。
【図２０】Ｓｕｍ−ｐｒｏｄｕｃｔに用いられる回路を示すブロック図である。
【図２１】ＣＭＰ ｆｏｒｍａｔとＡＢＳ ｆｏｒｍａｔとの関連を示す表である。
【図２２】Ｓｕｍ−ｐｒｏｄｕｃｔの詳細を示す図であり、（Ａ）はパリティチェックマトリックスを示す図であり、（Ｂ）および（Ｃ）はフローチャートである。
【図２３】Ｓｕｍ−ｐｒｏｄｕｃｔの詳細を示す図であり、（Ａ）はパリティチェックマトリックスを示す図であり、（Ｂ）および（Ｃ）はフローチャートである。
【符号の説明】
【０１５９】
１０ 誤り訂正装置
１１ ＥＣＣブロック
１２ ページ
１３ 情報領域
１４ ページ内冗長データ
１５ ページ間冗長データ
２０ 符号化装置
２１ ＲＳ符号化部
２２ ＬＤＰＣ符号化部
２３ データ変換部
２４ データ変換部
３０ 復号化装置
３１ ＬＤＰＣ復号化部
３２ ＲＳ復号化部
３３ データ変換部
３４ データ変換部
４０ 伝送経路
４２ 入力データ
４３ 第１符号化データ
４４ 第２符号化データ
４５ 第１復号化データ
４６ 第２復号化データ
４７ イレージャー信号
４８ 出力データ
４９ 入力データ
５０ シンドローム演算部
５１ 多項式演算部
５２ シンドローム演算部
５３ Ｅｕｃｌｉｄｅ演算部
５４ Ｃｈｅｉｎ演算部
５５ エラー訂正部
６０ パリティ検査行列
【特許請求の範囲】
【請求項１】
入力された入力データを符号化する符号化装置であり、
前記入力データに対してＲＳ符号化を行って第１符号化データを生成するＲＳ符号部と、
前記第１符号化データに対してＬＤＰＣ符号化を行って第２符号化データを生成するＬＤＰＣ符号部と、を具備することを特徴とする符号化装置。
【請求項２】
前記入力データは複数のページからなり、
前記ＲＳ符号部では、ページ間冗長データを生成し、
前記ＬＤＰＣ符号部では、ページ内冗長データを生成することを特徴とする請求項１記載の符号化装置。
【請求項３】
前記ＲＳ符号部と、前記ＬＤＰＣ符号部との間に、前記第１符号化データを構成するシンボルのビット数を多くするデータ変換部を有することを特徴とする請求項１記載の符号化装置。
【請求項４】
符号化データを復号化して復号化データを生成する復号化装置であり、
前記符号化データに対してＬＤＰＣ復号化を行って第１復号化データを生成するＬＤＰＣ復号部と、
前記第１復号化データに対してＲＳ復号化を行って第２復号化データを生成するＲＳ復号部と、を備えることを特徴とする復号化装置。
【請求項５】
前記ＬＤＰＣ復号部は、誤り訂正が不可であった前記第１復号化データが属するシンボルを無効シンボルとし、前記無効シンボルの位置を示すイレージャー信号を発生させ、
前記ＲＳ復号部では、前記イレージャー信号を用いて前記第１復号化データを復号して前記第２復号化データを生成することを特徴とする請求項４記載の復号化装置。
【請求項６】
入力されたデータを符号化して符号化データを生成する符号化装置と、前記符号化データを復号化して復号化データを生成する復号化装置と、を具備し、
前記符号化装置は、前記入力データに対してＲＳ符号化を行って第１符号化データを生成するＲＳ符号部と、前記第１符号化データに対してＬＤＰＣ符号化を行って第２符号化データを生成するＬＤＰＣ符号部と、を備え、
前記復号化装置は、前記第２復号化データに対してＬＤＰＣ復号化を行って第１復号化データを生成するＬＤＰＣ復号部と、前記第１復号化データに対してＲＳ復号化を行って第２復号化データを生成するＲＳ復号部と、を備えることを特徴とする誤り訂正装置。
【請求項７】
多数のシンボルから構成される入力データを符号化する符号化装置であり、
前記入力データに含まれる前記シンボルのビット数を多くするデータ変換部と、
前記入力データに対してＬＤＰＣ符号化を行って符号化データを生成するＬＤＰＣ符号化部と、を具備することを特徴とする符号化装置。
【請求項８】
前記データ変換部では、前記入力データに含まれるシンボルのビット数を８ビットから１６ビットに変換することを特徴とする請求項７記載の符号化装置。
【請求項９】
前記入力データは、ＲＳ符号化が施されたデータであることを特徴とする請求項７記載の符号化装置。
【請求項１０】
前記ＬＤＰＣ符号部の後段に、前記符号化データに含まれるシンボルのビット数を少なくする他のデータ変換部を更に具備することを特徴とする請求項７記載の符号化装置。
【請求項１１】
前記他のデータ変換部が前記シンボルを変換する規則は、前記変換部が前記シンボルを変換する規則と逆であることを特徴とする請求項１０記載の符号化装置。
【請求項１２】
符号化データを復号化して復号化データを生成する復号化装置であり、
前記符号化データに対してＬＤＰＣ復号化を行って前記復号化データを生成するＬＤＰＣ復号部と、
前記復号化データに含まれるシンボルのビット数を少なくするデータ変換部と、を具備することを特徴とする復号化装置。
【請求項１３】
入力された入力データを符号化して符号化データを生成する符号化装置と、前記符号化データを復号化して復号化データを生成する復号化装置、と具備し、
前記符号化装置は、前記入力データに含まれるシンボルのビット数を多くする符号側データ変換部と、前記入力データに対してＬＤＰＣ符号化を行って符号化データを生成するＬＤＰＣ符号部と、を備え、
前記復号化装置は、前記符号化データに対してＬＤＰＣ復号化を行って復号化データを生成するＬＤＰＣ復号部と、前記復号化データに含まれるシンボルのビット数を少なくする復号側データ変換部と、を備えることを特徴とする誤り訂正装置。
【請求項１４】
アルファ係数とベータ係数とを用いるＳｕｍ−ｐｒｏｃｕｃｔアルゴリズムを含む復号化を演算部により行う復号化装置に於いて、
前記アルファ係数を算出する演算部と、前記ベータ係数を算出する演算部とを、少なくとも一部共用することを特徴とする復号化装置。
【請求項１５】
前記アルファ係数及び前記ベータ係数は、記憶部に一時的に記憶されることなく演算されることを特徴とする請求項１４の復号化装置。
【請求項１６】
前記演算部は、入力されたデータに対して加算処理を行う加算部と、前記加算部から入力されたデータに対して減算処理を行う減算部と、前記減算部にて処理されたデータのフォーマットを変換する変換部と、Ｇａｌｌａｇｅｒ Ｆｕｎｃｔｉｏｎを算出する変数算出部とを含み、
前記変換部および前記変数算出部は、前記アルファ係数の算出および、前記ベータ係数算出部の算出の両方に用いられることを特徴とする請求項１４記載の復号化装置。
【請求項１７】
入力された入力データをＬＤＰＣ符号により符号化して符号化データを生成する符号化装置と、前記符号化データを復号化して復号化データを生成する復号化装置と、を具備し、
前記復号化装置は、アルファ係数とベータ係数とを用いるＳｕｍ−Ｐｒｏｄｕｃｔアルゴリズムを含む復号化を演算部により行い、
前記アルファ係数を算出する演算部と、前記ベータ係数を算出する演算部とを、少なくとも一部共有することを特徴とする誤り訂正装置。
【請求項１】
入力された入力データを符号化する符号化装置であり、
前記入力データに対してＲＳ符号化を行って第１符号化データを生成するＲＳ符号部と、
前記第１符号化データに対してＬＤＰＣ符号化を行って第２符号化データを生成するＬＤＰＣ符号部と、を具備することを特徴とする符号化装置。
【請求項２】
前記入力データは複数のページからなり、
前記ＲＳ符号部では、ページ間冗長データを生成し、
前記ＬＤＰＣ符号部では、ページ内冗長データを生成することを特徴とする請求項１記載の符号化装置。
【請求項３】
前記ＲＳ符号部と、前記ＬＤＰＣ符号部との間に、前記第１符号化データを構成するシンボルのビット数を多くするデータ変換部を有することを特徴とする請求項１記載の符号化装置。
【請求項４】
符号化データを復号化して復号化データを生成する復号化装置であり、
前記符号化データに対してＬＤＰＣ復号化を行って第１復号化データを生成するＬＤＰＣ復号部と、
前記第１復号化データに対してＲＳ復号化を行って第２復号化データを生成するＲＳ復号部と、を備えることを特徴とする復号化装置。
【請求項５】
前記ＬＤＰＣ復号部は、誤り訂正が不可であった前記第１復号化データが属するシンボルを無効シンボルとし、前記無効シンボルの位置を示すイレージャー信号を発生させ、
前記ＲＳ復号部では、前記イレージャー信号を用いて前記第１復号化データを復号して前記第２復号化データを生成することを特徴とする請求項４記載の復号化装置。
【請求項６】
入力されたデータを符号化して符号化データを生成する符号化装置と、前記符号化データを復号化して復号化データを生成する復号化装置と、を具備し、
前記符号化装置は、前記入力データに対してＲＳ符号化を行って第１符号化データを生成するＲＳ符号部と、前記第１符号化データに対してＬＤＰＣ符号化を行って第２符号化データを生成するＬＤＰＣ符号部と、を備え、
前記復号化装置は、前記第２復号化データに対してＬＤＰＣ復号化を行って第１復号化データを生成するＬＤＰＣ復号部と、前記第１復号化データに対してＲＳ復号化を行って第２復号化データを生成するＲＳ復号部と、を備えることを特徴とする誤り訂正装置。
【請求項７】
多数のシンボルから構成される入力データを符号化する符号化装置であり、
前記入力データに含まれる前記シンボルのビット数を多くするデータ変換部と、
前記入力データに対してＬＤＰＣ符号化を行って符号化データを生成するＬＤＰＣ符号化部と、を具備することを特徴とする符号化装置。
【請求項８】
前記データ変換部では、前記入力データに含まれるシンボルのビット数を８ビットから１６ビットに変換することを特徴とする請求項７記載の符号化装置。
【請求項９】
前記入力データは、ＲＳ符号化が施されたデータであることを特徴とする請求項７記載の符号化装置。
【請求項１０】
前記ＬＤＰＣ符号部の後段に、前記符号化データに含まれるシンボルのビット数を少なくする他のデータ変換部を更に具備することを特徴とする請求項７記載の符号化装置。
【請求項１１】
前記他のデータ変換部が前記シンボルを変換する規則は、前記変換部が前記シンボルを変換する規則と逆であることを特徴とする請求項１０記載の符号化装置。
【請求項１２】
符号化データを復号化して復号化データを生成する復号化装置であり、
前記符号化データに対してＬＤＰＣ復号化を行って前記復号化データを生成するＬＤＰＣ復号部と、
前記復号化データに含まれるシンボルのビット数を少なくするデータ変換部と、を具備することを特徴とする復号化装置。
【請求項１３】
入力された入力データを符号化して符号化データを生成する符号化装置と、前記符号化データを復号化して復号化データを生成する復号化装置、と具備し、
前記符号化装置は、前記入力データに含まれるシンボルのビット数を多くする符号側データ変換部と、前記入力データに対してＬＤＰＣ符号化を行って符号化データを生成するＬＤＰＣ符号部と、を備え、
前記復号化装置は、前記符号化データに対してＬＤＰＣ復号化を行って復号化データを生成するＬＤＰＣ復号部と、前記復号化データに含まれるシンボルのビット数を少なくする復号側データ変換部と、を備えることを特徴とする誤り訂正装置。
【請求項１４】
アルファ係数とベータ係数とを用いるＳｕｍ−ｐｒｏｃｕｃｔアルゴリズムを含む復号化を演算部により行う復号化装置に於いて、
前記アルファ係数を算出する演算部と、前記ベータ係数を算出する演算部とを、少なくとも一部共用することを特徴とする復号化装置。
【請求項１５】
前記アルファ係数及び前記ベータ係数は、記憶部に一時的に記憶されることなく演算されることを特徴とする請求項１４の復号化装置。
【請求項１６】
前記演算部は、入力されたデータに対して加算処理を行う加算部と、前記加算部から入力されたデータに対して減算処理を行う減算部と、前記減算部にて処理されたデータのフォーマットを変換する変換部と、Ｇａｌｌａｇｅｒ Ｆｕｎｃｔｉｏｎを算出する変数算出部とを含み、
前記変換部および前記変数算出部は、前記アルファ係数の算出および、前記ベータ係数算出部の算出の両方に用いられることを特徴とする請求項１４記載の復号化装置。
【請求項１７】
入力された入力データをＬＤＰＣ符号により符号化して符号化データを生成する符号化装置と、前記符号化データを復号化して復号化データを生成する復号化装置と、を具備し、
前記復号化装置は、アルファ係数とベータ係数とを用いるＳｕｍ−Ｐｒｏｄｕｃｔアルゴリズムを含む復号化を演算部により行い、
前記アルファ係数を算出する演算部と、前記ベータ係数を算出する演算部とを、少なくとも一部共有することを特徴とする誤り訂正装置。
【図１】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１２】
【図１３】
【図１４】
【図１５】
【図１６】
【図１７】
【図１８】
【図１９】
【図２０】
【図２１】
【図２２】
【図２３】
【図１０】
【図１１】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１２】
【図１３】
【図１４】
【図１５】
【図１６】
【図１７】
【図１８】
【図１９】
【図２０】
【図２１】
【図２２】
【図２３】
【図１０】
【図１１】
【公開番号】特開２００７−３３６５２９（Ｐ２００７−３３６５２９Ａ）
【公開日】平成１９年１２月２７日（２００７．１２．２７）
【国際特許分類】
【出願番号】特願２００７−１３０７２７（Ｐ２００７−１３０７２７）
【出願日】平成１９年５月１６日（２００７．５．１６）
【出願人】（３０１０１６１５９）システムエルエスアイ株式会社 (5)
【Ｆターム（参考）】
【公開日】平成１９年１２月２７日（２００７．１２．２７）
【国際特許分類】
【出願日】平成１９年５月１６日（２００７．５．１６）
【出願人】（３０１０１６１５９）システムエルエスアイ株式会社 (5)
【Ｆターム（参考）】
[ Back to top ]