Deteksi & Koreksi Kesalahan
Pendahuluan • Tujuan dalam komunikasi : data benar dan utuh • Masalah : Bit dapat terjadi kerusakan • Penyebab : • Korupnya data ketika ditransmisikan Thermal Noise Crosstalk (hub elektikal antar kabel) Atenuasi (lemah) Distorsi (penundaan/delay)
• Kesalahan dalam pengiriman frame
Ukuran lebih panjang dari frame Probabilitas frame yang diterima tanpa ada kesalahan rendah
• Akibatnya : Data yang diterima salah & tidak utuh
Solusi • Deteksi Kesalahan • Proses recovery kesalahan • Pembetulan kesalahan (correct error) • Pengiriman ulang (retransmision)
• Deteksi kesalahan : Ya dan tidak, tidak perduli letak error • Koreksi : perlu mengetahui jumlah dan posisi • Retransmision : receiver mendeteksi kesalahan dan meminta pengiriman ulang
Tipe Kesalahan (A) A. Single-bit errors
Biasanya terjadi pada komunikasi pararel Hanya 1 bit yang salah/rusak
4
Tipe Kesalahan (B) B. Burst errors
Biasanya terjadi pada komunikasi serial Data korup lebih dari 1 Terjadi ketika durasi noise lebih panjang dari durasi pengiriman 1’s bit
Deteksi Kesalahan & Koreksi • Permasalahan : Deteksi kesalahan pada frame • Solusi : tambahkan bit ekstra untuk setiap paket • Tujuan: Mengurangi jumlah redundansi(diulang) bit, overhead biaya dapat dikurangi Meningkatkan jumlah dan pola bit salah yang dapat dideteksi
• Metode : Kesalahan Simple parity check Two-dimensional parity Checksum Cyclic Redundancy Check (CRC)
Koreksi Hamming Codes
M
FCS(frame check sequence)
Parity Check • Metode paling populer dan sederhana dalam mendeteksi kesalahan • Menambahkan parity bit pada data • Contoh : 1 0
0 0
1 1
1 0 0 1 0 even 1 1 0 1 1 odd
Tak asinkron : odd parity (ganjil) Asinkron : even parity (genap)
Parity check • Bit parity merupakan bilangan biner yang ditambahkan untuk meyakinkan bahwa jumlah bit yang dikirimkan mempunyai angka satu yang selalu genap atau ganjil. • Terdiri dari : • even parity bit • odd parity bit.
Parity Checking:
Even dan Odd Parity • Even parity bit diset ke 1 jika jumlah angka 1 yang dikirimkan berjumlah ganjil (berarti membuat total angka 1 berjumlah genap). • Odd parity bit akan diset ke 1 jika jumlah angka 0 yang dikirimkan berjumlah genap (berarti membuat total angka 1 berjumlah ganjil).
• Event Parity Bit, nilai parity bit sama dengan hasil peng-XOR an. • Odd Parity Bit, Nilai parity bit merupakan komplement( kebalikan ) dari hasil peng-XOR an data. • ODD PARITY (Parity Ganjil), Jika data direkam dengan menggunakan odd parity, maka jumlah 1 bit yang merepresentasikan suatu karakter adalah ganjil. Jika jumlah 1 bitnya sudah ganjil, maka parity bit yang terletak pada track ke-n adalah 0 bit, akan tetapi jika jumlah 1 bitnya masih genap maka parity bitnya adalah 1 bit. • EVEN PARITY ( Parity Genap), Bila kita merekam data dengan menggunakan even parity, maka jumlah 1 bit yang merepresentasikan suatu karakter adalah genap jika jumlah 1 bitnya sudah genap, maka parity bit yang terletak pada track ke-n adalah 0 bit, akan tetapi jika jumlah 1 bitnya masih ganjil maka parity bitnya adalah 1 bit.
Pernyataan mana yg benar ?? Karakter
ASCII
Pariti Ganjil
K
100 1011
0100 1011
J
100 1010
1100 1010
T
101 0100
0101 0100
Hardware Pembangkit Bit Parity
A
B
C
D
E
F
jika bit 1 pada data berjumlah genap maka keluaran ahirnya pasti "0", jika ganjil maka "1"
Gerbang X-OR
Contoh (data asli: 1010000) Gerbang
Input
Output
A
00
0
B
00
0
C
00
0
D
10
1
E
01
1
F
11
0
Jika tidak ada kesalahan kondisi tetap terpenuhi dengan gerbang G mempunyai masukan 0 dan 0 outputnya adalah 0
Contoh dengan 1 kesalahan (data asli: 1010000) Gerbang
input
output
A
00
0
B
00
0
C
00
0
D
10
1
E
11
0
F
10
1
G
01
1
Contoh kesalahan 2 (data asli: 1010000) Gerbang
Input
Output
A
00
0
B
10
1
C
01
1
D
11
0
E
10
1
F
11
0
G
00
0
Hasil akhir adalah 0 (indikasi benar) tetapi salah karena isyarat yang diterima 01110100
Contoh Kasus • Pengirim Ingin mengirimkan Kata “world". Kodekan ke kode ASCII diperoleh: 1110111 1101111 1110010 1101100 1100100
• Dikirim dengan penambahan even parity: 11101110 11011110 11100100 11011000 11001001
Latihan : • Johan dan Budi sedang berkomunikasi dengan sistem sms, keduanya saling berkirim pesan dengan metode berkirim teks. Salah satu teks yang dikirim adalah Aku. Perkirakan data yang dikirim dalam bit agar sampai ke tujuan dengan benar. Asumsikan Metode Pendeteksian Error = Parity Check (even parity bit) • A = 1000001 k = 1101011 u = 1010111
Jawab : • Konversi ke kode ASCII A = 1000001 k = 1101011 u = 1010111 • Dalam terminal Pengirim, Kata "Aku" Dianalisa Perkarakter "A" lalu "k" lalu "u". Dari masing masing huruf itu Masing masing ditambahkan dengan parity bit nya ( Asumsikan kita menggunakan Even Parity Bit ) Maka Data Akan berubah menjadi: • (A = 1000001 Setelah Di XOR kan, Hasilnya "0" Karena kita menggunakan metode Even Parity Bit maka Parity Bitnya Bernilai "0", maka Kode biner huruf "A" ditambah menjadi A = 10000010) A = 10000010 k = 11010111 u = 10101111
Two Dimensional Parity (Paritas Blok) • Pesan dibagi menjadi beberapa blok • Setiap blok memiliki karakter pemeriksa blok (block check character) • Berupa bit parity (even atau odd parity)
Contoh • 7 Bit karakter per paket, metode even parity 0
1 1
1 0
0
1
1 1
0 0
0 1
0
0 0
1
1 1
1
0
1 0
0 0
1
1
0
1
1
0
1
1
LRC = longitudina l Redudancy char= block BCC
0
check character (diakhir)
1
0
1
1
1
0
0
0
1
1
BCC= 10001101
0
1
LRC
0
1
Dulu : 7 x 5 Sekarang : 8x6
Data yang dikirim 01101001:10110100:00101101:11101010:10010110:10001101
Deteksi 1 bit error
Deteksi 2 bit Error
Deteksi 3 Bit error
Deteksi 4 bit error • Tidak terdeteksi
Latihan Diketahui Data Asli : 1011011 : 1010101 : 0101101 : 1101010 Gunakan metode Two dimensional Parity untuk mengetahui data yang akan dikirim. Gunakan even parity
Checksum • Metode yang digunakan untuk mendeteksi kesalahan pada sistem komunikasi • Analogi : Terdapat data : 7, 5, 20, 2, 4 Jumlahkan : 7 + 5 + 20 + 2 + 4 = ?
38 Berarti untuk checksum adalah -38 Jadi data akan menjadi 7,5,20,2,4,-38
Contoh 1 • Contoh : 22 • Konversi ke biner 10110 1
0
1
1
0
1 +
1’s Complemen
0
1
1
1
= 7 (sum )
1
0
0
0
= 8
2ˆn -1 = 2ˆ4 -1 = 15
Jadi 15-7 = 8
Contoh 2 • Sisi Pengirim • Data 5, 7, 8, 1, 17 • Sum : 5+7+8+1+17=38 • Konversi 38 ke Biner = 100110 1 0
0 1 1 0 1 0
+ 1 0 0 0
1’s complement
0 1 11
= 8 (wrapped sum)
Checksum= 7
Contoh 2 (cont…) • Sisi penerima • Data + checksum => 5, 7, 8, 1, 17, 7 • Lakukan sum = 45 • Konversi 45 ke biner = 101101 1 0
1 1 0 1 1 0
+ 1 1 1 1 1’s complement
0 0 0 0
= 15 Checksum= 00
0 berarti tidak ada error
Latihan Checksum • Diketahui data yang akan dikirim sebagai berikut: 10110011101010110101101011010101 • Cari checksumnya pada sisi sender • Buktikan checksum benar pada posisi penerima
Kode Hamming • Diciptakan Richard Hamming di Bell Lab 1950 • Mekanisme pendeteksian kesalahan dengan menambahkan data word (D) dengan suatu kode, biasanya bit cek paritas (C). • Data yang disimpan memiliki panjang D + C. • Kesalahan diketahui dengan menganalisa data dan bit paritas tersebut • Kode Hamming mampu mendeteksi dan mengetahui posisi 1 bit yang salah di penerima • kekurangan dari metode Hamming Code adalah tidak dapat mendeteksi bila terjadi dua buah kesalahan sekaligus
Penulisan • Penulisan : Hamming (7,4) • 4 data bits • 3 parity bits
• Cara menetukan bit parity (2ˆk)-1 >= m+k dengan k= n check bit m = banyaknya word
Even Parity • 101101_? • 111000_?
Bila Bit paritas = 4, maka Jumlah bit informasi yg akan dikirim atau diterima adalah = (2^4) – 4 – 1 = 16 – 5 = 11 Sehingga urutan bit nya :
C1 C2 D1 C3 D2 D3 D4 C4 D5 D6 D7 1
2
3
4
5
6
7
8
9
10
11
Kode Hamming
Kode Hamming • Bit cek paritas ditempatkan dengan perumusan 2^N dimana N = 0,1,2, ……, sedangkan bit data adalah sisanya. Kemudian dengan exclusive-OR dijumlahkan: C1 = D1 D2 D4 D5 D7 C2 = D1 D3 D4 D6 D7 C3 = D2 D3 D4 C4 = D5 D6 D7
• Setiap cek bit (C) beroperasi pada setiap posisi bit data yang nomor posisinya berisi bilangan 1 pada kolomnya
Bit cek paritas • Ilustrasi keterkaitan (data : 1000) C1/P1
D1
D2 D4
C2/P2
D3
C3/P3
Kode Hamming • masukkan data : 00111001 kemudian ganti bit data ke 3 dari 0 menjadi 1 sebagai error-nya. 00111101 • Bagaimanakah cara mendapatkan bit data ke 3 sebagai bit yang terdapat error?
Kode Hamming Jawab : Masukkan data pada perumusan cek bit paritas : C1 = 1 0 1 1 0 = 1 C2 = 1 0 1 1 0 = 1 C3 = 0 0 1 =1 C4 = 1 1 0 =0 Sekarang bit 3 mengalami kesalahan data menjadi: 00111101 C1 = 1 0 1 1 0 = 1 C2 = 1 1 1 1 0 = 0 C3 = 0 1 1 =0 C4 = 1 1 0 =0
Kode Hamming Apabila bit – bit cek dibandingkan antara yang lama dan baru maka terbentuk syndrom word : C4 C3 C2 C1 0 1 1 1 0 0 0 1 (EX-OR) 0 1 1 0 =6 Sekarang kita lihat posisi bit ke-6 adalah data ke-3.
C1 C2 D1 C3 D2 D3 D4 C4 D5 D6 D7 0 0 1 1 1 1 0 1 Data asli yang dikirim adalah = D1 D2 D3 D4 1 1 1 0
Contoh Kasus • Data 1011
Pengirim
1010101 ?
Penerima
Latihan • Di sisi penerima menerima data berupa 7 bit hamming kode sebagai berikut: 1011011 Dengan asumsi menggunakan even parity, apakah data yang diterima tersebut benar atau salah Jika salah posisi bit nya berada pada posisi? Tampilkan data sesungguhnya
