LAPORAN PRAKTIKUM TEKNIK KODING
Disusun Oleh : Abdul Wahid 1210147015
Teknik Telekomunikasi - PJJ PENS Akatel Politeknik Negeri Elektro Surabaya Surabaya
19
PERCOBAAN III ENCODER DAN DECODER KODE KONVOLUSI 1. Tujuan : Setelah melakukan praktikum, mahasiswa diharapkan dapat :
Pengertian prinsip pengkodean dengan kode konvolusi
Sifat-sifat pengkodean kode konvolusi
Kemampuan koreksi kode konvolusi
2. Teori Pendahuluan : Konsep Kode Konvolusi Kode konvolusi merupakan kode non-blok dan lebih tepat untuk disebut dengan kode sekuensial. Karena sifatnya yang non-blok, kode ini sesuai untuk informasi yang panjang frame-nya tidak tentu (tidak terdefinisi). Nama kode konvolusi diambil dengan pertimbangan bahwa proses pengkodean dapat dianalogikan sebagai proses konvolusi dan dekoder akan melakukan proses dekonvolusi. Untuk merealisasikan fungsi konvolusi, sebagai konvolutor sering digunakan rangkaian “shift register” linear yang inputnya akan tergantung pada deretan sinyal input. Dari gambar 1, ditunjukkan bahwa operasi dari encoder konvolusi sangat bergantung pada panjang bit yang mengubah output pada setiap periode (information frame), panjang register yang digunakan sebagai buffer (constrain length) dan rangkaian logika yang menentukan operasi pengkodeannya. Output proses tersebut adalah frame atau simbol yang telah dikodekan. Salah satu cara analisis sinyal pada kode konvolusi adalah menggunakan diagram pohon ( tree diagram) dimana akhirnya dekoder harus bisa melakukan pencarian untuk menemukan sinyal yang mempunyai pola runtutan yang melalui cabang yang seharusnya. Salah satu contoh pengkodean dengan cara itu adalah Viterbi. Parameterisasi Agar mampu bekerja dengan kode konvolusi, maka diperlukan pemahaman tentang beberapa definisi dasar yang nantinya merupakan kunci pengembangan kode tersebut.
20
a. Sebuah kode tree(no,ko) adalah pemetaan dari elemen-elemen semi-finite (agak tak terbatas) GF(q) kepada dirinya sendiri, sedemikian hingga untuk tiap N, bila dua deret semi-finite cocok dengan komponen Nko, maka peta dari deret tersebut juga akan cocok dengan komponen Nno. no= output frameword dan ko=input frame. b. Nk disebut dengan constrain length boleh terbatas dan boleh tidak terbatas. c. Kode mempunyai sifat time invariant, jika fungsinya tidak berubah karena adanya pergeseran waktu. d. Kode mempunyai sifat linear jika fungsi dari dua sequence merupakan pemjumlahan dari fungsi masing-masing sequence. e. Kode disebut systematic jika kode tersebut setiap frame informasinya terlihat tidak berubah sepanjang simbol pertama (ko) dari frame codeword (output) yang dihasilkannya.
Struktur Kode Konvolusi Struktur kode konvolusi (n,k,m), dimana n adalah output encoder, k adalah input dan m adalah memori. Jadi struktur kode konvolusi (n,k,m) dapat diimplementasikan dalam bentuk encoder dengan k jumlah masukan, n keluaran rangkaian sequensial linier dengan panjang memori m. Dimana n dan k adalah bilangan bulat kecil dengan k < n, sementara m harus dibuat besar untuk mencapai probability error yang rendah. Pada kondisi k = 1, deretan informasinya tidak diproses secara blok-blok melainkan dapat diproses secara kontinyu.
Rate Dalam kode konvolusi dikenal dengan istilah rate, untuk menunjukkan lajunya kode dan mempunyai persamaan seperti berikut : R = k / n bit informasi per kanal bit Dimana : k adalah jumlah bit yang masuk tiap satuan waktu n adalah jumlah keluaran Kode rate ½ Untuk mempermudah pengertian tentang rate disini akan diberikan contoh encoder dengan rate ½. Encoder dengan rate ½ akan mengeluarkan 2 bit untuk setiap satu bit masukan, seperti pada gambar 1. Kode rate ½ ini merupakan kode rate yang banyak diaplikasikan. Sedangkan kode rate yang lain misalnya : kode rate 1/3, 2/3, ¾, 7/8 dst. 21
Uj … U3 U2 U1
Dari Sumber
....P3U3 P2U2 P1U1 Ke Modulator Pj
Gambar 1. Encoder Kode Kovolusi Rate ½ Pada gambar 1, tampak bahwa Pj = Uj +Uj-1 , Jika dimisalkan dari sumber diberikan sederetan informasi U1=1, U2=1, U3=0, U4=1 sehingga dapat disusun (1101), maka akan menghasilkan deretan paritas P1=1, P2=0, P3=1, P4=1 atau dapat disusun (1011). Jadi Codeword yang dihasilkan oleh encoder tersebut adalah 11 10 01 11.
Matrix Polinomial Parity Check, Error Correction And Distance Sebagai sebuah operasi pengkodean, maka ada pertanyaan-pertanyaan mendasar misalnya : bagaimana cara melakukan verifikasi (pengecekan kebenaran), bagaimana caranya pengkodean dapat melakukan koreksi kesalahan dan bagaimana evaluasi unjuk kerja pengkode itu sendiri.
Matrix Polinomial Parity Check Jika kita mempunyai matrik generator polinomial G(x), maka sebuah matrik Polinomial Parity Check H(x) adalah matrik berukuran (no-ko) kali no, yang memenuhi persyaratan : G(x)H(x)T=0
Error Correction Kemampuan error-correction ditentukan oleh “distance Hamming” terkecil dari dua codeword yang dibangkitkan.
Distance sebagai alat evaluasi Distance Hamming dari dua word berbeda d(x,y) dengan panjang n adalah jumlah tepat mempunyai isi berbeda. Misalnya: x=10110 dan y=01100, maka d(10110, 01100) =3. Dalam evaluasi performansi, nilai yang paling menarik untuk menghitung kemampuan sebuah kode atau probabilitas kesalahan adalah distance minimum, d*. Distance minimum d*, adalah nilai terendah dari semua kemungkinan distance. 22
Apabila terjadi e kesalahan, dan distance dari tiap word lebih besar dari e, maka dekoder akan mampu melakukan koreksi terhadap kesalahan tersebut ke word terdekat. Apabila d * 2e 1 ,maka error akan dikoreksi, kecuali ada aspek lain yang membuatnya salah, misalnya input yang tidak ideal.
Free Distance Free distance atau minimum free distance dari suatu kode konvolusi dapat didefinisikan dengan persamaan : dfree min {d (v’, v”): u’ u”} di mana v’ dan v” adalah codeword dari informasi u’ dan u” . Bila panjang u’ dan u” tidak sama, maka perlu dilakukan zero padding pada data yang lebih pendek. Berdasarkan persamaan di atas, maka dfree adalah jarak minimum antara 2 sembarang codeword yang merupakan bagian kode. Karena kode konvolusi adalah kode linier, maka : dfree = min {w (v’- v”): u’ u”} = min {w (v): u 0} = min {w (uG): u 0} di mana v adalah codeword dari informasi u . Berdasarkan persamaan di atas, maka dfree adalah codeword berbobot minimum dengan panjang sembarang yang dihasilkan oleh urutan informasi yang tidak sama dengan 0.
ENCODER Contoh sederhana dari teknik pengkodean konvolusi digambarkan dengan rangkaian seperti gambar 2, yaitu berupa enkoder konvolusi (2,1,3) dengan jumlah shift register 3 buah, 2 buah penjumlah modulo2 (berupa gerbang EXOR) dan satu input data. Generator yang digunakan sebanyak 2 buah , yaitu g(1)= (1011) dan g(2)= (1111), jika informasi yang dimasukan adalah U=(10111) maka codeword V akan diperoleh melalui proses : V v0(1) v0( 2) v1(1) v1( 2) v2(1) v2( 2) Sedangkan : v (1) u g (1) Jadi :
dan v ( 2) u g ( 2)
v (1) (10111) (1011) (10000001) v ( 2) (10111) (1111) (11011101)
Sehingga Codeword yang dihasilkan adalah : V (11,01,00,01,01,01,00,11)
23
V(1) U
V
V(2)
Gambar 2. Encoder Kode Konvolusi (2,1,3) Diagram Tree Metode pencarian Tree dan Trellis digunakan untuk mendapatkan kode yang keluar dari enkoder kode konvolusi berdasarkan bit-bit informasi yang diberikan padanya. Diagram tree berbentuk seperti pohon (tree) lengkap dengan sebuah akar (root), dan beberapa batang, dahan, dan rantingnya. Contoh diagram tree untuk kode konvolusi dengan rate ½ dengan nilai (n,k,m) = (2,1,3) adalah seperti berikut : Untuk mendapatkan deretan bit-bit kanal (bit hasil enkode) dari bit-bit data dengan memakai diagram tree, dilakukan cara sebagai berikut: Proses kode tree dimulai dari akar (root) tree, kemudian mengikuti arah diagram ke atas (jika data pertama yang masuk adalah 1) atau arah ke bawah (jika data pertama yang masuk adalah 0). Selanjutnya, dengan membaca kode pada cabang yang diikuti (ke atas untuk data 1, atau ke bawah untuk data 0) akan diperoleh codeword untuk bit tersebut. Sebagai contoh, jika data pertama adalah satu, maka dua bit kanal yang dihasilkan adalah 11. Proses ini akan berlanjut dari cabang pertama yang telah dicapai tadi, sehingga jika bit data kedua adalah nol, maka cabang yang dituju adalah cabang yang bawah dan menghasilkan bit 01. Jika diberikan data 1101…, dengan menggunakan diagram tree pada gambar 3 akan diperoleh deretan bit kanal 11 10 01 11 . . ..
Diagram Trellis Diagram Trellis merupakan diagram yang dibentuk dari diagram tree. Dalam diagram tree tampak bahwa simpul a dan c mempunyai kesamaan pada level tiga ke kanan. Hal yang serupa juga terjadi antara simpul b dan d. Dengan menggabungkan
24
simpul a dengan c, serta simpul b dengan d, maka akan diperoleh diagram Trellis seperti dalam gambar 4. 10 10 01 10
a
11 1 00
01 11
10 11 01 01
b
11 00
1
00
Root
10 10
0
01 11
c
11 1 00
01 00
10 11 01 00
d
11 00 00
Gambar 3. Diagram Tree Kode Rate ½
00
00
10
10
10 11
11
11
11
01
01
01
00
00
Gambar 4. Diagram Trellis Kode Rate ½ Pada gambar 4, tampak bahwa bit paritas yang bergabung dengan bit informasi 0 dibaca
mengikuti garis tebal. Sedangkan yang bergabung dengan bit informasi 1,
dibaca mengikuti garis putus-putus. Sebagai contoh, untuk data input 1101…, garisgaris yang dilewati adalah : garis putus (11), garis putus (10), garis tebal (01), garis putus (11) , sehingga dihasilkan kode 11 10 01 11 … Jumlah baris (yang digambarkan dalam bentuk deretan state serupa dengan posisi horisontal), tergantung dari jumlah kemungkinan yang terjadi pada bit-bit
25
masukan. Untuk contoh di atas, karena k=1 bit, maka jumlah kemungkinannya adalah 2k = 21 = 2, sehingga jumlah baris = 2. Syndrome Syndrome adalah suatu vektor (berbentuk matriks) yang digunakan pada proses decoding untuk mendefinisikan set error yang akan diperbaiki. Syndrome merupakan hasil perkalian antara matriks bit yang diterima (yang umumnya sudah mengandung error) dengan matriks transpose parity HT.
Dengan diketahuinya matriks bit yang
diterima dan syndrome-nya, maka kesalahan pada bit yang diterima dapat diperbaiki.
Kode Catasthropic Kode Catasthropic adalah kode yang menyebabkan terjadinya rangkaian kesalahan (error propagation). Sebagai contoh : jika suatu codeword (dihasilkan oleh enkoder dengan k=3), ditransmisikan melalui Binary Symmetric Channel, maka terdapat kemungkinan 3 bit codeword non zero, semuanya berubah menjadi zero akibat noise pada saluran. Akibatnya, Maximum Likelihood Decoder akan mengestimasi bahwa u(D)=0, sehingga sejumlah error lainnya akan dihasilkan oleh 3 bit codeword yang salah tadi. Kondisi seperti itu sangat tidak diharapkan. Kode yang menyebabkan terjadinya rambatan error catasthropic (catasthropic error propagation)
seperti itu
disebut kode catasthropic. Untuk menghindari hal semacam itu, sebaiknya digunakan kode konvolusi sistematik (karena selalu menghasilkan kode non catasthropic). Indikasi kode catasthropic dapat dilihat dengan berbagai cara. Salah satu caranya, diagram state pada kode catasthropic akan mengandung self loop dengan bobot 0 semua (00 atau 000, atau lainnya) pada state selain state 0 (S0). Selain itu, Rosenberg juga menunjukkan bahwa 1/(2n-1) dari kode konvolusi non sistematik (n,1,m) adalah kode catasthropic. Kode (n,k,m) dengan k>1, tidak mempunyai kode catasthropic sebanyak itu.
3. Prosedur Percobaan : 1. Masukan = Pesan = Informasi Tuliskan pesan yang akan dikirim sebanyak 8 bit : >> pesan_kirim = [1 0 1 1 0 1 0 0] pesan_kirim = 1 0 1 1 0 1 0 0 Tampilkan Pesan yang dikirim : >> stem(pesan) 26
>> xlabel('Jumlah Bit Pesan'); >> ylabel('Amplitudo Bit Pesan'); >> title('Bit Pesan Yang Dikirim');
Atau : >> stem(pesan) >> xlabel('Jumlah Bit Pesan'); >> ylabel('Amplitudo Bit Pesan'); >> title('Bit Pesan Yang Dikirim');
2. Proses Pengkodean ( Encoder) Untuk proses pengkodean, digunakan metode pencarian trellis : digunakan ½ , parameter encoder (2,1,2).
rate yang
>> t=poly2trellis(3,[6 7]); %ditulis dalam oktal Struktur trellis (3,[6 7]) , dimana : 3 adalah constraint length (jumlah shift register ditambah 1), sedangkan [6 7] menyatakan polinomial generator yang terdiri dari 6 = polinomial generator bagian atas dan 7 = polinomial generator bagian bawah. Untuk lebih jelasnya perhatikan gambar encoder dibawah ini.
27
Gambar 5. Encoder Kode Konvolusi (2,1,2) Coba ubahlah struktur trellis berturut-turut :(3,5) , (3,[5 9]),([3 3],[7 4]) dan ([3 3],[7 3 1;2 5 4]). Sebutkan struktur trellis yang mana yang berhasil dan mana yang tidak berhasil ? Jelaskan secara teoritis mengapa hal itu bisa terjadi. >> codeword = convenc(pesan_kirim,t); % hasil pengkodean >> codeword' ans = 1 1 1 1 1 0 0 0 1 0 1 0 1 1 0 1 Tampilkan Hasil Pengkodean : >> stairs(codeword); >> ylabel('Amplitudo Codeword'); >> xlabel('Jumlah Bit Codeword'); >> title('Bit Hasil Pengkodean')
28
Atau : >> stem(codeword); >> ylabel('Amplitudo Codeword'); >> xlabel('Jumlah Bit Codeword'); >> title('Bit Hasil Pengkodean')
V(1) U
V
V(2)
Gambar 6. Encoder Kode Konvolusi (2,1,3)
29
A. Tugas : 1. Ulangi langkah 1, untuk pesan sebanyak 10 bit, 15 bit dan 20 bit 2. Kodekan masing-masing pesan 10 bit, 15 bit dan 20 bit tersebut, menggunakan metode trellis dengan encoder seperti gambar 6. 3.
Dekoder (Pengkodean Kembali) Pengkodean kembali pada kode konvolusi dapat dilakukan dengan menggunakan dua decision yaitu ”hard” decision dan ”soft” decision. Pengkodean kembali menggunakan hard decision : >> tb=2; >> pesan_terima=vitdec(codeword,t,tb,'trunc','hard') pesan_terima = 1 0 1 1 0 1 0 0 >> pesan_terima' ans = 1 0 1 1 0 1 0 0 >> cek=[pesan_kirim' pesan_terima'] cek = 1 1 0 0 1 1 1 1 0 0 1 1 0 0 0 0
Pengkodean kembali pesan yang dikirim menjadi pesan terima. tidak terjadi kesalahan pada bit-bitnya. Atau dikatakan bit error = 0, ini bisa dilihat pada hasil cek atau dapat juga dilakukan pengecekan langsung sebagai berikut : >> [jml_biterr,ratio_bitter] = biterr(pesan_terima,pesan_kirim) jml_biterr = 0 ratio_bitter = 0
30
Tampilkan bersama-sama antara pesan yang dikirim, codeword dan pesan yang diterima dalam satu figure, seperti pada gambar dibawah ini.
Atau :
B. Tugas : 1. Ulangi langkah 3, dengan mengubah-ubah nilai tb = 4, 7, 9 dan 10 2. Jelaskan secara teoritis, apa yang terjadi dengan perubahan nilai tb ?
4.
Kemampuan koreksi kesalahan (Error Control Coding) Untuk mengamati kemampuan koreksi kesalahan kode konvolusi, maka dapat ditambahkan error secara random sebagai berikut : 31
>> pesan_kirim = [1 0 1 1 0 1 0 0]; >> t=poly2trellis(3,[6 7]); %ditulis dalam oktal >>codeword=convenc (pesan_kirim,t); >>N=length(codeword); >>var=0.4; %varian noise >>noise=var*randn(N,1);%noise random yang dibangkitkan >>ncoden =xor(codeword,noise); >>noisecode=fix(ncoden); >>tb=2; >>Pesan_terima_bernoise = vitdec(noisecode,t,tb,'trunc','hard'); Pesan_terima_bernoise ans = 1 0 1 1 0 1 0 0
>> [jml_biterr,ratio_bitter] = biterr(pesan_terima_bernoise,pesan_kirim) jml_bitter = 0 ratio_bitter = 0 Tampilkan gambar codeword, codeword dengan noise unquantisasi dan codeword dengan noise quantisasi, seperti berikut : Setelah dilakukan encoding tampilkan pesan yang dikirim dan pesan terima setelah diberi error, amati secara teliti apakah pesan yang dikirim sama dengan pesan terima ? Jelaskan apa yang terjadi pada kode convolusional ?
32
C. Tugas :
Listing Program pesan_kirim = [1 0 1 1 0 1 0 0]; pesan_kirim = randint(1,10,[0 1]); t=poly2trellis(3,[6 7]); %ditulis dalam oktal codeword = convenc(pesan_kirim,t); % hasil pengkodean tb=2; pesan_terima=vitdec(codeword,t,tb,'trunc','hard'); cek=[pesan_kirim' pesan_terima']; [jml_biterr,ratio_bitter] = biterr(pesan_terima,pesan_kirim); N=length(codeword); noise=zeros(N,1); noise([3,5],1)=1; ncoden =xor(codeword',noise); noisecode=fix(ncoden); tb=2; pesan_terima_bernoise = vitdec(noisecode,t,tb,'trunc','hard'); [jml_biterr,ratio_bitter] = biterr(pesan_terima_bernoise,pesan_kirim'); figure(1) subplot(3,1,1) stem(pesan_kirim,'b') title('Pesan Yang Dikirim') subplot(3,1,2) stem(codeword,'m') ylabel('Codeword Tanpa Error') subplot(3,1,3) stem(pesan_terima,'r') xlabel('Pesan Yang Diterima') figure(2) subplot(3,1,1) stem(pesan_kirim,'b') title('Pesan Yang Dikirim') subplot(3,1,2) stem(noisecode,'m') ylabel('Codeword Dengan 1 Bit Error') subplot(3,1,3) stem(pesan_terima_bernoise,'r') xlabel('Pesan Yang Diterima')
33
Hasil Output
34
