Sandi Blok Risanuri Hidayat Jurusan Teknik Elektro dan Teknologi Informasi FT UGM
Sandi Blok disebut juga sebagai sandi (n, k) sandi. Sebuah blok k bit informasi disandikan menjadi blok n bit. Tetapi sebelum melangkah lebih jauh, perlu dilihat sebuah konsep dalam penyadian yang disebut sebagai jarak Hamming Katakanlah diinginkan sandi untuk 10 bilangan bulat, 0 sampai 9, dengan urutan digital. Ada empat bit untuk membentuk angka-angka bulat tersebut. Tabel 1 di bawah ini menunjukkan urutan angka-angka binernya. Enam urutan yang tersisa (10 s.d. 15) tidak digunakan.
Tabel 1. Angka Biner dan Nilai Desimal-nya Biner
Desimal
0000
0
0001
1
0010
2
0011
3
0100
4
0101
5
0110
6
0111
7
1000
8
1001
9
1010
Tdk digunakan
1011
Tdk digunakan
1100
Tdk digunakan
1101
Tdk digunakan
1110
Tdk digunakan
1111
Tdk digunakan
tersebut
beserta
angka
0000
0111
0001
1000
0010
1001
1010
0011
1100 1101 Va
lid
0100 0101
1011
0110
Tdk digunakan
Semua kombinasi yang mungkin untuk 4 bit data disebut ruang sandi. Untuk 4-bit data di atas terdapat 16 urutan ruang sandi, dan yang digunakan hanya sepuluh (valid). Enam kombinasi bit data yang lain tidak dipakai, dan tidak akan pernah dikirim. Sehingga jika ada kombinasi bit data yang tidak valid ini diterima di bagian penerima, maka penerima mengetahui bahwa ada kesalahan bit yang terkirim.
1110 1111
Ruang Sandi
Gambar . Ruang sandi yang berupa daftar kombinasi data 4-bit . Data yang valid merupakan bagian dari ruang sandi, yaitu berupa kombinasi data 4-bit yang dipakai.
1.1.1
Bobot Hamming
Bobot Hamming adalah jumlah terbesar dari nilai bit 1 dalam sebuah data yang valid. Dalam skema contoh ini bernilai 3, yaitu di antara 10 kombinasi bit yang valid (0111).
1.1.2
Konsep Jarak Hamming
Dalam sistem kontinyu, jarak diukur dengan konsep Euclidean seperti panjang, sudut dan vektor. Sedangkan di dunia biner, jarak yang dihitung antara dua kata biner dilaksanakan dengan sesuatu yang disebut jarak Hamming. Jarak Hamming adalah jumlah perbedaan nilai bit antara dua urutan biner yang ukurannya sama. Misal, jarak Hamming antara 001 dan 101 adalah = 1. Jarak Hamming antara 001 1001 dan 101 0100 adalah = 4 Jarak dan bobot Hamming merupakan konsep yang sangat penting dalam penyandian. Jarak Hamming digunakan untuk menentukan kemampuan sandi untuk mendeteksi dan memperbaiki kesalahan. Meskipun bobot Hamming sandi dalam hal ini adalah 3, jarak Hamming minimum adalah 1. Antara 1011 dan 1010 dibedakan hanya oleh satu bit. Kesalahan sebuah bit tunggal dapat menyebabkan 1011 menjadi 1010. Penerima akan membacanya sebagai 1010, dan akan melihatnya sebagai sebuah data yang valid. Penerima tidak akan pernah tahu bahwa sebenarnya urutan yang dikirim adalah 1011. Jadi kesalahan satu bit pada sebuah data valid yang berubah ke data valid lain tidak akan diketahui bahwa ada kesalahan bit.
Sekarang sandi diperpanjang dengan tambahan satu bit paritas. Jika jumlah bit bernilai 1 adalah genap, maka ditambahkan bit 1 pada sandi tersebut, dan jika jumlah bit bernilai 1 adalah ganjil, maka ditambahkan bit 0 pada akhir sandi tersebut. Ruang sandi sekarang bertambah besar dua kali lipat. Dari 16 kombinasi menjadi 32. Ruang sandi menjadi sama dengan 2N, di mana N adalah panjang sandi. Jika panjang sandi ditambah lagi, maka ruang sandi dapat bertambah menjadi 64. Jumlah sandi yang valid adalah 10 dari 32 pada kasus pertama, dan tetap 10 dari 64 pada kasus kedua. Kini ada tiga pilihan sandi, dengan 4, 5 atau 6-bit. Berat Hamming sandi biner pertama adalah 3, 4 untuk sandi kedua dan 5 untuk sandi terakhir. Jarak Hamming minimum untuk sandi pertama adalah 1. Jarak Hamming minimum untuk sandi kedua 2 bit dan 3 untuk yang terakhir. Pada sandi pertama, kesalahan bit tunggal tidak dapat ditoleransi (karena tidak dapat dideteksi). Pada sandi kedua, satu kesalahan bit dapat dideteksi karena kesalahan bit tunggal tidak menyebabkan satu sandi berubah ke bentuk sandi yang lain. Dapat dikatakan bahwa kemampuan deteksi kesalahannya adalah 1. Sandi terakhir dapat mendeteksi sampai 2 bit kesalahan. Sehingga kemampuan deteksi kesalahan adalah 2 bit.
Tabel 2. Data valid dan penambahan bit paritas Desi mal
Biner
Tambah 1 bit paritas
Tambah 1 lagi bit paritas
0
0000
0000 0
0000 00
1
0001
0001 1
0001 10
2
0010
0010 1
0010 10
3
0011
0011 0
0011 00
4
0100
0100 1
0100 10
5
0101
0101 0
0101 00
6
0110
0110 0
0110 00
7
0111
0111 1
0111 10
8
1000
1000 1
1000 10
9
1001
1001 0
1001 00
6 lagi tak digunakan
22 lagi tak digunakan
52 lagi tak digunakan
Jumlah maksimum kesalahan bit dapat diketahui adalah 𝑡 = 𝑑𝑚𝑖𝑛 − 1
𝑑𝑚𝑖𝑛 adalah jarak Hamming dari sandi. Untuk sandi dengan 𝑑𝑚𝑖𝑛 = 3, 1 dan 2 bit kesalahan dapat dideteksi dengan baik. Dengan demikian dapat dibuat sejumlah sandi dengan jarak Hamming sedemikian sehingga mampu mendeteksi kesalahan bit sejumlah yang diinginkan. Namun jarak Hamming yang besar membutuhkan sandi yang panjang. Hal ini akan menambah panjang kepala (overhead), dan mengurangi kecepatan data pada sebuah kanal dengan lebar bidang tertentu, sebagaimana pepatah bahwa jer basuki mawa bea (segala usaha untuk menjadi lebih baik pasti butuh pengorbanan.
1.1.3
Membuat sandi blok
Sandi blok dituliskan dengan (n.k). Sandi mengandung k bit informasi dan menghitung (n-k) bit paritas dari matriks generator sandi. Kebanyakan sandi blok tidak mengubah bit informasi walaupun bit paritas ditambahkan baik di depan atau pun di belakang bit informasi tersebut.
Sandi Hamming, sandi blok linear sederhana Kode Hamming yang paling banyak digunakan kode blok linear. Sebuah kode Hamming umumnya ditentukan sebagai (2𝑛 − 1, 2𝑛 − 𝑛 − 1). Ukuran blok adalah sama dengan 2𝑛 − 1. Jumlah bit informasi dalam blok adalah sama dengan 2𝑛 − 𝑛 − 1, dan jumlah bit overhead adalah n. Semua sandi Hamming dapat mendeteksi kesalahan 3 bit dan dan mengkoreksi satu bit. Umumnya ukuran sandi Hamming adalah (7, 4), (15,11) dan (31, 26), yang ke semuanya ini mempunyai jarak Hamming yang sama. Kita lihat sandi Hamming (7,4). Dalam sandi ini, panjang data informasi adalah 4 bit. Sehingga hanya ada 16 kombinasi bit yang mungkin. Tabel 3 berikut menunjukkan semua 16 kombinasi tersebut.
Tabel 3. Informasi dan kombinasi bit data Informasi
bit ke 1
bit ke 2
bit ke 3
bit ke 4
0
0
0
0
0
1
0
0
0
1
2
0
0
1
0
3
0
0
1
1
4
0
1
0
0
5
0
1
0
1
6
0
1
1
0
7
0
1
1
1
8
1
0
0
0
9
1
0
0
1
10
1
0
1
0
11
1
0
1
1
12
1
1
0
0
13
1
1
0
1
14
1
1
1
0
15
1
1
1
1
Tiga bit paritas akan ditambahkan ke bit-bit data di atas. Akan ada delapan kombinasi yang berbeda dari 3 bit paritas yang mungkin. Dengan mengabaikan kombinasi semua nol (000) dan menuliskan tujuh kombinasi yang tersisa, hasilnya terlihat pada Tabel 4.
Tabel 4. Kombinasi 3 bit paritas Kombi nasi ke
Paritas
1
001
2
010
3
011
4
100
5
101
6
110
7
111
Katakanlah matriks H ada tujuh baris, disebut dengan matriks paritas sandi. Matriks ini mempunyai n baris dan n-k kolom. Untuk sandi (7, 4), ada 7 baris dan 3 kolom. Baris-baris matriks disusun ulang dengan baris dasar untuk bersama-sama baik di atas atau di bagian bawah. Penataan akan memberikan sandi Hamming baru. Berikut ini adalah hanya dua cara menyusun baris-baris H, yang masing-masing akan menghasilkan sandi yang berbeda.
𝐻=
1 1 1 0 1 1 1 0 1 1 1 0 −−−−− 1 0 0 0 1 0 0 0 1
atau dengan susunan yang berbeda 𝐻 =
1 1 1 0 1 1 1 1 0 1 0 1 −−−−− 0 0 1 0 1 0 1 0 0
Ambil bagian atas dari matriks ini (atas garis), dan buat sebuah matriks baru G
𝐺=
1 0 0 0
0 1 0 0
0 0 1 0
0 0 0 1
1 0 1 1
1 1 1 0
1 1 0 1
Ambil bagian atas dari matriks H (sebagai contoh, ambil matriks H yang kanan), tempelkan di sebelah kanan sebuah matriks identitas, sehingga membentuk sebuah matriks baru ukuran (4 x 7). Matriks ini adalah matriks generator, yang akan memetakan ke 16 informasi ke 16 sandi yang valid. Penyusunan baris H yang berbeda akan menyebabkan matriks G berbeda, sehingga akan membentuk pemetaan yang berbeda. Point penting di sini adalah bahwa dua sandi blok dengan ukuran yang sama akan menyebabkan pemetaan yang berbeda tergantung pada susunan baris-barisnya, namun masing-masing pemetaan mempunyai bobot Hamming yang sama dan mempunyai kemampuan koreksi/deteksi kesalahan yang sama. c adalah sandi yang dikirim, diperoleh dari perkalian antara informasi vektor d dengan matriks G, c = d. G
Contoh, Data informasi 0110 akan menghasilkan sandi terkirim sepanjang 7 bit,
𝑐= 0 1
1.1.4
1 0
1 0 0 0
0 1 0 0
0 0 1 0
0 0 0 1
1 0 1 1
1 1 1 0
1 1 = 0 0 1
1 1 0
1 0
1
Pengawa Sandi
Konsep utama pengawa-sandi (decoder) adalah untuk menentukan yang mana dari 2k sandi yang valid terkirim di antara salah satu dari 2n sandi yang telah diterima. Lanjutan dari contoh sandi blok (7, 4) sebelumnya.
Pengawa sandi blok cukup mudah. Akan dihitung sebuah Sindrom (s) dari sebuah sandi yang masuk. Kalikan vektor masuk dengan transpose paritas matriks H. (Ingat bahwa perkalian dengan matriks G di sisi pengirim/penyandi dan perkalian dengan H di sisi penerima)
𝑠 = 𝑐. 𝐻
Ukuran dari sindrom sama dengan (n-k) bit. Dari contoh sandi (7, 4) di atas, panjang bit adalah tiga. Untuk mudahnya, ketika sindrom semua bernilai nol maka berarti tidak terjadi kesalahan. Jadi di sini diinginkan sindrom sama dengan nol. Dari contoh di atas, kalikan vektor sandi yang diterima [0 1 1 0 1 0 1] dengan matriks HT, untuk diuji apakah sindrom bernilai semua nol, yang membuktikan bahwa yang diterima adalah sandi yang valid.
𝑠= 0 1 1 0 1 0 1
1 0 1 1
1 1 1 0
1 1 0 1
0 0 1 0 1 0 1 0 0
1.0 + 0.1 + 1.1 + 1.0 + 0.1 + 0.0 + 1.1 𝑠 = 1.0 + 1.1 + 1.1 + 0.0 + 0.1 + 1.0 + 0.1 1.0 + 1.1 + 0.1 + 1.0 + 1.1 + 0.0 + 0.1
= 0 0
0
Hasilnya adalah (0 0 0), sindrom dengan semua nol.
Katakanlah sebuah kesalahan terjadi. Vektor yang diterima sekarang (1 1 1 0 1 0 1), yaitu bit paling kiri diterima terbalik. Penghitungan sindrom mendapatkan
𝑠= 1 1 1 0 1 0 1
1 0 1 1
1 1 1 0
1 1 0 1
0 0 1 0 1 0 1 0 0
1.1 + 0.1 + 1.1 + 1.0 + 0.1 + 0.0 + 1.1 𝑠 = 1.1 + 1.1 + 1.1 + 0.0 + 0.1 + 1.0 + 0.1 1.1 + 1.1 + 0.1 + 1.0 + 1.1 + 0.0 + 0.1
= 1 1
1
Hasil sindrom (1 1 1) adalah yang merupakan baris pertama pada matriks H. Sehingga kesalahan bit terjadi pada bit pertama (paling kiri) yang bernilai 1. Koreksi dilakukan dengan membalik ulang bit di posisi tersebut dari 1 kembali ke 0. Vektor yang seharusnya adalah (0 1 1 0 1 0 1)
Berikut adalah contoh lain, bit-bit yang diterima adalah (0 1 1 1 1 1 0). kalau ada kesalahan bit, di mana terjadi kesalahan bit tersebut.
𝑠= 0 1 1 1 1 1 0
1 0 1 1
1 1 1 0
1 1 0 1
0 0 1 0 1 0 1 0 0
1.0 + 0.1 + 1.1 + 1.1 + 0.1 + 0.1 + 1.0 𝑠 = 1.0 + 1.1 + 1.1 + 0.1 + 0.1 + 1.1 + 0.0 1.0 + 1.1 + 0.1 + 1.1 + 1.1 + 0.1 + 0.0
= 0 1
1
s = (0 1 1) terletak di baris ke dua. Maka kesalahan bit terjadi pada bit kedua. Vektor yang seharusnya adalah (0 0 1 1 1 1 0) 𝑠𝑑𝑖𝑡𝑒𝑟𝑖𝑚𝑎 = 0
1 1 1 1 1
0
𝑠𝑡𝑒𝑟𝑘𝑜𝑟𝑒𝑘𝑠𝑖 = 0
1 1 1 1 1
0
Terbukti metode ini tidak hanya mendeteksi bahwa sebuah kesalahan bit telah terjadi, namun diketahui pula posisi (lokasi) kesalahan bit sehingga dapat diperbaiki. Semua kesalahan bit tunggal dapat dideteksi dan dikoreksi dengan metode ini. Mengingat bahwa probabilitas kesalahan bit tunggal jauh lebih besar daripada kesalahan lebih dari satu bit, metode pengawa sandi ini disebut dengan Pengawa-sandi Kemungkinan Maksimum (Maximum Likelihood Decoding, MLD). MLD merupakan metode yang paling efisien meskipun metode lain seperti tetangga terdekat memberikan hasil yang lebih baik, namun dengan mengorbankan kecepatan decoding dan memori.
Sumber: http://www.complextoreal.com/chapters/block.pdf
