Lewati ke konten utama

Bagian 8.2 Kode Linear

Untuk memperoleh pemahaman lebih mendalam tentang suatu kode dan mengembangkan teknik pengodean, pendekodean, dan pendeteksian kesalahan yang lebih efisien, kita perlu menambahkan struktur pada kode tersebut. Salah satu caranya adalah mensyaratkan agar kode tersebut juga merupakan grup. Kode grup adalah kode yang juga merupakan subgrup dari \({\mathbb Z}_2^n\text{.}\)
Untuk memeriksa bahwa suatu kode merupakan kode grup, kita hanya perlu memverifikasi satu hal. Jika sebarang dua unsur dalam kode dijumlahkan, hasilnya harus merupakan tupel-\(n\) yang kembali berada dalam kode. Tidak perlu diperiksa bahwa invers tupel-\(n\) tersebut berada dalam kode, sebab setiap kata kode merupakan invers dirinya sendiri, dan juga tidak perlu diperiksa bahwa \({\mathbf 0}\) merupakan kata kode. Sebagai contoh,
\begin{equation*} (\codeword{11000101}) + (\codeword{11000101}) = (\codeword{00000000})\text{.} \end{equation*}

Contoh 8.2.1.

Andaikan kita mempunyai kode yang terdiri atas tupel-7 berikut:
\begin{align*} &(\codeword{0000000}) & & (\codeword{0001111}) & & (\codeword{0010101}) & & (\codeword{0011010})\\ &(\codeword{0100110}) & & (\codeword{0101001}) & & (\codeword{0110011}) & & (\codeword{0111100})\\ &(\codeword{1000011}) & & (\codeword{1001100}) & & (\codeword{1010110}) & & (\codeword{1011001})\\ &(\codeword{1100101}) & & (\codeword{1101010}) & & (\codeword{1110000}) & & (\codeword{1111111})\text{.} \end{align*}
Memverifikasi bahwa kode ini juga merupakan subgrup dari \({\mathbb Z}_2^7\text{,}\) dan oleh karena itu merupakan kode grup, merupakan tugas langsung meskipun melelahkan. Kode ini merupakan kode pendeteksi dan pengoreksi kesalahan tunggal, tetapi menghitung semua jarak antara pasangan kata kode untuk menentukan bahwa \(d_{\min} = 3\) merupakan proses yang panjang dan melelahkan. Jauh lebih mudah melihat bahwa bobot minimum semua kata kode tak nol adalah \(3\text{.}\) Seperti akan segera kita lihat, hal ini bukan kebetulan. Namun, hubungan antara bobot dan jarak dalam suatu kode sangat bergantung pada fakta bahwa kode tersebut merupakan grup.

Bukti.
Andaikan \({\mathbf x}\) dan \({\mathbf y}\) merupakan tupel-\(n\) biner. Maka jarak antara \({\mathbf x}\) dan \({\mathbf y}\) tepat sama dengan banyaknya posisi tempat \({\mathbf x}\) dan \({\mathbf y}\) berbeda. Namun, \({\mathbf x}\) dan \({\mathbf y}\) berbeda pada suatu koordinat tepat ketika jumlah pada koordinat tersebut adalah \(1\text{,}\) sebab
\begin{align*} 1 + 1 & = 0\\ 0 + 0 & = 0\\ 1 + 0 & = 1\\ 0 + 1 & = 1\text{.} \end{align*}
Akibatnya, bobot jumlah tersebut harus sama dengan jarak antara kedua kata kode.

Bukti.
Perhatikan bahwa
\begin{align*} d_{\min} & = \min \{ d({\mathbf x},{\mathbf y}) : {\mathbf x}\neq{\mathbf y} \}\\ &= \min \{ d({\mathbf x},{\mathbf y}) : {\mathbf x}+{\mathbf y} \neq {\mathbf 0} \}\\ &= \min\{ w({\mathbf x} + {\mathbf y}) : {\mathbf x}+{\mathbf y}\neq {\mathbf 0} \}\\ & = \min\{ w({\mathbf z}) : {\mathbf z} \neq {\mathbf 0} \}\text{.} \end{align*}

Subbagian 8.2.1 Kode Linear

Dari Contoh 8.2.1, kini mudah diperiksa bahwa bobot tak nol minimum adalah \(3\text{;}\) dengan demikian, kode tersebut memang mendeteksi dan mengoreksi semua kesalahan tunggal. Kini kita telah mereduksi masalah pencarian kode yang “baik” menjadi masalah membangkitkan kode grup. Salah satu cara mudah membangkitkan kode grup adalah menggunakan sedikit teori matriks.
Definisikan hasil kali dalam dari dua tupel-\(n\) biner sebagai
\begin{equation*} {\mathbf x} \cdot {\mathbf y} = x_1 y_1 + \cdots + x_n y_n\text{,} \end{equation*}
dengan \({\mathbf x} = (x_1, x_2, \ldots, x_n)^\transpose\) dan \({\mathbf y} = (y_1, y_2, \ldots, y_n)^\transpose\) merupakan vektor kolom.
 1 
Karena kita akan bekerja dengan matriks, dalam sisa bab ini kita akan menulis tupel-\(n\) biner sebagai vektor kolom.
Sebagai contoh, jika \({\mathbf x} = (\codeword{011001})^\transpose\) dan \({\mathbf y} = (\codeword{110101})^\transpose\text{,}\) maka \({\mathbf x} \cdot {\mathbf y} = 0\text{.}\) Kita juga dapat memandang hasil kali dalam sebagai hasil kali matriks baris dengan matriks kolom; yaitu,
\begin{align*} {\mathbf x} \cdot {\mathbf y} & = {\mathbf x}^\transpose {\mathbf y}\\ & = \begin{pmatrix} x_1 & x_2 & \cdots & x_n \end{pmatrix} \begin{pmatrix} y_1 \\ y_2 \\ \vdots \\ y_n \end{pmatrix}\\ & = x_{1}y_{1} + x_{2}y_{2} + \cdots + x_{n}y_{n}\text{.} \end{align*}

Contoh 8.2.4.

Andaikan kata-kata yang hendak dikodekan terdiri atas semua tupel-\(3\) biner dan skema pengodean kita menggunakan paritas genap. Untuk mengodekan sebarang tupel-\(3\text{,}\) kita menambahkan bit keempat agar diperoleh jumlah bit \(1\) yang genap. Perhatikan bahwa sebarang tupel-\(n\) \({\mathbf x} = (x_1, x_2, \ldots, x_n)^\transpose\) mempunyai jumlah bit \(1\) yang genap tepat ketika \(x_1 + x_2 + \cdots + x_n = 0\text{;}\) dengan demikian, tupel-\(4\) \({\mathbf x} = (x_1, x_2, x_3, x_4)^\transpose\) mempunyai jumlah bit \(1\) yang genap jika \(x_1+ x_2+ x_3+ x_4 = 0\text{,}\) atau
\begin{equation*} {\mathbf x} \cdot {\mathbf 1} = {\mathbf x}^\transpose {\mathbf 1} = \begin{pmatrix} x_1 & x_2 & x_3 & x_4 \end{pmatrix} \begin{pmatrix} 1 \\ 1 \\ 1 \\ 1 \end{pmatrix} = 0\text{.} \end{equation*}
Contoh ini memberi petunjuk bahwa terdapat hubungan antara matriks dan teori pengodean.
Misalkan \({\mathbb M}_{m \times n}({\mathbb Z}_2)\) melambangkan himpunan semua matriks \(m \times n\) dengan entri dalam \({\mathbb Z}_2\text{.}\) Kita melakukan operasi matriks seperti biasa, kecuali bahwa semua operasi penjumlahan dan perkalian berlangsung dalam \({\mathbb Z}_2\text{.}\) Definisikan ruang nol dari suatu matriks \(H \in {\mathbb M}_{m \times n}({\mathbb Z}_2)\) sebagai himpunan semua tupel-\(n\) biner \({\mathbf x}\) sedemikian sehingga \(H{\mathbf x} = {\mathbf 0}\text{.}\) Kita melambangkan ruang nol matriks \(H\) dengan \(\Null(H)\text{.}\)

Contoh 8.2.5.

Andaikan
\begin{equation*} H = \begin{pmatrix} 0 & 1 & 0 & 1 & 0 \\ 1 & 1 & 1 & 1 & 0 \\ 0 & 0 & 1 & 1 & 1 \end{pmatrix}\text{.} \end{equation*}
Agar tupel-\(5\) \({\mathbf x} = (x_1, x_2, x_3, x_4, x_5)^\transpose\) berada dalam ruang nol \(H\text{,}\) \(H{\mathbf x} = {\mathbf 0}\text{.}\) Secara ekuivalen, sistem persamaan berikut harus dipenuhi:
\begin{align*} x_2 + x_4 & = 0\\ x_1 + x_2 + x_3 + x_4 & = 0\\ x_3 + x_4 + x_5 & = 0\text{.} \end{align*}
Himpunan tupel-\(5\) biner yang memenuhi persamaan-persamaan ini adalah
\begin{equation*} (\codeword{00000}) \qquad (\codeword{11110}) \qquad (\codeword{10101}) \qquad (\codeword{01011})\text{.} \end{equation*}
Mudah ditentukan bahwa kode ini merupakan kode grup.

Bukti.
Karena setiap unsur \({\mathbb Z}_2^n\) merupakan invers dirinya sendiri, satu-satunya hal yang benar-benar perlu diperiksa di sini adalah ketertutupan. Misalkan \({\mathbf x}, {\mathbf y} \in \Null(H)\) untuk suatu matriks \(H\) dalam \({\mathbb M}_{m \times n}({\mathbb Z}_2)\text{.}\) Maka \(H{\mathbf x} = {\mathbf 0}\) dan \(H{\mathbf y} = {\mathbf 0}\text{.}\) Jadi,
\begin{equation*} H({\mathbf x}+{\mathbf y}) = H{\mathbf x} + H{\mathbf y} = {\mathbf 0} + {\mathbf 0} = {\mathbf 0}\text{.} \end{equation*}
Dengan demikian, \({\mathbf x} + {\mathbf y}\) berada dalam ruang nol \(H\) dan karenanya harus merupakan kata kode.
Suatu kode disebut kode linear jika ditentukan oleh ruang nol suatu matriks \(H \in {\mathbb M}_{m \times n}({\mathbb Z}_2)\text{.}\)

Contoh 8.2.7.

Misalkan \(C\) adalah kode yang diberikan oleh matriks
\begin{equation*} H = \begin{pmatrix} 0 & 0 & 0 & 1 & 1 & 1 \\ 0 & 1 & 1 & 0 & 1 & 1 \\ 1 & 0 & 1 & 0 & 0 & 1 \end{pmatrix}\text{.} \end{equation*}
Andaikan tupel-\(6\) \({\mathbf x} = (\codeword{010011})^\transpose\) diterima. Menentukan apakah \({\mathbf x}\) merupakan kata kode cukup dilakukan melalui perkalian matriks sederhana. Karena
\begin{equation*} H{\mathbf x} = \begin{pmatrix} 0 \\ 1 \\ 1 \end{pmatrix}\text{,} \end{equation*}
kata yang diterima bukan kata kode. Kita harus mencoba mengoreksi kata tersebut atau meminta agar kata itu ditransmisikan kembali.
Sblm.Paling AtasLanjut