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.