JP2000295116A - 誤り修正符号化方法 - Google Patents
誤り修正符号化方法Info
- Publication number
- JP2000295116A JP2000295116A JP2000069880A JP2000069880A JP2000295116A JP 2000295116 A JP2000295116 A JP 2000295116A JP 2000069880 A JP2000069880 A JP 2000069880A JP 2000069880 A JP2000069880 A JP 2000069880A JP 2000295116 A JP2000295116 A JP 2000295116A
- Authority
- JP
- Japan
- Prior art keywords
- multiplication
- elements
- bits
- polynomial
- multiplications
- Prior art date
- Legal status (The legal status is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the status listed.)
- Abandoned
Links
Classifications
-
- H—ELECTRICITY
- H03—ELECTRONIC CIRCUITRY
- H03M—CODING; DECODING; CODE CONVERSION IN GENERAL
- H03M13/00—Coding, decoding or code conversion, for error detection or error correction; Coding theory basic assumptions; Coding bounds; Error probability evaluation methods; Channel models; Simulation or testing of codes
- H03M13/03—Error detection or forward error correction by redundancy in data representation, i.e. code words containing more digits than the source words
- H03M13/05—Error detection or forward error correction by redundancy in data representation, i.e. code words containing more digits than the source words using block codes, i.e. a predetermined number of check bits joined to a predetermined number of information bits
- H03M13/13—Linear codes
- H03M13/15—Cyclic codes, i.e. cyclic shifts of codewords produce other codewords, e.g. codes defined by a generator polynomial, Bose-Chaudhuri-Hocquenghem [BCH] codes
- H03M13/151—Cyclic codes, i.e. cyclic shifts of codewords produce other codewords, e.g. codes defined by a generator polynomial, Bose-Chaudhuri-Hocquenghem [BCH] codes using error location or error correction polynomials
- H03M13/158—Finite field arithmetic processing
-
- G—PHYSICS
- G06—COMPUTING OR CALCULATING; COUNTING
- G06F—ELECTRIC DIGITAL DATA PROCESSING
- G06F7/00—Methods or arrangements for processing data by operating upon the order or content of the data handled
- G06F7/60—Methods or arrangements for performing computations using a digital non-denominational number representation, i.e. number representation without radix; Computing devices using combinations of denominational and non-denominational quantity representations, e.g. using difunction pulse trains, STEELE computers, phase computers
- G06F7/72—Methods or arrangements for performing computations using a digital non-denominational number representation, i.e. number representation without radix; Computing devices using combinations of denominational and non-denominational quantity representations, e.g. using difunction pulse trains, STEELE computers, phase computers using residue arithmetic
- G06F7/724—Finite field arithmetic
-
- H—ELECTRICITY
- H03—ELECTRONIC CIRCUITRY
- H03M—CODING; DECODING; CODE CONVERSION IN GENERAL
- H03M13/00—Coding, decoding or code conversion, for error detection or error correction; Coding theory basic assumptions; Coding bounds; Error probability evaluation methods; Channel models; Simulation or testing of codes
- H03M13/03—Error detection or forward error correction by redundancy in data representation, i.e. code words containing more digits than the source words
- H03M13/05—Error detection or forward error correction by redundancy in data representation, i.e. code words containing more digits than the source words using block codes, i.e. a predetermined number of check bits joined to a predetermined number of information bits
- H03M13/13—Linear codes
- H03M13/15—Cyclic codes, i.e. cyclic shifts of codewords produce other codewords, e.g. codes defined by a generator polynomial, Bose-Chaudhuri-Hocquenghem [BCH] codes
- H03M13/151—Cyclic codes, i.e. cyclic shifts of codewords produce other codewords, e.g. codes defined by a generator polynomial, Bose-Chaudhuri-Hocquenghem [BCH] codes using error location or error correction polynomials
- H03M13/1515—Reed-Solomon codes
-
- H—ELECTRICITY
- H03—ELECTRONIC CIRCUITRY
- H03M—CODING; DECODING; CODE CONVERSION IN GENERAL
- H03M13/00—Coding, decoding or code conversion, for error detection or error correction; Coding theory basic assumptions; Coding bounds; Error probability evaluation methods; Channel models; Simulation or testing of codes
- H03M13/03—Error detection or forward error correction by redundancy in data representation, i.e. code words containing more digits than the source words
- H03M13/05—Error detection or forward error correction by redundancy in data representation, i.e. code words containing more digits than the source words using block codes, i.e. a predetermined number of check bits joined to a predetermined number of information bits
- H03M13/13—Linear codes
- H03M13/15—Cyclic codes, i.e. cyclic shifts of codewords produce other codewords, e.g. codes defined by a generator polynomial, Bose-Chaudhuri-Hocquenghem [BCH] codes
- H03M13/151—Cyclic codes, i.e. cyclic shifts of codewords produce other codewords, e.g. codes defined by a generator polynomial, Bose-Chaudhuri-Hocquenghem [BCH] codes using error location or error correction polynomials
- H03M13/157—Polynomial evaluation, i.e. determination of a polynomial sum at a given value
-
- H—ELECTRICITY
- H03—ELECTRONIC CIRCUITRY
- H03M—CODING; DECODING; CODE CONVERSION IN GENERAL
- H03M13/00—Coding, decoding or code conversion, for error detection or error correction; Coding theory basic assumptions; Coding bounds; Error probability evaluation methods; Channel models; Simulation or testing of codes
- H03M13/03—Error detection or forward error correction by redundancy in data representation, i.e. code words containing more digits than the source words
- H03M13/05—Error detection or forward error correction by redundancy in data representation, i.e. code words containing more digits than the source words using block codes, i.e. a predetermined number of check bits joined to a predetermined number of information bits
- H03M13/13—Linear codes
- H03M13/15—Cyclic codes, i.e. cyclic shifts of codewords produce other codewords, e.g. codes defined by a generator polynomial, Bose-Chaudhuri-Hocquenghem [BCH] codes
- H03M13/159—Remainder calculation, e.g. for encoding and syndrome calculation
-
- H—ELECTRICITY
- H03—ELECTRONIC CIRCUITRY
- H03M—CODING; DECODING; CODE CONVERSION IN GENERAL
- H03M13/00—Coding, decoding or code conversion, for error detection or error correction; Coding theory basic assumptions; Coding bounds; Error probability evaluation methods; Channel models; Simulation or testing of codes
- H03M13/27—Coding, decoding or code conversion, for error detection or error correction; Coding theory basic assumptions; Coding bounds; Error probability evaluation methods; Channel models; Simulation or testing of codes using interleaving techniques
- H03M13/2735—Interleaver using powers of a primitive element, e.g. Galois field [GF] interleaver
-
- H—ELECTRICITY
- H03—ELECTRONIC CIRCUITRY
- H03M—CODING; DECODING; CODE CONVERSION IN GENERAL
- H03M13/00—Coding, decoding or code conversion, for error detection or error correction; Coding theory basic assumptions; Coding bounds; Error probability evaluation methods; Channel models; Simulation or testing of codes
- H03M13/37—Decoding methods or techniques, not specific to the particular type of coding provided for in groups H03M13/03 - H03M13/35
- H03M13/39—Sequence estimation, i.e. using statistical methods for the reconstruction of the original codes
- H03M13/41—Sequence estimation, i.e. using statistical methods for the reconstruction of the original codes using the Viterbi algorithm or Viterbi processors
-
- H—ELECTRICITY
- H03—ELECTRONIC CIRCUITRY
- H03M—CODING; DECODING; CODE CONVERSION IN GENERAL
- H03M13/00—Coding, decoding or code conversion, for error detection or error correction; Coding theory basic assumptions; Coding bounds; Error probability evaluation methods; Channel models; Simulation or testing of codes
- H03M13/65—Purpose and implementation aspects
- H03M13/6502—Reduction of hardware complexity or efficient processing
- H03M13/6505—Memory efficient implementations
Landscapes
- Physics & Mathematics (AREA)
- Engineering & Computer Science (AREA)
- Theoretical Computer Science (AREA)
- Mathematical Physics (AREA)
- Probability & Statistics with Applications (AREA)
- General Physics & Mathematics (AREA)
- Pure & Applied Mathematics (AREA)
- Algebra (AREA)
- Mathematical Optimization (AREA)
- Mathematical Analysis (AREA)
- Computational Mathematics (AREA)
- Computing Systems (AREA)
- General Engineering & Computer Science (AREA)
- Error Detection And Correction (AREA)
- Detection And Prevention Of Errors In Transmission (AREA)
- Detection And Correction Of Errors (AREA)
Abstract
(57)【要約】 （修正有）
【課題】 ガロア体演算を効率的に実現するための乗算
表使用に於て、メモリ容量と消費電力を低減する。 【解決手段】 リード・ソロモンエンコーダにおけるガ
ロア体乗算処理において、全乗算ルックアップテーブル
からの列の選択（デシメート）と効率的なアクセスのた
めの再順序付け（インタリーブ）とによってルックアッ
プテーブルを構築し、リード・ソロモンコード生成多項
式の係数は保持する列、乗算ルックアップテーブル内容
及び順序を決定する。
表使用に於て、メモリ容量と消費電力を低減する。 【解決手段】 リード・ソロモンエンコーダにおけるガ
ロア体乗算処理において、全乗算ルックアップテーブル
からの列の選択（デシメート）と効率的なアクセスのた
めの再順序付け（インタリーブ）とによってルックアッ
プテーブルを構築し、リード・ソロモンコード生成多項
式の係数は保持する列、乗算ルックアップテーブル内容
及び順序を決定する。
Description
【０００１】
【発明の属する技術分野】本発明は電子デバイスに関
し、詳述すれば、誤り修正符号化に関する。
し、詳述すれば、誤り修正符号化に関する。
【０００２】
【従来の技術】ディジタル通信及び記憶システムは、伝
送または記憶媒体に起因する誤りを解消するために、典
型的に誤り修正符号化（コーディング）を行なってい
る。順方向誤り修正符号化（ＦＥＣ）システムは、受信
機が受信した信号だけを使用して誤りを検出して修正で
きるように、伝送される信号に冗長度を付加する。これ
により、受信機は送信機に対して再伝送を要求する必要
がなくなる。
送または記憶媒体に起因する誤りを解消するために、典
型的に誤り修正符号化（コーディング）を行なってい
る。順方向誤り修正符号化（ＦＥＣ）システムは、受信
機が受信した信号だけを使用して誤りを検出して修正で
きるように、伝送される信号に冗長度を付加する。これ
により、受信機は送信機に対して再伝送を要求する必要
がなくなる。
【０００３】より一般的な誤り修正符号型の１つは、リ
ード・ソロモン符号である。リード・ソロモン符号は最
大距離分離を有するブロック符号であり、それらの冗長
度の使用は高度に効率的である。リード・ソロモン符号
の最も興味深い面は、効率的な復号（デコーディング）
アルゴリズムを使用できることである。例えば、Wicker
及びBhargava (Eds.), Reed-Solomon Codes and Their
Applications (IEEE Press, Piscataway, New Jersey,
1994)を参照されたい。
ード・ソロモン符号である。リード・ソロモン符号は最
大距離分離を有するブロック符号であり、それらの冗長
度の使用は高度に効率的である。リード・ソロモン符号
の最も興味深い面は、効率的な復号（デコーディング）
アルゴリズムを使用できることである。例えば、Wicker
及びBhargava (Eds.), Reed-Solomon Codes and Their
Applications (IEEE Press, Piscataway, New Jersey,
1994)を参照されたい。
【０００４】図１は、リード・ソロモン符号化システム
の高レベル図である。情報ビットのブロックＩは、元の
情報と冗長ビットとを含んでいるより大きいブロックで
あるコードワードＣ内に符号化されている。あるチャン
ネルを通して伝送された後に受信されたビットのブロッ
クは、Ｃ＋Ｅで表すことができる。ここにＥは誤りビッ
トのブロックである。デコーダは、Ｃ＋ＥからＩ’を生
成する。Ｉ’は、もしE内の誤りビットの数がコードの
修正能力内にあれば、Ｉに等しい。
の高レベル図である。情報ビットのブロックＩは、元の
情報と冗長ビットとを含んでいるより大きいブロックで
あるコードワードＣ内に符号化されている。あるチャン
ネルを通して伝送された後に受信されたビットのブロッ
クは、Ｃ＋Ｅで表すことができる。ここにＥは誤りビッ
トのブロックである。デコーダは、Ｃ＋ＥからＩ’を生
成する。Ｉ’は、もしE内の誤りビットの数がコードの
修正能力内にあれば、Ｉに等しい。
【０００５】図２は、リード・ソロモン符号化をより詳
細に示す図である。詳述すれば、ｂｋ情報ビットのブロ
ックはｂビットのｋ群に分割され、ｂビットの各群はあ
る記号によって表され、符号化のためのｋ情報記号のブ
ロックが作られる。エンコーダはｋ情報記号のブロック
を操作し、ある形状の元の情報と、冗長とを含むｎコー
ドワード記号のブロックを作る。このコードは、冗長が
誤り検出だけに使用されるか、誤り修正だけに使用され
るか、または誤り検出及び誤り修正の組合わせに使用さ
れるように計画されている。次いで、ｎ符号化された記
号のブロックはｂｎビットのブロックに翻訳され、チャ
ンネルを通して伝送される。受信機のフロントエンド
は、チャンネルの歪みの量に依存して誤っているかも知
れないｂｎビットのブロックを発生する。ｂｎビットの
ブロックはｎ記号のブロックに翻訳され、デコーダを用
いて処理される。伝送誤りがもたらす誤り記号が多くて
も(n−k)／2である限り、ハードデシジョンデコーダは
入力ｋ情報記号及び入力ｂｋビットを信頼できるように
回復することができる。冗長度を追加するための代価と
して、伝送される記号の数がn／k倍だけ増加される。勿
論、これは伝送速度が一定である場合には、情報がk／n
倍だけ減少することを意味している。
細に示す図である。詳述すれば、ｂｋ情報ビットのブロ
ックはｂビットのｋ群に分割され、ｂビットの各群はあ
る記号によって表され、符号化のためのｋ情報記号のブ
ロックが作られる。エンコーダはｋ情報記号のブロック
を操作し、ある形状の元の情報と、冗長とを含むｎコー
ドワード記号のブロックを作る。このコードは、冗長が
誤り検出だけに使用されるか、誤り修正だけに使用され
るか、または誤り検出及び誤り修正の組合わせに使用さ
れるように計画されている。次いで、ｎ符号化された記
号のブロックはｂｎビットのブロックに翻訳され、チャ
ンネルを通して伝送される。受信機のフロントエンド
は、チャンネルの歪みの量に依存して誤っているかも知
れないｂｎビットのブロックを発生する。ｂｎビットの
ブロックはｎ記号のブロックに翻訳され、デコーダを用
いて処理される。伝送誤りがもたらす誤り記号が多くて
も(n−k)／2である限り、ハードデシジョンデコーダは
入力ｋ情報記号及び入力ｂｋビットを信頼できるように
回復することができる。冗長度を追加するための代価と
して、伝送される記号の数がn／k倍だけ増加される。勿
論、これは伝送速度が一定である場合には、情報がk／n
倍だけ減少することを意味している。
【０００６】リード・ソロモン符号化は、本質的に、２
の要素（エレメント）数乗を有する有限体（ finite fi
eld ）（ガロア体またはＧＦ）の要素としての記号を有
するｋ情報記号を、同一有限体からのＧＦ要素であるｎ
記号内へマップしてコードワードを形成する。２Mを有
するこのような体（ＧＦ(２M)で表される）の場合には
要素はＭビットによって表され、非０要素は原始（プリ
ミティブ）要素αの累乗として表すことができる。即
ち、ＧＦ(２M)の要素は、０，１，α，α2，…，α qで
あり、ここにｑ＝２M−２である。
の要素（エレメント）数乗を有する有限体（ finite fi
eld ）（ガロア体またはＧＦ）の要素としての記号を有
するｋ情報記号を、同一有限体からのＧＦ要素であるｎ
記号内へマップしてコードワードを形成する。２Mを有
するこのような体（ＧＦ(２M)で表される）の場合には
要素はＭビットによって表され、非０要素は原始（プリ
ミティブ）要素αの累乗として表すことができる。即
ち、ＧＦ(２M)の要素は、０，１，α，α2，…，α qで
あり、ここにｑ＝２M−２である。
【０００７】非システマティックリード・ソロモン符号
化は、情報及び冗長を、符号化アルゴリズムに従ってｎ
記号のコードワード全体に分布させることによってコー
ドワードを発生する。一方、システマティックリード・
ソロモン符号化は、ｋ情報記号と、符号化アルゴリズム
に従って計算されたn−kパリティ記号とを連結させるこ
とによってコードワードを形成する。これらの付加的な
n−kパリティ記号は、伝送されたことが考えられるｋ情
報記号を選択するために受信機が使用する冗長情報を含
む。詳述すれば、受信機のソフトデシジョンを用いるこ
とによって、誤り記号を修正するためにn−kパリティ記
号を使用することができ、２e＋sが多くてもn−kに等し
いことを条件として消された記号を検出することができ
る。ｎ＝204及びｋ＝188のような値であって、ＧＦがＧ
Ｆ(２8)（256要素を有する有限体）であることが稀では
ないことに注目されたい。実際に、これは高速モデムに
関して広く使用されているコードであり、( 204, 188 )
コードと呼ぶ。このコードは204記号コードワード当た
り８つの誤り記号を修正することができる。
化は、情報及び冗長を、符号化アルゴリズムに従ってｎ
記号のコードワード全体に分布させることによってコー
ドワードを発生する。一方、システマティックリード・
ソロモン符号化は、ｋ情報記号と、符号化アルゴリズム
に従って計算されたn−kパリティ記号とを連結させるこ
とによってコードワードを形成する。これらの付加的な
n−kパリティ記号は、伝送されたことが考えられるｋ情
報記号を選択するために受信機が使用する冗長情報を含
む。詳述すれば、受信機のソフトデシジョンを用いるこ
とによって、誤り記号を修正するためにn−kパリティ記
号を使用することができ、２e＋sが多くてもn−kに等し
いことを条件として消された記号を検出することができ
る。ｎ＝204及びｋ＝188のような値であって、ＧＦがＧ
Ｆ(２8)（256要素を有する有限体）であることが稀では
ないことに注目されたい。実際に、これは高速モデムに
関して広く使用されているコードであり、( 204, 188 )
コードと呼ぶ。このコードは204記号コードワード当た
り８つの誤り記号を修正することができる。
【０００８】システマティックリード・ソロモン符号化
は、リード・ソロモン解号操作を適用しないでも、受信
したコードワードの情報成分を受信機において抽出する
ことができるので有利である。最初のｋ記号は、情報の
全てを表す。最後のn−k記号は、情報記号から計算しな
ければならない。
は、リード・ソロモン解号操作を適用しないでも、受信
したコードワードの情報成分を受信機において抽出する
ことができるので有利である。最初のｋ記号は、情報の
全てを表す。最後のn−k記号は、情報記号から計算しな
ければならない。
【０００９】パリティ記号は、多項式（それらの係数が
ＧＦ要素であり、これらの要素はビットの群を表す）演
算に基づく方法を使用して、情報記号から計算すること
ができる。情報、パリティ、及びコードワードはそれぞ
れ、多項式Ｉ(x)、Ｐ(x)、及びＣ(x)によって表され
る。システマティックリード・ソロモン符号化の場合に
は、Ｃ(x)＝ｘn-kＩ(x)＋Ｐ(x)であり、Ｐ(x)はｘn-kＩ
(x)をＧ(x)で除した時の剰余である。Ｇ(x)はコードの
生成元（ジェネレータ）多項式であり、次数n−kのモニ
ック（ monic ）多項式Ｇ(x)＝ｘn-k＋Ｇn-k-1ｘn-k-1
＋Ｇn-k-2ｘn-k-2＋…＋Ｇ1ｘ＋Ｇ0であるので、Ｐ(x)
は多くてもn−k−1の次数を有している。Ｉ(x)は次数が
多くてもk−１（ｋ係数はｋ情報記号である）の多項式
であるので、Ｃ(x)は次数が多くてもn−1（係数はｎコ
ードワード記号である）の多項式である。
ＧＦ要素であり、これらの要素はビットの群を表す）演
算に基づく方法を使用して、情報記号から計算すること
ができる。情報、パリティ、及びコードワードはそれぞ
れ、多項式Ｉ(x)、Ｐ(x)、及びＣ(x)によって表され
る。システマティックリード・ソロモン符号化の場合に
は、Ｃ(x)＝ｘn-kＩ(x)＋Ｐ(x)であり、Ｐ(x)はｘn-kＩ
(x)をＧ(x)で除した時の剰余である。Ｇ(x)はコードの
生成元（ジェネレータ）多項式であり、次数n−kのモニ
ック（ monic ）多項式Ｇ(x)＝ｘn-k＋Ｇn-k-1ｘn-k-1
＋Ｇn-k-2ｘn-k-2＋…＋Ｇ1ｘ＋Ｇ0であるので、Ｐ(x)
は多くてもn−k−1の次数を有している。Ｉ(x)は次数が
多くてもk−１（ｋ係数はｋ情報記号である）の多項式
であるので、Ｃ(x)は次数が多くてもn−1（係数はｎコ
ードワード記号である）の多項式である。
【００１０】システマティックリード・ソロモン符号化
の多項式除算を実施する最も一般的なアーキテクチャ
は、図３に示すように、遅延素子、ＧＦ要素乗算器、及
びＧＦ要素加算器からなるフィードバックシフトレジス
タからなっている。遅延素子Ｄは、０記号値を用いて初
期化される。情報記号は、最高位数（Ｉk-1）を最初と
して一時に１つレジスタ内へシフトされる。レジスタの
各クロックサイクル中、最後の（最も左の）遅延素子内
に保持されているＧＦ要素はn−k乗算器へフィードバッ
クされ、n−k乗算器はフィードバック要素とフィードバ
ックレジスタ乗算器要素Ｇ0乃至Ｇn-k-1との積を計算す
る。有限体は２の要素数乗を有しているから、減算及び
加算は同じ演算である。
の多項式除算を実施する最も一般的なアーキテクチャ
は、図３に示すように、遅延素子、ＧＦ要素乗算器、及
びＧＦ要素加算器からなるフィードバックシフトレジス
タからなっている。遅延素子Ｄは、０記号値を用いて初
期化される。情報記号は、最高位数（Ｉk-1）を最初と
して一時に１つレジスタ内へシフトされる。レジスタの
各クロックサイクル中、最後の（最も左の）遅延素子内
に保持されているＧＦ要素はn−k乗算器へフィードバッ
クされ、n−k乗算器はフィードバック要素とフィードバ
ックレジスタ乗算器要素Ｇ0乃至Ｇn-k-1との積を計算す
る。有限体は２の要素数乗を有しているから、減算及び
加算は同じ演算である。
【００１１】フィードバックレジスタの各段において、
積は先行段内に格納されている要素に加算され、結果は
後続段内に格納される。レジスタがｎ回クロッキングさ
れた後に遅延素子Ｄ内に格納される要素は、除算の剰余
であるか、またはパリティ多項式Ｐ(x)の係数を構成し
ているパリティ要素である。図４は、レジスタのn−kク
ロックサイクルで剰余を計算するためにプリシフトされ
たＩ(x)を使用する簡易化フィードバックシフトレジス
タを示している。
積は先行段内に格納されている要素に加算され、結果は
後続段内に格納される。レジスタがｎ回クロッキングさ
れた後に遅延素子Ｄ内に格納される要素は、除算の剰余
であるか、またはパリティ多項式Ｐ(x)の係数を構成し
ているパリティ要素である。図４は、レジスタのn−kク
ロックサイクルで剰余を計算するためにプリシフトされ
たＩ(x)を使用する簡易化フィードバックシフトレジス
タを示している。
【００１２】図３−４に示すアーキテクチャは、回路素
子を用いてリード・ソロモンエンコーダを効率的に実現
したいとの要望から考案されたものであることを理解す
ることが重要である。典型的なエンコーダ設計において
は、３つの型の回路素子（遅延素子、ＧＦ加算器、ＧＦ
乗算器）は個々に最適化され、次いで所望の剰余計算動
作を遂行するように組合わされる。この型のエンコーダ
アーキテクチャは、汎用ディジタル信号処理（ＤＳＰ）
プラットフォーム上でエミュレートすることができる。
しかしながら、使用される特定のＧＦ表現に依存してＧ
Ｆ乗算またはＧＦ加算の何れかは効率的に実現できて
も、それらの両方を同時に効率的に実現することはでき
ない。例えば、１つの特定表現は、２つの要素の２進成
分の簡単な排他的ＯＲ演算で計算されるＧＦ加算を可能
にする。一般的に、これはＤＳＰの１サイクルで実施す
ることができる。しかしながら、この同じＧＦ要素表現
について、ＧＦ乗算を計算するには多数のサイクルが必
要になる。
子を用いてリード・ソロモンエンコーダを効率的に実現
したいとの要望から考案されたものであることを理解す
ることが重要である。典型的なエンコーダ設計において
は、３つの型の回路素子（遅延素子、ＧＦ加算器、ＧＦ
乗算器）は個々に最適化され、次いで所望の剰余計算動
作を遂行するように組合わされる。この型のエンコーダ
アーキテクチャは、汎用ディジタル信号処理（ＤＳＰ）
プラットフォーム上でエミュレートすることができる。
しかしながら、使用される特定のＧＦ表現に依存してＧ
Ｆ乗算またはＧＦ加算の何れかは効率的に実現できて
も、それらの両方を同時に効率的に実現することはでき
ない。例えば、１つの特定表現は、２つの要素の２進成
分の簡単な排他的ＯＲ演算で計算されるＧＦ加算を可能
にする。一般的に、これはＤＳＰの１サイクルで実施す
ることができる。しかしながら、この同じＧＦ要素表現
について、ＧＦ乗算を計算するには多数のサイクルが必
要になる。
【００１３】ＧＦ乗算表を使用すると、２つのＧＦ要素
を乗算するのに必要なサイクル数を減少させることがで
きる。しかしながら、ＧＦ乗算表は多量のメモリを必要
とし、２つのＧＦ要素の積を決定するためのメモリ索引
（ルックアップ）にも多少の時間を消費し得る。
を乗算するのに必要なサイクル数を減少させることがで
きる。しかしながら、ＧＦ乗算表は多量のメモリを必要
とし、２つのＧＦ要素の積を決定するためのメモリ索引
（ルックアップ）にも多少の時間を消費し得る。
【００１４】
【発明の概要】本発明は、デシメートされ、インタリー
ブされて簡易化された有限体（ガロア体またはＧＦ）乗
算表を提供する。これは、汎用ディジタル信号プロセッ
サ（ＤＳＰ）がリード・ソロモン符号化を効率的に遂行
することを可能にし、それによって特殊なフィードバッ
クシフトレジスタ回路の必要性を排除するという利点を
有している。
ブされて簡易化された有限体（ガロア体またはＧＦ）乗
算表を提供する。これは、汎用ディジタル信号プロセッ
サ（ＤＳＰ）がリード・ソロモン符号化を効率的に遂行
することを可能にし、それによって特殊なフィードバッ
クシフトレジスタ回路の必要性を排除するという利点を
有している。
【００１５】
【実施の形態】システムの概要 図５−６は、全乗算ルックアップテーブルからの列の選
択（デシメート）と、効率的なアクセスのための再順序
付け（インタリーブ）とによって構築された好ましい実
施の形態のＧＦ(２8)要素乗算ルックアップテーブルを
示している。ＧＦの要素としてのリード・ソロモンコー
ド生成元多項式の係数は保持される列を示しており、遅
延のエミュレーションのために使用されるメモリ位置は
これらの列の順序をセットする。（ 204, 188 ）コード
の場合、コード生成元多項式Ｇ(x)は次数16を有し、情
報多項式Ｉ(x)は次数187を有し、そしてパリティ多項式
Ｐ(x)は次数15を有しているので、多項式除算は188のス
テップを有することになり、各ステップは16の乗算と16
の加算とを必要とする。
択（デシメート）と、効率的なアクセスのための再順序
付け（インタリーブ）とによって構築された好ましい実
施の形態のＧＦ(２8)要素乗算ルックアップテーブルを
示している。ＧＦの要素としてのリード・ソロモンコー
ド生成元多項式の係数は保持される列を示しており、遅
延のエミュレーションのために使用されるメモリ位置は
これらの列の順序をセットする。（ 204, 188 ）コード
の場合、コード生成元多項式Ｇ(x)は次数16を有し、情
報多項式Ｉ(x)は次数187を有し、そしてパリティ多項式
Ｐ(x)は次数15を有しているので、多項式除算は188のス
テップを有することになり、各ステップは16の乗算と16
の加算とを必要とする。
【００１６】ＧＦ係数多項式除算 好ましい実施の形態は図４のフィードバックシフトレジ
スタを汎用プロセッサでエミュレートするから、先ずシ
フトレジスタの動作を説明する。Ｐ(x)を求めるための
Ｇ(x)によるｘn-kＩ(x)の多項式除算は複数のステップ
で進行し、各ステップはｘ項の次の低位羃を商に加算
し、ｘの１つの低位羃の剰余を残す。最後のステップは
商の定数項を生成し、遅延素子内に最終剰余の係数Ｐ
(x)を発生する。各ステップは、図４のフィードバック
レジスタ内の１クロックサイクルに対応する。Ｇ(x)＝
ｘn-k＋Ｇn-k-1ｘn-k-1＋…＋Ｇ0であり、Ｉ(x)＝Ｉk-1
ｘk-1＋Ｉk-2ｘk-2＋Ｉk-3ｘk-3＋…＋Ｉ0である。
スタを汎用プロセッサでエミュレートするから、先ずシ
フトレジスタの動作を説明する。Ｐ(x)を求めるための
Ｇ(x)によるｘn-kＩ(x)の多項式除算は複数のステップ
で進行し、各ステップはｘ項の次の低位羃を商に加算
し、ｘの１つの低位羃の剰余を残す。最後のステップは
商の定数項を生成し、遅延素子内に最終剰余の係数Ｐ
(x)を発生する。各ステップは、図４のフィードバック
レジスタ内の１クロックサイクルに対応する。Ｇ(x)＝
ｘn-k＋Ｇn-k-1ｘn-k-1＋…＋Ｇ0であり、Ｉ(x)＝Ｉk-1
ｘk-1＋Ｉk-2ｘk-2＋Ｉk-3ｘk-3＋…＋Ｉ0である。
【００１７】従って、ｘn-kＩ(x)＝Ｉk-1ｘn-1＋Ｉk-2
ｘn-2＋Ｉk-3ｘn-3＋…＋Ｉ0であり、除算の最初のステ
ップは、第１の商の項Ｉk-1ｘk-1と、（Ｉk-2−Ｇn-k-1
Ｉk- 1）ｘn-2＋（Ｉk-3−Ｇn-k-2Ｉk-1）ｘn-3＋…＋
（Ｉk-1-(n-k)−Ｇ0Ｉk-1）ｘk -1＋Ｉk-2-(n-k)ｘk-2＋
Ｉk-3-(n-k)ｘk-3＋…＋Ｉ0ｘn-kに等しい剰余とを発生
させる。第１のクロックサイクル中に、図４のフィード
バックシフトレジスタはＩk-1をシフトインさせ、ｊ＝
０乃至n−k−１のための積ＧjＩk-1を計算し、そしてそ
れらを遅延素子０，１，…，n−k−１内に格納する。最
初のクロックはＩ k-1をシフトインさせるが、項Ｉk-2，
Ｉk-3，…，Ｉ0は未だにシフトインされていない。
ｘn-2＋Ｉk-3ｘn-3＋…＋Ｉ0であり、除算の最初のステ
ップは、第１の商の項Ｉk-1ｘk-1と、（Ｉk-2−Ｇn-k-1
Ｉk- 1）ｘn-2＋（Ｉk-3−Ｇn-k-2Ｉk-1）ｘn-3＋…＋
（Ｉk-1-(n-k)−Ｇ0Ｉk-1）ｘk -1＋Ｉk-2-(n-k)ｘk-2＋
Ｉk-3-(n-k)ｘk-3＋…＋Ｉ0ｘn-kに等しい剰余とを発生
させる。第１のクロックサイクル中に、図４のフィード
バックシフトレジスタはＩk-1をシフトインさせ、ｊ＝
０乃至n−k−１のための積ＧjＩk-1を計算し、そしてそ
れらを遅延素子０，１，…，n−k−１内に格納する。最
初のクロックはＩ k-1をシフトインさせるが、項Ｉk-2，
Ｉk-3，…，Ｉ0は未だにシフトインされていない。
【００１８】第２のステップは、第２の商の項（Ｉk-2
−Ｇn-k-1Ｉk-1）ｘk-2と、第２の剰余｛Ｉk-3−Ｇ
n-k-2Ｉk-1−（Ｉk-2−Ｇn-k-1Ｉk-1）Ｇn-k-1｝ｘn-3
＋｛Ｉk-4−Ｇn-k-3Ｉk-1−（Ｉk-2−Ｇn-k-1Ｉk-1）Ｇ
n-k-2｝ｘn-4＋…＋｛Ｉk-1-(n-k)−Ｇ0Ｉk-1−（Ｉk-2
−Ｇn-k-1Ｉk-1）Ｇ1｝ｘk-1＋｛Ｉk-2-(n-k)−（Ｉk-2
−Ｇn -k-1Ｉk-1）Ｇ0｝ｘk-2＋Ｉk-3-(n-k)ｘk-3＋…＋
Ｉ0ｘn-kとを発生させる。第２のクロックサイクル中に
シフトレジスタはＩk-2をシフトインさせ、ｊ＝０，
…，n−k−１のための項（Ｉk-2−Ｇn-k-1Ｉk-1）Ｇjを
計算し、それら（ｊ＝０のためのものを除く）を項Ｇ
j-1Ｉk-1から減算（加算）し、そして遅延素子内に格納
する。項（Ｉk-2−Ｇn-k-1Ｉk-1）Ｇjは、先ず積Ｇ
n-k-1Ｉk-1（先行クロックサイクルによって遅延素子n
−k−１内に格納されている）をシフトインされたＩk-2
から減算（加算）し、次に各乗算器においてその結果を
Ｇjに乗算することによって計算されることに注目され
たい。また、この積に加算されるＧj-1Ｉk-1項は最初の
クロックサイクルにおいて隣接する遅延素子内に格納さ
れており、加算及び格納のためにシフトインされる。こ
こでも、Ｉk-3，…，Ｉ0は未だにシフトインされていな
い。
−Ｇn-k-1Ｉk-1）ｘk-2と、第２の剰余｛Ｉk-3−Ｇ
n-k-2Ｉk-1−（Ｉk-2−Ｇn-k-1Ｉk-1）Ｇn-k-1｝ｘn-3
＋｛Ｉk-4−Ｇn-k-3Ｉk-1−（Ｉk-2−Ｇn-k-1Ｉk-1）Ｇ
n-k-2｝ｘn-4＋…＋｛Ｉk-1-(n-k)−Ｇ0Ｉk-1−（Ｉk-2
−Ｇn-k-1Ｉk-1）Ｇ1｝ｘk-1＋｛Ｉk-2-(n-k)−（Ｉk-2
−Ｇn -k-1Ｉk-1）Ｇ0｝ｘk-2＋Ｉk-3-(n-k)ｘk-3＋…＋
Ｉ0ｘn-kとを発生させる。第２のクロックサイクル中に
シフトレジスタはＩk-2をシフトインさせ、ｊ＝０，
…，n−k−１のための項（Ｉk-2−Ｇn-k-1Ｉk-1）Ｇjを
計算し、それら（ｊ＝０のためのものを除く）を項Ｇ
j-1Ｉk-1から減算（加算）し、そして遅延素子内に格納
する。項（Ｉk-2−Ｇn-k-1Ｉk-1）Ｇjは、先ず積Ｇ
n-k-1Ｉk-1（先行クロックサイクルによって遅延素子n
−k−１内に格納されている）をシフトインされたＩk-2
から減算（加算）し、次に各乗算器においてその結果を
Ｇjに乗算することによって計算されることに注目され
たい。また、この積に加算されるＧj-1Ｉk-1項は最初の
クロックサイクルにおいて隣接する遅延素子内に格納さ
れており、加算及び格納のためにシフトインされる。こ
こでも、Ｉk-3，…，Ｉ0は未だにシフトインされていな
い。
【００１９】同様に、連続する除算ステップは、ｋ番目
の、そして最後のステップが遅延素子n−k−１，…，０
内に剰余Ｐ(x)係数Ｐn-k-1，…，Ｐ0を有するようにな
るまで剰余を累積する。
の、そして最後のステップが遅延素子n−k−１，…，０
内に剰余Ｐ(x)係数Ｐn-k-1，…，Ｐ0を有するようにな
るまで剰余を累積する。
【００２０】好ましい実施の形態は、上述した多項式除
算の後続の解析に頼っている。ｉ番目のステップにおい
て、n−k−１メモリ内に格納されているＭn-k-1が、シ
フトインされた記号Ｉk-1から減算（加算）され、その
結果に各生成元多項式係数Ｇn -k-1，…，Ｇ0が乗算され
る。従って、もし記号Ｉk-1−Ｍn-k-1をαmで表せば
（但し、αはＧＦの原始要素である）、n−k乗算はαm
Ｇn-k-1，αmＧn-k-2，…，αmＧ0である。従って、被
乗数は全て同一、即ちαmである。
算の後続の解析に頼っている。ｉ番目のステップにおい
て、n−k−１メモリ内に格納されているＭn-k-1が、シ
フトインされた記号Ｉk-1から減算（加算）され、その
結果に各生成元多項式係数Ｇn -k-1，…，Ｇ0が乗算され
る。従って、もし記号Ｉk-1−Ｍn-k-1をαmで表せば
（但し、αはＧＦの原始要素である）、n−k乗算はαm
Ｇn-k-1，αmＧn-k-2，…，αmＧ0である。従って、被
乗数は全て同一、即ちαmである。
【００２１】今度は、これらの乗算をルックアップテー
ブルによって実現することを考えよう。要素αmは乗算
表の行の１つを索引するために使用され、要素Ｇjは表
の列の１つを索引する。クロックサイクル中に実行され
る連続乗算は、列が要素Ｇn-k- 1，…，Ｇ0に対応して索
引される度毎に同一の行をアクセスする必要がある。従
って、連続乗算によって発生された積は、表の所与の行
及び種々の列から抽出される。一般的に言えば、列索引
は連続的に順序付けされていない。レジスタの何れかの
クロックサイクルについて行索引は変化し得るが、列索
引用パターンは同一のままである。
ブルによって実現することを考えよう。要素αmは乗算
表の行の１つを索引するために使用され、要素Ｇjは表
の列の１つを索引する。クロックサイクル中に実行され
る連続乗算は、列が要素Ｇn-k- 1，…，Ｇ0に対応して索
引される度毎に同一の行をアクセスする必要がある。従
って、連続乗算によって発生された積は、表の所与の行
及び種々の列から抽出される。一般的に言えば、列索引
は連続的に順序付けされていない。レジスタの何れかの
クロックサイクルについて行索引は変化し得るが、列索
引用パターンは同一のままである。
【００２２】索引されることが決してない列を排除する
ことによって、乗算表を格納するのに必要なメモリの量
を減少させることができる。乗算表内に残される列は、
要素Ｇn-k-1，…，Ｇ0に対応する。従って、これらの列
だけを有する新しい乗算表を格納するためのメモリサイ
ズは、ＧＦが有限体ＧＦ(２M)である場合には２M×（n
−k）である。例えば、ＧＦ(２8)ならば完全な表は256
×256要素になるが、（204, 188 ）コードでは表は僅か
に256×16要素で済む。
ことによって、乗算表を格納するのに必要なメモリの量
を減少させることができる。乗算表内に残される列は、
要素Ｇn-k-1，…，Ｇ0に対応する。従って、これらの列
だけを有する新しい乗算表を格納するためのメモリサイ
ズは、ＧＦが有限体ＧＦ(２M)である場合には２M×（n
−k）である。例えば、ＧＦ(２8)ならば完全な表は256
×256要素になるが、（204, 188 ）コードでは表は僅か
に256×16要素で済む。
【００２３】表の索引によってＧＦ乗算を実現するため
に必要なＤＳＰサイクルの数は、列が連続要素
Ｇn-k-1，…，Ｇ0に対応するように列を順序付けする
（または、遅延素子をエミュレートするメモリ位置の順
序付けに依存してＧ0，Ｇ1，…，Ｇn-k- 1）ことによっ
て減少させることができる。このように列を順序付けし
た後のαmによる乗算は、適切な行をアクセスし、次い
でその行の連続n−k要素を読み出すことによって実施さ
れる。
に必要なＤＳＰサイクルの数は、列が連続要素
Ｇn-k-1，…，Ｇ0に対応するように列を順序付けする
（または、遅延素子をエミュレートするメモリ位置の順
序付けに依存してＧ0，Ｇ1，…，Ｇn-k- 1）ことによっ
て減少させることができる。このように列を順序付けし
た後のαmによる乗算は、適切な行をアクセスし、次い
でその行の連続n−k要素を読み出すことによって実施さ
れる。
【００２４】デシメートされた乗算表は、それを一次元
構造（αm要素が一次元メモリアレイ内へのオフセット
を決定する）に変えることによって更に簡易化すること
ができる。次いで、n−k連続要素がアレイ内の連続メモ
リ位置から読み出される。各要素がアクセス可能なメモ
リ素子サイズよりも小さい場合には、幾つかの積を同時
にアクセスすることができる。例えば、もし各積が８ビ
ットＧＦ要素であり、ＤＳＰがメモリの32ビットワード
にアクセス可能であれば、１回のメモリアクセスで４つ
の積を読み出すことができる。
構造（αm要素が一次元メモリアレイ内へのオフセット
を決定する）に変えることによって更に簡易化すること
ができる。次いで、n−k連続要素がアレイ内の連続メモ
リ位置から読み出される。各要素がアクセス可能なメモ
リ素子サイズよりも小さい場合には、幾つかの積を同時
にアクセスすることができる。例えば、もし各積が８ビ
ットＧＦ要素であり、ＤＳＰがメモリの32ビットワード
にアクセス可能であれば、１回のメモリアクセスで４つ
の積を読み出すことができる。
【００２５】図５は関心のあるＧＦ(２8)積を完全サイ
ズ型ＧＦ乗算表から抽出する手法を、そして図６はそれ
らをデシメートされてインタリーブされたＧＦ乗算表内
に配置する手法を概念的に示している。この例では各Ｇ
Ｆ要素は８ビットによって表されている。従って、完全
乗算表は、256×256要素を含んでいる。第１行は無意味
（トリビアル）に０であり、従って新しいアレイの第１
のn−k要素である。第２行（要素α0＝１のための）か
ら開始して、積要素α0Ｇ0が新しいアレイ内に配置さ
れ、要素α0Ｇ1が第２の位置に配置される等々と、要素
α0Ｇn-k-1まで続けられる。以上のように、第２のn−k
要素は、α0と生成元多項式Ｇ(x)の順序付けられた要素
（係数）との積である。α1とＧ(x)の順序付けられた要
素との積が、次のn−kアレイ位置内に配置される、等々
と続く。動作中、αjとＧ(x)の順序付けられた要素との
乗算の結果は、指標j(n-k)から始めて、メモリアレイ内
のn−k要素にアクセスすることによって入手することが
できる。
ズ型ＧＦ乗算表から抽出する手法を、そして図６はそれ
らをデシメートされてインタリーブされたＧＦ乗算表内
に配置する手法を概念的に示している。この例では各Ｇ
Ｆ要素は８ビットによって表されている。従って、完全
乗算表は、256×256要素を含んでいる。第１行は無意味
（トリビアル）に０であり、従って新しいアレイの第１
のn−k要素である。第２行（要素α0＝１のための）か
ら開始して、積要素α0Ｇ0が新しいアレイ内に配置さ
れ、要素α0Ｇ1が第２の位置に配置される等々と、要素
α0Ｇn-k-1まで続けられる。以上のように、第２のn−k
要素は、α0と生成元多項式Ｇ(x)の順序付けられた要素
（係数）との積である。α1とＧ(x)の順序付けられた要
素との積が、次のn−kアレイ位置内に配置される、等々
と続く。動作中、αjとＧ(x)の順序付けられた要素との
乗算の結果は、指標j(n-k)から始めて、メモリアレイ内
のn−k要素にアクセスすることによって入手することが
できる。
【００２６】図６は、256（n−k）要素のデシメートさ
れてインタリーブされたＧＦ乗算表を示している。８ビ
ット入力または被乗数は、０またはｊ＝０，１，２，
…，254としてαjである。シフトレジスタ乗数（または
他の被乗数）はＧ0，Ｇ1，…，Ｇn-k-1である。積はイ
ンタリーブされた表として格納されるので、入力とシフ
トレジスタ乗数との全ての積は１ブロック以内の適切な
順序で索引することができる。これによって、１索引サ
イクルで複数の乗算を遂行することが可能になる。例え
ば、32ビットをロードすることによって、４つの８ビッ
トＧＦ乗算の積を発生させることができる。これは、幅
広いメモリバスを有するＤＳＰ装置にとって極めて効率
的である。
れてインタリーブされたＧＦ乗算表を示している。８ビ
ット入力または被乗数は、０またはｊ＝０，１，２，
…，254としてαjである。シフトレジスタ乗数（または
他の被乗数）はＧ0，Ｇ1，…，Ｇn-k-1である。積はイ
ンタリーブされた表として格納されるので、入力とシフ
トレジスタ乗数との全ての積は１ブロック以内の適切な
順序で索引することができる。これによって、１索引サ
イクルで複数の乗算を遂行することが可能になる。例え
ば、32ビットをロードすることによって、４つの８ビッ
トＧＦ乗算の積を発生させることができる。これは、幅
広いメモリバスを有するＤＳＰ装置にとって極めて効率
的である。
【００２７】変更 上述した好ましい実施の形態は、リード・ソロモンコー
ド生成元多項式係数に対してデシメートされ、そして順
次アクセスのためにインタリーブされた乗算表の特色を
保持しながら、さまざまな方法で変更することができ
る。
ド生成元多項式係数に対してデシメートされ、そして順
次アクセスのためにインタリーブされた乗算表の特色を
保持しながら、さまざまな方法で変更することができ
る。
【００２８】例えば、有限体は異なるサイズを有するこ
とができ、順次アクセスは多項式除算の別の方法に適合
させることができる、等々である。
とができ、順次アクセスは多項式除算の別の方法に適合
させることができる、等々である。
【００２９】以上の記載に関連して、以下の各項を開示
する。
する。
【００３０】１． 有限体係数を有する多項式除算の方
法であって、（ａ）複数の除数多項式の係数からなり、
上記除数多項式の上記係数に従って順序付けされたエン
トリを有する有限体乗算表を準備するステップと、
（ｂ）部分商及び剰余を反復して計算するステップと、
を含んでいることを特徴とする方法。
法であって、（ａ）複数の除数多項式の係数からなり、
上記除数多項式の上記係数に従って順序付けされたエン
トリを有する有限体乗算表を準備するステップと、
（ｂ）部分商及び剰余を反復して計算するステップと、
を含んでいることを特徴とする方法。
【００３１】２． リード・ソロモン符号化計算に有用
な、有限体のためのデシメートされ、インタリーブされ
た乗算表。生成元多項式係数は乗算表内容及び順序付け
を決定する。
な、有限体のためのデシメートされ、インタリーブされ
た乗算表。生成元多項式係数は乗算表内容及び順序付け
を決定する。
【図１】リード・ソロモン符号化の概要を示す図であ
る。
る。
【図２】リード・ソロモン符号化の概要を示す図であ
る。
る。
【図３】多項式除算のためのシフトレジスタを示す図で
ある。
ある。
【図４】多項式除算のためのシフトレジスタを示す図で
ある。
ある。
【図５】ＧＦ(256)乗算表を示す図である。
【図６】好ましい実施の形態ＧＦ(256)乗算表を示す図
である。
である。
Claims (1)
- 【請求項１】 有限体係数を有する多項式除算の方法で
あって、 （ａ）複数の除数多項式の係数からなり、上記除数多項
式の上記係数に従って順序付けされたエントリを有する
有限体乗算表を準備するステップと、 （ｂ）部分商及び剰余を反復して計算するステップと、
を含んでいることを特徴とする方法。
Applications Claiming Priority (2)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| US12448399P | 1999-03-15 | 1999-03-15 | |
| US60/124483 | 1999-03-15 |
Publications (1)
| Publication Number | Publication Date |
|---|---|
| JP2000295116A true JP2000295116A (ja) | 2000-10-20 |
Family
ID=22415156
Family Applications (1)
| Application Number | Title | Priority Date | Filing Date |
|---|---|---|---|
| JP2000069880A Abandoned JP2000295116A (ja) | 1999-03-15 | 2000-03-14 | 誤り修正符号化方法 |
Country Status (5)
| Country | Link |
|---|---|
| US (1) | US6598201B1 (ja) |
| EP (1) | EP1037148B1 (ja) |
| JP (1) | JP2000295116A (ja) |
| AT (1) | ATE285090T1 (ja) |
| DE (1) | DE60016648T2 (ja) |
Cited By (2)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| JP2007514371A (ja) * | 2003-12-12 | 2007-05-31 | アナログ・デバイシズ・インコーポレーテッド | ガロア体乗算のためのルックアップテーブルを使用するリード・ソロモン符号の符号化および復号化 |
| JP2008288884A (ja) * | 2007-05-17 | 2008-11-27 | Mitsubishi Electric Corp | 符号化装置、暗号化装置及びプログラム |
Families Citing this family (3)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| US8286059B1 (en) | 2007-01-08 | 2012-10-09 | Marvell International Ltd. | Word-serial cyclic code encoder |
| JP5927323B1 (ja) * | 2015-05-12 | 2016-06-01 | 日本電信電話株式会社 | 行列作用装置、行列作用方法、およびプログラム |
| CN105024707B (zh) * | 2015-07-31 | 2018-05-11 | 福建联迪商用设备有限公司 | 一种rs纠错解码方法 |
Family Cites Families (9)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| JPS58219852A (ja) * | 1982-06-15 | 1983-12-21 | Toshiba Corp | エラ−訂正回路 |
| US4937829A (en) * | 1987-04-24 | 1990-06-26 | Ricoh Company, Ltd. | Error correcting system and device |
| US5040179A (en) * | 1989-08-18 | 1991-08-13 | Loral Aerospace Corp. | High data rate BCH encoder |
| US5140596A (en) * | 1990-02-20 | 1992-08-18 | Eastman Kodak Company | High speed encoder for non-systematic codes |
| US5465261A (en) * | 1993-08-03 | 1995-11-07 | National Semiconductor Corporation | RAM based architecture for ECC circuits |
| EP0730795B1 (en) * | 1993-11-22 | 2003-02-19 | Thomson Consumer Electronics, Inc. | Satellite receiver code rate switching apparatus |
| US5914969A (en) * | 1995-10-03 | 1999-06-22 | Matsushita Electric Industrial Co., Ltd. | Device and method for error correcting coding, and device and method for error correcting decoding |
| US6327690B1 (en) * | 1999-02-04 | 2001-12-04 | Intel Corporation | Integrated reed-solomon error correction code encoder and syndrome generator |
| US6360348B1 (en) * | 1999-08-27 | 2002-03-19 | Motorola, Inc. | Method and apparatus for coding and decoding data |
-
2000
- 2000-03-08 US US09/520,566 patent/US6598201B1/en not_active Expired - Lifetime
- 2000-03-14 EP EP00200916A patent/EP1037148B1/en not_active Expired - Lifetime
- 2000-03-14 JP JP2000069880A patent/JP2000295116A/ja not_active Abandoned
- 2000-03-14 DE DE60016648T patent/DE60016648T2/de not_active Expired - Lifetime
- 2000-03-14 AT AT00200916T patent/ATE285090T1/de not_active IP Right Cessation
Cited By (3)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| JP2007514371A (ja) * | 2003-12-12 | 2007-05-31 | アナログ・デバイシズ・インコーポレーテッド | ガロア体乗算のためのルックアップテーブルを使用するリード・ソロモン符号の符号化および復号化 |
| JP4777258B2 (ja) * | 2003-12-12 | 2011-09-21 | アナログ・デバイシズ・インコーポレーテッド | ガロア体乗算のためのルックアップテーブルを使用するリード・ソロモン符号の符号化および復号化 |
| JP2008288884A (ja) * | 2007-05-17 | 2008-11-27 | Mitsubishi Electric Corp | 符号化装置、暗号化装置及びプログラム |
Also Published As
| Publication number | Publication date |
|---|---|
| EP1037148B1 (en) | 2004-12-15 |
| DE60016648D1 (de) | 2005-01-20 |
| DE60016648T2 (de) | 2005-12-15 |
| EP1037148A1 (en) | 2000-09-20 |
| ATE285090T1 (de) | 2005-01-15 |
| US6598201B1 (en) | 2003-07-22 |
Similar Documents
| Publication | Publication Date | Title |
|---|---|---|
| US6374383B1 (en) | Determining error locations using error correction codes | |
| US4873688A (en) | High-speed real-time Reed-Solomon decoder | |
| US5999959A (en) | Galois field multiplier | |
| US5517509A (en) | Decoder for decoding ECC using Euclid's algorithm | |
| US20040153722A1 (en) | Error correction code circuit with reduced hardware complexity | |
| US5805617A (en) | Apparatus for computing error correction syndromes | |
| WO2000057561A1 (en) | Pipelined high speed reed-solomon error/erasure decoder | |
| US5905740A (en) | Apparatus and method for error correction | |
| JP3305525B2 (ja) | 復号器、誤りロケータシーケンス生成器および復号方法 | |
| JPH1093445A (ja) | 誤り位置検出多項式計算装置 | |
| US6263471B1 (en) | Method and apparatus for decoding an error correction code | |
| KR100258951B1 (ko) | 리드-솔로몬(rs) 복호기와 그 복호방법 | |
| JP2001127645A (ja) | 誤り訂正方法および誤り訂正装置 | |
| US6735737B2 (en) | Error correction structures and methods | |
| JP3343857B2 (ja) | 復号装置、演算装置およびこれらの方法 | |
| JPH0865175A (ja) | リードソロモン復号器の誤り位置検出回路 | |
| US6598201B1 (en) | Error coding structure and method | |
| JP3614978B2 (ja) | ガロア体の除算方法および除算装置 | |
| EP0793352B1 (en) | Apparatus for determining the error evaluator polynomial for use in a Reed-Solomon decoder | |
| JPH0476540B2 (ja) | ||
| JP2662472B2 (ja) | 誤り訂正処理用シンドローム演算回路 | |
| JPH09307458A (ja) | エラー訂正向け多項式評価装置 | |
| JPH0220124A (ja) | インタリーブ式エンコーディング方法及び装置 | |
| JP2907138B2 (ja) | 誤り訂正の演算処理方法及び処理回路 | |
| JP2575506B2 (ja) | チエンサーチ回路 |
Legal Events
| Date | Code | Title | Description |
|---|---|---|---|
| A621 | Written request for application examination |
Free format text: JAPANESE INTERMEDIATE CODE: A621 Effective date: 20070213 |
|
| A762 | Written abandonment of application |
Free format text: JAPANESE INTERMEDIATE CODE: A762 Effective date: 20081211 |