BAB IV HASIL DAN PEMBAHASAN
Pada BAB IV ini dibahas tentang permasalahan sebagai berikut: Kajian Teori yang digunakan dalam penelitian, Membahas Aritmetik Aljabar Matriks, Program-program Aritmetik Aljabar Matriks Biner, Program-program Pelacakan Kode Optimal Kuat, Algoritme Konstruksi kode optimal kuat, dan Konstruksi Kode Optimal Kuat Dengan Jarak Minimum 13 dan 15.
Kajian Teori Diberikan kode linear C dengan parameter [n, k, d]. Misalkan H merupakan matriks
cek
paritas
C= H
untuk
C.
Dari
definisi
matriks
cekparitas
, atau dengan kata lain C adalah himpunan solusi dari SPL = 0 ( C disebut dengan kernel H) . Hal ini karena baris-baris dari matriks H
merupakan basis untuk
, komplemen orthogonal bagi C.
Karena kode linear C merupakan kernel dari matriks cek paritasnya, maka mengkonstruksi suatu kode linear C sama dengan mengkonstruksi matriks cek paritasnya. Berikut ini adalah teorema yang berkaitan dengan konstruksi kode linear biner optimal kuat. Teorema 6 (The Gilbert-Varshamov bound) Diberikan kode linear C dengan parameter [n, k, d]. Jika ketaksamaan 1+
+
+
+
<
berlaku maka dapat dikonstruksi kode
dengan parameter [n+1, k+1, d]. Bukti : Misal diberikan kode linear yang memiliki parameter [n, k, d]. Berdasarkan Teorema 7, ada matriks cek paritas berordo (n – k) yang setiap d – 1 vektor dari vektor
. Jika ada vektor x
n, yaitu H =
adalah bebas linear dalam ruang yang bukan i kombinasi linear dari
vektor-vektor kolom H, untuk i = 1,2,…,d – 2 , maka
=
adalah
matriks cek paritas untuk kode linear yang memiliki parameter [n + 1, k + 1, d].
22
Hal ini karena
berordo (n – k )
( k + 1) dan setiap d – 1 vektor dari
adalah bebas linear dalam ruang vektor Jika
.
banyaknya kombinasi linear yang mungkin dari kolom-kolom
sehingga tidak ada d – 1 kolom yang bergantung linear lebih besar atau sama dengan jumlah vektor tak nol dalam
, maka
bukan matriks cek paritas
untuk kode linear dengan parameter [n + 1, k + 1, d]. Banyaknya vektor-vektor tan yang mungkin dipilih untuk x adalah
nol dalam
. Sedangkan
banyaknya kombinasi linear yang mungkin dari kolom-kolom +
+…+
adalah
, sehingga jika ada kode linear C dengan parameter
[n, k, d], dan persamaan 1 +
+
+…+
<
berlaku, maka
dapat dikonstruksi kode baru dengan parameter [n + 1, k + 1, d] berdasarkan kode linear C tersebut. Teorema 7 Diberikan kode linear C dengan panjang n. Jika H adalah matriks cek paritas dari suatu kode dengan panjang n, 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: Diberikan kode linear C dengan panjang n. 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. Teorema 8 Diberikan kode linear C dengan panjang n. Jika H adalah matriks cek paritas dari suatu kode dengan panjang n 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.
23
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 sarat berikut terpenuhi Ada vektor v ϵ
i.
dengan wt (v) = d sehingga
untuk setiap w ϵ
ii.
=
dengan wt (w) < d. (jika
=
maka w ϵ C. Kontradiksi dengan fakta bahwa wt (w) < d). Disisi lain, kedua sarat 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 yang bebas linear. Teorema 9 (The Singleton bound) Diberikan kode linear C. Jika C adalah kode dengan parameter [n, k, d] maka (n – k)
(d – 1).
Bukti : Misal diberikan kode kode linear C dengan parameter [n, k, d], maka kode linear C memiliki matriks cek paritas H berukuran (n – k) x n, sehingga rank (H) ≤ (n – k). Dari teorema 7, matriks H memiliki d – 1 kolom yang bebas linear. Sehingga rank (H) = (d – 1), dengan kata lain (d – 1) ≤ (d – k). Mengonstruksi suatu kode, sama artinya dengan mengonstruksi matriks cek paritas H. Berdasarkan teorema-teorema yang telah disebutkan di landasan teori, maka cukup dikonstruksi bentuk standar dari H, yaitu H =
. Dan atas
pertimbangan efisiensi komputasi, cukup dikonstruksi matriks B berukuran k
r.
Dari teorema Gilbert-Vashamov diturunkan suatu teorema baru yaitu Teorema 10. Dalam tulisan ini konstruksi kode linear biner optimal kuat dilakukan atas dasar Teorema 10 berikut ini. Teorema 10 Jika matriks B berukuran k
r dikonstruksi berdasarkan sifat-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 dimana s = min {d – 1 , k}, dan (d – 1) ≤ r,
24
maka
H=
dan G =
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 merupakan
disyaratkan teorema. Akan ditunjukan bahwa H =
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 ditunjukan bahwa kode linear C minimum ≥ d. Andaikan ada v v=
dimana
C dengan wt
d–i
< d dan ditulis
merupakan vektor pesan dengan wt
adalah vektor cek dengan wt i+j < d
memiliki jarak
wt
= i dan
= j , maka berlaku
< d–i
( 1.1 )
dan H
=
=
Karena wt wt
+
=
=
( 1.2 )
= i , dan berdasarkan sifat 2 dari Teorema 10, maka ≥ d–i
( 1.3 )
Dari persamaan 1.2 diperoleh bahwa ekivalen dengan wt
=
, sehingga persamaan 1.3
≥ d – i. Hal ini kontradiksi dengan persamaan 1.1.
Sehingga dapat disimpulkan bahwa kode linear C memiliki jarak minimum ≥ d. Dari Teorema 10 , 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 = 2, 3, …, s dengan s = min { d – 1 , k }, dan (d – 1) < r.
Membahas Aritmetik Aljabar Matriks Untuk kepentingan efisiensi komputasi maka data pada penelitian ini disajikan dalam representasi himpunan. Sebelum melakukan eksplorasi untuk mengonstruksi kode optimal kuat maka kita perlu melakukan pendefinisian data
25
yang kita gunakan dalam representasi himpunan. Adapun langkah-langkah yang dilakukan dalam membangun aritmetik aljabar matriks mengacu pada tesis Putranto HU (2011). Langkah-langkah untuk membangun aritmetik aljabar matriks adalah sebagai berikut: a. Mendefinisikan Ruang Vektor Biner (power set) dari
sebagai
himpunan Kuasa
= {0, 1, 2, …., n – 1}.
Dalam penelitian ini sembarang vektor biner dengan panjang n secara komputasi merupakan subhimpunan dari
, sedangkan operasi jumlah
dari dua vektor diartikan sebagai selisih simetrik dari dua himpunan, dan produk dalam
dari dua vektor dipandang sebagai irisan dari dua
himpunan. Pada penelitian ini matriks biner A berordo n sebagai list dari sebanyak p subhimpunan dari
p kita pandang
.
b. Mendefinisikan matriks sebagai list (daftar) dari sejumlah anggota
.
Sebagai contoh : * Jika A =
Ini artinya bahwa
=
*B=
Artinya
=
Program-program Aritmetik Aljabar Matriks Biner Sebelum melakukan pelacakan kode optimal kuat terlebih dahulu kita membangun aritmetik aljabar matriks dengan menggunakan program-program yang mengacu pada tesis Putranto HU (2011). Rincian program-program ada di Lampiran B. Berikut ini adalah program-program yang digunakan :
26
a. AcakSet yaitu suatu program yang digunakan untuk membangkitkan vektor dalam ruang berdimensi n secara acak. b. Addv yaitu suatu program yang digunaakan untuk menjumlahkan dua vektor. c. MtxSetC yaitu program untuk mendefinisikan matriks kolom biner berordo m
n secara acak, dimana m adalah ukuran vektor baris dan n
adalah banyaknya vektor kolom dalam matriks. d. MtxSetC1 yaitu program yang mendefinisikan matriks kolom biner berordo m
n secara acak, tidak vektor kolom yang nol. Dalam hal ini
m adalah panjang vektor dan n adalah banyaknya vektor kolom dalam matriks. e. UbahMtxCR yaitu program yang mengubah tampilan matriks kolom ke matriks baris berukuran n
m.
f. TrpsC yaitu suatu program yang digunakan untuk menentukan transpose matriks kolom berordo m berordo n
n menghasilkan matriks kolom
m.
g. TukarR yaitu suatu program yang digunakan untuk menukar baris kei dan ke-j dalam matriks kolom berordo m
n, dimana
0 ≤ i,
j ≤ m – 1. h. GantiB yaitu suatu program yang digunakan untuk mengganti baris ke-j dengan bris ke-i ditambah baris ke-j dalam matriks kolom berordo m x n, dimana 0 ≤ i, j ≤ m – 1. i.
KanonC yaitu suatu program yang digunakan untuk menentukan bentuk kanonik matriks kolom berordo m
j.
n , dimana m ≤ n.
AddMtx yaitu program yang digunakan untuk menjumlahkan dua matriks.
k. DotV yaitu program untuk menentukan produk titik dari dua vektor. l.
MultMtx yaitu program untuk mengalikan matriks kolom m dengan matriks kolom n
n
p.
m. InkodG yaitu program yang digunakan untuk mengkoding vektor pesan P menjadi vektor katakode C menggunakan matriks generator umum G berordo k
n.
27
n. ParG yaitu program untuk menentukan vektor paritas X dari vektor pesan P menggunakan matriks generator bentuk standar G =
,
dalam hal ini P dan B menjadi input, dan X adalah output. Vektor C=
adalah katakode dari pesan P.
o. InkodS yaitu program yang digunakan untuk mengkoding vektor pesan P menjadi vektor katakode C menggunakan matriks generator bentuk standar G =
, dalam hal ini P dan B menjadi input.
p. HmDist yaitu suatu program untuk menentukan jarak hamming dari dua vektor. q. NonZeroWt yaitu suatu program untuk menentukanbobot tak- nol dari suatu kode yang direpresentasikan oleh matriks generator G.
Program-program Pelacakan Kode Optimal Kuat Untuk mengonstruksi kode optimal kuat digunakan program-program pelacakan kode optimal kuat yang mengacu pada tesis Putranto HU (2011), sedangkan rincian lengkap dari program-program ada di Lampiran C. Program-program yang digunakan adalah sebagai berikut : 1. Diberikan matriks generator dalam bentuk standar G =
.
2. Misalkan M adalah matriks representasi vektor baris dari B. 3. Menentukan list semua kombinasi j vektor dari vektor-vektor M (representasi baris) untuk suatu nilai j=1,2,3,…..,k (dengan program KombinM) 4. Menambah satu baris vektor v ke matriks M (representasi baris) di posisi terahir (dengan program AddVekM). 5. Menghapus baris ke-i pada matriks M (representasi kolom) dengan program DelVekM. 6. Menentukan list dari semua list kombinasi M untuk semua j=1,2,3,…..,t dengan t = min{k,d-1}dengan program ListKombM. 7. Menguji apakah vektor x bisa ditambahkan ke M menggunakan output ListKombM dengan program UjiAdd1VekM.
28
8. Melacak satu vektor baris x dalam yang bisa ditambahkan ke M berlandaskan
teorema
Gilbert-Vashamov
dengan
program
Lacak1VekM. Prosedur ini menggunakan program UjiAdd1VekM. 9. Menentukan himpunan semua vektor baris x dalam yang bisa ditambahkan ke M berdasarkan teorema Gilbert-Vashamov dengan program Kolek1VekM. Prosedur ini menggunakan UjiAdd1VekM. 10. Membuang anggota output dari Kolek1VekM dan menyisakan vektorvektor yang menghasilkan matriks-matriks yang tidak saling ekivalen jika ditambahkan ke M dengan program ReduEkil. 11. Misalkan himpunan H adalah output Kolek1VekM, maka setiap pasang vektor (x, y) anggota H akan menghasilkan vektor z = x + y. Agar dua vektor x dan y dapat ditambahkan langsung ke matriks M, maka z diuji dengan prosedur UjiAdd2VekM berdasarkan output ListKombM. 12. Menentukan himpunan semua pasang (x, y) dalam yang bisa ditambahkan ke M berdasarkan teorema Gilbert-Vashamov dengan program Kolek2VekM. Prosedur ini menggunakan UjiAdd2VekM. 13. Menentukan himpunan semua pasang (x, y) menggunakan data hasil sebelumnya dengan program Kolek2VekMDt. 14. Membuang anggota output Kolek2VekM dan menyisakan vektor-vektor yang menghasilkan matriks-matriks yang tidak saling ekivalen jika ditambahkan ke M dengan program ReduEkiX. 15. Misalkan himpunan H adalah output Kolek2VekM, maka setiap 3 vektor (x, y, z) anggota H akan menghasilkan vektor w = x + y + z, agar tiga vektor x, y dan z dapat ditambahkan langsung ke matriks M, maka W diuji dengan prosedur UjiAdd3VekM
berdasarkan output
ListKombM. 16. Menentukan himpunan semua pasang (x, y, z) dalam yang dapat ditambahkan
ke
M
berdasarkan
teorema
Gilbert-Vashamov
menggunakan program Kolek3VekM. Prosedur ini menggunakan program UjiAdd3VekM. 17. Menentukan himpunan semua pasang (x, y, z) menggunakan data hasil sebelumnya dengan program Kolek3VekMDt.
29
18. Misalkan himpunan H adalah output Kolek3VekM, maka setiap 4 vektor (x, y, z, w) anggota H akan menghasilkan vektor v = w + x + y + z, agar empat vektor x, y, z dan w dapat ditambahkan langsung ke matriks M, maka v diuji dengan prosedur UjiAdd4VekM berdasarkan output ListKombM. 19. Menentukan himpunan semua pasang (x, y, z, w) dalam yang dapat ditambahkan ke M berdasarkan teorema Gilbert-Vashamov dengan program Kolek4VekM. Prosedur ini menggunakan UjiAdd4VekM. 20. Menentukan himpunan semua pasang (x, y, z, w) menggunakan data hasil sebelumnya dengan program Kolek4VekMDt. 21. Misalkan himpunan H adalah output Kolek4VekM, maka setiap lima vektor (x, y, z, v, w) anggota H akan menghasilkan vektor u = w + v + x + y + z, agar lima vektor x, y, z, v dan w dapat ditambahkan langsung ke matriks M, maka u diuji dengan prosedur UjiAdd5VekM berdasarkan output ListKombM. 22. Menentukan himpunan semua pasang (x, y, z, v, w) dalam yang dapat ditambahkan ke M berdasarkan teorema Gilbert-Vashamov dengan program Kolek5VekM. Prosedur ini menggunakan UjiAdd5VekM. 23. Menentukan himpunan semua pasang (x, y, z, v, w) menggunakan hasil data sebelumnya dengan program Kolek5VekMDt. 24. Misalkan himpunan H
adalah output dari Kolek(X-1)VekM, maka
setiap x vektor anggota H akan menghasilkan jumlah. Agar x vektor ini dapat ditambahkan langsung ke matriks M, maka diuji dengan prosedur UjiAddXVekM berdasarkan output ListKombM. 25. Menentukan himpunan semua x vektor yang dapat ditambahkan ke M berdasarkan teorema Gilbert-Vashamov dengan program KolekXVekM. Prosedur ini menggunakan UjiAddXVekM. 26. Menentukan himpunan semua pasang x vektor menggunakan data hasil sebelumnya dengan program KolekXVekMDt.
30
Algoritme Konstruksi Kode Optimal Kuat Dalam mengonstruksi kode optimal kuat digunakan algoritme-algoritme yang mengacu pada tesis Putranto HU (2011), sedangkan rincian program konstruksi ada di Lampiran D. Berikut ini adalah algoritme-algoritme yang digunakan: Algoritme 1 untuk mengkonstruksi kode optimal kuat adalah
sebagai
berikut: 1. Masukan bentuk standar dari matriks H yaitu H = Untuk mempertimbangkan efisiensi komputasi maka kita cukup memasukan matriks B berukuran k
r yang memenuhi sifst-sifat:
a. Vektor-vektor dari B berbobot paling sedikit ( d-1 ). b. Jumlah setiap i-vektor baris dari B berbobot paling sedikit ( d-1 ) untuk i = 2, 3, …..s, dimana s = min { d-1, k }. 2. Eksplorasi matriks B dengan cara: a. Menambahkan beberapa matriks kolom nol pada B sesuai dengan yang diinginkan. b. Menentukan list dari semua list kombinasi j vektor dari vektorvektor M (representasi baris) untuk semua j = 1, 2, 3,…, t dengan t = min{k, d - 1} c. Mengkoleksi semua vektor baris X dalam yang bisa ditambahkan ke M berdasarkan teorema Gilbert-Vashamov. 3. Print salah satu kode optimal kuat hasil eksplorasi. Dalam melakukan eksplorasi terhadap matriks B ini dilakukan secara bertahap. Pada langkah 2a matriks kolom yang ditambahkan pada B adalah matriks kolom nol dan penambahannya bisa satu kolom, dua kolom, tiga kolom, dan seterusnya tergantung dengan kebutuhan. Pada langkah 2b menentukan semua list dari peningkatan dimensi yang dapat dilakukan maksimal sama dengan dimensi dari matriks yang akan diubah. Sebagai contoh jika matriks B yang akan ditingkatkan dimensinya berukuran k
r, maka matriks B ini hanya dapat
ditingkatkan maksimal sebanyak k dimensi. Pada langkah 2c mengoleksi vektor baris x dalam yang dapat ditambahkan pada M berdasarkan teorema GilbertVashamov. Maksudnya adalah untuk meningkatkan dimensi dari matriks dasar.
31
Dimulai dengan meningkatkan satu dimensi, dua dimensi, tiga dimensi, empat dimensi, lima dimensi dan seterusnya. Adapun algoritma yang digunakan adalah sebagai berikut :
Algoritme 2 : mencari satu vektor x dalam yang dapat ditambahkan ke B berdasarkan teorema Gilbert-Vashamov 1. Input vektor x ϵ 2. Bobot vektor x + dengan
sedemikian sehingga wt (X +
) ≥ d – 1 – i,
adalah anggota dari semua kombinasi i-vektor baris di B
untuk i = 1,2,3,…t, dan t = min {d – 1, k}. 3. Jika x lulus uji lanjutkan langkah 4. 4. Print satu vektor yang dapat ditambahkan ke dalam matriks B. Algoritme 3 : mencari dua vektor x dan y yang dapat ditambahkan ke dalam matriks B berdasarkan teorema Gilbert-Vashamov. 1. Input adalah koleksi dari himpunan satu vektor yang dapat ditambahkan ke matriks B, misalkan
.
2. Jika wt ( z) > d – 2, dimana z = x + y untuk setiap x, y ϵ
, maka
lanjutkan langkah 3. 3. Uji bobot vektor dengan
≥ d – 2 – i,
sedemikian sehingga wt
adalah anggota dari semua kombinasi i-vektor baris di B
untuk i = 1,2,3,…t, dan t = min {d – 1, k}. 4.
Jika x dan y lolos uji maka lanjutkan langkah 5.
5. Print dua vektor x dan y yang dapat ditambahkan ke dalam matriks B.
Algoritme 4 : menguji apakah m + 1 vektor bisa ditambahkan ke matriks B. 1. Input adalah koleksi dari himpunan m vektor anggota ditambahkan ke matriks B, misalkan 2. Misal
,
ϵ
. Jika
dan
yang dapat
. digabung memiliki m + 1 vektor yang
berbeda maka selanjutnya dilakukan pengujian sebagai berikut. a. Diuji apakah kedua vektor anggota ( ditambahkan ke matriks B.
) – (
) dapat
32
b. Diuji apakah kedua vektor anggota ( ditambahkan dengan setiap i vektor dalam (
)–(
) yang jika ), i = 1, 2, …, m-1
bisa ditambahkan ke matriks B. 3. Untuk menguji j vektor yang bisa ditambahkan ke matriks B, yaitu dengan menjumlahkan j vektor tersebut, misalkan hasil penjumlahannya adalah vektor y. Jika wt (j) > (d – j) lanjutkan langkah 4. 4. Uji bobot vektor ( y + dengan
) sedemikian sehingga wt ( y +
) ≥ d – j – i,
adalah anggota dari semua kombinasi i vektor baris di B untuk
i = 1, 2, …, s, dan s = min {d – 1, k}. 5. Jika vektor y lolos uji, maka lanjutkan langkah 6. 6. Print m + 1 vektor yang dapat ditambahkan ke matriks B. Berikut ini adalah program-program yang digunakan untuk meningkatkan dimensi pada matriks dasar.
Tabel 2 Program dan Prosedur untuk meningkatkan dimensi dari matriks Dasar Untuk meningkatkan
Program
Prosedur
1
Satu dimensi
Kolek1VekM
UjiAdd1VekM
2
Dua dimensi
Kolek2VekM
UjiAdd2VekM
3
Tiga dimensi
Kolek3VekM
UjiAdd3VekM
4
Empat dimensi
Kolek4VekM
UjiAdd4VekM
5
Lima dimensi
Kolek5VekM
UjiAdd5VekM
6
x dimensi
KolekXVekM
UjiAddXVekM
33
Konstruksi Kode Optimal Kuat Dengan Jarak Minimum 13 dan 15
Tabel 3 Hasil Eksplorasi Kode Optimal dengan jarak minimum d = 13 Panjang (n)
Dimensi (k)
Jarak Minimum (d)
Kode [n, k, d]
20
2
13
[20, 2, 13]
24
3
13
[24, 3, 13]
27
5
13
[27, 5, 13]
29
6
13
[29, 6, 13]
32
8
13
[32, 8, 13]
34
9
13
[34, 9, 13]
1. Konstruksi kode [20, 2, 13] Konstruksi dimulai dari kode [20, 2, 13], yaitu dengan mendefinisikan matriks B yang berukuran 2
18 sebagai berikut
B= Dengan menggunakan program UbahMtxCR mengubah tampilan matriks kolom ke matriks baris M. Berikutnya untuk memastikan bahwa jarak minimum d = 13 maka di uji dengan program NonZeroWt. 2.
Konstruksi kode [24, 3, 13]
Selanjutnya matriks B berordo 2 untuk diperluas menjadi matriks
18 ini digunakan sebagai matriks dasar
yang berordo 3
21 dengan cara: pertama-
tama kita menambahkan tiga vektor kolom nol pada matriks dasar sehingga matriks B berordo 2
21. Berikutnya kita mengubah tampilan matriks kolom ke
matriks baris M dengan program UbahMtxCR.
Untuk memastikan bahwa
matriks dasar memiliki jarak minimum d = 13 maka kita uji dengan program NonZeroWt.
Karena
matriks dasar
berdimensi dua
maka
kita dapat
meningkatkanya sampai maksimum dua dimensi. Selanjutnya dengan program ListKombM mencari semua kemungkinan vektor baris X dalam yang dapat ditambahkan ke matriks M. Dengan program Kolek1VekM kita meningkatkan dimensi dari matriks dasar menjadi tiga, sehingga dimensinya menjadi tiga. Tanpa
34
memperhatikan relasi ekivalensi, hasil eksplorasi menunjukan minimal yang berordo 3
42.875 macam parameter
ada
21 yang mendefinisikan kode dengan
[24, 3. 13]. Dan dengan program ReduEki1 dihilangkan matriks-
matriks yang saling ekivalen ternyata diperoleh 8 macam
yang tidak saling
ekivalen, salah satunya
=
3. Konstruksi kode [27, 5, 13] Matriks
berordo 3
menjadi matriks matriks
21 ini dijadikan matriks dasar untuk diperluas
yang berordo
5
22. Caranya adalah; Pertama-tama
ini ditambah satu vektor kolom nol sehingga menjadi matriks dasar
yang berordo 3
22. Kemudian matriks
diubah, dari tampilan matriks kolom
menjadi matriks baris M dengan menggunakan program UbahMtxCR. Untuk memastikan bahwa matriks dasar memiliki jarak minimum d = 13 maka kita uji dengan program NonZeroWt. Karena M berdimensi 3 maka kita dapat meningkatkan matriks dasar ini maksimal 3 dimensi. Dengan program ListKombM mencari semua kemungkinan vektor baris X dalam yang dapat ditambahkan ke M. Dengan program Kolek1VekM kita tingkatkan dimensi dari matriks dasar satu tingkat sehingga dimensinya menjadi empat, dan hasilnya terdapat minimal ada 17.496 kode dengan parameter [26, 4, 13]. Selanjutnya ditingkatkan lagi dimensinya menjadi menjadi lima dengan cara menambahkan satu lagi vektor baris X dalam ke M dengan program Kolek2VekMDt. Dari hasil eksplorasi tanpa melihat relasi ekivalensi ternyata minimal ada 39.432 macam matriks
berordo
5
22 yang mendefinisikan kode dengan parameter
[27, 5, 13]. Dengan program ReduEkiX dihilangkan matriks-matriks yang saling ekivalen. Hasilnya hanya minimal ada 4 macam matriks ekivalen. Salah satunya adalah
yang tidak saling
35
=
4. Konstruksi kode [29, 6, 13] Matriks
berordo 5
menjadi matrik
22 ini dijadikan matriks dasar untuk diperluas lagi
yang berordo 6
23. Dengan cara ; Pertama-tama matriks
dasar ini ditambahkan satu vektor kolom nol sehingga menjadi matriks dasar yang berordo 5
23. Dengan program UbahMtxCR diubah tampilan matriks, dari
matriks kolom menjadi matriks baris M. Untuk memastikan bahwa matriks dasar kita mempunyai jarak minimum d = 13, maka kita uji dengan menggunakan program NonZeroWt. Karena dimensi dari matriks dasar kita adalah lima, maka kita dapat meningkatkan dimensi dari matriks dasar tersebut maksimal lima dimensi. Dengan program ListKombM
mencari semua kemungkinan vektor
baris X dalam yang dapat ditambahkan ke M. Dengan program Kolek1VekM kita tingkatkan dimensi dari matriks dasar satu tingkat menjadi enam. Dari hasil eksplorasi paling tidak ada satu macam matriks
berukuran 6
23 yang
mendefinisikan kode dengan parameter [29, 6, 13]. Matriks tersebut adalah
=
5. Konstruksi kode [32, 8, 13] Matriks menjadi matriks
berordo 6 berordo 8
23 ini dijadikan matriks dasar untuk diperluas lagi 24 yang mendefinisikan kode dengan parameter
[32, 8, 13]. Dengan cara; Pertama-tama ditambahkan satu vektor kolom nol dan menghapus baris ke-1 pada matriks representasi kolom dengan program DelVekM sehingga didapat matriks dasar yang berordo 5
24. Kemudian
dengan program UbahMtxCR diubah tampilan matriks, dari matriks kolom menjadi matriks baris M. Karena matriks dasar kita berdimensi lima maka, kita dapat
meningkatkan maksimal sampai lima dimensi. Dengan program
ListKombM mencari semua kemungkinan vektor baris X dalam yang dapat
36
ditambahkan ke M. Dengan program Kolek1VekM kita meningkatkan dimensi dari matriks dasar satu tingkat sehingga dimensinya menjadi enam. Setelah ditingkatkan satu dimensi ternyata diperoleh setidaknya ada 14.692 kode dengan parameter [30, 6 13]. Berikutnya dengan program Kolek2VekMDt dimensinya ditingkatkan satu tingkat lagi menjadi tujuh, dan didapat paling sedikit ada 1.000 kode
dengan
parameter
[31,
7,
13].
Selanjutnya
dengan
program
Kolek3VekMDtx, dimensinya ditingkatkan satu tingkat lagi menjadi delapan, dan diperoleh paling sedikit ada 192 matriks
berordo 8
24 yang
mendefinisikan kode dengan parameter [32, 8, 13]. dan setelah dihilangkan matriks-matriks yang saling ekivalen dengan program ReduEkiX ternyata semuanya tidak saling ekuivalen, Sehingga didapat paling tidak ada 192 matriks berukuran 8
24 yang mendefinisikan kode dengan parameter [32, 8, 13].
Salah satunya adalah
=
6. Konstruksi kode [34, 9, 13] Matriks menjadi matriks
berordo 8
24 dijadikan matriks dasar untuk diperluas lagi
berordo 9
25 untuk mendefinisikan kode dengan parameter
[34, 9, 13]. Dengan cara; Pertama-tama ditambahkan satu vektor kolom nol, dan menghapus baris ke-1 pada matriks representasi kolom dengan program DelVekM sehingga didapat matriks dasar yang berukuran 7
25. Kemudian
dengan program UbahMtxCR diubah tampilan matriks, dari matriks kolom menjadi matriks baris M. Karena matriks dasar ini berdimensi tujuh maka kita dapat meningkatkan matriks dasar ini maksimal sampai tujuh dimensi. Dengan program ListKombM mencari semua kemungkinan vektor baris X dalam yang dapat ditambahkan ke M. Dengan program Kolek1VekM kita tingkatkan satu dimensi sehingga ukuran matriks menjadi 8
25, ternyata didapat paling sedikit
ada 2.107 kode dengan parameter [33, 8, 13]. Selanjutnya dengan program Kolek2VekMDt dimensinya ditingkatkan lagi satu tingkat sehingga ukuran
37
matriks menjadi 9 berukuran 9
25, ternyata didapat paling sedikit ada dua matriks
25 yang mendefinisikan kode dengan parmeter [34, 9, 13]. Matriks
yang didapat sebagai berikut:
[1] =
Dan
[2] =
Untuk selanjutnya
ini gagal untuk diperluas lagi. Seandainya matriks
tersebut dapat diperluas menjadi matriks berukuran 10
25 maka telah berhasil
diperbaiki batas bawah untuk kode yang berjarak minimum d = 13, yaitu kode dengan parameter [35, 10, 13]. Atau dengan kata lain telah berhasil dikonstruksi kode baru yaitu kode [35, 10, 13].
Tabel 4 Hasil Eksplorasi Kode Optimal dengan jarak minimum d = 15 Panjang (n)
Dimensi (k)
Jarak Minimum (d)
Kode [ n, k, d ]
23
2
15
[23, 2, 15]
27
3
15
[27, 3, 15]
31
6
15
[31, 6, 15]
35
8
15
[35, 8, 15]
37
9
15
[37, 9, 15]
38
7. Konstruksi kode [23, 2, 15] Untuk kode [ 23, 2, 15 ] dapat dikonstruksi dengan mudah menggunakan matriks B berukuran 2
21 sebagai berikut
B = Tetapi matriks B ini tidak berhasil diperluas untuk mendapatkan kode optimal berikutnya. 8. Konstruksi kode [27, 3, 15]
Karena matriks B tidak dapat diperluas untuk mendapatkan kode optimal berikutnya, maka selanjutnya dikonstruksi matriks dasar
berukuran 3
untuk mendefinisikan kode dengan parameter [ 27, 3, 15 ]. Matriks
24 yang
digunakan adalah sebagai berikut
=
9. Konstruksi kode [31, 6, 15] Matriks
berordo 3
diperluas menjadi matriks
24 ini dijadikan sebagai matriks dasar untuk yang berordo 6
25 untuk mendefinisikan kode
dengan parameter [31, 6, 15]. Dengan cara; pertama menambahkan satu vektor kolom nol pada matriks dasar sehingga matriks dasar ordonya menjadi 3
25,
dilanjutkan dengan mengubah tampilan matriks, dari matriks kolom menjadi matriks baris M dengan program UbahMtxCR. Selanjutnya untuk memastikan bahwa jarak minimum distenya 15 maka digunakan program NonZeroWt. Karena matriks yang dijadikan matriks dasar mempunyai dimensi tiga, maka dimensinya dapat ditingkatkan maksimal tiga dimensi. Dengan program ListKombM mencari semua kemungkinan vektor baris X dalam yang dapat ditambahkan ke M. Dengan program Kolek1VekM ditingkatkan satu dimensi sehingga dimensinya menjadi empat dan didapat paling sedikit 34.992 kode dengan para meter [29, 4, 15]. Berikutnya dengan program Kolek2VekMDt dimensinya ditingkatkan satu tingkat lagi menjadi lima, tanpa memperhatikan relasi ekuivalensi didapat paling sedikit ada 199.904 kode dengan parameter
39
[30, 5, 15]. Dengan program Kolek3VekMDt dimensinya ditingkatkan satu tingkat lagi menjadi enam, dan tanpa memperhatikan relasi ekuivalensi didapat paling sedikit ada 9.309 matriks
berordo 6
25 yang mendefinisikan kode
dengan parameter [31, 6, 15]. Salah satunya adalah
=
10. Konstruksi kode [35, 8, 15] berordo 6
Matriks
menjadi matriks
25 ini dijadikan matriks dasar untuk diperluas lagi
yang berordo 8
27, yaitu untuk mendefinisikan kode
dengan parameter [ 35, 8, 15 ]. Cara mengonstruksi matriks
adalah sebagai
berikut ; Yang pertama menambahkan dua vektor kolom nol pada matriks dasar dan dengan program DelVekM untuk i = 1, menghapus baris ke-1 pada matriks dasar sehingga didapat matriks dasar yang berordo 5
27. Untuk memastikan
bahwa matriks dasar mempunyai jarak minimum d = 15 maka di uji dengan program NonZeroWt. Sebelum melakukan eksplorasi lebih lanjut, terlebih dulu kita mengubah tampilan matriks, dari matriks kolom menjadi matriks baris M dengan program UbahMtxCR. Karena matriks dasar berdimensi lima maka kita dapat meningkatkanya sampai maksimal lima dimensi. Selanjutnya Dengan program ListKombM mencari semua kemungkinan vektor baris X dalam yang dapat ditambahkan ke M. Dengan program Kolek1VekM kita tingkatkan satu dimensi sehingga dimensinya menjadi enam, hasilnya minimal ada 3.971 matriks dasar beerordo 6
27 yang medefinisikan kode dengan parameter [33, 6, 15].
Langkah selanjutnya dengan program Kolek2VekM
matriks dasar ini
dimensinya kita tingkatkan satu tingkat lagi menjadi tujuh, hasilnya minimal ada 19930 matriks dasar yang berordo 7
27 yang mendefinisikan kode dengan
parameter [34, 7, 15]. Berikutnya matriks dasar ini kita tingkatkan satu tingkat lagi dengan program Kolek3VekM sehingga dimensinya menjadi delapan, hasilnya tanpa memperhatikan relasi ekuivalensi minimal ada 1.699 matriks berordo 8
27 yang mendefinisikan kode dengan parameter [35, 8, 15]. Dan
setelah dihilangkan matriks-matriks yang saling ekuivalen dengan program
40
ReduEkiX didapat minimal ada 689
kode optimal kuat dengan parameter
[35,8,15]. Salah satunya adalah
=
11. Konstruksi kode [37, 9, 15] Matriks
berordo 8
menjadi matriks
27 ini dijadikan matriks dasar untuk diperluas lagi
yang berordo 9
28 untuk mendefinisikan kode dengan
parameter [ 37, 9, 15 ]. Cara mengonstruksi matriks
adalah sebagai berikut ;
Yang pertama menambahkan satu vektor kolom nol pada matriks dasar dan dengan program DelVekM untuk i = 8, menghapus baris ke-8 pada matriks dasar sehingga didapat matriks dasar yang berordo 7
28. Untuk memastikan bahwa
matriks dasar mempunyai jarak minimum d = 15 maka di uji dengan program NonZeroWt. Sebelum melakukan eksplorasi lebih lanjut, terlebih dulu kita mengubah tampilan matriks, dari matriks kolom menjadi matriks baris M dengan program UbahMtxCR. Karena matriks dasar berdimensi tujuh maka kita dapat meningkatkanya sampai maksimal tujuh dimensi. Selanjutnya Dengan program ListKombM mencari semua kemungkinan vektor baris X dalam yang dapat ditambahkan ke M. Dengan program Kolek1VekM kita tingkatkan satu dimensi sehingga dimensinya menjadi delapan, hasilnya minimal ada 2.472 matriks dasar beerordo 8
28
yang medefinisikan kode dengan parameter [36, 8, 15].
Selanjutnya dengan program Kolek2VekM matriks dasar ini dimensinya kita tingkatkan satu tingkat lagi menjadi sembilan, hasilnya tanpa melihat relasi ekuivalensi minimal ada 542 matriks dasar yang berordo 9
28 yang
mendefinisikan kode optimal kuat dengan parameter [37, 9, 15]. Dan setelah dihilangkan matriks-matriks yang saling ekuivalen dengan program ReduEkiX didapat minimal ada 281 kode optimal kuat dengan parameter [37, 9, 15]. Salah satunya adalah
41
=
Selanjutnya untuk menjadikan matriks
menjadi matriks dasar dan
ditingkatkan ke order yang lebih tinggi mengalami kegagalan. Kegagalan ini dapat disebabkan oleh beberapa kemungkinan, diantaranya: 1. Pemilihan kode dasar ( matriks B awal ) yang kurang baik. 2. Algoritme konstruksi yang masih belum sempurna.
