Transcript 슬라이드 1

Digital Convergence!
•
Smart Phone: IT + Telecommunication + Consumer Electronics + Entertainment
•
Analog vs Digital system
Ex: Watch, LP vs CD, Camera
- Why Digital?
- Representation? Continuous vs Discrete Signals (value, time)
continuous: discrete-time, analog: digital
- Noise?, Accuracy?
Resolution: # of digits used to represent the signals
•
Digital circuits: process digital input signals and output digital signals
ref. Analog to Digital Converter, D/A Converter
•
Digital logic: fundamental theories and practices for designing the digital circuits
•
Course Objectives:
- Learn to analyze and design digital circuits; namely, combinational circuits and
sequential circuits.
1
Digital Logic
• Professor:
김 재희 교수
B619, 2123-2869
[email protected]
• Teaching Assistant:
고준범 선생
2123-4537
B618
• Homepage:
cherup.yonsei.ac.kr
2
Digital Logic
•
Text: Fundamentals of Digital Logic, by Charles H. Roth, Jr., 6th Edition
Reference: Computer Engineering: Hardware Design, by Mano
more..
•
Course Objective:
컴퓨터를 포함한 여러 디지탈 시스템의 구성 요소가 되는, 다양한 디지탈 회로
를 이해하고 설계할 수 있는 기법을 익힘.
•
Summary of Course:
Boolean Algebra, Logic Gates, Design of Combinational Circuits,
Multiplexers, Programmable Logic Devices, Latches and Flip-Flops,
Registers and Counters, Design of Sequential Circuits
Chap 1, 2, 3, 4, 5, 6, 7, 8, 9, 11, 12, 13, 14, 15, 16
Related Courses (H/W):
Digital Electronics, Computer Architectures, Operating System
Digital Logic Experiments, Digital System Design
•
3
Digital Logic
• Evaluation: 수업계획서의 일정을 원칙으로 실시, 조정
가능
Exams (3 hrs.) : 300 (mid), 400(final)
Homework, etc: 300
Total: 1000
• Communications: One minute quiz, 수업 전/후 면담
• Note:
Lecture-schedules may be adaptively changed.
4
One Minute Quiz
• Date: 2012.
• Department:
Name:
Student ID #:
• Important topic(s) learned today:
• Topic(s) hard to understand:
• Any comments to the professor:
5
CHAPTER 1
INTRODUCTION
NUMBER SYSTEMS AND CONVERSION
This chapter in the book includes:
Objectives
Study Guide
1.1
Digital Systems and Switching Circuits
1.2
Number Systems and Conversion
1.3
Binary Arithmetic
1.4
Representation of Negative Numbers
1.5
Binary Codes
6
Objectives
Topics introduced in this chapter:
• Difference between Analog and Digital Systems
• Difference between Combinational and Sequential Circuits
• Binary number and digital systems
• Number systems and Conversion
• Add, Subtract, Multiply, Divide Positive Binary Numbers
• 1’s Complement, 2’s Complement for Negative binary number
• BCD code, 6-3-1-1 code, excess-3 code, ASCII code etc
7
1.1 Digital Systems and Switching Circuits
• Digital systems: used in computation, data processing,
control, communication, measurement, etc
- Accurate, Reliable, Integration
• Analog – Continuous
- Natural Phenomena
(Pressure, Temperature, Speed…)
- Difficulty in realizing, processing using electronics
• Digital – Discrete
- Binary Digit  Signal Processing as ‘bit’ unit
- Easy in realizing, processing using electronics
- High performance due to Integrated Circuit Technology
8
Binary Digit?
• Binary:- Two values(0, 1)
- Each digit is called as a “bit”
Good things in Binary Number
- Number representation with only two values (0,1)
- Can be implemented with simple electronics devices
(ex: Voltage High(1), Low(0) ; positive logic <-> negative
Switch On (1) Off(0)…)
9
Switching Circuit
*takes on discrete values
• Combinational Circuit :
outputs depend on only present inputs, not on past inputs
Boolean algebra in Unit 2 & 3 used to describe I/O relations.
10
Sequential Circuit
Sequential Circuit:
- outputs depend on both present inputs and past inputs
- have “memory” function
Combinational
Circuit
Memory
11
Design Levels of Digital Systems
• System Design:
Memory unit, ALU, I/O devices, etc
(Computer System Architectures)
• Logic Design:
Logic gates, F/F, etc for a specific function
(Digital Logic)
• Circuit Design:
Resistors, diodes, transistors to form a gate, F/F, or
other logic building block
(Digital Electronics)
Refer to Appendix A
12
1.2 Number Systems and Conversion
Any number system to Decimal
Decimal:
953.7810  9 10 2  5 101  3 100  7 10 1  8 10 2
Binary:
1011.112  1 23  0  22  1 21  1 20  1 21  1 22
*基數
Radix(Base),R
to Decimal:
1 1
3
 8  0  2  1    11  11.7510
2 4
4
N  (a4 a3a2 a1a0 .a1a2 a3 ) R
 a4  R 4  a3  R 3  a2  R 2  a1  R1  a0  R 0
 a1  R 1  a2  R 2  a3  R 3
Example:
147.38  1 82  4  81  7  80  3  81  64  32  7 
 103.37510
3
8
13
1.2 Number Systems and Conversion
Hexa-Decimal:
A2 F16  10 16 2  2 161  15 160  2560  32  15  260710
0, 1, 2, 3, 4, 5, 6, 7, 8, 9, A, B, C, D, E, F
14
1.2 Number Systems and Conversion
Decimal Number N to Base-R: integer part
N  (an an 1    a2 a1a0 ) R  an R n  an 1 R n 1      a2 R 2  a1 R1  a0
N
 an R n 1  an 1 R n  2      a2 R1  a1  Q1 , remainder a0
R
Q1
 a n R n  2  a n 1 R n 3      a 3 R1  a 2  Q2 , remainder a1
R
Q2
 an R n 3  an 1 R n 4      a3  Q3 , remainder a2
R
Continue until to get an. Thus divide N by R until we have Q = 0, then
we will get (anan-1
… a2a1a0)R.
15
1.2 Number Systems and Conversion
Example: Decimal to Binary Conversion: From 5310 to base 2?
2
53
2
26
rem. = 1 = a0
2
13
rem. = 0 = a1
2
6
rem. = 1 = a2
2
3
rem. = 0 = a3
2
1
rem. = 1 = a4
0
rem. = 1 = a5
5310  1101012
16
1.2 Number Systems and Conversion
Conversion of a decimal fraction F to Base-R
F  (0.a1a2 a3  a m ) R  a1 R 1  a2 R 2  a3 R 3    a m R  m
FR  a1  a 2 R 1  a3 R 2      a m R  m 1  a1  F1
F1 R  a 2  a3 R 1      a m R  m  2  a 2  F2
F2 R  a3      a m R  m3  a3  F3
Thus multiplying F by R continuously, we will get (.a-1a-2…a-m)R.
Example: From .625 to base 2
F  .625
 2
1.250
( a1  1)
F1  .250
F2  .500
 2
0.500
 2
1.000
( a3  1)
(a 2  0)
.62510  .1012
17
1.2 Number Systems and Conversion
Example: Convert 0.7 to binary
.7
2
(1).4
2
(0).8
2
(1).6
2
(1).2
2
(0).4
2
(0).8
Process starts repeating here because .4 was previously
obtained
0.710  0.1 0110 0110 0110 2
18
1.2 Number Systems and Conversion
Example: Convert
(231.3)4 to base-7
231.34  2  42  3  4  1 
7
45
7
6
rem.3
0
rem.6
.75
7
(5).25
7
(1).75
7
(5).25
7
(1).75
3
 45.7510
4
45.7510  63.5151  7
19
1.2 Number Systems and Conversion
Conversion of Binary to Octal, Hexa-decimal
1001101.0101112  0100
{ 1100
{  4D.5C16
{ . 0101
{ 1101
4
D
•
(101 011 010 111 )2
= ( 5 3 2 7 )8, octal
•
(1010 1111 0010 0101)2
= ( A F 2 9 )16, Hexadecimal
5
C
20
1.3 Binary Arithmetic
Addition
000
0 1  1
1 0 1
1 1  0
Example:
and carry 1 to the next higher column
1 1 1 1
1310  1 1 0 1
1110 
carries
1 0 1 1
1 1 0 0 0  2410
21
1.3 Binary Arithmetic
Subtraction
00  0
0 1  1
and borrow 1 from the next higher column
1 0 1
1 1  0
Example:
1
11101
 10011
1010
(indicates
a borrow
From the
3rd column)
1111
borrows
111
10000

11
1101
borrows
111001

1011
101110
22
*1.3 Binary Arithmetic
Subtraction Example with Decimal;
column 2
* borrow 1 from column n means subtract
1 from n and add 10 to column n-1
205
 18
187
205  18  [2  10 2  0  101  5  10 0 ]
[
column 1
1 101  8  10 0 ]
note borrow from column 1
 [2  10 2  (0  1)  101  (10  5)  10 0 ]
[
1101 
8  10 0 ]
note borrow from column 2
 [( 2  1)  10 2  (10  0  1)  101  15  10 0 ]
[
 [1 10 2
1)  101  8  10 0 ]
 8  101
 7  10 0 ]  187
23
1.3 Binary Arithmetic
Multiplication
Multiply: (13 x11)10
0 0  0
0 1  0
1 0  0
1 1  1
1111
1101
1111
0000
(01111)
1111
(1001011)
1111
11000011
1101
1011
1101
1101
0000
1101
10001111  14310
multiplicand
multiplier
*For easy hardware
implementation,
first partial product
shifting and
second partial product
partial products
sum of first two partial products
are needed
third partial product
sum after adding third partial product
fourth partial product
final product (sum after adding fourth partial product) 24
1.3 Binary Arithmetic
Division
1101
1011 10010001
1011
1110
1011
1101
1011
10
The quotient is 1101 with a remainder
of 10.
25
1.4
Representation of Negative Numbers: Integer
(a) Unsigned number: for positive only
(b) Signed number: for positive and negative both
i) Sign and Magnitude
ii) 2’s Complement
iii) 1’s Complement
* only negative numbers are represented
differently
26
1.4
Representation of Negative Numbers: Integer
bn – 1
b1
b0
Magnitude
MSB
(a) Unsigned number: for positive only
bn – 1 bn – 2
b0
Magnitude
Sign
0 denotes +
1 denotes –
b1
MSB
(b) Signed number: for positive and negative both
i) Sign and Magnitude
27
1.4
Representation of Negative Numbers: Integer
i) Sign and Magnitude
• for 4 bits,
+0: 0000, +1: 0001, .. , +7: 0111
-0: 1000, -1: 1001, .. , -7: 1111
• for n bits,
2n-1 positive numbers,
2n-1 negative numbers
2 zeros: 000..0 and 100..0
* Not good for arithmetic operations
28
[1’s and 2’s complement are used for subtraction by adder]
ii) 2’s Complement Representation of N for Negative Numbers
N *  2n  N
n: number of bits
Ex:
N=1100,
n=6
Thus N* = 26 – 1100 =
1000000
-) 001100
-------------110100
as they are
last non zero, subtract from r (=2)
subtract from r -1 (=1)
29
Signed Binary Integers (word size n=4)
Negative integers
+N
Positive
integers
(all systems)
+0
+1
+2
+3
+4
+5
+6
+7
0000
0001
0010
0011
0100
0101
0110
0111
-N
Sign and
magnitude
-0
-1
-2
-3
-4
-5
-6
-7
-8
1000
1001
1010
1011
1100
1101
1110
1111
-
2’s complement
N*
- , 1)*
1111
1110
1101
1100
1011
1010
1001
1000
1’s complement
N
1111
1110
1101
1100
1011
1010
1001
1000
-
1)* There is no – 0, but + 0 is 000..0. So only 1 zero in 2’s complement.
30
1.4 Representation of Negative Numbers
iii) 1’s complement representation for Negative Numbers
N  (2 n 1)  N
Example:
2n  1  111111
N  001100
Thus 1’s complement of N is
obtained by complementing
each bit of N.
N  110011
N *  2 n  N  (2 n  1  N )  1  N  1
== 2’s complement: 1’s complement + ‘1’
So 2’s complement
of N is obtained by adding
1 to the 1’s complement
of N.
31
1.4 Representation of Negative Numbers
2n  N * = 2n - (2n  N )  N
(2n  1)  N  (2n  1)  ((2n  1)  N )  N
Ex:
Complement of N’s complement is N.
In other words, magnitude of a negative
number represented by a complement
can be obtained by complementing it.
0 0101 : +5, its 2’ complement is 100000 – 00101 = 11011
1 1011 : -5, its 2’ complement is 100000 – 11011 = 00101
Thus, Complement is not just to represent negative of positive numbers,
but to represent negative of negative numbers.
32
2’s complement of N
• Subtract from 2n
• Add 1 to 1’s complement of N
• Starting from the right-most bit,
change the first 1 to 0 and complement all
the left-side remaining.
for N=010011000,
1’s com.->101100111
2’s com.->101101000
33
1.4 Representation of Negative Number
Addition of 2’s complement Numbers
* Addition is carried out just as if all the numbers were positive, and any carry from
the sign position is ignored. Subtraction is done by taking the complement of the
Minuend. Overflow occurs when correct sum requires one more bit.
Case 1
Case 2
Case 3
3
0011
4
7
0100
0111
5
6
0101
5
6
0110
1011
0101
1010
1111
(correct answer)
wrong answer because of overflow (+11 requires
5 bits including sign)
(correct answer)
34
1.4 Representation of Negative Numbers
Addition of 2’s complement Numbers
Case 4
Case 5
5
6
1011
0110
(1)0001
3
1101
4
7
1100
(1)1001
Case 6
5
6
Discard the carry
Care about overflow
correct answer when the carry from the sign bit
is ignored (this is not an overflow)
correct answer when the last carry is ignored
(this is not an overflow)
1011
1010
(1)0101
wrong answer because of overflow
(-11 requires 5 bits including sign)
35
Detection of Overflow in 2’s
^
+5
0101
+6
0110
--------------------+11
1011
^
: Overflow = carry Cn EOR Cn-1
-5
1011
-6
1010
-------------------11 (1) 0 1 0 1
1. Overflow occurs when the sign of sum is different from the sign of the two
positive or negative numbers.
2. Overflow can be also detected by observing the carry bits:
=> Overflow = (Carry at Cn) EOR (Carry at Cn-1)
36
1.4 Representation of Negative Numbers
Addition of 1’s complement Numbers
Instead of discarding the last carry, carry is added to the n-bit sum.
=> end-around carry
Case 3
Case 4
5
6
1
5
6
0101
1001
1110
(correct answer)
1010
0110
(1) 0000
1 (end-around carry)
0001 (correct answer, no overflow)
37
1.4 Representation of Negative Numbers
Addition of 1’s complement Numbers
3
4
Case 5
1100
1011
(1) 0111
1 (end-around carry)
1000 (correct answer, no overflow)
Case 6
1010
5
6
1001
(1) 0011
1
0100
(end-around carry)
(wrong answer because of overflow)
38
Addition of end-carry
2’s com. : B – A => B + A* = B+ (2n – A) = 2n + (B – A)
= 2n – (A - B) = (A – B)*
Thus, when there is a carry 2n, just ignore the carry (2n) and the result becomes
(B – A), correctly.
Otherwise if there is no carry, result is 2’s complement of (A - B) which is
- (A - B) = (B-A)
It occurs when A > B.
1’s com. : B – A => B + A’ = B + (2n – 1 – A) = 2n + (B – A) – 1
= 2n – 1 – (A - B) = (A – B)’
Thus when there is a carry, we want to take (2n – 1) from the result
so that it becomes (B – A). To take the carry means we take 2n.
So, we want to add 1 (end-carry) to the result.
If there is no carry, result is (A – B) represented by
1’s complement form. It occurs when A >= B.
39
1.4 Representation of Negative Numbers
Addition of 1’s complement Numbers
11110100
11101011
(1) 11011111
1
( 11)
 ( 20)
(end-around carry)
11100000  31
Addition of 2’s complement Numbers
11111000
00010011
(1)00001011
( 8)
 19
 11
(end-around carry)
40
1.5 Binary Codes
*To store and process decimal numbers in a computer, various types of coding are
possible.
9 3 7.2 5
    
1001 0011 0111 . 0010 0101
Decimal
Digit
0
1
2
3
4
5
6
7
8
9
8-4-2-1
Code
(BCD)
0000
0001
0010
0011
0100
0101
0110
0111
1000
1001
6-3-1-1
Code
0000
0001
0011
0100
0101
0111
1000
1001
1011
1100
Excees-3
Code
0011
0100
0101
0110
0111
1000
1001
1010
1011
1100
2-out-of-5
Code
00011
00101
00110
01001
01010
01100
10001
10010
10100
11000
Gray
Code
0000
0001
0011
0010
0110
1110
1010
1011
1001
1000
41
Binary Codes for Decimal Digits
• 8-4-2-1 & 6-3-1-1 are weighted.
• Excess-3 is self-complemented.
• 2-out-of-5 is non-weighted and error
checked for only two bits are 1’s.
• Gray code is for minimal change of ‘1’
bits to increase and also used for error
correction.
42
1.5 Binary Codes
6-3-1-1 Code:
N  w3a3  w2 a2  w1a1  w0 a0
N  6 1  3  0 11  11  8
ASCII Code
Graphic Characters: 94 as in Table 1-3.
Control Characters: 34 including ESC, DEL, SP, BS, etc.
Table 1-6 in Ref. Mano
1010011 1110100 1100001 1110010 1110100
S
t
a
r
t
43
Homework
• HW. Unit 1: 4, 7, 8. 13, 15, 25, 27
44