(57)【要約】【課題】ＱＣ符号の符号化を多項式の演算のみによって行い、符号化装置の簡略化を図れる符号化方法を提供する。【解決手段】任意の符号語をｐだけ巡回置換したものがまた符号語となる性質を持った線形符号で情報記号が符号語の一部として表われる符号多項式を、ｐ個の多項式Ｇ０（ｘ），．．．，Ｇｐ−１（ｘ）と情報記号を係数とする多項式との演算により求める。ＱＣ符号の符号化を多項式の演算のみによって行うことができ、符号化装置の簡略化を図れる。【選択図】　　図２
2004072130.tif 000002
【特許請求の範囲】
【請求項１】
情報記号にパリティを付加することにより前記情報記号を符号化する符号化方法であって：
前記情報記号が少なくとも一部の係数を構成する多項式とｈ個の生成多項式Ｇ０（ｘ），．．．，Ｇｈ−１（ｘ）との演算により（ｈは、２以上の整数）、前記パリティを求める工程；
を含むことを特徴とする符号化方法。
【請求項２】
前記符号化は、符号語をｐだけ巡回置換したものがまた符号語となる性質を有する線形符号であることを特徴とする、請求項１記載の符号化方法。
【請求項３】
ｈ＝ｐであることを特徴とする、請求項２記載の符号化方法。
【請求項４】
請求項３記載の符号化方法であって：
各ｉについて、一の生成多項式Ｇｉ（ｘ）が符号多項式から選択され、
選択される多項式Ｇｉ（ｘ）は、次数をｐで割った剰余がｉである候補多項式の中で最小の次数を持つものであり、
前記符号多項式は、ｘｊの係数が情報記号であり（ｊは、ｊ≧ｍｊ　ｍｏｄｐを満たす整数、ｍｉは、選択された多項式Ｇｉ（ｘ）の次数）、他の係数がパリティ記号であり、
【数１】
2004072130.tif 000014
で表現されるものである、
ことを特徴とする符号化方法。
【請求項５】
請求項４に記載の符号化方法で得られた符号語をｐの倍数だけ巡回置換したものを符号語とすることを特徴とする符号化方法。
【請求項６】
請求項４に記載の符号化方法で得られた符号語の情報記号の順序を反転させたものを符号語とすることを特徴とする符号化方法。
【請求項７】
請求項３記載の符号化方法において、
ｐ個の各多項式Ｇｉ（ｘ）が、符号多項式の中で、ｘｒでは割り切れるがｘｒ＋１では割り切れないもので、ｒをｐで割った余りがｉ、かつｒが最大となるものであり、各Ｇｉ（ｘ）がｘｒｉでは割り切れるがｘｒｉ＋１では割り切れないとすると、ｊ≦ｒｊ　ｍｏｄ　ｐを満たすｊに関して前記符号多項式のｘｊの係数が情報記号、その他の係数がパリティとなるもので、かつ前記符号多項式が
【数２】
2004072130.tif 000015
と表されるものであることを特徴とする符号化方法。
【請求項８】
請求項７に記載の符号化方法で得られた符号語をｐの倍数だけ巡回置換したものを符号語とすることを特徴とする符号化方法。
【請求項９】
請求項７に記載の符号化方法で得られた符号語の情報記号の順序を反転させたものを符号語とすることを特徴とする符号化方法。
【請求項１０】
任意の符号語をｐだけ巡回置換したものがまた符号語となる性質を持った線形符号で情報記号が符号語の一部として表われる符号多項式を符号化する装置において、
ｐ個の多項式Ｇ０（ｘ），．．．，Ｇｐ−１（ｘ）と前記情報記号を係数とする多項式との演算によってパリティを生成するパリティ生成部と、
このパリティ生成部によって生成されたパリティと前記情報記号とを連結して前記符号多項式を生成する連結手段と
を備えることを特徴とする符号化装置。
【請求項１１】
請求項１０記載の符号化装置において、
前記パリティ生成部が、情報記号を複数同時に入力して順次前記各情報記号に対応するパリティを生成するものであることを特徴とする符号化装置。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、たとえば記録、伝送に用いられる情報記号の符号化方法および符号化装置に関する。
【０００２】
【従来の技術】
符号長ｎ、次元ｋの線形符号（ｌｉｎｅａｒ　ｃｏｄｅ）Ｃは生成行列（ｇｅｎｅｒａｔｏｒ　ｍａｔｒｉｘ）Ｇと情報記号（ｉｎｆｏｒｍａｔｉｏｎ　ｂｉｔｓ）ｃとの積によって符号化できる。線形符号Ｃが組織符号（ｓｙｓｔｅｍａｔｉｃ　ｃｏｄｅ）である場合、パリティはパリティ生成行列（ｐａｒｉｔｙ　ｇｅｎｅｒａｔｏｒ　ｍａｔｒｉｘ）Ｐと情報記号ｃの積により得られるが、行列Ｐの大きさは（ｎ−ｋ）×ｋであり、符号化率ｒ＝ｋ／ｎを一定としたとき、行列の大きさは符号長ｎの２乗に比例して大きくなる。
【０００３】
ただし線形符号Ｃが巡回符号（Ｃｙｃｌｉｃ　Ｃｏｄｅ）である場合、組織符号の符号化は多項式の演算により容易に行える。すなわち情報記号を係数とする多項式Ｍ（ｘ）にｘｎ−ｋを掛けた結果を生成多項式（ｇｅｎｅｒａｔｏｒ　ｐｏｌｙｎｏｍｉｎａｌ）Ｇ（ｘ）で割り、剰余（ｒｅｍａｉｎｄｅｒ）を求めることによりパリティを計算できる。符号化装置も帰還シフトレジスタを用いることで行え、パリティ生成行列を用意しておく必要はない。
【０００４】
今、線形符号Ｃの任意の符号語をｐだけ巡回置換したものもまた線形符号Ｃの符号語となるとき、ＣをＱＣ符号（Ｑｕａｓｉ−Ｃｙｃｌｉｃ　Ｃｏｄｅ）と呼ぶことにする。ｐ＝１のＱＣ符号は巡回符号となるため、符号化は生成多項式によって行えるが、一般的に
【数３】
2004072130.tif 000003
のＱＣ符号は通常の巡回符号のようには行えない。このため、ＱＣ符号は、生成行列Ｇあるいはパリティ生成行列Ｐによって符号化しなければならず、符号長が長くなれば生成行列も大きくなるため符号化装置に大規模なＲＯＭ等が必要になる。
巡回符号の多項式演算による符号化についてはＳｈｕ　Ｌｉｎ，ＤａｎｉｅｌＪ．Ｃｏｓｔｅｌｌｏ，Ｊｒ．による　”Ｅｒｒｏｒ　Ｃｏｎｔｒｏｌ　Ｃｏｄｉｎｇ：Ｆｕｎｄａｍｅｎｔａｌｓ　ａｎｄ　Ａｐｐｌｉｃａｔｉｏｎｓ”（Ｐｒｅｎｔｉｃｅ−Ｈａｌｌ，１９８３）などに説明されている。
【０００５】
【発明が解決しようとする課題】
上記のように、ＱＣ符号の符号化に生成行列を用いる場合、符号長が長くなるほど生成行列も大きくなり、符号化装置の規模が大きくなるという問題があった。ＬＤＰＣ符号（Ｌｏｗ−Ｄｅｎｓｉｔｙ　Ｐａｒｉｔｙ　Ｃｈｅｃｋ　ｃｏｄｅ）やタ−ボ符号（Ｔｕｒｂｏ　ｃｏｄｅ）においては、符号長を大きくすることによりシャノン限界に近い特性が得られることが知られているため、特に、ＱＣ符号をＬＤＰＣ符号やタ−ボ符号に適用することを考えると、従来のＱＣ符号に関する上記問題は好ましくない。
【０００６】
本発明は、このような課題を解決すべくなされたもので、ＱＣ符号の符号化を多項式の演算のみによって行うことができ、符号化装置の簡略化を図ることのできる符号化方法と符号化装置の提供を目的とするものである。
【０００７】
【課題を解決するための手段】
この発明は、上記の課題を解決するために、入力された情報記号にパリティを付加することにより情報記号を符号化する際に、情報記号が少なくとも一部の係数を構成する多項式とｈ個の生成多項式Ｇ０（ｘ），．．．，Ｇｈ−１（ｘ）との演算により（ｈは、２以上の整数）、パリティを求める工程を含む構成を採用する。
例えば、本発明の好適な実施の形態においては、複数の生成多項式による準除算（ｑｕａｓｉ−ｄｉｖｉｓｉｏｎ）とも言えるような演算により、最終的な剰余としてパリティを求めることができる。ここで、準除算と表現した演算は、一の生成多項式を除数として用い（ｈｋ−１）次の商を計算し、他の生成多項式を除数として用い（ｈｋ−２）次の商を計算し、・・・、更に他の生成多項式を除数として用いｈ（ｋ−１）次の商を計算する、演算方法である。言い換えると、準除算は、除数として複数の生成多項式を順次入れ換えながら除算類似の計算を行うものである。本発明では、複数の生成多項式に、最高次が相互に異なるものを用いることが好ましい。なお、周知のように、２値デ−タ（ｂｉｎａｒｙ　ｄａｔａ）の多項式の除算は、除数による引算／加算類似の演算を順次行うことにより、実質的に実現可能であるが、本発明においても、このような方法をパリティ演算に適用することもできる。また、符号の多項式表現では、情報記号列（ｉｎｆｏｒｍａｔｉｏｎ　ｂｉｔｓ　ｓｔｒｉｎｇｓ）、符号列（ｃｏｄｅ　ｓｔｒｉｎｇｓ）ないし情報記号ベクトル（ｉｎｆｏｒｍａｔｉｏｎ　ｂｉｔｓ　ｖｅｃｔｏｒ）上での記号の並びの入れ換えにより、多項式上の次数と係数の関係を容易に変形することが可能であるが、このような変形を行った構成も、実質的に本発明のクレ−ム記載の構成を含む場合には、本発明の範囲に属すると解される。
本発明の更に他の好適な実施の形態は、任意の符号語をｐだけ巡回置換したものがまた符号語となる性質を持った線形符号で情報記号が符号語の一部として表われる符号多項式を、ｐ個の多項式Ｇ０（ｘ），．．．，Ｇｐ−１（ｘ）と情報記号を係数とする多項式との演算により求めるようになしたものである。
【０００８】
また、この発明は、上記の符号化方法において、ｐ個の各多項式Ｇｉ（ｘ）が、符号多項式の中で、その次数をｐで割った余りがｉ、かつ次数が最小となるものであり、各Ｇｉ（ｘ）の次数をｍｉとすると、ｊ≧ｍｊ　ｍｏｄ　ｐを満たすｊに関して前記符号多項式のｘｊの係数が情報記号、その他の係数がパリティとなるもので、かつ前記符号多項式が
【数４】
2004072130.tif 000004
と表されてなるものである。
なお、符号多項式の中でその次数をｐで割った余りがｉとなるものが、各ｉについての候補多項式であり、したがって、生成多項式Ｇｉ（ｘ）は、各ｉについて候補多項式の中から選択されると考えることもできる。
【０００９】
さらに、この発明は、上記の符号化方法において、ｐ個の各多項式Ｇｉ（ｘ）が、符号多項式の中で、ｘｒでは割り切れるがｘｒ＋１では割り切れないもので、ｒをｐで割った余りがｉ、かつｒが最大となるものであり、各Ｇｉ（ｘ）がｘｒｉでは割り切れるがｘｒｉ＋１では割り切れないとすると、ｊ≦ｒｊ　ｍｏｄ　ｐを満たすｊに関して前記符号多項式のｘｊの係数が情報記号、その他の係数がパリティとなるもので、かつ前記符号多項式が
【数５】
2004072130.tif 000005
と表されてなるものである。
【００１０】
上記の方法で符号化を行うことにより、生成行列あるいはパリティ生成行列を必要とせず、ｈ個或いはｐ個の多項式のみでＱＣ符号の符号化を行うことができる。したがって、ＱＣ符号の符号化装置を実装する際、符号長が長くなってもパリティ生成行列に対応した大規模なＲＯＭ等を必要とせず、装置を簡略化できる。
【００１１】
【発明の実施の形態】
以下、この発明の実施の形態を図面を用いて説明する。
【００１２】
１．第１の実施の形態（１ｓｔ　ｅｍｂｏｄｉｍｅｎｔ）
この発明の第１の実施の形態に係る符号化方法を説明する。
【００１３】
ＧＦ（ｑ）の元を係数にもつｐ個の生成多項式をＧ０（ｘ），．．．，Ｇｐ−１（ｘ）、各多項式の次数をｍ０，．．．，ｍｐ−１とし、これらの多項式は次数がｍｉ　ｍｏｄ　ｐ＝ｉ、最高次の係数が１という特徴をもつものとする（Ａｍｏｄ　ＢはＡをＢで割ったときの剰余を表す）。なお、多項式において最高次の係数が１となるということは、対応する情報記号ベクトルまたは符号ベクトルで考えた場合、より高次の係数に相当するシンボルが”０”であることを意味する。
【００１４】
情報記号を係数として持つ多項式Ａ（ｘ）を次のように定義する。
【数６】
2004072130.tif 000006
ただし、ａｉ＝０（ｉ＜ｍｉ　ｍｏｄ　ｐ）
【００１５】
任意のＡ（ｘ）は生成多項式Ｇ０（ｘ），．．．，Ｇｐ−１（ｘ）を用いて次のような和で表すことができる。
Ａ（ｘ）＝Ｗ（ｘ）＋Ｒ（ｘ）
【数７】
2004072130.tif 000007
【００１６】
ただし、Ｑｉ（ｘｐ），Ｒｉ（ｘｐ）はそれぞれＧＦ（ｑ）の元を係数にもつｘｐの多項式であり、Ｗ（ｘ）はｎ−１次以下の多項式、Ｒ（ｘ）はｄｅｇ［Ｒｉ（ｘｐ）ｘｉ］＜ｍｉを満たすものとする（ｄｅｇ［Ｆ（ｘ）］は多項式Ｆ（ｘ）の次数を表す）。
【００１７】
このようなパリティ多項式Ｒ（ｘ）は、図６に示すように、次のような手順で求めることができる。
１．Ｒ（ｘ）←Ａ（ｘ），ｓ←ｎ−１　・・・　（Ｓ１）
２．ｓ≧ｍｓ　ｍｏｄ　ｐであれば（Ｓ２）、Ｒ（ｘ）のｘｓの係数をｒｓとして、
【数８】
2004072130.tif 000008
（Ｓ３）
３．ｓ←ｓ−１（Ｓ４），ｓ≧ｍｉｎ　ｍｉ（０≦ｉ＜ｐ）であれば２へ，ｓ＜ｍｉｎ　ｍｉであれば４へ（Ｓ５）
４．終了
なお、ｓは、演算における注目次数である。また、Ａ（ｘ）は、情報記号を一部の係数に持ち、残りの係数の部分にパリティが入ることにより符号多項式Ｗ（ｘ）となる、多項式である。
【００１８】
以上によって求まったＲ（ｘ）を用いて、Ｗ（ｘ）＝Ａ（ｘ）−Ｒ（ｘ）を計算する。
【００１９】
Ｗ（ｘ）を符号多項式とする線形符号は、符号の一部に情報記号が現れる組織符号として符号化されることになる。また、上記の手順で符号化を行うと生成行列あるいはパリティ生成行列を必要とせず、ｐ個の多項式のみで符号化を行うことができる。
【００２０】
例えば、ＧＦ（２），ｐ＝３，Ｇ０（ｘ）＝ｘ９＋ｘ３＋ｘ２＋ｘ，Ｇ１（ｘ）＝ｘ４＋ｘ３＋ｘ，Ｇ２（ｘ）＝ｘ８＋ｘ６＋１として、符号長ｎ＝２１の２元符号を符号化するとき、情報ビットを（ａ２０，ａ１９，ａ１８，ａ１７，ａ１６，ａ１５，ａ１４，ａ１３，ａ１２，ａ１１，ａ１０，ａ９，ａ８，ａ７，ａ４）として、Ａ（ｘ）＝ａ２０ｘ２０＋ａ１９ｘ１９＋ａ１８ｘ１８＋ａ１７ｘ１７＋ａ１６ｘ１６＋ａ１５ｘ１５＋ａ１４ｘ１４＋ａ１３ｘ１３＋ａ１２ｘ１２＋ａ１１ｘ１１＋ａ１０ｘ１０＋ａ９ｘ９＋ａ８ｘ８＋ａ７ｘ７＋ａ４ｘ４をつくる。上記手順によりＲ（ｘ）＝ｒ６ｘ６＋ｒ５ｘ５＋ｒ３ｘ３＋ｒ２ｘ２＋ｒ１ｘ＋ｒ０が求まり、Ｗ（ｘ）は、Ｗ（ｘ）＝ａ２０ｘ２０＋ａ１９ｘ１９＋ａ１８ｘ１８＋ａ１７ｘ１７＋ａ１６ｘ１６＋ａ１５ｘ１５＋ａ１４ｘ１４＋ａ１３ｘ１３＋ａ１２ｘ１２＋ａ１１ｘ１１＋ａ１０ｘ１０＋ａ９ｘ９＋ａ８ｘ８＋ａ７ｘ７−ｒ６ｘ６−ｒ５ｘ５＋ａ４ｘ４−ｒ３ｘ３−ｒ２ｘ２−ｒ１ｘ−ｒ０と符号化できる。Ｗ（ｘ）を符号多項式とする符号は組織符号であり、ｐ＝３のＱＣ符号となっている。
【００２１】
情報ビット（１，１，１，１，１，１，１，１，１，１，１，１，１，１，１）を符号化する際、Ｒ（ｘ）を求める過程をｘの高次のものから順に係数を並べると次のようになる。
ｓ＝２０　１１１１１１１１１１１１１１００１００００
ｓ＝１９　　１０１１１１１０１１１１１００１００００
ｓ＝１８　　　１１０１１１０１１１１１００１００００
ｓ＝１７　　　　１０１１１１００１１１００１００００
ｓ＝１４　　　　　　　１１１０００１１００１００００
ｓ＝１３　　　　　　　　１００００１１１０１００００
ｓ＝１２　　　　　　　　　１０１０１１１０１００００
ｓ＝１０　　　　　　　　　　　１０１１０１０００００
ｓ＝９　　　　　　　　　　　　　１１００１０００００
ｓ＝８　　　　　　　　　　　　　　１００１０１１１０
ｓ＝６　　　　　　　　　　　　　　　　１１０１１１１
【００２２】
最終的にＲ（ｘ）＝ｘ６＋ｘ５＋ｘ３＋ｘ２＋ｘ＋１が得られ、符号化された結果はＷ（ｘ）＝ｘ２０＋ｘ１９＋ｘ１８＋ｘ１７＋ｘ１６＋ｘ１５＋ｘ１４＋ｘ１３＋ｘ１２＋ｘ１１＋ｘ１０＋ｘ９＋ｘ８＋ｘ７＋ｘ６＋ｘ５＋ｘ４＋ｘ３＋ｘ２＋ｘ＋１となる。
【００２３】
ｐ個の多項式が、
【数９】
2004072130.tif 000009
と書けるとき、これらの多項式で求まる符号はＱＣ符号となる。前の例のように、ＱＣ符号の符号化は情報記号を係数にもつ多項式とｐ個の多項式の演算により行える。２元ＱＣ符号のパラメ−タの例を表１に示す。
【表１】
2004072130.tif 000010
【００２４】
図１に組織符号の符号化装置の構成を示す。このように符号化装置は、情報記号を入力とし、パリティを出力とするパリティ生成装置１を持つ。このパリティ生成装置１によって生成されたパリティは情報記号と連結され、符号として出力される。
【００２５】
図２にパリティ生成装置１の構成の例を示す。パリティを計算するには−Ｒ（ｘ）を求めればよい。図２に示すパリティ生成装置１は、情報記号を一つずつ入力して順次計算を行うことによりＲ（ｘ）を求めるものである。
【００２６】
この例のパリティ生成装置１は、シフトレジスタ１１、乗算回路１３、選択回路１５およびカウンタ１７を備える。シフトレジスタ１１には情報記号がＡ（ｘ）の高次の係数から順に入力される。乗算回路１３は、シフトレジスタ１１の特定位置の値と選択回路１５で選ばれた多項式とを乗算するものであり、この乗算結果でシフトレジスタ１１の値を減算して値のシフトが行われる。この動作を繰り返すことにより、シフトレジスタ１１からＲ（ｘ）の係数が順に出力される。
【００２７】
選択回路１５はシフトレジスタ１１に入力された記号の数を示すカウンタ１７の値に応じて、毎時刻ｐ個の多項式に対応した値あるいは０を選択する回路である。２元符号の場合、乗算回路１３はＡＮＤゲ−トで、図示しない減算回路はＸＯＲゲ−トで実現できる。
【００２８】
図３は、図２の生成装置１を適用した符号化装置の一具体例であり、先に示したｐ＝３，Ｇ０（ｘ）＝ｘ９＋ｘ３＋ｘ２＋ｘ，Ｇ１（ｘ）＝ｘ４＋ｘ３＋ｘ，Ｇ２（ｘ）＝ｘ８＋ｘ６＋１の（２１，１５）２元ＱＣ符号を符号化する装置である。
この装置では高次からＡ（ｘ）の係数を順にシフトレジスタ右側から入力すると、シフトレジスタ左側から符号化された符号多項式Ｗ（ｘ）の係数が高次から順に出力される構成となっている。シフトレジスタは上下２段から構成されているが、上段のシフトレジスタはＡ（ｘ）の情報記号を遅延させるためのものであり、下段はパリティを計算するためのものである。
以下、信号の流れを順に説明する。
符号化を行う前に、初期設定としてシフトレジスタの中身をすべてゼロにリセットしておく。カウンタの値をｓ←２０に設定し、Ａ（ｘ）の係数を順に入力する。シフトレジスタ上段に値（ａ２０，ａ１９，ａ１８，ａ１７，ａ１６，ａ１５，ａ１４，ａ１３）が格納された時点では、下段のシフトレジスタにも同じ値が入っているが、この値は先ほどの手順におけるｓ＝２０のＲ（ｘ）の係数ｒ２０〜ｒ１３と考えることができる。
ｓ＝２０のときに選択回路にしたがって選択される値（１，０，１，０，０，０，０，０，１）はｘ１２Ｇ２（ｘ）に相当し、ＡＮＤ回路によってｒ２０の値と乗算されてＸＯＲ回路によってｒ２０ｘ２０＋ｒ１９ｘ１９＋ｒ１８ｘ１８＋ｒ１７ｘ１７＋ｒ１６ｘ１６＋ｒ１５ｘ１５＋ｒ１４ｘ１４＋ｒ１３ｘ１３＋ｒ１２ｘ１２より減算される。その結果、下段シフトレジスタの左端からはｒ２０＋ｒ２０＝０が出力され、回路の出力としてａ２０＋０＝ａ２０を得る。また次の時刻には下段シフトレジスタには手順２で更新されたＲ（ｘ）←Ｒ（ｘ）−ｒ２０ｘ１２Ｇ２（ｘ）の係数ｒ１９〜ｒ１２が入り、カウンタの値もｓ←１９に更新される。
ｓ＝１９のときに選択回路にしたがって選択される値（１，１，０，１，０，０，０，０，０）はｘ１５Ｇ１（ｘ）に相当し、ＡＮＤ回路によってｒ１９の値と乗算されてＸＯＲ回路によってｒ１９ｘ１９＋ｒ１８ｘ１８＋ｒ１７ｘ１７＋ｒ１６ｘ１６＋ｒ１５ｘ１５＋ｒ１４ｘ１４＋ｒ１３ｘ１３＋ｒ１２ｘ１２＋ｒ１１ｘ１１より減算される。その結果、下段シフトレジスタの左端からはｒ１９＋ｒ１９＝０が出力され、回路の出力としてａ１９＋０＝ａ１９を得る。また次の時刻には下段シフトレジスタには手順２で更新されたＲ（ｘ）←Ｒ（ｘ）−ｒ１９ｘ１５Ｇ１（ｘ）の係数ｒ１８〜ｒ１１が入り、カウンタの値もｓ←１８に更新される。
ｓ＝１８のときに選択回路にしたがって選択される値（１，０，０，０，０，０，１，１，１）はｘ９Ｇ０（ｘ）に相当し、ＡＮＤ回路によってｒ１８の値と乗算されてＸＯＲ回路によってｒ１８ｘ１８＋ｒ１７ｘ１７＋ｒ１６ｘ１６＋ｒ１５ｘ１５＋ｒ１４ｘ１４＋ｒ１３ｘ１３＋ｒ１２ｘ１２＋ｒ１１ｘ１１＋ｒ１０ｘ１０より減算される。その結果、下段シフトレジスタの左端からはｒ１８＋ｒ１８＝０が出力され、回路の出力としてａ１８＋０＝ａ１８を得る。また次の時刻には下段シフトレジスタには手順２で更新されたＲ（ｘ）←Ｒ（ｘ）−ｒ１８ｘ９Ｇ０（ｘ）の係数ｒ１７〜ｒ１０が入り、カウンタの値もｓ←１７に更新される。
同様の動作が続き、ｓ＝７までにＡ（ｘ）はゼロ次の項まで入力が完了するが、その後ゼロを入力し続ける。
ｓ＝６のとき下段シフトレジスタの左側７個にはＲ（ｘ）のｒ６〜ｒ０が入っている。Ａ（ｘ）の６次の係数はゼロのため、回路の出力としてパリティ０＋ｒ６＝ｒ６を得る。また下段シフトレジスタでは減算は行われず、次の時刻には左側６個にｒ５〜ｒ０の値が入り、カウンタの値はｓ←５に更新される。
Ａ（ｘ）の５次の係数はゼロのため、回路の出力としてパリティ０＋ｒ５＝ｒ５を得る。また下段シフトレジスタでは減算は行われず、次の時刻には左側５個にｒ４〜ｒ０の値が入り、カウンタの値はｓ←４に更新される。
ｓ＝４のときに選択回路にしたがって選択される値（１，１，０，１，０，０，０，０，０）はＧ１（ｘ）に相当し、ＡＮＤ回路によってｒ４の値と乗算されてＸＯＲ回路によってｒ４ｘ４＋ｒ３ｘ３＋ｒ２ｘ２＋ｒ１ｘ１＋ｒ０より減算される。その結果、下段シフトレジスタの左端からはｒ４＋ｒ４＝０が出力され、回路の出力としてａ４＋０＝ａ４を得る。また次の時刻には下段シフトレジスタの左側４個には手順２で更新されたＲ（ｘ）←Ｒ（ｘ）−ｒ４Ｇ１（ｘ）の係数ｒ３〜ｒ０が入り、カウンタの値もｓ←３に更新される。
Ａ（ｘ）の３次の係数はゼロのため、回路の出力としてパリティ０＋ｒ３＝ｒ３を得る。また下段シフトレジスタでは減算は行われず、次の時刻には左側３個にｒ２〜ｒ０の値が入り、カウンタの値はｓ←２に更新される。
Ａ（ｘ）の２次の係数はゼロのため、回路の出力としてパリティ０＋ｒ２＝ｒ２を得る。また下段シフトレジスタでは減算は行われず、次の時刻には左側２個にｒ１〜ｒ０の値が入り、カウンタの値はｓ←１に更新される。
Ａ（ｘ）の１次の係数はゼロのため、回路の出力としてパリティ０＋ｒ１＝ｒ１を得る。また下段シフトレジスタでは減算は行われず、次の時刻には左側１個にｒ０の値が入り、カウンタの値はｓ←０に更新される。
Ａ（ｘ）の０次の係数はゼロのため、回路の出力としてパリティ０＋ｒ０＝ｒ０を得る。
以上のような信号の流れにより符号化が行われる。
【００２９】
図４は多項式の数ｐあるいはその倍数の情報記号を、同時に入力してＲ（ｘ）を求める装置の例である。この例の装置の場合、入力された記号の数を示すカウンタはなく、選択回路および乗算回路は組み合わせ回路２１で実現できる。
図２の構成によりパリティを計算する際は、入力として多項式Ａ（ｘ）の係数を１時刻につき１ずつ入力する。演算は先の手順に従えば、２〜３の１サイクルが１時刻の動作に相当するため、ｓの値は毎時刻１ずつ減少する。手順２でｒｓｘｓ−ｍｓ　ｍｏｄ　ｐと乗算される生成多項式Ｇｓ　ｍｏｄ　ｐ（ｘ）はｓの値に応じて毎時刻切り替わるため、時刻を管理するカウンタと多項式の選択回路が必要となる。
これに対して図４の構成では、演算は先に示した手順のｐサイクル、あるいはｐの倍数のサイクルに相当する演算を一括して１時刻で行う。特に符号語の前方部分が情報記号、後方部分がパリティとなるような符号で、情報記号数ｋあるいはパリティ数（ｎ−ｋ）が、ｐの倍数となる場合には、一括した演算を行うことにより生成多項式の切り替えの必要がなくなり装置を簡略化できる。また符号化の時間を短縮できるという効果もある。
【００３０】
図５は、図４の生成装置１の一具体例であり、ｐ＝３，Ｇ０（ｘ）＝ｘ６＋ｘ４＋ｘ２，Ｇ１（ｘ）＝ｘ７＋ｘ５＋ｘ３＋ｘ２＋ｘ，Ｇ２（ｘ）＝ｘ８＋ｘ５＋ｘ４＋１の（２１，１５）２元ＱＣ符号のパリティを求める装置である。情報記号列をＡ（Ｘ）＝ａ２０ｘ２０＋ａ１９ｘ１９＋ａ１８ｘ１８＋ａ１７ｘ１７＋ａ１６ｘ１６＋ａ１５ｘ１５＋ａ１４ｘ１４＋ａ１３ｘ１３＋ａ１２ｘ１２＋ａ１１ｘ１１＋ａ１０ｘ１０＋ａ９ｘ９＋ａ８ｘ８＋ａ７ｘ７＋ａ６ｘ６として入力すると、符号多項式は、Ｗ（Ｘ）＝ａ２０ｘ２０＋ａ１９ｘ１９＋ａ１８ｘ１８＋ａ１７ｘ１７＋ａ１６ｘ１６＋ａ１５ｘ１５＋ａ１４ｘ１４＋ａ１３ｘ１３＋ａ１２ｘ１２＋ａ１１ｘ１１＋ａ１０ｘ１０＋ａ９ｘ９＋ａ８ｘ８＋ａ７ｘ７＋ａ６ｘ６−ｒ５ｘ５＋ｒ４ｘ４−ｒ３ｘ３−ｒ２ｘ２−ｒ１ｘ−ｒ０となる。
【００３１】
シフトレジスタに情報記号をＡ（ｘ）の高次の係数から３ずつ区切って順に入力すると、Ａ（ｘ）のすべての記号を処理した後にシフトレジスタにおいてＲ（ｘ）が求まる。
以下、信号の流れを順に説明する。
符号化を行う前に、初期設定としてシフトレジスタの中身をすべてゼロにリセットしておく。
Ａ（ｘ）の係数を高次の項から３ずつ順に下段、中段、上段に入力する。
入力が開始されてから２時刻後にはシフトレジスタに値（ａ２０，ａ１９，ａ１８，ａ１７，ａ１６，ａ１５）が格納されるが、この値は先の手順においてｓ＝２０におけるＲ（ｘ）の係数ｒ２０〜ｒ１５と考えることができる。
Ｇ２（ｘ）の６，７次およびＧ１（ｘ）の６次の係数がゼロであることに注意すると３サイクル後のＲ（ｘ）の値は
Ｒ（ｘ）←Ｒ（ｘ）−ｒ２０ｘ１２Ｇ２（ｘ）−ｒ１９ｘ１２Ｇ１（ｘ）−ｒ１８ｘ１２Ｇ０（ｘ）
＝Ｒ（ｘ）−ｒ２０（ｘ２０＋ｘ１７＋ｘ１６＋ｘ１２）−ｒ１９（ｘ１９＋ｘ１７＋ｘ１５＋ｘ１４＋ｘ１３）−ｒ１８（ｘ１８＋ｘ１６＋ｘ１４）
＝Ｒ（ｘ）−ｒ２０ｘ２０−ｒ１９ｘ１９−ｘ１８ｘ１８−（ｒ２０＋ｒ１９）ｘ１７−（ｒ２０＋ｒ１８）ｘ１６−ｒ１９ｘ１５−（ｒ１９＋ｒ１８）ｘ１４−ｒ１９ｘ１３−ｒ２０ｘ１２
となり、この演算はシフトレジスタの格段における最左ビットｒ２０〜ｒ１８のＸＯＲ組み合わせ回路と、減算に対応したＸＯＲ回路で実現される。
この演算の結果シフトレジスタに格納される値は、先の手順におけるｓ＝１７のＲ（ｘ）の係数ｒ１７〜ｒ１２と考えることができる。
同様の動作が４時刻続き、最終的にシフトレジスタに値ｒ５〜ｒ０が求まる。
【００３２】
２．第２の実施の形態（２ｎｄ　ｅｍｂｏｄｉｍｅｎｔ）
次に、この発明の第２の実施の形態に係る符号化方法を説明する。
【００３３】
ＧＦ（ｑ）の元を係数にもつｐ個の多項式をＧ０（ｘ），．．．，Ｇｐ−１（ｘ）とし、これらの多項式Ｇｉ（ｘ）はそれぞれあるｒｉに関してｘｒｉでは割り切れるがｘｒｉ＋１では割り切れないもので、かつｒｉ　ｍｏｄ　ｐ＝ｉであり、さらにｘｒｉの係数が１という特徴をもつものとする。
【００３４】
情報記号を係数として持つ多項式Ａ（ｘ）を次のように定義する。
【数１０】
2004072130.tif 000011
ただし、ａｉ　＝０（ｉ＞ｒｉ　ｍｏｄ　ｐ）
【００３５】
任意のＡ（ｘ）は、Ｇ０（ｘ），．．．，Ｇｐ−１（ｘ）を用いて次のような和で表すことができる。
Ａ（ｘ）＝Ｗ（ｘ）＋Ｕ（ｘ）
【数１１】
2004072130.tif 000012
ただし、Ｑｉ（ｘ−ｐ），Ｕｉ（ｘ−ｐ）はそれぞれＧＦ（ｑ）の元を係数にもつｘ−ｐの多項式であり、Ｗ（ｘ）はｎ−１次以下の多項式、Ｕ（ｘ）は各Ｕｉ（ｘ−ｐ）ｘｎ−ｐ＋ｉがｘｒｉ＋ｐで割り切れるものとする。
【００３６】
このような多項式Ｕ（ｘ）は、図７に示すように、次のような手順で求めることができる。
１．Ｕ（ｘ）←Ａ（ｘ），ｓ←０　・・・　（Ｓ１１）
２．ｓ≦ｒｓ　ｍｏｄ　ｐであれば（Ｓ１２）、Ｕ（ｘ）のｘｓの係数をｕｓとして、
【数１２】
2004072130.tif 000013
（Ｓ１３）
３．ｓ←ｓ＋１（Ｓ１４），ｓ≦ｍａｘ　ｒｉ（０≦ｉ＜ｐ）であれば２へ，ｓ＞ｍａｘ　ｒｉであれば４へ（Ｓ１５）
４．終了
以上によって求まったＵ（ｘ）を用いて、Ｗ（ｘ）＝Ａ（ｘ）−Ｕ（ｘ）を計算する。
【００３７】
Ｗ（ｘ）を符号多項式とする線形符号は、符号の一部に情報記号があらわれる組織符号として符号化されることになる。また、上記の手順で符号化を行うと生成行列あるいはパリティ生成行列を必要とせず、ｐ個の多項式のみで符号化を行うことができる。
【００３８】
例えば、ＧＦ（２），ｐ＝３，Ｇ０（ｘ）＝ｘ２０＋ｘ１８＋ｘ１２，Ｇ１（ｘ）＝ｘ１９＋ｘ１８＋ｘ１６，Ｇ２（ｘ）＝ｘ１９＋ｘ１５＋ｘ１１として、符号長ｎ＝２１の２元符号を符号化するとき、情報ビットを（ａ１６，ａ１３，ａ１２，ａ１１，ａ１０，ａ９，ａ８，ａ７，ａ６，ａ５，ａ４，ａ３，ａ２，ａ１，ａ０）として、Ａ（Ｘ）＝ａ１６ｘ１６＋ａ１３ｘ１３＋ａ１２ｘ１２＋ａ１１ｘ１１＋ａ１０ｘ１０＋ａ９ｘ９＋ａ８ｘ８＋ａ７ｘ７＋ａ６ｘ６＋ａ５ｘ５＋ａ４ｘ４＋ａ３ｘ３＋ａ２ｘ２＋ａ１ｘ＋ａ０をつくる。上記手順によりＵ（ｘ）＝ｕ２０ｘ２０＋ｕ１９ｘ１９＋ｕ１８ｘ１８＋ｕ１７ｘ１７＋ｕ１５ｘ１５＋ｕ１４ｘ１４が求まり、Ｗ（ｘ）はＷ（ｘ）＝−ｕ２０ｘ２０−ｕ１９ｘ１９−ｕ１８ｘ１８−ｕ１７ｘ１７＋ａ１６ｘ１６−ｕ１５ｘ１５−ｕ１４ｘ１４＋ａ１３ｘ１３＋ａ１２ｘ１２＋ａ１１ｘ１１＋ａ１０ｘ１０＋ａ９ｘ９＋ａ８ｘ８＋ａ７ｘ７＋ａ６ｘ６＋ａ５ｘ５＋ａ４ｘ４＋ａ３ｘ３＋ａ２ｘ２＋ａ１ｘ＋ａ０と符号化できる。Ｗ（ｘ）を符号多項式とする符号は組織符号であり、ｐ＝３のＱＣ符号となっている。
【００３９】
情報ビット（１，１，１，１，１，１，１，１，１，１，１，１，１，１，１）を符号化する際、Ｕ（ｘ）を求める過程をｘの高次のものから順に係数を並べると次のようになる。
ｓ＝０　　００００１００１１１１１１１１１１１１１１
ｓ＝１　　００００１００１１１１１０１０１１１１１
ｓ＝２　　００００１００１１１１１０１０１００１
ｓ＝５　　００００１００１１１０１０１１１
ｓ＝６　　００００１０００１１０００１１
ｓ＝７　　００００１０１００１０００１
ｓ＝９　　００００１０１００１１１
ｓ＝１０　０００１１１１００１１
ｓ＝１１　０００１１１１１１１
ｓ＝１２　０１０１１０１１１
ｓ＝１３　１１１１１０１１
ｓ＝１４　１１１１０１１
最終的にＵ（ｘ）＝ｘ２０＋ｘ１９＋ｘ１８＋ｘ１７＋ｘ１５＋ｘ１４が得られ、符号化された結果はＷ（ｘ）＝ｘ２０＋ｘ１９＋ｘ１８＋ｘ１７＋ｘ１６＋ｘ１５＋ｘ１４＋ｘ１３＋ｘ１２＋ｘ１１＋ｘ１０＋ｘ９＋ｘ８＋ｘ７＋ｘ６＋ｘ５＋ｘ４＋ｘ３＋ｘ２＋ｘ＋１となる。
【００４０】
【発明の効果】
以上のように、この発明により、ＱＣ符号の符号化を多項式の演算のみで行え、符号化が簡単になる、という効果が奏される。また、ＱＣ符号の符号化装置を実装する際、符号長が長くなってもパリティ生成行列に対応した大規模なＲＯＭ等を必要とせず、装置を簡略化できる。
【図面の簡単な説明】
【図１】組織符号の符号化装置の構成を示すブロック図である。
【図２】この発明に係る符号化装置におけるパリティ生成装置の構成を示すブロック図である。
【図３】この発明に係る符号化装置のより具体的な構成例を示す図である。
【図４】この発明に係る情報記号を複数入力してパリティ生成を行うパリティ生成装置の構成を示すブロック図である。
【図５】情報記号を複数入力してパリティ生成を行うパリティ生成装置のより具体的な構成を示す図である。
【図６】この発明の符号化方法に関するフロ−チャ−トである。
【図７】この発明の他の符号化方法に関するフロ−チャ−トである。
【符号の説明】
１　　パリティ生成装置
１１　　シフトレジスタ
１３　　乗算回路
１５　　選択回路
１７　　カウンタ
２１　　組み合わせ回路
【図１】
2004072130.tif 000016
【図２】
2004072130.tif 000017
【図３】
2004072130.tif 000018
【図４】
2004072130.tif 000019
【図５】
2004072130.tif 000020
【図６】
2004072130.tif 000021
【図７】
2004072130.tif 000022