Institutionen för systemteknik (ISY)

User activity detection in grant-free random access massive machine type communication (mMTC) using pilot-hopping sequences can be formulated as solving a non-negative least squares (NNLS) problem. In this work, two architectures using different algorithms to solve the NNLS problem is proposed. The algorithms are implemented using a fully parallel approach and fixed-point arithmetic, leading to high detection rates and low power consumption. The first algorithm, fast projected gradients, converges faster to the optimal value. The second algorithm, multiplicative updates, is partially implemented in the logarithmic domain, and provides a smaller chip area and lower power consumption. For a detection rate of about one million detections per second, the chip area for the fast algorithm is about 0.7 mm 2 compared to about 0.5 mm 2 for the multiplicative algorithm when implemented in a 28 nm FD-SOI standard cell process at 1 V power supply voltage. The energy consumption is about 300 nJ/detection for the fast projected gradient algorithm using 256 iterations, leading to a convergence close to the theoretical. With 128 iterations, about 250 nJ/detection is required, with a detection performance on par with 192 iterations of the multiplicative algorithm for which about 100 nJ/detection is required.

The most challenging aspect of particle filtering hardware implementation is the resampling step. This is because of high latency as it can be only partially executed in parallel with the other steps of particle filtering and has no inherent parallelism inside it. To reduce the latency, an improved resampling architecture is proposed which involves pre-fetching from the weight memory in parallel to the fetching of a value from a random function generator along with architectures for realizing the pre-fetch technique. This enables a particle filter using M particles with otherwise streaming operation to get new inputs more often than 2M cycles as the previously best approach gives. Results show that a pre-fetch buffer of five values achieves the best area-latency reduction trade-off while on average achieving an 85% reduction in latency for the resampling step leading to a sample time reduction of more than 40%. We also propose a generic division-free architecture for the resampling steps. It also removes the need of explicitly ordering the random values for efficient multinomial resampling implementation. In addition, on-the-fly computation of the cumulative sum of weights is proposed which helps reduce the word length of the particle weight memory. FPGA implementation results show that the memory size is reduced by up to 50%.

A direct digital-to-RF converter (DRFC) is presented in this work. Due to its digital-in-nature design, the DRFC benefits from technology scaling and can be monolithically integrated into advance digital VLSI systems. A fourth-order single-bit quantizer bandpass digital EA modulator is used preceding the DRFC, resulting in a high in-band signal-to-noise ratio (SNR). The out-of-band spectrally-shaped quantization noise is attenuated by an embedded semi-digital FIR filter (SDFIR). The RF output frequencies are synthesized by a novel configurable voltage-mode RF DAC solution with a high linearity performance. The configurable RF DAC is directly synthesizing RF signals up to 10 GHz in first or second Nyquist zone. The proposed DRFC is designed in 22 nm FDSOI CMOS process and with the aid of Monte-Carlo simulation, shows 78.6 dBc and 63.2 dBc worse case third intermodulation distortion (IM3) under process mismatch in 2.5 GHz and 7.5 GHz output frequency respectively.

Optimization problem formulation for semi-digital FIR digital-to-analog converter (SDFIR DAC) is investigated in this work. Magnitude and energy metrics with variable coefficient precision are defined for cascaded digital sigma modulators, semi-digital FIR filter, and Sinc roll-off frequency response of the DAC. A set of analog metrics as hardware cost is also defined to be included in SDFIR DAC optimization problem formulation. It is shown in this work, that hardware cost of the SDFIR DAC, can be significantly reduced by introducing flexible coefficient precision while the SDFIR DAC is not over designed either. Different use-cases are selected to demonstrate the optimization problem formulations. A combination of magnitude metric, energy metric, coefficient precision and analog metrics are used in different use cases of optimization problem formulation and solved to find out the optimum set of analog FIR taps. A new method with introducing the variable coefficient precision in optimization procedure was proposed to avoid non-convex optimization problems. It was shown that up to 22% in the total number of unit elements of the SDFIR filter can be saved when targeting the analog metric as the optimization objective subject to magnitude constraint in pass-band and stop-band.

The single constant coefficient multiplication is a frequently used operation in many numeric algorithms. Extensive previous work is available on how to reduce constant multiplications to additions, subtractions, and bit shifts. However, on previous work, only common two-input adders were used. As modern field-programmable gate arrays (FPGAs) support efficient ternary adders, i.e., adders with three inputs, this brief investigates constant multiplications that are built from ternary adders in an optimal way. The results show that the multiplication with any constant up to 22 bits can be realized by only three ternary adders. Average adder reductions of more than 33% compared to optimal constant multiplication circuits using two-input adders are achieved for coefficient word sizes of more than five bits. Synthesis experiments show FPGA average slice reductions in the order of 25% and a similar or higher speed than their two-input adder counterparts.

This brief presents a new type of fast Fourier transform (FFT) hardware architectures called serial commutator (SC) FFT. The SC FFT is characterized by the use of circuits for bit-dimension permutation of serial data. The proposed architectures are based on the observation that, in the radix-2 FFT algorithm, only half of the samples at each stage must be rotated. This fact, together with a proper data management, makes it possible to allocate rotations only every other clock cycle. This allows for simplifying the rotator, halving the complexity with respect to conventional serial FFT architectures. Likewise, the proposed approach halves the number of adders in the butterflies with respect to previous architectures. As a result, the proposed architectures use the minimum number of adders, rotators, and memory that are necessary for a pipelined FFT of serial data, with 100% utilization ratio.

In this brief, we present the CORDIC II algorithm. Like previous CORDIC algorithms, the CORDIC II calculates rotations by breaking down the rotation angle into a series of microrotations. However, the CORDIC II algorithm uses a novel angle set, different from the angles used in previous CORDIC algorithms. The new angle set provides a faster convergence that reduces the number of adders with respect to previous approaches.

In this brief, we propose how the hardware complexity of arbitrary-order digital multibit error-feedback delta-sigma modulators can be reduced. This is achieved by splitting the combinatorial circuitry of the modulators into two parts, i.e., one producing the modulator output and another producing the error signal fed back. The part producing modulator output is removed by utilizing a unit-element-based digital-to-analog converter. To illustrate the reduced complexity and power consumption, we compare the synthesized results with those of conventional structures. Fourth-order modulators implemented with the proposed technique use up to 26% less area compared with conventional implementations. Due to the area reduction, the designs consume up to 33% less dynamic power. Furthermore, it can operate at a frequency 100 MHz higher than that of the conventional.

This paper proposes optimal finite-length impulse response (FIR) digital filters, in the least-squares (LS) sense, for compensation of chromatic dispersion (CD) in digital coherent optical receivers. The proposed filters are based on the convex minimization of the energy of the complex error between the frequency responses of the actual CD compensation filter and the ideal CD compensation filter. The paper utilizes the fact that pulse shaping filters limit the effective bandwidth of the signal. Then, the filter design for CD compensation needs to be performed over a smaller frequency range, as compared to the whole frequency band in the existing CD compensation methods. By means of design examples, we show that our proposed optimal LS FIR CD compensation filters outperform the existing filters in terms of performance, implementation complexity, and delay.

The appearance of radix-2(2) was a milestone in the design of pipelined FFT hardware architectures. Later, radix-2(2) was extended to radix-2(k). However, radix-2(k) was only proposed for single-path delay feedback (SDF) architectures, but not for feedforward ones, also called multi-path delay commutator (MDC). This paper presents the radix-2(k) feedforward (MDC) FFT architectures. In feedforward architectures radix-2(k) canbe used for any number of parallel samples which is a power of two. Furthermore, both decimation in frequency (DIF) and decimation in time (DIT) decompositions can be used. In addition to this, the designs can achieve very high throughputs, which makes them suitable for the most demanding applications. Indeed, the proposed radix-2(k) feedforward architectures require fewer hardware resources than parallel feedback ones, also called multi-path delay feedback (MDF), when several samples in parallel must be processed. As a result, the proposed radix-2(k) feedforward architectures not only offer an attractive solution for current applications, but also open up a new research line on feedforward structures.

The coefficient decimation technique for reconfigurable FIR filters was recently proposed as a filter structure with low computational complexity. In this brief, we propose to design these filters using linear programming taking all configuration modes into account, instead of only considering the initial reconfiguration mode as in previous works. Minimax solutions with significantly lower approximation errors compared to the straightforward design method in earlier works are obtained. In addition, some new insights that are useful when designing coefficient decimation filters are provided.

This brief presents a novel approach for improving the accuracy of rotations implemented by complex multipliers, based on scaling the complex coefficients that define these rotations. A method for obtaining the optimum coefficients that lead to the lowest error is proposed. This approach can be used to get more accurate rotations without increasing the coefficient word length and to reduce the word length without increasing the rotation error. This brief analyzes two different situations where the optimization method can be applied: rotations that can be optimized independently and sets of rotations that require the same scaling. These cases appear in important signal processing algorithms such as the discrete cosine transform and the fast Fourier transform (FFT). Experimental results show that the use of scaling for the coefficients clearly improves the accuracy of the algorithms. For instance, improvements of about 8 dB in the Frobenius norm of the FFT are achieved with respect to using non-scaled coefficients.

This letter describes an efficient architecture for the computation of fast Fourier transform (FFT) algorithms with single-bit input. The proposed architecture is aimed for the first stages of pipelined FFT architectures, processing one sample per clock cycle, hence making it suiable for real-time FFT computation. Since natural input order pipeline FFTs use large memories in the early stages, it is important to keep the word length shorter in the beginning of the pipeline. By replacing the initial butterflies and rotators of an architecture with that of the proposed block, the memory requirements can be significantly reduced. Comparisons with the commonly used single delay feedback (SDF) architecture show that more than 50% of the required memory can be saved in some cases.

The generation of a canonical signed digit representation from a binary representation is revisited. Based on the property that each nonzero digit is surrounded by a zero digit, a hardware-efficient conversion method using bypass instead of carry propagation is proposed. The proposed method requires less area per digit and the required bypass signal can be generated or propagated with only a single NOR gate. It is shown that the proposed converter outperforms previous converters and a look-ahead circuitry to speed up the generation of bypass signals is also proposed.

Multiplication by constants can be efficiently realized using shifts, additions, and subtractions. In this work we consider how to select a fixed-point value for a real valued, rational, or floating-point coefficient to obtain a low-complexity realization. It is shown that the process, denoted addition aware quantization, often can determine coefficients that has as low complexity as the rounded value, but with a smaller approximation error by searching among coefficients with a longer wordlength.

Multiple constant multiplication (MCM) is an efficient way of implementing several constant multiplications with the same input data. The coefficients are expressed using shifts, adders, and subtracters. By utilizing redundancy between the coefficients the number of adders and subtracters is reduced resulting in a low complexity implementation. However, for digit-serial arithmetic a shift requires a flip-flop, and, hence, the number of shifts should be taken into consideration as well. In this work we investigate the area, speed, power trade-offs for implementation of FIR filters using MCM and digit-serial arithmetic. We also introduce an algorithm for reducing both the number of adders and subtracters as well as the number of shifts.

In many digital signal processing algorithms, e.g., linear transforms and digital filters, the multiplier coefficients are constant. Hence, it is possible to implement the multiplier using shifts, adders, and subtracters. In this work two approaches to realize constant coefficient multiplication with few adders and subtracters are presented. The first yields optimal results, i.e., a minimum number of adders and subtracters, but requires an exhaustive search. Compared with previous optimal approaches, redundancies in the exhaustive search cause the search time to be drastically decreased. The second is a heuristic approach based on signed-digit representation and subexpression sharing. The results for the heuristic are worse in only approximately 1% of all coefficients up to 19 bits. However, the optimal approach results in several different optimal realizations, from which it is possible to pick the best one based on other criteria. Relations between the number of adders, possible coefficients, and number of cascaded adders are presented, as well as exact equations for the number of required full and half adder cells. The results show that the number of adders and subtracters decreases on average 25% for 19-bit coefficients compared with the canonic signed-digit representation.

The problem of selecting codewords for memoryless low-power bus coding is considered. A graph-based procedure is proposed to obtain a subset of all possible codewords with minimum average energy consumption. The procedure can be applied to arbitrary cost models.

In this work filter structures that decrease the required number of multipliers and adders for implementation of linear-phase FIR filters using frequency-response masking techniques are introduced. The basic idea of the proposed structures is that identical subfilters are used. This leads to the same arithmetic structure can be multiplexed in the implementation, reducing the number of required multipliers and adders. The subfilters are mapped using the folding transformation to obtain an area-efficient time-multiplexed (or pipeline/interleaved) implementation. Both narrow-band and wide-band frequency-response masking as well as arbitrary bandwidth frequency-response masking techniques are considered. The filter design is discussed and for each filter structure the limits on the specifications are derived. Designed examples show the usefulness of the proposed structures.

In this chapter fundamentals of arithmetic operations and number representations used in DSP systems are discussed. Different relevant number systems are outlined with a focus on fixed-point representations. Structures for accelerating the carry-propagation of addition are discussed, as well as multi-operand addition. For multiplication, different schemes for generating and accumulating partial products are presented. In addition to that, optimization for constant coefficient multiplication is discussed. Division and square-rooting are also briefly outlined. Furthermore, floating-point arithmetic and the IEEE 754 floating-point arithmetic standard are presented. Finally, some methods for computing elementary functions, e.g., trigonometric functions, are presented.

The optimization of shift‐and‐add network for constant multiplications is found to have great potential for reducing the area, delay, and power consumption of implementation of multiplications in several computation‐intensive applications not only in dedicated hardware but also in programmable computing systems. To simplify the shift‐and‐add network in single constant multiplication (SCM) circuits, this chapter discusses three design approaches, including direct simplification from a given number representation, simplification by redundant signed digit (SD) representation, and simplification by adder graph. Examples of the multiple constant multiplication (MCM) methods are constant matrix multiplication, discrete cosine transform (DCT) or fast Fourier transform (FFT), and polyphase finite impulse response (FIR) filters and filter banks. The given constant multiplication methods can be used for matrix multiplications and inner‐product; and can be applied easily to image/video processing and graphics applications. The chapter further discusses some of the shortcomings in the current research on constant multiplications, and possible scopes of improvement.

In this work we discuss the realization of constant multiplication using a minimum number of carry-save adders. We consider both non-redundant and carry-save representation for the input data. For both cases we present all possible interconnection topologies, using up to six and five adders, respectively. These are sufficient to realize constant multiplications for all coefficients with a wordlength up to 19 bits.

In this work modelling of the power consumption for ripple-carry adders implemented in CMOS is considered. Based on the switching activity of each input bit, two switching models, one full and one simplified, are derived. These switching models can be used to derive the average energy consumed for one computation. This work extends previous results by introducing a data dependent power model, i.e., correlated input data is considered. Examples show that the switching model is accurate, while there are some differences in the power consumption. This is due to the fact that not all switching in the ripple-carry adder is rail-to-rail (full swing) in the actual implementation.

In this work, we analyze the step-size approximation for fixed-point least-mean-square (LMS) and block LMS (BLMS) algorithms. Our primary focus is on investigating how step size approximation impacts the convergence rate and steady-state mean square error (MSE) across varying block sizes and filter lengths. We consider three different FP quantized LMS and BLMS algorithms. The results demonstrate that the algorithm with two quantizers in single precision behaves approximately the same as one quantizer under quantized weights, regardless of block size and filter lengths. Subsequently, we explore the approximation effects of nearest power-of-two and their combinations with different design parameters on the convergence performance. Simulation results for within the context of a system identification problem under these approximations reveal intriguing insights. For instance, a single quantizer algorithm without quantized error is more robust than its counterpart under these approximations. Additionally, both single quantizer algorithms with combined power-of-two approximations matches the behavior of the actual step-size.

Matrix transposition, the procedure of swapping rows and columns of a matrix, has applications in various signal processing applications, such as massive multiple-input multiple-output (MIMO) communication systems, data compression, and multidimensional fast Fourier transforms – which are used in MIMO radar systems. In low-latency high-throughput streaming applications, specialized circuits for matrix transposition are needed in order to perform transposition in real-time. This is in contrast to "slower" applications, where transposition can be adequately performed by storing a matrix in a shared memory and afterward reading it back in a transposed order. In this paper, a design procedure for streaming matrix transposition on field-programmable gate arrays (FPGAs) using distributed memories is presented. It is shown that significantly fewer FPGA resources are required for small- to medium-sized streaming matrix transpositions compared to recent related works.

Spade is a new open source hardware descriptionlanguage (HDL) designed to increase developer productivitywithout sacrificing the low-level control offered by HDLs. Itis a standalone language which takes inspiration from modernsoftware languages, and adds useful abstractions for commonhardware constructs. It also comes with a convenient set of tool-ing, such as a helpful compiler, a build system with dependencymanagement, tools for debugging, and editor integration.

Approaches to shift-and-add realization of time-domain chromatic dispersion compensation FIR filters are considered. The coefficient word length has larger impact than filter length on both BER penalty and adder complexity.

Finite word length effects for frequency-domain implementation of chromatic dispersion compensation is analyzed. The results show a significant difference for the different factors when it comes to power consumption and receiver penalty.

Floating-point numbers represented using a hidden one can readily be approximately converted to the logarithmic domain using Mitchell's approximation. Once in the logarithmic domain, several arithmetic operations including multiplication, division, and square-root can be easily computed using the integer arithmetic unit. This has earlier been used in fast reciprocal square-root algorithms, sometimes referred to as magic number algorithms. The proposed approximate operations are realized by performing an integer operation using an integer unit on floating-point data and adding an integer constant to obtain the approximate floating-point result. In this work, we derive easy to use equations and constants for multiple floating-point formats and operations.

We perform exploratory ASIC design of key DSP and FEC units for 400-Gbit/s coherent data-center interconnect receivers. In 22-nm CMOS, the considered units together dissipate 5 W, suggesting implementation feasibility in power-constrained form factors. (C) 2020 The Authors

An implementation of activity detection for grant-free massive machine type communication is presented. The implemented algorithm is based on coordinate descent which shows a rapid convergence time. A number of modifications to the original algorithm is proposed to allow efficient implementation in hardware. In addition, the implementation is based on fixed-point representation, and, hence, exhaustive word length simulations have been performed for the different processing steps.

Chromatic dispersion is one of the error sources limiting the transmission capacity in coherent optical communication that can be mitigated with digital signal processing. In this paper, the current status and plans of implementation of chromatic dispersion compensation (CDC) filters on FPGAs are discussed. As these high-speed filters are most efficiently implemented in the frequency-domain, different approaches for high-speed FFT-based architectures are considered and preliminary results of fully parallel FFT implementation by utilizing FPGA hardware features are presented.

We perform exploratory ASIC design of key DSP and FEC units for 400-Gbit/s coherent data-center interconnect receivers. In 22-nm CMOS, the considered units together dissipate 5 W, suggesting implementation feasibility in power-constrained form factors.

In this work, a processing architecture for grant-free machine type communication based on compressive sensing is proposed. The architecture can be adapted for a number of parameters. An instantiation for 128 terminals and 96 antennas is implemented. Without memories it consumes 1.52 W and occupies and area of 5.1 mm(2) in a 28 nm SOI CMOS process. The implemented instance can process about 10k messages per second, each containing four bits.

Massive MIMO is key technology for the upcoming fifth generation cellular networks (5G), promising high spectral efficiency, low power consumption, and the use of cheap hardware to reduce costs. Previous work has shown how to create a distributed processing architecture, where each node in a network performs the computations related to one or more antennas. The required total number of antennas, M, at the base station depends on the number of simultaneously operating terminals, K. In this work, a flexible node architecture is presented, where the number of terminals can he traded for additional antennas at the same node. This means that the same node can be used with a wide range of system configurations. The computational complexity, along with the order in which to compute incoming and outgoing symbols is explored.

This paper presents an area-efficient fast Fouriertransform (FFT) processor for orthogonal frequency-division multiplexing systems based on multi-path delay commutator architecture. This paper proposes a data scheduling scheme to reduce the number of complex constant multipliers. The proposed mixed-radix multi-path delay commutator FFT processor can support 128-, 256-, and 512-point FFT sizes. The proposed processor was synthesized using the Samsung 65-nm CMOS standard cell library. The proposed processor with eight parallel data paths can achieve a high throughput rate of up to 2.64 GSample/s at 330 MHz.

This work presents an extension of Karatsuba's method to efficiently use rectangular multipliers as a base for larger multipliers. The rectangular multipliers that motivate this work are the embedded 18x25-bit signed multipliers found in the DSP blocks of recent Xilinx FPGAs: The traditional Karatsuba approach must under-use them as square 18x18 ones. This work shows that rectangular multipliers can be efficiently exploited in a modified Karatsuba method if their input word sizes have a large greatest common divider. In the Xilinx FPGA case, this can be obtained by using the embedded multipliers as 16x24 unsigned and as 17x25 signed ones.The obtained architectures are implemented with due detail to architectural features such as the pre-adders and post-adders available in Xilinx DSP blocks. They are synthesized and compared with traditional Karatsuba, but also with (non-Karatsuba) state-of-the-art tiling techniques that make use of the full rectangular multipliers. The proposed technique improves resource consumption and performance for multipliers of numbers larger than 64 bits.

In optical communication the non-ideal properties of the fibers lead to pulse widening from chromatic dispersion. One way to compensate for this is through digital signal processing. In this work, two architectures for compensation are compared. Both are designed for 60 GSa/s and 512 filter taps and implemented in the frequency domain using FFTs. It is shown that the high-speed requirements introduce constraints on possible architectural choices. Furthermore, the theoretical multiplication complexity estimates are not good predictors for the energy consumption. The results show that the implementation with 10% more multiplications per sample has half the power consumption and one third of the area consumption. The best architecture for this specification results in a power consumption of 3.12 W in a 65 nm technology, corresponding to an energy per complex filter tap of 0.10 mW/GHz.

Lifting-based complex multiplications and rotations are integer invertible, i.e., an integer input value is mapped to the same integer output value when rotating forward and backward. This is an important aspect for lossless transform-based source coding, but since the structure only require three real-valued multiplications and three real-valued additions it is also a potentially attractive way to perform complex multiplications when the coefficient has unity magnitude. In this work, we consider two aspects of these structures. First, we show that both the magnitude and angular error is dependent on the angle of input value and derive both exact and approximated expressions for these. Second, we discuss how to design such structures without the typical separation into three subsequent matrix multiplications. It is shown that the proposed design method allows many more values which are integer invertible, but can not be separated into three subsequent matrix multiplications with fixed-point values. The results show good correspondence between the error approximations and the actual error as well as a significantly increased design space.

Massive MIMO-systems have received considerable attention in recent years as an enabler in future wireless communication systems. As the idea is based on having a large number of antennas at the base station it is important to have both a scalable and distributed realization of such a system to ease deployment. Most work so far have focused on the theoretical aspects although a few demonstrators have been reported. In this work, we propose a base station architecture based on connecting the processing nodes in a K-ary tree, allowing simple scalability. Furthermore, it is shown that most of the processing can be performed locally in each node. Further analysis of the node processing shows that it should be enough that each node contains one or two complex multipliers and a few complex adders/subtracters operating at some hundred MHz. It is also shown that a communication link of some Gbps is required between the nodes, and, hence, it is fully feasible to have one or a few links between the nodes to cope with the communication requirements.

In this work we explore the trade-offs between established algorithms for symmetric matrix inversion for fixed-point hardware implementation. Inversion of symmetric positive definite matrices finds applications in many areas, e.g. in MIMO detection and adaptive filtering. We explore computational complexity and show simulation results where numerical properties are analyzed. We show that LDL^T decomposition combined with equation system solving are the most promising algorithm for fixed-point hardware implementation. We further show that simply counting the number of operations does not establish a valid comparison between the algorithms as the required word lengths differ significantly.

This paper considers frequency-domain implementation of finite-length impulse response filters. In practical fixed-point arithmetic implementations, the overall system corresponds to a time-varying system which can be represented with either a multirate filter bank, and the corresponding distortion and aliasing functions, or a periodic time-varying impulse-response representation or, equivalently, a set of impulse responses and the corresponding frequency responses. The paper provides systematic derivations and analyses of these representations along with design examples. These representations are useful when analyzing the effect of coefficient quantizations as well as the use of shorter DFT lengths than theoretically required.

The most challenging step of implementing particle filtering is the resampling step which replicates particles with large weights and discards those with small weights. In this paper, we propose a generic architecture for resampling which uses double multipliers to avoid normalization divisions and make the architecture  equally efficient for non-powers-of-two number of particles. Furthermore, the complexity of resampling is greatly affected by the size of memories used to store weights. We illustrate that by storing the original weights instead of their cumulative sum and calculating them online reduces the total complexity, in terms of area, ranging from 21% to 45%, while giving up to 50% reduction in memory usage.

This paper analyzes the limits of FFT performance on FPGAs. For this purpose, a FFT generation tool has been developed. This tool is highly parameterizable and allows for generating FFTs with different FFT sizes and amount of parallelization. Experimental results for FFT sizes from 16 to 65536, and 4 to 64 parallel samples have been obtained. They show that even the largest FFT architectures fit well in today's FPGAs, achieving throughput rates from several GSamples/s to tens of GSamples/s.

This paper presents a reconfigurable FFT architecture for variable-length and multi-streaming WiMax wireless standard. The architecture processes 1 stream of 2048-point FFT, up to 2 streams of 1024-point FFT or up to 4 streams of 512-point FFT. The architecture consists of a modified radix-2 single delay feedback (SDF) FFT. The sampling frequency of the system is varied in accordance with the FFT length. The latch-free clock gating technique is used to reduce power consumption. The proposed architecture has been synthesized for the Virtex-6 XCVLX760 FPGA. Experimental results show that the architecture achieves the throughput that is required by the WiMax standard and the design has additional features compared to the previous approaches. The design uses 1% of the total available FPGA resources and maximum clock frequency of 313.67 MHz is achieved. Furthermore, this architecture can be expanded to suit other wireless standards.

Many contemporary FPGAs have introduced a pre-adder before the hard multipliers, primarily aimed at linear-phase FIR filters. In this work, structural modifications are proposed with the aim of reducing the LUT resource utilization and, finally, using the pre-adder for implementing single path delay feedback pipeline FFTs. The results show that two thirds of the LUT resources can be saved when the pre-adder has bypass functionality, as in the Xilinx 6 and 7 series, compared to a direct mapping.

This paper presents a 512-point feedforward FFT architecture for wireless personal area network (WPAN). The architecture processes a continuous flow of 8 samples in parallel, leading to a throughput of 2.64 GSamples/s. The FFT is computed in three stages that use radix-8 butterflies. This radix reduces significantly the number of rotators with respect to previous approaches based on radix-2. Besides, the proposed architecture uses the minimum memory that is required for a 512-point 8-parallel FFT. Experimental results show that besides its high throughput, the design is efficient in area and power consumption, improving the results of previous approaches. Specifically, for a wordlength of 16 bits, the proposed design consumes 61.5 mW and its area is 1.43 mm².

In this work a systematic method to generate all possible fast Fourier transform (FFT) algorithms is proposed based on the relation to binary trees. The binary tree is used to represent the decomposition of a discrete Fourier transform (DFT) into sub-DFTs. The radix is adaptively changed according to compute sub-DFTs in proposed decomposition. In this work we determine the number of possible algorithms for 2ⁿ-point FFTs with radix-2 butterfly operation and propose a simple method to determine the twiddle factor indices for each algorithm based on the binary tree representation.

Matrix inversion is sensitive towards the number representation used. In this paper simulations of matrix inversion with numbers represented in the fixed-point and logarithmic number systems (LNS) are presented. A software framework has been implemented to allow extensive simulation of finite wordlength matrix inversion. Six different algorithms have been used and results on matrix condition number, wordlength, and to some extent matrix size are presented. The simulations among other things show that the wordlength requirements differ significantly between different algorithms in both fixed-point and LNS representations. The results can be used as a starting point for a matrix inversion hardware implementation.

Matrix inversion is a key operation in for instance adaptivefilters and MIMO communication system receivers. For ill-conditionedchannel matrices long wordlengths are required for fixed-point implementationof matrix inversion. In this work, the wordlength/error tradeoffsfor matrix inversion using different algorithms with fixed-point andlogarithmic number systems (LNS) are considered. LNS provides higherresolution for small numbers and a larger dynamic range. Also, it willalter the cost of the basic operations in the algorithms. The results showthat also the wordlength required to achieve a comparable error differsignificantly between different algorithms and for most algorithms isreduced for LNS compared to fixed-point.

Frequency-response masking (FRM) is a set of techniques for lowering the computational complexity of narrow transition band FIR filters. These FRM use a combination of sparse periodic filters and non-sparse filters. In this work we consider the implementation of these filters in a time-multiplexed manner on FPGAs. It is shown that the proposed architectures produce lower complexity realizations compared to the vendor provided IP blocks, which do not take the sparseness into consideration. The designs are implemented on a Virtex-6 device utilizing the built-in DSP blocks.

In this work a new technique for design of narrow-band and wide-band linear-phase finite-length impulse response (FIR) frequency-response masking based filters is introduced. The technique is based on a sparse FIR filter design method for both the model (bandedge shaping) filter as well as the masking filter using mixed integer linear programming optimization. The proposed technique shows promising results for realization of efficient low arithmetic complexity structures.

In this work, a method for estimation of the switching activity in integrators is presented. To achieve low power, it is always necessary to develop accurate and efficient methods to estimate the switching activity. The switching activities are then used to estimate the power consumption. In our work, the switching activity is first estimated for the general purpose integrators and then it is extended for the estimation of switching activity in cascaded integrators in CIC filters.

In this paper, we propose higher point FFT (fast Fourier transform) algorithms for a single delay feedback pipelined FFT architecture considering the 4096-point FFT. These algorithms are different from each other in terms of twiddle factor multiplication. Twiddle factor multiplication complexity comparison is presented when implemented on Field-Programmable Gate Arrays (FPGAs) for all proposed algorithms. We also discuss the design criteria of the twiddle factor multiplication. Finally it is shown that there is a trade-off between twiddle factor memory complexity and switching activity in the introduced algorithms.

In this paper, we propose equivalent radix-2² algorithms and evaluate them based on twiddle factor switching activity for a single delay feedback pipelined FFT architecture. These equivalent pipeline FFT algorithms have the same number of complex multipliers with the same resolution as the radix-2². It is shown that the twiddle factor switching activity of the equivalent algorithms is reduced with up to 40% for some of the equivalent algorithms derived for N = 256.

An optimization algorithm for the design of puncturing patterns for low-density parity-check codes is proposed. The algorithm is applied to the base matrix of a quasi-cyclic code, and is expanded for each block size used. Thus, storing puncturing patterns specific to each block size is not required. Using the optimization algorithm, the number of 1-step recoverable nodes in the base matrix is maximized. The obtained sequence is then used as a base to obtain longer puncturing sequences by a sequential increase of the allowed recovery delay. The proposed algorithm is compared to one previous greedy algorithm, and shows superior performance for high rates when the heuristics are applied to the base matrix in order to create block size-independent puncturing patterns.

The core of many DSP tasks is Multiplication ofone data with several constants, i.e. in Digital filtering, image processing DCT and DFT. The Modern Portable equipments like Cellular phones and MP3 players which has DSP circuits,involve large number of multiplications of one variable with several constants (MCM) which leads to large area, delay and energy consumption in hardware. Multiplication operation can be realized using addition/subtraction and shifts without general multipliers. Different number representations are used in MCM algorithms and there are differnet views about different representations. Some of the authors termed the Canonic Signed Digit (CSD) representation as better for subexpression sharing. We have compared the results of CSD and Binary representations using our Generalized MCM Algorithm on Random Matrices and come to conclusion that binary representation is better compared to CSD when a system has multiple inputs and multiple outputs.

In this work, we analyze different approaches to store the coefficient twiddle factors for different stages of pipelined Fast Fourier Transforms (FFTs). The analysis is based on complexity comparisons of different algorithms when implemented  on Field-Programmable Gate Arrays (FPGAs) and ASIC for different radix-2^i algorithms. The objective of this work is to investigate the best possible combination for storing the coefficient twiddle factor for each stage of the pipelined FFT.

In this work, we propose a switching activity model for constant multipliers. The model can also be used for other architectures that are composed by full adders. Hence, the proposed model is suitable to be used in power consumption aware design algorithms. An important category is algorithms for the multiple-constant multiplication (MCM) problem. The model is shown to agree well with simulations, especially for carry-save arithmetic.

Input switching activity is one of the deciding factors for power consumption in digital signal processing components. For accurate power estimation, it is essential to have knowledge about the switching activity in the input signal, including how this activity changes in different environments, e.g., in the presence of noise. The dual bit type (DBT) method aims at characterizing the bit-level switching activity in a signal, using signal statistics. However, the DBT method requires that the correlation coefficient and switching activity for the most significant bit of the signal are available. In this paper we give an expression for direct calculation of the correlation coefficient for the most significant bit in a signal, using the word-level correlation coefficient. Using simulation results we examine the accuracy of the given method to calculate the switching activity and correlation coefficient for the most significant bit. Furthermore, we derive expressions for accurately calculating the variance and word-level correlation coefficient for a correlated signal, when an additional noise of a given variance is added to the signal. This can be used to estimate the bit-level switching activity in a signal in the presence of noise. Finally, based on this we study the impact the additional noise has on the switching activity of the resulting signal.

When hardware for implementing elementary functions is discussed it is often stated that for "small enough" tables it is possible to just synthesize the HDL description to standard cells. In this work we investigate this fact and show that the resulting cell area primarily depends on the smallest of the number of input and output bits, while the contribution of the larger of the two bit-widths is significantly smaller.

In this work we present the design and implementation of a decimation filter for an audio range AE-modulator. The architecture is based on a dual wordlength multiply-accumulate (MAC) unit to handle the reduced wordlength of the input. Each stage is composed of FIR filters which are mapped to the MAC unit. The design trade-offs and decisions for co-design of architecture and filters are discussed.

In this work we propose a switching activity model for single adder multipliers. This correspond to the case where a signal is added to a shifted version of itself, which is a common part in multiple constant multiplication (MCM). Hence, the proposed model is suitable to be used in power consumption aware MCM algorithms. The model is shown to agree well with simulations, and for the studied test cases a maximum error of 0.26% is obtained.

Implementation of FIR filters using shift-and-add multipliers has been an active research area for the last decade. However, almost all algorithms so far has been focused on reducing the number of adders and subtractors, while little effort was put on the bit-level implementation. In this work we propose a method to optimize the number of full adders and half adders required to realize a given number of additions. We present results which show that both area and power consumption can be reduced using the proposed method.

When designing thereduction tree of a parallel multiplier, we can exploit a largeintrinsic freedom for the interconnection order of partialproducts. The transition activities vary significantly fordifferent internal partial products. In this work we propose amethod for generation of power-efficient parallel multipliers insuch a way that its partial products are connected to minimizeactivity. The reduction tree is designed progressively. A SimulatedAnnealing optimizer uses power cost numbers from a speciallyimplemented probabilistic gate-level power estimator and selects apower-efficient solution for each stage of the reduction tree. VHDLsimulation using ModelSim shows a significant reduction in theoverall number of transitions. This reduction ranges from 15% up to32% compared to randomly generated reduction trees and is achievedwithout any noticeable area or performanceoverhead.

The Farrow structure can be used for efficient realization of adjustable fractional-delay finite-length impulse response (FIR) filters, but, nevertheless, its implementation complexity grows rapidly as the bandwidth approaches the full bandwidth. To reduce the complexity, a multirate approach can be used. In this approach, the input signal is first interpolated by a factor of two via the use of a fixed half-band linearphase FIR filter. Then, the actual fractional-delay filtering takes place. Finally, the so generated signal is downsampled to retain the original input/output sampling rate. In this way, the bandwidth of the fractional-delay filter used is halved compared to the overall bandwidth. Because the complexity of halfband linear-phase FIR filter interpolators is low, the overall complexity can be reduced. In this paper, we present more implementation details, design trade-offs, and comparisons when the filters are implemented using multiple constant multiplication techniques, which realize a number of constant multiplications with a minimum number of adders and subtracters.

In this work a novel approach for approximating elementary functions is presented. By rewriting the function as a sum of weighted bit-products an efficient implementation is obtained. For most functions a majority of the bit-products can be neglected and still obtain good accuracy. The method is suitable for high-speed implementation of fixed-point functions.

In this work an approach to converting a number in two's complement representation to a minimum signed-digit representation is proposed. The novelty in this work is that this conversion is done from left-to-right and right-to-left concurrently. Hence, the execution time is significantly decreased, while the area overhead is small.

In this work amodel for estimation of the switching activity in ripple-carryadders is presented. The model is based on word-level statistics,such as mean, variance, and correlation, of the two input signalsto be added. It is shown that the proposed model gives accurateresults when the two-s-complement represented inputs are realworld signals.

In this work a novel architecture suitable for high-speed FIR decimation filters for single-bit sigma-delta modulation is proposed. By using efficient data and coefficient representation the total number of partial products is reduced leading to low power consumption. The work is focused on filters designed based on cascaded comb filters, although the approach is applicable to any FIR filter.

Recently, a novel technique to compute sine and cosine has been proposed. By rewriting the expressions using trigonometric equations a weighted sum of bit-products is used to compute the values. This can then be mapped onto a bit-product generator followed by an adder tree. This provides an efficient architecture that can be pipelined to an arbitrary degree. It was shown in previous work that it is possible to remove a large portion of the bit-products and still obtain accurate results. The objective of this work is to study the effects of this removal and also the finite wordlength representation of the weights. Furthermore, optimization problems are formulated that can be used to minimize the maximum absolute error, the average absolute error, and the mean square error for the output values, respectively, as well as implementation complexity under error constraints.

Recently, a noveltechnique to compute sine and cosine has been proposed. Byrewriting the expressions using trigonometric equations a weightedsum of bit-products are used to compute the values. This can thenbe mapped onto a bit-product generator followed by an adder tree.This provides an efficient architecture that can be pipelined to anarbitrary degree. It was shown in previous work that it is possibleto remove a large portion of the bit-products and still obtainaccurate results. The effects of this removal and also the finiteworldlength representation of the weights has also been discussedin previous work. The objective of this work is to study differentways to split the architecture into sub-blocks that may be disabledto decrease the power consumption.

Low-density parity-check codes have recently received extensive attention as a forward error correction scheme in a wide area of applications. The decoding algorithm is inherently parallelizable, allowing communication at high speeds. One of the main disadvantages, however, is large memory requirements for interim storing of decoding data. In this paper, we investigate the performance of a hybrid decoding algorithm, using an approximating early decision algorithm and a regular probability propagation algorithm. When the early decision algorithm fails, the block is re-decoded using a probability propagation decoder. As almost all errors are detectable, the error correction performance of the hybrid algorithm is negligibly detoriated. However, simulations still achieve a 32% decrease of memory accesses.

We investigate amodification to the sum-product algorithm used for decodinglow-density parity-check (LDPC) codes. The sum-product algorithm isalgorithmically simple and highly parallelizable, but suffers fromhigh memory usage, making LDPC codes unsuitable for usage inbattery powered devices such as cell phones and PDAs.The proposed modification defines a measure of bit reliabilitiesduring the decoding process. Whenever the reliability of a bit isover a certain threshold, the bit is declared decided, and itsmessages are no longer calculated. We give experimental results forwhite Gaussian channels, and show that the amount of memoryaccesses can be substantially reduced, while performance does notsuffer significantly. At a bit error rate of 10^-4, the number ofmemory accesses is halved, while the required transmitter powerincreases about 0.3 dB.

We present two coding techniques for reducing the power dissipation in deep sub-micron, parallel data buses. The techniques differ in their parameter values and are suitable in different scenarios. In both cases typical reduction in power dissipation is 20%.

In this paper we discuss implementation of low-complexity FIR filters using difference methods. By realizing the differences between coefficients and from them the actual coefficients, the complexity of the filter implementations can be reduced. Here two different methods are proposed for selecting the differences. Both methods can be implemented with low execution times, making it possible to include them in the search for quantized filter coefficients.

In this paper we propose a method for implementation of multiple constant multiplications, as used in, for example, FIR filters. The method is shifted difference coefficient method where the differences are selected using a minimum spanning tree. By finding a minimum spanning tree of an undirected graph, corresponding to the coefficients, an implementation of a multiple constant multiplication block with low arithmetic complexity is obtained. There are algorithms that find a minimum spanning tree in polynomial time, making the proposed method computational efficient. We also propose that the differences are computed on odd coefficients only. This reduces the number of adders in an implementation further, compared to other difference coefficient methods. Several stages of differences, i.e., a set of differences is used to compute a new set of higher order differences, may also be used. We show that the proposed method give optimal, or close to optimal, results with respect to the number of additions required for a number of FIR filter implementations.

In this work we investigate the possibilities to minimize the complexity of bit-serial constant-coefficient multipliers. This is done in terms of number of required building blocks, which includes adders and flip-flops. The multipliers are described using a graph representation. We show that it is possible to find a minimum set of graphs that are required to get optimal results for the different multiplier types. The complexity cost for these multipliers are then investigated. Most results are compared to multipliers that adopt the commonly used canonic signed-digit representation.

This paper introduces Mth-band linear-phase FIR filter interpolators and decimators utilizing the Farrow structure. In these new overall structures, each polyphase component (except for the pure delay term) is a Farrow structure with a distinct fractional delay. The overall structures can therefore be implemented using only one set of linear-phase FIR subfilters and one set of multipliers that correspond to the distinct fractional delays. Many of these multiplier coefficients are trivial and it is possible to further reduce the complexity by utilizing symmetries. The proposed converter structures are more efficient than conventional single-stage converters structures are more efficient than conventional single-stage converters but less efficient than multistage converters in terms of arithmetic operations required per sample. However, the main advantages of the proposed structures are that they can be used also for conversions with prime number and that they are flexible as to the conversion factors. In particular, they can simultaneously implement several converters at a low cost. The multistage converters are not fully flexible since they can be designed using linear programming which generates optimum filters in the minimax sense. Design examples are included.

In this paper, a digit-serial multiplier based on shift-accumulation (DSAAM) [1] is compared to a digit-serial/parallel multiplier (S|/P_pipe) [2]. Both the studied multipliers can be pipelined to an arbitrary degree and are, therefore, well suited for high-throughput implementation. In our study bit-level pipelining was considered. Neither of the multipliers have been implemented in a deep-submicron technology previously, which motivates our study. The multipliers were implemented using a 0.18 μm standard cell technology, and the area, throughput and current consumptionwas analyzed. It was concluded that the DSAAM can be implemented with a lower latency than the (S/P_pipe, leading to a higher throughput and lower area and current consumption. Onaverage the area and current consumption of the DSAAM is 50% and 52% lower than for the S/P_pipe, respectively. Furthermore, the throughput of the DSAAM is 37% higher.

In this paper a novel approach for realizing constant coefficient matrix multiplication using few additions and subtractions is proposed. This method is applicable in, e.g., FIR filter banks, transforms, and polyphase form FIR filters for sample rate changes. Examples show that the proposed method yields good results compared to realizing the matrix multiplication by utilizing multiple coefficient multiplication techniques for the rows or columns separately.

Relationships are examined between two traditional strategies used to design "multiplier blocks": graphical methods and common subexpression elimination (CSE), four applications: single multipliers, multiplier blocks (several products of a single multiplicand), FIR filters and matrix multipliers are compared. A new representation shows how graphical designs can be extracted from CSE designs. Algorithms for both approaches are compared. A new graphical algorithm for FIR filter design and new results for CSE in the multiple product case are presented so comparison can be made for all applications. We conclude that for simpler problems, graphical methods are best, while CSE works better for the more complex problems

In this work we formulate a mixed integer linear programming (MILP) problem that minimizes the number of signed-power-of- two (SPT) terms given a filter specification for linear-phase frequency-response masking (FRM) filters. The proposed method designs the filters in two steps. The model filter and the masking filters are designed separately, but subject to each other. Hence, it is not guaranteed that the global minimum is obtained. However, each solution is optimal given the other filter(s), and iteration may improve the overall solution. The filter design problems are formulated using normalized peak ripple magnitude (NPRM), which for FRM filters introduces some implications, which is also discussed in this work.

The basic elements of an algorithm for designing multiplier blocks for matrices are presented. The new algorithm often produces results superior to the best of the older algorithms applied only to columns.

By introducing simplifications to multiplier graphs we extend the previous work on minimum adder multipliers to five adders and show that this is enough to express all coefficients up to 19 bits. The average savings are more than 25% for 19 bits compared with CSD multipliers. The simplifications include addition reordering and vertex reduction to see that different graphs can generate the same coefficient sets. Thus, fewer graphs need to be evaluated. A classification of the graphs reduces the effort to search the coefficient space further.

In this work, we introduce a novel approach to digit-serial/parallel multiplication. This general class of multipliers is based on shift-accumulation which also makes the approach suitable for implementation of shift-accumulators in distributed arithmetic. As a variable in the design process, the maximal number of cascaded full-adders can be selected. Thus, it is possible to, as a special case, obtain a bit-level pipelined multiplier. Both general and fixed coefficient multiplication is considered. The hardware complexity is low compared with other approaches.

In this work we formulate a mixed integer linear programming (MILP) problem for designing linear-phase FIR filters with low arithmetic complexity. By incorporating subexpression sharing in the problem formulation, the number of adders will be lower compared with previous approaches, where minimizing the number of non-zero bits of the coefficients has been the objective.

Arithmetic transformations for increased maximal sample rate of bit-parallel lattice wave digital filters implemented with carry-save arithmetic are proposed. The purpose is to increase the throughput in order to allow a reduction of the power consumption through supply voltage scaling. A lattice wave digital filter can be composed of first- and second-order allpass sections which are recursive structures. This sets a bound on the maximal sample rate. The proposed transformations reduce the latency of the critical loop by reordering of arithmetic operations. The resulting structure is numerically equivalent to the original structure. Hence, the favourable properties of lattice wave digital filters, such as guaranteed stability, low coefficient sensitivity, and good dynamic range, are retained. An example of a filter implementation where the proposed transformations are applied is presented. The maximal sample rate for this example was improved by about 40% at the expense of a 10% increase of the area.

In this thesis we discuss various issues involving the design path for low power design of frequency-selective digital filters. As recursive filters have a bound on the minimal iteration period, T_min we focus on these. Implementations that obtain T_min are known as maximally fast.

The main idea to obtain a low power implementation is to use a maxi­mally fast implementation and trade any excess speed for lower power consumption by decreasing the power supply voltage.

We show that using three-port adaptor allpass sections and constrained third-order allpass sections for implementation of maximally fast lattice wave digital filters are advantageous compared with second-order Richards' structures.

We further show that maximally fast ladder wave digital filters can be efficiently implemented using the same techniques as for lattice wave digital filters, despite that they have a more complex structure with many loops.

We also show that maximally fast digital filters can be implemented using a numerically equivalent state-space representation and distributed arithmetic. As the latency of distributed arithmetic is dependent on the number of fractional bits of the longest coefficient, it may decrease the performance if the critical loop is through one of the shorter coefficients. However, we show that by modifying the contents of the ROM we can achieve T_min independent of the other coefficients in the ROM.

Further, we introduce single filter frequency masking. In this approach we substitute the different subfilters in narrow-band frequency masking and frequency-response masking structures to identical subfilters (except for the periodicity). By mapping the subfilters to the same hardware structure using folding an efficient hardware implementation is obtained. This approach is discussed for narrow-band lowpass recursive and FIR filters, and for frequency-response masking structures based on FIR filters.