ppg mte 3114

8/12/2019 Ppg Mte 3114

http://slidepdf.com/reader/full/ppg-mte-3114 1/46

Draf Modul Matematik PPG : MTE3114 Aplikasi

Pengenalan

Modul Matematik ini merupakan usaha sama pensyarah-pensyarah Matematik IPGKPP dan IPGKTB. Agihan topik-topik dalam modul ini berdasarkan ProForma MTE !!" Aplikasi Matematik.

Modul ini sesuai diguna sebagai bahan online learning tambahan yang boleh membantu pela#ar guruPI$MP dan peserta kursus PPG memahami kandungan kursus ini dengan mudah. $elain daripadanota ringkas dan %ontoh-%ontoh terker#a& modul ini #uga mengandungi latihan& akti'iti berkumpulandan bahan ba%aan yang bertu#uan mempermudahkan pembela#aran akses kendiri pela#ar.

Panel Penulis Modul IPGK Pulau Pinang

!. En. (ng )o%k Tong *Ketua +abatan,. En. Tan Kah Kheng. r. Teong Mee Mee

M T E 3 1 1 4 / k k t a n / i p g k p p

8/12/2019 Ppg Mte 3114


Isi Kandungan Modul

Topik 1: Matematik dalam Kehidupan eharian !IPGK Tuanku "ainun#

• Peranan matematik teknologi moden

• Matematik sebagai kegiatan budaya yang berterusan

• Asas bagi matematik kontemporari

Topik $: Klasik Kod dan %ipher !IPGK Pulau Pinang#

•Beberapa e/inisi

• Gantian

• Transposisi

Topik 3: Klasik Kod dan %ipher !IPGK Pulau Pinang#

• Kapal Angkasa Mariner0

• Kod Pembetulan Kesilapan

• Kod 1langan

• Kod $emakan Pariti

• Kod )inear

• Kod 2amming

• Algoritma 3$A

4 Penggunaan Model Matematik dalam "iologi dan Ekologi !IPGKPP & IPGKT"#

• Model Mangsa - pemangsa4 generasi terpisah dan tak terpisah& persamaan logistik

interaksi antara spesis& simulasi.

• Penggunaan persamaan pembe5aan yang mudah dalam model dos dadah yang

selamat dan berkesan.

• Model penularan penyakit seperti AI$& selsema burung dan lain-lain.

' "e(erapa Idea )tama Matematik "erkaitan dengan Kalkulus !IPGK Tuanku "ainun#

• Penghampiran Ar%himedes bagi 6

• Penentuan luas bulatan Ar%himedes• Paradoks 7eno

• Penyiasatan lengkung kubik 8e9ton

M T E 3 1 1 4 / k k t a n / i p g k p p

8/12/2019 Ppg Mte 3114


M T E 3 1 1 4 / k k t a n / i p g k p p

Topik 1: Matematik dalam Kehidupan eharian !IPGK Tuanku "ainun#

• Peranan matematik teknologi moden

• Matematik sebagai kegiatan budaya yang berterusan

• Asas bagi matematik kontemporari

8/12/2019 Ppg Mte 3114


$: Kod Klasik dan Cipher

$*1 "e(erapa Definisi

Kod

$atu peraturan :petua untuk menukar sebarang maklumat ke dalam bentuk : per9akilan yangberlainan.

Pengkodan

Proses di mana maklumat daripada sumber ditukar kepada simbol untuk dikomunikasi.

Pengdekodan

Proses songsang pengkodan di mana simbol kod ditukar balik kepada bentuk : maklumat yang mudahdi/ahami oleh si penerima.

%ipher

Algoritma atau prosedur yang ditetapkan untuk men#alankan proses enkripsi * mese# dienkod agarmaklumat tidak dapat di/ahami oleh pihak lain ke%uali pihak yang dibenarkan,; atau dekripsi *prosesmengdekod mese# yang diterima kepada mese# yang asal dan mudah di/ahami,

Perkembangan kod klasik dan cipher menggunakan teknik-teknik yang berikut

o Transposisio Gantian

$*$ Transposisi

Kaedah enkripsi mese# yang melibatkan perubahan penyusunan semula huru/ : kumpulan huru/mengikut peraturan atau sistem tertentu

%ipher Pagar Kereta Api

2uru/-huru/ dalam mese# ditulis semula dalam dua atau lebih baris. Kemudiannya& di%antumkan semulauntuk membentuk mese# yang telah dienkodkan.

<ontoh4

Mese# = KAMI TE3TIP1 ()E2 ME3EKA )AGI > bila ditulis dalam )IMA baris men#adi

K E 1 M A A 3 ( E ) M T ) 3 A I I E E G T P 2 K Idan bila digabungkan semula men#adi mese# = KE1MAA3(E)MT)3AIIEEGTP2KI =

$i penerima akan menyusun mese# yang diterima dalam lima baris dan memba%a mengikut arah yangdipersetu#ui dengan si pengirim ? dalam %ontoh ini dari atas ke ba9ah untuk mengdekod mese# kepadayang asal.

%ipher +intasan

2uru/-huru/ dalam mese# ditulis semula mengikut satu lintasan yang tertentu& misalnya mengikutlintasan spiral dari luar ke dalam yang tersusun dalam satu segiempat sama. Bilangan petak dalamsegiempat sama yang diguna merupakan rahsia antara si pengirim dan si penerima.

M T E 3 1 1 4 / k k t a n / i p g k p p

http://en.wikipedia.org/wiki/Encryption#cite_note-Goldreich-1

http://en.wikipedia.org/wiki/Encryption#cite_note-Goldreich-1

8/12/2019 Ppg Mte 3114


<ontoh4Mese# = KAMI TE3TIP1 ()E2 ME3EKA )AGI = selepas ditulis mengikut lintasan spiral akan men#adimese# = KAMITME3EE2GIK3EA)AT)(1PI =

1ntuk mengdekod mese#& si penerima menggunakan segiempat sama yang serupa dengan si pengirimdan memba%a ikut lintasan yang dipersetu#ui.

$*3 Gantian

Kaedah enkripsi mese# yang melibatkan penggantian semula huru/:kumpulan huru/ mengikut peraturanatau sistem tertentu

%ipher Gantian Mudah

$emua huru/ dalam ab#ad dipadankan dengan huru/ se%ara padanan satu dengan satu mengikutperaturan atau sistem yang dipersetu#ui dan dirahsiakan.

<ontoh4

A B < E F G 2 I + K ) M 8 ( P @ 3 $ T 1 C D 7M E + A , ) " % D - G . I / K 0 P 2 T 5 6 7

Meru#uk kepada sistem di atas mese# = $AT1 MA)AD$IA = akan ditulis sebagai =@M3$IM2MC@M>Kedua-dua pengirim dan penerima akan menggunakan sistem yang sama.

%ipher %aesar

$etiap huru/ dalam ab#ad digantikan oleh huru/ yang berkedudukan tertentu daripadanya dalamsusunan ab#ad.

<ontoh4

A B < E F G 2 I + K ) M 8 ( P @ 3 $ T 1 C D 7

, 7 A " % D E - G . I / K + M 0 P 2 T ) 5 6

alam %ontoh ini& setiap huru/ digantikan dengan huru/ yang berada dua tempat selepasnya.

(leh yang demikian& mese# = KE<EME3)A8GA8 = akan ditulis sebagai =I<A<K<P+D)ED)>

%ipher Pigpen

M T E 3 1 1 4 / k k t a n / i p g k p p

8/12/2019 Ppg Mte 3114


$istem ini menggunakan simbol-simbol yang diguna oleh kumpulan Freemason bagi me9akili huru/-huru/ tertentu. <ipher ini #uga dikenali sebagai %ipher Masoni% atau 3osi%ru%ian.

<ontoh4

%ipher At(ash

<ipher ini merupakan %ipher gantian yang mudah yang hanya mengandungi dua baris ab#ad yang yangdisusun se%ara bertentangan arah.

<ontoh 4

A B < E F G 2 I + K ) M 8 ( P @ 3 $ T 1 C D 77 , 6 5 ) T 2 P 0 M + K / I . G - E D % " A

Mese# = BA2A$A +IA BA8G$A = akan ditulis sebagai =D7$727 @37 D7MT27 =

%ipher Kama utra

<ipher ini #uga dikenali sebagai %ipher ats8a8ana yang pernah dihuraikan dalam buku Kama$utra yang ditulis dalam abad ke-" A. $etiap huru/ dipadankan dengan huru/ lain se%ara ra9ak dandigunakan untuk menulis mese# rahsia. Padanan satu dengan satu antara pasangan huru/-huru/ hanyadiketahui oleh pengirim dan penerima.

<ontoh4

A K B % < 7 I E F G M 2 P I + + . K ) E M ,8 G ( / P - @ 0 3 5 $ " T 1 D 6 ) C A D T 7 2

Mese# = TE3PE3A8GKAP = ditulis sebagai = (3F3KGMKF =

M T E 3 1 1 4 / k k t a n / i p g k p p

http://en.wikipedia.org/wiki/Kama_Sutra





8/12/2019 Ppg Mte 3114


3: Kod dan Kriptografi

3*1 Kapal Angkasa Mariner9 19

Pada tahun!0& Amerika $yarikat telah melan%arkan kapal angkasa Mariner" untuk mengambil gamba

Marikh. Transmisi setiap gambar mengambil masa H #am. Misi Mariner selan#ut& seperti Mariner0& telah

menghasilkan gambar yang lebih #elas sebab menggunakan kod pembetulan ralat.

.

Kaedah transmisi gambar oleh Mariner0 dari Marikh ke Bumi yang digunakan pada tahun !0 melibatkan

penggunaan grid halus yang diletakkan ke atas gambar yang dikirim. $etiap =petak> atau piksel& diberi =dar#ah

kehitaman> antara #ulat hingga 0.

M T E 3 1 1 4 / k k t a n / i p g k p p

8/12/2019 Ppg Mte 3114


$etiap nombor ditulis sebagai urutan enam dan !. <ontoh %ara penulisan dalam sistem binari *nombor asas

, adalah seperti di ba9ah4

! !

!

!!

" !

!!

0 !!

J !!!

H !

!!

" !!!!

0 !!!!!!

+adi& dar#ah kehitaman " L !!!!.

alam kes Mariner0& setiap gambar dipe%ahkan kepada J H petak& di mana setiap petak dikodkan oleh

0 digit binari& setiap gambar akan mengandungi satu urutan 0 J H "" " digit binari.

alau bagaimana pun& dar#ah kehitaman setiap petak mengandungi enam digit binari manakala mese# yang

dikirim sebenarnya menggunakan lebih banyak digit bagi setiap dar#ah kehitaman ? sebenarnya digit binari

digunakan bagi setiap petak& oleh yang demikian gambar akan mengandungi urutan J H !H 00

H digit binari.

Proses Transmisi Mese;

M T E 3 1 1 4 / k k t a n / i p g k p p

8/12/2019 Ppg Mte 3114


$ungguh pun& saluran transmisi mese# yang ditun#ukkan di atas mudah. Kadang-kadang mese# yang dikirim

akan diganggu oleh ralat tertentu. $ama ada saluran transmisi yang digunakan merupakan pautan satelit

tanpa 9ayar atau 9ayar tele/on& biasanya saluran tersebut mungkin akan menambah unsur gangguan *noise

yang menyebabkan ralat. Ke#adian ini serupa dengan gangguan suara yang kita alami semasa panggilan

tele/on di ka9asan isyarat lemah.

alam %ontoh di atas& mese# !!! dikirim tetapi mese# yang diterima kurang #elas. +adi& adalah sukar untuk

menter#emahkan digit tengah dan digit terakhir yang diterima !NN

Apakah yang si penerima patut buat bila menerima mese# tersebutN +a9apannya bergantung kepada situasi

Misalnya& adalah mungkin mese# tersebut diminta dikirim sekali lagi ? semasa panggilan tele/on& minta disebut

sekali lagi atau pun semasa menggunakan kad kredit& kad kredit dilalui mesin kad kredit sekali lagi #ika nombor

yang diterima kurang #elas sebab sukar diteka. alam kes misi angkasa lepas Mariner& gambar tersebut tidak

dapat dihantar sekali lagi dan adalah lebih praktikal untuk mengdekod mese# seberapa yang mungkin *oleh

komputer bukan oleh manusia,.

$e%ara am& kesan gangguan dalam saluran komunikasi akan mengakibatkan ralat yang menyebabkan mese#

yang diterima berlainan daripada apa yang dikirim. (leh demikian& dalam %ontoh Mariner0 di atas& kita dapat

lihat situasi di mana " yang ditransmisikan oleh kapal angkasa diterima dan diter#emahkan sebagai !! diBumi.

M T E 3 1 1 4 / k k t a n / i p g k p p

8/12/2019 Ppg Mte 3114


3*$ Kod Pem(etulan Kesilapan

Kod pembetulan kesilapan *ralat, menangani masalah ralat dengan menggunakan konsep lebihan *redundancy

? menggunakan lebih banyak simbol yang diperlukan untuk mese#.

alam bahasa biasa& lebihan kerap berlaku& di mana pengetahuan bahasa dan konteks ianya digunakan ?

membantu kita mengenal pasti ralat tipogra/ikal *e#aan, dan membetulkannya apabila diba%a.

Misalnya& #ika perkataan Ocetakan’ dikirim& ia mungkin diterima sebagai Ocetekan’ atau ‘cetakau’. alam konteks

topik ini& memang dapat dikenal pasti dengan mudah yang ralat tipogra/ikal *e#aan, telah berlaku danperkataan yang betul diteka dengan tepat sebagai Ocetakan’ .

Misi Mariner0 telah menggunakan 0 digit binari untuk mengenkod setiap petak ke%il *piksel, dalam gambar

Marikh. Apabila mengirim isyarat balik ke Bumi& Mariner0 mengirim digit dengan 0 *-0, digit lebihan

Dang lebih mengkagumkan ialah ter#emahan betul bagi setiap rantaian yang mengandungi kurang daripada H

ralat.

+adi4

$etiap rantaian mengandungi enam dan ! L rantaian tiga puluh dua dan ! L

rantaian dengan H ralat didekodkan dengan betul

Bagaimanakah ini boleh berlakuN

Proses mengenkod mese# bermula dengan penukaran teks biasa kepada satu rantaian nombor dengan

menggunakan ab#ad digital berikut. alam kod ini& setiap huru/ *dan #uga tanda isyarat, di9akili oleh urutan

dan ! sepan#ang -digit. (leh yang demikian& urutan-urutan tersebut merupakan nombor antara dan yang

ditulis dalam sistem binari *asas ,.

alam kest Mariner0& satu kod 3eed-Muller yang kuat telah digunakan untuk pembetulan kesilapan. $eperti

yang dinyatakan& mese# 0 digit binari telah ditukar kepada mese# digit binari yang digelar sebagai katakod*codewords,.

Misalnya& mese# yang dikirim mengandungi digit binari. (leh yang demikian& terdapat H mese# yang mungkin&

yang boleh di9akili oleh integer hingga J.

M T E 3 1 1 4 / k k t a n / i p g k p p

8/12/2019 Ppg Mte 3114


alam %ontoh ini& digit lebihan akan ditambah kepada setiap mese# untuk menghasilkan katakod yang

pan#angnya H.

0 = 000 000 00000

1 = 001 001 10110

2 = 010 010 10101

3 = 011 → 011 00011

4 = 100 100 10011

5 = 101 101 00101

6 = 110 110 00110

7 = 111 111 10000

Katakod <<11<11< me9akili integer 1. +ika dibandingkan dengan katakod <<<<<<<< yang me9akili integer <

mudah dilihat baha9a kedua-dua katakod ini berbe5a di empat tempat *ketiga& keempat& keenam dan ketu#uh,.

engan %ara yang sama& #ika dibandingkan <11<11< dengan katakod <1<1<1<1& dapat dilihat sekali lag

baha9a kedua-dua katakod ini berbe5a di empat tempat ? kali ini di tempat kedua& ketiga& ketu#uh dan

kelapan.

Perhatikan yang hanya ada H mese#& iaitu H katakod daripada H 0 rantaian lapan digit binari yang

mungkin. 2al ini akan dapat membantu pengesanan ralat tetapi #uga pembetulan ralat yang tunggal.

+ika !!!!! diterima& memang mudah untuk menyemak baha9a ini bukan katakod dan ralat telah berlaku ?

biasanya tidak pasti hanya satu ralat berlaku tetapi yang pasti adalah sekurang-kurangnya satu ralat telah

berlaku.

$ungguh pun sukar untuk mengetahui mese# asal& prinsip kemungkinan maksimum * principle of maximumlikelihood) boleh digunakan untuk mengdekod mese# yang diterima. Ini boleh dilakukan dengan

membandingkan mese# yang diterima dengan H katakod dan lihat yang mana satu katakod paling rapat

dengan mese# yang diterima.

Apabila ini dilakukan& dapat dilihat yang katakod yang paling rapat dengan <<11111< ialah <<11<11<. Ia hanya

berbe5a di satu tempat ? tempat kelima *yang digariskan,.

(leh sebab setiap katakod berbe5a daripada yang laing dalam tepat empat tempat& mese# yang diterima

<<11111< akan berbe5a daripada yang lain dalam sekurang-kurangnya tiga tempat.

+adi& dapat diandaikan yang ralat #arang-#arang berlaku& #adi katakod yang mungkin ditransmisikan ialah

<<11<11<. alam kes ini& selagi ada satu ralat *dan ini adalah kes yang paling mungkin, ianya dapat

diperbetulkan.

Ini memang benar untuk semua kes di mana satu ralat berlaku ? #adi ia digelarkan sebagai kode pembetulan

ralat tunggal *single-error-correcting code ).

alam %ontoh ini&

H digit katakod

digit maklumat dan

digit lebihan.

M T E 3 1 1 4 / k k t a n / i p g k p p

8/12/2019 Ppg Mte 3114


Kadar maklumat 8

3

$e%ara am&

n digit

Q

? ? ? ? ? ? ? ?

Q Q

k digitmese#

r digitsemakan*lebihan,

Kadar maklumat, 3 n

k .

Bagi Mariner 0& kadar maklumat 3 32

6.

3*3 Kod )langan

$atu %ara yang mudah untuk memperkenalkan lebihan adalah untuk mengulang semua. +adi& #ika ada mese#ia boleh dikodkan dengan mengulang setiap digit n kali.

+ika n & pan#ang kod ulangan ialah 5.

<ontoh 4

S → 10011 → 11111 00000 00000 11111 11111

U → 10101 → 11111 00000 11111 00000 11111

S → 10011 → 11111 00000 00000 11111 11111

I → 01001 → 00000 11111 00000 00000 11111

E → 00101 → 00000 00000 11111 00000 11111

+ika dikirim = 1<<11 as 11111 <<<<< <<<<< 11111 11111& ia akan diterima sebagai urutan , dan ! yang

pan#angnya .

Kita perlu peraturan *algoritma, untuk mengdekod mese# yang diterima.

engan bantuan komputer mengdekod mese#& tekaan mengikut konteks tidak dilakukan tetapi peraturan yang

tepat perlu digunakan.

Misalnya& apabila mese# berikut di terima4

11<11 <<11< 11<<< 1<<<< 1<111 bagaimanakah ianya didekod N

M T E 3 1 1 4 / k k t a n / i p g k p p

8/12/2019 Ppg Mte 3114


Algoritma Dekod (agi Kod )langan Pan;ang '

!. Bilang digit !.

. +ika bilangan digit ! R & tulis 11111.

. +ika bilangan digit ! S & tulis <<<<<.

Perhatikan baha9a kod ini boleh membetulkan ralat tetapi ia mempunyai kad maklumat yang sangat rendah

5

1.

+ika n " *setiap digit diulang " kali,&apakah yang berlaku #ika terika <<11 N

aluran imetri "inari

Kebarangkalian menerima simbol yang silap adalah serupa sama ada simbol atau simbol ! dikirim.

Kebarangkalian menerima simbol yang silap p

Misalnya& #ika p 100

1 & #adi kebarangkalian satu digit tunggal diterima se%ara silap ialah

100

1 .!& #adi

kebarangkalian satu digit tunggal diterima se%ara betul ialah100

99 ..

ianggap semual ralat berlaku se%ara ra9ak ? iaitu se%ara tidak bersandar satu sama lain.

1ntuk memudahkan pengiraan& kod ulangan pan#ang digunakan.

Bolehkah kebarangkalian100

99 . diperbaiki #ika satu katakod satu digit diterimaN

Mese#dikirim

Mese#

dikodkan

Mese# mungkinditerima

Mese#didekod

0 → 000

→

000 001

010 100

→ 0

1 → 111→

101 011

110 111 → 1

M T E 3 1 1 4 / k k t a n / i p g k p p

8/12/2019 Ppg Mte 3114


+ika <<< dikirim&

Pengiraan kebarangkalian mese# yang mungkin diterima4

Pr *<<<, 100

99

100

99 100

99 .J

Pr *<<1, 100

99

100

99 100

1 .H!

Pr *<1<, 100

99 100

1 100

99 .H!

Pr *1<<, 100

1 100

99

100

99 .H!

+adi kebarangkalian mengdekod mese# sebagai <4

Pr *<, Pr *<<<, Pr *<<1, Pr *<1<, Pr *1<<,

.J .H!

.J .

+adi& se%ara purata& kesilapan mengdekod mese# yang dikirim < sebagai 1 berlaku hanya sekali setiap !

kali& kita akan dapat ralat kurang daripada setiap ! *atau !:, U Ini merupak kema#uan yang hebat.

Bagi kod ulangan pan#ang n&

n digit

Q

? ? ? ? ?

Q Q

! digitMese#

n ? ! digitsemakan

Kadar maklumat, 3 n

1. Ini sangat ke%ilU

Kod ulangan dapat membetulkan ralat tetapi kadar maklumatnya sangat rendahU

M T E 3 1 1 4 / k k t a n / i p g k p p

8/12/2019 Ppg Mte 3114


+atihan

!. Anda telah menerima mese# berikut yang ditulis dengan kod ulangan pan#ang .

00000 10010 11011 11000 01111

11110 01010 01000 01011 00001

00111 10000 01100 11100 00000

01000 11111 00111 10111 11101

01111 00010 01000 10111 10000

a, Tukar mese# ini kepada kod digit binari.

b, Tukarkan kepada ab#ad biasa.

. Anda telah menerima mese# berikut yang ditulis dengan kod ulangan pan#ang .

00000 11011 01111 00100 11111

01000 11111 00100 00001 11101

11101 00100 00000 11110 01111

11111 10000 01000 00000 00100

10111 00010 10000 00111 01100

01100 10001 01010 00011 11001

01010 10111 01111 11111 00000

11111 00010 11011 01000 00000

a, Tukar mese# ini kepada kod digit binari.

b, Tukarkan kepada ab#ad biasa.

%, Apakah mese# yang sebenarN

. Kod ulangan pan#ang digunakan untuk transmisi mese#. +ika kebarangkalian membuat kesilapan dalam

satu digit ialah .! dan kita anggap kesilapan berlaku se%ara tak bersandar satu sama lain& kirakan

kebarangkalian mese# yang dikirim diterima sebagai !!!.

M T E 3 1 1 4 / k k t a n / i p g k p p

8/12/2019 Ppg Mte 3114


3*4 Kod emakan Pariti

Kod semakan pariti tunggal merupakan ekstrem daripada kod ulangan. Berbanding dengan kod ulangan& kod

semakan pariti tunggal hanya ada satu digit semakan.

igit semakan ini diperolehi daripada #umlah digit maklumat *mod ,.

$ebagai %ontoh& lihat bagaimana digit semakan dikira

A 000001 1 }

5 digit

maklumat

1 digit

semakan

B 000010 1

C 000011 0

D 000100 1

…

$e%ara am katakod ditulis sebagai c ! c c c " c c 0 di mana

c 0 c ! c c c " c *mod ,.

Bagi kod semakan pariti tunggal&

n digit

Q

>> ? > >

Q

@

k = n ? !digit

mese#

! digit semakan

Kadar maklumatn

k

n

n 1− & amat tinggiU

Akan tetapi& kod semakan pariti tunggal hanya boleh mengesan bilangan ralat yang gan#il tetapi tidak dapat

membetulkannya.

M T E 3 1 1 4 / k k t a n / i p g k p p

8/12/2019 Ppg Mte 3114


+atihan

!. <ari katakod yang me9akili huru/ berikut dalam kod semakan pariti tunggal di atas 4 + & ) &

@ & $ & G & C.

. Tulis mese# 8( E33(3$ dengan kod semakan pariti tunggal.

. Mese# berikut telah diterima dalam kod semakan pariti tunggal4

!! !!!! !!!! !!! !! !! !! !!!! !!! !! !!

a, Kesan di mana ralat telah berlaku.

b, ekod semua huru/ yang lain.

%, <uba teka mese# yang dikirim.

3*' Kod +inear

Perhatikan kod linear pan#ang 0 berikut ada digit mese# dan digit semakan

Katakod pan#ang 0

Q

c ! c c c " c c 0 Q

digit

mese#

digit

semakan

boleh ditulis semula sebagai persamaan linear untuk mentakri/kan digit-digit semakan.

Bila diberi mese# c ! c c &

c " = c ! + c *mod ,

c = c ! + c *mod ,

c 0 = c + c *mod ,

untuk memperolehi katakod C = ;c ! c c c " c c 0V.

M T E 3 1 1 4 / k k t a n / i p g k p p

8/12/2019 Ppg Mte 3114


=

6

5

4

c

c

c

=

110

101

011

3

2

1

c

c

c

.

$ebagai %ontoh& ! akan ditransmisikan sebagai ;!!!V.

+atihan

Tuliskan katakod yang sepadan dengan mese#4

*i, !!! *ii, !!

*a, Berapakah mese# tiga digit yang dibentukkanN

*b, $enaraikan semua katakod bagi kod ini.

Persamaan emakan Pariti

Katakod C ;c ! c c c " c c 0 V menyempurnakan persamaan semakan pariti

c ! + c + c " *mod ,

c ! + c + c *mod ,

c + c + c 0 *mod ,.

Persamaan-persamaan ini dinamakan sebagai persamaan semakan pariti sebab menyemak pariti atau

kegenapan hasil tambah digit-digit dalam katakod ? untuk memperolehi di sebelah kanan& kita perlu dapa

bilangan ! yang genap pada sebelah kiri setiap persamaan.

Persamaan semakan pariti #uga boleh ditulis sebagai

100110

010101

001011

6

5

4

3

2

1

c

c

c

c

c

c

=

0

0

0

&

atau H C T = < &

di mana H ialah matriks semakan pariti.

;C T transpos menegak bagi 'ektor < V

M T E 3 1 1 4 / k k t a n / i p g k p p

8/12/2019 Ppg Mte 3114


Apakah 8ang (erlaku semasa transmisi katakodB

Apabila katakod C ;c ! c c c " c c 0V dikirim

saluran transmisi akan menambah gangguan *ralat,

E ;e! e e e" e e0V

mengakibatkan katakod diterima sebagai

R ;r ! r r r " r r 0V

di mana r i c i ei *mod , .

+atihan

!. +ika C ;!!!V & E ;!!V& %ari R.

. +ika R ;!V& E ;!!V& %ari C.

. +ika R ;!V& C ;!!!V& %ari E.

Biasanya& kita hanya tahu katakod yang diterima& R . +adi masalah adalah untuk mengetahui katakod yang

dikirim C #ika kita terima katakod R . Ini boleh dilakukan dengan men%ari E dahulu.

M T E 3 1 1 4 / k k t a n / i p g k p p

8/12/2019 Ppg Mte 3114


Mengira indrom

Bagi katakod yang diterima& R ;r ! r r r " r r 0V& kita mentakri/kan sindrom& s ;s! s sV bagi R dengan

s! = r ! + r + r " *mod ,

s = r ! + r + r *mod ,

s = r + r + r 0 *mod ,.

3

2

1

s

s

s

=

100110

010101

001011

6

5

4

3

2

1

r

r

r

r

r

r

atau

sT = H R T.

(leh kerana digit-digit sindrom ditakri/kan oleh persamaan semakan pariti yang sama dengan katakod& digi

sindrom akan mendedahkan pola kegagalan semakan pariti.

s dinamakan sebagai sindrom R sebab ia mempamerkan = simptom khas> ralat tanpa mengenal past

sebabnya& seperti %ara kita mengenal sesuatu penyakit daripada simptomnya dan bukan sindrom *sebabnya

yang sebenar, ? %ontoh $I$ $udden In/ant eath $yndrome.

$emua katakod mempunyai sindrom ;V sebab H C T = 0 .

$indrom katakod yang diterima serupa dengan sindrom ralat.

Katakod yand diterima R merupakan hasil tambah katakod C dan ralat E .

R C E .

+adi C R ? E dan

< = H C T = H !R ? E ,T

= H !R T ? E T,

= H R T ? H E T

(leh itu sT = H R T = H E T.

+adi katakod yang diterima R mempunyai sindrom yang sama dengan ralat E .

Maklumat ini sangat berguna sebab ini bermakna #ika R merupakan katakod yang diterima& set ralat yang

mungkin #uga merupakan set 'ektor yang sama dengan sindrom R .

ari atas& #ika R dan E mempunyai sindrom yang sama& kita boleh guna akas penghu#ahan untuk

menun#ukkan baha9a #ika H R T = H E T & #adi R ? E C & di mana C adalah katakod.

Bilangan perkataan dengan sindrom yang sama serupa dengan bilangan katakod.

M T E 3 1 1 4 / k k t a n / i p g k p p

8/12/2019 Ppg Mte 3114


alam kes ini ada H sindrom yang mungkin dan setiap selaras tepat dengan

88

64

8

26

== perkataan.

(leh itu& sebagai %ontoh& H katakod selaras tepat dengan H perkataan dengan sindrom;V.

MenCari perkataan selaras dengan sindrom 8ang di(eri

$ebab sindrom katakod yang diterima R sama dengan sindrom ralat E & satu perkara yan perlu dilakukan untukdekod katakod yang diterima adalah untuk men%ari semua perkataan yang mempunyai sindrom yang

sama dengan R .

Misalnya& kita akan men%ari semua perkataan dengan sindrom ;!V bila kita menggunakan kod linear yang

ditakri/kan. (leh itu&

r ! + r + r " *mod ,

r ! + r + r *mod ,

r + r + r 0 ! *mod ,.

100110

010101

001011

6

5

4

3

2

1

r

r

r

r

r

r

=

1

0

0

atau H R T =

1

0

0

= sT*

engan %ara yang sama& kita akan dapat men%ari semua perkataan yang selaras dengan sindrom ;!V

dengan %ara menyenaraikan semua H pilihan yang mungkin bagi dan ! bagi ketiga-tiga pembolehubah yang

pertama dan men%ari nilai baki tiga pembolehubah tersebut. Misalnya& #ika kita mula dengan r ! & r & r

& kita dapat lihat daripada persamaan ini& kita dapatkan tiga persamaan di mana r " & r & r 0 !.

+adi salah satu daripada H perkataan yang selaras dengan sindrom ;!V ialah ;!V.

Kita boleh memperolehi semua H perkataan dengan %ara yang sama.Misalnya& #ika r ! & r & r !& kita

dapat r " & r !& r 0 & yang membentuk perkataan ;!!V.

M T E 3 1 1 4 / k k t a n / i p g k p p

8/12/2019 Ppg Mte 3114


+atihan

!. <ari 0 perkataan lagi yang selaras dengan sindrom ;!V.

. $enaraikan semua perkataan dengan sindrom

a, ;!V.

b, ;!!!V.

M T E 3 1 1 4 / k k t a n / i p g k p p

8/12/2019 Ppg Mte 3114


Tatasusunan Pia9ai $lepian menyenaraikan semua perkataan yang selaras dengan setiap sindrom bagi kod

linear.

$et perkataan W ;r ! r r r " r r 0V di mana r i atau !& bagi i !& & & 0Q membentuk ruang 'ektordimensi 0 di atas Medan Galois GF*,.

$ebab semua katakod merupakan penyelesaian bagi H C T = <& semua katakod membentuk subruang bag

ruang 'ektor yang mengandungi semua perkataan. imensi sub ruang ini ialah 0 ? .

Khasnya, ini bermakna set katakod akan membentuk kumpulan di bawahpenambahan(mod 2) dan juga hasil tambah mana-mana dua katakod merupakan satukatakod.

+atihan "erkumpulan

!. $emak baha9a hasil tambah mana-mana dua katakod merupakan katakod.

. Pilih sindrom yang tidak sama dengan ;V ? pastikan semua ahli dalam kumpulan anda memilih

sindrom yang berlainan.

a, Pilih satu katakod dan tambah kepadanya setiap daripada perkataan dalam baris yang selaras dengansindrom pilihan anda. Apakah yang anda dapati Nhat do you /indN

b, engan menggunakan sindrom yang sama& pilih katakod yang berlainan dan ulang *a,.

%, engan menggunakan sindrom yang sama& semak yang setiap perkataan yang selaras dengan sindromdlam Tatasusunan Pia9ai $lepian boleh diperolehi sebagai hasil tambah perkataan pertama dalam baris* pemimpin koset , dan katakod dalam la#ur yang sama.

d, Banding #a9apan a,& b, dan %, dengan ahli kumpulan lain.

alam Tatasusunan Pia9ai $lepian& semua katakod disenaraikan sebagai baris pertama bermula dengankatakod ;V.

$etiap baris berikut dalam tatasusunan mengandungi satu koset katakod. alam setiap koset& perkataandisusun dalam setiap baris di mana perkataan pertama dalam setiap baris mempunyai bilangan ! yang palingkurang. Perkataan pertama dalam setiap baris Tatasusunan Pia9ai $lepian dinamakan pemimpin koset .

alam baris pertama& selaras dengan sindrom ;V& perkataan dalam baris tiada !X perkataan pertama dalamsetiap daripada enam baris berikut mempunyai hanya satu ! saha#aX manakala perkataan pertama dalambaris terakhir merupakan salah satudaripada tiga perkataan dalam baris tersebut yang ada tepat dua !.

M T E 3 1 1 4 / k k t a n / i p g k p p

8/12/2019 Ppg Mte 3114


"erat sesuatu perkataan ditakri/kan sebagai bilangan ! dalam perkataan tersebut.

Tatasusunan Piaai lepian boleh dibina bagi kod linear dengan langkah-langkah berikut4

!. alam baris pertama& senaraikan semua katakod yang bermula dengan <.

. Pilih mana satu perkataan& W & yang berat minimum 9eight yang bukan katakod *tidak disenaraikan pada

baris pertama, dan senaraikannya sebagai unsur pertama dalam baris berikut.

. Bermula dengan W & senaraikan semua unsur koset W C & di mana C adalah katakod& dalam urutan yang

sama seperti senarai katakod dalam baris pertama.

". 1langi langkah dan dengan menggunakan perkataan baru X & di mana X tiada dalam dua baris yang

pertama.

5. Ulangi langkah 4 dengan menggunakan perkataan baru yang tiada dalam baris-baris sebelumnya sehingga semua perkataan telah disenaraikan.

Pengdekodan Perkataan 8ang diterima

R ;r ! r r r " r r 0V boleh didekodkan dengan langkah-langkah berikut4

!. Kirakan sindrom s ;s! s sV bagi R .

Ini merupakan sindrom bagi E .

. Guna Tatasusunan Pia9ai $lepian untuk men%ari perkataan dengan sindrom s dengan bilangan ! yang

paling sedikit.

Pilih perkataan ini sebagai E .

. Kirakan < di mana C R ? E.

+atihan

!. <ari < #ika R ;!!!!V.; 8ota4 Apabila menggunakan tatasusunan ini& kita tidak perlu mengira sindrom. $ebab 3 dan E

mempunyai sindrom yang sama& kita hanya %ari 3 dalam si/ir ini. E merupakan perkataan dalam barisyang mengandungi 3. V

. <ari C #ika *i, R ;!!!!!!V& *ii, R ;!!!!!V& *iii, R ;!!!!V.

. Beker#a se%ara berpasangan dan #alankan langkah-langkah berikut4;!V Pilih katakod < untuk dikirim sebagai mese#.;V Pilih ralat E.;V Kirakan 3 < E dan kirimkan kepada pasangan anda.;"V ekod perkataan pasangan anda.;V 1lang ini sebanyak tiga kali4 sekali pilih E yang berat ! *hanya satu ! dalam perkataan,X sekali

dengan E X dan sekali dengan E yang berat *dengan dua ! dalam perkataan,.

alam kes yang manakah anda dapat mengenal pasti katakodN

M T E 3 1 1 4 / k k t a n / i p g k p p

8/12/2019 Ppg Mte 3114


Kod +inear seCara Am

$atu kod merupakan kod linear atau kod kumpulan #ika katakodnya merupakan set 'ektor < yang memuaskan

persamaan H C T = 0, di mana H adalah matriks semakan pariti.

alam kod semakan pariti tunggal & digit-digit c1, c2, c3, c4, c5, c6 dalam katakod [c1 c2 c3 c4 c5 c6 ] memuaskan

persamaan semakan pariti

c6 = c1 + c2 + c3 + c4 + c5 (mod 2),

yang serupa dengan

c1 + c2 + c3 + c4 + c5 + c6 = 0 (mod 2).

Ini ditulis sebagai H C ! ", di mana H = [111111].

Kod ulangan pan#ang #uga boleh ditakri/kan dengan menggunakan persamaan semakan pariti berikut4

c1 + c2 = 0 (mod 2)

c1 + c3 = 0 (mod 2)

c1 + c4 = 0 (mod 2)

c1 + c5 = 0 (mod 2).

H C T = 0, di mana H !

10001

01001

00101

00011

.

$e%ara am& #ika kod ulangan pan#ang n kita akan dapat matriks semakan pariti H yang *n ? !, n

Kod blok merupakan kod di mana setiap katakod merupakan urutan bilangan tetap& n& simbol. Bagi kes kod

linear& pan#ang bloknya ialah bilangan la#ur dalam H .

$indrom, s& katakod yang diterima R diberi sebagai sT = H R T. Koset terdiri daripada semua perkataan yang mempunyai sindrom tertentu.Berat perkataan meru#uk kepada bilangan ! dalam perkataan tersebut.

alam satu koset& perkataan yang mempunyai berat yang minimum dipilih sebagaai pemimpin koset *coset

leader).

1ntuk mengdekod R 4

!. Kirakan sindrom sX

. <ari pemimpin koset E X dan

. Kirakan C R ? E.

M T E 3 1 1 4 / k k t a n / i p g k p p

8/12/2019 Ppg Mte 3114


3*9 Kod .amming

Teori kod pembetulan ralat telah bermula dengan usaha 3i%hard 2amming dalam !"J. $ebagai seorang ahl

matematik& 2amming dapat menggunakan kemudahan komputer di Bell Telephone )aboratories untuk

men#alankan pengiraan matematik. Ketika itu& masa untuk melaksanakan program sangat lama dan apabila

2amming datang beker#a pada hu#ung minggu beliau kerap menemui situasi di mana program pengiraan

terhenti kerana menemui ralat. (leh yang demikian& 2amming memikirkan tentang kebolehan komputer bukan

saha#a untuk mengesan ralat tetapi membetulkannyaU

Pada ! 3i%hard 2amming telah memperkembangkan kod 2amming yang merupakan kod linear yang

dapat membetulkan ralat tunggal.

H =

100110

010101

001011

sT = H RT = H ET.

+ika ralat E = [e1 e2 e3 e4 e5 e6], persamaan boleh ditulis semula sebagai

3

2

1

s

s

s

= e1

0

1

1

+ e2

1

0

1

+ e3

1

1

0

+ e4

0

0

1

+ e5

0

1

0

+ e6

1

0

0

.

$indrom ialah hasil tambah la#ur-la#ur H di mana ralat-ralat saluran berlaku.

(leh yang demikian& #ika mana4

• satu la#ur H adalah < & ralat pada kedudukan tersebut tidak dapat dikesanX dan

• dua la#ur H serupa& kita tidak dapat membe5akan ralat tunggal yang berlaku pada kedua-dua

kedudukan tersebut

Kod linear hanya dapat membetulkan semua pola ralat tunggal #ika la#ur-la#ur H berbe5a dan bukan si/ar

$ebaliknya& #ika semua la#ur H berbe5a dan bukan si/ar& ralat tunggal pada kedudukan berbe5a akan

menghasilkan sindrom yang berbe5a.

Kod binari linear mampu membetulkan semua pola yang tiada lebih daripada satu ralat saluran #ika dan hanya

semua la#ur dalam matriks semakan pariti H berbe5a dan bukan si/ar.

M T E 3 1 1 4 / k k t a n / i p g k p p

8/12/2019 Ppg Mte 3114


Pengdekodan Perkataan

1ntuk mengdekodkan perkataan yang diterima R, sindrom s dikira.

+ika s ialah si/ar& andaikan tiada ralat.

+ika s bukan si/ar dan sama dengan salah satu la#ur dalam H, andaikan ralat tunggal telah berlaku pada

kedudukan tersebut.

+ika s bukan si/ar dan tidak sama dengan mana satu la#ur dalam H , prosedur pengdekodan ini gagal.

Kegagalan pengdekodan dan ralat hanya berlaku #ika dua atau lebih ralat saluran berlaku.

Misalnya& #ika H =

101000111

011001110

101011100

011111000

.

+ika diterima perkataan R ;1<1<<<1<1V& #adi kita dapat mengira s ;11<<V.

$ebab sT merupakan la#ur kelima dalam H , kita andaikan E ;<<<<1<<<<V.

(leh itu C R ? E ;1<1<1<1<1V.

alau bagaimana pun #ika R ;1<1<<<1<1V& kita perolehi s ;11<1V& dan dalam kes ini di mana s bukan

salah satu la#ur dalam H , ini bermakna terdapat ≥ 2 ralat dan prosedur pengdekodan gagal.

+atihan

Bagi matriks semakan pariti H di atas& %uba dekodkan perkataan-perkataan berikut yang diterima4

!i# R = ;!!!!!V !ii# R = ;!!!!!V !iii# R = ;!!!!!V

Bagi kod pembetulan ralat tunggal& bilangan maksimum la#ur bukan si/ar matriks binari yang berbe5a dan

bukan si/ar r ? !.

M T E 3 1 1 4 / k k t a n / i p g k p p

8/12/2019 Ppg Mte 3114


Kod .amming

)a#ur-la#ur dalam matriks semakan pariti H & Kod 2amming terdiri daripada r ? ! la#ur bukan si/ar r ?tuple

*non-zero binary r-tuples , yang tersusun dalam mana-mana satu urutan.

+ika A merupakan matriks m × n dengan pangkat r , dimensi ruang nol A adalah n − r .

$ebab H mengandungi semua la#ur bukan si/ar yang mungkin& ia mengandungi setiap satu daripada la#ur-la#ur

matriks identiti r x r dan mempunyai pangkat r .+adi H merupakan matriks r x n dengan pangkat r dan dimensi subruang yang memenuhi syarat H

C T = 0 iaitu n − r = k.

(leh itu& bilangan digit mese# k = n r = r ? ! ? r .

Bagi setiap integer positi/& 9u#ud Kod 2amming dengan digit semakan r& pan#ang blok n= 2r – 1 dan k = n r−

= 2r – 1 – r .

Kod ini boleh membetulkan ralat tunggal pada mana-mana satu digit. $ebab setiap r-tuple bukan si/ar 9u#ud

sebagai la#ur& kegagalan pengdekodan tidak akan berlaku. +adi prosedur pengdekodan ralat tunggal lengkap.

alau bagaimana pun kod ini tidak dapat mengesan lebih daripada ralat. Kadangkala digit semakan parit

yang lain akan ditambah untuk mengesan *tetapi tidak dapat membetulkan , ralat.)a#ur-la#ur dalam matrikssemakan pariti H boleh disusun dalam mana-mana satu urutan.

Kadar maklumat Kod 2amming

R =n

k =

12

12

r

r

−

−− r

= 1 –12

r −

r

.

Bila r ! "& 3!!.

engan membina Kod 2amming yang mempunyai pan#ang blok yang besar& kita akan dapat kadar

maklumat yang sangat tinggi. $ungguh pun Kod 2amming merupakan perkembangan hebat berbanding

dengan kod semakan pariti tunggal& kod ini tidak dapat membetulkan lebih daripada dua ralat.

$ekitar !0& Bose& <hanghuri and 2o%Yuenghan telah menemui kod pembetulan d9i-ralat Kod B<2

*double-error-%orre%ting %odes, yang lebih kompleks. $eterusnya& kod-kod ini diperkembangkan sehingga

men#adi kod pembetulan t ralat.

M T E 3 1 1 4 / k k t a n / i p g k p p

8/12/2019 Ppg Mte 3114


+atihan

!.*a, Dang mana satu daripada matriks semakan pariti ini merupakan kod pembetulan ralat tunggalN Beri

sebab #a9apan anda.

(i) H =

0111011100

0001000101

1100110011

1010101010

(ii) H =

110110000

000110110

000011011

011011000

*b, Dang mana satu daripada kedua matriks di atas merupakan Kod 2amming N Beri sebab mengapaatau mengapa tidak.

. Guna matriks *ii, daripada soalan ! di atas untuk mengdekod setiap daripada perkataan yang diterimaberikut4

*a, R ;!!!!!V *b, R ;!!!!!!V

*%, R ;!!!V *d, R ;!!!V.

. Pertimbangkan Kod-Kod 2amming yang ditakri/kan oleh tiga matriks semakan pariti di ba9ah.

(i) H =

1010101

1100110

1111000

(ii) H =

1001011

0101101

0011110

(iii) H =

1010101

0110011

0001111

*a, Bagi setiap kod& dekodkan perkataan-perkataan berikut yang diterima4

R 1 = F111<<<< R 2 = F1111<<< *

*b, Tun#ukkan yang dua daripada tiga matriks di atas mentakri/kan kod-kod yang serupa *identical codes,

Panduan4 Tun#ukkan baha9a baris-baris mana satu merupakan kombinasi linear yang lain.

M T E 3 1 1 4 / k k t a n / i p g k p p

8/12/2019 Ppg Mte 3114


3*H Algoritma A

Masalah Pen8e(aran KunCi !Ke8>Distri(ution Pro(lem#

alam sistem tradisional& kun%i yang diguna oleh si-pengirim untuk mengenkod mese# diguna #uga oleh si-penerima untuk mengdekodnya. (leh yang demikian& kun%i tunggal ini mesti di#aga dengan baik dandirahsiakan agar hanya dapat digunakan oleh pihak tertentu.

alam masyarakat moden& masih ada #umlah data yang banyak yang perlu dirahsiakan dan ini mengakibatkan

keperluan penggunaan kun%i bagi pengguna-pengguna kod.

Masalah penyebaran kun%i ini diterangkan oleh $imon $ingh dalam bukunya The <odebook *, sepertberikut4

a classic catch-22 situation. If two people want to exchange a secret message over the phone, the

sender must encrypt it. To encrypt the secret message the sender must use a key, which is itself secret,

so then there is the problem of transmitting the secret key to the receiver in order to transmit the secret

message. In short, before two people can exchange a secret (an encrypted message) they must already

share a secret (the key). (pp. 189–190)

Pada pertengahan tahun J-an& hit/ield i//ie& Martin 2elman dan 3alph Merkle telah men%adangkanpenggunaan %ipher asimetrik *asymmetric cipher , untuk mengatasi masalah penyebaran kun%i. Mereka

men%adangkan penggunaan kun%i berlainan untuk mengenkod dan mengdekod mese#.

Peranan Pemfaktoran

Aktiiti: Faktorkan 518 940 557

arabkan ! !J dengan " !

Akti'iti di atas menun#ukkan betapa sukarnya untuk men%ari /aktor-/aktor hasildarab dua nombor perdana.(leh yang demikian& konsep ini diguna untuk men#anakan sistem pengkodan yang baru yang dinamakansebagai Kriptogra/i Kun%i 1mum * Public Key Cryptography,.

alam kriptogra/i kun%i umum& kun%i untuk mengdekod mese# tidak dapat diperolehi dengan mudah

daripada kun%i yang diguna untuk mengenkodnya. Ini membolehkan pengiriman mese# se%ara elektronikse%ara selamat ke destinasi di mana kun%i umum boleh dihebahkan se%ara umum.

Penggunaan Aritmetik Modular

Aritmetik modular digunakan dalam banyak kriptosistem untuk menyamarkan maklumat dengan mudahkerana /ungsinya yang agak mengelirukan.

+adual berikut menun#ukkan bagaimana nilai P dapat dirahsiakan melalui pengiraan C = # dalam modulo!!.

P 0 1 2 3 4 5 6 7 8 9 10

C = P3 0 1 8 27 64 125

216

343

512

729

1000

C = P3 modulo 11 0 1 8 5 9 4 7 2 6 3 10

Aritmetik modular #uga dikenali sebagai Oaritmetik #amZ diperkenalkan oleh K.F.Gauss *!JJJ-!H,.Bagi sebarang nombor asli n& aritmetik modulo n berasaskan kepada pembahagian set integer Z = {…, −3,−2

−1, 0, 1, 2, 3, …} ke dalam n kelas yang berasingan yang selaras dengan n baki yang mungkin apabila

dibahagi oleh n.

M T E 3 1 1 4 / k k t a n / i p g k p p

8/12/2019 Ppg Mte 3114


Misalnya& #ika n & baki yang mungkin #ika integer dibahagi oleh adalah atau !.

Kelas integer dengan baki merupakan set nombor genap = {..., – 6, – 4, – 2, 0, 2, 4, 6, ...} manakala kelas

integer dengan baki ! merupakan set nombor gan#il = {..., – 5, – 3, – 1, 1, 3, 5, 7, ...}.

$e%ara umum& semua integer dalam kelas yang sama mempunyai baki yang sama apabila terbahagi olehmodulus. Ini bermakna terdapat perbe5aan antara dua integer dalam kelas yang sama #uga merupakangandaan modulus.

+adi& dalam %ontoh di atas& apabila kita memerhatikan perbe5aan antara dua nombor genap kita akanmemperolehi gandaan 2 (8 – 2 = 6 = 3x2) dan apabila kita lihat perbe5aan antara dua nombor gan#il kita #uga

akan mendapat gandaan ( 7 – (– 1) = 8 = 4x2).

ifat Kongruen Modulo

ua integer a dan b dikatakan sebagai kongruen modulo #ika a ? b merupakan gandaan n dan ini ditulissebagai

a [ $ *mod n, .

(leh yang demikian& semua nombor genap ≡ 0 (mod 2) dan semua nombor gan#il ≡ 1 (mod 2).

engan perkataan lain& kita boleh me9akili setiap nombor genap *mod , dengan integer dan setiap nomborgan#il *mod , dengan !.

Aktiiti

!. *a, Apakah baki yang mungkin bila integer dibahagi dengan N

*b, Bagi setiap integer berikut& tulis baki yang diperolehi selepas dibahagi dengan 4

*i, JX *ii, !X *iii, 0X *i', ?!X *', ?X *'i, ?!.

*%, Pasangan integer yang manakah yang kongruen mod N

. Beker#a se%ara berkumpulan.*a, Pilih mana-mana dua integer a dan $ % pastikan semua orang menggunakan pasangan integer yang

$er$e&a.

<ari integer bukan negati/ terke%il a' dan $' di mana

a [ a' *mod J, dan $ [ $' *mod J,.

*b, Kirakan nilai& dengan bantuan kalkulator sainti/ik #ika perlu4

*i, a$ X *ii, a$ *mod J, X *iii, a'$' X *i', a'$' *mod J, .

*%, Berdasarkan pengiraan kumpulan anda& apakah kesimpulan yang anda dapati tentang apa yang

berlaku dengan hasil darab aritmetik moduloN

+ika a [ a' *mod n, dan $ [ $' *mod n,& maka a$ [ a' $' *mod n,.

M T E 3 1 1 4 / k k t a n / i p g k p p

8/12/2019 Ppg Mte 3114


%ontoh4

<ari C 0 \ \ ! \ !J \ *mod ,.

Penyelesaian 4

0 [ J *mod ,& [ " *mod ,& ! [ " *mod ,& !J [ !J *mod ,& dan [ *mod ,.

Ini boleh ditulis semula sebagai

C 0 \ \ ! \ !J \ *mod ,

J \ " \ " \ !J \ *mod ,

!0H \ 0H \ *mod ,

\ ! \ *mod ,

\ *mod ,

J \ *mod ,

" *mod ,

!".

$emak 0 \ \ ! \ !J \ 0" 0 HJ dan 0" 0 HJ *mod , !".

;8ota4 Kalkulator sainti/ik komputer anda #uga boleh melakukan pengiraan aritmetik modulo.V

Aktiiti

<ari C J \ \ ! \ !" \ HJ *mod !, dan semak #a9apan anda.

<ontoh pengiraan aritmetik modulo se%ara berperingkat-peringkat4

%ari 6 = 1143 !mod 13#*

Perhatikan baha9a !! *mod !, !!*mod !, ".

+adi !!"

*mod !, "

*mod !, !0 *mod !, . !!H *mod !, *mod !, *mod !, & dan

!!!0 *mod !, *mod !, H! *mod !, .

!! *mod !, *mod !, *mod !, .

Tidak perlu %ari kuasa yang lebih tinggi bagi !! sebab !!0" ] !!".

Perhatikan yang !!" !! \ !!!! !! \ !!H\ !! !! \ !!H\ !! \ !!.

(leh itu !!" *mod !, !! \ !!H\ !! \ !! *mod !, \ \ " \ !! *mod !,

H! \ "" *mod !, H! \ "" *mod !, \ *mod !,

! *mod !, .

Aktiiti

<ari C !J0 *mod !!,.

Teorem KeCil -ermat

M T E 3 1 1 4 / k k t a n / i p g k p p

8/12/2019 Ppg Mte 3114


Fungsi Euler ^ bagi integer m ditakri/kan sebagai bilangan integer positi/ yang kurang atau sama dengan mdan perdana relati/ *relatively prime, kepada m.

Aktiiti

<ari ^*n, bagi n !& & & & .

$emak baha9a n p ( bagi nombor-nombor perdana p dan (&

dan ^*n, * p ? !, *( ? !,

Teorem Ke%il Fermat menyatakan baha9a bagi setiap integer yang perdana relati/ kepada n&

aJ!n# [ !*mod n,.

Aktiiti

Beker#a se%ar berkumpulan& pilih satu nilai n antara ! dan .

<ari ^*n,

$emak baha9a a^*n, [ !*mod n,.

istem iest>hamir>Adleman !A#

$alah satu kriptosistem kun%i umum yang paling a9al adalah sistem 3$A yang di%ipta oleh Ted 3i'est& Adi

$hamir dan )eonard Adleman. $istem 3$A bergantung kepada kesukaran mem/aktorkan nombor yang besar

dan penggunaan aritmetik modular serta teori nombor.

$istem 3$A boleh diterangkan seperti berikut4

Men8ediakan istem

Pilih dua nombor perdana yang besar& p dan (& di mana pan#ang setiap satu ! digit. * 8ombor perdana inidirahsiakan.,Biar n = p (. *8ombor n dihebahkan se%ara umum tetapi pengetahuan n tidak memungkinkan andamenentukan nilai p dan Y kerana kesukaran mem/aktorkan nombor ini.,

Fungsi Euler unction ^*n, * p ? !,*( ? !, merupakan bilangan integer antara ! dan n yang perdana relati/kepada n ? iaitu& bilangan nombor integer yang /aktor sepunya dengan n adalah !. Fungsi Euler ^*n,mempunyai %iri bagi sebarang integer a antara dan n % ! di mana

a ! k.^*n,= a mod n .

Pilih integer positi/ ra9ak E ^*n, & di mana E perdana relati/ kepada *̂n,. *E & seperti n& diumumkan ?bersama n dan E men#adi kun%i umum,

$ebab pihak yang menyediakan kod ketahui rahsia nombor perdana p dan (& mereka #uga ketahui nilai ^*n, * p ? !,*( ? !,& tetapi nilai ini dirahsiakan daripada orang ramai. +adi bagi pihak yang menyediakan kod& adalahmudah untuk men%ari songsang E modulo ^*n, ? iaitu nombor * di mana

*.E [ ! mod ^*n, &Iaitu nombor * yang memberi

*.E ! k .^*n, bagi sebarang integer k.

8ombor * ini #uga dirahsiakan.

$e%ara ringkas&

unci rahsia p, (, ^*n,& * unci umum n, E.

M T E 3 1 1 4 / k k t a n / i p g k p p

8/12/2019 Ppg Mte 3114


Enkripsi

)angkah pertama adalah untuk me9akili sebarang mese# sebagai urutan integer. $etiap mese# dipe%ahkankepada beberapa blok digit& setiapnya merupakan nombor yang kurang daripada n. $etiap blok bolehdienkodkan se%ara berasingan.

+ika # adalah blok dalam mese# ? iaitu integer antara dan n % !.

$ekarang biarkanC = # E mod n&

Iaitu& kita naikkan kuasa # ke kuasa E dan men%ari bakinya selepas dibahagi dengan n.

engan %ara demikian& C dienkripkan atau mese# berkod yang selaras dengan mese# asal #, dan C ialahmese# yang ditransmisikan dengan apa #ua kaedah *mungkin kurang selamat, yang digunakan.

Dekripsi

1ntuk mengdekodkan mese# C & kita %ari # se%ara mengira

# = C * mod n.

(leh keranaC = # E mod n,

Kita akan dapat

C*

mod n = #E.*

mod n= # ! k .^*n, mod n= # mod n , se$a$ # n.

Ke(erkesanan Kod A

$emasa kod 3$A diperkembangkan& adalah di#angka yang masa untuk mem/aktorkan nombor digit n = p ( akan mengambil masa se#uta tahun dengan bantuan algoritma komputer terpantas di dunia ketika itu. Kini&dengan komputer yang %epat dan %anggih& kaedah pengkodan sebegini mungkin akan dite9askan pada satumasa. (leh yang demikian& sistem-sistem kriptogra/i yang baru sentiasa di%ipta demi menampung keperluankeselamatan dan kerahsiaan ketika menyimpan data dan transmisi maklumat digital. Minat dalam penggunaanKriptogra/i Kun%i 1mum telah memesatkan lagi penyelidikan dan perkembangan teknik pem/aktoran nombordan teori nombor se%ara umum.

%ontoh Pengiraan Algoritma A

_!4 Pilih nilai p dan Y *nombor perdana, p J& Y !! ] n J !! JJ

_4 <ari nilai `*n, *p-!,*Y-!, `*n, *J-!,*!!-!, 0 ! 0

_4 Pilih nilai e *nombor yg relati/ perdana, e !

_"4 <ari nilai d di mana d.e ! mod `*n, - Kaedah Euler d. ! ! mod 0 0 " ! ! H ! ? ! ! ! H ! ? ! * ? !, H ! ! ? ! ! ! *H ? !, ? ! ! ! ! H ? ! H ? *! ? ! H,

H ? ! *0 ? " !, ? !

M T E 3 1 1 4 / k k t a n / i p g k p p

8/12/2019 Ppg Mte 3114


0 ? ! *sebab nilai negati/ #adikena tukar kpd yg positi/,

d 0 - J

_4 +ika diberi& M 0 %ari < < Memod n 0! mod JJ J 0! modJJ 0

0 modJJ 0J0 modJJ 00" modJJ 0 modJJ H0H modJJ H modJJ

0! modJJ 0H 0" 0! modJJ H 0 modJJ J! 0 modJJ J

_0 4 $emakan ? guna M <dmod nM JJmod JJ 0 J! modJJ J

J modJJ 0 modJJ "J" modJJ " modJJ !0JH modJJ !0 modJJ J!0 modJJ modJJ J modJJ modJJ "

JJ modJJ J J" J! modJJ " !0 J modJJ

0" J modJJ 0

Aktiiti "aCaan

$ila ba%a artikel berikut tentang perkembangan $istem 3$A.

M T E 3 1 1 4 / k k t a n / i p g k p p

8/12/2019 Ppg Mte 3114


M T E 3 1 1 4 / k k t a n / i p g k p p

8/12/2019 Ppg Mte 3114


4 Penggunaan Model Matematik dalam "iologi dan Ekologi

• Model Mangsa > pemangsa: generasi terpisah dan tak terpisah persamaan

logistik interaksi antara spesis simulasi*

• Penggunaan persamaan pem(eaan 8ang mudah dalam model dos dadah

8ang selamat dan (erkesan*

• Model penularan pen8akit seperti AID selsema (urung dan lain>lain*

M T E 3 1 1 4 / k k t a n / i p g k p p

8/12/2019 Ppg Mte 3114


' "e(erapa Idea )tama Matematik "erkaitan dengan Kalkulus

• Penghampiran ArChimedes (agi L

• Penentuan luas (ulatan ArChimedes

• Paradoks 7eno

• Pen8iasatan lengkung ku(ik 0eton

ppg mte 3114

Documents