integriti data objektif: mengetahui maksud ralat dalam komunikasi data dan rangkaian memahami teknik...
Post on 15-Jan-2016
309 views
TRANSCRIPT
INTEGRITI DATA
Objektif:Mengetahui maksud ralat dalam komunikasi data dan rangkaianMemahami teknik mengenalpasti dan membetulkan ralat.
Sepintas lalu
Jenis-jenis ralat Ralat 1-bit (Single-bit error) Ralat Meletus (Burst error)
Kaedah pengawalan ralat Penyemakan pariti (Vertical Redundancy Check) Longitudanal Redundancy Check Cyclical Redundancy Check Checksums Kod Hamming Penyemakan echo Pariti bulatan (cyclical)
Dalam rangkaian komunikasi data, mungkin berlaku ralat dalam transmisi data
Mengelak atau membetulkan ralat ini dipanggil mengekalkan kesahihan/integriti data
Integriti ~ merujuk kepada data yg diterima adalah sama dengan data yang dihantar.
Keselamatan ~ merujuk kepada data yang dihantar selamat daripada intipan termasuk juga keselamatan data drp perbuatan yg tidak disengajakan.
Kawalan ke atas rangkaian diperlukan utk: Mencegah sebarang ancaman drp berlaku Mengesan sebarang ancaman yg akan berlaku Membetulkan kesan ancaman yang telah dikesan.
Rangkaian mesti dikawal drp: Ralat yang diciptakan oleh manusia Ralat rangkaian yang mengakibatkan kehilangan
data, perubahan data dan kerosakan data.
Jenis-jenis ralat
Data boleh menjadi rosak semasa transmisi. Utk komunikasi yg boleh dipercayai, semua ralat
hendaklah dikesan dan diperbetulkan. Apabila isyarat elektromagnet mengalir dari satu titik
ke titik lain, gangguan drp panas, medan magnet dan lain-lain bentuk elektrik boleh berlaku.
Gangguan ini boleh mengubah bentuk atau penjangkamasa isyarat.
Jika isyarat membawa data binari yang dikodkan, perubahan boleh menukarkan maksud asal data.
2 jenis ralat: Ralat 1-bit (Single-bit error) Ralat Letusan (Burst error)
Ralat 1-bit
Hanya satu bit dalam unit data seperti (bait, aksara, 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.
Ia selalunya berlaku apabila kita menghantar menggunakan transmisi selari.
Contoh: 8 wayar digunakan utk menghantar semua 8 bit bagi satu bait pd masa yg sama, dan salah satu wayar amat sibuk, satu bit boleh menjadi rosak dalam setiap bait.
Contoh Ralat 1-bit
Ralat Letusan (Burst Error)
Dua atau lebih bit dalam unit data telah berubah dari bit 1 ke bit 0 atau sebaliknya
Contoh: bit 01000001 (ASCII huruf ‘A’) dihantar, tetapi 01110011 (ASCII huruf ‘s’) diterima
Panjang letusan (burst) disukat drp bit yg mula tercemar sehingga bit terakhir yg tercemar
Sesetengah bit diantaranya mungkin tidak tercemar
Ia selalunya berlaku dalam transmisi sesiri
Contoh : Ralat Letusan
Kaedah Kawalan Ralat
Terdapat pelbagai kaedah yang digunakan untuk mengesan ralat, diantaranya ialah: Penyemakan pariti (Vertical Redundancy
Check) Longitudanal Redundancy Check Cyclical Redundancy Check Checksums Penyemakan talun (echo) Pariti Kitaran (cyclical) Kod Hamming
Menggunakan konsep‘redundancy’
Mengesan Ralat : Ulangan Ia menggunakan konsep pengulangan, iaitu menambah
bit tambahan untuk mengesan ralat di peranti destinasi (penerima).
Bit pengulang digunakan utk memeriksa ketepatan unit data.
Apabila strim data dikeluarkan, ia melalui peranti yang menganalisa dan menambah kod pemeriksaan pengulangan.
Unit data menjadi lebih besar dengan tambahan bit dan ia bergerak melalui talian ke penerima.
Penerima meletakkan keseluruhan strim melalui fungsi pemeriksaan.
Jika strim bit yg diterima lulus kriteria pemeriksaan, data akan diterima dan bit pengulangan akan dibuang.
Contoh Proses Mengesan Ralat
Pengesanan Ralat
4 jenis pemeriksaan pengulangan digunakan dalam komunikasi data: Vertical redundancy check (VRC) (juga dikenali
sebagai parity check) Longitudinal redundancy check (LRC) Cyclical redundancy check (CRC) Checksum
VRC, LRC, CRC selalunya diimplementasikan dalam lapisan fizikal utk digunakan pada lapisan pautan data.
Checksum digunakan terutamanya oleh lapisan teratas dlm OSI Reference Model
Mekanisma pengesanan ralat yg paling digemari, murah - dikenali sebagai penyemakan pariti Digunakan dalam penghantaran asinkroni
Jenis penyemakan pariti: genap, ganjil, ruang, tanda, tiada pariti dan pariti tak diendahkan
Penyemakan pariti memerlukan setiap transmisi menghantar bit pengulangan (yg dipanggil bit pariti ditambah pada setiap unit data) mengikut keperluan pariti.
Contoh: menjadikan bilangan bit 1 (termasuk bit pariti) menjadi genap utk bit pariti genap
VRC/Semakan Pariti
VRC/Semakan 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
Pariti Genap: bil. bit 1 perlu genap pd setiap baitPariti Ganjil: bil. bit 1 perlu ganjil pd setiap baitPariti Ruang: menggunakan bit 0 utk setiap bit paritiPariti Tanda: menggunakan bit 1 utk setiap bit
pariti * Gunakan kod ASCII 7-bit. Bit paling kiri adalah bit pariti
Proses VRC (pariti genap)
Andaikan kita ingin mentransmit unit data binari 1100001 [ASCII ‘a’]
Mencampurkan bilangan bit 1 menjadikan 3, iaitu nombor ganjil
Sebelum mentransmit, unit data melalui penjana pariti
Penjana pariti mengira bilangan bit 1 dan meletakkan bit pariti (bit 1) pd penghujung
Jumlah bilangan bit 1 adalah 4, nombor genap
Proses VRC (Pariti genap)
Proses VRC
Sistem mentransmit keseluruhan unit data ke destinasi
Apabila ia tiba pada destinasi, penerima meletakkan semua 8 bit melalui fungsi penyemakan pariti genap
Jika penerima melihat 11000011, ia mengira 4 utk bit 1, iaitu nombor genap, dan unit data diterima
Jika bilangan bit 1 adalah ganjil, penerima tahu bahawa ralat telah berlaku dalam data unit tersebut dan menolak unit data
Contoh VRC (Pariti genap)
Andaikan pengirim ingin menghantar perkataan “world”, dlm ASCII, lima aksara dikodkan sebagai:
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.
1110111 1101111 1110010 1101100 1100100
w o r l d
01110111 01101111 01110010 01101100 11100100
w o r l d
Contoh VRC (cont.)
Andaikan perkataan “world” diterima oleh penerima tanpa berlaku ralat dlm transmisi.
Penerima mengira bit 1 dalam setiap aksara dan memperolehi nombor genap (6,6,4,4,4).
Data tersebut boleh diterima.
Contoh VRC (cont..)
Andaikan perkataan “world” yg diterima oleh penerima mempunyai ralat semasa transmisi.
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 semula.
01111111 01101111 01110110 01101100 11100100
DEL o v l d
Prestasi VRC (even parity)
VRC boleh mengesan semua jenis ‘single-bit error’. Ia juga boleh mengesan ‘burst errors’ jika bilangan bit
yang berubah adalah ganjil (keburukan) Contoh: Unit data menggunakan pariti genap di mana
bilangan bit 1 termasuk bit pariti adalah 6, iaitu: 10011111
Jika mana-mana nilai utk 3 bit berubah, hasilnya pariti akan menjadi ganjil dan ralat boleh dikesan.
11101111:7, 11001011:5, 10000011:3 – semua ganjil Unit data tidak akan diterima.
Prestasi VRC (samb…)
Contoh: Unit data menggunakan pariti genap di mana bilangan bit 1 termasuk pariti bit adalah 6, iaitu: 10011111
Andaikan 2 bit atau nombor genap bit berubah: 11111111:8, 11101011:6, 10100000:2 – semua genap
Unit data masih boleh diterima walaupun mengandungi ralat.
Kelemahan VRC
VRC tidak boleh mengesan ralat meletus di mana bilangan bit yang berubah adalah genap.
Jika 2 bit berubah semasa transmisi, unit data dapat diluluskan semasa melalui pemeriksaan pariti walaupun unit data adalah rosak.
Ia juga benar untuk semua nombor genap yang berlaku ralat.
Longitudinal Redundancy Check (Semakan pariti 2-dimensi) Dalam LRC, blok bit disusun dalam bentuk jadual
(baris dan lajur) Contoh: selain menghantar satu blok yg
mengandungi 32 bit, ia boleh disusun dalam bentuk jadual yg terdiri drp 4 baris dan 8 lajur
Kemudian, kita mengira bit pariti utk setiap lajur dan menambah baris baru yg terdiri dari 8 bit, di mana merupakan bit pariti utk keseluruhan blok
Pariti bit pertama dalam baris ke-5 dikira berdasarkan semua bit pertama dlm setiap baris, pariti bit kedua dikira berdasarkan semua bit kedua dlm setiap baris dan seterusnya.
Kesemua 8 bit pariti disertakan bersama-sama dengan data asal dan dihantar ke penerima.
Longitudinal Redundancy Check
Original
Original Plus LRC
11100111
11011101
00111001
10101001
10101010LRC
Contoh LRC/2-dimensi
Andaikan blok di bawah dihantar:
Semasa transmisi, gangguan berlaku mengakibatkan beberapa bit berubah (‘burst error’)
Apabila penerima memeriksa LRC, sesetengah bit tidak mengikuti peraturan pariti genap, maka keseluruhan blok tidak diterima.
10101001 11001010 11000011 11100100 01000100
T e a r LRC
10100011 01111010 11000011 11100100 01000100
Q = a r LRC
10100011 01111010 11000011 11100100 01000100
Q = a r LRC
Prestasi LRC/2-dimensi
LRC meningkatkan keupayaan utk mengesan ‘burst errors’.
LRC dengan n bit mudah utk mengesan ‘burst error’ utk n bit.
Kelemahan: Jika dua bit dalam satu unit data rosak, dan 2 bit tsb berada pada posisi yg sama dlm unit data yg juga rosak, pemeriksaan LRC tidak dapat mengesan ralat.
Contoh, 2 unit data: 11110000 dan 11000011. Jika bit pertama dan bit terakhir dalam setiap unit
data di atas berubah, menjadikannya sebagai 01110001 dan 01000010, maka ralat tidak boleh dikesan oleh LRC.
Cyclical Redundancy Check (CRC)
Teknik pemeriksaan ralat yg terbaik menggunakan konsep pengulangan
Kaedah pengesanan ralat yang hampir tepat berdasarkan corak bit sebagai polinomial.
Ianya adalah berasaskan pembahagian perduaan Turutan bit pengulangan yg dinamakan sbg CRC
atau baki CRC, diletakkan bersama pada penghujung data unit supaya hasilnya boleh dibahagi dgn suatu nombor perduaan kedua (yg ditentukan)
CRC (samb…)
Pada destinasi, unit data yg diterima dibahagi dgn nombor perduaan tadi
Pada peringkat ini, jika tiada baki, unit data dikira tidak berubah dan diterima
Kehadiran baki menunjukkan bhw data unit telah rosak semasa penghantaran dan perli ditolak.
Bit pengulangan yg digunakan oleh CRC didapati drp membahagikan unit data dengan pembahagi, iaitu baki dalam CRC
Sebagai pengesahan, CRC mesti mempunyai dua kualiti. Ia mesti mempunyai kurang 1 bit drp
pembahagi, Menambahnya pd penghujung rentetan data
menghasilkan jujukan bit yg boleh dibahagi dgn tepat oleh pembahagi.
Proses CRC
1. Rentetan n bit 0 ditambah pd hujung unit data. n adalah suatu nombor yg kurang 1 drp bilangan bit yg terdapat dalam pembahagi (bil bit pembahagi = n+1)
2. Unit data yg terhasil (dr langkah 1.) dibahagi dengan pembahagi menggunakan proses pembahagian perduaan. Baki drp pembahagian ini merupakan CRC
3. CRC (Baki) bagi n bit yg didapati dalam langkah 2. akan menggantikan bit-bit 0 yang ditambah pd penghujung unit data (CRC mungkin juga suatu jujukan bit 0 cth : 0000)
Proses CRC (samb…)
Unit data tiba pada penerima, diikuti oleh CRC. Penerima mengambil keseluruhan jujukan bit yg diterima (unit data + CRC) dan membahagikannya dgn pembahagi yg sama utk mendapatkan baki CRC
Jika rentetan tiba tanpa ralat, penyemak CRC akan mendapati tiada baki (baki=0) dan unit data diterima
Jika rentetan berubah semasa transmisi, pembahagian menghasilkan baki dan unit data tidak diterima
Proses CRC
Pembahgian dlm penjana CRC
n+1 = 4 n = 3
Jika bit plg kiri bg baki = 0, guna pembhgi dgn semua bit 0 (dan bukan pembhgi asal)
Pembahagian dlm penyemak CRC
Polinomial mewakili pembahagi
Name Polynomial Application
CRC-8CRC-8 x8 + x2 + x + 1 ATM header
CRC-10CRC-10 x10 + x9 + x5 + x4 + x 2 + 1 ATM AAL
ITU-16ITU-16 x16 + x12 + x5 + 1 HDLC
ITU-32ITU-32x32 + x26 + x23 + x22 + x16 + x12 + x11 + x10 + x8 + x7 +
x5 + x4 + x2 + x + 1LANs
* Darjah polinomial = kuasa tertinggi
Prestasi CRC
CRC boleh mengesan semua ralat letusan yg mengubah bil bit yg ganjil
CRC boleh mengesan semua ralat letusan yg panjangnya <= darjah polinomial
CRC boleh mengesan hampir kesemua (99.97) ralat letusan yg panjangnya > darjah polinomial
Checksum/Jumlah semakan Juga berasaskan konsep pengulangan Ia dibentuk dengan menambah bit strim menggunakan
arithmetik komplimen 1 (one’s complement arithmetic) dan kemudian mengkomplimen hasilnya
Pada pengirim, pengeluar checksum membahagikan 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 penghujung data unit asal sbg bit pengulang, yang dikenali sebagai medan jumlah semakan (checksum field)
Checksum (samb…)
Data unit tsb dihantar melalui rangkaian. Jika jumlah segmen data adalah T, maka checksum
adalah –T. Penerima membahagikan 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 mengandungi ralat dan penerima menolak data tsb.
Pengirim mengikut langkah2 ini: Unit dibahagikan kpd k seksyen, setiap satu n bit. Semua seksyen 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 dibahagikan kpd k seksyen, setiap satu n bit. Semua seksyen 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 mengandungi 16 bit berikut dihantar menggunakan checksum 8 bit: 10101001 00111001
Nombor ditambah menggunakan 1’s complement arithmetic
Corak yg dihantar adalah: 10101001
00111001SUM 11100010CHECKSUM 00011101
10101001 00111001 00011101
checksum
Andaikan penerima menerima corak yg dihantar dan tidak mengandungi ralat: 10101001 00111001 00011101
Apabila penerima menambah tiga seksyen bersama2, ia akan mendapat semua nilai 1s, dan apabila dikomplimen, nilai menjadi 0s menunjukkan tiada ralat berlaku.
checksum
10101001
00111001
00011101SUM 11111111COMPLEMENT 00000000
Contoh Checksum (samb…)
Contoh Checksum (samb…)
Andaikan burst error berlaku sepanjang 5 bit yg mempengaruhi 4 bit: 10101111 11111001 00011101
Apabila penerima menambah 3 seksyen bersama-sama, ia akan mendapat:
Bermaksud data unit mengandungi ralat.
checksum
10101111
11111001
00011101
SUM 11000110
COMPLEMENT 00111001
Prestasi Checksum
Ia mengesan semua ralat termasuk bit nombor ganjil dan genap.
Walau bagaimanapun, jika satu atau lebih bit dalam satu segmen rosak, dan nilai bit yg sama yg terdapat bertentangan dalam segmen kedua juga rosak, dan jumlah dalam kolum tidak berubah, maka penerima tidak dapat mengesan ralat.
Kod Hamming
Ia bukan sekadar mengesan ralat, tetapi dapat juga membetulkan ralat dengan ketepatan 100%
Kod Hamming utk aksara ASCII 7-bit memerlukan 4 bit pariti, menjadikannya 11 bit
Bit pariti berada pada kedudukan 1,2,4,8 (2X), manakala bit data berada pada kedudukan 3,5,6,7,9,10,11
Ia juga membenarkan penyemakan pariti genap dan ganjil
Contoh Hamming Code
Andaikan aksara ‘A’ dihantar menggunakan hamming code: 1000001
Kedudukan 1,2,4,8 digunakan utk bit pariti, manakala kedudukan 3,5,6,7,9,10,11 digunakan utk bit data
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
Contoh Kod Hamming (genap)
Andaikan hamming code menggunakan pariti genap
Bit 1,3,5,7,9,11 disemak oleh bit pariti 1 (P1) Bit 2,3,6,7,10,11 disemak oleh bit pariti 2 (P2) Bit 4,5,6,7 disemak oleh bit pariti 4 (P4) Bit 8,9,10,11 disemak oleh bit pariti 8 (P8) Oleh itu bit 00100001001 dihantar
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
Bagaimana mengesan & membetulkan ralat?
Tentukan pariti mana yg mengesan ralat (jika semuanya tiada ralat maka penghantaran dianggap tiada ralat)
Jumlahkan lokasi pariti bit yg ralat (andaikan P2 dan P4)
Jumlah tersebut adalah lokasi ralat Tukarkan bit tersebut (jika 1 jadikan 0 dan
sebaliknya).
Andaikan hamming code menggunakan pariti genap dan bit yg dihantar mengandungi ralat
pariti 1 (P1) dan pariti 8 (P8) menyemak dan mendapati bil. bit 1 adalah genap. (tiada ralat)
pariti 2 (P2) dan pariti 4 (P4) menyemak dan mendapati bil. bit 1 adalah ganjil. (ada ralat)
Apabila kita menambah pariti yg mempunyai ralat (2+4=6), ia menunjukkan bit 6 tidak benar
Oleh itu bit pd kedudukan ke-6 ditukar dari bit 1 ke bit 0
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
P1=1,3,5,7,9,11P2=2,3,6,7,10,11
P4=4,5,6,7P8=8,9,10,11
Cyclical Parity (Pariti Kitaran)
Ia menggunakan 2 bit pengesan ralat. Melalui pariti bulatan, ia meningkatkan kecekapan
mengesan ralat. Ia juga mempunyai penyemakan pariti bulatan
genap dan ganjil. Setiap bit pariti menyemak bit-bit tertentu dalam
sesuatu bait. Contohnya, bit pariti pertama menyemak bit pada
lokasi 1,3,5,7 dan bit pariti kedua menyemak pada lokasi 2,4,6.
Contoh Pariti Bulatan (genap)
Andaikan, kita menggunakan pariti bulatan genap, dan rentetan data unit yang hendak dihantar adalah: 1000011
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).
Data unit P1 P2
1 0 0 0 0 1 1 0 1
P1 P2 P1 P2 P1 P2 P1 P1 P2
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