Hamming CodeDeteksi dan Koreksi Kesalahan dengan Contoh

Apa itu Kesalahan?

TransmitData yang dikirim dapat mengalami kerusakan selama komunikasi. Data tersebut kemungkinan terpengaruh oleh gangguan eksternal atau kegagalan fisik lainnya. Dalam situasi seperti itu, data masukan tidak mungkin sama dengan data keluaran. Ketidaksesuaian ini dikenal sebagai "Kesalahan."

Kesalahan data dapat menyebabkan hilangnya data penting atau data yang aman. Sebagian besar transfer data dalam sistem digital berbentuk "transfer bit," dan bahkan perubahan kecil pada satu bit saja dapat memengaruhi kinerja seluruh sistem. Dalam urutan data, jika angka 1 diubah menjadi 0, atau angka 0 diubah menjadi 1, hal itu disebut "kesalahan bit."

Jenis Kesalahan

Pada dasarnya ada tiga jenis kesalahan bit yang terjadi ketika data transmitdikirim dari pengirim ke penerima. Diagram di bawah ini menggambarkan bagaimana setiap jenis memengaruhi urutan data:

• Kesalahan bit tunggal
• Kesalahan beberapa bit
• Kesalahan meledak

Kesalahan Bit Tunggal

Perubahan yang dilakukan pada satu bit dalam keseluruhan rangkaian data dikenal sebagai "kesalahan satu bit". Terjadinya kesalahan satu bit tidak begitu umum. Hal ini sebagian besar terjadi dalam sistem komunikasi paralel, karena data ditransfer bit demi bit pada jalur terpisah, sehingga ada kemungkinan lebih tinggi bahwa satu jalur menjadi bising sementara jalur lainnya tetap bersih.

Kesalahan Beberapa Bit

Ketika dua bit atau lebih dari suatu urutan data berubah antara transmitPada terminal dan penerima, hal ini dikenal sebagai "kesalahan multi-bit."

Jenis kesalahan ini terjadi baik pada jaringan komunikasi data serial maupun paralel.

Kesalahan Meledak

Perubahan pada sekumpulan bit berurutan dalam suatu rangkaian data dikenal sebagai "kesalahan beruntun" (burst error). Panjang kesalahan beruntun diukur dari bit pertama yang berubah hingga bit terakhir yang berubah.

Apa itu Deteksi Kesalahan dan Koreksi Kesalahan?

Dalam sistem komunikasi digital, kesalahan dapat terjadi saat data berpindah dari satu perangkat ke perangkat lain. Jika kesalahan ini tidak terdeteksi dan diperbaiki, data akan hilang. Untuk komunikasi yang efektif, data harus ditransfer dengan akurasi tinggi, yang dicapai dengan terlebih dahulu mengidentifikasi kesalahan dan kemudian memperbaikinya.

Deteksi kesalahan adalah metode untuk menemukan kesalahan yang ada dalam data. transmitted dari sebuah transmitter ke penerima di komunikasi data sistem.

Kode redundansi digunakan untuk menemukan kesalahan ini dengan menambahkan bit tambahan ke data ketika data tersebut transmitDiambil dari sumbernya. Bagian tambahan ini disebut "kode pendeteksi kesalahan." Tiga jenis kode pendeteksi kesalahan yang paling umum adalah:

• Pengecekan Paritas
• Cyclic Redundancy Check (CRC)
• Pemeriksaan Redundansi Longitudinal (LRC)

Pengecekan Paritas

• Ini juga dikenal sebagai pemeriksaan paritas.
• Ini menyediakan mekanisme yang hemat biaya untuk deteksi kesalahan.
• Dalam teknik ini, bit redundan yang ditambahkan ke setiap unit data dikenal sebagai bit paritas. Bit ini diatur sedemikian rupa sehingga jumlah total angka 1 dalam unit menjadi genap (paritas genap) atau ganjil (paritas ganjil).

Pemeriksaan Redundansi Longitudinal

Dalam teknik deteksi kesalahan ini, blok bit disusun dalam sebuah tabel. Metode LRC menghitung bit paritas untuk setiap kolom, dan kumpulan bit paritas ini dikirim bersama dengan data asli. Blok bit paritas membantu penerima memeriksa redundansi dan mendeteksi kesalahan.

Pemeriksaan Redundansi Siklik

Cyclic Redundancy Check menambahkan serangkaian bit redundan ke akhir unit data sehingga unit data yang dihasilkan menjadi habis dibagi oleh bilangan biner kedua yang telah ditentukan sebelumnya.

Di tempat tujuan, data yang masuk dibagi dengan angka yang sama. Jika tidak ada sisa, unit data dianggap benar dan diterima. Jika tidak, itu menunjukkan bahwa unit data rusak selama transmisi, dan harus ditolak.

Apa itu Hamming? Code?

Kode Hamming adalah kode linier yang berguna untuk mendeteksi hingga dua kesalahan bit langsung dan mengoreksi kesalahan bit tunggal. Koreksi kesalahan jenis ini biasanya beroperasi pada lapisan tautan data, membingkai data dan memeriksa integritasnya antara node yang berdekatan.

Dalam kode Hamming, sumber mengkodekan pesan dengan menambahkan bit redundan. Bit redundan ini disisipkan dan dihasilkan pada posisi tertentu dalam pesan untuk melakukan proses deteksi dan koreksi kesalahan.

Sejarah Hamming Code

• Kode Hamming adalah teknik yang dikembangkan oleh RW Hamming untuk mendeteksi dan memperbaiki kesalahan.
• Metode ini dapat diterapkan pada unit data dengan panjang berapa pun dan menggunakan hubungan antara bit data dan bit redundansi.
• Hamming mengerjakan masalah koreksi kesalahan dan mengembangkan serangkaian algoritma yang semakin canggih.
• Pada tahun 1950, ia menerbitkan kode Hamming, yang masih banyak digunakan hingga saat ini dalam aplikasi seperti memori ECC.

Penerapan Hamming Code

Berikut beberapa aplikasi umum dari kode Hamming:

• Satelit
• Memori komputer (ECC RAM)
• modem
• Kamera Plasma
• Buka konektor
• Kawat terlindung
• Prosesor tertanam

Keuntungan dari Hamming Code

• Kode Hamming efektif pada jaringan di mana aliran data rentan terhadap kesalahan satu bit.
• Ini tidak hanya mendeteksi kesalahan bit tetapi juga membantu Anda mengidentifikasi bit yang mengandung kesalahan sehingga dapat diperbaiki.
• Kemudahan penggunaan kode Hamming membuatnya sangat cocok untuk memori komputer dan koreksi kesalahan tunggal.

Kelemahan Hamming Code

• Ini adalah kode deteksi dan koreksi kesalahan satu bit. Jika beberapa bit ditemukan salah, hasilnya dapat membalik bit lain yang sebenarnya benar, sehingga merusak data lebih lanjut.
• Algoritma kode Hamming hanya dapat menyelesaikan masalah bit tunggal.

Cara Mengenkode Pesan di Hamming Code

Proses yang digunakan pengirim untuk mengenkode pesan melibatkan tiga langkah berikut:

• Hitung jumlah total bit yang berlebihan.
• Tentukan posisi bit yang berlebihan.
• Hitung nilai setiap bit yang berlebihan.

Ketika bit-bit yang berlebihan disematkan di dalam pesan, kode kata lengkap akan dikirim ke penerima.

Langkah 1) Hitung jumlah total bit redundan.

Anggaplah pesan tersebut berisi n bit data dan p bagian yang berlebihan, ditambahkan sehingga 2^p dapat menunjukkan setidaknya (n + p + 1) keadaan yang berbeda.

Di sini, (n + p) memperhitungkan lokasi kesalahan di setiap posisi bit (n + p), dan satu keadaan tambahan menunjukkan tidak ada kesalahan. Karena p bit paritas dapat menunjukkan 2^p negara bagian, 2^p harus setidaknya sama dengan (n + p + 1).

Langkah 2) Tempatkan bagian-bagian yang berlebihan pada posisi yang tepat.

Bit-bit redundan p ditempatkan pada posisi bit yang merupakan pangkat 2 — misalnya, 1, 2, 4, 8, dan 16. Bit-bit ini disebut sebagai p.₁ (di posisi 1), hal₂ (di posisi 2), hal₃ (pada posisi 4), dan seterusnya.

Langkah 3) Hitung nilai setiap bit redundan.

Setiap bit redundan adalah bit paritas yang membuat jumlah angka 1 dalam kelompoknya menjadi genap atau ganjil. Dua jenis paritas tersebut adalah:

• Kesetaraan: Jumlah total angka 1 pada posisi yang tertutupi dibuat genap.
• Paritas ganjil: Jumlah total angka 1 pada posisi yang tertutupi dibuat ganjil.

Setiap bit paritas mencakup serangkaian posisi tertentu, yang ditentukan oleh representasi biner dari nomor posisi:

• p₁ Memeriksa setiap posisi yang nilai binernya memiliki angka 1 pada bit paling tidak signifikan — posisi 1, 3, 5, 7, 9, 11, dan seterusnya.
• p₂ Memeriksa setiap posisi yang nilai binernya memiliki angka 1 pada bit kedua dari kanan — posisi 2, 3, 6, 7, 10, 11, dan seterusnya.
• p₃ Memeriksa setiap posisi yang nilai binernya memiliki angka 1 pada bit ketiga dari kanan — posisi 4 hingga 7, 12 hingga 15, dan seterusnya.

Contoh yang dikerjakan (7,4): Perhatikan keempat bit data tersebut 1011Tiga bit paritas diperlukan (2³ = 8 ≥ 4 + 3 + 1), menghasilkan codeword tujuh bit yang disusun sebagai p₁ p₂ d₁ p₃ d₂ d₃ d₄. Penempatan data menghasilkan posisi 3, 5, 6, 7 = 1, 0, 1, 1. Menggunakan paritas genap: p₁ mencakup posisi 1, 3, 5, 7 (bit 1, 0, 1 → p₁ = 0); hal.₂ mencakup 2, 3, 6, 7 (bit 1, 1, 1 → p)₂ = 1); hal.₃ mencakup 4, 5, 6, 7 (bit 0, 1, 1 → p)₃ = 0). Yang transmitoleh karena itu kode rahasia ted adalah 0110011.

Cara Menerjemahkan Pesan di Hamming Code

Penerima menerima pesan yang masuk dan melakukan perhitungan ulang untuk menemukan dan memperbaiki kesalahan. Proses perhitungan ulang menggunakan langkah-langkah berikut:

• Hitung jumlah bit yang berlebihan.
• Atur posisi semua bagian yang berlebihan dengan benar.
• Lakukan pengecekan paritas.

Langkah 1) Hitung jumlah bit yang berlebihan. Gunakan rumus yang sama seperti untuk pengkodean: 2^p ≥ n + p + 1, di mana n adalah jumlah bit data dan p adalah jumlah bit redundan.

Langkah 2) Posisikan semua bit yang berlebihan dengan benar. Setiap bit redundan berada pada posisi bit yang merupakan pangkat 2 — misalnya, 1, 2, 4, dan 8.

Langkah 3) Lakukan pengecekan paritas. Bit paritas dihitung ulang dari bit data dan bit redundan yang diterima:

• p₁ = paritas(1, 3, 5, 7, 9, 11, …)
• p₂ = paritas(2, 3, 6, 7, 10, 11, …)
• p₃ = paritas(4–7, 12–15, 20–23, …)

Bit paritas yang dihitung ulang bersama-sama membentuk bilangan biner. Jika bilangan tersebut nol, tidak ada kesalahan; jika tidak, nilainya memberikan posisi pasti dari bit yang rusak, yang kemudian dibalik untuk memperbaiki pesan.

Pertanyaan Umum Demo Slot