Oprava chyby Reed – Solomon - Reed–Solomon error correction

Kódy Reed – Solomon jsou skupinou kódů opravujících chyby, které zavedli Irving S. Reed a Gustave Solomon v roce 1960. Mají mnoho aplikací, z nichž mezi nejvýznamnější patří spotřebitelské technologie, jako jsou MiniDiscs , CD , DVD , Blu-ray disky, QR kódy , technologie přenosu dat jako DSL a WiMAX , vysílací systémy jako satelitní komunikace, DVB a ATSC a úložné systémy jako RAID 6 .

Reed-Solomonovy kódy fungují na bloku dat, který je považován za sadu prvků konečného pole nazývaných symboly. Kódy Reed – Solomon jsou schopné detekovat a opravit více chyb symbolů. Přidáním kontrolních symbolů t = n  -  k k datům může kód Reed -Solomon detekovat (ale ne opravit) jakoukoli kombinaci až t chybných symbolů, nebo vyhledat a opravit až ⌊ t /2⌋ chybných symbolů na neznámých místech . Jako mazací kód může opravit až t vymazání na místech, která jsou známá a poskytnuta algoritmu, nebo může detekovat a opravit kombinace chyb a vymazání. Reed-Solomon kódy jsou také vhodné jako vícenásobné roztržení opravovat kódy bitové chyby, protože sekvence b  + 1 po sobě následujících bitových chyb může mít vliv na nejvýše dva symboly velikost b . Volba t je na návrháři kódu a může být vybrána v širokých mezích.

Existují dva základní typy kódů Reed – Solomon - původní zobrazení a zobrazení BCH - přičemž nejčastější je zobrazení BCH, protože dekodéry zobrazení BCH jsou rychlejší a vyžadují méně pracovního úložiště než dekodéry původního zobrazení.

Dějiny

Kódy Reed – Solomon byly vyvinuty v roce 1960 Irvingem S. Reedem a Gustavem Solomonem , kteří byli tehdy zaměstnanci laboratoře MIT Lincoln Laboratory . Jejich klíčový článek měl název „Polynomiální kódy nad určitými konečnými poli“. ( Reed & Solomon 1960 ). Původní schéma kódování popsané v článku Reed & Solomon používalo variabilní polynom na základě zprávy, která má být kódována, kde je kodéru a dekodéru známa pouze pevná sada hodnot (vyhodnocovacích bodů), které mají být kódovány. Původní teoretický dekodér generoval potenciální polynomy na základě podmnožin k (délka nekódované zprávy) z n (kódované délky zprávy) hodnot přijaté zprávy, přičemž jako správný vybral nejoblíbenější polynom, což bylo nepraktické pro všechny, kromě nejjednodušších případy. To bylo původně vyřešeno změnou původního schématu na schéma podobné BCH kódu založené na pevném polynomu známém kodéru i dekodéru, ale později byly vyvinuty praktické dekodéry založené na původním schématu, i když pomalejší než schémata BCH. Výsledkem je, že existují dva hlavní typy kódů Reed Solomon, ty, které používají původní schéma kódování, a ty, které používají schéma kódování BCH.

Také v roce 1960 byl praktický fixní polynomiální dekodér pro BCH kódy vyvinutý Danielem Gorensteinem a Nealem Zierlerem popsán ve zprávě MIT Lincoln Laboratory od Zierlera v lednu 1960 a později v příspěvku v červnu 1961. Dekodér Gorenstein – Zierler a související práce o BCH kódech jsou popsány v knize Error Correcting Codes od W. Wesley Petersona (1961). V roce 1963 (nebo možná dříve) JJ Stone (a další) uznali, že kódy Reed Solomon by mohly používat schéma BCH pomocí polynomu s pevným generátorem, což z těchto kódů činí speciální třídu kódů BCH, ale kódy Reed Solomon založené na původním kódování schémata, nejsou třídou BCH kódů a v závislosti na sadě vyhodnocovacích bodů to nejsou ani cyklické kódy .

V roce 1969 vyvinuli vylepšený dekodér schématu BCH Elwyn Berlekamp a James Massey a od té doby je znám jako dekódovací algoritmus Berlekamp – Massey .

V roce 1975 vyvinul Yasuo Sugiyama další vylepšený dekodér schématu BCH na základě rozšířeného euklidovského algoritmu .

V roce 1977 byly v programu Voyager implementovány kódy Reed – Solomon ve formě spojených kódů pro opravu chyb . První komerční aplikace v sériově vyráběných spotřebních výrobcích se objevila v roce 1982 s kompaktním diskem , kde jsou použity dva prokládané kódy Reed-Solomon. Dnes jsou kódy Reed-Solomon široce implementovány v digitálních paměťových zařízeních a digitálních komunikačních standardech, i když jsou pomalu nahrazovány modernějšími kódy pro kontrolu parity s nízkou hustotou (LDPC) nebo turbo kódy . Například kódy Reed – Solomon se používají ve standardu DVB-S pro digitální video vysílání (DVB) , ale kódy LDPC se používají v jeho nástupci DVB-S2 .

V roce 1986 byl vyvinut originální dekodér schématu známý jako Berlekamp -Welchův algoritmus .

V roce 1996 vyvinul Madhu Súdán a další varianty původních schématických dekodérů nazývaných dekodéry seznamu nebo měkké dekodéry a práce na těchto typech dekodérů pokračují - viz dekódovací algoritmus seznamu Guruswami – Súdán .

V roce 2002 vyvinul Shuhong Gao další originální dekodér schématu na základě rozšířeného euklidovského algoritmu Gao_RS.pdf .

Aplikace

Datové úložiště

Kódování Reed -Solomon je v systémech velkokapacitních paměťových systémů velmi široce používáno k opravě chyb shluku spojených s vadami médií.

Kódování Reed – Solomon je klíčovou součástí kompaktního disku . Jednalo se o první použití silného kódování pro opravu chyb v sériově vyráběném spotřebním produktu a DAT a DVD používají podobná schémata. Na disku CD dvě vrstvy kódování Reed – Solomon oddělené 28cestným konvolučním prokládačem poskytují schéma nazvané Cross-Interleaved Reed – Solomon Coding ( CIRC ). Prvním prvkem dekodéru CIRC je relativně slabý vnitřní (32,28) kód Reed – Solomon, zkrácený z (255 251) kódu s 8bitovými symboly. Tento kód může opravit až 2 bajtové chyby na 32bajtový blok. Ještě důležitější je, že označí jako vymaže všechny neopravitelné bloky, tj. Bloky s více než 2 bajtovými chybami. Dekódované 28bajtové bloky s indikacemi vymazání jsou pak rozkládacím zařízením rozloženy do různých bloků (28,24) vnějšího kódu. Díky prokládání se ze vymazaného 28bajtového bloku z vnitřního kódu stane jeden vymazaný bajt v každém z 28 vnějších bloků kódu. Vnější kód to snadno opraví, protože dokáže zpracovat až 4 taková vymazání na blok.

Výsledkem je CIRC, který dokáže zcela opravit chybové shluky až 4000 bitů, tedy asi 2,5 mm na povrchu disku. Tento kód je tak silný, že většina chyb při přehrávání disků CD je téměř jistě způsobena chybami sledování, které způsobují, že laser přeskočí stopu, nikoli neopravitelnými chybovými výbuchy.

DVD používají podobné schéma, ale s mnohem většími bloky, (208,192) vnitřním kódem a (182,172) vnějším kódem.

Oprava chyb Reed – Solomon se používá také v parchivačních souborech, které jsou běžně zveřejňovány jako doprovodné multimediální soubory na USENET . Distribuovaná služba online úložiště Wuala (ukončena v roce 2015) také používala při rozdělování souborů Reed – Solomon.

Čárový kód

Téměř všechny dvojrozměrné čárové kódy, jako jsou PDF-417 , MaxiCode , Datamatrix , QR Code a aztécký kód, používají opravu chyb Reed – Solomon, aby bylo možné správné čtení i v případě poškození části čárového kódu. Pokud snímač čárových kódů nerozpozná symbol čárového kódu, bude to považovat za vymazání.

Kódování Reed – Solomon je v jednorozměrných čárových kódech méně obvyklé, ale používá ho symbolika PostBar .

Přenos dat

K překonání nespolehlivé povahy přenosu dat přes mazací kanály lze použít specializované formy kódů Reed – Solomon, konkrétně Cauchy -RS a Vandermonde -RS . Proces kódování předpokládá kód RS ( N ,  K ), jehož výsledkem je generování N kódových slov o délce N symbolů, z nichž každý ukládá K symbolů dat, která jsou poté odeslána přes vymazávací kanál.

Jakákoli kombinace K kódových slov přijatých na druhém konci stačí k rekonstrukci všech N kódových slov. Rychlost kódu je obecně nastavena na 1/2, pokud není možné dostatečně vymodelovat pravděpodobnost vymazání kanálu a je považována za menší. Závěrem lze říci, že N je obvykle 2 K , což znamená, že alespoň polovina všech odeslaných kódových slov musí být přijata, aby bylo možné rekonstruovat všechna odeslaná kódová slova.

Reed-Solomon kódy jsou také používány v xDSL systémů a CCSDS ‚s Space Communications Protocol specifikace jako forma dopřednou chybovou korekci .

Vesmírný přenos

Deep-space zřetězený kódovací systém. Zápis: RS (255, 223) + CC („délka omezení“ = 7, kódová rychlost = 1/2).

Jednou významnou aplikací kódování Reed -Solomon bylo zakódování digitálních obrázků odeslaných zpět programem Voyager .

Voyager představil kódování Reed -Solomon zřetězené s konvolučními kódy , což je postup, který se od té doby velmi rozšířil v komunikaci v hlubokém vesmíru a v satelitní (např. Přímé digitální vysílání).

Dekodéry Viterbi mají tendenci vytvářet chyby v krátkých dávkách. Oprava těchto chyb shluku se nejlépe provádí pomocí krátkých nebo zjednodušených kódů Reed – Solomon.

Moderní verze zřetězeného konvolučního kódování dekódovaného Reed – Solomon/Viterbi byly a jsou použity na misích Mars Pathfinder , Galileo , Mars Exploration Rover a Cassini , kde dosahují výkonu přibližně 1–1,5 dB od konečného limitu, Shannonovy kapacity .

Tyto zřetězené kódy jsou nyní nahrazovány výkonnějšími turbo kódy :

Konstrukce (kódování)

Kód Reed -Solomon je vlastně rodina kódů, kde každý kód je charakterizován třemi parametry: velikost abecedy q , délka bloku n a délka zprávy k, s k <n ≤ q. Sada symbolů abecedy je interpretována jako konečné pole řádu q , a proto q musí být primární mocninou . V nejužitečnějších parametrizacích Reed -Solomonova kódu je délka bloku obvykle nějaký konstantní násobek délky zprávy, to znamená, že rychlost R = k / n je nějaká konstanta, a navíc je délka bloku stejná nebo jedna menší než velikost abecedy, tj. n = q nebo n = q - 1 .

Původní pohled Reeda a Solomona: Kódové slovo jako posloupnost hodnot

Pro kód Reed – Solomon existují různé postupy kódování, a proto existují různé způsoby, jak popsat sadu všech kódových slov. V původním pohledu na Reeda a Solomona (1960) je každé kódové slovo kódu Reed – Solomon posloupností funkčních hodnot polynomu stupně menšího než k . Za účelem získání kódového slova Reed-Solomonova kódu jsou symboly zpráv (každý v abecedě velikosti q) považovány za koeficienty polynomu p stupně menšího než k , přes konečné pole F s q prvky. Na druhé straně je polynom p vyhodnocen v n ≤ q odlišných bodech pole F a posloupnost hodnot je odpovídající kódové slovo. Mezi běžné možnosti pro sadu hodnotících bodů patří {0, 1, 2, ..., n - 1}, {0, 1, α , α ² , ..., α ^{n −2} } nebo pro n < q {1, α , alfa ² , ..., α ^{n -1} }, ..., kde α je primitivní prvek z F . ${\ displaystyle a_ {1}, \ tečky, a_ {n}}$

Formálně je sada kódových slov kódu Reed – Solomon definována následovně: ${\ displaystyle \ mathbf {C}}$

${\ Displaystyle \ mathbf {C} = {\ Big \ {} \; {\ big (} p (a_ {1}), p (a_ {2}), \ tečky, p (a_ {n}) {\ velký)} \; {\ Velký |} \; p {\ text {je polynom nad}} F {\ text {stupně}} <k \; {\ Velký \}} \ ,.}$

Protože ve většině bodů jsou jakékoli dva odlišné polynomy méně než shodné , znamená to, že jakákoli dvě kódová slova kódu Reed -Solomon nesouhlasí alespoň v polohách. Kromě toho existují dva polynomy, které se shodují v bodech, ale nejsou si rovny, a proto je vzdálenost kódu Reed -Solomon přesně . Potom je relativní vzdálenost , kde je míra. Tento kompromis mezi relativní vzdálenosti a rychlosti je asymptoticky optimální, neboť až Singleton vázán , každý kód splňuje . Jako kód, který dosahuje tohoto optimálního kompromisu, patří kód Reed – Solomon do třídy kódů oddělitelných na maximální vzdálenost . ${\ displaystyle k}$${\ Displaystyle k-1}$${\ Displaystyle n- (k-1) = n-k+1}$${\ Displaystyle k-1}$${\ Displaystyle d = n-k+1}$${\ Displaystyle \ delta = d/n = 1-k/n+1/n = 1-R+1/n \ sim 1-R}$${\ Displaystyle R = k/n}$${\ Displaystyle \ delta +R \ leq 1 +1/n}$

Zatímco počet různých polynomů stupně menší než k a počet různých zpráv jsou oba stejné a každá zpráva může být jedinečně mapována na takový polynom, existují různé způsoby, jak toto kódování provést. Původní konstrukce Reeda a Solomona (1960) interpretuje zprávu x jako koeficienty polynomu p , zatímco následující konstrukce interpretují zprávu jako hodnoty polynomu v prvních k bodech a získají polynom p p interpolací těchto hodnot pomocí a polynom stupně menší než k . Druhý kódovací postup, i když je o něco méně účinný, má tu výhodu, že dává vznik systematickému kódu , to znamená, že původní zpráva je vždy obsažena jako podsekce kódového slova. ${\ displaystyle q^{k}}$${\ displaystyle a_ {1}, \ tečky, a_ {k}}$

Jednoduchý postup kódování: Zpráva jako posloupnost koeficientů

V původní konstrukci Reeda a Solomona (1960) je zpráva mapována na polynom s ${\ Displaystyle x = (x_ {1}, \ tečky, x_ {k}) \ v F^{k}}$${\ displaystyle p_ {x}}$

${\ Displaystyle p_ {x} (a) = \ sum _ {i = 1}^{k} x_ {i} a^{i-1} \ ,.}$

Kódové slovo pro se získá vyhodnocením v různých bodech pole . Klasická kódovací funkce pro Reed -Solomonův kód je tedy definována následovně: ${\ displaystyle x}$${\ displaystyle p_ {x}}$${\ displaystyle n}$${\ displaystyle a_ {1}, \ tečky, a_ {n}}$${\ displaystyle F}$${\ Displaystyle C: F^{k} \ až F^{n}}$

${\ Displaystyle C (x) = {\ big (} p_ {x} (a_ {1}), \ tečky, p_ {x} (a_ {n}) {\ velké)} \ ,.}$

Tato funkce je lineární mapování , to znamená, že splňuje následující matici s prvky z : ${\ displaystyle C}$${\ Displaystyle C (x) = x^{T} \ cdot A}$${\ displaystyle (k \ times n)}$${\ displaystyle A}$${\ displaystyle F}$

${\ Displaystyle A = {\ begin {bmatrix} 1 & \ dots & 1 & \ dots & 1 \\ a_ {1} & \ dots & a_ {k} & \ dots & a_ {n} \\ a_ {1}^{2} & \ tečky & a_ {k}^{2} & \ tečky & a_ {n}^{2} \\\ vdots && \ vdots && \ vdots \\ a_ {1}^{k-1} & \ dots & a_ {k}^ {k-1} & \ dots & a_ {n}^{k-1} \ end {bmatrix}}}$

Tato matice je přemístit z matrice Vandermonde nad . Jinými slovy, Reed-Solomonův kód je lineární kód , a v klasickém kódování řízení, jeho generátor matice je . ${\ displaystyle F}$${\ displaystyle A}$

Systematický postup kódování: Zpráva jako počáteční posloupnost hodnot

Existuje alternativní postup kódování, který také produkuje kód Reed -Solomon, ale dělá to systematickým způsobem. Zde funguje mapování ze zprávy na polynom jinak: polynom je nyní definován jako jedinečný polynom stupně menšího než takového, že ${\ displaystyle x}$${\ displaystyle p_ {x}}$${\ displaystyle p_ {x}}$${\ displaystyle k}$

${\ displaystyle p_ {x} (a_ {i}) = x_ {i}}$platí pro všechny .${\ Displaystyle i \ in \ {1, \ dots, k \}}$

Pro výpočet tohoto polynomu od , jeden může používat Lagrange interpolace . Jakmile je nalezen, je vyhodnocen v ostatních bodech pole. Alternativní kódovací funkce pro kód Reed – Solomon je pak opět jen posloupnost hodnot: ${\ displaystyle p_ {x}}$${\ displaystyle x}$${\ Displaystyle a_ {k+1}, \ tečky, a_ {n}}$${\ Displaystyle C: F^{k} \ až F^{n}}$

${\ Displaystyle C (x) = {\ big (} p_ {x} (a_ {1}), \ tečky, p_ {x} (a_ {n}) {\ velké)} \ ,.}$

Protože se první položky každého kódového slova shodují s , je tento postup kódování skutečně systematický . Protože Lagrangeova interpolace je lineární transformace, je lineární mapování. Ve skutečnosti máme , kde ${\ displaystyle k}$${\ Displaystyle C (x)}$${\ displaystyle x}$${\ displaystyle C}$${\ Displaystyle C (x) = x \ cdot G}$

${\ displaystyle G = (A {\ text {'s square submatrix}})^{-1} \ cdot A = {\ begin {bmatrix} 1 & 0 & 0 & \ dots & 0 & g_ {1, k+1} & \ dots & g_ { 1, n} \\ 0 & 1 & 0 & \ dots & 0 & g_ {2, k+1} & \ dots & g_ {2, n} \\ 0 & 0 & 1 & \ dots & 0 & g_ {3, k+1} & \ dots & g_ {3, n} \\ \ vdots & \ vdots & \ vdots && \ vdots & \ vdots && \ vdots \\ 0 & \ dots & 0 & \ dots & 1 & g_ {k, k+1} & \ dots & g_ {k, n} \ end {bmatrix}}}$

Diskrétní Fourierova transformace a její inverze

Diskrétní Fourierova transformace je v podstatě stejný jako postup kódování; používá polynom generátoru p (x) k mapování sady vyhodnocovacích bodů do hodnot zprávy, jak je uvedeno výše:

${\ Displaystyle C (x) = {\ big (} p_ {x} (a_ {1}), \ tečky, p_ {x} (a_ {n}) {\ velké)} \ ,.}$

Inverzní Fourierovu transformaci by bylo možné použít k převodu bezchybné sady hodnot n < q zpráv zpět do kódovacího polynomu k koeficientů k , s omezením, že aby to fungovalo, musí sada vyhodnocovacích bodů použitých ke kódování zprávy být množinou rostoucích sil α :

${\ Displaystyle a_ {i} = \ alpha ^{i-1}}$

${\ Displaystyle a_ {1}, \ dots, a_ {n} = \ {1, \ alpha, \ alpha ^{2}, \ dots, \ alpha ^{n-1} \}}$

Lagrangeova interpolace však provádí stejnou konverzi bez omezení na sadu vyhodnocovacích bodů nebo požadavku bezchybné sady hodnot zpráv a používá se pro systematické kódování a v jednom z kroků Gao dekodéru .

Pohled BCH: Kódové slovo jako posloupnost koeficientů

V tomto pohledu je zpráva interpretována jako koeficienty polynomu . Odesílatel počítá související polynom stupne kde a odešle polynom . Polynom je vytvořen vynásobením polynomu zprávy , který má stupeň , polynomem generátoru stupně, který je známý odesílateli i příjemci. Polynom generátoru je definován jako polynom, jehož kořeny jsou sekvenční mocnosti primitiva Galoisova pole${\ displaystyle p (x)}$${\ displaystyle s (x)}$${\ Displaystyle n-1}$${\ Displaystyle n \ leq q-1}$${\ displaystyle s (x)}$${\ displaystyle s (x)}$${\ displaystyle p (x)}$${\ Displaystyle k-1}$ ${\ displaystyle g (x)}$${\ displaystyle nk}$${\ displaystyle g (x)}$${\ Displaystyle \ alpha}$

${\ Displaystyle g (x) = (x- \ alpha ^{i}) (x- \ alpha ^{i+1}) \ cdots (x- \ alpha ^{i+nk-1}) = g_ {0 }+g_ {1} x+\ cdots+g_ {nk-1} x^{nk-1}+x^{nk}}$

Pro „úzkém slova smyslu kódu“ . ${\ displaystyle i = 1}$

${\ Displaystyle \ mathbf {C} = \ left \ {\ left (s_ {1}, s_ {2}, \ dots, s_ {n} \ right) \; {\ Big |} \; s (a) = \ sum _ {i = 1} ^{n} s_ {i} a ^{i} {\ text {je polynom, který má alespoň kořeny}} \ alpha ^{1}, \ alpha ^{2}, \ tečky, \ alpha ^{nk} \ vpravo \} \ ,.}$

Systematický postup kódování

Proceduru kódování pro zobrazení BCH kódů Reed -Solomon lze upravit tak, aby poskytovala systematický postup kódování , ve kterém každé kódové slovo obsahuje zprávu jako předponu a jednoduše přidává symboly opravující chyby jako příponu. Zde místo odesílání kodér konstruuje přenesený polynom tak, že koeficienty největších monomiálů se rovnají odpovídajícím koeficientům a koeficienty nižšího řádu jsou vybrány přesně takovým způsobem, který je dělitelný . Pak jsou koeficienty koeficientem posloupnosti koeficientů . Abychom získali kód, který je celkově systematický, konstruujeme polynom zprávy tak, že zprávu interpretujeme jako posloupnost jejích koeficientů. ${\ Displaystyle s (x) = p (x) g (x)}$${\ displaystyle s (x)}$${\ displaystyle k}$${\ displaystyle p (x)}$${\ displaystyle s (x)}$${\ displaystyle s (x)}$${\ displaystyle g (x)}$${\ displaystyle p (x)}$${\ displaystyle s (x)}$${\ displaystyle p (x)}$

Formálně se konstrukce provádí vynásobením , aby se vytvořil prostor pro kontrolní symboly, rozdělením tohoto produktu na nalezení zbytku a následným kompenzováním tohoto zbytku jeho odečtením. Tyto kontrolní symboly jsou vytvořeny tím, že počítá zbytek : ${\ displaystyle p (x)}$${\ displaystyle x^{t}}$${\ displaystyle t = nk}$${\ displaystyle g (x)}$${\ displaystyle t}$${\ displaystyle s_ {r} (x)}$

${\ Displaystyle s_ {r} (x) = p (x) \ cdot x^{t} \ {\ bmod {\}} g (x).}$

Zbytek má nejvýše stupeň , zatímco koeficienty v polynomu jsou nulové. Následující definice kódového slova má tedy tu vlastnost, že první koeficienty jsou totožné s koeficienty : ${\ displaystyle t-1}$${\ Displaystyle x^{t-1}, x^{t-2}, \ tečky, x^{1}, x^{0}}$${\ Displaystyle p (x) \ cdot x^{t}}$${\ displaystyle s (x)}$${\ displaystyle k}$${\ displaystyle p (x)}$

${\ Displaystyle s (x) = p (x) \ cdot x^{t} -s_ {r} (x) \ ,.}$

Výsledkem je, že kódová slova jsou skutečně prvky , to znamená, že jsou dělitelná polynomem generátoru : ${\ displaystyle s (x)}$${\ displaystyle \ mathbf {C}}$${\ displaystyle g (x)}$

${\ Displaystyle s (x) \ equiv p (x) \ cdot x^{t} -s_ {r} (x) \ equiv s_ {r} (x) -s_ {r} (x) \ equiv 0 \ mod g (x) \ ,.}$

Vlastnosti

Kód Reed – Solomon je kód [ n , k , n - k + 1]; jinými slovy, je to lineární blokový kód délky n (přes F ) s rozměrem k a minimální Hammingovou vzdáleností Reedův -Solomonův kód je optimální v tom smyslu, že minimální vzdálenost má maximální možnou hodnotu pro lineární kód velikosti ( n ,  k ); toto je známé jako Singleton vázané . Takový kód se také nazývá kód oddělitelný na maximální vzdálenost (MDS) . ${\ textstyle d _ {\ min} = n-k+1.}$

Schopnost opravovat chyby kódu Reed-Solomon je určena jeho minimální vzdáleností nebo ekvivalentně mírou nadbytečnosti v bloku. Pokud umístění chybových symbolů není předem známo, pak kód Reed – Solomon dokáže opravit až chybné symboly, tj. Dokáže opravit polovinu chyb, kolik je do bloku přidáno nadbytečných symbolů. Někdy jsou místa chyb známa předem (např. „Boční informace“ v poměrech signálu k šumu demodulátoru )-tomu se říká vymazání . Reed -Solomonův kód (jako jakýkoli kód MDS ) je schopen opravit dvakrát tolik vymazání než chyb a jakoukoli kombinaci chyb a vymazání lze opravit, pokud je splněn vztah 2 E  +  S  ≤  n  -  k , kde je počet chyb a počet vymazání v bloku. ${\ displaystyle nk}$${\ displaystyle (nk)/2}$ ${\ displaystyle E}$${\ displaystyle S}$

Teoretická BER výkonnost Reed-Solomonova kódu (N = 255, K = 233, QPSK, AWGN). Kroková charakteristika.

Teoretickou mez chyby lze popsat pomocí následujícího vzorce pro kanál AWGN pro FSK :

${\ Displaystyle P_ {b} \ cca {\ frac {2^{m-1}} {2^{m} -1}} {\ frac {1} {n}} \ sum _ {\ ell = t+ 1}^{n} \ ell {n \ choose \ ell} P_ {s}^{\ ell} (1-P_ {s})^{n- \ ell}}$

a pro další schémata modulace:

${\ Displaystyle P_ {b} \ cca {\ frac {1} {m}} {\ frac {1} {n}} \ sum _ {\ ell = t+1}^{n} \ ell {n \ vybrat \ ell} P_ {s}^{\ ell} (1-P_ {s})^{n- \ ell}}$

kde , , , je chybovost symbolů v nekódované AWGN případě, a je pořadí modulace. ${\ Displaystyle t = {\ frac {1} {2}} (d _ {\ min} -1)}$${\ Displaystyle P_ {s} = 1- (1 s)^{h}}$${\ displaystyle h = {\ frac {m} {\ log _ {2} M}}}$${\ displaystyle s}$${\ displaystyle M}$

Pro praktické použití Reed -Solomonových kódů je běžné používat konečné pole s prvky. V tomto případě může být každý symbol reprezentován jako -bitová hodnota. Odesílatel odešle datové body jako kódované bloky a počet symbolů v kódovaném bloku je . Kód Reed-Solomon pracující na 8bitových symbolech má tedy symboly na blok. (To je velmi populární hodnota z důvodu výskytu byte orientovaných počítačových systémů.) Číslo , s , z datových symbolů v bloku je parametr konstrukce. Běžně používaný kód kóduje osmibitové datové symboly plus 32 osmibitových paritních symbolů v bloku -symbol; toto je označeno jako kód a je schopno opravit až 16 chyb symbolu na blok. ${\ displaystyle F}$${\ displaystyle 2^{m}}$${\ displaystyle m}$${\ Displaystyle n = 2^{m} -1}$${\ Displaystyle n = 2^{8} -1 = 255}$${\ displaystyle k}$${\ displaystyle k <n}$${\ displaystyle k = 223}$${\ displaystyle n = 255}$${\ Displaystyle (n, k) = (255,223)}$

Vlastnosti kódu Reed-Solomon popsané výše je činí obzvláště vhodnými pro aplikace, kde dochází k chybám v sekvencích . Důvodem je, že pro kód nezáleží na tom, kolik bitů v symbolu je chybných - pokud je poškozeno více bitů v symbolu, počítá se to pouze jako jedna chyba. Naopak, pokud datový tok není charakterizován shluky chyb nebo výpadky, ale náhodnými jednobitovými chybami, je Reed-Solomonův kód obvykle špatnou volbou ve srovnání s binárním kódem.

Kód Reed -Solomon, stejně jako konvoluční kód , je transparentní kód. To znamená, že pokud byly symboly kanálů obráceny někde podél čáry, dekodéry budou stále fungovat. Výsledkem bude inverze původních dat. Kód Reed – Solomon však ztrácí svou průhlednost, když je kód zkrácen. „Chybějící“ bity ve zkráceném kódu je třeba vyplnit buď nulami, nebo jedničkami, podle toho, zda jsou data doplněna či nikoli. (Jinak řečeno, pokud jsou symboly invertovány, pak nulovou výplň je třeba převést na jednu výplň.) Z tohoto důvodu je povinné, aby byl vyřešen smysl dat (tj. Pravdivý nebo doplněný). před dekódováním Reed – Solomon.

Zda je kód Reed – Solomon cyklický nebo ne, závisí na jemných detailech konstrukce. V původním pohledu na Reeda a Solomona, kde jsou kódová slova hodnotami polynomu, lze zvolit posloupnost vyhodnocovacích bodů takovým způsobem, aby byl kód cyklický. Zejména pokud je primitivní kořen pole , pak podle definice všechny nenulové prvky mají formu pro , kde . Každý polynom nad vyvolává kódové slovo . Protože funkce je také polynom stejného stupně, dává tato funkce vzniknout kódovému slovu ; protože platí, toto kódové slovo je cyklický posun vlevo od původního kódového slova odvozeného z . Takže výběr posloupnosti primitivních kořenových sil jako hodnotících bodů způsobí, že původní pohled Reed – Solomonův kód bude cyklický . Reed – Solomonovy kódy v zobrazení BCH jsou vždy cyklické, protože kódy BCH jsou cyklické . ${\ Displaystyle \ alpha}$${\ displaystyle F}$${\ displaystyle F}$${\ displaystyle \ alpha ^{i}}$${\ Displaystyle i \ in \ {1, \ dots, q-1 \}}$${\ displaystyle q = | F |}$${\ displaystyle p}$${\ displaystyle F}$${\ Displaystyle (p (\ alpha ^{1}), \ dots, p (\ alpha ^{q-1}))}$${\ Displaystyle a \ mapsto p (\ alpha a)}$${\ Displaystyle (p (\ alpha ^{2}), \ dots, p (\ alpha ^{q}))}$${\ Displaystyle \ alpha ^{q} = \ alpha ^{1}}$${\ displaystyle p}$

Poznámky

Návrháři nejsou povinni používat „přirozené“ velikosti bloků kódu Reed – Solomon. Technika známá jako „zkracování“ může z většího kódu vytvořit menší kód libovolné požadované velikosti. Například široce používaný (255,223) kód lze převést na (160,128) kód vyplněním nepoužité části zdrojového bloku 95 binárními nulami a jejich nevysíláním. V dekodéru je stejná část bloku lokálně načtena s binárními nulami. Věta Delsarte – Goethals – Seidel ilustruje příklad aplikace zkrácených kódů Reed – Solomon. Souběžně se zkracováním umožňuje technika známá jako punktování vynechat některé z kódovaných paritních symbolů.

Zobrazit dekodéry BCH

Dekodéry popsané v této části používají pohled BCH kódového slova jako posloupnost koeficientů. Používají pevný generátorový polynom známý kodéru i dekodéru.

Dekodér Peterson – Gorenstein – Zierler

Daniel Gorenstein a Neal Zierler vyvinuli dekodér, který byl popsán ve zprávě MIT Lincoln Laboratory od Zierlera v lednu 1960 a později v článku v červnu 1961. Dekodér Gorenstein -Zierler a související práce na BCH kódech jsou popsány v knize Error Correcting kódy podle W. Wesley Peterson (1961).

Formulace

Na přenášenou zprávu ,, se pohlíží jako na koeficienty polynomu s ( x ): ${\ Displaystyle (c_ {0}, \ ldots, c_ {i}, \ ldots, c_ {n-1})}$

${\ Displaystyle s (x) = \ sum _ {i = 0}^{n-1} c_ {i} x^{i}}$

V důsledku procedury kódování Reed-Solomon je s ( x ) dělitelné generátorovým polynomem g ( x ):

${\ Displaystyle g (x) = \ prod _ {j = 1} ^{nk} (x- \ alpha ^{j}),}$

kde α je primitivní kořen.

Protože s ( x ) je násobkem generátoru g ( x ), vyplývá z toho, že „dědí“ všechny své kořeny:

${\ Displaystyle s (\ alpha ^{j}) = 0, \ j = 1,2, \ ldots, nk}$

Přenesený polynom je při přenosu poškozen chybovým polynomem e ( x ) za vzniku přijatého polynomu r ( x ).

${\ Displaystyle r (x) = s (x)+e (x)}$

${\ Displaystyle e (x) = \ sum _ {i = 0}^{n-1} e_ {i} x^{i}}$

Koeficient e _i bude nulový, pokud nedojde k chybě při tomto výkonu x, a nenulový, pokud dojde k chybě. Pokud jsou vmax chyby na odlišných sil i _k o x , potom

${\ Displaystyle e (x) = \ sum _ {k = 1}^{\ nu} e_ {i_ {k}} x^{i_ {k}}}$

Cílem dekodéru je zjistit počet chyb ( ν ), polohy chyb ( i _k ) a chybové hodnoty v těchto polohách ( e _{i k} ). Z nich lze vypočítat e ( x ) a odečíst od r ( x ), abychom získali původně odeslanou zprávu s ( x ).

Dekódování syndromu

Dekodér začíná vyhodnocením polynomu přijatého v bodech . Výsledky tohoto hodnocení nazýváme „syndromy“, S _j . Jsou definovány jako: ${\ Displaystyle \ alpha ^{1} \ dots \ alpha ^{nk}}$

${\ Displaystyle {\ begin {aligned} S_ {j} & = r (\ alpha ^{j}) = s (\ alpha ^{j})+e (\ alpha ^{j}) = 0+e (\ alfa ^{j}) = e (\ alpha ^{j}), \ j = 1,2, \ ldots, nk \\ & = \ sum _ {k = 1} ^{\ nu} e_ {i_ {k }} \ left (\ alpha ^{j} \ right) ^{i_ {k}} \ end {aligned}}}$

Výhodou pohledu na syndromy je, že vypadne polynom zprávy. Jinými slovy, syndromy se týkají pouze chyby a nejsou ovlivněny skutečným obsahem přenášené zprávy. Pokud jsou všechny syndromy nulové, algoritmus se zde zastaví a oznámí, že zpráva nebyla při přenosu poškozena.

Lokátory chyb a hodnoty chyb

Pro usnadnění definujte lokátory chyb X _k a chybové hodnoty Y _k jako:

${\ Displaystyle X_ {k} = \ alpha ^{i_ {k}}, \ Y_ {k} = e_ {i_ {k}}}$

Pak lze syndromy zapsat pomocí těchto lokátorů chyb a hodnot chyb jako

${\ Displaystyle S_ {j} = \ sum _ {k = 1}^{\ nu} Y_ {k} X_ {k}^{j}}$

Tato definice hodnot syndromu je ekvivalentní předchozí od té doby . ${\ Displaystyle (\ alpha ^{j}) ^{i_ {k}} = \ alpha ^{j*i_ {k}} = (\ alpha ^{i_ {k}}) ^{j} = X_ {k }^{j}}$

Syndromy dávají systém n  -  k ≥ 2 ν rovnic ve 2 v neznámých, ale tento systém rovnic je v X _k nelineární a nemá zřejmé řešení. Pokud by však bylo známo X _k (viz níže), pak rovnice syndromu poskytují lineární systém rovnic, které lze snadno vyřešit pro chybové hodnoty Y _k .

${\ displaystyle {\ begin {bmatrix} X_ {1}^{1} & X_ {2}^{1} & \ cdots & X _ {\ nu}^{1} \\ X_ {1}^{2} & X_ {2 }^{2} & \ cdots & X _ {\ nu}^{2} \\\ vdots & \ vdots && \ vdots \\ X_ {1}^{nk} & X_ {2}^{nk} & \ cdots & X_ { \ nu}^{nk} \\\ end {bmatrix}} {\ begin {bmatrix} Y_ {1} \\ Y_ {2} \\\ vdots \\ Y _ {\ nu} \ end {bmatrix}} = = \ begin {bmatrix} S_ {1} \\ S_ {2} \\\ vdots \\ S_ {nk} \ end {bmatrix}}}$

V důsledku toho je problém najít X _k , protože pak by byla známá matice úplně vlevo a obě strany rovnice by mohly být vynásobeny její inverzí, čímž se získá Y _k

Ve variantě tohoto algoritmu, kde je umístění chyb již známé (když se používá jako kód pro mazání ), to je konec. Místa chyb ( X _k ) jsou již známa nějakou jinou metodou (například v FM přenosu jsou úseky, kde bitový tok byl nejasný nebo překonaný interferencí, pravděpodobnostně určitelné z frekvenční analýzy). V tomto scénáři lze opravit až chyby. ${\ displaystyle nk}$

Zbývající část algoritmu slouží k lokalizaci chyb a bude vyžadovat hodnoty syndromu až místo dosud používaných. To je důvod, proč je třeba přidat 2 x tolik symbolů opravujících chyby, kolik lze opravit bez znalosti jejich umístění. ${\ displaystyle 2v}$${\ displaystyle v}$

Polynom lokátoru chyb

Existuje lineární relační relace, která dává vznik systému lineárních rovnic. Řešení těchto rovnic identifikuje tato chybová místa X _k .

Definujte polynom lokátoru chyb Λ ( x ) jako

${\ Displaystyle \ Lambda (x) = \ prod _ {k = 1}^{\ nu} (1-xX_ {k}) = 1+ \ Lambda _ {1} x^{1}+\ Lambda _ {2 } x^{2} +\ cdots +\ Lambda _ {\ nu} x^{\ nu}}$

Nuly Λ ( x ) jsou převrácené hodnoty . To vyplývá z výše uvedené konstrukce zápisu produktu, protože pokud pak jeden z vynásobených výrazů bude nula , celý polynom se vyhodnotí na nulu. ${\ displaystyle X_ {k}^{-1}}$${\ displaystyle x = X_ {k}^{-1}}$${\ Displaystyle (1-X_ {k}^{-1} \ cdot X_ {k}) = 1-1 = 0}$

${\ Displaystyle \ Lambda (X_ {k}^{-1}) = 0}$

Nechť je jakékoli takové celé číslo . Vynásobte obě strany a stále bude nula. ${\ displaystyle j}$${\ Displaystyle 1 \ leq j \ leq \ nu}$${\ Displaystyle Y_ {k} X_ {k}^{j+\ nu}}$

${\ Displaystyle {\ begin {aligned} & Y_ {k} X_ {k}^{j+\ nu} \ Lambda (X_ {k}^{-1}) = 0. \\ & Y_ {k} X_ {k}^ {j+\ nu} (1+ \ Lambda _ {1} X_ {k}^{-1}+\ Lambda _ {2} X_ {k}^{-2}+\ cdots+\ Lambda _ {\ nu} X_ {k}^{-\ nu}) = 0. \\ & Y_ {k} X_ {k}^{j+\ nu}+\ Lambda _ {1} Y_ {k} X_ {k}^{j+\ nu } X_ {k}^{-1}+\ Lambda _ {2} Y_ {k} X_ {k}^{j+\ nu} X_ {k}^{-2}+\ cdots+\ Lambda _ {\ nu } Y_ {k} X_ {k}^{j+\ nu} X_ {k}^{-\ nu} = 0. \\ & Y_ {k} X_ {k}^{j+\ nu}+\ Lambda _ {1 } Y_ {k} X_ {k}^{j+\ nu -1}+\ Lambda _ {2} Y_ {k} X_ {k}^{j+\ nu -2}+\ cdots+\ Lambda _ {\ nu } Y_ {k} X_ {k}^{j} = 0. \\\ end {zarovnaný}}}$

Součet pro k = 1 až ν a stále bude nula.

${\ Displaystyle {\ begin {aligned} & \ sum _ {k = 1}^{\ nu} \ left (Y_ {k} X_ {k}^{j+\ nu}+\ Lambda _ {1} Y_ {k } X_ {k}^{j+\ nu -1}+\ Lambda _ {2} Y_ {k} X_ {k}^{j+\ nu -2}+\ cdots+\ Lambda _ {\ nu} Y_ {k } X_ {k}^{j} \ right) = 0 \\\ end {zarovnaný}}}$

Shromážděte každý výraz do jeho součtu.

${\ Displaystyle {\ begin {aligned} & \ left (\ sum _ {k = 1}^{\ nu} Y_ {k} X_ {k}^{j+\ nu} \ right)+\ left (\ sum _ {k = 1}^{\ nu} \ Lambda _ {1} Y_ {k} X_ {k}^{j+\ nu -1} \ right)+\ left (\ sum _ {k = 1}^{\ nu} \ Lambda _ {2} Y_ {k} X_ {k}^{j+\ nu -2} \ right)+\ cdots+\ left (\ sum _ {k = 1}^{\ nu} \ Lambda _ {\ nu} Y_ {k} X_ {k}^{j} \ right) = 0 \ end {aligned}}}$

Extrahujte konstantní hodnoty, které nejsou součtem ovlivněny. ${\ Displaystyle \ Lambda}$

${\ Displaystyle {\ begin {aligned} & \ left (\ sum _ {k = 1}^{\ nu} Y_ {k} X_ {k}^{j+\ nu} \ right)+\ Lambda _ {1} \ left (\ sum _ {k = 1}^{\ nu} Y_ {k} X_ {k}^{j+\ nu -1} \ right)+\ Lambda _ {2} \ left (\ sum _ {k = 1}^{\ nu} Y_ {k} X_ {k}^{j+\ nu -2} \ right)+\ cdots+\ Lambda _ {\ nu} \ left (\ sum _ {k = 1}^ {\ nu} Y_ {k} X_ {k}^{j} \ right) = 0 \ end {aligned}}}$

Tyto souhrny jsou nyní ekvivalentní hodnotám syndromu, které známe a můžeme je nahradit! Tím se snižuje na

${\ Displaystyle S_ {j+\ nu}+\ Lambda _ {1} S_ {j+\ nu -1}+\ cdots+\ Lambda _ {\ nu -1} S_ {j+1}+\ Lambda _ {\ nu } S_ {j} = 0 \,}$

Odečtením výnosů z obou stran ${\ displaystyle S_ {j+\ nu}}$

${\ Displaystyle S_ {j} \ Lambda _ {\ nu}+S_ {j+1} \ Lambda _ {\ nu -1}+\ cdots+S_ {j+\ nu -1} \ Lambda _ {1} = - S_ {j+\ nu} \}$

Připomeňme, že j bylo vybráno jako jakékoli celé číslo mezi 1 a v včetně a tato ekvivalence platí pro všechny a všechny tyto hodnoty. Proto máme v lineární rovnice, nejen jednu. Tento systém lineárních rovnic lze proto vyřešit pro koeficienty Λ _i polynomu umístění chyby:

${\ displaystyle {\ begin {bmatrix} S_ {1} & S_ {2} & \ cdots & S _ {\ nu} \\ S_ {2} & S_ {3} & \ cdots & S _ {\ nu +1} \\\ vdots & \ vdots && \ vdots \\ S _ {\ nu} & S _ {\ nu +1} & \ cdots & S_ {2 \ nu -1} \ end {bmatrix}} {\ begin {bmatrix} \ Lambda _ {\ nu} \ \\ Lambda _ {\ nu -1} \\\ vdots \\\ Lambda _ {1} \ end {bmatrix}} = {\ begin {bmatrix} -S _ {\ nu +1} \\-S _ {\ nu +2} \\\ vdots \\-S _ {\ nu +\ nu} \ end {bmatrix}}}$

Výše uvedené předpokládá, že dekodér zná počet chyb ν , ale toto číslo ještě nebylo určeno. PGZ dekodér neurčuje ν přímo, ale spíše jej vyhledává zkoušením po sobě jdoucích hodnot. Dekodér nejprve převezme největší hodnotu pro pokus ν a nastaví lineární systém pro tuto hodnotu. Pokud lze rovnice vyřešit (tj. Determinant matice je nenulový), pak tato zkušební hodnota je počet chyb. Pokud lineární systém nelze vyřešit, pak se pokus ν sníží o jeden a zkoumá se další menší systém. ( Gill nd , str. 35)

Najděte kořeny polynomu lokátoru chyb

Pomocí koeficientů Λ _i nalezených v posledním kroku vytvořte polynom umístění chyby. Kořeny polynomu umístění chyby lze nalézt vyčerpávajícím vyhledáváním. Lokátory chyb X _k jsou převrácené hodnoty těchto kořenů. Pořadí koeficientů polynomu umístění chyby lze obrátit, v takovém případě jsou kořeny tohoto obráceného polynomu lokátory chyb (nikoli jejich převrácené hodnoty ). Chien search je efektivní implementace tohoto kroku. ${\ displaystyle X_ {k}}$${\ displaystyle X_ {k}^{-1}}$

Vypočítejte chybové hodnoty

Jakmile jsou známy lokátory chyb X _k , lze určit chybové hodnoty. To lze provést přímým řešením pro Y _k v matici chybových rovnic uvedených výše, nebo pomocí Forneyova algoritmu .

Vypočítejte umístění chyb

Vypočítat i _k tím, že základna protokolu z X _k . To se obecně provádí pomocí předem vypočítané vyhledávací tabulky. ${\ Displaystyle \ alpha}$

Opravte chyby

Nakonec se e (x) vygeneruje z i _k a e _{i k} a poté se odečte od r (x), aby se získala původně odeslaná zpráva s (x), s opravenými chybami.

Příklad

Zvažte kód Reed – Solomon definovaný v GF (929) s α = 3 a t = 4 (používá se v čárových kódech PDF417 ) pro kód RS (7,3). Polynom generátoru je

${\ Displaystyle g (x) = (x-3) (x-3^{2}) (x-3^{3}) (x-3^{4}) = x^{4}+809x^{ 3}+723x^{2}+568x+522}$

Pokud je polynom zprávy p ( x ) = 3 x ² + 2 x + 1 , pak je systematické kódové slovo zakódováno následovně.

${\ Displaystyle s_ {r} (x) = p (x) \, x^{t} \ mod g (x) = 547x^{3}+738x^{2}+442x+455}$

${\ Displaystyle s (x) = p (x) \, x^{t} -s_ {r} (x) = 3x^{6}+2x^{5}+1x^{4}+382x^{3 }+191x^{2}+487x+474}$

Chyby v přenosu mohou způsobit, že bude místo toho přijato.

${\ Displaystyle r (x) = s (x)+e (x) = 3x^{6}+2x^{5}+123x^{4}+456x^{3}+191x^{2}+487x+ 474}$

Syndromy se vypočítají vyhodnocením r při silách α .

${\ Displaystyle S_ {1} = r (3^{1}) = 3 \ cdot 3^{6} +2 \ cdot 3^{5} +123 \ cdot 3^{4} +456 \ cdot 3^{ 3} +191 \ cdot 3^{2} +487 \ cdot 3+474 = 732}$

${\ Displaystyle S_ {2} = r (3^{2}) = 637, \; S_ {3} = r (3^{3}) = 762, \; S_ {4} = r (3^{4 }) = 925}$

${\ displaystyle {\ begin {bmatrix} 732 & 637 \\ 637 & 762 \ end {bmatrix}} {\ begin {bmatrix} \ Lambda _ {2} \\\ Lambda _ {1} \ end {bmatrix}} = {\ begin { bmatrix} -762 \\-925 \ end {bmatrix}} = {\ begin {bmatrix} 167 \\ 004 \ end {bmatrix}}}$

Pomocí Gaussovy eliminace :

${\ Displaystyle {\ begin {bmatrix} 001 & 000 \\ 000 & 001 \ end {bmatrix}} {\ begin {bmatrix} \ Lambda _ {2} \\\ Lambda _ {1} \ end {bmatrix}} = {\ begin { bmatrix} 329 \\ 821 \ end {bmatrix}}}$

Λ (x) = 329 x ² + 821 x + 001, s kořeny x ₁ = 757 = 3 ⁻³ a x ₂ = 562 = 3 ⁻⁴

Koeficienty lze obrátit, aby vznikly kořeny s kladnými exponenty, ale obvykle se to nepoužívá:

R (x) = 001 x ² + 821 x + 329, s kořeny 27 = 3 ³ a 81 = 3 ⁴

s logem kořenů odpovídajícím chybovým místům (zprava doleva, umístění 0 je poslední výraz v kódovém slovu).

Chcete -li vypočítat hodnoty chyb, použijte algoritmus Forney .

Ω (x) = S (x) Λ (x) mod x ⁴ = 546 x + 732

Λ '(x) = 658 x + 821

e ₁ = −Ω (x ₁ )/Λ '(x ₁ ) = 074

e ₂ = −Ω (x ₂ )/Λ '(x ₂ ) = 122

Odečtením od přijatého polynomu r (x) se reprodukuje původní kódové slovo s . ${\ Displaystyle e_ {1} x^{3}+e_ {2} x^{4} = 74x^{3}+122x^{4}}$

Dekodér Berlekamp – Massey

Algoritmus Berlekamp-Massey je alternativní iterační postup pro zjištění chyby lokátoru polynom. Během každé iterace vypočítá nesrovnalost na základě aktuální instance Λ (x) s předpokládaným počtem chyb e :

${\ Displaystyle \ Delta = S_ {i}+\ Lambda _ {1} \ S_ {i-1}+\ cdots+\ Lambda _ {e} \ S_ {ie}}$

a poté upraví Λ ( x ) a e tak, aby přepočtené Δ bylo nulové. Článek Algoritmus Berlekamp – Massey má podrobný popis postupu. V následujícím příkladu C ( x ) slouží k reprezentaci Λ ( x ).

Příklad

Použitím stejných dat jako výše uvedený příklad Petersona Gorensteina Zierlera:

Konečná hodnota C je polynom lokátoru chyb, Λ ( x ).

Euklidovský dekodér

Další iterační metoda pro výpočet polynomu lokátoru chyb a polynomu chybové hodnoty je založena na Sugiyamově adaptaci rozšířeného euklidovského algoritmu .

Definujte S (x), Λ (x) a Ω (x) pro t syndromy a chyby e :

${\ Displaystyle S (x) = S_ {t} x^{t-1}+S_ {t-1} x^{t-2}+\ cdots+S_ {2} x+S_ {1}}$

${\ Displaystyle \ Lambda (x) = \ Lambda _ {e} x^{e}+\ Lambda _ {e-1} x^{e-1}+\ cdots+\ Lambda _ {1} x+1}$

${\ Displaystyle \ Omega (x) = \ Omega _ {e} x^{e}+\ Omega _ {e-1} x^{e-1}+\ cdots+\ Omega _ {1} x+\ Omega _ {0}}$

Klíčová rovnice je:

${\ Displaystyle \ Lambda (x) S (x) = Q (x) x^{t}+\ Omega (x)}$

Pro t = 6 a e = 3:

${\ Displaystyle {\ begin {bmatrix} \ Lambda _ {3} S_ {6} & x^{8} \\\ Lambda _ {2} S_ {6}+\ Lambda _ {3} S_ {5} & x^{ 7} \\\ Lambda _ {1} S_ {6}+\ Lambda _ {2} S_ {5}+\ Lambda _ {3} S_ {4} & x^{6} \\ S_ {6}+\ Lambda _ {1} S_ {5}+\ Lambda _ {2} S_ {4}+\ Lambda _ {3} S_ {3} & x^{5} \\ S_ {5}+\ Lambda _ {1} S_ { 4}+\ Lambda _ {2} S_ {3}+\ Lambda _ {3} S_ {2} & x^{4} \\ S_ {4}+\ Lambda _ {1} S_ {3}+\ Lambda _ {2} S_ {2}+\ Lambda _ {3} S_ {1} & x^{3} \\ S_ {3}+\ Lambda _ {1} S_ {2}+\ Lambda _ {2} S_ {1 } & x^{2} \\ S_ {2}+\ Lambda _ {1} S_ {1} & x \\ S_ {1} \ end {bmatrix}} = {\ begin {bmatrix} Q_ {2} x^{ 8} \\ Q_ {1} x^{7} \\ Q_ {0} x^{6} \\ 0 \\ 0 \\ 0 \\\ Omega _ {2} x^{2} \\\ Omega _ {1} x \\\ Omega _ {0} \ end {bmatrix}}}$

Prostřední členy jsou nulové kvůli vztahu mezi Λ a syndromy.

Rozšířený euklidovský algoritmus dokáže najít řadu polynomů formuláře

A _i ( x ) S ( x ) + B _i ( x ) x ^t = R _i ( x )

kde je stupeň R klesá se i zvyšuje. Jakmile je stupeň R _i ( x ) < t /2, pak

A _i (x) = Λ (x)

B _i (x) = −Q (x)

R _i (x) = Ω (x).

B (x) a Q (x) není třeba ukládat, takže algoritmus se stává:

R ₋₁ = x ^t

R ₀ = S (x)

A ₋₁ = 0

A ₀ = 1

i = 0

zatímco stupeň R _i ≥ t/2

i = i + 1

Q = R _i-2 / R _i-1

R _i = R _i-2 -QR _i-1

A _i = A _i-2 -QA _i-1

pro nastavení dolního řádu Λ (x) na 1 vydělte Λ (x) a Ω (x) A _i (0):

Λ (x) = A _i / A _i (0)

Ω (x) = R _i / A _i (0)

A _i (0) je konstantní (nízkého řádu) člen A _i .

Příklad

Použijeme stejná data jako výše uvedený příklad Peterson – Gorenstein – Zierler:

Λ (x) = a ₂ /544 = 329 x ² + 821 x 001 +

Ω (x) = R ₂ /544 = 546 x 732 +

Dekodér využívající diskrétní Fourierovu transformaci

Pro dekódování lze použít diskrétní Fourierovu transformaci. Abyste se vyhnuli konfliktu s názvy syndromů, nechte c ( x ) = s ( x ) kódované kódové slovo. r ( x ) a e ( x ) jsou stejné jako výše. Definujte C ( x ), E ( x ) a R ( x ) jako diskrétní Fourierovy transformace c ( x ), e ( x ) a r ( x ). Protože r ( x ) = c ( x ) + e ( x ), a protože diskrétní Fourierova transformace je lineární operátor, R ( x ) = C ( x ) + E ( x ).

Transformujte r ( x ) na R ( x ) pomocí diskrétní Fourierovy transformace. Protože výpočet pro diskrétní Fourierovu transformaci je stejný jako výpočet pro syndromy, t koeficienty R ( x ) a E ( x ) jsou stejné jako syndromy:

${\ Displaystyle R_ {j} = E_ {j} = S_ {j} = r (\ alpha ^{j})}$

${\ displaystyle {\ text {for}} 1 \ leq j \ leq t}$

Použití přes jako syndromů (jsou stejné) a generování chyb lokátoru polynom použití metod z některého z výše uvedených dekodérů. ${\ displaystyle R_ {1}}$${\ displaystyle R_ {t}}$

Nechť v = počet chyb. Generování E (x) s použitím známých koeficientů se , chyby lokátoru polynomu, a tyto vzorce ${\ displaystyle E_ {1}}$${\ displaystyle E_ {t}}$

${\ Displaystyle E_ {0} =-{\ frac {1} {\ Lambda _ {v}}} (E_ {v}+\ Lambda _ {1} E_ {v-1}+\ cdots+\ Lambda _ { v-1} E_ {1})}$

${\ Displaystyle E_ {j} =-(\ Lambda _ {1} E_ {j-1}+\ Lambda _ {2} E_ {j-2}+\ cdots+\ Lambda _ {v} E_ {jv}) }$

${\ displaystyle {\ text {for}} t <j <n}$

Potom vypočítejte C ( x ) = R ( x ) - E ( x ) a vezměte inverzní transformaci (polynomickou interpolaci) C ( x ) k vytvoření c ( x ).

Dekódování za hranicí korekce chyb

Singleton vázané uvádí, že minimální vzdálenost d lineárního blokového kódu velikosti ( n , k ) je horní ohraničená n  -  k  + 1. Vzdálenost d se obvykle rozumí omezit schopnost opravy chyb pro ⌊ (D- 1) / 2⌋. Kód Reed – Solomon dosahuje této hranice s rovností, a může tedy opravit až ⌊ (nk) / 2⌋ chyb. Tato hranice opravy chyb však není přesná.

V roce 1999 Madhu Sudan a Venkatesan Guruswami na MIT publikovali „Vylepšené dekódování kódů Reed-Solomon a Algebraic-Geometry“, které zavádí algoritmus, který umožňoval opravu chyb přesahujících polovinu minimální vzdálenosti kódu. Vztahuje se na Reed -Solomonovy kódy a obecněji na algebraické geometrické kódy . Tento algoritmus vytváří seznam kódových slov (jedná se o algoritmus dekódování seznamu ) a je založen na interpolaci a faktorizaci polynomů a jejich rozšíření. ${\ displaystyle GF (2^{m})}$

Soft dekódování

Algebraické dekódovací metody popsané výše jsou metodami tvrdého rozhodování, což znamená, že pro každý symbol se dělá těžké rozhodnutí o jeho hodnotě. Dekodér může například ke každému symbolu přidružit dodatečnou hodnotu odpovídající důvěře kanálového demodulátoru ve správnost symbolu. Příchod LDPC a turbo kódů , které využívají iterované metody dekódování propagace víry s měkkým rozhodnutím k dosažení výkonu korekce chyb blízké teoretickému limitu , vyvolal zájem o aplikaci dekódování s měkkým rozhodováním na konvenční algebraické kódy. V roce 2003 Ralf Koetter a Alexander Vardy představili algoritmus dekódování algebraických dekódovacích algoritmů polynomiálního času s měkkým rozhodováním pro kódy Reed-Solomon, který byl založen na práci Súdánu a Guruswamiho. V roce 2016 vydali Steven J. Franke a Joseph H. Taylor nový dekodér s měkkým rozhodováním.

Příklad Matlabu

Kodér

Zde uvádíme jednoduchou implementaci Matlabu pro kodér.

function [encoded] = rsEncoder(msg, m, prim_poly, n, k)
    % RSENCODER Encode message with the Reed-Solomon algorithm
    % m is the number of bits per symbol
    % prim_poly: Primitive polynomial p(x). Ie for DM is 301
    % k is the size of the message
    % n is the total size (k+redundant)
    % Example: msg = uint8('Test')
    % enc_msg = rsEncoder(msg, 8, 301, 12, numel(msg));
 
    % Get the alpha
    alpha = gf(2, m, prim_poly);
 
    % Get the Reed-Solomon generating polynomial g(x)
    g_x = genpoly(k, n, alpha);
 
    % Multiply the information by X^(n-k), or just pad with zeros at the end to
    % get space to add the redundant information
    msg_padded = gf([msg zeros(1, n - k)], m, prim_poly);
 
    % Get the remainder of the division of the extended message by the
    % Reed-Solomon generating polynomial g(x)
    [~, remainder] = deconv(msg_padded, g_x);
 
    % Now return the message with the redundant information
    encoded = msg_padded - remainder;
 
end

% Find the Reed-Solomon generating polynomial g(x), by the way this is the
% same as the rsgenpoly function on matlab
function g = genpoly(k, n, alpha)
    g = 1;
    % A multiplication on the galois field is just a convolution
    for k = mod(1 : n - k, n)
        g = conv(g, [1 alpha .^ (k)]);
    end
end

Dekodér

Nyní dekódovací část:

function [decoded, error_pos, error_mag, g, S] = rsDecoder(encoded, m, prim_poly, n, k)
    % RSDECODER Decode a Reed-Solomon encoded message
    %   Example:
    % [dec, ~, ~, ~, ~] = rsDecoder(enc_msg, 8, 301, 12, numel(msg))
    max_errors = floor((n - k) / 2);
    orig_vals = encoded.x;
    % Initialize the error vector
    errors = zeros(1, n);
    g = [];
    S = [];
 
    % Get the alpha
    alpha = gf(2, m, prim_poly);
 
    % Find the syndromes (Check if dividing the message by the generator
    % polynomial the result is zero)
    Synd = polyval(encoded, alpha .^ (1:n - k));
    Syndromes = trim(Synd);
 
    % If all syndromes are zeros (perfectly divisible) there are no errors
    if isempty(Syndromes.x)
        decoded = orig_vals(1:k);
        error_pos = [];
        error_mag = [];
        g = [];
        S = Synd;
        return;
    end
 
    % Prepare for the euclidean algorithm (Used to find the error locating
    % polynomials)
    r0 = [1, zeros(1, 2 * max_errors)]; r0 = gf(r0, m, prim_poly); r0 = trim(r0);
    size_r0 = length(r0);
    r1 = Syndromes;
    f0 = gf([zeros(1, size_r0 - 1) 1], m, prim_poly);
    f1 = gf(zeros(1, size_r0), m, prim_poly);
    g0 = f1; g1 = f0;
 
    % Do the euclidean algorithm on the polynomials r0(x) and Syndromes(x) in
    % order to find the error locating polynomial
    while true
        % Do a long division
        [quotient, remainder] = deconv(r0, r1);
        % Add some zeros
        quotient = pad(quotient, length(g1));
     
        % Find quotient*g1 and pad
        c = conv(quotient, g1);
        c = trim(c);
        c = pad(c, length(g0));
     
        % Update g as g0-quotient*g1
        g = g0 - c;
     
        % Check if the degree of remainder(x) is less than max_errors
        if all(remainder(1:end - max_errors) == 0)
            break;
        end
     
        % Update r0, r1, g0, g1 and remove leading zeros
        r0 = trim(r1); r1 = trim(remainder);
        g0 = g1; g1 = g;
    end
 
    % Remove leading zeros
    g = trim(g);
 
    % Find the zeros of the error polynomial on this galois field
    evalPoly = polyval(g, alpha .^ (n - 1 : - 1 : 0));
    error_pos = gf(find(evalPoly == 0), m);
 
    % If no error position is found we return the received work, because
    % basically is nothing that we could do and we return the received message
    if isempty(error_pos)
        decoded = orig_vals(1:k);
        error_mag = [];
        return;
    end
 
    % Prepare a linear system to solve the error polynomial and find the error
    % magnitudes
    size_error = length(error_pos);
    Syndrome_Vals = Syndromes.x;
    b(:, 1) = Syndrome_Vals(1:size_error);
    for idx = 1 : size_error
        e = alpha .^ (idx * (n - error_pos.x));
        err = e.x;
        er(idx, :) = err;
    end
 
    % Solve the linear system
    error_mag = (gf(er, m, prim_poly) \ gf(b, m, prim_poly))';
    % Put the error magnitude on the error vector
    errors(error_pos.x) = error_mag.x;
    % Bring this vector to the galois field
    errors_gf = gf(errors, m, prim_poly);
 
    % Now to fix the errors just add with the encoded code
    decoded_gf = encoded(1:k) + errors_gf(1:k);
    decoded = decoded_gf.x;
 
end

% Remove leading zeros from Galois array
function gt = trim(g)
    gx = g.x;
    gt = gf(gx(find(gx, 1) : end), g.m, g.prim_poly);
end

% Add leading zeros
function xpad = pad(x, k)
    len = length(x);
    if (len < k)
        xpad = [zeros(1, k - len) x];
    end
end