Was sind weniger rechenintensive Alternativen zum Viterbi-Decoder?

7

Was sind weniger rechenintensive Alternativen zum Viterbi-Decoder?

Im Idealfall möchte ich eine Liste der am häufigsten verwendeten Näherungsmethoden sowie kurze Vor- und Nachteile.

Gyroidben
quelle
Fragen Sie speziell nach der Dekodierung von Faltungsfehlerkorrekturcodes (wahrscheinlich die bekannteste Anwendung)? Der Viterbi-Algorithmus kann in einer Reihe von Anwendungen verwendet werden, bei denen eine Sequenzerkennung mit maximaler Wahrscheinlichkeit gewünscht wird.
Jason R
Ja, daran habe ich gedacht. Ich würde mich sowohl für Algorithmen interessieren, die für diese Anwendung spezifisch sind, als auch für allgemeinere Methoden zur Erkennung von ML-Sequenzen.
Gyroidben

Antworten:

5

Eine einfache Alternative zu einem Viterbi-Decoder zum Decodieren von Faltungscodes ist ein sequentieller Decoder. Der Algorithmus ist einfacher, aber die Leistung ist nicht so gut. Beispielsweise sind die üblichen Beschränkungslängen für Systeme, die eine Viterbi-Decodierung verwenden, typischerweise k = 7 oder k = 9. Ein System, das mit einem sequentiellen Decodierer decodiert wird, hat typischerweise eine Beschränkungslänge in den dreißiger Jahren oder so. Die Komplexität eines Viterbi-Decoders wäre bei einer so langen Beschränkungslänge unerschwinglich, und die Leistung eines sequentiellen Decoders ist bei den kurzen Beschränkungslängen, die mit einem Viterbi-Decoder verwendet werden, sehr schlecht.

Eine andere Alternative wäre die Verwendung eines APP- oder MAP-Decoders, die jedoch komplexer sind als ein Viterbi-Decoder (da es sich im Wesentlichen um zwei Viterbi-Decoder handelt, die in entgegengesetzten Richtungen zusammenlaufen). Wenn Sie jedoch nur sagen möchten, dass Sie keinen "Viterbi" -Decoder verwenden, der sich möglicherweise qualifiziert.

Eric Jacobsen
quelle
4

Ein (alles andere als optimaler) Ansatz:

Ein Faltungscode mit halber Rate kann als zwei multiplikativ verschlüsselte Kanalcodierer angesehen werden, die zusammen gemultiplext werden. Sie können die beiden Pfade mit den inversen multiplikativen Descramblern dekodieren und dann die beiden Pfade kombinieren. Auch wenn Sie die Entwürflern schaffen weiche Entscheidungen zu treffen, werden die Ergebnisse weit vom Optimum entfernt , sollte aber sehr schnell sein.

Mark Borgerding
quelle