Teoria informacji i kodowanie  Wykład nr 11
1. Kody splotowe - notacja
Kody splotowe zwykle są określane poprzez trzy parametry: (n,k,m)
gdzie:
n  liczba bitów wychodzących
k  liczba bitów wchodzących do dekodera
m  liczba przerzutników  D w rejestrze albo ilość boksów, z których ten rejestr się składa
Wielkość k/n określa klasę kodu i jest miarą efektywności kodu. Zazwyczaj parametry k i n
zawierają się w granicach od 1 do 8, a parametr m od 2 do 10. Klasa kodu zawiera się w
granicach od 1/8 do 7/8, za wyjątkiem aplikacji bardziej zaawansowanych gdzie klasy kodu
są tak niskie jak 1/100 albo nawet stosowany kod wychodzący jest dłuższy.
Często producenci układów kodów splotowych precyzują kod przez inną notacją parametrów
(n,k,L). Wielkość L oznacza ograniczoną długość kodu i jest definiowana jako:
L = k (m-1) , ograniczona długość kodu
Ograniczona długość L reprezentuje liczbę bitów w pamięci kodera wpływających na
generowanie n bitów wyjściowych. Ograniczona długość L jest także odnoszona do dużej
litery K, która może zostać pomylona z małą literą k, a reprezentuje liczbę bitów
wejściowych. W niektórych książkach K jest definiowane jako porównanie z
wyprodukowanymi wielkości k i m.
Często w komercyjnych opracowaniach, kody splotowe są określane przez parametry ( r,K ),
gdzie:
r  klasa kodu k/n
K  jest ograniczoną długością kodu
Jednakże wielkość K ( ograniczona długość kodu) jest przyrównywana do L  1, jak to
zdefiniowano w tym dokumencie. Będziemy jednak używać dla kodów splotowych notacji
(n,k,m) a nie ( r,K).
2. Parametry kodu i struktura kodu splotowego
A
atwo jest narysować koder kodu splotowego korzystając z jego parametrów. Najpierw
rysujemy m boksów reprezentujących m rejestrów pamiętających. Póz
niej rysujemy n
sumatorów modulo-2, które reprezentują n bitów wyjściowych. Teraz należy połączyć
rejestry pamięci z sumatorami generującymi wielomian. Przykład takiego kodera pokazano na
rysunku:
Rys.1. Koder kodu splotowego o parametrach (3,1,3). Zawiera on 3 rejestry pamięci, 1 bit
wejściowy i 3 bity wyjściowe.
1
Teoria informacji i kodowanie  Wykład nr 11
Klasa tego kodu to 1/3. Każdy bit wejściowy jest kodowany jako 3 bity wyjściowe.
Ograniczona długość tego kodu wynosi 2.Są 3 bity wyjściowe wytwarzane przez 3 sumatory
modulo-2 dodające bity znajdujące się w rejestrach pamiętających. Wybór, które bity są
dodawane i wytwarzają bit wyjściowy, jest dokonywany na podstawie wielomianu
generującego g dla tego bitu. Np. pierwszy bit wyjściowy ma wielomian generujący w postaci
(1,1,1). Drugi bit - (0,1,1), a trzeci - (1,0,1). Bity wyjściowe są tylko suma tych trzech bitów.
v1 = mod2(u1 + u0 + u-1)
v2 = mod2(u0 + u-1)
v3 = mod2(u1 + u-1)
Wielomiany te dają kod, który ma unikalną jakość korekcji błędów. Np. kod (3,1,4) może
mieć całkowicie inne własności od innego takiego kodu w zależności od wybranego
wielomianu generującego.
Jak dobieramy wielomiany
Są różne wielomiany możliwe do wyboru dla każdego m szukanego kodu. Wielomiany te nie
generują wszystkich możliwych sekwencji wyjściowych, a mimo to mają dobre własności
wykrywania błędów. W książce Petersona i Weldona zawarte są kompletne listy tych
wielomianów. Na liście tej wyszukano  dobre wielomiany i używa się ich do różnych
symulacji komputerowych. Lista tych dobrych wielomianów dla kodów o klasie � jest
przedstawiona poniżej:
Tab.1 Wielomiany generujące dla kodów o (szybkości) klasie 1/2 znalezione przez Busganga.
Ograniczona długość g1 g2
3 110 111
4 1101 1110
5 11010 11101
6 110101 111011
7 110101 110101
8 110111 1110011
9 110111 111001101
10 110111001 1110011001
Stany kodera
Koder podobnie jak człowiek zapamiętuje stany w pamięci. Porównując do stanu psychiki
człowieka, raz jesteśmy bardzo przygnębieni a następnego dnia może zdarzyć się zupełnie
odmienny nastrój. Nasz nastrój zależy od naszego stanu psychicznego, na który składają się
także wcześniejsze wydarzenia, które mamy w pamięci. Przekładając to na działanie kodera
możemy powiedzieć, że koder działa na tej samej zasadzie. To, co jest na jego wyjściu zależy
od jego stanu pamiętania, czyli od tego, co było w pamięci. Nasze ludzkie stany są bardzo
skomplikowane, natomiast stany kodera są tylko sekwencją bitów. Wyrafinowane kodery
mają długie L (ograniczoną długość), natomiast niektóre prostsze kodery mają krótkie L. Tym
samym obcinają liczbę stanów, które są pamiętane w koderze.
Koder, który jest przedstawiony na rys. 2 ma ograniczoną długość kodu L = 3. Zaciemnione
rejestry na tym rysunku przetrzymują trzy bity, natomiast niezaciemniony rejestr
przetrzymuje tylko bit wchodzący. Na tych trzech bitach można utworzyć osiem różnych
2
Teoria informacji i kodowanie  Wykład nr 11
kombinacji. Są to stany bitów, jakie mogą być w rejestrach pamięci w danej chwili. Tych
osiem różnych kombinacji determinuje nam jaką sekwencje kodu dostaniemy na wyjściach v1
i v2.
Liczba kombinacji bitów w zaciemnionych na rysunku rejestrach są nazywane stanem kodera
i definiuje się je jej jako:
Liczba stanów = 2L
gdzie L oznacza ograniczoną długość kodu (inaczej mówiąc długość układu pamiętającego
historię) i jest równe k ( m-1) .
Rys.2. Stany kodera pokazujące, co jest w rejestrach pamięci
O tych stanach kodera możemy także myśleć w kategoriach warunków początkowych. Bity
na wyjściu zależą od tych warunków początkowych, które zmieniają się wraz z każdym
taktem zegara.
Przeanalizujmy stany kodera (2,1,4) przedstawionego powyżej. Koder ten daje dwa bity
wyjściowe na każdy jeden bit wejściowy. Jest to więc kod o klasie 1/2 . Jego ograniczenie
długości wynosi L = 3. Całkowita liczba stanów tego kodera (2,1,4) równa jest osiem i są to:
000, 001, 010, 011, 100, 101, 110, 111.
Kody przebite
Kody o szczególnych parametrach takich jak k = 1 i klasach 1/2, 1/3, 1/4, 1/5, 1/7 są czasem
nazywane  kodami matkami . Możemy łączyć pojedyncze bity wejściowe takich kodów, aby
wytworzyć kody przebite (punctured), które dają nam klasy inne niż 1/n.
Przez równoczesne zastosowanie dwóch identycznych koderów o klasach 1/2, tak jak to
pokazano na rys.3, możemy najprościej uzyskać kod przebity. Z układu takiego nie
przesyłamy dalej któregoś z bitów wyjściowych. Dzięki temu możemy przekonwertować kod
o klasie 1/2 na kod, którego klasa będzie wynosić 2/3. W kodzie takim na 2 bity wchodzące
przypada 3 bity wychodzące. Takie postępowanie jest nazywane przebijaniem. Po stronie
odbiorczej te sztuczne bity nie wpływają na dekodowanie, ponieważ ich wykrywanie jest
wbudowane w odpowiednim miejscu przed dekodowaniem.
3
Teoria informacji i kodowanie  Wykład nr 11
Rys.3. Dwa kodery splotowe (2,1,3) dające 4 bity wyjściowe. Trzeci bit jest  przebijany więc
faktyczna kombinacja parametrów kodu to (3,2,3).
Technika ta pozwala nam wytwarzać kody o wielu różnych klasach, które znajdują
zastosowanie w prostych układach hardware owych. Mimo, że możemy bezpośrednio
konstruować kody o klasie 2/3 jak zobaczymy póz
niej, przewagę nad kodami przebitymi mają
kody, w których klasa może być zmieniana dynamicznie (przez software) w zależności od
stanu kanału, otrzymywanych danych wejściowych itp. Zaimplementowanie układu kodera
przebijającego na stałe, mimo że łatwiejsze, nie pozwala na elastyczność w zastosowaniu.
Struktury koderów dla k > 1
Alternatywnie możemy tworzyć kody, gdzie k jest większe niż jeden bit tak jak np. w kodzie
(4,3,3). Taki kod na 3 bity wejściowe daje 4 bity na wyjściu. Liczba rejestrów w tym koderze
jest równa 3. A
atwo wyznaczyć skróconą długość, która wynosi 3 x 2 = 6, a ilość stanów w
kodzie wynosi 64. Kod ten wymaga wielomianów dziewiątego stopnia. Zaciemnione rejestry
na rysunku reprezentują skróconą długość kodu.
Kolejne etapy rysowania struktury kodu (n,k,m), gdzie k jest większe niż jeden, są
następujące. Najpierw rysujemy m boksów, gdzie w każdym z nich znajduje się w po k
rejestrów. Potem rysujemy n sumatorów i łączymy je z rejestrami pamięci wykorzystując do
tego celu współczynniki przy n-tym stopniu wielomianu. Postępując według powyższego
schematu dostaniemy koder jak na rysunku poniżej:
Rys.4. Koder splotowy (4,3,3), posiadający 9 rejestrów pamiętających, 3 bity wejściowe i 4
bity wyjściowe. Zaciemnione rejestry przechowują  stare bity reprezentujące bieżący
stan kodera.
4
Teoria informacji i kodowanie  Wykład nr 11
Kod splotowy systematyczny kontra niesystematyczny
Specjalna odmiana kodu splotowego, w której bity wyjściowe zawierają łatwo rozpoznawalna
sekwencje bitów wejściowych, jest nazywana odmianą systematyczną. Wersja systematyczna
wcześniejszego kodu (4,3,3) jest pokazana poniżej. Z czterech bitów wyjściowych, trzy są
dokładnie taki same jak bity wejściowe. Czwarty bit jest odmianą bitu parzystości
wytwarzany jako kombinacja trzech bitów używanego pojedynczego wielomianu.
Rys.5. Wersja kodera kodu splotowego systematycznego (4,3,3). Koder ten ma taką samą
liczbę rejestrów jak poprzedni oraz trzy bity wejściowe i cztery bity wyjściowe.
Wyjściowe bity składają się z trzech bitów oryginalnych oraz czwartego bitu
 parzystości .
Kody systematyczne są często chętniej stosowane od kodów niesystematycznych, ponieważ
można je łatwo rozpoznać. Dodatkowo kody te potrzebują mniej zasobów sprzętowych do ich
zdekodowania. Inną ważną własnością kodów systematycznych jest to, że nie są one
 katastrofalne , co znaczy, że błędy nie mogą się katastrofalnie propagować. Wszystkie te
własności czynią ten kod bardzo pożądanym. Kody systematyczne są również używane w
Kratowej Modulacji Kodowej (TCM  Trellis Code Modulation). Jednakże własności
zabezpieczające przed błędami kody systematyczne są takie same jak w kodach
niesystematycznych.
Kodowanie sekwencji wejściowej
Wyjściowa sekwencja v może być wyliczona przez splot wejściowej sekwencji bitów u z
odpowiedzią impulsową g. Można to przedstawić jako:
v = u * g
albo w bardziej ogólnej formie:
m
vlj =
"u �" gij
l-i
i=0
gdzie vlj jest bitem wyjściowym l z kodera j, ul-i bitem wejściowym, a gij jest i  tym
wyrazem w wielomianie j .
5
Teoria informacji i kodowanie  Wykład nr 11
Zakodujmy sekwencje dwóch bitów w koderze (2,1,4) i zaobserwujmy proces tworzenia
kodu:
a) t=0, stan początkowy = 000, bit wejściowy = 1, stan bitów wyjściowych = 11:
b) t=1, stan początkowy = 100, bit wejściowy = 0, stan bitów wyjściowych = 11:
c) t=2, stan początkowy = 010, bit wejściowy = 0, stan bitów wyjściowych = 10:
d) t=3, stan początkowy = 001, bit wejściowy = 0, stan bitów wyjściowych = 11:
Rys.6.(a-d). Sekwencja pokazująca przejście pojedynczy bitu przez koder. Jeden bit
wejściowy produkuje 8 bitów wyjściowych.
Najpierw przez koder będzie przechodził pojedynczy bit  1 jak na rysunku powyżej.
a) W chwili t = 0, widzimy, że stan początkowy kodera zainicjowany jest zerami (bity w
prawo są pozycjami rejestru L). Podanie na wejście  1 spowoduje pojawienie się na
wyjściu  11 . Obliczono to przez sumowanie modulo 2 wszystkich bitów w rejestrach
co daje pierwszy bit wyjściowy, a drugi uzyskano przez zsumowanie modulo 2 trzech
bitów . Bity, z których rejestrów należy zsumować, określają nam współczynniki
wielomianu.
b) W chwili t = 1, podana wcześniej  1 przesuwa się do następnego rejestru. Rejestr
wejściowy napełnia się strumieniem zer. Teraz stan kodera jest  100 , a bity
wyjściowe są takie same jak w poprzedniej chwili czyli  11 , co obliczono jak w
punkcie a).
c) W chwili t = 2 wejściowa  1 znowu przesuwa do przodu do kolejnego rejestru. Stan
kodera wynosi teraz  010 , a do rejestru wejściowego napłynęło kolejne  0 . Na
wyjściu mamy stan  10 .
6
Teoria informacji i kodowanie  Wykład nr 11
d) W chwili t = 3 bit wejściowy przesuwa się do ostatniego rejestru dając tym samym
stan 001. Bity wyjściowe są teraz w postaci  11 . W następnej chwili czasowej, czyli
t= 4, podana w chwili t = 0 na wejście  1 opuszcza koder. Do kodera napływają
wtedy same zera utrzymując  zerowy stan początkowy, czyli gotowość kodera do
zakodowania następnej sekwencji.
Zauważamy, że pojedynczy bit wejściowy produkuje 8 bitów wyjściowych, chociaż
nominalnie klasa kodu wynosi 1/2 . To pokazuje, że dla krótkich sekwencji wejściowych,
górna granica klasy kodu jest wyższa od nominalnej, która to odnosi się tylko do długich
sekwencji wejściowych.
Jeżeli będziemy postępować jak powyżej tylko zamiast  1 podamy na wejście  0 , wtedy też
otrzymamy 8 bitów, ale wszystkie będą zerami.
To, co przed chwilą wyznaczyliśmy, jest nazywane odpowiedzią impulsową kodera. Bit  1
ma odpowiedz
impulsową w postaci: 11 11 10 11. Bit  0 również ma odpowiedz
impulsową,
ale jest ona złożona z samych zer: 00 00 00 00 ( nie zostało to pokazane  bit po bicie , ale jest
to intuicyjne i dosyć oczywiste).
Splecienie sekwencji wejściowej z wielomianami kodu, produkuje te dwie sekwencje
wyjściowe, które są nazywane kodami splotowymi. Wykorzystując zasadę  liniowego
nakładania  superpozycji możemy produkować sekwencje kodowe z powyżej
wyznaczonych odpowiedzi impulsowych.
Powiedzmy, że nasza sekwencja bitów wejściowych jest  1011 i chcemy sprawdzić, jaka
sekwencje bitów dostaniemy na wyjściu po zakodowaniu. Bity wyjściowe możemy
wyznaczyć poprzez zsumowanie odpowiednio przesuniętych odpowiedzi impulsowych.
Przykładowo:
Sekwencja bity wejściowych: 1011
Odpowiedz impulsowa dla:
 1  11 11 10 11
 0  00 00 00 00
Sumujemy:
Bity wejściowe Odpowiedz
impulsowa
1 11 11 10 11
0 00 00 00 00
1 11 11 10 11
1 11 11 10 11
Po zsumowaniu
1011 11 11 01 11 01 01 11
Otrzymaliśmy odpowiedz
kodera na podanie sekwencji wejściowej w postaci  1011 poprzez
zsumowanie przesuniętych odpowiedzi dla  1 i  0 .
Na rys.7. ręcznie wprowadzano sekwencję wejściową 1011 i przebadano w kolejnych
chwilach czasowych, w celu weryfikacji wyniku uzyskanego powyżej. Jak się okazało
dostaliśmy ten sam kod wyjściowy. Pokazuje to, że model splotowy, jaki zastosowaliśmy we
wcześniejszych rachunkach jest prawidłowy.
a) t=0, b) t=1, c) t=2, d) t=3,
stan początk.= 000 stan początk.= 100 stan początk.= 010 stan początk.= 101
7
Teoria informacji i kodowanie  Wykład nr 11
bit wejściowy  1 bit wejściowy  0 bit wejściowy  1 bit wejściowy  1
bity wyjściowe  11 bity wyjściowe  11 bity wyjściowe  01 bity wyjściowe  11
Po czterech taktach sekwencja wejściowa kończy się, ale musimy  doczytać stany
rejestrów kodera. W tym celu podajemy tzw. ogon kodu złożony z samych zer (w naszym
przypadku trzech zer):
e) t=4, f) t=5, g) t=6, d) t=7
stan początk.= 110 stan początk.= 011 stan początk.= 001 wyzerowanie kodera
bit wejściowy  0 bit wejściowy  0 bit wejściowy  0 bity na we. i wy.
bity wyjściowe  01 bity wyjściowe  01 bity wyjściowe  11 to strumień zer.
Rys.7. Przebieg kodowania sekwencji 1011.
Wyniki powyższego kodowania w każdej chwili czasowej są przedstawione w tabeli.2.
Tabela.2.Bity wyjściowe oraz bity przechowywane w koderze dla kodu (2,1,4). Bity
wejściowe to:  1011000 .
Chwila czasowa Bit na wejściu Bity na wyjściu Bity w koderze
0 1 11 000
1 0 11 100
2 1 01 010
3 1 11 101
4 0 01 110
5 0 01 011
6 0 11 011
Zakodowana sekwencja to:  11 11 01 11 01 01 11 .
Projekt kodera
Dwie poprzednie metody pokazują w sposób matematyczny co dzieje się w koderze.
Realizacja sprzętowa kodera jest prostsza, ponieważ koder nie koduje sposobem
matematycznym. Kodery kodów splotowych używają gotowych tablic do kodowania (tzw.
look-up table). Taka tablica składa się z czterech kolumn.
1. Bit wejściowy.
2. Stan kodera, który jest jednym z 8 możliwych stanów np. dla kodu (2,1,4)
3. Bitów wyjściowych. Dla kodu (2,1,4), wyjściowe 2 bity mogą tworzyć cztery
kombinacje: 00, 01, 10, 11.
4. Stan wyjścia, który będzie stanem wejściowym dla następnego bitu.
Dla kodu (2,1,4) dostajemy wielomiany tak jak na rys.7. Za ich pomocą została utworzona
tablica z gotowymi wynikami kodowania (look-up table):
8
Teoria informacji i kodowanie  Wykład nr 11
Tablica.3. Tablica look up dla kodu (2,1,4).
Bit wejściowy Stany rejestrów kodera Bity wyjściowe Stany wyjść
I1 s1 s2 s3 O1 O2 s1 s2 s3
0 0 0 0 0 0 0 0 0
1 0 0 0 1 1 1 0 0
0 0 0 1 1 1 0 0 0
1 0 0 1 0 0 1 0 0
0 0 1 0 1 0 0 0 1
1 0 1 0 0 1 1 0 1
0 0 1 1 0 1 0 0 1
1 0 1 1 1 0 1 0 1
0 1 0 0 1 1 0 1 0
1 1 0 0 0 0 1 1 0
0 1 0 1 0 0 0 1 0
1 1 0 1 1 1 1 1 0
0 1 1 0 0 1 0 1 1
1 1 1 0 1 0 1 1 1
0 1 1 1 1 0 0 1 1
1 1 1 1 0 1 1 1 1
Ta tablica look-up unikalnie opisuje kod (2,1,4). Taka tablica jest zupełnie inna dla każdego
kodu w zależności od parametrów użytego wielomianu.
Graficznie możemy przedstawić na trzy sposoby działanie kodera dla lepszego zrozumienia
jego operacji. Są to:
1. Diagram stanu
2. Diagram o strukturze drzewa
3. Diagram kratowy
Rys. 8. Diagram stanu dla kodu (2,1,4)
Strzałki:
- oznacza, że na wejściu kodera pojawiło się zero
- oznacza, że na wejściu kodera pojawiła się jedynka
9
Teoria informacji i kodowanie  Wykład nr 11
Diagram stanu dla kodu (2,1,4) pokazano na powyższym rysunku. Każdy okrąg reprezentuje
jeden stan kodera. W każdej chwili czasowej koder przebywa w jednym z tych stanów.
Strzałki, które łączą poszczególne okręgi pokazują rodzaj transmisji, jaka może wystąpić w
zależności od tego jaki bit podamy na wejście. W dowolnej chwili czasu może nadejść  1
lub  0 . W zależności od tego bitu, który nadszedł, koder skacze do różnych stanów. Wadą
diagramu stanu jest to, że nie obejmuje on działania w czasie, ale tylko połączenia logiczne.
Porównując powyższy diagram z kodowaniem za pomocą tablicy look up stwierdzamy, że
diagram stanu zawiera te same informacje, które są zawarte w tablicy look up lecz w postaci
graficznej. Strzałki  ciągłe wykrywają nadejście  0 , a strzałki rysowane linią przerywana
wykrywają nadejście  1 . Bity wyjściowe dla każdego przypadku są umieszczone na
strzałkach wykrywających stan transmisji.
Jeszcze raz wróćmy do pojęcia stanów. Wyobraz
my sobie, że jesteśmy na wyspie. Ile jest
możliwych dróg, którymi możemy opuścić wyspę? Możemy wskoczyć do wody i płynąć albo
możemy wziąć łódkę. Mamy tylko te dwie możliwości na opuszczenie małej wyspy.
Bierzemy łódkę, aby dopłynąć do stałego lądu. Teraz ile jest możliwości dróg, którymi
możemy się poruszać? Aby dotrzeć do celu możemy znów skorzystać z łódki, lecz także z
samochodu. To gdzie jesteśmy (nasz stan) determinuje nam czym możemy się przemieszczać
(nasze wyjście).
Niektóre stany kodera dają bity wyjściowe  00 i  11 a inne dają  01 i  10 . Stan kodera nie
daje wszystkich czterech opcji.
Jak zakodować sekwencje 1011 stosując diagram stanu?
(1) Zaczynamy od stanu  000 . Przychodzi  1 na wejście, przez co na wyjściu ustawiany
jest stan  11 , a stan, w którym jest koder to  100 .
(2) Następnie przychodzi na wejście  0 . Bity wyjściowe nadal będą  11 , a stan naszego
kodera  010 .
(3) Przychodzi  1 na wejście, co powoduje zmianę bitów wyjściowych na  01 , a koder
znajduje się w stanie  101 .
(4) Ostatnia  1 ustawia stan kodera na  110 i bity wyjściowe na  11 . W tym momencie
mamy sekwencje 11 11 01 11, lecz to nie koniec kodowania, gdyż musimy jeszcze
doprowadzić koder do stanu wyjściowego, czyli stanu  000 .
(5) Ze stanu  110 koder przechodzi do  011 , na wyjściu pojawiają się bity  01 .
(6) Następnie ze stanu  011 koder przechodzi do  001 , na wyjściu bity  01
(7) Ostatecznie koder przyjmuje wreszcie stan  000 i ustawia na wyjściu bity na  11 .
Końcowy wynik kodowania jest następujący: 11 11 01 11 01 01 11.
Wynik ten jest identyczny z tym, który otrzymaliśmy poprzez dodawanie pojedynczych,
odpowiednio przesuniętych, odpowiedzi impulsowych dla sekwencji 1011000.
Diagram o strukturze drzewa
Na rys.9. przedstawiono diagram o strukturze drzewa dla kodu (2,1,4). Diagram ten próbuje
pokazać przejścia w czasie, gdy wchodzimy coraz głębiej w gałęzie drzewa. Diagram taki jest
w jakimś stopniu lepszy niż diagram stanu, lecz nadal jest to niedoskonała reprezentacja
kodów splotowych.
W tym diagramie zamiast skoków z jednego stanu do innego, poruszamy się po gałęziach
drzewa w górę bądz
w dół, w zależności czy na wejściu zostało odebrane  0 czy  1 .
Na rys.9. Pierwsza gałąz
wykrywa przybycie  1 lub  0 . Zaczynamy od stanu  000 . Jeżeli
zostanie odebrane  0 idziemy w drzewie do góry, a jeżeli  1 to idziemy w dół. Na rys. 9.
linie koloru czerwonego oznaczają przybycie na wejście  0 , natomiast linie koloru
10
Teoria informacji i kodowanie  Wykład nr 11
niebieskiego mówią, że na wejście nadeszła  1 . Pierwsze 2 bity oznaczają stan wyjścia, bity
w nawiasach informują o stanie kodera.
Zakodujmy sekwencje 1011, taką sama jak w poprzednich przykładach. Na pierwszej gałęzi
idziemy w dół. Na wyjściu jest  11 a stan, w którym jesteśmy to  100 . Teraz otrzymujemy
na wejście  0 , więc idziemy do góry. Stan wyjść to  11 a stan, w którym jesteśmy to  010 .
Następnie nadchodzi  1 , idziemy w dół i dostajemy na wyjściu  01 , a stan jest  101 .
Jako następny bit na wejściu pojawia się kolejna  1 , więc idziemy w dół i dostajemy na
wyjściu  11 . W tym momencie kończy się nam sekwencja wejściowa, lecz musimy dojść do
stanu  000 . W tym celu podajemy na wejście już tylko same zera. Czyli podając teraz zero
na wejście idziemy w górę. Na wyjściu jest  01 a stan  011 .
Lecz co się dzieje w przypadku, gdy sekwencja wejściowa jest dłuższa od gałęzi drzewa? W
takim przypadku musimy  rozciągnąć gałęzie drzewa. Więc teraz powtarzamy fragment
drzewa. Aktualnie potrzebujemy zakodować sekwencje 1011 000, gdzie 3 ostatnie bity to bity
 ogona , dołożone, aby wyzerować stan. W takim przypadku przeskakujemy w drzewie do
miejsca gdzie bity wyjściowe i stan odpowiada naszemu następnemu stanowi. Następnie
podając kolejne bity na wejście, dochodzimy do końca drzewa. Teraz dopiero otrzymujemy
pełną sekwencje bitów na wyjściu: 11 11 01 11 01 01 11. Jak widać jest ona identyczna z
sekwencjami bitów wyznaczonych innymi sposobami.
11
Teoria informacji i kodowanie  Wykład nr 11
Rys. 9. Diagram o strukturze drzewa kodu (2,1,4)
12
Teoria informacji i kodowanie  Wykład nr 11
Diagram kratowy
Generalnie diagramy kratowe są mało przejrzyste, ale mają inne zalety, co decyduje o ich
wyższości nad poprzednimi diagramami: stanów oraz diagramem o strukturze drzewa. W
diagramie kratowym jest uwzględniany linowo czas wszystkich kolejnych sekwencji zdarzeń.
Na osi X jest zaznaczony zdyskretyzowany czas, a na osi Y wszystkie możliwe stany, jakie
mogą wystąpić. W diagramie takim poruszamy się poziomo zgodnie z upływem czasu. Każda
transmisja oznacza, że na wejście został podany jeden nowy bit.
Tworzenie diagramu kratowego
Rysując diagram kratowy musimy najpierw nanieść wszystkie możliwe stany (2L) na oś
pionową. Póz
niej łączymy każdy stan z dopuszczalnym stanem następnym. W każdym stanie
są tylko dwie możliwości do wybrania. Są one zdeterminowane przez nadchodzące bity w
zależności czy to jest  0 czy  1 . Na poszczególnych strzałkach zaznaczone są bity
wejściowe oraz bity wyjściowe, które umieszczamy w nawiasie. Strzałki są skierowane w
górę bądz
w dół, w zależności od tego jaki bit został podany na wejście. Jeżeli podamy  1
wówczas strzałka jest skierowana w dół, jeżeli natomiast podamy  0 to strzałka skierowana
jest do góry. Taki diagram kratowy jest unikalny dla każdego kodu, podobnie jak diagram
stanu i diagram o strukturze drzewa. Możemy także rysować kraty dla tylu okresów ile
chcemy. Każdy okres będzie powtarzał możliwą transmisje.
Zawsze startujemy ze stanu  000 . Rozpoczynamy z tego punktu i rozszerzamy kraty, aż
wszystkie możliwe transmisje zostaną wykorzystane i uwzględnione na diagramie.
Możliwe
stany
kodera
Upływ czasu
Rys.10. Diagram kratowy kodu (2,1,4)
13
Teoria informacji i kodowanie  Wykład nr 11
Jak kodować sekwencje bitów używając diagramu kratowego
W górnej części rys.10a pokazano nadchodzące bity w danych chwilach czasowych.
Kodowanie jest nie jest trudne. Możemy zaczynać tylko z jednego punktu  000 . Następnie
przesuwamy się w prawą stronę  w zależności od stanów na wejściu w górę, gdy jest  0 lub
w dół, gdy przychodzi  1 . Na rysunku przedstawiono tak zbudowaną  ścieżkę dla
przykładowej sekwencji bitów wejściowych 1011000.Widzimy, że diagram kratowy daje taką
samą sekwencje zakodowanych bitów na wyjściu jak wcześniejsze trzy metody (odpowiedzi
impulsowej, diagram stanu oraz diagram o strukturze drzewa). Takie diagramy kratowe
wyglądają bardzo podobnie, lecz musimy pamiętać, że każdy z nich jest unikalny i opisuje
tylko jeden określony kod.
Rys.10a. Kodowanie sekwencji bitów wejściowych 1011000.
Bity wyjściowe to 11110111010111
Czwarty sposób definiowania kodów splotowych: podajemy macierz
generującą kod.
Wyjściowa sekwencja kodera splotowego jest uzależniona od m-stopniowego rejestru
przesuwnego. Każde z n połączeń jest reprezentowane przez wielomian stopnia m. Zatem
koder kodu splotowego (n, 1, m), jest określony za pomocą n wielomianów, zwanych
wielomianami generującymi:
( j) 2 m
g (X ) = g0( j) + g1( j) X + g2( j) X + ...+ gm( j) X j =1,...,n
Wielomiany generujące możemy zapisać w postaci macierzy, otrzymując tym samym
tzw. macierz generującą kod splotowy:
14
Teoria informacji i kodowanie  Wykład nr 11
(1)
Ą# ń#
g (X )
ó# Ą#
(2)
ó#g (X )Ą#
G(X ) =
ó# Ą#
...
ó# Ą#
(n)
ó# Ą#
Ł#g (X )Ś#
Każdy j-ty ciąg kodowy można wyrazić przy pomocy wielomianu:
2 l
v( j) = ...+ v0( j) + v1( j) X + v2( j) X + ...+ vl ( j) X j =1,...,n
Cała wyjściowa sekwencja, może być reprezentowana przez wektor wielomianów
kodowych:
Ą# ń#
v(1) (X )
ó# Ą#
(2)
ó#v (X )Ą#
v(X ) =
ó# Ą#
...
ó# Ą#
(n)
ó# Ą#
Ł#v (X )Ś#
Operację kodowania można więc przedstawić w postaci macierzowej:
v(X ) = c(X ) �" G(X )
gdzie, c jest wielomianem odpowiadającym ciągowi informacyjnemu.
Przykład
Rozpatrzmy kod splotowy o parametrach (2, 1, 2). Niech macierz generująca kod
splotowy ma postać:
2
Ą# ń#
1+ X
G(X ) =
ó# Ą#
2
Ł#1+ X + X Ś#
2 3 4
Ciąg informacyjny podany na wejście kodera ma postać: c(X ) =1+ X + X + X .
Należy znalez
ć ciąg kodowy.
Ciąg kodowy można wyznaczyć korzystając z podanego wcześniej wzoru:
2 3 5 6
Ą# ń# Ą# ń#
1+ X 1+ X + X + X
2 3 4
v(X ) = c(X ) �"G(X ) = [1+ X + X + X ]�" =
ó# Ą# ó# Ą#
2 4 6
Ł#1+ X + X Ś# Ł#1+ X + X + X Ś#
A więc ostatecznie zakodowana sekwencja odpowiada wektorowi:
1 0 0 1 0 1 1 ...
Ą# ń#
v =
ó#1 1 0 0 1 0 1 ...Ą#
Ł# Ś#
Podobnie jak w przypadku kodów blokowych, można dla kodów splotowych
wprowadzić pojęcie macierzy testów parzystości H(X). Macierz taka musi spełniać
równanie:
15
Teoria informacji i kodowanie  Wykład nr 11
T
v(X )�" H (X ) = 0
dla każdego wektora wielomianów kodowych v(X). Macierz generującą kod splotowy G(X)
można zapisać w postaci:
G(X ) = [IP(X )]
gdzie: I = 1, a P(X) to wektor wielomianowy. Macierz testów parzystości H(X) można
zapisać więc w postaci:
H (X ) = [P(X )T I]
lub zapisując w wygodnej do obliczeń postaci (gdy znamy macierz G(X)):
T
G(X )�" H (X ) = 0
Należy pamiętać, że obie macierze są oczywiście wielomianowe.
Przykład
Podobnie jak w poprzednim przykładzie, niech będą dane wielomiany kodowe:
2
v(1) (X ) = c(X )�"(1+ X )
2
v(2) (X ) = c(X )�"(1+ X + X )
Należy znalez
ć macierz testów parzystości.
Jeśli porównamy oba te równania względem wspólnego c(X), otrzymamy:
2 2
v(1) (X ) �"(1+ X + X ) = v(2) (X )�"(1+ X )
czyli:
2 2
v(1) (X ) �" (1+ X + X ) + v(2) (X ) �" (1+ X ) = 0
Szukana macierz testów parzystości ma postać:
2
Ą# ń#
1+ X + X
H (X ) =
ó# Ą#
2
1 + X
Ł# Ś#
Możliwe jest zbudowanie kodera dla każdego kodu splotowego w postaci sprzężonego
układu dzielenia wielomianów. Przykładowy koder dla kodu (2, 1, 2) z poprzedniego
przykładu ma postać:
16