NO178088B - Fremgangsmåte og anordning for utförelse av en approksimativ divisjon - Google Patents

Description

FREMGANGSMÅTE OG ANORDNING FOR UTFØRELSE AV EN APPROKSIMATIV DIVISJON

Teknisk område

Oppfinnelsen tilveiebringer en fremgangsmåte for å ved oppdatering av et adaptivt digitalt filter utføre en approksimativ divisjon av et konstant tall med et variabelt tall i binær form, hvis verdier representerer signalenergien til et inngangssignal til filteret og som foreligger i form av elektriske signaler som representerer logiske enere og nuller, hvorved det variable tallet omfatter en tegnbit, Ni heltallsbiter og N2 binærbrøksbiter, der N1>0 og N2>0.

Oppfinnelsen viser også en anordning for å utføre en approksimativ divisjon av et konstant tall og et tall i binær form som omfatter en tegnbit, NI heltallsbiter og N2 binærbrøksbiter, der N1>0 og N2>0, omfattende en første inngang for fremskaffelse av nevnte tegnbit, N1+N2 innganger for fremskaffelse av nevnte heltallsbiter og binærbrøks-biter, en første utgang for ivaretagelse av en tegnbit og N1+N2 utganger for ivaretagelse av heltallsbiter og binærbrøksbiter.

Teknikkens stilling

Ved oppdatering av et adaptivt digitalt filter ifølge eksempelvis LMS-algoritmen (Least Mean Square), beregnes en konvergensfaktor som angir den såkalte stegstørrelsen. For at filteret skal fungere på ønsket måte for forskjellige inngangssignaler, skal stegstørrelsen være omvendt propor-sjonal med signalenergien til filterets inngangssignal. I forbindelse med beregningen av konvergensfaktoren er det derfor et behov for å utføre en divisjon av et konstant tall med et variabelt tall hvis verdi representerer signalenergien. Divisjoner er dog ofte temmelig beregningskrevende og derigjennom også temmelig tidkrevende.

Eksempelvis utføres en divisjon ifølge en kjent metode, som en serie av gjentatte såkalte betingede subraksjoner. Den absolutte nøyaktighet som oppnås på denne måten er propor-sjonal med antallet iterasjoner. Divisjoner kan også utføres ved hjelp av utstyr med temmelig stor minnekapasitet. Et eksempel på dette er beskrevet i US 4.707.798, der en apprQksimativ divisjon utføres ved hjelp av såkalte tabelloppslag i et minne i kombinasjon med interpolering.

Redegjørelse for oppfinnelsen

Et formål med foreliggende oppfinnelse er å foreslå en

fremgangsmåte hvor en divisjon av innledningsvis nevnte type kan utføres raskt og med enkelt utstyr. Dette oppnås gjennom to trinn. Først dannes et digitalt ord gjennom at eventuelle enere med lavere signifikans enn den mest signifikante

eneren til de biter som angir det variable tallets absoluttverdi erstattes med nuller. Deretter dannes i binærform et nytt tall som har samme tegnbit som det variable tallet og gjennom at bitene i det digitale ordet leses i omvendt rekkefølge.

Den divisjon som utføres ifølge denne fremgangsmåten er åpenbart ikke eksakt, men er dog tilstrekkelig bra for beregning av konvergensfaktoren ved oppdatering av adaptive filtre. Det vil f.eks. være åpenbart at en høy signalenergi gir opphav til en lav konvergensfaktor og vice versa.

Et annet formål med oppfinnelsen er å tilveiebringe en anordning av ovenfor nevnte type som er enkel i sin konstruksjon og med hvilken en approksimativ divisjon kan utføres raskt. Anordningen omfatter derved i hovedsak kun ett logisk organ som erstatter eventuelle enere med lavere signifikans enn en mest signifikant ener med nuller.

Oppfinnelsens karakteristiske trekk fremgår av patent-kravene.

Figurbeskrivelse

Oppfinnelsen vil beskrives nærmere med henvisning til tegningene, på hvilke figurene 1 og 2 er tabeller som viser eksempler på sammenhengen mellom forskjellige inngangsverdier og utgangsverdier i binær form ved utførelse av en divisjon ifølge oppfinnelsen, og i tillegg forskjellige digitale ord som dannes som et mellomtrinn ved utførelse av en sådan divisjon, og figur 3 viser et utførelseseksempel på en anordning for utførelse av en divisjon ifølge oppfinnelsen.

Foretrukket utførelsesform

I tabellen i figur 1 vises i en kolonne lengst til venstre eksempel på forskjellige tall i binær form, hvis verdier varierer mellom null og 15/16. Den første biten i hvert tall er en tegnbit og har verdien null, hvilket ifølge eksempelet innebærer at tallet er positivt. Punktet etter den første nullen er et såkalt binærpunkt og markerer at de følgende bitene har verdiene 1/2, 1/4, 1/8, og 1/16, hvilket også fremgår av figuren. De viste binære tallene har således ingen heltallsbit, men omfatter kun én tegnbit og fire såkalte binærbrøksbiter.

Ved utførelse av en approksimativ divisjon ifølge oppfinnelsen mellom et konstant tall og ett av de binære tallene i den venstre kolonnen, dannes i et første trinn et digitalt ord-av binærbrøksbitene, dvs. av de fire bitene til høyre for tegnbiten i det binære tallet. Forskjellige slike digitale ord vises i figurens mellomste kolonne. Hvert og ett av disse ord er dannet gjennom at eventuelle enere med lavere signifikans enn den mest signifikante eneren i det binære tallet erstattes av nuller. Derigjennom vil hvert av disse digitale ordene bestå av en eneste ener og tre nuller, med unnak av det nedeste ordet i tabellen som tilsvarer det binære tallet null, og som består av fire nuller.

I et andre trinn dannes et nytt tall i binær form, og forskjellige slike tall er vist i figurens høyre kolonne. Hvert og ett av de nye tallene har en samme tegnbit som tilsvarende tegn i den venstre kolonnen, og binærpunktet befinner seg på samme plass som i det tilsvarende tallet. De binære bitene etter binærpunktet tilsvarer bitene i tilsvarende digitale ord i midtkolonnen, men lest i omvendt rekkefølge.

Av tabellen fremgår det at tallet 1/16 omdannes til tallet 1/2, tallene 1/8 og 3/16 omdannes til tallet 1/4, tallene 1/4-7/16 omdannes til 1/8, tallene 1/2-15/16 omdannes til tallet 1/16 og tallet null forblir null. Med unntak av tallet null gir således et tall med relativt høy verdi opphav til et tall med relativt lav verdi og vice versa. Ifølge den beskrevne fremgangsmåten tas det kun hensyn til den mest signifikante eneren hos hvert og ett av tallene i den venstre kolonnen, hvilket får til følge at flere forskjellige inngangsverdier kan gi opphav til en og samme utgangsverdi. Fremgangsmåten kan dog ses som en approksimativ divisjon mellom et konstant tall og det binære tallet i den venstre kolonnen. For de binære tall som har kun en eneste ener, dvs. for tallene 1/16, 1/8, 1/4 og 1/2, innebærer fremgangsmåten en eksakt divisjon mellom det konstante tallet 1/32 og det aktuelle tallet. For eksempel tallet 1/16 som binært skrives 0.0001 gjelder det at dette omdannes til 0.1000, som er det samme som 1/2. Tallet 15/16 som binært skrives 0.1111 omdannes derimot til 1/16. Om denne omdannelsen skal tilsvare en divisjon med 15/16 blir telleren derved 15/(16x16) = 30/(16x32), dvs. nesten 2x1/32. Denne telleren er således nesten dobbelt så stor som den telleren som ble beregnet ovenfor, dvs. da binære tall med kun en enste ener ble betraktet. Den fremgangsmåten som legges til grunn for omdannelse av tallene kan derfor for samtlige binære tall i tabellen, med unntak av tallet null, sies å tilsvare en approksimativ divisjon av på den ene siden et konstant tall hvis verdi ligger midt mellom 1/32 og 2/32, og på den andre siden det aktuelle binære tallet.

Det har gjennomgående blitt forutsatt at de binære tallene er positive. For det tilfellet at tallet presenteres i en såkalt tegn-tallrepresentasjon, vil fremgangsmåten for omdannelse også tilsvare en approksimativ divisjon av negative tall. Med en slik representasjon vil nemlig et positivt og et like stort negativt tall skille seg fra hverajidre kun gjennom tegnbiten. Dette gjelder dog ikke ved f.eks. såkalt toerkomplementsrepresentasjon.

Ettersom divisjon med null ikke er en definert operasjon, kan omdannelsen av tallet null i prinsipp velges vilkårlig. I dette tilfellet er det ansett å være passende at tallet null gir opphav til tallet null etter omdannelse. Dette forklares av at ved oppdatering av adaptive filtre er det trolig at tallet null på omdannerens inngang er resultatet av en for øyeblikket "stille" overføringskanal. Dette skal ikke gi opphav til endret filterinnstilling.

I figur 2 vises en andre tabell med forskjellige tall i binær form. Disse tallene er de samme som tallene i tabellen ifølge figur 1, men binærpunktet har blitt flyttet to posisjoner til høyre. Tallene har derfor to heltallsbiter med verdiene 2 og 1, og to binærbrøksbiter med verdiene 1/2 og 1/4, hvilket er markert i figuren. Tallene omdannes ifølge samme prinsipp som tallene ifølge figur 1, og digitalordene i den mellomste kolonnen stemmer derfor helt overens med tilsvarende ord i figur 1. De omdannede tallene 1 kolonnen lengst til høyre, har i dette tilfellet to binære biter til høyre for binærpunktet, dvs. to binærbrøksbiter.

Omdannelsen av binære tall som kun har en eneste ener tilsvarer i dette tilfellet en divisjon av 1/2 med det aktuelle tallet. F.eks. omdannes 1/4 til 2. Tallet 3 3/4 skrives binært 011.11 og omdannes til 1/4. Dette tilsvarer en divisjon av tallet (30/16)x1/2, dvs. nesten 2x1/2, med tallet 3 3/4. For de binære tallene i tabellen ifølge figur 2 tilsvarer fremgangsmåten for omdannelse således en approksimativ divisjon av et konstant tall, hvis verdi ligger omtrent midt mellom 1/2 og 1, og det aktuelle binære tallet. Som før utgjør tallet null et unntak, ettersom dette tallet ikke forandres i det hele tatt.

I figur 3 vises et utførelseseksempel på en anordning for utførelse av en approksimativ divisjon av ovenfor angitte type*- Anordningen har fem innganger 10-14 og fem utganger 50-54. Inngangen 10 er sammenkoblet med utgangen 50 og er reservert for tilførsel av tegnbiten i et inngangstall i binær form. således vil tegnbiten føres uforandret fra inngangen 10 til utgangen 50. Til inngangene 11-14 føres etter tur inngangssignalets mest signifikante bit, nest mest signifikante bit, osv. Inngangene 11-14 er tilkoblet til et logisk organ 20 med utganger 21-24. Det logiske organet vil bli beskrevet nærmere nedenfor og har til hensikt å finne den mest signifikante eneren på inngangene 11-14 og å erstatte eventuelle enere med lavere signifikans med nuller. På utgangene 21-24 fremskaffes således de digitale ord som er vist i midtkolonnene i figurene 1 og 2.

Utgangene 21-24 fra organet 20 er tilkoblet anordningens utganger 51-54 gjennom at utgangen 21 er koblet til utgangen 54, utgangen 22 til utgangen 53 osv. Derigjennom vil bitene i det digitale ordet fra organet 20 opptre i omvendt rekkefølge på anordningens utganger 51-54. Tegnbiten på utgangen 50 og bitene på utgangene 51-54 vil således danne de binære ord som vises i de høyre kolonnene i figurene 1 og 2. -

Organet 20 består i det viste eksempelet av et portnett som inneholder fire OG-porter 31-34 og to ELLER-porter 41-42 og som er anordnet for omdannelse av binære tall som har fire binære biter i tillegg til tegnbiten. En inngang 15 og en utgang 25 er reservert for såkalte carrybiter, som benyttes ved eventuell kaskadekobling av flere portnett av den viste typen. Dette gir mulighet for å omdanne binære tall med flere biter enn fire. Om portnettet ikke er kaskadekoblet med et lignende nett for biter med høyere signifikans enn den på inngangen 11, tilføres carryinngangen 15 en logisk null.

En null på carryinngangen 15 holder porten 31 åpen for en eventuell ener på inngangen 11 for den mest signifikante biten i et binært tall som tilføres nettet. Om den mest signifikante biten er en ener, vil det derfor foreligge en ener på utgangen 21 til porten 31. Eneren på inngangen 11 forårsaker i tillegg at en null foreligger på en negert utgang ved porten 41, og denne nullen sperrer portene 32-34 slik at nuller foreligger på utgangene 22-24 uavhengig av om enere eller nuller foreligger på inngangene 12-14. Hvis den mest signifikante biten i stedet er en null, foreligger en null også på utgangen 21, og en ener vil foreligge på utgangen ved porten 41. Denne eneren holder porten 32 åpen for en eventuell ener på inngangen 12 for det binære tallets nest mest signifikante bit. En ener på inngangen 12 vil samtidig sperre portene 33 og 34 slik at nuller vil foreligge på utgangene 23 og 24.

Om tallets mest signifikante ener foreligger på inngangen 13, vil det foreligge en ener på utgangen 23 og porten 34 holdes sperret. En ener vil foreligge på utgangen 24 kun dersom nuller foreligger på inngangene 11-13 samtidig som en ener foreligger på inngangen 14.

Om en ener foreligger på minst én av inngangene 11-14, foreligger en ener på carryutgangen 25. Om en ener foreligger på carryinngangen 15 sperres portene 31-34, hvilket gjør at nuller foreligger på samtlige utganger 21-24 og i tillegg på carryutgangen 25.

De enere og nuller som omtales i bestrivelsen ovenfor utgjøres naturligvis i praksis av forskjellige elektriske signaler som representerer slike logiske verdier.

Claims (3)

1 . Fremgangsmåte for å ved oppdatering av et adaptivt digitalt filter utføre en approksimativ divisjon av et konstant tall med et variabelt tall i binær form, hvis verdier representerer signalenergien til et inngangssignal til filteret og som foreligger i form av elektriske signaler som representerer logiske enere eller nuller, hvorved det variable tallet omfatter en tegnbit, N1 heltallsbiter og N2 binærbrøksbiter, der N1>0 og N2>0, karakterisert ved at de signaler som representerer bitene (11-14) i det variable tallet, med unntak av det signalet som representerer tegnbiten, benyttes for å danne signaler som representerer biter i et digitalt ord (21-24) ved at signaler som representerer eventuelle enere i bitene (11-14) i det variable tallet med lavere signifikans enn den mest signifikante eneren erstattes av signaler som representerer nuller, og at det dannes signaler som representerer et nytt tall i binær form hvis tegnbit (50) stemmer overens med det variable tallets tegnbit (10) og hvis øvrige biter (51-54) stemmer overens med bitene i det digitale ordet (21-24), men lest i omvendt rekkefølge (24-21), og at med unntak av det signalet som representerer tegnbiten vil de signaler som representerer de NI første bitene i det nye tallet representere heltallsbiter og de signaler som representerer de N2 gjenstående bitene representere binærbrøksbiter.

2. ' Fremgangsmåte ifølge krav 1, karakterisert ved at i tilfelle av at ingen av de sinaler som benyttes for å danne signaler som representerer biter i det nevnte digitale ord (21-24) representerer en ener, vil det nevnte digitale ord bestå av kun nuller.

3. Anordning for å utføre en approksimativ divisjon av et konstant tall og et tall i binær form som omfatter en tegnbit, N1 heltallsbiter og N2 binærbrøksbiter, der NI>0 og N2>0, omfattende en første inngang (10) for fremskaffelse av nevnte tegnbit, N1+N2 innganger (11-14) for fremskaffelse av de nevnte heltallsbiter og binærbrøksbiter, en første utgang (50) for fremskaffelse av en tegnbit og N1+N2 utganger (51-54) for fremskaffelse av heltallsbiter og binærbrøksbiter, karakterisert ved et logisk organ (20) som omfatter N1+N2 innganger (11-14) som er forbundet ved anordningens nevnte N1+N2 innganger (11-14), og N1+N2 utganger (21-24), og som er anordnet for, når et første digitalt ord foreligges på inngangene, å danne et andre digitalt ord som stemmer overens med det første digitale ordet med unnak av at eventuelle enere som er mindre signifikante enn den mest signifikante eneren er erstattet av nuller, og videre ved at nevnte første utgang (50) er forbundet med nevnte første inngang (10) og at nevnte N1+N2 utganger (51-54) i anordningen er forbundet med nevnte NI+N2 utganger (21-24) i det logiske organet (20) på en slik måte at den utgang (24) i det logiske organet som er reservert for en minst signifikant bit i det nevnte andre digitale ord er forbundet med den utgang (51) som er reservert for den mest signifikante biten av de heltallsbiter og binærbrøks-biter som fremskaffes på anordningens utganger, og ved at den utgang (23) i det logiske organet som er reservert for en nest minst signifikant bit er forbundet med den utgang (52) i anordningen som er reservert for den nest mest signifikante biten av heltallsbitene og binærbrøksbitene på anordningens utganger, osv.