JPH087700B2 - 巡回冗長検査符号生成の方法および装置 - Google Patents
巡回冗長検査符号生成の方法および装置Info
- Publication number
- JPH087700B2 JPH087700B2 JP3284176A JP28417691A JPH087700B2 JP H087700 B2 JPH087700 B2 JP H087700B2 JP 3284176 A JP3284176 A JP 3284176A JP 28417691 A JP28417691 A JP 28417691A JP H087700 B2 JPH087700 B2 JP H087700B2
- Authority
- JP
- Japan
- Prior art keywords
- crc
- codeword
- preliminary
- prescribed
- message
- 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.)
- Expired - Fee Related
Links
- 238000000034 method Methods 0.000 title claims description 22
- 125000004122 cyclic group Chemical group 0.000 title claims description 5
- 230000005540 biological transmission Effects 0.000 claims description 3
- 238000010586 diagram Methods 0.000 description 5
- 230000008569 process Effects 0.000 description 4
- 230000008878 coupling Effects 0.000 description 3
- 238000010168 coupling process Methods 0.000 description 3
- 238000005859 coupling reaction Methods 0.000 description 3
- 101100258315 Neurospora crassa (strain ATCC 24698 / 74-OR23-1A / CBS 708.71 / DSM 1257 / FGSC 987) crc-1 gene Proteins 0.000 description 1
- 230000006698 induction Effects 0.000 description 1
- 230000001939 inductive effect Effects 0.000 description 1
- 238000012986 modification Methods 0.000 description 1
- 230000004048 modification Effects 0.000 description 1
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/09—Error detection only, e.g. using cyclic redundancy check [CRC] codes or single parity bit
- H03M13/091—Parallel or block-wise CRC computation
-
- 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/6575—Implementations based on combinatorial logic, e.g. Boolean circuits
Landscapes
- Engineering & Computer Science (AREA)
- Physics & Mathematics (AREA)
- Probability & Statistics with Applications (AREA)
- Theoretical Computer Science (AREA)
- Computing Systems (AREA)
- Error Detection And Correction (AREA)
- Detection And Correction Of Errors (AREA)
- Detection And Prevention Of Errors In Transmission (AREA)
Description
【０００１】
【産業上の利用分野】本発明は、符号語の生成に関し、
さらに詳細には、ＣＲＣ（巡回冗長検査）符号語の生成
に関する。
さらに詳細には、ＣＲＣ（巡回冗長検査）符号語の生成
に関する。
【０００２】
【従来の技術】ＣＲＣ符号語は、直列的にも並列的にも
生成される。「高い」ビット速度の通信網では、ＣＲＣ
符号語を並列的に生成する方が望ましい。ＣＲＣ符号語
を並列的に生成する周知の従来の装置は、たとえ可能で
あるとしても実用的に実現するには困難であるような複
雑な回路構造を用いる必要があった。この実現上の困難
さは、ＣＲＣ符号語の生成に一般に用いられるＣＲＣ生
成多項式の形式によるものである。一般に、ＣＲＣ生成
多項式は、（１＋ｘ）ｆ(ｘ)という形式である。因子
（１＋ｘ）のために、従来の並列ＣＲＣ符号語生成装置
に対し手にあまる複雑さが導入される。これは、従来の
装置ではＣＲＣ生成多項式全体による除算を１段階で行
うことによってＣＲＣ符号語が生成されたからである。
このような除算をハードウェア設計で実現することは極
めて困難である。
生成される。「高い」ビット速度の通信網では、ＣＲＣ
符号語を並列的に生成する方が望ましい。ＣＲＣ符号語
を並列的に生成する周知の従来の装置は、たとえ可能で
あるとしても実用的に実現するには困難であるような複
雑な回路構造を用いる必要があった。この実現上の困難
さは、ＣＲＣ符号語の生成に一般に用いられるＣＲＣ生
成多項式の形式によるものである。一般に、ＣＲＣ生成
多項式は、（１＋ｘ）ｆ(ｘ)という形式である。因子
（１＋ｘ）のために、従来の並列ＣＲＣ符号語生成装置
に対し手にあまる複雑さが導入される。これは、従来の
装置ではＣＲＣ生成多項式全体による除算を１段階で行
うことによってＣＲＣ符号語が生成されたからである。
このような除算をハードウェア設計で実現することは極
めて困難である。
【０００３】
【発明が解決しようとする課題】発明が解決しようとす
る課題は、（１＋ｘ）・ｆ（ｘ）という形式のＣＲＣ生
成多項式を用いてＣＲＣコードを効率的に生成する方法
および装置を与えることである。
る課題は、（１＋ｘ）・ｆ（ｘ）という形式のＣＲＣ生
成多項式を用いてＣＲＣコードを効率的に生成する方法
および装置を与えることである。
【０００４】
【課題を解決するための手段】従来の並列ＣＲＣ符号語
生成装置に関する問題は、本発明に従い（１＋ｘ）ｆ
(ｘ)という形式のＣＲＣ生成多項式を用いる２段階処理
において全体的なＣＲＣ符号語を生成することによっ
て、解決できる。第１段階は、ｆ(ｘ)に相当する予備段
階のＣＲＣ符号語の生成を含む。第２段階は、（１＋
ｘ）に相当する項の生成を含む。これらの２つの段階
は、独立に並行して同時に行われる。これらの２つの段
階が完了すると、全体的なＣＲＣ符号語を生成するため
に、予備段階のＣＲＣ符号語および（１＋ｘ）に相当す
る項が規定の要領で結合される。
生成装置に関する問題は、本発明に従い（１＋ｘ）ｆ
(ｘ)という形式のＣＲＣ生成多項式を用いる２段階処理
において全体的なＣＲＣ符号語を生成することによっ
て、解決できる。第１段階は、ｆ(ｘ)に相当する予備段
階のＣＲＣ符号語の生成を含む。第２段階は、（１＋
ｘ）に相当する項の生成を含む。これらの２つの段階
は、独立に並行して同時に行われる。これらの２つの段
階が完了すると、全体的なＣＲＣ符号語を生成するため
に、予備段階のＣＲＣ符号語および（１＋ｘ）に相当す
る項が規定の要領で結合される。
【０００５】さらに詳細には、（１＋ｘ）に相当する項
を巧みに利用してｆ(ｘ)に相当する予備段階のＣＲＣ符
号語を規定の要領で修正することによって、全体的なＣ
ＲＣ符号語が得られる。（１＋ｘ）に相当する項は、
（０）状態または（１）状態の何れかである。この項が
０状態の場合、予備段階のＣＲＣ符号語を第１の規定の
要領で修正することによって、すなわち、ｆ(ｘ)に相当
する予備段階のＣＲＣ符号語のビットを左に１回シフト
することによって、全体的なＣＲＣ符号語を得る。前記
の項が１状態の場合、予備段階のＣＲＣ符号語を第２の
規定の要領で修正することによって、すなわち、ｆ(ｘ)
に相当する予備段階のＣＲＣ符号語のビットを左に１回
シフトし、さらにそのシフトした予備段階のＣＲＣ符号
語にｆ(ｘ)を加えることによって、全体的なＣＲＣ符号
語を得る。
を巧みに利用してｆ(ｘ)に相当する予備段階のＣＲＣ符
号語を規定の要領で修正することによって、全体的なＣ
ＲＣ符号語が得られる。（１＋ｘ）に相当する項は、
（０）状態または（１）状態の何れかである。この項が
０状態の場合、予備段階のＣＲＣ符号語を第１の規定の
要領で修正することによって、すなわち、ｆ(ｘ)に相当
する予備段階のＣＲＣ符号語のビットを左に１回シフト
することによって、全体的なＣＲＣ符号語を得る。前記
の項が１状態の場合、予備段階のＣＲＣ符号語を第２の
規定の要領で修正することによって、すなわち、ｆ(ｘ)
に相当する予備段階のＣＲＣ符号語のビットを左に１回
シフトし、さらにそのシフトした予備段階のＣＲＣ符号
語にｆ(ｘ)を加えることによって、全体的なＣＲＣ符号
語を得る。
【０００６】
【実施例】論理的説明 以下において、ＣＲＣ符号の性質を簡単に振り返ってみ
る。ＣＲＣ符号は、ビット列が０および１のみの係数を
有する多項式の表現として扱われるという点で、多項式
符号である。ｎビットのメッセージは、ｘn-1からｘ0に
わたるｎ項を有する１つの多項式に対する係数のリスト
であると見なされる。代数分野の理論の法則によって、
多項式演算は２を法として行われる。従って、加算も減
算も、ともに排他的論理和演算と同じである。
る。ＣＲＣ符号は、ビット列が０および１のみの係数を
有する多項式の表現として扱われるという点で、多項式
符号である。ｎビットのメッセージは、ｘn-1からｘ0に
わたるｎ項を有する１つの多項式に対する係数のリスト
であると見なされる。代数分野の理論の法則によって、
多項式演算は２を法として行われる。従って、加算も減
算も、ともに排他的論理和演算と同じである。
【０００７】以下において、ＣＲＣフィールドを含むメ
ッセージの長さをｎとし、生成多項式をＧ(ｘ)で表し、
Ｇ(ｘ)の次数をｒと仮定する。
ッセージの長さをｎとし、生成多項式をＧ(ｘ)で表し、
Ｇ(ｘ)の次数をｒと仮定する。
【０００８】（ｘ＋１）が生成多項式Ｇ(ｘ)を割り切る
ことができ、かつＧ(ｘ)がｘとｎまでの任意のｋに対す
る（ｘk＋１）とを割り切ることができない場合、ゼロ
でない正当な多項式のハミングの重み（Hamming weigh
t）は、少なくとも４である。これにより、ハミングの
距離４を与えることができるＣＲＣ符号の生成多項式を
見つける方法が与えられる。
ことができ、かつＧ(ｘ)がｘとｎまでの任意のｋに対す
る（ｘk＋１）とを割り切ることができない場合、ゼロ
でない正当な多項式のハミングの重み（Hamming weigh
t）は、少なくとも４である。これにより、ハミングの
距離４を与えることができるＣＲＣ符号の生成多項式を
見つける方法が与えられる。
【０００９】次の多項式は、ＣＲＣ−１０、ＣＲＣ−１
２、およびＣＲＣ−１６に対して、それぞれ国際標準と
なったものである。
２、およびＣＲＣ−１６に対して、それぞれ国際標準と
なったものである。
【数１】 これらの多項式は、すべて（１＋ｘ）・ｆ(ｘ)という形
式である。ただし、ｆ(ｘ)は、原始多項式である。関数
（１＋ｘ）は、ハミングの距離４を与える生成多項式に
おける因子である。本発明の実施において他の多項式も
同様に使用できることは明かである。
式である。ただし、ｆ(ｘ)は、原始多項式である。関数
（１＋ｘ）は、ハミングの距離４を与える生成多項式に
おける因子である。本発明の実施において他の多項式も
同様に使用できることは明かである。
【００１０】前記のような多項式に特に適し、かつ本発
明により並列式に非常に簡単に実施することを可能とす
るＣＲＣ符号語生成の方法および装置を説明する。多項
式ｇ(ｘ)を多項式ｈ(ｘ)によって割ったときに得られる
剰余を表すのに
明により並列式に非常に簡単に実施することを可能とす
るＣＲＣ符号語生成の方法および装置を説明する。多項
式ｇ(ｘ)を多項式ｈ(ｘ)によって割ったときに得られる
剰余を表すのに
【数２】 という表記を用いる。
【００１１】ＣＲＣ生成多項式Ｇ(ｘ)が次式で表される
とする。 Ｇ(ｘ)＝（１＋ｘ）ｆ(ｘ) （４） ＣＲＣ符号を求めるメッセージ多項式をＭ(ｘ)とし、検
査ビットの数（すなわち、Ｇ(ｘ)の次数）をｒとする
と、ｆ(ｘ)の次数はｒ−１である。
とする。 Ｇ(ｘ)＝（１＋ｘ）ｆ(ｘ) （４） ＣＲＣ符号を求めるメッセージ多項式をＭ(ｘ)とし、検
査ビットの数（すなわち、Ｇ(ｘ)の次数）をｒとする
と、ｆ(ｘ)の次数はｒ−１である。
【００１２】次に、次式によって与えられる剰余Ｒ(ｘ)
を求める。
を求める。
【数３】 剰余Ｒ'は、次のように定義される。
【数４】 換言すれば、ｆ(ｘ)が生成多項式であるとき、すなわ
ち、Ｒ'(ｘ)がｆ(ｘ)に相当する予備段階のＣＲＣ符号
語であるとき、Ｒ'(ｘ)は、Ｍ(ｘ)に対するＣＲＣ符号
である。
ち、Ｒ'(ｘ)がｆ(ｘ)に相当する予備段階のＣＲＣ符号
語であるとき、Ｒ'(ｘ)は、Ｍ(ｘ)に対するＣＲＣ符号
である。
【００１３】式（６）は、次のように書くことができ
る。 ｘr-1Ｍ(ｘ)＝Ｑ'(ｘ)・ｆ(ｘ)＋Ｒ'(ｘ) （７） ただし、Ｑ'(ｘ)は、商の多項式である。次に、（１＋
ｘ）に相当する項が、次のように定義される。
る。 ｘr-1Ｍ(ｘ)＝Ｑ'(ｘ)・ｆ(ｘ)＋Ｒ'(ｘ) （７） ただし、Ｑ'(ｘ)は、商の多項式である。次に、（１＋
ｘ）に相当する項が、次のように定義される。
【数５】 つまり、Ｒ"(ｘ)は、Ｑ'(ｘ)を（１＋ｘ）で割ったとき
に得られる剰余である。式（８）は、次のように書くこ
とができる。 Ｑ'(ｘ)＝Ｑ"(ｘ)・（１＋ｘ）＋Ｒ"(ｘ) （９） ただし、Ｑ"(ｘ)は、適切な商多項式である。式（９）
を式（７）に代入し、全体にｘを乗じると、 xrM(x)=x・Q"(x)・(1+x)・f(x)+x・R"(x)・f(x)+x・R'(x) （１０） となる。剰余演算子は線形であるから、式（１０）の全
体を（１＋ｘ）ｆ(ｘ)で割ると、次のようになる。
に得られる剰余である。式（８）は、次のように書くこ
とができる。 Ｑ'(ｘ)＝Ｑ"(ｘ)・（１＋ｘ）＋Ｒ"(ｘ) （９） ただし、Ｑ"(ｘ)は、適切な商多項式である。式（９）
を式（７）に代入し、全体にｘを乗じると、 xrM(x)=x・Q"(x)・(1+x)・f(x)+x・R"(x)・f(x)+x・R'(x) （１０） となる。剰余演算子は線形であるから、式（１０）の全
体を（１＋ｘ）ｆ(ｘ)で割ると、次のようになる。
【数６】 これは、式（１０）の右辺の第１項が剰余０を与えるか
らである。ここで、Ｒ"(ｘ)は、０次であるから、x・R"
(x)・f(x)はｒ次である。（１＋ｘ）ｆ(ｘ)の次数はｒで
ある。従って、剰余
らである。ここで、Ｒ"(ｘ)は、０次であるから、x・R"
(x)・f(x)はｒ次である。（１＋ｘ）ｆ(ｘ)の次数はｒで
ある。従って、剰余
【数７】 を生成するには、１回は除算が必要である。Ｒ"(ｘ)
は、０次であるから、２つの値、すなわち０または１の
何れかをとることができる。項Ｒ"(ｘ)が０の場合、こ
の剰余は０である。項Ｒ"(ｘ)が１ならば、剰余
は、０次であるから、２つの値、すなわち０または１の
何れかをとることができる。項Ｒ"(ｘ)が０の場合、こ
の剰余は０である。項Ｒ"(ｘ)が１ならば、剰余
【数８】 を生成するだけでよく、その結果はｆ(ｘ)である。
【００１４】式（１１）の右辺の第２項については、
Ｒ'(ｘ)がｒ−２次であるから、ｘＲ'(ｘ)はｒ−１次で
ある。分母はｒ次である。従って、結果はｘＲ'(ｘ)で
ある。これには、Ｒ'(ｘ)のビットの左へのシフトを伴
うに過ぎない。所望の最終的な結果は、次のようにな
る。 ｆ(ｘ)＋ｘ・Ｒ'(ｘ) （Ｒ"(ｘ)＝１の場合） Ｒ(ｘ)＝｛ （１２） ｘ・Ｒ'(ｘ) （Ｒ"(ｘ)＝０の場合）
Ｒ'(ｘ)がｒ−２次であるから、ｘＲ'(ｘ)はｒ−１次で
ある。分母はｒ次である。従って、結果はｘＲ'(ｘ)で
ある。これには、Ｒ'(ｘ)のビットの左へのシフトを伴
うに過ぎない。所望の最終的な結果は、次のようにな
る。 ｆ(ｘ)＋ｘ・Ｒ'(ｘ) （Ｒ"(ｘ)＝１の場合） Ｒ(ｘ)＝｛ （１２） ｘ・Ｒ'(ｘ) （Ｒ"(ｘ)＝０の場合）
【００１５】全体的なＣＲＣ符号の生成には、２つの段
階が伴う。すなわち、生成多項式としてｆ(ｘ)を有する
Ｍ(ｘ)の予備段階のＣＲＣ符号であるＲ'(ｘ)の生成、
および（１＋ｘ）に相当する項Ｒ"(ｘ)の生成である。
これらの２つの段階が終了すると、本発明により、式
（１２）を用いることによって、所望の全体的なＣＲＣ
符号、すなわち、剰余Ｒ(ｘ)を非常に簡単に得ることが
できる。
階が伴う。すなわち、生成多項式としてｆ(ｘ)を有する
Ｍ(ｘ)の予備段階のＣＲＣ符号であるＲ'(ｘ)の生成、
および（１＋ｘ）に相当する項Ｒ"(ｘ)の生成である。
これらの２つの段階が終了すると、本発明により、式
（１２）を用いることによって、所望の全体的なＣＲＣ
符号、すなわち、剰余Ｒ(ｘ)を非常に簡単に得ることが
できる。
【００１６】以下において、Ｒ'(ｘ)およびＲ"(ｘ)の並
行的生成を説明する。例として、１６ビットの実施例を
用いる。しかし、勿論、結果は、バイト・ベースでも３
２ビット・ベースでも他の任意の実施例に拡張すること
ができる。
行的生成を説明する。例として、１６ビットの実施例を
用いる。しかし、勿論、結果は、バイト・ベースでも３
２ビット・ベースでも他の任意の実施例に拡張すること
ができる。
【００１７】Ｍ(ｘ)が次の多項式表現を有するものとす
る。
る。
【数９】 ただし、ｋは、メッセージの長さである。式（１３）
は、次のように書ける。
は、次のように書ける。
【数１０】 式（１４）にｘr-1を掛けて、次式を得る。
【数１１】 Ｂ-1＝０ を境界条件として、次の漸化式を定義する。
【数１２】 式（１７）の定義より、
【数１３】 従って、式（１６）は、次のように書ける。 ｘr-1・Ｍ(ｘ)＝Ａ0・ｘr-1＋Ｂk-2 （１９） 次のようにｒi(ｘ)を帰納的に定義する。
【数１４】 境界条件はｒ-1(ｘ)＝０である。式（２０）の代わり
に、次のように表現できる。 Ａk-1-i・ｘr-1＋ｘ16・ｒi-1(ｘ)＝ｆ(ｘ)・Ｃi(ｘ)＋ｒi(ｘ) （２１） ただし、Ｃi(ｘ)は、適当な商多項式である。
に、次のように表現できる。 Ａk-1-i・ｘr-1＋ｘ16・ｒi-1(ｘ)＝ｆ(ｘ)・Ｃi(ｘ)＋ｒi(ｘ) （２１） ただし、Ｃi(ｘ)は、適当な商多項式である。
【００１８】式（２１）を式（１７）に代入して、次式
を得る。 Ｂ0＝ｘ16・ｒ0(ｘ)＋ｘ16・ｆ(ｘ)・Ｃ0(ｘ) （２２） 式（２２）および式（２１）を式（１７）に代入して、
次式を得る。 Ｂ1＝ｘ16・ｒ1(ｘ)＋ｘ16・ｆ(ｘ)［Ｃ1(ｘ)＋ｘ16 ・Ｃ0(ｘ)］ （２３） 式（１７）の帰納的処理を実行すると、次のようにな
る。
を得る。 Ｂ0＝ｘ16・ｒ0(ｘ)＋ｘ16・ｆ(ｘ)・Ｃ0(ｘ) （２２） 式（２２）および式（２１）を式（１７）に代入して、
次式を得る。 Ｂ1＝ｘ16・ｒ1(ｘ)＋ｘ16・ｆ(ｘ)［Ｃ1(ｘ)＋ｘ16 ・Ｃ0(ｘ)］ （２３） 式（１７）の帰納的処理を実行すると、次のようにな
る。
【数１５】 式（２４）を式（１９）に入れると、
【数１６】 となる。剰余演算子は、線形である。
【００１９】式（２５）をｆ(ｘ)で割ると、
【数１７】 となる。これは、式（２５）の右辺の第２項が、剰余０
を生じるからである。また、
を生じるからである。また、
【数１８】 ただし、Ｑ'は、既に定義したように、式（２６）にお
ける除算によって生成される商である。次の漸化式でＤ
i(ｘ)を定義する。 Ｄi(ｘ)＝ｘ16［Ｃi(ｘ)＋Ｄi-1(ｘ)］ （２８） この境界条件は、 Ｄ-1＝０ である。式（２８）の帰納的処理を実行すると、次のよ
うになる。 Ｑ'(ｘ)＝Ｃk-1(ｘ)＋Ｄk-2(ｘ) （２９） 次のようにti(ｘ)を定義する。
ける除算によって生成される商である。次の漸化式でＤ
i(ｘ)を定義する。 Ｄi(ｘ)＝ｘ16［Ｃi(ｘ)＋Ｄi-1(ｘ)］ （２８） この境界条件は、 Ｄ-1＝０ である。式（２８）の帰納的処理を実行すると、次のよ
うになる。 Ｑ'(ｘ)＝Ｃk-1(ｘ)＋Ｄk-2(ｘ) （２９） 次のようにti(ｘ)を定義する。
【数１９】 境界条件は、 ｔ-1＝０ である。式（３０）は、代わりに次のように書くことが
できる。 Ｃi(ｘ)＋ｘ16・ｔi-1(ｘ)＝（１＋ｘ）Ｅi(ｘ)＋ｔi(ｘ) （３１） ただし、Ｅi(ｘ)は、商多項式である。式（３１）を式
（２８）に代入し、帰納的処理を実行して式（２９）と
結合すると、次式を得る。
できる。 Ｃi(ｘ)＋ｘ16・ｔi-1(ｘ)＝（１＋ｘ）Ｅi(ｘ)＋ｔi(ｘ) （３１） ただし、Ｅi(ｘ)は、商多項式である。式（３１）を式
（２８）に代入し、帰納的処理を実行して式（２９）と
結合すると、次式を得る。
【数２０】 式（３２）全体を（１＋ｘ）によって割り、剰余が線形
演算子であるという事実を用いて、次式を得る。
演算子であるという事実を用いて、次式を得る。
【数２１】
【００２０】全面的実施に到るために、式（２６）の
Ｒ'(ｘ)を帰納的に求め、式（３３）のＲ"(ｘ)を帰納的
に求める。
Ｒ'(ｘ)を帰納的に求め、式（３３）のＲ"(ｘ)を帰納的
に求める。
【００２１】Ｒ'(ｘ)の生成に伴う重要な段階は、式
（２０）によって指定される帰納処理である。ｆ(ｘ)は
ｒ−１次であるから、ｒi-1はｒ−２次である。従っ
て、ｘ16・ｒi-1は、１４＋ｒ次である。Ａk-1-iは１５
次であるから、Ａk-1-i（ｘr-1）も１４＋ｒである。ｆ
(ｘ)による除算の実行にブロック除算回路を使用すれ
ば、剰余が帰還され、到来する１６ビットに加えられ
る。
（２０）によって指定される帰納処理である。ｆ(ｘ)は
ｒ−１次であるから、ｒi-1はｒ−２次である。従っ
て、ｘ16・ｒi-1は、１４＋ｒ次である。Ａk-1-iは１５
次であるから、Ａk-1-i（ｘr-1）も１４＋ｒである。ｆ
(ｘ)による除算の実行にブロック除算回路を使用すれ
ば、剰余が帰還され、到来する１６ビットに加えられ
る。
【００２２】Ｒ"(ｘ)を生成するのに重要な段階は、式
（３０）によって与えられる。ここで、ｔi-1は０次で
あり、ｘ16ｔi-1は１６次である。Ｃi(ｘ)は１５次であ
る。まず、一般的な多項式に対するＣi(ｘ)を生成し、
（１＋ｘ）による除算をブロック除算回路によって行
う。
（３０）によって与えられる。ここで、ｔi-1は０次で
あり、ｘ16ｔi-1は１６次である。Ｃi(ｘ)は１５次であ
る。まず、一般的な多項式に対するＣi(ｘ)を生成し、
（１＋ｘ）による除算をブロック除算回路によって行
う。
【００２３】この実施および本発明の技術的利点は、ｆ
(ｘ)に相当する予備段階のＣＲＣ符号および（１＋ｘ）
に相当する項が互いに完全に独立して同時並列的に生成
されることである。
(ｘ)に相当する予備段階のＣＲＣ符号および（１＋ｘ）
に相当する項が互いに完全に独立して同時並列的に生成
されることである。
【００２４】典型的な実施例 以下において、本発明の実施例を、次のＣＲＣ符号生成
多項式について説明する。 Ｇ(ｘ)＝（１＋ｘ2＋ｘ15＋ｘ17＋ｘ30＋ｘ31） ＝（１＋ｘ）（１＋ｘ＋ｘ15＋ｘ16＋ｘ30） （３４）
多項式について説明する。 Ｇ(ｘ)＝（１＋ｘ2＋ｘ15＋ｘ17＋ｘ30＋ｘ31） ＝（１＋ｘ）（１＋ｘ＋ｘ15＋ｘ16＋ｘ30） （３４）
【００２５】図１において、（１＋ｘ）ｆ(ｘ)という形
式の生成多項式を用いてＣＲＣ符号Ｒ'(ｘ)が並行して
生成される。同図には、メッセージ源１０１、予備段階
ＣＲＣ符号語Ｒ'(ｘ)生成器１０２、Ｒ"(ｘ)項生成器１
０３、および結合論理回路１０４が示されている。メッ
セージ源１０１には、ＣＲＣ符号Ｒ(ｘ)が生成される対
象であるメッセージＭ(ｘ)を得るために伝送路１００な
どへのインタフェースをとる装置も含まれる。メッセー
ジＭ(ｘ)の所定のビット長Ａiのブロックが、メッセー
ジ源１０１から予備段階ＣＲＣ符号Ｒ'(ｘ)生成器１０
２およびＲ"(ｘ)項生成器１０３の両方に供給される。
この例では、Ａiビットの各ブロックは、１６ビットを
並列に含んでいるが、これは本発明の範囲を制限するも
のではない。予備段階ＣＲＣ符号Ｒ'(ｘ)生成器１０２
は、供給されたメッセージＭ(ｘ)のＡiビットのブロッ
クに応答して、理論的説明において既に述べたような要
領で、すなわち、式（２６）に従って、ｆ(ｘ)に相当す
るＣＲＣ符号Ｒ'(ｘ)を生成する。また、Ｒ"(ｘ)項生成
器１０３は、供給されるＡiビットのブロックに応答し
て、同様に理論的説明において既に述べたように、すな
わち、式（３３）に従って、項Ｒ"(ｘ)を生成する。
尚、Ｒ'(ｘ)およびＲ"(ｘ)が出力として供給されるの
は、ＣＲＣ符号Ｒ(ｘ)が生成されている対象のメッセー
ジＭ(ｘ)全体のビットＡiのブロックが生成器１０２お
よび１０３の両方にすべて入力された後であるという点
に注意を要する。その後、結合論理回路１０４が、理論
的説明において既に述べたように、すなわち、式（１
２）に従って、Ｒ'(ｘ)およびＲ"(ｘ)を結合して所望の
ＣＲＣ符号語Ｒ(ｘ)を与える。尚、ＣＲＣ符号生成多項
式である式（３４）については、Ｒ'(ｘ)が２９次、Ｒ"
(ｘ)が１次、そしてＲ(ｘ)が３０次である。さらに、生
成器１０３で生成されているＲ"(ｘ)項とは独立して、
予備段階のＣＲＣ符号Ｒ'(ｘ)が生成器１０２において
生成される。
式の生成多項式を用いてＣＲＣ符号Ｒ'(ｘ)が並行して
生成される。同図には、メッセージ源１０１、予備段階
ＣＲＣ符号語Ｒ'(ｘ)生成器１０２、Ｒ"(ｘ)項生成器１
０３、および結合論理回路１０４が示されている。メッ
セージ源１０１には、ＣＲＣ符号Ｒ(ｘ)が生成される対
象であるメッセージＭ(ｘ)を得るために伝送路１００な
どへのインタフェースをとる装置も含まれる。メッセー
ジＭ(ｘ)の所定のビット長Ａiのブロックが、メッセー
ジ源１０１から予備段階ＣＲＣ符号Ｒ'(ｘ)生成器１０
２およびＲ"(ｘ)項生成器１０３の両方に供給される。
この例では、Ａiビットの各ブロックは、１６ビットを
並列に含んでいるが、これは本発明の範囲を制限するも
のではない。予備段階ＣＲＣ符号Ｒ'(ｘ)生成器１０２
は、供給されたメッセージＭ(ｘ)のＡiビットのブロッ
クに応答して、理論的説明において既に述べたような要
領で、すなわち、式（２６）に従って、ｆ(ｘ)に相当す
るＣＲＣ符号Ｒ'(ｘ)を生成する。また、Ｒ"(ｘ)項生成
器１０３は、供給されるＡiビットのブロックに応答し
て、同様に理論的説明において既に述べたように、すな
わち、式（３３）に従って、項Ｒ"(ｘ)を生成する。
尚、Ｒ'(ｘ)およびＲ"(ｘ)が出力として供給されるの
は、ＣＲＣ符号Ｒ(ｘ)が生成されている対象のメッセー
ジＭ(ｘ)全体のビットＡiのブロックが生成器１０２お
よび１０３の両方にすべて入力された後であるという点
に注意を要する。その後、結合論理回路１０４が、理論
的説明において既に述べたように、すなわち、式（１
２）に従って、Ｒ'(ｘ)およびＲ"(ｘ)を結合して所望の
ＣＲＣ符号語Ｒ(ｘ)を与える。尚、ＣＲＣ符号生成多項
式である式（３４）については、Ｒ'(ｘ)が２９次、Ｒ"
(ｘ)が１次、そしてＲ(ｘ)が３０次である。さらに、生
成器１０３で生成されているＲ"(ｘ)項とは独立して、
予備段階のＣＲＣ符号Ｒ'(ｘ)が生成器１０２において
生成される。
【００２６】図２に示したように、メッセージＭ(ｘ)の
Ａiビットの各ブロックにおけるビットａ(i-16)ｘ0〜ａ
(i-1)ｘ15が、対応する複数の排他的ＯＲゲートへと供
給され、さらにレジスタ２０１の各段へと供給される。
この例におけるレジスタ２０１は、１６段のシフト・レ
ジスタである。レジスタ２０１からの出力は、別の排他
的ＯＲゲートにおいて結合されて、レジスタ２０２に供
給される。この例では、レジスタ２０２も、ＡからＮま
での段を備えたシフト・レジスタである。レジスタ２０
１および２０２は、すべての段がゼロ（０）状態となる
ように初期化される。尚、レジスタ２０１および２０２
からの出力は、組合わさって予備段階のＣＲＣ符号Ｒ'
(ｘ)を形成するが、説明を明晰にするために図示してい
ない。レジスタ２０１および２０２からの出力は、図３
において、メッセージＭ(ｘ)のＡiビットのすべてのブ
ロックが処理された後に、出力制御３０２の制御下で可
制御スイッチ３０１を通る出力として供給されるように
示してある。尚、＋記号を円で囲んだ記号は、排他的Ｏ
Ｒゲートを表し、レジスタの段または排他的ＯＲゲート
に入る矢印は、入力を表し、レジスタ段または排他的Ｏ
Ｒゲートから出る矢印は、出力を表す。
Ａiビットの各ブロックにおけるビットａ(i-16)ｘ0〜ａ
(i-1)ｘ15が、対応する複数の排他的ＯＲゲートへと供
給され、さらにレジスタ２０１の各段へと供給される。
この例におけるレジスタ２０１は、１６段のシフト・レ
ジスタである。レジスタ２０１からの出力は、別の排他
的ＯＲゲートにおいて結合されて、レジスタ２０２に供
給される。この例では、レジスタ２０２も、ＡからＮま
での段を備えたシフト・レジスタである。レジスタ２０
１および２０２は、すべての段がゼロ（０）状態となる
ように初期化される。尚、レジスタ２０１および２０２
からの出力は、組合わさって予備段階のＣＲＣ符号Ｒ'
(ｘ)を形成するが、説明を明晰にするために図示してい
ない。レジスタ２０１および２０２からの出力は、図３
において、メッセージＭ(ｘ)のＡiビットのすべてのブ
ロックが処理された後に、出力制御３０２の制御下で可
制御スイッチ３０１を通る出力として供給されるように
示してある。尚、＋記号を円で囲んだ記号は、排他的Ｏ
Ｒゲートを表し、レジスタの段または排他的ＯＲゲート
に入る矢印は、入力を表し、レジスタ段または排他的Ｏ
Ｒゲートから出る矢印は、出力を表す。
【００２７】図４は、図１のＲ"(ｘ)項生成器１０３に
おいて利用するのに好都合な構造の１つの略ブロック図
である。メッセージＭ(ｘ)のＡiビットの各ブロックに
おけるビットａ(i-16)ｘ0〜ａ(i-1)ｘ15が、レジスタ４
０１の段０〜１５にそれぞれ供給される。レジスタ４０
１は、各段がゼロ（０）状態となるように初期化され
る。レジスタ４０１の段０〜１３および１５および１６
の出力は、図のように排他的ＯＲゲートによって結合さ
れる。メッセージＭ(ｘ)のすべてのブロックＡiを処理
した後で排他的ＯＲをとった最終的な結果が、レジスタ
４０１の段１６に入力として供給される。レジスタ４０
１の段１６からの出力が、所望の項Ｒ"(ｘ)であり、メ
ッセージＭ(ｘ)のＡiビットのすべてのブロックが処理
された後に、出力制御４０３の制御下で可制御スイッチ
４０２を介して出力として供給される。既に指摘したよ
うに、＋記号を円で囲んだ記号は、排他的ＯＲゲートを
表し、レジスタの段または排他的ＯＲゲートに入る矢印
は、入力を表し、レジスタ段または排他的ＯＲゲートか
ら出る矢印は、出力を表す。
おいて利用するのに好都合な構造の１つの略ブロック図
である。メッセージＭ(ｘ)のＡiビットの各ブロックに
おけるビットａ(i-16)ｘ0〜ａ(i-1)ｘ15が、レジスタ４
０１の段０〜１５にそれぞれ供給される。レジスタ４０
１は、各段がゼロ（０）状態となるように初期化され
る。レジスタ４０１の段０〜１３および１５および１６
の出力は、図のように排他的ＯＲゲートによって結合さ
れる。メッセージＭ(ｘ)のすべてのブロックＡiを処理
した後で排他的ＯＲをとった最終的な結果が、レジスタ
４０１の段１６に入力として供給される。レジスタ４０
１の段１６からの出力が、所望の項Ｒ"(ｘ)であり、メ
ッセージＭ(ｘ)のＡiビットのすべてのブロックが処理
された後に、出力制御４０３の制御下で可制御スイッチ
４０２を介して出力として供給される。既に指摘したよ
うに、＋記号を円で囲んだ記号は、排他的ＯＲゲートを
表し、レジスタの段または排他的ＯＲゲートに入る矢印
は、入力を表し、レジスタ段または排他的ＯＲゲートか
ら出る矢印は、出力を表す。
【００２８】図５において、結合論理回路は、既に示し
たように式（１２）の条件を満たすように動作する。つ
まり、Ｒ"(ｘ)がゼロならば、Ｒ'(ｘ)のビットを左に１
回シフトすることによって、所望のＣＲＣ符号Ｒ(ｘ)が
得られる。Ｒ"(ｘ)が１ならば、Ｒ'(ｘ)のビットを左に
１回シフトし、さらにシフトしたＲ'(ｘ)に関数ｆ(ｘ)
を加えることによって、所望のＣＲＣ符号Ｒ(ｘ)が得ら
れる。
たように式（１２）の条件を満たすように動作する。つ
まり、Ｒ"(ｘ)がゼロならば、Ｒ'(ｘ)のビットを左に１
回シフトすることによって、所望のＣＲＣ符号Ｒ(ｘ)が
得られる。Ｒ"(ｘ)が１ならば、Ｒ'(ｘ)のビットを左に
１回シフトし、さらにシフトしたＲ'(ｘ)に関数ｆ(ｘ)
を加えることによって、所望のＣＲＣ符号Ｒ(ｘ)が得ら
れる。
【００２９】以上の説明は、本発明の一実施例に関する
もので、この技術分野の当業者であれば、本発明の種々
の変形例が考えられるが、それらはいずれも本発明の技
術的範囲に包含される。
もので、この技術分野の当業者であれば、本発明の種々
の変形例が考えられるが、それらはいずれも本発明の技
術的範囲に包含される。
【００３０】
【発明の効果】以上述べたように、本発明によれば、Ｃ
ＲＣ符号を効率的に生成することができる。
ＲＣ符号を効率的に生成することができる。
【図１】ＣＲＣ符号語を並列に生成する構造の略ブロッ
ク図である。
ク図である。
【図２】ｆ(ｘ)に相当する予備段階のＣＲＣ符号語を並
列に生成する構造の略ブロック図である。
列に生成する構造の略ブロック図である。
【図３】図２の予備段階のＣＲＣ符号語生成器１０２の
出力を略ブロック図の形に表した図である。
出力を略ブロック図の形に表した図である。
【図４】（１＋ｘ）に相当する項を生成する構造の略ブ
ロック図である。
ロック図である。
【図５】図１の結合論理回路ユニットの関数を図式的に
表す図である。
表す図である。
１０１ メッセージ源 １０２ 予備段階ＣＲＣ符号Ｒ'(ｘ)生成器 １０３ Ｒ"(ｘ)項生成器 １０４ 結合論理回路
───────────────────────────────────────────────────── フロントページの続き (56)参考文献 特開 平１−265332（ＪＰ，Ａ) 特開 昭58−72253（ＪＰ，Ａ) 特開 昭57−68944（ＪＰ，Ａ) 特開 昭57−25046（ＪＰ，Ａ)
Claims (14)
- 【請求項１】 メッセージＭ(ｘ)の並列ビットＡiのブ
ロックを得るために伝送路へのインタフェースをとるス
テップと、 メッセージＭ(ｘ)のビットＡiの前記ブロックに応答し
て、巡回冗長検査（ＣＲＣ）符号生成多項式としてｆ
(ｘ)を用いて予備段階のＣＲＣ符号語を生成するステッ
プと、 メッセージＭ(ｘ)のビットＡiの前記ブロックに応答し
て、（１＋ｘ）に相当する項を生成するステップと、 全体的なＣＲＣ符号語を得るために、前記の生成された
（１＋ｘ）に相当する項に応じて前記の予備段階ＣＲＣ
符号語を規定の要領で修正するステップを備えて、 メッセージＭ(ｘ)について、（１＋ｘ）ｆ(ｘ)という形
式のＣＲＣ生成多項式を用いて全体的なＣＲＣ符号語を
並列的に生成することを特徴とする巡回冗長検査符号生
成の方法。 - 【請求項２】 前記の予備段階ＣＲＣ符号語および（１
＋ｘ）に相当する項を生成する両ステップが独立して同
時に実行されることを特徴とする請求項１の方法。 - 【請求項３】 生成中の（１＋ｘ）に相当する項が、第
１の規定の状態または第２の規定の状態の何れかを有す
ることを特徴とする請求項２の方法。 - 【請求項４】 前記の修正するステップが、 前記の（１＋ｘ）に相当する項が前記第１の規定の状態
を有するなら、前記の予備段階のＣＲＣ符号語を第１の
規定の方法で修正し、前記の（１＋ｘ）に相当する項が
前記第２の規定の状態を有するなら、前記の予備段階の
ＣＲＣ符号語を第２の規定の方法で修正することを含む
ことを特徴とする請求項３の方法。 - 【請求項５】 前記第１の規定の状態が論理０であり、
前記第２の規定の状態が論理１であり、前記の予備段階
のＣＲＣ符号語を修正する前記第１の規定の方法が、前
記規定の状態が論理０ならば前記の予備段階のＣＲＣ符
号語のビットを左に１回シフトすることからなり、前記
の予備段階のＣＲＣ符号語を修正する前記第２の規定の
方法が、前記規定の状態が論理１ならば前記の予備段階
のＣＲＣ符号語のビットを左に１回シフトし、かつシフ
トされた予備段階のＣＲＣ符号語にｆ(ｘ)を加えること
からなることを特徴とする請求項４の方法。 - 【請求項６】 「Ａ／Ｂ」がＡ÷Ｂの剰余を表すものと
し、Ｒ'(ｘ)が予備段階のＣＲＣ符号語であり、Ｍ(ｘ)
が全体的なＣＲＣ符号語を生成する対象のメッセージで
あり、ｒがＣＲＣ生成多項式の次数であり、かつ（ｒ−
１）がｆ(ｘ)の次数である場合、前記の予備段階のＣＲ
Ｃ符号語が、Ｒ'(ｘ)＝「ｘr-1Ｍ(ｘ)／ｆ(ｘ)」に従っ
て生成されることを特徴とする請求項５の方法。 - 【請求項７】 Ｒ"(ｘ)が（１＋ｘ）に相当する項であ
り、かつＱ'(ｘ)が前記メッセージＭ(ｘ)から得た商多
項式である場合、前記の（１＋ｘ）に相当する項が、
Ｒ"(ｘ)＝「Ｑ'(ｘ)／（１＋ｘ）」に従って生成される
ことを特徴とする請求項６の方法。 - 【請求項８】 メッセージＭ(ｘ)の並列ビットＡiのブ
ロックを得るために伝送路へのインタフェースをとる手
段と、 メッセージＭ(ｘ)のビットＡiの前記ブロックに応答し
て、ＣＲＣ生成多項式としてｆ(ｘ)を用いて予備段階の
ＣＲＣ符号語を生成する手段と、 メッセージＭ(ｘ)のビットＡiの前記ブロックに応答し
て、（１＋ｘ）に相当する項を生成する手段と、 全体的なＣＲＣ符号語を得るために、前記の生成された
（１＋ｘ）に相当する項に応じて前記の予備段階ＣＲＣ
符号語を規定の要領で修正する手段を備えて、 メッセージＭ(ｘ)について、（１＋ｘ）ｆ(ｘ)という形
式のＣＲＣ生成多項式を用いて全体的なＣＲＣ符号語を
並列的に生成することを特徴とする巡回冗長検査符号生
成装置。 - 【請求項９】 前記の予備段階のＣＲＣ符号語を生成す
る手段および前記の（１＋ｘ）に相当する項を生成する
手段が、前記の予備段階のＣＲＣ符号語および前記の
（１＋ｘ）に相当する項を独立して同時に生成すること
を特徴とする請求項８の装置。 - 【請求項１０】 生成中の（１＋ｘ）に相当する項が、
第１の規定の状態または第２の規定の状態の何れかを有
することを特徴とする請求項９の装置。 - 【請求項１１】 前記の修正する手段が、 前記の（１＋ｘ）に相当する項が前記第１の規定の状態
を有する場合に前記の予備段階のＣＲＣ符号語を第１の
規定の方法で修正する手段と、前記の（１＋ｘ）に相当
する項が前記第２の規定の状態を有する場合に前記の予
備段階のＣＲＣ符号語を第２の規定の方法で修正する手
段とを含むことを特徴とする請求項１０の装置。 - 【請求項１２】 前記第１の規定の状態が論理０であ
り、前記第２の規定の状態が論理１であり、前記の予備
段階のＣＲＣ符号語を修正する前記第１の規定の方法
が、前記規定の状態が論理０ならば前記の予備段階のＣ
ＲＣ符号語のビットを左に１回シフトすることからな
り、前記の予備段階のＣＲＣ符号語を修正する前記第２
の規定の方法が、前記規定の状態が論理１ならば前記の
予備段階のＣＲＣ符号語のビットを左に１回シフトし、
かつシフトされた予備段階のＣＲＣ符号語にｆ(ｘ)を加
えることからなることを特徴とする請求項１１の装置。 - 【請求項１３】 「Ａ／Ｂ」がＡ÷Ｂの剰余を表すもの
とし、Ｒ'(ｘ)が予備段階のＣＲＣ符号語であり、Ｍ
(ｘ)が全体的なＣＲＣ符号語を生成する対象のメッセー
ジであり、ｒがＣＲＣ生成多項式の次数であり、かつ
（ｒ−１）がｆ(ｘ)の次数である場合、前記の予備段階
のＣＲＣ符号語を生成する前記手段が、前記の予備段階
のＣＲＣ符号語をＲ'(ｘ)＝「ｘr-1Ｍ(ｘ)／ｆ(ｘ)」に
従って生成する手段を含むことを特徴とする請求項１２
の装置。 - 【請求項１４】 Ｒ"(ｘ)が（１＋ｘ）に相当する項で
あり、かつＱ'(ｘ)が前記メッセージＭ(ｘ)から得た商
多項式である場合、前記の（１＋ｘ）に相当する項を生
成する手段が、前記の（１＋ｘ）に相当する項をＲ"
(ｘ)＝「Ｑ'(ｘ)／（１＋ｘ）」に従って生成する手段
を含むことを特徴とする請求項１４の装置。
Applications Claiming Priority (2)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| US59589990A | 1990-10-11 | 1990-10-11 | |
| US595899 | 1990-10-11 |
Publications (2)
| Publication Number | Publication Date |
|---|---|
| JPH05127934A JPH05127934A (ja) | 1993-05-25 |
| JPH087700B2 true JPH087700B2 (ja) | 1996-01-29 |
Family
ID=24385167
Family Applications (1)
| Application Number | Title | Priority Date | Filing Date |
|---|---|---|---|
| JP3284176A Expired - Fee Related JPH087700B2 (ja) | 1990-10-11 | 1991-10-04 | 巡回冗長検査符号生成の方法および装置 |
Country Status (5)
| Country | Link |
|---|---|
| US (1) | US5282214A (ja) |
| EP (1) | EP0480621B1 (ja) |
| JP (1) | JPH087700B2 (ja) |
| CA (1) | CA2050123C (ja) |
| DE (1) | DE69117857T2 (ja) |
Families Citing this family (22)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| JP2821324B2 (ja) * | 1992-11-04 | 1998-11-05 | 三菱電機株式会社 | 誤り訂正回路 |
| US5390196A (en) * | 1992-11-12 | 1995-02-14 | Bull Hn Information Systems Inc. | Byte-wise determination of a checksum from a CRC-32 polynomial |
| JP3000811B2 (ja) * | 1993-01-25 | 2000-01-17 | 日本電気株式会社 | 巡回符号化およびｃｒｃ装置とその処理方法 |
| GB9312135D0 (en) * | 1993-06-11 | 1993-07-28 | Inmos Ltd | Generation of checking data |
| GB9312136D0 (en) * | 1993-06-11 | 1993-07-28 | Inmos Ltd | Transmission of messages |
| KR950009690B1 (ko) * | 1993-09-14 | 1995-08-26 | 재단법인한국전자통신연구소 | 순환 여유검사(crc) 동기 장치 |
| US5878057A (en) * | 1995-10-06 | 1999-03-02 | Tektronix, Inc. | Highly parallel cyclic redundancy code generator |
| US5805614A (en) * | 1996-07-03 | 1998-09-08 | General Signal Corporation | Fault tolerant switch fabric with control and data correction by hamming codes |
| US5812556A (en) * | 1996-07-03 | 1998-09-22 | General Signal Corporation | Fault tolerant switch fabric with control and data correction by hamming codes and error inducing check register |
| US5796733A (en) * | 1996-07-03 | 1998-08-18 | General Signal Corporation | Time division switching system |
| GB2321374A (en) * | 1997-01-21 | 1998-07-22 | Ico Services Ltd | Spread spectrum satellite communication |
| US6006354A (en) * | 1997-02-12 | 1999-12-21 | Stmicroelectronics, Inc. | Security device for a video digital to analog converter |
| DE69731074T2 (de) * | 1997-04-30 | 2005-10-06 | Hewlett-Packard Development Co., L.P., Houston | Anordnung und Verfahren zur Übertragung von Daten über eine Vielzahl von Kanälen |
| DE19838865C2 (de) * | 1998-08-26 | 2001-03-01 | Ericsson Telefon Ab L M | Parallele CRC Erzeugungsschaltung zum Erzeugen eines CRC Codes und Verfahren zum Generieren einer derartigen Schaltung |
| US6519738B1 (en) * | 2000-03-07 | 2003-02-11 | International Business Machines Corporation | Method and apparatus for high-speed CRC computation based on state-variable transformation |
| US6766493B1 (en) | 2000-12-21 | 2004-07-20 | Cisco Technology, Inc. | Method and apparatus for generating and checking cyclic redundancy code (CRC) values using a CRC generator and binary galois field multiplier |
| US6609225B1 (en) * | 2000-12-21 | 2003-08-19 | Cisco Technology, Inc. | Method and apparatus for generating and checking cyclic redundancy code (CRC) values using a multi-byte CRC generator on a variable number of bytes |
| GB2383725A (en) * | 2001-12-27 | 2003-07-02 | Ubinetics Ltd | Data decoding with Cyclic Redundancy Check |
| US7458006B2 (en) * | 2002-02-22 | 2008-11-25 | Avago Technologies General Ip (Singapore) Pte. Ltd. | Methods for computing the CRC of a message from the incremental CRCs of composite sub-messages |
| US7225387B2 (en) * | 2004-02-03 | 2007-05-29 | International Business Machines Corporation | Multilevel parallel CRC generation and checking circuit |
| US8438265B2 (en) * | 2004-11-04 | 2013-05-07 | International Business Machines Corporation | Method of offloading iSCSI PDU corruption-detection digest generation from a host processing unit, and related iSCSI offload engine |
| JP4935787B2 (ja) * | 2008-09-12 | 2012-05-23 | 日本電気株式会社 | 巡回符号演算処理回路 |
Family Cites Families (13)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| US3805232A (en) * | 1972-01-24 | 1974-04-16 | Honeywell Inf Systems | Encoder/decoder for code words of variable length |
| US3775746A (en) * | 1972-05-19 | 1973-11-27 | Ibm | Method and apparatus for detecting odd numbers of errors and burst errors of less than a predetermined length in scrambled digital sequences |
| US4312068A (en) * | 1976-08-12 | 1982-01-19 | Honeywell Information Systems Inc. | Parallel generation of serial cyclic redundancy check |
| JPS58147807A (ja) * | 1982-02-26 | 1983-09-02 | Toshiba Corp | 誤り訂正回路 |
| US4454600A (en) * | 1982-08-25 | 1984-06-12 | Ael Microtel Limited | Parallel cyclic redundancy checking circuit |
| US4498174A (en) * | 1982-08-25 | 1985-02-05 | Ael Microtel Limited | Parallel cyclic redundancy checking circuit |
| US4677623A (en) * | 1983-11-11 | 1987-06-30 | Hitachi, Ltd. | Decoding method and apparatus for cyclic codes |
| US4593393A (en) * | 1984-02-06 | 1986-06-03 | Motorola, Inc. | Quasi parallel cyclic redundancy checker |
| US4809273A (en) * | 1987-01-29 | 1989-02-28 | International Business Machines Corporation | Device for verifying operation of a checking code generator |
| US4890286A (en) * | 1987-12-11 | 1989-12-26 | Sanyo Electric Co., Ltd. | Method and apparatus for decoding error correcting code |
| US5121396A (en) * | 1988-10-27 | 1992-06-09 | International Business Machines Corp. | Preservation of crc integrity upon intentional data alteration during message transmission |
| US5111463A (en) * | 1989-11-09 | 1992-05-05 | Exabyte Corporation | Error correction method and apparatus |
| US5103451A (en) * | 1990-01-29 | 1992-04-07 | Motorola, Inc. | Parallel cyclic redundancy check circuit |
-
1991
- 1991-08-29 CA CA002050123A patent/CA2050123C/en not_active Expired - Fee Related
- 1991-10-02 DE DE69117857T patent/DE69117857T2/de not_active Expired - Fee Related
- 1991-10-02 EP EP91309021A patent/EP0480621B1/en not_active Expired - Lifetime
- 1991-10-04 JP JP3284176A patent/JPH087700B2/ja not_active Expired - Fee Related
-
1993
- 1993-03-01 US US08/026,236 patent/US5282214A/en not_active Expired - Lifetime
Also Published As
| Publication number | Publication date |
|---|---|
| JPH05127934A (ja) | 1993-05-25 |
| DE69117857D1 (de) | 1996-04-18 |
| EP0480621A2 (en) | 1992-04-15 |
| US5282214A (en) | 1994-01-25 |
| EP0480621A3 (en) | 1992-05-13 |
| EP0480621B1 (en) | 1996-03-13 |
| CA2050123A1 (en) | 1992-04-12 |
| CA2050123C (en) | 1997-12-09 |
| DE69117857T2 (de) | 1996-08-14 |
Similar Documents
| Publication | Publication Date | Title |
|---|---|---|
| JPH087700B2 (ja) | 巡回冗長検査符号生成の方法および装置 | |
| KR900006666B1 (ko) | 유한체상의 승산기 | |
| EP0114938B1 (en) | On-the-fly multibyte error correction | |
| US6467063B1 (en) | Reed Solomon coding apparatus and Reed Solomon coding method | |
| US4797848A (en) | Pipelined bit-serial Galois Field multiplier | |
| JP4777258B2 (ja) | ガロア体乗算のためのルックアップテーブルを使用するリード・ソロモン符号の符号化および復号化 | |
| JPH09507110A (ja) | 有限体反転 | |
| US4994995A (en) | Bit-serial division method and apparatus | |
| JPH10135848A (ja) | リードソロモン符号化装置およびその方法 | |
| JP3354025B2 (ja) | エラー位置多項式の計算方法およびその装置 | |
| US6295626B1 (en) | Symbol based algorithm for hardware implementation of cyclic redundancy check | |
| US6751773B2 (en) | Coding apparatus capable of high speed operation | |
| JPH11296347A (ja) | ガロワ体乗算器及びガロワ体乗算の方法 | |
| US6895545B2 (en) | System and method for generating cyclic codes for error control in digital communications | |
| CN108809323B (zh) | 循环冗余校验码的生成方法和装置 | |
| US5971607A (en) | Polynomial evaluator for use in a Reed-Solomon decoder | |
| TWI226758B (en) | Encoding method and apparatus for cross interleaved cyclic codes | |
| US6484192B1 (en) | Root finding method and root finding circuit of quadratic polynomial over finite field | |
| JPH06314978A (ja) | チェン・サーチ回路 | |
| JP4057876B2 (ja) | ガロア体掛け算器の制御方法 | |
| JPH06230991A (ja) | 有限体での任意元素の逆数算出方法及び装置 | |
| JP2591611B2 (ja) | ｔ重誤り訂正符号の符号化復号化回路 | |
| JPH1196030A (ja) | 有限体上の乗算方法及び乗算回路 | |
| JPH1065553A (ja) | リードソロモン復号化器用多項式評価装置 | |
| JP2710176B2 (ja) | 誤り位置及び誤りパターン導出回路 |
Legal Events
| Date | Code | Title | Description |
|---|---|---|---|
| R250 | Receipt of annual fees |
Free format text: JAPANESE INTERMEDIATE CODE: R250 |
|
| LAPS | Cancellation because of no payment of annual fees |