Keajaiban CRC – Teknik Deteksi Kesalahan


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

Cyclic Redundancy Check (atau CRC), adalah cara untuk mendeteksi kesalahan dalam penyimpanan data atau transmisi. Dengan data yang lebih banyak dan lebih sedang dikirim melalui saluran telepon, kebutuhan untuk protokol yang melindungi data dari kerusakan dalam perjalanan meningkat, tetapi teori di balik generasi CRC tidak banyak dikenal.

Cyclic Redundancy Check (CRC) adalah suatu cara untuk mendeteksi perubahan kecil dalam blok data. Deteksi kesalahan sangat penting ketika program komputer yang dikirim atau disimpan, karena kesalahan bahkan satu bit (mungkin karena ratusan ribu) seringkali cukup untuk membuat suatu program rusak. Meskipun beberapa kesalahan dalam sebuah file teks mungkin dapat diterima (karena teks bisa diedit ulang waktu diterima atau direstore), file bebas error adalah lebih baik. Sebuah protokol error-correcting dipicu oleh CRC-deteksi kesalahan dapat memberikan akurasi dengan biaya rendah.

Algoritma CRC beroperasi pada blok data sebagai unit. Kita dapat memahami CRC lebih baik jika kita melihat blok data sebagai nilai numerik (besar) tunggal. Algoritma CRC membagi nilai besar ini dengan angka magic (polinomial CRC atau polinomial generator), memberikan sisanya, yang merupakan hasil CRC.

Hasil CRC dapat dikirim atau disimpan bersama dengan data asli. Ketika data diterima (atau dipulihkan dari penyimpanan) algoritma CRC dapat diterapkan kembali, dan hasil terbaru dibandingkan dengan hasil asli. Jika error telah terjadi, kita mungkin akan mendapatkan hasil CRC yang berbeda. Kebanyakan penggunaan CRC tidak berusaha untuk mengklasifikasikan atau mencari kesalahan (atau error), tetapi hanya mengatur untuk mengulang operasi data sampai tidak ada kesalahan yang terdeteksi.

Spesifikasi IBM disk 8-inch floppy menggunakan polinomial CRC-CCITT untuk deteksi kesalahan, dan CRC ini sekarang digunakan di hampir semua perangkat disk controller. Sebuah disk controller menghitung CRC saat menulis sebuah sektor disk, dan kemudian menambahkan CRC ini dengan data. Ketika data itu dibaca kembali, CRC baru dihitung dari data yang ditemukan dan dibandingkan dengan CRC asli. Jika nilai CRC berbeda, error telah terjadi dan operasi diulang. Disk standar CRC (CRC-CCITT) disembunyikan dalam controller, dan saat ini menerima sedikit komentar.

Salah satu versi protokol transmisi file  XMODEM (atau Christensen) menggunakan polinomial CRC-CCITT untuk mendeteksi kesalahan transmisi data, biasanya disebabkan oleh noise line. Ketika penerima mendeteksi kesalahan data, mengirimkan sebuah karakter NAK (Negatif Acknowledge) ke pengirim, yang meminta bahwa blok data akan ditransmisikan kembali. Sisi penerima mengulangi proses ini sampai CRC dari ujung transmisi sesuai dengan hasil lokal, atau satu sampai atau kedua ujung berhenti. Bila hasilnya tidak cocok, maka penerima mengirimkan karakter ACK (Acknowledge), dan transmisi berakhir kemudian mengirimkan blok berikutnya.

Banyak polynomial CRC polinomial yang tersedia dan mungkin berbeda; generator polinomial ini didesain dan dibangun untuk memiliki sifat diharapkan mendeteksi kesalahan. Jika polinomial CRC “dibangun dengan baik” perbedaan utama antara mereka adalah panjang mereka. Polinomial yang lebih panjang lebih memberikan jaminan akurasi data dan sepenuhnya dapat digunakan lebih pada jumlah yang lebih besar data, namun, polinomial lebih panjang juga menghasilkan nilai sisa panjang, yang menambah overhead tambahan pengecekan error pada data.

A “16-bit” polinomial memiliki sisa 16-bit. Ada dua polinomial 16-bit terkenal: CRC-16 (yang digunakan dalam protokol BISYNC awal) dan CRC-CCITT (digunakan dalam penyimpanan disk, SDLC, dan XMODEM CRC). Dari keduanya, CRC-CCITT mungkin sedikit lebih kuat, dan, dengan konvensi ini sering digunakan dalam cara yaitu memperkuat kemampuan deteksi kesalahan. Artikel ini menggambarkan CRC-CCITT, yang merupakan polinomial x ^ 16 + x ^ 12 + x ^ 5 + 1.

Polinomial diklasifikasikan oleh digit non-zero (tempat) tertinggi yang disebut derajat polinomial tersebut. Baik-CRC 16 dan CRC-CCITT adalah 16 derajat, yang berarti bahwa bit 16 sampai 0 adalah signifikan dalam deskripsi mereka, sebuah derajat 16 polinomial akan memiliki 17 bit. Biasanya kita paling berkonsentrasi dengan sisa operasi CRC, yang memiliki satu bit kurang dari polinomial itu. Jadi, kita mungkin berpikir CRC 16-bit, meskipun generator polinomial mereka benar-benar berisi 17 bit (bit 16 sampai 0).

Dalam polinomial CRC yang tepat, baik most significant bit (MSB) dan least significant bit (LSB) selalu menjadi ‘1 ‘. Karena bit tertinggi polinomial ini selalu ‘1 ‘, kita dapat memperlakukan bit ini berbeda dari bit yang lain polinomial tersebut. Karena sisanya dari 16 derajat polinomial hanya mempunyai16 bit, register 16-bit cukup untuk operasional CRC pada polinomial 16-bit, meskipun polinomial itu sendiri sebenarnya memiliki 17 bit.

Sebuah polinomial CRC yang dikonstruksi dengan baik di atas blok data dengan ukuran terbatas akan mendeteksi ledakan contiguous error lebih pendek dari polinomial, berapapun jumlah kesalahan ganjil di seluruh blok, sembarang 2 bit error di mana saja dalam blok, dan kasus lainnya dari kemungkinan kesalahan mana saja dalam data. Maka setiap pengaturan kemungkinan 1, 2 atau 3 bit error akan terdeteksi. Namun demikian, tetap ada kemungkinan kecil bahwa beberapa kesalahan tidak akan terdeteksi. Hal ini terjadi ketika pola hasil kesalahan dalam nilai baru yang ketika dibagi, menghasilkan sisanya tepat sama sebagai blok yang benar. Dengan konstruksi CRC 16-bit yang benar, ada rata-rata satu pola kesalahan yang tidak akan terdeteksi untuk setiap 65.535 yang akan dideteksi. Yaitu, dengan CRC-CCITT, kita seharusnya deteksi dapat mendeteksi 65535/65536t hs atau 99,998 persen dari semua kesalahan yang mungkin.

Tidak ada teknik yang bisa kita gunakan dapat benar-benar menjamin deteksi kesalahan, tetapi kita bisa meminimalkan kesalahan yang tidak terdeteksi dengan biaya murah. Teknik deteksi kesalahan yang lain yang tersedia, seperti checksum atau voting, tapi ini memiliki kemampuan lebih buruk data deteksi error. Sebagai contoh, checksum single-byte (digunakan dalam versi asli XMODEM) tampak sekitar 99,29 persen akurat, yang tampaknya cukup bagus. Tapi untuk byte tambahan tunggal, teknik CRC adalah sekitar 460 kali lebih kecil kemungkinannya untuk membiarkan error yang lewat tidak terdeteksi. Dalam prakteknya, perbedaannya jauh lebih besar karena CRC akan mendeteksi semua kasus hanya beberapa kesalahan, dan kasus-kasus ini yang paling umum. Biaya adalah 2-byte nilai CRC dalam setiap blok. Sebagai contoh, protokol XMODEM mengirimkan data dalam blok 128-byte, blok ini bisa mendeteksi error CRC dengan dua byte tambahan – untuk overhead error check sekitar 1,5 persen.

Polynomial codes for error detection

Also called CRC (Cyclic Redundancy Check)
Data is sent with a checksum.
When arrives, checksum is recalculated. Should match the one that was sent.

Bitstring represents polynomial.
e.g. 110001 represents:
1 . x5 + 1 . x4 + 0 . x3 + 0 . x2 + 0 . x1 + 1 . x0
= x5 + x4 + x0

The order of a polynomial is the power of the highest non-zero coefficient. This is polynomial of order 5.

Modulo 2 arithmetic

We are going to define a particular field (or here), in fact the smallest field there is, with only 2 members.

We define addition and subtraction as modulo 2 with no carries or borrows.
This means addition = subtraction = XOR.
Here’s the rules for addition:

0 + 0 = 0 
0 + 1 = 1
1 + 0 = 1 
1 + 1 = 0

Multiplication:

0 * 0 = 0 
0 * 1 = 0
1 * 0 = 0 
1 * 1 = 1

Subtraction: if 1+1=0, then 0-1=1, hence:

0 - 0 = 0 
0 - 1 = 1
1 - 0 = 1 
1 - 1 = 0

Long division is as normal, except the subtraction is modulo 2.

Example

No carry or borrow:

011 + (or minus)
110
---
101

Consider the polynomials:

x + 1 +
x2 + x
————-
x2 + 2x + 1
= x2 + 1

We’re saying the polynomial arithmetic is modulo 2 as well, so that:

2 xk = 0

for all k.

What does this mean?

Just consider this as a set of rules which, if followed, yield certain results.

When the checksum is re-calculated by the receiver, we should get the same results.

All sorts of rule sets could be used to detect error.

It is useful here that the rules define a well-behaved field.

Consider the polynomials with x as isomorphic to binary arithmetic with no carry.
It is just easier to work with abstract x so we don’t make the mistake of starting to add, say. 3 x3 to get x4 + x3 if we were thinking of x=2.
We work in abstract x and keep “the coefficients of each power nicely isolated” (in mod 2, when we add two of same power, we get zero, not another power).


multiplication

Multiply 110010 by 1000
Multiply (x5 + x4 + x) by x3
= x8 + x7 + x4
= 110010000
i.e. Just add 3 zeros

In general, to multiply by xk, add k zeros.

division

x2 + 1 = (x+1)(x+1)
(since 2x=0)

Do long division:
Divide (x+1) into x2 + 1
Divide 11 into 101
Subtraction mod 2
Get 11, remainder 0

11 goes into 10 once, remainder 1
A goes into B if it has the same number of bits

Polynomial factors and primes

If a polynomial has no factors other than 1 and itself, it is a prime polynomial or an Irreducible Polynomial.
x2 + 1 (= 101) is not prime
This is not read as “5”, but can be seen as the “5th pattern” when enumerating all 0,1 patterns.

Polynomial primes do not correspond to integer primes.

Note any bitstring ending in 0 represents a polynomial that is not prime since it has x as a factor (see above).
All primes look like 1….1

Error detection with CRC

Consider a message 110010 represented by the polynomial M(x) = x5 + x4 + x
Consider a generating polynomial G(x) = x3 + x2 + 1 (1101)
This is used to generate a 3 bit CRC = C(x) to be appended to M(x).
Note this G(x) is prime.

Steps:

  1. Multiply M(x) by x3 (highest power in G(x)). i.e. Add 3 zeros. 110010000
  2. Divide the result by G(x). The remainder = C(x).
    1101 long division into 110010000 (with subtraction mod 2)
    = 100100 remainder 100

Special case: This won’t work if bitstring = all zeros. We don’t allow such an M(x).
But M(x) bitstring = 1 will work, for example. Can divide 1101 into 1000.

If: x div y gives remainder c
that means: x = n y + c
Hence (x-c) = n y
(x-c) div y gives remainder 0
Here (x-c) = (x+c)
Hence (x+c) div y gives remainder 0
110010000 + 100 should give remainder 0.

  1. Transmit 110010000 + 100
    To be precise, transmit: T(x) = x3M(x) + C(x)
    = 110010100
  2. Receiver end: Receive T(x). Divide by G(x), should have remainder 0.

Note if G(x) has order n – highest power is xn,
then G(x) will cover (n+1) bits
and the remainder will cover n bits.
i.e. Add n bits to message.

Example

Another example of calculating CRC.
3rd line should read 11010110110000
Transmit: 11010110111110
Here G(x) = x4+x+1 which is prime.

Errors

An error is the same as adding some E(x) to T(x)
e.g. add 1010011000001110000
will flip the bits at the locations where “1” is in the error bitstring.
Instead of T(x) arriving, T(x)+E(x) arrives.

In general, each 1 bit in E(x) corresponds to a bit that has been flipped in the message.
If there are k 1 bits in E(x), k single-bit errors have occurred.
A burst error looks like 1….1


Detecting errors

Far end receives T(x)+E(x)
T(x) is multiple of G(x) (remainder zero)
Hence remainder when you divide (T(x)+E(x)) by G(x)
= remainder when you divide E(x) by G(x)

e.g. remainder when divide (1000+n) by 10
= remainder when you divide n by 10

If remainder when you divide E(x) by G(x) is zero, the error will not be detected.

In general, if you are unlucky enough that E(x) is a multiple of G(x), the error will not be detected.
Otherwise, it will. All other error patterns will be caught.

1 bit error

A 1 bit error is the same as adding E(x) = xk to T(x)
e.g. add 0000001000000000000
will flip the bit at that location only.

Is this detected?
The remainder when you divide E(x) by G(x) is never zero with our prime G(x) = x3 + x2 + 1
because E(x) = xk has no prime factors other than 1 and x.
Hence error detected.

In general, if G(x) is not equal to xi for any i (including 0)
then all 1 bit errors will be detected.


2 adjacent bit errors

E(x) = xk + xk+1
= xk (x+1)
Prime factors x,(x+1)
Not divisible by our prime G(x) = x3 + x2 + 1

In general, if G(x) is not equal to xi for any i (including 0)
or xi(x+1) for any i (including 0)
then all 2 adjacent bit errors detected.

Any 2 bit error

E(x) = xi + xj where i > j (to its left)
= xj (xi-j + 1)

Detected if (xk+1) cannot be divided by G(x) for any k up to frame length.

For example, it is true (though no proof provided here) that G(x) = x15+x14+1 will not divide into any (xk+1) for k < 32768
Hence can add 15 bits to each block of 32 k bits and can detect any 1-bit or 2-bit error.
This G(x) represents 1100000000000001. This is prime.

If G(x) will not divide into any (xk+1) for k up to the frame length, then all 2 bit errors will be detected.

Odd no. of errors

First note that (x+1) multiplied by any polynomial can’t produce a polynomial with an odd number of terms:

  • e.g. (x+1) (x7+x6+x5)
    = x8+x7+x6 +
    x7+x6+x5
    = x8+x5
  • In general,
    (x+1) ( xp1+…+xpn )
    = xp1+1+…+xpn+1 +
    xp1+…+xpn
    If all these powers are different – even no. of terms.
    If any pair pi = pj+1, these cancel out, still even no. of terms.
    Can’t get 3 the same power (why not?)

So if there are an odd no. of errors, E(x) contains an odd no. of terms.
E(x) can’t be divided by (x+1)
If we make G(x) not prime but a multiple of (x+1), then E(x) can’t be divided by G(x).
Can detect all odd no. of errors.

e.g. CRC-8 = x8+x2+x+1 (=100000111) which is not prime.
See its factors.
It equals (x+1) (x7+x6+x5+x4+x3+x2+1)

If G(x) is a multiple of (x+1) then all odd no. of errors are detected.

Burst of length k

[good bits][burst start]….[burst end][good bits]
… [burst lhs at xi+k-1] …. [burst rhs at xi] ….
E(x) = xi+k-1 + … + xi
= xi ( xk-1 + … + 1 )
If G(x) contains a +1 term, it will not have xi as a factor. If also G(x) is of order k or greater, then:
( xk-1 + … + 1 ) / G(x) is a fraction, and xi cannot cancel out, so
xi ( xk-1 + … + 1 ) / G(x) can’t give remainder 0.

If G(x) contains a +1 term and has order n (highest power is xn) it detects all burst errors of up to and including length n.


Burst of length k+1

Where G(x) is order k.
E(x) = xi ( xk + … + 1 )
( xk + … + 1 ) is only divisible by G(x) if they are equal.
i.e. The burst pattern of k+1 bits = the G(x) pattern of k+1 bits.
By definition, burst starts and ends with 1, so whether it matches depends on the (k+1)-2 = k-1 intermediate bits.
This matches G(x) by chance with probability (1/2)k-1

If G(x) contains a +1 term and has order n, the chance of it failing to detect a burst of length n+1 is (1/2)n-1

Some CRC polynomials that are actually used

Some CRC polynomials

  • CRC-8:
    x8+x2+x+1
    • [Factors] = (x+1) (x7+x6+x5+x4+x3+x2+1)
    • Used in: 802.16 (along with error correction).
  • CRC-CCITT:
    x16+x12+x5+1
  • IBM-CRC-16 (ANSI):
    x16+x15+x2+1
  • 802.3:
    x32+x26+x23+x22 +x16+x12+x11+x10 +x8+x7+x5+x4+x2+x+1
    • [Factors] = Prime
    • Append 32 bits to the message.
    • Detects all bursts of length 32 or less.
    • Probability of not detecting burst of length 33 = (1/2)31 = 1 in 2 billion. And remember, won’t get such a burst on every message. Burst itself very rare.
    • Used in: Ethernet, PPP option

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: