Bài giảng Thiết kế logic số - Chương 4: Thiết kế các mạch số thông dụng (Tiết 3)

Thiết kế logic số

(Digital logic design)

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

Mục đích, nội dung

 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.

2

Restoring division

------------------------------

z

1 0 0 0 0 1 0 1

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

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

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

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

------------------------------

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|

= u

= -d

------------------------------

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

-----------------------------

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)

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

2*(u-d) + d = 2*u -d

2s(3) 0 |0 1 0 1 0 1 restore

-2^4d 0 |1 0 0 1 0 q2 = 0

------------------------------

4

Restoring division VS Non-Restoring division

------------------------------ ------------------------------

z

1 0 0 0 0 1 0 1 z

1 0 0 0 0 1 0 1

2^d

1 1 1 0 2^d

1 1 1 0

s(0) 0 |0 0 1 0 0 0 0 1 0 1 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|

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 s(1) (0)|1 1 0 1 0|0 1 0 1

2s(1) 0 |1 0 0 0 0|1 0 1 restore 2s(1) 0 |1 0 0 0 0|1 0 1

-2^4d 0 |1 0 0 1 0 q4 = 0 +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 -2^4d 1 |1 0 0 1 0 q3 = 1

------------------------------ ------------------------------

s(3) (0)|1 0 1 1 1 0 1

s(3) 0)|1 0 1 1 1 0 1

2s(3) 0 |0 1 0 1 0 1 restore 2s(3) 1 |0 1 1 1 0 1

+2^4d 0 |1 0 0 1 0 q2 = 0 +2^4d 0 |0 1 1 1 0 q2 = 0

------------------------------ ------------------------------

….

5

Non restoring division example

------------------------------ ------------------------------

z

2^d

1 0 0 0 0 1 0 1 s(4) (0)|1 1 1 0 0 1 q1 = 0

1 1 1 0 2s(4) 1 |1 1 0 0 1

s(0) 0 |0 0 1 0 0 0 0 1 0 1 +2^4d 0 |0 1 1 1 0

2s(0) 0 |0 1 0 0 0|0 1 0 1

-2^4d 1 |1 0 0 1 0|

------------------------------

S(5) = (1)|0 0 1 1 1 q0 = 1

------------------------------ s = 2s(5) = 0 1 1 1 = 7

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

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

2s(3) 1 |0 1 1 1 0 1

+2^4d 0 |0 1 1 1 0 q2 = 0

------------------------------

6

Restoring division structure

K+1-bit(quotient)

MUX

Sel

(SHIFT LEFT)

K-bit

0

divisor

remainder

K-bit

(SHIFT LEFT)

2s’ complement

opb

opa

Cout

Σ k-bit

SUB =1

SUM

7

Non-restoring division

qoutient

K+1-bit

(SHIFT LEFT)

divisor

K-bit

0

2s’ complement

remainder

K-bit

(SHIFT LEFT)

MUX

opb

opa

Cout

1-bit

Σ k+1-bit

SUM

8

Signed division principle

-2⁴d

+2³d

+112

21

-2²d

-56

-35

0

-2¹d

+28

-7

+2⁰d

+14

+7

Z =133

133

-224

Remainder -91

Quoitient

p

0

1

0

1

-1

+1

-1

+1

- Trị tuyệt đối của phần dư luôn giảm

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.

- Tổng quát hóa từ sơ đồ chia không phục hồi phần dư, nếu ta mã

hóa q_ikhác đi như sau:

p_i= 1 nếu s(i) và d cùng dấu

p_i= -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

9

Signed division principle

Quy tắc chuyển đổi P về Q:

•Chuyển tất cả các p_igiá trị -1 thành 0. Gọi giá

trị này là r = r_k-1r_k-2…r₀. Suy ra q_i= 2r_i– 1.

•Lấy đảo của r_k-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

divisor

K-bit

0

2s’ complement

K-bit

MUX

opb

K+1-bit

opa

quotient

Σ k+1-bit

Correct quotient

SUM

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