PENGKODE VITEITBI PADA RANGKAIAN KOMUNIKASI DIGITAI,
Oleh: Siswo Wardoyo Dosen Fakultas Teknik Elektro Universitas Tidar Magelang
ABSTRACT Algoritma viterbi is usually called as 4,namic-progr.amrtirtgalgctrithm. Algorilma viterbi is ttsed to make a correction on the set oJ'digital contntunication, in this pupe, it is usetJ l6 heet codes. Thefailure is on the 5 th beet and it v,itl be coded ttsing trellis itr thefst uplo 8 th step. [n the last step, trellis process is creoted. II'e can choose which part that has the lo,,uest metric total. The orders of input beet are collected u,ith some parts. Thej, gan be clarified by adjusting the order of input code.
Key Word
:
Viterbi Codes, Trellis, Hard and soft der.ision.
I.
PENDAHULUAN Tahun 1967 Viterbi memperkenalkan suatu prosedur pengkodean untuk kode-kode konvolusional yang kemudian menunjukkan suatu penyediaan kemungkinan pengkodean maksimum pada kode--kode konvolusi. Algoritma Viterbi atau Pengdekode Viterbi, biasa juga disebut sebagai dynamic Programming Algorithm. Algoritma Viterbi mempunyai pemahaman sebagai koreksi kesalahan untuk rangkaian komunikasi digital, yakni mencari hubungan aplikasi yang luas dalam Pengdekodean terhadap kode konvolusi, digunakan pada CDMA, GSM
t2s
Pengkodc lTterhi Puda Rongkaian Komunikasi Digitol (Siswo ll'ardoyo)
seluler digital, modem dial-HP satelit, komunikasi deep space, dan 802.11 wireless LAN. Saat ini umum juga digunakan pada pengenalan tutur kata (speech recognition). keyword sofnng, linguistik komputasi, dan bioinformatika.
II.
Ide Dasar Pengdekode
Diasumsikan ada 3 bits yang dikirinr melalui % kecepatan code (code rate). Kita akan menerima 6 buah bits (tidak memperhatikan
fl
ush bits).
Kita tahu dari proses pengkodean. bahwa bit tersebut dipetakan secara unik. Jadi 3 bit inputan akan meniadi 5 bit keluaran yang unik. Akan tetapi. karena trdanva error kita dapat menerirna semua kombinasi yang mungkin dari 6 bit tersebut.
Pennutasi dari 3 input bit rnenghasilkan 8 kemungkinan runtun iqpLrt seperti 1'ang tercantutn dalarn tabel l. Sctiap runtun mempunYai pemetaan 6 bit output code 1'ang unik. I'{al ini membentuk suatu set dari rllntun yang benarldiiiinkan dan merupakan tugas Cari Pengdekode untuk menentukan yang mana.
Tabel I . Bit Agreement sebagai metricirl Valid Cqde
Received
Bit
Sequence
Sequence
Agreement
000
000000
111100
2
001
00001
1
111100
010
001 1 11
l l 1100
0 ')
011
001 100
I 1 1100
4
100
1l1110
1llt00
5
Input
r26
Pengkode lrtlerbi Puda Rangkaian Komunikssi Digital (Siswo llardoyo)
Bual nrlilr node krnr
Garnbar l.Diagram alir Pengdekodean kode Kon','olusi Iil
: 001 I 100001 1001 I I Contoh kasus
lr4arilah
kita
metrdekcrde clata inpLrl
dengan menggunakan
Viterbi:
:
Pengdekode
0 menr-tju ke level I Proses Pada level jah"rr arval dimulai pada kondisi bahwa dimulaidengan asumsi 0, terlihat terdapat 2 jalur kemungkinan yang tersedia yaitu ke state 00 dan 10. Kedua nilai tadi akan disimpan untuk proses trellis selanjutnl'a (lihat gambar 2).
Langkah
I-
State 00
.
State
01 o
Stete
10
.0
UU
'1,1
6
o
State I I
128
Iitl. l0
No. 2, I5 Septenther 200t
: I2j-lt2
Gambar 2. Langkah a\\'al pengdekodean dengan menghitlurg error rnetric
Langkah 2 - Pada leve l: l. pengdekode bercabang rnenjacli 4 untuk langkah selanjutnya. masing-masing 2 yung ,o.rupukon perluasan dari cabang pada langkah pertama. Saat simboiyung diterima adalah ,? = I 1, maka disini akan dibandingkan dengan masihg-masing jalur cabang yang diperbolehkan, yaitu untuk t]?tl S, ke'Soo, S.ook. S,o, S,oke So,= 0, dan S,nk€ S,,, maka nilar error matnc untrk masing-masing cabdng yaiig baru adalah Soo'= 2, So, :3, S,n:0, dan S,, :3. Jalur dengan nilai metnc I'ang terkecil (keadaan S,n) sebagai pemenangnya dan nilai metric yang besar untuk caUang-cabang lain Iintasannya tidak diambil. (lihat garnbar 3)
il;i,
EError Mctric =
0+2='
State 00
State 01
2+ I =
state 10
0+0= ot.
Statell ! Di penerima
2+l=
" : 00
It
Gambar 3. Langkah 2 pengdekodean dengan men-uhitr.rng error rnetric
Langkah 3 - Pada level:2. pengdekode bercabang menjadi 8 untuk langkah selanjutnya, masing-masing 2 yang merupakan perluasan dari cabang pada langkah kedua. Saat simbol yang diterirna adalah r3 : I l. sedangkan data yang t29
Pengkode I'iterhi Pada Rangkaian Komunikusi Digital (Siswo ll'uttlol'o)
adalah 10. rnaka Pengdekode akan melakukan koreksi terhadap masukkan yang simbol dan sekaligus seharusnya
memperbaikinya dengan cara akan membandingkan dengan masing-masing .lalur cabang yang diperbolehkan. yaitu untuk state S,,,, ke S,,0. Souke S,o, So, ka Suo, Su, ke S,o. S,oke So,:0. S,ok. S,, dan S,,k. S,, (lihat gambar 4). Lcvcl
:
2+3;3+0i
Strta Ol
O+l;
ftli
Strta lO
2+Oi
t+Zi :
Shte 11 Di
Gambar
lEror Mclric =
strte 00
o+l;3+l;
o
Pqsima :
t
l
l
oo
4. Langkah 3.
Pengdekodean dengan menghitung
...ot -btri.
4-
Pada level:3, Pengdekode bercabang menjadi 8 untuk langkah selanjutnya. masing-masing 2 yang mempakan perluasan dari cabang pada langkah ketiga' Saat simbol yang diterima adalah 14 : 00. rnaka Pengdekode akan membandingkan dengan masing-masing jalur cabang yang diperbolehkan, yaitu untuk state Sn., ke S,,,,. S,,,,k. S,,,. S,,, ka S,,,,, S kcS S keS =0,S keS danS keS . Sehingganilai .iJo, #otri'. untJik n,uri$g--i!ing .Jf,ung'iung baru utrtttk Ievel ini akan mempunyai dua nilai, tetapi nilai error yang paling terkecil sebagai pemenangnya (lihat gambar 5).
Langkah
130
lbl Lcwl ; StC.
30 No. 2, I5 Septenther 2008: 125-!12
0
O0
Sttc 0l " Stac l0
o
Sttr ll
o
Di
3-]:1+0:
0t
Pcrcdmr:
l0
\/
00
o
2*1;1+l;
/tt
ll
CO
l0 111 r
Gambar 5. Langkah 4. Pengdekodean dengan menghitung error metiic
5-
Langkah
Pada level:4, Pengdekode bercabang
menjadi 8 untuk langkah selanjutnya, masing-masing 2 yang merupakan perluasan dari cabang pada langkah ketiga. Saat simbol yang diterima adalah 15 = 01. maka Pengdekode akan membhndingkan dengan masing-masing jalur cabang yang diperbolehkan, yaitu untuk state Sno ke S,,r, Snu k. S Su k. Suu, ,n, 'gambar , S ke S S ke S : 0, S,o ke S,, dan S,, ke"S,, (liliat
6j]
ro' ro
or
L6tl: 0
I
2
3
4
j Etrorlv*Eic
Shtc
l0
=
-+--+_# lrlt00m
Shtc 01
Shtc 10 01
Shtcll
c
Dkncnnn:
00 ll
llm0r
Gambar 6. Langkah 5 Pengdekodean dengan rnenghitung error
r31
Pengkode
metnc
Iilerhi Pudu Rangkaian Kotwtnikasi Digitol (Siswo ll'urtlol'o)
6-
Pada level:S. Pengdekode bercabang menjacli 8 untuk langkah selanjutn.va. nlasing-masing 2 yang merupakan perluasan dari cabang pada langkah ketiga. Saat simbol yang diterima adalah 16 = 00. tnaka Pengdekode akan 'membandingkan dengan masing-masing jalur cabang yang diperbolehkan, yaitu untuk state Soo ke S,,0, S*kt S,o' So,kt loo, S^ = 0. S ke S dan S,,k. S,, (lihat gambar S . S.^ke S '--'10, "01 ke -10 ' ll
Langkah
l0
0l
7). Lnrl:
0
EnctL{eEic = 3+ li ?+li .
3{: l+l
Strte 01
strte
10
Sht{
11
D?enerima:
CC ll
:i
C0
0i
Gambar 7. Langkah 6 Pengdekodean dengan menghitung error metric
Langkah 7
-
Pada level=6- Pengdekode bercabang meniacli 8 untuk langkah selanjutnya. nlasing-nlasing 2 yang merupakan perluasan dari cabang pada langkah ketiga' Saat sirnbol yang diterirna adalah r7 : 01. rnaka Pengdekode akan membandingkan dengan tnasing-masing jalur cabang yang diperbolehkan, yaitu r:ntuk state S,,,, ke S,,u. Sun ke S,n' Su, kt luu' (lihat gambar Su-ke S,u, S,oke Su,:0, S,,,ke S,, dan Slrke S,, 8).
132
lbl. 30 No. 2,
Si€ll
,
I5
Septemher 2008
: I 2S-112
"
DPmciur
00
rr r$ or ol
to
ol
Gambar 8. Langkah 7 Pengdekodean dengan menghitung error
metric
Langkah 8
- Pada level=7, Pengdekode bercabang menjadi 8 untuk langkah selanjutnya, masing-masing 2 yang merupakan periuasan dari cabang pada langkah ketiga. Saat simbol yang diterima adalah rS : 11. maka pengdekode akan membandingkan dengan masing-masing .ialur cabang yang diperbolehkan, yaitu untnk state S,,,, k€ S,,u, S^^ ke S,,,, S,,, ke S (xr o!"mtr'u', S,,, k. S,.. S,"ke S^,: 0. S iilot ttiilo. 0l l0' ^ke S.. dan S. l0 0l t0
-"'t.'3
e).
ll
ll
I
i;;'#
-L"rl stb
1
Gambar 9. Langkah 8 Pengdekodean dengan menghitung error
metric r33
Pengkode
lllerhi
Hasil perhitungan
Puda Rangkaian Konnnikusi Digital (Siswo llurdoyo)
error
lrletric Llnttlk selnua
langkah
Pengdekodean dapat dilihat pada tabel 2. sebagai berikut Tabel 2. Akurnulasi
t-
0
Stdc 00,
U
Std.
Olz
Std.
102
St*c
112
1
o
2
error metric untuk senllla level 3
4
6
6
7
8
2
3
3
3
3
4
1
3
1
2
2
3
1
4
o
2
1
3
3
4
3
3
I
2
1
3
4
2
Untuk memp€roleh data yang dikirimkan yaitu dengan cara melihat ke Tabel3. Transisi Keadaan (state) dan Tabel 4. Simbol Keluaran, sebagai berikut : Tabel 3. T'ransisi Keadaan (State) ,Stde eelsnJutnya. Jlka
Tabel
{. Sirnbol Slmtrol
.Stdte awal
oo
Input : oo
keluaran keluarann;ra,
O:
Input: 11
o1
t1
lo
10
ol
11
o1
10
t34
1
lbl. 30
No. 2, I 5 Septcnther 2008
: I )5-t12
[)engan demikian hasil akhir dari Pengdekode Vitcrbi dapar dilihat pada gambar 10. Lcvel
1t
0
m
)cm ll
lEbol . Irbu
o
ItsEll
o
il
ll
"
0l t0
Odprt
l0
Pnglodc. c!
00
0t
P@imr:
00
0t
00
0l
I
I
Di
g6t:
00
ocp0r
P*gd!ko& :00 si6tol
Ocpt:
0
Gambar 10. Hasil akhir dari Pengdekode Viterbi
ry.
Pengdekode Viterbi dengan Soft Decision Pengdekode Viterbi ditempatkan setelah demodulator dan de'cision statistik. Jika kita tinjau dari sisi siny'al maka dapat digambarkan seperti pada gambar 12. t
Etc
r
--ttRIrsKl'(0
l./o
rl coovolutioral ocodg L &n hns
modulua
0,rf,yr codc bits
,
-J
r *,,-1*, ", dsL bils
Vildti
deoda '
.-
*''*
'l
l;
[l]o' '
strriJth
irl"
AW(iN u(r)
(r)
x'{ ool cmchtor
Gambar I l. Diagram blok Pengdekode Viterhi dengan soli decision trl
r35
Pengkode
literhi
Pada Rangkaian
Konunikasi Digitol (Siswo llrurdoyo)
(u)
(c)
Gambar'12. a) Dr-ra sinyal menunjLrkkan bit I dan 0. b) Noise dari S,rN = 2 menyebar kesinyal. c) Noise dari S,N :4 menyebar yang mengalirkan energi dari satu daerah keputusan ke yang lainnva. 12l Seperti pada gambar 12 (a) diatas. Spektrum dari I sinl'al biasa rner,vakili 0 dan I bit. ketika dirusak oleh noise maka akan sulit untuk mc'mbuat proses keputusan. Gambar ll. b. c. menunjukkan dua kasus berbeda untuk SN berbeda. .lika kita bandingkan gambar c dengan b. bila derau lang ditambahkan kecil. maka variance-n1'a juga rendah (karena dava derau = variancc). kemudian tersebar rneniadi lebih kecil. Pada gan-rbar l2(c). Area I menunlukkan bila energi tergantung pada sinyal Lrntuk I yang sudah berada di daerah
l3(i
]bL 30 No. 2, l 5 Septet rhu 2008 : 1 25-t42
keputusan yang berlawanan dan sebab itu kekeliruan mengantar
untuk menrbaca kode dari bit seperti 0 dan area2 yang mana energi dari bit 0 telah berada didalam daerah yan diinginkan. Bila I dikirim, kemungkinan akan dibaca sebagai 0 adalah
Pel:\u,7, L -
t#l
(1)
.,12o
Dima,na: u-l: decisidn threshold voltage, dalam kasus iniyang dipakai adalah 0 o: Variance dari noise atau daya. Kita dapat menulis kembali persamaan tersebut sebagai sebuah fungsi SA{ :
Pel:|",fr,^F
,
(2)
lni merupakan persamaan laju kesalahan bit (bit error
rate). Tetapi sekarang apabila kita rnelakukan hal tersebut; dan hanya
lnempunyai 2 daerah keputusan, maka kita dapat membagi area menjadi 4 bagian seperti yang dituniukkan pada gambar 13 di bau,ah ini : Re:er'.'eC
'.
ilr.i qe
r
Gambar 13. Kurva pembagian 2 daerah keputusan menjadi 4 bagian t:l
t37
Pengkode l,iterhi Putlo Rangkaian Komunikasi Digital (Siswo ll'urdoyo)
Dari pernbagian daerah seperti yang ditunjukkan pada gambar l3 diatas, didapat empat daerah seperti di bawah ini: - Daerah 1 : bila menerima tegangan lebih besar dari 0.8 v - Daerah 2: blla menerima tegangan lebih besar dari 0 v tapi lebih kecil dari 0.8 v : Daerah 3 : bila menerima tegangan lebih besar dari -0.8 v tapi lebih kecil dari 0 v - Daerah 4 : bila menerima tegangan lebih kecil dari -0'8 v
Fungsi Q memberikan area di bagian bawah yang didefinisikan dengan jarak dari rcta-rata ke nilai yang lain seperti yang terlihat pada gambar 14' Maka Q(2) untuk suatu rata-rata2 isyarat akan memberikan kemungkinan nilai 4 atau lebih.
'Aree = a(A-vt/s)) For A =1 arxl vt = .8
o = l, tfrc Arca = A(.2)
Ovr
A
c
v
Gambar 14. Kurva Fr"rngsi Q t:l
Dari gambar 16. diasumsjkan nilai vt : 0'8 (ini standar jurnlah untuk 4-level) tapi ini dapat ber,lumlah berapa sa.ia. lvlaka persamaan-persamaann),a dapat ditulis - Pel (probabilitas untuk I .iika tegangan penerima berada dalam daerah l) : I -Q(A- vt /o) - Pe4 (probabilitas ttntuk I jika tegangan penerima berada dalarn daerah 4) : Q(2(A+vt)/o) :
138
200t
: I l j-l j2
- I'e2 (probabilitas Llntuk r jika tcganga' pencrirna dalam daerali 2): t- pel-e(A/o)
heracra
lbl.
-
.10
,\'o.
). l5 .lcptenther
Pe3 (probabilitas untuk r iika tegangan penerirna berada dalam daerah l) : l- pel- pe2
-pe:l
Hasil perl'ritungan untuk S,N : l, ternyata diasumsikan nilai v1 : 0.8A dan A : 1.0. Kita juga menganggap kedua bit 0 dan I adalah equiprobable. Jadi a'ea dari daerah 4 atatr Pe4 setara dengan Q(l.8) yang dapat dilihat dari tabel fungsi Q. Dapat pula probabilitas kondisional dihitung dengan menggunakan cara grafis seperti dituniukkan gambar lf di bawah ini
to....
Gambar 15. Probabilitas kondisional dari pcnrbacaan kode 0 atau I tergantung besarnla tegangan y,ang cliterima. ketika tegangarr diukLrr ke dalarn .{ le,",cl i s. l.trl Sofi-c'lecisi'n dapat rncnrpcrbaiki kepekaan dari pembacaan kode-kode metric clan rnemperbaiki kinerja sebanyak 3 dB dalam kasus 8-le'e-l soft decisirn. {intuk rnenghitung soft decision metric dibuat tabel prol:abiritas dari ketrclaan di atas.
l3e
Penllkode
litarbi Putlu Rangkaian Konruniku.si Digitul
(.9iswo ll'urdoyo)
Tabel 5. Probalitas keadaanlrj Seut I
\'-l tl -l
(i
.6
"'l 6t)
I
ll
t5
r)l
Ambil natlrral log dari tiap diatas dan dinormalisasi sehingga salah satu dari nilainya adalah 0. Setelah beberapa nomer dimanipulasi didapatkan hasil seperti pada tabel 6. Tabel 6. Normalisasi dari Probabilitas keadaan
Sent
li
r'-l
r'_i
r'l
0
I
-+
-J
I
1(t
t2l
\'1
I{) t)
Pengdekode metnandang metric ini untuk tegattgan diiri tabel di atas dengan urembuat penghitungan sebagiii berikut : Diasumsikan pasangan legangan (v3. v2) diterir-na. floderiord yang diperbolehkan adalah 01, 10. maka:
,\4elrit'ttntuk0l : Metric ttntuk l0--
p(0,:l* p(t v2): -l * -J = -8 p(l \'3)- p(0iv2) == -l ' -l -. -2
Dapat dikatakan hanya dengan melihat
0l
sungguh lebih
banl,ak daripada I 0. Ketika metric ini bertambah, akan semakin terlihat perbedaan dan akan tnembantu hasil penrbacaan kode
140
lbl. 30,\o. 2, I5,Septcmher
V.
20()8
:
125-112
Log-likelyhoodltatio
Satu metric )'ang pe nting untuk diketahui disebut clengan log-likelihoocl nretric. lv{etric ini kemudian dimasukkan ke dalam perhitungan Llntuk mencari probabilitas kanal error dan didefinisikan sebagai . Metric untuk agreement: :
LoErc2(l-p)
, Log,o2 Metric unftik disagreement
(3)
:
Log,o2Qt)
LogrrZ
.
(4)
untuk p : 0.1. maka. metric untuk agreement : -20, sedangkan r'natric tintuk disagreement: - l . Jadi jika data bit yang diterima adalah 01 dan codervord adalah 00. ntaka total metric-nya adalah -20 + -l == -21 dan keseluruhan metric untuk agreement rneniadi -40.
VI. KESIMPT]LAN l. Diagrarn trellis nrerupakan .jantr-rng dari
t "
2. 3.
pendekocle
Viterbi Prinsip dasar algoiitma \,-iterbi adalah rnemilih lintasan yang menlpunl,ai node minimurn. Pendekode Viterbi tnempunvai 2 metode keputusan. r aitu hard decision dan soft decision
4. Itasio
log-likelyhood dapat memperbaiki
pembacaan kode 1'ang akan didekodekan
141
kiner.ja
Pengkode l'iterhi Pnda Rangkoion Konunikusi Digital (Siswo llardoyo)
DAI..TATT PUSTAKA [Jreen, Dan, et a1, Vitcrlri Perrgdekode, I:l.SI tle,sign Projecl Chtn'an Lunglcttr, Tutorial 12 : Coding and Pengdekodean rvith Convolutional Codes, Signul Prot'e.ssing & SimLtlation
'
h'ev,sletler
Chip Fleming, " A Tutorial on Convolutional Lloding rvith Viterbi Pengdekode", (Nov 200I), http://horne.netcom. i/ t u t o r i a l. h t ml Matthev' Vhlenti, Convolutional Codes: Pengdekodean and Performance Analysis. April 21, 2003 Paniailan, Sihar P, Sistem Pengkodean, Fakttltas Tbknik Jttrusan Teknik Elektro [.Jniversilas Sumalera Utara Rorabaugll, C. Britton, Error Coding Cookbook : Practical C/C++ Routines and Recipes fbr Error Detection and Correction. McGrav'-Hill, I 996 co
nz/ -c h'ilt,f/
WIer b
t42
