Teoria kodowania - Coding theory

Teoria kodowania to nauka o właściwościach kodów i ich przydatności do określonych zastosowań. Kody są wykorzystywane do kompresji danych , kryptografii , wykrywania i korekcji błędów , transmisji i przechowywania danych . Kody są badane przez różne dyscypliny naukowe — takie jak teoria informacji , elektrotechnika , matematyka , językoznawstwo i informatyka — w celu projektowania wydajnych i niezawodnych metod transmisji danych . Zwykle wiąże się to z usunięciem nadmiarowości i korektą lub wykryciem błędów w przesyłanych danych.

Istnieją cztery rodzaje kodowania:

1. Kompresja danych (lub kodowanie źródłowe )
2. Kontrola błędów (lub kodowanie kanałów )
3. Kodowanie kryptograficzne
4. Kodowanie linii

Kompresja danych próbuje usunąć nadmiarowość danych ze źródła w celu ich bardziej wydajnej transmisji. Na przykład kompresja danych ZIP zmniejsza pliki danych w celu zmniejszenia ruchu internetowego. Kompresja danych i korekcja błędów mogą być badane łącznie .

Korekcja błędów dodaje dodatkowe bity danych, aby transmisja danych była bardziej odporna na zakłócenia występujące w kanale transmisyjnym. Zwykły użytkownik może nie wiedzieć, że wiele aplikacji korzysta z korekcji błędów. Typowa muzyczna płyta CD (CD) wykorzystuje kod Reed-Solomon do korekcji zarysowań i kurzu. W tej aplikacji kanałem transmisji jest sama płyta CD. Telefony komórkowe wykorzystują również techniki kodowania, aby skorygować blaknięcie i szum transmisji radiowej o wysokiej częstotliwości. Modemy danych, transmisje telefoniczne i NASA Deep Space Network wykorzystują techniki kodowania kanałów, aby przepuścić bity, na przykład kod turbo i kody LDPC .

Historia teorii kodowania

W 1948 roku Claude Shannon opublikował „ A Mathematical Theory of Communication ”, artykuł w dwóch częściach w lipcowym i październikowym wydaniu Bell System Technical Journal . Praca ta skupia się na problemie, jak najlepiej zakodować informacje, które nadawca chce przekazać. W tej fundamentalnej pracy wykorzystał narzędzia teorii prawdopodobieństwa opracowane przez Norberta Wienera , które znajdowały się wówczas na początkowym etapie zastosowania w teorii komunikacji. Shannon rozwinął entropię informacyjną jako miarę niepewności w wiadomości, jednocześnie wymyślając dziedzinę teorii informacji .

Kod binarny Golaya został opracowany w 1949 roku. Jest to kod korygujący błędy, zdolny do skorygowania do trzech błędów w każdym 24-bitowym słowie i wykrycia czwartego.

Richard Hamming zdobył nagrodę Turinga w 1968 roku za pracę w Bell Labs w zakresie metod numerycznych, automatycznych systemów kodowania oraz kodów wykrywania i korygowania błędów. Wymyślił koncepcje zwane kody Hamminga , okna Hamminga , numery Hamminga i Hamminga odległości .

W 1972 roku Nasir Ahmed zaproponował dyskretną transformatę kosinusową (DCT), którą opracował wraz z T. Natarajanem i KR Rao w 1973 roku. DCT jest najczęściej używanym algorytmem kompresji stratnej , będącym podstawą formatów multimedialnych, takich jak JPEG , MPEG i MP3 .

Kodowanie źródłowe

Celem kodowania źródłowego jest pomniejszenie danych źródłowych.

Definicja

Dane mogą być postrzegane jako zmienna losowa , gdzie pojawia się z prawdopodobieństwem . ${\ Displaystyle X: \ Omega \ do {\ Matematyka {X}}}$${\displaystyle x\in {\mathcal {X}}}$${\ Displaystyle \ mathbb {P} [X = x]}$

Dane są kodowane ciągami (słowami) w alfabecie . ${\ Displaystyle \ Sigma}$

Kod to funkcja

${\ Displaystyle C: {\ mathcal {X}} \ do \ Sigma ^ {*}}$(lub jeśli pusty ciąg nie jest częścią alfabetu).${\ Displaystyle \ Sigma ^ {+}}$

${\ Displaystyle C (x)}$to słowo kodowe powiązane z . ${\displaystyle x}$

Długość słowa kodowego jest zapisana jako

${\displaystyle l(C(x)).}$

Oczekiwana długość kodu to

${\ Displaystyle l (C) = \ suma _ {x \ w {\ mathcal {X}}} l (C (x)) \ mathbb {P} [X = x].}$

Konkatenacja słów kodowych . ${\ Displaystyle C (x_ {1}, \ ldots, x_ {k}) = C (x_ {1}) C (x_ {2}) \ cdots C (x_ {k})}$

Słowo kodowe pustego ciągu jest samym pustym ciągiem:

${\ Displaystyle C (\ epsilon ) = \ epsilon }$

Nieruchomości

1. ${\ Displaystyle C: {\ mathcal {X}} \ do \ Sigma ^ {*}}$nie jest liczbą pojedynczą, jeśli jest iniektywna .
2. ${\ Displaystyle C: {\ mathcal {X}} ^ {*} \ do \ Sigma ^ {*}}$jest jednoznacznie dekodowany, jeśli jest iniekcyjny.
3. ${\ Displaystyle C: {\ mathcal {X}} \ do \ Sigma ^ {*}}$jest natychmiastowe, jeśli nie jest przedrostkiem (i odwrotnie).${\displaystyle C(x_{1})}$${\displaystyle C(x_{2})}$

Zasada

Entropia źródła jest miarą informacji. Zasadniczo kody źródłowe próbują zredukować nadmiarowość obecną w źródle i reprezentują źródło z mniejszą liczbą bitów, które przenoszą więcej informacji.

Kompresja danych, która jawnie próbuje zminimalizować średnią długość wiadomości zgodnie z określonym przyjętym modelem prawdopodobieństwa, nazywana jest kodowaniem entropijnym .

Różne techniki stosowane przez schematy kodowania źródłowego próbują osiągnąć granicę entropii źródła. C ( x ) ≥ H ( x ), gdzie H ( x ) to entropia źródła (bitrate), a C ( x ) to bitrate po kompresji. W szczególności żaden schemat kodowania źródła nie może być lepszy niż entropia źródła.

Przykład

Transmisja faksowa wykorzystuje prosty kod długości przebiegu . Kodowanie źródła usuwa wszystkie dane zbędne dla potrzeb nadajnika, zmniejszając przepustowość wymaganą do transmisji.

Kodowanie kanałów

Celem teorii kodowania kanałów jest znalezienie kodów, które szybko się transmitują, zawierają wiele ważnych słów kodowych i mogą poprawić lub przynajmniej wykryć wiele błędów. Chociaż nie wykluczają się wzajemnie, wydajność w tych obszarach jest kompromisem. Tak więc różne kody są optymalne dla różnych zastosowań. Potrzebne właściwości tego kodu zależą głównie od prawdopodobieństwa wystąpienia błędów podczas transmisji. W typowej płycie CD uszkodzeniem jest głównie kurz lub zarysowania.

Płyty CD wykorzystują przeplatane kodowanie Reed-Solomon, aby rozłożyć dane na dysku.

Chociaż nie jest to bardzo dobry kod, prosty powtarzający się kod może służyć jako zrozumiały przykład. Załóżmy, że bierzemy blok bitów danych (reprezentujących dźwięk) i wysyłamy go trzy razy. Przy odbiorniku zbadamy trzy powtórzenia krok po kroku i podejmiemy głosowanie większościowe. Skręt polega na tym, że nie tylko wysyłamy bity w porządku. Przeplatamy je. Blok bitów danych jest najpierw podzielony na 4 mniejsze bloki. Następnie przechodzimy przez blok i wysyłamy jeden bit od pierwszego, potem drugi itd. Odbywa się to trzy razy, aby rozłożyć dane na powierzchni dysku. W kontekście prostego powtarzającego się kodu może to nie wydawać się skuteczne. Jednakże, znane są kody o większej mocy, które są bardzo skuteczne w korygowaniu błędu „wybuchowego” zadrapania lub drobinek kurzu, gdy stosowana jest ta technika przeplatania.

Inne kody są bardziej odpowiednie dla różnych zastosowań. Komunikacja w przestrzeni kosmicznej jest ograniczona przez szum termiczny odbiornika, który ma charakter bardziej ciągły niż impulsowy. Podobnie modemy wąskopasmowe są ograniczone przez szum, występujący w sieci telefonicznej, a także lepiej modelowane jako ciągłe zakłócenia. Telefony komórkowe ulegają szybkiemu wyblaknięciu . Zastosowane wysokie częstotliwości mogą powodować szybkie zanikanie sygnału, nawet jeśli odbiornik zostanie przesunięty o kilka cali. Znowu istnieje klasa kodów kanałów, które mają na celu walkę z blaknięciem.

Kody liniowe

Termin algebraiczna teoria kodowania oznacza poddziedzinę teorii kodowania, w której właściwości kodów są wyrażane w terminach algebraicznych, a następnie dalej badane.

Teoria kodowania algebraicznego jest zasadniczo podzielona na dwa główne typy kodów:

• Liniowe kody blokowe
• Kody splotowe

Analizuje następujące trzy właściwości kodu – głównie:

• Długość słowa kodowego
• Całkowita liczba poprawnych słów kodowych
• Minimalna odległość między dwoma poprawnymi słowami kodowymi, wykorzystująca głównie odległość Hamminga , czasami także inne odległości, takie jak odległość Lee

Liniowe kody blokowe

Liniowe kody blokowe mają właściwość liniowości , tzn. suma dowolnych dwóch słów kodowych jest również słowem kodowym i są one stosowane do bitów źródłowych w blokach, stąd nazwa liniowe kody blokowe. Istnieją kody blokowe, które nie są liniowe, ale bez tej właściwości trudno jest udowodnić, że kod jest dobry.

Liniowe kody blokowe są podsumowane za pomocą ich alfabetów symboli (np. binarnych lub trójskładnikowych) i parametrów ( n , m , d _min ) gdzie

1. n to długość słowa kodowego, w symbolach,
2. m to liczba symboli źródłowych, które zostaną użyte do kodowania jednocześnie,
3. d _min to minimalna odległość Hamminga dla kodu.

Istnieje wiele rodzajów liniowych kodów blokowych, takich jak

1. Kody cykliczne (np. kody Hamminga )
2. Kody powtórzeń
3. Kody parzystości
4. Kody wielomianowe (np. kody BCH )
5. Kody Reeda-Salomona
6. Algebraiczne kody geometryczne
7. Kody Reeda-Mullera
8. Idealne kody

Kody blokowe są powiązane z problemem pakowania kulek , któremu poświęcono od lat pewną uwagę. W dwóch wymiarach łatwo to sobie wyobrazić. Weź kilka groszy płasko na stole i złóż je razem. Rezultatem jest sześciokątny wzór przypominający gniazdo pszczół. Ale kody blokowe opierają się na większej liczbie wymiarów, których nie można łatwo zwizualizować. Potężny (24,12) kod Golaya używany w komunikacji kosmicznej wykorzystuje 24 wymiary. Jeśli jest używany jako kod binarny (co zwykle jest), wymiary odnoszą się do długości słowa kodowego, jak zdefiniowano powyżej.

Teoria kodowania wykorzystuje N- wymiarowy model sfery. Na przykład, ile groszy można zapakować w okrąg na blacie lub w 3 wymiarach, ile kulek można zapakować w globus. Inne względy dotyczą wyboru kodu. Na przykład upakowanie sześciokątne w wiązanie prostokątnego pudełka pozostawi pustą przestrzeń w rogach. Wraz ze wzrostem wymiarów zmniejsza się procent pustej przestrzeni. Ale przy pewnych wymiarach opakowanie zajmuje całą przestrzeń, a te kody są tak zwanymi kodami „doskonałymi”. Jedynymi nietrywialnymi i użytecznymi kodami doskonałymi są kody Hamminga odległości-3 o parametrach spełniających parametry (2 ^r – 1, 2 ^r – 1 – r , 3) oraz binarne [23,12,7] i [11,6,5] ] trójskładnikowe kody Golaya.

Inną właściwością kodu jest liczba sąsiadów, które może mieć pojedyncze słowo kodowe. Ponownie rozważmy grosze jako przykład. Najpierw pakujemy grosze w prostokątną siatkę. Każdy grosz będzie miał 4 w pobliżu sąsiadów (i 4 na rogach, które są dalej). W sześciokącie każdy grosz będzie miał 6 w pobliżu sąsiadów. Gdy zwiększamy wymiary, liczba pobliskich sąsiadów rośnie bardzo szybko. W rezultacie rośnie również liczba sposobów, w jakie szum skłoni odbiornik do wyboru sąsiada (stąd błąd). Jest to podstawowe ograniczenie kodów blokowych, a właściwie wszystkich kodów. Wywołanie błędu u jednego sąsiada może być trudniejsze, ale liczba sąsiadów może być wystarczająco duża, aby w rzeczywistości ucierpiało całkowite prawdopodobieństwo błędu.

Właściwości liniowych kodów blokowych są wykorzystywane w wielu aplikacjach. Na przykład właściwość unikalności syndromu-kosetu liniowych kodów blokowych jest wykorzystywana w kształtowaniu kraty, jednym z najbardziej znanych kodów kształtowania .

Kody splotowe

Ideą kodu splotowego jest sprawienie, aby każdy symbol słowa kodowego był sumą ważoną różnych symboli komunikatów wejściowych. Przypomina to splot używany w systemach LTI w celu znalezienia wyjścia systemu, gdy znasz wejście i odpowiedź impulsową.

Tak więc zazwyczaj znajdujemy wyjście systemowego kodera splotowego, które jest splotem bitu wejściowego, w stosunku do stanów rejestrów kodera splotowego.

Zasadniczo kody splotowe nie zapewniają lepszej ochrony przed szumem niż równoważny kod blokowy. W wielu przypadkach oferują one na ogół większą prostotę implementacji w porównaniu z kodem blokowym o równej mocy. Koder jest zwykle prostym układem, który ma pamięć stanów i pewną logikę sprzężenia zwrotnego, zwykle bramki XOR . Dekoder może być zaimplementowany w oprogramowaniu lub firmware.

Algorytm Viterbiego jest optymalny algorytm stosowany do dekodowania kodów splotowych. Istnieją uproszczenia mające na celu zmniejszenie obciążenia obliczeniowego. Polegają na wyszukiwaniu tylko najbardziej prawdopodobnych ścieżek. Chociaż nie są one optymalne, ogólnie stwierdzono, że dają dobre wyniki w środowiskach o niskim poziomie hałasu.

Kody splotowe stosowane są w modemach głosowych (V.32, V.17, V.34) oraz w telefonach komórkowych GSM, a także w urządzeniach łączności satelitarnej i wojskowej.

Kodowanie kryptograficzne

Kryptografia lub kodowanie kryptograficzne to praktyka i nauka technik bezpiecznej komunikacji w obecności osób trzecich (tzw. adwersarzy ). Mówiąc ogólniej, chodzi o konstruowanie i analizowanie protokołów, które blokują przeciwników; różne aspekty bezpieczeństwa informacji , takich jak dane dotyczące poufności , integralności danych , uwierzytelniania i niezaprzeczalności są kluczowe dla współczesnej kryptografii. Współczesna kryptografia istnieje na przecięciu dyscyplin matematyki , informatyki i elektrotechniki . Zastosowania kryptografii obejmują karty bankomatowe , hasła komputerowe i handel elektroniczny .

Kryptografia sprzed ery nowożytnej była praktycznie synonimem szyfrowania , konwersji informacji ze stanu czytelnego do pozornego nonsensu . Twórca zaszyfrowanej wiadomości udostępnił technikę dekodowania potrzebną do odzyskania oryginalnych informacji tylko zamierzonym odbiorcom, uniemożliwiając tym samym niechcianym osobom zrobienie tego samego. Od czasu I wojny światowej i pojawienia się komputera metody wykorzystywane do prowadzenia kryptologii stały się coraz bardziej złożone, a ich zastosowanie coraz powszechniejsze.

Współczesna kryptografia jest mocno oparta na teorii matematycznej i praktyce informatycznej; Algorytmy kryptograficzne są zaprojektowane w oparciu o założenia dotyczące twardości obliczeniowej , co sprawia, że ​​takie algorytmy są trudne do złamania w praktyce przez każdego przeciwnika. Teoretycznie możliwe jest złamanie takiego systemu, ale jest to niewykonalne w jakikolwiek znany praktyczny sposób. Schematy te są zatem określane jako bezpieczne obliczeniowo; postępy teoretyczne, np. udoskonalenia algorytmów faktoryzacji liczb całkowitych , oraz szybsze technologie obliczeniowe wymagają ciągłego dostosowywania tych rozwiązań. Istnieją teoretycznie bezpieczne schematy, których nie da się złamać nawet przy nieograniczonej mocy obliczeniowej – przykładem jest jednorazowy pad – ale te schematy są trudniejsze do wdrożenia niż najlepsze teoretycznie możliwe do złamania, ale obliczeniowo bezpieczne mechanizmy.

Kodowanie linii

Kod linii (zwany także cyfrowej modulacji pasma lub metody cyfrowej transmisji pasma podstawowego) jest kod wybierane do użycia w ramach systemu komunikacyjnego dla pasma przenoszenia celów. Kodowanie linii jest często używane do cyfrowego przesyłania danych.

Kodowanie liniowe polega na reprezentowaniu sygnału cyfrowego, który ma być transportowany, przez sygnał dyskretny amplitudowo i czasowo, który jest optymalnie dostrojony do określonych właściwości kanału fizycznego (i sprzętu odbiorczego). Fali wzór napięcia lub prądu używany do reprezentowania 1 i 0 z ciągu danych cyfrowych na łącza transmisyjnego jest nazywany kodowanie linii . Popularne typy kodowania linii to kodowanie unipolarne , polarne , bipolarne i Manchester .

Inne zastosowania teorii kodowania

Innym problemem teorii kodowania jest projektowanie kodów, które pomagają w synchronizacji . Kod można zaprojektować tak, aby przesunięcie fazowe można było łatwo wykryć i skorygować oraz aby wiele sygnałów mogło być wysyłanych w tym samym kanale.

Innym zastosowaniem kodów, stosowanym w niektórych systemach telefonii komórkowej, jest wielokrotny dostęp z podziałem kodów (CDMA). Każdy telefon ma przypisaną sekwencję kodów, która jest w przybliżeniu nieskorelowana z kodami innych telefonów. Podczas transmisji słowo kodowe jest używane do modulowania bitów danych reprezentujących wiadomość głosową. W odbiorniku wykonywany jest proces demodulacji w celu odzyskania danych. Właściwości tej klasy kodów pozwalają wielu użytkownikom (posiadającym różne kody) korzystać z tego samego kanału radiowego w tym samym czasie. Dla odbiornika sygnały innych użytkowników będą widoczne dla demodulatora tylko jako szum o niskim poziomie.

Inną ogólną klasą kodów są kody automatycznego żądania powtórzenia (ARQ). W tych kodach nadawca dodaje nadmiarowość do każdej wiadomości w celu sprawdzenia błędów, zwykle przez dodanie bitów kontrolnych. Jeśli bity kontrolne nie są zgodne z resztą wiadomości po jej nadejściu, odbiorca poprosi nadawcę o retransmisję wiadomości. Wszystkie oprócz najprostszych protokołów sieci rozległych używają ARQ. Popularne protokoły to SDLC (IBM), TCP (Internet), X.25 (International) i wiele innych. Istnieje szerokie pole badań na ten temat ze względu na problem dopasowania odrzuconego pakietu do nowego pakietu. Czy jest to nowy czy retransmisja? Zazwyczaj używane są schematy numeracji, jak w TCP. „RFC793” . RFC . Grupa Robocza ds. Inżynierii Internetu (IETF). Wrzesień 1981.

Testy grupowe

Testowanie grupowe wykorzystuje kody w inny sposób. Rozważ dużą grupę elementów, w których bardzo niewiele różni się w określony sposób (np. wadliwe produkty lub zainfekowane osoby testowe). Ideą testowania grupowego jest określenie, które elementy są „różne” przy użyciu jak najmniejszej liczby testów. Geneza problemu ma swoje korzenie w II wojnie światowej, kiedy Siły Powietrzne Armii Stanów Zjednoczonych musiały przetestować swoich żołnierzy na syfilis .

Kodowanie analogowe

Informacje te są kodowane w analogiczny sposób do sieci neuronowe w mózgu w przetwarzaniu sygnału analogowego i elektroniki analogowych . Aspekty kodowania analogowego obejmują analogową korekcję błędów, analogową kompresję danych i analogowe szyfrowanie.

Kodowanie neuronowe

Neural kodowania jest neuroscience dotyczy sposobu sensorycznej i inne informacje są reprezentowane w pole związane z modelem mózgu przez sieci z neuronów . Głównym celem badania kodowania neuronowego jest scharakteryzowanie związku między bodźcem a indywidualnymi lub zespołowymi reakcjami neuronów oraz związku między aktywnością elektryczną neuronów w zespole. Uważa się, że neurony mogą kodować zarówno informacje cyfrowe, jak i analogowe , i że neurony przestrzegają zasad teorii informacji i kompresują informacje oraz wykrywają i korygują błędy w sygnałach wysyłanych przez mózg i szerszy układ nerwowy.

Zobacz też

• Wzmocnienie kodowania
• Kod pokrywający
• Kod korekcji błędów
• Składany Reed – kod Salomona
• Testy grupowe
• Odległość Hamminga , waga Hamminga
• Odległość Lee
• Lista tematów teorii kodowania algebraicznego
• Kodowanie przestrzenne i MIMO w badaniach wielu anten
  • Kodowanie dywersyfikacji przestrzennej to kodowanie przestrzenne, które przesyła repliki sygnału informacyjnego wzdłuż różnych ścieżek przestrzennych, aby zwiększyć niezawodność transmisji danych.
  • Kodowanie eliminacji zakłóceń przestrzennych
  • Przestrzenne kodowanie multipleksowe
• Oś czasu teorii informacji, kompresji danych i kodów korekcji błędów

Uwagi

Bibliografia

• Elwyn R. Berlekamp (2014), Algebraic Coding Theory , World Scientific Publishing (wydanie poprawione), ISBN  978-9-81463-589-9 .
• MacKay, David JC . Teoria informacji, wnioskowanie i algorytmy uczenia Cambridge: Cambridge University Press, 2003. ISBN  0-521-64298-1
• Vera Pless (1982), Wprowadzenie do teorii kodów korekcji błędów , John Wiley & Sons, Inc., ISBN  0-471-08684-3 .
• Randy Yates, samouczek dotyczący teorii kodowania .