TAILIEUCHUNG - Lecture VLSI Digital signal processing systems: Chapter 8 - Keshab K. Parhi

The main contents of this chapter include all of the following: Cook-toom algorithm and modified cook-toom algorithm, winograd algorithm and modified winograd algorithm, iterated convolution, cyclic convolution, design of fast convolution algorithm by inspection. | Chapter 8: Fast Convolution Keshab K. Parhi Chapter 8 Fast Convolution • Introduction • Cook-Toom Algorithm and Modified Cook-Toom Algorithm • Winograd Algorithm and Modified Winograd Algorithm • Iterated Convolution • Cyclic Convolution • Design of Fast Convolution Algorithm by Inspection Chap. 8 2 Introduction • Fast Convolution: implementation of convolution algorithm using fewer multiplication operations by algorithmic strength reduction • Algorithmic Strength Reduction: Number of strong operations (such as multiplication operations) is reduced at the expense of an increase in the number of weak operations (such as addition operations). These are best suited for implementation using either programmable or dedicated hardware • Example: Reducing the multiplication complexity in complex number multiplication: – Assume (a+jb)(c+dj)=e+jf, it can be expressed using the matrix form, which requires 4 multiplications and 2 additions: e c −d a f = d c ⋅ b – However, the number of multiplications can be reduced to 3 at the expense of 3 extra additions by using: ac − bd = a(c − d ) + d (a − b) ad + bc = b(c + d ) + d (a − b) Chap. 8 3 – Rewrite it into matrix form, its coefficient matrix can be decomposed as the product of a 2X3(C), a 3X3(H)and a 3X2(D) matrix: 0 0 1 0 c − d e 1 0 1 a s= = ⋅ 0 c + d 0 ⋅ 0 1 ⋅ = C ⋅ H ⋅ D ⋅ x b f 0 1 1 1 −1 0 d 0 • Where C is a post-addition matrix (requires 2 additions), D is a pre-addition matrix (requires 1 addition), and H is a diagonal matrix (requires 2 additions to get its diagonal elements) • – So, the arithmetic complexity is reduced to 3 multiplications and 3 additions (not including the additions in H matrix) In this chapter we will discuss two well-known approaches to the design of fast short-length convolution algorithms: the Cook-Toom algorithm (based on Lagrange Interpolation) and the Winograd Algorithm (based on .

• Điện - Điện tử
• VLSI Digital signal processing systems
• Digital signal
• Digital signal processing
• DSP systems
• Cook toom algorithm
• Fast convolution
• FIR Digital Filters
• Parallel processing
• Loop bound
• DSP programs
• Retiming formulation
• Applications of retiming
• Algorithm for unfolding
• Applications of unfolding
• Retiming for folding
• Systolic architecture design
• Projection vector
• Algorithmic strength reduction
• Parallel FIR filters
• Adaptive filters
• Parallel pecursive
• Round off noise
• State variable description
• Bit level arithmetic architectures
• Parallel multipliers
• Redundant arithmetic
• Redundant number representations
• Numerical strength reduction
• Multiple constant multiplication
• Low power design
• Programmable DSPs
• DSP applications