DE69327683T2

DE69327683T2 - Erweitertes fehlergeschütztes Kommunikationssystem

Info

Publication number: DE69327683T2
Application number: DE69327683T
Authority: DE
Inventors: Constant Paul Marie Jozef Baggen
Original assignee: Koninklijke Philips Electronics NV
Current assignee: Koninklijke Philips NV
Priority date: 1992-05-19
Filing date: 1993-05-11
Publication date: 2000-07-27
Anticipated expiration: 2013-05-12
Also published as: JPH0661872A; JP3283097B2; US5539755A; DE69327683D1; ES2144000T3; KR930024334A; KR100294436B1

Description

Die Erfindung bezieht sich auf das Gebiet der Kommunikation, bei der ein erweitertes, gemäß einem digitalen Codierstandard codiertes Kommunikationssignal verwendet wird, das Daten enthält, die von einem Blockcode zum Fehlerschutz abgedeckt werden. Es sind zahlreiche Systeme bekannt, in denen ein derartiges erweitertes Kommunikationssignal eingesetzt wird, z. B. bei den Standards der Compact Disc für Hi-Fi- Audioanlagen, und ihrer erweiterten Version, der CD-ROM, die einen noch größeren Fehlerschutz für empfindliche Daten bietet. Gegenwärtig werden auch Fernsehsignale entsprechend einem Format auf Bit-Basis genormt. Ein derartiger Standard entsteht oft aus intensiverem Kontakt zwischen zahlreichen Herstellern, Regierungen, Behörden und anderen. Neben Standards für derartige Unterhaltungskommunikationssysteme sind von Rechts wegen oder tatsächlich auch professionelle Kommunikationsstandards entstanden. Im allgemeinen beinhaltet das Format Benutzerbits und Steuerbits, dies ist jedoch keine Voraussetzung. Die Bezeichnung "erweitert" zeigt an, dass das System die Übertragung von mehr Informationen als dem Minimum berücksichtigt, wodurch eine zusätzliche physische, logische oder fiktive Kanalkapazität geschaffen wird. "Physisch" bedeutet zusätzliche Daten, so dass dem Benutzer eine höhere Datenrate zur Verfügung steht. "Logisch" bedeutet, dass zusätzliche Daten übertragen werden, die ihre Bedeutung den Hauptdaten entnehmen, z. B. eine Zeitangabe, die dem Benutzer zugänglich gemacht oder von ihm genutzt werden kann, um einen einfacheren direkten Zugriff zu ermöglichen, wenn die Daten in einem Speicher gespeichert sind. "Fiktiv" bedeutet, daß die Funktionalität der zusätzlichen Daten für den Benutzer transparent ist, z. B. wenn das System dadurch eine bessere Funktionalität erhält. Es existieren zahlreiche weitere Möglichkeiten.
Der Dateninhalt der Benutzerbits ist nicht vorhersehbar, da ihre vorgegebene Mindestmenge gegeben ist und folglich ihr Vorhandensein als gegeben angesehen wird.
Die Erweiterungsbits werden häufig auf Systemebene dazu verwendet, auf der Empfängerseite gewisse allgemeine Eigenschaften der Signalorganisation zu signalisieren. Derartige Eigenschaften können sich ohne Einschränkung in der folgenden Darlegung auf das Codierformat der zugehörigen Benutzerinformationen, auf zusätzliche Benutzerinformationen, die nach Belieben zu den Hauptbenutzerinformationen hinzugefügt werden können, auf Rahmennumerierung oder Zeitangaben oder auf Informationen beziehen, die selbst auf die geeigneten Steuerinformationen verweisen. Häufig bleiben nun beim ersten Einstellen eines neuen Standards für das Kommunikationssignal, siehe oben, einige der Steuerbits nicht definiert, sondern werden für eine mögliche Definition zu einem späteren Zeitpunkt in Reserve gehalten. Es hat sich außerdem herausgestellt, dass ein Schutz der Steuerbits oder anderer Erweiterungsbits gegen Burstfehler bzw. Zufallsfehler erforderlich ist. Fehlerschutz-Blockcodes sind an sich wohlbekannt. Es gibt nun für den Schutz der Erweiterungsbits zahlreiche verschiedene Möglichkeiten, da gewisse Erweiterungsbits gemäß eines Standardisierungs- oder Zuordnungsprotokolls definiert wurden, während andere (noch) nicht definiert wurden und infolgedessen von der Steuerungsebene als Leer- oder Ersatzbits betrachtet werden können. Eine erste Möglichkeit besteht darin, die noch nicht definierten Bits gleich Null zu setzen und das Fehlerkorrekturschema so auszulegen, dass es sowohl definierte als auch nicht definierte Bits abdeckt. Der Erfinder hat jedoch erkannt, daß dies eine Vergeudung der Übertragungs- und Fehlerschutzkapazität des Kanals bedeutet. Ein weiterer Aspekt besteht darin, eine Strategie einzusetzen, bei der ein variabler fehlerkorrigierender Code (error correcting code, EEC) angewendet wird, um die bekannten Schwankungen der Kanalqualität zu bewältigen: der Decoder müsste entscheiden können, welcher Fehlerschutzgrad anzuwenden ist.
Der vorliegenden Erfindung liegt unter anderem die Aufgabe zugrunde, ein einheitliches Schutzformat für die tatsächlich definierten Steuerbits zu schaffen, das einen höheren Schutzgrad bietet und gleichzeitig Raum für später zu definierende Bits, die ebenfalls einen bestimmten Fehlerschutzgrad haben würden, zurückhält, wodurch dann ein Teil des Fehlerschutzes von vorher definierten Bits aktiv bleiben würde.
Gemäß einem ihrer Aspekte schafft die Erfindung ein Decodierverfahren, wie in ANSPRUCH 1 dargelegt. Bei der späteren Verwendung von zu späteren Teilen der Folge gehörigen Redundanzbits für andere Zwecke bleibt der durch frühere Teile der Folge gebotene Fehlerschutz aktiv. Zwar kann n willkürliche ganzzahlige Werte haben, mindestens 2 ist jedoch vorteilhaft: dies bedeutet, daß zwei aufeinanderfolgende Schutzgrade aufgegeben werden können. Das Format ist des Weiteren unabhängig und erfordert daher keine externe Angabe zum tatsächlich vorliegenden Schutzgrad: eine externe Angabe könnte selbst fehlerhaft sein. Erfindungsgemäß würde die Struktur eines Codeblockes selbst anzeigen, ob sie einen höheren oder alternativ einen niedrigeren Fehlerschutzgrad aufweist. Der Code, wie oben beschrieben, ist kein verketteter Code: bei der Decodierung eines verketteten Codes wird jede Decodierebene vollständig ausgewertet, bevor die Decodierung der nächsten Ebene vorgenommen werden kann. Auf dieser nächsten Ebene wird die Redundanz bezüglich der vorherigen Ebene vollständig unberücksichtigt gelassen. Gemäß der vorliegenden Erfindung gehören die erforderlichen Codes zu einer einzigen mathematischen Klasse, und es muss auf keinerlei Informationen außerhalb des Codeblocks zugegriffen werden, um den anzuwendenden Schutzgrad zu ermitteln.
In den Zusammenfassungen der japanischen Patentschriften, Band 11, Nr. 152 (E-507), vom 16. Mai 1987, und JP A-61 280 524, vom 18. Dezember 1987, wird die Verwendung eines in Faktoren zerlegbaren erzeugenden Polynoms in Verbindung mit Bemühungen zur Reduzierung des für die Fehlerkorrektur erforderlichen Festspeicherplatzes beschrieben. In dieser Referenz wird nicht die Verwendung eines fehlergeschützten Blockes mit einheitlichem Format beschrieben, in dem die Funktion gewisser Bitpositionen nach Daten oder Redundanz ausgewählt werden kann. Im Widerspruch dazu steht, dass zusätzliche Redundanz scheinbar genutzt wird, wenn sich der geringere Platz als unzureichend erweist.
Es ist vorteilhaft, wenn die genannten Daten Steuerdaten sind, die den Benutzerdaten in dem genannten Signal, das nicht durch den genannten Code abgedeckt ist, untergeordnet sind. Häufig ist die Benutzerdatenmenge größer als die Steuerdatenmenge. Die Benutzerdaten können digital, z. B. Bildschirmtext, oder analog, z. B. ein herkömmliches Fernsehsignal, sein. Die erfindungsgemäße Codierung kann kleine oder große Datenmengen schützen.
Es ist vorteilhaft, wenn der genannte Code ein BCH-Code ist. Für BCH- Codes gibt es eine nachgewiesene Theorie bezüglich ihrer Erzeugung und Decodierung. Der Code kann binär sein oder auf Mehrbit-Symbolen basieren, wie bei Reed-Solomon- Codes. Die Auswahl kann auf der Grundlage eines Fehlermodells erfolgen. Für Zufallsbitfehler sind binäre Codes vorzuziehen.
Es ist vorteilhaft, wenn die Faktoren g&sub0;(x), ... gn(x) kleinste Polynome sind, die einen Mindestgrad zum Erreichen eines bestimmten Abstands haben, wie er von dem niedrigsten Grad des Polynoms vorgegeben wird, das die gewünschte Potenz von a enthält.
Dadurch ergibt sich außerdem eine geringe Redundanz. Manchmal kann die Decodierung bei Polynomen einfacher sein, die nicht kleinste Polynome sind.
Es ist vorteilhaft, wenn jedes erzeugende Polynom Gj(x), wobei j ≥ 2, eine Anzahl von Nullen mit gleichem Abstand von Gn(x) definiert. Die Nullen können aufeinanderfolgende Nullen sein, oder ihr Abstand kann gleichmäßig zwei, drei oder mehr Positionen betragen. Dadurch bleibt der Index der kleinsten Polynome offen. Eine derartige einheitliche Struktur ist einfacher zu decodieren und für die Codiertheorie besser zugänglich, und ihre effektive Schützbarkeit ist leichter vorherzusagen.
Es ist vorteilhaft, wenn das erzeugende Polynom bei kleinsten binären BCH- Codes
Gn(x) = m&sub1;(x) * m&sub3;(x) ... * m2n+1(x)
und jedes Polynom G2j+1(x) es ermöglichen, einen zusätzlichen Fehler über eine derartige Fehlerkorrektur, wie sie durch G2j-1(x) durchführbar wird, zu korrigieren, vorausgesetzt, dass m2j+1(x) eine zusätzliche Null in das erzeugende Polynom G2j+1(x) einfügt. Es hat sich herausgestellt, dass es vorteilhaft ist, wenn die stufenweise Erhöhung des Schutzgrades die Erhöhung des Grades der Korrigierbarkeit bedeutet. Der erste Term kann sich auf einen CRC-Code beziehen. Dieser ist wohlbekannt und leicht auszuführen. Es ist anzumerken, daß in diesem speziellen erzeugenden Polynom die von m&sub9;(x) abgedeckte Null auch von m&sub3;(x) abgedeckt wird, so dass Ersteres den Abstand des Codes nicht erhöhen würde. Das gleiche gilt für geradzahlige kleinste Polynome.
Es ist vorteilhaft, wenn der Code auf einem erzeugenden Polynom
Gn(x) = (x - 1)k * Gn(x)
basiert, wobei k ≤ n + 1 ist und jeder der genannten k-Faktoren (x - 1) zusammen mit einem einzigen der genannten Faktoren codiert wird, beginnend mit dem Ersten (n = 0). Durch die Kombination des Faktors m&sub1;(x) mit einem Faktor (x - 1) nimmt der Abstand dieser gepaarten Faktoren zu. Durch die Kombination weiterer größerer Faktoren mit dem gleichen Faktor (x - 1) nimmt der Abstand an sich nicht zu, jedoch wird die Fähigkeit zur Korrektur von Burstfehlern in einem binären Code noch verbessert.
Im Besonderen kann das Signal ein Funksignal für das digitale Fernsehen sein. Eine bevorzugte Zeile ist die erste Hälfte Nr. 23 im PALPLUS-Format zur Positionierung des betreffenden erweiterten Kommunikationssignal für die Unterhaltungselektronik. Es ist anzumerken, dass die Frage der Standardisierung, wie sie oben angesprochen wurde, insbesondere in Systemen der Unterhaltungselektronik ein wichtiger Punkt ist: Eine Ver besserung der Leistungsfähigkeit des Systems sollte nicht sofort den Einsatz neuer Benutzerterminals erforderlich machen.
Die Erfindung bezieht sich des Weiteren auf ein Verfahren zur Codierung eines erweiterten Kommunikationssignals wie oben definiert.
Die Erfindung bezieht sich außerdem auf einen Decoder zur Decodierung eines derartigen erweiterten Kommunikationssignals, der insbesondere so ausgelegt ist, dass er entweder ein OK-Signal bei Beendigung eines Korrekturvorgangs oder ein Signal "unausführbar" erzeugt, gesteuert entweder von einem erkannten, für den betreffenden Decoder nicht korrigierbaren Fehler oder von einem Fehler, der außerhalb des korrigierbaren Bereichs des empfangenen Codes liegt. Diese Einstellung ist unter zahlreichen Aspekten vorteilhaft. Der Decoder signalisiert richtig, dass er das Fehlermuster nicht bearbeiten kann. Das Problem kann dann darin liegen, dass entweder der Abstand des Codes oder die Kapazität des Decoders nicht ausreicht. Natürlich können beide Fälle gleichzeitig auftreten. Der Decoder braucht nicht im Voraus der Abstand eines empfangenen Codes zu kennen und kann in der Tat vermischte Codes empfangen, die unterschiedliche Abstände aufweisen. Zahlreiche weitere vorteilhafte Aspekte sind in den abhängigen Patentansprüchen dargelegt.

KURZE BESCHREIBUNG DER FIGUREN

Die Erfindung wird nachfolgend ausführlicher in Bezug auf ein uneingeschränktes Ausführungsbeispiel erläutert, das im Hinblick auf die Figuren und Tabellen beschrieben wird. Es zeigen:
Tabelle 1 kleinste Polynome;
Tabelle 2 verschachtelte BCH-Codes mit der Ausgangsblocklänge 127;
Tabelle 3 die Wahrscheinlichkeit von nicht erkannten Fehlern bei Burstfehlern;
Tabelle 4 die Bewertung von Codewörtern mit kleinster Gewichtung;
Tabelle 5 die Fehlerwahrscheinlichkeit bei Zufallsfehlern;
Fig. 1 Konfigurationen verschiedener Codewörter;
Fig. 2 ein Gesamtblockdiagramm des Systems;
Fig. 3 einen Ablaufplan der Decodieroperationen.

ABHANDLUNG ÜBER DIE CODIERASPEKTE DER ERFINDUNG

Zahlreiche Fehlerschutzcodes, wie z. B. CRCs (zyklische Redundanzprüfungen, cyclic redundancy checks), Hamming-Codes und auch zahlreiche Mehrfachfehler- Korrekturcodes, können als BCH-Codes beschrieben werden. Im Allgemeinen ist die Erfindung jedoch auf die Codes anwendbar, die ein in Faktoren zerlegbares Polynom enthalten. Wie immer erfolgt die effektive Auswahl aus der Skala der Codes auf der Basis von Argumenten bezüglich Fehlermodell, Blockgröße, erforderlicher Grad des Fehlerschutzes und leichte Decodierung. Im restlichen Teil ist nun ein Codewort, (eine Folge von Bits) der Längen als ein Polynom in der unbestimmten Menge x dargestellt, d. h.
(c&sub0;, c&sub1;, ....., cn-1) c&sub0;x + c&sub1;x + ... +cn-1xn-1 = cixi : = c(x)
wobei ci {0,1}. Somit dient die Potenz i von xi als Positionsanzeiger des Bits c&sub1;. In gleicher Weise wird ein empfangenes Wort (das eventuell Fehler enthält) als r(x) dargestellt. Das nachfolgend besprochene spezielle Beispiel betrifft binäre BCH-Codes. Die Erfindung ist jedoch ebenso auf nichtbinäre Codes, z. B. Reed-Solomon-Codes, und sogar auf Codes anwendbar, die keine BCH-Codes sind.
BCH-Codes sind zyklische Codes und dadurch gekennzeichnet, dass jedes Codewort c(x) ein Mehrfaches eines erzeugenden Polynoms g(x) ist. Diese Tatsache wird für die Codierung und Decodierung von BCH-Codes genutzt. Beispielsweise wird bei der Überprüfung eines CRC das empfangene Wort r(x) einem Rückkopplungs-Schieberegister zugeführt, was mathematisch gesehen der Division (im Galois-Feld GF(2)) des empfangenen Wortes durch das Polynom entspricht, das durch die Rückkopplungsverbindungen des Rückkopplungs-Schieberegisters dargestellt wird. Ist der Rest Null (CRC=OK), so ist das empfangene Wort ein Mehrfaches von g(x):
r(x) mod g(x) = 0,
d. h. das empfangene Wort gehört zu dem Code. Ist der Rest nicht Null, wurde ein Fehler erkannt. In Abhängigkeit von den Eigenschaften des Codes können Fehler durch die Durchführung mathematischer Operationen an diesem Rest korrigiert werden. Die Eigenschaften der Fehlererkennung und -korrektur werden durch die Faktoren des erzeugenden Polynoms bestimmt, d. h. in unserem Fall
g(x) = m&sub0;(x)m&sub1;(x)m&sub3;(x) ...,
wobei jeder Faktor mi(x) selbst ein Polynom ist. Die Faktoren selbst können minimal sein und somit die geringste Redundanz aufweisen, die mit dem geplanten Abstand des Codes vergleichbar ist. Die Faktoren können unzerlegbar oder selbst ein Produkt unzerlegbarer Polynome sein. Ein spezieller Faktor kann nun m&sub0;(x) = (x + 1) sein, was einer einfachen Gesamtparitätsprüfung entspricht, wenn c(x) durch (x + 1) teilbar ist. Das Polynom g(x) kann mehrere Faktoren haben, wobei die Fehlerkorrekturfähigkeit im allgemeinen zunimmt, wenn mehrere Faktoren enthalten sind.
Ein beispielhafter CRC-8 wird definiert durch:
g(x) = g&sub4;(x) = (x + 1)m&sub1;(x),
wobei ml(x) ein Primitivpolynom siebter Ordnung über GF(2) ist. Somit entspricht die Ordnung von g&sub4;(x) acht und der Anzahl der Paritätsbits. Die BCH-Theorie zeigt, dass der Mindestabstand d dieses Codes C&sub4; gleich vier ist, vorausgesetzt, dass die Codewortlänge 127 nicht überschreitet. Der Abstand des erzeugten Codes wird durch die tiefstehende Zahl von C und die tiefstehende Zahl seines erzeugenden Polynoms g angegeben. Der durch g&sub4;(x) erzeugte Code C&sub4; erkennt jegliches Fehlermuster mit einer Gewichtung kleiner gleich drei. Er kann alternativ einen einzelnen Fehler korrigieren und gleichzeitig alle doppelten Fehler erkennen.
Wird m&sub3;(x) siebter Ordnung zu g&sub4;(x) addiert, erhält man einen durch
g&sub6;(x) = m&sub3;(x)g&sub4;(x)
erzeugten Code C&sub6;, der ein Teilcode des durch g&sub4;(x) erzeugten Codes ist, d. h. die zu C&sub6; gehörenden Codewörter sind eine Teilgruppe der zu C&sub4; gehörenden Codewörter. Die Fehlerkorrekturfähigkeit erhöht sich auf Zwei-Bit-Fehlerkorrektur oder Fünf-Bit-Fehlererkennung, wieder vorausgesetzt, dass die Codewortlänge 127 nicht überschreitet. Die Addition von m&sub3;(x) zum erzeugenden Polynom bedeutet, dass sieben weitere Paritäten gespeichert werden müssen, d. h. C&sub6; hat 15 Paritätsbits.
Eine alternative Möglichkeit ist
g'&sub6;(x) = (x + 1)m&sub3;(x)g&sub4;(x),
wobei 16 Paritätsbits benötigt werden und zwei zusammenfallende Nullen bei x = -1 auftreten. Es ist anzumerken, dass für einen durch ein Feld der Kennlinie 2 definierter BCH-Code die Faktoren (x - 1) und (x + 1) identisch sind. In gleicher Weise können die Codes C&sub8; und C&sub1;&sub0; konstruiert werden, erzeugt durch
g&sub8;(x) = m&sub5;(x)g&sub6;(x) (1)
g&sub1;&sub0;(x) = m&sub7;(X)g&sub8;(x), (2)
die 22 bzw. 29 Paritätsbits enthalten. Die Beziehungen zwischen den verschachtelten Codes ergeben sich aus
C&sub4; C&sub6; C&sub8; C&sub1;&sub0;
Im Allgemeinen kann ein durch gd(x) erzeugter Code Cd t korrigieren und gleichzeitig jegliche Anzahl von e (e ≥ t) Fehlern erkennen, vorausgesetzt, dass
t + e < d.
Es ist anzumerken, dass der Saldo zwischen t und e in einer tatsächlichen Situation von den erforderlichen Wahrscheinlichkeiten der Erkennung und falschen Korrektur abhängig ist. Unter Verwendung der Gewichtungsverteilung der beteiligten Codes können diese berechnet werden.
In dieser Hinsicht zeigt Fig. 1 das Format von 40-Bit-Codewörtern, von denen das erste gemäß C&sub4; gebildet ist, bis zum letzten, das gemäß C&sub1;&sub0; gebildet ist. Fig. 1A zeigt nun das 40-Bit-Wort, das aus 32 Datenbits D und 8 Paritätsbits 20 eines CRC- Prüfcodes besteht, dessen Fehlerschutzfähigkeit weiter oben beschrieben wurde. Die nächste Fig. 1B zeigt den Code C&sub6;, der 7 zusätzliche Paritätsbits 22 und 24 Datenbits D enthält. Teil 28 gibt die Paritätsbits des Codes C&sub4; wieder, die in Figur B auch zur Erhöhung des Fehlerschutzgrades verwendet werden. Ein einzelnes Bit 30 kann für zahlreiche Zielsetzungen eingesetzt werden. Erstens kann es Daten beinhalten, die bei diesem Grad fehlergeschützt sind. Der Übergang zum nächsthöheren Schutzgrad kann zu einer Verschiebung von 8 Bits an der Grenze zwischen Daten und Parität führen, was die Berechnung erleichtert. Bei diesem höheren Grad wäre Bit 30 dann ein Leerbit. Eine weitere Lösung besteht in einer Verschiebung der Grenze um sieben Bits, wodurch so viele Daten wie möglich verfügbar bleiben, die Berechnungen in einem 8-Bit-Prozessor jedoch erschwert werden. Eine dritte Lösung besteht darin, einen weiteren Faktor (x + 1) zu dem erzeugenden Polynom zu addieren. Dadurch vergrößert sich der Abstand des Codes nicht (doppelte Nutzung desselben Faktorpolynoms), die Korrektur- und Erkennungsfähigkeit in Bezug auf Burstfehler wird jedoch verbessert. Fig. 1C zeigt das Format eines C&sub8;-Codewortes, dessen Daten in 16 Bits enthalten sind und das zusätzlich 7 Paritätsbits enthält. Fig. 1D zeigt das Format eines C&sub1;&sub0;-Codewortes. Durch Nutzung der drei durch kleine Kreuze markierten Bits würde die höchste Anzahl verfügbarer Daten auf 11 Bits bei dem höchsten Schutzgrad erhöht, was jedoch ziemlich ungleichmäßige Verarbeitungsanforderungen nach sich zieht. Natürlich kann die verschachtelte Organisation gemäß der vorliegenden Erfindung in anderen modu laren Schritten erfolgen, wobei die Verhältniszahl vorzugsweise eine Potenz von 2 ist. Das 40-Bit-Codewortformat ist natürlich nur eine von vielen Möglichkeiten.

BESCHREIBUNG DER HARDWARE

Fig. 2 stellt ein Gesamtblockdiagramm des Systems dar. Block 60 liefert die Benutzerdaten. Für das Fernsehen kann er beispielsweise das Bild selbst, zahlreiche Synchronisierungssignale und zusätzliche Daten, z. B. Videotext, enthalten. In Block 62 können zahlreiche spezielle Daten, z. B. Steuerdaten, über den Eingang 64 hinzugefügt werden. Es ist machbar, dass entweder diese speziellen Daten oder alle Daten gemäß den Lehren der vorliegenden Erfindung geschützt werden. Es können gleichzeitig mehrere verschiedene Grade des Fehlerschutzes gemäß der vorliegenden Erfindung vorliegen. In Block 66 wird der tatsächliche Fehlerschutz geschaffen, z. B. durch Matrixmultiplikation oder ein anderes Verfahren. In Block 68 kann jegliche verbleibende Operation für die Übertragung durchgeführt werden, beispielsweise die Umwandlung in Kanalbits und die allgemeine Modulation mit Trägerfrequenzen und ähnliches. Nach der Übertragung 70 werden in Block 72 die übertragenen Daten erneut durch Demodulation erkannt. Block 74 erkennt die Teile der Daten, die fehlergeschützt sind, und führt den Fehlerschutz durch, wie nachfolgend beschrieben wird. In Block 76 werden die Steuerdaten vom Hauptstrom gemäß Pfeil 78 getrennt. In Block 80 werden die Benutzerdaten für den Benutzer darstellbar gemacht, beispielsweise durch Anzeige, Hardcopy oder auf andere Weise.
Sowohl auf der Codier- als auch auf der Decodierseite können alle Operationen mit handelsübliche Hardware ausgeführt werden. Auf der Decodierseite kann dies in geeigneter Weise programmierte Standard-Hardware sein, zum Beispiel ein 8-Bit- Microcontroller. Für die Massenfertigung kann speziell ausgelegte Hardware verwendet werden.

BESCHREIBUNG DES DECODIERVORGANGS

Ein besonderer Vorteil dieser Gruppe verschachtelter Codes liegt darin, dass ein Code Ci durch einen Decoder aller Codes Cj, j ≤ i, bis zum Abstand von Cj decodiert werden kann. Wenn beispielsweise der tatsächliche übertragene Code durch g&sub6;(x) erzeugt wird, kann immer noch der CRC-8 überprüft werden, da ein Vielfaches von g&sub6;(x) mit Sicherheit ein Vielfaches von g&sub4;(x) ist. Das Konzept der verschachtelten Codes ermöglicht eine erneute Definition der Bits und Codes zu einem späteren Zeitpunkt, ohne dass Proble me mit der Abwärts-Kompatibilität entstehen. Es wird angenommen, dass ursprünglich, wenn nur ein paar Informationsbits definiert wurden, beispielsweise der Code Cm verwendet wird. Wenn zu einem späteren Zeitpunkt weitere Informationsbits erforderlich sind und sich die Kanalbedingungen als günstig erweisen, kann der übertragene Code von C&sub1;&sub0; in C&sub8; geändert werden, und es können damit sieben oder acht Informationsbits mehr gewonnen werden, natürlich mit einem geringeren Fehlerschutz. Zu einem noch späteren Zeitpunkt kann noch einmal von C&sub8; zu C&sub6; und von C&sub6; zu C&sub4; gewechselt werden, wodurch jedesmal sieben oder acht Informationsbits hinzu gewonnen werden. Mit C&sub4; ist der CRC-8 erreicht und kann die Anzahl der Paritäten nicht weiter verringert werden, ohne die Zuverlässigkeit stark zu gefährden. Somit kann der CRC-8 für alle Codes eingesetzt werden.
Die tatsächliche Wahl des Decoders auf der Empfängerseite kann durch die Kostenfrage mitbestimmt werden; in der Tat ist häufig eine unabhängige Auswahl möglich, die als Beispiel hier gegeben wird. Man könnte sich beispielsweise dafür entscheiden, nur den CRC-8 zu überprüfen, obwohl Code C&sub1;&sub0; übertragen wird. Oder es könnte ein Decoder konstruiert werden, der höchstens einen einzigen Fehler korrigiert, während C&sub1;&sub0; übertragen wird.
Tabelle 1 enthält eine Liste der für den Aufbau des Codes erforderlichen kleinsten Polynome. Tabelle 2 enthält eine Liste der verschachtelten Codes, in der für jeden Code die Anzahl der Paritätssymbole r, der Abstand d und das erzeugenden Polynom des Codes aufgeführt sind. Das erzeugende Polynom ergibt sich aus den Potenzen von x, die in g(x) vorliegen, d. h.
x&sup8; + x&sup7; + x&sup5; + x&sup4; + x + 1 8,7,5,4,1,0
Da der Empfänger den tatsächlichen Abstand des Codes nicht kennt, muß eine Decodiermethode definiert werden. Die Decodiermethode ergibt fast die gleiche annehmbare Wahrscheinlichkeit nicht erkannter Fehler wie bei Verwendung des CRC-8, jedoch mit einer stark verbesserten Wahrscheinlichkeit eines richtigen Empfangs, falls der tatsächlich übertragene Code einen größeren Abstand aufweist.
Hier wird eine mögliche Decodiermethode in Form einer Pseudosprache dargelegt. Es wird angenommen, dass das erzeugende Polynom g(x) ein Produkt der kleinsten Polynome m&sub0;(x), m&sub1;(x) und einer unbekannten Anzahl weiterer unzerlegbarer Faktoren ist, so dass der geplante Abstand in jeder aufeinanderfolgenden verschachtelten Ebene um 2 zunimmt. Beim Empfang definieren sich die Syndrome gemäß
Sj = r(x) mod mj(x),
d. h. Sj ist der Rest der Division des empfangenen Wortes r(x) durch mj(x). Bei einer gegebenen Anzahl von Syndromen Sj kann das entsprechende Fehlermuster unter Verwendung des BCH-Decodierungsalgorithmus berechnet werden. Das Ergebnis dieses Algorithmus ist entweder ein geschätztes Fehlermuster mit einem entsprechenden Hamming-Gewicht t (das Null sein kann, wenn keinerlei Fehler aufgetaucht sind) oder ein nicht korrigierbares Fehlermuster (Algorithmus schlägt fehl). Die Decodiermethode kann als eine Baumstruktur mit Knotenpunkten und Blättern angesehen werden. Die Knotenpunkte werden durch den Abstand d benannt, der vom Decoder an diesem Punkt berücksichtigt wird.
Begin (Knotenpunkt 4)
calculate S&sub0;
calculate S&sub1;
estimate error pattern (Prüfung ob S&sub0; und S&sub1; gleich Null sind)
if t = 0
then OK, exit
else (Knotenpunkt 6)
calculate S&sub3;
estimate error pattern (einfache Fehlerkorrektur versuchen)
if t = 1
then correct, OK, exit
else (Knotenpunkt 8)
calculate S&sub5;
estimate error pattern (doppelte Fehlerkorrektur versuchen)
if t = 2
then correct, OK, exit
else (Knotenpunkt 10)
calculate S&sub7;
estimate error pattern (dreifache Fehlerkorrektur versuchen)
if t = 3
then correct, OK, exit
else ERROR, exit
end
Das Verlassen nach der Signalisierung ERROR bedeutet, dass entweder die Anzahl der Fehler größer war als mit dieser speziellen Decoderauslegung korrigiert werden kann, oder alternativ größer war als mit dem tatsächlich implementierten Code korrigiert werden kann. Im letzeren Fall kann der Decoder in der Lage gewesen sein, das tatsächlich aufgetretene Fehlermuster zu lösen oder nicht.
Es ist anzumerken, dass eine Decoderausführung nicht die gesamte Baumstruktur zu durchsuchen braucht. Nach jedem "else" kann der Decoder das Programm mit dem Ergebnis ERROR verlassen, falls die erforderlichen Operationen am nächsten Knotenpunkt nicht durchgeführt werden. So wird beispielsweise für eine einfache CRC-8-Prüfung das Datenfeld (Knotenpunkt 6) in -ERROR, exit- geändert, während die Zeilen von - calculate S&sub3;- bis zur vorletzten Zeile gelöscht werden. Bei einer einfachen Fehlerkorrektur wird in dem obigen Programm -(Knotenpunkt 8)- in -ERROR, exit- geändert, während alle Zeilen von -calculate S&sub5;- bis zur vorletzten Zeile gelöscht werden.
In Fig. 3 ist der obige Vorgang in einem Ablaufplan dargestellt. Die Blöcke 30, 32, 34, 36 berechnen nach Bedarf die Syndrome, die Blöcke 38, 40, 42, 44 prüfen das tatsächliche Vorhandensein einer entsprechenden vorher festgelegten Anzahl von Fehlern (0, 1, 2 bzw. 3), die Blöcke 46, 48, 50 führen die geeignete Korrektur durch und Block 52 signalisiert einen effektiven Fehler.
Es können in Abhängigkeit von der Zerlegung in Faktoren, der berechneten Fehlerwahrscheinlichkeit, der verfügbaren Hardware und anderen Aspekten zahlreiche andere Methoden angewendet werden. Die Abstufung des Abstands durch die zusätzlichen Faktoren kann unterschiedlich sein. Im Prinzip ist eine Zunahme des Abstands um eins möglich, eine Zunahme um mindestens zwei ist jedoch vorzuziehen. Diese Zunahme braucht bei der Folge von Faktoren nicht einheitlich zu sein. Ein oder zwei Grade könnten online ausgeführt werden, ein höherer Schutzgrad könnte jedoch den Einsatz eines Hintergrundprozessors erforderlich machen.

AUSWERTUNG DER LEISTUNGSFÄHIGKEIT

Nachfolgend wird die Leistungsfähigkeit für jede der obengenannten Kombination eines Codes C&sub4;...C&sub1;&sub0; und eines Decoders D&sub4;...D&sub1;&sub0; unter Verwendung des hinsichtlich Fig. 2 beschriebenen Verfahrens sowohl für Zufallsfehler als auch für Burstfehler ausgewertet:
D&sub4;: = t = 0 bei Verwendung von S&sub0; und S&sub1;
D&sub6;: = bis t = 1 bei Verwendung von S&sub0;, S&sub1; und S&sub3;
D&sub8;: = bis t = 2 bei Verwendung von S&sub0;, S&sub1;, S&sub3; und S&sub5;
D&sub1;&sub0;: = bis t = 3 bei Verwendung von S&sub0;, S&sub1;, S&sub3;, S&sub5; und S&sub7;
Die Leistungsfähigkeit wird ausgedrückt als eine Rate nicht korrigierter Fehler Puncor (Wahrscheinlichkeit, dass ein Decoder das empfangene Wort nicht korrigieren kann) und eine Rate nicht erkannter Fehler pundet (Wahrscheinlichkeit, dass der Decoder ein Fehlermuster falsch korrigiert oder nicht erkennt). Das Decodierverfahren kann als eine Baumstruktur angesehen werden, bei der jeder vom Decoder Di durchsuchte Knotenpunkt einen getrennten Beitrag zu der resultierenden puncor und Pundet dieses bestimmten Decoders leistet in Abhängigkeit davon, dass der Decoder diesen Knotenpunkt erreicht, und von der bedingten Wahrscheinlichkeit (abhängig von dem Decoder, der diesen Knotenpunkt erreicht) der an diesem Knotenpunkt getroffenen Entscheidungen.
Bei Burstfehlern sei angenommen, dass die Größe des Bursts derart ist, dass das Syndrom als zufällig betrachtet werden kann. Die gewünschte Reaktion aller Decoder in allen Beispielen ist eine Erkennung eines nicht korrigierbaren Fehlermusters. Alle anderen Ergebnisse, bei denen ein Decoder das empfangene Wort (falsch) annimmt oder korrigiert, werden als nicht erkannter Fehler definiert. In Tabelle 3 ist die Wahrscheinlichkeit derartiger nicht erkannter Fehler für jedes mögliche Paar Code-Decoder angegeben, wenn das Auftreten eines großen Burstfehlers als gegeben angesehen wird, d. h. es ist die Wahrscheinlichkeit in Abhängigkeit von dem Auftreten eines Burstfehlers dargestellt. Die Wahrscheinlichkeit für einen nicht erkannten Fehler eines ausreichend großen Bursts hängt nur von der Decodiermethode und nicht von dem Code ab, da das empfangene Muster als zufällig angesehen wird. Es seien r Paritätsbits und ein Fehlermuster mit einer Gewichtung t angenommen; dann ergibt sich der Beitrag an einem Knotenpunkt aus
d. h. der Teil zufällig gewählter Syndrome, die einem korrigierbaren Fehlermuster entsprechen, wenn die ersten r Syndrombits gegeben sind. Die Tabelle 3 ist aufgebaut unter Verwendung von n = 64. Es ist anzumerken, daß für eine Näherung erster Ordnung pundet(D&sub1;&sub0;) = Δpundet(Knotenpunkt 4) + Δpundet(Knotenpunkt 6) + Δpundet(Knotenpunkt 8) + Δpundet(Knotenpunkt 10).
In gleicher Weise können die anderen Einträge berechnet werden.
Tabelle 5 gibt für jedes mögliche Paar Code-Decoder die Näherung erster Ordnung für die Wahrscheinlichkeit nicht korrigierter und nicht erkannter Fehler an, wenn zufällige Bitfehler mit einer (kleinen) Bitfehlerwahrscheinlichkeit p angenommen werden. Zur Auswertung der Leistungsfähigkeit muss zwischen einigen Knotenpunktsituationen unterschieden werden.
Bei der ersten Knotenpunktsituation sind der Code Cd und der aktuelle Decodierversuch hinsichtlich des Abstands d aufeinander abgestimmt, d. h. der übertragene Code weist r Paritätsbits auf, und der Decoder berücksichtigt ebenfalls r Paritätsbits. Dies entspricht der herkömmlichen Methode zur Auswertung der Leistungsfähigkeit eines Codes. Bei einem linearen Code Cd mit einer Längen, einem Mindestabstand d und einer Anzahl A(d) von Worten mit der Gewichtung d, der Wahrscheinlichkeit eines nicht korrigierten Fehlers unter Annahme von t ist die Fehlerkorrektur (Schätzung erster Ordnung)
Des Weiteren kann die Wahrscheinlichkeit eines nicht erkannten Fehlers angenähert werden durch
Es sei angenommen, dass die Gewichte für Gewichte größer gleich d binomisch verteilt sind, d. h.
wobei r die Anzahl der Paritätsbits des Codes ist. Es ist anzumerken, dass, da x + 1 ein Faktor von g(x) für alle Codes ist, A(w) = 0 für ungerade w. Angenommen n = 64, dann erhält man eine Liste von Codewörtern mit kleinster Gewichtung, wie in Tabelle 4 aufgeführt.
Bei der zweiten Knotenpunktsituation ist der Abstand des tatsächlich übertragenen Codes größer als der von dem Decoder an diesem Knotenpunkt berücksichtigte Abstand, d. h. der übertragene Cd hat r Paritätsbits, während am aktuellen Knotenpunkt r' < r Bits berücksichtigt werden. In diesem Fall kennt der Decoder nicht die zusätzlichen Einschränkungen für den Code und berücksichtigt nur die Nullen von g(x), die den ersten r Paritätsbits entsprechen. Somit ist die Leistungsfähigkeit bei der Fehlerkorrektur und Fehlererkennung die gleiche wie in dem Fall, dass Cd, entsprechend r' Paritätsbits, übertragen worden wäre. Es ist anzumerken, dass im Falle eines nicht korrigierbaren Fehlermusters an einem bestimmten Knotenpunkt der nächste Knotenpunkt mit der Wahrscheinlichkeit 1 - Δpundet durchsucht wird, wenn dieser Knotenpunkt in dem Decoder ausgeführt wurde. Falls dies nicht der Fall ist, wird ein Fehler erkannt.
Bei der dritten Knotenpunktsituation versucht ein Decoder Cd über den geplanten Abstand hinaus zu decodieren. Das einzige richtige Ergebnis der Decodierversuche bei einer derartigen Situation wäre keine Decodierung, da ein korrigierbares Fehlermuster an einem der vorherigen Knotenpunkte hätte korrigiert werden müssen. Die Rate der nicht korrigierbaren Fehler wird durch Cd bestimmt, da bis zum Abstand d passende Ergebnis durch die Berücksichtigung der Nullen des erzeugenden Polynoms erzielt werden können. Falls der Decoder jedoch das empfangene Wort in einer nicht existierenden Null des Codes auswertet, ist das Ergebnis ein zufälliges 7-Bit-Muster (mit einer Wahrscheinlichkeit von 2&supmin; &sup7;, dass es zu einem gegebenen Fehlermuster passt), wenn angenommen wird, dass alle Codewörter gleich sind.
Das Ergebnis ist leicht durch Zählen der Parameter darzustellen. Man betrachte beispielsweise die Standardmatrix von C&sub6;, die aus 2¹&sup5; Nebengruppen besteht. Jede Nebengruppe entspricht einem bestimmten Syndrom. Das Syndrom (15 Bits) kann aufgeteilt werden in S&sub0; (1 Bit), S&sub1; (7 Bits) und S&sub3; (7 Bits). Da jegliches der fünfzehn Bitmuster genau einmal auftritt, gibt es genau eine Nebengruppe für jeden Wert von S&sub3; und S&sub0; = S&sub1; = 0. Da der Code C&sub4; auf der Vereinigung der Nebengruppen mit S&sub0; = S&sub1; = 0 besteht, ist der Code C&sub4; in Gruppen gleicher Größe hinsichtlich des Wertes von S&sub3; aufgeteilt. Da angenommen wird, dass jedes Codewort mit der gleichen Wahrscheinlichkeit übertragen wird, und da die Berechnung eines Restes eine lineare Operation ist, wurde das einheitliche Ergebnis des Restes in einer nicht existierenden Null gezeigt.
Über den geplanten Abstand hinausgehende Decodierversuche verbessern die Korrekturfähigkeit (puncor) nicht, haben jedoch eine negative Auswirkung auf Pundet, da ein erkannter Fehler korrigierbar zu sein scheint. Der Beitrag von pundet am Knotenpunkt d + 2 entspricht einer Näherung erster Ordnung
wobei t die Anzahl der Fehler ist, die der Decoder am Knotenpunkt d + 2 zu korrigieren versucht. In gleicher Weise ist der Beitrag zu pundet am Knotenpunkt d + 4 in einer Näherung erster Ordnung
wobei t die Anzahl der Fehler ist, die der Decoder am Knotenpunkt d + 2 zu korrigieren versucht.

Claims

1. Verfahren zur Decodierung einer fehlergeschützten Blocks erweiterter Daten zum Erzeugen eines Benutzerblocks mit Benutzerdaten, wobei der geschützte Block erzeugt wurde durch (a) Codierung eines ursprünglichen Benutzerblocks mit Benutzerdaten durch einen linearen und systematischen, ersten, fehlergeschützten Blockcode, definiert durch ein in Faktoren zerlegbares erzeugendes Polynom

Gn(x) = g&sub0;(x) ... gn-1(x) * gn(x) = Gn-1(x) * gn(x), wenn der ursprüngliche Benutzerblock eine erste Länge hat, oder (b) Codierung des ursprünglichen Benutzerblocks durch einen linearen und systematischen, zweiten, fehlergeschützten Blockcode, definiert durch ein erzeugendes Polynom Gn-1(x) = g&sub0;(x) ... gn-1(x), wenn der Benutzerblock eine zweite Länge hat, die größer als die erste Länge ist, wobei der fehlergeschützte Block dieselbe Länge aufweist, unabhängig davon, ob der ursprüngliche zu seiner Erzeugung codierte Benutzerblock die erste oder zweite Länge hat, wobei das Verfahren folgendes beinhaltet:

Decodierung des fehlergeschützten Block gemäß dem zweiten Code zum Erzeugen eines ersten decodierten Blocks;

Erkennung, ob der erste decodierte Block richtige Benutzerdaten enthält, und in diesem Fall Ausgabe (46) des ersten decodierten Blocks als Benutzerblock; und

Decodierung des fehlergeschützten Blocks gemäß dem ersten Code zum Erzeugen eines zweiten decodierten Blocks, falls der erste decodierte Block keine richtigen Benutzerdaten enthält, und anschließend Ausgabe (48, 50) des zweiten decodierten Blocks als Benutzerblock.

2. Decodierverfahren nach Anspruch 1, wobei der erste und der zweite Code BCH-Codes sind.

3. Decoder (74) zur Decodierung eines fehlergeschützten Blocks erweiterter Daten zum Erzeugen eines Benutzerblocks mit Benutzerdaten, wobei der geschützte Block erzeugt wurde durch (a) Codierung eines ursprünglichen Benutzerblocks mit Benutzerdaten durch einen linearen und systematischen, ersten, fehlergeschützten Blockcode, definiert durch ein in Faktoren zerlegbares erzeugendes Polynom

Gn(x) = g&sub0;(x) ... gn-1(x) * gn(x) = Gn-1(x) * gn(x), wenn der ursprüngliche Benutzerblock eine erste Länge hat, oder (b) Codierung des ursprünglichen Benutzerblocks durch einen linearen und systematischen, zweiten, fehlergeschützten Blockcode, definiert durch ein erzeugendes Polynom Gn-1(x) = g&sub0;(x) ... gn-1(x), wenn der ursprüngliche Benutzerblock eine zweite Länge hat, die größer als die erste Länge ist, wobei der fehlergeschützte Block dieselbe Länge aufweist, unabhängig davon, ob der ursprüngliche zu seiner Erzeugung codierte Benutzerblock die erste oder zweite Länge hat, wobei der Decoder folgendes beinhaltet:

erste Decodiermittel zum Decodieren des fehlergeschützten Block gemäß dem zweiten Code zum Erzeugen eines ersten decodierten Blocks;

Erkennungsmittel zum Erkennen, ob der erste decodierte Block richtige Benutzerdaten enthält;

zweite Decodiermittel zum Decodieren des fehlergeschützten Blocks gemäß dem ersten Code zum Erzeugen eines zweiten decodierten Blocks, falls der erste decodierte Block keine richtigen Benutzerdaten enthält; und

Mittel zum Ausgeben des ersten decodierten Blocks als Benutzerblock, falls er richtige Benutzerdaten enthält, oder des zweiten decodierten Blocks als Benutzerblock, falls der erste decodierte Block keine richtigen Benutzerdaten enthält.

4. Decoder nach Anspruch 3, der des Weiteren Mittel zum Aktivieren der Reihe nach der genannten ersten Decodiermittel und der genannten Erkennungsmittel und, falls erforderlich, danach der genannten zweiten Decodiermittel, enthält.

5. Decoder nach Anspruch 3 oder 4, wobei die genannten ersten Decodiermittel so ausgelegt sind, dass sie eine erste Fehlermenge korrigieren und eine zweite Fehlermenge erkennen, die größer als die erste Fehlermenge ist.

6. Decoder nach Anspruch 3, 4 oder 5, wobei die genannten ersten und zweiten Decodiermittel herkömmliche Hardware nutzen.

7. Decoder nach einem der Ansprüche 3 bis 6, wobei der erste und der zweite Code BCH-Codes sind.

8. Sender-Empfänger-Kommunikationssystem, das folgendes beinhaltet: einen Codierer, der folgendes umfasst:

Empfangsmittel zum Empfangen eines Benutzerblocks mit Benutzerdaten, der entweder eine erste oder eine zweite Länge hat, wobei die zweite Länge größer als die erste ist;

Codiermittel zum Codieren des Benutzerblocks durch einen linearen und systematischen, ersten, fehlergeschützten Blockcode, definiert durch ein in Faktoren zerlegbares erzeugendes Polynom Gn(x) = g&sub0;(x) ... gn-1(x) * gn(x) zum Erzeugen des fehlergeschützten Blocks,

wobei der durch die genannten Codiermittel erzeugte fehlergeschützte Block eine Standardlänge aufweist, die unabhängig von dem Wert von n ist; und einen Decoder, der folgendes beinhaltet:

Empfangsmittel zum Empfangen des genannten fehlergeschützten Blocks mit Standardlänge;

erste Decodiermittel zum Decodieren des fehlergeschützten Block gemäß einem Code mit einem relativ geringeren Wert von n zum Erzeugen eines ersten decodierten Blocks;

erste Erkennungsmittel zum Erkennen, ob der erste decodierte Block richtige Benutzerdaten enthält;

zweite Decodiermittel zum Decodieren des fehlergeschützten Blocks gemäß einem Code mit einem relativ höheren Wert von n zum Erzeugen eines zweiten decodierten Blocks, wenn der erste decodierte Block keine richtigen Benutzerdaten enthält; und

Mittel zum Ausgeben des ersten decodierten Blocks, wenn er richtige Benutzerdaten enthält, oder des zweiten decodierten Blocks, wenn der erste decodierte Block keine richtigen Benutzerdaten enthält.

9. System nach Anspruch 8, wobei der erste und der zweite Code BCH-Codes sind.

Tabellenunterschriften

Tabelle 1: Kleinste Polynome

Tabelle 2: Verschachtelte BCH-Codes mit der Ausgangsblocklänge = 127

Tabelle 3: Wahrscheinlichkeit nicht erkannter Fehler bei Burstfehlern

Tabelle 4: Codewörter mit kleinster Gewichtung

Tabelle 5: Fehlerwahrscheinlichkeit bei Zufallfehlern (erste Ordnung)