SE519003C2 - Anordningar och förfarande relaterande till felkorrigerade transmission av digital data - Google Patents

Description

25 30 v v: o | n a v Q > . o n s | n | | n u 519 003 e Q - . u; 2 signal kan ta många olika vägar från en punkt till en annan genom det att den reflekteras mot exempelvis byggnader osv.

I vissa digitala mobilkommunikationsstandarder har kodning i. två steg introducerats för att ge ett acceptabelt skydd mot förlust av information. På den sändande sidan introduceras en feldetekterande CRC-kodare och som ett andra steg introduceras en felkorrigerande block-kodningsanordning. En signal antas bestå av ett antal sekvenser där varje sekvens är uppdelad i ett antal block, där vardera av sagda block i sin tur består av ett antal bitar.

Felkorrigeringsanordningen arbetar blockvis.

På den nwttagande sidan bildar en felkorrigerande avkodare som avkodar block i den totala sekvensen i ett första steg. I ett andra steg implementeras en feldetekterande CRC-avkodare för att fastställa om den felkorrigerande avkodaren har tagit några felaktiga beslut. Den feldetekterande avkodaren verkar på hela sekvensen, vilken, såsom hänvisats till ovan, består av ett antal block. När den feldetekterande CRC-avkodaren detekterar att den skall sändas om. Emellertid kan detta bli mycket tidskrävande eftersom det kan bli avkodade sekvensen är felaktig, begär den att sekvensen nödvändigt med flera försök. Dessutom krävs signalering mellan den sändande och den mottagande sidan för att administrera omsändningarna och detta kräver kapacitet som annars skulle kunna ha använts för nyttig transmission av information. så snabbt Vad som behövs är därför ett sätt att, som nbjligt, hitta den korrekta sekvensen och således undvika, eller åtminstone reducera, omsändning. Ett känt sätt för att hantera detta problem är att få den felkorrigerande blockavkodaren att tillhandahålla ett flertal alternativa förslag som testas av den feldetekterande avkodaren. Sannolikheten att ett av förslagen är korrekt kommer då att bli större. Det är emellertid svårt att välja ut kandidater.

Den felkorrigerande avkodaren är bara kapabel att testa ett 10 15 20 25, 30 » ø o o u u u; n a u n . | ø u u» ø n o n en 519 003 begränsat antal alternativa lösningar. Om vidare för många alternativ' skall testas, ökar risken att ett felaktigt förslag accepteras. Alternativ kan väljas om varje databit har ett attribut i form av så kallad mjuk information som är ett mått på sannolikheten att det valda tecknet (noll eller ett) är korrekt.

Kandidater väljes ut genom att invertera de bitar som har lägst mjuk information, dvs. de bitar vilket med störst sannolikhet är felaktiga, ifrågasätts först. Ett förfarande som använder mjuk information är Chase's andra algoritm. Det diskuteras i "A class of algorithms for decoding block codes with channel measurement» information", IEEE Trans. Inform. Theory, vol. IT-18, sidorna 170- 182, januari 1972, av D. Chase. I "Improved decoding of a concatenated code using soft decoding techniques", ett examensarbete på avdelningen för Informationsteori, Chalmers University of Technology, Göteborg, Sverige, av M. Fahami och P.

Flodin, december 1995, dessa dokument inkorporeras häri genom hänvisning därtill. har metoden ytterligare utvärderats. Båda Metoden med mjuk information består i att ett antal, exempelvis M, alternativ beräknas för varje block i sekvensen. Ett antal block, N, väljs ut bland det totala antalet block. blocken detta kan De N blocken bör vara block totala de sämsta såvitt avgöras, dvs. de relaterande till vilka osäkerheten är som störst. Den sekvensen produceras därvid och den består av permutationerna av alternativen. Totalt behöver alltså M" alternativa sekvenser testas. Det skall emellertid noteras att det finns ett antal block som aldrig har förändrats (den totala summan minus N).

Den feldetekterande CRC-avkodaren tillämpas på så sätt att den avkodade totalblockssekvensen multipliceras med paritetskontroll- matrisen UU av' CRC-polynomet. Detta kan realiseras såsom att sekvensen skiftas genom ett skiftregister, som exempelvis kan implementeras som hårdvara eller som mjukvara. har skiftats När hela sekvensen genom skiftregistret, läses innehållet i 10 15 20 25 30 o v; .o . n . n » n u u a n o u o o u o 519 003 o | n | - en n u 4 skiftregistret ut. Detta bildar syndromet för avkodnings- operationen. Om syndromet bara innehåller nollor, accepteras sekvensen, annars avslås den. CRC-kodningen kan definieras genom att den ursprungliga sekvensen skiftas genom ett skiftregister i vilket cellerna har en startposition som skiljer sig från noll. På detta sätt göres skiftningsoperationen icke-linjär.

Detta kan emellertid ses som, om man startar från ett begynnelse- tillstànd i vilket det är nollor i alla celler, att en blockbörjan skiftas in vilken genererar det definierade starttillståndet och ' därpå skiftas den sekvens in som skall kodas. På avkodningssidan motsvarar detta att blockbörjan skiftas in först följd av den sekvens som skall avkodas. Om det krävs en blockbörjan, ökas paritetskontrollmatrisen med så många rader som blockbörjan innefattar. Emellertid blir antalet operationer stort, och dessutom krävs det många skiftningar och sådana operationer är i allmänhet långa och krävande operationer vilket i sin tur reducerar prestanda eller kräver mycket effekt. En följd härav kan exempelvis bli att färre alternativ än vad som egentligen skulle behövas bli testade.

REDOGÖRELSE FÖR UPPFINNINGEN Vad som behövs är därför en mottagande anordning, för mottagning av en digitalt kodad datasignal som transporteras över en kanal, vilken inkluderar medel för felkorrigering och detektering, vilken bara kräver ett begränsat antal avancerade och krävande beräkningsoperationer för att finna en korrekt sänd sekvens, och vilken speciellt kräver färre operationer än vad hitintills kända anordningar gör. Speciellt behövs en anordning genom vilken det är möjligt att spara effekt och att sänka framställningskostnaderna. också En anordning behövs genom vilken en hög prestanda kan tillhandahållas och genom vilken en korrekt sänd signal effektivt v n o | | : | . - I | n - n. 10 15 20 25 30 519 003 u n u n nu u n kan hittas utan att det kräver ett stort antal krävande operationer, hög effekt osv.

Ett system för att överföra digitalt kodade datasignaler över kanaler från en sändande sida till en mottagande sida behövs också sänd genonn vilket ovan nämnda mål uppnås, dvs. där en korrekt sekvens lätt och snabbt kan hittas och vilket kräver så få omsändningar som möjligt.

En feldetekterande CRC-avkodare för fel- genom vilken ovan nämnda mål kan mottagen CRC-kodad digital datasignal som har avkodats i korrigeringsmedel behövs också, uppnås.

Dessutom behövs också ett förfarande för att detektera fel i en CRC-kodad digital datasignalsekvens genom vilket detektering kan utföras snabbt och på ett effektivt och tillförlitligt sätt och som kräver så få långa och komplicerade beräkningsoperationer som möjligt, och genom vilket prestanda kan hållas på en hög nivå.

Dessutom behövs ett förfarande genom vilket ovan nämnda mål uppnås och vilket dessutom är kostnadseffektivt.

Därför anges en Hwttagande anordning såsom hänvisats till ovan, vilken innefattar feldetekteringsmedel och lagringsmedel för att lagra information relaterande till de möjliga, olika, blockalternativen, där feldetekteringsmedlen innefattar en differentiell CRC-avkodare. Sagda differentiella avkodare inkluderar första avkodningsmedel för att avkoda en sekvens av block med referenssyndrom. Det andra avkodningsmedlet används för att avkoda användning av en referensfrekvens för att ge ett utvalda, alternativa, differentiella block av sekvensen, där sagda alternativ kan erhållas via felkorrigeringsmedlen. De differentiella blocken beräknas såsom skillnaden mellan v n n - v u u a u u u. ø ø n | | ø - u » n v ~ u n n o u u att detektera fel i en ' 10 15 20 25 30 519 003 motsvarande block i referenssekvensen respektive varje alternativt block, för att tillhandahålla differentiella syndrom. Därpå tas summan av referenssyndromet och respektive differentiellt syndrom för att ge resulterande syndrom. De respektive resulterande syndromen används för att fastställa om ett alternativ är korrekt mottaget eller ej.

Speciellt beräknas referenssyndromen genom multiplikation av referenssekvensen med en paritetskontrollmatris för CRC-polynomet och de differentiella blocken beräknas som skillnaden (modulo 2) av referenssekvensens block och respektive utvalda blockalternativ. I en speciell implementering genereras de differentiella syndromen genom multiplikation av de differentiella med motsvarande del av blocken CRC-polynomets paritetskontrollmatris.

I en speciell, fördelaktig, implementering innefattar de första avkodningsmedlen ett första skiftregister och referenssyndromet beräknas genom att skifta referenssekvensen en gång genom sagda första skiftregister. Speciellt innefattar de andra avkodningsmedlen ett andra skiftregister med parametrar som kan laddas positioner enligt de olika alternativen och de blocken differentiella med värden som tabuleras i lagringsmedlen för olika differentiella skiftas genom sagda andra skiftregister för att ge syndrom. Speciellt blir, för en sekvens som innefattar K block, av vilka N block väljs ut att ha M alternativ, antalet beräkningsoperationer K skiftningar för att ge referenssyndromet, Nx(M-l) skiftningar för att beräkna de differentiella syndromen och MN additioner (modulo 2) för att beräkna de resulterande syndromen. De första och andra avkodningsmedlen kan implementeras såsom hårdvara eller mjukvara enligt olika utföringsexempel. Speciellt används det andra skiftregistret på olika sätt för varje blockposition vilket är ett 10 15 20 25 30 519 un: ;jj=;jj,.;jj,_:;== resultat av ovan nämnda påståenden och vilket möjliggör framåtmatning såväl som bakåtmatning av data, där CRC-polynomezs koefficienter används för bakåtmatning och individuella vektcrer i CRC-polynomets H-matris används för framåtmatning. Speciellt lagras givna rader i H-matrisen i lagringsmedlen, tabell, och raderna ges av hur den ursprungliga indelad i block. exempelvis en sekvensen är Därför tillhandahållas också ett system såsom hänvisats till ovan vilket inkluderar ett antal sändande anordningar och ett antal mottagande anordningar, där de sändande anordningarna innefattar feldetekterande CRC-kodningsmedel och felkorrigerande blockkodningsmedel genom vilka en signal sändes till en mottagande anordning som inkluderar felkorrigerande medel som finner ett antal blockalternativ i en sekvens, där sagda alternativ tillhandahållas till feldetekterande CRC-avkodningsmedel. De feldetekterande CRC-avkodningsmedlen består av en differentiell CRC-avkodare som inkluderar första och andra avkodningsmedel.

Dessutom tillhandahàlles lagringsmedel. De första avkodningsmedlen används för att avkoda en sekvens av block med användning av en referenssekvens för att ge ett referenssyndronl medan de andra avkodningsmedlen används för att avkoda alternativa differentiella block av den ursprungliga sekvensen ingiven till de nwttagande medlen. Alternativen tillhandahålles av de feldetekterande medlen och information om de olika alternativen innehålles i lagringsmedlen. De differentiella blocken beräknas med användning av de andra avkodningsmedlen såsom skillnaden mellan motsvarande block i referenssekvensen och varje respektive alternativt block och de respektive differentiella syndromen fås genom multiplikation med de adekvata delarna av CRC-polynomets paritetskontrollmatris. (modulo 2) Resulterande syndrom beräknas som summan av referenssyndromet och de respektive differentiella syndromen. 10 15 20 25 30 u u ø - u: . ~ 1 | - - n u nu o ø ~ ø n a 0 u 519 003 - Q ~ | ~ | « | - . u.

Således beräknas referenssyndromet genom att multiplicera referenssekvensen med en paritetskontrollmatris för CRC-polynomet och de differentiella syndromen beräknas som skillnaden (modulo 2) av referenssekvensens block och de respektive utvalda blockalternativen multiplicerade med de relevanta raderna i paritetskontrollmatrisen. Speciellt innefattar de första avkodningsmedlen ett första skiftregister och referenssyndromen beräknas genom att skifta referenssekvensen en gång genom sagda första skiftregister. De andra avkodningsmedlen speciellt som ett andra skiftregister med laddningsbara parametrar vilka ges värden som är tabulerade i lagringsmedlen för olika positioner enligt de olika alternativen såsom tillhandahållna av Differentiella block skiftas felkorrigeringsmedlen. därpå genom det andra skiftregistret för att ge det differentiella syndromet.

Därför tillhandahålles också en feldetekteringsanordning vilken består av eni CRC-avkodare. Enligt uppfinningen är* CRC-avkodaren differentiell och innefattar första avkodningsmedel, andra avkodningsmedel och lagringsmedel såsom redan diskuterats ovan.

Dessutom anges ett förfarande för att detektera fel i en CRC-kodad Förfarandet inkluderar dela in block detektera block i sekvensen i en felkorrigerande avkodare digital signal. stegen att datasignalsekvensen i som vardera innefattar ett antal bitar; där den felkorrigerande avkodaren ger ett antal blockalternativ till feldetekteringsmedel. Förfarandet inkluderar dessutom stegen att; tillhandahålla information, till exempelvis parametervärden, som till alternativ i relaterar blockalternativen, lagringsmedel; lagra information om sagda sagda lagringsmedel; tillhandahålla alternativen till en differentiell feldetekterande avkodare; använda en referenssekvens i första avkodningsmedel i den differentiella avkodaren för att ge ett referenssyndrom; implementeras» 10 15 20 25 30 519 003 block blockalternativen och information som relaterar därtill innehàllen avkoda differentiella alternativa med användning av i lagringsmedlen genom att beräkna skillnaden mellan referensblocket och respektive differentiella block för att ge differentiella syndrom; addera ett antal (mellan l och N) differentiella syndrom (ej två från samma blockposition) till referenssyndromet för att erhålla ett respektive antal resulterande syndrom; och, om värdet på ett respektive resulterande syndrom är noll, accepteras ett blockalternativ.

Speciellt anges fördelaktiga utföringsexempel eller alternativ av- underkraven.

Det är en fördel med uppfinningen att antalet långa och komplicerade beräkningar väsentligt reduceras och i hög utsträckning ersätts av kortare och enklare beräknings- operationer. Det är speciellt en fördel med uppfinningen att en hög prestanda kan tillhandahållas och att det tillräckliga antalet alternativ lätt kan testas, och således ge en tillförlitlig anordning ett tillförlitligt förfarande. Det är speciellt en fördel med uppfinningen att genom förenklingen av beräkningsoperationerna kan effekt sparas och i ett speciellt utföringsexempel kan exempelvis antalet DSP:er (Digital Signal Processor) som behövs reduceras.

KORTFATTAD FIGURBESKRIVNING Uppfinningen kommer i det följande att ytterligare beskrivas på sätt och under ett icke-begränsande hänvisning till bifogade figurer i vilka: FIG 1A mycket schematiskt illustrerar hur felkorrigerande och detekterande medel verkar på en sekvens på den sändande sidan, lO 15 20 25 30 FIG FIG FIG FIG FIG FIG FIG FIG FIG FIG FIG IB 5A 5B 5C 5D 5E n . . . n . o .u | n n a nu un. 519 003 10 mycket schematiskt, såsom j_ Fig. 1A, illustrerar hur felkorrigerings- och detekteringsmedel verkar på en sekvens på den mottagande sidan, schematiskt illustrerar kan CRC-kodningsmedel som användas för kodningsproceduren, schematiskt illustrerar de första CRC-avkodningsmedlen för avkodningsproceduren av referenssekvensen enligt uppfinningen, illustrerar de andra CRC-avkodningsmedlen för avkodningen av en differentiell sekvens enligt uppfinningen, illustrerar ett exempel på en sekvens som innefattar fenl block därför tre av blocken olika alternativ är angivna, där visar ett första blockalternativ, visar ett andra alternativ, visar ett tredje alternativ, visar ett fjärde alternativ, visar ett femte alternativ, är ett flödesdiagram som, beskriver feldetektering på den mottagande sidan enligt uppfinningen, och 10 l5 20 25 30 o u e > u o av ø n ø n . . 4 n n. u n ø n v o I o 519 003 1 | | . | vn ll FIG 7 är ett flödesdiagram som beskriver testning av permutationer i en gren av flödet som beskrivits i Fig. 6.

DETALJERAD BESKRIVNING AV UPPFINNINGEN Figurerna lA och lB illustrerar mycket schematiskt principen för kodning respektive avkodning i två steg. På den sändande sidan, såsom schematiskt illustrerat i figur 1A, implementeras först feldetekterande kodningsmedel ITX vilka verkar på hela sekvensen.

I figur lA först den okodade till på sekvensen; slutet illustreras illustreras hur bitar läggs (här) för kodningsändamàl; de adderade bitarna är visade att följa efter den streckade linjen. (bitarna Bl-BK). felkorrigeringskodningsmedel Därpå utförs en separering j. K block andra Iïrxf Därefter, i ett steg, implementeras ett vilka applicerar felkorrigerande kodning blockvis; jämför den sista raden i figur 1A som visar adderade bitar i slutet av varje block.

Figur IB visar på ett motsvarande sätt principen på den mottagande sidan när en felkorrigerande avkodare Im först avkodar blocken i den totala sekvensen. I det andra steget appliceras den feldetekterande CRC-avkodaren IIw< för att undersöka om den felkorrigerande avkodaren har tagit ett felaktigt beslut. Såsom illustrerat i figuren verkar den feldetekterande avkodaren på hela sekvensen. Figur lB illustrerar blocksammansättningen separat.

Enligt uppfinningen tillhandahålles en differentiell CRC-avkodare (CRC-kodning som sådan kommer att förklaras kortfattat nedan) vilken verkar på en frekvens av exempelvis K block, av vilka N block har M olika alternativ, Enligt medan de andra blocken bara har ett hela multipliceras med paritetskontrollmatrisen H (exempelvis skiftad alternativ. uppfinningen behöver inte sekvensen det genom ett skiftregister) för MN alternativ. Istället skiftas därpà~ 10 15 20 25 30 » 1 ø o n nu o ~ o a a n n n n. u n n a o o 0 nu 519 003 a nu a | o - . - nu n n o 12 det första alternativet, referensalternativet, en gång genom skiftregistret (om skiftregister användes, vilket emellertid relaterar till en fördelaktig implementering) varpå ett referenssyndrom beräknas såsom: F- _.

HE Hu fßz Sa = [p bzo bzo - - - bra brx-uo bxo] -mm Hb (k-l; En ___l där matrisens dimensioner är följande: s (som är ett syndrom) har dimensionen 1 x m, där m är ordningen på CRC-polynomet, p (preamble; här dimensionen 1 x rn, bx till block x) avkodat block, blockbörjan) (refererande har dimensionen l >< n, där ri är längden på ett Hp har dimensionen m x m, där m är ordningen på CRC-polynomet såsom refererats till ovan, och Pßx har dimensionen n x m, där n är längden på ett avkodat block såsom också hänvisats till ovan.

Därutöver används de linjära egenskaperna hos koden på ett sådant sätt att differentiella block beräknas som skillnaden (modulo 2) och de syndrom tillhanda- av blocket som är inkluderat i referensalternativet respektive blockalternativen. Differentiella hålles motsvarande del av paritetskontrollmatrisen såsom: genom att de differentiella blocken multipliceras med 10 15 20 25 30 u v o u n o o . - n u | q n n u n o o n | o o n n n 519 003 13 få Hm fißz ASk = [ÛÛÛ...Abk...ÛÛ] :Abkffbk Éßk Hb (n-i) Hß ._ 'LJ I ett speciellt utförande implementeras detta genom skiftning av (det de differentiella blocken genom skiftregister andra skiftregistret som refererats till ovan, som har parametrar som kan ges värden enligt innehållet i lagringsmedel såsom kommer att diskuteras ytterligare nedan) för att beräkna differentiella syndrom. Det nya eller det resulterande syndromet beräknas som (modulo 2) av referenssyndromet och (differentiella) summan differentiellt respektive syndrom. Om skiftregister används, är det andra skiftregistret "olika" båda som koefficienter för olika blockpositioner och medger matning av data i riktningarna. CRC-polynomets koefficienter används för bakåtmatning medan koefficienterna för framåtmatning består av individuella vektorer i paritetskontrollmatrisen. Om en implementering som använder skiftregister tillämpas, bör det andra skiftregistret som tillhandahåller differentiella block bk ha h-koefficienter enligt den understa raden i Pßk. På detta sätt kommer skiftningen att bli ekvivalent med matrismultipliceringen.

I det kommer diskuteras kortfattat. följande konceptet CRC-kodning/avkodning att CRC-bitar används för att detektera om en mottagen enhet kan vara densamma som den enhet som sänts. Om inte, avvisas enheten och det begärs att sändningen skall repeteras. 10 15 2O 25 30 v c u ø n n nu . n o n n n n n n: n u n ; | o n ø q 519 003 u | « . u 14 blockkod (Detta är CRC-koden är en med ett generatorpolynom g(x)=l+x5+x”+x1ï bara ett exempel på ett generatorpolynom.) Ett sätt att realisera kodningen är genom att använda skiftregister, jämför kodningsmedlen lO i figur 2. Som ett starttillstànd innehåller registret bara ettor vilket, i likhet med generatorpolynomet, är specificerat i ITU-T's (tidigare CCITT) kodstandard. (Emellertid kan vilket starttillstànd som helst användas och uppfinningen är inte begränsad till standarden).

Vektorpresentationen g av g(x) är [lOOOl00O00OlOO0]. Därpå skiftas bitar genom och de registrerade bitarna skiftas ut. görs genom att skifta enheten som består av ett antal bitar genom ett på liknande sätt konstruerat register. Om en blockbörjan är implementerad, måste denna skiftas genom registret först. Detta kommer att diskuteras ytterligare nedan, se också figur 3. Om avkodningsregistret efter skiftningsoperationerna bara innehåller nollor, accepteras sekvensen och bitarna ges ut. När CRC-kodningen är utförd på den sändande sidan skiftas en sekvens u genom ett skiftregister såsom beskrivet i figur 2. Begynnelsetillståndet för cellerna c(cO,c1, ..., ck4,cm4,Cm4) är l i varje cell. g- faktorerna definieras av CRC-generator-polynomet g(x), dvs. g5 och gu är lika med l, medan alla andra är lika med O. Faktorn gg är l genonx definition. och. den är inte utskriven i figur 2. Således används g-faktorerna i multipliceringsmedlen Zh 22, ..., 2m¿.

CRC-koden är en systematisk blockkod vilket betyder att informationsbitarna förblir oförändrade, och kontrollbitarna läggs till i början eller i slutet. Så länge som informationsbitar skiftas in, matas de också till x-utgången. När alla informationsbitar har behandlats, slår en switch 3 över och cellinnehàllet skiftas ut. bli Den kodade sekvensen x kommer då att X = [vara Hem cm-1 Cm-z Co] Avkodningen lO 15 20 25 30 519 005 15 eftersom cmj skiftas ut först och co skiftas ut sist av registrets tillstàndsbitar.

Blockkoden med ett genererande polynom kommer att beskrivas av en generatormatris G. Generatormatrisen för en systematisk kod som kodar k bitar till n och lägger till kontrollbitarna på slutet antar uttrycket: Gm, n) = fïuf, k; I Ruf, n-ml Där indexen är storlekarna på matriserna och I är identitetsmatrisen. I en implementering som använder skiftregister, och om skiftningsprocessen skall vara ekvivalent med en matrismultiplikation, måste starttillstånden i varje registercell vara noll. Annars är skiftningsprocessen inte linjär vilket matrismultiplikationen är. I CRC-kodningsmedlen i figur 2 är gi CRC-generatorpolynomets koefficienter för xi, u den okodade sekvensen och x den kodade sekvensen. x innefattar den ursprungliga sekvensen u följd av innehållet i cellerna när dessa skiftas ut av switchen 3 vid t = som motsvarar tiden när tslut/ hela sekvensen u har skiftats in.

CRC-avkodning kommer nu att diskuteras kortfattat. När en mottagen sekvens y avkodas, multipliceras den med paritetskontrollmatrisen H. H definieras som: H(n-1=,n) = [Rraz-Jgk) | Im-Jgn-Jq] där R är samma delmatris som i generatorpolynomet G. Sekvensen y kan ses som modulo-2 summan av den sända sekvensen x och en 10 15 20 25 30 o no o o s n n ø v I' u | u a u a ~ n | a a ; n a ø n c I 519 003 16 felvektor vars element är 1 när ett fel inträffat och O annars.

Syndromet s definieras som: s = [p y]HT= ([p x] ® e)HT= [p x]HT® eHT där e i felvektorn motsvarande [p x]. Bitarna i e svarande mot p (som är blockbörjan) är alla noll.

Produkten [p x]HT kan skrivas som: [p XJH” = fp UJGH” = Raon-k) R (Jen-Jul - [p U] [Ioma | Im-Jgn-k; [p U1(R(k,n-k) æ Runa-JU) = Û och därför är s = eHæ.

Således är syndromet 0 om alla element i e är O. Om s skiljer sig från 0, finns det åtminstone ett fel i den detekterande sekvensen Y.

Beräkningen av s kan utföras i ett skiftregister liknande det som används i kodningsproceduren.

Figur 3 visar ett första avkodningsmedel 20A som används for avkodning av referenssekvensen. 10 15 20 25 30 u r nu o u n u: oo en HH I II I I I I! I I Il I I I I I I I I Q I I Cl l I I I I O III I!! ID i ll IVO I I l I I O I I ll I l C I I I O I V Ü 0 0 Q a u av en -:cc cec: nu 17 Faktorerna g är desamma som i kodningsmedlen, dvs. de representerar CRC-generatorpolynomet. Syndromet är detsamma som tillståndet på cellerna s efter inskiftning av alla bitarna i [p y]. Starttillståndsbitarna bör alla vara nollor. Detta är ekvivalent med att använda p bitarna i omvänd ordning som ett starttillstånd och därpå skifta in de mottagna y bitarna.

Kopplingen mellan en matrismultiplikation och en skiftnings- procedur är att raderna i matrisen HT Inotsvarar tillstånden i registret när en enda l och sen bara Ozor skiftas in i ett tomt register. Denna tillståndssekvens kan ses som registrets impulssvar.

Den sista raden i HT är samma som det första tillståndet i impulssvaret, dvs. när lzan skiftas in. Detta är så eftersom när den sista biten i en sekvens skiftas in, kommer den att bidra till det tillståndet om den är en 1:a jämfört med om det är O bit.

Sluttillståndet i registret blir detsamma som modulo-2 summan av tillstånden som genererats av bitarna som skiftas in.

Skiftningsoperationen är således linjär. Det är också matrismultiplikationen, produkten är detsamma som modulo-2 summan av raderna i HTi positioner som svarar mot ettor i in-vektorn.

Den linjära egenskapen kan användas när många liknande sekvenser y analyseras. Om två sekvenser yl och yz med en längd på t.ex. 130 (vilket bara utgör ett exempel) och som bara skiljer sig åt i några positioner mellan po och (p0+Ap-l) skall utvärderas för att se om någon av dem genererar ett noll syndrom, kan utvärderingen av den andra sekvensen göras snabbt genom att bygga en differentiella ny skiftregisterstruktur. Den sekvensen beräknas såsom: aquvuo 10 15 20 25 30 519 003 n ø u ø n n . '- ......Z°' 18 Ayk-1 = Yi (B Yz och Syz = fp yblfiw = [P yälfifl G9 [Û Aykulff = = 5y1 æ (AW) Hrrows p0 to (p0 +Ap-1) = 5y1 æ A5/ där Aw är sekvensen i Aybí mellan po och Qm+Ap-1). Den första termen, i figur 3. För att beräkna den andra termen, skall en natris- multiplikation göras. Denna operation behöver bara raderna po till Qm+Ap-1) i HT. Eftersom bara Ap bitar ska skiftas in i registret är det onödigt att använda en struktur som kräver att t.ex. 130-po skiftningar skall utföras för att generera det tillstånd som svarar mot rad po. Det skulle vara lämpligt att använda ett register som har impulssvarstillstånd svarande mot raderna po till (pO-Ap-i) i HT.

Detta kan uppnås genom att använda de andra avkodningsmedlen 2OB i figur 4. Faktorerna h (ho-mwl) i multipliceringsmedlen 60,...,6m¿ svarar mot rad Qm+Ap-1) i HT. Efter inskiftning av Aw bitarna, läses As bitarna från registertillståndet. Därpå kan y2:s syndrom beräknas såsom: Syg = Syl æ AS Om Aszn svarande mot N Awzn beräknas, kan 2N (förutsatt att det bara finns två olika alternativ för de olika positionerna) olika yzn räknas ut, dvs. deras syndrom beräknas. I en generaliserad form skulle detta bli MN, där M är antalet alternativ. sfl, har redan beräknats med användning av skiftregistret_ 10 15 20 25 30 519 003 . n . n . ~ Q '- , _ . o . . | . , ' ° ' nu I v n 19 De första avkodningsmedlen 20A (som illustrerat i. figur 3) är, sålunda, en skiftregistersavkodare för en hel sekvens. Såsom hänvisats till ovan är gi (i multipliceringsmedlen 2'i,...,2'm4) 1 om koefficienten för' xi i CRC-polynomet är l; O annars. I det illustrerade exemplet är CRC-polynomet av grad m. y är den sekvens som matas in och si innehåller, efter att skiftningen har fullbordats, syndromet för referenssekvensen. Såsom hänvisats till ovan är starttillstånden för alla si noll. Om starttillstånden ci för cellerna l0,...,lm4 i kodningsmedlen skiljer sig från noll (på grund av definitionen i kodningsstandarden), måste y föregås av en' blockbörjan. Längden på blockbörjan är densamma som ordningen m på CRC~polynomet. Blockbörjaren definieras på ett sådant sätt att om den skiftas in i kodningsregistret, vilket inledningsvis är satt till noll, skall det definierade starttillståndet genereras.

Figur 4 illustrerar således de andra avkodningsmedlen 2OB (som är differentiella) implementerade som ett skiftregister för ett separat block. gisvarar mot gi i figur 3, medan hi anges av en rad i CRC-polynomets paritetskontrollmatris H, beroende på block, såsom förklarats ovan. Ay är det ingivna differentiella blocket och Asi innehåller, efter att skiftningen har blivit fullbordat, motsvarande differentiella syndrom. Startpositionen skall också här bara innehålla nollor. Faktorerna hi lagras i lagringsmedlen för varje möjlig blockposition.

Med hänvisning till figurerna 5, 5A-5E kommer en utföringsform att exemplifieras i vilken en sekvens består av fem block Bl-B5. Det antas dessutom att alternativ kommer att tillhandahållas för tre block. referenssekvens Y med. fenl block svarande mot blockpositionerna av fem av dessa Figur 5 visar ett exempel på en Bl,B2,B3,B4,B5. Referenssekvensen antas ha ett första alternativ (index 1) i blocken l, 3 och 4. Referenssekvensen Y multipliceras 10 l5 20 25 30 . , _ . . - . I - . . . n. ø . . , ,, 519 003 20 med paritetskontrollmatrisen H för att ge en kontrollsumma, här kallad S. Såsom hänvisats till ovan, kan denna operation åstadkommas genom att skifta referenssekvensen en gång genom de första avkodningsmedlen, dvs. det första skiftregistret 10, en gång, för att tillhandahålla ett referenssyndrom S.

Figur 5A visar en alternativ sekvens i vilken ett andra alternativ testas i blockposition Bl, medan i blockposition B3 och B4 första alternativ svarande mot alternativen i referensalternativet bibehålles. multipliceras med paritetskontrollsmatrisen H.

Således behöver den alternativa sekvensen YA Emellertid utförs detta enligt uppfinningen genom skapandet av ett differentiellt block AYA i vilket skillnaden mellan alternativt i. block J. och referens-alternativet j. motsvarande block tas, dvs. illustrerat genom B12-B11 i blockposition 1. I de andra blockpositionerna finns nollor. Det differentiella syndromet ASA skapas därpå genom att nmltiplicera det differentiella blocket AYA med nmtsvarande del av paritetskontrollmatrisen H, såsom diskuterats ovan. Således ges det nya (resulterande) syndromet för alternativet YA såsom summan (modulo 2) av referenssyndromet S och det differentiella syndromet ASA.

I figur 5B testas ett annat alternativ i block B3, medan blocken Bl och B4 är oförändrade. Detta indikeras genom referensen YA för vilken index 2 är visad i block B3 illustrerande ett andra alternativ för sagda block. Pà ett sätt som liknar det som diskuterats under hänvisning till figur 5A bildas den differentiella sekvensen eller ett differentiellt block genom att man tar skillnaden mellan YB:s alternativ och referensalternativet, dvs. B32-B31 i blockposition 3. II de andra blockpositionerna fås nollor. Detta ger ett differentiellt syndrom ASB och det nya (resulterande) syndromet består av summan (modulo också' 10 15 20 25 30 I nu n - u « . » n u n u o - | u ø n n 519 003 o o | . n | - n - . « Q u. 21 2) av referenssyndromet och det differentiella syndromet ASS såsom i figur 5A.

I figur 5C illustreras ett alternativ i vilket både block Bl och B3 de andra alternativen som illustrerats ovan testas på samma gång, medan det inte är någon förändring i blockposition B4 såsom jämfört med referensalternativet. Detta alternativ kallas YC och i likhet med föregående utföringsexempel behöver det multipliceras med paritetskontrollmatrisen H (en del därav). Emellertid har i detta fall både det alternativ, används i blockposition Bl (motsvarande figur 5A), och det i vilket det andra alternativet används i den tredje (B32) 5B), erhålles det alternativ, blockpositionen (motsvarande figur redan beräknats.

Därför resulterande syndromet som summan av referensalternativen och de differentiella alternativen ASA och ASB.

I figur 5D kommer ett andra alternativ i blockposition. 4 att testas svarande mot alternativ YD. På nytt kommer det differentiella blocket B42-B41 i position B4 svarande mot AYD att multipliceras med motsvarande del av H-matrisen och det nya syndromet kommer att bli S+AS@ Figur 5E relaterar till en annan situation, i vilken bara ett alternativ visas, svarande mot det fall när det finns tre alternativ för blockposition Bl och det tredje alternativet (illustrerat genom index 3 i blockposition Bl) indikeras. Liksom tidigare bibehâlles de första alternativen i blockpositionerna B3 och B4. Också här skiftas den differentiella sekvensen (eller det differentiella blocket B13-Blfl delen av genom den relevanta paritetskontrollmatrisen H vilket ger differentiellt syndrom ASM och det nya syndromet kommer att bli S+ASm. i vilket ett andra alternativ' 10 15 20 25 30 519 003 o > Q a n n . ' n . '. u n n | o u n c | n v n n» 22 De operationer som ger de differentiella syndromen är, såsom hänvisats till ovan, snabba operationer och de relevanta delarna av paritetskontrollmatrisen, h-koefficienterna, lagras i lagringsmedlen, exempelvis en tabell, och referenssyndromet (beräknat en gång) används vid testning av varje alternativ.

Således räcker det att den långa operationen görs en gång, medan de korta operationerna görs tre gånger under förutsättning att M = 2. Detta betyder att åtta olika alternativ kan testas med användning av additioner (eller XOR-operationer) långa operationer (svarande mot den operation som här görs en gång Eftersom h-koefficienterna är differentiella för att ge referenssyndromet). lagrade i lagringsmedlen, kan de operationerna utföras direkt. Om för tre positioner tre alternativ skall prövas, kan 27 (33) alternativ testas och ändå behövs det bara en lång operation. Dessutom behövs sex korta skiftoperationer och 26 XOR- operationer för att beräkna de olika kombinationerna.

Figur 6 är ett flödesdiagram som beskriver en implementering av det uppfinningsmässiga konceptet. Till en felkorrigerande och detekterande anordning inges detekterad data Dm, vilken innehåller sekvenser som vardera består av K block, 101. För varje block anges M avkodade alternativ och N block väljs därpå ut för vardera av vilket de M-1 alternativen skall tests vilket svarar mot den felkorrigerande avkodningen, 102. För de avkodade blocken finns det således N positioner som vardera innehåller M alternativ och K-N positioner med bara ett alternativ. (P0, P1, ..., PNq för de N blocken flest antal betecknar positionerna som har alternativ).

En referenssekvens sammansätts därpå av alla K första alternativ, 103. Därpå tillämpas CRC-avkodningen, enligt någon standardmetod, på referenssekvensen vilket ger som ett resultat ett istället för nio 10 15 20 25 30 o n . o ø » » o Q ' '. n | n n ø u o 519 005 23 104, (Referenssekvensen kan inkludera en blockbörjan om en referenssyndrom S, jämför beskrivningen som refererar till figur 3. sådan detta är emellertid inte implementering är tillämplig; nödvändigt).

Därpå undersöks om referenssyndromen svarar mot 0-vektorn. 105A, Om emellertid referenssyndromet inte är lika med till noll, 106. j 107, skiftregister bildas input av lämplig rad i Om ja, är referenssekvensen OK, och inga ytterligare alternativ behöver testas. noll, och ett sätts i är lika med 1, genom svarande mot position Pi, där h-koefficienterna tillhandahàlles i lagringsmedlen, 108. (Denna procedur utvecklades mera noggrant under hänvisning till figur 4). Det differentiella blocket erhålles ur sambandet AbLj=bL0-bLj, 109. Därpå beräknas det differentiella syndromet AsLj med användning av en kundanpassad, skapad skiftregisteravkodare pi: AbLj, 110. Därpå. ökas j med 1, 111, differentiella block och det undersöks onl j 2 DL 112. Om ej, beräknas nästa (j ökas med 1) och proceduren repeteras från steg 109. Om emellertid j Z M, ökas i med 1, 113, och det undersöks om i 2 N, 114. Om ja, är alla As tillgängliga och permutationer skall testas, 214, vilket diskuteras ytterligare i figur 7. Annars repeteras förfarandet från steg 108.

I figur 7 testas permutationerna, 214 Antalet Till att börja med är k lika med 1, (jämför figur 6). permutationer sätts till MN-1. 215, och permutation nummer k skapas såsom, 216: C§(k) = (k div(i°RU) mod M7 i = O,l,...,N-l.

Därpå beräknas motsvarande kontrollsumma Sk enligt HT-matrisen' 10 15 519 003 . v n u n o . n , ' '. | a ø | ø ø ' ' ' ' ' ° ' u s u n e .n 24 N-1 Sk = 5 + 2 ASLCQJ; i=Û med villkoret är att ASLO = 0 för varje i, 217. Därpå undersöks om Sk = 0, 218. Om ja, är Sk riktig och en lösning har hittats, 218A, och det behövs inte någon ytterligare testning.

Om Sk inte är lika med 0, ökas k med 1, 219, och det undersöks om k överskrider antalet permutationer MN-l. Om ej, permutation k+1, jämför 216 ovan, och proceduren upprepas. Om emellertid k överskrider antalet permutationer, har alla permutationer undersökts och det fastställs att hittats, 221. ingen lösning Det skall vara klart att uppfinningen inte är begränsad till de illustrerade utföringsexemplen utan att den kan varieras på ett antal sätt inom ramen för vidhängande patentkrav. bildas

Claims (24)

10 15 20 25 30 o n n n | n . Q , ' ', a o o n _ un 519 003 ø - n u ; u. o u 25 PATENTKRAV

1. l. Mottagande anordning för mottagning av en över en kanal transporterad digitalt kodad datasignal vilken datasignal innefattar ett antal sekvenser, där varje sekvens är indelad i ett antal block, där varje block i sin tur består av ett antal bitar, där sagda mottagande anordning innefattar felkorrigerande nædel som tillhandahåller ett antal alternativa block, k ä n n e t e c k n a d d ä r a v att den dessutom innefattar feldetekterande medel och lagringsmedel för lagring av information relaterande till varje möjlig blockposition i en sekvens, där sagda feldetekterande medel differentiell CRC-avkodare (2OA) användning av en referenssekvens för att ge ett referenssyndrom, (2OB) för innefattar en inkluderande första avkodningsmedel för* avkodning av' en sekvens av' block med och andra avkodningsmedel avkodning av utvalda alternativa differentiella block av den sekvensen som kan fås via de felkorrigerande medlen, där sagda differentiella block beräknas såsom skillnaden mellan motsvarande block i referenssekvensen och varje respektive alternativt block för att ge differentiella syndrom, där resulterande syndrom beräknas som summan av referenssyndromet och ett antal differentiella syndrom.

2. En anordning enligt patentkrav l, k ä n n e t e c k n a d d ä r a v att referenssyndromet beräknas genom multiplikation av referens- sekvensen med en paritetskontrollmatris (H) för CRC-polynomet och att de differentiella blocken beräknas som differensen (modulo 2) referenssekvensen och utvalt av blocken i respektive blockalternativ.

3. En anordning enligt patentkrav 2, 10 15 20 25 30 519 003 u - u ~ . n. 26 k ä n n e t e c k n a d d ä r a v att de differentiella syndromen genereras genom multiplikation av de differentiella blocken med nwtsvarande del av CRC-avkodarens paritetskontrollmatris.

4. En anordning enligt något av föregående patentkrav, k ä n n e t e c k n a d d ä r a v att de första avkodningsmedlen innefattar ett första skiftregister (20A) och att beräknas skifta referenssyndromet genom att referensen en gång genom det första skiftregistret (ZOA).

5. En anordning enligt patentkrav 4, k ä n n e t e c k n a d d ä r a v att de andra avkodningsmedlen innefattar ett andra skiftregister (ZOB) med laddningsbara parametrar soul är tabulerade för olika positioner enligt de olika positionerna/alternativen och att differentiella block skiftas genom sagda andra skiftregister (ZOB) för att ge de differentiella syndromen.

6. En anordning enligt något av patentkraven 4 eller 5, k ä n n e t e c k n a d d ä r a v att för en sekvens som innefattar K block, av vilka N block är valda att ha M alternativ med blir vardera, användning av de felkorrigerande medlen, antalet beräkningsoperationer K skiftningsoperationer för att beräkna referenssyndromet, N x (M-1) skiftoperationer för att beräkna de differentiella syndromen och beräkna de resulterande MN additioner (modulo 2) för att syndromen.

7. En anordning enligt något av föregående patentkrav, k ä n n e t e c k n a d d ä r a V att de första och de andra avkodningsmedlen, exempelvis skiftregister (20A, 20B), är implementerade som hårdvara. 10 15 20 25 30 519 003 :n::r:-W 27

8. En anordning enligt av patentkraven 1-6, k ä n n e t e c k n a d d ä r a v att de första och andra avkodningsmedlen, exempelvis skiftregister, är implementerade som mjukvara.

9. En anordning enligt något av patentkraven 4-7, k ä n n e t e c k n a d d ä r a v att det andra skiftregistret (2OB) används på olika sätt för varje och att det data, där blockposition medger framåtmatning såväl bakåtmatning av koefficienterna för CRC-polynomet används för bakåtmatning och individuella vektorer i CRC- polynomets H-matris används för framåtmatning.

10. En anordning enligt något av föregående patentkrav, k ä n n e t e c k n a d d ä r a v att i lagringsmedlen lagras givna rader från H-matrisen, där raderna ges av hur sekvensen är indelad i block. (den ursprungliga)

11. ll. En anordning enligt något av föregående patentkrav, k ä n n e t e c k n a d d ä r a v att lagringsmedlen innefattar en tabell i vilken H-matrisens h- koefficienter för olika blockalternativ lagras. över kanaler

12. Ett överföra digitalt system för att kodade sekvenser sonx är indelade i. block, transporterade datasignaler, vilka datasignaler innefattar där vardera av sagda block består av ett antal databitar, varvid systemet innefattar ett antal sändande anordningar och ett antal mottagande anordningar, sändande innefattar varvid vardera av feldetekterande sagda anordningar CRC-kodningsmedel och felkorrigerande blockkodningsmedel genom vilka en signal sändes till en mottagande SOITI ' 10 15 20 25 30 ~ o . a a ø a n " I o | o | , , " 519 003 28 anordning inkluderande felkorrigerande medel som finner ett antal blockalternativ i en sekvens som tillhandahàlles till feldetekterande CRC-avkodningsmedel, k ä n n e t e c k n a t d ä r a v att sagda feldetekterande medel innefattar en differentiell CRC- avkodare och att anordnade för att lagringsmedel är lagra information relaterande till varje möjlig blockposition i ett block, och att sagda differentiella CRC-avkodare inkluderar första (ZOA) avkodningsmedel för avkodning av efii sekvens av block lned användning av en referenssekvens för att ge ett referenssyndrom ' och andra avkodningsmedel (2OB) för att avkoda utvalda alternativa differentiella block i sekvensen som kan erhållas via de felkorrigerande medlen med användning av information i lagringsmedlen, där sagda differentiella block beräknas som skillnaden mellan motsvarande block i referenssekvensen respektive varje alternativt block för att ge differentiella syndrom, och att för varje alternativ beräknas resulterande syndrom som summan av referenssyndromet och ett antal differentiella syndrom, och om värdet på ett resulterande syndrom är noll, är det mottagna sekvensalternativet korrekt, annars är det felaktigt.

13. Ett system enligt patentkrav 12, k ä n n e t e c k n a t d ä r a v att referenssyndromet beräknas genom multiplikation av referenssekvensen med en paritetskontrollmatris för CRC-polynomet och att de differentiella blockalternativen beräknas som skillnaden (modulo 2) av blocket i referenssekvensen och respektive utvalda blockalternativ, och att de differentiella syndromen genereras genom att multiplicera de differentiella blockalternativen med motsvarande del av CRC-avkodarens paritetskontrollmatris.

14. Ett system enligt patentkrav 12 eller 13, lO 15 20 25 30 519 003 29 k ä n n e t e c k n a t d ä r a v att de första avkodningsmedlen innefattar ett första skiftregister (2OA), och att referenssyndromen beräknas genom att skifta referenssekvensen en gång genom det första skiftregistret, och att de andra avkodningsmedlen innefattar ett andra skiftregister (2OB) med laddningsbara parametrar vilka är tabulerade för olika positioner enligt information som innehàlles i lagringsmedlen, och att de differentiella blocken skiftas andra genom sagda skiftregister för att ge de respektive differentiella syndromen.

15. Ett system enligt något av patentkraven 12-14, k ä n n e t e c k n a t d ä r a v att för en ingiven sekvens som innefattar K block, av vilka N block. är valda att ha M alternativ, som tillhandahàlles av de felkorrigerande medlen, l)xN blir antalet beräkningsoperationer K+(M- och de för att skiftningar för att ge referenssyndromet differentiella syndromen och MN additioner (modulo 2) beräkna de resulterande syndromen.

16. En feldetekterande CRC-avkodare för att detektera fel j. en mottagen CRC-kodad digital datasekvens, vilken sekvens är indelade i ett antal block soul vardera består av ett antal bitar, och vilken signal är avkodad i felkorrigeringsmedel som ger ett antal blockalternativ, k ä n n e t e c k n a d d ä r a v att den feldetekterande CRC-avkodaren är differentiell, och att lagringsmedel är anordnade för att lagra information relaterande till varje möjlig blockposition i en sekvens, och att den differentiella CRC-avkodaren inkluderar första avkodningsmedel för block referenssekvens för att ge ett att avkoda en sekvens av med användning av en referenssyndrom och andra avkodningsmedel för att avkoda utvalda alternativa differentiella block i sekvensen som kan erhållas från de felkorrigerande medlen, l0 15 20 25 30 519 30 där' de differentiella blocken beräknas såsom skillnaden mellan motsvarande block i referenssekvensen respektive varje alternativt block för att ge differentiella syndrom, och att ett resulterande syndrom beräknas för varje alternativ såsom summan det (modulo 2) av referenssyndromet respektive eller de differentiell(a) syndrom(en).

17. En feldetekterande CRC-avkodare enligt patentkrav 16, k ä n n e t e c k n a d d ä r a v att referenssyndromet beräknas genom multiplikation av referenssekvensen med en paritetskontrollmatris for CRC-polynomet, och att de differentiella blocken beräknas som skillnaden (modulo blocket i och att de differentiella 2) av referenssekvensen och respektive utvalda blockalternativ, syndromen genereras genom multiplikation av de differentiella blocken med motsvarande del av CRC-avkodarens paritetskontrollmatris.

18. En feldetekterande CRC-avkodare enligt patentkrav 16 eller 17, k ä n n e t e c k n a d d ä r a v att de första avkodningsmedlen innefattar ett forsta skiftregister (2OA), där referenssyndromen beräknas genom att skifta referenssekvensen en gång genom sagda första skiftregister, och att de andra avkodningsmedlen innefattar ett andra skiftregister (20B) mellan som är tabulerade i laddningsbara parametrar lagringsmedel för olika positioner, och att de differentiella blocken skiftas genom sagda andra skiftregister (2OB) för att ge de respektive differentiella syndromen.

19. En feldetekterande CRC-avkodare enligt något av patentkraven 16-18, k a n n e t e c k n a d d ä r a v att for en sekvens som innefattar K block, av vilka N block är valda att ha M alternativ enligt de felkorrigerande medlen, blir e u q I un.'u'l o. f”. .". " " " 'I I u n. g , , ' I. . z -ø I n n o IH u n. , , '. ' I n a r n: u g; , _' ' ° - - -- H ann 10 15 20 25 30 uu . a . o n n . n .o n n . n ur 519 003 | | o c nu 31 antalet beräkningsoperationer K+(M-l)xN skiftningar för att ge referenssyndromet och de differentiella (modulo 2) syndromen och MN additioner för att beräkna de resulterande syndromen.

20. Ett förfarande för att detektera fel i en CRC-kodad digital signalsekvens, som inkluderar stegen att: - dela upp den digitala sekvensen i block som vardera består av ett antal bitar, - avkoda block i sekvensen i en felkorrigerande avkodare som för ett antal blockpositioner ger ut ett antal blockalternativ, k ä n n e t e c k n a t d ä r a v att det dessutom innefattar stegen att: - tillhandahålla information om blockalternativen till lagringsmedel, - lagra informationen i sagda lagringsmedel, - tillhandahålla blockalternativen till en differentiell avkodare, - i första avkodningsmedel i den differentiella avkodaren använda en referensfrekvens för att ge ett referenssyndrom, - avkoda differentiella alternativa block med användning av information relaterande till de respektive blocken i lagringsmedlen för att beräkna skillnaden mellan de motsvarande blocken i referensfrekvensen och respektive blockalternativ" för att ge ett differentiellt syndrom för varje blockalternativ, - beräkna resulterande syndrom för varje blockalternativ som de summorna av differentiellt (differentiella) respektive referenssyndromet och respektive syndrom, - acceptera ett alternativ om värdet på respektive syndrom är noll.

21. Ett förfarande enligt patentkrav 20, k ä n n e t e c k n a t d ä r a v 10 15 20 25 30 att

22. k ä att

23. k á att

24. k ä att 519 D03 u a » » | n» . a . ø . u . o no a n | o o 0 I ' ; . - - . ø ' ' " . . . . = - | . | | .- 32 det inkluderar stegen att: multiplicera referenssekvensen næd eni paritetskontrollmatris för CRC-polynomet således tillhandahållande ett referens- syndrom, beräkna skillnaden (modulo 2) mellan blocket i referenssekvensen motsvarande ett utvalt blockalternativ och sagda respektive utvalda blockalternativ för att ge ett differentiellt syndrom, repetera beräkningen av differentiella syndrom för ett antal alternativ. Ett förfarande enligt patentkrav 21, n n e t e c k n a t d ä r a v det innefattar stegen att: generera differentiella syndrom genom att multiplicera de differentiella blocken med respektive motsvarande del i CRC- avkodarens paritetskontrollmatris. Ett förfarande enligt något av patentkraven 20-22, n n e t e c k n a t d ä r a v det inkluderar stegen att: beräkna referenssyndromet genom att skifta referenssekvensen en gång genom ett första skiftregister, beräkna ett antal differentiella syndrom genom att skifta ett antal differentiella block genom ett andra skiftregister som innehåller laddningsbara parametrar som är tabulerade i lagringsmedel för olika positioner enligt olika blockalternativ. Ett förfarande enligt något av patentkraven 20-23, n n e t e c k n a t d ä r a v det innefattar stegen att, för en sekvens innefattande K block, av vilka N block är valda att ha M alternativ, 519 005 33 utföra K+(M-l)xN skiftningar för att ge ett referenssyndrom och differentiella syndrom, utföra MN additioner (modulo 2) för att beräkna resulterande syndrom.