Jurnal Matematika, Statistika & Komputasi Vol. 3 No 1 Juli 2006
Proses Decoding Kode Reed Muller Orde Pertama Menggunakan Transformasi Hadamard
Andi Kresna Jaya ∗

## Abstract
The first order Reed Muller, that is written R(1, r ), is obtained by construction variation from dual of extended Hamming code. Error from message or image through satellite transmission use R(1, r ) code will be easier to detected with decoding process. One of the efficient process decoding is Hadamard transformation. A vector message, binary vector tuple-2 n , is transformed by Hadamard transformation and output transformation is R real vector tuple-2 n with entries 1 and -1. Then R is transformed with Hadamard Matrix can be R ˆ real vector.
Key Word: Kode Reed Muller orde pertama (R(1, r )) , matriks Hadamard, proses decoding, simbol pengecek, transformasi Hadamard,  vektor pesan .

## 1.  Pendahuluan
Pesatnya perkembangan ilmu pengetahuan dan teknologi mendorong pertukaran informasi sebanyak-banyaknya dari suatu tempat ke tempat lain. Dalam teknologi informatika, informasi/pesan dikirim berupa data melalui encoder, saluran transmisi dan decoder. Pesan yang terkirim melalui encode berupa barisan karakter biner (0 dan 1) di saluran transmisi dapat saja mengalami gangguan yang menyebabkan kesalahan pada penerimaan pesan. Pada decoder pesan yang diterima diuraikan kembali menjadi pesan asli setelah dideteksi dan dikoreksi kesalahannya.
Kode merupakan hasil proses encoding dari semua pesan-pesan yang siap dikirimkan, sedangkan vektor di dalam Kode disebut kata kode. Kata kode umumnya terdiri dari gabungan dua sub vektor yaitu pesan asli dan simbol cek tambahan. Misalnya dalam bentuk pesan awal :
1 2 1 0 − = k m m m m m L dengan proses encoding, menjadi : 1 1 1 2 1 0 − + − = n k k k c c c c c c c c L L
dimana pesan asli pada kata kode c tersebut adalah
1 2 1 0 1 2 1 0 − − = k k m m m m c c c c L L dan sebagai simbol cek tambahan. 1 1 − + n k k c c c L
Tulisan ini membahas tentang konstruksi kode R(1, r ) dan proses decodingnya menggunakan transformasi Hadamard dan memperlihatkan algoritma sederhana dari proses decoding tersebut.  Kode ini pertama kali diterapkan oleh pesawat Mariner IX untuk pengiriman gambar hitam putih pada tahun 1972.
∗ Staf Pengajar pada Jurusan Matematika  F.MIPA Universitas Hasanuddin  Makassar
Jurnal Matematika, Statistika, & Komputasi Vol. 13  No.2 Januari  2017
Vol 13, No 2, 117-122, Januari 2017 122-127
Jurnal Matematika, Statistika & Komputasi Vol. 3 No 1 Juli 2006
2. Kode linier C( n , k , d ) dan kode dualnya C ┴ ( n , n - k , d )
Kode linier C( n , k , d ) adalah sub ruang berdimensi k dari ruang biner berdimensi n ( GF (2 n )). Sedangkan d merupakan minimum jarak Hamming atau minimum banyaknya posisi koordinat untuk dua buah vektor kode (kata kode). Untuk menghitung jarak Hamming sebuah kode yang mempunyai m kata kode, harus dilihat semua jarak dari pasangan kata kodenya. Misalkan  Kode C adalah sub ruang  berdimensi k dari ruang vektor GF (2 n ) di mana k<n .
( ) { } n j m i GF c c c c c C C C C C C j n i m , , 3 , 2 , 1 , , , 3 , 2 , 1 , 2 , , , , , 3 2 1 3 2 1 L L L L = = ∈ = = ( ) { } k i C C C C d d k i k i ≠ ≠ = , , min
Kode linier tersebut sesungguhnya merupakan range dari transformasi linier dari himpunan pesan asli yang diuraikan dalam bentuk biner sebagai ruang GF (2 k ) ke ruang biner GF (2 n ). Bentuk transformasi ini bisa disajikan sebagai matriks G berukuran n k × , sehingga kata kode c di C( n , k,d ) diperoleh sebagai hasil perkalian vektor pesan m dengan matriks G , untuk setiap  vektor pesan m dalam GF (2 k ). Matriks G dikenal sebagi matriks perentang untuk kode linier C( n,k ), yang  baris- barisnya merupakan vektor-vektor basis dari C( n , k ). Matriks perentang dalam   bentuk baku dapat ditulis sebagai :
[ ] A I G k M =
di mana :
I k adalah entri-entri pada matriks identitas orde k . A adalah matriks berukuran ) ( k n k − × yang entri-entrinya 0 dan 1.
Bentuk matriks perentang tidak tunggal karena dengan operasi baris elementer pada G menghasilkan suatu matriks yang juga merupakan perentang yang lain untuk kode C( n , k,d ). Kata kode c diperoleh sebagai hasil perkalian vektor pesan m dengan matriks G , untuk setiap , yaitu : ) 2 ( k GF m ∈ ) 2 ( ) 2 ( : n k GF GF E → mG c m = a
Misalkan vektor pesan m = (1 0 1) di GF (2 3 ) maka dengan matriks G diperoleh
( ) ( 10111 1 0 0 1 1 0 1 0 0 0 1 0 0 0 1 101 = ⎟ ⎟ ⎟ ⎠ ⎞ ⎜ ⎜ ⎜ ⎝ ⎛ = mG )
Selain kode C( n , k ),  dalam ruang GF (2 n ) terdapat juga sub ruang yang merupakan komplemen ortogonal dari kode C yaitu kode linier ( n , n - k ). Disebut komplemen ortogonal karena perkalian dot (kali dalam) antara vektor di C dan komplemennya adalah 0 (skalar nol). Kode linier yang merupakan komplemen dari C( n , k ) dinyatakan sebagai kode dual C dan ditulis dalam bentuk himpunan
( ) { } C c c b GF b C n ∈ ∀ = • ∈ = ⊥ , 0 2 .
Yang menarik di sini adalah matriks perentang dari C ┴ merupakan matriks pengecek untuk C, demikian pula sebaliknya. Secara khusus, jika adalah [ A I G k M = ]
Jurnal Matematika, Statistika, & Komputasi Vol. 13  No.2 Januari  2017
123
Andi Kresna Jaya 118 122 123
Jurnal Matematika, Statistika & Komputasi Vol. 3 No 1 Juli 2006
matriks perentang C, maka matriks perentang untuk kode dualnya berbentuk [ ] k n T I A H − = M . 3. Konstruksi kode R(1, r ) dari Kode Hamming (2 r –1, 2 r –1– r ,3)
Pandang kode linier dengan matriks pengeceknya adalah H . Kode ini akan dikonstruksi menjadi kode baru baik dengan penambahan atau pengurangan simbol pengecek maupun simbol pesan.
Kode linier C( n , k ) disebut juga kode Hamming( n , k ) jika dan dengan matriks pengecek H adalah matriks berukuran sedemikian sehingga kolom-kolomnya adalah semua vektor tak nol dalam ruang GF (2 1 2 − = m n m n k − = n k × m ). Kode Hamming merupakan kode linier C( n , k , d ) dimana n =2 r –1 dan k = n – r dengan matriks pengeceknya adalah matriks berukuran r × n sedemikian sehingga kolom- kolomnya adalah semua vektor dalam GF (2 r ) yang tidak nol. Konstruksi kode baru dari kode Hamming (2 r –1, 2 r –1– r ,3) dapat dilihat pada diagram berikut:
Kode Hamming (2 r –1, 2 r –1– r , d )
Kode Perluasan Hamming
(2 r , 2 r –1– r ,d+1)
Sub Kode Hamming (2 r –1, 2 r –2– r , d ’) pembesaran penghilangan pemanjangan pemendekan pemotongan perluasan

## Diagram 1. Variasi kode dari kode Hamming
Misalkan H r adalah matriks pengecek kode Hamming. H r memuat 2 r – 1 vektor kolom terurut r yang tidak nol. Kode dualnya adalah kode linier (2 r -1, r ) dengan matriks perentangnya adalah matriks pengecek kode Hamming. Konstruksi kode dual Hamming mempunyai kata kode yang berbobot 2 r -1, kecuali vektor nol.
Konstruksi kode baru dari kode dual Hamming dengan penambahan simbol pesan akan diperoleh kode Reed Muller orde pertama. Dual dari variasi konstruksi kode Hamming pada diagram di atas merupakan konstruksi dari dual kode Hamming. Diagram konstruksinya dapat dilihat pada diagram berikut:
Kode  dual Hamming (2 r –1, r,d )
Kode R(1, r )
(2 r , r +1, d’ ) Kode puncture R(1, r ) (2 r –1, r +1, d’ +1) penghilangan pembesaran pemotongan perluasan pemanjangan pemendekan Diagram 2. Variasi kode dari kode dual  Hamming
Jurnal Matematika, Statistika, & Komputasi Vol. 13  No.2 Januari  2017
124
Andi Kresna Jaya
Kode Reed Muller orde pertama R(1, r ) adalah kode linier (2 r , r +1,2 r -1 ) yang merupakan sub ruang vektor dengan matriks perentang adalah:
⎥ ⎦ ⎤ ⎢ ⎣ ⎡ = ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎦ ⎤ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎣ ⎡ = 0 : 1 0 0 0 1 1 1 1 ˆ Hr Hr H r M L H r adalah matriks pengecek kode Hamming atau matriks perentang kode dual Hamming. Matriks perentang untuk kode reed muller orde pertama memuat vektor-vektor kolom yang tidak nol berdimensi r +1.

## 4. Proses Decoding Kode Reed Muller Orde Pertama

## 4.1. Proses Decoding Konvensional
Proses decoding adalah proses menerjemahkan vektor kode  yang diterima menjadi pesan dalam bentuk aslinya setelah dikoreksi dan dideteksi kesalahannya. Misalnya setiap vektor c yang dikirimkan oleh transmiter diterima sebagai vektor r oleh receiver.
Strategi penguraian vektor pesan yang diterima secara umum bisa digambarkan sebagai berikut:
Misalkan vektor pesan yang diterima adalah r dimana r sama dengan sebuah vektor hasil encoding c ’, maka vektor r tidak akan dikoreksi tapi langsung diterjemahkan sebagai m sebagai bentuk pesan awal sebelum diubah menjadi c ’ pada encoding, walaupun sebenarnya vektor kode yng dikirimkan belum tentu c ’.
Jika r tidak sama dengan salah satu dari vektor kode, maka vektor r akan dikoreksi menjadi satu dan hanya satu vektor kode c di C yang paling dekat dengan r . Selanjutnya c diuraikan kembali menjadi m . Jika lebih dari satu vektor kode berjarak sama dengan vektor r , kesalahan hanya dapat terdeteksi tanpa dilakukan koreksi.

## 4.2. Proses Decoding Dengan Transformasi Hadamard
Untuk memahami proses decoding dengan menggunakan transformasi Hadamard ini diperlukan matriks Hadamard. Matriks Hadamard (dinotasikan H n ) adalah matriks bujur sangkar ordo- n dengan entri 1 dan -1 dan berlaku H n . H n T = n. I n . Matriks Hadamard ordo 2 n dengan n =2 r -1 dapat dikonstruksi dari hasil kali kronecker dari r buah matriks Hadamard . ⎥ ⎦ ⎤ ⎢ ⎣ ⎡ − = 1 1 1 1 2 H
Selanjutnya akan dibentuk vektor R terurut 2 r sebagai vektor dengan  entri  1 dan yang diperoleh dari r vektor biner terurut 2 1 − r . Untuk setiap komponen vektor r yang diasosiasikan dengan suatu vektor biner terurut- r yang berbeda. Suatu vektor u terurut- r mendefinisikan skalar r ( u ) adalah komponen dari r yang berasosiasi dengan u sehingga komponen pada posisi yang sama di R adalah R ( u ) = (-1) r ( u ) .
Jurnal Matematika, Statistika, & Komputasi Vol. 13  No.2 Januari  2017 125 Andi Kresna Jaya 120 125
Jurnal Matematika, Statistika & Komputasi
Vol. 3 No 1 Juli 2006
Pada posisi yang sama dari vektor R yang diasosiasikan dengan u vektor terurut- r , transformasi Hadamard dilakukan untuk mendapatkan vektor R ˆ yang komponennya diasosiasikan dengan vektor u dinyatakan dengan rumus:
∑ ∈ − = ) 2 ( . ) ( ) 1 ( ) ( ˆ r GF v v u v R u R
Komponen dari vektor R ˆ yang terbesarlah yang akan menentukan pada posisi mana dari vektor r yang akan dikoreksi. Berikut ini adalah ilustrasi proses decoding untuk R(1, r =5). Misalnya diberikan matriks perentang untuk R(1,5) adalah:
⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎦ ⎤ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎣ ⎡ = ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎦ ⎤ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎣ ⎡ = 5 4 3 2 1 5 1 11 1111111111 0000001111 0000000000 11
0000111111 1111110000 0000000011
11
1111000011 0011110000 0000111100 11 0011001100 1100110011 0011001100
01
0101010101 0101010101 0101010101
11 1111111111 1111111111 1111111111 ~ v v v v v H - Jika kata kode yang diterima adalah vektor dengan  panjang  32,  yang  berbentuk r = (01110110011101100111011001110110), maka  vektor hasil transformasinya adalah R ˆ = (-8,8,8,24,-8,8,8,-8,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0). Karena komponen terbesar pada posisi keempat berasosiasi dengan kolom keempat dari matriks perentang, maka hasil decoding adalah
c =  (0110011001100110011001100110  0110).  Hasil  akhir  decoding  adalah
m = (011000).
- Jika kata kode yang diterima adalah vektor dengan panjang  32,  yang  berbentuk r = (01101101100111011001111000011100), maka  hasil transformasinya adalah
R ˆ =(4,4,-4,-8,8,0,12,-4,-4,-4,0,8,0,0,-4,-4,-4,4,0,0,0,-6,-4,12,4,2,0,8,0,0,4,8). Karena komponen terbesar lebih dari satu, yaitu pada posisi ke-7 dan ke-24, proses decoding hanya mendeteksi bahwa telah terjadi kesalahan ganda pada kata kode yang diterima.
- Jika kata kode yang diterima adalah  vektor  dengan  panjang  32  adalah r = (11111111000000001111111100000000), maka vektor hasil transformasinya adalah (0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,-32,0,0,0,0,0,0,0). Karena komponen terbesar pada posisi 25 berasosiasi dengan kolom ke-25 dari matriks perentang, maka hasil decoding adalah r = (11111111000000001111111100000000). Hasil akhir decoding adalah m = (100011).

## 5. Penutup
Kode Reed Muller R(1, r ) diperoleh dari konstruksi kode dual Hamming dengan proses penambahan simbol pesan atau merupakan kode dual perluasan hamming yang merupakan bentuk kode linier C(2 r , r +1, 2 r -1 ). Proses decoding kode R(1, r ) untuk sembarang kata pesan yang diterima akan ditransformasi linier dua kali. Pertama dengan mengubah vektor biner tersebut menjadi vektor riil, kemudian vektor riil itu ditransformasi lagi dengan menggunakan transformasi
Jurnal Matematika, Statistika, & Komputasi Vol. 13  No.2 Januari  2017
126
Jurnal Matematika, Statistika & Komputasi Vol. 3 No 1 Juli 2006
Hadamard. Vektor yang diperoleh dari transformasi Hadamard inilah yang memberi informasi letak kesalahan pada kata pesan semula.
Jika vektor hasil transformasi hadamard itu mempunyai komponen lebih dari satu, maka vektor pesan hanya diketahui mengalami kesalahan pada posisi-posisi tersebut tapi tidak dapat dilakukan koreksi terhadap pesan yang diterima.
Kemampuan mengoreksi kesalahan tersebut serupa dengan proses decoding menggunakan sifat koset dari grup kode ataupun dengan strategi maksimum decoding. Untuk itu disarankan penelitian lebih lanjut mengenai proses decoding untuk ketiga cara ini.

## Daftar Pustaka
[1]   Hillman Abraham, Gerald A., 1994, “Abstract Algebra” , A First Undergraduate Course. PWS Publishing Co.
[2]  J.B. Fraleigh., 1994, “A First Course in Abstract Algebra” , Addison Wesley.
[3]    F.J. Mac Williams, N.J.A. Sloane, 1993, “The theory of Error Correcting Codes”. Volume 16. North Holland mathematics Library.
Jurnal Matematika, Statistika, & Komputasi Vol. 13  No.2 Januari  2017
127 Andi Kresna Jaya 122 127