peng ko dean

55
83 LEMBAGA KAJIAN DAN PENGEMBANGAN PENDIDIKAN ( L K P P ) LAPORAN MODUL PEMBELAJARAN BERBASIS SCL Judul : PENERAPAN METODE STUDENT CENTRE LEARNING PADA MATA KULIAH TEKNIK PENGKODEAN Oleh : Ir. Dewiani, MT

Upload: tyas-agustina

Post on 01-Jan-2016

117 views

Category:

Documents


3 download

DESCRIPTION

Shsbe

TRANSCRIPT

Page 1: Peng Ko Dean

83

LEMBAGA KAJIAN DAN PENGEMBANGAN PENDIDIKAN ( L K P P )

LAPORAN MODUL PEMBELAJARAN BERBASIS SCL

Judul : PENERAPAN METODE STUDENT CENTRE LEARNING

PADA MATA KULIAH TEKNIK PENGKODEAN

Oleh : Ir. Dewiani, MT

Page 2: Peng Ko Dean

84

NIP. 132 126 352

Dibiayai oleh Dana DIPA Universitas Hasanuddin Sesuai dengan Surat Perjanjian Pelaksanaan Pekerjaan Nomor : 469/H4.23/pm.15/2008 Tanggal 04 Januari 2008

PROGRAM STUDI TEKNIK ELEKTRO JURUSAN ELEKTRO FAKULTAS TEKNIK

UNIVERSITAS HASANUDDIN FEBRUARI 2008

HALAMAN PENGESAHAN

LAPORAN MODUL PEMBELAJARAN PROGRAM TRANSFORMASI DARI TEACHING KE LEARNING

UNIVERSITAS HASANUDDIN 2008

J u d u l : TEKNIK PENGKODEAN

Page 3: Peng Ko Dean

85

Nama Lengkap : Ir. Dewiani, MT

N I P : 132 126 352

Pangkat / Golongan : Penata Muda Tingkat I / IIIc

Jurusan : Elektro Fakultas / Universitas : Teknik / Unhas Jangka Waktu Kegiatan : 1 (satu) bulan Mulai 04 Januari 2008 s.d. 04 Februari 2008 Biaya : Rp. 4.000.000,- (Empat Juta Rupiah)

Dibiayai oleh Dana DIPA Universitas Hasanuddin Sesuai dengan surat Perjanjian Pelaksanaan Pekerjaan Nomor : 469/H4.23/PM.15/2008. Tanggal : 04 Januari 2008

Makassar 04 Februari 2008

Mengetahui : a.n. Dekan Fakultas Teknik Unhas Pembantu Dekan I Pembuat Modul

Ketua Peneliti

Page 4: Peng Ko Dean

86

Dr. Ing.Ir. Wahyu H.Piarah , MSME Ir. Dewiani, MT NIP. 131 645 219 NIP. 132 126 352

KATA PENGANTAR

Puji syukur ke hadirat Allah SWT karena atas rahmat dan hidayah-Nya sehingga Laporan Modul Pembelajaran Bebasis Student Centre

Learning (SCL) untuk mata kuliah “Teknik Pengkodean” dapat terselesaikan.

Sebagaimana diketahui bahwa salah satu program kerja Universitas Hasanuddin dalam meningkatkan Citra UNHAS 2010 adalah dengan

melaksanakan sistem pengajaran dari Teaching to Learning, yang tentunya diharapkan pada setiap dosen pengasuh mata kuliah untuk melakukan

transformasi sistem pengajaran tersebut.

Penulisan dan penyusunan Modul Pembelajaran Bebasis Student Centre Learning (SCL) ini telah dilakukan semaksimal mungkin, namun

karena keterbatasan waktu dan kemampuan yang dimiliki disadari bahwa modul ini mungkin masih jauh dari kesempurnaan . Oleh karenanya

kritik dan saran yang sifatnya membangun tetap diharapkan untuk kesempurnaan laporan ini.

Terselesaikannya laporan ini tidak terlepas dari dukungan dan kerjasama dari para coach, reviewer, olehnya itu pada kesempatan ini kami

mengucapkan terima kasih yang sebesar-besarnya. Akhirnya semoga laporan modul pembelajaran ini dapat bermanfaat untuk mahasiswa yang

mengambil mata kuliah tersebut. Amin…

Makassar, Februari 2008

Page 5: Peng Ko Dean

87

Ir. Dewiani, MT Nip. 132 126 352

RINGKASAN

Pengiriman dan penerimaaan data dalam berkomunikasi ternyata tidak semudah apa yang di bayangkan, agar supaya proses

telekomunikasi dapat berjalan dengan baik. Dibutuhkan beberapa persyaratan dan faktor agar proses Telekomunikasi itu berjalan denagan lancar

antara lain yaitu flow control, pengalamata, informasi kontrol dan manajemen link.

Namun apakah semua faktor itu telah dipenuhi oleh teknik antar muka pada lapisan fisik? Sehingg perlu mereview fungsi lapis fisik yang

kita ketahui seperti sinkronisasi bit, karakter, frame; kalkulasi bit untuk deteksi dan koreksi kesalahan; kompresi data, dll.

Page 6: Peng Ko Dean

88

Pada dasarnya data yang dikirim hendaknya sama dengan data yang diterima tapi adakalanya terdapat perbedaan antara data yang dikirim

tidak sama dengan data yang diterima karena dalam proses pengiriman data terlebih dahulu melalui bagian pengirim, transmisi dan penerima

dimana kemungkinan besar bisa terjadi error pada salah satu bagian tersebut.

Proses pengiriman data tersebut diawali dengan pembangkitan kode oleh generator matrix yang pada aplikasi coding untuk sistem

komunikasi, kode yang diinginkan harus selalu dimodifikasi untuk memenuhi persyaratan khusus pada panjang kode n dan digit informasi k

yang selanjutnya akan dikodekan dengan menggunakan kode cyclic dan kode Hamming. Selanjutnya pada bagian penerima akan dikoreksi

terlebih dahulu apakah ada error atau tidak

Decoder Maggitt dapat diterapkan pada beberapa code cyclic. Ada hubungan satu-satu antara bentuk error tunggal dan sindromnya. Bila

sindrom tersebut diketahui maka lokasi error tunggal bisa diketahui. Karena sindrom s(x) dihitung dari pesan yang diterima oleh r(x)

Fungsi decoder adalah untuk mendeteksi bentuk kesalahan dari sindrom. Sebuah kode siklik yang dipendekkan dengan panjang kode n-i

dapat diuraikan kembali dengan dekoder Meggitt yang didesain untuk kode asli (n,k). Bagaimanapun juga, ketidakcocokan dapat terjadi pada

saat pewaktuan dari dekoder asli sejak kode word yang tiba mengandung digit n-i. Ketidakcocokan pada pewaktuan dapat diselesaikan dengan

desain sirkuit yang cocok berdasarkan pewaktuan n-i.

Decoding Error Trapping merupakan versi pengembangan dari decoding maggitt dan digunakan untuk aplikasi percobaan. Ini terbukti

sangat efektif dalam mengkoreksi double error atau single burst error. Ada beberapa tipe dari Correcting error yang biasa digunakan anara lain

dengan menggunakan Burst Error Correcting, Short Error Corecting dan Bose-Chaudhuri-Hocquenghem code (Kode BCH) dan Reed Salomon

code (RS-Code)

Dengan menggunakan bantuan algoritma “Peterson Berlekamp” dan “Fast Algoritma” dapat diketahui dan mendetesi letak error

(kesalahan data) yang terjadi selama pengiriman data, apakah berupa single error atau double error. Skema decoding Error Trapping di sini lebih

Page 7: Peng Ko Dean

89

cocok untuk code pendek dengan redundansi yang relatif tinggi dan lebih jarang digunakan untuk code yang panjang. Walaupun demikian versi

ini sangat efektif untuk mengkoreksi kesalahan yang terjadi apakah double atau triple error.

Setelah dilakukan deteksi error maka dilakukan pembetulan kode dengan CRC (Cyclic Redundancy check) dan ARQ (Automatic Repeat

Request) yang seharusnya sesuai dengan data yang dikirim sehingga komunikasi dapat berjalan dengan baik karena informasi yang diterima

sesuai dengan yang aslinya. CRC merupakan hasil operasi pembagian biner dengan suatu pembagi tertentu (generator polinomial). Dalam

penerapannya CRC ini diharapkan bisa memaksimalkan kemampuannya mendeteksi kesalahan (jumlah bit yang salah) dengan minimal jumlah

redudant bits juga merupakan operasi binary division (XOR dan shift). ARQ adalah Fasilitas dalam jaringan yang secara otomatis akan

meminta kembali pengiriman ulang apabila diketahui ada suatu kesalahan dalam proses transmisi. ARQ akan mengulang / tidak mengulang

pengiriman data sesuai dengan feedback dari penerima. Yang paling efisien (Utilitas link lebih tinggi) adalah Selective Repeat dan Yang

paling tidak efisien adalah idle RQ.

Page 8: Peng Ko Dean

90

PETA KEDUDUKAN MODUL

MODUL I Error Control

MODUL V Short Random Error Correction

MODUL II Bentuk Matematis

MODUL VI Kode BCH dan RS

Page 9: Peng Ko Dean

91

MODUL III Cyclic Code

MODUL IV Burst Error Correction

MODUL VII CRC dan aplikasinya

Uji Kompetensi

Uji Kompetensi

Page 10: Peng Ko Dean

92

Lampiran A : Rancangan Pembelajaran Mata Kuliah

RENCANA PEMBELAJARAN BERBASIS KBK Matakuliah : Teknik Pengkodean

Kompetensi Utama : Mampu mengembangkan ilmu pengetahuan dan teknologi khususnya dalam bidang telekomunikasi dan informasi, serta

senantiasa menyesuaikan diri dengan kemajuan ilmu pengetahuan dan teknologi dalam bidang tersebut. (No. 7) Kompetensi Pendukung : Mampu menggunakan bahasa asing sebagai sebagai second language (No.15) Kompetensi Lainnya : Beriman dan bertakwa kepada Tuhan yang Maha Esa, berbudi pekerti luhur, memiliki etika dan moral, (Institusional) berkepribadian yang luhur dan mandiri serta bertanggung jawab terhadap masyarakat dan bangsa (No.17)

Minggu Ke :

Materi Pembelajaran

Bentuk Pembelajaran (Metode SCL)

Kompetensi Akhir Sesi Pembelajaran Indikator Penilaian Bobot Nilai (%)

1 2 3 4 5 6

1

Penjelasan umum tentang topik-topik yang akan dibahas dan metode yang akan diterapkan serta kontrak kuliah

Kuliah

2 Dasar system Kuliah + Kerja - Kemampuan menjelaskan blok diagram sistem 1. Kejelasan uraian dan Konsep 5

Page 11: Peng Ko Dean

93

informasi dan teknik pengkodean

Individual + Tutorial (Project Based Learning)

- Kemampuan menjelaskan struktur aljabar :Grup, Field, Ring, Matrix, saling bebas dan ECF.

- Kemampuan menjelaskan Generator matrix untuk single bit errot dan double bit error

2. Kedisiplinan

1 2 3 (5) (5) 6

3-6 Hamming Code dan Bentuk Sistematis Pengkodean

Kuliah + Kerja Kelompok + Presentasi (Collaborative Learning)

Kemampuan menghubungkan antara teori dengan perhitungan pada decoder dengan encoder

1. Kejelasan isi 2. Keterkaitan metode yang

dipilih 3. Kreativitas 4. Kerja sama tim pada

presentasi

20

7-9

Metode Koreksi Error, Error Locator Polynomial, Syndrome

Kuliah + Kerja Individu + Presentasi (Project Based Learning)

- Kemampuan Menghubungkan teori dengan penerapannya dalam kehidupan sehari-hari. - Kemampuan menganalisis error yang terjadi pada decoder dan encoder (single bit error dan double bit error)

1. Ketepatan ANalisis 2. Kejelasan Alasan 3. Kreativitas 4. Kedisiplinan 5. Kemampuan

menyelesaikan problem set

35

10-15

Kode BCH, RS Code, Maximum Likelihood Decoder, Band Limited Radio) Channel

Studi Kasus + Presentasi (Problem Solving Learning)

- Kemampuan menentukan letak error yang terjadi - Kemampuan menyelesaikan decicion Viterbi

Decoding

1. Kejelasan langkah penyelesaian masalah 2. Kejelasan alasan 3. Ketelitian 4. Cara presentasi 5. Kreativitas

40

Page 12: Peng Ko Dean

94

Page 13: Peng Ko Dean

95

1. Rumusan Kompetensi Program Studi

ELEMEN

KOMPETENSI KELOMPOK KOMPETENSI NO RUMUSAN KOMPETENSI

A B C D E1 Memiliki keahlian dasar dalam bidang ilmu teknik elektro √ 2. Mampu mendesain sistem kelistrikan dan menganalisisnya secara teknis-

ekonomis. √ √ √

3 Menguasai teknik instalasi, transmisi dan distribusi listrik, serta pekerjaan gardu induk.

4 Menguasai bidang pengendalian, pengoperasian dan perawatan mesin-mesin listrik dan mengaplikasikannya.

√ √ √

5 Mampu bekerja sebagai tenaga perencana, pelaksana, pengaturan dan pengendalian sistem, jaringan, perangkat keras dan perangkat lunak yang diaplikasikan dalam bidang telekomunikasi dan informasi dalam format multimedia.

√ √ √

6 Mampu mengantisipasi, merumuskan dan menyelesaikan masalah yang terkait dengan sistem, jaringan, perangkat keras dan perangkat lunak yang diaplikasikan dalam bidang telekomunikasi dan informasi dalam format multimedia.

√ √ √

KOMPETENSI UTAMA

7 Mampu mengembangkan ilmu-pengetahuan dan teknologi khususnya dalam bidang telekomunikasi dan informasi, serta senantiasa menyesuaikan diri

√ √

Page 14: Peng Ko Dean

96

dengan kemajuan ilmu-pengetahuan dan teknologi dalam bidang tersebut 8 Mampu memakai paket-paket perangkat lunak komputer untuk pemodelan dan

simulasi masalah-masalah teknik elektro khususnya dan masalah rekayasa pada umumnya.

√ √

9 Menguasai konsep, rancangan dan aplikasi perangkat keras komputer digital √ √ √ 10 Mampu merencanakan & merancang arsitektur jaringan komputer serta

pengetahuan dasar utk mengadministrasikan suatu jaringan komputer terpadu. √ √ √

ELEMEN KOMPETENSI KELOMPOK

KOMPETENSI NO RUMUSAN KOMPETENSI A B C D E

11 menguasai dasar-dasar teori kendali, baik yang klasik maupun moderen serta aplikasinya dalam analisis dan perancangan sistem kendali.

√ √

12 menguasai pengetahuan tentang perancangan, fabrikasi dan aplikasi berbagai piranti, rangkaian dan sistem elektronika dan mikroelektronika termasuk penggunaan paket-paket perangkat lunak untuk merancang tata letak rangkaian terintegrasi.

13 Mampu berwirausaha / bekerja mandiri / bekerjasama dalam bidang teknik elektro

√ √ √

14 Mampu menggunakan bahasa-bahasa pemrograman yang umum digunakan dalam dunia enjiniring

√ KOMPETENSI PENDUKUNG

15 Mampu menggunakan bahasa asing sebagai second language √ √

16 Mampu terlibat dalam kehidupan sosial bermasyarakat berdasarkan budaya bahari

√ √

17 Beriman dan bertaqwa kepada Tuhan YME, berbudi pekerti luhur, memiliki etika dan moral, berkepribadian yang luhur dan mandiri serta bertanggung jawab terhadap masyarakat dan bangsa

√ √ KOMPETENSI LAINNYA

18 Memiliki jiwa kepemimpinan, peneliti dan enterpreneur serta mampu bersaing √ √

Page 15: Peng Ko Dean

97

Elemen Kompetensi: a. Landasan kepribadian b. Penguasaan ilmu dan keterampilan c. Kemampuan berkarya d. Sikap dan perilaku dalam berkarya menurut tingkat keahlian berdasarkan ilmu dan keterampilan yang dikuasai e. Pemahaman kaidah berkehidupan bermasyarakat sesuai dengan pilihan keahlian dalam berkarya

Page 16: Peng Ko Dean

98

MODUL I

ERROR CONTROL BAB I. PENDAHULUAN

A. Latar Belakang

Pengiriman dan penerimaaan data dalam berkomunikasi ternyata tidak semudah apa

yang di bayangkan. Dibutuhkan beberapa persyaratan dan faktor agar proses Telekomunikasi

itu berjalan denagan lancar.

Faktor-faktor yang perlu ada yaitu :

- Flow control: stasiun pengirim tidak boleh mengirimkan frame dengan laju yang lebih

cepat daripada laju “penyerapan” stasiun penerima

- Pengalamatan: pada saluran multipoint (contohnya LAN), identitas kedua stasiun yang

berkomunikasi harus jelas

- Informasi kontrol dan data dikirimkan pada link yang sama: penerima harus dapat

membedakan kedua jenis informasi tersebut

- Manajemen link: inisiasi (call setup), pemeliharaan, dan terminasi pertukaran data

memerlukan proses koordinasi di antara semua stasiun yang terlibat.

Dalam pengiriman data dari pengirim hingga ke penerima sering terjadi

bahwa data yang diterima tidak sama dengan data yang terkirim, sehingga perlu diadakan

mengontrolan kesalahan (error control) data yang memungkinkan diketahuinya data

yang diterima tersebut terjadi error atau tidak.

B. Ruang Lingkup Isi

Materi yang akan dibahas meliputi : Definisi

Pengaruh Noise

Metoda yang digunakan

Pengenalan Kode Hamming

C. Kaitan Modul

Modul ini merupakan modul ke-1 yang merupakan pendahuluan agar mahasiswa

memahami apa yang akan dipelajari dalam mata kuliah teknik pengkodean ini.

D. Sasaran Pembelajaran Modul

Setelah mempelajari modul ini, mahasiswa diharapkan dapat :

a. Menjelaskan definisi dan ruang lingkup error control

Page 17: Peng Ko Dean

99

b. Menjelaskan pengaruh noise pada pengiriman data

c. Mengetahui metoda yang digunakan pada error control

d. Menjelaskan pemakaian kode hamming untuk memperbaiki salah bit.

BAB II. PEMBELAJARAN

A. DEFINISI DAN RUANG LINGKUP ERROR CONTROL

Problema :

Keterngan : Medium : - Transmisi

- Storage

B. PENGARUH NOISE PADA PENGIRIMAN DATA

Pengaruh Noise : )()( tdtd ≠∧

(1) d(t) : PCM – Voice / picture

Redundansi sinyal suara sangat besar → tahan terhadap salah bit

(2) d(t) : Kode binari dari angka

Tak ada redundansi → sangat peka terhadap salh bit

(3) d(t) : Compressed Digital Voice / picture

Redundansi sangat kecil → rentan terhadap salah bit

{data compression : menghilangkan redudansi olah kata oleh otak → fuzzy system}

Redundancy : apabila terjadi kesalahan tapi penerima tidak merasakan.

Jalan keluar : Tambahi bit redundansi

C. METODA ERROR CONTROL

1. Primitif : - Pengulangan sebanyak (2n + 1) kali, n ε z (integer)

- Retrieval : majoritas

Source Medium Retrieval

d(t)

Noise

)(td∧

Page 18: Peng Ko Dean

100

Contoh :

d(t) = {1 0 1} ;

s(t) = {1 1 1 0 0 0 1 1 1} Symbol

)(ts∧

= {1 1 1 0 1 0 1 1 1} mayoritas 0, ada error 1

algoritma majoritas →

y(t) = {1 0 1)

Bahasan :

Umpama : BER = P(E) = 10-3 = p

Maka :

a. P [salah satu-bit / symbol] = 32 10.3)1(13 −≈−⎟⎟⎠

⎞⎜⎜⎝

⎛pp → majoritas masih benar

dimana : 3 : panjang simbol dan 1 : banyaknya salah

P [salah dua-bit/symbol] = 62 10.3)1(23 −≈−⎟⎟⎠

⎞⎜⎜⎝

⎛pp → majority salah

P [salah tiga-bit / symbol] = 903 10)1(33 −≈−⎟⎟⎠

⎞⎜⎜⎝

⎛pp → majority salah

Jadi {salah-bit} terkoreksi → perbaikan ≈ 103 kali (3 orde of magnitude)

b. Banyaknya bit naik 3-kali → idem BW transmisi atau storage space → mahal

2. Menambah Even . Odd parity bit

Umpama :

d = ( d1 , d2 , d3 , . . . , dk ) tambah 1 bit parity

s = ( d1 , d2 , d3 , . . . , dk , p ) p : bit parity

dengan : idp⊕∑= (even)

1+∑=⊕

idp (odd)

⊕ = exor

⊕ = Modulus-2 adder

EXOR :

Page 19: Peng Ko Dean

101

000110101011

=+=+=+=+

Contoh :

d = ( 1 0 1 1 ) → 1=∑⊕

id

sE = ( 1 0 1 1 1 ) → 0=∑⊕

is

so = ( 1 0 1 1 0 ) → 1=∑⊕

is

Umpama salah satu-bit di S3 →

YE = ( 1 0 0 1 1 ) → 1=∑⊕

iY

Yo = ( 1 0 0 1 0 ) → 0=∑⊕

iY

Bahasan :

• Salah 1-bit → (odd) terdeteksi tapi tak terkoreksi

Satu jalan keluar : sistem ARQ (Automatic Request)

• Salah 2-bit → (even) tak terdeteksi dari parity-cheh saja

• Ada BW hilang untuk retransmission

(bisa sangat significant, jika jarak hubungan jauh)

D. KODE HAMMING ( n,k)

k : banyak nya bit (panjang) data : d

n : panjang kode : C

n-k : panjang bit – parity : p

Umpama : H (7,4) binary

d = ( d1 , d2 , d3 , d4 )

C = ( d1 , d2 , d3 , d4 , p1 , p2 , p3 )

p = ( p1 , p2 , p3 )

dengan :

p1 = d1 ⊕ d2 ⊕ d3 ↔ p1 ⊕ d1 ⊕ d2 ⊕ d3 = 0

p2 = d2 ⊕ d3 ⊕ d4 ↔ p2 ⊕ d2 ⊕ d3 ⊕ d4 = 0

Page 20: Peng Ko Dean

102

p3 = d1 ⊕ d2 ⊕ d4 ↔ p3 ⊕ d1 ⊕ d2 ⊕ d4 = 0

Kemampuan : memperbaiki satu salah-bit

Bukti :

Ambil : q1 = p1 ⊕ d1 ⊕ d2 ⊕ d3

q2 = p2 ⊕ d2 ⊕ d3 ⊕ d4

q3 = p3 ⊕ d1 ⊕ d2 ⊕ d4

Maka :

(1) Tak ada salah : q1 = q2 = q3 = 0

(2) Ada salah satu-bit

Bit salah di :

d1 d2 d3 Ff p1 p2 p3

q1 1 1 1 0 1 0 0

q2 0 1 1 1 0 1 0

q3 1 1 0 1 0 0 1

Kombinasi berbeda → posisi salah bit = terkenali

Terlihat : pola q = (q1 , q2 , q3) unik untuk setiap posisi bit salah di kode yang

diterima.

Kesimpulan : dapat dibuat rangkaian logika untuk mengenali posisi salah bit dan

mengkoreksi data diterima.

Contoh : Pengkoreksi d1

d1 d2 d3

p

Page 21: Peng Ko Dean

103

q = ( 0 0 1 ) → k1 = 1 → }{)( 11

−∧

= dtd

q ≠ ( 1 0 1 ) → k1 = 0 → 11 )( dtd =∧

invers=−

}.{

Catatan :

(1) Dipenerima, pi tak dibituhkan, jadi tak perlu dikoreksi

(2) Karena menggunakan rangkaian logika, pembetulan terjadi seketika (sangat cepat)

(3) Operasi harus per blok kode yang ‘benar’ (tak salah posisi bit awal)

(4) Kode Hamming ε Blok Code

BAB III. PENUTUP

Dalam komunikasi data pengaruh noise yang terjadi selama proses pengiriman data apakah

disisi pengirim, transmisi maupun penerima merupakan hal yang pasti terjadi diamping pengaruh

dari luar lainnya. Akibat dari adanya noise tersebut maka terjadi error jika Noise lebih besar dari

sinyalnya sehingga digunakan metoda error control. Serta penggunaan rangkaian logika untuk

pembetulan kesalahan serta operasi per blok kode dengan menggunakan Kode Hamming.

DAFTAR PUSTAKA

1. Shu Lin & Costello, “Error Control Coding” (Prentice Hall), 2000

2. Wicker, “Error Control Systems for Digital Communication & Storage” (Prentice Hall),

1996

3. Rhee, “Error Correcting Coding Theory” (Mc. Graw Hill), 2001

A N D

Page 22: Peng Ko Dean

104

Page 23: Peng Ko Dean

105

MODUL II

BENTUK SISTEMATIK

BAB I. PENDAHULUAN

A. Latar Belakang

Pengiriman dan penerimaaan data dalam berkomunikasi ternyata tidak semudah

apa yang di bayangkan. Dibutuhkan beberapa persyaratan dan faktor agar proses

Telekomunikasi itu berjalan denagan lancar.

Faktor-faktor yang perlu ada yaitu :

- Flow control: stasiun pengirim tidak boleh mengirimkan frame dengan laju yang lebih

cepat daripada laju “penyerapan” stasiun penerima

- Pengalamatan: pada saluran multipoint (contohnya LAN), identitas kedua stasiun yang

berkomunikasi harus jelas

- Informasi kontrol dan data dikirimkan pada link yang sama: penerima harus dapat

membedakan kedua jenis informasi tersebut

- Manajemen link: inisiasi (call setup), pemeliharaan, dan terminasi pertukaran data

memerlukan proses koordinasi di antara semua stasiun yang terlibat.

Data yang akan di kirim ke penerima dalam system Telekomunikasi

bukanlah data riil tetapi dalam bentuk kode yang sistematik yang mana akan dilewatkan

dari ENKODER dan diterima oleh DEKODER sehingga menjadi data aslinya kembali.

B. Ruang Lingkup Isi

Materi yang akan dibahas meliputi : Generator MAtrix

Null_Space Matrix

Dekode - Enkoder

Syndrome

C. Kaitan Modul

Modul ini merupakan modul ke-2 yang merupakan penjelasan dari modul

satu secara terinci mengenai tahapan awal dari Pengkodean.

D. Sasaran Pembelajaran Modul

Page 24: Peng Ko Dean

106

Setelah mempelajari modul ini, mahasiswa diharapkan dapat :

e. Menjelaskan Generator Matrix dari pembangkitan data

f. Menjelaskan Null-Space MAtrix

g. Mengetahui fungís dekoder ddan enkoder pada pembangkitan data

h. Menjelaskan síndrome yang terjadi apabila ada salah bit.

BAB II. PEMBELAJARAN

Diketahui :

d = ( do , d1 , d2 , … , dk-1 ) ↔ d (x) = do + dq.x + d2.x2 + … + dx-1.xk-1

g(x) = 1 + gq.x + g2.x2 + … + gn-k.xk-1

Dicari :

C = ( po , p1 , p2 , … , pn-k-1 , do , d1 , … , dn-k )

C = ( Co , C1 , … , Cn-k )

do , d1 , … , dn-k = sistematik code.

Solusi : {code over GF (2) }

xn-k . d(x) = do.xn-k + d1.xn-k+1 + … + dk-1.xn-1

DEG [ g(x) } = n-k ;

DEG [ xn-k.d(x) ] = (n – 1)

Jadi, jika { xn-k.d(x) } dibagi g(x) →

xn+k.d(x) = a(x) . g(x) + b(x)

dengan :

b(x) = bo + b1.x + b2.x2 + … + bn-k-1.xn-k-1

atau :

b(x) + xn-k.d(x) = a(x).g(x).c(x)

dimana : a(x) . g(x) : dapat dibangkitkan oleh g(x)

bo + b1.x + … + bn-k-1.xn-k-1 + … + dk-1.xn-1

Page 25: Peng Ko Dean

107

Contoh :

* d = ( 1 1 1 0 ) → d(x) = 1 + x + x2 + 0.x3

g(x) = 1 + x + x3

* Kode sistematik (7,4) = ….. ?

Jawab : n = 7 ; k = 4 → x3.d(x) = x3 + x4 + x5 + 0.x6

Mencari b(x) : { sisa hasil bagi xn-k.d(x) / g(x) }

g(x) = x3.d(x)

1 1 0 1 / 0 0 0 1 1 1 0 / 0 1 1 0 ← tidak diperlukan

0 0 0 0

0 1 1 1

1 1 0 1

0 1 0 1

1 1 0 1

0 1 0 0 ← { deg = 1 } < deg [ g(x) ]

0 0 0 0

0 1 0 → b(x) = 0.x0 + 1.x1 + 0.x2

Code : d(3) = 0 0 0 1 1 1 0

b = 0 1 0 0 0 0 0 imbuhan

c = b + d(3) = 0 1 0 1 1 1 0 ↔ [C] = [ b . d ]

GENERATOR MATRIX

* (n,k) code : subspace dari

* Jadi Generator matrix : vektor basis

Satu pilihan : code dari vektor basis data

Contoh :

Kode (7,4) dengan g(x) = 1 + x2 + x3

Page 26: Peng Ko Dean

108

d b C

1 0 0 0 1 0 1 1 0 1 1 0 0 0

0 1 0 0 1 1 1 1 1 1 0 1 0 0

0 0 1 0 1 1 0 1 1 0 0 0 1 0

0 0 0 1 0 1 1 0 1 1 0 0 0 1

basis dari basis dari code

data (vektor) (vektor)

NULL – SPACE / PARITY CHECK MATRIX

G = [ Pk,n-k ! Ik ] → H = [ In-k ! PTn-k,k ]

Contoh :

d = ( 1 0 1 1 ) → C = d . G

C.HT : { ∑ baris 4, 6 & 7 dari HT ≡ ∑ kolom 4, 6 & 7 dari H }

4 : 1 0 1

5 : 1 1 0

6 : 0 1 1 +

0 0 0

Umpama : ε = ( 0 0 0 0 1 0 0 ) → r = c’ = c + ε = ( 0 0 0 1 1 1 1 )

c’.HT = { ∑ baris 4, 5, 6 & 7 dari HT }

1 1 1 0 1

0 1 1 1 1 ≡ k5 dari H

1 1 0 1 1

Catatan :

Data : [ d0 d1 d2 d3 ]

(1) Geser 3-bit → [ 0 0 0 d0 d1 d2 d3 ]

(2) Bagi dengan g(x) ; diambil sisa hasil bagi [ p0 p1 p2 ]

Page 27: Peng Ko Dean

109

(3) Sambung [ p ] dengan [ r ] → [ p0 p1 p2 d0 d1 d2 d3 ]

DEKODER

Kode sistematik :

xn-k.d(x) = q(x) . g(x) + b(x)

→ c(x) = b(x) + xn-k.d(x)

Penghasil sisa : xr.d(x) / g(x)

{ operasi mod. g(x) }

* Shift register kosong dulu (awal operasi semua SR dinolkan)

(i) k = 1 ; d(x) dimasukkan (serial), high order bit first, ke sistem dan output.

Setelah data habis, SR memuat xr.d(x) mod. [g(x)]

Catatan :

d(x) = d0 + d1.x + … + dk-1.xk-1

d = 1 0 1 1 0 1 0 1 → [ p0 p1 p2 1 0 1 1 0 1 0 1 ]

x7

(i) k = 0 ; isi SR dikeluarkan ke-output

secara otomatik SR dinolkan }

(ii) idem (1) ; dstnya.

COBA :

1.* Siklis kode (kode siklis) (7,4) dengan g(x) = 1 + x + x3 ; d(x) = 1 + x + x3

* Cek kebenaran hasil akhir !

Jawab :

a. n = 7 ; k = 4 → x3.d(x) = x3 + x4 + x6

1 1 0 1 / 0 0 0 1 1 0 1 \ 0 0 0 1 (hasil bagi = 0 0 0 1 → x3)

1 1 0 1

Page 28: Peng Ko Dean

110

0 → sisa hasil bagi ( 0 0 0 0 )

Kode : [c] = [ b d ] = [ 0 0 0 1 1 0 1 ]

b. Shift Register

2. g(x) = 1 + x + x3 ; kode siklis (7,4) ; d(x) = 1 + x2 + x3

Jawab :

a. x3.d(x) = x3 + x5 + x6

x3.d(x)

g(x) → 1 1 0 1 / 0 0 0 1 0 1 1 \ 1 1 1 1

1 1 0 1

0 0 1 1

1 1 0 1

0 1 1 1

1 1 0 1

0 1 0 1

1 1 0 1

1 0 0

Kodenya : [ 1 0 0 1 0 1 1 ]

b. Shift Register

ENKODER ALTERNATIF

g(x) : satu faktor dari : xn + 1

atau :

xn + 1 = g(x) . h(x)

→ kode (n,k) : Deg. [g(x)] = n – k

Jadi : deg. [h(x) = n – (n – k) = k

Dapatkah c(x) dibangkitkan oleh h(x) ???? (dapat!!)

c(x) = c0 + c1.x + … + cn-1.xn-1 = a(x).g(x) →

Page 29: Peng Ko Dean

111

c(x),h(x) = a(x).g(x).h(x) = 0 mod. (xn + 1)

xn + 1

Koef. dari suku xj di c(x).h(x) = 0 →

ho.cj + h1.cj-1 + … + hk.cj-k = 0

Tapi : hk = 1 { deg. [h(x)] = k } →

cj-k = ho.cj + h1,cj-1 + … + hk-1.cj-k-1 ( j = 0, 1, …, n-1 )

untuk j = n-1 → cn-k-1 = ho.cn-1 + h1.cn-2 + … + hk-1.cn-k

Pada kode sisi : ( cn-k, … , cn-1 ) ≡ ( d0, d1, … , dk )

- Enkoder dengan h(x)

- Dipilih bila banyak SR < dengan g(x)

Langkah :

1. Dengan L = 1, data : (do, … , dk) dimasukkan ke sistem, output dan SR.

2. Setelah semua data masuk (k-kali right shift) ; l = 0 , kini :

B = ho.cn-1 + … + hk-1.cn-k = cn-k-1

3. SR digeser hingga akhirnya diperoleh c (sebanyak n-k-1 kali)

Catatan :

· Sistem digambar untuk kode binary

· Rangkaian dapat digunakan untuk pengkodean non binary dengan :

gj → -gj

hj → -hj

SINDROME

Div. algorithm :

* r(x) = q(x).g(x) + s(X)

* Deg. [s(x)] < Deg. [g(x)]

Kasus-1 : ε(x) = 0 → r(x) = c(x) = a(x).g(x) atau : s(x) = 0

Page 30: Peng Ko Dean

112

Kasus-2 : ε(x) : suatu code-word = c1(x)

→ r(x) = c(x) + c1(x) = c2(x) = a2(x).g(x)

atau : s(x) = 0

Catatan :

Untuk selanjutnya : kasus-2 tak diperhatikan (dianggap tidak ada)

Kasus-3 : ε(x) = ε0 + ε1.x + … + εn-1.xn-1 ≠ 0

→ r(x) = c(x) + ε(x)

= a(x).g(x) + {l(x).g(x) + k(x)}

= { a(x) + l(x) } g(x) + k(x) }

= q(x).g(x) + s(x)

Catatan :

Sindrom s(x) = sisa hasil bagi r(x) oleh g(x)

Jadi rangkaian pembangkit / penghitung sindrom = pengkoda [r(x) masuk dari kiri]

Dan : high order first, kondisi awal = 0 0 … 0

Setelah semua data (kode) masuk, isi SR = sindrom

COBA :

Hitung isi SR jika masukan : r(x) = 1 + x3 + x4 + x5 + x6

Contoh :

Sindrome Gen. Untuk kode siklik (7,4) dengan : g(x) = 1 + x + x3

r(x) masuk dari kiri.

SINGLE BIT ERROR

Dasar :

1. Syndrome ≠ 0 ; ada error

2. Synd.[r(x)] = synd.[ε(x)]

3. Shift cyclic dari c(x) adalah anggota code / code polynomial

Page 31: Peng Ko Dean

113

Akibat :

* Andaikan, bit salah ada di posisi l-bit sebelum bit terakhir

* Jika r(x) digeser cyclic l-bit ke kanan, maka posisi error ada di bit-terakhir dan

Syndrome selalu sama dengan syn [xn-1]

Dapat dibuktikan :

Synd.[xl.r(x)] dapat diperoleh dengan menggeser siklis syndrome generator yang telah

berisi synd.[r(x), l-bit siklis ke kanan.

LATIHAN SOAL

1. Buktikan bahwa g(x) = 1 + x + x4 adalah generator polynomial dari cyclic code (15,10)

2. Hitung isi syndrome generator jika r = (1101001) dengan g(x) = 1 + x x3

3. Jika : g(x) = 1 + x + x3

d(x) = x + x2

(n, k) = (7, 4)

Cari / tentukan kode sistematiknya

BAB III. PENUTUP

Dalam bab ini menguraikan pembangkitan kode oleh generator matrix serta null space

matrix sebelum data dikirim melalui decoder dan setelah diterima oleh encoder serta apabila

terjadi kesalahan data maka akan terjadi nilai dari syndrome tidak sama dengan nol tetapi kalau

tidak terjadi error maka nilai dari syndrome akan sama dengan nol.

DAFTAR PUSTAKA 4. Shu Lin & Costello, “Error Control Coding” (Prentice Hall), 2000

5. Wicker, “Error Control Systems for Digital Communication & Storage” (Prentice Hall),

1996

6. Rhee, “Error Corrcting Coding Theory” (Mc. Graw Hill), 2001

Page 32: Peng Ko Dean

114

MODUL III

LINEAR BINARY BLOCK CODES BAB I. PENDAHULUAN

A. Latar Belakang

Pengiriman dan penerimaaan data dalam berkomunikasi ternyata tidak semudah apa

yang di bayangkan. Dibutuhkan beberapa persyaratan dan faktor agar proses Telekomunikasi

itu berjalan denagan lancar.

Faktor-faktor yang perlu ada yaitu :

- Flow control: stasiun pengirim tidak boleh mengirimkan frame dengan laju yang lebih

cepat daripada laju “penyerapan” stasiun penerima

- Pengalamatan: pada saluran multipoint (contohnya LAN), identitas kedua stasiun yang

berkomunikasi harus jelas

- Informasi kontrol dan data dikirimkan pada link yang sama: penerima harus dapat

membedakan kedua jenis informasi tersebut

- Manajemen link: inisiasi (call setup), pemeliharaan, dan terminasi pertukaran data

memerlukan proses koordinasi di antara semua stasiun yang terlibat.

Dalam proses pengiriman dan penerimaan data, umumnya data yang asli

tersebut harus dikodekan terlebih dahulu, dimana dikenal dengan dua pengkodean yaitu kode

binear dan non binear.

B. Ruang Lingkup Isi

Materi yang akan dibahas meliputi : Matrix Linier

Parity check Matrix

Bobot dan Kode Hamming

Bobot Enumeration

Jenis-jenis Kode Linear

Golay Code

Kode Hadamark

C. Kaitan Modul

Page 33: Peng Ko Dean

115

Modul ini merupakan modul ke-3 yang merupakan kelanjutan penjelasan ari

modul satu dan dua mengenai kode binear serta dilengkapi dengan bebarapa jenis pengkodean

antara lain kode Golay dan Hadamark

D. Sasaran Pembelajaran Modul

Setelah mempelajari modul ini, mahasiswa diharapkan dapat :

i. Menjelaskan Matrix Linear dari pembangkitan data

j. Menjelaskan Parity check MAtrix

k. Mengetahui cara mendapatkan robot dan kode Hamming

l. Menjelaskan Kode Hadamark..

BAB II. PEMBELAJARAN NON BINER ; contohnya Reeed Solomon GF(2m)

KODE BINER LINER ;contoh: kode GF(2)

Bentuk umum : (n,k) dimanan n:kolom, k:baris

MATRIX LINIER CODE

• Kode linier (n,k) ditentukan oleh kXn generator matrix G jika C=code linier kombinasi G

dgn data d (d0,d1 …,dk-1) maka c= d0g0+d1g1+…dk-1gk-1

• Parity check

Dimana pij=0 atau 1

10

....... 1,12,21,10,0

1

0,

−−≤≤

++++== −−−−

=∑

knj

dpdpdpdpdPj kjkkjkjj

k

iijiγ

Page 34: Peng Ko Dean

116

[ ]

⎥⎥⎥⎥

⎢⎢⎢⎢

=

⎥⎥⎥⎥⎥⎥

⎢⎢⎢⎢⎢⎢

=

−−−−

−−

−−

1

1

0

0,11,10,1

1,11,1,10

1,01,00,0

)(

1.....100

................................

0....010

0....001

kKKK

kn

kn

kKNKX

g

gg

PPP

PPP

PPP

IPG

Μ

Μ

GENERATOR MATRIX

C = d.G; dimana

Misalkan d=(101)

• ……… nonsystematik

» ……systematik

PARITY CHECK MATRIX

Null space : C.HT=0, G.HT=0

Kode linier C(n,k) memiliki parity check H

( )101100010110100011011011

)101( =⎥⎥⎥

⎢⎢⎢

⎡=c

( )011101100011010110001101

)101( =⎥⎥⎥

⎢⎢⎢

⎡=c

knfedcba

Hkfcebda

G

nn

−⎭⎬⎫⎥⎦

⎤⎢⎣

⎡=→

⎪⎭

⎪⎬

⎥⎥⎥

⎢⎢⎢

⎡=

444 3444 21444 3444 21

10...01...

101010001

⎥⎥⎥⎥⎥⎥

⎢⎢⎢⎢⎢⎢

=

1001......

fcebda

H T

Page 35: Peng Ko Dean

117

BOBOT & JARAK MIN HAMMING

Bobot = banyak bit”1” dari code ◊(w)

Jarak = banyak bit berbeda dari beberapa code◊(dH)

Mis: c1 = 1 0 1 1 0 0 0 → w1=3

c2 = 1 1 0 0 0 1 0 → w2=3

0 1 1 1 0 1 0 → dH=4

Dgn mengetahui dmin maka error dpt diketahui:

dmin ≥ 2t+1

t = [(dmin-1)/2]

Aturan hamming

Probabilitas I error=

Error corecting:

• Plotkin bound:

Untuk 2k-1 non zero code word:

• Non binary:

• Gilbert-varshamov bound

Parity check:

SYNDROME

• Jika r ≠ c

• e = r + c ; e = n tupple error

• S = ( c + e ) Ht = r. Ht

ini PPin

Pi −−⎟⎟⎠

⎞⎜⎜⎝

⎛= )1(

∑∑=

=⎟⎟⎠

⎞⎜⎜⎝

⎛≥⎟⎟

⎞⎜⎜⎝

⎛≥

t

t

knt

t

kn

in

atauin

002.....22

122min

1

−≤

k

knd( ) ⎥

⎤⎢⎣

⎡−⎟⎟

⎞⎜⎜⎝

⎛≥− ∑

=

t

t

iq q

in

kn0

1log

knd

i in −

=

<⎟⎟⎠

⎞⎜⎜⎝

⎛ −∑ 2

12min

0

Page 36: Peng Ko Dean

118

• c = r + e

STANDARD ARRAY

BOBOT ENUMERATON

Jika Ai adalah bobot I pada code c

A0, A1,…, An distribusi bobot

A0 = 1, A1,…,Admin-1 bobot = 2k untuk k = kecil

dual code = k > n/2

dual code:

PROBABILITAS DIODER ERROR

Probabilitas I error untuk code panjang n

Probabilitas koreksi error

Untuk error lebih besar dari t

⎟⎠⎞

⎜⎝⎛+−

+=

⎟⎠⎞

⎜⎝⎛+−

+=

=

−−

−−

−∑

zzBzzA

zzAzzB

ZBzB

nkn

nkn

n

i

ii

11)1(2)(

11)1(2)(

)(

)(

)(

0

ini pPin

EPi −−⎟⎟⎠

⎞⎜⎜⎝

⎛= )1()(

∑=

−−⎟⎟⎠

⎞⎜⎜⎝

⎛=

t

t

ini ppin

cP0

)1()(

Page 37: Peng Ko Dean

119

Probabilitas error yang tidak dideteksi

JENIS-JENIS KODE LINIER

Hamming code :

untuk code (n,k) n-k : m baris ; n=2m-1

Bobot enumerator = untuk n=2m-1

GOLAY CODE

Binary code &ternary code

Jumlah vektor =GF (q)(n-k)

Stainer systems = (ℓ,w,n) ; ℓ=4 dan ℓ=5

total blok =

∑+=

−−⎟⎟⎠

⎞⎜⎜⎝

⎛=

n

ti

inie pp

in

EP1

)1()(

nn

i

ii

knud

nud

ppBEP

ppApEP

)1()21(2)(

11

)1()(

0

)( −−−=

⎥⎦

⎤⎢⎣

⎡−⎟⎟⎠

⎞⎜⎜⎝

⎛−

−=

∑=

−−

( ) ( ) ( )[ ]2/)1(2/)1( 1111

1)( +− −++++

= nnn zznzn

zA12)12(1)(−

−+=m

zzB m

⎟⎟⎠

⎞⎜⎜⎝

⎛⎟⎟⎠

⎞⎜⎜⎝

⎛=

λλwn

B /

Page 38: Peng Ko Dean

120

HADAMARD CODE

BENTUK UMUM

Product codes

Product code antara c1 & c2

C1 (n, k, d1) & C2 (n2, k2, d2)

Contoh product [3,2,2] = 24 = (9,4,4)

[ ]

[ ] [ ] [ ][ ] [ ] ⎥

⎤⎢⎣

⎡=

⎥⎦

⎤⎢⎣

⎡=⎥

⎤⎢⎣

⎡−+++

=

NN

NNN HH

HHH

H

2

2 1000

1111

Page 39: Peng Ko Dean

121

t1 = [(d1-1)/2] ; t2 = [(d2-1)/2] t2 = 2 t1 t2 + t1 +t2

Gambaran Cyclic Code

Sebuah kode linier (n,k) C over GF(q)

Berlaku hukum

1. Perkalian

2. Pembagian (menghasilkan sisa)

Hubungan g(x),h(x) dan d(x)

g(x) merupakan generator derajat polinomial dari kode.

h(x) merupakan derajat polinomial dari k

d(x) merupakan derajat polinomual dari informasi (data).

xn+1 = h(x).g(x)

c(x) = d(x).g(x)

Contoh Soal

Cyclic code (7,4) dengan g(x) 3 adalah faktor dari X7+1. g(x) dapat difaktorkan shg trdpat

2 g(x), yaitu g(x)=1+x+x3 atau g(x)=1+x2+x3. Deretan informasi yg akan dikirim

d=(1010) dengan polinomial d(x) =1+x2.

Jawaban

11

2210 ....)( −

−++++= nn xcxcxccxc

Page 40: Peng Ko Dean

122

Jika digunakan c(x)=d(x)g(x), maka akan dihasilkan kode word yang bentuknya tidak

sistematik.

c(x)=d(x).g(x)=(1+x)(1+x2+x3) = 1 + x3 + x4 + x5

Atau kode word c = (100110)

GENERATOR MATRIX DAN PARITY CHECK MATRIX

Generator matriks dibentuk oleh kode Cyclic matriks(n,k).

Struktur dari Kode Sistematik

Suatu kode bisa terdiri dari

c = ( ŷ0, ŷ1,... Ŷn-k-1, d0 ,d1,…,dk-1)

Dimana d(x) dan ŷ(x) adalah derajat polinomial

Pengkodean dari Kode Cyclic

Pengkodean dari cyclic kode disempurnakan dengan menggunakan suatu sirkit pembagi

xn-k d(x) pada g(x) dimana suatu (n-k) SSR yang memiliki feedback dengan generator

polinomial g(x).

Dalam pengkodean sistematik, digunakan untuk high rate kode, dimana bit informasi

dikirim tanpa adanya perubahan.

Encoder dengan SSR (n,k) Cyclic Code

Karena urutan informasi menjadi input dari masing2 register, maka bit parity akan

terbentuk dalam register. Pada saat gate off, maka bit parity akan masuk ke saluran untuk

membentuk kode word.

Di bawah ini merupakan register yang digunakan sebagai rangkaian encoder

⎥⎥⎥⎥

⎢⎢⎢⎢

=

0110001110001011101001011000

G ⎥⎥⎥

⎢⎢⎢

⎡=

001110101001111001110

H

Page 41: Peng Ko Dean

123

decoder dengan bilangan polinomial h(x)

Encoder ini lebih sesuai untuk kode yang bernilai rendah yang menggunakan register

khusus.Informasi bit tersimpan dalam register khusus, dan register digeser sebanyak n-k

kali untuk memenuhi bit parity check(n-k).

Syndrome dan Decoding

Syndrome adalah bit vektor yang dibentuk oleh perkalian urutan data yang diterima

melalui matriks parity check.

Hubungan matematisnya : S = r.HT

S = syndrome ; r = data yang diterima(received)

H = matriks parity check

Syndrome, received vektor, matriks parity check

Untuk kode cyclic yang sistematis,syndrome derajat polinomial (n-k-1) merupakan sisa

dari hasil pembagian received polinomial dengan generator matriks

r(x) = q(x).g(x) + s(x)

Atau : s(x) = r(x) mod g(x)

DECODER

Fungsi dari decoder adalah untuk memperkirakan error e(x) berdasarkan pada syndrome

s(x).

Rangkaian encoding digunakan untuk menghitung syndrome

Page 42: Peng Ko Dean

124

Contohnya :Syndrome generator yang dikenal dengan detektor error

Modifikasi Cyclic Code

Agar kode yang diinginkan sesuai dengan format yang disediakan.

Dengan mengubah(memodifikasi) kolom atau baris dari generator matriks (G)

Ada 6 cara modifikasi dari cyclic code

Cara Modifikasi Cyclic Code

Kode cyclic (n,k) dapat ditambahkan menjadi cyclic kode (n+1,k) dengan menambah bit

parity check.

Contoh : Kode Hamming (7,4) menjadi kode tambahan (8,4).

Menghapus bit parity check, yang merupakan inverse dari penambahan kode

Contoh: Kode tambahan (8,4) dapat diubah untuk menghasilkan kode hamming (7,4).

Mengurangi k tanpa mengubah n. Sehingga ada beberapa kode yang dipertahankan dengan

mengganti beberapa kode kata.

Contoh : Kode Hamming(7,4) dengan g(x)=1+x+x3 bisa menjadi kode(7,3) dengan

g(x)=(1+x)(1+x+x3)

Menambah k tanpa mengubah n

Suatu kode dapat dipanjangkan dengan menambah bit informasi

Suatu kode dapat dipendekkan dengan mengurangi bit informasi

Memendekkan Cyclic Code

Suatu kode yg dipendekkan (n-i,k-i) dapat dibentuk dengan menurunkan bit informasi I

dari tiap kode kata dari suatu cyclic kode (n,k).

LATIHAN SOAL

1. Suatu referensi disebut bahwa generator polynomial dari suatu cyclic code (15, 7) adalah

g(x) = 1 + x + x2 + x4 + x8.

a. Buktikan bahwa selain dari referensi itu benar adanya dengan menggunakan g(x)

tersebut !

b. Hitung kode sistematik dari d(x) = 1 + x2 + x5

c.. Hitung syndrome dari received vector dengan satu salah di bit terakhir.

d. Jika r = (111001011010100), hitung d(x) !

Page 43: Peng Ko Dean

125

2. Parity check matrix dari suatu kode (n, k) adalah :

⎥⎥⎥⎥

⎢⎢⎢⎢

=

1111000110010001100101010001

H

a. Hitung (n, k) serta jarak minimum dari kode tersebut

b. Jika dianggap terjadi ≤ 1 salah bit, hitung data yang dikirim jika

r(x) = 1 + x2 + x5

BAB III. PENUTUP

Blok kode linear dengan parity check matrix dapat mnghitung bobot dan jarak Hamming

serta menggunakan Kode Hadamark yang merupakan salah satu teknik pengkodean yang

digunakan dalam pengiriman data.

DAFTAR PUSTAKA 7. Shu Lin & Costello, “Error Control Coding” (Prentice Hall), 2000

8. Wicker, “Error Control Systems for Digital Communication & Storage” (Prentice Hall),

1996

9. Rhee, “Error Correcting Coding Theory” (Mc. Graw Hill), 2001

Page 44: Peng Ko Dean

126

MODUL VII

CRC MENGGUNAKAN ARQ

DALAM KOMUNIKASI DATA

BAB I. PENDAHULUAN

A. Latar Belakang :

Pengiriman dan penerimaaan data dalam berkomunikasi ternyata tidak semudah apa

yang di bayangkan. Dibutuhkan beberapa persyaratan dan faktor agar proses Telekomunikasi

itu berjalan denagan lancar.

Faktor-faktor yang perlu ada yaitu :

- Flow control: stasiun pengirim tidak boleh mengirimkan frame dengan laju yang lebih

cepat daripada laju “penyerapan” stasiun penerima

- Pengalamatan: pada saluran multipoint (contohnya LAN), identitas kedua stasiun yang

berkomunikasi harus jelas

- Informasi kontrol dan data dikirimkan pada link yang sama: penerima harus dapat

membedakan kedua jenis informasi tersebut

- Manajemen link: inisiasi (call setup), pemeliharaan, dan terminasi pertukaran data

memerlukan proses koordinasi di antara semua stasiun yang terlibat.

Namun apakah semua faktor itu telah dipenuhi oleh teknik antar muka pada lapisan

fisik? Sehingg perlu meriview fungsi lapis fisik yang kita ketahui seperti sinkronisasi bit,

karakter, frame; kalkulasi bit untuk deteksi dan koreksi kesalahan; kompresi data, dll.

Dalam terminologinya, beberapa hal yang penting harus diketahui yaitu :

- Frame adalah kumpulan bit yang membentuk paket data yang merupakan unit transmisi

dan error control.

- Transmission Time adalah waktu yang dibutuhkan pengirim untuk mengirimkan semua

bit sebuah frame ke medium transmisi

- Propagation Time adalah waktu yang dibutuhkan oleh sebuah bit untuk melintas

sepanjang medium transmisi dari pengirim ke penerima

- Bit Length of a link adalah jumlah bit maksimum yang dapat berada sepanjang sebuah

sambungan

B. Ruang Lingkup Isi

Page 45: Peng Ko Dean

127

Materi yang akan dibahas meliputi : - Flow Control

- Error Control (CRC dan ARQ)

- Perhitungan CRC dan ARQ

- Selective Repaet ARQ

- Go Back N ARQ

C. Kaitan Modul

Modul ini merupakan modul ke-8 yang merupakan aplikasi dari metode error control

dan pengkodean yang dijelaskan pada modul-modul sebelumnya yang t erjadi pada komunikasi

data .

D. Sasaran Pembelajaran Modul

Setelah mempelajari modul ini, mahasiswa diharapkan dapat :

m. Menjelaskan Metode Error Control CRC

n. Menjelaskan Selective Repeat ARQ

o. Menjelaskan Go Back N ARQ

p. Menjelaskan perhitungan CRC dan ARQ

BAB II. PEMBELAJARAN Beberapa fungsi yang harus dilakukan oleh Data Link Control antara lain :

– Sinkronisasi Frame

– Flow Control

– Error Control

– Pengalamatan

– Data dan kontrol pada jalur yang sama

– Manajemen sambungan

FLOW CONTROL

Flow Control adalah Merupakan teknik untuk memastikan bahwa entitas pengirim tidak

membanjiri entitas penerima dengan data.

Page 46: Peng Ko Dean

128

Flow Control mencegah pengirim terhadap kondisi penerima yang memiliki keterbatasan

kapasitas. Contoh : komunikasi antara PDA dengan PC melalui infrared.

Dalam pngiriman data Penerima harus memproses setiap frame yang datang sebelum

mengirimkannya ke lapisan lebih atas, dan proses ini membutuhkan waktu. Delay ini mungkin

menyebabkan penampung penerima terus terisi (Rr < Rs).

Ada dua cara bagi penerima agar dapat mengontrol aliran frame dari pengirim :

• Stop and Wait Flow Control

• Sliding Window Flow Control

ERROR CONTROL

Error control merupakan suatu mekanisme untuk mendeteksi dan membetulkan kesalahan

yang terjadi dalam transmisi PDU. Ada dua tipe kesalahan :

- Lost PDU. PDU gagal untuk tiba di tujuan.

- Damaged PDU. Reorganized PDU tiba, tapi ada beberapa bit informasi dalam kondisi error. Teknik error control sebagian besar di dasarkan pada beberapa unsur berikut :

1. Error detection, penerima mendeteksi error dan membuang PDU yang error. Ada beberapa

metode error detection, seperti Parity Check dan CRC (Cyclic Redundancy Check). Error

detection dilakukan pada layer MAC.

Page 47: Peng Ko Dean

129

2. Positive acknowledgment, tujuan mengembalikan positive acknowledgment untuk menunjukkan

bahwa PDU diterima dengan baik tanpa error.

3. Retransmission after timeout, sumber mengirim ulang PDU yang belum diacknowledged

setelah kurun waktu tertentu.

4. Negative acknowledgment and retransmission, tujuan mengembalikan negative

acknowledgment terhadap PDU yang terdapat kesalahan. Sumber mengirim ulang PDU

tersebut.

Mekanisme-mekanisme tersebut bertindak sebagai automatic repeat request (ARQ), dimana efek

dari ARQ adalah mengembalikan data link unreliable ke reliable.

CRC (CYCLIC REDUNDANCY CHECK)

CRC merupakan hasil operasi pembagian biner dengan suatu pembagi tertentu (generator

polinomial). Dalam penerapannya CRC ini diharapkan bisa memaksimalkan kemampuannya

mendeteksi kesalahan (jumlah bit yang salah) dengan minimal jumlah redudant bits. Selain itu

CRC juga harus cepat . Operasi algoritma CRC merupakan operasi binary division (XOR dan

shift) => rangkaian dijital, gate.

Gambar 1 : Frame: Message + CRC code

Efektifitas dari CRC adalah mampu mendeteksi :

- Semua kesalahan bit tunggal.

- Semua kesalahan bit ganda, selama C(x) memiliki min 3 suku.

- Semua kesalahan dgn jumlah bit ganjil, selama C(x) mengandung faktor (x+1).

Page 48: Peng Ko Dean

130

- Semua deretan kesalahan (burst error) dgn panjang < k, pangkat tertinggi C(x).

- Sebagian besar burst error yg lebih panjang (99,9 %).

Prosedur CRC dapat dilakukan dengan 3 cara:

1. Aritmetika modulo 2

2. operasi eksklusif-OR

3. T = 2nM + F

T = frame sepanjang (k+n) bit yang akan dikirim, di mana n<k

M = pesan k bit

Polinomial ekspresi semua nilai sebagai polinomial dengan peubah X dan koefisien biner T(X) =

XnM(X) + R(X)

Logika digital yang terdiri dari:

- Shift register (sama dengan panjang FCS),

- Gerbang eksklusif-OR sesuai dengan posisi bit 1 pada pola generator P CRC

- Memerlukan perhitungan xor sebanyak jumlah bit data

Diciptakan metoda checksum untuk mengurangi perhitungan

ARSITEKTUR CRC

Page 49: Peng Ko Dean

131

Gambar di atas menunjukkan arsitektur umum implementasi shift register CRC untuk polinomial

di mana A0 = An = 1 dan semua Ai lainnya sama dengan 0 atau 1.

Rangkaian diimplementasikan sebagai berikut:

- Register berisi total n bit, sama dengan panjang FCS

- Ada tidaknya suatu gerbang xor sesuai dengan ada tidaknya komponen dalaM

polinomial P(x), tidak termasuk xn.

AUTOMATIC REPEAT REQUEST ( ARQ )

ARQ adalah Fasilitas dalam jaringan yang secara otomatis akan meminta kembali

pengiriman ulang apabila diketahui ada suatu kesalahan dalam proses transmisi.

ARQ akan mengulang / tidak mengulang pengiriman data sesuai dengan feedback dari

penerima

Feedback dari penerima :

ACK = acknowledge data = diterima benar

NAK = not acknowledge = data diterima salah

Ada 3 versi ARQ yang telah distandarkan:

1. Stop and wait ARQ

2. Go back N

3. Selective-reject

Page 50: Peng Ko Dean

132

1. Stop And Wait ARQ

Source mengirim single frame dan harus menunggu acknowledgment (ACK).

Error dapat terjadi pada: Frame dideteksi dengan teknik CRC, block sum, dll.

ACK :

Keuntungan: lebih simple

Kelemahan: tidak efisien

2. Go Back N ARQ (Idle RQ)

– Source dapat mengirimkan beberapa frame sekaligus yang diberi nomor.

– Ketika terjadi error, source harus retransmit frame error dan semua

frame setelahnya.

3. Selective Reject ARQ

– Frame yang di-retransmit hanya yang mendapatkan NAK atau timeout.

PERHITUNGAN CRC Dan ARQ

A. CRC (Cyclic Redundancy Check)

Merupakan hasil operasi pembagian biner dengan suatu pembagi tertentu (generator

polinomial)

- Pembagi : Dn Dn-1 …D1

- Deretan bit : b1 b2 b3 …. bm

- Operasi :

- b1 b2 b3…bm)n-1 / Dn…D1 � sisa (Rn-1…R1)

- Dikirim b1 b2 b3…bm Rn-1…R1

Agar bisa mendeteksi jumlah bit kesalahan ganjil : harus habis dibagi oleh (1 + X) Oleh

penerima dilakukan operasi yang sama :

- b1 b2 b3…bm Rn-1…R1 / Dn…D1 � sisa(rn-1…r1)

- Data benar jika rn-1…r1 = 0

- Data salah jika rn-1…r1 ≠ 0

- Pembagi standar internasional

Page 51: Peng Ko Dean

133

- CRC-16 >11000000000000101

- CRC-ITU >10001000000100001

- CRC-32 >100000100100000010001110110110111

- Jika diperlukan pembagi boleh tidak menggunakan standar ini asal memenuhi:

- Diawali dan diakhiri dengan bit 1 ( 1xxxxxx1)

- Jumlah minimum bit “1” : 3 bit

Contoh Perhitungan :

Checksum

� CRC memerlukan perhitungan xor sebanyak jumlah bit data

� Diciptakan metoda checksum untuk mengurangi perhitungan

� Cara perhitungan :

� Data dibagi menjadi kelompok-kelompok 16 bit

� Data kelompok pertama di xor dengan kelompok kedua

� Hasil di xor dengan kelompok ke 3

Page 52: Peng Ko Dean

134

� dst sampai didapat 16 bit checksum dari seluruh data

Contoh Perhitungan :

2. Automatic Repeat reQuest ( ARQ )

ARQ : Selective Repeat

Hanya mengirim ulang untuk paket yang salah

ARQ : Go Back N Mengirim ulang mulai dari paket yang salah :

Page 53: Peng Ko Dean

135

Contoh

Selective Repeat :

Page 54: Peng Ko Dean

136

Go Back N :

Yang paling efisien (Utilitas link lebih tinggi) = Selective Repeat

� Yang paling tidak efisien = Idle RQ

� Utilitas link = f(metoda,BER,panjang paket, jumlah paket sekali pengiriman)

BAB III. PENUTUP

Beberapa fungsi yang harus dilakukan oleh Data Link Control antara lain : sinkronisasi

frame, flow control, error control, pengalamatan, data dan kontrol pada jalur yang sama,

manajemen sambungan

Page 55: Peng Ko Dean

137

CRC merupakan hasil operasi pembagian biner dengan suatu pembagi tertentu (generator

polinomial). Dalam penerapannya CRC ini diharapkan bisa memaksimalkan kemampuannya

mendeteksi kesalahan (jumlah bit yang salah) dengan minimal jumlah redudant bits. Selain itu

CRC juga harus cepat . Operasi algoritma CRC merupakan operasi binary division (XOR dan

shift).

ARQ adalah Fasilitas dalam jaringan yang secara otomatis akan meminta kembali

pengiriman ulang apabila diketahui ada suatu kesalahan dalam proses transmisi. ARQ akan

mengulang / tidak mengulang pengiriman data sesuai dengan feedback dari penerima. Yang

paling efisien (Utilitas link lebih tinggi) adalah Selective Repeat dan Yang paling tidak efisien

adalah idle RQ.

DAFTAR PUSTAKA 10. Shu Lin & Costello, “Error Control Coding” (Prentice Hall), 2000

11. Wicker, “Error Control Systems for Digital Communication & Storage” (Prentice Hall),

1996

12. Rhee, “Error Correcting Coding Theory” (Mc. Graw Hill), 2001