Kód řádku

Aktuální verze stránky ještě nebyla zkontrolována zkušenými přispěvateli a může se výrazně lišit od verze recenzované 28. ledna 2021; ověření vyžaduje 1 úpravu .

V matematice a teorii informace je řádkový kód typem blokového kódu používaného v obvodech pro detekci a opravu chyb. Lineární kódy ve srovnání s jinými kódy umožňují implementovat efektivnější algoritmy pro kódování a dekódování informací.

Základy

V procesu ukládání dat a přenosu informací po komunikačních sítích nevyhnutelně dochází k chybám. Kontrola integrity dat a oprava chyb jsou důležité úkoly na mnoha úrovních práce s informacemi (zejména fyzické vrstvy , datové spoje a transportní vrstvy modelu OSI ).

V komunikačních systémech je možných několik strategií pro řešení chyb:

detekce chyb v datových blocích a automatický požadavek na opakovaný přenos poškozených bloků - tento přístup se používá především na datové spojové a transportní vrstvě;
detekce chyb v datových blocích a vyřazení špatných bloků – tento přístup se někdy používá v systémech streamovaných médií, kde je důležité zpoždění přenosu a není čas na opakovaný přenos;
oprava chyb ( anglicky forward error correction ) je aplikována na fyzické vrstvě.

Kódy pro detekci a opravu chyb

Opravné kódy - kódy, které se používají k detekci nebo opravě chyb, ke kterým dochází při přenosu informace pod vlivem rušení , jakož i při jejím ukládání.

K tomu při zápisu (přenosu) do užitečných dat přidávají speciálně strukturované redundantní informace a při čtení (přijímání) se používají k detekci nebo opravě chyb. Počet chyb, které lze opravit, je samozřejmě omezený a závisí na konkrétním použitém kódu.

S kódy pro opravu chyb úzce souvisí kódy pro detekci chyb . Na rozdíl od prvního může druhý pouze zjistit přítomnost chyby v přenášených datech, ale neopravit ji.

Ve skutečnosti použité kódy detekce chyb patří do stejných tříd kódů jako kódy pro opravu chyb. Ve skutečnosti lze k detekci chyb použít také jakýkoli kód opravující chyby (přitom bude schopen detekovat více chyb, než byl schopen opravit).

Podle způsobu práce s daty se kódy opravující chyby dělí na kódy blokové , které rozdělují informace na fragmenty konstantní délky a zpracovávají každý z nich samostatně, a kódy konvoluční , které pracují s daty jako souvislý proud.

Blokové kódy

Nechte zakódovanou informaci rozdělit na fragmenty bitové délky, které se převedou na kódová slova bitové délky . Potom je obvykle označen odpovídající blokový kód . V tomto případě se toto číslo nazývá kódová sazba . $k$ $n$ $(n,k)$ $R={\frac {k}{n}}$

Pokud kód ponechá původní bity beze změny a přidá kontroly , takový kód se nazývá systematický , jinak nesystematický . $k$ $nk$

Blokový kód můžete nastavit různými způsoby, včetně tabulky, kde je každá sada informačních bitů spojena s bitem kódového slova. Dobrý kód by však měl splňovat alespoň následující kritéria: $k$ $n$

schopnost opravit co nejvíce chyb,
co nejmenší redundanci,
snadnost kódování a dekódování.

Je snadné vidět, že tyto požadavky si vzájemně odporují. Proto existuje velké množství kódů, z nichž každý je vhodný pro svůj rozsah úkolů.

Téměř všechny použité kódy jsou lineární . To je způsobeno skutečností, že nelineární kódy je mnohem obtížnější studovat a je pro ně obtížné poskytnout přijatelnou snadnost kódování a dekódování.

Lineární prostory

Generování matice

Nechť vektory jsou základem lineárního prostoru . Podle definice báze může být jakýkoli vektor reprezentován jako lineární kombinace základních vektorů: nebo ve formě matice jako: $\overrightarrow {x_{1}}=(x_{{11}},..,x_{{1n}}),\overrightarrow {x_{2}}=(x_{{21}},..,x_{ {2n}}),..,\overrightarrow {x_{k}}=(x_{{k1}},..,x_{{kn}})$ $C$ $\overrightarrow {v}\v C$ $\overrightarrow {v}={c_{1}}\overrightarrow {x_{1}}+{c_{2}}\overrightarrow {x_{2}}+...+{c_{k}}\overrightarrow {x_ {k}}$

$\overrightarrow {v}=({c_{1}},{c_{2}},..,{c_{k}}){\begin{bmatrix}x_{{11}}&x_{{12}}& ..&x_{{1n}}\\x_{{21}}&x_{{22}}&..&x_{{2n}}\\..&..&..&..\\x_{{k1 }}&x_{{k2}}&..&x_{{kn}}\\\end{bmatrix}}=\overrightarrow {c}G$ ,

kde se nazývá generátorová matice lineárního prostoru . $G={\begin{bmatrix}x_{{11}}&x_{{12}}&..&x_{{1n}}\\x_{{21}}&x_{{22}}&..&x_{{2n }}\\..&..&..&..\\x_{{k1}}&x_{{k2}}&..&x_{{kn}}\\\end{bmatrix}}$

Tento vztah vytváří spojení mezi vektory koeficientů a vektory . Vypsáním všech vektorů koeficientů získáte všechny vektory . Jinými slovy, matice generuje lineární prostor. $\overrightarrow {c}=({c_{1}},{c_{2}},..,{c_{k}})$ $\overrightarrow {v}\v C$ $\overrightarrow {c}=({c_{1}},{c_{2}},..,{c_{k}})$ $\overrightarrow {v}\v C$ $G$

Kontrolní matice

Dalším způsobem, jak definovat lineární prostory, je popsat je pomocí kontrolní matice.

Dovolit být lineární k-rozměrný podprostor n-rozměrného prostoru přes konečné pole a být ortogonální doplněk . Pak podle jedné z vět lineární algebry je rozměr . Proto existuje r základních vektorů v . Nechť je základ v . $\mathbb {C}$ $\mathbb {F} _{q}$ ${\mathbb {W}}$ $\mathbb {C}$ ${\mathbb {W}}$ $r=nk$ ${\mathbb {W}}$ $\overrightarrow {h}_{1}=({{h_{1}}_{1}},...,{{h_{1}}_{n}}),\overrightarrow {h}_{2 }=({{h_{2}}_{1}},...,{{h_{2}}_{n}}),...,\overrightarrow {h}_{r}=({ {h_{r}}_{1}},...,{{h_{r}}_{n}})$ ${\mathbb {W}}$

Potom jakýkoli vektor splňuje následující systém lineárních rovnic : ${\overrightarrow {v}}\in \mathbb {C}$

${\begin{cases}h_{{11}}x_{1}+h_{{12}}x_{2}+...+h_{{1n}}x_{n}=0\\h_{{21 }}x_{1}+h_{{22}}x_{2}+...+h_{{2n}}x_{n}=0\\...\\h_{{r1}}x_{1 }+h_{{r2}}x_{2}+...+h_{{rn}}x_{n}=0\end{cases}}$

Nebo v maticové podobě : $\overrightarrow {v}H^{T}=0$

kde je kontrolní matice. $H={\begin{bmatrix}\overrightarrow {h}_{1}\\\overrightarrow {h}_{2}\\...\\\overrightarrow {h}_{r}\\\end{bmatrix }}={\begin{bmatrix}h_{{11}}&h_{{12}}&..&h_{{1n}}\\h_{{21}}&h_{{22}}&..&h_{{ 2n}}\\..&..&..&..\\h_{{r1}}&h_{{r2}}&..&h_{{rn}}\\\end{bmatrix}}$

Redukovaný systém lineárních rovnic by měl být považován za systém kontrol pro všechny vektory lineárního prostoru, proto se matice nazývá kontrolní matice. ${\mathbb {H}}$

Formální definice

Lineární kód délky n a pozice k je lineární podprostor C dimenze k vektorového prostoru , kde je konečné pole q prvků . Takový kód s parametrem q se nazývá q-ární kód (například pokud q = 5, pak se jedná o 5-ární kód). Pokud q = 2 nebo q = 3, pak je kód binární nebo ternární . ${\mathbb {F}}_{q}^{n}$ $\mathbb {F} _{q}$

Lineární (blokový) kód je takový kód, že množina jeho kódových slov tvoří -rozměrný lineární podprostor (říkejme tomu ) v -rozměrném lineárním prostoru , izomorfním s prostorem -bitových vektorů . $k$ $C$ $n$ $k$

To znamená, že operace kódování odpovídá násobení původního bitového vektoru nesingulární maticí , nazývanou generátorová matice . $k$ $G$

Dovolit být ortogonální podprostor vzhledem k , a být matice definující základ tohoto podprostoru. Pak pro jakýkoli vektor platí: $C^{\perp}$ $C$ $H$ $\overrightarrow {v}\v C$

\overrightarrow {v}H^{T}=\overrightarrow {0}

Vlastnosti a důležité věty

Minimální vzdálenost a korekční síla

Hammingova vzdálenost ( Hammingova metrika ) mezi dvěma kódovými slovyjepočet různých bitů v odpovídajících pozicích, to znamená počet "jednotek" ve vektoru. $\overrightarrow {v_{1}}$ $\overrightarrow {v_{2}}$ $\overrightarrow {v_{1}}\oplus \overrightarrow {v_{2}}$

Minimální vzdálenost řádkového kódu je minimem všech Hammingových vzdáleností všech párů kódových slov. $d$

Váha vektoru je Hammingova vzdálenost mezi tímto vektorem a nulovým vektorem, jinými slovy, počet nenulových složek vektoru. $w$

Věta 1:

Minimální vzdálenost řádkového kódu se rovná minimu Hammingových vah nenulových kódových slov: $d$

$d=\min _{{\overrightarrow {c}\v C,\overrightarrow {c}\not =\overrightarrow {0}}}(w(\overrightarrow {c}))$

Důkaz:

Vzdálenost mezi dvěma vektory splňuje rovnost , kde je Hammingova váha vektoru . Ze skutečnosti, že rozdíl libovolných dvou kódových slov lineárního kódu je zároveň kódovým slovem lineárního kódu, vyplývá tvrzení věty: $d(\šipka vpravo {x},\šipka vpravo {y})$ $d(\overrightarrow {x},\overrightarrow {y})=w(\overrightarrow {x}-\overrightarrow {y})$ $w(\overrightarrow {t})$ $\overrightarrow {t}$ $d=\min _{{\overrightarrow {c}\v C,\overrightarrow {c}\not =\overrightarrow {0}}}w(\overrightarrow {c})$

Minimální Hammingova vzdálenost je důležitou charakteristikou lineárního blokového kódu. Definuje další, neméně důležitou vlastnost - korekční schopnost : $d$

$t=\left\lpatro {\frac {d-1}{2}}\pravé\rpatro$ , zde lomené závorky označují zaokrouhlení "dolů".

Opravná síla určuje, jaký je maximální počet chyb v jednom kódovém slově, u kterých lze zaručit , že kód opraví.

Vysvětlíme si to na příkladu. Předpokládejme, že existují dvě kódová slova A a B, Hammingova vzdálenost mezi nimi je rovna 3. Pokud bylo přeneseno slovo A a kanál zavedl chybu v jednom bitu, lze ji opravit, protože i v tomto případě je přijaté slovo blíže kódové slovo A než B. Pokud však kanál zavedl dvoubitové chyby, dekodér může předpokládat, že slovo B bylo přeneseno.

Počet zjištěných chyb je počet chyb, při kterých může dekodér detekovat chybovou situaci (a např. zahájit opakovaný přenos zprávy). Toto číslo je

f=d-1

Věta 2 (bez důkazu):

Pokud jsou některé sloupce kontrolní matice H lineárního (n, k)-kódu lineárně nezávislé, pak je minimální kódová vzdálenost alespoň d. Pokud existuje d lineárně závislých sloupců, pak minimální kódová vzdálenost je přesně d. $l\leqslant d-1$

Věta 3 (bez důkazu):

Pokud je minimální vzdálenost lineárního (n, k) kódu d, pak jsou libovolné sloupce kontrolní matice H lineárně nezávislé a existuje d lineárně závislých sloupců. $l\leqslant d-1$

Hammingovy kódy

Historicky by se „ Hammingovy kódy “ měly nazývat kódy R. Fishera a byly zavedeny v roce 1942 (Fisher RA The theory of conouding in factor to thr theory). Hammingovy kódy jsou nejjednodušší lineární kódy s minimální vzdáleností 3, to znamená, že jsou schopné opravit jednu chybu. Hammingův kód lze znázornit tak, že syndrom

\overrightarrow {s}=\overrightarrow {r}H^{T}

, kde je přijímaný vektor,

\overrightarrow{r}

se bude rovnat číslu pozice, na které došlo k chybě. Tato vlastnost velmi usnadňuje dekódování.

Reed-Mullerův kód

Reed-Mullerův kód je lineární binární blokový kód. Při určitém způsobu výstavby může být systematická. Obecně platí, že Reed-Mullerův kód není cyklický. Reed-Mullerovy kódy jsou dány následujícími parametry: pro jakékoli hodnotya, nazývané kódové pořadí, menší než: $m$ $r$ $m$

délka kódového slova

n=2^{m};

délka informační části

k=1+C_{m}^{1}+\tečky +C_{m}^{r};

délka zkušebního dílu

nk=1+C_{m}^{1}+\tečky +C_{m}^{mr-1};

minimální vzdálenost kódu

d_{min}=2^{mr}.

Reed-Mullerův kód je určen pomocí generátorové matice sestávající ze základních vektorů, která je sestavena podle pravidla:

nechť je vektor, jehož všechny složky jsou rovny 1;

V_{0}

nechť jsou řádky matice, jejíž sloupce jsou všechny binární množiny délky

{\displaystyle V_{1},\ V_{2},\dots V_{m))

m

Reed-Mullerův kód t. řádu obsahuje vektory a všechny dílčí produkty nebo menší počet těchto vektorů jako základ. $r$ ${\displaystyle V_{0},\ V_{1},\dots V_{m))$ $r$

Obecná metoda pro kódování řádkových kódů

Lineární kód délky n s k informačními symboly je k-rozměrný lineární podprostor, takže každé kódové slovo je lineární kombinací základních vektorů podprostoru : $\overrightarrow {g_{1}}=(g_{{11}},..,g_{{1n}}),\overrightarrow {g_{2}}=(g_{{21}},..,g_{ {2n}}),..,\overrightarrow {g_{k}}=(g_{{k1}},..,g_{{kn}})$

$\overrightarrow {c}={m_{1}}\overrightarrow {g_{1}}+{m_{2}}\overrightarrow {g_{2}}+...+{m_{k}}\overrightarrow {g_ {k}}$ .

Nebo pomocí matice generátoru:

$\overrightarrow {c}=\overrightarrow {m}G=({m_{1}},{m_{2}},..,{m_{k}}){\begin{bmatrix}g_{{11}} &g_{{12}}&..&g_{{1n}}\\g_{{21}}&g_{{22}}&..&g_{{2n}}\\..&..&..&. .\\g_{{k1}}&g_{{k2}}&..&g_{{kn}}\\\end{bmatrix}}$ , kde $\overrightarrow {m}=({m_{1}},..,{m_{k}}),{m_{1}},..,{m_{k}}\in {\mathbb {Q}}$

Tento poměr je kódovacím pravidlem , podle kterého je informační slovo mapováno do kódu $\overrightarrow {m}=({m_{1}},..,{m_{k}})$ $\overrightarrow {c}=({c_{1}},..,{c_{n}})$

Obecná metoda detekce chyb v lineárním kódu

Jakýkoli kód (včetně nelineárního) lze dekódovat pomocí běžné tabulky, kde každá hodnota přijatého slova odpovídá nejpravděpodobnějšímu přenášenému slovu . Tato metoda však vyžaduje použití obrovských tabulek již pro kódová slova relativně malé délky. $\overrightarrow {r_{i}}$ $\overrightarrow {u_{i}}$

U lineárních kódů lze tento způsob výrazně zjednodušit. V tomto případě se pro každý přijatý vektor vypočítá syndrom . Protože , kde je kódové slovo a je chybový vektor, pak . Poté se pomocí tabulky syndromů určí chybový vektor, s jehož pomocí se určí přenášené kódové slovo. V tomto případě je tabulka mnohem menší než při použití předchozí metody. $\overrightarrow {r_{i}}$ $\overrightarrow {s_{i}}=\overrightarrow {r_{i}}H^{T}$ $\overrightarrow {r_{i}}=\overrightarrow {v_{i}}+\overrightarrow {e_{i}}$ $\overrightarrow {v_{i}}$ $\overrightarrow {e_{i}}$ $\overrightarrow {s_{i}}=\overrightarrow {e_{i}}H^{T}$

Lineární cyklické kódy

Navzdory skutečnosti, že oprava chyb v lineárních kódech je již mnohem jednodušší než oprava ve většině nelineárních kódů, pro většinu kódů je tento proces stále poměrně komplikovaný. Cyklické kódy mají kromě jednoduššího dekódování další důležité vlastnosti.

Cyklický kód je lineární kód s následující vlastností: jestliže je kódové slovo, pak jeho cyklická permutace je také kódovým slovem. $\overrightarrow{v}$

Slova cyklického kódu jsou vhodně reprezentována jako polynomy. Například kódové slovo je reprezentováno jako polynom . V tomto případě je cyklický posun kódového slova ekvivalentní násobení polynomu modulo . $\overrightarrow {v}=(v_{0},v_{1},...,v_{{n-1}})$ $v(x)=v_{0}+v_{1}x+...+v_{{n-1}}x^{{n-1}}$ $X$ $x^n-1$

V budoucnu, pokud nebude uvedeno jinak, budeme předpokládat, že cyklický kód je binární , to znamená ... může nabývat hodnot 0 nebo 1 . $v_{0},v_{1}$

Generování polynomu

Lze ukázat, že všechna kódová slova určitého cyklického kódu jsou násobky určitého generujícího polynomu . Polynom generátoru je dělitel . $g(x)$ $x^n-1$

Pomocí generujícího polynomu se kódování provádí cyklickým kódem. Zejména:

nesystematické kódování se provádí vynásobením zakódovaného vektoru : ; $g(x)$ $v(x)=u(x)g(x)$

systematické kódování se provádí „přidáním“ ke zakódovanému slovu zbytek dělení , tedy . $x^{{nk}}u(x)$ $g(x)$ $v(x)=x^{{nk}}u(x)+[x^{{nk}}u(x)\mod g(x)]$

CRC kódy

CRC kódy (cyklická redundantní kontrola - cyklická redundantní kontrola) jsou systematické kódy určené nikoli k opravě chyb, ale k jejich odhalování. Používají metodu systematického kódování uvedenou výše: „kontrolní součet“ se vypočítá vydělením . Protože není vyžadována žádná oprava chyb, lze ověření přenosu provést stejným způsobem. $x^{{nk}}u(x)$ $g(x)$

Tvar polynomu g(x) tedy specifikuje konkrétní CRC kód. Příklady nejoblíbenějších polynomů:

krycí jméno	stupeň	polynom
CRC-12	12	$x^{12}+x^{11}+x^{3}+x^{2}+x+1$
CRC-16	16	$x^{16}+x^{15}+x^{2}+1$
CRC- CCITT	16	$x^{16}+x^{12}+x^{5}+1$
CRC-32	32	$x^{32}+x^{26}+x^{23}+x^{22}+x^{16}+x^{12}+x^{11}+x^{10}+x^ {8}+x^{7}+x^{5}+x^{4}+x^{2}+x+1$

BCH kódy

Bose-Chowdhury-Hockwingham (BCH) kódy jsou podtřídou binárních cyklických kódů. Jejich rozlišovacím znakem je schopnost zkonstruovat BCH kód s minimální vzdáleností, která není menší než daná. To je důležité, protože obecně řečeno je určení minimální vzdálenosti kódu velmi obtížný úkol.

Matematicky konstrukce BCH kódů a jejich dekódování využívá rozklad generujícího polynomu na faktory v Galoisově poli . $g(x)$

Reed-Solomonovy kódy

Reed-Solomonovy kódy (RS kódy) jsou ve skutečnosti nebinární BCH kódy, to znamená, že prvky kódového vektoru nejsou bity, ale skupiny bitů. Reed-Solomonovy kódy jsou velmi běžné, pracují s byty ( oktety ).

Výhody a nevýhody řádkových kódů

+ Kvůli linearitě stačí k zapamatování nebo vyčíslení všech kódových slov uložit do paměti kodéru nebo dekodéru jejich podstatně menší část, a to pouze ta slova, která tvoří základ odpovídajícího lineárního prostoru. To značně zjednodušuje implementaci kódovacích a dekódovacích zařízení a činí lineární kódy velmi atraktivními z hlediska praktických aplikací.

— Ačkoli lineární kódy se zpravidla dobře vypořádají se vzácnými, ale velkými shluky chyb , jejich účinnost s častými, ale malými chybami (například v kanálu s AWGN ) je méně vysoká.

Hodnocení výkonu

Účinnost kódů je dána počtem chyb, které dokáže opravit, množstvím nadbytečných informací, které je třeba přidat, a složitostí implementace kódování a dekódování (jak hardware, tak počítačový software ).

Hammingovo vázané a dokonalé kódy

Nechť existuje binární blokový kód s opravnou schopností . Pak platí následující nerovnost (nazývaná Hammingova hranice ): $(n,k)$ $t$

\sum _{i=0}^{t}{C_{n}^{i}}\leq 2^{nk}

Kódy splňující tuto hranici rovnosti jsou považovány za dokonalé . Mezi dokonalé kódy patří například Hammingovy kódy. Kódy s velkou korekční silou, které se v praxi často používají (jako Reed-Solomonovy kódy), nejsou dokonalé.

Energetický zisk

Při přenosu informací komunikačním kanálem závisí pravděpodobnost chyby na poměru signálu k šumu na vstupu demodulátoru, takže při konstantní úrovni šumu má rozhodující význam výkon vysílače. V satelitních a mobilních systémech, stejně jako v jiných typech komunikací, je otázka úspor energie akutní. Kromě toho v určitých komunikačních systémech (například v telefonu) technická omezení neumožňují neomezené zvýšení výkonu signálu.

Protože kódování pro opravu chyb umožňuje opravu chyb, jeho aplikace může snížit výkon vysílače a ponechat rychlost přenosu informací nezměněnou. Energetický zisk je definován jako rozdíl mezi poměry s/n v přítomnosti a nepřítomnosti kódování.

Aplikace

Platí kódy řádků:

v digitálních komunikačních systémech , včetně: satelitu, radioreléového, mobilního přenosu dat přes telefonní kanály;
v systémech ukládání informací, včetně magnetických a optických;
v síťových protokolech různých úrovní .

Literatura

Výkladový slovník výpočetních systémů. Ed. V. Illingworth a další: Per. z angličtiny. - M.: Mashinostroenie , 1990. 560 s.: nemocný.