(57)【特許請求の範囲】
【請求項１】
巡回符号又は擬似巡回符号である誤り訂正符号を用いて誤り訂正符号化されている符号語系列を受信する符号語系列受信手段と、上記符号語系列受信手段により受信された符号語系列の検査多項式に応じたシフト量で上記符号語系列のビットをシフトして、複数の符号語シフト系列を生成する符号語シフト系列生成手段と、上記符号語系列受信手段により受信された符号語系列及び上記符号語シフト系列生成手段により生成された符号語シフト系列におけるビット同士の排他的論理和演算を実施してシンドローム系列を生成するシンドローム系列生成手段と、上記符号語系列受信手段により受信された符号語系列の検査多項式に応じたシフト量で上記シンドローム系列生成手段により生成されたシンドローム系列のビットをシフトして、複数のシンドロームシフト系列を生成するシンドロームシフト系列生成手段と、上記シンドローム系列生成手段により生成されたシンドローム系列及び上記シンドロームシフト系列生成手段により生成されたシンドロームシフト系列におけるビット同士の論理演算を実施して誤り系列を生成する誤り系列生成手段と、上記誤り系列生成手段により生成された誤り系列を用いて、上記符号語系列受信手段により受信された符号語系列の誤りを訂正する誤り訂正手段とを備えた復号装置。
【請求項２】
符号語シフト系列生成手段は、符号語系列受信手段により受信された符号語系列の検査多項式がｘ７＋ｘ３＋ｘ１＋ｘ０である場合、上記符号語系列のビットを右に１ビットシフトして第１の符号語シフト系列を生成し、上記第１の符号語シフト系列のビットを右に２ビットシフトして第２の符号語シフト系列を生成し、上記第２の符号語シフト系列のビットを右に４ビットシフトして第３の符号語シフト系列を生成することを特徴とする請求項１記載の復号装置。
【請求項３】
シンドローム系列生成手段は、符号語系列のビットと、第１の符号語シフト系列のビットと、第２の符号語シフト系列のビットと、第３の符号語シフト系列のビットとの排他的論理和を求め、その排他的論理和の結果をシンドローム系列として出力することを特徴とする請求項２記載の復号装置。
【請求項４】
シンドロームシフト系列生成手段は、シンドローム系列生成手段により生成されたシンドローム系列のビットを左に１ビットシフトして第１のシンドロームシフト系列を生成し、上記第１のシンドロームシフト系列のビットを左に２ビットシフトして第２のシンドロームシフト系列を生成し、上記第２のシンドロームシフト系列のビットを左に４ビットシフトして第３のシンドロームシフト系列を生成することを特徴とする請求項３記載の復号装置。
【請求項５】
誤り系列生成手段は、シンドローム系列、第１のシンドロームシフト系列、第２のシンドロームシフト系列及び第３のシンドロームシフト系列におけるビット同士の第１の論理演算と第２の論理演算と第３の論理演算を実施し、上記第１の論理演算の結果と上記第２の論理演算の結果との論理積を求めて、上記論理積の結果と上記第３の論理演算の結果との論理和を求め、上記論理和の結果を誤り系列として出力することを特徴とする請求項４記載の復号装置。
記
・  第１の論理演算
＝Ｓ０  EXOR  Ｓ−１  EXOR  Ｓ−３  EXOR  Ｓ−７
・  第２の論理演算
＝((Ｓ０  EXOR  Ｓ−１  EXOR  Ｓ−３)  AND  Ｓ−７)
EXOR  (((Ｓ０  EXOR  Ｓ−１)  AND  Ｓ−３)  EXOR  (Ｓ０  AND  Ｓ−１))
・  第３の論理演算
＝((Ｓ０  EXOR  Ｓ−１  EXOR  Ｓ−３)  AND  Ｓ−７)
AND  (((Ｓ０  EXOR  Ｓ−１)  AND  Ｓ−３)  EXOR  (Ｓ０  AND  Ｓ−１))
・  誤り系列
＝第３の論理演算結果  OR  （第１の論理演算結果  AND  第２の論理演算結果）
ただし、
Ｓ０  ＝シンドローム系列
Ｓ−１＝第１のシンドロームシフト系列
Ｓ−３＝第２のシンドロームシフト系列
Ｓ−７＝第３のシンドロームシフト系列
ＥＸＯＲ：排他的論理和を示す記号
ＡＮＤ  ：論理積を示す記号
ＯＲ    ：論理和を示す記号
【請求項６】
誤り訂正手段は、誤り系列生成手段により生成された誤り系列と符号語系列受信手段により受信された符号語系列の排他的論理和を求め、その排他的論理和の結果を誤り訂正結果として出力することを特徴とする請求項５記載の復号装置。
【請求項７】
巡回符号又は擬似巡回符号である誤り訂正符号を用いて、データの誤り訂正符号化を実施し、上記データの誤り訂正符号化結果である符号語系列を送信する誤り訂正符号化装置と、上記誤り訂正符号化装置から送信された符号語系列を受信し、上記符号語系列の誤りを訂正してデータを再生する復号装置とを備えた通信システムにおいて、上記復号装置は、上記誤り訂正符号化装置から送信された符号語系列を受信する符号語系列受信手段と、上記符号語系列受信手段により受信された符号語系列の検査多項式に応じたシフト量で上記符号語系列のビットをシフトして、複数の符号語シフト系列を生成する符号語シフト系列生成手段と、上記符号語系列受信手段により受信された符号語系列及び上記符号語シフト系列生成手段により生成された符号語シフト系列におけるビット同士の排他的論理和演算を実施してシンドローム系列を生成するシンドローム系列生成手段と、上記符号語系列受信手段により受信された符号語系列の検査多項式に応じたシフト量で上記シンドローム系列生成手段により生成されたシンドローム系列のビットをシフトして、複数のシンドロームシフト系列を生成するシンドロームシフト系列生成手段と、上記シンドローム系列生成手段により生成されたシンドローム系列及び上記シンドロームシフト系列生成手段により生成されたシンドロームシフト系列におけるビット同士の論理演算を実施して誤り系列を生成する誤り系列生成手段と、上記誤り系列生成手段により生成された誤り系列を用いて、上記符号語系列受信手段により受信された符号語系列の誤りを訂正する誤り訂正手段とから構成されていることを特徴とする通信システム。
【発明の詳細な説明】
【技術分野】
【０００１】
この発明は、誤り訂正符号を用いて誤り訂正符号化されている符号語系列を受信して、その符号語系列の誤りを訂正する復号装置と、その復号装置を実装している通信システムとに関するものである。
【背景技術】
【０００２】
誤り訂正符号を採用する従来の通信システムでは、一般的に、誤り訂正符号を用いて、データの誤り訂正符号化を実施し、上記データの誤り訂正符号化結果である符号語系列を通信路上に送信する誤り訂正符号化装置と、誤り訂正符号化装置から送信された符号語系列を受信し、その符号語系列の誤りを訂正してデータを再生する復号装置とから構成されている。
なお、復号装置は、通信路上でノイズが符号語系列に重畳されたり、攻撃者に故意の改竄などが行われたりすることによって、符号語系列に誤りが含まれる可能性があるため、その符号語系列の誤り訂正を行う。
【０００３】
誤り訂正符号化装置における一般的な符号化処理について説明する。
ただし、ここでは説明の簡単化のために、０フラットＥＧ（２，２＾２）符号で記載している。ＥＧは“Ｅｕｃｌｉｄｅａｎ  ｇｅｏｍｅｔｒｙ”の略である。
以降、断りのない場合以外は、すべてガロア体の２（ＧＦ（２）＝｛０，１｝）上で表現する。
【０００４】
ここでは、長さｋの情報系列ｕ＝（ｕｋ−１，・・・，ｕ１，ｕ０）から長さｎの符号語系列ｗ＝（ｗｎ−１，・・・，ｗ１，ｗ０）を生成するものとする。
この符号語系列ｗの生成多項式は、０フラットＥＧ（２，２＾２）符号の場合、例えば、ｎ＝１５で、Ｇ（ｘ）＝ｘ８＋ｘ７＋ｘ６＋ｘ４＋１が該当する。
この生成多項式Ｇ（ｘ）から得られる巡回行列をガウス消去法で、下記の式（１）中の行列に変換する。
【０００５】
例えば、情報系列をｕ＝（１，１，０，１，０，０，１）とすると、符号語系列ｗは、下記の式（１）のようになる。
【数１】
0004854686.tif 000002
【０００６】
式（１）の行列の中から、パリティ部である７行８列の行列のみを取り出すと、符号語系列ｗは、下記の式（２）のようになる。
【数２】
0004854686.tif 000003
【０００７】
以上から明らかなように、ソフトウェアで符号化処理する場合でも、ハードウェアで符号化処理する場合でも、下記の式（３）の行列における各列をレジスタに格納し、各列の値と情報系列ｕの排他的論理和を求めることにより、その情報系列ｕから符号語系列ｗを生成することができることが分る。
【数３】
0004854686.tif 000004
【０００８】
次に、復号装置における復号処理について説明する。
符号語系列ｗの生成多項式がＧ（ｘ）＝ｘ８＋ｘ７＋ｘ６＋ｘ４＋１である場合、検査多項式Ｈ（ｘ）は“ｘ７＋ｘ３＋ｘ＋１”となるので、符号語系列ｗの検査行列は、下記の式（４）のようになる。
【数４】
0004854686.tif 000005
【０００９】
復号装置では、誤り訂正符号化装置から送信された符号語系列ｗを受信すると、図５に示すように、その符号語系列ｗをレジスタに格納し、そのレジスタからシンドローム計算の対象ビットを抽出して、対象ビットの排他的論理和を演算する（例えば、特許文献１を参照）。
そして、復号装置は、排他的論理和の結果を多数決演算で判定する。
即ち、排他的論理和の演算結果が“１”の場合は誤り、“０”の場合は正しいと判断し、その演算結果の多数決で“１”の合計が２以下なら対応ビットは正しく、２以上なら対応ビットは誤りと判定する。
図５の例では、対応ビット毎にシンドローム計算と多数決演算を行うので、１５ビット分のシフト演算と、１６回の排他的論理和演算と、多数決演算のための３回の加算演算（４入力である為）と、１回の２以上判定用論理演算とが必要となる。
【００１０】
【特許文献１】特開平９−１３０２７１号公報（図５）
【発明の開示】
【発明が解決しようとする課題】
【００１１】
従来の復号装置は以上のように構成されているので、誤り訂正符号化装置から送信された符号語系列の誤りを訂正するには、数多くの演算を実施しなければならず、復号処理の高速化を図ることが困難であるなどの課題があった。
【００１２】
この発明は上記のような課題を解決するためになされたもので、復号処理の高速化を実現して、スループットを高めることができる復号装置及び通信システムを得ることを目的とする。
【課題を解決するための手段】
【００１３】
この発明に係る復号装置は、誤り訂正符号を用いて誤り訂正符号化されている符号語系列の検査多項式に応じたシフト量で符号語系列のビットをシフトして、複数の符号語シフト系列を生成する符号語シフト系列生成手段と、その符号語系列及び符号語シフト系列におけるビット同士の排他的論理和演算を実施してシンドローム系列を生成するシンドローム系列生成手段と、その検査多項式に応じたシフト量でシンドローム系列のビットをシフトして、複数のシンドロームシフト系列を生成するシンドロームシフト系列生成手段と、そのシンドローム系列及びシンドロームシフト系列におけるビット同士の論理演算を実施して誤り系列を生成する誤り系列生成手段とを設け、誤り訂正手段が誤り系列生成手段により生成された誤り系列を用いて、その符号語系列の誤りを訂正するようにしたものである。
【発明の効果】
【００１４】
この発明によれば、誤り訂正符号を用いて誤り訂正符号化されている符号語系列の検査多項式に応じたシフト量で符号語系列のビットをシフトして、複数の符号語シフト系列を生成する符号語シフト系列生成手段と、その符号語系列及び符号語シフト系列におけるビット同士の排他的論理和演算を実施してシンドローム系列を生成するシンドローム系列生成手段と、その検査多項式に応じたシフト量でシンドローム系列のビットをシフトして、複数のシンドロームシフト系列を生成するシンドロームシフト系列生成手段と、そのシンドローム系列及びシンドロームシフト系列におけるビット同士の論理演算を実施して誤り系列を生成する誤り系列生成手段とを設け、誤り訂正手段が誤り系列生成手段により生成された誤り系列を用いて、その符号語系列の誤りを訂正するように構成したので、復号処理の高速化を実現して、スループットを高めることができる効果がある。
【発明を実施するための最良の形態】
【００１５】
実施の形態１．
図１はこの発明の実施の形態１による通信システムを示す構成図であり、図１において、誤り訂正符号化装置１は巡回符号又は擬似巡回符号である誤り訂正符号を用いて、データである情報系列ｕの誤り訂正符号化を実施し、その情報系列ｕの誤り訂正符号化結果である符号語系列ｗを通信路２上に送信する。
復号装置３は通信路２を介して誤り訂正符号化装置１と接続されており、誤り訂正符号化装置１から送信された符号語系列を受信して、その符号語系列の誤りを訂正して情報系列ｕを再生する。
この実施の形態１では、誤り訂正符号化装置１が長さｋの情報系列ｕ＝（ｕｋ−１，・・・，ｕ１，ｕ０）から長さｎの符号語系列ｗ＝（ｗｎ−１，・・・，ｗ１，ｗ０）を生成して、その符号語系列ｗを通信路２上に送信するが、通信路２上で、エラーベクトルｅ＝（ｅｎ−１，・・・，ｅ１，ｅ０）が符号語系列ｗに重畳されることにより、復号装置３では、符号語系列として、ｙ＝ｗ＋ｅが受信されるものとする。
【００１６】
図２はこの発明の実施の形態１による復号装置を示す構成図である。
図２において、符号語系列受信部１１は誤り訂正符号化装置１から送信された符号語系列ｙ０（ｙ＝ｗ＋ｅ）を受信する処理を実施する。ｙ０の右肩における“０”は、符号語系列のビットがシフトされていないことを示している。なお、符号語系列受信部１１は符号語系列受信手段を構成している。
【００１７】
符号語シフト系列生成部１２は符号語系列受信部１１により受信された符号語系列ｙ０の検査多項式Ｈ（ｘ）に応じたシフト量（検査多項式Ｈ（ｘ）のべき数分だけシフトするシフト量）で、その符号語系列ｙ０のビットをシフトして、複数の符号語シフト系列ｙ１，ｙ３，ｙ７を生成する処理を実施する。ｙ１，ｙ３，ｙ７の右肩における“１”は符号語系列ｙ０のビットが１ビット、“３”は符号語系列ｙ０のビットが３ビット、“７”は符号語系列ｙ０のビットが７ビットだけ右にシフトされていることを示している。なお、符号語シフト系列生成部１２は符号語シフト系列生成手段を構成している。
【００１８】
シンドローム系列生成部１３は符号語系列受信部１１により受信された符号語系列ｙ０及び符号語シフト系列生成部１２により生成された符号語シフト系列ｙ１，ｙ３，ｙ７におけるビット同士の排他的論理和演算を実施してシンドローム系列ｓ０を生成する処理を実施する。ｓ０の右肩における“０”は、シンドローム系列のビットがシフトされていないことを示している。なお、シンドローム系列生成部１３はシンドローム系列生成手段を構成している。
【００１９】
シンドロームシフト系列生成部１４は符号語系列受信部１１により受信された符号語系列ｙ０の検査多項式Ｈ（ｘ）に応じたシフト量（検査多項式Ｈ（ｘ）のべき数分だけシフトするシフト量）で、そのシンドローム系列生成部１３により生成されたシンドローム系列ｓ０のビットをシフトして、複数のシンドロームシフト系列ｓ−１，ｓ−３，ｓ−７を生成する処理を実施する。ｓ−１，ｓ−３，ｓ−７の右肩における“−１”はシンドローム系列ｓ０のビットが１ビット、“−３”はシンドローム系列ｓ０のビットが３ビット、“−７”はシンドローム系列ｓ０のビットが７ビットだけ左にシフトされていることを示している。なお、シンドロームシフト系列生成部１４はシンドロームシフト系列生成手段を構成している。
【００２０】
誤り系列生成部１５はシンドローム系列生成部１３により生成されたシンドローム系列ｓ０及びシンドロームシフト系列生成部１４により生成されたシンドロームシフト系列ｓ−１，ｙ−３，ｙ−７におけるビット同士の論理演算を実施して誤り系列ＤＥＣを生成する処理を実施する。なお、誤り系列生成部１５は誤り系列生成手段を構成している。
誤り訂正部１６は誤り系列生成部１５により生成された誤り系列ＤＥＣを用いて、符号語系列受信部１１により受信された符号語系列ｙ０の誤りを訂正する処理を実施する。なお、誤り訂正部１６は誤り訂正手段を構成している。
【００２１】
次に動作について説明する。
この実施の形態１では、断りのない場合以外は、すべてガロア体の２（ＧＦ（２）＝｛０，１｝）上で表現するものとする。
【００２２】
誤り訂正符号化装置１は、巡回符号又は擬似巡回符号である誤り訂正符号を用いて、情報系列ｕの誤り訂正符号化を実施し、その情報系列ｕの誤り訂正符号化結果である符号語系列ｗを通信路２上に送信する。
即ち、誤り訂正符号化装置１は、長さｋの情報系列ｕ＝（ｕｋ−１，・・・，ｕ１，ｕ０）から長さｎの符号語系列ｗ＝（ｗｎ−１，・・・，ｗ１，ｗ０）を生成し、その符号語系列ｗを通信路２上に送信する。
この符号語系列ｗの生成多項式は、０フラットＥＧ（２，２＾２）符号の場合、例えば、ｎ＝１５で、Ｇ（ｘ）＝ｘ８＋ｘ７＋ｘ６＋ｘ４＋１が該当する。
【００２３】
通信路２上では、ノイズが符号語系列ｗに重畳されたり、攻撃者に故意の改竄などが行われたりすることによって、符号語系列ｗに誤りが含まれる可能性がある。
その符号語系列ｗに含まれる誤りを示すエラーベクトルがｅ＝（ｅｎ−１，・・・，ｅ１，ｅ０）であるとすると、復号装置３において、符号語系列ｙ＝ｗ＋ｅが受信される。
【００２４】
ここで、ＥＧ符号の検査行列Ｈは正方行列かつ巡回符号であり、復号装置３により符号語系列ｙ＝ｗ＋ｅが受信されたとすると、シンドローム系列ｓは、ｓ＝Ｈ・ｙにより求められる。
また、誤り訂正符号化装置１が誤り訂正符号化する際に用いる生成多項式Ｇ（ｘ）に対応する検査多項式Ｈ（ｘ）は、下記の通りであり、ｗｉ＋７＋ｗｉ＋３＋ｗｉ＋１＋ｗｉ＝０、ｉ＝０，１，・・・，ｎ−１という線形再帰関係が成立する。
Ｈ（ｘ）＝ｘ７＋ｘ３＋ｘ１＋ｘ０                              （５）
一方、シンドローム系列ｓｉは、下記のように表現することができる。
ｓｉ＝ｅｉ＋７＋ｅｉ＋３＋ｅｉ＋１＋ｅｉ＝０、ｉ＝０，１，・・・，ｎ−１
（６）
ただし、ｉはｎを法として考える。即ち、ｉ（ｍｏｄ  ｎ）と考える。
【００２５】
復号装置３の処理内容の詳細については後述するが、復号装置３では、上記の関係から、シンドローム系列ｓを計算するに際して、検査多項式Ｈ（ｘ）に応じたシフト量で、符号語系列ｙのビットをシフトして、検査多項式Ｈ（ｘ）の次数分の符号語シフト系列（ビットをシフトしてない符号語系列ｙ０を１個含む）を生成する。
即ち、検査多項式Ｈ（ｘ）の係数１の総数であるＪ＝４個の系列ｙ０，ｙ１，ｙ３，ｙ７を生成する。
ｙ０＝（ｙｎ−１，ｙｎ−２，・・・，ｙ１，ｙ０）
ｙ１＝（ｙ０，ｙｎ−１，・・・，ｙ２，ｙ１）
ｙ３＝（ｙ２，・・・，ｙ０，ｙｎ−１，・・・，ｙ４，ｙ３）
ｙ７＝（ｙ６，・・・，ｙ０，ｙｎ−１，・・・，ｙ８，ｙ７）
（７）
ただし、ｙｊは符号語系列ｙ０のビットをｊだけ右シフトしている符号語シフト系列（符号語ベクトル）を示している。
【００２６】
これらの系列ｙ０，ｙ１，ｙ３，ｙ７における同一要素番号のビット毎に排他的論理和演算を実施することにより、シンドローム系列ｓｉが求まる（受信している符号語系列ｙにおけるｗ成分の計算結果が“０”になる為）。
以下、シンドローム系列ｓｉのシンドロームベクトルをｓ＝（ｓ０，ｓ１，・・・，ｓｎ−１）とする。
なお、シンドローム系列ｓｉを計算するに要するシフト命令の回数は３（＝Ｊ−１＝４−１）回、排他的論理和命令の回数は３（＝Ｊ−１＝４−１）回である。
【００２７】
次に、復号装置３では、下記の式（８）に示すように、受信している符号語系列ｙの位置ｐ（ｐ＝０，１，・・・，ｎ−１）と直交するシンドロームの組み合わせをベクトルｓｐで表現して、符号語系列ｙの位置ｐのビットが誤っているか否かを判定する多数決論理復号を行う。
ｓｐ＝（ｓ−ｐ，ｓ１−ｐ，ｓ３−ｐ，ｓ７−ｐ）                      （８）
Ｅｐ＝ｍａｊ［ｓｐ，０］                                      （９）
ただし、ｍａｊ［●］は、集合●のうち、“０”または“１”のいずれか過半数を占める方の値をとる多数決関数である。
復号装置３は、多数決関数Ｅｐの値が“０”であれば位置ｐのビットが正しいと判定し、多数決関数Ｅｐの値が“１”であれば位置ｐのビットが誤りであると判定する。０フラットＥＧ（２，２＾２）符号の場合、“１”が３以上４以下で、位置ｐのビットは誤りである。
【００２８】
即ち、復号装置３では、多数決論理復号を行うに際して、シンドローム系列ｓのビットをシフトして、検査多項式Ｈ（ｘ）の次数分のシンドロームシフト系列（ビットをシフトしてないシンドローム系列ｓ０を１個含む）を生成する。
即ち、検査多項式Ｈ（ｘ）の係数１の総数であるＪ＝４個の系列ｓ０，ｓ−１，ｓ−３，ｓ−７を生成する。
ｓ０＝（ｓｎ−１，ｓｎ−２，・・・，ｓ１，ｓ０）
ｓ−１＝（ｓｎ−２，ｓｎ−３，・・・，ｓ０，ｓｎ−１）
ｓ−３＝（ｓｎ−４，・・・，ｓ０，ｓｎ−１，・・・，ｓｎ−２，ｓｎ−３）
ｓ−７＝（ｓｎ−８，・・・，ｓ０，ｓｎ−１，・・・，ｓｎ−６，ｓｎ−７）
（１０）
ただし、ｓ−ｊはシンドローム系列ｓ０のビットをｊだけ左シフトしているシンドロームシフト系列（シンドロームベクトル）を示している。
これらの系列ｓ０，ｓ−１，ｓ−３，ｓ−７における同一要素番号のビット毎に排他的論理和や論理積演算などの論理演算を実施することにより、符号語系列ｙの位置ｐのビットが誤っているか否かを示す誤りベクトルである誤り系列ＤＥＣを計算することができる。
【００２９】
以下、復号装置３の処理内容を具体的に説明する。
符号語系列受信部１１は、誤り訂正符号化装置１から送信された符号語系列ｙ＝ｗ＋ｅ、即ち、符号語系列ｙ０＝（ｙｎ−１，ｙｎ−２，・・・，ｙ１，ｙ０）を受信する。
符号語シフト系列生成部１２は、符号語系列受信部１１が符号語系列ｙ０を受信すると、検査多項式Ｈ（ｘ）に応じたシフト量で（検査多項式Ｈ（ｘ）のべき数分だけシフトするシフト量）、その符号語系列ｙ０のビットをシフトして、複数の符号語シフト系列ｙ１，ｙ３，ｙ７を生成する。
【００３０】
シンドローム系列生成部１３は、符号語シフト系列生成部１２が符号語シフト系列ｙ１，ｙ３，ｙ７を生成すると、符号語系列受信部１１により受信された符号語系列ｙ０及び符号語シフト系列生成部１２により生成された符号語シフト系列ｙ１，ｙ３，ｙ７におけるビット同士の排他的論理和演算を実施してシンドローム系列ｓ０を生成する。
以下、符号語シフト系列生成部１２及びシンドローム系列生成部１３の処理内容を具体的に説明する。
図３は符号語シフト系列生成部１２及びシンドローム系列生成部１３の処理内容を示す説明図である。
【００３１】
まず、符号語シフト系列生成部１２は、符号語系列受信部１１により受信された符号語系列ｙ０＝（ｙｎ−１，ｙｎ−２，・・・，ｙ１，ｙ０）をレジスタ（１）に格納する。
また、符号語シフト系列生成部１２は、バレルシフタを用いて、符号語系列ｙ０を右に１ビットシフトすることにより、符号語シフト系列ｙ１＝（ｙ０，ｙｎ−１，・・・，ｙ２，ｙ１）を生成して、その符号語シフト系列ｙ１をレジスタ（２）に格納する。
【００３２】
シンドローム系列生成部１３は、符号語シフト系列生成部１２が符号語系列ｙ０をレジスタ（１）に格納し、符号語シフト系列ｙ１をレジスタ（２）に格納すると、下記の式（１１）に示すようなビット単位の排他的論理和演算、即ち、レジスタ（１）に格納されている符号語系列ｙ０のビットと、レジスタ（２）に格納されている符号語シフト系列ｙ１のビットとの排他的論理和演算を実施し、その演算結果をレジスタ（１）に格納する。
ｙ０  ＥＸＯＲ  ｙ１                                        （１１）
ただし、ＥＸＯＲは排他的論理和演算を示す記号である。
【００３３】
符号語シフト系列生成部１２は、シンドローム系列生成部１３が排他的論理和演算の演算結果をレジスタ（１）に格納すると、バレルシフタを用いて、レジスタ（２）に格納されている符号語シフト系列ｙ１を右に２ビットシフトすることにより、符号語シフト系列ｙ３＝（ｙ２，・・・，ｙ０，ｙｎ−１，・・・，ｙ４，ｙ３）を生成して、その符号語シフト系列ｙ３をレジスタ（２）に格納する。
【００３４】
シンドローム系列生成部１３は、符号語シフト系列生成部１２が符号語シフト系列ｙ３をレジスタ（２）に格納すると、下記の式（１２）に示すようなビット単位の排他的論理和演算、即ち、レジスタ（１）に格納されている前回の排他的論理和演算結果のビットと、レジスタ（２）に格納されている符号語シフト系列ｙ３のビットとの排他的論理和演算を実施し、その演算結果をレジスタ（１）に格納する。
（ｙ０  ＥＸＯＲ  ｙ１）  ＥＸＯＲ  ｙ３                  （１２）
【００３５】
符号語シフト系列生成部１２は、シンドローム系列生成部１３が排他的論理和演算の演算結果をレジスタ（１）に格納すると、バレルシフタを用いて、レジスタ（２）に格納されている符号語シフト系列ｙ３を右に４ビットシフトすることにより、符号語シフト系列ｙ７＝（ｙ６，・・・，ｙ０，ｙｎ−１，・・・，ｙ８，ｙ７）を生成して、その符号語シフト系列ｙ７をレジスタ（２）に格納する。
【００３６】
シンドローム系列生成部１３は、符号語シフト系列生成部１２が符号語シフト系列ｙ７をレジスタ（２）に格納すると、下記の式（１３）に示すようなビット単位の排他的論理和演算、即ち、レジスタ（１）に格納されている前回の排他的論理和演算結果のビットと、レジスタ（２）に格納されている符号語シフト系列ｙ７のビットとの排他的論理和演算を実施し、その演算結果をシンドローム系列ｓ０＝（ｓｎ−１，ｓｎ−２，・・・，ｓ１，ｓ０）としてレジスタ（１）に格納する。
（（ｙ０  ＥＸＯＲ  ｙ１）  ＥＸＯＲ  ｙ３）  ＥＸＯＲ  ｙ７
（１３）
【００３７】
シンドロームシフト系列生成部１４は、シンドローム系列生成部１３がシンドローム系列ｓ０をレジスタ（１）に格納すると、そのレジスタ（１）からシンドローム系列ｓ０を読み出し、検査多項式Ｈ（ｘ）に応じたシフト量で（検査多項式Ｈ（ｘ）のべき数分だけシフトするシフト量）、そのシンドローム系列ｓ０のビットをシフトして、複数のシンドロームシフト系列ｓ−１，ｓ−３，ｓ−７を生成する。
【００３８】
誤り系列生成部１５は、シンドロームシフト系列生成部１４がシンドロームシフト系列ｓ−１，ｙ−３，ｙ−７を生成すると、シンドローム系列生成部１３により生成されたシンドローム系列ｓ０及びシンドロームシフト系列生成部１４により生成されたシンドロームシフト系列ｓ−１，ｙ−３，ｙ−７におけるビット同士の論理演算を実施して誤り系列ＤＥＣを生成する。
以下、シンドロームシフト系列生成部１４及び誤り系列生成部１５の処理内容を具体的に説明する。
図４はシンドロームシフト系列生成部１４及び誤り系列生成部１５の処理内容を示す説明図である。
【００３９】
まず、シンドロームシフト系列生成部１４は、図３のレジスタ（１）に格納されているシンドローム系列ｓ０＝（ｓｎ−１，ｓｎ−２，・・・，ｓ１，ｓ０）を読み出し、そのシンドローム系列ｓ０を図４のレジスタＳＵＭ（０）に格納する。
また、シンドロームシフト系列生成部１４は、バレルシフタを用いて、そのシンドローム系列ｓ０を左に１ビットシフトすることにより、シンドロームシフト系列ｓ−１＝（ｓｎ−２，ｓｎ−３，・・・，ｓ０，ｓｎ−１）を生成して、そのシンドロームシフト系列ｓ−１を図４のレジスタＳに格納する。
【００４０】
誤り系列生成部１５は、シンドロームシフト系列生成部１４がシンドローム系列ｓ０をレジスタＳＵＭ（０）に格納し、シンドロームシフト系列ｓ−１をレジスタＳに格納すると、下記の式（１４）に示すようなビット単位の排他的論理和演算、即ち、ＳＵＭ（０）に格納されているシンドローム系列ｓ０のビットと、レジスタＳに格納されているシンドロームシフト系列ｓ−１のビットとの排他的論理和演算を実施し、その演算結果をＳＵＭ（０）に格納する。
ｓ０  ＥＸＯＲ  ｓ−１                                        （１４）
【００４１】
また、誤り系列生成部１５は、式（１４）の排他的論理和演算と同時に下記の式（１５）に示すようなビット単位の論理積演算、即ち、ＳＵＭ（０）に格納されているシンドローム系列ｓ０のビットと、レジスタＳに格納されているシンドロームシフト系列ｓ−１のビットとの論理積演算を実施する。
ｓ０  ＡＮＤ  ｓ−１                                          （１５）
ただし、ＡＮＤは論理積演算を示す記号である。
【００４２】
さらに、誤り系列生成部１５は、式（１５）の論理積演算結果のビットと、レジスタＳＵＭ（１）に格納されているビット（全てのビットが“０”に初期化されている）との排他的論理和演算を実施し、その演算結果をＳＵＭ（１）に格納する。したがって、この段階では、式（１５）の論理積演算結果がＳＵＭ（１）に格納される。
【００４３】
次に、シンドロームシフト系列生成部１４は、バレルシフタを用いて、レジスタＳに格納されているシンドロームシフト系列ｓ−１を左に２ビットシフトすることにより、シンドロームシフト系列ｓ−３＝（ｓｎ−４，・・・，ｓ０，ｓｎ−１，・・・，ｓｎ−２，ｓｎ−３）を生成して、そのシンドロームシフト系列ｓ−３をレジスタＳに格納する。
【００４４】
誤り系列生成部１５は、シンドロームシフト系列生成部１４がシンドロームシフト系列ｓ−３をレジスタＳに格納すると、下記の式（１６）に示すようなビット単位の排他的論理和演算、即ち、ＳＵＭ（０）に格納されている式（１４）の排他的論理和演算結果のビットと、レジスタＳに格納されているシンドロームシフト系列ｓ−３のビットとの排他的論理和演算を実施し、その演算結果をＳＵＭ（０）に格納する。
（ｓ０  ＥＸＯＲ  ｓ−１）  ＥＸＯＲ  ｓ−３                  （１６）
【００４５】
また、誤り系列生成部１５は、式（１６）の排他的論理和演算と同時に下記の式（１７）に示すようなビット単位の論理積演算、即ち、ＳＵＭ（０）に格納されている式（１４）の排他的論理和演算結果のビットと、レジスタＳに格納されているシンドロームシフト系列ｓ−３のビットとの論理積演算を実施する。
（ｓ０  ＥＸＯＲ  ｓ−１）  ＡＮＤ  ｓ−３                    （１７）
【００４６】
さらに、誤り系列生成部１５は、下記の式（１８）に示すようなビット単位の排他的論理和演算、即ち、式（１７）の論理積演算結果のビットと、ＳＵＭ（１）に格納されている式（１５）の論理積演算結果のビットとの排他的論理和演算を実施し、その演算結果をＳＵＭ（１）に格納する。
（（ｓ０  ＥＸＯＲ  ｓ−１）  ＡＮＤ  ｓ−３）
ＥＸＯＲ  （ｓ０  ＡＮＤ  ｓ−１）
（１８）
【００４７】
次に、シンドロームシフト系列生成部１４は、バレルシフタを用いて、レジスタＳに格納されているシンドロームシフト系列ｓ−３を左に４ビットシフトすることにより、シンドロームシフト系列ｓ−７＝（ｓｎ−８，・・・，ｓ０，ｓｎ−１，・・・，ｓｎ−６，ｓｎ−７）を生成して、そのシンドロームシフト系列ｓ−７をレジスタＳに格納する。
【００４８】
誤り系列生成部１５は、シンドロームシフト系列生成部１４がシンドロームシフト系列ｓ−７をレジスタＳに格納すると、下記の式（１９）に示すようなビット単位の排他的論理和演算、即ち、ＳＵＭ（０）に格納されている式（１６）の排他的論理和演算結果のビットと、レジスタＳに格納されているシンドロームシフト系列ｓ−７のビットとの排他的論理和演算を実施し、その演算結果をＳＵＭ（０）に格納する。
（（ｓ０  ＥＸＯＲ  ｓ−１）  ＥＸＯＲ  ｓ−３）  ＥＸＯＲ  ｓ−７
（１９）
以下、式（１９）の排他的論理和演算を「第１の論理演算」と称する。
【００４９】
また、誤り系列生成部１５は、式（１９）の排他的論理和演算と同時に下記の式（２０）に示すようなビット単位の論理積演算、即ち、ＳＵＭ（０）に格納されている式（１６）の排他的論理和演算結果のビットと、レジスタＳに格納されているシンドロームシフト系列ｓ−７のビットとの論理積演算を実施する。
（（ｓ０  ＥＸＯＲ  ｓ−１）  ＥＸＯＲ  ｓ−３）  ＡＮＤ  ｓ−７
（２０）
【００５０】
さらに、誤り系列生成部１５は、下記の式（２１）に示すようなビット単位の排他的論理和演算、即ち、式（２０）の論理積演算結果のビットと、ＳＵＭ（１）に格納されている式（１８）の排他的論理和演算結果のビットとの排他的論理和演算を実施し、その演算結果をＳＵＭ（１）に格納する。
（（（ｓ０  ＥＸＯＲ  ｓ−１）  ＥＸＯＲ  ｓ−３）  ＡＮＤ  ｓ−７）
ＥＸＯＲ
（（（ｓ０  ＥＸＯＲ  ｓ−１）  ＡＮＤ  ｓ−３）
ＥＸＯＲ  （ｓ０  ＡＮＤ  ｓ−１））
（２１）
以下、式（２１）の排他的論理和演算を「第２の論理演算」と称する。
【００５１】
また、誤り系列生成部１５は、下記の式（２２）に示すようなビット単位の論理積演算、即ち、式（２０）の論理積演算結果のビットと、ＳＵＭ（１）に格納されている式（１８）の排他的論理和演算結果のビットとの論理積演算を実施し、その演算結果をＳＵＭ（２）に格納する。
（（（ｓ０  ＥＸＯＲ  ｓ−１）  ＥＸＯＲ  ｓ−３）  ＡＮＤ  ｓ−７）
ＡＮＤ
（（（ｓ０  ＥＸＯＲ  ｓ−１）  ＡＮＤ  ｓ−３）
ＥＸＯＲ  （ｓ０  ＡＮＤ  ｓ−１））
（２２）
以下、式（２２）の論理積演算を「第３の論理演算」と称する。
【００５２】
誤り系列生成部１５は、上記のようにして、第１の論理演算、第２の論理演算及び第３の論理演算を実施すると、下記に示すように、第１の論理演算結果と第２の論理演算結果との論理積を求め、その論理積結果と第３の論理演算結果との論理和を求めることにより、誤り系列ＤＥＣ（符号語系列ｙの位置ｐのビットが誤っているか否かを示す誤りベクトル）を生成する。
誤り系列ＤＥＣ
＝第３の論理演算結果  ＯＲ  （第１の論理演算結果  ＡＮＤ  第２の論理演算結果）
（２３）
【００５３】
誤り訂正部１６は、誤り系列生成部１５が誤り系列ＤＥＣを生成すると、その誤り系列ＤＥＣを用いて、符号語系列受信部１１により受信された符号語系列ｙ０の誤りを訂正する。
即ち、誤り訂正部１６は、誤り系列生成部１５により生成された誤り系列ＤＥＣと、符号語系列受信部１１により受信された符号語系列ｙ０の排他的論理和を求め、その排他的論理和の結果を誤り訂正結果ｗとして出力する。
【００５４】
以上で明らかなように、この実施の形態１によれば、誤り訂正符号を用いて誤り訂正符号化されている符号語系列の検査多項式に応じたシフト量で符号語系列のビットをシフトして、複数の符号語シフト系列を生成する符号語シフト系列生成部１２と、その符号語系列及び符号語シフト系列におけるビット同士の排他的論理和演算を実施してシンドローム系列を生成するシンドローム系列生成部１３と、その検査多項式に応じたシフト量でシンドローム系列のビットをシフトして、複数のシンドロームシフト系列を生成するシンドロームシフト系列生成部１４と、そのシンドローム系列及びシンドロームシフト系列におけるビット同士の論理演算を実施して誤り系列を生成する誤り系列生成部１５とを設け、誤り訂正部１６が誤り系列生成部１５により生成された誤り系列を用いて、その符号語系列の誤りを訂正するように構成したので、復号処理の高速化を実現して、スループットを高めることができる効果を奏する。
【００５５】
即ち、シンドローム系列ｓを計算する過程では、シフト命令の回数が３（＝Ｊ−１＝４−１）回、排他的論理和命令の回数が３（＝Ｊ−１＝４−１）回で済み、また、誤り系列ＤＥＣを生成する過程では、シフト命令の回数が３（＝Ｊ−１＝４−１）回、排他的論理和命令の回数が６（＝（Ｊ−１）×２＝（４−１）×２）回、論理積演算命令の回数が４回（＝（Ｊ−１）＋１＝（４−１）＋１）回で済み、大幅に計算回数を減らすことができる。
【００５６】
なお、この実施の形態１では、復号装置３がハードウェアで構成されているものについて示したが、復号装置３がソフトウェアで構成されているようにしてもよい。
即ち、復号装置３の処理内容を記述しているプログラムを用意して、そのプログラムをコンピュータのメモリに格納し、当該コンピュータのＣＰＵが当該メモリに格納されているプログラムを実行するようにしてもよい。
【００５７】
また、この実施の形態１では、検査多項式がｘ７＋ｘ３＋ｘ１＋ｘ０であるものについて示したが、巡回符号又は擬似巡回符号である誤り訂正符号を用いて誤り訂正符号化されている符号語系列の誤りを訂正するものであれば、上記の検査多項式に限るものではなく、他の検査多項式を適用するようにしてもよい。
【図面の簡単な説明】
【００５８】
【図１】この発明の実施の形態１による通信システムを示す構成図である。
【図２】この発明の実施の形態１による復号装置を示す構成図である。
【図３】符号語シフト系列生成部１２及びシンドローム系列生成部１３の処理内容を示す説明図である。
【図４】シンドロームシフト系列生成部１４及び誤り系列生成部１５の処理内容を示す説明図である。
【図５】従来の復号装置における論理演算を示す説明図である。
【符号の説明】
【００５９】
１  誤り訂正符号化装置、２  通信路、３  復号装置、１１  符号語系列受信部（符号語系列受信手段）、１２  符号語シフト系列生成部（符号語シフト系列生成手段）、１３  シンドローム系列生成部（シンドローム系列生成手段）、１４  シンドロームシフト系列生成部（シンドロームシフト系列生成手段）、１５  誤り系列生成部（誤り系列生成手段）、１６  誤り訂正部（誤り訂正手段）。
【図１】
0004854686.tif 000006
【図２】
0004854686.tif 000007
【図３】
0004854686.tif 000008
【図４】
0004854686.tif 000009
【図５】
0004854686.tif 000010