Bài giảng Nhập môn Mạch số - Chương 5, Phần 1: Mạch tổ hợp-Mạch tính toán số học

Chương 5 – phần 1 
NHẬP MÔN MẠCH SỐ 
Mạch tổ hợp:Mạch tính toán số học 
Tổng quan 
Chương này sẽ học về: 
Một số mạch logic tổ hợp thông dụng 
Thiết kế các mạch logic tổ hợp phức tạp sử dụng các mạch logic tổ hợp thông dụng 
Phân biệt mạch tổ hợp và tuần tự 
Mạch tổ hợp 
: : 
: : 
inputs 
outputs 
Mạch tổ hợp 
: : 
inputs 
outputs 
: : 
Memory 
MẠCH TỔ HỢP 
- Ngõ ra sẽ thay đổi lập tức khi ngõ vào thay đổi 
MẠCH TUẦN TỰ 
- Ngõ ra sẽ thay đổi phụ thuộc vào ngõ vào và trạng thái trước đó. 
- Mạch có tính chất nhớ 
Nội dung 
Mạch cộng (Carry Ripple (CR) Adder) 
Mạch cộng nhìn trước số nhớ - (Carry Look-Ahead (CLA) Adder) 
Mạch cộng/ mạch trừ 
Đơn vị tính toán luận lý (Arithmetic Logic Unit) 
Mạch giải mã (Decoder)/ Mạch mã hoá ( Encoder) 
Mạch dồn kênh (Multiplexer)/ Mạch chia kênh ( Demultiplexer) 
Mạch tạo Parity/ Mạch kiểm tra Parity 
Mạch so sánh (Comparator) 
Nội dung 
Mạch cộng (Carry Ripple (CR) Adder) 
Mạch cộng nhìn trước số nhớ - (Carry Look-Ahead (CLA) Adder) 
Mạch cộng/ mạch trừ 
Đơn vị tính toán luận lý (Arithmetic Logic Unit) 
Mạch giải mã (Decoder)/ Mạch mã hoá ( Encoder) 
Mạch dồn kênh (Multiplexer)/ Mạch chia kênh ( Demultiplexer) 
Mạch tạo Parity/ Mạch kiểm tra Parity 
Mạch so sánh (Comparator) 
1. Mạch cộng Carry Ripple (CR) 
Cộng 2 số 1 bit có 4 trường hợp 
Mạch cộng 1 bit có tổng và số nhớ như thế này được gọi là mạch cộng bán phần ( HA ) 
Mạch cộng bán phần (Half Adder) 
Sơ đồ mạch 
x 
y 
Tổng 
Số nhớ 
Mạch cộng nhị phân song song 
Cộng những số có 2 hoặc nhiều bit 
Cộng từng cặp bit bình thường 
Nhưng ở vị trí cặp bit i, có thể có carry-in từ bit i-1 
(Sẽ cộng vào vị trí kế tiếp) 
Thiết kế một bộ cộng toàn phần (Full Adder) 
Bộ cộng toàn phần ( FA ) 
 3 ngõ vào (2 ngõ vào cho 2 số 1-bit cần tính tổng, và 1 ngõ vào cho số nhớ đầu vào ( carry-in )) 
 2 ngõ ra (1 ngõ ra cho tổng và 1 cho số nhớ đầu ra ( carry-out )) 
Thiết kế một bộ cộng toàn phần (Full Adder) 
Bảng sự thật 
Ký hiệu 
Thiết kế một bộ cộng toàn phần (Full Adder) 
Bảng sự thật 
Thiết kế một bộ cộng toàn phần (Full Adder) 
Sơ đồ mạch 
Ký hiệu 
Ký hiệu khác 
Thiết kế một bộ cộng toàn phần (Full Adder) 
Sử dụng lại HA 
Sơ đồ mạch FA sử dụng lại HA 
Sơ đồ mạch HA 
x 
y 
Sơ đồ mạch 
Mạch cộng Carry Ripple (CR) 
Sơ đồ biểu diễn mạch cộng 4 bit song song sử dụng full adder 
Mạch cộng Carry Ripple 
Mạch FA bắt đầu với việc cộng các cặp bit từ LSB đến MSB 
Nếu carry xuất hiện ở vị trí bit i, nó được cộng thêm vào phép cộng ở vị trí bit thứ i+1 
Việc kết hợp như vậy thường được gọi là mạch cộng Carry-Ripple 
vì carry được “ripple” từ FA này sang các FA kế tiếp 
Tốc độ phép cộng bị giới hạn bởi quá trình truyền số nhớ 
Mạch cộng Carry Ripple 
Mỗi FA có một khoảng trễ (delay), giả sử là Δt 
Độ trễ phụ thuộc vào số lượng bit 
Carry-out ở FA đầu tiên C 1 có được sau Δt 
Carry-out ở FA đầu tiên C 2 có được sau 2 Δt 
=> C n được tính toán sau n Δt 
Mô hình carry look ahead (CLA) thường được sử dụng để cải thiện tốc độ 
2. Mạch cộng nhìn trước số nhớ Carry Look-Ahead (CLA) Adder 
Hiệu năng 
Tốc độ của mạch bị giới hạn bởi độ trễ lớn nhất dọc theo đường nối trong mạch 
Độ trễ lớn nhất được gọi là critical-path-delay 
Đường nối gây ra độ trễ đó gọi là critical path 
Carry Look-Ahead Adder (CLA) 
Cải thiện tốc độ mạch cộng bằng cách 
Tại mỗi tầng (stage), ta sẽ xác định nhanh giá trị carry-in ở tầng cộng trước đó sẽ có giá trị 0 hay 1 
 giảm critical-path- delay 
Hàm xác định carry-out ở lần cộng thứ i 
	c i+1 = x i y i + x i c i + y i c i = x i y i + (x i + y i )c i 
Đặt g i = x i y i và p i = x i + y i => c i+1 = g i + p i c i 
g i = 1 khi cả x i và y i đều bằng 1, không quan tâm c i 
g được gọi là hàm generate , vì carry-out luôn được generate ra khi g=1 
p i = 1 khi x i = 1 hoặc y i = 1; carry-out = c i 
p được gọi là hàm propagate , vì carry-in = 1 được propagate (truyền) ở tầng cộng thứ i 
Carry Look-Ahead Adder (CLA ) 
Xác định carry-out của mạch cộng n bit 
	 c n	 = g n-1 + p n-1 c n-1 
Mà 	c n-1	 = g n-2 + p n-2 c n- 2 
	c n = g n-1 + p n-1 ( g n-2 + p n-2 c n-2 ) 
Tiếp tục khai triển đến lần cộng đầu tiên 
c n = g n-1 + p n-1 g n-2 +p n-1 p n-2 g n-3 ++ p n-1 p n-2 .p 1 g 0 + p n-1 p n-2 .p 1 p 0 c 0 
Carry Look-Ahead Adder (CLA) 
c n = g n-1 + p n-1 g n-2 + p n-1 p n-2 c n-2 
Carry Look-Ahead Adder (CLA) 
Số nh ớ đầu vào c 0 đ ượ c truyền qua tất cả các lần cộng 
Số nh ớ sinh ra ở lần cộng thứ 1 và đ ượ c truyền qua các lần cộng còn lại 
Số nh ớ sinh ra ở lần cộng thứ n-3 và đ ượ c truyền qua các lần cộng còn lại 
Số nh ớ sinh ra ở lần cộng thứ n-2 và đ ượ c truyền qua các lần cộng còn lại 
Số nh ớ sinh ra ở lần cộng cuối cùng 
Ví dụ: Trường hợp cộng 4 bit 
C 1 = G 0 + P 0 .C 0   
C 2 = G 1 + P 1 .G 0 + P 1 .P 0 .C 0  C 3 = G 2 + P 2 .G 1 + P 2 .P 1 .G 0 + P 2 .P 1 .P 0 .C 0   C 4 = G 3 + P 3 .G 2 + P 3 .P 2 .G 1 + P 3 P 2 .P 1 .G 0 + P 3 P 2 .P 1 .P 0 .C 0 
Carry Look-Ahead Adder (CLA) 
Mạch cộng Carry Ripple - critical path 
Tổng quát, đ ộ trễ 2n+1 cổng đối với mạch cộng Carry Ripple n-bit 
Độ trễ 3 cổng đối với C 1 
Độ trễ 5 cổng đối với C 2 
Mạch cộng CLA - critical path 
C 1 = G 0 + P 0 .C 0   
C 2 = G 1 + P 1 .G 0 + P 1 .P 0 .C 0 
Độ trễ 3 cổng đối với C 1 
Độ trễ 3 cổng đối với C 2 
Độ trễ 3 cổng đối với C n 
Độ trễ tổng cộng cho mạch cộng CLA n-bit là độ trễ 4 cổng 
gi, pi: độ trễ 1 cổng 
Ci: độ trễ 2 cổng 
Độ trễ 1 cộng còn lại là do tính tổng s 
Mạch cộng CLA 
Cấu trúc của một tầng của mạch cộng CLA 
Giới hạn của mạch cộng CLA 
Biểu thức tính carry trong mạch cộng CLA 
 c n = g n-1 + p n-1 g n-2 +p n-1 p n-2 g n-3 ++ p n-1 p n-2 .p 1 g 0 + p n-1 p n-2 .p 1 p 0 c 0 
CLA là giải pháp tốc độ cao (2 level AND-OR ) 
Vấn đề Fan-in có thể hạn chế tốc độ của mạch cộng CLA 
Độ phức tạp tăng lên nhanh chóng khi n lớn 
3 Adder/ Subtractor 
Mạch cộng/ trừ 
X, Y là 2 số không dấu n-bit 
Phép trừ: D = X - Y 
 = X + (-Y)  = X+ (Bù 2 của Y) = X+ (Bù 1 của Y) + 1 = X+ Y’+ 1 
Phép cộng: S = X + Y 
Mạch trừ 
Mạch cộng Carry Ripple có thể được dùng để xây dựng mạch trừ Carry Ripple bằng cách đảo Y và đặt số nhớ đầu tiên là 1 
Tràn (Arithmetic Overflow) 
Overflow là khi kết quả của phép toán vượt quá số bit biểu diễn phần giá trị 
n bit biểu diễn được số từ -2 n-1 đến +2 n-1 -1 
Overflow luôn luôn cho ra 1 kết quả sai 
=> Mạch để xác định có overflow hay không 
Ví dụ về arithmetic overflow 
Với số 4 bit, 3 bit giá trị và 1 bit dấu 
Overflow không xuất hiện khi cộng 2 số trái dấu 
O 
O 
Arithmetic o verflow 
Overflow có thể phát hiện được (từ ví dụ ở slide trước) 
Mạch cộng/ trừ có thể bổ sung mạch kiểm tra overflow với 1 cổng XOR 
Với n bit 
	 Overflow = c n-1 c n 
Ví dụ 
Thiết kế một mạch cộng/ trừ với 2 ngõ điều khiển ADD và SUB 
ADD = 1: mạch cộng 2 số trong 2 thanh ghi A và B 
SUB = 1: mạch thực hiện phép trừ số B-A 
Chú ý: 
	 Trong một lúc chỉ một trong hai ngõ ADD, SUB bằng 1 
Ví dụ 
4 Arithmetic Logic Unit (ALU ) 
ALU 
ALUs có thể thực thi nhiều toán tử và hàm logic khác nhau 
Các toán tử và hàm được xác định bởi một mã ngõ vào 
Inputs 
S2 
S1 
S0 
Function 
0 
0 
0 
F = 0000 
0 
0 
1 
F = B – A – 1 + Cin 
0 
1 
0 
F = A – B – 1 + Cin 
0 
1 
1 
F = A + B + Cin 
1 
0 
0 
F = A B 
1 
0 
1 
F = A + B 
1 
1 
0 
F = A * B 
1 
1 
1 
F = 1111 
Any question ?