(57)【要約】【課題】符号化に係る処理を高速化する。【解決手段】組み合わせ回路２５３では、(ＮＫ)段レジスタ２５１の上位２ｐシンボルから逐次ｑj（ｘ2p）の係数を得て、これらの２ｐ個の係数と生成多項式を乗算した値を、レジスタ出力および新たな２ｐ個の情報シンボルからなる値より減算することによって、次のレジスタ入力値に用いる。レジスタから得られる２ｐシンボル分の係数ｑj（ｘ2p）は同時に得られるため、係数と生成多項式の乗算は同時に行なうことができる。本発明は、符号化を行う装置のパリティを生成する回路に適用することができる。【選択図】図９
2010056660.tif 000002
【特許請求の範囲】
【請求項１】
任意の符号語をpシンボル巡回シフトしたものがまた符号語となる準巡回符号を扱う符号化装置において、
ｍｐ(pの倍数)シンボル単位でパラレル処理を行ない、
前記ｍｐ個の生成多項式を用い、
前記生成多項式gj(x)を、それより次数の低いすべてのgi(x)について、xの次数deg(gi(x))の係数を零となるように選択し、その生成多項式gj(x)を組み合わせた回路を連接した
符号化装置。
【請求項２】
前記生成多項式gj(x)を組み合わせた回路は、生成多項式の高次の次数が、各生成多項式で重なって用いられないように連接される
請求項１に記載の符号化装置。
【請求項３】
任意の符号語をpシンボル巡回シフトしたものがまた符号語となる準巡回符号を扱う符号化装置の符号化方法において、
ｍｐ(pの倍数)シンボル単位でパラレル処理を行ない、
前記ｍｐ個の生成多項式を用い、
前記生成多項式gj(x)を、それより次数の低いすべてのgi(x)について、xの次数deg(gi(x))の係数を零となるように選択し、その生成多項式gj(x)を組み合わせた回路が連接された回路で符号化を行なう
符号化方法。
【請求項４】
（Ｎ，Ｋ）準巡回符号における符号化装置において、
（Ｎ−Ｋ）段レジスタの上位ｍpシンボルから、逐次、ｘmpの多項式であるqj(xmp)の係数を得て、これらのｍp個の係数と生成多項式を乗算した値を、レジスタ出力および新たなｍp個の情報シンボルからなる値より減算することによって生成される値を、次のレジスタ入力値に用い、
前記qj(xmp)の係数は、複数段の組み合わせ回路に供給される
符号化装置。
【請求項５】
（Ｎ，Ｋ）準巡回符号における符号化装置の符号化方法において、
（Ｎ−Ｋ）段レジスタの上位ｍpシンボルから、逐次、ｘmpの多項式であるqj(xmp)の係数を得て、これらのｍp個の係数と生成多項式を乗算した値を、レジスタ出力および新たなｍp個の情報シンボルからなる値より減算することによって生成される値を、次のレジスタ入力値に用い、
前記qj(xmp)の係数を、複数段の組み合わせ回路に供給する
符号化方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は符号化装置および方法に関し、特に、符号化に係わる処理の低減や、高速化を行なえるようにした符号化装置および方法に関する。
【背景技術】
【０００２】
近年、誤り訂正符号として、Low-Density Parity-Check (LDPC)符号（非特許文献１参照）が注目されている。LDPC符号は、LDPC符号のパリティ検査行列に特定の規則性をもたせると、符号設計が容易になり、さらにその規則性を用いて符号化や復号を行なう回路を構成しやすくなるというメリットがある。中でも、準巡回構造の規則性を用いたLDPC符号が多く研究されている。（例えば、非特許文献２，３参照）
【０００３】
任意の符号語をpシンボル巡回シフトしたものが、また符号語となる符号長Ｎ＝ｐＬ、情報語長Ｋの線形ブロック符号は、（Ｎ，Ｋ）準巡回符号(quasi-cyclic)と呼ばれている。（例えば、非特許文献４参照）
【０００４】
図１は、ｐ＝２の２元（１２，７）準巡回符号のパリティ検査行列の例である。図１に示したパリティ検査行列中の、線で区切った６行２列の各部分行列は、それぞれ左隣の部分行列を下方向に１行巡回シフトした構造となっている。例えば、１行１列目と１行２列目の“１ ０”は、２行３列目と２行４列目にシフトし、２行１列目と２行２列目の“１ ０”は、３行３列目と３行４列目にシフトしている。このように、左隣の部分行列を下方向に１行巡回シフトしている。
【０００５】
非特許文献４において、Ｋ段巡回シフトレジスタとそれに接続した複数のＸＯＲ回路から逐次パリティを出力する符号化回路の構成が示されている。また、特許文献１では、準巡回符号の別の符号化方法として、ｐ個の生成多項式を繰り返し用いて組織符号に符号化する方法が示されている。
【０００６】
特許文献１に記載の符号化方法は、すべての符号語が次数の異なるｐ個の生成多項式と、ｘpの多項式の積の和で表されるという性質を元にしている。すなわち、任意の符号多項式ｃ（ｘ）は次式（１）で表すことができる。
【数１】
2010056660.tif 000003
【０００７】
式（１）において、ｑj（ｘp）は、ｘpの多項式であり、ｇj（ｘ）は、生成多項式であり、次数が、  ｄｅｇ（ｇi（ｘ）） ｍｏｄ ｐ＝ｊ  を満たす最小次数の符号多項式である。
情報シンボル列を、  [a0 a1 ... aK1]
パリティシンボル列を、  [r0 r1 ... rNK1]
とし、情報多項式a(x)、パリティ多項式r(x)をそれぞれ次式で定義する。
【数２】
2010056660.tif 000004
【数３】
2010056660.tif 000005
【０００８】
このとき、組織符号化されたシンボル列[a0 a1 ... aK1 r0 r1 ... rNK1]は、
符号多項式c(x) = a(x)xN-K r(x)
と書ける。従って、符号化は次式（４）を満たすパリティ多項式を求めればよい。
【数４】
2010056660.tif 000006
【０００９】
パリティ検査行列が、図１に示した準巡回符号の場合、２つの生成多項式は、
ｇ0（ｘ）＝ｘ6＋ｘ3＋ｘ
ｇ1（ｘ）＝ｘ5＋ｘ4＋ｘ3＋１
とすることができる。
【００１０】
図２は、２ビット単位でパラレル処理を行い、上記した２つの生成多項式を満たすパリティ生成回路の構成例を示す図である。図２に示したパリティ生成回路１０は、入力端子１１，１２、フリップフロップ１３乃至１７、出力端子１８，１９、AND回路２０，２１、および加算器２２乃至２４を含む構成とされている。
【００１１】
図２に示したパリティ生成回路１０は、入力端子１１には、情報シンボル列（Information bits）a1，a3，a5，０，０，０が順次入力され、入力端子１２には、情報シンボル列a0，a2，a4，a6，０，０が順次入力される。出力端子１８からは、パリティビット（Parity bits）r0，r2，r4が順次出力され、出力端子１９からは、パリティビットr1，r3が順次出力される。
【００１２】
パリティ生成回路１０は、符号化を行なう前に、すべてのフリップフロップ１３乃至１７をゼロに初期化する。情報シンボル列は、パリティの数だけ0を追加した形で２ビットずつ入力され、その間、制御信号（Control Signal）は１とされる。
【００１３】
すべての情報シンボル列がパリティ生成回路１０に入力されると、各フリップフロップ１３乃至１７には、それぞれパリティシンボルが求められている状態であり、制御信号を０としてパリティが順次出力される。フリップフロップ１３乃至１７の上位ビットからの帰還は、生成多項式の係数が１の場所に対応している。
【００１４】
図３は、pシンボル単位でパラレル処理を行なうパリティ生成回路を模式的に表した図である。また、図３は、図２に示したパリティ生成回路１０を、模式的に表した図である。図３に示したパリティ生成回路５０は、（Ｎ-Ｋ）段レジスタ５１と組み合わせ回路５２を含む構成とされている。
【００１５】
図３に示したパリティ生成回路５０の組み合わせ回路５２は、(ＮＫ)段レジスタ５１の上位pシンボルから、逐次qj(xp)の係数を得て、これらのp個の係数と生成多項式を乗算した値を、レジスタ出力および新たなp個の情報シンボルから減算することによって、次のレジスタ入力値に用いる構成とされている。
【００１６】
このような１段の組み合わせ回路５２で構成されるパリティ生成回路５０において、より高速に符号化を行なうためには、回路の動作クロックを高くすることが考えられる。しかしながら、動作クロックを、例えば400MHz以上と高くすることは、システム上困難であった。
【００１７】
そこで、より高速に符号化を行なうために、pの倍数シンボル単位でパラレル処理を行なう構成とすることが考えられる。例えば、２ｐシンボル単位でパラレル処理を行なう符号化回路は、図２のpシンボル単位で処理を行なうパリティ生成回路の組み合わせ回路を２段連接することで実現できる。
【００１８】
図４は、図２に示したパリティ生成回路１０における組み合わせ回路を、２段連接した４ビット単位でパラレル処理を行なうパリティ生成回路１００を示している。図４に示したパリティ生成回路１００は、入力端子１０１乃至１０４、フリップフロップ１０５乃至１０９、出力端子１１０乃至１１３、AND回路１１４乃至１１７、および加算器１１８乃至１２７を含む構成とされている。
【００１９】
図４に示したパリティ生成回路１００は、入力端子１０１には、情報シンボル列a3，０，０が順次入力され、入力端子１０２には、情報シンボル列a0，a4，０が順次入力され、入力端子１０３には、情報シンボル列a1，ａ5，０が順次入力され、入力端子１０４には、情報シンボル列a2，a6，０が順次入力される。そして、出力端子１１０からは、パリティビットr0，r4が順次出力され、出力端子１１１からは、パリティビットr1が出力され、出力端子１１２からは、パリティビットr2が順次出力され、出力端子１１３からは、パリティビットr3が出力される。
【００２０】
パリティ生成回路１００は、符号化を行なう前に、すべてのフリップフロップ１０５乃至１０９をゼロに初期化する。情報シンボル列は、パリティの数だけ0を追加した形で２ビットずつ入力され、その間、制御信号は１とされる。
【００２１】
すべての情報シンボル列がパリティ生成回路１００に入力されると、各フリップフロップ１０５乃至１０９には、それぞれパリティシンボルが求められている状態であり、制御信号を０としてパリティが順次出力される。
【００２２】
図５は、p個の生成多項式を用いた図３に示したパリティ生成回路５０における組み合わせ回路５２を２段連接した２ｐシンボル単位でパラレル処理を行なうパリティ生成回路１５０を模式的に表した図である。図５に示したパリティ生成回路１５０は、（Ｎ-Ｋ）段レジスタ１５１、組み合わせ回路１５２、および組み合わせ回路１５３を含む構成とされている。
【００２３】
連接された２つの組み合わせ回路１５２と組み合わせ回路１５３は、それぞれ図３に示した組み合わせ回路５２と同じ構成である。１段目の組み合わせ回路１５２は、(NK)段レジスタ１５１の上位pシンボルから逐次qj(xp)の係数を得る。２段目の組み合わせ回路１５３は、１段目の組み合わせ回路１５２からの出力における上位pシンボルから逐次qj(xp)の係数を得る。
【００２４】
そのため、１段目の組み合わせ回路１５２においてp個の係数と生成多項式を乗算した値を、レジスタ出力から減算することによって得た結果の上位pシンボルが確定した後に、さらに２段目のp個の係数と生成多項式の乗算が行なわれる。このように、１段目の演算結果を用いて、２段目の演算が開始されるため、１段目の演算結果を待たなくならないという遅延が生じ、結果として大きな遅延が生じてしまう。
【非特許文献１】R. G. Gallager, "Low-density parity-check codes," IRE Trans. Inform. Theory, vol. IT-8, pp. 21-28, Jan. 1962.
【非特許文献２】Y. Kou, S. Lin, M. P. C. Fossorier, "Low-density parity-check codes based on finite geometries: a rediscovery and new results," IEEE Trans. Inform. Theory, vol. 47, no. 7, pp. 2711-2736, Nov. 2001.
【非特許文献３】M. Noda, "Designing a self-orthogonal quasi-cyclic code with extended minimum Hamming distance," Proc. 4th Int. Sympo. Turbo Codes and Related Topics, Apr. 2006.
【非特許文献４】R. L. Townsend and E. J. Weldon, Jr., "Self-orthogonal quasi-cyclic codes," IEEE Trans. Inform. Theory, vol. IT-13, no. 2, pp. 183-195, Apr. 1967.
【特許文献１】特許4045872号公報
【発明の開示】
【発明が解決しようとする課題】
【００２５】
上記したように、符号化を高速化するためには、回路の動作クロックを高くすることが考えられる。しかしながら、回路の動作クロックを高くすることは、回路構成上困難であった。そこで、pの倍数シンボル単位でパラレル処理を行なう（多段階の構成として処理を行なう）ようにすることが考えられるが、前段の処理後に後段の処理が行なわれるため、段数を増やすことで遅延が累積され、結果として高速化が困難であった。
【００２６】
本発明は、このような状況に鑑みてなされたものであり、符号化を高速化することができるようにするものである。
【課題を解決するための手段】
【００２７】
本発明の一側面の符号化装置は、任意の符号語をpシンボル巡回シフトしたものがまた符号語となる準巡回符号を扱う符号化装置において、ｍｐ(pの倍数)シンボル単位でパラレル処理を行ない、前記ｍｐ個の生成多項式を用い、前記生成多項式gj(x)を、それより次数の低いすべてのgi(x)について、xの次数deg(gi(x))の係数を零となるように選択し、その生成多項式gj(x)を組み合わせた回路を連接した。
【００２８】
前記生成多項式gj(x)を組み合わせた回路は、生成多項式の高次の次数が、各生成多項式で重なって用いられないように連接されるようにすることができる。
【００２９】
本発明の一側面の符号化方法は、任意の符号語をpシンボル巡回シフトしたものがまた符号語となる準巡回符号を扱う符号化装置の符号化方法において、ｍｐ(pの倍数)シンボル単位でパラレル処理を行ない、前記ｍｐ個の生成多項式を用い、前記生成多項式gj(x)を、それより次数の低いすべてのgi(x)について、xの次数deg(gi(x))の係数を零となるように選択し、その生成多項式gj(x)を組み合わせた回路が連接された回路で符号化を行なう。
【００３０】
本発明の一側面の符号化装置および方法においては、任意の符号語をpシンボル巡回シフトしたものがまた符号語となる準巡回符号を符号化する際、ｍｐ(pの倍数)シンボル単位でパラレル処理が行なわれ、ｍｐ個の生成多項式が用いられ、生成多項式gj(x)が、それより次数の低いすべてのgi(x)について、xの次数deg(gi(x))の係数を零となるように選択され、その生成多項式gj(x)を組み合わせた回路が連接された構成とされる。
【００３１】
本発明の一側面の符号化装置は、（Ｎ，Ｋ）準巡回符号における符号化装置において、（Ｎ−Ｋ）段レジスタの上位ｍpシンボルから、逐次、ｘmpの多項式であるqj(xmp)の係数を得て、これらのｍp個の係数と生成多項式を乗算した値を、レジスタ出力および新たなｍp個の情報シンボルからなる値より減算することによって生成される値を、次のレジスタ入力値に用い、前記qj(xmp)の係数は、複数段の組み合わせ回路に供給される。
【００３２】
本発明の一側面の符号化方法は、（Ｎ，Ｋ）準巡回符号における符号化装置の符号化方法において、（Ｎ−Ｋ）段レジスタの上位ｍpシンボルから、逐次、ｘmpの多項式であるqj(xmp)の係数を得て、これらのｍp個の係数と生成多項式を乗算した値を、レジスタ出力および新たなｍp個の情報シンボルからなる値より減算することによって生成される値を、次のレジスタ入力値に用い、前記qj(xmp)の係数を、複数段の組み合わせ回路に供給する。
【００３３】
本発明の一側面の符号化装置および方法においては、（Ｎ，Ｋ）準巡回符号における符号化が行なわれ、（Ｎ−Ｋ）段レジスタの上位ｍpシンボルから、逐次、ｘmpの多項式であるqj(xmp)の係数が取得され、これらのｍp個の係数と生成多項式を乗算した値が、レジスタ出力および新たなｍp個の情報シンボルからなる値より減算され、その結果生成される値が、次のレジスタ入力値に用いられ、qj(xmp)の係数は、複数段の組み合わせ回路に供給される構成とされる。
【発明の効果】
【００３４】
本発明の一側面によれば、符号化に係る処理を高速化することが可能となる。
【発明を実施するための最良の形態】
【００３５】
以下に、本発明の実施の形態について図面を参照して説明する。
【００３６】
本発明は、符号化装置に係わる。本発明に係わる符号化装置の構成について説明する前に、本発明に係わる符号化について説明を加える。
【００３７】
任意の符号語をpシンボル巡回シフトしたものがまた符号語となる (Ｎ, Ｋ) 準巡回符号は、ｍを整数とすると、任意の符号語をｍｐシンボル巡回シフトしたものも符号語となる性質を有する。これにより、符号多項式ｃ（ｘ）は、ｍｐ個の生成多項式を用いて次式（５）で表すことができる。
【数５】
2010056660.tif 000007
【００３８】
式（５）において、ｑj（ｘmp）は、ｘmpの多項式であり、ｇj（ｘ）は、次数が
ｄｅｇ（ｇj（ｘ）） ｍｏｄ ｍｐ＝ｊ
を満たす最小次数の符号多項式である。ここでは、ｇj（ｘ）を生成多項式と記述する。このように定義した場合、準巡回符号の符号化は、次式（６）を満たすパリティ多項式を求めることで行なえる。
【数６】
2010056660.tif 000008
【００３９】
特に、生成多項式を選ぶにあたり、ｇj（ｘ）は、それより次数の低いすべてのｇi（ｘ）について、xの次数deg(ｇi（ｘ）)の係数を零となるように選択される。例えば、パリティ検査行列が図１で表される準巡回符号でｍ＝２の場合、４つの生成多項式は、
ｇ0（ｘ）＝ｘ8＋ｘ4＋１
ｇ1（ｘ）＝ｘ5＋ｘ4＋ｘ3＋１
ｇ2（ｘ）＝ｘ6＋ｘ3＋ｘ
ｇ3（ｘ）＝ｘ7＋ｘ4＋ｘ2＋ｘ＋１
と選択される。これらの生成多項式を、式（７）とする。
【００４０】
この生成多項式のｇ0（ｘ）はｘ7，ｘ6，ｘ5の項を含まず、ｇ3（ｘ）はｘ6，ｘ5の項を含まず、ｇ2（ｘ）はｘ5の項を含まない。このようなことを考慮すると、図８に示したようなパリティ生成回路を構成することができるが、その説明の前に、上記した４つの生成多項式の選択の仕方について説明を加える。
【００４１】
上記したように、式（７）は、パリティ検査行列が図１で表される準巡回符号でｍ＝２の場合のときに導き出される式である。図１に示したパリティ検査行列に対して、行の基本変形を施すと、図６Ａに示した行列Ｈ’になる。この行列Ｈ’に注目すると、右側の部分行列（図６Ａ中、縦線の右側の部分行列）は、単位行列となっていることがわかる。さらに、図６Ａ中の縦線の左側の部分行列に対して転置などの変形を施すと図６Ｂに示したような行列Ｇとなる。行列Ｇは一般に生成行列と呼ばれる。
【００４２】
図６Ｂに示した行列Ｇに注目すると、左側の部分行列（図６Ｂ中、縦線の左側の部分行列）は、単位行列となっていることがわかる。このような行列Ｇから生成多項式を選択することができる。行列Ｇと生成多項式は、図７に示すような関係になっている。説明の都合上、行列Ｇに行番号と列番号を図７においては記載してある。
【００４３】
各列は、生成多項式を構成する次数を表している。例えば、１２列目の各要素は生成多項式を構成する次数０（ｘ0）に相当し、１１列目の各要素は生成多項式を構成する次数１（ｘ1）ぶ相当し、１０列目の各要素は生成多項式を構成する次数２（ｘ2）に相当し、・・・、４列目の各要素は生成多項式を構成する次数８（ｘ8）に相当する。
【００４４】
ここで、７行目を生成多項式のｇ1（ｘ）とすると、要素の値が１である項のみが残るので、生成多項式ｇ1（ｘ）は、１２列目の要素である次数０（ｘ0＝１）、９列目の要素である次数３（ｘ3）、８列目の要素である次数４（ｘ4）、および９列目の要素である次数５（ｘ5）で構成されることになる。よって、生成多項式ｇ1（ｘ）は、
生成多項式ｇ1（ｘ）＝ｘ5＋ｘ4＋ｘ3＋１
となる。
【００４５】
同様に、６行目を生成多項式のｇ2（ｘ）とすると、生成多項式ｇ2（ｘ）は、１１列目の要素である次数１（ｘ1＝ｘ）、９列目の要素である次数３（ｘ3）、および６列目の要素である次数６（ｘ6）で構成されることになる。よって、生成多項式ｇ2（ｘ）は、
生成多項式ｇ2（ｘ）＝ｘ6＋ｘ3＋ｘ
となる。
【００４６】
同様に、５行目を生成多項式のｇ3（ｘ）とすると、生成多項式ｇ3（ｘ）は、１２列目の要素である次数０（ｘ0＝１）、１１列目の要素である次数１（ｘ1＝ｘ）、１０列目の要素である次数２（ｘ2）、８列目の要素である次数４（ｘ4）、および５列目の要素である次数７（ｘ7）で構成されることになる。よって、生成多項式ｇ3（ｘ）は、
生成多項式ｇ3（ｘ）＝ｘ7＋ｘ4＋ｘ2＋ｘ＋１
となる。
【００４７】
同様に、４行目を生成多項式のｇ0（ｘ）とすると、生成多項式ｇ0（ｘ）は、１２列目の要素である次数０（ｘ0＝１）、８列目の要素である次数４（ｘ4）、および４列目の要素である次数８（ｘ8）で構成されることになる。よって、生成多項式ｇ0（ｘ）は、
生成多項式ｇ0（ｘ）＝ｘ8＋ｘ4＋１
となる。
【００４８】
このように、パリティ検査行列を変形した行列Ｇから、生成多項式を選択することができる。すなわち、生成多項式を選ぶにあたり、ｇj（ｘ）は、それより次数の低いすべてのｇi（ｘ）について、xの次数deg(ｇi（ｘ）)の係数を零となるように選択される。
【００４９】
また、行列Ｇの左側の部分行列を単位行列とすることで、高次の次数（５乃至８）が各生成多項式で重なって用いられるようなことを防ぐことが可能となり、図８に示すようなパリティ生成回路を構成することができ、もって、符号化の高速化をはかることが可能となる。
【００５０】
図８は、式（７）の生成多項式に基づき、ｍ＝２とした場合の4ビット単位でパラレル処理を行なうパリティ生成回路の構成を示す図である。図８に示したパリティ生成回路２００は、入力端子２０１乃至２０４、フリップフロップ２０５乃至２０９、出力端子２１０乃至２１３、AND回路２１４乃至２１７、および加算器２１８乃至２２８を含む構成とされている。
【００５１】
パリティ生成回路２００は、符号化を行なう前に、すべてのフリップフロップ２０５乃至２０９をゼロに初期化する。情報シンボル列は、パリティの数だけ０を追加した形で４ビットずつ入力され、その間、制御信号は１とされる。
【００５２】
すべての情報シンボル列がパリティ生成回路２００に入力されると、各フリップフロップ２０５乃至２０９には、それぞれパリティシンボルが求められている状態であり、制御信号を０としてパリティが順次出力される。フリップフロップ２０５乃至２０９からの上位ビットからの帰還は、生成多項式の係数が１の場合に対応している。これは、図６、図７を参照して説明したように、生成多項式（７）を行列Ｇから選択したからである。
【００５３】
図８に示したパリティ生成回路２００の入力端子２０１には、情報シンボル列a3，０，０が順次入力され、入力端子２０２には、情報シンボル列a0，a4，０が順次入力され、入力端子２０３には、情報シンボル列a1，ａ5，０が順次入力され、入力端子２０４には、情報シンボル列a2，a6，０が順次入力される。そして、出力端子２１０からは、パリティビットr0，r4が順次出力され、出力端子２１１からは、パリティビットr1が出力され、出力端子２１２からは、パリティビットr2が出力され、出力端子２１３からは、パリティビットr3が出力される。
【００５４】
図８に示したパリティ生成回路２００の接続関係について説明する。入力端子２０１は、加算器２１８にデータを供給する。加算器２１８には、AND回路２１７からのデータも供給される。加算器２１８は、AND回路２１７からのデータと、入力端子２０１からのデータを加算して、加算器２２０に出力する。加算器２２０には、AND回路２１６からのデータも供給される。加算器２２０は、AND回路２１６からのデータと、加算器２１８からのデータを加算して、加算器２２６に出力する。加算器２２６には、AND回路２１４からのデータも供給される。加算器２２６は、AND回路２１４からのデータと、加算器２２０からのデータを加算して、フリップフロップ２０５に出力する。
【００５５】
入力端子２０２は、加算器２２５にデータを供給する。加算器２２５には、AND回路２１５からのデータも供給される。加算器２２５は、AND回路２１５からのデータと、入力端子２０２からのデータを加算して、加算器２２７に出力する。加算器２２７には、AND回路２１４からのデータも供給される。加算器２２７は、AND回路２１４からのデータと、加算器２２５からのデータを加算して、フリップフロップ２０８に出力する。
【００５６】
入力端子２０３は、加算器２２２にデータを供給する。加算器２２２には、AND回路２１６からのデータも供給される。加算器２２２は、AND回路２１６からのデータと、入力端子２０３からのデータを加算して、フリップフロップ２０７に出力する。
【００５７】
入力端子２０４は、加算器２２１にデータを供給する。加算器２２１には、AND回路２１６からのデータも供給される。加算器２２１は、AND回路２１６からのデータと、入力端子２０４からのデータを加算して、加算器２２４に出力する。加算器２２４には、AND回路２１５からのデータも供給される。加算器２２４は、AND回路２１５からのデータと、加算器２２１からのデータを加算して、フリップフロップ２０６に出力する。
【００５８】
フリップフロップ２０５からの出力は、加算器２１９に入力される。加算器２１９には、AND回路２１７からのデータも供給される。加算器２１９は、AND回路２１７からのデータと、フリップフロップ２０５からのデータを加算して、加算器２２３に出力する。加算器２２３には、AND回路２１６からのデータも供給される。加算器２２３は、AND回路２１６からのデータと、加算器２１９からのデータを加算して、加算器２２８に出力する。加算器２２８には、AND回路２１４からのデータも供給される。加算器２２８は、AND回路２１４からのデータと、加算器２２３からのデータを加算して、フリップフロップ２０９に出力する。フリップフロップ２０９からの出力は、パリティビットとして出力される一方で、AND回路２１７に供給される。
【００５９】
フリップフロップ２０８からの出力は、パリティビットとして出力される一方で、AND回路２１６に供給される。フリップフロップ２０７からの出力は、パリティビットとして出力される一方で、AND回路２１５に供給される。フリップフロップ２０６からの出力は、パリティビットとして出力される一方で、AND回路２１４に供給される。
【００６０】
AND回路２１４乃至２１７には、コントロール信号が供給され、そのコントロール信号に対応して、所定のタイミングでデータを出力するように構成されている。すなわち、AND回路２１４は、加算器２２６乃至２２８にデータを出力し、AND回路２１５は、加算器２２４と加算器２２５にデータを出力し、AND回路２１６は、加算器２２０乃至２２３にデータを出力し、AND回路２１７は、加算器２１８と加算器２１９にデータを出力するように構成されている。
【００６１】
このように構成されているために、遅延を低減することが可能となる。このことについて、図８を再度参照して説明する。図８において、点線で囲んだ部分は、生成多項式に対応する演算を行なう部分を示している。点線で囲んだ部分を、図８内の上から１段目、２段目、３段目、４段目と記載する。
【００６２】
１段目は、生成多項式ｇ0（ｘ）の演算に対応し、２段目は、生成多項式ｇ3（ｘ）の演算に対応し、３段目は、生成多項式ｇ2（ｘ）の演算に対応し、４段目は、生成多項式ｇ1（ｘ）の演算に対応している。図８に示したパリティ生成回路２００は、各段の生成多項式の演算に必要な、AND回路２１４乃至２１７からの出力は、同時に得られることができる構成とされている。よって、遅延時間を最小としたパリティの生成を実現することが可能となる。
【００６３】
図９は、２ｐ個の生成多項式を用いて２ｐシンボル単位でパラレル処理を行なうパリティ生成回路を模式的に表した図である。図９に示したパリティ生成回路２５０は、（Ｎ-Ｋ）段レジスタ２５１、組み合わせ回路２５２、および組み合わせ回路２５３を含む構成とされている。図５に示した従来のパリティ生成回路１５０と対比できるように、２ｐ個の生成多項式による演算を行なう組み合わせ回路は、それぞれｐ個の演算を行なう組み合わせ回路２５２と組み合わせ回路２５３に分けて示している。
【００６４】
組み合わせ回路２５２には、２ｐシンボルと（Ｎ-Ｋ）段レジスタ２５１からの入力がある。また組み合わせ回路２５２には、（Ｎ-Ｋ）段レジスタ２５１からの最上位ｐシンボルのレジスタ出力も入力される。組み合わせ回路２５３には、組み合わせ回路２５２からの出力と、（Ｎ-Ｋ）段レジスタ２５１からの上位ｐ＋1シンボル目から２ｐシンボル目までのｐシンボルのレジスタ出力が入力される。
【００６５】
組み合わせ回路２５２は、(Ｎ−Ｋ)段レジスタ２５１の上位ｐシンボルから逐次ｑj（ｘ2p）の係数を得て、これらのｐ個の係数と生成多項式を乗算した値を、レジスタ出力および新たな２ｐ個の情報シンボルからなる値より減算し、組み合わせ回路２５３に出力する。組み合わせ回路２５３は、(Ｎ−Ｋ)段レジスタ２５１のｐシンボルから逐次ｑj（ｘ2p）の係数を得て、これらのｐ個の係数と生成多項式を乗算した値を、組み合わせ回路２５２の出力から減算する。そしてその値は、次のレジスタ入力値として、（Ｎ−Ｋ）段レジスタ２５１に出力される。(Ｎ−Ｋ)段レジスタ２５１から得られる２ｐシンボル分の係数ｑj（ｘ2p）は、組み合わせ回路２５２と組み合わせ回路２５３で同時に得られる。よって、組み合わせ回路２５２と組み合わせ回路２５３で係数と生成多項式の乗算を、同時に行なうことができる。
【００６６】
例えば、図５に示した従来の２段目の組み合わせ回路１５３において生成多項式との乗算に用いる係数が、１段目の組み合わせ回路１５２の演算結果を元にしていたため、組み合わせ回路１５２，１５３を連接したことによる遅延が大きかった。しかしながら、図９に示した本発明では、生成多項式との乗算に用いる係数がすべてレジスタ出力より同時に得られるため、遅延が大きく軽減されるという顕著な効果を期待できる。
【００６７】
このように、本発明においては、ｍｐ(pの倍数)シンボル単位でパラレル処理を行なう場合に、ｍｐ個の生成多項式を用いた符号化回路が構成される。そして、各生成多項式ｇj（ｘ）は、それより次数の低いすべてのｇi（ｘ）について、xの次数ｄｅｇ(ｇi（ｘ）)の係数を零とするように選ばれる。このようにすることで、p個の多項式による組み合わせ回路を連接した場合と比べて回路遅延を小さくでき、高速に符号化できるようになる。
【００６８】
また、上述した実施の形態においては、２元符号を例に挙げて説明したが、２元以外の場合、乗算や減算といった処理がさらに含まれる。例えば、図９に示したパリティ生成回路２５０において、１段目の組み合わせ回路２５２で乗算や減算といった処理がさらに行なわれ、２段目の組み合わせ回路２５３で乗算や減算といった処理がさらに行なわれる。これらの演算において、１段目の乗算や減算の演算結果を用いて、２段目の演算が行なわれるのではないため、１段目における演算結果待ちによる遅延が発生するようなことを防ぐことが可能となる。よって、２元符号以外の符号のときには、従来に比べてより高速に符号化できるようになる。
【図面の簡単な説明】
【００６９】
【図１】パリティ検査行列を示す図である。
【図２】従来のパリティ生成回路の一例の構成を示す図である。
【図３】従来のパリティ生成回路の一例の構成を示す図である。
【図４】従来のパリティ生成回路の一例の構成を示す図である。
【図５】従来のパリティ生成回路の一例の構成を示す図である。
【図６】生成多項式の選択について説明するための図である。
【図７】生成多項式の選択について説明するための図である。
【図８】本発明を適用したパリティ生成回路の一実施の形態の構成を示す図である。
【図９】本発明を適用したパリティ生成回路の一実施の形態の構成を示す図である。
【符号の説明】
【００７０】
２００  パリティ生成回路，  ２０１乃至２０４  入力端子，  ２０５乃至２０９  フリップフロップ，  ２１０乃至２１３  出力端子，  ２１４乃至２１７   AND回路，  ２１８乃至２２８  加算器，  ２５０  パリティ生成回路，  ２５１  （ｎ−ｋ）段レジスタ，  ２５２，２５３  組み合わせ回路
【図１】
2010056660.tif 000009
【図２】
2010056660.tif 000010
【図３】
2010056660.tif 000011
【図４】
2010056660.tif 000012
【図５】
2010056660.tif 000013
【図６】
2010056660.tif 000014
【図７】
2010056660.tif 000015
【図８】
2010056660.tif 000016
【図９】
2010056660.tif 000017