EDARAN KOD LINEAR.pptx
Click here to load reader
-
Upload
timothy-macias -
Category
Documents
-
view
287 -
download
11
description
Transcript of EDARAN KOD LINEAR.pptx
![Page 1: EDARAN KOD LINEAR.pptx](https://reader038.fdokumen.site/reader038/viewer/2022102502/563dba35550346aa9aa39d20/html5/thumbnails/1.jpg)
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)
![Page 2: EDARAN KOD LINEAR.pptx](https://reader038.fdokumen.site/reader038/viewer/2022102502/563dba35550346aa9aa39d20/html5/thumbnails/2.jpg)
1.0PENGENALANKOD LINEAR
![Page 3: EDARAN KOD LINEAR.pptx](https://reader038.fdokumen.site/reader038/viewer/2022102502/563dba35550346aa9aa39d20/html5/thumbnails/3.jpg)
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.
![Page 4: EDARAN KOD LINEAR.pptx](https://reader038.fdokumen.site/reader038/viewer/2022102502/563dba35550346aa9aa39d20/html5/thumbnails/4.jpg)
• Mempunyai 6-digit
KATAKOD(codeword )
![Page 5: EDARAN KOD LINEAR.pptx](https://reader038.fdokumen.site/reader038/viewer/2022102502/563dba35550346aa9aa39d20/html5/thumbnails/5.jpg)
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!!!!!
![Page 6: EDARAN KOD LINEAR.pptx](https://reader038.fdokumen.site/reader038/viewer/2022102502/563dba35550346aa9aa39d20/html5/thumbnails/6.jpg)
Modulo 2 (0,1)
Galois Field GF(2)
MENGIRA DIGIT SEMAKAN
![Page 7: EDARAN KOD LINEAR.pptx](https://reader038.fdokumen.site/reader038/viewer/2022102502/563dba35550346aa9aa39d20/html5/thumbnails/7.jpg)
3 digit mesej [001]
Maka, [001] akan ditransmit sebagai
[001011]
0 + 0 = 0
0 + 1 = 1
0 + 1= 1
CONTOH
![Page 8: EDARAN KOD LINEAR.pptx](https://reader038.fdokumen.site/reader038/viewer/2022102502/563dba35550346aa9aa39d20/html5/thumbnails/8.jpg)
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
![Page 9: EDARAN KOD LINEAR.pptx](https://reader038.fdokumen.site/reader038/viewer/2022102502/563dba35550346aa9aa39d20/html5/thumbnails/9.jpg)
2.0BERAT &
JARAKMINIMUM
![Page 10: EDARAN KOD LINEAR.pptx](https://reader038.fdokumen.site/reader038/viewer/2022102502/563dba35550346aa9aa39d20/html5/thumbnails/10.jpg)
• 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
![Page 11: EDARAN KOD LINEAR.pptx](https://reader038.fdokumen.site/reader038/viewer/2022102502/563dba35550346aa9aa39d20/html5/thumbnails/11.jpg)
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
![Page 12: EDARAN KOD LINEAR.pptx](https://reader038.fdokumen.site/reader038/viewer/2022102502/563dba35550346aa9aa39d20/html5/thumbnails/12.jpg)
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
![Page 13: EDARAN KOD LINEAR.pptx](https://reader038.fdokumen.site/reader038/viewer/2022102502/563dba35550346aa9aa39d20/html5/thumbnails/13.jpg)
Jika katakod 0101 dihantar, tetapi gangguan menyebabkan kesilapan berlaku dan katakod yang diterima adalah 0010, kesilapan dapat dikesan tetapi tidak dapat dibetulkan.
![Page 14: EDARAN KOD LINEAR.pptx](https://reader038.fdokumen.site/reader038/viewer/2022102502/563dba35550346aa9aa39d20/html5/thumbnails/14.jpg)
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
![Page 15: EDARAN KOD LINEAR.pptx](https://reader038.fdokumen.site/reader038/viewer/2022102502/563dba35550346aa9aa39d20/html5/thumbnails/15.jpg)
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’
![Page 16: EDARAN KOD LINEAR.pptx](https://reader038.fdokumen.site/reader038/viewer/2022102502/563dba35550346aa9aa39d20/html5/thumbnails/16.jpg)
1. Diberi digit mesej adalah [100], cari digit semakan dan codeword.
Digit semakan = 110
codeword = [100110]
LATIHAN
![Page 17: EDARAN KOD LINEAR.pptx](https://reader038.fdokumen.site/reader038/viewer/2022102502/563dba35550346aa9aa39d20/html5/thumbnails/17.jpg)
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
![Page 18: EDARAN KOD LINEAR.pptx](https://reader038.fdokumen.site/reader038/viewer/2022102502/563dba35550346aa9aa39d20/html5/thumbnails/18.jpg)
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
![Page 19: EDARAN KOD LINEAR.pptx](https://reader038.fdokumen.site/reader038/viewer/2022102502/563dba35550346aa9aa39d20/html5/thumbnails/19.jpg)
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
![Page 20: EDARAN KOD LINEAR.pptx](https://reader038.fdokumen.site/reader038/viewer/2022102502/563dba35550346aa9aa39d20/html5/thumbnails/20.jpg)
5. Secara berpasangan, carikan jarak minimum di antara mana-mana dua katakod (codeword) dalam soalan 4.
LATIHAN
![Page 21: EDARAN KOD LINEAR.pptx](https://reader038.fdokumen.site/reader038/viewer/2022102502/563dba35550346aa9aa39d20/html5/thumbnails/21.jpg)
3.0PERSAMAAN
SEMAKAN PARITI
![Page 22: EDARAN KOD LINEAR.pptx](https://reader038.fdokumen.site/reader038/viewer/2022102502/563dba35550346aa9aa39d20/html5/thumbnails/22.jpg)
PERSAMAAN SEMAKAN PARITI
Katakod (codeword) memenuhi persamaan semakan pariti seperti di bawah.
![Page 23: EDARAN KOD LINEAR.pptx](https://reader038.fdokumen.site/reader038/viewer/2022102502/563dba35550346aa9aa39d20/html5/thumbnails/23.jpg)
Boleh dituliskan dalam persamaan matriks seperti di bawah:
![Page 24: EDARAN KOD LINEAR.pptx](https://reader038.fdokumen.site/reader038/viewer/2022102502/563dba35550346aa9aa39d20/html5/thumbnails/24.jpg)
Boleh dituliskan dalam persamaan matriks seperti di bawah:
Oleh itu,
H = matriks semakan pariti = transpos bagi vektor katakod
![Page 25: EDARAN KOD LINEAR.pptx](https://reader038.fdokumen.site/reader038/viewer/2022102502/563dba35550346aa9aa39d20/html5/thumbnails/25.jpg)
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,
![Page 26: EDARAN KOD LINEAR.pptx](https://reader038.fdokumen.site/reader038/viewer/2022102502/563dba35550346aa9aa39d20/html5/thumbnails/26.jpg)
Maka,
Katakod yg
diterima
Katakodsebenar
Gangguangyg berlaku
R = C + EC = R - E
![Page 27: EDARAN KOD LINEAR.pptx](https://reader038.fdokumen.site/reader038/viewer/2022102502/563dba35550346aa9aa39d20/html5/thumbnails/27.jpg)
CONTOH 1Jika C = [110011] dan E = [001000],cari R.
R = C + E= [110011] + [001000]= [111011]
![Page 28: EDARAN KOD LINEAR.pptx](https://reader038.fdokumen.site/reader038/viewer/2022102502/563dba35550346aa9aa39d20/html5/thumbnails/28.jpg)
CONTOH 2
Jika R = [010000], dan C = [111000], cari E. E = R – C= [010000] – [ 111000] = [101000]
![Page 29: EDARAN KOD LINEAR.pptx](https://reader038.fdokumen.site/reader038/viewer/2022102502/563dba35550346aa9aa39d20/html5/thumbnails/29.jpg)
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
![Page 30: EDARAN KOD LINEAR.pptx](https://reader038.fdokumen.site/reader038/viewer/2022102502/563dba35550346aa9aa39d20/html5/thumbnails/30.jpg)
4.0 SINDROM
![Page 31: EDARAN KOD LINEAR.pptx](https://reader038.fdokumen.site/reader038/viewer/2022102502/563dba35550346aa9aa39d20/html5/thumbnails/31.jpg)
• 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
![Page 32: EDARAN KOD LINEAR.pptx](https://reader038.fdokumen.site/reader038/viewer/2022102502/563dba35550346aa9aa39d20/html5/thumbnails/32.jpg)
Oleh itu,
= Transpos bagi vektor sindrom
= Hamming matriks
semakan pariti
= Transpos bagi vektor
katakod yang diterima
![Page 33: EDARAN KOD LINEAR.pptx](https://reader038.fdokumen.site/reader038/viewer/2022102502/563dba35550346aa9aa39d20/html5/thumbnails/33.jpg)
Dengan menggunakan dan
Maka setiap katakod mempunyai sindrom 0=[000]
Andaian katakod yang diterima
tiada ralat,
Maka,
![Page 34: EDARAN KOD LINEAR.pptx](https://reader038.fdokumen.site/reader038/viewer/2022102502/563dba35550346aa9aa39d20/html5/thumbnails/34.jpg)
Persamaan sindrom katakod yang diterima dengan sindrom ralat.
Dari,
Maka,
Katakod yang diterima, R mempunyai sindrom yg
sama dengan ralat E.
![Page 35: EDARAN KOD LINEAR.pptx](https://reader038.fdokumen.site/reader038/viewer/2022102502/563dba35550346aa9aa39d20/html5/thumbnails/35.jpg)
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
![Page 36: EDARAN KOD LINEAR.pptx](https://reader038.fdokumen.site/reader038/viewer/2022102502/563dba35550346aa9aa39d20/html5/thumbnails/36.jpg)
Cari semua perkataan dengan sindrom [010]
Dengan menggunakan kod linear yg ditakrifkan,
Maka, untuk S = [010]
CONTOH 1
![Page 37: EDARAN KOD LINEAR.pptx](https://reader038.fdokumen.site/reader038/viewer/2022102502/563dba35550346aa9aa39d20/html5/thumbnails/37.jpg)
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
![Page 38: EDARAN KOD LINEAR.pptx](https://reader038.fdokumen.site/reader038/viewer/2022102502/563dba35550346aa9aa39d20/html5/thumbnails/38.jpg)
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
![Page 39: EDARAN KOD LINEAR.pptx](https://reader038.fdokumen.site/reader038/viewer/2022102502/563dba35550346aa9aa39d20/html5/thumbnails/39.jpg)
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)
![Page 40: EDARAN KOD LINEAR.pptx](https://reader038.fdokumen.site/reader038/viewer/2022102502/563dba35550346aa9aa39d20/html5/thumbnails/40.jpg)
TATASUSUNAN PIAWAI SLEPIAN(SLEPIAN’S STANDARD ARRAY)
![Page 41: EDARAN KOD LINEAR.pptx](https://reader038.fdokumen.site/reader038/viewer/2022102502/563dba35550346aa9aa39d20/html5/thumbnails/41.jpg)
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
![Page 42: EDARAN KOD LINEAR.pptx](https://reader038.fdokumen.site/reader038/viewer/2022102502/563dba35550346aa9aa39d20/html5/thumbnails/42.jpg)
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)
![Page 43: EDARAN KOD LINEAR.pptx](https://reader038.fdokumen.site/reader038/viewer/2022102502/563dba35550346aa9aa39d20/html5/thumbnails/43.jpg)
5.0MENDEKOD KATAKOD YG
DITERIMA
![Page 44: EDARAN KOD LINEAR.pptx](https://reader038.fdokumen.site/reader038/viewer/2022102502/563dba35550346aa9aa39d20/html5/thumbnails/44.jpg)
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.
![Page 45: EDARAN KOD LINEAR.pptx](https://reader038.fdokumen.site/reader038/viewer/2022102502/563dba35550346aa9aa39d20/html5/thumbnails/45.jpg)
Gunakan langkah di atas untuk mencari katakod
jika katakod yang diterima adalah [101110].
Penyelesaian :Langkah 1
CONTOH
![Page 46: EDARAN KOD LINEAR.pptx](https://reader038.fdokumen.site/reader038/viewer/2022102502/563dba35550346aa9aa39d20/html5/thumbnails/46.jpg)
Langkah 2S = [011]Dari Tatasusunan Piawai Slepian, cari
perkataanyang paling sedikit ‘1’ bagi sindrom 011.
Oleh itu, E = 001000
![Page 47: EDARAN KOD LINEAR.pptx](https://reader038.fdokumen.site/reader038/viewer/2022102502/563dba35550346aa9aa39d20/html5/thumbnails/47.jpg)
Langkah 3 Jadi, C = R – E C = 101110 – 00100 = 100110
![Page 48: EDARAN KOD LINEAR.pptx](https://reader038.fdokumen.site/reader038/viewer/2022102502/563dba35550346aa9aa39d20/html5/thumbnails/48.jpg)
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.
![Page 49: EDARAN KOD LINEAR.pptx](https://reader038.fdokumen.site/reader038/viewer/2022102502/563dba35550346aa9aa39d20/html5/thumbnails/49.jpg)
6.0KOD LINEAR
SECARA UMUM
![Page 50: EDARAN KOD LINEAR.pptx](https://reader038.fdokumen.site/reader038/viewer/2022102502/563dba35550346aa9aa39d20/html5/thumbnails/50.jpg)
• 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.
![Page 51: EDARAN KOD LINEAR.pptx](https://reader038.fdokumen.site/reader038/viewer/2022102502/563dba35550346aa9aa39d20/html5/thumbnails/51.jpg)
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
![Page 52: EDARAN KOD LINEAR.pptx](https://reader038.fdokumen.site/reader038/viewer/2022102502/563dba35550346aa9aa39d20/html5/thumbnails/52.jpg)
• 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.
![Page 53: EDARAN KOD LINEAR.pptx](https://reader038.fdokumen.site/reader038/viewer/2022102502/563dba35550346aa9aa39d20/html5/thumbnails/53.jpg)
Secara umumnya, kod ulangan dengan n kali ulangan akan memberi matriks semakan pariti (n-1) x n