124

たぶん私はそれを見ていないだけかもしれませんが、CRC32 は不必要に複雑であるか、Web 上で見つけることができる場所では説明が不十分なようです。

メッセージ値を (生成) 多項式で割った非桁上げベースの算術除算の余りであることは理解していますが、実際の実装については理解できません。

A Painless Guide To CRC Error Detection Algorithms を読みましたが、それは無痛ではなかったと言わざるを得ません。理論はかなりうまく説明されていますが、著者は単純な「これだ」とは決して言いません。彼は、標準の CRC32 アルゴリズムのパラメータが何であるかを述べていますが、どのようにそれに到達するかを明確に説明することを怠っています。

私を惹きつけるのは、彼が「これだ」と言い、「ちなみに、逆にすることも、異なる初期条件で開始することもできます」と付け加えたときです。彼が追加したばかりのすべての変更を考慮して、CRC32 チェックサムを計算します。

  • CRC32 の計算方法の簡単な説明はありますか?

テーブルがどのように形成されるかをCでコーディングしようとしました：

for (i = 0; i < 256; i++)
{
    temp = i;

    for (j = 0; j < 8; j++)
    {
        if (temp & 1)
        {
            temp >>= 1;
            temp ^= 0xEDB88320;
        }
        else {temp >>= 1;}
    }
    testcrc[i] = temp;
}

しかし、これは私がインターネット上の他の場所で見つけた値と矛盾する値を生成するようです. オンラインで見つけた値を使用できますが、それらがどのように作成されたかを理解したいです。

これらの信じられないほど紛らわしい数字を解決するための助けをいただければ幸いです.

4

7 に答える 7

142

CRC32の多項式は次のとおりです。

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

または16進数と2進数：

0x 01 04 C1 1D B7
1 0000 0100 1100 0001 0001 1101 1011 0111

最高の用語（x 32）は通常、明示的に記述されていないため、代わりに16進数で次のように表すことができます。

0x 04 C1 1D B7

1と0を自由に数えますが、これらは多項式と一致していることがわかります。ここで、1はビット0（または最初のビット）であり、xはビット1（または2番目のビット）です。

なぜこの多項式なのか？多項式が与えられた標準が必要であり、標準はIEEE802.3によって設定されたためです。また、さまざまなビットエラーを効果的に検出する多項式を見つけることは非常に困難です。

CRC-32は、一連の「キャリーのない2進演算」、または基本的に「XORおよびシフト演算」と考えることができます。これは、技術的には多項式の算術と呼ばれます。

それをよりよく理解するために、この乗算について考えてください。

(x^3 + x^2 + x^0)(x^3 + x^1 + x^0)
= (x^6 + x^4 + x^3
 + x^5 + x^3 + x^2
 + x^3 + x^1 + x^0)
= x^6 + x^5 + x^4 + 3*x^3 + x^2 + x^1 + x^0

xが2を底とする場合、次のようになります。

x^7 + x^3 + x^2 + x^1 + x^0

なんで？3x^3は11x^11であるため（ただし、1桁または0桁の前桁のみが必要です）、次のように引き継ぎます。

=1x^110 + 1x^101 + 1x^100          + 11x^11 + 1x^10 + 1x^1 + x^0
=1x^110 + 1x^101 + 1x^100 + 1x^100 + 1x^11 + 1x^10 + 1x^1 + x^0
=1x^110 + 1x^101 + 1x^101          + 1x^11 + 1x^10 + 1x^1 + x^0
=1x^110 + 1x^110                   + 1x^11 + 1x^10 + 1x^1 + x^0
=1x^111                            + 1x^11 + 1x^10 + 1x^1 + x^0

しかし、数学者はそれがmod 2になるように規則を変更しました。したがって、基本的に、2進多項式mod 2は、キャリーやXORなしで加算されます。したがって、元の方程式は次のようになります。

=( 1x^110 + 1x^101 + 1x^100 + 11x^11 + 1x^10 + 1x^1 + x^0 ) MOD 2
=( 1x^110 + 1x^101 + 1x^100 +  1x^11 + 1x^10 + 1x^1 + x^0 )
= x^6 + x^5 + x^4 + 3*x^3 + x^2 + x^1 + x^0 (or that original number we had)

私はこれが信仰の飛躍であることを知っていますが、これはラインプログラマーとしての私の能力を超えています。あなたがハードコアのCS学生またはエンジニアである場合、私はこれを分解することに挑戦します。誰もがこの分析の恩恵を受けるでしょう。

したがって、完全な例を作成するには、次のようにします。

   Original message                : 1101011011
   Polynomial of (W)idth 4         :      10011
   Message after appending W zeros : 11010110110000

ここで、CRC演算を使用して、拡張メッセージをポリで除算します。これは以前と同じ区分です。

            1100001010 = Quotient (nobody cares about the quotient)
       _______________
10011 ) 11010110110000 = Augmented message (1101011011 + 0000)
=Poly   10011,,.,,....
        -----,,.,,....
         10011,.,,....
         10011,.,,....
         -----,.,,....
          00001.,,....
          00000.,,....
          -----.,,....
           00010,,....
           00000,,....
           -----,,....
            00101,....
            00000,....
            -----,....
             01011....
             00000....
             -----....
              10110...
              10011...
              -----...
               01010..
               00000..
               -----..
                10100.
                10011.
                -----.
                 01110
                 00000
                 -----
                  1110 = Remainder = THE CHECKSUM!!!!

除算により、破棄する商と、計算されたチェックサムである剰余が生成されます。これで計算は終了です。通常、チェックサムはメッセージに追加され、結果が送信されます。この場合、送信は11010110111110になります。

除数として32ビットの数値のみを使用し、配当としてストリーム全体を使用します。商を捨て、余りを残します。メッセージの最後に残りをタックすると、CRC32が作成されます。

平均的な男のレビュー：

         QUOTIENT
        ----------
DIVISOR ) DIVIDEND
                 = REMAINDER
  1. 最初の32ビットを取ります。
  2. シフトビット
  3. 32ビットがDIVISOR未満の場合は、手順2に進みます。
  4. DIVISORによるXOR32ビット。手順2に進みます。

（ストリームは32ビットで分割可能であるか、パディングする必要があることに注意してください。たとえば、8ビットANSIストリームはパディングする必要があります。また、ストリームの最後で、分割が停止します。）

于 2011-01-27T00:21:32.073 に答える
11

CRC は非常に単純です。ビットとデータとして表される多項式を取り、多項式をデータに分割します (または、データを多項式として表して同じことを行います)。0 と多項式の間の剰余が CRC です。あなたのコードは、部分的に不完全であるため、理解するのが少し難しいです。

CRC を理解する方法は、短いデータ (16 ビット程度) と短い多項式 (おそらく 4 ビット) を使用して、いくつかの計算を試みることです。このように練習すれば、どのようにコーディングすればよいかを本当に理解できるようになります。

頻繁に実行している場合、CRC はソフトウェアで計算するのが非常に遅くなります。ハードウェア計算ははるかに効率的で、必要なゲート数はわずかです。

于 2010-04-06T19:56:05.203 に答える
8

ウィキペディアのCyclic redundancy checkとComputation of CRC の記事に加えて、 Reversing CRC - Theory and Practice *というタイトルの論文が参考になると思います。

CRC の計算には、代数的アプローチ、ビット指向アプローチ、およびテーブル駆動型アプローチの 3 つの基本的なアプローチがあります。Reversing CRC - Theory and Practice *では、これら 3 つのアルゴリズム/アプローチのそれぞれについて、C プログラミング言語での CRC32 の実装による APPENDIX を伴う理論で説明されています。

* PDF リンク
CRC を逆にする – 理論と実践。
HU ベルリン公開レポート
SAR-PR-2006-05
2006 年 5 月
著者:
Martin Stigge、Henryk Plötz、Wolf Müller、Jens-Peter Redlich

于 2011-01-27T03:55:43.337 に答える
2

次に、数十のコンピューター言語で実装された crc32 を示す Rosetta Code が常にあります。https://rosettacode.org/wiki/CRC-32には、多くの説明と実装へのリンクがあります。

于 2020-04-15T00:46:55.713 に答える