Algoritmus BCJR

BCJR algoritmus , název je odvozen z iniciál vývojářů L. Bahl, J. Cocke , F. Jelínek J. Raviv, byl vyvinut v roce 1974 pro dekódování bloku a konvoluční kódy . Na rozdíl od algoritmu Viterbi , který vypočítává nejpravděpodobnější sekvenci (dekódování sekvence s maximální pravděpodobností, MLSD), je algoritmus BCJR optimálním dekódovacím algoritmem (maximální a posteriori pravděpodobnost, MAP) z hlediska minimální pravděpodobnosti chyby symbolu. Používá se proto zejména pro iterační dekódování paralelních nebo sériově spojených řetězcových nebo blokových kódů, jako jsou turbo kódy . Hraje proto důležitou roli při implementaci dekodérů pro mobilní rádiové standardy UMTS a Long Term Evolution (LTE), které používají turbo kódy pro kódování ochrany proti chybám .

Výhoda BCJR algoritmu pro dekódování konvolučních kódů pomocí takzvaného měkkého rozhodování spočívá v efektivním využití informací o kombinačních pravděpodobnostech následných kódových symbolů (typicky bitů ). Stejně jako Viterbiho algoritmus může být graficky znázorněn ve formě mřížového diagramu . Algoritmus BCJR lze kromě dekódování použít také při výpočtu obecných Markovových řetězců .

Základní myšlenka

Cílem výpočtu je a posteriori log-likelihood ratio (LLR) pro každý bit zprávy, tj. (Log) poměr pravděpodobností, že bit bude rozhodnuto v přijímači být 0 nebo 1. Nechť je bit -té zprávy a přijímací sekvence (pozorování). A a posteriori LLR pro je definován jako ${\ displaystyle u_ {l}}$ ${\ Displaystyle l}$ ${\ displaystyle \ mathbf {y}}$ ${\ displaystyle u_ {l}}$

{\ Displaystyle L (u_ {l}) = \ log \ left ({\ frac {P (u_ {l} = 0 | \ mathbf {y})} {P (u_ {l} = 1 | \ mathbf {y })}} \ že jo)}

Výsledkem maxima a posteriori (MAP) rozhodnutí u příjemce je ${\ displaystyle u_ {l}}$

{\ Displaystyle {\ hat {u}} _ {l} = \ arg \ max _ {u_ {l}} P (u_ {l} | \ mathbf {y}) = {\ begin {cases} 0 & {\ text {if}} L (u_ {l}) \ geq 0 \\ 1 & {\ text {if}} L (u_ {l}) <0 \ end {cases}}}

Obecně platí, že pro výpočet čitatele nebo jmenovatele LLR by nyní bylo třeba vzít v úvahu každé kódové slovo, pro které nebo je. Toho nelze dosáhnout u praktických kódů, protože počet kódových slov se exponenciálně mění s délkou kódového slova. Trikem algoritmu BCJR je nyní pracovat s mřížemi kódu. Mřížka bere v úvahu vlastnost, že kódová slova se skládají ze stejných částí, tj. Hrany jsou použity vícekrát. To snižuje úsilí o výpočet pravděpodobností stavu a přechodu stavu. To je obzvláště výhodné v případě konvolučních kódů , protože zde je počet stavů mřížoviny určen přímo délkou posuvného registru, a je tedy nezávislý na délce kódového slova. Složitost algoritmu se proto lineárně zvyšuje s délkou zprávy . ${\ displaystyle u_ {l} = 0}$ ${\ displaystyle u_ {l} = 1}$ ${\ displaystyle L}$

Nechte počáteční stav mřížky před bitem a následný stav. Nechť sada určí všechny stavové přechody, pro které platí, a podle toho všechny stavové přechody s . To lze použít k přepsání výše uvedeného vzorce následujícím způsobem: ${\ displaystyle s '= s_ {l-1}}$ ${\ displaystyle u_ {l}}$ ${\ displaystyle s = s_ {l}}$ ${\ displaystyle U_ {0}}$ ${\ displaystyle (s ', s)}$ ${\ displaystyle u_ {l} = 0}$ ${\ displaystyle U_ {1}}$ ${\ displaystyle (s ', s)}$ ${\ displaystyle u_ {l} = 1}$

{\ Displaystyle L (u_ {l}) = \ log \ left ({\ frac {\ sum _ {(s ', s) \ in U_ {0}} p (s_ {l} = s', s_ {l } = s, \ mathbf {y})} {\ sum _ {(s ', s) \ v U_ {1}} p (s_ {l} = s', s_ {l} = s, \ mathbf {y })}} \ že jo)}

Faktorováním vyskytující se funkce hustoty pravděpodobnosti lze výše uvedenou rovnici efektivně vypočítat pomocí dopředné a zpětné rekurze přes mříž. To je důvod, proč se algoritmu BCJR také říká algoritmus dopředu-dozadu . ${\ Displaystyle p (s ', s', \ mathbf {y})}$

Algoritmus BCJR s pravděpodobnostmi

Faktorizaci lze odvodit z posouzení mříží , přičemž platí následující: ${\ Displaystyle p (s ', s, \ mathbf {y}) = \ alpha _ {l-1} (s') \ gamma _ {l} (s ', s) \ beta _ {l} (s) }$

{\ Displaystyle {\ begin {aligned} \ alpha _ {l} (s) & = p (s_ {l} = s, \ mathbf {y} _ {1: l}) \\\ gamma _ {l} ( s ', s) & = p (s_ {l} = s, y_ {l} | s_ {l-1} = s') \\\ beta _ {l} (s) & = p (\ mathbf {y } _ {l + 1: L} | s_ {l} = s) \\\ end {zarovnaný}}}

Kroky výpočtu algoritmu BCJR jsou následující:

Dopředu rekurze začínající na ${\ Displaystyle \ alpha _ {l} (s) = \ sum _ {s '} \ gamma _ {l} (s', s) \ alpha _ {l-1} (s ')}$ ${\ Displaystyle \ alpha _ {0} (s) = {\ begin {cases} 1, & s = 0 \\ 0, & s \ neq 0 \ end {cases}}}$
Zpětná rekurze , počínaje zde Předpokládá se, že kodér se vrátí do počátečního stavu „0“. ${\ Displaystyle \ beta _ {l-1} (s ') = \ sum _ {s} \ beta _ {l} (s) \ gamma _ {l} (s', s)}$ ${\ displaystyle \ beta _ {L} (s) = {\ begin {cases} 1, & s = 0 \\ 0, & s \ neq 0 \ end {cases}}}$
Výpočet pravděpodobností asociací a z nich (viz výše). ${\ Displaystyle p (s ', s, \ mathbf {y}) = \ alpha _ {l-1} (s') \ gamma _ {l} (s ', s) \ beta _ {l} (s) }$ ${\ displaystyle L (u_ {l})}$

Hodnoty pro se vypočítají přímo z apriorních pravděpodobností (frekvencí výskytu) pro a rozdělení pravděpodobnosti přechodu kanálu jako . ${\ Displaystyle \ gamma _ {l} (s ', s) = P (u_ {l}) p (y_ {l} | u_ {l})}$ ${\ displaystyle u_ {l}}$ ${\ Displaystyle \ gamma _ {l} (s ', s) = P (u_ {l}) p (y_ {l} | u_ {l})}$

Algoritmus BCJR s logovými pravděpodobnostmi

Výpočty s pravděpodobnostmi mohou během implementace vést k numerické nestabilitě , protože rekurzivní produkty po několika krocích konvergují k hodnotám blízkým 0. Stejně tak jsou násobení velmi složitými operacemi, kterým se v hardwarových implementacích například LTE modemů kvůli jejich složitosti vyhýbá. Z tohoto důvodu je algoritmus BCJR většinou implementován v doméně protokolu; tato varianta je také známá jako algoritmus log-MAP . Násobení se stává mnohem jednodušším přidáváním, zatímco přírůstky se počítají pomocí takzvané operace max-Star. Lze to formulovat následovně:

{\ Displaystyle \ operatorname {max} ^ {*} (x, y) = \ log (e ^ {x} + e ^ {y}) = \ max (x, y) + \ log (1 + e ^ { - | xy |})}

Algoritmus BCJR v doméně protokolu se vypočítá následovně:

Dopředu rekurze začínající na ${\ Displaystyle {\ tilde {\ alpha}} _ {l} (s) = \ operatorname {max *} _ {s '} \ left ({\ tilde {\ alpha}} _ {l-1} (s' ) + {\ tilde {\ gamma}} _ {l} (s ', s) \ right)}$ ${\ Displaystyle {\ tilde {\ alpha}} _ {0} (s) = {\ begin {cases} 0, & s = 0 \\ - L _ {\ mathrm {max}}, & s \ neq 0 \ end {cases}}}$
Zpětná rekurze začínající na ${\ Displaystyle {\ tilde {\ beta}} _ {l-1} (s ') = \ operatorname {max *} _ {s} \ left ({\ tilde {\ beta}} _ {l} (s) + {\ tilde {\ gamma}} _ {l} (s, s) \ right)}$ ${\ Displaystyle {\ tilde {\ beta}} _ {L} (s) = {\ begin {cases} 0, & s = 0 \\ - L _ {\ mathrm {max}}, & s \ neq 0 \ end {cases}}}$
Výpočet MAP-LLR ${\ displaystyle {\ begin {aligned} L (u_ {l}) = & \ operatorname {max *} _ {(s ', s) \ in U_ {0}} \ left ({\ tilde {\ alpha}} _ {l-1} (s ') + {\ tilde {\ gamma}} _ {l} (s', s) + {\ tilde {\ beta}} _ {l} (s) \ right) \\ & - \ operatorname {max *} _ {(s ', s) \ in U_ {1}} \ left ({\ tilde {\ alpha}} _ {l -1} (s') + {\ tilde {\ gamma}} _ {l} (s ', s) + {\ tilde {\ beta}} _ {l} (s) \ right) \ end {aligned}}}$

Zde je takzvaná okrajová metrika, která vyplývá přímo z přijaté sekvence . ${\ Displaystyle {\ tilde {\ gamma}} _ {l} (s ', s) = \ log P (u_ {l}) + \ log p (y_ {l} | u_ {l})}$ ${\ displaystyle \ mathbf {y}}$

Individuální důkazy

↑ L. Bahl, J. Cocke, F. Jelinek a J. Raviv: Optimální dekódování lineárních kódů pro minimalizaci chybovosti symbolů , publikováno v IEEE Transactions on Information Theory, vydání IT-20 (2), strany 284 až 287, Března 1974.
↑ J. Hagenauer, E. Nabídka, L. Papke: Iterační dekódování binárních blokových a konvolučních kódů . In: IEEE Transactions on Information Theory . páska 42 , č. 2 , březen 1996, s. 429-445 , doi : 10,1109 / 18,485714 ( ieee.org [přístup 28. října 2020]).
^ S. Lin, WE Ryan: Kanálové kódy: Klasické a moderní . Cambridge University Press, Cambridge 2009, ISBN 978-0-521-84868-8 .

webové odkazy

Online učebnice: Informační teorie, odvozování a učící se algoritmy , David JC MacKay ; Kapitola 25

[1] L. Bahl, J. Cocke, F. Jelinek a J. Raviv: Optimální dekódování lineárních kódů pro minimalizaci chybovosti symbolů , publikováno v IEEE Transactions on Information Theory, vydání IT-20 (2), strany 284 až 287, Března 1974.

[2] J. Hagenauer, E. Nabídka, L. Papke: Iterační dekódování binárních blokových a konvolučních kódů . In: IEEE Transactions on Information Theory . páska 42 , č. 2 , březen 1996, s. 429-445 , doi : 10,1109 / 18,485714 ( ieee.org [přístup 28. října 2020]).

[3] S. Lin, WE Ryan: Kanálové kódy: Klasické a moderní . Cambridge University Press, Cambridge 2009, ISBN 978-0-521-84868-8 .

Languages