DD201957A5

DD201957A5 - Verfahren zur fehlerkorrektur

Info

Publication number: DD201957A5
Application number: DD81231938A
Authority: DD
Inventors: Yoichiro Sako; Kentaro Odaka
Original assignee: Sony Corp
Priority date: 1980-07-18
Filing date: 1981-07-20
Publication date: 1983-08-17
Also published as: SE461620B; FR2491278B1; GB2081479A; KR860000500B1; NL8103426A; ES504085A0; DE3128599C2; SE462607B; SE8104418L; NL191002C; ES8205089A1; ATA314981A; NL9400376A; CA1170776A; US4476562A; AU541864B2; DK162862B; NL191002B; DK321481A; AU7310681A

Abstract

Ziel und Aufgabe der Erfindung bestehen darin, ein Verfahren zur Fehlerkorrektur zu schaffen, das es ermoeglicht, Fehler mit hoher Geschwindigkeit zu korrigieren. Das erfindungsgemaesse Verfahren enthaelt folgende Schritte:- Bildung von k Syndromen S tiefo bis S tief k-1 durch die nachfolgende Berechnung eines Blocks V hoch T aus n empfangenen Woertern und einer Paritaetspruefmatrix H,worin die Paritaetspruefmatrix H aus n Spalten und k Zeilen besteht und in der jedes Element einer vorbestimmten Zeile ausgewaehlt wird aus alpha Grad (=1) bis alpha HOCH 2m-1 und worin das Element alpha eine Wurzel ist,die das Polynom F(x)=O befriedigt,wenn F(x) ein irreduzibles Polynom auf einem Galoisfeld GF(2) ist,so dass der gleiche Wert in der vorbestimmten Zeil e nicht zweimal erscheint;-Bildung der Konstanten A,B und C auf der Grundlage der Syndrome;-Ausfuehrung des Fehlernachweises und der Fehlerkorrektur mittels der Syndrome und Konstanten. Matrix H u.

Description

Berlin, 3* 3» 1982

59 559 /13

Verfahren zur Fehlerkorrektur

Anwendungsgebiet der Erfindung

Die vorliegende Erfindung bezieht sich allgemein auf ein Verfahren zur Fehlerkorrektur,

Charakteristik der bekannten technischen Lösungen

Es ist bereits ein für die Korrektur von Fehlerburts wirksaines Datenübertragungssystem unter Benutzung der sogenannten Zweirichtungsverflechtung ("cross-.interleave"-Technik) vorgeschlagen worden, und zwar in der.Offenlegungsschrift Nr, 218 256 vom 19, Dezember 1980 des gleichen Inhabers» Bei dieser cross-interleave-Technik sind Wörter einer POM-Datensignalfolge in Mehrfachfolgen oder Mehrfachkanälen vorgesehen, die in einem ersten Ordnungszustand geordnet sind und zur Erzeugung einer ersten Prüfwortfolge an einen ersten Fehlerkorrekturkodierer gebracht werden. Diese ersten Prüfwortfolgen und die PCM-Datensignalfolgen in den Mehrfachkanälen werden in einen zweiten Ordnungszustand umgewandelt. Sodann wird ein Wort im zweiten Ordnungszustand für jede der PCM-Datensignalfolgen in den Mehrfachkanälen an einen zweiten Fehlerkorrekturkodierer gebracht, um dort eine zweite Prüfwortfolge zu erzeugen, so daß dadurch eine Doppelverflechtung (d, h. eine zweifache Umordnung) für jedes Wort vorgenommen wird. Der Zweck dieser Doppelverflechtung besteht in der Verminderung der Anzahl der fehlerhaften Wörter in jeder Wortgruppe, die in einem.gemeinsamen Fehlerkorrekturblock enthalten ist, wenn das in einem solchen Fehlerkorrekturblock enthaltene Prüfwort und die zugehörigen PCM-Daten verteilt und übertragen werden. Auf der Empfangsseite werden sämtliche fehlerhaften Wörter zwischen die verschiedenen Blöcke verteilt und in deren Originalzu-

3. 3* 1982 319 3 8 6 59 559 /!3

stand übergeführt. Mit anderen V/orten, ein Fehlerburst kann, wenn er im Verlaufe der Übertragung entsteht, verteilt wer-. den. Wird die voranstehend beschriebene Verschachtelung zweimal durchgeführt, werden die ersten und zweiten Prüfwörter jeweils zur Korrektur von Wörtern jeweils in verschiedenen Fehlerkorrekturblöcken verwendet, Damit kann ein Fehler, selbst wenn er von einem ersten und einem zweiten Prüfwort nicht korrigiert v/erden kann, durch andere Prüfwörter korrigiert werden, .Diese Technik bietet einen erheblichen Vorteil bezüglich der Pehlerkorrekturfähigkeit von Fehlerbursts*

Wenn jedoch nur ein einziges Bit in einem Wort als fehlerhaft erkannt wird, wird das gesamte Wort als fehlerhaft bezeichnet, ?/enn daher ein empfangenes Datensignal eine verhältnismäßig große Zahl von statistischen Fehlern aufweist, so ist das genannte Verfahren der Doppelverflechtung zur Korrektur dieser zufälligen Fehler nicht immer ausreichend.

Wenn jedoch zwei Wortfehler zu korrigieren sind, da der Fundamentalalgorithmus der Fehlerkorrektur derart ist, daß durch Anwendung des Syndroms bereits beim ersten Schritt geprüft wird, ob ein Fehler vorliegt oder nicht, so wird beim zweiten Schritt geprüft, ob der Fehler ein Einwort-· fehler ist oder nicht,, und beim dritten Schritt wird geprüft, ob es sich bei diesem Fehler um zwei Wortfehler handelt oder nicht, wobei die für die Abarbeitung sämtlicher Schritte erforderliche Zeit verhältnismäßig lang ist und insbesondere das Problem in Erscheinung tritt, wenn die Fehlerstellen von zwei Wortfehlern berechnet werden.

3. 3. 1982 59 559 /13 - 3 -

Ziel der Erfindung

Ziel der Erfindung ist es, ein verbessertes Verfahren zur Fehlerkorrektur zu schaffen, mit dem das Problem der bisherigen Technik gelöst wird und durch das der Aufbau von Rechenschaltungen und anderer Hardware, die in einer Fehlerkorrekturvorrichtung verwendet werden, vereinfacht werden kann»

Darlegung des Wesens der Erfindung

Der Erfindung liegt die Aufgabe zugrunde, ein Verfahren zur Fehlerkorrektur vorzustellen, das es ermöglicht, Fehler mit hoher Geschwindigkeit zu korrigieren.

Es wird vorgeschlagen, daß ein Fehlerkorrekturkode mit einer hohen Fehlerkorrekturkapazität, beispielsweise ein Reed-Solomon (RS-Code), Bose-Chauduri-Hocquendem (BCH-Code), oder eine Variante eines b-angrenzenden Kodes, mit dem K Wortfehle.r, z. B, zwei Wortfehler in einem Block und ebenfalls M Wortfehler korrigiert werden können, z, B. drei oder vier Wortfehler, wenn die Stelle der Fehler bekannt. ist, - kombiniert wird mit der voranstehend beschriebenen Mehrf a chve rf 1 e c.htung st e chnik,

Mit diesem Fehlerkorrekturkode wird es möglich, den Aufbau eines Dekodierers zu vereinfachen, wenn lediglich ein einziger Wortfehler zu korrigieren ist.

Gemäß einem Aspekt der vorliegenden Erfindung wird ein Verfahren zur Fehlerkorrektur von Daten vorgeschlagen, die aus η Wörtern in einem Block und jeweils m Bits in einem Wort bestehen, wobei das Verfahren die folgenden Schritte umfaßt

231938 6

3. 3- 1932 59 559 /13

Bildung von k Syndromen S bis S₁ _Λ durch die nachfolgende

O rn jC"" I

Berechnung eines Blocks V^x aus η empfangenen Wörtern und einer Paritätsprüfmatrix H

H . V

S₁

worin die Paritätsprüfmatrix H aus η Spalten und k Zeilen besteht und in der jedes Element einer vorbestimmten Zeile ausgewählt wird aus oC° (=1) bis oC ^m -1 und worin das Element oCeine Wurzel ist, die das Polynom P(x)=o befriedigt, wenn P(x) ein irreduzibles Polynom auf einem Galoisfeld GF(2) ist, so daß der gleiche Wert in der vorbestimmten Zeile nicht zweimal erscheint, und worin die Elemente · in den verbleibenden Zeilen mit einer vorgegebenen Potenz für alle Elemente in der jeweiligen Zeile ausgewählt werden, von entsprechenden Elementen in der vorbestimmten Zeile;

Bildung der folgenden Konstanten A, B und C auf der Grundlage der Syndrome

3. 3. 1982 59 559 /13

B.

^So^S2

S₁S₂

S₁S₃

S₂S₃

^S2^S4

^So^S3 2

« 2

^Sk-4^Sk-2

k-3 ~ k-3' c-3 ^{= S}k-3^S^-

^Sk-3²

^Sk-4^Sk-1

^sk-2²

und

Ausführung des Pehlernachweises und der Fehlerkorrektur, die nachstehend auf der Grundlage der Syndrome und Konstanten unter (a), (b) und (c) dargelegt werden:

(a) wenn S_Q = S^ = A_k.₃ = 0 ,

= 0 und.

= 0

erfüllt sind, wird festgestellt, daß kein Fehlerwort vor handen ist;

(b) wenn S_Q Φ- /, S₃ ?έ 0, S₄ ji 0, -... S^₁ φ 0, A_k = 0,

B_k = 0 mit k = 1 bis k-3 und.Cj- = 0 erfüllt sind, wird entschieden, daß es einen Einwortfehler gibt und die Fehlerkorrektur durch Berechnung der Syndrome vorgenommen wird und

231938 6

3. 3. 1982 59 559 /13 -βwenn A, £ O, B, j£ 0 und C, ~ ^ O erfüllt sind, werden die folgenden Beziehungen vorausgesetzt:

-3 = ^D>

*-3 ^{= E)}

und die Fehlerstellengleichung von

OC²¹ + DOC¹ + E = 0

wird gelöst, um die Fehlerstellen i und j festzustellen und zwei Wortfehler zu korrigieren.

Au sf ührungsbe i spi e1

Die Erfindung wird in einem Ausführungsbeispiel an Hand der beigefügten Zeichnung näher erläutert. Darin zeigen:

Fig. 1: ein Blockschaltbild eines Ausführungsbeispieles einer Fehlerkorrektureinrichtung, in der die Erfindung angewendet wird;

Fig. 2: (bestehend aus den Fig. 2A und 2B) ein Blockschaltbild eines Ausführungsbeispieles eines Fehlerkorrekturkodierers, in der die Erfindung angewendet wird;

Fig. 3: eine Anordnung eines Blocks kodierter Daten bei der Übertragung;

Fig. 4: (bestehend aus den Fig. 4A und" 4B) ein Blockschaltbild eines Ausführungsbeispiels eines Fehlerkorrekturdekodierers, in dem die Erfindung angewendet wird;

Fig. 5j 6 und 7: Diagramme zur Erklärung der Funktion des Fehlerkorrekturdekodierers,

3. 3. 1982

Zunächst wird ein Fehlerkorrekturkode erklärt, der in der vorliegenden Erfindung verwendet'.wird. In dieser Beschreibung wird der Fehlerkorrekturkode durch eine Vektordarstellung oder durch die Darstellung einer zyklischen Gruppe formuliert«,

Zuerst wird ein irreduzibles Polynom m-ter Ordnung F(x) auf einem Galoisfeld GF(2) betrachtet, Auf dem Feld GF(2), das lediglich die Elemente "0" und "1" enthält, besitzt das irreduzible Polynom F(x) keine reale Wurzel, Daher soll eine imaginäre (oder komplexe) Y/urzel oc betrachtet v/erden, die das Polynom F(x) = 0 befriedigt. Hierbei bilden 2^m verschiedene Elemente 0, o£, oC , OC , ... oC^2m"" , die jeweils eine Potenz von c< sind und ein Null-Element enthalten, ein erweitertes Galoisfeld GF(2^m). Dieses erweiterte Feld FG(2^m) ist ein Polynomring mit einem irreduziblen Polynom F(x) m-ter Ordnung über dem Feld GF(2) als Modulo, Das Element von GF(2^m) kann als eine lineare Kombination von 1, CX= Bd\ Ok² = [-κ²] ... a^m~¹ = /x^m~¹7 dargestellt werden, Diese Elemente können damit folgendermaßen ausgedrückt werden:

a_Q + a(x) + a(x²) + + ^a^^xm""

oder

^am-2'

worin ag, a^ »»» ^am-1 ^zu ^ ^²^ gehören,

Als ein Beispiel wird .das Erweiterungsfeld GF(2 ) und als

8 4-3? Modulo das Polynom F(x) = χ + χ + χ + χ +1 (sämtliche Variablen stellen 8-Bit-Daten dar) betrachtet. Dieses Feld

231938 6

3* 3* 1982 59 559/13

GP(2 ) läßt sich folgendermaßen ausdrücken:

a^x oder

a_cx

a_ox 2

j 3g }S[- j S λ j So )3p ^)a"! »^an

Durch dieses Beispiel wird daher a₇ als das Bit höchster Ordnung (MSB) betrachtet und a₀ als das Bit niedrigster Ordnung (LSB), Da a zu GF(2) gehört, sind seine Elemente entweder 0 oder 1,

Ferner wird vom Polynom F(x) die folgende Matrix T mit m Zeilen und m Spalten abgeleitet:

T =

0	0
1	0
0	1

0 0 O

^a1

0 0

in-1

Andernfalls läßt sich zu dieser Darstellung ein Ausdruck verwenden, der eine zyklische Gruppe enthält und in dem berücksichtigt wird, daß der Rest des Galois'sehen Erweiterungsfeldes GF(2^m) (mit Ausnahme des Null-Elements) eine Vervielfachende Gruppe vom Grade 2^m-1 bildet. Wenn die Elemente aus GF(2^m) mittels einer zyklischen Gruppe dargestellt werden, so erhält man folgenden Ausdruck:

0, 1 (=

, od , oC , cLr , ... οο

In einem Beispiel der vorliegenden Erfindung werden auf der Grundlage einer Paritätsprüfmatrix H k Prüfwörter er-

3. 3. 1982 59 559 /13

zeugt, wenn m Bits ein Wort und η Wörter einen Block bilden:

H =

oC2(n~1)

1-2 oC2(n-2

Darüber hinaus läßt sich, die Prüfrnatrix H bei "Verwendung der Matrix T in ähnlicher Weise folgendermaßen darstellen:

n-1

_?n-2 ^(n-2)

0 * -L

(k-1)(n-2)

Darin ist I eine Einheitsmatrix mit m Zeilen und m Spalten^ Wie bereits erwähnt, sind die Ausdrücke unter Ife^venctuüig der Y/urzel oC grundsatzlich dieselben wie bei Verwendung einer Erzeugungsmatrix T. .

Wenn ferner als Beispiel der Fall von vier (k=4) Prüfwörtern genommen wird, erhält die Prüfmatrix H folgende Gestalt:

H =

n-1

2(n-1) 3(n-1)

n-2) 3(n-2)

231 938

3, 3. 1982 59 559 /13

- 10 -

In diesem Pall, wenn ein einzelner Block empfangener Daten als Spaltenvektor

= (W_n-1, S_n-2, ... W₁, W₀).

mit Wi = Wi + ei ausgedrückt wird und ei ein Fehlermuster ist, lassen sich vier Syndrome S , S₁, Sp und S-, die auf der Empfangerseite erzeugt v/erden, folgendermaßen ausdrücken

^So S₁

= H . V^J

DieserFehlerkorrekturkode kann bis zu zwei Wortfehler in einem Pehlerkorrekturblock und ebenfalls drei Wortfehler oder vier Wortfehler korrigieren, wenn die'Fehlerstelle bekannt ist.

In. jedem Block gibt es vier Prüfwörter

(p = W₃ , q = W

r = W₁ , s = W_Q ).

Diese PrüfWörter können aus den folgenden Beziehungen erhalten werden:

<C³p

r oCr

s = i_ Wi

s = JoC¹Wi

=JX³ⁱw.i

n-

wobei L ist I , Wird der Berechnungsvorgang wegge-

1=4

lassen, so kann das Ergebnis folgendermaßen ausgedrückt werden:

31

-U-

<2¹² cc153 ^152 ^209 <2 ^135

3. 3. 1982 59 559 /13

a" b c d

Der auf der Übertragimgsseite vorgesehene Kodierer hat die PrüfWörter p, q, r und. s in der voranstehend dargelegten Weise zu bilden.

Als nächstes wird der fundamentale Algorithmus der Fehlerkorrektur beschrieben, wenn Daten, einschließlich der Prüfwö'rter, die in der voranstehenden ?/eise erzeugt werden, übertragen und empfangen werden.

(1) Die Syndrome sind alle Null, wenn kein Fehler vorhanden ist:

S₀ =

= S₃ = 0

(2) Bei Vorhandensein eines einzigen Wortfehlers (ein Fehlermuster wird als ei dargestellt) wird:

S_n = ei , S₁ se^ei , S_p = ^ei , S =

3i„,

ex.

Damit ergeben sich folgende Beziehungen:

= S

Ob ein einziger Wortfehler vorliegt oder nicht kann dadurch beurteilt werden, ob die voranstehende Beziehung zutrifft oder nicht, wenn i nacheinander verändert wird, Nachstehend wird die Beziehung aufgestellt:

19 38 6 ³·³·¹⁹⁸²

59 559 /13 - 12 -

TU ά I J d

Folglich wird das Muster von oC¹ mit dem zuvor in einem ROM (Lesespeicher) eingespeicherten Muster zur "Erkennung der Fehlerstelle i verglichen. Gleichzeitig wird das Syndrom Sq das Fehlermuster ei selbst.

(3) Liegen zwei Wortfehler (ei und ej) vor, folgen die Syndrome den Beziehungen:

5₀ = ei + .ej

5₁ = od ^eI

5₂ = <²ⁱei

5₃ =

Die voranstehenden Gleichungen lassen sich folgendermaßen modifizieren:

OC¹S_n +S₁ = (<*3 +<Ki) ei

+ S₂ od^x (öd" +c<J) ei

+ S₃ =06 (oC +oCi^) ei „

Wenn die folgenden Gleichungen aufgestellt werden können, lassen sich dementsprechend zwei Wortfehler unterscheiden;

^s₀ + S₁) = 06^s₁ + S₂ ^s₁ + S₂) = ^s₂ + S₃

Sind die voranstehenden Gleichungen aufgestellt, so werden zwei Wortfehler angenommen. Das bedeutet, daß die Kombination von i und j verändert wird, um zu prüfen, ob die Beziehung der obigen Gleichungen erfüllt ist oder nicht.

3*, 3« 1982

2 3 19 3 8 6 59 559 /13

- 13 -

Somit v/erden die Pehlermuster diesmal folgendermaßen ausgedrückt :

οι -, . O 1

ei = 3—ξ— und e.i =

(4) Bei Auftreten von drei Wortfehlern (ei, ej und ek) werden die Syndrome folgendermaßen dargestellt:

f e,i + ek

⁸O	= ei
^S1	= cd-el
^S2	= o6²¹ei
^S3	= <³ⁱei

Die voranstehenden Gleichungen lassen sich wie folgt modifizieren:

+c6^k)ei

Dementsprechend lassen sich die folgenden Gleichungen ableiten:

⁰^ fel^kS₀ + S₁) + (A₁ + S₂) = (<? +(XJ)(OC¹ +cd^c)ei

₁ + S₂) + GA₂ + S₃) ^^(«C¹ +0Ob(CC¹ +oC^k)ei,

Wenn daher die folgende Gleichung erfüllt ist, die für drei Wortfehler eine' notwendige Bedingung darstellt, lassen sich drei Wortfehler unterscheiden,

u.^ks_Q + S₁ )+Cc?C^ks₁ + S₂)] =oC^:JGC^cs₁+s₂)+(_oc^ks₂ + S₃)

3- 3. 1982

19 38 S 59 559/13

- 14 -

Die jeweiligen Fehlermuster werden diesmal folgendermaßen ausgedrückt: . _v

ei =

(Ί

S₀ + &T^k + «Γ¹) S₁

ek =

(1

Tatsächlich ist der Aufbau einer Schaltung für die Korrektur von drei Wortfehlern außerordentlich kompliziert und die für die Korrektur erforderliche Zeit ist lang. Daher wird in der Praxis ein Verfahren der Fehlerkorrektur verwendet, bei dem die voranstehende Operation mit einem Fehlerkorrekturverfahren kombiniert wird, bei dem die Fehlerstellen i, j, k und 1 durch ein Fehleranzeigebit.oder eine Fehleranzeigeadresse bekannt sind und die voranstehenden Gleichungen für die Prüfung angewandt werden,

(5) Wenn vier Wortfehler (ei, ej, ek und el) vorhanden sind, v/erden die Syndrome folgendermaßen dargestellt:

S₀ = ei + ej + ek + el

k + ^eI S^ =^^JJ-ei +öd-^^ej +oC^JiLek +cC³¹el

Die voranstehenden Gleichungen lassen sich folgendermaßen modifizieren:

³* ³* ¹⁹⁸² 59 559 /13

(1

\¥enn daher die Fehlerstellen (i, j, k, 1) durch Pehleranzeigeadressen dargestellt werden, läßt sich ein Fehler durch die obige Berechnung korrigieren.

Der grundlegende Algorithmus der obigen Fehlerkorrektur besteht darin, daß in einem ersten Schritt mittels der Syndrome Sq bis S-a geprüft wird, ob ein Fehler vorhanden ist oder nicht, während in einem zweiten Schritt geprüft wird, ob es sich um einen Einwortfehler handelt oder nicht, und im dritten Schritt wird geprüft, ob der Fehler ein Zweiwortfehler ist oder nicht. Wenn bis zu zwei Wortfehler korrigiert werden, wird die für alle Schritte erforderliche Zeit sehr lang, was besonders dann zu einem Problem wird, wenn die Fehlerstelle von zwei Wortfehlern gebildet wird.

Es v/ird nun ein modifizierter Algorithmus beschrieben, der sehr wirksam ist, wenn die Korrektur von zwei Wortfehlern angenommen v/ird, ohne daß das obige Problem entsteht»

\ S3 O Ό 59 559 /13

Die Gleichungen der Syndrome Sq, S₁, Sp und S- im Fall-von zv/ei Wortfehlern (ei und ej) lauten folgendermaßen:

S_n = ei + ej

Die obigen Gleichungen werden wie folgt modifiziert:

₀ + S₁)(OC¹S₂ + S₃) = _{1 2}

Die Gleichung wird weiter modifiziert und das folgende Fehlerstellenpolynom gebildet:

(S₀S₂ + S₁ ²X²¹ + (S₁S₂ + S₀S₃) ed- + (S₁S₃ + s₂ ²) =0

Die Konstanten der jeweiligen Terme des obigen Polynoms werden jetzt wie folgt vorausgesetzt:

S₀S₂ + S₁ ² = A

^S1^S3 ^{+ S}2 = C .'

Durch Verwendung der obenstehenden Konstanten A, B und C kann die Fehlerstelle von zwei Wortfehlern gebildet werden

(1) Im Falle keines Fehlers:

A=B=C=O , S₀ =0 und S₃ = 0.

3, 3* 1982

(2) Bei einem Einwortfehler gilt:

Wenn die Bedingung A = B = G = O, S_Q^0 und S^ j£ 0 befriedigt ist, wird der Fehler als Einwortfehler an genommen. Aus der Beziehung

kann die Fehlerstelle i leicht .bestimmt werden, Damit wird der Fehler bei Verwendung der Beziehung ei = S₀ korrigiert,

(3) Bei zwei Wortfehlern gilt:

Wenn ein Fehler in mehr als zwei Worten auftritt, werden A Φ 0, B^O und C^O erfüllt und die Entscheidung wird damit recht einfach.

Dabei wird die folgende Gleichung aufgestellt:

M?²- + Bo6 + C = 0 ,

darin ist i = 0 bis (n-1).

Wenn vorausgesetzt wird, daß B/A = D und C/A = E, werden die folgenden^Gleichungen gebildet:

D = o6 + et¹

Ξ =oO -ei? .

Somit wird die folgende Gleichung abgeleitet:

Wenn die Differenz zwischen den zwei Fehlerstellen als t angenommen wird, d» h. j = i + t, werden die folgenden Gleichungen gebildet:

3. 3- 1982

23 19 3 8 6 59 559 /13

-18-

D = οβ- (1 + ο<ί) E = oC²ⁱ + t . "

Daher läJ3t sich folgende Gleichung ableiten:

D² (1 + ei?)² t V = oC + oC ·

E od*

Wenn der Wert von oC~ + ⁰^ für jeden Wert von t = 1 bis (n-1) zuvor in einen ROM eingeschrieben und festgestellt wird, daß der Wert mit dem Wert von D /E übereinstimmt, der vom Ausgang des ROM und einem empfangenen Wort errechnet wird, kann t erhalten v/erden. Wird eine solche Übereinstimmung nicht festgestellt, bedeutet dies, daß die Fehler in mehr als drei Worten auftreten.

Wenn daher die folgenden Ausdrücke vorausgesetzt werden, X = 1 + ⁰O Y = 1 + «C* = D²/E + X ,

so können die folgenden Ausdrücke gebildet werden:

⁰⁶¹ = D/X oO - D/Y ,

Aus den obigen Gleichungen werden die Fehlerstellen i und j gebildet. Sodann lassen sich die Fehlermuster ei und ej folgendermaßen darstellen:

3. 3. 1982

19 38 6 59 559/13

- 19 -

*?₀ + s)

ei = ϊ !_ = S_o/Y +

+ S₁) ¹

D Polglich können die Fehler korrigiert werden.

Der obige modifizierte Korrekturalgorithmus kann die zur Berechnung der Fehlerstelle bei der Korrektur von zwei Wortfehlern im Vergleich zum fundamentalen Algorithmus erforderliche Zeit wesentlich verkürzen.

Wenn darüber hinaus die Zahl der Prüfwörter k. erhöht wird, läßt sich die Pehlerkorrekturkapazität dementsprechend verbessern. Wird beispielsweise für k der Wert 6 gewählt, können drei Wortfehler korrigiert werden und sechs Wortfehler können korrigiert werden, wenn die Fehlerstelle bekannt ist.

Fig. 1 zeigt ein Beispiel für eine Fehlerkorrekturvorrichtung, bei der die vorliegende Erfindung angewandt wird. In dieser Fig. bezeichnet 1' einen Eingang, zu dem die empfangenen Daten geführt v/erden. Sodann werden die Daten zu einem Pufferspeicher 2 geführt und zu einer Schaltung 3> die ein Syndrom bildet. Der Pufferspeicher 2 dient zur Verzögerung der empfangenen Daten um die Zeit, die zum Nachweis eines Fehlers und der Erzeugung eines Fehlermusters erforderlich ist. Der Ausgang·dieses Speichers ist: mit der Fehlerkorrekturschaltung 4 (ein Addierer des Modulo 2) verbunden. Der Ausgang der Fehlerkorrekturschaltung ist zur Ausgangsklemme 5 geführt.

3 19 3 8 6 59 559 /13

In der Syndromerzeugungsschaltung 3 wird d^e Berechnung von

H · V zur Bildung der Syndrome S₀, S^, S_? und So vorgenommen, die in die Be rec.hnungs schaltung 6 für das Galoisfeld GP 2^m gegeben werden. Die Berechnungsschaltung 6 übernimmt derartige Berechnungen, daß die Konstanten A, B, C, D und E und ebenfalls die Fehlermuster erzeugt werden» Die Konstanten der Be rec.hnungs schaltung 6 werden auf ein Pufferregister 7 gegeben und dort gespeichert, und die Fehlermuster aus der Berechnungsschaltung β werden zu einem Pufferregister 8 geführt und dort gespeichert. Das Fehlermuster wird vom Pufferregister 8 an die Fehlerkorrekturschaltung 4 zur Ausführung der Fehlerkorrektur geführt. Im Beispiel der Fig, 1 werden ein Fehlerstellendekodierer 9 und ein ROH (Lesespeicher) 10 vorgesehen.

Die Konstanten D und Ξ vom Pufferregister 7 und die Ausgänge oC und oC vom ROM 10 werden insgesamt an den Fehlerstellendekodierer 9 gelegt, der dann die Fehlerstelle i und neue Konstanten X und Y liefert. Die neuen Konstanten X, Y, die Konstante D des Pufferregisters 7 und die Syndrome werden der Berechnungsschaltung 6 zugeführt, so daß die Schaltung 6 die Fehlermuster ei und ej erzeugt, die in das Pufferregister 8 zur Speicherung eingegeben werden.

Die Syndrome S₀ und S., von der Synd r omer ζ eugung s schaltung 3 und die Konstanten A, B und C aus dem Pufferregister 7 werden an eine Fehlerbewertungsschaltung 11 gegeben, die feststellt, ob ein Fehler vorhanden ist oder nicht, ob ein Fehler ein Einwortfehler ist oder nicht, ob der Fehler ein Zweiwortfehler ist oder niht und der Fehler mehr als zwei Wortfehler darstellt. Das erhaltene Resultat wird von dort an eine Steuerschaltung 12 gegeben. Diese Steuerschaltung 12 dient zur Lieferung von Taktimpulsen oder Steuersignalen, die auf eine vorbestimmte Zeitbeziehung für die jeweiligen Schaltungen beschränkt werden.

3-3* 1982

19 3 8 6 ^{59 559 /13}

Aus der voranstehenden Beschreibung der vorliegenden Erfindungwird offensichtlich, daß die Werte von aCt und ⁰C wobei t = 1 bis (n-1) ist,vom ROM 10 gespeichert werden und der Ausgang vom ROM 10 mit der durch Berechnung des Syndroms erzeugten Konstanten verglichen wird, um den lachweis von zwei Wortfehlern und der Fehlerstelle vorzunehmen, so daß der Pehiernachweis und die Fehlerkorrektur mit hoher Geschwindigkeit durchgeführt werden können.

Ein praktisches Ausführungsbeispiel der vorliegenden Erfindung, das in einer Vorrichtung zur Aufnahme und Wiedergabe eines PCM-Audiosignals verwendet wird, soll nun unter Bezugnahme auf die beigefügten Zeichnungen beschrieben -werden,

Fig. 2 zeigt als Ganzes einen Fehlerkorrekturkodierer, der in einem Aufnahmesystem vorgesehen ist, an den ein PCM-Audiosignal als Eingangssignal gegeben wird. Das PCM-Audiosignal wird derart zugeführt, daß die linken und rechten Stereosignale mit einer Abtastfrequenz f_ (beispielsweise 44,1 kHz) abgetastet werden und jeder abgetastete Wert in ein Digitalwort umgewandelt wird (das beispielsweise in eine 16-Bit-Zahl in Zwei-Komplementdarstellung umgesetzt wird). Entsprechend werden für den linken Kanal des Audiosignals PCM-Datenwörter Lq, L₁, L_? ... und für den rechten Kanal PCM-Datenwörter R_Q, R.., R_? ... gebildet, Die PCM-Datenwörter der linken und rechten Kanäle v/erden in jeweils sechs Kanäle getrennt; somit werden insgesamt zwölf Kanäle von PCM-Datenfolgen dem Fehlerkorrekturkodierer zugeführt. Zu jedem vorgegebenen Zeitpunkt werden beispielsweise zwölf Wörter L_6n, Rg_n, Lg_n+1, Rg_n+1, Lg_n+2, Rg_n+2, Lg_n+3, Rg_n+3, ^L6n+4' ^R6n+4' ^L6n+5' ^R6n+5 ^{in den} ^alever gegeben. In dem dargestellten Beispiel wird jedes Wort in acht bedeutsamere Bits und acht weniger bedeutsame Bits eingeteilt und die zwölf Kanäle damit wie 24 Kanäle verarbeitet. Aus Gründen

3.3* 1982

23 19 3 8 6 59 559/13

- 22 -

der Einfachheit wird jedes einzelne Wort der PCM-Daten als Wi bezeichnet, wobei die acht höheren Bits als Wi,A und die unteren acht Bits als Wi,B bezeichnet werden. Beispielsweise wird das Wort Lg in zwei Wörter geteilt:

,A - W_12n,B .

Die PCM-Datenfolgen von 24 Kanälen werden zunächst auf eine Gerade-Ungerade-Verschachtelungseinrichtung 1 gegeben. Wenn η eine ganze Zahl 0, 1, 2 ... ist, so sind die Wörter Lg (d. h. W_12n,A und W_12n,B), Rg_n (d. h. W_12n+1,A und

^(d' ^h' ^W12n₊₄'^A ^ ^W12m4'^B)' ^R6n₊2 ^(d* ^h ,Α-und W_12n+5,B), Lg_n+4 (d. h. W_12n+8,A und W_12n+8,B)

und Rg_n+4 (d. h. ^w-|₂n+9'^{A und W}12n+9'^B^ J^ei/reils Wörter mit geradzahliger Rangordnung, während die verbleibenden Wörter jeweils Wörter ungeradzahlier Rangordnung sind. Die PCIvI-Datenfolgen, die aus Wörtern geradzahliger Rangordnung bestehen, v/erden um ein einziges Wortintervall mittels der Laufzeitschaltungen oder Laufzeitleitungen 22A, 22B, 23A, 23B, 24A, 24B, 25A, 25B, 26A, 26B, 27A und 27B der Gerade-Ungerade-Verschachtelungseinrichtung 1 verzögert. Selbstverständlich ist es möglich, Wörter um mehr als ein Wort zu verzögern, z. B. acht Wörter. Ferner v/erden in der Gerade-Ungerade-Verschachtelungseinrichtung 1 die aus Wörtern geradzahliger Rangordnung begehenden zwölf Datenfolgen so umgewandelt oder verschoben, daß die ersten zwölf Übertragungskanäle belegt v/erden, während die aus Wörtern ungeradzahliger Rangordnung bestehenden zwölf Datenfolgen so umgewandelt werden, daß sie jeweils die Übertragungskanäle 13 bis 24 belegen.

Die Gerade-Ungerade-Verschachtelungseinrichtung 1 hat die

3* 3» 1982 59 559 /13 23 -

Aufgabe zu verhindern, daß mehr als zwei aufeinanderfolgende Wörter der jeweiligen linken bzw. rechten Stereοsignale falsch sind; in diesem EaIl ist es nahezu unmöglich, die Fehler zu korrigieren.

Um den Vorteil dieses Merkmals zu veranschaulichen, werden als Beispiel drei aufeinanderfolgende Wörter Li-1, Li und Li + 1 betrachtet» Wenn das Wort Li fehlerhaft und nicht korrigierbar ist, so ist es äußerst wünschenswert, daß beide benachbarten Wörter Li-1 und Li+1 richtig sind, Der Grund hierfür besteht darin, daß zur Kompensation eines nichtkorrigierbaren, fehlerhaften Wortes Li dieses Wort zwischen dem vorangegangenen richtigen Wort Li-1 und dem folgenden Wort Li+1 interpoliert wird, indem in der Regel der Mittelwert von Li-1 und Li+1 gebildet wird. Die Laufzeitleitungen 22A, 22B, ... 27A und 27B der Gerade-Ungerade-Verschachtelungseinrichtung 1 sind so angeordnet, daß die benachbarten Wörter in verschiedenen Fehlerkorrekturblöcken erscheinen. Der Grund für das Zusammenfassen der Gruppen von Übertragungskanälen für die Wörter geradzahliger und ungeradzahliger Randordnung besteht darin, daß, wenn die Datenfolgen verschachtelt werden, der Abstand zwischen den Aufnahmepositionen der benachbarten Wörter geradzahliger und ungeradzahliger Rangordnung so groß wie möglich ist.

Am Ausgang der Gerade-Ungerade-Verschachtelungseinrichtung 1 erscheinen die Wörter der 24 Kanäle in einem ersten Ordnungszustand. Von .der Verschachtelungseinrichtung 1 werden die jeweiligen PCM-Datenwörter Wort für Wort an einen Kodierer 8 geführt, der sodann erste Prüfwörter Q-ipn' ^12n+1' ^19n+2 ^un<^ ^12+3 ^erzeuS^> ^w^^e ^ⁿ ^en oben angegebenen Ausdrücken p, q, r, s gezeigt wurde.

_ 3. 3. 1982

19 38 6 59 559/13

- 24 -

Danach kommt ein Fehlerkorrekturblock, der erste Prüfwörter enthält:

^(W12n-12'^{A; if}12n-12'^{B; W}12n+1-12'^{A; W}12n-M-12'^B;

W Δ · W "R · ¥/ A-W "R ·

^w12n+4-T2'^A' 12n+4-12'-°' ^w12n+5-12'^A' ^v12n+5-12* ' ^W12n+8-12,^{A; W}i2n+8-12,^{B; W}12n+9-12'^{A; W}12n+9-12'^B;

W A-W "R · W Δ · W "R ·

'Ί2η+2'^Α' ^w12n+2' ' 'Ί2η+3'^Α' 12η+3' ' ^W12n₊6>^A' ^W12n₊6'^B' ^W12n₊7'^{A; W}12n₊7'^B;

W Δ · W "R · W Δ · W "R ·

^w12n+10'^A' ^w12n+1O^sJ:5' ^W12n+1.1'^A» 12n+11'^ß' ^Q12n^{; Q}12n₊1¹ Q_12n+2; Q_13n+3) .

Der erste Kodierer 2S führt seine Funktion durch Berechnung der ersten PrüfWörter Q₁^_n bis Q^ori+3 entsprechend der Zahl der Wörter eines Blocks (n=28), der Bitlänge m jedes Y/Ortes (m=8) und der Zahl der Prüfwörter (k=4) aus.

Die 24 PGM-Datenwortfolgen und die vier Prüfwortfolgen werden sodann auf eine Yerschachtelungseinrichtung 29 gegeben. In dieser Verschachtelungseinrichtung 29 werden die relativen Positionen der Kanäle so verändert, daß die PrüfWortfolgen zwischen den PCM-Datenfolgen angeordnet sind, die aus Wörtern geradzahliger Rangordnung.bestehen und den PCM-Datenfolgen, die aus Wörtern ungeradzahliger Rangordnung bestehen, wonach ein Verzögerungsvorgang für diese Verschachte-lungsfolgen abläuft. Dieser Verzögerungsvorgang wird, beginnend mit dem zweiten Übertragungskanal, auf 27 Übertra™ gungskanälen mittels Laufzeitleitungen mit einem Verzögerungsbetrag von 1D, 2D, 3D, 4D ... 26D bzw. 27 D durchgeführt (wobei D eine Verzögerungseinheit darstellt)*

Am Ausgang der "ferschachtelungseinrichtung 29 erscheinen 28 Folgen von Datenwörtern in einem zweiten Ordnungszustand, Die Datenwörter werden Wort für Wort aus den jeweiligen Da-

3* 3» 1982 19 3 8 6 59 559 /13

- 25 -

tenfolgen genommen und an den Kodierer 30 gebracht, der dann die zweiten Prüfwörter ^_12n* ^p-]2n+1' ^P12n+2 ^und P₁₂ _ in der gleichen Weise bildet wie die PrüfWörter ^Q12n ^{bis Q}12n₊3'

Genau wie der .obige Kodierer 28 die ersten Prüfwörter entsprechend den Parametern n=28, m=8 und k=4 liefert, liefer der ähnliche Kodierer 30 die zweiten Prüfwörter entsprechend den Parametern n=32, m=8 und k=4.

Es wird ein Fehlerkorrekturblock gebildet, der die zweiten Prüfwörter enthält und aus 32 Wörtern wie folgt gebildet wird:

^(W12n-12'^{A ; W}12n-12(D+1)'^B ' ^W12n+1-12(2D+1)'^{A ;}

^W12n+1-12(3D+D'^{B 5}

^W12n+4-12(4D+1)^}A ' ^W12n+4-12(5D+1)^}B ' ^Wi2n+5-12(6D+1)'^{A ; W}12n+5~12(7D+1)'^B '>·"'> ^Q12n-12(12D) ' ^Q12n+1-12(13D)' ^Q12n+2-12(14D)' ^Q12n+3-12(15D) ' "* ^W12n+10-12(24D)'^A '

^W12n+10-12(25D)'^{B ; W}12n+11-12(26D)'^A;

W "R-P-P · P -P ^

^w12n+11-12(27D), ' ^12n' ^r12n+1' ^12n-h2' ^r12n+3^;*

Danach wird eine Verschachtelungseinrichtung 31 vorgesehen, die Laufzeitleitungen mit einem Yerzögerungsbetrag von einem Wort für die Übertragungskanäle der 32 Datenfolgen ; geradzahliger Rangordnung einschließlich der ersten und zweiten Prüfwörter enthält und Inverter 32, 33» 34 und 35 zur Invertierung der zweiten PrüfWortfolgen sind je vorge-

3. 3. 1982 59 559 /13 - 26 -

sehen. Die Verschachtelungseinrichtung 31 dient zur Verhinderung von Fehlern, die im Bereich zwischen den Blöcken auftreten und auf so viele Wörter einwirken, daß ihre Korrektur unmöglich wird. Die Inverter 32, 33» 34 und 35 sollen eine Fehloperation vermeiden, wenn sämtliche Daten in einem Block durch einen Ausfall bei der Übertragung "Null" geschaltet werden. Das bedeutet, daß bei einem Ausfall die invertierten Prüfwortfolgen im Wiedergabesystem korrekt unterschieden v/erden, Für den gleichen Zweck können bei den ersten Prüfwortfolgen Inverter vorgesehen werden.

Die zuletzt abgeleiteten 24 PCM-Datenfolgen und 8 Prüfwortfolgen werden seriell als .32-Wort-Blöcke geschaltet und ein Synchronsignal von 16 Bits wird den erhaltenen seriellen Daten zu Beginn hinzugefügt, um einen in Fig, 3 dargestellten Übertragungsblock zu bilden. Der so erhaltene Block wird über ein Übertragungsmedium oder einen Träger übertragen. In Fig. 3 wird das auf dem i-ten Übertragungskanal erhaltene Wort als U. dargestellt.

Praktische Beispiele des Übertragungsmediums oder des Trägers für das übertragene Signal können magnetische Aufnahme- und Wiedergabegeräte, Platten für die Verwendung in einem Plattenabspielgerät oder ähnliche Medien sein. Im oben genannten Übertragungszustand wird, wenn das Synchronsignal vernachlässigt wird, der Abstand zwischen den ?/örtern betrachtet, die im gleichen, ersten Fehlerkorrekturblock enthalten sind (d* h. 24 Wörter werden an den Kodierer 28 geführt). Wenn beispielsweise die Wörter W_{1 ?} ~, A und ^12n-12'^ betrachtet werden, wird der Abstand zwischen den benachbarten Wörtern, die in dem ersten Fehlerkorrekturblock enthalten sind, 12(D+1) (Wörter).

Da jedoch die Prüfwörter Q_12n, Q_12n+1, Q_12n+2 und Q

3. 3, 1982

8 6 ^{59 559 /13}

- 27 -

die vom Kodierer 28 kommen, in die Datenwörter der 24 Wörter eingefügt werden, wird der Abstand zwischen den Wörtern W_12n+O-JOjB und W₁ O_n+P>^A fünfmal so groß wie der von 12(D+1)„ Dementsprechend hat es den Anschein, daß, wenn ein Fehlerburst die 12(D+1) überschreitet, im Übertragungsweg mehr als zwei Wörter jedem der 12 Wörter von W₁ „ .. ,A , ^12r—12'^B "* ^12n+9-12'^B ^lDenac^^llDaT^ sind, so daß 12 Wörter von W_12n+2, A , ^_12n+2'^B '· ' ^W12n+11^{5B Fel:lle} Wörter werden. Wenn mehr als zwei benachbarte Wörter, zum Beispiel 4 Wörter als Fehlerwörter nachgewiesen werden, wird die Fehlerkorrektur im Fall bekannter Fehlerstellen für die vier Wortfehler durchgeführt. Im allgemeinen werden andere Wörter als fehlerhaft angesehen, wenn im Falle eines Pehlernachweises oder einer Fehlerkorrektur in jedem aus einer Vielzahl von Wörtern bestehenden Block ein^Fehlernac.hweiskode nicht jedem Wort hinzugefügt wird und die Fehlerkorrektur infolge der Tatsache unmöglich ist, daß mehr als eine unbestimmte Anzahl von Fehlerwörtern im gleichen Fehlerkorrekturblock vorkommt. In der Praxis werden, wenn die Fehlerkorrektur im Falle bekannter Fehlerstellen für -M-WÖrter vorgenommen wird, die dennoch keinen Fehler enthalten, aber infolge der Eigenschaft des Fehlerkorrekturkodes als Fehlerwörter gehalten werden, die Wörter, die korrigiert.wurden, anomal. Durch Anwendung einer solchen Eigenschaft, daß bei der Übertragung von Wörtern durch die Verschachtelungseinrichtung statistische Fehler im Übertragungsweg in geringerem Maße benachbarte Wortfehler nach der Entschachtelung werden, wenn die oben dargelegte Korrektur lediglich für benachbarte Fehlerwörter vorgenommen wird, kann jedoch die Gefahr der Ausführung einer falschen Fehlerkorrektur reduziert werden. Außerdem kann durch Anwendung der Fehlerstelle, die i, i+1, i+2 und i+3 annimmt, die Struktur der Fehlerkorrektur vereinfacht werden.

231938b 59 559

Die reproduzierten Daten werden nach jeweils 32 Wörtern eines Blocks des übertragenen Signals an den Eingang des in Pig, 4 gezeigten Fehlerkorrekturdekodierers geführt. Die übertragenen Daten, die am Fehlerkorrekturdekodierer empfangen werden, können einen oder mehrere Fehler enthalten, da die Eingangsdaten reproduzierte Daten sind. Ist kein Fehler vorhanden, stimmen die 32 Wörter, die an den Eingang des Dekodierers gegeben wurden, mit den am Ausgang des Fehlerkorrekturkodierers erscheinenden 32 Wörtern überein. Zur Umwandlung der Daten in ihren ursprünglichen Zustand wird am Fehlerkorrekturdekodierer ein Entschachtelungsprozeß durchgeführt, der zu dem entsprechenden Verschachtelungsprozeß am Kodierer komplementär abläuft. Liegt dort ein Fehler vor, wird ein Fehlerkorrekturvorgang nach der Wiederherstellung der Daten in ihren ursprünglichen Zustand durchgeführt.

Wie in Fig, 4 gezeigt, werden zunächst eine Entschachtelungseinrichtung 36 mit Laufzeitleitungen mit jeweils einem Verzögerungsbetrag von einem Wort für die Übertragungskanäle ungeradzahliger Rangordnung und Inverter 37, 38, 39 und für die Umkehrung der empfangenen zweiten Prüfwortfolgen vorgesehen. Die Ausgänge an der Entschachtelungseinrichtung 36 und an den Invertern 37, 38, 39 und 40 werden an einen ersten Dekodierer 41 gekoppelt. In diesem ersten Dekodierer 41 werden entsprechend einer Matrix wie der Paritatsprüfmatrix H_n. nach Reed-Solomon (Fig. 5) durch die in Fig. 5

φ gezeigten 32 Eingangsworter V " die Syndrome S₁₀, S₁₁, S₁ „ und S₁-, erzeugt und auf der Grundlage dieser Syndrome die o. g. Fehlerkorrektur durchgeführt. In Fig, 5 ist oC ein . Element aus dem Galoisfeld GF (2 ) und eine Wurzel der Gleichung F(x) = χ + χ + sr +χ +1. Der Dekod.ierer 41 Mtet die korrigierten 24 PCM-Datenfolgen und vier erste Prüfwortfolgen ab. Jedem einzelnen Wort der Datenfolgen wird eine

3. 3* 1982 59 559 /13 - 29 -

Anzeigeadresse oder ein Fehleraachweiskode (mindestens 1 Bit) hinzugefügt, um anzuzeigen, ob in dem betreffenden Wort ein Fehler vorhanden ist (Fehlernachweisadresse 1) oder nicht (Fehlernachweisadresse 0). In den Fig. 5 und 6 sowie in der nachfolgenden Beschreibung wird das eine empfangene Wort Wi lediglich als Wi bezeichnet.

Die Ausgangsdatenfolgen vom DekodJa?er 41 werden auf die Entschachtelungseinrichtung 42 gegeben, die zur Kompensation des von der Verschachtelungseinrichtung 29 im Fehlerkorrekturkodierer durchgeführten Verzögerungsprozesses dient und über entsprechende Laufzeitleitungen mit entsprechend verschiedenen Verzögerungswerten 27D, 26D, 25D «... 2D und 1D verfügt, die für die ersten 27 Übertragungskanäle vorgesehen sind. Der Ausgang der Entschachtelungseinrichtung 42 wird auf einen zweiten Dekodierer 43 geführt, in dem die Syndrome Sp₀, S ., Spp und S „ entsprechend der Matrix, wie beispielsweise der Reed-Solonom-Paritatsprüfmatrix H_n (Fig. 6), ge~ bildet werden. Die 28 Wörter Y„, wie sie in Fig, 6 dargestellt werden, v/erden eingegeben und die bereits erwähnte Fehlerkorrektur auf der Grundlage der Syndrome S„_Q bis S „ durchgeführt.

Der Dekodierer 43 löscht die Anzeigeadresse bezüglich jedes Wortes, dessen Fehler korrigiert wird, löscht jedoch nicht die Anzeigeadresse bezüglich irgendeines Wortes, dessen Fehler nicht korrigiert werden kann.

Die am Ausgang des Dekodierers 43 erscheinenden Datenfolgen kommen auf eine Gerade-Ungerade-Verschachtelungseinrichtung 44) in der die PCM-Datenfolgen, bestehend aus den Wörtern geradzahliger Rangordnung und die PGM-Folgen, bestehend aus den Wörtern ungeradzahliger Rangordnung, so neu geordnet werden, daß sie sich in abwechselnden Übertragungskanalen befinden, wobei Laufzeitleitungen mit einem Verzögerungswert

3. 3. 1982

23 19 3 8 6 ₃₀ ^{59 559 /13}

von einem Wort für die PCM-Datenfolgen, bestehend aus den Wörtern ungeradzahliger Rangordnung, vorgesehen werden, Damit wird die im Kodierer vor der Übertragung durchgeführte Operation entsprechend kompensiert. Am Ausgang der Gerade-Ungerade-Entschachtelungseinrichtung 44 werden die PCM— Datenfolgen vorgesehen, die den ursprünglichen Ordnungszustand haben, und die νοrbestimmte Ordnung des Digitalsignals wird vollständig wiederhergestellt, wie sie vor Eingabe in den Fehlerkorrekturkodierer bestanden hatte.

Zur Behebung der nichtkorrigierbaren Pehler wird in der nächsten Stufe nach der Gerade-Ungerade-Entschachtelungseinrichtung 44 vorzugsweise.eine Kompensationsschaltung vorgesehen, die in Pig. 4 nicht gezeigt wird. Beispielsweise kann eine Mittelwertinterpolation angewendet werden,sooft Pehler von den Dekodierern 41 und 43 nicht'korrigiert werden, so daß sämtliche verbleibenden Pehler verdeckt und eliminiert werden. Um die hohe Pehlerkorrekturkapazität des Fehlerkorrekturkodes darzustellen, wenn der erste Dekodierungsvorgang ausgeführt wird, wird jedem Wort eine Anzeigeadresse hinzugefügt, mit der das etwaige Vorhandensein eines Fehlers angezeigt wird, wobei der Zustand der Anzeigeadresse bei der zweiten Dekodierrung erkannt wird und die· Fehlerkorrektur durch Anwendung des festgestellten Ergebnisses vorgenommen wird. Gleichzeitig wird, wenn die Daten durch den Verschaentelungsprozeß und den Entschachtelungsprozeß zur Rückführung der Daten in den zweiten Ordnungszustand übertragen werden, um die zweite Dekodierung auszuführen, der Pehler aus der Erkenntnis festgestellt., ob die Anzeigeadresse einen bestimmten Zustand hat oder nicht, und die Pehler werden bis zu maximal M Wörtern korrigiert. Mit anderen Worten, die Verschachtelung und Entschachtelung dienen dazu, die im Übertragungsweg erzeugten Fehlerbursts zu verteilen und die Erhöhung der Anzahl der Fehlerwörter in einem Fehlerkorrekturblock auf eine solch hohe Anzahl

"3. 3* 1982

19 3 8 6 59 559 /13

- 31 -

zu verhindern; die nicht mehr korrigiert v/erden kann. Wenn jedoch die Periode des Fehlerbursts lang wird, kann der Fall eintreten, daß eine Vielzahl von Wörtern neben dem Fehlerkorrekturblock, die durch die Entschachtelung erhalten werden, einen Fehler enthält.

Hur dann, wenn der bestimmte Fehler durch den Zustand der Anzeigeadresse bekannt ist und falls die Korrektur für die Vielzahl der Fehlerwörter vorgenommen wird, läßt sich die Gefahr einer falschen Fehlerkorrektur im Vergleich zu dem Fall reduzieren, in dem die Fehlerkorrektur durch Verwendung der lediglich durch die Anzeigeadresse angegebenen Fehlerstelle vorgenommen wird.

In dem in Fig, 4 gezeigten Beispiel der Erfindung wird"ein Wortfehler durch einen ersten Dekodierer 41 korrigiert. Wenn erkannt wird, daß mehr als zwei Wortfehler in einem Fehlerkorrekturblock.vorhanden sind, wird die Anzeigeadresse (mindestens 1 Bit) allen 28 Wörtern des Fehlerkorrekturblocks hinzugefügt, d* h* allen Wörtern des 32-Wort-Blocks mit Ausnahme der Prüfwörter, um das Vorhandensein von Fehlern in der voranstehend angeführten Weise anzuzeigen. Diese Anzeigeadresse ist eine "1", wenn ein Fehler vorhanden ist, wird jedoch bei Fehlen eines Fehlers eine "0", Für den Fall, daß ein Wort aus 8 Bits besteht, wird die Anzeigeadresse als ein Bit mehr als MSB hinzugefügt, so daß ein Wort damit aus 9 Bits besteht. Sodann werden die Wörter durch die Entschachtelungseinrichtung 42 verarbeitet und danach an den zweiten Dekodierer 43 geführt«.

In diesem Dekodierer 43 wird der Fehler korrigiert,"indem die Anzahl der Fehlerwörter im ersten Fehlerkorrekturblock verwendet wird, die durch die Anzeigeadresse oder Fehlerstelle angegeben wird.

23 1 9 38 6 59 559¹/⁹?

Fig, 7 zeigt eine Tafel, die ein Beispiel für den Vorgang der Fehlerkorrektur angibt,, der im zweiten Dekodierer 43 ausgeführt wird. In Fig. 6 und der nachfolgenden Beschreibung wird die Anzahl der fehlerhaften Wörter durch die Anzeigeadressen mit Up ausgedrückt und die Fehlerstelle durch die Anzeigeadresse mit Ei bezeichnet. Ferner stellt Y in Fig. 7 "ja" und Έ "nein" dar.

Da im zweiten Dekodierer 43 zwei Wortfehler korrigiert werden, wird der modifizierte fehlerkorrigierende Algorithmus als Fehlerkorrekturalgorithmus genommen. Mit anderen Worten, es wird das zu Beginn des in der Figur dargestellten Flußbildes bereits erwähnte Fehlerstellenpolynom

2i i A +B +C=O berechnet und die Fehlerkorrektur mittels der Konstanten A, B und C des obigen Polynoms und der Syndrome SpQ bis S_?_ vorgenommen. Gleichzeitig wird die Gesamtzahl Up der Anzeigeadressen, die die Fehler repräsentieren und in einem Block enthalten sind, geprüft. Selbstverständlich ist es. möglich, den fundamentalen Algorithmus zu verwenden, in dem durch die Syndrome das Uichtvorhandensein eines Fehlers, das Vorhandensein eines Einwortfehlers und danach das Vorhandensein von zwei Wortfehlern schrittweise nachgewiesen wird,

(1) Das Vorhandensein oder Nichtvorhandensein eines Fehlers wird untersucht. Wenn A=B=C=O , S₂₀ = 0 und S₂_ = 0 gelten, wird allgemein davon ausgegangen, daß kein Fehler vorhanden ist. Zu diesem Zeitpunkt wird geprüft, ob Up = z. befriedigt wird oder nicht. Wenn 1\T ^ z. gilt, wird angenommen, daß kein Fehler vorliegt und die Anzeigeadresse ' im Fehlerkorrekturblock wird gelöscht (d. h. auf "0" gestellt). Wenn im Gegensatz dazu Έ~> ζ. gilt, wird die Feh- lererkennung durch die Syndrome als falsch angesehen und die Anzeigeadresse bleibt unverändert oder für alle Wörter

9 1 1

3.-3. 1982 59 559 /13

im Block werden die Anzeigeadressen auf "1" gestellt. In diesem Fall wird der Wert von z., relativ groß gewählt, z. B. 14.

(2) Es wird geprüft, ob ein Fehler ein Einwortfehler ist oder nicht. ?/enn A = B = C = O, Sp₀ Φ 0 und S₃ φ 0 gelten, wird der Fehler im allgemeinen als Einwortfehler betrachtet und die Fehlerstelle i aus der Beziehung S₂-,/Sp₀ = ⁰^" erhalten. Es wird nachgewiesen, ob die Fehlerstelle i mit der durch die Anzeigeadresse angezeigten Stelle übereinstimmt oder nicht. Wenn die Mehrzahl der Fehlerstellen durch An-.Zeigeadressen angezeigt wird, wird geprüft, ob die Fehlerstelle i mit irgendeiner von ihnen übereinstimmt oder nicht, Wenn i = Ei ist, wird geprüft, ob Np = z_? gilt oder nicht, worin z_? beispielsweise 10 beträgt. Wenn N_p = z_? gilt, wird der Fehler als Einwortfehler betrachtet und danach ein Einwortfehler durch Verwendung der Beziehung ei = S_?Q korrigiert. Gilt lp> Zp auch dann, wenn i = Ei ist, besteht die Gefahr, daß der Fehler als Binwortfehler mißdeutet wird, da die Anzahl der Anzeigeadressen für Einwortfehler zu groß ist. Die Anzeigeadressen bleiben daher unverändert oder sämtliche Wörter werden als fehlerhaft betrachtet und deren Anzeigeadressen dementsprechend auf "1" gestellt.

Im Falle von i £ ei wird geprüft, ob ITp = z~ befriedigt wird oder nicht, worin z„ ein sehr kleiner Wert ist, z. B. 3» Wenn Np = z-, gilt, wird durch Berechnung des Syndroms ein Wortfehler an der Fehlerstelle i korrigiert.

Im Falle von TTp> z„ wird darüber hinaus geprüft, ob TT = z. befriedigt wird oder nicht. Wenn z~ < IT = z^ gilt, bedeutet dies, daß IT zu klein ist, obgleich die Annahme eines Einwortfehlers durch das Syndrom falsch ist. In diesem Fall werden daher die Anzeigeadressen aller Wörter des Blocks

23 1 9 3 8 6 59 559 /13

auf "1" gestellt. Im Gegensatz zu dem Fall N > z. werden

P .

die Anzeigeadressen nicht verändert.

(3) Es wird geprüft, ob zwei Wortfehler vorhanden sind oder nicht. Wenn es sich bei dem Fehler um einen Zweiwortfehler handelt, werden die Fehlerstellen i und j durch Berechnung ermittelt.'Wenn A^O, B^O, C^O und D²/E = ©C* + <£, worin t die Werte zwischen 1 und 27 annimmt, wird der Fehler als Zweiwortfehler angesehen und die Fehlerstellen i und j aus C<_ = D/X und ⁰Cr = D/Y erhalten. Es wird ermittelt, ob die Fehlerstellen i und j mit den von den Anzeigeadressen angezeigten Fehlerstellen Ei und Ej übereinstimmen oder nicht. Y/enn i = Ei und j = Ej gelten, wird die Anzahl N der fehlerrepräsentierenden Anzeigeadressen mit dem vorbestimmten Wert von Zr verglichen. Wenn N ^ ζ gilt, werden zwei Wortfe.hler in Bezug auf die Fehlerstellen i und j korrigiert. Diese Korrektur wird vorgenommen, indem die Fehlermuster ei und ej in der voranstehend dargelegten. Weise ermittelt werden. Bei Ή > ζ,- wird keine Korrektur unter

P ο der Annahme vorgenommen, daß z, B, mehr als drei Wortfehler fälschlicherweise als zwei Wortfehler nachgewiesen wurden, wobei die Anzeigeadressen unverändert bleiben oder alle Wörter im Block als fehlerhaft angesehen werden,

Wenn eine der Fehlerstellen i und j.. mit einer der Fehlerstellen Ei und Ej übereinstimmt, d. h. i = Ei, j Φ Ej oder i Φ Ei oder j = Ej, wird geprüft, ob TT £ Zg befriedigt wird oder nicht. Wenn Ή ^ ζ,- ist, werden" zwei V/ortfehler in Bezug auf die Fehlerstellen i und j korrigiert. Wenn Np^>' ^Z6 ist,wird geprüft, ob IT & z^ befriedigt wird oder nicht. Diese Prüfung wird derart, ausgeführt, daß, wenn die Fehlerstellen teilweise übereinstimmen, die Anzahl der fehlerdarstellenden Anzeigeadressen überprüft wird, um festzustellen, ob sie groß oder klein ist.

9? 1 Q O Q C ³* ³' ¹⁹⁸²

Q C

Q Q 59 559/13

- 35 -

Wenn Έ = Z₇ ist, wird angenommen, daß die Anzahl der An-

Sr I

Zeigeadressen zu klein ist, wonach die Anzeigeadressen aller Wörter im Block auf "1" gestellt wird* Wenn jedoch Έ > Z₇ gilt, kann die Zuverlässigkeit der Anzeigeadressen als hoch betrachtet werden, so daß die Anzeigeadressen unverändert bleiben,

Wenn i Φ Ei und j Φ Ej gelten, wird, überprüft, ob 1 ^ z„ gilt oder nicht. Herrn Έ sehr klein ist, wird das durch Anwendung des Fehlerstell.enpolynoms erhaltene Resultat als wichtiger angesehen als die Anzeigeadressen und es werden zwei Wortfehler in bezug auf die Fehlerstellen i und j korrigiert. Wenn Έ > z„ ,gilt, wird darüber hinaus geprüft, ob Έ £ Zn befriedigt ist oder nicht. Diese Prüfung verläuft ähnlich derjenigen, wenn Έ £ z„ ist,, bei der die Anzeigeadressen des Blocks unverändert blieben oder die Anzeigeadressen sämtlicher. Wörter auf "1" gestellt wurden,

(4) In dem Pail, der von den obigen Fällen (1), (2) und (3) verschieden ist, wo es also mehr als zwei Wortfehler gibt, wird geprüft, ob W =3 oder Έ . = 4 gelten oder nicht und ob- im ersten F.e.hlerkorrekturblock drei oder vier Wörter jedem der 12 Wörter der Datenwörter von-24 Wörtern benachbart sind oder nicht. Lediglich dann, wenn das voranstehend Gesagte gilt, werden drei Wortfehler in bezug auf die durch die Anzeigeadressen dargestellten Fehlerstellen korrigiert. Da in diesem Fall die Fehlerwörter benachbart sind, werden die Fehlerstellen i, i+1, i+2 und i+3» Somit kann das Fehlermuster durch Berechnung erhalten werden, die sich im Vergleich zur Berechnung auf die Korrektur von vier Wortfehlern stark vereinfacht. Dieses läßt sich folgendermaßen beschreiben:

3. 3. 1982 2319386 59 559 /!3

ei = CC²¹⁸S₂₀ +odSScC-is^ +

ei + 1 = «<-¹⁵⁸S_2O +Od¹³⁸^-¹S₂₁ + ^"C²¹S₂₂ +»6¹

ei + 2 - ^¹⁵⁶S₂₀ +^C¹S₂₁ +^¹³⁵^-²¹S₂₂ +

ei ₊ 3 =

Wenn darüber hinaus N = 3 ist und die Fehlerstellen von drei Wortfehlern i, i+1 und i+2 sind, wird ein Scheinfehler zu dem Wort der Fehlerstelle i+3 hinzugefügt, wobei dieses Wort als ein Fehlerwort betrachtet wird und die Fehlerwörter als vier Wortfehler verarbeitet werden,

(5) In einem anders gelagerten Fall als in den voranstehenden Fällen (1), (2), (3) und (4) wird keine Fehlerkorrektur vorgenommen. In diesem Fall wird geprüft, ob IT ^= z.„ befriedigt wird oder nicht. Wenn N ^ 10 gilt, wird die Zuverlässigkeit der Anzeigeadressen als gering angenommen und die Anzeigeadressen sämtlicher Wörter werden auf "1" gestellt«, Wenn ΪΓ lassen.

Darüber hinaus wird der Wert zi, der mit der Gesamtzahl N

Wenn ΪΓ > z.q ist, werden die Anzeigeadressen unverändert geder fehlerrepräsentierenden Anzeigeadressen eines Blocks verglichen wird, als ein geeigneter Wert in Anbetracht der Wahrscheinlichkeit der Entstehung eines fehlerhaften Nachweises infolge des Fehlerkorrekturkodes gewählt (im voranstehenden Beispiel besteht, wenn ein Fehler mehr als 5 Wortfehler enthält, die Gefahr, daß der voranstehende Fehler nicht als Fehler bewertet wird; wenn ein Fehler mehr als vier Wortfehler enthält, kann dieser Fehler als Einwortfeh-

3D C ^{3# 3}* ¹⁵⁸²

ö 0 59 559 /13

- 37 -

ler bewertet werden, und wenn ein Fehler mehr als drei Wortfehler enthält, kann dieser Fehler als Zweiwortfehler ange~ nommen werden].

Wie bereits ausgeführt, werden entsprechend dem voranstehend dargelegten Dekodierungsverfahren die durch die Anzeigeadressen als fehlerhaft identifizierten Wörter als nicht korrigierbar kompensiert.

In dem in Fig, 4 dargestellten Fehlerkorrekturdekodierer wird die Fehlerkorrektur mittels der ersten PrüfWörter ^Q12n' ^Q12n+1' ^Q12n+2 ^{Und Q}12n+3 ^{und mittels der} zweiten Prüfwörter P_12n, ^_12b+1 > ^p-,_2n+2 ^Wld ^Pi2n+3 jeweils einmal durchgeführt. Wenn die voranstehenden Fehlerkorrekturen jedoch jeweils zweimal oder mehr (in der Praxis etwa zweimal) durchgeführt werden, läßt sich die Fehlerkorrekturkapazität beträchtlich erhöhen, da das korrigierte Ergebnis jedesmal weniger Fehler aufweist«, Wie bereits ausgeführt, wird es in dem Fall, wo ein zusätzlicher Dekodierer in der letzten Stufe vorgesehen wird, notwendig, daß das Prüfwort in den Dekodierern 41 und 43 korrigiert wird.

In dem voranstehenden Beispiel unterscheidet sich der Verzögerungswert . im Verzögerungsprozeß der Verschachtelungseinrichtung 29 von einem Kanal zum nächsten durch einen konstanten Änderungsbetrag D, wobei es jedoch auch möglich ist, eine nicht konstante Änderung des Verzögerungswertes anzuwenden, und-zwar eher als die obige konstante Änderung, Ferner sind die zweiten Prüfwörter Pi solche Fehlerkorrekturkodes, die nicht nur von den PCM-Datenwörtern gebildet werden, sondern auch von den ersten Prüfwörtern Qi, Ähnlich ist es möglich, daß die ersten Prüfwörter Qi von Wörtern gebildet werden, die das zweite Prüfwort Pi enthalten. Hier läßt sich eine Rückkopplungstechnik einsetzen, so daß die

7_β 3, 1982

2 3 19 3 8 6 59 559 /13

- 38 -

zweiten Prüfwörter Pi an den Kodierer zurückgeführt werden, der die ersten PrüfWörter erzeugt.

Diese Rückkopplungstechnik ist dann effektiv, wenn die Anzahl der Dekodierungen mehr als dreimal ausgeführt wird*

Außerdem kann es möglich sein, daß bis zu zwei Wortfehler im ersten Dekodierer 41 korrigiert werden. Es kann jedoch wie in dem voranstellenden Ausführungsbeispiel durch die Tatsache, daß, obwohl zwei Wortfehler im ersten Dekodierer korrigiert werden können, aber lediglich ein Wortfehler im ersten Dekodierer korrigiert wird, eine solche Gefahr, daß ein falscher Fe.hlernachweis oder eine falsche Fehlerkorrektur im Dekodierer verursacht wird, reduziert werden. In diesem Fall werden zwei Wortfehler im zweiten Dekodierer korrigiert, so daß die Fehlerkorrekturkapazität nicht so herabgesetzt wird. Außerdem läßt sich, da die Fehlerkorrektur durch Berechnung der Syndrome auf einen Einwortfehler begrenzt ist, der Aufbau des ersten Dekodierers sehr vereinfachen, .

Selbst wenn im ersten Dekodierer ein Einwortfehler korrigiert wird und die Anzeigeadresse für jedes Wort im Block, in dem das korrigierte Wort enthalten ist, auf "1" gestellt wird, läßt sich der Fehlernachweis richtig durchführen und die Gefahr einer falschen Korrektur damit herabsetzen.

Wie sich aus der voranstehenden Beschreibung erkennen läßt, werden Fe.hlerburts durch die Zweirichtungsverflechtung (cross-interleave) verteilt, so daß die Fehlerkorrektur sowohl für statistische Fehler als auch für Fehlerbursts wirksam durchgeführt werden kann,

Ferner wird die Fehlerkorrektur bezüglich der durch die Anzeigeadressen dargestellten Fehlerstellen nur dann ausgeführt, wenn lediglich Fehlerwörter, deren Anzahl ähnlich

3, 3, 1982 ^{59 559}

der Anzahl der benachbarten M Wörter im ersten Fehlerkorrekturblock ist, bei der Entschachtelung erhalten und durch die Anzeigeadressen nachgewiesen v/erden, Die Gefahr einer falschen Fehlerkorrektur kann daher im Vergleich zu dem Fall herabgesetzt werden, wo die Fehlerkorrektur lediglich durch die Anwendung der durch die Anzeigeadressen angezeigten Fehlerstellen vorgenommen wird, womit sich die Fehlerkorrekturkapazität verbessert·

Die vorliegende Erfindung kann mit hervorragender Wirkung bei einem digitalen Audio-Plattensystem angewendet werden, deren Theorie ähnlich der eines Video-Plattensystems ist, das als eine Wiedergabeeinrichtung und getrennt von dem Fehlerkorrekturkodierer aufgebaut werden kann. Es ist offensichtlich, daß viele Modifikationen und Änderungen durch geschickte Anwendung der Technik erreicht werden können, ohne Geist und. Rahmen der vorliegenden Erfindung zu verlassen, die im beigefügten Anspruch festgelegt ist.

Claims

Erfindungsanspruch

- 40 -

Verfahren zur Fehlerkorrektur von Daten mit η Wörtern in einem Block, wobei jedes Wort aus m Bits besteht, gekennzeichnet durch folgende Schritte:

Bildung von Syndromen S_Q bis S, . durch die folgende Berechnung eines Blocks V , der aus den empfangenen η Wörtern und einer Paritätsprüfmatrix H besteht

S₀

S,

tT =

wobei die Paritätsprüfmatrix H η Spalten und k Zeilen hat und in der jedes Element aus einer zuvor bestimmten Zeile aus oC (=1) bis ^C ~ ausgewählt wird, wobei das Element ^Ceine Wurzel ist, die ΐ(χ) = 0 genügt, wenn F(x) ein irreduzibles Polynom auf einem Galois Feld GI¹C2) ist, so daß der gleiche Wert in der vorbestimmten Zeile nicht zweimal erscheint, und worin die Elemente in den verbleibenden Zeilen ausgewählt werden, um eine bestimmte Potenz für alle Elemente in der jeweiligen Zeile zu bilden, von den entsprechenden Elementen in der vorbestimmten Zeile;

Bildung der folgenden Konstanten A, B und C, die auf folgenden Syndromen basieren

31

A = A₁

^S0^S2

S.

+ S₀S₃ + S₂ ²

S₂S₄ + S₃

3. 3* 1982 59 559 /13

Ausführung der Fehlererkennung und Fehlerkorrektur, die nachstehend unter (a), (b) und (c) dargestellt sind und auf den genannten Syndromen und Konstanten basieren

(a) wenn S_Q = S₃ A₁- = A₂ B₁ - B₂

— Φ 0 Λ

— # Φ #

V₃
k-3

= 0,

und C₁ _ = 0

Ά.—J

befriedigt γ/erden, v/ird festgestellt, daß kein Fehlerwort vorhanden ist;

(b) wenn S_Q ^ 0, S₃ φ 0, S₄ φ 0, ... S_k-1 Φ 0, A_fc = 0, B_k = 0, wobei k = 1 bis k -.3 und C_k_~ = 0 erfüllt sind, wird entschieden, daß ein Einwortfehler vorhanden ist,,und die Fehlerkorrektur wird durch die Berechnung der Syndrome vorgenommen;

3 19 3 8 6 59 559 /13

(c) wenn A₁ Φ O, B-, ^ 0 und C₁ ., Φ 0 befriedigt werden, wird folgendes vorausgesetzt:

^B1 ^B2 ^Bk-3 ( — = — = ... =

^AT ^A2 A_k_3

1 2 k""3

^A1 ^A2 '" ^Ak-3

und die Pehlerstellengleichung °C +D⁰C +E=O wird gelöst, um die Fehlerstellen i und j zu erkennen und zwei Wortfehler zu korrigieren.

Hierzu 8 Seiten Zeichnungen