HAMMING CODES

Dibuat sebagai tugas mata kuliah Pengkodean Kanal

Oleh :

Kelompok 3

M. Adisty Padmasari 0604405076

I Putu Rai Suitra

I Putu Agus Ari Wiweka

Kadek Hady Surya Wirawan 0604405081

Komang Wahyu Wedastra Putra 0604405094

Komang Apriana 0704405047

Nyoman Wendy Saputra 0704405076

Dosen :

Gede Sukardamika

JURUSAN TEKNIK ELEKTRO

FAKULTAS TEKNIK UNIVERSITAS UDAYANA

2009

BAB I

PENDAHULUAN

Pengiriman suatu pesan dari seseorang yang bersifat rahasia atau pribadi kepada

orang lain atau orang yang dikehendaki adalah dengan cara merubah pesan yang

akan dikirim tersebut menjadi kata kode sehingga pesan rahasia tersebut hanya

dapat dibaca oleh pengirim dan orang yang bersangkutan.

Teori yang digunakan untuk merubah suatu pesan rahasia menjadi kata kode atau

sebaliknya merubah kata kode menjadi pesan adalah Teori Pengkodean (Coding

Theory).

Encoding (pengkodean) adalah proses penambahan bilangan biner sebanyak (n-m)

karakter pada setiap kode agar terbentuk kata kode. Decoding (menguraikan kata

kode) adalah proses menguraikan suatu kata kode menjadi sebuah pesan. Contoh

teknik encoding dan decoding adalah: (1) Kode Pengulangan (Repetition Code)

dan (2) Kode Hamming (Hamming Code). Dalam encoding berupa kode

pengulangan, kata kode diperoleh dengan cara mengulang suatu pesan yang sudah

diubah dalam bentuk kode sebanyak k-kali. Dalam encoding berupa kode

Hamming, kata kode diperoleh dengan cara menambahkan bilangan biner pada

setiap pesan yang sudah diubah dalam bentuk kode sebanyak k-karakter.

Sedangkan dalam decoding berupa kode pengulangan, pesan diperoleh dengan

cara membagi kata kode sebanyak k-bagian. Dalam decoding berupa kode

Hamming, pesan diperoleh dengan cara menghapus kata kode terakhir sebanyak

k-karakter. Untuk mengetahui pesan yang diterima sama dengan yang dikirim

maka perlu dilakukan pengecekan dan pengoreksian kesalahan kata kode yang

diterima, yaitu dengan cara-cara tertentu sehingga diperoleh pesan yang

sesungguhnya.

BAB II

DASAR TEORI

Keunggulan dari teknologi telekomunikasi digital dibandingkan dengan sistem

analog merupakan daya tarik tersendiri dalam perkembangan teknik

telekomunikasi belakangan ini, yang semakin menuntut akurasi dan kehandalan

sistem telekomunikasi. Salah satu keunggulannya adalah dalam hal kemampuan

mengatasi noise yang terjadi pada kanal telekomunikasi.

Noise merupakan sinyal yang tidak diharapkan dalam sistem telekomunikasi

karena bersifat mengganggu serta kehadirannya tidak bisa ditentukan

(random/acak). Namun, noise selalu ada dalam setiap sistem telekomunikasi,

khususnya pada sistem transmisi. Hal ini dapat menyebabkan kesalahan pada

informasi yang diterima. Pengaruh noise tidak sepenuhnya dapat dihilangkan,

melainkan hanya dapat dikurangi.

Karakter data yang akan dikirim dari suatu titik ke titik yang lain tidak dapat

dikirimkan secara langsung. Perlu proses pengkodean pada setiap titik. Dengan

kata lain, karakter-karakter data tersebut harus dikodekan terlebih dahulu dengan

kode yang dikenal oleh setiap terminal yang ada.

Ada dua jenis error yang dialami dari proses pentransmisian data yaitu random

error dan burst error. Error yang terjadi ini dapat diatasi dengan beberapa teknik

pengkodean yang ada diantaranya yaitu Hamming Code, BCH Code, Reed

Solomon Code, CRC Code, dan Konvolusi Code.

2.1 Hamming Code

Kode Hamming merupakan kode non-trivial untuk koreksi kesalahan yang

pertama kali diperkenalkan. Kode ini dan variasinya telah lama digunakan untuk

kontrol kesalahan pada sistem komunikasi digital. Kode Hamming ada dua

macam, yaitu biner dan non-biner. Kode Hammin biner dapat dipresentasikan

dalam bentuk persamaan berikut :

(n,k) = (2m – 1, 2m – 1 – m )

di mana k adalah jumlah bit informasi yang membentuk n bit kata sandi, dan m

adalah bilangan bulat positif. Jumlah paritas bitnya adalah sejumlah m = n-k bit.

Jika m = 3 dan n = 7 dan k = 4, kode hammingnya adalah C(7,4) dengan

dmin = 3. Tabel berikut menunjukkan data dan kode kata dari kode (7,4) .

Datawords Codewords Datawords Codewords

0000 0000000 1000 1000110

0001 0001101 1001 1001011

0010 0010111 1010 1010001

0011 0011010 1011 101100

0100 0100011 1100 1100101

0101 0101110 1101 1101000

0110 0110100 1110 1110010

0111 0111001 1111 1111111

2.2 Kode Konvolusi

Kode ini merupakan kode yang sistem kerjanya adalah menerima k-bit blok uruan

informasi, yang nantinya akan menghasilkan codeword v dari n buah simbol

blok. Tiap blok encode bergantung tidak hanya pada message k-bit pengirim pada

saat yang bersamaan, tetapi juga m blok pesan sebelumna.

Encoder memiliki sebuah m memory order. Urutan encode dihasilkan dari

sebuah k- input, n-output encoder dari memory order m yang sering disebut

(n,k,m) kode konvolusi.

Bit redundant dapat ditambahkan pada urutan informasi ketika k > n atau R >

1, penambahan redundant dilakukan dengan cara meningkatkan memory order m.

2.3 BCH Code

Kode BCH merupakan kode yang dapat mengkoreksi kesalahan jamak pada

codeword yang diterima, teknik pengkodean ini ditemukan oleh Bose, Chaudhuri

dan Hocquenghem. Kode BCH mempunyai jenis yang bervariasi untuk

mengkoreksi kesalahan, dimana tiap-tiap jenis kode BCH mempunyai

kemampuan mengkoreksi kesalahan yang tergantung pada julah parity yang

digunakan.

Untuk nilai bilangan bulat positif m ≥ 3, kode BCH (n,k) memepunyai

beberapa parameter, yaitu :

a. n = 2m – 1, yaitu panjang dari codeword (bit)

b. t, yaitu jumlah maksimum dari kesalahan yang dapat dikoreksi

c. k ≥ n - m*t, yaitu jumlah bit informasi dalam codeword

d. dmin ≥ 2*t + 1, yaitu jarak Hamming minimum

Untuk t = 1 merupakan konstruksi dari kode BCH untuk membangkitkan kode

Hamming.

Algoritma pembentukan kode BCH dimulai dengan mengambil sebanyak k

bit data dimana k adalah banyaknya dalam satu blok data pada kode BCH.

Kemudian k bit tersebut dikalikan dengan generator matriks. Hasilnya merupakan

kode BCH.

2.4 CRC Code

Cyclic Redudancy Check (CRC) merupakan sistem dengan penambahan

kontrol bit untuk menjamin keamanan data. Kontrol bit dibentuk oleh komputer

pengirim berdasarkan perhitungan atas data yang dikirim. Pada prinsipnya, ketika

data sampai di komputer penerima maka akan dilakukan perhitungan seperti yang

dilakukan oleh komputer pengirim. Jika hasil perhitungan sama maka tidak ada

kesalahan dalam pengiriman.

CRC beroperasi pada sebuah frame/block. Setiap block berukuran m bit yang

akan dikirim akan dihitung CRC checksumnya (berukuran r bit), kemudian

dikirim bersama2 dengan frame (dengan ukuran m+r bit). Pada sisi penerima,

penerima akan menghitung CRC checksum pada frame yang diterima, dan

dibandingkan dengan checksum yang diterima, jika berbeda, berarti frame rusak

CRC menggunakan prinsip modulo bilangan. Data dianggap sebagai sebuah

bilangan, dan untuk menghitung checksum, sama dengan menambahkan digit

untuk data dengan digit untuk checksum (berisi 0) kemudian dibagi dengan

pembilang tertentu, dan sisa pembagiannya menjadi checksum untuk data

tersebut.Tergantung pemilihan bilangan pembagi, CRC dapat mendeteksi single-

bit error, double bit error, error berjumlah ganjil, burst error dengan panjang maks

r. Bilangan pembagi disebut sebagai generator

CRC – modulo arithmetic :

Operasi penambahan dan pengurangan = XOR

Contoh:

1. Data memiliki m bit ; 1001, m = 4

2. Generator memiliki panjang r bit ; 101, r = 3

3. Tambahkan r-1 bit 0 ke data: 100100

4. Bagi bilangan ini dengan generator, sisanya (11) adalah checksum

5. Tambahkan checksum ke data asal: 100111

6. Pada sisi penerima, cukup membagi data yang diterima dengan

generator. Jika sisanya bukan 0, berarti terjadi kesalahan

7. Jika sisanya 0, berarti tidak terjadi kesalahan, sesuai dengan

kriteria generator yang digunakan

2.5 Reed Solomon Code

Reed Solomon Code adalah suatu error-correction-code yang cukup populer

dan merupakan pengembangan dari errorcorrection- code sebelumnya.

Kemampuan deteksi dan koreksi dikenal sebagai multiple error. Seperti coding

sebelumnya kemampuan koreksi data merupakan hubungan antara panjang blok

data dengan parity. Kemampuan lain yang dikembangkan pada Reed Solomon

Code adalah penerapan sistem interleave data. Sistem interleave tersebut

menghasilkan kemampuan blok data yang dapat dikoreksi lebih panjang.Kode

reed-solomon merupakan kode yang menyediakan kemampuan error-correction

yang sangat handal dan mempunyai efisiensi kanal yang tinggi. Terdapat teknik

coding blocked code berdasarkan permintaan penambahan parity redundant pada

data untuk menjalankan error correction.

Suatu data dikelompokkan menjadi blok-blok dan setiap blok diproses

sebagai unit tunggal oleh encoder dan decoder. Banyaknya parity check perblok

didapat dari banyaknya error correction yang diperlukan. Penambahan tersebut

harus memiliki informasi yang cukup untuk menentukan posisi dan nilai dari

error.

Kode reed-solomonsering dideskripsikan sebagai (n,k) dimana parameter-

parameternya adalah sebagai berikut :

n = panjang blok

k = panjang informasi

n-k = 2t nilai dari parity check

t = nilai maksimum dari error yang terkoreksi.

BAB III

METODOLOGI

3.1 Metode Penulisan

Dalam penyusunan paper ini dilakukan secara tim atau perkelompok,

dimana dalam penyusunannya digunakan tinjauan pustaka berupa buku-buku dan

observasi langsung dengan memanfaatkan fasilitas internet.

3.2 Materi

Pencarian materi dalam penyusunan paper ini dilakukan secara perorangan

dengan menggunakan referensi berupa buku dan internet yang selanjutnya

digabungkan sehingga tersusun menjadi satu kesatuan yang utuh.

BAB IV

PEMBAHASAN

Kode Hamming merupakan salah satu contoh dari error-correting code,

yaitu sebuah kode dicirikan oleh sejumlah error bit data dalam word yang dapat

dikoreksi dan di deteksinya. Kode Hamming ini diciptakan oleh Prof. Wesley

Richard Hamming di laboratorium Bell pada tahun 1950 dengan menggunakan

diagram Venn (dapat dilihat pada gambar 1).

c. b.

c. d.

Gambar 1. Diagram Venn error corecting code Hamming codes

Penjelasan dari gambar tersebut adalah sebagai berikut :

Pada tiga buah lingkaran, yang berpotongan, terdapat tujuh kompartemen, dengan

menggunakan word 4-bit (M=4), akan diberikan 4 buah bit data ke kompartemen

yang terletak di tengah (Gambar 2a). kompartemen sisanya diisi dengan apa

disebut dengan bit paritas yaitu bit tambahan untuk dapat mendeteksi bit yang

salah nantinya. Setiap bit paritas dipilih sehingga bilangan 1 dalam lingkaran

berjumlah genap (Gambar 2b). Jadi, karena lingkaran A terdiri dari tiga buah

bilangan 1, maka bit paritas dalam lingkaran itu disetel menjadi 1. sekarang,

apabila suatu error mengubah salah satu bit data (Gambar 2c), maka error itu akan

dengan mudah ditemukan. Dengan memeriksa bit paritas, cacat-cacat dapat

ditemukan pada lingkaran A dan C namun tidak pada lingkaran B. hanya salah

1 1

110

00

0

11

1

0

01

1 0 1 1

10

00

01

00

AB

C

satu dari kompartemen berada pada A dan C namun tidak pada B. karena itu error

dapat dikoreksi dengan mengubah bit tersebut.

Kode Hamming memiliki kemampuan mendeteksi dan koreksi kesalahan / error

bit yang ditransmisikan, antara lain :

1. Mendeteksi semua kesalahan bit tunggal dan ganda sekaligus mengetahui

posisi bit yang salah tersebut. Dilakukan dengan membandingkan

codeword hasil encoding dengan codeword hasil deteksi

2. Mengkoreksi semua kesalahan bit tunggal. Jika terdeteksi adanya

kesalahan bit dalam blok codeword pada proses decoding, maka dengan

operasi XOR akan diperbaiki sebanyak 1 bit error yang terdeteksi.

Menurut Proakis (1989), kode Hamming termasuk ke dalam linear blok code (n,k)

yang dapat dibentuk dengan ketentuan parameternya sbb:

n = 2m - 1

k = 2m – m – 1

m = n-k

dimana : n = Jumlah bit blok codeword atau panjang kode

k = Jumlah bit informasi

m = Jumlah bit parity

Berdasarkan jumlah parity bit kode Hamming dibedakan menjadi beberapa jenis,

yaitu :

m (n.k)3 (7,4)4 (15,11)5 (31,26)6 (63,57)7 (127,120)8 (255,247)

Suatu Hamming code bisa mempunyai “single-error correcting code” atau

”double error detecting”, bila suatu Hamming code berupa single error, maka bila

ada single error yang muncul selama deteksi transmissi sinyal, maka nilai

resultante syndrome adalah “bukan nol (non-zero)dan terdiri dari bilangan bulat

(odd number) dari 1, bila double error yang terjadi,nilai syndrome juga

merupakan nonzero tetapi biasanya angka ganjil (even number) dari 1.

Generator Hamming

Untuk menentukan matrik generator dari kode Hamming dapat dengan

dilakukan dengan cara menentukan (n) dan (k). Dimana nilai (n) dan (k) diperoleh

dengan persamaan :

(n,k) = (2m – 1, 2m – m – 1)

Setelah diperoleh nilai (n) dan (k) lalu ditentukan nilai polynomials sesuai dengan

tabel polynomials :

m Polynomials3 11014 110015 1010016 11000017 1001001

Setelah diketahui nilai dari polynomial sesuai dengan tabel polynomials, maka

selanjutnya disusun matrik dengan susunan sebagai berikut:

Contoh generator Hamming dengan parity(m) = 3.

n = 2m – 1 = 7

k = 2m – 1 – m = 4

1. Gunakan polynomials dalam tabel 3 sebagai baris pertama dan

menambahkan nilai 0 hingga n dengan nama g(x).

g(x) = 1 1 0 1 0 0 0

2. Membuat baris kedua dengan menggeser baris pertama kekanan,

prosesnya diberi nama x.g(x).

x.g(x) = 0 1 1 0 1 0 0

3. Membuat baris ke 3 dengan menggeser baris ke2 ke kanan dengan

proses x2.g(x). Baris terus dilanjutkan sampai sejumlah k.

Genetator yang terbentuk merupakan generator non sistematik. Untuk

merubahnya menjadi sistematik yaitu dengan operasi baris elementer. Matrik dari

G sistematik merupakan generator dari kode Hamming (7,4).

Untuk generator kode Hamming dengan parity yang lain dapat diperoleh dengan

cara yang sama.

Parity Check Kode Hamming

Untuk melakukan koreksi kesalahan pada kode Hamming harus diketahui parity

check matrixnya. Parity check matrix digunakan untuk mengetahui bentuk error

dan error syndrome serta memperbaiki bit yang mengalami error. Untuk itu

diperlukan coset leader yang bisa diperoleh dari standar array.

Dalam bentuk yang sistematik, pengaturan dari parity chek berbentuk:

Dimana :

Im : matriks Identity (m x m) dan sub-matrik:

Q : 2m – m - 1 buah kolom, dengan m merupakan bilangan bulat

misalnya untuk nilai m = 3, maka parity chek dari Hamming code terdiri dari

panjang: 7, dan dapat berbentuk matrik sbb:

ini merupakan kode liner dengan ukuran 7x3. kode tersebut mempunyai : 2 3 = 8

buah co-set sehingga terdapat delapan buah error patern yang mungkin untuk

dikoreksi termasuk semua vektor nolnya, dan kode ini mempunyai jarak: 3 yang

mampu mengkoreksi kesalahan vector error-nya berbobot: 1 dan nol. Untuk kode

Hamming (7,4), jumlah coset leadernya adalah 2(7-4) = 23 = 8 termasuk

codeword (0000000).

Untuk mengetahui error dalam codeword, dilakukan dengan membandingkan

syndrome error dari kode masing-masing jenis Hamming dengan syndrome error

codeword yang diterima. Syndrome error diperoleh dengan mengalikan codeword

yang diterima dengan transpose matriks cek parity.

Bentuk tabel yang mungkin dapat dikoreksi disebut dengan tabel koreksi,contoh

nya adalah tabel koreksi dari kode

liner (7,4) ini beserta syndrome-nya adalah sebagai berikut :

Untuk memperbaiki error, dilakukan dengan menjumlahkan codeword yang

diterima dengan bentuk error yang sesuai dengan syndrome error.

Misalkan ,

code word vector yang dikirimkan: v = (1 0 0 1 0 1 1) dan sinyal yang diterima

sebesar r = (1 0 0 1 1 1 1) , untuk dapat mendeteksi sinyal r maka yang harus

dilakukan adalah menentukan besarnya syndrome, sebagai berikut :

Maka, diperoleh besarnya sindrome menurut teori sebesar ( 0 1 1) yang

merupakan syndrome yang terjadi pada nilai co-set leader pada posisi: e = (0 0 0

0 1 0 0 ), nilai ini dapat dianggap sebagai error patern disebabkan karena kanal

komunikasi dengan hasil decode nya men-jadi:r. Nilai r tersebut kemudian di

decode kembali pada pengiriman ulang: :

v* = r + e

= (1 0 0 1 1 1 1 ) + ( 0 0 0 0 1 0 0 )

= (1 0 0 1 0 1 1 )

v* sebenarnya kode actual vector yang ditransmisikan.

Sekarang bila ditentukan kode yang dipancar ulang adalah: v = ( 0 0 0 0 0 0 0 )

artinya tidak ada message yang dikirim kembali hanya vektor kosong saja, dan

penerima (receiver) menerima kode r = ( 1 0 0 0 1 0 0 ) maka dapat diketahui

terdapat 2 (dua) buah error yang terjadi selama pengiriman tersebut, besarnya

error tersebut dapat di decode dan dihitung dengan melalui sindrome s yang

besarnya:

s = r.HT = (1 1 1)

Pada tabel decoding pada nilai syndrome: s = ( 1 1 1 ) didapat e = (0 0 0 0 0 1)v* = r + e

= (1000100) + (0000010) = (1 0 0 0 1 1 0)

Vektor v* inilah sebenarnya yang dikirimkan.

BAB V

KESIMPULAN

Data digital merupakan data yang memiliki deretan nilai yang berbeda dan

memiliki ciri-ciri tersendiri. Salah satu contoh dari data digital adalah

teks,bilangan bulat dan berbagai karakter lain. Tetapi permasalahannya adalah

data dalam bentuk karakter yang dapat dipahami oleh manusia tersebut tidak bisa

langsung ditransmisikan dengan mudah kedalam sistem komunikasi. Data terlebih

dahulu harus diubah kedalam bentuk biner. Jadi suatu data digital akan

ditransmisikan dalam deretan bit.

Tiga teknik dasar modulasi untuk mengubah data digital menjadi sinyal analog

adalah : Amplitude-Shift Keying (ASK), Frequency-Shift Keying (FSK), dan

Phase-Shift Keying (PSK)

Kinerja beberapa skema modulasi digital ke analog, paremeter pertama adalah

bandwith yang dimodulasikan. Hal ini bergantung pada faktor :

1. Definisi bandwith yang digunakan

2. Teknik penggunaan filter yang menghasilkan sinyal bandpass.

DAFTAR PUSTAKA

Ariyus, Dony dan Andri, Rum, 2008. Komunikasi Data.Yogyakarta : Andi Offset.

Silalahi,Nurain, 2003. Komunikasi Mobil Publik dan Sistem Personal PCS.

Jakarta : PT. Elex Media Komputindo.

Tomasi, Wayne. Advanced Electronic Communications Systems Sixth

Edition.Ohio.

www.google.com