(57)【要約】  処理遅延を小さくすることができ、追加の乗算回路・剰余回路を不要にして回路規模を小さくすることができる並列剰余演算器。この装置では、並列ＣＲＣ計算回路（１００）は、入力データが複数のサブブロックに分割されて並列に入力される入力端子（１０１）〜（１０４）、各サブブロックの先頭点に対応する部分ＣＲＣを初期値として生成する初期値生成部（１１０）、各サブブロックの先頭に対応する部分ＣＲＣを初期値として受け取り、残りの部分ＣＲＣを所定の漸化式に従って順次生成する部分ＣＲＣ生成部（１１１）〜（１１４）、部分ＣＲＣの値の論理積を計算するＡＮＤ部（１２１）〜（１２４）、及びＡＮＤ部（１２１）〜（１２４）から出力される値を累積的に加算する累積加算部（１３０）を備える。
2008023684.tif 000002
【特許請求の範囲】
【請求項１】
入力データが複数のサブブロックに分割されて並列に入力される並列剰余演算器であって、
前記各サブブロックの先頭点に対応する部分剰余を初期値として生成する初期値生成手段と、
前記初期値生成手段から各サブブロックの先頭に対応する部分剰余を初期値として受け取り、残りの部分剰余を所定の漸化式に従って順次生成する部分剰余生成手段と、
前記入力データと、前記部分剰余生成手段から出力される部分剰余の値の論理を計算する論理手段と、
前記論理手段から出力される値を、累積的に加算する累積加算手段と
を備える並列剰余演算器。
【請求項２】
入力データが複数のサブブロックに分割されて並列に入力される並列剰余演算器であって、
前記各サブブロックの最終点に対応する部分剰余を初期値として生成する初期値生成手段と、
前記初期値生成手段から各サブブロックの最終点に対応する部分剰余を初期値として受け取り、残りの部分剰余を所定の漸化式に従って順次生成する逆順部分剰余生成手段と、
前記入力データと、前記逆順部分剰余生成手段から出力される逆順部分剰余の値の論理を計算する論理手段と、
前記論理手段から出力される値を、累積的に加算する累積加算手段と
を備える並列剰余演算器。
【請求項３】
前記初期値生成手段は、長さｎの入力データを長さｎ−ｍとｍのデータ列に分割し、分割された個々のデータ列をサブブロックとするとき、最大次数ｃにおいて定められる多項式Ｇ(Ｄ)の値に応じて、各サブブロックのｉ＝０，ｍにおける先頭点の部分剰余であるＤｎ−ｌ＋cｍｏｄＧ(Ｄ)とＤｎ−ｌ＋c−mｍｏｄＧ(Ｄ)を初期値として生成する請求項１記載の並列剰余演算器。
【請求項４】
前記初期値生成手段は、長さｎの入力データを長さｎ−ｍとｍのデータ列に分割し、分割された個々のデータ列をサブブロックとするとき、最大次数ｃにおいて定められる多項式Ｇ(Ｄ)の値に応じて、各サブブロックのｉ＝ｍ−１，ｎ−１における最終点の部分剰余であるＤｎ−ｌ＋c−（ｍ−１）ｍｏｄＧ(Ｄ)とＤｎ−ｌ＋c−（ｎ−１）ｍｏｄＧ(Ｄ)を初期値として生成する請求項２記載の並列剰余演算器。
【請求項５】
前記部分剰余生成手段は、元のデータ順に従いデータが入力され、
前記Ｄｎ−ｌ＋cｍｏｄＧ(Ｄ)とＤｎ−ｌ＋c−mｍｏｄＧ(Ｄ)を初期値として、ｉ＝１〜ｍ−ｌ及びｉ＝ｍ＋ｌ〜ｎ−ｌに対応する部分剰余を、所定の漸化式により算出する請求項１記載の並列剰余演算器。
【請求項６】
前記逆順部分剰余生成手段は、元のデータ順を逆順にしてデータが入力され、
前記Ｄｎ−ｌ＋c−（ｍ−１）ｍｏｄＧ(Ｄ)とＤｎ−ｌ＋c−（ｎ−１）ｍｏｄＧ(Ｄ)を初期値として、ｉ＝ｍ−２〜０及びｉ＝ｎ−２〜ｍに対応する逆順部分剰余を、所定の漸化式により算出する請求項２記載の並列剰余演算器。
【請求項７】
前記累積加算手段は、ビットごとの排他的論理和により加算する請求項１に記載の並列剰余演算器。
【請求項８】
長さｎの入力データを長さｎ−ｍとｍのデータ列に分割し、分割された個々のデータ列をサブブロックとするとき、最大次数ｃにおいて定められる多項式Ｇ(Ｄ)の値に応じて、各サブブロックのｉ＝０，ｍにおける先頭点の部分剰余であるＤｎ−ｌ＋cｍｏｄＧ(Ｄ)とＤｎ−ｌ＋c−mｍｏｄＧ(Ｄ)を初期値としてあらかじめ求めるステップと、
前記Ｄｎ−ｌ＋cｍｏｄＧ(Ｄ)とＤｎ−ｌ＋c−mｍｏｄＧ(Ｄ)を初期値として、ｉ＝１〜ｍ−ｌ及びｉ＝ｍ＋ｌ〜ｎ−ｌに対応する部分剰余を、順次算出するステップと
を有する並列剰余演算方法。
【請求項９】
長さｎの入力データを長さｎ−ｍとｍのデータ列に分割し、分割された個々のデータ列をサブブロックとするとき、最大次数ｃにおいて定められる多項式Ｇ(Ｄ)の値に応じて、各サブブロックのｉ＝ｍ−１，ｎ−１における最終点の部分剰余であるＤｎ−ｌ＋c−（ｍ−１）ｍｏｄＧ(Ｄ)とＤｎ−ｌ＋c−（ｎ−１）ｍｏｄＧ(Ｄ)を初期値としてあらかじめ求めるステップと、
前記Ｄｎ−ｌ＋c−（ｍ−１）ｍｏｄＧ(Ｄ)とＤｎ−ｌ＋c−（ｎ−１）ｍｏｄＧ(Ｄ)を初期値として、ｉ＝ｍ−２〜０及びｉ＝ｎ−２〜ｍに対応する逆順部分剰余を、順次算出するステップと
を有する並列剰余演算方法。
【請求項１０】
前記部分剰余を算出するステップでは、
元のデータ順に従いデータを入力し、
前記Ｄｎ−ｌ＋cｍｏｄＧ(Ｄ)とＤｎ−ｌ＋c−mｍｏｄＧ(Ｄ)を初期値として、ｉ＝１〜ｍ−ｌ及びｉ＝ｍ＋ｌ〜ｎ−ｌに対応する部分剰余を、所定の漸化式により算出する請求項８記載の並列剰余演算方法。
【請求項１１】
前記逆順部分剰余を算出するステップでは、
元のデータ順を逆順にしてデータを入力し、
前記Ｄｎ−ｌ＋c−（ｍ−１）ｍｏｄＧ(Ｄ)とＤｎ−ｌ＋c−（ｎ−１）ｍｏｄＧ(Ｄ)を初期値として、ｉ＝ｍ−２〜０及びｉ＝ｎ−２〜ｍに対応する部分剰余を、所定の漸化式により算出する請求項９記載の並列剰余演算方法。
【請求項１２】
さらに、入力データと、前記部分剰余の値の論理を計算するステップと、
前記論理計算された値を、累積的に加算するステップとを有する請求項８記載の並列剰余演算方法。
【請求項１３】
さらに、入力データと、前記逆順部分剰余の値の論理を計算するステップと、
前記論理計算された値を、累積的に加算するステップとを有する請求項９記載の並列剰余演算方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、並列剰余演算器及び並列剰余演算方法に関し、例えば、ターボ復号器などの出力が並列で入力され、デジタル情報の誤りを検出する並列剰余演算器及び並列剰余演算方法に関する。
【背景技術】
【０００２】
無線によるパケット通信や、光ディスクなどの記録ディスクなど、さまざまな分野でＣＲＣ（Cyclic Redundancy Check：巡回冗長検査）符号が用いられている。例えば、無線通信システムでは、無線回線を介して通信することから無線伝送路において送信データに誤りが発生する可能性があるので、ＣＲＣを使用した誤り訂正回路を設ける。送信側で送信データ列に基づいてＣＲＣビットを生成し、それを送信データ列の後ろに付加する。ＣＲＣビットを付加したビット列は、畳み込み符号化やターボ符号化などの符号化方式を用いて符号化され、これにより得られる符号化ビット列が送信される。【０００３】
ＣＲＣ符号の原理については、非特許文献１に詳細に記載されている。【０００４】
図１は、ＣＲＣ符号の使われ方を説明する図である。【０００５】
図１において、入力源（ソース）１１からの入力データ列Ａは、ＣＲＣ符号化部１２でＣＲＣ符号化され、送信データ列Ｂとして通信路１３を介して受信側に送信される。通信路１３は、例えば無線伝送路でありビット誤り（ノイズ）Ｅが付加される。受信側では、ビット誤りＥが付加された送信データ列Ｂ’を受信し、ＣＲＣ検査部１４でＣＲＣ検査し、ＣＲＣ検査に基づく受信データＡ’を出力側（シンク）１５に渡す。無線通信システムが、誤り訂正能力が高いターボ符号化とＡＲＱ（Auto Repeat reQuest）とを組み合わせたＨＡＲＱ（Hybrid Auto Repeat reQuest）の場合、ＣＲＣ検査部１４でＣＲＣチェックを行い、誤りの発生状況を検出し、誤りが発生していない場合、データ列Ａの受信データＡ’を出力するとともに、通信相手に送信するＡＣＫ／ＮＡＣＫ信号としてＡＣＫ信号を形成する。これに対して、誤りが発生した場合、受信データを出力せずに、通信相手に送信するＡＣＫ／ＮＡＣＫ信号としてＮＡＣＫ信号を形成する。【０００６】
より一般的に説明する。【０００７】
ｎビットの入力データ列をＡ＝[ａ０ａ１…ａｎ−２ａｎ−１]とする。ａ０がＭＳＢ（Most Significant Bit）、すなわち先に送信されるビットでる。ａ０，…，ａｎ−１をそれぞれＧＦ(２)の元（すなわち、値０又は１をとる）とし、ビット列を次式（１）のように多項式で表す。【０００８】
【数１】
2008023684.tif 000003
入力データ列Ａは、ＣＲＣ符号化され、次式（２）のＢとなる。一般に用いられるＣＲＣ符号化では、ｎビットの入力データ列の後に長さｃのビット列を追加することで行われる。追加されたｃビットをＣＲＣと呼ぶこともある。【０００９】
Ｂ＝[ａ０ａ１…ａｃ−２ａｃ−１ｒ０ｒ１…ｒｃ−２ｒｃ−１]    …（２）
ＣＲＣの多項式表現を、次式（３）で表すとすると、Ｂの多項式表現は、次式（４）で示される。【００１０】
【数２】
2008023684.tif 000004
Ｂ(Ｄ)＝Ａ(Ｄ)Ｄｃ＋Ｒ(Ｄ)                        …（４）
ＣＲＣ符号化は、あらかじめ定められたｃ次の多項式Ｇ(Ｄ)に対し、Ｂ(Ｄ)がＧ(Ｄ)で割り切れるようにＲ(Ｄ)が定められる。すなわち、Ａ(Ｄ)ＤｃをＧ(Ｄ)で割った剰余がＲ(Ｄ)である。【００１１】
上記Ｇ(Ｄ)は生成多項式と呼ばれ、次式（５）で示される。【００１２】
【数３】
2008023684.tif 000005
以下では、生成多項式の次数ｃをＣＲＣの次数と呼ぶ場合がある。【００１３】
以上をまとめると、次式（６）になる。Ｑ(Ｄ)はＡ(Ｄ)ＤｃをＧ(Ｄ)で除した商である。【００１４】
Ｂ(Ｄ)＝Ａ(Ｄ)Ｄｃ＋Ｒ(Ｄ)＝Ｇ(Ｄ)Ｑ(Ｄ)          …（６）
以上のようにしてＣＲＣ符号化されたｎ＋ｃビットが、通信路１３を介して送信される。通信路１３では、ビット誤り（ノイズ）Ｅ(Ｄ)が付加される。【００１５】
ＣＲＣ検査は、受信値Ｂ’(Ｄ)＝Ｂ(Ｄ)＋Ｅ(Ｄ)がＧ(Ｄ)で割り切れるかどうかを検査することで行われる。受信値にビット誤りがなければ（すなわち、Ｅ(Ｄ)＝０のとき）、Ｂ’(Ｄ)はＧ(Ｄ)で割り切れる。受信値にビット誤りがある場合、Ｅ(Ｄ)がＧ(Ｄ)で割り切れない場合にはＢ’(Ｄ)がＧ(Ｄ)で割り切れなくなる。したがって、通信路でビット誤りが発生したことを検出できる。Ｅ(Ｄ)がＧ(Ｄ)で割り切れる場合、誤りがあることをＣＲＣにより検出できない。しかし、ｃが十分な長さを持っていればその発生確率は低い。ｃとしては、３２〜８といった値がよく用いられる。【００１６】
図２は、より実際的なシステムに適用したＣＲＣ符号の使われ方を説明する図である。【００１７】
図２において、情報源（ソース）２１からの入力データＡ(Ｄ)は、ＣＲＣ符号化部２２でＣＲＣ符号化され、ＣＲＣ符号化されたデータＢ(Ｄ)は誤り訂正符号化部２３で送信データＣ(Ｄ)として通信路２４を介して受信側に送信される。送信側では、ＣＲＣ符号化ののち、誤り訂正符号化が行われる。誤り訂正符号化の方法としては、リードソロモン符号、畳み込み符号、ターボ符号、などが用いられる。【００１８】
通信路２４において、ビット誤り（ノイズ）Ｅが付加されることがある。受信側では、ビット誤りＥが付加された送信データ列Ｃ’(Ｄ)を受信し、誤り訂正復号部２５で誤り訂正の復号を行って送信データＢ’(Ｄ)を出力し、ＣＲＣ検査部２６でＣＲＣ検査し、ＣＲＣ検査に基づく受信データＡ’を出力側（シンク）２７に渡す。受信側では、誤り訂正符号の復号が行われる。これにより、通信路２４で加えられたビット誤りの大部分が取り除かれる。ＣＲＣ検査部２６によるＣＲＣ検査では、誤り訂正復号で取りきれなかった誤りがあるかどうかを検査する。【００１９】
（従来例１：逐次ＣＲＣ計算回路）
図３は、一般的によく知られる逐次ＣＲＣ計算回路の構成を示す図である。【００２０】
図３において、逐次ＣＲＣ計算回路３０は、ＥＸＯＲ（排他的論理和）回路３１と、[０]〜[ｃ−１]のフリップフロップ（ＦＦ）３２と、ＡＮＤ回路３３とから構成される。【００２１】
図３は、シフトレジスタを用いた一般的な構成であり、入力データ列の先頭から１ｂｉｔずつ毎クロックサイクル入力する。【００２２】
逐次ＣＲＣ計算回路３０のＣＲＣ符号化では、ａ[ｔ]で示す入力端子に、ａ０〜ａｎ−１を１ビットずつ入力する。すべて入力した後、ｃビットのフリップフロップ（ＦＦ）に保持されている値が、ＣＲＣ演算結果となる。【００２３】
ＣＲＣ検査では、受信したｎ＋ｃビットのデータＢ’(Ｄ)を１ビットずつ入力した後、フリップフロップに残った値が０かどうかを判定する。又は、Ｂ’(Ｄ)の先頭のｎビットを入力し、フリップフロップに残った値がＢ’(Ｄ)の残りのｃビットと一致するかどうかを判定してもよい。【００２４】
しかし、この構成では、入力がｎビットの場合、ＣＲＣ符号化に少なくともｎクロックを要し、処理遅延時間が大きいという問題がある。【００２５】
（従来例２：部分ＣＲＣを算出する方法）
特許文献１には、部分ＣＲＣを算出することで処理遅延時間を短縮する部分ＣＲＣ算出方法が開示されている。【００２６】
特許文献１では、剰余Ｒ(Ｄ)の計算式を次式（７）のように変形する。【００２７】
【数４】
2008023684.tif 000006
ここで、Ｄｎ−ｌ＋ｃ−ｉｍｏｄＧ(Ｄ)(ｉ＝０〜ｎ−１)の値（部分ＣＲＣ）をあらかじめ求めておき、入力データをパラレルで一度に入力することで１クロックサイクルでＣＲＣを求めることができる。【００２８】
図４は、部分ＣＲＣ回路の構成を示す図であり、上記式（７）においてｎ＝１６，ｃ＝２４の場合の部分ＣＲＣ回路を示す。【００２９】
図４において、部分ＣＲＣ回路４０は、演算対象ビット列Ａ[０]Ａ[１５]入力端子４１と、各ビット列Ａ[０]Ａ[１５]とあらかじめ算出された部分ＣＲＣのＡＮＤをとるＡＮＤ回路４２と、部分ＣＲＣをまとめる加算回路４３とから構成される。【００３０】
ＡＮＤ回路４２では、あらかじめ算出された部分ＣＲＣの、各演算対象ビット列の有効値を部分ＣＲＣ符号にデコードし、加算回路４３では、演算対象ビット列全体に対するＣＲＣ符号を求める。【００３１】
しかし、特許文献１に示される並列度ｎの構成では、ｎが大きくなると、回路規模がとても大きくなってしまう。並列度を下げ、データの一部を順次入力していくことも考えられるが、ｉ＝０〜ｎ−１に対する任意の部分ＣＲＣを即座に計算することは回路規模や処理遅延の面から困難である。そこで、すべての部分ＣＲＣをあらかじめ求めておく必要があるが、ｎが大きい場合には、部分ＣＲＣを保持しておくメモリの容量が大きくなってしまい、コストの増大を招く。【００３２】
（従来例３：サブブロックに分割する方法）
また、特許文献２，３には、データをサブブロックに分割して並列処理を行うサブブロック分割型並列ＣＲＣ回路が開示されている。特許文献２，３では、剰余Ｒ(Ｄ)の計算式を次式（８）のように変形する。【００３３】
【数５】
2008023684.tif 000007
すなわち、上記式（８）長さｎのデータを、長さｍとｎ−ｍに分割し、(ａ)長さｎ−ｍのＣＲＣ計算と、(ｂ)長さｍのＣＲＣ計算とに分解する。【００３４】
しかし、このサブブロック分割方法では、(ａ)の結果にＤｍｍｏｄＧ(Ｄ)を乗算したのち、Ｇ(Ｄ)による剰余を計算しなければならない。これらの処理のため、乗算器と剰余計算器が追加で必要となり、回路規模及び処理遅延の増加を招いていた。【００３５】
最も一般的な並列化方法として、シリアル・パラレル変換型の並列ＣＲＣ回路がある。【００３６】
図５Ａ及び図５Ｂは、シリアル・パラレル変換型の並列ＣＲＣ回路を示す図である。図５Ａにおいて、Ｓ／Ｐ変換型並列ＣＲＣ回路５０は、Ｓ／Ｐ変換器５１と、並列ＣＲＣ回路５２とから構成される。【００３７】
Ｓ／Ｐ変換型並列ＣＲＣ回路５０は、図５Ｂに示すように、Ｓ／Ｐ変換器５１により入力をシリアル・パラレル変換し、並列ＣＲＣ回路５２で並列処理によるＣＲＣ計算を行う。並列処理は、例えば１ｂｙｔｅずつ処理する。この並列化方法は、ハード・ソフトいずれにおいても実装及び応用例が多い。
【非特許文献１】今井秀樹著、「符号理論」、電子情報通信学会、１９９０年３月
【特許文献１】特開平８−１４９０１７号公報
【特許文献２】特表２００３−５２３６８２号公報
【特許文献３】特開２００５−６１８８号公報
【発明の開示】
【発明が解決しようとする課題】
【００３８】
しかしながら、このような従来のＣＲＣ計算回路にあっては、以下のような課題がある。【００３９】
（１）上述したように、逐次ＣＲＣ計算回路は、処理遅延時間が非常に大きく、部分ＣＲＣ回路は、部分ＣＲＣを保持しておくメモリの容量が大きくなりコストの増大を招く。【００４０】
（２）サブブロック分割型並列ＣＲＣ回路は、以下の点で必要性が高い。【００４１】
並列ターボデコーダの出力は、サブブロック分割型であるため、サブブロック分割型並列ＣＲＣ回路を適用できれば、メモリを介さずに直接入力可能という利点がある。すなわち、並列ターボ復号器の出力をＣＲＣ計算回路に直接入力するため、並列ＣＲＣ計算回路は、シリアル・パラレル変換型（例えば、先頭から１ｂｙｔｅずつ処理）ではなく、サブブロック分割型（例えば、データ系列を長さＭの小ブロックに分割）である必要がある。したがって、サブブロック分割型並列ＣＲＣ回路は、Ｓ／Ｐ型並列ＣＲＣ回路を使う場合に比べ、インターフェースとなるメモリが不要となり、処理遅延の削減、回路規模・電流の削減につながる。しかしながら、このサブブロック分割型並列ＣＲＣ回路では、サブブロックに分割し並列処理するため、並列処理する複数ＣＲＣ剰余発生器の後段に、乗算器と加算器などの剰余計算器が追加で必要となり、回路規模及び処理遅延の増加を招く。【００４２】
（３）シリアル・パラレル変換型並列ＣＲＣ回路では、インターフェースメモリが必要となり、このことは、処理遅延の増加をもたらし、ＡＣＫ送信の遅れ、反復停止の遅れによる消費電流増加を招く。【００４３】
上述したように、サブブロック分割型並列ＣＲＣ回路は、サブブロック分割を行う並列ターボ復号器と組み合わせる場合には、利点が大きいが、従来のサブブロック分割型並列ＣＲＣ回路は、処理遅延・回路規模が大きく、処理遅延・回路規模の小さいＣＲＣ回路が求められている。【００４４】
本発明の目的は、処理遅延を小さくすることができ、追加の乗算回路・剰余回路を不要にして回路規模を小さくすることができる並列剰余演算器を提供することである。
【課題を解決するための手段】
【００４５】
本発明の並列剰余演算器は、入力データが複数のサブブロックに分割されて並列に入力される並列剰余演算器であって、前記各サブブロックの先頭点に対応する部分剰余を初期値として生成する初期値生成手段と、前記初期値生成手段から各サブブロックの先頭に対応する部分剰余を初期値として受け取り、残りの部分剰余を所定の漸化式に従って順次生成する部分剰余生成手段と、前記入力データと、前記部分剰余生成手段から出力される部分剰余の値の論理を計算する論理手段と、前記論理手段から出力される値を、累積的に加算する累積加算手段とを備える構成を採る。【００４６】
本発明の並列剰余演算器は、入力データが複数のサブブロックに分割されて並列に入力される並列剰余演算器であって、前記各サブブロックの最終点に対応する部分剰余を初期値として生成する初期値生成手段と、前記初期値生成手段から各サブブロックの最終点に対応する部分剰余を初期値として受け取り、残りの部分剰余を所定の漸化式に従って順次生成する逆順部分剰余生成手段と、前記入力データと、前記逆順部分剰余生成手段から出力される逆順部分剰余の値の論理を計算する論理手段と、前記論理手段から出力される値を、累積的に加算する累積加算手段とを備える構成を採る。【００４７】
本発明の並列剰余演算方法は、長さｎの入力データを長さｎ−ｍとｍのデータ列に分割し、分割された個々のデータ列をサブブロックとするとき、最大次数ｃにおいて定められる多項式Ｇ(Ｄ)の値に応じて、 各サブブロックのｉ＝０，ｍにおける先頭点の部分剰余であるＤｎ−ｌ＋cｍｏｄＧ(Ｄ)とＤｎ−ｌ＋c−mｍｏｄＧ(Ｄ)を初期値としてあらかじめ求めるステップと、前記Ｄｎ−ｌ＋cｍｏｄＧ(Ｄ)とＤｎ−ｌ＋c−mｍｏｄＧ(Ｄ)を初期値として、ｉ＝１〜ｍ−ｌ及びｉ＝ｍ＋ｌ〜ｎ−ｌに対応する部分剰余を、順次算出するステップとを有する。【００４８】
本発明の並列剰余演算方法は、長さｎの入力データを長さｎ−ｍとｍのデータ列に分割し、分割された個々のデータ列をサブブロックとするとき、最大次数ｃにおいて定められる多項式Ｇ(Ｄ)の値に応じて、 各サブブロックのｉ＝ｍ−１，ｎ−１における最終点の部分剰余であるＤｎ−ｌ＋c−（ｍ−１）ｍｏｄＧ(Ｄ)とＤｎ−ｌ＋c−（ｎ−１）ｍｏｄＧ(Ｄ)を初期値としてあらかじめ求めるステップと、前記Ｄｎ−ｌ＋c−（ｍ−１）ｍｏｄＧ(Ｄ)とＤｎ−ｌ＋c−（ｎ−１）ｍｏｄＧ(Ｄ)を初期値として、ｉ＝ｍ−２〜０及びｉ＝ｎ−２〜ｍに対応する逆順部分剰余を、順次算出するステップとを有する。
【発明の効果】
【００４９】
本発明によれば、処理遅延を小さくすることができ、部分ＣＲＣをすべて保存しておく必要が無く、また追加の乗算回路・剰余回路を不要にして回路規模を小さくすることができる。特に、サブブロック分割を行う並列ターボ復号器と組み合わせた場合に処理遅延を格段に小さくすることができる。
【図面の簡単な説明】
【００５０】
【図１】ＣＲＣ符号の使われ方を説明する図
【図２】実際的なシステムに適用したＣＲＣ符号の使われ方を説明する図
【図３】従来のＣＲＣ計算回路の構成を示す図
【図４】従来の部分ＣＲＣ回路の構成を示す図
【図５Ａ】従来のシリアル・パラレル変換型の並列ＣＲＣ回路を示す図
【図５Ｂ】従来のシリアル・パラレル変換型の並列ＣＲＣ回路を示す図
【図６】本発明の実施の形態１に係る並列剰余演算器の全体構成を示すブロック図
【図７】上記実施の形態１に係る並列剰余演算器のデータの入出力を示すタイミングチャート
【図８】上記実施の形態１に係る並列剰余演算器の部分ＣＲＣ生成部が計算する部分ＣＲＣを表にまとめた図
【図９】上記実施の形態１に係る並列剰余演算器の部分ＣＲＣ生成部の回路構成を示す図
【図１０】上記実施の形態１に係る並列剰余演算器の部分ＣＲＣ生成部の動作を示すタイミングチャート
【図１１】上記実施の形態１に係る並列剰余演算器のＡＮＤ部の回路構成を示す図
【図１２】上記実施の形態１に係る並列剰余演算器のＡＮＤ部の動作を示すタイミングチャート
【図１３】上記実施の形態１に係る並列剰余演算器の累積加算部の回路構成を示す図
【図１４】上記実施の形態１に係る並列剰余演算器の初期値生成部の構成を示すブロック図
【図１５】上記実施の形態１に係る並列剰余演算器の初期値候補生成部の回路構成を示す図
【図１６】上記実施の形態１に係る並列剰余演算器の初期値生成部の動作を示すタイミングチャート
【図１７】本発明の実施の形態２に係る並列剰余演算器の全体構成を示すブロック図
【図１８】上記実施の形態２に係る並列剰余演算器の逆順部分ＣＲＣ生成部の回路構成を示す図
【図１９】上記実施の形態２に係る並列剰余演算器のそれぞれの部分ＣＲＣ生成部が計算する部分ＣＲＣを表にまとめた図
【図２０】上記実施の形態２に係る並列剰余演算器の初期値生成部の動作を示すタイミングチャート
【発明を実施するための最良の形態】
【００５１】
以下、本発明の実施の形態について、図面を参照して詳細に説明する。【００５２】
（基本原理）
まず、本発明の基本原理について説明する。【００５３】
本発明は、全体構成に関連する[ポイント１]、部分ＣＲＣ生成回路に関連する[ポイント２]、部分ＣＲＣ生成回路（逆順）に関連する[ポイント３]を有する。【００５４】
[ポイント１]：全体構成に関連して
本発明では、剰余Ｒ(Ｄ)の計算式を次式（９）のように変形する。【００５５】
【数６】
2008023684.tif 000008
すなわち、上記従来例２（部分ＣＲＣを算出する方法）と同様に、部分ＣＲＣ(Ｄｎ−ｌ＋c−ｉｍｏｄＧ(Ｄ))の和としてＣＲＣを計算するよう式変形し、さらに、上記従来例３（サブブロックに分割する方法）と同様に、長さｎのデータを長さｎ−ｍとｍに分割する。以下、分割された個々のデータ列をサブブロックと呼ぶことにする。入力データは、上記式（９）中(a)に対応するａ０〜ａm−ｌと、(b)に対応するａm〜ａn−ｌに分割され、それぞれを並列に計算することで高速計算を実現する。【００５６】
このとき、本発明では、次のようにして部分剰余（部分ＣＲＣ）を算出する。ここで、入力データは、上記式（９）中(a)に対応するサブブロック１は、ａ０から１ビットずつ順に、ａm−ｌまで、上記式（９）中(b)に対応するサブブロック２は、ａmから１ビットずつ順に、ａn−ｌまで、それぞれ与えられる（入力される）ものとする。[手順１]  ｉ＝０，ｍにおける部分ＣＲＣの値（すなわち、サブブロックの先頭点における部分ＣＲＣ）Ｄｎ−ｌ＋cｍｏｄＧ(Ｄ))、Ｄｎ−ｌ＋c−mｍｏｄＧ(Ｄ))をあらかじめ求めておく。[手順２]  上記の２つの値を初期値として、ｉ＝１〜ｍ−ｌ及びｉ＝ｍ＋ｌ〜ｎ−ｌに対応する部分ＣＲＣを、順次算出する。【００５７】
上記のような計算方法をとったので、本発明のサブブロック分割型並列ＣＲＣ回路は、（１）部分ＣＲＣをすべて保存しておく必要が無く、（２）追加の乗算回路・剰余回路が不要のため、小型・低遅延という特徴がある。【００５８】
[ポイント２]：部分ＣＲＣ生成回路に関連して
上記、サブブロックの先頭点における部分ＣＲＣを元に、その他の部分ＣＲＣを順次求める方法について、好適な計算方法について説明する。【００５９】
生成多項式を次式（１０）としたとき、通常用いられるＣＲＣの生成多項式は、最低次の項の係数gc−１の値が１である、という特徴がある。【００６０】
【数７】
2008023684.tif 000009
この特徴を利用すると、次式（１１）に示す漸化式により、ＤTｍｏｄＧ(Ｄ)の値からＤT−１ｍｏｄＧ(Ｄ)の値を容易に求めることができる。【００６１】
【数８】
2008023684.tif 000010
以上から、次の手順により、上記[ポイント１]で述べた並列ＣＲＣ計算を効率よく実現できる。[手順１’]  ＤＭｎ−ｌ＋ｃ(Ｄ)＝Ｄｎ−ｌ＋cｍｏｄＧ(Ｄ)及びＤＭｎ−ｌ＋ｃ−ｍ(Ｄ)＝Ｄｎ−ｌ＋c−ｍｍｏｄＧ(Ｄ)をあらかじめ求めておく。[手順２’]  ＤＭｎ−ｌ＋ｃ(Ｄ)を元に、ｉ＝１〜ｍ−１に対応する部分ＣＲＣ(ＤＭｎ−ｌ＋ｃ−ｌ(Ｄ)〜ＤＭｎ−ｌ＋ｃ−（ｍ−ｌ）(Ｄ)）及び、ｉ＝ｍ＋１〜ｎ−１に対応する部分ＣＲＣ(ＤＭｎ−ｌ＋ｃ−（ｍ＋ｌ）(Ｄ)〜ＤＭｎ−ｌ＋ｃ−ｎ(Ｄ)）を、順次求める。【００６２】
上記のように、部分ＣＲＣをシフトレジスタを用いて順次計算する方法をとったので、本発明のサブブロック分割型並列ＣＲＣ回路は、ｍｏｄＧ(Ｄ)上で定義される多項式の除算を行うことなく、小型の回路で部分ＣＲＣを算出することができる。【００６３】
[ポイント３]：部分ＣＲＣ生成回路（逆順）に関連して
上記では、各サブブロックのデータは、元のデータ順に従い順序良く入力する（例えばａ０〜ａｍ−ｌ）としたが、逆順（例えばａｍ−ｌ〜ａ０）に入力するような並列ＣＲＣ計算回路も実現できる。【００６４】
すなわち、下記の算出式（１２）において、サブブロック１では、ａｍ−ｌ〜ａ０の順に、サブブロック２では、ａｎ−ｌ〜ａｍの順にデータを入力する。これは、ターボ復号器の出力を並列ＣＲＣ計算器に直接入力するような場合に特に有効である。【００６５】
【数９】
2008023684.tif 000011
部分ＣＲＣの生成手順は次の通りである。[手順１]  ｉ＝ｍ−ｌ，ｎ−ｌにおける部分ＣＲＣの値（すなわち、サブブロックの最終点における部分ＣＲＣ）Ｄｎ−ｌ＋c−（ｍ−ｌ）ｍｏｄＧ(Ｄ)、Ｄｎ−ｌ＋c−（ｎ−ｌ）ｍｏｄＧ(Ｄ)をあらかじめ求めておく。[手順２]  上記の２つの値を初期値として、ｉ＝ｍ−２〜０及びｉ＝ｎ−２〜ｍに対応する部分ＣＲＣを、順次算出する。【００６６】
好適な方法では、次の漸化式（１３）を用いると良い。【００６７】
【数１０】
2008023684.tif 000012
上記のように、部分ＣＲＣを逆順に順次生成する方法をとったので、本発明のサブブロック分割型並列ＣＲＣ回路は、データが（部分的に）逆順になっている場合にも、並べ替え操作を行うことなく、ＣＲＣ計算が行えるようになった。その結果、並べ替え操作のための処理遅延をなくすことができた。【００６８】
（実施の形態１）
図６は、上記基本原理に基づく本発明の実施の形態１に係る並列剰余演算器の全体構成を示すブロック図である。本実施の形態は、上記[ポイント１]及び[ポイント２]に対応する例である。「ポイント」の説明では、データを２分割する（２並列）例を示したが、実施の形態１では、４並列の場合を例として説明する。すなわち、長さｎの入力データをｉ＝０〜ｍ−１、ｉ＝ｍ〜２ｍ−１、ｉ＝２ｍ〜３ｍ−１、ｉ＝３ｍ〜ｎ―１の４つのサブブロックに分割する。また、ＣＲＣの長さを２４ビット（ｃ＝２４）とした。【００６９】
図６において、並列ＣＲＣ計算回路（並列剰余演算器）１００は、入力端子１０１〜１０４（入力端子<１>〜<４>）、初期値生成部１１０、部分ＣＲＣ生成部１１１〜１１４（部分ＣＲＣ生成部<１>〜<４>）、ＡＮＤ部１２１〜１２４（ＡＮＤ部<１>〜<４>）、及び累積加算部１３０を備えて構成される。【００７０】
初期値生成部１１０は、部分ＣＲＣ生成部１１１〜１１４に入力する初期値Ｉ１〜Ｉ４（初期値<１>〜<４>）を生成する。具体的には、各サブブロックのｉ＝０，ｍ，２ｍ，３ｍにおける先頭点の部分ＣＲＣ（部分剰余）であるＤｎ−ｌ＋cｍｏｄＧ(Ｄ)Ｄｎ−ｌ＋c−mｍｏｄＧ(Ｄ)とＤｎ−ｌ＋c−２mｍｏｄＧ(Ｄ)とＤｎ−ｌ＋c−３mｍｏｄＧ(Ｄ)を初期値として生成する。初期値生成部１１０の実装方法については、図１４乃至図１６により後述する。【００７１】
部分ＣＲＣ生成部１１１〜１１４（部分ＣＲＣ生成部<１>〜<４>）は、それぞれのサブブロックの先頭に対応する部分ＣＲＣを初期値として初期値生成部１１０から受け取り、残りの部分ＣＲＣを漸化式に基づき順次生成する。部分ＣＲＣ生成部１１１〜１１４の構成及び動作については、図８乃至図１０により後述する。【００７２】
ＡＮＤ部１２１〜１２４（ＡＮＤ部<１>〜<４>）は、入力端子１０１〜１０４から入力された１ビットと、部分ＣＲＣ生成部１１１〜１１４から出力された２４ビットの値のＡＮＤ（論理積）を計算する。なお、部分ＣＲＣの値の論理を計算する論理回路であればよく、ＡＮＤ（論理積）には限定されない。ＡＮＤ部１２１〜１２４の構成及び動作については、図１１及び図１２により後述する。【００７３】
累積加算部１３０は、ＡＮＤ部１２１〜１２４から出力される値を、累積的に加算する。この加算は、ビットごとの排他的論理和（ＥＸＯＲ）である。累積加算部１３０の構成及び動作については、図１３により後述する。【００７４】
以下、上述のように構成された並列剰余演算器の動作について説明する。まず、並列ＣＲＣ計算回路１００の全体の動作タイミングについて述べる。【００７５】
本実施の形態では、データを４分割する４並列の場合を例に採る。また、ＣＲＣの長さを２４ビット(ｃ＝２４)としている。【００７６】
入力データの長さをＮ[ビット]とし、サブブロック１〜３の長さをＭ[ビット]とし、サブブロック４のサイズを残りのＮ−３Ｍ[ビット]とするようにデータを分割した。この分割方法は一例であり、どのように定めてもよい。【００７７】
図７は、データの入出力を示すタイミングチャートであり、入力データをＡ[ｎ−１：０]のように表記した。また、図７中、ｔは時刻を表す。図６中の信号ｔは、明記していない。【００７８】
入力端子１０１には、ａ１に示すサブブロック１のデータ（Ａ[０]〜Ａ[Ｍ−１]）が、Ａ[０]を先頭に１ビットずつ入力される。入力端子１０２には、ａ２に示すサブブロック２のデータ（Ａ[Ｍ]〜Ａ[２Ｍ−１]）が、Ａ[Ｍ]を先頭に１ビットずつ入力される。入力端子１０３，１０４も同様である。なお、上記の例では、サブブロック４のサイズは他のサブブロックと異なる（端数のため、他より１ビット少ない）とした。そこで、図７のａ４に示すように、時刻Ｍ−１には、入力端子１０４には０を入力するようにした。【００７９】
すべてのデータが入力されると、所望のＣＲＣの値がＣＲＣ出力端子（ｒ）から出力される。本実施の形態では、すべての入力が完了した後も、入力端子の値を０に保持している限り、出力端子（ｒ）に所望のＣＲＣの値が保持されるようになっている。【００８０】
次に、並列ＣＲＣ計算回路１００の個々のモジュールについて説明する。【００８１】
〔部分ＣＲＣ生成部１１１〜１１４〕
図８は、部分ＣＲＣ生成部１１１〜１１４が計算（担当）する部分ＣＲＣを表にまとめた図である。ここで、ＤＭ｛Ｔ｝(Ｄ)という表記を用いた。ＤＭ｛Ｔ｝(Ｄ)＝ＤＭＴ(Ｄ)＝ＤＴｍｏｄＧ(Ｄ)である。【００８２】
部分ＣＲＣ生成部１１１〜１１４（部分ＣＲＣ生成部<１>〜<４>）は、それぞれのサブブロックの先頭（０、Ｍ、２Ｍ、３Ｍ）に対応する部分ＣＲＣを初期値として初期値生成回路１１０から受け取り、残りの部分ＣＲＣを前述した漸化式（１１）に基づき順次生成する。【００８３】
例えば、図８の表において、回路番号１の部分ＣＲＣ生成部１１１は、入力データ番号０〜Ｍ−１、初期値をＤＭ｛Ｎ−１＋ｃ｝(Ｄ)とするとき、生成する部分ＣＲＣはＤＭ｛Ｎ−１＋ｃ−１｝(Ｄ)〜ＤＭ｛Ｎ−１＋ｃ−（Ｍ−１）｝(Ｄ)である。同様に、部分ＣＲＣ生成部１１２〜１１４は、それぞれのサブブロックの先頭（Ｍ、２Ｍ、３Ｍ）に対応する部分ＣＲＣを初期値として残りの部分ＣＲＣを前記式（１１）に基づき順次生成する。【００８４】
次に、部分ＣＲＣ生成部１１１を例に採り、さらに詳細に説明する。【００８５】
図９は、部分ＣＲＣ生成部１１１の回路構成を示す図である。部分ＣＲＣ生成部１１１〜１１４は、同一構成をとるため部分ＣＲＣ生成部１１１を代表して説明する。【００８６】
図９において、部分ＣＲＣ生成部１１１は、セレクタ２０１、Ｄフリップフロップ（ＦＦ）２０２、ＥＸＯＲ回路２０３、及びＡＮＤ回路２０４から構成される。【００８７】
部分ＣＲＣ生成部１１１は、２４ビット分のＤフリップフロップ２０２を中心とした構成となっている。なお、フリップフロップが数珠繋ぎになっている構成はしばしばシフトレジスタとも呼ばれる。【００８８】
Ｉ１[２３：０]は初期値であり、ｇ[２３：０]は生成多項式を表す値である。例えば、生成多項式が次式（１４）で定義されるとき、
ｇ[０]＝ｇ[１７]＝ｇ[１８]＝ｇ[２２]＝ｇ[２３]＝１，
ｇ[１]＝ｇ[２]＝...＝ｇ[１５]＝ｇ[１６]＝ｇ[１９]＝ｇ[２０]＝ｇ[２１]＝０と定める。ここで、ｇ[ｉ]は、Ｄｃ−ｉ−１の係数である。Ｄｃの係数は常に１であるから、ｇ[−１]を定義する必要はない。【００８９】
Ｇ(Ｄ)＝Ｄ２４＋Ｄ２３＋Ｄ６＋Ｄ５＋Ｄ＋１                …（１４）
１６進数で表記すると、
ｇ＝Ｃ６０００１Ｈである。【００９０】
ｐ１[２３：０]は、生成された部分ＣＲＣである。【００９１】
次に、部分ＣＲＣ生成部１１１の動作を説明する。【００９２】
図１０は、部分ＣＲＣ生成部１１１の動作を示すタイミングチャートである。図１０中、ｌｄは制御信号で、ｌｄ＝１のとき、初期値Ｉ１の値がシフトレジスタにロードされる。ここで、Ｉ１の値は、具体的には、図８表に示した通りＤＭ｛Ｎ−１＋ｃ｝(Ｄ)である。図１０のタイミングチャートでは、見易さのためＮ−１＋ｃ＝９８であるとした。【００９３】
すると、時刻ｔ＝０には、ロードされた値そのものがＡ[０]に対応する部分ＣＲＣとして出力される。同時に、部分ＣＲＣ生成部１１１内部では、次のＤＭ[９７]の値が漸化式に基づき算出される。【００９４】
回路図の信号名に従うと、計算式は次式（１５）のようになる。なお、ｐ１’は更新後の（例えばＤＭ[９７]）、ｐ１は更新前の（例えばＤＭ[９８]）シフトレジスタの内容である。【００９５】
ｐ１’[２３：０]＝｛ｐ１[２２：０]，０｝＋ｐ１[２３]＊｛ｇ[２２：０]，１｝
…（１５）
上記式（１５）中の＋はビットごとの排他的論理和（ＥＸＯＲ）、＊は論理積（ＡＮＤ）である。また、｛ｐ１[２２：０]，０｝という表記は、シフト操作を表す。すなわち、ｐ１の値を１ビット分上位方向にシフトし、ＬＳＢに０を挿入することを意味する。｛ｇ[２２：０]，１｝は、同様にシフト操作であるが、ＬＳＢに１を挿入することを意味する。【００９６】
以上のように、並列ＣＲＣ計算回路１００の部分ＣＲＣ生成部１１１〜１１４は、シフトレジスタと、ビットごとのＡＮＤ・ＥＸＯＲという簡易な構成のみで、入力データに合わせて適時必要な部分ＣＲＣを算出することができる。【００９７】
〔ＡＮＤ部１２１〜１２４〕
ＡＮＤ部１２１〜１２４（ＡＮＤ部<１>〜<４>）は、入力端子１０１〜１０４から入力された１ビットと、上記部分ＣＲＣ生成部１１１〜１１４から出力された２４ビットの値のＡＮＤ（論理積）を計算する。【００９８】
図１１は、ＡＮＤ部１２１の回路構成を示す図である。ＡＮＤ部１２１〜１２４は、同一構成をとるためＡＮＤ部１２１を代表して説明する。【００９９】
図１１において、ＡＮＤ部１２１は、入力端子１０１から入力された１ビットと、部分ＣＲＣ生成部１１１〜１１４から出力された２４ビットの値のＡＮＤを計算するＡＮＤ回路２１１から構成される。【０１００】
図１１に示すＡＮＤ部１２１では、入力端子１０１から入力された１ビットと、部分ＣＲＣ生成部１１１〜１１４から出力された２４ビットの値のＡＮＤを計算する。すなわち、次式（１５）において、ａｉとＤｎ−ｌ＋ｃ−ｉｍｏｄＧ(Ｄ)の積をとる操作に相当する。【０１０１】
【数１１】
2008023684.tif 000013
図１２は、ＡＮＤ部１２１の動作を示すタイミングチャートである。図１２において、時刻を表すｔは、前記図１０のｔと共通である。すなわち、部分ＣＲＣ生成部１１１〜１１４では、入力データと対応付けられるべき部分ＣＲＣをタイミング良く生成しているのである。【０１０２】
〔累積加算部１３０〕
図１３は、累積加算部１３０の回路構成を示す図である。【０１０３】
図１３において、累積加算部１３０は、ＥＸＯＲ回路２１１、フリップフロップ（ＦＦ）２２２、及びスイッチ回路２２３から構成される。【０１０４】
累積加算部１３０では、ＡＮＤ部<１>〜<４>から出力される値を、累積的に加算していく。ここで、加算はビットごとの排他的論理和（ＥＸＯＲ）である。すなわち、ｉ＝０〜２３に対し、次式（１６）に示す演算を行う。【０１０５】
ｓ’[ｉ]＝ｓ[ｉ] ＥＸＯＲ ｑ１[ｉ] ＥＸＯＲ ｑ２[ｉ] ＥＸＯＲ ｑ３[ｉ] ＥＸＯＲ ｑ４[ｉ]                                        …（１６）
上記式（１６）中、ｓは更新前のフリップフロップの値、ｓ’は更新後のフリップフロップの値である。【０１０６】
〔初期値生成部１１０〕
初期値生成部１１０の実装方法について説明する。【０１０７】
サブブロックサイズＭと生成多項式があらかじめ定められている場合は、必要なＤｎ＋IｍｏｄＧ(Ｄ)の値をあらかじめ求めておき、メモリ（ＲＡＭやＲＯＭ）に保存しておけばよい。とりうるＩの種類は少ないので、メモリ容量は少なくてよい。【０１０８】
本実施の形態では、サブブロックサイズＭが固定値であるとすれば、ＤＭ｛Ｎ−１＋ｃ｝(Ｄ)、ＤＭ｛Ｎ−１＋ｃ−Ｍ｝(Ｄ)、ＤＭ｛Ｎ−１＋ｃ−２Ｍ｝(Ｄ)、ＤＭ｛Ｎ−１＋ｃ−３Ｍ｝(Ｄ)の４つの値のみ求めておけばよいので、メモリ容量は２４ビット×４通り＝９６ビットのみでよい。【０１０９】
また、サブブロックサイズＭや生成多項式が変更される場合にも、変更される度に、ＣＰＵやＤＳＰを用いてソフトウェアにより値を求め、ＲＡＭに保存すればよい。【０１１０】
Ｄｎ＋IｍｏｄＧ(Ｄ)（Ｉ＝０〜Ｎ−１）は、次の漸化式（１７）により求めることができる。Ｔ＝ｃ＋Ｉ，Ｉ＝０〜Ｎ−１である。【０１１１】
【数１２】
2008023684.tif 000014
ここで、ＤｃｍｏｄＧ(Ｄ)＝Ｇ(Ｄ)−Ｄｃである。【０１１２】
上記の初期値生成を高速に行う必要がある場合には、次に示すようなハードウェアを用いるとよい。【０１１３】
図１４は、初期値生成部１１０の構成を示すブロック図である。【０１１４】
図１４において、初期値生成部１１０は、初期値候補生成部２３０、データ取得タイミング生成部２３１、データ取得部２４１〜２４４（データ取得部<１>〜<４>）、及び初期値記憶部２５１〜２５４（初期値記憶部<１>〜<４>）を備えて構成される。【０１１５】
図１５は、上記初期値候補生成部２３０の回路構成を示す図である。【０１１６】
図１５において、初期値候補生成部２３０は、セレクタ２６１、フリップフロップ（ＦＦ）２６２、ＥＸＯＲ回路２６３、及びＡＮＤ回路２６４から構成される。【０１１７】
初期値候補生成部２３０は、Ｄｎ＋IｍｏｄＧ(Ｄ)の値をＩ＝０〜Ｎ−１まで順次求める。内部構成は、図１５の通りである。【０１１８】
図１６は、初期値生成部１１０の動作を示すタイミングチャートである。【０１１９】
データ取得部２４１（データ取得部<１>）は、部分ＣＲＣ生成部１１１（図６参照）で使用する初期値ＤＭ｛Ｎ−１＋ｃ｝(Ｄ)を取得し、初期値記憶部２５１（初期値記憶部<１>）に保存する。すなわち、データ取得タイミング生成部２３１は、図１６に示すように、初期値候補生成部２３０がＤＭ｛Ｎ−１＋ｃ｝(Ｄ)を出力したときにｌｄ１にトリガ信号を送る。データ取得部２４１は、ｌｄ１のトリガ信号に応じて初期値候補生成部２３０の出力を取得することにより、初期値記憶部１に格納すべき値ＤＭ｛Ｎ−１＋ｃ｝を取得することができる。【０１２０】
同様に、ＤＭ｛Ｎ−１＋ｃ−Ｍ｝(Ｄ)が出力されるタイミングでｌｄ２にトリガ信号が出力され、ＤＭ｛Ｎ−１＋ｃ−２Ｍ｝(Ｄ)が出力されるタイミング(Ｉ＝j＝Ｎ−１−２Ｍ)でｌｄ３にトリガ信号が出力され、ＤＭ｛Ｎ−１＋ｃ−３Ｍ｝(Ｄ)が出力されるタイミング(Ｉ＝k＝Ｎ−１−３Ｍ)でｌｄ４にトリガ信号が出力される。【０１２１】
以上のように、本実施の形態によれば、並列ＣＲＣ計算回路１００は、入力データが複数のサブブロックに分割されて並列に入力される入力端子１０１〜１０４、各サブブロックの先頭点に対応する部分ＣＲＣを初期値として生成する初期値生成部１１０、各サブブロックの先頭に対応する部分ＣＲＣを初期値として受け取り、残りの部分ＣＲＣを所定の漸化式に従って順次生成する部分ＣＲＣ生成部１１１〜１１４、部分ＣＲＣの値の論理積を計算するＡＮＤ部１２１〜１２４、及びＡＮＤ部１２１〜１２４から出力される値を累積的に加算する累積加算部１３０を備える。部分ＣＲＣ生成では、ｍ番目の入力の次数（ｎ−１−ｍ）に生成多項式の次数ｃを足した次数（ｉ＝ｎ−１−ｍ＋ｃ）について示される剰余Ｒ(Ｄ)の計算式を、部分ＣＲＣ(Ｄｎ−ｌ＋c−ｉｍｏｄＧ(Ｄ))の和で示される式に変形して、各サブブロックの先頭点に対応する部分ＣＲＣを生成している。これにより、本実施の形態では、処理遅延を小さくすることができ、追加の乗算回路・剰余回路を不要にして回路規模を小さくすることができる。具体的な効果は以下の通りである。【０１２２】
（１）従来構成では、分割した入力データのＣＲＣを求めてから合成していたので、追加の乗算回路・剰余回路が必要となり、回路規模や処理遅延の増大を招いていた。本実施の形態では、並列度に応じた個数の部分ＣＲＣ生成部１１１〜１１４を設けることにより、簡易な構成でサブブロック分割型の並列ＣＲＣ計算を行うことができる。また、従来の乗算回路の代わりにＡＮＤ回路が使用できるので遅延が小さい、さらに、最終段に追加の剰余計算回路が不要となり、遅延及び回路規模が小さい利点がある。【０１２３】
（２）従来例２のように従来構成では、あらかじめ部分ＣＲＣを求めておく必要があったため、入力データのサイズに比例して、記憶容量の増加を招いていた。これに対し、本実施の形態では、部分ＣＲＣ生成部１１１〜１１４は、初期値を元に順次新たな値を生成するようにしたので、入力データのサイズにかかわらない回路規模・記憶容量で部分ＣＲＣを算出できる。【０１２４】
（３）本実施の形態では、部分ＣＲＣをシフトレジスタを用いて順次計算する方法をとっているので、ｍｏｄＧ(Ｄ)上で定義される多項式の除算を行うことなく、小型の回路で部分ＣＲＣを算出できる。【０１２５】
このように、サブブロック分割型並列ＣＲＣ回路の新しい構成を実現することができた。ターボ復号器と組み合わせて用いる場合に、処理遅延を少なくし、ＡＣＫ／ＮＡＣＫ送信までの遅延を短縮することができる。ターボ符号の反復復号を行う場合に、反復ごとに即座にＣＲＣ判定ができるので、復号を早期に停止し、消費電力を低減できる。ターボ復号器とＣＲＣ計算回路の間のインターフェースメモリへのアクセスを不要とできるので、消費電力を低減できる。【０１２６】
以上のように、特に、サブブロック分割を行う並列ターボ復号器と組み合わせた場合に処理遅延を格段に小さくすることができる。ターボ符号の種別を問わず、汎用に適用可能であり、実施も容易である。【０１２７】
（実施の形態２）
図１７は、本発明の実施の形態２に係る並列剰余演算器の全体構成を示すブロック図である。図６と同一構成部分には同一符号を付している。【０１２８】
本実施の形態は、基本原理で述べた[ポイント３]に対応する例である。[ポイント３]では、サブブロックごとにデータ入力順を逆順にする例について述べた。データを４分割する４並列において、サブブロック<２>とサブブロック<４>を逆順にする場合を例として説明する。【０１２９】
図１７において、並列ＣＲＣ計算回路（並列剰余演算器）３００は、入力端子１０１〜１０４（入力端子<１>〜<４>）、初期値生成部３１０、部分ＣＲＣ生成部１１１，１１３（部分ＣＲＣ生成部<１>，<３>）、逆順部分ＣＲＣ生成部３１２，３１４（逆順部分ＣＲＣ生成部<２>，<４>）、ＡＮＤ部１２１〜１２４（ＡＮＤ部<１>〜<４>）、及び累積加算部１３０を備えて構成される。【０１３０】
図１７の並列ＣＲＣ計算回路３００は、サブブロックサイズをＭとし、入力端子１０２，１０４についてのみデータの入力順を逆にした例である。【０１３１】
構成上の特徴は、次の通りである。【０１３２】
図６の並列ＣＲＣ計算回路１００と比較して、部分ＣＲＣ生成部１１２，１１４を、それぞれ逆順部分ＣＲＣ生成部３１２，３１４に変更した。また、逆順部分ＣＲＣ生成回路３１２，３１４に入力する初期値を変更した。このため、初期値生成部３１０で生成する初期値は、図６の初期値生成部１１０と異なるが、構成は同一（図１４参照）である。【０１３３】
図１８は、逆順部分ＣＲＣ生成部３１２の回路構成を示す図である。逆順部分ＣＲＣ生成部３１２，３１４は、同一構成をとるため逆順部分ＣＲＣ生成部３１２を代表して説明する。【０１３４】
図１８において、逆順部分ＣＲＣ生成部３１２は、セレクタ４０１、Ｄフリップフロップ（ＦＦ）４０２、ＥＸＯＲ回路４０３、及びＡＮＤ回路４０４から構成される。【０１３５】
逆順部分ＣＲＣ生成部３１２は、部分ＣＲＣ生成部１１１（図９参照）と同様、２４ビット分のＤフリップフロップ４０２を中心とした構成となっているが、データの生成方向が逆方向である。【０１３６】
図１９は、それぞれの部分ＣＲＣ生成部、すなわち部分ＣＲＣ生成部１１１，逆順部分ＣＲＣ生成部３１２，部分ＣＲＣ生成部１１３，逆順部分ＣＲＣ生成部３１４が計算（担当）する部分ＣＲＣを表にまとめた図である。ここで、ＤＭ｛Ｔ｝(Ｄ)という表記を用いた。ＤＭ｛Ｔ｝(Ｄ)＝ＤＭＴ(Ｄ)＝ＤＴｍｏｄＧ(Ｄ)である。【０１３７】
図１９の表に示すように、回路番号２，４の入力データ順が逆になっており、それに対応して初期値と部分ＣＲＣの生成順が変わっている。【０１３８】
基本原理の[ポイント３]で説明した通り、次の漸化式（１８）に基づきＤＭ｛Ｎ−１＋ｃ−(２Ｍ−１)｝(Ｄ)を初期値として、ＤＭ｛Ｎ−１＋ｃ−(２Ｍ−２)｝(Ｄ)〜ＤＭ｛Ｎ−１＋ｃ−Ｍ｝(Ｄ)の値を順次求めるものである。【０１３９】
【数１３】
2008023684.tif 000015
正順の部分ＣＲＣ生成部１１１，１１３では、Ｔが減少していく方向に算出したのに対し、逆順部分ＣＲＣ生成部３１２，３１４では、Ｔが増加していく方向に算出しているのがわかる。【０１４０】
上述したように、初期値生成部３１０は、実施の形態１の部分ＣＲＣ生成部１１１と同等の構成となる。但し、逆順部分ＣＲＣ生成部３１２で必要とされる初期値は、ＤＭ｛Ｎ−１＋ｃ−Ｍ｝(Ｄ)ではなく、ＤＭ｛Ｎ−１＋ｃ−(２Ｍ−１)｝(Ｄ)であるから、ｌｄ２のトリガを発生するタイミングが異なる。すなわち、Ｉ＝Ｎ−１−(２Ｍ−１)のタイミングでｌｄ２＝１となる。ｌｄ４のタイミングについても同様であり、Ｉ＝０のタイミングでl４＝０となる。【０１４１】
図２０は、初期値生成部３１０の動作を示すタイミングチャートである。並列ＣＲＣ計算回路１００の初期値生成部１００の動作を示すタイミングチャート図１６と比較すると、信号ｌｄ２とｌｄ４に対しトリガが出力されるタイミングが異なることが分かる。【０１４２】
このように、本実施の形態では、実施の形態１の効果に加えてさらに、サブブロックごとにデータの入力順を逆順に入力することができる。したがって、サブブロック分割を行う並列ターボ復号器と組み合わせる場合の親和性が高い。例えば、ターボ複合器でＭａｘ−ｌｏｇ−ＭＡＰ復号を行うとき、ターボ復号器の出力を本並列ＣＲＣ計算回路（並列剰余演算器）３００に直接入力することができる。特に、サブブロック分割を行う並列ターボ復号器と組み合わせた場合に処理遅延を格段に小さくすることができる。【０１４３】
以上の説明は本発明の好適な実施の形態の例証であり、本発明の範囲はこれに限定されることはない。【０１４４】
例えば、上記各実施の形態では、データを４分割する（４並列）の場合を例にとって説明したが、分割数やＣＲＣのビット長さはこれに限定されない。【０１４５】
また、上記実施の形態１では、部分ＣＲＣ生成部１１１は図１０に示したように１クロックサイクルあたり１つの部分ＣＲＣを式（８）により計算するものとしたが、式（８）を繰り返し用いることにより、１クロックサイクルあたり２以上の部分ＣＲＣを計算するようにしても良い。例えば、部分ＣＲＣ生成部１１１は、ＤＭ｛Ｎ−１＋ｃ＋ｉ｝(Ｄ)（ｉは整数）から、２つの部分ＣＲＣ、ＤＭ｛Ｎ−１＋ｃ＋ｉ＋１｝(Ｄ)とＤＭ｛Ｎ−１＋ｃ＋ｉ＋２｝(Ｄ)を出力する。このような構成により、各入力端子１０１〜１０４には１クロックサイクルごとに２ビットのデータを入力することができるようになる。すなわち、データをサブブロック分割した上で、各サブブロックのデータをシリアル・パラレル変換する場合にも、本明細に「ポイント１」「ポイント２」として示した方法を用いて、簡易な構成で並列計算が可能となる。【０１４６】
また、上記実施の形態２では、サブブロック２，４を逆順にしたが、どのサブブロックを逆順にしてもよく、一部のサブブロックのみ逆順としてもよい。【０１４７】
また、本実施の形態では、並列剰余演算器及び並列ＣＲＣ計算回路という名称を用いたが、これは説明の便宜上であり、ＣＲＣ計算回路、誤り訂正回路、誤り訂正方法等であってもよい。【０１４８】
また、本発明を本アルゴリズムによる並列剰余演算器及び並列剰余演算方法が実現できればよく、ハードウェアで構成する場合は勿論のこと、並列剰余演算方法を機能させるためのソフトウェアで実現することも可能である。このソフトウェアはコンピュータで読み取り可能な記録媒体に格納されている。【０１４９】
また、上記各実施の形態の説明に用いた各機能ブロックは、典型的には集積回路であるＬＳＩとして実現される。これらは個別に１チップ化されても良いし、一部又は全てを含むように１チップ化されても良い。ここでは、ＬＳＩとしたが、集積度の違いにより、ＩＣ、システムＬＳＩ、スーパーＬＳＩ、ウルトラＬＳＩと呼称されることもある。また、集積回路化の手法はＬＳＩに限るものではなく、専用回路又は汎用プロセッサで実現しても良い。ＬＳＩ製造後に、プログラムすることが可能なＦＰＧＡ（Field Programmable Gate Array）や、ＬＳＩ内部の回路セルの接続や設定を再構成可能なリコンフィギュラブル・プロセッサーを利用しても良い。さらには、半導体技術の進歩又は派生する別技術によりＬＳＩに置き換わる集積回路化の技術が登場すれば、当然、その技術を用いて機能ブロックの集積化を行っても良い。例えば、バイオ技術の適用等が可能性としてありえる。【０１５０】
２００６年８月２２日出願の特願２００６−２２５９３４の日本出願に含まれる明細書、図面および要約書の開示内容は、すべて本願に援用される。
【産業上の利用可能性】
【０１５１】
本発明に係る並列剰余演算器及び並列剰余演算方法は、ターボ復号器などの出力が並列で入力され、デジタル情報の誤りを検出する通信システムにおいて、従来のＣＲＣ計算回路に代えて使用される新規な並列剰余演算器及び並列剰余演算方法として有用である。例えば、誤り訂正のために畳み込み符号、ターボ符号化等で符号化された送信データを復号するため、受信側で、ビタビ復号器やターボ復号器等の軟出力復号器や伝送誤りの有無を検出するための巡回符号を使用する受信装置や携帯電話等の通信端末装置に用いるに好適である。
【図１】
2008023684.tif 000016
【図２】
2008023684.tif 000017
【図３】
2008023684.tif 000018
【図４】
2008023684.tif 000019
【図５Ａ】
2008023684.tif 000020
【図５Ｂ】
2008023684.tif 000021
【図６】
2008023684.tif 000022
【図７】
2008023684.tif 000023
【図８】
2008023684.tif 000024
【図９】
2008023684.tif 000025
【図１０】
2008023684.tif 000026
【図１１】
2008023684.tif 000027
【図１２】
2008023684.tif 000028
【図１３】
2008023684.tif 000029
【図１４】
2008023684.tif 000030
【図１５】
2008023684.tif 000031
【図１６】
2008023684.tif 000032
【図１７】
2008023684.tif 000033
【図１８】
2008023684.tif 000034
【図１９】
2008023684.tif 000035
【図２０】
2008023684.tif 000036
【手続補正書】
【提出日】平成21年1月20日(2009.1.20)
【手続補正１】
【補正対象書類名】特許請求の範囲
【補正対象項目名】全文
【補正方法】変更
【補正の内容】
【特許請求の範囲】
【請求項１】
入力データが複数のサブブロックに分割されて並列に入力される並列剰余演算器であって、
前記各サブブロックの先頭点に対応する部分剰余を初期値として生成する初期値生成手段と、
前記初期値生成手段から各サブブロックの先頭に対応する部分剰余を初期値として受け取り、残りの部分剰余を所定の漸化式に従って順次生成する部分剰余生成手段と、
前記入力データと、前記部分剰余生成手段から出力される部分剰余の値の論理を計算する論理手段と、
前記論理手段から出力される値を、累積的に加算する累積加算手段と
を備える並列剰余演算器。
【請求項２】
入力データが複数のサブブロックに分割されて並列に入力される並列剰余演算器であって、
前記各サブブロックの最終点に対応する部分剰余を初期値として生成する初期値生成手段と、
前記初期値生成手段から各サブブロックの最終点に対応する部分剰余を初期値として受け取り、残りの部分剰余を所定の漸化式に従って順次生成する逆順部分剰余生成手段と、
前記入力データと、前記逆順部分剰余生成手段から出力される逆順部分剰余の値の論理を計算する論理手段と、
前記論理手段から出力される値を、累積的に加算する累積加算手段と
を備える並列剰余演算器。
【請求項３】
前記初期値生成手段は、長さｎの入力データを長さｎ−ｍとｍのデータ列に分割し、分割された個々のデータ列をサブブロックとするとき、最大次数ｃにおいて定められる多項式Ｇ(Ｄ)の値に応じて、各サブブロックのｉ＝０，ｍにおける先頭点の部分剰余であるＤｎ−ｌ＋cｍｏｄＧ(Ｄ)とＤｎ−ｌ＋c−mｍｏｄＧ(Ｄ)を初期値として生成する請求項１記載の並列剰余演算器。
【請求項４】
前記初期値生成手段は、長さｎの入力データを長さｎ−ｍとｍのデータ列に分割し、分割された個々のデータ列をサブブロックとするとき、最大次数ｃにおいて定められる多項式Ｇ(Ｄ)の値に応じて、各サブブロックのｉ＝ｍ−１，ｎ−１における最終点の部分剰余であるＤｎ−ｌ＋c−（ｍ−１）ｍｏｄＧ(Ｄ)とＤｎ−ｌ＋c−（ｎ−１）ｍｏｄＧ(Ｄ)を初期値として生成する請求項２記載の並列剰余演算器。
【請求項５】
前記部分剰余生成手段は、元のデータ順に従いデータが入力され、
前記Ｄｎ−ｌ＋cｍｏｄＧ(Ｄ)とＤｎ−ｌ＋c−mｍｏｄＧ(Ｄ)を初期値として、ｉ＝１〜ｍ−ｌ及びｉ＝ｍ＋ｌ〜ｎ−ｌに対応する部分剰余を、所定の漸化式により算出する請求項１記載の並列剰余演算器。
【請求項６】
前記逆順部分剰余生成手段は、元のデータ順を逆順にしてデータが入力され、
前記Ｄｎ−ｌ＋c−（ｍ−１）ｍｏｄＧ(Ｄ)とＤｎ−ｌ＋c−（ｎ−１）ｍｏｄＧ(Ｄ)を初期値として、ｉ＝ｍ−２〜０及びｉ＝ｎ−２〜ｍに対応する逆順部分剰余を、所定の漸化式により算出する請求項２記載の並列剰余演算器。
【請求項７】
前記累積加算手段は、ビットごとの排他的論理和により加算する請求項１に記載の並列剰余演算器。
【請求項８】
長さｎの入力データを長さｎ−ｍとｍのデータ列に分割し、分割された個々のデータ列
をサブブロックとするとき、最大次数ｃにおいて定められる多項式Ｇ(Ｄ)の値に応じて、各サブブロックのｉ＝０，ｍにおける先頭点の部分剰余であるＤｎ−ｌ＋cｍｏｄＧ(Ｄ)とＤｎ−ｌ＋c−mｍｏｄＧ(Ｄ)を初期値としてあらかじめ求めるステップと、
前記Ｄｎ−ｌ＋cｍｏｄＧ(Ｄ)とＤｎ−ｌ＋c−mｍｏｄＧ(Ｄ)を初期値として、ｉ＝１〜ｍ−ｌ及びｉ＝ｍ＋ｌ〜ｎ−ｌに対応する部分剰余を、順次算出するステップと
を有する並列剰余演算方法。
【請求項９】
長さｎの入力データを長さｎ−ｍとｍのデータ列に分割し、分割された個々のデータ列をサブブロックとするとき、最大次数ｃにおいて定められる多項式Ｇ(Ｄ)の値に応じて、各サブブロックのｉ＝ｍ−１，ｎ−１における最終点の部分剰余であるＤｎ−ｌ＋c−（ｍ−１）ｍｏｄＧ(Ｄ)とＤｎ−ｌ＋c−（ｎ−１）ｍｏｄＧ(Ｄ)を初期値としてあらかじめ求めるステップと、
前記Ｄｎ−ｌ＋c−（ｍ−１）ｍｏｄＧ(Ｄ)とＤｎ−ｌ＋c−（ｎ−１）ｍｏｄＧ(Ｄ)を初期値として、ｉ＝ｍ−２〜０及びｉ＝ｎ−２〜ｍに対応する逆順部分剰余を、順次算出するステップと
を有する並列剰余演算方法。
【請求項１０】
前記部分剰余を算出するステップでは、
元のデータ順に従いデータを入力し、
前記Ｄｎ−ｌ＋cｍｏｄＧ(Ｄ)とＤｎ−ｌ＋c−mｍｏｄＧ(Ｄ)を初期値として、ｉ＝１〜ｍ−ｌ及びｉ＝ｍ＋ｌ〜ｎ−ｌに対応する部分剰余を、所定の漸化式により算出する請求項８記載の並列剰余演算方法。
【請求項１１】
前記逆順部分剰余を算出するステップでは、
元のデータ順を逆順にしてデータを入力し、
前記Ｄｎ−ｌ＋c−（ｍ−１）ｍｏｄＧ(Ｄ)とＤｎ−ｌ＋c−（ｎ−１）ｍｏｄＧ(Ｄ)を初期値として、ｉ＝ｍ−２〜０及びｉ＝ｎ−２〜ｍに対応する部分剰余を、所定の漸化式により算出する請求項９記載の並列剰余演算方法。
【請求項１２】
さらに、入力データと、前記部分剰余の値の論理を計算するステップと、
前記論理計算された値を、累積的に加算するステップとを有する請求項８記載の並列剰余演算方法。
【請求項１３】
さらに、入力データと、前記逆順部分剰余の値の論理を計算するステップと、
前記論理計算された値を、累積的に加算するステップとを有する請求項９記載の並列剰余演算方法。
【手続補正２】
【補正対象書類名】明細書
【補正対象項目名】全文
【補正方法】変更
【補正の内容】
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、並列剰余演算器及び並列剰余演算方法に関し、例えば、ターボ復号器などの出力が並列で入力され、デジタル情報の誤りを検出する並列剰余演算器及び並列剰余演算方法に関する。
【背景技術】
【０００２】
無線によるパケット通信や、光ディスクなどの記録ディスクなど、さまざまな分野でＣＲＣ（Cyclic Redundancy Check：巡回冗長検査）符号が用いられている。例えば、無線通信システムでは、無線回線を介して通信することから無線伝送路において送信データに誤りが発生する可能性があるので、ＣＲＣを使用した誤り訂正回路を設ける。送信側で送信データ列に基づいてＣＲＣビットを生成し、それを送信データ列の後ろに付加する。ＣＲＣビットを付加したビット列は、畳み込み符号化やターボ符号化などの符号化方式を用いて符号化され、これにより得られる符号化ビット列が送信される。
【０００３】
ＣＲＣ符号の原理については、非特許文献１に詳細に記載されている。
【０００４】
図１は、ＣＲＣ符号の使われ方を説明する図である。
【０００５】
図１において、入力源（ソース）１１からの入力データ列Ａは、ＣＲＣ符号化部１２でＣＲＣ符号化され、送信データ列Ｂとして通信路１３を介して受信側に送信される。通信路１３は、例えば無線伝送路でありビット誤り（ノイズ）Ｅが付加される。受信側では、ビット誤りＥが付加された送信データ列Ｂ’を受信し、ＣＲＣ検査部１４でＣＲＣ検査し、ＣＲＣ検査に基づく受信データＡ’を出力側（シンク）１５に渡す。無線通信システムが、誤り訂正能力が高いターボ符号化とＡＲＱ（Auto Repeat reQuest）とを組み合わせたＨＡＲＱ（Hybrid Auto Repeat reQuest）の場合、ＣＲＣ検査部１４でＣＲＣチェックを行い、誤りの発生状況を検出し、誤りが発生していない場合、データ列Ａの受信データＡ’を出力するとともに、通信相手に送信するＡＣＫ／ＮＡＣＫ信号としてＡＣＫ信号を形成する。これに対して、誤りが発生した場合、受信データを出力せずに、通信相手に送信するＡＣＫ／ＮＡＣＫ信号としてＮＡＣＫ信号を形成する。
【０００６】
より一般的に説明する。
【０００７】
ｎビットの入力データ列をＡ＝[ａ０ａ１…ａｎ−２ａｎ−１]とする。ａ０がＭＳＢ（Most Significant Bit）、すなわち先に送信されるビットでる。ａ０，…，ａｎ−１をそれぞれＧＦ(２)の元（すなわち、値０又は１をとる）とし、ビット列を次式（１）のように多項式で表す。
【０００８】
【数１】
2008023684.tif 000037
入力データ列Ａは、ＣＲＣ符号化され、次式（２）のＢとなる。一般に用いられるＣＲＣ符号化では、ｎビットの入力データ列の後に長さｃのビット列を追加することで行われる。追加されたｃビットをＣＲＣと呼ぶこともある。
【０００９】
Ｂ＝[ａ０ａ１…ａｃ−２ａｃ−１ｒ０ｒ１…ｒｃ−２ｒｃ−１]    …（２）
ＣＲＣの多項式表現を、次式（３）で表すとすると、Ｂの多項式表現は、次式（４）で示される。
【００１０】
【数２】
2008023684.tif 000038
Ｂ(Ｄ)＝Ａ(Ｄ)Ｄｃ＋Ｒ(Ｄ)                        …（４）
ＣＲＣ符号化は、あらかじめ定められたｃ次の多項式Ｇ(Ｄ)に対し、Ｂ(Ｄ)がＧ(Ｄ)で割り切れるようにＲ(Ｄ)が定められる。すなわち、Ａ(Ｄ)ＤｃをＧ(Ｄ)で割った剰余がＲ(Ｄ)である。
【００１１】
上記Ｇ(Ｄ)は生成多項式と呼ばれ、次式（５）で示される。
【００１２】
【数３】
2008023684.tif 000039
以下では、生成多項式の次数ｃをＣＲＣの次数と呼ぶ場合がある。
【００１３】
以上をまとめると、次式（６）になる。Ｑ(Ｄ)はＡ(Ｄ)ＤｃをＧ(Ｄ)で除した商である。
【００１４】
Ｂ(Ｄ)＝Ａ(Ｄ)Ｄｃ＋Ｒ(Ｄ)＝Ｇ(Ｄ)Ｑ(Ｄ)          …（６）
以上のようにしてＣＲＣ符号化されたｎ＋ｃビットが、通信路１３を介して送信される。通信路１３では、ビット誤り（ノイズ）Ｅ(Ｄ)が付加される。
【００１５】
ＣＲＣ検査は、受信値Ｂ’(Ｄ)＝Ｂ(Ｄ)＋Ｅ(Ｄ)がＧ(Ｄ)で割り切れるかどうかを検査することで行われる。受信値にビット誤りがなければ（すなわち、Ｅ(Ｄ)＝０のとき）、Ｂ’(Ｄ)はＧ(Ｄ)で割り切れる。受信値にビット誤りがある場合、Ｅ(Ｄ)がＧ(Ｄ)で割り切れない場合にはＢ’(Ｄ)がＧ(Ｄ)で割り切れなくなる。したがって、通信路でビット誤りが発生したことを検出できる。Ｅ(Ｄ)がＧ(Ｄ)で割り切れる場合、誤りがあることをＣＲＣにより検出できない。しかし、ｃが十分な長さを持っていればその発生確率は低い。ｃとしては、３２〜８といった値がよく用いられる。
【００１６】
図２は、より実際的なシステムに適用したＣＲＣ符号の使われ方を説明する図である。
【００１７】
図２において、情報源（ソース）２１からの入力データＡ(Ｄ)は、ＣＲＣ符号化部２２でＣＲＣ符号化され、ＣＲＣ符号化されたデータＢ(Ｄ)は誤り訂正符号化部２３で送信データＣ(Ｄ)として通信路２４を介して受信側に送信される。送信側では、ＣＲＣ符号化ののち、誤り訂正符号化が行われる。誤り訂正符号化の方法としては、リードソロモン符号、畳み込み符号、ターボ符号、などが用いられる。
【００１８】
通信路２４において、ビット誤り（ノイズ）Ｅが付加されることがある。受信側では、ビット誤りＥが付加された送信データ列Ｃ’(Ｄ)を受信し、誤り訂正復号部２５で誤り訂正の復号を行って送信データＢ’(Ｄ)を出力し、ＣＲＣ検査部２６でＣＲＣ検査し、ＣＲＣ検査に基づく受信データＡ’を出力側（シンク）２７に渡す。受信側では、誤り訂正符号の復号が行われる。これにより、通信路２４で加えられたビット誤りの大部分が取り除
かれる。ＣＲＣ検査部２６によるＣＲＣ検査では、誤り訂正復号で取りきれなかった誤りがあるかどうかを検査する。
【００１９】
（従来例１：逐次ＣＲＣ計算回路）
図３は、一般的によく知られる逐次ＣＲＣ計算回路の構成を示す図である。
【００２０】
図３において、逐次ＣＲＣ計算回路３０は、ＥＸＯＲ（排他的論理和）回路３１と、[０]〜[ｃ−１]のフリップフロップ（ＦＦ）３２と、ＡＮＤ回路３３とから構成される。
【００２１】
図３は、シフトレジスタを用いた一般的な構成であり、入力データ列の先頭から１ｂｉｔずつ毎クロックサイクル入力する。
【００２２】
逐次ＣＲＣ計算回路３０のＣＲＣ符号化では、ａ[ｔ]で示す入力端子に、ａ０〜ａｎ−１を１ビットずつ入力する。すべて入力した後、ｃビットのフリップフロップ（ＦＦ）に保持されている値が、ＣＲＣ演算結果となる。
【００２３】
ＣＲＣ検査では、受信したｎ＋ｃビットのデータＢ’(Ｄ)を１ビットずつ入力した後、フリップフロップに残った値が０かどうかを判定する。又は、Ｂ’(Ｄ)の先頭のｎビットを入力し、フリップフロップに残った値がＢ’(Ｄ)の残りのｃビットと一致するかどうかを判定してもよい。
【００２４】
しかし、この構成では、入力がｎビットの場合、ＣＲＣ符号化に少なくともｎクロックを要し、処理遅延時間が大きいという問題がある。
【００２５】
（従来例２：部分ＣＲＣを算出する方法）
特許文献１には、部分ＣＲＣを算出することで処理遅延時間を短縮する部分ＣＲＣ算出方法が開示されている。
【００２６】
特許文献１では、剰余Ｒ(Ｄ)の計算式を次式（７）のように変形する。
【００２７】
【数４】
2008023684.tif 000040
ここで、Ｄｎ−ｌ＋ｃ−ｉｍｏｄＧ(Ｄ)(ｉ＝０〜ｎ−１)の値（部分ＣＲＣ）をあらかじめ求めておき、入力データをパラレルで一度に入力することで１クロックサイクルでＣＲＣを求めることができる。
【００２８】
図４は、部分ＣＲＣ回路の構成を示す図であり、上記式（７）においてｎ＝１６，ｃ＝２４の場合の部分ＣＲＣ回路を示す。
【００２９】
図４において、部分ＣＲＣ回路４０は、演算対象ビット列Ａ[０]Ａ[１５]入力端子４１と、各ビット列Ａ[０]Ａ[１５]とあらかじめ算出された部分ＣＲＣのＡＮＤをとるＡＮＤ回路４２と、部分ＣＲＣをまとめる加算回路４３とから構成される。
【００３０】
ＡＮＤ回路４２では、あらかじめ算出された部分ＣＲＣの、各演算対象ビット列の有効値を部分ＣＲＣ符号にデコードし、加算回路４３では、演算対象ビット列全体に対するＣＲＣ符号を求める。
【００３１】
しかし、特許文献１に示される並列度ｎの構成では、ｎが大きくなると、回路規模がとても大きくなってしまう。並列度を下げ、データの一部を順次入力していくことも考えられるが、ｉ＝０〜ｎ−１に対する任意の部分ＣＲＣを即座に計算することは回路規模や処理遅延の面から困難である。そこで、すべての部分ＣＲＣをあらかじめ求めておく必要があるが、ｎが大きい場合には、部分ＣＲＣを保持しておくメモリの容量が大きくなってしまい、コストの増大を招く。
【００３２】
（従来例３：サブブロックに分割する方法）
また、特許文献２，３には、データをサブブロックに分割して並列処理を行うサブブロック分割型並列ＣＲＣ回路が開示されている。特許文献２，３では、剰余Ｒ(Ｄ)の計算式を次式（８）のように変形する。
【００３３】
【数５】
2008023684.tif 000041
すなわち、上記式（８）長さｎのデータを、長さｍとｎ−ｍに分割し、(ａ)長さｎ−ｍのＣＲＣ計算と、(ｂ)長さｍのＣＲＣ計算とに分解する。
【００３４】
しかし、このサブブロック分割方法では、(ａ)の結果にＤｍｍｏｄＧ(Ｄ)を乗算したのち、Ｇ(Ｄ)による剰余を計算しなければならない。これらの処理のため、乗算器と剰余計算器が追加で必要となり、回路規模及び処理遅延の増加を招いていた。
【００３５】
最も一般的な並列化方法として、シリアル・パラレル変換型の並列ＣＲＣ回路がある。
【００３６】
図５Ａ及び図５Ｂは、シリアル・パラレル変換型の並列ＣＲＣ回路を示す図である。図５Ａにおいて、Ｓ／Ｐ変換型並列ＣＲＣ回路５０は、Ｓ／Ｐ変換器５１と、並列ＣＲＣ回路５２とから構成される。
【００３７】
Ｓ／Ｐ変換型並列ＣＲＣ回路５０は、図５Ｂに示すように、Ｓ／Ｐ変換器５１により入力をシリアル・パラレル変換し、並列ＣＲＣ回路５２で並列処理によるＣＲＣ計算を行う。並列処理は、例えば１ｂｙｔｅずつ処理する。この並列化方法は、ハード・ソフトいずれにおいても実装及び応用例が多い。
【非特許文献１】今井秀樹著、「符号理論」、電子情報通信学会、１９９０年３月
【特許文献１】特開平８−１４９０１７号公報
【特許文献２】特表２００３−５２３６８２号公報
【特許文献３】特開２００５−６１８８号公報
【発明の開示】
【発明が解決しようとする課題】
【００３８】
しかしながら、このような従来のＣＲＣ計算回路にあっては、以下のような課題がある。
【００３９】
（１）上述したように、逐次ＣＲＣ計算回路は、処理遅延時間が非常に大きく、部分ＣＲＣ回路は、部分ＣＲＣを保持しておくメモリの容量が大きくなりコストの増大を招く。
【００４０】
（２）サブブロック分割型並列ＣＲＣ回路は、以下の点で必要性が高い。
【００４１】
並列ターボデコーダの出力は、サブブロック分割型であるため、サブブロック分割型並列ＣＲＣ回路を適用できれば、メモリを介さずに直接入力可能という利点がある。すなわち、並列ターボ復号器の出力をＣＲＣ計算回路に直接入力するため、並列ＣＲＣ計算回路は、シリアル・パラレル変換型（例えば、先頭から１ｂｙｔｅずつ処理）ではなく、サブブロック分割型（例えば、データ系列を長さＭの小ブロックに分割）である必要がある。したがって、サブブロック分割型並列ＣＲＣ回路は、Ｓ／Ｐ型並列ＣＲＣ回路を使う場合に比べ、インターフェースとなるメモリが不要となり、処理遅延の削減、回路規模・電流の削減につながる。しかしながら、このサブブロック分割型並列ＣＲＣ回路では、サブブロックに分割し並列処理するため、並列処理する複数ＣＲＣ剰余発生器の後段に、乗算器と加算器などの剰余計算器が追加で必要となり、回路規模及び処理遅延の増加を招く。
【００４２】
（３）シリアル・パラレル変換型並列ＣＲＣ回路では、インターフェースメモリが必要となり、このことは、処理遅延の増加をもたらし、ＡＣＫ送信の遅れ、反復停止の遅れによる消費電流増加を招く。
【００４３】
上述したように、サブブロック分割型並列ＣＲＣ回路は、サブブロック分割を行う並列ターボ復号器と組み合わせる場合には、利点が大きいが、従来のサブブロック分割型並列ＣＲＣ回路は、処理遅延・回路規模が大きく、処理遅延・回路規模の小さいＣＲＣ回路が求められている。
【００４４】
本発明の目的は、処理遅延を小さくすることができ、追加の乗算回路・剰余回路を不要にして回路規模を小さくすることができる並列剰余演算器を提供することである。
【課題を解決するための手段】
【００４５】
本発明の並列剰余演算器は、入力データが複数のサブブロックに分割されて並列に入力される並列剰余演算器であって、前記各サブブロックの先頭点に対応する部分剰余を初期値として生成する初期値生成手段と、前記初期値生成手段から各サブブロックの先頭に対応する部分剰余を初期値として受け取り、残りの部分剰余を所定の漸化式に従って順次生成する部分剰余生成手段と、前記入力データと、前記部分剰余生成手段から出力される部分剰余の値の論理を計算する論理手段と、前記論理手段から出力される値を、累積的に加算する累積加算手段とを備える構成を採る。
【００４６】
本発明の並列剰余演算器は、入力データが複数のサブブロックに分割されて並列に入力される並列剰余演算器であって、前記各サブブロックの最終点に対応する部分剰余を初期値として生成する初期値生成手段と、前記初期値生成手段から各サブブロックの最終点に対応する部分剰余を初期値として受け取り、残りの部分剰余を所定の漸化式に従って順次
生成する逆順部分剰余生成手段と、前記入力データと、前記逆順部分剰余生成手段から出力される逆順部分剰余の値の論理を計算する論理手段と、前記論理手段から出力される値を、累積的に加算する累積加算手段とを備える構成を採る。
【００４７】
本発明の並列剰余演算方法は、長さｎの入力データを長さｎ−ｍとｍのデータ列に分割し、分割された個々のデータ列をサブブロックとするとき、最大次数ｃにおいて定められる多項式Ｇ(Ｄ)の値に応じて、 各サブブロックのｉ＝０，ｍにおける先頭点の部分剰余であるＤｎ−ｌ＋cｍｏｄＧ(Ｄ)とＤｎ−ｌ＋c−mｍｏｄＧ(Ｄ)を初期値としてあらかじめ求めるステップと、前記Ｄｎ−ｌ＋cｍｏｄＧ(Ｄ)とＤｎ−ｌ＋c−mｍｏｄＧ(Ｄ)を初期値として、ｉ＝１〜ｍ−ｌ及びｉ＝ｍ＋ｌ〜ｎ−ｌに対応する部分剰余を、順次算出するステップとを有する。
【００４８】
本発明の並列剰余演算方法は、長さｎの入力データを長さｎ−ｍとｍのデータ列に分割し、分割された個々のデータ列をサブブロックとするとき、最大次数ｃにおいて定められる多項式Ｇ(Ｄ)の値に応じて、 各サブブロックのｉ＝ｍ−１，ｎ−１における最終点の部分剰余であるＤｎ−ｌ＋c−（ｍ−１）ｍｏｄＧ(Ｄ)とＤｎ−ｌ＋c−（ｎ−１）ｍｏｄＧ(Ｄ)を初期値としてあらかじめ求めるステップと、前記Ｄｎ−ｌ＋c−（ｍ−１）ｍｏｄＧ(Ｄ)とＤｎ−ｌ＋c−（ｎ−１）ｍｏｄＧ(Ｄ)を初期値として、ｉ＝ｍ−２〜０及びｉ＝ｎ−２〜ｍに対応する逆順部分剰余を、順次算出するステップとを有する。
【発明の効果】
【００４９】
本発明によれば、処理遅延を小さくすることができ、部分ＣＲＣをすべて保存しておく必要が無く、また追加の乗算回路・剰余回路を不要にして回路規模を小さくすることができる。特に、サブブロック分割を行う並列ターボ復号器と組み合わせた場合に処理遅延を格段に小さくすることができる。
【発明を実施するための最良の形態】
【００５０】
以下、本発明の実施の形態について、図面を参照して詳細に説明する。
【００５１】
（基本原理）
まず、本発明の基本原理について説明する。
【００５２】
本発明は、全体構成に関連する[ポイント１]、部分ＣＲＣ生成回路に関連する[ポイント２]、部分ＣＲＣ生成回路（逆順）に関連する[ポイント３]を有する。
【００５３】
[ポイント１]：全体構成に関連して
本発明では、剰余Ｒ(Ｄ)の計算式を次式（９）のように変形する。
【００５４】
【数６】
2008023684.tif 000042
すなわち、上記従来例２（部分ＣＲＣを算出する方法）と同様に、部分ＣＲＣ(Ｄｎ−ｌ＋c−ｉｍｏｄＧ(Ｄ))の和としてＣＲＣを計算するよう式変形し、さらに、上記従来例３（サブブロックに分割する方法）と同様に、長さｎのデータを長さｎ−ｍとｍに分割する。以下、分割された個々のデータ列をサブブロックと呼ぶことにする。入力データは、上記式（９）中(a)に対応するａ０〜ａm−ｌと、(b)に対応するａm〜ａn−ｌに分割され、それぞれを並列に計算することで高速計算を実現する。
【００５５】
このとき、本発明では、次のようにして部分剰余（部分ＣＲＣ）を算出する。ここで、入力データは、上記式（９）中(a)に対応するサブブロック１は、ａ０から１ビットずつ順に、ａm−ｌまで、上記式（９）中(b)に対応するサブブロック２は、ａmから１ビットずつ順に、ａn−ｌまで、それぞれ与えられる（入力される）ものとする。
[手順１]  ｉ＝０，ｍにおける部分ＣＲＣの値（すなわち、サブブロックの先頭点における部分ＣＲＣ）Ｄｎ−ｌ＋cｍｏｄＧ(Ｄ))、Ｄｎ−ｌ＋c−mｍｏｄＧ(Ｄ))をあらかじめ求めておく。
[手順２]  上記の２つの値を初期値として、ｉ＝１〜ｍ−ｌ及びｉ＝ｍ＋ｌ〜ｎ−ｌに対応する部分ＣＲＣを、順次算出する。
【００５６】
上記のような計算方法をとったので、本発明のサブブロック分割型並列ＣＲＣ回路は、（１）部分ＣＲＣをすべて保存しておく必要が無く、（２）追加の乗算回路・剰余回路が
不要のため、小型・低遅延という特徴がある。
【００５７】
[ポイント２]：部分ＣＲＣ生成回路に関連して
上記、サブブロックの先頭点における部分ＣＲＣを元に、その他の部分ＣＲＣを順次求める方法について、好適な計算方法について説明する。
【００５８】
生成多項式を次式（１０）としたとき、通常用いられるＣＲＣの生成多項式は、最低次の項の係数gc−１の値が１である、という特徴がある。
【００５９】
【数７】
2008023684.tif 000043
この特徴を利用すると、次式（１１）に示す漸化式により、ＤTｍｏｄＧ(Ｄ)の値からＤT−１ｍｏｄＧ(Ｄ)の値を容易に求めることができる。
【００６０】
【数８】
2008023684.tif 000044
以上から、次の手順により、上記[ポイント１]で述べた並列ＣＲＣ計算を効率よく実現できる。
[手順１’]  ＤＭｎ−ｌ＋ｃ(Ｄ)＝Ｄｎ−ｌ＋cｍｏｄＧ(Ｄ)及びＤＭｎ−ｌ＋ｃ−ｍ(Ｄ)＝Ｄｎ−ｌ＋c−ｍｍｏｄＧ(Ｄ)をあらかじめ求めておく。
[手順２’]  ＤＭｎ−ｌ＋ｃ(Ｄ)を元に、ｉ＝１〜ｍ−１に対応する部分ＣＲＣ(ＤＭｎ−ｌ＋ｃ−ｌ(Ｄ)〜ＤＭｎ−ｌ＋ｃ−（ｍ−ｌ）(Ｄ)）及び、ｉ＝ｍ＋１〜ｎ−１に対応する部分ＣＲＣ(ＤＭｎ−ｌ＋ｃ−（ｍ＋ｌ）(Ｄ)〜ＤＭｎ−ｌ＋ｃ−ｎ(Ｄ)）を、順次求める。
【００６１】
上記のように、部分ＣＲＣをシフトレジスタを用いて順次計算する方法をとったので、本発明のサブブロック分割型並列ＣＲＣ回路は、ｍｏｄＧ(Ｄ)上で定義される多項式の除算を行うことなく、小型の回路で部分ＣＲＣを算出することができる。
【００６２】
[ポイント３]：部分ＣＲＣ生成回路（逆順）に関連して
上記では、各サブブロックのデータは、元のデータ順に従い順序良く入力する（例えば
ａ０〜ａｍ−ｌ）としたが、逆順（例えばａｍ−ｌ〜ａ０）に入力するような並列ＣＲＣ計算回路も実現できる。
【００６３】
すなわち、下記の算出式（１２）において、サブブロック１では、ａｍ−ｌ〜ａ０の順に、サブブロック２では、ａｎ−ｌ〜ａｍの順にデータを入力する。これは、ターボ復号器の出力を並列ＣＲＣ計算器に直接入力するような場合に特に有効である。
【００６４】
【数９】
2008023684.tif 000045
部分ＣＲＣの生成手順は次の通りである。
[手順１]  ｉ＝ｍ−ｌ，ｎ−ｌにおける部分ＣＲＣの値（すなわち、サブブロックの最終点における部分ＣＲＣ）Ｄｎ−ｌ＋c−（ｍ−ｌ）ｍｏｄＧ(Ｄ)、Ｄｎ−ｌ＋c−（ｎ−ｌ）ｍｏｄＧ(Ｄ)をあらかじめ求めておく。
[手順２]  上記の２つの値を初期値として、ｉ＝ｍ−２〜０及びｉ＝ｎ−２〜ｍに対応する部分ＣＲＣを、順次算出する。
【００６５】
好適な方法では、次の漸化式（１３）を用いると良い。
【００６６】
【数１０】
2008023684.tif 000046
上記のように、部分ＣＲＣを逆順に順次生成する方法をとったので、本発明のサブブロック分割型並列ＣＲＣ回路は、データが（部分的に）逆順になっている場合にも、並べ替え操作を行うことなく、ＣＲＣ計算が行えるようになった。その結果、並べ替え操作のための処理遅延をなくすことができた。
【００６７】
（実施の形態１）
図６は、上記基本原理に基づく本発明の実施の形態１に係る並列剰余演算器の全体構成を示すブロック図である。本実施の形態は、上記[ポイント１]及び[ポイント２]に対応する例である。「ポイント」の説明では、データを２分割する（２並列）例を示したが、実施の形態１では、４並列の場合を例として説明する。すなわち、長さｎの入力データをｉ＝０〜ｍ−１、ｉ＝ｍ〜２ｍ−１、ｉ＝２ｍ〜３ｍ−１、ｉ＝３ｍ〜ｎ―１の４つのサブブロックに分割する。また、ＣＲＣの長さを２４ビット（ｃ＝２４）とした。
【００６８】
図６において、並列ＣＲＣ計算回路（並列剰余演算器）１００は、入力端子１０１〜１０４（入力端子<１>〜<４>）、初期値生成部１１０、部分ＣＲＣ生成部１１１〜１１４（部分ＣＲＣ生成部<１>〜<４>）、ＡＮＤ部１２１〜１２４（ＡＮＤ部<１>〜<４>）、及び累積加算部１３０を備えて構成される。
【００６９】
初期値生成部１１０は、部分ＣＲＣ生成部１１１〜１１４に入力する初期値Ｉ１〜Ｉ４（初期値<１>〜<４>）を生成する。具体的には、各サブブロックのｉ＝０，ｍ，２ｍ，３ｍにおける先頭点の部分ＣＲＣ（部分剰余）であるＤｎ−ｌ＋cｍｏｄＧ(Ｄ)Ｄｎ−ｌ＋c−mｍｏｄＧ(Ｄ)とＤｎ−ｌ＋c−２mｍｏｄＧ(Ｄ)とＤｎ−ｌ＋c−３mｍｏｄＧ(Ｄ)を初期値として生成する。初期値生成部１１０の実装方法については、図１４乃至図１６により後述する。
【００７０】
部分ＣＲＣ生成部１１１〜１１４（部分ＣＲＣ生成部<１>〜<４>）は、それぞれのサブブロックの先頭に対応する部分ＣＲＣを初期値として初期値生成部１１０から受け取り、残りの部分ＣＲＣを漸化式に基づき順次生成する。部分ＣＲＣ生成部１１１〜１１４の構成及び動作については、図８乃至図１０により後述する。
【００７１】
ＡＮＤ部１２１〜１２４（ＡＮＤ部<１>〜<４>）は、入力端子１０１〜１０４から入力された１ビットと、部分ＣＲＣ生成部１１１〜１１４から出力された２４ビットの値のＡＮＤ（論理積）を計算する。なお、部分ＣＲＣの値の論理を計算する論理回路であればよく、ＡＮＤ（論理積）には限定されない。ＡＮＤ部１２１〜１２４の構成及び動作については、図１１及び図１２により後述する。
【００７２】
累積加算部１３０は、ＡＮＤ部１２１〜１２４から出力される値を、累積的に加算する。この加算は、ビットごとの排他的論理和（ＥＸＯＲ）である。累積加算部１３０の構成及び動作については、図１３により後述する。
【００７３】
以下、上述のように構成された並列剰余演算器の動作について説明する。まず、並列ＣＲＣ計算回路１００の全体の動作タイミングについて述べる。
【００７４】
本実施の形態では、データを４分割する４並列の場合を例に採る。また、ＣＲＣの長さを２４ビット(ｃ＝２４)としている。
【００７５】
入力データの長さをＮ[ビット]とし、サブブロック１〜３の長さをＭ[ビット]とし、サブブロック４のサイズを残りのＮ−３Ｍ[ビット]とするようにデータを分割した。この分割方法は一例であり、どのように定めてもよい。
【００７６】
図７は、データの入出力を示すタイミングチャートであり、入力データをＡ[ｎ−１：０]のように表記した。また、図７中、ｔは時刻を表す。図６中の信号ｔは、明記していない。
【００７７】
入力端子１０１には、ａ１に示すサブブロック１のデータ（Ａ[０]〜Ａ[Ｍ−１]）が、Ａ[０]を先頭に１ビットずつ入力される。入力端子１０２には、ａ２に示すサブブロック２のデータ（Ａ[Ｍ]〜Ａ[２Ｍ−１]）が、Ａ[Ｍ]を先頭に１ビットずつ入力される。入力端子１０３，１０４も同様である。なお、上記の例では、サブブロック４のサイズは他のサブブロックと異なる（端数のため、他より１ビット少ない）とした。そこで、図７のａ４に示すように、時刻Ｍ−１には、入力端子１０４には０を入力するようにした。
【００７８】
すべてのデータが入力されると、所望のＣＲＣの値がＣＲＣ出力端子（ｒ）から出力される。本実施の形態では、すべての入力が完了した後も、入力端子の値を０に保持している限り、出力端子（ｒ）に所望のＣＲＣの値が保持されるようになっている。
【００７９】
次に、並列ＣＲＣ計算回路１００の個々のモジュールについて説明する。
【００８０】
〔部分ＣＲＣ生成部１１１〜１１４〕
図８は、部分ＣＲＣ生成部１１１〜１１４が計算（担当）する部分ＣＲＣを表にまとめた図である。ここで、ＤＭ｛Ｔ｝(Ｄ)という表記を用いた。ＤＭ｛Ｔ｝(Ｄ)＝ＤＭＴ(Ｄ)＝ＤＴｍｏｄＧ(Ｄ)である。
【００８１】
部分ＣＲＣ生成部１１１〜１１４（部分ＣＲＣ生成部<１>〜<４>）は、それぞれのサブブロックの先頭（０、Ｍ、２Ｍ、３Ｍ）に対応する部分ＣＲＣを初期値として初期値生成回路１１０から受け取り、残りの部分ＣＲＣを前述した漸化式（１１）に基づき順次生成する。
【００８２】
例えば、図８の表において、回路番号１の部分ＣＲＣ生成部１１１は、入力データ番号０〜Ｍ−１、初期値をＤＭ｛Ｎ−１＋ｃ｝(Ｄ)とするとき、生成する部分ＣＲＣはＤＭ｛Ｎ−１＋ｃ−１｝(Ｄ)〜ＤＭ｛Ｎ−１＋ｃ−（Ｍ−１）｝(Ｄ)である。同様に、部分ＣＲＣ生成部１１２〜１１４は、それぞれのサブブロックの先頭（Ｍ、２Ｍ、３Ｍ）に対応する部分ＣＲＣを初期値として残りの部分ＣＲＣを前記式（１１）に基づき順次生成する。
【００８３】
次に、部分ＣＲＣ生成部１１１を例に採り、さらに詳細に説明する。
【００８４】
図９は、部分ＣＲＣ生成部１１１の回路構成を示す図である。部分ＣＲＣ生成部１１１〜１１４は、同一構成をとるため部分ＣＲＣ生成部１１１を代表して説明する。
【００８５】
図９において、部分ＣＲＣ生成部１１１は、セレクタ２０１、Ｄフリップフロップ（ＦＦ）２０２、ＥＸＯＲ回路２０３、及びＡＮＤ回路２０４から構成される。
【００８６】
部分ＣＲＣ生成部１１１は、２４ビット分のＤフリップフロップ２０２を中心とした構成となっている。なお、フリップフロップが数珠繋ぎになっている構成はしばしばシフトレジスタとも呼ばれる。
【００８７】
Ｉ１[２３：０]は初期値であり、ｇ[２３：０]は生成多項式を表す値である。例えば、生成多項式が次式（１４）で定義されるとき、
ｇ[０]＝ｇ[１７]＝ｇ[１８]＝ｇ[２２]＝ｇ[２３]＝１，
ｇ[１]＝ｇ[２]＝...＝ｇ[１５]＝ｇ[１６]＝ｇ[１９]＝ｇ[２０]＝ｇ[２１]＝０
と定める。ここで、ｇ[ｉ]は、Ｄｃ−ｉ−１の係数である。Ｄｃの係数は常に１であるから、ｇ[−１]を定義する必要はない。
【００８８】
Ｇ(Ｄ)＝Ｄ２４＋Ｄ２３＋Ｄ６＋Ｄ５＋Ｄ＋１                …（１４）
１６進数で表記すると、
ｇ＝Ｃ６０００１Ｈ
である。
【００８９】
ｐ１[２３：０]は、生成された部分ＣＲＣである。
【００９０】
次に、部分ＣＲＣ生成部１１１の動作を説明する。
【００９１】
図１０は、部分ＣＲＣ生成部１１１の動作を示すタイミングチャートである。図１０中、ｌｄは制御信号で、ｌｄ＝１のとき、初期値Ｉ１の値がシフトレジスタにロードされる。ここで、Ｉ１の値は、具体的には、図８表に示した通りＤＭ｛Ｎ−１＋ｃ｝(Ｄ)である。図１０のタイミングチャートでは、見易さのためＮ−１＋ｃ＝９８であるとした。
【００９２】
すると、時刻ｔ＝０には、ロードされた値そのものがＡ[０]に対応する部分ＣＲＣとして出力される。同時に、部分ＣＲＣ生成部１１１内部では、次のＤＭ[９７]の値が漸化式
に基づき算出される。
【００９３】
回路図の信号名に従うと、計算式は次式（１５）のようになる。なお、ｐ１’は更新後の（例えばＤＭ[９７]）、ｐ１は更新前の（例えばＤＭ[９８]）シフトレジスタの内容である。
【００９４】
ｐ１’[２３：０]＝｛ｐ１[２２：０]，０｝＋ｐ１[２３]＊｛ｇ[２２：０]，１｝
…（１５）
上記式（１５）中の＋はビットごとの排他的論理和（ＥＸＯＲ）、＊は論理積（ＡＮＤ）である。また、｛ｐ１[２２：０]，０｝という表記は、シフト操作を表す。すなわち、ｐ１の値を１ビット分上位方向にシフトし、ＬＳＢに０を挿入することを意味する。｛ｇ[２２：０]，１｝は、同様にシフト操作であるが、ＬＳＢに１を挿入することを意味する。
【００９５】
以上のように、並列ＣＲＣ計算回路１００の部分ＣＲＣ生成部１１１〜１１４は、シフトレジスタと、ビットごとのＡＮＤ・ＥＸＯＲという簡易な構成のみで、入力データに合わせて適時必要な部分ＣＲＣを算出することができる。
【００９６】
〔ＡＮＤ部１２１〜１２４〕
ＡＮＤ部１２１〜１２４（ＡＮＤ部<１>〜<４>）は、入力端子１０１〜１０４から入力された１ビットと、上記部分ＣＲＣ生成部１１１〜１１４から出力された２４ビットの値のＡＮＤ（論理積）を計算する。
【００９７】
図１１は、ＡＮＤ部１２１の回路構成を示す図である。ＡＮＤ部１２１〜１２４は、同一構成をとるためＡＮＤ部１２１を代表して説明する。
【００９８】
図１１において、ＡＮＤ部１２１は、入力端子１０１から入力された１ビットと、部分ＣＲＣ生成部１１１〜１１４から出力された２４ビットの値のＡＮＤを計算するＡＮＤ回路２１１から構成される。
【００９９】
図１１に示すＡＮＤ部１２１では、入力端子１０１から入力された１ビットと、部分ＣＲＣ生成部１１１〜１１４から出力された２４ビットの値のＡＮＤを計算する。すなわち、次式（１５）において、ａｉとＤｎ−ｌ＋ｃ−ｉｍｏｄＧ(Ｄ)の積をとる操作に相当する。
【０１００】
【数１１】
2008023684.tif 000047
図１２は、ＡＮＤ部１２１の動作を示すタイミングチャートである。図１２において、時刻を表すｔは、前記図１０のｔと共通である。すなわち、部分ＣＲＣ生成部１１１〜１１４では、入力データと対応付けられるべき部分ＣＲＣをタイミング良く生成しているのである。
【０１０１】
〔累積加算部１３０〕
図１３は、累積加算部１３０の回路構成を示す図である。
【０１０２】
図１３において、累積加算部１３０は、ＥＸＯＲ回路２１１、フリップフロップ（ＦＦ）２２２、及びスイッチ回路２２３から構成される。
【０１０３】
累積加算部１３０では、ＡＮＤ部<１>〜<４>から出力される値を、累積的に加算していく。ここで、加算はビットごとの排他的論理和（ＥＸＯＲ）である。すなわち、ｉ＝０〜２３に対し、次式（１６）に示す演算を行う。
【０１０４】
ｓ’[ｉ]＝ｓ[ｉ] ＥＸＯＲ ｑ１[ｉ] ＥＸＯＲ ｑ２[ｉ] ＥＸＯＲ ｑ３[ｉ] ＥＸＯＲ ｑ４[ｉ]                                        …（１６）
上記式（１６）中、ｓは更新前のフリップフロップの値、ｓ’は更新後のフリップフロップの値である。
【０１０５】
〔初期値生成部１１０〕
初期値生成部１１０の実装方法について説明する。
【０１０６】
サブブロックサイズＭと生成多項式があらかじめ定められている場合は、必要なＤｎ＋IｍｏｄＧ(Ｄ)の値をあらかじめ求めておき、メモリ（ＲＡＭやＲＯＭ）に保存しておけばよい。とりうるＩの種類は少ないので、メモリ容量は少なくてよい。
【０１０７】
本実施の形態では、サブブロックサイズＭが固定値であるとすれば、ＤＭ｛Ｎ−１＋ｃ｝(Ｄ)、ＤＭ｛Ｎ−１＋ｃ−Ｍ｝(Ｄ)、ＤＭ｛Ｎ−１＋ｃ−２Ｍ｝(Ｄ)、ＤＭ｛Ｎ−１＋ｃ−３Ｍ｝(Ｄ)の４つの値のみ求めておけばよいので、メモリ容量は２４ビット×４通り＝９６ビットのみでよい。
【０１０８】
また、サブブロックサイズＭや生成多項式が変更される場合にも、変更される度に、ＣＰＵやＤＳＰを用いてソフトウェアにより値を求め、ＲＡＭに保存すればよい。
【０１０９】
Ｄｎ＋IｍｏｄＧ(Ｄ)（Ｉ＝０〜Ｎ−１）は、次の漸化式（１７）により求めることができる。Ｔ＝ｃ＋Ｉ，Ｉ＝０〜Ｎ−１である。
【０１１０】
【数１２】
2008023684.tif 000048
ここで、ＤｃｍｏｄＧ(Ｄ)＝Ｇ(Ｄ)−Ｄｃである。
【０１１１】
上記の初期値生成を高速に行う必要がある場合には、次に示すようなハードウェアを用いるとよい。
【０１１２】
図１４は、初期値生成部１１０の構成を示すブロック図である。
【０１１３】
図１４において、初期値生成部１１０は、初期値候補生成部２３０、データ取得タイミング生成部２３１、データ取得部２４１〜２４４（データ取得部<１>〜<４>）、及び初期値記憶部２５１〜２５４（初期値記憶部<１>〜<４>）を備えて構成される。
【０１１４】
図１５は、上記初期値候補生成部２３０の回路構成を示す図である。
【０１１５】
図１５において、初期値候補生成部２３０は、セレクタ２６１、フリップフロップ（ＦＦ）２６２、ＥＸＯＲ回路２６３、及びＡＮＤ回路２６４から構成される。
【０１１６】
初期値候補生成部２３０は、Ｄｎ＋IｍｏｄＧ(Ｄ)の値をＩ＝０〜Ｎ−１まで順次求める。内部構成は、図１５の通りである。
【０１１７】
図１６は、初期値生成部１１０の動作を示すタイミングチャートである。
【０１１８】
データ取得部２４１（データ取得部<１>）は、部分ＣＲＣ生成部１１１（図６参照）で使用する初期値ＤＭ｛Ｎ−１＋ｃ｝(Ｄ)を取得し、初期値記憶部２５１（初期値記憶部<１>）に保存する。すなわち、データ取得タイミング生成部２３１は、図１６に示すように、初期値候補生成部２３０がＤＭ｛Ｎ−１＋ｃ｝(Ｄ)を出力したときにｌｄ１にトリガ信号を送る。データ取得部２４１は、ｌｄ１のトリガ信号に応じて初期値候補生成部２３０の出力を取得することにより、初期値記憶部１に格納すべき値ＤＭ｛Ｎ−１＋ｃ｝を取得することができる。
【０１１９】
同様に、ＤＭ｛Ｎ−１＋ｃ−Ｍ｝(Ｄ)が出力されるタイミングでｌｄ２にトリガ信号が出力され、ＤＭ｛Ｎ−１＋ｃ−２Ｍ｝(Ｄ)が出力されるタイミング(Ｉ＝j＝Ｎ−１−２Ｍ)でｌｄ３にトリガ信号が出力され、ＤＭ｛Ｎ−１＋ｃ−３Ｍ｝(Ｄ)が出力されるタイミング(Ｉ＝k＝Ｎ−１−３Ｍ)でｌｄ４にトリガ信号が出力される。
【０１２０】
以上のように、本実施の形態によれば、並列ＣＲＣ計算回路１００は、入力データが複数のサブブロックに分割されて並列に入力される入力端子１０１〜１０４、各サブブロックの先頭点に対応する部分ＣＲＣを初期値として生成する初期値生成部１１０、各サブブロックの先頭に対応する部分ＣＲＣを初期値として受け取り、残りの部分ＣＲＣを所定の漸化式に従って順次生成する部分ＣＲＣ生成部１１１〜１１４、部分ＣＲＣの値の論理積を計算するＡＮＤ部１２１〜１２４、及びＡＮＤ部１２１〜１２４から出力される値を累積的に加算する累積加算部１３０を備える。部分ＣＲＣ生成では、ｍ番目の入力の次数（ｎ−１−ｍ）に生成多項式の次数ｃを足した次数（ｉ＝ｎ−１−ｍ＋ｃ）について示される剰余Ｒ(Ｄ)の計算式を、部分ＣＲＣ(Ｄｎ−ｌ＋c−ｉｍｏｄＧ(Ｄ))の和で示される式に変形して、各サブブロックの先頭点に対応する部分ＣＲＣを生成している。これにより、本実施の形態では、処理遅延を小さくすることができ、追加の乗算回路・剰余回路を不要にして回路規模を小さくすることができる。具体的な効果は以下の通りである。
【０１２１】
（１）従来構成では、分割した入力データのＣＲＣを求めてから合成していたので、追加の乗算回路・剰余回路が必要となり、回路規模や処理遅延の増大を招いていた。本実施の形態では、並列度に応じた個数の部分ＣＲＣ生成部１１１〜１１４を設けることにより、簡易な構成でサブブロック分割型の並列ＣＲＣ計算を行うことができる。また、従来の乗算回路の代わりにＡＮＤ回路が使用できるので遅延が小さい、さらに、最終段に追加の剰余計算回路が不要となり、遅延及び回路規模が小さい利点がある。
【０１２２】
（２）従来例２のように従来構成では、あらかじめ部分ＣＲＣを求めておく必要があったため、入力データのサイズに比例して、記憶容量の増加を招いていた。これに対し、本実施の形態では、部分ＣＲＣ生成部１１１〜１１４は、初期値を元に順次新たな値を生成するようにしたので、入力データのサイズにかかわらない回路規模・記憶容量で部分ＣＲＣを算出できる。
【０１２３】
（３）本実施の形態では、部分ＣＲＣをシフトレジスタを用いて順次計算する方法をと
っているので、ｍｏｄＧ(Ｄ)上で定義される多項式の除算を行うことなく、小型の回路で部分ＣＲＣを算出できる。
【０１２４】
このように、サブブロック分割型並列ＣＲＣ回路の新しい構成を実現することができた。ターボ復号器と組み合わせて用いる場合に、処理遅延を少なくし、ＡＣＫ／ＮＡＣＫ送信までの遅延を短縮することができる。ターボ符号の反復復号を行う場合に、反復ごとに即座にＣＲＣ判定ができるので、復号を早期に停止し、消費電力を低減できる。ターボ復号器とＣＲＣ計算回路の間のインターフェースメモリへのアクセスを不要とできるので、消費電力を低減できる。
【０１２５】
以上のように、特に、サブブロック分割を行う並列ターボ復号器と組み合わせた場合に処理遅延を格段に小さくすることができる。ターボ符号の種別を問わず、汎用に適用可能であり、実施も容易である。
【０１２６】
（実施の形態２）
図１７は、本発明の実施の形態２に係る並列剰余演算器の全体構成を示すブロック図である。図６と同一構成部分には同一符号を付している。
【０１２７】
本実施の形態は、基本原理で述べた[ポイント３]に対応する例である。[ポイント３]では、サブブロックごとにデータ入力順を逆順にする例について述べた。データを４分割する４並列において、サブブロック<２>とサブブロック<４>を逆順にする場合を例として説明する。
【０１２８】
図１７において、並列ＣＲＣ計算回路（並列剰余演算器）３００は、入力端子１０１〜１０４（入力端子<１>〜<４>）、初期値生成部３１０、部分ＣＲＣ生成部１１１，１１３（部分ＣＲＣ生成部<１>，<３>）、逆順部分ＣＲＣ生成部３１２，３１４（逆順部分ＣＲＣ生成部<２>，<４>）、ＡＮＤ部１２１〜１２４（ＡＮＤ部<１>〜<４>）、及び累積加算部１３０を備えて構成される。
【０１２９】
図１７の並列ＣＲＣ計算回路３００は、サブブロックサイズをＭとし、入力端子１０２，１０４についてのみデータの入力順を逆にした例である。
【０１３０】
構成上の特徴は、次の通りである。
【０１３１】
図６の並列ＣＲＣ計算回路１００と比較して、部分ＣＲＣ生成部１１２，１１４を、それぞれ逆順部分ＣＲＣ生成部３１２，３１４に変更した。また、逆順部分ＣＲＣ生成回路３１２，３１４に入力する初期値を変更した。このため、初期値生成部３１０で生成する初期値は、図６の初期値生成部１１０と異なるが、構成は同一（図１４参照）である。
【０１３２】
図１８は、逆順部分ＣＲＣ生成部３１２の回路構成を示す図である。逆順部分ＣＲＣ生成部３１２，３１４は、同一構成をとるため逆順部分ＣＲＣ生成部３１２を代表して説明する。
【０１３３】
図１８において、逆順部分ＣＲＣ生成部３１２は、セレクタ４０１、Ｄフリップフロップ（ＦＦ）４０２、ＥＸＯＲ回路４０３、及びＡＮＤ回路４０４から構成される。
【０１３４】
逆順部分ＣＲＣ生成部３１２は、部分ＣＲＣ生成部１１１（図９参照）と同様、２４ビット分のＤフリップフロップ４０２を中心とした構成となっているが、データの生成方向が逆方向である。
【０１３５】
図１９は、それぞれの部分ＣＲＣ生成部、すなわち部分ＣＲＣ生成部１１１，逆順部分ＣＲＣ生成部３１２，部分ＣＲＣ生成部１１３，逆順部分ＣＲＣ生成部３１４が計算（担当）する部分ＣＲＣを表にまとめた図である。ここで、ＤＭ｛Ｔ｝(Ｄ)という表記を用いた。ＤＭ｛Ｔ｝(Ｄ)＝ＤＭＴ(Ｄ)＝ＤＴｍｏｄＧ(Ｄ)である。
【０１３６】
図１９の表に示すように、回路番号２，４の入力データ順が逆になっており、それに対応して初期値と部分ＣＲＣの生成順が変わっている。
【０１３７】
基本原理の[ポイント３]で説明した通り、次の漸化式（１８）に基づきＤＭ｛Ｎ−１＋ｃ−(２Ｍ−１)｝(Ｄ)を初期値として、ＤＭ｛Ｎ−１＋ｃ−(２Ｍ−２)｝(Ｄ)〜ＤＭ｛Ｎ−１＋ｃ−Ｍ｝(Ｄ)の値を順次求めるものである。
【０１３８】
【数１３】
2008023684.tif 000049
正順の部分ＣＲＣ生成部１１１，１１３では、Ｔが減少していく方向に算出したのに対し、逆順部分ＣＲＣ生成部３１２，３１４では、Ｔが増加していく方向に算出しているのがわかる。
【０１３９】
上述したように、初期値生成部３１０は、実施の形態１の部分ＣＲＣ生成部１１１と同等の構成となる。但し、逆順部分ＣＲＣ生成部３１２で必要とされる初期値は、ＤＭ｛Ｎ−１＋ｃ−Ｍ｝(Ｄ)ではなく、ＤＭ｛Ｎ−１＋ｃ−(２Ｍ−１)｝(Ｄ)であるから、ｌｄ２のトリガを発生するタイミングが異なる。すなわち、Ｉ＝Ｎ−１−(２Ｍ−１)のタイミングでｌｄ２＝１となる。ｌｄ４のタイミングについても同様であり、Ｉ＝０のタイミングでl４＝０となる。
【０１４０】
図２０は、初期値生成部３１０の動作を示すタイミングチャートである。並列ＣＲＣ計算回路１００の初期値生成部１００の動作を示すタイミングチャート図１６と比較すると、信号ｌｄ２とｌｄ４に対しトリガが出力されるタイミングが異なることが分かる。
【０１４１】
このように、本実施の形態では、実施の形態１の効果に加えてさらに、サブブロックごとにデータの入力順を逆順に入力することができる。したがって、サブブロック分割を行う並列ターボ復号器と組み合わせる場合の親和性が高い。例えば、ターボ複合器でＭａｘ−ｌｏｇ−ＭＡＰ復号を行うとき、ターボ復号器の出力を本並列ＣＲＣ計算回路（並列剰余演算器）３００に直接入力することができる。特に、サブブロック分割を行う並列ターボ復号器と組み合わせた場合に処理遅延を格段に小さくすることができる。
【０１４２】
以上の説明は本発明の好適な実施の形態の例証であり、本発明の範囲はこれに限定されることはない。
【０１４３】
例えば、上記各実施の形態では、データを４分割する（４並列）の場合を例にとって説明したが、分割数やＣＲＣのビット長さはこれに限定されない。
【０１４４】
また、上記実施の形態１では、部分ＣＲＣ生成部１１１は図１０に示したように１クロックサイクルあたり１つの部分ＣＲＣを式（８）により計算するものとしたが、式（８）を繰り返し用いることにより、１クロックサイクルあたり２以上の部分ＣＲＣを計算するようにしても良い。例えば、部分ＣＲＣ生成部１１１は、ＤＭ｛Ｎ−１＋ｃ＋ｉ｝(Ｄ)（
ｉは整数）から、２つの部分ＣＲＣ、ＤＭ｛Ｎ−１＋ｃ＋ｉ＋１｝(Ｄ)とＤＭ｛Ｎ−１＋ｃ＋ｉ＋２｝(Ｄ)を出力する。このような構成により、各入力端子１０１〜１０４には１クロックサイクルごとに２ビットのデータを入力することができるようになる。すなわち、データをサブブロック分割した上で、各サブブロックのデータをシリアル・パラレル変換する場合にも、本明細に「ポイント１」「ポイント２」として示した方法を用いて、簡易な構成で並列計算が可能となる。
【０１４５】
また、上記実施の形態２では、サブブロック２，４を逆順にしたが、どのサブブロックを逆順にしてもよく、一部のサブブロックのみ逆順としてもよい。
【０１４６】
また、本実施の形態では、並列剰余演算器及び並列ＣＲＣ計算回路という名称を用いたが、これは説明の便宜上であり、ＣＲＣ計算回路、誤り訂正回路、誤り訂正方法等であってもよい。
【０１４７】
また、本発明を本アルゴリズムによる並列剰余演算器及び並列剰余演算方法が実現できればよく、ハードウェアで構成する場合は勿論のこと、並列剰余演算方法を機能させるためのソフトウェアで実現することも可能である。このソフトウェアはコンピュータで読み取り可能な記録媒体に格納されている。
【０１４８】
また、上記各実施の形態の説明に用いた各機能ブロックは、典型的には集積回路であるＬＳＩとして実現される。これらは個別に１チップ化されても良いし、一部又は全てを含むように１チップ化されても良い。ここでは、ＬＳＩとしたが、集積度の違いにより、ＩＣ、システムＬＳＩ、スーパーＬＳＩ、ウルトラＬＳＩと呼称されることもある。また、集積回路化の手法はＬＳＩに限るものではなく、専用回路又は汎用プロセッサで実現しても良い。ＬＳＩ製造後に、プログラムすることが可能なＦＰＧＡ（Field Programmable Gate Array）や、ＬＳＩ内部の回路セルの接続や設定を再構成可能なリコンフィギュラブル・プロセッサーを利用しても良い。さらには、半導体技術の進歩又は派生する別技術によりＬＳＩに置き換わる集積回路化の技術が登場すれば、当然、その技術を用いて機能ブロックの集積化を行っても良い。例えば、バイオ技術の適用等が可能性としてありえる。
【０１４９】
２００６年８月２２日出願の特願２００６−２２５９３４の日本出願に含まれる明細書、図面および要約書の開示内容は、すべて本願に援用される。
【産業上の利用可能性】
【０１５０】
本発明に係る並列剰余演算器及び並列剰余演算方法は、ターボ復号器などの出力が並列で入力され、デジタル情報の誤りを検出する通信システムにおいて、従来のＣＲＣ計算回路に代えて使用される新規な並列剰余演算器及び並列剰余演算方法として有用である。例えば、誤り訂正のために畳み込み符号、ターボ符号化等で符号化された送信データを復号するため、受信側で、ビタビ復号器やターボ復号器等の軟出力復号器や伝送誤りの有無を検出するための巡回符号を使用する受信装置や携帯電話等の通信端末装置に用いるに好適である。
【図面の簡単な説明】
【０１５１】
【図１】ＣＲＣ符号の使われ方を説明する図
【図２】実際的なシステムに適用したＣＲＣ符号の使われ方を説明する図
【図３】従来のＣＲＣ計算回路の構成を示す図
【図４】従来の部分ＣＲＣ回路の構成を示す図
【図５Ａ】従来のシリアル・パラレル変換型の並列ＣＲＣ回路を示す図
【図５Ｂ】従来のシリアル・パラレル変換型の並列ＣＲＣ回路を示す図
【図６】本発明の実施の形態１に係る並列剰余演算器の全体構成を示すブロック図
【図７】上記実施の形態１に係る並列剰余演算器のデータの入出力を示すタイミングチャート
【図８】上記実施の形態１に係る並列剰余演算器の部分ＣＲＣ生成部が計算する部分ＣＲＣを表にまとめた図
【図９】上記実施の形態１に係る並列剰余演算器の部分ＣＲＣ生成部の回路構成を示す図
【図１０】上記実施の形態１に係る並列剰余演算器の部分ＣＲＣ生成部の動作を示すタイミングチャート
【図１１】上記実施の形態１に係る並列剰余演算器のＡＮＤ部の回路構成を示す図
【図１２】上記実施の形態１に係る並列剰余演算器のＡＮＤ部の動作を示すタイミングチャート
【図１３】上記実施の形態１に係る並列剰余演算器の累積加算部の回路構成を示す図
【図１４】上記実施の形態１に係る並列剰余演算器の初期値生成部の構成を示すブロック図
【図１５】上記実施の形態１に係る並列剰余演算器の初期値候補生成部の回路構成を示す図
【図１６】上記実施の形態１に係る並列剰余演算器の初期値生成部の動作を示すタイミングチャート
【図１７】本発明の実施の形態２に係る並列剰余演算器の全体構成を示すブロック図
【図１８】上記実施の形態２に係る並列剰余演算器の逆順部分ＣＲＣ生成部の回路構成を示す図
【図１９】上記実施の形態２に係る並列剰余演算器のそれぞれの部分ＣＲＣ生成部が計算する部分ＣＲＣを表にまとめた図
【図２０】上記実施の形態２に係る並列剰余演算器の初期値生成部の動作を示すタイミングチャート
【手続補正３】
【補正対象書類名】図面
【補正対象項目名】全図
【補正方法】変更
【補正の内容】
【図１】
2008023684.tif 000050
【図２】
2008023684.tif 000051
【図３】
2008023684.tif 000052
【図４】
2008023684.tif 000053
【図５Ａ】
2008023684.tif 000054
【図５Ｂ】
2008023684.tif 000055
【図６】
2008023684.tif 000056
【図７】
2008023684.tif 000057
【図８】
2008023684.tif 000058
【図９】
2008023684.tif 000059
【図１０】
2008023684.tif 000060
【図１１】
2008023684.tif 000061
【図１２】
2008023684.tif 000062
【図１３】
2008023684.tif 000063
【図１４】
2008023684.tif 000064
【図１５】
2008023684.tif 000065
【図１６】
2008023684.tif 000066
【図１７】
2008023684.tif 000067
【図１８】
2008023684.tif 000068
【図１９】
2008023684.tif 000069
【図２０】
2008023684.tif 000070
【国際調査報告】
2008023684.tif 000071
2008023684.tif 000072
2008023684.tif 000073
2008023684.tif 000074