SE515807C2 - Metod och arrangemang för beräkning av en diskret Fouriertransform - Google Patents

Description

25 30 (fl _; m co c: -1 . - ~ Q m Beskrivning av besläktad teknik.

Kretsar för beräkning av FFT med hjälp av olika tekniker är kända från flera dokument.

US 5 163 017 offentliggör till exempel en pipelinead FF T-arkitektur som innefattar ett minne för lagring av data i form av komplexa tal. En pipelinead dataväg är kopplad till ett minne för att komma åt data i form av komplexa tal från detta för beräkning av en FFT butterfly-operatör och lagring resultaten från butterfly-operatom i minnet under en pipeline-cykel. Ändamålet enligt detta dokument är att minska antalet minnesåtkomster för en butterfly-operator. Inget stöd ges för parallella butterfly-operatorer.

Dessutom offentliggör US 5 028 877 ett arrangemang av kretsar för att genomföra en snabb DF T i realtid genom att använda kontrollerade operationer av tvärlänkade butterflies.

Arrangemanget överför successivt två hälfter av en sekvens av ett komplext inmatningsord genom ett serieparallellt inmatningsregister och en interrnediär datalagring till ett flertal butterfly- operatorer som fungerar parallellt. Utmatningarna från operatörerna är omkopplingsbara med hjälp av en multiplexenhet för upprepad förbindelse med den intennediära lagringen, eller för att leverera utmatningsordet för frekvensomfång till ett serieparallellt utmatningsregister. Även om parallella butterfly-operatorer används i enlighet med detta dokument, är lösningen inte flexibel eftersom FF T-längden alltid är bestämd till 16 punkter och inte kan ändras. Arrangemanget använder sig av pipelineteknik, och inte minnesarrangemang, för intermediär lagring av resultat.

Dessutom består hela sekvensen av inmatningsord som utsätts för FFT av fyra gånger fler värden än antalet tillhandahållna butterfly-operatorer. Dessutom tas ingen reduktion av minnesåtkomster upp.

Andra arrangemang som inte använder sig av parallella butterfly-operatorer och reducerat antal minnesåtkomster presenteras i EP-Al-805 401 och US 4 601 006, där den senare i huvudsak beskriver en pipelinearkitektur för tvådimensionell FFT.

Sammanfattning av uppfinningen.

Huvudändamålet med den föreliggande uppfinningen är att tillhandahålla ett flexibelt arrangemang för snabb beräkning av FFT-algoritmen. 10 15 20 25 30 m -å en co c:- ~a u | - - I " 3 Ett annat huvudändamål med uppfinningen är att tillhandahålla ett snabbt och flexibelt arrangemang för beräkning av FFT, i vilket FFT-längden kan bestämmas och ändras utan behov av att modifiera arrangemanget.

Ett ändamål med uppfinningen är också att tillhandahålla ett arrangemang för beräkning av FFT, vilket är lämpligt för att genomföras med hårdvara; d. v. s. det är mindre komplext.

Arrangemanget i enlighet med uppfinningen tillhandahåller en ny minneskonfiguration, adressgenerering och datakontroll vid beräkningar av F F T, vilket tillåter uppdelning av minnesuppsättningar i mindre enheter, vilket möjliggör färre minnesåtkomster per minnesuppsättning.

I arrangemanget enligt inledningen är butterfly-operatorerna följaktligen arrangerade parallellt och m minnesenheter är arrangerade vilket tillåter 2r åtkomster per minnesenhet under varje beräkning. För att åstadkomma flexibilitet använder arrangemanget företrädesvis en parameter för variabel F FT-längd, i vilken längden av F F T är rLMODE, och där LMODE 2 m + 1. I ett fördelaktigt utförande som använder sig av nonnal bitlagring är antalet minnesenheter 2m och minnesuppsättningama är svängande minnen.

Företrädesvis är minnesstorleken för en minnesuppsättning FFT-längden dividerad med antalet butterfly-operatorer.

I ett föredraget utförande innefattar arrangemanget dessutom medel för att generera adresser och första och andra styrmedel kopplade till nämnda minnesuppsättningar.

Medlet för generering av adresser består av en tillståndsmaskin, vilken antar olika tillstånd som representerar val av olika minneskonfigurationer i nämnda minnesuppsättningar, där åtminstone ett av nämnda tillstånd arrangerar åtminstone en minnesuppsättning som ett inmatnings / utmatningsminne och en minnesuppsättning för att ta emot data från åtminstone en av nämnda butterfly-operatorer. Tillståndsmaskinen är företrädesvis ordnad för att anta sex olika tillstånd.

För att styra adresseringen av minnena innefattar det första och andra medlet för minnesstyrning omkopplingsanordningar som styrs av nämnda medel för generering av adresser, där omkopplingsanordningarna innefattar multiplexenheter. Det första medlet för styrning av minne, vilket innefattar multiplexenheter som är kopplade mellan butterfly-operatorernabch minnesuppsättningama, är ordnat för att koppla om data från korrektaminnesuppsättningar, och det andra medlet för minnesstyming är ordnat för att koppla om data till korrekta minnesuppsättningar. Det andra medlet för minnesstyming innefattar en styrsignalkrets, en I/O -krets och anordningar för omkoppling, där nämnda signalkrets och I/O -krets är kopplade till 10 15 20 25 30 »_ ÉÅÉ ÛÛÛ Ü|äf uu, . » - . .- 4 nämnda medel för omkoppling, och styrs av nämnda medel för generering av adresser.

Företrädesvis innefattar minnesuppsättningarna fyra lagringsmedel av typen SRAM (Static Random Access Memory).

Uppfinningen hänför sig också till en anordning för beräkning, i huvudsak för beräkning av diskreta Fouriertransforrner med användning av Fast Fourier Transform (FF T) på en uppsättning av data. Anordningen innefattar m bas-r butterfly-operatorer, uppsättningar av dataminnen inklusive minnesenheter och medel för omkoppling. Anordningen innefattar dessutom: butterfly- operatorema ordnade parallellt, m minnesenheter, ett styrblock vilket styr och övervakar anordningens funktioner, en generator av tWiddle-koefficienter för att generera twiddle- koefficienter till nämnda butterfly-operatorer, enheter för styrning av minnesdata för att styra dataflöden till / från minnesuppsättningama, medel för att ta emot en FFT-längd för en FFT- beräkning och en enhet för minnesstyming för att styra funktionen av minnesenhetema. I ett utförande innefattar anordningen dessutom styrmedel för inmatningsdata för att behandla inkommande data, styrmedel för utmatningsdata för att behandla utgående data, och förbehandlingsmedel ordnade för att behandla data före FFT. Företrädesvis kan anordningen tillämpa både FFT och I FFT (Inverterad FF T) på data. Den innefattar även ett behandlingsmedel som utför operationer på data i frekvensdomänen, och medel för efterbehandling före utmatning.

Anordningen är ordnad så att data läses från en minnesuppsättning och skrivs tillbaka till en annan.

Metoden i enlighet med uppfinningen innefattar i huvudsak stegen att ordna butterfly- operatorema parallellt och ordna m minnesenheter vilket tillåter 2r minnesåtkomster per minnesenhet under varje beräkning. I enlighet med metoden lagras data i normal eller bitreverserad ordning i minnet. F FT-beräkningen består av ett antal beräkningsfaser, och riktningen av dataflödet kastas om efter varje fas.

Dessutom styrs dataflödet till minnesuppsättningama av olika konfigurationer för att bestämma ett mönster för användning av omkopplingsmedlet med avseende på signalerna STEP, LAP och NFFT = FFT längd = rLMODE, LMODE 2 m + 1, vilka tas emot från en styranordning.

Metoden för konfigurering innefattar stegen att: bestämma en första konfiguration för det första omkopplingsmedlet om STEP är noll och' LAP är jämnt, bestämma en andra konfiguration för det första omkopplingsmedlet om STEP är noll och LAP är ojämnt, bestämma en tredje konfiguration för det första och andra medlet för omkoppling om STEP är LMODE - 2, bestämma en fjärde konfiguration för det första och det andra medlet för omkoppling om STEP är LMODE - 1. I 10 15 20 25 30 m .à en (b c: ~4 | ø ~ v n 5 enlighet med metoden är ordningen för beräkning av butterfly-operatorerna mindre än två dataavläsningar / inskrivningar från / till 2-ports minnesenheter vid varje beräkningssteg.

Dessutom styrs dataflödet till minnesuppsättningama med hjälp av styrmedel som genererar signaler för minnenas hantering av data till och från butterfly-operatorema. Metoden innefattar stegen att: ta emot inmatningar, LAP, vilket är beräkningsstegets index, STEP vilket är föreliggande beräkningssteg, kontrollera LAP och om LAP är noll initieras ett sling-index som bildarinläsningskommandon till nämnda minnesuppsättningar och bildar skrivkommandon till nämnda minnesuppsättningar. Om LAP är skilt från noll bildas andra uppsättningar av skriv- och läskommandon. Om data föreligger i reverserad bitordning och inläsningsadressema är samma som skrivadresserna kommer nya läs / skrivkomrnandon att bildas.

Kortfattad beskrivning av ritningarna.

I det följ ande kommer uppfinningen att ytterligare beskrivas under hänvisning till de medföljande ritningama i vilka: F ig. 1 är ett schematiskt blockdiagram av ett första utförande av ett arrangemang i enlighet med den föreliggande uppfinningen.

F ig. 2 visar ett annat schematiskt utförande i enlighet med Fig. 1 i mer detalj.

Fig. 3 är en schematisk bild av DC-block i enlighet med F ig. 2.

Fig. 4 är en schematisk bild av IDC / ODC -block i enlighet med Fig. 3.

Fig. 5 är en schematisk bild av MDCU-O -block i enlighet med Fig. 2.

Fig. 6 är ett schematiskt flödesschema över fiinktionen av ett styrblock i enlighet med Fig. 5.

F ig. 7 är en schematisk bild över MDCU-I -block i enlighet med Fig. 2. 10 15 20 25 30 51-5 807 . « . t | - 6 Fig. 8 är ett tillståndsdiagram för ett styrblock MCU i enlighet med F ig. 2.

Fig. 9 är en schematisk bild av MU-block i enlighet med Fig. 2.

F i g. 10 illustrerar schematiskt ett annat utförande i enlighet med uppfinningen.

Detaljerad beskrivning av utfóringsexemplen I korthet använder sig den föreliggande uppfinningen av flera butterfly-operatörer för FFT- beräkningarna. Det är möjligt genom delning av minnesuppsättningar (som var och en innefattar ett antal minnesenheter) med hjälp av en ny minneskonfigurering, adressgenerering och inkoppling av dataflöde. Genom att till exempel använda "svängande" minnen är det till exempel att erhålla 8 minnesuppsättningar med 2 minnesåtkomster under varje beräkningscykel, istället för 2 minnesuppsättningar med 8 åtkomster. Utan svängande minnesuppsättningar skulle antalet minnesåtkomster per minnesenhet naturligtvis öka.

De huvudsakliga förbättringama åstadkoms med hjälp av en ny sorts datastyrning och minneskonfigurering. I det första steget lagras datai en minnesuppsättning som skall läsas från.

Sedan utförs en FF T-beräkning i ett antal steg. Om svängande minnen används byter data plats mellan minnena genom ändring av "skriv" och "läs" -kommandona till minnena. Under varj e steg utför butterfly-operatorema beräkningar. Serienumret för varje beräkningscykel, den bestämda FFT-längden och numret på steget som skall beräknas används som inmatningsdata för att bilda minnesadresser och för att styra data. Följaktligen är det möjligt att förändra FF T-längden från beräkning till beräkning för att erhålla bästa möjliga resultat, om till exempel bas-r -butterfly- operatom används så är de möjliga FF T-längdema rx, där x är större än eller lika med log2 (antal minnesenheter som används) + l.

I ett icke begränsande utförande som skall beskrivas närmare i det följande, läses 8 data från en del av minnesuppsättningen medan 8 data skrivs till den andra delen av j minnesuppsättningen. I detta fall används 4 minnesenheter med datainmatníngar ( minne med 2 portar [imnatningar / utmatningar]). Minnesstorleken för en rninnesuppsättrring som har 2 datainmatningar är FF T-längden dividerad med antalet butterifly-operatorer. Basen för beräkningsordningen för butterfly-operatorema är att undvika mer än 2 läsningar/ skrivningar av data från / till varje 2-portsminne under varje beräkningssteg. 10 15 20 25 30 5151807 7 Data som läses från en sida av minnesuppsättningama uppträder i en speciell ordning som beror på beräkningssteget, FFT-längden och typen av beräkningar som måste utföras. Detta åstadkoms med hjälp av arrangemang för omkoppling, vilket kopplar om data till en korrekt butterfly-operator och sedan tillbaka till den ordning i vilken data skrivs till minnet.

Arrangemanget i enlighet med den föreliggande uppfinningen, i det följ ande benämnt P3FTD (Parallell Flexible Fast Fourier Transform Device) 10, illustreras schematiskt i Fig. 1.

P3FTD innefattar butterfly-operatorer (BO) 11.1 - 11.4, minnesuppsättningar (MS) 12, anordning för generering av adresser MCU 13, styrenhet 14 för inmatningsdata 14 (IDC), styrenhet för utmatningsdata 15 (ODC), en generator av tvviddle-koefficienter 16 och styrenheter 17 och 18 för dataflöde. P3F TD 10 kan dessutom innefatta inmatníngs- och utmatningsbuffertar 28 respektive 29, till exempel i fonn av FIFO (First In First Out) -mínnesenheten Den nya centrala delen av uppfinningen innefattar emellertid minnesblocken 12, den adressgenererande anordningen MCU 13 och styrenheterna för inmatnings / utmatningsdata 14 och 15 och parallella butterfly- operatorer.

Ett föredraget utförande av P3F TD så som den kan vara genomförd i en integrerad krets visar i mer detalj i blockdiagrammet i Fig. 2. Av tydlighetsskäl visas endast vissa interna signaler.

Pilar som ej är fyllda anger styrsignaler.

Den arkitektur som används bygger på fyra (4) bas-2 BO, vilka är lokaliserade till databeräkningsblocket (DC) 11. Data läses från en rninnesuppsättning (MSO, MS1, MS2) 12.1 - 12.3 och skrivs tillbaka till en arman (MSO, MS1, MS2) efter en butterfly-operation. FFT- beräkningen består av ett antal beräkningsfaser. Datariktningen kastas om efter varje fas. En av MS används för lagring av data, i huvudsak för samtidig inmatning / utmatning.

De fyra BO är försedda med twiddle-koefficienter från TG 16. När data läses från MS, uppträder den inte i korrekt ordning för återlagring i MS efter butterfly-operationen. Styrenheterna för minnesdata MDCU-I 17 (inmatning) och MCDU-= 18 (utmatning) styr dataflödet till/ från minnesuppsättningarna. De olika MS "byter plats", d. v. s. data läses och skrivs inte till samma MS, vilket hanteras av MDCU-l 17, MDCU-I 18. Funktionen av dess kretsar styrs dessutom av en minnesstymingskrets (MCU) 13. En ytterligare minnesuppsättning, ICM, 20 används för att förvara några styrparametriar, såsom filter och fönsterkoefficienter vilka används för butterfly- operationer.

Utförandet tillhandahålls av flera andra styrblock: inkommande data som ska behandlas hanteras först av IOLC 21, som kan vara en del av inmatningsbufferten 28, och utmatningsdata 10 15 20 25 30 515 897 Q s ~ i H 8 hanteras av blocket DOC 22, vilket kan vara en dela av utmatningsbufferten 29. Dessutom är blocket PRE 23 ordnat för att behandla data innan FF T i DC-blocket 11.

I ett föredraget utförande är det möjligt att tillämpa både FF T och I FF T (inverterad F FT) på data. I detta fall utför ett block FDO 24 operationer på data i frekvensdomänen. Resultaten behandlas av en efterbehandlingsenhet POST 25 före utmatning.

Blocket CONTROL 26 är en inre eller yttre styrenhet som styr och övervakar i stort sett alla funktioner i P3FTD. Om denna tillhandahålls intemt kan den också hantera kommunikation med extern(a) styrenhet(er). Ytterligare ett styrblock, PROC 27 kan ordnas, vilket är ett övervakande block som styr funktionerna i DC 11, MDCU-l 17, MDCU-O 18, TG 16 och eventuella FFT / IFFT -funktioner.

I det följande kommer de olika blocken som illustreras i Fig. 2 att beskrivas närmare.

CONTROL 26.

CONTROL 26 består företrädesvis av en tillståndsmaskin som i huvudsak styr alla funktionerna i P3FTD och en eventuell kommunikationssektion, vilken hanterar kommunikationen med extema styrenheter. Styrsignalerna från detta block kommer att beskrivas i anslutning till beskrivningen av de återstående blocken.

CONTROL -blocket innefattar också ett register till vilket de FF T-längder som används för beräkningarna överförs. FFT-längden är en applikationsberoende variabel och kan erhållas från yttre arrangemang för styming, till exempel en behandlingsenhet för en radannottagare eller en processenhet för en videosignal.

IOLC 21.

Blocket IOLC 21 är ordnat för att läsa data från inmatningen, vilken kan vara en buffert eller ett register (företrädesvis FIF O), och att skriva den till dataminnet MS, vilken i det ögonblicket är konfigurerad som 1/ O -minne av MCU 13. IOLC 21 är genomförd i form av en tillståndsmaskin som styr externa FIF O ( visas ej) kopplade till inrnatningsporten. Den producerar data till PRE 23. Den initieras av CONTROL 26. Data tas emot i satser. Företrädesvis är operationen "Read" från F IF O möjlig vid klockfrekvenshastighet.

DOC 22.

Blocket DOC 22 (Data Output Controller) är ordnat för att sända data till utmatningsbuffertarna, vilka kan genomföras i form av FIFO. Företrädesvis innehåller blocket en 10 15 20 25 30 f 515 807 .m u: 9 synkron intern FIFO för att läsa data (delar av data eller en datarubrik). En styrenhet, företrädesvis genomförd i form av en tillståndsmaskin, läser data från de interna dataminnena och skriver till den externa utmatningen (FIFO). Blocket kan också innefatta en anordning för att omvandla data till olika former (parallell / seriell) eller protokoll som kan tas emot av yttre enheter.

Utmatningsdata tas emot från POST 25 och skrivs till ett F IF O (visas ej). DOC 22 läser data genom att sända adresser (datalokalisering) till MDCU-O 18. Utmatningsadressen till MDCU-O uppdateras och kommunikation mellan MDCU-O och ODC aktiveras av en uppdateringssignal. För att ta emot data från MDCU-O 18 till DOC 22 aktiveras en initieringssignal och DOC uppdateras varje cykel till dess att en signal 'data giltig” tas emot från POST 25. Åtminstone delar av data (första bytes) skrivs till en utmatnings-F IF O (visas ej). Sedan uppdateras DOC och signaler för inkoppling initieras innan nästa uppsättning data är giltig vid inmatningen. Denna procedur upprepas till dess att den sista uppsättningen har skrivits till OF IFO.

När den sista adressen har sänts till MDCU-O kopplas signalerna 'adress giltig' ur. Den sista datauppsättningen upptäcks när en 'data giltig' -signal från POST 25 kopplas ur. Om OFIFO- signaler fiilla eller en väntesignal är aktiva görs ett uppehåll i skrivningen till OFIFO.

PRE 23.

Som nämns ovan utför blocket PRE 23 (PRE-processing) operationer på data före FFT/ IFF T -beräkningarna Det beräknar komplexa värden innefattande multiplikationsoperationer etc.

FDO 24.

Blocket F DO 24 (FrekvensDomänOperator) utför operationer på data i frekvensdomänen mellan FFT / IFFT -operationema.

ICM 20.

Blocket ICM 20 är en minnesuppsättning som innehåller parametrar för filtrering, tönsterkoefficienter etc. En yttre processor eller inre enheter kan komma åt detta minne för att hämta eller ändra parametrama. ICM har följ ande driftlägen: Externt skrivläge FDO skrivläge PRE läsläge l ett föredraget utförande består ICM av ett 4096 x 32 synkront SRAM, med en dubbelriktad databuss med gemensam inmatning och utmatning. Skrivsignalen styr databussens riktning. 10 15 20 ; | . v I ~ POST 25.

Blocket POST 25 utför de slutliga operationerna på data innan resultatet levereras från P3F TD. POST 25 innefattar till exempel medel för att utföra funktioner såsom skalning, avrundning och klippning.

DC11.

Blocket DC 11 är huvudblocket för Signalbehandling i P3FTD och i detta utförande, som visas i detalj i Fig. 3, består det av 4 bas-2 butterfly-operatorer (BO) 11.1 - 11.4, styrenhet för flödet av inmatningsdata IDC 14, styrenhetema för flödct av utmatningsdata ODC 15, styrenhet (CU) 30 och fördröjningselement 31 och 32.

F ördröjningselementen är ordnade för att kompensera styrsignaler för fördröjningar i DC 11. IDC 14 och ODC 15 utför omkopplingen av data och CU 30 bland andra styr enfasberälmingar.

Arkitekturen för IDC 14 och ODC 15 är illustrerade i Fig. 4. Båda blocken är identiska och består av flera multiplexenheter 40 - 47 där första och sista MUX, 40 respektive 47, i denna konfiguration har två datainmatningar medan de återstående MUX har fyra inmatningar.

Inmatningsdata till IDC 14 har sitt ursprung i MDCU-O 18. Det finns 8 inmatningssignaler IDCO, ..., IDC7 som innefattar komplexa signaler (reella och imaginära). Utmatningama från IDC 14 är inmatningar till BO 11.1 till 11.4 och noteras som BOnIi, där n är BO-numret och i ( i = 0 eller 1) är signalnumret. BOII, betyder inmatningsdata till BO 1 (11.1) inmatning 1. Inmatningar till ODC 15 är utmatningar från BO 11.1 till 11.4, och därför betyder, analogt med ovanstående BOnO, utmatningar från BO nr n (1 1.n = 1, ..., 4) och signal nr i (i = 0 eller 1).

Inmatningssignaler till inmatningarna i MUX (MUXO - MUX7 motsvarande MUX 40 - 47) listas i tabell 1. .ø» R C _- ! 7 I i.. ”_ s . w I U U U I :__ U, : ,.. 1 1 Tabell 1 Iyrtjxo _ "MUXI _ MUX: a , 'MUx4 » Muxs Mvxe fMUXv* 5 o IDC, IDC, IDC, IDC, IDC, IDC, IDC, IDC, _ 30,0, 30,0, 30,0, 30,0, 30,0, 30,0, 30,0, 30,0, I I ~ , IDC, IDC, IDC, IDC, IDC, IDC, IDC, IDC, 30,0, 30,0, 30,0, 30,0, 30,0, 30,0, 30,0, 30,0, 10 IDC, IDC, IDC, IDC, IDC, IDC, i ; 30,0, 30,0, 30,0, 30,0, 30,0, 30,0, i 11 IDC, IDC, IDC, IDC, IDC, IDC, i 30,0, 30,0, 30,0, 30,0, 30,0, 30,0, 10 Utmatningar från MUX till nästa block listas i tabell 2.

Tabell 2 :MUxo I MUXI MUxz Muxs MUx4 MUxs Muxs MUX? 0DC, 0DC, 0DC, 0DC, 0DC, 0DC, 0DC, 0DC, 0DC, 15 30 30,I, 30,1, 30,I, 30,I, 30,I, 30,I, 30,I, 30,I, Styrsignaler till IDC 14 och ODC 15 är index for inmatningsdata från MDCU-I (fördröjd till ODC) och styrsignaler från blocken CONTROL och PROC.

Utmatningen från varje MUX bestäms i enlighet med tabell 3. I tabell 3 visar kolumnerna 2 20 kolumnen frånvänster). Det finns 6 uppsättningar av styrmönster för MUX. - 8 MUX-inmatningalna, utvalda med ledning av styrorden (konfigurationer) 0 - 5 (första 10 15 515 807 ' Tabell 3 1 01 01 00 ll 10 10 0 0 00 11 10 01 00 ll 1 1 10 10 ll 00 01 01 O 1 ll 01 11 00 10 OO 0 1 01 10 01 10 01 10 0 1 10 00 00 ll ll 01 0 Med utgångspunkt från tabell 3 framgår det att styrsignalerna till MUX4 - MUX7 är inverterade och reverserade signaler från MUXO - MUX3, vilket faktum förenklar styrningen av MUX ytterligare.

Styrorden 0 - 5 (den första kolumnen i tabell 3) vilka avgör vilket mönster som skall användas i IDC och ODC med avseende på utmatningssignalerna STEP och LAP anges i tabell 4. 10 20 25 30 m .à en co c: -1 .n s== 13 Tabell 4 ., __ .STEP=0, LAP(0)=O 0 3 STEP=0, LAP(0)=1 1 3 STEP=LMODE-2 2 2 STEP=LMODE-1 4 5 annars 3 3 STEP är det pågående F FT-beräkningssteget mellan 0 och log2 (NFFT) - 1, LAP är index för beräkningssteg (räknare för beräkningscykler) mellan 0 och NLAP - 1 (antal varv), NFFT är FFT-längden, i detta exempel 8 upp till 4096, NLAP = NFFT / 8 och NMODE är läget för FFT- längden, erhållet från CONTROL. En beräkningscykel är en en-butterfly-beräkning utförd av varje BO.

Från tabell 4 framgår att: om STEP är 0 (noll) och LAP är jämn så bestäms konfigurationen 0 för IDC, om STEP är 0 (noll) och LAP är udda så bestäms konfiguration 1 för IDC, om STEP är LMODE - 2 så bestäms konfiguration 2 för IDC, om STEP är LMODE - 1 så bestäms konfiguration 4 för IDC och konfiguration 5 för ODC, i annat fall bestäms konfiguration 3 för både IDC och ODC.

BO 11.

I F ig. 3 är varje BO en bas-2 butterfly-enhet. en bas-2 butterfly tar två komplexa inmatningar och en komplex twiddle-koefficient (WO - W3) och framställer två komplexa utmatningar Twiddle- koefficienten beror på butterfly-positionen i beräkningsschemat. Funktionen av butterfly- operatom antas vara känd av en person med erfarenhet inom området och beskrivs inte nämnare här.

TG 16. 10 15 20 25 30 C112 (H17 v09 VU! . . . - n 14 Blocket TG 16 beräknar butterfly tWiddle-koefficienterna för var och en av de fyra parallella butterfly-enhetema. TG 16 innefattar en krets för att bilda indexvärden, vilka är beroende av vilken butterfly som skall beräkna beräkningsschemat för FFT. Dessutom innefattar TG en krets för att bilda twiddle-koefficientema WO, Wl, WZ och W3. BO som skall beräknas under varje fas och varv ges av 4 indexvärden som beräknas i enlighet med följ ande metod. De fyra komplexa tWiddle-koefficienterna beräknas sedan som: W(n) = EXP (j * 2 * p * D * INDEX (n) / 211 *STEWL där j är den imaginära delen av data och D är riktningen för FFT, och INDEX (n) = n * NLAP + LAP + dçsriaP) * (n MoDULUs 2) * (NLAP - 2 * LAP - 1) d är Kroneckers deltafunktion, definierad som: d(x) = 0, x 1 O; och d(x) = 1, x = 0.

STEP, NLAP och LAP definieras ovan.

CU 30.

CU 30 är en tillståndsmaskin som producerar indexvärden till IMC 20, vilken beräknar adresserna till minnesuppsättningar. Data passerar genom ODC och anländer vid DC, sedan beräknas den och matas till IDC för att lagras i en arman MS.

MS 12.

En minnesuppsättning, MS, 12 visas i detalj i Fig. 9. Åtminstone 3 MS 12.1 - 12.3 ordnas, där en fungerar som I/ O -minnet. MS 12 i detta utförande består av 4 minnesenheter, här 4 SRAM (Static Random Access Memory) med dubbelport 90 - 93. lnrnatningsdata till DINO och DINl-porten i varje SRAM 90 - 93 levereras från datautmatningar från MDCU-O 18 och utmatningar från varje SRAM, DOUTO och DOUTl är kopplade till datainmatningar i MDCU-1 17. Styrsignalerna (adress och skrivsignaler AO, WEO, A1 och WEl) levereras från MDCU-O 18.

MDCU-O 18.

Huvudfunktionen för MDCU-O 18 är att koppla om data och adresser till korrekta minnesuppsättningar och minnespositioner. Ett något detalj erat utförande av MDCU-O visas i 10 15 20 25 30 C12 007 vnv vv! :u n» 15 Fig. 5. I allmänhet består MDCU-O av en styrsignalkrets (RW) 50, en I / O -krets (IO) 51 och MUX 52 - 54.

IO 51 bildar I / O -adressvektorer och dess utmatningar är inmatningar till inportarna i MUX 52 - 54 (port 2). Inmatningaina till IO 51 har sitt ursprung i DOC 22 och PRE 23, och innefattar till exempel läs- och 'data giltig” -signaler.

De återstående in-portarna (0, 1) i MUX är kopplade till utmatningar från RW 50 och försedda med läs / skrivsignaler som skall sändas till MS. MUX urvalssignaler till varje MUX har sitt ursprung i MCU 13. Utmatningar från MUX 52 - 54 är kopplade till MS 12.1 respektive 12.3, för omkoppling av adressvektorer, data, läsadress och adressindex.

RW 50 bildar signaler för datahantering av minnen till och från DC 11.

Inmatningssignalerna till denna krets innefattar data och datastymingssignaler från DC 11 och FDO 24. Styrsignalerna som matas ut till MUX 52 - 54 för att styra läsning och skrivning från MS bildas i enlighet med det flödesdiagram som visas i F ig. 6.

Proceduren har följande inmatningar: NFFT FFT-längden, till exempel 8 till 4096, antal FFT, LAP vilket är index för beräkningssteg mellan 0 och NLAP - 1, och STEP vilket är STEP- index mellan 0 och log2 (NFFT) - 1.

Det har även ordnats hjälpvariabler, 62, N = log2 (NF FT) - 3, S = 6 - N och NLAP = NFFT / 8, 61.

Under beräkningen av ett FFT STEP, utför NFFT / 2 butterfly-operationer varje STEP.

Det finns 4 BO. Därför ar antalet varv (NLAP) NFFT / 2 / 4.

Proceduren returnerar utmatningarna: W00, W0l, Wl0, Wl 1, skrivadresser, och R00, RO1, R10, Rll och läsadresser.

Första index anger adresser för port 0 eller 1 på SRAM 90 - 93, medan andra index anger om adresserna är avsedda för SRAM 90 och SRAM 92 (index = O) eller för SRAM 91 och SRAM 93 (index = 1). W0l är till exempel skrivadressen till port O på SRAM 91 och SRAM 93, R10 är läsadressen till port 1 på SRAM 90 och 92.

I enlighet med proceduren kan beräkningarna, om data föreligger i bitreverserad ordning i minnet, utföras "på plats"-och strukturen med "svängande minnen" behövs inte. Bildning av adresser ges nedan i två versioner, med och utan data i bitreverserad ordning.

Inorrnal ordning läggs inmatningsdata i minnet, d. v. s. första data i index O och andrai index 1 etc. Detta gör att data i den första fasen måste läsas i bitreverserad ordning och skrivas till normal 10 15 20 25 30 -E4E 0n'¶ and UUI l6 ordning. I detta fall måste svängande minnen användas, eftersom beräkningen av den första fasen inte utförs "på plats". Det är av vikt att läsa data i bitreverserad ordning, eftersom data är delad i fyra minnesenheter som var och en innehåller en fjärdedel av uppsättningen av inmatningsdata.

Det är också nödvändigt att beräkna butterfly-operatorer i en ordning med avseende på att endast två data läses och skrivs till / från varje minnesenhet. Därför behandlas den första fasen annorlunda än därpå följ ande faser. RLAP är ett intermediärt index som används för beräkningar av läsadresser för den första fasen.

Sedan fortsätter proceduren 60 genom att kontrollera LAP och om LAP är noll, 63, så initieras RLAP, 64: RLAP (N - 1 ner till 1) = LAP (1 upp till N - l) xor LAP (O) RLAP (0) = LAP (O) sedan bildas läskommandon, 65, R00 = 2 * RLAP R10 = R00 + 1 R0l = bitvis inversion av R10 (N ner till 0), kvarstående bitar av ROI är°0' Rll = bitvis inversion av R00 OI ner till 0), kvarstående bitar av R1 l är'0' sedan bildas skrivkommandon, 66 W00 = 2 * LAP Wl0 = W00 + 2'“*““““'“(STEP' N) WOl = bitvis inversion av W10 (N ner till 0), återstående bitar av W01 är ”O” Wll = bitvis inversion av W00 (N ner till O), återstående bitar av W1 1 är ”O” om LAP inte är noll, 63, d. v. s. inte forsta gången, så genereras läskommandon, 67 R00 = 2 * LAP - LAP (N ner till 0) R10 = ROO + 2ml""““m(STEP* N) ROI = R00 Rll = R10 och slutligen bildas skrivkommandon, 68 WOO = 2 * LAP - LAP (N ner till 0) Wl0 = WOO + 2'“"“lf““'“(STEP*N) W01 = WOO Wll = Wl0 Proceduren avslutas genom utmatning av de bildade kommandona, 69. 20 25 30 (fl IA (H O H7 ul r-ß \J När det gäller bitreverserad ordning kan data behandlas på plats eftersom den redan placerats i minnet i bitreverserad ordning. Läsadressema är desamma som skrivadressema i exemplet ovan. Den första fasen beräknas också: ROO = WOO = 2 * LAP - LAP (N ner till O) R10 = W10 = WOO + 2““'“*'"“"“(STE'”' N) R01 = WO1 = WOO R11=W11=W10.

MDCU-I 17.

MDCU-I 17 tillhandahålls for att koppla om data från den korrekta minnesenheten 12 och minnesposition. Den illustreras i Fig. 7. Blocket innefattar flera enheter för omkoppling, företrädesvis MUX 70 - 76. Styrinrnatningssignalerna till MUX tillhandahålls av MCU 13.

MUX 70 och 75 kopplar om dataindexsignaler från MS 12.1 - 12.3, MUX 71 kopplar om data fiån MS, och MUX 72 och 76 kopplar om signaler ”data giltig” från MS. MCU 13 styr omkopplingsoperationerna i MUX. Utmatningarna från MUX kopplas om ytterligare till FDO eller POST genom MUX 73 och 74.

MCU 13.

Blocket MCU 13 består av en tillståndsmaskin. Minneskonfigurationen är ordnad for att anta sex olika tillstånd, S0 - S5 såsom visas i Fig. 8. I Olika MS väljs i olika tillstånd. Valen offentliggörs i tabell 5. MS 12.1 - 12.3 noteras som MSO - MS3.

Tabell 5 TILLSTÅND I/o-MINNE DATA FRÅN DATA FRÅN Bo MTNNE TILL Bo TILL MINNE so Mso Msz Msi si Mso Msi Msz sz Msi . Mso Msz ss Msi Msz Mso s4 Msz Msi Mso ss Msz Mso Msi 10 15 20 25 30 ~. C4E Onfl u nu uu: 18 Motsvarande selektionssignaler för multiplexorportar offentliggörs I tabell 6, MUX- selektionssignalerna indikeras i Fig. 5 och 7. I enlighet med tabell 6, vid tillstånd S0, så används MSO som I/O-minne, innehållet i MS2 sänds till BO och resultat från BO skrivs till MSI.

Tabell 6 . _ Välj I Msb__sELj Ms1_'AsEL ' Ms2_s1~:i." ,D_P~_¿s1f:1.7 ¿ OQLSEL Wsfå" (fig-S) *g tfig-S) (fig- s) (H:- 1) i "gïgm i S0 2 1 0 2 0 S1 2 0 1 1 0 S2 0 2 1 O 1 S3 1 2 0 2 1 S4 1 0 2 1 2 S5 0 1 2 0 2 Värdena av cellerna i tabell 6 hänvisar till portnummer för en MUX som skall selekteras. I enlighet med detta betyder S2 och MS 1_SEL att port 2 i MUX 53 (Fig. 5) selekteras.

I tillständsdiagrammet i F ig. 8 indikeras tvâ signaler för förändring av tillstånd, MEM_SWIT CH och NEW_STATE. MEM_SWITCH är en styrsignal från CONTROL 26 för att koppla om alla minnen och NEW-STATE är en styrsignal från PROC för att koppla om läs- och skrivminnen. Starttillståndet, S0, nås efter ett återställningskommando, REST-CMD.

Utförandet i enlighet med Fig. 2 och besläktade ritningar ges endast som ett icke begränsande exempel. Det är möjligt att sätta in nya eller ta bort några av blocken / kretsarna och ordna vissa block som yttre kretsar. Multiplexenheterna kan ersättas med andra arrangemang för omkoppling, såsom PLC (Programmable Logic Control) eller liknande.

Ett annat utförande visas i Fig. 10, i vilket två bas-4 butterfly-operatorer 11.1' och 1 1.1' tillhandahålls. Antalet minnesuppsättningar 12” reduceras till fyra men antalet datainmatningar för varje minnesuppsättning ökas till fyra. Samma referensnummer anger samma delar som i Fig. 1.

.- Emellertid anges referensnummer till delar med modifierade funktioner på grund av bas-4 butterfly-operatorer med accenter, men annars är funktionen av alla delar analog med det ovan beskrivna utförandet.

Elf' Oflfi UIQ OUI : v | | n , « = « i . 19 Uppfinningen är inte begränsad till de visade utforandena utan kan varieras på ett antal sätt utan att avvika från omfattningen av de bifogade kraven, och arrangemanget och metoden kan genomföras på olika sätt beroende på tillämpning, funktionella enheter, behov och krav etc.

Claims (33)

10 15 20 25 30 (fl Ià en ca c: ~a .nu - 5, _, P15420SE.C03 PATENTKRAV

1. Arrangemang for beräkning av en diskret Fouriertransforin (DFT) innefattande m bas- 2, r = 2, 4, 8, .. _, butterfly-operatorer (11.1 - 11.4), dataminnesuppsättningar (12, 12') innefattande minnesenheter (90 ~ 93) och medel för omkoppling (14, 15), kännetecknat av, att nämnda butterfly-operatorer (1 1.1 - 11.4, 11.1”, 11.2”) är ordnade parallellt och kopplade till m minnesenheter ( m = 1, 2, ...) tillåtande 2r åtkomster per minnesenhet under varje beräkning, att det använder sig av en FFT-längdparameter for butterfly-operationer, vilken FF T-längd är variabel, och att FFT-längden är rLMODE, vari LMODE z m + 1.

2. Arrangemang enligt krav 1, kännetecknat av, att antalet minnesenheter är 2m.

3. Arrangemang enligt krav 1, kännetecknat av, att en minnesstorlek för en minnesuppsättning är FFT-längden dividerad med antalet butterfly- operatorer.

4. Arrangemang enligt krav 2, kännetecknat av, att nämnda minnesuppsättningar (12, l2”) är svängande minnen.

5. Arrangemang enligt vilket som helst av krav 1 - 4, kännetecknat av, att det innefattar medel for generering av adresser, och första och andra styrmedel (17, 18) kopplade till nämnda minnesuppsättningar (12, l2').

6. Arrangemang enligt krav 5, 10 15 20 25 30 m _) m CO c: ~a 'Ni ~_\ kännetecknat av, att nämnda medel for generering av adresser (13) består av en tillståndsmaskin.

7. Arrangemang enligt krav 6, kännetecknat av, att nämnda tillståndsmaskin antar olika tillstånd (S0 - S5) som representerar val av olika minneskonfigurationer i minnesuppsättningar (12).

8. Arrangemang enligt krav 7, kännetecknat av, att åtminstone ett av nämnda tillstånd arrangerar åtminstone en minnesuppsättning som en inmatnings / utmatnings-minnesuppsättning och en minnesuppsättning för att ta emot data från åtminstone en av nämnda butterfly-operatorer.

9. Arrangemang enligt krav 7, kännetecknat av, att nämnda tillståndsmaskin är ordnad for att anta sex olika tillstånd (S0 - S5).

10. Arrangemang enligt krav 5, kännetecknat av, att nämnda forsta och andra styrmedel innefattar omkopplingsanordningar styrda av nämnda medel för generering av adresser.

11. Arrangemang enligt krav 10, kännetecknat av, att nämnda omkopplingsanordningar innefattar multiplexorer (40 - 43).

12. Arrangemang enligt krav 5, kännetecknat av, att nämnda forsta styrmedel (17) är ordnat for att koppla om data från korrekta minnesuppsättningar (12, 12 ”). 10 15 20 25 30 *Il må m oo t: w

13. Arrangemang enligt krav 5, kärmetecknat av, att nämnda andra medel for minnesstyming (18) är ordnat for att koppla om data till korrekta minnesuppsättningar (12, 12”).

14. Arrangemang enligt krav 5, kärmetecknat av, att nämnda första styrmedel (17) innefattar multiplexor (70 - 76) kopplad mellan butterfly- operatorema och minnesuppsättningar.

15. Arrangemang enligt krav 5 och 7, kännetecknat av, att nämnda andra medel for minnesstyrning (18) innefattar en styrsignalkrets (50), en I/O-krets (51) och medel för omkoppling (52 - 54), där nämnda styrsignalkrets och I/O-krets är kopplade till nämnda anordningar for omkoppling (52 - 54) genom nämnda adressgenererande medel.

16. Arrangemang enligt krav 1, kännetecknat av, att minnesuppsättningarna (12) innefattar fyra lagringsmedel av typen SRAM (Static Random Access Memory) (90 - 91).

17. Arrangemang enligt krav 1 och 5, kännetecknat av, att nämnda medel för omkoppling (14, 15) innefattar multiplexorer (40 ~ 47) arrangerade mellan butterfly-operatorema och medel för minnesstyming (17, 18).

18. Arrangemang enligt krav 17, kännetecknat av, att utmatningen från nämnda medel for omkoppling (14, 15) beror av pågående FFT- 515 807 beräkningssteg och ett index for beräkningssteg.

19. Beräkningsanordning, i huvudsak for diskret Fouriertransform (DFT) beräkning med användning av Fast Fourier Transform (FFT) på en uppsättning av data, där anordningen 5 innefattar m bas-r butterfly-operatorer (1 1.1 - 11.4), dataminnesuppsättningar (12) innefattande minnesenheter och medel for omkoppling (14, 15), kännetecknad av, att nämnda butterfly-operatorer är ordnade parallellt och att anordningen dessutom innefattar: - m minnesenheter, m = O, 1, 2, ..., 10 - styrblock (26, 27), som styr och övervakar anordningens funktioner, - generator av twiddle-koefficienter (16), för att generera twiddle-koefficienter (WO - W3) till nämnda butterfly-operatorer, - Styrenheter for minnesdata (17, 18) för att styra dataflöden till/från minnesuppsättningama, 15 - medel (26) för att ta emot en variabel FFT-längd för en FFT-beräkning, - styrenhet for minne (13) for styrning av funktionen hos minnesenhetema, och - att nämnda FFT-längd är FF T = rLMODE, vari LMODE z m + 1.

20. Anordning enligt krav 19, 20 kännetecknad av, att den dessutom innefattar - styrmedel för inmatningsdata (21) for att behandla inkommande data, - styrmedel for utmatningsdata (22) för att behandla utgående 25 data, och - forbehandlingsmedel (23) ordnar for att behandla data före FFT.

21. .Anordning enligt krav 19, 30 kännetecknad av, att den tillämpar både FFT och I FFT (inverterad FFT) på data. 10 15 20 25 30 411 .à 151 m <2 <|

22. Anordning enligt krav 21, kännetecknad av, att den innefattar ett medel för behandling (24) som utför operationer på data i frekvens- domänen.

23. Anordning enligt krav 21, kännetecknad av, att den innefattar medel för efterbehandling (25) före utmatning.

24. Anordning enligt krav 21, kännetecknad av, att data läses från en minnesuppsättning ( 12.1 - 12.3) och skrivs tillbaka till en annan.

25. Metod för att utföra FFT-beräkning i ett beräkningsarrangemang som innefattar m (m = 1, 2, 3, ...) bas-r butterfly-operatorer (11.1 - 11.4, 11.1', 11.2”), dataminnesuppsättningar (12, 12') vilka innefattar minnesenheter, och första och andra omkopplingsmedel (14, 15), kännetecknad av, ordnande av nämnda butterfly-operatorer (11.1 - 11.4, l1.1°, 11.2”) parallellt och ordnande av m minnesenheter (12) vilket tillåter 2r minnesåtkomster per minnesenhet under varje beräkning, och anordna medel (26) för att mottaga en variabel FFT-längd för en F F T- beräkning, vars FFT-längd är FFT = rLMODE, vari LMODE z m + 1.

26. Metod enligt krav 25, kännetecknad av, att data lagras i normal eller bitreverserad ordning i minnet.

27. Metod enligt krav 25, kännetecknad av, att FFT-beräkningen består av ett antal beräkningsfaser och riktningen för dataflödet kastas om efter varje fas. 10 15 20 25 30 UT .å *fl oo o \'l

28. Metod enligt krav 27, kärmetecknad av, att dataflödet till minnesuppsättningarna styrs av olika konfigurationer för bestämning av ett mönster för användning av omkopplingsmedlen ( 14,15) med avseende på signalerna STEP, LAP och NFFT = FFT-längd = rLMODE, LMODE z m + l, som tas emot från en styrenhet (26, 27).

29. Metod enligt krav 28, kännetecknad av, - bestämning av en första konfiguration för det första medlet för omkoppling (14) om STEP är 0 (noll) och LAP är jämn, - bestämning av en andra konfiguration för det första medlet för omkoppling (14) om STEP är O (noll) och LAP är udda, - bestämning av en tredje konfiguration för det första och det andra medlet för omkoppling (14, 15) om STEP är LMODE - 2. - bestämning av en fjärde konfiguration för det första och det andra medlet för omkoppling (14, 15) är LMODE - l.

30. Metod enligt krav 25, kännetecknad av, att dataflödet till minnesuppsättningama styrs med hjälp av stynnedel, som genererar signaler för datahantering av minnen till och från butterfly-operatorema, där metoden innefattar stegen att: - ta emot inmatningar: LAP, vilken är index för beräkningssteg, STEP vilket är pågående FFT beräkningssteg, - kontrollera LAP och om LAP är noll (63) så initierar RLAP ett slingindex, i vilket RLAP (N - 1 ner till 1) = LAP (1 upp till N - 1) xor LAP (0), och RLAP (0) = LAP (O), - bilda läskommandon till nämnda minnesuppsättningar R00 = 2 * RLAP, 10 15 20 25 30 i* 515 807 R10 = R00 + 1, R01 = bitvis inversion av R10 (N ner till 0), återstående bitar av R01 är ,0,, R11 = bitvis inversion av R00 (N ner till O), återstående bitar av R1 1 är ,0,, - och bilda skrivkommandon till nämnda minnesuppsättningar WOO = 2 * LAP, WlO = WOO + 2mi“"““"' (STEP- N) W01 = bitvis inversion av W10 (N ner till O), återstående bitar av W01 är “O”, Wll = bitvis inversion av WOO (N ner till O), återstående bitar av Wll är ”O”, där första index anger adress för portar i en minnesenhet (90 - 93) och andra index anger adresser till minnesenheter (90 - 93).

31. Metod enligt krav 30, kännetecknad av, att om LAP inte är noll så bildas läskommandon: ROO = 2 * LAP - LAP (N ner till 0) R10 = ROO + Zminimumßrav, N) R01 = ROO R11 = R10, och bildning av skrivkommandon: W00 = 2 * LAP - LAP OI ner till 0) W10 = Woo + zmffliffmmßTfiPt N> W01 = WOO Wll = WlO.

32. Metod enligt krav 25 och 27, kännetecknad av, 10 515 807* att data är i bitreverserad ordning och läsadresserna är samma som skrivadresserna: R00 = WOO = 2 * LAP - LAP (N ner till 0) RIO = WIO = WOO + 2mí“"““"'(STEP* N) R01 = W01 = WOO R11=W11=W10.

33. Metod enligt krav 25, kännetecknad av, att en ordning för beräkning av butterfly-operatorerna är mindre än 2 läsningar/skrivningar av data från/till 2-po11s minnesenheter vid varje bräkningssteg.