NL8104342A - Rekenmachinesysteem, gebaseerd op een symboolkorrigerende kode met twee werkmodes. - Google Patents

Description

ΡΗΝ 10.155 1 N.V. PHILIPS' GLOEILMPEOTSBRIEKEN ΤΕ EINDHOVEN.

"Rekenmachinesysteen, gebaseerd op een symboolkorrigerende kode met twee werkmodes"

De uitvinding betreft een dataverwarkende inrichting voor het bewerken van datawoorden die zijn opgebouwd uit k=2p-2 ^ 2 datasymbolen, xniddels kodewoorden die uit de respektievelijke datawoorden warden gevormd middels een foutkorrigerende kode, en welke kodewoorden bevat-5 ten n = 2p kodesymbolen, waarbij alle symbolen bestaan uit m=2s^»4 bits en deel uitmaken van een Galois lichaam GF (2111) = £ 0, a°, a1.. .a2^"2 ^ , welke inrichting bevat een eerste ingang voor een datawoord, eerste ver-menigvuldigingsmiddelen voor het vermenigvuldigen van het datawoord met een generatormatrix [gJ die bestaat uit nxk elementen van elk m 10 bits cm een kodewoord te vormen, bewerkingsmiddelen voor het bewsrken van het kodewoord tot een bewerkingsresultaat, en rekonstruktiemiddelen voor het middels een met de generatormatrix orthogonale pariteitskon-trolematrix (rJ rekonstrueren van het bij het bewerkingsresultaat beho-rende tweede datawoord ter afgifte op een eerste uitgang. Zo'n inrich-15 ting is bekend uit de voorgepubliceerde Europese Octrooiaanvrage 0031183 (aanvraagnummer 80201185.8) van dezelfde aanvrager. De bekende inrichting betreft restringer end een multiprocessorrekenmachinesysteea waarin de digitale dataverwerking is georganiseerd volgens n parallel werkende processors vocar telkens het datawoord en de data-opslag is georganiseerd 20 volgens n geheugens die telkens een kodesymbool opslaan. De bekende inrichting implementeert een foutkorrigerende kode die in twee modes kan werken: a) in een eerste, symboolkorrigerende, werkmode kan een op wille- keurige manier gestoord symbool worden gekorrigeerd.

25 b) in een tweede mode, uitwismode, kan middels veronachtzaming van een bepaald syiribool, bijvoorbeeld een verdacht symbool, een enkele bit-fout buiten het veronachtzaamde symbool worden gekorrigeerd.

De uitvinders van de onderhavige uitvinding hebben gekonsta-teerd dat een familie van foutkorrigerende kodes bestaat die uitgebrei-30 dere foutkorrigerende eigenschappen heeft en bovendien in veel verschil-lende kategorieen van dataverwerkende inrichtingen gebruikt kan worden.

Cm daarvan de vruchten te plukken heeft een dataverwerkende inrichting 8104342 ΓΗΝ 10.155 2 Λ *

I I

volgens de uitvinding het kenmerk dat de rekonstruktiemiddelen bevatten: a) tweede vermenigvuldigingsmiddelen met een tweede ingang an het bewerkingsresultaat te ontvangen ter vennenigvuldiging met een pari-teitskontrolematrix [r]= [s] · [h] · [t] on op een tweede uitgang een aan-5 tal van tenminste (n-k) =2t 2 syndroomsymbolen te vormen, waarbij (sj een niet singuliere matrix is van een afmeting van (mkxmk) bits, en de matrix |kj bevat een eerste deelmatrix van lode symbolben met de vorrn van een identiteitsmatrix, en verder bevat een tweede deelmatrix van kx(n-k) symbolen waarvan de determinant ongelijk is aan 1j=a°, en, waar-10 bij op elke rij en elke kolom van de matrix [h] de absolute waarden modulo (2m-1) van de verschillen der exponenten van de als machten van (a) geschreven symbolen telkens tenminste gelijk zijn aan (m) , terwijl elke (kxk) deelmatrix van [nj niet-singulier is: en waarbij de matrix Jr] bestaat uit mode nmxnm bits die volgens nxn 15 blokken die volgens rijen en kolommen gerangsehikt zijn en elk bestaan uit mxm bits, waarbij elke rij en elke kolom van blokken n-1 blokken ' bevat die uitsluitend uit "0"-bits bestaan, en voorts elke rij van bits en elke kolan van bits precies een "1 "-bit bevat en verder uitsluitend "0"-bits; 20 b) een moderegister dat een derde ingang en een derde uitgang bezit, waarbij een eerste inboud van het moderegister een normale mode bestuurt am de kodewoorden te behandelen als deel uitmakende van een kode met minimum Hamming-afstand over de symbolen van drie, respektie-velijk een minimum Hamming-afstand over de bits van vijf, waarbij n 25 respektievelijke tweede inhouden van het moderegister telkens een uitwisoperatie besturen van een uniek bij de respektievelijke stand behorend kodesymbool om de resterende kodesymbolen te behandelen als deel uitmakend van een kode met een minimum-afstand over de bits van drie; c) een datahervormingsinrichting met een vierde ingang om het 30 bewerkingsresultaat te ontvangen en een vijfde ingang an de syndroansym-bolen te ontvangen en voorzien van een vierde uJgang am op basis van respektievelijke deelverzamelingen van k kodesymbolen telkens een gere-konstrueerd datawoord te vormen; d) een selektieinrichting met een zesde ingang die is verbonden 35 met de tweede uitgang cm de syndroomsymbolen te ontvangen, en met een zevende ingang die is verbonden met de derde uitgang om de stand van het moderegister te ontvangen, en voorzien van een zesde uitgang die is verbonden met de derde ingang en voorts voorzien van een zevende uitgang 8104342 V 4 ESN 10.155 3 am op basis van de syndrocmsymbolen en de stand van het moderegister een selektiesignaal af te geven op de zevende uitgang cm de foutvrije kode-symbolen aan te geven en voorts een instelsignaal te geven voor het moderegister; 5 e) een poortinrichting waarvan ingangen verbonden zijn met de vierde uitgang en de zevende uitgang om een gekorrigeerd datawoord te selekteren.

Mat name in de normale mode is aldus een uitgebreidere kor-rektiemogelijkheid voor fouten gerealiseerd: bij een minimum Hamming-10 afstand van vijf kunnen dinners twee willekeurige enkelbitsfouten worden gekorrigeerd. Cp zichzelf is het bekend dat bij zo'n minimum Hairming-afstand nog twee andere werkmodes mogelijk zijn: a) korrektie van een bitfout en detektie van twee verdere enkel- bitsfouten, 15 b) detektie van vier willekeurige enkelbits fouten. Daarbij bete- kent "wiHekeurig" steeds "willekeurig geplaatst". Cp zich geeft de matrix Jh] al een aanzienlijke familie van kodes waer, die alle syste-matische kodes zijn. Door vermenigvuldiging met de matrix (sj worden oak niet systematische kodes verkregen. De matrix |t] is een zogenoemde per-20 mutatiematrix waardoar rijen^kolarmen, en bovendien bits binnen de syrn-bolen gepermuteerd kunnen worden. Als (s] en [t] identiteitsmatrices zijn blijft de oorspronkelijke kode onveranderd. De besturing van het mode-register kan plaatsvinden op basis van eerder gekonstateerde fouten.

Bij n=4 moet het moderegister in het algemsen minstens drie bits be vat-25 ten voor de vijf werkmodi. De gereciteerde oplossing leent zich in het bijzonder voor het gebruik bij zogenoemde onregelmatige logika (wild logic). Als de voorkeur gegeven moet worden aan regelmatige logika (alleen-leesgeheugens, programmeerbare logische veldschakelingen of pro-grarrmable logic arrays) is het voordelig als de rekonstruktiemiddelen 30 bevatten: a) tweede vermenigvuldigingsmiddelen met een tweede Ingang cm het bewerkingsresultaat te ontvangen ter vermenigvuldiging met een pari-teitskontrolematrix [sHsHh3-[t1 cm op een tweede uitgang een aan-tal van tenminste (n-k)=2t ^ 2 syndroomsymbolen te vormen, waarbij Jsj 35 een niet-singuliere matrix is van een afmeting van (irikxmk) bits, en de matrix JhJ bevat een eerste deelmatrix van kxk symbolen met de vorm van een identiteitsmatrix en verder bevat een tweede deelmatrix van 8104542

V

» I

*· PHN 10.155 4 kx (n-k) syrnbolen waarvan de determinant ongelijk is aan a°=1, en waarbij op elke rij en elke kolom van de matrix (H) de absolute waarden modulo (2^1) van de verschillen der exponenten van de als maohten van (a) geschreven syrnbolen telkens tenminste gelijk zijn aan (m), terwijl 5 elke (kxk) deelmatrix van .|h} niet-singulier is: en waarbij de matrix |t| bestaat uit mode nmxnm bits die volgens nxn blokken die volgens rijen en kolommen gerangschikt zijn en elk bestaan uit mxm bits, waarbij elke rij en elke kolom van blokken n-1 blokken bevat die uitsluitend uit "0"-bits bestaan en elke kolom van bits 10 precies een "1"-bit bevat en verder uitslutiend "0"-bits; b) een moderegister dat een derde ingang en een derde uitgang beziij waarbij een eerste inboud van het mode-register een normale mode bestuurt am de kodewoorden te behandelen als deel uitmakende van een kode met minimum Hamming-afstand over de syrnbolen van drie, respektievelijk een 15 minimum Hamming-af stand over de bits van vijf, waarbij n respektie-velijke tweede inhouden van het moderegister telkens een uitwisoperatie besturen van een uniek bij de respektievelijke stand behorend kodesym-bool am de resterende kodesymbolen te behandelen als deel uitmakend van een kode met een minimnm-afstand over de bits van drie; 20 c) korrektiebepaalmiddelen met een achtste ingang die verbonden is met de tweede uitgang am de syndroomsymbolen te ontvangen en een negende ingang die verbonden is met de derde uitgang cm de stand van het moderegister te ontvangen, en voorzien van een achtste uitgang om eei karrektiegrootheid af te geven en een negende uitgang voor het afgeven 25 van een foutindikatiesignaal, welke is verbonden met de derde ingang van het moderegister; d) korrektiemiddelen met een tiende ingang cm tenminste de datasymbolen van het bewerkingsresultaat te ontvangen en modulo-twee op te tellen bij de korrektiegrootheid om op een tiende uitgang een 30 gekorrigeerd datawoord af te geven. De twee oplossingen zijn nauw ver-want, en voor alle kodes op zich gelijkelijk toepasbaar. Het is gebleken dat meerbitsfouten in een enkel symbool vooral door processorfouten ont-staan; enkelbits fouten daarentegen ontspringen meest aan geheagenfunk-ties en zijn ook veelwerf van voorbijgaande aard. Er wordt nog opge-35 merkt dat voor het symbool 0 wordt verondersteld dat de exponent van ah=0 gelijk zij aan "-0O ".

Het is voordelig als voor n=4, k=2, de matrix (h) gekozen is uit: 8104342 ΕΗΝ 10.155 5 % *

(Η. _ ra00a6a10l ’ ' [ 0 a0 a10 a6 J

waarbij een elarent is van het Galois-lichaam GF(24) dat gegenereerd is met het primitieve en irreducibele polynocm ΤΓ (x) =oc4+x+1, en

LOa a a J

waarbij a? element is van het Galois-lichaam GF(24) dat gegenereerd is door het primitieve en irreducibele polynocm % (x) = x4+x3+i;

Voor een beperkte hoeveelheid redundantie is zo een grote verscheiden-10 heid aan erikelsymtoolfouten en enkelbitsfouten korrigeerbaar.

Het is gunstig als het moderegister n bits bevat die elk aan een respektievelijk kodesymbool binnen het kodewoord zijn toegewezen cm daarvoor de uitwismode te besturen. Zo wordt de in- en uitkodering van het moderegister eenvoudig gehoaden.

15 Het is gunstig als een foutregister aanwezig is met tenminste n bitplaatsen, hetwelk een elfde ingang bezit die parallel is aangesloten met de derde ingang van het moderegister cm bij detektie van een korri-geerbare fout in een symhool een symboolindikator te ontvangen ter opslag in de bijbehorende positie van het foutregister, dat voortdurend on de ontvangen symboolindikatoren middels een syiriboolsgewijze logische OF-funktie worden samengencroen met een qpgeslagen symboolindikator, dat het foutregister voorzien is van een elfde uitgang ter aansluiting cp een boekhcud- en besturingsinrichting en van een terugstelingang cm van de besturingsinrichting een terugstelsignaal te ontvangen. Zo is 25 het mogelijk cm naast een korte-termijn signalering van een opgetreden fout, ook een lange termijn-signalering te doen boekhouden. Daardoor kan in twijfelgevallen een gerechtvaardigder uitspraak worden gedaan over de betrouwbaarheid van een symbool van bepaald rangnuirmer.

Het is gunstig als het moderegister voorzien is van een extra 30 dataingang en een laadbesturingsingang cm van de besturingsinrichting een besturingswoord te ontvangen cm in een doorlaatmode de dataverwer-kende inrichting zo te besturen dat middels selektieve uitwissing van (n-k) kodesymbolen op basis van de dan resterende k kodesymbolen zonder korrektie van fouten een datawoord hervormd wordt. Zo kan de dataverwer-35 kende inrichting zelfs voortgaan als er (n-k) kodesymbolen, respektie-velijk kodesymboolplaatsen min of meer permanent onbetrouwbare ge~ gevens bevatten.

8104342

*r MT

t PHN 10.155 6

Het is gunstig als een detektor aanwezig is am in de normale mode een meerbits enkelsymbDolfoat te detekteren en daarop onver-wijld het moderegister on te stellen ter besturing van de uitwismade, waarbij kodesymbolen met hetzelfde symtoolnummer als dat waarin de . 5 meerbits enkelsymboolsfout was opgetreden, daarna worden uitgewist.

Het blijkt voordelig cot zo’n meerbitsymboolsfout te gebruiken als in-dikatie voor een onbetrouwbare kcide symboolspositie.

Voorts kan een multiprocessorsysteem volgens de stand der techniek bij gebruik van de onderhavige kode op voor del i^e manier uit-10 gebreid worden als elke deelrekenmachine verder een eigei moderegister en een eigen foutregister bevat om de behandellng van de kodesymbolen te besturen respektievelijk een gedetekteerde fout voorbijgaand te registreren. Relatief grote delen van het systeem kunnen voorbijgaand respektievelijk min of meer langdurig aanzienlijke marikementen vertonen, 15 zonder dat de werking van het gehele systeem in gevaar wordt gebracht.

20 25 30 35 _ 8104342 1 4 * * EHN 10.155 7 KOKEE BESCHRUVING VM DE FIGOREN.

De uitvinding wordt nader uitgelegd aan de hand van enkele figuren.

Fig. 1 geeft de zestien elenenten van het Galois lichaam 5 GF(24).

Fig. 2 geeft de generatormatrix en de pariteitskontrolematrix van een voorbeeldkode.

Fig. 3 geeft de metode voor het vonren van andere kodes met dezelfde eigenschappen als die welke bij Fig. 2 behoort.

10 Fig. 4 geeft de vorming van de datasymbolen op basis van alle selekties uit de kodesymbolen.

Fig. 5 geeft het vormen van een uitgebreide pariteitscontrole-matrix [q] op basis van (H).

Fig. 6 geeft een uitvoeringsvoorbeeld van een dekodeur.

15 Fig. 7a/ 7b geven de matrix voor het vormen van de syndrocnt- symbolen als-mede voor twee extra hulpfunkties van kodesymbolen.

Fig. 8 geeft het vormen van de datasymbolen volgens Fig. 4 met gebruikmaking van de extra funkties.

fig. 9 symboliseert de detektor αα voor elk syndrocrosymbool 20 de bijbehcrende symboolklasse te detekteren.

Fig. 10 geeft de vertaling van de inhoud van het moderegister naar de coder scheidene werkmodes.

Fig. 11 geeft de vertaling van de syndrocmsymboolklassen in de te gebruiken werkmodes.

25 Fig. 12 geeft de te vervullen voorwaardes op dat de respek- tievelijke keuzes uit de gerekonstrueerde versies van het datawoord gedaan moeten kunnen warden.

fig. 13 geeft de schakeling voor de keuze van de versie y32 van de datasymbolen.

30 Fig. 14 geeft de schakeling voor de keuze van de versie y31.

Fig. 15 geeft de schakeling voor de keuze van de versie y30.

Fig. 16 geeft de schakeling voor de keuze van de versie y21.

Fig. 17 geeft de schakeling voor de keuze van de versie y20.

Fig. 18 geeft de schakeling voor de keuze van de versie y10.

35 Fig. 19 geeft een schakeling voor het afleiden van een aantal stuursignalen uit de inhoud van het moderegister.

Fig. 20a.....d geven de instelkonditfes voor de respektievelij-ke bitposities van het foutregister.

8104342 *s '*

I I

J* « PHN 10.155 8

Fig. 21a......21f geven de vergelijkingen voor het afleiden van de selektiesignalen voor de respektievelijke versies van het data-woord.

Fig. 22a.....,22d geven een eenvoudiger formulering voor de 5 instelkondities voor het' foutregister.

Fig. 23 geeft de besturing van het foutregister als logische schakeling.

Fig. 24 geeft een imltiprocessorrekenmachinesysteem waarin de uitvinding is geinplementeerd.

10 Fig. 25 geeft de besturing van het moderegister als logische schakeling.

Fig. 26 geeft een andere uitvoeringsvorm van de dekodeur. BESCHRTJVING VM DE GEBRUIKTE KODE

De gebruikte kode is gekozen vanwege zijn symboolkorrigerende 15 eigenschappen. Een symbool bestaat uit een vast aantal van bijvoorbeeld m bits en kan dan 2111 verschillende waarden hebben. De verzameling van deze 2111 symbolen vorrat dan,een Galois lichaam GF(2m) waarvoor de alge-braische bewerkingen gedefinieerd zijn, zie bijvoorbeeld het artikel door T.C, Bartee et al, Information and Control, Vol. 61 (1963) p. 19-98. 20 In dit verband geeft Fig. 1 de zestien elementen van het Galois lichaam GF (2 ) en wel e§n maal geschreven als een macht reeks, en een maal, geschreven als een bitgroep. De bitgroepen kunnen worden gevormd middels het primitieve en niet-reduceerbare polynoom”f^ ($= x4+x+1. In dit en vele andere gevallen bestaan er meerdere mogelijke van zulke polynonen.

4 25 Zo kan het Galois lichaam GF(2 ) ook gevormd warden door het polynoom It*) = x4+x^+1. Het element (0000) wordt 0 genoemd, het element a°=(0001) wordt _1_ genoemd.

In het beschreven uitvoeringsvoorbeeld bestaan de datawoorden uit twee symbolen van vier bits, de (redundante) kode woorden uit vier 30 symbolen van vier bits. Fig. 2 geeft voor deze kode de generator matrix [gJ en de pariteits controle matrix (parity check matrix) (hJ , waarvan de elementen telkens vierbits-symbolen zijn. Door vermenigvuldiging van de pariteitsmatrix volgens [s] . jk] net sea niet-staguliere matrix (s] van 2x2 symbolen ontstaat een getransformeerde pariteitscontrole matrix 35 die dezelfde eigenschappen aan de kode verleent als de oorspronkelijke matrix.

De volgende grootheden van de kodewoorden worden nu gedefinieerd. Ws is het symbool gewicht van een kodewoord, dat wil zeggen het 8104342 • » * i 4 « · EHN 10.155 9 aantal symbolen van een kodewuord dat ongelijk is aan het symbool £ (0000). is het bitgewicht van een symbool, dat wil zeggen het aantal bits van een symbool dat ongelijk is aan 0. De grootheid dg is het symboolgewicht van de kode, dat wil zeggen het minitum symboolgewicht . 5 over alle kodewoorden. Daarbij wordt verondersteld dat het kodevoord (0000) en het symbool £ (0000) toelaatbaar zijn. Verder worden alleen lineaire kodes beschaiwd, dat wil zeggen dat de som (bitsgewijs modulo- 2) van twee kodewoorden veer een verder kodewoord oplevert. Daardoor zijn het minimum symboolgewicht en de minimum kode-afstand identiek.

10 Voor het bewijs wordt verwazen naar het standaardwerk in dit vakgebied "Error correcting codes" door W.W. Peterson et al, MET, Boston, 2° druk 1971.

De kode heeft de volgende eigenschappen: 1. Doordat alle (2x2) sytmatrixen van de pariteits controlematrix (H) riet-15 singulier zijn is het symboolgewicht van de kode d ^ 3. Dat betekent dat in alle gevallen een willekeurig gestoord symbool geheel korri-geerhaar is.

2. Er is geen kodewoord met symboolgewicht 4 (dus zonder symbool £) waar-bij het bitgewicht van alle symbolen gelijk is aan 1.

20 Alle kodewoorden kunnen worden geschreven als c = (a\a7, a7+V1+t alm+17+3) en voor een willekeurige keuze o i, j 3 is er geen geval dat vorcferde en vierde symbool en symboolgewicht 1 oplevert. Daarvcor zou er een paar waarden i,j moeten zijn (i^j) met i,j^£o, 1, 2, 3^ , 25 zodat ook a^’+a"'”^ 6 £a9, a^, a^, a^3 en eveneens a1Hl7+36{a°, a1, a2, a3]

Door uitscbrijven van alle mogelijkheden blijkt zo'n kombinatie niet te bestaan. Dus heeft bij een symbool gewicht 4 tenminste een symbool een bitgewicht ^ 2.

30 3. Er is geen kodewoord met symboolgewicht gelijk aan 3, waarvan twee of drie symbolen een bitgewicht hebben gelijk aan 1. Uit de generator matrix volgt dat alle kodewoorden met symboolgewicht gelijk aan 3 geschreven kunnen worden als: m i „11+i _7+i.

(0 , a , a , a ) 35 tJ- n 37+i 11+i.

(a , £ , a , a ) (a4+\ a1, £ , a 9+1) (a1, a4+1, a9+1 , £ ) 8104342 s *

» I

* \ ** * PHN 10,155 10

Daarbij mag i een willekeurige waarde (modulo-15) hebben, dat wil zeggen ife£o, 1, 2.....14} . Uit de verschillen van de exponenten van a volgt direkt, dat als een van de exponenten de waarde 0, 1, 2, 3 heeft de andere twee nooit e6n van deze vier waarden kunnen hebben.

5 Alle gevallen van twee enklebits fouten zijn nu onderling onderscheidbaar. Als dit niet zo zou zijn, meet het aldus gestoorde kodewoord na vermenigvuldiging met de pariteitscontrolematrix [hJ in twee verschillende gevallen hetzelfde syndroomresultaat geven. Anders gezegd: de bits-gewijze modulo-2 som van twee verschillende foutvektoren 10 zou dan een kodewoord moeten vormen omdat dit laatste bij vermanigvul-diging met de pariteitscontrolematrix een syndroomresultaat nul zou moeten opleveren. Dat zou namelijk slechts in de volgende gevallen kunnen voorkomen: a) het symfcoolgewicht van het kodewoord is twee; (enkelbitsfouten twee 15 aan twee op dezelfde symboolplaatsen) b) het symboolgewicht van het kodewoord is drie, waarvan twee, symbolen het bitgewicht 1 hebben; (twee enkelbitsfouten op dezelfde symboolplaats, de andere op verschillende symboolplaatsen).

c) het symboolgewicht van het kodewoord is vier; alle symbolen hebben 20 het bitgewicht 1, alle vier enkelbitsfouten op verschillende symboolplaatsen.

Geen van deze gevallen kcxat echter voor, en twee willekeurige enkelbitsfouten zijn dus altijd korrigeerbaar.

Een enkel-symboolfout kan kan alleen hetzelfde syndroan geven 25 als twee enkelbitsfouten in de volgende gevallen: a) het symboolgewicht is gelijk aan twee; b) het symboolgewicht is gelijk aan drie, waarbij twee symbolen het bitgewicht 1 hebben. Geen van deze gevallen komt echter voor en zo is dus steeds een willekeurig symbool en anderzijds ook twee willekeurige 30 enkele bitsfouten korrigeerbaar.

Voorts is bij uitwissen (erasure) van een kodesymbool, waarvan dus de foutlokator bekend is, maar de grootte van de fout niet, daarenboven nog een enkelbits fout korrigeerbaar. Dit zou alleen onmo-gelijk zijn als bij uitwissen van hetzelfde symbool twee verschillende 35 enkelbitsfouten hetzelfde syndroom zouden veroorzaken. Dit zou alleen kunnen als: a. het symbool gewicht van het kodewoord is gelijk aan twee; \ 8104342 g. -t % EHN 10.155 11 b. bet kodewoord heeft een symboolgewicht van drie, waarbij twee sytibolen een bitgewicht hetben gelijk aan een.

Geen van deze gevallen korat echter voor en zo is ook deze fout in de weglaagmode korr igeerbaar.

5 Fig. 3 geeft alle rtogelijkheden om door vermenigvuldiging van eenzelfde matrix alle pariteitskcntrolematrixen te krijgen die de boven besproken voordelige eigenschappen bezitten. Cok andere (2x2) matrixen kunnen voor de vermenigvuldiging gebruikt worden, maar dan ont-staan geen systematische kodes. Deze hebben dan wel precies dezelfde 10 fcut korrigerende eigenschappen maar. de implamentatie kost weer onder-delen. Verdere leden van dezelfde kodefamilie, met dus in-herent dezelfde foutkorrigerende eigenschappen kunnen nog gevonden warden door: a. pennuteren van de volgorde van kodesymbolen binnen een kode woord; 15 b. pennuteren van de volgorde van de kodebits binnen de respektie- velijke kodesymbolen; c. vermenigvuldigen van de pariteitskontrolematrix §ί] uitge-schreven als bitmatrix met een niet-s inguliere matrix |tJ van afmeting 8x8 bits, volgens de formules [t] . [h] ,· 20 d. uitgaan van bet andere primitieve en irreduceerbare polynocm met inherente afbeelding van de machtreeks in a op de zestien elemen-ten van bet Galois-lichaam GF(24), een en ander desgewsnst gekombineerd met een (of meer) van de bovenstaande modifikaties cm leden van dezelfde kodefamilie te genereren.

25 Daarmee is de hier gegeven uitgebreide kodefamilie de enige met de vermelde eigenschappen voor n=4/ k=2 en m=4 (datawoorden van twee sytibolen a 4 bits en een redundantiegraad van 2: kodewoorden van vier symbolen).

BESCHRIJVING VAN EEN DEKODEUR.

30 De enkodeur voor een dergelijke kode implementeert de verme nigvuldiging van de datawoorden met de generatormatrix (deze wordt steeds op elementaire manier van de pariteitskontrole-inatrix afgeleid.

Deze vermenigvuldiging kan bijvoorbeeld gebeuren met behulp van een alleen-lees (RCM) geheugen. De dekodeur is gekarpliceerder. Het blijkt 35 dat bij de gebraikte systematische kodes volgens Fig. 3 de datawoorden altijd te rekcns truer en zijn uit een willekeurig' stel van twee (k) on-gestoorde kodesymbolen. Het is voordelig om bij de konstruktie van de 8104342 5 > EHN 10.155 12 dekodeur van dit principe gebruik te maken.

Fig. 4 geeft in de eerste plaats de voming van de kodesymbo- len (c0/ c1/ c2, c3) uit de datasymbolen (dO, d1) middels de generator- matrix (fig. 3, tweede regel). Voorts zijn getoond de vorming van de 4 n 5 (2) = (^) = 6 mogelijke stellen van twee kodesymbolen, en middels de geinverteerde generatormatrix de hervorming van de datasymbolen uit deze respektievelijke stellen kodesymbolen.

Ctn nu de foutlokatie (s) te vinden wordt in de dekodeur eerst de ontvangen verzameling mogelijk gestoorde kodesymbolen vermenigvuldigd 10 met een uitgebreide pariteitskontrolamatrix [q^ . Deze is getoond in Fig. 5 en wordt uit de oorspronkelijke pariteitskontrolsnatrix verkre-gen door vermenigvuldiging met een hulpmatrix Ja| . De matrix [aJ wordt bepaald op grond van de volgende eisen: 1. alle 2x2 submatrices van JKj zijn niet-singulier en daarom 15 kan elke kcmbinatie van twee rijen van de matrix jpj gebruikt warden als pariteitskontrole matrix an de kode te definieren.

2. elke rij van de matrix |q bevat een enkel symbool £.

3. de rijen van de matrix jK kunnai gebruikt worden voor het her-berekenen van de datasymbolen op de manier zoals dit in Fig. 4 is ge- 20 toond.

Voor de keuze van de matrix |a| zijn er verschillende mogelijk-heden binnen de hier gestelde beperkingen.

Fig. 6 geeft een dekodeur in blokschema. De kodesymbolen arri-veren qp ingang 100, en wel bitserieel, parallel of gemengd. Blokele-25 ment 102 is de syndroomvormer, waarin de kodewoorden warden vermenigvuldigd met de matrix zoals aangegeven. Daardoor ontstaan de syn-droomsymbolen' sO, s1, s2, s3 die elk met een kodesymbool korresponderen. Als de kodesymbolen niet gestoord zijn, is het syndroom gelijk aan nul, het gebruik van de additionele matrix (aJ verandert daaraan niets. Het 30 blijkt dat nu de volgende. gevallen optreden.

a) Als in de normale mode geen fout is opgetreden dan hebben alle syndroomsymbolen de waarde nul (0_).

b) Als in de normale mode een enkelsymboolfout optreedt op de kodesymboolplaats i (i^£o, 1, 2, 3jjj ) dan is het syndrocmsymbool 35 s. = terwijl alle andere syndroomsymbolen ongelijk aan nul zijn.

c) Als twee enkelbitsfouten optreden op de kodesymboolplaatsen i, j (i f j) dan worden de bijbehorende syndroomsymbolen aangegeven door de beperking: 8104342 PHN 10.155 13 » 5j6{ a", a*1, aw2, a*3 $ waarbij a^i.. = het element van de matrix jQj op rij i en kolcm j. a=hji 5 Uit deze gegevens is in alle gevallen de foutlokator precies te be- palen. Bijvoorbeeld als de kodesymbolen c3 en c2 gestoord zijn, zijn de 0 12 3 syndrcmsn s3 en s2 beide een element van de verzarreling (a ,a ,a ,a ). Het amgekeerde geldt evenzo.

Karibinaties die niet aan een van de bovenstaande relaties voor 10 de syndrocmsymbolen voldoen, zijn in de normale mode niet korrigeerbaar. Kombinaties die wel aan een van de bovenstaande relaties voor de syndrocmsymbolen voldoen kunnen overigens ook veroorzaakt warden door een niet-korrigeerbare staring dan wel zelfs door een niet-detekteerbare staring.

15 In de uitwismode, bijvoorbeeld die voor bet dan als fcut ver- anderstelde kodesymbool op symboolplaats i^wordt dit kodesymbool niet in rekening gebracht. Als er dan geen verdere font optreedt in het kodewoord is bet syndroansymbool S.j=0. Als er een enkele bitfout optreedt op kodesymboolplaats j, dan geldt: 20 s1&£av, av+1, av+2, aw33 , waarin a^h^j volgens de bovengegeven definitie. Aldus vormt blokele-menet 102 in Fig. 6 pp zijn respektievelijke uitgangen voor elk kodewoord de vier syndrocxisroorden sO, s1, s2, s3. Deze warden telkens. toege-voerd aan de blokelementen 104 en 106.

25 Bldkelement 104 is de datahervarminrichting en ontvangt daartoe de vier syndrocmsymbolen en bovendien de op ingang 100 ontvangen, moge-lijkerwijze gestoarde kodesymbolen. In blokelement 104 warden (£)=6 versies van het datawoord gevorrnd, telkens uitgaande van een andere deelverzameling van als ongestoord veronderstelde kodesymbolen. Zo 30 verschijnt op uitgang 108 het datawoord dat hervonrd is op basis van alleen de kodesymbolen c2 en c3: y^r en overeenkanstig op de andere uitgangen van blokelement 104. In blokelement 106 warden uit de vier ontvangen syndrocmsymbolen zes signalen Fig. 7b afgeleid, die aangeven welke van de zes door blokelement 104 hervormde datasymbolen zijn afge-35 leid van ongestoorde kodesymbolen. Fig. 7a geeft de binaire represen-tatie van de matrix |q] uit Fig. 5, op zichzelf is de binaire represen-tatie van zo’n transfonnatie matrix gebruikelijk; elk der "1" bits re-presenteert een term die middels EXCLDSIEF-OF-behandeling voor het uit- 8104342 EHN 10.155 14 $ > P 9 eindelijke resultant m rekening meet worden gebracht.

Fig. 8 geeft de achtereenvolgens gevormde kambinaties. Daar- bij blijken de datasymbolen hervormd te kunnen warden middels de ont- vangen kodesymbolen door bitsgewijze optelling (modulo-2) van datasymr 114 5 bolen en kodesymbolen, en middels twee extra funkties, t1-(a c,+a c-) ,43 j i .

en x2=(a Cg+a Cg). Deze funkties worden in blokelement 104 additioneel gevormd volgens een uitdrukking die made in fig. 7 is getoond.

Vervolgens worden de maatregelen beschreven om van de zes, door blokelement 104 gevormde symboolparen de juiste te selekteren; deze 10 signalering gebeurt in blokelement 106. Fig. 9 geeft symbolisch aan, welke logische funkties van de syndroomsymbolen worden gevormd. Ms het syndroemsymbool s1 bijvoorbeeld deel uitmaken moet van de verzameling 4 5 6 7 (a , a , a , a'), dan wordt het betreffende symbool bitsgewijs vergeleken 4 met elk der vier desbetreffende elementen van het Galois lichaam GF (2 ) 15 uit Fig. 1. Zo'n voorwaarde is eerder genoemd bij het lokaliseren van twee enkelbitsfouten. Ms aan de betreffende voorwaarde is voldaan dan wordt de korresponderende uitgangssignaalbit in Fig. 9 "waar".

De dekodeur kan in negen verschillende toestanden werken, name-lijk achtereenvolgens:

20 de normale mode, genoemd: RM

uitwismode, kodesymbool "3" veronachtzamen: EM3 " " ”2" " : EM2 " " "1" " : EM1 II II HQtl t. ; ΕΜ0 25 doarlaatnode qp kodesymbolen 3 en 2: DOS 32 " ” " 3 en 1: MDS 31 " " " 3 en 0: MQS 30 " " 2 en 1: MQS 21 " " " 2 en 0: MQS 20 30 " " " 1 en 0: MOS 10

Element 110 in Fig. 6 stelt voor een besturings- en signale-ringsregister. Fig. 10 geeft de uitvoering met een vierbits moderegis-ter en de daartoe noodzakelijke uitkodering. Fig. 11 geeft daarbij de criteria waaraan de beschreven signalen p en g moeten voldoen en de 35 daar te vormai modesignalen, alsmede de vulling van het foutsignale-ringsregister dat eveneens vier bits he vat. De gebruikte afkortingen hebben daarbij de volgende betekenissen: 8104342 H3N 10.155 15 r EE: het betreffende kodesymhool wordt uitgewist BE: optreden van een enkelbitsfout DBE: optreden van een dubbelbitsfout SSE: optreden van een enkelsymboolfout 5 NE: f outloos, respektievelijk geen fout gesignaleerd.

De indices achter de letters geven het kodesymboolnunmer aan waarcp de uitwissing- , respektievelijk de fcutlokalisatie betrekking heeft. Nu betekent een "1" in de kolommen voor de grootheden p en q dat de desbetreffende grootheid ook die waarde moet hebben. Een "0" betekent 10 dat de desbetreffende grootheid de waarde "1” niet mag hebben. Als geen causaliteitsrelatie bestaat is geen teken aangegeven.

Er wordt nog op gewezen dat als q. .=1, dan is q. ,=0 voor k^j. Voorts, id indien q. .=q.. =1, dan zijn alle andere grootheden q,,^1.

Xj JX j£i«

In deze uitvoeringsvorm wordt de fout in feite niet gekorri- 15 geerd, maar wordt door fcutlokalisatie het goede paar kodesymbolen geselekteerd cp basis waarvan de datasyrribolen moeten warden terugge- WDnnen. In de tabel kant elke korrigeerbare fout eenmaal voor. Het geval NE (foutloos) kcmt tweemaal voor: dan kan het systeem das paraL- lelsgewijs zcwel gebruik maken van de eerste twee kodesymbolen (y10) 20 als van de laatste twee kodesymbolen (y32). Dit betekent dat van de EN-poorten 112 tot en met 122 in fig. 6 zowel de EN-poorten 116 and 118 dcorlaatbaar zijn (deze EN-poorten werken telkens over een breedte van 8 bits). Het bovenstaande is evenwel geen bezwaar. De doorverbin- dingseenheid 124 bevat namelijk voor elke uitgaande bitlijn van 8 bits 25 brede uitgang 126 een OF-poort met zes ingangen: elk van deze ingangen wordt gevoed door een der respektievelijke EN-poorten 112 t/m 122.

In het geval er geen fout is geldt evenwel steeds dat de beide uit- gangsresultaten y32 en y10 identiek zijn. Het blijkt dat deze dubbele definitie van het geval "NE" zowel onderdelen als tijdsvertraging 30 spaart tegenover andere oplossingen.

Fig. 12 geeft de voorwaarden die vervuld moeten zijn voor de respektievelijke keuzes uit de informaties y32, y31, y30, y21, y20, y10; deze voorwaarden zijn eerst gegeven als een son van produkten die direkt uit de tabel van Fig. 11 volgt. Vervolgens zijn ze telkens nog eenmaal 35 gegeven als een produkt van somtermen. voor deze onzetting is nog gebruik gemaakt van de eigenschap dat de signalen RM, EM. en MOS.. disjunkt zijn: 1 xj slechts een van deze elf signalen kan telkens tegelijk optreden.

8104342 ΡΗΝ 10.155 16 Λ ν • \

Het blijkt dat de herschreven funkties gerealiseerd kunnen warden met relatief weinig bouwstenen en een kleine vertraagtijd voor de door loop der signalen. De schakelingen voor het vormen van de stuursignalen, die dus de poorten 112 t/m 122 in Fig. 6 besturen, is voor de respektie-5 velijke gevallen getoond in de figuren 13/ 14, 15, 16, 17, 18. De delen van de funkties die alleen afhangen van de inhoud van het moderegister zijn getoond in Fig. 19.

Het foutregister, deel uitmakend van element 110 in Fig. 6 bevat de volgende informatie; 10 1) als er geen fouten zijn bevat het register uitsluitend nullen.

2) als er een enkelbitsfout of een enkelsymboolfout optreedt bevat het foutregister een enkele "1" die het bijbehorende kodesymbool aanwijst.

3) als er twee enkelbitsfouten optreden bevat het foutregister 15 twee informaties "1" die de respektievelijke bijbehorende kodesymbolen aanwijzen.

4) in de uitwismode bevat het foutregister een "1" voor het kodesymbool waarin een enkelbitsfout optreedt, alle andere bits van het foutregister zijn nul.

20 5) als er een detekteerbare, niet korrigeerbare fout optreedt war den alle bits van het foutregister op "1" gesteld. Zo dient het foutregister voor het signaleren van aktuele, of reeds eerder opgetreden fouten. Daarentegen dient het moderegister voor het (mede)besturen van de aktuele werkmode en het kiezen uit de informaties y32.....y10. In. dit 25 uitvoeringsvoorbeeld hebben beide registeis evenveel bitposities als het aantal kodesymbolen in het kodewoord. Er zijn evenwel andere keuzes rnoge-lijk. Zo kunnen ook twee foutregisters van vier bits gebruikt worden: een voor het signaleren van de enkelbitsfouten en een voor het signaleren van enkelsymboolsfouten. Deze uitgebreide uitvoering wordt. hier niet 30 nader beschreven.

Zo wordt telkens een. fouts ignalerende tetrade toegevoerd aan het foutregister die bitsgewijze met de reeds opgeslagen informatie wordt samengenomen. Dat betekent dat het niet mogelijk is om twee ver-schillende kodewoorden (na elkaar) optredende enkelsymtoolfouten te 35 onderscheiden van een dubbele enkelbitsfout in hetzelfde kodewoord.

Dit is geen bezwaar omdat het foutregister voor de ext erne signalering wordt gebruikt en niet voor de direkte bes turing. Het aan het foutre- 8104342 ESN 10.155 17 - «.

*, gister toe te voeren woord is afgebeeld in Fig. 11, meest rechtste kolan, waardoar het verband net de inhoud van het moderegister, de verschillen-de reeds vermelde criteria en het type font wordt uitgebeeld. Hit de tabel van Fig. 11 warden eerder de selektiefunkties afgeleid: deze 5 gaven aan walke versie van het datawoord (van de zes mogelijke versies) gefcruikt moest worden. De inhoud van het foutregister wordt gedeelte-lijk bepaald door juist deze selektiefunkties. De voorwaarden waaronder achtereenvolgens de eerste, tweede, derde en vierde bit van het foutregister gelijk aan 1 gemaakt worden zijn afgebeeld in Fig. 20 a.....

10 20d. Daarbij worden al deze bits ook nog op een gesteld in het geval van een detekteerbare, doch onkorrigeerbare fout; de destetreffende konditie is evenwel niet in Fig. 20 a... .d afgebeeld. Deze voorwaarden worden afgeleid uit de selektiefunkties.

Fig. 21a......21f geven aldus de uit de respektievelijke figu- 15 ren 13, 14, 15, 16, 17, 18 af te leiden funkties. Daarbijwordt mede gebruik gemaakt van de eigenschap dat de variabelen RM, EM^, en onderling disjunkt zijn: op een zeker moment kan slechts hoogstens len van hen de waarde "1" bezitten.

Er wordt nog gebruik van de volgende funkties af te leiden zijn 20 van de tabel in Fig. 10: RM + ΕΜ0 = Hj. i^.

EM + EM1 = Mq. M^. RM + EM 3 = MQ.M1 RM + EM2 = Mr

Daarbij geven Mg......M2 de inhouden van de respektievelijke raoderegis- 25 terbits aan, terwijl een streep boven een grootheid de geinverteerde waarde aanduidt. Zo is uit vergelijking (34)-(Fig. 12); (35) (Fig. 20), (40)-(Fig. 21) af te leiden dat aan bitpositie "O" van het foutregister de waarde "1" moet warden toegevoerd onder de volgende voorwaarde: (RMfEMI). SED01.SEL10+(RMfEM2) .SEL02.SEL20+(RMfEM3) .SEL03.SEL30 = 1 30 Door konibinatie met de zojuist hiervoor gegeven uitdrukking worden de voorwaarden verkregen die in Fig. 22 a... .d zijn afgebeeld. Deze figuur geeft ook de overeenkomstige expressies voor de andere drie bits van het foutregister.

Daarbij geeft Fig. 23 de realisatie met twaalf EN-poorten (&) 35 200.....222, vier OF-poorten (OR) 224....230 en een NIET-OF-poort 232 cm de instelvoorwaarden te vormen. Het foutregister is uitgevoerd met vier data-flipflops 234.....240 waarvan de klok-besturing niet is ge- 8104342 « * PHN 10.155 18 toond. Deze flipflops zijn voorts van een niet-getekende terugstel-ingang voorzien. Het vormen van de OF-funktie tussen oude inhoud van de data-flipflops en een nieuw f out-signalerend woord gebeurt middels de OF-poorten 242....248. Als een detekteerbare onkorrigeerbare fout 5 ontstaat zijn· alle syndroomsymbolen SO, S1, S2, S3 ongelijk aan rail.

Aan de andere kant is er geen enkele aan het foatregister toe te voeren (middels de daarvoor geschakelde OF-funkties) bit gelijk aan "1". Dit wDrdt veroorzaakt door het feit dat de hierv06r afgeleide funkties al-leen reageren (de waarde "1" vormen) op een korrigeerbare fout. Dit 10 feit wordt gebruikt om de funktie af te leiden die een detekteerbare onkorrigeerbare fout signaleert (een niet-detekteerbare fout brengt uiteraard geen reaktie in het systeem teweeg^.ALs dus de funkties van Fig. 22 alle vier onwaar zijn en bovendien de funkties p2 en p3 de waarde nul bezitten dan wordt middels NIET-OF-poort (geinverteerde uit-15 gang) 232 een logische "1" aan alle bitposities van het foutregister toegevoerd. Het fout-register kan met voordeel gebruikt worden als boekhoudinrichting voor de korte termijn: er kunnen een aantal recente fouten in worden gesignaleerd. In een dataverwerkend systeem wordt het foutregister bijvoorbeeld als volgt gebruikt. Periodiek wordt het 20 foutregister door een supervisie-inrichting uitgelezen en teruggesteld op nul. Dit heeft geen direkte invloed op de inhoud van het moderegis-ter zoals later blijken zal. De supervisie-inrichting werkt bijvoorbeeld onder software-besturing. De inhoud van het foutregister wordt dan bijvoorbeeld gebruikt voor een lange-termijn boekhouding: voor elk 25 kodesymbool wordt het aantal foutsignaleringen over een bepaalde periods gesorameerd. De kodesymbolen waarvan de sonroen de laagste zijn kunnen als relatief het meest betrouwbaar worden beoordeeld, en juist deze worden dan in de doorlaatmode gebruikt. De signalering van een onkorrigeerbare fout (poort 232) kan gebruikt worden om een onderbreek-30 signaal te genereren of on een nieuwe poging (retry) te besturen. Op zichzelf zijn zulke herpogingen in dataverwerkende inrichtingen gebrui-kelijk. De voor zo'n poging noodzakelijke deeloperaties hangen af van het soort inrichting en de aktuele databewerking; kortheidshalve worden ze niet nader beschreven.

35 Fig. 24 geeft een rekenmachinesysteem waar de uitvinding in geinplementeerd is; wat betreft de interkonnektie der subsystemen is dit, maar dan voor gebruik met een minder effektieve foutkorrigerende 8104342 > - * PHN 10.155 19 deels kode, al/yoorgepubliceerd in de geciteerde Europese Octrooiaanvrage 0031183 (PHN 9652). De datawoorden bestaan uit 8 bits, die veronder-steld zijn als twee syrribolen van vier bits. In het getoonde viervoudige system wordt elk datawoord in elke processor bewarkt en in het daarbij 5 behorende geheugen, respektievelijccp de uitgang van de deelrekenmachine telkens vertegenwoordigd door vier kodebits. Cp de lijnen 62, 64, 66, 68 verschijnen de datawoorden. Deze warden bewarkt in de respektie-velijke processar-elementen 12, 14, 16, 18. De processor-elementen genereren daarop dataresultaatwoorden op de lijnen 90, 92, 94, 96,.res-10 pektievelijk adreswoorden op de lijnen 70, 72, 74, 76. Voor de respek-tievelijke geheugens kan telkens een cp zichzelf bekende geheugenbeheers-eenheid aanwezig zijn (memory management unit)Deze is niet nader aan-gegeven. Via de adresdekodeurs 27, 29, 31, 33 warden de lokale geheugens 28, 30, 32, 34 geadresseerd. In de kodevormers 20, 22, 24, 26 wordt tel-15 kens uit een ontvangen 8-bits-datawcord een 16-bits kodesymbool gevormd, zodat de uit een datawoord gevormde kodesymbolen tesamen een kodewoord vorrnen. Deze kodesymbolen warden aan de geheugens 28, 30, 32, 34 ter cpslag aangeboden. De uitgelezen kodesymbolen warden geregenereerd in de uitleesversterkers 36, 38, 40, 42. Dit laatste kan ook gebeuren 20 zonder tussentijdse opslag in de geheugens. De kodesymbolen zijn alle toevoerbaar aan alle registers 46, 48, 50, 52. Deze registers zijn aangesloten op de rekonstruktiexnrichtingen oftewel dekodeurs 54, 56, 58, 60 cm uit de kodewoorden de datawoorden te hervormen ter presentatie op de lijnen 62, 64, 66, 68. De elemental 46, 54, 12, 20, 28 en 36 zijn 25 in een separaat isolatiegebied voor fouten opgenomen. Daarbij wordt ver-ondersteld dat de fouten in twee verschillende isolatiegebieden-voor-fouten onafhankelijk zijn; in vele gevallen is deze eis voor veel kategorieen van fouten vervuld, als elk isolatiegebied-voor-fouten bijvoorbeeld een aparte plaat met gedrukte bedrading plus opgatonteerde 30 komponentai, respektievelijk een apart geintegreerd circuit beslaat. Zo vormt de schakeling van de figuur vier respektievelijke isolatiegebieden-voor-fouten. De synchronisaties van de operaties in de vier isolatiege-bieden-voor-fouten is kortheidshalve niet aangegeven. De processoren wer-ken volgens overeenkanstige programma's. Verder zijn de subsystems In 35 de respektievelijke isolatiegebieden voor fouten cp overeenkanstige ma-nier opgebouwd, behalve de kodevormers (20, 24, 26, 28) implenenteren elk een ander algorithms cm uit het 8-bits datawoord de vier respektie- 8104342 < *» FHN 10.155 20 velijke kodesymbolen te vormen. Voorts kunnen de besturingen van de . infonratierekonstruktieinrichtingen 54, 56, 58, 60 onderling verschil-lend zijn, al naar gelang de bestur ingsmode waarin het rekenrnachine-systeem werkt. Voor de beschrijving van de aansluiting van een rand-5 apparaat wordt verwezen riaar de geciteerde Europese Octrooiaanvrage 0031183 (PHN 9652).

De informatierekonstruktiernrichting nu kan opgebouwd zijn vol-gens het principe dat naar aanleiding van Fig. 6 is besproken. Daarbij kan in de uitwismode alle apparatuur van een geselekteerd isolatiegebied 10 voor fouten (FIA) veronachtzaamd worden. Het is gebleken dat de normale inode die twee willekeurig gelegen bitfouten 0f een enkelsymboolfout kan korrigeren, zeer goed geschxkt is voor het korrigeren van fouten die in het geheugen optreden. Deze fouten zijn gewoonlijk onderling onafhankelijk, bovendien zijn ze veelal voorbijgaand zg. "soft errors".

15 Symboolfouten, die dus een geheel symbool onbetrouwbaar maken, zijn veelal veroorzaakt door een falende processor. Het blijkt dat zulke symboolfouten veelal een permanent karakter hebben. Toch behoeven ze in dit rekenmachinesysteem niet op korte termijn gerepareerd te warden, omdat de dekodeurs kunnen omschakelen naar de uitwismode. Dit laatste 20 beleid brengt evenwel een nieuw gevaar met zich mede, nanelijk dat tegelijkertijd een enkelsymboolfout (^ 2 bits in een symbool) en een verdere enkelbitsfout optreden. Deze is in de normale mode (PM) niet korrigeerbaar. Het daaram van belang zo spoedig mogelijk cm te schake-len van de normale mode naar de uitwismode. De overschakeling geschiedt 25 onder de volgende voorwaarden: a) tevoren is het systeem in de normale mode (M^M^ 1^^=0000).

b) er treedt een enkelsymboolfout op waarvan het bitgewicht ten-minste "2" bedraagt.

Voor kodesymbool G3 is de konditie b) vervuld als: 30 S3 = 0 -½ p3 = 1 S1^a°, a1, a2, a3] ^ q13 = 0 SI f 0 p1 = 0 m = 1.

(de eerste en derde konditie geven een enkelsymboolfout, het tegenge-35 stelde van de tweede konditie geeft een enkelbitsfout daarbij. De konditie is dus: RM.p3.pT . g13 = 1 8104342

A

PHN 10.155 21

Voor de andere kodewoorden zijn de kondities: c2:M.p2.pT.q12 = 1 C1 :EM.p1 .p2.q21 - 1 c0:RM.p0.p2.q20 = 1 5 Verder bevat in Fig. 24 elk isolatie-gebied-voor-fouten een afzonderlijk foatregister (148, 150, 152, 154) dat bestuurd wordt door uitgangs-signalen van de respektievelijke dekodeurs (54, 56, 58, 60) en waarvan de uitgangssignalen op bun beurt weer aan de centrale bestuursinrichting 44 warden toegevoerd. Tenslotte zijn in dit verband aangegeven de res-10 pektievelijke terugstellijnen vanuit de centrale bestuursinrichting 44 voor de foutregisters. De multipliciteit van deze bestuurslijnen is niet aangegeven. Voorts bevat in Fig. 24 elk isolatiegebied-voor-fouten een 4-bits moderegister respektievelijk 140, 142, 144, 146.

Deze warden bestuurd door uitgangssignalen van de respektievelijke 15 dekodeurs (54, 56, 58, 60). Anderzijds bestuurt de inhoud van elk mode-register de werkmode van de bijbehorende dekodeur. Voorts wordt de in-stelling van hat foutregister mede bestuurd door de inhoud van bet bijbehorende moderegister. Deze relatie is door een extra pijl telkens aangegeven (gedeelten van de schakeling van Fig. 23 zouden in Fig. 24 dus 20 in bet foutregister zijn gelegen). Tenslotte ontvangt elk moderegister nog besturingssignalen van de centrale besturingsinrichting 44. De op~ bcuw van deze besturingslijnen wordt nader besproken. In de foutloos werkende toestand wordt nu in alle isolatiegebieden hetzelfde progranma verwerkt. Dit geldt ook in de normale mode. Als echter in een bepaald 25 isolatiegebied voor fouten een systematische verwerkingsstoring optreedt. wordt de daaruit hoogstwaarschijnlijk resulterende symboolfout net bit-gewicht ^ 2 in de andere isolatiegebieden gedetekteerd; deze zullen dan naar de uitwismode cmschakelen zodat bet falende isolatiegebied niet langer in rekening wordt gebracht. In het falende isolatiegebied 30 zelf behoeft deze signalering niet beslist korrekt te zijn; het is zelfs mogelijk dat daar (bijvoorbeeld door falen van het moderegister) een geheel andere besturing cptreedt. Desalniettemin blijft het systeem als totaliteit korrekt funktioneren middels de drie andere isolatiegebieden voor fouten.

35 Fig. 25 geeft het vierbits moderegister en de bijbehorende besturing. De konditiesignalen warden voor de respektievelijke modebits gevorird middels de vier EN-poorten 250......256. Deze warden via de 8104342 * It

J

PHN 10.155 22 OF-poorten 258-......264 toegevoerd aan het eigenlijke register dat is gevormd uit vier data-flipflops 266......272. De klokbesturing van deze data-flipflops is niet apart aangegeven. De data-uitgangen warden samen-gencmen in de NIET-OF- (NOR) -poort 274: het uitgangssignaal daarvan (EM) 5 indiceert de normale node. Voorts is de schakeling voorzien van een extra besturingsingang 276 en een vier-bits dataingang 278. Door middel van vier EN-poorten 280-286 kan dan een willekeurige informatie van buiten-af warden toegevoerd/ bijvoorbeeld onder besturing van de residentiele software van besturingsinriohtlng 44 in Fig. 24. Zo kan bijvoorbeeld de 10 doorlaatmode-ingang gebracht worden, als de lange-termijn-boekhcuding van de gedetekteerde fouten daartoe aanleiding geeft.

De konditiesignalen voor de moderegisterbits worden mede afge-leid van de funkties SEL .. die in Figs. 13.....18 zijn gevormd/ dus bij- ij voorbeeld voor flipflop 266: 15 RM.p3.pT.SEL13=RM.p3.pT (q13+EM3-+M3S20) = FM.p3.pT.qT3.®.MDS20 -EM.p3.pT.q13 (want als EM=1 zijn EM3 en MDS20 gelijk aan nul. Daarbij werkt een "1"-signaal op de besturingsingang 288 als toestenniings (enable-)signaal. Dit mag alleen in bepaalde fases van de dataverwer-king worden gevormd/ bijvoorbeeld als alle detektiesignalen (p^/SEL^) 20 tot rust zijn gekcmen.

Fig. 26 geeft een eerste alternatief voor de dekodeur met gebruikmaking van. een voorgeprogranmeerd alleen-lees geheugen (EOM).

Eerst wordt uit het zestienbits kodewoord middels een EXCLUSIEF-OF- matrix (300) een 8-bits syndrocm gevormd. Dit syndroom bevat de volle- 25 dige informatie betreffende de fout. Daarcra is het mogelijk om met een alleen-lees-geheugen 302 een 8-bits korrektiewoord te vormen. Dit kan bitgewijs modulo-2 bij de tweedatasymbolen worden opgeteld (304) om het ongestoorde datawoord te hervormen. Voorts zijn op hetzelfde moment de vier aan het foutregister 316 toe te voeren signaalbits te vormen.

30 Cmdat het systeem in verschillende modes kan opereren, meet het alleen-lees-geheugen ook de vier bits van het moderegister 308 ontvangen, omdat de interpretatie van het syndroom medebepaald wordt door de mode.

12

Het alleen-lees-geheugen meet dus een kapaciteit hebben van 2 worden a 12 bit. Voorts bevat Fig. 25 de binaire versie van de pariteitskon-35 trolematrix. DLtkan geirriplementeerd worden met 38 twee-ingangs EXCLDSlEF-OF-poorten. Door een boomvormige rangsehikking daarvan levert het iirplementeren van deze matrix een vertraging van slechts drie poort-vertraagtijden. De interaktie tussen moderegister en foutregister vindt 8104342 FHN 10.155 23 plaats op de manier van Fig. 23 en is niet separaat aangegeven; ook de verdere besturing van bet moderegister 308 is niet apart getoond.

Het is ook rnogelijk cm de pariteits kontrolematrix met een verder alleen-lees-geheugen te iiqplementeren. Daartoe wordt alleen het 5 niet-identiteitsdeel van de pariteitskontrolematrix (rechtsboven in

Fig. 26) gehruikt: . 6 10 S S = Φ0 a6 > · &

Het resultaat wordt qpgetela bij Cy C2 (EXdXJSIEF-OF) cm het twee — symboolsresultaat s S te produceren. Dit laatste wordt op precies dezelf- 10 de manier gehruikt als getoond in Fig. 26.

De kode is evenzeer toepasbaar voor langere datawoorden. Zo kan een 16-bits datawoord direkt gesplitst worden in vier symbolen van vier bits; deze worden telkens paarsgewijze behandeld. Uiteraard is er dan eei grotere variatie rnogelijk cm een systeem te verdelen in een aantal 15 isolatiegebieden voor fouten. Voorts beperken de geschetste metoden zich niet tot symbolen van maximaal vier bits.

20 25 30 35 8104342

Claims (8)

1. Dataverwerkende inrichting voor het bewerken van datawoorden die zijn opgebouwd uit k = 2p-2$>2 datsymbolen, middels kodewoorden die uit de respektievelijke datawcorden worden gevormd middels een fout-korrigerende kode, en welke kodewoorden bevatten n=2p kodesymbolen, 5 waarbij alle symbolen bestaan nit m=25 4 bits en deel uitraaken van een Galois lichaam GF(2m)=^£/ a°, a^ ......a^*^ welke inrichting bevat een eerste ingang voor een datawoord, eerste vermenigvuldigingsmiddelen voor het vermenigvuldigen van het datawoord met een generatormatrix [g^ die bestaat uit nxk elementen van elk m bits cm een kodewoord te 10 vorrnen, bewerkingsmiddelen voor het bewerken van het kodewoord tot een bewerkingsresultaat, en rekonstruktiemiddelen voor het midrtels een met de generatormatrix orthogonale pariteitskontrolematrix R rekon-strueren van het bij het bewerkingsresultaat behorende tweede datawoord, ter afgifte op een eerste ingang, met het kenmerk, dat de rekonstruktie-15 middelen bevatten: a) tweede vermenigvuldigingsmiddelen (102) met een tweede ingang cm het bewerkingsresultaat te ontvangen ter vermenigvuldiging met een pariteitskontrolematrix = [s] .[h] .jirjcm op een tweede uitgang een ^anr tal van terminste (n-k) - 2tsyndrocm-symbolen (SO,SI,S2,S3) vorment'1/ 20 [sjeen niet singuliere matrix is van een afmeting van (mkxmk) bits, en de matrixjVJ bevat een eerste deelmatrix van kxk symbolen met de vorm van een identiteitsmatrix, en verder bevat een tweede deelmatrix van kx(n-k) symbolen waarvan de determinant, ongelijk is aan 1_ = a0, en waarbij op elke rij en elke kolcm van de matrix £hJ de absolute waarden 25 nodulo (2m—1) van de verschillen der exponenten van de als machten van (a) geschreven symbolen telkens tenminste gelijk zijn aan (m), terwijl elke. (kxk) deelmatrix van [hJ niet-singulier is: en waarbij de matrix T bestaat uit . nmxnm bits die volgens nxn blokken die volgens rijen en kolommen gerangschikt zijn en elk bestaan 30 uit mxm bits, waarbij elke rij en elke kolcm van blokken n-1 blokken bevat die uitsluitend uit "0,'-bits bestaan, en voorts elke rij van bits en elke kolcm van bits precies een ”1"-bits bevat en verder uitsluitend "0"-bits; b) een moderegister (110) dat een derde ingang 35 en een derde uitgang bezit, waarbij een eerste inhoud van het mode-register een normale mode bestuurt cm de kodewoorden te behandelen als deel uitmakende van een kode met minimum Hamming-afstand over de symbolen van drie, respektievelijk een minimum Hamning-afstand over de 8104J42 > « EHN 10.155 25 bits van vijf, waarbij n respektievelijk tweede inhouden van het node-register telkens een uitwiscperatie besturen van een uniek, bij de res-pektievelijke stand behorend kodesymbool an de resterende kodesymbolen te behandelen als deel uitmakend van een kode met een minimum-afstand 5 over de bits van drie; c) een datahervorminrichting (104) met een vierde ingang (100) an het bewerkingsresultaat te ontvangen en een vijfde ingang an de syndrocm-syrribolen te ontvangen en voorzien van een vierde uitgang (Y32, Y31, Y30, Y21, Y20, Y10) an op basis van respektievelijke deelverzamelingen 10 van k kodesymbolen telkens een gerekonstrueerd datawoord te vormen. d) een selektie-inrichting (106) met een zesde ingang die is verbonden met de tweede uitgang on de syndroansymbolen te ontvangen, en net een zevende ingang die is verbonden met de derde uitgang cm. de stand van het moderegister te ontvangen en voorzien van een zesde uitgang die 15 is verbonden met de derde ingang en voorts voorzien van een zevende uitgang an op basis van de syndroaisymbolen en de stand van het mode-register een selektiesignaal af te geven op de zevende uitgang cm de foutvrije kodesymbolen aan te geven en voorts een instelsignaal te geven voor het moderegister; 20 e) een poortinriditing (112-122) waarvan ingangen verbonden zijn net de vierde uitgang en de zevende uitgang an een gekorrigeerd datawoord te selekteren.

2. Dataverwerkende inrichting voor het bewerken van datawoorden die zijn opgebouwd uit k=2p-2 ^2 datasymbolen, middels kodewoorden die 25 uit de respektievelijke datawoorden warden gevormd middels een fout- korrigerende kode en welke kodewoorden bevatten n=2p kodesymbolen, waarbij alle syrnbolen bestaan uit m=2s^4 bits en deel uitmaken van een C o 1 2^2 2 Galois lichaam GF(2m)=^_0, a , a .... a h welke inrichting bevat een eerste ingang voor een datawoord, eerste vermenigvuldigingsmiddelen 30 voor het vermenigvuldigen van het datawoord met een generatormatrix^Gj die bestaat uit nxk elementen van elk m bits cm een kodewoord te vormen bewerkingsmiddelen voor het bewerken van het kodewoord tot een bewerkingsresultaat, en rekonstruktiemiddelen voor het middels een met de generator-matrix crthogcnale pariteitskontrolematrix^R^ rekons truer en van het 35 bij het bewerkingsresultaat behorende tweede datawoord, ter afgifte cpeen eerste uitgang, met het kenmerk, dat de rekonstruktiemiddelen bevatten: a) tweede vermenigvuldigingsmiddelen (300) met een tweede ingang om 8104342 PHN 10.155 26 1* , * het' bewerkingsresultaat te ontvangen ter vermenigvuldiging met een pari-teitskontrolematrix [r1=[s].[h].[tJcto op een tweede uitgang een aantal van tenrainste (n-k) = 2t 2 syndroomsymbolen te vormen, waarbij £"sj een niet singuliere matrix is van een afmeting van (itikxrrik) bits, en 5 de matrix £ H^bevat een eerste deelmatrix van kxk symbolen net de vorm van een identiteitsmatrix en verder bevat een tweede deelmatrix van kx(n-k) symbolen waarvan de determinant ongelijk is aan a°=1_, en waar- bij op elke rij en elke kolom van de matrixΓ H~l de absolute waarden in ^ J modulo (2 -1) van de verschillen der exponenten van de als machten van 10 (a) geschreven symbolen telkens tenminste gelijk zijn aan (m), terwijl elke (kxk) deelmatrix van DO niet-singulier is: en waarbij de matrix bestaat uit nmxnm bits die volgens nxn blokken die volgens rijen en kolcmmen gerangschikt zijn en elk bestaan uit mxm bits, waarbij elke rij en elke kolom van blokken n-1 blokken 15 bevat die uitsluitend uit "0"-bits bestaan en elke kolom van bits precies έέη "1"-bits bevat en verder uitsluitend "0"-bits; b) een moderegister (308) dat een derde ingang en een derde uitgang bezit, waarbij een eerste inhoud van het moderegister een normale mode bestuurt an de kcdewoorden te behandelen als deel uitmakende van een 2o kode met minimum Hamming-afstand over de symbolen van drie, respektieve-lijk een minimum Hamming-afstand over de bits van vijf, waarbij n res-pektievelijke tweede inhouden van het moderegister telkens een uitwis-operatie besturen van een uniek, bij de respektievelijke stand behorend kodesymbool an de resterende kodesyiribolen te behandelen als deel uit-25 makend van een kode met een minimumrafstand over de bits van drie; c) korrektiebepaalmiddelen (302) met een achtste ingang die verbonden is met de tweede uitgang cm de syndroamsymbolen te ontvangen en een negende ingang die verbonden is net de derde uitgang on de stand van het moderegister te ontvangen, en voorzien van een achtste uitgang on 30 een korrektiegrootheid af te geven en een negende uitgang voor het af-geven van een foutindikatiesignaal, welke is verbonden met de derde ingang van het moderegister; d) korrektiemiddelen (304) met een tiende ingang cm tenminste de data-symbolen van het bewerkingsresultaat te ontvangen en modulo-twee op 35 te tellen bij de korrektiegrootheid am op een tiende uitgang een ge-korrigeerd datawoord af te geven.

3. Dataverwerkende inrichting volgens conclusie 1, of 2, met het kenmerk, dat voor n=4, k=2, de matrix £ Hjgekozen is uit: 8104542 EHN 10.155 27 * Λ « fH l_fa0 0 ab a10 l r[oa°a10a* waarbij a1 een element is van het Galois-lichaam GF(24) dat gegenereerd is met het primitieve en irreducihele polynocm^x) = x4+x+1, en 5 Γη 1-Fa° 9. a5 a9l r2Joa°a9a5 waarbij a-^ element is van het Galois-lichaam GF(2^} dat gegenereerd is door het primitieve en irreducibele polynocxnTC(x) = x^+x^+1. 1Q

4. Dataverwerkende inrichting volgens conclusie 1, 2 of 3, met het kenmerk, dat het moderegister n bits bevat die elk aan een res-pektievelijk kodesymbool binnen het kodewoord zijn toegewezen cm daarvoor de uitwismode te besturen.

5. Dataverwerkende inrichting volgens een der conclusies 1 tot 15 en net 4, net het kenmerk, dat een foutregister (110, 306) aanwezig is met terrains te n bitplaatsen, hetwelk een elfde ingang bezit die parallel is aangesloten met de derde ingang van het moderegister cm bij detektie van een korrigeerbare fout in een symbool een symboolindikator te ontvangen ter opslag in de bijbehorende positie van het foutregister, 2Q dat voortdurend de ontvangen symboolindikatoren middels een symbools-gewijze logische OF-funktie (242-248) warden samangenanen met een opge-slagen symboolindikator, dat het foutregister voorzien is van een elfde uitgang ter aansluiting op een boekhoud- en besturings inrichting een terugstelsignaal te ontvangen. 2g

6. Dataverwerkende inrichting volgens conclusie 5, met het kenmerk, dat het moderegister voorzien is van een extra dataingang (278) en een laadbesturingsingang (276) cm van de besturingsinrichting een besturingswoord te ontvangen an in een doorlaatmode de dataverwerkende inrichting zo te besturen dat middels selektieve uitwissing van (n-k) kodesymbolen op basis van de aan resterende k kodesymbolen zonder korrektie van fouten een datawoord hervormd wordt,

7. Dataverwerkende inrichting volgens een der conclusies 1 tot en met 6, met het kenmerk, dat een detektor aanwezig is am in de normale mode een meerbits enkelsymboolfait te detekteren en daarop onverwijld het moderegister cm te stellen ter besturing van de uitwismode, waarbij kode-symbolen met hetzelfde symboolnuinner als dat waarin de meerbits enkel-symboolsfout was opgetreden, daama worden uitgewist.

8. Multiprocessor— rekenmachinesysteecn dat is opgebouwd uit n deel— 8104342 PHN 10.155 28 f. 14 * *' rekenmachines die gelegen zijn in respektievelijke isolatiegebieden voor fouten en elk bevatten voor gebruik in een dataverwerkende inrich-ting volgens een der conclusies 1 tot en net 7, een informatiekonstruk-tie-inrichting cm alle kodesymbolen van een te bewerken kodewoord te 5 ontvangen en daaruit een datawoord te rekonstrueren, processormiddelen om het datawoord op overeenkomstige manier als in de andere deelreken-machines te bewerken, een kodevormer om uit een bewerkt datawoord een kodesymbool te vormen, zodat de verzameling der aldus gevormde kodesymbolen een kodewoord vormt, een geheugen om het gevormde kodesymbool 10 op te slaan en een uitgang voor een kodesymbool, met het kenmerk, dat elke deelrekenmachine verder een eigen moderegister en een eigen fout-register bevat om de behandeling van de kodesymbolen te besturen, respektievelijk een gedetekteerde fout voorbijgaand te registreren. 15 20 25 30 35 \ 8104342