BAB II TEORI DASAR. Definisi Grup G disebut grup komutatif atau grup abel jika berlaku hukum

BAB II TEORI DASAR

2.1 Aljabar Linier Definisi 2. 1. 1 Grup Himpunan tak kosong 𝐺 disebut grup (𝐺,∗) jika pada 𝐺 terdefinisi operasi ∗ , sedemikian rupa sehingga berlaku : a. Jika 𝑎, 𝑏 elemen dari 𝐺, maka

𝑎 ∗ 𝑏 elemen dari 𝐺. Dengan kata lain, 𝐺 tertutup

terhadap operasi ∗. b. Berlaku hukum asosiatif di 𝐺, yaitu diberikan 𝑎, 𝑏, 𝑐 elemen dari 𝐺 , maka 𝑎 ∗ 𝑏 ∗ 𝑐 = 𝑎 ∗ 𝑏 ∗ 𝑐. c. Terdapat 𝑒 elemen dari 𝐺 sedemikian rupa sehingga untuk setiap 𝑎 elemen dari 𝐺 berlaku 𝑎 ∗ 𝑒 = 𝑒 ∗ 𝑎 = 𝑎. Selanjunya elemen e disebut elemen identitas atau unit di 𝐺. d. Untuk setiap 𝑎 elemen dari 𝐺, terdapat 𝑎−1 ∈ 𝐺 sedemikian rupa sehingga 𝑎 ∗ 𝑎−1 = 𝑎−1 ∗ 𝑎 = 𝑒. Elemen 𝑎−1 disebut invers dari 𝑎 di 𝐺. Definisi 2. 1. 2 Grup 𝐺 disebut grup komutatif atau grup abel jika berlaku hukum komutatif di 𝐺, yaitu 𝑎 ∗ 𝑏 = 𝑏 ∗ 𝑎, untuk setiap 𝑎, 𝑏 ∈ 𝐺. Contoh 2.1.3 Himpunan bilangan bulat (Z, +) merupakan grup komutatif terhadap operasi penjumlahan. Definisi 2. 1. 4 Lapangan Lapangan adalah sebuah himpunan 𝐹, elemen-elemannya dinamakan skalar, bersama dengan dua buah operasi biner yaitu penjumlahan dinotasikan dengan +, dan perkalian dinotasikan dengan ∗; bersama dengan dua buah elemen 0, 1 𝜖 𝐹 sedemikian rupa sehingga berlaku : a. Untuk Setiap 𝑥, 𝑦, 𝑧 ∈ 𝐹 1. 𝑥 + 𝑦 ∈ 𝐹 2

2. 𝑥 + 𝑦 = 𝑦 + 𝑥 3. 𝑥 + 𝑦 + 𝑧 = 𝑥 + (𝑦 + 𝑧) 4. 0 + 𝑥 = 𝑥 5. terdapat (−𝑥) ∈ 𝐹 sedemikian rupa sehingga (−𝑥) + 𝑥 = 0 b. Untuk setiap 𝑥, 𝑦, 𝑧 ∈ 𝐹 6. 𝑥 ∗ 𝑦 ∈ 𝐹 7. 𝑥 ∗ 𝑦 = 𝑦 ∗ 𝑥 8.

𝑥 ∗ 𝑦 ∗ 𝑧 = 𝑥 ∗ (𝑦 ∗ 𝑧)

9. 1 ∗ 𝑥 = 𝑥 c. Untuk setiap 𝑥 ∈ F, 𝑥 ≠ 0, terdapat elemen 𝑥 −1 di 𝐹 sedemikian rupa sehingga 𝑥 ∗ 𝑥 −1 = 𝑥 −1 ∗ 𝑥 = 1. d. Untuk setiap 𝑥, 𝑦, 𝑧 ∈ 𝐹, berlaku hukum distributif yaitu 𝑥 + 𝑦 ∗ 𝑧 = 𝑥 ∗ 𝑦 + 𝑥 ∗ 𝑧. Lapangan 𝐹 disebut lapangan hingga jika 𝐹 memiliki sebanyak hingga elemen. Banyaknya elemen di suatu lapangan hingga dinamakan orde lapangan. Jika lapangan 𝐹 memiliki tak hingga elemen, 𝐹 disebut lapangan tak hingga. Contoh 2.1.5 Himpunan 𝑭𝟐 = {0,1} dengan operasi penjumlahan dan perkalian dilakukan dalam modulo 2, merupakan lapangan hingga berorde 2. Lapangan 𝑭𝟐 biasa disebut lapangan biner. Himpunan bilangan riil 𝑹 merupakan salah satu contoh lapangan tak hingga. Definisi 2. 1. 5 Sub Ruang Vektor Sub Ruang Vektor dari 𝐹𝑝 adalah sub himpunan 𝑉 ⊆ 𝐹 𝑝 dari p-vektor dengan 0 ∈ 𝑉 sedemikian rupa sehingga berlaku: a. Jika 𝑣 ∈ 𝑉 dan 𝑎 ∈ 𝐹, maka 𝑎 ∗ 𝑣 ∈ 𝑉 b. Jika 𝑢, 𝑣 ∈ 𝑉 maka 𝑢 + 𝑣 ∈ 𝑉 Definisi ini ekuivalen dengan, suatu subruang vektor dari 𝐹𝑝 adalah himpunan tak kosong dari p-vektor dan tertutup terhadap operasi penjumlahan dan perkalian skalar.

3

Definisi 2. 1. 6 Ruang Vektor Ruang vektor 𝑉 atas lapangan 𝐹 adalah suatu himpunan tak kosong 𝑉, dengan elemenelemennya dinamakan vektor, sebuah elemen dari 𝑉 yaitu 0 disebut vektor nol, bersama dengan sebuah operasi biner +, disebut penjumlahan vektor, dan suatu perkalian skalar dinotasikan ∗, dari vektor dengan elemen dari 𝐹; sedemikian rupa sehingga memenuhi sifat-sifat : a. Untuk Setiap 𝑢, 𝑣, 𝑤 𝜖 𝑉 1. 𝑢 + 𝑣 ∈ 𝑉 2. 0 + 𝑣 = 𝑣 3. 𝑢 + 𝑣 = 𝑣 + 𝑢 4. 𝑢 + 𝑣 + 𝑤 = 𝑣 + 𝑢 + 𝑤 b. Untuk setiap 𝑢, 𝑣 𝜖 𝑉 dan untuk setiap 𝑟, 𝑠 𝜖 F 5. 𝑟 ∗ 𝑣 ∈ 𝑉 6. 1 ∗ 𝑣 = 𝑣 7. 0 ∗ 𝑣 = 0 8. 𝑟(𝑢 + 𝑣) = 𝑟 ∗ 𝑢 + 𝑟 ∗ 𝑣 9. (𝑟 + 𝑠) ∗ 𝑣 = 𝑟 ∗ 𝑣 + 𝑠 ∗ 𝑣 10. (𝑟 ∗ 𝑠) ∗ 𝑣 = 𝑟 ∗ (𝑠 ∗ 𝑣) Kondisi a1 menyatakan 𝑉 tertutup terhadap operasi penjumlahan, sedangkan kondisi b5 menyatakan 𝑉 tertutup terhadap operasi perkalian skalar. Definisi 2. 1. 7 Subruang dari suatu ruang vektor 𝑉 adalah sebuah subhimpunan 𝑈 ⊆ V, sedemikian rupa sehingga 𝑈 merupakan suatu ruang vektor dengan operasi biner penjumlahan dan perkalian skalar yang dimiliki 𝑉. Definisi subruang berbeda dengan definisi subruang vektor, akan tetapi lemma berikut ini menunjukan kedua definisi tersebut mendefinisikan konsep yang sama. Lemma 2. 1. 8 Sebuah subhimpunan tak hampa 𝑈 ⊆ 𝑉 dari suatu ruang vektor V merupakan suatu subruang dari V jika dan hanya jika :

4

(i) Jika u, v 𝜖 V, maka 𝑢 + 𝑣 𝜖 𝑈 (ii) Jika 𝑘 𝜖 F dan 𝑢 𝜖 𝑈, maka 𝑘 ∗ 𝑢 𝜖 𝑈 Bukti : Bukti terdapat pada lampiran 1. Definisi 2. 1. 9 Misal F n suatu ruang vektor atas lapangan F , bentuk bilinier pada F n adalah suatu fungsi <,>: F n x F n  F yang memenuhi : a. < 𝑢, 𝑣 >=< 𝑣, 𝑢 > untuk setiap 𝑢, 𝑣 𝜖 F n b. < 𝑘 ∗ 𝑢, 𝑣 >= 𝑘 ∗< 𝑣, 𝑢 > untuk setiap k 𝜖 F dan untuk semua u,v 𝜖 F n c. < 𝑢 + 𝑣, 𝑤 >=< 𝑢, 𝑣 > +< 𝑣, 𝑤 >

Contoh 2.1.10 : Hasil kali titik pada 𝐹𝑛2 yang didefinisikan sebagai 𝑢 · 𝑣 = 𝑢1 𝑣1 + 𝑢2 𝑣2 + ⋯ + 𝑢𝑛 𝑣𝑛 untuk sebarang 𝑢 = (𝑢1 𝑢2 … 𝑢𝑛 ) dan 𝑣 = (𝑣1 + 𝑣2 + ⋯ + 𝑣𝑛 ) elemen dari 𝐹𝑛2 merupakan suatu bentuk bilinier pada 𝐹𝑛2 . Jika 𝑢 · 𝑣 = 0, u dan v dinamakan vektor-vektor yang saling orthogonal. Definisi 2. 1. 11 Misal V suatu ruang vektor atas lapangan F, dan W adalah subhimpunan tak kosong dari V. Komplemen orthogonal dari W di V didefinisikan sebagai subruang 𝑊⊥ (dibaca S perpendikular), dengan 𝑊⊥ = {𝑣 ∈ 𝑉| < 𝑣, 𝑤 ≥ 0 untuk semua 𝑤 ∈ 𝑊}. Definisi 2.1.12 Sebuah vektor 𝑤 disebut kombinasi linier dari vektor-vektor v1 , v2 ,..., vr , jika w dapat dituliskan dalam bentuk w  k1v1  k2v2  ...  kr vr , dengan k1 , k2 ,..., kr merupakan skalar. Definisi 2.1.13 Jika 𝑆 = {𝑣1 , 𝑣2 , … , 𝑣𝑟 } merupakan suatu subhimpunan dari suatu ruang vektor V, maka subruang W dari ruang vektor V, yang terdiri atas semua kombinasi linier dari vektor-vektor di S dinamakan ruang yang dibangun oleh 𝑣1 , 𝑣2 , … , 𝑣r . Selanjutnya, kita sebut vektor-vektor 𝑣1 , 𝑣2 , … , 𝑣r membangun W. Untuk menandakan 𝑊 adalah ruang yang dibangun oleh vektor-vektor di 𝑆 = {𝑣1 , 𝑣2 , … , 𝑣𝑟 } kita tuliskan 𝑊 = 𝑠𝑝𝑎𝑛(𝑆) atau 𝑊 = 𝑠𝑝𝑎𝑛{𝑣1 , 𝑣2 , … , 𝑣𝑟 }.

5

Definisi 2.1.14 Jika 𝑆 = {𝑣1 , 𝑣2 , … , 𝑣𝑟 } merupakan himpunan tak kosong dari vektorvektor, maka persamaan vektor 𝑘1 𝑣1 + 𝑘2 𝑣2 + ⋯ + 𝑘𝑟 𝑣r = 0 memiliki paling sedikit satu buah solusi yaitu 𝑘1 = 0, 𝑘2 = 0, … , 𝑘𝑟 = 0. Jika ini merupakan satu-satunya solusi, maka S dinamakan himpunan yang bebas linier. Jika terdapat solusi lain, maka S dinamakan himpunan yang bergantung linier. Definsi 2.1.14 Misal V suatu ruang vektor atas sebarang lapangan F, dan 𝑆 = {𝑣1 , 𝑣2 , … , 𝑣𝑟 } merupakan himpunan dari beberapa vektor di V. S dinamakan basis bagi V, jika terpenuhi dua buah kondisi berikut : a. S bebas liner b. S membangun V Contoh 2.1.15 Misal 𝑒𝑖 = (0,0, … ,1,0, … .0) vektor di 𝐹𝑛 dengan entri ke-i sama dengan 1 dan entri lainnya sama dengan nol. Dengan mudah dapat dilihat bahwa 𝑒1 , 𝑒2 , … , 𝑒𝑛 merupakan basis bagi 𝐹𝑛 . Secara umum 𝑒1 , 𝑒2 , … , 𝑒𝑛 dikenal sebagai basis standar bagi 𝐹𝑛 . Definisi 2.1.16 Misalkan V suatu ruang vektor dengan B merupakan basis bagi V, misal B terdiri dari sebanyak hingga elemen, sebut sebanyak n untuk suatu 𝑛 𝜖 𝑁. Maka kita sebut V berdimensi n. Jika V memiliki dimensi n, V disebut ruang vektor berdimensi hingga. Jika V tidak berdimensi hingga (tidak memiliki suatu basis dengan banyak elemennya berhingga), V disebut ruang vektor berdimensi tak hingga.

2.2 Teori Koding Definisi 2.2.1 Sebuah katakode dengan panjang n atas lapangan F adalah sebuah vektor elemen dari ruang vektor 𝐹𝑛 . Definisi 2.2.2 Kode dengan panjang n adalah kumpulan katakode dengan panjang n. Contoh 2.2.3 u=10011, v=11000, u dan v merupakan kata kode dengan panjang 5 atas lapangan F2 . Di samping itu, C ={10011, 11000,} merupakan kode dengan panjang 5.

6

Dalam Tugas Akhir kita hanya akan membahas tentang katakode dan kode atas lapangan biner. Selain itu, operasi penjumlahan kode pada ruang vektor yang dibangun atas lapangan biner dilakukan dalam modulo 2. Definisi 2.2.4 Bobot Hamming dari suatu kata kode x = 𝑥1 𝑥2 … 𝑥𝑛 ditulis wt(x) adalah banyaknya entri tak nol pada x. Definisi 2.2.5 Jarak Hamming antara dua buah kata kode x = 𝑥1 𝑥2 … 𝑥𝑛 dan y = 𝑦1 𝑦2 … 𝑦𝑛 dinotasikan dengan dist(x, y) adalah banyaknya posisi x dan y berbeda. Contoh 2.2.6 Untuk u=10011 dan v=11000, diperoleh wt(u)=3, wt(v)=2, dan dist(u,v)= dist(10011, 10001)=1. Perlu diperhatikan bahwa jarak Hamming antara sebarang dua katakode u dan v dengan panjang n sama dengan bobot Hamming dari (u+v), karena keduanya merujuk pada banyaknya posisi u dan v berbeda. sehingga diperoleh dist(u,v)=wt(u+v). Definisi 2.2.7 Misal C suatu kode, dan 𝑑 = min dist u, v , untuk setiap u ∈ 𝐶, v ∈ 𝐶, u ≠ v. d dinamakan jarak minimum kode C. Contoh 2.2.8 Kode C1 = {00, 10, 01, 11}. Jarak minimum kode C1 adalah 1. Dalam Tugas Akhir ini, istilah bobot Hamming ditulis sebagai bobot dan istilah jarak Hamming ditulis sebagai jarak. Disamping itu, istilah jarak minimum kode ditulis sebagai jarak minimum. Sekarang kita memasuki salah satu bagian penting dari teori koding, yaitu tentang kode pendeteksi dan pengoreksi kesalahan. Kode C dikatakan dapat mendeteksi pola kesalahan u jika dan hanya jika v + u ∉ C untuk setiap v ∈ C. Dengan kata lain, u dapat dideteksi oleh C bila setiap katakode v yang ditransmisikan, dekoder dapat mengenali bahwa katakode yang diterimanya, yakni u+v, bukan merupakan katakode; sehingga dapat disimpulkan terjadi kesalahan.

7

Suatu kode dikatakan kode pendeteksi t kesalahan bila ia dapat mendeteksi semua pola kesalahan taknol dengan bobot kurang dari atau sama dengan t, dan tidak dapat mendeteksi sedikitnya satu pola kesalahan dengan bobot t + 1. Teorema berikut ini menujukan setiap kode C dengan jarak d merupakan kode pendeteksi d-1 kesalahan. Teorema 2.2.9 Suatu kode C dengan jarak d akan dapat mendeteksi sedikitnya semua pola kesalahan taknol dengan bobot ≤ d−1. Tapi, ada sedikitnya satu pola kesalahan dengan bobot d yang tidak dapat dideteksi oleh C. Bukti : Bukti terdapat pada lampiran 2. Suatu kode C dikatakan dapat mengoreksi pola kesalahan u jika untuk semua v ∈ C, v+u berjarak lebih dekat ke v dibanding dengan jarak ke katakode lain di C. Kode C dikatakan kode pengoreksi t kesalahan bila ia mengoreksi semua pola kesalahan dengan bobot t dan tidak mengoreksi sedikitnya satu pola kesalahan dengan bobot t + 1. Teorema berikut ini menunjukan setiap kode C dengan jarak d merupakan kode pengoreksi [(d − 1)/2] kesalahan, (notasi [x] menujukan bilangan bulat terbesar yang kurang dari atau sama dengan bilangan riil x). Teorema 2.2.10 Suatu kode C berjarak d akan mengoreksi semua pola kesalahan dengan bobot kurang dari atau sama dengan [(d − 1)/2]. Namun, C tidak dapat mengoreksi sedikitnya satu pola kesalahan berbobot 1 + [(d − 1)/2]. Bukti : Bukti terdapat pada lampiran 3.

Contoh 2.2.11 Untuk kode C1 = {00, 10, 01, 11}. Maka setiap katakode yang diterima merupakan katakode di C1 , sehingga C1 tidak dapat mendeteksi adanya kesalahan. Kode C1 tidak dapat mengoreksi kesalahan karena setiap kata yang diterima tidak perlu perubahan untuk menjadi katakode. Contoh 2.2.12

Ubah kode C1 dengan mengulang setiap katakodenya 3 kali dan didapat

kode C2 = {000000, 101010, 010101, 111111}. Misal kata 111010 yang diterima. Karena kata ini tidak di C2 , maka kita dapat mendeteksi sedikitnya ada satu kesalahan. Untuk menjadikan katakode, kata 111010 perlu diubah sedikitnya pada satu digitnya menjadi 101010. Sehingga kita mengharap bahwa 101010 memang kata yang ditransmisikan, 8

sehingga kita mengoreksi 111010 menjadi 101010. Kode C2 dapat mengoreksi satu kesalahan. Definisi 2.2.14 Suatu kode C dengan panjang n atas lapangan F disebut kode linier jika C membentuk subruang dari ruang vektor 𝐹𝑛 . Definisi di atas memberikan pengertian bahwa kode linier adalah kode yang tertutup terhadap operasi penjumlahan katakode. Disamping itu, C tentulah memuat vektor nol, karena untuk sebarang 𝑣 ∈ C, mengakibatkan 𝑣 + 𝑣 = 0 ∈ C. Dalam Tugas Akhir ini, suatu kode linier C dengan panjang n, dimensi k, dan jarak minimum d ditulis sebagai kode 𝐶 [𝑛, 𝑘, 𝑑] . Contoh sederhana kode linier adalah C4 = {000, 111}, karena 000 + 000 = 000, 111 + 000 = 111, 000 + 111 = 111, dan 111 + 111 = 000 semuanya ada di C4. Namun, C5 = {000, 100, 110} bukan kode linier, karena 100 + 110 = 010 ∉ C5. Salah satu keunggulan menggunakan kode linier adalah mudah untuk dihitung jaraknya. Yakni, jarak suatu kode linier C sama dengan bobot terkecil katakode taknol di C. Kenapa demikian? Perhatikan penjelasan berikut ini. Misal jarak minimum C adalah k, dan v dan w dua katakode di C yang memberikan d(v,w) = k. Misal c bobot terkecil di C. Karena C linier maka z = v + w ∈ C, dan wt(z) = wt(v + w) = d(v,w) = k. Jadi 𝑐 ≤ 𝑘, karena c merupakan bobot terkecil di C. Sebaliknya, jika c bobot terkecil di C dan wt(u) = c, maka kelinieran C menjamin adanya 0 ∈ C, dan d(0, u) = c. Sehingga 𝑘 ≤ 𝑐, karena k merupakan jarak minimum di C. Jadi diperoleh 𝑘 = 𝑐. Misalkan C adalah kode linier [𝑛, 𝑘, 𝑑] atas F. Misalkan pula 𝐴𝑖 adalah banyaknya katakode yang berbobot 𝑖 di C . Enumerator bobot Hamming dari kode C adalah polinom homogen berderajat n dalam dua variabel, yaitu : WC x, y =

n n−i i y i=0 Ai x

Enumerator bobot hamming juga bisa ditulis menjadi : 𝑊𝐶 𝑥, 𝑦 =

𝑢 ∈𝐶

𝑥 𝑛−𝑤𝑡 (𝑢) 𝑦 𝑤𝑡 (𝑢)

Misal C kode linier [𝑛, 𝑘], kode dual atau kode orthogonal dari C, ditulis 𝐶⊥ adalah himpunan vektor-vektor yang ortogonal dengan semua katakode dari C. Secara eksplisit 9

kita dapat menuliskan 𝐶⊥ ={𝑣 ∈ (𝐹2 )𝑛 | 𝑣. 𝑤 = 0, untuk semua 𝑤 ∈ 𝐶}. Jika 𝐶 ⊂ 𝐶 ⊥ , kode C dinamakan kode swa-dual lemah(weakly self-dual), sedangkan jika 𝐶 = 𝐶 ⊥ , kode C dinamakan kode swa-dual(self-dual). Misal 𝐴𝑗 ′ adalah banyaknya katakode yang berbobot 𝑗 di 𝐶 ⊥ . Maka pencacah bobot Hamming dari kode 𝐶 ⊥ adalah polinom homogen berderajat n dalam dua variabel, yaitu : 𝑊𝐶 ⊥ 𝑥, 𝑦 = =

′ 𝑛−𝑗 𝑗 𝑛 𝑦 𝑗 =0 𝐴𝑗 𝑥 𝑢 ∈𝐶 ⊥

𝑥 𝑛−𝑤𝑡 (𝑢 ) 𝑦 𝑤𝑡 (𝑢 )

Untuk kode swa-dual C, tentulah C tidak memuat katakode berbobot ganjil. Andaikan terdapat v ∈ C dan v berbobot ganjil, akibatnya v. v = 1. Kontradiksi dengan C swa-dual (seharusnya v. v = 0). Lebih lanjut, untuk suatu n, kita bisa mendapatkan kode swa-dual dengan panjang n dan bobot setiap katakodenya merupakan kelipatan 4. Kode swa-dual semacam ini dinamakan kode swa-dual genap. Untuk kode swa-dual genap dengan panjang n, kode tersebut tentulah memuat katakode berbobot n. Karena vektor berbobot n tentu orthogonal dengan setiap katakode di C. Matriks Pembangun dari suatu kode linier 𝐶[𝑛, 𝑘, 𝑑] adalah suatu matriks 𝐺 berukuran 𝑘 x 𝑛, 𝑟𝑎𝑛𝑘(𝐺) = 𝑘, dan himpunan semua vektor baris dari 𝐺 merupakan basis bagi 𝐶. Untuk kode 𝐶 yang sama, didefinisikan Matriks Cek Paritas 𝐻, yaitu suatu matriks berukuran 𝑛 x (n − k), 𝑟𝑎𝑛𝑘(𝐻) = (𝑛 − 𝑘) , dan himpunan semua vektor kolom dari 𝐻 merupakan basis bagi 𝐶 ⊥ . Teorema 2.2.15 Matriks G dan H berturut-turut merupakan matriks pembangun dan matriks cek paritas untuk suatu kode linier 𝐶 jika dan hanya jika: i. Baris dari G bebas linier, ii. Kolom dari H bebas linier, iii. Banyaknya baris dari G + Banyaknya kolom dari H = Banyaknya kolom dari G = Banyaknya baris dari H, dan iv. GH = 0.

10

Bukti : Untuk (i), (ii), dan (iii) cukup jelas dari definisi matriks pembangun dan matriks cek paritas. Definisi kode dual menyebabkan (iv). Terbukti.

∎

Selanjutnya, karena 𝐻𝑇 𝐺𝑇 = (𝐺𝐻)𝑇 = 0 dan berdasar teorema 2. 2. 8, maka didapat teorema berikut : Teorema 2.2.16 H adalah matriks cek paritas dari 𝐶 jika dan hanya jika 𝐻𝑇 matriks pembangun dari 𝐶 ⊥ , G matriks pembangun dari C jika dan hanya jika 𝐺𝑇 matriks cek paritas dari 𝐶 ⊥ . Jadi, untuk kode swa-dual kita peroleh 𝐺 = 𝐻𝑇 . Sekarang kita tinjau suatu fakta menarik pada kode dual biner, yaitu pencacah bobot dari kode dual biner 𝐶 ⊥ ditentukan secara unik oleh pencacah bobot kode 𝐶. Fakta ini dinyatakan dalam teorema Mac Williams di bawah ini. Teorema ini memberikan jalan bagi kita untuk mendapatkan pencacah bobot kode dual 𝐶 ⊥ tanpa harus mendaftar katakode-katakode pada kode dual 𝐶 ⊥ . Teorema 2.2.17 (Teorema Mac Williams) Jika 𝐶 [𝑛, 𝑘, 𝑑] merupakan suatu kode linier biner dengan kode dualnya adalah 𝐶 ⊥ , maka 𝑊𝐶 ⊥ 𝑥, 𝑦 =

1 𝐶

𝑊𝐶 (𝑥 + 𝑦, 𝑥 − 𝑦),

(i)

dengan 𝐶 = 2𝑘 adalah banyaknya katakode di 𝐶. Persamaan (i) ekuivalen dengan persamaan : (ii)

𝑛 𝑘 =0

𝐴′𝑖 𝑥 𝑛−𝑘 𝑦 𝑘 =

(iii)

𝑢 ∈𝐶 ⊥

1 𝐶

𝑛 𝑖=0 𝐴𝑖

𝑥 𝑛−𝑤𝑡 (𝑢) 𝑦 𝑤𝑡 (𝑢) =

1 𝐶

(𝑥 + 𝑦)𝑛−𝑖 (𝑥 − 𝑦)𝑖 , atau 𝑢 ∈𝐶 (𝑥

+ 𝑦)𝑛 −𝑤𝑡(𝑢) (𝑥 − 𝑦)𝑤𝑡 (𝑢) .

Persamaan (i), (ii), dan (iii) dikenal sebagai identitas MacWilliams. Pembuktian Teorema Mac Williams memakai lemma berikut ini : Lemma 2.2.18 Misal f sebarang pemetaan yang didefinisikan pada 𝐹 𝑛 . Transformasi Hadamard 𝑓 dari f didefinisikan sebagai 𝑓 𝑢 = 11

𝑣∈𝐹 𝑛

−1

𝑢.𝑣

𝑓 𝑣 ,

𝑢 ∈ 𝐹𝑛 .

Jika 𝐶[𝑛, 𝑘, 𝑑] merupakan kode linier, maka

𝑢 ∈𝐶 ⊥

𝑓 𝑢 =

1 𝐶

𝑢 ∈𝐶 𝑓 (𝑢).

Bukti : Bukti terdapat pada lampiran 4.

Bukti Teorema Mac Williams : Cukup dibuktikan persamaan (iii). Misalkan 𝑓 𝑢 = 𝑥 𝑛−𝑤𝑡 (𝑢) 𝑦 𝑤𝑡 (𝑢) , sehingga diperoleh 𝑓 𝑢 =

𝑣∈𝐹 𝑛 (−1)

𝑓 𝑢 =

𝑢.𝑣 𝑛−𝑤𝑡 (𝑣) 𝑤𝑡 (𝑣)

𝑣∈𝐹 𝑛 (−1)

=

𝑛 𝑖=1

𝑥

𝑦

𝑢 1 𝑣1 +⋯+𝑢 𝑛 𝑣𝑛

1 𝑢𝑖𝑤 𝑤 =0 (−1)

. Misal 𝑢 = 𝑢1 … 𝑢𝑛 , 𝑣 = (𝑣1 … 𝑣𝑛 ), maka didapatkan :

𝑛 𝑖−𝑣𝑖 𝑣𝑖 𝑦 𝑖=1 𝑥

=

1 𝑣1 =0

1 𝑣2 =0 …

1 𝑣𝑛 =0

𝑛 𝑢 𝑖 𝑣𝑖 1−𝑣𝑖 𝑣𝑖 𝑥 𝑦 𝑖=1(−1)

𝑥 1−𝑤 𝑦 𝑤

Untuk 𝑢𝑖 = 0, notasi sigma menghasilkan 𝑥 + 𝑦. Jika 𝑢𝑖 = 1, notasi sigma memberikan 𝑥 − 𝑦.

Akibatnya,

𝑓 𝑢 = (𝑥 + 𝑦)𝑛 −𝑤𝑡 (𝑢) (𝑥 − 𝑦)𝑤𝑡 (𝑢) ,

persamaan ini menghasilkan

𝑢 ∈𝐶 ⊥

𝑥 𝑛−𝑤𝑡 (𝑢) 𝑦 𝑤𝑡 (𝑢) =

1 𝐶

terapkan lemma 𝑢 ∈𝐶 (𝑥

2.2.18 pada

+ 𝑦)𝑛−𝑤𝑡 (𝑢 ) (𝑥 − 𝑦)𝑤𝑡 (𝑢) . ∎

Terbukti.

12