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.
