Dengan pengetahuan tentang gelanggang polinomial dan lapangan hingga, kini kita dapat memperoleh kode yang lebih canggih daripada kode dalam
Bab 8. Pertama-tama, ingat bahwa kode blok-
\((n, k)\) terdiri atas fungsi pengodean satu-ke-satu
\(E:{\mathbb Z}^{k}_{2} \rightarrow {\mathbb Z}^{n}_{2}\) dan fungsi pendekodean
\(D:{\mathbb Z}^{n}_{2} \rightarrow {\mathbb Z}^{k}_{2}\text{.}\) Kode tersebut bersifat mengoreksi galat jika
\(D\) surjektif. Suatu kode merupakan kode linear jika kode tersebut adalah ruang nol dari matriks
\(H \in {\mathbb M}_{k \times n}({\mathbb Z}_2)\text{.}\)
Kita tertarik pada suatu kelas kode yang dikenal sebagai
kode siklik. Misalkan
\(\phi : {\mathbb Z}_2^k \rightarrow {\mathbb Z}_2^n\) suatu kode blok-
\((n,k)\) biner. Maka
\(\phi\) merupakan
kode siklik jika untuk setiap kata kode
\((a_1, a_2, \ldots, a_n )\text{,}\) tupel-
\(n\) yang digeser secara siklik, yaitu
\((a_n, a_1, a_2, \ldots,
a_{n - 1} )\text{,}\) juga merupakan kata kode. Kode siklik sangat mudah diimplementasikan pada komputer dengan menggunakan register geser [2, 3].
Contoh 22.2.1.
Tinjau kode linear-\((6,3)\) yang dibangkitkan oleh dua matriks
\begin{equation*}
G_1
=
\begin{pmatrix}
1 & 0 & 0 \\
0 & 1 & 0 \\
0 & 0 & 1 \\
1 & 0 & 0 \\
0 & 1 & 0 \\
0 & 0 & 1
\end{pmatrix}
\quad
\text{dan}
\quad
G_2 =
\begin{pmatrix}
1 & 0 & 0 \\
1 & 1 & 0 \\
1 & 1 & 1 \\
1 & 1 & 1 \\
0 & 1 & 1 \\
0 & 0 & 1
\end{pmatrix}\text{.}
\end{equation*}
Pesan dalam kode pertama dikodekan sebagai berikut:
\begin{equation*}
\begin{array}{rclccrcl}
(\codeword{000}) & \mapsto & (\codeword{000000}) & & & (\codeword{100}) & \mapsto & (\codeword{100100}) \\
(\codeword{001}) & \mapsto & (\codeword{001001}) & & & (\codeword{101}) & \mapsto & (\codeword{101101}) \\
(\codeword{010}) & \mapsto & (\codeword{010010}) & & & (\codeword{110}) & \mapsto & (\codeword{110110}) \\
(\codeword{011}) & \mapsto & (\codeword{011011}) & & & (\codeword{111}) & \mapsto & (\codeword{111111}).
\end{array}
\end{equation*}
Mudah dilihat bahwa kata-kata kode tersebut membentuk kode siklik. Dalam kode kedua, tupel-3 dikodekan dengan cara berikut:
\begin{equation*}
\begin{array}{rclccrcl}
(\codeword{000}) & \mapsto & (\codeword{000000}) & & & (\codeword{100}) & \mapsto & (\codeword{111100}) \\
(\codeword{001}) & \mapsto & (\codeword{001111}) & & & (\codeword{101}) & \mapsto & (\codeword{110011}) \\
(\codeword{010}) & \mapsto & (\codeword{011110}) & & & (\codeword{110}) & \mapsto & (\codeword{100010}) \\
(\codeword{011}) & \mapsto & (\codeword{010001}) & & & (\codeword{111}) & \mapsto & (\codeword{101101}).
\end{array}
\end{equation*}
Kode ini tidak mungkin siklik, karena \((\codeword{101101})\) merupakan kata kode, tetapi \((\codeword{011011})\) bukan kata kode.
Subbagian 22.2.1 Kode Polinomial
Kita ingin menemukan metode yang mudah untuk memperoleh kode linear siklik. Untuk melakukannya, kita dapat menggunakan pengetahuan tentang lapangan hingga dan gelanggang polinomial di atas \({\mathbb Z}_2\text{.}\) Sebarang tupel-\(n\) biner dapat ditafsirkan sebagai polinomial dalam \({\mathbb Z}_2[x]\text{.}\) Dengan kata lain, tupel-\(n\) \((a_0, a_1, \ldots,
a_{n - 1} )\) bersesuaian dengan polinomial
\begin{equation*}
f(x) = a_0 + a_1 x + \cdots + a_{n-1} x^{n - 1}\text{,}
\end{equation*}
dengan derajat \(f(x)\) paling tinggi \(n - 1\text{.}\) Sebagai contoh, polinomial yang bersesuaian dengan tupel-\(5\) \((\codeword{10011})\) adalah
\begin{equation*}
1 + 0 x + 0 x^2 + 1 x^3 + 1 x^4 = 1 + x^3 + x^4\text{.}
\end{equation*}
Sebaliknya, dengan sebarang polinomial \(f(x) \in {\mathbb Z}_2[x]\) yang memenuhi \(\deg f(x) \lt n\text{,}\) kita dapat mengaitkan suatu tupel-\(n\) biner. Polinomial \(x + x^2 + x^4\) bersesuaian dengan tupel-\(5\) \((\codeword{01101})\text{.}\)
Tetapkan suatu polinomial tak konstan
\(g(x)\) dalam
\({\mathbb Z}_2[x]\) yang berderajat
\(n - k\text{.}\) Kita dapat mendefinisikan kode-
\((n,k)\) \(C\) dengan cara berikut. Jika
\((a_0, \ldots, a_{k - 1})\) merupakan tupel-
\(k\) yang akan dikodekan, maka
\(f(x) = a_0 + a_1 x + \cdots + a_{k - 1} x^{k - 1}\) merupakan polinomial yang bersesuaian dalam
\({\mathbb Z}_2[x]\text{.}\) Untuk mengodekan
\(f(x)\text{,}\) kita mengalikannya dengan
\(g(x)\text{.}\) Kata-kata kode dalam
\(C\) adalah semua polinomial dalam
\({\mathbb Z}_2[x]\) yang berderajat kurang dari
\(n\) dan dapat dibagi oleh
\(g(x)\text{.}\) Kode yang diperoleh dengan cara ini disebut
kode polinomial.
Contoh 22.2.2.
Jika kita mengambil
\(g(x)= 1 + x^3\text{,}\) kita dapat mendefinisikan kode-
\((6,3)\) \(C\) sebagai berikut. Untuk mengodekan tupel-
\(3\) \(( a_0, a_1, a_2 )\text{,}\) kita mengalikan polinomial yang bersesuaian,
\(f(x) = a_0 + a_1 x + a_2 x^2\text{,}\) dengan
\(1 + x^3\text{.}\) Kita mendefinisikan pemetaan
\(\phi : {\mathbb Z}_2^3 \rightarrow {\mathbb Z}_2^6\) dengan
\(\phi : f(x) \mapsto g(x) f(x)\text{.}\) Mudah diperiksa bahwa pemetaan ini merupakan homomorfisma grup. Bahkan, jika kita memandang
\({\mathbb Z}_2^n\) sebagai ruang vektor atas
\({\mathbb Z}_2\text{,}\) \(\phi\) merupakan transformasi linear ruang vektor (lihat
Latihan 20.5.15). Mari kita hitung kernel
\(\phi\text{.}\) Perhatikan bahwa
\(\phi ( a_0, a_1, a_2 ) = (\codeword{000000})\) tepat ketika
\begin{align*}
0 + 0x + 0x^2 + 0x^3 + 0x^4 + 0 x^5 & = (1 + x^3) ( a_0 + a_1 x + a_2 x^2 )\\
& = a_0 + a_1 x + a_2 x^2 + a_0 x^3 + a_1 x^4 + a_2 x^5\text{.}
\end{align*}
Karena polinomial di atas suatu lapangan membentuk daerah integral, \(a_0 + a_1 x + a_2 x^2\) harus merupakan polinomial nol. Oleh karena itu, \(\ker \phi = \{ (\codeword{000}) \}\) dan \(\phi\) satu-ke-satu.
Untuk menghitung matriks pembangkit bagi \(C\text{,}\) kita hanya perlu mengkaji cara polinomial \(1\text{,}\) \(x\text{,}\) dan \(x^2\) dikodekan:
\begin{align*}
(1 + x^3) \cdot 1 & = 1 + x^3\\
(1 + x^3)x & = x + x^4\\
(1 + x^3)x^2 & = x^2 + x^5\text{.}
\end{align*}
Kita memperoleh kode yang bersesuaian dengan matriks pembangkit
\(G_1\) dalam
Contoh 22.2.1. Matriks pemeriksa paritas untuk kode ini adalah
\begin{equation*}
H
=
\begin{pmatrix}
1 & 0 & 0 & 1 & 0 & 0 \\
0 & 1 & 0 & 0 & 1 & 0 \\
0 & 0 & 1 & 0 & 0 & 1
\end{pmatrix}\text{.}
\end{equation*}
Karena bobot terkecil sebarang kata kode tak nol adalah \(2\text{,}\) kode ini mampu mendeteksi semua galat tunggal.
Gelanggang polinomial memiliki banyak struktur; oleh karena itu, tujuan langsung kita adalah membangun hubungan antara kode polinomial dan teori gelanggang. Ingat bahwa \(x^n - 1 = (x - 1)( x^{n - 1} + \cdots + x + 1)\text{.}\) Gelanggang hasil bagi
\begin{equation*}
R_n = {\mathbb Z}_2[x]/ \langle x^n - 1 \rangle
\end{equation*}
dapat dipandang sebagai gelanggang polinomial berbentuk
\begin{equation*}
f(t) = a_0 + a_1 t + \cdots + a_{n - 1} t^{n - 1}
\end{equation*}
yang memenuhi syarat \(t^n = 1\text{.}\) Sebagai latihan mudah, tunjukkan bahwa \({\mathbb Z}_2^n\) dan \(R_n\) isomorfik sebagai ruang vektor. Kita akan sering mengidentifikasi elemen-elemen dalam \({\mathbb Z}_2^n\) dengan elemen-elemen dalam \({\mathbb Z}[x] / \langle x^n - 1 \rangle\text{.}\) Dengan cara ini, kita dapat menafsirkan kode linear sebagai himpunan bagian dari \({\mathbb Z}[x] / \langle x^n - 1 \rangle\text{.}\)
Struktur gelanggang tambahan pada kode polinomial sangat ampuh untuk mendeskripsikan kode siklik. Pergeseran siklik suatu tupel-\(n\) dapat dideskripsikan melalui perkalian polinomial. Jika \(f(t) = a_0 + a_1 t + \cdots + a_{n - 1} t^{n - 1}\) merupakan polinomial kode dalam \(R_n\text{,}\) maka
\begin{equation*}
tf(t) = a_{n - 1} + a_0 t + \cdots + a_{n - 2} t^{n - 1}
\end{equation*}
merupakan kata yang digeser secara siklik, yang diperoleh dengan mengalikan \(f(t)\) dengan \(t\text{.}\) Teorema berikut memberikan klasifikasi indah bagi kode siklik dalam istilah ideal-ideal dari \(R_n\text{.}\)
Teorema 22.2.3.
Kode linear
\(C\) dalam
\({\mathbb Z}_2^n\) bersifat siklik jika dan hanya jika kode tersebut merupakan ideal dalam
\(R_n = {\mathbb Z}[x] / \langle x^n - 1 \rangle\text{.}\)
Bukti.
Misalkan
\(C\) suatu kode linear siklik dan andaikan bahwa
\(f(t)\) berada dalam
\(C\text{.}\) Maka
\(t f(t)\) juga harus berada dalam
\(C\text{.}\) Akibatnya,
\(t^k f(t)\) berada dalam
\(C\) untuk semua
\(k \in {\mathbb N}\text{.}\) Karena
\(C\) merupakan kode linear, setiap kombinasi linear kata-kata kode
\(f(t), tf(t),
t^2f(t), \ldots, t^{n-1}f(t)\) juga merupakan kata kode; oleh karena itu, untuk setiap polinomial
\(p(t)\text{,}\) \(p(t)f(t)\) berada dalam
\(C\text{.}\) Jadi,
\(C\) merupakan ideal.
Sebaliknya, misalkan
\(C\) suatu ideal dalam
\({\mathbb Z}_2[x]/\langle x^n + 1\rangle\text{.}\) Andaikan bahwa
\(f(t) = a_0 + a_1 t + \cdots + a_{n - 1} t^{n - 1}\) merupakan kata kode dalam
\(C\text{.}\) Maka
\(t f(t)\) merupakan kata kode dalam
\(C\text{;}\) artinya,
\((a_1, \ldots, a_{n-1}, a_0)\) berada dalam
\(C\text{.}\)
Teorema 22.2.3 memberi tahu kita bahwa mengetahui ideal-ideal dari
\(R_n\) ekuivalen dengan mengetahui kode linear siklik dalam
\({\mathbb Z}_2^n\text{.}\) Untungnya, ideal-ideal dalam
\(R_n\) mudah dideskripsikan. Homomorfisma gelanggang alami
\(\phi : {\mathbb Z}_2[x] \rightarrow R_n\) yang didefinisikan oleh
\(\phi[f(x)] = f(t)\) merupakan homomorfisma surjektif. Kernel
\(\phi\) adalah ideal yang dibangkitkan oleh
\(x^n - 1\text{.}\) Menurut
Teorema 16.3.15, setiap ideal
\(C\) dalam
\(R_n\) berbentuk
\(\phi(I)\text{,}\) dengan
\(I\) suatu ideal dalam
\({\mathbb Z}_2[x]\) yang memuat
\(\langle x^n - 1 \rangle\text{.}\) Menurut
Teorema 17.3.10, kita mengetahui bahwa setiap ideal
\(I\) dalam
\({\mathbb Z}_2[x]\) merupakan ideal utama, karena
\({\mathbb Z}_2\) merupakan lapangan. Oleh karena itu,
\(I = \langle g(x) \rangle\) untuk suatu polinomial monik tunggal dalam
\({\mathbb Z}_2[x]\text{.}\) Karena
\(\langle x^n - 1 \rangle\) termuat dalam
\(I\text{,}\) harus berlaku bahwa
\(g(x)\) membagi
\(x^n - 1\text{.}\) Akibatnya, setiap ideal
\(C\) dalam
\(R_n\) berbentuk
\begin{equation*}
C = \langle g(t) \rangle = \{ f(t)g(t) : f(t) \in R_n \text{ dan } g(x) \mid (x^n - 1) \text{ dalam } {\mathbb Z}_2[x] \}\text{.}
\end{equation*}
Polinomial monik tunggal berderajat terkecil yang membangkitkan \(C\) disebut polinomial pembangkit minimal dari \(C\text{.}\)
Contoh 22.2.4.
Jika kita memfaktorkan \(x^7 - 1\) menjadi komponen-komponen tak tereduksi, kita memperoleh
\begin{equation*}
x^7 - 1 = (1 + x)(1 + x + x^3)(1+ x^2 + x^3)\text{.}
\end{equation*}
Kita melihat bahwa
\(g(t) = (1 + t + t^3)\) membangkitkan ideal
\(C\) dalam
\(R_7\text{.}\) Kode ini merupakan kode blok-
\((7, 4)\text{.}\) Seperti dalam
Contoh 22.2.2, matriks pembangkit mudah dihitung dengan mengkaji tindakan
\(g(t)\) pada polinomial
\(1\text{,}\) \(t\text{,}\) \(t^2\text{,}\) dan
\(t^3\text{.}\) Matriks pembangkit bagi
\(C\) adalah
\begin{equation*}
G =
\begin{pmatrix}
1 & 0 & 0 & 0 \\
1 & 1 & 0 & 0 \\
0 & 1 & 1 & 0 \\
1 & 0 & 1 & 1 \\
0 & 1 & 0 & 1 \\
0 & 0 & 1 & 0 \\
0 & 0 & 0 & 1
\end{pmatrix}\text{.}
\end{equation*}
Secara umum, kita dapat menentukan matriks pembangkit bagi kode-\((n, k)\) \(C\) melalui cara elemen-elemen \(t^k\) dikodekan. Misalkan \(x^n - 1 = g(x) h(x)\) dalam \({\mathbb Z}_2[x]\text{.}\) Jika \(g(x) = g_0 + g_1 x + \cdots + g_{n-k} x^{n-k}\) dan \(h(x) = h_0 + h_1 x + \cdots + h_k x^k\text{,}\) maka matriks \(n \times k\)
\begin{equation*}
G =
\begin{pmatrix}
g_0 & 0 & \cdots & 0 \\
g_1 & g_0 & \cdots & 0 \\
\vdots & \vdots &\ddots & \vdots \\
g_{n-k} & g_{n-k-1} & \cdots & g_0 \\
0 & g_{n-k} & \cdots & g_{1} \\
\vdots & \vdots & \ddots & \vdots \\
0 & 0 & \cdots & g_{n-k}
\end{pmatrix}
\end{equation*}
merupakan matriks pembangkit bagi kode \(C\) dengan polinomial pembangkit \(g(t)\text{.}\) Matriks pemeriksa paritas bagi \(C\) adalah matriks \((n - k) \times n\)
\begin{equation*}
H =
\begin{pmatrix}
0 & \cdots & 0 & 0 & h_k & \cdots & h_0 \\
0 & \cdots & 0 & h_k & \cdots & h_0 & 0 \\
\cdots & \cdots & \cdots & \cdots & \cdots & \cdots & \cdots \\
h_k & \cdots & h_0 & 0 & 0 & \cdots & 0
\end{pmatrix}\text{.}
\end{equation*}
Perincian bukti proposisi berikut kita serahkan sebagai latihan.
Proposisi 22.2.5.
Misalkan
\(C = \langle g(t) \rangle\) suatu kode siklik dalam
\(R_n\) dan andaikan bahwa
\(x^n - 1 = g(x) h(x)\text{.}\) Maka
\(G\) dan
\(H\) masing-masing merupakan matriks pembangkit dan matriks pemeriksa paritas bagi
\(C\text{.}\) Lebih lanjut,
\(HG = 0\text{.}\)
Contoh 22.2.6.
\begin{equation*}
x^7 - 1 = g(x) h(x) = (1 + x + x^3)(1 + x + x^2 + x^4)\text{.}
\end{equation*}
Oleh karena itu, matriks pemeriksa paritas untuk kode ini adalah
\begin{equation*}
H =
\begin{pmatrix}
0 & 0 & 1 & 0 & 1 & 1 & 1 \\
0 & 1 & 0 & 1 & 1 & 1 & 0 \\
1 & 0 & 1 & 1 & 1 & 0 & 0
\end{pmatrix}\text{.}
\end{equation*}
Untuk menentukan kemampuan mendeteksi dan mengoreksi galat dari suatu kode siklik, kita perlu mengetahui sesuatu tentang determinan. Jika \(\alpha_1, \ldots, \alpha_n\) merupakan elemen-elemen dalam lapangan \(F\text{,}\) maka matriks \(n \times n\)
\begin{equation*}
\begin{pmatrix}
1 & 1 & \cdots & 1 \\
\alpha_1 & \alpha_2 & \cdots & \alpha_n \\
\alpha_1^2 & \alpha_2^2 & \cdots & \alpha_n^2 \\
\vdots & \vdots & \ddots & \vdots \\
\alpha_1^{n-1} & \alpha_2^{n-1} & \cdots & \alpha_n^{n-1}
\end{pmatrix}
\end{equation*}
disebut matriks Vandermonde. Determinan matriks ini disebut determinan Vandermonde. Kita akan memerlukan lema berikut dalam penyelidikan kode siklik.
Lema 22.2.7.
Misalkan \(\alpha_1, \ldots, \alpha_n\) elemen-elemen dalam lapangan \(F\) dengan \(n \geq 2\text{.}\) Maka
\begin{equation*}
\det
\begin{pmatrix}
1 & 1 & \cdots & 1 \\
\alpha_1 & \alpha_2 & \cdots & \alpha_n \\
\alpha_1^2 & \alpha_2^2 & \cdots & \alpha_n^2 \\
\vdots & \vdots & \ddots & \vdots \\
\alpha_1^{n-1} & \alpha_2^{n-1} & \cdots & \alpha_n^{n-1}
\end{pmatrix}
= \prod_{1 \leq j \lt i \leq n} (\alpha_i - \alpha_j)\text{.}
\end{equation*}
Khususnya, jika \(\alpha_i\) berbeda-beda, maka determinan tersebut tak nol.
Bukti.
Kita akan melakukan induksi pada \(n\text{.}\) Jika \(n = 2\text{,}\) maka determinannya adalah \(\alpha_2 - \alpha_1\text{.}\) Andaikan hasil tersebut berlaku untuk \(n - 1\) dan tinjau polinomial \(p(x)\) yang didefinisikan oleh
\begin{equation*}
p(x) = \det
\begin{pmatrix}
1 & 1 & \cdots & 1 & 1 \\
\alpha_1 & \alpha_2 & \cdots & \alpha_{n-1} & x \\
\alpha_1^2 & \alpha_2^2 & \cdots & \alpha_{n-1}^2 & x^2 \\
\vdots & \vdots & \ddots & \vdots & \vdots \\
\alpha_1^{n-1} & \alpha_2^{n-1} & \cdots & \alpha_{n-1}^{n-1} & x^{n-1}
\end{pmatrix}\text{.}
\end{equation*}
Dengan mengembangkan determinan ini menurut kofaktor pada kolom terakhir, kita melihat bahwa \(p(x)\) merupakan polinomial berderajat paling tinggi \(n-1\text{.}\) Selain itu, akar-akar \(p(x)\) adalah \(\alpha_1, \ldots, \alpha_{n-1}\text{,}\) karena menyubstitusikan salah satu elemen ini pada kolom terakhir akan menghasilkan kolom yang identik dengan kolom terakhir dalam matriks. Ingat bahwa determinan suatu matriks bernilai nol jika matriks tersebut mempunyai dua kolom yang identik. Oleh karena itu,
\begin{equation*}
p(x) = (x - \alpha_1)(x - \alpha_2) \cdots (x - \alpha_{n-1}) \beta\text{,}
\end{equation*}
dengan
\begin{equation*}
\beta = (-1)^{n + n} \det
\begin{pmatrix}
1 & 1 & \cdots & 1 \\
\alpha_1 & \alpha_2 & \cdots & \alpha_{n-1} \\
\alpha_1^2 & \alpha_2^2 & \cdots & \alpha_{n-1}^2 \\
\vdots & \vdots & \ddots & \vdots \\
\alpha_1^{n-2} & \alpha_2^{n-2} & \cdots & \alpha_{n-1}^{n-2}
\end{pmatrix}\text{.}
\end{equation*}
Berdasarkan hipotesis induksi kita,
\begin{equation*}
\beta = (-1)^{n+n} \prod_{1 \leq j \lt i \leq n - 1} (\alpha_i - \alpha_j)\text{.}
\end{equation*}
Jika kita mengambil \(x = \alpha_n\text{,}\) hasil tersebut langsung diperoleh.
Teorema berikut memberikan taksiran kemampuan mendeteksi dan mengoreksi galat bagi suatu polinomial pembangkit tertentu.
Teorema 22.2.8.
Misalkan
\(C = \langle g(t) \rangle\) suatu kode siklik dalam
\(R_n\) dan andaikan bahwa
\(\omega\) merupakan akar kesatuan ke-
\(n\) primitif di atas
\({\mathbb Z}_2\text{.}\) Jika
\(s\) pangkat berurutan dari
\(\omega\) merupakan akar-akar
\(g(x)\text{,}\) maka jarak minimum
\(C\) setidaknya
\(s + 1\text{.}\)
Bukti.
Andaikan bahwa
\begin{equation*}
g( \omega^r) = g(\omega^{r + 1}) = \cdots = g( \omega^{r + s - 1}) = 0\text{.}
\end{equation*}
Misalkan \(f(x)\) suatu polinomial dalam \(C\) dengan paling banyak \(s\) koefisien tak nol. Kita dapat mengandaikan bahwa
\begin{equation*}
f(x) = a_{i_0} x^{i_0} + a_{i_1} x^{i_1} + \cdots + a_{i_{s - 1}} x^{i_{s - 1}}
\end{equation*}
merupakan suatu polinomial dalam \(C\text{.}\) Cukup ditunjukkan bahwa semua \(a_i\) harus bernilai 0. Karena
\begin{equation*}
g( \omega^r) = g(\omega^{r + 1}) = \cdots = g( \omega^{r + s - 1}) = 0
\end{equation*}
dan \(g(x)\) membagi \(f(x)\text{,}\)
\begin{equation*}
f( \omega^r) = f(\omega^{r + 1}) = \cdots = f( \omega^{r + s - 1}) = 0\text{.}
\end{equation*}
Secara ekuivalen, kita mempunyai sistem persamaan berikut:
\begin{align*}
a_{i_0} (\omega^r)^{i_0} + a_{i_1} (\omega^r)^{i_1} + \cdots + a_{i_{s - 1}} (\omega^r)^{i_{s - 1}} & = 0\\
a_{i_0} (\omega^{r + 1})^{i_0} + a_{i_1} (\omega^{r + 1})^{i_2} + \cdots + a_{i_{s-1}} (\omega^{r+1})^{i_{s-1}} & = 0\\
& \aatavdots{=}\\
a_{i_0} (\omega^{r + s - 1})^{i_0} + a_{i_1} (\omega^{r + s - 1})^{i_1} + \cdots + a_{i_{s - 1}} (\omega^{r + s - 1})^{i_{s - 1}} & = 0\text{.}
\end{align*}
Oleh karena itu, \((a_{i_0}, a_{i_1}, \ldots,
a_{i_{s - 1}})\) merupakan solusi sistem homogen persamaan linear
\begin{align*}
(\omega^{i_0})^r x_0 + (\omega^{i_1})^r x_1 + \cdots + (\omega^{i_{s - 1}})^r x_{n - 1} & = 0\\
(\omega^{i_0})^{r + 1} x_0 + (\omega^{i_1})^{r + 1} x_1 + \cdots + (\omega^{i_{s - 1}})^{r + 1} x_{n - 1} & = 0\\
& \aatavdots{=}\\
(\omega^{i_0})^{r + s - 1} x_0 + (\omega^{i_1})^{r + s - 1} x_1 + \cdots + (\omega^{i_{s - 1}})^{r + s - 1} x_{n - 1} & = 0\text{.}
\end{align*}
Akan tetapi, sistem ini mempunyai solusi tunggal, karena determinan matriks
\begin{equation*}
\begin{pmatrix}
(\omega^{i_0})^r & (\omega^{i_1})^r & \cdots & (\omega^{i_{s-1}})^r \\
(\omega^{i_0})^{r+1} & (\omega^{i_1})^{r+1} & \cdots &
(\omega^{i_{s-1}})^{r+1} \\
\vdots & \vdots & \ddots & \vdots \\
(\omega^{i_0})^{r+s-1} & (\omega^{i_1})^{r+s-1} & \cdots &
(\omega^{i_{s-1}})^{r+s-1}
\end{pmatrix}
\end{equation*}
dapat ditunjukkan tak nol dengan menggunakan
Lema 22.2.7 dan sifat-sifat dasar determinan (Latihan). Oleh karena itu, solusi ini haruslah
\(a_{i_0} = a_{i_1} = \cdots = a_{i_{s - 1}} = 0\text{.}\)
Subbagian 22.2.2 Kode BCH
Beberapa kode terpenting, yang ditemukan secara terpisah oleh A. Hocquenghem pada tahun 1959 serta oleh R. C. Bose dan D. V. Ray-Chaudhuri pada tahun 1960, adalah kode
BCH. Sistem komunikasi Eropa dan transatlantik sama-sama menggunakan kode
BCH. Kata informasi yang akan dikodekan memiliki panjang
\(231\text{,}\) dan polinomial berderajat
\(24\) digunakan untuk membangkitkan kode. Karena
\(231 + 24 = 255 = 2^8-1\text{,}\) kita berhadapan dengan kode blok-
\((255, 231)\text{.}\) Kode
BCH ini akan mendeteksi enam galat dan mempunyai tingkat kegagalan
\(1\) dalam
\(16\) juta. Salah satu keunggulan kode
BCH adalah tersedianya algoritma koreksi galat yang efisien.
Gagasan di balik kode
BCH adalah memilih polinomial pembangkit berderajat terkecil yang mempunyai kemampuan terbesar dalam mendeteksi dan mengoreksi galat. Misalkan
\(d = 2r + 1\) untuk suatu
\(r \geq 0\text{.}\) Andaikan bahwa
\(\omega\) merupakan akar kesatuan ke-
\(n\) primitif di atas
\({\mathbb Z}_2\text{,}\) dan misalkan
\(m_i(x)\) polinomial minimal di atas
\({\mathbb Z}_2\) dari
\(\omega^i\text{.}\) Jika
\begin{equation*}
g(x) = \lcm[ m_1(x), m_{2}(x), \ldots, m_{2r}(x)]\text{,}
\end{equation*}
maka kode siklik
\(\langle g(t) \rangle\) dalam
\(R_n\) disebut
kode BCH dengan panjang \(n\) dan jarak \(d\text{.}\) Menurut
Teorema 22.2.8, jarak minimum
\(C\) setidaknya
\(d\text{.}\)
Teorema 22.2.9.
Misalkan \(C = \langle g(t) \rangle\) suatu kode siklik dalam \(R_n\text{.}\) Pernyataan-pernyataan berikut ekuivalen.
-
Kode
\(C\) merupakan kode
BCH yang jarak minimumnya setidaknya
\(d\text{.}\)
-
Polinomial kode
\(f(t)\) berada dalam
\(C\) jika dan hanya jika
\(f( \omega^i) = 0\) untuk
\(1 \leq i \lt d\text{.}\)
-
Matriks
\begin{equation*}
H =
\begin{pmatrix}
1 & \omega & \omega^2 & \cdots & \omega^{n-1}\\
1 & \omega^2 & \omega^{4} & \cdots & \omega^{(n-1)(2)} \\
1 & \omega^3 & \omega^{6} & \cdots & \omega^{(n-1)(3)} \\
\vdots & \vdots & \vdots & \ddots & \vdots \\
1 & \omega^{2r} & \omega^{4r} & \cdots & \omega^{(n-1)(2r)}
\end{pmatrix}
\end{equation*}
merupakan matriks pemeriksa paritas bagi \(C\text{.}\)
Bukti.
(1)
\(\Rightarrow\) (2). Jika
\(f(t)\) berada dalam
\(C\text{,}\) maka
\(g(x) \mid f(x)\) dalam
\({\mathbb Z}_2[x]\text{.}\) Jadi, untuk
\(i = 1, \ldots, 2r\text{,}\) berlaku
\(f( \omega^i) = 0\) karena
\(g( \omega^i ) = 0\text{.}\) Sebaliknya, andaikan bahwa
\(f( \omega^i) = 0\) untuk
\(1 \leq i \leq d\text{.}\) Maka
\(f(x)\) dapat dibagi oleh setiap
\(m_i(x)\text{,}\) karena
\(m_i(x)\) merupakan polinomial minimal dari
\(\omega^i\text{.}\) Oleh karena itu,
\(g(x) \mid f(x)\) berdasarkan definisi
\(g(x)\text{.}\) Akibatnya,
\(f(x)\) merupakan kata kode.
(2) \(\Rightarrow\) (3). Misalkan \(f(t) = a_0 + a_1 t + \cdots + a_{n - 1}v t^{n - 1}\) berada dalam \(R_n\text{.}\) Tupel-\(n\) yang bersesuaian dalam \({\mathbb Z}_2^n\) adalah \({\mathbf x} = (a_0 a_1 \cdots a_{n - 1})^\transpose\text{.}\) Menurut (2),
\begin{equation*}
H {\mathbf x} =
\begin{pmatrix}
a_0 + a_1 \omega + \cdots + a_{n-1} \omega^{n-1} \\
a_0 + a_1 \omega^2 + \cdots + a_{n-1} (\omega^2)^{n-1} \\
\vdots \\
a_0 + a_1 \omega^{2r} + \cdots + a_{n-1} (\omega^{2r})^{n-1}
\end{pmatrix}
=
\begin{pmatrix}
f(\omega) \\
f(\omega^2) \\
\vdots \\
f(\omega^{2r})
\end{pmatrix}
= 0
\end{equation*}
tepat ketika \(f(t)\) berada dalam \(C\text{.}\) Dengan demikian, \(H\) merupakan matriks pemeriksa paritas bagi \(C\text{.}\)
(3)
\(\Rightarrow\) (1). Menurut (3), polinomial kode
\(f(t) = a_0 + a_1 t + \cdots + a_{n - 1} t^{n - 1}\) berada dalam
\(C\) tepat ketika
\(f(\omega^i) = 0\) untuk
\(i = 1, \ldots, 2r\text{.}\) Polinomial terkecil semacam itu adalah
\(g(t) = \lcm[ m_1(t),\ldots,
m_{2r}(t)]\text{.}\) Oleh karena itu,
\(C = \langle g(t) \rangle\text{.}\)
Contoh 22.2.10.
Mudah diverifikasi bahwa \(x^{15} - 1 \in {\mathbb Z}_2[x]\) mempunyai faktorisasi
\begin{equation*}
x^{15} - 1 = (x + 1)(x^2 + x + 1)(x^4 + x + 1)(x^4 + x^3 + 1)(x^4 + x^3 + x^2 + x + 1)\text{,}
\end{equation*}
dengan setiap faktornya berupa polinomial tak tereduksi. Misalkan \(\omega\) suatu akar dari \(1 + x + x^4\text{.}\) Lapangan Galois \(\gf(2^4)\) adalah
\begin{equation*}
\{ a_0 + a_1 \omega + a_2 \omega^2 + a_3 \omega^3 : a_i \in {\mathbb Z}_2 \text{ dan } 1 + \omega + \omega^4 = 0 \}\text{.}
\end{equation*}
Menurut
Contoh 22.1.8,
\(\omega\) merupakan akar kesatuan ke-
\(15\) primitif. Polinomial minimal dari
\(\omega\) adalah
\(m_1(x) = 1 + x + x^4\text{.}\) Mudah dilihat bahwa
\(\omega^2\) dan
\(\omega^4\) juga merupakan akar dari
\(m_1(x)\text{.}\) Polinomial minimal dari
\(\omega^3\) adalah
\(m_2(x) = 1 + x + x^2 + x^3 + x^4\text{.}\) Oleh karena itu,
\begin{equation*}
g(x) = m_1(x) m_2(x) = 1 + x^4 + x^6 + x^7 + x^8
\end{equation*}
mempunyai akar-akar
\(\omega\text{,}\) \(\omega^2\text{,}\) \(\omega^3\text{,}\) \(\omega^4\text{.}\) Karena
\(m_1(x)\) dan
\(m_2(x)\) keduanya membagi
\(x^{15} - 1\text{,}\) kode
BCH tersebut merupakan kode-
\((15, 7)\text{.}\) Jika
\(x^{15} -1 = g(x)h(x)\text{,}\) maka
\(h(x) = 1 + x^4 + x^6 + x^7\text{;}\) oleh karena itu, matriks pemeriksa paritas untuk kode ini adalah
\begin{equation*}
\left(
\begin{array}{ccccccccccccccc}
0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 1 & 0 & 1 & 0 & 0 & 0 & 1 \\
0 & 0 & 0 & 0 & 0 & 0 & 1 & 1 & 0 & 1 & 0 & 0 & 0 & 1 & 0 \\
0 & 0 & 0 & 0 & 0 & 1 & 1 & 0 & 1 & 0 & 0 & 0 & 1 & 0 & 0 \\
0 & 0 & 0 & 0 & 1 & 1 & 0 & 1 & 0 & 0 & 0 & 1 & 0 & 0 & 0 \\
0 & 0 & 0 & 1 & 1 & 0 & 1 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 \\
0 & 0 & 1 & 1 & 0 & 1 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 \\
0 & 1 & 1 & 0 & 1 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 \\
1 & 1 & 0 & 1 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0
\end{array}
\right)\text{.}
\end{equation*}
