CRC (Cyclic Redudancy Check)

CRC (Cyclic Redundancy Check) adalah algoritma untuk memastikan integritas data dan mengecek kesalahan pada suatu data yang akan ditransmisikan atau disimpan.

Data yang hendak ditransmisikan atau disimpan ke sebuah media penyimpanan rentan sekali mengalami kesalahan, seperti halnya noise yang terjadi selama proses transmisi atau memang ada kerusakan perangkat keras. Untuk memastikan integritas data yang hendak ditransmisikan atau disimpan, CRC dapat digunakan. CRC bekerja secara sederhana, yakni dengan menggunakan perhitungan matematika terhadap sebuah bilangan yang disebut sebagai Checksum, yang dibuat berdasarkan total bit yang hendak ditransmisikan atau yang hendak disimpan.

Dalam transmisi jaringan, khususnya dalam jaringan berbasis teknologi Ethernet, checksum akan dihitung terhadap setiap frame yang hendak ditransmisikan dan ditambahkan ke dalam frame tersebut sebagai informasi dalam header atau trailer. Penerima frame tersebut akan menghitung kembali apakah frame yang ia terima benar-benar tanpa kerusakan, dengan membandingkan nilai frame yang dihitung dengan nilai frame yang terdapat dalam header frame. Jika dua nilai tersebut berbeda, maka frame tersebut telah berubah dan harus dikirimkan ulang.

CRC didesain sedemikian rupa untuk memastikan integritas data terhadap degradasi yang bersifat acak dikarenakan noise atau sumber lainnya (kerusakan media dan lain-lain). CRC tidak menjamin integritas data dari ancaman modifikasi terhadap perlakukan yang mencurigakan oleh para hacker, karena memang para penyerang dapat menghitung ulang checksum dan mengganti nilai checksum yang lama dengan yang baru untuk membodohi penerima

Redundansi siklik Periksa

Error detection is important whenever there is a non-zero chance of your data getting corrupted. Deteksi error adalah penting jika ada kesempatan bukan nol mendapatkan data Anda rusak. Apakah itu sebuah paket Ethernet atau file di bawah kendali aplikasi Anda, Anda dapat menambahkan sepotong informasi berlebihan untuk memvalidasi itu.

Contoh paling sederhana adalah bit paritas. Banyak komputer menggunakan satu bit paritas per byte dari memori. Setiap kali byte yang ditulis, komputer menghitung jumlah nol non-bit di dalamnya. Jika jumlah genap, ia menetapkan kesembilan bit paritas, selain itu, membersihkan itu. Ketika membaca byte, komputer menghitung jumlah nol non-bit di dalam byte, ditambah bit paritas. Jika salah satu dari sembilan membalik bit, jumlah akan menjadi aneh dan komputer akan berhenti dengan kesalahan memori. (Tentu saja, jika dua bit membalik - yang lebih jarang terjadi - sistem ini tidak akan mendeteksi itu.)

Untuk pesan lebih dari satu byte, Anda ingin menyimpan lebih dari satu sedikit informasi berlebihan. Anda mungkin, misalnya, menghitung checksum. Tambahkan bersama semua byte dalam pesan dan append (atau simpan di tempat lain) jumlah. Biasanya jumlah dipotong untuk, katakanlah, 32 bit. Sistem ini akan mendeteksi banyak jenis korupsi dengan probabilitas yang wajar. Ini akan, bagaimanapun, gagal buruk ketika pesan tersebut dimodifikasi dengan membalik atau kelompok bertukar byte. Juga, ia akan gagal jika Anda menambah atau menghapus null byte.

Siklik redundansi menghitung Periksa yang jauh lebih kuat algoritma pengecekan error. Pada artikel ini saya akan sketsa dasar-dasar matematika CRC perhitungan dan menggambarkan dua C + + implementasi - pertama yang lambat tapi sederhana, maka lebih dioptimalkan satu.

Polynomials Polinomial

Here's a simple polynomial, 2x ² - 3x + 7 . Berikut adalah polinom sederhana, 2x ² - 3x + 7. It is a function of some variable x , which depends only on powers of x . Ini adalah fungsi dari beberapa variabel x, yang hanya bergantung pada kekuatan dari x. The degree of a polynomial is equal to the highest power of x in it; here it is 2 because of the x ² term. Derajat polinom sama dengan kekuasaan tertinggi x di dalamnya; di sini adalah 2 karena x ² istilah. A polynomial is fully specified by listing its coefficients, in this case (2, -3, 7). Sebuah polinomial sepenuhnya ditentukan oleh daftar yang koefisien, dalam hal ini (2, -3, 7). Notice that to define a degree-d polynomial you have to specify d + 1 coefficients. Perhatikan bahwa untuk menentukan derajat-d polinomial Anda harus menentukan d + 1 koefisien.

It's easy to multiply polynomials. Sangat mudah untuk multiply polinomial. For instance, Misalnya,

(2x ² - 3x + 7) * (x + 2)

(2x ² - 3x + 7) * (x + 2)

= 2x ³ + 4x ² - 3x ² - 6x + 7x + 14

= 2x ³ + x ² + x + 14

Conversely, it is also possible to divide polynomials. Sebaliknya, juga memungkinkan untuk membagi polinomial. For instance, the above equation can be rewritten as a division: Sebagai contoh, persamaan di atas dapat ditulis kembali sebagai divisi:

(2x ³ + x ² + x + 14) / (x + 2) = 2x ² - 3x + 7 (2x ³ + x ² + x + 14) / (x + 2) = 2x ² - 3x + 7

Just like in integer arithmetic, one polynomial doesn't have to be divisible by another. Persis seperti dalam aritmatika integer, satu polinom tidak harus dapat dibagi oleh lain. But you can always divide out the "whole" part and be left with the remainder. Tapi Anda selalu bisa membagi luar "seluruh" bagian dan dibiarkan dengan sisanya. For instance x ² - 2x is not divisible by x + 1 , but you can calculate the quotient to be x - 3 and the remainder to be 3 : Sebagai contoh x ² - 2x tidak habis dibagi oleh x + 1, tapi Anda dapat menghitung hasil bagi menjadi x - 3 dan sisanya menjadi 3:

(x ² - 2x) = (x + 1) * (x - 3) + 3 (x ² - 2x) = (x + 1) * (x - 3) + 3

In fact you can use a version of long division to perform such calculations Bahkan Anda dapat menggunakan suatu versi dari pembagian panjang untuk melakukan perhitungan seperti :

Arithmetic Modulo Two Arithmetic Modul Dua

Most of us are familiar with polynomials whose coefficients are real numbers. Sebagian besar dari kita sudah familiar dengan polinomial yang koefisien adalah bilangan real. In general, however, you can define polynomials with coefficients taken from arbitrary sets. Secara umum, bagaimanapun, Anda dapat menentukan polinomial dengan koefisien yang diambil dari set sewenang-wenang. One such set (in fact a field ) consists of the numbers 0 and 1 with arithmetic defined modulo 2. Salah satu set (sebenarnya sebuah ladang) terdiri dari angka 0 dan 1 dengan aritmetika didefinisikan Modul 2. It means that you perform arithmetic as usual, but if you get something greater than 1 you keep only its remainder after division by 2. Ini berarti bahwa Anda melakukan aritmatika seperti biasa, tapi jika anda mendapatkan sesuatu yang lebih besar dari 1 Anda tetap hanya dengan sisa setelah pembagian dengan 2. In particular, if you get 2, you keep 0. Secara khusus, jika anda mendapatkan 2, Anda tetap 0. Here's the addition table: Berikut tabel tambahan:

0 + 0 = 0

0 + 0 = 0

0 + 1 = 1 + 0 = 1

(because 2 has remainder 0 after dividing by 2)

1 + 1 = 0 (karena 2 memiliki sisa 0 setelah membaginya dengan 2)

The multiplication table is equally simple: Tabel perkalian adalah sama sederhana:

0 * 0 = 0

0 * 0 = 0

0 * 1 = 1 * 0 = 0

1 * 1 = 1

What's more, subtraction is also well defined (in fact the subtraction table is identical to the addition table) and so is division (except for division by zero). Terlebih lagi, pengurangan juga didefinisikan dengan baik (dalam kenyataannya meja pengurangan identik dengan meja tambahan) dan sebagainya adalah divisi (kecuali untuk pembagian dengan nol). What is nice, from the point of view of computer programming, is that both addition and subtraction modulo 2 are equivalent to bitwise exclusive or (XOR). Apa yang bagus, dari sudut pandang pemrograman komputer, adalah bahwa baik penjumlahan dan pengurangan Modulo 2 adalah setara dengan bitwise eksklusif atau (XOR).

Now imagine a polynomial whose coefficients are zeros and ones, with the rule that all arithmetic on these coefficients is performed modulo 2. Sekarang bayangkan sebuah polinomial yang koefisien adalah nol dan satu, dengan aturan bahwa semua aritmatika pada koefisien ini dilakukan Modulo 2. You can add, subtract, multiply and divide such polynomials (they form a ring ). Anda dapat menambah, mengurangi, mengalikan dan membagi polinomial tersebut (mereka membentuk sebuah cincin). For instance, let's do some easy multiplication: Sebagai contoh, mari kita lakukan beberapa perkalian mudah:

(1x ² + 0x + 1) * (1x + 1)

(1x ² + 0x + 1) * (1x + 1)

= 1x ³ + 1x ² + 0x ² + 0x + 1x + 1

= 1x ³ + 1x ² + 1x + 1

Let's now simplify our notation by representing a polynomial as a series of coefficients. Sekarang mari kita menyederhanakan notasi kita dengan mewakili polinom sebagai rangkaian koefisien. For instance, 1x ² + 0x + 1 has coefficients (1, 0, 1), 1x + 1 (1, 1), and 1x ³ + 1x ² + 1x + 1 (1, 1, 1, 1). Sebagai contoh, 1x ² + 0x + 1 memiliki koefisien (1, 0, 1), 1x + 1 (1, 1), dan 1x ³ + 1x ² + 1x + 1 (1, 1, 1,1).

Do you see what I am driving at? Apakah anda melihat apa yang saya mengemudi di? A polynomial with coefficients modulo 2 can be represented as a series of bits. Sebuah polinomial dengan koefisien Modulo 2 dapat digambarkan sebagai serangkaian bit. Conversely, any series of bits can be looked upon as a polynomial. Sebaliknya, setiap rangkaian bit dapat dipandang sebagai polinomial. In particular any binary message, which is nothing but a series of bits, is equivalent to a polynomial. Secara khusus pesan biner manapun, yang tak lain adalah serangkaian bit, setara dengan polinomial.

CRC CRC

Take a binary message and convert it to a polynomial then divide it by another predefined polynomial called the key . Mengambil pesan biner dan mengubahnya menjadi sebuah polinom kemudian bagi dengan polinomial standar lain yang disebut kunci. The remainder from this division is the CRC. Sisanya dari divisi ini adalah KHA. Now transmit both the message and the CRC. Sekarang baik mengirimkan pesan dan KHA. The recipient of the transmission does the same operation (divides the message by the same key) and compares his CRC with yours. Penerima transmisi operasi melakukan hal yang sama (membagi pesan dengan tombol yang sama) dan membandingkan CRC dengan Anda. If they differ, the message must have been mangled. Jika mereka berbeda, pesan pasti sudah hancur. If, on the other hand, they are equal, the odds are pretty good that the message went through uncorrupted. Jika, di sisi lain, mereka adalah sama, peluang yang cukup bagus pesan masuk melalui uncorrupted. Most localized corruptions (burst of errors) will be caught using this scheme. Kebanyakan korupsi lokal (ledakan kesalahan) akan ditangkap dengan menggunakan skema ini.

Not all keys are equally good. Tidak semua kunci yang sama baik. The longer the key, the better error checking. Semakin panjang kunci, pengecekan error yang lebih baik. On the other hand, the calculations with long keys can get pretty involved. Di sisi lain, perhitungan dengan kunci panjang bisa jadi sangat terlibat. Ethernet packets use a 32-bit CRC corresponding to degree-31 remainder (remember, you need d + 1 coefficients for a degree-d polynomial). Paket ethernet menggunakan 32-bit CRC sesuai dengan derajat-31 sisa (ingat, anda perlu d + 1 koefisien untuk meraih gelar-d polinomial). Since the degree of the remainder is always less than the degree of the divisor, the Ethernet key must be a polynomial of degree 32. Karena tingkat sisanya selalu kurang dari derajat dari pembagi, kunci Ethernet harus menjadi polinomial derajat 32. A polynomial of degree 32 has 33 coefficients requiring a 33-bit number to store it. Sebuah polinomial derajat 32 memiliki 33 koefisien yang memerlukan 33-bit untuk menyimpan hal itu. However, since we know that the highest coefficient (in front of x ³² ) is 1, we don't have to store it. Namun, karena kita tahu bahwa koefisien tertinggi (di depan x ³²⁾ adalah 1, kita tidak perlu menyimpannya. The key used by the Ethernet is 0x04c11db7 . Kunci yang digunakan oleh Ethernet adalah 0x04c11db7. It corresponds to the polynomial: Ini sesuai dengan polinomial:

x ³² + x ²⁶ + ... x ³² + x ²⁶ + ... + x ² + x + 1 + X ² + x + 1

There is one more trick used in packaging CRCs. Ada satu trik yang digunakan dalam kemasan CRC. First calculate the CRC for a message to which you have appended 32 zero bits. Pertama menghitung CRC untuk pesan yang Anda telah ditambahkan 32 nol bit. Suppose that the message had N bits, thus corresponding to degree N-1 polynomial. Anggaplah bahwa pesan telah N bit, dengan demikian sesuai dengan derajat N-1 polinomial. After appending 32 bits, it will correspond to a degree N + 31 polynomial. Setelah menambahkan 32 bit, maka akan sesuai dengan tingkat N + 31 polinomial. The top-level bit that was multiplying x ^N-1 will be now multiplying x ^N+31 and so on. Tingkat atas sedikit yang mengalikan x ^N-1 akan menjadi sekarang mengalikan x ^{N 31} dan seterusnya. In all, this operation is equivalent to multiplying the message polynomial by x ³² . Secara keseluruhan, operasi ini setara dengan mengalikan pesan polinomial oleh x ^32. If we denote the original message polynomial by M (x) , the key polynomial by K (x) and the CRC by R (x) (remainder) we have: Jika kita menyatakan polinom pesan asli oleh M (x), kunci polinom oleh K (x) dan KHA oleh R (x) (sisa) kita memiliki:

M * x ³² = Q (x) * K (x) + R (x) M * x ³² = Q (x) * K (x) + R (x)

Now add the CRC to the augmented message and send it away. Sekarang tambahkan KHA ke ditambah pesan dan mengirimkannya pergi. When the recipient calculates the CRC for this sum, and there was no transmission error, he will get zero. Ketika penerima CRC untuk menghitung jumlah ini, dan tidak ada kesalahan transmisi, ia akan mendapatkan nol. That's because: Itu karena:

M * x ³² + R (x) = Q (x) * K (x) (no remainder!) M * x ³² + R (x) = Q (x) * K (x) (tidak ada sisa!)

You might think I made a sign mistake--it should be -R (x) on the left. Anda mungkin berpikir aku membuat kesalahan tanda - mestinya-R (x) di sebelah kiri. Remember, however, that in arithmetic modulo 2 addition and subtraction are the same! Ingat, bagaimanapun, bahwa dalam aritmetika Modulo 2 penjumlahan dan pengurangan adalah sama!

Next: Let'sl use this property of the CRC to test our implementation of the algorithm.Next: Let'sl menggunakan harta benda ini untuk menguji kita KHA implementasi dari algoritma

Redundansi siklik Periksa

Sebuah metode yang kuat untuk mendeteksi kesalahan dalam data yang diterima adalah dengan pengelompokan data byte ke dalam sebuah balok dan menghitung Siklik redundansi Check (CRC). Hal ini biasanya dilakukan oleh protokol data link dan CRC dihitung ditambahkan ke akhir data link layer bingkai.

CRC dihitung dengan melakukan pembagian Modulo 2 data dengan generator polinomial dan merekam sisanya setelah pembagian.

Three polynomials are in common use they are: Tiga polinomial adalah lazim dipakai mereka adalah:

• CRC-16 = x16 + x15 + x2+ 1 (used in HDLC ) CRC-16 = x16 + x15 + x2 + 1 (digunakan dalam HDLC)
• CRC-CCITT = x16 + x12 + x5 + 1 CRC-CCITT = x16 + x12 + x5 + 1
• CRC-32 = x32 + x26 + x23 + x22 + x16 + x12 + x11 + x10 + x8 + x7 + x5 + x4 + x2 + x + 1 (used in Ethernet ) CRC-32 = x32 + x26 + X23 + x22 + x16 + x12 + x11 + x10 + x8 + x7 + x5 + x4 + x2 + x + 1 (digunakan dalam Ethernet)

Walaupun pembagian ini dapat dilakukan di perangkat lunak, biasanya dilakukan menggunakan register geser dan X-OR gerbang. Solusi perangkat keras untuk mengimplementasikan CRC jauh lebih sederhana daripada pendekatan perangkat lunak.Sebuah implementasi praktis dari sebuah decoder juga membutuhkan metode untuk menginisialisasinya pembuat sandi sebelum transmisi data bit pertama dalam bingkai, dan untuk menyiram encoder setelah mengirim byte terakhir. Pada contoh di bawah ini (yang menggunakan representasi yang berbeda dari skema untuk X-OR register geser gerbang dan unsur-unsur), proses dimulai dengan inisialisasi sandi dengan nol bit, dengan mengatur beralih ke B. Beberapa CRC's menginisialisasinya yang mendaftar ke non nilai nol, yang dapat memberikan kemampuan deteksi ditambahkan bila bit pertama dalam bingkai mungkin sendiri menjadi nol. Then the switch is moved to position A and one data bit enter the encoder for each clock cycle. Maka saklar dipindahkan ke posisi A dan satu bit data yang masuk ke encoder untuk setiap clock cycle. The data bits are immediately available at the output. Bit data segera tersedia pada output. After the last bit has been sent, the switch is returned to position B and the contents of the encoder are sent to the output. Setelah bit terakhir telah dikirim, saklar dikembalikan ke posisi B dan isi sandi akan dikirim ke output. This is often called flushing the encoder and requires one clock cycle per bit held in the shift register. Hal ini sering disebut pembilasan alat pembuat sandi dan memerlukan satu siklus clock per bit diadakan di register geser.

On reception, the process is reversed. Pada penerimaan, proses dibalik. The CRC register is first set to zero (or the initial value on transmission, if non-zero). Register CRC pertama diatur ke nol (atau nilai awal pada transmisi, jika bukan nol). The bits (this time including the CRC) are fed into the register on each clock cycle. Bit (kali ini termasuk CRC) yang dimasukkan ke dalam register pada setiap clock cycle. If the CRC contains the value zero (assuming initialisation was zero), the CRC is valid, if not it has detected an error. Jika CRC berisi nilai nol (dengan asumsi inisialisasi adalah nol), KHA berlaku, jika tidak hal itu telah mendeteksi kesalahan. The CRC-16 is able to detect all single errors, all double errors, all odd numbers of errors and all errors with burst less than 16 bits in length. CRC-16 yang mampu mendeteksi semua error tunggal, semua kesalahan ganda, semua angka ganjil dari kesalahan dan semua kesalahan dengan meledak kurang dari 16 bit panjangnya. In addition 99.9984 % of other error patterns will be detected. Selain 99,9984% dari pola-pola kesalahan lain akan terdeteksi.

Protocols at the network layer and higher (eg IP , UDP , TCP ) usually use a simpler checksum to verify that the data being transported has not been corrupted by the processing performed by the nodes in the network. Protokol di lapisan jaringan dan lebih tinggi (misalnya IP, UDP, TCP) biasanya menggunakan checksum yang lebih sederhana untuk memastikan bahwa data yang diangkut tidak rusak oleh proses yang dilakukan oleh node dalam jaringan.

Bit Order Bit Order

The CRC is the only field which is by convention sent most significant bit first. KHA adalah satu-satunya bidang yang dikirim oleh konvensi bit yang paling signifikan pertama. (This is contrary to all header and payload bytes which are sent least significant bit first .) Thus the first bit of the a CRC-16 to be sent is the bit corresponding to X16 and the last, the bit corresponding to X1. (Hal ini bertentangan dengan semua header dan payload byte yang akan dikirim paling significant bit pertama.) Jadi bit pertama dari sebuah CRC-16 yang akan dikirim adalah sedikit sesuai dengan X16 dan yang terakhir, sesuai dengan bit X1.

= Baca Juga Sob =