Cyclic Redundancy Check

Kode pendeteksian kesalahan yang paling umum serta paling hebat adalah Cyclic Redundancy Check (CRC) yang dapat digambarkan sebagai berikut, dengan adanya blok bit k?bit, atau pesan, transmitter mengirimkan suatu deretan n?bit, disebut sebagai Frame Check Sequence (FCS), sehingga frame yang dihasilkan, terdiri dari k+n bit, dapat dibagi dengan jelas oleh beberapa nomor yang sebelumnya sudah ditetapkan. Kemudian receiver membagi frame yang datang dengan nomor tersebut dan, bila tidak ada sisa, maka diasumsikan tidak terdapat kesalahan.
Untu.k menjelaskan hal ini, kita sajikan prosedur dalam dua cara, yakni: modulo 2 aritmatik dan polynomials.

Modulo 2 Aritmatik
Modulo 2 aritmatik menggunakan penambahan biner tanpa pembawa, yang hanya merupakan operasi OR?eksklusif saja. Pengurangan biner tanpa pembawa juga diterjemahkan sebagai operasi OR?eksklusif. Sebagai contoh,

Sekarang menetapkan
T = (k + n)?bit frame untuk ditransmisikan, dengan n
M = k?bit pesan, bit k pertama dari T
F = n?bit FCS, bit n terakhir dari T
P = pola n + 1 bit, ini merupakan pembagi yang sudah ditetapkan sebelumnya
Kita inginkan T/P tidak memiliki sisa. Sehingga harus dinyatakan dengan

T=2ⁿM+F

Yaitu, dengan cara mengalikan M dengan 2ⁿ. sebenarnya kita telah memindahkannya ke kiri lewat bit n dan menambahi hasilnya dengan nol. Dengan menambahkan F menghasilkan deretan M dan F, yang merupakan T. Kita ingin T bisa dibagi oleh P. Anggap saja kita membagi 2ⁿM dengan P, berikut persamaannya:

Ada hasil bagi dan sisa. Karena pembaginya. berupa Modulo 2, sisanya selalu sedikitnya satu bit lebih pendek daripada pembagi. Kita akan menggunakan sisa ini sebagai FCS. Kemudian

T=2ⁿM+R

Apakah R memenuhi syarat bahwa T/P tidak memiliki sisa? Untuk melihatnya, amati yang berikut ini:

Disubsitusi dalam persamaan di atas, kita peroleh

Bagaimanapun juga, apapun angka biner yang ditambahkan dengan modulo 2?nya sendiri akan menghasilkan nol. Sehingga

Tidak ada sisa, dan karenanya T bisa dibagi dengan P. Jadi, FCS dengan mudah dibangkitkan: Secara sederhana membagi 2ⁿM dengan P dan mengunakan sisanya sebgai FCS. Pada penerima, receiver akan membagi T dengan P dan tidak memperoleh sisa bila tidak terdapat kesalahan.
Sekarang kita perhatikan contoh sederhana berikut ini.

1. Diketahui:
   Pesan M = 1010001101 (10 bit)
   Pola P 110101 (6 bit)
   FCS R akan dikalkulasikan (5 bit)
2. Pesan dikalikan dengan 25, menghasilkan 101000110100000.
3. HasiInya. dibagi dengan P:
4. Sisanya ditambahkan dengan 2ⁿM untuk memberi T=101000110101110, yang ditransmisikan.
5. Bila tidak terdapat kesalahan, receiver menerima T utuh. Frame yang diterima dibagi dengan P:

Karena tidak ada sisa, diasumsikan bahwa tidak terdapat kesalahan.
Pola P dipilih sebagai satu bit lebih panjang dibanding FCS yang diinginkan, dan pola bit yang dipilih tergantung pada jenis kesalahan yang diharapkan. Pada nilai minimum, orde bit yang tinggi maupun yang rendah dari P harus berupa 1.
Tidak ada metode yang ringkas untuk menentukan adanya satu kesalahan atau lebih. Suatu kesalahan terjadi dalam pembalikan bit. Ini ekuivalen dengan pengambilan eksklusif OR (XOR) bit dan 1 (modulo 2 dari 1 dijumlahkan ke bit): 0 + 1 = 1; 1 + 1 = 0. Jadi, kesalahan pada frame (n+k)?bit dapat ditunjukkan lewat bidang (n+k) dengan ls pada setiap posisi kesalahan. Frame T_r yang diperoleh dinyatakan sebagai

dimana
T = frame yang ditransmisikan
E = pola kesalahan dengan 1s pada posisi dimana kesalahan terjadi
T_r = frame yang diterima
Receiver akan gagal mendeteksi kesalahan bila dan hanya bila T, dapat dibagi dengan P tanpa sisa, yang ekuivalen dengan E yang dibagi dengan P. Secara. intuitif, hal ini tidak mungkin terjadi.
Polynomials
Cara kedua mengamati proses CRC adalah dengan menyatakan seluruh nilai sebagai polynomial dalam suatu model variabel X, dengan koefisien?koefisien biner. Koefisien berhubungan dengan bit?bit dalam angka biner. Jadi, unt?uk M = 110011, kita peroleh M(X) = X⁵ + X⁴ + X + 1, dan untuk P = 11001, kita peroleh p (X) = X⁴ + X³ + 1. Operasi aritmetik lagilagi berupa modulo 2. Sekarang, proses CRC digambarkan sebagai:

Error E(X) hanya akan menjadi tak terdeteksi bila dibagi dengan P(X). Hal ini bisa ditunjukkan bahwa semua kesalahan berikut ini tidak dibagi dengan pilihan P(X) yang sesuai dan karenanya mampu dideteksi:

• Semua bit kesalahan tunggal
• Semua bit kesalahan ganda, selama P(X) memiliki sedikitnya tiga 1s
• Apapun angka kesalahan yang garijil, selama P(X) memuat faktor (X + 1)
• Apapun banyaknya kesalahan dimana panjangnya kurang dari panjang polynomial pembagi; yakni, kurang dari atau setara dengan panjang FCS.
• Kesalahan yang besar sekali

Selain itu, dapat pula ditunjukkan bahwa bila semua pola kesalahan dianggap sama, maka untuk kesalahan dari panjang r + 1, probabilitas dari kesalahan yang tak terdeteksi [E(X) dibagi dengan p(X)l adalah 1/2r?1, dan untuk kesalahan yang lebih panjang, probabilitasnya adalah 1/2^r?1, dimana r adalah panjang FCS.
Empat versi P(X) yang telah digunakan secara luas adalah:

CRC?12 CRC?16 CRC?CCITT CRC?32

= X12 + X11 + X3 + X2 + X + 1 = X16 + X15 + X2 + 1 = X16 + X12 + X5 + 1 = X32 + X26 + X23 + X22 + X16 + X 12 + X11 + X10 + X8 + X7 + X5 + X4 + X2 + X + 1

Sistem CRC?12 dipergunakan untuk transmisi sederatan sebesar 6?bit karakter dan menbangkitkan 12?bit FCS. Baik CRC?16 maupun CRC?COTT populer untuk 8?bit karakter, masing?masing di Amerika Serikat dan Eropa, di mana keduanya sama?sama menghasilkan 16?bit FCS. Nampaknya ini sesuai untuk sebagian besar aplikasi, meskipun CRC?32 ditentukan sebagai salah satu pilihan untuk standar transmisi synchronous ujung?ke?ujung.