视频压缩，无线通信，全球定位、雷达影像……在DSP的广泛应用领域内，怎样设计出高速、精巧的VLSI系统?并行处理、流水线。ASIC、可编程数字信号处理器，为实现DSP算法，技术与工具怎样结合才能更加完美?本书将为您提供答案。它既是折叠、异步流水线等技术的资源宝库，同时也是方向标，通过大量的实践经验指明了进入VLSI王国的捷径。
本书特点：
通过上百张图片对不同的DSP算法进行解释
每章后的习题将技术与现实紧密结合起来
适用面广，可作为《VlSI数字信号处理体系结构》或《高性能VLSI系统设计》等课程的教材提供有无线。有线。多媒体通信多个领域内的技术与经验
作者简介：
Keshab K．Parhi于印度理工学院获得工学学士学位；1984年于宾夕法尼亚大学获得电子与电气工程硕士学
位：1988年在加利福尼亚大学伯克利分校获得博士学位。自1988年以来，一直执教于明尼苏达大学电子和计算机工程系，最近刚刚获得McKnight大学杰出教授荣誉称号。他的研究方向包括：并发算法，通信架构设计、信号和图像处理系统。数字集成电路、VLSI数字滤波器等。
他是IEEE成员。作为主席，他主持了IEEE 1995 VLSI数字处理研讨会。IEEE1996特殊应用系统、体系结构和处理器研讨会以及IEEE2002数字处理的设计与实现研讨会。
Digital signal processing (DSP) is used in numerous applications such as video compression, digital set-top box, cable modems, digital versatile disk, portable video systems/computers, digital audio, multimedia and wireless communi-cations, digital radio, digital still and network cameras, speech processing,transmission systems, radar imaging, acoustic beamformers, global positioning systems, and biomedical signal processing. The field of DSP has always been driven by the advances in DSP applications and in scaled very-large scale-integrated (VLSI)technologies. Therefore, at any given time, DSP applications impose several challenges on the implementations of the DSP systems. These implementations must satisfy the enforced sampling rate con-straints of the real-time DSP applications and must require less space and power consumption.
This book addresses the methodologies needed to design custom or semicustom VLSI circuits for these applications. Many of the techniques presented in the book are also applicable for faster implementations using off-the-shelf programmable digital signal processors. This book is intended to be used as a textbook for first-year graduate or senior courses on VLSI DSP architectures, or DSP structures for VLSI or High-Performance VLSI system design.This book is also an excellent reference for those involved in algorithm or architecture or circuit design for DSP applications.
This book brings together the distinct fields of computer architecture the-ory and DSP. DSP computation is different from general-purpose computation in the sense that the DSP programs are nonterminating programs. In DSP such as addition and multiplication and digital filters, high-performance VLSI system design issues such as pipelining styles and low-power design, and pro-grammable digital signal processors. Design of adders and multipliers using various implementation styles, such as bit-parallel, bit-serial, and digit-serial,and various number systems such as two's complement, canonic signed digit,and carry-save are discussed in Chapter 13. This chapter also addresses distributed arithmetic. Chapter 14 addresses arithmetic architectures based on redundant or signed-digit implementations. The main advantage of redundant arithmetic lies in its carry-free property, which enables computation in both least significant bit and most significant bit first modes. Conversion from redundant to nonredundant and vice versa is also addressed. In these chapters,bit-serial multipliers are derived from bit-parallel designs by systolic design methodology. Residue arithmetic, which can be used for implementation of FIR digital filters and transforms, is not studied in this book. Chapter 15 presents strength reduction at numerical level to reduce the area and power consumption of two's complement and canonic signed digit number based digital filters. Chapter 16 discusses various pipelining styles, such as synchronous,wave, and asynchronous pipelining. Approaches to reduction of clock skew in synchronous systems and synthesis of interface circuits in asynchronous systems are also addressed. Chapter 17 on low-power design presents various approaches for reduction of power consumption at architectural and technology levels and for estimation of power consumption. Chapter 18 addresses various architectures used in programmable digital signal processors.
Seven appendixes in the book cover shortest path algorithms used for determining the iteration bound and for retiming, scheduling, and allocation techniques used for determining the folding sets: for design of folded architectures; Euclid's GCD algorithm, which is used for Winograd's convolution;orthonormality of Schur polynomials used for design :of lattice digital filters;
fast bit-parallel addition and multiplication; scheduling techniques for bitserial systems; and coefficient quantization in FIR filters.
The concepts in this book have been described in a technology-independent manner. The examples in this book are based on digital filters and transforms. Many real-time DSP systems make use of control flow constructs such as conditionals, interrupts, and jump. Design of control-dominated DSP systerns is beyond the scope of this book. The exercises can be completed using any programming language such as MATLAB or C. Many application-driven problems have been included at the end of the chapters, For example, the problems at the end of the algorithmic strength reduction chapter address the use of fast filters in design of equalizers in communications systems, wavelets,two-dimensional FIR digital filters, and motion estimation. These problems introduce the reader to different applications where the concepts covered in the chapter can be applied.
This book is based on the material taught at the University of Minnesota in two current semester courses: EE 5329: VLSI Digital Signal Processing on the iteration period of any recursive signal processing algorithm. Two algorithms are described for determining this bound. The next 5 chapters address various transformations for improving performance of digital signal processing implementations. In Chapter 3, the basic concepts of pipelining and parallel processing are reviewed and the use of these techniques in design of high-speed or low-power applications is demonstrated. Chapter 4 addresses the retiming transformation, which is a generalization of the pipelining approach. Chapter5 addresses unfolding, which can be used to design parallel architectures.
Chapters 6 and 7 address folding techniques used to design time-multiplexed architectures where area reduction is important. While Chapter 6 addresses folding of arbitrary data-flow graphs, Chapter 7 addresses folding of regular data-flow graphs based on systolic design methodology.
Chapters 8 to 12 address design of algorithm structures for various DSP algorithms based on algorithm transformations such as strength reduction,look-ahead and relaxed look-ahead, and scaling and roundoff noise in digital filters. Chapter 8 addresses fast convolution based on Cook-Toom and Winograd convolution algorithms. In Chapter 9, algorithmic strength reduction is exploited to reduce the number of multiplication operations in parallel FIR filters, discrete cosine transforms, and parallel rank-order filters. Design of fast Fourier transform (FFT) structures is also based on strength reduction transformations but is not covered in this book since it is covered in many introductory DSP textbooks. While it is easy to achieve pipelining and parallel processing in nonrecursive computations, recursive and adaptive digital filters cannot be easily pipelined or processed in parallel due to the presence of feedback loops. In Chapter 10, the look-ahead technique is discussed and is used to pipeline first-order infinite impulse response (IIR) digital filters. For higher order filters, two types of look-ahead techniques, clustered and scattered look-ahead, are discussed. It is shown that the scattered look-ahead 'technique guarantees stability in pipelined IIR filters. The parallel implementations of IIR digital filters and how to combine pipelining and parallel processing in these digital filters are also addressed. Adaptive digital filters are pipelined based on relaxed look-ahead, which are based on certain approximations or relaxations of look-ahead. Chapter 11 addresses scaling and roundoff noise, which are important for VLSI implementations of DSP systems using fixed-point arithmetic. Roundoff noise computation techniques cannot be applied to many digital filters. These filters are preprocessed using slowdown, pipelining and/or retiming so that every roundoff noise node can be expressed as a state variable. The direct-form IIR digital filters cannot meet the filter requirements in certain applications. Lattice digital filters may be better suited for these applications due to their excellent roundoff noise property. Chapter 12 presents Schur polynomials, orthonormality of Schur polynomials, and use of these polynomials to design basic (two multiplier and one multiplier), normalized, and scaled-normalized lattice digital filters.
Pipelined implementation of these lattice digital filters is also discussed.
Chapters 13 to 18 address VLSI implementations of arithmetic operations such as addition and multiplication and digital filters, high-performance VLSI system design issues such as pipelining styles and low-power design, and programmable digital signal processors. Design of adders and multipliers using various implementation styles, such as bit-parallel, bit-serial, and digit-serial,and various number systems such as two's complement, canonic signed digit,
and carry-save are discussed in Chapter 13. This chapter also addresses distributed arithmetic. Chapter 14 addresses arithmetic architectures based on redundant or signed-digit implementations. The main advantage of redundant arithmetic lies in its carry-free property, which enables computation in both least significant bit and most significant bit first modes. Conversion from redundant to nonredundant and vice versa is also addressed. In these chapters,bit-serial multipliers are derived from bit-parallel designs by systolic design methodology. Residue arithmetic, which can be used for implementation of FIR digital filters and transforms, is not studied in this book. Chapter 15 presents strength reduction at numerical level to reduce the area and power consumption of two's complement and canonic signed digit number based digital filters. Chapter 16 discusses various pipelining styles, such as synchronous,wave, and asynchronous pipelining. Approaches to reduction of clock skew in synchronous systems and synthesis of interface circuits in asynchronous systems are also addressed. Chapter 17 on low-power design presents various approaches for reduction of power consumption at architectural and technology levels and for estimation of power consumption. Chapter 18 addresses
various architectures used in programmable digital signal processors.
Seven appendixes in the book cover shortest path algorithms used for determining the iteration bound and for retiming, scheduling, and allocation techniques used for determining the folding sets for design of folded architectures; Euclid's GCD algorithm, which is used for Winograd's convolution;
orthonormality of Schur polynomials used for design of lattice digital filters;fast bit-parallel addition and multiplication; scheduling techniques for bitserial systems; and coefficient quantization in FIR filters.
The concepts in this book have been described in a technology-independent manner. The examples in this book are based on digital filters and trans forms. Many real-time DSP systems make use of control flow constructs such as conditionals, interrupts, and jump. Design of control-dominated DSP systems is beyond the scope of this book. The exercises can be completed using any programming language such as MATLAB or C. Many application-driven problems have been included at the end of the chapters. For example, the problems at the end of the algorithmic strength reduction chapter address the use of fast filters in design of equalizers in communications systems, wavelets,two-dimensional FIR digital filters, and motion estimation. These problems introduce the reader to different applications where the concepts covered in the chapter can be applied.
This book is based on the material taught at the University of Minnesota in two current semester courses: EE 5329: VLSI Digital Signal Processing Systems and EE 5549: Digital Signal Processing Structures for VLSI. EE 5329 (with a basic course on VLSI Design as prerequisite) covers chapters 2 through 7 and parts of chapters 13 through 18 (in that order). EE 5549 (with a basic course on digital signal processing as prerequisite) covers parts of chapters 2,
3, and 4, chapters 8 through 12, and some architectures for video compression based on journal and conference papers. These two semester courses were taught as three-quarter courses in the past. For a single semester course on VLSI Digital Signal Processing, chapters 2 through 7, parts of chapters 9, 10, .13 and 15, and an overview of topics in chapters 17 and 18 are recommended.
However, the instructors can select the chapters that suit their needs. The chapters need not be followed in the order they are presented. Many chapters can be taught independently. The precedence graph in Fig. 0.1 shows the dependencies among chapters. The dashed lines represent weak dependencies where a section of the current chapter is dependent on the preceding chapter.
The author has been fortunate to receive valuable help, support, and and suggestions from numerous colleagues, students, and friends. The author is grateful to Leilei Song for her constant and enthusiastic help during the writing of this book. He is also grateful to Jin-Gyun Chung, Tracy Denk,David Parker, Janardhan Satyanarayana, and Ching-Yi Wang for their help during the early part of the writing of this book. The author is thankful to Wayne Burleson, Francky Catthoor, Ed F. Deprettere, Graham Jullien, and Naresh R. Shanbhag for their thorough and constructive reviews of the first draft; their comments have resulted in reorganization of several chapters in the book. Ed F. Deprettere and Scott Douglas used the preliminary versions of the book at Delft University of Technology and at the University of Utah,respectively, and provided numerous suggestions.
The author appreciates the constant support and encouragement he has received from David G. Messerschmitt and Mos Kaveh. The author's research included in this book has been supported by the National Science Foundation,the Army Research Office, the Office of Naval Research, the Defense Advanced Research Projects Agency, Texas Instruments, Lucent Technologies, and NEC Corporation. The author is thankful to John Cozzens, Wanda Gass, Arup Gupta, Clifford Lau, Jose Munoz, Takao Nishitani, and Bill Sander for their encouragement.
Several chapters in the book are based on the joint research work of the author with his colleagues Jin-Gyun Chung, Tracy Denk, Kazuhito Ito, Lori Lucke, David G. Messerschmitt, Luis Montalvo, David Parker, Janardhan Satyanarayana, Naresh Shanbhag, H. R. Srinivas, and Ching-Yi Wang. The author also thanks many of his colleagues: Bryan Ackland, Jonathan Allen,Magdy Bayoumi, Don Boudlin, Robert W. Brodersen, Peter Cappello, Anan tha Chandrakasan, Liang-Gee Chen, Gerhard Fettweis, Eby Friedman, Richard Hartley, Mehdi Hatamian, Sonia Heemstra, Yu Hen Hu, M. K. Ibrahim,Mary Irwin, Rajeev Jain, Leah Jamieson, Chein-Wei Jen, S.Y. Kung, Ichiro Kuroda, Edward Lee, K. J. R. Liu, Vijay Madisetti, John McCanny, Teresa Meng, Takao Nishitani, Tobias Noll, Robert Owens, Peter Pirsch, Miodrag Potkonjak, Jan Rabaey, Takayasu Sakural, Edwin Sha, Bing Sheu, Michael Soderstrand, Mani Srivastava, Thanos Stouraitis, Earl Swartzlander, P. P.
Vaidyanathan, Ingrid Verbanwhede, and Kung Yao. He has enjoyed numerous interactions with them. This book has been directly or indirectly influenced by these interactions. Thanks are also due to Carl Harris of Kluwer Academic Publishers for his permitting the author to reprint several parts of chapters 11 and 12 from an earlier monograph.
The author thanks Andrew Smith of John Wiley & Sons for his personal interest in this topic and for having invited the author to write this book.
He also thanks Angioline Loredo, associate managing editor at Wiley, for her help in production of this book. It was truly a pleasure to work with them.
KESHAB K. PARHI
Minneapolis, MN
(美)Keshab K.Parhi：Keshab K.Parhi: 凯夏博·帕里（Keshab K. Parhi）教授分别于1982年、1984年和1988年在印度理工学院、美国宾夕法尼亚大学和加州大学伯克利分校取得电机工程专业学士、硕士和博士学位。从1988年起，Parhi 教授在明尼苏达大学从事教学与研究工作，并被评为电机与计算机工程系的McKinght荣誉教授。 他的研究领域重点在于宽带通信系统物理层方面的VLSI体系结构设计。他当前的研究包括纠错码的编/解码器与加密/解密算法的体系结构、高速发送/接收器、超宽带系统、量子纠错编/解码器与量子加密/解密。他已经发表了350多篇学术论文，撰写了教科书“VLSI Digital Signal Processing Systems: Design and Implementation”（Wiley, 1999）。这套教材被美国、荷兰、瑞典、芬兰等国的多所大学采用。此外，他还参与了“多媒体系统的数字信号处理”（Marcel Dekker, 1999）一书的编写工作。 Parhi教授曾获得多次殊荣，包括2003年度“IEEE Kiyo Tomiyasu”技术领域奖、2001年IEEE W.R.G. Baker最佳论文奖和1999年度IEEE电路与系统协会Golden Jubilee奖。1996年，他被评选为电气电子工程师学会会士（IEEE Fellow）。历年来，他曾担任“IEEE Transactions on Circuits and Systems, Circuits and Systems-II”、“VLSI Systems”、“Signal Processing”、“Signal Processing Letters”等学术杂志的编委会成员。此外，他还担任 “IEEE Trans. On Circuits and Systems-I”（2004—2005年度）的主编和“IEEE Signal Processing Magazine”的编委。Parhi教授是IEEE 1995年“VLSI信号处理研讨会”和1996年“专用系统、体系结构与处理器国际会议”(ASAP)的技术委员会联合主席，以及2002年“IEEE信号处理系统研讨会”的主席。他曾被IEEE电路与系统协会授予1996—1998年度杰出讲师的称号。
Preface
Introduction to Digital Signal Processing Systems
1.1 Introduction
1.2 Typical DSP Algorithms
1.3 DSP Application Demands and Scaled CMOS Technologies
1.4 Representations of DSP Algorithms
1.5 Book Outline
References
2 Iteration Bound
2.1 Introduction
2.2 Data-Flow Graph Representations
2.3 Loop Bound and Iteration Bound
2.4 Algorithms for Computing Iteration Bound
2.5 Iteration Bound of Multirate Data-Flow Graphs
2.6 Conclusions
2.7 Problems
References
3 Pipelining and Parallel Processing
3.1 Introduction
3.2 Pipelining of FIR Digital Filters
3.3 Parallel Processing
3.4 Pipelining and Parallel Processing for Low Power
3.5 Conclusions
3.6 Problems
References
4 Retiming
4.1 Introduction
4.2 Definitions and Properties
4.3 Solving Systems of Inequalities
4.4 Retiming Techniques
4.5 Conclusions
4.6 Problems
References
5 Unfolding
5.1 Introduction
5.2 An Algorithm for Unfolding
5.3 Properties of Unfolding
5.4 Critical Path, Unfolding, and Retiming
5.5 Applications of Unfolding
5.6 Conclusions
5.7 Problems
References
6 Folding
6.1 Introduction
6.2 Folding Transformation
6.3 Register Minimization Techniques
6.4 Register Minimization in Folded Architectures
6.5 Folding of Multirate Systems
6.6 Conclusions
6.7 Problems
References
7 .Systolic Architecture Design
7.1 Introduction
7.2 Systolic Array Design Methodology
7.3 FIR Systolic Arrays
7.4 Selection of Scheduling Vector
7.5 Matrix-Matrix Multiplication and 2D Systolic Array Design
7.6 Systolic Design for Space Representations Containing
Delays
7.7 Conclusions
7.8 Problems
References
8 Fast Convolution
8.1 Introduction
8.2 Cook-Toom Algorithm
8.3 Winograd Algorithm
8.4 Iterated Convolution
8.5 Cyclic Convolution
8.6 Design of Fast Convolution Algorithm by Inspection
8.7 Conclusions
8.8 Problems
References
9 Algorithmic Strength Reduction in Filters and Transforms
9.1 Introduction
9.2 Parallel FIR Filters
9.3 Discrete Cosine Transform and Inverse DCT
9.4 Parallel Architectures for Rank-Order Filters
9.5 Conclusions
9.6 Problems
References
10 Pipelined and Parallel Recursive and Adaptive Filters
10.1 Introduction
10.2 Pipeline Interleaving in Digital Filters
10.3 Pipelining in 1st-Order IIR Digital Filters
10.4 Pipelining in Higher-Order IIR Digital Filters
10.5 Parallel Processing for IIR filters
10.6 Combined Pipelining and Parallel Processing for IIR Filters
10.7 Low-Power IIR Filter Design Using Pipelining and Parallel
Processing
10.8 Pipelined Adaptive Digital Filters
10.9 Conclusions
10.10 Problems
References
11 Scaling and Roundoff Noise
11.1 Introduction
11.2 Scaling and Roundoff Noise
11.3 State Variable Description of Digital Filters
11.4 Scaling and Roundoff Noise Computation
11.5 Roundoff Noise in Pipelined IIR Filters
11.6 Roundoff Noise Computation Using State Variable
Description
11.7 Slow-Down, Retiming, and Pipelining
11.8 Conclusions
11.9 Problems
References
12 Digital Lattice Filter Structures
12.1 Introduction
12.2 Schur Algorithm
12.3 Digital Basic Lattice Filters
12.4 Derivation of One-Multiplier Lattice Filter
12.5 Derivation of Normalized Lattice Filter
12.6 Derivation of Scaled-Normalized Lattice Filter
12.7 Roundoff Noise Calculation in Lattice Filters
12.8 Pipelining of Lattice IIR Digital Filters
12.9 Design Examples of Pipelined Lattice Filters
12.10 Low-Power CMOS Lattice IIR Filters
12.11 Conclusions
12.12 Problems
References
13 Bit-Level Arithmetic Architectures
13.1 Introduction
13.2 Parallel Multipliers
13.3 Interleaved Floor-plan and Bit-Plane-Based Digital Filters
13.4 Bit-Serial Multipliers
13.5 Bit-Serial Filter Design and Implementation
13.6 Canonic Signed Digit Arithmetic
13.7 Distributed Arithmetic
13.8 Conclusions
13.9 Problems
References
14 Redundant Arithmetic
14.1 Introduction
14.2 Redundant Number Representations
14.3 Carry-Free Radix-2 Addition and Subtraction
14.4 Hybrid Radix-4 Addition
14.5 Radix-2 Hybrid Redundant Multiplication Architectures
14.6 Data Format Conversion
14.7 Redundant to Nonredundant Converter
14.8 Conclusions
14.9 Problems
References
15 Numerical Strength Reduction
15.1 Introduction
15.2 Subexpression Elimination
15.3 Multiple Constant Multiplication
15.4 Subexpression Sharing in Digital Filters
15.5 Additive and Multiplicative Number Splitting
15.6 Conclusions
15.7 Problems
References
16 Synchronous, Wave, and Asynchronous Pipelines
16.1 Introduction
16.2 Synchronous Pipelining and Clocking Styles
16.3 Clock Skew and Clock Distribution in Bit-Level Pipelined
VLSI Designs
16.4 Wave Pipelining
16.5 Constraint Space Diagram and Degree of Wave Pipelining
16.6 Implementation of Wave-Pipelined Systems
16.7 Asynchronous Pipelining
16.8 Signal Transition Graphs
16.9 Use of STG to Design Interconnection Circuits
16.10 Implementation of Computational Units
16.11 Conclusions
16.12 Problems
References
17 Low-Power Design
17.1 Introduction
17.2 Theoretical Background
17.3 Scaling Versus Power Consumption
17.4 Power Analysis
17.5 Power Reduction Techniques
17.6 Power Estimation Approaches
17.7 Conclusions
17.8 Problems
References
18 Programmable Digital Signal Processors
18.1 Introduction
18.2 Evolution of Programmable Digital Signal Processors
18.3 Important Features of DSP Processors
18.4 DSP Processors for Mobile and Wireless Communications
18.5 Processors for Multimedia Signal Processing
18.6 Conclusions
References
Appendix A: Shortest Path Algorithms
A.1 Introduction
A.2 The Bellman-Ford Algorithm
A.3 The Floyd-Warshall Algorithm
A.4 Computational Complexities
References
Appendix B: Scheduling and Allocation Techniques
B.1 Introduction
B.2 Iterative/Constructive Scheduling Algorithms
B.3 Transformational Scheduling Algorithms
B.4 Integer Linear Programming Models
Appendix C: Euclidean GCD Algorithm
C.1 Introduction
C.2 Euclidean GCD Algorithm for Integers
C.3 Euclidean GCD Algorithm for Polynomials
Appendix D: Orthonormality of Schur Polynomials
D.1 Orthogonality of Schur Polynomials
D.2 Orthonormality of Schur Polynomials
Appendix E: Fast Binary Adders and Multipliers
E.1 Introduction
E.2 Multiplexer-Based Fast Binary Adders
E.3 Wallace Tree and Dadda Multiplier
References
Appendix F: Scheduling in Bit-Serial Systems
F.1 Introduction
F.2 Outline of the Scheduling Algorithm
F.3 Minimum Cost Solution
F.4 Scheduling of Edges with Delays
References
Appendix G: Coefficient Quantization in FIR Filters
G.1 Introduction
G.2 NUS Quantization Algorithm
References
Index
