# 程序代写代做代考 Microsoft PowerPoint – 054-power-of-2-checker

Microsoft PowerPoint – 054-power-of-2-checker

9/26/2016

University of Illinois at Urbana-Champaign

Dept. of Electrical and Computer Engineering

ECE 120: Introduction to Computing

A Power-of-Two Checker

ECE 120: Introduction to Computing © 2016 Steven S. Lumetta. All rights reserved. slide 1

Powers of Two are Easy to Spot in Binary

Let’s do another bit-sliced design.

Can we check whether an unsigned number

represents a power of two?

What does a power of two look like in bits?

For 5-bit unsigned, the powers of 2 are…

00001, 00010, 00100, 01000, 10000

A power of two has exactly one 1 bit

(with place value 2N for some N, of course!).

ECE 120: Introduction to Computing © 2016 Steven S. Lumetta. All rights reserved. slide 2

The Answers are Not Always Enough

So our design will answer the following:

Is A = aN-1aN-2…a1a0 a power of two?

How many answers are possible?

Two: Yes, and No.

A trick question:

How many bits do we need to pass

between slices?

That’s right: TWO bits.

ECE 120: Introduction to Computing © 2016 Steven S. Lumetta. All rights reserved. slide 3

What Extra Information Do We Need?

Why not just one? An answer only needs 1 bit!

Say that we pass bits from right to left.

If the bits aN-2…a1a0 represent a power of two,

can aN-1aN-2…a1a0 be a power of two?

What if aN-2…a1a0 does not

represent a power of two?

In that case, we can’t tell whether

aN-1aN-2…a1a0 is a power of two or not!

What else do we need to know?

ECE 120: Introduction to Computing © 2016 Steven S. Lumetta. All rights reserved. slide 4

No.

9/26/2016

For Inductive Step, We Must Know Whether all Bits are 0

Imagine that we have completed N-1 bits.

Under what conditions can number A be a

power of two?

1. aN-1 = 1 and the rest is all 0s, or

2. aN-1 = 0 and the rest is a power of two.

For #2, we need to know whether the rest

of the bits form a power of two.

But for #1, we also need to know whether

the rest of the bits are all 0.

ECE 120: Introduction to Computing © 2016 Steven S. Lumetta. All rights reserved. slide 5

There are Three Possible Messages between Bit Slices

The “yes” cases for #1 and #2 do not overlap:

all 0 bits is not a power of two.

The “no” cases need not be further separated:

◦all 0s means no 1 bits

◦a power of two means one 1 bit

◦more than one 1 bit means

“no” to both questions

That’s all we need to know. Three possible

messages between slices, so two bits.

ECE 120: Introduction to Computing © 2016 Steven S. Lumetta. All rights reserved. slide 6

We Need a Representation for Answers

ECE 120: Introduction to Computing © 2016 Steven S. Lumetta. All rights reserved. slide 7

I’ll use the following representation.

Others may be

better. C1 C0 meaning

0 0 no 1 bits

0 1 one 1 bit

1 0 not used

1 1 more than

one 1 bit

We Need a Representation for Answers

ECE 120: Introduction to Computing © 2016 Steven S. Lumetta. All rights reserved. slide 8

Let’s build a slice that

operates on two bits of A.

In the bit slice, we call them A and B.

Inputs from the previous bit slice

are C1 and C0.

Outputs to the next bit slice

are Z1 and Z0.

Direction of our operation doesn’t matter.

Either will do.

9/26/2016

Two Zeroes Do Not Change the Result

ECE 120: Introduction to Computing © 2016 Steven S. Lumetta. All rights reserved. slide 9

Let’s fill in a truth table.

We’ll start with the case of A = 0 and B = 0.

A B C1 C0 meaning Z1 Z0 meaning

0 0 0 0 no 1s

0 0 0 1 one 1

0 0 1 0 ???

0 0 1 1 >one 1

no 1s

>one 1

one 1

don’t care

0 0

0 1

x x

1 1

One 1 Input Increments the Count of 1 Bits

ECE 120: Introduction to Computing © 2016 Steven S. Lumetta. All rights reserved. slide 10

Now consider A = 0 and B = 1.

A B C1 C0 meaning Z1 Z0 meaning

0 1 0 0 no 1s

0 1 0 1 one 1

0 1 1 0 ???

0 1 1 1 >one 1

one 1

>one 1

>one 1

don’t care

0 1

1 1

x x

1 1

One 1 Input Increments the Count of 1 Bits

ECE 120: Introduction to Computing © 2016 Steven S. Lumetta. All rights reserved. slide 11

The case for A = 1 and B = 0 is the same.

A B C1 C0 meaning Z1 Z0 meaning

1 0 0 0 no 1s

1 0 0 1 one 1

1 0 1 0 ???

1 0 1 1 >one 1

one 1

>one 1

>one 1

don’t care

0 1

1 1

x x

1 1

Two 1s in the Number Rules Out Powers of Two

ECE 120: Introduction to Computing © 2016 Steven S. Lumetta. All rights reserved. slide 12

Finally, consider A = 1 and B = 1.

A B C1 C0 meaning Z1 Z0 meaning

1 1 0 0 no 1s

1 1 0 1 one 1

1 1 1 0 ???

1 1 1 1 >one 1

>one 1

>one 1

>one 1

don’t care

1 1

1 1

x x

1 1

9/26/2016

We Solve Z1 as a POS Expression

ECE 120: Introduction to Computing © 2016 Steven S. Lumetta. All rights reserved. slide 13

Let’s use a K-map to solve Z1. POS looks good.

What are the loops?

(C1 + A + B)

(C0 + A)

(C0 + B)

So Z1 = (C1 + A + B)

(C0 + A)(C0 + B)

Z1

AB

00 01 11 10

C1C0

00 0 0 1 0

01 0 1 1 1

11 1 1 1 1

10 x x x x

We Solve Z0 as an SOP Expression

ECE 120: Introduction to Computing © 2016 Steven S. Lumetta. All rights reserved. slide 14

Now let’s solve Z0. SOP and POS are the

same.

What are the loops

for SOP?

C0

A

B

So Z0 = (C0 + A + B)

Z0

AB

00 01 11 10

C1C0

00 0 1 1 1

01 1 1 1 1

11 1 1 1 1

10 x x x x

We Can Reuse Some Factors with Algebra

ECE 120: Introduction to Computing © 2016 Steven S. Lumetta. All rights reserved. slide 15

Notice that we can reuse factors

from Z1 to calculate Z0:

Z1 = (C1 + A + B)(C0 + A)(C0 + B)

Z0 = (C0 + A + B) = (C0 + A) + (C0 + B)

Let’s draw the bit slice, then analyze its

area and delay.

Area is 6N, and Delay is N Gate Delays for N Bits

Here is an implementation of the bit

slice using NAND and NOR. Let’s find area.

How many literals?

How many operations?

And delay?

2 on all paths.

So N gate delays

for N bits.

ECE 120: Introduction to Computing © 2016 Steven S. Lumetta. All rights reserved. slide 16

C0

B

C0

A

C1

A

B Z1

Z0

7

5 (4 NOR, 1 NAND)

9/26/2016

Need One More Gate Delay to Get the Answer

But we don’t get an answer!

Our N-bit checker,

◦ composed of N/2 bit slices,

◦ produces only a “count” of 1 bits

(0, 1, or “many”).

We want yes (P = 1) or no (P = 0)!

Looking at the representation, the fastest solution

is to add an XOR gate at the end.

P = Z1 Z0 from the last bit slice.

So delay is actually N + 1 gate delays.

ECE 120: Introduction to Computing © 2016 Steven S. Lumetta. All rights reserved. slide 17