(57)【要約】本発明は、環Ｒ上線形符号により符号化した符号化データを復号する場合に用いて好適な、復号方法および復号装置、プログラム、記録再生装置および方法、並びに、再生装置および方法に関する。低密度化処理部は、ステップＳ２１において、パリティ検査行列低密度化処理を実行し、取得した受信語に含まれるパリティ検査行列の行について線形結合を行い、線形結合結果よりパリティ検査行列を生成することにより、復号に用いられるパリティ検査行列の密度を疎にする。そして、ステップＳ２２において、ＬＤＰＣ復号部は、ステップＳ２１の処理により低密度化されたパリティ検査行列を利用し、サムプロダクトアルゴリズム（ＳＰＡ）を用いた復号処理を行う。ステップＳ２２の処理が終了すると、ＬＤＰＣ復号部は、その受信語に対する復号処理を終了する。本発明は、誤り訂正システムに適用できる。
2004107585.tif 000002
【特許請求の範囲】
【請求項１】
環Ｒ上の線形符号の復号方法であって、
前記線形符号の検査行列に対して、値が１である要素の密度を低密度化させる低密度化処理ステップと、
前記低密度化処理ステップの処理により低密度化された前記検査行列を用いて、前記線形符号をサムプロダクトアルゴリズムにより復号する復号ステップと
を含むことを特徴とする復号方法。
【請求項２】
前記環は、素数のべき乗を元とする有限体である
ことを特徴とする請求の範囲第１項に記載の復号方法。
【請求項３】
前記線形符号は、前記有限体上のＢＣＨ符号またはリードソロモン符号を含む
ことを特徴とする請求の範囲第２項に記載の復号方法。
【請求項４】
前記低密度化処理ステップは、
前記検査行列の各行の線形結合を計算する線形結合計算ステップと、
前記線形結合計算ステップの処理により計算された前記線形結合によって得られるベクトルの集合の中から、符号補空間を張る、より重みの低いベクトル部分集合を抽出し、前記ベクトル部分集合の全ベクトルを行成分とする新たな検査行列を作成する検査行列作成ステップと
を含むことを特徴とする請求の範囲第１項に記載の復号方法。
【請求項５】
前記低密度化処理ステップは、前記有限体上の前記検査行列を、前記有限体の部分体上に所定の次元で展開する展開ステップをさらに含み、
前記線形結合計算ステップは、前記展開ステップの処理により展開された前記検査行列の各行の線形結合を計算する
ことを特徴とする請求の範囲第４項に記載の復号方法。
【請求項６】
環Ｒ上の線形符号の復号装置であって、
前記線形符号の検査行列に対して、値が１である要素の密度を低密度化させる低密度化処理を行う低密度化処理手段と、
前記低密度化処理手段により低密度化された前記検査行列を用いて、前記線形符号をサムプロダクトアルゴリズムにより復号する復号手段と
を備えることを特徴とする復号装置。
【請求項７】
前記環は、素数のべき乗を元とする有限体である
ことを特徴とする請求の範囲第６項に記載の復号装置。
【請求項８】
前記線形符号は、前記有限体上のＢＣＨ符号またはリードソロモン符号を含む
ことを特徴とする請求の範囲第７項に記載の復号装置。
【請求項９】
前記低密度化処理手段は、
前記検査行列の各行の線形結合を計算する線形結合計算手段と、
前記線形結合計算手段により計算された前記線形結合によって得られるベクトルの集合の中から、符号補空間を張る、より重みの低いベクトル部分集合を抽出し、前記ベクトル部分集合の全ベクトルを行成分とする新たな検査行列を作成する検査行列作成手段と
を備えることを特徴とする請求の範囲第６項に記載の復号装置。
【請求項１０】
前記低密度化処理手段は、前記有限体上の前記検査行列を、前記有限体の部分体上に所定の次元で展開する展開手段をさらに備え、
前記線形結合計算手段は、前記展開手段により展開された前記検査行列の各行の線形結合を計算する
ことを特徴とする請求の範囲第９項に記載の復号装置。
【請求項１１】
畳み込み符号化された線形符号を軟判定復号する軟判定復号手段をさらに備え、
前記低密度化処理手段は、前記軟判定復号手段により軟判定復号された前記線形符号の検査行列に対して、値が１である要素の密度を低密度化させる
ことを特徴とする請求の範囲第６項に記載の復号装置。
【請求項１２】
前記軟判定復号手段による前記軟判定復号、前記低密度化処理手段による前記低密度化処理、および前記復号手段による前記復号を繰り返し実行する
ことを特徴とする請求の範囲第１１項に記載の復号装置。
【請求項１３】
環Ｒ上の線形符号の復号をコンピュータに行わせるプログラムにおいて、
前記線形符号の検査行列に対して、値が１である要素の密度を低密度化させる低密度化処理ステップと、
前記低密度化処理ステップの処理により低密度化された前記検査行列を用いて、前記線形符号をサムプロダクトアルゴリズムにより復号する復号ステップと
を含む処理をコンピュータに実行させることを特徴とするプログラム。
【請求項１４】
環Ｒ上の線形符号の復号方法であって、
受信値を入力する入力ステップと、
前記線形符号の検査行列に対し、値が１である要素の密度を低密度化させた前記検査行列と、前記入力ステップの処理により入力された受信値とを用いて、前記線形符号をサムプロダクトアルゴリズムにより復号する復号ステップと
を含むことを特徴とする復号方法。
【請求項１５】
環Ｒ上の線形符号の復号装置であって、
受信値を入力する入力手段と、
前記線形符号の検査行列に対し、値が１である要素の密度を低密度化させた前記検査行列と、前記入力手段により入力された受信値とを用いて、前記線形符号をサムプロダクトアルゴリズムにより復号する復号手段と
を備えることを特徴とする復号装置。
【請求項１６】
環Ｒ上の線形符号の復号をコンピュータに行わせるプログラムにおいて、
受信値を入力する入力ステップと、
前記線形符号の検査行列に対し、値が１である要素の密度を低密度化させた前記検査行列と、前記入力ステップの処理により入力された受信値とを用いて、前記線形符号をサムプロダクトアルゴリズムにより復号する復号ステップと
を含む処理をコンピュータに実行させることを特徴とするプログラム。
【請求項１７】
記録媒体に情報を記録し、前記記録媒体に記録された前記情報を再生する記録再生装置であって、
環Ｒ上の線形符号を前記記録媒体に記録する記録手段と、
前記記録手段により記録された前記線形符号を再生する再生手段と、
前記再生手段により再生された前記線形符号の検査行列に対して、値が１である要素の密度を低密度化させる低密度化処理を行う低密度化処理手段と、
前記低密度化処理手段により低密度化された前記検査行列を用いて、前記線形符号をサムプロダクトアルゴリズムにより復号する復号手段と
を備えることを特徴とする記録再生装置。
【請求項１８】
前記線形符号は、所定の次元で積符号化された線形符号であり、
前記低密度化処理手段は、前記検査行列に対して、各次元に対して、前記低密度化処理を行い、
前記復号手段は、前記低密度化された前記検査行列の各次元に対して、サムプロダクトアルゴリズムによる復号を行う
ことを特徴とする請求の範囲第１７項に記載の記録再生装置。
【請求項１９】
前記低密度化処理手段による前記低密度化処理、および前記復号手段による前記復号を繰り返し実行する
ことを特徴とする請求の範囲第１７項に記載の記録再生装置。
【請求項２０】
記録媒体に情報を記録し、前記記録媒体に記録された前記情報を再生する記録再生装置の記録再生方法であって、
環Ｒ上の線形符号の、前記記録媒体への記録を制御する記録制御ステップと、
前記記録制御ステップの処理により記録が制御された前記線形符号の、再生を制御する再生制御ステップと、
前記再生制御ステップの処理により再生が制御された前記線形符号の検査行列に対して、値が１である要素の密度を低密度化させる低密度化処理を行う低密度化処理ステップと、
前記低密度化処理ステップの処理により低密度化された前記検査行列を用いて、前記線形符号をサムプロダクトアルゴリズムにより復号する復号ステップと
を含むことを特徴とする記録再生方法。
【請求項２１】
記録媒体に情報を記録し、前記記録媒体に記録された前記情報を再生する処理をコンピュータに行わせるプログラムにおいて、
環Ｒ上の線形符号の、前記記録媒体への記録を制御する記録制御ステップと、
前記記録制御ステップの処理により記録が制御された前記線形符号の、再生を制御する再生制御ステップと、
前記再生制御ステップの処理により再生が制御された前記線形符号の検査行列に対して、値が１である要素の密度を低密度化させる低密度化処理を行う低密度化処理ステップと、
前記低密度化処理ステップの処理により低密度化された前記検査行列を用いて、前記線形符号をサムプロダクトアルゴリズムにより復号する復号ステップと
を含む処理をコンピュータに実行させることを特徴とするプログラム。
【請求項２２】
記録媒体に情報を記録し、前記記録媒体に記録された前記情報を再生する記録再生装置であって、
環Ｒ上の線形符号を前記記録媒体に記録する記録手段と、
前記記録手段により記録された前記線形符号を再生する再生手段と、
前記線形符号の検査行列に対し、値が１である要素の密度を低密度化させた前記検査行列を用いて、前記線形符号をサムプロダクトアルゴリズムにより復号する復号手段と
を備えることを特徴とする記録再生装置。
【請求項２３】
記録媒体に情報を記録し、前記記録媒体に記録された前記情報を再生する記録再生装置の記録再生方法であって、
環Ｒ上の線形符号の、前記記録媒体への記録を制御する記録制御ステップと、
前記記録制御ステップの処理により記録が制御された前記線形符号の再生を制御する再生制御ステップと、
前記線形符号の検査行列に対し、値が１である要素の密度を低密度化させた前記検査行列を用いて、前記線形符号をサムプロダクトアルゴリズムにより復号する復号ステップと
を含むことを特徴とする記録再生方法。
【請求項２４】
記録媒体に情報を記録し、前記記録媒体に記録された前記情報を再生する処理をコンピュータに行わせるプログラムにおいて、
環Ｒ上の線形符号の、前記記録媒体への記録を制御する記録制御ステップと、
前記記録制御ステップの処理により記録が制御された前記線形符号の再生を制御する再生制御ステップと、
前記線形符号の検査行列に対し、値が１である要素の密度を低密度化させた前記検査行列を用いて、前記線形符号をサムプロダクトアルゴリズムにより復号する復号ステップと
を含む処理をコンピュータに実行させることを特徴とするプログラム。
【請求項２５】
記録媒体に記録された情報を再生する再生装置であって、
前記記録媒体に記録された、環Ｒ上の線形符号を再生する再生手段と、
前記再生手段により再生された前記線形符号の検査行列に対して、値が１である要素の密度を低密度化させる低密度化処理を行う低密度化処理手段と、
前記低密度化処理手段により低密度化された前記検査行列を用いて、前記線形符号をサムプロダクトアルゴリズムにより復号する復号手段と
を備えることを特徴とする再生装置。
【請求項２６】
前記線形符号は、所定の次元で積符号化された線形符号であり、
前記低密度化処理手段は、前記検査行列に対して、各次元に対して、前記低密度化処理を行い、
前記復号手段は、前記低密度化された前記検査行列の各次元に対して、サムプロダクトアルゴリズムによる復号を行う
ことを特徴とする請求の範囲第２５項に記載の再生装置。
【請求項２７】
前記低密度化処理手段による前記低密度化処理、および前記復号手段による前記復号を繰り返し実行する
ことを特徴とする請求の範囲第２５項に記載の再生装置。
【請求項２８】
記録媒体に記録された情報を再生する再生装置の再生方法であって、
前記記録媒体記録された、環Ｒ上の線形符号の再生を制御する再生制御ステップと、
前記再生制御ステップの処理により再生が制御された前記線形符号の検査行列に対して、値が１である要素の密度を低密度化させる低密度化処理を行う低密度化処理ステップと、
前記低密度化処理ステップの処理により低密度化された前記検査行列を用いて、前記線形符号をサムプロダクトアルゴリズムにより復号する復号ステップと
を含むことを特徴とする再生方法。
【請求項２９】
記録媒体に記録された情報を再生する処理をコンピュータに行わせるプログラムにおいて、
前記記録媒体記録された、環Ｒ上の線形符号の再生を制御する再生制御ステップと、
前記再生制御ステップの処理により再生が制御された前記線形符号の検査行列に対して、値が１である要素の密度を低密度化させる低密度化処理を行う低密度化処理ステップと、
前記低密度化処理ステップの処理により低密度化された前記検査行列を用いて、前記線形符号をサムプロダクトアルゴリズムにより復号する復号ステップと
を含む処理をコンピュータに実行させることを特徴とするプログラム。
【請求項３０】
記録媒体に記録された情報を再生する再生装置であって、
前記記録媒体に記録された、環Ｒ上の線形符号を再生する再生手段と、
前記線形符号の検査行列に対し、値が１である要素の密度を低密度化させた前記検査行列を用いて、前記線形符号をサムプロダクトアルゴリズムにより復号する復号手段と
を備えることを特徴とする再生装置。
【請求項３１】
記録媒体に記録された情報を再生する再生装置の再生方法であって、
前記記録媒体に記録された、環Ｒ上の線形符号の再生を制御する再生制御ステップと、
前記線形符号の検査行列に対し、値が１である要素の密度を低密度化させた前記検査行列を用いて、前記線形符号をサムプロダクトアルゴリズムにより復号する復号ステップと
を含むことを特徴とする再生方法。
【請求項３２】
記録媒体に記録された情報を再生する処理をコンピュータに行わせるプログラムにおいて、
前記記録媒体に記録された、環Ｒ上の線形符号の再生を制御する再生制御ステップと、
前記線形符号の検査行列に対し、値が１である要素の密度を低密度化させた前記検査行列を用いて、前記線形符号をサムプロダクトアルゴリズムにより復号する復号ステップと
を含む処理をコンピュータに実行させることを特徴とするプログラム。
【発明の詳細な説明】
【技術分野】  本発明は、復号方法および復号装置、プログラム、記録再生装置および方法、並びに、再生装置および方法に関し、特に、環Ｒ上線形符号により符号化した符号化データを復号する場合に用いて好適な、復号方法および復号装置、プログラム、記録再生装置および方法、並びに、再生装置および方法に関する。
【背景技術】  近年、例えば、移動体通信や深宇宙通信といった通信分野、及び地上波又は衛星ディジタル放送といった放送分野の研究が著しく進められているが、それに伴い、誤り訂正符号化及び復号の効率化を目的として符号理論に関する研究も盛んに行われている。
符号性能の理論的限界としては、いわゆるシャノン（Ｃ．Ｅ．Ｓｈａｎｎｏｎ）の通信路符号化定理によって与えられるシャノン限界が知られている。符号理論に関する研究は、このシャノン限界に近い性能を示す符号を開発することを目的として行われている。近年では、シャノン限界に近い性能を示す符号化方法として、例えば、並列連接畳み込み符号（ＰＣＣＣ（Ｐａｒａｌｌｅｌ  Ｃｏｎｃａｔｅｎａｔｅｄ  Ｃｏｎｖｏｌｕｔｉｏｎａｌ  Ｃｏｄｅｓ））や、縦列連接畳み込み符号（ＳＣＣＣ（Ｓｅｒｉａｌｌｙ  Ｃｏｎｃａｔｅｎａｔｅｄ  Ｃｏｎｖｏｌｕｔｉｏｎａｌ  Ｃｏｄｅｓ））といった、いわゆるターボ符号化（Ｔｕｒｂｏ  ｃｏｄｉｎｇ）と呼ばれる手法が開発されている。また、これらのターボ符号が開発される一方で、古くから知られる符号化方法である低密度パリティ検査符号（Ｌｏｗ  Ｄｅｎｓｉｔｙ  Ｐａｒｉｔｙ  Ｃｈｅｃｋ  ｃｏｄｅｓ）（以下、ＬＤＰＣ符号という）が脚光を浴びつつある。
ＬＤＰＣ符号は、Ｒ．Ｇ．Ｇａｌｌａｇｅｒによる「Ｒ．Ｇ．Ｇａｌｌａｇｅｒ，″Ｌｏｗ  Ｄｅｎｓｉｔｙ  Ｐａｒｉｔｙ  Ｃｈｅｃｋ  Ｃｏｄｅｓ″，Ｃａｍｂｒｉｄｇｅ，Ｍａｓｓａｃｈｕｓｅｔｔｓ：Ｍ．Ｉ．Ｔ．Ｐｒｅｓｓ，１９６３」において最初に提案されたものであり、その後、「Ｄ．Ｊ．Ｃ．ＭａｃＫａｙ，″Ｇｏｏｄ  ｅｒｒｏｒ  ｃｏｒｒｅｃｔｉｎｇ  ｃｏｄｅｓ  ｂａｓｅｄ  ｏｎ  ｖｅｒｙ  ｓｐａｒｓｅ  ｍａｔｒｉｃｅｓ″，Ｓｕｂｍｉｔｔｅｄ  ｔｏ  ＩＥＥＥ  Ｔｒａｎｓ．Ｉｎｆ．Ｔｈｅｏｒｙ，ＩＴ−４５，ｐｐ．３９９−４３１，１９９９」や、「Ｍ．Ｇ．Ｌｕｂｙ，Ｍ．Ｍｉｔｚｅｎｍａｃｈｅｒ，Ｍ．Ａ．Ｓｈｏｋｒｏｌｌａｈｉ  ａｎｄ  Ｄ．Ａ．Ｓｐｉｅｌｍａｎ，″Ａｎａｌｙｓｉｓ  ｏｆ  ｌｏｗ  ｄｅｎｓｉｔｙ  ｃｏｄｅｓ  ａｎｄ  ｉｍｐｒｏｖｅｄ  ｄｅｓｉｇｎｓ  ｕｓｉｎｇ  ｉｒｒｅｇｕｌａｒ  ｇｒａｐｈｓ″，ｉｎ  Ｐｒｏｃｅｅｄｉｎｇｓ  ｏｆ  ＡＣＭ  Ｓｙｍｐｏｓｉｕｍ  ｏｎ  Ｔｈｅｏｒｙ  ｏｆ  Ｃｏｍｐｕｔｉｎｇ，ｐｐ．２４９−２５８，１９９８」等において再注目されるに至ったものである。
ＬＤＰＣ符号は、近年の研究により、ターボ符号等と同様に、符号長を長くしていくにしたがって、シャノン限界に近い性能が得られることがわかりつつある。また、ＬＤＰＣ符号は、最小距離が符号長に比例するという性質があることから、その特徴として、ブロック誤り確率特性がよく、さらに、ターボ符号等の復号特性において観測される、いわゆるエラーフロア現象が殆ど生じないことも利点として挙げられる。
以下、このようなＬＤＰＣ符号について具体的に説明する。なお、ＬＤＰＣ符号は、線形符号であり、必ずしも２元である必要はないが、ここでは、２元であるものとして説明する。
ＬＤＰＣ符号は、そのＬＤＰＣ符号を定義する検査行列（ｐａｒｉｔｙ  ｃｈｅｃｋ  ｍａｔｒｉｘ）が疎なものであることを最大の特徴とするものである。ここで、疎な行列とは、行列のコンポーネントの″１″の個数が非常に少なく構成されるものであり、疎な検査行列をＨで表すものとすると、そのような検査行列としては、例えば、図１に示されるＨＬＤＰＣように、各行のハミング重み（″１″の数）（ｗｅｉｇｈｔ）が″２″であり、且つ、各列のハミング重みが″４″であるもの等がある。
このように、各行及び各列のハミング重みが一定である検査行列Ｈによって定義されるＬＤＰＣ符号は、レギュラーＬＤＰＣ符号と称される。一方、各行及び各列のハミング重みが一定でない検査行列Ｈによって定義されるＬＤＰＣ符号は、イレギュラーＬＤＰＣ符号と称される。
このようなＬＤＰＣ符号による符号化は、検査行列Ｈに基づいて生成行列Ｇを生成し、この生成行列Ｇを２元の情報メッセージに対して乗算することによって符号語を生成することで実現される。具体的には、ＬＤＰＣ符号による符号化を行う符号化装置は、まず、検査行列Ｈの転置行列ＨＴとの間に、式ＧＨＴ＝０が成立する生成行列Ｇを算出する。ここで、生成行列Ｇが、ｋ×ｎ行列である場合には、符号化装置は、生成行列Ｇに対してｋビットからなる情報メッセージ（ベクトルｕ）を乗算し、ｎビットからなる符号語ｃ（＝ｕＧ）を生成する。この符号化装置によって生成された符号語は、値が″０″の符号ビットが″＋１″に、値が″１″の符号ビットが″１″にといったようにマッピングされて送信され、所定の通信路を介して受信側において受信されることになる。
一方、ＬＤＰＣ符号の復号は、Ｇａｌｌａｇｅｒが確率復号（Ｐｒｏｂａｂｉｌｉｓｔｉｃ  Ｄｅｃｏｄｉｎｇ）と称して提案したアルゴリズムであって、バリアブルノード（ｖａｒｉａｂｌｅ  ｎｏｄｅ（メッセージノード（ｍｅｓｓａｇｅ  ｎｏｄｅ）ともいう。））と、チェックノード（ｃｈｅｃｋ  ｎｏｄｅ）とからなる、いわゆるタナーグラフ（Ｔａｎｎｅｒ  ｇｒａｐｈ）上での確率伝播（ｂｅｌｉｅｆ  ｐｒｏｐａｇａｔｉｏｎ）によるメッセージ・パッシング・アルゴリズムによって行うことが可能である。ここで、以下、適宜、バリアブルノードとチェックノードを、単に、ノードともいう。
例えば、図１に示されるパリティ検査行列ＨＬＤＰＣは、図２に示されるようなタナーグラフによって表される。図２のタナーグラフは、図１のパリティ検査行列ＨＬＤＰＣの各列をバリアブルノード、各行をチェックノードとし、パリティ検査行列ＨＬＤＰＣの値が「１」のｉ行ｊ列の要素に対して、ｊ番目のバリアブルノードとｉ番目のチェックノードをエッジ（ｅｄｇｅ）としてつないでいる。
しかしながら、確率復号においては、各ノード間で受け渡されるメッセージが実数値であることから、解析的に解くためには、連続した値をとるメッセージの確率分布そのものを追跡する必要があり、非常に困難を伴う解析を必要とすることになる。そこで、Ｇａｌｌａｇｅｒは、ＬＤＰＣ符号の復号アルゴリズムとして、アルゴリズムＡ又はアルゴリズムＢを提案している。
ＬＤＰＣ符号の復号は、一般的には、図２に示すような手順にしたがって行われる。なお、ここでは、受信値（受信した符号系列）をＵ０（ｕ０ｉ）とし、チェックノードから出力されるメッセージをｕｊとし、バリアブルノードから出力されるメッセージをｖｉとする。また、ここでは、メッセージとは、値の″０″らしさを、いわゆる対数尤度比（ｌｏｇ  ｌｉｋｅｌｉｈｏｏｄ  ｒａｔｉｏ）で表現した実数値である。
ＬＤＰＣ符号の復号は、一般的には、図３に示すような手順にしたがって行われる。なお、ここでは、受信値（受信した符号系列）をＵ０（ｕ０ｉ）とし、チェックノードから出力されるメッセージをｕｊとし、バリアブルノードから出力されるメッセージをｖｉとする。また、ここでは、メッセージとは、値の″０″らしさを、いわゆる対数尤度比（ｌｏｇ  ｌｉｋｅｌｉｈｏｏｄ  ｒａｔｉｏ）で表現した実数値である。
まず、ＬＤＰＣ符号の復号においては、図３に示すように、ステップＳ１において、受信値Ｕ０（ｕ０ｉ）が受信され、メッセージｕｊが″０″に初期化されるとともに、繰り返し処理のカウンタとしての整数をとる変数ｋが″０″に初期化され、ステップＳ２に進む。ステップＳ２において、受信値Ｕ０（ｕ０ｉ）に基づいて、式（１）に示す演算（バリアブルノードの演算）を行うことによってメッセージｖｉが求められ、さらに、このメッセージｖｉに基づいて、式（２）に示す演算（チェックノードの演算）を行うことによってメッセージｕｊが求められる。
2004107585.tif 000003
ここで、式（１）と式（２）におけるｄｖとｄｃは、それぞれ、検査行列Ｈの縦方向（列）と横方向（行）の″１″の個数を示す任意に選択可能とされるパラメータであり、例えば、（３，６）符号の場合には、ｄｖ＝３，ｄｃ＝６となる。
なお、式（１）または（２）の演算においては、それぞれ、メッセージを出力しようとする枝（ｅｄｇｅ）（バリアブルノードとチェックノードとを結ぶ線）から入力されたメッセージを、和または積演算のパラメータとしては用いないことから、和または積演算の範囲が、１乃至ｄｖ−１または１乃至ｄｃ−１となっている。また、式（２）に示す演算は、実際には、２入力ｖ１，ｖ２に対する１出力で定義される式（３）に示す関数Ｒ（ｖ１，ｖ２）のテーブルを予め作成しておき、これを式（４）に示すように連続的（再帰的）に用いることによって行われる。
2004107585.tif 000004
ステップＳ２では、さらに、変数ｋが″１″だけインクリメントされ、ステップＳ３に進む。ステップＳ３では、変数ｋが所定の繰り返し復号回数Ｎよりも大きいか否かが判定される。ステップＳ３において、変数ｋがＮよりも大きくないと判定された場合、ステップＳ２に戻り、以下、同様の処理が繰り返される。
また、ステップＳ３において、変数ｋがＮよりも大きいと判定された場合、ステップＳ４に進み、式（５）に示す演算を行うことによって最終的に出力する復号結果としてのメッセージｖｉが求められて出力され、ＬＤＰＣ符号の復号処理が終了する。
2004107585.tif 000005
ここで、式（５）の演算は、式（１）の演算とは異なり、バリアブルノードに接続している全ての枝からの入力メッセージを用いて行われる。
このようなＬＤＰＣ符号の復号は、例えば（３，６）符号の場合には、図４に示すように、各ノード間でメッセージの授受が行われる。なお、図４における″＝″で示すノード（バリアブルノード）では、式（１）に示した演算が行われ、″＋″で示すノード（チェックノード）では、式（２）に示した演算が行われる。特に、アルゴリズムＡにおいては、メッセージを２元化し、″＋″で示すノードにて、ｄｃ−１個の入力メッセージの排他的論理和演算を行い、″＝″で示すノードにて、受信値Ｒに対して、ｄｖ−１個の入力メッセージが全て異なるビット値であった場合には、符号を反転して出力する。
また、一方で、近年、ＬＤＰＣ符号の復号の実装法に関する研究も行われている。実装方法について述べる前に、まず、ＬＤＰＣ符号の復号を摸式化して説明する。
図５は、（３，６）ＬＤＰＣ符号（符号化率１／２、符号長１２）の検査行列（ｐａｒｉｔｙ  ｃｈｅｃｋ  ｍａｔｒｉｘ）の例である。ＬＤＰＣ符号の検査行列は、図６のように、タナーグラフを用いて書き表すことができる。ここで、図６において、″＋″で表されるのが、チェックノードであり、″＝″で表されるのが、バリアブルノードである。チェックノードとバリアブルノードは、それぞれ、検査行列の行と列に対応する。チェックノードとバリアブルノードとの間の結線は、枝（ｅｄｇｅ）であり、検査行列の″１″に相当する。即ち、検査行列の第ｊ行第ｉ列のコンポーネントが１である場合には、図６において、上からｉ番目のバリアブルノード（″＝″のノード）と、上からｊ番目のチェックノード（″＋″のノード）とが、枝により接続される。枝は、バリアブルノードに対応する符号ビットが、チェックノードに対応する拘束条件を持つことを表わす。なお、図６は、図５の検査行列のタナーグラフとなっている。
ＬＤＰＣ符号の復号方法としては、サムプロダクトアルゴリズム（Ｓｕｍ  Ｐｒｏｄｕｃｔ  Ａｌｇｏｒｉｔｈｍ）がある（例えば、「和田山正、”低密度パリティ検査符号とｓｕｍ−ｐｒｏｄｕｃｔアルゴリズムについて”、［ｏｎｌｉｎｅ］、平成１３年６月２２日、岡山県立大学、［平成１５年５月１９日検索］、インターネット，〈ＵＲＬ：ｈｔｔｐ：／／ｖｅｇａ．ｃ．ｏｋａ−ｐｕ．ａｃ．ｊｐ／〜ｗａｄａｙａｍａ／ｐｄｆ／ＬＤＰＣ．ｐｄｆ〉」参照）。
このサムプロダクトアルゴリズムでは、バリアブルノードの演算とチェックノードの演算とが繰り返し行われる。
バリアブルノードでは、図７のように、式（１）の演算（バリアブルノード演算）を行う。すなわち、図７において、計算しようとしている枝に対応するメッセージｖｉは、バリアブルノードに繋がっている残りの枝からのメッセージｕ１およびｕ２と、受信情報ｕ０ｉを用いて計算される。他の枝に対応するメッセージも同様に計算される。
次に、チェックノードの演算について説明する前に、式（２）を、式ａ×ｂ＝ｅｘｐ｛１ｎ（｜ａ｜）＋１ｎ（｜ｂ｜）｝×ｓｉｇｎ（ａ）×ｓｉｇｎ（ｂ）の関係を用いて、式（６）のように書き直す。但し、ｓｉｇｎ（ｘ）は、ｘ≧０のとき１であり、ｘ＜０のとき−１である。
2004107585.tif 000006
更に、ｘ≧０において、φ（ｘ）＝１ｎ（ｔａｎｈ（ｘ／２））と定義すると、φ−１（ｘ）＝２ｔａｎｈ−１（ｅ−ｘ）であるから、式（６）は、式（７）のように書くことができる。
2004107585.tif 000007
チェックノードでは、図８のように、式（７）の演算（チェックノード演算）を行う。すなわち、図８において、計算しようとしている枝に対応するメッセージｕｊは、チェックノードに繋がっている残りの枝からのメッセージｖ１，ｖ２，ｖ３，ｖ４，ｖ５を用いて計算される。他の枝に対応するメッセージも同様に計算される。
なお、関数φ（ｘ）は、φ（ｘ）＝１ｎ（（ｅｘ＋１）／（ｅｘ−１））とも表すことができ、ｘ＞０において、φ（ｘ）＝φ−１（ｘ）である。関数φ（ｘ）およびφ−１（ｘ）をハードウェアに実装する際には、ＬＵＴ（Ｌｏｏｋ  Ｕｐ  Ｔａｂｌｅ）を用いて実装される場合があるが、両者共に同一のＬＵＴとなる。
サムプロダクトアルゴリズムをハードウェアに実装する場合、式（１）で表されるバリアブルノード演算および式（７）で表されるチェックノード演算とを、適度な回路規模と動作周波数で繰り返し行うことが必要である。
また、このようなサムプロダクトアルゴリズムを適用したＬＤＰＣ符号の演算コストの算出方法も広く知られている（例えば、「Ｍａｔｔｈｅｗ  Ｃ．Ｄａｖｅｙ，Ｄａｖｉｄ  Ｊ  Ｃ  ＭａｃＫａｙ”Ｌｏｗ  Ｄｅｎｓｉｔｙ  Ｐａｒｉｔｙ  Ｃｈｅｃｋ  Ｃｏｄｅｓ  ｏｖｅｒ  ＧＦ（ｑ）”」参照）。
以上のようにサムプロダクトアルゴリズム（ＳＰＡ）を適応して良い復号性能を得るには、パリティ検査行列が低密度である必要がある。
また、その他の一般の線形符号、例えば、リードソロモン（Ｒｅｅｄ  Ｓｏｌｏｍｏｎ）符号等のパリティ検査行列Ｈは、定義体の原始根をαとした場合、図９のように表される。図９に示されるように、線形符号のパリティ検査行列Ｈは、一般に低密度ではない。このような低密度でないリードソロモン符号には、ユークリッド（Ｅｕｃｌｉｄ）のアルゴリズム等を用いた復号（以下、通常復号と称する）が行われる。
図１０は、リードソロモン符号を用いて誤り訂正を行う誤り訂正システムの構成例を示すブロック図である。図１０に示される誤り訂正システムは、例えば、ディジタルテレビ等のディジタル通信システムに用いられるシステムである。
図１０の誤り訂正システムにおいては、送信側である符号化装置１０より送信されたディジタル情報が、例えばインターネットに代表される通信路２１を介して、受信側である復号装置３０に供給される。
符号化装置１０は、外部より供給された送信用のディジタル情報を、リードソロモン符号を用いて符号化するリードソロモン符号化部１１、符号化されたディジタル情報の並べ替えを行うインタリーバ１２、畳み込み符号化を行う畳み込み符号化部１３、並びに、通信路２１を介して、復号装置３０と通信を行う通信処理部１４からなる。
また、復号装置３０は、通信路２１を介して供給された送信語を取得する通信処理部３１、取得した送信語に畳み込み復号を行う畳み込み復号部３２、並べ替えられた情報を元の順番に戻すデインタリーバ３３、並びに、リードソロモン復号（通常復号）を行うリードソロモン復号部３４からなる。
符号化装置１０の外部より供給された送信用のディジタル情報は、符号化装置１０のリードソロモン符号化部１１において、リードソロモン符号化された後、インタリーバ１２に供給される。インタリーバ１２は、主に通信路２１において発生するバースト的誤りを拡散させるために、情報の並べ替え（インタリービング）を行う。リードソロモン符号は、複数ビットを１シンボルとする誤り訂正を行うので、インタリーバ１２は、シンボル単位でバースト的誤りを拡散するシンボルインタリービングを行う。
並べ替えが行われた送信用のディジタル情報は、さらに、畳み込み符号化部１３において、複数の情報ブロックに基づいて逐次的に符号系列が定まる畳み込み符号が行われる。例えば、拘束長Ｋの畳み込み符号化部１３は、インタリーバ１２よりディジタル情報がｋビットの情報ブロック毎に供給されると、今回供給された情報ブロックだけでなく、過去に供給された情報ブロックも含めたＫ個の情報ブロックに基づいて、ｎビットの符号ブロックに符号化する。
そして、畳み込み符号化されたディジタル情報は、通信処理部１４において、送信可能なデータ形式に変換され、通信路２１を介して復号装置３０に供給される。
復号装置３０は、通信処理部３１において、有線または無線の通信路２１を介して供給された送信語を取得する。取得された送信語は、畳み込み復号部３２により、畳み込み復号が行われる。デインタリーバ３３は、畳み込み復号された情報を取得すると、符号化装置１０のインタリーバ１２において行われたインタリービングに対応した方法で情報の並び替えを行い、並び替えられた情報を元の順序に戻す処理（デインタリービング）を行う。リードソロモン復号部３４は、元の順序に戻されたディジタル情報に、通常復号によるリードソロモン復号処理を行い、符号化される前のディジタル情報を再現し、その情報を復号装置３０の外部に出力する。
以上のようにして、図１０の誤り訂正システムは、通信の際に発生した誤りを訂正し、より正確な通信を行えるようにする。
図１１は、リードソロモン符号を用いて誤り訂正を行う誤り訂正システムを適用した記録再生装置の構成例を示すブロック図である。図１１に示される記録再生装置は、例えば、ＤＶＤ（Ｄｉｇｉｔａｌ  Ｖｅｒｓａｔｉｌｅ  Ｄｉｓｃ）レコードプレーヤ等のディジタル記録媒体記録再生装置である。
図１１の記録再生装置５０は、外部より供給されたディジタル情報を、符号化処理部６０において符号化し、記録再生処理部７０において記録媒体７２に記録する。また、記録再生装置５０は、記録媒体７２に記録されているディジタル情報を、記録再生処理部７０において再生し、復号処理部８０において復号処理を行って元のディジタル情報を取得し、その情報を外部に出力する。
符号化処理部６０は、ディジタル情報に互いに異なる次元に関するリードソロモン符号を行う第１リードソロモン符号化部６１−１乃至第ｎリードソロモン符号化部６１−ｎからなる。
記録再生処理部７０は、符号化処理部６０より供給された情報を記録媒体７２に記録する記録部７１、例えば光ディスク等の記録媒体７２、記録媒体７２に記録されている情報を再生する再生部７３からなる。
また、復号処理部８０は、符号化処理部６０に対応する復号器であり、ディジタル情報に互いに異なる次元に関するリードソロモン復号（通常復号）を行う第１リードソロモン復号部８１−１乃至第ｎリードソロモン復号部８１−ｎからなる。
符号化処理部６０の外部より供給されたディジタル情報は、第１リードソロモン符号化部６１−１において１次元目に関するリードソロモン符号化が行われる。続いて、ディジタル情報は、第２リードソロモン符号化部６１−２乃至第ｎリードソロモン符号化部６１−ｎの各部において、２次元目乃至ｎ次元目までの各次元目に関するリードソロモン符号が行われる。第ｎリードソロモン符号化部６１−ｎによる符号化が終了すると、符号化処理部６０は、符号化されたディジタル情報を記録再生処理部７０に供給する。記録再生処理部７０の記録部７１は、符号化処理部６０より供給されたディジタル情報を記録媒体７２に記録する。
記録再生処理部７０の再生部７３は、記録媒体７２に記録されているディジタル情報（符号化されたディジタル情報）を再生し、復号処理部８０に供給する。
復号処理部８０は、第１リードソロモン復号部８１−１乃至第ｎリードソロモン復号部８１−ｎの各部において、再生部７３より供給されたディジタル情報に、各次元目に関するリードソロモン復号（通常復号）を行い、元のディジタル情報を復元する。なお、復号処理部８０は、符号化処理部６０の場合と逆に、まず、第ｎリードソロモン復号部８１−ｎにおいて第ｎ次元目に関するリードソロモン復号から行い、ｎ−１次元目、ｎ−２次元目と順に次元数を下げるようにリードソロモン復号を行い、最後に第１次元目に関するリードソロモン復号を行う。復号処理部８０は、復元した元のディジタル情報を記録再生装置５０の外部に出力する。
以上のようにして、図１１の記録再生装置５０は、情報の記録や再生の際に発生した情報の誤りを訂正する。
以上のようなリードソロモン符号やＢＣＨ（Ｂｏｓｅ−Ｃｈａｕｄｈｕｒｉ−Ｈｏｃｑｕｅｎｇｈｅｍ）符号等に対する通常復号は、受信した値を「０」または「１」のみで推定する硬判定の受信語に対して行う復号方法である。
しかしながら、軟判定の受信語が得られる場合、通常、軟判定受信語を用いての復号性能に比べて、硬判定受信語を用いての復号性能は劣るので、軟判定受信語が得られるシステムにおいて、上述したようにリードソロモン符号を通常復号するようにした場合、その復号性能が良くならないという課題があった。
そこで、上述したようなサムプロダクトアルゴリズムを用いて復号する方法が考えられるが、一般の線形符号のパリティ検査行列は、通常、低密度ではないため、復号性能は良くならないという課題があった。また、仮に、与えられたパリティ検査行列が低密度であるとしても、大きな有限体上でのサムプロダクトアルゴリズムは、非常に複雑であり、その演算コストも大きくなってしまうという課題もあった。
【発明の開示】
本発明はこのような状況に鑑みてなされたものであり、一般の線形符号に対する復号方法としてサムプロダクトアルゴリズムを適用した場合に、容易に、性能の良い復号処理を行うことができるようにするものである。
本発明の第１の復号方法は、環Ｒ上の線形符号の検査行列に対して、値が１である要素の密度を低密度化させる低密度化処理ステップと、低密度化処理ステップの処理により低密度化された検査行列を用いて、線形符号をサムプロダクトアルゴリズムにより復号する復号ステップとを含むことを特徴とする。
前記環は、素数のべき乗を元とする有限体であることができる。
前記線形符号は、有限体上のＢＣＨ符号またはリードソロモン符号を含むことができる。
前記低密度化処理ステップは、検査行列の各行の線形結合を計算する線形結合計算ステップと、線形結合計算ステップの処理により計算された線形結合によって得られるベクトルの集合の中から、符号補空間を張る、より重みの低いベクトル部分集合を抽出し、ベクトル部分集合の全ベクトルを行成分とする新たな検査行列を作成する検査行列作成ステップとを含むようにすることができる。
前記低密度化処理ステップは、有限体上の検査行列を、有限体の部分体上に所定の次元で展開する展開ステップをさらに含み、線形結合計算ステップは、展開ステップの処理により展開された検査行列の各行の線形結合を計算することができる。
本発明の第１の復号装置は、環Ｒ上の線形符号の検査行列に対して、値が１である要素の密度を低密度化させる低密度化処理を行う低密度化処理手段と、低密度化処理手段により低密度化された検査行列を用いて、線形符号をサムプロダクトアルゴリズムにより復号する復号手段とを備えることを特徴とする。
前記環は、素数のべき乗を元とする有限体であることができる。
前記線形符号は、有限体上のＢＣＨ符号またはリードソロモン符号を含むことができる。
前記低密度化処理手段は、検査行列の各行の線形結合を計算する線形結合計算手段と、線形結合計算手段により計算された線形結合によって得られるベクトルの集合の中から、符号補空間を張る、より重みの低いベクトル部分集合を抽出し、ベクトル部分集合の全ベクトルを行成分とする新たな検査行列を作成する検査行列作成手段とを備えるようにすることができる。
前記低密度化処理手段は、有限体上の検査行列を、有限体の部分体上に所定の次元で展開する展開手段をさらに備え、線形結合計算手段は、展開手段により展開された検査行列の各行の線形結合を計算することができる。
畳み込み符号化された線形符号を軟判定復号する軟判定復号手段をさらに備え、低密度化処理手段は、軟判定復号手段により軟判定復号された線形符号の検査行列に対して、値が１である要素の密度を低密度化させることができる。
前記軟判定復号手段による軟判定復号、低密度化処理手段による低密度化処理、および復号手段による復号を繰り返し実行することができる。
本発明の第１のプログラムは、環Ｒ上の線形符号の検査行列に対して、値が１である要素の密度を低密度化させる低密度化処理ステップと、低密度化処理ステップの処理により低密度化された検査行列を用いて、線形符号をサムプロダクトアルゴリズムにより復号する復号ステップとをコンピュータに実行させることを特徴とする。
本発明の第２の復号方法は、受信値を入力する入力ステップと、線形符号の検査行列に対し、値が１である要素の密度を低密度化させた検査行列と、入力ステップの処理により入力された受信値とを用いて、線形符号をサムプロダクトアルゴリズムにより復号する復号ステップとを含むことを特徴とする。
本発明の第２の復号装置は、受信値を入力する入力手段と、線形符号の検査行列に対し、値が１である要素の密度を低密度化させた検査行列と、入力手段により入力された受信値とを用いて、線形符号をサムプロダクトアルゴリズムにより復号する復号手段とを備えることを特徴とする。
本発明の第２のプログラムは、受信値を入力する入力ステップと、線形符号の検査行列に対し、値が１である要素の密度を低密度化させた検査行列と、入力ステップの処理により入力された受信値とを用いて、線形符号をサムプロダクトアルゴリズムにより復号する復号ステップとをコンピュータに実行させることを特徴とする。
本発明の第１の記録再生装置は、環Ｒ上の線形符号を記録媒体に記録する記録手段と、記録手段により記録された線形符号を再生する再生手段と、再生手段により再生された線形符号の検査行列に対して、値が１である要素の密度を低密度化させる低密度化処理を行う低密度化処理手段と、低密度化処理手段により低密度化された検査行列を用いて、線形符号をサムプロダクトアルゴリズムにより復号する復号手段とを備えることを特徴とする。
前記線形符号は、所定の次元で積符号化された線形符号であり、低密度化処理手段は、検査行列に対して、各次元に対して、低密度化処理を行い、復号手段は、低密度化された検査行列の各次元に対して、サムプロダクトアルゴリズムによる復号を行うことができる。
前記低密度化処理手段による低密度化処理、および復号手段による復号を繰り返し実行することができる。
本発明の第１の記録再生方法は、環Ｒ上の線形符号の、記録媒体への記録を制御する記録制御ステップと、記録制御ステップの処理により記録が制御された線形符号の、再生を制御する再生制御ステップと、再生制御ステップの処理により再生が制御された線形符号の検査行列に対して、値が１である要素の密度を低密度化させる低密度化処理を行う低密度化処理ステップと、低密度化処理ステップの処理により低密度化された検査行列を用いて、線形符号をサムプロダクトアルゴリズムにより復号する復号ステップとを含むことを特徴とする。
本発明の第３のプログラムは、環Ｒ上の線形符号の、前記記録媒体への記録を制御する記録制御ステップと、前記記録制御ステップの処理により記録が制御された前記線形符号の、再生を制御する再生制御ステップと、前記再生制御ステップの処理により再生が制御された前記線形符号の検査行列に対して、値が１である要素の密度を低密度化させる低密度化処理を行う低密度化処理ステップと、前記低密度化処理ステップの処理により低密度化された前記検査行列を用いて、前記線形符号をサムプロダクトアルゴリズムにより復号する復号ステップとをコンピュータに実行させることを特徴とする。
本発明の第２の記録再生装置は、環Ｒ上の線形符号を記録媒体に記録する記録手段と、記録手段により記録された線形符号を再生する再生手段と、線形符号の検査行列に対し、値が１である要素の密度を低密度化させた検査行列を用いて、線形符号をサムプロダクトアルゴリズムにより復号する復号手段とを備えることを特徴とする。
本発明の第２の記録再生方法は、環Ｒ上の線形符号の、記録媒体への記録を制御する記録制御ステップと、記録制御ステップの処理により記録が制御された線形符号の再生を制御する再生制御ステップと、線形符号の検査行列に対し、値が１である要素の密度を低密度化させた検査行列を用いて、線形符号をサムプロダクトアルゴリズムにより復号する復号ステップとを含むことを特徴とする。
本発明の第４のプログラムは、環Ｒ上の線形符号の、記録媒体への記録を制御する記録制御ステップと、記録制御ステップの処理により記録が制御された線形符号の再生を制御する再生制御ステップと、線形符号の検査行列に対し、値が１である要素の密度を低密度化させた検査行列を用いて、線形符号をサムプロダクトアルゴリズムにより復号する復号ステップとをコンピュータに実行させることを特徴とする。
本発明の第１の再生装置は、記録手段により記録された、環Ｒ上の線形符号を再生する再生手段と、再生手段により再生された線形符号の検査行列に対して、値が１である要素の密度を低密度化させる低密度化処理を行う低密度化処理手段と、低密度化処理手段により低密度化された検査行列を用いて、線形符号をサムプロダクトアルゴリズムにより復号する復号手段とを備えることを特徴とする。
前記線形符号は、所定の次元で積符号化された線形符号であり、低密度化処理手段は、検査行列に対して、各次元に対して、低密度化処理を行い、復号手段は、低密度化された検査行列の各次元に対して、サムプロダクトアルゴリズムによる復号を行うことができる。
前記低密度化処理手段による低密度化処理、および復号手段による復号を繰り返し実行することができる。
本発明の第１の再生方法は、記録媒体記録された、環Ｒ上の線形符号の再生を制御する再生制御ステップと、再生制御ステップの処理により再生が制御された線形符号の検査行列に対して、値が１である要素の密度を低密度化させる低密度化処理を行う低密度化処理ステップと、低密度化処理ステップの処理により低密度化された検査行列を用いて、線形符号をサムプロダクトアルゴリズムにより復号する復号ステップとを含むことを特徴とする。
本発明の第５のプログラムは、記録媒体記録された、環Ｒ上の線形符号の再生を制御する再生制御ステップと、再生制御ステップの処理により再生が制御された線形符号の検査行列に対して、値が１である要素の密度を低密度化させる低密度化処理を行う低密度化処理ステップと、低密度化処理ステップの処理により低密度化された検査行列を用いて、線形符号をサムプロダクトアルゴリズムにより復号する復号ステップとをコンピュータに実行させることを特徴とする。
本発明の第２の再生装置は、記録媒体に記録された、環Ｒ上の線形符号を再生する再生手段と、線形符号の検査行列に対し、値が１である要素の密度を低密度化させた検査行列を用いて、線形符号をサムプロダクトアルゴリズムにより復号する復号手段とを備えることを特徴とする。
本発明の第２の再生方法は、記録媒体に記録された、環Ｒ上の線形符号の再生を制御する再生制御ステップと、線形符号の検査行列に対し、値が１である要素の密度を低密度化させた検査行列を用いて、線形符号をサムプロダクトアルゴリズムにより復号する復号ステップとを含むことを特徴とする。
本発明の第６のプログラムは、記録媒体に記録された、環Ｒ上の線形符号の再生を制御する再生制御ステップと、線形符号の検査行列に対し、値が１である要素の密度を低密度化させた検査行列を用いて、線形符号をサムプロダクトアルゴリズムにより復号する復号ステップとをコンピュータに実行させることを特徴とする。
本発明においては、環Ｒ上の線形符号の検査行列に対して、値が１である要素の密度が低密度化され、その低密度化された検査行列が用いられ、線形符号がサムプロダクトアルゴリズムにより復号される。
また本発明においては、値が１である要素の密度を低密度化させた検査行列が用いられて、線形符号がサムプロダクトアルゴリズムにより復号される。
【図面の簡単な説明】  図１は、低密度パリティ検査行列の例を示す図である。
図２は、図１のパリティ検査行列に対応するタナーグラフを説明する図である。
図３は、ＬＤＰＣ符号の復号手順を説明するフローチャートである。
図４は、メッセージの流れを説明する図である。
図５は、ＬＤＰＣ符号の検査行列の例を示す図である。
図６は、検査行列のタナーグラフを示す図である。
図７は、バリアブルノードを示す図である。
図８は、チェックノードを示す図である。
図９は、リードソロモン符号の検査行列の例を示す図である。
図１０は、従来の誤り訂正システムの構成例を閉めす図である。
図１１は、従来の記録再生装置の構成例を示す図である。
図１２は、本発明を適用した復号装置の構成例を示す図である。
図１３は、図１２の復号装置による復号処理を説明するフローチャートである。
図１４は、図１３のステップＳ２１において実行されるパリティ検査行列低密度化処理を説明するフローチャートである。
図１５は、ＢＣＨ符号のパリティ検査行列の例を示す図である。
図１６は、図１５のパリティ検査行列に対応するタナーグラフを示す図である。
図１７は、展開されたパリティ検査行列の例を示す図である。
図１８は、図１７のパリティ検査行列に対応するタナーグラフを示す図である。
図１９は、復号性能を比較するためのグラフである。
図２０は、本発明を適用した復号装置の他の構成例を示す図である。
図２１は、図２０の復号装置による復号処理を説明するフローチャートである。
図２２は、リードソロモン符号におけるパリティ検査行列の例を示す図である。
図２３は、展開されたパリティ検査行列の例を示す図である。
図２４は、復号性能を比較するためのグラフである。
図２５は、本発明を適用した誤り訂正システムの構成例を示すブロック図である。
図２６は、本発明を適用した誤り訂正システムの他の構成例を示すブロック図である。
図２７は、本発明を適用した記録再生装置の構成例を示すブロック図である。
図２８は、記録装置の構成例を示すブロック図である。
図２９は、本発明を適用した再生装置の構成例を示すブロック図である。
図３０は、本発明を適用した記録再生装置の他の構成例を示すブロック図である。
図３１は、本発明を適用した再生装置の他の構成例を示すブロック図である。
図３２は、本発明を適用したコンピュータの一実施の形態の構成例を示すブロック図である。
【発明を実施するための最良の形態】  以下、本発明の実施の形態について説明するが、最初に本発明が適用される技術の例について説明する。
図１２は、本発明を適用した復号装置の構成例を示すブロック図である。
図１２において、復号装置１００は、例えばＢＣＨ符号に対応する復号装置であり、環Ｒ上の（または有限体上の）受信語のパリティ検査行列を十分低密度な行列に変換する低密度化処理部１１０および低密度化されたパリティ検査行列を用いて、受信語を復号するＬＤＰＣ復号部１２１からなる。
低密度化処理部１１０は、パリティ検査行列の行の線形結合を計算する線形結合計算部１１１、線形結合された行を用いて、十分疎なパリティ検査行列を作成するパリティ検査行列作成部１１２、および作成されたパリティ検査行列のランクが元のパリティ検査行列のランクと同じであるか否かを判定する判定処理部１１３により構成される。
線形結合計算部１１１は、取得した受信語に含まれるパリティ検査行列の各行の線形結合を、全ての組み合わせについて計算する。すなわち、線形結合計算部１１１は、ｎ行のパリティ検査行列に対して、２ｎ通りの組み合わせで線形結合を計算する。線形結合計算部１１１は、計算結果および受信語をパリティ検査行列作成部１１２に供給する。
パリティ検査行列作成部１１２は、線形結合計算部１１１より供給された計算結果、すなわち、線形結合された行の中から、所定の条件に従って行を抽出し、その抽出した行により構成されるパリティ検査行列を作成する。パリティ検査行列作成部１１２は、例えば、線形結合された行の中から、値が「１」の要素の数が所定の数以下の行を抽出する等、作成したパリティ検査行列の密度が疎になるように条件を設定し、その条件に該当する行を抽出する。パリティ検査行列作成部１１２は、作成したパリティ検査行列および受信語を判定処理部１１３に供給する。なお、後述するように、判定処理部１１３において、作成したパリティ検査行列のランクが元のパリティ検査行列のランクと異なると判定された場合、パリティ検査行列作成部１１２は、再度、行の抽出を行い、新たなパリティ検査行列を作成する。その際、パリティ検査行列作成部１１２は、前回行った行の抽出の条件を変更し、前回作成されたパリティ検査行列と異なる行で構成されるパリティ検査行列を作成する。
判定処理部１１３は、パリティ検査行列作成部１１２において作成されたパリティ検査行列のランク（階数）が、元のパリティ検査行列のランクと一致するか否かを判定する。ランクが一致すると判定した場合、判定処理部１１３は、受信語と、作成されたパリティ検査行列をＬＤＰＣ復号部１２１に供給する。ランクが一致しないと判定した場合、判定処理部１１３は、処理をパリティ検査行列作成部１１２に戻し、新たなパリティ検査行列を作成させる。
以上のように、低密度化処理部１１０は、受信語に含まれるＢＣＨ符号のパリティ検査行列の密度を低密度化させ、その低密度化されたパリティ検査行列を受信語とともにＬＤＰＣ復号部１２１に供給する。
ＬＤＰＣ復号部１１２は、取得した低密度化されたパリティ検査行列を用いて、受信語をサムプロダクトアルゴリズムにより復号し、復号された受信語を復号装置１００の外部に出力する。
以上のように、低密度化処理部１１０が受信語のパリティ検査行列を低密度化させることにより、ＬＤＰＣ復号部１２１は、その低密度のパリティ検査行列を用いて、サムプロダクトアルゴリズムを用いた復号処理を行うことができ、性能の良い復号処理を行うことができる。また、低密度化処理部１１０が受信語のパリティ検査行列を、線形結合を用いて低密度化させるので、ＬＤＰＣ復号部１２１は、部分体上の復号を行うことができ、演算コストを削減することもできる。すなわち、サムプロダクトアルゴリズムを用いた復号処理を行う前に、パリティ検査行列の密度を、線形結合により低密度化させることにより、復号装置１００は、容易に、性能の良い復号処理を行うことができる。
次に、以上のような復号装置による復号処理について、図１３のフローチャートを参照して説明する。
最初に、復号装置１００の低密度化処理部１１０は、ステップＳ２１において、パリティ検査行列低密度化処理を実行し、取得した受信語に含まれるパリティ検査行列の密度を疎にする。パリティ検査行列低密度化処理の詳細については、図１４のフローチャートを参照して後述する。
そして、ステップＳ２２において、ＬＤＰＣ復号部１２１は、ステップＳ２１の処理により低密度化されたパリティ検査行列を利用し、サムプロダクトアルゴリズム（ＳＰＡ）を用いた復号処理を行う。ステップＳ２２の処理が終了すると、ＬＤＰＣ復号部１２１は、その受信語に対する復号処理を終了する。なお、復号装置１００は、上述した復号処理を受信語毎（ブロック毎）に実行する。
次に、図１４のフローチャートを参照して、図１３のステップＳ２１において実行されるパリティ検査行列低密度化処理の詳細を説明する。
最初に、ステップＳ４１において、低密度化処理部１１０の線形結合計算部１１１は、取得した受信語に含まれるパリティ検査行列の各行を用いて、全ての組み合わせで線形結合を行い、結合結果を計算する。
線形結合を計算した線形結合計算部１１１は、ステップＳ４２において、後述するように行の抽出条件となる変数ｎの値を、例えば「１」等の初期値に設定する。そして、線形結合計算部１１１は、受信語、線形結合の計算結果、および変数ｎをパリティ検査行列作成部１１２に供給し、ステップＳ４３に処理を進める。
ステップＳ４３において、パリティ検査行列作成部１１２は、取得した線形結合結果のそれぞれについて値が「１」の要素の数ｗｅｉｇｈｔを算出し、全ての線形結合結果の中から、値が「１」の要素の数ｗｅｉｇｈｔが変数ｎ以下であるものを抽出し、それらを行とする新たな低密度のパリティ検査行列を作成する。
すなわち、パリティ検査行列作成部１１２は、線形結合計算部１１１において計算された線形結合によって得られるベクトルの集合の中から、符号補空間を張る、より重みの低いベクトル部分集合を抽出し、ベクトル部分集合の全ベクトルを行成分とする新たなパリティ検査行列を作成する。
新たなパリティ検査行列を作成したパリティ検査行列作成部１１２は、ステップＳ４４に処理を進め、変数ｎの値に「１」を加算し、受信語、作成したパリティ検査行列、および、変数ｎを判定処理部１１３に供給する。
受信語、作成したパリティ検査行列、および、変数ｎを供給された判定処理部１１３は、ステップＳ４５において、受信語に含まれる元のパリティ検査行列に関する情報に基づいて、元のパリティ検査行列のランク（階数）と、低密度のパリティ検査行列のランク（階数）とが一致するか否かを判定する。
例えば、低密度のパリティ検査行列のランクが低く、元のパリティ検査行列と一致しないと判定した場合、判定処理部１１３は、ステップＳ４３に処理を戻し、それ以降の処理を繰り返す。すなわち、判定処理部１１３は、パリティ検査行列作成部１１２にその判定結果を供給し、再度、パリティ検査行列作成部１１２に低密度のパリティ検査行列を作成させる。その際、線形結合結果より抽出する条件となる変数ｎの値が前回の処理の時と異なるので、パリティ検査行列作成部１１２は、前回と異なる行を有する（前回と要素が異なる）低密度のパリティ検査行列を作成することができる。
ステップＳ４５において、元のパリティ検査行列のランク（階数）と、低密度のパリティ検査行列のランク（階数）とが一致すると判定した場合、判定処理部１１３は、ステップＳ４６に処理を進め、受信語、および、作成された低密度のパリティ検査行列をＬＤＰＣ復号部１２１に出力し、図１３のステップＳ２２に処理を戻す。
以上のように、復号処理、およびパリティ検査行列低密度化処理を実行することにより、復号装置１００は、サムプロダクトアルゴリズムを用いた復号処理を行う前に、パリティ検査行列の密度を線形結合により低密度化させるので、容易に、性能の良い復号処理を行うことができる。
次に、以上の復号装置１００を用いた具体的な低密度化の例について説明する。
以下においては、有限体を素数のべき乗を元とする有限体ＧＦ（２４）（ＧＦ（２）の４次拡大体）とし、線形符号Ｃとして、符号長１５、情報長７の（１５，７）−ＢＣＨ符号を復号する場合について説明する。
線形符号Ｃのパリティ検査行列Ｈが、例えば、図１５のように与えられるとする。図１５に示されるパリティ検査行列Ｈは８行１５列の行列であり、このパリティ検査行列Ｈに対応するタナーグラフは図１６のように表される。図１６のタナーグラフは、図１５に示されるパリティ検査行列Ｈの各列を「＝」で示されるバリアブルノードで表し、各行を「＋」で示されるチェックノードで表したグラフであり、バリアブルノードとチェックノードを結ぶエッジ（ｅｄｇｅ）の密度が高くなっており、図１５のパリティ検査行列Ｈが低密度の行列でないことを示している。
図１２の低密度化処理部１１０は、上述したように、この８行を用いて線形結合を行い、「１」の密度が少ない２８＝２５６個の行ベクトルを作成する。そして、低密度化処理部１１０は、「１」の個数が４以下の行ベクトルを１５個抽出し、１５元ベクトルを縦に並べて作成した、図１７に示されるような新しい行列Ｈｓｐ４を作成する。図１７に示される行列Ｈｓｐ４に対応するタナーグラフは、図１８に示されるようになる。図１７に示される行列Ｈｓｐ４の行数および列数がともに１５であるので、図１８に示されるタナーグラフのバリアブルノードおよびチェックノードの数がともに１５個になり、図１６の場合と比較して、バリアブルノードとチェックノードを結ぶエッジ（ｅｄｇｅ）の密度が低くなっている。
低密度化処理部１１０は、この行列Ｈｓｐ４をパリティ検査行列とし、ＬＤＰＣ復号部１２１に供給する。ＬＤＰＣ復号部１２１は、図１７に示される低密度のパリティ検査行列Ｈｓｐ４を用いて、受信語に対して、サムプロダクトアルゴリズムを適用した復号を行う。
図１９は、このようなパリティ検査行列を有するＢＣＨ符号をビタビ（Ｖｉｔｅｒｂｉ）復号により最尤復号した場合と、図１７に示されるような低密度パリティ検査行列Ｈｓｐ４を用いてサムプロダクトアルゴリズムによる復号を行った場合の復号性能の比較を示すグラフである。
図１９において、曲線１３１は、サムプロダクトアルゴリズム（ＳＰＡ）による復号結果の、ビットエラーレート（ＢＥＲ）を示しており（（２）ｂｃｈ  １５  ７（ｗｇｔ４）ＳＰＡ  ＢＥＲ）、曲線１３２は、ビタビ復号による復号結果のビットエラーレート（ＢＥＲ）を示している（（１）ｂｃｈ  １５  ７  ＭＬ  ＢＥＲ）。また、点１３３によりプロットされたデータは、サムプロダクトアルゴリズムによる復号結果のフレームエラーレート（ＦＥＲ）を示しており（（２）ｂｃｈ  １５  ７（ｗｇｔ４）ＳＰＡ  ＦＥＲ）、点１３４によりプロットされたデータは、ビタビ復号による復号結果のフレームエラーレート（ＦＥＲ）を示している（（１）ｂｃｈ  １５  ７  ＭＬ  ＦＥＲ）。
最尤復号（図１９の曲線１３２）は、サムプロダクトアルゴリズムの様な確率的復号を用いた場合の性能限界であるが、図１９に示されるように本発明を用いた曲線１３１は、その性能限界に迫る性能をあげている。
以上のように、復号装置１００は、ＢＣＨ符号に対して、サムプロダクトアルゴリズムを用いた復号処理を行う前に、パリティ検査行列の密度を線形結合により低密度化させるので、容易に、性能の良い復号処理を行うことができる。
なお、以上においては、ＢＣＨ符号に対する復号処理について説明したが、これに限らず、例えば、リードソロモン符号等のように、一般的な線形符号であればどのような符号方法であってもよい。以下に、リードソロモン符号に対してサムプロダクトアルゴリズムを適用した復号を行う場合について説明する。
図２０は、本発明を適用した復号装置の他の構成例を示すブロック図である。
図２０において、復号装置１５０は、例えばリードソロモン符号に対応する復号装置であり、受信語のパリティ検査行列を展開する展開処理部１６１、展開されたパリティ検査行列を十分低密度な行列に変換する低密度化処理部１７０、および低密度化されたパリティ検査行列を用いて、受信語を復号するＬＤＰＣ復号部１８１からなる。
展開処理部１６１は、パリティ検査行列の低密度化処理の前処理として、取得した受信語に含まれるパリティ検査行列の各要素をその行列の有限体の次元に応じて、それぞれ所定の次数に展開する。すなわち、展開処理部１６１は、素数のべき乗を元とする有限体上のパリティ検査行列を、その有限体の部分体上に所定の次元で展開する。展開処理部１６１は、その展開されたパリティ検査行列および受信語を低密度化処理部１７０に供給する。
低密度化処理部１７０は、パリティ検査行列の行の線形結合を計算する線形結合計算部１７１、線形結合された行を用いて十分疎なパリティ検査行列を作成するパリティ検査行列作成部１７２、および作成されたパリティ検査行列のランクが元のパリティ検査行列のランクと同じであるか否かを判定する判定処理部１７３により構成される。これらの各部の構成および動作は、それぞれ、図１２に示される復号装置１００の低密度化処理部１１０の場合と同様であるので、それらの説明は省略する。すなわち、低密度化処理部１７０を構成する線形結合計算部１７１乃至判定処理部１７３は、図１２に示される線形結合計算部１１１乃至判定処理部１１３にそれぞれ対応する。ただし、低密度化処理部１７０は、展開処理部１６１より供給された、展開されたパリティ検査行列に対して低密度化処理を行う。
低密度化処理部１７０は、展開処理部１６１により展開されたリードソロモン符号のパリティ検査行列の密度を低密度化させ、その低密度化されたパリティ検査行列を受信語とともにＬＤＰＣ復号部１８１に供給する。
ＬＤＰＣ復号部１８１は、取得した低密度化されたパリティ検査行列を用いて、受信語をサムプロダクトアルゴリズムにより復号し、復号された受信語を復号装置１５０の外部に出力する。
以上のように、低密度化処理部１７０がパリティ検査行列を低密度化させる前に、展開処理部１６１によりパリティ検査行列の展開を行うことにより、ＬＤＰＣ復号部１８１による、低密度化されたパリティ検査行列Ｈｓｐ２４を用いたサムプロダクトアルゴリズムによる復号処理の演算コストは、以下に示される式（８）のように、受信語に含まれるパリティ検査行列Ｈを用いてサムプロダクトアルゴリズムによる復号処理を行った場合と比べて、約４分の１に削減される。
2004107585.tif 000008
従って、復号装置１５０は、容易に、性能の良い復号処理を容易に行うことができる。
次に、以上のような復号装置１５０による復号処理について、図２１のフローチャートを参照して説明する。
最初に、復号装置１５０の展開処理部１６１は、ステップＳ６１において、取得した受信語に含まれるパリティ検査行列をその有限体の次元に合わせて展開する。そして、展開処理部１６１は、展開したパリティ検査行列および受信語を低密度化処理部１７０に供給し、処理をステップＳ６２に進める。
低密度化処理部１７０は、ステップＳ６２において、パリティ検査行列低密度化処理を実行し、展開されたパリティ検査行列の密度を疎にする。パリティ検査行列低密度化処理の詳細については、図１４のフローチャートを参照して説明した場合と同様であるのでその詳細な説明は省略する。ただし、この場合のパリティ検査行列低密度化処理において、低密度化処理部１７０は、上述したように展開処理部１６１により展開されたパリティ検査行列を低密度化させるように処理を行う。
そして、ステップＳ６３において、ＬＤＰＣ復号部１８１は、ステップＳ６２の処理により低密度化されたパリティ検査行列を利用し、サムプロダクトアルゴリズム（ＳＰＡ）を用いた復号処理を行う。ステップＳ６３の処理が終了すると、ＬＤＰＣ復号部１２１は、その受信語に対する復号処理を終了する。なお、復号装置１５０は、上述した復号処理を受信語毎（ブロック毎）に実行する。
以上のように、復号処理を実行することにより、復号装置１５０は、低密度化処理を行う前に、パリティ検査行列の各要素を展開させるので、容易に、性能の良い復号処理を行うことができる。
次に、以上の復号装置１５０を用いた具体的な展開の例について説明する。
以下においては、有限体をＧＦ（２４）とし、線形符号Ｃとして、符号長１５、情報長１１の（１５，１１）−リードソロモン符号を復号する場合について説明する。なお、ＧＦ（２４）の原始根をαとし、その原始根αからなる原始多項式を式（９）とし、符号の生成多項式を式（１０）とする。
2004107585.tif 000009
このときの線形符号Ｃのパリティ検査行列は、図２２に示されるように与えられる。図２２に示されるパリティ検査行列Ｈは４行１５列の行列である。ところで、有限体ＧＦ（２４）は、ＧＦ（２）の４次拡大体であることから、有限体ＧＦ（２４）上の元、行列を全て４次元に展開することが可能である。復号装置１５０の展開処理部１６１は、図２２に示されるパリティ検査行列Ｈを展開し、図２３に示されるような１６行６０列のパリティ検査行列Ｈｅｘｐに変換する。この場合、展開処理部１６１は、図２２に示されるパリティ検査行列Ｈの各要素を４×４の要素群に展開することで、図２３に示されるパリティ検査行列Ｈｅｘｐを生成する。
復号装置１５０の低密度化処理部１７０は、この展開されたパリティ検査行列Ｈｅｘｐに対して低密度化処理を行い、ＬＤＰＣ復号部１８１は、低密度化されたパリティ検査行列Ｈｅｘｐを用いて、サムプロダクトアルゴリズムによる復号処理を行う。
図２４は、このようなパリティ検査行列を有するリードソロモン符号を通常復号した場合と、図２３の展開されたパリティ検査行列Ｈｅｘｐを低密度化したパリティ検査行列Ｈｓｐ２４を用いてサムプロダクトアルゴリズムによる復号を行った場合の復号性能の比較を示すグラフである。
図２４において、曲線１９１は、低密度化したパリティ検査行列Ｈｓｐ２４を用いてサムプロダクトアルゴリズム（ＳＰＡ）による復号を行った場合の復号結果の、ビットエラーレート（ＢＥＲ）を示しており（（４）ＲＳ  ｗｇｔ２４  ＳＰＡ  ＢＥＲ）、曲線１９２は、通常復号による復号結果のビットエラーレート（ＢＥＲ）を示している（（３）ＲＳ  ＯＲＤ  ＢＥＲ）。また、点１９３によりプロットされたデータは、低密度化したパリティ検査行列Ｈｓｐ２４を用いてサムプロダクトアルゴリズムによる復号を行った場合の復号結果のフレームエラーレート（ＦＥＲ）を示しており（（４）ＲＳ  ｗｇｔ２４  ＳＰＡ  ＦＥＲ）、点１９４によりプロットされたデータは、通常復号による復号結果のフレームエラーレート（ＦＥＲ）を示している（（３）ＲＳ  ＯＲＤ  ＦＥＲ）。
図２４に示されるように、本発明を用いた復号の復号結果である曲線１９１（点１９３）は、通常復号の場合の復号結果である曲線１９２（点１９４）と比較して、より良い性能が得られている。
以上のように、復号装置１５０は、リードソロモン符号に対して、サムプロダクトアルゴリズムを用いた復号処理を行う前に、パリティ検査行列の密度を線形結合により低密度化させるので、容易に、性能の良い復号処理を行うことができる。また、復号装置１５０は、パリティ検査行列を低密度化させる前に、パリティ検査行列の各要素、行列を展開するので、演算コストを低く抑えることができる。
図２５は、本発明を適用した、リードソロモン符号を用いた誤り訂正システムの構成例を示すブロック図である。図２５に示される誤り訂正システムは、例えば、ディジタルテレビ等のディジタル通信システムに用いられるシステムである。
図２５の誤り訂正システムにおいては、送信側である符号化装置２１０より送信されたディジタル情報が、例えばインターネットに代表される通信路２２１を介して、受信側である復号装置２３０に供給される。
符号化装置２１０は、外部より供給された送信用のディジタル情報を、リードソロモン符号を用いて符号化するリードソロモン符号化部２１１、符号化されたディジタル情報の並べ替えを行うインタリーバ２１２、畳み込み符号化を行う畳み込み符号化部２１３、並びに、通信路２２１を介して、復号装置２３０と通信を行う通信処理部２１４からなる。
リードソロモン符号化部２１１は、符号化装置２１０の外部より供給されたディジタル情報に対して、リードソロモン符号を用いた符号化処理を行い、符号化されたディジタル情報をインタリーバ２１２に供給する。インタリーバ２１２は、その符号化されたディジタル情報を、主に通信路２２１において発生するバースト的誤りを拡散させるために、情報の並べ替え（インタリービング）を行う。リードソロモン符号は複数ビットを１シンボルとする誤り訂正を行うので、インタリーバ２１２は、シンボル単位でバースト的誤りを拡散するシンボルインタリービングを行う。情報の並べ替えを終了したインタリーバ２１２は、その並び替えられたディジタル情報を畳み込み符号化部２１３に供給する。
畳み込み符号化部２１３は、並び替えられたディジタル情報に対して、過去に符号化した情報を参照し、複数の情報ブロックに基づいて、逐次的に符号系列が定まる畳み込み符号を行う。例えば、拘束長Ｋの畳み込み符号化部２１３は、インタリーバ２１２よりディジタル情報がｋビットの情報ブロック毎に供給されると、今回供給された情報ブロックだけでなく、過去に供給された情報ブロックも含めたＫ個の情報ブロックに基づいて、ｎビットの符号ブロックに符号化する。畳み込み符号化が完了すると、畳み込み符号化部２１３は、畳み込み符号化されたディジタル情報を通信処理部２１４に供給する。
通信処理部２１４は、通信制御処理を行い、所定のプロトコルに基づいて、供給されたディジタル情報を送信語として、通信路２２１を介して復号装置２３０に送信する。
符号化装置２１０より出力されたディジタル情報は、通信路２２１を介して復号装置２３０に供給される。
復号装置２３０は、通信路２２１を介して供給されたディジタル情報を、受信語として受信する通信処理部２３１、通信処理部２３１が取得した受信語に対して、畳み込み復号処理を行う畳み込み復号部２３２、畳み込み復号された受信語を元の順序に並び替えるデインタリーバ２３３、並びに、元の順序に戻されたディジタル情報に、サムプロダクトアルゴリズムによる復号処理を行い、リードソロモン符号化される前のディジタル情報を復元するリードソロモンＳＰＡ復号部２３４からなる。
通信処理部２３１は、通信路２２１を介して符号化装置２１０の通信処理部２１４と通信を行い、所定のプロトコルに基づいて、通信処理部２１４より供給されたディジタル情報を受信語として取得する。通信処理部２３１は、取得した受信語を畳み込み復号部２３２に供給する。
畳み込み復号部２３２は、符号化装置２１０の畳み込み符号化部２１３による符号化方法に対応した方法で、送信処理部２３１より供給された受信語を復号する。すなわち、畳み込み復号部２３２は、受信語に対して、例えば、事後確率最大化復号（ＭＡＰ復号（Ｍａｘｉｍｕｍ  ａ  ｐｏｓｔｅｒｉｏｒｉ  ｐｒｏｂａｂｉｌｉｔｙ  ｄｅｃｏｄｉｎｇ））を実現するＢＣＪＲ（Ｂａｈｌ，Ｃｏｃｋｅ，Ｊｅｌｉｎｅｋ，ａｎｄ  Ｒａｖｉｖ）アルゴリズムやＳＯＶＡ（ｓｏｆｔ  ｏｕｔｐｕｔ  Ｖｉｔｅｒｂｉ  ａｌｇｏｒｉｔｈｍ）等を用いて、軟判定復号を行う。そして、畳み込み復号部２３２は、この軟判定復号された受信語をデインタリーバ２３３に供給する。
デインタリーバ２３３は、供給された受信語に対して、符号化装置２１０のインタリーバ２１２において行われたインタリービングに対応した方法で情報の並び替えを行い、並び替えられた情報を元の順序に戻す処理（デインタリービング）を行い、元の順序に並び替えられた受信語を、リードソロモンＳＰＡ復号部２３４に供給する。
リードソロモンＳＰＡ復号部２３４は、図２０に示される復号装置１５０と基本的に同様の構成であり、基本的に同様の動作を行い、復号装置１５０の場合と同様に、図２０のブロック図、および図２１に示されるフローチャートを適用することができるので、その詳細な説明を省略する。
リードソロモンＳＰＡ復号部２３４は、リードソロモン符号化された受信語に対して、そのパリティ検査行列を展開するとともに低密度化し、そのパリティ検査行列を用いて、サムプロダクトアルゴリズムによる復号処理を行い、符号化される前の元のディジタル情報を復元する。リードソロモンＳＰＡ復号部２３４は、復号したディジタル情報を復号装置２３０の外部に出力する。
以上のようにして、図２５の誤り訂正システムは、容易に、性能の良い復号処理を行うことができ、より正確な通信を行うことができる。また、復号装置２３０は、パリティ検査行列を低密度化させる前に、パリティ検査行列の各要素、行列を展開するので、復号処理の演算コストを低く抑えることができる。
なお、以上においては、誤り訂正システムは、リードソロモン符号を復号するように説明したが、これに限らず、例えば、ＢＣＨ符号を復号するようにしてもよい。
図２６は、本発明を適用した、リードソロモン符号を用いた誤り訂正システムの他の構成例を示すブロック図である。図２６に示される誤り訂正システムは、例えば、ディジタルテレビ等のディジタル通信システムに用いられるシステムである。図２５に示される場合と同様の部分については同一の符号を付しており、その説明を省略する。
図２６の誤り訂正システムにおいては、送信側である符号化装置２１０において符号化されたディジタル情報が、例えばインターネットに代表される通信路２２１を介して、受信側である復号装置２４０に供給される。
復号装置２４０は、通信路２２１を介して供給されたディジタル情報を、受信語として受信する通信処理部２４１、通信処理部２４１が取得した受信語に対して、畳み込み復号処理を行う畳み込み復号部２４２、畳み込み復号された受信語を元の順序に並び替えるデインタリーバ２４３、元の順序に戻されたディジタル情報に、サムプロダクトアルゴリズムによる復号処理を行い、リードソロモン符号化される前のディジタル情報を復元するリードソロモンＳＰＡ復号部２４４、並びに、符号化装置２１０のインタリーバ２１２と同様に、ディジタル情報の並び替えを行うインタリーバ２４５からなる。
通信処理部２４１は、図２５の通信処理部２３１の場合と同様に、通信路２２１を介して符号化装置２１０の通信処理部２１４と通信を行い、所定のプロトコルに基づいて、通信処理部２１４より供給されたディジタル情報を受信語として取得する。通信処理部２４１は、取得した受信語を畳み込み復号部２４２に供給する。
畳み込み復号部２４２は、図２５の畳み込み復号部２３２の場合と同様に、符号化装置２１０の畳み込み符号化部２１３による符号化方法に対応した方法で、送信処理部２４１より供給された受信語を復号する。すなわち、畳み込み復号部２４２は、受信語に対して、例えば、ＢＣＪＲアルゴリズムやＳＯＶＡ等を用いて、軟判定復号を行う。そして、畳み込み復号部２４２は、この軟判定復号された受信語をデインタリーバ２４３に供給する。また、畳み込み復号部２４２には、インタリーバ２４５より、サムプロダクトアルゴリズムによる復号が行われた受信語が再度並び替えられて供給される。畳み込み復号部２４２は、この受信語に対しても、通信処理部２４１より供給された受信語の場合と同様に、例えば、ＢＣＪＲアルゴリズムやＳＯＶＡ等を用いて、軟判定復号を行い、デインタリーバ２４３に供給する。
デインタリーバ２４３は、図２５のデインタリーバ２３３の場合と同様に、畳み込み復号部２４２より供給された受信語に対して、符号化装置２１０のインタリーバ２１２において行われたインタリービングに対応した方法で情報の並び替えを行い、並び替えられた情報を元の順序に戻す処理（デインタリービング）を行い、元の順序に並び替えられた受信語を、リードソロモンＳＰＡ復号部２４４に供給する。なお、上述したように、畳み込み復号部２４２より供給される受信語には、通信処理部２４１から畳み込み復号部２４２を介して供給される受信語の他に、インタリーバ２４５から畳み込み復号部２４２を介して供給される受信語も含まれる。
リードソロモンＳＰＡ復号部２４４は、図２５のリードソロモンＳＰＡ復号部２４４の場合と同様に、図２０に示される復号装置１５０と基本的に同様の構成であり、基本的に同様の動作を行い、復号装置１５０の場合と同様に、図２０のブロック図、および図２１に示されるフローチャートを適用することができる。
リードソロモンＳＰＡ復号部２４４は、デインタリーバ２４３より取得した受信語に対して、その受信語に含まれるパリティ検査行列を展開するとともに低密度化し、そのパリティ検査行列を用いてサムプロダクトアルゴリズムによる復号処理を行い、符号化される前の元のディジタル情報を復元する。リードソロモンＳＰＡ復号部２４４は、復号したディジタル情報を復号装置２４０の外部に出力する。また、リードソロモンＳＰＡ復号部２４４は、その復号したディジタル情報をインタリーバ２４５に供給する。
インタリーバ２４５は、符号化装置２１０のインタリーバ２１２と同様に、取得したディジタル情報を所定の順番に並び替える。このインタリーバ２４５による並び替えのパターンは、インタリーバ２１２と同様である。このようにして並び替えられたディジタル情報は、畳み込み復号部２４２に供給される。
以上のように、復号装置２４０は、通信処理部２４１において取得した受信語に対して、デインタリーバ２４３とインタリーバ２４５を介しながら、畳み込み復号部２４２による軟判定復号と、リードソロモンＳＰＡ復号部２４４によるサムプロダクトアルゴリズムを用いた復号とを繰り返し行い、復号処理における復号誤り確率を小さくしていく。なお、この復号の繰り返し回数は、予め定められていてもよいし、例えば、誤り訂正する箇所の数等のような所定の条件に基づいて、繰り返しを中止するか否かが判定されるようにしてもよい。
このようにすることで、復号装置２４０は、容易に性能の良い復号処理を行うことができ、図２６の誤り訂正システムは、より正確な通信を行うことができる。また、復号装置２４０は、パリティ検査行列を低密度化させる前に、パリティ検査行列の各要素、行列を展開するので、復号処理の演算コストを低く抑えることができる。
なお、以上において、リードソロモンＳＰＡ復号部２４４は、復号したディジタル情報を復号装置２４０の外部に出力するとともにインタリーバ２４５に供給するように説明したが、これに限らず、例えば、復号を繰り返している間は、インタリーバ２４５にのみ復号したディジタル情報を供給するようにし、復号の繰り返しが終了した場合に、ディジタル情報の出力先をインタリーバ２４５から復号装置２４０の外部に切り替えて、復号したディジタル情報を出力するようにしてもよい。
なお、以上においては、誤り訂正システムは、リードソロモン符号を復号するように説明したが、これに限らず、例えば、ＢＣＨ符号を復号するようにしてもよい。
図２７は、本発明を適用した、リードソロモン符号を用いて誤り訂正を行う誤り訂正システムを適用した記録再生装置の構成例を示すブロック図である。図２７に示される記録再生装置は、例えば、ＤＶＤレコードプレーヤ等のディジタル記録媒体記録再生装置である。
図２７の記録再生装置２５０は、外部より供給されたディジタル情報を、符号化処理部２６０において符号化し、記録再生処理部２７０において記録媒体２７２に記録する。また、記録再生装置２５０は、記録媒体２７２に記録されているディジタル情報を、記録再生処理部２７０において再生し、復号処理部２８０において復号処理を行って元のディジタル情報を取得し、その情報を外部に出力する。
符号化処理部２６０は、ディジタル情報に互いに異なる次元に関するリードソロモン符号を行う第１リードソロモン符号化部２６１−１乃至第ｎリードソロモン符号化部２６１−ｎからなる。
符号化処理部２６０の外部より供給されたディジタル情報は、第１リードソロモン符号化部２６１−１において１次元目に関するリードソロモン符号化が行われる。続いて、ディジタル情報は、第２リードソロモン符号化部２６１−２乃至第ｎリードソロモン符号化部２６１−ｎの各部において、２次元目乃至ｎ次元目までの各次元目に関するリードソロモン符号が順に行われる。第ｎリードソロモン符号化部２６１−ｎによる符号化が終了すると、符号化処理部２６０は、符号化されたディジタル情報を記録再生処理部２７０に供給する。
記録再生処理部２７０は、符号化処理部２６０より供給された情報を記録媒体２７２に記録する記録部２７１、例えば光ディスク等の記録媒体２７２、記録媒体２７２に記録されている情報を再生する再生部２７３からなる。
記録再生処理部２７０の記録部２７１は、符号化処理部２６０より供給されたディジタル情報をＮＲＺＩ（Ｎｏｎ  Ｒｅｔｕｒｎ  ｔｏ  Ｚｅｒｏ  Ｉｎｖｅｒｔ）変換（ＮＲＺＩ符号化）するなどして記録媒体２７２に記録する。また、記録再生処理部２７０の再生部２７３は、記録媒体２７２に記録されているディジタル情報（リードソロモン符号化されたディジタル情報）を再生し、そのディジタル情報に施されたＮＲＺＩ変換を元に戻し（復号し）、そのディジタル情報を復号処理部２８０に供給する。
復号処理部２８０は、符号化処理部２６０に対応する復号器であり、ディジタル情報に互いに異なる次元に関して、サムプロダクトアルゴリズムによる復号処理を行う第１リードソロモンＳＰＡ復号部２８１−１乃至第ｎリードソロモンＳＰＡ復号部２８１−ｎからなる。
第１リードソロモンＳＰＡ復号部２８１−１乃至第ｎリードソロモンＳＰＡ復号部２８１−ｎは、それぞれ、符号化処理部２６０の第１リードソロモン符号化部２６１−１乃至第ｎリードソロモン符号化部２６１−ｎに対応し、各次元に関するリードソロモン符号に対して、サムプロダクトアルゴリズムによる復号を行う。第１リードソロモンＳＰＡ復号部２８１−１乃至第ｎリードソロモンＳＰＡ復号部２８１−ｎは、それぞれ、図２０に示される復号装置１５０と基本的に同様の構成であり、基本的に同様の動作を行う。従って、第１リードソロモンＳＰＡ復号部２８１−１乃至第ｎリードソロモンＳＰＡ復号部２８１−ｎは、それぞれ、復号装置１５０の場合と同様に、図２０のブロック図、および図２１に示されるフローチャートを適用することができる。
復号処理部２８０は、第１リードソロモンＳＰＡ復号部２８１−１乃至第ｎリードソロモンＳＰＡ復号部２８１−ｎの各部において、再生部２７３より供給されたディジタル情報に対して、パリティ検査行列の各要素、行列を展開し、そのパリティ検査行列を低密度化して、各次元目に関するサムプロダクトアルゴリズムによる復号処理を行う。その際、復号処理部２８０は、図２７に示されるように、符号化処理部２６０の場合と逆に、まず、第ｎリードソロモンＳＰＡ復号部２８１−ｎにおいて第ｎ次元目に関するサムプロダクトアルゴリズムによる復号処理から行い、続いて、直列に接続される各リードソロモンＳＰＡ復号部において、それぞれ、ｎ−１次元目、ｎ−２次元目と順に次元数を下げるようにサムプロダクトアルゴリズムによる復号処理を行い、最後に第１リードソロモンＳＰＡ復号部２８１−１において第１次元目に関するサムプロダクトアルゴリズムによる復号処理を行う。復号処理部２８０は、このようにして復元した元のディジタル情報を記録再生装置２５０の外部に出力する。
このようにすることにより、復号処理部２８０は、容易に性能の良い復号処理を行うことができ、記録再生装置２５０は、より正確にディジタル情報の記録および再生を行うことができる。また、復号処理部２８０は、パリティ検査行列を低密度化させる前に、パリティ検査行列の各要素、行列を展開するので、復号処理の演算コストを低く抑えることができる。
なお、以上においては、記録再生装置２５０は、リードソロモン符号を復号するように説明したが、これに限らず、例えば、ＢＣＨ符号を復号するようにしてもよい。
以上においては、ディジタル情報の記録および再生を行う記録再生装置の例について説明したが、この記録再生装置２５０の、ディジタル情報を記録媒体に記録する記録機能と、記録媒体に記録されているディジタル情報を再生する再生機能とが別体として構成されるようにしてもよい。
図２８は、図２７の記録再生装置２５０と同様の記録機能を有する記録装置の構成例を示すブロック図である。なお、図２７に示される場合と同様の部分については同一の符号を付しており、その説明を省略する。
図２８の記録装置３００は、第１リードソロモン符号化部２６１−１乃至第ｎリードソロモン符号化装置２６１−ｎからなる符号化処理部２６０、並びに、記録部２７１および記録媒体２７２からなる記録処理部３１０を有する。記録装置３００の符号化処理部２６０の外部より供給されたディジタル情報は、最初に、第１リードソロモン符号化部２６１−１において１次元目に関するリードソロモン符号化が行われる。続いて、その１次元目に関して符号化されたディジタル情報は、第２リードソロモン符号化部２６１−２乃至第ｎリードソロモン符号化部２６１−ｎの各部に順に供給され、各部において、２次元目乃至ｎ次元目までの各次元目に関するリードソロモン符号が行われる。第ｎリードソロモン符号化部２６１−ｎによる符号化が終了すると、符号化処理部２６０は、符号化されたディジタル情報を記録処理部３１０に供給する。
記録処理部３１０は、符号化処理部２６０より供給された情報を記録媒体２７２に記録する記録部２７１、および、例えば光ディスク等の記録媒体２７２を含む。記録処理部３１０の記録部２７１は、符号化処理部２６０より供給されたディジタル情報をＮＲＺＩ変換（ＮＲＺＩ符号化）するなどして記録媒体２７２に記録する。
すなわち、記録装置３００は、図２７の記録再生装置２５０と同様に、符号化処理部２６０においてディジタル情報をリードソロモン符号化し、記録処理部３１０の記録部２７１の制御により、そのリードソロモン符号化されたディジタル情報を記録媒体２７２に記録する。
このような記録装置３００に対応する再生装置を図２９に示す。なお、図２７に示される場合と同様の部分については同一の符号を付しており、その説明を省略する。
図２９の再生装置３５０は、図２８に示される記録装置３００に対応する再生装置であり、第１リードソロモンＳＰＡ復号部２８１−１乃至第ｎリードソロモン符号化装置２８１−ｎからなる復号処理部２８０、並びに、記録媒体２７２および再生部２７３からなる再生処理部３５０を有する。再生装置３５０の再生部２７３は、記録媒体２７２に記録されているディジタル情報（リードソロモン符号化されたディジタル情報）を再生し、そのディジタル情報に施されたＮＲＺＩ変換を元に戻し（復号し）、そのディジタル情報を復号処理部２８０に供給する。
復号処理部２８０は、第１リードソロモンＳＰＡ復号部２８１−１乃至第ｎリードソロモンＳＰＡ復号部２８１−ｎの各部において、再生部２７３より供給されたディジタル情報に対して、パリティ検査行列の各要素、行列を展開し、そのパリティ検査行列を低密度化して、各次元目に関するサムプロダクトアルゴリズムによる復号処理を行う。その際、復号処理部２８０は、図２９に示されるように、符号化処理部２６０の場合と逆に、まず、第ｎリードソロモンＳＰＡ復号部２８１−ｎにおいて第ｎ次元目に関するサムプロダクトアルゴリズムによる復号処理から行い、続いて、直列に接続される各リードソロモンＳＰＡ復号部において、それぞれ、ｎ−１次元目、ｎ−２次元目と順に次元数を下げるようにサムプロダクトアルゴリズムによる復号処理を行い、最後に第１リードソロモンＳＰＡ復号部２８１−１において第１次元目に関するサムプロダクトアルゴリズムによる復号処理を行う。復号処理部２８０は、このようにして復元した元のディジタル情報を再生装置３５０の外部に出力する。
このようにすることにより、復号処理部２８０は、容易に性能の良い復号処理を行うことができ、再生装置３５０は、より正確にディジタル情報の再生を行うことができる。また、復号処理部２８０は、パリティ検査行列を低密度化させる前に、パリティ検査行列の各要素、行列を展開するので、復号処理の演算コストを抑制することができる。
なお、以上においては、記録再生装置３００は、リードソロモン符号を復号するように説明したが、これに限らず、例えば、ＢＣＨ符号を復号するようにしてもよい。
図３０は、本発明を適用した、リードソロモン符号を用いて誤り訂正を行う誤り訂正システムを適用した記録再生装置の構成例を示すブロック図である。図３０に示される記録再生装置４００は、例えば、ＤＶＤレコードプレーヤ等のディジタル記録媒体記録再生装置である。なお、図２７に示される場合と同様の部分については同一の符号を付しており、その説明を省略する。
図３０の記録再生装置４００は、外部より供給されたディジタル情報を、符号化処理部２６０において符号化し、記録再生処理部２７０において記録媒体２７２に記録する。また、記録再生装置４００は、記録媒体２７２に記録されているディジタル情報を、記録再生処理部２７０において再生し、復号処理部４１０において復号処理を行って元のディジタル情報を取得し、その情報を外部に出力する。
復号処理部４１０は、符号化処理部２６０に対応する復号器であり、それぞれが、図２７に示される復号処理部２８０と同様の構成であり、同様の復号処理を行う、直列に接続されたｍ個の復号部である第１復号部４２０−１乃至第ｍ復号部４２０−ｍからなる。
第１復号部４２０−１は、図２７の復号処理部２８０と同様に、符号化処理部２６０の第１リードソロモン符号化部２６１−１乃至第ｎリードソロモン符号化部２６１−ｎに対応し、各次元に関するリードソロモン符号に対して、サムプロダクトアルゴリズムによる復号を行う、直列に接続されたｎ個の復号部である第１リードソロモンＳＰＡ復号部４２１−１−１乃至第ｎリードソロモンＳＰＡ復号部４２１−１−ｎにより構成される。この第１リードソロモンＳＰＡ復号部４２１−１−１乃至第ｎリードソロモンＳＰＡ復号部４２１−１−ｎは、それぞれ、図２０に示される復号装置１５０と基本的に同様の構成であり、基本的に同様の動作を行う。従って、これらの、第１リードソロモンＳＰＡ復号部４２１−１−１乃至第ｎリードソロモンＳＰＡ復号部４２１−１−ｎは、それぞれ、復号装置１５０の場合と同様に、図２０のブロック図、および図２１に示されるフローチャートを適用することができる。
第２復号部４２０−２乃至第ｍ復号部４２０−ｍも、それぞれ、第１復号部４２０−１と同様の構成であり、第１復号部４２０−１と同様の動作を行う。例えば、第２復号部４２０−２は、直列に接続されたｎ個の復号部である第１リードソロモンＳＰＡ復号部４２１−２−１乃至第ｎリードソロモンＳＰＡ復号部４２１−２−ｎにより構成され、第ｍ復号部４２０−ｍも直列に接続されたｎ個の復号部である第１リードソロモンＳＰＡ復号部４２１−ｍ−１乃至第ｎリードソロモンＳＰＡ復号部４２１−ｍ−ｎにより構成される。なお、これらの第２復号部４２０−２乃至第ｍ復号部４２０−ｍを構成する第１リードソロモンＳＰＡ復号部乃至第ｎリードソロモンＳＰＡ復号部は全て、それぞれ、図２０に示される復号装置１５０と基本的に同様の構成であり、基本的に同様の動作を行うので、それぞれ、復号装置１５０の場合と同様に、図２０のブロック図、および図２１に示されるフローチャートを適用することができる。
復号処理部４１０は、まず、再生部２７３より供給されたディジタル情報に対して、第１復号部４２０−１の第１リードソロモンＳＰＡ復号部４２１−１−１乃至第ｎリードソロモンＳＰＡ復号部４２１−１−ｎの各部において、パリティ検査行列の各要素、行列を展開し、そのパリティ検査行列を低密度化して、各次元目に関するサムプロダクトアルゴリズムによる復号処理を行う。
その際、第１復号部４２０−１は、符号化処理部２６０の場合と逆に、まず、第ｎリードソロモンＳＰＡ復号部４２１−１−ｎにおいて第ｎ次元目に関するサムプロダクトアルゴリズムによる復号処理から行い、続いて、直列に接続される各リードソロモンＳＰＡ復号部において、それぞれ、ｎ−１次元目、ｎ−２次元目と順に次元数を下げるようにサムプロダクトアルゴリズムによる復号処理を行い、最後に第１リードソロモンＳＰＡ復号部４２１−１−１において第１次元目に関するサムプロダクトアルゴリズムによる復号処理を行う。
復号処理が終了すると、第１復号部４２０−１は、復号されたディジタル情報を第２復号部４２０−２に供給する。第２復号部４２０−２は、第１の復号部４２０−１の場合と同様に、第１リードソロモンＳＰＡ復号部４２１−２−１乃至第ｎリードソロモンＳＰＡ復号部４２１−２−ｎを用いて、次元数を１つずつ下げるような順番でサムプロダクトアルゴリズムによる復号処理を行い、復号されたディジタル情報を次の復号部に供給する。このようにして、順に第ｍ復号部４２０−ｍまで復号処理が続けられる。第ｍ復号部４２０−ｍにおける復号処理が完了すると、復号処理部４１０は、復号されたディジタル情報を記録再生装置４００の外部に出力する。
このようにすることにより、復号処理部４１０は、容易に性能の良い復号処理を行うことができ、記録再生装置４００は、より正確にディジタル情報の記録および再生を行うことができる。また、復号処理部４１０は、パリティ検査行列を低密度化させる前に、パリティ検査行列の各要素、行列を展開するので、復号処理の演算コストを低く抑えることができる。
なお、以上においては、記録再生装置４００は、リードソロモン符号を復号するように説明したが、これに限らず、例えば、ＢＣＨ符号を復号するようにしてもよい。
なお、以上においては、ディジタル情報の記録および再生を行う記録再生装置の例について説明したが、この記録再生装置４００の、ディジタル情報を記録媒体に記録する記録機能と、記録媒体に記録されているディジタル情報を再生する再生機能とが別体として構成されるようにしてもよい。その場合、図３０の記録再生装置４００と同様の記録機能を有する記録装置は、図２８に示される記録装置３００と同様の構成であり、同様の動作を行うので、図２８のブロック図を適用することができ、その説明を省略する。
このような図３０の記録再生装置４００と同様の記録機能を有する記録装置である記録装置３００に対応する再生装置を図３１に示す。なお、図３０に示される場合と同様の部分については同一の符号を付しており、その説明を省略する。
図３１の再生装置４５０は、図２８に示される記録装置３００に対応する再生装置であり、第１復号部４２０−１乃至第ｍ復号部４２０−ｍからなる復号処理部４１０、並びに、記録媒体２７２および再生部２７３からなる再生処理部４６０を有する。再生装置４５０の再生部２７３は、記録媒体２７２に記録されているディジタル情報（リードソロモン符号化されたディジタル情報）を再生し、そのディジタル情報に施されたＮＲＺＩ変換を元に戻し（復号し）、そのディジタル情報を復号処理部４１０に供給する。
復号処理部４１０は、まず、再生部２７３より供給されたディジタル情報に対して、第１復号部４２０−１において、パリティ検査行列の各要素、行列を展開し、そのパリティ検査行列を低密度化して、サムプロダクトアルゴリズムによる復号処理を各次元に対して行う。続いて、復号処理部４１０は、ディジタル情報を、直列に接続される第２復号部４２０−２乃至４２０−ｍに、順に供給し、各部においてサムプロダクトアルゴリズムによる復号処理を行う。第ｍ復号部４２０−ｍにおける復号処理が完了すると、復号処理部４１０は、復号されたディジタル情報を記録再生装置４００の外部に出力する。
このようにすることにより、復号処理部４１０は、容易に性能の良い復号処理を行うことができ、再生装置４５０は、より正確にディジタル情報の再生を行うことができる。また、復号処理部４１０は、パリティ検査行列を低密度化させる前に、パリティ検査行列の各要素、行列を展開するので、復号処理の演算コストを抑制することができる。
なお、以上においては、ＢＣＨ符号またはリードソロモン符号に対する復号に本発明を適用する場合について説明したが、これに限らず、本発明は、一般の線形符号であればどのような符号に対応する復号に本発明を適用するようにしてもよい。
また、以上においては、再生装置４５０は、リードソロモン符号を復号するように説明したが、これに限らず、例えば、ＢＣＨ符号を復号するようにしてもよい。
さらに、以上においては、例えば、図１２に示される復号装置１００、図２０に示される復号装置１５０、図２５に示されるリードソロモンＳＰＡ復号部２３４、図２６に示されるリードソロモンＳＰＡ復号部２４４、図２７に示される第１リードソロモンＳＰＡ復号部２８１−１乃至第ｎリードソロモン復号部２８１−ｎ、並びに、図３０に示される第１復号部４２０−１乃至第ｍ復号部４２０−ｍのような、本発明を適用した復号装置または復号部は、一般の線形符号に対する復号方法として、検査行列を低密度化し、その低密度化した検査行列を用いて、線形符号を復号するように説明したが、これに限らず、例えば、他の装置または他の処理部において、検査行列を予め低密度化しておくようにしてもよい。その場合、復号装置（または復号部）は、その予め低密度化された検査行列を用いて、符号化装置等より供給される線形符号の復号を行う。すなわち、例えば、図２５に示される復号装置２３０、図２６に示される復号装置２４０、図２７に示される記録再生装置２５０、図２９に示される再生装置３５０、図３０に示される記録再生装置４００、または、図３１に示される再生装置４５０の外部において検査行列が予め低密度化されるようにし、各装置が、その予め低密度化された検査行列を用いて、供給される線形符号の復号を行うようにしてもよい。
上述した一連の処理は、ハードウエアにより実行させることもできるし、ソフトウエアにより実行させることもできる。ソフトウエアにより実行される場合、上述した画像処理装置は、図３２に示されるようなパーソナルコンピュータにより構成される。
図３２において、パーソナルコンピュータ５００のＣＰＵ（Ｃｅｎｔｒａｌ  Ｐｒｏｃｅｓｓｉｎｇ  Ｕｎｉｔ）５０１は、ＲＯＭ（Ｒｅａｄ  Ｏｎｌｙ  Ｍｅｍｏｒｙ）５０２に記憶されているプログラム、または記憶部５１３からＲＡＭ（Ｒａｎｄｏｍ  Ａｃｃｅｓｓ  Ｍｅｍｏｒｙ）５０３にロードされたプログラムに従って各種の処理を実行する。ＲＡＭ５０３にはまた、ＣＰＵ５０１が各種の処理を実行する上において必要なデータなども適宜記憶される。
ＣＰＵ５０１、ＲＯＭ５０２、およびＲＡＭ５０３は、バス５０４を介して相互に接続されている。このバス５０４にはまた、入出力インタフェース５１０も接続されている。
入出力インタフェース５１０には、キーボード、マウスなどよりなる入力部５１１、ＣＲＴ（Ｃａｔｈｏｄｅ  Ｒａｙ  Ｔｕｂｅ）、ＬＣＤ（Ｌｉｑｕｉｄ  Ｃｒｙｓｔａｌ  ｄｉｓｐｌａｙ）などよりなるディスプレイ、並びにスピーカなどよりなる出力部５１２、ハードディスクなどより構成される記憶部５１３、モデムなどより構成される通信部５１４が接続されている。通信部５１４は、インターネットを含むネットワークを介しての通信処理を行う。
入出力インタフェース５１０にはまた、必要に応じてドライブ５１５が接続され、磁気ディスク、光ディスク、光磁気ディスク、或いは半導体メモリなどのリムーバブルメディア９２１が適宜装着され、それらから読み出されたコンピュータプログラムが、必要に応じて記憶部５１３にインストールされる。
一連の処理をソフトウエアにより実行させる場合には、そのソフトウエアを構成するプログラムが、ネットワークや記録媒体からインストールされる。
この記録媒体は、図３２に示されるように、装置本体とは別に、ユーザにプログラムを提供するために配布される、プログラムが記録されている磁気ディスク（フロッピディスクを含む）、光ディスク（ＣＤ−ＲＯＭ（Ｃｏｍｐａｃｔ  Ｄｉｓｋ−Ｒｅａｄ  Ｏｎｌｙ  Ｍｅｍｏｒｙ），ＤＶＤ（Ｄｉｇｉｔａｌ  Ｖｅｒｓａｔｉｌｅ  Ｄｉｓｋ）を含む）、光磁気ディスク（ＭＤ（Ｍｉｎｉ−Ｄｉｓｋ）を含む）、もしくは半導体メモリなどよりなるリムーバブルメディア５２１により構成されるだけでなく、装置本体に予め組み込まれた状態でユーザに提供される、プログラムが記録されているＲＯＭ５０２や、記憶部５１３に含まれるハードディスクなどで構成される。
なお、本明細書において、記録媒体に記録されるプログラムを記述するステップは、記載された順序に沿って時系列的に行われる処理はもちろん、必ずしも時系列的に処理されなくとも、並列的あるいは個別に実行される処理をも含むものである。
また、本明細書において、システムとは、複数の装置により構成される装置全体を表すものである。
【産業上の利用可能性】  以上のごとく本発明によれば、一般の線形符号の復号処理を行うことができる。特に、一般の線形符号に対する復号方法としてサムプロダクトアルゴリズムを適用した場合に、容易に、性能の良い復号処理を行うことができる。
【図１】
2004107585.tif 000010
【図２】
2004107585.tif 000011
【図３】
2004107585.tif 000012
【図４】
2004107585.tif 000013
【図５】
2004107585.tif 000014
【図６】
2004107585.tif 000015
【図７】
2004107585.tif 000016
【図８】
2004107585.tif 000017
【図９】
2004107585.tif 000018
【図１０】
2004107585.tif 000019
【図１１】
2004107585.tif 000020
【図１２】
2004107585.tif 000021
【図１３】
2004107585.tif 000022
【図１４】
2004107585.tif 000023
【図１５】
2004107585.tif 000024
【図１６】
2004107585.tif 000025
【図１７】
2004107585.tif 000026
【図１８】
2004107585.tif 000027
【図１９】
2004107585.tif 000028
【図２０】
2004107585.tif 000029
【図２１】
2004107585.tif 000030
【図２２】
2004107585.tif 000031
【図２３】
2004107585.tif 000032
【図２４】
2004107585.tif 000033
【図２５】
2004107585.tif 000034
【図２６】
2004107585.tif 000035
【図２７】
2004107585.tif 000036
【図２８】
2004107585.tif 000037
【図２９】
2004107585.tif 000038
【図３０】
2004107585.tif 000039
【図３１】
2004107585.tif 000040
【図３２】
2004107585.tif 000041
【国際調査報告】
2004107585.tif 000042
2004107585.tif 000043
2004107585.tif 000044