Teknik Pengkodean – Encoder dan Decoder Kode Konvolusi

LAPORAN TEKNIK PENGKODEAN

ENCODER DAN DECODER KODE KONVOLUSI

Disusun Oleh :

Inggi Rizki Fatryana (1210147002)

Teknik Telekomunikasi - PJJ PENS Akatel

Politeknik Negeri Elektro Surabaya

2014-2015

Teknik Pengkodean – Encoder dan Decoder Kode Konvolusi

Inggi Rizki Fatryana - 1210147002 2

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.



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.

R a t e

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.



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

Dari Sumber

Ke Modulator

… U3 U2 U1

Uj

Pj

....P3U3 P2U2 P1U1

Gambar 1. Encoder Kode Kovolusi Rate ½



kemampuan sebuah kode atau probabilitas kesalahan adalah distance minimum, d*. Distance

minimum d*, adalah nilai terendah dari semua kemungkinan distance.

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 12* ed ,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 :

)2(

2

)1(

2

)2(

1

)1(

1

)2(

0

)1(

0 vvvvvvV

Sedangkan : )2()2()1()1( guvdanguv



Jadi : )11011101()1111()10111(

)10000001()1011()10111(

)2(

)1(

v

v

Sehingga Codeword yang dihasilkan adalah : )11,00,01,01,01,00,01,11(V

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 . . ..

V

V(1)

V(2)

U

Gambar 2. Encoder Kode Konvolusi (2,1,3)



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 simpul a dengan c, serta simpul b dengan d,

maka akan diperoleh diagram Trellis seperti dalam gambar 4.

Gambar 3. Diagram Tree Kode Rate ½

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

00 00 00 00

10 10 10

11 11 11 11

01 01 01

10

10

01

11

1 00

10

01

11

00

10

01

11

1 00

10

01

11

00

10

01

a

11

00

b

10

01

c

11

00

d

01

11

00

11

00

1

0

Root



putus-putus. Sebagai contoh, untuk data input 1101…, garis-garis 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 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)

>> 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 : rate yang digunakan ½ ,

parameter encoder (2,1,2).

>> 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.




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')

Atau :

>> stem(codeword);

>> ylabel('Amplitudo Codeword');

>> xlabel('Jumlah Bit Codeword');

>> title('Bit Hasil Pengkodean')



A. Tugas :

1. 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')

V

V(1)

V(2)

U




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

Tampilkan bersama-sama antara pesan yang dikirim, codeword dan pesan yang diterima

dalam satu figure, seperti pada gambar dibawah ini.



Atau :

4. Kemampuan koreksi kesalahan (Error Control Coding)

Untuk mengamati kemampuan koreksi kesalahan kode konvolusi, maka dapat ditambahkan

error secara random sebagai berikut :

>> 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 :



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')



Hasil Output

Teknik Pengkodean – Encoder dan Decoder Kode Konvolusi

Documents