Lewati ke konten utama

Bagian 8.3 Matriks Pemeriksa Paritas dan Matriks Pembangkit

Kita perlu menemukan cara sistematis untuk membangkitkan kode linear serta metode pendekodean yang cepat. Dengan memeriksa sifat-sifat matriks \(H\) dan memilih \(H\) dengan cermat, kita dapat mengembangkan metode pengodean dan pendekodean pesan yang sangat efisien. Untuk tujuan ini, kita akan memperkenalkan matriks pembangkit standar dan matriks pemeriksa paritas kanonik.
Andaikan \(H\) adalah matriks \(m \times n\) dengan entri dalam \({\mathbb Z}_2\) dan \(n \gt m\text{.}\) Jika \(m\) kolom terakhir matriks tersebut membentuk matriks identitas \(m \times m\text{,}\) \(I_m\text{,}\) maka matriks tersebut merupakan matriks pemeriksa paritas kanonik. Secara lebih khusus, \(H= (A \mid I_m)\text{,}\) dengan \(A\) adalah matriks \(m \times (n-m)\)
\begin{equation*} \begin{pmatrix} a_{11} & a_{12} & \cdots & a_{1,n-m} \\ a_{21} & a_{22} & \cdots & a_{2,n-m} \\ \vdots & \vdots & \ddots & \vdots \\ a_{m1} & a_{m2} & \cdots & a_{m,n-m} \end{pmatrix} \end{equation*}
dan \(I_m\) adalah matriks identitas \(m \times m\)
\begin{equation*} \begin{pmatrix} 1 & 0 & \cdots & 0 \\ 0 & 1 & \cdots & 0 \\ \vdots & \vdots & \ddots & \vdots \\ 0 & 0 & \cdots & 1 \end{pmatrix}\text{.} \end{equation*}
Dengan setiap matriks pemeriksa paritas kanonik, kita dapat mengaitkan sebuah \(n \times (n-m)\) matriks pembangkit standar
\begin{equation*} G = \left( \frac{I_{n-m}}{A} \right)\text{.} \end{equation*}
Tujuan kita adalah menunjukkan bahwa terdapat \(\mathbf x\) yang memenuhi \(G {\mathbf x} = {\mathbf y}\) jika dan hanya jika \(H{\mathbf y} = {\mathbf 0}\text{.}\) Diberikan blok pesan \({\mathbf x}\) yang hendak dikodekan, matriks \(G\) memungkinkan kita mengodekannya dengan cepat menjadi kata kode linear \({\mathbf y}\text{.}\)

Contoh 8.3.1.

Andaikan kita mempunyai delapan kata berikut untuk dikodekan:
\begin{equation*} (\codeword{000}), (\codeword{001}), (\codeword{010}), \ldots, (\codeword{111})\text{.} \end{equation*}
Untuk
\begin{equation*} A = \begin{pmatrix} 0 & 1 & 1 \\ 1 & 1 & 0 \\ 1 & 0 & 1 \end{pmatrix}\text{,} \end{equation*}
matriks pembangkit standar dan matriks pemeriksa paritas kanonik yang terkait adalah
\begin{equation*} G= \begin{pmatrix} 1 & 0 & 0 \\ 0 & 1 & 0 \\ 0 & 0 & 1 \\ 0 & 1 & 1 \\ 1 & 1 & 0 \\ 1 & 0 & 1 \end{pmatrix} \end{equation*}
dan
\begin{equation*} H = \begin{pmatrix} 0 & 1 & 1 & 1 & 0 & 0 \\ 1 & 1 & 0 & 0 & 1 & 0 \\ 1 & 0 & 1 & 0 & 0 & 1 \end{pmatrix}\text{,} \end{equation*}
secara berurutan.
Perhatikan bahwa baris-baris dalam \(H\) merepresentasikan pemeriksaan paritas pada posisi bit tertentu dalam tupel-\(6\text{.}\) Bit-bit \(1\) dalam matriks identitas berfungsi sebagai pemeriksa paritas untuk bit-bit \(1\) pada baris yang sama. Jika \({\mathbf x} = (x_1, x_2, x_3, x_4, x_5, x_6)\text{,}\) maka
\begin{equation*} {\mathbf 0} = H{\mathbf x} = \begin{pmatrix} x_2 + x_3 + x_4 \\ x_1 + x_2 + x_5\\ x_1 + x_3 + x_6 \end{pmatrix}\text{,} \end{equation*}
yang menghasilkan sistem persamaan:
\begin{align*} x_2 + x_3 + x_4 & = 0\\ x_1 + x_2 + x_5 & = 0\\ x_1 + x_3 + x_6 & = 0\text{.} \end{align*}
Di sini \(x_4\) berfungsi sebagai bit pemeriksa untuk \(x_2\) dan \(x_3\text{;}\) \(x_5\) adalah bit pemeriksa untuk \(x_1\) dan \(x_2\text{;}\) dan \(x_6\) adalah bit pemeriksa untuk \(x_1\) dan \(x_3\text{.}\) Matriks identitas mencegah \(x_4\text{,}\) \(x_5\text{,}\) dan \(x_6\) harus saling memeriksa. Dengan demikian, \(x_1\text{,}\) \(x_2\text{,}\) dan \(x_3\) dapat dipilih sebarang, tetapi \(x_4\text{,}\) \(x_5\text{,}\) dan \(x_6\) harus dipilih untuk menjamin paritas. Ruang nol \(H\) mudah dihitung sebagai
\begin{equation*} \begin{array}{cccc} (\codeword{000000}) & (\codeword{001101}) & (\codeword{010110}) & (\codeword{011011}) \\ (\codeword{100011}) & (\codeword{101110}) & (\codeword{110101}) & (\codeword{111000}). \end{array} \end{equation*}
Cara yang lebih mudah lagi untuk menghitung ruang nol adalah menggunakan matriks pembangkit \(G\) (Tabel 8.3.2).
Tabel 8.3.2. Kode yang dibangkitkan oleh matriks
Kata Pesan \(\mathbf x\) Kata Kode \(G \mathbf x\)
\(\codeword{000}\) \(\codeword{000000}\)
\(\codeword{001}\) \(\codeword{001101}\)
\(\codeword{010}\) \(\codeword{010110}\)
\(\codeword{011}\) \(\codeword{011011}\)
\(\codeword{100}\) \(\codeword{100011}\)
\(\codeword{101}\) \(\codeword{101110}\)
\(\codeword{110}\) \(\codeword{110101}\)
\(\codeword{111}\) \(\codeword{111000}\)
Pembuktian teorema ini kami serahkan sebagai latihan. Berdasarkan teorema tersebut, \(n - m\) bit pertama dalam \({\mathbf x}\) disebut bit informasi, sedangkan \(m\) bit terakhir disebut bit pemeriksa. Dalam Contoh 8.3.1, tiga bit pertama merupakan bit informasi dan tiga bit terakhir merupakan bit pemeriksa.

Bukti.
Misalkan \(G {\mathbf x}_1 = {\mathbf y}_1\) dan \(G {\mathbf x}_2 ={\mathbf y}_2\) adalah dua kata kode. Maka \({\mathbf y}_1 + {\mathbf y}_2\) berada dalam \(C\) karena
\begin{equation*} G( {\mathbf x}_1 + {\mathbf x}_2) = G {\mathbf x}_1 + G {\mathbf x}_2 = {\mathbf y}_1 + {\mathbf y}_2\text{.} \end{equation*}
Kita juga harus menunjukkan bahwa dua blok pesan tidak dapat dikodekan menjadi kata kode yang sama. Artinya, kita harus menunjukkan bahwa jika \(G {\mathbf x} = G {\mathbf y}\text{,}\) maka \({\mathbf x} = {\mathbf y}\text{.}\) Misalkan \(G {\mathbf x} = G {\mathbf y}\text{.}\) Maka
\begin{equation*} G {\mathbf x} - G {\mathbf y} = G( {\mathbf x} - {\mathbf y}) = {\mathbf 0}\text{.} \end{equation*}
Namun, \(k\) koordinat pertama dalam \(G( {\mathbf x} - {\mathbf y})\) tepat sama dengan \(x_1 -y_1, \ldots, x_k - y_k\text{,}\) karena koordinat-koordinat tersebut ditentukan oleh matriks identitas \(I_k\text{,}\) yang merupakan bagian dari \(G\text{.}\) Jadi, \(G( {\mathbf x} - {\mathbf y}) = {\mathbf 0}\) tepat ketika \({\mathbf x} = {\mathbf y}\text{.}\)
Sebelum kita dapat membuktikan hubungan antara matriks pemeriksa paritas kanonik dan matriks pembangkit standar, kita perlu membuktikan sebuah lema.

Bukti.
Misalkan \(C = HG\text{.}\) Entri ke-\(ij\) dalam \(C\) adalah
\begin{align*} c_{ij} & = \sum_{k=1}^n h_{ik} g_{kj}\\ & = \sum_{k=1}^{n-m} h_{ik} g_{kj} + \sum_{k=n-m+1}^n h_{ik} g_{kj}\\ & = \sum_{k=1}^{n-m} a_{ik} \delta_{kj} + \sum_{k=n-m+1}^n \delta_{i-(m-n),k} a_{kj}\\ & = a_{ij} + a_{ij}\\ & = 0\text{,} \end{align*}
dengan
\begin{equation*} \delta_{ij} = \begin{cases} 1 & i = j \\ 0 & i \neq j \end{cases} \end{equation*}
adalah delta Kronecker.

Bukti.
Pertama, misalkan \({\mathbf y} \in C\text{.}\) Maka \(G {\mathbf x} = {\mathbf y}\) untuk suatu \({\mathbf x} \in {\mathbb Z}_2^m\text{.}\) Berdasarkan Lema 8.3.5, \(H {\mathbf y} = HG {\mathbf x} = {\mathbf 0}\text{.}\)
Sebaliknya, misalkan \({\mathbf y} = (y_1, \ldots, y_n)^\transpose\) berada dalam ruang nol \(H\text{.}\) Kita perlu mencari suatu \({\mathbf x}\) dalam \({\mathbb Z}_2^{n-m}\) sedemikian sehingga \(G {\mathbf x}^\transpose = {\mathbf y}\text{.}\) Karena \(H {\mathbf y} = {\mathbf 0}\text{,}\) sistem persamaan berikut harus dipenuhi:
\begin{align*} a_{11} y_1 + a_{12} y_2 + \cdots + a_{1, n-m} y_{n-m} + y_{n-m+1} & = 0\\ a_{21} y_1 + a_{22} y_2 + \cdots + a_{2, n-m} y_{n-m} + y_{n-m+2} & = 0\\ & \aatavdots{=}\\ a_{m1} y_1 + a_{m2} y_2 + \cdots + a_{m, n-m} y_{n-m} + y_{n-m+m} & = 0\text{.} \end{align*}
Secara ekuivalen, \(y_{n-m+1}, \ldots, y_n\) ditentukan oleh \(y_1, \ldots, y_{n-m}\text{:}\)
\begin{align*} y_{n-m+1} & = a_{11} y_1 + a_{12} y_2 + \cdots + a_{1, n-m} y_{n-m}\\ y_{n-m+2} & = a_{21} y_1 + a_{22} y_2 + \cdots + a_{2, n-m} y_{n-m}\\ & \aatavdots{=}\\ y_{n} & = a_{m1} y_1 + a_{m2} y_2 + \cdots + a_{m, n-m} y_{n-m}\text{.} \end{align*}
Akibatnya, kita dapat menetapkan \(x_i = y_i\) untuk \(i= 1, \ldots, n - m\text{.}\)
Akan sangat membantu apabila kita dapat menghitung jarak minimum suatu kode linear secara langsung dari matriks \(H\)-nya untuk menentukan kemampuan kode tersebut dalam mendeteksi dan mengoreksi kesalahan. Misalkan
\begin{align*} {\mathbf e}_1 & = (\codeword{100 \cdots 00})^\transpose\\ {\mathbf e}_2 & = (\codeword{010 \cdots 00})^\transpose\\ & \aatavdots{=}\\ {\mathbf e}_n & = (\codeword{000 \cdots 01})^\transpose \end{align*}
adalah tupel-\(n\) dalam \({\mathbb Z}_2^n\) yang berbobot \(1\text{.}\) Untuk matriks biner \(m \times n\) \(H\text{,}\) \(H{\mathbf e}_i\) tepat merupakan kolom ke-\(i\) dari matriks \(H\text{.}\)

Contoh 8.3.7.

Perhatikan bahwa
\begin{equation*} \begin{pmatrix} 1 & 1 & 1 & 0 & 0 \\ 1 & 0 & 0 & 1 & 0 \\ 1 & 1 & 0 & 0 & 1 \end{pmatrix} \begin{pmatrix} 0 \\ 1 \\ 0 \\ 0 \\ 0 \end{pmatrix} = \begin{pmatrix} 1 \\ 0 \\ 1 \end{pmatrix}\text{.} \end{equation*}
Hasil ini kita nyatakan dalam proposisi berikut dan pembuktiannya kita serahkan sebagai latihan.

Bukti.
Misalkan \(\Null(H)\) merupakan kode pendeteksi kesalahan tunggal. Maka jarak minimum kode tersebut harus sekurang-kurangnya \(2\text{.}\) Karena ruang nol tersebut merupakan kode grup, cukup disyaratkan bahwa kode itu tidak memuat kata kode berbobot kurang dari \(2\text{,}\) selain kata kode nol. Artinya, \({\mathbf e}_i\) tidak boleh menjadi kata kode untuk \(i = 1, \ldots, n\text{.}\) Karena \(H{\mathbf e}_i\) merupakan kolom ke-\(i\) dari \(H\text{,}\) satu-satunya cara \({\mathbf e}_i\) dapat berada dalam ruang nol \(H\) adalah jika kolom ke-\(i\) seluruhnya nol, yang mustahil; jadi, kode tersebut setidaknya harus memiliki kemampuan untuk mendeteksi kesalahan tunggal.
Sebaliknya, misalkan tidak ada kolom \(H\) yang merupakan kolom nol. Berdasarkan Proposisi 8.3.8, \(H{\mathbf e}_i \neq {\mathbf 0}\text{.}\)

Contoh 8.3.10.

Jika kita meninjau matriks-matriks
\begin{equation*} H_1 = \begin{pmatrix} 1 & 1 & 1 & 0 & 0 \\ 1 & 0 & 0 & 1 & 0 \\ 1 & 1 & 0 & 0 & 1 \end{pmatrix} \end{equation*}
dan
\begin{equation*} H_2 = \begin{pmatrix} 1 & 1 & 1 & 0 & 0 \\ 1 & 0 & 0 & 0 & 0 \\ 1 & 1 & 0 & 0 & 1 \end{pmatrix}\text{,} \end{equation*}
maka ruang nol \(H_1\) merupakan kode pendeteksi kesalahan tunggal, sedangkan ruang nol \(H_2\) bukan.
Kita bahkan dapat memperoleh hasil yang lebih kuat daripada Teorema 8.3.9. Teorema ini memberikan syarat-syarat pada suatu matriks \(H\) yang menunjukkan kapan bobot minimum kode yang dibentuk oleh ruang nol \(H\) adalah \(2\text{.}\) Kita juga dapat menentukan kapan jarak minimum suatu kode linear adalah \(3\) dengan memeriksa matriks yang bersesuaian.

Contoh 8.3.11.

Jika kita menetapkan
\begin{equation*} H = \begin{pmatrix} 1 & 1 & 1 & 0 \\ 1 & 0 & 0 & 1 \\ 1 & 1 & 0 & 0 \end{pmatrix} \end{equation*}
dan ingin menentukan apakah \(H\) merupakan matriks pemeriksa paritas kanonik bagi suatu kode pengoreksi kesalahan, kita perlu memastikan bahwa \(\Null(H)\) tidak memuat tupel-\(4\) berbobot \(2\text{.}\) Artinya, \((\codeword{1100})\text{,}\) \((\codeword{1010})\text{,}\) \((\codeword{1001})\text{,}\) \((\codeword{0110})\text{,}\) \((\codeword{0101})\text{,}\) dan \((\codeword{0011})\) tidak boleh berada dalam \(\Null(H)\text{.}\) Teorema berikut menyatakan bahwa kita memang dapat menentukan bahwa kode yang dibangkitkan oleh \(H\) mengoreksi kesalahan dengan memeriksa kolom-kolom \(H\text{.}\) Perhatikan dalam contoh ini bahwa \(H\) bukan hanya tidak memiliki kolom nol, melainkan juga tidak memiliki dua kolom yang sama.

Bukti.
Tupel-\(n\) \({\mathbf e}_{i} +{\mathbf e}_{j}\) memiliki \(1\) pada entri ke-\(i\) dan ke-\(j\text{,}\) serta \(0\) di tempat lainnya, dan \(w( {\mathbf e}_{i} +{\mathbf e}_{j}) = 2\) untuk \(i \neq j\text{.}\) Karena
\begin{equation*} {\mathbf 0} = H({\mathbf e}_{i} +{\mathbf e}_{j}) = H{\mathbf e}_{i} + H{\mathbf e}_{j} \end{equation*}
hanya dapat terjadi jika kolom ke-\(i\) dan ke-\(j\) identik, ruang nol \(H\) merupakan kode pengoreksi kesalahan tunggal.
Sekarang, misalkan kita memiliki matriks pemeriksa paritas kanonik \(H\) dengan tiga baris. Kita dapat menanyakan berapa banyak kolom lagi yang dapat ditambahkan ke matriks tersebut sambil tetap memperoleh ruang nol yang merupakan kode pendeteksi dan pengoreksi kesalahan tunggal. Karena setiap kolom memiliki tiga entri, terdapat \(2^3 = 8\) kemungkinan kolom yang berbeda. Kita tidak dapat menambahkan kolom-kolom
\begin{equation*} \begin{pmatrix} 0 \\ 0 \\ 0 \end{pmatrix}, \begin{pmatrix} 1 \\ 0 \\ 0 \end{pmatrix}, \begin{pmatrix} 0 \\ 1 \\ 0 \end{pmatrix}, \begin{pmatrix} 0 \\ 0 \\ 1 \end{pmatrix}\text{.} \end{equation*}
Jadi, kita dapat menambahkan hingga empat kolom dan tetap mempertahankan jarak minimum \(3\text{.}\)
Secara umum, jika \(H\) adalah matriks pemeriksa paritas kanonik \(m \times n\text{,}\) maka terdapat \(n-m\) posisi informasi dalam setiap kata kode. Setiap kolom memiliki \(m\) bit, sehingga terdapat \(2^m\) kemungkinan kolom yang berbeda. Kolom-kolom \({\mathbf 0}, {\mathbf e}_1, \ldots, {\mathbf e}_m\) harus dikecualikan, sehingga tersisa \(2^m - (1 + m)\) kolom bagi informasi jika kita ingin tetap mempertahankan kemampuan bukan hanya untuk mendeteksi, melainkan juga untuk mengoreksi kesalahan tunggal.
Sblm.Paling AtasLanjut