Transcript 1 - La Salle University

Shift registers and Floating
Point Numbers
Chapter 11 in Tokheim
PHY 201 (Blum)
1
What are they?
Recall that a register is a small piece of
memory that holds values.
In addition to holding values, a shift
register performs a simple operation on
the values; it moves them to the left or
to the right.
PHY 201 (Blum)
2
Example
Serial
output
Serial
input
Shift register
0
1
0
1
0
1
1
1
1
0
1
0
1
1
1
0
0
1
0
1
1
1
0
1
1
0
1
1
1
0
1
0
PHY 201 (Blum)
3
Parallel loading register
PHY 201 (Blum)
4
Register
On the previous slide, the input of a
flip-flop is selected from two possible
choices
The output of the same flip-flop
The data switch above
Recall that selecting from one of two
inputs is done by a 2-to-1 MUX.
The load line serves as the address/select
input.
PHY 201 (Blum)
5
When Load is high, we are selecting the data switches to be the
data input. So when we go through a positive edge of the clock,
we are writing the value from the data switches to the register.
PHY 201 (Blum)
6
When Load is low, we are selecting the flip-flop’s output to be
the data input. So when we go through a positive clock edge, we
are writing the value from the flip-flop to the flip-flop – thus
keeping the value the same as before (holding).
PHY 201 (Blum)
7
Register  Shift Register
We can adapt the previous circuit to make a
shift register.
Instead of having one of the two possible inputs
for a flip-flop come from the output of the same
flip-flop, we can change this to having that input
come from an adjacent flip-flop.
Then if when the load input is low and we go
through a positive clock edge, the effect is not to
hold the values of the register but to shift them.
This is part of the lab.
PHY 201 (Blum)
8
On the ends
If one shifts from the right to the left, then
the input to the rightmost flip-flop does not
come from an adjacent flip-flop during the
shift operation. There are several options
Data switch input
Always 1
Always 0
Use leftmost output to form a ring
PHY 201 (Blum)
9
How are shift registers used?
Modems
Cyclic Redundancy Check (CRC)
Multiplication
Adding floats
PHY 201 (Blum)
10
Modems
A modem (Modulator-Demodulator) takes a
signal from a computer and places it on a
transmission line.
A transmitting modem modulates, that is,
converts a digital signal from a computer to a
pseudo-analog signal more appropriate for a
transmission line.
The receiving modem demodulates, that is,
converts the pseudo-analog signal back into
digital form.
PHY 201 (Blum)
11
Modems (Cont.)
But the aspect of modems relevant here is
that
The transmitting modem converts parallel data to
serial.
The receiving modem converts serial data into
parallel form.
Inside the computer, data that moves around
as words on parallel cables having a
connection for each bit in the word.
The transmission lines are longer and require
data to be sent serially (one bit at a time).
PHY 201 (Blum)
12
Parallel to Serial
To leave the computer, data
moves into register in parallel,
several bits at once.
1
0
PHY 201 (Blum)
1
0
0
Data then moves out of
the register serially, one
bit at a time.
13
Serial to Parallel
1
0
1
0
0
To enter the
computer, data
enters the register in
serial, one bit at a
time.
Data then moves out of the
register in parallel.
DEMO!
PHY 201 (Blum)
14
Cyclic Redundancy Check
In order to check for errors that may occur
during transmission, the sender calculates a
number, a cyclic redundancy check. The
receiver does the same calculation. If they
agree, then presumably no error occurred in
transmission.
Actually the receiver does a calculation that
includes the sender’s CRC as part of the data
and should get an answer of zero.
It’s easier electronically to see if series of bits
corresponds to zero.
PHY 201 (Blum)
15
CRC
Any mathematical operation performed on the
transmitted data could serve as a check.
Another common calculation is summing, then it is
called a checksum.
The calculation should not be time consuming.
Think of CRC as a funny kind of division, the
remainder from the division is the check.
It’s not ordinary division, but a strange kind of
division that is easy to realize electronically.
PHY 201 (Blum)
16
CRC = Shift register + XORs
Basically one has a shift register with a few
excluded OR gates inserted in strategic positions.
PHY 201 (Blum)
17
0

0
0
0

11000001010
1

1
0
0

0001010
0

0
0
1

001010
0

0
1
0

01010
PHY 201 (Blum)
18
0

1
0
0

1010
1

0
0
1

010
1

0
1
1

10
1

1
1
0

0
0

1
0
1

PHY 201 (Blum)
19
Multiplication: Shift and add

+
PHY 201 (Blum)
1
1
0
0
1
1
0
0
0
1
1
1
0
0
1
0
0
0
0
0
0
0
1
0
1
1
1
1
shift
shift
0
1
1
20
Fractions
Similar to what we’re used to with decimal
numbers
3.14159 = 3 · 100 + 1 · 10-1 + 4 · 10-2
+ 1 · 10-3 + 5 · 10-4 + 9 · 10-5
11.001001 =
1 · 21 + 1 · 20 + 0 · 2-1 + 0 · 2-2
+ 1 · 2-3 + 0 · 2-4 + 0 · 2-5
+ 1 · 2-6
(11.001001  3.140625)
PHY 201 (Blum)
21
Converting decimal to binary II
98.61
Integer part
98 / 2
49 / 2
24 / 2
12 / 2
6/2
3/2
1/2
= 49
= 24
= 12
= 6
= 3
= 1
= 0
remainder
remainder
remainder
remainder
remainder
remainder
remainder
0
1
0
0
0
1
1
1100010
PHY 201 (Blum)
22
Converting decimal to binary III
98.61
Fractional part
0.61  2 = 1.22
0.22  2 = 0.44
0.44  2 = 0.88
0.88  2 = 1.76
0.76  2 = 1.52
0.52  2 = 1.04
.100111
PHY 201 (Blum)
23
Converting decimal to binary IV
Put together the integral and fractional
parts
98.61  1100010.100111
PHY 201 (Blum)
24
Another Example (Whole number part)
123.456
Integer part
123 / 2
61 / 2
30 / 2
15 / 2
7/2
3/2
1/2
= 61
= 30
= 15
= 7
= 3
= 1
= 0
remainder
remainder
remainder
remainder
remainder
remainder
remainder
1
1
0
1
1
1
1
1111011
PHY 201 (Blum)
25
Checking: Go to
Programs/Accessories/Calculator
PHY 201 (Blum)
26
Put the calculator in Scientific view
PHY 201 (Blum)
27
Enter number, put into binary mode
PHY 201 (Blum)
28
Another Example (fractional part)
123.456
Fractional part
0.456 
0.912 
0.824 
0.648 
0.296 
0.592 
0.184 
…
2
2
2
2
2
2
2
=
=
=
=
=
=
=
0.912
1.824
1.648
1.296
0.592
1.184
0.368
.0111010…
PHY 201 (Blum)
29
Checking fractional part: Enter digits
found in binary mode
Note that the leading zero does not display.
PHY 201 (Blum)
30
Convert to decimal mode, then
PHY 201 (Blum)
31
Divide by 2 raised to the number of digits
(in this case 7, including leading zero)
PHY 201 (Blum)
32
In most cases it will not be exact
PHY 201 (Blum)
33
Other way around
Multiply fraction by 2 raised to the desired
number of digits in the fractional part. For
example
.456  27 = 58.368
Throw away the fractional part and represent
the whole number
58 111010
But note that we specified 7 digits and the
result above uses only 6. Therefore we need
to put in the leading 0
0111010
PHY 201 (Blum)
34
Fixed point
If one has a set number of bits reserved
for representing the whole number part
and another set number of bits
reserved for representing the fractional
part of a number, then one is said to be
using fixed point representation.
The point dividing whole number from
fraction has an unchanging place in the
number.
PHY 201 (Blum)
35
Limits of the fixed point approach
Suppose you use 4 bits for the whole
number part and 4 bits for the fractional
part (ignoring sign for now).
The largest number would be
1111.1111 = 15.9375
The smallest, non-zero number would
be 0000.0001 = .0625
PHY 201 (Blum)
36
Floating point representation
Floating point representation allows one
to represent a wider range of numbers
using the same number of bits.
It is like scientific notation.
PHY 201 (Blum)
37
Scientific notation
Used to represent very large and very
small numbers
Ex. Avogadro’s number
 6.0221367  1023 particles
 602213670000000000000000
Ex. Fundamental charge e
 1.60217733  10-19 C
 0.000000000000000000160217733 C
PHY 201 (Blum)
38
Scientific notation: all of these are
the same number
12345.6789
= 1234.56789  100
1234.56789  10 = 1234.56789  101
123.456789  100 =123.456789  102
12.3456789  103
1.23456789  104
Rule: Shift the point to the left and
increment the power of ten.
PHY 201 (Blum)
39
Small numbers
0.000001234
0.00001234  10-1
0.0001234  10-2
0.001234  10-3
0.01234  10-4
0.1234  10-5
1.234  10-6
Rule: shift point to the right and decrement
the power.
PHY 201 (Blum)
40
Floating Point Rules
Starting with the fixed point binary
representation, shift the point and
increase the power (of 2 now that we’re
in binary)
Shift so that the number has no whole
number part and also so that the first
fractional bit (the half’s place) has a
1.
PHY 201 (Blum)
41
Floats
SHIFT expression so it is just under 1
and keep track of the number of shifts
1100010.1001100110011001
.11000101001100110011001  27
Express the number of shifts in binary
.11000101001100110011001  200000111
PHY 201 (Blum)
42
Mantissa and Exponent and Sign
.11000101001100110011001  200000111
(Significand) Mantissa
.11000101001100110011001  200000111
Exponent
The number may be negative, so there
a bit (the sign bit) reserved to indicate
whether the number is positive or
negative
PHY 201 (Blum)
43
Biasing
Actually the exponent is not represented as
shown on the previous slide
There were 8 bits used to represent the
exponent on the previous slide, that means
there are 256 numbers that could be
represented
Since the exponent could be negative (to
represent numbers less than 1), we choose
half of the range to be positive and half to be
negative , i.e. -128 to 127
PHY 201 (Blum)
44
Biasing (Cont.)
In biasing, one does not use 2’s
complement or a sign bit.
Instead one adds a bias (equal to the
magnitude of the most negative
number) to the exponents and
represents the result of that addition.
PHY 201 (Blum)
45
Biasing (Cont.)
With 8 bits, the bias is 128.
We had to shift 7 times to the left,
corresponding to an exponent of +7
We add that to the bias 128+7=135
That is the number we put in the exponent
portion: 10000111
(In the IEEE 754 format for floats, you bias
by one less (127) and reserve the exponents
00000000 and 11111111 for special
purposes.)
PHY 201 (Blum)
46
Big floats
Assume we use 8 bits, 4 for the mantissa and
4 for the exponent (neglecting sign). What is
the largest float?
Mantissa: 1111 Exponent 1111
0.9375  27
=120
(Compare this to the largest fixed-point
number using the same amount of space
15.9375)
PHY 201 (Blum)
47
Small floats
Assume we use 8 bits, 4 for the mantissa and
4 for the exponent (neglecting sign). What is
the smalles float?
Mantissa: 1000 Exponent 0000
0.5  2-8
= 0.001953125
(Compare this to the smallest fixed-point
number using the same amount of space
.0625)
PHY 201 (Blum)
48
One more fine point
As discussed so far, the mantissa (significand)
always starts with a 1.
When storage was expensive, designers
opted not to represent this bit, since it is
always 1.
It had to be inserted for various operations
on the number (adding, multiplying, etc.), but
it did not have to be stored.
PHY 201 (Blum)
49