Genetic approach to design of multiplierless FIR filters

The design of multiplierless FIR filters using genetic algorithms is presented. The proposed algorithm uses simple operators (reproduction, crossover, and mutation) to search through the discrete coefficient space of predefined power-of-two coefficients. This approach has proved to be highly effective and outperformed existing multiplierless FIR design techniques.<>     

Discrete Lagrangian Methods for Designing Multiplierless Two-Channel PR-LP Filter Banks

In this paper, we present a new search method based on the theory of discrete Lagrange multipliers for designing multiplierless PR (perfect reconstruction) LP (linear phase) filter banks. To satisfy the PR constraints, we choose a lattice structure that, under certain conditions, can guarantee the resulting two filters to be a PR pair. Unlike the design of multiplierless QMF filter banks that represents filter coefficients directly using PO2 (powers-of-two) form (also called Canonical Signed Digit or CSD representation), we use PO2 forms to represent the parameters associated with the lattice structure. By representing these parameters as sums or differences of powers of two, multiplications can be carried out as additions, subtractions, and shifts. Using the lattice representation, we decompose the design problem into a sequence of four subproblems. The first two subproblems find a good starting point with continuous parameters using a single-objective, multi-constraint formulation. The last two subproblems first transform the continuous solution found by the second subproblem into a PO2 form, then search for a design in a mixed-integer space. We propose a new search method based on the theory of discrete Lagrange multipliers for finding good designs, and study methods to improve its convergence speed by adjusting dynamically the relative weights between the objective and the Lagrangian part. We show that our method can find good designs using at most four terms in PO2 form in each lattice parameter. Our approach is unique because our results are the first successful designs of multiplierless PR-LP filter banks. It is general because it is applicable to the design of other types of multiplierless filter banks.     

Multiplierless multilayer feedforward neural network design suitable for continuous input-output mapping

A method for designing a multiplierless multilayer feedforward neural network (MFNN) suitable for continuous input-output mapping is presented. When tested with noisy vectors, the network can retain a similar recall accuracy as the corresponding MFNN with continuous weights. The advantages of the design method include faster computational speed and reduced digital hardware cost.<>     

CSDC: a new complexity reduction technique for multiplierless implementation of digital FIR filters

We present a computation reduction technique called computation sharing differential coefficient (CSDC) method, which can be used to obtain low-complexity multiplierless implementation of finite-impulse response (FIR) filters. It is also applicable to digital signal processing tasks involving multiplications with a set of constants. The main component of our proposed CSDC method is to combine the strength of the augmented differential coefficient approach and subexpression sharing. Exploring computation reuse through algorithmic equivalence, the augmented differential coefficient approach greatly expands the design space by employing both differences and sums of filter coefficients. The expanded design space is represented by an undirected and complete graph. The problem of minimizing the adder cost (the number of additions/subtractions) for a given filter is transformed into a problem of searching for an appropriate subexpression set that leads to a minimal adder cost. A heuristic search algorithm based on genetic algorithm is developed to search for low-complexity solutions over the expanded design space in conjunction with exploring subexpression sharing. It is shown that up to 70.1% reduction in the adder cost can be obtained over the conventional multiplierless implementation. Comparison with several existing techniques based on the available data shows that our method yields comparable results for multiplierless FIR filter implementation.     

A Pulsed Neural Network With On-Chip Learning and Its Practical Applications

This paper proposes a new model for the pulsed neural network. In this model, the information is coded in terms of firing times of pulses that are generated by the neuron. The pulses transmit through the network and excite the dynamics of the neuron. Their synchronism is utilized to design the architecture of the neural network such that it acts as a radial basis function (RBF) network. A new network-learning algorithm is also developed for this pulsed RBF network. The RBF neurons are generated based on the feature of the training data, and the synaptic delays can be adjusted to distribute these RBF neurons in the training data space. The pulse neural network has been implemented compactly with multiplierless approach for both the forward computation and learning algorithm with a field programmable gate array board. As an application demonstration, it is extended to a nonlinear look-up table and applied to estimate the friction occurs in a precision linear stage     

Digital Filter Design Using Computer Algebra Systems

Digital filter design can be performed very efficiently using modern computer tools. The drawback of the numeric-based tools is that they usually generate a tremendous amount of numeric data, and the user might easily lose insight into the phenomenon being investigated. The computer algebra systems successfully overcome some problems encountered in the traditional numeric-only approach. In this paper, we introduce an original approach to algorithm development and digital filter design using a computer algebra system. The main result of the paper is the development of an algorithm for an infinite impulse response (IIR) filter design that, theoretically, is impossible to be implemented using the traditional approach. We present a step-by-step procedure which includes derivations of closed-form expressions for (1) the transfer functions of the implemented digital filter which contains the algebraic loop; (2) the closed-form expression for computing the number of requested iteration steps; and (3) the error function representing the difference of the output sample values of the new filter and that of the conventional filter. We demonstrate how one can use some already-known multiplierless digital filter as a start-up filter to design a new digital filter whose passband edge frequency can be simply moved by using a single parameter. As a result, we obtain a multiplierless IIR filter, which belongs to the family of low-power digital filters where multipliers are replaced with a small number of adders and shifters.     

Complexity reduction of digital filters using shift inclusive differential coefficients

We present a graph theoretical methodology that reduces the implementation complexity of the multiplication of a constant vector and a scalar. The complexity of implementation is defined as the required amount of computations like additions. The proposed approach is called minimally redundant parallel (MRP) optimization and is mainly presented in a finite impulse response (FIR) filtering framework to obtain a low-complexity multiplierless implementation. The key idea is to expand the design space using shift inclusive differential coefficients (SIDCs) together with computation reordering using a graph theoretic approach to obtain maximal computation sharing. The problem is formulated using a graph in which vertices and edges represent coefficients and computational cost (number of resources). The multiplierless solution is obtained by solving a set cover problem on the vertices in the graph. A simple polynomial run time algorithm based on a greedy approach is presented. The proposed approach is compared with common-subexpression elimination to show slightly better results and is combined with it for further reduction of complexity. Simulation results show that 50-60% complexity reduction is achieved by only applying the MRP algorithm, and 70% complexity reduction is obtainable by combining it with common-subexpression elimination under a delay constraint of two or three.     

Design of multiplierless fir filters by multiple use of the same filter

A novel approach to the design of multiplierless filters, based on the ACF (amplitude change function), is discussed. The prototype filter chosen is a CCOS (the cascade of the cosine functions) which requires no multipliers and only some adders. The required filter specifications are met by multiple use of the same CCOS filter. Effects due to coefficient quantisation do not arise when using the new approach. No multipliers are required to implement this filter.<>     

Fast multiplierless approximations of the DCT with the liftingscheme

We present the design, implementation, and application of several families of fast multiplierless approximations of the discrete cosine transform (DCT) with the lifting scheme called the binDCT. These binDCT families are derived from Chen's (1977) and Loeffler's (1989) plane rotation-based factorizations of the DCT matrix, respectively, and the design approach can also be applied to a DCT of arbitrary size. Two design approaches are presented. In the first method, an optimization program is defined, and the multiplierless transform is obtained by approximating its solution with dyadic values. In the second method, a general lifting-based scaled DCT structure is obtained, and the analytical values of all lifting parameters are derived, enabling dyadic approximations with different accuracies. Therefore, the binDCT can be tuned to cover the gap between the Walsh-Hadamard transform and the DCT. The corresponding two-dimensional (2-D) binDCT allows a 16-bit implementation, enables lossless compression, and maintains satisfactory compatibility with the floating-point DCT. The performance of the binDCT in JPEG, H.263+, and lossless compression is also demonstrated     

普遍故障下神经网络隐层冗余容错的分析与应用

隐层神经元冗余是提高神经网络容错性的一个有效的方法,在神经网络分类器的容错设计中,这一方法得到了良好的效果,对单故障可以做到完全容错.但是这一应用仅仅只能应用于输出层为硬限幅函数的前向网络,并且只证明了对网络中单故障有效.在实际应用中,网络中的各个节点和权值的故障往往是普遍存在的,因此本文提出了一种隐层冗余结构,对普遍故障存在下隐层神经元冗余容错方法做以评估,得出的结论是应用这种隐层神经元冗余结构可以减小网络的全局故障率;并提出了针对一般前向神经网络的实用的隐层神经元容错方法,这种方法可以有效地提高网络在普遍故障下的容错能力.     

Improved design procedure for multiplierless FIR digital filters

An algorithm is presented for the design of finite impulse response filters, yielding filter coefficients that are either single powers of two, or sums or differences of two powers of two. In all cases tried this algorithm gives simpler realisations compared both to conventional design methods and to other multiplierless design algorithms.<>     

Multiplierless, Folded 9/7– 5/3 Wavelet VLSI Architecture

This brief proposes a multiplierless VLSI architecture for the famous 9/7 wavelet filters. The novelty of this architecture is the possibility to compute the 5/3 wavelet results into the 9/7 data path with a reduced number of adders compared to other solutions. The multiplierless architecture has been characterized in terms of performance through simulations into a JPEG2000 environment and compared to other solutions. Implementation on a 0.13-mum standard cell technology shows that the proposed architecture compared to other multiplierless architectures requires a reduced amount of logic with excellent performance.     

Two-stage CIC-based decimator with improved characteristics

A simple two-stage multiplierless cascaded-integrator-comb (CIC)-based decimator is presented. The first stage is a cascaded CIC filter whereas the second stage is a cascaded CIC filter and a second-order multiplierless compensator. The proposed decimator can be realised without filtering at high input rate by making use of the polyphase decomposition of the comb filter in the first stage. The proposed filter exhibits high aliasing attenuation and a low passband droop. The design parameters are the decimation factors, M ₁ and M ₂, numbers of cascaded CIC filters L and K, and parameter b of the compensator.     

A 3-V, 2%-mW multibit current-mode ΣΔ DAC with 100 dBdynamic range

The area ratio of analog to digital for mixed-mode chip has been inversely proportional to the process design rule for a given dynamic range objective, in contradiction to the LSI trend. This paper presents a design approach to realize a high degree of size reduction with process design rules for analog circuitry and a signal processing architecture for digital circuitry. A five-level current-mode ΣΔ digital-to-analog converter (DAC) system reveals full scale total harmonic: distortion plus noise (THD+N) of -90 dB and dynamic-range of 100 dB at 3 V (low power of 22 mW). Analog-area down-scaling can be accomplished by this architecture to be 1.09 mm², using 0.6-μm double-poly double-metal (DPDM) CMOS. For the digital filter, a pipeline instruction sequence with multiplierless architecture also gives small area of 1.98 mm²     

Common subexpression elimination algorithm for low-cost multiplierless implementation of matrix multipliers

The design of multiplierless implementations (which use only adders, subtracters and binary shifts) of fixed-point matrix multipliers is considered and a new common subexpression elimination method is described that recursively extracts signed two-term common subexpressions. Examples are given that show that the resulting adder-cost is significantly lower than for existing algorithms.     

Trigonometrical approach to design a simple wideband comb compensator

This paper presents a trigonometrical approach to design a simple second order wideband compensator of a comb decimation filter. The method is based on the similarity of the inverse passband comb characteristic and the squared sine function. The design parameter B, which is the amplitude of the squared sine function, depends only on the number K of the cascaded comb filters. Considering that the parameter B can be expressed in terms of only addition and shift operations, we may obtain a multiplierless filter. The proposed filter performs wideband compensation efficiently using a maximum of four additions/subtractions, and for a given K, can be applied to any value of the decimation factor M.     

Design of FIR Hilbert transformers using prescribed subfilters and nested FT technique

In this article, a transformation (subfilter) for designing finite impulse response (FIR) Hilbert transformers (HTs) is proposed. With our approach, except simple search procedures, neither optimisation nor any filter design algorithm is needed to obtain the transformation. The proposed subfilter requires only two multipliers regardless of the subfilter order. For the frequency transformation design, the purpose of the subfilter is to provide a “rough” shape of the desired HT; the two coefficients of the subfilter can be implemented as the form of sum of power of two (SOPOT) with only a few bits, thus leading to a multiplierless realisation. Moreover, by applying the transformation on the subfilter again, a technique named as nested frequency transformation (nested FT) is introduced. This technique can further reduce the number of multipliers needed in the overall HT.     

Design of Multiplierless Lattice QMF: Structure and Algorithm Development

In this brief, efficient multiplierless design of lattice quadrature mirror filter bank is presented. Previous work by the authors has shown that splitting each lattice stage into cascade of subrotations results in larger stopband attenuation of filter than the conventional direct quantization. This brief extends the work further by exploiting the subrotations which yield more flexible sum of signed powers-of-two quantization. This enables us to find more possible discrete representations, and hence to reduce the quantization error. Also, an algorithm for the efficient gathering of candidate discrete coefficients is developed, based on the trellis-based searching approach. It substantially alleviates the overheads of optimization program, especially when the wordlengths and the number of nonzero digits are large. Several design examples are provided to show that the proposed structure with the candidate gathering algorithm provides improved frequency response.     

Higher order Σ-Δ modulation encoding for design ofmultiplierless FIR filters

A technique is presented for the design of multiplierless FIR filters with canonical signed digit (CSD) coefficients based on higher-order Σ-Δ modulation with a CSD quantiser (Σ-Δ-CSD). The proposed algorithm requires little computational resources and is capable of designing more types of filters and providing better performance than the previously proposed first-order method     

一种高度并行无乘法器结构的二维IDCT协处理器设计

介绍了一种适用于MPEG-4视频简单层解压缩应用的二维IDCT协处理器。该处理器采用Loeffler架构的IDCT快速算法,并使用加法和移位运算代替IDCT快速算法中的浮点乘法运算单元,用高度并行流水VLSI结构加快数据处理速度,采用一维的IDCT单元的复用的方式来实现二维的IDCT运算。在满足处理速度和精度要求的基础上,利用较少的晶体管数目实现了一种高性能的二维IDCT处理器。该方案已经应用于一款SOC芯片中的硬件MMA(多媒体加速单元)中,IDCT的运算精度也得到了验证。