(57)【要約】 【目的】  少ないテーブル容量で情報ビットの除算を高速に行えることを課題とする。【構成】  入力の情報ビット列が複数ブロックに分割された各サブビット列に対し、それぞれの上位ビットから該各サブビット列の最下位次数に対応するビット１を生成多項式で割った場合の剰余値を順に乗算する乗算手段と、前記得られた各乗算結果を除算手段における従前の剰余値にモジュロ２加算する加算手段と、前記加算手段の加算結果を前記生成多項式で順次除算する前記除算手段とを備える。【選択図】  図１
2008160663.tif 000002
【特許請求の範囲】
【請求項１】
乗算部と加算部とを備えた演算装置における入力情報ビット列の生成多項式による除算方法において、
入力情報ビット列を分割部で分割して複数のサブビット列Ａｉ（ｉ＝１〜Ｎ）を得て、
該サブビット列Ａｉの最下位ビットに対応する前記入力情報ビット列内におけるビット位置を１として前記入力情報ビット列における他のビットを０としたものに相当するビット列を多項式表現したものを前記生成多項式で除算して得られる剰余値を、対応するサブビット列Ａｉの上位側から各ビットに順に前記乗算部で乗算してゆき、
各サブビット列Ａｉについての乗算結果を前記加算部でモジュロ２加算して得られるビット列を多項式表現したものを前記生成多項式で除算する、ことを特徴とする情報ビット列の除算方法。
【請求項２】
入力情報ビット列の生成多項式による除算装置において、
入力情報ビット列を複数のサブビット列Ａｉ（ｉ＝１〜Ｎ）に分割する分割手段と、
前記サブビット列Ａｉの最下位のビットに対応する前記入力情報ビット列内におけるビット位置を１として前記入力情報ビット列における他のビットを０としたものに相当するビット列を多項式表現したものを前記生成多項式で除算して得られる剰余値を、対応するサブビット列Ａｉの上位側から各ビットに順に乗算する乗算手段と、
前記各サブビット列Ａｉについての乗算結果をモジュロ２加算する加算手段と、
前記加算結果のビット列を多項式表現したものを前記生成多項式で除算する除算手段と、を備えることを特徴とする情報ビット列の除算装置。
【請求項３】
入力の情報ビット列が複数ブロックに分割された各サブビット列に対し、それぞれの上位ビットから該各サブビット列の最下位次数に対応するビット１を生成多項式で割った場合の剰余値を順に乗算する乗算手段と、
前記得られた各乗算結果を除算手段における従前の剰余値にモジュロ２加算する加算手段と、
前記加算手段の加算結果を前記生成多項式で順次除算する前記除算手段とを備えることを特徴とする情報ビット列の除算装置。
【請求項４】
乗算手段は、分割後の各サブビット列のうちの最大のビット長に満たないサブビット列の上位側に該満たない分のビット０を付加して乗算を行うことを特徴とする請求項３記載の情報ビット列の除算装置。
【請求項５】
乗算手段は、最下位のサブビット列に対する乗算を行わないと共に、加算手段は最下位のサブビット列の情報をその上位から１ビットづつ抽出して他の乗算結果に加算することを特徴とする請求項３記載の情報ビット列の除算装置。
【請求項６】
情報ビット列の下位にＣＲＣビット数分のビット０を付加してその全体を複数ブロックのサブビット列に分割する分割手段と、
前記分割された各サブビット列に対し、それぞれの上位ビットから、該各サブビット列の最下位次数に対応する各ビット１を生成多項式で割った場合の各剰余値を順に乗算する乗算手段と、
前記得られた各乗算結果を除算手段における従前の剰余値にモジュロ２加算する加算手段と、
前記加算手段の加算結果を前記生成多項式で順次除算する前記除算手段とを備えることを特徴とする誤り検出符号装置。
【請求項７】
情報ビット列を複数ブロックのサブビット列に分割する分割手段と、
前記分割された各サブビット列に対し、それぞれの上位ビットから、該各サブビット列を予めＣＲＣビット数分上位にシフトしたと仮定した場合の各最下位ビット１を生成多項式で除算して得られる各剰余値を順に乗算する乗算手段と、
前記得られた各乗算結果を除算手段における従前の剰余値にモジュロ２加算する加算手段と、
前記加算手段の加算結果を前記生成多項式で順次除算する前記除算手段とを備えることを特徴とする誤り検出符号装置。
【請求項８】
複数のコードブロックに係る各情報ビット列が複数ブロックに分割された各サブビット列に対し、それぞれの上位ビットから該各サブビット列の最下位次数に対応するビット１を生成多項式で割った場合の剰余値を順に乗算する乗算手段と、
前記得られた各乗算結果を除算手段における従前の剰余値にモジュロ２加算する加算手段と、
前記加算手段の加算結果を前記生成多項式で順次除算する前記除算手段と、  前記除算手段における前回の剰余値を次回のコードブロックにおける最上位のサブビット列の頭に付加する付加手段とを備えることを特徴とする情報ビット列の除算装置。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は情報ビット列の除算方法及びその装置に関する。
特に、情報ビット列に対する誤り検出符号化及び復号化処理を並列に行う情報ビット列の除算方法及びその装置に用いて好適である。
【背景技術】
【０００２】
誤り検出符号は、データを誤り無く伝送することが要求されるデータ通信システムや、データを誤り無く読み出すことが要求される外部記憶装置などに使用され、伝送誤りを検出するために使用される。図２３に誤り検出符号を適用したシステムの例を示す。送信機側では、送信信号の誤り検出符号化処理を行った後、誤り訂正符号化を行い、伝送路を介して受信機に送信する。受信機側では、受信信号の誤り訂正復号を行い、その後に、誤り検出復号を行う。その際に誤り訂正復号でも訂正できない誤りが存在した場合は、送信機側に再送要求信号を送り、データの再送を行うことにより、結果として、受信機側にて誤りの無いデータを抽出することができる。
【０００３】
巡回冗長検査(ＣＲＣ: Cyclic Redundancy Check)符号は誤り検出符号の１つであり、連続した誤りを検出することが可能なため、誤り検出符号の中でもよく利用されている。ＣＲＣ符号は、送信側でｎビットの情報ビットを多項式に見立てて生成多項式により除算を行い、得られたｍビットの剰余を情報ビットに付加した（ｎ＋ｍ）ビットとし、生成多項式で割り切れるデータに符号化する。受信側では、受信データを生成多項式により除算を行い、剰余が０である場合は誤りなし、それ以外の場合に誤りありとして、誤り検出を行う。ＣＲＣの符号化、復号化の際には除算を行う必要があるが、この除算器はハードウエアで構成することにより比較的簡単な回路で構成することが出来る。
【０００４】
図２４は除算回路の一例のブロック図で、入力信号のビット列をｍ次の生成多項式Ｇ（ｘ）＝ｘｍ＋ｇｍ−１ｘｍ−１＋…＋ｇ１ｘ＋１で除算を行う場合の典型的な構成例を示している。除算回路はシフトレジスタと排他的論理和（＋）による簡単な回路で構成できると共に、図中の係数ｇｉは０又は１をとり、ｇｉ＝１の場合は線をつなぎ、ｇｉ＝０の場合は線をつながない構成となる。係る構成により、被除多項式をその高次から入力することにより、商多項式が高次から出力されると共に、被除多項式の全ての次数を入力した時点で各遅延素子Ｄには剰余多項式が保存されている。
【０００５】
従来のＣＲＣ符号化、復号化のために用いられる除算器では、入力を多項式と見立てて高次の項から順次入力する必要があり、除算処理を行うためには入力ビット数に応じたステップ数が必要となり、処理遅延時間が大きいという問題点があった。
【０００６】
この点、従来は、除算処理の高速化のために、入力データ列を複数のサブブロックに分割して、それぞれのサブブロックで並列に除算処理を行う除算装置（特許文献１）が知られている。特許文献１に示された方法は、各サブブロックについてそれぞれに除算処理を行って部分的な剰余を求めた後に、各剰余をサブブロックの次数にあわせたシフト行列を用いてシフト処理を行い、各シフト結果を合成（モジュロ２加算）することで最終的な剰余を求めるものである。
【特許文献１】特願２００３-５８７０１４（ＷＯ２００３／０９０３６２）
【特許文献２】特開２００４-１５２８５
【発明の開示】
【発明が解決しようとする課題】
【０００７】
しかし、特許文献１による方法ではシフト量１個に対して１個のシフト行列が必要となる。シフト行列は生成多項式の次数をｍとした場合に、サイズｍ×ｍの行列の各要素が０または１となる行列となる。そのため、入力データが可変長である場合は、各データ長に応じたシフト行列を得る手段が必要となり、ＲＯＭ化したテーブルを実装した場合には、シフト量１個に対してｍ２[ｂｉｔ]のメモリ容量が必要となるため、大きな容量のＲＯＭを必要とし、回路規模に大きなインパクトを与えるという問題があった。例えば、入力データ長：５１１４[ｂｉｔ]、行列サイズ：２４×２４[ｂｉｔ]の場合のＲＯＭサイズは５１１４×２４×２４＝２．９Ｍ[ｂｉｔ]となる。
【０００８】
本発明は上記従来技術の問題点に鑑みなされたもので、情報ビットの除算を高速に行える情報ビット列の除算方法及びその装置を提供することにある。また、少ないテーブル容量で情報ビットの除算を高速に行える情報ビット列の除算方法及びその装置を提供することにある。
【課題を解決するための手段】
【０００９】
本発明の第１の態様においては、乗算部と加算部とを備えた演算装置における入力情報ビット列の生成多項式による除算方法において、入力情報ビット列を分割部で分割して複数のサブビット列Ａｉ（ｉ＝１〜Ｎ）を得て、該サブビット列Ａｉの最下位ビットに対応する前記入力情報ビット列内におけるビット位置を１として前記入力情報ビット列における他のビットを０としたものに相当するビット列を多項式表現したものを前記生成多項式で除算して得られる剰余値を、対応するサブビット列Ａｉの上位側から各ビットに順に前記乗算部で乗算してゆき、各サブビット列Ａｉについての乗算結果を前記加算部でモジュロ２加算して得られるビット列を多項式表現したものを前記生成多項式で除算するものである。
【００１０】
以下に本発明による除算方法の原理を説明する。以下の演算は全てモジュロ（Ｍ０ｄ）２演算を示しており、Ｍｏｄ２加算の演算子は「＋」を使用している。入力データを多項式表現してＡ（ｘ）とし、ｍ次の生成多項式Ｇ（ｘ）で割った剰余を求める。今、Ａ（ｘ）をＭ個のサブブロックＡｋ（ｘ），０≦ｋ≦Ｍ−１分割する。それぞのサブブロックのビット数は任意としてＡｋ（ｘ）のビット数をｎｋビットとする。ｋが小さいものから、入力の次数の小さいサブブロックに対応させるものとして、入力データＡ（ｘ）は、
【００１１】
【数１】
2008160663.tif 000003
【００１２】
と表せる。ここで、ｋ番目のサブブロックＡｋ（ｘ）の次数は、
【００１３】
【数２】
2008160663.tif 000004
【００１４】
としている。
【００１５】
また各サブブロックのデータを多項式表現したものは、
【００１６】
【数３】
2008160663.tif 000005
【００１７】
となる。ａｉ，ｋはｋ番目のサブブロックのｉ番目のビットで０または１の係数となる。
【００１８】
ここでは、記述を簡単にするために、各サブブロックのビット長のうち最大のものをｎで定義して、Ａｋ（ｘ）をａｉ，ｋ＝０  ｉ≧ｎｋで拡張し、定義し直したものを使用する。即ち、
【００１９】
【数４】
2008160663.tif 000006
【００２０】
とする。
【００２１】
式(１)に式(４)を代入して入力多項式を書き直すと、
【００２２】
【数５】
2008160663.tif 000007
【００２３】
となる。ここで、ｘＮｋをＧ（ｘ）で割った商多項式をＱＮｋ（ｘ）、余り多項式をＲＮｋ（ｘ）とすると、ｘＮｋは、
【００２４】
【数６】
2008160663.tif 000008
【００２５】
と表現できる。式(５)に式(６)を代入すると式（７）、
【００２６】
【数７】
2008160663.tif 000009
【００２７】
となる。
【００２８】
式(７)の第１項はＧ（ｘ）で割り切れることから、Ａ（ｘ）÷Ｇ（ｘ）の剰余は第２項をＧ（ｘ）で割った剰余と等しくなる。すなわち、求める剰余は、
【００２９】
【数８】
2008160663.tif 000010
【００３０】
の剰余となる。ここで、
【００３１】
【数９】
2008160663.tif 000011
【００３２】
とおくと、Ｂｉ（ｘ）は各サブブロックの入力データ(１ビット)に対して、各サブブロックの次数に対応したあまり多項式ＲＮｋ（ｘ）を乗算し、全てのサブブロックで加算したものとなる。そのため、Ｂｉ（ｘ）はｍ−１次以下の多項式となる。また、求める剰余は、
【００３３】
【数１０】
2008160663.tif 000012
【００３４】
となり、これは、シフトレジスタを使った除算回路を用いることにより図１，図２に示し
た回路で表現できる。以上から、予め分割したサブブロックの次数に対応した余り多項式ＲＮｋ（ｘ）が判っている場合に、上記の演算を行うことが出来る。
【００３５】
本発明の第２の態様による情報ビット列の除算装置は、入力情報ビット列の生成多項式による除算装置において、入力情報ビット列を複数のサブビット列Ａｉ（ｉ＝１〜Ｎ）に分割する分割手段と、前記サブビット列Ａｉの最下位のビットに対応する前記入力情報ビット列内におけるビット位置を１として前記入力情報ビット列における他のビットを０としたものに相当するビット列を多項式表現したものを前記生成多項式で除算して得られる剰余値を、対応するサブビット列Ａｉの上位側から各ビットに順に乗算する乗算手段と、前記各サブビット列Ａｉについての乗算結果をモジュロ２加算する加算手段と、前記加算結果のビット列を多項式表現したものを前記生成多項式で除算する除算手段と、を備えるものである。
【００３６】
本発明の第３の態様による情報ビット列の除算装置は、入力の情報ビット列が複数ブロックに分割された各サブビット列に対し、それぞれの上位ビットから該各サブビット列の最下位次数に対応するビット１を生成多項式で割った場合の剰余値を順に乗算する乗算手段と、前記得られた各乗算結果を除算手段における従前の剰余値にモジュロ２加算する加算手段と、前記加算手段の加算結果を前記生成多項式で順次除算する前記除算手段とを備えるものである。
【００３７】
本発明の第４の態様では、乗算手段は、分割後の各サブビット列のうちの最大のビット長に満たないサブビット列の上位側に該満たない分のビット０を付加して乗算を行う。従って、各サブビット列に対する剰余値の乗算位相を容易に合わせることができる。
【００３８】
本発明の第５の態様では、乗算手段は、最下位のサブビット列に対する乗算を行わないと共に、加算手段は最下位のサブビット列の情報をその上位から１ビットづつ抽出して他の乗算結果に加算する。従って、乗算器やレジスタの回路規模を削減できる。
【００３９】
本発明の第６の態様では、連続する各次数のビット１につき求められた剰余値を記憶している剰余テーブルを備え、乗算手段は前記剰余テーブルからサブビット列の最下位次数に対応する剰余値を読み出して該サブビット列に乗算する。本発明によれば、剰余テーブルの容量は、入力ビット長の各次数についてｍ [ｂｉｔ]のデータを持てばよく、従来と比較して、１／ｍと大幅に削減できる。
【００４０】
本発明の第７の態様による情報ビット列の除算装置は、所定間隔おきの各次数に対応するビット１につき求められた剰余値を記憶している剰余テーブルと、入力のサブビット列の最下位次数に満たない前記所定間隔置きの最大の次数で剰余テーブルから対応する剰余値を読み出す読出手段と、前記読み出した剰余値の下位にビット０を付加しつつ生成多項式による除算を行い、前記サブビット列の最下位次数に対応する剰余値を求める第２の除算手段とを備え、乗算手段は前記第２の除算手段で求めた剰余値を入力のサブビット列に乗算するものである。従って、剰余テーブルの容量を更に削減できる。
【００４１】
本発明の第８の態様による情報ビット列の除算装置は、所定間隔おきの各次数に対応するビット１につき求められた剰余値を記憶している剰余テーブルと、入力のサブビット列の最下位次数に満たない前記所定間隔置きの最大の次数で剰余テーブルから対応する剰余値を読み出す読出手段と、前記読み出された剰余値を前記サブビット列の最下位次数ビット分上位にシフトするシフト手段と、前記シフトされた剰余値を入力として該入力を生成多項式で除算した剰余値を出力する排他的論理和回路の組み合わせからなる割り算手段とを備え、乗算手段は前記割り算手段で求めた剰余値を入力のサブビット列に乗算するものである。従って、剰余テーブルの容量を削減できると共に、割り算処理を高速に行える。
【００４２】
本発明の第９の態様による誤り検出符号装置は、情報ビット列の下位にＣＲＣビット数分のビット０を付加してその全体を複数ブロックのサブビット列に分割する分割手段と、前記分割された各サブビット列に対し、それぞれの上位ビットから、該各サブビット列の最下位次数に対応する各ビット１を生成多項式で割った場合の各剰余値を順に乗算する乗算手段と、前記得られた各乗算結果を除算手段における従前の剰余値にモジュロ２加算する加算手段と、前記加算手段の加算結果を前記生成多項式で順次除算する前記除算手段とを備えるものである。
【００４３】
本発明の第１０の態様による誤り検出符号装置は、情報ビット列を複数ブロックのサブビット列に分割する分割手段と、前記分割された各サブビット列に対し、それぞれの上位ビットから、該各サブビット列を予めＣＲＣビット数分上位にシフトしたと仮定した場合の各最下位ビット１を生成多項式で除算して得られる各剰余値を順に乗算する乗算手段と、前記得られた各乗算結果を除算手段における従前の剰余値にモジュロ２加算する加算手段と、前記加算手段の加算結果を前記生成多項式で順次除算する前記除算手段とを備えるものである。
【００４４】
本発明の第１１の態様による誤り検出復号装置は、ＣＲＣを含む受信ビット列を複数ブロックのサブビット列に分割する分割手段と、前記分割された各サブビット列に対し、それぞれの上位ビットから、該各サブビット列の最下位次数に対応する各ビット１を生成多項式で割った場合の各剰余値を順に乗算する乗算手段と、前記得られた各乗算結果を除算手段における従前の剰余値にモジュロ２加算する加算手段と、前記加算手段の加算結果を前記生成多項式で順次除算する前記除算手段と、前記除算手段における最終的な剰余値が全ビット０か否かを検出する誤り検出手段とを備えるものである。
【００４５】
本発明の第１２の態様による誤り検出復号装置は、入力の受信ビット列中のＣＲＣビットを全ビット０で置換した受信ビット列を複数ブロックのサブビット列に分割する分割手段と、前記分割された各サブビット列に対し、それぞれの上位ビットから、該各サブビット列の最下位次数に対応する各ビット１を生成多項式で割った場合の各剰余値を順に乗算する乗算手段と、前記得られた各乗算結果を除算手段における従前の剰余値にモジュロ２加算する加算手段と、前記加算手段の加算結果を前記生成多項式で順次除算する前記除算手段と、前記除算手段における最終的な剰余値と前記入力の受信ビット列から抽出したＣＲＣビット列とを比較して一致するか否かを検出する誤り検出手段とを備えるものである。
【００４６】
本発明の第１３の態様による誤り検出復号装置は、ＣＲＣを含む受信ビット列中の情報ビット列を複数ブロックのサブビット列に分割する分割手段と、前記分割された各サブビット列に対し、それぞれの上位ビットから、該各サブビット列を予めＣＲＣビット数分上位にシフトしたと仮定した場合の各最下位ビット１を生成多項式で除算して得られる各剰余値を順に乗算する乗算手段と、前記得られた各乗算結果を除算手段における従前の剰余値にモジュロ２加算する加算手段と、前記加算手段の加算結果を前記生成多項式で順次除算する前記除算手段と、前記除算手段における最終的な剰余値と前記受信ビット列から抽出したＣＲＣビット列とを比較して一致するか否かを検出する誤り検出手段とを備えるものである。
【００４７】
本発明の第１４の態様による情報ビット列の除算装置は、複数のコードブロックに係る各情報ビット列が複数ブロックに分割された各サブビット列に対し、それぞれの上位ビットから該各サブビット列の最下位次数に対応するビット１を生成多項式で割った場合の剰余値を順に乗算する乗算手段と、前記得られた各乗算結果を除算手段における従前の剰余値にモジュロ２加算する加算手段と、前記加算手段の加算結果を前記生成多項式で順次除
算する前記除算手段と、前記除算手段における前回の剰余値を次回のコードブロックにおける最上位のサブビット列の頭に付加する付加手段とを備えるものである。
【発明の効果】
【００４８】
以上述べた如く本発明によれば、情報ビットの除算を高速に行える情報ビット列の除算方法及びその装置を提供することができる。また、例えば、少ないテーブル容量で情報ビットの除算を行うことができる。また、例えば、乗算用の剰余値を保持するテーブル量は、入力ビット長のそれぞれ（各次数）についてｍ [ｂｉｔ]のデータを持てばよく、従来の特許文献１の方式と比較して、１／ｍと大幅に削減できる。
【発明を実施するための最良の形態】
【００４９】
以下、添付図面に従って本発明に好適なる実施の形態を詳細に説明する。なお、全図を通して同一符号は同一又は相当部分を示すものとする。
【００５０】
＜第１の実施の形態＞
図３は第１の実施の形態による除算装置のブロック図で、上記式(８)の除算を行う一例の構成を示している。図において、１０はサブブロック長の情報に従って対応する剰余値を読み出す剰余テーブル、２１は入力の各サブビット列に対応する剰余値を乗算する乗算器、２２は各サブビット列に対する剰余値を保持するレジスタ、２５はモジュロ（Ｍｏｄ）２の加算部、３０は加算部２５の出力を生成多項式Ｇ（ｘ）で除算する除算部、３１は除算部が保持する従前の剰余に加算部の出力を加算するＭｏｄ２の加算器、３２はフリップフロップ（ＦＦ）である。
【００５１】
一例の生成多項式Ｇ（ｘ）＝ｘ２４＋ｘ２３＋ｘ６＋ｘ５＋ｘ＋１である。剰余テーブル１０は、例えば入力Ａ（ｘ）＝ｘ０〜ｘ５０００について求められた剰余Ｒ０〜Ｒ５００００をｘの次数（べき乗）に対応するアドレスに記憶している。この剰余テーブル１０は入力データＡ（ｘ）に占める各サブブロックＳＢ１〜ＳＢＭ−１の中の最下位ビットの次数に基づきアクセスできる。本第１の実施の形態では入力の情報ビット列が任意サイズのサブブロックに分割されることを考慮して、剰余テーブル１０はどのようなサブビット長にも対処できるように、全ての剰余値を記憶している。
【００５２】
図４は第１の実施の形態による除算装置の動作説明図で、入力の情報ビット列を３つのサブブロックに分割してこれらを生成多項式Ｇ（ｘ）により並列に除算する場合を示している。但し、ここでは紙面の関係より次数ｍ＝３の生成多項式Ｇ（ｘ）＝ｘ３＋ｘ＋１を使用した場合の除算動作を具体的に説明する。
【００５３】
図において、入力の情報ビット列Ａ（ｘ）をビット１５〜１２よりなるサブブロック（ＳＢ）Ａ２と、ビット１１〜７よりなるＳＢＡ１と、ビット６〜０よりなるＳＢＡ０とに分割する。但し、ＳＢＡ２〜ＳＢ０の各最下位ビットはそれぞれｘ１２，ｘ７，ｘ０の位を有している。
【００５４】
好ましくは、後述の加算部２５における各剰余要素ｍ（即ち、乗算器２１で生じる各桁のサブ乗算結果ｍ）の加算位相を合わせ易くするために、各ＳＢＡ２〜ＳＢＡ０のうちの最大のビット長に満たないサブビット列の上位側に該満たない分のビット０を付加しておく。図の例の最大ビット長はＳＢＡ０の７ビットであり、これを満たすためにＳＢＡ２の頭には３ビットの０、ＳＢＡ１の頭には２ビットの０を付加しておく。サブビット列の頭にビット０を付加しても除算演算には何の影響も与えない。
【００５５】
除算開始の初期化段階では、まず剰余テーブル１０からＳＢＡ２（ｘ），ＳＢＡ１（ｘ）の各最下位ビットｘ１２，ｘ７をそれぞれＧ（ｘ）＝Ｘ３＋ｘ＋１で割った際の各剰余
値Ｒ１２＝１１１，Ｒ７＝００１を読み出してレジスタ２２２，２２１にセットする。一方、除算部３０のレジスタ（各ＦＦ）３２は全て初期化（リセット）されている。
【００５６】
ところで、ＳＢＡ０の最下位ビットｘ０＝１は３次のＧ（ｘ）では割れないから、剰余テーブル１０を引くまでもなく、その剰余値Ｒ０＝００１である。更に、この剰余値Ｒ０＝００１をＳＢＡ０のビット列に上位ビットから順に乗算した結果ｍ６〜ｍ０に注目すると、それぞれの最下位ビットを並べた系列「００１０００１」は丁度ＳＢＡ０の入力ビット列「００１０００１」と等しい。そこで、本第１の実施の形態では、最下位ブロックＳＢＡ０のラインに乗算器２２０を設けないと共に、加算部２５は、最下位ブロックＳＢＡ０のビット情報を上位から１ビットづつ抽出して他の乗算結果に加算するものとなっている。但し、図４の説明では、各サブブロックＳＢＡ２〜ＳＢＡ０に対する除算処理の一貫性（一様性）を示すために、乗算器２２０があるものとして説明する。
【００５７】
この状態で、ＳＢＡ２〜Ａ０の各ビット列Ａ２（ｘ）〜Ａ０（ｘ）はそれぞれの上位ビットから１ビットづつ一斉に入力する。 乗算器２２２はＡ２（ｘ）の最上位ビットｘ１８＝０（上記付け加えたビット０）に剰余値Ｒ１２＝１１１を乗算して３ビットの剰余要素ｍ１８＝０００を出力する。同時に、乗算器２２１はＡ１（ｘ）の最上位ビットｘ１３＝０に剰余値Ｒ７＝００１を乗算して３ビットの剰余要素ｍ１３＝０００を出力し、また乗算器２２０はＡ０（ｘ）の最上位ビットｘ６＝０に剰余値Ｒ０＝００１を乗算して３ビットの剰余要素ｍ６＝０００を出力する。但し、実際のＡ０（ｘ）については、乗算器２２０が無いので、加算部２５はこのタイミングにＡ０（ｘ）の最上位ビットｘ６＝０を抽出し、これを剰余要素ｍ６の最下位ビットとして保持する。
【００５８】
加算部２５では各剰余要素ｍ１８，ｍ１３，ｍ６のＭｏｄ２加算を行い、１回目の加算結果ｓ６＝０００を除算部３０に出力する。除算部３０では、前回までの剰余値（最初は全ビット０）に加算結果ｓ６＝０００をＭｏｄ２加算して該加算結果＝０００を１ビット上位側にシフトすると共に、最上位ビット（即ち、ＦＦ３２３）＝０であることにより、これを１回目の剰余値＝０００として保持する。
【００５９】
次に、２回目の加算結果ｓ５＝０００についても同様に処理され、除算部３０における２回目の剰余値＝０００となる。更に、３回目の加算結果ｓ４＝００１であるが、加算シフト後の最上位ビット＝０であるため、３回目の剰余値＝０１０となる。次に、加算部２５では各剰余要素ｍ１５，ｍ１０，ｍ３のＭｏｄ２加算を行い、４回目の加算結果ｓ３＝１１１を除算算部３０に出力する。除算部３０では、３回目の剰余値＝０１０に４回目の加算結果ｓ３＝１１１をＭｏｄ２加算して該加算結果＝１０１を１ビット上位側にシフトすると共に、最上位ビットの値＝１であることにより、該シフト結果を生成多項式Ｇ（ｘ）＝１０１１で除算（減算）し、４回目の剰余値＝００１を形成する。以下、同様にして進み、６回目の剰余値＝０１０に７回目の加算結果ｓ０＝１１０を加算シフトした時点で、除算部３０には最終的な剰余値Ｒ＝１００が保持されている。
【００６０】
＜第２の実施の形態＞
図５は第２の実施の形態による除算装置のブロック図で、剰余テーブルの容量を削減した場合を示している。この例の剰余テーブル１１は間を間引いたＰ個おきの剰余値のみを記憶している。そのため、剰余テーブル１１に記憶されていないサブブロック長が設定された場合には、その値に対応した剰余値を補間により求める。図において、２３１〜２３Ｍ−１は除算器であり、その他の構成については上記図３で述べたものと同様である。
【００６１】
次に、補間のための原理を説明する。Ｐを任意の定数として、Ｎｋ＝Ｐ・ｕ＋ｌ，０≦ｌ≦Ｐ―１で分解する。このとき、ｘＮｋをＧ（ｘ）で割ったときの商多項式ＱＮｋ（ｘ）と剰余多項式ＲＮｋ（ｘ）を利用すると、ｘＮｋは、
【００６２】
【数１１】
2008160663.tif 000013
【００６３】
となる。
【００６４】
式（１１）の第１項はＧ（ｘ）で割り切れることから、ｘＮｋをＧ（ｘ）で割った剰余は第２項のＲＰｕ（ｘ）ｘｌをＧ（ｘ）で割った剰余となる。ＲＰｕ（ｘ）ｘｌ÷Ｇ（ｘ）の演算はシフトレジスタを利用したＧ（ｘ）による除算器で行うことができ、始めにシフトレジスタにＲＰｕ（ｘ）の値を設定しておき、続けて下位よりビット０を１個づつ入力しつつ、シフトジスタをｌサイクル分シフトすることで実現できる。
【００６５】
本第２の実施の形態では、上記第１の実施の形態におけるレジスタ２２１〜２２Ｍ−１に対して、必要な除算を行うための数個の排他的論理和（ＥＸＯＲ）素子を追加するだけで除算器２３１〜２３Ｍ−１を構成できる。また、初期設定時間として最大Ｐ―１サイクル分の除算処理を追加するだけで良く、剰余テーブル１１の容量を１／Ｐに削減できる。
【００６６】
＜第３の実施の形態＞
図６は第３の実施の形態による除算装置のブロック図で、除算テーブルの容量を削減すると共に、必要な桁数分の除算（シフト）処理を１サイクルで実行することにより初期設定時間を短縮した場合を示している。本第３の実施の形態では、ＲＰｕ（ｘ）ｘｌ÷Ｇ（ｘ）の演算を、ＲＰｕ（ｘ）ｘｌの演算を実施する部分と、その結果をＧ（ｘ）で除算する部分との２段階に分けて行う。図において、１２はシフトレジスタ、１３は排他的論理和（ＥＸＯＲ）回路で構成した除算器である。
【００６７】
ＲＰｕ（ｘ）ｘｌは剰余テーブル１１から読み出したＰＰｕ（ｘ）を上位側にｌビットシフトしつつ、下位側にからビット０を挿入する演算となる。剰余値ＰＰｕ（ｘ）をｍビットとするとシフト演算後のＲＰｕ（ｘ）ｘｌは、最大ｍ＋Ｐ−１ビットとなる。このシフト結果ＲＰｕ（ｘ）ｘｌをＧ（ｘ）で除算する演算は、高々（ｍ＋Ｐ−１）ビットの固定入力ビット長に対する除算と考えることができるので、排他的論理和回路のみからなる一意の固定回路で実現することができる。従って、本第３の実施の形態による初期設定は高速に行える。
【００６８】
図７に生成多項式Ｇ（ｘ）＝ｘ２４＋ｘ２３＋ｘ６＋ｘ５＋ｘ＋１を用いて、Ｐ＝３２とした場合の処理内容のイメージを示す。また、表１に除算器１３内で行われる論理演算の内容を示す。
【００６９】
【表１】
2008160663.tif 000014
【００７０】
表 １は、５５ビットの除算器入力Ｉ[５４]〜Ｉ[０]から２４ビットの除算（シフト）結果Ｏ[２３]〜Ｏ[０]が得られる関係を表で示している。「＋」演算子は排他的論理和（Ｍｏｄ２加算に相当）を表す。例えば、出力ビット０[２２]は入力ビット（Ｉ[４５]＋Ｉ[４０]＋Ｉ[２２]により形成され、また出力ビット０[２１]は入力ビット（Ｉ[４４]＋Ｉ[３９]＋Ｉ[２１]）により形成される。他の出力ビットについても同様である。
【００７１】
＜第４の実施の形態＞
図８は第４の実施の形態による誤り検出符号装置のブロック図で、予め情報ビットの下位側にＣＲＣｍビット分のビット０を付加し、その全体を複数のサブブロックに分割して除算装置に入力すると共に、除算部３０における最終の除算結果ＲがそのままＣＲＣビットを表す場合を示している。誤り検出符号装置では、情報ビットを係数とする多項式Ａ（ｘ）にｘｍを掛けたものをＧ（ｘ）で割った剰余多項式Ｒ（ｘ）を求め、Ａ（ｘ）ｘｍ＋Ｒ（ｘ）として符号化する。即ち、情報ビットにＣＲＣビットを付加したものが符号語となる。本第４の実施の形態ではＳＢ＃０のラインにセレクタ（ＳＬ）４１を設けると共に、ＳＢ＃０に分割した情報ビットの末尾に続けてｍビット分のビット０を挿入し、その全体をＳＢ＃０として除算装置に入力する構成となっている。その他の構成については上記図３で述べたものと同様で良い。
【００７２】
図９，図１０は第４の実施の形態による誤り検出符号装置の動作説明図（１），（２）で、図９（Ａ）にＣＲＣ符号処理の動作イメージを示す。予め情報ビットの下位側にｍビット分のビット０を付加すると共に、その全体を４つサブブロックＳＢ＃３〜ＳＢ＃０に分割して除算装置に入力している。図９（Ｂ）にその動作タイミングチャートを示す。
【００７３】
図１０は１３ビット分の情報ビットにｍビット分のビット０を付加した全体を３つのサブブロックＡ２〜Ａ０に分割して除算装置に入力し、ＣＲＣ符号を生成する場合を示している。但し、ここでは紙面の関係より、次数ｍ＝３の生成多項式Ｇ（ｘ）＝ｘ３＋ｘ＋１を使用した場合のＣＲＣ符号動作を具体的に説明する。
【００７４】
ところで、本第４の実施の形態の除算装置に入力する情報ビット列の全体を、上記図４の情報ビット列と比較すると、各サブブロックＡ２〜Ａ０の分割位置は同一であると共に、図４の最下位ビットｂ０＝１と図１０の最下位ビットｂ０＝０（ＣＲＣ用ｍビットの一部）とが異なっているのみである。従って、加算シフト２までの除算動作は図４と同一であると共に、図１０の最終剰余値Ｒ（即ち，ＣＲＣビット）＝１０１となっている。従って、入力の情報ビットｂ１５〜ｂ３に続けてＣＲＣビットｂ２〜ｂ０を出力することで、ＣＲＣ符号を生成できる。
【００７５】
＜第５の実施の形態＞
図１１は第５の実施の形態による誤り検出符号装置のブロック図で、入力の情報ビットのみを複数のサブブロックに分割して除算装置に入力すると共に、該各サブブロックに対し、それぞれの上位ビットから、前記各サブブロックを予めｍビット分上位にシフトしたと仮定した場合における各最下位ビット１をＧ（ｘ）で除算して得られる各剰余値を順に乗算することで、除算部３０における最終の除算結果Ｒがそのまま入力の情報ビットに付加されるＣＲＣビットを表す場合を示している。
【００７６】
本第５の実施の形態ではＳＢ＃０のラインにも乗算器２１１とレジスタ２２１を設けると共に、ＳＢ＃３〜ＳＢ＃１のみならず、ＳＢ＃０の情報ビットに対しても予めｍビット分シフトしたと仮定した入力に対する剰余値を乗算する構成となっている。また、加算部２５もＳＢ＃３〜ＳＢ＃０の各乗算結果をＭｏｄ２加算する構成となっている。その他の構成については上記図３で述べたものと同様で良い。
【００７７】
図１２，図１３は第５の実施の形態による誤り検出符号装置の動作説明図（１），（２）で、図１２（Ａ）にＣＲＣ符号処理の動作イメージを示す。入力の情報ビットのみを複数のサブブロックＳＢ＃３〜ＳＢ＃０に分割して除算装置に入力すると共に、各サブブロックＳＢ＃３〜ＳＢ＃０に対して予めＣＲＣのｍビット分シフトしたと仮定した入力に対する剰余値を乗算することで、除算部３０における最終の除算結果Ｒがそのまま入力の情報ビットに続くＣＲＣビットを表している。図１２（Ｂ）にその動作タイミングチャートを示す。
【００７８】
図１３は１３ビット分の情報ビットを３つのサブブロックＡ２〜Ａ０に分割して除算装置に入力すると共に、各サブブロックに対して予めｍビット分シフトしたと仮定した入力に対する剰余値を乗算することで、除算部３０における最終の除算結果Ｒがそのまま入力の情報ビットに続くＣＲＣビットを表す場合を示している。但し、ここでは紙面の関係より、次数ｍ＝３の生成多項式Ｇ（ｘ）＝ｘ３＋ｘ＋１を使用した場合のＣＲＣ符号動作を具体的に説明する。
【００７９】
本第５の実施の形態では、入力の情報ビットのみを３つのサブブロックＳＢＡ２〜ＳＢＡ０に分割すると共に、剰余テーブル１０から各サブブロックＳＢＡ２〜ＳＢＡ０に対し
て予めｍ＝３ビット分シフトしたと仮定した入力に対する各剰余値が読み出され、各レジスタ２２２〜２２０に設定される。例えば、ＳＢＡ２の最下位ビットの次数＝９であるが、該ＳＢＡ２を３ビット上位側にシフトしたと仮定した場合の最下位ビットの次数＝１２であるから、剰余テーブル１０からは次数＝１２に対応する剰余値Ｒ１２＝１１１が読み出される。同様にして、ＳＢＡ１に対しては次数＝７に対応する剰余値Ｒ７＝００１が読み出され、ＳＢＡ０に対しては次数＝３に対応する剰余値Ｒ３＝０１１が読み出される。以下は、これらの情報に対して上記同様の乗算及び加算を行い、除算が終わった時点の除算部３０には最終的に剰余値Ｒ（即ち，ＣＲＣビット）＝１０１が保持されている。従って、入力の情報ビットｂ１２〜ｂ０に続けてＣＲＣビット＝１０１を出力することで、ＣＲＣ符号を生成できる。
【００８０】
＜第６の実施の形態＞
図１４は第６の実施の形態による誤り検出復号装置のブロック図で、ＣＲＣビットを含む受信ビットの全てを除算装置に入力してこれらを生成多他項式Ｇ（ｘ）により除算し、剰余が全ビット０の場合はＣＲＣ検査ＯＫ、０以外の場合はＣＲＣ検査ＮＧとする場合を示している。図において、この除算装置の構成は上記図３で述べたものと同様でよい。但し、この除算部３０’は該除算部３０’における最終的な剰余値を並列に出力可能となっている。全ビット０検査部５１は除算部３０’の出力の最終的な剰余値が全ビット０か否かを判定し、全ビット＝０ならＣＲＣ検査ＯＫ、それ以外ならＣＲＣ検査ＮＧの検査結果を出力する。
【００８１】
図１５は第６の実施の形態による誤り検出復号装置の動作説明図で、図１５（Ａ）にＣＲＣ検査処理の動作イメージを示し、図１５（Ｂ）にＣＲＣ検査処理のタイミングチャートを示す。図において、ＣＲＣビットを含む受信ビットの全体を４つのサブブロックＳＢ＃３〜ＳＢ＃０に分割して除算装置に入力する。全ＣＲＣビット＝０を含む受信ビット列の除算動作は、上記第４の実施の形態で述べた誤り検出符号装置における除算動作と同様に考えられ、ＣＲＣビットも含めたＳＢ＃３〜ＳＢ＃０の除算動作を終了した時点で除算部３０’にはＣＲＣ検査結果の剰余値が残されていることになる。
【００８２】
図１０の符号装置における生成ＣＲＣ＝１０１であったが、このＣＲＣビット＝１０１を含む受信ビットの全体を正常に受信した場合は、図１５の処理に従う除算部３０’の最終的な剰余値＝０００となり、ＣＲＣ検査ＯＫと判別できる。また、それ以外の場合はＣＲＣ検査ＮＧと判別できる。
【００８３】
＜第７の実施の形態＞
図１６は第７の実施の形態による誤り検出復号装置のブロック図で、受信ビット中のＣＲＣビット部分をビット０で置換して除算装置に入力すると共に、その除算結果と前記受信ビットより抽出したＣＲＣビットとを比較し、一致ならＣＲＣ検査ＯＫ、不一致ならＣＲＣ検査ＮＧとする場合を示している。図において、５２はＳＢ＃０から分離した受信ＣＲＣビット列をパラレル信号に変換するシリアルパラレル変換器、５３は除算部３０’の出力の生成ＣＲＣデータと、Ｓ／Ｐ５２の出力の受信ＣＲＣデータとを比較して一致ならＣＲＣ検査ＯＫ、不一致ならＣＲＣ検査ＮＧを出力する全ビット一致検査部である。
【００８４】
図１７は第７の実施の形態による誤り検出復号装置の動作説明図で、図１７（Ａ）にＣＲＣ検査処理の動作イメージを示し、図１７（Ｂ）にＣＲＣ検査処理のタイミングチャートを示す。図において、ＣＲＣビットを含む受信ビットの全体を４つのサブブロックＳＢ＃３〜ＳＢ＃０に分割して除算装置に入力する。その際には、受信ビット列中のサブブロックＳＢ＃０からＣＲＣビットを分離してＳ／Ｐ変換器５２によりパラレルＣＲＣビットに変換する。一方、前記ＣＲＣビットを分離する代わりに、このＳＢ＃０には引き続きセレクタ（ＳＬ）４１を介してＣＲＣビット数分のビット０が挿入され、除算装置に入力さ
れる。
【００８５】
全ＣＲＣビット＝０を含む受信ビット列の除算動作は、上記第４の実施の形態で述べた誤り検出符号装置における除算動作と同様に考えられ、全ＣＲＣビット＝０も含めたＳＢ＃３〜ＳＢ＃０の除算動作を終了した時点で除算部３０’には受信情報のみに基づいて生成された最終的な剰余値ＲとしてＣＲＣのビット列情報が保持されている。全ビット一致検査部５３では除算部３０’の出力の生成ＣＲＣデータと、Ｓ／Ｐ５２の出力の受信ＣＲＣデータとを比較して一致ならＣＲＣ検査ＯＫ、不一致ならＣＲＣ検査ＮＧを出力する。
【００８６】
＜第８の実施の形態＞
図１８は第８の実施の形態による誤り検出復号装置のブロック図で、受信ビット列中の情報ビットのみを除算装置に入力して上記第５の実施の形態で述べたのと同様の方法によりＣＲＣビットを生成すると共に、これを受信ビット列から分離したＣＲＣビットと比較し、一致ならＣＲＣ検査ＯＫ、不一致ならＣＲＣ検査ＮＧとする場合を示している。図において、５４は除算部３０’の出力のパラレルＣＲＣビットをシリアルＣＲＣビット列に変換するパラレルシリアル変換器（Ｐ／Ｓ）である。また、この除算装置には上記図１１で述べたと同様にＳＢ＃０のラインにも乗算器２１０とレジスタ２２０が設けられている。
【００８７】
図１９は第８の実施の形態による誤り検出復号装置の動作説明図で、図１９（Ａ）にＣＲＣ検査処理の動作イメージを示し、図１９（Ｂ）にＣＲＣ検査処理のタイミングチャートを示す。図において、受信ビット列中の情報ビットのみを４つのサブブロックＳＢ＃３〜ＳＢ＃０に分割して除算装置に入力する。情報ビット列のみに対する除算動作は、上記第５の実施の形態で述べた誤り検出符号装置における除算動作と同様に考えられ、情報ビットのみを含むＳＢ＃３〜ＳＢ＃０の除算動作を終了した時点で除算部３０’には情報ビット列のみに基づいて生成された最終的な剰余値ＲとしてＣＲＣのビット列情報が保持されている。これをＰ／Ｓ変換器５４でシリアル信号に変換すると共に、これを受信ビット系列から分離したＣＲＣビット列と比較することにより、一致ならＣＲＣ検査ＯＫ、不一致ならＣＲＣ検査ＮＧとする。
【００８８】
＜第９の実施の形態＞
図２０は第９の実施の形態による誤り検出復号装置のブロック図で、誤り訂正復号を並列に行うターボ復号器６０に本発明による誤り検出復号装置を接続した場合を示している。誤り訂正符号としてターボ符号を使用する場合に、高速にターボ復号を行うことを目的としたターボ復号器として特許文献２が知られている。この復号器ではコードブロックを複数のサブブロックに分割してこれらを並列に誤り訂正復号することによって１コードブロック当たりの誤り訂正復号時間を大幅に短縮することができる。後段の誤り検出復号装置では、ターボ復号器６０の出力の誤り訂正復号された各サブブロックＳＢ＃３〜ＳＢ＃０をそのまま並列に除算装置に入力して並列にＣＲＣ検査することにより、復号処理全体に掛かる時間を大幅に短縮している。
【００８９】
図２１，図２２は第９の実施の形態による誤り検出復号装置の動作説明図（１），（２）で、図２１は誤り検出復号装置の動作イメージを示している。図において、ターボ復号器６０は受信データの各コードブロックＣＢ＃０，ＣＢ＃１，ＣＢ＃３を単位に誤り訂正復号をシーケンシャルに行うと共に、各誤り訂正復号はコードブロックを複数のサブブロックＳＢ＃３〜ＳＢ＃０に分割して並列に誤り訂正復号し、誤り訂正復号された各サブブロックＳＢ＃３〜ＳＢ＃０が並列に出力される。
【００９０】
誤り検出復号装置では誤り訂正復号された各サブブロックＳＢ＃３〜ＳＢ＃０を並列に入力すると共に、ＣＢ＃０の誤り検査で得られたＳＢ０における最終的な剰余値がＣＢ＃
１におけるＳＢ＃３の先頭に付加されて誤り検出復号装置に入力する。この様な処理を、全てのコードブロックに対して行うと共に、最後のコードブロックについて求めた剰余値Ｒ＝０となった場合はＣＲＣ検査ＯＫ、それ以外の場合はＣＲＣ検査ＮＧとなる。
【００９１】
このとき、誤り訂正復号サブブロックのサイズが全てのコードブロックについて同じである場合は、除算装置に対する初期設定は最初に一回行えば良い。
【００９２】
図２２はターボ復号器６０からの各コードブロックＣＢ＃０，ＣＢ＃１に係る各サブブロックＳＢＡ２〜ＳＢＡ０が順次除算装置に並列に入力すると共に、これらを連続して生成多項式Ｇ（ｘ）＝ｘ３＋ｘ＋１により並列に除算する場合を具体的に示している。この除算装置における除算動作は基本的には上記図４で述べたものと同様である。即ち、図４を参照すると、最初のＣＢ＃０に係るサブブロックＳＢＡ２〜ＳＢＡ０を並列処理した時点で除算部３０’における最終的な剰余値Ｒ＝１００となる。
【００９３】
続く２番目のコードブロックＣＢ＃１についてＧ（ｘ）による除算を継続すると言うことは、前記ＣＢ＃０の除算で得られた剰余値Ｒ＝１００を続くＣＢ＃１の最上位ビット（即ち、ＳＢＡ２の最上位ビットｂ１５）に貼り付けてＧ（ｘ）による除算を継続することである。この状態が図２２に示されている。幸い、この例ではＳＢＡ２の頭部（ｂ１８〜ｂ１６の位置）にダミーのビット０が３つ付加されるので、ここに上記ＣＢ＃０の除算で得られた剰余値Ｒ＝１００を貼り付ける。こうして、上記同様にしてＣＢ＃１に対する除算を行うと、その最終段階の除算部３０’にはＣＢ＃０とＣＢ＃１とについてＧ（ｘ）による除算を継続したと等価な剰余値Ｒ＝０００が得られる。なお、この例ではＣＢ＃０とＣＢ＃１の情報ビットがたまたま同一であるため、ＣＢ＃０の処理で生成したＣＲＣ符号をＣＢ＃１の処理でＣＲＣ検査した形になっている。以下、同様にして除算処理を続け、最終的に送信側で付加したＣＲＣビット（例えば最終ＣＢにおけるＳＢＡ０の最後尾に挿入）によってＣＲＣ検査を行える。
【００９４】
なお、上記第９の実施の形態における除算装置は、誤り訂正符号としてターボ符号を用いた場合の、ターボ復号結果の誤り検出を行う誤り検出復号装置への適用例を示したが、これに限らない。この除算装置は、複数のコードブロックがそれぞれ複数のサブブロックに分割された各入力のサブビット列について、前回のコードブロックをＧ（ｘ）で除算して得たサブ剰余を次回のコードブロックの除算操作に引き継ぐことにより、最終のコードブロックが入力された時点て最終の剰余値を得る除算装置として利用できる。このような除算装置は、上記誤り検出復号装置としてのみならず、誤り検出符号装置としても利用可能である。
【００９５】
また、上記各実施の形態では、第１の実施の形態で説明した除算装置を使用する場合を中心に述べたが、これに限らない。第２又は第３の実施の形態による除算装置を使用しても良いことは明らかである。
【００９６】
また、上記各実施の形態では加算部２５による各乗算結果の加算と、除算部３０による加算結果の除算とを並行して進めたが、これに限らない。全手の乗算結果を加算後にＧ（ｘ）で除算しても良い。
【００９７】
また、上記各実施の形態では情報ビット列に対する一例のサブブロックへの分割例を具体的に述べたが、これに限らない。情報ビット列は任意ビット長のサブブロックに分割できる。
【００９８】
また、上記本発明に好適なる複数の実施の形態を述べたが、本発明思想を逸脱しない範囲内で各部の構成、制御、処理及びこれらの組合せの様々な変更が行えることは言うまで
も無い。
【００９９】
（付記１）  乗算部と加算部とを備えた演算装置における入力情報ビット列の生成多項式による除算方法において、入力情報ビット列を分割部で分割して複数のサブビット列Ａｉ（ｉ＝１〜Ｎ）を得て、該サブビット列Ａｉの最下位ビットに対応する前記入力情報ビット列内におけるビット位置を１として前記入力情報ビット列における他のビットを０としたものに相当するビット列を多項式表現したものを前記生成多項式で除算して得られる剰余値を、対応するサブビット列Ａｉの上位側から各ビットに順に前記乗算部で乗算してゆき、各サブビット列Ａｉについての乗算結果を前記加算部でモジュロ２加算して得られるビット列を多項式表現したものを前記生成多項式で除算する、ことを特徴とする情報ビット列の除算方法。
【０１００】
（付記２）  入力情報ビット列の生成多項式による除算装置において、入力情報ビット列を複数のサブビット列Ａｉ（ｉ＝１〜Ｎ）に分割する分割手段と、前記サブビット列Ａｉの最下位のビットに対応する前記入力情報ビット列内におけるビット位置を１として前記入力情報ビット列における他のビットを０としたものに相当するビット列を多項式表現したものを前記生成多項式で除算して得られる剰余値を、対応するサブビット列Ａｉの上位側から各ビットに順に乗算する乗算手段と、前記各サブビット列Ａｉについての乗算結果をモジュロ２加算する加算手段と、前記加算結果のビット列を多項式表現したものを前記生成多項式で除算する除算手段と、を備えることを特徴とする情報ビット列の除算装置。
【０１０１】
（付記３）  入力の情報ビット列が複数ブロックに分割された各サブビット列に対し、それぞれの上位ビットから該各サブビット列の最下位次数に対応するビット１を生成多項式で割った場合の剰余値を順に乗算する乗算手段と、前記得られた各乗算結果を除算手段における従前の剰余値にモジュロ２加算する加算手段と、前記加算手段の加算結果を前記生成多項式で順次除算する前記除算手段とを備えることを特徴とする情報ビット列の除算装置。
【０１０２】
（付記４）  乗算手段は、分割後の各サブビット列のうちの最大のビット長に満たないサブビット列の上位側に該満たない分のビット０を付加して乗算を行うことを特徴とする付記３記載の情報ビット列の除算装置。
【０１０３】
（付記５）  乗算手段は、最下位のサブビット列に対する乗算を行わないと共に、加算手段は最下位のサブビット列の情報をその上位から１ビットづつ抽出して他の乗算結果に加算することを特徴とする付記３記載の情報ビット列の除算装置。
【０１０４】
（付記６）  連続する各次数のビット１につき求められた剰余値を記憶している剰余テーブルを備え、乗算手段は前記剰余テーブルからサブビット列の最下位次数に対応する剰余値を読み出して該サブビット列に乗算することを特徴とする付記３記載の情報ビット列の除算装置。
【０１０５】
（付記７）  所定間隔おきの各次数に対応するビット１につき求められた剰余値を記憶している剰余テーブルと、入力のサブビット列の最下位次数に満たない前記所定間隔置きの最大の次数で剰余テーブルから対応する剰余値を読み出す読出手段と、前記読み出した剰余値の下位にビット０を付加しつつ生成多項式による除算を行い、前記サブビット列の最下位次数に対応する剰余値を求める第２の除算手段とを備え、乗算手段は前記第２の除算手段で求めた剰余値を入力のサブビット列に乗算することを特徴とする付記３記載の情報ビット列の除算装置。
【０１０６】
（付記８）  情報ビット列の除算装置は、所定間隔おきの各次数に対応するビット１につき求められた剰余値を記憶している剰余テーブルと、入力のサブビット列の最下位次数に満たない前記所定間隔置きの最大の次数で剰余テーブルから対応する剰余値を読み出す読出手段と、前記読み出された剰余値を前記サブビット列の最下位次数ビット分上位にシフトするシフト手段と、前記シフトされた剰余値を入力として該入力を生成多項式で除算した剰余値を出力する排他的論理和回路の組み合わせからなる割り算手段とを備え、乗算手段は前記割り算手段で求めた剰余値を入力のサブビット列に乗算することを特徴とする付記３記載の情報ビット列の除算装置。
【０１０７】
（付記９）  情報ビット列の下位にＣＲＣビット数分のビット０を付加してその全体を複数ブロックのサブビット列に分割する分割手段と、前記分割された各サブビット列に対し、それぞれの上位ビットから、該各サブビット列の最下位次数に対応する各ビット１を生成多項式で割った場合の各剰余値を順に乗算する乗算手段と、前記得られた各乗算結果を除算手段における従前の剰余値にモジュロ２加算する加算手段と、前記加算手段の加算結果を前記生成多項式で順次除算する前記除算手段とを備えることを特徴とする誤り検出符号装置。
【０１０８】
（付記１０）  情報ビット列を複数ブロックのサブビット列に分割する分割手段と、前記分割された各サブビット列に対し、それぞれの上位ビットから、該各サブビット列を予めＣＲＣビット数分上位にシフトしたと仮定した場合の各最下位ビット１を生成多項式で除算して得られる各剰余値を順に乗算する乗算手段と、前記得られた各乗算結果を除算手段における従前の剰余値にモジュロ２加算する加算手段と、前記加算手段の加算結果を前記生成多項式で順次除算する前記除算手段とを備えることを特徴とする誤り検出符号装置。
【０１０９】
（付記１１）  ＣＲＣを含む受信ビット列を複数ブロックのサブビット列に分割する分割手段と、前記分割された各サブビット列に対し、それぞれの上位ビットから、該各サブビット列の最下位次数に対応する各ビット１を生成多項式で割った場合の各剰余値を順に乗算する乗算手段と、前記得られた各乗算結果を除算手段における従前の剰余値にモジュロ２加算する加算手段と、前記加算手段の加算結果を前記生成多項式で順次除算する前記除算手段と、前記除算手段における最終的な剰余値が全ビット０か否かを検出する誤り検出手段とを備えることを特徴とする誤り検出復号装置。
【０１１０】
（付記１２）  入力の受信ビット列中のＣＲＣビットを全ビット０で置換した受信ビット列を複数ブロックのサブビット列に分割する分割手段と、前記分割された各サブビット列に対し、それぞれの上位ビットから、該各サブビット列の最下位次数に対応する各ビット１を生成多項式で割った場合の各剰余値を順に乗算する乗算手段と、前記得られた各乗算結果を除算手段における従前の剰余値にモジュロ２加算する加算手段と、前記加算手段の加算結果を前記生成多項式で順次除算する前記除算手段と、前記除算手段における最終的な剰余値と前記入力の受信ビット列から抽出したＣＲＣビット列とを比較して一致するか否かを検出する誤り検出手段とを備えることを特徴とする誤り検出復号装置。
【０１１１】
（付記１３）  ＣＲＣを含む受信ビット列中の情報ビット列を複数ブロックのサブビット列に分割する分割手段と、前記分割された各サブビット列に対し、それぞれの上位ビットから、該各サブビット列を予めＣＲＣビット数分上位にシフトしたと仮定した場合の各最下位ビット１を生成多項式で除算して得られる各剰余値を順に乗算する乗算手段と、前記得られた各乗算結果を除算手段における従前の剰余値にモジュロ２加算する加算手段と、前記加算手段の加算結果を前記生成多項式で順次除算する前記除算手段と、前記除算手段における最終的な剰余値と前記受信ビット列から抽出したＣＲＣビット列とを比較して一致するか否かを検出する誤り検出手段とを備えることを特徴とする誤り検出復号装置
。
【０１１２】
（付記１４）  複数のコードブロックに係る各情報ビット列が複数ブロックに分割された各サブビット列に対し、それぞれの上位ビットから該各サブビット列の最下位次数に対応するビット１を生成多項式で割った場合の剰余値を順に乗算する乗算手段と、前記得られた各乗算結果を除算手段における従前の剰余値にモジュロ２加算する加算手段と、前記加算手段の加算結果を前記生成多項式で順次除算する前記除算手段と、  前記除算手段における前回の剰余値を次回のコードブロックにおける最上位のサブビット列の頭に付加する付加手段とを備えることを特徴とする情報ビット列の除算装置。
【図面の簡単な説明】
【０１１３】
【図１】本発明による除算装置の原理図である。
【図２】本発明における除算部の原理図である。
【図３】第１の実施の形態による除算装置のブロック図である。
【図４】第１の実施の形態による除算装置の動作説明図である。
【図５】第２の実施の形態による除算装置のブロック図である。
【図６】第３の実施の形態による除算装置のブロック図である。
【図７】第３の実施の形態による剰余テーブルの動作説明図である。
【図８】第４の実施の形態による誤り検出符号装置のブロック図である。
【図９】第４の実施の形態による誤り検出符号装置の動作説明図（１）である。
【図１０】第４の実施の形態による誤り検出符号装置の動作説明図（２）である。
【図１１】第５の実施の形態による誤り検出符号装置のブロック図である。
【図１２】第５の実施の形態による誤り検出符号装置の動作説明図（１）である。
【図１３】第５の実施の形態による誤り検出符号装置の動作説明図（２）である。
【図１４】第６の実施の形態による誤り検出復号装置のブロック図である。
【図１５】第６の実施の形態による誤り検出復号装置の動作説明図である。
【図１６】第７の実施の形態による誤り検出復号装置のブロック図である。
【図１７】第７の実施の形態による誤り検出復号装置の動作説明図である。
【図１８】第８の実施の形態による誤り検出復号装置のブロック図である。
【図１９】第８の実施の形態による誤り検出復号装置の動作説明図である。
【図２０】第９の実施の形態による誤り検出復号装置のブロック図である。
【図２１】第９の実施の形態による誤り検出復号装置の動作説明図（１）である。
【図２２】第９の実施の形態による誤り検出復号装置の動作説明図（２）である。
【図２３】誤り検出符号を使用したソシテムの例である。
【図２４】一例の除算回路のブロック図である。
【符号の説明】
【０１１４】
１０，１１  剰余テーブル
１２  シフトレジスタ
１３  除算器
２１  乗算器
２２  レジスタ
２３  除算器
２５  加算部
３０  除算部
４１  セレクタ（ＳＬ）
５１  全ビット０検査部
５３  全ビット一致検査部
６０  ターボ復号器
【図１】
2008160663.tif 000015
【図２】
2008160663.tif 000016
【図３】
2008160663.tif 000017
【図４】
2008160663.tif 000018
【図５】
2008160663.tif 000019
【図６】
2008160663.tif 000020
【図７】
2008160663.tif 000021
【図８】
2008160663.tif 000022
【図９】
2008160663.tif 000023
【図１０】
2008160663.tif 000024
【図１１】
2008160663.tif 000025
【図１２】
2008160663.tif 000026
【図１３】
2008160663.tif 000027
【図１４】
2008160663.tif 000028
【図１５】
2008160663.tif 000029
【図１６】
2008160663.tif 000030
【図１７】
2008160663.tif 000031
【図１８】
2008160663.tif 000032
【図１９】
2008160663.tif 000033
【図２０】
2008160663.tif 000034
【図２１】
2008160663.tif 000035
【図２２】
2008160663.tif 000036
【図２３】
2008160663.tif 000037
【図２４】
2008160663.tif 000038