VLSI Digital Signal Processing Systems Design and Implementation

by Parhi, Keshab K.

• ISBN13: 9780471241867
• ISBN10: 0471241865
• Edition: 1st
• Format: Hardcover
• Copyright: 1999-01-05
• Publisher: Wiley-Interscience

Summary

An Instructor's Manual presenting detailed solutions to all the problems in the book is available from the Wiley editorial department.

Author Biography

<b>KESHAB K. PARHI</b> is Edgar F. Johnson Professor of Electrical and Computer Engineering at the University of Minne-sota in Minneapolis. Dr. Parhi is widely recognized for his work in the area of VLSI digital signal and image processing. In addition to publishing more than two hundred fifty papers and serving on the editorial boards of a number of professional journals, he has coauthored several books, most recently, Pipelined Lattice and Wave Digital Recursive Filters, and Digital Signal Processing for Multimedia Systems.

Table of Contents

Preface	xv
1 Introduction to Digital Signal Processing Systems	1	(42)
1.1 Introduction	1	(1)
1.2 Typical DSP Algorithms	2	(25)
1.3 DSP Application Demands and Scaled CMOS Technologies	27	(4)
1.4 Representations of DSP Algorithms	31	(9)
1.5 Book Outline	40	(1)
References	41	(2)
2 Iteration Bound	43	(20)
2.1 Introduction	43	(1)
2.2 Data-Flow Graph Representations	43	(2)
2.3 Loop Bound and Iteration Bound	45	(2)
2.4 Algorithms for Computing Iteration Bound	47	(8)
2.5 Iteration Bound of Multirate Data-Flow Graphs	55	(2)
2.6 Conclusions	57	(1)
2.7 Problems	58	(3)
References	61	(2)
3 Pipelining and Parallel Processing	63	(28)
3.1 Introduction	63	(1)
3.2 Pipelining of FIR Digital Filters	64	(5)
3.3 Parallel Processing	69	(5)
3.4 Pipelining and Parallel Processing for Low Power	74	(8)
3.5 Conclusions	82	(1)
3.6 Problems	83	(5)
References	88	(3)
4 Retiming	91	(28)
4.1 Introduction	91	(2)
4.2 Definitions and Properties	93	(2)
4.3 Solving Systems of Inequalities	95	(2)
4.4 Retiming Techniques	97	(15)
4.5 Conclusions	112	(1)
4.6 Problems	112	(6)
References	118	(1)
5 Unfolding	119	(30)
5.1 Introduction	119	(2)
5.2 An Algorithm for Unfolding	121	(3)
5.3 Properties of Unfolding	124	(3)
5.4 Critical Path, Unfolding, and Retiming	127	(1)
5.5 Applications of Unfolding	128	(12)
5.6 Conclusions	140	(1)
5.7 Problems	140	(7)
References	147	(2)
6 Folding	149	(40)
6.1 Introduction	149	(2)
6.2 Folding Transformation	151	(6)
6.3 Register Minimization Techniques	157	(6)
6.4 Register Minimization in Folded Architectures	163	(7)
6.5 Folding of Multirate Systems	170	(4)
6.6 Conclusions	174	(1)
6.7 Problems	174	(12)
References	186	(3)
7 Systolic Architecture Design	189	(38)
7.1 Introduction	189	(1)
7.2 Systolic Array Design Methodology	190	(2)
7.3 FIR Systolic Arrays	192	(9)
7.4 Selection of Scheduling Vector	201	(4)
7.5 Matrix-Matrix Multiplication and 2D Systolic Array Design	205	(5)
7.6 Systolic Design for Space Representations Containing Delays	210	(3)
7.7 Conclusions	213	(1)
7.8 Problems	213	(10)
References	223	(4)
8 Fast Convolution	227	(28)
8.1 Introduction	227	(1)
8.2 Cook-Toom Algorithm	228	(9)
8.3 Winograd Algorithm	237	(7)
8.4 Iterated Convolution	244	(2)
8.5 Cyclic Convolution	246	(4)
8.6 Design of Fast Convolution Algorithm by Inspection	250	(1)
8.7 Conclusions	251	(1)
8.8 Problems	251	(2)
References	253	(2)
9 Algorithmic Strength Reduction in Filters and Transforms	255	(58)
9.1 Introduction	255	(1)
9.2 Parallel FIR Filters	256	(19)
9.3 Discrete Cosine Transform and Inverse DCT	275	(10)
9.4 Parallel Architectures for Rank-Order Filters	285	(12)
9.5 Conclusions	297	(1)
9.6 Problems	297	(13)
References	310	(3)
10 Pipelined and Parallel Recursive and Adaptive Filters	313	(64)
10.1 Introduction	313	(1)
10.2 Pipeline Interleaving in Digital Filters	314	(6)
10.3 Pipelining in 1st-Order IIR Digital Filters	320	(5)
10.4 Pipelining in Higher-Order IIR Digital Filters	325	(14)
10.5 Parallel Processing for IIR filters	339	(6)
10.6 Combined Pipelining and Parallel Processing for IIR Filters	345	(3)
10.7 Low-Power IIR Filter Design Using Pipelining and Parallel Processing	348	(3)
10.8 Pipelined Adaptive Digital Filters	351	(16)
10.9 Conclusions	367	(1)
10.10 Problems	367	(7)
References	374	(3)
11 Scaling and Roundoff Noise	377	(44)
11.1 Introduction	377	(1)
11.2 Scaling and Roundoff Noise	378	(4)
11.3 State Variable Description of Digital Filters	382	(4)
11.4 Scaling and Roundoff Noise Computation	386	(5)
11.5 Roundoff Noise in Pipelined IIR Filters	391	(12)
11.6 Roundoff Noise Computation Using State Variable Description	403	(2)
11.7 Slow-Down, Retiming, and Pipelining	405	(5)
11.8 Conclusions	410	(1)
11.9 Problems	410	(9)
References	419	(2)
12 Digital Lattice Filter Structures	421	(56)
12.1 Introduction	421	(1)
12.2 Schur Algorithm	422	(7)
12.3 Digital Basic Lattice Filters	429	(8)
12.4 Derivation of One-Multiplier Lattice Filter	437	(7)
12.5 Derivation of Normalized Lattice Filter	444	(3)
12.6 Derivation of Scaled-Normalized Lattice Filter	447	(7)
12.7 Roundoff Noise Calculation in Lattice Filters	454	(4)
12.8 Pipelining of Lattice IIR Digital Filters	458	(6)
12.9 Design Examples of Pipelined Lattice Filters	464	(5)
12.10 Low-Power CMOS Lattice IIR Filters	469	(1)
12.11 Conclusions	470	(1)
12.12 Problems	470	(4)
References	474	(3)
13 Bit-Level Arithmetic Architectures	477	(52)
13.1 Introduction	477	(1)
13.2 Parallel Multipliers	478	(11)
13.3 Interleaved Floor-plan and Bit-Plane-Based Digital Filters	489	(1)
13.4 Bit-Serial Multipliers	490	(9)
13.5 Bit-Serial Filter Design and Implementation	499	(6)
13.6 Canonic Signed Digit Arithmetic	505	(6)
13.7 Distributed Arithmetic	511	(7)
13.8 Conclusions	518	(1)
13.9 Problems	518	(9)
References	527	(2)
14 Redundant Arithmetic	529	(30)
14.1 Introduction	529	(1)
14.2 Redundant Number Representations	530	(1)
14.3 Carry-Free Radix-2 Addition and Subtraction	531	(5)
14.4 Hybrid Radix-4 Addition	536	(4)
14.5 Radix-2 Hybrid Redundant Multiplication Architectures	540	(5)
14.6 Data Format Conversion	545	(2)
14.7 Redundant to Nonredundant Converter	547	(4)
14.8 Conclusions	551	(1)
14.9 Problems	552	(3)
References	555	(4)
15 Numerical Strength Reduction	559	(32)
15.1 Introduction	559	(1)
15.2 Subexpression Elimination	560	(1)
15.3 Multiple Constant Multiplication	560	(6)
15.4 Subexpression Sharing in Digital Filters	566	(8)
15.5 Additive and Multiplicative Number Splitting	574	(9)
15.6 Conclusions	583	(1)
15.7 Problems	583	(6)
References	589	(2)
16 Synchronous, Wave, and Asynchronous Pipelines	591	(54)
16.1 Introduction	591	(2)
16.2 Synchronous Pipelining and Clocking Styles	593	(8)
16.3 Clock Skew and Clock Distribution in Bit-Level Pipelined VLSI Designs	601	(5)
16.4 Wave Pipelining	606	(6)
16.5 Constraint Space Diagram and Degree of Wave Pipelining	612	(2)
16.6 Implementation of Wave-Pipelined Systems	614	(5)
16.7 Asynchronous Pipelining	619	(3)
16.8 Signal Transition Graphs	622	(4)
16.9 Use of STG to Design Interconnection Circuits	626	(5)
16.10 Implementation of Computational Units	631	(9)
16.11 Conclusions	640	(1)
16.12 Problems	640	(3)
References	643	(2)
17 Low-Power Design	645	(50)
17.1 Introduction	645	(3)
17.2 Theoretical Background	648	(2)
17.3 Scaling Versus Power Consumption	650	(2)
17.4 Power Analysis	652	(10)
17.5 Power Reduction Techniques	662	(9)
17.6 Power Estimation Approaches	671	(17)
17.7 Conclusions	688	(1)
17.8 Problems	688	(4)
References	692	(3)
18 Programmable Digital Signal Processors	695	(22)
18.1 Introduction	695	(1)
18.2 Evolution of Programmable Digital Signal Processors	696	(1)
18.3 Important Features of DSP Processors	697	(6)
18.4 DSP Processors for Mobile and Wireless Communications	703	(1)
18.5 Processors for Multimedia Signal Processing	704	(10)
18.6 Conclusions	714	(1)
References	714	(3)
Appendix A: Shortest Path Algorithms	717	(6)
A.1 Introduction	717	(1)
A.2 The Bellman-Ford Algorithm	718	(2)
A.3 The Floyd-Warshall Algorithm	720	(1)
A.4 Computational Complexities	721	(1)
References	722	(1)
Appendix B: Scheduling and Allocation Techniques	723	(20)
B.1 Introduction	723	(2)
B.2 Iterative/Constructive Scheduling Algorithms	725	(4)
B.3 Transformational Scheduling Algorithms	729	(9)
B.4 Integer Linear Programming Models	738	(3)
References	741	(2)
Appendix C: Euclidean GCD Algorithm	743	(4)
C.1 Introduction	743	(1)
C.2 Euclidean GCD Algorithm for Integers	743	(2)
C.3 Euclidean GCD Algorithm for Polynomials	745	(2)
Appendix D: Orthonormality of Schur Polynomials	747	(6)
D.1 Orthogonality of Schur Polynomials	747	(2)
D.2 Orthonormality of Schur Polynomials	749	(4)
Appendix E: Fast Binary Adders and Multipliers	753	(10)
E.1 Introduction	753	(1)
E.2 Multiplexer-Based Fast Binary Adders	753	(5)
E.3 Wallace Tree and Dadda Multiplier	758	(3)
References	761	(2)
Appendix F: Scheduling in Bit-Serial Systems	763	(8)
F.1 Introduction	763	(1)
F.2 Outline of the Scheduling Algorithm	764	(2)
F.3 Minimum Cost Solution	766	(2)
F.4 Scheduling of Edges with Delays	768	(1)
References	769	(2)
Appendix G: Coefficient Quantization in FIR Filters	771	(4)
G.1 Introduction	771	(1)
G.2 NUS Quantization Algorithm	771	(3)
References	774	(1)
Index	775