3
BAB II TINJAUAN PUSTAKA Pada bab ini akan dituliskan beberapa aspek teoritis berupa definisi, teorema dan sifat-sifat yang berhubungan dengan aljabar linear, struktur aljabar dan teori koding yang digunakan sebagai landasan teori untuk penulisan tesis ini.
2.1 Struktur Aljabar Definisi 2.1.1 Operasi Biner Operasi biner
pada suatu himpunan S adalah suatu fungsi dari S
membawa setiap (a,b)
S
S ke a
b
S yang unik. Jadi (a,b)
a
S yang
b. Karena a
b juga berada dalam S maka dikatakan S tertutup di bawah operasi . ( Aliatiningtyas 2002) Definisi 2.1.2 Grup Struktur aljabar G dengan operasi biner
disebut grup jika memenuhi aksioma-
aksioma berikut ini: 1. operasi bersifat assosiatif (x 2. ada unsur identitas e
y
,
, ,
, sehingga berlaku e
ada unsur x-1
3. untuk setiap x
z=x
. ,
.
sehingga x x-1 = x-1 x = e. (Aliatiningtyas 2002)
Definisi 2.1.3 Subgrup Misalkan G grup dan H
. Maka H disebut subgrup dari G jika H grup di bawah
operasi biner yang sama dengan G.( notasi: H
). (Aliatiningtyas 2002)
Teorema 2.1.4 ( teorema Langrange) Jika G grup hingga dan H adalah subgrup G, maka order dari H membagi order dari G. (Aliatiningtyas 2002) Definisi 2.1.4 Field Suatu himpunan
yang padanya didefinisikan operasi jumlah (+) dan operasi kali (.)
disebut field, notasi ( , +, . ), jika memenuhi sifat-sifat berikut: 1. ( , + ) merupakan grup komutatif terhadap +, yaitu memenuhi sifat-sifat:
4
a. Assosiatif: ( b.
, ,
,
mempunyai unsur identitas: ( ! 0
c. Setiap unsur dari
0
mempunyai invers:
!
0
,
, 0,
0, dalam hal ini ,
d. Komutatif:
.
2. ( , . ), dimana
\ 0 , merupakan grup komutatif terhadap ., bersifat:
, ,
a. Assosiatif: b.
=
,
mempunyai unsur identitas: ( ! 1
c. Setiap unsur dari :(
.1
)( !
mempunyai invers:(
dalam hal ini d.
1.
)
1,
dan , ,
.
3. Berlaku sifat distributif . terhadap + :
, ,
.
atau
(Guritman 2005) 2.1.5 Definisi Finite Field dikatakan berhingga (finite field) jika himpunannya memiliki banyak
Suatu field
elemen yang berhingga. Order
adalah banyaknya anggota . (Menezes et al. 1997)
2.2. Aljabar linear Definisi 2.2.1: Ruang Vektor Misalkan Fq merupakan field hingga dengan order q . Himpunan tak kosong V (dengan penjumlahan vektor dan perkalian skalar oleh elemen Fq ) merupakan ruang vektor dari Fq jika untuk semua u , v ∈ V dan untuk semua λ , μ ∈ Fq , maka berlaku: 1. u + v ∈V 2. (u + v) + w = u + (v + w) 3.
∃ unsur
0 ∈V dimana 0 + v = v = v + 0, ∀v ∈V
4. ∀u ∈ V , ∃ − u ∈ V dimana u + ( −u ) = 0 = ( −u ) + u 5. u + v = v + u 6. λ ⋅ v ∈ V
5
7.
λ ⋅ (u + v ) = λ ⋅ u + λ ⋅ v
8.
(λ + μ ) ⋅ u = λu + μu
9.
( λμ ) ⋅ u = λ ( μ ⋅ u )
10. Jika 1 merupakan unsur identitas untuk perkalian di Fq maka 1u =u. (Ling & Xing 2004) Definisi 2.2.2: Penjumlahan Vektor dan Perkalian Skalar di Fqn Misalkan Fqn merupakan himpunan dari vektor-vektor dengan panjang n yang unsur-unsurnya merupakan elemen dari Fq , yaitu: Fqn = {u1 , u2 , u3 ,K, un } ; ui ∈ Fq . Misalkan pula v = ( v1 , v2 ,K, vn ) ∈ Fqn {v1 , v2 ,K, vr } , w = ( w1 , w2 ,K, wn ) ∈ Fqn , dan
λ ∈ Fq . maka
penjumlahan
vektor
di
Fqn
didefinisikan
sebagai
u + w = ( v1 + w1 , v2 + w2 ,K, vn + wn ) ∈ Fq , sedangkan perkalian skalar didefinisikan sebagai λ ⋅ v = ( λ v1 , λ v2 ,K , λ vn ) ∈ Fqn . (Ling & Xing 2004) Definisi 2.2.3: Subruang (Subspace) Suatu himpunan tak kosong C dari ruang vektor V merupakan subruang (ruang bagian) dari V jika C merupakan ruang vektor dan memiliki sifat penjumlahan vektor dan perkalian vektor yang sama dengan V . (Ling & Xing 2004) Definisi 2.2.4: Kombinasi Linear Misalkan V
merupakan ruang vektor atas Fq , λi ∈ Fq sembarang,
maka
λ1u1 + λ2u2 +K + λr ur merupakan kombinasi linear dari u1 , u2 ,K, ur .elemen V. (Ling & Xing 2004) Definisi 2.2.5: Bebas Linear Misalkan V merupakan ruang vektor terhadap Fq , himpunan vektor {v1 , v2 ,K, vr } dalam V dikatakan saling bebas linear jika
λ1v1 + λ2 v2 + K + λr vr = 0 → λ1 = λ2 = K = λr = 0 , tak bebas linear jika,
λ1v1 + λ2 v2 + K + λr vr = 0 ∧ ∃λi ≠ 0 .
6
(Ling & Xing 2004) Definisi 2.2.6: Rentang Linear Misalkan V merupakan ruang vektor atas Fq dan S = {v1 , v2 ,K, vk } merupakan himpunan tak kosong dari V . Rentang linear dari S didefinisikan sebagai S = {λ1v1 + λ2 v2 + K + λk vk ; λi ∈ Fq } . Jika S = ∅ maka didefinisikan S = {0} .
(Ling & Xing 2004) Definisi 2.2.7: Basis Misalkan
V
merupakan ruang vektor dari
Fq . Himpunan tak kosong
B = {v1 , v2 ,K, vk } dari V dikatakan basis untuk V jika V = B dan B bebas linear Misalkan B = {v1 , v2 ,K, vk } basis untuk V , maka sembarang vektor v ∈V dapat dinyatakan sebagai kombinasi linear dari vektor B secara unik. Teorema 2.2.1 Misalkan V merupakan ruang vektor atas Fq . Jika dim (V ) = k , maka: i. V memiliki q k elemen
1 k −1 k i ii. V memiliki ∏ q − q basis yang berbeda k ! i =0
(
)
(Ling & Xing 2004) Definisi 2.2.8: Hasil Kali Skalar Misalkan V = ( v1 , v2 ,K, vn ) ∈ Fqn , W = ( w1 , w2 ,K, wn ) ∈ Fqn Hasil kali skalar (dot .
product) dari V dan W didefinisikan sebagai V ⋅ W = v1w1 + v2 w2 + K + vn wn ∈ Fq . Definisi 2.2.9: Komplemen Orthogonal
Misalkan V = ( v1 , v2 ,K, vn ) ∈ Fqn , W = ( w1 , w2 ,K, wn ) ∈ Fqn . i. Vektor V dan W dikatakan saling tegak lurus (orthogonal) jika V ⋅ W = 0 ii. Misalkan S merupakan himpunan bagian dari Fqn . Komplemen orthogonal dari S , yaitu S ⊥ didefinisikan sebagai S ⊥ = {v ∈ Fqn | v ⋅ s = 0, ∀s ∈ S } . Jika S = ∅ , maka didefinisikan S ⊥ = Fqn . Jika S merupakan subruang dari ruang vektor Fqn , maka S ⊥ merupakan subruang dari ruang vektor Fqn dan S
⊥
= S⊥
(Ling & Xing 2004)
7
Teorema 2.2.2
Diberikan ruang vektor Fqn . Misalkan S himpunan bagian dari Fqn . Maka dim ( S
) + dim ( S ) = n ⊥
(Ling S, Xing C. 2004)
2.3 Model Aljabar Kode Linear
Misalkan
menotasikan vektor berdimensi n atas field biner
2=
{0,1}.
Kode linear biner dengan panjang n didefinisikan sebagai sub ruang C dari
.
Anggota suatu kode disebut dengan kata kode (codeword). Kode linear C dengan panjang n dan dimensi k dinamakan kode linear dengan parameter [n, k]. Jika jarak minimum d diketahui maka C dinyatakan sebagai kode linear dengan parameter [n,k.d ]. Setiap kata kode dalam kode linear C memiliki panjang tetap n disebut blok yang terbagi menjadi dua bagian yaitu: simbol pesan dan simbol cek. Dimensi k merupakan panjang dari simbol pesan. Menurut Mac Williams dan Sloane (1981) setiap kode akan memiliki kata kode sebanyak 2k.. Definisi 2.3.1
Jarak (Hamming distance) antara dua vektor x,y
, dinotasikan d(x,y), adalah
banyaknya posisi digit dari x dan y dimana simbol mereka berbeda. Jarak minimum (minimum hamming distance) dari suatu kode linear C didefinisikan: d(C) = min { d(x,y) | x,y
C, x ≠ y }.
Definisi 2.3.2
Bobot (Hamming weight) dari suatu vektor x
, dinotasikan
, adalah
banyaknya simbol taknol dalam x. Bobot minimum (minimum hamming weight ) dari suatu kode C didefinisikan: min {
|x
, ≠ 0 }.
Berdasarkan definisi 2.3.1 dan 2.3.2 maka diperoleh d(x,y)= . ebagai ilustrasi, di dalam ruang
maka d(x,y) =
10011
11010
, jika x =10011 dan y =11010,
01001
2.
Proposisi 2.3.1
Jarak minimum dari suatu kode linear C adalah bobot minimum dari sembarang kata kode tak nol.
8
Bukti.
Perhatikan bahwa karena C linear, maka d(C) = min { d(x,y) | x,y )|z
= min
| x,y
C, x ≠ y } = min { C, z ≠ 0 } =
C, x ≠ y }
. ( terbukti ).
Definisi 2.3.3 , didefinisikan
Ortogonal dari C (dibaca : kode dual dari C), notasi
| x . y = 0 untuk setiap x C }. Dimana “.” adalah produk dalam
= {y standar pada x . y = ∑
yang didefinisikan sebagai :
. ,
= (
,
, …..
), y = (
,
Dengan demikian , jika C berdimensi k , maka
.
)
,….
berdimensi r = n- k.
2.4 Matriks Cek Paritas
Suatu matriks H berukuran r x n yang semua barisnya merupakan suatu basis untuk
disebut matriks cek paritas ( parity check matrix ) dari C.
Pengertian matrik paritas ini berimplikasi pada pendefinisian kode linear yang berkaitan dengan cara konstruksinya, yaitu C = { x
|H
= 0 }. Dengan kata
lain, C adalah ker ( H). Mengkonstruksi ( membuat ) kode linear dengan panjang n dan k sama artinya dengan mendefinisikan matriks cek paritas seperti yang dimaksud diatas. Di samping itu matriks cek paritas berfungsi mengubah pesan menjadi katakode, dengan kata lain ia merupakan parameter didalam enkoding.
2.5 Enkoding Kode Linear
Enkoding kode linear dengan menggunakan matriks cek paritas H, diilustrasikan
sebagai berikut. Diberikan blok simbol pesan dengan panjang k
misalnya u = u1u 2 ...u k , akan dienkode menjadi kata kode x = x1 x2 ...xn dimana n≥k
dengan menggunakan matriks cek paritas
H
yang telah didefinisikan
sebelumnya. Maka, pertama kali didefinisikan = dan diikuti dengan pendefinisian
,
=
, …
r = (n − k )
= simbol cek
xk +1 xk +1 ...xn
yang
9
nilainya bergantung pada nilai simbol pesan. Ketergantungan ini ditentukan oleh H dengan menyelesaikan SPL homogen berikut: ⎛ x1 ⎞ ⎛ 0 ⎞ ⎜ ⎟ ⎜ ⎟ x 0 T Hx = 0 ⇔ H ⎜ 2 ⎟ = ⎜ ⎟ . ⎜ M ⎟ ⎜M⎟ ⎜ ⎟ ⎜ ⎟ ⎝ xn ⎠ ⎝ 0 ⎠
Untuk memudahkan penyelesaian, matriks A biasanya diberikan dalam bentuk standar, yaitu
H = ( A | Ir ). Dengan A adalah matriks biner berukuran r x k , dan Ir adalah matriks identitas berukuran r x r . Jika matriks H belum berbentuk standar, maka dilakukan operasi baris / kolom elementer untuk mendapatkan matriks ekivalen standarnya. Berikut ini diilustrasikan proses kalkulasi enkoding dengan menggunakan H.
Didefinisikan matriks cek paritas H berikut:
⎛0 1 1 1 0 0⎞ ⎜ ⎟ H = ⎜ 1 0 1 0 1 0 ⎟. ⎜1 1 0 0 0 1⎟ ⎝ ⎠ Dari ukuran H diperoleh n =6, n – k =3, sehingga k = 3. Terlihat bahwa H mempunyai bentuk standar dengan
⎛0 1 1⎞ ⎜ ⎟ A = ⎜ 1 0 1 ⎟. ⎜1 1 0⎟ ⎝ ⎠ Pesan u = u1u2u3 akan dienkode menjadi x = x1 x2 x3 x4 x5 x6 . Hal ini dimulai dari x1 = u1 , x2 = u2 , x3 = u3 ,
kemudian x4, x5, x6
dipilih sehingga memenuhi HxT = 0, sehingga diperoleh
Sistem Persamaan Linear (SPL)
x2 + x3 + x4 = 0, x1 + x3 + x5 = 0, x1 + x2 + x6 = 0.
10
dan disebut SPL cek paritas. Misalnya pesan u = 110, maka x1 = 1,
x2 = 1,
x3 = 0, dan dari SPL diperoleh
x4 = −1 = 1, x5 = −1 = 1, x6 = −1 − 1 = 1 + 1 = 0. Ini berarti H mengubah pesan u = 110 menjadi katakode x = 110110. Secara keseluruhan, karena
k = 3,
maka ada
23 = 8
pesan berbeda yang bertindak
sebagai input dalam enkoding, sehingga H mendefinisikan kode C dengan anggota 8 katakode C = {000000, 001110, 010101, 011011, 100011, 101101, 110110, 111000} Selain menggunakan matriks cek paritas H, untuk mengkonstruksi C juga dapat menggunakan matriks generator dari C, biasanya dinotasikan dengan G. Semua baris dari G merupakan basis untuk C. Akibatnya G berukuran
kxn
dan setiap kata kode merupakan kombinasi linear dari semua vektor baris dari G, dengan kata lain C = Span({ ,
Dimana { ,
, ….
}
, ….
})
adalah himpunan semua baris dari G, hubungan antara
H dan G dapat dinyatakan dalam persamaan berikut: G HT = HGT 2.6 Dasar-dasar konstruksi kode 2.6.1
Penambahan pada matriks cek paritas (Adding an overall parity check/Extending a code)
Misalkan C adalah suatu kode linear biner dengan parameter [ n, k , d ] yang beberapa kata kode nya berbobot ganjil. Dari kode tersebut akan dibentuk kode baru Cˆ dengan menambahkan bit "0" di akhir kata kode yang berbobot genap, dan bit "1 " di akhir kata kode yang berbobot ganjil. Dengan penambahan ini, jarak tiap pasang kata kode menjadi genap. Jika jarak minimum kode C ganjil, maka kode yang baru memiliki jarak minimum d + 1, sehingga
Cˆ
memiliki
parameter
[ n + 1, k , d + 1] .
Secara umum, proses
penambahan simbol pada matriks cek paritas disebut sebagai extending a code. (Williams & Sloane 1981)
11
2.6.2 Pemotongan kode dengan cara menghapus koordinat tertentu (Puncturing a code by deleting coordinates) Misalkan C adalah suatu kode linear. Proses pemotongan kode (puncturing) merupakan invers/kebalikan dari proses memperluas kode (extending a code). Proses ini menghapus satu atau lebih koordinat dari setiap kata kode. Ketika suatu koordinat dihapus, panjang dan jarak minimum dari kode akan berkurang satu (namun, pada kasus tertentu, ada kalanya jarak minimum tetap). Dengan kata lain, jika kode awal C memiliki parameter [ n, k , d ] , kode yang baru C * memiliki parameter [ n − 1, k , d − 1] .
(Williams & Sloane 1981)
2.6.3 Penghapusan dengan cara menghilangkan beberapa kata kode (Expurgating by thowing away codewords) Misalkan kode linear biner C memiliki parameter [ n, k , d ] dan memiliki kata kode dengan bobot ganjil dan genap. Kata kode dengan bobot ganjil dapat dihapus untuk mendapatkan kode baru dengan parameter
[ n, k − 1, d '] .
Pada
umumnya d ' > d (Williams & Sloane 1981)
2.6.4 Memperbesar suatu kode dengan cara menambahkan kata kode baru ( Augmenting by adding new codeword)
Salah satu cara untuk memperbesar suatu kode adalah dengan cara menambahkan satu baris vektor 1 pada matriks generator. Jika C adalah suatu kode dengan parameter [ n, k , d ] dan tidak memiliki kata kode 1 (vektor satu), kode yang telah diperbesar berbentuk C ( ) = C ∪ (1 + C ) a
( C(
a)
mengandung/memiliki kata kode dari kode C beserta komplemennya).
Dengan
demikian
C( a)
memiliki
parameter
⎡ n, k + 1, d ( a ) ⎤ , ⎣ ⎦
dengan
d ( a ) = min {d , n − d '} , d ' = bobot terbesar dari kata kode di C . (Williams & Sloane 1981)
12
2.6.5 Memperpanjang suatu kode dengan menambahkan simbol pesan (Lengthening by adding message symbols) Untuk memperpanjang suatu kode linear C , dapat dilakukan dengan cara menambahkan kata kode baru, yaitu vektor 1 (augmenting a code). Setelah itu, dilanjutkan dengan memperluas (extending) kode sebanyak satu bit. Proses ini akan menambah satu simbol pesan (Williams & Sloane. 1981)
2.6.6 Memperpendek kode (Shortening a code) Memperpendek
kode
merupakan
invers/kebalikan
dari
proses
memperpanjang suatu kode (length a code). Untuk memperpendek suatu kode, diambil kata kode yang dimulai dengan x1 = 0 (symbol pertama = 0). Selanjutnya koordinat dari x1 dihapus. Proses seperti ini disebut mengambil cross-section dari suatu kode (taking a cross-section of the code). (Williams & Sloane 1981)
