Bài giảng Thiết kế logic số - Chương 4, Phần 3 - Hoàng Văn Phúc

Chương IV: Thiết kế các mạch số thông dụng
TS. Hoàng Văn Phúc
Bộ môn KT Xung, số, Vi xử lý
https://sites.google.com/site/phucvlsi/teaching
1/2014
Thiết kế logic số
(Digital logic design)
 Nội dung: Khối chia số nguyên có dấu và
không dấu. Phương pháp tiết kiệm tài nguyên
thiết kế bằng cấu trúc lặp cứng
 Thời lượng: 3 tiết bài giảng
 Yêu cầu: Sinh viên có sự chuẩn bị sơ bộ trước
nội dụng bài học.
Mục đích, nội dung
2
Restoring division
------------------------------
z 1 0 0 0 0 1 0 1 
2^d 1 1 1 0
s(0) 0 |0 0 1 0 0 0 0 1 0 1 
2s(0) 0 |0 1 0 0 0|0 1 0 1 
-2^4d 1 |1 0 0 1 0| 
------------------------------
s(1) (0)|1 1 0 1 0|0 1 0 1 
2s(1) 0 |1 0 0 0 0|1 0 1 restore
-2^4d 0 |1 0 0 1 0 q4 = 0
------------------------------
s(2) (1)|0 0 0 1 0 1 0 1 
2s(2) 0 |0 0 1 0 1 0 1 
-2^4d 1 |1 0 0 1 0 q3 = 1
------------------------------
s(3) (0)|1 0 1 1 1 0 1
2s(3) 0 |0 1 0 1 0 1 restore 
+2^4d 0 |1 0 0 1 0 q2 = 0
------------------------------
------------------------------
s(4) (0)|1 1 1 0 0 1 q1 = 0
2s(4) 1 |1 0 1 0 1 restore
+2^4d 0 |1 0 0 1 0
------------------------------
S(5) = (1)|0 0 1 1 1 q0 = 1
s = 2s(5) = 0 1 1 1 = 7 
q = 0 1 0 0 1 = 9
d = 1 1 1 0 = 14
-d = 1 0 0 1 0
z = 1 0 0 0 0 1 0 1 = 133
q = 0 1 0 0 1 = 9
S = 0 1 1 1 = 7
3
Non-restoring division principle
------------------------------
z 1 0 0 0 0 1 0 1 
2^d 1 1 1 0
s(0) 0 |0 0 1 0 0 0 0 1 0 1 
2s(0) 0 |0 1 0 0 0|0 1 0 1 
-2^4d 1 |1 0 0 1 0| 
------------------------------
s(1) (0)|1 1 0 1 0|0 1 0 1 
2s(1) 0 |1 0 0 0 0|1 0 1 restore
-2^4d 0 |1 0 0 1 0 q4 = 0
------------------------------
s(2) (1)|0 0 0 1 0 1 0 1 
2s(2) 0 |0 0 1 0 1 0 1 
-2^4d 1 |1 0 0 1 0 q3 = 1
------------------------------
s(3) (0)|1 0 1 1 1 0 1
2s(3) 0 |0 1 0 1 0 1 restore 
-2^4d 0 |1 0 0 1 0 q2 = 0
------------------------------
-----------------------------
= u
= -d
-----------------------------
u –d 
= 2*(u-d) (u-d >0)|2u (u-d <0)
= -d | 
----------------------------
2*(u-d)–d (u-d >0)|2u–d(u-d <0)
2*(u-d) + d = 2*u -d
4
Restoring division VS Non-Restoring division
------------------------------
z 1 0 0 0 0 1 0 1 
2^d 1 1 1 0
s(0) 0 |0 0 1 0 0 0 0 1 0 1 
2s(0) 0 |0 1 0 0 0|0 1 0 1 
-2^4d 1 |1 0 0 1 0| 
------------------------------
s(1) (0)|1 1 0 1 0|0 1 0 1 
2s(1) 0 |1 0 0 0 0|1 0 1 restore
-2^4d 0 |1 0 0 1 0 q4 = 0
------------------------------
s(2) (1)|0 0 0 1 0 1 0 1 
2s(2) 0 |0 0 1 0 1 0 1 
-2^4d 1 |1 0 0 1 0 q3 = 1
------------------------------
s(3) (0)|1 0 1 1 1 0 1
2s(3) 0 |0 1 0 1 0 1 restore 
+2^4d 0 |1 0 0 1 0 q2 = 0
------------------------------
.
------------------------------
z 1 0 0 0 0 1 0 1 
2^d 1 1 1 0
s(0) 0 |0 0 1 0 0 0 0 1 0 1 
2s(0) 0 |0 1 0 0 0|0 1 0 1 
-2^4d 1 |1 0 0 1 0| 
------------------------------
s(1) (0)|1 1 0 1 0|0 1 0 1 
2s(1) 0 |1 0 0 0 0|1 0 1 
+2^4d 0 |0 1 1 1 0 q4 = 0
------------------------------
s(2) (1)|0 0 0 1 0 1 0 1 
2s(2) 0 |0 0 1 0 1 0 1 
-2^4d 1 |1 0 0 1 0 q3 = 1
------------------------------
s(3) 0)|1 0 1 1 1 0 1
2s(3) 1 |0 1 1 1 0 1 
+2^4d 0 |0 1 1 1 0 q2 = 0
------------------------------
.
5
Non restoring division example
------------------------------
z 1 0 0 0 0 1 0 1 
2^d 1 1 1 0
s(0) 0 |0 0 1 0 0 0 0 1 0 1 
2s(0) 0 |0 1 0 0 0|0 1 0 1 
-2^4d 1 |1 0 0 1 0| 
------------------------------
s(1) (0)|1 1 0 1 0|0 1 0 1 
2s(1) 0 |1 0 0 0 0|1 0 1 
+2^4d 0 |0 1 1 1 0 q4 = 0
------------------------------
s(2) (1)|0 0 0 1 0 1 0 1 
2s(2) 0 |0 0 1 0 1 0 1 
-2^4d 1 |1 0 0 1 0 q3 = 1
------------------------------
s(3) 0)|1 0 1 1 1 0 1
2s(3) 1 |0 1 1 1 0 1 
+2^4d 0 |0 1 1 1 0 q2 = 0
------------------------------
------------------------------
s(4) (0)|1 1 1 0 0 1 q1 = 0
2s(4) 1 |1 1 0 0 1
+2^4d 0 |0 1 1 1 0
------------------------------
S(5) = (1)|0 0 1 1 1 q0 = 1
s = 2s(5) = 0 1 1 1 = 7 
q = 0 1 0 0 1 = 9
d = 1 1 1 0 = 14
-2^d = 1 0 0 1 0
z = 1 0 0 0 0 1 0 1 = 133
q = 0 1 0 0 1 = 9
S = 0 1 1 1 = 7
6
Restoring division structure
Σ k-bit
divisor
2s’ complement
K+1-bit(quotient)
SUB =1
Cout
(SHIFT LEFT)
MUX
K-bit K-bit 0
K-bit K-bit
SUM
opaopb
Sel
(SHIFT LEFT)
remainder
7
Non-restoring division
Σ k+1-bit
divisor
2s’ complement
K+1-bit
Cout
(SHIFT LEFT)
K-bit K-bit 0
K-bit K-bit
SUM
opaopb
(SHIFT LEFT)
MUX
1-bit
remainder
qoutient
8
Signed division principle
- Trị tuyệt đối của phần dư luôn giảm
Z =133 -24d +23d -22d -21d +20d
133 -224 +112 -56 +28 +14
Remainder -91 21 -35 -7 +7
Quoitient 0 1 0 0 1
p -1 +1 -1 -1 +1
- Tổng quát hóa từ sơ đồ chia không phục hồi phần dư, nếu ta mã
hóa qi khác đi như sau:
pi = 1 nếu s(i) và d cùng dấu
pi = -1 nếu s(i) và d khác dấu.
Ta vẫn có Z = p(i) * 2^i
Vấn đề: Đưa P về dạng biểu diễn bù 2
Yêu cầu với kết quả
1. Phần dư s cùng dấu với z
2. Trị tuyệt đối của s nhỏ hơn trị tuyệt đối của d.
9
Signed division principle
Quy tắc chuyển đổi P về Q:
•Chuyển tất cả các pi giá trị -1 thành 0. Gọi giá
trị này là r = rk-1rk-2r0. Suy ra qi = 2ri – 1.
•Lấy đảo của rk-1, thêm 1 vào cuối r, giá trị thu
được dưới dạng bù 2 chính là thương số
CHỨNG MINH TOÁN HỌC
10
Signed division
Σ k+1-bit
divisor
2s’ complement
K+1-bit
K-bit K-bit 0
K-bit K-bit
SUM
opaopb
quotient
MUX
Correct quotient
11
Trắc nghiệm
Câu 1: Bản chất của phép chia số nguyên
thực hiện bằng thiết kế logic số là
A. Phép nhân với số nghịch đảo
B. Phép cộng
C.Phép trừ
D.Phép trừ và dịch
12
Trắc nghiệm
Câu 2: Ý nghĩa của việc khôi phục phần dư là:
A. Giá trị dư hiện tại không bị trừ đi
B. Giá trị dư hiện tại không bị trừ đi khi kết quả
âm
C. Giá trị dư hiện tại được khôi phục và bổ xung
thêm 1 bit của số bị chia 
D. Giá trị dư được khôi phục hoàn toàn
13
Trắc nghiệm
Câu 3: Thuật toán không phục hồi phần dư có
ưu điểm:
A. Số dư hiện tại luôn được dịch mà không quan
tâm tới giá trị âm hay dương
B. Số dư hiện tại luôn dương
C. Có tốc độ tốt hơn so với thuật toán khôi phục
phần dư
D. Có thể làm việc với số dạng có dấu.
14
Trắc nghiệm
Câu 4: Sơ đồ khối chia có dấu được xây dựng
trên cơ sở
A. Khối trừ và khối dịch
B. Tính chất của số bù 2
C. Khối chia phục hồi phần dư
D. Khối chia không phục hồi phần dư.
15