Kod splotowy
Z Wikipedii
W telekomunikacji kod splotowy (ang. convolutional codes) jest typem kodu korekcyjnego. Kody splotowe zwykle są określane przez trzy parametry: (n,k,m). Ideą kodowania splotowego jest przekształcenie wejściowego k-bitowego ciągu informacyjnego na n-bitowy ciąg wyjściowy. Sprawność kodu splotowego wynosi k/n (n ≥ k). Dodatkowym parametrem jest m, który oznacza liczbę przerzutników "D" w rejestrze albo ilość boksów, z których ten rejestr się składa. Można również wyróżnić wielkość L, która 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 wpływających na generowanie n bitów wyjściowych.
Spis treści |
[edytuj] Gdzie kody splotowe są używane?
Kody splotowe używane są często w celu poprawy odbioru w radiofonii cyfrowej, telefonii komórkowej oraz w łączach satelitarnych.
[edytuj] Kody przebite (ang. punctured convolutional 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 (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.1, 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. Kody przebite używane są w systemach satelitarnych, np. w Intelsat lub DVB.
[edytuj] Struktura koderów kodu splotowego
Koder zapamiętuje stany w pamięci. Wyrafinowane kodery mają długie L, natomiast niektóre prostsze kodery mają krótkie L. Liczba stanów kodera to liczba kombinacji bitów w L rejestrach i wyraża sie wzorem: Liczba stanów = 2L.
- k=1
Koder składa się z: m boksów reprezentujących m rejestrów pamiętających, n sumatorów mudulo-2, które reprezentują n bitów wejściowych. Rejestry pamięci są odpowiednio połączone z sumatorami generującymi wielomian. Wybór, które bity są dodawane i wytwarzają bit wyjściowy jest dokonywany na podstawie wielomianu generującego g dla tego bitu. Dla kodera na rys.2: pierwszy bit wyjściowy ma wielomian generujący w postaci (1,1,1), drugi bit (0,1,1), a trzeci (1,0,1).
v1 = mod2(u1 + u0 + u − 1);
v2 = mod2(u0 + u − 1);
v3 = mod2(u1 + u − 1);
Koder przedstawiony na rys.1 ma ograniczoną długość kodu L=2. Z tego wynika, że liczba stanów kodera wynosi 4. Zaciemnione rejestry są układem pamiętającym historię.
- k>1
Kolejne etapy rysowania kodera dla 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. Dla kodera na rys.3 kod ma 3 bity wejściowe, daje 4 bity na wyjściu. Liczba rejestrów w tym koderze jest równa 3. Ł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 generujących dziewiątego stopnia. Zaciemnione rejestry na rysunku reprezentują skróconą długość kodu.
[edytuj] 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) z rys. 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.
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.
[edytuj] Jak dobrać wielomian generujący?
Dla każdego m szukanego kodu istnieje wiele różnych wielomianów generujących. Wielomiany te nie generują wszystkich możliwych sekwencji wyjściowych, a mimo to mają dobre własności wykrywania błędów. Poniżej w tabeli znajduje się lista "dobrych" wielomianów.
| Ograniczona długość L | 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 |
Tab.1 Wielomiany generujące dla kodów o klasie 1/2 znalezione przez Busganga.
[edytuj] Kodowanie kodów splotowych
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 lub w bardziej ogólnej formie:
gdzie vlj jest bitem wyjściowym l z kodera j, ul-i bitem wejściowym, a gij jest i-tym wyrazem w wielomianie j.
[edytuj] 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 wejściowy.
2. Stan kodera.
3. Bity wyjściowe.
4. Stan wyjścia, który będzie stanem wejściowym dla następnego bitu.
[edytuj] Diagram stanu
W diagramie stanu 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.
[edytuj] Diagram o strukturze drzewa
W tym diagramie zamiast skoków z jednego stanu do innego, poruszamy się po gałęziach drzewa w górę bądź w dół, w zależności czy na wejściu zostało odebrane „0” czy „1”. Pierwsza gałąź wykrywa przybycie „1” lub „0”. Zaczynamy od stanu „0..0” (L zer). Jeżeli zostanie odebrane „0” idziemy w drzewie do góry, a jeżeli „1” to idziemy w dół. Na rys.6 linie koloru czerwonego oznaczają przybycie na wejście „0”, natomiast linie kolor niebieskiego mówią, że na wejście nadeszła „1”. Pierwsze bity oznaczają stan wyjścia, bity w nawiasach informują o stanie kodera. W przypadku, gdy sekwencja wejściowa jest dłuższa od gałęzi drzewa należy „rozciągnąć” gałęzie drzewa - przeskakujemy w drzewie do miejsca gdzie bity wyjściowe i stan odpowiada naszemu następnemu stanowi.
[edytuj] Diagram kratowy
- Tworzenie diagramu kratowego
W diagramie kratowym jest uwzględniany liniowo 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. Rysując diagram kratowy musimy najpierw nanieść wszystkie możliwe stany (2L) na oś pionową. Póź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ądź 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 „0..0” (L zer). Rozpoczynamy z tego punktu i rozszerzamy kraty, aż wszystkie możliwe transmisje zostaną wykorzystane i uwzględnione na diagramie.
- Kodowanie z użyciem diagramy kratowego
W górnej części rys.8 pokazano nadchodzące bity w danych chwilach czasowych. Zaczynamy z punktu „0..0” (L zer). 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 rys.8 przedstawiono tak zbudowaną „ścieżkę” dla przykładowej sekwencji bitów wejściowych 1011000.
[edytuj] Dekodowanie kodów splotowych
Istnieje kilka metod dekodowania kodów splotowych. Są one podzielone na dwie zasadnicze kategorie.
1.Metoda „twarda” (ang. hard). Porównujemy odebraną sekwencję z wszystkimi dostępnymi kombinacjami i wybieramy jedną, która ma najmniejszą odległość Hamminga. Metodę tą ma bardzo silny próg decyzyjny. Jest to przykład dekodowania sekwencyjnego.
2.Metoda „miękka” (ang. soft). Możemy skorelować te sekwencje i wybrać jedną o najlepszej korelacji.Próg decyzyjny jest trochę rozmyty i pozostaje tu zawsze pewien margines niepewności. Jest to jeden z przykładów dekodowania metodą maksymalnego prawdopodobieństwa. Na takiej zasadzie działa np. dekodowanie Viterbiego.
[edytuj] Dekodowanie sekwencyjne
Polega na wędrowaniu ścieżką diagramu kratowego i liczeniu ewentualnych błędnych decyzji. Gdy błędów będzie zbyt wiele – cofamy się i wybieramy inną ścieżkę. Liczbę błędów zapamiętuje licznik, a maksymalną ilość błędnych decyzji ustalamy sami. Pomimo odebrania zakłóconego sygnału, dekoder jest w stanie zdekodować go poprawnie.
Dekodowanie sekwencyjne używane jest gdy mamy do czynienia z dużymi zakłóceniami i słabym sygnałem użytecznym (gdzie odstęp sygnał-szum jest mały). Często spotykane w systemach satelitarnych, np. FEC.
[edytuj] Dekodowanie metodą maksymalnego prawdopodobieństwa
Metoda ta korzysta z algorytmu Viterbiego. Polega on na analizowaniu wszystkich ścieżek i porównaniu ich z sekwencją odebraną. Patrzymy przy tym na liczbę pozycji, na których się różnią i wybieramy oczywiście ścieżkę najbardziej podobną do odebranej sekwencji. Metoda ta jest stosowana w systemach gdzie błędy występują stosunkowo rzadko – małe jest prawdopodobieństwo przekłamania bitów, oraz błędy występują zupełnie przypadkowo a prawdopodobieństwo błędu podwójnego jest o wiele mniejsze od prawdopodobieństwa wystąpienia błędu pojedynczego.
