Sekarang kita telah sampai pada tahap ketika kita dapat membangkitkan kode linear yang mendeteksi dan mengoreksi kesalahan dengan cukup mudah, tetapi mendekode tupel-\(n\) yang diterima dan menentukan kata kode terdekat masih merupakan proses yang memakan waktu, sebab tupel-\(n\) yang diterima harus dibandingkan dengan setiap kata kode yang mungkin untuk menentukan pendekodean yang tepat. Hal ini dapat menjadi kendala serius jika kodenya sangat besar.
Jadi, \({\mathbf x}\) merupakan kata kode, sedangkan \({\mathbf y}\) bukan, sebab \({\mathbf x}\) berada dalam ruang nol, sedangkan \({\mathbf y}\) tidak. Perhatikan bahwa \(H{\mathbf y}\) identik dengan kolom pertama \(H\text{.}\) Sesungguhnya, pada posisi inilah kesalahan terjadi. Jika kita membalik bit pertama dalam \({\mathbf y}\) dari \(0\) menjadi \(1\text{,}\) kita memperoleh \({\mathbf x}\text{.}\)
Jika \(H\) merupakan matriks \(m \times n\) dan \({\mathbf x} \in {\mathbb Z}_2^n\text{,}\) maka kita mengatakan bahwa sindrom dari \({\mathbf x}\) adalah \(H{\mathbf x}\text{.}\) Proposisi berikut memungkinkan pendeteksian dan pengoreksian kesalahan secara cepat.
Misalkan matriks biner \(m \times n\)\(H\) menentukan suatu kode linear dan misalkan \({\mathbf x}\) adalah tupel-\(n\) yang diterima. Tuliskan \({\mathbf x}\) sebagai \({\mathbf x} = {\mathbf c} +{\mathbf e}\text{,}\) dengan \({\mathbf c}\) sebagai kata kode yang ditransmisikan dan \({\mathbf e}\) sebagai kesalahan transmisi. Maka sindrom \(H{\mathbf x}\) dari kata kode yang diterima \({\mathbf x}\) juga merupakan sindrom dari kesalahan \({\mathbf e}\text{.}\)
Proposisi ini menunjukkan bahwa sindrom suatu kata yang diterima hanya bergantung pada kesalahannya, bukan pada kata kode yang ditransmisikan. Pembuktian teorema berikut langsung diperoleh dari Proposisi 8.4.2 dan dari fakta bahwa \(H{\mathbf e}\) merupakan kolom ke-\(i\) dari matriks \(H\text{.}\)
Misalkan \(H \in {\mathbb M}_{ m \times n} ( {\mathbb Z}_2)\) dan misalkan kode linear yang bersesuaian dengan \(H\) mengoreksi kesalahan tunggal. Misalkan \({\mathbf r}\) adalah tupel-\(n\) yang diterima setelah ditransmisikan dengan paling banyak satu kesalahan. Jika sindrom \({\mathbf r}\) adalah \({\mathbf 0}\text{,}\) maka tidak terjadi kesalahan; jika tidak, apabila sindrom \({\mathbf r}\) sama dengan suatu kolom \(H\text{,}\) misalnya kolom ke-\(i\text{,}\) maka kesalahan terjadi pada bit ke-\(i\text{.}\)
dan misalkan tupel-\(6\)\({\mathbf x} = (\codeword{111110})^\transpose\text{,}\)\({\mathbf y} = (\codeword{111111})^\transpose\text{,}\) dan \({\mathbf z} = (\codeword{010111})^\transpose\) telah diterima. Maka
Jadi, \({\mathbf x}\) memiliki kesalahan pada bit ketiga dan \({\mathbf z}\) memiliki kesalahan pada bit keempat. Kata kode yang ditransmisikan untuk \({\mathbf x}\) dan \({\mathbf z}\) masing-masing pasti adalah \((\codeword{110110})\) dan \((\codeword{010011})\text{.}\) Sindrom \({\mathbf y}\) tidak muncul pada kolom mana pun dari matriks \(H\text{,}\) sehingga pasti terjadi beberapa kesalahan yang menghasilkan \({\mathbf y}\text{.}\)
Kita dapat menggunakan teori grup untuk memperoleh cara lain dalam mendekode pesan. Suatu kode linear \(C\) merupakan subgrup dari \({\mathbb Z}_2^n\text{.}\) Pendekodean koset atau pendekodean standar menggunakan koset-koset \(C\) dalam \({\mathbb Z}_2^n\) untuk menerapkan pendekodean kemungkinan maksimum. Misalkan \(C\) adalah kode linear \((n,m)\text{.}\) Suatu koset \(C\) dalam \({\mathbb Z}_2^n\) dituliskan dalam bentuk \({\mathbf x} + C\text{,}\) dengan \({\mathbf x} \in {\mathbb Z}_2^n\text{.}\) Berdasarkan Teorema Lagrange (Teorema 6.2.2), terdapat \(2^{n - (n - m)} = 2^m\) koset berbeda dari \(C\) dalam \({\mathbb Z}_2^n\text{.}\)
Terdapat \(2^{5-2} = 2^3\) koset \(C\) dalam \({\mathbb Z}_2^5\text{,}\) masing-masing berorde \(2^2 =4\text{.}\) Koset-koset ini tercantum dalam Tabel 8.4.6.
Tugas kita adalah mencari tahu bagaimana pengetahuan tentang koset dapat membantu kita mendekode suatu pesan. Misalkan \({\mathbf x}\) adalah kata kode asli yang dikirim dan \({\mathbf r}\) adalah tupel-\(n\) yang diterima. Jika \({\mathbf e}\) adalah kesalahan transmisi, maka \({\mathbf r} = {\mathbf e} + {\mathbf x}\) atau, secara ekuivalen, \({\mathbf x} = {\mathbf e} + {\mathbf r}\text{.}\) Namun, ini tepat merupakan pernyataan bahwa \({\mathbf r}\) adalah suatu unsur dalam koset \({\mathbf e} + C\text{.}\) Dalam pendekodean kemungkinan maksimum, kita mengharapkan kesalahan \({\mathbf e}\) sekecil mungkin; artinya, \({\mathbf e}\) memiliki bobot terkecil. Tupel-\(n\) berbobot terkecil dalam suatu koset disebut pemimpin koset. Setelah kita menentukan pemimpin koset bagi setiap koset, proses pendekodean menjadi tugas menghitung \({\mathbf r} + {\mathbf e}\) untuk memperoleh \({\mathbf x}\text{.}\)
Dalam Tabel 8.4.6, perhatikan bahwa kita telah memilih wakil dengan bobot sekecil mungkin bagi setiap koset. Wakil-wakil ini merupakan pemimpin koset. Sekarang, misalkan \({\mathbf r} = (\codeword{01111})\) adalah kata yang diterima. Untuk mendekode \({\mathbf r}\text{,}\) kita mendapati bahwa kata tersebut berada dalam koset \((\codeword{00010}) + C\text{;}\) jadi, kata kode yang mula-mula ditransmisikan pasti adalah \((\codeword{01101}) = (\codeword{01111}) + (\codeword{00010})\text{.}\)
Potensi masalah dengan metode pendekodean ini adalah bahwa kita mungkin harus memeriksa setiap koset untuk mencari kata kode yang diterima. Proposisi berikut memberikan metode untuk menerapkan pendekodean koset. Proposisi itu menyatakan bahwa kita dapat mengaitkan suatu sindrom dengan setiap koset; jadi, kita dapat membuat tabel yang menetapkan pemimpin koset yang bersesuaian dengan setiap sindrom. Daftar semacam itu disebut tabel pendekodean.
Misalkan \(C\) adalah kode linear \((n,k)\) yang diberikan oleh matriks \(H\text{,}\) dan misalkan \({\mathbf x}\) serta \({\mathbf y}\) berada dalam \({\mathbb Z}_2^n\text{.}\) Maka \({\mathbf x}\) dan \({\mathbf y}\) berada dalam koset \(C\) yang sama jika dan hanya jika \(H{\mathbf x} = H{\mathbf y}\text{.}\) Artinya, dua tupel-\(n\) berada dalam koset yang sama jika dan hanya jika sindrom keduanya sama.
Dua tupel-\(n\)\({\mathbf x}\) dan \({\mathbf y}\) berada dalam koset \(C\) yang sama tepat ketika \({\mathbf x} - {\mathbf y} \in C\text{;}\) namun, hal ini ekuivalen dengan \(H({\mathbf x} - {\mathbf y}) = 0\) atau \(H {\mathbf x} = H{\mathbf y}\text{.}\)
Tabel 8.4.8 merupakan tabel pendekodean bagi kode \(C\) yang diberikan dalam Contoh 8.4.5. Jika \({\mathbf x} = (\codeword{01111})\) diterima, maka sindromnya dapat dihitung sebagai
Dengan memeriksa tabel pendekodean, kita menentukan bahwa pemimpin kosetnya adalah \((\codeword{00010})\text{.}\) Sekarang, kata kode yang diterima dapat didekode dengan mudah.
Untuk suatu kode blok \((n,k)\text{,}\) timbul pertanyaan apakah pendekodean koset merupakan skema yang dapat dikelola. Suatu tabel pendekodean memerlukan daftar koset dan sindrom, masing-masing satu untuk setiap \(2^{n - k}\) koset \(C\text{.}\) Misalkan kita memiliki kode blok \((32, 24)\text{.}\) Kita memiliki kata kode dalam jumlah yang sangat besar, yaitu \(2^{24}\text{,}\) tetapi hanya terdapat \(2^{32 - 24} = 2^{8} = 256\) koset.
