CH653503A5

CH653503A5 - Fehlerkorrekturverfahren fuer die datenuebertragung.

Info

Publication number: CH653503A5
Application number: CH4065/81A
Authority: CH
Inventors: Yoichiro Sako; Kentaro Odaka
Original assignee: Sony Corp
Priority date: 1980-06-20
Filing date: 1981-06-19
Publication date: 1985-12-31
Also published as: DK158484B; SE451421B; IT1194806B; BE889322A; AU542192B2; DE3123978A1; BR8103912A; ATA275081A; JPH0353817B2; IT8122477A1; NL191104B; AU7200081A; NL8103002A; FR2485303A1; DK158484C; US4497058A; CA1169154A; ES8203543A1; AT378070B; DK270481A

Description

Die vorliegende Erfindung betrifft allgemein gesehen ein Fehlerkorrekturverfahren und insbesondere ein Fehlerkorrekturverfahren, das grosse Möglichkeiten zur Fehlerkorrektur sowohl von Büschelfehlern als auch von Zufallsfehlern aufweist, und das die Möglichkeit reduzieren kann, dass ein unkorrigierter Fehler übersehen wird.

In dem vom gleichen Anmelder angemeldeten US-Patentgesuch Nr. 218 256 wurde eine Datenübertragungsanlage

5

10

15

20

25

30

35

40

45

50

55

60

65

3

653 503

angegeben, welche wirksam ist für die Korrektur für Büschelfehlern, und zwar unter Verwendung der sogenannten Kreuz-verschachtelungstechnik. Bei dieser Kreuzverschachtelungs-technik werden Wörter in einem PCM-Datensignal in mehreren Folgen an mehrere Kanäle angelegt, die in einer ersten Anordnung ausgelegt sind, und werden an einen ersten Feh-lerkorrekturcoder angelegt, um daraus eine Folge von ersten Prüfwörtern zu erzeugen. Diese Folge von ersten Prüfwörtern und die Folgen von PCM-Datensignalen in den verschiedenen Kanälen werden dann in eine zweite Anordnung umgemodelt. Dann wird ein Wort in der zweiten Anordnung für jede der PCM-Datensignalfolgen in den verschiedenen Kanälen an einen zweiten Fehlerkorrekturcoder angelegt, um daraus eine Folge von zweiten Prüfwörtern zu erzeugen, so dass eine doppelte Verschachtelung (d.h. eine doppelte Neuanordnung) für jedes Wort ausgeführt wird. Der Zweck der doppelten Verschachtelung besteht darin, die Anzahl von fehlerhaften Wörtern in irgendeiner Gruppe von Wörtern, die in einem gemeinsamen Fehlerkorrekturblock enthalten sind, zu reduzieren, indem das in einem solchen Fehlerkorrekturblock enthaltene Prüfwort und die dazugehörigen PCM-Daten gestreut und dann übertragen werden. Dadurch werden solche fehlerhaften Wörter auf verschiedene Blöcke verteilt und kommen auf der Empfangsseite wieder in die ursprüngliche Anordnung zurück. Wenn also während der Übertragung ein Büschelfehler auftritt, dann wird der Büschelfehler verteilt. Wenn die obige Verschachtelung zweimal ausgeführt wird, werden die ersten und zweiten Prüfwörter je für die Korrektur von Wörtern in bestimmten Fehlerkorrekturblöcken verwendet. Daher ist es möglich, dass auch dann, wenn ein Fehler durch eines der ersten und zweiten Prüfwörter nicht korrigiert werden kann, der Fehler durch das entsprechende andere Prüfwort korrigiert werden kann. Daher ergibt sich mit dieser Technik eine beträchtliche Verbesserung der Fehlerkorrekturmöglichkeiten für Büschelfehler.

Es wird jedoch, auch wenn nur ein Bit eines Wortes als fehlerhaft entdeckt wird, das ganze Wort als fehlerhaft betrachtet. Daher ist, wenn das empfangene Datensignal eine relativ grosse Anzahl von Zufallsfehlern hat, die oben beschriebene Doppelverschachtelungstechnik nicht immer hinreichend wirksam zur Korrektur dieser Zufallsfehler.

Daher wird vorgeschlagen, die obenerwähnte Vielfachver-schachtelungstechnik mit einem Fehlerkorrekturcode zu kombinieren, der hohe Fehlerkorrekturmöglichkeiten aufweist, z.B. mit dem Reed-Solomon-Code (RS), Bose-Chaudhuri-Hocquenghem-Code (BCH) oder mit einer Variante eines b-Codes, welches K Wortfehler korrigieren kann, z.B. zwei Wortfehler in einem Block und der auch M Wortfehler korrigieren kann, z.B. drei oder vier Wortfehler, wenn die Position der Fehler bekannt ist.

Diese Fehlerkorrekturcodes ermöglichen eine Vereinfachung des Aufbaus eines Decoders, wenn nur ein Wortfehler zu korrigieren ist.

Im Falle, in welchem ein erster Decodierschritt für den zweiten Fehlerkorrekturblock ausgeführt wird, dann dieser in die erste Anordnung umgewandelt wird und ein nachfolgender Decodierschritt für den ersten Fehlerkorrekturblock durchgeführt wird, ist es möglich, dass selbst dann, wenn ein Fehler im nachfolgenden Decodieren vorhanden ist, dieser Block als fehlerfrei betrachtet wird oder der Fehler nicht detektiert wird. Daher tritt im Falle von z.B. PCM-Tonsigna-len, wenn Datensignale auftreten mit nicht festgestellten Fehlern, und die fehlerhaften Daten ohne Korrektur einer Digital/Analog-Wandlung unterworfen werden, im tonfrequenten Analog-Ausgangssignal ein Fremdton auf.

Es ist daher ein Zweck der vorliegenden Erfindung, ein verbessertes Verfahren zur Fehlerkorrektur vorzusehen, welches das Übersehen von Fehlern reduziert.

Ein weiterer Zweck besteht darin, ein Verfahren vorzusehen, bei welchem keine Fremdtöne entstehen, wenn ein ton-frequentes PCM-Signal übertragen wird.

Gemäss einem Aspekt der vorliegenden Erfindung wird ein Verfahren zur Fehlerkorrektur eines empfangenen übertragenen Datensignales, z.B. eines PCM-Tonsignales vorgesehen. Die Übertragung kann über einen Träger erfolgen, z.B. über eine Funkverbindung oder ein Kabel oder sie kann die Aufzeichnung des Signales auf ein magnetisches Band, eine optisch abzutastende Platte oder ein anderes Medium ein-schliessen. Die Daten werden als Blöcke von digitalen Datenwörtern empfangen und werden einem ersten Decoder als erste Fehlerkorrekturblöcke zugeführt, welche Blöcke eine Vielzahl von Informationswörtern, eine Folge von ersten Prüfwörtern und eine Folge von zweiten Prüfwörtern aufweisen. Die empfangenen Wörter werden darin decodiert, und die Informationswörter und die ersten Prüfwörter werden korrigiert durch Erzeugung von Fehlersyndromen unter Benützung der zweiten Prüfwörter. Ein Fehlerkennzeichen, z.B. ein zusätzliches Bit, wird den Wörtern zugefügt, um zu zeigen, dass in solchen Wörtern noch ein unkorrigierter Fehler verblieben ist. Zum Beispiel ist das Fehlerkennzeichen « 1 », wenn das zugehörige Wort unkorrigierte Fehler enthält, jedoch «0», wenn dies nicht der Fall ist. Dann werden die Wörter in einer Entschachtelungsstufe entschachtelt, indem die Wörter um unterschiedliche Beträge verzögert werden, und dann als zweite Fehlerkorrekturblöcke an einen zweiten Decoder angelegt. In diesem werden die Informationswörter decodiert durch Erzeugung von Fehlersyndromen unter Benützung der ersten Prüfwörter, während, falls festgestellt wird, dass Fehler vorhanden sind, die Wortposition von irgendwelchen fehlerhaften Wörtern innerhalb des zweiten Fehlerkorrekturblocks berechnet werden. Die berechnete Wortposition wird mit der Position des fehlerhaften Wortes verglichen, wie sie durch das zugehörige Fehlerkennzeichen angegeben wird und mindestens ein solches fehlerhaftes Wort wird an der Position des fehlerhaften Wortes korrigiert. Dann wird die Anzahl der fehlerhaften Wörter, wie sie durch die Fehlerkennzeichen angegeben werden, bestimmt, und dann wird diese Zahl mit einem vorbestimmten Wert verglichen. Wenn die Zahl kleiner ist als dieser Wert, dann werden die zu den korrigierten fehlerhaften Wörtern gehörenden Fehlerkennzeichen gelöscht, ist diese Zahl aber grösser als der genannte Wert, dann bleiben die Fehlerkennzeichen ungelöscht. Da die Daten dann als unzuverlässig betrachtet werden, kann man allen Wörtern in diesem Block ein Fehlerkennzeichen geben.

Danach werden die fehlerhaften Wörter (wie sie durch die Fehlerkennzeichen bestimmt werden) z.B. durch Interpolation kompensiert.

Ein Ausführungsbeispiel der Erfindung wird nun anhand der Zeichnung näher erläutert. In der Zeichnung zeigt:

Die Fig. 1, bestehend aus den Fig. 1A und 1B, ein Blockschema eines Beispiels eines fehlerkorrigierenden Coders, in welchem die vorliegende Erfindung angewendet wird;

die Fig. 2 die Anordnung eines Blocks von codierten Daten bei der Übertragung;

die Fig. 3, bestehend aus den Fig. 3A und 3B, ein Blockschema eines Beispiels eines fehlerkorrigierenden Decoders, in welchem die vorliegende Erfindung angewendet wird, und die Fig. 4, 5,6, 7A und 7B für die Erklärung der Arbeitsweise des fehlerkorrigierenden Decoders verwendete Diagramme.

Zunächst soll der bei der vorliegenden Erfindung verwendete Fehlerkorrekturcode erläutert werden. Bei dieser Diskussion wird der Fehlerkorrekturcode durch eine Vektordarstellung oder durch eine zyklische Gruppendarstellung ausgedrückt. Zuerst soll ein nichtreduzierbares Polynom F(x) von

5

10

15

20

25

30

35

40

45

50

55

60

65

653 503

4

m-ter Ordnung in einem Galois-Feld GF(2) betrachtet werden. Im Feld GF(2), das nur die Elemente «0» und «1» enthält, hat das nichtreduzierbare Polynom F(x) keine reelle Wurzel. Daher wird eine imaginäre (oder komplexe) Wurzel a betrachtet, welche die Bedingung F(x) = 0 erfüllt. Nun bilden 2m verschiedene Elemente 0, a, a2, a3,... a2m_I, von denen jedes eine Potenz von a ist und ein Element Null enthält, ein verlängertes Galois-Feld GF(2m). Dieses verlängerte Feld GF(2m) ist ein Polynom-Ring mit einem nichtreduzierbaren Polynom F(x) von m-ter Ordnung über dem Feld GF(2) als Modulo. Das Element von GF(2m) kann ausgedrückt werden als eine lineare Kombination von 1, a = [x], a2 = [x2],... am~l = [xm_ ']. Das heisst, diese Elemente können ausgedrückt werden als ao + ai[x] + a2[x2] +... + am_ i[xm~ ']

s15"1

2(n-2)

,2(n-2)

,(k-l)(n-l) (k-1)(n-2)

J * 1

.k-1 1

Weiter kann die Paritäts-Prüfmatrix H ähnlich ausgedrückt werden unter Verwendung der Matrix T, wie dies folgt:

= ao + aia + a2(x2 + ... am_|Ctm_l oder

(am_i, am_2,... a2, ai, ao)

wobei ao, ai,... am_i Elemente von sGF(2) sind.

Als Beispiel soll das verlängerte Feld GF(28) und als Modulo das Polynom F(x) = x8 + x4 + x3 + x2 + 1 betrachtet werden, wobei alle Variablen 8-Bit-Daten sind. Dieses Feld GF(28) kann wie folgt ausgedrückt werden :

a?x7 + aax6 + a5X5 + a4X4 + a3X3 + a2X2 + aix + ao oder

(a7, a6, as, a4, a3, a2, ai, ao)

Daher wird beispielsweise a? als bedeutsamstes Bit MSB und ao als am wenigsten bedeutsames Bit LSB betrachtet. Da an zu GF(2) gehört, sind seine Elemente entweder 0 oder 1.

Weiter wird vom Polynom F(x) die folgende Matrix T mit m Zeilen und m Kolonnen abgeleitet.

T +

0

1 0

0

1

0 0 0

Vi

I

fl-1 _2(n-1)

rr'"2

_2(n-2)

^1 T

I I

r(k-l)(n-l) T(k-1)(n-2)

T2 I

„k-1 j

Wobei I eine Einheitsmatrix von m Zeilen und m Kolon-30 nen ist.

Wie obenerwähnt, sind die Ausdrücke, die die Wurzel a verwenden im Grunde die gleichen wie jene, unter Benützung einer Erzeugungsmatrix T.

Wenn weiter der Fall, in welchem 4 (k = 4) Prüfworte 35 benützt werden, beispielhaft dargestellt werden soll, wird die Paritäts-Prüfmatrix H die folgende Form annehmen:

40

45

1

... 1

1

„n— 1

n-2

a a

• » • £

1

q2(n-1)

a2(n-2)

• • • 2 a

1

03(n-l)

a3(n-2)

3

• • • 0

1

In diesem Fall werden, wenn ein einzelner Block von empfangenen Daten als Kolonnenvektor v = (Wn_ i, Wn_2,. -Wi, Wo) ausgedrückt wird, wobei Wi = Wi + ei, ei ein Fehler-50 muster ist, vier Syndrome So, Si, S2 und S3, welche auf der Empfangsseite erzeugt werden, in folgender Weise ausgedrückt:

/ \

S»

Als alternativer Ausdruck kann einer verwendet werden, welcher eine zyklische Gruppe enthält, welche angibt, dass der Rest des verlängerten Galois-Feldes GF(2m) (mit Ausnahme des Elementes Null) eine multiplikative Gruppe mit derOrdnung2m -1 bildet. Wenn die Elemente von GF(2m) ausgedrückt werden durch Benützung einer zyklischen Gruppe, dann wird das folgende erhalten :

0,1 (a=2m), a, a2, a3,... a2m_2

Wenn in der vorliegenden Erfindung m Bits ein Wort und n Worte einen Block bilden, werden k Prüfworte erzeugt unter Verwendung einer Paritäts-Prüfmatrix H, z.B. der folgenden:

H . Vx

60

Dieser Fehlerkorrekturcode kann Fehler von bis zu zwei fehlerhaften Worten in einem Fehlerkorrekturblock korrigieren und kann auch drei Wortfehler oder vier Wortfehler kor-65 rigieren, wenn die Fehlerposition bekannt ist.

In jedem Block sind vier Prüfworte (p = W3, q = W2, r = Wi, s = Wo) enthalten. Diese Prüfworte können von den folgenden Gleichungen erhalten werden.

653 503

p + q + r + s = ZWi = a a3p + a2q + ar + s = la'Wi = b a6p + a4q + a2r + s = Ea2'Wi = c a9p + a6q + a3r + s = £a3'Wi = d n-I

wobei S = 2 ist.

i = 4

Das Ergebnis des weggelassenen Rechenvorganges ist das folgende;

q212

a153

a152

q

a156

a2

a135

r

«

a158

q138

a2

s

„218

a a158

a156

,209 ,152 <153

212

\

a b c

ajSo + Si = (a' + aJ)ei aiSi + S2 = a'(a' + aJ)ei

5 ajS2 + S3 = a2'(a' + aJ)ei

Entsprechend werden, wenn die folgenden Gleichungen erfüllt werden, zwei Wortfehler diskriminiert.

10 a'(a)So + Si) = aJ'Si + S2

a'(aJSi + S2) = aJS2 + S3

Wenn die obigen Gleichungen erfüllt werden, wird dies 15 als zwei Wortfehler betrachtet und daher können die Fehlermuster nun folgenderweise ausgedrückt werden :

S0 +

20

1 + a

1-3

und ej =

S0 + a-1S1

1 + a

J-3-

Der auf der Sendeseite angeordnete Coder muss die Prüfworte p, q, r und s in der obigen Art erzeugen.

Als nächstes wird der grundlegende Algorhythmus der Fehlerkorrektur beschrieben werden, wenn die Daten mit in obiger Weise erzeugten Prüfwörtern übertragen und dann empfangen werden.

[1] wenn kein Fehler vorhanden ist, sind alle Syndrome Null; So = Si = S2 = S3 = 0

[2] wenn ein Wortfehler vorhanden ist (wobei das Fehlermuster durch ei dargestellt wird), dann ist So = ei, Si = a'ei, S2 = a2'ei, S3 = a3iei.

Es werden also die folgenden Gleichungen aufgestellt:

oc'So = Si a'Si = S2

a'S2 = S3

Ob ein Wortfehler vorhanden ist oder nicht, kann festgestellt werden, indem geprüft wird, ob die obige Beziehung erfüllt ist oder nicht, wenn i sukzessive verändert wird.

25

30

Es wird also das Muster a' verglichen mit dem früher in einem Festwertspeicher ROM gespeicherten, um die Fehlerposition i zu erfahren. Zu diesem Zeitpunkt wird das Syndrom Si selbst das Fehlermuster ei.

[3] Im Falle von zwei Wortfehlern (ei und ej) folgen die Syndrome den Beziehungen:

50 = ei + ej

51 = a'ei + aiej

52 = a2l'ei + a2J'ej

53 = a3iei + a3J'dj

Die obigen Gleichungen können in der folgenden Weise modifiziert werden:

[4] Wenn drei Wortfehler (ei, ej und ek) auftreten, können die Syndrome auf folgende Weise ausgedrückt werden:

50 = ei + ej + ek

51 = a'ei + ajej + akek

52 = a2'ei + a2Jej + a2kek

53 = a3'ek + a3J'ej + a3kek

Die obigen Gleichungen können folgenderweise modifiziert werden:

35

akSo + Si = (a' + ak)ei + (ai + ak)ej akSi + S2 = a'(a' + ak)ei + aJ(ai + ak)ej

40 akS2 + S3 = a2'(a' + ak)ei + a2-i(aJ + ak)ej

Entsprechend werden die folgenden Gleichungen abgeleitet:

45 a-i(akSo + Si) + (akSi + S2) = (a' + aJ)(a" + ak)ei aJ(akSi + S2) + (akS2 +- S3) = a'(a' + aJ)(a' + ak)ei

Entsprechend können, wenn die folgende Gleichung auf-

5o gestellt wird, welche eine notwendige Bedingung für drei Wortfehler ist, alle drei Wortfehler diskriminiert werden. Dabei wird angenommen, dass die Bedingungen Sp^0, Si ^0 und 827^0 erfüllt sind:

55 a'{aJ(akSo + Si) + (akSi + S2)} = ai(akSi + S2) + (akS2 + S3)

Die entsprechenden Fehlermuster werden hier wie folgt ausgedrückt:

SQ + (o"-3 + + o"j"k£

60

©3

ek =

(1 +

a1_j)(l + a1"10

S0 + (a"

k + o'^Sj + o~]f-'iS2

(1 +

aJ_i)(l + a3'k)

s0 + (0"

1 + + a_1*js2

(1 +

ak*1)(l + ak"jj

653 503

In Wirklichkeit ist die Konstruktion einer Schaltung zur Korrektur von drei Wortfehlern eher kompliziert und die für den Korrekturvorgang benötigte Zeit ist lang. In der Praxis wird daher ein Fehlerkorrekturvorgang verwendet, indem der obige Vorgang mit einem Fehlerkorrekturvorgang kombiniert wird, in welchem die Fehlerpositionen i, j, k und 1 bekannt sind durch ein Fehlerkennzeichen-Bit und die obigen Gleichungen für die Prüfung angewendet werden.

[5] Wenn vier Wortfehler vorhanden sind (ei, ej, ek und el), werden die Syndrome wie folgt ausgedrückt:

ei =

ej =

ek =

e-t =

Nun werden die Konstanten der entsprechenden Ausdrücke des obigen Polynoms in folgender Weise angenommen:

SoS2+S!2=A

S1S2 + S0S3 = B

SiS5 + S22 = C

Unter Verwendung der obigen Konstanten A, B und C kann die Fehlerposition von zwei Wortfehlern erhalten werden.

[1] Falls kein Fehler vorhanden ist: A = B = C = 0, So = 0 und S3 = 0

[2] Falls ein einziger Wortfehler vorhanden ist: Wenn A=B = C = 0, So^O und S3^0 erfüllt sind, dann wird der Fehler als ein einziger Wortfehler betrachtet. Aus der Gleichung a' = S1/S0, kann die Fehlerposition i leicht bestimmt werden. Der Fehler wird also korrigiert unter Verwendung der Beziehung ei = So.

[3] Im Falle von zwei Wortfehlern: Wenn ein Fehler in mehr als zwei Wörtern auftritt, werden die Ungleichungen A^O, B^O und C^0 aufgestellt und die Betrachtung des Fehlers wird ganz einfach.

Diesmal wird die folgende Gleichung aufgestellt:

Aa2i + Ba' + C = 0

wobei i = 0 bis (n-1).

Wenn nun angenommen wird, dass B/A= D und C/A = E ist, werden die folgenden Gleichungen erhalten.

D = a' + aJ

E=a'-aj

Es wird also die folgende Gleichung erhalten:

a2' + Da' + E = 0

6

50 = ei + ej + ek + el

51 = a'ei + aJ'ej + akek + a'ei

5 S2 = a2iei + a2jej + a2kek + a2lel S3 = a3'ei + acJej + a3kek + a3lel

Die obigen Gleichungen werden in folgender Weise modi-10 fiziert:

Wenn die Differenz zwischen den Fehlerpositionen als t 30 bezeichnet wird, d.h. j = i +1, dann werden die folgenden Gleichungen erhalten.

Wenn also die Fehlerposition (i, j, k, 1) durch Fehlerkennzeichen angegeben sind, kann der Fehler durch die obige Rechnung korrigiert werden.

35 Der Grundalgorhythmus der obigen Fehlerkorrektur besteht darin, dass in einem ersten Schritt durch die Syndrome So bis S3 geprüft wird, ob ein Fehler vorhanden ist oder nicht, dass beim zweiten Schritt geprüft wird, ob nur ein einziger Wortfehler vorhanden ist oder nicht, und dass beim drit-40 ten Schritt geprüft wird, ob zwei Wortfehler vorhanden sind oder nicht. Wenn bis zu zwei Wortfehler korrigiert werden, wird die Zeit zum Ablauf all dieser Schritte lang, was ein Problem ergibt, insbesondere wenn die Fehlerposition der zwei Wortfehler erhalten wird.

45 Es soll nun ein modifizierter Algorhythmus beschrieben werden für die Korrektur von zwei Wortfehlern, der das obige Problem nicht bewirkt.

Die Gleichungen der Syndrome So, Si, S2 und S3 im Falle von zwei Wortfehlern (ei, ej) lauten wie folgt:

50

50 = ei + ej

51 = a'ei + aJej 55 S2 = a2iei + a2Jej

S3 = a3'ei + aejej

Die obigen Gleichungen werden in folgender Weise modi-60 fiziert:

(a'So + Si)(a'S2 + S3) = (a'Si + S2)2

Die Gleichung wird weiter modifiziert und es wird das 65 folgende Fehlerlokalisierungs-Polynom erhalten:

(S0S2 + Si2)a2j + (S1S2 + SoS3)a' + (S1S3 + S22) = 0

S0+(a~j+cTk+ tx"£)S1 + (a"j"k+cfk"£+ o~£_J)S2 + a~j~k_£S3

(l+ai~j)(l+ oi_k)Cl+a1"*)

S0+(a"k+a"£+cx"1)S1 + (a~k~£+ a"£_1 + o"J"k)S2+a"k"£"1S3

(l+cr5'1) (l+aj"k) (l+aj"£)

S 0+(a- £+a_i+a" j ) S-j+Ca" £" *+0' i_ j+û"^ " £) S2+a~ l~1_^ S3

(1+ ak_i)(l+ ak'j)(l+ak'£)

SQ+ (a'^a'-S -t-a'k)S1 + (a~i"j+a~j~k + a'k-i)S2+ a"1"j"kS3

(l+o1*1)(l+a*"3)(l+at_k)

7

653 503

D = a'(l -fa')

E = a2i+t

Entsprechend wird die folgende Gleichung erhalten:

D2 = (1 + ext)2 = rt-t at

E t a

Wenn der Wert von a ~ ' + a< für jeden Wert von t= 1 bis (n-1) vorher in einen Festwertspeicher eingeschrieben wird, und wenn festgestellt wird, dass der Wert zusammenfällt mit dem Wert von D2/E, der aus dem Ausgangssignal des Festwertspeichers und einem empfangenen Wort errechnet wird, dann kann t erhalten werden. Wenn das obige Zusammenfallen nicht detektiert wird, dann bedeutet dies, dass in mehr als drei Wörtern Fehler vorhanden sind.

Wenn also die folgenden Ausdrücke angenommen werden: ^

x = 1

-t _ _i)2 E

+ a Y = 1 + a"

+ S

Können die folgenden Ausdrücke erhalten werden:

■l"§

«3

D Y

Aus den obigen Ausdrücken können die Fehlerpositionen i und j erhalten werden. Dann können die Fehlermuster ei und ej in folgender Weise ausgedrückt werden:

(o^O + Sl>

(°iso + S1

s0

+ 51

Y

+ D

so

+ S1

= 3T

+ D

eu =-

Die Fehler können also korrigiert werden.

Dieser modifizierte Korrekturalgorhythmus verkürzt die für die Fehlerlokalisierung notwendige Zeit beträchtlich, bei die Korrektur von zwei Wortfehlern im Vergleich zu jener, die beim grundsätzlichen Algorhythmus notwendig ist.

Weiter kann, wenn die Anzahl k der Prüfworte erhöht wird, die Fehlerkorrekturfähigkeit entsprechend erhöht werden. Wenn z.B. k mit 6 gewählt wird, dann können drei Wortfehler korrigiert werden und sechs Wortfehler können korrigiert werden, wenn die Fehlerposition bekannt ist.

Nun soll ein Ausführungsbeispiel der Erfindung anhand der Zeichnung näher beschrieben werden. Dabei wird die Erfindung beispielsweise verwendet für die Aufzeichnung und Wiedergabe eines PCM-Tonsignales.

Fig. 1 zeigt als ganzes, d.h. die Fig. 1A und 1B zusammen, einen fehlerkorrigierenden Coder in einer Aufzeichnungsanlage, an welche ein PCM-Tonfrequenzsignal als Eingangssignal angelegt wird. Um dieses PCM-Tonfrequenzsignal zu erhalten, werden die linken und rechten Stereosignale je mit einer Abtastfrequenz fs (z.B. 44,1 kHz) abgetastet und jeder Abtastwert wird in ein digitales Wort umgewandelt, das z.B. als Komplement von zwei codiert ist und eine Länge von 16 Bits aufweist. Entsprechend werden für den linken Kanal des Tonsignales die PCM-Datenworte Lo, Li, Li... erhalten und für den rechten Kanal die PCM-Datenworte Ro, Ri, R2... Die PCM-Datenworte des linken und rechten Kanals werden je in sechs Kanäle aufgeteilt und daher ergibt sich ein Total von zwölf Kanälen von PCM-Datenfolgen als Eingangssignal für den fehlerkorrigierenden Coder. Zu einem gegebenen Zeitpunkt sind zwölf Worte L6n, R6n, L6n+:, R^,, L6n+2, ^„+2, Lön+35 ï^6n+3> ^611+4* ^61;+4^ Lgn+5 und Rgn+5 Eingangssignal für den Coder. Im gezeichneten Beispiel wird jedes Wort auf-5 geteilt in acht obere Bits und acht untere Bits, so dass die zwölf Kanäle als vierundzwanzig Kanäle verarbeitet werden. Zur Vereinfachung ist jedes Wort der PCM-Daten als Wi ausgedrückt, dessen obere Bits bezeichnet werden mit Wi, A und dessen untere acht Bits bezeichnet werden mit Wi, B. So wird io zum Beispiel das Wort L6n aufgeteilt in zwei Worte W|2n, A und Wi2n, B.

Die PCM-Datenfolgen der vierundzwanzig Kanäle werden zuerst an eine Verschachtelungsschaltung 1 für gerade und ungerade Datenfolgen angelegt. Wenn n eine ganze Zahl 15O, 1, 2 ... ist, dann sind die Worte L6n (d.h. Wi2n,A und WI2n, B), Rôn (d.h. Wl2n + 1,A und Wl2n+1,B), L6n+2 (d.h. W,n+4,A und W|2n + 4jB)) Rtìn + 2 (d.h. W[2n + 5,A Und Wi2n + 5,B), Ljn + 4 (d.h. W|2n+8,A und W|2n+8,B), und R<;n+4 (d.h. W12n+9,A und W|2n+9,B) je Wörter gerader Ordnung und die verbleibenden 20 Wörter sind ungerade Wörter. Die PCM-Datenfolgen bestehen aus geraden Wörtern, welche je durch eine Einwort-Ver-zögerungsschaltung oder -Leitung 2A, 2B, 3A, 3B, 4A, 4B, 5A, 5B, 6A, 6B, 7A und 7B der Verschachtelungsschaltung 1 verzögert sind. Es ist natürlich möglich, die Wörter um mehr als 25 ein Wort zu verzögern, z.B. um acht Wörter. Weiter werden in der Verschachtelungsschaltung 1 die zwölf aus den geraden Wörtern bestehenden Datensequenzen umgewandelt oder verschoben, so dass sie die Übertragungskanäle eins bis zwölf belegen, und die zwölf aus den ungeraden Wörtern bestehen-30 den Datenfolgen werden umgewandelt, dass sie die Übertragungskanäle dreizehn bis vierundzwanzig belegen.

Die Verschachtelungsschaltung 1 für gerade und ungerade Wörter dient dazu, zu verhindern, dass mehr als zwei aufeinanderfolgende Wörter des linken bzw. rechten Stereosignales 35 Fehler entwickeln, in welchem Fall die Fehler praktisch nicht mehr korrigiert werden könnten.

Um den Nutzen dieses Merkmales zu erläutern, sollen drei aufeinanderfolgende Wörter Li — 1, Li, und Li + 1 als Beispiel betrachtet werden. Wenn das Wort Li fehlerhaft ist und 40 nicht korrigierbar ist, ist es sehr erwünscht, dass die beiden benachbarten Wörter Li - 1 und Li + 1 richtig sind. Der Grund dafür besteht darin, dass, um ein unkorrigierbares fehlerhaftes Wort Li zu kompensieren, Li interpoliert werden muss zwischen dem vorausgehenden richtigen Wort Li — 1 45 und dem nachfolgenden richtigen Wort Li+ 1, üblicherweise durch Bilden des Mittelwertes aus Li - 1 und Li + 1. Die Verzögerungsleitungen 2A, 2B,... 7A und 7B der Verschachtelungsschaltung 1 sind vorgesehen, damit benachbarte Wörter in unterschiedlichen Fehlerkorrekturblöcken auftreten. Ein so weiterer Grund für die Zusammenfassung von Gruppen von Übertragungskanälen für die gradzahligen Wörter und die ungradzahligen Wörter besteht darin, dass, wenn die Datenfolgen verschachtelt werden, der Abstand zwischen den Aufzeichnungsstellen von benachbarten gradzahligen und 55 ungradzahligen Wörtern so gross als möglich sein sollte.

Am Ausgang der Verschachtelungseinrichtung 1 erscheinen die Wörter der vierundzwanzig Kanäle in einer ersten Anordnung. Die entsprechenden PCM-Datenwörter von der Verschachtelungsschaltung 1 werden Wort um Wort an einen 60 Coder 8 angelegt, welcher dann erste Prüfworte Qi2n, Qi2n+i> Qi2n+2 und Qi2n+3 erzeugt, wie sie in den oben angegebenen Ausdrücken p, q, r, s gezeigt sind.

Ein Fehlerkorrekturblock, der die ersten Prüfworte aufweist, erscheint dann wie folgt:

65

653 503

8

(Wi2n-12,A; W|2n-|2)B; Wi2„+1 - n.Ai W|2n+|_12,B;

Wj2n + 4-l2sA; WJ2n + 4-I2,B; Wi2n + 5_|2,A; W]2n + 5-12>B;

W]2n + 8-12>A.; Wi2n + 8-l2>B; Wi2n + 9-12:A; Wi2n + 9_i2,B;

Wi2„+2,A; W|2n+2,B; W|2„+3jA; wI2n+3,B;

W12n+6,A; W|2n+6,B; Wi2n+7,A; W12n+7,B;

Wi2n+10)A; W|2n+|0>B; W,2n+U,A; W]2n+|1,B;

Ql2n! Ql2n + |! Ql2n + 2! Ql2n + 3)

Der erste Coder 8 führt seine Funktion durch, indem er die ersten Prüfworte QI2n bis Qi2n+13 entsprechend der Anzahl Wörter eines Blocks (n = 28) errechnet, wobei m die Bit-Länge jedes Wortes (m = 8) und k die Anzahl der Prüfworte (k = 4) ist.

Die vierundzwanzig PCM-Datenwortfolgen und die vier Prüfwortfolgen werden dann an eine Verschachtelungsschaltung 9 angelegt. In dieser Verschachtelungsschaltung 9 werden die relativen Positionen der Kanäle so geändert, dass die Prüfwortfolgen zwischen den PCM-Datenfolgen, bestehend aus den gradzahligen Wörtern, und den PCM-Datenfolgen, bestehend aus den ungradzahligen Wörtern, liegen, und danach wird ein Verzögerungsvorgang durchgeführt für diese Verschachtelungsfolgen. Dieser Verzögerungsvorgang wird auf siebenundzwanzig Übertragungskanälen durchgeführt, beginnend mit dem zweiten Übertragungskanal, und zwar durch Verzögerungsleitungen mit Verzögerungsbeträgen von 1D, 2D, 3D, 4D,... 26D und 27D, wobei D eine Einheitsverzögerung ist.

Am Ausgang der Verschachtelungsschaltung 9 erscheinen achtundzwanzig Folgen von Datenwörtern in einer zweiten Anordnung. Die Datenwörter werden Wort für Wort von den entsprechenden Datenfolgen übernommen und einem Coder 10 zugeführt, welcher zweite Prüfworte P|2n, P|2n+1, Pi2n+2 und Pi2n+3 in der gleichen Art erzeugt wie die Prüfworte Q|2n bis Qi2n + 3-

Genau wie der Coder 8 die ersten Prüfworte entsprechend den Parametern n = 28, m = 8 und k = 4 erzeugt, erzeugt der ähnliche Coder 10 die zweiten Prüfworte, entsprechend den Parametern n = 32, m = 8 und k = 4.

Ein Fehlerkorrekturblock umfasst die zweiten Prüfwörter und besteht aus zweiunddreissig Wörtern und wird wie folgt gebildet:

(W|2„-12>A; Wi2n_12(D+l>B; WI2„+1-12(2D+1)jA;

Wi2„+1-I2(3D+1)>B;

Wi2n+4- i2(4d+ !)>A; W|2n + 4- 12(5D+ 1)3 !

W|2n+5-!2(6D+l)>A; W12n + 5- 12(7D+ 1)3 '

Ql2n— 12(12D)» Ql2n+l-12(13D)î Ql2n + 2- 12(14D)i

Ql2n+3-12(I5D)! ••• W)2n+ 10-i2(24d)>A;

W|2n+ 10- 12(25D)3 î W12n + 11 - 12(25D)>A;

Wi2n+1!-I2(27D)3; Pl2rò P|2n+l! Pl2n + 2Ì P|2n + 3)-

Darauf folgt eine Verschachtelungsschaltung 11, welche Verzögerungsleitungen mit einer Verzögerung von einem Wort für die gradzahligen Übertragungskanäle der zweiunddreissig Datenfolgen inklusive die ersten und zweiten Prüfworte aufweist, und ferner Inverter 12,13, 14 und 15 zur Inversion der zweiten Prüfwortfolgen. Die Verschachtelungsschaltung 11 dient dazu, zu verhindern, dass Fehler, die an der Grenze zwischen den Blöcken auftreten, so viele Worte beeinflussen, dass es unmöglich ist, sie zu korrigieren. Die Inverter 12,13,14 und 15 dienen dazu, eine fehlerhafte Betriebsweise zu verhindern, wenn alle Daten in einem Block «0» sind, wegen eines Ausfalls während der Übertragung. Dies bedeutet, dass, wenn ein Ausfall auftritt, die invertierten Prüfwortfolgen im Wiedergabesystem richtig diskriminiert werden. Für denselben Zweck können auch für die ersten Prüfwortfolgen Inverter vorgesehen sein.

Die so erhaltenen vierundzwanzig PCM-Datenfolgen und acht Prüfwortfolgen werden dann als zweiunddreissig Wortblöcke in Serieform gebracht, und es wird ein Synchronisiersignal von sechzehn Bits an den Kopf des resultierenden Seriesignales gestellt, um einen Übertragungsblock zu bilden, wie er in Fig. 2 gezeigt ist. Der so hergestellte Block wird auf einem Übertragungsmedium oder Träger übertragen. In Fig. 2 wird ein vom i-ten Übertragungskanal geliefertes Signal als U bezeichnet.

Praktische Beispiele des Übertragungsmediums oder des Trägers für das übertragene Signal können ein Magnetband zur Verwendung in einem magnetischen Aufzeichnungs- und Wiedergabegerät umschliessen, ferner eine Scheibe in einem Gerät mit einer rotierenden Scheibe oder ein ähnliches Medium.

Die reproduzierten Daten von jedem der zweiunddreissig Wörter jedes Blocks des übertragenen Signales werden an den Eingang eines fehlerkorrigierenden Decoders, der in Fig. 3 gezeigt ist, angelegt. Die übertragenen Daten, wie sie vom fehlerkorrigierenden Decoder empfangen werden, können einen oder mehrere Fehler enthalten, da die Eingangsdaten wiedergegebene Daten sind. Wenn kein Fehler vorhanden ist, stimmen die zweiunddreissig an den Eingang des Decoders angelegten Wörter mit den zweiunddreissig am Ausgang des fehlerkorrigierenden Codes erscheinenden Wörter überein. Im fehlerkorrigierenden Decoder wird ein Entschachtelungs-vorgang durchgeführt, der komplementär ist zum entsprechenden Verschachtelungsvorgang auf der Coderseite, um die Daten in ihre ursprüngliche Reihenfolge zurückzubringen. Wenn kein Fehler vorhanden ist, wird der Fehlerkorrekturvorgang durchgeführt, nachdem die Daten in die ursprüngliche Reihenfolge zurückgeführt sind.

Am Anfang ist, wie in Fig. 3 gezeigt, eine Entschachte-lungsschaltung 16 vorgesehen, welche Verzögerungsleitungen mit je einer Verzögerung von einem Wort für die ungradzahligen Übertragungskanäle und Inverter, 17, 18, 19 und 20 für die Inversion der empfangenen zweiten Prüfwortfolgen aufweist. Die Ausgangssignale der Entschachtelungsschaltung 16 und der Inverter 17 bis 20 gelangen an einen ersten Decoder 21. In diesem ersten Decoder 21 werden die Syndrome Sio, Su, S12 und S13 entsprechend einer Matrix erzeugt, wie zum Beispiel der Reed-Solomon-Paritätsdetektionsmatrix HC1 (Fig. 4), und zwar durch die zweiunddreissig Eingangswörter V, wie in Fig. 4 gezeigt, und die obenerwähnte Fehlerkorrektur wird basierend auf den Syndromen Sio bis S13 durchgeführt. In Fig. 4 ist • ein Element von GF(28) und eine Wurzel von F(x) = x8 + x4 + x3 + x2 + 1. Der Decoder 21 leitet die korrigierten vierundzwanzig PCM-Datenfolgen und die vier ersten Prüfwortserien ab. Bei jedem individuellen Wort der Datenfolgen wird ein Fehlerkennzeichen- oder Fehlerdetektions-code (mindestens ein Bit) hinzugefügt, um anzugeben, ob im zugehörigen Wort ein Fehler ist (Fehlerkennzeichen ist « 1 ») oder nicht (Fehlerkennzeichen ist «0»). In den Fig. 4 und 5 und auch in der der nachfolgenden Beschreibung ist das empfangene eine Wort Wi lediglich als Wi bezeichnet.

Die Ausgangsdatenfolgen von Decoder 21 werden an eine

5

10

15

20

25

30

35

40

45

50

55

60

65

9

653 503

Entschachtelungsschaltung 22 angelegt, welche zur Kompensation des Verzögerungsvorganges dient, der in der Verschachtelungsschaltung 9 im fehlerkorrigierenden Coder durchgeführt wird, und besitzt entsprechende Verzögerungsleitungen mit entsprechenden unterschiedlichen Verzögerungsbeträgen 27D, 26D, 25D ... 2D, und 1D für die Übertragungskanäle eins bis siebenundzwanzig. Der Ausgang der Entschachtelungsschaltung 21 wird an einen zweiten Decoder 23 angelegt, in welchem Syndrome S20, S21, S22 und S23, entsprechend einer Matrix, wie der Reed-Solomon-Paritätsde-tektionsmatric Hc2 (Fig. 5) erzeugt werden. Die achtundzwanzig Wörter VT, wie sie in Fig. 5 gezeigt sind, werden daran angelegt und die obenerwähnte Fehlerkorrektur wird basierend auf den Syndromen S20 bis S23 ausgeführt.

Der Decoder 23 löscht das zu jedem Wort, dessen Fehler korrigiert wurde, gehörende Fehlerkennzeichen, löscht jedoch das Fehlerkennzeichen nicht, das zu irgendeinem Wort gehört, dessen Fehler nicht korrigiert werden kann.

Die am Ausgang des Decoders 23 erscheinenden Datenfolgen werden an eine Entschachtelungsschaltung 24 für gradzahlige und ungradzahlige Folgen angelegt, in welcher die aus gradzahligen Wörtern bestehenden PCM-Datenfolgen und die aus ungradzahligen Wörtern bestehenden PCM-Datenfolgen neu angeordnet werden, so dass sie in andern Übertragungskanälen positioniert sind, und Verzögerungsleitungen mit einer Verzögerung um ein Wort werden für die PCM-Datenfolgen vorgesehen, die aus den ungradzahligen Wörtern bestehen. Dies kompensiert den entsprechenden Vorgang, der im Coder vor der Übertragung durchgeführt wurde. Am Ausgang der Entschachtelungsschaltung 24 erscheinen PCM-Datenfolgen, deren ursprüngliche Anordnung und vorbestimmte Reihenfolge vollständig wiederhergestellt ist, wie sie waren, bevor der Fehler korrigierende Coder seine Wirkung ausübte.

Obwohl in Fig. 3 nicht gezeigt, ist in der Stufe, die auf die Entschachtelungsschaltung 24 folgt, vorzugsweise eine Kompensationsschaltung vorgesehen, um nichtkorrigierbare Fehler zu kompensieren. Zum Beispiel kann eine Mittelwertinterpolation verwendet werden, wenn immer Fehler durch die Decoder 21 und 23 nicht korrigiert werden können, so dass allfällig verbleibende Fehler maskiert und unauffällig gemacht werden.

In dem in Fig. 3 gezeigten Beispiel der Erfindung wird ein Fehler von einem Wort durch den ersten Decoder 21 korrigiert. Wenn festgestellt wird, dass mehr als zwei Wortfehler vorhanden sind in einem Fehlerkorrekturblock, dann wird das Fehlerkennzeichen von mindestens einem Bit zu allen der achtundzwanzig Wörter des Fehlerkorrekturblockes, d.h. zu allen Wörtern des Blocks mit zweiunddreissig Wörtern, ausser den Prüfwörtern, zugefügt, um anzugeben, dass Fehler vorhanden sind. Dieses Fehlerkennzeichen ist «1», wenn ein Fehler vorhanden ist, jedoch «0», wenn kein Fehler vorhanden ist. Im Falle, in welchem ein Wort aus acht Bits besteht, wird das Fehlerkennzeichen als ein Bit höher als das bedeutsamste Bit zugefügt, so dass ein 9-Bit-Wort entsteht. Dann werden die Wörter durch die Entschachtelungsschaltung 22 und danach durch den zweiten Decoder 23 weiterverarbeitet.

In diesem Decoder 23 wird der Fehler korrigiert unter Verwendung der Anzahl von Fehlerwörtern im ersten Fehlerkorrekturblock, die durch die Fehlerkennzeichen oder Fehlerpositionen angegeben werden.

Fig. 6 zeigt ein Flussdiagramm eines Beispiels eines Feh-Ierkorrekturvorganges, wie er vom zweiten Decoder 23 ausgeführt wird. In Fig. 6 und der nachfoglenden Beschreibung wird die Anzahl von fehlerhaften Wörtern, die durch die Fehlerkennzeichen angegeben werden, ausgedrückt als Np und die Fehlerposition, angegeben durch die Fehlerkennzeichen,

wird ausgedrückt durch Ei. Weiter stellt in Fig. 6 Y die Antwort «ja» und N die Antwort «nein» dar.

(1) Das Vorhandensein oder Nichtvorhandensein eines Fehlers wird bestimmt durch die Syndrome S20 bis S23. Wenn S20 = S21 = S22 = 0 ist, dann ist bestimmt, dass kein Fehler vorhanden ist. Nun wird geprüft, ob die Bedingung NpS=zi erfüllt ist oder nicht. Wenn Npi=zi ist, dann liegt fest, dass kein Fehler vorhanden ist und die Fehlerkennzeichen im Fehlerkorrekturblock werden gelöscht («0»). Wenn dagegen

Np > zi ist, dann wird die Fehlerdetektion durch die Syndrome als fehlerhaft bezeichnet und die Fehlerkennzeichen werden unverändert belassen oder es wird sogar für alle Wörter in diesem Block das Fehlerkennzeichen «1» gemacht. Im letztern Fall wird der Wert von zi relativ gross gewählt, z.B. mit 14.

(2) Im Falle, dass ein Fehler vorhanden ist, wird über die Berechnung der Syndrome festgestellt, ob der Fehler ein

1-Wort-Fehler ist. Im Falle eines 1-Wort-Fehlers wird die Fehlerposition i erhalten. Es wird festgestellt, ob die durch die Berechnung über die Syndrome erhaltene Fehlerposition i mit der durch das Fehlerkennzeichen angegebenen übereinstimmt oder nicht. Wenn durch die Fehlerkennzeichen mehrere Fehlerpositionen angegeben werden, wird festgestellt, welche Fehlerposition i übereinstimmt mit den durch die Fehlerkennzeichen angegebenen mehrfachen Fehlerpositionen. Wenn i = Ei ist, dann wird geprüft, ob NpS=Z2 ist oder nicht, wobei Z2 zum Beispiel 10 ist. Wenn NP^Z2 ist, dann wird der Fehler als ein Wortfehler betrachtet und es wird ein einziger Wortfehler korrigiert. Wenn Np > Z2 ist, dann ist es möglich, dass der Fehler unrichtigerweise als ein 1-Wort-Fehler betrachtet wurde. Daher bleibt das Fehlerkennzeichen unverändert oder es werden sogar alle Wörter als fehlerhaft angenommen und die entsprechenden Fehlerkennzeichen werden auf « 1 » gesetzt.

Im Fall von i ^ Ei wird abgeklärt, ob Np Si Z3 oder nicht ist, wobei Z3 einen ziemlich kleinen Wert aufweist, z.B. 3. Wenn die Bedingung NP^Z3 erfüllt ist, dann ist ein Wortfehler in der Fehlerposition i korrigiert durch die Berrechnung des Syndroms.

Wenn Np>Z3 ist, wird weiter geprüft, ob Np5=Z4 ist oder nicht. Wenn Z3 < NP^Z4 ist, bedeutet dies, dass, obwohl die Feststellung eines Wortfehlers durch das Syndrom fehlerhaft ist, Np zu klein ist. Daher werden in diesem Falle die Fehlerkennzeichen aller Wörter des Blocks auf «1» gesetzt. Wenn jedoch Np > Z4 ist, bleibt jedes Fehlerkennzeichen unverändert. In diesem Falle ist Z4 zum Beispiel 5.

(3) Wenn nicht ein einzelner Wortfehler vorhanden ist, wird festgestellt, ob Np^zs ist. Wenn Np^zs ist, dann ist das Fehlerkennzeichen mangelhaft oder unzuverlässig, so dass die Fehlerkennzeichen aller Wörter auf «1» gesetzt werden. Wenn jedoch Np>zs ist, bleiben alle Fehlerkennzeichen wie sie waren.

(4) Wie es in Fig. 6 durch die gestrichelte Linie gezeigt ist, ist es möglich, Fehler in bis zu M Wörtern zu korrigieren unter Verwendung der durch das Fehlerkennzeichen angegebenen Fehlerposition. Es können bis zu vier Wortfehler korrigiert werden, doch das Verfahren der Fehlerkennzeichenlöschung kann eine fehlerhafte Korrektur nicht vermeiden. Daher wird unter Berücksichtigung der Zeit und der Komplexität für den Korrekturvorgang M ungefähr 2 gewählt. Dann werden zwei Wortfehler, die zu den durch die Fehlerkennzeichen angegebenen Fehlerpositionen i und j gehören, korrigiert. Wenn Np ¥= M ist, verbleiben die Fehlerkennzeichen unverändert oder die Fehlerkennzeichen aller Wörter werden auf jene verändert, die Fehler angeben.

In der obigen Beschreibung sind die praktischen Werte für die Vergleichswerte zi bis zs bezogen auf die Anzahl Np der Fehlerkennzeichen, die Fehler in einem Block angeben,

5

10

15

20

25

30

35

40

45

50

55

60

65

653 503

10

lediglich Beispiele. Im obigen Beispiel hat der Fehler korrigierende Code einen möglichen Nachteil insofern, als, wenn ein Block mehr als fünf Wortfehler enthält, dieser unrichtigerweise als fehlerfrei betrachtet werden kann, und auch wenn ein Block mehr als vier Wortfehler enthält, dieser unrichtigerweise als einer mit nur einem Wortfehler betrachtet werden kann. Daher müssen die Vergleichswerte geeignet gewählt werden in Berücksichtigung der Wahrscheinlichkeit, dass das obige Fehlerübersehen oder fehlerhafte Korrektur erfolgen kann.

Im obigen Beispiel der Erfindung kann, obwohl im ersten Decoder ein Wortfehler korrigiert werden kann, der Coder so modifiziert werden, dass zwei Wortfehler korrigiert werden und Fehlerkennzeichen hinzugefügt werden, welche das Vorhandensein von Fehlern in allen Wörtern des Fehlerkorrekturblocks angeben, in welchen das Fehler korrigierte Wort enthalten ist. In ähnlicher Weise können bis zu zwei Wortfehler im zweiten Decoder korrigiert werden.

Nun soll ein mehr praktisches Ausführungsbeispiel des obigen Fehlerkorrekturverfahrens unter Bezug auf die Fig. 7A und 7B beschrieben werden. Ein Block von Daten wird im ersten Decoder 21 (Schritt Ci) verbeitet, wobei der Zustand eines Fehlers beurteilt wird unter Verwendung des obenerwähnten Fehlerlokalisierungs-Polynoms und des Fehlersyn-droms.

(1) Wenn der Block als fehlerfrei beurteilt wird, wird kein Fehlerkennzeichen zugefügt und die Daten werden nicht verändert, welche der zweiten Codierung C2 zugeführt werden.

(2) Im Falle eines Wortfehlers wird die Fehlerposition erhalten. Wenn die Fehlerposition i kleiner oder gleich 31 ist, wird das Wort korrigiert, wenn jedoch die Fehlerposition i mehr als 31 ist, dann werden vier Wortfehler irrtümlicherweise als ein einziger Wortfehler betrachtet. Folglich werden Fehlerkennzeichen allen Wörtern zugefügt und die Daten werden in der nächsten Stufe D2 decodiert.

(3) Im Falle von zwei Wortfehlern werden die Fehlerpositionen errechnet. Wenn die Fehlerposition i je mit weniger oder gleich 31 bestimmt werden, werden die beiden Wörter korrigiert und Fehlerkennzeichen werden allen Wörtern zugefügt. Wenn die Fehlerposition i mehr als 31 ist, dann werden mehr als drei Wortfehler irrtümlich als zwei Wortfehler beurteilt. Daher erhalten alle Wörter fehleranzeigende Kennzeichen und werden der nächsten Decodierstufe D2 zugeführt.

(4) Im Falle von mehr als drei Wortfehlern wird kein Korrekturvorgang ausgeführt, sondern es werden allen Wörtern Fehlerkennzeichen beigegeben und dann die Daten der nächsten Decodierstufe C2 zugeführt.

Im zweiten Decoder 23, der ähnlich aufgebaut ist wie der Decoder 21, wird die Art jedes Fehlers zuerst durch ein Fehlerpositionspolynom und durch die Fehlersyndrome beurteilt. Dies wird im Zusammenhang mit Fig. 7B erläutert.

(1) Im Falle, dass kein Fehler detektiert wird, wird, wenn ein durch den ersten Decoder zugeführtes Fehlerkennzeichen vorhanden ist (d.h. wenn es «1» ist), dieses gelöscht (d.h. «0» gemacht).

(2) Im Falle eines Wortfehlers wird die Fehlerposition errechnet. Wenn die Fehlerposition kleiner oder gleich 27 ist, wird das fehlerhafte Wort korrigiert und das durch den ersten Decoder 21 zugefügte Fehlerkennzeichen wird gelöscht.

Wenn jedoch die Fehlerposition grösser als 27 ist, wird kein Korrekturvorgang durchgeführt und das vorher zugefügte Fehlerkennzeichen bleibt wie es ist.

(3) Im Falle von zwei Wortfehlern werden die Fehlerpositionen i und j errechnet. Wenn die Fehlerposition i und j je mehr als 27 sind, werden mehr als drei Wortfehler irrtümlich als nur zwei Wortfehler beurteilt. In diesem Fall jedoch wird die Anzahl der durch den ersten Decoder 21 zugeführten Fehlerkennzeichen geprüft. Wenn diese Anzahl von Fehlerkennzeichen 2 übersteigt, werden die Fehlerkennzeichen unverändert belassen. Wenn die Anzahl der Fehlerkennzeichen kleiner als 2 ist, obwohl zwei Wortfehler detektiert wurden, werden allen Wörtern Fehlerkennzeichen zugefügt, da die Daten eines ganzen Blockes dann als unzuverlässig betrachtet werden. Selbst wenn die Fehlerposition i, j kleiner als 27 sind, werden, wenn die Anzahl der durch den ersten Decoder 21 zugefügten Fehlerkennzeichen kleiner als 3 ist, die beigegebenen Fehlerkennzeichen unverändert belassen. Ebenfalls wird, wenn die Anzahl der Fehlerkennzeichen grösser als 4 ist, die von dieser Stufe erhaltene Fehlerposition i oder j mit dem vom ersten Fehlerdecoder 21 beigegebenen Fehlerkennzeichen verglichen.

(a) Wenn die beiden Wörter nicht zusammenfallen, wird kein Fehlerkorrekturvorgang ausgeführt und die Anzahl der Fehlerkennzeichen wird geprüft. Wenn diese Anzahl 2 übersteigt, werden die zugefügten Fehlerkennzeichen unverändert belassen. Wenn jedoch die Anzahl von Fehlerkennzeichen kleiner 2 ist, werden allen Wörtern Fehlerkennzeichen beigegeben.

(b) Wenn nur ein Wort übereinstimmt, wird die Anzahl der Fehlerkennzeichen ebenfalls geprüft. Wenn diese Anzahl 3 übersteigt, z.B. 4 ist, werden die beigegebenen Fehlerkennzeichen unverändert belassen. Wenn jedoch diese Anzahl kleiner als 3 ist, werden allen Wörtern Fehlerkennzeichen beigegeben.

(c) Wenn die beiden Wörter übereinstimmen, werden die beiden Wörter korrigiert und danach die Fehlerkennzeichen gelöscht.

(4) Im Falle, dass ein Fehler mit mehr als drei Wörtern gefunden wird, wird die Anzahl der Fehlerkennzeichen geprüft. Wenn diese Anzahl 2 übersteigt, werden die zugefügten Fehlerkennzeichen unverändert belassen, während, wenn diesse Anzahl kleiner als 2 ist, allen Wörtern Fehlerkennzeichen beigegeben werden.

Wie obenerwähnt, werden später im Decodiervorgang die mit Fehlerkennzeichen versehenen Wörter als unkorrigierbare Wörter, z.B. durch Verschachtelung kompensiert.

Bei dem in Fig. 3 gezeigten Fehler korrigierenden Decoder wird die Fehlerkorrektur unter Verwendung der ersten Prüfworte Qi2n, Qi2n+1> Qi2n+2 und Q|2n+j und die Fehlerkorrektur unter Verwendung der zweiten Prüfwörter P|2n, Pi2n+1> Pi2n+2 und P|2n+3 je einmal ausgeführt. Wenn jedoch die obigen Fehlerkorrekturen je zweimal oder mehrmals (in Praxis ungefähr 2 Mal) ausgeführt werden, kann die Fehlerkorrekturmöglichkeit beträchtlich erhöht werden, da das korrigierte Resultat jedes Mal weniger Fehler enthält. Wie obenerwähnt, ist es im Falle, wo ein zusätzlicher Decoder weiter in der letzteren Stufe vorgesehen ist, notwendig, dass das Prüfwort in einem entsprechenden Decoder korrigiert wird, der zusätzlich zu den Decodern 21 und 23 vorhanden ist.

Im obigen Beispiel unterscheiden sich die Verzögerungsbeträge im Verzögerungsvorgang von der Verschachtelungsschaltung 9 von Kanal zu Kanal um einen konstanten Betrag D, es ist jedoch auch möglich, eine unregelmässige Veränderung im Verzögerungsbetrag statt der obigen konstanten Veränderung zu verwenden. Weiter sind die zweiten Prüfworte Pi solche Fehlerkorrekturendecodes, welche nicht nur von den PCM-Datenwörtern, sondern auch von den ersten Prüfwörtern Qi gebildet werden. Ähnlich ist es möglich, dass die ersten Prüfwörter Qi aus Wörtern gebildet werden, welche die zweiten Prüfwörter Pi umfassen. Zu diesem Zweck kann eine Rückführtechnik verwendet werden, so dass die zweiten Prüfwörter Pi an den Coder zurückgeführt werden, welcher die ersten Prüfwörter erzeugt.

Aus der obigen Beschreibung eines Ausführungsbeispieles der vorliegenden Erfindung kann entnommen werden, dass jeder Büschelfehler durch die Kreuzverschachtelungsarbeits-

5

10

15

20

25

30

35

40

45

50

55

60

65

11

653 503

weise so gestreut wird, dass sowohl zufällige Fehler als auch Büschelfehler durch die Technik der vorliegenden Erfindung korrigiert werden können.

Femer wird dann, wenn in der ersten Stufe der Decodie-rung ein Fehler detektiert wird, ein Kennzeichen, das das 5 Vorhandensein eines Fehlers darstellt, dem Wort beigegeben. Im Falle, in welchem das Vorhandensein oder Nichtvorhandensein eines Fehlers bei der Decodierung im zweiten Decoder festgestellt wird, wird die Möglichkeit, dass die Fehlerde-tektion in der zweiten Decodierung fehlerhaft ist, vermieden, 10

und zwar nicht nur durch die errechneten Syndrome, sondern auch durch Beurteilung der Anzahl der Fehlerkennzeichen in jedem Block, der vom ersten Decoder geliefert wird. Auf diese Weise wird die Wahrscheinlichkeit, dass ein detektierter Fehler übersehen wird, reduziert, wodurch die Wahrscheinlichkeit, dass ein Fremdton in einem übertragenen PCM-Ton-frequenzsignal erzeugt wird, minimal gemacht wird.

Es ist klar, dass durch den Fachmann verschiedene Modifikationen ausgeführt werden können, ohne dass dabei der Gedanke der vorliegenden Erfindung verlassen wird.

G

9 Blatt Zeichnungen

Claims

653 503

2

PATENTANSPRÜCHE

1. Verfahren zur Decodierung eines übertragenen digitalen Informationssignales, um darin als Folge der Übertragung vorkommende Fehler zu korrigieren, wobei das Informationssignal als Blöcke von digitalen Datenwörtern empfangen wird und an einen ersten Decoder als erste Fehlerkorrektur-Blöcke, enthaltend je eine Anzahl von Informationswörtern, eine Reihe von ersten Prüfwörtern und eine Reihe von zweiten Prüfwörtern, angelegt werden, gekennzeichnet durch die Schritte:

Decodieren der empfangenen digitalen Datenwörter im genannten ersten Decoder und Korrigieren der decodierten digitalen Informationswörter und erster Prüfwörter durch Erzeugung von Fehlersyndromen unter Benützung der zweiten Prüfwörter, wobei die korrigierten und decodierten digitalen Informationswörter einen Teil eines Blocks von ver-schàchtelten Wörtern bilden;

Hinzufügen eines Fehlerkennzeichencodes zu jedem der Wörter eines Blocks von verschachtelten Wörtern, um anzugeben, ob ein unkorrigierbarer Fehler in diesen Wörtern verbleibt;

Verzögern der Wörter jedes solchen Blockes von verschachtelten Wörtern in einer Entschachtelungsstufe um entsprechende unterschiedliche Beträge, so dass diese Worte in einer unterschiedlichen Anordnung entschachtelt werden, wodurch sich ein zweiter Fehlerkorrekturblock ergibt;

Decodieren der digitalen Informationswörter jedes solchen zweiten Fehlerkorrekturblockes in einem zweiten Decoder durch Erzeugen von Fehlersyndromen unter Benützung der ersten Prüfworte, wobei, wenn mindestens ein solches Wort als fehlerhaft festgestellt wird, mindestens ein solches fehlerhaftes Wort durch die genannten Syndrome und die ersten Prüfworte korrigiert wird, dann für jeden der genannten zweiten Fehlerkorrekturblöcke, in welche mindestens ein Wort als fehlerhaft bestimmt wurde, einen Vergleich durchführen zwischen der Anzahl der fehlerhaften Wörter, wie sie durch den Fehlerkennzeichencodes angegeben sind, mit einem vorbestimmten Wert, und endlich, wenn diese Anzahl kleiner ist als der genannte Wert, die Fehlerkennzeichencodes, die zu den korrigierten fehlerhaften Wörtern gehören, löschen, wenn jedoch die genannte Anzahl den genannten Wert übersteigt, die Fehlerkennzeichencodes ungelöscht lassen; und anschliessendes Kompensieren von irgendwelchen unkor-rigierten fehlerhaften Wörtern, welche durch den Fehlerkennzeichencode angegeben werden.
2. Verfahren nach Anspruch 1, dadurch gekennzeichnet, dass selbst dann, wenn alle Wörter im genannten zweiten Fehlerkorrekturblock als fehlerfrei bestimmt werden, alle zugehörigen Fehlerkennzeichencodes ungelöscht bleiben, wenn die genannte Anzahl den vorbestimmten Wert übersteigt.
3. Verfahren nach Anspruch 1, dadurch gekennzeichnet, dass, wenn alle Wörter im genannten Fehlerkorrekturblock als fehlerfrei bestimmt werden, die genannte Anzahl jedoch den genannten vorbestimmten Wert übersteigt, alle Wörter in diesem Block mit dem Fehlerkennzeichencode versehen werden, um einen unkorrigierten Fehler anzuzeigen.
4. Verfahren nach Anspruch 1, dadurch gekennzeichnet, dass, wenn für eine vorbestimmte Anzahl von Wörtern in irgendeinem zweiten Fehlerkorrekturblock unter Verwendung der Fehlersyndrome im zweiten Decoder bestimmt wurde, dass sie Fehler enthalten und dass die Anzahl von fehlerhaften Wörtern in einem solchen Block, wie sie durch die Fehlerkennzeichencodes angegeben werden, kleiner ist als ein vorbestimmter Betrag, alle Wörter in einem solchen Block einen Fehlerkennzeichencode erhalten zur Angabe eines unkorrigierten Fehlers.
5. Verfahren nach Anspruch 1, dadurch gekennzeichnet, dass, wenn für eine Mehrzahl von Wörtern im genannten zweiten Fehlerkorrekturblock bestimmt wurde, dass sie fehlerhaft sind und die Position jedes solchen fehlerhaften Wortes unter Verwendung eines Fehlerkennzeichencodes bestimmt wurde, die fehlerhaften Wörter korrigiert werden, und dass, wenn die Anzahl von fehlerhaften Wörtern, wie sie durch die Fehlerkennzeichencodes angegeben wird, verschieden ist von der genannten Anzahl, die Fehlerkennzeichencodes, welche zu den Wörtern im genannten zweiten Fehlerkorrekturblock gehören, unverändert bleiben, wenn jedoch die genannte Zahl gleich der genannten Anzahl ist, die Fehlerkennzeichencodes gelöscht werden.
6. Verfahren nach Anspruch 5, dadurch gekennzeichnet, dass die genannte Mehrzahl von Fehlern begrenzt ist auf nicht mehr als zwei fehlerhafte Wörter.
7. Verfahren nach Anspruch 1, dadurch gekennzeichnet, dass die im genannten ersten Decoder durchgeführte Decodierung die Bestimmung der Wortposition jedes fehlerhaften Wortes im genannten ersten Fehlerkorrekturblock umschliesst, weiter den Vergleich der Wortposition mit einer vorbestimmten Ziffer, und dass, wenn die detektierte Wortposition grösser ist als die vorbestimmte Ziffer, allen Wörtern in einem solchen Block ein Fehlerkennzeichencode zugefügt wird, um einen unkorrigierten Fehler anzuzeigen.
8. Verfahren nach Anspruch 7, dadurch gekennzeichnet, dass jedes Wort im genannten Block eine Ordnungsnummer für die Wortposition hat, und dass die genannte vorbestimmte Ziffer der Wortpositions-Ordnungszahl des Wortes mit höchster Ordnungsnummer im genannten ersten Fehlerkorrekturblock entspricht.
9. Verfahren nach Anspruch 7, dadurch gekennzeichnet, dass die im genannten zweiten Decoder durchgeführte Decodierung die Bestimmung der Wortposition jedes fehlerhaften Wortes im zweiten Fehlerkorrekturblock umschliesst, weiter den Vergleich der Wortposition mit einer andern vorbestimmten Ziffer und endlich das Hinzufügen eines Fehlerkennzeichencodes für alle Wörter im genannten zweiten Fehlerkorrekturblock zur Anzeige eines unkorrigierten Fehlers, wenn die detektierte Wortposition grösser ist als die genannte andere, vorbestimmte Ziffer.
10. Verfahren nach Anspruch 7, dadurch gekennzeichnet, dass jedes Wort im genannten zweiten Fehlerkorrekturblock eine Wortpositions-Ordnungszahl aufweist, und dass die genannte andere, vorbestimmte Ziffer der Wortpositions-Ord-nungszahl des Wortes mit der höchsten Ordnungszahl im genannten zweiten Fehlerkorrekturblock entspricht.
11. Verfahren nach Anspruch 1, dadurch gekennzeichnet, dass der Schritt des Decodierens im zweiten Decoder weiter die Berechnung der Wortposition irgendeines fehlerhaften Wortes innerhalb des zweiten Fehlerkorrekturblockes umschliesst, weiter den Vergleich der berechneten Wortposition mit der durch den Fehlerkennzeichencode angegebenen Position eines fehlerhaften Wortes und endlich die Korrektur eines solchen Wortes in der Position eines solchen fehlerhaften Wortes.