RFC3385 日本語訳
3385 Internet Protocol Small Computer System Interface (iSCSI) CyclicRedundancy Check (CRC)/Checksum Considerations. D. Sheinwald, J.Satran, P. Thaler, V. Cavanna. September 2002. (Format: TXT=53450 bytes) (Status: INFORMATIONAL)
プログラムでの自動翻訳です。
RFC一覧
英語原文
Network Working Group D. Sheinwald
Request for Comments: 3385 J. Satran
Category: Informational IBM
P. Thaler
V. Cavanna
Agilent
September 2002
Sheinwaldがコメントのために要求するワーキンググループD.をネットワークでつないでください: 3385年のJ.Satranカテゴリ: 情報のIBMのP.ターレルV.カヴァナAgilent2002年9月
Internet Protocol Small Computer System Interface (iSCSI)
Cyclic Redundancy Check (CRC)/Checksum Considerations
インターネットプロトコルスモールコンピュータシステムインタフェース(iSCSI)周期冗長検査(CRC)/チェックサム問題
Status of this Memo
このMemoの状態
This memo provides information for the Internet community. It does not specify an Internet standard of any kind. Distribution of this memo is unlimited.
このメモはインターネットコミュニティのための情報を提供します。 それはどんな種類のインターネット標準も指定しません。 このメモの分配は無制限です。
Copyright Notice
版権情報
Copyright (C) The Internet Society (2002). All Rights Reserved.
Copyright(C)インターネット協会(2002)。 All rights reserved。
Abstract
要約
In this memo, we attempt to give some estimates for the probability of undetected errors to facilitate the selection of an error detection code for the Internet Protocol Small Computer System Interface (iSCSI).
このメモでは、私たちは、非検出された誤りの確率がインターネットプロトコルSmallコンピュータSystem Interface(iSCSI)のためにエラー検出コードの選択を容易にするようにいくつかの見積りを与えるのを試みます。
We will also attempt to compare Cyclic Redundancy Checks (CRCs) with other checksum forms (e.g., Fletcher, Adler, weighted checksums), as permitted by available data.
また、私たちは、Cyclic Redundancy Checks(CRCs)を他のチェックサムフォームと比べるのを試みるつもりです(例えば、フレッチャー(アドラー)はチェックサムに重みを加えました)、利用可能なデータによって受入れられるように。
1. Introduction
1. 序論
Cyclic Redundancy Check (CRC) codes [Peterson] are shortened cyclic codes used for error detection. A number of CRC codes have been adopted in standards: ATM, IEC, IEEE, CCITT, IBM-SDLC, and more [Baicheva]. The most important expectation from this kind of code is a very low probability for undetected errors. The probability of undetected errors in such codes has been, and still is, subject to extensive studies that have included both analytical models and simulations. Those codes have been used extensively in communications and magnetic recording as they demonstrate good "burst error" detection capabilities, but are also good at detecting several independent bit errors. Hardware implementations are very simple and well known; their simplicity has made them popular with hardware
周期的なRedundancy Check(CRC)コード[ピーターソン]は誤り検出に使用される短くされた巡回符号です。 多くのCRCコードが規格で採用されました: ATM、IEC、IEEE、CCITT、IBM-SDLC、および、より多くの[Baicheva。] この種類のコードからの最も重要な期待は非検出された誤りのための非常に低い確率です。 そのようなコードの非検出された誤りの確率は、あって、まだあります、分析モデルとシミュレーションの両方を含んでいた広範囲な研究を受けることがあります。 それらのコードも、彼らが良い「バースト誤り」検出能力を示すとき、コミュニケーションと磁気録音に手広く使用されましたが、また、いくつかの独立している噛み付いている誤りを検出するのが上手です。 ハードウェア実装は、非常に簡単であって、よく知られています。 自己の簡単さで、それらはハードウェアにポピュラーになりました。
Sheinwald, et. al. Informational [Page 1] RFC 3385 iSCSI CRC Considerations September 2002
et Sheinwald、アル。 [1ページ]情報のRFC3385iSCSI CRC問題2002年9月
developers for many years. However, algorithms and software for effective implementations of CRC are now also widely available [Williams].
何年間も開発者。 しかしながら、また、CRCの有効な実現のためのアルゴリズムとソフトウェアも現在、広く利用可能です[ウィリアムズ]。
The probability of undetected errors depends on the polynomial selected to generate the code, the error distribution (error model), and the data length.
非検出された誤りの確率はコードを発生させるのが選択された多項式、誤差分布(誤差模型)、およびデータの長さに依存します。
2. Error Models and Goals
2. 誤差模型と目標
We will analyze the code behavior under two conditions:
私たちは2つの条件のもとでコードの振舞いを分析するつもりです:
- noisy channel - burst errors with an average length of n bits
- low noise channel - independent single bit errors
- 騒がしいチャンネル--nビット--低雑音チャンネル--平均した長さの独立しているただ一つの噛み付いている誤りがあるバースト誤り
Burst errors are the prevalent natural phenomenon on communication lines and recording media. The numbers quoted for them revolve around the BER (bit error rate). However, those numbers are frequently nothing more than a reflection of the Burst Error Rate multiplied by the average burst length. In field engineering tests, three numbers are usually quoted together -- BER, error-free-seconds and severely-error-seconds; this illustrates our point.
通信回線とメディアを記録するとき、バースト誤りは一般的な自然現象です。 それらのために引用された数はBER(ビット誤り率)を中心題目とします。 しかしながら、頻繁にそれらの数はただ平均した炸裂の長さが掛けられたBurst Error Rateの反映です。 そして、分野技術試験では、通常、3つの番号が一緒に引用されます--、BER、エラーのない秒、厳しさ、誤り秒、。 これは私たちのポイントを例証します。
Even beyond communication and recording media, the effects of errors will be bursty. An example of this is a memory error that will affect more than a single bit and the total effect will not be very different from the communication error, or software errors that occur while manipulating packets will have a burst effect. Software errors also result in burst errors. In addition, serial internal interconnects will make this type of error the most common within machines as well.
コミュニケーションとメディアを記録することを超えてさえ、誤りの影響はburstyになるでしょう。 この例は単一の1ビット以上に影響するメモリ誤りです、そして、全効果が通信エラーとそれほど異ならないだろうか、またはパケットを操っている間に発生するソフトウェア誤りは炸裂効果を持つでしょう。 また、ソフトウェア誤りはバースト誤りをもたらします。 さらに、連続の内部の内部連絡で、このタイプの誤りはまた、マシンの中に最も一般的になるでしょう。
We also analyze the effects of single independent bit errors, since these may be caused by certain defects.
また、これらが、ある欠陥によって引き起こされるかもしれないので、私たちはただ一つの独立している噛み付いている誤りの影響を分析します。
On burst, we assume an average burst error duration of bd, which at a given transmission rate s, will result in an average burst of a = bd*s bits. (E.g., an average burst duration of 3 ns at 1Gbs gives an average burst of 3 bits.)
炸裂では、私たちはbdの平均したバースト誤り持続時間を仮定します。(与えられた通信速度sでは、bdは=bd*の平均した炸裂をもたらすでしょう)。sビット。 (例えば、1Gbsの3ナノ秒の平均した炸裂持続時間は3ビットの平均した炸裂を与えます。)
For the burst error rate, we will take 10^-10. The numbers quoted for BER on wired communication channels are between 10^-10 to 10^-12 and we consider the BER as burst-error-rate*average-burst-length. Nevertheless, please keep in mind that if the channel includes wireless links, the error rates may be substantially higher.
バースト誤りレートのために、私たちは10^-10を取るつもりです。 10^-10から10^-12の間には、BERのためにワイヤードな通信チャネルで引用された数があります、そして、私たちはBERがバースト誤り率*平均にバースト長さであるとみなします。 それにもかかわらず、チャンネルが無線のリンクを入れるなら、誤り率が実質的により高いかもしれないのを覚えておいてください。
For independent single bit errors, we assume a 10^-11 error rate.
独立しているただ一つの噛み付いている誤りによって、私たちは、10^が-11誤り率であると思います。
Sheinwald, et. al. Informational [Page 2] RFC 3385 iSCSI CRC Considerations September 2002
et Sheinwald、アル。 [2ページ]情報のRFC3385iSCSI CRC問題2002年9月
Because the error detection mechanisms will have to transport large amounts of data (petabytes=10^16 bits) without errors, we will target very low probabilities for undetected errors for all block lengths (at 10Gb/s that much data can be sent in less than 2 weeks on a single link).
誤り検出メカニズムが誤りなしで多量のデータ(ペタバイトは10^と16ビット等しい)を輸送しなければならなくて、私たちはすべてのブロック長(単一のリンクの上の2週間未満で多くのデータを送ることができる10Gb/sの)のための非検出された誤りなので非常に低い確率を狙うつもりです。
Alternatively, as iSCSI has to perform efficiently, we will require that the error detection capability of a selected protection mechanism be very good, at least up to block lengths of 8k bytes (64kbits).
あるいはまた、iSCSIが効率的に働かなければならないとき、私たちは、選択された保護メカニズムの誤り検出能力が非常に良いのを必要とするつもりです、少なくとも8キロバイト(64kbits)のブロック長まで。
The error detection capability should keep the probability of undetected errors at values that would be "next-to-impossible". We recognize, however, that such attributes are hard to quantify and we resorted to physics. The value 10^23 is the Avogadro number while 10^45 is the number of atoms in the known Universe (or it was many years ago when we read about it) and those are the bounds of incertitude we could live with. (10^-23 at worst and 10^-45 if we can afford it.) For 8k blocks, the per/bit equivalent would be (10^-28 to 10^-50).
誤り検出能力は「不可能に次」の値における非検出された誤りの確率を保つべきです。 しかしながら、私たちはそのような属性は定量化しにくくて、物理学に訴えたと認めます。 10^45は知られている宇宙の中の原子数(私たちが何年も前にそれに関して読むとき、それは多かった)ですが、値10^23はAvogadro番号です、そして、それらは私たちが受け入れることができた不確実の領域です。 (10 最悪と10^-45の^-23は私たちであるならそれを都合することができます。) 8kブロック/ビットあたり、同等物は(10^-28から10^-50)でしょう。
3. Background and Literature Survey
3. バックグラウンドと文学調査
Each codeword of a binary (n,k) CRC code C consists of n = k+r bits. The block of r parity bits is computed from the block of k information bits. The code has a degree r generator polynomial g(x).
2進(n、k)のCRCコードCの各符号語はn=k+rビットから成ります。 rパリティビットのブロックはk情報ビットのブロックから計算されます。 コードには、rジェネレータ多項式g(x)が1度あります。
The code is linear in the sense that the bitwise addition of any two codewords yields a codeword.
コードが意味で直線的である、それ、bitwiseする、どんな2つの符号語の添加も符号語をもたらします。
For the minimal m such that g(x) divides (x^m)-1, either n=m, and the code C comprises the set D of all the multiplications of g(x) modulo (x^m)-1, or n<m, and C is obtained from D by shortening each word in the latter in m-n specific positions. (This also reduces the number of words since all zero words are then discarded and duplicates are not maintained.)
最小量のmに関しては、g(x)が(x^m)-1、どちらかのn=m、およびコードCを分割するようなものはg(x)法(x^m)<-1mかn mのすべての掛け算のセットDを包括します、そして、Dからm-n特定の位置で後者における各単語を短くすることによって、Cを得ます。 (また、次に、すべての単語が捨てられるというわけではなくて、写しが維持されないので、これはワード数を減少させます。)
Error detection at the receiving end is made by computing the parity bits from the received information block, and comparing them with the received parity bits.
受信された情報ブロックからパリティビットを計算して、容認されたパリティビットとそれらを比べることによって、犠牲者の誤り検出をします。
An undetected error occurs when the received word c' is a codeword, but is different from the c that is transmitted.
'非検出された誤りは、受信された単語c'が符号語であるときに、起こりますが、伝えられるcと異なっています。
This is only possible when the error pattern e=c'-c is a codeword by itself (because of the linearity of the code). The performance of a CRC code is measured by the probability Pud of undetected channel errors.
'誤りパターンe=c'-cがそれ自体(コードの直線形による)で符号語であるときにだけ、これは可能です。 CRCコードの性能は非検出されたチャンネル誤りの確率Pudによって測定されます。
Sheinwald, et. al. Informational [Page 3] RFC 3385 iSCSI CRC Considerations September 2002
et Sheinwald、アル。 [3ページ]情報のRFC3385iSCSI CRC問題2002年9月
Let Ai denote the number of codewords of weight i, (i.e., with i 1- bits). For a binary symmetric channel (BSC), with sporadic, independent bit error ratio of probability 0<=epsilon<=0.5, the probability of undetected errors for the code C is thus given by:
Aiに重さiの符号語の数を指示させてください、(すなわち、i1ビットがある。) 2進対称チャネル(BSC)に関しては、0<がε<=0.5と等しいという確率の過疎の、そして、独立している噛み付いている誤り比で、以下はコードCのための非検出された誤りの確率をこのようにして与えます。
Pud(C,epsilon) = Sigma[for i=d to n] (Ai*(epsilon^i)*(1-epsilon)^(n-i))
プディング(C、ε)はσ[nへのi=dであることの]と等しいです。(Ai*(ε^i)*(1ε)^(n-i))
where d is the distance of the code: the minimal weight difference between two codewords in C which, by the linearity of the code, is also the minimal weight of any codeword in the code. Pud can also be expressed by the weight distribution of the dual code: the set of words each of which is orthogonal (bitwise AND yields an even number of 1-bits) to every word of C. The fact that Pud can be computed using the dual code is extremely important; while the number of codewords in the code is 2^k, the number of codewords in the dual code is 2^r. k is in the orders of thousands, and r in the order of 16 or 24 or 32. If we use Bi to denote the number of codewords in the dual code which are of weight i, then ([LinCostello]):
dがコードの距離であるところ: またコードの直線形によるコードのどんな符号語の最小量の重さであるCの2つの符号語の最小量の重さの差。 また、二種コード機構の重さの分配でプディングを急送できます: それのそれぞれがC. 二種コード機構を使用することでPudを計算できるという事実のあらゆる単語と直交している(1ビットの偶数をbitwiseして、もたらします)単語のセットは非常に重要です。 コードの符号語の数は2^kですが、二種コード機構の符号語の数は2^r.kが数千の注文、および16か24か32の注文におけるrにあるということです。 私たちであるならBiを使用して、二種コード機構の重さiがある符号語の数を指示してください、そして([LinCostello]):
Pud (C,epsilon) = 2^-r Sigma [for i=0 to n] Bi*(1-2*epsilon)^i - (1-epsilon)^n
プディング(C、ε)は2^r Sigma[nへのi=0であることの]2*(1-2 *ε)^i--(1ε)の^nと等しいです。
Wolf [Wolf94o] introduced an efficient algorithm for enumerating all the codewords of a code and finding their weight distribution.
オオカミ[Wolf94o]はコードのすべての符号語を列挙して、彼らの重さの分配を見つけるための効率的なアルゴリズムを導入しました。
Wolf [Wolf82] found that, counter to what was assumed, (1) there exist codes for which Pud(C,epsilon)>Pud(C,0.5) for some epsilon not=0.5 and (2) Pud is not always increasing for 0<=epsilon<=0.5. The value of what was assumed to be the worst Pud is Pud(C,0.5)=(2^- r) - (2^-n). This stems from the fact that with epsilon=0.5, all 2^n received words are equally likely and out of them 2^(n-r)-1 will be accepted as codewords of no errors, although they are different from the codeword transmitted. Previously Pud had been assumed to equal [2^(n-r)-1]/(2^n-1) or the ratio of the number of non-zero multiples of the polynomial of degree less than n (each such multiple is undetected) and the number of possible error polynomials. With either formula Pud approaches 1/2^r as n approaches infinity, but Wolf's formula is more accurate.
(2) オオカミ[Wolf82]は、(1) 想定されたことへのカウンタ、いくらかのεのためのPud(C、ε)>Pud(C、0.5)が0.5と等しくないコードが存在するのがわかりました、そして、プディングはε<0<==0.5のためにいつも増加しているというわけではありません。 何が最も悪いPudであると思われたかに関する値はPud(C、0.5)=(2^r)です--(2^n。) これはε=0.5で、すべての2^n受信された単語が等しくありそうであり、それらから、2^(n-r)-1が誤りがない符号語として認められるという事実に由来します、それらは伝えられた符号語と異なっていますが。 以前、Pudが/(2^n-1)かn(そのような各倍数は非検出される)の度の多項式の非ゼロ倍数の数と可能な誤り多項式の数の比率と等しいと[2^(n-r)-1]思われました。 どちらの公式でも、nが無限にアプローチするのに応じて、Pudは1/2^rにアプローチしますが、ヴォルフの公式は、より正確です。
Wolf [Wolf94j] investigated the CCITT code of r=16 parity bits. This code is a member of the family of (shortened codes of) BCH codes of length 2^(r-1) -1 (r=16 in the CCITT 16-bit case) generated by a polynomial of the form g(x) =(x+1)p(x) with p(x) being a primitive polynomial of degree r-1 (=15 in this case). These codes have a BCH design distance of 4. That is, the minimal distance between any two codewords in the code is at least 4 bits (which is earned by the fact
オオカミ[Wolf94j]はr=16パリティビットのCCITTコードを調査しました。 このコードが家族のメンバーである、(コードを短くする、)、フォームg(x)の多項式で発生する-1(CCITTの16ビットの場合におけるr=16)の長さ2^(r-1)のBCHコードは(x+1)p(x)と度r-1(この場合、=15)の原始多項式であるp(x)で等しいです。 これらのコードには、4のBCHデザイン距離があります。 すなわち、コードのどんな2つの符号語の間の最小量の距離が少なくとも4ビットである、(どれが事実によって稼がれるか。
Sheinwald, et. al. Informational [Page 4] RFC 3385 iSCSI CRC Considerations September 2002
et Sheinwald、アル。 [4ページ]情報のRFC3385iSCSI CRC問題2002年9月
that the sequence of powers of alpha, the root of p(x), which are roots of g(x), includes three consecutive powers -- alpha^0, alpha^1, alpha^2). Hence, every 3 single bit errors are detectable.
アルファの強国、p(x)の根の系列であり、どれがあるかがg(x)を根づかせるのが3つの連続した強国を含んでいます--アルファ^0、アルファ^1、アルファ^2)。 したがって、3つのただ一つの噛み付いている誤り毎が検出可能です。
Wolf found that different shortened versions of a given code, of the same codeword length, perform the same (independent of which specific indexes are omitted from the original code). He also found that for the unshortened codes, all primitive polynomials yield codes of the same performance. But for the shortened versions, the choice of the primitive polynomial does make a difference. Wolf [Wolf94j] found a primitive polynomial which (when multiplied by x+1) yields a generating polynomial that outperforms the CCITT one by an order of magnitude. For 32-bit redundancy bits, he found an example of two polynomials that differ in their probability of undetected burst of length 33 by 4 orders of magnitude.
ヴォルフは、与えられたコード、同じ符号語の長さの異なった短縮版が同じように(の如何にかかわらず特定のインデックスが元のコードから省略される)働くのがわかりました。 また、彼は、非短くされたコードのために、すべての原始多項式が同じ性能のコードをもたらすのがわかりました。 しかし、短縮版のために、原始多項式の選択に効果があります。 オオカミ[Wolf94j]はCCITT1より1桁優れている発生多項式をもたらす(x+1が掛けられるとき)原始多項式を見つけました。 32ビットの冗長ビットに関しては、彼はそれらの長さ33の非検出された炸裂の確率において4桁異なる2つの多項式に関する例を見つけました。
It so happens, that for some shortened codes, the minimum distance, or the distribution of the weights, is better than for others derived from different unshortened codes.
いくつかの短くされたコードのためのそれ(最小の距離、または重りの分配)は、したがって、それが起こって、異なった非短くされたコードから得られた他のものより良いです。
Baicheva, et. al. [Baicheva] made a comprehensive comparison of different generating polynomials of degree 16 of the form g(x) = (x+1)p(x), and of other forms. They computed their Pud for code lengths up to 1024 bits. They measured their "goodness" -- if Pud(C,epsilon) <= Pud(C,0.5) and being "well-behaved" -- if Pud(C,epsilon) increases with epsilon in the range (0,0.5). The paper gives a comprehensive table that lists which of the polynomials is good and which is well-behaved for different length ranges.
et Baicheva、アル。 [Baicheva]はフォームg(x)=(x+1)p(x)、および他の用紙の度16の異なった発生多項式の包括的な比較をしました。彼らは最大1024ビットのコードの長さのために自分達のPudを計算しました。 εに従ってPud(C、ε)が範囲(0、0.5)で増加するならPud(C、ε)<がプディング(C、0.5)と「品行方正」であるのと等しいなら、彼らは自分達の「善良」を測定しました。 紙は記載する包括的なテーブルを与えます(利益であって異なった長さの範囲に、どれが品行方正であるかという多項式のことです)。
For a single burst error, Wolf [Wolf94J] suggested the model of (b:p) burst -- the errors only occur within a span of b bits, and within that span, the errors occur randomly, with a bit error probability 0 <= p <= 1.
シングル・バースト誤りによって、ヴォルフ[Wolf94J]は、(b: p)のモデルがはち切れたと示唆しました--誤りはbビットの長さの中に発生するだけです、そして、その長さの中では、誤りは手当たりしだいに発生します、0<がp<=1と等しいというしばらくエラー確率で。
For p=0.5, which used to be considered the worst case, it is well known [Wolf94J] that the probability of undetected one burst error of length b <= r is 0, of length b=r+1 is 2^-(r-1), and of b > r+1, is 2^-r, independently of the choice of the primitive polynomial.
p=0.5に関しては、長さのb<=rの1つの非検出されたバースト誤りの確率が0である、b=r+1が長さにおいて、2^(r-1)であり、b>r+1についてそうする[Wolf94J]、選択の如何にかかわらず2^rが原始多項式のものであることがよく知られています。(p=0.5は以前は最悪の場合であるとよく考えられていました)。
With Wolf's definition, where p can be different from 0.5, indeed it was found that for a given b there are values of p, different from 0.5 which maximize the probability of undetected (b:p) burst error.
本当に、ヴォルフの定義で、pが0.5と異なる場合があるところで当然のことbに関してpの値があります、それが非検出された(b: p)バースト誤りの確率を最大にする0.5と異なっているのがわかりました。
Sheinwald, et. al. Informational [Page 5] RFC 3385 iSCSI CRC Considerations September 2002
et Sheinwald、アル。 [5ページ]情報のRFC3385iSCSI CRC問題2002年9月
Wolf proved that for a given code, for all b in the range r < b < n, the conditional probability of undetected error for the (n, n-r) code, given that a (b:p) burst occurred, is equal to the probability of undetected errors for the same code (the same generating polynomial), shortened to block length b, when this shortened code is used with a binary symmetric channel with channel (sporadic, independent) bit error probability p.
ヴォルフは、これがコードを短くしたとき、(b: p)炸裂が起こったなら(n、n-r)コードがブロック長bに短くされた同じコード(多項式を発生させる同じくらい)のための非検出された誤りの確率と等しいので与えられたコード、範囲r<b<nのすべてのbに、非検出された誤りの条件付き確率が2進対称チャネルと共にチャンネル(過疎の、そして、独立している)ビットエラー確率pで使用されると立証しました。
For the IEEE-802.3 used CRC32, Fujiwara et al. [Fujiwara89] measured the weights of all words of all shortened versions of the IEEE 802.3 code of 32 check bits. This code is generated by a primitive polynomial of degree 32:
IEEE-802.3の中古のCRC32、フジワラ他のために [Fujiwara89]は32のチェックビットのIEEE802.3コードのすべての短縮版のすべての単語の重りを測定しました。 このコードは度32の原始多項式で発生します:
g(x) = x^32 + x^26 + x^23 + x^22 + x^16 + x^12 + x^11 + x^10 + x^8 + x^7 + x^5 + x^4 + x^2 + x + 1 and hence the designed distance of it is only 3. This distance holds for codes as long as 2^32-1. However, the frame format of the MAC (Media Access Control) of the data link layer in IEEE 802.3, as well as that of the data link layer for the Ethernet (1980) forbid lengths exceeding 12,144 bits. Thus, only such bounded lengths are investigated in [Fujiwara89]. For shortened versions, the minimum distance was found to be 4 for lengths 4096 to 12,144; 5 for lengths 512 to 2048; and even 15 for lengths 33 through 42. A chart of results of calculations of Pud is presented in [Fujiwara89] from which we can see that for codes of length 12,144 and BSC of epsilon = 10^-5 - 10^-4, Pud(12,144,epsilon)= 10^-14 - 10^-13 and for epsilon = 10^-4 - 10^-3, Pud(512,epsilon) = 10^-15, Pud(1024,epsilon) = 10^-14, Pud(2048,epsilon) = 10^-13, Pud(4096,epsilon) = 10^-12 - 10^-11, and Pud(8192,epsilon) = 10^-10 which is rather close to 2^-32.
g(x)=x^32+x^26+x^23+x^22+x^16+x^12+x^11+x^10+x^8+x^7+x^5+x^4+x^2+x+1としたがって、それの設計された距離は3にすぎません。 この距離はコードに2^32-1と同じくらい長い間、当てはまります。 しかしながら、IEEEのデータ・リンク層のMAC(メディアAccess Control)のフレーム形式は上回っている1万2144ビットを長さに同じくらい802.3に、イーサネット(1980)のためのデータ・リンク層のものと同じくらいよく禁じます。 そのような境界がある長さだけが[Fujiwara89]で調査されます。 短縮版において、最小の距離は長さのための4096〜1万2144に4であることがわかりました。 5 長さ512〜2048のために。 そして、長さ33〜42のための15さえ。 図..結果..計算..提示..見る..コード..長さ..等しい..等しい..むしろ..およそ
Castagnoli, et. al. [Castagnoli93] extended Fujiwara's technique for efficiently calculating the minimum distance through the weight distribution of the dual code and explored a large number of CRC codes with 24 and 32 redundancy bit. They explored several codes built as a multiplication of several lower degree irreducible polynomials.
et Castagnoli、アル。 [Castagnoli93]は、二種コード機構の重さの分配で効率的に最小の距離について計算するためにフジワラのテクニックを広げて、24と32冗長ビットで多くのCRCコードを探りました。 彼らはいくつかの低い度既約多項式の乗法として築き上げられたいくつかのコードを探りました。
In the popular class of (x+1)*deg31-irreducible-polynomial they explored 47000 polynomials (not all the possible ones). The best they found has d=6 up to block lengths of 5275 and d=4 up to 2^31-1 (bits).
ポピュラーなクラスの(x+1)*deg31-既約多項式で、彼らは47000の多項式(すべての可能なものでない)を探りました。 彼らが見つけた中で最も良いものには、5275年のブロック長までのd=6とd=4最大2^31-1(ビット)があります。
The investigation was done in 1993 with a special purpose processor.
1993年に専用プロセッサで調査をしました。
By comparison, the IEEE-802 code has d=4 up to at least 64,000 bits (Fujikura stopped looking at 12,144) and d=3 up to 2^32-1 bits.
比較で、IEEE-802コードにはd=4が少なくとも6万4000ビット(1万2144を見るのが止められたフジクラ)とd=3最大2^まで32-1ビットあります。
Sheinwald, et. al. Informational [Page 6] RFC 3385 iSCSI CRC Considerations September 2002
et Sheinwald、アル。 [6ページ]情報のRFC3385iSCSI CRC問題2002年9月
CRC32/4 (we will refer to it as CRC32C for the remainder of this memo) is 11EDC6F41; IEEE-802 CRC is 104C11DB7, denoting the coefficients as a bit vector.
CRC32/4(私たちはこのメモの残りのためのCRC32Cとそれを呼ぶつもりである)は11EDC6F41です。 しばらくベクトルとして係数を指示して、IEEE-802 CRCは104C11DB7です。
[Stone98] evaluated the performance of CRC (the AAL5 CRC that is the same as IEEE802) and the TCP and Fletcher checksums on large amounts of data. The results of this experiment indicate a serious weakness of the checksums on real-data that stems from the fact that checksums do not spread the "hot spots" in input data. However, the results show that Fletcher behaves by a factor of 2 better than the regular TCP checksum.
[Stone98]は多量のデータでCRC(IEEE802と同じAAL5 CRC)、TCP、およびフレッチャーチェックサムの性能を評価しました。 この実験の結果はチェックサムが入力データの「ホットスポット」を広げないという事実による本当のデータでチェックサムの重大な弱点を示します。 しかしながら、結果は、フレッチャーが2の要素で通常のTCPチェックサムよりよく振る舞うのを示します。
4. Probability of Undetected Errors - Burst Error
4. Undetected誤りの確率--バースト誤り
4.1 CRC32C (Derivations from [Wolf94j])
4.1 CRC32C([Wolf94j]からの派生)
Wolf [Wolf94j] found a 32-bit polynomial of the form g(x) = (1+x)p(x) for which the conditional probability of undetected error, given that a burst of length 33 occurred, is at most (i.e., maximized over all possible channel bit error probabilities within the burst) 4 * 10^- 10.
オオカミ[Wolf94j]は、フォームg(x)の32ビットの多項式が長さ33の炸裂が起こったなら非検出された誤りの条件付き確率が高々(すなわち、炸裂の中でエラー確率をすべての可能なチャンネルビットの上最大にします)4*10^-10である(1+x)p(x)と等しいのがわかりました。
We will now figure the probability of undetected error, given that a burst of length 34 occurred, using the result derived in this paper, namely that for a given code, for all b in the range 32 < b < n, the conditional probability of undetected error for the (n, n-32) code, given that a (b:p) burst occurred, is equal to the probability of undetected errors for the same code (the same generating polynomial), shortened to block length b, when this shortened code is used with a binary symmetric channel with channel (sporadic, independent) bit error probability p.
私たちは、現在、この紙で引き出された結果を使用して、長さ34の炸裂が起こって、すなわち、(b: p)炸裂が起こったなら(n、n-32)コードのための非検出された誤りの条件付き確率が与えられたコード、範囲32<b<nのすべてのbに関して同じコード(多項式を発生させる同じくらい)のための非検出された誤りの確率と等しいなら非検出された誤りの確率がブロック長bに短くされたのを計算するつもりです; これが短くされたとき、コードは2進対称チャネルと共にチャンネル(過疎の、そして、独立している)ビットエラー確率pで使用されます。
The approximation formula for Pud of sporadic errors, if the weights Ai are distributed binomially, is:
重りのAiが二項式に分配されるなら、過疎の誤りのPudのための近似公式は以下の通りです。
Pud(C, epsilon) =~= Sigma[for i=d to n] ((n choose i) / 2^r )*(1- epsilon)^(n-i) * epsilon^i .
プディング(C、ε)=~=σ[nへのi=dであることの](nはi)/2^rを選ぶ)*(1つのε)^(n-i)*ε^i。
Assuming a very small epsilon, this expression is dominated by i=d. From [Fujiwara89] we know that for 32-bit CRC, for such small n, d=15. Thus, when n grows from 33 to 34, we find that the approximation of Pud grows by (34 choose 15) / (33 choose 15) = 34/19; when n grows further to 35, Pud grows by another 35/20.
非常に小さいεを仮定して、この表現はi=dによって支配されます。 [Fujiwara89]から、私たちは32ビットのCRC、小さいn、そのようなd=15であるときにそれを知っています。 したがって、nが33〜34まで成長すると、私たちは、Pudの近似が(34は15を選びます)/(33は15を選びます)=34/19成長するのがわかりました。 nが35に加えて成長すると、Pudは別の35/20成長します。
Taking, from Wolf [Wolf94j], the most generous conditional
probability, computed with the bit error probability p* that
maximizes Pub(p|b), we derive: Pud(p*|33) = 4 x 10^{-10}, yielding
Pud(p*|34) = 7.15 x 10^{-10} and Pud(p*|35) = 1.25 x 10^{-9}.
ヴォルフ[Wolf94j]から*それがPub(p| b)を最大にするという噛み付いているエラー確率pで計算される中で最も豊富な条件付き確率を取って、私たちは以下を引き出します。 7.15x10^-10とPud(p*| 35)=1.25x10^Pud(p*| 34)=-9をもたらして、プディング(p*| 33)は4x10^-10と等しいです。
Sheinwald, et. al. Informational [Page 7] RFC 3385 iSCSI CRC Considerations September 2002
et Sheinwald、アル。 [7ページ]情報のRFC3385iSCSI CRC問題2002年9月
For the density function of the burst length, we assume the Rayleigh density function (the discretization thereof to integers), which is the density of the absolute values of complex numbers of Gauss distribution:
炸裂の長さの密度関数のために、私たちは、レイリーが密度関数(それの整数への離散化)であると思います:(密度関数はガウス分配の複素数の絶対値の密度です)。
f(x) = x / a^2 exp {-x^2 / 2a^2 } , x>0 .
f(x)がx/a^2expと等しい、-、x^2 / 2a^2、x>0
This density function has a peak at the parameter a and it decreases smoothly as x increases.
aはこの密度関数でパラメタでaに最大限にします、そして、xが増加するのに従って、それはスムーズに減少します。
We take three consecutive bits as the most common burst event once an error does occur, and thus a=3.
私たちは最も一般的な炸裂出来事、誤りがいったん発生するとおよびその結果、a=3として連続した3ビット取ります。
Now, the probability that a burst of length b occurs in a specific
position is the burst error rate, which we estimate as 10^{-10},
times f(b). Calculating for b=33 we find f(33) = 1.94 x 10^{-26}.
Together, we found that the probability that a burst of length 33
occurred, starting at a specific position, is 1.94 x 10^{-36}.
現在、長さbの炸裂が特定の位置に起こるという確率はバースト誤りレートです、回のf(b)。(私たちは10^-10としてそれを見積もっています)。 b=33を予測して、私たちは、1.94x10f(33)=^が-26であることがわかりました。 私たちは、特定の位置で始まって、長さ33の炸裂が起こったという確率が1.94x10^-36であることが一緒に、わかりました。
Multiplying this by the generous upper bound on the probability that
this burst error is not detected, Pud(p*|33), we get that the
probability that a burst occurred at a specific position, and is not
detected, is 7.79 x 10 ^{-46}.
このバースト誤りが検出されています、Pud(p*| 33)、私たちがそれを得るということでないという確率で寛大な上限にこれを掛けるのは、炸裂が特定の位置に起こって、検出されないで、7.79x10^-46がそうという確率です。
Going again along this path of calculations, this time for b=34 we
find that f(34) = 4.85*10^{-28}. Multiplying by 10^{-10} and by
Pud(p*|34) = 7.15*10^{-10} we find that the probability that a burst
of length 34 occurred at a specific position, and is not detected, is
3.46*10^{-47}.
再び計算のこの経路に沿って行って、今回、b=34に関して、私たちは、4.85*10そのf(34)=^が-28であることがわかりました。 10^-10とPud(p*| 34)を=7.15*10^-10に掛けて、私たちは、長さ34の炸裂が特定の位置に起こって、検出されないという確率が3.46*10^-47であることがわかりました。
Last, computing for b=35, we get 1*10^{-29} * 10^{-10} * 1.25*10^{-9}
= 1.25*10^{-48}.
最後に、b=35であるときに計算して、私たちは1*10^-29*10^-10*1.25*10^-9=1.25*10^-48を手に入れます。
It looks like the total can be approximated at 10^-45 which is within the bounds of what we are looking for.
私たちが探しているものに関する領域の中にある10^-45で合計に近似できるように見えます。
When we multiply this by the length of the code (because thus far we calculated for a specific position) we have 10^-45 * 6.5*10^4 = 6.5*10^-41 as an upper bound on the probability of undetected burst error for a code of length 8K Bytes.
コードの長さにこれを掛けるとき(私たちがこれまでのところ特定の位置を予測したので)、私たちは上限として長さの8KのBytesのコードのための非検出されたバースト誤りの確率に10^-45*6.5*10^4 = 6.5*10^-41を持っています。
We can also apply this overestimation for IEEE 802.3.
また、私たちはIEEE802.3のためにこの過大評価を適用できます。
Comment: 2^{-32} = 2.33*10^{-10}.
コメント: 2^{-32} = 2.33*10^{-10}.
Sheinwald, et. al. Informational [Page 8] RFC 3385 iSCSI CRC Considerations September 2002
et Sheinwald、アル。 [8ページ]情報のRFC3385iSCSI CRC問題2002年9月
5. Probability of Undetected Errors - Independent Errors
5. Undetected誤りの確率--独立している誤り
5.1 CRC (Derivations from [Castagnoli93])
5.1 CRC([Castagnoli93]からの派生)
It is reported in [Castagnoli93] that for BER = epsilon=10^-6, Pud
for a single bit error, for a code of length 8KB, for both cases,
IEEE-802.3 and CRC32C is 10^{-20}. They also report that CRC32C has
distance 4, and IEEE either 3 or 4 for this code length. From this,
and the minimum distance of the code of this length, we conclude that
with our estimation of epsilon, namely 10^{-11}, we should multiply
the reported result by {10^{-5}}^4 = 10^{-20} for CRC32C, and either
10^{-15} or 10^{-20} for IEEE802.3.
それはBER=εのために10^-6と等しい[Castagnoli93]で報告されます、ただ一つの噛み付いている誤りのためのPud、両方のための8KBの長さのケース、IEEE-802.3、およびCRC32Cのコードが10^-20であるので。 また、彼らは、CRC32Cには距離4、およびIEEE3か4がこのコードの長さのためにあると報告します。 これ、およびこの長さのコードの最小の遠方から、私たちは、すなわち、私たちのεに関する見積り、10^-11で、IEEE802.3のためのCRC32Cと、10^-15か10^-20のどちらかのために10^-5^4 = 10^-20に報告された結果を掛けるべきであると結論を下します。
5.2 Checksums
5.2 チェックサム
For independent bit errors, Pud of CRC is approximately 12,000 better than Fletcher, and 22,000 better than Adler. For burst errors, by the simple examples that exist for three consecutive values that can produce an undetected burst, we take the factor to be at least the same.
独立している噛み付いている誤りのために、CRCのPudはフレッチャーよりよく、そして、アドラーより2万2000よくおよそ1万2000です。 バースト誤りのために、3つの連続した値のために存在する簡単な例でそれは非検出された炸裂を発生させることができて、私たちは、少なくとも同じになるように要素を取ります。
If in three consecutive bytes, the error values are x, -2x, x then the error is undetected. Even for this error pattern alone, the conditional probability of undetected error, assuming a uniform distribution of data, is 2^-16 = 1.5 * 10^-5. The probability that a burst of length 3 bytes occurs, is f(24) = 3*10^-14. Together: 4.5*10^-19. Multiplying this by the length of the code, we get close to 4.5*10^-16, way worse than the vicinity of 10^-40.
連続した3バイトにおいて、誤り値がx、-2x、xであるなら、誤りは非検出されます。 この誤りパターンだけのためにさえ、データの一様分布を仮定して、非検出された誤りの条件付き確率は2^16 = 1.5*10^-5です。 3バイトの長さの炸裂が起こるという確率はf(24)=3*10^-14です。 一緒に: 4.5*10^-19. コードの長さにこれを掛けて、私たちは4.5*10^-16に近く、10^-40の付近よりずっと悪くなります。
The numbers in the table in Section 7 below reflect a more "tolerant" difference (10*4).
以下のセクション7におけるテーブルの数は、より「許容性がある」違い(10*4)を反映します。
6. Incremental CRC Updates
6. 増加のCRCアップデート
In some protocols the packet header changes frequently. If the CRC includes the changing part, the CRC will have to be recomputed. This raises two issues:
いくつかのプロトコルでは、パケットのヘッダーは頻繁に変化します。 CRCが変化部分を含んでいると、CRCは再計算されなければならないでしょう。 これは2冊を提起します:
- the complete computation is expensive
- the packet is not protected against unwanted changes
between the last check and the recomputation
- 完全な計算は高価です--パケットは最後のチェックと再計算の間の求められていない変化に対して保護されません。
Fortunately, changes in the header do not imply a need for completed CRC computation. The reason is the linearity of the CRC function. Namely, with I1 and I2 denoting two equal-length blocks of information bits, CRC(I) denoting the CRC check bits calculated for I, and + denoting bitwise modulo-2 addition, we have CRC(I1+I2) = CRC(I1)+CRC(I2).
幸い、ヘッダーにおける変化は完成したCRC計算の必要性を含意しません。 理由はCRC機能の直線形です。 すなわち、I1とI2が2情報ビット、予測されたCRCチェックビットを指示するCRC(I)の等しいレングス・ブロックの私、および+を指示している状態で、指示は法-2添加をbitwiseして、私たちはCRC(I1+I2)にCRC(I1)+CRC(I2)と等しくさせます。
Sheinwald, et. al. Informational [Page 9] RFC 3385 iSCSI CRC Considerations September 2002
et Sheinwald、アル。 [9ページ]情報のRFC3385iSCSI CRC問題2002年9月
Hence, for an IP packet, made of a header h followed by data d followed by CRC bits c = CRC(h d), arriving at a node, which updates header h to become h', the implied update of c is an addition of CRC(h'-h 0), where 0 is an all 0 block of the length of the data block d, and addition and subtraction are bitwise modulo 2.
'したがって、ヘッダーで作られたIPパケットに関して、ノードに到着して、CRCビットcが支えたデータd=CRC(h d)によって続かれたh(h'になるアップデートヘッダーh、cの暗示しているアップデートは0がすべて、データ・ブロックdの長さの0ブロックであるCRC(h'-h0)の添加であり、足し算と引き算は添加である)は法2をbitwiseします。
We know that a predetermined permutation of bits does not change distance and weight statistics of the codewords. It follows that such a transformation does not change the probability of undetected errors.
私たちは、ビットの予定された順列が距離を変えて、符号語の統計に重みを加えないのを知っています。 そのような変化が非検出された誤りの確率を変えないということになります。
We can then conceive the packet as if it was built from data d followed by header h, compute the CRC accordingly, c=CRC(d h), and update at the node with an addition of CRC(0 h'-h)=CRC(h'-h), but on transmission, send the header part before the data and the CRC bits. This will allow a faster computation of the CRC, while still letting the header part lead (no change to the protocol).
'次に、まるでそれがヘッダーhによって従われたデータdから建てられるかのように私たちはパケットを発想できますが、c=CRC(d h)、それに従って、CRCを計算してください、そして、ノードでのCRC('の0時間の-h)の添加によるアップデートはCRC(h'-h)と等しいのですが、トランスミッションのときに、データとCRCビットの前にヘッダー部分を送ってください。 ヘッダー部分に(プロトコルへの変化がありません)をまだ導かせている間、これはCRCの、より速い計算を許すでしょう。
Error detection, i.e., computing the CRC bits by the data and header parts that arrive, and comparing them with the CRC part that arrives together with them, can be done at the final, end-target node only, and the detected errors will include unwanted changes introduced by the intermediate nodes.
誤り検出、すなわち、データと到着するヘッダーの部品のそばでCRCビットを計算して、決勝でそれらと共に到着するCRC部分とそれらは比べることができます、終わり目標ノードだけ、そして、検出された誤りが中間的ノードによって導入された求められていない変化を含むでしょう。
The analysis of the undetected error probability remains valid according to the following rationale:
非検出されたエラー確率の分析は以下の原理によると、有効なままで残っています:
The packet started its way as a codeword. On its way, several codewords were added to it (any information followed by the corresponding CRC is a codeword). Let e denote the totality of errors added to the packet, on its long, multi-hop journey. Because the code is linear (i.e., the sum of two codewords is also a codeword) the packet arriving to the end-target node is some codeword + e, and hence, as in our preceding analysis, e is undetected if and only if it is a codeword by itself. This fact is the basis of our above analysis, and hence that analysis applies here too. (See a detailed discussion at [braun01].)
パケットは符号語を道に始めました。 途中では、いくつかの符号語がそれに加えられました(対応するCRCによって従われたどんな情報も符号語です)。 eに長いマルチホップ旅行のときにパケットに加えられた誤りの全体を指示させてください。 コードが直線的であるので(また、すなわち、2つの符号語の合計は符号語です)、終わり目標ノードに到着するパケットがいくつかの符号語+eであり、したがって、私たちが分析に先行するようにeが非検出される、それである場合にだけ、それ自体で符号語はそうです。 この事実は私たちの上の分析の基礎です、そして、したがって、また、その分析はここに適用されます。 ([braun01]で詳細な論議を見てください。)
7. Complexity of Hardware Implementation
7. ハードウェア実装の複雑さ
Comparing the cost of various CRC polynomials, we used a tool available at http://www.easics.com/webtools/crctool to implement CRC generators/checkers for various CRC polynomials. The program gives either Verilog or VHDL code after specifying a polynomial, as well as the number of data bits, k, to be handled in one clock cycle. For a serial implementation, k would be one.
様々なCRC多項式の費用を比較して、私たちは、様々なCRC多項式のためにCRCジェネレータ/市松模様を実行するのに http://www.easics.com/webtools/crctool で利用可能なツールを使用しました。 プログラムは、1クロック周期で扱われるために多項式を指定した後のコード、およびデータ・ビット、kの数をVerilogかVHDLのどちらかに与えます。 連続の実現のために、kはものでしょう。
Sheinwald, et. al. Informational [Page 10] RFC 3385 iSCSI CRC Considerations September 2002
et Sheinwald、アル。 [10ページ]情報のRFC3385iSCSI CRC問題2002年9月
The cost for either one generator or checker is shown in the following table.
1個のジェネレータか数奇のどちらかのための費用は以下のテーブルに示されます。
The number of 2-input XOR gates, for an un-optimized implementation, required for various values of k:
kの様々な値に必要である不-最適化された実現のための2入力しているXORゲートの数:
+----------------------------------------------+ | Polynomial | k=32 | k=64 | k=128 | +----------------------------------------------+ | CCITT-CRC32 | 488 | 740 | 1430 | +----------------------------------------------+ | IEEE-802 | 872 | 1390 | 2518 | +----------------------------------------------+ | CRC32Q(Wolf)| 944 | 1444 | 2534 | +----------------------------------------------+ | CRC32C | 1036 | 1470 | 2490 | +----------------------------------------------+
+----------------------------------------------+ | 多項式| k=32| k=64| k=128| +----------------------------------------------+ | CCITT-CRC32| 488 | 740 | 1430 | +----------------------------------------------+ | IEEE-802| 872 | 1390 | 2518 | +----------------------------------------------+ | CRC32Q(オオカミ)| 944 | 1444 | 2534 | +----------------------------------------------+ | CRC32C| 1036 | 1470 | 2490 | +----------------------------------------------+
After optimizing (sharing terms) and in terms of Cells (4 cells per 2 input AND, 7 cells per 2 input XOR, 3 cells per inverter) the cost for two candidate polynomials is shown in the following table.
最適化した(用語を共有します)後とCells(2入力ANDあたり4つのセル、2あたり7つのセルがXORを入力しました、1インバータあたり3つのセル)に関して、2つの候補多項式のための費用は以下のテーブルに示されます。
+-----------------------------------+ | Polynomial | k=32 | k=64 | +-----------------------------------+ | CCITT-CRC32 | 1855 | 3572 | +-----------------------------------+ | CRC32C | 4784 | 7111 | +-----------------------------------+
+-----------------------------------+ | 多項式| k=32| k=64| +-----------------------------------+ | CCITT-CRC32| 1855 | 3572 | +-----------------------------------+ | CRC32C| 4784 | 7111 | +-----------------------------------+
For 32-bit datapath, CCITT-CRC32 requires 40% of the number of cells required by the CRC32C. For a 64-bit datapath, CCITT-CRC32 requires 50% of the number of cells.
32ビットのdatapathに関しては、CCITT-CRC32はCRC32Cによって必要とされたセルの数の40%を必要とします。 64ビットのdatapathに関しては、CCITT-CRC32はセルの数の50%を必要とします。
The total size of one of our smaller chips is roughly 1 million cells. The fraction represented by the CRC circuit is less than 1%.
私たちの、より小さいチップの1つの総サイズはおよそ100万のセルです。 CRCサーキットによって表された断片は1%未満です。
8. Implementation of CRC32C
8. CRC32Cの実現
8.1 A Serial Implementation in Hardware
8.1 ハードウェアにおける連続の実現
A serial implementation that processes one data bit at a time and performs simultaneous multiplication of the data polynomial by x^32 and division by the CRC32C polynomial is described in the following Verilog [ieee1364] code.
CRC32C多項式で一度に、1データ・ビット処理して、x^32と分割でデータ多項式の同時の乗法を実行する連続の実現は以下のVerilog[ieee1364]コードで説明されます。
Sheinwald, et. al. Informational [Page 11] RFC 3385 iSCSI CRC Considerations September 2002
et Sheinwald、アル。 [11ページ]情報のRFC3385iSCSI CRC問題2002年9月
///////////////////////////////////////////////////////////////////// //File: CRC32_D1.v //Date: Tue Feb 26 02:47:05 2002 // //Copyright (C) 1999 Easics NV. //This source file may be used and distributed without restriction //provided that this copyright statement is not removed from the file //and that any derivative work contains the original copyright notice //and the associated disclaimer. // //THIS SOURCE FILE IS PROVIDED "AS IS" AND WITHOUT ANY EXPRESS //OR IMPLIED WARRANTIES, INCLUDING, WITHOUT LIMITATION, THE IMPLIED //WARRANTIES OF MERCHANTIBILITY AND FITNESS FOR A PARTICULAR PURPOSE. // //Purpose: Verilog module containing a synthesizable CRC function //* polynomial: (0 1 2 4 5 7 8 10 11 12 16 22 23 26 32) //* data width: 1 // //Info: jand@easics.be (Jan Decaluwe) //http://www.easics.com ///////////////////////////////////////////////////////////////////// module CRC32_D1; // polynomial: (0 1 2 4 5 7 8 10 11 12 16 22 23 26 32) // data width: 1 function [31:0] nextCRC32_D1; input Data; input [31:0] CRC; reg [0:0] D; reg [31:0] C; reg [31:0] NewCRC; begin D[0] = Data; C = CRC; NewCRC[0] = D[0] ^ C[31]; NewCRC[1] = D[0] ^ C[0] ^ C[31]; NewCRC[2] = D[0] ^ C[1] ^ C[31]; NewCRC[3] = C[2]; NewCRC[4] = D[0] ^ C[3] ^ C[31]; NewCRC[5] = D[0] ^ C[4] ^ C[31]; NewCRC[6] = C[5]; NewCRC[7] = D[0] ^ C[6] ^ C[31]; NewCRC[8] = D[0] ^ C[7] ^ C[31]; NewCRC[9] = C[8]; NewCRC[10] = D[0] ^ C[9] ^ C[31]; NewCRC[11] = D[0] ^ C[10] ^ C[31]; NewCRC[12] = D[0] ^ C[11] ^ C[31]; NewCRC[13] = C[12]; NewCRC[14] = C[13];
ファイル CRC32_D1.v//日付: 2002年2月26日火曜日2時47分5秒////著作権(C)1999Easicsネバダ。 この著作権宣言文がファイル//から取り除かれなければ、このソースがファイルする//は、制限//なしで使用されて、分配されるかもしれません、そして、どんな派生物も働いているのがオリジナル版権情報//と関連注意書きを含んでいます。 このソースファイルが制限なしでMERCHANTIBILITYと特定目的への適合性の暗示している//保証を含む少しも「そのままで」と黙示的な保証急行//、または、なしで提供される////。 ////目的: synthesizable CRC機能//*多項式を含むVerilogモジュール: (0 1 2 4 5 7 8 10 11 12 16 22 23 26 32) //*データ幅: 1////インフォメーション: モジュール //多項式: (0 1 2 4 5 7 8 10 11 12 16 22 23 26 32) //データ幅: 1 機能[31:0]nextCRC32_D1。 Dataを入力してください。 [31:0]CRCを入力してください。 reg[0:0]D。 reg[31:0]C。 reg[31:0]NewCRC。 D[0]=データを始めてください。 CはCRCと等しいです。 NewCRC[0]はD[0]^C[31]と等しいです。 NewCRC[1]はD[0]^C[0]^C[31]と等しいです。 NewCRC[2]はD[0]^C[1]^C[31]と等しいです。 NewCRC[3]はC[2]と等しいです。 NewCRC[4]はD[0]^C[3]^C[31]と等しいです。 NewCRC[5]はD[0]^C[4]^C[31]と等しいです。 NewCRC[6]はC[5]と等しいです。 NewCRC[7]はD[0]^C[6]^C[31]と等しいです。 NewCRC[8]はD[0]^C[7]^C[31]と等しいです。 NewCRC[9]はC[8]と等しいです。 NewCRC[10]はD[0]^C[9]^C[31]と等しいです。 NewCRC[11]はD[0]^C[10]^C[31]と等しいです。 NewCRC[12]はD[0]^C[11]^C[31]と等しいです。 NewCRC[13]はC[12]と等しいです。 NewCRC[14]はC[13]と等しいです。
Sheinwald, et. al. Informational [Page 12] RFC 3385 iSCSI CRC Considerations September 2002
et Sheinwald、アル。 [12ページ]情報のRFC3385iSCSI CRC問題2002年9月
NewCRC[15] = C[14]; NewCRC[16] = D[0] ^ C[15] ^ C[31]; NewCRC[17] = C[16]; NewCRC[18] = C[17]; NewCRC[19] = C[18]; NewCRC[20] = C[19]; NewCRC[21] = C[20]; NewCRC[22] = D[0] ^ C[21] ^ C[31]; NewCRC[23] = D[0] ^ C[22] ^ C[31]; NewCRC[24] = C[23]; NewCRC[25] = C[24]; NewCRC[26] = D[0] ^ C[25] ^ C[31]; NewCRC[27] = C[26]; NewCRC[28] = C[27]; NewCRC[29] = C[28]; NewCRC[30] = C[29]; NewCRC[31] = C[30]; nextCRC32_D1 = NewCRC; end endfunction endmodule
NewCRC[15]はC[14]と等しいです。 NewCRC[16]はD[0]^C[15]^C[31]と等しいです。 NewCRC[17]はC[16]と等しいです。 NewCRC[18]はC[17]と等しいです。 NewCRC[19]はC[18]と等しいです。 NewCRC[20]はC[19]と等しいです。 NewCRC[21]はC[20]と等しいです。 NewCRC[22]はD[0]^C[21]^C[31]と等しいです。 NewCRC[23]はD[0]^C[22]^C[31]と等しいです。 NewCRC[24]はC[23]と等しいです。 NewCRC[25]はC[24]と等しいです。 NewCRC[26]はD[0]^C[25]^C[31]と等しいです。 NewCRC[27]はC[26]と等しいです。 NewCRC[28]はC[27]と等しいです。 NewCRC[29]はC[28]と等しいです。 NewCRC[30]はC[29]と等しいです。 NewCRC[31]はC[30]と等しいです。 nextCRC32_D1はNewCRCと等しいです。 終わりのendfunction endmodule
8.2 A Parallel Implementation in Hardware
8.2 ハードウェアにおける平行な実現
A parallel implementation that processes 32 data bits at a time is described in the following Verilog [ieee1364] code. In software implementations, the next state logic is typically implemented by means of tables indexed by the input and the current state.
一度に32データ・ビット処理される平行な実現は以下のVerilog[ieee1364]コードで説明されます。 ソフトウェア実行では、入力と現状までに索引をつけられたテーブルによって次の州の論理は通常実行されます。
///////////////////////////////////////////////////////////////////// //File: CRC32_D32.v //Date: Tue Feb 26 02:50:08 2002 // //Copyright (C) 1999 Easics NV. //This source file may be used and distributed without restriction //provided that this copyright statement is not removed from the file //and that any derivative work contains the original copyright notice //and the associated disclaimer. // //THIS SOURCE FILE IS PROVIDED "AS IS" AND WITHOUT ANY EXPRESS //OR IMPLIED WARRANTIES, INCLUDING, WITHOUT LIMITATION, THE IMPLIED //WARRANTIES OF MERCHANTIBILITY AND FITNESS FOR A PARTICULAR PURPOSE. // //Purpose: Verilog module containing a synthesizable CRC function //* polynomial: p(0 to 32) := "100000101111011000111011011110001" //* data width: 32 // //Info: jand@easics.be (Jan Decaluwe)
///////////////////////////////////////////////////////////////////// //File: CRC32_D32.v //Date: Tue Feb 26 02:50:08 2002 // //Copyright (C) 1999 Easics NV. //This source file may be used and distributed without restriction //provided that this copyright statement is not removed from the file //and that any derivative work contains the original copyright notice //and the associated disclaimer. // //THIS SOURCE FILE IS PROVIDED "AS IS" AND WITHOUT ANY EXPRESS //OR IMPLIED WARRANTIES, INCLUDING, WITHOUT LIMITATION, THE IMPLIED //WARRANTIES OF MERCHANTIBILITY AND FITNESS FOR A PARTICULAR PURPOSE. // //Purpose: Verilog module containing a synthesizable CRC function //* polynomial: p(0 to 32) := "100000101111011000111011011110001" //* data width: 32 // //Info: jand@easics.be (Jan Decaluwe)
Sheinwald, et. al. Informational [Page 13] RFC 3385 iSCSI CRC Considerations September 2002
Sheinwald, et. al. Informational [Page 13] RFC 3385 iSCSI CRC Considerations September 2002
//http://www.easics.com ///////////////////////////////////////////////////////////////////// module CRC32_D32; // polynomial: p(0 to 32) := "100000101111011000111011011110001" // data width: 32 // convention: the first serial data bit is D[31] function [31:0] nextCRC32_D32; input [31:0] Data; input [31:0] CRC; reg [31:0] D; reg [31:0] C; reg [31:0] NewCRC; begin D = Data; C = CRC; NewCRC[0] = D[31] ^ D[30] ^ D[28] ^ D[27] ^ D[26] ^ D[25] ^ D[23] ^ D[21] ^ D[18] ^ D[17] ^ D[16] ^ D[12] ^ D[9] ^ D[8] ^ D[7] ^ D[6] ^ D[5] ^ D[4] ^ D[0] ^ C[0] ^ C[4] ^ C[5] ^ C[6] ^ C[7] ^ C[8] ^ C[9] ^ C[12] ^ C[16] ^ C[17] ^ C[18] ^ C[21] ^ C[23] ^ C[25] ^ C[26] ^ C[27] ^ C[28] ^ C[30] ^ C[31]; NewCRC[1] = D[31] ^ D[29] ^ D[28] ^ D[27] ^ D[26] ^ D[24] ^ D[22] ^ D[19] ^ D[18] ^ D[17] ^ D[13] ^ D[10] ^ D[9] ^ D[8] ^ D[7] ^ D[6] ^ D[5] ^ D[1] ^ C[1] ^ C[5] ^ C[6] ^ C[7] ^ C[8] ^ C[9] ^ C[10] ^ C[13] ^ C[17] ^ C[18] ^ C[19] ^ C[22] ^ C[24] ^ C[26] ^ C[27] ^ C[28] ^ C[29] ^ C[31]; NewCRC[2] = D[30] ^ D[29] ^ D[28] ^ D[27] ^ D[25] ^ D[23] ^ D[20] ^ D[19] ^ D[18] ^ D[14] ^ D[11] ^ D[10] ^ D[9] ^ D[8] ^ D[7] ^ D[6] ^ D[2] ^ C[2] ^ C[6] ^ C[7] ^ C[8] ^ C[9] ^ C[10] ^ C[11] ^ C[14] ^ C[18] ^ C[19] ^ C[20] ^ C[23] ^ C[25] ^ C[27] ^ C[28] ^ C[29] ^ C[30]; NewCRC[3] = D[31] ^ D[30] ^ D[29] ^ D[28] ^ D[26] ^ D[24] ^ D[21] ^ D[20] ^ D[19] ^ D[15] ^ D[12] ^ D[11] ^ D[10] ^ D[9] ^ D[8] ^ D[7] ^ D[3] ^ C[3] ^ C[7] ^ C[8] ^ C[9] ^ C[10] ^ C[11] ^ C[12] ^ C[15] ^ C[19] ^ C[20] ^ C[21] ^ C[24] ^ C[26] ^ C[28] ^ C[29] ^ C[30] ^ C[31]; NewCRC[4] = D[31] ^ D[30] ^ D[29] ^ D[27] ^ D[25] ^ D[22] ^ D[21] ^ D[20] ^ D[16] ^ D[13] ^ D[12] ^ D[11] ^ D[10] ^ D[9] ^ D[8] ^ D[4] ^ C[4] ^ C[8] ^ C[9] ^ C[10] ^ C[11] ^ C[12] ^ C[13] ^ C[16] ^ C[20] ^ C[21] ^ C[22] ^ C[25] ^ C[27] ^ C[29] ^ C[30] ^ C[31]; NewCRC[5] = D[31] ^ D[30] ^ D[28] ^ D[26] ^ D[23] ^ D[22] ^ D[21] ^
//http://www.easics.com ///////////////////////////////////////////////////////////////////// module CRC32_D32; // polynomial: p(0 to 32) := "100000101111011000111011011110001" // data width: 32 // convention: the first serial data bit is D[31] function [31:0] nextCRC32_D32; input [31:0] Data; input [31:0] CRC; reg [31:0] D; reg [31:0] C; reg [31:0] NewCRC; begin D = Data; C = CRC; NewCRC[0] = D[31] ^ D[30] ^ D[28] ^ D[27] ^ D[26] ^ D[25] ^ D[23] ^ D[21] ^ D[18] ^ D[17] ^ D[16] ^ D[12] ^ D[9] ^ D[8] ^ D[7] ^ D[6] ^ D[5] ^ D[4] ^ D[0] ^ C[0] ^ C[4] ^ C[5] ^ C[6] ^ C[7] ^ C[8] ^ C[9] ^ C[12] ^ C[16] ^ C[17] ^ C[18] ^ C[21] ^ C[23] ^ C[25] ^ C[26] ^ C[27] ^ C[28] ^ C[30] ^ C[31]; NewCRC[1] = D[31] ^ D[29] ^ D[28] ^ D[27] ^ D[26] ^ D[24] ^ D[22] ^ D[19] ^ D[18] ^ D[17] ^ D[13] ^ D[10] ^ D[9] ^ D[8] ^ D[7] ^ D[6] ^ D[5] ^ D[1] ^ C[1] ^ C[5] ^ C[6] ^ C[7] ^ C[8] ^ C[9] ^ C[10] ^ C[13] ^ C[17] ^ C[18] ^ C[19] ^ C[22] ^ C[24] ^ C[26] ^ C[27] ^ C[28] ^ C[29] ^ C[31]; NewCRC[2] = D[30] ^ D[29] ^ D[28] ^ D[27] ^ D[25] ^ D[23] ^ D[20] ^ D[19] ^ D[18] ^ D[14] ^ D[11] ^ D[10] ^ D[9] ^ D[8] ^ D[7] ^ D[6] ^ D[2] ^ C[2] ^ C[6] ^ C[7] ^ C[8] ^ C[9] ^ C[10] ^ C[11] ^ C[14] ^ C[18] ^ C[19] ^ C[20] ^ C[23] ^ C[25] ^ C[27] ^ C[28] ^ C[29] ^ C[30]; NewCRC[3] = D[31] ^ D[30] ^ D[29] ^ D[28] ^ D[26] ^ D[24] ^ D[21] ^ D[20] ^ D[19] ^ D[15] ^ D[12] ^ D[11] ^ D[10] ^ D[9] ^ D[8] ^ D[7] ^ D[3] ^ C[3] ^ C[7] ^ C[8] ^ C[9] ^ C[10] ^ C[11] ^ C[12] ^ C[15] ^ C[19] ^ C[20] ^ C[21] ^ C[24] ^ C[26] ^ C[28] ^ C[29] ^ C[30] ^ C[31]; NewCRC[4] = D[31] ^ D[30] ^ D[29] ^ D[27] ^ D[25] ^ D[22] ^ D[21] ^ D[20] ^ D[16] ^ D[13] ^ D[12] ^ D[11] ^ D[10] ^ D[9] ^ D[8] ^ D[4] ^ C[4] ^ C[8] ^ C[9] ^ C[10] ^ C[11] ^ C[12] ^ C[13] ^ C[16] ^ C[20] ^ C[21] ^ C[22] ^ C[25] ^ C[27] ^ C[29] ^ C[30] ^ C[31]; NewCRC[5] = D[31] ^ D[30] ^ D[28] ^ D[26] ^ D[23] ^ D[22] ^ D[21] ^
Sheinwald, et. al. Informational [Page 14] RFC 3385 iSCSI CRC Considerations September 2002
Sheinwald, et. al. Informational [Page 14] RFC 3385 iSCSI CRC Considerations September 2002
D[17] ^ D[14] ^ D[13] ^ D[12] ^ D[11] ^ D[10] ^ D[9] ^ D[5] ^ C[5] ^ C[9] ^ C[10] ^ C[11] ^ C[12] ^ C[13] ^ C[14] ^ C[17] ^ C[21] ^ C[22] ^ C[23] ^ C[26] ^ C[28] ^ C[30] ^ C[31]; NewCRC[6] = D[30] ^ D[29] ^ D[28] ^ D[26] ^ D[25] ^ D[24] ^ D[22] ^ D[21] ^ D[17] ^ D[16] ^ D[15] ^ D[14] ^ D[13] ^ D[11] ^ D[10] ^ D[9] ^ D[8] ^ D[7] ^ D[5] ^ D[4] ^ D[0] ^ C[0] ^ C[4] ^ C[5] ^ C[7] ^ C[8] ^ C[9] ^ C[10] ^ C[11] ^ C[13] ^ C[14] ^ C[15] ^ C[16] ^ C[17] ^ C[21] ^ C[22] ^ C[24] ^ C[25] ^ C[26] ^ C[28] ^ C[29] ^ C[30]; NewCRC[7] = D[31] ^ D[30] ^ D[29] ^ D[27] ^ D[26] ^ D[25] ^ D[23] ^ D[22] ^ D[18] ^ D[17] ^ D[16] ^ D[15] ^ D[14] ^ D[12] ^ D[11] ^ D[10] ^ D[9] ^ D[8] ^ D[6] ^ D[5] ^ D[1] ^ C[1] ^ C[5] ^ C[6] ^ C[8] ^ C[9] ^ C[10] ^ C[11] ^ C[12] ^ C[14] ^ C[15] ^ C[16] ^ C[17] ^ C[18] ^ C[22] ^ C[23] ^ C[25] ^ C[26] ^ C[27] ^ C[29] ^ C[30] ^ C[31]; NewCRC[8] = D[25] ^ D[24] ^ D[21] ^ D[19] ^ D[15] ^ D[13] ^ D[11] ^ D[10] ^ D[8] ^ D[5] ^ D[4] ^ D[2] ^ D[0] ^ C[0] ^ C[2] ^ C[4] ^ C[5] ^ C[8] ^ C[10] ^ C[11] ^ C[13] ^ C[15] ^ C[19] ^ C[21] ^ C[24] ^ C[25]; NewCRC[9] = D[31] ^ D[30] ^ D[28] ^ D[27] ^ D[23] ^ D[22] ^ D[21] ^ D[20] ^ D[18] ^ D[17] ^ D[14] ^ D[11] ^ D[8] ^ D[7] ^ D[4] ^ D[3] ^ D[1] ^ D[0] ^ C[0] ^ C[1] ^ C[3] ^ C[4] ^ C[7] ^ C[8] ^ C[11] ^ C[14] ^ C[17] ^ C[18] ^ C[20] ^ C[21] ^ C[22] ^ C[23] ^ C[27] ^ C[28] ^ C[30] ^ C[31]; NewCRC[10] = D[30] ^ D[29] ^ D[27] ^ D[26] ^ D[25] ^ D[24] ^ D[22] ^ D[19] ^ D[17] ^ D[16] ^ D[15] ^ D[7] ^ D[6] ^ D[2] ^ D[1] ^ D[0] ^ C[0] ^ C[1] ^ C[2] ^ C[6] ^ C[7] ^ C[15] ^ C[16] ^ C[17] ^ C[19] ^ C[22] ^ C[24] ^ C[25] ^ C[26] ^ C[27] ^ C[29] ^ C[30]; NewCRC[11] = D[21] ^ D[20] ^ D[12] ^ D[9] ^ D[6] ^ D[5] ^ D[4] ^ D[3] ^ D[2] ^ D[1] ^ D[0] ^ C[0] ^ C[1] ^ C[2] ^ C[3] ^ C[4] ^ C[5] ^ C[6] ^ C[9] ^ C[12] ^ C[20] ^ C[21]; NewCRC[12] = D[22] ^ D[21] ^ D[13] ^ D[10] ^ D[7] ^ D[6] ^ D[5] ^ D[4] ^ D[3] ^ D[2] ^ D[1] ^ C[1] ^ C[2] ^ C[3] ^ C[4] ^ C[5] ^ C[6] ^ C[7] ^ C[10] ^ C[13] ^ C[21] ^ C[22]; NewCRC[13] = D[31] ^ D[30] ^ D[28] ^ D[27] ^ D[26] ^ D[25] ^ D[22] ^ D[21] ^ D[18] ^ D[17] ^ D[16] ^ D[14] ^ D[12] ^ D[11] ^ D[9] ^ D[3] ^ D[2] ^ D[0] ^ C[0] ^ C[2] ^ C[3] ^ C[9] ^ C[11] ^ C[12] ^ C[14] ^ C[16] ^ C[17] ^ C[18] ^ C[21] ^ C[22] ^ C[25] ^ C[26] ^ C[27] ^ C[28] ^ C[30] ^ C[31]; NewCRC[14] = D[30] ^ D[29] ^ D[25] ^ D[22] ^ D[21] ^ D[19] ^
D[17] ^ D[14] ^ D[13] ^ D[12] ^ D[11] ^ D[10] ^ D[9] ^ D[5] ^ C[5] ^ C[9] ^ C[10] ^ C[11] ^ C[12] ^ C[13] ^ C[14] ^ C[17] ^ C[21] ^ C[22] ^ C[23] ^ C[26] ^ C[28] ^ C[30] ^ C[31]; NewCRC[6] = D[30] ^ D[29] ^ D[28] ^ D[26] ^ D[25] ^ D[24] ^ D[22] ^ D[21] ^ D[17] ^ D[16] ^ D[15] ^ D[14] ^ D[13] ^ D[11] ^ D[10] ^ D[9] ^ D[8] ^ D[7] ^ D[5] ^ D[4] ^ D[0] ^ C[0] ^ C[4] ^ C[5] ^ C[7] ^ C[8] ^ C[9] ^ C[10] ^ C[11] ^ C[13] ^ C[14] ^ C[15] ^ C[16] ^ C[17] ^ C[21] ^ C[22] ^ C[24] ^ C[25] ^ C[26] ^ C[28] ^ C[29] ^ C[30]; NewCRC[7] = D[31] ^ D[30] ^ D[29] ^ D[27] ^ D[26] ^ D[25] ^ D[23] ^ D[22] ^ D[18] ^ D[17] ^ D[16] ^ D[15] ^ D[14] ^ D[12] ^ D[11] ^ D[10] ^ D[9] ^ D[8] ^ D[6] ^ D[5] ^ D[1] ^ C[1] ^ C[5] ^ C[6] ^ C[8] ^ C[9] ^ C[10] ^ C[11] ^ C[12] ^ C[14] ^ C[15] ^ C[16] ^ C[17] ^ C[18] ^ C[22] ^ C[23] ^ C[25] ^ C[26] ^ C[27] ^ C[29] ^ C[30] ^ C[31]; NewCRC[8] = D[25] ^ D[24] ^ D[21] ^ D[19] ^ D[15] ^ D[13] ^ D[11] ^ D[10] ^ D[8] ^ D[5] ^ D[4] ^ D[2] ^ D[0] ^ C[0] ^ C[2] ^ C[4] ^ C[5] ^ C[8] ^ C[10] ^ C[11] ^ C[13] ^ C[15] ^ C[19] ^ C[21] ^ C[24] ^ C[25]; NewCRC[9] = D[31] ^ D[30] ^ D[28] ^ D[27] ^ D[23] ^ D[22] ^ D[21] ^ D[20] ^ D[18] ^ D[17] ^ D[14] ^ D[11] ^ D[8] ^ D[7] ^ D[4] ^ D[3] ^ D[1] ^ D[0] ^ C[0] ^ C[1] ^ C[3] ^ C[4] ^ C[7] ^ C[8] ^ C[11] ^ C[14] ^ C[17] ^ C[18] ^ C[20] ^ C[21] ^ C[22] ^ C[23] ^ C[27] ^ C[28] ^ C[30] ^ C[31]; NewCRC[10] = D[30] ^ D[29] ^ D[27] ^ D[26] ^ D[25] ^ D[24] ^ D[22] ^ D[19] ^ D[17] ^ D[16] ^ D[15] ^ D[7] ^ D[6] ^ D[2] ^ D[1] ^ D[0] ^ C[0] ^ C[1] ^ C[2] ^ C[6] ^ C[7] ^ C[15] ^ C[16] ^ C[17] ^ C[19] ^ C[22] ^ C[24] ^ C[25] ^ C[26] ^ C[27] ^ C[29] ^ C[30]; NewCRC[11] = D[21] ^ D[20] ^ D[12] ^ D[9] ^ D[6] ^ D[5] ^ D[4] ^ D[3] ^ D[2] ^ D[1] ^ D[0] ^ C[0] ^ C[1] ^ C[2] ^ C[3] ^ C[4] ^ C[5] ^ C[6] ^ C[9] ^ C[12] ^ C[20] ^ C[21]; NewCRC[12] = D[22] ^ D[21] ^ D[13] ^ D[10] ^ D[7] ^ D[6] ^ D[5] ^ D[4] ^ D[3] ^ D[2] ^ D[1] ^ C[1] ^ C[2] ^ C[3] ^ C[4] ^ C[5] ^ C[6] ^ C[7] ^ C[10] ^ C[13] ^ C[21] ^ C[22]; NewCRC[13] = D[31] ^ D[30] ^ D[28] ^ D[27] ^ D[26] ^ D[25] ^ D[22] ^ D[21] ^ D[18] ^ D[17] ^ D[16] ^ D[14] ^ D[12] ^ D[11] ^ D[9] ^ D[3] ^ D[2] ^ D[0] ^ C[0] ^ C[2] ^ C[3] ^ C[9] ^ C[11] ^ C[12] ^ C[14] ^ C[16] ^ C[17] ^ C[18] ^ C[21] ^ C[22] ^ C[25] ^ C[26] ^ C[27] ^ C[28] ^ C[30] ^ C[31]; NewCRC[14] = D[30] ^ D[29] ^ D[25] ^ D[22] ^ D[21] ^ D[19] ^
Sheinwald, et. al. Informational [Page 15] RFC 3385 iSCSI CRC Considerations September 2002
Sheinwald, et. al. Informational [Page 15] RFC 3385 iSCSI CRC Considerations September 2002
D[16] ^ D[15] ^ D[13] ^ D[10] ^ D[9] ^ D[8] ^ D[7] ^ D[6] ^ D[5] ^ D[3] ^ D[1] ^ D[0] ^ C[0] ^ C[1] ^ C[3] ^ C[5] ^ C[6] ^ C[7] ^ C[8] ^ C[9] ^ C[10] ^ C[13] ^ C[15] ^ C[16] ^ C[19] ^ C[21] ^ C[22] ^ C[25] ^ C[29] ^ C[30]; NewCRC[15] = D[31] ^ D[30] ^ D[26] ^ D[23] ^ D[22] ^ D[20] ^ D[17] ^ D[16] ^ D[14] ^ D[11] ^ D[10] ^ D[9] ^ D[8] ^ D[7] ^ D[6] ^ D[4] ^ D[2] ^ D[1] ^ C[1] ^ C[2] ^ C[4] ^ C[6] ^ C[7] ^ C[8] ^ C[9] ^ C[10] ^ C[11] ^ C[14] ^ C[16] ^ C[17] ^ C[20] ^ C[22] ^ C[23] ^ C[26] ^ C[30] ^ C[31]; NewCRC[16] = D[31] ^ D[27] ^ D[24] ^ D[23] ^ D[21] ^ D[18] ^ D[17] ^ D[15] ^ D[12] ^ D[11] ^ D[10] ^ D[9] ^ D[8] ^ D[7] ^ D[5] ^ D[3] ^ D[2] ^ C[2] ^ C[3] ^ C[5] ^ C[7] ^ C[8] ^ C[9] ^ C[10] ^ C[11] ^ C[12] ^ C[15] ^ C[17] ^ C[18] ^ C[21] ^ C[23] ^ C[24] ^ C[27] ^ C[31]; NewCRC[17] = D[28] ^ D[25] ^ D[24] ^ D[22] ^ D[19] ^ D[18] ^ D[16] ^ D[13] ^ D[12] ^ D[11] ^ D[10] ^ D[9] ^ D[8] ^ D[6] ^ D[4] ^ D[3] ^ C[3] ^ C[4] ^ C[6] ^ C[8] ^ C[9] ^ C[10] ^ C[11] ^ C[12] ^ C[13] ^ C[16] ^ C[18] ^ C[19] ^ C[22] ^ C[24] ^ C[25] ^ C[28]; NewCRC[18] = D[31] ^ D[30] ^ D[29] ^ D[28] ^ D[27] ^ D[21] ^ D[20] ^ D[19] ^ D[18] ^ D[16] ^ D[14] ^ D[13] ^ D[11] ^ D[10] ^ D[8] ^ D[6] ^ D[0] ^ C[0] ^ C[6] ^ C[8] ^ C[10] ^ C[11] ^ C[13] ^ C[14] ^ C[16] ^ C[18] ^ C[19] ^ C[20] ^ C[21] ^ C[27] ^ C[28] ^ C[29] ^ C[30] ^ C[31]; NewCRC[19] = D[29] ^ D[27] ^ D[26] ^ D[25] ^ D[23] ^ D[22] ^ D[20] ^ D[19] ^ D[18] ^ D[16] ^ D[15] ^ D[14] ^ D[11] ^ D[8] ^ D[6] ^ D[5] ^ D[4] ^ D[1] ^ D[0] ^ C[0] ^ C[1] ^ C[4] ^ C[5] ^ C[6] ^ C[8] ^ C[11] ^ C[14] ^ C[15] ^ C[16] ^ C[18] ^ C[19] ^ C[20] ^ C[22] ^ C[23] ^ C[25] ^ C[26] ^ C[27] ^ C[29]; NewCRC[20] = D[31] ^ D[25] ^ D[24] ^ D[20] ^ D[19] ^ D[18] ^ D[15] ^ D[8] ^ D[4] ^ D[2] ^ D[1] ^ D[0] ^ C[0] ^ C[1] ^ C[2] ^ C[4] ^ C[8] ^ C[15] ^ C[18] ^ C[19] ^ C[20] ^ C[24] ^ C[25] ^ C[31]; NewCRC[21] = D[26] ^ D[25] ^ D[21] ^ D[20] ^ D[19] ^ D[16] ^ D[9] ^ D[5] ^ D[3] ^ D[2] ^ D[1] ^ C[1] ^ C[2] ^ C[3] ^ C[5] ^ C[9] ^ C[16] ^ C[19] ^ C[20] ^ C[21] ^ C[25] ^ C[26]; NewCRC[22] = D[31] ^ D[30] ^ D[28] ^ D[25] ^ D[23] ^ D[22] ^ D[20] ^ D[18] ^ D[16] ^ D[12] ^ D[10] ^ D[9] ^ D[8] ^ D[7] ^
D[16] ^ D[15] ^ D[13] ^ D[10] ^ D[9] ^ D[8] ^ D[7] ^ D[6] ^ D[5] ^ D[3] ^ D[1] ^ D[0] ^ C[0] ^ C[1] ^ C[3] ^ C[5] ^ C[6] ^ C[7] ^ C[8] ^ C[9] ^ C[10] ^ C[13] ^ C[15] ^ C[16] ^ C[19] ^ C[21] ^ C[22] ^ C[25] ^ C[29] ^ C[30]; NewCRC[15] = D[31] ^ D[30] ^ D[26] ^ D[23] ^ D[22] ^ D[20] ^ D[17] ^ D[16] ^ D[14] ^ D[11] ^ D[10] ^ D[9] ^ D[8] ^ D[7] ^ D[6] ^ D[4] ^ D[2] ^ D[1] ^ C[1] ^ C[2] ^ C[4] ^ C[6] ^ C[7] ^ C[8] ^ C[9] ^ C[10] ^ C[11] ^ C[14] ^ C[16] ^ C[17] ^ C[20] ^ C[22] ^ C[23] ^ C[26] ^ C[30] ^ C[31]; NewCRC[16] = D[31] ^ D[27] ^ D[24] ^ D[23] ^ D[21] ^ D[18] ^ D[17] ^ D[15] ^ D[12] ^ D[11] ^ D[10] ^ D[9] ^ D[8] ^ D[7] ^ D[5] ^ D[3] ^ D[2] ^ C[2] ^ C[3] ^ C[5] ^ C[7] ^ C[8] ^ C[9] ^ C[10] ^ C[11] ^ C[12] ^ C[15] ^ C[17] ^ C[18] ^ C[21] ^ C[23] ^ C[24] ^ C[27] ^ C[31]; NewCRC[17] = D[28] ^ D[25] ^ D[24] ^ D[22] ^ D[19] ^ D[18] ^ D[16] ^ D[13] ^ D[12] ^ D[11] ^ D[10] ^ D[9] ^ D[8] ^ D[6] ^ D[4] ^ D[3] ^ C[3] ^ C[4] ^ C[6] ^ C[8] ^ C[9] ^ C[10] ^ C[11] ^ C[12] ^ C[13] ^ C[16] ^ C[18] ^ C[19] ^ C[22] ^ C[24] ^ C[25] ^ C[28]; NewCRC[18] = D[31] ^ D[30] ^ D[29] ^ D[28] ^ D[27] ^ D[21] ^ D[20] ^ D[19] ^ D[18] ^ D[16] ^ D[14] ^ D[13] ^ D[11] ^ D[10] ^ D[8] ^ D[6] ^ D[0] ^ C[0] ^ C[6] ^ C[8] ^ C[10] ^ C[11] ^ C[13] ^ C[14] ^ C[16] ^ C[18] ^ C[19] ^ C[20] ^ C[21] ^ C[27] ^ C[28] ^ C[29] ^ C[30] ^ C[31]; NewCRC[19] = D[29] ^ D[27] ^ D[26] ^ D[25] ^ D[23] ^ D[22] ^ D[20] ^ D[19] ^ D[18] ^ D[16] ^ D[15] ^ D[14] ^ D[11] ^ D[8] ^ D[6] ^ D[5] ^ D[4] ^ D[1] ^ D[0] ^ C[0] ^ C[1] ^ C[4] ^ C[5] ^ C[6] ^ C[8] ^ C[11] ^ C[14] ^ C[15] ^ C[16] ^ C[18] ^ C[19] ^ C[20] ^ C[22] ^ C[23] ^ C[25] ^ C[26] ^ C[27] ^ C[29]; NewCRC[20] = D[31] ^ D[25] ^ D[24] ^ D[20] ^ D[19] ^ D[18] ^ D[15] ^ D[8] ^ D[4] ^ D[2] ^ D[1] ^ D[0] ^ C[0] ^ C[1] ^ C[2] ^ C[4] ^ C[8] ^ C[15] ^ C[18] ^ C[19] ^ C[20] ^ C[24] ^ C[25] ^ C[31]; NewCRC[21] = D[26] ^ D[25] ^ D[21] ^ D[20] ^ D[19] ^ D[16] ^ D[9] ^ D[5] ^ D[3] ^ D[2] ^ D[1] ^ C[1] ^ C[2] ^ C[3] ^ C[5] ^ C[9] ^ C[16] ^ C[19] ^ C[20] ^ C[21] ^ C[25] ^ C[26]; NewCRC[22] = D[31] ^ D[30] ^ D[28] ^ D[25] ^ D[23] ^ D[22] ^ D[20] ^ D[18] ^ D[16] ^ D[12] ^ D[10] ^ D[9] ^ D[8] ^ D[7] ^
Sheinwald, et. al. Informational [Page 16] RFC 3385 iSCSI CRC Considerations September 2002
Sheinwald, et. al. Informational [Page 16] RFC 3385 iSCSI CRC Considerations September 2002
D[5] ^ D[3] ^ D[2] ^ D[0] ^ C[0] ^ C[2] ^ C[3] ^ C[5] ^ C[7] ^ C[8] ^ C[9] ^ C[10] ^ C[12] ^ C[16] ^ C[18] ^ C[20] ^ C[22] ^ C[23] ^ C[25] ^ C[28] ^ C[30] ^ C[31]; NewCRC[23] = D[30] ^ D[29] ^ D[28] ^ D[27] ^ D[25] ^ D[24] ^ D[19] ^ D[18] ^ D[16] ^ D[13] ^ D[12] ^ D[11] ^ D[10] ^ D[7] ^ D[5] ^ D[3] ^ D[1] ^ D[0] ^ C[0] ^ C[1] ^ C[3] ^ C[5] ^ C[7] ^ C[10] ^ C[11] ^ C[12] ^ C[13] ^ C[16] ^ C[18] ^ C[19] ^ C[24] ^ C[25] ^ C[27] ^ C[28] ^ C[29] ^ C[30]; NewCRC[24] = D[31] ^ D[30] ^ D[29] ^ D[28] ^ D[26] ^ D[25] ^ D[20] ^ D[19] ^ D[17] ^ D[14] ^ D[13] ^ D[12] ^ D[11] ^ D[8] ^ D[6] ^ D[4] ^ D[2] ^ D[1] ^ C[1] ^ C[2] ^ C[4] ^ C[6] ^ C[8] ^ C[11] ^ C[12] ^ C[13] ^ C[14] ^ C[17] ^ C[19] ^ C[20] ^ C[25] ^ C[26] ^ C[28] ^ C[29] ^ C[30] ^ C[31]; NewCRC[25] = D[29] ^ D[28] ^ D[25] ^ D[23] ^ D[20] ^ D[17] ^ D[16] ^ D[15] ^ D[14] ^ D[13] ^ D[8] ^ D[6] ^ D[4] ^ D[3] ^ D[2] ^ D[0] ^ C[0] ^ C[2] ^ C[3] ^ C[4] ^ C[6] ^ C[8] ^ C[13] ^ C[14] ^ C[15] ^ C[16] ^ C[17] ^ C[20] ^ C[23] ^ C[25] ^ C[28] ^ C[29]; NewCRC[26] = D[31] ^ D[29] ^ D[28] ^ D[27] ^ D[25] ^ D[24] ^ D[23] ^ D[15] ^ D[14] ^ D[12] ^ D[8] ^ D[6] ^ D[3] ^ D[1] ^ D[0] ^ C[0] ^ C[1] ^ C[3] ^ C[6] ^ C[8] ^ C[12] ^ C[14] ^ C[15] ^ C[23] ^ C[24] ^ C[25] ^ C[27] ^ C[28] ^ C[29] ^ C[31]; NewCRC[27] = D[31] ^ D[29] ^ D[27] ^ D[24] ^ D[23] ^ D[21] ^ D[18] ^ D[17] ^ D[15] ^ D[13] ^ D[12] ^ D[8] ^ D[6] ^ D[5] ^ D[2] ^ D[1] ^ D[0] ^ C[0] ^ C[1] ^ C[2] ^ C[5] ^ C[6] ^ C[8] ^ C[12] ^ C[13] ^ C[15] ^ C[17] ^ C[18] ^ C[21] ^ C[23] ^ C[24] ^ C[27] ^ C[29] ^ C[31]; NewCRC[28] = D[31] ^ D[27] ^ D[26] ^ D[24] ^ D[23] ^ D[22] ^ D[21] ^ D[19] ^ D[17] ^ D[14] ^ D[13] ^ D[12] ^ D[8] ^ D[5] ^ D[4] ^ D[3] ^ D[2] ^ D[1] ^ D[0] ^ C[0] ^ C[1] ^ C[2] ^ C[3] ^ C[4] ^ C[5] ^ C[8] ^ C[12] ^ C[13] ^ C[14] ^ C[17] ^ C[19] ^ C[21] ^ C[22] ^ C[23] ^ C[24] ^ C[26] ^ C[27] ^ C[31]; NewCRC[29] = D[28] ^ D[27] ^ D[25] ^ D[24] ^ D[23] ^ D[22] ^ D[20] ^ D[18] ^ D[15] ^ D[14] ^ D[13] ^ D[9] ^ D[6] ^ D[5] ^ D[4] ^ D[3] ^ D[2] ^ D[1] ^ C[1] ^ C[2] ^ C[3] ^ C[4] ^ C[5] ^ C[6] ^ C[9] ^ C[13] ^ C[14] ^ C[15] ^ C[18] ^ C[20] ^ C[22] ^ C[23] ^ C[24] ^ C[25] ^ C[27] ^ C[28]; NewCRC[30] = D[29] ^ D[28] ^ D[26] ^ D[25] ^ D[24] ^ D[23] ^ D[21] ^
D[5] ^ D[3] ^ D[2] ^ D[0] ^ C[0] ^ C[2] ^ C[3] ^ C[5] ^ C[7] ^ C[8] ^ C[9] ^ C[10] ^ C[12] ^ C[16] ^ C[18] ^ C[20] ^ C[22] ^ C[23] ^ C[25] ^ C[28] ^ C[30] ^ C[31]; NewCRC[23] = D[30] ^ D[29] ^ D[28] ^ D[27] ^ D[25] ^ D[24] ^ D[19] ^ D[18] ^ D[16] ^ D[13] ^ D[12] ^ D[11] ^ D[10] ^ D[7] ^ D[5] ^ D[3] ^ D[1] ^ D[0] ^ C[0] ^ C[1] ^ C[3] ^ C[5] ^ C[7] ^ C[10] ^ C[11] ^ C[12] ^ C[13] ^ C[16] ^ C[18] ^ C[19] ^ C[24] ^ C[25] ^ C[27] ^ C[28] ^ C[29] ^ C[30]; NewCRC[24] = D[31] ^ D[30] ^ D[29] ^ D[28] ^ D[26] ^ D[25] ^ D[20] ^ D[19] ^ D[17] ^ D[14] ^ D[13] ^ D[12] ^ D[11] ^ D[8] ^ D[6] ^ D[4] ^ D[2] ^ D[1] ^ C[1] ^ C[2] ^ C[4] ^ C[6] ^ C[8] ^ C[11] ^ C[12] ^ C[13] ^ C[14] ^ C[17] ^ C[19] ^ C[20] ^ C[25] ^ C[26] ^ C[28] ^ C[29] ^ C[30] ^ C[31]; NewCRC[25] = D[29] ^ D[28] ^ D[25] ^ D[23] ^ D[20] ^ D[17] ^ D[16] ^ D[15] ^ D[14] ^ D[13] ^ D[8] ^ D[6] ^ D[4] ^ D[3] ^ D[2] ^ D[0] ^ C[0] ^ C[2] ^ C[3] ^ C[4] ^ C[6] ^ C[8] ^ C[13] ^ C[14] ^ C[15] ^ C[16] ^ C[17] ^ C[20] ^ C[23] ^ C[25] ^ C[28] ^ C[29]; NewCRC[26] = D[31] ^ D[29] ^ D[28] ^ D[27] ^ D[25] ^ D[24] ^ D[23] ^ D[15] ^ D[14] ^ D[12] ^ D[8] ^ D[6] ^ D[3] ^ D[1] ^ D[0] ^ C[0] ^ C[1] ^ C[3] ^ C[6] ^ C[8] ^ C[12] ^ C[14] ^ C[15] ^ C[23] ^ C[24] ^ C[25] ^ C[27] ^ C[28] ^ C[29] ^ C[31]; NewCRC[27] = D[31] ^ D[29] ^ D[27] ^ D[24] ^ D[23] ^ D[21] ^ D[18] ^ D[17] ^ D[15] ^ D[13] ^ D[12] ^ D[8] ^ D[6] ^ D[5] ^ D[2] ^ D[1] ^ D[0] ^ C[0] ^ C[1] ^ C[2] ^ C[5] ^ C[6] ^ C[8] ^ C[12] ^ C[13] ^ C[15] ^ C[17] ^ C[18] ^ C[21] ^ C[23] ^ C[24] ^ C[27] ^ C[29] ^ C[31]; NewCRC[28] = D[31] ^ D[27] ^ D[26] ^ D[24] ^ D[23] ^ D[22] ^ D[21] ^ D[19] ^ D[17] ^ D[14] ^ D[13] ^ D[12] ^ D[8] ^ D[5] ^ D[4] ^ D[3] ^ D[2] ^ D[1] ^ D[0] ^ C[0] ^ C[1] ^ C[2] ^ C[3] ^ C[4] ^ C[5] ^ C[8] ^ C[12] ^ C[13] ^ C[14] ^ C[17] ^ C[19] ^ C[21] ^ C[22] ^ C[23] ^ C[24] ^ C[26] ^ C[27] ^ C[31]; NewCRC[29] = D[28] ^ D[27] ^ D[25] ^ D[24] ^ D[23] ^ D[22] ^ D[20] ^ D[18] ^ D[15] ^ D[14] ^ D[13] ^ D[9] ^ D[6] ^ D[5] ^ D[4] ^ D[3] ^ D[2] ^ D[1] ^ C[1] ^ C[2] ^ C[3] ^ C[4] ^ C[5] ^ C[6] ^ C[9] ^ C[13] ^ C[14] ^ C[15] ^ C[18] ^ C[20] ^ C[22] ^ C[23] ^ C[24] ^ C[25] ^ C[27] ^ C[28]; NewCRC[30] = D[29] ^ D[28] ^ D[26] ^ D[25] ^ D[24] ^ D[23] ^ D[21] ^
Sheinwald, et. al. Informational [Page 17] RFC 3385 iSCSI CRC Considerations September 2002
Sheinwald, et. al. Informational [Page 17] RFC 3385 iSCSI CRC Considerations September 2002
D[19] ^ D[16] ^ D[15] ^ D[14] ^ D[10] ^ D[7] ^ D[6] ^ D[5] ^ D[4] ^ D[3] ^ D[2] ^ C[2] ^ C[3] ^ C[4] ^ C[5] ^ C[6] ^ C[7] ^ C[10] ^ C[14] ^ C[15] ^ C[16] ^ C[19] ^ C[21] ^ C[23] ^ C[24] ^ C[25] ^ C[26] ^ C[28] ^ C[29]; NewCRC[31] = D[30] ^ D[29] ^ D[27] ^ D[26] ^ D[25] ^ D[24] ^ D[22] ^ D[20] ^ D[17] ^ D[16] ^ D[15] ^ D[11] ^ D[8] ^ D[7] ^ D[6] ^ D[5] ^ D[4] ^ D[3] ^ C[3] ^ C[4] ^ C[5] ^ C[6] ^ C[7] ^ C[8] ^ C[11] ^ C[15] ^ C[16] ^ C[17] ^ C[20] ^ C[22] ^ C[24] ^ C[25] ^ C[26] ^ C[27] ^ C[29] ^ C[30]; nextCRC32_D32 = NewCRC; end endfunction
D[19] ^ D[16] ^ D[15] ^ D[14] ^ D[10] ^ D[7] ^ D[6] ^ D[5] ^ D[4] ^ D[3] ^ D[2] ^ C[2] ^ C[3] ^ C[4] ^ C[5] ^ C[6] ^ C[7] ^ C[10] ^ C[14] ^ C[15] ^ C[16] ^ C[19] ^ C[21] ^ C[23] ^ C[24] ^ C[25] ^ C[26] ^ C[28] ^ C[29]; NewCRC[31] = D[30] ^ D[29] ^ D[27] ^ D[26] ^ D[25] ^ D[24] ^ D[22] ^ D[20] ^ D[17] ^ D[16] ^ D[15] ^ D[11] ^ D[8] ^ D[7] ^ D[6] ^ D[5] ^ D[4] ^ D[3] ^ C[3] ^ C[4] ^ C[5] ^ C[6] ^ C[7] ^ C[8] ^ C[11] ^ C[15] ^ C[16] ^ C[17] ^ C[20] ^ C[22] ^ C[24] ^ C[25] ^ C[26] ^ C[27] ^ C[29] ^ C[30]; nextCRC32_D32 = NewCRC; end endfunction
8.3 Some Hardware Implementation Comments
8.3 Some Hardware Implementation Comments
The iSCSI spec specifies that the most significant 32 bits of the data be complemented prior to performing the CRC computation. For most implementations of the CRC algorithm, such as the ones described here, which perform simultaneous multiplication by x^32 and division by the CRC polynomial, this is equivalent to initializing the CRC register to ones regardless of the CRC polynomial. For other implementations, in particular one that only performs division by the CRC polynomial (and for which the prescribed multiplication by x^32 is performed externally) initializing the CRC register to ones does not have the same effect as complementing the most significant 32 bits of the message. With such implementations, for the CRC32c polynomial, initializing the CRC register to 0x2a26f826 has the same effect as complementing the most significant 32 bits of the data. See reference [Tuikov&Cavanna] for more details.
The iSCSI spec specifies that the most significant 32 bits of the data be complemented prior to performing the CRC computation. For most implementations of the CRC algorithm, such as the ones described here, which perform simultaneous multiplication by x^32 and division by the CRC polynomial, this is equivalent to initializing the CRC register to ones regardless of the CRC polynomial. For other implementations, in particular one that only performs division by the CRC polynomial (and for which the prescribed multiplication by x^32 is performed externally) initializing the CRC register to ones does not have the same effect as complementing the most significant 32 bits of the message. With such implementations, for the CRC32c polynomial, initializing the CRC register to 0x2a26f826 has the same effect as complementing the most significant 32 bits of the data. See reference [Tuikov&Cavanna] for more details.
8.4 Fast Hardware Implementation References
8.4 Fast Hardware Implementation References
Fast hardware implementations start from a canonic scheme (as the one presented in 7.2) and optimize it based on different criteria. Two classic papers on this subject are [Albertengo1990] and [Glaise1997]. A more modern (and systematic) approach can be found in [Shie2001] and [Sprachman2001].
Fast hardware implementations start from a canonic scheme (as the one presented in 7.2) and optimize it based on different criteria. Two classic papers on this subject are [Albertengo1990] and [Glaise1997]. A more modern (and systematic) approach can be found in [Shie2001] and [Sprachman2001].
9. Summary and Conclusions
9. Summary and Conclusions
The following table is a summary of the error detection capabilities of the different codes analyzed. In the table, d is the minimal distance at block length block (in bits), i/byte - software instructions/byte, Table size (if table lookup needed), T-look number of lookups/byte, Pudb - Pud burst and Puds - Pud sporadic:
The following table is a summary of the error detection capabilities of the different codes analyzed. In the table, d is the minimal distance at block length block (in bits), i/byte - software instructions/byte, Table size (if table lookup needed), T-look number of lookups/byte, Pudb - Pud burst and Puds - Pud sporadic:
Sheinwald, et. al. Informational [Page 18] RFC 3385 iSCSI CRC Considerations September 2002
Sheinwald, et. al. Informational [Page 18] RFC 3385 iSCSI CRC Considerations September 2002
+-----------------------------------------------------------+ | Code |d| Block |i/Byte|Tsize|T-look| Pudb | Puds | +-----------------------------------------------------------+ | Fletcher32|3| 2^19 | 2 | - | - | 10^-37 | 10^-36 | +-----------------------------------------------------------+ | Adler32 |3| 2^19 | 3 | - | - | 10^-36 | 10^-35 | +-----------------------------------------------------------+ | IEEE-802 |3| 2^16 | 2.75 | 2^18| 0.5/b| 10^-41 | 10^-40 | +-----------------------------------------------------------+ | CRC32C |3| 2^31-1| 2.75 | 2^18| 0.5/b| 10^-41 | 10^-40 | +-----------------------------------------------------------+
+-----------------------------------------------------------+ | Code |d| Block |i/Byte|Tsize|T-look| Pudb | Puds | +-----------------------------------------------------------+ | Fletcher32|3| 2^19 | 2 | - | - | 10^-37 | 10^-36 | +-----------------------------------------------------------+ | Adler32 |3| 2^19 | 3 | - | - | 10^-36 | 10^-35 | +-----------------------------------------------------------+ | IEEE-802 |3| 2^16 | 2.75 | 2^18| 0.5/b| 10^-41 | 10^-40 | +-----------------------------------------------------------+ | CRC32C |3| 2^31-1| 2.75 | 2^18| 0.5/b| 10^-41 | 10^-40 | +-----------------------------------------------------------+
The probabilities for undetected errors in the above table are computed assuming uniformly distributed data. For real data - that can be biased - [Stone98], checksums behave substantially worse than CRCs.
The probabilities for undetected errors in the above table are computed assuming uniformly distributed data. For real data - that can be biased - [Stone98], checksums behave substantially worse than CRCs.
Considering the protection level it offers, the lack of sensitivity for biased data and the large block it can protect, we think that CRC32C is a good choice as a basic error detection mechanism for iSCSI.
Considering the protection level it offers, the lack of sensitivity for biased data and the large block it can protect, we think that CRC32C is a good choice as a basic error detection mechanism for iSCSI.
Please observe also that burst errors characterized by a fixed average time will have a higher impact on error detection capability as the speed of the channels (machines and networks) increases. The only way to keep the Pud within bounds for the long-term is to reduce the BER by using better coding of lower levels of the channel.
Please observe also that burst errors characterized by a fixed average time will have a higher impact on error detection capability as the speed of the channels (machines and networks) increases. The only way to keep the Pud within bounds for the long-term is to reduce the BER by using better coding of lower levels of the channel.
10. Security Considerations
10. Security Considerations
These codes detect unintentional changes to data such as those caused by noise. In an environment where an attacker can change the data, it can also change the error-detection code to match the new data. Therefore, the error-detection codes overviewed here do not provide protection against attacks. Indeed, these codes are not intended for security purposes; they are meant to be used within some application, and the application's threat model and security design control the security considerations for the use of the CRC.
これらのコードは雑音によって引き起こされたものなどのデータへの意図的でない変化を検出します。 また、攻撃者がデータを変えることができる環境で、それは、新しいデータを合わせるためにエラー検出コードを変えることができます。 したがって、ここで「過剰-見」られたエラー検出コードは攻撃に対する保護を提供しません。 本当に、これらのコードはセキュリティ目的のために意図しません。 それらは何らかのアプリケーションの中で使用されることになっています、そして、アプリケーションの脅威モデルとセキュリティデザインはCRCの使用のためにセキュリティ問題を制御します。
11. References and Bibliography
11. 参照と図書目録
[Albertengo1990] G. Albertengo, R. Sisto, "Parallel CRC Generation
IEEE Micro", Vol. 10, No. 5, October 1990, pp. 63-
71.
[Albertengo1990] G.Albertengo、R.シスト、「平行なCRC世代IEEEミクロ」、Vol.10、No.5、1990年10月、ページ 63- 71.
[Arazi] B Arazi, "A commonsense Approach to the Theory of
Error Correcting codes".
[アラジ]Bアラジ、「Error CorrectingコードのTheoryへの常識的なApproach。」
Sheinwald, et. al. Informational [Page 19] RFC 3385 iSCSI CRC Considerations September 2002
et Sheinwald、アル。 [19ページ]情報のRFC3385iSCSI CRC問題2002年9月
[Baicheva] T Baicheva, S Dodunekov and P Kazakov, "Undetected
error probability performance of cyclic redundancy-
check codes of 16-bit redundancy", IEEE Proceedings
on Communications, 147:253-256, October 2000.
[Baicheva] T BaichevaとS DodunekovとPカザコーフ、「16ビットの冗長の周期的な冗長検査符号のUndetectedエラー確率性能」、Communications、147のIEEE Proceedings: 253-256と、2000年10月。
[Black] "Fast CRC32 in Software" by Richard Black, 1994, at
www.cl.cam.ac.uk/Research/SRG/bluebook/21/crc/crc.
html.
[黒い] リチャードBlack、www.cl.cam.ac.uk/研究/SRG/bluebook/21/crc/crc. htmlの1994年までに「ソフトウェアの速いCRC32。」
[Castagnoli93] Guy Castagnoli, Stefan Braeuer and Martin Herrman
"Optimization of Cyclic Redundancy-Check Codes with
24 and 32 Parity Bits", IEEE Transact. on
Communications, Vol. 41, No. 6, June 1993.
IEEEは、「24と32のパリティビットとの周期的な冗長検査コードの最適化」と商取引します。[Castagnoli93]奴のCastagnoli、ステファンBraeuer、およびマーチンHerrman. コミュニケーション、Vol.41、No.6、1993年6月で。
[braun01] Florian Braun and Marcel Waldvogel, "Fast
Incremental CRC Updates for IP over ATM Networks",
IEEE, High Performance Switching and Routing, 2001,
pp. 48-52.
[braun01] フローリアンブラウンとマルセルWaldvogelと「速い気圧ネットワークの上のIPにおける増加のCRCアップデート」とIEEEとHighパフォーマンスSwitchingとルート設定、2001、ページ 48-52.
[FITS] "NASA FITS documents" at http://heasarc.gsfc.nasa.
gov/docs/heasarc/ofwg/docs/general/checksum/node26.
html.
[適合サイズ]、「NASA、適合サイズ、ドキュメント、」 http://heasarc.gsfc.nasa gov/docs/heasarc/ofwg/docs/一般/チェックサム/node26htmlで。
[Fujiwara89] Toru Fujiwara, Tadao Kasami, and Shu Lin, "Error
detecting capabilities of the shortened hamming
codes adopted forerror detection in IEEE standard
802.3", IEEE Transactions on Communications, COM-
37:986989, September 1989.
[Fujiwara89] Toruフジワラ、Tadao Kasami、およびシュ・リン、「短くされたハミング・コードの誤り検出能力はIEEEの標準の802.3でforerror検出を採用した」Communicationsの上のIEEE Transactions、COM37:986989、1989年9月。
[Glaise1997] Glaise, R. J., "A two-step computation of cyclic
redundancy code CRC-32 for ATM networks", IBM
Journal of Research and Development, Volume 41,
Number 6, 1997.
[Glaise1997]Glaise、R.J.、「ATMネットワークのための周期的な冗長コードCRC-32のツーステップ計算」、ResearchとDevelopmentのIBM Journal、Volume41(Number6、1997)。
[ieee1364] IEEE Standard Hardware Description Language Based on
the Verilog Hardware Description Language, IEEE
Standard 1364-1995, December 1995.
[ieee1364]IEEEの標準のハードウェア記述言語は規格1364-1995、1995年12月をVerilogハードウェア記述言語、IEEEに基礎づけました。
[LinCostello] S. Lin and D.J. Costello, Jr., "Error Control
Coding: Fundamentals and Applications", Englewood
Cliffs, NJ: Prentice Hall, 1983.
[LinCostello]S.リンとD.J.コステロ、Jr.、「以下をコード化する誤り制御」 「原理とアプリケーション」、イングルウッドがけ、ニュージャージー: 新米のホール、1983。
[Peterson] W Wesley Peterson & E J Weldon - Error Correcting
Codes - First Edition 1961/Second Edition 1972.
[ピーターソン]Wウエスリー・ピーターソンとE Jウェルダン--誤り検出方式--初版1961/第2版1972。
Sheinwald, et. al. Informational [Page 20] RFC 3385 iSCSI CRC Considerations September 2002
et Sheinwald、アル。 [20ページ]情報のRFC3385iSCSI CRC問題2002年9月
[RFC2026] Bradner, S., "The Internet Standards Process --
Revision 3", BCP 9, RFC 2026, October 1996.
[RFC2026] ブラドナー、S.、「改正3インチ、BCP9、RFC2026、1996年インターネット標準化過程--10月。」
[Ritter] Ritter, T. 1986. The Great CRC Mystery. Dr. Dobb's
Journal of Software Tools. February. 11(2): 26-34,
76-83.
[リッター]リッター、T.1986。 すばらしいCRCミステリー。 ドッブ博士のソフトウェアツールのジャーナル。 2月。 11(2): 26-34, 76-83.
[Polynomials] "Information on Primitive and Irreducible
Polynomials" at http://www.theory.csc.uvic.ca/~cos/
inf/neck/PolyInfo.html.
[多項式] http://www.theory.csc.uvic.ca/~cos/ inf/首/PolyInfo.htmlの「原始的で削減できない多項式に関する情報。」
[RFC1146] Zweig, J. and C. Partridge, "TCP Alternate Checksum
Options", RFC 1146, March 1990.
[RFC1146] ツバイクとJ.とC.ヤマウズラ、「TCPの交互のチェックサムオプション」、RFC1146、1990年3月。
[RFC1950] Deutsch, P. and J. Gailly, "ZLIB Compressed Data
Format Specification version 3.3", RFC 1950, May
1996.
[RFC1950] ドイツ語、P.、およびJ.ゲイル、「ZLIB Compressed Data Format Specification、バージョン3.3インチ、RFC1950、1996インチ年5月。
[Shie2001] Ming-Der Shieh, et. al, "A Systematic Approach for
Parallel CRC Computations", Journal of Information
Science and Engineering, Vol.17 No.3, pp.445-461.
et[Shie2001]明-Der Shieh、アル、「平行なCRC計算のためのシステム・アプローチ」、情報ScienceとEngineeringのJournal、Vol.17No.3(pp.445-461)。
[Sprachman2001] Michael Sprachman, "Automatic Generation of Parallel
CRC Circuits", IEEE Design & Test May-June 2001.
[Sprachman2001]マイケルSprachman、「平行なCRCサーキットの自動世代」と、IEEEは、2001年5月-6月に設計して、テストします。
[Stone98] J. Stone et. al., "Performance of Checksums and
CRC's over Real Data", IEEE/ACM Transactions on
Networking, Vol. 6, No. 5, October 1998.
[Stone98]J.ストーンetアル、「本当のデータの上のチェックサムとCRCのパフォーマンス」、Networking、Vol.6、No.5(1998年10月)のIEEE/ACM Transactions
[Williams] Ross Williams - A PAINLESS GUIDE TO CRC ERROR
DETECTION ALGORITHMS widely available on the net -
(e.g., ftp.adelaide.edu.au/pub/rocksoft/crc_v3.txt)
[ウィリアムズ] ロス・ウィリアムズ--ネットで広く利用可能なPAINLESS GUIDE TO CRC ERROR DETECTION ALGORITHMS、-(例えば、ftp.adelaide.edu.au/パブ/rocksoft/crc_v3.txt)
[Wolf82] J.K. Wolf, Arnold Michelson and Allen Levesque, "On
the probability of undetected error for linear block
codes", IEEE Transactions on Communications, COM-30:
317-324, 1982.
[Wolf82] J.K.ヴォルフとアーノルド・マイケルソンとアレン・レベスク、「直線的なブロック・コードのための非検出された誤りの確率」、Communications、COM-30の上のIEEE Transactions: 317-324, 1982.
[Wolf88] J.K. Wolf, R.D. Blackeney, "An Exact Evaluation of
the Probability of Undetected Error for Certain
Shortened Binary CRC Codes", Proc. MILCOM - IEEE
1988.
[Wolf88]J.K.ヴォルフ、R.D.Blackeney、「確かなUndetected誤りの確率の的確な評価は2進のCRCコードを短くしました」、Proc。 MILCOM--IEEE1988。
[Wolf94J] J.K. Wolf and Dexter Chun, "The single burst error
detection performance of binary cyclic codes", IEEE
Transactions on Communications COM-42:11-13, January
1994.
[Wolf94J] J.K.ヴォルフとデクスター・クーン、「シングルは2進の巡回符号の誤り検出性能を押し破きました」、Communications COM-42: 11-13のIEEE Transactions、1994年1月。
Sheinwald, et. al. Informational [Page 21] RFC 3385 iSCSI CRC Considerations September 2002
et Sheinwald、アル。 [21ページ]情報のRFC3385iSCSI CRC問題2002年9月
[Wolf94O] Dexter Chun and J.K. Wolf, "Special Hardware for
computing the probability of undetected error for
certain binary crc codes and test results", IEEE
Transactions on Communications, COM-42:2769-2772.
[Wolf94O]デクスター・クーンとJ.K.ヴォルフ、「ある2進のcrcコードとテストのための非検出された誤りの確率を計算するための特別なHardwareは結果になります」、Communicationsの上のIEEE Transactions、COM-42: 2769-2772。
[Tuikov&Cavanna] Luben Tuikov and Vicente Cavanna, "The iSCSI CRC32C
Digest and the Simultaneous Multiply and Divide
Algorithm", January 30, 2002. White paper
distributed to the IETF ips iSCSI reflector.
[Tuikovとカヴァナ]のリューベンTuikovとビセンテ・カヴァナ、「iSCSI CRC32Cダイジェストと同時は、アルゴリズムを掛けて、割る」2002年1月30日。 IETF ips iSCSI反射鏡に配布された白書。
12. Acknowledgements
12. 承認
We would like to thank Matt Wakeley for providing us with the motivation to co-author this paper and for helpful discussions on the subject matter, during his employment with Agilent.
内容でこの紙について共同執筆する動機を私たちに提供して、役立つ議論についてマット・ウェイクリーに感謝申し上げます、Agilentとの彼の雇用の間。
13. Authors' Addresses
13. 作者のアドレス
Julian Satran IBM, Haifa Research Lab MATAM - Advanced Technology Center Haifa 31905, Israel EMail: julian_satran@il.ibm.com
ジュリアンSatran IBM、ハイファ研究研究室マタム--先進技術センターハイファ31905、イスラエルメール: julian_satran@il.ibm.com
Dafna Sheinwald IBM, Haifa Research Lab MATAM - Advanced Technology Center Haifa 31905, Israel EMail: Dafna_Sheinwald@il.ibm.com
Dafna Sheinwald IBM、ハイファ研究研究室マタム--先進技術センターハイファ31905、イスラエルメール: Dafna_Sheinwald@il.ibm.com
Pat Thaler Agilent Technologies 1101 Creekside Ridge Drive Suite 100, M/S RH21 Roseville, CA 95661 EMail: pat_thaler@agilent.com
パットターレルAgilent技術1101クリークサイド尾根ドライブスイート100、RH21ローズビル、M/Sカリフォルニア 95661はメールされます: pat_thaler@agilent.com
Vicente Cavanna Agilent Technologies 1101 Creekside Ridge Drive Suite 100, M/S RH21 Roseville, CA 95661 EMail: vince_cavanna@agilent.com
ビセンテカヴァナAgilent Technologies1101クリークサイド尾根ドライブスイート100、RH21ローズビル、M/Sカリフォルニア 95661はメールされます: vince_cavanna@agilent.com
Sheinwald, et. al. Informational [Page 22] RFC 3385 iSCSI CRC Considerations September 2002
et Sheinwald、アル。 [22ページ]情報のRFC3385iSCSI CRC問題2002年9月
14. Full Copyright Statement
14. 完全な著作権宣言文
Copyright (C) The Internet Society (2002). All Rights Reserved.
Copyright(C)インターネット協会(2002)。 All rights reserved。
This document and translations of it may be copied and furnished to others, and derivative works that comment on or otherwise explain it or assist in its implementation may be prepared, copied, published and distributed, in whole or in part, without restriction of any kind, provided that the above copyright notice and this paragraph are included on all such copies and derivative works. However, this document itself may not be modified in any way, such as by removing the copyright notice or references to the Internet Society or other Internet organizations, except as needed for the purpose of developing Internet standards in which case the procedures for copyrights defined in the Internet Standards process must be followed, or as required to translate it into languages other than English.
それに関するこのドキュメントと翻訳は、コピーして、それが批評するか、またはそうでなければわかる他のもの、および派生している作品に提供するか、または準備されているかもしれなくて、コピーされて、発行されて、全体か一部広げられた実現を助けるかもしれません、どんな種類の制限なしでも、上の版権情報とこのパラグラフがそのようなすべてのコピーと派生している作品の上に含まれていれば。 しかしながら、このドキュメント自体は何らかの方法で変更されないかもしれません、インターネット協会か他のインターネット組織の版権情報か参照を取り除くのなどように、それを英語以外の言語に翻訳するのが著作権のための手順がインターネットStandardsの過程で定義したどのケースに従わなければならないか、必要に応じてさもなければ、インターネット標準を開発する目的に必要であるのを除いて。
The limited permissions granted above are perpetual and will not be revoked by the Internet Society or its successors or assigns.
上に承諾された限られた許容は、永久であり、インターネット協会、後継者または案配によって取り消されないでしょう。
This document and the information contained herein is provided on an "AS IS" basis and THE INTERNET SOCIETY AND THE INTERNET ENGINEERING TASK FORCE DISCLAIMS ALL WARRANTIES, EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO ANY WARRANTY THAT THE USE OF THE INFORMATION HEREIN WILL NOT INFRINGE ANY RIGHTS OR ANY IMPLIED WARRANTIES OF MERCHANTABILITY OR FITNESS FOR A PARTICULAR PURPOSE.
このドキュメントとそして、「そのままで」という基礎とインターネットの振興発展を目的とする組織に、インターネット・エンジニアリング・タスク・フォースが速達の、または、暗示しているすべての保証を放棄するかどうかというここにことであり、他を含んでいて、含まれて、情報の使用がここに侵害しないどんな保証も少しもまっすぐになるという情報か市場性か特定目的への適合性のどんな黙示的な保証。
Acknowledgement
承認
Funding for the RFC Editor function is currently provided by the Internet Society.
RFC Editor機能のための基金は現在、インターネット協会によって提供されます。
Sheinwald, et. al. Informational [Page 23]
et Sheinwald、アル。 情報[23ページ]
一覧
スポンサーリンク
