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. a
k
t
2/5
2/5
1/5
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. kta 5/5
tk
a
3/5
2/5
a
k
t
2/5
2/5
1/5
Gambar 2.2. Pohon Huffman Masukan: “katak”. Langkah 4: Menuliskan kode „0‟ pada sebelah kiri dan menuliskan kode „1‟ pada sebelah kanan pada cabang.
6
kta 5/5
0
1
kt
a
3/5
2/5
0
1
a
k
t
2/5
2/5
1/5
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
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 Karakter
Jumlah
Probabilitas
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
Karakter
Jumlah
Probabilitas
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, karakter „k‟=0,25 Batas atas k= (0,25-0,00)*0,25+0,00 =0,25*0,25+0,00=0,0625
batas bawah karakter „k‟=0,00, probabilitas
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 bawah
k
0,00
1,00
0,00
0,25
1
atas-batas
)
11
a
0,0625
0,1875
0,25
t
0,15625
0,1875
0,125
a
0,1640625 0,164062
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). Karakter
Probabilitas
Rentang
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
Selanjutnya, membandingkan dengan Tabel 2.4. Dengan tabel ini, dapat dilihat hasil penyandian karakter ke-2 memenuhi rentang karakter „a‟ karena antara rentang 0,25 sampai 0,75 (pada baris yang diberi anak panah).
Karakter
Probabilitas
Rentang
k
¼
0,00-0,25
a
2/4
0,25-0,75
t
¼
0,75-1,00
berada di
12
probabilitas di antara 0,25 sampai 0,75 sehingga karakter ke-2 adalah karakter a
Hasil penyandian sebelumnya= Batas bawah dan batas atas yang dipakai batas bawah batas atas karakter sebelumnya. Batas bawah
=0,25
Batas atas
=0,75
Selanjutnya, membandingkan dengan Tabel 2.4. Dengan tabel ini, dapat dilihat hasil penyandian karakter ke-3 memenuhi rentang karakter „t‟ karena
berada di
antara rentang 0,75 sampai 1,00 (pada baris yang diberi anak panah).
Karakter
Probabilitas
Rentang
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 dan batas atas yang dipakai batas bawah batas atas karakter sebelumnya. Batas bawah
=0,75
Batas atas
=0,1
Selanjutnya, membandingkan dengan Tabel 2.4. Dengan tabel ini, dapat dilihat hasil penyandian karakter ke-4 memenuhi rentang karakter „a‟ karena antara rentang 0,25 sampai 0,75 (pada baris yang diberi anak panah).
Karakter
Probabilitas
Rentang
k
¼
0,00-0,25
a
2/4
0,25-0,75
berada di
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
Data Even parity Generator
1 1 0 0 0 1 0
Parity Bit
1 1 0 0 0 1 0 1
Checking function
Adalah jumlah total angka 1 genap
penerima menerima data
1 1 0 0 0 1 0
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.
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. Data Asli 11100111
11011101
0011001
10101001
11100111
Baris 1 Baris 2
11011101 Baris 3
00111001 Baris 4
10101001 Baris 5
10101010
LRC
LRC Pengirim
11100111
11011101
0011001
10101001
Data Asli
10101010 Parity
Penerima
11100111
11011101
0011001
10101001
10101010
Gambar 2.5. Longitudinal Redundancy Check (Data tak Terkorupsi). o Penerima memeriksa blok LRC, 10101010 dan mengikuti aturan parity genap.
16
Gambar 2.6 menggambarkandata sebenarnya ditambah LRC, diterima oleh penerima ketika data terkorupsi selama pengiriman.
Pengirim
11100111
11011101
0011001
11100111
11011101
10001001
10101001
10101010
Penerima
10100011
10101010
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.
17
Gambar 2.7 menunjukkan generator CRC, Gambar 2.8 menunjukkan pengecek CRC, dan Gambar 2.9 menunjukkan transmisi CRC. Data
00 - - - - 0 k-bit
Pembagi
CRC
n+1 bit
n-bit
Gambar 2.7. Generator CRC. Data
CRC
Pembagi
Angka yang belum ditentukan
Sisa 0 , menerima bukan 0 , menolak
Gambar 2.8. Pengecek CRC.
Pengirim
Data
CRC
Penerima
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.
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. 111101 1101
100100000
Data plus ekstra 0. Angka 0 adalah angka bit pembagi dikurangi 1
1101 1000 1101 1010 1101 1110 1101 0110
Ketika bit paling kiri dari sisa adalah 0, harus menggunakan 0000 bukan pembagi asli
0000 1100 1101 001
Sisa atau n- bits (CRC)
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.
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. 111101 1101 1 0 0 1 0 0 0 0 1 1101
Pembagi –1101, data plus CRC–100100001, dan hasilnya 000
1000 1101 1010 1101 1110 1101 0110 0000
Ketika bit paling kiri dari sisa adalah 0, kita harus menggunakan 0000 bukan pembagi
1101 1101 000
Hasil CRC setelah dideteksi
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.
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
2.7.
10101001
(segmen data)
00111001
(segmen data)
00011101
(cek jumlah/ checksum)
11111111
(jumlah)
00000000
(komplemen)
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 bit Jumlah angka bit 2rm+r+1
Angka data bit Angka (m)
redundancy (r)
(m+r)
1
2
3
44
2
3
5
86
3
3
6
87
4
3
7
88
5
4
9
16 10
6
4
10
16 11
7
4
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. 11
10
9
8
7
6
5
4
3
2
1
m1
m2
m3
r8
m4
m5
m6
r4
m7
r2
r1
Bit redudancy
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 o r 2 adalah parity bit untuk satu kombinasi data bit, yaitu: r 2 : bit 2, 3, 6, 7, 10, 11
23
o r 4 adalah parity bit untuk satu kombinasi data bit, yaitu: r 4 : bit 4, 5, 6, 7 o r 8 adalah parity bit untuk satu kombinasi data bit, yaitu: 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
Mengirim 1
0
0
1
1
1
0
0
1
0
1
0
0
1
0
1
Error
Menerima 1
0
0
0
1
1
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. 11
10
9
8
7
6
5
4
3
2
1
1
0
0
1
0
1
0
0
1
0
1
11
10
9
8
7
6
5
4
3
2
1
1
0
0
1
0
1
0
0
1
0
1
r 1
( r1 dihitung dengan pengkombinasian bit 1, 3, 5, 7, 9 dan 11)
r 2
11
10
9
8
7
6
5
4
3
2
1
1
0
0
1
0
1
0
0
1
0
1
11
10
9
8
7
6
5
4
3
2
1
1
0
0
1
0
1
0
0
1
0
1
r 4
r 8
0
1
(Bit pada posisi 7 salah) 7
Gambar 2.16. Error Detection.
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 S1 S2 KONDISI 0 0 0 A 1 0 0 A 0 1 0 B 1 1 0 B 0 0 1 C 1 0 1 C 0 1 1 D 1 1 1 D
NEXT STATES S1’ S2’ KONDISI 0 0 A 1 0 B 0 1 C 1 1 D 0 0 A 1 0 B 0 1 C 1 1 D
OUTPUT V1 V2 0 0 1 1 1 0 0 1 1 1 0 0 0 1 1 0
Gambar 2.20. Diagram Keadaan Penyandian Convolution Code (2,1,2).
30
Reed Salomon Code
2.10
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, 2m-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-1x2t-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+0x2+3x3+x4
(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 = 2m -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-1xm-1+ 1x1+ 0
(2.11)
Untuk m=4 memiliki persamaan elemen Galois Field berikut :
3x3+ 2x2+1x1+ 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.
