danang’s blog

Sandi blok pada prinsipnya adalah membentuk runtunan data dengan panjang tetap (k) selanjutnya menambahkan sejumlah (n-k) bit sehingga terbentuk codeword sepanjang n yang unik.

Jarak Hamming : banyaknya bit yang tidak sama antara dua codeword.

C1 = 011011,     C2 = 110001

Jarak hamming kedua codeword diatasa dapat dinyatakan d(C1,C2) = 3

Bagaiman penambahan bit ini dapat memberikan kemampuan koreksi pada transmisi data digital dapat dijelaskan pada contoh berikut :

misalkan : k =2 dan n=5 maka :

blok data : 00 01 10 11 diubah menjadi 5 bit data

codeword : 00000   00111   11001   11110

Selanjutnya deteksi dapat dilakukan ketika blok diterima berbeda dengan pola bit codeword terkirim misalkan diterima blok codeword 00100 yang bukan merupakan sandi yang sah. Jika kita perhatikan sandi tidak sah diterima hanya diperlukan pengubahan satu bit akan menghasilkan pola bit dari sandi yang sah, yaitu 00000 sedangkan untuk menjadi sandi sah yang lain diperlukan pengubahan 2 bit untuk 00111, 4 bit untuk 11001, dan 3 bit untuk 11110. Dapat kita ambil kesimpulan bahwa sandi diterima adalah 00000 karena memiliki kemungkinan terbesar dibandingkan dengan sandi sah lainya atau memiliki jarak hamming terkecil. Ini adalah kemampuan koreksi galat dengan penambahan bit redundansi.

Pada suatu sandi dengan sandi C1, C2, C3, … Cs dengan S = 2^k, jarak paling kecil dmin pada sandi dinyatakan sebagai :

dmin =min [d(Si,Sj)]  i ≠j

jika suatu sandi memenuhi dmin≥2t+1 dengan t bilangan bulat positif maka sandi dapat mengkoreksi galat sejumlah ≤t .  Selanjutnya hubungan antar dmin dan t dapat dinyatakan sebagai berikut :

t = floor (dmin-1)/2                   ; untuk mengkoreksi galat sejumlah t

t = dmin -1                                   ; untuk mendeteksi galat sejumlah t

Jika terjadi galat sejumlah dmin maka galat ini hanya mampu merubah satu codeword sah menjadi codeword sah yang lain, sementara ketika galat terjadi kuran dari dmin maka galat tidak akan merubah codeword sah menjadi codeword sah yang lain.

Beberapa pertimbangan dalam merancang sandi blok antara lain :

1. untuk n dan k, maka diharapakan dmin terbesar yang mungkin
2. harus mudah dalam penyandianya, tidak membutuhkan memori dan waktu proses yang banyak
3. redundan bit sedikit, hemat bandwidth
4. redundan bit banyak, mengurangi laju galat