Browse Prior Art Database

Beschleuniger für Rate 1/n Viterby-Decodierer

IP.com Disclosure Number: IPCOM000017392D
Original Publication Date: 2000-Oct-01
Included in the Prior Art Database: 2003-Jul-25
Document File: 4 page(s) / 27K

Publishing Venue

Siemens

Related People

Dr. Andreas Falkenberg: AUTHOR

Abstract

Der Viterby-Algorithmus wird in vielen Bereichen zur Sicherung von Daten eingesetzt. Das einzige Problem dieser sehr effektiven Decodierungsmethode ist der Ressourcenbedarf, so dass fast immer eine Hardwareunterstütztung notwendig ist. Der hier dargestellte, modifizierte Algorithmus bietet eine sehr effiziente Methode zur Berechnung der Metriken, womit eine starke Beschleunigung des Viterby-Algorithmuses möglich ist. Optimal wäre es, die dargestellten Funktionen der Metriken als Hardware zu implementieren.

This text was extracted from an ASCII text file.
This is the abbreviated version, containing approximately 36% of the total text.

- 78 -

Information / Kommunikation

Beschleuniger für Rate 1/n Viterby-Decodierer

Idee: Dr. Andreas Falkenberg, Bocholt

Der Viterby-Algorithmus wird in vielen Bereichen zur Sicherung von Daten eingesetzt. Daseinzige Problem dieser sehr effektiven Decodierungsmethode ist der Ressourcenbedarf, sodass fast immer eine Hardwareunterstütztung notwendig ist. Der hier dargestellte,modifizierte Algorithmus bietet eine sehr effiziente Methode zur Berechnung der Metriken,womit eine starke Beschleunigung des Viterby-Algorithmuses möglich ist. Optimal wäre es,die dargestellten Funktionen der Metriken als Hardware zu implementieren.

Ein wesentlicher Anteil der Rechenzeit bei der Decodierung mit einem Viterby-Algorithmusentsteht durch die Berechnung der Pfadmetrik. Für jeden möglichen Pfad muss dabei derHammmingabstand zwischen den Inputbits und den korrekten Bits, die zur Wahl einesbestimmten Pfades führen, berechnet werden. Im Rahmen dieses Textes soll nun eineLösung vorgeschlagen werden, die im Wesentlichen dazu geeignet ist, eine optimierteHardwareimplementierung zu finden.

Als Beispiel für die weitere Betrachtung soll der in Abbildung 1 dargestellte Codiererdienen, für den anschliessend ein Decodierer entwickelt werden soll.

Die wesentlichen Schritte sind dabei die folgenden:Zuerst wird die Wertetabelle des Dekodierers (Tab. 1) aufgestellt.

Aus den vier Inputs 1

0

10 ,

,  iund

i

zz   kann sowohl mit der KNF (konjunktive Normalform)als auch mit der DNF (disjunktive Normalform) der Output 0 berechnet werden. Dieser istkorrekt, wenn keine Fehler im Eingangsdatenstrom auftreten. Wird ein fehlerhafter Inputgeliefert, so ist die Wertetabelle an der entsprechenden Stelle nicht definiert. Es wird bei derKonstruktion der DNF impliziert, dass alle nicht definierten Inputs zu einem Output von 0führen. Dies liegt daran, dass nur die Terme genutzt werden, die als Ergebnis eine 1 liefern.Umgekehrt ist dies bei der Konstruktion der KNF. Hier werden nur die Terme betrachtet,die als Ausgabe eine 0 liefern, alle anderen Inputs führen somit zu einer 1 als Output. Andieser Stelle soll nun von der DNF ausgegangen werden. Nachdem die DNF für dasgegebene Beispiel konstruiert wurde, wird sie so erweitert, dass es möglich wird, hierausdie Metriken für die Softdecision-Decodierung zu berechnen.

Die DNF sieht wie folgt aus:

,

DNF

0

(

z

,

z

i

,

i

i

)

=

1

0

1

(

z

0

Ù

z

1

Ù

Ù

i

)

Ú

(

z

Ù

Ù

0

1

0

1

z

i

0

Ù

i

1

)

Ú

(

z

Ù

z

)

0

1

Ù

i

0

Ù

i

Ú

(

z

Ù

z

Ù

i

Ù

i

1

0

1

0

1

)

Siemens Technik Report

Jahrgang 3  Nr. 9  Oktober 2000

- 79 -

Die dargestellte DNF decodiert richtig, wenn die Inputs korrekt sind. Wenn die Inputs nichtkorrekt sind, also ein Bitfehler auftritt, so wird immer eine 0 ausgegeben. Es wird alsoimmer in eine "Richtung" dekodiert.

Um die DNF zur Berechnung der Metrik eines Softdecision Viterby Algorithmus benutzenzu können, muss sie modifiziert werden. Die Modifikation besteht nun darin, Werte aus demWertebereich [0, 1 ] als Inputs zuzulassen (...