BAB 2 LANDASAN TEORI

BAB 2 LANDASAN TEORI

Pada bab ini akan dijelaskan mengenai teori – teori yang berhubungan dengan penelitian sehingga dapat dijadikan sebagai landasan berfikir dalam melakukan penelitian dan akan mempermudah dalam hal pembahasan hasil utama pada bab berikutnya. Adapun teori – teori tersebut mencakup pengertian dari ring, field, polynomial, generating matrix, dan check matrix. 2.1 Ring dan Field Pada bagian ini akan diberikan beberapa definisi dan teorema dasar tentang field dan ring. Definisi 2.1 : Suatu ring adalah suatu himpunan tak kosong R dengan dua operasi biner yang dinotasikan dengan operasi “penjumlahan” dan “perkalian” sehingga memenuhi aksioma – aksioma 1. untuk semua , berlaku 2. untuk semua , berlaku 3. R mempunyai unsur identitas relatif terhadap operasi penjumlahan, yakni terdapat suatu unsur sehingga untuk semua 4. untuk setiap , terdapat sehingga 5. untuk semua , berlaku 6. untuk semua , dipenuhi, a) b) Dari definisi 2.1 juga dapat dikatakan bahwa suatu himpunan tak kosong R dengan operasi biner “+” dan “” dikatakan suatu ring bila 1. adalah suatu grup komutatif 2. adalah suatu semigrup 3. operasi perkalian adalah distributif terhadap penjumlahan, yakni untuk semua dan

Universitas Sumatera Utara

Jika operasi perkalian dari R adalah komutatif, maka R disebut sebagai ring komutatif. Jika terdapat suatu unsur yang dinotasikan dengan 1 sedemikian hingga untuk semua , maka R disebut sebagai ring dengan unsur kesatuan, dan unsur 1 disebut sebagai unsur kesatuan. Selanjutnya apabila memungkinkan penulisan notasi cukup dituliskan saja.

Definisi 2.2 : Suatu ring komutatif F dengan unsur kesatuan disebut sebagai field bilamana setiap unsur tak nol adalah unsur satuan. Definisi di atas juga dapat dinyatakan sebagai berikut. Suatu field F adalah suatu struktur aljabar dengan dua operasi biner “+” dan “” sehingga 1. adalah suatu grup komutatif 2. adalah suatu semigrup 3. operasi perkalian adalah distributif terhadap penjumlahan, yakni untuk semua dan

2.2 Ring Polinomial Andaikan R adalah suatu ring komutatif. Himpunan R[x] = {a0 + a1x + a2x2 + … + anxn ; ai R dan n Z+} disebut sebagai ring polynomial atas R dalam indeterminate x. Pada definisi di atas, symbol x, x2, …, xn tidak menyatakan suatu variabel yang berasal dari ring R, tetapi symbol – symbol tersebut semata – mata hanyalah sebagai suatu tempat penyimpanan yang pada suatu saat mungkin saja digantikan dengan unsur R. Dua unsur di R[x] a0 + a1x + a2x2 + … + anxn dan b0 + b1x + b2x2 + … + bmxm dikatakan sama jika dan hanya jika ai = bi untuk semua bilangan bulat tak negatif i. Tentu saja pada definisi ini harus mengambil ai = 0 jika i > n dan bi = 0 jika i > m.


Selanjutnya perhatikan suatu polynomial a(x) = a0 + a1x + a2x2 + … + anxn di R[x]. Pada polynomial ini, bentuk akxk disebut sebagai suku dari polynomial a(x) dan untuk setiap suku akxk, k = 0,1,…,n, ak disebut sebagai koefisien dari xk. Derajat dari suatu polynomial a(x) adalah bilangan bulat positif terbesar n sehingga an 0. Dengan kata lain suatu polynomial a(x) = a0 + a1x + a2x2 + … + anxn dikatakan berderajat s, jika as 0 dan an

0 untuk semua k > s. Derajat dari a(x) ditunjukkan dengan deg(a), atau deg[a(x)]. Deg(a) = 0 jika dan hanya jika a(x) adalah polynomial konstan (constant polynomial) yang tak nol, yaitu, jika dan hanya jika a(x) adalah polynomial ao, untuk tak nol a0 R. Bila a(x) adalah polynomial berderajat s, maka koefisien as disebut sebagai koefisien utama (leading coefisien) dari a(x). Polinomial a(x) dikatakan sebagai polynomial monic jika koefisien utamanya adalah 1. Himpunan semua polynomial atas R ditunjukkan dengan R[x]. Selanjutnya akan dilakukan abstraksi dari konsep pembagian polynomial, yakni konsep pembagian pada polynomial atas suatu field F. Teorema berikut ini memperlihatkan secara umum bahwa dapat dilakukan pembagian polynomial atas sebarang field F.

Teorema 2.1 : Andaikan F adalah suatu field. Bila f(x), g(x) F[x] dengan g(x) 0, maka terdapat polynomial q(x) dan r(x) di F[x] yang tunggal sehingga f(x) = g(x)q(x) + r(x) dengan r(x) = 0 atau derajat r(x) lebih kecil dari derajat g(x). Bukti : Dengan menggunakan induksi pada derajat polynomial f(x) akan diperlihatkan keberadaan polynomial q(x) dan r(x). Jika f(x) = 0 atau derajat f(x) lebih kecil dari derajat g(x), maka q(x) dan r(x) diperoleh r(x) = f(x) dan q(x) = 0. Selanjutnya, andaikan f(x) berderajat n dan g(x) berderajat m dengan n > m. Misalkan f(x) = a0 + a1x + a2x2 + … + anxn g(x) = b0 + b1x + b2x2 + … + bmxm


Dengan menggunakan teknik pembagian seperti di atas, misalkan h(x) = f(x) – anb-1mxn-mg(x) Sehingga h(x) = 0 atau derajat h(x) lebih kecil dari derajat f(x). Dengan menggunakan asumsi pada induksi, untuk polynomial h(x) terdapat polynomial q1(x) dan r1(x) sehingga h(x) = g(x)q1(x) + r1(x) dengan r1(x) = 0 atau derajat r1(x) lebih kecil dari derajat g(x). Hal ini berakibat

f(x) = anbm-1xn-mg(x) + h(x) = anbm-1xn-mg(x) + g(x)q1(x) + r1(x) = g(x) [anbm-1xn-m + q1(x)] + r1(x)

Dengan mengambil q(x) = anbm-1xn-m + q1(x) dan r(x) = r1(x), diperoleh f(x) = g(x) q(x) + r(x) Dengan r(x) = 0 atau derajat r(x) lebih kecil dari derajat g(x). Selanjutnya akan diperlihatkan ekspresi f(x) = g(x) q(x) + r(x) adalah tunggal. Misalkan f(x) juga dapat ditulis sebagai f(x) = g(x) s(x) + t(x) dengan t(x) = 0 atau derajat t(x) lebih kecil dari derajat g(x). Perlihatkan bahwa g(x) q(x) + r(x) = g(x) s(x) + t(x) Sehingga g(x) [q(x) – s(x)] = t(x) – r(x) Karena derajat t(x) – r(x) lebih kecil dari derajat g(x), maka haruslah q(x) – s(x) = 0. Yakni, q(x) = s(x) dan tentunya r(x) = t(x). Polinomial q(x) disebut quotient dan r(x) disebut remainder (sisa) dalam pembagian f(x) dengan g(x). Jika f(x), g(x) F[x] dengan g(x) 0, maka f(x) dapat dibagi dengan g(x) atas F jika f(x) = g(x) q(x) untuk q(x) F[x]. Jika f(x) dapat dibagi dengan g(x) (atas F), maka dapat dikatakan g(x) adalah faktor dari f(x) (atas F). Suatu elemen c F disebut akar (atau pembuat nol) dari polynomial f(x) F[x] jika f(c) = 0.


Akibat langsung dari teorema di atas diperoleh hasil sebagai berikut. Akibat 2.1 : Andaikan F adalah suatu field. Bila a F dan f(x) F[x], maka f(a) adalah sisa hasil bagi dari f(x) oleh (x– a). Bukti : Menurut teorema 2.1 untuk polynomial f(x) dan (x– a) terdapat polynomial q(x), r(x) F[x] sehingga f(x) = (x– a) q(x) + r(x) dengan derajat r(x) lebih kecil dari derajat (x– a). Akibatnya r(x) adalah suatu konstanta yang berada di F, sehingga f(x) = (x– a) q(x) + r. Karena f(x) F[x], untuk x F kita dapat memandang f sebagai suatu pemetaan f : F F. Sehingga f(x) = (a– a) q(a) + r, yakni sisa hasil bagi r = f(a).

Akibat 2.2 : Andaikan F adalah suatu field, dan misalkan a F dan f(x) F[x]. Unsur a adalah pembuat nol dari f(x) jika dan hanya jika (x – a) adalah faktor dari f(x). Bukti : Dengan menggunakan algoritma pembagian, maka polynomial f(x) dapat ditulis sebagai f(x) = (x– a) q(x) + r(x) dengan r(x) = 0 atau derajat dari r(x) adalah 0. Bila a pembuat nol dari f(x) maka f(a) = 0 = (a– a) q(x) + r, yang berakibat r = 0. Jadi (x – a) adalah faktor dari f(x). Sebaliknya jika (x – a) adalah faktor dari f(x), maka terdapat polynomial q(x) F[x] sehingga f(x) = (x– a) q(x). Hal ini berakibat f(a) = (a– a) q(a) = 0q(a) = 0. Jadi a adalah pembuat nol dari f(x).

Akibat 2.3 : Bila F adalah suatu field, maka suatu polynomial di F[x] yang berderajat n 1 mempunyai paling banyak n akar.


Bukti : Andaikan f(x) adalah suatu polynomial berderajat n di F[x]. Akan diperlihatkan pernyataan di atas dengan menggunakan induksi pada derajat dari f(x). Andaikan f(x) adalah polynomial berderajat n = 1. Misalkan f(x) = ax + b, dengan a, b F dan a 0. Akibatnya ab-1 adalah akar dari f(x). Sekarang andaikan f(x) berderajat n > 1. Andaikan adalah pembuat nol dari f(x). Menurut akibat 2.1, f(x) dapat ditulis sebagai f(x) = (x– a) g(x) dengan g(x) adalah polynomial berderajat n – 1. Jika adalah akar dari f(x), maka 0 = f() = (– ) g(). Karena – , maka g() = 0. Yakni adalah pembuat nol dari g(). Tetapi menurut hipotesis induksi g() mempunyai banyak n – 1 akar. Sehingga f mempunyai paling banyak n akar.

Definisi 2.3 : Andaikan f(x) = a0 + a1x + a2x2 + … + anxn adalah suatu polynomial di Z[x]. Isi dari f(x) didefinisikan sebagai pembagi persekutuan terbesar dari a(x) = a0 , a1 , …, an. Suatu polynomial f(x) Z[x] dikatakan primitip jika isi dari f(x) adalah 1.

Contoh 2.2.1 : Isi dari polynomial f(x) = 6 + 4x + 10x2 + 18x6 adalah 2, karena pembagi persekutuan terbesar dari 6, 4, 10 dan 18 adalah 2. Sementara isi dari polynomial g(x) = 3x + 9x3 + 4x5 adalah 1. Sehingga g(x) adalah primitip. Definisi 2.4 : Untuk suatu polynomial monik f(x) dengan derajat tak nol atas field F, ring polynomial modulo f(x) adalah himpunan semua polynomial dengan derajat lebih kecil dari f(x), bersama dengan penjumlahan dan perkalian polynomial modulo f(x). Ring ini biasanya ditunjukkan dengan F(x) /


Selanjutnya, a(x) kongruens ke b(x) modulo f(x), ditunjukkan dengan a(x) b(x) (modulo ), jika dan hanya jika terdapat c(x) dengan a(x) = c(x) f(x) + b(x). Untuk setiap polynomial monik f(x) dengan derajat tak nol, misalkan F(x) / yang menunjukkan himpunan kelas – kelas kongruens dari polynomial di F[x] modulo f(x). Ini disebut ring polynomial modulo f(x). Ini adalah suatu ring yang terdiri dari semua polynomial dengan derajat yang lebih kecil dari derajat f(x).

Teorema 2.2 : F(x) / adalah field jika dan hanya jika f(x) irreducible. Bukti : Misalkan I merupakan principal ideal f(x). Andaikan f(x) reducible atas F, katakan f(x) = a(x)b(x) dengan a(x) dan b(x) keduanya berderajat lebih rendah dari p(x). F[x]/I bukan suatu field. Derajat polynomial tak nol di I harus paling sedikit sebesar degf(x), jadi a(x) I dan b(x) I. Oleh karena itu I + a(x) dan I + b(x) keduanya elemen tak nol F[x]/I. Tetapi (I + a(x))(I + b(x)) = I + a(x)b(x) = I + f(x) = I, elemen nol dari F[x]/I. Disimpulkan, F[x]/I memiliki pembagi nol sehingga F[x]/I bukan field (bukan juga daerah integral). Ini membuktikan bahwa F[x]/I suatu field, maka f(x) irreducible. Andaikan f(x) irreducible. F[x]/I komutatif dan I + e adalah unsur kesatuan untuk F[x]/I (dengan e unsure kesatuan dari F). Jadi ini mencukupi untuk membuktikan setiap elemen tak nol dari F[x]/I memiliki perkalian inverse di F[x]/I. Ambil I + F[x] tak nol. Maka f(x) I, berarti r(x) bukan perkalian f(x) di F[x]. Karena f(x) irreducible, ini menyatakan secara tidak langsung bahwa f(x) dan r(x) memiliki pembagi bersama terbesar e. Oleh karena itu e = f(x)u(x) + r(x)v(x) untuk u(x),v(x) F[x]. Berarti e – r(x)v(x) = f(x)u(x) I, dan oleh karena I + e = I + r(x)v(x) = (I + r(x))(I + v(x)). Ini menunjukkan bahwa I + v(x) adalah perkalian invers dari I + r(x).


Definisi 2.5 : Suatu elemen primitip dari field GF(q) adalah elemen sehingga setiap elemen field kecuali nol dapat ditulis sebagai pangkat dari . Contoh 2.2.2 : Field GF(5) 21 = 2, 22 = 4, 23 = 3, 24 = 1 Dan dengan demikian 2 adalah elemen primitip dari GF(5). Jadi, adalah elemen primitip dari F jika setiap elemen tak nol di F adalah pangkat dari . Suatu elemen primitip di field dengan q elemen memiliki order q – 1. Tidak selalu akar dari polynomial irreducible adalah elemen primitip. Suatu polynomial irreducible yang memiliki elemen primitip sebagai akar disebut polynomial primitip. Dengan menemukan irreducible polynomial berderajat n atas GF(p), pembentukan field berhingga dengan pn elemen dapat dilakukan. Contoh, pembentukan field dengan 16 elemen, atau GF(24), menggunakan polynomial f(x) = x4 + x3 + 1. Misalkan adalah akar dari f(x), f() = 4 + 3 + 1 = 0, sehingga 4 = 3 + 1.


Tabel 2.1 Representasi GF (24) Bentuk Pangkat

Bentuk n - Tuple

Bentuk Polinomial

0

0000

0

1

1000

1

0100

2

0010

2

3

0001

3

4

1001

1 + 3

5

1101

1 + + 3

6

1111

1 + + 2 + 3

7

1110

1 + + 2

8

0111

+ 2 + 3

9

1010

1 + 2

10

0101

+ 3

11

1011

1 + 2 + 3

12

1100

1+

13

0110

+ 2

14

0011

2 + 3

Dengan menentukan setiap pangkat dari, mempermudah menentukan invers dari suatu elemen dan mengalikan dua elemen. Contoh, invers dari 3 + 1. Karena 3 + 1 = 4 dan 4 11= 15 = 1 sehingga (3 + 1)–1 = 11 = 3 + 2 + 1. Teorema 2.3 : Misalkan m(x) adalah minimal polynomial dengan elemen di finite field GF(pr). Maka yang fakta – fakta berikut diperoleh : 1. m(x) irreducible. 2. Jika adalah akar dari polynomial f(x) dengan koefisien – koefisien di GF(p), maka m(x) membagi f(x). r

3. m(x) membagi x p = x. 4. Jika m(x) adalah primitip, maka derajatnya adalah r. Dalam suatu kasus derajat m(x) r.


Bukti : 1. Jika m(x) irreducible, maka m(x) = a(x)b(x) dan m() = 0, salah satunya a(x) atau b(x) adalah 0 menyangkal fakta bahwa m(x) adalah polynomial dengan derajat terkecil dengan sebagai akar. 2. Dengan algoritma pembagian, f(x) = a(x)m(x) + r(x) dengan derajat r(x) lebih kecil dari derajat m(x). Karena f() = m() = 0, r() = 0 dan karena derajat r(x) lebih kecil dari derajat m(x), r(x) sama dengan 0. 3. Ini mengikuti dari (2) karena suatu elemen di GF(pr) adalah akar dari persamaan x p

r

= x. 4. Karena

di GF(pr) dan GF(pr) adalah r – dimensional vector space atas GF(p),

himpunan 1, , …, r adalah linierly independent dan juga memenuhi persamaan derajat lebih kecil

dari atau sama dengan r. Jika m(x) adalah primitip

membangkitkan semua GF(pr) dan juga m(x) memiliki derajat r. Jika f(x) adalah polynomial berderajat m, reciprocal polynomial dari f(x) didefinisikan menjadi xmf(x-1). Jika f(x) = anxn + an-1xn-1 +…+ a0, reciprocal polynomialnya sama dengan a0xn + a1xn-1 +…+ an.

2.3 Mengubah Codeword dalam Bentuk Polinomial Information digit yang berupa barisan digit 0 dan 1 merupakan elemen dari kode yang disebut codeword. Misalkan, suatu kode yang terdiri dari semua codeword dengan panjang dua adalah C = {00, 01, 10, 11} Suatu codeword v = a0a1a2…an-1 dengan panjang n dapat diubah dalam bentuk polynomial f(x) = a0 + a1x + a2x2 + … + an-1xn-1 berderajat n.Contoh, codeword dengan panjang 7; v = 1000111 diubah dalam polynomial f(x) = 1 + x4 + x5 + x6. Jadi suatu kode dengan panjang n dapat ditunjukkan sebagai himpunan polynomial atas GF(2) berderajat n – 1.


2.4 Cyclic Codes Cyclic codes adalah kelas yang penting dari kode. Salah satu alasannya adalah dapat diencode secara efisien dengan memakai shift register. Begitu juga dengan pola decoding yang memakai shift register. Polinomial v(x) = a0 + a1x + a2x2 + … + an-1xn-1 dapat dianggap sebagai codeword v = a0a1a2…an-1. Suatu (n,k) code C disebut cyclic jika x = (a0, a1, a2,… ,an-1) di C, begitu juga cyclic shift pertamanya y = (an-1, a0, a1,…, an-2). Ini berarti (an-2, an-1, a0, …, an-3), cyclic shift dari y yang pertama, dan semua cyclic shift yang lain dari x juga di C. Misalkan suatu vector (a0, a1, a2,… ,an-1) dapat disamakan dengan polynomial a0 + a1x + a2x2 + … + an-1xn-1. Maka (an-1, a0, a1,…, an-2) dapat disamakan dengan an-1 + a0x + a1x2 + … + an-2xn-1. Jadi polynomial ini sama dengan polynomial (a0 + a1x + a2x2 + … + an-1xn-1)x(modulo ). Misalkan v adalah codeword dengan panjang n. Cyclic shift dari v adalah codeword dengan panjang n yang diperoleh dari v dengan mengambil digit terakhir dari v dan memindahkan nya menjadi digit paling awal, semua digit yang lain berpindah satu posisi ke kanan. Suatu kode dikatakan cyclic code jika cyclic shift dari setiap codeword juga merupakan codeword. Untuk cyclic code, elemen dari kode bisa dikatakan sebagai codeword dan polynomial. Diberikan suatu codeword v dengan panjang n, misalkan codeword dapat disamakan dengan polynomial v(x), maka cyclic shift dari v dapat disamakan dengan polynomial xiv(x) (mod ) untuk i = 0, 1, …, n – 1. Cyclic codes didasarkan pada Rn = F[x]/ , yang terdiri dari kelas – kelas kongruens dari polynomial – polynomial berderajat lebih kecil dari n di F[x] tetapi perkaliannya adalah modulo (xn – 1). Secara eksplisit, jika terdapat dua polynomial a(x) dan b(x), hasil kalinya di F[x] adalah a(x)b(x) = c(x(xn – 1) + r(x) dengan derajat r(x) lebih kecil dari derajat xn – 1 dengan algoritma pembagian. Jadi r(x) dianggap sebagai hasil kali dari a(x) dan b(x) dengan Rn adalah himpunan semua polynomial di F[x] berderajat yang lebih kecil dari n dengan perkalian modulo (xn – 1). Misalkan , …, r adalah elemen di field F = GF(qm) dan misalkan f1(x), …, fr(x) adalah minimal polynomial dari setiap . Selanjutnya, misalkan n adalah bilangan bulat sehingga setiap fi(x) membagi xn – 1. Misalkan C adalah kode dengan panjang n yang terdiri


dari semua polynomial h(x) di F[x]/ sehingga h(i) = 0, i = 1, …, r. Maka C adalah cyclic codes dengan generator polynomial g(x) = lcm(f1(x), …, fr(x)). Jelas bahwa cyclic codes C dapat ditentukan dengan cara ini karena f1(x) dapat diambil sebagai factor yang irreducible dari generator polynomial dari C dan i adalah akar dari f1(x). 2.5 Generating Matrix dan Check Matrix Suatu ideal I di Rn = F[x]/ disebut principal ideal jika setiap elemen di I adalah perkalian dari polynomial g(x) tertentu. Jika I adalah principal, maka I = {c(x)g(x); c(x) di Rn }. Ditunjukkan dengan I = . Suatu ring disebut principal ideal ring (PIR) jika setiap ideal adalah principal.

Teorema 2.4 : Jika C adalah ideal (yaitu suatu cyclic code dengan panjang n) di Rn, misalkan g(x) adalah polynomial monik dengan derajat terkecil di C. Maka g(x) tunggal dan C = . Bukti : Akan ditunjukkan bahwa Rn adalah suatu P.I.R dan monic generator dengan derajat terkecil dari ideal adalah tunggal sekalipun ideal dapat memiliki generator lain. Pertama ditunjukkan Rn adalah PIR. Misalkan g(x) adalah polynomial monik dengan derajat terkecil di C dan misalkan a(x) polynomial lain di C. Dengan algoritma pembagian di F[x], a(x). Dengan definisi ideal r(x) di C. Tetapi ini menyangkal pilihan g(x) kecuali kalau r(x) sama dengan nol sehingga a(x) = g(x)b(x). Oleh karena itu Rn adalah PIR. Jika g(x) dan h(x) adalah polynomial monik dengan derajat yang sama dan keduanya di C, maka g(x) – h(x) adalah polynomial di C dengan derajat yang lebih rendah dari g(x) atau h(x). Ini tidak dapat terjadi jika g(x) memiliki derajat terkecil. Jadi g(x) adalah polynomial monik tunggal dengan derajat terkecil di C dan C = .


Teorema berikut memberitahukan bagaimana menemukan generator dari cyclic code. Teorema 2.5 : Jika C adalah suatu ideal, monic generator tunggal, g(x), dari C dengan derajat terkecil yang membagi xn – 1 dan sebaliknya jika polynomial g(x) di C membagi xn – 1, maka g(x) memiliki derajat terrendah di . Bukti : Pertama andaikan bahwa g(x) adalah polynomial monik dengan derajat terkecil di C. Dengan algoritma pembagian di F[x], xn – 1 = a(x)g(x) + r(x) dengan derajat r(x) lebih kecil dari derajat g(x). r(x) = – a(x)g(x) modulo (xn – 1) dan jadi r(x) di . Ini kontradiksi kecuali kalau r(x) sama dengan nol. Jadi g(x) membagi xn – 1. Sebaliknya, andaikan g(x) membagi xn – 1 dan b(x) di tetapi memiliki derajat yang lebih rendah dari g(x). Maka b(x) = c(x)g(x) + (xn – 1)d(x) di F[x] karena b(x) di C. Bagaimanapun, karena g(x) membagi xn – 1, g(x) membagi b(x), ini kontradiksi. Polinomial monik g(x) dengan derajat terkecil di C disebut generator polynomial dari C. Dengan teorema sebelumnya diketahui C = dan g(x) membagi xn – 1.

Teorema 2.6 : Jika derajat g(x) adalah n – k, maka dimensi dari C = adalah k. Jika g(x) = g0 + g1x + g2x2 + … + gn-kxn-k, maka generator matrix dari C sebagai berikut.

g0 g1 0 g 0  0 0  0 0

... gn-k ... gn-k-1 ... ...

0 0 ... 0  gn-k 0 ... 0  M M ... 0   g0 g1 ... gn-k 

Bukti : Vektor – vektor g(x), g(x)x,g(x)x2, …, g(x)xk-1 adalah linierly independent jika tidak maka terdapat elemen – elemen field ai, 0 i k – 1, sehingga a0gx+ a1gx x + a2gx x2 + … + ak-1gxxk-1 = (a0 + a1x + a2x2 + … + ak-1xk-1)g(x) = 0.


Tetapi hasil kali ini memiliki derajat lebih kecil dari n jadi ini tidak dapat menjadi 0 modulo (xn – 1) kecuali kalau setiap ai adalah 0. Untuk melihat bahwa vektor – vektor ini span C, catatan bahwa s(x) di C dapat diekspresikan sebagai c(x)g(x) dengan derajat c(x) lebih kecil dari atau sama dengan k – 1. Karena itu c(x)g(x) = (c0 + c1x + c2x2 + … + ck-1xk-1)g(x) = c0gx+ c1gx x + … + ck-1gxxk-1 Dari sini bahwa generator matrix dari C adalah matrix yang baris pertamanya adalah g(x), baris keduanya g(x)x, baris ketiga g(x)x2, …, hingga g(x)xk-1. Andaikan g(x) adalah generator polynomial dari cyclic code C. Diketahui bahwa g(x) membagi g(x) membagi xn – 1 sehingga xn – 1 = g(x)h(x). Jika g(x) memiliki derajat h(x) membagi xn – 1, ini adalah generator polynomial dari cyclic code C’ dengan dimensi n – k. !

memiliki dimensi n – k dan ini tentu sesuai jika h(x) generator polynomial dari

!

.

g(x)h(x) = 0 di Rn tetapi ini tidak mengikuti dari ini bahwa inner product dari dua vector g(x) dan h(x) adalah 0. Pada kenyataannya tidak benar pada umumnya bahwa h(x) generator dari !

. Jika xn – 1 = g(x)h(x), dan g(x) adalah generator polynomial dari cyclic code C, maka

h(x) disebut check polynomial dari C.

2.6 Istilah Matrix

a c   maka berlaku aturan berikut. b d 

Misalkan diberikan matriks A = 

a b   c d 

•

T Transpose A = A' = A = 

•

Determinan matriks A = A = 

a c   = ad − bc b d 

Jika |A| = 0, maka A matriks singular. JIka |A| 0, maka A nonsingular.


−1

1 1  d − c adj.A =  A A − b a 

•

Invers matriks A = A =

•

Matriks identitas I = 

•

Determinan matriks berukuran 3× 3 .

1 0  0 1

a b c  a b c a b A = d e f  , maka A = d e f d e = (aei + bfg + cdh) − (bdi + afh + ceg ) g h i  g h i g f


BAB 2 LANDASAN TEORI

Recommend Documents