Here We Go Again

The book is designed to serve as a textbook for courses offered to undergraduate and graduate students enrolled in electrical, electronics, and communication engineering. The objective of this book is to help the readers to understand the concepts of digital system design as well as to motivate the students to pursue research in this field. Verilog Hardware Description Language (HDL) is preferred in this book to realize digital architectures. Concepts of Verilog HDL are discussed in a separate chapter and many Verilog codes are given in this book for better understanding. Concepts of system Verilog to realize digital hardware are also discussed in a separate chapter. The book covers basic topics of digital logic design like binary number systems, combinational circuit design, sequential circuit design, and finite state machine (FSM) design. The book also covers some advanced topics on digital arithmetic like design of high-speed adders, multipliers, dividers, square root circuits, and CORDIC block. The readers can learn about FPGA and ASIC implementation steps and issues that arise at the time of implementation. One chapter of the book is dedicated to study the low-power design techniques and another to discuss the concepts of static time analysis (STA) of a digital system. Design and implementation of many digital systems are discussed in detail in a separate chapter. In the last chapter, basics of some advanced FPGA design techniques like partial re-configuration and system on chip (SoC) implementation are discussed. These designs can help the readers to design their architecture. This book can be very helpful to both undergraduate and postgraduate students and researchers. Preface Objective of the Book Organization of the Book Acknowledgements Contents About the Author Abbreviations 1 Binary Number System 1.1 Introduction 1.2 Binary Number System 1.3 Representation of Numbers 1.3.1 Signed Magnitude Representation 1.3.2 One's Complement Representation 1.3.3 Two's Complement Representation 1.4 Binary Representation of Real Numbers 1.4.1 Fixed Point Data Format 1.5 Floating Point Data Format 1.6 Signed Number System 1.6.1 Binary SD Number System 1.6.2 SD Representation to Two's Complement Representation 1.7 Conclusion 2 Basics of Verilog HDL 2.1 Introduction 2.2 Verilog Expressions 2.2.1 Verilog Operands 2.2.2 Verilog Operators 2.2.3 Concatenation and Replication 2.3 Data Flow Modelling 2.4 Behavioural Modelling 2.4.1 Initial Statement 2.4.2 Always Statement 2.4.3 Timing Control 2.4.4 Procedural Assignment 2.5 Structural Modelling 2.5.1 Gate-Level Modelling 2.5.2 Hierarchical Modelling 2.6 Mixed Modelling 2.7 Verilog Function 2.8 Verilog Task 2.9 File Handling 2.9.1 Reading from a Text File 2.9.2 Writing into a Text File 2.10 Test Bench Writing 2.11 Frequently Asked Questions 2.12 Conclusion 3 Basic Combinational Circuits 3.1 Introduction 3.2 Addition 3.3 Subtraction 3.4 Parallel Binary Adder 3.5 Controlled Adder/Subtractor 3.6 Multiplexers 3.7 De-Multiplexers 3.8 Decoders 3.9 Encoders 3.10 Majority Voter Circuit 3.11 Data Conversion Between Binary and Gray Code 3.12 Conversion Between Binary and BCD Code 3.12.1 Binary to BCD Conversion 3.12.2 BCD to Binary Conversion 3.13 Parity Generators/Checkers 3.14 Comparators 3.15 Constant Multipliers 3.16 Frequently Asked Questions 3.17 Conclusion 4 Basic Sequential Circuits 4.1 Introduction 4.2 Different Flip-Flops 4.2.1 SR Flip-Flop 4.2.2 JK Flip-Flop 4.2.3 D Flip-Flop 4.2.4 T Flip-Flop 4.2.5 Master-Slave D Flip-Flop 4.3 Shift Registers 4.3.1 Serial In Serial Out 4.3.2 Serial In Parallel Out 4.3.3 Parallel In Serial Out 4.3.4 Parallel In Parallel Out 4.4 Sequence Generator 4.5 Pseudo Noise Sequence Generator 4.6 Synchronous Counter Design 4.7 Loadable Counter 4.7.1 Loadable Up Counter 4.7.2 Loadable Down Counter 4.8 Even and Odd Counter 4.9 Shift Register Counters 4.10 Phase Generation Block 4.11 Clock Divider Circuits 4.11.1 Clock Division by Power of 2 4.11.2 Clock Division by 3 4.11.3 Clock Division by 6 4.11.4 Programmable Clock Divider Circuit 4.12 Frequently Asked Questions 4.13 Conclusion 5 Memory Design 5.1 Introduction 5.2 Controlled Register 5.3 Read Only Memory 5.3.1 Single Port ROM 5.3.2 Dual Port ROM (DPROM) 5.4 Random Access Memory (RAM) 5.4.1 Single Port RAM (SPRAM) 5.4.2 Dual Port RAM (DPRAM) 5.5 Memory Initialization 5.6 Implementing Bigger Memory Element Using Smaller Memory Elements 5.7 Implementation of Memory Elements 5.8 Conclusion 6 Finite State Machines 6.1 Introduction 6.2 FSM Types 6.3 Sequence Detector Using Mealy Machine 6.4 Sequence Detector Using Moore Machine 6.5 Comparison of Mealy and Moore Machine 6.6 FSM-Based Serial Adder Design 6.7 FSM-Based Vending Machine Design 6.8 State Minimization Techniques 6.9 Row Equivalence Method 6.10 Implication Chart Method 6.11 State Partition Method 6.12 Performance of State Minimization Techniques 6.13 Verilog Modelling of FSM-Based Systems 6.14 Frequently Asked Questions 6.15 Conclusion 7 Design of Adder Circuits 7.1 Introduction 7.2 Ripple Carry Adder 7.3 Carry Look-Ahead Adder 7.3.1 Higher Bit Adders Using CLA 7.3.2 Prefix Tree Adders 7.4 Manchester Carry Chain Module (MCC) 7.5 Carry Skip Adder 7.6 Carry Increment Adder 7.7 Carry Select Adder 7.8 Conditional Sum Adder 7.9 Ling Adders 7.10 Hybrid Adders 7.11 Multi-operand Addition 7.11.1 Carry Save Addition 7.11.2 Tree of Carry Save Adders 7.12 BCD Addition 7.13 Conclusion 8 Design of Multiplier Circuits 8.1 Introduction 8.2 Sequential Multiplication 8.3 Array Multipliers 8.4 Partial Product Generation and Reduction 8.4.1 Booth's Multiplication 8.4.2 Radix-4 Booth's Algorithm 8.4.3 Canonical Recoding 8.4.4 An Alternate 2-bit at-a-time Multiplication Algorithm 8.4.5 Implementing Larger Multipliers Using Smaller Ones 8.5 Accumulation of Partial Products 8.5.1 Accumulation of Partial Products for Unsigned Numbers 8.5.2 Accumulation of Partial Products for Signed Numbers 8.5.3 Alternative Techniques for Partial Product Accumulation 8.6 Wallace and Dedda Multiplier Design 8.7 Multiplication Using Look-Up Tables 8.8 Dedicated Square Block 8.9 Architectures Based on VEDIC Arithmetic 8.9.1 VEDIC Multiplier 8.9.2 VEDIC Square Block 8.9.3 VEDIC Cube Block 8.10 Conclusion 9 Division and Modulus Operation 9.1 Introduction 9.2 Sequential Division Methods 9.2.1 Restoring Division 9.2.2 Unsigned Array Divider 9.2.3 Non-restoring Division 9.2.4 Conversion from Signed Binary to Two's Complement 9.3 Fast Division Algorithms 9.3.1 SRT Division 9.3.2 SRT Algorithm Properties 9.4 Iterative Division Algorithms 9.4.1 Goldschmidt Division 9.4.2 Newton–Raphson Division 9.5 Computation of Modulus 9.6 Conclusion 10 Square Root and its Reciprocal 10.1 Introduction 10.2 Slow Square Root Computation Methods 10.2.1 Restoring Algorithm 10.2.2 Non-restoring Algorithm 10.3 Iterative Algorithms for Square Root and its Reciprocal 10.3.1 Goldschmidt Algorithm 10.3.2 Newton–Raphson Iteration 10.3.3 Halley's Method 10.3.4 Bakhshali Method 10.3.5 Two Variable Iterative Method 10.4 Fast SRT Algorithm for Square Root 10.5 Taylor Series Expansion Method 10.5.1 Theory 10.5.2 Implementation 10.6 Function Evaluation by Bipartite Table Method 10.7 Conclusion 11 CORDIC Algorithm 11.1 Introduction 11.2 Theoretical Background 11.3 Vectoring Mode 11.3.1 Computation of Sine and Cosine 11.4 Linear Mode 11.4.1 Multiplication 11.4.2 Division 11.5 Hyperbolic Mode 11.5.1 Square Root Computation 11.6 CORDIC Algorithm Using Redundant Number System 11.6.1 Redundant Radix-2-Based CORDIC Algorithm 11.6.2 Redundant Radix-4-Based CORDIC Algorithm 11.7 Example of CORDIC Iteration 11.8 Implementation of CORDIC Algorithms 11.8.1 Parallel Architecture 11.8.2 Serial Architecture 11.8.3 Improved CORDIC Architectures 11.9 Application 11.10 Conclusion 12 Floating Point Architectures 12.1 Introduction 12.2 Floating Point Representation 12.3 Fixed Point to Floating Point Conversion 12.4 Leading Zero Counter 12.5 Floating Point Addition 12.6 Floating Point Multiplication 12.7 Floating Point Division 12.8 Floating Point Comparison 12.9 Floating Point Square Root 12.10 Floating Point to Fixed Point Conversion 12.11 Conclusion 13 Timing Analysis 13.1 Introduction 13.2 Timing Definitions 13.2.1 Slew of Waveform 13.2.2 Clock Jitter 13.2.3 Clock Latency 13.2.4 Launching and Capturing Flip-Flop 13.2.5 Clock Skew 13.2.6 Clock Uncertainty 13.2.7 Clock-to-Q Delay 13.2.8 Combinational Logic Timing 13.2.9 Min and Max Timing Paths 13.2.10 Clock Domains 13.2.11 Setup Time 13.2.12 Hold Time 13.2.13 Slack 13.2.14 Required Time and Arrival Time 13.2.15 Timing Paths 13.3 Timing Checks 13.3.1 Setup Timing Check 13.3.2 Hold Timing Check 13.4 Timing Checks for Different Timing Paths 13.4.1 Setup Check for Flip-Flop to Flip-Flop Timing Path 13.4.2 Setup and Hold Check for Input to Flip-Flop Timing Path 13.4.3 Setup Check for Flip-Flop to Output Timing Path 13.4.4 Setup Check for Input to Output Timing Path 13.4.5 Multicycle Paths 13.4.6 False Paths 13.4.7 Half Cycle Paths 13.5 Asynchronous Checks 13.5.1 Recovery Timing Check 13.5.2 Removal Timing Check 13.6 Maximum Frequency Computation 13.7 Maximum Allowable Skew 13.8 Frequently Asked Questions 13.9 Conclusion 14 Digital System Implementation 14.1 Introduction 14.2 FPGA Implementation 14.2.1 Internal Structure of FPGA 14.2.2 FPGA Implementation Using XILINX EDA Tool 14.2.3 Design Verification 14.2.4 FPGA Editor 14.3 ASIC Implementation 14.3.1 Simulation and Synthesis 14.3.2 Placement and Routing 14.4 Frequently Asked Questions 14.5 Conclusion 15 Low-Power Digital System Design 15.1 Introduction 15.2 Different Types of Power Consumption 15.2.1 Switching Power 15.2.2 Short Circuit Power 15.2.3 Leakage Power 15.2.4 Static Power 15.3 Architecture-Driven Voltage Scaling 15.3.1 Serial Architecture 15.3.2 Parallel Architecture 15.3.3 Pipeline Architecture 15.4 Algorithmic Optimization 15.4.1 Minimizing the Hardware Complexity 15.4.2 Selection of Data Representation Techniques 15.5 Architectural Optimization 15.5.1 Choice of Data Representation Techniques 15.5.2 Ordering of Input Signals 15.5.3 Reducing Glitch Activity 15.5.4 Choice of Topology 15.5.5 Logic Level Power Down 15.5.6 Synchronous Versus Asynchronous 15.5.7 Loop Unrolling 15.5.8 Operation Reduction 15.5.9 Substitution of Operation 15.5.10 Re-timing 15.5.11 Wordlength Reduction 15.5.12 Resource Sharing 15.6 Frequently Asked Questions 15.7 Conclusion 16 Digital System Design Examples 16.1 FPGA Implementation FIR Filters 16.1.1 FIR Low-Pass Filter 16.1.2 Advanced DSP Blocks 16.1.3 Different Filter Structures 16.1.4 Performance Estimation 16.1.5 Conclusion 16.1.6 Top Module for FIR Filter in Transposed Direct Form 16.2 FPGA Implementation of IIR Filters 16.2.1 IIR Low-Pass Filter 16.2.2 Different IIR Filter Structures 16.2.3 Pipeline Implementation of IIR Filters 16.2.4 Performance Estimation 16.2.5 Conclusion 16.3 FPGA Implementation of K-Means Algorithm 16.3.1 K-Means Algorithm 16.3.2 Example of K-Means Algorithm 16.3.3 Proposed Architecture 16.3.4 Design Performance 16.3.5 Conclusion 16.4 Matrix Multiplication 16.4.1 Matrix Multiplication by Scalar–Vector Multiplication 16.4.2 Matrix Multiplication by Vector–Vector Multiplication 16.4.3 Systolic Array for Matrix Multiplication 16.5 Sorting Architectures 16.5.1 Parallel Sorting Architecture 1 16.5.2 Parallel Sorting Architecture 2 16.5.3 Serial Sorting Architecture 16.5.4 Sorting Processor Design 16.6 Median Filter for Image De-noising 16.6.1 Median Filter 16.6.2 FPGA Implementation of Median Filter 16.7 FPGA Implementation of 8-Point FFT 16.7.1 Data Path for 8-Point FFT Processor 16.7.2 Control Path for 8-Point FFT Processor 16.8 Interfacing ADC Chips with FPGA Using SPI Protocol 16.9 Interfacing DAC Chips with FPGA Using SPI Protocol 16.10 Interfacing External Devices with FPGA Using UART 16.11 Conclusion 17 Basics of System Verilog 17.1 Introduction 17.2 Language Elements 17.2.1 Logic Literal Values 17.2.2 Basic Data Types 17.2.3 User Defined Data-Types 17.2.4 Enumeration Data Type 17.2.5 Arrays 17.2.6 Dynamic Arrays 17.2.7 Associative Array 17.2.8 Queues 17.2.9 Events 17.2.10 String Methods 17.3 Composite Data Types 17.3.1 Structures 17.3.2 Unions 17.3.3 Classes 17.4 Expressions 17.4.1 Parameters and Constants 17.4.2 Variables 17.4.3 Operators 17.4.4 Set Membership Operator 17.4.5 Static Cast Operator 17.4.6 Dynamic Casting 17.4.7 Type Operator 17.4.8 Concatenation of String Data Type 17.4.9 Streaming Operators 17.5 Behavioural Modelling 17.5.1 Procedural Constructs 17.5.2 Loop Statements 17.5.3 Case Statement 17.5.4 If Statement 17.5.5 Final Statement 17.5.6 Disable Statement 17.5.7 Event Control 17.5.8 Continuous Assignment 17.5.9 Parallel Blocks 17.5.10 Process Control 17.6 Structural Modelling 17.6.1 Module Prototype 17.7 Summary 18 Advanced FPGA Implementation Techniques 18.1 Introduction 18.2 System-On-Chip Implementation 18.2.1 Implementations Using SoC FPGAs 18.2.2 AXI Protocol 18.2.3 AXI Protocol Features 18.3 Partial Re-configuration (PR) 18.3.1 Dynamic PR 18.3.2 Advantages of DPR 18.3.3 DPR Techniques 18.3.4 DPR Terminology 18.3.5 DPR Tools 18.3.6 DPR Flow 18.3.7 Communication Between Reconfigurable Modules 18.4 Conclusion Appendix References Index