Kod blokowy - Block code

W teorii kodowania , kody blokowe duża i ważna rodzina kodów korekcji błędów , które kodują dane w blokach. Istnieje wiele przykładów kodów blokowych, z których wiele ma szeroki zakres praktycznych zastosowań. Abstrakcyjna definicja kodów blokowych jest koncepcyjnie przydatna, ponieważ umożliwia teoretykom kodowania, matematykom i informatykom badanie ograniczeń wszystkich kodów blokowych w ujednolicony sposób. Takie ograniczenia często przybierają postać granic, które wiążą ze sobą różne parametry kodu blokowego, takie jak szybkość i zdolność wykrywania i korygowania błędów.

Przykładami kodów blokowych są kody Reeda – Solomona , Hamminga , Hadamarda , Expandera , Golaya i Reeda – Mullera . Te przykłady również należą do klasy kodów liniowych , stąd nazywane są liniowymi kodami blokowymi . Bardziej szczegółowo, te kody są znane jako algebraiczne kody blokowe lub cykliczne kody blokowe, ponieważ mogą być generowane przy użyciu wielomianów boolowskich.

Algebraiczne kody blokowe są zwykle trwale dekodowane za pomocą dekoderów algebraicznych.

Termin kod blokowy może również odnosić się do dowolnego kodu korekcji błędów, który działa na bloku bitów danych wejściowych w celu wytworzenia bitów danych wyjściowych . W konsekwencji koder blokowy jest urządzeniem bez pamięci . Zgodnie z tą definicją kody, takie jak kody turbo , zakończone kody splotowe i inne kody iteracyjnie dekodowalne (kody podobne do turbo) również byłyby uważane za kody blokowe. Niezakończony koder splotowy byłby przykładem kodu nieblokowego (bez ramki), który ma pamięć i jest zamiast tego klasyfikowany jako kod drzewa . ${\ displaystyle k}$${\ displaystyle n}$${\ displaystyle (n, k)}$

Ten artykuł dotyczy „algebraicznych kodów blokowych”.

Kod blokowy i jego parametry

Kody korekcji błędów służą do niezawodnego przesyłania danych cyfrowych przez zawodne kanały komunikacyjne, w których występuje szum kanału . Gdy nadawca chce przesłać możliwie bardzo długi strumień danych przy użyciu kodu blokowego, nadawca dzieli strumień na części o ustalonym rozmiarze. Każdy taki fragment nazywany jest wiadomością, a procedura podana przez kod blokowy koduje każdą wiadomość indywidualnie na słowo kodowe, zwane także blokiem w kontekście kodów blokowych. Nadawca przesyła następnie wszystkie bloki do odbiorcy, który z kolei może użyć pewnego mechanizmu dekodowania, aby (miejmy nadzieję) odzyskać oryginalne wiadomości z prawdopodobnie uszkodzonych odebranych bloków. Wydajność i powodzenie całej transmisji zależy od parametrów kanału i kodu blokowego.

Formalnie kod blokowy jest odwzorowaniem iniekcyjnym

${\ Displaystyle C: \ Sigma ^ {k} \ do \ Sigma ^ {n}}$ .

Tutaj jest skończony i niepusty zbiór i i są liczbami całkowitymi. Znaczenie i znaczenie tych trzech parametrów oraz innych parametrów związanych z kodem opisano poniżej. ${\ displaystyle \ Sigma}$${\ displaystyle k}$${\ displaystyle n}$

Alfabet Σ

Strumień danych do zakodowania jest modelowany jako ciąg znaków na pewnym alfabecie . Rozmiar alfabetu jest często zapisywany jako . Jeśli , to kod blokowy nazywany jest binarnym kodem blokowym. W wielu zastosowaniach warto uważać ją za potęgę pierwszą i identyfikować się z ciałem skończonym . ${\ displaystyle \ Sigma}$${\ displaystyle | \ Sigma |}$${\ displaystyle q}$${\ displaystyle q = 2}$${\ displaystyle q}$${\ displaystyle \ Sigma}$ ${\ displaystyle \ mathbb {F} _ {q}}$

Długość wiadomości k

Wiadomości są elementami z , czyli ciągi długości . Stąd liczba nazywana jest długością wiadomości lub wymiarem kodu blokowego. ${\ displaystyle m}$${\ displaystyle \ Sigma ^ {k}}$${\ displaystyle k}$${\ displaystyle k}$

Długość bloku n

Długość bloku z kodu grupowego jest liczba symboli w bloku. W związku z tym, elementy w to łańcuchy o długości , odpowiadają na bloki, które mogą być odbierane przez odbiornik. Dlatego nazywane są również słowami otrzymanymi. Jeśli dla jakiejś wiadomości , to nazywane jest słowem kodowym . ${\ displaystyle n}$${\ displaystyle c}$${\ displaystyle \ Sigma ^ {n}}$${\ displaystyle n}$${\ Displaystyle c = C (m)}$${\ displaystyle m}$${\ displaystyle c}$${\ displaystyle m}$

Stawka R

Szybkość z kodu bloku definiuje się jako stosunek długości komunikatów i długości bloku:

${\ Displaystyle R = k / n}$ .

Duża szybkość oznacza, że ​​ilość rzeczywistej wiadomości na przesłany blok jest duża. W tym sensie, szybkość mierzy szybkość transmisji, a ilość mierzy narzut, który występuje z powodu kodowania za pomocą kodu blokowego. Jest to prosta informacja, teoretyczna fakt, że szybkość nie może przekroczyć, ponieważ dane w zasadzie nie mogą być kompresowane bezstratnie. Formalnie wynika to z faktu, że kod jest mapą iniekcyjną. ${\ displaystyle 1-R}$${\ displaystyle 1}$${\ displaystyle C}$

Odległość d

Odległości lub minimalnej odległości d od kodu grupowego jest minimalna ilość położeń, w których dwa oddzielne słowa kodowe różne, a wzajemny odstęp jest frakcją . Formalnie odebranych słów , niech oznaczają odległość Hamminga pomiędzy a , to znaczy, liczbę pozycji, w których i różne. Następnie minimalna odległość kodu jest definiowana jako ${\ displaystyle \ delta}$${\ displaystyle d / n}$${\ displaystyle c_ {1}, c_ {2} \ in \ Sigma ^ {n}}$${\ Displaystyle \ Delta (c_ {1}, c_ {2})}$${\ displaystyle c_ {1}}$${\ displaystyle c_ {2}}$${\ displaystyle c_ {1}}$${\ displaystyle c_ {2}}$${\ displaystyle d}$${\ displaystyle C}$

${\ Displaystyle d: = \ min _ {m_ {1}, m_ {2} \ w \ Sigma ^ {k} \ na szczycie m_ {1} \ neq m_ {2}} \ Delta [C (m_ {1}) , C (m_ {2})]}$ .

Ponieważ każdy kod musi być wstrzykiwany , dowolne dwa słowa kodowe będą niezgodne w co najmniej jednej pozycji, więc odległość dowolnego kodu wynosi co najmniej . Poza tym odległość jest równa minimalnej wadze dla liniowych kodów blokowych, ponieważ: ${\ displaystyle 1}$

${\ Displaystyle \ min _ {m_ {1}, m_ {2} \ w \ Sigma ^ {k} \ na szczycie m_ {1} \ neq m_ {2}} \ Delta [C (m_ {1}), C ( m_ {2})] = \ min _ {m_ {1}, m_ {2} \ in \ Sigma ^ {k} \ atop m_ {1} \ neq m_ {2}} \ Delta [\ mathbf {0}, C (m_ {1}) + C (m_ {2})] = \ min _ {m \ in \ Sigma ^ {k} \ atop m \ neq \ mathbf {0}} w [C (m)] = w_ {\ min}}$ .

Większa odległość pozwala na większą korekcję i wykrywanie błędów. Na przykład, jeśli weźmiemy pod uwagę tylko błędy, które mogą zmienić symbole wysłanego słowa kodowego, ale nigdy ich nie usuniemy ani nie dodamy, to liczba błędów to liczba pozycji, w których wysłane słowo kodowe i odebrane słowo różnią się. Kod z odległością d umożliwia odbiornikowi wykrycie aż do błędów transmisji, ponieważ zmiana pozycji słowa kodowego nigdy nie może przypadkowo dać innego słowa kodowego. Ponadto, jeśli wystąpią nie więcej niż błędy transmisji, odbiornik może w unikalny sposób dekodować odebrane słowo na słowo kodowe. Dzieje się tak, ponieważ każde odebrane słowo ma co najwyżej jedno słowo kodowe na odległość . Jeżeli wystąpi więcej niż błędy transmisji, odbiornik nie może w ogólności jednoznacznie zdekodować odebranego słowa, ponieważ może istnieć kilka możliwych słów kodowych. Jednym ze sposobów radzenia sobie przez odbiornik w tej sytuacji jest użycie dekodowania listy , w którym dekoder wyprowadza listę wszystkich słów kodowych w określonym promieniu. ${\ displaystyle d-1}$${\ displaystyle d-1}$${\ displaystyle (d-1) / 2}$${\ displaystyle (d-1) / 2}$${\ displaystyle (d-1) / 2}$

Popularna notacja

Notacja opisuje kod bloku w alfabecie o rozmiarze , z długością bloku, długością wiadomości i odległością . Jeśli kod blokowy jest liniowym kodem blokowym, to do przedstawienia tego faktu używane są nawiasy kwadratowe w zapisie . W przypadku kodów binarnych z indeksem jest czasami pomijany. W przypadku kodów możliwych do rozdzielenia maksymalnej odległości odległość jest zawsze , ale czasami dokładna odległość nie jest znana, nietrywialne do udowodnienia lub stwierdzenia, lub nie jest potrzebne. W takich przypadkach może brakować -komponentu. ${\ Displaystyle (n, k, d) _ {q}}$${\ displaystyle \ Sigma}$${\ displaystyle q}$${\ displaystyle n}$${\ displaystyle k}$${\ displaystyle d}$${\ displaystyle [n, k, d] _ {q}}$${\ displaystyle q = 2}$${\ Displaystyle d = n-k + 1}$${\ displaystyle d}$

Czasami, szczególnie w przypadku kodów nieblokowych, notacja jest używana w przypadku kodów zawierających słowa kodowe o określonej długości . W przypadku kodów blokowych z wiadomościami o długości przekraczającej alfabet o rozmiarze , liczba ta wynosiłaby . ${\ Displaystyle (n, M, d) _ {q}}$${\ displaystyle M}$${\ displaystyle n}$${\ displaystyle k}$${\ displaystyle q}$${\ Displaystyle M = q ^ {k}}$

Przykłady

Jak wspomniano powyżej, istnieje ogromna liczba kodów korekcji błędów, które w rzeczywistości są kodami blokowymi. Pierwszym kodem korygującym błędy był kod Hamminga (7,4) , opracowany przez Richarda W. Hamminga w 1950 r. Ten kod przekształca wiadomość składającą się z 4 bitów w słowo kodowe o długości 7 bitów poprzez dodanie 3 bitów parzystości. Stąd ten kod jest kodem blokowym. Okazuje się, że jest to również kod liniowy i ma odległość 3. W powyższym zapisie skróconym oznacza to, że kod Hamminga (7,4) jest kodem. ${\ displaystyle [7,4,3] _ {2}}$

Kody Reeda-Solomona to rodzina kodów posiadających i będących mocą główną . Kody rangi to rodziny kodów z . Kody Hadamarda to rodzina kodów z i . ${\ displaystyle [n, k, d] _ {q}}$${\ Displaystyle d = n-k + 1}$${\ displaystyle q}$${\ displaystyle [n, k, d] _ {q}}$${\ displaystyle d \ leq n-k + 1}$${\ displaystyle [n, k, d] _ {2}}$${\ Displaystyle n = 2 ^ {k-1}}$${\ Displaystyle d = 2 ^ {k-2}}$

Właściwości wykrywania i korekcji błędów

Słowo kodowe można uznać za punkt w przestrzeni -wymiarowej, a kod jest podzbiorem . Kod ma odległość oznacza, że nie ma innego słowa kodowego w kuli Hamminga wyśrodkowanej w promieniu , która jest zdefiniowana jako zbiór słów -wymiarów, do których odległość Hamminga nie jest większa niż . Podobnie z (minimalną) odległością ma następujące właściwości: ${\ displaystyle c \ in \ Sigma ^ {n}}$${\ displaystyle n}$${\ displaystyle \ Sigma ^ {n}}$${\ displaystyle {\ mathcal {C}}}$${\ displaystyle \ Sigma ^ {n}}$${\ displaystyle {\ mathcal {C}}}$${\ displaystyle d}$${\ displaystyle \ forall c \ in {\ mathcal {C}}}$${\ displaystyle c}$${\ displaystyle d-1}$${\ displaystyle n}$${\ displaystyle c}$${\ displaystyle d-1}$${\ displaystyle {\ mathcal {C}}}$${\ displaystyle d}$

• ${\ displaystyle {\ mathcal {C}}}$ może wykrywać błędy: ponieważ słowo kodowe jest jedynym słowem kodowym w kuli Hamminga wyśrodkowanej na sobie z promieniem , żaden wzorzec błędu lub mniej błędów nie może zmienić jednego słowa kodowego na inne. Gdy odbiornik wykryje, że odebrany wektor nie jest słowem kodowym , wykrywane są błędy (ale bez gwarancji ich poprawienia). ${\ displaystyle d-1}$${\ displaystyle c}$${\ displaystyle d-1}$${\ displaystyle d-1}$${\ displaystyle {\ mathcal {C}}}$
• ${\ displaystyle {\ mathcal {C}}}$ potrafi poprawiać błędy. Ponieważ słowo kodowe jest jedynym słowem kodowym w kuli Hamminga wyśrodkowanej na sobie z promieniem , dwie kulki Hamminga wyśrodkowane odpowiednio na dwóch różnych słowach kodowych z obydwoma promieniem nie nakładają się na siebie. Dlatego, jeśli weźmiemy pod uwagę korektę błędów jako znalezienie słowa kodowego najbliższego otrzymanemu słowu , o ile liczba błędów jest nie większa niż , w kuli młotkowej wyśrodkowanej na promieniu jest tylko jedno słowo kodowe , dlatego wszystkie błędy można poprawić . ${\ Displaystyle \ textstyle \ lewo \ lfloor {{d-1} \ ponad 2} \ prawo \ rfloor}$${\ displaystyle c}$${\ displaystyle d-1}$${\ Displaystyle \ textstyle \ lewo \ lfloor {{d-1} \ ponad 2} \ prawo \ rfloor}$${\ displaystyle y}$${\ Displaystyle \ textstyle \ lewo \ lfloor {{d-1} \ ponad 2} \ prawo \ rfloor}$${\ displaystyle y}$${\ Displaystyle \ textstyle \ lewo \ lfloor {{d-1} \ ponad 2} \ prawo \ rfloor}$
• Aby zdekodować w obecności więcej niż błędów, można zastosować dekodowanie listy lub dekodowanie z maksymalnym prawdopodobieństwem . ${\ displaystyle (d-1) / 2}$
• ${\ displaystyle {\ mathcal {C}}}$ może poprawić wymazania . Przez usunięcia Oznacza to, że pozycja usunięte symbolu jest znane. Korektę można osiągnąć przez ominięcie dekodowania: podczas przechodzenia usunięta pozycja jest wypełniana symbolem i wykonywana jest korekcja błędów. Musi się zdarzyć, że liczba błędów nie przekracza, a zatem można skorygować wymazania. ${\ displaystyle d-1}$ ${\ displaystyle q}$${\ displaystyle i ^ {th}}$${\ displaystyle i ^ {th}}$${\ Displaystyle \ textstyle \ lewo \ lfloor {{d-1} \ ponad 2} \ prawo \ rfloor}$

Dolna i górna granica kodów blokowych

Limit Hamminga

Istnieją teoretyczne ograniczenia (takie jak granica Hamminga), ale inna kwestia dotyczy tego, które kody można faktycznie skonstruować. To jak pakowanie kulek w pudełko w wielu wymiarach. Ten diagram przedstawia konstruowalne kody, które są liniowe i binarne. W x oś pokazuje liczbę chronionych symboli k The Y osi ilość potrzebnych symboli kontrolnych N-K . Wykreślone są granice dla różnych odległości Hamminga od 1 (niezabezpieczone) do 34. Oznaczone kropkami to doskonałe kody:

• jasnopomarańczowy na osi x : trywialne kody niezabezpieczone
• pomarańczowy na osi y : trywialne powtórzenia kodów
• ciemnopomarańczowy na zestawie danych d = 3: klasyczne, doskonałe kody Hamminga
• ciemnoczerwony i większy: jedyny doskonały kod binarny Golaya

Rodzina kodów

${\ displaystyle C = \ {C_ {i} \} _ {i \ geq 1}}$ nazywana jest rodziną kodów , gdzie jest kod z monotonicznym wzrostem . ${\ displaystyle C_ {i}}$${\ displaystyle (n_ {i}, k_ {i}, d_ {i}) _ {q}}$${\ displaystyle n_ {i}}$

Współczynnik rodziny kodów C określa się jako ${\ Displaystyle R (C) = \ lim _ {i \ do \ infty} {k_ {i} \ ponad n_ {i}}}$

Względna odległość rodziny kodów C jest zdefiniowana jako ${\ Displaystyle \ delta (C) = \ lim _ {i \ do \ infty} {d_ {i} \ ponad n_ {i}}}$

Aby zbadać związek między i , znany jest zestaw dolnych i górnych granic kodów blokowych. ${\ Displaystyle R (C)}$${\ Displaystyle \ delta (C)}$

Hamming związany

${\ Displaystyle R \ równoważnik 1- {1 \ ponad n} \ cdot \ log _ {q} \ cdot \ lewo [\ suma _ {i = 0} ^ {\ lewo \ lfloor {{\ delta \ cdot n-1) } \ ponad 2} \ right \ rfloor} {\ binom {n} {i}} (q-1) ^ {i} \ right]}$

Singleton związany

Ograniczenie singletona polega na tym, że suma szybkości i względnej odległości kodu blokowego nie może być dużo większa niż 1:

${\ Displaystyle R + \ delta \ leq 1 + {\ Frac {1} {n}}}$ .

Innymi słowy, każdy kod blokowy spełnia nierówność . Kody Reeda-Solomona są nietrywialnymi przykładami kodów, które spełniają singleton związany z równością. ${\ displaystyle k + d \ leq n + 1}$

Plotkin związane

Dla , . Innymi słowy . ${\ displaystyle q = 2}$${\ displaystyle R + 2 \ delta \ leq 1}$${\ displaystyle k + 2d \ leq n}$

W ogólnym przypadku następujące granice Plotkina obowiązują dla każdego z odległością d : ${\ Displaystyle C \ subseteq \ mathbb {F} _ {q} ^ {n}}$

1. Gdyby ${\ Displaystyle d = \ lewo (1- {1 \ ponad q} \ prawej) n, | C | \ równoważnik 2qn}$
2. Gdyby ${\ Displaystyle d> \ lewo (1- {1 \ ponad q} \ prawej) n, | C | \ równoważnik {qd \ ponad {qd- \ lewo (q-1 \ prawo) n}}}$

Dla każdego q -ary kodu z odległości , ${\ displaystyle \ delta}$${\ Displaystyle R \ równoważnik 1- \ lewo ({q \ ponad {q-1}} \ prawej) \ delta + o \ lewo (1 \ prawo)}$

Związany Gilbert-Varshamov

${\ Displaystyle R \ geq 1-H_ {q} \ lewo (\ delta \ prawej) - \ epsilon}$ Gdzie , to q -ary funkcji entropii. ${\ Displaystyle 0 \ równoważnik \ delta \ równoważnik 1- {1 \ ponad q}, 0 \ równoważnik \ epsilon \ równoważnik 1-H_ {q} \ lewo (\ delta \ prawej)}$${\ Displaystyle H_ {q} \ lewo (x \ w prawo) ~ {\ overset {\ underset {\ mathrm {def}} {}} {=}} ~ -x \ cdot \ log _ {q} {x \ ponad {q-1}} - \ left (1-x \ right) \ cdot \ log _ {q} {\ left (1-x \ right)}}$

Johnson związany

Zdefiniuj . Niech będzie maksymalną liczbą słów kodowych w kuli Hamminga o promieniu e dla dowolnego kodu odległości d . ${\ Displaystyle J_ {q} \ lewo (\ delta \ prawej) ~ {\ overset {\ underset {\ mathrm {def}} {}} {=}} ~ \ lewo (1- {1 \ ponad q} \ prawo ) \ left (1 - {\ sqrt {1- {q \ delta \ over {q-1}}}} \ right)}$
${\ Displaystyle J_ {q} \ lewo (n, d, e \ prawej)}$${\ Displaystyle C \ subseteq \ mathbb {F} _ {q} ^ {n}}$

Następnie mamy Johnson Związany  : jeśli ${\ Displaystyle J_ {q} \ lewo (n, d, e \ prawej) \ równoważnik qnd}$${\ Displaystyle {e \ ponad n} \ równoważnik {{q-1} \ ponad q} \ lewo ({1 - {\ sqrt {1- {q \ ponad {q-1}} \ cdot {d \ ponad n }}}} \, \ right) = J_ {q} \ left ({d \ over n} \ right)}$

Związany Elias – Bassalygo

${\ Displaystyle R = {\ log _ {q} {| C |} \ ponad n} \ równoważnik 1-H_ {q} \ lewo (J_ {q} \ lewo (\ delta \ prawo) \ prawo) + o \ lewo (1 \ prawo)}$

Pakiety i kraty kulowe

Kody blokowe są związane z problemem pakowania kulistego, któremu na przestrzeni lat poświęcano uwagę. W dwóch wymiarach łatwo to wizualizować. Połóż kilka monet na stole i połącz je razem. Rezultatem jest sześciokątny wzór przypominający gniazdo pszczoły. Ale kody blokowe opierają się na większej liczbie wymiarów, których nie można łatwo wizualizować. Potężny kod Golaya używany w komunikacji kosmicznej wykorzystuje 24 wymiary. Jeśli jest używany jako kod binarny (którym zwykle jest), wymiary odnoszą się do długości słowa kodowego, jak określono 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 kwestie dotyczą wyboru kodu. Na przykład, sześciokątne upakowanie w ograniczenie prostokątnego pudełka pozostawi puste miejsce w rogach. Wraz ze wzrostem wymiarów zmniejsza się procent pustej przestrzeni. Ale przy pewnych wymiarach opakowanie zajmuje całą przestrzeń i te kody to tak zwane kody doskonałe. Jest ich bardzo niewiele.

Inną właściwością jest liczba sąsiadów, które może mieć jedno słowo kodowe. Ponownie rozważmy grosze jako przykład. Najpierw pakujemy grosze w prostokątną siatkę. Każdy grosz będzie miał 4 sąsiadów w pobliżu (i 4 w rogach, które są dalej). W sześciokącie każdy grosz będzie miał 6 bliskich sąsiadów. Odpowiednio, w trzech i czterech wymiarach, maksymalne upakowanie jest podane przez 12-ścianową i 24-komorową komorę z odpowiednio 12 i 24 sąsiadami. Kiedy zwiększamy wymiary, liczba najbliższych sąsiadów rośnie bardzo szybko. Ogólnie wartość jest podawana przez liczby całujące .

W rezultacie rośnie również liczba sposobów, na jakie hałas powoduje, że odbiornik wybiera sąsiada (stąd błąd). Jest to podstawowe ograniczenie kodów blokowych, a właściwie wszystkich kodów. Może być trudniej spowodować błąd u pojedynczego sąsiada, ale liczba sąsiadów może być na tyle duża, że ​​w rzeczywistości spada całkowite prawdopodobieństwo błędu.

Zobacz też

• Pojemność kanału
• Twierdzenie Shannona – Hartleya
• Hałaśliwy kanał
• Dekodowanie listy
• Pakowanie kuli

Bibliografia

• JH van Lint (1992). Wprowadzenie do teorii kodowania . GTM . 86 (wyd. 2). Springer-Verlag. p.  31 . ISBN   3-540-54894-7 .
• FJ MacWilliams ; NJA Sloane (1977). Teoria kodów korygujących błędy . Północna Holandia. p.  35 . ISBN   0-444-85193-3 .
• W. Huffman; V.Pless (2003). Podstawy kodów korygujących błędy . Cambridge University Press. ISBN   978-0-521-78280-7 .
• S. Lin; DJ Jr. Costello (1983). Kodowanie kontroli błędów: podstawy i zastosowania . Prentice-Hall. ISBN   0-13-283796-X .

Zewnętrzne linki

• Charan Langton (2001) Koncepcje kodowania i kodowanie blokowe