BAB II LANDASAN TEORI
Sebagai acuan penulisan penelitian ini diperlukan beberapa pengertian dan teori yang berkaitan dengan pembahasan. Dalam sub bab ini akan diberikan beberapa landasan teori berupa pengertian, definisi, proposisi dan teorema yang berkaitan dengan pembahasan.
Definisi Sistem Persamaan Linear (SPL) Sistem Persamaan Linear (SPL) m
n adalah m persamaan linear dengan n
variabel (peubah). Bentuk umumnya adalah sebagai berikut: +
+
+
=
+
+
+
=
+
+
+
dengan
dan
sedangkan
=
berupa konstanta, i = 1, 2,
, m;
j = 1, 2,
, n,
merupakan variabel yang ingin ditentukan nilainya. Nilai
disebut koefisien
pada persamaan ke-i.
Suatu sistem persamaan linear dengan bentuk
=
=
=
= 0
disebut SPL homogen. Bentuk umum dari SPL homogen adalah sebagai berikut: +
+
+
=0
+
+
+
=0
+
+
+
=0 (Gunawan Santosa R. 2009)
Definisi Matriks Matriks adalah susunan segi empat yang unsur-unsurnya berupa bilanganbilangan. Matriks X dengan ordo m
n adalah matriks dengan ukuran m baris
dan n kolom, simbolnya adalah sebagai berikut.
5
X= Unsur matriks yang disimbolkan dengan j = 1, 2,
dimana i = 1, 2,
, m dan
, n, dibaca sebagai unsur matriks X pada baris ke-i dan kolom ke-j. (Gunawan Santosa R. 2009)
Definisi Field Suatu himpunan
yang padanya didefinisikan operasi jumlah (+) dan
operasi kali (.) disebut field, notasi 1.
, jika memenuhi sifat-sifat berikut,
merupakan grup komutatif terhadap +, yaitu memenuhi sifat-sifat: a. Asosiatif: ( b.
, ,
) ( + ) + = + ( + ),
mempunyai unsur identitas: ( 0
c. Setiap unsur dari
d. komutatif: ( , dimana
)0+ = +0= ,
mempunyai invers: (
+ = 0, dalam hal ini
2.
)(
=(
)(
)
+
=
), dan
)
.
=
, merupakan grup komutatif terhadap .,
bersifat: a. asosiatif: ( b.
)( )
,
mempunyai unsur identitas: (
c. setiap unsur dari
)(
) 1.
mempunyai invers: (
, dalam hal ini dinotasikan d. komutatif: (
)
) (
)
), dan
.
3. Berlaku sifat distributif . terhadap + : ( atau (
.1 = ,
)
) (Sugi Guritman 2005)
Contoh field takhingga diantaranya adalah: himpunan bilangan real, himpunan bilangan kompleks, sedangkan contoh dari field berhingga diantaranya adalah
= {0,1, 2,…, ( – 1)} dengan operasi jumlah dan kali modulo , dimana
bilangan prima. Jadi adalah {0,1}.
adalah contoh field berhingga dengan anggotanya
6
Definisi Ruang Vektor Diberikan sembarang himpunan
dan sembarang field
. Pada
didefinisikan aturan jumlah dan aturan perkalian dengan skalar. Himpunan disebut ruang vektor atas
jika terhadap aturan-aturan tersebut memenuhi 10
aksioma-aksioma berikut. 1. ( u, v
)( w
2. ( u, v, w
) u + v = w.
) (u + v) + w = u + (v + w).
3. ( 0
)( u
) 0 + u = u + 0 = u.
4. ( u
)( v
) u + v = v + u = 0, dalam hal ini v = u.
5. ( u, v
) u + v = v + u.
6. ( k
, u
7. ( k
, u, v
) k(u + v) = ku + kv.
8. ( k, l
, u
) (k + l) u = ku + lu.
9. ( k, l
, u
) (kl)u = k(lu).
10. ( u
)( v
) ku = v.
) 1u = u dimana 1 adalah unsur identitas dari
terhadap operasi
kali. (Sugi Guritman 2005) Unsur-unsur dari dari
dalam hal ini merupakan skalar, sedangkan unsur-unsur
disebut dengan vektor. Sebagai contoh: misalkan
merupakan himpunan dari pasangan terurut
dengan panjang n yang unsur-unsurnya merupakan elemen dari {(
,
,…,
)
}. Misalkan pula , dan
v
, yaitu
=
=
, w =
. Operasi Penjumlahan di
sebagai v + w =
didefinisikan
. Sedangkan perkalian
dengan skalar didefinisikan sebagai
.v =
. Maka
merupakan ruang vektor.
Definisi Subruang (Subspace) Misalkan
adalah ruang vektor atas skalar
disebut subruang dari
jika
operasi yang sama dengan .
dan
. Himpunan
juga merupakan ruang vektor atas
terhadap
7
Teorema 1 Misalkan
adalah ruang vektor atas skalar
dan
, maka tiga
proposisi berikut ini ekivalen. (i) (ii)
subruang dari . Berlaku dua sifat berikut ini: (a) (
,
)
(b) ( k (iii)
, w
( k, l
,
+
, dan
) kw
,
.
) k
+l
. (Sugi Guritman 2005)
Definisi Kombinasi Linear Misalkan
adalah
ruang vektor atas skalar
= { , ,…, } terdiri atas n vektor dalam kombinasi linear dari
jika
( , , …,
)
. Diberikan
himpunan
. Suatu vektor v
disebut
sehingga v =
.
(Sugi Guritman 2005)
Definisi Bebas Linear dan Terpaut linear Misalkan
adalah ruang vektor atas skalar
, dan misalkan
adalah himpunan yang terdiri atas n vektor dalam
.
=
disebut
bebas linear jika memenuhi persamaan berikut ( i Ingkarannya,
I = {1,2,…,n}
= 0).
disebut terpaut linear jika ( j
I = {1,2,…, n}
0). (Sugi Guritman 2005)
Definisi Perentang / Span Jika S =
adalah vektor-vektor di dalam ruang vektor
jika tiap-tiap vektor di dalam
dan
dapat dinyatakan sebagai kombinasi linear dari S,
maka dikatakan bahwa vektor-vektor S merentang (spanning) . Jika
=
, maka S disebut himpunan perentang
. Dan
dikatakan
direntang oleh S. (Gunawan Santosa R. 2009)
8
Definisi Basis Jika
adalah sembarang ruang vektor dan S = {
sebuah himpunan berhingga dari vektor-vektor di dalam sebuah basis untuk
} adalah
, maka S dinamakan
jika:
1. S bebas linear. 2. S merentang
. (Gunawan Santosa R. 2009)
Definisi Dimensi Dimensi dari sebuah ruang vektor
didefinisikan sebagai banyaknya
vektor-vektor dari basis di . (Gunawan Santosa R. 2009)
Definisi Ruang Baris dan Ruang Kolom Jika diketahui matriks A berukuran m
n, maka subruang
yang
direntang oleh vektor-vektor baris dinamakan ruang baris (row space) dari A. Sedangkan subruang
yang direntang oleh vektor-vektor kolom dinamakan
ruang kolom (column space) dari A. (Gunawan Santosa R. 2009)
Definisi Rank Dimensi ruang baris atau ruang kolom dari matriks A dinamakan rank dari matriks A. (Gunawan Santosa R. 2009)
Definisi Produk dalam Misalkan
adalah ruang vektor atas skalar
, misalkan x, y
sembarang. Operasi biner dari x dan y bernilai dalam , dinotasikan
, disebut
produk dalam (inner product) jika memenuhi sifat-sifat berikut. Untuk setiap x, y, z
dan k, l
1. Simetrik: 2. Linearitas:
berlaku: = =k
+l
, dan
9
3. Positifitas:
0 dan
= 0 jhj x = 0. (Sugi Guritman 2005)
Sebagai contoh: misalkan x = {
}
dan y = {
}
. Produk dalam baku dari x dan y didefinisikan sebagai berikut = x.y =
.
Definisi Ortogonal Dua vektor x dan y di dalam ruang vektor dinotasikan x
y, jika
dikatakan ortogonal,
= 0. (Sugi Guritman 2005)
Definisi Komplemen Ortogonal Misalkan
adalah ruang vektor dan S
juga dual) dari S, notasi
. Komplemen ortogonal (disebut
, didefinisikan sebagai =
. (Sugi Guritman 2005)
Sebagai contoh: misalkan v = i.
,w=
; v, w
.
Vektor v & w dikatakan saling tegak lurus (orthogonal) jika v.w = 0
ii.
Misalkan
S merupakan himpunan bagian dari
orthogonal dari S, notasi
didefinisikan sebagai
=
. Jika S =
Jika S merupakan subruang dari ruang vektor dari ruang vektor
dan
=
. Komplemen
, maka
, maka
=
.
merupakan subruang
. (Ling & Xing, 2004)
Definisi Kode Linear Misalkan diberikan field berhingga Fq . Misalkan pula Fqn merupakan himpunan dari vektor-vektor atas Fq dengan panjang n . Kode linear C didefinisikan sebagai subruang dari ruang vektor Fqn . (Ling & Xing, 2004)
10
Definisi Kode Dual Misalkan C merupakan kode linear atas dari C, notasi
, maka Kode dual (dual code)
, adalah komplemen orthogonal dari C.
Teorema 2 Misal C adalah kode linear atas
dengan panjang n dan dimensi k, maka :
i.
=
ii.
juga merupakan suatu kode linear dan dim (C ) + dim
iii.
dim ( C ) = =n
=C
Dengan demikian jika C berdimensi k, maka
berdimensi r = n – k . (Ling & Xing, 2004)
Definisi Jarak Hamming (Hamming distance) Diberikan ruang vektor anggota dari
(x, y
atas lapangan
. Misalkan pula x dan y adalah
). Jarak Hamming antara x dan y yang dinotasikan
dengan d ( x, y ) , didefinisikan sebagai berikut. d ( x, y ) = d ( x1 , y1 ) + d ( x2 , y2 ) + ...d ( xn , yn ) , dengan 1 d ( xi , yi ) = 0
xi ≠ yi . xi = yi
(Ling & Xing, 2004)
Definisi Jarak Minimum suatu kode (Minimum distance of a code) Misalkan C adalah kode linear yang memiliki kata kode lebih dari satu. Jarak minimum untuk C , yang dinotasikan d ( C ) , didefinisikan sebagai = d ( C ) min {d ( x, y ) | x, y ∈ C , x ≠ y} .
(Ling & Xing, 2004)
Parameter Kode Linear Kode linear C dengan panjang n dan berdimensi k disebut dengan kode linear dengan parameter [n, k]. Jika jarak minimum d dari C diketahui, maka C disebut kode linear dengan parameter [n, k, d]. Atau disebut kode linear-[n, k, d].
11
Untuk selanjutnya, jika parameter dari suatu kode tidak ditekankan, cukup disebutkan bahwa C adalah suatu kode linear. Anggota dari C disebut dengan kata kode. (Ling & Xing, 2004)
Definisi Bobot Hamming (Hamming weight) Diberikan ruang vektor
. Misalkan pula x
(Hamming Distance), yang dinotasikan
. Bobot Hamming
wt(x) didefinisikan sebagai jumlah
koordinat/unsur yang tak nol: Wt(x) = d(x, 0) dengan 0 adalah vektor nol atau dapat pula didefnisikan sebagai berikut. 1 = wt ( x) d= ( x, 0) 0
jika x ≠ 0 . jika x = 0
Lema 1. Diberikan ruang vektor
. Misalkan x, y
, maka d(x, y) = wt(x
y).
(Ling & Xing, 2004)
Definisi Bobot Minimum Hamming Diberikan kode linear C . Minimum Hamming weight (Bobot minimal Hamming) dari C , dinotasikan wt ( C ) , didefinisikan sebagai bobot terkecil dari kata kode tak nol dari C . Teorema 3 Misalkan C adalah suatu kode linear, maka d ( C ) = wt ( C ) . (Ling & Xing, 2004)
Definisi Matriks Generator dan Matriks Cek Paritas i.
G dikatakan matriks generator bagi kode C jika baris-barisnya merupakan basis untuk C.
ii.
H dikatakan matriks cek paritas dari kode C jika H merupakan matriks generator bagi kode dual
. (Ling & Xing, 2004)
12
Bentuk Standar dari Matriks Cek Paritas H dan Matriks Generator G Diberikan kode linear C . Misalkan H dan G , secara berturut-turut adalah matrik cek paritas dan matrik generator untuk kode linear C . i.
Bentuk standar untuk matriks generator G adalah ( I k | X ) , dengan
= Ik
ii.
Matriks identitas berukuran k × k .
Bentuk standar untuk matriks cek paritas H adalah
dengan I n − k =
(Y | I n − k ) ,
Matriks identitas berukuran ( n − k ) × ( n − k ) .
(Ling & Xing, 2004) Teorema 4 Misalkan H adalah suatu matriks cek paritas bagi kode linear C, maka C memiliki jarak minimum ≥
i.
d jika dan hanya jika d – 1 kolom
dari H saling bebas linear. C memiliki jarak minimum ≤ d jika dan hanya jika d kolom dari H
ii.
saling tidak bebas linear. (Ling & Xing, 2004) Teorema 5 Jika G =
adalah bentuk standar dari matriks generator untuk suatu
kode C dengan parameter [n, k], maka matriks cek paritas untuk kode C adalah H=
. (Ling & Xing, 2004)
Definisi Ekivalensi dari Kode Linear Misalkan diberikan sembarang kode linear C1 dan C2 . C1 dan C2 dikatakan ekivalen jika salah satunya dapat diperoleh dari kode yang lain dengan cara mengkombinasikan operasi-operasi sebagai berikut. i.
Mempermutasikan digit-digit yang ada di kata kode tersebut.
ii.
Mengalikan posisi tertentu dengan skalar. (Ling & Xing, 2004)
13
Model Aljabar Kode Linear Biner. Jika biner x
menotasikan ruang vektor standar berdimensi n atas dasar field = {0,1}. Maka definisi Bobot (Hamming weight) dari suatu vektor
adalah banyaknya simbol tak nol dalam x dan dinotasikan “ t (x) “ .
Definisi Jarak (Hamming distance) antara dua vektor x,y
adalah banyaknya
posisi digit dari x dan y dimana simbol mereka berbeda dan dinotasikan “ d(x,y) “, jelas bahwa d(x,y) = t(x + y). Sebagai contoh, di dalam ruang vektor
, jika
x = 110001 dan y = 101010, maka: d(x,y) = t(110001 + 101010) = t (011011) = 4 Dalam praktek, pengertian tersebut terkait dengan makna fisik sebagai berikut. Jika pesan x akan dikirim dan berubah menjadi y saat diterima, maka d(x,y) merepresentasikan banyaknya galat yang terjadi. d(x,y) = 0 berarti tidak terjadi kesalahan saat pengiriman. Dari definisi kode di atas dapat disimpulkan bahwa suatu kode linear biner dengan panjang n merupakan subruang C dari ruang vektor
. Anggota suatu
kode disebut dengan katakode (codeword). Mengonstruksi suatu kode bukan suatu hal yang sederhana karena harus mempertimbangkan makna praktek yang dijelaskan sebagai berikut. Kode merupakan representasi dari himpunan semua pesan. Artinya satu katakode mewakili satu pesan. Kode diciptakan untuk melindungi (koreksi atau deteksi) pesan dari kesalahan saat pengiriman. Dengan demikian di dalam setiap bitstring katakode harus mengandung dua makna, yaitu simbol pesan dan simbol cek. Simbol pesan telah diketahui (diberikan) sebagai bentuk biner dari pesan, sedangkan simbol cek merupakan simbol ekstra yang ditempelkan pada pesan. Biasanya nilai simbol cek bergantung pada simbol pesan. Berikut ini diberikan ilustrasi bagaimana mengonstruksi suatu kode berdasarkan persamaan aljabar. Contoh 1: Definisikan suatu kode C dengan panjang 6 di dalam ruang syarat : x =
C jika dan hanya jika
simbol cek yang memenuhi persamaan : =
+
=
+
=
+
+
dengan
simbol pesan dan
14
Karena simbol pesan berukuran 3 bit, maka himpunan semua simbol pesan adalah = {000, 001, 010, 011, 100, 101, 110, 111} Jika
= 011
, berarti
= 0 + 1 + 1 = 0, dan
= 0,
= 1 dan
= 1, maka
= 1 + 1 = 0, sehingga 011100
= 1 + 0 = 1,
C.
Secara lengkap pendefinisian C diberikan dalam tabel berikut : Tabel 1 Contoh pendefinisian pesan menjadi katakode Simbol Pesan
Katakode
000
000000
001
001111
010
010011
011
011100
100
100110
101
101001
110
110101
111
111010
Jadi C = {000000, 001111, 010011, 011100, 100110, 101001, 110101, 111010}
.
Ilustrasi praktek dari contoh di atas diberikan sebagai berikut. Suatu pesan 110 akan dikirim, maka pesan itu terlebih dahulu harus diubah (dienkoding) menjadi kata kode. Ini berarti 110 menjadi input dari enkoder. Dan enkoder melakukan perhitungan dengan menggunakan algoritma sebagaimana dirumuskan pada contoh tersebut untuk mengubahnya menjadi katakode. Output dari enkoder adalah berupa kata kode x = 110101. Katakode inilah yang kemudian dikirim melalui saluran yang diasumsikan terganggu (noisy). Apabila pada saat pengiriman terjadi gangguan dan x berubah menjadi y = 010101, maka dekoder harus mampu paling tidak mendeteksi dan akan lebih baik kalau bisa mengoreksi.
15
Pengertian 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 matriks paritas ini berimplikasi pada pendefinisian kode linear yang berkaitan dengan cara konstruksi seperti pada contoh 1 diatas, yaitu : C = {x
H
= 0}
Dengan kata lain, C adalah himpunan solusi dari SPL H
= 0 (disebut dengan
kernel H). Mengkonstruksi (membuat) kode linear dengan panjang n dan berdimensi k sama artinya dengan mendefinisikan matriks cek paritas seperti yang dimaksud di atas. Disamping itu matriks cek paritas berfungsi mengubah pesan menjadi katakode, dengan kata lain ia merupakan parameter didalam enkoding. Enkoding kode linear dengan menggunakan matriks paritas H di ilustrasikan sebagai berikut. Diberikan blok simbol pesan dengan panjang k, misalnya u = akan dienkode menjadi kata kode x =
…….
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
, ,
….
yang
nilainya bergantung pada nilai simbol pesan. Ketergantungan ini ditentukan oleh H dengan menyelesaikan SPL homogen berikut. H
=0
H
=
(1)
Demi kemudahan penyelesaian, matriks H biasanya diberikan dalam bentuk standar, yaitu H=(AC )
dengan A adalah matriks biner berukuran r x k, dan
(2)
adalah matriks idetitas
berukuran r x r. Jika H belum berbentuk standar, maka dengan operasi baris/kolom elementer dapat dicari matriks ekuivalen standarnya. Untuk semua
16
perhitungan menggunakan aritmetik operasi modulo 2 yang telah didefinisikan pada
. Berikut ini adalah ilustrasi proses kalkulasi enkoding dengan menggunakan
matriks H. Contoh 2: Didefinisikankan matriks cek paritas H= Dari ukuran H diperoleh n = 6; n – k = 3, sehingga k = 3. Terlihat bahwa matriks H mempunyai bentuk standar sama dengan A= Pesan u =
akan dienkode menjadi x =
. Hal ini dimulai
dari = kemudian
;
=
;
=
dipilih sehingga memenuhi H
; = 0, sehingga diperoleh Sistem
Persamaan Linear (SPL) +
+
= 0;
+
+
= 0;
+
+
= 0:
dan disebut SPL cek paritas. Misalnya pesan u = 110, maka
= 1,
= 1,
= 0,
dan dari SPL diperoleh = -1 = 1 = -1 = 1 = -1 – 1 = 1 + 1 = 0 Ini berarti H mengubah pesan u = 110 menjadi katakode x = 110110. Secara keseluruhan, karena k = 3, maka ada
= 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 bisa menggunakan matriks generator dari C, biasanya dinotasikan dengan G. Dengan demikian, semua baris dari G merupakan basis untuk C. Akibatnya, G berukuran
17
k x n dan setiap katakode merupakan kombinasi linear dari semua
vektor baris
dari G, dengan kata lain C = Merentang ({ dimana {
,
, ….
,
, ….
})
} adalah himpunan semua baris dari G.
Dasar-dasar Konstruksi Kode Apabila suatu kode telah berhasil dikonstruksi, maka kode dengan parameter yang berbeda dapat pula dikonstruksi, berikut adalah beberapa cara untuk mendapatkan kode lain tersebut. 1. Penambahan pada matriks cek paritas Misalkan C adalah suatu kode linear biner dengan parameter
[ n, k , d ]
dengan 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 exending a code (memperluas suatu kode) . (MacWilliams & Sloane,1981) 2. Penghapusan dengan cara menghilangkan beberapa kata kode 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 . (MacWilliams & Sloane,1981)
