Network Working Group                                       D. Sheinwald
Request for Comments: 3385                                     J. Satran
Category: Informational                                              IBM
                                                               P. Thaler
                                                              V. Cavanna
                                                                 Agilent
                                                          September 2002
        

Internet Protocol Small Computer System Interface (iSCSI) Cyclic Redundancy Check (CRC)/Checksum Considerations

インターネットプロトコルスモールコンピュータシステムインタフェース(iSCSI)巡回冗長検査(CRC)/チェックサム考慮事項

Status of this 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.

著作権(c)インターネット社会(2002)。全著作権所有。

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).

このメモでは、インターネットプロトコルスモールコンピュータシステムインタフェース(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.

また、利用可能なデータによって許可されているように、巡回冗長検査(CRC)(例えば、Fletcher、Adler、Weighted Checksums)と比較しようとします。

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 developers for many years. However, algorithms and software for effective implementations of CRC are now also widely available [Williams].

巡回冗長検査(CRC)コード[Peterson]は、エラー検出に使用される巡回コードを短縮します。ATM、IEC、IEEE、CCITT、IBM-SDLC、およびより多くの[Baicheva]には、さまざまなCRCコードが採用されています。この種のコードからの最も重要な期待は、検出されないエラーに対する非常に低い可能性です。そのようなコードにおける未検出の誤差の確率は、分析モデルとシミュレーションの両方を含んでいた広範な研究を受けています。それらのコードは、それらが良好な「バーストエラー」検出機能を示すが、いくつかの独立したビットエラーを検出するのが得意であるので、それらのコードは通信および磁気記録で使用されてきた。ハードウェア実装は非常にシンプルでよく知られています。彼らの単純さは長年にわたってハードウェア開発者に人気されました。しかしながら、CRCの効果的な実装のためのアルゴリズムおよびソフトウェアもまた広く利用可能である[Williams]。

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(ビットエラーレート)を中心に回転します。ただし、これらの数値は、バーストエラー率が平均バースト長を掛けたのを掛けたものを反映しています。フィールドエンジニアリングテストでは、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.

コミュニケーションや記録メディアを超えても、エラーの影響は激しくなります。この例は、単一のビット以上に影響を与えるメモリエラーであり、パケットを操作しながらパケットを操作している間に発生するソフトウェアエラーは、通信エラーとは異なるメモリエラーです。ソフトウェアエラーにもバーストエラーが発生します。さらに、シリアル内部インターコネクトはこのタイプのエラーもマシン内で最も一般的なものになります。

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.)

バーストでは、所与の伝送速度SでA = BD * Sビットの平均バーストをもたらすBDの平均バースト誤差期間を仮定する。(例えば、1GBSで3nsの平均バースト持続時間は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を取ります。有線通信チャネル上のBERに引用されている数字は10 ^ -10から10 ^ -12の間であり、BERはバーストエラーレート*の平均バースト長として考慮されます。それにもかかわらず、チャネルが無線リンクを含む場合、エラー率は実質的に高いことを留意してください。

For independent single bit errors, we assume a 10^-11 error rate.

独立したシングルビットエラーの場合は、10 ^ -11エラー率を想定します。

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).

エラー検出メカニズムはエラーなしで大量のデータ(Petabytes = 10 ^ 16ビット)を輸送する必要があるため、すべてのブロック長に対して検出されなかったエラーに対する非常に低い確率をターゲットにします。1回のリンクで2週間以上。

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が効率的に実行されなければならないので、選択された保護機構の誤り検出能力が非常に良く、少なくとも最大8Kバイト(64KBIS)の長さを超えることを必要とする。

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 ^ 23はAvogadro Numberですが、10 ^ 45は既知の宇宙の原子数です(または長年は何年も前に読んだとき)、それらは私たちが住むことができる偶発的な範囲です。8Kブロックの場合、(10 ^ -23、10 ^ -45)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).

バイナリ(N、K)CRCコードCの各コードワードは、n = k rビットからなる。Rパリティビットのブロックは、K情報ビットのブロックから計算されます。コードには、次数Rジェネレータ多項式g(x)があります。

The code is linear in the sense that the bitwise addition of any two codewords yields a codeword.

コードは、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.)

g(x)がn = mのいずれかで分割され、コードCは、g(x)modulo(x ^ m)-1のすべての乗算のセットdを含む。またはN <M、Cは、MN特異的位置で後者の各ワードを短くすることによってDから得られる。(これは、すべてのゼロワードが破棄され、重複が維持されていないため、単語の数が減少します。)

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によって測定されます。

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のコードワードの数(すなわち、I 1ビットで)を示す。2値対称チャネル(BSC)の場合、確率0 <= epsilon <= 0.5の散発的で独立したビット誤差率を備えた場合、コードCに対する検出されないエラーの確率は次のように与えられます。

Pud(C,epsilon) = Sigma[for i=d to n] (Ai*(epsilon^i)*(1-epsilon)^(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つのコードワード間の最小の重み差は、コードの直線性によっても、コード内のコードワードの最小重みです。PUDはまた、デュアルコードの重量分布によって表現することができ、それぞれが直交している単語のセット(ビット単語および偶数の1ビットをもたらす)には、PUDを使用して計算することができるという事実デュアルコードは非常に重要です。コード内のコードワードの数は2 ^ ^ ^ ^ kであるが、デュアルコード内のコードワードの数は2 ^ rである。kは16または24または32のオーダーでrの順序でrです。

Pud (C,epsilon) = 2^-r Sigma [for i=0 to n] Bi*(1-2*epsilon)^i -
(1-epsilon)^n
        

Wolf [Wolf94o] introduced an efficient algorithm for enumerating all the codewords of a code and finding their weight distribution.

WOLF [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.

WOLL [WOLF82]は、想定されたものに対抗することを発見した(1)PUD(C、Epsilon)> PUD(C、0.5)が= 0.5であり、(2)PUDが常に増加するわけではありません。0 <=ε≦0.5。最悪のPUDであると仮定されたものの値は、PUD(C、0.5)=(2 ^ -R) - (2 ^ -N)です。これは、epsilon = 0.5では、2つの2つの受信単語が等しく、それらのうちすべての2つの^ nが同様に可能性があり、それらは送信されたコードワードとは異なります。以前はPUDが[2 ^(nr)-1] /(2 ^ n-1)と仮定されていたか、またはnよりも小さい程度の多項式の非ゼロ倍数の比率(そのような倍数は検出されない)可能な誤差多項式の数。いずれの式PUDが1/2 ^ Rに近づくと、Nは無限大に近づくにつれて、オオカミの式はより正確です。

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 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.

WOLF [WOLF94J] R = 16パリティビットのCCITTコードを調べた。このコードは、g(x)の多項式によって生成された長さ2 ^(r - 1)-1(CCITT 16 - ビットの場合のR = 16)のBCHコードの族の一員のメンバーのメンバーのメンバーのメンバーのメンバーです(x)=(x 1)p(x)p(x)は、= r - 1の原始多項式(この場合は= 15)である。これらのコードはBCH設計距離4を有する。すなわち、コード内の任意の2つの符号語間の最小距離は少なくとも4ビットである(これは、アルファの一連の順序、P(x)の根本的なものによって獲得される。G(X)の根である、3つの連続した電力 - アルファ^ 0、alpha ^ 1、alpha ^ 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.

オオカミは、同じコードワード長の特定のコードのさまざまなバージョンが同じことを実行し、同じ(どの特定のインデックスが元のコードから省略されている)を実行することがわかりました。彼はまた、非短縮コードでは、すべての原始多項式が同じ性能のコードを生み出すことを発見しました。しかし、短縮されたバージョンのために、原始多項式の選択は違いを生じさせる。WOLF [WOLF94J]はプリミティブ多項式を見つけた(x 1を掛けた場合)CCITTの順序でCCITTの順に発生する生成多項式をもたらしました。32ビットの冗長ビットの場合、彼は、長さ33の長さ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.

Baichevaら。al。[Baicheva]は、g(x)=(x 1)p(x)、および他の形式の形状16の異なる生成多項式を包括的に比較した。それらは1024ビットまでのコード長にPUDを計算しました。彼らは彼らの「良さ」を測定しました - PUD(C、Epsilon)<= PUD(C、0.5)、「行儀の良い」 - IF PUD(C、Epsilon)が範囲のεと共に増加する(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.

単一のバーストエラーの場合、Wolf [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の長さb≦rの1バースト誤差が0である確率は2 ^ ^ - (rのwolf94j)である。-1)、およびB> R 1のうち、原始多項式の選択とは無関係に、2 ^ -Rです。

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に対して、未検出の確率(B:P)バーストエラーを最大にする0.5とは異なるPの値があることがわかった。

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)バーストが発生した(B:P)バーストが発生したことを考えると、範囲R <B <Nの範囲R <B <Nの範囲のすべてのBについて、同じコード(同じ生成多項式)に対する検出されないエラーの確率(同じ生成多項式)は、この短縮されたコードがチャネル(Sporadic、独立した)ビット誤差確率pを有する二値対称チャネルと共に使用されるときにブロック長Bに短縮される。

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、Fujiwara et al。[FUJIWARA89] IEEE 802.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 ^ 11 x ^ 10 x ^ 8 x ^ 7 x ^ 5 x ^ 4 x ^ 2 x 1、したがって設計されたその距離は3です。この距離は、2 ^ 32-1である限り、コードを保持します。しかしながら、IEEE802.3内のデータリンク層のMAC(メディアアクセス制御)のフレームフォーマット、ならびにイーサネット(1980)のデータリンク層のフレームフォーマット(1980)は、12,144ビットを超える長さ。したがって、[Fujiwara89]では、このような境界の長さのみを調べます。短縮バージョンの場合、最小距離は長さ4096~12,144の場合は4であることがわかりました。 5長さ512~2048については5。図33から42までの長さの計算結果のチャートは、PUDの計算結果のチャートをepsilon = 10 ^ -5 - 10 ^ -4、PUDの長さ12,144とBSCの符号であることがわかります。 (12,144、イプシロン)= 10 ^ -14 - 10 ^ -13およびε= 10 ^ -4 - 10 ^ -3、PUD(512、ε)= 10 ^ -15、PUD(1024、ε)= 10 ^ -14、PUD(2048、Epsilon)= 10 ^ -13、PUD(4096、イプシロン)= 10 ^ -12 - 10 ^ -11、およびPUD(8192、ε)= 10 ^ -10これは2にかなり近い^ -32。

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.

Castagnoliら。al。[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-reledure-polynomialの人気クラスでは、それらは47000多項式(すべての可能なものではありません)を調べました。それらが見つかった最善のことは、5275およびD = 4から2 ^ 31-1(ビット)までの長さをブロックするためにD = 6を有する。

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まで少なくとも64,000ビット(富士クラが12,144を見て)、D = 3まで2 ^ 32-1ビットまでのD = 3です。

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とFletcherチェックサムの性能を評価しました。この実験の結果は、チェックサムが入力データの「ホットスポット」を拡散させないという事実から生じる実データ上のチェックサムの深刻な弱さを示しています。ただし、結果はFletcherが通常のTCPチェックサムよりも2倍になることを示しています。

4. Probability of Undetected Errors - Burst Error
4. 未検出エラーの確率 - バーストエラー
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.
        

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.

この論文で導出された結果を使用して、あるいは所与のコードに対して、所与のコードに対して、32 <B <Nの範囲内の全てのBの場合、条件付き確率が32 <B <Nの範囲内の全てのBの場合、検出された誤差の確率を図して考える。(B:P)バーストが発生したことを考慮して、(n、n-32)コードの検出されたエラーは、同じコード(同じ生成多項式)に対する検出されないエラーの確率と等しい。この短縮されたコードは、チャネル(SpoRadic、独立)ビット誤差確率pを持つ2値対称チャネルと共に使用されます。

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 .

PUD(C、ε)= =シグマ[i = dからn]((nを選ぶ)/ 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]から、このような小さいn、d = 15のために、32ビットCRCの場合は知っています。したがって、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}.

Pubを最大にするビット誤り率P *で計算された、Wolf [Wolf94j]から、最も寛大な条件付き確率を撮る(P)

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:

バースト長の密度関数については、Rayleigh密度関数(整数に対する離散化)を想定します。これは、複素数のガウス分布の絶対値の密度です。

f(x) = x / a^2 exp {-x^2 / 2a^2 } , x>0 .

f(x)= x / a ^ 2 exp {-x ^ 2 / 2a ^ 2}、x> 0。

This density function has a peak at the parameter a and it decreases smoothly as x increases.

この密度関数はパラメータaにピークを有し、xが増加するにつれてスムーズに減少する。

We take three consecutive bits as the most common burst event once an error does occur, and thus a=3.

エラーが発生したら、最も一般的なバーストイベントとして3つの連続したビットを取り、したがってa = 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のバーストが特定の位置に発生する確率は、バーストエラー率がバーストエラー率であり、これは10 ^ { - 10}、時間F(B)と見積もります。B = 33の計算F(33)= 1.94×10 ^ { - 26}一緒に、我々は、特定の位置から始まる長さ33のバーストが発生した確率が1.94×10 ^ { - 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 *

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の場合、F(34)= 4.85 * 10 ^ { - 28}であることがわかります。10 ^ { - 10}とPUDによる倍増(P *

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.

これをコードの長さだけ掛けると(これまでの位置についてはこれまでの場合)、未検出バーストの確率の上限として10 ^ -45 * 6.5 * 10 ^ 4 = 6.5 * 10 ^ -41があります。長さ8kバイトのコードに対するエラー。

We can also apply this overestimation for IEEE 802.3.

IEEE 802.3のこの過大評価を適用することもできます。

Comment: 2^{-32} = 2.33*10^{-10}.

コメント:2 ^ { - 32} = 2.33 * 10 ^ { - 10}。

5. Probability of Undetected Errors - Independent Errors
5. 未検出エラーの確率 - 独立したエラー
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.

[CastAgnoli93]では、BER = EPSILON = 10 ^ -6の場合、1ビット誤差のためのPUDは、1つの長さ8KBのコードの場合、IEEE-802.3とCRC32Cは10 ^ { - 20}です。また、CRC32Cには距離4があり、このコード長では3または4のいずれかがあることを報告します。これから、この長さのコードの最小距離は、イプシロンの推定値、すなわち10 ^ { - 11}で、報告された結果に{10 ^ { - 5}} ^ 4 = 10の推定であると結論します。CRC32Cの場合は^ { - 20}、およびIEEE802.3の10 ^ { - 15}または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はFletcherより約12,000優れており、アドララーより22,000が優れています。バーストエラーの場合、未検出のバーストを生み出すことができる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は、I1およびI2がI1で示されているI1およびI2は、Iに対して算出されたCRC(I)を示すCRC(I)、およびビット単位モジュロ-2加算を示すCRC(I1 I2)= CRC(I1)CRCを有する。(i2)

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.

したがって、ヘッダHからなるIPパケットに続いて、その後にCRCビットC = CRC(HD)が続いて、ヘッダHがH 'になるノードに到着する。ここで、0はデータブロックDの長さの全0ブロックであり、加算および減算はビットされたモジュロ2である。

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).

その後、データDの後にヘッダHが続くかのようにパケットを想像することができ、それに応じてCRCを計算し、C = CRC(DH)、およびCRC(0 H'-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はそれがある場合に限り、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多項式のコストの比較は、http://www.easics.com/webtools/crctoolで利用可能なツールを使用して、さまざまなCRC多項式のCRCジェネレータ/チェッカーを実装しました。プログラムは、多項式を指定した後、1クロックサイクルで処理されるデータビット数Kの数と同様に、VerilogまたはVHDLコードを提供します。シリアル実装の場合、kは1つになります。

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     |
   +----------------------------------------------+
        

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.

(共有用語)およびセルに関して(2つの入力ごとに4つのセル、2入力XORごとに7つのセル、インバータあたり3個のセル)を最適化した後、2つの候補多項式のコストを次の表に示します。

   +-----------------------------------+
   | Polynomial  | 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ビットデータパスの場合、CCITT-CRC32はCRC32Cに必要なセル数の40%を必要とします。64ビットデータパスの場合、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.

一度に1つのデータビットを処理し、データ多項式の同時乗算を実行し、CRC32C多項式による除算を実行するシリアル実装は、次のVerilog [IEEE1364]コードに記載されています。

   /////////////////////////////////////////////////////////////////////
   //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];
        
   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
        
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)
        
   //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]
   ^
   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[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[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[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 いくつかのハードウェア実装コメント

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.

iSCSI Specは、CRC計算を実行する前にデータの最上位32ビットを補完することを指定します。ここで説明されているものなど、CRCアルゴリズムのほとんどの実装では、CRC多項式による同時倍率と分割を実行するために、これはCRC多項式に関係なくCRCレジスタを1に初期化することと同じです。他の実装形態では、特にCRC多項式(および外部で規定されている乗算が外部で実行される)のみを実行するだけのものは、CRCレジスタを初期化することだけである。メッセージ。このような実装では、CRC32C多項式の場合、CRCレジスタを0x2A26F826に初期化すると同じ効果があり、データの最上位32ビットを補完すると同じ効果があります。詳細については、参考資料を参照してください[Tuikov&Cavanna]。

8.4 Fast Hardware Implementation References
8.4 高速ハードウェア実装参照

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].

高速ハードウェア実装は、(7.2で提示されているものとして)、そして異なる基準に基づいてそれを最適化します。この被験者の2つの古典的な論文は[Albertengo1990]と[Glaise1997]です。より現代的な(そして体系的な)アプローチは[Shie2001]と[Sprachman2001]にあります。

9. Summary and Conclusions
9. まとめと結論

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:

次の表は、分析されたさまざまなコードのエラー検出機能の概要です。表では、Dはブロック長ブロック(ビット内)、I /バイト - ソフトウェア命令/バイト、テーブルサイズ(テーブルルックアップが必要な場合)、ルックアップ/バイト、PUDB - PUDバーストのTルック数およびPUDS - PUD Sporadic:

   +-----------------------------------------------------------+
   | 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.

上記の表における未検出の誤差の確率は、一様に分散されたデータを想定して計算されます。Real Dataの場合 - それはバイアスされる可能性があります - [Stone98]、チェックサムは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.

保護レベルを考慮すると、バイアスデータとそれが保護することができる大きなブロックの感度の欠如、CRC32Cは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.

一定の平均時間を特徴とするバーストエラーは、チャネル(マシンとネットワーク)の速度が向上するにつれて、エラー検出機能に大きな影響を与えることを確認してください。PUDを長期間の境界内に保つ唯一の方法は、より低いレベルのチャネルのより良いコーディングを使用することによってBERを減らすことです。

10. Security Considerations
10. セキュリティに関する考慮事項

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.Sisto、 "Parallel CRC世代IEEE Micro"、Vol。10、No. 5、1990年10月、PP。63-71。

[Arazi] B Arazi, "A commonsense Approach to the Theory of Error Correcting codes".

[Arazi] B Arazi、「誤り訂正符号の理論への常識的なアプローチ」。

[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ビット冗長の巡回冗長検査コードの定期誤差確率性能」、通信に関するIEEE議事録、147: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] Richard Black、1994年にwww.cl.cam.ac.uk/research/srg/bluebook/21/crc/crcによる「ソフトウェアの高速CRC32」。HTML。

[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.

[Castagnoli93] Guy Castagnoli、Stefan BraeuerとMartin Herrman "24日と32のパリティビットと32パリティビットを巡回冗長検査コードの最適化"、IEEE Transact。コミュニケーションについては、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] Floruian BraunとMarcel WaldVogel、「IP over ATMネットワークの高速インクリメンタルCRC更新」、IEEE、高性能スイッチングおよびルーティング、2001、PP。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 / docs / general / checksum / node26。HTML。

[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]藤原徹、笠見徹、そしてShu Lin、「IEEE規格802.3の販売台の検出能力の検出能力は採用された能力は採用されています。

[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の2段階計算」、IBM研究開発、第41巻、1997年。

[ieee1364] IEEE Standard Hardware Description Language Based on the Verilog Hardware Description Language, IEEE Standard 1364-1995, December 1995.

[IEEE1364] IEEEの標準的なハードウェア記述言語Verilogハードウェア記述言語、IEEE規格1364-1995、1995年12月。

[LinCostello] S. Lin and D.J. Costello, Jr., "Error Control Coding: Fundamentals and Applications", Englewood Cliffs, NJ: Prentice Hall, 1983.

[Lincostello] S. LinとD.J.Costello、Jr.、 "Error Control Coding:Fundamentalals and Applications"、NJ:Prentice Hall、1983年。

[Peterson] W Wesley Peterson & E J Weldon - Error Correcting Codes - First Edition 1961/Second Edition 1972.

[Peterson] W Wesley Peterson&E J Weldon - エラー修正コード - 初版1961 /第2版1972年。

[RFC2026] Bradner, S., "The Internet Standards Process -- Revision 3", BCP 9, RFC 2026, October 1996.

[RFC2026] Bradner、S.、「インターネット規格プロセス - リビジョン3」、BCP 9、RFC 2026、1996年10月。

[Ritter] Ritter, T. 1986. The Great CRC Mystery. Dr. Dobb's Journal of Software Tools. February. 11(2): 26-34, 76-83.

[Ritter] Ritter、T. 1986。素晴らしいCRCの謎。DOBBのソフトウェアツールのジャーナル。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 / inf / polyinfo.htmlでの「原始的および既約多項式に関する情報」。

[RFC1146] Zweig, J. and C. Partridge, "TCP Alternate Checksum Options", RFC 1146, March 1990.

[RFC1146] Zweig、J.およびC.パーリッジ、「TCP代替チェックサムオプション」、RFC 1146、1990年3月。

[RFC1950] Deutsch, P. and J. Gailly, "ZLIB Compressed Data Format Specification version 3.3", RFC 1950, May 1996.

[RFC1950] Deutsch、P.およびJ. Gailly、 "ZLIB圧縮データフォーマット仕様バージョン3.3"、RFC 1950、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.

[SHIE2001] Ming-Der Shieh、ET。AL、「並列CRC計算のための体系的なアプローチ」、情報科学誌、Vol.17 No.3、PP.445-461。

[Sprachman2001] Michael Sprachman, "Automatic Generation of Parallel CRC Circuits", IEEE Design & Test May-June 2001.

[Sprachman2001] Michael Sprachman、「並列CRC回路の自動生成」、IEEE設計&テスト2001年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. Stone et。al。、「チェックサムとCRCの実際のデータのパフォーマンス」、ネットワーキング、VOLのIEEE / ACMトランザクション。6、No. 5、1998年10月。

   [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)
        

[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.c。オオカミ、アーノルド・マイケルソンとアレン・レブスク、「線形ブロック符号の検出されていない誤差の可能性」、通信に関するIEEE取引、COM-30: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.c。Wolf、R.D. BlackNey、「特定の短縮されたバイナリCRCコードに対する未検出誤差の確率の正確な評価」、Proc。Milcom - IEEE 1988。

[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.c。Wolf and Dexter Chun、「バイナリ巡回符号の単一バーストエラー検出性能」、Commanicals Com-42:11-13、1994年1月のIEEEトランザクション。

[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.c。オオカミ、「特定のバイナリCRCコードとテスト結果の検出されないエラーの確率を計算するための特別なハードウェア」、通信のIEEEトランザクション、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&Cavanna] Luben TuikovとVicente Cavanna、「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.

私たちは、この論文を共著し、主題に関する役立つ議論のために、アジレントとの彼の雇用中に、マットワークレイに提供してくれてありがとう。

13. Authors' Addresses
13. 著者の住所

Julian Satran IBM, Haifa Research Lab MATAM - Advanced Technology Center Haifa 31905, Israel EMail: julian_satran@il.ibm.com

Julian Satran IBM、Haifa Research Lab Matam - Advanced Technology Center Haifa 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、Haifa Research Lab Matam - Advanced Technology Center Haifa 31905、イスラエルEメール: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

Pat Saler Agilent Technologies 1101 Creekside Ridge Drive Suite 100、M / S RH21ローズビル、CA 95661 Eメール:PAT_THALER@AGIENT.com

Vicente Cavanna Agilent Technologies 1101 Creekside Ridge Drive Suite 100, M/S RH21 Roseville, CA 95661 EMail: vince_cavanna@agilent.com

Vicente Cavanna Agilent Technologies 1101 Crekside Ridge Drive Suite 100、M / S RH21ローズビル、CA 95661 Eメール:vince_cavanna@agilent.com

14. Full Copyright Statement
14. 完全著作権宣言

Copyright (C) The Internet Society (2002). All Rights Reserved.

著作権(c)インターネット社会(2002)。全著作権所有。

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.

この文書と翻訳はコピーされている可能性があり、他の文書にはコピーされ、その実装を説明するか、またはその実装を説明するか、またはその実装を支援することができます。上記の著作権通知とこの段落がそのようなすべてのコピーや派生的な作品に含まれているとしました。ただし、この文書自体は、インターネット規格を開発するために必要な場合を除き、インターネット社会や他のインターネット組織への参照を削除するなど、著作権社会やその他のインターネット組織への参照を除去することはできません。インターネット標準プロセスに従う必要があるか、それを英語以外の言語に翻訳する必要があります。

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エディタ機能のための資金は、現在インターネット社会によって提供されています。