Selasa, 17 Mei 2016

koreksi kesalahan dengan metode hamming




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                                                                                                                               1


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

H =
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
















Metode Hamming by Gapra                                                                                                                               2


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

0











1


T =
1
0
1
1
0
0
1
0
0

1
=
0










0


1
1
0
0
1
0
0
1
0

1

0











C1



1
0
1
0
1
0
0
0
1

C2

0











C3

























C4


Dari hasil perkalian diatas diperoleh nilai
C1
=
1
C3
=
0
C2
=
1
C4
=
0

Sandi baru diperoleh dengan menggabungkan sandi lama dengan 4 elemen baru yang diperoleh dari perhitungan diatas. Dengan demikian sandi baru untuk pesan A adalah

011011100. Sandi baru untuk ke 32 pesan diatas dapat dilihat pada tabel dibawah ini.

Tabel Sandi Lama dan Sandi Baru

Pesan
Sandi Lama
Sandi Baru



A
01101
011011100
B
00001
000010011
C
00010
000101100
D
00011
000111111
E
00100
001000101
F
00101
001010110
G
00110
001101001
H
00111
001111010
I
10010
100100011
J
01001
010011001




Metode Hamming by Gapra                                                                                                                               3


Pesan
Sandi Lama
Sandi Baru



K
01010
010100110
L
11010
110101001
M
01011
010110101
N
11101
111010011
O
11100
111000000
P
11110
111101100
Q
11001
110010110
R
11000
110000101
S
10101
101011001
T
10100
101001010
U
11011
110111010
V
00000
000000000
W
01000
010001010
X
11111
111111111
Y
10110
101100110
Z
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 :





1
1
0
1
0
1
0
0
0

1
1
0
1
1
0
0
1
0
0

0

1
1
1
0
0
1
0
0
1
0

1

1
1
0
1
0
1
0
0
0
1

1

1










1



















1














Isyarat sindrom yang diperoleh dari perhitungan diatas adalah [ 1 0 1 0 ] -1. Jika isyarat sindrom ini dicocokan dengan matrix H, terlihat bahwa isyarat sindrom cocok dengan kolom ke 2. Dengan demikian, kesalahan terjadi pada angka ke 2, yaitu dari angka “0” harus diubah menjadi angka “1”.

METODE HAMMING

KOREKSI ERROR

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.


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 :


 
                                                                                                                         6
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 :



 

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.