CRC対チェックサム
1. 序章
コンピュータネットワークを使用すると、あるデバイスから別のデバイスにデータを転送できます。 データ転送を成功させるには、ターゲットシステムがソースシステムから送信されたものと同じデータを受信する必要があります。 ただし、あるノードから別のノードに転送するときにデータが破損する可能性があります。 巡回冗長検査(CRC)とチェックサムは、データ破損を検出するための2つの一般的なメカニズムです。
この記事では、これら2つの一般的な手法、それらがどのように機能するか、およびそれらの長所と短所について説明します。
2. エラーの種類
データ破損エラーは、送信中に変更されたビット数に基づいて分類されます。 干渉が原因で変化が発生し、信号の形状が変化する可能性があります。 これらのエラーは2つのカテゴリに分類されます。
2.1. シングルビットエラー
データバイトの1ビットに変更があるとシングルビットエラーが発生します:
2.2. バーストエラー
データバイトの複数のビットに変更があると、バーストエラーが発生します。
3. 巡回冗長検査とは何ですか?
巡回冗長検査(CRC)は、送信データの偶発的な変更を検出できるエラー検出コードです。 これらの単語が何を指すかを定義しましょう:
- Cyclic :巡回コードに基づいており、CRCはこの用語を導き出します
- 冗長性:データの正確性を検証するためにデータに追加されるチェック値
宛先では、受信データがチェック値(除数)で除算されます。 余りがゼロの場合、データ単位は有効であると見なされ、受け入れられます。 ゼロ以外の余りは、データが破損しているため、拒否する必要があることを示します。 送信機のCRCチェッカーと受信機のCRCジェネレーターは同じように機能します。
3.1. CRCはどのように機能しますか?
CRC は、モジュロ2除算に基づいて動作し、排他的論理和演算によって加算が実行されます。 排他的論理和演算では、減算演算は加算演算と同じです。 これは、 1 + 1 = 0 のように、2つの1ビットを追加すると0になることを意味します。
また、CRCでは、送信データユニットの末尾に冗長ビットのシーケンスが付加されます。 これは、CRC剰余とも呼ばれます。 したがって、結果のデータ単位は、事前に決定された2進数(除数)で正確に割り切れます。
CRCジェネレーターの除数は、代数多項式で表されます。 0と1の文字列は、係数が0と1の多項式として表されます。 多項式の各項の累乗はビットの位置を示し、対応する係数はビットの値(0または1)を反映します。 多項式は、係数がゼロのすべての項を削除することで表されます。 送信側と受信側の両方の例を使用して、計算について説明しましょう。
3.2. 送信側でのCRC計算
この例では、多項式 x3 + x +1を使用して3ビットCRCで14ビットメッセージをエンコードします。 3次多項式には、4つの係数( 1×3 + 0x2 + 1x + 1 )があります。 この場合、係数は1、0、1、および1です。 計算結果は3ビット長です。
送信する必要のあるメッセージから始めましょう。11010011101100これが3ビットCRCを計算するための最初の計算です。
11010011101100 000 <--- Data padded by 3 bits of 0s on the right side 1011 <--- Divisor (4 bits) = x³ + x + 1 ------------------ 01100011101100 000 <--- Result
それでは、完全な計算を示しましょう。
11010011101100 000 <--- Data padded by three bits of 0s on the right side 1011 <--- Divisor (four bits) = x³ + x + 1 01100011101100 000 <--- Result (First four bits are XORed with the divisor, rest of the bits are unchanged) 1011 <--- Divisor ... 00111011101100 000 1011 00010111101100 000 1011 00000001101100 000 <--- Divisor moves over to align with the next 1 in the dividend (since quotient for that step was zero) 1011 00000000110100 000 1011 00000000011000 000 1011 00000000001110 000 1011 00000000000101 000 101 1 ----------------- 00000000000000 100 <--- remainder (three bits). Division algorithm stops here as dividend is equal to zero.
3.3. 受信機側でのCRC計算
受信したメッセージの有効性は、上記の計算を再度実行することで簡単に確認できます。今回は、ゼロの代わりにチェック値を追加します。 検出可能なエラーがない場合、余りはゼロに等しくなります。
11010011101100 100 <--- Input with the check value 1011 <--- Divisor 01100011101100 100 <--- Result 1011 <--- Divisor 00111011101100 100 ...... 00000000001110 100 1011 00000000000101 100 101 1 ------------------ 00000000000000 000 <--- Remainder
余りの値0は、受信したデータが正しく、受け入れることができることを示します。
ここで、受信したデータに送信エラーがあり、1ビットが反転した例を見てみましょう。 したがって、排他的論理和演算はゼロ以外の剰余を生成します。
11010011101101 100 <--- input with check value 1011 <--- divisor 01100011101101 100 <--- result 1011 <--- divisor ... 00111011101101 100 ...... 00000000001111 100 1011 00000000000100 100 101 1 ------------------ 00000000000001 000 1 011 ------------------ 00000000000000 011 <--- remainder
4. チェックサムとは何ですか?
チェックサムは、送信されたデータの整合性を検証するもう1つのエラー検出手法です。 チェックサム値は、一連の数字と文字で構成されます。 チェックサムを計算するために、そのファイルをハッシュ関数に通すプログラムを実行します。 頻繁に使用されるアルゴリズムは、MD5、SHA-1、 SHA-256 、およびSHA-512です。
ハッシュ関数は入力を受け取り、固定長の文字列を生成します。 同じ入力に対して、ハッシュ関数は常に同じチェックサム値を返します。 ただし、入力データにわずかな変化がある場合、チェックサム値は大きく異なります。
4.1. チェックサムを計算する方法は?
ファイルのチェックサムを計算する方法はいくつかあります。 たとえば、ほとんどのプログラミング言語は、チェックサムを計算できるAPIを提供します。 ほとんどのオペレーティングシステムは、チェックサム値をすばやく計算できるユーティリティも提供しています。 たとえば、Linuxには、ファイルのチェックサムを計算するためのcksumユーティリティが用意されています。 Windowsでは、 PowerShellは、ファイルのチェックサムを計算するためのGet-FileHashコマンドを提供します。
Get-FileHash C:\baeldung\Hello.txt
Get-FileHash出力には、アルゴリズム名、チェックサム値、およびファイルの場所が含まれます。
Algorithm Hash Path
--------- ---- ----
SHA256 45356929829DC9FDED17E755DB91B93C25A4ED3FB9D60D92D4BD1E935A0ECC75 C:\baeldung\Hello.txt
上記のPowerShellコマンドは、Hello.txtファイルのチェックサムを計算します。 デフォルトでは、SHA256アルゴリズムを使用します。 別のアルゴリズムを使用するには、-Algorithm引数を使用して指定できます。
Get-FileHash C:\baeldung\Hello.txt -Algorithm SHA512
get-FileHashの出力には、同じファイルの変更されたアルゴリズム名とチェックサム値が表示されます。
Algorithm Hash Path
--------- ---- ----
SHA512 3B6FC410AAC9453DF953A84E806FF789A88549AD35DBB6EA30C832AF32316AC4832... C:\baeldung\Hello.txt
5. 概要
さまざまな側面でCRCとチェックサムの比較を要約してみましょう。
領域 | CRC | チェックサム |
---|---|---|
目的 | ソースマシンとターゲットマシン間のデータ伝送エラーを検出します。 | ソフトウェアアプリケーションは、チェックサムを使用してデータの整合性を計算します |
エラー検出 | 2桁のエラーを検出できます | シングルビットエラーを検出できます |
複雑 | 複雑な関数を使用してエラーを検出します | 比較的複雑でない関数を使用します |
信頼性 | CRCの計算に使用する数式により、チェックサムよりも信頼性が高くなります | CRCよりも信頼性が低い |
存在 | 比較的新しい–チェックサムよりも改善 | チェックサムは古い概念です |
6. 結論
この記事では、データ送信中に使用される2つの主要なエラー検出技術について説明しました。 まず、CRCから始めて、それがどのように機能するかを説明しました。 次に、チェックサムについて話し、それを計算するためのいくつかの手段を示しました。
最後に、CRCとチェックサムのいくつかの重要な属性の簡単な要約を提供しました。