SE506241C2 - Förfarande och anordning för bitmönsterdetektering - Google Patents

Description

15 20 25 30 35 506 241 2 formationsmängd överförs åt gången via ett antal parallella dataledningar, vanligen multiplar av åtta bitar. Om- vandling mellan de två överföringssätten kan ske med serie till parallell-omvandlare och parallell till serie-omvand- lare.

Bitmönsterdetektering kan ske på ett förutbestämt antal på varandra följande bitar eller på utspridda bitar' i en seriellt tillgänglig bitström. Ur bitströmmen bildas ett kandidatbitmönster med det förutbestämda antal bitar som de bitmönster har som man önskar att detektera. Vanligen önskas att bitmönsterdetekteringen sker över hela eller de- lar av bitströmmen varvid nya kandidatbitmönster med det Kandidatbit- mönster bildas genom extraktion ut ur bitströmmen. Nya förutbestämda antalet bitar måste bildas. kandidatbitmönster bildas lämpligen med samma takt som bittakten i bitströmmen genom att för varje följande extraktion av ett nytt kandidatbitmönster förskjuts bit- strömmen med en bitposition. Detta kan man även beteckna som att bitmönsterdetekteringen förflyttas en bitposition i bitströmmen. Önskemålet att känna igen vissa bitmönster kombineras oftast med ett önskemål om att igenkänningen skall gå så fort som möjligt och dessutom med så få operationer som möjligt.

En tidigare känd lösning går ut på att använda en XOR-kon- struktion. XOR-konstruktionen jämför varje kandidatbit- mönster av en mottagen bitström med vart och ett av de bit- mönster man önskar känna igen. Ett bitmönster anses vara detekterat när resultatet av en XOR-operation är lika med noll. Lösningar med XOR-konstruktioner blir ytterst kapacitetskrävande eftersom alla XOR-Operationer och jämförelser med noll måste rymmas i ett tidsintervall som motsvarar bitströmmens bittakt. Dessutom måste alla XOR- 10 15 20 25 30 35 506 241 3 operationer och jämförelser med noll repeteras för varje kandidatbitmönster som bildas från bitströmmen. Med tanke på det ovan nämnda kravet på snabbhet ställer detta extremt stora krav på maskinvaran.

En lösning som kräver många operationer och där varje operation kräver många deloperationer lider av att den klockfrekvens son\maskinvaran.måste klockas med nödvändigt- vis blir mycket hög. Om inte maskinvarans bearbetnings- takt, som står i relation till dess klockfrekvens, är till- räckligt hög, finns det inte tid att utföra alla nödvändiga operationer och deloperationer i ett tillgängligt tidsin- tervall. Det finns en teoretisk och praktisk övre gräns för hur hög en anordnings klockfrekvens kan vara, vilket ger en övre gräns på hur många operationer och deloperatio- ner som maskinvaran/anordningen kan utföra inom ett tidsintervall. En anordning som klockas med en hög klock- frekvens drar oundvikligen också mycket ström, ett särdrag som kan vara ett stort problem i mobila och till exempel batteridrivna anordningar.

XOR-metoden lämpar sig egentligen bara för överföringsme- toder som har en låg bittakt och en låg felintensitet, eftersom metoden är extremt beräkningsintensiv. På grund av att XOR-metoden är beräkningsintensiv hinner metoden, även med överföringsmetoder som har en låg överföringstakt, endast med jämförelser för de bitmönster som man önskar finna. XOR-metoden blir därmed inte feltolerant. För att uppnå feltolerans, det vill säga att kunna detektera bitmönster med en förvanskning (något eller några bitfel), krävs att de ovan nämnda XOR-operationerna och jämförelser- na utökas med XOR-operationer och jämförelser mot varje "förvanskning" som man vill inbegripa i detekteringen.

Utökningen av antalet XOR-operationer och jämförelser måste dessutom kunna utföras inom samma tillgängliga tidsin- tervall. En utökning av antalet operationer som behöver 10 15 20 25 30 506 241 4 utföras inom ett givet tidsintervall ställer ytterligare snabbhetskrav på den utförande maskinvaran. Detta leder, om det överhuvud taget är möjligt att utföra, till dyrare ingående komponenter och högre strömförbrukning.

En del mobiltelefonisystem använder sig av TDMA (Time Division Multiple Access), till exempel PDC (Pacific Digital Cellular). I TDMA-system är det ett starkt önskemål att kunna kombinera de ovan nämnda kraven på snabbhet med feltolerans vid sökning efter bitmönster, exempelvis synkroniseringsord, i en bitström. Feltolerans är en särskilt viktig egenskap i radiobaserade informa- tionsöverföringssystem eftersom radiobaserad överföring är långtifrån ideal. system, bland annat data och synkroniseringsord, sker i Översändning av' information i. TDMA- tilldelade tidsluckor och genom att hitta synkroniserings- ord kan mottagaren bestämma var i tidsluckan som informa- tionen befinner sig.

I det amerikanska patentet US 4,847,877 beskrivs en anord- ning som är avsedd för detektering av ett bitmönster i en bitström. Metoden försöker först detektera delmängder av det sökta bitmönstret i en bitström genom att jämföra del- kandidatbitmönster ur bitströmmen med varje godtagbar delmängd var för sig. Därefter, vid detektering av en godtagbar delmängd, jämförs varje enskild bit i bitströmmen med resterande bitar i det sökta bitmönstret, varvid räknare räknar antalet godkända jämförelser. Det kan anses att en nackdel med denna anordning är att den kräver ett stort antal operationer och deloperationer för bitmönster- detektering, samt att den på ett enkelt sätt sannolikt ej medger någon större grad av feltolerans. 10 15 20 25 30 35 506 241 REDoGöRELsE FÖR UPPFINNINGEN Ett ändamål med uppfinningen är att ange ett förfarande och en anordning för snabb bitmönsterdetektering i en bitström.

Ett annat ändamål med uppfinningen är att ange ett för- farande och en anordning för att kunna uppnå en feltolerant bitmönsterdetektering i en bitström.

Ytterligare ett ändamål med uppfinningen är att ange ett förfarande och en anordning medelst vilka man feltolerant kan detektera och identifiera olika fördefinierade synkro- niseringsord i en bitström. Ännu ett ändamål med uppfinningen är att ange ett för- farande och en anordning medelst vilka man kan bestämma tidläget för en informationsmängd i en tidlucka.

Ovannämnda ändamål uppnås enligt uppfinningen genom ett förfarande och en anordning där man snabbt och strömsnålt med feltolerans samtidigt detekterar alla önskade bit- mönster, inklusive godtagbara förvanskningar, per ex- traherat kandidatbitmönster i en bitström. Detta åstadkom- mes genom att en fördefinierad tabell utnyttjas vilken adresseras av kandidatbitmönster. Positioner i tabellen vilkas adresser motsvarar de bitmönster man söker efter, inklusive godtagbara förvanskningar av dessa, innehåller uppgift om det föreligger en detektering vid den adressen.

Positionerna innehåller också information relaterad till de bitmönster man söker. Informationen kan bestå av vilket bitmönster som detekterats feltolerant och uppgifter om hur förvanskat kandidatbitmönstret är relativt det feltolerant detekterade bitmönstret. Positioner i. tabellen vilkas adresser ej motsvarar något av de bitmönster man söker efter eller godtagbara förvanskaningar av dessa innehåller 10 15 20 25 30 35 506 241 6 uppgift om att det ej föreligger en detéktering vid den adressen.

Ovannämnda ändamål uppnås enligt uppfinningen även genom ett förfarande för att i en bitström detektera ett visst antal förutbestämda bitmönster och, inom en bestämd feltolerans, förvanskningar av bitmönstren. Förfarandet för detekteringen innefattar ett antal steg. Först bildas ett kandidatbitmönster i form av ett bestämt antal bitar ur bitströmmen. Därefter används kandidatbitmönstret som adress för adressering av positioner i en tabell. Varje position i tabellen innefattar träffinformation som anger träff om positionens adress överenstämmer med något av de förutbestämda bitmönstren eller de inom feltoleransen varande förvanskningarna. Träffinformationen anger miss i övriga positioner. Positionerna i tabellen innefattar även felinformation som, vid positioner där träffinformationen anger träff, anger hur mycket positionens adress avviker från det förutbestämda bitmönster som träffinformationen anger träff om. Träffinformationen 5. den position som adresseras av kandidatbitmönstret utvärderas därefter varvid ett resultat skapas som anger om det inom den bestämda feltoleransen föreligger en detektering av något av de förutbestämda bitmönstren eller inte.

Träffinformationen vid de positioner i tabellen som anger träff är företrädesvis lika med det förutbestämda bit- mönster som motsvarande position representerar eller en referens till det förutbestämda bitmönster som motsvarande position representerar.

Tabellen kan även bestå av minst två deltabeller. Adres- seringen av tabellen sker då för varje deltabell med en motsvarande del av kandidatbitmönstret sekvensiellt så länge som träffinformationen i deltabellerna anger träff.

Då träffinformationen i en deltabell anger miss eller den 10 15 20 25 30 35 506 241 7 sista deltabellen adresserats, utvärderas träffinforma- tionen från de adresserade deltabellerna och då en miss framträtt i en deltabells träffinformation förkastas hela kandidatbitmönstret.

Resultatet kan bestämma tidsläget för detekterade förutbe- stämda bitmönster i bitströmmen. De förutbestämda bit- mönstren kan även vara synkroniseringsord som används för synkronisering ev en bitström mellan en sändare och en mottagare.

Ovannämnda ändamål uppnås enligt uppfinningen även genonnen anordning som detekterar ett visst antal förutbestämda bitmönster, och inom en bestämd feltolerans, förvanskningar av bitmönstren, i en bitström. Anordningen innefattar lämpligen extraktionsmedel, minst en tabell, adresserings- medel och utvärderingsmedel. Extraktionsmedlet är inrättat att ur bitströmmen bilda ett kandidatbitmönster av ett förutbestämt antal bitar. Tabellen är inrättad med ett antal adresserbara positioner. Varje position i tabellen innefattar träffinformation som anger träff om positionens adress överenstämmer med något av de förutbestämda bit- mönstren eller de inom feltoleransen varande förvanskning- arna. Träffinformationen anger miss i övriga positioner.

Varje position innefattar lämpligen även felinformation som, vid positioner där träffinformationen anger träff, anger hur mycket positionens adress avviker från det förutbestämda bitmönster'som träffinformationen anger träff om. Adresseringsmedlet är inrättat att adressera tabellen med kandidatbitmönstret varvid tabellen ger träffinforma- tion och felinformation från motsvarande position. Utvär- deringsmedlet i anordningen är inrättat att utvärdera träffinformationen från kandidatbitmönstrets adressering av tabellen och därav skapa ett resultat som definierar om det inom feltoleransen föreligger en detektering av något av de förutbestämda bitmönstren eller inte. 10 15 20 25 30 35 506 241 8 Träffinformationen vid de positioner som anger träff är lämpligen lika med det förutbestämda bitmönster som motsva- rande position representerar eller en referens till det förutbestämda bitmönster son1motsvarande position represen- terar.

Tabellen kan även bestå av minst två deltabeller. Adres- seringsmedlet adresserar då varje deltabell med en motsva- rande del av kandidatbitmönstret sekvensiellt så länge som träffinformationen i deltabellerna anger träff. Då träffinformationen j. en deltabell anger miss eller den sista deltabellen adresserats, utvärderar utvärderings- medlet träffinformationen från de adresserade deltabellerna och då en miss framträtt i en deltabells träffinformation förkastas hela kandidatbitmönstret.

Resultatet kan bestämma tidsläget för detekterade förutbe- stämda bitmönster i bitströmmen. De förutbestämda bit- mönstren kan vara synkroniseringsord som används för synkronisering av en bitström mellan en sändare och en mottagare.

Lämpligen är extraktionsmedlet, adresseringsmedlet och utvärderingsmedlet innefattade i en digital signal pro- CGSSOI" .

Ovannämnda ändamål uppnås enligt uppfinningen även genom ett system för att i en bitström detektera ett förutbestämt antal förutbestämda bitmönster och, inom en bestämd feltolerans, förvanskningar av bitmönstren. De förutbe- stämda bitmönstren utgörs av första och andra delbitsmön- ster och förvanskningarna av bitmönstren utgörs av första och andra delförvanskningar. Systemet innefattar ex- traktionsmedel, en första och en andra deltabell, adres- seringsmedel och utvärderingsmedel. Extraktionsmedlet är inrättat att ur bitströmmen bilda ett kandidatbitmönster av 10 l5 20 25 30 35 506 241 9 ett förutbestämt antal bitar. Kandidatbitmönstret bildar två delkandidatbitmönster. deltabellen är inrättade med ett antal adresserbara posi- Den första och den andra tioner. Varje position i båda deltabellerna innefattar träffinformation. Träffinformationen anger träff om posi- tionens tillhörande adress överenstämmer med något av de första respektive andra delbitmönstren eller de första respektive andra delförvanskningarna. Träffinformationen anger miss i övriga positioner. Varje position i den andra deltabellen innefattar även felinformation. Felinformatio- nen anger, vid positioner där träffinformationen anger träff, hur mycket positionens adress avviker från det förutbestämda bitmönster som träffinformationen angett träff om. Adresseringsmedlet är inrättat att först adressera den första deltabellen med det första delkandi- datbitmönstret och att om miss framträder ur träffinforma- tionen förkasta hela kandidatbitmönstret och att om träff framträder ur träffinformationen fortsätta och adressera den andra deltabellen med.det andra delkandidatbitmönstret.

Varvid den andra deltabellen ger träffinformation och felinformation från motsvarande position. Utvärderingsmed- let är inrättat att utvärdera träffinformationen från respektive delkandidatbitmönsters adressering av respektive deltabell och därav skapa ett resultat som definierar ifall det föreligger en feltolerant detektering av något av de förutbestämda bitmönstren eller inte.

FIGURBESKRIVNING Uppfinningen skall. i det följande närmare beskrivas i förklarande och inte på något vis begränsande syfte, med hänvisning till bifogade figurer, där Fig. 1 visar schematiskt en TDMA ram, 10 15 20 25 30 35 506 241 10 Fig. 2 visar schematiskt täckningen för basstationer i ett mobiltelefonisystem, Fig. 3 visar schematiskt den principiella funktionen hos uppfinningen, Fig. 4A visar ett flödeschema över ett förfarande enligt uppfinningen, Fig. 4B visar ett flödeschema över ytterligare ett för- farande enligt uppfinningen, Fig. 5 visar ett blockschema över en utföringsform av en anordning enligt uppfinningen, Fig. 6 visar ett blockschema över ytterligare en ut- föringsform av en anordning enligt uppfinningen.

FÖREDRAGNA UTFÖRINGSFORMER Mobiltelefonisystem är ofta så kallade TDMA-system (Time Division Multiple Access). Ett TDMA-överföringssystem innebär att, se figur 1, ett visst antal, K, så kallade ka- naler delar på en och samma frekvens genom att varje kanal sänder sin information inom en viss tidsperiod (tidlucka) 110 i en TDMA-ram 190. Den information som kanalen sänder under sin tidlucka innehåller förutom data även, bland annat, synkroniseringsord. Synkroniseringsord gör att den mottagande parten kan avgöra var i tidluckan den mottagna bitströmmen är placerad. Detta sker genom att den motta- gande parten söker genom informationsmängden i en tidslucka efter synkroniseringsord. När den mottagande parten hittat synkroniseringsord i tidsluckan vet den mottagande parten var den sökta "nyttiga" informationen befinner sig i den tidsluckan. 10 15 20 25 30 35 506 241 ll ' Behov av synkronisering inonnmobiltelefdni kan till exempel uppstå vid så kallad "hand-over". Betrakta den schematiska täckningen för ett mobiltelefonisystemet i figur 2. Den yta som täcks av mobiltelefonisystemet är indelad i celler 211, 212, 213, 214, 221, 222. cell finns en basstation, som kommunicerar dels med de Centralt placerad i varje mobiltelefoner som finns i cellen, dels med en telefonväxel 210, 220 som är ansluten till ett antal celler. I det här exemplet är växel 210 ansluten bland annat till bassta- tionerna i cellerna 211, 212, 213 och 214 och växel 220 är bland annat ansluten till basstationerna i cellerna 221 och 222.

Basstationerna sänder konstant ut information på så kallade styrfrekvenser, bland annat information om vilka kanaler (tidluckor) som är lediga i den cellen. Denna information utnyttjas av de mobiltelefoner som är nya i cellen. En mobiltelefon som är på väg ut ur en cell, till exempel cell 211, och på väg in i cell 212 kan på detta vis få besked om vilken tidlucka den skall använda i den nya cellen.

Mobiltelefonen börjar använda denna tidlucka, ochlmed hjälp av synkroniseringsordet i dataströmmen synkroniserar basstationen den nya mobiltelefonens bitström. Eftersom båda basstationerna (i cellerna 211 och 212) kommunicerar med samma växel 210 skulle, i ett idealfall, mobiltelefonen kunna "överföras" mellan basstationerna utan synkronise- ringsproblem.

Problem uppstår emellertid när en mobiltelefon skall förflytta sig mellan celler som tillhör olika växlar, där basstationerna inte är synkroniserade med varandra. I de fall en mobiltelefon skall förflytta sig mellan bassta- tioner som tillhör växlar med olika operatörer är problemen med synkronisering vid förflyttning mellan basstationer ännu större. Problem kan alltså uppstå ifall en mobiltele- fon förflyttar sig frân cell 212, som med sin basstation är 10 15 20 25 30 35 506 241 12 ansluten till växel 210, till cell '2fl, som med sin basstation är ansluten till en annan växel 220.

För att synkronisera information från mobiltelefoner och förbli synkroniserade med dessa söker basstationer i ett mobiltelefonisysten\ konstant efter synkroniseringsord i tidluckor. Synkroniseringsorden kan typiskt vara cirka tjugo bitar långa i en tidlucka som rymmer i storleksord- ningen några hundratal bitar. En. TDMA-ram innefattar vanligtvis sex stycken tidluckor med minst ett synkronise- ringsord per tidlucka.

För att försäkra sig mot falska detekteringar av synkroni- seringsord ställs vanligen krav på att samma synkronise- ringsord skall detekteras på samma ställe i samma tidlucka ett visst antal gånger. Detta medför ett behov av ytterli- gare beräkningar som till exempel kan ske genom att bilda statistik över vilka synkroniseringsord som har detekte- rats, och var i de olika tidluckorna de har detekterats.

För att systemet skall ha en viss feltolerans godtar man att det i ett detekterat synkroniseringsord finns ett antal fel, som vanligtvis kan röra sig om två stycken bitfel. De ytterligare beräkningarna ovan bör med andra ord även inne- fatta de godtagbara "förvanskningarna" av de synkronise- ringsord som man letar efter. Det är alltså ett starkt önskemål att kunna kombinera de ovan nämnda kraven på snabbhet med feltolerans. Feltolerans är en särskilt viktig egenskap i radiobaserade system eftersom överfö- ringen är långtifrån perfekt via radio och omsändningar är tidskrävande och kanske inte möjliga för att kunna uppfylla hårda tidskrav.

Uppfinningen har som ändamål att ange ett förfarande och en anordning som uppfyller de krav på snabbhet, som exempelvis TDMA överföringssystem har, vid letandet efter bitmönster 10 15 20 25 30 35 506 241 13 som exempelvis kan vara synkroniseringsord. För att tydliggöra uppfinningen skall några exempel på dess tillämpning i. det följande beskrivas j. anslutning till figurerna 3 - 6.

Figur 3 visar i blockschemaform en grundläggande utförings- form av ett förfarande och en anordning enligt föreliggande uppfinning. För att sätta in exemplet i ett sammanhang har här antagits att man söker efter synkroniseringsord vilket inte skall ses som en begränsning utan endast som en illustration över ett användningsområde för uppfinningen.

I figur 3 visas en seriell bitström 310 i vilken man söker efter synkroniseringsord, samt en tabell 340. Tabellen 340 är uppdelad i två delar, en första del 342 och en andra del 344.

Antag att ordlängden för de synkroniseringsord som skall hittas i bitströmmen är L. I en grundanordning och enligt ett grundförfarande ingår i sådana fall en tabell med storleken 2L som innehåller samtliga de synkroniseringsord man vill söka efter, inklusive de godtagbara "förvansk- ningarna" av dessa i en första del 342. Ett kandidatbit- mönster 330 av längden L bildas genom att L bitar exe traheras ur bitströmmen. Kandidatbitmönstret används för att adressera en position 349 i tabellen, det vill säga kandidatbitmönstret används som adress. Varje adress motsvarar således en position i tabellen. För varje gång en ny bit mottas, skiftas bitströmmen en position, varvid ett nytt kandidatbitmönster extraheras och därmed också en ny adress.

De positioner i tabellen 340 vilkas adresser ej motsvarar något av de synkroniseringsord man söker efter eller godtagbara förvanskningar av dessa, innefattar i den första delen 342 en indikering att adressen ej motsvarar en detektering och kan exempelvis vara talet noll. De 10 15 20 25 506 241 14 positioner i tabellen 340 vilkas adresser däremot motsvarar något av de synkroniseringsord man söker efter eller godtagbara förvanskningar av dessa, innefattar i den första delen 342 en indikering att adressen motsvarar en detekte- ring. Indikeringen att en adress motsvarar en detektering kan vara det oförvanskade synkroniseringsord som kandidat- bitmönstret motsvarar eller en referens till det oförvan- skade synkroniseringsordet. Den andra delen 344 av tabellen 340 innefattar information om hur många fel kandi- datbitmönstret har i. förhållande till det oförvanskade eftersökta synkroniseringsordet.

Om den adresserade positionen 349 innehåller något av de synkroniseringsord man söker efter indikeras "träff" i den första delen 342. Samtidigt indikeras, enligt vad som har beskrivits ovan, antalet "fel" i den andra delen 344.

Således kan vidare beräkningar över var i tidluckan som ett eventuellt synkroniseringsord befinner sig enkelt göras.

För att illustrera metoden i ytterligare ett exempel antas här för enkelhetens skull att man letar efter ett bit- mönster som är fem bitar långt och lika med 10101 binärt.

I exemplet godtas ett bitfel som en förvanskning av det sökta bitmönstret. Önskvärt i detta fall är alltså att hitta ett bitmönster och dess fem olika förvanskningar, se tabell 1. 10 15 20 25 30 506 241 15 BITMÖNSTER 10101 ETT HIT FEL 00101 ETT BIT FEL 11101 ETT BIT FEL 10001 ETT BIT FEL 10111 ETT BIT FEL 10100 TABELL 1 - Sökt bitmönster och godtagbara förvanskningar Eftersom bitmönstret i detta enkla exempel är fem bitar långt krävs enligt en utföringsform av uppfinningen en tabell med trettiotvå positioner (25=32). Tabell 2 visar hur en sådan tabell kan se ut. Här är de trettiotvå positionerna numrerade från noll till trettioett eftersom det stämmer överens med den binära adressering som utnytt- jas. Observera att det inte behöver vara en absolut adressering utan kan vara en förskjutning (offset) i ett större minne.

Till varje adress svarar en position. Till varje position hör två olika typer av information, nämligen information om en träff föreligger eller ej (träffdata, vilket motsvarar den första delen 342 i det föregående exemplet) och information om hur förvanskad träffen är (feldata, vilket motsvarar den andra delen 344 i det föregående exemplet).

I exemplet kan man konstatera att träffdatadelen för alla positioner utom de med adresserna 5, 17, 20, 21, 23 och 29 innehåller värdet noll. Noll i träffdata indikerar att den positionen inte är någon träff och att feldata i så fall saknar innebörd. 10 15 20 25 30 35 506 241 position F' Ökbæxlßiwnßbulfll-'C l-' l-' I-' IQ |-' b) |-' uß F' UT I-' 03 |-' \I I-l æ 19 20 21 22 23 24 25 26 27 28 29 30 31 TABELL 2 - tabell / positionsinnehåll adress 00000 00001 00010 00011 00100 00101 00110 00111 01000 01001 01010 01011 01100 01101 01110 01111 10000 10001 10010 10011 10100 10101 10110 10111 11000 11001 11010 11011 11100 11101 11110 11111 16 träff Q- DJ rf KD F-*OOOOO O F' O F* OOOOOOOOOOO 10101 10101 10101 10101 OOOOO 10101 fel data 10 15 20 25 30 35 506 241 17 lFör att hitta det sökta bitmönstret och'dess godtagbara förvanskningar i detta exempel extraherar man ett kandidat- bitmönster av samma längd som det sökta bitmönstret. Kan- didatbitmönstret används sedan som adress för att adressera en position i tabell 2. Ur tabell 2 fås information om träff föreligger eller ej och om en träff föreligger hur förvanskat kandidatbitmönstret är i relation till det sökta bitmönstret. Informationen från tabellen kan därefter användas på lämpligt sätt till vidare beräkningar beroende på applikation. Därefter börjar proceduren om igen med att ett nytt kandidatbitmönster bildas för att därigenom bilda en ny adress till tabell 2 och så vidare.

Antag att man extraherat ett kandidatbitmönster som är 11011 binärt.

Position 27 innehåller träffdata med värdet 0 vilket indikerar att man i detta fall inte har någon träff med det Det motsvarar position 27 i tabell 2. sökta bitmönstret eller ens en godtagbar förvanskning.

Eftersom träffdata innehöll 0 saknar feldata relevans överhuvudtaget vilket har indikerats med ett “-" tecken i tabell 2.

Om man vid ett annat tillfälle har extraherat ett kandi- datbitmönster som är 11101 binärt, motsvarar det istället position 29 i tabell 2. I position 29 innehåller träffdata värdet 10101 vilket är skilt från 0 och indikerar att en träff har skett i detta fall.

Träffdata ger antingen det sökta bitmönstret direkt som i det här fallet eller indirekt som en referens till det bitmönster man påträffat. När man bara söker efter ett bitmönster räcker det egentligen med 0 och 1 i träffdata för att indikera träff eller ej. Ifall man letar efter längre och flera olika bitmönster, kan det vara lämpligt att använda sig av en referens som indikerar att det är träff och vilket av de sökta bitmönstren det blev träff på. 10 15 20 25 30 35 506 241 18 I det senaste exemplet är kandidatbitmönstret 11101 vilket inte är lika med det sökta bitmönstret 10101, men kandi- datbitmönstret tillhör mängden bitmönster med godtagbara förvanskningar. Feldata i tabellen innebär en indikering på om det är en perfekt träff eller en träff .med en godtagbar förvanskning. I position 29 på feldata står det 1 vilket ger att kandidatbitmönstret är en godtagbar förvanskning med ett bitfel.

Som en summering kan en grundutföringsform av uppfinningen beskrivas som en anordning och en metod som samtidigt söker efter alla bitmönster N och deras godtagbara förvanskningar M av en längd L för varje kandidatbitmönster. Ett kandi- datbitmönster av längden L används som adress i en tabell med storleken ZÄ På de positioner vars adresser motsvarar ett av de sökta bitmönstren N eller godtagbara förvansk- ningar M indikeras träff. Träff indikeras till exempel genom att positionen anger vilket av de oförvanskade bit- mönstren N det är eller en referens som motsvarar vilket av de oförvanskade bitmönstren det är. På alla andra posi- tioner indikeras miss, till exempel genom att där står noll.

Figur 4A. visar ett flödesschema på en tillämpning av uppfinningen för detektering av bitmönster. Första steget är ett startsteg 410 som kan vara maskinvarunollställning eller ett programvaruanrop. Startsteget 410 kan också med fördel skapa en fördefinierad tabell som senare steg använder ifall den fördefinierade tabellen ej skapats tidigare. Därefter kommer företrädesvis ett anpassnings- steg 420 som anpassar informationsflödesformatet till ett för följande steg lämpligt format. Anpassningen kan bestå av seriell till parallellomvandling om informationsflödes- formatet är en seriell bitström eller någon annan slags anpassning av data till efterföljande steg. Därefter 10 15 20 25 30 35 506 241 19 följer ett extraktionssteg 430 som extraherar ett kandidat- bitmönster.

När ett kandidatbitmönster är extraherat används detta som en adress för att adressera en position i den fördefiniera- de tabellen. 'Tabelladresseringen sker i adresseringssteget 440. Alla positioner i tabellen består, som nämnts ovan, fördelaktigast av minst två delar, nämligen en första del som innefattar träffdata och en andra del som innefattar feldata. Tabellen måste minst innefatta träffdatadelen.

Träffdatadelen till den position i tabellen som adressera- des i adresseringssteget 440 testas därefter i teststeget 450. I det fall att ingen träff indikeras förkastas det aktuella kandidatbitmönstret och.proceduren fortsätter till ett "mera data" teststeg 470. Om däremot träff indikeras går proceduren vidare till ett bearbetningssteg 460.

I bearbetningssteget 460 bestäms vilket sökt bitmönster som detekterades genom utnyttjande av träffdatadelen. Kandi- datbitmönstret är inte nödvändigtvis lika med det sökta bitmönster som detekterades utan kan även vara en godtagbar förvanskning. Bearbetningssteget 460 bestämmer eventuellt också genom att utnyttja feldatadelen om det var en perfekt träff, det vill säga noll fel, eller en träff inom en felmarginal på ett förutbestämt antal bitfel. Bearbet- ningssteget 460 kan eventuellt även bearbeta data och feldata vidare för att till exempel bestämma var i bit- strömmen som träffar sker. Bearbetningssteget 460 skickar företrädesvis vidare träffdata och eventuella feldata och/eller eventuellt resultaten av ytterligare bearbet- ningar till andra behandlingssteg.

När behandlingen av data är färdig i behandlingssteget 460 fortsätter proceduren till "mera data" teststeget 470.

Teststeget 470 kan i vissa tillämpningar vara överflödigt.

Vissa tillämpningar utnyttjar endast proceduren en gång i 10 15 20 25 30 35 506 241 20 taget, det vill säga att endast ett kandidatbitmönster extraheras ur bitströmmen och att proceduren slutar och går till slutsteget 480 direkt för att därefter utföra andra bearbetningar innan det eventuellt är tid att starta hela proceduren igen. Andra tillämpningar låter proceduren (som kan utföras både rent programvarumässigt eller rent maskinvarumässigt eller som en kombination) fortsätta kontinuerligt. Detta innebär att proceduren fortsätter och hoppar till anpassningssteget 420 och sedan extraktionsste- get 430, där ett nytt kandidatbitmönster extraheras ur bitströmmen. Teststeget 470 klarar av ytterligheterna och allt däremellan.

Om L är stort (L=bitmönsterlängd), det vill säga tabellen blir stor och minneskrävande, kan det lösas genom att två alternativt fyra eller fler adresseringar göres för varje kandidatbitmönster med delkandidatbitmönster där varje delkandidatbitmönster har längden L/2 eller L/4 och så vidare. Om man enligt ett typiskt TDMA-system använder synkroniseringsord på 20 bitar, kräver den grundläggande utföringsformen enligt uppfinningen att en tabell med 1048576 positioner används.

Om däremot kandidatbitmönstret exempelvis delas upp i två lika stora delar och det första och det andra delkandi- datbitmönstret adresserar var sin tabell med storleken 2”2, blir varje tabell i exemplet med synkroniseringsord på 20 bitar endast 1024 positioner stor. Det ger i detta fall en besparing med hela 1046528 positioner.

Först adresserar det första delkandidatbitmönstret sin tabell och vid träff adresserar det andra delkandidatbit- mönstret sin tabell. Hela kandidatbitmönstret förkastas så fort det inte blir någon träff i en av adresseringarna.

Det betyder att i allmänhet behöver endast en adressering göras även i detta fall. Endast i de fall där det första 10 15 20 25 30 35 506 241 21 delkandidatbitmönstret ger en träff behöver en andra adressering göras med det andra delkandidatbitmönstret i den andra tabellen.

Figur 4B visar ett flödesschema för en variant av den mera avancerade utföringsformen av uppfinningen. Flödesschemat illustrerar det fall tabellen delas upp i två deltabeller.

De tre första stegen, startsteget 410, anpassningssteget 420 och extraktionssteget 430, kan fungera i stort sett enligt beskrivningen av figur 4A ovan. Det tidigare adresseringssteget är nu uppdelat i två delar varav det första deladresseringssteget 442 använder den första halvan av kandidatbitmönstret från extraktionssteget 430 för att Båda deltabellerna som utnyttjas är som tidigare nämnts lämpligen fördefinierade. adressera en första deltabell.

Den första deladresseringen ger minst information om, huruvida det är träff eller ej. I det fall att den första deladresseringen indikerar ej träff, förkastar det första delteststeget 452 hela kandidatbitmönstret och proceduren fortsätter vidare till ett "mera data" teststeg 470. Om däremot den första deladresseringen indikerar träff, skickar det första delteststeget 452 proceduren vidare till ett andra deladresseringssteg 444.

Det andra deladresseringssteget 444 använder sig av den andra halvan av kandidatbitmönstret för att adressera en andra deltabell. I det fall att den andra deladresseringen indikerar ej träff förkastar det andra delteststeget 454 hela kandidatbitmönstret och skickar proceduren vidare till "mera data"-teststeget 470. Om däremot den andra del- adresseringen indikerar träff, skickar det andra deltest- steget 454 proceduren vidare till ett bearbetningssteg 460.

Bearbetningssteget 460 fungerar i. princip som tidigare beskrivits enligt figur 4A ovan. Teststeget 470 fungerar även det i princip som det tidigare enligt figur 4A och be- stämmer således när proceduren skall sluta. 10 15 20 25 30 35 506 241 22 Föreliggande uppfinning kan apparatiseras antingen som ren maskinvara, som ren programvara eller som en kombination av maskinvara och programvara. Om metoden enligt uppfinningen realiseras som programvara, kan den vara helt självständig eller vara en del i ett större program. Programvaran kan lämpligen befinna sig i en generell dator eller i en dedicerad dator såsom en digital signal processor (DSP).

Figurerna 5 och 6 'visar två olika apparatiseringar av föreliggande uppfinning och skall endast ses som exempel på möjliga utföringsformer.

Figur 5 visar ett blockschema över ett exempel på en ut- föringsform av en anordning enligt uppfinningen i huvudsak utförd i maskinvara. Ett informationsflöde i form av en bitström finns tillgängligt vid 515 och matas in i ett extraktionsblock 520 för kandidatbitmönster. Extraktions- blocket 520 är lämpligen försett med medel för anpassning av informationsflödet 515 till övrig maskinvara som till exempel en kontinuerlig seriell till parallellomvandling med hjälp av till exempel en skiftregisterfunktion. Vid användning i TDMA-system kan exempelvis medel för ram- synkronisering innefattas i extraktionsblocket 520.

I anordningen innefattas minst ett minne 530 för lagring av tabellen enligt uppfinningen. Minnet 530 kan vara ett flyktigt minne men vid en ren xnaskinvaruapparatisering föredrages att minnet 530 är icke-flyktigt och fördefinie- rat med tabellen enligt uppfinningen. Tabellen i minnet 530 adresseras av kandidatbitmönstret från extraktions- blocket S20 och ger resultatet till ett behandlingsblock 540 som lämpligen innefattar medel, såsom jämförare, för att fastställa ifall kandidatbitmönstret gav upphov till en träff eller ej. Behandlingsblocket 540 skickar lämpligen resultatet 555 såsom vilket bitmönster det blev träff på och hur många bitfel ifrån det sökta bitmönstret kandidat- 10 15 20 25 30 35 506 241 23 bitmönstret var och eventuell ytterligare information till andra enheter för eventuell vidare behandling.

Varje block enligt figur 5 kan exempelvis utföras antingen med hjälp av diskreta grindar och minnen, i mer eller mindre komplexa kretsar, eller som grindfunktioner i en eller flera kundspecificerade kretsar (ASIC - Application Specific IC).

Figur 6 visar ett blockschema över en utföringsform av en anordning som utnyttjar uppfinningen i huvudsak i program- varuform exekverad i en dator. Datorn innefattar lämpligen minst två gränssnittsenheter (I/O) 620, 630, en styrenhet (CPU) 660, ett programminne (RAM, ROM, PROM, EPROM, EEPROM) 650 och ett dataminne (RAM, EEPROM) 640. flödet i form av exempelvis en bitström finns tillgängligt Informations- vid 615 och matas in i en första gränssnittsenhet 620. Den första gränssnittsenheten 620 anpassar, bland annat, informationsflödet till informationsöverföringen mellan de olika enheterna vilket sker via ett adress- och databuss- system 675. Adress- och databuss-systemet 675 innefattar medel för att säkerställa att alla erforderliga adress-, data- och styrsignaler är sammankopplade mellan alla enheter.

Styrenheten 660 utför beräkningar och styr och kontrollerar informationsflödet mellan alla enheterna. Programminnet 650, som företrädesvis är fördefinierat, innehåller lämpli- gen styrprogrammet med instruktioner för styrenheten 660 så att anordningen kan utföra metoden enligt uppfinningen.

Dataminnet 640 eller eventuellt programminnet 650 in- nehåller tabellen enligt uppfinningen. Dataminnet 640 är företrädesvis också försett med utrymme för permanent och temporär lagring av bland annat variabler som utnyttjas av styrenheten 660. 10 15 20 506 241 24 Detta andra exempel på en apparatisering'av uppfinningen innefattar även en andra gränssnittsenhet 630. Den andra gränssnittsenheten 630 har lämpligen till uppgift att först eventuellt lagra och sedan vidarebefodra resultaten 655.

Vilken typ av information och resultat som skickas vidare till andra enheter bestäms av den specifika utförings- formen.

Alla dessa block och enheter kan vara fysiskt helt separat utförda i olika enheter, varje block kan till och med bestå av ett flertal fysiska enheter, eller fysiskt bestå av en enda enhet eller någon variant däremellan, det vill säga att vissa block innefattas i en fysisk enhet medan andra inte gör det. De enskilda blocken eller hela datorn kan delas med andra funktioner med hjälp av till exempel tidsdelning. En föredragen variant är att metoden utförs som en del i en digital signalprocessor.

Uppfinningen är ej begränsad till de ovan nämnda utförings- formerna utan kan varieras inom ramen för de efterföljande patentkraven.

Claims (14)

10 15 20 25 30 35 506 241 25 PATENTKRAV

1. Förfarande för att i en bitström detektera ett visst antal förutbestämda bitmönster och, inom en bestämd feltolerans, förvanskningar av bitmönstren, kännetecknat därav, att detekteringen innefattar följande steg: - ett kandidatbitmönster bildas i form av ett bestämt antal bitar ur bitströmmen; - kandidatbitmönstret används sonladress för adressering av positioner i en tabell, varvid varje position i tabellen innefattar: - träffinformation som anger träff om positionens adress överenstämmer med något av de förutbe- stämda bitmönstren eller de inom feltoleransen varande förvanskningarna och där träffinforma- tionen anger miss i övriga positioner, och - felinformation som, vid positioner där träffin- formationen anger träff, anger hur mycket posi- tionens adress avviker från det förutbestämda bitmönster som träffinformationen anger träff om; - träffinformationen i den position som adresseras av kandidatbitmönstret utvärderas varvid ett resultat skapas som anger om det inom den bestämda feltoleran- sen föreligger en detektering av något av de förut- bestämda bitmönstren eller inte.

2. Förfarande enligt patentkrav 1, kännetecknat därav, att träffinformationen vid de positioner i tabellen som anger träff är lika med det förutbestämda bitmönster som motsva- rande position representerar. 10 15 20 25 30 35 506 241 26

3. Förfarande enligt patentkrav 1, kännetecknat därav, att träffinformationen vid de positioner i tabellen som anger träff är lika med en referens .till det förutbestämda bitmönster som motsvarande position representerar.

4. Förfarande enligt något av patentkrav 1-3, kännetecknat därav, att tabellen består av minst två deltabeller och att adresseringen av tabellen sker för varje deltabell med en motsvarande del av kandidatbitmönstret sekvensiellt så länge som träffinformationen i deltabellerna anger träff och då träffinformationen i en deltabell anger miss eller den sista deltabellen adresserats, utvärderas träffin- formationen från de adresserade deltabellerna och då en miss framträtt i en deltabells träffinformation förkastas hela kandidatbitmönstret.

5. Förfarande enligt något av patentkrav 1-4, kännetecknat därav, att genom resultatet bestämes tidsläget för detekterade förutbestämda bitmönster i bitströmen.

6. Förfarande enligt något av patentkrav 1-5, kännetecknat därav, att de förutbestämda bitmönstren är synkroniserings- ord som används för synkronisering av en bitströnxmellan en sändare och en mottagare.

7. Anordning för att i en bitström (515, 615) detektera ett visst antal förutbestämda bitmönster och, inom en bestämd feltolerans, förvanskningar av bitmönstren, kännetecknad därav, att nämnda anordning innefattar: - extraktionsmedel (520, 620, 660) som är inrättat att ur bitströmmen bilda ett kandidatbitmönster av ett förutbestämt antal bitar; - minst en tabell (530, 640, 650) inrättad med ett antal adresserbara positioner varvid varje position i tabel- len innefattar: 10 15 20 25 30 35 506 241 27 - träffinformation som anger träff om positionens adress överenstämmer med något av de förutbe- stämda bitmönstren eller de inom feltoleransen varande förvanskningarna och där träffinforma- tionen anger miss i övriga positioner, och - felinformation som, vid positioner där träffin- formationen anger träff, anger hur mycket posi- tionens adress avviker från det förutbestämda bitmönster som träffinformationen anger träff om; - adresseringsmedel (520, 660) som är inrättat att adressera tabellen med kandidatbitmönstret varvid tabellen ger träffinformation och felinformation från motsvarande position; - utvärderingsmedel (540, 660) som är inrättat att ut- värdera träffinformationen från kandidatbitmönstrets adressering av tabellen och därav skapa ett resultat som definierar om det inom feltoleransen föreligger en detektering av något av de förutbestämda bitmönstren eller inte.

8. Anordning enligt patentkrav 7, kännetecknad därav, att träffinformationen vid de positioner som anger träff är lika med det förutbestämda bitmönster son! motsvarande position representerar.

9. Anordning enligt patentkrav 7, kännetecknad därav, att träffinformationen vid de positioner som anger träff är lika med en referens till det förutbestämda bitmönster som motsvarande position representerar.

10. Anordning enligt något av patentkrav 7-9, kännetecknad därav, att tabellen består av minst två deltabeller och att adresseringsmedlet adresserar varje deltabell med en motsvarande del av kandidatbitmönstret sekvensiellt så länge som träffinformationen i deltabellerna anger träff 10 15 20 25 30 35 506 241 28 och då träffinformationen i en deltabell-anger miss eller den sista deltabellen adresserats, utvärderar utvärderings- medlet träffinformationen från de adresserade deltabellerna och då en miss framträtt i en deltabells träffinformation förkastas hela kandidatbitmönstret.

11. Anordning enligt något av patentkrav 7-10, kännetecknad därav, att genom resultatet bestämmes tidsläget för detekterade förutbestämda bitmönster i bitströmmen.

12. Anordning enligt något av patentkrav 7-11, kännetecknad därav, att de förutbestämda bitmönstren är synkroniserings- ord som används för synkronisering av en bitström mellan en sändare och en mottagare.

13. Anordning enligt patentkrav 12, kännetecknad därav, att extraktionsmedlet, adresseringsmedlet och utvärderingsmed- let innefattas i en digital signal processor.

14. System för att i en bitström (515, 615) detektera ett förutbestämt antal förutbestämda bitmönster och, inom en bestämd feltolerans, förvanskningar av bitmönstren, där de förutbestämda bitmönstren utgörs av första och andra del- bitsmönster och förvanskningarna av bitmönstren utgörs av första och andra delförvanskningar, kännetecknad därav, att nämnda system innefattar: - extraktionsmedel (520, 620, 660) som är inrättat att ur bitströmmen bilda ett kandidatbitmönster av ett förutbestämt antal bitar; - medel (520, 620, 660) inrättat att ur kandidatbitmön- stret bilda två delkandidatbitmönster; - en första och en andra deltabell (530, 640, 650) in- rättade med ett antal adresserbara positioner varvid varje position i båda deltabellerna innefattar: - träffinformation som anger träff om positionens tillhörande adress överenstämmer med något av de 10 15 20 25 506 241 29 första respektive andra delbitmönstren eller de första respektive andra delförvanskningarna och där träffinformationen anger miss i övriga posi- tioner, 4 och där varje position i den andra deltabellen även innefattar: - felinformation som, vid positioner där träffin- formationen anger träff, anger hur mycket posi- tionens adress avviker från det förutbestämda bitmönster som träffinformationen anger träff om; adresseringsmedel (520, 660) som är inrättat att först adressera den första deltabellen med det första delkandidatbitmönstret och att om miss framträder ur träffinformationen förkasta hela kandidatbitmönstret och att om. träff framträder ur träffinformationen fortsätta och adressera den andra deltabellen med det andra delkandandidatbitmönstret varvid den andra deltabellen ger träffinformation och felinformation från motsvarande position; utvärderingsmedel (540, 660) som är inrättat att ut- värdera träffinformationen från respektive delkandi- datbitmönsters adressering av respektive deltabell och därav skapa ett resultat som definierar ifall det föreligger en feltolerant detektering av något av de förutbestämda bitmönstren eller inte.