KON NSTRUKS SI KODE LINEAR BINER O OPTIMAL L KUAT BER RJARAK MINIMUM 9 DAN N 11
DI UTOM MO PUTRANTO HAD
SEKOLA AH PASCA ASARJAN NA IN NSTITUT T PERTAN NIAN BOG GOR 2011
.
PERNYATAAN MENGENAI TESIS DAN SUMBER INFORMASI Dengan ini saya menyatakan bahwa tesis (Konstruksi Kode Linear Biner Optimal Kuat Berjarak Minimum 9 dan 11) adalah karya saya dengan arahan dari komisi pembimbing dan belum diajukan dalam bentuk apapun kepada perguruan tinggi manapun. Sumber informasi yang berasal atau dikutip dari karya yang diterbitkan maupun tidak diterbitkan dari penulis lain telah disebutkan dalam teks dan dicantumkan dalam Daftar Pustaka di bagian akhir tesis ini. Bogor, November 2011 Putranto Hadi Utomo NIM G551090421
.
ABSTRACT PUTRANTO HADI UTOMO. Construction of Strongly Optimal Binary Linear Code with Minimum Distance 9 and 11. Supervised by SUGI GURITMAN and TEDUH WULANDARI MAS’OED. A binary linear code of length n over Fq is a subspace of Fqn . A code has three parameters that attached to it, namely length, dimension, and minimum distance. A code with length n, dimension k and minimum distance d is often called [ n, k , d ] -code. Usually, when two parameters are given, then we want to find a code that has the best value for the last parameter. Based on GilbertVarshamov bound, if a [ n, k , d ] -code exists and can not be expanded, we call it a strongly optimal code. In this paper, we construct strongly optimal code with minimum distance 9 and 11. In constructing the code, we created a theorem and algorithm based on Gilbert-Varshamov bound before we implement the algorithm to MAPLE programming language. Because of computational limitations, the program can only construct up to k = 10 for d = 9 and k = 12 for d = 11. Keywords: binary linear code, Gilbert Varshamov bound, strongly optimal code.
.
RINGKASAN PUTRANTO HADI UTOMO. Konstruksi Kode Linear Biner Optimal Kuat Berjarak Minimum 9 dan 11. Dibimbing oleh SUGI GURITMAN dan TEDUH WULANDARI MAS’OED. Media informasi, seperti sistem komunikasi dan media penyimpanan untuk data, tidak sepenuhnya reliabel. Hal ini dikarenakan bahwa pada praktiknya ada gangguan (noise) atau interferensi lainnya sehingga pesan yang dikirim berubah (terdapat error pada pesan). Salah satu masalah dalam teori koding (coding theory) adalah untuk mendeteksi atau bahkan mengoreksi galat (error) tersebut. Suatu kode (code) diciptakan untuk mendeteksi atau mengoreksi galat akibat saluran yang terganggu. Dari masalah tersebut, ingin dikonstruksi kode-kode optimal kuat, yaitu kode dengan parameter [n,k,d] dengan syarat tidak ada kode dengan parameter [n+1,k+1, d], lebih jauh lagi, diharapkan dapat diperbaiki batas bawah dari Tabel Brouwer. Untuk mencapai hal tersebut, perlu dilakukan beberapa hal sebagai berikut, yang selanjutnya menjadi tujuan dari penelitian ini. 1. Mengkaji teorema yang terkait dengan konstruksi kode linear, terutama Gilbert-Varshamov bound. 2. Menyusun algoritme-algoritme untuk mengontruksi kode linear biner. 3. Mengimplementasikan algoritme-algoritme tersebut dalam suatu bahasa pemograman dan mengujicobakan untuk kode linear dengan jarak minimum 9 dan 11. Setelah dipelajari teorema Gilbert-Varshamov, disusun teorema konstruksi sebagai berikut. Jika matriks B berukuran k × r dikonstruksi berdasarkan sifat sebagai berikut. 1. Semua vektor baris dari B berbeda, dan 2. Jumlah setiap i vektor baris dari B berbobot paling sedikit ( d − i ) untuk i = 2, 3,..., s di mana s = min {d − 1, k} , dan ( d −1) ≤ r , maka
H = ( BT | I r ) dan G = ( I k | B )
secara berturut-turut merupakan matriks cek paritas dan matriks generator untuk kode linear C dengan parameter [ k + r , k , ≥ d ] . Selanjutnya, untuk membangun metode konstruksi yang efisien, perlu didefiniskan struktur data yang baru, yang merepresentasikan ruang vektor F2n ,
yaitu himpunan kuasa atas A = {0,1, 2,..., n − 1} . Untuk itu, perlu didefinisikan
korespondensi satu-satu antara suatu vektor di Fqn dengan suatu himpunan bilangan bulat tak negatif. Selanjutnya, operasi penjumlahan dalam representasi himpunan didefinisikan sebagai operasi xor/selisih simetri. Karena struktur data
yang digunakan adalah struktur data khusus, maka perlu didefinisikan terlebih dahulu program-program tentang aritmatik aljabar matriks dalam representasi himpunan, seperti menghitung penjumlahan dua vektor dan operasi OBD. Setelah dibangun program-program dasar untuk proses aritmatik aljabarnya, selanjutnya akan dikonstruksi program pelacakan kode linear biner. Tiga program terpenting adalah: k 1. Melacak/mencari satu vektor baris x dalam F2 yang bisa ditambahkan ke matriks B berdasarkan teorema Gilbert-Vashamov. 2. Menguji apakah dua vektor x dan y bisa ditambahkan ke matriks B berdasarkan teorema Gilbert-Varshamov. 3. Menguji apakah m+1 vektor bisa ditambahkan ke matriks B Dalam penelitian ini, kode linear biner yang berhasil dikonstruksi hanya sampai k = 12, r = 18 untuk d = 9 dan sampai k = 14, r = 22 untuk d = 11. Namun demikian, sangat sulit untuk mengonstruksi semua kode optimal kuat. Hal ini disebabkan antara lain oleh: 1. Keterbatasan komputer yang digunakan, sehingga tidak mungkin melacak semua kemungkinan kombinasi. 2. Pemilihan kode dasar (matriks B awal) yang kurang baik. 3. Program konstruksi yang masih belum sempurna. Dalam penelitian ini, masih banyak kekurangan yang ada di dalamnya, diantaranya adalah: 1. Tidak semua kode linear optimal kuat dapat dikonstruksi, walaupun kode tersebut ada (telah dikonstruksi oleh orang lain). 2. Algoritme konstruksi, walaupun untuk representasi himpunan sudah cukup baik, masih dapat diperbaiki dalam hal kecepatan pelacakan kode-kode linear biner, terutama untuk dimensi yang cukup besar. Untuk ke depannya, dapat diperbaiki algoritme konstruksi sehingga dapat digunakan untuk mencari/melacak kode dengan lebih cepat dan dapat mencakup kode linear yang memiliki dimensi yang besar. Selain itu, dapat pula dikembangkan program untuk mengoleksi kode-kode atas Fq , untuk q > 2 . Kata kunci: kode linear biner, teorema Gilbert-Varshamov, kode optimal kuat
.
© Hak Cipta milik IPB, tahun 2011 Hak Cipta dilindungi Undang-Undang Dilarang mengutip sebagian atau seluruh karya tulis ini tanpa mencantumkan atau menyebutkan sumbernya. Pengutipan hanya untuk kepentingan pendidikan, penelitian, penulisan karya ilmiah, penyusunan laporan, penulisan kritik, atau tinjauan suatu masalah; dan pengutipan tersebut tidak merugikan kepentingan yang wajar IPB Dilarang mengumumkan dan memperbanyak sebagian atau seluruh karya tulis dalam bentuk apa pun tanpa izin IPB
.
KONSTRUKSI KODE LINEAR BINER OPTIMAL KUAT BERJARAK MINIMUM 9 DAN 11
PUTRANTO HADI UTOMO
Tesis sebagai salah satu syarat untuk memperoleh gelar Magister Sains pada Program Studi Matematika Terapan
SEKOLAH PASCASARJANA INSTITUT PERTANIAN BOGOR 2011
Penguji Luar Komisi pada Ujian Tesis: Dr. Ir. Sri Nurdiati, M.Sc.
Judul Tesis Nama NIM
: Konstruksi Kode Linear Biner Optimal Kuat Berjarak Minimum 9 dan 11 : Putranto Hadi Utomo : G551090421
Disetujui Komisi Pembimbing
Teduh Wulandari, M. Si. Anggota
Dr. Sugi Guritman Ketua Diketahui Ketua Program Studi Matematika Terapan
Dekan Sekolah Pascasarjana
Dr. Ir. Endar H. Nugrahani, M.S.
Dr. Ir. Dahrul Syah, M.Sc.Agr.
Tanggal Ujian: 28 Oktober 2011
Tanggal Lulus:
:
.
Untuk Ayahanda, Ibunda, serta Adik-adikku tersayang.
.
PRAKATA Puji dan syukur penulis panjatkan kepada Allah SWT atas segala karuniaNya sehingga tesis ini dapat diselesaikan. Tema yang dipilih dalam penelitian ini tentang masalah pada coding theory. Tesis ini merupakan syarat untuk menyelesaikan studi pada Program Magister Matematika Terapan, Departemen Matematika, Fakultas Matematika dan Ilmu Pengetahuan Alam, Institut Pertanian Bogor. Terima kasih penulis ucapkan kepada : • Bapak Sugi Guritman, Ibu Teduh Wulandari, dan Ibu Sri Nurdiati, selaku dosen pembimbing dan penguji yang telah memberi bimbingan, masukan, dorongan, nasihat serta segala bantuan sehingga tugas akhir ini dapat terselesaikan. • Ayah, ibu, dan adik-adik yang selalu memberi kasih sayang, perhatian, dukungan moril dan materi. • Semua staf dan dosen pengajar Departemen Matematika yang telah memberikan ilmu yang bermanfaat selama menuntut ilmu di Departemen Matematika. • Sahabat yang selalu memberi kebahagiaan, semangat, tantangan, perhatian, bantuan, inspirasi, doa, dan kasih sayang. • Teman-teman mahasiswa departemen Matematika. Terima kasih atas segala persahabatan yang telah kita jalin selama beberapa tahun ini. Penulis menyadari bahwa tulisan ini masih jauh dari kesempurnaan dan penulis sangat menghargai segala saran dan kritik yang membangun dari pembaca. Penulis juga mengharapkan tulisan ini dapat bermanfaat bagi semua pihak yang memerlukan. Terima kasih.
Bogor, November 2011
Putranto
.
RIWAYAT HIDUP Penulis dilahirkan di Bogor pada tanggal 7 September 1986 sebagai anak pertama dari 4 bersaudara pasangan Bapak Hadi Sumarno dan Ibu Dwi Ananingsih. Pendidikan formal yang ditempuh penulis yaitu di SDN Panaragan 2 Kodya Bogor lulus pada tahun 1999, SLTPN 1 Darmaga Kab. Bogor lulus pada tahun 2002, SMAN 5 Bogor lulus pada tahun 2005, dan pada tahun yang sama penulis diterima di Institut pertanian Bogor melalui jalur USMI (Undangan seleksi Masuk IPB). Pendidikan sarjana ditempuh di Departemen Matematika, Fakultas Matematika dan Ilmu Pengetahuan Alam, lulus pada tahun 2009. Penulis melanjutkan studi di Program Studi Matematika Terapan pada Program Pascasasarjana IPB. Selama mengikuti perkuliahan, penulis pernah menjadi asisten praktikum Analisis Numerik pada tahun 2009 dan asisten praktikum Metode Komputasi pada tahun 2010.
.
DAFTAR ISI Halaman
DAFTAR TABEL ...................................................................................... xiii DAFTAR GAMBAR .................................................................................. xiii DAFTAR LAMPIRAN .............................................................................. xiii 1
2
3
4
PENDAHULUAN ................................................................................ 1 1.1
Latar Belakang............................................................................... 1
1.2
Tujuan Penelitian ........................................................................... 4
TINJAUAN PUSTAKA ....................................................................... 6 2.1
Definisi Dasar dalam Aljabar dan Teori Koding ........................... 7
2.2
Enkoding Kode Linear ................................................................ 15
2.3
Dekoding Tetangga Terdekat ...................................................... 16
2.4
Dekoding Sindrom ...................................................................... 17
2.5
Dasar-dasar Konstruksi Kode ...................................................... 17
HASIL DAN PEMBAHASAN .......................................................... 20 3.1
Formulasi Masalah ...................................................................... 21
3.2
Analisis Teori .............................................................................. 23
3.3
Metode Komputasi ...................................................................... 30
3.4
Hasil yang Diperoleh ................................................................... 52
KESIMPULAN DAN SARAN .......................................................... 55
DAFTAR PUSTAKA .................................................................................. 57 LAMPIRAN ................................................................................................ 59
.
DAFTAR TABEL Halaman
Tabel 1. Tabel kebenaran unrtuk sifat asosiatif pada operasi xor................ 36 Tabel 2. Perbandingan komputasi antara dua representasi data .................. 52 Tabel 3. Hasil konstruksi untuk kode untuk d = 9 dan d = 11 ..................... 52
DAFTAR GAMBAR Halaman
Gambar 1. Proses koding untuk suatu pesan ................................................. 2 Gambar 2. Contoh enkoding dan dekoding dari suatu pesan ........................ 2 Gambar 3. Contoh informasi yang gagal terkirim ......................................... 3
DAFTAR LAMPIRAN Halaman
Lampiran 1. Tabel Brouwer......................................................................... 61 Lampiran 2. Program Konstruksi Kode ....................................................... 62
.
1 1.1
PENDAHULUAN
Latar Belakang
Media informasi, seperti sistem komunikasi dan media penyimpanan untuk data, tidak sepenuhnya reliabel. Hal ini dikarenakan bahwa pada praktiknya ada gangguan (noise) atau inferensi lainnya sehingga pesan yang dikirim berubah (terdapat galat pada pesan). Salah satu masalah dalam teori koding (coding theory) adalah untuk mendeteksi atau bahkan mengoreksi galat tersebut. Artikel tentang masalah tersebut pertama kali ditulis oleh C. E. Shannon pada tahun 1948 dalam artikelnya yang berjudul A Mathematical Theory of Communication. Masalah itu dapat digambarkan sebagai berikut. Apabila suatu pesan (informasi) dikirim melalui saluran terganggu (noisy channel), sering kali terjadi bahwa pesan yang diterima tidak sama dengan yang dikirim, misalnya pesan yang berupa gambar atau suara menjadi tidak jelas. Di dalam komunikasi, pesan direpresentasikan dalam bentuk digital sebagai blok (barisan) simbol, sering kali digunakan simbol biner yang dikenal dengan bitstring. Saluran biasanya berupa jaringan telepon, jaringan radio berfrekuensi tinggi atau jaringan komunikasi satelit. Saluran yang terganggu menyebabkan berubahnya beberapa simbol yang dikirim, sehingga mengurangi kualitas informasi yang diterima. Suatu kode (code) diciptakan untuk mendeteksi atau mengoreksi galat (error) akibat saluran terganggu. Dalam hal ini sebelum dikirim, semua pesan akan diubah menjadi kata kode (codeword) dengan cara menambahkan beberapa simbol ekstra pada simbol pesan. Proses pengubahan pesan menjadi kata kode disebut enkoding. Perangkat yang mengubah pesan menjadi kata kode disebut Enkoder. Kode merupakan himpunan yang anggotanya kata kode. Pendefinisian kode ini dilakukan sedemikian sehingga apabila terjadinya perubahan beberapa simbol pada kata kode, maka galat itu bisa dipulihkan lagi oleh dekoder. Dekoder merupakan perangkat yang mengubah barisan simbol yang diterima menjadi kata kode. Suatu model komunikasi dapat digambarkan seperti pada Gambar 1, dan untuk contohnya dapat dilihat pada Gambar 2.
2
sumber pesan
mesin penerima
enkoder sumber
dekoder sumber
enkoder saluran
saluran
dekoder saluran
gangguan
Gambar 1. Proses koding untuk suatu pesan.
Apel
Apel
00
00
00000
channel
01000
gangguan
Gambar 2. Contoh enkoding dan dekoding dari suatu pesan.
Ilustrasi tentang source coding dan channel coding akan dijelaskan pada paragraf berikut ini. Source coding terdiri dterdiri atasari dua bagian, yaitu source encoding dan source decoding. Source encoding meliputi perubahan pesan asal (message source) menjadi kode yang bersesuaian sehingga dapat dikirimkan melalui suatu saluran/jalur data, sedangkan source decoding meliputi perubahan kode yang dikirimkan menjadi pesan asal. Kode ASCII adalah salah satu contoh source coding yang mengubah setiap karakter menjadi suatu “byte” yang terdiri atas delapan bit. Sebagai contoh, misalkan source encoding untuk empat jenis buah-buahan didefinisikan sebagai berikut. •
Apel = 00
•
Pisang = 01
•
Ceri = 10
•
Anggur = 11
3
Misalkan pula pesan “Apel”, yang dikodekan sebagai “00” akan dikirimkan melalui noisy channel (jalur bergangguan). Pesan tersebut dapat saja menyimpang/ berubah dan diterima sebagai “10”. Dalam kasus ini, mesin penerima tidak dapat mendeteksi kesalahan tersebut, sehingga komunikasi tersebut gagal (lihat Gambar 3).
Apel
00
Pisang
channel
01
gangguan
Gambar 3. Contoh informasi yang gagal terkirim.
Pesan yang telah dikodekan oleh source encoder dapat saja berubah jika melalui noisy channel. Ide dari channel coding adalah untuk mendeteksi kesalahan tersebut dengan cara men-enkode lagi pesan yang akan dikirimkan dengan cara menambahkan unsur redundansi/unsur ekstra sehingga kesalahan tersebut dapat dideteksi atau bahkan dikoreksi. Untuk mengilustrasikan channel encoding, misalkan ditambahkan satu bit data redundansi pada contoh sebelumnya sebagai berikut. •
00 = 000
•
01 = 011
•
11 = 110
Misalkan pula pesan “apel” yang dikodekan sebagai “000” (setelah dilakukan source dan channel encoding) dikirimkan melalui saluran yang terganggu (noise) memiliki kesalahan satu bit, sehingga pesan yang diterima dapat berubah menjadi “001”, 010”, atau “100”. Dalam kasus ini, kesalahan dapat dideteksi karena tidak ada satupun dari “001”, “010”, dan “100” yang merupakan pesan awal. Untuk contoh di atas, kesalahan pesan dapat dideteksi dengan kompensasi kecepatan transfer, karena untuk mengirim pesan berukuran dua bit, perlu ditransmisikan kata kode berukuran tiga bit. Walaupun kesalahan pada pesan dapat dideteksi, mesin
4
penerima tidak dapat memperbaiki kesalahan tersebut, karena jika yang diterima adalah “100”. Ada kemungkinan kata kode tersebut berasal dari “000”, “110”, atau “101”. Namun, dengan ditambahkan lagi unsur redundansi, kesalahan tersebut dapat dikoreksi. Sebagai contoh, dapat didesain skema koding sebagai berikut. •
00 = 00000
•
01 = 01111
•
10 = 10110
•
11 = 11001
Untuk dapat membandingkan dengan contoh sebelumnya, misalkan pesan “apel” akan dikirimkan melalui sinyal terganggu dan hanya terjadi satu bit kesalahan. Dengan demikian, pesan yang diterima adalah salah satu dari lima kemungkinan berikut: “10000”, “01000”, “00100”, “00010”, atau “00001”. Misalkan yang sampai adalah “10000”, mesin penerima akan dapat mengambil kesimpulan bahwa pesan tersebut berasal dari “0000”, karena kesalahan yang terjadi hanya satu bit, sehingga tidak mungkin pesan tersebut berasal dari “01111”, “10110”, dan “11001”. Namun, dengan skema seperti ini, lebih banyak waktu yang terbuang. Secara umum, tujuan dari teori koding adalah untuk mengonstruksi suatu kode (enkoder dan dekoder) sehingga 1. dapat meng-enkode suatu pesan dengan cepat, 2. dapat mentransmisi pesan yang sudah di-enkode dengan mudah, 3. dapat men-dekode suatu pesan yang diterima dengan cepat, 4. dapat memaksimumkan informasi yang ditransfer per satuan waktu, dan 5. dapat secara maksimal dalam mendeteksi dan mengoreksi kesalahan. 1.2
Tujuan Penelitian
Berdasarkan latar belakang yang dipaparkan di atas, maka tujuan dari penelitian ini adalah: 1. Mengkaji teorema yang terkait dengan konstruksi kode linear, terutama Gilbert-Vashamov bound. 2. Menyusun algoritme-algoritme untuk mengontruksi kode linear biner.
5
3. Mengimplementasikan algoritme-algoritme tersebut dalam suatu bahasa pemograman dan mengujicobakan untuk kode linear dengan jarak minimum 9 dan 11. Dari tujuan-tujuan tersebut, penelitian ini diharapkan dapat memberikan suatu hal yang baru dalam teori koding, yaitu memperbaiki batas bawah dari Tabel Brouwer.
.
2
TINJAUAN PUSTAKA
Pada bab ini diberikan definisi dan teorema dalam aljabar linear maupun dalam teori koding yang melandasi penelitian yang dilakukan. 2.1
Definisi Dasar dalam Aljabar dan Teori Koding
Berikut adalah definisi dan teorema dasar dalam aljabar yang melandasi teori koding. 2.1.1
Definisi: Ruang Vektor
Misalkan Fq merupakan lapangan hingga dengan order q . Himpunan tak kosong V (dengan penjumlahan vektor dan perkalian skalar oleh elemen Fq ) merupakan ruang vektor dari Fq jika untuk semua u, v ∈V dan untuk semua
λ , μ ∈ Fq , berlaku: i.
u + v ∈V
ii.
(u + v ) + w = u + ( v + w)
iii.
∃ unsur 0 ∈V dimana 0 + v = v = v + 0, ∀v ∈V
iv.
∀u ∈ V , ∃ − u ∈ V dimana u + ( −u ) = 0 = ( −u ) + u
v.
u +v = v+u
vi.
λ ⋅ v ∈V
vii.
λ ⋅ (u + v ) = λ ⋅ u + λ ⋅ v
viii.
( λμ ) ⋅ u = λ ( μ ⋅ u )
ix.
Jika 1 merupakan unsur identitas untuk perkalian di Fq , maka
1⋅ u = u (Ling & Xing, 2004) 2.1.2
Definisi: Penjumlahan Vektor dan Perkalian Skalar di Fqn
Misalkan
didefinisikan
ruang
vektor
Fqn
atas
Fq ,
yaitu:
Fqn = {u | u = ( u1 , u 2 , u3 , … , u n ) ; ui ∈ Fq } . Misalkan pula V = ( v1 , v2 ,… , vn ) ∈ Fqn ,
W = ( w1 , w2 ,… , wn ) ∈ Fqn , dan
λ ∈ Fq . Maka penjumlahan vektor di Fqn
8
didefinisikan
sebagai
U + W = ( v1 + w1 , v2 + w2 ,… , vn + wn ) ∈ Fq ,
sedangkan
perkalian skalar didefinisikan sebagai λ ⋅ v = ( λ v1 , λ v2 ,… , λ vn ) ∈ Fqn . (Ling & Xing, 2004) 2.1.3
Definisi: Subruang (Subspace)
Suatu himpunan tak kosong C dari ruang vektor V merupakan subruang (ruang bagian) dari V jika C merupakan ruang vektor dan memiliki sifat penjumlahan vektor dan perkalian vektor yang sama dengan V . (Ling & Xing, 2004) 2.1.4
Proposisi 1
Suatu himpunan tak kosong C yang merupakan himpunan bagian dari atas Fq merupakan subruang jika dan hanya jika untuk
ruang vektor V
∀x, y ∈ C & λ ,μ ∈ Fq , berlaku λ x + μ y ∈ C . (Ling & Xing, 2004) 2.1.5
Definisi: Kombinasi Linear
Misalkan V merupakan ruang vektor atas Fq , λi ∈ Fq sembarang, maka
λ1u1 + λ2u 2 + … + λr u r merupakan kombinasi linear dari u1 , u 2 ,… , u r ∈ V . (Ling & Xing, 2004) 2.1.6
Definisi: Bebas Linear
Misalkan V
{v1 , v2 ,… , vk }
merupakan ruang vektor atas
dalam
V
dikatakan
saling
Fq , himpunan vektor bebas
linear
jika
λ1 v1 + λ2 v2 + … + λr vr = 0 mengakibatkan λ1 = λ2 = … = λr = 0 , dan tak bebas linear jika ada λi ≠ 0 yang mengakibatkan λ1 v1 + λ2 v2 + … + λr vr = 0 . (Ling & Xing, 2004) 2.1.7
Definisi: Rentang Linear
Misalkan V
merupakan ruang vektor atas Fq dan S = {v1 , v2 ,… , vk }
merupakan himpunan tak kosong dari V . Rentang linear dari S didefinisikan
9
S = {λ1v1 + λ2 v2 + … + λk vk ; λi ∈ Fq } .
sebagai
Jika
S =∅,
didefinisikan
S = {0} .
(Ling & Xing, 2004) 2.1.8
Definisi: Basis
Misalkan V merupakan ruang vektor atas Fq . Himpunan tak kosong B = {v1 , v2 ,… , vk } dari V dikatakan basis untuk V jika V = B dan B bebas
linear. Misalkan B = {v1 , v2 ,… , vk } basis untuk V , maka sembarang vektor v ∈V dapat dinyatakan sebagai kombinasi linear dari vektor B secara unik. 2.1.9
Teorema 1
Misalkan V merupakan ruang vektor atas Fq . Jika dim (V ) = k , maka: i.
V memiliki q k elemen.
ii.
V memiliki
1 k −1 k i ∏ ( q − q ) basis yang berbeda. k ! i =0 (Ling & Xing, 2004)
2.1.10 Definisi: Hasil Kali Skalar
Misalkan
V = ( v1 , v2 ,… , vn ) ∈ Fqn , W = ( w1 , w2 ,… , wn ) ∈ Fqn
.
Hasil
kali
skalar (dot product/hasil kali euclidian) dari V dan W didefinisikan sebagai
V ⋅W = v1w1 + v2 w2 + … + vn wn ∈ Fq . Hasil kali skalar merupakan salah satu contoh dari hasil kali dalam pada Fgn . Hasil kali dalam pada
Fqn
didefinisikan sebagai pasangan terurut
, : Fqn × Fqn → Fq yang memenuhi : ∀u , v ∈ Fqn , berlaku
i.
u + u , w = u , w + v, w .
ii.
u , v + w = u , w + v, w .
iii.
u , v = 0 untuk semua u ∈ Fqn jhj v = 0 .
iv.
u , v = 0 untuk semua v ∈ Fqn jhj u = 0 .
(Ling & Xing, 2004)
10
2.1.11 Definisi: Komplemen Orthogonal
Misalkan V = ( v1 , v2 ,… , vn ) ∈ Fqn , W = ( w1 , w2 ,… , wn ) ∈ Fqn . i.
Vektor V dan W dikatakan saling tegak lurus (orthogonal) jika
V ⋅W = 0 . ii.
Misalkan S merupakan himpunan bagian dari Fqn . Komplemen orthogonal
dari
S,
yaitu
S⊥
didefinisikan
sebagai
S ⊥ = {v ∈ Fqn | v ⋅ s = 0, ∀s ∈ S } . Jika S = ∅ , didefinisikan S ⊥ = Fqn .
Jika S merupakan subruang dari ruang vektor Fqn , maka S ⊥ merupakan subruang dari ruang vektor Fqn dan S
⊥
= S⊥.
(Ling & Xing, 2004) 2.1.12 Teorema 2
Diberikan ruang vektor Fqn . Misalkan S himpunan bagian dari Fqn , maka dim ( S
) + dim ( S ) = n . ⊥
(Ling & Xing, 2004) 2.1.13 Definisi: Kode Linear
Misalkan diberikan lapangan hingga Fq . Misalkan pula Fqn merupakan himpunan dari vektor-vektor atas Fq dengan panjang n . Kode linear C didefinisikan sebagai ruang bagian dari ruang vektor Fqn . Kode linear C dengan panjang n dan dimensi k sering dinamakan q − ary [ n, k ] − code (kode linear dengan parameter [ n, k ] ). Jika jarak minimum d dari C diketahui, C dapat disebut kode linear dengan parameter [ n, k , d ] . Atau biasa disebut kode linear-
[ n, k , d ] .
Untuk selanjutnya, jika parameter dari suatu kode tidak ditekankan,
cukup disebutkan bahwa C adalah suatu kode linear. Anggota dari C disebut dengan kata kode. (Ling & Xing, 2004)
11
2.1.14 Definisi: Kode dual dan dimensi dari suatu kode
Misalkan C merupakan kode linear, maka i.
⊥ Kode dual (dual code) dari C adalah C , yang merupakan
komplemen othogonal dari C . ii.
Dimensi dari kode linear C sama dengan dimensi C dalam sudut pandang subruang vektor atas Fq , yaitu dim ( C ) . (Ling & Xing, 2004)
2.1.15 Teorema 3
Diberikan ruang vektor Fqn . Misalkan C adalah kode linear dengan panjang
n dan dimensi k di Fqn , maka: C = q dim( C ) ↔ dim(C ) = log q C .
i.
Banyaknya unsur di C
ii.
C ⊥ juga merupakan suatu kode linear dan dim(C ) + dim(C ⊥ ) = n .
iii.
(C )
⊥ ⊥
=
=C.
(Ling & Xing, 2004) 2.1.16 Definisi: Self-orthogonal dan Self-Dual
Misalkan C adalah kode linear. i.
C dikatakan self- orthogonal jika C ⊆ C ⊥ .
ii.
C dikakatan self-dual jika C = C⊥ . (Ling & Xing, 2004)
2.1.17 Proposisi 2
Misalkan C adalah kode linear dengan panjang n . i.
Jika C merupakan kode yang self-orthogonal, maka dim ( C ) ≤
ii.
Jika C merupakan kode yang self-dual, maka dim ( C ) =
n . 2
n . 2
(Ling & Xing, 2004)
12
2.1.18 Definisi: Jarak Hamming (Hamming distance)
Diberikan ruang vektor Fqn atas lapangan Fq . Misalkan pula x dan y adalah anggota dari Fqn
( x, y ∈ F ) . n q
Jarak Hamming antara x dan y yang
dinotasikan dengan d ( x , y ) , didefinisikan sebagai berikut. d ( x, y ) = d ( x1 , y1 ) + d ( x2 , y2 ) + ...d ( xn , yn ) , dengan ⎧1 d ( xi , yi ) = ⎨ ⎩0
xi ≠ yi xi = yi
. (Ling & Xing, 2004)
2.1.19 Definisi: Jarak minimum suatu kode (Minimum distance of a code)
Misalkan C adalah kode linear yang memiliki kata kode lebih dari satu. Jarak minimum untuk C , yang dinotasikan d ( C ) , didefinisikan sebagai d ( C ) = min {d ( x, y ) | x, y ∈ C , x ≠ y} .
(Ling & Xing, 2004) 2.1.20 Definisi: Bobot Hamming (Hamming weight)
Diberikan ruang vektor Fqn . Misalkan pula x ∈ Fqn . Bobot Hamming (Hamming Distance), yang dinotasikan wt ( x) didefinisikan sebagai jumlah koordinat/unsur yang tak nol: wt ( x ) = d ( x, 0)
dengan 0 adalah vektor nol
atau dapat pula didefnisikan sebagai berikut.
⎧1 wt ( x) = d ( x, 0) = ⎨ ⎩0
jika x ≠ 0 . jika x = 0 (Ling & Xing, 2004)
2.1.21 Lema 1.
Diberikan ruang vektor Fqn . Misalkan x, y ∈ Fqn , maka d ( x, y) = wt ( x − y) . (Ling & Xing, 2004)
13
2.1.22 Lema 2
Misalkan diberikan bilangan prima q sembarang. Misalkan pula Fqn suatu ruang
vektor
atas
Fq .
Untuk
sembarang
x, y ∈ Fqn ,
berlaku
wt ( x ) + wt ( y ) ≥ wt ( x + y ) ≥ wt ( x ) − wt ( y ) .
(Ling & Xing, 2004) 2.1.23 Definisi: Bobot Minimal Hamming
Diberikan kode linear C . Minimum Hamming weight (bobot minimal Hamming) dari C , dinotasikan wt ( C ) , didefinisikan sebagai bobot terkecil dari kata kode tak nol dari C . (Ling & Xing, 2004) 2.1.24 Teorema 4
Misalkan C adalah suatu kode linear, maka d ( C ) = wt ( C ) . (Ling & Xing, 2004) 2.1.25 Definisi: Operasi Baris Dasar
Diberikan lapangan hingga Fq . Misalkan A adalah matriks dengan elemenelemen di Fq , yaitu A = ( aij ) , aij ∈ Fq . Matriks A dikatakan dikenakan operasi baris dasar (elementary row operation) jika •
Mempertukarkan baris ke- i dan ke- j .
•
Mengalikan baris ke- i dengan suatu konstanta k ≠ 0 .
•
Menambahkan baris ke- i dengan k kali baris ke- j . (Ling & Xing, 2004)
2.1.26 Definisi: Ekivalen baris
Misalkan A1 dan A2 adalah suatu matriks sembarang. Matriks A1 dikatakan ekivalen baris (row equivalent) terhadap A2 jika A1 bisa diperoleh dari sekumpulan operasi baris dasar dari matriks A2 . (Ling & Xing, 2004)
14
2.1.27 Definisi: Matriks Generator dan Matriks Cek Paritas
Diberikan kode linear C . i.
G dikatakan matriks generator bagi kode linear C jika barisbarisnya merupakan basis untuk C .
ii.
H dikatakan matriks cek paritas bagi kode linear C jika H ⊥ merupakan matriks generator bagi kode dual C .
(Ling & Xing, 2004) 2.1.28 Definisi: Bentuk standar dari H dan G
Diberikan kode linear C . Misalkan H dan G , secara berturut-turut adalah matriks cek paritas dan matriks generator untuk kode linear C . i.
Bentuk standar untuk matriks generator G adalah ( I k | X ) , dengan I k = Matriks identitas berukuran k × k .
ii.
Bentuk standar untuk matriks cek paritas H adalah
(Y | I n − k ) ,
dengan I n − k = Matriks identitas berukuran ( n − k ) × ( n − k ) . (Ling & Xing, 2004) 2.1.29 Teorema 5
Diberikan kode linear C . Misalkan H adalah suatu matriks cek paritas bagi kode linear C , maka i.
d ( C ) (jarak minimum dari C ) ≥ d jika dan hanya jika d − 1 kolom
dari H saling bebas linear. ii.
d ( C ) (jarak minimum dari C ) ≤ d jika dan hanya jika d kolom
dari H saling bergantung linear. (Ling & Xing, 2004) 2.1.30 Teorema 6
Diberikan kode linear C . Jika G = ( I k | X ) adalah bentuk standar dari matriks generator untuk suatu kode C dengan parameter [ n, k ] , maka matriks cek paritas untuk kode C adalah H = ( − X Τ | I n − k ) . (Ling & Xing, 2004)
15
2.1.31 Definisi: Ekivalensi dari Kode Linear
Misalkan diberikan sembarang kode linear C1 dan C2 . C1 dan C2 dikatakan ekivalen jika salah satunya dapat diperoleh dari kode yang lain dengan cara mengkombinasikan operasi-operasi sebagai berikut. i.
Mempermutasikan digit-digit yang ada di kata kode tersebut.
ii.
Mengalikan posisi tertentu dengan skalar. (Ling & Xing, 2004)
2.1.32 Teorema 7
Misalkan C adalah suatu kode linear dengan matriks generator G . Kode C akan ekivalen dengan kode linear C ' dengan matriks generator yang sudah dalam bentuk standar. (Ling & Xing, 2004) 2.2
Enkoding Kode Linear
Misalkan C adalah suatu kode linear- [ n, k , d ] , dan G adalah matriks generator untuk C . Misalkan pula u = ( u1 , u2 ,..., uk ) ∈ Fqk . Jika didefinisikan v = uG = u1 g1 + u 2 g 2 + ... + u k g k , karena v ∈ Fqn , maka v merupakan salah satu
kata kode di C . Proses membuat u menjadi v dinamakan dengan proses enkoding. (Ling & Xing, 2004) 2.2.1
Definisi: Koset
Misalkan C adalah suatu kode linear dengan panjang n . Misalkan pula u ∈ Fqn merupakan suatu vektor sembarang dengan panjang n . Koset C yang
ditentukan oleh u didefinisikan sebagai C + u = u + C = {v + u | v ∈ C } . (Ling & Xing, 2004) 2.2.2
Teorema 8
Diberikan ruang vektor Fqn . Misalkan C adalah suatu linear kode dengan parameter [ n, k , d ] , maka: i.
Semua vektor dari Fqn ada di dalam koset C .
16
ii.
Untuk semua u ∈ Fqn , C + u = C = q k .
iii.
Untuk semua u , v ∈ Fqn , jika u ∈ C + v , maka C + u = C + v .
iv.
Dua koset dikatakan identik jika irisannya merupakan himpunan kosong.
v.
Ada q n − k koset yang berbeda untuk C .
vi.
Untuk semua u , v ∈ Fqn , u − v ∈ C jika dan hanya jika u dan v ada dalam koset yang sama. (Ling & Xing, 2004)
2.2.3
Definisi: Coset Leader
Diberikan kode linear C . Suatu kata kode dalam C yang memiliki bobot (Hamming) terkecil, dikatakan sebagai coset leader. (Ling & Xing, 2004) 2.3
Dekoding Tetangga Terdekat
Diberikan kode linear C . Misalkan kata kode v dikirim dan diterima sebagai kode w . Misalkan didefinisikan vektor galat e = w − v . Dari definisi koset, diperoleh e = w − v ∈ w + C atau w − e = v ∈ C . Karena
w − e ∈ C , maka vektor galat e dan kode w yang diterima berada dalam koset yang sama. Karena vektor galat dengan bobot terkecil memiliki peluang terbesar untuk terjadi, maka ketika dekoder menerima kata kode w , dekoder memilih vektor galat e (dalam koset w + C ) dengan bobot terkecil dan menyimpulkan kode yang dikirim adalah v = w − e . (Ling & Xing, 2004) 2.3.1
Definisi: Sindrom
Misalkan C adalah suatu kode linear − [ n, k , d ] dan H adalah matriks cek paritas untuk C . Untuk sembarang w ∈ Fqn , sindrom dari w didefinisikan sebagai S ( w ) = wH T ∈ Fqn − k .
(Ling & Xing, 2004)
17
2.3.2
Teorema 9
Misalkan C adalah kode linear − [ n, k , d ] , maka kode C dapat memperbaiki ⎢ d − 1⎥ galat/error sebanyak ⎢ ⎥. ⎣ 2 ⎦
(Ling & Xing, 2004) 2.4
Dekoding Sindrom
Dekoding sindrome merupakan perbaikan dari dekoding tetangga terdekat. Ide dasar dari dekoding ini adalah untuk menghemat memori yang digunakan. 2.4.1
Teorema 10
Misalkan C adalah kode linear − [ n, k , d ] dan H adalah matriks cek paritas untuk C . Untuk sembarang u , v ∈ Fqn , berlaku i.
S (u + v ) = S (u ) + S ( v ) .
ii.
S ( u ) = 0 jika dan hanya jika u adalah kata kode dalam C .
iii.
S ( u ) = s ( v ) jika dan hanya jika u dan v ada dalam koset yang
sama. (Ling & Xing, 2004) Dari Teorema 10, dapat diambil kesimpulan bahwa suatu koset dapat didefinisikan oleh sindromnya, dan semua kata kode yang berada dalam suatu koset menghasilkan sindrom yang sama, atau dapat dikatakan sindrom dari suatu koset sama dengan sindrom dari anggotanya. Dengan kata lain, ada korespondensi satu-satu antara koset dan sindromnya. (Ling & Xing, 2004) 2.5
Dasar-dasar Konstruksi Kode
Apabila suatu kode telah berhasil dikonstruksi, maka kode dengan parameter yang berbeda dapat pula dikonstruksi, berikut adalah beberapa cara untuk mendapatkan kode lain tersebut.
18
2.5.1
Adding an overall parity check/Extending a code (Penambahan pada matriks cek paritas)
Misalkan C adalah suatu kode linear biner dengan parameter [ n, k , d ] dengan beberapa kata kodenya berbobot ganjil. Dari kode tersebut akan dibentuk kode baru Cˆ dengan menambahkan bit "0" di akhir kata kode yang berbobot genap, dan bit "1" di akhir kata kode yang berbobot ganjil. Dengan penambahan ini, jarak tiap pasang kata kode menjadi genap. Jika jarak minimum kode C ganjil, maka kode yang baru memiliki jarak minimum
d + 1, sehingga Cˆ memiliki parameter
[ n + 1, k , d + 1] .
Secara umum, proses
penambahan simbol pada matriks cek paritas disebut sebagai exending a code (memperluas suatu kode) . (MacWilliams & Sloane,1981) 2.5.2
Puncturing a code by deleting coordinates (Pemotongan kode dengan cara menghapus koordinat tertentu)
Misalkan C adalah suatu kode linear. Proses pemotongan kode (puncturing) merupakan invers/kebalikan dari proses memperluas kode (extending a code). Proses ini menghapus satu atau lebih koordinat dari setiap kata kode. Ketika suatu koordinat dihapus, panjang dan jarak minimum dari kode akan berkurang satu (namun, pada kasus tertentu, ada kalanya jarak minimum tetap). Dengan kata lain, jika kode awal C memiliki parameter [ n, k , d ] , kode yang baru C * memiliki parameter [ n − 1, k , d − 1] . (MacWilliams & Sloane,1981) 2.5.3
Expurgating by thowing away codewords (Penghapusan dengan cara menghilangkan beberapa kata kode)
Misalkan kode linear biner C memiliki parameter [ n, k , d ] dan memiliki kata kode dengan bobot ganjil dan genap. Kata kode dengan bobot ganjil dapat dihapus untuk mendapatkan kode baru dengan parameter
[ n, k − 1, d '] .
Pada
umumnya d ' > d . (MacWilliams & Sloane,1981)
19
2.5.4
Augmenting by adding new codeword (Memperbesar suatu kode dengan cara menambahkan kata kode baru)
Salah satu cara untuk memperbesar suatu kode adalah dengan cara menambahkan satu baris vektor 1 pada matriks generator. Jika C adalah suatu kode dengan parameter [ n, k , d ] dan tidak memiliki kata kode 1 (vektor satu), kode yang telah diperbesar berbentuk C ( ) = C ∪ (1 + C ) a
( C(
a)
mengandung/memiliki kata kode dari kode C beserta komplemennya),
sehingga C (
a)
a a memiliki parameter ⎡ n, k + 1, d ( ) ⎤ , dengan d ( ) = min {d , n − d '} , ⎣ ⎦
dan d ' = bobot terbesar dari kata kode di C . (MacWilliams & Sloane,1981) 2.5.5
Lengthening by adding message symbols (Memperpanjang suatu kode dengan menambahkan simbol pesan)
Untuk memperpanjang suatu kode linear C , dapat dilakukan dengan cara menambahkan kata kode baru, yaitu vektor 1 (augmenting a code). Setelah itu, dilanjutkan dengan memperluas (extending) kode sebanyak satu bit. Proses ini akan menambah satu simbol pesan. (MacWilliams & Sloane,1981) 2.5.6
Shortening a code (Memperpendek kode)
Memperpendek
kode
merupakan
invers/kebalikan
dari
proses
memperpanjang suatu kode (length a code). Untuk memperpendek suatu kode, diambil kata kode yang dimulai dengan x1 = 0 (simbol pertama = 0). Selanjutnya koordinat dari x1 dihapus. Proses seperti ini disebut mengambil cross-section dari suatu kode (taking a cross-section of the code) . (MacWilliams & Sloane,1981)
.
3 3.1
HASIL DAN PEMBAHASAN
Formulasi Masalah
Sejauh ini telah diperkenalkan bahwa terdapat tiga parameter yang terkait dengan konstruksi suatu kode, yaitu panjang, dimensi, dan jarak minimum. Jika
C adalah kode linear biner yang mempunyai panjang n , berdimensi k , dan berjarak minimum d , maka C dikatakan baik jika n kecil, k besar dan d besar. Makna fisiknya, n harus kecil terkait dengan kecepatan proses enkoding dan dekoding, dan juga terkait dengan besarnya memori yang digunakan dalam proses itu. Sementara itu k harus besar terkait dengan banyaknya pesan yang dapat diubah menjadi kata kode, sedangkan d harus besar terkait dengan banyaknya galat yang dapat dikoreksi. Misalkan diberikan sembarang dua parameter, yaitu
n
dan
k.
Permasalahannya, apakah ada suatu kode [ n, k , d ] untuk nilai d yang sebesarbesarnya?
Pertanyaan
tersebut
mengarah
pada
pendefinisian
fungsi
D ( n, k ) = max {d | kode [ n, k , d ] ada} . Dalam hal ini, suatu kode C dengan
parameter [ n, k , d ] disebut optimal − D (optimal jarak minimum), jika C ada (telah berhasil dikonstruksi) dan tidak ada kode dengan parameter [ n, k , d + 1] (telah pula dibuktikan). Batas bawah l dan batas atas u dari fungsi D ( n, k ) diartikan sebagai berikut. Misalnya D ( n, k ) terletak di antara l dan u
( l ≤ D ( n, k ) ≤ u ) , [ n, k , d ≤ l ] parameter
artinya telah berhasil dikonstruksi kode dengan parameter
dan telah berhasil pula dibuktikan bahwa tidak ada kode dengan
[ n, k , d > u ] ,
sedangkan ada atau tidaknya kode dengan parameter
[ n, k , d ] dengan l < d ≤ u
merupakan masalah terbuka (open problem).
Untuk memperbaiki satu langkah batas bawah dari fungsi D ( n, k ) , perlu dikonstruksi kode dengan parameter [ n, k , l + 1] , sedangkan untuk perbaikan satu langkah batas atas dari fungsi D ( n, k ) sama dengan membuktikan bahwa tidak ada kode dengan parameter
[ n, k , u ] .
Informasi terkini untuk batas fungsi
22
D ( n, k ) dapat dilihat di dalam Tabel Brouwer dan bisa diakses secara on-line
pada alamat http://codetables.de (cuplikan dari Tabel Brouwer dapat dilihat pada Lampiran 1). Jika berhasil diperbaiki satu saja batas (bawah atau atas) dari Tabel Brouwer, berarti telah berhasil "dipecahkan satu rekor dunia". Secara analog (ekivalen), untuk optimalisasi dimensi (optimal-K) dapat didefinisikan fungsi K ( n, k ) atau fungsi N ( n, k ) untuk optimalisasi panjang kode (optimal-N), dan sekaligus memformulasikan masalahnya. •
K ( n, d ) := max {k | kode [ n, k , d ] ada} .
•
N ( k , d ) := min {n | kode [ n, k , d ] ada} .
Berdasarkan formulasi umum problem di atas, pada penelitian ini akan didefinisikan kode optimal kuat (strongly optimal codes) beserta formula konstruksinya berlandaskan teorema-teorema yang telah didefinisikan pada tinjauan pustaka. Kode linear C dengan parameter [ n, k , d ] disebut kode optimal kuat jika kode linear- [ n, k , d ] ada dan telah berhasil dibuktikan bahwa kode linear- [ n + 1, k + 1, d ] tidak ada, sedangkan suatu kode disebut optimal- D jika kode linear- [ n, k , d ] ada dan telah berhasil dibuktikan bahwa kode linear-
[ n, k , d + 1]
tidak ada. Jika kode linear- [ n, k , d ] ada dan telah berhasil dibuktikan
bahwa kode linear- [ n − 1, k , d ] tidak ada, maka kode tersebut disebut optimal- N . Selanjutnya, jika kode linear- [ n, k , d ] ada dan telah berhasil dibuktikan bahwa kode linear- [ n, k + 1, d ] tidak ada, maka kode tersebut disebut optimal- K . Berdasarkan dasar-dasar konstruksi kode, dalam penelitian ini juga dianalisis hubungan antara kode yang memiliki sifat optimal-D, optimal-K, optimal-N, dan optimal kuat. Konstruksi kode yang dilakukan dalam penelitian ini dilakukan atas dasar teori konstruksi langsung (direct constructions). Ide dasarnya adalah sebagai berikut. Jika suatu kode memenuhi pertaksamaan Gilber-Varshamov, maka kode tersebut dapat diperluas [Brouwer, 1997]. Dalam penelitian ini, konstruksi kode dibatasi hanya untuk jarak minimum
d = 9 dan d = 11 . Selain itu, kode yang akan dikonstruksi hanya untuk kode linear
23
n biner, yaitu kode yang ada dalam ruang vektor F2 . Pemilihan kasus cukup untuk
d ganjil, hal ini didasarkan pada salah satu sifat kode linear yang dinyatakan sebagai berikut. 3.1.1
Teorema 11
Jika kode dengan parameter
[ n, k , d ]
dikonstruksi kode dengan parameter
ada untuk d ganjil, maka dapat
[ n +1, k, d +1]
dan setiap anggotanya
berbobot genap. Bukti:
Misalkan telah dikonstruksi kode linear dengan parameter [ n, k , d ] , dengan
d ganjil. Dengan melakukan penambahan pada matriks cek paritas (dasar konstruksi kode yang pertama) akan diperoleh kode dengan parameter
[ n +1, k, d +1] . ͏ 3.2
Analisis Teori
Diberikan kode linear C dengan parameter [ n, k ] . Misalkan H merupakan matriks
cek
paritas
untuk
C.
Dari
definisi
matriks
cek
paritas,
C = { x ∈ Fqn | HxT = 0} , atau dengan kata lain, C = ker ( H ) . Hal ini karena baris-
baris dari matriks H merupakan basis untuk C ⊥ , komplemen orthogonal bagi C . Karena kode linear C merupakan kernel dari matriks cek paritasnya, maka mengonstruksi suatu kode linear C sama dengan mengonstruksi matriks cek paritasnya. 3.2.1
Teorema 12
Diberikan kode linear C dengan panjang n . Jika H adalah matriks cek paritas untuk C , maka kode tersebut mempunyai dimensi ( n − r ) jika dan hanya jika ada r kolom dari H yang bebas linear tetapi tidak ada r + 1 kolom dari H yang bebas linear ( r adalah rank dari H ). Bukti:
24
Diberikan kode linear C dengan panjang n . Didefinisikan r = n-k. Misalkan H adalah matriks cek paritas bagi kode linear C . Misalkan pula G adalah matriks generator bagi kode linear C . Kode linear
C
memiliki pangkat
(n − r )
jika dan hanya jika
rank ( G ) = ( n − k ) . [Karena G adalah basis, dan banyaknya baris di G menunjukkan dimensi suatu kode]. Karena G dan H saling orthogonal, maka
rank ( G ) = ( n − r ) jika dan hanya jika rank ( H ) = r . ͏ 3.2.2
Teorema 13
Diberikan kode linear C dengan panjang n . Jika H adalah matriks cek paritas untuk C , maka kode tersebut mempunyai jarak minimum d jika dan hanya jika setiap d − 1 kolom dari H yang bebas linear dan ada d kolom dari H yang tidak bebas linear. Bukti:
Diberikan kode linear C dengan panjang n . Misalkan H adalah matriks cek paritas bagi kode linear C . Kode linear C berbobot minimum d jika dan hanya jika kedua butir berikut terpenuhi i. ii.
n Ada vektor v ∈ F2 dengan wt ( v ) = d sehingga HvT = 0T .
HwT ≠ 0T untuk setiap w ∈ F2 dengan wt ( w) < d . (Jika HwT = 0T , n
maka w ∈ C . Kontradiksi dengan fakta bahwa wt ( w) < d ). Di sisi lain, kedua butir di atas (i dan ii) dapat terjadi jika dan hanya jika ada
d kolom dari H yang tidak bebas linear dan setiap d − 1 kolom dari H bebas linear. ͏ 3.2.3
Teorema 14: The Singleton Bound
Diberikan kode linear C . Jika C adalah kode dengan parameter [ n, k , d ] maka ( n − k ) ≥ ( d −1) .
25
Bukti:
Misalkan diberikan kode linear C dengan parameter [ n, k , d ] , maka kode linear C memiliki matriks cek paritas H berukuran
(n − k)×n,
sehingga
rank ( H ) ≤ ( n − k ) . Dari Teorema 13, matriks H memiliki d − 1 kolom yang bebas linear, sehingga rank ( H ) = ( d − 1) , dengan kata lain ( d − 1) ≤ ( n − k ) . ͏ 3.2.4
Teorema 15: The Gilbert-Varshamov Bound
Diberikan kode linear C dengan parameter
⎛n⎞ ⎛n⎞ 1+ ⎜ ⎟ + ⎜ ⎟ + ⎝1⎠ ⎝2⎠
[ n, k , d ] .
Jika ketaksamaan
⎛ n ⎞ + ⎜ ⎟ < 2n− k berlaku, maka dapat dikonstruksi kode dengan ⎝ d −2 ⎠
parameter [ n + 1, k + 1, d ] . Bukti:
Misalkan diberikan kode linear yang memiliki parameter Berdasarkan Teorema 5, ada matriks cek paritas berordo
[ n, k , d ] .
(n − k)×n,
yaitu
H = ( c1 c2 ... cn ) yang setiap d − 1 vektor dari {c1, c2 ,..., cn } adalah bebas n−k n−k yang bukan i linear dalam ruang vektor F2 . Jika ada vektor x ∈ F2
kombinasi linear dari vektor-vektor kolom H , untuk i = 1, 2,..., d − 2 , maka
H ' = ( c1 c2 … cn
x ) adalah matriks cek paritas untuk kode linear yang
memiliki parameter [ n + 1, k + 1, d ] . Hal ini karena H ' berorde ( n − k ) × ( k + 1) dan setiap d − 1 vektor dari
{c1, c2 ,..., cn , x}
adalah bebas linear dalam ruang
n−k vektor F2 .
Jika banyaknya kombinasi linear yang mungkin dari kolom-kolom H ' sehingga tidak ada d − 1 kolom yang bergantung linear lebih besar atau sama n−k dengan jumlah vektor tak nol dalam F2 , maka H ' bukan matriks cek paritas
untuk kode linear dengan parameter [ n + 1, k + 1, d ] . Banyaknya vektor-vektor tak-
26
n−k yang mungkin dipilih untuk x adalah 2n − k − 1 , sedangkan nol dalam F2
banyaknya kombinasi linear yang mungkin dari kolom-kolom H ' adalah
⎛n⎞ ⎛n⎞ ⎜ ⎟+⎜ ⎟+ ⎝1⎠ ⎝2⎠
⎛ n ⎞ + ⎜ ⎟ . Dengan demikian, jika ada kode linear C dengan parameter ⎝ d −2 ⎠
⎛n⎞ ⎛n⎞ dan pertaksamaan 1 + ⎜ ⎟ + ⎜ ⎟ + ⎝1⎠ ⎝2⎠
[ n, k , d ]
⎛ n ⎞ + ⎜ ⎟ < 2n− k berlaku, maka dapat ⎝ d −2 ⎠
dikonstruksi kode baru dengan parameter [ n + 1, k + 1, d ] berdasarkan kode linear
C tersebut. ͏ 3.2.5
Lema 3
Misalkan C adalah suatu kode linear dengan panjang n , maka jumlah unsur satu pada setiap kata kode di posisi ke- i sama dengan nol atau setengah dari jumlah kata kode yang ada di C . Bukti:
Misalkan X adalah himpunan kata kode yang memiliki unsur nol pada koordinat ke- i dan Y adalah himpunan kata kode yang memiliki unsur satu pada koordinat ke- i , maka C = X ∪ Y . Jika Y = ∅ , maka C = X , sehingga tidak ada kata kode yang memiliki unsur satu pada posisi ke- i . Namun demikian, jika
Y ≠ ∅ , ambil c ∈ Y sembarang, karena c + Y ⊆ X , maka Y ≤ X . Selanjutnya, karena c + X ⊆ Y , maka X ≤ Y . Oleh karena itu, dapat diambil kesimpulan bahwa Y = X . ͏ 3.2.6
Proposisi 1
i.
Jika ada kode linear dengan parameter [ n, k , d ] , maka ada kode linear dengan parameter [ n − 1, k , d − 1] , di di manamana d > 1 .
ii.
Jika ada kode linear dengan parameter [ n, k , d ] , maka ada kode linear dengan parameter [ n + 1, k , d ] .
27
iii.
Jika ada kode linear dengan parameter [ n, k , d ] , maka ada kode linear dengan parameter [ n, k − 1, d ] , di mana k > 1 .
iv.
Jika ada kode linear dengan parameter [ n, k , d ] , maka ada kode linear dengan parameter [ n − 1, k − 1, d ] , di mana k > 1 .
Bukti:
i.
Misalkan C adalah kode linear dengan parameter [ n, k , d ] dengan
d > 1 . Karena C memiliki jarak minimal d , maka ada kata kode c ∈ C dimana wt ( c ) = wt ( C ) = d . Misalkan kata kode c memiliki unsur satu pada koordinat ke- i . Dengan menghapus unsur ke- i pada semua kata kode dalam C , akan diperoleh kode linear C ' dengan panjang ( n −1) dan c berubah menjadi c ' . Karena wt ( c ') = d −1 , maka wt ( C ') = d −1 . Untuk menunjukkan dim ( C ') = k , misalkan
dim ( C ') < k , maka ada x , y ∈ C , sehingga x + c = y di mana
wt ( c ) = 1 . Kontradiksi dengan d > 1 . Haruslah dim ( C ') = k . Dengan demikian, C ' memiliki parameter [ n − 1, k , d − 1] . ii.
Misalkan G k × n adalah matriks generator untuk kode linear C dengan parameter [ n, k , d ] . Tambahkan vektor nol pada kolom terakhir G sehingga membentuk matriks G ' yang berukuran k × ( n +1) . Karena yang ditambahkan adalah vektor nol, maka banyaknya kombinasi linear dari baris-barisnya tidak akan berubah, sehingga jarak minimumnya tidak berubah. Dengan kata lain, telah diperoleh kode linear dengan parameter [ n + 1, k , d ] .
iii.
Misalkan C adalah kode linear dengan parameter [ n, k , d ] dengan
k > 1 . Karena C memiliki jarak minimal d , maka ada kata kode
c ∈ C di mana wt ( c ) = wt ( C ) = d . Misalkan Gk ×n adalah matriks generator untuk C dan c ada di salah satu baris dari G . Misalkan
28
pula baris ke- r dari G yang tidak sama dengan c dihapus sehingga membentuk kode baru, yaitu C ' dengan matriks generator G ' . Karena baris-baris di G saling bebas linear, maka semua baris di G ' juga saling bebas linear, sehingga
dim ( C ') = k − 1. Karena
wt ( C ) = wt ( c ) = d dan kata kode c tetap ada di C ' , maka wt ( C ') = d , sehingga kode linear
C'
memiliki parameter
[ n, k −1, d ] . iv.
Misalkan C adalah kode linear dengan parameter [ n, k , d ] dengan
k > 1 . Karena C memiliki jarak minimal d , maka ada kata kode c ∈ C di mana wt ( c ) = wt ( C ) = d . Misalkan G dan H adalah matriks generator dan matriks cek paritas untuk C . Misalkan pula kata kode c memiliki unsur nol pada koordinat ke- i . Ada dua kasus yang mungkin terjadi, kasus pertama adalah semua kata kode di C memiliki unsur nol pada koordinat ke- i , sedangkan kasus kedua tidak semua kata kode memiliki unsur nol pada koordinat ke- i . Jika kasus pertama yang terjadi, maka koordinat ke- i pada semua kata kode dapat dihapus sehingga menghasilkan kode dengan parameter
[ n −1, k, d ] (Proposisi 1 butir i), selanjutnya dengan menghapus satu baris dari matriks generator untuk kode dengan parameter
[ n −1, k, d ]
tersebut, akan diperoleh kode dengan parameter
[ n −1, k −1, d ]
(Proposisi 1 butir ii). Seandainya kasus kedua yang
terjadi, yaitu ada beberapa kata kode yang memiliki unsur satu pada koordinat ke- i , maka berdasarkan Lema 3, setengah dari kata kode yang ada di C memiliki unsur satu pada koordinat ke- i . Dengan menghapus koordinat ke- i pada setiap kata kode yang ada di C , akan diperoleh kode C ' yang meniliki panjang ( n −1) . Misalkan kata kode c berubah menjadi c ' , karena yang dihapus pada koordinat ke-
i adalah unsur nol, maka wt ( c ') = d , sehingga wt ( C ') = d .
29
Selanjutnya dengan menghapus satu baris dari matriks generator untuk kode dengan parameter [ n −1, k , d ] tersebut, akan diperoleh kode dengan parameter [ n − 1, k −1, d ] (Proposisi 1 butir ii). ͏ 3.2.7
Proposisi 2
Diberikan kode linear C dengan parameter [ n, k , d ] . i.
Jika C optimal kuat, maka C optimal- K .
ii.
Jika C optimal- N , maka C optimal- D .
iii.
Jika C optimal- K , maka belum tentu C optimal kuat.
iv.
Jika C optimal- D , maka belum tentu C optimal- N .
v.
Jika C optimal- D , maka belum tentu C optimal- K .
vi.
Jika C optimal- D , maka belum tentu C optimal kuat.
vii.
Jika C optimal- N , maka belum tentu C optimal kuat.
Bukti:
i.
Andaikan C tidak optimal- K , maka ada kode linear C ' dengan parameter [ n, k + 1, d ] . Karena ada kode C ' ada, maka dari Proposisi 1 bagian ii, akan ada kode linear dengan parameter [ n + 1, k + 1, d ] . Hal ini kontradiksi dengan fakta bahwa kode C optimal kuat.
ii.
Andaikan C tidak optimal- D , maka ada kode linear C ' dengan parameter [ n, k, d + 1] . Karena kode C ' ada, maka dari Proposisi 1 bagian i, akan ada kode linear dengan parameter [ n − 1, k , d ] . Hal ini kontradiksi dengan fakta bahwa kode C optimal-N.
iii.
Dari Tabel Brouwer, ada kode dengan parameter [13,9,3] dan tidak ada kode dengan parameter parameter [14,10,3] ada.
[13,10,3] .
Tetapi kode dengan
30
iv.
Dari Tabel Brouwer, ada kode dengan parameter [14,7,4] dan tidak ada kode dengan parameter [14,7,5] . Tetapi kode dengan parameter
[13,7,4] ada. v.
Dari Tabel Brouwer, ada kode dengan parameter [15,4,8] dan tidak ada kode dengan parameter [15,3,9] . Tetapi kode dengan parameter
[15,4,8] ada. vi.
Dari Tabel Brouwer, ada kode dengan parameter [17,8,6] dan tidak ada kode dengan parameter [17,8,9] . Tetapi kode dengan parameter
[18,9,6] ada. vii.
Dari Tabel Brouwer, ada kode dengan parameter [15,4,8] dan tidak ada kode dengan parameter [14,4,8] . Tetapi kode dengan parameter
[16,5,8] ada. ͏ 3.3
Metode Komputasi
Dalam penelitian ini, software yang digunakan untuk mengonstruksi kode optimal kuat adalah MAPLE. Dari analisis teori, diturunkan algoritme-algoritme untuk mengonstruksi kode optimal kuat. Dalam subbab-subbab berikut ini, dibahas algoritme konstruksi dan deskripsi program konstruksi. 3.3.1
Ide dasar konstruksi kode
Untuk mengkonstruksi suatu kode, sama saja artinya dengan mengonstruksi matriks cek paritas H . Berlandaskan teorema-teorema yang telah disebutkan di landasan teori, cukup dikonstruksi bentuk standar dari H , yaitu H = ( B T | I r ) . Berdasarkan pertimbangan efisiensi komputasi, cukup dikonstruksi matriks B berukuran k × r . Setelah mempelajari teorema-teorema sebelumnya, terutama teorema Gilbert-Varshamov, dapat dibuat teorema baru yang berkaitan dengan konstruksi kode linear biner, yaitu:
31
Teorema 16
Jika matriks B berukuran k × r dikonstruksi berdasarkan sifat sebagai berikut. 1. Semua vektor baris dari B berbeda, dan 2. Jumlah setiap i vektor baris dari B berbobot paling sedikit ( d − i ) untuk i = 2, 3,..., s di mana s = min {d −1, k} , dan ( d −1) ≤ r ,
maka H = ( BT | I r ) dan G = ( I k | B )
secara berturut-turut merupakan matriks cek paritas dan matriks generator untuk kode linear C dengan parameter [ k + r , k , ≥ d ] . Bukti:
Misalkan telah dikonstruksi matriks B berukuran k × r sebagaimana disyaratkan teorema. Akan ditunjukkan bahwa H = ( B t | I r ) merupakan matriks cek paritas untuk kode linear C dengan parameter [ k + r , k , ≥ d ] . Karena H berukuran r × ( k + r ) , maka C memiliki panjang k + r . Karena jumlah baris matriks B sama dengan k , maka kode linear C berdimensi k . Selanjutnya, akan ditunjukkan bahwa kode linear C memiliki jarak minimum kurang dari atau sama dengan d . Andaikan ada v ∈ C dengan
wt ( v ) < d dan dituliskan v = ( vm , vc ) di mana vm merupakan vektor pesan dengan wt ( vm ) = i dan vc adalah vektor cek dengan wt ( vc ) = j , maka berlaku
i + j < d ⇔ j < d − i ⇒ wt ( vc ) < d − i
(1)
⎛ vT ⎞ HvT = 0T ⇔ ( B T | I r ) ⎜ mT ⎟ = 0T ⇔ B T vmT + I r vcT = 0T ⇔ B T vmT = vcT . ⎝ vc ⎠
(2)
dan
Karena wt ( vm ) = i , dan berdasarkan pada syarat 2 dari konstruksi B, maka wt ( BT vmT ) ≥ d − i .
(3)
32
Dari persamaan 2, diperoleh bahwa BT vmT = vcT , sehingga persamaan 3 ekivalen dengan wt ( vc ) ≥ d − i . Hal ini kontradiksi dengan persamaan 1. Sehingga dapat disimpulkan bahwa kode linear C memiliki jarak minimum ≥ d . ͏ Dari Teorema 16, untuk mengonstruksi kode linear C - [ k + r, k , d ] , sama artinya dengan mengonstruksi matriks B yang berukuran k × r yang semua baris dari B berbeda dan jumlah setiap i vektor baris dari B berbobot paling sedikit
( d − i ) , untuk i = 1, 2, 3,..., s , dengan s = min {d −1, k} , dan ( d −1) ≤ r . Misalkan diberikan matriks B untuk kode C dengan parameter [ n, k , d ] , dengan G = [ I | Bk×r ] adalah matriks generator untuk C . Akan dicari vektor x ∈ F2r
yang bisa ditambahkan ke matriks
B sehingga diperoleh kode
[ n +1, k +1, d ] . Untuk memilih vektor x , pertama-tama dipilih salah satu baris dari matriks
B . Misalkan pula banyaknya unsur satu dari baris tersebut sama dengan v , dan banyaknya unsur nol sama dengan r − v . Dari Teorema 16, salah satu syarat suatu vektor dapat ditambahkan adalah memiliki bobot paling sedikit sebesar d − 1 , sehingga dipilih vektor x = ⎡ x11×v | x21×( r−v) ⎤ dengan x1 merupakan vektor biner yang ⎣ ⎦ memiliki ( v − i ) unsur satu dengan i = 0,1, 2,..., v dan x2 merupakan vektor biner yang memiliki
( j − i)
unsur satu dengan j = d − 2, d − 1,...r yang memenuhi
ketaksamaan v + j − 2i ≥ d − 1 (karena bobot dari x sama dengan banyaknya unsur satu dalam x , yaitu sama dengan
(v − i) + ( j − i) ,
atau v − j − 2 i ).
Pemilihan vektor dengan cara di atas dilakukan untuk mengefisiensikan komputasi yang dilakukan, sehingga tidak semua vektor anggota F2r diuji berdasarkan Teorema 16. Setelah diperoleh vektor x , langkah selanjutnya adalah menguji apakah vektor x dapat ditambahkan ke matriks B dengan menguji bobot vektor x + bi sedemikian sehingga wt ( x + bi ) ≥ d − 1 − i , dengan bi adalah anggota dari semua
33
kombinasi i vektor baris di B untuk i = 1, 2,..., s , dan s = min {d −1, k} . Apabila x lulus uji, maka diperoleh satu vektor yang dapat ditambahkan ke matriks B .
Jika semua langkah untuk memperoleh satu vektor diulangi sampai tidak ada vektor anggota F2r yang bisa ditambahkan ke matriks B , maka akan diperoleh himpunan satu vektor yang dapat ditambahkan ke matriks B . Misalkan L1 adalah himpunan satu vektor yang dapat ditambahkan ke matriks B . Dari L1 , dapat dicari pasangan dua vektor yang dapat ditambahkan ke matriks B sehingga diperoleh kode linear dengan parameter
[ n + 2, k + 2, d ] .
Caranya adalah dengan menjumlahkan setiap kemungkinan dua vektor yang berbeda yang ada di L1 . Misalkan hasil penjumlahannya adalah vektor y . Apabila bobot y lebih besar dari ( d − 2) , proses dilanjutkan dengan menguji bobot vektor
( y + bi )
sedemikian sehingga wt ( y + bi ) ≥ d − 2 − i , dengan bi
adalah anggota dari semua kombinasi i vektor baris di B untuk i = 1, 2,..., s , dan
s = min {d −1, k} . Apabila vektor y tersebut lulus uji, maka diperoleh dua vektor yang dapat ditambahkan ke matriks B . Jika semua langkah untuk memperoleh dua vektor diulangi sampai tidak ada pasangan dua vektor anggota L1 yang bisa ditambahkan ke matriks B , maka akan diperoleh himpunan dari kumpulan dua vektor yang dapat ditambahkan ke matriks
B. Secara serupa, untuk memperoleh pasangan m + 1 vektor yang bisa ditambahkan ke matriks B , dapat dicari dari himpunan dari kumpulan m vektor yang bisa ditambahkan ke matriks B . Misalkan Lm adalah himpunan dari kumpulan m vektor anggota F2r yang dapat ditambahkan ke matriks B . Dari Lm , dapat dicari ( m + 1) vektor yang bisa ditambahkan ke matriks B dengan cara mencari dua anggota Lm yang jika digabung memiliki m + 1 vektor yang berbeda. Misalkan dua kumpulan m vektor tersebut adalah y1 dan y2 . Selanjutnya dilakukan pengujian sebagai berikut.
34
1. Menguji apakah kedua vektor anggota
( y1 ∪ y2 ) − ( y1 ∩ y2 )
dapat
ditambahkan ke matriks B . 2. Menguji apakah kedua vektor anggota
( y1 ∪ y2 ) − ( y1 ∩ y2 )
ditambahkan dengan setiap i vektor dalam
( y1 ∩ y2 ) ,
yang jika
i = 1, 2,...m − 1
bisa ditambahkan ke matriks B . Untuk menguji j vektor bisa ditambahkan ke matriks B, caranya adalah dengan menjumlahkan j vektor tersebut, misalkan hasil penjumlahannya adalah vektor y . Apabila bobot y lebih besar dari ( d − j ) , proses dilanjutkan dengan menguji bobot vektor ( y + bi ) sedemikian sehingga wt ( y + bi ) ≥ d − j − i , dengan
bi adalah anggota dari semua kombinasi i vektor baris di B untuk i = 1, 2,..., s , dan s = min {d −1, k} . Apabila vektor y tersebut lulus uji, maka diperoleh m + 1 vektor yang dapat ditambahkan ke matriks B . Misalkan Lm adalah himpunan dari kumpulan m vektor anggota F2r yang dapat ditambahkan ke matriks B . Untuk mencari pasangan ( m + 1) vektor yang bisa ditambahkan ke matriks B , dapat diilustrasikan pula dengan menggunakan teori graf, yaitu dengan memisalkan vektor xi ∈ F2r sebagai suatu verteks. Jika ada j verteks yang membentuk graf lengkap, maka j vektor yang berkaitan dengan
verteks tersebut dapat ditambahkan ke matriks B . Dengan demikian, untuk memperoleh pasangan
( m + 1)
vektor yang bisa ditambahkan ke matriks B ,
dipilih graf lengkap (complete graph) yang terdiri atas ( m + 1) verteks. Dari penjabaran di atas, proses ekstensi kode [ n, k , d ] tersebut dilakukan tahap demi tahap. Hal tersebut dilakukan sampai diperoleh suatu kode C dengan parameter [ n ', k ', d '] yang sudah tidak bisa diperluas lagi. Jika telah dibuktikan bahwa kode dengan parameter [ n '+ 1, k '+ 1, d ] tidak ada, maka C merupakan kode optimal kuat yang telah berhasil dikonstruksi. Akan tetapi, ketika diperoleh informasi bahwa ada kode dengan parameter [ n '+ 1, k '+ 1, d ] , berarti kode optimal kuat tersebut telah gagal dikonstrusi. Dalam hal ini, harus dilakukan rekonstruksi
35
ulang dengan strategi memilih kode dasar yang lain yang berpeluang besar dapat diperluas menjadi kode optimal kuat C . 3.3.2
Struktur data himpunan
Untuk membangun metode konstruksi yang efisien, perlu didefiiniskan struktur data yang baru, yang merepresentasikan ruang vektor F2n , yaitu himpunan kuasa atas A = {0,1, 2,..., n − 1} . Untuk itu, perlu didefinisikan korespondensi satusatu antara suatu vektor di Fqn dengan suatu himpunan bilangan bulat tak negatif. Misalkan diberikan x ∈ F2n sembarang, katakanlah x = ( x0 , x1 , x2 ,..., xn −1 ) , dengan xi ∈ {0,1} , maka x akan direpresentasikan dalam bentuk himpunan dengan aturan/cara sebagai berikut. -
Definisikan A = {Z , n} , dengan Z = {
},
-
Jika xi = 1 , maka Z = Z ∪ i , i = 0,1, 2,..., n − 1 .
Maka, x akan sama dengan A (dalam representasi himpunan). Sebagai contoh: -
x = ( 0, 0, 0, 0 ) ↔ A = {{ } , 4} .
-
x = (1, 0,1,1, 0 ) ↔ A = {{0, 2, 3} , 5} .
Selanjutnya, operasi penjumlah dalam representasi himpunan didefinisikan sebagai operasi xor/selisih simetri, yang akan dilambangkan dengan ⊕ . Sebagai contoh, misalkan
A1 = {{1,3, 5} , 6} , dan
A2 = {{0,3, 4} , 6} , maka
A1 + A2 =
{{0,1, 4,5} , 6} , atau dalam representasi vektor biner, ( 0,1, 0,1, 0,1) + (1, 0, 0,1,1, 0 ) = (1,1, 0, 0,1) .
Akan ditunjukkan bahwa dengan struktur data yang baru tersebut, ruang vektor biner dengan operasi penjumlahan yang direpresentasikan dengan himpunan bilangan bulat dengan operasi xor juga merupakan grup. Dengan kata lain, perlu ditunjukkan -
⊕ bersifat asosiatif,
-
ada unsur identitas (I),
-
setiap
anggotanya
A ⊕ A' = I .
punya
inverse,
( ∀A ∈ F )( ∃A ' ∈ F ) sehingga n 2
n 2
36
Akan dibuktikan ⊕ bersifat asosiatif. Misalkan diberikan 3 vektor biner (dalam representasi himpunan) dengan panjang n sembarang, yaitu A1 , A2 , A3 , dengan
A j = {{a0 , a1 ,..., ak } , n} ,
ai ∈{0,1, 2,...n − 1}
dan
k ≤ n −1.
Akan
ditunjukkan ( A1 ⊕ A2 ) ⊕ A3 = A1 ⊕ ( A2 ⊕ A3 ) . Ambil sembarang unsur pada A1 , misalkan yang diambil adalah digit ke- l . Selanjutnya, ambil unsur pada A2 dan
A3 di urutan digit yang sama. Misalkan unsurnya adalah x , y , dan z . Dengan menggunakan tabel kebenaran, dapat dilihat bahwa untuk sembarang unsur di A1 ,
A2 , dan A3 (pada koordinat yang sama), ⊕ bersifat asosiatif. Tabel 1. Tabel kebenaran untuk sifat asosiatif pada operasi xor
x
y
z
(1) (2) (3) 1 1 1 1 0 0 0 0
1 1 0 0 1 1 0 0
1 0 1 0 1 0 1 0
(x ⊕ y)
( x ⊕ y) ⊕ z
( y ⊕ z)
x ⊕ ( y ⊕ z)
(5) ↔ (7)
(4)
(5)
(6)
(7)
(8)
0 0 1 1 1 1 0 0
1 0 0 1 0 1 1 0
0 1 1 0 0 1 1 0
1 0 0 1 0 1 1 0
1 1 1 1 1 1 1 1
Untuk menunjukkan adanya unsur identitas dan adanya invers, misalkan diberikan vektor biner (dalam representasi himpunan) dengan panjang n sembarang, yaitu A = {{a0 , a1 ,..., ak } , n} , dengan ai ∈{0,1, 2,...n − 1} dan k ≤ n − 1 . I = {{ } , n} merupakan untuk identitas, karena I ⊕ A = A ⊕ I = A . Sebagai
contoh,
{{0, 2, 3} , 4} ⊕ {{ } , 4} = {{0, 2,3} , 4} .
Selanjutnya akan ditunjukkan ada
A ' sehingga A ⊕ A ' = I , karena A ⊕ A = I , maka pilih A ' = A . Oleh karena itu, setiap unsur di F2n memiliki invers, yaitu dirinya sendiri. Selanjutnya suatu matriks biner juga akan direpresentasikan sebagai list/daftar dari sejumlah himpunan bilangan bulat tak negatif. Misalkan diberikan matriks biner sembarang. karena suatu matriks dapat dianggap sebagai kumpulan vektor-vektor kolom atau sebagai kumpulan dari vektor-vektor baris, maka ada dua cara untuk mendefinisikan matriks dalam representasi himpunan, yaitu
37
sebagai representasi matriks baris jika matriks tersebut dianggap sebagai kumpulan vektor-vektor baris atau sebagai representasi matriks kolom jika matriks tersebut dianggap sebagai kumpulan vektor-vektor kolom. Apabila suatu matriks dianggap sebagai representasi matriks kolom, maka informasi tentang banyaknya baris diletakkan sebelum list vektor-vektor, sebaliknya jika suatu matriks dianggap sebagai representasi matriks baris, maka informasi tentang banyaknya kolom diletakkan setelah list dari vektor-vektor. Sebagai contoh,
⎡1 0 0 1 ⎤ misalkan diberikan matriks M = ⎢⎢0 1 1 1 ⎥⎥ . M dapat dianggap sebagai ⎢⎣1 1 1 0 ⎥⎦ representasi matriks baris, yaitu L1 = {{0,3} , {1, 2,3}{0,1, 2} , 3} atau sebagai representasi matriks kolom, yaitu L2 = {4, {0, 2} , {1, 2} , {1, 2} , {0,1}} . Dengan didefinisikannya struktur data yang baru tersebut, maka perlu disusun suatu program untuk melakukan perhitungan aritmatik aljabar matriks. 3.3.3
Algoritme Kostruksi
Pada bab-bab ini, akan dideskripsikan algoritme-algoritme yang diperlukan untuk mengontruksi suatu kode linear biner. 3.3.3.1 Algoritme tentang fungsi aritmetik aljabar matriks
Karena struktur data yang digunakan adalah struktur data khusus, maka perlu didefinisikan terlebih dahulu program-program tentang aritmatik aljabar matriks dalam representasi himpunan, sebagai berikut.
38
1. Menghitung penjumlahan dua vektor. Algoritme: Misalkan diberikan vektor x dan y, jumlah antara vektor x dan y dapat dihitung dengan mencari selisih simetrik antara kedua himpunan tersebut.
2. Mengubah tampilan dari matriks kolom ke bentuk matriks baris (atau sebaliknya). Algoritme: Misalkan diberikan matriks B berukuran m×n (dalam representasi kolom). Untuk mengubah tampilan menjadi matriks baris, dapat dilakukan dengan cara sebagai berikut. 1. Untuk setiap himpunan vektor-vektor kolom yang ada di dalam list, periksa apakah ada bilangan i, i = 0, 1, 2, …, m-1. 2. Jika ada, simpan indeks (urutan himpunan dalam list), yang dimulai dari nol, ke dalam himpunan baru, katakanlah himpunan si. 3. Akan diperoleh diperoleh m himpunan vektor baris. Untuk mengubah tampilan dari matriks baris ke matriks kolom, dapat dilakukan dengan cara yang serupa.
3. Menentukan transpose dari suatu matriks. Algoritme: Misalkan diberikan matriks B dalam representasi kolom. Untuk menentukan transpose dari matriks B, tampilan matriks B diubah menjadi representasi matriks baris. Selanjutnya, informasi tentang banyaknya kolom dipindahkan ke bagian depan list (banyaknya kolom menjadi banyaknya baris).
39
4. Menukar baris ke- i dan ke- j . Algoritme: Misalkan diberikan matriks B dengan ukuran m×n dalam representasi kolom. Misalkan yang akan ditukar adalah baris ke-i dan ke-j, dengan indeksnya dimulai dari 0 sampai dengan m-1. Untuk menukar, dilihat semua himpunan yang ada di dalam list, apabila ada himpunan yang mengandung unsur i dan j atau tidak mengandung kedua unsur tersebut, maka himpunan tersebut dibiarkan (tidak berubah). Namun apabila himpunan tersebut mengandung unsur i saja, maka unsur tersebut diganti dengan unsur j. Begitu pula sebaliknya.
5. Menambahkan baris ke- j dengan baris ke- i di baris ke-j. Algoritme: Misalkan diberikan matriks B dengan ukuran m×n dalam representasi kolom. Misalkan misalkan baris ke-i akan ditambahkan ke dalam baris i. dengan indeksnya dimulai dari 0 sampai dengan m-1. Untuk semua himpunan dalam list, apabila di dalam himpunan tersebut terkandung unsur i dan j, maka unsur j dihapus. Apabila hanya ada unsur j, atau tidak mengandung kedua unsur tersebut, maka himpunan tersebut dibiarkan (tidak berubah). Namun, apabila hanya mengandung unsur i, maka unsur j ditambahkan pada himpunan tersebut.
6. Menentukan bentuk kanonik dari suatu matriks. Algoritme: Misalkan diberikan matriks A dengan ukuran m×n. Akan dicari bentuk kanonik dari matriks A. Dilakukan OBD (menukar baris, menambahkan suatu baris dengan baris yang lain, dan mengalikan suatu baris dengan skalar) pada matriks A sehingga anak matriks persegi m×m di bagian kiri matriks merupakan matriks identitas.
40
7. Menjumlahkan dua matriks. Algoritme: Misalkan diberikan matriks A dan matriks B (dalam representasi yang sama, misalkan representasi baris). Untuk menjumlahkan dua matriks, dij Jumlahkan vektor-vektor dari A dan vektor-vektor dari B (dalam posisi yang sama).
8. Menentukan hasil kali skalar (dot product) dari dua vektor. Algoritme: Misalkan diberikan vektor x dan y. dot product dari x dan y dapat dihitung dengan menghitung banyaknya unsur dari irisan antara himpunan x dan y, yang selanjutnya dimodulokan dengan bilangan 2.
9. Mengalikan matriks A berukuran m × n dengan matriks B berukuran n × p (A dan B dalam representasi kolom). Algoritme: Misalkan diberikan matriks A dan B. Langkah-langkah untuk mengalikan kedua matriks tersebut adalah: 1. Mengubah format matriks A ke dalam representasi matriks baris. 2. Untuk setiap vektor yang ada pada matriks A, dilakukan hasil kali skalar dengan vektor-vektor matriks B. Selanjutnya, disimpan indeksnya pada himpunan baru, misalkan s. 3. Setelah diperoleh sebanyak p himpunan s, dikumpulkan jadi satu ke dalam suatu list.
10. Menambahkan satu baris vektor v ke matriks B di posisi/baris terakhir. (B dalam representasi baris). Algoritme: Misalkan diberikan matriks B dan vektor v. untuk menambahkan v ke dalam baris terakhir matriks B, ditambahkan himpunan vektor v pada list dari vektor-vektor baris B di posisi terakhir.
41
11. Menghapus baris ke-i pada matriks B. (B dalam representasi kolom). Algoritme: Misalkan diberikan matriks B. Untuk menghapus baris ke-i, dihapus angka i1 pada list dari vektor-vektor kolom B.
3.3.3.2 Algoritme tentang pelacakan kode linear biner
Setelah dibangun program-program dasar untuk proses aritmatik aljabarnya, selanjutnya akan dikonstruksi program pelacakan kode linear biner. Berikut diberikan deskripsi singkat tentang program-program tersebut. 1. Mengubah matriks generator yang sudah dalam bentuk standar menjadi matriks cek paritas (dalam representasi matriks kolom). Algoritme: Diberikan kode linear
dengan matriks generator
matriks cek paritas untuk kode linear
. Maka,
.
adalah
2. Mengkoding suatu pesan p menjadi vektor kata kode c menggunakan matriks generator G , G dalam bentuk umum. Algoritme: Diberikan matriks generator vektor pesan matriks
dan vektor pesan
. Kata kode
dapat diperoleh dengan cara mengalikan vektor
untuk dengan
.
3. Mengkoding suatu vektor pesan p menjadi kata kode c menggunakan matriks B , di mana G = [ I k | B] merupakan matriks generator. Algoritme: Diberikan matriks
dan vektor pesan
. Kata kode
dapat diperoleh dengan cara menghitung vektor disusun vektor
.
untuk vektor pesan , kemudian
42
4. Menentukan jarak Hamming dari dua vektor. Algoritme: Misalkan diberikan dua vektor x dan y. Untuk menentukan jarak Hamming antara vektor x dan y, ditambahkan x dan y (dengan operasi
). Misalkan
hasilnya adalah vektor z. Selanjutnya, jarak antara vektor x dan y adalah banyaknya unsur dari vektor z. dengn kata lain, banyaknya unsur “1” di vektor z.
5. Menentukan bobot tak-nol dari suatu kode berdasakan matriks generatornya. Algoritme: Untuk menentukan bobot tak nol dari suatu kode berdasarkan matriks generatornya, perlu dicari semua kata kode yang ada dalam kode tersebut dengan cara menghitung
, dengan
adalah dimensi dari
kode tersebut. Selanjutnya dihitung bobot Hamming (atau jarak Hamming) dari setiap dua vektor yang berbeda.
6. Menentukan list dari semua kombinasi
j
vektor dari matriks B
(representasi baris), dengan j = 1, 2, 3,..., t , dan t = min {k , d −1} . Algoritme: List dari semua kombinasi j vektor dari matriks B dapat diperoleh dengan cara: 1. Menyimpan list 1 vektor (list awal dari matriks B) 2. Untuk memperoleh list dari semua kombinasi 2 vektor, dijumlahkan setiap dua vektor yang berbeda dalam list 1 vektor. Hasilnya digabungkan dengan hasil poin 1. 3. Dengan cara yang serupa, untuk memperoleh list dari semua kombinasi j vektor, di jumlahkan setiap j vektor yang berbeda dalam list 1 vektor. Selanjutnya, gabungkan hasilnya dalam list yang sebelumnya.
43
k 7. Melacak/mencari satu vektor baris x dalam F2 yang bisa ditambahkan ke
matriks B berdasarkan teorema Gilbert-Vashamov. Algoritme: Misalkan diberikan vektor
, selanjutnya diuji bobot vektor
sedemikian sehingga semua
kombinasi
, dengan vektor
. Apabila
baris
di
adalah anggota dari
untuk
,
dan
lulus uji, maka diperoleh satu vektor yang
dapat ditambahkan ke matriks
.
8. Menghimpun semua vektor-vektor baris anggota
F2k
yang bisa
ditambahkan ke matriks B. Algoritme: Misalkan diberikan matriks B yang merepresentasian kode linear biner dengan parameter
. Untuk menghimpun semua vektor-vektor baris
yang bisa ditambahkan ke matriks B, perlu di cek semua vektor di dalam
,
apakah bisa ditambahkan atau tidak. Namun, untuk menghemat waktu komputasi, cukup dipilih vektor vektor biner yang memiliki
, dengan unsur satu dengan
merupakan vektor biner yang memiliki
merupakan dan
unsur satu dengan
yang memenuhi ketaksamaan v adalah banyaknya unsur satu dari baris pertama pada matriks B.
, dengan
44
9. Menguji apakah dua vektor x dan y bisa ditambahkan ke matriks B berdasarkan teorema Gilbert-Varshamov. Algoritme: Misalkan
adalah himpunan satu vektor yang dapat ditambahkan ke
matriks
. Dari
, dapat dicari pasangan dua vektor yang dapat
ditambahkan ke matriks
. Caranya adalah dengan menjumlahkan setiap
kemungkinan dua vektor yang berbeda yang ada di penjumlahannya adalah vektor
. Apabila bobot
. Misalkan hasil
lebih besar dari
proses dilanjutkan dengan menguji bobot vektor sehingga
, dengan
kombinasi
vektor baris di
Apabila vektor
untuk
,
sedemikian
adalah anggota dari semua , dan
.
tersebut lulus uji, maka diperoleh dua vektor yang dapat
ditambahkan ke matriks
.
10. Menghimpun semua pasangan vektor-vektor x dan y yang bisa ditambahkan ke B. Algoritme: Misalkan matriks
adalah himpunan satu vektor yang dapat ditambahkan ke . Untuk mencari semua pasangan 2 vektor yang bisa ditambahkan
ke matriks B, perlu dicek semua 2 vektor
yang berbeda.
45
11. Menguji apakah m+1 vektor bisa ditambahkan ke matriks B Algoritme: Misalkan
adalah himpunan dari kumpulan
vektor anggota
dapat ditambahkan ke matriks
. Dari
bisa ditambahkan ke matriks
dengan cara mencari dua anggota
jika digabung memiliki
, dapat dicari
yang
vektor yang yang
vektor yang berbeda. Misalkan dua kumpulan
vektor tersebut adalah
dan
. Selanjutnya dilakukan pengujian
sebagai berikut. 1.
Menguji apakah kedua vektor anggota ditambahkan ke matriks
2.
dapat
.
Menguji apakah kedua vektor anggota ditambahkan dengan setiap
yang jika
vektor dalam
bisa ditambahkan ke matriks
,
.
Untuk menguji j vektor bisa ditambahkan ke matriks B, caranya adalah dengan menjumlahkan j vektor tersebut, misalkan hasil penjumlahannya adalah vektor
. Apabila bobot
lebih besar dari
dilanjutkan dengan menguji bobot vektor , dengan vektor baris di
.
sedemikian sehingga
adalah anggota dari semua kombinasi
untuk
tersebut lulus uji, maka diperoleh matriks
, proses
, dan
. Apabila vektor vektor yang dapat ditambahkan ke
46
12. Menghimpun semua m+1 vektor yang bisa ditambahkan ke matriks B berdasarkan teorema Gilbert-Varshamov. Algoritme: Analog dengan algoritme untuk menghimpun semua pasangan 2 vektor, Untuk menghimpun semua m+1 vektor, perlu di cek semua himpunan dari kumpulan
13. Mereduksi
vektor anggota
himpunan
yang dapat ditambahkan ke matriks
pasangan
vektor-vektor
baris
.
dengan
cara
membuang pasangan vektor yang saling ekivalen. Algoritme: Misalkan dari hasil eksplorasi diperoleh
matriks
. Selanjutnya, setiap dua
pasang matriks tersebut di cek, apakah saling ekivalen atau tidak, apabila kedua matriks tersebut saling ekivalen, maka salah satunya dapat dihapus, sehingga nantinya hanya diperoleh matriks-matriks
yang tidak saling
ekivalen.
Implementasi dari algoritme-algoritme di atas dapat dilihat pada Lampiran 2. Algoritme tersebut ditulis dalam bahasa pemograman MAPLE. 3.3.4
Eksplorasi kode linear untuk jarak minimum 9
Pada subbab ini, akan diceritakan proses diperolehnya (konstruksi) kode optimal kuat dengan jarak minimum 9. Konstruksi kode linear tersebut dilakukan dengan menggunakan software MAPLE. Dari Tabel Brouwer, dapat dilihat bahwa untuk d = 9 , kode
[14, 2,9] , [17,3,9] , [ 20,5,9] , [ 23,7,9] ,
dan
[ 27,10,9]
merupakan kode optimal kuat. Konstruksi dimulai dari kode [14, 2,9] , yaitu dengan mendefinisikan matriks B yang berukuran 2 ×12 sebagai berikut
⎛1 1 1 1 1 1 1 1 0 0 0 0 ⎞ B=⎜ ⎟ ⎝1 1 1 1 0 0 0 0 1 1 1 1 ⎠ Matriks tersebut dipakai sebagai matriks dasar untuk diperluas menjadi matriks B1 yang berukuran 3 ×14 (yang mendefinisikan kode [17,3,9] ) dengan cara menambahkan dua vektor kolom nol pada B , dilanjutkan dengan menambah satu vektor baris berukuran 13 bit yang memenuhi syarat strategi berdasarkan
47
algoritme konstruksi. Dari hasil komputasi yang dilakukan, diperoleh 8 kode linear dengan parameter [17,3,9] yang tidak saling ekivalen, salah satunya:
⎛1 1 1 1 1 1 1 1 0 0 0 0 0 0 ⎞ ⎜ ⎟ B1 = ⎜1 1 1 1 0 0 0 0 1 1 1 1 0 0 ⎟ ⎜1 1 1 0 1 1 1 0 1 1 1 0 1 1 ⎟ ⎝ ⎠ Selanjutnya, B1 akan diperluas ke matriks yang berukuran 5 × 15 (yang mendefinisikan kode [ 20,5,9] ) dengan cara: 1. Menambahkan satu vektor kolom nol pada B1 , 2. Mencari dua vektor baris berukuran 15 bit yang dapat ditambahkan ke B1 berdasarkan algoritme konstruksi. Dari hasil eksplorasi, diperoleh 128 matriks yang tidak saling ekivalen yang merepresentasikan kode liner dengan parameter [ 20,5,9] . Salah satunya adalah: ⎛1 ⎜ ⎜1 B2 = ⎜1 ⎜ ⎜1 ⎜1 ⎝
1 1 1 1 1 1 1 0 0 0 0 0 0 0⎞ ⎟ 1 1 1 0 0 0 0 1 1 1 1 0 0 0⎟ 1 1 0 1 1 1 0 1 1 1 0 1 1 0⎟ . ⎟ 1 0 0 1 1 0 0 1 0 0 1 1 0 1⎟ 0 1 0 1 0 0 1 0 1 0 0 1 1 1 ⎟⎠
Dengan cara yang serupa, yaitu dengan menambahkan satu vektor nol pada kolom terakhir dari B2 dan mencari dua vektor baris yang bisa ditambahkan ke
B2 , diperoleh 5040 kode linear dengan parameter [ 23,7,9] yang tidak saling ekivalen. Salah satunya adalah ⎛1 ⎜ ⎜1 ⎜1 ⎜ B3 = ⎜ 1 ⎜1 ⎜ ⎜1 ⎜0 ⎝
1 1 1 1 1 1 1 0 0 0 0 0 0 0 0⎞ ⎟ 1 1 1 0 0 0 0 1 1 1 1 0 0 0 0⎟ 1 1 0 1 1 1 0 1 1 1 0 1 1 0 0⎟ ⎟ 1 0 0 1 1 0 0 1 0 0 1 1 0 1 0⎟ . 0 1 0 1 0 0 1 0 1 0 0 1 1 1 0⎟ ⎟ 0 0 1 0 0 1 0 0 0 1 0 1 1 1 1⎟ 1 1 0 1 0 1 0 0 0 1 1 1 0 0 1 ⎟⎠
Dari matriks B3 , akan dikonstruksi kode linear dengan parameter [ 27,10,9] . Setelah ditambahkan satu vektor nol pada kolom terakhir dari matriks B3 dan
48
dicari tiga vektor baris yang bisa ditambahkan, diperoleh delapan matriks yang berukuran 10 × 17 yang tidak saling ekivalen. Salah satunya adalah
⎛1 ⎜ ⎜1 ⎜1 ⎜ ⎜1 ⎜1 B4 = ⎜ ⎜1 ⎜0 ⎜ ⎜0 ⎜0 ⎜ ⎜1 ⎝
1 1 1 1 1 1 1 0 0 0 0 0 0 0 0 0⎞ ⎟ 1 1 1 0 0 0 0 1 1 1 1 0 0 0 0 0⎟ 1 1 0 1 1 1 0 1 1 1 0 1 1 0 0 0⎟ ⎟ 1 0 0 1 1 0 0 1 0 0 1 1 0 1 0 0⎟ 0 1 0 1 0 0 1 0 1 0 0 1 1 1 0 0⎟ ⎟. 0 0 1 0 0 1 0 0 0 1 0 1 1 1 1 0⎟ 1 1 0 1 0 1 0 0 0 1 1 1 0 0 1 0⎟ ⎟ 1 0 0 1 0 1 1 1 1 0 0 1 0 1 1 1⎟ 0 1 1 1 1 1 0 1 1 0 1 0 1 1 0 1 ⎟⎟ 1 0 1 1 1 1 1 0 1 1 1 1 1 0 1 1 ⎟⎠
Setelah ditambahkan vektor nol pada kolom terakhir dari matriks B4 , akan dicari vektor-vektor baris yang dapat ditambahkan. Harapannya, ingin diperoleh matriks 14 × 18 yang merepresentasikan kode baru yang berparameter [32,14,9] , Namun hasil komputasi menunjukkan bahwa matriks B4 yang telah ditambahkan vektor kolom hanya dapat diperluas menjadi matriks yang berukuran 12 × 17 yang merepresentasikan kode dengan parameter [30,12,9] . 3.3.5
Eksplorasi kode linear untuk jarak minimum 11
Identik dengan eksplorasi untuk kode dengan jarak minimum 9, konstruksi kode optimal kuat untuk d = 11 dilakukan dengan menggunakan software MAPLE dan dimulai dari kode optimal dengan dimensi dua, yang direpresentasikan dengan matriks
⎛1 1 1 1 1 1 1 1 1 1 0 0 0 0 0 ⎞ B=⎜ ⎟. ⎝1 1 1 1 1 0 0 0 0 0 1 1 1 1 1 ⎠ Karena kode optimal kuat berikutnya berparameter [ 20,3,11] , matriks B perlu ditambahkan dua vektor nol sebelum dicari satu vektor yang dapat ditambahkan sehingga diperoleh dengan parameter [ 20,3,11] . Hasil komputasi menunjukkan ada dua matriks yang tidak saling ekivalen yang merepresentasikan kode dengan parameter [ 20,3,11] , salah satunya adalah:
49
⎛1 1 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0 ⎞ ⎜ ⎟ B1 = ⎜1 1 1 1 1 0 0 0 0 0 1 1 1 1 1 0 0 ⎟ . ⎜1 1 1 0 0 1 1 1 0 0 1 1 1 0 0 1 1 ⎟ ⎝ ⎠ Selanjutnya, dengan menambahkan satu vektor nol pada kolom terakhir dari
B1 dan mencari dua vektor baris yang bisa diambahkan, diperoleh 128 macam matriks yang merepresentasikan kode linear dengan parameter [ 23,5,11] . Salah satunya adalah:
⎛1 ⎜ ⎜1 B2 = ⎜1 ⎜ ⎜1 ⎜1 ⎝
1 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0⎞ ⎟ 1 1 1 1 0 0 0 0 0 1 1 1 1 1 0 0 0⎟ 1 1 0 0 1 1 1 0 0 1 1 1 0 0 1 1 0⎟ . ⎟ 1 0 1 0 1 0 0 1 1 1 1 0 1 0 1 0 1⎟ 0 1 0 1 1 1 0 1 0 1 0 0 1 1 0 1 1 ⎟⎠
Dengan cara yang serupa untuk memperoleh kode dengan parameter
[ 23,5,11] , yaitu dengan menambahkan satu vektor nol pada kolom terakhir dari matriks B2 dan mencari dua vektor baris yang bisa ditambahkan, diperoleh 4032 macam matriks yang merepresentasikan kode linear dengan parameter [ 26,7,11] . Salah satunya adalah: ⎛1 ⎜ ⎜1 ⎜1 ⎜ B3 = ⎜ 1 ⎜1 ⎜ ⎜1 ⎜0 ⎝
1 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0 0⎞ ⎟ 1 1 1 1 0 0 0 0 0 1 1 1 1 1 0 0 0 0⎟ 1 1 0 0 1 1 1 0 0 1 1 1 0 0 1 1 0 0⎟ ⎟ 1 0 1 0 1 0 0 1 1 1 1 0 1 0 1 0 1 0⎟ . 0 1 0 1 1 1 0 1 0 1 0 0 1 1 0 1 1 0⎟ ⎟ 0 1 0 0 0 1 1 0 1 1 0 1 0 1 0 0 1 1⎟ 0 1 1 1 0 0 1 1 1 1 0 0 1 1 1 0 0 1 ⎟⎠
Selanjutnya, B3 akan diperluas menjadi matriks yang berukuran 11 × 20 yang merepresentasikan kode dengan parameter
[31,11,11]
dengan cara
menambahkan satu vektor nol pada kolom terakhir dari B3 dan mencari empat vektor yang dapat ditambahkan. Akan tetapi, dari hasil komputasi yang dilakukan, matriks tersebut hanya dapat diperluas menjadi matriks yang berukuran 8 × 20 , sehingga hanya diperoleh kode dengan parameter [ 28,8,11] . Gagalnya konstruksi
50
kode [31,11,11] disebabkan oleh pemilihan kode awal yang kurang baik, dalam kasus ini kode awal tersebut adalah kode [ 26,7,11] yang direpresentasikan oleh matriks B3 . Salah satu cara untuk mengatasi hal tersebut adalah dengan cara menghapus baris ke-3 dan ke-4 dari matriks B3 .Dilanjutkan dengan rekonstruksi ulang, yaitu dengan menambahkan vektor nol pada kolom terakhirnya. Kemudian dicari 6 vektor yang dapat ditambahkan, sehingga diperoleh empat matriks berukuran 11 × 20 yang tidak saling ekivalen yang merepresentasikan kode dengan parameter [31,11,11] . Salah satunya adalah
⎛1 ⎜ ⎜1 ⎜1 ⎜ ⎜1 ⎜0 ⎜ B4 = ⎜ 1 ⎜1 ⎜ ⎜1 ⎜0 ⎜ ⎜1 ⎜ ⎝1
1 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0⎞ ⎟ 1 1 1 1 0 0 0 0 0 1 1 1 1 1 0 0 0 0 0⎟ 0 1 0 1 1 1 0 1 0 1 0 0 1 1 0 1 1 0 0⎟ ⎟ 0 1 0 0 0 1 1 0 1 1 1 1 0 1 0 0 1 1 0⎟ 0 1 1 1 0 0 1 1 1 1 0 0 1 1 1 0 0 1 0⎟ ⎟ 1 1 1 0 1 0 0 0 0 1 0 0 0 0 0 1 1 1 1⎟ . 0 0 1 1 0 1 1 0 0 0 1 1 0 0 0 1 0 1 1⎟ ⎟ 0 0 0 1 0 0 0 0 1 1 1 0 1 0 1 1 1 1 0⎟ 1 1 0 1 1 0 1 0 0 0 0 1 0 1 1 0 0 1 1 ⎟⎟ 1 1 0 1 0 0 1 1 0 1 1 0 0 0 1 1 0 0 1⎟ ⎟ 0 1 0 1 1 1 1 1 1 0 1 1 1 0 1 0 1 1 1⎠
Pemilihan baris dan banyaknya baris yang dihapus berkaitan dengan peluang perluasan matriks dasar tersebut, namun tidak ada aturan yang pasti mengenai penghapusan tersebut agar diperoleh kode dengan dimensi terbesar. Yang pasti hanyalah peluang untuk memperluas kode dengan menghapus dua baris lebih besar jika dibandingkan dengan menghapus satu baris, tapi waktu komputasinya menjadi jauh lebih lambat. Dengan cara yang serupa, kode linear dengan parameter
[33,12,11]
diperoleh dengan menghapus beberapa baris dari matriks B4 , dan dilakukan rekonstruksi ulang. Hasil komputasi menunjukkan ada 2 matriks yang tidak saling ekivalen, salah satunya
51
⎛1 ⎜ ⎜0 ⎜1 ⎜ ⎜1 ⎜0 ⎜ ⎜1 B5 = ⎜ 1 ⎜ ⎜1 ⎜1 ⎜ ⎜0 ⎜ ⎜0 ⎜0 ⎝
0 1 0 1 1 1 0 1 0 1 0 0 1 1 0 1 1 0 0 0⎞ ⎟ 0 1 1 1 0 0 1 1 1 1 0 0 1 1 1 0 0 1 1 0⎟ 0 0 1 1 0 1 1 0 0 0 1 1 0 0 0 1 0 1 1 0⎟ ⎟ 0 0 1 1 0 1 1 0 0 0 1 1 0 0 0 1 0 1 1 0⎟ 1 1 0 1 1 0 1 0 0 0 0 1 0 1 1 0 0 1 1 0⎟ ⎟ 1 1 0 1 0 0 1 1 0 1 1 0 0 0 1 1 0 0 1 0⎟ . 0 1 0 1 1 1 1 1 1 0 1 1 1 0 1 0 1 1 1 0⎟ ⎟ 1 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0⎟ 1 1 0 0 0 1 1 0 0 0 0 0 1 1 0 1 0 0 1 1 ⎟⎟ 1 1 0 1 0 0 1 0 1 0 1 0 1 0 1 0 1 0 0 1⎟ ⎟ 1 0 1 1 0 0 0 0 1 1 1 1 0 0 0 1 1 0 1 1⎟ 1 0 1 0 1 1 1 1 1 0 1 0 1 0 0 1 1 1 1 1 ⎟⎠
Agar dapat memperoleh kode baru yang belum diperoleh orang lain, yaitu kode dengan parameter [37,15,11] , matriks B5 harus dapat diperluas menjadi matriks berukuran 15 × 22 . Namun, matriks tersebut gagal dikonstruksi, dari hasil komputasi yang dilakukan, hanya diperoleh kode dengan parameter [36,14,11] yang direpresentasikan oleh matriks yang berukuran 14 × 22 sebagai berikut.
⎛1 ⎜ ⎜1 ⎜0 ⎜ ⎜1 ⎜1 ⎜ ⎜1 ⎜1 B6 = ⎜ ⎜0 ⎜0 ⎜ ⎜1 ⎜ ⎜1 ⎜0 ⎜ ⎜1 ⎜1 ⎝
1 1 1 0 1 0 0 0 0 1 0 0 0 0 0 1 1 1 1 0 0⎞ ⎟ 0 0 1 1 0 1 1 0 0 0 1 1 0 0 0 1 0 1 1 0 0⎟ 1 1 0 1 1 0 1 0 0 0 0 1 0 1 1 0 0 1 1 0 0⎟ ⎟ 1 1 0 1 0 0 1 1 0 1 1 0 0 0 1 1 0 0 1 0 0⎟ 0 1 0 1 1 1 1 1 1 0 1 1 1 0 1 0 1 1 1 0 0⎟ ⎟ 1 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0⎟ 1 1 0 0 0 1 1 0 0 0 0 0 1 1 0 1 0 0 1 1 0⎟ ⎟. 1 1 0 1 0 0 1 0 1 0 1 0 1 0 1 0 1 0 0 1 0⎟ 1 0 1 0 1 1 1 1 1 0 1 0 1 0 0 1 1 1 1 1 0 ⎟⎟ 1 1 1 0 0 0 0 0 1 0 0 0 1 1 1 0 0 1 0 0 1⎟ ⎟ 1 0 0 0 0 0 1 1 1 1 0 1 0 1 1 0 0 0 0 1 0⎟ 1 1 0 1 1 1 0 0 0 1 0 0 1 0 1 1 0 0 0 0 1⎟ ⎟ 1 0 1 1 0 0 0 1 1 0 1 1 0 1 0 1 0 0 0 0 1⎟ 0 1 1 1 0 0 0 0 1 1 1 1 1 0 1 1 1 0 1 0 1 ⎟⎠
52
3.3.6
Fakta tentang komputasi untuk dua representasi data yang berbeda
Dalam melakukan konstruksi kode linear biner, dapat dilakukan dengan dua representasi data yang berbeda, yaitu dengan representasi himpunan dan dengan representasi matriks/vektor. Proses pengerjaan dengan representasi himpunan delakukan dengan menggunakan software MAPLE, sedangkan untuk representasi matriks dilakukan dengan software MATLAB Dari kedua representasi tersebut, dibandingkan waktu komputasinya dengan PC berprosessor Intel® Core™ i3, 2.93 GHz, 6 GB RAM. Dalam melakukkan perbandingan ini, diambil contoh untuk d = 11 . Berikut hasil perbandingan komputasi yang dilakukan. Tabel 2. Perbandingan komputasi antara dua representasi data
Kode Basis
3.4
Waktu eksekusi (detik)
Kode yang dihasilkan
Himpunan
Matriks
[17, 2,11]
[ 20,3,11]
0.787
36.917
[ 20,3,11]
[ 23,5,11]
219.590
1985.293
[ 23,5,11]
[ 26,7,11]
25.156
938.301
Hasil yang Diperoleh
Dari eksplorasi dengan menggunakan software MAPLE, telah berhasil dikonstruksi kode optimal sebagai berikut. Tabel 3. Hasil konstruksi untuk kode untuk d = 9 dan d = 11
Jarak Minimal
Panjang dan Dimensi dari Suatu Kode - [ n, k ]
d =9 [14, 2]
d = 11 [17,2]
[17,3] [ 20,5] [ 23,7] [ 27,10]
[ 20,3] [ 23,5] [ 26,7] [31,11] [33,12]
-
53
Dari Tabel Brouwer, dapat diketahui bagaimana cara mengontruksi suatu kode pada saat pertama kali ditemukan. Pada umumnya, kode-kode tersebeut diperoleh dengan cara menggabungkan 2 kode yang memiliki dimensi yang sama. Sebagai contohnya, kode [14, 2,9] diperoleh dengan cara menggabungkan kode
[ 2, 2,1]
dan kode [12, 2,8] . Begitu pula kode [17,3,9] , kode tersebut diperoleh
dengan cara menggabungkan kode
[3,3,1]
dan kode
[13,3,8] .
Selain
penggabungan, suatu kode juga dapat diperoleh dengan cara memotong kode yang lebih besar, seperti untuk memperoleh kode [ 26,7,11] , yang diperoleh dengan cara: 1. mengontruksi kode
[50,8, 23]
dengan memotong (puncturing)
matriks generator dari kode [51,8, 24] di kolom ke 51. 2. mengontruksi kode
[ 27,7,12]
dengan memotong (puncturing)
matriks generator dari kode [51,8, 24] di kolom ke 1, 9, 13, 14, 16, 19, 21, 22, 25, 26, 28, 29, 30, 31, 34, 35, 36, 38, 39, 42, 45, 46, 50. 3. mengontruksi kode
[ 26,7,11]
dengan memotong (puncturing)
matriks generator dari kode [ 27,7,12] di kolom ke 27. Kelebihan dari metode konstruksi tersebut adalah lebih mudah dan lebih cepat, terutama untuk kode dengan dimensi besar. Namun, jika dibandingkan dengan metode konstruksi yang dilakukan pada penelitian ini, metode tersebut memiliki kelemahan, yaitu tidak dapat mengoleksi kode-kode yang memiliki parameter yang sama sebanyak-banyaknya. Sebagai contoh, diperoleh 4048 kode dengan parameter [ 27,7,11] yang tidak saling ekivalen. Dari dari penelitian yang dilakukan, waktu komputasi dengan menggunakan struktur data himpunan jauh lebih cepat bila dibandingkan dengan menggunakan struktur data ruang vektor. Dua hal yang berpengaruh terhadap kecepatan tersebut adalah: 1. Program yang digunakan dalam struktur data himpunan lebih ramping, artinya, program tersebut didesain hanya untuk masalah ini.
54
2. Banyaknya memori yang digunakan akan berkurang jika menggunakan struktur data himpunan, karena sebagian besar dari himpunan dalam list memiliki
panjang
yang
kurang
dari
panjang
vektor
ketika
merepresentasikan suatu matriks biner. Dari hasil penelitian yang dilakukan, ternyata sangat sulit untuk memperbaiki batas bawah dari Tabel Brouwer. Salah satu faktor yang paling berpengaruh dalam ketidak berhasilan tersebut adalah faktor hardware, yaitu keterbatasan komputer yang digunakan.
4 4.1
KESIMPULAN DAN SARAN
Kesimpulan
Dalam penelitian ini, telah dibuktikan teorema-teorema dasar yang cukup penting dalam konstruksi kode linear biner, terutama teorema Gilbert-Varshamov. Dari teorema Gilbert-Varshamov, disusun suatu teorema yang berkaitan langsung dengan konstruksi kode linear biner. Dari teorema baru ini, disusun algoritmealgoritme untuk mengontruksi kode linear biner. Selanjutnya,
algoritme-algoritme
tersebut
diimplementasikan
dalam
program MAPLE (dalam representasi himpunan) dan MATLAB (dalam representasi ruang vektor). Program ini diujicobakan untuk mengontruksi kode linear biner dengan jarak minimum 9 dan 11. Dalam praktiknya, konstruksi kode linear biner dengan representasi himpunan lebih efisien jika dibandingkan dengan menggunakan representasi matriks. Dalam penelitian ini, kode linear biner yang berhasil dikonstruksi hanya sampai k = 12, r = 18 untuk d = 9 dan sampai k = 14, r = 22 untuk d = 11. Namun demikian, sangat sulit untuk mengonstruksi semua kode optimal kuat, hal ini disebabkan antara lain oleh: 1. Keterbatasan komputer yang digunakan, sehingga tidak mungkin melacak semua kemungkinan kombinasi. 2. Pemilihan kode dasar (matriks B awal) yang kurang baik. 3. Program konstruksi yang masih belum sempurna. 4.2
Saran
Dalam penelitian ini, masih banyak kekurangan yang ada di dalamnya, diantaranya adalah: 1. Tidak semua kode linear optimal kuat dapat dikonstruksi, walaupun kode tersebut ada (telah dikonstruksi oleh orang lain). 2. Algoritme konstruksi, walaupun untuk representasi himpunan sudah cukup baik, masih dapat diperbaiki dalam hal kecepatan pelacakan kodekode linear biner, terutama untuk dimensi yang cukup besar. Untuk ke depannya, dapat diperbaiki algoritme konstruksi sehingga dapat dicari/dilacak kode dengan lebih cepat dan dapat mencakup kode linear yang
56
memiliki dimensi yang besar. Selain itu, dapat dikembangkan program untuk mengoleksi kode-kode atas Fq , untuk q > 2 .
DAFTAR PUSTAKA Brouwer AE. 1997. “Bounds on the size of linear codes” in Handbook of Coding Theory. Amsterdam: North-Holland Publishing Company. Hoffman DG et al. 1991. Coding Theory, the Essentials. New York: Marcel Dekker. Ling S. & Xing C, 2004. Coding Theory – A First Course. New York: Cambrige. MacWilliams FJ, Sloane NJA. 1981. The Theory of Error-Correcting Codes. Amsterdam: North-Holland Publishing Company. Grassl M. Code Tables: Bounds on the Parameters of Various Types of Codes. http://codetables.de/ [15 Juni 2011].
..
.
LAMPIRAN
.
61
Lampiran 1. Tabel Brouwer
Berikut diberikan cuplikan dari Tabel Brouwer. Terutama yang berkaitan dengan batas untuk d = 9 dan 11 . n/k 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30
1 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30
2 6 6 7 8 8 9 10 10 11 12 12 13 14 14 15 16 16 17 18 18 19 20
3 4 5 6 6 7 8 8 8 9 10 10 11 12 12 12 13 14 14 15 16 16 16
4 4 4 5 6 6 7 8 8 8 8 9 10 10 11 12 12 12 13 14 14 15 16
5 3 4 4 4 5 6 7 8 8 8 8 9 10 10 11 12 12 12 13 14 14 15
6 2 3 4 4 4 5 6 6 7 8 8 8 8 9 10 10 11 12 12 12 13 14
7 2 2 3 4 4 4 5 6 6 7 8 8 8 8 9 10 10 11 12 12 12 12
8 2 2 2 3 4 4 4 5 6 6 7 8 8 8 8 8 9 10 10 11 12 12
9 1 2 2 2 3 4 4 4 5 6 6 7 8 8 8 8 8 9 10 10 11 12
10
n/k 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43
11 9 10 11 12 12 12 12 12‐13 13‐14 14 14 15 16 16 16
12 8 9 10 10 11 12 12 12 12‐13 13‐14 14 14 14‐15 15‐16 16
13 8 8 9 10 10 10 11 12 12 12 12‐13 13‐14 14 14 15
14 8 8 8 8‐9 9‐10 10 10 11 12 12 12 12‐13 12‐14 13‐14 14
15 7 8 8 8 8‐9 9‐10 10 10 10‐11 11‐12 12 12 12‐13 12‐14 13‐14
16 6 7 8 8 8 8‐9 9‐10 10 10 10‐11 11‐12 12 12 12‐13 12‐14
17 6 6 7 8 8 8 8 8‐9 9‐10 10 10‐11 11‐12 12 12 12‐13
18 6 6 6 6‐7 7‐8 8 8 8 8‐9 9‐10 10 10‐11 11‐12 12 12
19 5 6 6 6 6‐7 7‐8 8 8 8 8‐9 9‐10 10 10‐11 11‐12 12
20 4 5 6 6 6 6‐7 7‐8 8 8 8 8‐9 9‐10 10 10 11
1 2 2 2 3 4 4 4 4 5 6 7 8 8 8 8 8 9 10 10 11
62
Lampiran 2. Program Konstruksi Kode
> AddV:=proc(S::set,T::set) return({op(S minus T),op(T minus S)}); end proc: Program 1. Menghitung penjumlahan dua vektor
> UbahMtxCR:=proc(A::list) local M,N::list, S::set, i,j,m,n::integer: M:=op(2,A): n:=nops(M): m:=op(1,A): N:=[]: for i from 0 to m-1 do S:={}: for j from 1 to n do if i in M[j] then S:={op(S),j-1}: end if: end do: N:=[op(N),S] end do: return([N,n]); end proc: Program 2. Mengubah tampilan dari matriks kolom ke bentuk matriks baris.
> UbahMtxRC:=proc(A::list) local B,N::list: B:=[op(2,A),op(1,A)]: N:=UbahMtxCR(B); return([N[2],N[1]]); end proc: Program 3. Mengubah tampilan dari matriks baris ke bentuk matriks kolom.
63
> TrpsC:=proc(A::list) local M,N::list, m::integer: M:=UbahMtxCR(A); m:=op(2,M): N:=op(1,M): return([m,N]); end proc: Program 4. Menentukan transpose dari suatu matriks.
> TukarR:=proc(i::integer,j::integer,A::list) local M::list, S,T::set, k,n::integer: M:=op(2,A): n:=nops(M): for k from 1 to n do S:=M[k] intersect {i,j}: if nops(S)=1 then T:=AddV(M[k],{i,j}): M:=subsop(k=T,M): end if: end do: return([op(1,A),M]); end proc: Program 5. Menukar baris ke-i dan ke-j.
> GantiB:=proc(i::integer,j::integer,A::list) local M::list, S::set, k,n::integer: M:=A: n:=nops(M): for k from 1 to n do if i in M[k] then S:=AddV(M[k],{j}): M:=subsop(k=S,M): end if: end do: return(M); end proc: Program 6. Menambahkan baris ke-j dengan baris ke-i di baris ke-j.
64
AddMtx:=proc(M::list,N::list) local A,B,H::list, m,n::integer: A:=op(2,M): B:=op(2,N): m:=op(1,M): n:=nops(B): if m<>op(1,N) or nops(A)<>n then return(false) end if: H:=[seq(AddV(A[i],B[i]),i=1..n)]: return([m,H]); end proc: Program 7. Menjumlahkan dua matriks.
DotV:=proc(S::set,T::set) local C::integer: C:=nops(S intersect T) mod 2; return(C); end proc: Program 8. Menentukan hasil kali skalar (dot product) dari dua vektor
MultMtx:=proc(M::list,N::list) local TA,A,B,H::list, S::set, m,n,i,j,k,p::integer: A:=op(2,M): B:=op(2,N): m:=op(1,M): n:=op(1,N): p:=nops(B): if n<>nops(A) then return(false) end if: TA:=(op(2,TrpsC(M))): H:=[]: for i from 1 to p do S:={}: for j from 1 to m do k:=DotV(TA[j],B[i]): if k=1 then S:={op(S),j-1}: end if: end do: H:=[op(H),S] end do: return([m,H]); end proc: Program 9. Mengalikan matriks A berukuran m × n dengan matriks B berukuran n × p
65
InkodG:=proc(P::set,G::list) local A,B,C::list, H::set, k,p::integer: k:=op(1,G): A:=TrpsC([k,[P]]): B:=MultMtx(A,G): C:=TrpsC(B): H:=op(C[2]): return(H); end proc: Program 10. Mengkoding suatu pesan p menjadi vektor kata kode c menggunakan matriks generator G , G dalam bentuk umum.
InkodS:=proc(P::set,B::list,k::posint) local S::set, r,i,s::integer: r:= nops(B): S:=P: for i from 1 to r do s:=DotV(P,B[i]): if s=1 then S:={op(S),k+i-1}: end if: end do: return(S); end proc: Program 11. Mengkoding suatu vektor pesan p menjadi kata kode c menggunakan matriks
B , di mana G = [ I k | B ] merupakan matriks generator.
HmDist:=proc(S::set,T::set) local C::set: C:=AddV(S,T); return(nops(C)); end proc: Program 12. Menentukan jarak Hamming dari dua vektor.
66
NonZeroWt:=proc(B::list) local Wt,C,P::set, i,r,m,k::integer: k:=B[1]: m:=2^k-1: Wt:={}: for i from 1 to m do P:=UbahDesKeSet(i); C:=InkodS(P,B[2],k); r:=nops(C): Wt:={op(Wt),r}: end do: return(Wt); end proc: Program 13. Menentukan bobot tak-nol dari suatu kode berdasakan matriks B.
KombinM:=proc(j::posint,M::list) local S,C,L,K,N::set, W::list, i,k::integer: K:= M[1]: k:=nops(K): L:={seq(i,i=1..k)}: N:=combinat[choose](L,j): W:=[]: for S in N do C:={}: for i in S do C:=AddV(C,K[i]): end do: W:=[op(W),C]: end do: return(W); end proc: Program 14. Menentukan list dari semua kombinasi j vektor dari matriks B (representasi baris) untuk suatu j, dengan j = 1, 2, 3, ..., t , dan t = min {k , d − 1}
67
AddVekM:=proc(V::set,M::list) local S::list, r::integer: S:=[op(M[1]),V]: r:=max(max(V),M[2]); return([S,r]); end proc: Program 15. Menambah satu baris vektor V ke matriks B (representasi baris) di posisi terakhir.
AddVekMX:=proc(H::set,M::list) local S::list, V::set: S:=M: for V in H do S:=AddVekM(V,S): end do: return(S); end proc: Program 16. Menambahkan beberapa vektor baris ke matriks B
DelVekM:=proc(i::posint,A::list) local M,T,N,B::list, m,n::integer: M:=op(2,A): n:=nops(M): m:=op(1,A): T:=TrpsC(A): N:=subsop(i=NULL,T[2]): B:=TrpsC([n,N]): return(B); end proc: Program 17. Menghapus baris ke-i pada matriks B. (B dalam representasi kolom).
68
ListKombM:=proc(M::list,t::posint) local L,T::list, j::integer: L:=[]: for j from 1 to t do T:=KombinM(j,M); L:=[op(L),T]: end do: return(L); end proc: Program 18. Menentukan list dari semua kombinasi j vektor dari matriks B (representasi baris) untuk semua j, dengan j = 1, 2, 3, ..., t , dan t = min {k , d − 1}
UjiAdd1VekM:=proc(d::posint,X::set,L::list) local K,T,H::list, i,j,b,n,h,k::integer: T:=subsop(1=NULL,L[1]): H:=subsop(1=T,L): h:=nops(H): for i from 1 to h do K:=H[i]: k:=nops(K): b:=d-1-i: for j from 1 to k do n:=HmDist(X,K[j]): if n
Program 19. Menguji apakah suatu vektor baris x dalam F2 bisa ditambahkan ke matriks B berdasarkan teorema Gilbert-Vashamov.
69
Lacak1VekM:=proc(d::posint,t::posint,r::posint,L::list) local
S,R,X,Y,Z,V,W::set,
B::list,
i,j,k,v,x::integer,
T::symbol: B:=L[1]: V:=B[1]: v:=nops(V): W:={seq(i,i=0..r-1)} minus V: for j from d-2 to t do for i from 0 to v do if (v+j-2*i)>=(d-1) then S:=combinat[choose](V,v-i): R:=combinat[choose](W,j-i): for Y in S do for Z in R do X:={op(Y),op(Z)}: T:=UjiAdd1VekM(d,X,L); if T=true then return(X); end if: end do: end do: end if: end do: end do: return(0); end proc: k
Program 20. Melacak/mencari satu vektor baris x dalam F2 yang bisa ditambahkan ke matriks B berdasarkan teorema Gilbert-Vashamov.
70
Kolek1VekM:=proc(d::posint,t::posint,r::posint,L::list) local
S,R,C,X,Y,Z,V,W::set,
B::list,
i,j,k,v,x::integer,
T::symbol: B:=L[1]: V:=B[1]: v:=nops(V): C:=[]: W:={seq(i,i=0..r-1)} minus V: for j from d-2 to t do for i from 0 to v do if (v+j-2*i)>=(d-1) then S:=combinat[choose](V,v-i): R:=combinat[choose](W,j-i): for Y in S do for Z in R do X:={op(Y),op(Z)}: T:=UjiAdd1VekM(d,X,L); if T=true then C:=[op(C),X]: end if: end do: end do: end if: end do: end do: return(C); end proc: k
Program 21. Menghimpun semua vektor-vektor baris anggota F2 yang bisa ditambahkan ke matriks B.
71
UjiAdd2VekM:=proc(d::posint,Z::set,L::list) local H,G::list, i,j,g,b,k,n,t::integer: if nops(Z)<(d-2) then return(false) end if; H:=L: k:=nops(L[1]): n:=min(d-3,k): for i from 1 to n do G:=H[i]: g:=nops(G): b:=d-2-i: for j from 1 to g do t:=HmDist(Z,G[j]): if t
72
Kolek2VekM:=proc(d::posint,H::list,L::list,c::posint) local X,Y,Z::set, C::list, h,i,j::integer, T::symbol: h:=nops(H): C:=[]: for i from 1 to (h-1) do X:=H[i]: for j from (i+1) to h do Y:=H[j]: Z:=AddV(X,Y): T:=UjiAdd2VekM(d,Z,L): if T=true then C:=[op(C),{X,Y}]: if nops(C)=c then C:=[op({op(C)})]: return(C); end if: end if: end do: end do: C:=[op({op(C)})]: return(C): end proc: Program 23. Menghimpun semua pasangan vektor-vektor x dan y yang bisa ditambahkan ke B.
73
UjiAddXVekM:=proc(x::posint,d::posint,U::set,L::list) local H,G::list, i,j,g,b,k,n,t::integer: if nops(U)<(d-x) then return(false) end if; H:=L: k:=nops(L[1]): n:=min(d-x-1,k): for i from 1 to n do G:=H[i]: g:=nops(G): b:=d-x-i: for j from 1 to g do t:=HmDist(U,G[j]): if t
74
KolekXVekM:=proc(x::posint,d::posint,H::list,L::list,c::posint) local X,Y,Z,U,V,S,A,B,R,N,K,W,Q::set, h,i,j,k,l::integer, T,T1::symbol, C::list: h:=nops(H): C:=[]: for i from 1 to (h-1) do X:=H[i]: for j from (i+1) to h do Y:=H[j]: Z:=X union Y: if nops(Z)=x then S:=X intersect Y: V:=Z minus S: A:=AddV(op(1,V),op(2,V)): T:=UjiAdd2VekM(d,A,L): if T=true then for k from 1 to (x-3) do N:=combinat[choose](S,k); T1:=true: for R in N while T1=true do B:=A: for K in R do B:=AddV(B,K): end do: T1:=UjiAddXVekM(2+k,d,B,L): end do: if T1=false then break; end if: end do: if T1=true then W:=op(S minus R): Q:=AddV(B,W): T:=UjiAddXVekM(x,d,Q,L): if T=true then C:=[op(C),{op(Z)}]: if nops(C)=c then C:=[op({op(C)})]: return(C): end if: end if: end if: end if: end if: end do: end do: C:=[op({op(C)})]: return(C): end proc: Program 25. Menghimpun semua m+1 vektor yang bisa ditambahkan ke matriks B berdasarkan teorema Gilbert-Varshamov.
75
ReduEkiX:=proc(H::list,M::list) local i,h::integer, A,L,G,K,R::list, Q,S::set: h:=nops(H): A:=H[1]: G:=AddVekMX(A,M): K:=UbahMtxRC(G): L:=sort(map(S->UbahSetKeDes(S),K[2])): R:=[A]: Q:={L}: for i from 2 to h do A:=H[i]: G:=AddVekMX(A,M): K:=UbahMtxRC(G): L:=sort(map(S->UbahSetKeDes(S),K[2])): S:={L} intersect Q: if S={} then Q:={op(Q),L}: R:=[op(R),A]: end if: end do: return(R): end proc: Program 26. Menghimpun semua m+1 vektor yang bisa ditambahkan ke matriks B berdasarkan teorema Gilbert-Varshamov.
IPB 2011
PUTRANTO HADI UTOMO O
G5510990421
