| Tento článek má několik problémů. Prosím pomozte vylepši to nebo diskutovat o těchto otázkách na internetu diskusní stránka. (Zjistěte, jak a kdy tyto zprávy ze šablony odebrat) (Zjistěte, jak a kdy odstranit tuto zprávu šablony) |
v teorie kódování, dekódování seznamu je alternativou k jedinečnému dekódování kódů opravujících chyby za přítomnosti mnoha chyb. Pokud má kód relativní vzdálenost , potom je možné v zásadě obnovit kódovanou zprávu, až je zlomek symbolů kódového slova je poškozen. Ale když je chybovost větší než , to obecně nebude možné. Seznam dekódování tento problém překoná tím, že umožní dekodéru vydat krátký seznam zpráv, které mohly být zakódovány. Dekódování seznamu může opravit více než zlomek chyb.
Existuje mnoho algoritmů polynomiálního času pro dekódování seznamu. V tomto článku nejprve představíme algoritmus pro Kódy Reed-Solomon (RS) který opravuje až chyby a je způsobeno Madhu Súdán. Následně popisujeme vylepšené Guruwami –Súdán seznam dekódovacího algoritmu, který může opravit až chyby.
Zde je graf rychlosti R a vzdálenosti pro různé algoritmy.
https://wiki.cse.buffalo.edu/cse545/sites/wiki.cse.buffalo.edu.cse545/files/81/Graph.jpg
Algoritmus 1 (algoritmus dekódování seznamu Súdánu)
Problémové prohlášení
Vstup : Pole ; n zřetelné páry prvků v ; a celá čísla a .
Výstup: Seznam všech funkcí uspokojující
je polynom v stupně nanejvýš
| | (1) |
Abyste lépe porozuměli Súdánskému algoritmu, možná budete chtít nejprve znát jiný algoritmus, který lze považovat za dřívější verzi nebo za základní verzi algoritmů pro seznam kódů RS - seznam Berlekamp – Welchův algoritmus Welch a Berlekamp původně přišli s algoritmus což může vyřešit problém v polynomiálním čase s nejlepší prahovou hodnotou být . Mechanismus súdánského algoritmu je téměř stejný jako algoritmus Berlekamp-Welchova algoritmu, s výjimkou kroku 1, který chce spočítat bivariační polynom ohraničeného stupeň. Súdánský dekódovací algoritmus pro kód Reed-Solomon, který je vylepšením algoritmu Berlekamp a Welch, může vyřešit problém s . Tato vazba je lepší než jedinečná vazba dekódování pro .
Algoritmus
Definice 1 (vážený stupeň)
Pro váhy , - vážený stupeň monomia je . The - vážený stupeň polynomu je maximum monomiálů s nenulovými koeficienty - vážený stupeň monomia.
Například, má -stupeň 7
Algoritmus:
Vstupy: ; {} / * Parametry l, m budou nastaveny později. * /
Krok 1: Najděte nenulový bivariační polynom uspokojující
- má - vážený stupeň nanejvýš
- Pro každého ,
| | (2) |
Krok 2. Faktor Q na neredukovatelné faktory.
Krok 3. Výstup všech polynomů takhle je faktor Q a alespoň pro t hodnoty
Analýza
Je třeba dokázat, že výše uvedený algoritmus běží v polynomiálním čase a vydává správný výsledek. Toho lze dosáhnout prokázáním následujícího souboru nároků.
Nárok 1:
Pokud je funkce splňující (2) existuje, pak jej lze najít v polynomiálním čase.
Důkaz:
Všimněte si, že dvojrozměrný polynom z - vážený stupeň nanejvýš lze jednoznačně napsat jako . Pak je třeba najít koeficienty uspokojení omezení , pro každého . Toto je lineární sada rovnic v neznámých {}. Jeden může najít řešení pomocí Gaussova eliminace v polynomiálním čase.
Nárok 2:
Li pak existuje funkce uspokojující (2)
Důkaz:
Aby bylo zajištěno, že existuje nenulové řešení, počet koeficientů v by měl být větší než počet omezení. Předpokládejme, že maximální stupeň z v je ma maximální stupeň z v je . Pak stupeň bude nanejvýš . Je třeba vidět, že lineární systém je homogenní. Nastavení splňuje všechna lineární omezení. To však nesplňuje (2), protože řešení může být identicky nulové. Aby bylo zajištěno, že existuje nenulové řešení, je třeba zajistit, aby počet neznámých v lineárním systému byl , takže jeden může mít nenulovou hodnotu . Protože tato hodnota je větší než n, existuje více proměnných než omezení, a proto existuje nenulové řešení.
Nárok 3:
Li je funkce splňující (2) a je funkce splňující (1) a , pak rozděluje
Důkaz:
Zvažte funkci . Toto je polynom v , a argumentují tím, že má nanejvýš titul . Zvažte jakoukoli monomii z . Od té doby má - vážený stupeň nanejvýš , to se dá říct . Tedy termín je polynom v stupně nanejvýš . Tím pádem má titul nanejvýš
Dále to argumentujte je shodně nula. Od té doby je nula kdykoli , to se dá říct je nula pro přísně větší než bodů. Tím pádem má více nul než jeho stupeň, a proto je identicky nulový, z čehož vyplývá
Hledání optimálních hodnot pro a .Všimněte si, že a Pro danou hodnotu , lze vypočítat nejmenší pro kterou platí druhá podmínka Výměnou druhé podmínky lze získat být nanejvýš Dosazením této hodnoty do první podmínky lze dosáhnout být alespoň Dále minimalizujte výše uvedenou rovnici neznámého parametru . Lze to udělat tak, že vezmeme derivaci rovnice a srovnáme ji s nulou. Tím, že dostaneme, Nahrazení zpět hodnota do a jeden dostane
Algoritmus 2 (algoritmus dekódování seznamu Guruswami – Súdán)
Definice
Zvažte a Reed – Solomonův kód přes konečné pole s vyhodnocovací sadou a kladné celé číslo Dekodér seznamu Guruswami-Súdán přijímá vektor jako vstup a výstup seznam polynomů stupně které jsou v korespondenci 1: 1 s kódovými slovy.
Myšlenkou je přidat další omezení na bi-variační polynom což má za následek zvýšení omezení spolu s počtem kořenů.
Násobnost
Bi-variační polynom má nulovou multiplicitu na znamená, že nemá žádný titul , Kde X-stupeň je definován jako maximální stupeň libovolného x výrazu v
Například: Let .
https://wiki.cse.buffalo.edu/cse545/sites/wiki.cse.buffalo.edu.cse545/files/76/Fig1.jpg
Proto, má nulu multiplicity 1 v (0,0).
Nechat .
https://wiki.cse.buffalo.edu/cse545/sites/wiki.cse.buffalo.edu.cse545/files/76/Fig2.jpg
Proto, má nulu multiplicity 1 v (0,0).
Nechat
https://wiki.cse.buffalo.edu/cse545/sites/wiki.cse.buffalo.edu.cse545/files/76/Fig3.jpg
Proto, má nulu multiplicity 2 při (0,0).
Podobně, pokud Pak, má nulu multiplicity 2 v .
Obecná definice multiplicity
má kořeny v -li má nulovou multiplicitu na když .
Algoritmus
Nechte přenášené kódové slovo být , být podporovanou sadou přenášeného kódového slova a přijatého slova
Algoritmus je následující:
• Interpolační krok
Pro přijatý vektor , zkonstruujte nenulový bi-variační polynom s vážený stupeň maximálně takhle má nulovou multiplicitu v každém z bodů kde
• Faktorizační krok
Najděte všechny faktory formuláře a alespoň hodnoty
kde & je polynom stupně
Připomeňme si polynomy stupně jsou v korespondenci 1: 1 s kódovými slovy. Tento krok proto vydává seznam kódových slov.
Analýza
Interpolační krok
Lemma:Z kroku interpolace vyplývá omezení koeficientů
Nechat kde a
Pak, ........................ (rovnice 1)
kde
Důkaz rovnice 1:
- ................. Použití binomické expanze
-
Důkaz lemma:
Polynom má nulovou multiplicitu na -li
- takhle
- můžu vzít hodnoty jako . Celkový počet omezení je tedy
Tím pádem, lze provést několik výběrů pro a každý výběr znamená omezení koeficientů
Faktorizační krok
Tvrzení:
-li je faktorem
Důkaz:
Od té doby, je faktorem , lze reprezentovat jako
kde, je kvocient získaný, když je rozděleno je zbytek
Teď když je nahrazen , , jen když
Teorém:
Li , pak je faktorem
Důkaz:
........................... Z rovnice 2
Vzhledem k tomu, mod
Proto, mod
Tím pádem, je faktorem .
Jak bylo prokázáno výše,
kde LHS je horní mez počtu koeficientů a RHS je dříve prokázaná Lemma.
Proto,
Náhradní ,
Ukázalo se tedy, že algoritmus dekódování seznamu Guruswami – Súdán může dekódovat seznam Kódy Reed-Solomon až do chyby.
Reference