Przejdź do treści
Wróć do wyników wyszukiwania

Kodowanie turbo z dekodowaniem iteracyjnym

Autor metody
Claude Berrou, Alain Glavieux, and Punya Thitimajshima
Rok
1993
Typ
iterative error-correcting code
Rodzina
Coding theory

Ten tekst jest tłumaczeniem maszynowym i nie został jeszcze sprawdzony. Przeczytaj oryginał po angielsku

Rozmiar czcionki

Do czego służy?

Kody turbo, wprowadzone przez Berrou, Glavieux i Thitimajshimę w 1993 roku, stanowią kamień milowy w historii kodowania kanałowego.

Osiągają one wydajność w granicach 0,5 dB od limitu Shannona – teoretycznej granicy niezawodnej komunikacji – co wcześniej uważano za niemożliwe przy praktycznej złożoności. Kody turbo wykorzystują połączone kody konwolucyjne z przeplotnikiem i dekodowanie iteracyjne za pomocą propagacji wiarygodności. Zostały przyjęte w standardzie 3G (UMTS) i nadal odgrywają ważną rolę w systemach 4G/5G obok kodów LDPC.

Intuicja stojąca za metodą

Standardowe kody korygujące błędy dodają redundancji do ochrony danych, ale zazwyczaj wymagają złożonego dekodowania (np. największej wiarygodności, które rośnie wykładniczo wraz z długością kodu). Kody turbo odwracają problem: używają prostych enkoderów (dwóch lub więcej kodów konwolucyjnych) równolegle, rozdzielonych pseudo-losowym przeplotnikiem, a dekodery wymieniają informacje iteracyjnie. Przeplotnik zapewnia, że błędy, które są trudne dla jednego kodu, są prawdopodobnie łatwe dla innego (ze względu na permutację), więc iteracyjne udoskonalanie zbiega do prawdziwej wiadomości. Ten „efekt turbo” (stąd nazwa) zapewnia wykładniczo lepszą wydajność niż dekodowanie jednoprzebiegowe, zbliżając się do teoretycznej granicy.

Historia

Kody turbo zostały ogłoszone na konferencji ICC w 1993 roku, szokując społeczność teorii kodowania wydajnością zbliżoną do Shannona. Były one głównym motorem adopcji standardu 3G (UMTS, cdma2000) pod koniec lat 90. Zrozumienie kodów turbo doprowadziło do szerszej teorii dekodowania iteracyjnego i renesansu w zrozumieniu klasycznych kodów (np. pokazano, że kody Hamminga mają strukturę iteracyjną). W latach 2000. kody LDPC (ponownie odkryte przez Gallagera w 1962 r.) pojawiły się jako konkurenci o porównywalnej wydajności i prostszej architekturze. Kody polarne (Arikan, 2009) oferowały teoretyczną optymalność w granicy. Nowoczesne standardy (5G NR) obsługują wszystkie trzy rodziny; kody turbo są przestarzałe, ale szeroko implementowane.

Kiedy stosować

Kody turbo sprawdzają się w kanałach z głębokimi zanikami lub silnym szumem, gdzie potrzebna jest silna korekcja błędów (np. komunikacja satelitarna, kosmiczna, podwodna). Używaj kodowania turbo, gdy krytyczne są niskie wskaźniki błędów bitowych (BER < 10^-6), a opóźnienie pozwala na dekodowanie iteracyjne (kilka milisekund). Kody turbo są mniej odpowiednie dla aplikacji krytycznych pod względem szybkości lub bardzo krótkich pakietów (przeplotnik i stan dekodera dominują narzut). Wraz z rozwojem kodów LDPC i polarnych (nieco lepsza wydajność, prostsza architektura) kody turbo są obecnie przestarzałe w wielu nowych standardach, chociaż nadal są używane w warstwach kompatybilności.

Ograniczenia i uwagi

  • Dekodowanie iteracyjne wprowadza opóźnienie (dziesiątki milisekund dla długich przeplotników)
  • Wydajność jest wrażliwa na projekt przeplotnika; zły wybór podważa efekt turbo
  • Błędy mają tendencję do propagowania się w klastrach (podłoga błędów) przy bardzo niskich BER; wymaga dostosowania kodu do łagodzenia
  • Złożoność dekodowania jest proporcjonalna do długości informacji (nie wykładnicza, ale nadal wysoka)
  • Krótkie pakiety cierpią z powodu narzutu przeplotnika i niewystarczającej głębokości iteracji dla zbieżności

Warunki podane w źródle nie zastępują niezależnego przeglądu naukowego ani walidacji przez silnik analityczny.

Mocne strony

  • Wydajność w granicach 0,5 dB od limitu Shannona przy praktycznej złożoności
  • Działa dobrze w szerokim zakresie stosunków sygnału do szumu bez zjawiska progowego (w przeciwieństwie do kodów klasycznych)
  • Dekodowanie iteracyjne poprawia wydajność z każdą iteracją, umożliwiając kontrolę szybkości poprzez liczbę iteracji
  • Rozdzielna konstrukcja: można użyć dowolnego kodu konwolucyjnego, co zapewnia elastyczność
  • Odporność na błędy impulsowe dzięki rozproszeniu przez przeplotnik

Zastosowania

  • Komórkowe 3G/4G (UMTS, LTE): kanały ruchu radioliniowego i downlink z kodami turbo zapewniającymi wydajność zbliżoną do Shannona
  • Komunikacja satelitarna: misje kosmiczne (np. łaziki marsjańskie) wykorzystują kody turbo do niezawodnego odzyskiwania danych z ekstremalnego szumu
  • Wojskowa komunikacja bezpieczna: szyfrowana transmisja danych z silną korekcją błędów w środowiskach podatnych na zakłócenia
  • Bezprzewodowe sieci czujnikowe: węzły o niskim poborze mocy wykorzystują krótkie kody turbo do niezawodnego przekazywania danych w wielu skokach
  • Telemetria medyczna: urządzenia biomedyczne przesyłające krytyczne dane pacjenta przez zaszumione łącza bezprzewodowe

Jak to działa

Jak to działa

1

Bity informacyjne są kodowane do dwóch równoległych słów kodowych przy użyciu identycznych enkoderów konwolucyjnych (RSC: rekursywny systematyczny kod konwolucyjny).

2

Pomiędzy dwoma enkoderami pseudo-losowy przeplotnik bitów permutuje sekwencję informacyjną. Zapewnia to, że dwa słowa kodowe mają różne rozkłady wag dla tych samych informacji.

3

Zakodowane bity (systematyczne i parzystościowe z obu enkoderów) są przesyłane przez kanał, zniekształcone przez szum.

4

Na odbiorniku dekodery typu soft-input soft-output (SISO) iterują: dekoder 1 wykorzystuje odebrany sygnał i informację zewnętrzną z dekodera 2 do udoskonalenia swojej estymacji. Dekoder 2 robi to samo. De-interleaver/interleaver przekazuje informacje między dekoderami.

5

Po ustalonej liczbie iteracji (np. 8-20) podejmowana jest ostateczna twarda decyzja poprzez progowanie ilorazu wiarygodności. Zbieżność można śledzić za pomocą „turbo zbocza”: wydajność gwałtownie spada, gdy SNR przekroczy próg, przy którym rozpoczyna się iteracja zbieżna.

Częste pułapki

  • Użycie deterministycznego lub zbyt krótkiego przeplotnika; pseudo-losowość jest niezbędna dla zysku iteracyjnego
  • Zakładanie, że stała liczba iteracji jest optymalna; wydajność zależy od SNR; adaptacyjna liczba iteracji jest lepsza
  • Nieuwzględnianie podłogi błędów; kody turbo mogą wykazywać próg (turbo zbocze), poniżej którego wydajność gwałtownie spada
  • Stosowanie kodów turbo do bardzo krótkich bloków informacyjnych (<100 bitów); względny narzut staje się zaporowy
  • Nie uwzględnianie opóźnienia sprzężenia zwrotnego w dekodowaniu iteracyjnym; wymagane jest spójne taktowanie między dekoderami

Najczęściej zadawane pytania

Co oznacza „turbo” w kodach turbo?

Nazwa odnosi się do iteracyjnego procesu dekodowania przypominającego silnik turbo: każdy dekoder „doładowuje” sygnał dla następnego dekodera. Wykładniczy zysk wydajności na iterację jest czasami nazywany efektem turbo. Nie jest on dosłownie związany z turbosprężarkami.

Dlaczego przeplotnik jest tak ważny?

Przeplotnik łamie korelacje w schematach błędów z pierwszego dekodera, zanim zobaczy je drugi dekoder. Bez niego oba dekodery powtarzałyby te same błędy. Dobry przeplotnik zapewnia, że błędy z jednego dekodera są losowo rozproszone, dając drugiemu dekoderowi świeżą perspektywę i umożliwiając produktywną iterację.

Co to jest turbo zbocze?

Kody turbo wykazują ostry próg: poniżej krytycznego SNR dekodowanie iteracyjne nie zbiega, a BER jest słaby. Powyżej progu BER gwałtownie spada. Jest to turbo zbocze. W projektowaniu systemu SNR musi być bezpiecznie powyżej zbocza; działanie tuż poniżej powoduje katastrofalną awarię, mimo pozornego SNR.

Ile iteracji jest potrzebnych?

Typowe dekodery turbo używają 8-20 iteracji; więcej iteracji poprawia wydajność, ale zwiększa opóźnienie. Przy wysokim SNR wystarczy kilka iteracji (zbieżność jest szybka). Przy niskim SNR potrzeba więcej iteracji. Adaptacyjna liczba iteracji (sprawdź zbieżność, zakończ wcześnie, jeśli zakończono) równoważy opóźnienie i wydajność.

Pokrewne metody

Źródła

  1. Berrou, C., Glavieux, A., & Thitimajshima, P. (1993). Near Shannon limit error-correcting coding and decoding: Turbo-codes. In Proceedings of the IEEE International Conference on Communications (ICC), 1064-1070.

    Otwórz odnośnik DOI
    Skopiowano.
  2. Richardson, T. J., & Urbanke, R. L. (2002). The capacity of low-density parity-check codes under message-passing decoding. IEEE Transactions on Information Theory, 47(2), 599-618.

    Otwórz odnośnik DOI
    Skopiowano.