BAB III TEOREMA GLEASON DAN t-DESAIN
Dalam subbab 3.1, kita akan mempelajari salah satu sifat penting dari kode swa-dual genap. Sifat tersebut diberikan oleh Teorema 3.1(Teorema Gleason), Teorema ini secara mengesankan telah menentukan bentuk pencacah bobot dari sebarang kode swa-dual genap. Di samping itu, pada subbab 3.2 kita akan mempelajari teori t-desain. Kemudian kita tunjukan bahwa untuk sebarang kode linier C, jika banyaknya bobot tak nol pada C kurang dari atau sama dengan jarak minimum pada kode dual πΆ β₯ , maka setiap katakode di C membentuk t-desain. Dua hasil yang disebutkan di atas merupakan dua hal penting yang akan digunakan dalam menentukan batas atas bagi jarak minimum kode swa-dual genap. Penentuan batas atas tersebut dibahas pada bab IV.
3.1 Teorema Gleason Teorema 3.1.1 Teorema Gleason(Gleason, 1970). Pencacah bobot sebarang kode swa-dual genap
merupakan
polinom
dalam
π1 π₯, π¦ = π₯ 8 + 14π₯ 4 π¦ 4 + π¦ 8
dan
π2 π₯, π¦ =
n
, serta setiap
π₯ 4π¦4 π₯ 4 β π¦4 4. Bukti: Misal πΆ kode swa-dual biner dengan panjang n dan dimensi k ο½
2
bobot dari semua kata kode di C merupakan kelipatan 4. Misalkan WC ο¨ x, y ο© adalah pencacah bobot kode swa-dual tersebut, karena C
swa-dual WC ο¨ x, y ο© = WC ο ο¨ x, y ο© .
Berdasarkan teorema Mac Williams, WC ο ο¨ x, y ο© dapat dihitung sebagai berikut :
WC ο ο¨ x, y ο©
=
1 2
n 2
WC ο¨ x ο« y, x ο y ο©
13
=
1 2
n 2
n
=
ο₯
n
ο₯ A ο¨ x ο« yο© ο¨ x ο yο© j ο½0
nο j
Aj ο¨ x ο« y ο©
j ο½0
n
=
ο₯ Aj
nο j
2
ο¨ x ο« yο©
j ο½0
j
j
ο¨ x ο yο©
n 2
nο j
ο¨ x ο yο©
ο¨ nο j ο©
2
j
2
2
j
j 2
ο¦ xο« yοΆ = ο₯ Aj ο§ 1/2 ο· ο¨ 2 οΈ j ο½0
nο j
ο¦ xο yοΆ ο§ 1/2 ο· ο¨ 2 οΈ
j
ο¦ xο« yοΆ = ο₯ Aj ο§ ο· ο¨ 2 οΈ j ο½0
nο j
ο¦ xο yοΆ ο§ ο· ο¨ 2 οΈ
j
n
n
ο¦ xο« y xο yοΆ = Wο§ , ο· 2 οΈ ο¨ 2
ο¦ xο« y xο yοΆ Sehingga diperoleh WC ο¨ x, y ο© = WC ο ο¨ x, y ο© = W ο§ , ο·. 2 οΈ ο¨ 2
(3.1.a)
Kita tinjau WC ο¨ x, y ο© berdasarkan definisi pencacah bobot, bentuk WC ο¨ x, y ο© dapat dituliskan sebagai : n
WC ο¨ x, y ο© ο½ ο₯ Aj x n ο j y j ; A j banyaknya kata kode berbobot j . j ο½0
Karena setiap bobot dari semua kata kode di πΆ merupakan kelipatan 4, WC ο¨ x, y ο© hanya memuat pangkat dari y 4 . Sehingga WC ο¨ x, y ο© dapat kita tulis sebagai :
WC ο¨ x, y ο©
n
= ο₯ Aj ο¨ x ο©
nο j
j ο½0
ο¨
ο1y
ο©
j
= WC ο¨ x, iy ο© , dengan i = ο1 .
(3.2.b)
Persamaan (3.2.a) menunjukan WC ο¨ x, y ο© tidak berubah atau invarian terhadap transformasi linier T1 : 14
ο·
Ganti x dengan
xο« y 2
ο·
Ganti y dengan
xο y 2
Atau dalam bentuk matriks
ο¦ xοΆ T1 : ganti ο§ ο· ο¨ yοΈ
dengan
1 2
ο¦1 1 οΆ ο¦ x οΆ ο§ ο· ο§ ο·. ο¨1 ο1οΈ ο¨ y οΈ
Sejalan dengan hal di atas, persamaan (3.2.b) menunjukan bahwa WC ο¨ x, y ο© juga tidak berubah atau invarian terhadap transformasi linier T2 : ο·
Ganti x dengan x
ο·
Ganti y dengan iy
ο¦ xοΆ Atau dalam bentuk matriks T2 : ganti ο§ ο· ο¨ yοΈ
dengan
ο¦1 0οΆ ο¦ x οΆ ο§ ο·ο§ ο· . ο¨0 i οΈ ο¨ yοΈ
Selain hal di atas, WC ο¨ x, y ο© tentulah invarian terhadap sebarang kombinasi
T12 , T2T1 , TT 1 2T1 ,.... dari transformasi ini. Tidaklah sulit untuk menunjukan bahwa matriks transformasi T1 dan T2 ketika dikalikan dalam semua kemungkinan, menghasilkan sebuah grup G1 yang memuat 192 matriks. Sehingga permasalahan kita adalah mencari semua polinom WC ο¨ x, y ο© yang invarian terhadap setiap matriks dari G1 . Polinom-polinom tersebut kita sebut sebagai polinompolinom yang invarian terhadap grup G1 . Akan tetapi, kita tidak akan mendapatkan jawaban yang tunggal. Karena jika polinom f dan g invarian terhadap setiap matriks dari G1 , maka cf untuk semua c elemen πΉ, f+g, f-g, dan fg juga invarian terhadap setiap matriks dari
G1 . Oleh karena itu, cukuplah kita cari banyaknya polinom homogen yang bebas linier dan invarian terhadap semua matriks dari G1 untuk setiap derajat d, sebut sebagai ad .
15
Salah satu cara sederhana untuk menangani bilangan-bilangan a0 , a1 , a2 ,... adalah dengan mengombinasikan a0 , a1 , a2 ,... dalam bentuk deret pangkat atau fungsi pembangkit π π = a0 ο« a1ο¬ ο« a2ο¬ 2 ο« ... . Sebaliknya, jika kita tahu Ξ¦ π , kita bisa mendapatkan ad . Sampai pada tahap ini kita akan memanfaatkan teorema Molien berikut ini : Teorema 3.2.2 Teorema Molien. Untuk suatu grup hingga π’ dari matriks-matriks kompleks π Γ π, π π diberikan oleh : π π =
1
1 π΄βπ’ πππ‘ πΌβππ΄
π’
dimana π’ adalah banyaknya matriks di π’, det adalah determinan, πΌ adalah matriks identitas, dan A merupakan matriks-matriks di π’. Bukti Teorema Molien tidak dituliskan dalam Tugas Akhir ini, demi menjaga kefokusan Tugas Akhir ini. Bukti Teorema Molien dapat dilihat di [1]. 1
Untuk grup G 1 , kita dapatkan ππΊ π = 192 1
1 1βπ 2
+
1 1βπ2
1
+
1βπ 1βππ
+ β― . Dengan
penghitungan langsung menggunakan program Maple, diperoleh : ππΊ π = 1
Persamaan
(3.2.a)
diekspansi
1
(3.2.a)
1βπ8 1βπ24
dalam
pangkat
dari
π,
menghasilkan
:
ππΊ π = π0 + π1 π + π2 π2 + β― 1
= 1 + π8 + π16 + π24 + β― 1 + π24 + π48 + β―
(3.2.b)
Persamaan (3.2.b) menunjukan ππ sama dengan nol, kecuali untuk d kelipatan 8. Artinya, derajat dari polinom homogen yang invariant terhadap grup G 1 haruslah kelipatan 8. Hal ini membuktikan bahwa panjang dari sebarang kode swa-dual genap merupakan kelipatan 8. Lebih lanjut, ruas kanan dari persamaan ini menunjukan bahwa terdapat dua buah polinom βbasisβ berderajat 8 dan 24 yang invarian terhadap grup G 1, sedemikian rupa sehingga semua polinom homogen yang invarian terhadap grup G 1 16
dibentuk dari penjumlahan dan perkalian dua buah polinom berderajat 8 dan 24 tersebut. Sebut dua polinom tersebut sebagai π1 π₯, π¦ dan π2 π₯, π¦ . Karena, π1 π₯, π¦ berderajat 8 dan π2 π₯, π¦ berderajat 24, akan membangkitkan polinom-polinom yang invarian terhadap grup G1 berikut : derajat (d)
poliom yang invarian
nilai ππ
0
1
1
8
π1 π₯, π¦
1
16
2
1
, π2 π₯, π¦
2
, π1 π₯, π¦ π2 π₯, π¦
2
π1 π₯, π¦
24
π1 π₯, π¦
32
π1 π₯, π¦
40
π1 π₯, π¦
48
π1 π₯, π¦
6
4 5
3
, π1 π₯, π¦ 3
, π1 π₯, π¦
β¦
2
2
π2 π₯, π¦
π2 π₯, π¦ , π2 π₯, π¦
2
β¦
Dari tabel di atas semua hasil kali π1 π₯, π¦ π π2 π₯, π¦
3 β¦
π
bebas linier, dengan kata
lain π1 π₯, π¦ dan π2 π₯, π¦ bebas aljabar, dan nilai ππ pada tabel di atas merupakan koefisien-koefisien pada persamaan 1 + π8 + π16 + 2π24 + 2π32 + 2π40 + 3π48 + β― = 1 + π8 + π16 + π24 + β― 1 + π24 + π48 + β― =
1 1βπ
8
1 β π24
yang sama dengan persamaan (3). Jadi, jika kita dapat menemukan polinom homogen π1 π₯, π¦
berderajat 8 dan π2 π₯, π¦
berderajat 24 yang bebas aljabar, kita dapat
menyatakan bahwa sebarang polinom homogen yang invarian terhadap grup G 1 merupakan polinom dalam π1 π₯, π¦ dan π2 π₯, π¦ .
17
Pandang Ξ = π₯8 + 14π₯4 π¦4 + π¦8 suatu polinom homogen berderajat 8, dan Ξ¦ = π₯4 π¦4 π₯4 β π¦4
4
suatu polinom homogen berderajat 24, Ξ dan Ξ¦ bebas aljabar. Pilih
π1 π₯, π¦ = π© dan π2 π₯, π¦ = Ξ¦, maka sebarang polinom homogen yang invarian terhadap grup G 1 merupakan polinom dalam π1 π₯, π¦ dan π2 π₯, π¦ . Pernyataan ini Setara dengan menyatakan bahwa pencacah bobot dari sebarang kode swa-dual genap merupakan polinom dalam π1 π₯, π¦ dan π2 π₯, π¦ . Terbukti.
β
3.2 t-desain Definisi 3.2.1 Misal X merupakan suatu v-himpunan (himpunan dengan v buah elemen), eleman-elemen di X disebut titik atau varietas. Suatu t(π, π, π)-desain adalah suatu koleksi dari k-subhimpunan (dinamakan blok) dari X, yang berbeda satu sama lain, dengan sifat sebarang t-subhimpunan dari X termuat di tepat π buah blok. Dalam bahasa yang lebih ilustratif, t-desain merupakan koleksi dari komite-komite yang dibentuk dari v orang, setiap komite beranggotakan k orang, sedemikian rupa sehingga setiap t orang bekerja bersama-sama dalam tepat π komite. Contoh 3.2.2 Perhatikan gambar di bawah ini :
Gambar 3.2 Terdapat tujuh titik dan tujuh garis (salah satunya merupakan garis lengkung) pada gambar di atas . Jika kita mengambil garis-garis sebagai blok, kita peroleh tujuh blok yaitu : 18
013, 045, 062, 165, 412, 463, dan 325. Selanjutnya kita dapatkan 2-(7,3,1) desain, karena setiap dua buah titik dilewati oleh sebuah garis yang tunggal. Teorema 3.2.3 Di dalam t-(v,k , π) desain, misalkan π1 , π2 , β¦ , ππ‘ merupakan t titik yang berbeda, misal ππ adalah banyaknya blok yang memuat π1 , π2 , β¦ , ππ , untuk 1 β€ π β€ π‘, dan misal π0 = π merupakan jumlah keseluruhan dari blok-blok. Maka ππ tidak bergantung pada pemilihan dari π1 , π2 , β¦ , ππ dan diperoleh fakta : ππ =
π π£βπ π‘βπ π βπ π‘βπ
=π
,1 β€ π β€ π‘
π£βπ π£βπβ1 β¦(π£βπ‘+1) π βπ πβπβ1 β¦(πβπ‘+1)
Hal ini menyebabkan suatu t-(v, k , π) juga merupakan i-(v, k , ππ ) untuk 1 β€ π β€ π‘. Bukti : Teorema benar untuk π = π‘ , karena menurut definisi t-desain, setiap t titik termuat tepat pada π blok. Kita lanjutkan dengan induksi pada i. Asumsikan ππ+1 tidak bergantung pada pemilihan π1 , π2 , β¦ , ππ+1 . Untuk setiap blok B yang memuat π1 , π2 , β¦ , ππ , dan untuk setiap titik Q yang berbeda dengan π1 , π2 , β¦ , ππ definisikan π π, π΅ = 1 jika π β π΅, dan π π, π΅ = 0 jika π β π΅. Maka dari hipotesis induksi kita peroleh : π)
=
π
π΅π
π
π΅π
π, π΅ = ππ+1 (π£ β
π, π΅ = ππ+1 (π β π), yang menunjukan bahwa ππ bebas dari pemilihan
π1 , π2 , β¦ , ππ ,dan menunjukan fakta pada teorema di atas. Terbukti.
β
Misal v dan w merupakan dua vektor di F n , v ο½ v1...vn dan w ο½ w1...wn . Misalkan
ο»
ο½
Iv ο½ j v j ο½ 1; j ο½ 1...n dan Iw ο½ ο»i wi ο½ 1;i ο½ 1...nο½. Vektor w dikatakan menyelimuti v, jika
Iw ο Iu . Teorema 3.2.4(MacWilliams dan Sloane [1]). Misal [C] adalah matriks Mxn dengan barisbarisnya merupakan semua katakode di suatu kode C. Sebarang himpunan dari r ο£ d' ο 1 kolom di [C] memuat setiap r-tuple sebanyak tepat M 2r kali, dan d ' merupakan bilangan terbesar dalam kasus ini. Bukti Teorema ini dapat dilihat pada [1]. 19
Teorema 3.2.5(MacWilliams dan Sloane [1]). Misal kita pilih sebuah vektor u berbobot t di
F n , 0 οΌ t οΌ d ' . Untuk ο΄ i ο³ t , misal ο¬ο΄ i (u) adalah banyaknya katakode di C yang berbobot ο΄ i yang menyelimuti u. Maka ο¬ο΄ i (u) memenuhi persamaan : ο¦ο΄ i ο t οΆ M ο¦nοt οΆ ο· ο¬ο΄ i (u) ο½ t ο« j ο§ ο· 2 ο¨ j οΈ j οΈ i ο½1 ο¨ s
ο₯ο§
ο½
2nοt ο j ο¦ n ο t οΆ ' ο§ ο· , dengan 0 ο£ j ο£ d ο 1 ο t . (3.2.1) N ο¨ j οΈ
Bukti : Kita gunakan Teorema 3.2.4 untuk menghitung (dalam dua arah) banyaknya katakode berbobot t+j yang menyelimuti u dan terselimuti oleh sebuah katakode di C. Terbukti
β
Teorema 3.2.6 (Mac Williams dan Sloane[1]) Jika s ο£ d ' , maka semua katakode berbobot
ο΄ i di C membentuk t ο (n,ο΄ i , ο¬ο΄ )ο desain, dengan t ο½ (d 'ο s) , dan parameter ο¬ο΄ diberikan i
s
oleh ο¬ο΄ i . ο (ο΄ j ο ο΄ i ) ο½ j ο½1, j οΉi
i
An .S (n) 1 n ο¦ n ο t οΆ S (r ) , memberikan ο΄ i ο³ d ' ο s . ο« ο₯ο§ ο· n οο΄ i N r ο½t ο¨ r ο t οΈ ο΄ i ο r
Bukti : Karena vektor 1= 1β¦1 di F n menyelimuti semua semua vektor di F n , kita dapat menuliskan persamaan (3.2.1) menjadi : ο¦ 2nοt ο j οΆο¦ n ο t οΆ ο¦ο΄ i ο t οΆ ο¬ ( u ) ο½ ο An ο· ο§ ο§ ο₯ ο§ ο· ο΄i ο·. j οΈ i ο½1 ο¨ ο¨ N οΈο¨ j οΈ s
(3.2.2)
Jika kita dapat memilih t sedemikian rupa sehingga d ' ο t ο½ s , maka kita dapatkan sebanyak s persamaan yang bebas linier dalam veriabel ο¬ο΄ i (u) .
Dengan kata lain, ο¬ο΄ i (u) tidak
bergantung pada pemilihan u. Oleh karena itu, semua katakode berbobot ο΄ i membentuk tdesain, dengan t ο½ d 'ο s . Parameter-paremeter dari desain ini diperoleh sebagai berikut : Persamaan (3.2.2) memiliki solusi :
ο¬ο΄ gο΄ οt (ο΄ i ο t ) ο½ i
i
1 n οt ο¦ n ο t οΆ ο₯ ο§ ο· g (r ) ο An gο΄i οt (n ο t ), N r ο½0 ο¨ r οΈ ο΄ i οt
dengan 20
gο΄ i οt ( x ) ο½
ο ο¨ο΄ s
j ο½1, j οΉi
j
ο©
οt ο x .
Jelas bahwa gο΄ i οt ( x ο t ) ο½ gο΄ i ( x ) , sehingga solusi dari persamaan (3.2.2) adalah : gο΄ i (ο΄ i ) ο¬ο΄ i ο½
1 n ο¦nοt οΆ ο₯ ο§ ο· g (r ) ο An gο΄i (n), N r ο½t ο¨ r ο t οΈ ο΄ i
ο¬ο΄ . ο (ο΄ j ο ο΄ i ) ο½
An .S (n) 1 n ο¦ n ο t οΆ S (r ) . ο« ο₯ο§ ο· n οο΄ i N r ο½t ο¨ r ο t οΈ ο΄ i ο r
s
atau
i
j ο½1, j οΉi
Terbukti
(3.2.3) β
21