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
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
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
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
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.
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
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.
90
PETA KEDUDUKAN MODUL
MODUL I Error Control
MODUL V Short Random Error Correction
MODUL II Bentuk Matematis
MODUL VI Kode BCH dan RS
91
MODUL III Cyclic Code
MODUL IV Burst Error Correction
MODUL VII CRC dan aplikasinya
Uji Kompetensi
Uji Kompetensi
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
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
94
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
√ √
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 √ √
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
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
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∧
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 :
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
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
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
⊕
104
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
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
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
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 ]
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
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) →
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
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
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
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
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γ
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
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
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()(
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 /
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
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
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
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
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) !
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
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
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.
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.
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).
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
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
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
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
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 :
135
Contoh
Selective Repeat :
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
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