INTEGRITAS DATA
Objektif: Mengetahui maksud ralat dalam komunikasi data Memahami teknik mengenal error dan membetulkan error
Pendahuluan Metoda Pengujian Ralat
Parity Checking Vertical Redundancy Check Longitudanal Redundancy Check Cyclical Redundancy Check Checksums Kode Hamming Echo Checking Parity bulatan (cyclical)
Dalam rangkaian komunikasi data, mungkin
ditemukan error dalam transmisi data Mengecek atau membetulkan error ini disebutintegriti data Integriti ~ data yg diterima apakah sama dengan data yang dihantar. Keselamatan ~ data yang dihantar selamat sampai ketujuan tanpa ada sabotase dari pihak lain
Parity Checking Hanya satu bit dalam unit data seperti (byte,
kharakter, paket) yg berubah dari bit 1 ke bit 0 atau bit 0 ke bit 1. Contoh: bit 01000001 (ASCII huruf ‘A’) dihantar, tetapi 01001001 (ASCII huruf ‘I’) diterima. Hanya digunakan untuk pengiriman data melalui transmisi serial. Contoh: 8 jalur kawat digunakan utk menghantar 8 bit bagi satu byte pd saat yg sama, dan salah satu kawat amat sibuk, satu bit akan menjadi rusak dalam setiap byte.
Contoh
Parity Checking Pariti Genap: bil. bit 1 perlu genap pd setiap byte Pariti Ganjil: bil. bit 1 perlu ganjil pd setiap byte Pariti Ruang: menggunakan bit 0 utk setiap bit pariti Pariti Tanda: menggunakan bit 1 utk setiap bit pariti * Gunakan kod ASCII 7-bit. Bit paling kiri adalah bit pariti ASCII
Pariti Genap
Pariti Ganjil
Pariti Ruang
Pariti Tanda
A
01000001
11000001
01000001
11000001
B
01000010
11000010
01000010
11000010
C
11000011
01000011
01000011
11000011
D
01000100
11000100
01000100
11000100
Proses VRC (Pariti genap)
Contoh VRC (Pariti genap) Andaikan pengirim ingin menghantar perkataan
“world”, dlm ASCII, lima aksara dikodekan sebagai: 1110111
1101111
1110010
1101100
1100100
w
o
r
l
d
Setiap 4 aksara pertama mempunyai bilangan bit 1
yg genap, oleh itu bit pariti adalah 0. Aksara terakhir ‘d’, mempunyai 3 bit 1 (ganjil), oleh itu parity bit adalah 1 untuk menjadikan bit 1 sebagai pariti genap. 01110111
01101111
01110010
01101100
11100100
w
o
r
l
d
Contoh VRC (cont.) Andaikan perkataan “world” diterima oleh
penerima tanpa ada ralat pada saat transmisi.
Penerima mengira bit 1 dalam setiap aksara
dan memperolehi nomor genap (6,6,4,4,4). Data tersebut dapat diterima.
Contoh VRC (cont..) Andaikan perkataan “world” yg diterima oleh penerima
mempunyai ralat selama transmisi. 01111111
01101111
01110110
01101100
11100100
DEL
o
v
l
d
Penerima mengira bit 1 dalam setiap aksara dan mendapati
terdapat bilangan genap dan ganjil (7,6,5,4,4). Penerima tahu bhw data tersebut telah diubah, dan membuangnya serta memohon transmisi di ulangi.
Longitudinal Redundancy Check 11100111 11011101 00111001 10101001
Original
LRC
Original
10101010
Plus LRC
Contoh LRC/2-dimensi Andaikan blok di bawah dihantar: 10101001
11001010
11000011
11100100
01000100
T
e
a
r
LRC
Selama transmisi, gangguan terjadi yg
mengakibatkan beberapa bit berubah (‘burst error’) 10100011
01111010
11000011
11100100
01000100
Q
=
a
r
LRC
Apabila penerima memeriksa LRC, setengah bit
tidak mengikuti peraturan pariti genap, maka keseluruhan blok tidak diterima. 10100011
01111010
11000011
11100100
01000100
Q
=
a
r
LRC
Cyclical Redundancy Check (CRC) Teknik pemeriksaan ralat yg terbaik menggunakan
konsep pengulangan Metoda penandaan ralat yang hampir tepat berdasarkan bentuk bit sebagai polinomial. Yaitu berdasarkan sebahagian (dibagi 2 bagian) Urutan bit pengulangan yg dinamakan sbg CRC atau wadah CRC, diletakkan bersamaan pada akhir unit data supaya hasilnya dapat dibagi dgn suatu nomor separoh kedua (yg ditentukan)
CRC (samb…) Pada penerima, unit data yg diterima dibagi
dgn separoh kedua tadi Pada tahap ini, jika tiada wadah, unit data dianggap tidak berubah dan diterima Kehadiran wadah menunjukkan bhw unit data telah rusak saat penghantaran dan ditolak. Bit pengulangan yg digunakan oleh CRC didapat dari pembagian unit data dengan pembagi, yaitu wadh dalam CRC
Sebagai pengesahan, CRC harus
mempunyai dua kualitas.
Harus mempunyai kurang 1 bit dari pembahagi, Menambahnya pd penghujung rentetan data yang menghasilkan rangkaian bit yg dapat dibagi dgn tepat oleh pembahagi.
Proses CRC Urutan n bit 0 ditambah pd ujung unit data. n adalah suatu nomor yg kurang 1 dr bilangan bit yg terdapat dalam pembagi (bil bit pembagi = n+1) 2. Unit data yg terhasil (dr langkah 1.) dibagi dengan pembagi menggunakan proses pembahagian separoh unit. Wadah drp pembagian ini merupakan CRC 3. CRC (Wadah) bagi n bit yg terdapat dalam langkah 2. akan menggantikan bit-bit 0 yang ditambah pd ujung unit data (CRC mungkin juga suatu rangkaian bit 0 cth : 0000) 1.
Proses CRC (samb…) Unit data tiba pada penerima, diikuti oleh
CRC. Penerima mengambil keseluruhan rangkaian bit yg diterima (unit data + CRC) dan membaginya dgn pembahagi yg sama utk mendapatkan wadah CRC Jika urutan sampai tanpa ralat, metoda CRC akan mendapat tiada wadah (wadah=0) dan unit data diterima Jika urutan berubah selama transmisi, pembagian menghasilkan wadah dan unit data tidak diterima
Proses CRC
Pembagian dlm wadah CRC n+1 = 4
Jika bit plg kiri bg wadah = 0, gunakan pembagi dgn semua bit 0 (dan bukan pembagi asal)
Operasi XOR (⊕)
n=3
Pembahagian dlm metoda CRC
Polinomial mewakili pembahagi
Name
Polynomial
Application
CRC--8 CRC
x8 + x2 + x + 1
ATM header
CRC--10 CRC
x10 + x9 + x5 + x4 + x 2 + 1
ATM AAL
ITU--16 ITU
x16 + x12 + x5 + 1
HDLC
ITU--32 ITU
x32 + x26 + x23 + x22 + x16 + x12 + x11 + x10 + x8 + x7 + x5 + x4 + x2 + x + 1
LANs
* Tingkat polinomial
Checksum/Jumlah pengecekan Juga berasaskan konsep pengulangan yaitu dibentuk dengan menambah bit stream
menggunakan arithmetik komplimen 1 (one’s complement arithmetic) dan kemudian mengkomplimen hasilnya Pada pengirim, pengeluar checksum membagik data unit kedalam segmen yg sama utk beberapa n bit Segmen ini ditambah bersama2 menggunakan one’s complement arithmetic supaya jumlah panjangnya juga n bit Jumlah itu kemudian dikomplimen dan ditambah pada ujung data unit asal sbg bit pengulang, yang dikenal sebagai medan jumlah pengecekan (checksum field)
Checksum (samb…) Data unit tsb dihantar melalui rangkaian. Jika jumlah segmen data adalah T, maka checksum
adalah –T. Penerima membagikan data unit, dan menambah semua segmen bersama2 dan komplimen hasilnya. Jika data unit tidak mengandungi ralat, jumlah nilai dgn menambah data segmen dan medan checksum hendaklah 0. Jika hasilnya bukan 0, paket tersebut mengandung ralat dan penerima menolak data tsb.
Pengirim mengikut langkah2 ini:
Unit dibahagikan kpd k sesi, setiap satu n bit. Semua sesi ditambah menggunakan one’s complement untuk mendapat jumlah. Jumlahnya dikomplemen dan menjadi medan checksum Checksum akan dihantar bersama2 data unit.
Penerima mengikut langkah2 ini:
Unit dibagikan kpd k sesi, setiap satu n bit. Semua sesi ditambah menggunakan one’s complement untuk mendapat jumlah. Jumlahnya dikomplemen. Jika hasilnya adalah 0, data diterima, jika tidak, data ditolak.
Contoh Checksum Andaikan blok yg mengandung 16 bit berikut dihantar
menggunakan checksum 8 bit: 10101001 00111001 Nombor ditambah menggunakan 1’s complement arithmetic Corak yg dihantar adalah:
10101001
00111001
10101001 00111001 SUM
11100010
CHECKSUM
00011101
00011101 checksum
Contoh Checksum (samb…) Andaikan penerima menerima data yg dihantar dan tidak
mengandungi ralat: 10101001 00111001 00011101 Apabila penerima menambah tiga sesi bersama2, maka akan mendapat semua nilai 1s, dan apabila dikomplimen, nilai menjadi 0s menunjukkan tiada ada ralat.
checksum
10101001 00111001 00011101
SUM
11111111
COMPLEMENT
00000000
Contoh Checksum (samb…) Andaikan burst error untuk panjang 5 bit yg mempengaruhi
4 bit: 10101111 11111001 00011101 Apabila penerima menambah 3 sesi bersama-sama, maka akan mendapat:
checksum
10101111 11111001 00011101
SUM
11000110
COMPLEMENT
00111001
Maka data unit mengandungi ralat.
Prestasi Checksum Untuk mengecek semua ralat termasuk bit
nomor ganjil dan genap. Walau bagaimanapun, jika satu atau lebih bit dalam satu segmen rusak, dan nilai bit yg sama yg terdapat bertentangan dalam segmen kedua juga rusak, dan jumlah dalam kolom tidak berubah, maka penerima tidak dapat mengetahui ralat.
Kode Hamming Metoda ini bukan hanya sekadar mengetahui
ralat, tetapi dapat juga membetulkan ralat dengan ketepatan 100% Kode Hamming utk aksara ASCII 7-bit memerlukan 4 bit pariti, menjadikannya 11 bit Bit pariti berada pada posisi 1,2,4,8 (2X), dan bit data berada pada posisi 3,5,6,7,9,10,11 Dapat juga menggunakan pariti genap dan ganjil
Contoh Hamming Code Andaikan aksara ‘A’ dihantar menggunakan
hamming code: 1000001 1
2
3
4
5
6
7
8
9
10
11
?
?
1
?
0
0
0
?
0
0
1
P1
P2
B1
P4
B2
B3
B4
P8
B5
B6
B7
Posisi 1,2,4,8 digunakan utk bit pariti, manakala
posisi 3,5,6,7,9,10,11 digunakan utk bit data
Contoh Kod Hamming (genap) Andaikan hamming code menggunakan pariti
genap 1
2
3
4
5
6
7
8
9
10
11
0
0
1
0
0
0
0
1
0
0
1
P1
P2
B1
P4
B2
B3
B4
P8
B5
B6
B7
Bit 1,3,5,7,9,11 dicek oleh bit pariti 1 (P1) Bit 2,3,6,7,10,11 dicek oleh bit pariti 2 (P2) Bit 4,5,6,7 dicek oleh bit pariti 4 (P4) Bit 8,9,10,11 dicek oleh bit pariti 8 (P8) Maka bit 00100001001 dihantar
Bagaimana mengesan & membetulkan ralat? Tentukan pariti mana yg mengesan ralat (jika
semuanya tidak ada ralat maka penghantaran dianggap tidak ada ralat) Jumlahkan lokasi pariti bit yg diralat (andaikan P2 dan P4) Jumlah tersebut adalah lokasi ralat Tukarkan bit tersebut (jika 1 jadikan 0 dan sebaliknya).
P1=1,3,5,7,9,11 P2=2,3,6,7,10,11
P4=4,5,6,7 P8=8,9,10,11
Andaikan hamming code menggunakan pariti genap dan bit
yg dihantar mengandungi ralat 1
2
3
4
5
6
7
8
9
10
11
0
0
1
0
0
1
0
1
0
0
1
P1
P2
B1
P4
B2
B3
B4
P8
B5
B6
B7
pariti 1 (P1) dan pariti 8 (P8) mencek dan mendapatkan bil.
bit 1 adalah genap. (tidak ada ralat) pariti 2 (P2) dan pariti 4 (P4) mencek dan mendapatkan bil. bit 1 adalah ganjil. (ada ralat) Apabila kita menambah pariti yg mempunyai ralat (2+4=6), maka menunjukkan bit 6 tidak benar Oleh karena itu bit pd kedudukan ke-6 diganti dari bit 1 ke bit 0
Cyclical Parity (Pariti Kitaran) menggunakan 2 bit pengemas ralat. Melalui pariti bulatan, maka meningkatkan
kecekapan mengecek ralat. Dapat juga mempunyai pengecekan pariti bulatan genap dan ganjil. Setiap bit pariti mengecek bit-bit tertentu dalam sesuatu bait. Contohnya, bit pariti pertama mengemas bit pada lokasi 1,3,5,7 dan bit pariti kedua mengemas pada lokasi 2,4,6.
Contoh Pariti Bulatan (genap) Andaikan, kita menggunakan pariti bulatan genap, dan
rentetan data unit yang hendak dihantar adalah: 1000011 Data unit 1
0
0
P1 P2 P1
0
0
P1 P2 1
1
0
1
P2 P1 P2 P1 P1 P2
Maka bit pariti pertama akan memasukkan nilai 0 (kerana
jumlah bit adalah genap), dan bit pariti kedua akan memasukkan nilai 1 (kerana jumlah bit adalah ganjil).
Semakan Talun (Echo Checking) Penerima mengulang semua data unit yg diterima
daripada pengirim Jika aksara “ABC” ditransmit menggunakan penyemakan echo, penerima akan menghantar kembali “ABC” kepada pengirim Pengirim boleh mengenalpasti sama ada data unit yg dihantar mengandungi ralat atau tidak Jika mengandungi ralat, pengirim boleh mentransmit semula data unit tersebut
