metode hamming gapra - gapra.files.wordpress.com · pendeteksian kesalahan dan mekanisme perbaikan...
TRANSCRIPT
Metode Hamming by Gapra 1
METODE HAMMING
By Galih Pranowo
Emailing [email protected]
PENDAHULUAN
Dalam era kemajuan teknologi komunikasi digital, maka persoalan yang utama
adalah bagaimana menyandikan isyarat analog menjadi isyarat digital yang berupa sandi
biner. Isyarat sandi biner ini diharapkan kebal terhadap gangguan pengiriman dan
mempunyai pesat informasi optimum.
Dalam melaksanakan fungsi penyimpanan, memori semikonduktor
dimungkinkan mengalami kesalahan. Baik kesalahan berat yang biasanya merupakan
kerusakan fisik memori maupun kesalahan ringan yang berhubungan data yang
disimpan. Kesalahan ringan dapat dikoreksi kembali. Untuk mengadakan koreksi
kesalahan data yang disimpan diperlukan dua mekanisme, yaitu mekanisme
pendeteksian kesalahan dan mekanisme perbaikan kesalahan.
Mekanisme pendeteksian kesalahan dengan menambahkan data word (D) dengan
suatu kode, biasanya bit cek paritas (C). Sehingga data yang disimpan memiliki panjang
D + C. Kesalahan akan diketahui dengan menganalisa data dan bit paritas tersebut.
Mekanisme perbaikan kesalahan yang paling sederhana adalah kode Hamming. Metode
ini diciptakan Richard Hamming di Bell Lab pada tahun 1950.
Untuk mengurangi bahkan menghilangkan kesalahan sandi biner dapat juga
mengggunakan metode Hamming. Dalam tulisan ini akan dibahas untuk koreksi galat
satu digit dan koreksi kesalahan untuk word data.
Metode Hamming by Gapra 2
METODE HAMMING
PENGENDALIAN GALAT SANDI BINER
Banyak ragam cara pengendalian galat sandi biner, diantaranya adalah dengan
cara “Hamming”, “Block Coding” dan sebagainya. Dalam tulisan ini dibahas salah satu
cara pengendalian galat untuk satu digit kesalahan dengan metode Hamming, yang
merupakan matrix H untuk melacak kesalahan sandi yang diterima.
Sandi digital yang dikirimkan sebagai pulsa angka “0” dan angka “1” agar dapat
dikoreksi galat yang mungkin terjadi pada penerima perlu disandikan kembali
menggunakan metode Hamming. Dipilih matrix Ħ yang menghasikan H.T = 0, dengan
T adalah vektor yang elemen-elemennya merupakan sandi digital yang akan dikirimkan.
Matrix H terdiri dari r kolom matrix diagonal dan n kolom matrix sembarang, dengan n
adalah cacah digit digital yang akan dikirimkan.
Pada pesawat penerima atau pengawa-sandian, isyarat yang diterima, dimisalkan
sebagai vektor R, dikalikan kembali dengan matrix H dan menghasilkan isyarat sindrom
S. Bila S = H.R = 0, berarti isyarat yang diterima sudah benar atau cocok dengan isyarat
yang dikirimkan. Tetapi jika S = H.R ≠ 0, berarti isyarat yang diterima ada kesalahan.
Kesalahan yang terjadi bisa dilihat dari isyarat sindrom yang terbentuk. Dengan
mencocokan isyarat sindrom dengan matrix H akan dapat diketahui kesalahan yang
terjadi pada angka ke berapa. Sebagai contoh, jika isyarat sindrom cocok dengan kolom
ke 5, berarti kesalahan terjadi pada angka ke 5 dari pesan yang dikirimkan.
Diatas telah disebutkan bahwa matrix H bisa dipilih sembarang, dengan
ketentuan tidak boleh ada kolom yang mempunyai elemen-elemen persis sama. Dengan
alasan inilah, maka matrix H dipilih sebagai berikut :
1 1 0 1 0 1 0 0 0
1 0 1 1 0 0 1 0 0
1 1 0 0 1 0 0 1 0
1 0 1 0 1 0 0 0 1
H =
Metode Hamming by Gapra
CONTOH PENENTUAN SANDI BARU DENGAN METODE HAMMING
Misal akan dicari sandi baru untuk pesan A yang mempunyai sandi lama 01101.
perkalian matrix H dengan vektor T, yang mempunyai 5 elemen pertama sama dengan
sandi lama yang akan diubah dan 4 elemen berikutnya adalah elemen yang akan dicari
nilainya, dapat dinyatakan sebagai berikut :
1 1 0 1 0 1 0 0 0 0
1 0 1 1 0 0 1 0 0 0
1 1 0 0 1 0 0 1 0 0
1 0 1 0 1 0 0 0 1 0
Dari hasil perkalian diatas diperoleh nilai
C1 = 1 C3 = 0
C2 = 1 C4 = 0
Sandi baru diperoleh dengan menggabungkan sandi lam
diperoleh dari perhitungan diatas. Dengan demikian san
011011100. Sandi baru untuk ke 32 pesan diatas dapat di
Tabel Sandi Lama dan Sandi
Pesan Sandi Lama S
A 01101 0B 00001 0C 00010 0D 00011 0E 00100 0F 00101 0G 00110 0H 00111 0I 10010 1J 01001 0
T = =
01101
C1C2C3
3
a dengan 4 elemen baru yang
di baru untuk pesan A adalah
lihat pada tabel dibawah ini.
Baru
andi Baru
11011100000100110010110000111111010001010101011001101001011110100010001110011001
C4
Metode Hamming by Gapra 4
Pesan Sandi Lama Sandi Baru
K 01010 010100110L 11010 110101001M 01011 010110101N 11101 111010011O 11100 111000000P 11110 111101100Q 11001 110010110R 11000 110000101S 10101 101011001T 10100 101001010U 11011 110111010V 00000 000000000W 01000 010001010X 11111 111111111Y 10110 101100110Z 10111 101110101. 01100 011001111, 10011 100110000? 01110 011100011! 10001 100011100: 01111 011110000= 10000 100001111
CONTOH PELACAKAN KESALAHAN
Dikirimkan suatu pesan yang oleh penerima pesan tersebut diterima sebagai
sandi 101111111. Untuk melihat apakah pesan ini benar atau tidak, maka pesan yang
diterima tersebut harus dicek.
Untuk mengecek sandi yang diterima, perlu dicari isyarat sindrom, yaitu
perkalian antara matrix H dengan sandi yang diterima. Hasil perkaliannya adalah
sebagai berikut :
Metode Hamming by Gapra
1 1 0 1 0 1 0 0 0
1 0 1 1 0 0 1 0 0
1 1 0 0 1 0 0 1 0
1 0 1 0 1 0 0 0 1
Isyarat sindrom yang diperoleh dari perhitungan diatas ada
sindrom ini dicocokan dengan matrix H, terlihat bahwa i
kolom ke 2. Dengan demikian, kesalahan terjadi pada ang
harus diubah menjadi angka “1”.
METODE HAMMING
KOREKSI ERROR
Mekanisme pendeteksian kesalahan dengan menam
suatu kode, biasanya bit cek paritas (C). Sehingga data yan
D + C. Kesalahan akan diketahui dengan menganalisa
Mekanisme perbaikan kesalahan yang paling sederhana ada
1011111
5
lah [ 1 0 1 0 ] -1. Jika isyarat
syarat sindrom cocok dengan
ka ke 2, yaitu dari angka “0”
bahkan data word (D) dengan
g disimpan memiliki panjang
data dan bit paritas tersebut.
lah kode Hamming.
11
Metode Hamming by Gapra 6
Perhatikan gambar diatas, disajikan tiga lingkaran Venn (A, B, C) saling
berpotongan sehingga terdapat 7 ruang. Metode diatas adalah koreksi kesalahan untuk
word data 4 bit (D =4). Gambar (a) adalah data aslinya. Kemudian setiap lingkaran
harus diset bit logika 1 berjumlah genap sehingga harus ditambah bit – bit paritas pada
ruang yang kosong seperti gambar (b). Apabila ada kesalahan penulisan bit pada data
seperti gambar (c) akan dapat diketahui karena lingkaran A dan B memiliki logika 1
berjumlah ganjil.
Lalu bagaimana dengan word lebih dari 4 bit ? Ada cara yang mudah yang akan
diterangkan berikut. Sebelumnya perlu diketahui jumlah bit paritas yang harus
ditambahkan untuk sejumlah bit word. Contoh sebelumnya adalah koreksi kesalahan
untuk kesalahan tunggal yang sering disebut single error correcting (SEC). Jumlah bit
paritas yang harus ditambahkan lain pada double error correcting (DEC). Tabel
dibawah ini menyajikan jumlah bit paritas yang harus ditambahkan dalam sistem kode
Hamming.
Tabel Penambahan bit cek paritas untuk koreksi kode Hamming
# Data Bits # Bit Paritas SEC # Bit Paritas DEC
8 4 5
16 5 6
32 6 7
64 7 8
128 8 9
512 9 10
CONTOH KOREKSI KODE HAMMING 8 BIT DATA
Dari tabel yang disajikan diatas untuk 8 bit data diperlukan 4 bit tambahan
sehingga panjang seluruhnya adalah 12 bit.
Layout bit disajikan seperti dibawah ini :
Metode Hamming by Gapra 7
Bit cek paritas ditempatkan dengan perumusan 2N dimana N = 0,1,2, ……, sedangkan
bit data adalah sisanya. Kemudian dengan exclusive-OR dijumlahkan ebagai berikut :
Setiap cek bit (C) beroperasi pada setiap posisi bit data yang nomor posisinya berisi
bilangan 1 pada kolomnya. Sekarang ambil contoh suatu data, misalnya masukkan data :
00111001 kemudian ganti bit data ke 3 dari 0 menjadi 1 sebagai error-nya.
Bagaimanakah cara mendapatkan bit data ke 3 sebagai bit yang terdapat error?
Jawaban :
Masukkan data pada perumusan cek bit paritas :
Metode Hamming by Gapra 8
Sekarang bit 3 mengalami kesalahan sehingga data menjadi: 00111101
Apabila bit – bit cek dibandingkan antara yang lama dan baru maka terbentuk syndrom
word :
Sekarang kita lihat posisi bit ke-6 adalah data ke-3.
Mekanisme koreksi kesalahan akan meningkatkan realibitas bagi memori tetapi
resikonya adalah menambah kompleksitas pengolahan data. Disamping itu mekanisme
koreksi kesalahan akan menambah kapasitas memori karena adanya penambahan bit –
bit cek paritas. Jadi ukuran memori akan lebih besar beberapa persen atau dengan kata
lain kapasitas penyimpanan akan berkurang karena beberapa lokasi digunakan untuk
mekanisme koreksi kesalahan.