Block Code

Kode balok (Block Code) adalah skema penyandian yang menggunakan kode-kode biner dengan panjang yang sama dan tetap. Dengan skema kode balok, sebuah pesan biner atau sebuah rangkaian bit data akan dipotong-potong menjadi blok-blok data yang masing-masing panjangnya k bit, dan tiap-tiap blok data sepanjang k bit ini kemudian akan dikonversi menjadi sebuah kode binear sepanjang n bit, di mana n>k. Himpunan kode biner yang dihasilkan disebut sebagai kode balok (n,k). Panjang k bit untuk sebuah blok data (pesan) menghasilkan kemungkinan xx blok pesan yang berbeda, yang masing-masingnya disebut sebagai tupel-k. Panjang n bit untuk blok kode menghasilkan kemungkinan [latex]\small 2^{k}[/latex] blok kode yang berbeda, yang masing-masingnya disebut sebagai tupel-n. Himpunan semua tupel-n (blok kode sepanjang n bit) yang didefinisikan untuk K=[0,1] dituliskan dengan notasi [latex]\small K^{n}[/latex]. Enkoder kanal akan melaksanakan pemetaan (transformasi) berikut ini :

[latex]\small T:U\rightarrow V[/latex]

di mana U adalah himpunan blok data biner sepanjang k, dan V adalah himpunan blok kode biner sepanjang n, di mana n>k. Masing-masing dari keseluruhan xx blok data (tupel-k) akan dipetakan ke sebuah blok kode (tupel-n) yang unik. Nilai rasio k/n disebut sebagai laju kode.

Field Biner

Himpunan semesta abjad K=[0,1] disebut sebagai field biner. Field biner memiliki dua jenis operasi, yaitu penjumlahan dan perkalian, yang akan menjadikan hasil operasinya tetap berada di dalam K. Untuk lebih jelasnya, aturan kedua operasi tersebut adalah sebagai berikut :
Penjumlahan :

[latex]\tiny 0\oplus 0=0 \ \ \ 1\oplus 1=0 \ \ \ 0\oplus1=1 \ \ \ 1\oplus0=1[/latex]

Perkalian

[latex]\tiny 0\cdot 0=0 \ \ \ 1\cdot 1=1 \ \ \ 0\cdot 1=0 \ \ \ 1\oplus0=0[/latex]

Kode Linear

Jika diketahui [latex]\tiny a=(a_{1},a_{2},…,a_{n}) \ \ \ dan \ \ \ b=(b_{1}, b_{2},…,b_{n})[/latex] adalah dua buah blok kode (tupel-n) di dalam sebuah himpunan kode balok C. Penjumlahan antara a dan b, yang dituliskan sebagai [latex]\tiny a\oplus b[/latex], didefinisikan oleh [latex]\tiny (a_{1}\oplus b_{1},a_{2}\oplus b_{2},…,a_{n}\oplus b_{n})[/latex]. Sebuah kode balok C akan disebut sebagai kode linear jika hasil penjumlahan dua kode biner (atau blok kode)nya adalah sebuah kode biner yang juga berada di dalam C. Sebuah kode lienar C harus memiliki kode biner nol 0=(0,0,..,0) sebagai salah satu anggota himpunannya, karena [latex]\tiny a\oplus a=0[/latex]

Bobot dan Jarak Hamming

Misalkan c adalah sebuah kode biner sepanjang n, Maka, bobot hamming (hamming weight) dari c, yang dituliskan dengan notasi w(c), adalah banyaknya bit 1 di dalam biner c. Misalkan a dan b adalah dua buah kode bienar yang berbeda, masing-masingnya sepanjang n. Maka, jarak hamming (hamming distance) antara a dan b, yang dituliskan notasi d(a,b) adalah banyak perbedaan bit di posisi yang sama antara kedua kode biner yaitu [latex]\tiny a_{j}\neq b_{j}, j=1,…,n[/latex]. Sehingga, bobot Hamming dari sebuah kode biner c adalah sama dengan jarak hamming antara kode biner tersebut dan kode biner 0 atau jelasnya

[latex]\tiny w(c)=d(c,0)[/latex]

Sehingga jarak Hamming dapat pula dituliskan sebagai fungsi dari bobot hamming, sebagaimana berikut ini

[latex]\tiny d(a,b)=w(a\oplus b)[/latex]

Jarak Minimum

Jarak minimum $d_{min}$ dari sebuah kode balok linear C adalah jarak Hamming terkecil di antara pasangan-pasangan kode biner yang menjadi anggota himpunan C. Dari sifat tertutup kode balok linear yaitu penjumlahan dengan modulo-2 dari sembarang dua buah kode binernya adalah sebuah kode biner yang juga anggota himpunannya.

“Jarak minimum $d_{min}$ dari sebuah kode linear C adalah bobot Hamming terkecil dari kode-kode biner bukan nol yang ada di dalam C”

Kemampuan Deteksi dan Koreksi Error

Jarak minimum $d_{min}$ dari sebuah kode linear C adalah salah satu parameter terpenting dari kode lienar tersebut. Bagi sebuah kode linear, parameter ini menentukan kemampuannya untuk mendeteksi dan/atau mengoreksi error. Hal ini dinyatakan oleh teorema berikut

“Sebuah kode linear C yang memiliki jarak minimum $d_{min}$ dapat mendeteksi hingga sebanyak t posisi error di dalam sembarang kode binernya, jika dan hanya jika

$d_{min}\geq t+1$
Sebuah kode linear C yang memiliki jarak minimum $d_{min}$ dapat mengoreksi hingga sebanyak t buah error di dalam sembarang kode binernya, jika dan hanya jika

$d_{min}\geq 2t+1$

Matriks Generator Kode

Untuk sebuah kode balok linear (n,k) C, kita dapat mendefinisikan sebuah vektor kode c dan sebuah vektor data (atau pesan atau informasi) d sebagai berikut :

$c=[c_{1},c_{2},...,c_{n}]$
$d=[d_{1},d_{2},...,d_{k}]$
Jika bit-bit data pada d muncul di vektor c, maka kode linear C dikatakan bersifat sistematis. JIka tidak demikian halnya, maka C dikatakan tidak sistematis. Di sini kita mengasumsikan bahwa k bit pertama dari c adalah bit-bit data, dan (n-k) bit selanjutnya adalah bit-bit cek paritas, yang dihasilkan dari suatu kombinasi linear bit-bit data, atau jelasnya

$\begin{matrix} c_{1}=d_{1}\\ c_{2}=d_{2}\\ ... \\ c_{k+1}=p_{11}d_{1}\oplus p_{12}d_{2}...\oplus p_{1k}d_{k} \\ c_{k+2}=p_{21}d_{1}\oplus p_{22}d_{2}...\oplus p_{2k}d_{k} \\ ... \\ c_{k+m}=p_{m1}d_{1}\oplus p_{m2}d_{2}...\oplus p_{mk}d_{k} \end{matrix}$
di mana $m=n-k$ . persamaan xx dapat dituliskan kembali dalam bentuk matriks sebagai berikut

$c=dG=\begin{bmatrix} d_{1} &d_{2} & ... & d_{k} \end{bmatrix}\begin{bmatrix} 1 & 0 & ... & 0 & p_{11} & p_{21} & ... &p_{m1} \\ 0 &1 &... &0 & p_{12} & p_{22} & ... &p_{m2} \\ ... & ... &... & ... &... &... &... &... \\ 0 & 0 & ... & 1 &p_{1k} & p_{2k} & ... &p_{mk} \end{bmatrix}$

di mana

$G=[I_{k}P^{T}]$

dimana $I_{k}$ adalah matriks identitasnya ordo ke-k dan [latex]\tiny P^{T}[/latex] adalah matriks transposisi dari matriks P di bawah ini

$P=\begin{bmatrix} p_{11} & p_{12} & ... &p_{1k} \\ p_{21} & p_{22} & ... &p_{2k} \\ ... &... &... &... \\ p_{m1} & p_{m1} & ... &p_{mk} \end{bmatrix}$

Matriks $G(k\ x \ n)$ dinamakan matriks generator kode. Perhatikan bahwa sebuah matriks generator untuk C harus memiliki sebanyak k baris dan n kolom, dan harus memiliki rank minimal k; yaitu sebanyak k baris dari matriks G harus bersifat independen secara linear.

Matrik Cek Paritas

Misalkan H melambangkan sebuah matriks m x n yang didefinisikan sebagai berikut :

$H=\begin{bmatrix} P & I_{m} \end{bmatrix}$

di mana m=n-k dan $I_{m}$ adalah matriks identitas orde ke-m, maka

$H^{T}=\begin{bmatrix} P^{T}\\ I_{m} \end{bmatrix}$

Dengan menggunakan persamaan diatas kita dapat menuliskan

$GH^{T}=\begin{bmatrix} I_{k} & P^{T} \end{bmatrix}\begin{bmatrix} P^{T}\\I_{m} \end{bmatrix}=P^{T}\oplus P^{T}=0$

di mana O melambangkan matriks nol k x m. Selanjutnya dari persamaan xx dan xx kita mendapatkan

$cH^{T}=dGH^{T}=0$

di mana 0 melambangkan vektor nol 1 x m

Matriks H dinamakan matriks cek paritas untuk C. Perhatikan bahwan rank H adalah m=n-k dan bahwa baris-baris H independen linear. Jarak minimum $d_{min}$ dari sebuah kode balok linear C terkait erat dengan struktur matriks cek paritas untuk C. Hal ini dinyatakan dalam teorema berikut ini

“Jarak minimum $d_{min}$ dari sebuah kode balok linear C adalah sama dengan jumlah minimum baris pada $H^{T}$ yang hasil penjumlahannya adalah vektor 0, di mana $H^{T}$ adalah matriks transposisi dari matriks cek paritas H untuk C”

Decoding Sindrom

Misalkan r melambangkan blok kode sepanjang n yang diterima di ujung penerima, jika kode biner c sepanjang n dikirimkan via suatu kanal yang terganggu derau. Maka, [latex]\tiny r=c \oplus e[/latex], di mana e disebut sebagai pola error. Perhatikan bahwa e=r+c.

Anggaplah kasus pertama adalah sebuah error tunggal di posisi ke-i pada blok data yang diterima. Maka, kita dapat merepresentasikan e sebagai vektor.

$e=[0..010...0]$
posisi ke-i

Selanjutnya, kita mengambil perkalian matriks $rH^{T}$ untuk mendapatkan

$rH^{T}=(c\oplus e)H^{T}=cH^{T}\oplus eH^{T}=eH^{T}=s$
dengan bantuan persamaan dan di sini s dinamakan sindrom dari r

Sehingga, dengan menggunakan s dan menganggap bahwa $eH^{T}$ adalah baris ke-i dari $H^{T}$ , kita menentukan posisi error pada blok kode yang diterima r. dengan cara membandingkan s terhadap baris-baris pada $H^{T}$ . Teknik decoding yang memanfaatkan proses perbandingan sederhana semacam ini dikenal dengan nama decoding sindrom. Perhatikan bahwa tidak semua pola error dapat di-decoding secara benar dengan menggunakan teknik decoding sindrom. Sindrom nol mengindikasikan bahwa r adalah sama dengan salah satu kode biner dan diasumsikan bebas error.

Dengan teknik decoding sindrom, sebuah kode balok linear (n,k) akan memiliki kemampuan untuk mengoreksi hingga t posisi error di dalam sebuah blok kode yang diterima, jika n dan k memenuhi batasan Hamming (Hamming bound) berikut ini :

$2^{n-k}=\sum_{i=0}^{t}\binom{n}{i}$

di mana

$\binom{n}{i}=\frac{n!}{(n-1)!i!}$

Sebuah kode balok yang dapat memenuhi persamaan diatas disebut sebagai kode sempurna. Kode-kode sempurna yang memiliki kemampuan mengoreksi sebuah error tunggal disebut kode hamming. Perhatikan bahwa batasan Hamming mutlak dipenuhi, namun bukan satu-satunya syarat yang diperlukan, untuk membuat sebuah kode balok linear dengan kemampuan koreksi t posisi error.

Lihat juga pembahasan tentang kode konvolusional

Referensi

[1] Komunikasi Analog dan Digital

S	S	R	K	J	S	M
				1	2	3
4	5	6	7	8	9	10
11	12	13	14	15	16	17
18	19	20	21	22	23	24
25	26	27	28	29	30	31