-
Die
vorliegende Erfindung betrifft eine Vorrichtung und Verfahren zur
Fehlererkennung in einem CRC(zyklische Redundanzüberprüfung)-Code und insbesondere
eine Vorrichtung und Verfahren zum Erkennen in einem Empfänger von Übertragungsfehlern
in dem CRC-Code, falls ein Sender den CRC-Code überträgt, der durch Sequentialisieren der
Paritätsbits
erzeugt wird, die durch Benutzen eines Generatorpolynoms in umgekehrter
Reihenfolge erzeugt werden.
-
Digitale
Kommunikationssysteme wenden oft ein Verfahren an, das die Paritätsbits zu
den Informationen tragenden Nachrichtenbits addiert, die übertragen
werden, um zu ermöglichen,
dass der Empfänger Übertragungsfehler
erkennt.
-
In
dem Empfänger
werden die Paritätsbits
allein oder zusammen mit den Nachrichtenbits überprüft, um zu bestimmen, ob Übertragungsfehler
aufgetreten sind. Unter den Verfahren zur Fehlererkennung, welche
solche Paritätsbits
benutzen, ist das CRC-Verfahren als das leistungsstärkste Verfahren bekannt.
-
1 stellt
die Struktur des herkömmlichen CRC(zyklische
Redundanzüberprüfung)-Codes
dar. Mit Bezug auf 1 umfassen n CRC-Code-Bits k Nachrichtenbits
(mk-1 ~ m0) und
n-k Paritätsbits
(Pn-k-1 ~ p0).
-
Der
CRC-Code kann durch ein bestimmtes Polynom dargestellt werden und
die Paritätsbits
können
auch durch ein Polynom dargestellt werden, indem das Restpolynom
des Nachrichtenbitpolynoms benutzt wird, das durch das Generatorpolynom
dividiert wird.
-
Die
Polynomdarstellung von k Nachrichtenbits lautet m(X)
= m0 + m1X1 + m2X2 +
... + mk-1Xk-1 und
die Polynomdarstellung des Generatorpolynoms zum Erzeugen der Paritätsbits lautet g(X) = g0 + g1X1 + g2X2 + ... + gn-kXn-k und die Polynomdarstellung von n-k
Paritätsbits
lautet p(X) = p0 + p1X1 + p2X2 + ... + gn-k-1Xn-k-1
-
Danach
kann der CRC-Code ausgedrückt werden
durch C(X) = Xn-km(X)
+ p(X)worin p(X) = Xn-km(X) mod g(X).
-
Solch
ein CRC-Code-Verfahren zum Erkennen, ob Übertragungsfehler aufgetreten
sind, dividiert den empfangenen CRC-Code durch das Generatorpolynom
und erkennt, ob der Rest der Division null ist. Dieses Verfahren
zur Erkennung von Übertragungsfehlern
des CRC-Codes kann durch die folgenden Gleichungen bewiesen werden.
-
Da
p(X) der Rest von Xn-km(X) dividiert durch g(X)
ist, kann, wie oben erwähnt,
die folgende Gleichung definiert werden. Xn-km(X) = g(X)G(x) + p(X)
-
Wenn
p(X) nach links transponiert wird, ergibt sich Xn-km(X) – p(X)
= g(X)G(X).
-
Da
hier im Gegensatz zu den allgemeinen Vorgängen „-p(X)" gleich „+p(X)" in den Vorgängen in dem binären Galois-Feld
ist, ist Xn-km(X) + p(X)
= g(X)Q(X).
-
Da
die linke Seite in der obigen Gleichung c(X) entspricht, sind der
Quotient und der Rest von c(X) dividiert durch g(X) jeweils gleich
Q(X) und „0". 2 veranschaulicht
eine herkömmliche
Vorrichtung zum Erkennen von CRC-Code-Fehlern unter Anwendung des
genannten Prinzips. Mit Bezug auf 2 umfasst
die beschriebene Vorrichtung eine Divisionseinheit 11 zum
Dividieren des empfangenen CRC-Codes durch das Generatorpolynom
und eine Bestimmungseinheit 13 zum Bestimmen des Auftretens
von Fehlern durch Benutzen von Ausgaben aus der Divisionseinheit 11.
Die Divisionseinheit 11 umfasst n-k Ein-Bit-Register 11a,
n-k Multiplikatoren 11b und n-k exklusive OR-Gates 11c.
Die Bestimmungseinheit 13 umfasst ein NOR-Gate 13 für einen NOR-Vorgang
bezüglich
der Ausgaben aus den Registern 11a der Divisionseinheit 11.
-
Wenn
ein Sender in dem digitalen Kommunikationssystem die CRC-Code-Bits
(mk-1, mk-2, ...
m0, pn-k-1, ...,
p0) welche die Struktur aus 1 aufweisen, überträgt, werden
die CRC-Code-Bits, die durch einen angemessenen Kanal gegangen sind,
in die Register 11a sequentiell eingegeben und jedes der CRC-Code-Bits
in den Registern wird bei jeder Eingabe um eine Position von links
nach rechts verschoben. Die Multiplikatoren 11b multiplizieren
die CRC-Code-Bits, die sequentiell übertragen werden, durch das
Register 11a, das sich ganz rechts befindet, mit dem Koeffizientensignal
g0, g1, g2, ..., gn-k-1 des
Generatorpolynoms und jedes der X-OR-Gates 11c führt bitweise
einen exklusiven OR-Vorgang auf jedem Bit aus, das aus jedem der
Multiplikatoren 11b und jedem der CRC-Code-Bits, die nacheinander eingegeben
werden, folgt. Nachdem alle n Bits in die Register 11a eingegeben
worden sind und durch die oben erwähnten Vorgänge verarbeitet worden sind, bleibt
der Endrest des CRC-Codes, der durch das Generatorpolynom dividiert
wird, in den Registern 11a. Wenn keine Übertragungsfehler aufgetreten sind,
werden alle resultierenden Inhalte der Register 11a zu „0s". Folglich stellt
die Bestimmungseinheit 13a zum Ausführen von NOR-Vorgängen auf
den n-k Eingabebits aus den Registern 11a eine Ausgabe „1" bereit, nur wenn
der CRC-Code keine Übertragungsfehler
aufweist. Wenn das Ergebnis sämtlicher NOR-Vorgänge andererseits „0" ist, entscheidet
die Bestimmungseinheit 13a, dass der CRC-Code Übertragungsfehler
aufweist.
-
Unlängst wurde
ein neues Verfahren, das sich von dem oben erwähnten Verfahren unterscheidet,
zur Erzeugung des CRC-Codes
mit Hilfe von Paritätsbits
als ein Datenübertragungsverfahren
in dem universellen mobilen Telekommunikationssystem (UMTS) vorgeschlagen,
das die nächste
Generation mobiler Telekommunikation betrifft und IMT-2000 genannt
wird. Das heißt,
das UMTS wendet ein neues Verfahren zur Benutzung von Paritätsbits an,
die im Gegensatz zu der herkömmlichen
Technik erzeugt werden, indem die Restbits der Nachrichtenbits dividiert
durch das Generatorpolynom in umgekehrter Reihenfolge sequentialisiert
werden.
-
Im
Folgenden wird das neue Verfahren detailliert erläutert.
-
3 stellt
eine Struktur des CRC-Codes dar, in dem die Paritätsbits in
umgekehrter Reihenfolge addiert werden. Der CRC-Code wird in einer
Sequenz von mk-1, mk-2,
.... m0, p0 ...,
pn-k-1 übertragen. Der
CRC-Code kann durch ein Polynom c(X) = Xm-km(X) + p☐(X)ausgedrückt werden,
worin unter der Annahme, dass p(X) = Xn-km(X)
mod g(X), p☐(X) definiert wird
als p☐(X) =
Xdegp(X)p(X-1)
-
Jedoch
kann die herkömmliche
Fehlererkennungsvorrichtung Fehler nur in dem herkömmlichen CRC-Code
erkennen, in dem die Paritätsbits
in der normalen Reihenfolge, die in 1 dargestellt
ist, hinzugefügt
werden. Die herkömmliche
Fehlererkennungsvorrichtung kann Übertragungsfehler in dem neuen
CRC-Code, in dem die Paritätsbits
in umgekehrter Reihenfolge hinzugefügt werden, wie in 3 dargestellt,
nicht erkennen, da der Rest des neuen CRC-Code-Polynoms c(X) dividiert
durch das Generatorpolynom g(X) in der herkömmlichen Vorrichtung nicht
zu „0" wird. Dementsprechend
besteht eine Notwendigkeit zur Erkennung von Übertragungsfehlern in dem CRC-Code,
der die invertierten Paritätsbits
aufweist.
-
JP 04 150 632 (Fujitsu)
offenbart eine Schaltung, in der eine Bitentnahmeschaltung ein CRC-Bit von
Empfangsdaten gemäß einem
Synchronisiersignal entnimmt, das durch eine Schaltung zur Erzeugung
von Synchronisiersignalen erzeugt wird, während eine arithmetische CRC-Bit-Schaltung
ein CRC-Bit von Empfangsdaten berechnet. Da das CRC-Bit jeder Rahmengruppe
mit einer Verzögerung einer
Rahmengruppe empfangen wird, wird die Zeitdifferenz eingestellt
und ergibt ein CRC-Bit, das im Hinblick auf eine relevante Rahmengruppe
berechnet wird, wobei das entnommene CRC zu einer Vergleichsschaltung
geht. Wenn die Empfangsdaten normal sind, sind beide CRC-Bits übereinstimmend, und
wenn ein Datenfehler existiert, sind sie abweichend. Im Falle einer
Abweichung sendet die Vergleichsschaltung ein Fehlersignal.
-
Das
Sitzungsdokument 3 GPP, TSGR1#5(99)689, „CRC position" vom 1. Juni 1999 offenbart
mögliche
CRC-Positionen, welche Positionen, in denen die CRC-Bits nach einem
Datenstrom variabler Größe angehängt werden,
und Positionen aufweist, in denen CRC-Bits vor dem Datenstrom variabler
Größe angehängt werden.
In dem erstgenannten Fall werden CRC-Bits in umgekehrter Reihenfolge
angehängt,
da sich herausgestellt hat, dass dies zur Datenübertragung bei variabler Geschwindigkeit
unter Verwendung der einfachen Blindgeschwindigkeitserkennung wünschenswert
ist.
-
WO
82/01084 (Western Electric Company) offenbart ein Verfahren und
eine Vorrichtung zum Überwachen
von Fehlern in digitalen Übertragungssystemen.
Hier werden Fehler bei einer digitalen Übertragung überwacht, indem eine zyklische
Redundanzprüfung
(CRC) angewendet wird. In einem Sender wird ein CRC-Codewort mit
einer vorbestimmten Bitzahl aus einem Bitblock eines derzeit übertragenen
Zeitmultiplexsignals erzeugt. Die Codewortbits werden dann in die
vorbestimmten Bitpositionen des nächsten darauf folgenden Bitblocks
des XTDM-Signals eingefügt.
In einem Empfänger
werden Bits eines derzeit empfangenen Zeitmultiplexsignals mit Bits
eines CRC-Codeworts
verglichen, das aus dem letzten davor empfangenen Bitblock erzeugt wird,
um Übertragungsfehler
anzuzeigen. In einem spezifischen Beispiel wird ein CRC-Codewort
eines sechsten Bits verwendet und die Codewortbits werden in die
vorbestimmten Rahmenbitpositionen eingefügt.
-
Es
ist die Aufgabe der vorliegenden Erfindung, eine Vorrichtung und
Verfahren zur Erkennung von Übertragungsfehlern
des empfangenen CRC-Codes bereitzustellen, in dem ein Paritätsbitstrom
in umgekehrter Reihenfolge hinzugefügt wird.
-
Gemäß der vorliegenden
Erfindung werden eine Vorrichtung und ein Verfahren nach den beigefügten Ansprüchen bereitgestellt.
Bevorzugte Merkmale der Erfindung werden aus den abhängigen Ansprüchen und
der folgenden Beschreibung offenbar.
-
In
einem ersten Aspekt der vorliegenden Erfindung wird ein Verfahren
zur Fehlererkennung in einem CRC-Code bereitgestellt, das die folgenden Schritte
umfasst: sequentielles Empfangen eines CRC-Codes mit Nachrichtenbits
und invertierten Paritätsbits,
die an den Nachrichtenbits angehängt
sind; Schalten der Nachrichtenbits und der invertierten Paritätsbits zur
getrennten Übertragung;
Dividieren der Nachrichtenbits durch ein Paritätsbit-Generatorpolynom, um
einen Rest zu bilden, wobei die Nachrichtenbits in mehrere seriell
verbundene Ein-Bit-Register gespeichert werden und danach nach vorne
verschoben werden, bis ein letztes Nachrichtenbit durch die mehreren
Ein-Bit-Register gegangen ist, während ferner
eine Verschiebung nach hinten bereitgestellt wird, um das Verschieben
nach hinten der Restbits zu bewirken, die in den mehrere Ein-Bit-Registern gespeichert
sind, um für
den Vergleichsschritt sequentiell nach hinten verschobene Restbits
in umgekehrter Reihenfolge bereitzustellen; Vergleichen von sequentiell
empfangenen Restbits mit den sequentiell empfangenen invertierten
Paritätsbits;
und Bestimmen, ob in dem empfangenen CRC-Code basierend auf den
Ergebnissen des Vergleichschritts ein Übertragungsfehler aufgetreten
ist.
-
In
einem anderen Aspekt der vorliegenden Erfindung wird eine Vorrichtung
zur Fehlererkennung in einem CRC-Code bereitgestellt, wobei die
Vorrichtung Folgendes umfasst: eine Schalteinheit zum sequentiellen
Empfangen des CRC-Codes mit Nachrichtenbits und invertierten Paritätsbits,
die an den Nachrichtenbits angehängt
sind, und zum Schalten der Nachrichtenbits und der invertierten
Paritätsbits, die
getrennt übertragen
werden sollen; eine Divisionseinheit zum Empfangen der Nachrichtenbits,
die durch die Schalteinheit übertragen
werden, und zum Dividieren der Nachrichtenbits durch ein Paritätsbit-Generatorpolynom,
um einen Rest zu bilden, und zum sequentiellen Ausgeben von Restbits
des Restes in umgekehrter Reihenfolge; eine Vergleichseinheit zum
Vergleichen der invertierten Restbits, die von der Divisionseinheit
sequentiell empfangen werden, mit den invertierten Paritätsbits,
die durch die Schalteinheit sequentiell übertragen werden; und eine
Bestimmungseinheit zum Bestimmen, ob in dem empfangenen CRC-Code
basierend auf den Ergebnissen der Vergleichseinheit Übertragungsfehler
aufgetreten sind; die Bestimmungseinheit umfasst Folgendes: mehrere
Ein-Bit-Register, die seriell miteinander verbunden sind, um die
Restbits der Nachrichtenbits zu speichern, die durch das Generatorpolynom
dividiert werden; mehrere Vorwärtsverschiebungsschalter,
die geschaltet werden, um eine Vorwärtsverschiebung der Nachrichtenbits
in den mehreren Registern zu bewirken, bis die letzte Nachrichtenbiteingabe
von der Schalteinheit durch die mehreren Ein-Bit-Register geht;
und mehrere Rückwärtsverschiebungsschalter,
die geschaltet werden, um eine Rückwärtsverschiebung
der Restbits in den mehreren Registern zu bewirken, so dass die
Restbits, die in den mehreren Ein-Bit-Registern gespeichert sind,
der Vergleichseinheit sequentiell bereitgestellt werden.
-
Vorzugsweise
umfasst die Vergleichseinheit ein X-OR-Gate.
-
Vorzugsweise
umfasst die Bestimmungseinheit Folgendes: ein OR-Gate mit einer
Eingabe zum Empfangen der Ausgabe aus der Vergleichseinheit; und
ein Verzögerungsregister
zum Empfangen der Ausgabe von dem OR-Gate und zum Rückkoppeln der
Ausgabe von dem OR-Gate zu dem OR-Gate einen Taktzeitraum später.
-
In
einem anderen Aspekt der Erfindung wird eine Vorrichtung zur Fehlererkennung
in einem CRC-Code bereitgestellt, wobei die Vorrichtung dadurch
gekennzeichnet ist, dass sie Folgendes umfasst: eine Divisionseinheit,
die den CRC-Eingabecode
sequentiell empfängt
und verschiebt, indem sie mehrere Ein-Bit-Register benutzt, wobei
der CRC-Eingabecode Nachrichtenbits und invertierte Paritätsbits umfasst,
die an den Nachrichtenbits angehängt
sind, und welche den CRC-Code durch ein Paritätsbit-Generatorpolynom dividiert,
um einen Rest zu bilden, und Restbits des Restes in den mehreren
Ein-Bit-Registern
speichert; eine Vergleichseinheit zum Vergleichen jedes von mehreren
symmetrisch gepaarten Entsprechungsbits miteinander, von den zwei äußersten
Bits zu den zwei innersten Bits der Restsequenz, die in den mehreren
Ein-Bit-Registern gespeichert ist; und eine Bestimmungseinheit zum
Bestimmen, ob in dem CRC-Eingabecode basierend auf den Ergebnissen
der Vergleichseinheit ein Übertragungsfehler
aufgetreten ist.
-
Vorzugsweise
umfasst die Vergleichseinheit mehrere X-OR-Gates, deren Anzahl dem ganzzahligen
Anteil des Quotienten der Division der Anzahl der mehreren Register
durch 2 entspricht.
-
Wenn
die Anzahl der mehreren Ein-Bit-Register ungerade ist, wird das
mittlere Bit des Restes, der in dem mittleren Register der mehreren Ein-Bit-Register
gespeichert ist, vorzugsweise direkt in die Bestimmungseinheit eingegeben.
-
In
einem anderen Aspekt der Erfindung wird ein Verfahren zur Fehlererkennung
in einem CRC-Code bereitgestellt, dass dadurch gekennzeichnet ist,
dass es die folgenden Schritt umfasst: sequentielles Empfangen eines
CRC-Eingabecodes, wobei der CRC-Eingabecode Nachrichtenbits und
invertierte Paritätsbits
umfasst, die an den Nachrichtenbits angehängt sind, und Dividieren des
CRC-Codes durch ein Paritätsbit-Generatorpolynom,
um einen Rest zu bilden; Vergleichen jedes von mehreren symmetrisch
gepaarten Entsprechungsbits miteinander, von den zwei äußersten
Bits zu den zwei innersten Bits von Restbits des Restes; und Bestimmen,
ob in dem CRC-Eingabecode basierend auf den Ergebnissen des Vergleichsschrittes
ein Übertragungsfehler
aufgetreten ist.
-
Vorzugsweise
umfasst der Schritt des Bestimmens den folgenden Schritt: wenn die
Anzahl der Restbits ungerade ist, Bestimmen, ob in dem CRC-Eingabecode
basierend auf den Ergebnissen des Vergleichsschrittes und basierend
auf dem Wert des mittleren Bits des Restes Übertragungsfehler aufgetreten
sind.
-
Für ein besseres
Verständnis
der Erfindung und um zu zeigen, wie die Ausführungsformen davon umgesetzt
werden können,
wird nun beispielhaft auf die beiliegenden Diagrammzeichnungen Bezug
genommen, in denen:
-
1 ein
schematisches Diagramm ist, welches die Struktur des herkömmlichen
CRC-Code-Bitstroms darstellt;
-
2 ein
schematisches Diagramm ist, das die Konfiguration einer herkömmlichen
Vorrichtung zur Fehlererkennung in dem CRC-Code aus 1 darstellt;
-
3 ein
schematisches Diagramm ist, das die Struktur eines CRC-Code-Bitstroms
darstellt, in welchem die Paritätsbits
an den Nachrichtenbits in umgekehrter Reihenfolge angehängt sind;
-
4 ein
schematisches Diagramm ist, das die Konfiguration einer Vorrichtung
zur Fehlererkennung in dem CRC-Code darstellt, der die invertierten Paritätsbits aus 3 aufweist;
-
5 ein
schematisches Diagramm ist, das die Konfiguration einer Vorrichtung
zur Fehlererkennung in dem CRC-Code mit den invertierten Paritätsbits gemäß einer
zweiten Ausführungsform
der vorliegenden Erfindung darstellt;
-
6 ein
schematisches Diagramm ist, das die Konfiguration einer Vorrichtung
zur Fehlererkennung in dem CRC-Code mit den invertierten Paritätsbits gemäß einer
dritten Ausführungsform
der vorliegenden Erfindung darstellt;
-
7 ein
schematisches Diagramm ist, das einen Beispielmodus der Vorrichtung
aus 6 darstellt, wenn die Anzahl der Restbits der
Division gerade ist; und
-
8 ein
schematisches Diagramm ist, das einen anderen Beispielmodus der
Vorrichtung aus 6 darstellt, wenn die Anzahl
der Restbits der Division ungerade ist.
-
Die
bevorzugten Ausführungsformen
der vorliegenden Erfindung werden nun mit Bezug auf die beiliegenden
Zeichnungen beschrieben. In der folgenden Beschreibung werden ähnliche
Bezugzeichen für ähnliche
Elemente benutzt.
-
Wie
oben bezüglich 3 beschrieben,
umfasst der CRC-Code die Nachrichtenbits und die Paritätsbits,
die an den Nachrichtenbits angehängt
sind. Die Paritätsbits
bestehen aus den invertierten Restbits der Nachrichtenbits, dividiert
durch ein bestimmtes Generatorpolynom.
-
Um
zum Verständnis
der vorliegenden Erfindung beizutragen, ist 4 ein schematisches
Diagramm, das die Konfiguration einer Vorrichtung zur Fehlererkennung
in dem CRC-Code darstellt. Mit Bezug auf 4 umfasst
die Vorrichtung zur Fehlererkennung in dem empfangenen CRC-Code
eine Schalteinheit 401, eine Divisionseinheit 402 zum
Dividieren der Eingabenachrichtenbits durch ein Paritätsbit-Generatorpolynom
und zum Speichern der Restbits der Division, eine Pufferspeichereinheit 403 zum
Zwischenspeichern der Eingabeparitätsbits, eine Schalteinheit 401 zum
selektiven Schalten des CRC-Eingabecodes zwischen der Divisionseinheit 402 und
der Pufferspeichereinheit 403, eine Vergleichseinheit 404 zum
Vergleichen der Ausgabe der Divisionseinheit 402 mit den
Paritätsbits,
die in der Pufferspeichereinheit 403 enthalten sind, und
eine Bestimmungseinheit 405, um basierend auf den Ergebnissen
der Vergleichseinheit 404 zu bestimmen, ob Übertragungsfehler
in dem CRC-Code aufgetreten sind.
-
Die
Schalteinheit 401 schaltet den CRC-Code zu der Divisionseinheit 402 während des
Eingabezeitraums der Nachrichtenbits. Andererseits schaltet die
Schalteinheit 401 den CRC-Code zu der Pufferspeichereinheit 403 während des
Eingabezeitraums der Paritätsbits.
-
De
Divisionseinheit 402 umfasst n-k Ein-Bit-Register 402a,
n-k Multiplikatoren 402b und n-k
exklusive OR-Gates 402c. Gemäß dem Schaltvorgang der Schalteinheit 401 werden
die Nachrichtenbits in die Divisionseinheit 402 während des
Eingabezeitraums der Nachrichtenbits des CRC-Codes sequentiell eingegeben.
Die Eingabenachrichtenbits werden in die Register 402a sequentiell
eingegeben, indem die Inhalte jeder der Register 402a mit
jeder Eingabe von links nach rechts um eine Position verschoben
werden.
-
Während die
Nachrichtenbits in die Divisionseinheit 402 eingegeben
werden, dividiert die Divisionseinheit 402 die Nachrichtenbits
durch das Generatorpolynom. Die Nachrichten, das heißt, die
Eingabenachrichtenbits werden mit dem Generatorpolynom in den Multiplikatoren 402b multipliziert,
wonach die Ergebnisse durch die X-OR-Gates 402c gemäß der exklusiven
OR-Funktion verknüpft
werden, so dass der Divisionsvorgang ausgeführt wird. Der Rest der Division
wird in den Registern 402a gespeichert. Das MSB (Most Significant
Bit = Bit mit dem höchsten Stellenwert)
des Restes wird in dem Register 402a ganz rechts gespeichert,
während
das LSB (Least Significant Bit = Bit mit dem niedrigsten Stellenwert) des
Restes in dem Register 402a ganz links gespeichert wird.
-
Nachdem
alle Nachrichtenbits in die Divisionseinheit 402 eingegeben
worden sind, schaltet die Schalteinheit 403 den CRC-Eingabecode
zu der Pufferspeichereinheit 403, um die Eingabeparitätsbits in der
Pufferspeichereinheit 403 sequentiell zu speichern. Die
Pufferspeichereinheit 403 umfasst n-k Ein-Bit-Register,
das heißt,
genauso viele wie die Anzahl der Paritätsbits. Jedes Register in der
Pufferspeichereinheit 403 speichert ein Paritätsbit.
-
Die
Vergleichseinheit 404 umfasst mehrere X-OR-Gates (exklusive
OR-Gates) 404a, welche jeweils bitweise X-OR-Vorgänge auf
dem jeweiligen Restbit, das von der Divisions einheit 402 ausgegeben
wird, und dem entsprechenden Paritätsbit ausführen, das in der Pufferspeichereinheit 403 gespeichert
ist. Die Anzahl der X-OR-Gates 404a ist n-k, was der Anzahl
der Paritätsbits
entspricht. Jedes der X-OR-Gates 404a weist eine Eingabe
aus einem der Register 402a der Divisionseinheit 402 und
die andere Eingabe aus einem der Register der Pufferspeichereinheit 403 auf.
Das erste Eingabeparitätsbit
in dem Paritätsbitstrom
wird mit dem LSB des Restes verglichen, der aus der Divisionseinheit 402 ausgegeben
wird, während
das letzte Eingabeparitätsbit
in dem Paritätsbitstrom
mit dem MSB des Restes verglichen wird, der aus der Divisionseinheit 402 ausgegeben
wird. Folglich werden die invertierten Paritätsbits mit den Restbits verglichen,
die aus der Divisionseinheit 402 ausgegeben werden.
-
Da
die Paritätsbits
ursprünglich
auf der Übertragungsseite
des CRC-Codes erzeugt werden, indem die Nachrichtenbits durch das
Generatorpolynom dividiert werden, wird der empfangene CRC-Code
auf der Empfangsseite wieder durch das Generatorpolynom dividiert,
um den Rest zu bilden, und der Rest wird mit dem invertierten Paritätsbitstrom
verglichen, um Übertragungsfehler
zu erkennen. Das heißt, Übertragungsfehler
in dem CRC-Code sind erkennbar, indem der Ausgabestrom aus der Divisionseinheit 402 mit
dem invertierten Inhaltsstrom der Pufferspeichereinheit 403 bitweise
verglichen wird. Wenn in dem CRC-Code keine Übertragungsfehler aufgetreten
sind, geben alle X-OR-Gates 404a in der Vergleichseinheit 404 „0s" aus.
-
Die
Entscheidungseinheit 405 umfasst ein NOR-Gate 405a mit
mehreren Eingaben aus der Vergleichseinheit 404. Dementsprechend
gibt die Bestimmungseinheit 405 „1" zur Angabe eines fehlerfreien CRC-Codes
nur dann aus, wenn alle X-OR-Gates 404a „0s" ausgeben.
-
Gemäß der oben
erwähnten
Vorrichtung wird der Divisionsvorgang zum Dividieren der Nachrichtenbits
durch das Genera torpolynom während
des Nachrichtenbit-Eingabezeitraums ausgeführt, um die Restbits zu bilden,
und während
des Paritätsbit-Eingabezeitraums
werden die Eingabeparitätsbits
gespeichert und mit den Restbits in umgekehrter Reihenfolge verglichen.
Wenn die verglichenen zwei Bitströme die gleichen sind, wird
bestimmt, dass kein Übertragungsfehler
in dem empfangenen CRC-Code aufgetreten ist. Aus diesem Grund kann
erkannt werden, ob die Übertragungsfehler
in dem empfangenen CRC-Code aufgetreten sind, der die invertierten
Paritätsbits
umfasst.
-
5 ist
ein schematisches Diagramm, dass die Konfiguration einer Vorrichtung
zur Fehlererkennung in dem CRC-Code
gemäß einer
zweiten Ausführungsform
der vorliegenden Erfindung darstellt. In der zweiten Ausführungsform
umfasst die Fehlererkennungsvorrichtung eine Divisionseinheit 502 zum Dividieren
der Eingabenachrichtenbits durch ein Paritätsbit-Generatorpolynom und zum Ausgeben des Restes
der Division, eine Vergleichseinheit 504, um die sequentiell
ausgegebenen Restbits aus der Divisionseinheit 502 mit
den sequentiell eingegebenen Paritätsbits auf einer Bit-für-Bit-Basis
bitweise zu vergleichen, eine Schalteinheit 501 zum selektiven Schalten
des CRC-Eingabecodes zu der Schalteinheit 502 und zu der
Vergleichseinheit 504 und eine Bestimmungseinheit 505,
um basierend auf den Ergebnissen der Vergleichseinheit 504 zu
bestimmen, ob Übertragungsfehler
in dem CRC-Code aufgetreten sind.
-
Die
Divisionseinheit 502 umfasst n-k Ein-Bit-Register 502a,
n-k Multiplikatoren 502b, n-k Vorwärtsverschiebungsschalter 503a,
n-k Rückwärtsverschiebungsschalter 503b und
n-k X-OR-Gates (exklusive
OR-Gates) 502c. Die Register 502a sind seriell
miteinander verbunden und jedes der Register 502a speichert
das eine Restbit, das aus der Divisionseinheit 502 ausgegeben
wird. Während
des Eingabezeitraums der Nachrichtenbits werden die Nachrichtenbits
in die Divisionseinheit 502 gemäß dem Schaltvorgang von der
Schalteinheit 501 sequentiell eingegeben. Die Eingabenachrichtenbits werden
in die Register 502a sequentiell eingegeben und von links
nach rechts um eine Position verschoben.
-
Während die
Nachrichtenbits in die Divisionseinheit 502 eingegeben
werden, dividiert die Divisionseinheit 502 die Nachrichtenbits
durch das Generatorpolynom. Der Divisionsvorgang ist dem oben bezüglich 4 erwähnten Divisionsvorgang ähnlich.
Dementsprechend werden die Endrestbits der Division in den Registern 502a gespeichert.
Insbesondere wird das MSB (Most Significant Bit = Bit mit dem höchsten Stellenwert)
des Restes in dem Register ganz rechts gespeichert, während das
LSB (Least Significant Bit = Bit mit dem niedrigsten Stellenwert) des
Restes in dem Register ganz links gespeichert wird.
-
Wenn
die Endrestbits jeweils in den Registern 502a gespeichert
werden, wird jeder der Inhalte der Register 502a sequentiell
bei jedem Taktsignal um eine Position nach links verschoben und
die verschobenen Bits werden sequentiell in die Vergleichseinheit 504 eingegeben.
-
Die
Schalteinheit 501 wird geschaltet, um den CRC-Code während des
Nachrichtenbit-Eingabezeitraums in die Divisionseinheit 502 einzugeben. Andererseits
wird die Schalteinheit 501 geschaltet, um den CRC-Code
während
des Paritätsbit-Eingabezeitraums
in die Vergleichseinheit 504 einzugeben.
-
Die
Schalteinheit 501 wirkt zusammen mit den Vorwärtsverschiebungsschaltern 503a und
den Rückwärtsverschiebungsschaltern 503b.
Während die
Schalteinheit 501 die Nachrichtenbits zu der Divisionseinheit 502 schaltet,
werden genauer gesagt alle Vorwärtsverschiebungsschalter 503a in
einen ON-Zustand versetzt und alle Rückwärtsverschiebungsschalter 503b werden
in einen OFF-Zustand versetzt. Während
die Schalteinheit 501 die Paritätsbits zu der Vergleichs einheit 504 schaltet,
werden andererseits alle Vorwärtsverschiebungsschalter 503a in
einen OFF-Zustand versetzt und alle Rückwärtsverschiebungsschalter 503b in
einen ON-Zustand versetzt. Während
die Nachrichtenbits in die Divisionseinheit 502 eingegeben
werden, dividiert die Divisionseinheit 502 die Nachrichtenbits
durch das Generatorpolynom. Nach Vollendung der Eingabe der Nachrichtenbits
werden die Restbits der Division in den Registern 502a der
Divisionseinheit 502 gespeichert. Und während jedes der Paritätsbits sequentiell in
die Vergleichseinheit 504 eingegeben wird, wird jedes der
Restbits, die in den Registern 502a in der Divisionseinheit 502 gespeichert
sind, sequentiell und in umgekehrter Reihenfolge in die Vergleichseinheit 504 eingegeben.
Dementsprechend werden die invertierten Restbits sequentiell auf
einer Bit-für-Bit-Basis
mit den Paritätsbits
verglichen.
-
Die
Vergleichseinheit 504 umfasst ein X-OR-Gate (exklusives
OR-Gate) 504a, das die zwei Eingabeanschlüsse aufweist,
einen für
die Restbits, die durch den letzten Rückwärtsverschiebungsschalter 503b verschoben
werden, und einen für
die Paritätsbits,
die durch die Schalteinheit 501 eingegeben werden. Somit
vergleicht die Vergleichseinheit 504 die invertierten Restbits
mit den sequentiell eingegebenen Paritätsbits und gibt „1" nur dann aus, wenn die
zwei Bitströme
die gleichen sind.
-
Die
Bestimmungseinheit 505 umfasst ein OR-Gate 505a und
ein Verzögerungsregister 505b. Die
Ausgabe aus der Vergleichseinheit 504 wird in das OR-Gate 505a eingegeben
und die Ausgabe aus dem OR-Gate 505a wird in das Verzögerungsregister 505b eingegeben
und nach einem Taktzeitraum zurück
in das OR-Gate 505a eingegeben.
Somit wird die Ausgabe der Bestimmungseinheit 505 zur Angabe
eines fehlerfreien CRC-Codes
nur dann zu „0", wenn das X-OR-Gate 504a in
der Vergleichseinheit 504 kontinuierlich „0s" ausgibt.
-
Gemäß der oben
erwähnten
Ausführungsform
werden die Nachrichtenbits während
des Nachrichtenbit-Eingabezeitraums durch das Generatorpolynom dividiert,
um den Rest zu bilden, und die Paritätsbits werden während des
Paritätsbit-Eingabezeitraums
mit den invertierten Restbits sequentiell verglichen. Aus diesem
Grund kann erkannt werden, ob Übertragungsfehler
in dem empfangenen CRC-Code aufgetreten sind, der die invertierten
Paritätsbits
aufweist.
-
6 stellt
die Konfiguration einer Vorrichtung zur Fehlererkennung in dem CRC-Code
gemäß einer
dritten Ausführungsform
der vorliegenden Erfindung dar. In der dritten Ausführungsform
umfasst die Fehlererkennungsvorrichtung eine Divisionseinheit 601 zum
Dividieren der Eingabenachrichtenbits durch das Generatorpolynom
und zum Speichern der Restbits der Division jeweils in den Registern 601a, eine
Vergleichseinheit 602 zum miteinander Vergleichen der zwei äußersten
Bits der Endrestbits, die in den Registern 601a gespeichert
sind, und der zwei innersten Bits der Restbits, und eine Bestimmungseinheit 603,
um basierend auf den Ergebnissen der Vergleichseinheit 602 zu
bestimmen, ob in dem CRC-Code Übertragungsfehler
aufgetreten sind.
-
Mit
Bezug auf 6 umfasst die Divisionseinheit 601 n-k
Register 601a, n-k Multiplikatoren 601b, n-k X-OR-Gates
(exklusive OR-Gates) 601c.
-
Die
Vorgänge
der Elemente sind denjenigen der oben erwähnten Ausführungsformen ähnlich.
Jedoch werden in der dritten Ausführungsform die gesamten CRC-Code-Bits
einschließlich
der Nachrichtenbits und der Paritätsbits in die Divisionseinheit 601 eingegeben.
Dementsprechend dividiert die Divisionseinheit 601 den
gesamten CRC-Code durch das Generatorpolynom und speichert den Rest
der Division in den Registern 601a.
-
Die
Vergleichseinheit 602 umfasst mehrere X-OR-Gates 602a,
deren Anzahl der ganzzahlige Anteil des Quotienten der Division
der Anzahl der Register 601c durch 2 ist. Wenn die Divisionseinheit 601 zum
Beispiel 4 Register 601a aufweist, wie in 7 dargestellt,
wird die Vergleichseinheit 602 mit 2 X-OR-Gates 602a bereitgestellt.
Wenn die Divisionseinheit 601 3 Register 601a aufweist,
wie in 8 dargestellt, wird die Vergleichseinheit 602 mit
1 X-OR-Gate 602a bereitgestellt.
-
Die
Eingaben jedes X-OR-Gates 602a werden wie folgt bestimmt.
Das heißt,
zwei symmetrische Gegenbits der Endrestbits, das heißt, von
den zwei äußersten
Bits der Endrestbits zu den zwei innersten Bits der Restbits, werden
gepaart und die jeweils gepaarten zwei Bits werden miteinander verglichen.
Mit anderen Worten, das MSB, das heißt, das Bit des Restes, das
sich ganz rechts befindet, wird mit dem LSB, das heißt, mit
dem Bit des Restes, das sich ganz links befindet, verglichen. Dementsprechend
werden die symmetrisch gepaarten zwei Bits in jedes X-OR-Gate 602a paarweise
eingegeben. Ferner werden alle Ausgaben aus den X-OR-Gates 602a in
der Vergleichseinheit 602 in die Bestimmungseinheit 603 eingegeben.
-
Wenn
indes die Anzahl der Register 601a ungerade ist, wird das
mittlere Bit des Restes, das in dem mittleren Register 601a gespeichert
wird, weiter direkt in die Bestimmungseinheit 603 eingegeben, wie
in 8 dargestellt.
-
Die
Bestimmungseinheit 603 umfasst ein NOR-Gate 603a.
Wenn die Anzahl der Register 601a gerade ist, wie in 7 dargestellt,
weist das NOR-Gate 603a mehrere Eingaben aus allen X-OR-Gates 602a der
Vergleichseinheit 602 auf. Wenn die Anzahl der Register 601a ungerade
ist, wie in 8 dargestellt, weist das NOR-Gate 603a eine zusätzliche
Eingabe aus dem mittleren Register 601a sowie die Eingaben
aus allen X-OR-Gates 602a der Vergleichseinheit 602 auf.
-
Wenn
alle Eingaben der Entscheidungseinheit 603 „0s" sind, dann ist der
empfangene CRC-Code fehlerfrei und eine „1" wird aus dem NOR-Gate 603 in
der Entscheidungseinheit 603 ausgegeben.
-
Eine
detailliertere Beschreibung des CRC-Code-Algorithmus gemäß den Ausführungsformen
der vorliegenden Erfindung wird nachstehend bereitgestellt.
-
Wie
früher
erwähnt,
lautet die Polynomdarstellung des CRC-Codes mit invertierten Paritätsbits C(X) = Xn-km(X) + p1(X)worin unter der Annahme, dass p(X)
= Xn-km(X) mod g(X), p1(X)
definiert wird als p1(X)
= Xdegp(X)p(X-1).
-
Worin
Xn-km(X) mod g(X) = p(X) und p1(X) mod g(X) = p1(X),
(∴ deg
p1(X) < deg
g(X). folglich ist c(X) mod g(X) = p(X)
+ p1(X)
= (p0 +
pn-k-1) + (p1 +
Pn-k-2)X + ... +
+ ... + (pn-k-2 + p1)Xn-k-2 +
(pn-k-1 +
p0)X
-
Aus
der letzten Gleichung ist ersichtlich, dass die Koeffizienten des
Restpolynoms des CRC-Code-Polynoms c(x) dividiert durch das Generatorpolynom
g(x) symmetrisch gebildet werden. Wenn folglich der Restbitstrom
in Hälften
aufgeteilt wird und der eine halbe Bitstrom mit dem anderen halben
Bitstrom bitweise vergleichen wird, nachdem die Bits des anderen
halben Stroms in umgekehrter Reihenfolge sequentialisiert worden
sind, dann muss jede der zwei Eingaben, die mit jedem der X-OR-Gates 602a verbunden
sind, die gleiche sein, sofern kein Übertragungsfehler in dem empfangenen CRC-Code
aufgetreten ist. Folglich geben alle X-OR-Gates 602a „0" aus und die Bestimmungseinheit 603 gibt
dementsprechend „1" aus, um einen fehlerfreien
CRC-Code anzugeben.
-
Wenn
indessen, wie in 8 dargestellt, die Anzahl der
Restbits von c(x) dividiert durch g(x) ungerade ist, ist aus der
letzen Gleichung ersichtlich, dass der Koeffizient des mittleren
Ausdrucks des Restes zu einer Summe der zwei gleichen Zahlen wird.
-
Das
heißt,
der mittlere Ausdruck des Restpolynoms wird zu (p(n-k-1)/2 +
p(n-k-1)/2)X(n-k-1)/2 (worin
n-k eine ungerade Zahl ist).
-
Da
das Addieren der zwei gleichen Zahlen, wie oben erwähnt, zu „0" in dem binären Galois-Feld führt, wird
der Koeffizient des mittleren Ausdrucks des Restes normalerweise
zu „0". Da folglich der
Koeffizient des mittleren Ausdrucks des Restes immer zu „0" wird, sofern in
dem empfangenen CRC-Code kein Übertragungsfehler
auftritt, werden alle Eingaben in das NOR-Gate 603a zu „0" und dementsprechend
gibt die Bestimmungseinheit 603 „1" aus, um einen fehlerfreien CRC-Code anzuzeigen.
-
Gemäß der dritten
Ausführungsform
der vorliegenden Erfindung ist es nicht notwenig, die Schalteinheit 401 oder 501 zum
Schalten des Nachrichtenbitstroms und des Paritätsbitstroms getrennt bereitzustellen,
und folglich wird die CRC-Code-Fehlererkennungsvorrichtung
simpler und kompakter als in der ersten und der zweiten Ausführungsform.
-
Im
Vergleich zu der Vorrichtung, die in 4 dargestellt
ist, umfasst die Vergleichseinheit 602 ferner weniger X-OR-Gates 602a und
folglich wird die Konfiguration der Fehlererkennungsvorrichtung
noch einfacher.
-
Außerdem besteht
im Vergleich zu der zweiten Ausführungsform
aus 5 nicht die Notwendigkeit, die Schalteinheit 501 mit
den Vorwärts-
und Rückwärtsverschiebungsschaltern 503a und 503b zusammenwirken
zu lassen. Es ist auch möglich,
die vorliegende Erfindung durch einfaches Benutzen einer herkömmlichen
Bestimmungseinheit ohne die Benutzung des bidirektionalen Verschiebungsregisters
umzusetzen. Folglich wird die Struktur einfacher. Im Vergleich zu
der zweiten Ausführungsform
aus 5, welche das sequentielle gesamte bitweise Vergleichsschema
anwendet, stellt die dritte Ausführungsform
ein schnelleres Vergleichsschema bereit, um Zeit zur Fehlererkennung
zu sparen.
-
Gemäß der vorliegenden
Erfindung stellen die hierin beschriebene Vorrichtung und das Verfahren
zur Erkennung von CRC-Code-Fehlern insofern Vorteile bereit, als
sie die Übertragungsfehler
während
des Entschlüsselns
des empfangenen CRC-Codes bei dem Empfänger effektiv erkennen, wobei
der CRC-Code die
Paritätsbits
aufweist, die nicht durch die herkömmlichen, normal angeordneten
Restbits geschaffen werden, sondern durch invertierte Restbits der
Nachrichtenbits, dividiert durch das Generatorpolynom.
-
Obwohl
wenige bevorzugte Ausführungsformen
dargestellt und beschrieben worden sind, wird der Fachmann zu schätzen wissen,
dass verschiedene Veränderungen
und Modifikationen vorgenommen werden können, ohne den Schutzbereich
der Erfindung, wie in den beigefügten
Ansprüchen
definiert, zu verlassen.