INFORMATICA 2/1979 
KONVOLUCIJSKI 
KODIRNI IN DEKODIRN 
POSTOPEK PRI 
Ml KRORACUNALNIKU 
ISKRA DATA 1680 
M.KAPUS 
G. DEVIDE 
B. HORVAT 
UDK: 681.325.3 VISOKA TEHNIŠKA ŠOLA MARIBOR 
POVZETEK - Brez dvoma je eden najmodernejših in atraktivnih dekodirnih postopkov v prenašanju in zavarovanju digital­
ne informacije Viterbijev algoritem. V naslednjem desetletju pričakujemo v komunikaciji podatkov ta algoritem realizi­
ran v integrirani obliki s pomočjo materialne opreme. Zaradi visoke redundance se tak postopek koristi predvsem pri 
prenosu podatkov FEC brez povratnega komunikacijskega kanala. Pri komuniciranju med procesorji in v želji po čim več­
ji zanesljivosti smo koristili ta kodni in dekodni postopek in ga realizirali s pomočjo programske opreme. 
Kodirnik je preprost pomikalni register povratno povezan s seštevalniki po m = 2. Dekodlranje je bolj zapleteno in je 
bistvo članka. Simulirali smo celoten prenosni sistem za ocenitev prenosa. Komunikacijski kanal smo ponazorili kot nor­
malno porazdelitev z generatorjem naključnih števil. Rezultati so obetavni in kažejo na veliko zanesljivost prenosa kljub 
množici motenj, v kanalu. 
CONVOLUTIONAL CODINGAND DECODING PROCEDURE BY MICROCOMPUTER ISKRA DATA 1680 - Without doubt is in 
communication the Viterbi algorithm one of the up to date decoding procedure. In next decade we expect that the proce­
dure be realized in integrated form on the chip. The procedure take more use in FEC transmission and noed for deplexing 
the same number Information as control bits. By communication between processors to achieve more transmission reli-
ability we use this coding and decoding procedures with softv/are suport. 
The coder is simple shift register feedback conected with exlcusive or elements. The decoding procedure is more complex 
and the matheniatical structure which we take is explained in this article. We simulate the communication channel with 
a random number generator, to valuethe transmission system. The decoding procedure has shown succesfuU transmi­
ssion with a great degree of reliability on channel errors. 
1. Uvod 
Ce želimo dvigniti zanesljivost prenaša nih sporočil v di­
gitalnih sistemih, pri katerih ni povratnega kanala, se 
odločamo najpogosteje za popravljanje napak na spre­
jemni strani. Tak način prenosa zahteva dokajšno redun­
danco prenesenega sporočila v obliki kontrolnih bitov, ki 
jih privesimo informacijskim bitom. Ravno tako moramo 
računati s povečanim procesorskim časom in povečano 
pomnilniško kapaciteto. Želeli smo ustvariti poseben 
minimalni procesorski modul, ki bi bil kot komunikacij­
ski procesor priključen na večji računalniški sistem in 
bi tako zagotavljal povečano zanesljivost vsem onim 
vhodno/izhodnim vodilom, kjer ni možnosti za povraten 
kanal, torej za prenos ARQ sistema. Takšni komunika­
cijski kanali so pogosto vsi prenosi podatkov na pomnil-
niške medije in vse prenosne poti, kjer pogosto ponav­
ljanje informacijskih paketov ne bi zavrlo prepustnost. 
informacijskega pretoka. Razumljivo Je, da komunikacij­
ska pot mora imeti določeno kvaliteto in nenavadne nepre-
velike aditivne napake kanala nam dekodlrni proces izlo­
či. Sam kodirni postopek je zelo preprost in ne zahteva 
procesorskega časa in ga najpreprosteje rešimo v ma­
terialni opremi. Dekodirni proces je mnogo bolj zamotan 
In podana Je njegova programska rešitev. Izbrali smo 
minimalno konfiguracijo registrov in si s tem zagotovili 
manjiii čas procesiranja in manjšo fMmnIlniško kapacite­
to. 
2. Opis kodirnega in dekodirnega algoritma 
Pri sinhronem prenosu sporočil nimamo povratne kontro­
le, ali Je bil prenos pravilen. ZatS moramo uporabiti na­
čine kodiranja, kjer bo šifra čim manj občutljiva na mot­
nje. Eden takih načinov Je konvolucijsko kodiranje. Odlo­
čili smo se za kodirnik z delovno besedo dolžine treh 
bitov. 
Km 
w 
informacijski biti 
Informacijske bite vodimo skozi pomikalni register in 
vsakokrat izračunamo .0] in 03. Namesto sekvence in­
formacijskih bitov oddajamo sekvenco urejenih parov 
(Ql, 02). Ta je dvakrat daljša od prvotne in implicitno 
vsebuje razen osnovne informacije še odnose med za]:)o-
rednimi tremi biti. Zaradi tega Je prenos zanesljivejši. 
Ker ne vemo, koliko se je informacija pri prenosu po­
kvarila, jo lahko dekodiramo le z verjetnostnim računom. 
Seveda ni mogoče zajeti vseh motenj, ki se lahko pojavi­
jo, saj bi potrebovali ogromen spomin. Zato zajamemo 
le najverjetnejše, to Je minimalne motnje. Rezultat teh 
motenj je zaporedje, ki se kar najmanj razlikuje od odda­
ne sekvence. 
Na tem principu sloni Viterbijev algoritem. 
Izmed informacijskih bitov, ki so trenutno v postopku ko­
diranja, bosta 2. in 3. bit skupaj z naslednjim informa­
cijskim bitom I določala vrednost Qi, Q2 v naslednjem 
koraku. Označimo urejeni par 2. in 3. bita z 
X. \ X. a = 00, b = 01, C = 10, d = 11 

48 
S sprejemom novo<ja inf. bita dobimo par xj,. |. IVi tem 
so možni prehodi, kot jili kaže tabela 1. 
'i.l 
i+l 
Urejena trojica (KJ, 1J+I) določa par (Qi, Q2)i.h| , ^. • '''^ 
se pri prenosu moti in dejansko sprejmemo par 
(Q| , Q2)i+I , '^' ^® "'' '^''"'^ ^^1 ' ^2^+1, Xj i-azlikujo na 
"li+l,Xi "^"S"''- '"i+l,Xi "''-^ 
Definirajmo funkcijo poti P. , 
11-1 ,XJ+1 
i+l, X 
i+l 
X. a.b 
1 
Xj C,d 
X. , 
1+1 
a 
b 
C 
d 
1 
Vi 
0 
1 
0 
1 
"i 
a 
C 
a 
C 
b 
d 
b 
d 
1' 2 1+1,x. 
' 1 
00 
11 
11 
00 
10 
01 
01 
10 
1^. , 
0 
1 
0 
1 
0 
1 
0 
1 
^^'S^+I, 
00 01 10 11 
'"1^1,X, 
0 
2 
2 
0 
1 
1 
1 
1 
1 
1 
1 
1 
2 
0 
0 
2 
1 
1 
1 
1 
0 
2 
2 
0 
2 
0 
0 
2 
1 
1 
1 
1 
Tabela 1 
Sprejeli smo sekvenco Q parov (Q,, O^). i j = li*"»i' 
i . 1 2 J 
Iz nje lahko sklepamo, kakšna je bila sekvenca inf. bitov 
Sj. Sklepamo ločeno za primere, ko se Sj končuje z a, b, 
C oziroma d. Tako dobimo štiri sekvence Si xi» 
xj a,b,c,d . Vsaka sekvenca Sj ^, nam da sekvenco 
Qi X,» ki se od dejansko sprejete sekvence Qj razlikuje 
na '^i,Xi mestih. 
i.x. 
Q. -Q. 
I 1 ,x 
i,x, 
M. 
l.x 
V naslednjem koraku sprejmemo par (Qi, 02)1 + 1 in za 
vsako končnico xi+| spot^ppiščenio najverjetnejšo vhodno 
sekvenco Sj+i ^i + i • Nove sekvence so seveda nastale z 
dodajanjem naslednjega informacijskega bita starim vhod­
nim sekvencam. 
i+l,X^^j i,Xj Xj^^ 
Odnos med x, , , x., 1 že poznamo iz tabele 1. 
1+1' 1' X. , ^ 
1+1 
i+l,x. °° ^i+l,x. , ' S+I,x. "S,x,' 
' i+l ' 1+1 ' i+l '. i 
<^PS)I+1.X. 
'^i+r'^i+i.x 
Ker sta za vsak x možna dva x., izberemo verjetnej­
šega, to je tistega, kjer jo M. manjša. 
' i+l 
X.: 
1 
M (x.) 
Izbrani x. določa funkcijo (xiti: 
i+1 .X 
= I 
i+l 
i+l,x. ,(x.) 
'1+1 1 
Izmed štirih sekvenc S. 
i^•^ ,x 
vzamemo kot pravilno 
tisto, kjer je 
M. 
i+l 
i+l i+l .X 
i+1 
(x. J 
1+1 
Ker vse sekvence Sj ^. težijo k isti najverjetnejši sekven-
ci S, se začenjajo deloma ujemati v bitili, ki so nastali 
prej in so šli žx) večkrat skozi (lostopek preverjanja ver­
jetnosti. S poskusi so ugotovili, da jo to dovolj pogosto 
že na mestu (i - 0.4), strožjo na mesti (i - 5.1)) , kjer 
je dolžina delovne besede kodirnikn, v našem primeru je 
D = 3. Bolov sekvenc Si^x:» ki so skupni, ni več mogoče 
izboljšati, zato predstavljajo rezultat dekodiranja. Torej 
' lahko predstavimo sekvenco v registrih z dolžino 4.13, 
bit, ki vsakokrat izpade iz registra, pa je rezultat. Pro­
gram smo realizirali na MC G800, ki ima 8-bltne celice, 
zato smo uporabili 16-bitne registre. 
Za SQ JJ. lahko izberemo poljubno zaporedje, prav tako 
za Mo^xo poljubne vrednosti, saj bodo te zanemarljive 
napram vsoti m 
so,xo=o^^ Mo,xo ="°-
višjih redov. Mi smo izbrali 
Za naslednji korak so pomembne le relativne razlike med 
Ml,xi ' ^^*° vsakokrat odštejemo minimalno. 
M. M. 
i,x 
M (x.) min, 
l,Xj 1 
Pri tem se pokaže, da so vse možne kombinacije nasled­
nje: 
Ma 
Mb 
Me 
Md 
M O 1 2 3 4 5 6 7 8 9 10 n 12 13 14 15 16 17 B 19 2) 21 22 
0 10 0 0 10 0 111 
0 0 10 0 10 10 11 
0 0 0 10 0 1110 1 
00001011110 
0 
0 
1 
2 
D 
0 
2 
1 
1 
2 
0 
0 
2 
1 
0 
0 
0 
2 
1 
1 
2 
0 
1 
1 
1 
1 
0 
2 
1 
1 
2 
0 
0 
1 
2 
2 
1 
0 
2 
2 
2 
2 
0 
1 
2 
2 
1 
0 
Tabela 2 
Ma 02220233 
Mb 20222033 
Vsak niz M . M. . M M, 
Me 
M,. 
22023 302 
22203320 
M 23 24 25 26 27 28 29 39 
a' b' " c' "d 
nadomestimo z njegovo zapo­
redno številko M \ 
M = O, 1, ,30 
Zahteve pri programiranju: 
1. Čim več rezultatov izračunamo vnaprej in jih po po­
trebi le pokličemo iz spomina. 
2. Uporabimo čim več spomina tipa KPROM in čim manj 
• RAM-a. 
Za vsak M izračunamo tabelo prehodov. 
M. 
1 1 
M^ , M P J 
i+1 i+1 i+1 
a O O 
0 1 
1 O 
d 1 1 
= M + m. , = M 
l,Xj 1+1,X. 1+1.x.^, 

49 
Primer za M = 19. 
19 
0 O O. 0222 23 0x00 
1 O 1 0010 3 0010 
2 1 O 0001 4 0001 
2 
1 
0 
0 
1 
0 
1 
0 
1 
1 
0 
0 
0 
Pri starem stanju Mi sprejmemo bita Oj, Q2. Dobimo 
minimalne razdalje - nabor Mj+j z imenom M, s tem da 
smo uporabili optimalne poti iz nabora Pj+i. 
P , = O, če smo šli po zgornji poti, n.pr. a v a . 
= 1, če smo šli po spodnji poti, n.pr. c v a . 
= X, če sta poti enakovredni. 
Mestom Mj^] ^. priredimo naslednje dvojiške vrednosti: 
M. 
1+1 ,a 
11 M. 
i+l,b 
10 M. 01 i M. , ^:00. 
' 1+1,d 
i+1 ,c 
, to je registra, iz J. , je oznaka minimalne M. , 
i+l 1+1,X. , 
i+l 
katerega bomo prebrali rezultat. 
1. Če je Mj^j min. ena sama, pišemo njeno pozicijo v 
stolfjec J.J^= 00. 
2. Če sta Mj+i min. dve, se poziciji vedno razlikujeta 
le po enem bitu. V stolpec J^ vpišemo skupni bit z 
njegsvo pravo vrednostjo, bit se razlikuje, pa ozna­
čimo z X.J = ob. 
3. Če so Mj^i min. tri, dve sosednji vpišemo kot pod 
točko 2, tretjo pa kot pod točko 1. 
4. Če.so Mj+i min. štiri, je Jx = XX in J = 00. 
5. S = 1 natanko v primeru 3, ko se moramo odločati 
med J in Jjj z verjetnostjo p(j), : p(Jx) = 1:2. 
6. S = O pomeni, da smo se odločili za J. To je v pri­
meru 1, po naši prosti izbiri pa tudi v primeru 3, 
ko se S posebej izračuna v llAM-u. 
7. S = 1, če se odločimo za Jjj, to je v primerih 2 in 
4. 
Vsaki kombinaciji M, Qj, Q2 priredimo tri spominske 
celice v EPHOM-u. Naj boR najnižji uporabljeni naslov. 
Potem najdemo na naslovu 
R + 4.M. + (QjQ2) 2 celico T, 
R + 4.M. + (Q^Q^) 2+4.31 celico U, 
H + 4.M. + (QjQ^) 2+8.31 celico V. 
mi 
M. 
i+l 
HE 
ZI3[3E^ 
ilHFZZir^^^ 
Biti vX(Jx) in X(Pj^j) 
T imajo vrednost 1 na 
mestih, kjer v Jj, In 
Pj+l nastopa X, sicer so 
0. 
Prva celica je del naslo-
V va za naslednji cikel. R 
še ni upoštevan, zato je 
možno vse tri bloke spomina prestavljati na poljubne 
naslove brez sprememb. V začetku vsakega cikla se iz­
računa naslov celice T in se dhrani v 1NDEX registru. 
Celice U in V so dosegljive z indeksiranim naslavlja­
njem . 
Za polnjenje ,X bitov potrebujemo psevdogenerator naključ­
nih števil GX, Glede na GX (mod 3) tudi določamo S , 
kadar je S = 1. 
Potrebne celice RAM-a: 
-GX, 
- štirje dvocelični pomikalni registri za S S S S 
a' b' c' d' 
štirje dvocelični S|)omini za spravljanje registrov S, 
ko jih jo treba [iremeSati, 
celica za informacijske bite, ki izpadejo iz registrov, 
celica za S , 
celica za U, ko se izračunajo X-biti, 
celica za dekodirano sekvenco informacijskih bitov. 
iSfirami r»yislrt 
S h INOK 
[pf«6»rioi,aj| 
ilraiunai X-bitt 
£^ g$£l 
qt9d* na / itbtri 
najvtrjttntjii iipadti 
in/ormtKijiki bil in 
ga dodaj d»ltodirani 
i^tivenci 
\lHDX~r\ 
prmvajanjm informacij-
iko smjtvoncm <f alta-
numthčnr zrnkt in izpis 
ČAKAJ 
3. Sklep 
Opisani algoritem smo preizkusili na simuliranem pre­
nosnem sistemu. Prenos sporočil je zanesljiv do dolo­
čene kvalitete kanala. Pri izbiri daljših registrov, bi po 
pričakovanju prenosni sistem Iskazal še boljšo zaneslji­
vost. Koristili smo majhen pomnilniški prostor in raz­
meroma malo procesorskega časa. V vsakem primeru 
bomo ob uix>rabi integriranih vezij s tem dekodirnim al­
goritmom dvignili zanesljivost tudi nad mediji, kjer je 
zanesljivost zelo slaba in hkrati povečali prepustnost ko­
munikacijskega kanala ter bo odpadla potreba po povrat­
ni Uniji. 
LITERATURA 
1) A.J. Viterbi: ISrror Dounds for Convolutional Codes 
and a Asymptotically Optimum Decoding Algorithm; 
IEEE Trans, on Information Theory Nov.1970 
Vol. llT-16 No 6. 
2) J. Justesen: Convolutional Code Construction; 
IEEE Trans, on Information Theory Vol. l.T- - 1973. 
3) B.Horvat in sculcjlavci: Prenos gospodarnih in vernih 
Inforinarij II. Naloga SBK 785/762502, januar 1978. 
4) M 6800 Microprocessor :Programming Manual 
Motorola Inc 1975. '