Contributions To Efficient Design And Implementation Of Variable Digital Filters

Contributions to Efficient Design and Implementation of Variable Digital Filters

Complexity reduction is one of the main issues of digital signal processing (DSP) algorithms, especially in communication systems where each new generation brings new requirements towards increasing data rates and improved accuracy positioning, leading to the growth of power consumption and chip area. To meet these requirements and at the same time find a trade-off between high performance and low implementation cost, more sophisticated DSP algorithms need to be developed. Recent communication standards require flexible, adaptive systems capable of real-time frequency-domain tuning. Variable digital filters (VDFs) address these needs by enabling "on-the-fly" frequency response adjustments without the need for online filter design. The key feature of VDFs is that they require only an adjustment of one or a few parameters to change their characteristics, without the need for extensive additional computations. Most VDF coefficients remain fixed after the initial design, allowing for efficient hardware implementation. This makes VDFs essential for modern adaptive communication technologies. This thesis primarily focuses on the design and low-complexity implementation techniques of VDFs and presents three main contributions. Firstly, it proposes three VDF realizations for simultaneous lowpass filtering and equalization using polynomial channel models, with systematic design procedures based on minimax optimization for all the proposed structures. In addition, a fast design method for the VDFs with several variable parameters, which can substantially decrease the design time, is presented. Secondly, it introduces frequency-domain implementations of VDFs using the overlap-save technique. Based on the assumption that these filters have been designed using a common design approach based on optimizing the impulse response coefficients, the filter DFT coefficients are proposed to be implemented as fixed, hybrid, or variable weights. Lastly, the thesis presents an efficient design approach for a variable-bandwidth digital filter implemented in the frequency domain using the overlap-save method. The proposed approach is based on a hybrid of frequency sampling and optimization, allowing for direct optimization of the DFT coefficients considering the filter frequency-domain implementation and thereby noticeably reducing the cost of implementation and an online update of the DFT filter coefficients when the bandwidth is varied. Reduktion av komplexitet är en av huvudfrågorna för digital signalbehandling (DSP) algoritmer, särskilt i kommunikationssystem där varje ny generation ställer nya krav på att öka datahastigheter och förbättrad noggrannhet positionering, vilket leder till en ökning av strömförbrukningen och kretsytan. För att möta dessa krav och samtidigt hitta en avvägning mellan hög prestanda och låg implementeringskostnad behöver mer sofistikerade DSP-algoritmer utvecklas. Senaste kommunikationsstandarder kräver flexibla, adaptiva system som kan frekvensdomäninställning i realtid. Variabla digitala filter (VDF) tillgodoser dessa behov genom att möjliggöra "on-the-fly" frekvenssvarsjusteringar utan behov av onlinefilterdesign. Nyckelegenskapen hos VDF:er är att de bara kräver en justering av en eller ett fåtal parametrar för att ändra deras egenskaper, utan behov av omfattande ytterligare beräkningar. De flesta VDF-koefficienter förblir fixerade efter den ursprungliga designen, vilket möjliggör effektiv hårdvaruimplementering. Detta gör VDF:er väsentliga för modern adaptiv kommunikationsteknik. Den här avhandlingen fokuserar främst på design och implementeringstekniker med låg komplexitet för VDF:er och presenterar tre huvudsakliga bidrag. För det första föreslår den tre VDF-realiseringar för samtidig lågpassfiltrering och utjämning med användning av polynomkanalmodeller, med systematiska designprocedurer baserade på minimax optimering för alla föreslagna strukturer. Dessutom presenteras en snabb designmetod för VDF:erna med flera variabla parametrar, som avsevärt kan minska designtiden. För det andra introducerar den frekvensdomänimplementationer av VDF:er med överlappningssparateknik. Baserat på antagandet att dessa filter har utformats med användning av en gemensam designmetod baserad på optimering av impulssvarskoefficienterna, föreslås filtrets DFT-koefficienter implementeras som fasta, hybrida eller variabla vikter. Slutligen presenterar avhandlingen en effektiv designansats för ett digitalt filter med variabel bandbredd implementerat i frekvensdomänen med användning av överlappningssparametoden. Det föreslagna tillvägagångssättet är baserat på en hybrid av frekvenssampling och optimering, vilket möjliggör direkt optimering av DFT-koefficienterna med tanke på implementeringen av filterfrekvensdomänen och därigenom märkbart minska kostnaden för implementering och en onlineuppdatering av DFT-filterkoefficienterna när bandbredden är varierande.

Contributions to Efficient Design and Implementation of Variable Digital Filters

Energy-Efficient Implementation of Communication Algorithms through Complexity Reduction

Energy-efficient implementations are essential for the future and modern society, especially in digital signal processing (DSP) and communication systems, where the rapid growth of devices, such as those battery-driven internet of things (IoT) sensors, necessitates low-complexity and low-power solutions. This thesis concentrates on two areas: constant multiplication and active user detection in wire-less networks. Constant multiplication can be implemented using a shift-and-add (SHA) network. Typically, the number of adders/subtracters is minimized, but the number of cascaded adders/subtracters (depth) also impacts the power consumption. The two classes of algorithms used to solve the problem are adder graph algorithms or sub-expression sharing algorithms. Adder graph algorithms typically yield better results for a single or a low number of inputs, since they do not depend on the representation of the numbers involved. However, they can lead to very high run times and worse results when the number of inputs is high. At the same time, it is known that it is possible to transpose the problem. For example, a sum of products (many inputs) can be transposed to a single input with multiple coefficients, meaning that it is possible to transpose the problem to the more advantageous form, solve it and then transpose the solution back. However, there has been no systematic algorithm available to obtain the transposed result that takes depth into account. In this thesis, a systematic algorithm that obtains the minimum depth of the transposed SHA network subject to the input is introduced. The practical application of the constant multiplication problem is demonstrated through the implementation of a reconfigurable lowpass equalizer, widely used in communication systems and DSP. Various formulations of the constant multiplication problem, combined with pipelining, are explored to identify the most efficient implementation in a 28 nm FD-SOI standard cell, significantly reducing power consumption and highlighting the real-world impact of our research. The second research focuses on the challenge of detecting active users in massive machine-type communication (mMTC) scenarios involving large numbers of devices. The problem is addressed using a pilot-hopping sequence method and is formulated as a non-negative least-squares (NNLS) problem. This work implements two NNLS algorithms, fast projected gradient (Fast) and multiplicative updates (Mult), to solve the active user detection problem. These implementations are implemented in a 28 nm FD-SOI process and are optimized for energy efficiency, chip area, and detection speed. The results demonstrate the ability to perform over a million detections per second with significantly lower energy consumption compared to existing methods. However, the implementations lack reconfigurability, and it can be argued whether the high detection rates are relevant for current practical applications. To enhance practicality and reconfigurability, the Fast algorithm is implemented using a reconfigurable time-multiplexed architecture, reducing resources by reusing them within one iteration. This architecture employs a novel user re-ordering method to enable parallel memory access and continuous operation for successive iterations, thereby increasing the execution speed. The architecture is implemented on numerous FPGA families, demonstrating resource efficiency and reconfigurability by storing the pilot-hopping sequences in memory, while obtaining a more practically usable detection rate of about one to a few thousand detections per second depending on the FPGA family. Energieffektiva implementationer är avgörande för framtiden och det moderna samhället, särskilt inom digital signalbehandling (DSP) och kommunikationssystem, där den snabba tillväxten av enheter, såsom de inom Internet of Things (IoT), kräver lösningar med låg komplexitet och låg effektförbrukning. Denna avhandling fokuserar på två områden: konstantmultiplikation och detektering av aktiva användare i trådlösa nätverk. Konstantmultiplikation kan implementeras med ett shift-and-add (SHA) nätverk. Vanligtvis så minimeras antalet adderare/subtraherare, men antalet kaskadkopplade adderare/subtraherare (djupet) påverkar också effektförbrukningen. De två klasserna av algoritmer för att lösa konstaktmultiplikation baseras på adderargrafer eller gemensamma deluttryck. Addergrafer är oftast bättre vid en eller få ingångar, eftersom de inte beror på vilken representation som talen uttrycks med. För många ingångar så kan beräkningstiden öka väldigt snabbt samt att resultaten ofta är sämre eftersom sökrymden ökar fort. Samtidigt så är det välkänt att det får att transponera problemet. Till exempel så kan en summa produkter (många ingångar) transponeras till en ingång som multipliceras med många olika konstanter. Detta leder till att det är möjligt att transponera problemet till den mest fördelaktiga formen, lösa det och sedan transponera lösningen. Det har tidigare inte funnits någon systematisk algoritm för att transponera ett nätverk som tar hänsyn till djupet, men i denna avhandling så presenteras en som garanterar minimalt djup givet en viss adderargraf som argument. Den praktiska tillämpningen av konstantmultiplikation demonstreras genom implementering av en konfigurerbar lågpassutjämnare, som är allmänt använd i DSP- och kommunikationssystem. Olika formuleringar av konstantmultiplikationsproblemet, kombinerat med pipelining, utforskas för att identifiera den mest effektiva implementationen i en 28 nm FD-SOI-standardcell, vilket avsevärt minskar strömförbrukningen och visar den verkliga påverkan av vår forskning. Den andra forskningen fokuserar på utmaningen att detektera aktiva användare i massive machinetype communication (mMTC) med ett stort antal enheter. Problemet hanteras med hjälp av en pilothoppingssekvensmetod och formuleras som ett problem med non-negative least-squares (NNLS). Detta arbete implementerar två NNLS-algoritmer, fast projected gradient (Fast) och multiplikativa uppdateringar (Mult), för att lösa problemet med detektering av aktiva användare. Dessa implementationer implementerade i en 28 nm FD-SOI-process och är optimerade för energieffektivitet, chiparea och detekteringshastighet. Resultaten visar att mer än en miljon detektioner per sekund kan utföras med betydligt lägre energiförbrukning än befintliga metoder, till stor del för att en iteration beräknas helt parallelt. Dock saknas möjlighet att ändra användarsekvenser och det kan diskuteras om den höga detektionstakten är praktiskt användbar. För att öka praktiskheten implementeras Fast-algoritmen med en konfigurerbar tidsmultiplexad arkitektur, vilken sparar resurser genom att återanvända dem i en iteration. Denna arkitektur använder en ny metod att ordna om användarna för att möjliggöra parallell minnesåtkomst och kontinuerliga beräkning-ar för efterföljande iterationer, vilket ökar exekveringshastigheten. Arkitekturen implementeras på olika FPGA-familjer och visar resurseffektivitet och konfigurerbarhet genom att pilothoppningssekvenserna sparas i minne, samtidigt som en mer praktiskt användbar detektionshastighet från ungefär ett tusen till några tusen detektioner per sekund beroende på FPGA-familj.