iese Erfindung betrifft insgesamt ein zyklisches Redundanzprüfungsverfahren zur Detektion von Nachrichtenlängen in einem Variable-Längen-Kommunikationssystem, und insbesondere ein modifiziertes zyklisches Redundanzprüfungsverfahren mit geringer Falschdetektions-Wahrscheinlichkeit für ein Variable-Längen-Kommunikationssystem, welches ein Faltungs-Kodierverfahren nutzt.

In digitalen Kommunikationssystemen, wie zum Beispiel einem CDMA (Code Division Multiple Access = Codemultiplex-Vielfachzugriff) System, wandert ein Binärzeichen aufweisender Datenbitstrom, welcher eine von einem Sender gesendete Nachricht darstellt, durch einen Datenkanal und wird von einem Empfänger empfangen. Der Datenbitstrom ist im Allgemeinen aus einer Anzahl von Nachrichtenblocks zusammengesetzt. Falls die Länge eines Nachrichtenblocks nicht fest ist, kann das System als ein Variable-Längen-Kommunikationssystem bezeichnet werden. In einem solchen Variable-Längen-System wird im Allgemeinen eine zusätzliche Längen-Information jedes Nachrichtenblocks für den Empfänger benötigt, um jeden Nachrichtenblock zu identifizieren und die Nachricht aus dem empfangenen Datenbitstrom zu extrahieren.

[1] beschreibt eine neuartige Modifikation einer zyklischen Redundanzprüfung (CRC) zur Bestimmung der Länge von Nachrichten unter Verwendung selektiv geflippter CRC-Bits.

Ferner beschreibt [2] die Besonderheiten des Multiplexens und der Kanalkodierung im Frequenzteilungs-Duplex-Modus des universellen terrestrischen Funkzugriffs (UTRA).

Ein herkömmliches Verfahren eines Variable-Längen-Kommunikationssystems kennzeichnet einen gesonderten Kanal als einen Kontrollkanal zum Übertragen von Längeninformation jedes Nachrichtenblocks. Demnach, wenn der Empfänger sowohl die Längeninformation und den Datenbitstrom empfängt, identifiziert der Empfänger die entsprechenden Nachrichtenblocks basierend auf die Längeninformationen und ent-blockt (”de-blocks”) den Datenbitstrom.

Das herkömmliche Verfahren nutzt im Allgemeinen ebenfalls Bits der zyklischen Redundanzprüfung (ZRP) für Zwecke der Fehlerdetektion. Insbesondere werden eine feste Anzahl von ZRP-Bits an das Ende von jedem Nachrichtenblock angehängt und haben eine vorbestimmte Beziehung zu dem entsprechenden Nachrichtenblock. Der Empfänger empfängt sowohl den Nachrichtenblock und die dem Nachrichtenblock folgenden ZRP-Bits und versucht die Beziehung zwischen ihnen wieder zu errichten. Falls die Beziehung erfüllt ist, wird der Nachrichtenblock als fehlerlos betrachtet. Andernfalls ist ein Fehler während der Übertragung dieses Blocks aufgetreten. Dieses Verfahren wird als nächstes im Einzelnen weiter erklärt.

Als Erstes wird ein ZRP-Generatorpolynom g_l(x) der Ordnung l ausgewählt. Ein üblicher Weg des Auswählens des ZRP-Generatorpolynoms ist, dass g_l(x) ggT(g_l(x), xⁱ) = 1 für jedes einzelne i zwischen 0 und l, einschließlich, erfüllen soll, wobei l und i ganze Zahlen sind, und die Funktion ggT(A(x), B(x)) als der größte gemeinsame Teiler der Polynome A(x) und B(x) definiert ist. Beispiele geeigneter g_l(x) enthalten g₄(x) = x⁴ + x³ + x² + 1 für l = 4, g₇(x) = x⁷ + x⁶ + x⁴ + 1 für l = 7, g₈(x) = x⁸ + x⁷ + x⁴ + x³ + x + 1 für l = 8, und g₁₂(x) = x¹² + x¹¹ + x³ + x² + x + 1 für l = 12. Die Information bezüglich des ZRP-Generatorpolynoms ist sowohl im Sender als auch im Empfänger gespeichert.

Zur Veranschaulichung ist ein binäres Polynom für jeden Binärzeichenstrom wie folgt definiert: falls ein Binärzeichenstrom A t Binärzeichen, a_t-1, a_t-2, ..., a₀, enthält, wobei t eine ganze Zahl ist, dann wird das binäre Polynom von A mit A(x) bezeichnet und es gilt A(x) = a_t-1x^t-1 + a_t-2x^t-2 + ... + a₀. Ebenfalls zur Veranschaulichung gilt ein Binärzeichenstrom A als die ZRP-Bedingung erfüllend, falls A(x) durch g_l(x) teilbar ist. Zwei Binärzeichenströme A und B gelten als die ZRP-Bedingung erfüllend, falls x^sA(x) + B(x) teilbar durch g_l(x) ist, wobei s die Anzahl der im Binärzeichenstrom B enthaltenen Bits ist. Einem Fachmann ist es bekannt, dass wenn zum Beispiel ein Polynom A(x) durch ein anderes Polynom g_l(x) teilbar ist, der Rest von A(x) geteilt durch g_l(x) 0 ist, und es kann gesagt werden, dassg_l(x) A(x) teilt, bezeichnet als g_l(x)|A(x).

Als nächstes wird für einen k Bits von binärer Information, m_k-1, m_k-2, ..., m₀, enthaltenden Nachrichtenblock M ein Paritätsprüfungsbitstrom P, welcher l Paritätsprüfungsbits, oder ZRP-Bits, p_l-1, p_l-2, ..., p₀, enthält, erzeugt, so dass Mund P die ZRP-Bedingung erfüllen, oder g_l(x)|(x^lM(x) + P(x)) gilt. Ein Paritätsprüfungsbitstrom kann auch ein Paritätsblock, ein Paritätsprüfungsblock oder ein ZRP-Block genannt werden. Für jeden Nachrichtenblock M kann bewiesen werden, dass nur ein entsprechender Paritätsprüfungsbitstrom P existiert. Der Beweis wird von einem Fachmann verstanden und ist hierin nicht im Detail diskutiert. Gemäß dem Standard-ZRP-Verfahren kann ein Paritätsprüfungsbitstrom P unter Verwendung von entweder Hardware oder Software erzeugt werden. Beispiele von Hardware-Implementierungen sind in den 1-2 gezeigt, und ein Beispiel einer Software-Implementierung ist in 3 gezeigt. Sowohl 1 als auch 2 nehmen l = 8 und ein ZRP-Generatorpolynom g_l(x) = x⁸ + x⁷ + x⁴ + x³ + x + 1 an.

1 zeigt eine erste Hardware-Implementierung des Erzeugens eines Paritätsprüfungsbitstroms P. Unter Bezugnahme auf 1 wird eine Rückkopplungs-Schieberegister-Schaltung 100 zum Erzeugen eines auf ein ZRP-Generatorpolynom g_l(x) = x⁸ + x⁷ + x⁴ + x³ + x + 1 basierenden Paritätsprüfungsbitstroms P verwendet. Die Schaltung 100 enthält mehrere Verzögerungsschaltungen 102, welche als Flip-Flops verwirklicht sein können. Die Anzahl der Verzögerungsschaltungen 102 ist gleich der Ordnung von g_l(x), d. h. l = 8. Daher gibt es in 1 acht Verzögerungsschaltungen, 1021, 1022, ..., 1028. Mehrere XOR-Gatter 104 sind zwischen den Verzögerungsschaltungen 102 eingefügt. Jedes XOR-Gatter 104 entspricht einem Koeffizienten des ZRP-Generatorpolynoms g_l(x). Wie Beispielsweise in 1 gezeigt ist, zeigt ein XOR-Gatter an der linken Seite der ersten Verzögerungsschaltung 1021, dass der Koeffizient von x⁰ = 1 von g_l(x) gleich 1 ist, das Fehlen eines XOR-Gatters 104 zwischen den Verzögerungsschaltungen 1022 und 1023 zeigt, dass der Koeffizient von x² von g_l(x) gleich 0 ist, und ein XOR-Gatter 1045 zwischen den Verzögerungsschaltungen 1027 und 1028 zeigt, dass der Koeffizient von x⁷ von g_l(x) gleich 1 ist. Ein Taktsignal (nicht gezeigt) schiebt die Registerschaltung 100 jeweils um ein Bit von links nach rechts. Wie in 1 gezeigt ist, ist der Ausgang der Verzögerungsschaltung 1028 zu jedem der XOR-Gatter 1041–1045 rückgekoppelt. Der Paritätsprüfungsdatenstrom wird erzeugt, indem in die linke Seite der Schaltung 100 der Nachrichtenblock M, gefolgt von acht Bits von 0, eingespeist wird. Die Ausgabe der Verzögerungsschaltung 1028 weist dann den Nachrichtenblock M, gefolgt von seinen entsprechenden Paritätsprüfungsbitstrom P, auf.

Eine zweite Hardware-Implementierung des Erzeugens eines Paritätsprüfungsbitstroms ist in 2 gezeigt. In ähnlicher Weise enthält eine Schieberegister-Schaltung 200 mehrere Verzögerungsschaltungen 202, von denen jede durch eine Flip-Flop-Schaltung realisiert sein kann. Mehrere XOR-Gatter 204 sind gemäß des ZRP-Generatorpolynoms g_l(x) zwischen den Verzögerungsschaltungen 202 eingefügt. Im Gegensatz zu 1 ist jedoch ein XOR-Gatter 204 zum rechten Ende der Schaltung 200 anstatt zum linken Ende der Schaltung 200 hinzugefügt, und der Nachrichtenblock M wird in das am weitesten rechts gelegene XOR-Gatter 204 eingegeben. Ein Schalter 206 schaltet den Ausgang der Rückkopplungs-Schieberegister-Schaltung 200 zwischen dem Nachrichtenblock M und dem Ausgang des am weitesten rechts gelegenen XOR-Gatters 204. Die Rückkopplungs-Schieberegister-Schaltung 200 gibt zuerst den Nachrichtenblock M aus und gibt dann die Paritätsbits aus, indem der Schalter 206 zum Ausgang des am weitesten rechts gelegenen XOR-Gatters 204 schaltet.

3 zeigt eine Software-Implementierung des Erzeugens eines Paritätsprüfungsbitstroms P. Anstatt den Paritätsprüfungsbitstrom P Bit für Bit zu erzeugen, wird in der Software-Implementierung eine Nachschlagetabelle verwendet. Die Nachschlagetabelle enthält eine Gesamtliste der ZRP-Bitströme für alle möglichen Nachrichten von einer bestimmten Länge. Wenn zum Beispiel l = 8 ist, enthält die Nachschlagetabelle 2⁸ = 256 Einträge von ZRP-Bitströmen, wobei jeder Bitstrom acht Binärzeichen enthält. Wie in 8 gezeigt ist, wird eine 3 Bytes (24 Bits), Byte 1, Byte 2 und Byte 3, enthaltende Nachricht unter Verwendung der Nachschlagetabelle kodiert. In Schritt 302 wird Byte 1 betrachtet und die Verweistabelle wird nach einem übereinstimmenden Eintrag für Byte 1 durchsucht. In Schritt 304 wird mit dem Ergebnis der Suche und Byte 2 eine XOR-Operation durchgeführt, um einen zwischenzeitlichen ZRP-Bitstrom ZRP2 zu erzeugen. Ein Eintrag, welcher mit ZRP2 übereinstimmt, wird (in Schritt 306) in der Nachschlagetabelle nachgeschlagen und es wird mit dem Ergebnis der Suche und Byte 3 eine XOR-Operation durchgeführt (Schritt 308), um den ZRP-Bitstrom ZRP3 der Nachricht zu erzeugen.

Die obigen drei Implementierungen werden von einem Fachmann leicht verstanden und daher werden die Details davon hierin nicht weiter diskutiert.

Nachdem der Paritätsprüfungsbitstrom P erzeugt wurde, werden die Paritätsprüfungsbits davon an das Ende des Nachrichtenblocks M angefügt, um einen verketteten Bitstrom C, aufweisend k + l Bits, m_k-1, m_k-2, ..., m₀, p_l-1, p_l-2, ..., p₀, zu bilden. Angesichts der obigen Bedingen teilt g_l(x) C(x) = x^lM(x) + P(x).

Für jeden in der Nachricht enthaltenen Nachrichtenblock wird das obige Kodierverfahren wiederholt, um einen entsprechenden verketteten Bitstrom zu erzeugen, und ein Datenbitstrom, welcher die verketteten Bitströme und Längeninformation jedes Nachrichtenblocks enthält, wird dann durch einen Datenkanal bzw. einem Kontrollkanal übertragen.

An der Empfänger-Seite werden sowohl der Datenbitstrom als auch die Längeninformation empfangen. Ein empfangener Nachrichtenblock M' und ein Paritätsprüfungsbitstrom P' werden basierend auf die Längeninformation extrahiert, wobei M' k Bits, m'_k-1, m'_k-2, ..., m'₀, enthält, und P' l Bits, p'_l-1, p'_l-2, ..., p'₀, enthält. Der Empfänger führt dann einen sogenannten ZRP-Test durch, um zu bestimmen, ob M' und P' die ZRP-Bedingung erfüllen. Wenn die Bedingung erfüllt ist, dann wird der Nachrichtenblock als ohne Fehler empfangen betrachtet.

Ein System, welches getrennt vorgesehene Kontrollkanäle zum Übertragen von Längeninformationen verwendet, wie oben diskutiert, kann sehr ineffizient sein, wenn die Datenrate langsam ist. Zum Beispiel, in einem Standard UMTS (”universal mobile telecommunications system) WCDMA (wideband code division multiple access) Modus, im AMR (Adaptive Multi-Rate) 12.2 kbps Modus, kann der Zusatz zum übertragen der Längeninformation so groß wie 3 kbps, oder fast 25% von der gesamten Übertragensrate von 12.2 kbps, sein.

Um den durch die getrennte Übertragung der Längeninformation verschuldeten Zusatz zu reduzieren, wurde ein ZRP-Verfahren (nachstehend ”Standard-ZRP-Verfahren” genannt) vorgeschlagen, welches die ZRP-Bits zur Detektion der Nachrichtenlängen verwendet, anstatt die Längeninformation jedes Nachrichtenblocks durch einen getrennten Kanal zu übertragen. Gemäß dem Standard-ZRP-Verfahren sendet der Sender nur den Datenbitstrom, und der Empfänger empfängt den Datenbitstrom mit keiner Längeninformation. Daher kann der Empfänger die Nachrichtenblocks nicht unmittelbar identifizieren oder die Nachricht extrahieren. Stattdessen wiederholt der Empfänger einen Versuch-und-Irrtum-Schritt, um den empfangenen Datenbitstrom nach einem Paar eines Nachrichtenblocks und eines Paritätsprüfungsstroms, welcher die ZRP-Bedingung erfüllt, zu durchsuchen. Als Erstes rät der Empfänger eine Zahl, beispielsweise k^ , als die Blocklänge, und behandelt die ersten k^ Bits des empfangenen Bitstroms als einen Nachrichtenblock, und die folgenden l Bits als einen Paritätsprüfungsbitstrom. Der Empfänger führt dann den ZRP-Test durch, um zu bestimmen, ob der geratene Nachrichtenblock und der geratene Paritätsprüfungsbitstrom die ZRP-Bedingung erfüllen. Falls das Ergebnis positiv ist, hat der Empfänger erfolgreich einen Nachrichtenblock identifiziert und fährt fort, um den nächsten Nachrichtenblock zu identifizieren. Andernfalls wurde der Nachrichtenblock nicht identifiziert, die geratene Blocklänge k^ wird um 1 erhöht und der ZRP-Test wird wiederholt. Theoretisch wird nach wenigen Versuchen der korrekte Nachrichtenblock identifiziert. Das Standard ZRP-Verfahren hat jedoch ein inhärentes Problem einer wahrscheinlichen Falschdetektion. Unter der Annahme einer rauschfreien Übertragung und einer gleichmäßig verteilten Nachricht ist die Wahrscheinlichkeit einer Falschdetektion für das Standard-ZRP-Verfahren durch Ausdruck (1) gegeben:

Da die Übertragung als rauschfrei angenommen wird, werden alle übertragenen Bits ohne Fehler empfangen. Falls i = k – k^ = 0 ist, wird daher die ZRP-Bedingung erfüllt und ein korrekter Nachrichtenblock ist identifiziert. Es tritt keine Falschdetektion auf, d. h., P_F(0) = 0.

Falls i = k – k^ = 1 ist, enthält der falsch geratene Nachrichtenblock M' k – 1 Bits, m_k-1, m_k-2, ..., m₁, und der geratene Paritätsprüfungsblock P' enthält l Bits, p_l-1, p_l-2, ..., p_l. Der ZRP-Test entscheidet daher, ob g_l(x) C'(x) = x^lM'(x) + P'(x) = m_k-1x^l+k-2 + m_k-2x^l+k-3 + ... + m₁x^l + m₀x^l-1 + p_l-1x^l-2 + p_l-2x^l-3 + ... p_l teilt. Weil ggT(g_l(x), x) = 1 ist, ist ein Entscheiden, ob g_l(x)|C'(x) gilt, äquivalent zum Entscheiden ob g_l(x)|xC'(x) gilt. C'(x) mit C(x) vergleichend, ist xC'(x) = C(x) – p₀. Falls daher p₀ = 0 ist, weil g_l(x)|C(x) gilt, dann gilt g_l(x)|xC'(x) und g_l(x)|C'(x). Der Empfänger hält den falschen Nachrichtenblock M' für den korrekten Nachrichtenblock, und es gibt eine Falschdetektion. Andernfalls, falls p₀ = 1 ist, wird die ZRP-Bedingung nicht erfüllt, und der Empfänger schließt, dass M' nicht der korrekte Nachrichtenblock ist, und es gibt keine Falschdetektion. Für gleichmäßig verteilte Nachrichten ist die Wahrscheinlichkeit für p₀ = 0 gleich ½, und daher die Wahrscheinlichkeit für eine Falschdetektion gleich ½.

In ähnlicher Weise, falls 1 < i ≤ l – 1 ist, enthält der falsch geratene Nachrichtenblock M' k – i Bits, m_k-1, m_k-2, ..., m_i, und der falsch geratene Paritätsblock P' enthält l Bits, m_i-1, m_i-2, ..., m₀, p_l-1, p_l-2, ..., p_i. Der ZRP-Test entscheidet daher, ob g_l(x) C'(x) = x^lM'(x) + P'(x) = m_k-1x^l-1+k-1 + m_k-2x^l-i+k-2 + ... + m₀x^l-i + p_l-1x^l-i-1 + p_l-2x^l-i-2 + ... + p_i teilt. C'(x) mit C(x) vergleichend, ist

Schließlich, falls i ≥ l ist, enthält der geratene Nachrichtenblock M' k – i Bits, m_k-1, m_k-2, ..., m_i, und der geratene ZRP-Bitstrom P' enthält m_i-1, m_i-2, ..., m_i-l. Da es nur einen möglichen ZRP-Bitstrom gibt, welcher M' entspricht, ist die Wahrscheinlichkeit dafür, dass P' die ZRP-Bedingung g_l(x)|(x^lM'(x) + P'(x)) erfüllt, d. h., die Wahrscheinlichkeit für eine Falschdetektion, 2^–l für einen gleichmäßig verteilten Nachrichtenblock.

4 zeigt ein Simulationsergebnis für Wahrscheinlichkeit des Bestehens des ZRP-Test für das Standard-ZRP-Verfahren bei verschieden geratenen Nachrichtenlängen. Die Simulationsbedingung enthält, dass die Ordnung des ZRP-Generatorpolynoms 8 ist und dass die tatsächliche Nachrichtenlänge 15 ist. Indem sich die geschätzte Nachrichtenlänge der tatsächlichen Nachrichtenlänge annähert, d. h., der Längen-Offset i sich an 0 annähert, wächst die Wahrscheinlichkeit des Bestehens des ZRP-Tests exponentiell, wie in 4 gezeigt ist.

Hinsichtlich der großen Wahrscheinlichkeit einer Falschdetektion für ein Standart-ZRP-Verfahren, wurde ein modifiziertes ZRP-Verfahren (”herkömmliche Modifikation”) mit einer reduzierten Wahrscheinlichkeit einer Falschdetektion vorgeschlagen. Gemäß der herkömmlichen Modifikation des ZRP-Verfahrens werden, nachdem der Paritätsprüfungsbitstrom P' erzeugt wurde, die Paritätsprüfungsbits in umgekehrter Reihenfolge an den Nachrichtenblock angefügt, um einen verketteten Bitstrom, m_k-1, m_k-2, m₀, p₀, ..., p_l, p_l-1 zu bilden. 5 zeigt die Simulationsergebnisse für die herkömmliche Modifikation im Vergleich zum Standard-ZRP-Verfahren. Die Bedingungen sind dieselben wie die in 4, d. h., die Ordnung des ZRP-Generatorpolynoms ist 8 und die tatsächliche Nachrichtenlänge ist 15. Wie in 5 gezeigt ist, ist die Wahrscheinlichkeit des Bestehens des ZRP-Tests, d. h., die Wahrscheinlichkeit einer Falschdetektion, für alle Nachrichtenlängen-Offsets i > 0 auf 2^–l reduziert.

Falls der Datenkanal rauscht, werden Fehler während der Übertragung auftreten. Um die sichere Übertragung von Daten zu schützen, kann ein Verfahren, genannt Faltungskodierung, angewendet werden, um die Daten vor deren Übertragung zu kodieren. Auf der Empfänger-Seite wird ein entsprechendes Verfahren angewendet, um die empfangenen Daten zu dekodieren.

Konzeptionell kodiert das Faltungskodierungs-Verfahren die Daten, um redundante Bits von Informationen zu erzeugen, und opfert Übertragungsgeschwindigkeit für eine verbesserte Übertragungsgenauigkeit. Gemäß des Faltungskodierungs-Verfahrens empfängt eine Faltungskodierer Nachrichtenblocks, welche gesendet werden sollen, und erzeugt mittels eines Kodierverfahrens einen Bitstrom, welcher mehrere Teile enthält, jeder einem Nachrichtenblock entsprechend. Jeder Teil kann als ein Faltungs-Codewort bezeichnet werden, oder Codewort. Das Faltungs-Codewort wird dann mittels eines Senders gesendet. Der Faltungskodierer kann zu einem gegebenen Zeitpunkt jeweils t Bits eines Nachrichtenblocks empfangen und n Bits der Ausgabe erzeugen, wobei n im Allgemeinen größer ist als t. Jedes von den n Bits der Ausgabe kann eine Linearkombination der t Bits der Eingabe und eines oder mehrerer vorhergehenden Bits, welche den t Bits der Eingabe vorangehen, sein. Der Faltungskodierer enthält eine Anzahl von Speicherregistern zum Merken solcher vorhergehenden Bits und um die t Bits der Eingabe zu empfangen, und eine Mehrzahl von logischen Gattern, welche an die Speicherregister in einer Weise angeschlossen sind, die konsistent mit einem Kodieralgorithmus zum Erzeugen der n Bits der Ausgabe ist. Eine Speicherordnung des Faltungskodierers ist definiert als die Anzahl der Speicherregister für jedes der t Eingabe-Bits. Ein Faltungskodierer mit der Ordnung j, welcher t Bits der Eingabe empfängt, und n Bits der Ausgabe ausgibt, kann als ein (n, t, j)-Kodierer bezeichnet werden. Offensichtlich hat ein (n, t, j)-Kodierer tj Speicherregister zum Speichern der vorhergehenden Bits und t Speicherregister zum Empfangen des einen Bits der Eingabe. In einem speziellen Fall hat ein (n, 1, j)-Kodierer j Speicherregister zum Speichern der vorhergehenden Bits und ein Speicherregister zum Empfangen des einen Bits der Eingabe. Weil jedes Speicherregister entweder eine 0 oder eine 1 speichert, gibt es 2^j mögliche Zustände von solchen Speicherregistern, d. h., es gibt 2^j mögliche Zustände des Kodierers.

Es wird ein Nachrichtenblock A mit k Bits betrachtet. Auf der Senderseite, vor dem Kodieren des Nachrichtenblocks A, ist ein (n, 1, j) Kodierer in einem Anfangszustand. Nach dem Kodieren des Nachrichtenblocks A ist der Kodierer in einem Endzustand. Offensichtlich gibt es, bei gegebenen Anfangszustand, nur einen entsprechenden Endzustand. Es ist üblich, den Anfangszustand als ein Alles-Null-Zustand zu setzen, in welchem alle Speicherregister, ausgenommen das eine zum Empfangen des einen Bits der Eingabe, ein 0-Bit darin gespeichert haben. Als Ergebnis des Kodierverfahrens ist ein Codewort erzeugt, welches n(k + j) Bits enthält.

An der Empfängerseite kann ein Dekodierer, wie zum Beispiel ein Viterbi-Dekodierer, verwendet werden, um ein empfangenes Codewort, welches n(k + j) Bits enthält, zu dekodieren. Im Allgemeinen kennt der Dekodierer im voraus den Anfangszustand des Kodierers. Für einen k-Bit Nachrichtenblock gibt es 2^k mögliche Codewörter. Der Dekodierer vergleicht diese 2^k mögliche Codewörter mit dem Empfangenen Codewort und findet die beste Übereinstimmung. In einem fehlerfreien System sollte es ein Codewort geben, welches vollständig mit dem empfangenen Codewort übereinstimmt. In einem System mit Rauschen ist es möglich, dass keines von den 2^k möglichen Codewörtern vollständig mit dem empfangenen Codewort übereinstimmt. Ein metrischer Pfad eines möglichen Codeworts ist definiert als die Anzahl der Bits des möglichen Codeworts, welche mit denen des empfangenen Codeworts übereinstimmen. Der Dekodierer versucht, das mögliche Codewort mit dem besten metrische Pfad zu finden. Der Nachrichtenblock, welcher dem Codewort mit dem besten metrische Pfad entspricht, wird als der dekodierte Nachrichtenblock betrachtet. Davon abhängig, welcher Dekodieralgorithmus angewendet wird, können verschiedenen Dekodierer verschiedene Wirkungsgrade haben, den besten metrische Pfad zu finden. Zum Beispiel hat ein Viterbi-Dekodierer, im Vergleich zu einem sequentiellen Dekodierer, im Allgemeinen einen besseren Wirkungsgrad. Der sequentielle Dekodierer und Veterbi-Dekodierer sind einen Fachmann bekannt und hierin nicht beschrieben.

In einem Variable-Längen-System sind die Länge von jedem Nachrichtenblock und die Länge des entsprechenden Codewortes unbekannt. Daher weiß der Faltungskodierer nicht, wann der Kodierprozess zu stoppen ist. Demgemäß können zusätzliche Bits zum Nachrichtenblock eingefügt werden vor dem Faltungs-Kodierprozess für diesen Nachrichtenblock. Es können zum Beispiel, für einen (n, 1, j) Kodierer, j 0-Bits an das Ende von jedem Nachrichtenblock angefügt werden. Demzufolge kehrt der Kodierer am Ende des Kodierprozesses zu dem Alles-Null-Zustand zurück. In dem Dekodierprozess rät der Dekodierer eine Länge k^ des Nachrichtenblocks und bestimmt, ob das eine von den

Ein Nachrichtenblock kann kodiert werden sowohl unter Verwendung des ZRP-Verfahrens (entweder das Standard-ZRP-Verfahren oder die herkömmliche Modifikation davon) als auch des Faltungsverfahrens. Zum Beispiel kann, nach dem oben diskutierten ZRP-Kodier-Verfahren, ein verketteter Bitstrom C, welcher einen Nachrichtenblock M, welcher k Bits, m_k-1, m_k-2, ..., m₀, enthält, und ein entsprechender Paritätsprüfungsbitstrom P, welcher l Bits, p_l-1, p_l-2, ..., p₀, enthält, zu einem (n, 1, j)-Faltungskodierer gesendet werden, welcher ein Codewort, welches n(k + l) Bits enthält, erzeugt.

Ein Dekodierer auf der Empfängerseite dekodiert das empfangene Codewort ebenfalls unter Verwendung sowohl des Faltungsverfahrens als auch des ZRP-Verfahrens. Insbesondere dekodiert ein Viterbi-Dekodierer faltungsmäßig das empfangene Codewort und findet einen geratenen verketteten Bitstrom C', welcher k^ + l Bits enthält. Dann wird der geratene verkettete Bitstrom C' zu einem ZRP-Dekodierer gesendet, wo der ZRP-Test durchgeführt wird. Falls der ZRP-Test bestanden wird, wird der geratene verkettete Bitstrom C' als den korrekten Nachrichtenblock M enthaltend betrachtet. Andernfalls wird k^ um 1 erhöht und das obige Verfahren wiederholt.

Die vorliegende Erfindung betrifft ein modifiziertes ZRP-Verfahren zur Längendetektion einer Nachricht mit Faltungs-Schutz.

Gemäß der Erfindung wird ein erstes Verfahren für ein Variable-Längen-Kommunikationssystem bereitgestellt, wobei das System einen Empfänger enthält.

Das erste Verfahren weist auf Speichern von Information eines Zyklischen-Redundanzprüfungs(ZRP)-Generatorpolynoms g_l(x), wobei l eine ganze Zahl und die Ordnung von g_l(x) ist, und von Information eines Flip-Polynoms f_l(x) der Ordnung l – 1 in den Empfänger, Empfangen eines mehrere Codewörter enthaltenden Datenbitstroms, wobei die Codewörter mit einem Faltungskodierer der Speicherordnung j kodiert werden, wobei j eine ganze Zahl ist, und wobei jedes Codewort einem verketteten Bitstrom entspricht, welcher aus einem Nachrichtenblock und einem entsprechenden geflippten Paritätsprüfungsbitstrom besteht, und Dekodieren eines ersten Nachrichtenblocks in dem Datenbitstrom.

Das Dekodieren des ersten Nachrichtenblocks enthält (a) Raten einer Blocklänge k^ und Erzeugen eines verketteten Bitstroms C' aus den ersten n(k^ + l + j) Bits des empfangenen Datenbitstroms, wobei der verkettete Bitstrom C' einen aus k^ Bits,

Das Raten der Nachrichtenblock-Länge k^ weist auf Finden eines von

Gemäß der Erfindung wird ferner ein zweites Verfahren für ein Variable-Längen-Kommunikationssystem bereitgestellt, wobei das System einen Sender und einen Empfänger enthält, der Sender einen Faltungskodierer der Speicherordnung j enthält, wobei j eine ganze Zahl ist, und wobei Nachrichten in Nachrichtenblocks variabler Länge geteilt werden.

Das zweite Verfahren weist auf Bereitstellen eines Zyklischen-Redundanzprüfungs(ZRP)-Generatorpolynoms g_l(x), wobei l eine ganze Zahl und die Ordnung von g_l(x) ist, Bereitstellen eines binären Flip-Polynoms f_l(x) der Ordnung l – 1, Speichern von Information eines ZRP-Generatorpolynoms g_l(x) und von Information eines Flip-Polynoms f_l(x) in sowohl den Sender als auch den Empfänger und Kodieren einer zu sendenden Nachricht mittels Kodieren jedes Nachrichtenblocks M davon.

Das Kodieren von M enthält Erzeugen eines Paritätsprüfungsbitstroms P unter Verwendung des ZRP-Generatorpolynoms g_l(x), Flippen des Paritätsprüfungsbitstroms P unter Verwendung des Flip-Polynoms f_l(x), um einen geflippten Paritätsprüfungsbitstrom P zu erzeugen, Anhängen des geflippten Paritätsprüfungsbitstroms P an das Ende des Nachrichtenblocks M, um einen verketteten Bitstrom C zu schaffen, und faltungsmäßiges Kodieren des verketteten Bitstroms C, um mit dem Faltungskodierer ein Codewort D zu erzeugen.

Das zweite Verfahren weist ferner auf Senden des Codeworts D des Nachrichtenblocks M der zu sendenden Nachricht, Empfangen eines mehrere Codewörter enthaltenden Datenbitstroms, wobei jedes Codewort einem aus einem Nachrichtenblock und einem entsprechenden geflippten Paritätsprüfungsbitstrom bestehenden verketteten Bitstrom entspricht, und Dekodieren des Datenbitstroms.

Das Dekodieren des Datenbitstroms enthält Dekodieren eines ersten Nachrichtenblocks in dem Datenbitstrom, welches enthält (a) Raten einer Nachrichtenblock-Länge k^ und Erzeugen eines verketteten Bitstroms C' aus den ersten n(k^ + l + j) Bits des empfangenen Datenbitstroms, wobei der verkettete Bitstrom C enthält einen geratenen Nachrichtenblock M' mit k^ Bits, m'_k-1, m'_k-2, ..., m'₀, wobei k^ eine ganze Zahl ist, und einen geratenen geflippten Bitstrom P', welcher l Bits enthält, (b) Erzeugen eines Paritätsprüfungsbitstrom P^ unter Verwendung eines ZRP-Generatorpolynoms g_l(x), (c) Flippen des Paritätsprüfungsbitstroms P^ unter Verwendung des Flippolynoms f_l(x), um einen geflippten Paritätsprüfungsbitstrom P^ ' zu erzeugen, (d) falls P' und P^ ' verschieden sind, Erhöhen von k^ um 1 und Wiederholen von (a)–(c), und (e) Entfernen der ersten n(k^ + l + j) Bits aus dem Datenbitstrom, wenn P' = P^ ' ist.

Das zweite Verfahren weist ferner auf Wiederholen des Kodierens des ersten Nachrichtenblocks in dem Datenbitstrom, nachdem die ersten n(k^ + l + j) Bits entfernt wurden.

Das Raten der Nachrichtenblock-Länge k^ weist auf Finden eines von

Das dritte Verfahren weist auf Speichern von Information eines ZRP-Generatorpolynoms und von Information eines Flip-Polynoms in den Empfänger, Empfangen eines Datenbitstrom, welcher mehrere Codewörter enthält, wobei jedes Codewort einem aus einem Nachrichtenblock einer Nachricht und einem entsprechenden geflippten Paritätsprüfungsbitstrom bestehenden verketteten Bitstrom entspricht, und Dekodieren eines ersten Nachrichtenblocks der Nachricht in dem Datenbitstrom.

Das Dekodieren des ersten Nachrichtenblocks enthält (a) Raten einer Nachrichtenblock-Länge des Ersten der Nachrichtenblocks und Erzeugen eines verketteten Bitstroms aus dem empfangenen Datenbitstrom, wobei der verkettete Datenbitstrom einen geratenen geflippten Paritätsprüfungsbitstrom enthält, (b) Erzeugen eines Paritätsprüfungsbitstroms aus dem verketteten Bitstrom unter Verwendung des ZRP-Generatorpolynoms, (c) Flippen des Paritätsprüfungsbitstroms unter Verwendung des Flip-Polynoms, um einen geflippten Paritätsprüfungsbitstrom zu erzeugen, (d) falls der geflippte Paritätsprüfungsbitstrom und der geratene geflippte Paritätsprüfungsbitstrom verschieden sind, Erhöhen der geratenen Nachrichtenblock-Länge um 1 und Wiederholen von (a)–(c), und (e) falls der geflippte Paritätsprüfungsbitstrom und der geratene geflippte Paritätsprüfungsbitstrom gleich sind, Entfernen des dem ersten der Nachrichtenblocks der Nachricht entsprechenden Codeworts aus dem Datenbitstrom.

Das Raten der Nachrichtenblock-Länge des Ersten der Nachrichtenblocks weist auf Finden eines aus allen möglichen Codewörtern, welches einem Alles-Null-Zustand entspricht, falls ein metrischer Pfad des einen Codeworts eine vorbestimmte Bedingung erfüllt, Fortfahren mit dem Erzeugen des Paritätsprüfungsbitstroms, und falls ein metrischer Pfad des einen Codeworts nicht die vorbestimmte Bedingung erfüllt, Erhöhen der geratenen Nachrichtenblock-Länge um 1 und Zurückkehren zum Finden eines Besten von allen möglichen Codewörtern.

Die vorbestimmte Bedingung ist definiert als

Gemäß der Erfindung wird ferner ein viertes Verfahren für ein Variable-Längen-Kommunikationssystem bereitgestellt, wobei das System einen Sender und einen Empfänger enthält, wobei die Nachrichten in Nachrichtenblocks variabler Länge geteilt werden.

Das vierte Verfahren weist auf Bereitstellen eines Zyklischen-Redundanzprüfungs(ZRP)-Generatorpolynoms, Bereitstellen eines binären Flip-Polynoms, Speichern von Information eines ZRP-Generatorpolynoms und von Information eines Flip-Polynoms in sowohl den Sender als auch den Empfänger, Kodieren einer zu sendenden Nachricht mittels Kodieren jedes Nachrichtenblocks davon.

Das Kodieren jedes Nachrichtenblocks enthält Erzeugen eines Paritätsprüfungsbitstroms unter Verwendung des ZRP-Generatorpolynoms, Flippen des Paritätsprüfungsbitstroms unter Verwendung des Flip-Polynoms, um einen geflippten Paritätsprüfungsbitstrom zu erzeugen, Anhängen des geflippten Paritätsprüfungsbitstroms an das Ende des entsprechenden Nachrichtenblocks, um einen verketteten Bitstrom zu schaffen, und faltungsmäßiges Kodieren des verketteten Bitstroms, um ein Codewort zu erzeugen, und Senden des Codeworts des Nachrichtenblocks der zu sendenden Nachricht.

Das vierte Verfahren weist ferner auf Empfangen eines Datenbitstroms, welcher einer empfangenen Nachricht entspricht, welche mehrere Nachrichtenblocks enthält, wobei der Datenbitstrom mehrere Codewörter enthält, wobei jedes Codewort einem entsprechenden der Nachrichtenblocks der empfangenen Nachricht und einem entsprechenden geflippten Paritätsprüfungsbitstrom bestehenden verketteten Bitstrom entspricht, und Dekodieren des Datenbitstroms durch Dekodieren jedes Nachrichtenblocks der empfangenen Nachricht.

Das Dekodieren jedes der Nachrichtenblock enthält (a) Raten einer Nachrichtenblock-Länge und Erzeugen eines verketteten Bitstroms aus dem empfangenen Datenbitstrom, wobei der verkettete Bitstrom einen geratenen Nachrichtenblock und einen geratenen geflippten Bitstrom enthält, (b) Erzeugen eines Paritätsprüfungsbitstrom unter Verwendung des ZRP-Generatorpolynoms, (c) Flippen des Paritätsprüfungsbitstroms unter Verwendung des Flippolynoms, um einen geflippten Paritätsprüfungsbitstrom zu erzeugen, (d) falls der geflippte Paritätsprüfungsbitstrom und der geratene geflippte Paritätsprüfungsbitstrom unterschiedlich sind, Erhöhen der geratenen Nachrichtenblock-Länge um 1 und Wiederholen von (a)–(c), und (e) falls der geflippte Paritätsprüfungsbitstrom und der geratene geflippte Paritätsprüfungsbitstrom gleich sind, Entfernen des Codeworts des entsprechenden Nachrichtenblocks aus dem Datenbitstrom.

Das Raten der Nachrichtenblock-Länge weist auf Finden eines aus allen möglichen Codewörtern, welches einem Alles-Null-Zustand entspricht, falls der metrische Pfad des einen Codeworts eine vorbestimmte Bedingung erfüllt, Fortfahren mit dem Erzeugen des Paritätsprüfungsbitstroms, und falls der metrische Pfad des einen Codewort nicht die vorbestimmte Bedingung erfüllt, Erhöhen der geratenen Nachrichtenblock-Länge um 1 und Zurückkehren zum Finden eines Besten aus allen möglichen Codewörtern.

Die vorbestimmte Bedingung ist definiert als

Zusätzliche Eigenschaften und Vorteile der Erfindung werden teilweise in der folgenden Beschreibung dargelegt, und werden teilweise aus der Beschreibung offensichtlich, oder können beim Benutzen der Erfindung gelernt werden. Die Eigenschaften und Vorteile der Erfindung werden realisiert und erlangt anhand der Elemente und der Kombinationen, welche insbesondere in den angefügten Ansprüchen aufgezeigt sind.

Es ist zu verstehen, dass sowohl die vorhergehende insgesamte Beschreibung und die folgende ausführliche Beschreibung beispielhaft und erläuternd sind und nicht einschränkend für die Erfindung sind, wie sie beansprucht ist.

Die beigefügten Zeichnungen, welche einbezogen sind und einen Teil dieser Spezifikationen bilden, zeigen Ausführungsbeispiele der Erfindung und dienen, zusammen mit der Beschreibung, zum Erklären der Ziele, der Vorteile und der Prinzipien der Erfindung.

In den Zeichnungen zeigen

1 eine erste Hardware-Implementierung des Erzeugens eines Paritätsprüfungsbitstroms gemäß des Standard-ZRP-Verfahrens,

2 eine zweite Hardware-Implementation des Erzeugens eines Paritätsprüfungsbitstroms gemäß des Standard-ZRP-Verfahrens,

3 eine Software-Implementation des Erzeugens eine Paritätsprüfungsbitstroms gemäß des Standard-ZRP-Verfahrens,

4 Simulationsergebnisse des Standard-ZRP-Verfahrens,

5 Simulationsergebnisse einer herkömmlichen Modifikation des ZRP-Verfahrens,

6 eine erste Hardware-Implementierung des Erzeugens eines geflippten Paritätsprüfungsbitstroms konsistent mit Ausführungsbeispielen der Erfindung,

7 eine zweite Hardware-Implementation des Erzeugens eines geflippten Paritätsprüfungsbitstroms konsistent mit Ausführungsbeispielen der Erfindung,

8 eine Software-Implementation des Erzeugens eines geflippten Paritätsprüfungsbitstroms konsistent mit Ausführungsbeispielen der Erfindung,

9 ein Kommunikationssystem, welches das mit der Erfindung konsistente ZRP-Kodierverfahren nutzt,

10A die Wahrscheinlichkeit des Bestehens sowohl des Metrischen-Pfad-Tests als auch des ZRP-Tests bezüglich eines Nachrichtenlängen-Offsets für das mit der Erfindung konsistente ZRP-Verfahren, wobei ein Flip-Polynom anngenommen wird, welches eine mit der Erfindung konsistente Bedingungen erfüllt,

10B die Wahrscheinlichkeit des Bestehens sowohl des Metrischen-Pfad-Tests als auch des ZRP-Tests bezüglich eines Nachrichtenlängen-Offsets für das mit der Erfindung konsistente ZRP-Verfahren, wobei ein Flip-Polynom angenommen wird, welches nicht eine mit der Erfindung konsistente Bedingungen erfüllt,

11A–11C vergleicht die Leistungsfähigkeit des mit der Erfindung konsistenten ZRP-Verfahrens und des herkömmlich modifizierten Verfahrens.

12A zeigt Simulationsergebnisse der Wahrscheinlichkeit des Versagens, einen korrekten Nachrichtenblock zu detektieren, für das mit der Erfindung konsistente ZRP-Verfahren und das herkömmlich modifizierte Verfahren, und

12B zeigt Simulationsergebnisse der Wahrscheinlichkeit einer Falschdetektion für das mit der Erfindung konsistente Flip-Bit-ZRP-Verfahren und das herkömmlich modifizierte Verfahren.

Es wird nun im Detail Bezug genommen auf die bevorzugten Ausführungsbeispiele der Erfindung, von denen Beispiele in den beigefügten Zeichnungen gezeigt sind. Wenn immer es möglich ist, wird durchwegs dasselbe Bezugszeichen in den Zeichnungen benutzt, um auf gleichen oder ähnliche Teile Bezug zu nehmen.

Die mit der Erfindung konsistenten Ausführungsbeispiele stellen ein modifiziertes ZRP-Verfahren zur Längendetektion einer Nachricht mit Faltungs-Schutz bereit.

Insbesondere sind die mit der Erfindung konsistenten Verfahren zum Verwenden in einem Variable-Längen-Kommunikationssystem geeignet, welches einen Sender und einen Empfänger enthält. Ein zu sendender Nachrichtenblock kann eine Anzahl von Nachrichtenblocks mit nicht festen Längen enthalten. Jeder Nachrichtenblock wird sowohl mit dem ZRP-Verfahren als auch dem faltungsmäßigem Verfahren kodiert und mittels eines Senders gesendet. Wenn der Empfänger die kodierten Nachrichtenblocks empfängt, wird jeder Nachrichtenblock dekodiert und die Nachricht wird extrahiert. Da das Verfahren des Kodierens und Dekodierens für alle Nachrichtenblocks dasselbe ist, wird nur ein Nachrichtenblock M, welcher k Bits, m_k-1, m_k-2, ..., m_k-l, m₀, enthält, in der folgenden Beschreibung betrachtet.

Zur Veranschaulichung wird ein binäres Polynom für jeden Binärzeichenstrom wie folgt definiert: falls ein Binärzeichenstrom A t Binärzeichen, a_t-1, a_t-2, ..., a₀, enthält, wobei t eine ganze Zahl ist, wird das binäre Polynom von A mit A(x) bezeichnet und es ist A(x) = a_t-1x^t-1 + a_t-2x^t-2 + ... + a₀. Es wird nachstehend angenommen, solange nichts anderes angedeutet wird, dass, wenn zwei binäre Polynome addiert werden, die Koeffizienten der zwei Polynome, welche demselben Exponenten entsprechen, gemäß einer Modulo-2-Additionsoperation addiert werden. Eine Modulo-2-Addition ist definiert als eine binäre Addition ohne Übertrag, zum Beispiel 0 + 1 = 1 und 1 + 1 = 0. Falls der Bitstrom B s Binärzeichen, b_s-1, b_s-2, ..., b₀, enthält, dann ist daher, unter der Annahme, dass s < t ist, A(x) + B(x) = a_t-1x^t-1 + a_t-2x^t-2 + ... + a_sx^s + (a_s-1 + b_s-1)x^s-1 + (a_s-2 + b_s-2)x^s-2 + ... + (a₀ + b₀), wobei (a_i + b_i) das Ergebnis der Modulo-2-Addition von a_i und b_i, für 0 ≤ i ≤ s – 1, ist. Es wird nachstehend also angenommen, solange nichts anderes angedeutet ist, dass, wenn zwei Binärzeichenströme addiert werden, die entsprechenden Bits von zwei Bitströmen gemäß einer Modulo-2-Additionsoperation addiert werden. Einem Fachmann ist es bekannt, dass, gemäß der Definition einer Modulo-2-Addition, a + b + b = a, A + B + B = A und A(x) + B(x) + B(x) = A(x) ist, wobei a und b Binärzeichen und A und B Binärzeichenströme sind.

Ein mit der Erfindung konsistentes Verfahren startet, indem zwei binäre Polynome, ein ZRP-Generatorpolynom (nachstehend ”ZRP-Polynom”) g_l(x), und ein Flip-Polynom f_l(x), ausgewählt werden. Das ZRP-Polynom g_l(x) hat die Ordnung l, und das Flip-Polynom f_l(x) hat die Ordnung l – 1, wobei l eine ganze Zahl ist. In einem Aspekt ist ggT(g_l(x), x') = 1 für jedes und alle 0 ≤ i ≤ l, wobei i eine ganze Zahl ist, und ggT(g_l(x), x') der größte gemeinsame Teiler von g_l(x) und xⁱ ist. Beispiele für passende g_l(x) enthalten g₄(x) = x⁴ + x³ + x² + x + 1 für l = 4, g₇(x) = x⁷ + x⁶ + x⁴ + 1 für l = 7, g₈(x) = x⁸ + x⁷ + x⁴ + x³ + x + 1 für l = 8 und g₁₂(x) = x¹² + x¹¹ + x³ + x² + x + 1 für l = 12. Das Flip-Polynom kann durch f₁(x) = f_l-1x^l-1 + f_l-2x^l-2 + ... + f₀ ausgedrückt werden, wobei f_i ∊ {0, 1} für 0 ≤ i ≤ l. Die Koeffizienten des Flip-Polynoms f_l(x), nämlich f_l-1, f_l-2, ..., f₀, können als Flip-Bits bezeichnet werden. Die Informationen des ZRP-Polynoms g_l(x) und des Flip-Polynoms f_l(x) sind sowohl im Sender als auch im Empfänger gespeichert.

Zur Veranschaulichung gilt ein Binärzeichenstrom A als die ZRP-Bedingung erfüllend, falls g_l(x) A(x) teilt oder g_l(x)|A(x) gilt, und zwei Binärzeichenströme A und B gelten als die ZRP-Bedingung erfüllend, falls g_l(x) x^sA(x) + B(x) teilt, oder g_l(x)|(x^sA(x) + B(x)) gilt, wobei s die Anzahl der in dem Binärzeichenstrom B enthaltenen Bits ist.

Auf der Senderseite erzeugt ein Kodierprozess als Erstes einen Paritätsprüfungsbitstrom P, welcher l Paritätsprüfungsbits, oder ZRP-Bits, p_l-1, p_l-2, ..., p₀ enthält, so dass M und P die ZRP-Bedingung erfüllen, oder g_l(x)|(x^lM(x) + P(x)) gilt, wobei M(x) = m_k-1x^k-1 + m_k-2x^k-2 + ... + m₀ und P(x) = p_l-1x^l-1 + p_l-2x^l-2 + ... + p₀ ist. Ein Paritätsprüfungsbitstrom P kann auch als ein Paritätsprüfungsblock, ein Paritätsblock oder ein ZRP-Block bezeichnet werden. Ein Fachmann wird nun schätzen, dass jeder Nachrichtenblock M nur einem einzigen eindeutigen Paritätsprüfungsbitstrom P entspricht.

Der Kodierprozess, flippt denn die Paritätsprüfungsbits gemäß dem Flip-Polynom f_l(x), oder speziell, mittels Durchführen einer Modulo-2-Addition von jedem Bit in dem Paritätsprüfungsbitstrom P und einem entsprechendem Flip-Bit. Der resultierende geflippte Paritätsprüfungsbitstrom P enthält l geflippte Paritätsprüfungsbits:

Dann werden die geflippten Paritätsprüfungsbits an das Ende des Nachrichtenblocks angefügt, um einen verketteten Bitstrom C zu bilden, welcher k + l Bits,

Konsistent mit der Erfindung kann der geflippte Paritätsprüfungsbitstrom durch Hardware oder Software erzeugt werden. 6 zeigt eine erste Hardware-Impemantierung zum Erzeugen des geflippten Paritätsprüfungsbits gemäß einem mit der Erfindung konsistenten Ausführungsbeispiel. Bezugnehmend auf 6 wird eine Rückkopplungs-Schieberegister-Schaltung 600 verwendet, um einen geflippten Paritätsprüfungsbitstrom P , basierend auf das ZRP-Generatorpolynom g_l(x) = x⁸ + x⁷ + x⁴ + x³ + x + 1, zu erzeugen. Die Schaltung 600 enthält mehrere Verzögerungsschaltungen 602, welche als Flip-Flops verwirklicht sein können. Die Anzahl der Verzögerungsschaltungen 602 ist gleich der Ordnung von g_l(x), d. h., l = 8. Daher gibt es in 6 acht Verzögerungsschaltungen, 6021, 6022, ..., 6028. Verschiedene XOR-Gatter 604 sind zwischen den Verzögerungsschaltungen 602 eingefügt. Jedes XOR-Gatter 604 entspricht einem Koeffizienten des ZRP-Generatorpolynoms g_l(x). Wie in 6 gezeigt ist, zeigt beispielsweise ein XOR-Gatter 604, an der linken Seite der ersten Verzögerungsschaltung 6021, dass der Koeffizient von x⁰ = 1 von g_l(x) gleich 1 ist, die Abwesenheit eines XOR-Gatters 604 zwischen den Verzögerungsschaltungen 6022 und 6023 zeigt, dass der Koeffizient von x² von g_l(x) gleich 0 ist, und ein XOR-Gatter 6045 zwischen den Verzögerungsschaltungen 6027 und 6028 zeigt, dass der Koeffizient von x⁷ von g_l(x) gleich 1 ist. Ein XOR-Gatter 6046 ist ebenfalls gekoppelt, um mit der Ausgabe der Verzögerungsschaltung 6028 und dem Nachrichtenblock M, gefolgt von Flip-Bits, f_l-1, f_l-2, ..., f₀, eine XOR-Operation durchzuführen. Gemäß des Ausdrucks für f_l(x), welcher vorher beschrieben wurde, und wie in 6 gezeigt ist, ist f₈(x) = x⁷ + 1. Daher sind 10000001 die entsprechenden 8 Flip-Bits. Ein Taktsignal (nicht gezeigt) schiebt die Registerschaltung 600 jeweils ein Bit von links nach rechts. Wie in 6 gezeigt ist, ist das die Rückkopplung des Ausgangs des XOR-Gatters 6046 zu jedem der XOR-Gatter 6041–6045. Ein Schalter 606 schaltet den Ausgang der Rückkopplungs-Schieberegister-Schaltung 600 zwischen den Nachrichtenblock M und dem Ausgang des XOR-Gatters 6046. Eine Rückkopplungs-Schieberegister-Schaltung 600 gibt zuerst den Nachrichtenblock M aus und gibt dann die geflippten Paritätsbits aus, indem der Schalter 606 zum Ausgang des XOR-Gatters 6046 geschaltet wird.

Eine zweite Hardware-Implementierung zum Erzeugen eines geflippten Paritätsprüfungsbitstroms P , konsistent mit einem Ausführungsbeispiel der Erfindung, ist in 7 gezeigt. Wie in 7 gezeigt ist, enthält eine Rückkopplungs-Schieberegister-Schaltung 700 mehrere Verzögerungsschaltungen 702, von denen jede als eine Flip-Flop-Schaltung verwirklicht sein kann. Mehrere XOR-Gatter 704 sind zwischen den Verzögerungsschaltungen 702 gemäß des ZRP-Generatorpolynoms g_l(x) eingefügt. Zwei XOR-Gatter 7041 und 7042 sind zum linken bzw. rechten Ende der Schaltung 700 hinzugefügt. Der Nachrichtenblock M wird in das XOR-Gatter 7041 eingegeben, und die am weitesten rechts gelegene Verzögerungsschaltung 702 gibt den Nachrichtenblock M und seinen entsprechenden Paritätsprüfungsbitstrom P aus. Dann flippt das XOR-Gatter 7042 den Paritätsprüfungsbitstrom P unter Verwendung der Flip-Bits, f_l-1, f_l-2, ..., f₀, um den geflippten Paritätsprüfungsbitstrom P zu erzeugen. Es wird in 7 also vorausgesetzt, dass das Flip-Polynom f₈(x) = x⁷ +1 ist, und daher 10000001 die Flip-Bits sind.

8 zeigt diagrammatisch eine Software-Implementierung des Erzeugens eines geflippten Paritätsprüfungsbitstroms P , wobei in der Software-Implementierung eine Nachschlage-Tabelle benutzt wird. Die Nachschlage-Tabelle enthält eine Gesamtliste der ZRP-Bitströme für alle möglichen Nachrichten mit einer bestimmten Länge. Wenn zum Beispiel l = 8 ist, enthält die Nachschlage-Tabelle 2⁸ = 256 Einträge von ZRP-Bitströmen, wobei jeder Bitstrom acht Binärzeichen enthält. Wie in 8 gezeigt ist, wird eine Nachricht, welche 3 Bytes (24 Bits), Byte 1, Byte 2 und Byte 3, enthält, unter Verwendung der Nachschlage-Tabelle kodiert. In Schritt 802 wird Byte 1 betrachtet, und die Nachschlage-Tabelle wird nach einem Übereinstimmenden Eintrag für Byte 1 durchsucht. Bei Schritt 804 wird am Ergebnis der Suche und Byte 2 eine XOR-Operation durchgeführt, um einen zwischenzeitlichen ZRP-Bitstrom ZRP2 zu erzeugen. Es wird ein Eintrag, welcher mit ZRP2 übereinstimmt, in der Nachschlage-Tabelle nachgeschlagen (Schritt 806) und mit Byte 3 mittels einer XOR-Operation verknüpft (Schritt 808), um den ZRP-Bitstrom ZRP3. der Nachricht zu erzeugen. Ferner wird ZRP3 unter Verwendung der Flip-Bits geflippt. Es wird in 8 ebenfalls vorausgesetzt, dass das Flip-Polynom f₈(x) = x⁷ + 1 ist und daher 10000001 die Flip-Bits sind.

Nach dem obigen ZRP-Kodierprozess wird ferner der verkettete Bitstrom C mittels eines (n, t, j)-Faltungskodierers kodiert, wobei n eine ganze Zahl ist, welche angibt, wie viele Bits jeweils durch den Kodierer ausgegeben werden, t eine ganze Zahl ist, welche die Anzahl der Eingaben anzeigt, welche der Kodierer empfängt und j die Speicherordnung des Kodierers ist. Um die Darstellung zu vereinfachen, wird t = 1 vorausgesetzt. Zuerst wird er verkettete Bitstrom C mit j Null-Bits angehängt, um einen 0-Beendeten Bitstrom B zu schaffen, welcher k + l + j Bits,

Der 0-Beendete Bitstrom B passiert dann den (n, 1, j)-Faltungskodierer, um ein Faltungs-Codewort D zu erzeugen, welches n(k + l + j) Bits enthält. Der Faltungs-Kodierprozess ist für einen Fachmann bekannt und ist hier nicht ausführlich beschrieben.

Der gleiche Kodierprozess wie oben wird durchgeführt, um ein Faltungs-Codewort für alle anderen Nachrichtenblocks der Nachricht zu erzeugen, und es wird ein Datenbitstrom, welcher die resultierenden Codewörter enthält, gesendet.

Wenn der Empfänger einen Datenbitstrom empfängt, welcher mindestens ein Faltungs-Codewort enthält, wird ein Dekodierprozess durchgeführt, um die erste Nachricht in dem Datenbitstrom zu identifizieren. Nachdem ein erster Nachrichtenblock identifiziert ist, wird das entsprechende Codewort aus dem Datenbitstrom entfernt, und der Empfänger fährt fort, den ersten Nachrichtenblock in dem resultierenden Datenbitstrom zu identifizieren. Wenn der Empfänger daher startet, den Nachrichtenblock M zu dekodieren, enthält der Datenbitstrom das Faltungscodewort D, welches dem Nachrichtenblock M entspricht, gefolgt von dem entsprechenden Faltungs-Codewort des nächsten Nachrichtenblocks.

Der Dekodierprozess enthält einen Faltungs-Dekodierprozess und einen ZRP-Dekodierprozess. Zuerst wird ein Nachrichtenblock M' mit einer Länge k^ geraten und der Dekodierer dekodiert faltungsmäßig die ersten n(k^ + l + j) Bits in dem empfangenen Datenbitstrom. In einem Aspekt wird k^ derart gewählt, dass es kleiner ist als die Länge k des Nachrichtenblocks M. Der Dekodierer bestimmt, ob das eine der

In dem ZRP-Dekodierprozess wird zuerst ein Paritätsprüfungsbitstrom P^ , welcher l Paritätsprüfungsbits, p^_l-1, p^_l-2, ..., p^₀ enthält, für den geratenen Nachrichtenblock M' generiert, so dass g_l(x)|(x^lM'(x) + P^(x)) gilt. Als Zweites wird unter Verwendung des Flip-Polynoms f_l(x) der Paritätsprüfungsbitstrom P^ geflippt, um einen geflippten Paritätsprüfungsbitstrom P^ ' zu erzeugen, welcher l geflippte Paritätsprüfungsbits, p^ '_l-1 = p^ '_l-1 + f_l-1,

Eine Falschdetektion tritt auf, wenn die ersten n(k^ + l + j) Bits sowohl den Metrischen-Pfad-Test als auch den ZRP-Test bestehen, obwohl k^ nicht die korrekte Länge des Nachrichtenblocks M ist. In der folgenden Beschreibung wird vorausgesetzt, dass der geratene Nachrichtenblock M' einem verketteten Bitstrom C', welcher k^ + l Bits enthält, einen 0-Beendeten Bitstrom B', welcher k^ + l + j Bits enthält, und einem Codewort D', welches die ersten n(k^ + l + j) Bits enthält, entspricht.

Zuerst muss, wie oben diskutiert, um den Metrischen-Pfad-Test in einem fehlerfreien Kanal zu bestehen, 1) D' den besten metrische Pfad unter diesen

Als Zweites muss, damit der mutmaßliche verkettete Bitstrom C' den ZRP-Test besteht, g_l(x)|(C'(x) + f_l(x)) gelten.

Indem ein geeignetes Flip-Poynom f_l(x) gewählt wird, kann das ZRP-Verfahren der Erfindung eine geringe Wahrscheinlichkeit einer Falschdetektion haben. In einem Aspekt wird das Flip-Polynom f_l(x) derart gewählt, dass gilt

Unter der Bedingung (2), und in der Annahme sowohl einer gleichmäßig verteilten Nachricht als auch einer fehlerfreien Übertragung, ist die Wahrscheinlichkeit des Bestehens sowohl des Metrischen-Pfad-Tests als auch des ZRP-Tests für D' durch Ausdruck (3) gegeben:

Falls i = 0 ist, enthält der Nachrichtenblock M' k Bits, m_k-1, m_k-2, ..., m₀, und der entsprechende geflippte Paritätsprüfungsblock P' enthält l Bits,

Falls 0 < i ≤ j ist, enthält M' k^ Bits, m_k-1, m_k-2, ..., m_i, P' enthält l Bits,

Falls j < i ≤ l + j – 1 ist, enthält M' k^ Bits, m_k-1, ..., m_i, P' enthält l Bits,

Daher gilt

In Hinblick auf das Obige ist die Wahrscheinlichkeit für eine Falschdetektion gleich Null, wenn 0 < i ≤ l + j – 1 ist.

Falls i ≥ l + m ist, dann enthält der geratene Nachrichtenblock M' gleich k – i Bits, m_k-1, m_k-2, ..., m_i, der geratene geflippte Paritätsprüfungsblock P' enthält m_i-1, m_i-2, ..., m_i-l, und B' enthält M' und P' , gefolgt von j Bits, m_i-l-1, m_i-l-2, ..., m_i-l-j. Um den Metrischen-Pfad-Test zu bestehen, müssen die letzten j Bits des Bitstroms B' alle Null sein, d. h., m_i-l-1, m_i-l-2, ..., m_i-l-j, sind alle Null. Weil es ferner nur einen einzigen Paritätsprüfungsblock gibt, welcher einem bestimmten Nachrichtenblock M' entspricht, gibt es nur einen möglichen geflippten Paritätsprüfungsblock P' , welcher dem Nachrichtenblock M' entspricht. Daher ist die Wahrscheinlichkeit, dass m_i-1, m_i-2, ..., m_i-l dem geflippten Paritätsprüfungsblock P' , welcher M' und m_i-l-1, m_i-l-2, ..., m_i-l-j entspricht, zusammensetzt, und dass m_i-l-1, m_i-l-2, ..., m_i-l-j alles Nullen sind, unter der Annahme, dass der Nachrichtenblock M gleichmäßig verteilt ist, 2^–(l+1)

9 zeigt ein Kommunikationssystem 900, welches das mit der Erfindung konsistente Flip-Bit-ZRP-Verfahren nutzt. Das System 900 enthält einen Sender 902 und einen Empfänger 904. Der Sender 902 enthält einen Flip-Bit-ZRP-Kodierer 906 und einen Faltungskodierer 908. Der Empfänger 904 enthält einen Faltungskodierer 910 und einen Flip-Bit-ZRP-Dekodierer 912. Nachrichtenblocks werden sequentiell kodiert mittels des Flip-Bit-ZRP-Kodierers 906 und Faltungskodierers 908, mittels eines Senders 902 gesendet, passieren einen Datenkanal 914 und werden sequentiell dekodiert mittels eines Faltungsdekodierers 910 und eines Flip-Bit-ZRP-Dekodierers 912.

Es wurden Computersimulationen durchgeführt und die Simulationsergebnisse sind in den 10A–10B und 11A–11C gezeigt.

10A zeigt die Wahrscheinlichkeit des Bestehens sowohl des Metrischen-Pfad-Tests als auch des ZRP-Tests bezüglich des Nachrichtenlängen-Offsets für das mit der Erfindung konsistente ZRP-Verfahren, unter der Annahme einer anfänglichen Signal-zu-Rauschen-Rate (”signal-to-noise-ratio”) (SNR) von 2.0 dB, 4.0 dB und 6.0 dB. Es wird in 10A angenommen, dass ein (2, 1, 8)-Faltungskodierer verwendet wird, die Ordnung des ZRP-Generatorpolynoms 8 ist, g₈(x) = x⁸ + x⁷ + x⁴ + x³ + x + 1, f₈(x) = x⁴ + x und die tatsächliche Nachrichtenlänge 30 ist. f₈(x) = x⁴ + x erfüllt die Bedingung (1). Wie in 10A gezeigt ist, wenn die SNR hoch ist, wie zum Beispiel 6.0 dB, tritt keine Falschdetektion auf, wenn der Nachrichtenlängen-Offset kleiner ist als l + j = 16. Sogar mit einer armen SNR, wie zum Beispiel 2.0 dB oder 4.0 dB, ist die Wahrscheinlichkeit einer Falschdetektion, wenn der Nachrichtenlängen-Offset kleiner ist als 16, wesentlich geringer als 2^–(l+j) = 2^–16.

10B zeigt den Effekt, wenn das Flip-Polynom die Bedingung (1) nicht erfüllt. 10B ist das Simulationsergebnis, welches auf denselben Annahmen basiert wie 10A, mit der Ausnahme, dass f₈(x) = x⁷ + 1, welches nicht die Bedingung (1) erfüllt, das Flip-Polynom ist. Infolgedessen ist die Wahrscheinlichkeit einer Falschdetektion viel größer.

Die 11A–11C vergleichen die Leistungsfähigkeit des mit der Erfindung konsistenten ZRP-Verfahrens und des herkömmlich modifizierten Verfahrens, wobei die Kreise das mit der Erfindung konsistente Flip-Bit-ZRP-Verfahren darstellen, und die Kreuz-Symbole stellen das herkömmlich modifizierte Verfahren dar. Es wird in den 11A–11C angenommen, dass ein (2, 1, 8)-Faltungskodierer verwendet wird, die Ordnung des ZRP-Generatorpolynoms 8 ist, g₈(x) = x⁸ + x⁷ + x⁴ + x³ + x + 1, f₈(x) = x⁴ + x, und die tatsächliche Nachrichtenlänge 30 ist. 11A zeigt den Vergleich, wenn die SNR 2.0 dB ist. 11B zeigt den Vergleich, wenn die SNR 4.0 ist. 11C zeigt den Vergleich, wenn die SNR 6.0 ist. Wie in den 11A–11C gezeigt ist, hat das mit der Erfindung konsistente ZRP-Verfahren eine bessere Leistungsfähigkeit als das herkömmlich modifizierte Verfahren, wenn der Nachrichtenlängen-Offset kleiner ist als l + j.

Wie oben diskutiert wurde, wenn ein Nachrichtenblock M' geraten wird, bestimmt der Faltungsdekodierer, ob D', welches die ersten n(k^ + l + j) Bits des empfangenen Datenbitstroms enthält, den Metrischen-Pfad-Test besteht, was erfordert 1) dass D' den besten metrische Pfad unter diesen

Um die Entspannung des Metrischen-Pfad-Tests zu quantisieren, wird ein relativer metrische Pfad d als

Es wird einem Fachmann ersichtlich sein, dass in dem offenbarten Verfahren verschiedenen Modifikationen und Variationen vorgenommen werden können, ohne den Rahmen oder die Lehre der Erfindung zu verlassen. Es werden dem Fachmann andere Ausführungsbeispiele der Erfindung ersichtlich aus der Betrachtung der Spezifikationen und der Anwendung der hierin offenbarten Erfindung. Es ist beabsichtigt, dass die Spezifikationen und Beispiele lediglich als beispielhaft betrachtet werden, wobei der wahre Rahmen und die Lehre der Erfindung durch die folgenden Ansprüche angegeben ist.

In diesem Dokument sind folgende Veröffentlichungen zitiert:

• [1] SHIEH, S.-L.; CHEN, P.-N.; HAN, Y. S.: A Novel Modification of Cyclic Redundancy Check for Message Length Detection. In: International Symposium an Information Theory and its Applications; Oktober 2004. URL: http://shannon.cm.nctu.edu.tw/html/paper/Shieh.pdf (28.1.2009)
• [2] 3GPP [Hrsg.]: 3^rd Generation Partnership Project; Technical Specification Group Radio Access Network; Multiplexing and channel coding (FDD); Technical Specification; März 2003. 3GPP TS 25.212 V3.9.0 Release 1999. URL: http://www.3gpp.org (28.1.2009)