Disediakan oleh:

Ainun Bariah binti Jaafar (2012141340038)Andi Haslinda binti Andi Sikandar (2012141340039)Maizura binti Abd Rahim (2012141340042)

KOD LINEAR

KERJA KURSUS APLIKASI MATEMATIK (MTE 3143)

1.0PENGENALANKOD LINEAR

Teori mengenai Kod Pembetulan Kesilapan bermula daripada hasil kerja Richard Hamming pada tahun 1947.

Hamming merupakan seorang ahli Matematik yang bekerja di Bell Telephone Laboratories dalam bidang komputer.

Pada masa itu, program dalam komputer mengambil masa yang lama untuk membuat pengiraan.

Dia tertanya-tanya mengapa jika komputer boleh mengesan kesilapan tetapi komputer tidak dapat membetulkan kesilapan tersebut. Lalu, Hamming memikirkan bagaimana hendak mengesan dan membaiki kesilapan yang wujud.

• Mempunyai 6-digit

KATAKOD(codeword )

Sesuatu kod adalah kod linear jika katakodnya (codeword) adalah set

vektor-vektor C yang memenuhi satu sistem persamaan HCT = 0 di mana

H adalah matriks semakan pariti dan C adalah matriks katakod yang

ditransposkan.

INGAT!!!!!

Modulo 2 (0,1)

Galois Field GF(2)

MENGIRA DIGIT SEMAKAN

3 digit mesej [001]

Maka, [001] akan ditransmit sebagai

[001011]

0 + 0 = 0

0 + 1 = 1

0 + 1= 1

CONTOH

Contoh katakod (codeword) yang dihantar

Contoh mesej

C4 C5 C6 codeword yang

dihantar

001 0+0=0 0+1=1 0+1=1 001011

010 0+1=1 0+0=0 1+0=1 010101

011 0+1=1 0+1=1 1+1=0 (mod 2)

011110

2.0BERAT &

JARAKMINIMUM

• Berat suatu katakod adalah bilangan digit yang bukan sifar dalam katakod itu. Jadi, dalam contoh kod binari, berat merupakan bilangan digit ‘1’ dalam katakod itu.

• Untuk dua katakod x dan y, jarak Hamming, d(x,y) ditakrifkan sebagai bilangan tempat di mana x dan y berbeza. bagi sesuatu set kod C, jarak minimum, ɗ (C) pula ditakrifkn sebagai nilai terkecil bagi d(x,y) bagi x,y dan C dengan x ≠ y

1. Andaikan C1 adalah satu set kod dengan

C1 = (00,01,10,11)

Jarak antara pasangan katakod berikut adalah:d (00,01) = 1 d(00,10)=1 d(00,11)=2d (01,10) = 2 d(01,11)=1 d(10,11)=1

Jadi jarak minimum, ɗ (C1) = 1

CONTOH 1

2. Andaikan C2 = (0000,0101,1010,1111)

Jarak antara pasangan katakod yang mungkin adalah:d (0000,0101) = 2 d(0000,1010)=2d (0000,1111) = 4 d(0101, 1010)=4d(0101, 1111)=2 d(1010,1111) =2

Jadi jarak minimum, ɗ (C2) = 2

CONTOH 2

Jika katakod 0101 dihantar, tetapi gangguan menyebabkan kesilapan berlaku dan katakod yang diterima adalah 0010, kesilapan dapat dikesan tetapi tidak dapat dibetulkan.

3. Andaikan C3 adalah satu set kod dengan

C3 = (000000,010101,101010,111111)

Jarak antara pasangan katakod yang mungkin adalah:d(000000,010101)=3 d(000000,101010)=3d(000000,111111)=6 d(010101, 101010)=6d(010101,111111)=3 d(101010,111111)=3

Jadi jarak minimum, ɗ (C3) = 3

CONTOH 3

Jika katakod 101010 dihantar, tetapi gangguan menyebabkan kesilapan berlaku dan katakod yang diterima adalah 111010, kesilapan dapat dikesan dan dapat dibetulkan mengikut peraturan ‘Pengesanan Logik Majoriti’

1. Diberi digit mesej adalah [100], cari digit semakan dan codeword.

Digit semakan = 110

codeword = [100110]

LATIHAN

2. Tuliskan katakod (codeword) yang sepadan dengan digit mesej berikut;

a) 111b) 101

Digit mesej : 111C = C1C2C3C4C5C6

C4 = C1 + C2 = 1+1=0C5 = C1 + C3 = 1+1=0C6 = C2 + C3 =1+1 =0

C = [111000]

Digit mesej : 101C = C1C2C3C4C5C6

C4 = C1 + C2 = 1+0=1C5 = C1 + C3 = 1+1=0C6 = C2 + C3 =0+1 =1

C = [101101]

LATIHAN

3. Berapakah bilangan 3 digit mesej ada pada kod?

Bilangan 3 digit mesej ialah ;

iaitu,23 = 8

000

001

010

011

100

101

110

111

LATIHAN

4. Senaraikan semua codeword bagi kod 3 digit mesej dalam soalan 3 000

001

010

011

100

101

110

111

000000

001011

010101

011110

100110

101101

110011

111000

LATIHAN

5. Secara berpasangan, carikan jarak minimum di antara mana-mana dua katakod (codeword) dalam soalan 4.

LATIHAN

3.0PERSAMAAN

SEMAKAN PARITI

PERSAMAAN SEMAKAN PARITI

Katakod (codeword) memenuhi persamaan semakan pariti seperti di bawah.

Boleh dituliskan dalam persamaan matriks seperti di bawah:

Boleh dituliskan dalam persamaan matriks seperti di bawah:

Oleh itu,

H = matriks semakan pariti = transpos bagi vektor katakod

PENGHANTARAN MAKLUMAT KATAKOD

• Apabila katakod di kirim, saluran transmisi kebiasaannya mengalami gangguan yang menyebabkan ralat berlaku.

• gangguan ialah vektor E,

• katakod yang diterima ialah vektor R,

Maka,

Katakod yg

diterima

Katakodsebenar

Gangguangyg berlaku

R = C + EC = R - E

CONTOH 1Jika C = [110011] dan E = [001000],cari R.

R = C + E= [110011] + [001000]= [111011]

CONTOH 2

Jika R = [010000], dan C = [111000], cari E. E = R – C= [010000] – [ 111000] = [101000]

1) Jika C = [100110] , E = [000101], cari R. 2) Jika R = [001000], E = [000011], cari C.3) Jika R = [101011], C = [101110], cari E.

LATIHAN

4.0 SINDROM

• Dalam situasi sebenar, kita tidak mengetahui ralat yang diterima.

• Oleh itu, kita boleh mencari ralat dengan menggunakan sindrom S.

• Sindrom S boleh dinyatakan sebagai

SINDROM

Oleh itu,

= Transpos bagi vektor sindrom

= Hamming matriks

semakan pariti

= Transpos bagi vektor

katakod yang diterima

Dengan menggunakan dan

Maka setiap katakod mempunyai sindrom 0=[000]

Andaian katakod yang diterima

tiada ralat,

Maka,

Persamaan sindrom katakod yang diterima dengan sindrom ralat.

Dari,

Maka,

Katakod yang diterima, R mempunyai sindrom yg

sama dengan ralat E.

Mencari perkataan yang sepadan dengan sindrom

tertentu• Katakod yg diterima, R mempunyai sindrom yang

sama dgn sindrom ralat, E.

• Untuk mendekod, kita perlu mencari semua perkataan yg mempunyai sindrom yg sama dgn R.

• Bilangan perkataan yg mempunyai sindrom, sama dgn bilangan katakod

3 digit katakod

3 digit semakan/sindrom

Kemungkinan bilangan

sindrom ialah

Cari semua perkataan dengan sindrom [010]

Dengan menggunakan kod linear yg ditakrifkan,

Maka, untuk S = [010]

CONTOH 1

Boleh diselesaikan menggunakan pengetahuan ruang vektor.

Tiga pemboleh ubah pertama tidak bersandar (independent)

Maka kita akan dapat pilihan gabungan kemungkinan utk ‘0’ dan ‘1’

{ [000], [001], [010], [011], [100], [101], [110], [111] }

3 x 6 6 x 1 3 x 1

Untuk mencari perkataan yg sepadan dengan sindrom

[010], senaraikan semua gabungan ‘0’ dan ‘1’ untuk tiga

pembolehubah pertama dan cari nilai

pembolehubah

Cth:

cari nilai

menggunakan

pendaraban matriks

Beberapa perkataan dengan sindrom [010]

Pembolehubah tak bersandar Pembolehubah bersandarPerkataan yang

dibentuk

0 0 0 0 1 0 0000100 0 1 0 0 1 0010010 1 0 1 1 1 010111

Boleh semak jawapan dengan Tatasusunan Piawai Slepian(Slepian’s Standard Array)

TATASUSUNAN PIAWAI SLEPIAN(SLEPIAN’S STANDARD ARRAY)

1) Jika H = ialah kod Hamming,

cari sindrom S, ralat E dan seterusnya dekodkan

perkataan yang diterima iaitu R = [1110011]

(Nov, 2013)

(5 markah)

LATIHAN

2) Matriks semakan dua parity di bawah menunjukkan kod linear.

i. Matriks manakah bukan kod pembetulan kesilapan?Berikan alasan bagi jawapan anda itu.

ii. Antara dua kod di atas, yg manakah merupakan Kod Hamming? Berikan alasan anda.

(2 markah)

(3 markah)

5.0MENDEKOD KATAKOD YG

DITERIMA

Langkah 1• Mengira sindrom, S dari katakod yang diterima, dengan

menggunakan persamaan,

Langkah 2• Menggunakan Tatasusunan Piawai Slepian, cari

sindrom S dan dapatkan perkataan yang mempunyai paling sedikit bilangan ‘1’. Perkataan ini dipilih sebagai ralat, E.

Langkah 3• Katakod dicari dengan C = R – E.

Gunakan langkah di atas untuk mencari katakod

jika katakod yang diterima adalah [101110].

Penyelesaian :Langkah 1

CONTOH

Langkah 2S = [011]Dari Tatasusunan Piawai Slepian, cari

perkataanyang paling sedikit ‘1’ bagi sindrom 011.

Oleh itu, E = 001000

Langkah 3 Jadi, C = R – E C = 101110 – 00100 = 100110

Oleh sebab katakod yang diterima mempunyai sindrom yang sama

dengan ralat, maka langkah satu boleh dipermudahkan dengan

mencari katakod yang diterima dalam

Tatasusunan Piawai Slepiandan sindrom bagi katakod yang

diterima ini adalah perkataan pertama dalam baris yang mana R

terletak.

6.0KOD LINEAR

SECARA UMUM

• Kod linear – kod yang katakodnya terdiri daripada satu set vektor, C yang memenuhi sistem persamaan di mana H merupakan matriks semakan pariti.

• Matriks semakan pariti, H mempunyai peringkat yang berubah-ubah.

Contoh, kod semakan pariti tunggal. Katakod terdiri daripada digit di mana merupakan digit semakan.

Jadi,

** bagi kod semakan pariti tunggal

dengan panjang n, matriks semakan pariti yang sepadan adalah matriks 1

x n

• Bagi kod ulangan sebagai contoh setiap digit diulang 3 kali, katakod terdiri daripada

di mana dan adalah digit ulangan. Jadi, dan

Dengan ini

* Dalam hal ini, matriks semakan partiti bagi kod ulangan di atas ialah 2 x 3.

Secara umumnya, kod ulangan dengan n kali ulangan akan memberi matriks semakan pariti (n-1) x n