Teoria informacji
i kodowanie
Wykład nr 11
prof. dr hab. inż. Andrzej Pach
Plan wykładu
Kody splotowe
Teoria informacji i kodowanie
Wykład 11 2
Kody splotowe - parametry
Kody splotowe 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 (ilość boksów rejestru)
Inna notacja parametrów kodu:
(n, k, L)
L - oznacza ograniczoną długość kodu i jest definiowana jako:
L = k ( m-1 )
Ograniczona długość L reprezentuje liczbę bitów w pamięci kodera
Teoria informacji i kodowanie
Wykład 11 3
Parametry c.d.
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
Wielkość:
k/n
określa klasę kodu i jest miarą jego efektywności.
Teoria informacji i kodowanie
Wykład 11 4
Przykład kodera (3,1,3)
m rejestrów pamiętających.
n sumatorów modulo-2, które reprezentują n bitów wyjściowych
Teoria informacji i kodowanie
Wykład 11 5
Wielomiany generujące - tabela
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
Teoria informacji i kodowanie
Wykład 11 6
Warunki początkowe kodera
Zaciemnione rejestry na tym rysunku przetrzymują trzy bity. Są to
stany bitów jakie mogą być w rejestrach pamięci w danej chwili. Jest
to osiem różnych kombinacji, które determinują nam jaką sekwencje
kodu dostaniemy na wyjściach v1 i v2. Są to stany początkowe
kodera i jest ich 2L (L - długość kodu pamiętającego).
Teoria informacji i kodowanie
Wykład 11 7
Kody przebite (punctured codes)
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, które dają nam klasy inne niż 1/n.
Teoria informacji i kodowanie
Wykład 11 8
Struktury koderów o k > 1
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.
Teoria informacji i kodowanie
Wykład 11 9
Kod splotowy systematyczny
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):
Teoria informacji i kodowanie
Wykład 11 10
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
ul-i
vlj
gdzie jest bitem wyjściowym l z kodera j, bitem wejściowym,
gij
jest i  tym wyrazem w wielomianie j .
Teoria informacji i kodowanie
Wykład 11 11
Kodowanie pary bitów
t=0, stan początkowy = 000, t=1, stan początkowy = 100,
bit wejściowy = 1, bit wejściowy = 0,
stan bitów wyjściowych = 11 stan bitów wyjściowych = 11
Teoria informacji i kodowanie
Wykład 11 12
Kodowanie pary bitów c.d.
t=2, stan początkowy = 010, t=3, stan początkowy = 001,
bit wejściowy = 0, bit wejściowy = 0,
stan bitów wyjściowych = 10 stan bitów wyjściowych = 11
Teoria informacji i kodowanie
Wykład 11 13
Odpowiedz
impulsowa
Wyznaczony wcześniej ciąg bitów, jest nazywany odpowiedzią
impulsową kodera.
Odpowiedz
impulsowa dla:
 1  11 11 10 11
 0  00 00 00 00
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.
Teoria informacji i kodowanie
Wykład 11 14
Przykład kodowania bitów
Przykład zakodowania sekwencji bitów 1011 za pomocą
odpowiedzi impulsowej:
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
1011 11 11 01 11 01 01 11
Teoria informacji i kodowanie
Wykład 11 15
Tablica look up
Kodery kodów splotowych używają gotowych tablic do
kodowania (tzw. look up table). Taka tablica składa się z
czterech kolumn.
1. Bitów wejściowych.
2. Stanu kodera, który np. dla kodu (2,1,4) jest jednym z 8
możliwych stanów
3. Bitów wyjściowych. Dla kodu (2,1,4), wyjściowe 2 bity
mogą tworzyć cztery kombinacje: 00, 01, 10, 11.
4. Stanu wyjścia, który będzie stanem wejściowym dla
następnego bitu.
Teoria informacji i kodowanie
Wykład 11 16
Tablica look up table - przykład
Stany rejestrów kodera Bity wyjściowe Stany wyjść
Bit wejściowy
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 Teoria informacji i kodowanie 1 1 1
1 0 1
Wykład 11 17
Diagram stanu dla kodu (2,1,4)
oznacza, że na wejściu kodera pojawiło się zero
oznacza, że na wejściu kodera pojawiła się jedynka
Teoria informacji i kodowanie
Wykład 11 18
Diagram stanu
Diagram stanu dla kodu (2,1,4) pokazano na poprzednim
slajdzie. 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. Bity wyjściowe
dla każdego przypadku są umieszczone na strzałkach
wykrywających stan transmisji. Wadą diagramu stanu jest to,
że nie obejmuje on działania w czasie ale tylko połączenia
Teoria informacji i kodowanie
logiczne.
Wykład 11 19
Diagram o strukturze drzewa
Teoria informacji i kodowanie
Wykład 11 20
Diagram o strukturze drzewa c.d.
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 . Zaczynamy od stanu  000 . Jeżeli zostanie odebrane
 0 idziemy w drzewie do góry, a jeżeli  1 to idziemy w
dół. Pierwsze 2 bity na gałęziach drzewa oznaczają stan
wyjścia, bity w nawiasach informują o stanie kodera.
Teoria informacji i kodowanie
Wykład 11 21
Diagram kratowy
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.
Teoria informacji i kodowanie
Wykład 11 22
Diagram kratowy - przykład
Możliwe
stany
kodera
Teoria informacji i kodowanie
Upływ czasu
Wykład 11 23
Kodowanie kratowe sekwencji
bitów 1011000
Teoria informacji i kodowanie
Wykład 11 24
Czwarta definicja kodu
splotowego
Koder kodu splotowego (n, 1, m), jest określony za pomocą n
wielomianów, zwanych wielomianami generującymi:
2 m
j = 1,...,n
g( j) (X ) = g0( j) + g1( j) X + g2( j) X +...+ gm( j) X
Wielomiany generujące możemy zapisać w postaci macierzy,
otrzymując tym samym tzw. macierz generującą kod splotowy :
Ą# ń#
g(1) (X )
ó# Ą#
(2)
ó#g (X )Ą#
G(X ) =
ó# Ą#
...
ó# Ą#
(n)
ó# Ą#
Ł#g (X )Ś#
Teoria informacji i kodowanie
Wykład 11 25
Wektor wielomianów kodowych
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,2,...,n
Cała wyjściowa sekwencja, może być reprezentowana przez
wektor wielomianów kodowych:
Ą# ń#
v(1) (X )
ó#v(2) Ą#
(X )Ą#
ó#
v(X ) =
ó# Ą#
...
ó# Ą#
(n)
ó# Ą#
Ł#v (X )Ś#
Operację kodowania można przedstawić w postaci macierzowej:
v(X ) = c(X ) �" G(X )
Teoria informacji i kodowanie
Wykład 11 26
Przykład
Macierz generująca kod splotowy ma postać:
2
Ą# ń#
1+ X
G(X ) =
ó#1+ X + X 2 Ą#
Ł# Ś#
Ciąg informacyjny podany na wejście kodera:
2 3 4
c(X ) =1+ X + X + X
Ciąg kodowy można wyznaczyć ze 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 Ś#
Teoria informacji i kodowanie
Wykład 11 27
Przykład c.d.
A więc ostatecznie zakodowana sekwencja odpowiada wektorowi:
1 0 0 1 0 1 1 ...
Ą# ń#
v =
ó#1 1 0 0 1 0 1 ...Ą#
Ł# Ś#
Przykład kodera dla kodu (2, 1, 2):
Teoria informacji i kodowanie
Wykład 11 28