JP2001524274A - 短縮ファイア符号エラートラッピング復号方法および装置 - Google Patents

Abstract

(57)【要約】 復号シフトレジスタ（１２）において、受信された短縮符号語の右巡回シフトを行うエラートラッピング復号器（１０）が提供される。結果として、受信された符号語のエラーバースト部分が、短縮符号の長さ内のレジスタ（１２）において遭遇される。換言すれば、受信された語のエラーバースト部分に遭遇するために、シフトレジスタ（１２）によって必要とされる右巡回シフトの数が、短縮語の長さのオーダーである。

Description

【発明の詳細な説明】 短縮ファイア符号エラートラッピング復号方法および装置 発明の背景 発明の技術分野 本発明は、一般的にはデータ通信エラー訂正の分野に関し、特にエラートラッ ピングを用いる短縮ファイア符号を復号する方法および装置に関する。 先行技術の説明 従来の高速データ通信システムは、通常、巡回冗長検査（ｃｙｃｌｉｃ ｒｅ ｄｕｎｄａｎｃｙ ｃｈｅｃｋ）（ＣＲＣ）エラー検出符号を用いて、受信され たデータ送信エラーを検出しまた訂正する。これらのエラーは、フェージング、 チャネルノイズまたは信号干渉（例えば、周波数共同使用またはジャミングから の）のような数々の送信妨害によって引き起こされうる。 特定の巡回符号エラー検出および訂正の構成が、ターコ（Ｔｕｒｃｏ）の米国 特許第５，３８１，４２３号（以下「ターコ」とする）に開示されている。ター コは、あるクラスの巡回符号（「ファイア符号（Ｆｉｒｅ Ｃｏｄｅｓ）」とし て知られている）を用いて、体系的に、送信チャネルのバーストエラーを訂正す ることができるということを開示している。「バーストエラー」は、エラー記号 の長い列であって、ゼロでないエラー値によっていずれかの端で範囲を定められ ている。ここで、ゼロエラー値は、エラーがないことを表示するために用いられ る。 数学的には、符号語多項式を用いて、送信されるべき情報（情報語）およびフ ァイア符号を表すことができる。例えば、ファイア符号のための生成多項式は、 以下のとおり表すことができる。 ここで、ｔは、ファイア符号のバースト訂正能力として定義され、また、ｐ（Ｘ ）は、既約多項式である。項ρ「ロー（ｒｈｏ）」が、ｐ（Ｘ）の周期とし て定義される。換言すれば、ρは、ｐ（Ｘ）が（Ｘ^ρ＋１）を割り切るような最 小の整数である。また、ｔは、式（２ｔ−１）がρによって割り切れないような 正の整数である。ファイア符号の長さｎ（各ファイア符号語のビット数）は、式 （２ｔ−１）とρとの最小公倍数である。注目すべきは、式（Ｘⁿ＋１）は、フ ァイア符号生成多項式ｇ（Ｘ）で割り切れる。 送信されるべき情報語（例えば、ｋ情報ビット）は、（ｋ−１）次の多項式と して表すことができる。式｛ｕ₀，．．．，ｕ_k-1｝が情報語のビットを表すなら ば、情報語多項式は以下のように表すことができる。 以上のことから、送信されるべき符号語多項式ｃ（Ｘ）は、以下のように表す ことができる。 ここで、 式（３）および（４）より、以下のことが明らかである。 典型的な演算設定では、符号語ｃ（Ｘ）は、通信チャネルを介してバーストと して送信される。送信の間にバーストエラーが発生したと仮定すると、送信され た符号語の、エラーのあるバージョンが、チャネル受信機で受信される。その受 信された符号語ｒ（Ｘ）は、次式で表される。 ここで、ｅ（Ｘ）は、エラービットパターンである。受信された符号語ｒ（Ｘ） は、受信された語を一方向にシフトすることによって、単一のシンドロームを計 算することができ、また、受信された語を反対の方向にシフトすることによって 、エラーが訂正できる単一の多項式と考えることができる。受信された語のシン ド ロームは、次式で表すことができる。 結果として、式（７）に示されるとおり、受信された単語のシンドロームは、受 信された語のエラービットパターンによって決定される。 バーストエラー訂正に普通に用いられる装置は、エラートラッピング復号器と して知られている。その動作は、受信された語のある量の巡回シフティングにつ いて、そのバーストのエラーが、シンドロームの最終のｔビットにまで孤立させ ることができるという前提に基づいている。したがって、その前提により、エラ ートラッピング復号器は以下のとおり動作する。 受信された語の各巡回シフトについて、復号器は、その語についてのシンドロ ームを計算する。復号器が、シンドロームの最初のｎ−ｋ−ｔビットが０である ことを測定するとき、シンドロームの最後のｔビットは、シフトされ、受信され た語で生じたバーストエラーを表す。続いて、エラーは、受信された語を、対応 するビット数だけ反対の方向にシフトすることによって訂正される。 現存するエラートラッピング復号器は、通常「左巡回シフティング」を用いて 、受信された語を復号する。数学的には、長さｎの、受信された語の左巡回シフ トｒ（Ｘ）は、以下のとおり表すことができる。 そのシンドロームｓ（Ｘ）に関して、受信された語ｒ（Ｘ）は以下のように表 すことができる：項のある値ａ（Ｘ）について、 結果として、左巡回シフトされて受信された語ｒ⁽¹⁾（ｘ）についてのシンドロ ームｓ⁽¹⁾（Ｘ）は、以下のとおり導出できる。 式（Ｘⁿ＋１）がｇ（Ｘ）で割り切れるので、式（１２）を示されたとおりに導 出することができる。注目すべきは、上述の通り、エラートラッピング復号器は 、受信された語のシンドロームのみを用いて、左巡回シフトされて受信された語 のシンドロームを測定できる。この原理は、現存するエラートラッピング復号器 のバーストエラーを訂正するのにも用いられる。 バーストエラー訂正が適用される多くの場合において、標準ファイア符号を用 いて得られるファイア符号語と情報語の全長（ｎ＋ｋ）は、結果として得られる 語が、実際のシステムにとってしばしば長すぎるので、不適切であり得る。結果 として、符号語の短縮バージョンが用いられる。ファイア符号化された語を送信 用に短縮するために、いくつかの情報ビットがゼロに設定され、パリティビット が設置され、また、ゼロとされていない情報ビットとパリティビットのみが送信 される。（ｎ，ｋ）語の組合せから、１情報ビットをゼロに設定し、また、これ らの１情報ビットを送信しないことによって、（ｎ，ｋ）ファイア符号化語を、 （ｎ−１，ｋ−１）符号化語に短縮することができる。送信機および受信機は、 これらの１ビットが常にゼロであることを承諾する。 例えば、移動通信用ヨーロッパ広域システム（Ｅｕｒｏｐｅａｎ Ｇｌｏｂａ ｌ Ｓｙｓｔｅｍ ｆｏｒ Ｍｏｂｉｌｅ Ｃｏｍｍｕｎｉｃａｔｉｏｎｓ）（ ＧＳＭ）プロトコルを用いて、長さ（３０１４６３３，３０１４５９３）の標準 ファイア符号化語が長さ（２２４，１８４）に短縮できる。この短縮符号語は、 長さ１２ビット以下の全てのバーストエラーを訂正するのに用いることができる 。 現実には、（２２４，１８４）ファイア符号は、単に、最も意味のない３０１ ４４０９情報ビットに０が代入されたより長い（３０１４６３３，３０１４５９ ３）ファイア符号であるに過ぎない。代わりに、その情報の表示を、以下のよう に記述することもできる。 概念的には、ゼロなる値を有するこれらの３０１４４０９の最も意味のないビッ トは、復号器の多項式除法回路（例えば、以下図２を参照）にシフトされる最初 のビットである。しかしながら、式０ｍｏｄｇ（Ｘ）＝０であるので、この演算 は、明らかに必要ではなく、また実際の情報ビットは、チャネルと同様多項式除 法回路にもシフトされる。１８４ビット全てが多項式除法回路にシフトされると き、除法プロセスの余りはパリティ多項式ｐ（Ｘ）を与える。これらのパリティ ビットは、情報ビットに続いてチャネルにはいる。 図１Ａおよび図１Ｂは、短縮ファイア符号化語を符号化するのに用いられる従 来の２つのビット構成を示す。図１Ａに示される構成では、情報ビットとパリテ ィビットが連続している。図１Ｂに示される構成では、情報ビットとパリティビ ットは連続していない。ダミー情報ビットは送信されない。図１Ａに示される構 成の方が、図１Ｂに示される構成よりも好まれるが、それは、図１Ｂの構成は、 ２つのより短いバーストエラーへの送信において生じるバーストエラーを分離し 、それを取り扱えるように、受信機の復号器が設備されていないかも知れないか らである。 図１Ｂの場合において、ゼロビットが明らかにチャネルにシフトされるか、ま たはパリティビットが他の多項式代数技術を用いて間接的に計算されるかするが 、しかし、それは、符号化回路で必要とされる演算の数を増大する。 エラートラッピング復号器はまた、受信され、復号された最初の情報ビットが ゼロおよびエラーのないものであると仮定することにより、短縮ファイア符号化 語を復号するのに用いることができる。しかしながら、そのような復号化の構成 には問題が生じるが、それは、符号語のエラーバースト部分に遭遇するまでに、 復号器が、かなりの回数、受信された符号化語を左シフトしなければならないか らである。実際、そのようなシフトの必要となる数は、短縮されていない符号化 語の長さのオーダーである。結果として、標準ＧＳＭ符号語については、約３０ ０万の左シフト演算が必要とされ、それは、エラー訂正の遅延を著しく増大し、 それによってデータ処理量を低減するものとなる。 この問題の一つの解決法は、Ｓ．ＬｉｎおよびＤ．Ｃｏｓｔｅｌｌｏによる「 エラー制御符号化：基礎と応用（Ｅｒｒｏｒ Ｃｏｎｔｒｏｌ Ｃｏｄｉｎｇ： Ｆｕｎｄａｍｅｎｔａｌｓ ａｎｄ Ａｐｐｌｉｃａｔｉｏｎｓ）」、Ｐｒｅｎ ｔｉｃｅ Ｈａｌｌ社、ニュージャージー州イングルウッド・クリフス、１９８ ３年出版、なるテキストブックに記述されている。受信された符号語の、１ビッ トの左巡回シフトのシンドロームを計算するプロセスから、問題が生じることが 認められる。換言すれば、受信されたビットｒ_n-1-1を復号するためのシンドロ ームは、以下の等式によって示されるように、式Ｘ^n-k+1ｒ（Ｘ）を生成多項式 ｇ（Ｘ）で割った結果得られる余りに等しい。 式（１６）は、先行乗数のｒ（Ｘ）によって、次式によって示されるとおり、所 望のシンドロームを生じさせることができることを意味する。 先行乗法係数ρ（Ｘ）は次式によって与えられる。 等式１８は、シンドロームｓ^(n-k-1)（Ｘ）が、式ρ（Ｘ）ｒ（Ｘ）／ｇ（Ｘ） を実行する多項式論理回路を用いることによって得ることができることを意味す る。しかしながら、そのような構成を実行するために、比較的複雑なハードウエ アがかなりの量要求される。 逆多項式に関して、上で直接記述される除法演算を表すことによって、同様の 結果が得られる。例えば、受信された符号語について以下の式で開始する。 ｒ（Ｘ）の逆数は以下のとおり記述できる。 等式２０は、逆巡回符号を記述することに注意する。 したがって、逆巡回符号のシンドロームｒ’（Ｘ）は、受信された語のシンドロ ームに関して、次式によって記述できる。 それによって、先行乗数項ν（Ｘ）は、式：（Ｘ^kｍｏｄｇ’（Ｘ））に等しい 。しかしながら、上で開示された記述によって示唆された回路を実行することで 得られる結果と同様、この構成を実行するためにはまた、比較的複雑なハードウ エアがかなりの量必要とされる。 発明の概要 本発明によると、復号シフトレジスタにおいて、受信された短縮符号語の右巡 回シフトを行う、エラートラッピング復号器が提供される。結果として、受信さ れた符号語のエラーバースト部分が、短縮された符号の長さ内のレジスタで遭遇 される。換言すれば、受信された語のエラーバースト部分に遭遇するために、シ フトレジスタによって必要とされる右巡回シフトの数は、短縮語の長さのオーダ ーである。 本発明の重要な技術上の利点は、必要とされるエラートラッピング復号器のハ ードウエアが著しく少ない部分からなっていて、より少ない電力を消費し、従来 の復号器よりもずっと少ない費用しかかからない。 本発明の別の重要な技術上の利点は、本復号法をソフトウエアで実行するのに 、従来の方法よりも著しく少ない処理演算しか必要とされないことである。 図面の簡単な説明 本発明の方法および装置を、より完全に理解するために、以下の詳細な説明を 参照するが、そのとき添付した図面も一緒に取り扱われ、ここで、 図１Ａは、短縮ファイア符号化語を送信するために用いられる、従来のビット 構成を示すブロック図であり、 図１Ｂは、短縮ファイア符号化語を送信するために用いられる、従来の第２の ビット構成を示すブロック図であり、 図２は、本発明の好ましい実施例による、巡回右シフトすることによって短縮 符号語を復号する装置および方法を示す概略ブロック図である。 図３は、図２に示される装置および実施例による、巡回右シフトすることによ る短縮符号語を復号化する方法を図示するフロー図である。 好ましい実施例の詳細な説明 本発明の好ましい実施例およびその利点は、図１〜３の図面を参照することに よって最も良く理解されるが、その種々の図面の同様で対応する部分には、同様 の番号が用いられれている。 本質的には、本発明によると、シフトレジスタにおいて、受信された巡回（例 えば、短縮）符号語の右巡回シフトを行う、エラートラッピング復号器が提供さ れる。結果として、受信される語のエラーバスト部分は、短縮符号の長さ内で遭 遇される。換言すれば、受信される語のエラーバースト部分に遭遇するために、 シフトレジスタによって必要とされる右巡回シフトの数は、短縮語の長さのオー ダーである。他方、エラーバースト部分が遭遇されるまでの、先行技術の復号器 によって必要とされる巡回シフトの数は、短縮されていない語の長さのオーダー であり、それによって、エラー訂正プロセスに著しい遅延が生じる。結果として 、本発明の右シフトする復号器では、先行技術の復号器よりもかなり少ないハー ドウエアしか必要とされない。 本発明の好ましい実施例によると、受信された右シフトされた語のシンドロー ムｒ（Ｘ）は、以下のように測定される。受信された語の右巡回シフトを一回行 うこと、ｒ（Ｘ）は、（ｎ−１）回の左巡回シフトを行うことと同じ演算であり 、ここで「ｎ」は、符号語長である。結果として、以下の式が得られる。 ｒ（Ｘ）のシンドロームはｓ（Ｘ）である。換言すれば、あるａ（Ｘ）について 、 語ｒ^(-1)（Ｘ）のシンドロームｓ^(-1)（Ｘ）が続いて以下のように計算される。 式（２８）へと続くのは、Ｘⁿ＋１がｇ（Ｘ）によって割り切れるからである。 シンドロームｓ（Ｘ）は、多項式の形となる。 したがって、巡回して右シフトされる語のシンドロームｓ^(-1)（Ｘ）は、以下の ように導出される。式（３４）によって確認されるとおり、巡回右シフトされる語のシンドロームは 、 受信される語の本来のシンドロームのより高いオーダーのビットをシフトし、か つマスク語（ｓ₀Ｘ^n-1ｍｏｄ ｇ（Ｘ））を加えることによって、測定できる。 そのようなものであるので、マスク語（ｓ₀Ｘ^n-1ｍｏｄ ｇ（Ｘ））は、ビット ｓ₀が「ゼロ」であるならばゼロに、ビットｓ₀が「１」であるなら、（Ｘ^n-1ｍ ｏｄ ｇ（Ｘ））に等しい。項（Ｘ^n-1ｍｏｄ ｇ（Ｘ））について所定の値を 即座に計算して、復号器のマスクレジスタ（以下に記述される）で用いるために 蓄積することができる。結果として、従来の復号器に比べて、受信された語Ｒ（ Ｘ）を処理するために必要とされる計算は、短縮された語のオーダーにある数に まで著しく低減される。式（３４）に示されるような右シフトされた語のシンド ロームを用いて、本復号器は、受信された語を復号し、また訂正のためのエラー バーストを孤立させることができる。エラー訂正の演算は、レジスタからの受信 された語を、エラーバーストを取り除くのに必要なビットの数だけシフトするこ とによって行うことができる。 図２は、本発明の好ましい実施例による、巡回右シフトすることによって短縮 符号語を復号する装置および方法を示す概略ブロック図である。ここで用いられ ているとおり、「右シフトする」という語は、図２において横移動されるデータ の方向を示す矢印に関係して定義される。結果として、図２において示される構 造が、水平に反転されるべきものであるなら、ここで記述される「右シフトする 」という概念は、現実には、「左シフトする」ことである。換言すれば、本発明 は、一つのシフトする方向に限定することを意図したものではない。 図２に関して、符号シフトレジスタ１２を含む復号器１０が示されている。レ ジスタ１２の入力は、復号受信機（はっきりと示されていない）の前方端の出力 に接続される。受信される符号語ｒ（Ｘ）のビットは、符号シフトレジスタ１２ へと右シフトされる。この代表的な実施例において、符号シフトレジスタ１２は 、２２４ビットの長さである。レジスタ１２の最も右側の複数のビット位置は、 データライン１３によって、バースト検出および訂正回路１４に接続される。受 信される語の（以下に記述されるバースト検出回路１６からの）エラーバースト の長さを測定する際に、加算器２６で、バースト訂正回路１４は、エラーバース トビットを符号シフトレジスタ１２の受信語ビットに加算する。受信語ビットプ ラ スバースト訂正ビットが、右に、かつ、加算器２６を経て符号シフトレジスタ１ ２からシフトされ、それによって、エラー訂正された語を受信機の次の段階に通 過させる。 複数のデータライン（はっきりと示されていない）は、バースト検出回路１６ の出力を、バースト訂正回路１４の入力に接続する。明瞭化のためにこれらの具 体的な特徴は図示されておらず、バースト検出および訂正回路１６および１４は 、図２の一つのブロックで組み合わされている。上の式（３４）に示されるとお り、右シフトされる受信語のシンドロームｓ^(-1)（Ｘ）によって、バースト検出 回路１６は、シンドロームレジスタ１８の最も右の位置に、長さｔ以下のバース トがあることを検出する。シンドロームレジスタ１８は、語Ｒ（Ｘ）のシンドロ ームを含むように構成される。このシンドロームは、前述されたとおり、リン（ Ｌｉｎ）およびコステロ（Ｃｏｓｔｅｌｌｏ）の教示にしたがって計算すること ができる。シンドロームレジスタ１８の出力は、データリード１７によって、バ ースト検出回路１６の対応する入力に接続される。複数の加算器（またはＸＯＲ ゲート）２０の各々は、データリード１９によって、シンドロームレジスタ１８ の対応するビット位置に接続される。マスクレジスタ２２の複数の出力２１の各 々は、加算器２０の各々に接続される。マスクレジスタ２２は、マスク語（ｓ₀ Ｘ^(n-1)ｍｏｄ ｇ（Ｘ））のビットを含むように構成される。符号レジスタ１ ２の出力は、データライン２３によって、加算器２６および受信機の次の段階に 結合される。データライン２５は、シンドロームレジスタ１８の最も右のビット を加算器２０に結合する。図２に示される回路およびレジスタの各々の動作を同 期するためのシステムクロック２４が、そのような回路およびレジスタの各々に 接続される。 動作中において、受信された短縮符号語は、符号レジスタ１２およびシンドロ ームレジスタ１８に右シフトされる。受信された語は、データライン２３上の符 号レジスタ１２から右シフトされる。上の等式３４に関して、シンドロームレジ スタ１８の最も右の位置にあるビットが「ゼロ」である限り、マスクレジスタ２ ２のマスク値はゼロに等しい。換言すれば、マスク値がゼロに等しい（ｓ₀＝０ ）ならば、右シフトされる語の（レジスタ１８の）シンドロームは、（ｓ₁＋ ｓ₂Ｘ＋・・・＋ｓ_n-k-1Ｘ^n-k-2）に等しい。結果として、符号シフトレジスタ １２の語は、一旦右にシフトアウトされる。しかしながら、シンドロームレジス タ１８からの出力ビットが「１」であるとき、加算器２０は使用可能であって、 マスクレジスタ２２のマスク値は、シンドロームレジスタ１８のシンドロームの 値に加えられる。換言すれば、ｓ₀＝１であるならば、（シンドロームレジスタ １８の）シンドロームは、数量（Ｓ₁＋Ｓ₂Ｘ＋・・・＋ｓ_n-k-1Ｘ^n-k-2）および （Ｘ^n-1ｍｏｄ ｇ（Ｘ））なる所定の値の和に等しい。結果として、符号シフ トレジスタ１２における語は、一旦シフトされる。 シンドロームレジスタ１８のシンドロームビットは、バースト検出回路１６の 対応するビット位置に結合される。シンドロームレジスタ１８のビットパターン は、バースト検出回路１６の対応するビット位置に結合される。バースト検出回 路１６の最も上のｔビットは、バースト訂正回路１４の対応するビット位置に結 合される。長さｔ以下のバーストが検出されるとき、バーストエラー訂正回路１ ４は、これらのビットを符号レジスタ１２の語に加え、また、エラー訂正プロセ スはこのように完了される。符号レジスタ１２のビットの剰余は、結果として、 シフトアウトされる。 図３は、図２に示される復号装置および実施例による、巡回右シフトをするこ とによって短縮符号語を復号する方法を図示するフロー図である。図３に示され る方法（１００）は、ソフトウエアで実行することができ、それはマイクロプロ セッサー（はっきりとは示されていない）の制御のもとで動作する。本質的には 、訂正できるエラーパターンは、シンドロームレジスタの（ｎ−ｋ−１−ｔ）の 最も重要な位置のゼロの列を有する。（ｔ）の最も意味のないビットは、訂正可 能なエラーパターンを形成し、それは、少なくとも一つのゼロでない要素を有す る。ＧＳＭの実施例について、ｔ＝１２，ｎ＝２２４およびｋ＝１８４である。 特に、ステップ１０４では、受信された短縮符号語ｒ（Ｘ）は、符号レジスタ １２（図２）にロードされる（右シフトされる）。符号レジスタはｎビット長で ある。右シフトされる語のシンドロームｓ（Ｘ）は、受信される符号語ｒ（Ｘ） の全ての右シフトについて計算される。ステップ１０６では、ビットカウンター （はっきりとは示されていない）は、ゼロに設定される。受信された符号語ｒ （Ｘ）からのビットの符号レジスタへの右シフトの各々は、ビットカウンターを １増加させる。シンドロームレジスタ１８の最も意味のないビットは、加算器２ ０を使用可能とするために用いられる。ステップ１０８では、受信された符号語 のシンドロームが計算される。ステップ１１０では、シンドロームレジスタの内 容が分析されて、そのレジスタに１２ビットエラーパターン（例えば、ＧＳＭに ついての）があるか、およびレジスタのその他全てのビットがゼロであるか測定 する。もしそうでないならば、エラーパターンがないと想定され、メッセージベ クトルｕ（Ｘ）が受信機の次の段階にシフトアウトされる。ステップ１１４では 、復号器は次の受信される符号語ｒ（Ｘ）を待つ。 しかしながら、ステップ１１０にて、シンドロームレジスタの内容が、１２ビ ットエラーパターンを含んでおり、他の全てのビットがゼロであるならば、ステ ップ１１６にて、訂正可能なエラーパターンが検出されていると想定される。ス テップ１１８では、加算器２０は使用不可能であり、シンドロームレジスタの内 容（エラーパターンを含む）が、受信される符号語ｒ（Ｘ）に、それが符号語レ ジスタから右シフトされるときに加えられる。ステップ１１８では、１２ビット エラーパターンは、そのビット位置（ビットカウンター値＋１）で開始する受信 された符号語に加えられる。ステップ１１４では、復号器は、次の受信される符 号語ｒ（Ｘ）を待つ。別の符号語ｒ（Ｘ）が受信されるならば、フローはステッ プ１０４に戻る。 ステップ１１６にて、シンドロームレジスタに、１２ビットエラーパターンが ない（他の全てのビットがゼロに等しくて）と測定されるならば、ステップ１２ ０にて、ビットカウンターの値が分析されて、それが（ｎ−１）に等しいかどう か測定する。もしそうであり、また訂正可能なビットパターンが検出されていな いならば、ステップ１２２にて、システムは「フレーム削除」が発生したことを 宣言し、また、フローはステップ１１４に進んで次の受信される符号語を待つ。 ステップ１２０にて、ビットカウントが（ｎ−１）ではないと測定されるなら ば、ステップ１２４にて、シンドロームレジスタが分析され、最も意味のないビ ットが「１」に等しいかどうか測定する。もしそうであるならば、シンドローム レジスタのビットは、最も意味のないビットに向けて右シフトされ、また、マス クレジスタ２２に蓄積される所定のマスク語（Ｘ^n-1）ｍｏｄｇ（Ｘ）に加えら れる。この実施例では、マスク語（Ｘ^n-1）ｍｏｄｇ（Ｘ）は、Ｘ³⁹＋Ｘ²⁵＋Ｘ^{2 2} ＋Ｘ¹⁶＋Ｘ²である。ステップ１３０では、ビットカウンターが１増加される。 しかしながら、ステップ１２４にて、シンドロームレジスタの最も意味のないビ ットが「１」に等しくないならば、ステップ１２８にて、シンドロームレジスタ の内容が、最も意味のないビットに向けて右シフトされ、そしてそれはこうして 削除される。ステップ１３０では、ビットカウンターは１増加され、そしてフロ ーはステップ１１６に戻る。 本発明の方法および装置の好ましい実施例が添付の図面に例示され、また、上 述の詳細な説明に記述されているが、本発明は、開示された実施例に限定される ものではなく、以下の請求の範囲で説明され、定義されるような発明の精神から 逸脱することなく、数々の再配列、変更および置き換えが可能であるということ が理解される。

【手続補正書】特許法第１８４条の８第１項 【提出日】平成１０年１１月６日（１９９８．１１．６） 【補正内容】 ｒ（Ｘ）の逆数は以下のとおり記述できる。 等式２０は、逆巡回符号を記述することに注意する。 したがって、逆巡回符号のシンドロームｒ’（Ｘ）は、受信された語のシンドロ ームに関して、次式によって記述できる。 それによって、先行乗数項ν（Ｘ）は、式：（Ｘ^kｍｏｄｇ’（Ｘ））に等しい 。しかしながら、上で開示された記述によって示唆された回路を実行することで 得られる結果と同様、この構成を実行するためにはまた、比較的複雑なハードウ エアがかなりの量必要とされる。 ＩＢＭ技術開示報告（ＩＢＭ Ｔｅｃｈｎｉｃａｌ Ｄｉｓｃｌｏｓｕｒｅ Ｂｕｌｌｅｔｉｎ）第３０巻、ナンバー５、１９８７年１０月、第４１−４４頁 の「反対回転ファイア符号ＥＣＣ訂正（Ｒｅｖｅｒｓｅ Ｒｏｔａｔｉｏｎ Ｆ ｉｒｅ Ｃｏｄｅ ＥＣＣ Ｃｏｒｒｅｃｔｉｏｎ）」において、ファイア符号 を用いるエラー訂正が開示されている。シンドロームをシフトする方向が反転さ れ、また、生成多項式の反転が用いられている。このやり方では、符号語の検索 が、開始時ではなくファイア符号の自然長の端で始まり、エラーを見つけるのに シフトする必要がより少ないものとなっている。 発明の概要 本発明によると、復号シフトレジスタにおいて、受信された短縮符号語の右巡 回シフトを行う、エラートラッピング復号器が提供される。結果として、受信さ れた符号語のエラーバースト部分が、短縮された符号の長さ内のレジスタで遭遇 される。換言すれば、受信された語のエラーバースト部分に遭遇するために、シ フトレジスタによって必要とされる右巡回シフトの数は、短縮語の長さのオーダ ーである。 本発明の重要な技術上の利点は、必要とされるエラートラッピング復号器のハ ードウエアが著しく少ない部分からなっていて、より少ない電力を消費し、従来 の復号器よりもずっと少ない費用しかかからない。 【手続補正書】特許法第１８４条の８第１項 【提出日】平成１１年２月２６日（１９９９．２．２６） 【補正内容】 請求の範囲 1. 巡回符号語を復号する方法であって、 前記巡回符号語を第１の蓄積位置にローディングするステップと、 前記巡回符号語のシンドロームを計算するステップと、 前記シンドロームを第２の蓄積位置にローディングするステップと、 前記シンドロームの最下位ビットが所定の値に等しいかどうか判定するステッ プと、 前記最下位ビットが前記所定の値に等しくないときに、前記第２の蓄積位置の 内容を前記最下位ビットに向けてシフトするステップと、 前記最下位ビットが前記所定の値に等しいときに、前記第２の蓄積位置の前記 内容を前記最下位ビットに向けてシフトし、かつ前記内容を所定のマスク語に加 えるステップと、 を含む方法。 2. 前記第１の蓄積位置がシフトレジスタである、請求項１に記載の方法。 3. 前記巡回符号語をローディングする前記ステップが、前記受信された符号 語を前記第１の蓄積位置に右シフトするステップを含む、請求項１に記載の方法 。 4. 前記所定の値が１に等しい、請求項１に記載の方法。 5. 前記巡回符号語がｒ（Ｘ）に等しいベクトルであり、前記第１の蓄積位置 がｎビット長であり、前記マスク語が（Ｘ^n-1）ｍｏｄｇ（Ｘ）に等しい、請求 項１に記載の方法。 6. 前記巡回符号語がファイア符号化語からなる、請求項１に記載の方法。 7. 前記巡回符号語が短縮巡回符号からなる、請求項１に記載の方法。 8.復号されるべき符号語を蓄積する符号語記憶手段と、 前記符号語のシンドロームを蓄積する、前記符号語記憶手段と関連するシンド ローム記憶手段と、 前記シンドローム記憶手段における所定のビット値の検出に応答して、所定の 語を蓄積し、かつ前記所定の語と前記シンドロームとの加算を可能とするマスク 語手段と、 を含むファイア符号復号器。 9. 前記符号語記憶手段がｎビット累算レジスタを含む、請求項８のファイア 符号復号器。 10．前記シンドローム記憶手段がレジスタを含む、請求項８のファイア符号復 号器。 11．前記マスク語手段が複数の加算器を含み、その加算器の各々が、前記シン ドローム記憶手段の各々のビット位置と前記マスク語手段との問に接続される、 請求項８のファイア符号復号器。 12．前記所定の語が（Ｘ^n-1）ｍｏｄｇ（Ｘ）を含む、請求項８のファイア符 号復号器。 13．前記所定の語が（Ｘ³⁹＋Ｘ²⁵＋Ｘ²²＋Ｘ¹⁶＋Ｘ²）を含み、かつ前記シン ドローム記憶手段の内容が１２ビットエラーパターンを含む、請求項８のファイ ア符号復号器。 14．前記所定のビット値が「１」を含む、請求項８のファイア符号復号器。 15．前記ファイア符号が短縮巡回符号を含む、請求項８のファイア符号復号器 。 16．前記符号語記憶手段、前記シンドローム記憶手段および前記マスク語手段 のうち少なくとも一つがシフトレジスタを含む、請求項８のファイア符号復号器 。

───────────────────────────────────────────────────── フロントページの続き (81)指定国 ＥＰ(ＡＴ，ＢＥ，ＣＨ，ＤＥ， ＤＫ，ＥＳ，ＦＩ，ＦＲ，ＧＢ，ＧＲ，ＩＥ，ＩＴ，Ｌ Ｕ，ＭＣ，ＮＬ，ＰＴ，ＳＥ)，ＯＡ(ＢＦ，ＢＪ，ＣＦ ，ＣＧ，ＣＩ，ＣＭ，ＧＡ，ＧＮ，ＭＬ，ＭＲ，ＮＥ， ＳＮ，ＴＤ，ＴＧ)，ＡＰ(ＧＨ，ＫＥ，ＬＳ，ＭＷ，Ｓ Ｄ，ＳＺ，ＵＧ，ＺＷ)，ＥＡ(ＡＭ，ＡＺ，ＢＹ，ＫＧ ，ＫＺ，ＭＤ，ＲＵ，ＴＪ，ＴＭ)，ＡＬ，ＡＭ，ＡＴ ，ＡＵ，ＡＺ，ＢＡ，ＢＢ，ＢＧ，ＢＲ，ＢＹ，ＣＡ， ＣＨ，ＣＮ，ＣＵ，ＣＺ，ＤＥ，ＤＫ，ＥＥ，ＥＳ，Ｆ Ｉ，ＧＢ，ＧＥ，ＧＨ，ＨＵ，ＩＤ，ＩＬ，ＩＳ，ＪＰ ，ＫＥ，ＫＧ，ＫＰ，ＫＲ，ＫＺ，ＬＣ，ＬＫ，ＬＲ， ＬＳ，ＬＴ，ＬＵ，ＬＶ，ＭＤ，ＭＧ，ＭＫ，ＭＮ，Ｍ Ｗ，ＭＸ，ＮＯ，ＮＺ，ＰＬ，ＰＴ，ＲＯ，ＲＵ，ＳＤ ，ＳＥ，ＳＧ，ＳＩ，ＳＫ，ＳＬ，ＴＪ，ＴＭ，ＴＲ， ＴＴ，ＵＡ，ＵＧ，ＵＺ，ＶＮ，ＹＵ，ＺＷ

Claims (1)

1. 【特許請求の範囲】 1. 巡回符号語を復号する方法であって、 前記巡回符号語を第１の蓄積位置にローディングするステップと、 前記巡回符号語のシンドロームを計算するステップと、 前記シンドロームを第２の蓄積位置にローディングするステップと、 前記シンドロームの最下位ビットが所定の値に等しいかどうか判定するステッ プと、 前記最下位ビットが前記所定の値に等しくないときに、前記第２の蓄積位置の 内容を前記最下位ビットに向けてシフトするステップと、 前記最下位ビットが前記所定の値に等しいときに、前記第２の蓄積位置の前記 内容を前記最下位ビットに向けてシフトし、かつ前記内容をマスク語に加えるス テップと、 を含む方法。 2. 前記第１の蓄積位置がシフトレジスタである、請求項１に記載の方法。 3. 前記巡回符号語をローディングする前記ステップが、前記受信された符号 語を前記第１の蓄積位置に右シフトするステップを含む、請求項１に記載の方法 。 4. 前記所定の値が１に等しい、請求項１に記載の方法。 5. 前記巡回符号語がｒ（Ｘ）に等しいベクトルであり、前記第１の蓄積位置 がｎビット長であり、前記マスク語が（Ｘ^n-1）ｍｏｄｇ（Ｘ）に等しい、請求 項１に記載の方法。 6. 前記巡回符号語がファイア符号化語からなる、請求項１に記載の方法。 7. 前記巡回符号語が短縮巡回符号からなる、請求項１に記載の方法。 8. 復号されるべき符号語を蓄積する符号語記憶手段と、 前記符号語のシンドロームを蓄積する、前記符号語記憶手段と関連するシンド ローム記憶手段と、 前記シンドローム記憶手段における所定のビット値の検出に応答して、所定の 語を蓄積し、かつ前記所定の語と前記シンドロームとの加算を可能とするマスク 語手段と、 を含むファイア符号復号器。 9. 前記符号語記憶手段がｎビット累算レジスタを含む、請求項８のファイア 符号復号器。 10．前記シンドローム記憶手段がレジスタを含む、請求項８のファイア符号復 号器。 11．前記マスク語手段が複数の加算器を含み、その加算器の各々が、前記シン ドローム記憶手段の各々のビット位置と前記マスク語手段との間に接続される、 請求項８のファイア符号復号器。 12．前記所定の語が（Ｘ^n-1）ｍｏｄｇ（Ｘ）を含む、請求項８のファイア符 号復号器。 13．前記所定の語が（Ｘ³⁹＋Ｘ²⁵＋Ｘ²²＋Ｘ¹⁶＋Ｘ²）を含み、かつ前記シン ドローム記憶手段の内容が１２ビットエラーパターンを含む、請求項８のファイ ア符号復号器。 14．前記所定のビット値が「１」を含む、請求項８のファイア符号復号器。 15．前記ファイア符号が短縮巡回符号を含む、請求項８のファイア符号復号器 。 16．復号されるべき符号語を蓄積する第１の蓄積位置と、 前記符号語のシンドロームを蓄積する、前記第１の蓄積位置と関連する第２の 蓄積位置と、 前記第２の蓄積位置における所定の値の検出に応答して、所定の語を蓄積し、 かつその所定の語の前記シンドロームとの加算を可能とする第３の蓄積位置と、 を含むファイア符号復号器。 17．前記ファイア符号が短縮巡回符号を含む、請求項１６のファイア符号復号 器。 18．前記第１，第２および第３の蓄積位置の少なくとも一つがシフトレジスタ を含む、請求項１６のファイア符号復号器。 19．前記所定の値が論理「１」を含む、請求項１６のファイア符号復号器。