Twierdzenie o kodowaniu zaszumionego kanału - Noisy-channel coding theorem

W teorii informacji The Noisy-kanałowy twierdzenie kodowania (czasami twierdzenie Shannona lub ograniczenie Shannon ), stanowi, że dla danego stopnia zanieczyszczenia hałasem kanału komunikacyjnego , jest możliwe do przekazywania danych dyskretnych (cyfrowych informacji ) niemal bezbłędną nawet do obliczalna maksymalna prędkość w kanale. Ten wynik został przedstawiony przez Claude'a Shannona w 1948 roku i był częściowo oparty na wcześniejszych pracach i pomysłach Harry'ego Nyquista i Ralpha Hartleya .

Granicy Shannona lub pojemności Shannona kanału komunikacyjnego odnosi się do maksymalnej szybkości danych bezbłędnych teoretycznie możliwe przesyłane w kanale, jeśli link jest podatne na błędy losowe transmisji danych dla danego poziomu hałasu. Została po raz pierwszy opisana przez Shannona (1948), a wkrótce potem opublikowana w książce Shannona i Warrena Weavera zatytułowanej The Mathematical Theory of Communication (1949). To stworzyło nowoczesną dyscyplinę teorii informacji .

Przegląd

Twierdzenie to, sformułowane przez Claude'a Shannona w 1948 roku, opisuje maksymalną możliwą skuteczność metod korekcji błędów w porównaniu z poziomami zakłóceń i uszkodzenia danych. Twierdzenie Shannona ma szerokie zastosowanie zarówno w komunikacji, jak i przechowywaniu danych . Twierdzenie to ma fundamentalne znaczenie dla współczesnej dziedziny teorii informacji . Shannon przedstawił jedynie zarys dowodu. Pierwszy rygorystyczny dowód na dyskretny przypadek pochodzi od Amiela Feinsteina w 1954 roku.

Twierdzenie Shannona mówi, że biorąc pod uwagę zaszumiony kanał o pojemności kanału C i informacje przesyłane z szybkością R , to jeśli istnieją kody, które pozwalają na dowolnie małe prawdopodobieństwo błędu w odbiorniku. Oznacza to, że teoretycznie możliwe jest przesyłanie informacji prawie bez błędów z dowolną szybkością poniżej szybkości granicznej C .

Odwrotność też jest ważna. Jeżeli , arbitralnie małe prawdopodobieństwo błędu nie jest osiągalne. Wszystkie kody będą miały prawdopodobieństwo błędu większe niż pewien dodatni poziom minimalny, a poziom ten wzrasta wraz ze wzrostem szybkości. Dlatego nie można zagwarantować, że informacje będą przesyłane niezawodnie przez kanał z szybkościami przekraczającymi pojemność kanału. Twierdzenie nie odnosi się do rzadkiej sytuacji, w której szybkość i pojemność są równe.

Pojemność kanału można obliczyć na podstawie fizycznych właściwości kanału; dla kanału o ograniczonym paśmie z szumem Gaussa, przy użyciu twierdzenia Shannona-Hartleya .

Proste schematy, takie jak „wyślij wiadomość 3 razy i użyj najlepszego schematu głosowania 2 z 3, jeśli kopie się różnią” są nieefektywnymi metodami korekcji błędów, niezdolnymi do asymptotycznie zagwarantowania, że ​​blok danych może zostać przesłany bez błędów. Zaawansowane techniki, takie jak kody Reeda-Solomona , a ostatnio kody kontroli parzystości o niskiej gęstości (LDPC) i kody turbo , znacznie zbliżają się do osiągnięcia teoretycznej granicy Shannona, ale kosztem dużej złożoności obliczeniowej. Używając tych wysoce wydajnych kodów i mocy obliczeniowej dzisiejszych cyfrowych procesorów sygnałowych , możliwe jest obecnie osiągnięcie bardzo bliskiej granicy Shannona. W rzeczywistości wykazano, że kody LDPC mogą osiągnąć 0,0045 dB limitu Shannona (dla kanałów binarnych z dodatkiem białego szumu Gaussa (AWGN) o bardzo długich blokach).

Stwierdzenie matematyczne

Podstawowy model matematyczny systemu komunikacyjnego jest następujący:

Wiadomość W jest przenoszona przez hałaśliwym kanału za pomocą funkcji kodowania i dekodowania. Koder odwzorowuje W we wstępnie określonej kolejności symboli kanału o długości n . W najbardziej podstawowym modelu kanał zniekształca każdy z tych symboli niezależnie od pozostałych. Wyjście kanału – odebrana sekwencja – jest wprowadzane do dekodera, który odwzorowuje sekwencję na oszacowanie wiadomości. W tym ustawieniu prawdopodobieństwo błędu definiuje się jako:

Twierdzenie (Shannon, 1948):

1. Dla każdego dyskretnego kanału bezpamięciowego pojemność kanału jest określana na podstawie wzajemnych informacji ,
ma następującą właściwość. Dla każdego i , dla wystarczająco dużego , istnieje kod o długości i szybkości oraz algorytm dekodowania, taki, że maksymalne prawdopodobieństwo błędu bloku wynosi .
2. Jeśli prawdopodobieństwo błędu bitowego jest akceptowalne, osiągalne są stawki do , gdzie
i jest funkcją entropii binarnej
3. Dla każdego stawki wyższe niż nieosiągalne.

(MacKay (2003), s. 162; por. Gallager (1968), rozdz. 5; Cover i Thomas (1991), s. 198; Shannon (1948) thm. 11)

Zarys dowodu

Podobnie jak w przypadku kilku innych ważnych wyników w teorii informacji, dowód twierdzenia o zaszumionym kodowaniu kanału obejmuje wynik osiągalności i odwrotny wynik dopasowania. Te dwa składniki służą do ograniczenia, w tym przypadku, zestawu możliwych szybkości, z jakimi można komunikować się przez zaszumiony kanał, a dopasowanie służy do pokazania, że ​​te granice są wąskimi granicami.

Poniższe szkice to tylko jeden zestaw wielu różnych stylów dostępnych do studiowania w tekstach teorii informacji.

Osiągalność dla dyskretnych kanałów bez pamięci

Ten szczególny dowód osiągalności jest zgodny ze stylem dowodów, które wykorzystują asymptotyczną własność ekwipartycji (AEP). Inny styl można znaleźć w tekstach teorii informacji wykorzystujących wykładniki błędów .

Oba typy dowodów wykorzystują losowy argument kodowania, w którym książka kodów używana w kanale jest konstruowana w sposób losowy - służy to uproszczeniu analizy, jednocześnie udowadniając istnienie kodu spełniającego pożądane niskie prawdopodobieństwo błędu przy dowolnej szybkości danych poniżej pojemność kanału .

Za pomocą argumentu związanego z AEP, przy danym kanale, ciągach długości symboli źródłowych i ciągach długości wyjść kanału , możemy zdefiniować wspólny typowy zestaw w następujący sposób:

Mówimy, że dwie sekwencje i są wspólnie typowe, jeśli leżą w zdefiniowanym powyżej zbiorze wspólnie typowym.

Kroki

  1. W stylu argumentu random coding generujemy losowo słowa kodowe o długości n z rozkładu prawdopodobieństwa Q.
  2. Ten kod jest ujawniany nadawcy i odbiorcy. Zakłada się również, że znana jest macierz przejścia dla używanego kanału.
  3. Komunikat W jest wybierany zgodnie z równomiernym rozkładem na zbiorze słów kodowych. To znaczy .
  4. Wiadomość W jest wysyłana przez kanał.
  5. Odbiornik odbiera sekwencję zgodnie z
  6. Przesyłając te słowa kodowe przez kanał, otrzymujemy i dekodujemy do jakiejś sekwencji źródłowej, jeśli istnieje dokładnie jedno słowo kodowe, które jest wspólne dla Y. Jeśli nie ma wspólnie typowych słów kodowych lub jeśli jest więcej niż jedno, deklarowany jest błąd. Błąd występuje również wtedy, gdy odkodowane słowo kodowe nie jest zgodne z oryginalnym słowem kodowym. Nazywa się to typowym dekodowaniem zestawu .

Prawdopodobieństwo błędu tego schematu dzieli się na dwie części:

  1. Po pierwsze, błąd może wystąpić, jeśli nie zostaną znalezione łącznie typowe sekwencje X dla odebranej sekwencji Y
  2. Po drugie, błąd może wystąpić, jeśli nieprawidłowa sekwencja X jest typowa łącznie z odebraną sekwencją Y.
  • Przez losowość konstrukcji kodu możemy założyć, że średnie prawdopodobieństwo błędu uśrednione dla wszystkich kodów nie zależy od przesłanego indeksu. Zatem bez utraty ogólności możemy założyć W = 1.
  • Ze wspólnego AEP wiemy, że prawdopodobieństwo, że nie istnieje wspólny typowy X, spada do 0, gdy n rośnie. Możemy ograniczyć to prawdopodobieństwo błędu przez .
  • Również ze wspólnego AEP znamy prawdopodobieństwo, że konkret i wynik z W = 1 są łącznie typowe, wynosi .

Definiować:

jako zdarzenie, w którym wiadomość i jest łącznie typowa z sekwencją otrzymaną podczas wysyłania wiadomości 1.

Możemy zaobserwować, że jak idzie do nieskończoności, jeśli dla kanału prawdopodobieństwo błędu spadnie do 0.

Wreszcie, biorąc pod uwagę, że przeciętna książka kodów jest „dobra”, wiemy, że istnieje książka kodów, której wydajność jest lepsza niż średnia, a zatem spełnia naszą potrzebę arbitralnie niskiego prawdopodobieństwa błędu w komunikacji w zaszumionym kanale.

Słaba zwrotka dla dyskretnych kanałów bez pamięci

Załóżmy kod słów kodowych. Niech W będzie narysowany jednolicie nad tym zbiorem jako indeks. Niech i będą odpowiednio transmitowanymi słowami kodowymi i odebranymi słowami kodowymi.

  1. używanie tożsamości zawierających entropię i wzajemną informację
  2. ponieważ X jest funkcją W
  3. przez wykorzystanie nierówności Fano
  4. przez fakt, że pojemność jest zmaksymalizowana wzajemna informacja.

Rezultatem tych kroków jest to, że . Gdy długość bloku zbliża się do nieskończoności, otrzymujemy wartość od 10, jeśli R jest większe niż C - możemy uzyskać arbitralnie niski poziom błędu tylko wtedy, gdy R jest mniejsze niż C.

Silna konwersja dla dyskretnych kanałów bez pamięci

Silne twierdzenie odwrotne, udowodnione przez Wolfowitza w 1957 roku, stwierdza, że:

dla pewnej skończonej dodatniej stałej . Podczas gdy słaba odwrotność stwierdza, że ​​prawdopodobieństwo błędu jest ograniczone od zera aż do nieskończoności, silna odwrotność stwierdza, że ​​błąd dochodzi do 1. Jest to więc ostry próg między doskonale niezawodną a całkowicie zawodną komunikacją.

Twierdzenie o kodowaniu kanałów dla niestacjonarnych kanałów bez pamięci

Zakładamy, że kanał jest bezpamięciowy, ale prawdopodobieństwa jego przejścia zmieniają się w czasie w sposób znany zarówno przez nadajnik, jak i odbiornik.

Wtedy pojemność kanału jest podawana przez

Maksimum jest osiągane przy przepustowości osiągającej dystrybucje dla każdego kanału. To znaczy, gdzie jest pojemność i- tego kanału.

Zarys dowodu

Dowód przebiega prawie tak samo, jak twierdzenie o kodowaniu kanałów. Osiągalność wynika z losowego kodowania z każdym symbolem wybranym losowo z przepustowości osiągającej dystrybucję dla tego konkretnego kanału. Argumenty typowości wykorzystują definicję typowych zbiorów dla źródeł niestacjonarnych określonych w artykule dotyczącym asymptotycznej ekwipartycji .

Techniczność lim inf wchodzi w grę, gdy nie są zbieżne.

Szybkość kodowania kanału w reżimie o skończonej długości bloku

Teoria informacji o skończonej długości bloku bada maksymalną szybkość kodowania kanału osiągalną przy danej długości bloku i prawdopodobieństwo błędu w reżimie skończonej długości bloku (reżim nieasymptotyczny). Maksymalne osiągalne kanał kodowania szybkość z prawdopodobieństwem błędu danego bloku i długości bloku (dla binarnej hałasu Dodatek biały Gaussa (AWGN) kanałów, z krótkich odcinków blokowych), ściśle przybliżona przez Polyanskiy , ubogich i Verdu (PPV) w 2010 roku, jest podana przez

gdzie jest odwrotnością komplementarnej funkcji skumulowanego rozkładu Gaussa , jest pojemnością kanału i jest cechą kanału określaną jako dyspersja kanału.

Zobacz też


Uwagi

Bibliografia

Linki zewnętrzne