(57)【要約】【課題】誤り検出に係る処理量を削減すること。【解決手段】剰余値取得部１２は、入力ビット列の各ビットａｎiのうち１であるビットのインデックス番号ｎｉに基づいて剰余値テーブル１１から剰余値を取得し、シフト部１３は、剰余値取得部１２で取得された剰余値をインデックス番号ｎｉに基づいてビットシフトし、累積加算部１４は、シフト部１３から順に入力されるシフト結果を累積加算し、剰余演算部１５は、累積加算部１４での累積加算結果を生成多項式で除算したときの剰余値を算出し、誤り判定部１６は、剰余演算部１５で算出された剰余値が「０」となるときは入力ビット列に「誤り無し」と判定し、剰余演算部１５で算出された剰余値が「０以外」となるときは入力ビット列に「誤り有り」と判定する。【選択図】図１
2016051923.tif 000002
【特許請求の範囲】
【請求項１】
多項式表現されるビット列におけるそれぞれのビット位置に応じたそれぞれの単項式を誤り検出符号生成用の生成多項式で除算したときのそれぞれの剰余値のうち、所定のビット間隔Ｐの各ビット位置ｐ×Ｐ（ｐは０以上の整数）に対応する第一の剰余値を記憶するメモリと、
入力ビット列の各ビットと、前記各ビットの正規のビット位置とを入力され、前記入力ビット列の前記各ビットのうちの１であるビットの前記正規のビット位置ｐ×Ｐ＋ｑ（ｑは０以上かつＰ未満の整数）におけるｐ×Ｐに対応する前記第一の剰余値を前記メモリから取得し、取得した前記第一の剰余値をｑビットだけシフトしたシフト結果を累積加算対象とし、前記入力ビット列の前記各ビットのうちの１であるすべてのビットに対応するすべての前記シフト結果を累積加算して累積加算結果を求めた後に、前記累積加算結果を前記生成多項式に基づいて除算したときの第二の剰余値を求める剰余演算を行い、前記第二の剰余値に基づいて前記入力ビット列における誤りの有無を判定するプロセッサと、
を具備する誤り検出装置。
【請求項２】
多項式表現されるビット列におけるそれぞれのビット位置に応じたそれぞれの単項式を誤り検出符号生成用の生成多項式で除算したときのそれぞれの剰余値のうち、所定のビット間隔Ｐの各ビット位置ｐ×Ｐ（ｐは０以上の整数）に対応する第一の剰余値を記憶するメモリと、
入力ビット列の各ビットと、前記各ビットの正規のビット位置とを入力され、前記入力ビット列の前記各ビットのうちの１であるビットの前記正規のビット位置ｐ×Ｐ＋ｑ（ｑは０以上かつＰ未満の整数）におけるｐ×Ｐに対応する前記第一の剰余値を前記メモリから取得し、取得した前記第一の剰余値をｑ毎に累積加算してｑ毎の累積加算結果を求めた後に、前記累積加算結果をｑビットだけシフトしたシフト結果を前記生成多項式に基づいて除算したときの第二の剰余値を求める剰余演算をｑ毎に行い、すべてのｑにそれぞれ対応するすべての前記第二の剰余値を加算して第三の剰余値を求め、前記第三の剰余値に基づいて前記入力ビット列における誤りの有無を判定するプロセッサと、
を具備する誤り検出装置。
【請求項３】
前記プロセッサは、前記生成多項式による剰余演算に用いられる行列の部分行列を用いて、ｑ毎の前記シフトとｑ毎の前記剰余演算とを一括して行う、
請求項２に記載の誤り検出装置。
【請求項４】
前記プロセッサは、ｑ毎の前記シフトと、ｑ毎の前記剰余演算と、すべての前記第二の剰余値の前記加算とを、ＦＦＴアルゴリズムを用いて行う、
請求項２に記載の誤り検出装置。
【請求項５】
多項式表現されるビット列におけるそれぞれのビット位置に応じたそれぞれの単項式を誤り検出符号生成用の生成多項式で除算したときのそれぞれの剰余値のうち、所定のビット間隔Ｐの各ビット位置ｐ×Ｐ（ｐは０以上の整数）に対応する第一の剰余値を記憶するメモリを有する誤り検出装置における誤り検出方法であって、
入力ビット列の各ビットのうちの１であるビットの正規のビット位置ｐ×Ｐ＋ｑ（ｑは０以上かつＰ未満の整数）におけるｐ×Ｐに対応する前記第一の剰余値を前記メモリから取得し、
取得した前記第一の剰余値をｑビットだけシフトしたシフト結果を累積加算対象とし、前記入力ビット列の前記各ビットのうちの１であるすべてのビットに対応するすべての前記シフト結果を累積加算して累積加算結果を求め、
前記累積加算結果を前記生成多項式に基づいて除算したときの第二の剰余値を求める剰余演算を行い、
前記第二の剰余値に基づいて前記入力ビット列における誤りの有無を判定する、
誤り検出方法。
【請求項６】
多項式表現されるビット列におけるそれぞれのビット位置に応じたそれぞれの単項式を誤り検出符号生成用の生成多項式で除算したときのそれぞれの剰余値のうち、所定のビット間隔Ｐの各ビット位置ｐ×Ｐ（ｐは０以上の整数）に対応する第一の剰余値を記憶するメモリを有する誤り検出装置における誤り検出方法であって、
入力ビット列の各ビットのうちの１であるビットの正規のビット位置ｐ×Ｐ＋ｑ（ｑは０以上かつＰ未満の整数）におけるｐ×Ｐに対応する前記第一の剰余値を前記メモリから取得し、
取得した前記第一の剰余値をｑ毎に累積加算してｑ毎の累積加算結果を求めた後に、前記累積加算結果をｑビットだけシフトしたシフト結果を前記生成多項式に基づいて除算したときの第二の剰余値を求める剰余演算をｑ毎に行い、
すべてのｑにそれぞれ対応するすべての前記第二の剰余値を加算して第三の剰余値を求め、
前記第三の剰余値に基づいて前記入力ビット列における誤りの有無を判定する、
誤り検出方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、誤り検出装置及び誤り検出方法に関する。
【背景技術】
【０００２】
データを誤り無く伝送することが望まれるデータ通信システム、及び、データの読み出しを誤り無く行うことが望まれる記憶装置等では、伝送誤り及び読出誤り等を検出するために「誤り検出符号」が使用される。
【０００３】
誤り検出符号の一つに「ＣＲＣ（Cyclic  Redundancy  Check）符号」がある。ＣＲＣ符号を用いた誤り検出を行うデータ通信システムでは、送信側が、Ｋ’ビットの情報ビット列に相当する多項式をＣＲＣ符号生成用の生成多項式で除算したときのＬビットの剰余を情報ビット列に付加してＫビットの符号化ビット列を形成して受信側へ送信する。よって、誤り検出符号化後の情報ビットサイズは「Ｋ＝Ｋ’＋Ｌ」となり、Ｋビットの符号化ビット列を生成多項式で除算したときの剰余は「０」となる。Ｋ’は１ブロックの情報ビットサイズ、つまり、ブロックサイズである。情報ビットの各ブロックに付加されるＬビットの剰余は「パリティビット」と呼ばれる。
【０００４】
受信側は、受信した符号化ビット列を生成多項式で除算し、剰余が「０」であれば「誤り無し」、剰余が「０以外」であれば「誤り有り」と判定して、受信した符号化ビット列に対する誤り検出を行う。
【０００５】
例えば、Ｋ’ビットの情報ビット列「ｂ＝（ａ０,…,ａＫ’−２,ａＫ’−１）」の多項式Ｂ（ｘ）は式（１）によって表される。
【数１】
2016051923.tif 000003
【０００６】
また、生成多項式Ｇ（ｘ）は式（２）によって表される。
【数２】
2016051923.tif 000004
【０００７】
式（１）に示す多項式Ｂ（ｘ）を生成多項式Ｇ（ｘ）で除算したときの剰余値Ｒｃｒｃ（ｘ）は式（３）によって表される。剰余値Ｒｃｒｃ（ｘ）はパリティビットに相当する。
【数３】
2016051923.tif 000005
【０００８】
ビット位置を調節したＲｃｒｃ（ｘ）をＢ（ｘ）に加算すると式（４）に示す多項式Ａ（ｘ）が得られる。このＡ（ｘ）は、誤り検出符号化後のＫビットの符号化ビット列「ａ＝（ａ０,…,ａＫ−２,ａＫ−１）」を多項式表現したものに相当する。
【数４】
2016051923.tif 000006
【０００９】
送信側は、多項式Ａ（ｘ）で表現される符号化ビット列を受信側へ送信する。
【００１０】
ここで、Ａ（ｘ）をＧ（ｘ）で除算したときの剰余は「０」となる。よって、Ａ（ｘ）をＧ（ｘ）で除算した商多項式をＱ（ｘ）とすると、Ａ（ｘ）は式（５）によって表される。
【数５】
2016051923.tif 000007
【００１１】
そこで、受信側は、受信した符号化ビット列Ａ＾（ｘ）を生成多項式Ｇ（ｘ）で除算したときの剰余Ｒ＾（ｘ）を式（６）に従って算出する。
【数６】
2016051923.tif 000008
【００１２】
そして、受信側は、Ｒ＾（ｘ）が「０」となるときはＡ＾（ｘ）に「誤り無し」と判定し、Ｒ＾（ｘ）が「０以外」となるときはＡ＾（ｘ）に「誤り有り」と判定する。
【００１３】
ここで、１つめの関連技術として、インタリーブ処理により並び順がランダム化された符号化ビット列に対し、デインタリーブ処理することなく、そのままの並び順で誤り検出が可能な誤り検出装置がある。この誤り検出装置では、インタリーブ処理前の情報ビット列におけるそれぞれのビット位置（つまり、正規のビット位置）に応じた多項式を生成多項式で除算したときの剰余値を予め算出してメモリに保存しておく。そして、ビット列の各ビットがランダムに入力されると共に、各ビットの正規のビット位置を示すビット位置情報が入力される。入力ビット列の各ビットのうち０でないビットの正規のビット位置に対応する各剰余値をメモリより取得し、取得した各剰余値を累積加算する。累積加算結果が「０」となるときは入力ビット列に「誤り無し」と判定し、累積加算結果が「０以外」となるときは入力ビット列に「誤り有り」と判定する。つまり、入力ビット列の各ビットのうち０でないビットの正規のビット位置に対応する各剰余値の累積加算結果が式（６）のＲ＾（ｘ）に相当する。
【００１４】
また、２つめの関連技術として、１つめの関連技術におけるメモリのサイズを削減可能な誤り検出装置がある。この誤り検出装置では、所定のビット間隔を「Ｐ」とするとき、正規のビット位置のうち「ｎ×Ｐ」（ｎ＝１,２,…）のビット位置に応じた剰余値のみをメモリに保存する。入力ビット列に対しては、正規のビット位置のうち「ｎ×Ｐ」のビット位置に対応する各剰余値を、１つめの関連技術と同様にして、メモリより求める。一方で、正規のビット位置のうち「ｎ×Ｐ＋ｋ」（０≦ｋ＜Ｐ）のビット位置に対応する各剰余値を、「ｎ×Ｐ」のビット位置に対応する剰余値をｋビットだけシフトし、そのシフト結果を生成多項式で除算することにより算出する。そして、メモリから取得した各剰余値と、シフト及び除算によって算出した各剰余値とを累積加算し、１つめの関連技術と同様にして、累積加算結果に基づいて入力ビット列における誤りの有無を判定する。
【先行技術文献】
【特許文献】
【００１５】
【特許文献１】特許第５１２６２３０号公報
【特許文献２】国際公開第２００９／０１９７６３号
【特許文献３】国際公開第２００８／０２３６８４号
【特許文献４】特開２００９−１３６０２５号公報
【特許文献５】特開２００５−００６１８８号公報
【特許文献６】米国特許出願公開第２０１０／０１３８７２５号明細書
【特許文献７】米国特許出願公開第２０１０／０１９８８９２号明細書
【発明の概要】
【発明が解決しようとする課題】
【００１６】
しかし、２つめの関連技術では、メモリに存在しない剰余値、つまり、「ｎ×Ｐ＋ｋ」のビット位置に対応する各剰余値の算出をシフト結果の除算により行うので、「ｎ×Ｐ＋ｋ」の各ビット位置毎に剰余演算が行われる。このため、２つめの関連技術では、ブロックサイズが大きくなるほど剰余演算の回数が多くなり、誤り検出に係る処理量が大きくなる。
【００１７】
開示の技術は、上記に鑑みてなされたものであって、誤り検出に係る処理量を削減することを目的とする。
【課題を解決するための手段】
【００１８】
開示の態様では、誤り検出装置は、メモリと、プロセッサとを有する。メモリは、多項式表現されるビット列におけるそれぞれのビット位置に応じたそれぞれの単項式を誤り検出符号生成用の生成多項式で除算したときのそれぞれの剰余値のうち、所定のビット間隔Ｐの各ビット位置ｐ×Ｐ（ｐは０以上の整数）に対応する第一の剰余値を記憶する。プロセッサは、入力ビット列の各ビットと、前記各ビットの正規のビット位置とを入力され、前記入力ビット列の前記各ビットのうちの１であるビットの前記正規のビット位置ｐ×Ｐ＋ｑ（ｑは０以上かつＰ未満の整数）におけるｐ×Ｐに対応する前記第一の剰余値を前記メモリから取得する。プロセッサは、取得した前記第一の剰余値をｑビットだけシフトしたシフト結果を累積加算対象とし、前記入力ビット列の前記各ビットのうちの１であるすべてのビットに対応するすべての前記シフト結果を累積加算して累積加算結果を求める。プロセッサは、前記累積加算結果を求めた後に、前記累積加算結果を前記生成多項式に基づいて除算したときの第二の剰余値を求める剰余演算を行い、前記第二の剰余値に基づいて前記入力ビット列における誤りの有無を判定する。
【発明の効果】
【００１９】
開示の態様によれば、誤り検出に係る処理量を削減することができる。
【図面の簡単な説明】
【００２０】
【図１】図１は、実施例１の誤り検出装置の一例を示す機能ブロック図である。
【図２】図２は、実施例１の剰余値テーブルの一例を示す図である。
【図３】図３は、実施例１の誤り検出装置の処理の説明に供するフローチャートである。
【図４】図４は、実施例２の誤り検出装置の一例を示す機能ブロック図である。
【図５】図５は、実施例２の誤り検出装置の処理の説明に供するフローチャートである。
【図６】図６は、実施例３の誤り検出装置の一例を示す機能ブロック図である。
【図７】図７は、誤り検出装置のハードウェア構成例を示す図である。
【発明を実施するための形態】
【００２１】
以下に、本願の開示する誤り検出装置及び誤り検出方法の実施例を図面に基づいて詳細に説明する。なお、以下の実施例により本願の開示する誤り検出装置及び誤り検出方法が限定されるものではない。また、各実施例において同一の機能を有する構成部、及び、同一の処理を行うステップには同一の符号を付し、重複する説明を省略する。
【００２２】
［実施例１］
＜誤り検出装置の動作＞
式（４）に示す多項式Ａ（ｘ）を生成多項式Ｇ（ｘ）で除算したときの剰余値Ｒ（ｘ）を求める剰余演算は、式（７）によって表すことができるため、「線形演算」となる。つまり、２つめの関連技術のようにしてビット位置毎に生成多項式による剰余演算を行って求めた各剰余値を累積加算することにより算出した剰余値と、ビット位置毎の各剰余値の累積加算結果を生成多項式で除算することにより算出した剰余値とは等しくなる。
【数７】
2016051923.tif 000009
【００２３】
そこで、実施例１では、２つめの関連技術における剰余演算と累積加算との実行順序を逆にする。つまり、実施例１では、まず、ビット位置毎の各剰余値の累積加算結果を求め、次に、累積加算結果を生成多項式で除算することにより最終的な剰余値を算出する。これにより、実施例１では、２つめの関連技術に比べ、剰余演算の回数を削減する。
【００２４】
また、実施例１では、行列を用いたベクトル演算により剰余値を求める。剰余値Ｒ（ｘ）を求める剰余演算は式（７）に示すような線形演算となるため、剰余値Ｒ（ｘ）を求めるベクトル演算は線形変換として表すことができる。
【００２５】
すなわち、単項式に対する剰余値Ｒｎ（ｘ）が式（８）により表されるとき、式（８）と等価な剰余ベクトルｒｎは、式（９）により表すことができる。
【数８】
2016051923.tif 000010
【数９】
2016051923.tif 000011
【００２６】
ここで、式（９）におけるＧｒは、ｎ＝０,１,…,Ｋ−１にそれぞれ対応する剰余値ｒ０,ｒ１,…,ｒＫ−１を用いて式（１０）によって表される。
【数１０】
2016051923.tif 000012
【００２７】
よって、Ｒ（ｘ）に対応するベクトルｒをｒ＝（ｒ０,ｒ１,…,ｒＬ）とすると、式（７）に示すＲ（ｘ）に対応する剰余ベクトルｒは、式（１１）によって表される。
【数１１】
2016051923.tif 000013
【００２８】
なお、ランダムに入力されるビット列ａｎiに対して式（１１）を一般化すると、剰余ベクトルｒは式（１２）によって表される。
【数１２】
2016051923.tif 000014
【００２９】
＜誤り検出装置の構成＞
図１は、実施例１の誤り検出装置の一例を示す機能ブロック図である。図１において、誤り検出装置１０は、剰余値テーブル１１と、剰余値取得部１２と、シフト部１３と、累積加算部１４と、剰余演算部１５と、誤り判定部１６とを有する。
【００３０】
剰余値取得部１２には、入力ビット列の各ビットａｎiが１ビットずつランダムに入力されるとともに、各ビットａｎiの正規のビット位置を示すインデックス番号ｎｉが入力される（ｉ＝０,１,２,…,Ｋ−１）。「正規のビット位置」とは、１ブロックの情報ビット列の各ビットの並び順がランダム化される前の各ビットの１ブッロク内における位置である。
【００３１】
剰余値テーブル１１は、各ビットａｎiの正規のビット位置ｎｉにそれぞれ対応するＬビットの剰余値ｒｎi（式（９）に示す剰余ベクトルｒｎに相当）のうち、所定のビット間隔「Ｐ」の各ビット位置「ｐｉ×Ｐ」（ｐｉ＝０,１,２,…,Ｋ−１）に対応する剰余値ｒｐｉ×Ｐのみを記憶する。ただし、Ｐ＝２ｍ、つまり、Ｐは２のベキ乗である。図２は、実施例１の剰余値テーブルの一例を示す図である。例えば、剰余値テーブル１１は、図２に示すように、ビット位置０,Ｐ,２Ｐ,…,（Ｋ−１）Ｐにそれぞれ対応させて剰余値ｒｐ0×Ｐ,ｒｐ1×Ｐ,ｒｐ2×Ｐ,…,ｒｐK-1×Ｐを記憶する。なお、各ビットａｎiの正規のビット位置ｎｉにそれぞれ対応する剰余値ｒｎiは式（８）及び式（９）に従って予め算出可能である。つまり、剰余値テーブル１１は、多項式Ａ（ｘ）によって表現されるビット列におけるそれぞれのビット位置に応じたそれぞれの単項式ｘｎを生成多項式Ｇ（ｘ）で除算したときのそれぞれの剰余値Ｒｎ（ｘ）のうち、所定のビット間隔Ｐの各ビット位置ｐ×Ｐ（ｐは０以上の整数）に対応する剰余値のみをｒｐ×Ｐとして記憶する。
【００３２】
剰余値取得部１２は、入力される各ビットａｎiのうち１であるビット（つまり、０でないビット）のインデックス番号ｎｉに基づいて、剰余値テーブル１１からＬビットの剰余値を取得する。剰余値取得部１２は、入力される各ビットａｎiのうち０であるビットについては、剰余値の取得は行わない。剰余値取得部１２は、入力されるインデックス番号ｎｉを「ｐｉ×Ｐ＋ｑｉ」（ｑi＝０,１,２,…,Ｐ−１）に分解し、「ｐｉ×Ｐ」に対応する剰余値を剰余値テーブル１１から取得してシフト部１３へ出力する。つまり、剰余値取得部１２は、入力ビット列の各ビットのうちの１であるビットの正規のビット位置ｐ×Ｐ＋ｑ（ｑは０以上かつＰ未満の整数）におけるｐ×Ｐに対応する剰余値ｒｐ×Ｐを剰余値テーブル１１から取得する。
【００３３】
ここで、任意のインデックス番号ｎを２つの整数Ｑ,ｑの和として「ｎ＝Ｑ＋ｑ」と表したとき、単項式に対する剰余値Ｒｎ（ｘ）は、式（１３）によって表すことができる。
【数１３】
2016051923.tif 000015
【００３４】
また、多項式Ａ（ｘ）に単項式ｘｑを乗算することは、式（１４）に示すように、Ａ（ｘ）の各項のベキをｑだけ加算することに等しい。
【数１４】
2016051923.tif 000016
【００３５】
式（１４）のベクトル表現は、式（１５）に示すように、インデックスａをｑだけシフトしたａｑ~に対応する。
【数１５】
2016051923.tif 000017
【００３６】
よって、式（１３）に示す剰余値Ｒｎ（ｘ）と等価な剰余ベクトルｒＱ＋ｑは、基準となる剰余ベクトルｒＱをｑだけシフトしたシフトベクトルｒ~Ｑ＋ｑと、式（１０）に示すＧｒとを用いて、式（１６）により表すことができる。
【数１６】
2016051923.tif 000018
【００３７】
そこで、シフト部１３には、インデックス番号ｎｉが入力される。シフト部１３は、入力されるインデックス番号ｎｉを「ｐｉ×Ｐ＋ｑｉ」に分解し、剰余値取得部１２によって取得された剰余値ｒｐｉ×Ｐをｑｉビットだけシフトさせ、シフト結果を累積加算部１４へ出力する。
【００３８】
累積加算部１４は、シフト部１３から順に入力されるＫ個（ｉ＝０,１,２,…,Ｋ−１）のシフト結果を累積加算し、累積加算結果を剰余演算部１５へ出力する。つまり、累積加算部１４は、剰余値取得部１２によって取得された剰余値ｒｐ×Ｐがシフト部１３によってｑビットだけシフトされたシフト結果を累積加算対象とする。剰余値取得部１２では、上記のように、入力される各ビットａｎiのうち１であるビットについてのみ剰余値の取得が行われ、０であるビットについては、剰余値の取得が行われない。よって、累積加算部１４では、入力ビット列の各ビットのうちの１であるすべてのビットに対応するすべてのシフト結果が累積加算された累積加算結果が算出される。
【００３９】
剰余演算部１５は、累積加算部１４での累積加算結果を生成多項式Ｇ（ｘ）で除算したときの剰余値Ｒ（ｘ）（式（１１）に示す剰余ベクトルｒに相当）を算出する剰余演算を行い、算出した剰余値を誤り判定部１６へ出力する。つまり、誤り検出装置１０では、１ブロックの情報ビット列に対する誤り検出において剰余演算は１回しか行われない。
【００４０】
誤り判定部１６は、剰余演算部１５で算出された剰余値が「０」となるときは入力ビット列に「誤り無し」と判定し、剰余演算部１５で算出された剰余値が「０以外」となるときは入力ビット列に「誤り有り」と判定する。そして、誤り判定部１６は、判定結果に対応する値をチェック結果として出力する。例えば、誤り判定部１６は、入力ビット列に「誤り無し」と判定したときはチェック結果として「０」を出力し、入力ビット列に「誤り有り」と判定したときはチェック結果として「１」を出力する。
【００４１】
＜誤り検出装置の処理＞
図３は、実施例１の誤り検出装置の処理の説明に供するフローチャートである。図３に示すフローチャートは、入力ビット列における最初のビットが誤り検出装置１０に入力されたときに開始される。
【００４２】
まず、誤り検出装置１０は、カウンターｉの値を０にリセットする（ステップＳ１０１）。
【００４３】
次いで、誤り検出装置１０は、ｉの値がＫ未満か否かを判断する（ステップＳ１０２）。
【００４４】
ｉの値がＫ未満であるとき（ステップＳ１０２：Ｙｅｓ）、ビットａｎiと、インデックス番号ｎｉとが誤り検出装置１０に入力される（ステップＳ１０３）。ビットａｎiはランダムな順序で入力される。
【００４５】
次いで、誤り検出装置１０は、ビットａｎiの値が１か否かを判断する（ステップＳ１０４）。
【００４６】
ビットａｎiの値が１でないとき、つまり、０であるときは（ステップＳ１０４：Ｎｏ）、ステップＳ１０５〜Ｓ１０８の処理は行われず、処理はステップＳ１０９へ進む。
【００４７】
ビットａｎiの値が１であるときは（ステップＳ１０４：Ｙｅｓ）、誤り検出装置１０は、インデックス番号ｎｉを「ｐｉ×Ｐ＋ｑｉ」に分解して「ｐｉ×Ｐ」のビット位置を判断する（ステップＳ１０５）。
【００４８】
次いで、誤り検出装置１０は、ステップＳ１０５で判断したビット位置ｐｉ×Ｐに対応する剰余値ｒｐｉ×Ｐを取得する（ステップＳ１０６）。
【００４９】
次いで、誤り検出装置１０は、ステップＳ１０６で取得した剰余値ｒｐｉ×Ｐを式（１７）に示すようにしてｑｉビットだけシフトしてシフト結果ｒ~（ｑi）ｐｉ×Ｐを求める（ステップＳ１０７）。つまり、誤り検出装置１０は、剰余ベクトルｒｐｉ×Ｐの先頭にｑｉ個の０を埋めることにより、剰余ベクトルｒｐｉ×Ｐを剰余ベクトルｒ~（ｑi）ｐｉ×Ｐに変換する。
【数１７】
2016051923.tif 000019
【００５０】
次いで、誤り検出装置１０は、ステップＳ１０７でのシフト結果を、式（１８）に従って累積加算する（ステップＳ１０８）。
【数１８】
2016051923.tif 000020
【００５１】
次いで、誤り検出装置１０は、カウンターｉの値を１だけインクリメントし（ステップＳ１０９）、処理はステップＳ１０２に戻る。
【００５２】
そして、ステップＳ１０３〜Ｓ１０９の処理がＫ回だけ繰り返されてｉの値がＫ以上となったときに（ステップＳ１０２：Ｎｏ）、誤り検出装置１０は、累積加算結果ｒ~に対する剰余演算を式（１９）に従って行って剰余ベクトルｒを算出する（ステップＳ１１０）。式（１９）では、行列Ｇｒの代わりに行列Ｆを用いて剰余演算を行う場合を示す。式（１９）におけるＦは、Ｇｒの一部を抽出した部分行列であり、抽出サイズは、シフトベクトルｒ~Ｑ＋ｑのサイズに等しい。シフト量の最大値は予め規定されているため、シフトベクトルのサイズをシフト量の最大値に合わせることで、シフト量によらずＦを固定の行列とすることができる。
【数１９】
2016051923.tif 000021
【００５３】
式（１９）を成分表示すると式（２０）に示すようになる。
【数２０】
2016051923.tif 000022
【００５４】
次いで、誤り検出装置１０は、ステップＳ１１０で算出した剰余ベクトルｒに基づいて、ビットａｎ0〜ａｎK-1から形成される入力ビット列における誤りの有無を判定し（ステップＳ１１１）、処理は終了する。すなわち、誤り検出装置１０は、式（２０）に示すｒ０〜ｒＬ−１のすべてが０であるときは、入力ビット列に「誤り無し」と判定する。一方で、誤り検出装置１０は、式（２０）に示すｒ０〜ｒＬ−１の何れかが１であるときは、入力ビット列に「誤り有り」と判定する。
【００５５】
以上のように、誤り検出装置１０では、まず、ビット位置毎の各剰余値の累積加算結果を求め、次に、累積加算結果を生成多項式で除算することにより、誤りの有無の判定に使用される最終的な剰余値を算出する。こうすることで、誤り検出装置１０では、１ブロックの情報ビット列に対する誤り検出において剰余演算は１回しか行われない。よって、実施例１によれば、誤り検出に係る処理量を削減することができる。
【００５６】
また、誤り検出装置１０では、行列Ｇｒの代わりに行列Ｆを用いて剰余演算を行うことが好ましい。行列Ｆは、行列Ｇｒの部分行列である。よって、こうすることで、行列演算の演算量を削減することができるため、誤り検出に係る処理量をさらに削減することができる。
【００５７】
［実施例２］
＜誤り検出装置の動作＞
任意のインデックス番号ｎに対応する剰余値ｒｎから、インデックス番号ｎ＋１に対応する剰余値ｒｎ＋１を求めるための変換行列Ｇを用いると、剰余値ｒｎ＋１は式（２１）によって表される。変換行列Ｇにより、剰余値ｒｎのシフトと、シフト結果に対する剰余演算とが一括して行われて剰余値ｒｎ＋１が算出される。
【数２１】
2016051923.tif 000023
【００５８】
インデックス番号ｎを「ｐ×Ｐ＋ｑ」に分解して表すと、式（２１）は式（２２）によって表される。
【数２２】
2016051923.tif 000024
【００５９】
そこで、実施例２では、すべてのインデックス番号に対応する剰余値を式（２２）に従って算出する。式（２２）における変換行列Ｇｑは、式（１９）における行列ＦのＬ×Ｌ部分行列である。よって、式（１９）における行列Ｆが式（２３）によって表されるとき、変換行列Ｇｑは式（２４）によって表される。
【数２３】
2016051923.tif 000025
【数２４】
2016051923.tif 000026
【００６０】
ここで、剰余値ｒｎは、シフト数を明示した剰余値と、行列Ｆとを用いて式（２５）によって表される。
【数２５】
2016051923.tif 000027
【００６１】
ｒ~（ｑ）ｐ×Ｐとｒｐ×Ｐとの変換は、式（２６）に示す行列演算として表される。
【数２６】
2016051923.tif 000028
【００６２】
よって、剰余値ｒｎは、変換行列Ｇｑを用いて、式（２７）によって表すことができる。
【数２７】
2016051923.tif 000029
【００６３】
＜誤り検出装置の構成＞
図４は、実施例２の誤り検出装置の一例を示す機能ブロック図である。図４において、誤り検出装置２０は、剰余値テーブル１１と、剰余値取得部１２と、出力先選択部２１と、累積加算部２２−０〜２２−Ｘとを有する。また、誤り検出装置２０は、ｑ０演算部２３−０〜ｑＰ−１演算部２３−Ｘと、加算部２４と、誤り判定部１６とを有する。
【００６４】
剰余値取得部１２は、実施例１と同様にして、入力される各ビットａｎiのうち１であるビットについてのみ、「ｐｉ×Ｐ」に対応する剰余値を剰余値テーブル１１から取得して出力先選択部２１へ出力する。
【００６５】
出力先選択部２１には、インデックス番号ｎｉが入力される。出力先選択部２１は、入力されるインデックス番号ｎｉを「ｐｉ×Ｐ＋ｑｉ」（ｑi＝０,１,２,…,Ｐ−１）に分解し、ｑｉに従って、剰余値の出力先を選択する。すなわち、出力先選択部２１は、ｑｉ＝０のときは累積加算部２２−０へ剰余値を出力し、ｑｉ＝１のときは累積加算部２２−１へ剰余値を出力し、ｑｉ＝Ｐ−１のときは累積加算部２２−Ｘへ剰余値を出力する。
【００６６】
よって、累積加算部２２−０は、各ｐｉのｑｉ＝０に対応する各剰余値を累積加算し、累積加算部２２−１は、各ｐｉのｑｉ＝１に対応する各剰余値を累積加算し、累積加算部２２−Ｘは、各ｐｉのｑｉ＝Ｐ−１に対応する各剰余値を累積加算する。つまり、累積加算部２２−０〜２２−Ｘは、剰余値取得部１２によって取得された各剰余値をｑ毎に累積加算してｑ毎の累積加算結果を求める。累積加算部２２−０は、ｑｉ＝０に対応する累積加算結果をｑ０演算部２３−０へ出力し、累積加算部２２−１は、ｑｉ＝１に対応する累積加算結果をｑ１演算部２３−１へ出力する。また、累積加算部２２−Ｘは、ｑｉ＝Ｐ−１に対応する累積加算結果をｑＰ−１演算部２３−Ｘへ出力する。
【００６７】
ｑ０演算部２３−０は、ｑｉ＝０に対応する累積加算結果をｑｉ＝０ビットだけシフトしたシフト結果（つまり、ｑｉ＝０に対応する累積加算結果）を生成多項式Ｇ（ｘ）で除算したときの剰余値を求める剰余演算を行い、算出した剰余値を加算部２４へ出力する。ｑ１演算部２３−１は、ｑｉ＝１に対応する累積加算結果をｑｉ＝１ビットだけシフトしたシフト結果を生成多項式Ｇ（ｘ）で除算したときの剰余値を求める剰余演算を行い、算出した剰余値を加算部２４へ出力する。また、ｑＰ−１演算部２３−Ｘは、ｑｉ＝Ｐ−１に対応する累積加算結果をｑｉ＝Ｐ−１ビットだけシフトしたシフト結果を生成多項式Ｇ（ｘ）で除算したときの剰余値を求める剰余演算を行い、算出した剰余値を加算部２４へ出力する。つまり、ｑ０演算部２３−０〜ｑＰ−１演算部２３−Ｘの各演算部は、ｑ毎の累積加算結果をｑビットだけシフトしたシフト結果を生成多項式で除算したときの剰余値を求める剰余演算をｑ毎に行う。
【００６８】
また、ｑ０演算部２３−０〜ｑＰ−１演算部２３−Ｘの各演算部は、ｑ毎の累積加算結果をｑビットだけシフトするシフト処理と、シフト結果を生成多項式で除算したときの剰余値を求める剰余演算とを、行列Ｆの部分行列である変換行列Ｇｑを用いて、式（２２）に従って、ｑ毎に行う。つまり、ｑ０演算部２３−０〜ｑＰ−１演算部２３−Ｘの各演算部は、シフト及び剰余演算を一括して行う変換行列Ｇｑを用いる。
【００６９】
加算部２４は、ｑ０演算部２３−０〜ｑＰ−１演算部２３−Ｘのそれぞれで算出された各剰余値をすべて加算して剰余値Ｒ（ｘ）（式（１１）に示す剰余ベクトルｒに相当）を算出し、算出した剰余値を誤り判定部１６へ出力する。つまり、加算部２４は、０〜Ｐ−１のすべてのｑにそれぞれ対応するすべての剰余値を加算して剰余値Ｒ（ｘ）を求める。
【００７０】
＜誤り検出装置の処理＞
図５は、実施例２の誤り検出装置の処理の説明に供するフローチャートである。図５に示すフローチャートは、入力ビット列における最初のビットが誤り検出装置２０に入力されたときに開始される。図５において、ステップＳ１０１〜Ｓ１０６，Ｓ１０９，Ｓ１１１の処理は実施例１（図３）と同一であるため、説明を省略する。
【００７１】
ステップＳ２０１において、誤り検出装置２０は、ステップＳ１０６で取得した剰余値ｒｐｉ×Ｐを式（２８）に従ってｑｉ毎に累積加算する。
【数２８】
2016051923.tif 000030
【００７２】
つまり、ステップＳ１０３〜Ｓ２０１，Ｓ１０９の一連の処理では、式（２９）に示す累積加算が行われて、ｑ毎の累積加算結果ｒ（ｑ）が算出される。
【数２９】
2016051923.tif 000031
【００７３】
そして、ステップＳ１０３〜Ｓ２０１，Ｓ１０９の処理がＫ回だけ繰り返されてｉの値がＫ以上となったときに（ステップＳ１０２：Ｎｏ）、誤り検出装置２０は、ステップＳ２０２及びＳ２０３の処理を一括して行う。すなわち、誤り検出装置２０は、ｑ毎の累積加算結果をｑビットだけシフトするシフト処理と、シフト結果を生成多項式で除算したときの剰余値を求める剰余演算とを、変換行列Ｇｑを用いて、式（３０）に従って行って、ｑ毎の剰余値ｒ［ｑ］を求める（ステップＳ２０２，Ｓ２０３）。
【数３０】
2016051923.tif 000032
【００７４】
式（３０）を成分表示すると式（３１）に示すようになる。
【数３１】
2016051923.tif 000033
【００７５】
次いで、誤り検出装置２０は、ステップＳ２０４〜Ｓ２０７の処理を行うことにより、式（３２）に示す加算を行って剰余ベクトルｒを算出する。
【数３２】
2016051923.tif 000034
【００７６】
すなわち、誤り検出装置２０は、カウンターｑの値を０にリセットする（ステップＳ２０４）。
【００７７】
次いで、誤り検出装置２０は、ｑの値がＰ未満か否かを判断する（ステップＳ２０５）。
【００７８】
ｑの値がＰ未満であるとき（ステップＳ２０５：Ｙｅｓ）、誤り検出装置２０は、ｑの値に対応するｒ［ｑ］を式（３３）に従って加算する（ステップＳ２０６）。
【数３３】
2016051923.tif 000035
【００７９】
次いで、誤り検出装置２０は、カウンターｑの値を１だけインクリメントし（ステップＳ２０７）、処理はステップＳ２０５に戻る。
【００８０】
そして、ステップＳ２０６，Ｓ２０７の処理がＰ回だけ繰り返されてｑの値がＰ以上となったときに（ステップＳ２０５：Ｎｏ）、誤り検出装置２０は、ステップＳ２０６での加算結果である剰余ベクトルｒに基づいて、ビットａｎ0〜ａｎK-1から形成される入力ビット列における誤りの有無を判定し（ステップＳ１１１）、処理は終了する。
【００８１】
以上のように、誤り検出装置２０では、まず、ビット位置毎の各剰余値の累積加算結果をｑ毎に求め、次に、ｑ毎の累積加算結果をｑビットだけシフトしたシフト結果を生成多項式で除算したときの剰余値を求める剰余演算をｑ毎に行う。そして、０〜Ｐ−１のすべてのｑにそれぞれ対応するすべての剰余値を加算することにより、誤りの有無の判定に使用される最終的な剰余値を算出する。こうすることで、ｑ毎の演算では、１つのｑに対し、剰余演算は１回しか行われない。ｑは０〜Ｐ−１である。つまり、誤り検出装置２０では、１ブロックの情報ビット列に対する誤り検出において、剰余演算は、最大でＰ回しか行われない。よって、実施例２によれば、誤り検出に係る処理量を削減することができる。
【００８２】
また、誤り検出装置２０では、ｑ毎の累積加算結果をｑビットだけシフトするシフト処理と、シフト結果を生成多項式で除算したときの剰余値を求める剰余演算とを、変換行列Ｇｑを用いて一括して行う。変換行列Ｇｑは行列Ｆの部分行列であり、行列Ｆは行列Ｇｒの部分行列である。よって、こうすることで、行列演算の演算量を削減することができるため、誤り検出に係る処理量をさらに削減することができる。
【００８３】
［実施例３］
＜誤り検出装置の動作＞
式（３２）は、式（３４）に書き換えることができる。
【数３４】
2016051923.tif 000036
【００８４】
つまり、実施例２におけるｑ０演算部２３−０〜ｑＰ−１演算部２３−Ｘ及び加算部２４で行われる演算は、Ｇのベキ演算となる。よって、実施例２におけるｑ０演算部２３−０〜ｑＰ−１演算部２３−Ｘ及び加算部２４で行われる演算は、ＦＦＴ（Fast  Fourier  Transform）アルゴリズムを用いて行うことができる。
【００８５】
なお、一般的なベキ級数に対してのＦＦＴアルゴリズムの一例を以下に示す。
【００８６】
求めるベキ級数Ａ（ｘ）を式（３５）に定義する。Ｎ＝２ｍである。一般には、Ｎが複数の素数のベキの因数の掛け算で表わされる場合に拡張される。
【数３５】
2016051923.tif 000037
【００８７】
式（３６），（３７）に示すように、級数の和について、まずインデックスの降順に２つの項の和を求める。
【数３６】
2016051923.tif 000038
【数３７】
2016051923.tif 000039
【００８８】
よって、ｘベキ級数は、Ｘ１（ｘ）についての半分項数のベキ級数として表される。よって、式（３６），（３７）におけるｉ回の繰り返しは、式（３８），（３９）によって与えられる。そして、ｉ＝ｍのとき、項目数が１つとなって、ＦＦＴアルゴリズムにおける最終的な演算結果が得られる。
【数３８】
2016051923.tif 000040
【数３９】
2016051923.tif 000041
【００８９】
＜誤り検出装置の構成＞
図６は、実施例３の誤り検出装置の一例を示す機能ブロック図である。図６において、誤り検出装置３０は、剰余値テーブル１１と、剰余値取得部１２と、出力先選択部２１と、累積加算部２２−０〜２２−Ｘとを有する。また、誤り検出装置３０は、ＦＦＴ部３１と、Ｇテーブル３２と、誤り判定部１６とを有する。つまり、誤り検出装置３０では、実施例２の誤り検出装置２０（図４）におけるｑ０演算部２３−０〜ｑＰ−１演算部２３−Ｘ及び加算部２４が、ＦＦＴ部３１に置き換えられている。
【００９０】
Ｇテーブル３２は、式（３４）におけるＧｑ（ｑ＝０〜Ｐ−１）を記憶する。
【００９１】
ＦＦＴ部３１は、Ｇテーブル３２に記憶されているＧｑを用いて、ｑ毎の累積加算結果に対して、実施例２におけるｑ０演算部２３−０〜ｑＰ−１演算部２３−Ｘ及び加算部２４で行われる演算に相当する演算を、上記のようなＦＦＴアルゴリズムに従って行う。このＦＦＴアルゴリズムに従った演算により、誤り判定部１６での判定に用いられる剰余値Ｒ（ｘ）（式（３４）に示す剰余ベクトルｒに相当）が算出される。
【００９２】
＜誤り検出装置の処理＞
実施例３のフローチャートは、実施例２におけるフローチャート（図５）におけるステップＳ２０２〜Ｓ２０７の処理を、式（３４）に従って行われるＦＦＴアルゴリズムを用いた演算に置き換えたものになる。
【００９３】
以上のように、誤り検出装置３０では、実施例２におけるｑ０演算部２３−０〜ｑＰ−１演算部２３−Ｘ及び加算部２４で行われる演算をＦＦＴアルゴリズムを用いて行う。こうすることで、ｑ毎の累積加算結果をｑビットだけシフトしたシフト結果を生成多項式で除算したときの剰余値を求める剰余演算と、０〜Ｐ−１のすべてのｑにそれぞれ対応するすべての剰余値の加算とを高速に行うことができる。
【００９４】
［他の実施例］
［１］上記実施例の誤り検出装置１０，２０，３０は、次のようなハードウェア構成により実現することができる。図７は、誤り検出装置のハードウェア構成例を示す図である。図７に示すように、誤り検出装置１０，２０，３０は、ハードウェアの構成要素として、プロセッサ４１と、メモリ４２とを有する。プロセッサ４１の一例として、ＣＰＵ（Central  Processing  Unit），ＤＳＰ（Digital  Signal  Processor），ＦＰＧＡ（Field  Programmable  Gate  Array）等が挙げられる。また、誤り検出装置１０，２０，３０は、プロセッサ４１と周辺回路とを含むＬＳＩ（Large  Scale  Integrated  circuit）を有してもよい。メモリ４２の一例として、ＳＤＲＡＭ等のＲＡＭ，ＲＯＭ，フラッシュメモリ等が挙げられる。剰余値取得部１２と、シフト部１３と、累積加算部１４と、剰余演算部１５と、誤り判定部１６と、出力先選択部２１と、累積加算部２２−０〜２２−Ｘと、ｑ０演算部２３−０〜ｑＰ−１演算部２３−Ｘと、加算部２４と、ＦＦＴ部３１とは、プロセッサ４１により実現される。剰余値テーブル１１と、Ｇテーブル３２とは、メモリ４２により実現される。
【００９５】
［２］誤り検出装置１０，２０，３０での上記説明における各処理は、各処理に対応するプログラムをプロセッサ４１に実行させることによって実現してもよい。例えば、誤り検出装置１０，２０，３０での上記説明における各処理に対応するプログラムがメモリ４２に記憶され、各処理に対応するプログラムがプロセッサ４１によってメモリ４２から読み出されて実行されてもよい。
【符号の説明】
【００９６】
１０，２０，３０  誤り検出装置
１１  剰余値テーブル
１２  剰余値取得部
１３  シフト部
１４  累積加算部
１５  剰余演算部
１６  誤り判定部
２１  出力先選択部
２２−０〜２２−Ｘ  累積加算部
２３−０  ｑ０演算部
２３−１  ｑ１演算部
２３−Ｘ  ｑＰ−１演算部
２４  加算部
３１  ＦＦＴ部
３２  Ｇテーブル
【図１】
2016051923.tif 000042
【図２】
2016051923.tif 000043
【図３】
2016051923.tif 000044
【図４】
2016051923.tif 000045
【図５】
2016051923.tif 000046
【図６】
2016051923.tif 000047
【図７】
2016051923.tif 000048