CZ407497A3 - Optimální dekodér se slabými výstupy pro trellis kódy s koncovými bity - Google Patents

Description

Optimální dekodér se slabými výstupy pro trellis kódy s koncovými bity

Oblast techniky

Vynález se týká optimálního dekodéru se slabými výstupy pro trellis kódy (mřížové kódy) s koncovými bity a obecněji dekódo-___ vání samoopravných kódů.

Dosavadní stav techniky

Viterbi algoritmus (VA) je způsob dekódování s maximální pravděpodobností, který určuje nejpravděpodobnější posloupnost dat nebo bitové slovo v případě aditivního bílého Gaussovského kanálového šumu, to jest minimalizuje pravděpodobnost, že dekódované slovo obsahuje chybu. Toto schéma je obecně dynamický program pro nalezení cesty v mříži (trellis) kódu, která je nejbližší posloupnosti přijaté z výstupu přenosového kanálu.

Na druhé straně chybová pravděpodobnost symbolu nebo bitu je minimalizována použitím tak zvaného maximálního a posteriori (MAP) dekodéru. MAP dekodér byl poprvé formálně popsán v článku Bahl, Cocke, Jelínek a Raviv (proto také alternativní jméno BCJR algoritmus), “Optimal Decoding of Linear Codes for Minimizing Symbol Error Rate”, IEEE Transactions on Information Theory, str. 284-287, březen 1974. Termín MAP dekodér nebo BCJR algoritmus jsou zde používány jako označení pro dekodér, který poskytuje pravděpodobnostní rozložení stavů v každé etapě mříže a který také může využívat a priori znalost statistik, týkajících se datových bitů. MAP dekodér je optimální v tom smyslu, že produkuje tyto stavové pravděpodobnosti neboli “slabý výstup” s perfektní přesností, zatímco jsou k disposici jiné, sice jednodušší, dekodéry, které ale mohou vytvářet pouze aproximace těchto pravděpodobností. Varianty algoritmu poskytují související informaci, například pravděpodobnostní rozložení datových symbolů v každé etapě nebo rozložení výstupních symbolů kodéru v každé etapě.

MAP dekodér vyžaduje, aby počáteční stav v přenosu podle trellis (mřížového) kódu byl znám a v některých aplikacích je také třeba znát koncový stav. Na neštěstí proto MAP dekodér nemůže být použit pro dekódování trellis kódů, které používají koncové bity, to jest kódů, pro které počáteční a koncový stav kodéru nemohou být známy dopředu. Speciálně řekneme, že přenos s využitím trellis kódu používá “koncové bity” (“tailbiting”), jestliže počáteční stav kodéru je roven je identický s koncovým kódovacím stavem pro daný blok vstupních bitů. U přímého kodéru je možno určit ze znalosti datových bitů okamžitě jaký bude koncový stav; je to přímo posledních km bitů bloku zprávy, kde k je počet bitů ve vstupním symbolu kodéru a m je paměť kódu. Kodér s koncovými bity je třeba odlišit od běžného kodéru, u kterého počáteční stav je předem stanovený stav, obvykle stav, daný samými nulami. Běžné kodéry také ukončují v předem daném stavu přidáním zakončení (tail) km bitů ke vstupnímu bloku zprávy. To co odlišuje dekodér s koncovými bity od běžného dekodéru je to, že musí kromě provádění svých dalších funkcí odhadnout počáteční stav kodéru. Jelikož kodér s koncovými bity má cylindrickou mříž, kódové slovo generované takovým kodérem může být znázorněno jako cyklus symbolů. Dekodér musí začít práci v některém libovolně zvoleném bodu na tomto cyklu, dosáhnout synchronizace a potom dekódovat

datové bity.

Byla předložena řada dekodérů s koncovými bity, které jsou analogy VA dekodéru, to jest produkují maximální pravděpodobnostní odhad cirkulární mříže kódového slova. Dekodér se slabými výstupy by měl na druhé straně odhadnout stavové pravděpodobnosti okolo cylindrické mříže a žádný takový dekodér není v současnosti znám. Speciálně, jak bylo vysvětleno výše, MAP dekodér se slabými výstupy vyžaduje, aby byl znám npbcaťěční^štavTFmříži a v některých aplikacích aby navíc byl znám také koncový stav. Z tohoto důvodu je použití MAP dekodéru omezeno na obvyklé kódy bez koncových bitů, ve kterých není možné získání výhod použitím koncových bitů, spočívající ve zlepšení schopnosti opravy chyb v systému, který vysílá krátké datové bloky (na příklad při vysílání paketů), pakliže je požadován pravý slabý výstup.

Z toho vyplývá potřeba přesného dekodéru se slabými výstupy pro trellis kódy s koncovými bity, který by měl nízkou složitost.

Podstata vynálezu

Vynález se týká optimálního dekodéru se slabými výstupy pro trellis (mřížové) kódy s koncovými bity. Je podán cirkulární MAP dekodér pro samoopravné trellis kódy, který používá koncové bity a vytváří slabá výstupní rozhodnutí. Cirkulární MAP dekodér poskytuje odhad pravděpodobností stavů v první mřížové (trellis) etapě a tyto pravděpodobnosti nahrazují a priori znalost počátečního stavu v běžném MAP dekodéru. Podle předkládaného vynálezu cirkulární MAP dekodér posky3 • ···· > > o · ····e • · · · · · · · 9« • · · · · « · • e © 9 Φ···φ· • · · ·· f

Φ · · b ······· · ·4 tuje pravděpodobnostní rozdělení počátečního stavu jedním ze dvou možných způsobů. První způsob zahrnuje řešení problému vlastní hodnoty, ve kterém výsledný vlastní vektor je požadované výchozí pravděpodobnostní rozložení; se znalostí počátečního stavu cirkulární MAP dekodér provádí zbytek dekódování stejně jako obvyklý MAP dekódovací algoritmus. Druhá metoda je založena na rekurzi, ve které iterace konvergují k rozložení počátečního stavu. Po dostatečném počtu iterací je stav cyklické posloupnosti znám s dostatečně vysokou pravděpodobností a cirkulární MAP dekodér provádí zbytek dekódování stejně jako obvyklý MAP dekódovací algoritmus.

Přehled obrázků na výkrese

Povaha a výhody předkládaného vynálezu se stanou zřejmými z následujícího detailního popisu vynálezu, který je doplněn násleujícími obrázky, ve kterých

Obr 1. znázorňuje cylindrickou mříž pro čtyřstavový trellis kód s koncovými bity, který má binární vstupní symboly;

Obr. 2 znázorňuje cirkulární stavovou posloupnost dekodéru a cirkulární výstupní posloupnost dekodéru pro trellis kód s koncovými bity;

Obr. 3 je zjednodušený blokový diagram znázorňující jedno provedení cirkulárního MAP dekodéru podle předkládaného vynálezu;

Obr. 4 znázorňuje časovou přímku cirkulárního MAP dekodéru podle předkládaného vynálezu;

Obr. 5 znázorňuje časovou přímku výhodného provedení cirkulárního MAP dekodéru podle předkládaného vynálezu;

Obr. 6 graficky znázorňuje bitový poměr chyb (BER - bit error rate) vzhledem k poměru signáhšum pro cirkulární MAP dekodér, dekódující konvoluční kód s koncovými bity a poměrem rovným 1/2 a pamětí rovnou 6 způsobem podle předkládaného vynálezu;

Obr. 7 graficky znázorňuje bitový^dměFčhybT/zhlědenrir poměru signáhšum s ovlivněným (biased) zdrojovým rozložením pro cirkulární MAP dekodér, dekódující konvoluční kód s koncovými bity a poměrem rovným 1/2 a pamětí rovnou 6 způsobem podle předkládaného vynálezu;

Obr. 8 je zjednodušený blokový diagram znázorňující výhodné provedení cirkulárního MAP dekodéru podle předkládaného vynálezu,

Příklady provedení vynálezu

Kodér s koncovými bity má cyklickou mříž (trellis); z tohoto důvodu může být kódové slovo, generované takovým kodérem může být vizualizováno jako cyklus symbolů. Obr. 1 znázorňuje příklad cylindrické mříže pro trellis (mřížový) kodér s koncovými bity, který má čtyři stavy a binární vstupní symboly. Nedostatek a priori znalostí o počátečním stavu kodéru v případě takových trellis kódů s koncovými bity degraduje spolehlivost dekódování prostřednictvím standardního MAP (nebo BCJR) dekódovacího algoritmu v první části přijaté zprávy.

Výstupní posloupnost kodéru pro trellis kód s koncovými bity vytváří cyklický tvar, který je znázorněn na obr. 2. Stavy kodéru jsou znázorněny jako umístěné okolo kruhu. Jestliže Sq je jedním z těchto stavů, kodér startuje ze stavu Sq posuvného registru v čase íq v kódovacím procesu a po postupu kolem kruhu v posloupnosti stavových přechodů skončí v témže stavu Sq. Dekodér, který pracuje s posloupností zakódovanou tímto způsobem jako s cyklem s každým stavem kodéru vedoucím k dalšímu stavu cyklicky kolem kruhu je cirkulární-dekodér-neboli-dekodér s koncovými bity.

Podle předkládaného vynálezu cirkulární MAP dekodér pro samoopravné trellis kódy, využívající koncových bitů, produkuje slabá výstupní rozhodnutí. Na rozdíl od toho v případě konvenčního MAP dekodéru zná dekodér počáteční stav neboli mřížový uzel; potom dekóduje cestu kodéru v mříži, která vychází z tohoto stavu. U dekodéru s koncovými bity však dekodér musí nejprve identifikovat stav ve stavové posloupnosti kodéru a teprve potom může započít vlastní dekódování. Cirkulární MAP dekodér podle vynálezu podává odhad pravděpodobností stavů v první mřížové (trellis) etapě, a tyto pravděpodobnosti nahrazují a priori znalost výchozího stavu u konvenčního MAP dekodéru. Cirkulární MAP dekodér podle předkládaného vynálezu podává pravděpodobnostní rozložení počátečního stavu jedním ze dvou způsobů. První zahrnuje řešení problému vlastní hodnoty, pro kterou odpovídající vlastní vektor je požadované pravděpodobnostní rozložení počátečního stavu; se znalostí počátečního stavu cirkulární MAP dekodér provádí zbývající část dekódování podle konvenčního MAP (nebo BCJR) dekódovacího algoritmu. Druhý způsob je založen na jisté rekurzi, jejíž iterace konvergují k rozložení počátečního stavu. Po dostatečném počtu iterací je stav na cyklické posloupnosti stavů znám s dostatečně velkou pravděpo dobností a cirkulární MAP dekodér provádí zbytek dekódování podle konvenčního MAP (nebo BCJR) dekódovacího algoritmu.

Cílem konvenčního MAP (nebo BCJR) dekódovacího algoritmu je nalézt následující podmíněné pravděpodobnosti:

P{stav m v čase t | přijaty kanálové výstupy yi, . ,Pl}·

Clen L v tomto výrazu představuje délku datového bloku v jednotkách počtu symbolů kodéru. (Kodér pro (n, &)-kód praduje s fc-bitovými vstupními symboly a generuje n-bitové výstupní symboly). Člen y_t je kanálový výstup (symbol) v čase t.

MAP dekódovací algoritmus ve skutečnosti nejprve nalezne pravděpodobnosti:

A_ť(m) = P{S_t = m; Y'/'}; (1) to jest spojené pravděpodobnosti, že stav kodéru v čase í, označený S_t, je m a je přijat soubor Υ-β — {y_r,..., y_L} kanálových výstupů. Jsou to požadované pravděpodobnosti, vynásobené konstantou (P{, pravděpodobnost přijmutí souboru kanálových výstupů {yi,...,y_L}).

Nyní definujme prvky matice r_ť jako = P{stav j v čase t-,y_t | stav i v čase t - 1}.

Matice r_ť je vypočtena j ako funkce kanálové přechodové pravděpodobnosti R(Y_t,X), pravděpodobnosti p_t(m/m'), že kodér provede přechod ze stavu m' do stavu m v čase t a pravděpodobnosti q_t(X | m', m), že výstup kodéru je X za předpokladu, že předchozí stav kodéru byl m! a současný stav kodéru je m. Speciálně, každý prvek matice je vypočten sečtením přes všechny možné hodnoty výstupu kodéru X následujícím způsobem:

7í(m', m) = ^pt(m\m')q_t(X\m', m)R(Y_t, X). (2)

X

MAP dekodér vypočítává L těchto matic, jednu pro každou mřížovou etapu. Tyto matice jsou vytvořeny z přijatých kanálových výstupních symbolů a z povahy mřížové větve pro daný kód.

Dále definujeme M společných pravděpodobnostních prvků řádkového vektoru a_t jako ^at(j) = P{stav j v čase ů; 3/1,..., y_t} (3) a M podmíněných pravděpodobnostních prvků sloupcového vektoru jako /%’) = P{yt + 1, · · - ,yL | Stav j v čase t} (4) pro j = 0,1,..., (Μ — 1), kde M je počet stavů kodéru. ? (Matice a vektory uvedené zde jsou značeny s použitím tučného písma).

Kroky MAP dekódovacího (nebo BCJR) algoritmu jsou následující:

·· ···· (i) vypočtou se «i,...,ai s využití přímé rekurze:

at = <*t_iTt, t = l,...,L. (5) (ii) vypočtou se £i> · · · > Pl-i s využitím zpětné rekurze:

______fit ~ Γί+1/^+ΐι___£ = 7-1,...,1.__(β)~· (iii) vypočtou se prvky X_t pomocí vztahu:

Aí(ž) = pro všechna i,t = 1,..., L. (7) (iv) Naleznou se potřebné související hodnoty: Například, nechť A{ je množina stavů S_t = {S}, Sf,..., S*™} taková, že j-tý prvek St, označený jako S³t<} je roven nule. Pro konvenční nerekurzivní trellis kód platí, že S³t = d³ _t, j-tý datový bit v čase t.

Slabé výstupní rozhodnutí dekodéru proto je

P{dj = 0 | l·/} = -1 Σ ^(m),

Ss_teAÍ kde Ρ{Υ^} = Ση λι^τη) a,m]e index, který odpovídá stavu

Silné rozhodnutí dekodéru neboli dekódovaný výstupní bit je získán použitím P{d³ _t = 0 | na následující rozhodovací pravidlo:

• · 0 · · ·· ···· d^J _t = O >

P{d{ = o I y^} <

d³ _t = 1

To jest jestliže' P'{d³t = CT| Pf} > |, pak d³t = 0; Jestliže P{d³t = O | Y^} < pak d³ = 1; ve zbývajícím případě se do dhaPt náhodně dosadí hodnota 0 nebo 1.

Jako další příklad související hodnoty pro krok (iv) uvedený výše lze uvést matici pravděpodobností která obsahuje prvky, definované následujícím způsobem:

= P{St-i = i·, St = j; Υγ} = at-iW7i(i,J)A(j)

Tyto pravděpodobnosti jsou užitečné, pokud je požadováno určení a posteriori pravděpodobností výstupních bitů kodéru.

Ve standardních aplikacích MAP dekódovacího algoritmu je přímá rekurze inicializována vektorem a₀ = (1, 0,..., 0) a zpětná rekurze je inicializována vektorem = (1,0,..., 0)^T. Tyto výchozí podmínky jsou založeny na předpokladu, že počáteční stav kodéru je Sq = 0 a jeho koncový stav je Sl = 0.

V souladu s jedním provedením předkládaného vynýlezu cirkulární MAP dekodér nalezne pravděpodobnostní rozložení počátečních stavů řešením problému vlastních hodnot následujícím způsobem. Nechť a_t, a A_ř jsou jak je uvedeno výše, ale • · ♦ · uvažujme počáteční hodnoty «o ^a Pl dané následujícím způsobem:

P_L je rovno sloupcovému vektoru (111... l)^r.

«o je neznámá (vektorová) proměnná.

Potom (i) Vypočte se Typfo Γ= Ί727“~ TTpódlě rovnice (2j.

(ii) Nalezne se největší vlastní hodnota odpovídající maticovému součinu Γ1Γ2 ... Γ5. Odpovídající vlastní vektor se normalizuje tak, aby součet jeho složek byl roven jedné. Tento vektor je řešení pro «ο· Hodnota vlastního vektoru dává vektor P .

(iii) Vypočtou se po sobě následující a_t přímou rekurzí, popsanou rovnicí (5).

(iv) Vycházejíce z P_L, inicializovaného výše uvedeným způsobem, vypočtou se zpětnou rekurzí, popsanou rovnicí (6).

(v) Vypočtou se A_ť způsobem uvedeným v (7), stejně tak jako další proměnné, jako jsou například slabá výstupní rozhodnutí P{d³ _t = 0 | Y^} nebo matice pravděpodobností a_t definované výše.

Vynálezci ukázali, že neznámé proměnné ao splňují maticovou rovnost _ ^αθΓιΓ2 ... Γζ,

Z toho, že tento vzorec vyjadřuje vztah mezi pravděpodobnostmi vyplývá, že součin matic na pravé straně má největší vlastní hodnotu rovnou P {Υχ¹'} a odpovídající vlastní vektor musí být vektor pravděpodobností.

Vycházejíce z počátečního = (111... 1)^T, z rovnice (6) vyplyne hodnota Opakovaným použitím této zpětné rekurze se dostanou všechna P_t. Jakmile je známo otQ a je nastavano veškeré výpočty, prováděné cirkulárním MAP dekodérem podle předkládaného vynálezu jsou shodné s výpočty konvenčního MAP dekódovacího alfgoritmu.

Obr. 3 je zjednodušené blokové schéma, ilustrující cirkulární dekodér 10 pro dekódování samoopravných trellis kódů s koncovými bity, který využívá výše popsanou metodu vlastních hodnot. Dekodér 10 zahrnuje zařízení 12 pro výpočet Γ_ί? které vypočítává r_ť jako funkci kanálových výstupů y_t. Zařízení pro výpočet dostává jako vstup z paměti 30 následující údaje: kanálovou přechodovou pravděpodobnost R(Y_t,X), pravděpodobnost Pt(m|m'), že kodér provede přechod ze stavu m' do stavu m v čase t a pravděpodobnost q_t(X\m', m), že výstupní symbol kodéru je X za předpokladu, že předchozí stav kodéru byl m' a současný stav kodéru je m. Zařízení pro výpočet Γ\ vypočítává každý prvek T_ť sčítáním přes všechny možné hodnoty výstupu X kodéru, vycházejíce při tom z rovnice (2).

Vypočtené hodnoty jsou převáděny do zařízení 14 pro výpočet maticového součinu, které vypočítává maticový součin ΓχΓ₂ ... Γ/,, využívajíce při tom jednotkovou matici 16, získanou například z paměti, přepínač 18 a zpožďovací obvod 20. V čase t = 1 se použije jednotková matice jako jeden ze vstupů zařízení pro výpočet maticového součinu. V časech t = 2 až t = L je maticový součin ΠίΞι převáděn prostřednictvím zpožďovacího • ·

obvodu zpět do zařízení pro výpočet maticového součinu. V čase t = L tedy je výsledný maticový součin převeden prostřednictvím přepínače 21 do zařízení 22 pro výpočet normalizovaného vlastního vektoru, odpovídajícího největší vlastní hodnotě maticového součinu, který mu byl zadán. S takto incializovaným «o, to jest s vypočteným normalizovaným vlastním vektorem, jsou následující hodnoty vektorů at určeny rekurzivně, vycházejíce z rovnice (5) pomocí zařízení 24 pro výpočet maticového součinu, __které využívá také zpožďovací obvod 26 _a..přepínací-obvod-28,------jak je ukázáno na obrázku. Odpovídající hodnoty Γ* jsou při tom získávány z paměti 30 a výsledné hodnoty on jsou uchovávány v paměti 30.

Hodnoty jsou určeny v zařízení 32 pro výpočet maticového součinu, který využívá přepínač 34 a zpožďovací obvod 36 a pracuje podle rovnice (6). Poté jsou vypočteny pravděpodobnosti A_t, vycházejíce při tom z hodnot a_t a P_t, přičemž výpočet se provádí v zařízení 40 pro výpočet součinu po složkách, které pracuje podle rovnice (7). Hodnoty A_t jsou přivedeny na zařízení 50 pro výpočet pravděpodobnosti hodnoty dekódovaného bitu, které určuje pravděpodobnost, že j-tý dekódovaný bit v čase t, označený d³ _t, je roven nule. Tato pravděpodobnost je předána prahovému rozhodovacímu zařízení 52, které implementuje následující rozhodovací pravidlo: jestliže pravděpodobnost, určená zařízením 50 pro výpočet pravděpodobnosti hodnoty dekódovaného bitu, je větší než pak rozhodne, že dekódovaný bit je roven nule, kdežto pokud je pravděpodobnost, určená zařízením 50 pro výpočet pravděpodobnosti hodnoty dekódovaného bitu, menší než |, pak rozhodne, že dekódovaný bit je roven jedné. V případě, že pravděpodobnost je rovna j, pak je jako dekódovaný bit zvolena náhodně jedna z hodnot 0 a 1. Výstup prahového rozhodovacího zařízení 52 dává výstupní bit dekodéru v čase t.

• ··· ·· ····

Pravděpodobnost, že dekódovaný bit je roven nule, (P{d³t = 0}) je na obr. 3 také znázorněna jako informace, předávaná bloku 54 slabých výstupních funkcí f(JP{d^Jt = 0}), která poskytuje funkci této pravděpodobnosti, jako je například pravděpodobnostní poměr =

- P{d{ = 0} p{4 = o} ~ jákó slábě výstupní rozhodnutí dekodéru. Jiná užitečná funkce hodnoty P{d^J _t — 0} je

log pravděpodobnostní poměr = log

Jiná užitečná funkce, kterou může vypočítávat blok 54 může být prostá identická funkce, takže slabý výstup je přímo P{d{ = 0}·

Cirkulární MAP dekodér podle alternativního provedení vynálezu určuje pravděpodobnostní rozložení stavů pomocí rekurzivní metody. Speciálně v jednom provedení vynálezu (dynamická konvergenční metoda) rekurze pokračuje tak dlouho, dokud není zjištěna konvergence dekodéru. V této rekurzivní (nebo dynamické rekurzivní) metodě jsou kroky (ii) a (iii) výše uvedeného způsobu, využívajícího vlastního vektoru, nahrazeny následujícím způsobem:

(ii.a) Vycházejíce z počátečního ao rovného (1/M,..., 1/M), kde M je počet stavů v mříži kódu, se provádí L-krát přímá rekurze. Výsledek se normalizuje tak, že prvky každého nového at mají součet jedna. Uchová se všech L vektorů at14 • ··♦· (ii.b) Nechť «ο j^e rovno cil z předchozího kroku a, vycházejíce z t — 1, se vypočte prvních L_Wmin pravděpodobnostních vektorů a_t ještě jednou.

To znamená, že se vypočte Qf_ť(m) = Σ^ο¹ at-iG)7íG>τη) pro m = 0,1,..., Μ - 1 a t = 1,2,..., L_Wmin, kde L_Wmin je vhodné minimální množství mřížových stavů.

Normalizuje se jako výše. Ponechá se pouze soubor posledních L hOdnoť a^nalěžěňýčhTěkuřží vTřrókuVÍLa) a (ii.b) a αχ ' ' ' ' ^wmin hodnot nalezených dříve v kroku (ii.a).

(ii.e) Porovná se «L_Wmin z kroku (ii.b) s dříve nalezeným souborem z kroku (ii.a). Jestliže M odpovídajících prvků nového a starého αχ. jsou uvnitř daného tolerančního rozmezí, pokračuje se krokem (iv) popsaným výše. V opačném případě se přechází do kroku (ii.d).

(ii.d) Nechť t = t + 1. Vypočte se at = a^-iiy Normalizuje se výše uvedeným způsobem. Ponechá se pouze L nejnovějších vypočtených hodnot a a a_t, nalezené dříve v kroku (ii.a).

(ii.e) Porovnají se nové hodnoty a_t s dříve nalezenou množinou hodnot. Jestliže M nových a starých a_t se nachází v daném tolerančním rozmezí, pokračuje se krokem (iv). Jinak se pokračuje krokem (ii.d) jestliže dva nejnovější vektory nespadají do daného tolerančního rozmezí a jestliže počet rekurzí nepřekročil dané maximum (typicky 2L). Ve zbývajícím případě se pokračuje krokem (iv).

Cirkulární “časová přímka” na obr. 4 shrnuje způsob podle kroků (ii.a) až (ii.e), uvedených výše, pro výpočet a_t pro t = 1,2,, L pro cirkulární MAP dekodér, jehož výsledkem je od15 • · hadnutí všech L vektorů a_t. Tento způsob potom pokračuje kroky (iv) a (v) popsanými výše u způsobu užívajícího výpočtu vlastních čísel a vytváří slabá výstupní rozhodnutí a dekódované výstupní bity cirkulárního MAP dekodéru.

V cirkulárním MAP dekodéru je hodnota ao inicializována jako ao — (1/Af,... ,1/M), protože počáteční stav kodéru je neznámý. Proto se předpokládá, že každý z jeho M možných výchozích stavů je stejně pravděpodobný. (Pokud tento předpo-_________ klaď není správný, výchozí hodnoty Qo(m) mohou být nastaveny v závislosti na jakékoliv a priori znalosti, týkající se pravděpodobností výchozích počátečních stavů. Zde popsaný dekodér je proto z tohoto důvodu také možno výhodně aplikovat na případ trellis kódů s částečnými koncovými bity).

Vysvětlení práce cirkulárního MAP dekodéru podle předkládaného vynálezu je usnadněno, uvažujeme-li definici Oí^m). Výraz a_t(m) je spojená pravděpodobnost toho, že kodér je ve stavu m v čase t a že dekodér pozoroval posloupnost {τ/i,... ,y_t} ve výstupním kanálu kodéru. Přezkoumáním rovnice (5), popisující rekurzivní výpočet a_t, se odhalí účinek faktu, že počáteční stav trellis kodéru s koncovými bity není znám. Z rovnice (5) je zřejmé, že neznalost počátečního stavu mřížového kodéru s koncovými bity ovlivní oj (m) v tom smyslu, že vypočtená pravděpodobnost, že kodér je ve stavu m v čase t = 1 a že dekodér pozoroval kanálový výstup yi bude větší v případě následníku správného počátečního stavu. Zatímco toto ovlivnění má tendenci přecházet do dalších etap výpočtu má také naštěstí tendenci klesat, pokud je pozorováno větší množství výstupních kanálových symbolů. Proto jestliže délka L bloku zprávy je dostatečně velká, pak a^m) bude daleko přesnější než ao(m), neboť dekodér nyní využil pozorování celé posloupnosti symbolů z kanálu, a^m) nyní může být použito jako ao(m) v následující • ·· · ·· 9

999 999 • · · · · · ·

9 99

999 9999 99· iteraci dekódování, jak bylo ukázáno v kroku (ii.b) popsaném výše.

Rekurzivní způsob (nebo způsob dynamické konvergence) podle předkládaného vynálezu porovnává hodnoty získané v každé iteraci a a ukončí rekurzivní výpočet a_ř v okamžiku, kdy je zjištěna konvergence. Tato technika proto redukuje potřebný počet výpočtů, neboť často není nutné opakovat výpočet a_t pro všech L etap mříže.

V jiném výhodném provedení předkládaného vynálezu je cirkulární MAP dekodér, užívající výše popsanou rekurzivní metodu modifikován tak, že dekodér provede pouze předem určený a pevný počet etap v mříži podruhé, což znamená předem danou hloubku opakování. To je výhodné z implementačních důvodů, neboť počet výpočtů pro dekódování je stejný pro každý dekódovaný blok zprávy. Z toho pak vyplývá snížení složitosti software a hardware.

Zde popsaná hloubka opakování se nachází v kontextu dekodéru omezené vzdálenosti, což je dekodér, který opraví jakoukoliv kombinaci e nebo méně chyb, k nimž dojde v počtu úrovní mříže L_ob_s. To se přímo přenáší na dekodéry navržené k dosažení jiných kritérií, jako je minimalizace chybové pravděpodobnosti dekodéru.

Jeden způsob odhadu požadované hloubky opakování pro popisované MAP dekódování konvolučních kódů s koncovými bity je její určení z hardwarových a softwarových experimentů, ve kterých je implementován MAP dekodér s proměnnou hloubkou opakování a jsou prováděny experimenty, v nichž se měří poměr bitových chyb dekódovaného signálu (BER) vzhledem k Eb/N₀ pro postupně narůstající hloubku opakování. Minimální hloubka ···· • ···· opakování, která podává minimální pravděpodobnost poměu bitových chyb dekódovaného signálu pro specifikované Eb/N₀ je nalezena v okamžiku, kdy další vzrůst hloubky opakování nesnižuje chybovou pravděpodobnost.

Jestliže poměr bitových chyb dekódovaného signálu, který je větší, než minimum dosažitelné pro specifikované E^/N^, je tolerovatelný je možné snížit požadovaný počet mřížových etap, prováděných cirkulárním MAP dekodérem. Speciálně zkoumání hloubky opakování, popsané výše, může být prostě ukončeno v okamžiku, kdy je dosaženo požadované střední pravděpodobnosti bitové chyby.

Jiný způsob určení hloubky opakování pro daný kód je na základě používání distančních vlastností kódu. Za tímto účelem je třeba definovat dvě odlišné rozhodovací hloubky dekodéru. Výraz “správná cesta” zde bude používán pro posloupnost stavů nebo cestu skrz mříž, která vychází z kódování bloku datových bitů. Výraz “nesprávná podmnožina uzlu” znamená množinu všech nesprávných (mřížových) větví, vycházejících z uzlu na správné cestě a nebo z jeho následníků. Obě rozhodovací délky definované níže závisí na konvolučním kodéru.

Pro ilustraci je zde toto provedení předkládaného vynálezu popsáno s odvoláním na konvoluční kodér. Nicméně je zřejmé, že předkládaný vynález se neomezuje na konvoluční kódy.

Rozhodovací hloubka je definována následujícím způsobm:

(i) Přímá rozhodovací hloubka pro e-chybovou korekci, označená jako LF(e), je definována jako první hloubka v mříži, ve které jsou všechny cesty v nesprávné podmnožině výchozího vrcholu na správné cestě, bez ohledu na to, zda se stýká se správnou ces18 tou nebo ne, leží ve více než v Hammingově vzdálenosti 2e od správné cesty. Význam LF(e) je v tom, že jestliže existuje e nebo méně chyb před iniciálním vrcholem a je známo, že zde začíná kódování, pak dekodér musí dekódovat správně. Formální tabelace přímých rozhodovacích hloubek pro konvoluční kódy podali J.B. Anderson a K. Balachandran v “Decision Depths of Convolutional Codes”, IEEE Transactions on Information Theory, svazek. IT-35, str. 455-459, březen 1989. Množství vlastností LF(e) bylo popsáno .v uvedené, referenci a také v článku J. B. Anderson a S.----------Mohan v Source and Channel Coding - An Algorithmic Approach, Kluwer Academie Publishers, Norwell, MA, 1991. Hlavní mezi těmito vlastnostmi je pozorování, že existuje jednoduchá lineární relace mezi LF a e. Například pro kódy s poměrem 1/2 je LF rovno přibližně 9,08e.

(ii) V následujícím kroku se definuje nesloučená rozhodovací hloubka pro e-chybovou korekci, LU(e), která je rovna první hloubce v mříži, ve které všechny cesty v mříži, které se nikdy nedotkly správné cesty, leží ve více než v Hammingově vzdálenosti 2e vzdáleny od správné cesty.

Význam LU(e) pro cirkulární MAP dekódování se slabými rozhodnutími je v tom, že pravděpodobnost identifikace stavu na skutečně vyslané cestě je vysoká poté, co dekodér provede LU(e) mřížových etap. Proto je minimální hloubka opakování pro cirkulární MAP dekódování rovna LU(e). Výpočty hloubky LU(e) ukazují, že je vždy větší než LF(e), ale vyhovuje stejným aproximačním zákonům. Z toho plyne, že minimální hloubka opakování může být určena jako přímá rozhodovací hloubka LF(e), pokud pro kód není známa nesloučená rozhodovací hloubka.

Nalezením minimální nesloučené rozhodovací hloubky pro daný kodér se nalezne nejmenší počet mřížových etap, které musí

být provedeny praktickým cirkulárním dekodérem, který generuje slabá výstupní rozhodnutí. Algoritmus pro nalezení LF(e), přímé rozhodovací hloubky, podali J.B. Anderson a K. Balachandran v “Decision Depths of Convolutional Codes”, citovaném výše. Pro nalezení LU(e) je třeba provést:

(i) Rozšířit mříž kódu zleva doprava, začínajíce ze všech uzlů mříže současně s výjimkou nulového stavu.

(ii) V každé úrovni vynechat každou cestu, která se spojuje se správnou (výhradně nulovou) cestou, ale nerozšiřovat žádnou cestu, vycházející ze správného (nulového) stavového uzlu.

(iii) V úrovni k se nalezne nej menší Hammingova vzdálenost nebo váha mezi cestami, končícími v uzlech této úrovně.

(iv) Jestliže tato nej menší vzdálenost překračuje 2e, ukončí se výpočet, jinak je LU(e) = k.

Jak bylo popsáno v U.S. patentové přihlášce č. (RD-29,923), experimenty provedené pomocí počítačové simulace vedly ke dvěma neočekávaným výsledkům:

(1) opakované zpracování zlepšuje výkonnost dekodéru a (2) použití hloubky opakování LU(e) + LF(e) = 2LF(e) zlepšuje výkonnost dekodéru významným způsobem. Tyto neočekávané výsledky vedly k modifikaci cirkulárního MAP dekodéru pro trellis kódy s koncovými bity, založené na rekurzi.

Proto výhodné provedení cirkulárního MAP dekódovacího algoritmu založeného na rekurzi zahrnuje následující kroky:

(i) VypočteníT_ř pro t = 1, 2,..., L vycházejíce z rovnice (2).

•9 ····

(ii) Vycházejíce z počátečního ao rovného (l/M,..., l/M), kde

M je počet stavů v mříži, provedení přímé rekurze podle rovnice (5) (L + £_w)-krát pro u = 1, 2,..., (L + L_w), kde L_w je hloubka opakování dekodéru. Index t v mříži má hodnoty ((w — 1) modL) +1. Jestliže dekodér provádí opakování okolo posloupnosti symbolů přijaté z kanálu, otL je zpracováno jako «o- Výsledky se normalizují tak, že prvky každého nového at dávají v součtu jednotku. Ponechá se L nejnovějších vektorů a, nalezených to ut o. rekurzL______________________________________________________________ (iii) Počínajíce od výchozího β_Ε rovného (1,..., 1)^T, provedení zpětné rekurze podle rovnice (6) celkově (L + L_w)-krát pro u — 1, 2,..., (L + L_w). Index t úrovně v mříži má hodnoty L — (u modL). Jestliže dekodér provádí opakování kolem přijaté posloupnosti, β_γ je použito jako fi_L+1 a Γι je použito jako Γζ,₊ι při výpočtu nového fi_L. Výsledky se normalizují tak, že prvky každého nového a_t dávají v součtu jednotku. Opět se ponechá L nejnovějších vektorů a, nalezených touto rekurzí.

Následující krok této výhodné rekurzivní metody je stejný jako krok (v) popsaný výše při popisu metody s vlastním vektorem a vytváří slabá rozhodnutí a dekódované bity, představující výstup cirkulárního MAP dekodéru.

Cirkulární “Časová osa” na obr. 5 shrnuje proces výpočtu a_t a β_ί pro u = 1,2,... ,(L -+- L_w) pro cirkulární MAP dekodér podle této výhodné rekurzní metody.

Výkonnost tohoto výhodného provedení cirkulárního MAP dekodéru byla testována pro slabá rozhodnutí v kanálu s aditivním bílým Gaussovským šumem (AWGN -aditive white Gaussian noise) pomocí počítačové simulace, předpokládajíce binární antipodální signalizaci (např. binární fázové posuvné klíčování

- binary phase shift keying). Simulace využívaly nej lepší známý konvoluční kód pro poměr = 1/2 a paměť = 6. (Kód je nejlepší v tom smyslu, že má největší volnou vzdálenost.) Všechny simulační výsledky, které jsou zde uvedeny byly získány s pomocí dekodéru, který používal hloubku opakování rovnou dvojnásobku rozhodovací hloubky kódu (40 mřížových etap). Kromě toho byly při simulaci použity krátké bloky zprávy, obsahující každý 48 bitů.

Obr. 6 je výsledný graf střední pravděpodobnosti chyby dekódovaného bitu vzhledem k poměru Eb/No. Zdrojové bity byly se stejnou pravděpodobností rovzny 0 nebo 1..Nicméně pokud byla tato simulace opakována s ovlivněným zdrojovým rozložením, které bylo známo a priori dekodéru, střední pravděpodobnost bitové chyby cirkulárního MAP dekodéru pro danou hodnotu Eb/No významně poklesla. Obr. 7 porovnává poměr bitových chyb pro danou hodnotu Eb/No pro následující tři případy:

Stejně pravděpodobné zdrojové bity, P{zdrojový bit je 1} = 0, 67, a P{zdrojový bit je 1} = 0, 91.

Ve druhém případě je F{zdrojový bit je 1} = 2P{zdrojový bit je 0}, zatímco ve třetím případě P{zdrojový bit je 1} = 10P{zdrojový bit je 0}.

Obr. 8 je zjednodušené blokové schéma znázorňující cirkulární MAP dekodér 80 podle výhodného provedení předkládaného vynálezu. Dekodér 80 zahrnuje zařízení 82 pro výpočet hodnoty r_ť, které vypočítává Γ\ jako funkci kanálových výstupů y_t. Kanálové výstupy 7/i,..., yi jsou předány zařízení pro výpočet prostřednictvím přepínače 84. Pokud je přepínač v dolní poloze, L kanálových výstupních symbolů je přivedeno do zařízení 82

4· ···· pro výpočet hodnoty T_t a posuvného registru 86 v týž okamžik. Potom je přepínač 84 přepnut do horní polohy, což umožní, aby posuvný registr přesunul prvních L_w přijatých symbolů znovu do zařízení pro výpočet Γ\, to jest provede cirkulární zpracování. Zařízení pro výpočet Tf dostává jako vstupy z paměti 96 kanálové přechodové pravděpodobnosti R(Yt, X), pravděpodobnosti že kodér provede přechod ze stavu m' do stavu m v čase t a pravděpodobnosti q_t(X\m', m), že výstupní symbol kodéru je X za předpokladu, že předchozí stav je m' a současný stav je m. Zařízení pro výpočet T_ř určuje každý prvek sečtením přes všechny možné hodnoty X výstupu kodéru na základě rovnice (2).

Vypočtené hodnoty se předají zařízení 90 pro výpočet maticového součinu, které násobí matici Γ\ s maticí oq_i, které dostane rekurzivně přes zpožďovací zařízení 92 a demultiplexor 94. Ovládací signál. CNTRL1 způsobí, že demultiplexor 94 zvolí v čase t = 1 ao z paměti 96 jako jeden ze vstupů pro zařízení 90 pro výpočet maticového součinu. Pokud je 2 < t < Λ, pak ovládací signál CNTRL1 způsobí, že demultiplexor 94 zvolí a_ť_j ze zpožďovacího zařízení 92 jako jeden ze vstupů pro zařízení 90 pro výpočet maticového součinu. Hodnoty Γ₍ aty jsou uchovávány v paměti 96 požadovaným způsobem.

Vektory jsou vypočítávány rekurzivně pro zařízení 100 pro výpočet maticového součinu přes zpožďovací zařízení 102 a demultiplexor 104. Ovládací signál CNTRL2 způsobí, že demultiplexor 104 zvolí v čase t = L — 1 z paměti 96 jako jeden ze vstupů pro zařízení 100 pro výpočet maticového součinu. Pokud jeÁ — 2>ř>l, pak ovládací signál CNTRL2 způsobí, že demultiplexor 104 zvolí ze zpožďovacího zařízení 102 jako jeden ze vstupů pro zařízení 100 pro výpočet maticového součinu. Výsledné hodnoty jsou násobeny hodnotami a_í; získanými ·· «···

z paměti 96, v zařízení 106 pro násobení vektorů po prvcích, čímž se vypočtou pravděpodobnosti A,, jak bylo popsáno výše. Stejným způsobem jako bylo popsáno výše při popisu obr. 3 se hodnoty A, použijí v zařízení 50 pro výpočet pravděpodobnosti hodnoty dekódovaného bitu, jehož výstup se přivádí do zařízení 52 pro provádění prahového rozhodnutí, které vytvoří výsledné výstupní bity dekodéru.

Na obr. 8 je také znázorněno, že podmíněná pravděpodobnost, že dekódovaný bit je roven nule (P{d³ _t = 0|y/}) je předávána slabému výstupnímu funkčnímu bloku 54, který vypočítává funkci této pravděpodobnosti, to jest hodnotu f{P{d³ = 0|Κ/}) takovou, jako je například poměr pravděpodobností =

- P{di = 0|l·?} P{di = jako slabé výstupní rozhodnutí dekodéru. Jiná užitečná funkce P{di = 0| Y?} je

- P{d’ = log poměr pravděpodobností = log -----~ i m = oim J

Jiná užitečná funkce, kterou může vypočítávat blok 54, je identická funkce, takže slabým výstupem je pak přímo P{d³ _t = om·

Několik praktických a účinných metod kódování závisí kritickým způsobem na slabé výstupní informaci MAP dekodéru, například na způsobech sériového zřetězeného (konkatenovaného) kódování. V jednom takovém způsobu, ve kterém vnější dekodér v ···· · ·· ·· ···♦ • · · 4 · · · 9*· • a · · · ·· e β, e · e e e e © e • · · · · · • · · U ·»»·*·· · ·« používá chybové dekódování a vymazávání, slabá výstupní rozhodnutí MAP vnitřního dekodéru mohou být zpracována jako indikátor spolehlivosti dekódování ternárního rozhodovacího zařízení, které může dekódovanému bitu přiřadit hodnotu 0 nebo 1 nebo deklarovat vymazání. Navíc může být slabý výstup dekodéru často výhodně použit následujícím procesorem, jako je dekodér řeči nebo obrazu. Například syntetizátor řeči ve vokodéru může používat slabá výstupní rozhodnutí pro identifikaci pravděpodobných přenosových chyb v rámci přenesené řeči - k------------------------tomu, aby bylo spuštěno zakrýváni chyb (error concealement) což je způsob, který zlepší kvalitu řeči u zařízení, pracujícího přes kanál s velmi silným šumem.

Až do objevení předkládaného vynálezu nebylo MAP dekódování možné pro kódy s koncovými bity. Význam koncových bitů je v tom, že dosahuje nejlepšího možného chování vzhledem k opravě chyb u krátkých kódových slov, pro které je těžké dosáhnout velkých kódovacích zisků. Krátká kódová slova se přirozeně vyskytují u paketových datových systémů a u hlasových komunikačních systémů s nízkou úrovní kódování řeči.

Předkládaný vynález je navíc užitečný v kanálech, ve kterých se vyskytuje únik (fading) nebo malý poměr signáhšum, což jsou běžné vlastnosti v případě “very smáli apertuře terminál” (VSÁT) družicové komunikace a v mobilní radiové komunikaci.

Zatímco bylo ukázáno a popsáno výhodné provedení předkládaného vynálezu, je zřejmé, že takové provedení bylo podáno pouze jako příklad. Odborníkovi je zřejmé, že mohou být provedeny početné změny, obměny a nahrazení, aniž by se řešení odchýlilo od předmětu zde předkládaného vynálezu. V souladu s tím je předmět předkládaného vynálezu omezen pouze duchem a rozsahem přiložených patentových nároků.

Claims (25)

1. PATENTOVÉ NÁROKY

   1. Dekodér pro trellis kódy s koncovými bity generované kodérem, přičemž dekodér dekóduje určováním spojených pravděpodobností, že stav kodéru v čase t, označený St, je m a je přijat soubor L kanálových výstupů Yf = {?/i,... ,ϊ/l}, označených A_ť(m) = P{S_t = τηβΥγ}, uvedený trellis kód má M stavů kodéru, uvedený dekodér určuje L prayděpodobnostních.matic , jednu pro každou z L mřížových etap, přičemž prvky uvedených pravděpodobnostních matic jsou definovány jako

   Γί(ϊ, j) = P{stav j v čase t - l\y_t | stav i v čase t - 1} a to určením řádkových vektorů a_t, které obsahují M prvků, představujících spojené pravděpodobnosti a jsou definovány jako ^at(j) = P{stav j v čase t; t/i,..., y_t} a určením sloupcových vektorů @_t, které obsahují M prvků, představujících podmíněné pravděpodobnosti a jsou definovány jako

   AC?) = P{yt + 1, · ·, yL | Stav j v čase t} pro j = 0,1,..., (Μ — 1), přičemž uvedený dekodér zahrnuje:

   zařízení pro výpočet matic Γ_ί? které přijímá uvedené kanálové výstupy, kanálové přechodové pravděpodobnosti R(Y_t, X), • · · · pravděpodobnosti Pt(m/m'), že kodér provede přechod ze stavu m! do stavu m v čase t a pravděpodobnosti q_t(X | že výstup kodéru je X za předpokladu, že předchozí stav kodéru byl m' a současný stav kodéru je m a které z těchto údajů určí skalární prvky uvedených pravděpodobnostních matic r_ť, zařízení pro výpočet součinu matic Ι\, které přijímá uvedené skalární prvky z uvedeného zařízení pro výpočet matic Γ\ a vypočítává jejich. maticový součin Γ1Γ2 ... __________________________________________ zařízení pro výpočet normalizovaného vlastního vektoru, které přijímá uvedený maticový součin Γ1Γ2 ...Fl a vypočítává normalizovaný vlastní vektor «o, odpovídající největší vlastní hodnotě uvedeného maticového součinu, zařízení pro výpočet součinu matic a_ť, které přijímá uvedený normalizovaný vlastní vektor «o ^a vytváří následující a_t pomocí přímé rekurze následujícím způsobem:

   paměť pro uchování uvedených pravděpodobnostních matic r_ť a uvedených řádkových vektorů a_t, zařízení pro výpočet součinu matic fi_t, které vypočítává uvedené sloupcové vektory provedením inicializace β_Ε = (1,1,1,..., 1)^T a vypočtením předchozích pomocí zpětné rekurze následujícím způsobem:

   fit — Vt+ifit+i, t — L — 1,..., 1, zařízení pro výpočet součinu po složkách, které vypočítává spojené pravděpodobnostní vektory A_t, jejichž prvky jsou uvedené spojené pravděpodobnosti X_t(i, ý), násobením prvků uvedených řádkových vektorů prvky uvedených sloupcových vektorů následujícím způsobem:

   At(?) = pro všechna i,t = 1,..., L, a zařízení pro výpočet pravděpodobnosti hodnoty dekódovaného bitu, které s využitím hodnot X_t určuje pravděpodobnost, že daný datový bit, který byl zadán kodéru v čase rovném t, je roven nule, přičemž datový bit je m-tý z k datových bitů a dále určuje slabé výstupy jako funkci uvedené pravděpodobnosti.
2. 2. Dekodér podle nároku 1, dále zahrnující prahové rozhodovací zařízení, které přijímá pravděpodobnost, že datový bit zadaný kodéru v čase rovném t, je roven nule a implementuje rozhodovací pravidlo, kterým z ní určí dekódovaný výstupní bit.
3. 3. Dekodér podle nároku 1, ve kterém uvedený trellis kód s koncovými bity zahrnuje konvoluční kód.
4. 4. Dekodér podle nároku 1 zahrnující dekodér s omezenou vzdáleností.
5. 5. Dekodér pro trellis kódy s koncovými bity generované kodé- rem, přičemž dekodér dekóduje určováním spojených pravděpodobností, že stav kodéru v časet, označený S_t, je m a je přijat soubor L kanálových výstupů Yf = {yi,... ,y_L], označených A_ř(m) = P{S_t = uvedený trellis kód má M stavů kodéru, uvedený dekodér určuje L pravděpodobnostních matic Γ_ί? jednu pro každou z L mřížových etap, přičemž prvky uvedených ·' · · 4 ·····

   4 « · « 4 ·· • · · · ·

   9 e e; C4««

   4 4 ·· • 4 4 4 · 4 4 44 % pravděpodobnostních matic jsou definovány jako

   Γί(ζ, ý) = P{stav j v čase t — l;y_t | stav i v čase t — 1} a to určením řádkových vektorů a_t, které obsahují M prvků, představujících spojené pravděpodobnosti a jsou definovány jako »í(J) = -P{stav j v čase ť, y_u ..., y_t} a určením sloupcových vektorů které obsahují M prvků, představujících podmíněné pravděpodobnosti a jsou definovány jako

   A(j) = P{yt + l,...,yL | stav j v čase t} pro j — 0,1,..., (Μ — 1), přičemž uvedený dekodér zahrnuje:

   zařízení pro výpočet matic Γ_ί; které přijímá uvedené kanálové výstupy, kanálové přechodové pravděpodobnosti pravděpodobnosti p_ř(m/m⁷), že kodér provede přechod ze stavu m⁷ do stavu m v čase t a pravděpodobnosti qt(X | m⁷,m), že výstup kodéru je X za předpokladu, že předchozí stav kodéru byl m⁷ a současný stav kodéru je m a které z tecHto údajů určí skalární prvky uvedených pravděpodobnostních matic rř, zařízení pro výpočet součinu matic a_t, které přijímá uvedené skalární prvky matic Γ\ z uvedeného zařízení pro výpočet matic r_ř a vytváří uvedené řádkové vektory a_t, ♦ ·« · a_t = zařízení pro výpočet součinu matic /?_ř, které vypočítává uvedené sloupcové vektory fi_t, zařízení pro výpočet součinu po složkách, které vypočítává spojené pravděpodobnostní vektory A_ť, jejichž prvky jsou uvedené spojené pravděpodobnosti (z, ý),-----------------------přičemž uvedené zařízení pro výpočet součinu matic a_t, uvedené zařízení pro výpočet součinu matic fi_t a uvedené zařízení pro výpočet součinu po složkách vytvářejí uvedené vektory a_t, fit a A_ř:

   (i.a) vycházejíce z počátečního ao rovného (1/M,..., 1/M), Lkrát provedením přímé rekurze a_t = a_t-_ír_t, t = l,...,L, a normalizováním výsledku tak, že prvky každého nového a_t mají součet jedna a uchováním všech L vektorů a_t, (i.b) položením «o rovno «£ z kroku (i.a) a, vycházejíce z t = 1, vypočtením ________ ^at — ^αί-1Γ\, t 1,..., L_Wmin, kde L_Wmin je předem daný minimální počet mřížových etap, normalizováním výsledku tak, že prvky každého nového a_t mají «· *··· součet jedna a ponecháním pouze souboru posledních L hodnot a, nalezených rekurzí v kroku (i.a) a (i.b) a a^_w nalezené v kroku (i.a), (i.c) porovnáním ar z kroku (i.b) s ar nalezeným v kroku ' ^wmin ' ' ^wmin (ii.a) a pokračováním do kroku (ii), jestliže hodnoty jsou uvnitř daného tolerančního rozmezí a pokračováním do kroku (ii.d) v opačném případě, (i.d) položením t = t + 1 a vypočtením a_t — a_tT_t, normalizováním výsledku rekurze tak, že prvky každého a_t mají součet jedna, ponecháním pouze L nejnovějších vypočtených hodnot a a hodnot a_t, nalezených dříve v kroku (i.a), (i.e) porovnáním hodnoty a_t s nejnovější již nalezenou množinou hodnot z kroků (i.a), (i.b) a (i.d), postoupením do kroku (ii) jestliže se hodnoty nachází v tolerančním rozmezí, pokračováním krokem (i.d) jestliže dva nejnovější vektory nespadají do daného tolerančního rozmezí a jestliže počet rekurzí nepřekročil předem dané dané maximum a pokračováním krokem (ii) ve zbývajícím případě, (ii) inicializováním β_Ε = (1,1,1,..., 1)^T a vypočtením předchozích pomocí zpětné rekurze následujícím způsobem:

   ⁼ Pt+iPt+ii t = L — 1,..., 1, normalizováním výsledků rekurze tak, že prvky každého mají součet jedna a uchováním všech L vektorů fi_t, (iii) vypočtením vektorů X_t spojených pravděpodobností, jejichž prvky jsou uvedené spojené pravděpodobnosti X_t, násobením prvků uvedených řádkových vektorů prvky uvedených sloupcových vektorů následujícím způsobem:

   A^ž) = Ρ^Γθ všechna i, t = 1,..., L, paměť pro uchovávání uvedených pravděpodobnostních matic a uvedených řádkových vektorů a _______________________________________________ a zařízení pro výpočet pravděpodobnosti hodnoty dekódovaného bitu, které s využitím hodnot A_ř určuje pravděpodobnost, že daný datový bit, který byl zadán kodéru v čase rovném t, je roven nule, přičemž datový bit je m-tý z k datových bitů a dále určuje slabé výstupy jako funkci uvedené pravděpodobnosti.
6. 6. Dekodér podle nároku 5, dále zahrnující prahové rozhodovací zařízení, které přijímá pravděpodobnost, že datový bit zadaný kodéru v čase rovném i, je roven nule a implementuje rozhodovací pravidlo, kterým z ní určí dekódovaný výstupní bit.
7. 7. Dekodér podle nároku 5, ve kterém uvedený trellis kód s koncovými bity zahrnuje konvoluční kód.
8. 8. Dekodér podle nároku 5 zahrnující dekodér s omezenou vzdáleností.
9. 9. Dekodér podle nároku 5, ve kterém kodér kóduje blok datových bitů, uvedené datové bity jsou seskupeny do A;-bitových symbolů pro kódování a předem dané maximum počtu rekurzí je dvojnásobek počtu A;-bitových vstupních symbolů v bloku datových bitů.
10. 10. Dekodér pro trellis kódy s koncovými bity generované kodérem, přičemž dekodér dekóduje určováním spojených pravděpodobností, že stav kodéru v čase í, označený S_t, je m a je přijat soubor L kanálových výstupů Υγ — {yi,... ,?/£,}, označených Aí(m) = P{S_t - m·, Y/'}, uvedený trellis kód má M stavů kodéru, uvedený dekodér určuje L pravděpodobnostních matic r_ř, jednu pro každou z L mřížových etap, přičemž prvky uvedených pravděpodobnostních matic jsou definovány jako

    Γί(ι, j) = P{stav j v čase t — 1; y_t | stav i v čase t — 1} rt· a to určením řádkových vektorů a*, které obsahují M prvků, představujících spojené pravděpodobnosti a jsou definovány jako = -P{stav j v čase ť, j/i,..., y_t} a určením sloupcových vektorů které obsahují M prvků, představujících podmíněné pravděpodobnosti a jsou definovány jako = P{yt + !,...,?/£ I stav j v čase t} pro j = 0,1,..., (Μ — 1), přičemž uvedený dekodér zahrnuje:

    zařízení pro výpočet matic Γ*, které přijímá uvedené kanálové výstupy, kanálové přechodové pravděpodobnosti fí(Y_ř,X), pravděpodobnosti že kodér provede přechod ze stavu m' do stavu m v čase t a pravděpodobnosti q_t(X | že výstup kodéru je X za předpokladu, že předchozí stav kodéru byl m' a současný stav kodéru je m a které z .těchto údajů určí skalární prvky uvedených pravděpodobnostních matic I\, zařízení pro výpočet součinu matic a_t, které přijímá uvedené skalární prvky matic Γχ z uvedeného zařízení pro výpočet matic Γχ a vytváří uvedené řádkové vektory a_t, = «t-ιΓχ, ř = l,...,L, zařízení pro výpočet součinu matic které vypočítává uvedené sloupcové vektory 0_t, __ __ _________ zařízení pro výpočet součinu po složkách, které vypočítává spojené pravděpodobnostní vektory Αχ, přičemž uvedené zařízení pro výpočet součinu matic a_ť, uvedené zařízení pro výpočet součinu matic β_ί a uvedené zařízení pro výpočet součinu po složkách vytvářejí uvedené vektory a_t, βί ^a (i.a) vycházejíce z počátečního «o rovného (1/M,..., l/M), Lkrát provedením přímé rekurze αχ = αχιΓχ, t = 1,..., L, a normalizováním výsledku tak, že prvky každého nového a_t mají součet jedna a uchováním všech L vektorů αχ, (i.b) položením ao rovno z kroku (i.a) a, vycházejíce z t = 1, vypočtením oit ιΓχ, t — 1,..., L_Wl

    • 0000 • 0 0 0 0 0 0 0· 00 0 • 0 Φ 0 < 0 · 0 · 0 0 0* ♦ 0 0 0 '0 0 • 0 0 0 • 0 0 0 0 0 0 0 0 0

    kde hloubka opakování L_w je předem daný počet mřížových etap, normalizováním výsledku tak, že prvky každého a_t mají součet jedna, nahrazením a vypočtenými v kroku (i.a) hodnotami at vypočtenými v kroku (i.b) pro t = 1, 2,..., L_w,

    ----------- ----. (ii.a) inicializováním = (1,1,1,..., l)^r a vypočtením před------chozích fi_t pomocí zpětné rekurze následujícím způsobem:

    fit ⁼ ^t+ifit+h t = L — 1,..., 1, normalizováním výsledků rekurze tak, že prvky každého mají součet jedna a uchováním všech L vektorů fi_t, (ii.b) položením fi_L+í rovným β₁ z kroku (ii.a) a položením Γζ,+ι = Γι, započetím pro t = L a vypočtením fit — Γt+ifit+i^ t = L, L — 1,..., L — (L_w + 1), kde hloubka opakování L_w je předem daný počet mřížových etap, ~~ normalizováním výsledku rekurze tak, že prvky každého fi_t mají součet jedna, nahrazením vypočtených v kroku (ii.a) hodnotami vypočtenými v kroku (ii.b) pro t — L, L — 1,..., L — ’ (L_w + 1), (iii) vypočtením vektorů A_ř spojených pravděpodobností, jejichž prvky jsou uvedené spojené pravděpodobnosti A_ř, násobením • 9 • 99 9

    9 99 9 prvků uvedených řádkových vektorů prvky uvedených sloupcových vektorů následujícím způsobem:

    λ/2) = 0:/2)/3/2), pro všechna i,t = 1,..., L, paměť pro uchovávání uvedených pravděpodobnostních matic a uvedených řádkových vektorů a_________________ a zařízení pro výpočet pravděpodobnosti hodnoty dekódovaného bitu, které s využitím hodnot X_t určuje pravděpodobnost, že daný datový bit, který byl zadán kodéru v čase rovném t, je roven nule, přičemž datový bit je m-tý z k datových bitů a dále určuje slabé výstupy jako funkci uvedené pravděpodobnosti.
11. 11. Dekodér podle nároku 10, dále zahrnující prahové rozhodovací zařízení, které přijímá pravděpodobnost, že datový bit zadaný kodéru v čase rovném t, je roven nule a implementuje rozhodovací pravidlo, kterým z ní určí dekódovaný výstupní bit.
12. 12. Dekodér podle nároku 10, ve kterém uvedený trellis kód s koncovými bity zahrnuje konvoluční kód.
13. 13. Dekodér podle nároku 10 zahrnující dekodér s omezenou vzdáleností.
14. 14. Dekodér podle nároku 10, ve kterém kodér kóduje blok datových bitů, uvedené datové bity jsou seskupeny do A:-bitových symbolů pro kódování a předem dané maximum počtu rekurzí je dvojnásobek počtu A:-bitových vstupních symbolů v bloku datových bitů.
15. 15. Způsob dekódování trellis kódů s koncovými bity, gene rovaných kodérem, určováním spojených pravděpodobností, že stav kodéru v čase t, označený St, je m a je přijat soubor L kanálových výstupů Υγ = {?/i,..., yi}, označených At(m) = P{S_t = τη-,Υγ'}, uvedený trellis kód má M stavů kodéru, uvedený způsob zahrnuje kroky určování L pravděpodobnostních matic Γ_ί} jednu pro každou z L mřížových etap, přičemž prvky uvedených pravděpodobnostních matic jsou definovány jako r_t(7, j) = P{stav j v čase t — 1; y_t | stav i v čase t -- 1} určování řádkových vektorů a_t, které obsahují M prvků, představujících spojené pravděpodobnosti a jsou definovány jako = P{stav j v čase ť,yi,...,y_t} a určování sloupcových vektorů které obsahují M prvků, představujících podmíněné pravděpodobnosti a jsou definovány jako

    A(j) = P{yt + l,...,yL | stav j v čase t} pro j = 0,1,..., (Μ — 1), přičemž kroky uvedeného způsobu___ zahrnují:

    určování skalárních prvků uvedených pravděpodobnostních matic r_ř na základě uvedených kanálových výstupů, kanálové přechodové pravděpodobnosti R(Y_t, X), pravděpodobnostipt(m/m'), že kodér provede přechod ze stavu m' do stavu m v čase t a pravděpodobnosti qt(X | m', m), že výstup kodéru je X za před38 pokladu, že předchozí stav kodéru byl m' a současný stav kodéru je m, vypočtení maticového součinu Γ1Γ2 ... z uvedených skalárních prvků matic I\, vypočtení normalizovaného vlastního vektoru «o, odpovídajícího největší vlastní hodnotě uvedeného maticového součinu Γ1Γ2 i.. Γ/,, vytváření následujících a_ť pomocí přímé rekurze následujícím způsobem:

    a_ř = «ί-χΓί, t = 1,...,1/, vypočtení uvedených sloupcových vektorů provedením inicializace @_L = (1,1,1,..., 1)^T a vypočtením předchozích β_ί pomocí zpětné rekurze následujícím způsobem:

    Pt — Γί+Ι^ί+Ι: i — L — 1,..., 1, vypočtení spojených pravděpodobnostních vektorů A_t, jejichž prvky jsou uvedené spojené pravděpodobnosti A_ř(ž, jí), násobením prvků uvedených řádkových vektorů prvky uvedených sloupcových vektorů následujícím způsobem: - — —

    A_ř(ž) = pro všechna i,t = 1,..., L, a vypočtení, s využitím hodnot X_t, pravděpodobnosti, že daný datový bit, který byl zadán kodéru v čase rovném t, je roven nule, přičemž datový bit je m-tý z k datových bitů a dále určení slabých výstupů jako funkce uvedené pravděpodobnosti.
16. 16. Způsob podle nároku 15, dále zahrnující krok implementující rozhodovací pravidlo, kterým se určí dekódovaný výstupní bit z pravděpodobnosti, že datový bit zadaný kodéru v čase rovném t, je roven nule.
17. 17. Dekodér podle nároku 15, ve kterém uvedený trellis kód s””koncovými””bity zahrnuje” konvoluční kód.
18. 18. Způsob dekódování trellis kódů s koncovými bity, generovaných kodérem, určováním spojených pravděpodobností, že stav kodéru v čase t, označený St, je m a je přijat soubor L kanálových výstupů Yy = {2/1,..., yi}, označených A_ť(m) = P{S_t = m; y/¹}, uvedený trellis kód má M stavů kodéru, uvedený způsob zahrnuje kroky určování L pravděpodobnostních matic Γ₍, jednu pro každou z L mřížových etap, přičemž prvky uvedených pravděpodobnostních matic jsou definovány jako r_ť(i,ý) — P{stav j v čase t — l-,y_t | stav i v Čase t — 1}, určování řádkových vektorů a_t, které obsahují M prvků, představujících spojené pravděpodobnosti a jsou definovány jako ^at(j) = P{stav j v čase ř; 3/1,..., y_t} a určování sloupcových vektorů P_t, které obsahují M prvků, představujících podmíněné pravděpodobnosti a jsou definovány jako

    A(ý) = P{yt + 1,..., 2/l I stav j v čase t} pro j = 0,1,..., (Μ — 1), přičemž kroky uvedeného způsobu zahrnují:

    určování skalárních prvků uvedených pravděpodobnostních matic r_ř na základě uvedených kanálových výstupů, kanálové přechodové pravděpodobnosti R(Yt, X), pravděpodobnosti. že kodér provede přechod ze stavu m' do stavu m v čase t a pravděpodobnosti q_t(X | τη',πι), že výstup kodéru je X za předpokladu, že předchozí stav kodéru byl m' a současný stav kodéru je m, určování uvedených vektorů at, fi_t a A_t (i.a) vycházejíce z počátečního «o rovného (1/M,..., l/JVf), Lkrát provedením přímé rekurze «i — a_ř_ir_ř, t — 1,..., L, a normalizováním výsledku tak, že prvky každého nového a_t mají součet jedna a uchováním všech L vektorů a_t, (i.b) položením ao rovno ap z kroku (i.a) a, vycházejíce z t — 1, vypočtením ^at — ^at-iPtj í — 1,..., L_Wmin, kde L_Wmin je předem daný minimální počet mřížových etap, normalizováním výsledků tak, že prvky každého a_t mají součet jedna a ponecháním pouze souboru posledních L hodnot a, nalezených rekurzí v kroku (i.a) a (i.b) a a^_w nalezené v kroku (i.a), (i.c) porovnáním ai z kroku (i.b) s «£ nalezeným v kroku (ii.a) a pokračováním do kroku (ii), jestliže hodnoty jsou uvnitř daného tolerančního rozmezí a pokračováním do kroku (ii.d) v opačném._případě,____________________________________________________________ . ________________ (i.d) položením t — t + 1 a vypočtením a_t = a^-jTí, normalizováním výsledku rekurze tak, že prvky každého a_t mají součet jedna, ponecháním pouze L nejnovějších vypočtených hodnot a a hodnot at, nalezených dříve v kroku (i.a), (i.e) porovnáním hodnoty a_t s nejnovější již nalezenou množinou hodnot z kroků (i.a), (i.b) a (i.d), postoupením do kroku (ii) jestliže se hodnoty nachází v tolerančním rozmezí, pokračováním krokem (i.d) jestliže dva nejnovější vektory nespadají do daného tolerančního rozmezí a jestliže počet rekurzí nepřekročil předem dané dané maximum a pokračováním krokem (ii) ve zbývajícím případě, (ii) inicializováním P_L — (1,1,1,..., l)^r a vypočtením předchozích pomocí zpětné rekurze následujícím způsobem:

    fit — Γί₊ιβ_ί+1, t — L — 1,..., 1, normalizováním výsledků rekurze tak, že prvky každého P_t mají součet jedna a uchováním všech L vektorů P_t, (iii) vypočtením vektorů X_t spojených pravděpodobností, jejichž

    • ··♦· • ·· ·· ♦ ··· • · • ·· · · • · · • • • · • · · e e e • © © © © © © • • ♦ · * · · ·»· > *·»···· ·· ·

    prvky jsou uvedené spojené pravděpodobnosti X_t, násobením prvků uvedených řádkových vektorů prvky uvedených sloupcových vektorů následujícím způsobem:

    X_t(i) — 0^(2)/^(2), pro všechna i,t — 1,..., L, a vypočtení, s využitím hodnot A_t, pravděpodobnosti, že daný ’daťový^_bit7~ktěřýT)ýl^_žaďán kodéru” v” čá^ Fdvňěm Týl θ roven nule, přičemž datový bit je m-tý z k datových bitů a dále určení slabých výstupů jako funkce uvedené pravděpodobnosti.
19. 19. Způsob podle nároku 18, dále zahrnující krok implementující rozhodovací pravidlo, kterým se určí dekódovaný výstupní bit z pravděpodobnosti, že datový bit zadaný kodéru v čase rovném t, je roven nule.
20. 20. Dekodér podle nároku 18, ve kterém uvedený trellis kód s koncovými bity zahrnuje konvoluční kód.
21. 21. Způsob podle nároku 18, ve kterém kodér kóduje blok datových bitů, uvedené datové bity jsou seskupeny do A:-bitových symbolů pro kódování a předem dané maximum počtu rekurzí je dvojnásobek počtu A:-bitových vstupních symbolů v bloku datových bitů.
22. 22. Způsob dekódování trellis kódů s koncovými bity, generovaných kodérem, určováním spojených pravděpodobností, že stav kodéru v čase t, označený S_t, je m a je přijat soubor L kanálových výstupů Yj^1, = {z/i,... ,y_L}, označených X_t(m) = P{S_t = m; K/}, uvedený trellis kód má M stavů kodéru, uvedený způsob zahrnuje kroky určování L podmíněných pravděpodobnostních matic r_ř, jednu pro každou z L mřížových etap, přičemž prvky uvedených pravděpodobnostních matic jsou definovány jako

    Γί(Λ J) = P{stav j v čase t — 1;^ | stav i v čase t — 1}, určování řádkových vektorů at, které obsahují M prvků, představujících spojené pravděpodobnosti a jsou definovány jako a_t(j) = Pfstav j v čase ť, ?/i,..., y_t} a určování sloupcových vektorů /?_ř, které obsahují M prvků, představujících podmíněné pravděpodobnosti a jsou definovány jako /W) = P{yt + 1, · ·, Vl i Stav j v čase t} pro j = 0,1,..., (Μ — 1), přičemž kroky uvedeného způsobu zahrnují:

    určování skalárních prvků uvedených pravděpodobnostních matic r_t na základě uvedených kanálových výstupů, kanálové přechodové pravděpodobnosti R(Y_t, X), pravděpodobnosti že kodér provede přechod ze stavu m' do stavu m v čase t a __pravděpodobnosti qt(X. | m^z, m), že výstup kodéru je X-za-před--pokladu, že předchozí stav kodéru byl m' a současný stav kodéru je m, určování uvedených vektorů a_t, fi_t a At (i.a) vycházejíce z počátečního ao rovného (1/M,..., 1/M), Lkrát provedením přímé rekurze ^at — <*ί-ιΓ,, t — 1,..., L, a normalizováním výsledku tak, že prvky každého nového a_t mají součet jedna a uchováním všech L vektorů a_t, (i.b) položením «o rovno cil ^z kroku (i.a) a, vycházejíce z t = 1, vypočtením d, cit—1Γ,, t — 1,..., L_w, kde hloubka opakování L_w je předem daný počet mřížových etap, normalizováním výsledku tak, že prvky každého a_t mají součet jedna, nahrazením a vypočtenými v kroku (i.a) hodnotami a_t vypočtenými v kroku (i.b) pro t = 1,2,..., L_w, (ii.a) inicializováním = (1,1,1,..., 1)^T a vypočtením předchozích pomocí zpětné rekurze následujícím způsobem:

    fit ⁼ Γί+ΐβί+l; t = L — 1,..., 1, normalizováním výsledků rekurze tak, že prvky každého fi_t mají součet jedna a uchováním všech L vektorů /?_ř, (ii.b) položením p_L+l rovným z kroku (ii.a) a položením Γl+i = Γι, započetím pro t = L a vypočtením fit — Γί₊ι^_ί+1, t — L, L — 1,..., L — (L_w + 1), kde hloubka opakování L_w je předem daný počet mřížových etap, normalizováním výsledku rekurze tak, že prvky každého fi_t mají * součet jedna, nahrazením fi_t vypočtených v kroku (ii.a) hodnotami fi_t vypočtenými v kroku (ii.b) pro t = L,L — 1,..., L — (L_w +1)>

    (iii) vypočtením vektorů A_t spojených pravděpodobností, jejichž prvky jsou uvedené spojené pravděpodobnosti A_ř, násobením prvků uvedených řádkových vektorů prvky uvedených sloupcových vektorů následujícím způsobem:

    Aí (ž) = (ž)/?_ř(z), pro všechna i,t = 1,..., L, a vypočtení, s využitím hodnot pravděpodobnosti, že daný datový bit, který byl zadán kodéru v čase rovném t, je roven nule, přičemž datový bit je m-tý z k datových bitů a dále určení slabých výstupů jako funkce uvedené pravděpodobnosti.
23. 23. Způsob podlěTnaroku 22, dále zahrnující krok implementující rozhodovací pravidlo, kterým se určí dekódovaný výstupní bit z pravděpodobnosti, že datový bit zadaný kodéru v čase rovném t, je roven nule.
24. 24. Dekodér podle nároku 22, ve kterém uvedený trellis kód s koncovými bity zahrnuje konvoluění kód.

    ··· · • ·

    4« · *
25. 25. Způsob podle nároku 22, ve kterém kodér kóduje blok datových bitů, uvedené datové bity jsou seskupeny do A:-bitových symbolů pro kódování a předem dané maximum počtu rekurzí je dvojnásobek počtu fc-bitových vstupních symbolů v bloku datových bitů.