DE3123978A1

DE3123978A1 - "verfahren zum decodieren einer uebertragenen digitalen information unter korrektur von fehlern"

Info

Publication number: DE3123978A1
Application number: DE19813123978
Authority: DE
Inventors: Kentaro Ohta Odaka; Yoichiro Sako
Original assignee: Sony Corp
Current assignee: Sony Corp
Priority date: 1980-06-20
Filing date: 1981-06-19
Publication date: 1982-04-01
Anticipated expiration: 2001-06-20
Also published as: DD159830A5; FR2485303B1; NL191104B; GB2079993B; DK158484C; IT8122477A0; DK270481A; CA1169154A; FR2485303A1; NL8103002A; SE451421B; SE8103835L; GB2079993A; ES503165A0; DE3123978C2; NL191104C; ES8203543A1; DK158484B; JPH0353817B2; AU7200081A

Description

7-35, Kitashinagawa 6-chome,

Shinagawa-ku, Tokyo/Japan

Verfahren zum Decodieren einer übertragenen
digitalen Information unter Korrektur von

Fehlern

Die vorliegende Erfindung bezieht sich generell auf ein Verfahren zur Fehlerkorrektur und insbesondere auf ein Fehlerkorrekturverfahren mit einer ausgeprägten Fehlerkorrekturfähigkeit sowohl für Burstfehler als auch für zufällige Fehler, wobei dieses Verfahren die Wahrscheinlichkeit vermindern kann, daß ein nichtkorrigierter Fehler übersehen wird.

Es ist bereits an anderer Stelle ein Datenübertragungssystem vorgeschlagen worden (US-Anm, Nr. 218 256 vom
19.12.1980), welches für die Korrektur von Burst-Fehlern wirksam ist, wozu ein sogenanntes Querverschachtelungs-' verfahren angewandt wird. Bei einem derartigen- Querverschachtelungsverfahren werden Wörter in einer pulscodemodulierten Datensignaireihe in.einer Vielzahl von Folgen über eine Vielzahl entsprechender Kanäle bereitgestellt, die in einem ersten Anordnungszustand vorgesehen sind. Ferner ist ein erster Fehlerkorrektur-Cödierer vorgesehen.

3123973

der aus dem betreffenden Signalen eine erste Prüfwortreihe erzeugt. Diese ersten Prüfwortreihen und die PCM-Datensignalreihen in der Vielzahl von Kanälen werden in einen zweiten Anordnungszustand umgesetzt. Sodann wird ein Wort in dem zweiten Anordnungszustand für jede PCM-Datensignalfolge in der Vielzahl von Kanälen einem zweiten Fehlerkorrekturcodierer zugeführt, um von diesem eine zweite Prüfwortreihe zu erzeugen, so daß eine Doppelverschachtelung (d.h. eine zweifache neue Anordnung) für jedes Wort vorgenommen wird. Der Zweck der Doppelverschachtelung besteht darin, die Anzahl der fehlerhaften Wörter in irgendeiner Gruppe von Wörtern zu reduzieren, die in einem gemeinsamen Fehlerkorrekturblock enthalten sind, wenn das in einem solchen Fehlerkorrekturblock enthaltene· Prüfwort und das zugehörige PCM-Datensignal · verteilt und übertragen werden. Jegliche derartigen fehlerhaften Wörter werden über mehrere Blöcke verteilt und auf der Empfangsseite in die ursprüngliche Anordnung wieder.zurückgebracht . Mit anderen Worten ausgedrückt heißt dies, daß dann, wenn ein Burst-Fehler sich während der Übertragung ausbildet, der Burst-Fehler verteilt sein kann. Wenn die obige Verschachtelung zweimal vorgenommen wird, dann werden die ersten und zweiten PrüfWörter jeweils dazu herangezogen, die Wörter in verschiedenen Fehlerkorrekturblöcken zu korrigieren. Demgemäß kann sogar dann, wenn ein Fehler durch eines der beiden EPüfwÖrter nMlt korrigiert werden kann, dieser Fehler durch das andere Prüfwort korrigiert werden. Demgemäß bringt dieses Verfahren einen erheblichen Fortschritt hinsichtlich der Fehlerkorrekturfähigkeit bei Burst-Fehlern mit sich.

Wenn jedoch in einem Wort ein Bit als fehlerhaft ermittelt worden ist, wird das gesamte Wort als fehlerhaft betrachtet. Wenn ein empfangenes Datensignal eine relativ große Anzahl von zufälligen Fehlern aufweist, dann ist somit das oben beschriebene Doppelverschachtelungsverfahren nicht immer genügend leistungsfähig hinsichtlich der Korrektur dieser zufälligen Fehler.

Zu diesem Zweck ist vorgeschlagen worden, daß ein Fehlerkorrekturcode mit einer starken Fehlerkorrekturfähigkeit beispielsweise der Reed-Solomon-(RS)-Code, der Bose-Chaudhuri-Hocquenghem-(BCH)-Code oder eine Variante eines b-Nachbarcodes, der K Wortfehler korrigieren kann, beispielsweise zwei Wörter in einem Block und der außerdem M Wortfehler, beispielsweise drei Wortfehler oder vier Wortfehler korrigieren kann, falls die Stelle der Fehler bekannt ist, mit dem obigen Mehrfachverschachtelungsverfahren kombiniert wird.

Dieser Fehlerkorrekturcode ermöglicht die Vereinfachung des Aufbaus eines Decoders, wenn lediglich ein- Wortfehler zu korrigieren ist. "

In dem Fall, daß ein erster Decodierungsschritt für den zweiten Fehlerkorrekturblock erzielt wird, erfolgt eine Umsetzung in den ersten Anordnungszustand, und mit Ausführen eines zweigten DecodierungsSchrittes bezüglich des ersten Fehlerkorrekturblockes ist es möglich, daß sogar dann, wenn ein Fehler bei der nachfolgenden Decodierung existiert, .dieser als kein Fehler bewertet wird oder daß der Fehler nicht ermittelt wird. Demgemäß tritt im Falle.der Verarbeitung von beispielsweise Ton-PCM-Signalen dann, wenn Daten mit einem.nicht ermittelten Fehler auftreten und wenn die fehlerhaften Daten ohne' eine Korrektur einer Digital-Analog-Wandlung unterzogen werden, ein Eremdt.on. in dem analogen Tonausgangs signal auf.

Der Erfindung liegt demgemäß die Aufgabe zugrunde, ein verbessertes Fehlerkorrekturverfahren anzugeben·, welches das übersehen von Fehlern vermindern kann.

Darüber hinaus soll ein Fehlerkorrekturvarfahren angegeben werden, durch, welches die Ausbildung von Fremdtönen vermieden wird, wenn ein PCM-Tonsignal übertragen wird.

31 2397Π

Gemäß einem Aspekt.der vorliegenden Erfindung ist ein Fehlerkorrekturverfahren für die Aufnahme von übertragenen Daten, wie digitalisierten PCM-Tonsignalen geschaffen. Die Übertragung kann über einen Träger, wie einen Rundfuhkträger oder über Kabel, erfolgen und das Aufzeichnen des Signals auf einem Magnetband, auf einer optischen·Platte oder einem anderen Aufzeichnungsträger einschließen. Die Daten werden als Blöcke digitaler Datenwörter aufgenommen und einem ersten Decoder als erste Fehlerkorrekturblöcke zugeführt, umfassend eine Vielzahl von Informationswörtern, eine Reihe von ersten Prüfwörtern und eine Reihe von zweiten PrüfWörtern. Die aufgenommenen Wörter werden, in der betreffenden Anordnung decodiert, wobei die Informatipnswör.ter und die ersten PrüfWörter dadurch korrigiert Werden, daß Fehlersyndrome unter Heranziehung der zweiten Prüfwörter erzeugt werden. Ein Zeiger, d.h. ein zusätzliches Bit, wird den Wörtern hinzugefügt., um anzugeben, ob ein nicht korrigierter Fehler in derartigen Wörtern zurückgeblieben ist. Der Zeiger ist beispielsweise "1", sofern das zugehörige Wort nicht korrigierte Fehler enthält; ansonsten ist der Zeiger "0". Sodann werden die Wörter in einer die Verschachtelung aufhebenden Entschachtelurigsstufe dadurch gewissermaßen entschachtelt, daß die Wörter um verschiedene Beträge verzögert und als zweite Fehlerkorrekturblöcke einem zweiten Decoder zugeführt werden. Jn diesem zweiten Decoder werden die Informationswörter durch Erzeugen von Fehlersyndromen decodiert, wozu die ersten Prüfwörter herangezogen werden. Sofern Fehler als vorhanden bestimmt werden, wird die Wörtstelle jeglicher fehlerhafter Wörter innerhalb des zweiten Fehlerkorrekturblockes berechnet. Die berechnete Wortstelle wird mit der fehlerhaften Wortstelle verglichen, wie sie durch den zugehörigen Zeiger angezeigt wird, wobei zumindest ein derartiges fehlerhaftes Wort an der fehlerhaften Wortstelle korrigiert wird. Sodann wird die Anzahl der fehlerhaften Wörter, was durch die Zeiger angezeigt wird, bestimmt, und die be-

3 1 2 3 a V ö

- ίο -

treffende Zahl wird mit einem vorbestimmten Wert verglichen. Sofern die Zahl kleiner ist als der betreffende Wert, werden die den korrigierten fehlerhaften Wörtern zugehörigen Zeiger gelöscht. Wenn jedoch die Zahl größer ist. als"der betreffende Wert, bleiben die Zeiger ungelöscht. Da die Daten dann als unzuverlässig betrachtet werden, kann das Verfahren alternativ sämtlichen Wörtern in dem Block einen Zeiger geben.

Danach werden die fehlerhaften Wörter (die durch den Zeiger bestimmt sind) kompensiert, beispielsweise durch Interpolation.

Anhand von Zeichnungen wird die Erfindung mit den ihr anhaftenden ' Merkmalen und Vorteilen nachstehend beispielsweise näher erläutert. · ■ ■

Fig. 1 . zeigt mit seinen Fig. 1A und 1B in einem ·

Blockdiagramm ein Ausführungsbeispiel für einen FehlerkorrekturfCodierer, bei dem die vorliegende Erfindung angewandt ist;

Fig. 2 zeigt eine Anordnung eines Blockes von

codierten Daten bei der Übertragung;

Fig. 3 zeigt mit seinen Fig. 3A und 3B in einem

Blockdiagramm ein Ausführungsbeispiel· eines. Fehlerkorrektur-Decoders, bei dem die vor- . . liegende Erfindung angewandt ist;

Fig. 4, 5, 6, . "

7A und 7B zeigen Diagramme, die zur Erläuterung der

• Arbeitsweise des Fehlerkorrektur-Decoders . herangezogen werden.

Im folgenden werden die bevorzugten Ausführungsformen der Erfindung näher erläutert. Zunächst wird ein Fehlerkorrek- . turcode erläutert, der bei dieser Erfindung benutzt wird.

Im Zuge der Erläuterung wird der Fehlerkorrekturcode durch eine Vektordarstellung oder durch eine zyklische Gruppendarstellung ausgedrückt.

Zunächst wird ein nicht-reduzierbares Polynom F(x) mter Ordnung in einem Galois-Feld GF(2) betrachtet. In dem Feld GF(2), welches lediglich die Elemente "0" und "1" enthält, weist das nichtreduzierbare bzw. nichtzerlegbare PoIynom F(x) keine reelle Wurzel auf. Demgemäß wird eine imaginäre (oder komplexe) Wurzel<* berücksichtigt, die die Be-Ziehung F(x)=0 erfüllt. Zu diesem Zeitpunkt bilden 2 verschiedene Elemente O, <*, t* , (A. , ... öl , d.h. alles Elemente, die eine Potenz von<* sind und die ein 0-Element enthalten, ein Erweiterungs-Galois-Feld GF(2 ). Dieses Erweiterungsfeld GF(2 ) ist ein Polynomring mit einem nichtzerlegbaren Polynom F(x) mter Ordnung über dem Feld GF(2) als Modul. Das Element von GF(2^m) kann als lineare Kombination von 1,Ot= /~x_7, <X² = Z"x²_7f .... a^m~¹ = /~x^m"¹_7 ausgedrückt werden. Dies bedeutet, daß diese Elemente wie folgt ausgedrückt werden können:

_a₀ + H₁Ix] + a₂[x²]

"+ · · · ao¹¹¹"

^(am-l' V-2' ·** ^a2' ^al' Vj

wobei a_Q, a,,'... ^a _m_i Elemente von eGF(2) sind.

Als Beispiel sei das Erweiterungsfeld GF(2 ) betrachtet, und als Modul sei das Polynom F(x)=x +x +x +x +1 berücksichtigt (alle Variablen seien 8-Bit-Daten). Dieses Feld GF(2⁸) kann wie folgt angegeben werden:

« ♦■

O I Z. O U-/ U

- 12 -

^oder

^(a7.i ^a6· ^a5· ^a4' ^a3' ^a2·. ^al-^:'

Demgemäß sei beispielsweise a_ als das höchstwertige Bit betrachtet/ und a_ sei als das niederwertigste Bit betrachtet. Da a_ zu GF(2) gehört, sind dessen Elemente entweder O oder 1.

Aus dem Polynom P(x) wird ferner folgende Matrix T abgeleitet, die m Zeilen und m Spalten aufweist:

T +

0	0	... ο
1	0	0
0	1	. · — 0

0 0

.1

Als alternativer Ausdruck kann ein Ausdruck verwendet werden, der eine zyklische Gruppe enthält, die zu erkennen erlaubt, daß der Rest des Erweiterungs-Gälois-Peldes GF(2^m) - mit Ausnahme des O-Elementes - eine mültiplikative Gruppe mit der· Ordnung 2^m bildet. Wenn die Elemente von GF(2^m) unter Verwendung einer zyklischen Gruppe ausgedrückt werden, dann erhält man folgenden Ausdruck:

•,τη

0, 1 (a=2^m), α, α", α"\

2m-2

Bei der vorliegenden Erfindung werden dann, wenn m Bits ein Wort und η Wörter einen Block bilden, k- PrüfWörter erzeugt, und zwar auf der Grundlage einer Paritätsprüfmatrix H:

H =

η-1 2(η-2)

η-2 2(η-2)

α-

2- 1

Jk-I) (η-1) _a(k-l)(n-2)

„k--l I

Ferner kann die Paritätsprüfmatrix H in entsprechender Weise unter Heranziehung der Matrix T ausgedrückt werden:

H ⁼

i-1

_Tn-2 _T2(n-2)

J-

τ² ι

,(k-D(n-l) _T(k-l)(n-2)

_Tk-1

Hierbei ist I eine Einheitsmatrix mit m-Zeilen und m-Spalten.

Wie oben erwähnt, sind die die Wurzel o( verwendenden Ausdrücke grundsätzlich dieselben Ausdrücke, die eine Generatormatrix T verwenden. .Wenn der Fall veranschaulicht wird, daß 4 (k=4) PrüfWörter benutzt werden, dann wird überdies die Paritätsprüfmatrix H zu folgender Matrix:

H =

2(η-1)

η-2

2(η-2) 3(η-2)

1 1

^ I C \S κ/ ι \J

Wenn in diesem Fall ein einziger Block von empfangenen

A Λ Aa

Daten als Spaltenvektor ν = (W -'/W _o, ... W₁, W>J ausge-

^ η—ι η~Λ ι υ

drückt wird, wobei Wi = Wi + ei gilt und wobei ei ein Fehlermuster ist, werden vier Syndrome S_Q, S-, S₂ und S₃ auf der Empfangsseite entsprechend folgender Beziehung erzeugt:

= H . V^J

. Dieser Fehlerkorrekturcode kann bei der .Fehlerkorrektur bis zu zwei Wortfehler in einem Fehlerkorrekturblock korrigieren und außerdem drei Wortfehler oder vier Wortfehler korrigieren, falls die Fehlerstelle bekannt ist.

In jedem Block sind vier Prüfwörter (p-W_, q=W,, T=W₁, S=W ) enthalten. Diese Prüfwörter können aus folgenden Beziehungen erhalten werden:

= a

Ea¹Wi = b

p + q-fr + s = EWi αρ + cxq + ar + s

Ot⁶P + a^q + a²r + s = E

a⁹p + a⁶q + a³r + s = Ea³¹Wi =d

wobei Σ gegeben ist als n? 1

i=4 ".'

Wenn der Rechenvorgang weggelassen wird, führt die Berechnung' zu folgender Beziehung:

.212
156
158
218

153

138 158

152 135

156

_t209 _t152 153

212

■ a b c

Der auf der Sendeseite vorgesehene Codierer dient dazu, die Prüf Wörter p,.q, r und sin der oben angedeuteten Art und Weise zu bilden.

Anschließend wird der grundsätzliche Algorithmus der Fehlerkorrektur beschrieben, und zwar für den Fall, -daß die Daten, welche' die PrüfWörter enthalten, wie sie oben erzeugt worden sind, übertragen und dann aufgenommen werden.

(1) Wenn kein Fehler vorhanden ist, sind alle Syndrome O: ³O= ^S1 =^iS2=^S3 =° ■ '

(2) Wenn ein Wortfehler vorliegt (ein Fehlermuster wird als ei dargestellt), dann sind S_n = ei, S₁ = ot^aei, S₀ = <* ei, S₃ = c* -^ei.

Damit sind folgende Beziehungen erreicht:

¹C -

α S_n =

et So — Sn

Das Vorliegen eines Wortfehlers oder keines Wortfehlers kann dadurch entschieden werden, ob die obige Beziehung erfüllt ist oder nicht, falls i sukzessiv geändert wird. Daraufhin wird die folgende Beziehung erhalten:

^Sl ₌ ■ ^S2 ₌ ^S3 _β j S₀ S₁ S₂

Damit wird das Muster von <* mit dem zuvor in einem Festwertspeicher ROM gespeicherten Muster verglichen, um die Fehlerstelle i zu kennen. Zu diesem Zeitpunkt wird das Syndrom S₁ zu dem Fehlermuster ei selbst.

(3) Im Falle von zwei Wortfehlern (ei und ej) genügen die Syndrome folgenden Beziehungen:

S_n = ei + ej j · ■

5-, - α ei + a^ej

^o ei

Die obigen Gleichungen können wie folgt modifiziert werden:

a^x + a^J)ei . ^X(a^X + a^)ei

S₂ = α (et

3 ~ ^α '^α

Wenn die folgenden Gleichungen erfüllt sind, werden demge mäß zwei Wortfehler unterschieden:

+ S₁) = 0^S₁ + S₂

₂) = a^JS₂

+ S₂) = a^JS₂ +

Wenn die obigen Gleichungen erfüllt bzw. festgelegt sind, · dann erfolgt eine Entscheidung der Fehler als 2-Wort-Fehler. Demgemäß werden die Fehlermuster zu diesem Zeitpunkt wie

folgt angegeben:

ei-

und

ej - ^SQ+,^tt"^lsl 1 4- «J"¹¹

(4) In dem Fall, daß drei Wortfehler (ei, ej und ek) auftreten, können die Syndrome wie folgt angegeben werden:

Sq = ei. 4- ej 4· ek :_:. S, = a^Xei 4- a^ej 4- a^kek

2i 2t 21c '■ S₂ = α ei 4- ά ^Jej 4- α ek

S_q = a^3xek 4- a.³^ej 4- ct^3kekl ..

Die obigen Gleichungen können wie folgt modifiziert werden;

= (a^X	4	a^k)ei + (	..J I Ct T"	- k. α )	ej	ej
= a^x(	ex¹	4- a^k)ei +	aJ(	<x^j 4-	.*>	^k)ej
	(α	¹ 4- ix^k)ei		j_(txj	4- α

Demgemäß werden folgende Gleichungen gewonnen:

aJ(q^kS₀ +.S₁) + (a^kS_x + S₂) = (a^X +^)Ca¹ +a^k)ei · ^Ca¹¹S₁ + S₂) ■+ (a^kS₂ 4- S₃) = a^x(a^X 4- α^)(α^Χ 4- a^k)ei

Wenn die folgende Gleichung festgelegt ist, die eine notwendige Bedingung für 3-Wort-Fehler darstellt, dann können demgemäß alle drei Wortfehler unterschieden werden. Hierbei ist angenommen/ daß die Bedingungen S ?* O, S_-. 5*0 und S₂ φ Ο erfüllt sind:

a^x{aJ(a^kS₀ 4- S₁) 4- (.Ai₁ + S₂)) = £ (0^S₁ 4- S₂) I

4- (a^kS_o 4-So)

J I ΔΟΌ

Die entsprechenden Fehlermuster werden zu diesem Zeitpunkt wie folgt angegeben:

ei = S₀ + (α

(1 + α¹"

ej = S₀ + (<T^K +- α"¹) S₁ + α"*"¹«

(1 + α³ ^χ) (1 + ct^{J K}) ek = S_n + (α"¹ + CTJ)S-, + α~^χ^£

. a^k~

Tatsächlich ist der Aufbau einer Schaltungsanordnung zur Korrektur von drei Wortfehlern ziemlich kompliziert, und die für den Korrekturbetrieb erforderliche Zeit ist lang. Demgemäß wird in der Praxis eine Fehlerkorrekturoperation benutzt, bei der die obige Operation mit einer Fehlerkorrekturoperation verknüpft wird, bei der die Fehlerstellen von i, j, k und 1 durch ein·Fehleranzeigebit oder= durch einen Zeiger bekannt sind. Die obigen Gleichungen . werden für die Prüfung verwendet.

(5) In dem Fall, daß vier Wortfehler (ei, ej, ek und el) vorhanden sin'd, können die Syndrome wie folgt angegeben werden:

5₀ = ei + ej + ek"+~e£

5₁ = ct^ei + O^ ej + a^kek + a^£e£

9i 2i ?V ?9 ₂ = α ei + α ^Jej + α ek + α *e£;

S₃ =- a³ⁱei + a^eJej + a^3kek + a^3jle£^;

Die obigen Gleichungen können wie folgt modifiziert werden

ei = S₀+(.a~J+a"^k+ α" ^)S₁ + (α

ej = S₀+(a~^k+a"^Jl+a~ⁱ)S

e£ = S₀+ ( a"¹+^^ +O^-1^)S₁ + (a"¹"·?+^-³"¹^ +' a"^lc"ⁱ)S₂+

^^J)(i+a^£"^k)

Wenn die Fehlerstellen (i, j, k, 1) durch Zeiger angezeigt werden, dann kann demgemäß der Fehler durch die obige Berechnung korrigiert werden. " . - .

Der grundsätzliche Algorithmus der obigen Fehlerkorrktur liegt darin, daß in dem ersten Schritt durch die Syndrome S_Q bis S₃ geprüft wird, ob ein Fehler vorhanden ist oder nicht, daß im zweiten Schritt überprüft wird, ob der Fehler ein 1-Wort-Fehler ist oder nicht, und daß im dritten Schritt überprüft wird, ob der Fehler durch 2-Wort-Fehler gegeben ist oder nicht. Wenn bis zu zwei Wortfehler korrigiert werden, wird die Zeitspanne zur Beendigung sämtlicher Schritte lang, was ein Problem insbesondere danr. mit sich bringt, wenn die Fehlerstelle der beiden Wortfehler erhalten wird.

Nunmehr wird eine Beschreibung eines modifizierten Algorithmus gqgeben, der dann wirksam ist, wenn die Korrektur von zwei Wortfehlern angenommen wird, ohne daß das obige Problem hervorgerufen wird.

Die Gleichungen der Syndrome S_Q, S₁, S₃ und S₃ im Falle von zwei Wortfehlern (ei, ej) werden wie folgt angegeben:

O I /LO Ö

S₀ = ei + ej

S-. = · α ei 4- α ej

5₂ = a^2lei + CX²^

5₃ = a³ⁱei + a^eJ

Die obigen Gleichungen werden wie folgt modifiziert:

•' - - η I

(a^xS₀ + S₁) (CX¹S₂ + S3) = (Ot¹S₁ + S₂)

Die Gleichung wird weiter modifiziert, so daß das folgende Fehlerstellen-Polynom erhalten wird:

(SqS₂ + S^)₀ ²¹ +· (S₁S₂ + S₀S₃)O¹ + (S₁S₃ + S₂ ²) =

Nunmehr werden die Konstanten der betreffenden Terme des obigen Polynoms wie folgt angegenommen:

• ^s0^s2⁺.^sl^?".^A i-

S₁S₃ + S₂ ² - C j

Durch Heranziehen der obigen Konstanten A, B und C kann die Fehlerstelle der beiden Wortfehler erhalten werden.

(1) Im Falle keines Fehlers:

A=B=C=O, S_Q =0 und S₃ =

(2) Im Falle eines 1-Wort-Fehlers:

Wenn A=B=C=O ist, dann sind die Beziehungen S_ ^O und S₃ φ 0 erfüllt, und der Fehler wird als 1-Wort-Fehler

bewertet. . - _

i 1 Aus der Beziehung ι* = ·=— kann die Fehlerstelle i ohne

0 weiteres bestimmt werden. Demgemäß wird der Fehler durch die Heranziehung der Beziehung ei = S_Q korrigiert.

(3) Im Falle von 2-Wort-Fehlern:

Wenn ein Fehler in mehr als zwei Wörtern auftritt, sind die Beziehungen A ψ O₁ B^O und C j£ 0 erfüllt, und damit wird die Entscheidung ziemlich einfach.
Zu diesem Zeitpunkt kann die folgende Gleichung festge-

ΑΛ²¹ + B*¹ + C = O

legt werden.
Αλ ^X + Β«*¹ +

wobei i = O bis (n-1) ist.

B C

Wenn angenommen wird, daß —5— = D und —r— = E gilt,

dann werden folgende Gleichungen erhalten:
D = Λ¹ + «* .

Damit wird folgende Gleichung gewonnen:

Λ²¹ + DoC¹ + E = 0, ' ■ .

Wenn die Differenz zwischen zwei Fehlerstellen mit t angenommen wird, d.h. j=i+t, dann werden folgende Gleichungen erhalten:

D =ot^l(1 + ef)
_ _ ,2i+t

Demgemäß wird folgende Gleichung erhalten:

^E a^ü

Wenn der Wert von c*. + c< des jeweiligen Wertes von
t = 1 bis (n-1) zuvor in einen ROM-Festwertspeicher
eingeschrieben ist und wenn festgestellt wird, daß der
Wert mit dem Wert von =- übereinstimmt, der aus dem

Ei

Ausgangssignal des ROM-Speichers und einem empfangenen
Wort berechnet worden ist, dann kann t erhalten werden. Wenn die obige Übereinstimmung nicht festgestellt wird, bedeutet dies, daß Fehler in mehr als drei Wörtern auftreten.

ό izjy /«

Wenn die folgenden Ausdrücke angenommen werden;

X— 1 J. _/
— IT c\

Y = 1 + cC^t = §- + S

Γι

dann können die folgenden Ausdrücke erhalten werden:

2
X

Y.

Aus den obigen Ausdrücken"können die Fehlerstellen i und j erhalten werden. Die Fehlermuster ei und ej werden sodann wie folgt angegeben: · - ·

. (a^Js0"+ .^Sl? " = ^S0 + ^Sl^:

■. ^a¹S_n + S₁^ S_n . S₁ : ej = Q 1. = _JJ + 1.

• D „__X .... D-Damit können die Fehler korrigiert werden..

Der obige modifizierte Korrekturalgorithmus kann die Zeitspanne wesentlich verkürzen, die erforderlich ist, um .die Fehlerlage bzw. Fehlerstelle auf die Korrektur von 2-Wort-Fehlern zu berechnen, und zwar im Vergleich zu der Zeitspanne bei dem.grundsätzlichen Algorithmus.

Wenn die Anzahl k der Prüfwörter erhöht wird, kann die Fehlerkorrekturfähigkeit demgemäß weiter verbessert werden. Wenn beispielsweise k. mit 6 gewählt wird, können drei Wortfehler korrigiert werden, und 6 Wortfehler können dann korrigiert.werden, wenn die Fehlerstelle bekannt ist.

Nunmehr wird eine Ausführungsform der vorliegenden Erfindung unter Bezugnahme auf die Zeichnungen beschrieben. Demgemäß

- 23-

ist die Erfindung als Ausführungsbeispiel für die Aufzeichnung und Wiedergabe eines PCM-Tonsignals angewandt.

In Fig. 1 ist insgesamt ein Fehlerkorrektur-Codierer gezeigt, der in einem Aufzeichnungssystem vorgesehen ist, dem als Eingangssignal ein PCM-Tonsignal bzw. -Audiosignal zugeführt wird. Dieses PCM-Tonsignal bereitzustellen, werden linke und rechte Stereo-Signale mit einer Abtastfrequenz f_ (von beispielsweise 44,1 kHz) abgetastet, und der jeweils abgetastete Wert wird in ein digitales Wort umgesetzt (welches beispielsweise als Zweierkomplement codiert ist und eine Länge von 16 Bits umfaßt). Demgemäß werden für den linken Kanal des Tonsignals PCM-Datenwörter L_n/ L₁, L„ .. und für den rechten Kanal PCM-Datenwörter R_Q, R₁, R₂ ... er- . halten. Die PCM-Datenwörter des linken Kanals und des rechten Kanals werden jeweils in sechs Kanäle aufgetrennt, womit insgesamt 12 Kanäle· vorliegen, in denen PCM-Datenfolgen auftreten, die dem Fehlerkorrektur-Codierer eingangsseitig zugeführt werden. Zu irgendeinem vorgegebenen Zeitpunkt werden 12 Wörter, wie L₆ , R_g , L_g ., Rg ₊₁, L_{g +2}, R_{g +2}/ L_{ß +3}, ^R6n+3' ^L6n+4' ^R6n+4' ^L6n+5 ^{ünd R}6n+5 ^{dem Codierer} eingangsseitig zugeführt. Bei. dem dargestellten .Ausführüngsbeispiel .

ist jedes Wort in obere 8 Bits und in untere 8 Bits aufgeteilt. Die 12 Kanäle werden demgemäß als 24 Kanäle verarbeitet. Der Einfachheit halber ist jedes Wort der PCM-Daten mit Wi ausgedrückt, wobei die oberen 8 Bits mit Wi, A angegeben sind, während die unteren 8 Bits mit Wi, B angegeben sind. Das Wort Lg ist beispielsweise in die beiden Wörter W₁₂ , A. und W₁₂ , B.unterteilt.

Die PCM-Datenfolgen der 24 Kanäle werden zunächst einer Verschachtelungseinrichtung 1 zugeführt, iln der geradzahlige und ungeradzahlige Kanäle'verschachtelt werden. Wenn η eine ganze Zahl 0, 1, 2 ... ist, dann sind die Wörter L_gn (d.h. W_12n,A und W_12n,B), R_6n (d.h. W_12n+1,A und W_12n+1,B)_r .

6 I ZOa /ö

(d.h. W₁₂n+4'^AundW12n+4'^B>' ^R6n+2 ^(d-^h· ^W12n+5'^{A und} ^W12n+5'^B)' ^L6n+4 ^(d-^h' ^W12n+8'^{A und W}12n+8'^B> ^sowi6 ^R6n+4 (^d'^h* ^W12n+9'^{A und W}12n+9'^{B) wörter} gerader Ordnung, während die übrigen Wörter solche ungerader Ordnung sind. Die PCM-Datenfolgen, die aus Wörtern gerader Ordnung bestehen, werden durch 1 -Wort-Verzögerungs schaltungen oder -Verzögerungsleitungen 2A, 2B, 3A, 3B, 4A, 4B, 5A, 5B, 6A, 6B, 7A und 7B der Verschachtelungseinrichtung 1 verzögert. Es ist selbstverständlich möglich, Wörter um eine längere Zeitspanne zu verzögern als um ein Wort, beispielsweise um 8 Wörter. In der Verschachtelungseinrichtung 1 werden ferner die 12 Datenfolgen, bestehend aus Wörtern gerader Ordnung, derart umgesetzt oder verschoben, daß diese Wörter den ersten bis zwölften Übertragungskanal einnehmen, während die 12 Datenfolgen, umfassend die Wörter ungerader Ordnung, so umgesetzt werden, daß sie den 13 bis. 24. Übertraguhgskanal einnehmen bzw. belegen.

Die Verschachtelungseinrichtung 1 dient daz.u, zu verhindern, daß mehr als zwei aufeinanderfolgende Wörter der linken bzw. rechten Stereosignale Fehler entwickeln. In diesem Fall wird es nahezu unmöglich, die Fehler· zu korrigieren. ' ■

Um den Nutzen dieses Merkmals zu erläutern, werden drei aufeinanderfolgende bzw. kontinuierlich auftretende Wörter Li-1, Li und Li+1 beispielsweise betrachtet.' Wenn das Li fehlerhaft und nicht korrigierbar ist, dann ist es höchst wünschenswert, daß die dieses Wort umgebenden beiden Wörter Li=1 und Li+1 richtig sind. Der Grund hierfür besteht darin, daß zur Kompensation eines nicht korrigierbaren, fehlerhaf-' ten Wortes Li das Wort Li zwischen dem vorangehenden korrekten Wort Li-1 und dem folgenden korrekten Wort Li+1 interpoliert wird, indem üblicherweise der Mittelwert von Li-1 und Li+1. herangezogen wird. Die Verzögerungsleitungen 2A, 2B ... 7A und 7B der Verschachtelungseinrichtung 1 sind so vor-· gesehen, daß benachbarte Wörter in verschiedenen Fehlerkorrek-

turblöcken auftreten. Darüber hinaus liegt der Grund dafür, daß Gruppen von Übertragungskanälen für Wörter gerader Ordnung und Wörter ungerader Ordnung gesammelt werden, darin, daß dann, wenn die Datenfolgen verschachtelt sind, die Distanz zwischen den Aufzeichnungsstellen benachbarter geradzahliger und ungeradzahliger Wörter so groß wie möglich sein sollte. Am Ausgang der Verschachtelungseinrichtüng 1 treten die Wörter:: der 24 Kanäle in einem ersten Anordnungszustand auf. Von der Verschachtelungseinrichtüng 1 werden die entsprechenden PCM-Datenwörter wortweise an einen Codierer 8 abgegeben, der sodann erste PrüfWörter Q_12n' ^Qi2n+1^{f Q}12n+2 ^{Und Q}12n+3 ^er~ zeugt, wie dies in dem obigen Ausdruck durch p, g, r bzw. s veranschaulicht ist.

Ein die ersteh Prüfwörter enthaltender Fehlerkorrekturblock tritt dann wie folgt auf:

^(W12n-12'^{A; W}12n-12'^B;-^W12n+1^12^^{; W}12n+1-12'^B'' ί^Κ12η+4-12,^Α; ^¥12η+4-12·^Βί %2η+5-12^ ^W12n+5-12'^{B; !} ^W12n+8-12'^A; ^12η+8-12·^{Β; W}12n+9-12^^A--^^B ^Wl2n+2'^{A; W}12n+2'^B: W₁₂n+3'^{A; W}l2n+3^iB; ^W12n+6'^{A; W}12n+6'^{B; W}12n+7'^{A; W}l2n4-7'^B^ ^W12n+10'^{A; W}12n+10'^{B; W}12n+11'^{A; W}12n+11'^B; ^Ql2n^{; Q}12n+1^{; :Q}12n+2^{; Q}12n+3⁾

Der erste Codierer 8 führt seine Funktion dadurch aus, daß die ersten Prüfwörder Q₁₂ bis Q-« .., entsprechend der Anzahl der Wörter eines Blockes (n=28), der Bitlänge m des jeweiligen Wortes (m=8) und der Anzahl.der Prüfwörter (k=4) berechnet werden.

Die 24 PCM-Datenwortfolgen und die 4 Prüfwortfolgen werden dann an eine Verschachtelungseinrichtüng 9 abgegeben. In dieser Verschachtelungseinrichtüng 9 werden die relativen

IZJ3 /ö

Positionen bzw. Lagen der Kanäle so geändert, daß die Wortfolgen zwischen den PCM-Datenfolgen, die die geradzahligen Wörter bilden, und den PCM-Datenfolgen, die die ungeradzahligen Wörter bilden, untergebracht werden. Danach wird ein Verzögerungsvorgang für diese verschachtelten Folgen durchgeführt. Dieser Verzögerungsvorgang wird in 27 Übertragungskanälen ausgeführt,und zwar beginnend mit dem zweiten Übertragungskanal, wozu Verzögerungsleitungen mit Verzögerungswerden 1D, 2D, 3D, 4D, ... 26D bzw. 27D verwendet werden. (Dabei bedeutet D einen Einheits-VerzÖgerungswert.)

Am Ausgang der Verschachtelungseinrichtung 9 treten 28 Datenwortfolgen in einem zweiten Anordnungszustand auf. Die Datenwörter werden wortweise aus den betreffenden Datenfolgen herausgenommen und einem Codierer 10 zugeführt, der dann die zweiten Prüfwörter P₁₂ , P-j₂n+1' ^P12n+2 ^und ^P12+3 ^erzeu9^t» und zwar in derselben Art und Weise, wie die Prüfwörter Q_12n' ^bis °-|2n+3'

So v/wie oben erläutert, gibt der Codierer 8 die obigen ersten Prüfwörter entsprechend den Parametern n= 28, m=8 und k-4 ab, und der entsprechende Codierer 10 stellt die zweiten PrüfWörter entsprechend den Parametern n=32,

m=8 und k=4 zur Verfügung.

Ein Fehlerkorrekturblock, der die zweiten Prüfwörter umfaßt und der aus 32 Wörtern besteht, wird wie folgt gebildet:

^(W12n-12'^A* ^W12n-12(EH-I) '^{B; W}12n+1-12(2IH-I) '^A; ^W12n+l-12(3rH-l)'^B;

^W12n+4-12(4D+l)'^{A; W}12n+4-12(5EH-I) ^)B; ^Wl2n+5-12(6m-l)'^{A; W}12n+5-12(7lH-l)'^B; *** ^; . ^Ql2n-12(12D)^{; Q}12n4-1-12(13B) ^{; Q}12n+2-12(14D);

^Q12n+3-12C15D)^; """ ^W12n+10-12(24D) '^A; ^W12n+10-12(25D)'^{B; W}12n+ll-12(25D) ^)A;

^B^ ^P12n_; ^P12n4-1^{; P}12n-f2^{; P}12n+3⁾ ν

Danach ist eine VerSchachtelungseinrichtung 11 vorgesehen, die Verzögerungsleitungen von einer Wortverzögerüng für die geradzahligen Übertragungskanäle der 32 Datenfolgen umfaßt, welche die ersten und zweiten Prüfwörter einschliessen. Außerdem sijid Inverter 12, 13, 14 und 15 zur Invertierung der zweiten PrüfWortfolgen vorgesehen. Die Verschachtelungseinrichturig 11 dient dazu, zu verhindern, daß über die Grenzen zwischen den Blöcken auftretende Fehler so viele Wörter beeinflussen, daß es unmöglich wird, diese zu korrigieren. Die Inverter 12, 13, 14 und 15 dienen dazu, den fehlerhaften Betrieb zu vermeiden, bis sämtliche Daten in einem Block zu "0" gemacht sind, und zwar durch das Auftreten eines Ausfalls während der Übertragung. Dies bedeutet, daß dann, wenn ein Ausfall bzw. Aussetzer auftritt, die invertierte Prüfwortfolge in dem Wiedergabesystem genau unterschieden wird. Aus demselben Grund können Inverter für die erste Prüfwortfolge vorgesehen sein.

Die schließlich abgeleiteten 24' PCM-Datenfolgen . und die 8 Prüfwortfolgen werden in Serienform als 32-Wort-Blöcke abgegeben, undei'n Synchronisiersignal von 16 Bits wird den resultierenden Seriendaten am Anfang hinzugefügt, um einen übertragurigsblock zu bilden, der in Fig. 2 veranschaulicht ist. Der so gebildete Block wird über ein über-

- 25-

tragungsmediuin oder einen Übertragungsträger übertragen. Gemäß Fig. 2 ist das" von dem i-ten Übertragungskanal bereitgestellte Wort^U bezeichnet.

Praktische Beispiele des Übertragungsmediums oder Übertragungsträgers für . das übertragene Signal können ein Magnetband in einer Magnetbandaufnahme- und wiedergabeanordnung, eine Platte bzw. Scheibe für "die Verwendung in einer Drehplattenanordnung oder einen entsprechenden Aufzeichnungsträger -einschließen»

Die wiedergegebenen Daten jedes der 32 Wörter jedes Blockes des übertragenen Signals werden dem Eingang eines in Fig. dargestellten Fehlerkorrektur-Decoders zugeführt. Die übertragenen Daten, die von dem Fehlerkorrektur-Decoder aufgenommen werden, können ein oder mehrere Fehler enthalten, da die Eingangsdaten wiedergegebene Daten sind. Wenn kein Fehler vorhanden ist/ dann werden die 32 Wörter dem Eingang des Decoders koinzident mit den 32 Wörtern zugeführt, die am Ausgang des Fehlerkorrektur-Codierers auftreten. In dem Fehlerkorrektur-Decoder wird ein zu dem entsprechenden Verschachtelungsvorgang in dem Codierer komplementärer Ent- . Schachtelungsvorgang ausgeführt, um die Daten in ihre ur-. sprüngliche Reihenfolge bzw. Ordnung zurückzuführen. Wenn dabei ein Fehler auftritt, wird der Fehlerkorrekturvorgang ausgeführt, nachdem die Daten in die ursprüngliche Ordnung bzw. Reihenfolge wieder zurückgebracht sind. .

Zunächst ist, wie in Fig. 3 gezeigt, eine. Entschachtelungs- " einrichtung 16 vorgesehen, in der Verzögerungsleitungen, die jeweils eine Verzögerung entsprechend einem Wort hervorrufen, für die ungeradzahligen Übertragungskanäle vorgesehen sind. Außerdem sind Inverter 17, 18, 19.und 20 vorgesehen, die die empfangenen zweiten PrüfWortfolgen invertieren. Die Ausgangssignale der Entschachtelungseinrichtung 16 und der Inverter 17 bis 20 werden einem ersten Decoder 21 zugeführt.

In diesem ersten Decoder 21 werden Syndromsignale S..Q, ^S11'
S₁₂ und S₁₃ entsprechend einer Matrix erzeugt, wie entsprechend der Reed-Solomon-Paritätsdetektormatrix H₁ (Fig.4)
durch idie 32 Eingangswörter V , wie dies in Fig. 4 veranschaulicht ist. Die oben erwähnte Fehlerkorrektur wird auf
der Grundlage der. Syndrome S_1Q bis S₁₃ ausgeführt. In Fig. 4
ist <* ein Element von GF (2 ) und eine Wurzel von F(x) =
χ +x +k +x +1. Der Decoder 21 leitet die korrigierten
24 PCM-Datenfolgen und die 4 ersten PrüfWortfolgen bzw.
Prüfwortreihen ab. Bei jedem einzelnen Wort der Dätenfolgen ' _; wird ein Zeiger oder ein Fehl er detektor code (zumindest 1 Bit) | hinzugefügt, um anzuzeigen, ob ein Fehler in dem zugehörigen
Wort (Zeiger ist "1") oder nicht (Zeiger ist "0") vorhanden
ist. Gemäß Fig. 4 und 5 und ferner gemäß der folgenden Be- I Schreibung wird das empfangene eine Wort Wi lediglich als j Wi bezeichnet. \

Die Ausgangsdatenfolgen von dem Decoder 21 werden einer *

Entschachtelungseinrichtung 22 zugeführt, die dazu dient, ,

den durch die Verschachtelungseinrichtung 9 in dem Fehler- |

korrektur-Codierer ausgeführten Verzögerungsvorgang zu

kompensieren. Die betreffende Einrichtung weist entspre-- ;

chende Verzögerungsleitungen mit unterschiedlichen Ver- ■

zögerungsbeträgen 27D, 26D, 25D ... 2D und 1D für die ■ ·

ersten bis 24 Übertragungskanäle auf. Das Ausgangssignal

der Entschachtelungseinrichtung 21 wird einem zweiten De- I

coder 23 zugeführt, in welchem die Syndrome S_2or ^S21' ^22

und S₂₃ in Übereinstimmung mit einer Matrix, wie der !

Reed-Solomon-Paritätsdetektormatrix H₀ (Fig.5) erzeugt j

werden. Die 28 Wörter V_T, wie sie in Fig. 5 gezeigt sind,

werden der betreffenden Anordnung zugeführt, und die :

oben erwähnte Fehlerkorrektur kann auf der Grundlage der i

i Syndrome S₂₀ big S₃₃ ausgeführt werden. J

¹ i

Der Decoder 23 löscht den Zeiger, der sich auf jedes Wort j bezieht, dessen Fehler korrigiertest. Der betreffende

ό ι ζ

• ♦ *

- 3Ö -

Decoder löscht indessen nicht den Zeiger, der sich auf irgendein Wort bezieht, dessen Fehler nicht korrigiert werden kann.

Die am Ausgang des Decoders 23 auftretenden. Datenfolgen werden einer Entschachtelungseinrichtung 24.zugeführt, die eine Entschachtelung bezüglich geradzahliger und ungeradzahliger Kanäle bzw. Signale vornimmt und .in der die PCM-Datenfolgen, bestehend aus den geradzahligen Wörter und den ungeradzahligen Wörtern so neu angeordnet werden, daß sie in abwechselnden Übertragungskanälen'untergebracht sind. Die Verzögerungsleitungen mit einer 1-Wort-Verzögerung sind für die.PCM-Datenfolgen vorgesehen, die aus ungeradzahligen Wörtern bestehen. Dadurch wird die entsprechende Operation kompensiert, die in dem Codierer vor der" Übertragung ausgeführt wird. Am Ausgang der Entschachtelungseinrichtung 24 werden die PCM-Datenfolgen zur Verfügung gestellt, die den ursprünglichen Anordnungszustand aufweisen, wobei die bestimmte Reihenfolge gänzlich wieder hergestellt ist, wie bei dem digitalen Signal, bevor der Fehlerkorrektur-rCodierer auf dieses Signal eingewirkt hat.

Obwohl in Fig. 3 nicht dargestellt, ist vorzugsweise in der nächsten Stufe auf die Entschachtelungseinrichtung 24 folgend eine Kompensationsschaltung vorgesehen, um nicht korrigierbare Fehler zu kompensieren. So kann beispielsweise eine' * Mittelwertinterpolation benutzt werden, wenn Fehler durch die Decoder 21 und 23 nicht korrigiert werden, so daß jegliche verbleibende Fehler ausgeblendet; und unauffällig " werden. ' . ·

Bei dem in Fig. 3 dargestellten Ausführungsbeispiel der Erfindung wird ein 1-Wort-Fehler· !.durch den ersten Decoder 21 korrigiert. Wenn festgestellt wird, daß mehr als zwei Wort- ' fehler in einem Fehlerkorrekturblock vorhanden sind, dann

• M · "

- 31; -

wird der Zeiger von zumindeste einem Bit sämtlichen 28 Wörtern des Fehlerkorrekturblocks hinzugefügt, d.h. sämtlichen Wörtern des 32-Wort-Blocks, mit Ausnahme der Prüfwörter, um nämlich das Vorhandensein von Fehlern anzuzeigen, wie dies oben ausgeführt worden ist. Dieser Zeiger ist eine "1", wenn ein Fehler vorhanden ist, während er eine "0" dann ist, wenn kein Fehler vorhanden ist. In dem Fall, daß ein Wort

es« 8 Bits umfaßt, wird der Zeiger als höheres Bit,als/aas Bit höchster Wertigkeii^hinzugefügtf, so daß ein Wort aus 9 Bits besteht. Sodann werden die Wörter durch die -Entschachtelungseinrichtung 22 verarbeitet und danach dem zweiten Decoder 23 zugeführt.

In diesem Decoder 23 wird der Fehler unter Heranziehung der Anzahl von Fehlerwörtern in dem ersten Fehlerkorrekturblock korrigiert, was durch den Zeiger oder die Fehlerstelle angezeigt wird.

In Fig. 6 ist ein Flußdiagramm der Fehlerkorrekturoperation veranschaulicht, die durch den zweiten Decoder 23 ausgeführt wird. Gemäß Fig. 6 und gemäß der folgenden Beschreibung dazu wird die Anzahl der fehlerhaften Wörter durch die Zeiger mit N ausgedrückt, und die Fehlerstelle wird durch die Zeiger Ei

ausgedrückt. Ferner bedeutet in Fig. 6 ein Y die Angabe "ja" und N bedeutet die Angabe "nein".

(1) Das Vorhandensein oder Fehlen eines Fehlers wird durch die Syndrome S_2öbis S₃₃ bestimmt. Wenn S₃₀ = S₂.. - S₂₂ ⁼ ° ist, dann wird entschieden, daß kein Fehler vorhanden ist. Zu diesem Zeitpunkt wird überprüft, ob die Beziehung N - Z₁ erfüllt ist oderjnicht. Wenn N - z- ist, dann wird entschieden, daß kein Fehler vorhanden ist. Sodann werden die Zeiger in dem Fehlerkorrekturblock gelöscht ("0"). Wenn demgegenüber N ^Z-J ist, dann wird die Fehlerermittelung durch die Syndrome als fehlerhaft entschieden, und die Zeiger werden unverändert beibehalten. Alternativ dazu werden die Zeiger für

ο ι L ο α / ο

sämtliche Wörter in dem Block zu "1" gemacht. In dem zuletzt genannten Fall wird der Wert von Z₁ relativ groß gewählt, beispielsweise mit 14.

(2) In dem Fall, daß ein Fehler vorhanden ist, wifddurch die Berechnung der Syndrome geprüft, ob der Fehler ein 1-Wort-Fehler ist oder nicht. Im Falle eines 1-Wort-Fehlers wird die Fehlerstelle i erhalten. Dabei wird festgestellt,ob die Fehlerstelle i, die durch die Berechnung des Syndröms erhalten ist, mit der Fehlerstelle übereinstimmt, die durch die Zeiger angezeigt wird. Wenn die Vielzahl von' Fehlerstellen durch die. Zeiger angezeigt wird, wird überprüft/ welche Fehlerstelle i mit welcher der Vielzahl von Fehlerstellen überstimmt, die durch die Zeiger angezeigt werden. Wenn i= Ei gilt, dann wird überprüft, ob N = z_o ist oder nicht, wobei z₀ beispielsweise 10 ist. Wenn N-Z₀ ist, dann wird der

Jr *

Fehler als 1-Wort-Fehler bewertet, und dann wird ein Wortfehler korrigiert. Wenn N > z_o ist, dann ist es möglich,

Xr **

daß der Fehler unrichtigerweise als Wort mit einem Fehler entschieden worden ist. Demgemäß bleiben die Zeiger unverändert, oder, alternativ dazu werden sämtliche Wörter als · fehlerhaft angesehen,und die entsprechenden Zeiger dieser Wörter werden zu "1" gemacht.

Im Falle von i ^ Ei, wird überprüft, ob N = Z₃ ist oder nicht, wobei Z₃ einen relativ kleinen Wert, beispielsweise · 3, aufweist. Wenn N = Z₃ erreicht ist, wird ein 1-Wort-Fehler an"der Fehlerstelle i durch die Berechnung des Syndröms korrigiert.

Im Falle von N > Z₃ wird weiter geprüft, ob N ^ Z₄ erfüllt ist oder nicht. Wenn Z₃ <· N = Z₄ erfüllt ist, bedeutet dies, daß - obwohl die Entscheidung eines 1—Wort-Fehlers durch das Syndrom fehlerhaft ist - N zu klein ist. In diesem Falle !/werden, daher die Zeiger für sämtliche Wörter des Blockes zu "1" gemacht. Demgegenüber bleibt im

Falle N > Z₄ jeder Zeiger unverändert. In diesem Fall beträgt ζ λ beispielsweise 5. ·

(3) In dem Fall, daß kein Einzelwortfehler vorhanden ist, wird entschieden, ob N =z₅ gilt oder nicht. Wenn N-Z₅ erfüllt ist, dann ist der Zeiger schlecht oder leidet an Zuverlässigkeit, so daß die Zeiger für sämtliche Wörter zu "1" gemacht werden. Wenn N > Z₅ gilt, dann bleiben jedoch die Zeiger so wie sie sind.

(4) Wie in Fig. 6 durch eine gestrichelte Linie veranschaulicht, ist es möglich, Fehler'bis zu M Wörtern unter Heranziehung der.durch den Zeiger bezeichneten Fehlerstelle zu korrigieren. Dabei können bis zu vier Wortfehler korrigiert werden, wobei jedoch ein Fehlerlöschverfahren eine·fehlerhafte Korrektur nicht vermeiden kann. Unter Berücksichtigung der Zeit und der Komplexheit, die für eine Korrekturoperatxon erforderlich ist, wird daher M mit etwa 2 gewählt. Sodann werden zwei Wortfehler bezüglich der Fehlerstellen i und j korrigiert, wie dies durch die Zeiger angezeigt wird. Im . Falle von N φ M b;leiben die Zeiger unverändert, oder die Zeiger für sämtliche Wörter werden so geändert, wie jene Zeiger, die Fehler anzeigen. ,

Bei der obigen Beschreibung sind die praktischen Werte der Vergleichswerte Z* bis Z₅ in bezug auf die Anzahl N der auf Fehler in einem Block hinzeigenden Zeiger lediglich beispielsweise angegeben worden. Bei dem obigen Beispiel weist der Fehierkorrektur-Code einen möglichen Nachteil insofern auf, als ein Block mehr als fünf Wortfehler enthält. In diesem Fall kann in unrichtiger Weise eine Fehlerfreiheit entschieden werden. Außerdem kann in dem Fall, daß ein Block' mehr als 5 Wortfehler enthält, in unrichtiger Weise entschieden werden, daß dieser Block lediglich einen Wortfehler enthält. Demgemäß können die Vergleichswerte in geeigneter Weise unter Berücksichtigung der Wahrscheinlichkeit gewählt

werden, daß das oben erläuterte Übersehen eines Fehlers oder eine fehlerhafte Korrektur auftreten.

Bei dem obigen Ausführungsbeispiel der Erfindung kann der Codierer - obwohl bis zu ein Wortfehler in dem ersten ' Decoder korrigiert wird.- so modifiziert werden, daß bis zu zwei Wortfehlern korrigiert werden. Außerdem können Zeiger hinzugefügt werden, die das Vorhandensein von Fehlern in sämtlichen Wörtern in dem Fehlerkorrekturblock.anzeigen, in welchem das fehlerkorrigierte Wort enthalten ist. In entsprechender Weise können bis zu zwei Wortfehler in dem zweiten Decoder korrigiert werden.

Nunmehr wird ein mehr praktisches Ausführungsbeispiel des oben beschriebenen Fehlerkorrekturverfahrens unter Bezugnahme auf Fig. 7A und 7B erläutert. Ein Datenblock wird im Schritt C. in dem ersten Decoder 21 verarbeitet, in welchem der Zustand eines Fehlers dadurch bewertet bzw. entschieden wird, daß das obige Fehlerstellenpolynom und das Fehlersnydrom herangezogen werden. / ; '

(1) In dem Fall, daß ein Block als fehlerfrei bewertet bzw. entschieden wird;, wird kein Zeiger hinzugefügt, und die Daten bleiben für die zweite Decodierung C₂ unverändert.

(2) Im Falle eines 1-Wort-Fehlers wird die Fehlerstelle erhalten. Wenn die Fehlerstelle i kleiner als oder gleich " 31 ist, wird das eine Wort korrigiert. Wenn die Fehlerstelle i höher ist als 31, werden jedoch vier Wortfehler fehlerhaft als ein Wortfehler bewertet. Demgemäß werden Zeiger zu sämtlichen Wörtern hinzugefügt, und sodann werden die Daten in der nächsten Stufe C₃ decodiert.

(3) Im Falle von zwei Wortfehlern werden die Fehlerstellen berechnet. Wenn die Fehlerstellen i jeweils als unterhalb von 31 liegend oder gleich 31 bestimmt sind, werden die beiden Wörter korrigiert, und außerdem werden Zeiger sämtlichen Wörter hinzugefügt. Wenn die. Fehlerstellen i jeweils höher sind als 31, dann werden mehr als drei Wortfehler in fehler-

hafter Weise als 2-Wortfehler bewertet. Demgemäß werden sämtlichen Wörter Fehleranzexgezeiger gegeben, und danach werden die betreffenden Wörter der nächsten Decodierungsstufe C₂ ausgesetzt. - ι

(4) Im Falle des Vorliegens von mehr drei Wortfehlern wird keine Korrekturoperation ausgeführt. Vielmehr werden Fehleranzeigezeiger sämtlichen Wörtern hinzugefügt, und sodann werden die Daten der nächsten Decodierungsstufe C₂ ausgesetzt.

In dem zweiten Decoder 23 werden in entsprechender Weise wie in dem ersten Decoder 21 zunächst die Eigenschaft jedes Fehlers durch das Fehlerstellenpolynom und die- Fehlersyndrome bewertet. Dies wird unter Bezugnahme auf Fig. 7B erläutert. "'·"'.

(1) Im Falle keines ermittelten Fehlers wird dann, wenn der dem ersten Decoder hinzugefügte Zeiger vorhanden ist (d.h. eine "1" ist), dieser Zeiger gelöscht (d.h. zu "0" gemacht). .

(2) Im Falle eines 1-Wort-Fehlers wird die Fehlerstelle berechnet. Wenn die Fehlerstelle kleiner als 27 oder gleich . 27 ist, dann wird das fehlerhafte Wort korrigiert, und der durch den ersten Decoder 21 hinzugefügte Zeiger wird gelöscht. Wenn jedoch die Fehlerstelle höher ist als 27, wird keine Korrekturoperation ausgeführt, und der zuvor hinzugefügte Zeiger bleibt so wie er ist.

(3) Im Falle von zwei Wortfehlern werden die Fehlerstellen i und j berechnet. Wenn die Fehlerstelle i und· j beide größer sind als 27, dann werden mehr als drei Wortfehler in fehlerhafter Weise als 2-Wort-Fehler bewertet. Zu diesem Zeitpunkt wird jedoch die Anzahl der in dem ersten Decoder 21 hinzugefügten Zeiger überprüft. Wenn die Anzahl der Zeiger den Wert 2 übersteigt, werden die Zeiger unverändert festgehalten. Wenn die Anzahl der Zeiger kleiner ist als 2 oder sogar zwei Wortfehler ermittelt werden,

werden Zeiger sämtlichen Wörtern hinzugefügt, da die Daten des gesamten Blocks unzuverlässig sind. Sogar dann, wenn die Fehlerstellen 1 , j kleiner sind als 27 und die Anzahl der in dem ersten Decoder 21 hinzugefügten Zeiger geringer ist als 3, werden die Zeiger unverändert festgehalten. Wenn • die Anzahl der Zeiger höher ist als 4, wird außerdem die Fehlerstelle i oder j, die in dieser Stufe erhalten wird, mit dem Zeiger verglichen, der dem ersten Decoder 21 hinzugefügt ist. ;

(a) Wenn zwei Wörter nicht koinzidieren, wird keine Fehlerkorrekturoperation ausgeführt, und die Anzahl der Zeiger wird überprüft. Wenn die Anzahl den Wert 2 übersteigt, werden die hinzugefügten Zeiger unverändert festgehalten. Wenn jedoch die Anzahl der Zeiger geringer ist als 2, werden Zeiger zu sämtlichen Wörtern hinzuaddiert.

(b) Wenn lediglich eines der Wörter übereinstimmt, wird ebenfalls die Anzahl der Zeiger überprüft. Wenn die Anzahlen Wert 3. übersteigt,;beispielsweise 4 ist, werden .die hinzugefügten Zeiger unverändert beibehalten. Wenn jedoch die Anzahl geringer ist als 3, werden Zeiger zu sämtlichen Wörtern hinzugefügt.

(c) Wenn von zwei Wörtern beide übereinstimmen, dann werden die beiden Wörter korrigiert, und danach werden die Zeiger gelöscht.

t4) In dem Fall, daß ein Fehler so bewertet wird, daß er mehr als drei Wörter betrifft, wird die Anzahl der Zeiger überprüft. Wenn die Anzahl den Wert 2 übersteigt," werden die hinzugefügten Zeiger nicht geändert; Demgegenüber, werden in dem Fall, daß die Anzahl geringer ist als 2, sämtlichen Wörtern Zeiger hinzugefügt.

Später während des Decodierungsvorgangs,.wie er oben erwähnt worden ist, werden die mit Zeigern versehenen Wörter als nichtkorrigierbar, beispielsweise durch Verschachtelung, 'kompensiert.

3123973.-. ■

Bei dem in Fig. 3 dargestellten Fehlerkorrektur-Decoder wird jeweils eine Fehlerkorrektur unter Heranziehung der ersten Prüfwörter Q_12n, Q₁-J₁₁₊₁, Q_12n+2 und Q_12n+3 sowie eine Fehlerkorrektur unter Heranzeihung der zweiten Prüf-Wörter P_12n, P_12n+1, P_12n+2 und P_12n+3 ausgeführt. Wenn

jedoch die obigen Fehlerkorrekturen zwei- oder mehrmals (in der Praxis etwa zweimal) ausgeführt werden, kann die Fehlerkorrekturfähigkeit beträchtlich' gesteigert werden, da das korrigierte Ergebnis jeweils einen geringeren Fehler aufweist. In dem Fall, daß ein zusätzlicher Decoder in der letzteren Stufe vorgesehen ist, ist es, wie oben ausgeführt, erforderlich, daß das Prüfwort in einem entsprechenden Decoder korrigiert wird, der zusätzlich zu den Decodern 21 und 23 vorgesehen ist.

Bei dem obigen Beispiel unterscheidet sich bei dem Verzögerungsvorgang in .der Verschachtelungseinrichtung 9 der Verzögerungswert von einem Kanal zum nächsten um einen .konstanten Änderungswert D. Es ist jedoch ebenso möglich, eine abweichende Änderung in der Verzögerungsgröße anstatt die obige konstante Änderung zu benutzen. Ferner sind die zweiten PrüfWörter Pi solche Fehlerkorrekturcode, die nicht nur aus den PCM-Datenwörtern gebildet werden, sondern auch aus den ersten Prüfwörtern Qi. In entsprechender Weise ist es möglich, daß die ersten PrüfWörter Qi aus Worten gebildet werden, die in den zweiten PrüfWörtern Pi enthalten sind. Zu diesem Zweck kann ein Rückkoppelungsverfahren angewandt werden, so daß die zweiten Prüfwörter Pi dem Decoder zurückgeführt werden, der die ersten PrüfWörter erzeugt.

Aus der vorstehenden Beschreibung eines Ausführungsbeispiels der Erfindung dürfte verständlich sein, daß jeglicher Burst-Fehler durch eine Querverschachtelungsoperation derart verteilt wird, daß sowohl zufällige Fehler als auch Burst-Fehler wirksam durch das Verfahren gemäß der Erfindung korrigiert werden können.

Wenn ein Fehler in der ersten Decodierungsstufe ermittelt wird, wird im übrigen ein das Vorhandensein des Fehlers anzeigender Zeiger dem Wort hinzugefügt. In dem Fall, daß das Vorhandensein oder Fehlen eines Fehlers auf die Decodierung in einem zweiten Decoder festgestellt wird, ist die Möglichkeit ·, daß die Fehlerermittelungi bei der zweiten Decodierung fehlerhaft ist, nicht nur durch das berechnete Syndrom vermieden, sondern außerdem durch die Bewertung der Anzahl der Zeiger in federn von dem ersten Decoder abgegebenen Block. Auf diese Art und Weise ist die Wahrscheinlichkeit vermindert, daß ein ermittelter Fetaler übersehen wird. Dadurch ist die Aussicht dafür herabgesetzt, daß ein Fremdton bei der Übertragung beispielsweise eine's PCM-Tonsignals, erzeugt wird. ' . · ' .

Patentanwalt

Claims

Patentansprüche

Verfahren zum Decodieren einer übertragenen digitalen Information unter Korrektur von in dieser Information infolge der Übertragung aufgetretenen Fehlern/ wobei die Information blockweise in Form von digitalen Datenwörtern aufgenommen und einem ersten Decoder in Form von ersten Fehlerkorrekturblöeken zugeführt wird, die aus einer Vielzahl von Informationswörtern, einer Reihe von ersten Prüfwörtern und einer Reihe von zweiten Prüfwörtern bestehen, dadurch gekennzeichnet, daß die empfangenen digitalen Datenwörter in dem ersten Decoder decodiert werden,

daß die decodierten digitalen Informationswörter und die ersten PrüfWörter dadurch korrigiert werden, daß Fehlersyndrome erzeugt werden, wozu die zweiten Prüfwörter, die korrigierten und decodierten digitalen Informationswörter herangezogen werden, die einen Block aus verschachtelten Wörtern bilden, daß jedem Wort der Wörter eines Blockes von verschachtelten Wörtern ein Zeigercode hinzugefügt wird, durch den angegeben wird, ob ein unkorrigierter Fehler in

derartigen Wörter verblieben ist oder nicht, daß die Wörter jedes derartigen Blockes der verschachtelten Blöcke in einer Entschachtelungsstufe um unterschiedliche Beträge derart verzögert werden, daß die betreffenden Wörter in einer unterschiedlichen Anordnungsreihenfolge entschachtelt und ein zweiter Fehlerkorrekturblock bereitgestellt werden, daß die digitalen Informationswörter jedes zweiten Fehlerkorrekturblocks in einem zweiten Decoder dadurch decodiert werden, daß Fehlersyndrome unter Heranziehung der ersten PrüfWörter erzeugt werden, wobei in dem Fall, daß zumindest ein derartiges Wort als fehlerhaft bestimmt wird, zumindest ein solches fehlerhaftes Wort durch die Syndrome und die ersten Prüfwörter korrigiert wird, wobei sodann bezüglich jedes zweiten Fehlerkorrekturblockes , in dem zumindest ein Wort als fehlerhaft bestimmt wird, die durch die Zeigercodes angezeigte Anzahl von fehlerhaften Wörtern mit einem bestimmten Wert verglichen wird, und wobei in dem Fall, daß die betreffende Zahl kleiner ist als der genannte Wert, die den korrigierten fehlerhaften Wörtern zugehörigen Zeigercodes gelöscht werden, während in dem Fall, daß' die betreffende Zahl den betreffenden Wert übersteigt, die Zeigercodes ungelöscht verbleiben, und däß danach jegliche durch die Zeigercodes bestimmten nicht korrigierten fehlerhaften Wörter kompensiert werden.
2. Verfahren nach Anspruch 1, dadurch gekennzeichnet, daß in dem:''Fäll, daß sämtliche Wörter in dem zweiten Fehlerkorrekturblock als fehlerfrei·bestimmt werden, sämtliche zugehörigen Zeigercödes in dem Fall ungelöscht zurückbelassen werden, däß die genannte Zahl den genannten bestimmten Wert übersteigt. .

3123973
3. Verfahren nach Anspruch 1, dadurch gekennzeichnet, daß. in dem Fall, daß sämtliche Wörter in dem Fehlerkorrektürblock als fehlerfrei bestimmt werden und die genannte Zahl den genannten bestimmten Wert übersteigt, sämtlichen Wörtern in einem solchen Block ein Zeigercode gegeben wird, der das Vorliegen eines nichtkorrigierten Fehlers anzeigt.
4. Verfahren nach Anspruch 1, dadurch gekennzeichnet, daß in dem Fall, daß eine bestimmte Anzahl von Wörtern in irgendeinem zweiten Fehlerkorrekturblock unter Heranziehung der Fehlersyndrome in dem zweiten Decoder als Fehler enthaltend bestimmt ist und daß die durch die Zeigercodes angezeigte Anzahl von Fehlerwörtern in einem solchen Block geringer ist als eine bestimmte Größe, sämtlichen Wort em in einem solchen Block ein Zeigercode zur Anzeige des nichtkorrigierten Fehlers gegeben wird.
5. Verfahren nach Anspruch 1, dadurch gekennzeichnet, daß in dem Fall, daß eine Vielzahl von Wörtern des zweiten Fehlerkorrekturblockes als fehlerhaft bestimmt wird und daß die Lage jedes derartigen fehlerhaften Wortes durch die Verwendung der Zeigercodes bestimmt wird, die fehlerhaften Wörter korrigiert werden und daß in dem Fall, daß die durch die Zeigercodes angezeigte Anzahl von fehlerhaften Wörtern verschieden ist von der betreffenden Vielzahl,, die den Wörtern in dem zweiten Fehlerkorrekturblock zugehörigen Zeigercodes unverändert verbleiben, während in dem Pail, daß die Anzahl gleich der betreffenden Vielzahl ist, die Zeigercodes gelöscht werden.
6. Verfahren nach Anspruch 5, dadurch gekennzeichnet, daß die betreffende Vielzahl auf nicht mehr als zwei fehlerhafte Wörter begrenzt wird.
7. Verfahren nach Anspruch 1, dadurch gekennzeichnet, daß die in dem ersten Decoder ausgeführte Decodierung die Bestimmung der Wortstelle jeglichen fehlerhaften Wortes in dem ersten Fehlerkorrekturblock umfaßt, daß außerdem die Wortstelle mit einer bestimmten Zahl verglichen wird, und daß in dem Fall, daß die ermittelte Wortstelle größer ist als eine bestimmte Zahl, sämtlichen Wörtern in einem solchen Block ein auf einen unkorrigierten Fehler hinzeigender Zeigercode gegeben wird.
8. Verfahren nach Anspruch 7, dadurch gekennzeichnet, daß jedem Wort in dem genannten Block eine Wortpositions-Reihenfolge gegeben wird und daß die genannte bestimmte Zahl gleich der Wortpositions-Reihenfolge des höchsten Wortes in dem ersten Fehlerkorrekturblock gewählt wird.
9. Verfahren nach Anspruch 7, dadurch gekennzeichnet, daß bei der in dem zweiten Decoder ausgeführten Decodierung die Wortstelle jeglichen fehlerhaften· Wortes in dem zweiten Fehlerkorrekturblock bestimmt wird, daß die betreffende Wortstelle mit einer weiteren bestimmten Zahl verglichen wird und daß in dem Fall, daß die er-

. mittelte Wortstelle größer ist als" die genannte andere bestimmte Zahl, sämtlichen Wörtern, in dem zweiten Fehlerkorrekturblock ein Zeigercode gegeben wird, durch den das Vorliegen eines nichtkorrigierten Fehlers angezeigt .wird. '
10. Verfahren nach Anspruch?, dadurch gekennzeichnet, daß' jedem Wort in dem zweiten Fehlerkorrekturblock eine Wortpositions-Reihenfolge gegeben wird, und daß die ge- " nannte andere bestimmte Zahl gleich der Wortpositions-Reihenfolge des höchsten Wortes in dem zweiten Fehlerkorrekturblock gewählt wird.

te«· * * · *ϊ ♦ Λ ·

• « ♦ ft Λ
11. Verfahren nach Anspruch 1, dadurch gekennzeichnet, daß bei der Decodierung in dem zweiten Decoder ferner die Wortstelle jeglicher fehlerhafter Wörter innerhalb des zweiten Fehlerkorrekturblockes, berechnet wird, daß die berechnete Wortstelle mit einer durch den zugehörigen
Zeigercode angezeigten fehlerhaften Wortstelle verglichen wird und daß zumindest ein derartiges Wort in einer solchen fehlerhaften Wortstelle korrigiert wird.