Deteksi Kesalahan & Kode Koreksi
Kita tahu bahwa bit 0 dan 1 sesuai dengan dua rentang tegangan analog yang berbeda. Jadi, selama transmisi data biner dari satu sistem ke sistem lainnya, noise juga dapat ditambahkan. Karena itu, mungkin ada kesalahan dalam data yang diterima di sistem lain.
Itu berarti bit 0 bisa berubah menjadi 1 atau bit 1 bisa berubah menjadi 0. Kita tidak bisa menghindari interferensi noise. Tapi, kita bisa mendapatkan kembali data asli terlebih dahulu dengan mendeteksi apakah ada kesalahan dan kemudian mengoreksi kesalahan tersebut. Untuk tujuan ini, kita dapat menggunakan kode-kode berikut.
- Kode deteksi kesalahan
- Kode koreksi kesalahan
Error detection codes- digunakan untuk mendeteksi kesalahan yang ada dalam data yang diterima (aliran bit). Kode-kode ini berisi beberapa bit, yang disertakan (ditambahkan) ke aliran bit asli. Kode-kode ini mendeteksi kesalahan, jika itu terjadi selama transmisi data asli (aliran bit).Example - Kode paritas, kode Hamming.
Error correction codes- digunakan untuk memperbaiki kesalahan yang ada pada data yang diterima (aliran bit) sehingga kita akan mendapatkan data asli. Kode koreksi kesalahan juga menggunakan strategi serupa dari kode deteksi kesalahan.Example - Kode Hamming.
Oleh karena itu, untuk mendeteksi dan memperbaiki kesalahan, bit tambahan ditambahkan ke bit data pada saat transmisi.
Kode Paritas
Sangat mudah untuk memasukkan (menambahkan) satu bit paritas baik di sebelah kiri MSB atau di sebelah kanan LSB dari aliran bit asli. Ada dua jenis kode paritas yaitu kode paritas genap dan kode paritas ganjil berdasarkan jenis paritas yang dipilih.
Bahkan Kode Paritas
Nilai bit paritas genap harus nol, jika bilangan genap yang ada dalam kode biner. Jika tidak, itu harus menjadi satu. Sehingga, jumlah yang genap ada dieven parity code. Bahkan kode paritas berisi bit data dan bahkan bit paritas.
Tabel berikut menunjukkan even parity codessesuai dengan setiap kode biner 3-bit. Di sini, bit paritas genap disertakan di sebelah kanan LSB kode biner.
| Kode biner | Bahkan paritas sedikit | Bahkan Kode Paritas |
|---|---|---|
| 000 | 0 | 0000 |
| 001 | 1 | 0011 |
| 010 | 1 | 0101 |
| 011 | 0 | 0110 |
| 100 | 1 | 1001 |
| 101 | 0 | 1010 |
| 110 | 0 | 1100 |
| 111 | 1 | 1111 |
Di sini, jumlah bit yang ada dalam kode paritas genap adalah 4. Jadi, kemungkinan bilangan genap yang ada dalam kode paritas genap ini adalah 0, 2 & 4.
Jika sistem lain menerima salah satu dari kode paritas genap ini, maka tidak ada kesalahan dalam data yang diterima. Bit selain bit paritas genap sama dengan bit kode biner.
Jika sistem lain menerima selain kode paritas genap, maka akan ada kesalahan dalam data yang diterima. Dalam kasus ini, kami tidak dapat memprediksi kode biner asli karena kami tidak mengetahui posisi bit kesalahan.
Oleh karena itu, bit paritas genap hanya berguna untuk mendeteksi kesalahan dalam kode paritas yang diterima. Tapi, itu tidak cukup untuk memperbaiki kesalahannya.
Kode Paritas Ganjil
Nilai bit paritas ganjil harus nol, jika bilangan ganjil ada dalam kode biner. Jika tidak, itu harus menjadi satu. Sehingga, ada jumlah ganjil yang masukodd parity code. Kode paritas ganjil berisi bit data dan bit paritas ganjil.
Tabel berikut menunjukkan odd parity codessesuai dengan setiap kode biner 3-bit. Di sini, bit paritas ganjil dimasukkan di sebelah kanan LSB kode biner.
| Kode biner | Bit Paritas Ganjil | Kode Paritas Ganjil |
|---|---|---|
| 000 | 1 | 0001 |
| 001 | 0 | 0010 |
| 010 | 0 | 01.00 |
| 011 | 1 | 0111 |
| 100 | 0 | 1000 |
| 101 | 1 | 1011 |
| 110 | 1 | 1101 |
| 111 | 0 | 1110 |
Di sini, jumlah bit yang ada dalam kode paritas ganjil adalah 4. Jadi, kemungkinan jumlah ganjil yang ada dalam kode paritas ganjil ini adalah 1 & 3.
Jika sistem lain menerima salah satu dari kode paritas ganjil ini, maka tidak ada kesalahan dalam data yang diterima. Bit selain bit paritas ganjil sama dengan bit kode biner.
Jika sistem lain menerima selain kode paritas ganjil, maka ada kesalahan pada data yang diterima. Dalam kasus ini, kami tidak dapat memprediksi kode biner asli karena kami tidak mengetahui posisi bit kesalahan.
Oleh karena itu, bit paritas ganjil hanya berguna untuk mendeteksi kesalahan dalam kode paritas yang diterima. Tapi, itu tidak cukup untuk memperbaiki kesalahannya.
Kode Hamming
Kode Hamming berguna untuk mendeteksi dan mengoreksi kesalahan yang ada dalam data yang diterima. Kode ini menggunakan beberapa bit paritas dan kita harus menempatkan bit paritas ini pada posisi pangkat 2.
Itu minimum value of 'k' yang mana relasi berikut benar (valid) tidak lain adalah jumlah bit paritas yang diperlukan.
$$ 2 ^ k \ geq n + k + 1 $$
Dimana,
'n' adalah jumlah bit dalam kode biner (informasi)
'k' adalah jumlah bit paritas
Oleh karena itu, jumlah bit pada kode Hamming sama dengan n + k.
Biarkan Hamming codeadalah $ b_ {n + k} b_ {n + k-1} ..... b_ {3} b_ {2} b_ {1} $ & bit paritas $ p_ {k}, p_ {k-1}, .... p_ {1} $. Kita dapat menempatkan bit paritas 'k' dalam pangkat 2 posisi saja. Dalam posisi bit yang tersisa, kita dapat menempatkan bit 'n' dari kode biner.
Berdasarkan kebutuhan, kita dapat menggunakan paritas genap atau paritas ganjil saat membentuk kode Hamming. Namun, teknik paritas yang sama harus digunakan untuk menemukan apakah ada kesalahan dalam data yang diterima.
Ikuti prosedur ini untuk menemukan parity bits.
Temukan nilai p1, berdasarkan jumlah yang ada di posisi bit b 3 , b 5 , b 7, dan seterusnya. Semua posisi bit ini (sufiks) dalam biner ekivalennya memiliki '1' di nilai tempat 2 0 .
Temukan nilai p2, berdasarkan jumlah yang ada di posisi bit b 3 , b 6 , b 7, dan seterusnya. Semua posisi bit ini (sufiks) dalam biner yang setara memiliki '1' di nilai tempat 2 1 .
Temukan nilai p3, berdasarkan jumlah yang ada di posisi bit b 5 , b 6 , b 7 dan seterusnya. Semua posisi bit ini (sufiks) dalam biner yang setara memiliki '1' di tempat nilai 2 2 .
Demikian pula, temukan nilai lain dari bit paritas.
Ikuti prosedur ini untuk menemukan check bits.
Tentukan nilai dari c 1 , berdasarkan jumlah yang ada di posisi bit b 1 , b 3 , b 5 , b 7 dan seterusnya. Semua posisi bit ini (sufiks) dalam biner ekivalennya memiliki '1' di nilai tempat 2 0 .
Tentukan nilai dari c 2 , berdasarkan banyaknya yang ada di posisi bit b 2 , b 3 , b 6 , b 7 dan seterusnya. Semua posisi bit ini (sufiks) dalam biner yang setara memiliki '1' di nilai tempat 2 1 .
Tentukan nilai dari c 3 , berdasarkan jumlah yang ada di posisi bit b 4 , b 5 , b 6 , b 7 dan seterusnya. Semua posisi bit ini (sufiks) dalam biner yang setara memiliki '1' di tempat nilai 2 2 .
Demikian pula, temukan nilai lain dari bit cek.
Setara desimal dari bit cek dalam data yang diterima memberikan nilai posisi bit, di mana ada kesalahan. Lengkapi saja nilai yang ada di posisi bit itu. Oleh karena itu, kita akan mendapatkan kode biner asli setelah menghapus bit paritas.
Contoh 1
Mari kita cari kode Hamming untuk kode biner, d 4 d 3 d 2 d 1 = 1000. Pertimbangkan bit paritas genap.
Jumlah bit dalam kode biner yang diberikan adalah n = 4.
Kita dapat menemukan jumlah bit paritas yang dibutuhkan dengan menggunakan relasi matematis berikut.
$$ 2 ^ k \ geq n + k + 1 $$
Gantikan, n = 4 pada relasi matematika di atas.
$$ \ Panah Kanan 2 ^ k \ geq 4 + k + 1 $$
$$ \ Panah Kanan 2 ^ k \ geq 5 + k $$
Nilai minimum k yang memenuhi relasi di atas adalah 3. Oleh karena itu, diperlukan 3 bit paritas p 1 , p 2 , dan p 3 . Oleh karena itu, jumlah bit pada kode Hamming adalah 7, karena terdapat 4 bit pada kode biner dan 3 bit paritas. Kita harus menempatkan bit paritas dan bit kode biner dalam kode Hamming seperti yang ditunjukkan di bawah ini.
Itu 7-bit Hamming code adalah $ b_ {7} b_ {6} b_ {5} b_ {4} b_ {3} b_ {2} b_ {1} = d_ {4} d_ {3} d_ {2} p_ {3} h_ {1 } p_ {2} bp_ {1} $
Dengan mengganti bit kode biner, kode Hamming akan menjadi $ b_ {7} b_ {6} b_ {5} b_ {4} b_ {3} b_ {2} b_ {1} = 100p_ {3} Op_ {2 } p_ {1} $. Sekarang, mari kita temukan bit paritas.
$$ p_ {1} = b_ {7} \ oplus b_ {5} \ oplus b_ {3} = 1 \ oplus 0 \ oplus 0 = 1 $$
$$ p_ {2} = b_ {7} \ oplus b_ {6} \ oplus b_ {3} = 1 \ oplus 0 \ oplus 0 = 1 $$
$$ p_ {3} = b_ {7} \ oplus b_ {6} \ oplus b_ {5} = 1 \ oplus 0 \ oplus 0 = 1 $$
Dengan mengganti bit paritas ini, file Hamming code akan menjadi $ b_ {7} b_ {6} b_ {5} b_ {4} b_ {3} b_ {2} b_ {1} = 1001011 $.
Contoh 2
Dalam contoh di atas, kita mendapatkan kode Hamming sebagai $ b_ {7} b_ {6} b_ {5} b_ {4} b_ {3} b_ {2} b_ {1} = 1001011 $. Sekarang, mari kita cari posisi kesalahan ketika kode yang diterima adalah $ b_ {7} b_ {6} b_ {5} b_ {4} b_ {3} b_ {2} b_ {1} = 1001111 $.
Sekarang, mari kita cari bit ceknya.
$$ c_ {1} = b_ {7} \ oplus b_ {5} \ oplus b_ {3} \ oplus b_ {1} = 1 \ oplus 0 \ oplus 1 \ oplus1 = 1 $$
$$ c_ {2} = b_ {7} \ oplus b_ {6} \ oplus b_ {3} \ oplus b_ {2} = 1 \ oplus 0 \ oplus 1 \ oplus1 = 1 $$
$$ c_ {3} = b_ {7} \ oplus b_ {6} \ oplus b_ {5} \ oplus b_ {4} = 1 \ oplus 0 \ oplus 0 \ oplus1 = 0 $$
Nilai desimal dari bit cek memberikan posisi kesalahan dalam kode Hamming yang diterima.
$$ c_ {3} c_ {2} c_ {1} = \ kiri (011 \ kanan) _ {2} = \ kiri (3 \ kanan) _ {10} $$
Oleh karena itu, kesalahan ada di bit ketiga (b 3 ) kode Hamming. Lengkapi saja nilai yang ada dalam bit itu dan hapus bit paritas untuk mendapatkan kode biner asli.