(57)【要約】【課題】  低密度パリティチェック行列の生成装置及びその方法を提供する。【解決手段】  パリティチェック行列のそれぞれの列ごとに、要素が１である行のインデックスを表す要素１行インデックスを生成する一つ以上のインデックス生成部を備え、インデックス生成部は、一つのクロックごとに、一つの要素１行インデックスを生成するモジュラーシフトレジスタ生成器を利用して具現されることを特徴とするパリティチェック行列の生成装置である。これにより、パリティチェック行列がメモリに保存されないため、エンコーダ及びデコーダに必要なメモリの容量を減少させうる。【選択図】      図４
2006050622.tif 000002
【特許請求の範囲】
【請求項１】
低密度パリティチェック行列の生成装置において、
前記パリティチェック行列のそれぞれの列ごとに、要素が１である行のインデックスを表す要素１行インデックスを生成する一つ以上のインデックス生成部を備え、
前記インデックス生成部は、一つのクロックごとに前記一つの要素１行インデックスを生成するモジュラーシフトレジスタ生成器を利用して具現されることを特徴とする装置。
【請求項２】
前記インデックス生成部は、
ａ）ｓビットの初期値を入力され、一つのクロックが進む度に保存値が次のレジスタにシフトされる、順に並べられたｓ個のレジスタと、
ｂ）前記ｓ個のレジスタのうち、最後のレジスタの値を前記選択的にフィードバックさせるフィードバックラインと、
ｃ）前記フィードバックされたレジスタの値をそれぞれのレジスタの値と合算した後、その次のレジスタに提供する合算器とを備えることを特徴とする請求項１に記載の装置。
【請求項３】
前記行インデックスは、それぞれのクロックごとに前記ｓ個のレジスタのうち、任意に選択されたｔ個のレジスタから出力される出力ベクトルであり、前記ｔビット出力ベクトルを生成し、ここで、前記ｓ及びｔは、パリティチェック行列の行の数ｍ、及び列の数ｎと次の数式
【数１】
2006050622.tif 000007
の関係を有することを特徴とする請求項１に記載の装置。
【請求項４】
前記フィードバックラインは、それぞれの合算器に連結されたスイッチを備え、前記スイッチの係数は、前記ｓ個のレジスタの出力ベクトルが２Ｓ−１クロックの間に何れも異なる値が出力されるように選択されることを特徴とする請求項２に記載の装置。
【請求項５】
前記スイッチの係数は、原形多項式の係数から選択され、前記原形多項式は、前記原形多項式に割れる多項式ｘｖ−１の可能な最小の正の数ｖが、次の数式
【数２】
2006050622.tif 000008
を満足する多項式であり、ここで前記原形多項式は、係数が０ないしｐ−１のうち、任意の数であり（すなわち、ｐ（ｘ）ＩＮ  ＧＦ（ｐ）［ｘ］である）次数がｕである非減少多項式であり、ｐは、任意の素数であることを特徴とする請求項２に記載の装置。
【請求項６】
低密度パリティチェック行列の生成方法において、
前記パリティチェック行列のそれぞれの列ごとに、要素が１である行のインデックスを表す要素１行インデックスを生成する一つ以上のインデックス生成ステップを含み、
前記インデックス生成ステップは、一つのクロックごとに前記一つの要素１行インデックスを生成するモジュラーシフトレジスタ生成器を利用して具現されることを特徴とする方法。
【請求項７】
前記インデックス生成ステップは、
ａ）ｓビットの初期値を入力されてレジスタに保存するステップと、
ｂ）前記初期値のそれぞれのビットのうち、最下位ビットを選択的にフィードバックするステップと、
ｃ）前記フィードバックした値を前記初期値のそれぞれのビットと合算するステップと、
ｄ）前記合算されたｓ個のビット値のうち、任意に選択されたｔビットの出力ベクトルを次のレジスタに保存し、前記保存値を前記要素１行インデックスとして出力するステップとを含む請求項６に記載の方法。
【請求項８】
前記要素１行インデックスは、それぞれのクロックごとに前記ｓ個のレジスタのうち、任意に選択されたｔ個のレジスタから出力される出力ベクトルであり、前記ｔビット出力ベクトルを生成し、ここで前記ｓ及びｔは、パリティチェック行列の行の数ｍ及び列の数ｎと、次の数式
【数３】
2006050622.tif 000009
の関係を有することを特徴とする請求項６に記載の方法。
【請求項９】
前記ｂ）ステップにおいて、前記それぞれのレジスタでフィードバックするか否かは、前記モジュラーシフトレジスタの特性多項式の係数で表現され、前記係数は、前記出力ベクトルが２ｓ−１クロックの間に何れも異なる値が出力されるように選択されることを特徴とする請求項７に記載の方法。
【請求項１０】
前記係数は、原形多項式の係数から選択され、前記原形多項式は、前記原形多項式に割れる多項式ｘｖ−１の可能な最小の正の数ｖが、次の数式
【数４】
2006050622.tif 000010
を満足する多項式であり、ここで前記原形多項式は、係数が０ないしｐ−１のうち、任意の数であり（すなわち、ｐ（ｘ）  ＩＮ  ＧＦ（ｐ）［ｘ］である）、次数が、ｕである非減少多項式であり、ｐは、任意の素数であることを特徴とする請求項９に記載の方法。
【請求項１１】
パリティチェック行列の生成装置において、
前記パリティチェック行列の要素１の位置は、モジュラーシフトレジスタ生成器により生成されることを特徴とする装置。
【請求項１２】
前記モジュラーシフトレジスタ生成器のフィードバックラインの構造を特定する特定多項式は、原形多項式であることを特徴とする請求項１１に記載の装置。
【請求項１３】
前記モジュラーシフトレジスタ生成器の初期値は、前記パリティチェック行列の要素１の位置がそれぞれのクロックごとに同じ列で同じ値が出力されないように選択されることを特徴とする請求項１１に記載の装置。
【請求項１４】
コンピュータで実行させるためのプログラムを記録したコンピュータで読み取り可能な記録媒体において、前記プログラムは、
コンピュータシステムによって実行される時、一つのクロックごとにパリティチェック行列のそれぞれの列ごとに、要素が１である位置を表す一つ以上の要素１のインデックスを生成するモジュラーシフトレジスタ生成器として作動するコンピュータで読み取り可能な記録媒体。
【請求項１５】
前記インデックスは、
ａ）ｓビットの初期値を入力されてレジスタに保存するステップと、
ｂ）前記初期値の最下位ビットを選択的にフィードバックするステップと、
ｃ）前記フィードバックした値を前記初期値のそれぞれのビットと合算するステップと、
ｄ）前記合算されたｓ個のビット値のうち、選択されたｔビットのそれぞれの出力ベクトルを保存して、前記ｔビットの出力ベクトルを前記要素１行インデックスとして出力するステップによって生成される請求項１４に記載のコンピュータで読み取り可能な記録媒体。
【請求項１６】
低密度パリティチェックコーディング方法で利用するために、Ｍ行及びＮ列のメッセージ情報及びパリティ情報の低密度パリティチェックマトリックスを形成する装置において、
第１初期値を受信するように結合され、異なるクロックで第１列ないし第Ｎ列のパリティチェックマトリックスのそれぞれの列に対して選定されたビットで、第１要素“１”の行インデックスを生成するための第１インデックス生成部と、
第２初期値を受信するように結合され、異なるクロックで第１列ないし第Ｎ列のパリティチェックマトリックスのそれぞれの列に対して選定されたビットで、第２要素“１”の行インデックスを生成するための第２インデックス生成部と、
第Ｎ初期値を受信するように結合され、異なるクロックで第１列ないし第Ｎ列のパリティチェックマトリックスのそれぞれの列に対して選定されたビットで、第Ｎ要素“１”の行インデックスを生成するための第Ｎインデックス生成部とを備えることを特徴とする装置。
【請求項１７】
前記第１インデックス生成部、前記第２インデックス生成部及び前記第Ｎインデックス生成部は、モジュラーシフトレジスタ生成器を利用して具現され、
‘ｓ’ビットの初期値を受信し、前記初期値をビット単位で保存し、一つのクロックごとに対応する保存されたビット値を次のレジスタにシフトするために順に並べられた“ｓ”個のレジスタと、
順に並べられる最終レジスタに保存されるビット値が選択的にフィードバックされるフィードバックラインと、
あらゆる２個のレジスタの間にそれぞれ配置されて、前記フィードバックされたビット値と、以前レジスタの前記保存されたビット値とを前記フィードバックラインを通じて合算し、次のレジスタに合算された値を提供するｓ−１個の合算器と、
それぞれの合算器への前記フィードバックライン上にそれぞれ配置され、前記フィードバックラインを通じて、前記それぞれの合算器へ前記フィードバックされたビット値の伝送を制御するｓ−１個のスイッチとを含み、
“ｓ”個のレジスタのうち選択された“ｔ”個のレジスタの出力は、前記パリティチェックマトリックスの要素“１”の行インデックスに対応することを特徴とする請求項１６に記載の装置。
【請求項１８】
それぞれのｔビットの行ベクトルが、前記ｓ個のレジスタのうち選択されたｔ個のレジスタから出力される出力ベクトルであり、ここで、前記ｓ及びｔは、パリティチェック行列の行の数ｍ及び列の数ｎと、次の数式
【数５】
2006050622.tif 000011
の関係を有することを特徴とする請求項１７に記載の装置。
【請求項１９】
前記フィードバックラインに配置されるそれぞれのスイッチには、２Ｓ−１クロックの間に前記レジスタから出力されたあらゆるベクトルが相異なるように選択される係数が提供されることを特徴とする請求項１７に記載の装置。
【請求項２０】
前記対応するスイッチの前記係数は、原形多項式ｐ（ｘ）の係数のうち選択され、前記原形多項式は、前記原形多項式に割れる多項式ｘｖ−１の可能な最小の正の数ｖが次の数式
ｖ＝ｐｕ−１        （６）
を満足する多項式であり、ここで前記原形多項式は、係数が０ないしｐ−１のうち任意の数であり（すなわち、ｐ（ｘ）  ＩＮ  ＧＦ（ｐ）［ｘ］である）、次数がｕである非減少多項式であり、ｐは、任意の素数であることを特徴とする請求項１９に記載の装置。
【請求項２１】
前記第１インデックス生成部は、
それぞれが初期値を受信し、前記初期値をビット単位で保存し、一つのクロックごとに対応する保存されたビット値を次のレジスタにシフトする順に並べられた第１レジスタないし第６レジスタと、
順に並べられた前記第６レジスタに保存されたビット値が選択的にフィードバックされるフィードバックラインと、
前記第５レジスタと前記第６レジスタとの間に配置され、前記第５レジスタの前記保存されたビット値を、前記フィードバックラインを通じて前記フィードバックされたビット値と合算し、合算された値を前記第６レジスタに提供する合算器とを備え、
前記第１レジスタないし第５レジスタの出力は、前記パリティチェックマトリックスの要素１の行インデックスに対応することを特徴とする請求項１６に記載の装置。
【請求項２２】
前記第１インデックス生成部は、
それぞれが初期値を受信し、前記初期値をビット単位で保存し、一つのクロックごとに対応する保存されたビット値を次のレジスタにシフトする、順に並べられた第１レジスタないし第６レジスタと、
順に並べられた前記第６レジスタに保存されたビット値が選択的にフィードバックされるフィードバックラインと、
前記第５レジスタと前記第６レジスタとの間に配置され、前記第５レジスタの前記保存されたビット値を、前記フィードバックラインを通じて前記フィードバックされたビット値と合算し、合算された値を前記第６レジスタに提供する第１合算器と、
前記第４レジスタと前記第５レジスタとの間に配置され、前記第４レジスタの前記保存されたビット値を、前記フィードバックラインを通じて前記フィードバックされたビット値と合算し、合算された値を前記第５レジスタに提供する第２合算器と、
前記第１レジスタと前記第２レジスタとの間に配置され、前記第１レジスタの前記保存されたビット値を、前記フィードバックラインを通じて前記フィードバックされたビット値と合算し、合算された値を前記第２レジスタに提供する第３合算器とを備え、
前記第１レジスタないし第５レジスタの出力は、前記パリティチェックマトリックスの要素１の行インデックスに対応することを特徴とする請求項１６に記載の装置
【請求項２３】
低密度パリティチェックコーディング方法で利用するために、Ｍ行及びＮ列のメッセージ情報及びパリティ情報のＬＤＰＣマトリックスを形成する方法において、
順に接続された“ｓ”個のレジスタ、及びあらゆる２個のレジスタの間にそれぞれ配置される“ｓ−１”個の合算器を備えるモジュラーシフトレジスタ生成器を獲得するステップと、
順に並べられた“ｓ”個のレジスタで“ｓ”ビットの初期値を保存し、一つのクロックごとに対応する保存されたビット値を次のレジスタにシフトするステップと、
フィードバックラインを通じて、最終レジスタに保存されたビット値を選択的にフィードバックするステップと、
あらゆる２個のレジスタの間にそれぞれ配置される前記“ｓ−１”個の合算器で、以前レジスタの前記保存されたビット値を、前記フィードバックラインを通じて前記フィードバックされたビット値と合算し、合算された値を次のレジスタに提供するステップと、
“ｓ”個のレジスタのうち選択された“ｔ”個のレジスタから、前記パリティチェックマトリックスの要素“１”の行インデックスを出力するステップとを含むことを特徴とする方法。
【請求項２４】
それぞれのｔビットの行ベクトルが、前記ｓ個のレジスタのうち選択されたｔ個のレジスタから出力される出力ベクトルであり、ここで前記ｓ及びｔは、パリティチェック行列の行の数ｍ及び列の数ｎと、次の数式
【数６】
2006050622.tif 000012
の関係を有することを特徴とする請求項２３に記載の方法。
【請求項２５】
前記フィードバックラインには、２Ｓ−１クロックの間に前記レジスタから出力されたあらゆるベクトルが相異なるように選択される係数を有するスイッチが提供されることを特徴とする請求項２４に記載の方法。
【請求項２６】
前記対応するスイッチの前記係数は、原形多項式ｐ（ｘ）の係数のうち選択され、前記原形多項式は、前記原形多項式に割れる多項式ｘｖ−１の可能な最小の正の数ｖが、次の数式
ｖ＝ｐｕ−１        ・・・（８）
を満足する多項式であり、ここで前記原形多項式は、係数が０ないしｐ−１のうち任意の数であり（すなわち、ｐ（ｘ）  ＩＮ  ＧＦ（ｐ）［ｘ］である）、次数がｕである非減少多項式であり、ｐは、任意の素数であることを特徴とする請求項２５に記載の方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、パリティチェック行列の生成装置及びその方法に係り、より詳細には、エンコーダ及びデコーダ内のメモリ容量を低密度パリティチェック（以下、ＬＤＰＣ）コーディング方法で非常に減少させうるパリティチェック行列方法及びその装置に関する。
【背景技術】
【０００２】
最近、多様な方法のコーディング方法が通信及び保存システムに提案されている。一般的に、ＬＤＰＣコードという一群のコードは、良好なエラー検出及び訂正性能を有していると説明されている。さらに、このようなＬＤＰＣコードは、非常に高速でデコーディングされうる。しかし、このようなＬＤＰＣコードは、ＬＤＰＣマトリックスの無作為的な選択により構成され、大容量のメモリを有する複雑なエンコーダ及びデコーダを必要とする。
【０００３】
例えば、図１は、ＬＤＰＣコーディング及びデコーディング方法の概念を示す図である。図１に示されたように、ＬＤＰＣコーディングとは、‘０’と‘１’から構成され、‘１’の数が‘０’の数より非常に少ないＬＤＰＣ行列Ｈを利用してパリティ情報を生成する方法である。
【０００４】
パリティチェック行列Ｈで、各行または列に含まれた１の個数は、それぞれ行次数及び列次数という。一般的に、あらゆる行の行次数が同じであり、あらゆる列の列次数が同じであるパリティチェック行列を規則的パリティチェック行列と言い、そうでない場合を、不規則的パリティチェック行列という。規則的パリティチェック行列において行次数は、行ウェイト（ｒｏｗ  ｗｅｉｇｈｔ：Ｗｒ）と言い、列次数は、列ウェイト（ｃｏｌｕｍｎ  ｗｉｇｈｔ：Ｗｃ）という。
【０００５】
ＬＤＰＣコーディング方法を利用したパリティ情報の生成は、次の式（９）により行われる。
【０００６】
ＨＸ＝０        ・・・（９）
ここでＨは、ｍ＊ｎのパリティチェック行列であり、Ｘは、ｎ＊１のコードワード行列である。Ｘは、ｍ個のメッセージ情報とｐ個のパリティ情報とから構成される。したがって、ｍ＋ｐ＝ｎである。
【０００７】
このようなＬＤＰＣコーディングの基本概念は、非特許文献１に開示されており、この文献によれば、パリティ情報は、ガウス消去法等の行列演算を利用して、式（９）を解くことによって生成されうる。
【０００８】
また、ＬＤＰＣデコーディングは、前記数式に基づいてパリティ検算を行う過程を含む。
【０００９】
既存のＬＤＰＣコードのパリティチェック行列を構成する方法は、大きく２つに分けられる。第一の方法は、パリティチェック行列Ｈのそれぞれの列に対して、要素１行インデックスをユーザーにより定められた任意の規則によって選択する方法である。例えば、第１列には、１、３、５の行インデックスを、第２列には、２、４、６の行インデックスを、第３列には、７、９、１１の行インデックスを、・・・、要素１要素で選択する方法である。この方法は、具現が容易であるが、ＢＥＲ（Ｂｉｔ  Ｅｒｒｏｒ  Ｒａｔｅ）性能が低下する。第二の方法は、パリティチェック行列Ｈのそれぞれの列に対して、要素１行インデックスをランダムに選択する方法である。この方法は、１の位置がランダムであるため具現が複雑であるが、ＢＥＲ性能に優れている。
【００１０】
第二の方法でパリティチェック行列を生成する方法の一例は、次の通りである。まず、第１列で、任意のｗｃ個の要素１行インデックスを選択する。その後、第２列で、既に生成された第１列の要素１行インデックスと二つ以上は重ならないように、任意の要素１行インデックスを選択する。その後、第３列で、既に生成された第１列及び第２列のうち、何れか一つの要素１行インデックスと二つ以上は重ならないように、任意の要素１行インデックスを選択する。最後に、前記過程を最後の列まで繰り返す。
【００１１】
すなわち、従来のパリティチェック行列の生成方法は、パリティチェック行列Ｈ内のあらゆる任意の二つの列の要素１行インデックスのうち、二つ以上は重ならないように任意の要素１行インデックスを選択する。
【００１２】
このような従来のパリティチェック行列の生成方法によれば、既に選択された要素１行インデックスは、パリティチェック行列を生成する装置のメモリ内に保存されねばならない。また、エンコーディングまたはデコーディングを行うためには、あらゆる要素１行インデックスがエンコーダまたはデコーダ内のメモリに保存されておらねばならない。
【００１３】
図２は、メモリ内にパリティチェック行列が保存されたメモリ構造を示す図である。図２に示されたように、メモリは、ＲＯＭ２０でありうる。パリティチェック行列は、それぞれの列に含まれた要素“１”の位置を示す要素１行インデックス、またはそれぞれの行に含まれた要素“１”の位置を表す要素１列インデックスにより特定されうる。図２は、要素１行インデックスを利用してパリティチェック行列Ｈを特定し、コーディング及びデコーディングのために、パリティチェック行列Ｈが保存されたメモリ構造を示す図である。
【００１４】
また、図２に示されたように、メモリ２０内の一つのアドレスに一つの要素１行インデックスが保存される。結局、一つのパリティチェック行列が占めるメモリは、ｎ＊Ｗｃ＊Ｂである。ここで、Ｂは、要素１行インデックスが占めるビット数であり、２Ｂ＝ｍであり、ここで、ｍは、パリティチェック行列の行の数である。
【００１５】
満足すべきＢＥＲ誤り性能を有するパリティチェック行列の一例として、ｍ＊ｎ＝（５１２）＊（５１２＊１７）である時、この場合に必要なメモリ容量は、５１２（＝２９）＊５１２＊７＊９ｂｉｔになり、より優れたＢＥＲのエラー性能を満足させるには、メモリ容量は更に増加する。このようなメモリ容量の増加は、エンコーダ及びデコーダの生産コストの増加などの数々の問題点を起す。
【特許文献１】日本特許公開２００３−１１５７６８号公報
【特許文献２】日本特許公開２００３−１９８３８３号公報
【非特許文献１】Ｄ.Ｊ.  ＭａｃＫａｙ，“Ｇｏｏｄ  ｅｒｒｏｒ−ｃｏｒｒｅｃｔｉｏｎ  ｃｏｄｅｓ  ｂａｓｅｄ  ｏｎ  ｖｅｒｙ  ｓｐａｒｓｅ  ｍａｔｒｉｃｅｓ，”ＩＥＥＥ  Ｔｒａｎｓ．ｏｎ  Ｉｎｆｏｒｍａｔｉｏｎ  Ｔｈｅｏｒｙ，ｖｏｌ.４５，ｎｏ.２，ｐｐ.３９９〜４３１，１９９９
【発明の開示】
【発明が解決しようとする課題】
【００１６】
本発明は、前記課題を解決するためになされたものであって、シフトレジスタを利用することによってＬＤＰＣコーディング及びデコーディングのために要求されるメモリの容量を減少させたパリティチェック行列の生成方法を提供することを目的とする。
【課題を解決するための手段】
【００１７】
前記課題を解決するために、本発明は、ＬＤＰＣ行列の生成装置において、前記パリティチェック行列のそれぞれの列ごとに、要素が１である行のインデックスを表す要素１行インデックスを生成する一つ以上のインデックス生成部を備え、前記インデックス生成部は、一つのクロックごとに前記一つの要素１行インデックスを生成するモジュラーシフトレジスタ生成器（ＭＳＲＧ）を利用して具現されることを特徴とする。
【００１８】
ここで、前記インデックス生成部は、ａ）ｓビットの初期値を入力され、一つのクロックが進む度に保存値が次のレジスタにシフトされる、順に並べられたｓ個のレジスタと、ｂ）前記ｓ個のレジスタのうち、最後のレジスタの値を前記選択的にフィードバックさせるフィードバックラインと、ｃ）前記フィードバックされたレジスタの値とそれぞれのレジスタの値と合算した後、その次のレジスタに提供する合算器とを備える。
【００１９】
また、ここで、前記行インデックスは、それぞれのクロックごとに前記ｓ個のレジスタのうち、任意に選択されたｔ個のレジスタから出力される出力ベクトルであり、前記ｔビット出力ベクトルを生成し、ここで、前記ｓ及びｔは、パリティチェック行列の行の数ｍ及び列の数ｎと、次の数式
【００２０】
【数７】
2006050622.tif 000003
の関係を有する。
【００２１】
また、本発明は、ＬＤＰＣ行列の生成方法において、前記パリティチェック行列のそれぞれの列ごとに、要素が１である行のインデックスを表す要素１行インデックスを生成する一つ以上のインデックス生成ステップを含み、前記インデックス生成ステップは、一つのクロックごとに前記一つの要素１行インデックスを生成するＭＳＲＧを利用して具現される。
【００２２】
また、本発明は、パリティチェック行列の生成装置において、前記パリティチェック行列の要素１の位置は、ＭＳＲＧにより生成される。
【００２３】
ここで、前記ＭＳＲＧのフィードバックラインの構造を特定する特定多項式は、原形多項式であることを特徴とする。
【発明の効果】
【００２４】
本発明によれば、パリティチェック行列がメモリに保存されずに、レジスタを利用してそれぞれのクロックごとに生成されることによって、エンコーダ及びデコーダに必要なメモリの容量が減少する。
【発明を実施するための最良の形態】
【００２５】
以下、添付された図面を参照して本発明に係る好ましい一実施形態を詳細に説明する。
【００２６】
図３は、本発明の一実施形態に係るパリティチェック行列の生成装置を示す図である。
【００２７】
本発明に係るパリティチェック行列の生成装置３００は、第１インデックス生成部３１０、第２インデックス生成部３２０、・・・第Ｗｃインデックス生成部３３０を備える。ここで、Ｗｃは、列ウェイトである。
【００２８】
第１インデックス生成部３１０は、ｓビットの第１初期値３１２を受信して、ｔビットのそれぞれの列の第１要素１行インデックス３１４を生成する。すなわち、第１インデックス生成部３１０は、第１クロックで、パリティチェック行列の第１列の第１要素１の行インデックス（ｔビット）を出力し、第２クロックで、パリティチェック行列の第２列の第１要素１の行インデックスを生成し、・・・・・・、第ｎクロックで、パリティチェック行列の第ｎ列の第１要素１の行インデックスを生成する。
【００２９】
第２インデックス生成部３２０ないし第Ｗｃインデックス生成部３３０の動作も、第１インデックス生成部３１０と類似している。例えば、第２インデックス生成部３２０は、ｓビットの第２初期値３２２を受信して、ｔビットのそれぞれの列の第２要素１行インデックス３２４を生成する。すなわち、第２インデックス生成部３２０は、第１クロックで、パリティチェック行列の第１列の第２要素１の行インデックスを出力し、第２クロックで、パリティチェック行列の第２列の第２要素１の行インデックスを生成し、・・・・・・、第ｎクロックで、パリティチェック行列の第ｎ列の第２要素１の行インデックスを生成する。
【００３０】
また、第Ｗｃインデックス生成部３３０は、ｓビットの第Ｗｃ初期値３３２を受信して、ｔビットのそれぞれの列の第Ｗｃ要素１の行インデックス３３４を生成する。すなわち、第Ｗｃインデックス生成部３３０は、第１クロックで、パリティチェック行列の第１列の第Ｗｃ要素１の行インデックスを出力し、第２クロックで、パリティチェック行列の第２列の第Ｗｃ要素１の行インデックスを生成し、・・・・・・、第ｎクロックで、パリティチェック行列の第ｎ列の第Ｗｃ要素１の行インデックスを生成する。
【００３１】
結局、第１クロックで、第１列に含まれた要素１の位置であるＷｃ個の行インデックスが出力され、第２クロックで、第２列に含まれた要素１の位置であるＷｃ個の行インデックスが出力され、・・・、第ｎクロックで、第ｎ列に含まれた要素１の位置であるＷｃ個の行インデックスが出力される。
【００３２】
図３のパリティチェック行列の生成装置３００は、図２のパリティチェック行列Ｈが保存されたメモリの代わりに、エンコーダまたはデコーダ内で式（９）の演算のためのパリティチェック行列Ｈを提供する。
【００３３】
第１初期値３１２、第２初期値３２２、・・・、第Ｗｃ初期値３３２は、それぞれ第１インデックス生成部３１０、第２インデックス生成部３２０、及び第Ｗｃインデックス生成部に入力されて、ユーザーにより選択される。但し、初期値は、第１行インデックス３１４ないし第Ｗｃ行インデックス３３４が、同じクロックで同じ値が出力されないように選択されなければならない。
【００３４】
図４は、図３のそれぞれのインデックス生成部の内部構造を示す図である。
【００３５】
本発明で、インデックス生成部は、図４に示されたようなＭＳＲＧを利用する。
【００３６】
図３の第１インデックス生成部３１０ないし第Ｗｃインデックス生成部３３０は、係数Ｃ１、Ｃ２、・・・、Ｃｓ−１及び初期値３１２ないし３３２が異なるという点を除いては、内部構造が何れも同じである。同じ内部構造を有するため、以下では第１ないし第Ｗｃインデックス生成部３１０ないし３３０を統一してインデックス生成部４００と、第１初期値ないし第Ｗｃ初期値３１２ないし３３２は、初期値４１０と、第１行インデックスないし第Ｗｃ行インデックス３１４ないし３３４は、行インデックス４２０と称する。
【００３７】
インデックス生成部４００は、ｓ個のレジスタＲ１、Ｒ２、・・・、Ｒｓ、ｓ−１個のスイッチ４３１、４３２、・・・、及びｓ−１個の合算器４０１、４０２、・・・を備える。図４のレジスタ、合算器及びスイッチの組合わせは、ＭＳＲＧと称される。
【００３８】
第１クロックで、初期値４１０は、レジスタＲ１、Ｒ２、・・・Ｒｓに入力される。行インデックス４２０は、それぞれのクロックでレジスタＲ１、Ｒ２、・・・Ｒｔに保存された値である。第１クロックでは、レジスタＲ１、Ｒ２、・・・、Ｒｔに保存された初期値４１０がそのままに出力される。行インデックス４２０を出力するレジスタＲ１、Ｒ２、・・・Ｒｔは、レジスタＲ１、Ｒ２、・・・Ｒｓのうち任意に選択される。
【００３９】
レジスタＲ１、Ｒ２、・・・Ｒｔの出力値は、パリティチェック行列Ｈの要素１行インデックスである。例えば、ｔ＝３、ｓ＝４であり、初期値４１０が１１０１であり、行インデックス４２０を出力するレジスタがＲ１、Ｒ２、Ｒ３に選択されれば、第１クロックで、インデックス生成部４００が出力する行インデックス４２０は、１１０（二進数）＝６（十進数）であり、したがって、インデックス生成部４００が出力した第１行インデックスは、６である。すなわち、パリティチェック行列の第１列の第１要素１行インデックスは、６であり、その結果、パリティチェック行列の第１列の第７行（行インデックス
０００＝第１行、行インデックス ００１＝第２行、行インデックス ０１０＝第３行、・・・）の要素が１である。
【００４０】
第２クロックで、それぞれのレジスタＲ１、Ｒ２、・・・Ｒｓに保存された値４２１、４２２、・・・は、合算器４０１、４０２、・・・によりスイッチの出力値４１１、４１２、・・・と合算された後、合算器４０１、４０２、・・・の次のレジスタＲ１、Ｒ２、・・・Ｒｓに保存される。ここで、それぞれの値は、ビット０または１である。スイッチの出力値４１１、４１２、・・・は、最後のレジスタＲｓが、フィードバックライン４４０及びスイッチ４３１、４３２、・・・を通じてスイッチングされた値である。係数Ｃ１、Ｃ２、・・・は、スイッチング如何を表す数であり、０または１のうち選択される。第２クロックで再びそれぞれのレジスタＲ１、Ｒ２、・・・Ｒｓに新たに保存された値は、第２行インデックス４２０に出力される。
【００４１】
第三クロックから第ｎクロックまで、前記のような過程が繰り返されつつｔビットの行インデックスが出力される。
【００４２】
パリティチェック行列の行の個数ｍ及び列の個数ｎと、レジスタの個数ｓ及び行インデックスを出力するレジスタの個数ｔは、次の式（１０）のような関係を有する。
【００４３】
【数８】
2006050622.tif 000004
式（１０）に示されたように、パリティチェック行列の行の個数ｍは、発生可能な要素１行インデックスの範囲（＝２ｔ）と同じであり、パリティチェック行列の列の個数ｎは、最小クロックの数（＝２Ｓ−１）と同じであるためである。
【００４４】
図４のＭＳＲＧのフィードバックライン４００に連結されたスイッチの係数Ｃ１、Ｃ２、・・・は、次の式（１１）のような特性方程式を利用して表す。
【００４５】
【数９】
2006050622.tif 000005
ここで、ｆ（ｘ）は、図４のインデックス生成部４００の特性方程式であり、Ｃｏ＝１、Ｃｉは０または１である。すなわち、特性方程式は、ＭＳＲＧのフィードバックライン４４０の連結構造を特定する。
【００４６】
本発明の好ましい実施形態で、インデックス生成部４００の特性方程式は、原形多項式である。すなわち、特性方程式の係数Ｃ１、Ｃ２、・・・は、同じ次数の原形多項式の係数である。
【００４７】
原形多項式は、次数がｕである非減少多項式のうちｐ（ｘ）に割られる多項式ｘｖ−１の可能な最小の正の数ｖが、次の式（１２）を満足する多項式ｐ（ｘ）と定義される。
【００４８】
【数１０】
2006050622.tif 000006
ここで、多項式ｐ（ｘ）は、係数が０ないしｐ−１のうち任意の数である（すなわち、ｐ（ｘ）  ＩＮ  ＧＦ（ｐ）［ｘ］である）非減少多項式である。ｐは、任意の素数であり、非減少多項式とは、それ以上因数分解されない多項式を意味する。
【００４９】
図４のインデックス生成部４００のフィードバックライン４４０の連結構造を表すｓ次の特性方程式が原形多項式になれば、すなわち、係数Ｃ１、Ｃ２、・・・が原形多項式の係数に選択されれば、ｓ個のレジスタＲ１、Ｒ２、・・・、Ｒｓの出力ベクトル４２０は、２Ｓ−１クロックの間に何れも異なる値が出力される。すなわち、ｓ個のレジスタで表現できるあらゆるベクトルが、一回ずつ出力される。
【００５０】
原形多項式を利用したＭＳＲＧの構造についての更に詳細な説明は、Ｓ．Ｗ．Ｇｏｌｏｍｂによる“Ｓｈｉｆｔ  Ｒｅｇｉｓｔｅｒ  Ｓｅｑｕｅｎｃｅ．Ｈｏｌｄｅｎ−Ｄａｙ，Ｓａｎ  Ｆｒａｎｃｉｓｃｏ，１９６７”を参考して本明細書に併合される。
【００５１】
この時、図４のように、ｓ個のレジスタのうち、任意のｔ個のレジスタの出力値を出力ベクトル４２０に選択すれば、出力ベクトル４２０には、発生可能なあらゆるベクトル値がほぼ同じ回数で出力される。特に、ｎ＝２Ｓ−１である場合、０ベクトルを除いたあらゆるベクトルは、２Ｓ−ｔ回ずつ出力され、０ベクトルは、２Ｓ−ｔ−１回出力される。
【００５２】
したがって、図４のインデックス生成部４００により生成されたパリティチェック行列Ｈは、ほぼ規則的なＬＤＰＣコードを有する。一般的に、デコーディング性能、すなわち、ＢＥＲ性能は、最大の行次数が大きくなるほど減少するが、前記したように、本発明の一実施形態により生成されたパリティチェック行列は、行列の各位置に１が現れる確率がほぼ一定であるため、デコーディング性能を向上させる。
【００５３】
一方、初期値４１０は、同じクロックで相異なるインデックス生成部の間に同じ出力値４２０が生成されないように、各インデックス生成部ごとに選択されねばならない。もし、相異なるインデックス生成部の間で同じ出力値が生成されれば、一つの列で１の位置が重なるため、規則的なパリティチェック行列が生成されないためである。初期値の選択は、シミュレーションを通じて決定できる。
【００５４】
図５は、本発明の一実施形態に係る第１インデックス生成部３１０を示す図である。図５で、ｓ＝６、ｔ＝５であり、第１インデックス生成部３１０の特性方程式は、次数が６である原形多項式のうち、ｆ１（ｘ）＝ｘ６＋ｘ５＋１に選択され、初期値は、０００００１に選択された。すなわち、Ｃ５＝１、Ｃ４＝Ｃ３＝Ｃ２＝Ｃ１＝０、Ｃｏ＝１であり、レジスタＲ１、Ｒ２、Ｒ３、Ｒ４、Ｒ５の初期値は、ビット０であり、レジスタＲ６の初期値は、１である。
【００５５】
ｓが‘６’に設定される時、図５に図示される第１インデックス生成部３１０は、対応する初期値５０１、５０２、・・・５０６を受信するためにそれぞれ結合されて、順に接続される６個のレジスタＲ１、Ｒ２、・・・Ｒ６と、対応するレジスタＲ１、Ｒ２、・・・Ｒ６から行インデックスと知られた出力値を合算するために、あらゆる２つのレジスタの間にそれぞれ接続される５つの合算器５１０、５２０、５３０、５４０及び５５０とを備える。
【００５６】
第１クロックで、インデックス生成部で生成される行インデックス５１１ないし５１５は、レジスタＲ１ないしＲ５の値がそのままに出力されるため、行インデックス５１１ないし５１５は、それぞれ初期値５０１ないし５０５である。したがって、第１クロックでの行インデックス５１１ないし５１５は、それぞれ０、０、０、０、０、１であり、すなわち、行インデックスベクトルは、００００１である。
【００５７】
第２クロックで、レジスタＲ２の値は、第１クロックでのレジスタＲ１の値であり、レジスタＲ３の値は、第１クロックでのレジスタＲ２の値であり、レジスタＲ４の値は、第１クロックでのレジスタＲ３の値であり、レジスタＲ５の値は、第１クロックでのレジスタＲ４の値である。また、第２クロックでレジスタＲ６の値は、第１クロックでレジスタＲ６の値と、第１クロックでのレジスタＲ５の値との和である。レジスタＲ６の値が、フィードバックライン５２１により合算器５５０にフィードバックされ、合算器５５０によりレジスタＲ５の値と合算されるためである。また、第２クロックでレジスタＲ１の値は、第１クロックでのレジスタＲ６の値である。第１クロックでのレジスタＲ６の値が、フィードバックライン５２１を通じてレジスタＲ１にフィードバックされるためである。
【００５８】
結局、第２クロックでレジスタＲ１ないしＲ５の値は、それぞれ１、０、０、０、０、０になるため、第２クロックでインデックス生成部から出力される行インデックスベクトルは、１０００００（二進数）＝１（十進数、レジスタＲ１の値をＬＳＢと定義する）である。
【００５９】
第３クロックないし第ｎクロックでの行インデックスの生成過程も、前記した方法と同一に行われる。
【００６０】
図６は、図５の第１インデックス生成部から出力される行インデックスを並べたテーブルである。図６を参照するに、図５で説明したように、特性方程式は、次数が６である原形多項式のうち、ｆ１（ｘ）＝ｘ６＋ｘ５＋１に選択され、初期値は、０００００１に選択された。第１インデックス生成部３１０から出力される行インデックスは、何れも２Ｓ−１＝２６−１＝６３個であり、このうち、０が２Ｓ−ｔ−１＝２６−５−１＝１回出力され、１ないし３１がそれぞれ２Ｓ−ｔ＝２６−５＝２回ずつ出力されることが分かる。
【００６１】
図７は、本発明の一実施形態に係る図３に示された第２インデックス生成部３２０を示す図である。
【００６２】
第２インデックス生成部３２０で、フィードバックラインの状態、すなわち、特性方程式は、図５に示された第１インデックス生成部３１０と異なるものに選択した。第７の第２インデックス生成部３２０の動作は、図５の第１インデックス生成部３１０の動作と同じである。例えば、図５に示された第１インデックス生成部３１０のように、第２インデックス生成部３２０も対応する初期値７０１、７０２、・・・７０６を受信するためにそれぞれ結合されて、順に接続される６個のレジスタＲ１、Ｒ２、・・・Ｒ６と、対応するレジスタＲ１、Ｒ２、・・・Ｒ６から列インデックスと知られた出力値を合算するために、あらゆる２つのレジスタの間にそれぞれ接続された５個の合算器７１０、７２０、７３０、７４０及び７５０とを備える。
【００６３】
第２インデックス生成部３２０の特性方程式は、第１インデックス生成部３１０の特性方程式と関係なく、数式３及び数式４を満足する原形多項式で任意に選択できる。ただし、第２インデックス生成部３２０の初期値７０１ないし７０６は、同じクロックで第１インデックス生成部３１０の行インデックスベクトル５１１ないし５１５と、第２インデックス生成部３２０の行インデックスベクトル７１１ないし７１５とが同じ値を出力しないように選択せねばならない。
【００６４】
同様に、第３インデックス生成部、第４インデックス生成部・・・第Ｗｃインデックス生成部の初期値も、他のインデックス生成部の行インデックスが同じクロックで重ならないように、それぞれの初期値が選択されねばならない。
【００６５】
初期値６０１ないし６０６は、シミュレーションを通じて経験的に選択される。しかし、一般的なＬＤＰＣコードで列ウェイトＷｃは、非常に小さな数であるため、シミュレーションはあまり難しくなく、その結果、前記条件を満足させる初期値を発見することがあまり難しいことではない。
【００６６】
図８は、図７の第２インデックス生成部から出力される行インデックスを並べたテーブル８００である。図８を参照するに、特性方程式は、次数が６である原形多項式のうち、ｆ１（ｘ）＝ｘ６＋ｘ５＋ｘ４＋ｘ＋１に選択され、第２インデックス生成部３２０の初期値は、００１１１１に選択し、その結果、出力された６３個の行インデックスは、図６の行インデックスと同じクロックで重ならないことが分かる。このように、それぞれのインデックス生成部３１０、３２０または３３０は、他のインデックス生成部と同じクロックの出力インデックスベクトルが重ならないように初期値が選択されねばならない。
【００６７】
パリティチェック行列をメモリに保存する場合と、本発明の一実施形態によるパリティチェック行列の生成装置を利用してパリティチェック行列を生成する場合とに必要なメモリビット数を比較する。ｍ＝２９＝５１２、ｎ＝２９＊１７＝５１２＊１７＝８７０４であり、Ｗｃ＝３であるパリティチェック行列の場合を例として挙げる。
【００６８】
まず、メモリに保存する場合、一つの要素１行インデックスを保存するのに必要なビット数は９ビットであるため、一つのパリティチェック行列に必要なメモリのビット数は、９＊３＊８７０４＝２３５００８である。
【００６９】
それに対し、本発明によれば、ｍ＝２９、ｎ＝８７０４に対して式（１０）を満足するｔ及び最小のｓは、ｔ＝９、ｓ＿ｍｉｎ＝１４である。したがって、一つのインデックス生成部に必要とするビット数は１４であるため、一つのパリティチェック行列を生成するために必要なメモリビット数は、１４＊Ｗｃ＝１４＊３＝４２であり、前記の場合に比べて非常に減少する。
【００７０】
さらに、前記したように、図４の構造を有するＭＳＲＧの特性方程式を原形方程式に選択すれば、生成されるパリティチェック行列は、更にＷｒの数が規則的であるため、デコーディング過程の具現が容易である。
【００７１】
図９は、本発明の一実施形態に係るパリティチェック行列の生成方法を示す時間フローチャートである。
【００７２】
ステップ９１０で、ｓビットの初期値を入力されて、それぞれのビット値をｓ個のレジスタにそれぞれ保存する。
【００７３】
ステップ９２０で、それぞれのビットのうち、最下位ビット（Ｌｅａｓｔ  Ｓｉｇｎｉｆｉｃａｎｔ  Ｂｉｔ：ＬＳＢ）、すなわち、最後のレジスタに保存されたビット値を選択的にフィードバックして、それぞれのレジスタの次に連結された合算器に提供する。フィードバックするか否かは、モジュラーシフトレジスタの特性方程式の係数により決定され、好ましい実施形態で特性方程式は、原形多項式である。
【００７４】
ステップ９３０で、ステップ９２０でフィードバックされた値と、本来のｓ個のレジスタに保存された値とを合算する。
【００７５】
ステップ９４０で、ステップ９３０で合算されたｓ個のビット値を、その次のレジスタにそれぞれ保存する。
【００７６】
ステップ９５０で、ステップ９４０でｔ個のレジスタに保存された値を、要素１行インデックスに出力する。
【００７７】
前記ステップで、ステップ９２０ないしステップ９４０は、一つのクロックの間に行われる。したがって、それぞれのクロックごとに一つの要素１行インデックスが出力される。
【００７８】
一方、本発明に係るパリティチェック行列の生成方法は、コンピュータプログラムで作成できる。前記プログラムを構成するコード及びコードセグメントは、当該分野のコンピュータプログラマーによって容易に推論されうる。また、前記プログラムは、コンピュータで読み取り可能な情報保存媒体に保存され、コンピュータによって読み取られて実行されることによって、パリティチェック行列の生成方法を具現する。前記情報保存媒体は、磁気記録媒体、光記録媒体、及びキャリアウェーブ媒体を備える。
【００７９】
これまで本発明について、その好ましい実施形態を中心に説明した。当業者は、本発明が本発明の本質的な特性から逸脱しない範囲で変形された形態で具現されうることを理解できる。したがって、開示された実施形態は、限定的な観点ではなく、説明的な観点から考慮されねばならない。本発明の範囲は、前記した説明ではなく、特許請求の範囲に表されており、それと同等の範囲内にあるあらゆる差異点は、本発明に含まれたものと解釈されねばならない。
【産業上の利用可能性】
【００８０】
本発明は、シフトレジスタを利用することによって、ＬＤＰＣコーディング及びデコーディングのために要求されるメモリの容量を減少させたパリティチェック行列の生成方法を提供し、その方法を利用する通信及び保存システムに適用される。
【図面の簡単な説明】
【００８１】
【図１】ＬＤＰＣコーディング及びデコーディング方法の概念を示す図である。
【図２】メモリ内にパリティチェック行列が保存されたメモリ構造を示す図である。
【図３】本発明の一実施形態に係るパリティチェック行列の生成装置を示す図である。
【図４】図３のそれぞれのインデックス生成部の内部構造を示す図である。
【図５】本発明の一実施形態に係る第１インデックス生成部を示す図である。
【図６】図５の第１インデックス生成部から出力される行インデックスを並べたテーブルである。
【図７】本発明の一実施形態に係る第２インデックス生成部を示す図である。
【図８】図７の第２インデックス生成部から出力される行インデックスを並べたテーブルである。
【図９】本発明の一実施形態に係るパリティチェック行列の生成方法を示す時間フローチャートである。
【符号の説明】
【００８２】
４００  インデックス生成部
４０１ないし４０４  合算器
４１１ないし４１４  スイッチの出力値
４１０  初期値
４２０  行インデックス
４３１ないし４３４  スイッチ
４４０  フィードバックライン
Ｒ１ないしＲｓ  レジスタ
Ｈ  パリティチェック行列
Ｃ１ないしＣｓ−１  係数
【図１】
2006050622.tif 000013
【図２】
2006050622.tif 000014
【図３】
2006050622.tif 000015
【図４】
2006050622.tif 000016
【図５】
2006050622.tif 000017
【図６】
2006050622.tif 000018
【図７】
2006050622.tif 000019
【図８】
2006050622.tif 000020
【図９】
2006050622.tif 000021