DE102017216264B4

DE102017216264B4 - Decodierverfahren

Info

Publication number: DE102017216264B4
Application number: DE102017216264.3A
Authority: DE
Inventors: Mustafa Cemil Coskun; Gianluigi Liva
Original assignee: Deutsches Zentrum fuer Luft und Raumfahrt eV
Current assignee: Deutsches Zentrum fuer Luft und Raumfahrt eV
Priority date: 2017-09-14
Filing date: 2017-09-14
Publication date: 2019-09-12
Anticipated expiration: 2037-09-15
Also published as: DE102017216264A1

Abstract

Verfahren zum Decodieren einer Datenbitfolge û(i=1,...,k), bei welchema) ein Datensignal y(r=1,...,n) empfangen wird, wobei es sich um ein Single-Parity-Check-Product-Code (SPC-PC) Signal handelt;b) ein SPC-PC-Decoder verwendet wird, welcher eine Vielzahl von lokalen SPC-Decodern aufweist, wobei die lokalen Decoder in mindestens einem Level l, angeordnet sind, wobei bei Vorsehen von mehr als einem Level die lokalen Decoder eines ersten Levels (l=1) mit den lokalen Decodern eines zweiten Levels (l=2) verbunden sind und wobei durch die lokalen Decoder des letzten Levels sich die Datenbitfolge ûermitteln lässt;c) durch die jeweiligen Möglichkeiten der Datenbits ûbis û∈ {0,1} P Pfade gebildet werden, wobei jeder Pfad p (p=1,...,P) i-1 Kanten aufweist, wobei jede Kante eines Pfades p jeweils ein Datenbit û(i' = 1,...,i-1) wiedergibt;d) wobei für jeden der vorhandenen Pfade p jeweils durch die lokalen Decoder die Soft-Decisions mermittelt werden für m(û= 0) sowie m(û= 1), sich somit jeder der Pfade verzweigt und somit 2P Pfade entstehen;e) wobei bei der Berechnung der Soft-Decisions mfür das i-te Bit ûalle vorherigen Entscheidungen insbesondere des jeweiligen lokalen Decoders berücksichtigt werden innerhalb des jeweiligen Pfades p;f) wobei fortgefahren wird mit der Berechnung der Soft-Decisions für das i+1-te Datenbit û;g) wobei bei Erreichen des k-ten Datenbits ûdie Soft-Decisions des Pfades p mit dem größten Soft-Decision-Wert als decodierte Datenbitfolge ûgenommen wird.

Description

Die vorliegende Erfindung betrifft ein Verfahren zum Decodieren einer Datenbitfolge, ein Übermittlungsverfahren mit einem solchen Verfahren zur Decodierung einer Datenbitfolge sowie eine Übertragungsvorrichtung zum Übertragen einer Datenbitfolge.
Bei bekannten Verfahren wird eine Datenbitfolge u_i (i = 1, ..., k) zunächst durch einen Encoder in ein Codewort x_r (r=1, ..., n) codiert. Das so codierte Codewort wird über einen verlustbehafteten Kanal zum Empfänger übertragen. Der Empfänger empfängt dabei ein Datensignal y_r, welches sodann decodiert wird zu û_i. Sofern u_i = û_i für alle i gilt, wurde die Datenbitfolge korrekt empfangen.
Aufgrund des verlustbehafteten Übertragungskanals ist es jedoch erforderlich, dass einzelne Fehler bei der Übertragung durch den Decodierer korrigiert werden können. Hierzu ist es bekannt, ein Maxium-Likelihood-Verfahren zu verwenden, bei dem zunächst Soft-Decisions berechnet werden. Bei der Soft-Decision handelt es sich in der dem Fachmann allgemein geläufigen Definition um einen Wert, der die Zuverlässigkeit der jeweiligen Entscheidung wiedergibt. Im Maximum-Likelihood-Verfahren werden sodann die Soft-Decisions ausgewählt mit dem höchsten Soft-Decision-Wert bzw. mit der größten Zuverlässigkeit für das jeweilige Codewort. Nachteilig hieran ist, dass das Maximum-Likelihood-Verfahren insbesondere für längere Codewörter, also bei großen Werten für n, sehr schnell rechenaufwändig wird und sich somit die Decodierperformance reduziert.
Insbesondere für große Blocklängen bzw. lange Codewörter ist die Verwendung von Product-Codes (PC) bekannt, bei der die langen Codewörter auf mehrere Decoder mittel Iterative-Decoding verteilt werden. Bei der Erzeugung von Codewörtern mittels PC wird eine Generatormatrix G = G₁ (⊕G₂ ⊕ ... ⊕ G_d verwendet und mittels x = uG die Codewörter erzeugt, wobei G_l der Generatormatrix der I-ten Komponente des Produktcodes entspricht, „⊕“ das Kronecker-Produkt bezeichnet und d der Dimension des PC. Hierdurch steigt zwar die Performance des Decodierverfahrens, dies jedoch auf Kosten einer gesteigerten Komplexität. Weiterhin sinkt für diese Verfahren die Blockfehlerrate, da einzelne lokale Decoder unabhängig voneinander sind.
COSKUN, M.C. [et al.]: Successive Cancellation Decoding of Single Parity-Check Product Codes, IEEE International Symposium on Information Theory, Juni 2017, S.1763-1767. IEEE Xplore [online]. DOI: 10.1109/ISIT.2017.8006832. In: IEEE beschreibt ein Decodingverfahren für Single Parity-Check Product Codes, welches auf dem sukzessiven Streichen unwahrscheinlicher Bits basiert.
Aufgabe der vorliegenden Erfindung ist es, ein Decodierverfahren zu schaffen, welches verringertem Rechenaufwand eine geringe Blockfehlerrate bzw. ein hohes Korrekturvermögen aufweist.
Die Aufgabe wird gelöst durch das Verfahren des Anspruchs 1, das Übermittlungsverfahren gemäß Anspruch 8, den Empfänger gemäß Anspruch 10 und die Übertragungsvorrichtung gemäß Anspruch 11.
Bei dem erfindungsgemäßen Verfahren zum Decodieren einer Datenbitfolge û₁ (i=1, ..., k) wird zunächst ein Datensignal y_r (r=1, ..., n) empfangen. Dabei handelt es sich bei dem Signal um ein Single-Parity-Check-Product-Code (SPC-PC) Signal, welches von einem entsprechenden Sender erzeugt wurde. Bei dem erfindungsgemäßen Verfahren wird ein SPC-PC Decoder verwendet, welcher eine Vielzahl von lokalen PC-Decodern aufweist zur Decodierung des Product-Code-Codeworts y_r. Dabei sind die lokalen Decoder in mindestens einem Level I und insbesondere einer Vielzahl von Levels I angeordnet, wobei die lokalen Decoder eines ersten Levels (I=1) mit dem lokalen Decoder eines zweiten Levels (1=2) verbunden sind, entsprechend der Struktur des verwendeten Produktcodes. Hierbei wird durch die lokalen Decoder des letzten Levels die Datenbitfolge û_i ermittelt. Hierzu weist insbesondere der SPC-PC Decoder n Eingänge im ersten Level auf und k Ausgänge im letzten Level. Die Ausgänge der lokalen Decoder des ersten Levels sind mit den Eingängen der lokalen Decoder des zweiten Levels verbunden usw.
Erfindungsgemäß werden durch die jeweiligen Bit-Möglichkeiten 0 oder 1 der Datenbits û_i bis û_i-1 ∈ {0,1} P Pfade gebildet, wobei jeder Pfad p (p=1, ..., P) i-1 Kanten aufweist und jede dieser Kanten eines bestimmten Pfades p jeweils ein Datenbit û_i' (i'=1, ..., i-1) wiedergibt. So kann beispielsweise das Datenbit û₁ die Möglichkeiten 0 oder 1 aufweisen. Somit wären bei Vollständigkeit zwei Pfade vorhanden, wobei der erste Pfad (p=1) û₁ = 0 repräsentiert und der zweite Pfad (p=2) û₁ = 1 repräsentiert. Für jedes weitere Datenbit û_i' verzweigt sich jeder dieser Pfade entsprechend den Möglichkeiten {0,1}, so dass insgesamt maximal 2^(i-1) Pfade vorliegen.
Erfindungsgemäß werden für jeden der vorhandenen Pfade p jeweils durch die lokalen Decoder die Soft-Decisions m_i ermittelt für m_i (û_i = 0) sowie m_i (û_i = 1). Bei Soft-Decisions handelt es sich um die Kombination aus dem möglichen Bitwert 0 oder 1 sowie einem Zuverlässigkeitswert bzw. Soft-Decision-Wert, welcher einen Anlasspunkt für die Wahrscheinlichkeit des jeweiligen Bitwerts angibt. Ist beispielsweise m_i (û_i = 0) = -∞, liegt eine hohe Wahrscheinlichkeit vor, dass û_i = 1. Aufgrund der Soft-Decisions verzweigt sich jeder der vorhandenen Pfade p, so dass 2P Pfade entstehen. Dabei werden bei der Berechnung der Soft-Decisions m_i für das i-te Bit û_i alle vorherigen Entscheidungen innerhalb des jeweiligen Pfades p berücksichtigt. Dabei werden insbesondere die vorherigen Entscheidungen des jeweiligen lokalen Decoders berücksichtigt. Alternativ hierzu werden die vorherigen Entscheidungen bezüglich der Datenbits û₁ bis û_i-1, innerhalb des jeweiligen Pfades p berücksichtigt. Sodann wird fortgefahren mit der Berechnung der Soft-Decisions für das i+1-te Datenbit û_i+1. Somit ergibt sich für jede Kante der Pfade p eine entsprechende Soft-Decision. Bei Erreichen des k-ten Datenbits û_k wird sodann die Soft-Decision des Pfades p mit dem höchsten Soft-Decision-Wert, also der größten Zuverlässigkeit, als decodierte Datenbitfolge û_i genommen. Hierdurch wird einerseits eine verbesserte Decodierperformance im Vergleich zum Iterative-Decoding erreicht. Gleichzeitig werden aufgrund der zunächst erfolgten Ermittlung von Soft-Decisions die bisherigen Entscheidungen im Decodiervorgang berücksichtigt. Hierdurch wird das Korrekturvermögen für fehlerhaft übertragene Bits im Datensignal y_r erhöht und die Blockfehlerrate reduziert.
Vorzugsweise wird ein Wert L > 1 festgelegt. Für den Fall, dass die Anzahl der vorhandenen Pfade P > L wird, werden die Pfade p ausgewählt, welche den größten Soft-Decision-Wert, also die größte Zuverlässigkeit aufweisen. Sodann werden so viele Pfade verworfen, bis P ≤ L ist. Somit wird die Anzahl der zu berücksichtigenden Pfade auf L reduziert, insbesondere nach jeder Decodierung eines weiteren Datentbits û_i. Wurden die Soft-Decisions für das Datenbit û_i bestimmt, wird sodann überprüft, ob weiterhin P ≤ L erfüllt ist. Anderenfalls wird eine entsprechende Anzahl von Pfaden mit einem geringen Soft-Decision-Wert verworfen.
Vorzugsweise ergibt sich die Anzahl η_l der lokalen Decoder auf dem Level I aus $η_{l} = \prod_{i' = 1}^{l - 1} (n_{i'} - 1) \prod_{i' = l + 1}^{d} n_{i'},$
wobei 1 ≤ I ≤ d und d die Dimension des PC angibt. Dabei ist n_i' die Blocklänge der lokalen Decoder auf dem Level i'.
Vorzugsweise wird ein Cyclic-Redundancay-Check (CRC) Code angewandt auf die verbleibenden Möglichkeiten nach Ermittlung der Soft-Decision des k-ten Datenbits û_k. Verbleiben sodann mehr als eine mögliche Datenbitfolge û_i, so wird aus den verbleibenden Pfaden p der Pfad mit den größten Soft-Decision-Werten ausgewählt.
Vorzugsweise handelt es sich beim dem Single-Parity-Check-Product-Code (SPC-PC) um einen (k,n)-PC Blockcode mit k ≥ 4 und n ≥ 9. Bevorzugt ist k ≥ 64 und n ≥ 125. Besonders bevorzugt ist k ≥ 125 und n ≥ 216. Somit können auch Codes mit langer Blocklänge n effizient verarbeitet und decodiert werden.
Vorzugsweise berechnen sich die Soft-Decision m_i zu $\begin{matrix} m_{l, j, i}^{p} (0) = P_{l, j, i}^{p} (0) + \sum_{i' = 1}^{i - 1} P_{l, j, i'}^{p} (λ_{l, j, i'}^{p}) \\ + max_{c_{i + 1}, \dots c_{n_{l}}} * [1 (λ_{l, j,1}^{p} \oplus \dots \oplus λ_{l, j, i - 1}^{p} \oplus 0 \oplus c_{i + 1} \oplus \dots \oplus c_{n_{l}} = 0) \sum_{i' = i + 1}^{n_{l}} P_{l, j, i'}^{p} (c_{i'})] \end{matrix}$
$\begin{matrix} m_{l, j, i}^{p} (1) = P_{l, j, i}^{p} (1) + \sum_{i' = 1}^{i - 1} P_{l, j, i'}^{(l), p} (λ_{l, j, i'}^{p}) \\ + max_{c_{i + 1}, \dots c_{n_{l}}} * [1 (λ_{l, j,1}^{p} \oplus \dots \oplus λ_{l, j, i - 1}^{p} \oplus 1 \oplus c_{i + 1} \oplus \dots \oplus c_{n_{l}} = 0) \sum_{i' = i + 1}^{n_{l}} P_{l, j, i'}^{p} (c_{i'})] \end{matrix}$
für den jeweiligen Pfad p, wobei I den Level des lokalen Decoders j bezeichnet und P^P _l,_j,_l' die ermittelten Soft-Decision-Werte bzw. Zuverlässigkeitswerte der vorhergehenden Entscheidungen. λ entspricht dabei den vorgehenden Entscheidungen und c_i+1, ..., c_nl ∈ {0,1} werden dabei so gewählt, dass ein Codewort entsteht, insbesondere mit einem Maximalwert für die Soft-Decision. Dabei ist n_l die Blocklänge des j-ten lokalen Decoders im Level l. Somit ist eine komplette Vorschrift für die Soft-Decisions gegeben, wobei die vorhergehenden Entscheidungen λ berücksichtigt werden. Somit wird für jede vorhandene Möglichkeit der Datenbitfolge û_i bzw. für die L-zuverlässigsten Varianten entsprechend dem jeweiligen Pfad die Zuverlässigkeitswerte des i-ten Datenbits û_i ermittelt.
Vorzugsweise erfolgt die Weiterleitung der ermittelten Soft-Decisions von einem lokalen Decoder j im Level I auf den nächsten lokalen Decoder j' im Level 1+1 durch die Weiterleitung von m^P _l,j,l (0) nach P^Pl₊₁,_j',_l' (0) sowie für die zweite Möglichkeit für das Datenbit û_i mit m^P _l,j,l (1) nach P^Pl_+1,j',_l' (1).
Weiterhin betrifft die Erfindung ein Übermittlungsverfahren mit einem Sender, wobei der Sender eine Datenbitfolge u = u₁, ..., u_k codiert mittels einem SPC-PC Code in das Codewort x = x₁, ..., x_n. Dabei wird zur Codierung des Codeworts x die Generatormatrix G = G₁ ⊕ G₂ ⊕ ... ⊕ G_d mittels x = uG, wobei G_l der Generatormatrix der I-ten Komponente des Product-Codes entspricht und d der Dimension des PC.
Im erfindungsgemäßen Übermittlungsverfahren wird sodann das Codewort x über einen Übertragungskanal übertragen. Dabei handelt es sich insbesondere um einen gestörten Übertragungskanal bzw. einen verlustbehafteten Übertragungskanal. Insbesondere handelt es sich um einen Binary-Input-Discrete gedächtnislosen Übertragungskanal (B-DMC). Durch den Übertragungskanal wird das Codewort x gestört, so dass vom Empfänger ein gestörtes Codewort y = y₁, ..., y_n empfangen wird. Würde es sich bei dem Übertragungskanal um einen verlustfreien idealen Kanal handeln, würde das ungestörte Codewort y dem gesendeten Codewort x entsprechen.
Bei dem erfindungsgemäßen Übermittlungsverfahren wird das empfangene Codewort y decodiert gemäß dem vorstehend beschriebenen Verfahren zum Decodieren einer Datenbitfolge û = û₁, ..., û_k, so dass û ermittelt wird, welches der ursprünglichen Datenbitfolge u bei fehlerfreier Decodierung entspricht.
Vorzugsweise ist vor der Erzeugung des Codeworts x zunächst ein CRC-Encoder vorgesehen zur Erzeugung einer mitübertragenen CRC-Prüfsumme.
Weiterhin betrifft die vorliegende Erfindung einen Empfänger zum Empfangen und Decodieren einer Datenbitfolge u mit einer Empfangsvorrichtung zum Empfangen eines Datensignals y = y₁, ..., y_n und einem Decodierer. Dabei ist der Decodierer ausgebildet zur Durchführung des Verfahrens zur Decodierung einer Datenbitfolge û = û₁, ..., û_k, wie vorstehend beschrieben.
Weiterhin betrifft die vorliegende Erfindung eine Übertragungsvorrichtung mit einem Sender, wobei der Sender eine Datenquelle und einen Codierer aufweist. Dabei ist der Codierer ausgebildet, um eine Datenbitfolge u der Daten-Datenquelle zu codieren mittels einem SPC-PC Code in ein Codewort x. Weiterhin weist die Übertragungsvorrichtung einen Übertragungskanal auf. Insbesondere handelt es sich hierbei um einen Binary-Input-Discrete gedächtnislosen Übertragungskanal (B-DMC). Weiterhin weist die Übertragungsvorrichtung einen Empfänger auf, wobei von dem Empfänger ein gestörtes Codewort y empfangen wird. Dabei ist der Empfänger ausgebildet wie vorstehend beschrieben.
Vorzugsweise ist zwischen der Datenquelle und dem Codierer ein CRC-Encoder vorgesehen zur Erstellung einer CRC-Prüfsumme, welche vom Sender mitgesendet wird. Weiterhin weist der Empfänger einen CRC-Decoder auf zur Überprüfung der decodierten Datenbitfolge.
Vorzugsweise handelt es sich bei dem Übertragungskanal um eine Funkverbindung oder eine kabelgebundene Verbindung oder eine optische Datenübertragung.
Nachfolgend wird die Erfindung anhand einer bevorzugten Ausführungsform unter Bezugnahme auf die beigefügten Zeichnungen näher erläutert.
Es zeigen:

1 einen Decodiergraph für einen beispielhaft gewählten (9, 4) SPC-PC,
2 den Decodiergraph der 1 mit Eingangswerten,
3 (a) bis 3 (e): Entscheidungsschritte des Decodierverfahrens gemäß dem Decodiergraph der 1,
4 den Decodiergraph der 1, bei der Entscheidung des dritten Bits,
5 eine schematische Darstellung der Berücksichtigung der vorhergehenden Entscheidungen für einen ausgewählten lokalen Decoder und
6 eine Ausführungsform des erfindungsgemäßen Übertragungsverfahrens.

1 zeigt einen Tanner-Graph für das erfindungsgemäße Decodierverfahren zur Decodierung einer Datenbitfolge û_i (i=1, ..., k) am Beispiel eines (n=9, k=4)-Single-Parity-Check-Product-Code (SPC-PC). Der in 1 dargestellte SPC-PC Decoder weist neun Eingänge auf, über die die neun Bits des empfangenen Codeworts y_r (r=1, ..., 9) in den SPC-PC Decoder gelangen. Bei dem Decodergraphen der 1 sind mit „=“ Variablenknoten gekennzeichnet, wohingegen mit „+“ Checkknoten gekennzeichnet sind. Der SPC-PC Decoder weist dabei einen ersten Level 10 sowie einen zweiten Level 12 auf. Im ersten Level 10 sind drei lokale SPC-PC Decoder 14 vorgesehen, deren Eingänge die entsprechenden Bits des übertragenen Codeworts y_i entgegennehmen. Die Ausgänge der lokalen Decoder 14 des ersten Levels 10 sind mit Eingängen von lokalen Decodern 16 des zweiten Levels 12 verbunden. Durch die lokalen Decoder 16 des zweiten Levels 12 lassen sich die übertragenen Datenbits û₁ bis û₄ ermitteln. Die Struktur des in 1 gezeigten SPC-PC Decoders richtet sich dabei nach der zugrundeliegenden PC-Struktur bzw. der verwendeten Generatormatrix G.
Durch die einzelnen lokalen Decoder 14, 16 wird keine finale Entscheidung über das jeweilige Datenbit û_i getroffen, sondern lediglich Soft-Decisions m_i für die beiden möglichen Werte 0 und 1 des jeweiligen Datenbits û_i.
Gemäß 2 wird das empfange Datensignal y_r durch den SPC-PC-Decoder als Log-Likelihoods P^P _l,j,i (0) bezüglich einer möglichen 0 und P^P _l,j,i (1) bezüglich einer möglichen 1 definiert, wobei p den jeweiligen Pfad angibt, I den entsprechenden Level, wobei l = 1 für den ersten Level gilt, und j den jeweiligen lokalen Decoder des Levels I bezeichnet. Dabei ergeben sich die Log-Likelihoods zu $P_{1, j, i}^{1} (0) ≜ ln [W (y (j - 1) n_{1} + i | 0)]$
$P_{1, j,i}^{1} (1) ≜ ln [W (y (j - 1) n_{1} + i | 1)]$
Sodann werden die Soft-Decisions für das erste Datenbit û₁ berechnet gemäß $\begin{matrix} m_{l, j, i}^{p} (0) = P_{l, j, i}^{p} (0) + \sum_{i' = 1}^{i - 1} P_{l, j, i'}^{p} (λ_{l, j, i'}^{p}) \\ + max_{c_{i + 1}, \dots c_{n_{l}}} * [1 (λ_{l, j,1}^{p} \oplus \dots \oplus λ_{l, j, i - 1}^{p} \oplus 0 \oplus c_{i + 1} \oplus \dots \oplus c_{n_{l}} = 0) \sum_{i' = i + 1}^{n_{l}} P_{l, j, i'}^{p} (c_{i'})] \end{matrix}$
$\begin{matrix} m_{l, j, i}^{p} (1) = P_{l, j, i}^{p} (1) + \sum_{i' = 1}^{i - 1} P_{l, j, i'}^{(l) p} (λ_{l, j, i'}^{p}) \\ + max_{c_{i + 1}, \dots c_{n_{l}}} * [1 (λ_{l, j,1}^{p} \oplus \dots \oplus λ_{l, j, i - 1}^{p} \oplus 1 \oplus c_{i + 1} \oplus \dots \oplus c_{n_{l}} = 0) \sum_{i' = i + 1}^{n_{l}} P_{l, j, i'}^{p} (c_{i'})] \end{matrix}$
wobei P den jeweiligen Pfad bezeichnet, I den Level des lokalen Decoders j, λ den bisherigen Entscheidungen entspricht und c_l+1, ..., c_nl ∈ {0,1} mit n_l der Blocklänge des lokalen Decoders j im Level l. Dabei berechnet sich max* gemäß $\begin{array}{l} max* (x_{i}) = max* (x 1, \dots, x n) = ln (e^{x_{1}} + \dots + e^{x_{n}}) \\ X_{1}, \dots, x_{n} \end{array}$
Somit ergeben sich gemäß 3 (a) zwei Möglichkeiten 0 und 1 mit den dafür berechneten Soft-Decisions m_i (0) sowie m_i (1), wobei für jede Möglichkeit ein Pfad vorliegt und somit P=2.
Sodann wird gemäß 3 (b) mit der Decodierung des zweiten Datenbits û₂ fortgefahren. Hierbei werden für jeden der vorhandenen Pfade p wiederum beide Möglichkeiten für das Datenbit û₂ berücksichtigt und die entsprechenden Soft-Decisions ermittelt, sodass vier Pfade entstehen. Bei der Ermittlung der Soft-Decisions für û₂ werden dabei die vorhergehenden Entscheidungen λ, die zu dem ersten Datenbit û₁ geführt haben, berücksichtigt.
4 zeigt exemplarisch die Situation bei der Entscheidung des dritten Datenbits û₃. Die Entscheidungen bezüglich des ersten Datenbits û₁ sowie û₂ werden von links nach rechts im Decodiergraphen der 4 zurückgeführt und durch die lokalen Decoder berücksichtigt als λ^P _l,j,z, z=1, ..., i-1 für den jeweiligen Pfad p. Die Soft-Decisions für das dritte Datenbit û₃ werden somit bestimmt aus den vorherigen Entscheidungen, wobei die Soft-Decisions des ersten Levels m^P _1,j,i Eingang finden in die lokalen Decoder des zweiten Levels, wobei $P_{l + 1, j', i'}^{p} (0) \leftarrow m_{l, j, i}^{p} (0) and P_{l + 1, j', i'}^{p} (1) \leftarrow m_{l, j, i}^{p} (1) .$
Gemäß der 3 (c) wird somit für jede weitere Möglichkeit ein weiterer Pfad erstellt, sodass nach der Ermittlung der Soft-Decisions für û₃ acht Pfade vorliegen, wobei jeder Pfad genau drei Kanten aufweist. Unter der Annahme, dass ein Parameter L = 4 gewählt sei, übersteigt nun die Anzahl der Pfade P die gewählten Parameter, sodass P > L. Sodann werden gemäß der Ausführungsform des beschriebenen Verfahrens die Pfade ausgewählt, welche die höchste Zuverlässigkeit aufweisen, und dann so viele Pfade mit geringer Zuverlässigkeit bzw. niedrigerem Soft-Decision-Wert herausgestrichen, bis P ≤ L. Dies ist in 3 (d) gezeigt, wobei lediglich auf Grund der Wahl von L = 4 genau vier Pfade übrig bleiben. Hierdurch wird sichergestellt, dass insbesondere bei großen Blocklängen nicht unnötige, weil unwahrscheinliche Kombinationen der Datenbits û_i weiterhin berücksichtigt werden.
In einem weiteren Schritt gemäß der 3 (e) wird das letzte Datenbit û₄ ermittelt durch Ermittlung der jeweiligen Soft-Decisions für die möglichen Werte von û₄ mit 0 oder 1. Somit verzweigt sich jeder Pfad erneut, so dass wiederum acht Pfade entstehen. Hierbei werden wiederum die vorhergehenden Entscheidungen berücksichtigt.
Exemplarisch ist dies für den Allgemeinfall für einen ausgewählten lokalen Decoder in der 5 dargestellt, bei dem die bisherigen Entscheidungen λ^P _l,_j,₁, ... λ^P _l,j,i-1 berücksichtigt werden sowie die entsprechenden Log-Likelihood-Werte, welche von der rechten Seite einfließen. Sodann werden für den j-ten lokalen Decoder auf dem I-ten Level für den p-ten Pfad die Soft-Decisions m^P _l,j,l (0) sowie m^P _l,j,i (1) für die möglichen Werte 0 und 1 ermittelt.
In einer ersten Alternative wird nach Ermitteln aller Soft-Decisions für jeden der Datenbits û₁ bis û₄ derjenige Pfad ausgewählt, mit dem höchsten Soft-Decision-Wert bzw. mit der höchsten Zuverlässigkeit. Alternativ hierzu ist, wie in 6 gezeigt, ist zwischen der Informationsquelle 18 und dem SPC-PC Encoder 10, 20 ein CRC (Cyclic-Redundancay-Check)-Encoder 22 vorgesehen, der eine CRC-Prüfnummer erstellt, welche in das Codewort durch den SPC-PC Encoder 20 eingebettet und über den Übertragungskanal 24 mitübertragen wird. Durch den SPC-PC Decoder 26 werden sodann, wie vorstehend beschrieben, die Datenbits û_i decodiert, welche die CRC-Prüfsumme enthalten. Die dabei auftretenden möglichen Pfade werden sodann in einem CRC Decoder 28 anhand der übermitteln CRC-Prüfsumme auf deren Integrität überprüft, so dass aus den durch den Decoder 26 ermittelten möglichen Pfaden derjenige ausgesucht wird, welcher den CRC-Test besteht. Stimmt die Prüfsumme für mehrere der möglichen Pfade, die durch den Decoder 26 ermittelt wurden, so wird derjenige mit dem höchsten Soft-Decision-Wert bzw. mit der höchsten Zuverlässigkeit ausgewählt und als übertragenes Signal bzw. zu übertragende Datenbitfolge u angesehen. Somit wird in dieser Variante einerseits das fehlertolerante Decodierverfahren mittels Soft-Decision implementiert, wobei auch große Blocklängen aufgrund der Verwendung des Produktcodes berücksichtigt werden können. Weiterhin können durch die nachgeschaltete Verwendung eines CRC Decoders weitere Fehler vermieden werden. Somit ist ein Decodierverfahren geschaffen mit einer hohen Performance und einer geringen Blockfehlerrate bzw. einem hohen Korrekturvermögen.

Claims

Verfahren zum Decodieren einer Datenbitfolge û_i (i=1,...,k), bei welchem a) ein Datensignal y_r (r=1,...,n) empfangen wird, wobei es sich um ein Single-Parity-Check-Product-Code (SPC-PC) Signal handelt; b) ein SPC-PC-Decoder verwendet wird, welcher eine Vielzahl von lokalen SPC-Decodern aufweist, wobei die lokalen Decoder in mindestens einem Level l, angeordnet sind, wobei bei Vorsehen von mehr als einem Level die lokalen Decoder eines ersten Levels (l=1) mit den lokalen Decodern eines zweiten Levels (l=2) verbunden sind und wobei durch die lokalen Decoder des letzten Levels sich die Datenbitfolge û_i ermitteln lässt; c) durch die jeweiligen Möglichkeiten der Datenbits û₁ bis û_i-1 ∈ {0,1} P Pfade gebildet werden, wobei jeder Pfad p (p=1,...,P) i-1 Kanten aufweist, wobei jede Kante eines Pfades p jeweils ein Datenbit û_i' (i' = 1,...,i-1) wiedergibt; d) wobei für jeden der vorhandenen Pfade p jeweils durch die lokalen Decoder die Soft-Decisions m_i ermittelt werden für m_i(û_l = 0) sowie m_i(û_i = 1), sich somit jeder der Pfade verzweigt und somit 2P Pfade entstehen; e) wobei bei der Berechnung der Soft-Decisions m_i für das i-te Bit û_i alle vorherigen Entscheidungen insbesondere des jeweiligen lokalen Decoders berücksichtigt werden innerhalb des jeweiligen Pfades p; f) wobei fortgefahren wird mit der Berechnung der Soft-Decisions für das i+1-te Datenbit û_i+1; g) wobei bei Erreichen des k-ten Datenbits û_k die Soft-Decisions des Pfades p mit dem größten Soft-Decision-Wert als decodierte Datenbitfolge û_i genommen wird.
Verfahren nach Anspruch 1, bei welchem ein Wert L > 1 festgelegt wird und für den Fall, dass die Anzahl der vorhandenen Pfade P > L, die Pfade p ausgewählt werden mit dem größten Soft-Decision-Wert, wobei so viele Pfade verworfen werden, bis P ≤ L.
Verfahren nach Anspruch 1 oder 2, bei welchem die Anzahl η_l der lokalen Decoder auf dem Level I sich ergibt aus $η_{l} = \prod_{i' = 1}^{l - 1} (n_{i'} - 1) \prod_{i = l + 1}^{d} n_{i'}$
wobei 1 ≤ I ≤ d, wobei d die Dimension des PC angibt und n_i' die Blocklänge des lokalen Decoders auf dem Level i'.
Verfahren nach einem der Ansprüche 1 bis 3, bei welchem ein Cyclic-Redundancy-Check (CRC) Code angewandt wird auf die verbleibenden Möglichkeiten nach Ermittlung der Soft-Decisions des k-ten Datenbits û_k und nachfolgend aus den verbleibenden Pfaden der Pfad mit dem größten Soft-Decision-Wert ausgewählt wird.
Verfahren nach einem der Ansprüche 1 bis 4, bei welchem es sich um einen (k,n)-PC Blockcode handelt, wobei k≥4 und n≥9.
Verfahren nach einem der Ansprüche 1 bis 5, bei welchem die Soft-Decisions m_i sich berechnen zu $\begin{matrix} 1 m_{l, j, i}^{p} (0) = P_{l, j, i}^{p} (0) + \sum_{i' = 1}^{i - 1} P_{l, j, i'}^{p} (λ_{l, j, i'}^{p}) \\ + max_{c_{i + 1}, \dots c_{n_{l}}} * [1 (λ_{l, j,1}^{p} \oplus \dots \oplus λ_{l, j, i - 1}^{p} \oplus 0 \oplus c_{i + 1} \oplus \dots \oplus c_{n_{l}} = 0) \sum_{i' = i + 1}^{n_{l}} P_{l, j, i'}^{p} (c_{i'})] \end{matrix}$
$\begin{matrix} m_{l, j, i}^{p} (1) = P_{l, j, i}^{p} (0) + \sum_{i' = 1}^{i - 1} P_{l, j, i'}^{(l) p} (λ_{l, j, i'}^{p}) \\ + max_{c_{i + 1}, \dots c_{n_{l}}} * [1 (λ_{l, j,1}^{p} \oplus \dots \oplus λ_{l, j, i - 1}^{p} \oplus 1 \oplus c_{i + 1} \oplus \dots \oplus c_{n_{l}} = 0) \sum_{i' = i + 1}^{n_{l}} P_{l, j, i'}^{p} (c_{i'})] \end{matrix}$
für den Pfad p, wobei l den Level des lokalen Decoders j bezeichnet, P^P _l,j,i' die ermittelten Soft-Decision-Werte der vorhergehenden Entscheidungen, λ den bisherigen Entscheidungen entspricht und c_i+1,...,c_nl ∈ {0,1} so gewählt sind, dass ein Codewort entsteht mit nl der Blocklänge des j-ten lokalen Decoder im Level l.
Verfahren nach Anspruch 6, bei welchem die Weiterleitung der ermittelten Soft-Decisions von einem lokalen Decoder j auf den nächsten lokalen Decoder j' erfolgt durch m^P _l,j,i(0) → P^P _l+1,j',i'(0) , sowie m^P _l,j,i(1) → P^P _l+1,j',i'(1).
Übermittlungsverfahren mit einem Sender, wobei der Sender eine Datenbitfolge u codiert mittels einem SPC-PC Code in ein Codewort x, das Codewort x übertragen wird über einen Übertragungskanal und ein gestörtes Codewort y von einem Empfänger empfangen wird, wobei ein ungestörtes Codewort y dem gesendeten Codewort x entspräche, wobei durch den Empfänger das empfangene Codewort decodiert wird gemäß dem Verfahren nach einem der Ansprüche 1 bis 7, so dass û ermittelt wird, welche der ursprünglichen Datenbitfolge u bei fehlerfreier Decodierung entspricht.
Übermittlungsverfahren nach Anspruch 8, bei welchem vor Erzeugung des Codeworts x zunächst ein CRC-Encoder vorgesehen ist zur Erzeugung einer mitübertragenen CRC-Prüfsumme.
Empfänger zum Empfangen und Decodieren einer Datenbitfolge u, mit einer Empfangsvorrichtung zum Empfangen eines Datensignals und einem Decodierer, wobei der Decodierer ausgebildet ist zur Durchführung des Verfahrens nach einem der Ansprüche 1 bis 7.
Übertragungsvorrichtung, mit einem Sender, wobei der Sender eine Datenquelle aufweist und einen Codierer, wobei der Codierer ausgebildet ist, um eine Datenbitfolge u der Datenquelle zu codieren mittels einem SPC-PC Code in ein Codewort x, einem Übertragungskanal und einem Empfänger, wobei ein gestörtes Codewort y von dem Empfänger empfangen wird, wobei der Empfänger ausgebildet ist gemäß einem Empfänger nach Anspruch 10.
Übertragungsvorrichtung nach Anspruch 11, bei welchem zwischen der Datenquelle und dem Codierer ein CRC-Encoder vorgesehen ist zur Erstellung einer CRC-Prüfsumme sowie der Empfänger einen CRC-Decoder aufweist zur Überprüfung der decodierten Datenbitfolge.
Übertragungsvorrichtung nach Anspruch 11 oder 12, wobei es sich bei dem Übertragungskanal um eine Funkverbindung oder eine kabelgebundene Verbindung oder eine optische Datenübertragung handelt.