bab ii landasan teori - repository.ipb.ac.id · bab ii landasan teori . sebagai acuan penulisan...

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 berupa konstanta, i = 1, 2, , m; j = 1, 2, , n,

sedangkan 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 bilangan-

bilangan. 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 dimana i = 1, 2, , m dan

j = 1, 2, , n, dibaca sebagai unsur matriks X pada baris ke-i dan kolom ke-j.


Definisi 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:

a. Asosiatif: ( , , ) ( + ) + = + ( + ),

b. mempunyai unsur identitas: ( 0 ) ( ) 0 + = + 0 = ,

c. Setiap unsur dari mempunyai invers: ( ) ( ) + =

+ = 0, dalam hal ini = ( ), dan

d. komutatif: ( ) .

2. , dimana = , merupakan grup komutatif terhadap .,

bersifat:

a. asosiatif: ( ) ( ) ,

b. mempunyai unsur identitas: ( ) ( ) 1. .1 = ,

c. setiap unsur dari mempunyai invers: ( ) ( )

, dalam hal ini dinotasikan ), dan

d. komutatif: ( ) .

3. Berlaku sifat distributif . terhadap + : ( )

atau ( )

(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 contoh field berhingga dengan anggotanya

adalah {0,1}.

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 ) u + v = w.

2. ( 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 )( v ) ku = v.

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 ) 1u = u dimana 1 adalah unsur identitas dari terhadap operasi

kali.


Unsur-unsur dari dalam hal ini merupakan skalar, sedangkan unsur-unsur

dari disebut dengan vektor.

Sebagai contoh: misalkan merupakan himpunan dari pasangan terurut

dengan panjang n yang unsur-unsurnya merupakan elemen dari , yaitu =

{( , ,…, ) }. Misalkan pula v = , w =

, dan . Operasi Penjumlahan di didefinisikan

sebagai v + w = . Sedangkan perkalian

dengan skalar didefinisikan sebagai .v = . Maka

merupakan ruang vektor.

Definisi Subruang (Subspace)

Misalkan adalah ruang vektor atas skalar dan . Himpunan

disebut subruang dari jika juga merupakan ruang vektor atas terhadap

operasi yang sama dengan .

7 Teorema 1

Misalkan adalah ruang vektor atas skalar dan , maka tiga

proposisi berikut ini ekivalen.

(i) subruang dari .

(ii) Berlaku dua sifat berikut ini:

(a) ( , ) + , dan

(b) ( k , w ) kw .

(iii) ( k, l , , ) k + l .


Definisi Kombinasi Linear

Misalkan adalah ruang vektor atas skalar . Diberikan himpunan

= { , ,…, } terdiri atas n vektor dalam . Suatu vektor v disebut

kombinasi linear dari jika ( , , …, ) sehingga v = .


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 I = {1,2,…,n} = 0).

Ingkarannya, disebut terpaut linear jika

( j I = {1,2,…, n} 0).


Definisi Perentang / Span

Jika S = adalah vektor-vektor di dalam ruang vektor dan

jika tiap-tiap vektor di dalam 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.


8 Definisi Basis

Jika adalah sembarang ruang vektor dan S = { } adalah

sebuah himpunan berhingga dari vektor-vektor di dalam , maka S dinamakan

sebuah basis untuk jika:

1. S bebas linear.

2. S merentang .


Definisi Dimensi

Dimensi dari sebuah ruang vektor didefinisikan sebagai banyaknya

vektor-vektor dari basis di .


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.


Definisi Rank

Dimensi ruang baris atau ruang kolom dari matriks A dinamakan rank dari

matriks A.


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 berlaku:

1. Simetrik: =

2. Linearitas: = k + l , dan

9

3. Positifitas: 0 dan = 0 jhj x = 0.


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 dikatakan ortogonal,

dinotasikan x y, jika = 0.


Definisi Komplemen Ortogonal

Misalkan adalah ruang vektor dan S . Komplemen ortogonal (disebut

juga dual) dari S, notasi , didefinisikan sebagai

= .


Sebagai contoh: misalkan v = , w = ; v, w .

i. Vektor v & w dikatakan saling tegak lurus (orthogonal) jika

v.w = 0

ii. Misalkan S merupakan himpunan bagian dari . Komplemen

orthogonal dari S, notasi didefinisikan sebagai

= . Jika S = , maka = .

Jika S merupakan subruang dari ruang vektor , maka merupakan subruang

dari ruang vektor dan = .

(Ling & Xing, 2004)

Definisi Kode Linear

Misalkan diberikan field berhingga qF . Misalkan pula nqF merupakan

himpunan dari vektor-vektor atas qF dengan panjang n . Kode linear C

didefinisikan sebagai subruang dari ruang vektor nqF .

(Ling & Xing, 2004)

10 Definisi Kode Dual

Misalkan C merupakan kode linear atas , maka Kode dual (dual code)

dari C, notasi , adalah komplemen orthogonal dari C.

Teorema 2

Misal C adalah kode linear atas dengan panjang n dan dimensi k, maka :

i. = dim ( C ) =

ii. juga merupakan suatu kode linear dan dim (C ) + dim = n

iii. = C

Dengan demikian jika C berdimensi k, maka berdimensi r = n – k .

(Ling & Xing, 2004)

Definisi Jarak Hamming (Hamming distance)

Diberikan ruang vektor atas lapangan . Misalkan pula x dan y adalah

anggota dari (x, y ). Jarak Hamming antara x dan y yang dinotasikan

dengan ( ),d x y , didefinisikan sebagai berikut.

( ) ( ) ( ) ( )1 1 2 2, , , ... ,n nd x y d x y d x y d x y= + + , dengan

( )1

,0

i ii i

i i

x yd x y

x y≠

= =.

(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

( ) ( ){ }min , | , ,d C 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 . Bobot Hamming

(Hamming Distance), yang dinotasikan 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 jika 0( ) ( ,0)

0 jika 0x

wt x d xx≠

= = =.

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 ( )|kI X , dengan

Matriks identitas berukuran kI k k= × .

ii. Bentuk standar untuk matriks cek paritas H adalah ( )| n kY I − ,

dengan ( ) ( ) Matriks identitas berukuran n kI n k n k− = − × − .

(Ling & Xing, 2004)

Teorema 4

Misalkan H adalah suatu matriks cek paritas bagi kode linear C, maka

i. C memiliki jarak minimum ≥ d jika dan hanya jika d – 1 kolom

dari H saling bebas linear.

ii. C memiliki jarak minimum ≤ d jika dan hanya jika d kolom dari H

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 1C dan 2C . 1C dan 2C 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 menotasikan ruang vektor standar berdimensi n atas dasar field

biner = {0,1}. Maka definisi Bobot (Hamming weight) dari suatu vektor

x 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 dengan

syarat : x = C jika dan hanya jika simbol pesan dan

simbol cek yang memenuhi persamaan :

= +

= + +

= +

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 dan = 1, maka = 1 + 0 = 1,

= 0 + 1 + 1 = 0, dan = 1 + 1 = 0, sehingga 011100 C.

Secara lengkap pendefinisian C diberikan dalam tabel berikut :

Tabel 1 Contoh pendefinisian pesan menjadi katakode

Simbol Pesan Katakode

000

001

010

011

100

101

110

111

000000

001111

010011

011100

100110

101001

110101

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 = ( A C ) (2)

dengan A adalah matriks biner berukuran r x k, dan 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

Berikut ini adalah ilustrasi proses kalkulasi enkoding dengan menggunakan

matriks H.

2 yang telah didefinisikan

pada .

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 1d + ,

Sehingga C memiliki parameter [ ]1, , 1n k d+ + . 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 [ ], 1, 'n k d− . Pada

umumnya 'd d> .

(MacWilliams & Sloane,1981)

bab ii landasan teori - repository.ipb.ac.id · bab ii landasan teori . sebagai acuan penulisan...

Documents