SE466578B - Foerfarande och anordning foer korrigering av ett block av kodsymboler - Google Patents

Description

15 20 25 30 35 466 578 b) vara korrigerbar i sig, men risken för inkorrekt korrektion ökar när kodordens längd ökar. För ett minimiavstånd större än tre, är risken för inkorrekt korrektion mindre, men förblir fortfarande betydande vid långa kodord (innefattande många symboler).

UPPFINNINGSFÖREMÅL Ändamålet med uppfinningen är att göra avkodningen tillförlitligare genom att göra det slutliga utförandet av en korrektion i ett kodord beroende av en ytterligare felindikerande information som inte avser hela kodordet utan endast kodsymbolen som möjligen skall korrigeras i detta ord, och som sålunda gör felkorrektionen tillförlitligare. Enligt upp- finningen antas det att en felaktig korrektion märkbart kan omvandla en kodsymbol som hittills var korrekt till en felaktig kodsymbol.

SUMMERING AV UPPFINNINGEN Ändamålet enligt uppfinningen uppnås genom att förfarandet av det slag som angivits innefattar följande steg: a. insamling av ett fullständigt block av kodsymboler; b. bestämning av alla syndromsymboler hos de första kodorden och de andra kodorden och bildande av en flagga för varje kodord för vilket syndromen avviker från 0; c. summering av antalet flaggor för alla första kodord och summering separat från detta av antalet flaggor för alla andra kodord; -d. bestämning av ett felläge för ett korrigerbart fel för ett första kodord med ett syndrom som avviker från noll; e. detektering av ett andra kodord som anges vara inkorrekt och som innehåller det ifrågavarande felläget, och korrigering av det ifråga- varande felet endast i händelse av ett positivt detekteringsresultat, medan ett nästföljande första kodord adresseras i överensstämmelse med steget d. i det motsatta fallet; f. uppdatering av syndromen hos det ifrågavararande första kodordet och det ifrågavarande andra kodordet efter_en korrektion i överensstäm- melse med steg e, uppdatering av de ifrågavarande två flaggorna och minskning av summeringsresultaten av antalet flaggor endast om de båda uppdaterade syndromen är noll, och därefter adressering av ett näst- följande första kodord i överensstämmelse med steget d, -fi 10 15 20 25 30 35 466. 578 g. utbyte av funktionen hos första kodord och andra kodord efter adres- seringen av åtminstone alla första kodord som varande inkorrekta och upprepning av stegen d, e, och f tills tvâ successiva utföranden av stegen d, e, f, inte alstrar en ytterligare modifiering för alla rådande första kodord; h. tillförande av ett block av kodsymboler med signalering av dess korrekthet eller inkorrekthet.

Det har visat sig att många mönster av inkorrekta symboler sålunda snabbt och korrekt kan korrigeras. Härigenom undviks särskilt försignaleringen att ett kodord är korrekt. Uppfinningen avser även anordning för utföran- de av förfarandet innefattande mottagarmedel för mottagning och uppsam- ling av ett fullständigt block av kodsymboler, första aritmetriska medel vilka matas av mottagarmedlen för att bilda ett antal syndromsymboler per kodord ur de mottagna symbolerna, uppdateringsmedel som är matade av de första aritmetriska medlen för att lagra en flagga per kodord för vilket syndromen avviker från noll, och för separat uppdatering av ett summe- ringsresultat för antalet flaggor för de första kodorden och för de andra kodorden, andra aritmetriska medel som är matade av de första aritmetris- ka medlen för att för varje kodord bestämma, om möjligt och nödvändigt, en eller flera korrektionssymboler, korrektionsmedel som är matade av mottagarmedlen och de andra aritmetriska medlen för att addera en korrek- tionssymbol till en inkorrekt symbol, och en utmatningsanordning för att presentera ett företrädesvis korrekt block för en användaranordning, kän- netecknad av att en serieordnare är anordnad som har ett antal positioner för att bestämma en korrektionssymbol och en lokaliseringssymbol i ett läge för godtyckligt första kodord, varvid nämnda serieordnare innefattar adresseringsmedel för adressering av ett syndrom av ett ifrågavarande andra kodord medelst nämnda lokaliseringssymbol och även innefattande en första detektor för att endast under styrningen av ett senare syndrom som avviker från noll korrigera kodsymbolen som är adresserad av den senare lokaliseringssymbolen och för att uppdatera eventuellt syndrom som hänför sig därtill, och en andra detektor för att endast under styrningen av ett syndrom hos det ifrågavarande andra kodordet som då kan vara lika med noll styra uppdateringsmedlen för att uppdatera flaggorna för det ifråga- varande första och andra kodordet för att minska summeringsresultaten och att därefter adressera ett nästföljande första kodord, varvid serieordna- ren även innefattar en utbytningsanordning för att efter att ha passerat genom alla lägen som svarar mot åtminstone de inkorrekta första kodorden 10 15 20 25 30 35 466 578 4 utbyta funktionen hos första och andra kodord och för aktivering av ytterligare lägen hos nämnda lägen, varvid en tredje detektor är anordnad för att vid aktivering av nämnda utbytningsanordning detektera eventuell modifiering som införts under de två senaste passagerna längs de då rådande första kodorden och för aktivering av nämnda utmatningsanordning i händelse av ett negativt detekteringsresultat. En tilltagande realise- ring är sålunda realiserad som ett resultat av inbegripandet av ett antal elementära detekteringar.

Ytterligare tilltalande egenskaper hos uppfinningen kommer att beskrivas i de osjälvständiga patentkraven. I dessa realiseras aspekter som ökar behandlingshastigheten och/eller tillförlitligheten och/eller avkodningskapaciteten.

KORT BESKRIVNING AV FIGURERNA Uppfinningen kommer att beskrivas närmare nedan under hänvisning till nâgra figurer.

Fig. 1 visar schematiskt ett exempel på en uppsättning av ett block av kodsymboler; Pig. 2 är en detaljerad representation av ett block av kodsymboler såsom de används i ett s k CD-ROM format; Fig. 3 visar kvalitetskontrollmatrisen för de använda Reed-Solomon koderna; Fig. 4 visar schematiskt en anordning enligt uppfinningen; Fig. 5 visar ett flödesdiagram i överensstämmelse med uppfinningen; Fig. 6 visar några exempel på fel mönster. Appendix A innehåller en lista med rubriker för Pig. 5.

BESKRIVNING AV EN FÖREDRAGEN UTFÖRINGSFORM Pig 1. visar schematiskt ett allmänt exempel på uppsättningen hos ett block av kodsymboler där varje kvadrat representerar en symbol. En symbol är en grupp bildad av ett fast antal bitar, exempelvis tre eller fyra bitar, men vanligtvis flera. Åtta är ett attraktivt värde i detta avseende. För längre symboler blir vanligtvis den ökande komplexiteten hos operationerna en nackdel. För enkelhets skull antas det att koden är symmetrisk på symbolniván. Detta är emellertid inte nödvändigt för genomförande av uppfinningen. I föreliggande exempel innefattar blocket 70 datasymboler som är numrerade som D.10...D19, D20...D29, D30...D79. fl, 10 15 20 25 30 35 4s¿ s7s Blocket innehåller tio första kodord hos en första Reed~Solomon-kod som vart och ett innefattar sju datasymboler och två redundanta symboler.

Exempelvis innefattar det första ordet i denna serie datasymbolerna D10...D70 och de redundanta symbolerna P10, P20. Det andra ordet innehåller de nio symbolerna hos den andra kolumnen. Det tionde ordet innehåller de nio symbolerna den tionde kolumnen. När symbollängden är tillräckligt lång för dessa kodord, kan minimiavständet mellan två möj- liga korrekta kodord vara lika med tre taget över symbolerna. Detta innebär att en inkorrekt symbol kan korrigeras (eller att som mest två inkorrekta kodsymboler kan detekteras). A andra sidan innehåller blocket nio andra kodord av en andra Reed-Solomon-kod. Vart och ett av dessa ord innehåller tre redundanta symboler och tio andra symboler. De andra symbolerna kan utgöras av datasymboler eller redundanta symboler av första ord Reed-Solomon-koden. Exempelvis innefattar det första ordet hos denna serie datasymbolerna D10...D19 och de redundanta symbolerna Q11, Q12, Q13. Det andra ordet innehåller de tretton symbolerna hos den andra raden. Det nionde ordet innehåller de tretton symbolerna hos den nionde raden, d v s de redundanta symbolerna P20...P29, vilka var och en är förbunden med ett första kodord hos den första Reed-Solomon-koden och de redundanta symbolerna Q91, Q92, Q93 hos den andra Reed-Solomon-koden. När symbollängden är tillräckligt láng för de senare kodorden kan minimi- avståndet mellan tvâ möjligen korrekta kodord vara lika med fyra taget över symbolerna. Detta innebär att en inkorrekt symbol kan korrigeras och att dessutom en andra inkorrekt symbol kan detekteras (eller att åtminstone tre inkorrekta kodsymboler kan detekteras). Samma generator- matris används för alla kodord hos den första Reed-Solomon-koden. Samma generatormatris används för alla kodord hos den andra Reed-Solomon- koden. I detta fall bildar var och en av den elfte och upp till och med den trettonde kolumnen även ett första kodord hos den första Reed-Solomon-koden där symbolerna Q81...Q83, Q91...Q93 verkar som om redundanta symboler och symbolerna Q11...13, Q21...23, Q71...73 verkar som datasymboler. Sålunda utgör alla symboler varje gång del av ett första kodord hos den första koden, liksom ett andra kodord hos den andra koden. En sådan konfiguration benämns (reell) produktkod.

Blockets uppsättning kan modifieras. Exempelvis kan antalet data- symboler per kodord vara ett annat. Det kan även vara desamma för båda koderna. Antalet redundanta symboler per kodord kan även vara ett annat, men för en korrektion pá basis av endast ett kodord måste det uppgå till 10 15 20 25 30 35 466 578 åtminstone två. Vidare kan en pseudoproduktkod vara berörd, där inte alla redundanta symbolerna även utgör del av de två kodorden. Det följande är ett exempel: De vertikala kodorden är bildade på samma sätt som visat i fig. 1. De horisontella kodorden bildas inte, utan istället bildas diago- nala kodord. De första kodorden består då av exempelvis D10, D21, D32,..., D76, P17, P28, D19, Q21, Q32, Q43. Det andra kodordet består av symbolerna D20, D31,... D75, P16,..., D18, D29,..., Q31,..., Q53, o s v.

I detta fall används samma generatormatris varje gång för alla vertikala kodord liksom för alla diagonala kodord. Emellertid utgör symbolerna Q11... Q93 inte del av ett vertikalt kodord i detta fall. Andra sätt att utföra en pseudoproduktkod är även möjliga. I detta fall kan indikeringen för en kodsymbol som skall korrigeras härledas på olika sätt ur ett eller flera kodord innehållande kodsymbolerna som möjligen skall korrigeras.

Symbolkorrigerande koder andra än Reed-Solomon-koder är även kända, exem- pelvis sidonärgränsande koder (by-adjacent codes).

Fig. 2 är en detaljerad representation av uppsättningen av ett block av kodsymboler som använts för så kallad CD-ROM format. Detta är en föredragen utföringsform. Det finns fyra 43 x 24 8-bits datasymboler. Det finns 43 P-kod ord på en (26, 24) Reed-Solomo-kod. Alla dessa kodord är anordnade i en kolumn. Det finns 266 ord hos en (45, 43) Reed-Solomon kod. Vad gäller datasymbolerna är dessa ord anordnade enligt den visade diagonalen. De redundanta symbolerna är visade på de två nedre linjerna.

Sålunda utgör Q redundanserna inte del av P-ord.

AVKODNINGSFILOSOFIN Kodformatet enligt fig. 2 per kodord betyder att en felsymbol kan korrigeras varje gång, eller att två felsymboler kan detekteras. I detta avseende visar fig.3 paritetsmatriserna HP, HQ hos de använda Reed-Solomon-koderna. Generatorpolynomet hos det ifrågavarande Galois fältet är (x3+x4+x3+x2+1), varvid a är roten ur detta och sålunda ett primitivt element hos Galoisfältet. Alla beräkningar utförs i detta fält. När en felaktig symbol korrigeras i ett kodord, men i själva verket fler än en symbol är inkorrekt, uppgår sannolikheten att detta faktum inte upptäckts till approximativt n/2m, där m är symbollängden i bitar och n är kodordets längd i symboler. För P-koden och Q-koden uppgår denna sannolikhet till approximativt 10% respektive 18%. Sannolikheten att ett inkorrekt kodord inte kommer att detekteras som sådant uppgår till 1/22m = 1.5 x 10'5 (1/2 3m i fallet med tre redundanta symboler per 10 15 20 25 30 35 46¿ 57s kodord).

Avkodningen kommer att accelereras väsentligt om alla syndromer endast beräknas en gang och om endast korrektionsbidraget till syndrom- symbolerna bestäms när en kodsymbol korrigeras. Antag exempelvis att en symbol hos det första P-kodordet (första kolumnen i fig. 2) korrigeras. I detta fall mäste syndromsymbolerna hos Q-ordet av vilket den ifråga- varande symbolen utgör del korrigeras i överensstämmelse med: SO' S1 som: S1 + a44 Y.

När den korrigerade symbolen, exempelvis är talet 0946, kommer det därmed förbundna Q-ordet att vara sammansatt av symbolerna 946, 990, 1034, 1078, 4, 48, . 558, 602. Exponenten (44) följer direkt ur paritetsmatrisen HQ. I denna matris är Y storleken pà korrektionen (uttryckt som en symbol). För andra symboler som skall korrigeras, korrigeras syndromena genom symbolkorrektionen Y multiplicerad i GF(23) med den aktuella potensen för a. Därför finns det så manga syndromsymbo- ler som det finns redundanta symboler;: 2 x 43 + 2 x 26 = 138.

Datasymbolerna är numrerade fràn 0000 till 1031. De redundanta symbolerna hos P-orden är numrerade från 1032 till 1117. Den redundanta symbolen som har ordningsnumret MP, förbunden med kodordet som har ordningsnumret MP, har då numret (( 43 x MP) + NP). De redundanta symbolerna hos Q-orden är numrerade från 1118 till 1169. Den redundanta symbolen som har ordnings- numret MQ förbundet med kodordet med ordningsnumret MQ har då numret (44 x MQ + 43 x NQ) mod. 1118.

Det är uppenbart att för avkodningen av P-orden är det ifråga- varande ordningsnumret NP känt. Ur avkodningsoperationen kan ordnings- numret MP hos symbolen som skall korrigeras härledas. Ur MP och NP kan återfinnas MQ och NQ för att ur korrektionen härleda modifieringen som skall tillföras syndromsymbolerna hos Q-koden. Omvänt gäller desamma för korrektionen av ett ord hos Q-koden. Det följande gäller för numren pá datasymbolerna: NP = MQ 43 X MP + NP = (44 X MQ + 43 X NQ) mod. 1118 I händelse av en P-korrektion följer ur detta att 10 15 20 25 30 35 466 578 8 MQ = NP NQ = MP - NP med. 26 I händelse av en Q-korrektion följer att: NP = MQ MP = MQ - NQ mod. 26.

De sistnämnda gäller endast symbolnumren 0-1117, eftersom redundans-symbolerna inte utgör del av något ord hos en P-kod.

Om emellertid en reell produktkod (fig. 1) är aktuell, är det alltid nödvändigt att modifiera syndromen hos de båda kodorden av vilka den ifrågavarande kodsymbolen utgör del i händelse av en korrektion. I detta fall gäller dessutom att MQ = NP och MP = NQ.

UTFÖRINGSFORMER FÖR EN LÃSANORDNING INNEFATTANDE EN AVKODARE ENLIGT UPPFINNINGEN Fig. 4 visar ett blockschema för en anordning för användning enligt uppfinningen. Lagringsmediumet utgörs av en skiva med en diameter pá 12 cm på vilken kanalbitar är lagrade i form av optiskt läsbara läsbara spår såsom känt för "kompaktskiva“. Block 22 representerar ett vridbord med motor, servosystem, centreringssystem, lasersystem, spårföljningssystem etc. Uppfinningen avser emellertid inte specifika funktioner hos dessa element. Lässystemet alstrar kanalbitar. I demodulatorn 22 omvandlas en serie på 17 successiva kanalbitar (inklusive distansbitar) till en kodsymbol med 8 kodbitar. I den första avkodaren 24 är en ram på 32 kod- symboler bildad genom antiförvrängning (de-scrambling). Denna ram kodas medelst redundanta symboler som ingår i denna, så att 28 kodsymboler återstår. Under avkodning, kan en korrektion av en eller flera symboler ske. För korthets skull kommer denna avkodningsfunktion inte att beskri- vas här. Koden är en Reed-Solomon kod. Andra korrigeringskoder kan även användas. I det interfolierande elementet 26 deinterfolieras de 28 kodsymbolerna mellan ett motsvarande antal ramar som innehåller 28 sym- boler vardera. I den andra avkodaren 28 avkodas en sådan ram medelst 4 redundanta symboler innehållna i denna, så att 24 kodsymboler återstår.

Under denna avkodningsfunktion kan en eller flera symboler korrigeras.

För korthets skull kommer inte denna avkodningsfunktion heller att beskrivas. De avkodade symbolerna uppträder i form av 8 parallella bitar på linjen 38. En ytterligare symbolviss omgruppering av symbolerna 10 15 20 25 30 35 578 sker även, men denna funktion kommer inte att beskrivas för korthets skull.

Symbolerna på elementets 28 utgång är organiserade som sektorer med formatet som jag visat i fig. 2. Av denna anledning kan elementet 28 innefatta en ytterligare anordning för omkonstruktion av följden av symboler (såsom känt genom den nämnda patentansökan). Antiförvrängning, deinterfoliering och rekonfigurering kan oftast med fördel utföras medelst ett minne med slumpvis åtkomst (RAM) i vilket ett stort antal fördröjningslinjer eller först-in-först-ut-anordningar (FIFO-anordningar) med olika fördröjningstider/längder realiseras. Detta är ett vanligt sätt och den ifrågavarande utrustningen kommer inte att beskrivas här. Blocken 22-28 har sålunda huvudsakligen en funktionsangivande funktion. På hård- varunivån är organisationen vanligen centrerad på en buss som samverkar med ALU, minne, och I/O subsystem.

En sektor innehåller först av allt synkroniseringsinformation följt av huvuddata, möjligen subhuvudtata, och slutligen annan data. Elementet 30 är en detektor. Detektorn aktiveras av synkroniseringsinformationen, vilket är möjligt genom att synkroniseringsinformationen har ett innehåll som i princip inte uppträder någon annanstans i dataflödet. Efter igen- kännandet av denna information aktiveras en symbolräknare i detektorn för att räkna ned de mottagna symbolerna. Det är sålunda känt när synkroni- seringsinformationen följs av ytterligare data som är skyddad genom koder med maximiseparabelt avstånd. En specifik symbol kan ange att denna kod i själva verket har realiserats eller utelämnats. Detekteringssignalen är tillförd avkodaren 34 som en initieringssignal via linjen 40. Denna signal återställer adressräknarna till de givna ursprungliga värdena och inställer andra kvantiteter såsom kommer att beskrivas till 45. Avkodaren 34 kan sålunda utgöras av en programmerad (mikro) processor innefattande beskrivna element, må vara för en annan kod, i den tidigare holländska patentansökan 8400629 (som motsvaras av amerikanska patentansökan 705.752) i sökandens namn och som härmed intas som hänvisning. En enhet för utförande av operationer i det ifrågavarande galois-fältet, ett data- minne, ett syndromminne, ett minne för flaggor hos de första och andra kodorden och räknemekanism för bestämning av två summor ur detta, ett programminne och därmed förbundna adresserings- och avkodningsorgan är anordnade, liksom anslutningsorgan för anslutning av nämnda element. För en sektor kan därför åtminstone lagras 1032 datasymboler och 138 redun- danta symboler (eller 138 syndromsymboler), 69 flaggor, två räknerör, och 10 15 20 25 30 35 466 578 10 ett antal hjälpstorheter (se nedan).

Efter avkodningsoperationerna, kan lagrade data göras tillgängliga för en användaranordning (icke visad för enkelhets skull) via en utgång 36. Korrektionen kan då redan ha skett. Alternativt är det möjligt att endast presentera själva korrektionsstorheterna (lokaliserare+korrige- rare) när data redan har gjorts tillgängligt för användaren på ett annat sätt. Dessutom avger anordningen 34 en indikering "korrekt/inkorrekt", i beroende av kvaliteten på det avkodade resultatet.

AVKODNINGSSTRATEGIN Den allmänna strategin kommer att beskrivas under hänvisning till flödesschemat i fig. 5. Först samlas allt innehåll hos en sektor, åtminstone vad det gäller den del som är skyddad genom pseudoproduktkoden (100). Alla syndromsymboler hos P-orden bestäms sedan. Alla P-ord med en syndrom som avviker från 0 tilldelas en första etikett (flagga) och de första etiketterna räknas för hela kodblocket (CP). Därefter bestäms alla syndromsymbolerna för Q-orden. Alla Q-ord som har ett syndrom som avviker från O tilldelas en andra etikett och dessa andra etiketter räknas för hela kodblocket: CQ. För given tillämpningsanvändning kan användas tre- valenta eller flervalenta flaggor. I detta fall innebär en flagga "00": kodord är korrekt och har alltid varit korrekt; "11" innebär: kodord har ett syndrom som avviker från 0: “10“ innebär: kodord har korrigerats så att syndromet därefter blev 0 (så 01 uppträder inte i detta fall). Även efter korrektion finns sålunda en given grad av signalering av antalet korrigerade fel. Efter bestämning av de två räkningarna, avgör systemet om avkodningen börjar med P-kodorden eller med Q-kodorden. När antalet P-etiketter är större eller lika med antalet Q-etiketter börjar avkod- ningen med P ord; x: = P; y; = Q. I det fall (mindre sannolikt) att det finns fler Q-etiketter än P-etiketter, börjar avkodningen med Q-ord; y:=P; x:=Q. Det har visat sig att i genomsnitt reducerar detta val i första fall antalet fel per kodord som skall avkodas, varigenom sannolik- heten för att omedelbart lyckas är högre. När den första och andra koden har ett annat minimiavstånd mellan de ifrågavarande kodorden, är det van- ligtvis fördelaktigt att starta med kodorden hos koden med det största avståndet. Slutligen inställs ett antal aritmetriska parametrar på de korrekta värdena, såsom antalet x-ord och y-ord, ett ordningsnummer för ett rådande ord, och värdena på en bivalent storhet corrx inställs på "falsk" och värden på en bivalent storhet corry inställs på “sann“. Sys- 10 15 20 25 30 35 4661578 11 temet fortskrider därefter till block 102 i vilket nästa x-kodord adres- seras: I detta fall det första. I block 104 detekteras om syndromet hos detta ord är lika med noll. Om detta är fallet inställs etiketten (x-eti- ketten) hos detta kodord på noll (uppdaterad) och summan av de ifrågava- rande etiketterna (106), naturligtvis om denna etikett hade värdet 1. Om denna etikett hade värdet 0 fortsätter systemet till block 108 utan att något åtgärdande vidtages. Snabba operationer uppnås genom att i blocket 102 det näst första kodordet med en etikett som avviker från 0 adresse- ras. I block 108 detekteras då om det ifrågavarande x-ordet var det sista i serien av märkta x-ord. Detta är ofta inte fallet, varför systemet åter fortskrider till blocket 102. När ett syndrom som avviker från 0 detekte- ras i blocket 104, fortskrider systemet till blocket 110. I detta block beräknas läget för den ensamma antagna inkorrekta symbolen. I blocket 112 detekteras om den ifrågavarande symbolen utgör del av ett Y-ord vars eti- kett även har värdet 1. Ett flertal möjligheter existerar: a. läget för den inkorrekta symbolen ligger under gränsen för kodordet eftersom symbolnumret är större än 45 respektive 23; b. den ifrågavarande inkorrekta symbolen utgör del av endast ett kodord; c. det ifrågavarande y-ordet har en etikett med värdet "0"; d. det ifrågavarande y~ordet har en etikett med värde "1".

Följaktligen är korrektionen omöjlig i fall a. Detta anger att ett abso- lut okorrigerbart fel vid denna tidpunkt, exempelvis genom att i själva verket två symboler hos det ifrågavarande kodordet är inkorrekta. Detta fel kan möjligen korrigeras i ett senare stadium (se nedan). Fall b kor- rigeras, men som ett ytterligare skydd förblir etiketten förbunden med det ifrågavarande kodordet omodifierad. Fallet c betraktas att vara för ovisst och korrektionen utförs inte; etiketterna förblir även omodifiera- de (emellertid skulle de kunna avse en bra korrektion när det ifrågava- rande y-ordet innehöll ett icke detekterbart fel). Fallet d betraktas som varande en tillräckligt "tillförlitlig" korrektion och som därför ut- förs. I fallet a, c återgår systemet till blocket 108. När undersökningen i blocket 112 är positiv (Y), fortsätter systemet till block 114 i vilket felet korrigeras. Detta kan alltid ske. Storheten corrx görs "sann" (om den redan var sann förblir den så). Detta anger att åtminstone en korrek- tion har utförts under passagen genom x-orden. Därefter instâlls syndro- met hos det ifrågavarande x-kodordet på 0 i blocket 114. Detta är alltid korrekt på g a minimiavståndet 23. Dessutom uppdateras syndromet hos det ifrågavarande y-ordet i blocket 116 för att ta hänsyn till den utförda korrektionen. Uppdateringen kräver färre beräkningar än den totala omräk- 10 15 20 25 30 35 466 578 12 ningen av syndromet hos det ifrågavarande ordet. Korrektion av ett kodord resulterar i en noll-syndrom även när minimiavståndet hos en kod är stör- re än 3, så att det då omedelbart kan anta noll. I blocket 118 detekteras om den modifierade y-syndromen har värdet 0. Om detta inte är fallet återgår systemet till block 102. Om det modifierade y~syndromet har vär- det “0" inställs båda etiketterna på 0 (uppdaterad) i blocket 120 och bå- da räkningarna minskas. Systemet återgår därefter till blocket 102. Fal- len a till d ovan är angivna vid de ifrågavarande övergångarna. Implicita detekteringar av fallen a, b i blocken 110 respektive 114 har utelämnats för enkelhets skull.

När det sista ordet har behandlats (block 108 alstrar ett positivt resultat), fortsätter systemet till blocket 122. I detta block detekteras om antalet x-etiketter som mest är lika med 2. När antalet är större än 2, fortskrider systemet till blocket 130. I detta block kontrolleras om någon korrektion har skett under den sista korrektionsoperationen (x-ord) eller under den näst sista operationen. Om inget av detta har skett kan inga ytterligare korrektioner utföras och systemet fortskrider till bloc- ket 134: fel. Kodblocket är inte korrigerbart. Efter den första korrek- tionsoperationen kan denna rörelse inte utföras, eftersom en "noll" attrappkorrektion har försökt efterliknas av det ursprungliga antagandet hos corry. Om en korrektion har skett, fortsätter systemet till block 132; funktionerna hos x och y utbyts där. Dessutom inställs storheten corrx på "falsk". Ett av initieringsstegen i blocket 100 består samtidigt i att ett givet värde även tilldelas corry, särskilt värdet "sann". Vida- re inställs ordräknare på ett begynnelsevärde så att det första verkligen kommer att adresseras i blocket 102.

När det i blocket 122 detekteras att endast en eller två x-etiket- ter återstår, kommer systemet att utföra en korrektion av y-orden, varvid x-etiketterna då fungerar som pekinformation. När antalet x-etiketter uppgår till 0, kommer detta att utgöras av en atrappoperation och syste- met kommer att fortsätta direkt till blocket 126. När antalet x-etiketter uppgår till 1 eller 2 antas att alla y-ord har ett syndrom som inte är lika med 0 och är inkorrekt exakt i det ifrågavarande x-ordläget.

När systemet slutligen når blocket 126, används en CR information som är känd genom den nämnda publikationen och som ingår i datasymboler~ na hos kodblocket vilket används för att detektera om korrektionen är korrekt. Om detta är fallet fortsätter systemet till blocket 128 och an- vändarinformationen kan göras tillgänglig. Om detta inte är fallet fort- 10 15 20 25 30 35 466.578 13 skrider systemet till blocket 134. Eventuella ytterligare försök att återvinna data (genom förnyade läsförsök, skugginformation och liknande) ligger utanför ramen för föreliggande uppfinning. I blocket 134 signa- leras det att korrektion är omöjlig. När det i blocket 122 detekteras att antalet flaggor uppgår till tre eller flera (åtminstone lika med minimi- avståndet hos y-kodorden), fortskrider systemet till blocket 130. I detta detekteras om någon korrektion har skett. Efter de första försöken efter- liknas ett nollte försök (corry). Om inga modifieringar har skett (n) kommer korrektion att vara omöjlig och systemet kommer att fortsätta till blocket 134. Om eventuell modifiering har skett, kommer systemet att fortsätta till blocket 132. I givna fall kan endast corrx betraktas i blocket 130. I blocket 132 övertas värdet på corrx. Därefter initieras corrx åter. Funktionerna hos x-orden och y-orden utbyts i en operation (betecknad genom parenteser). Systemet kommer därefter att återgå till blocket 102.

Figurerna 6a~6f visar några specifika felmönster för vilka en reell produktkod med ett minimiavstånd på tre över symbolerna antagits. Pig 6a visar sex fel (kryss) i ett block på 8 x 8 symboler. Dessa fel berör varje gång en separat rad liksom en separat kolumn (P-ord respektive Q-ord), så att alla korrektioner måste utföras efter en adresserings- operation i en riktning. I fig Gb är alla fel belägna i en kolumn.

Korrektion av kodordet i denna kolumn är därför omöjlig. Korrektion av radorden resulterar emellertid omedelbart i ett fullständigt korrigerat kodblock. I fig 6c kan en rad inte korrigeras. En kolumn är även okorri- gerbar. Alla andra rader och alla andra kolumner kan korrigeras. Under den första serien av adresseringsoperationer kan alla radord (utom det relevanta) korrigeras. Under den efterföljande serien av adresserings- operationer kan alla kolumnord korrigeras. I fig 6d kan korrektionen uppnås endast om det enda radordet som har inkorrekt symbol korrigeras. I detta fall finns två ord som innehåller två inkorrekta symboler i båda riktningarna. Exempelvis korrigeras de två inkorrekta kolumnorden då, varvid indikeringen av de inkorrekta radlägena (etikett) används som pek- information. Detta är ett exempel på ett mönster som är korrigerat i överensstämmelse med blocket 124 i fig 5. Fig 6e visar ett mönster i vilket endast radorden kan korrigeras och som använder pekinformation bildad över en kolumn. Fig 6f visar ett exempel på ett enkelt mönster som inte kan korrigeras. 10 15 20 25 30 35 466 578 14 Appendix A: 100: start 102: nästa märkta x-ord 104: syndrom = noll? 106: eliminera x-etikett, minska x-räkning 108: sista märkta x-ord? 110: beräkna felläge 112: svarar mot det märkta y-ordet? 114: korrekt symbol; corrx: = sann; x-syndrom: = 0 116: modifiera y-syndrom 118: modifiera y-syndrom = noll? 120: eliminera x-etikett: minska x-räkning eliminera y-etikett: minska y-räkning 122: O 124: 1,2 raderkorrektion i y-riktning, x-etikettslokalisering 126: C.R.C. O.K.? 128: O.K. , STOPP 130: corrx + corry = true? 132: corrx: = corry; corrx: = falsk; (Y: = X; X= = Y) 134: fel, stopp.

Claims (8)

4e¿ s7s 15 PATENTKRAV

1. Förfarande för korrigering av ett block av kodsymboler som är upp- delat i en första serie av första kodord av en första kod med maximi- separabelt avstånd liksom i andra serie av andra kodord hos en andra kod med maximiseparabelt avstånd, varvid varje korrekt kodord hos en kod har ett minimiavstånd med avseende på godtyckligt annat korrekt kodord på åtminstone tre taget över symbolerna, och varvid alla icke redundanta kodsymbolerna utgör del av ett första ord liksom av ett andra kodord, 10 15 20 25 30 35 k ä n n e t e c k n a t av följande steg: a. b. uppsamlande av ett fullständigt block av kodsymboler; bestämning av alla syndromsymboler hos de första kodorden och de andra ' kodorden och bildande av en flagga för vart och ett av kodorden för vilket syndromet avviker från noll; _ summering av antalet flaggor för alla första kodord och separerat från detta summering av antalet flaggor för alla andra ord; . bestämning av ett felläge för ett korrigerbart fel för ett första kodord med ett syndrom som avviker från noll; . detektering om ett andra kodord existerar som innehåller det ifråga- varande felläget och om detta andra kodord är angivet som varande _inkorrekt och korrigering av det ifrågavarande felet om båda selek- tionerna ger ett positivt resultat, men uteslutande korrektion om bestämningarna ger motsatta resultat; och vid sådant uteslutande adressering av ett nästkommande första kodord i överensstämmelse med steg d; . uppdatering av syndromen hos det ifrågavarande första kodordet och det ifrågavarande andra kodordet efter en korrektion i överensstämmelse med steget e, uppdatering av de tillhörande två flaggorna och minsk- ning av summeringsresultaten av antalet flaggor endast om båda synd- romen är noll, och därefter adressering av ett nästföljande första 'kodord i överensstämmelse med steget d; . utbyte av funktionen hos första kodord och andra kodord efter adresseringen av åtminstone alla första kodord som angivits som varande inkorrekta och upprepande av stegen d, e och f tills två successiva utföranden av stegen d, e, f inte alstrar en ytterligare modifiering för alla rådande första kodord; _ tillförande av ett block av kodsymboler med signalering av dess korrekthet eller inkorrekthet. 10 15 20 25 30 35 466 578 16

2. Förfarande enligt patentkravet 1, k ä n n e t e c k n a t av att för ettförsta kodord hos en kod med maximiseparabelt avstånd med ett minimiavstånd på tre över kodsymbolerna det ifrågavarande syndromet all- tid nollställs efter utförande av en korrektion.

3. Förfarande enligt patentkravet 1 eller 2, k ä n n e t e c k n a t av att när ett första kodord adresseras under styrning av en flagga bil- dad för det ifrågavarande kodordet i överenstämmelse med steget d,detek- teras ett syndrom som avviker från noll, medan i det motsatta fallet den ifrågavarande flaggan och det ifrågavarande summeringsresultatet uppdate- ras.

4. Förfarande enligt patentkravet 1,2 eller 3, k ä n n e t e c k.n a t av att när ett summeringsresultat av flaggorna hos de första kodorden uppnås som som mest är lika med minimiavståndet för de rådande andra kod- orden minskat med ett, korrigeras dessa andra kodord därefter i en rader- mod under vilken godtycklig flagga hos det första kodordet verkar som en felpekare.

5. Förfarande enligt något av patentkraven 1-4 k ä n n e t e c k n a t av att efter avslutande av nämnda korrektionsoperation utförs en omräk- ning av en feldetekteringskod som finns i kodblocket under ett slutligt steg, för att bilda nämnda signalering av korrekt eller inkorrekt till- stånd.

6. Anordning för utförande av förfarandet enligt patentkravet 1 för att korrigera ett block av kodsymboler som är uppdelat i en första serie av första kodord av en första kod med maximiseparabelt avstånd liksom i en andra serie av andra kodord av en kod med maximiseparabelt avstånd, -varvid varje korrekt kodord hos en kod har ett minimiavstånd med avseende på godtyckligt annat kodord på åtminstone tre taget över symbolerna, och varvid alla icke redundanta symboler utgör del av ett första kodord, lik- som av ett andra kodord, vilken anordning innefattar mottagarorgan för mottagning och insamling av fullständigt block av kodsymboler, första aritmetriska organ som är matade av mottagarorganen för att bilda ett an- tal syndromsymboler per kodord ur de mottagna symbolerna, uppdaterings- organ som är matade av de första aritmetriska organen för att lagra en flagga per kodord för vilket syndromet avviker från noll, och för att se- parat uppdatera ett summeringsresultat för antalet flaggor för de första kodorden och för de andra kodorden, andra aritmetriska organ som är mata- de av de första aritmetriska organen för att för varje kodord, om möjligt och nödvändigt, bestämma en eller flera korrektionssymboler, korrektions- 0 10 15 20 25 30 35 466 578 17 organ vilka är matade av mottagarorganen och de andra aritmetriska orga- nen för att addera en korrektionssymbol till en inkorrekt symbol, och en utmatningsanordning för att presentera företrädesvis korrekt block för en användaranordning, k ä n n e t e c k n a d av att en serieordnare är anordnad som har ett antal lägen för att bestämma en korrektionssymbol och en lokaliseringssymbol i ett läge för godtyckligt första kodord, var- vid nämnda serieordnare innefattar adresseringsorgan för adressering av ett syndrom hos ett ifrågavarande andra kodord genom nämnda lokalise- ringssymbol och även innefattande en första detektor för under styrning av ett senare syndrom som avviker från noll korrigera kodsymbolen som adresserats av den senare lokaliseringssymbolen och för uppdatering av därmed förbunden godtycklig syndrom, och en andra detektor för styrning endast under styrningen av en syndrom hos det ifrågavarande andra kodor- det som då är lika med noll, av uppdateringsorganen för att uppdatera flaggorna för det ifrågavarande första och andra kodordet, att minska summeringsresultaten, och att därefter adressera ett följande första kod- ord, varvid serieordnaren även innefattar en utbytesanordning för att efter att ha passerat alla lägen som svarar mot åtminstone de inkorrekta första kodorden utbyta funktionen hos första och andra kodord och för att vidare aktivera ytterligare lägen hos nämnda lägen där en tredje detektor är anordnad för att vid aktivering av nämnda utbytningsanordning detekte- ra godtycklig modifiering som införts under de två senaste passagerna ut- med de då rådande första kodorden och för aktivering av nämnda utmat- ningsanordning i händelse av ett negativt detekteringsresultat.

7. Anordning enligt patentkravet 6, k ä n n e t e c k n a t ' av att en fjärde detektor är anordnad för detektering av en uppdaterad flagga och för aktivering uteslutande under styrning av ett positivt detekte- ringsresultat, av läget hos serieordnaren för det ifrågavarande första kodordet.

8. Anordning enligt patentkravet 6 eller 7, k ä n n e t e c k n a t av att en femte detektor är anordnad för ett summeringsresultat av flag- gor hos de första kodorden som, som mest är lika med minimiavstándet för de då rådande andra kodorden minskat med ett för att aktivera utbyt- ningsanordningen under styrning av ett positivt detekteringsresultat och för att därefter aktivera de andra aritmetriska organen för att korrigera de då rådande första kodorden under en raderingsmod i vilken godtycklig flagga hos ett då rådande andra kodord verkar som en felindikator.