%Aksoy-TSP15, @Article{RefA, author = "Levent Aksoy and Paulo Flores and José Monteiro", title = "Exact and Approximate Algorithms for the Filter Design Optimization Problem", journal = TSP, volume = 63, number = 1, pages = " 142--154 ", month = JAN, year = 2015, abstract = "The filter design optimization (FDO) problem is For Revi defined as finding a set of filter coefficients which yields a filter design with minimum complexity, satisfying the filter constraints. It has received a tremendous interest due to the widespread application of filters. Assuming that the coefficient multiplications in the filter design are realized under a shift-adds architecture, the complexity is generally defined in terms of the total number of adders and subtractors. In this article, we present an exact FDO algorithm that can guarantee the minimum design complexity under the minimum quantization value, but can only be applied to filters with a small number of coefficients. We also introduce an approximate algorithm that can handle filters with a large number of coefficients using less computational resources than the exact FDO algorithm and find better solutions than existing FDO heuristics. We describe how these algorithms can be modified to handle a delay constraint in the shift-adds designs of the multiplier blocks and to target different filter constraints and filter forms. Experimental results show the effectiveness of the proposed algorithms with respect to prominent FDO algorithms and explore the impact of design parameters, such as the filter length, quantization value, and filter form, on the complexity and performance of filter designs.", keywords = "Finite Impulse Response (FIR) filters; Direct and trans- posed forms; Filter design optimization problem; Multiplierless design; Depth-first and local search methods; Delay reduction; Filter design and structures; DSP Algorithm implementation in hardware and software.", issn = "1053-587X", doi = "10.1109/TSP.2014.2366713" } %Aksoy-TODAES14, @Article{RefB, author = "Levent Aksoy and Paulo Flores and José Monteiro", title = "Multiplierless Design of Folded {DSP} Blocks", journal = TODAES, volume = 20, number = 1, pages = " 14:1--14:24 ", month = NOV, year = 2014, abstract = "This article addresses the problem of optimizing the implementation cost of the time-multiplexed constant multiplication (TMCM) operation which realizes the multiplication of an input variable by a single constant selected from a set of multiple constants at a time. It presents an efficient algorithm, called ORPHEUS, which finds a multiplierless TMCM design by sharing logic operators, i.e., adders, subtractors, adders/subtractors, and multiplexors (MUXes). Moreover, this article introduces folded design architectures for the digital signal processing (DSP) blocks, such as finite impulse response (FIR) filters and linear DSP transforms, and describes how these folded DSP blocks can be efficiently realized using TMCM operations optimized by ORPHEUS. Experimental results indicate that ORPHEUS can find better solutions than existing TMCM algorithms, yielding TMCM designs requiring less area. They also show that the folded architectures lead to alternative designs with significantly less area, but incurring an increase in latency and energy consumption, compared to the parallel architecture.", keywords = "Time-multiplexed constant multiplication; Folded architecture, multiplierless design; Area optimization; Finite Impulse Response (FIR) filter, Discrete Cosine Transform (DCT); Integer Cosine Transform (ICT); Folded architectures.", issn = "1084-4309", doi = "10.1145/2663343" } %Aksoy-TVLSI13, @Article{RefC, author = "Levent Aksoy and Cristiano Lazzari and Eduardo Costa and Paulo Flores and José Monteiro", title = "Design of Digit-Serial {FIR} Filters: Algorithms, Architectures, and a {CAD} Tool", journal = TVLSI, volume = 21, number = 3, pages = " 498--511 ", month = MAR, year = 2013, abstract = "In the last two decades, many efficient algorithms and architectures have been introduced for the design of low-complexity bit-parallel multiple constant multiplications (MCM) operation which dominates the complexity of many digital signal processing systems. On the other hand, little attention has been given to the digit-serial MCM design that offers alternative low-complexity MCM operations albeit at the cost of an increased delay. In this paper, we address the problem of optimizing the gate-level area in digit-serial MCM designs and introduce high-level synthesis algorithms, design architectures, and a computer-aided design tool. Experimental results show the efficiency of the proposed optimization algorithms and of the digit-serial MCM architectures in the design of digit-serial MCM operations and finite impulse response filters.", keywords = "0-1 Integer Linear Programming (ILP); Digit-Serial Arithmetic; Finite Impulse Response (FIR) Filters; Gate-Level Area Optimization; Multiple Constant Multiplications.", issn = "1063-8210", doi = "10.1109/TVLSI.2012.2188917", history = "Accepted and re-submitted on 2011-11-17" } %Aksoy-ICCAD12, @InProceedings{RefD, author = "Levent Aksoy and Eduardo Costa and Paulo Flores and José Monteiro", title = "Multiple Tunable Constant Multiplications: Algorithms and Applications", booktitle = ICCAD, pages = " 473--479 ", location = "San José, CA, USA", month = NOV # " 5--8, ", year = 2012, abstract = "The multiple constant multiplications (MCM) problem, that is defined as finding the minimum number of addition and subtraction operations required for the multiplication of multiple constants by an input variable, has been the subject of great interest since the complexity of many digital signal processing (DSP) systems is dominated by an MCM operation. This paper introduces a variant of the MCM problem, called multiple tunable constant multiplications (MTCM) problem, where each constant is not fixed as in the MCM problem, but can be selected from a set of possible constants. We present an exact algorithm that formalizes the MTCM problem as a 0-1 integer linear programming (ILP) problem when constants are defined under a number representation. We also introduce a local search method for the MTCM problem that includes an efficient MCM algorithm. Furthermore, we show that these techniques can be used to solve various optimization problems in finite impulse response (FIR) filter design and we apply them to one of these problems. Experimental results clearly show the efficiency of the proposed methods when compared to prominent algorithms designed for the MCM problem", keywords = "MTCM - Multiple Tunable Constant Multiplications; 0-1 ILP; Exact algorithm; Local search algorithm.", issn = "1092-3152", doi = "10.1145/2429384.2429482" } %Aksoy-MICPRO10, @Article{RefE, author = "Levent Aksoy and Ece Olcay Gunes and Paulo Flores", title = "Search algorithms for the multiple constant multiplications problem: Exact and approximate", journal = MICPRO, volume = 34, number = 5, pages = " 151--162 ", month = AUG, year = 2010, abstract = "This article addresses the multiplication of one data sample with multiple constants using addition/subtraction and shift operations, i.e., the multiple constant multiplications (MCM) operation. In the last two decades, many efficient algorithms have been proposed to implement the MCM operation using the fewest number of addition and subtraction operations. However, due to the NP-hardness of the problem, almost all the existing algorithms have been heuristics. The main contribution of this article is the proposal of an exact depth-first search algorithm that, using lower and upper bound values of the search space for the MCM problem instance, finds the minimum solution consuming less computational resources than the previously proposed exact breadth-first search algorithm. We start by describing the exact breadth-first search algorithm that can be applied on real mid-size instances. We also present our recently proposed approximate algorithm that finds solutions close to the minimum and is able to compute better bounds for the MCM problem. The experimental results clearly indicate that the exact depth-first search algorithm can be efficiently applied to large size hard instances that the exact breadth-first search algorithm cannot handle and the heuristics can only find suboptimal solutions.", keywords = "Multiple constant multiplications problem; Depth-first search; Breadth-first search; Graph-based algorithms; Finite Impulse Response filters.", issn = "0141-9331", doi = "10.1016/j.micpro.2009.10.001", note = "Special issue on selected papers from NORCHIP 2008." } %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%