# Digital Integrated Integrated Circuit Design...  VLSI Design and VLSI Circuit Design all ... However,

• View
222

5

Embed Size (px)

### Text of Digital Integrated Integrated Circuit Design...  VLSI Design and VLSI Circuit Design all ......

IUST

Lecture 13 Building Blocks (Multipliers)

Digital Integrated Circuit Design

Register

Shift Register

• IUST: Digital IC Design LECTURE 13 : Building BlocksLECTURE 13 : Building Blocks Adib Abrishamifar 20092/76

} This lecture note has been summarized and categorized from lecture note on Introduction to VLSI Design and VLSI Circuit Design all over the world. I cant remember where those slide come from. However, Id like to thank all professors who create such a good work on those lecture notes. Without those lectures, this slide cant be finished.

Acknowledgement

• IUST: Digital IC Design LECTURE 13 : Building BlocksLECTURE 13 : Building Blocks Adib Abrishamifar 20093/76

Contents

} Outline} Introduction} Signed Integers} Review - Multiplication} Multipliers} Sequential (Serial) Multiplier} Array Multipliers

Combinational Multiplier Booth Multiplier Pipelined Multiplier Wallace Tree Multiplier Carry Save Multiplier

} Serial-Parallel Multiplier} Summary

• IUST: Digital IC Design LECTURE 13 : Building BlocksLECTURE 13 : Building Blocks Adib Abrishamifar 20094/76

Outline

} Building Blocks for Digital Architectures} Arithmetic unit

Bit-sliced datapath (Adders, Multipliers, Shifters, Comparators, etc.)

} Memory RAM, ROM, Buffers, Shift registers

} Control Finite state machine (PLA, random logic) Counters

} Interconnect Switches Arbiters Bus

• IUST: Digital IC Design LECTURE 13 : Building BlocksLECTURE 13 : Building Blocks Adib Abrishamifar 20095/76

Contents

} Outline} Introduction} Signed Integers} Review - Multiplication} Multipliers} Sequential (Serial) Multiplier} Array Multipliers

Combinational Multiplier Booth Multiplier Pipelined Multiplier Wallace Tree Multiplier Carry Save Multiplier

} Serial-Parallel Multiplier} Summary

• IUST: Digital IC Design LECTURE 13 : Building BlocksLECTURE 13 : Building Blocks Adib Abrishamifar 20096/76

Introduction

} Multipliers are used in a lot of DSP applications} Vector product, matrix multiplication} Convolution} Filtering (tap filters, FIR, )} ...

} At least one good reason for studying multiplication and division is that there is an infinite number of ways of performing these operations

• IUST: Digital IC Design LECTURE 13 : Building BlocksLECTURE 13 : Building Blocks Adib Abrishamifar 20097/76

Contents

} Outline} Introduction} Signed Integers} Review - Multiplication} Multipliers} Sequential (Serial) Multiplier} Array Multipliers

Combinational Multiplier Booth Multiplier Pipelined Multiplier Wallace Tree Multiplier Carry Save Multiplier

} Serial-Parallel Multiplier} Summary

• IUST: Digital IC Design LECTURE 13 : Building BlocksLECTURE 13 : Building Blocks Adib Abrishamifar 20098/76

Signed Integers

} What Not to Do} Use fixed length binary representation} Use left-most bit (called most significant bit or MSB)

for sign:0 for positive1 for negative

} Example: +18ten = 00010010two18ten = 10010010two

• IUST: Digital IC Design LECTURE 13 : Building BlocksLECTURE 13 : Building Blocks Adib Abrishamifar 20099/76

Signed Integers

} Why Not to Use Sign Bit} Sign and magnitude bits should be differently treated

in arithmetic operations} Addition and subtraction require different logic

circuits} Overflow is difficult to detect} Zero has two representations:

+ 0ten = 00000000two 0ten = 10000000two

} Signed-integers are not used in modern computers

• IUST: Digital IC Design LECTURE 13 : Building BlocksLECTURE 13 : Building Blocks Adib Abrishamifar 200910/76

Signed Integers

} Integers With Sign Other Ways} Use fixed-length representation, but no sign bit

1s complement: To form a negative number, complement each bit in the given number

2s complement: To form a negative number, start with the given number, subtract one, and then complement each bit, or first complement each bit, and then add 1

} 2s complement is the preferred representation

• IUST: Digital IC Design LECTURE 13 : Building BlocksLECTURE 13 : Building Blocks Adib Abrishamifar 200911/76

Signed Integers

} 2s-Complement} Why not 1s-complement? Dont like two zeros} Add 1 to 1s-complement representation} Some properties:

Only one representation for 0 Exactly as many positive numbers as negative numbers Slight asymmetry there is one negative number with no

positive counterpart

• IUST: Digital IC Design LECTURE 13 : Building BlocksLECTURE 13 : Building Blocks Adib Abrishamifar 200912/76

0000

10000111

1111

1010 = 2

Signed integers

0000

1000

1111

1010 = 5

1s complement integers

0010

1010 1010

0101

2

25

5

0000

1000

1111

10000

1010 = 6

2s complement integers

1010 01106 6

0 0

0

7 87 7

0

07

7

Signed Integers

}} Three SystemsThree Systems

• IUST: Digital IC Design LECTURE 13 : Building BlocksLECTURE 13 : Building Blocks Adib Abrishamifar 200913/76

Sign-magnitude

000 = +0001 = +1010 = +2011 = +3100 = - 0101 = - 1110 = - 2111 = - 3

2s complement

000 = +0001 = +1010 = +2011 = +3100 = - 4101 = - 3110 = - 2111 = - 1

(Preferred)

1s complement

000 = +0001 = +1010 = +2011 = +3100 = - 3101 = - 2110 = - 1111 = - 0

Signed Integers

}} Three RepresentationsThree Representations

• IUST: Digital IC Design LECTURE 13 : Building BlocksLECTURE 13 : Building Blocks Adib Abrishamifar 200914/76

Signed Integers

} 2s Complement n-bit Numbers} Range: 2n 1 through 2n 1 1 } Unique zero: 00000000 . . . . . 0} Expansion of bit length: stretch the left-most bit all the

way, e.g., 11111101 is still 3.} Overflow rule: If two numbers with the same sign bit

(both positive or both negative) are added, the overflow occurs if and only if the result has the opposite sign

• IUST: Digital IC Design LECTURE 13 : Building BlocksLECTURE 13 : Building Blocks Adib Abrishamifar 200915/76

an-1an-2 . . . a1a0 = -2n-1an-1 + 2i aii=0

n-2

-128 64 32 16 8 4 2 18-bit conversion box

-128 64 32 16 8 4 2 11 1 1 1 1 1 0 1

Example

-128+64+32+16+8+4+1 = -128 + 125 = -3

Signed Integers

} 2s-Compliment to Decimal Conversion

• IUST: Digital IC Design LECTURE 13 : Building BlocksLECTURE 13 : Building Blocks Adib Abrishamifar 200916/76

Contents

} Outline} Introduction} Signed Integers} Review - Multiplication} Multipliers} Sequential (Serial) Multiplier} Array Multipliers

Combinational Multiplier Booth Multiplier Pipelined Multiplier Wallace Tree Multiplier Carry Save Multiplier

} Serial-Parallel Multiplier} Summary

• IUST: Digital IC Design LECTURE 13 : Building BlocksLECTURE 13 : Building Blocks Adib Abrishamifar 200917/76

} Basic algorithm analogous to decimal multiplication} Break multiplier into digits} Multiply one digit at a time;

shift multiplicand to form partial products} Create product as sum of partial products

} n bit multiplicand X m bit multiplier = (n+m) bit product

Multiplicand 0110 (6)Multiplier X 0011 (3)

0110011000000000

Product 00010010 (18)

Partial Products

Review - Multiplication

• IUST: Digital IC Design LECTURE 13 : Building BlocksLECTURE 13 : Building Blocks Adib Abrishamifar 200918/76

0 1 0 1 +5x0 0 1 1 +30 1 0 1

0 1 0 10 0 0 0

0 0 0 00 0 0 1 1 1 1 +15

1 0 1 1 -5x0 0 1 1 +3

1 1 1 1 0 1 11 1 1 0 1 10 0 0 0 00 0 0 01 1 1 0 0 0 1 -15

Review - Multiplication

} 2s complement} Multiplier positive, Multiplicand +/- :

Sign extend the partial products when adding up Example:

• IUST: Digital IC Design LECTURE 13 : Building BlocksLECTURE 13 : Building Blocks Adib Abrishamifar 200919/76

} 2s complement (cont.)} Mplier negative, Mcand +/- :

convert negative Mplier to positive, do the multiplication, negate the result

Example:

1 0 1 1 -5x1 1 0 1 -3

1 0 1 1 -5x0 0 1 1 +3

1 1 1 1 0 1 11 1 1 0 1 10 0 0 0 00 0 0 01 1 1 0 0 0 1 -150 0 0 1 1 1 1 +15

Review - Multiplication

• IUST: Digital IC Design LECTURE 13 : Building BlocksLECTURE 13 : Building Blocks Adib Abrishamifar 200920/76

Iteration Step Multiplicand Product

0 Initial values 0010 0000 0011

1 LSB=1 => Prod=Prod+Mcand 0010 0010 0011

Right shift product 0010 0001 0001

2 LSB=1 => Prod=Prod+Mcand 0010 0011 0001

Right shift product 0010 0001 1000

3 LSB=0 => no operation 0010 0001 1000

Right shift product 0010 0000 1100

4 LSB=0 => no operation 0010 0000 1100

Right shift product 0010 0000 0110

0010two 0011two = 0110two, i.e., 2ten3ten = 6ten

Review - Multiplication

} Example

• IUST: Digital IC Design LECTURE 13 : Building BlocksLECTURE 13 : Building Blocks Adib Abrishamifar 200921/76

Iteration Step Multiplicand Product

0 Initial values 11010 00000 0011

1 LSB=1 => Prod=Prod+Mcand 11010 11010 0011

Right shift product 11010 11101 0001

2 LSB=1 => Prod=Prod+Mcand 11010 10111 0001

Right shift product 11010 11011 1000

3 LSB=0 => no operation 11010 11011 1000

Right shift product 11010 11101 1100

4 LSB=0 => no operation 11010 11101 1100

Right shift product 11010 11110 1110

1010two 0011two = 101110two, i.e., -6ten

Recommended ##### Introduction to VLSI Design – Lec01. Chapter 1 Introduction to VLSI Design Lecture # 2 A Circuit Design Example
Documents ##### Combinational Circuit Design - ee.nthu.edu.t .Combinational Circuit Design CHAPTER 5. VLSI Design
Documents ##### Lecture 16: Circuit 16: Circuit Pitfalls CMOS VLSI DesignCMOS VLSI Design 4th Ed. 12 Reliability Hard
Documents ##### ECL VLSI ASIC 100K Circuit Design Optimization - HP .ECL VLSI ASIC lOOK CIRCUIT DESIGN OPTIMIZATION
Documents ##### Lecture 11: Sequential Circuit Design. CMOS VLSI DesignCMOS VLSI Design 4th Ed. 11: Sequential Circuits2 Outline  Sequencing  Sequencing Element Design
Documents ##### VLSI 2019-12-30آ  15A04604 VLSI DESIGN Course Objectives: To understand VLSI circuit design processes
Documents ##### ECEN474: (Analog) VLSI Circuit Design Fall Spalermo/Ecen474/Lecture25_ee474_vgas.pdfECEN474: (Analog)
Documents ##### VLSI Circuit Performance Optimization by Geometric Done/2001-7-AOR-CC.pdfآ  Keywords: VLSI design, unary
Documents Documents
{"ft_lang_label":"__label__en","ft_lang_prob":0.5270867,"math_prob":0.8132701,"size":8677,"snap":"2021-43-2021-49","text_gpt3_token_len":2686,"char_repetition_ratio":0.2243745,"word_repetition_ratio":0.34397164,"special_character_ratio":0.33145097,"punctuation_ratio":0.08972603,"nsfw_num_words":0,"has_unicode_error":false,"math_prob_llama3":0.95514035,"pos_list":[0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28],"im_url_duplicate_count":[null,null,null,null,null,null,null,null,null,null,null,null,null,null,null,null,null,null,null,null,null,null,null,null,null,null,null,null,null],"WARC_HEADER":"{\"WARC-Type\":\"response\",\"WARC-Date\":\"2021-10-23T01:13:35Z\",\"WARC-Record-ID\":\"<urn:uuid:245674e3-59e6-44fd-98a8-05c9fe48a402>\",\"Content-Length\":\"99585\",\"Content-Type\":\"application/http; msgtype=response\",\"WARC-Warcinfo-ID\":\"<urn:uuid:4679cc51-9eaf-476e-8776-f3511f2a05e6>\",\"WARC-Concurrent-To\":\"<urn:uuid:f5d66843-00a5-4522-890b-0d4b36c39174>\",\"WARC-IP-Address\":\"51.254.158.8\",\"WARC-Target-URI\":\"https://dokumen.tips/documents/digital-integrated-integrated-circuit-design-vlsi-design-and-vlsi-circuit.html\",\"WARC-Payload-Digest\":\"sha1:GHIVGWGOFZMLHM7IB2GKTXZ6AGX4PMSI\",\"WARC-Block-Digest\":\"sha1:BX2PHQ5ZKGCCCG5HBW6CRXSY2Z7QAUQB\",\"WARC-Identified-Payload-Type\":\"text/html\",\"warc_filename\":\"/cc_download/warc_2021/CC-MAIN-2021-43/CC-MAIN-2021-43_segments_1634323585537.28_warc_CC-MAIN-20211023002852-20211023032852-00168.warc.gz\"}"}