bab ii dasar teori 2.1. huffman code -...

4

BAB II

DASAR TEORI

2.1. Huffman Code

Algoritma Huffman menggunakan prinsip penyandian yang mirip dengan kode

Morse, yaitu tiap karakter (simbol) disandikan dengan rangkaian bit. Karakter yang

sering muncul disandikan dengan rangkaian bit yang pendek dan karakter yang jarang

muncul disandikan dengan rangkaian bit yang lebih panjang. Berdasarkan tipe peta

kode yang digunakan untuk mengubah masukan menjadi sekumpulan codeword,

algoritma Huffman termasuk ke dalam kelas algoritma yang menggunakan metode

statik .

Metode statik adalah metode yang selalu menggunakan peta kode yang sama.

Metode ini memiliki dua tahapan: tahap pertama untuk menghitung probabilitas

kemunculan tiap simbol dan menentukan peta kodenya, dan tahap kedua untuk

mengubah masukan menjadi kumpulan kode yang akan ditransmisikan.

Berdasarkan teknik penyandian simbol yang digunakan, algoritma Huffman

menggunakan metode symbolwise. Metode symbolwise adalah metode yang menghitung

probabilitas kemunculan setiap simbol dalam satu waktu, dengan simbol yang lebih

sering muncul diberi kode lebih pendek dibandingkan simbol yang jarang muncul.

Prosedur pembentukan kode Huffman adalah sebagai berikut.

4. Mengurutkan simbol-simbol sumber mulai dari yang memiliki probabilitas

terbesar hingga terkecil.

5. Menjumlahkan probabilitas dua simbol pada urutan terbawah (yaitu, dua simbol

dengan probabilitas terkecil), dan kemudian mengurutkan kembali nilai-nilai

yang dihasilkan. prosedur ini diulangi hingga hanya terdapat dua probabilitas

yang dijumlahkan sampai 1.

6. Selanjutnya dilakukan penyandian, probabilitas yang terkecil pertama diberi

kode '1' dan probabilitas terkecil kedua diberi kode '0'.

7. Menuliskan kode karakter dimulai dari level paling atas sampai level paling

bawah.

5

Contoh:

Masukan: katak

Langkah pertama: menghitung probabilitasnya:

Tabel 2.1. Probalitas Masukan: “katak”.

Karakter Jumlah Probabilitas

K 2 2/5

T 1 1/5

A 2 2/5

Langkah kedua: mengurutkan probabilitas dari yang paling besar ke probabilitas yang

paling kecil.

Gambar 2.1. Urutan Karakter Masukan: “katak.

Langkah ketiga: Menjumlahkan probabilitas yang terkecil dan terkecil kedua, kemudian

mengurutkan probabilitasnya lagi. Kalau sama, maka hasil penjumlahan probabilitas

yang terkecil dan terkecil kedua diletakkan di depan. Kemudian langkah ketiga ini

diulangi sampai total probabilitasnya 1.

Gambar 2.2. Pohon Huffman Masukan: “katak”.

Langkah 4: Menuliskan kode „0‟ pada sebelah kiri dan menuliskan kode „1‟ pada

sebelah kanan pada cabang.

a

2/5

k

2/5

t

1/5

kta

5/5

a

2/5

t k

3/5

t

1/5

k

2/5

a

2/5

6

0 1

0 1

Gambar 2.3. Pohon Huffman Masukan: “katak”.

Langkah kelima: menuliskan kode karakter dari kode paling atas sampai kode paling

bawah dan akan didapat hasil seperti pada tabel 2.2 berikut..

Tabel 2.2. Hasil Penyandian Masukan: “katak”.

Karakter Code Probabilitas

K 00 2/5

T 01 1/5

A 1 2/5

Langkah keenam: menuliskan masukan dengan code. Sehingga mendapatkan hasil

=00101100.

2.1.1. Rerata Informasi atau Entropi

Sistem-sistem komunikasi umumnya mentransmisikan serangkaian karakter

yang berasal dari sumber informasi. Oleh sebab itu, lebih penting untuk mengetahui

t

1/5

a

2/5

k

2/5

k t

3/5

a

2/5

kta

5/5

7

rerata jumlah informasi yang dihasilkan oleh sebuah sumber informasi, daripada jumlah

informasi yang dikandung oleh sebuah karakter tunggal. Entropi dinyatakan oleh

Persamaan (2.1).

( ) ∑ ( ) ( ) (2.1)

dengan:

n = jumlah karakter;

P(xi) =probabilitas setiap kode; dan

H(X) =entropi.

Misal untuk masukkan: “katak”, bisa dilihat pada Tabel 2.1


K 2 2/5

T 1 1/5

A 2 2/5

H(X) = ( )

= ( )

=1,52192 bit per karakter.

2.1.2. Panjang Rata-Rata dan Efisiensi Kode

Panjang sebuah kode biner adalah banyaknya digit biner (bit) di dalam kode

tersebut. Panjang kode rata-rata L untuk tiap karakter sumber ditentukan sebagai

berikut:

∑ ( ) (2.2)

dengan:

L =panjang kode rata-rata;

n = jumlah karakter;

P(xi) =probabilitas setiap kode; dan

ni =jumlah bit tiap kode Huffman.

Peubah L menunjukkan jumlah bit rata-rata yang digunakan untuk merepresentasikan

sebuah karakter sumber dalam penyandian sumber.

Selanjutnya, parameter efisiensi kode dirumuskan sebagai:

8

( )

(2.3)

dengan:

=efisiensi kode;

L =panjang kode rata-rata; dan

H(X) =entropi.

Misalnya untuk masukan: “katak”, bisa dilihat pada Tabel 2.2 berikut.

Karakter Code Probabilitas

K 00 2/5

T 01 1/5

A 1 2/5

= 1,6 bit per karakter

Sehingga panjang kode rata-rata masukan “katak” adalah 1,6 bit per karakter.

=0,9512 bit per karakter

Sehingga efisiensi kode masukan “katak” adalah 0,9512 bit per karakter.

2.2. Arithmetic Code

Pada umumnya, algoritma kompresi data melakukan penggantian satu atau lebih

karakter masukan dengan kode tertentu. Berbeda dengan cara tersebut, Arithmetic

Coding menggantikan satu deretan karakter masukan dengan sebuah bilangan floating

point. Keluaran arithmetic coding ini adalah satu angka yang lebih kecil dari 1 dan lebih

besar atau sama dengan 0. Angka ini secara unik dapat diawasandikan sehingga

menghasilkan deretan karakter yang dipakai untuk menghasilkan angka tersebut. Untuk

menghasilkan angka keluaran tersebut, tiap karakter yang akan disandikan diberi satu

set nilai probabilitas.

Contoh, masukan : “kata” akan disandikan. Akan didapatkan tabel probabilitas

berikut.

Langkah pertama: Mencari probabilitas tiap karakter

Tabel 2.3. Probabilitas Masukan: “kata”.

9


K 1 1/4

T 1 1/4

A 2 2/4

Langkah kedua: Setelah probabilitas tiap karakter diketahui. Tiap karakter akan

diberikan rentang tertentu yang nilainya berkisar di antara 0 dan 1, sesuai dengan

probabilitas yang ada. Dalam hal ini, penentuan rentang harus urut dari karakter

masukan. Dari Tabel 2.3 di atas dibentuk Tabel 2.4 berikut:

Tabel 2.4. Rentang untuk Masukan: “kata”.

Karakter Probabilitas Rentang

K 1/4 0,00-0,25

A 2/4 0,25-0,75

T 1/4 0,75-1,00

Langkah ketiga: Membuat diagram Arithmetic

Dengan low=0 dan high=1. Low adalah batas bawah dan high adalah batas atas yang

disesuaikan dengan rentang pada Tabel 2.4.

0,00 k 0,25 a 0,75 t 1

Langkah keempat: menyesuaikan urutan masukan, karena masukan “kata” maka

dimulai dengan huruf k yang mempunyai rentang 0,00 sampai 0,25. Sehingga batas

bawahnya =0,00 dan batas atasnya menjadi 0,25.

0,00 k 0,0625 a 0,1875 t 0,25

Rumus batas atas=(batas atas karakter – batas bawah karakter) * probabilitas karakter +

batas bawah.

Dengan nilai batas atas karakter „k‟=0,25, batas bawah karakter „k‟=0,00, probabilitas

karakter „k‟=0,25

Batas atas k= (0,25-0,00)*0,25+0,00

=0,25*0,25+0,00=0,0625

10

Sehingga didapatkan batas atas k adalah 0,0625.

Dengan batas atas karakter „a‟=0,25, batas bawah karakter „a‟=0,0625, dan probabilitas

karakter „a‟=0,5

Batas atas a= (0,25-0,0625)*0,5+0,0625

=0,1875

Sehingga didapatkan batas atas a adalah 0,1875

Lakukan sampai dengan huruf a yang terakhir. Sehingga didapatkan hasil seperti pada

Tabel 2.5.

Tabel 2.5. Tabel Batas untuk Masukan: “kata”.

Karakter Batas bawah Batas atas Batas atas-batas

bawah

0,00 1,00

k 0,00 0,25 1

a 0,0625 0,1875 0,25

t 0,15625 0,1875 0,125

a 0,1640625 0,1796875 0,03125

Langkah kelima: Mencari hasil penyandian dan pengawasandian

Untuk mencari hasil penyandian karakter ke-2 (huruf „a‟), dan seterusnya menggunakan

rumus

( )

Proses penyandian:

Hasil penyandian karakter pertama dapat dilihat pada Tabel 2.5 pada batas bawah

karakter terakhir (huruf „a‟) seperti yang dilingkari di bawah ini.

Karakter Batas bawah Batas atas Batas atas-batas

bawah

0,00 1,00

k 0,00 0,25 1

11

a 0,0625 0,1875 0,25

t 0,15625 0,1875 0,125

a 0,1640625 0,1796875 0,03125

Sehingga Karakter 1 =0,1640625

Selanjutnya, membandingkan dengan Tabel 2.4. Dengan tabel ini, dapat dilihat hasil

penyandian pertama memenuhi rentang karakter „k‟ karena 0,164025 berada di antara

rentang 0,00 sampai 0,25 (pada baris yang diberi anak panah).


k ¼ 0,00-0,25

a 2/4 0,25-0,75

t ¼ 0,75-1,00

probabilitas di antara 0,00 sampai 0,25 sehingga karakter pertama adalah karakter

k.

Untuk karakter ke 2 dan seterusnya menggunakan Persamaan 2.4.

Hasil penyandian sebelumnya=0,1640625

Batas bawah dan batas atas yang dipakai batas bawah batas atas karakter sebelumnya.

Batas bawah =0,00

Batas atas =0,25


penyandian karakter ke-2 memenuhi rentang karakter „a‟ karena berada di

antara rentang 0,25 sampai 0,75 (pada baris yang diberi anak panah).


k ¼ 0,00-0,25

a 2/4 0,25-0,75

t ¼ 0,75-1,00

0,164062

12

probabilitas di antara 0,25 sampai 0,75 sehingga karakter ke-2 adalah karakter a

Hasil penyandian sebelumnya=


Batas bawah =0,25

Batas atas =0,75


penyandian karakter ke-3 memenuhi rentang karakter „t‟ karena berada di



k ¼ 0,00-0,25

a 2/4 0,25-0,75

t ¼ 0,75-1,00

probabilitas di antara 0,75 sampai 1,00 sehingga karakter ke-3 adalah karakter t

Hasil penyandian sebelumnya=


Batas bawah =0,75

Batas atas =0,1


penyandian karakter ke-4 memenuhi rentang karakter „a‟ karena berada di



k ¼ 0,00-0,25

a 2/4 0,25-0,75

13

t ¼ 0,75-1,00

probabilitas di antara 0,25 sampai 0,75 sehingga karakter ke-4 adalah karakter a

Sehingga hasil setelah diawasandikan=kata.

2.3. Parity Check Code

Parity Check Code adalah penyandian menggunakan penambahan satu atau lebih bit

untuk membuat total jumlah 1 bit menjadi genap (parity genap) atau gasal (parity

gasal). Jika jumlah bit gasal (termasuk bit parity) berubah pada waktu pengiriman, maka

bit parity menjadi tidak benar dan mengindikasikan adanya kesalahan pada saat

diterima. Oleh karena itu, bit parity merupakan kode pendeteksi kesalahan (error

detecting code), dan bukan merupakan kode pengoreksi kesalahan (error correcting

code) karena tidak ada cara untuk menentukan bit mana yang keliru. Data harus

diabaikan seluruhnya dan mengulangi lagi transmisi dari awal. Pada media transmisi

yang terganggu, transmisi yang berhasil akan membutuhkan banyak waktu atau tidak

berhasil sama sekali. Bit ekstra disebut parity redundant bit.

Kelemahan Parity Check Code ini adalah jumlah kesalahan bitnya harus gasal,

jika tidak maka sistem tidak bisa mendeteksi error.

Contoh penggunaan parity check code ditunjukan pada Gambar 2.4.

Misalnya pengiriman data biner 1100010, menggunakan parity genap

o Karena jumlah bit 1 dalam data ada 3, maka parity bit nya adalah 1, agar jumlah

bit menjadi genap

o Pada penerima, jika penerima mengenali 11000101 dan menghitung jumlah total

angka 1 pada data yaitu empat angka genap, maka data dideteksi benar

o Jika data telah rusak selama pengiriman dan penerima menerima 11100101,

maka fungsi parity check menghitung angka 1 dan didapatkan jumlah bit 1

sebanyak 5, yang merupakan angka gasal. Penerima mengenali bahwa error

telah terjadi pada data.

14

Gambar 2.4. Parity Check Code

Bila sistem menggunakan parity check gasal, maka parity bit ditambahkan pada data

agar jumlah bit 1-nya gasal.

2.4. Longitudinal Redundancy Check (LRC)

Longitudinal Redundancy Check (LRC) merupakan pengembangan Parity Check

Code yang mempunyai kemampuan deteksi error yang lebih efisien. Pada data

Longitudinal Redundancy Check (LRC) dibagi menjadi sejumlah blok dan setiap blok

mempunyai karakter pemeriksa blok (Block Check Character/BCC) yang ditambahkan

di akhir blok.

Bit-bit paritas yang diletakan pada setiap karakter berfungsi sebagai LRC. Pada

teknik ini, satu blok bit diatur dalam bentuk baris dan kolom. LRC menggunakan paritas

genap untuk tiap kolomnya.

Jika dibandingkan Parity Check Code, LRC bisa mendeteksi junlah kesalahan

tidak hanya gasal saja tetapi bisa genap. Tetapi pada LRC memiliki kelemahan juga

yaitu jika jumlah kesalahannya 2 dan pada bit ke-n dan n+8, maka tidak terdeteksi

error. Karena LRCnya terdeteksi sama.

Adalah jumlah total angka 1 genap

1 1 0 0 0 1 0

penerima menerima data

1 1 0 0 0 1 0 1

Checking function

1 1 0 0 0 1 0 Even parity Generator

Parity Bit

Data

15

Sebagai contoh, anggap pengirim ingin mengirim satu blok yang terdiri dari 32 bit.

o Sebelum pengiriman, 32 bit diatur dalam empat baris dan delapan kolom.

o Bit-bit dibaca per kolom, lalu parity bit dihitung sesuai aturan parity check code,

parity bit untuk setiap kolom tersebut membentuk baris kelima.

o Parity bit pertama dalam baris kelima dihitung berdasarkan semua bit pertama

o Parity bit kedua dalam baris kelima dihitung berdasarkan semua bit kedua, dan

seterusnya.

o Pada saat pengiriman, dilampirkan baris kelima yang terdiri atas delapan parity

bit pada data asli. Gambar 2.5 menunjukkan Longitudinal Redundancy Check.

Gambar 2.5. Longitudinal Redundancy Check (Data tak Terkorupsi).

o Penerima memeriksa blok LRC, 10101010 dan mengikuti aturan parity

genap.

Pengirim

Penerima

LRC

Data Asli

11100111 11011101 0011001 10101001

11100111

11011101

00111001

10101001

Baris 1

Baris 2

Baris 3

Baris 4

10101010 Baris 5

LRC

11100111 11011101 0011001 10101001 10101010

11100111 11011101 0011001 10101001 10101010

Data Asli Parity

16

Gambar 2.6 menggambarkandata sebenarnya ditambah LRC, diterima oleh

penerima ketika data terkorupsi selama pengiriman.

Gambar 2.6. Longitudinal Redundancy Check (Data Terkorupsi).

Ketika penerima mengecek LRC, beberapa bit tidak mengikuti aturan parity

genap,

2.5. Cyclic Redundancy Check (CRC)

Cyclic Redundancy Check (CRC) adalah teknik untuk mendeteksi kesalahan

dalam data digital, tetapi tidak dapat mengoreksi ketika kesalahan terdeteksi. Hal ini

digunakan terutama dalam transmisi data. Penerima memeriksa bit pengecek CRC

yang sama dengan yang dikirim, untuk mendeteksi terjadinya kesalahan.

Teknik ini kadang-kadang diterapkan pada perangkat penyimpanan data, seperti

disk drive. Dalam situasi ini setiap blok pada disk akan memeriksa bit, dan hardware

secara otomatis memulai membaca kembali dari blok ketika kesalahan terdeteksi, atau

melaporkan kesalahan perangkat lunak.

CRC mempunyai kelebihan dibandingkan dengan parity check code dan LRC

,yaitu hasil koreksinya lebih akurat dan juga mempunyai bit redundant yang sedikit jika

dibandingkan LRC (jika bit pembaginya kurang dari 8 bit).

Penggunaan Cyclic Redundancy Check (CRC) dijelaskan sebagai berikut.

Data atau pesan yang diberikan sejumlah k-bit, kemudian pengirim

membangkitkan suatu bagian n-bit, sehingga jumlah bit yang terkirim adalah

k+n bit

Penerima memeriksa data (bit k+n).

Data dibagi oleh angka yang belum ditentukan, dan jika tidak ada sisa, maka

tidak terjadi error.

11100111 11011101 0011001 10101001 10101010

11100111 11011101 10001001 10100011 10101010

Pengirim

Penerima

17

Gambar 2.7 menunjukkan generator CRC, Gambar 2.8 menunjukkan pengecek

CRC, dan Gambar 2.9 menunjukkan transmisi CRC.

Gambar 2.7. Generator CRC.

Gambar 2.8. Pengecek CRC.

Gambar 2.9. Transmisi CRC.

Berikut ini adalah ilustrasi proses yang terjadi.

o String n ”0” diberikan pada data. Jumlah n kurang 1 dari jumlah bit pada

pembagi yang belum ditentukan, yaitu bit n+1.

o Data yang baru saja diperpanjang dibagi dengan pembagi menggunakan proses

yang disebut pembagian biner. Sisa yang dihasilkan dari pembagian adalah

CRC.

o CRC pada bit n berasal dari langkah ke-2 yang menggantikan 0 yang

ditambahkan pada akhir rentetan data.

o Rentetan data tiba pada penerima data pertama, diikuti oleh CRC.

Data 00 - - - - 0

Pembagi

CRC

k-bit

n+1 bit

n-bit

Data CRC

Pembagi

Sisa

Angka yang belum ditentukan

0 , menerima

bukan 0 , menolak

Data CRC Pengirim Penerima

18

o Penerima memperlakukan keseluruhan string sebagai sebuah kesatuan dan

membaginya dengan pembagi yang sama yang digunakan untuk menemukan

sisa CRC.

o Jika string bisa sampai tanpa error, pengecek CRC menghasilkan sisa nol, jika

string telah berubah dalam pengiriman, pembagian menghasilkan sisa yang

bukan nol.

Gambar 2.10 menggambarkan cara kerja generator CRC.

o Pada langkah pertama, keempat bit pembagi (1101) mengurangi empat bit

pertama yang dibagi (1001), menghasilkan 100 (0 pada sisa dikeluarkan).

o Selanjutnya satu bit berikutnya dari bit yang dibagi, ditarik ke bawah untuk

membuat jumlah bit pada sisa sama dengan bit pada pembagi.

o Langkah selanjutnya, 1000-1101 menghasilkan 101, dan seterusnya.

Gambar 2.10. Cara Kerja Generator CRC.

o Dalam proses ini, pembagi hanya bisa dikurangi dari sisa yang memiliki bit

sisa sebagian besar adalah satu.

1 0 0 1 0 0 0 0 0

1 1 0 1

1 0 0 0

1 1 0 1

1 0 1 0

1 1 0 1

1 1 1 0

1 1 0 1

0 1 1 0

0 0 0 0

1 1 0 0

1 1 0 1

0 0 1

Data plus ekstra 0. Angka 0 adalah angka bit pembagi dikurangi 1

Ketika bit paling kiri dari sisa adalah 0, harus menggunakan 0000 bukan pembagi asli

Sisa atau n- bits (CRC)

1101

111101

19

o Pada saat bit sisa sebagian besar adalah 0, kita harus menggunakan 0000

bukannya pembagi asli.

o Pembatasan ini menyatakan secara tidak langsung bahwa pada beberapa

langkah, pengurangan sisa sebagian besar akan menjadi 0-0 atau 1-1 yang

keduanya sama-sama menghasilkan angka 0.

o Proses ini dilakukan berulang-ulang hingga pembagi yang tersisa telah

digunakan. Di sini, CRC nya adalah 001.

Gambar 2.11 menunjukkan pengecek CRC untuk generator CRC.

o Pengirim mengirim data ditambah CRC ke penerima, setelah menerima data

yang ditambahkan CRC.

o Di sini, pembagi bit (1101) sama dengan generator CRC.

o Jika semua sisanya adalah 0, maka CRC dibuang dan data diterima; sesuai

dengan yang dikirim.

Gambar 2.11. Cara Kerja Pengecek CRC .

Jika hasil CRCnya tidak 0 semua, maka terjadi error saat data diterima, sebaliknya jika

hasil CRCnya 0 semua, maka tidak terjadi error saat data diterima.

Pembagi –1101, data plus CRC–100100001, dan hasilnya 000

Ketika bit paling kiri dari sisa adalah 0, kita harus menggunakan 0000 bukan pembagi

1101

111101

1 0 0 1 0 0 0 0 1

1 1 0 1

1 0 0 0

1 1 0 1

1 0 1 0

1 1 0 1

1 1 1 0

1 1 0 1

0 1 1 0

0 0 0 0

1 1 0 1

1 1 0 1

0 0 0 Hasil CRC setelah dideteksi

20

2.6. Checksum Code

Checksum Code adalah penyandian yang sering dipakai dalam komunikasi data

untuk mendeteksi error dengan cara menembahkan bit. Metode pendeteksian error

yang digunakan oleh protokol-protokol dengan lapisan lebih tinggi disebut checksum.

Checksum didasarkan pada konsep redundancy bit. Pengirim menggunakan generator

checksum dan penerima menggunakan pengecek checksum. Generator checksum

membagi kembali data menjadi segmen-segmen yang sama pada bit n, segmen-segmen

ini ditambahkan bersama-sama. Segmen yang ditambahkan disebut checksum field yang

ditambahkan pada akhir data asli sebagai bit redudancy. Pengirim mengirim data

ditambah checksum.

Checksum Code, jika dibandingkan dengan parity check code, LRC, dan CRC,

mempunyai kelebihan yaitu cara pendeteksiannya lebih sederhana dibandingkan CRC,

dan hasil pendeteksiannya a juga lebih akurat dibandingkan parity check code dan LRC.

Contoh data terdiri dari 16 bit yaitu 10101001 00111001.

o Rentetan data dibagi menjadi dua segmen 8 bit, sebagai berikut : 10101001

dan 00111001.

o Kedua segmen ditambahkan sebagai berikut:

10101001

00111001

11100010 (jumlah)

o Checksum dibentuk dari komplemen hasil jumlah yaitu 00011101.

o Checksum ditambahkan pada data. Pola yang terkirim adalah:

10101001 00111001 00011101

o Penerima menerima pola-pola di atas kemudian membaginya menjadi tiga

bagian, dan menjumlahkan secara bersamaan, dan akan mendapatkan semua

angka 1, yang dilomplemen menghasilkan semua angka 0.

o Ini menunjukkan bahwa tidak ada error dalam pengiriman.

o Jika hasil tidak nol semua maka terjadi error.

o Prosesnya sebagai berikut.

21

10101001 (segmen data)

00111001 (segmen data)

00011101 (cek jumlah/ checksum)

11111111 (jumlah)

00000000 (komplemen)

2.7. Hamming Code

Metode Hamming code merupakan salah satu metode pendeteksi error dan

pengkoreksi error (error detection and error correction) yang paling sederhana.

Metode ini menggunakan operasi logika XOR (Exclusive-OR) dalam proses

pendeteksian error maupun pengkoreksian error. masukan dan keluaran dari metode ini

berupa bilangan biner. Hamming code merupakan salah satu jenis linier error correcting

code linier yang sederhana dan banyak dipergunakan pada peralatan elektronik.

Metode hamming code bekerja dengan menyisipkan beberapa check bit ke

dalam data. Jumlah check bit yang disisipkan tergantung pada panjang data. Rumus

untuk menghitung jumlah check bit yang akan disisipkan ke dalam data adalah: data 2n

bit, c = (n+1) bit, dengan c adalah jumlah check bit yang disisipkan.

Metode koreksi error single bit yang dikembangkan oleh R.W Hamming

melibatkan penciptaan codeword spesial dari data. Hamming Code menyertakan parity

bit jamak dalam string bit sebelum pengiriman. Idenya adalah bahwa bit diubah,

posisinya menentukan suatu kombinasi unik error parity check.

Tabel 2.6 menunjukkan jumlah data dan bit redundant.

22

Tabel 2.6. Hubungan antara Data dan Bit Redudancy

Angka data bit

(m)

Angka bit

redundancy (r)

Jumlah angka bit

(m+r)

2rm+r+1

1

2

3

4

5

6

7

2

3

3

3

4

4

4

3

5

6

7

9

10

11

4 4

8 6

8 7

8 8

16 10

16 11

16 12

Misalnya data terdiri dari tujuh bit ASCII, akan diperlukan empat bit redudancy

yang bisa ditambahkan pada akhir unit data atau menyelingi dengan bit data asli.

Gambar 2.12 menunjukkan posisi bit redudancy pada kode Hamming.

Gambar 2.12. Posisi Bit Redudancy pada Kode Hamming

Pada kode Hamming, setiap bit r adalah parity bit untuk satu kombinasi data bit :

o r 1 adalah parity bit untuk satu kombinasi data bit, yaitu:

r 1 : bit 1, 3, 5, 7, 9, 11


r 2 : bit 2, 3, 6, 7, 10, 11

m1 m2 m3 m4 m5 m6 r 4 m7 r 8 r 2 r 1

11 10 9 7 6 5 4 3 8 2 1

Bit redudancy

23


r 4 : bit 4, 5, 6, 7


r 8 : bit 8, 9, 10, 11

Masing-masing bit data mungkin diikutsertakan dalam lebih dari satu hitungan

parity.

Di sini, r1 dihitung menggunakan semua posisi bit yang memiliki perwakilan biner

termasuk satu ”1” pada posisi paling kanan.

Bit r2 dihitung menggunakan semua posisi bit dengan satu ”1” pada posisi kedua,

dan seterusnya.

Gambar 2.13 menunjukkan penghitungan bit.

24

Gambar 2.13. Penghitungan Bit Redudancy.

Gambar 2.14 menunjukkan penghitungan untuk mendapatkan kode Hamming

Dalam contoh tersebut, kesebelas bit terdiri dari 7 karakter ASCII dan 4 parity

check.

Pertama-tama masing-masing karakter asli (7 bit) ditempatkanpada posisi yang tepat

pada 11 bit.

25

Langkah selanjutnya, menghitung parity genap untuk berbagai macam kombinasi

bit.

Nilai parity untuk masing-masing kombinasi adalah nilai hubungan bit r.

Gambar 2.14. Penghitungan Bit Redudancy.

Seperti ditunjukkan oleh Gambar 2.14, untuk mendapatkan kode berjumlah 11 bit,

pengirim mengirim kode berjumlah 11 bit kepada penerima melalui garis transmisi.

Sekarang misalkan pada saat pengiriman data di atas diterima, angka bit 7 telah

berubah dari 1 menjadi 0, seperti ditunjukkan oleh Gambar 2.15.

26

Gambar 2.15 Kesalahan pada Bit Tunggal.

Gambar 2.16 memperlihatkan deteksi error dengan menggunakan kode Hamming.

Penerima menghitung kembali empat parity check baru (vertikal redudancy check)

dengan menggunakan set bit yang sama yang digunakan pengirim ditambah

hubungan parity bit r untuk setiap set.

Dari contoh dapat diketahui bit yang salah adalah posisi ketujuh, sehingga detektor

langsung bisa mengoreksi bit pada posisi ketujuh yaitu 0 menjadi 1 sesuai data yang

dikirimkan.

Gambar 2.16. Error Detection.

1 0 0 1 1 1 0 0 1 0 1

1 0 0 1 0 1 0 0 1 0 1

Menerima Error

Mengirim

11 10 9 8 7 6 5 4 3 2 1

1 0 0 1 0 1 0 0 1 0 1

r

1 11 10 9 8 7 6 5 4 3 2 1

1 0 0 1 0 1 0 0 1 0 1

r

2

11 10 9 8 7 6 5 4 3 2 1

1 0 0 1 0 1 0 0 1 0 1

r

4 11 10 9 8 7 6 5 4 3 2 1

1 0 0 1 0 1 0 0 1 0 1

r

8

0 1 1 1

(Bit pada posisi 7 salah) 7

( r1

dih

itun

g d

engan

pen

gkom

bin

asia

n

bit

1,

3,

5,

7,

9 d

an 1

1)

27

2.8. BCH Code

Bose, Chaudhuri, and Hocquenghem (BCH) code merupakan sebuah metode

error correction yang dibangun pada bidang finite (terbatas). Kode ini merupakan

pengembangan dari Hamming code untuk multiple error correction. Kode BCH

merupakan Cyclic codes dengan beberapa karakter tersusun dari m-bit yang berurutan,

dengan m adalah bilangan bulat positif yang lebih besar dari 2. Pada binary BCH code

terdapat beberapa parameter sebagai berikut:

Panjang blok : n = 2m - 1

Panjang bit informasi : k

Jumlah bit error maksimal : t

Checkbit :c=m*t

Jumlah digit parity-check : n – k ≤m*t

Jarak minimal : n ≥ 2t + 1

Kode ini mampu mengoreksi sebanyak t atau lebih kecil dalam blok n digit,

yang disebut kode BCH t-error-correcting. Sebuah kode BCH digambarkan dengan

format pada Gambar 2.17. Sebuah kode BCH seperti Gambar 2.17 di bawah dapat

dituliskan dalam bentuk BCH (n,k), contohnya BCH (15,7), berarti setiap 7 bit informasi

akan dikelompokan (di-framekan) dan dikodekan secara BCH dengan panjang kode 15.

Hal ini berarti terdapat 8 bit parity yang ditambahkan, untuk jelasnya dapat dilihat di

Gambar 2.18.

Tambahan 8 bit ini akan diletakkan di belakang informasi. Fungsinya adalah

untuk melakukan deteksi dan koreksi pada bagian penerima. Jika terdapat kesalahan

pada 7 bit informasi maka bit parity-check akan dapat mengembalikan data yang rusak

ke nilai awal sebelum terjadi kesalahan. Jumlah kesalahan yang dapat dikoreksi pada

BCH (15,7) adalah t = 2 (n-k = mt).

Gambar 2.17. Elemen BCH Code.

Gambar 2.18. BCH (15,7) dalam Bentuk Blok.

28

2.9. Convolution Code

Terdapat dua tipe utama kode pengoreksi error yang umum yang digunakan

yaitu kode blok dan kode konvensional. Dengan kode blok (n,k), bit-bit data (atau

informasi) dikelompokan menjadi blok-blok sepanjang k bit , dan kemudian

penyandiannya untuk membentuk kode-kode biner (atau blok-blok kode) sepanjang n

bit, dengan (n-k) bit yang ditambahkan ke bit-bit data aslinya berfungsi sebagai cek

paritas. Salah satu karakteristik kode blok linier adalah bahwa blok data k bit yang

disandikan pada saat tertentu secara langsung menentukan kode biner n bit yang akan

dihasilkan oleh penyandi.

Di sisi lain sebuah penyandi untuk kode konvolusional (n,k,m) juga menerima

masukan berupa blok data k bit dan menghasilkan keluaran kode biner sebanyak n bit.

Namun berbeda halnya dengan kode blok, pembentukan sebuah kode biner n bit tidak

lagi hanya ditentukan oleh blok data k bit yang diumpankan ke penyandi pada titik

waktu yang sama, namun juga oleh (m-1) blok data k bit yang diumpankan sebelumnya.

Sehingga, karakteristik penting kode konvensional yang membedakannya dari kode

blok linier adalah digunakannya memori di dalam proses penyandian. Dalam

prakteknya, n maupun k adalah bilangan-bilangan bulat yang bernilai kecil dan tetap,

sedangkan nilai m akan diubah-ubah nilainya untuk mengatur redundansi pada kode.

Di dalam kasus khusus dengan k=1, rangkaian bit data tidak perlu dibagi terlebih

dulu menjadi blok-blok dan diolah terus-menerus secara berkesinambungan. Dalam

uraian selanjutnya mengenai kode konvolusional, hanya akan dibahas kasus khusus k =1

ini.

Kode-kode konvolusional sangat praktis. Beberapa metode yang berbeda bahkan

dapat digunakan untuk menjabarkan proses penyandian konvolusional, diantaranya

diagram koneksi, polinom koneksi, diagram keadaan (state diagram). Diagram pohon

(tree diagram), dan diagram teralis (trellis diagram). Gambar 2.19 memperlihatkan

sebuah penyandi konvolusional (2,1,2) sederhana denga n =2,k=1,dan m=2. Setiap kali

sebuah bit data dimasukkan ke register pertama pada penyandi, dua bit kode akan

dihasikan sebagai keluaran secara berurutan.

29

Gambar 2.19. Penyandian Convolution Code (2,1,2).

Tabel 2.7. Penyandian Convolution Code (2,1,2).

INPUT PRESENT STATES NEXT STATES OUTPUT

S1 S2 KONDISI S1’ S2’ KONDISI V1 V2

0 0 0 A 0 0 A 0 0

1 0 0 A 1 0 B 1 1

0 1 0 B 0 1 C 1 0

1 1 0 B 1 1 D 0 1

0 0 1 C 0 0 A 1 1

1 0 1 C 1 0 B 0 0

0 1 1 D 0 1 C 0 1

1 1 1 D 1 1 D 1 0

Gambar 2.20. Diagram Keadaan Penyandian Convolution Code (2,1,2).

30

2.10 Reed Salomon Code

Kode Reed Solomon mendeskripsikan sebuah cara sistematis untuk membentuk

kode yang mampu mengoreksi error yang muncul secara acak dan tak terduga (bursty)

pada paket data yang diterima.

Sebuah kode Reed Solomon ditulis dalam bentuk RS(n,k) dengan n adalah

panjang blok atau panjang kode yang terdiri dari susunan beberapa karakter, sedangkan

k adalah panjang informasi atau jumlah karakter data yang akan dikodekan. Panjang

block code ini dinyatakan oleh n = 2m-

1 dengan m adalah jumlah bit per karakter

sedangkan jumlah karakter parity yang harus ditambahkan untuk mengoreksi sejumlah

error sebanyak n-k = 2t dengan t adalah jumlah karakter error yang mampu dikoreksi.

Penyandian Reed Solomon mengganti karakter yang salah dengan karakter yang

sebenarnya tanpa memperdulikan apakah error yang terjadi pada karakter tersebut

disebabkan oleh satu bit yang rusak atau semua bit pada karakter tersebut mengalami

kerusakan. Alasan inilah yang menyebabkan kode Reed Solomon dianggap lebih baik

dibanding binary codes. Proses pendekodean Reed Solomon dijalankan dengan

mencari sindrom error pada data informasi.

Gambar 2.21. Gambar Elemen Reed Salomon Code.

2.10.1. Penyandi Reed-Solomon

Bentuk umum kode RS dituliskan dengan (n,k)=(2m -1, 2

m-1-2t), dengan n-k=2t

adalah banyaknya karakter parity dan t merupakan kemampuan untuk mengoreksi

karakter error. Sedangkan bentuk generator polinomial kode RS dituliskan sebagai

berikut:

g(x)=g0+g1x+g2x2+g2t-1x

2t-1 (2.5)

Derajat generator polinomial sama dengan banyaknya karakter parity yang

ditambahkan yaitu 2t. Sehingga akar generator polinomial, yang dilambangkan dengan

, mempunyai derajat yang sama. Akar-akar g(x) dituliskan sebagai , 2, 3

,... 2t.

Sebagai contoh, kode RS (7,3) dengan n=7 dan k=3,mempunyai kemampuan

untuk mengoreks error karakter 2t=n-k=4, maka kode tersebut mempunyai 4 akar.

31

Berdasarkan derajat polinomialnya dari rendah ke tinggi dan dalam field biner

+1= -1, maka generator g(x) dapat dituliskan dengan:

g(x)=3+

1x+

0x

2+

3x

3+x

4 (2.6)

Untuk pembentukan polinomial codewordnya dilakukan dengan persamaan:

U(x)= P(x)+x^(n-k)m(x) (2.7)

Dengan:

U(x) = codeword yang dibentuk;

m(x) = karakter informasi yang akan disandikan; dan

p(x) = karakter parity yang didapatkan dari sisa pembagian antara perkalian karakter

informasi yang akan disandikan dan polinomial xn-k

dengan generator

polinomial g(x) yang secara matematis p(x) dapat dituliskan dengan p(x)= xn-1

m(x) mod g(x).

2.10.2. Pengawasandi Reed-Solomon

Pada Reed-Solomon decoder, codeword yang diterima mempunyai persamaan

sebagai berikut:

c(x)=U(x)+h(x) (2.8)

dengan

h(x)= ∑

(2.9)

h(x) merupakan error yang direpresentasikan dalam bentuk polinomial.

Jika menggunakan pengawasandian biner,maka perlu diketahui hanya lokasi

errornya saja. Dengan mengetahui error, maka yang harus dilakukan adalah mengubah

bit pada lokasi tersebut dari 0 menjadi 1 atau dari 1 menjadi 0. Sementara

pengawasandian secara non biner, mengetahui letak errornya saja tidaklah cukup, tetapi

juga harus mengetahui nilai karakter yang sebenarnya pada lokasi tersebut.

32

2.11 Elemen Galois Field

Elemen galois field terdiri dari sekumpulan elemen yang dinotasikan oleh ,

dan bernilai n

0, 0, 1

, 2,...

n-1 (2.10)

untuk membentuk sebuah set elemen 2m, dengan n = 2

m -1. Nilai biasanya dipilih

bernilai 2, meskipun nilai lain dapat digunakan. Tiap elemen field yang ditunjukkan

pada persamaan (1) dapat direpresentasikan dalam bentuk polinomial :

m-1x

m-1+ 1

x1+ 0

(2.11)

Untuk m=4 memiliki persamaan elemen Galois Field berikut :

3x

3+ 2

x2+1

x1+ 0

(2.12)

2.12. Polynomial Generator Field

Polynomial Generator Field sering juga disebut polinomial primitif, p(x),

dengan pangkat m. Untuk galois field dengan ukuran tertentu, memiliki bentuk

polinomial yang secara umum sudah sering digunakan, seperti ditunjukan pada Tabel

2.8.

Tabel 2.8. Tabel Polinomial Primitif.

33

2.13. Pembentukan Galois Field (GF)

Pada Tabel 2.9 ditunjukkan nilai dari elemen field untuk GF(2m

) dalam bentuk

indeks, polinomial, biner, dan desimal. Berdasarkan Tabel 2.8, tiap tahap pembentukan

polinomial selalu dikalikan dengan „x‟, sedangkan untuk pembentukan bilangan biner

mewakili nilai-nilai koefisien polinomial.

Tabel 2.9. Tabel Galois Field.

bab ii dasar teori 2.1. huffman code -...

Documents