điện tử số phần 14

Thiết kế số
Thực hiện tối ưu hóa hàm logic:
Phân tích và tổng hợp mạch đa mức
Người trình bày:
TS. Hoàng Mạnh Thắng
TexPoint fonts used in EMF: AAAAA
Tổng hợp mạch đa mức
Vấn đề tối ưu hóa là đi tìm dạng tối thiểu dưới dạng POS hoặc SOP cho hàm logic
SOP hay POS thuộc loại hai mức:
Dạng SOP có mức thứ nhất chỉ gồm các cổng AND với các đầu ra nối đến các đầu vào của mức thứ 2 là cổng OR
Tương tự, POS có mức thứ nhất là các cổng OR và mức thứ 2 là cổng AND
Thực hiện tổng hợp mạch 2 lớp thường hiệu quả cho các hàm có vài đầu vào
Tổng hợp mạch đa mức (cont.)
Khi số đầu vào tăng thì vấn đề xảy ra ở chỗ đầu vào (fan-in problems)
Fan-in: tổng số đầu vào đi đến một cổng hay một phần tử của mạch
Xét cost cho biểu thức SOP dưới đây
f(x_1,..x_7)=x_1x_3x_6’+x_1x_4x_5x_6’+x_2x_3x_7+x_2x_4x_5x_7
Tổng hợp mạch đa mức (cont.)
Xét việc thực hiện hàm f hai lớp với các PLD như CPLD hay FPGA .
Với CPLD thì không sao bởi có đủ đầu vào, đủ cổng AND và cả cổng OR
Tổng hợp mạch đa mức (cont.)
Với FPGA có các LUTs 2 đầu vào thì hàm này ko thể thực hiện được trực tiếp vì:
Dạng SOP có 3 và 4 thành phần (literals)  yêu cầu các cổng AND có 3 và 4 đầu vào
Có 4 thành phần tích  cần các cổng OR có 3 và 4 đầu vào
Fan-in để thực hiện mạch này là lớn hơn so với các LUTs 2 đầu vào của FPGA
Tổng hợp mạch đa mức (cont.)
Để giải quyết, hàm phải được biểu diễn ở dạng có số mức logic lớn hơn 2. Nó được gọi là biểu thứ logic đa mức
Có 2 kỹ thuật tổng hợp các hàm logic đa mức là: factoring và functional decomposition (đặt thừa số và phân tách hàm)
Factoring (đặt thừa số)
Sử dụng tính chất phân bố để viết lại biểu thức dưới dạng có ít thành phần biến (literals) trong một nhóm hơn.
Ví dụ

Ở dạng này, hàm có ko quá 2 thành phần biến cho mỗi nhóm và có thể thực hiện với LUTs hai đầu vào
Factoring (đặt thừa số)
Các vấn đề của Fan-in
Các hạn chế Fan-in ko những chỉ trong PLDs, mà còn trong các cổng logic đơn
Nhìn chung, khi số đầu vào đến 1 cổng logic tăng dẫn đến trễ lan truyền tăng.
Trễ lan truyền là tổng trễ cần thiết cho sự thay đổi ở đầu vào tạo ra thay đổi ở đầu ra
Như vậy, mong muốn là hạn chế số đầu vào tới một phần tử. Thông thường tối đa là 5
Các vấn đề của Fan-in (cont.)
Cho một hàm
Thực hiện trực tiếp yêu cầu 2 cổng AND 6 đầu vào và 1 cổng OR 2 đầu vào
Đặt thừa số cho hàm này có

Hàm này giải quyết được vấn đề Fan-in
Bài tập
Thựu hiện factoring cho biểu thứ sau với lời giải là chỉ dùng các cổng AND và OR hai đầu vào
Ảnh hưởng lên mức phức tạp của kết nối
Không gian của IC được chiếm bởi mạch và các dây dẫn tạo nên kết nối cho các mạch
Mối literal tương ứng với 1 dây nối trong mạch, nó mang tín hiệu logic
Factoring làm giảm tổng số literal và cũng giúp giảm mức phức tạp của kết nối
Trong khi tổng hợp mạch logic, CAD tools xem xét các tham số như: chi phí của mạch, fan-in, tốc độ của mạch và mức phức tạp của dây
Functional decomposition (phân tách hàm)
Mức phức tạp của mạch logic (cổng logic và kết nối) thường có thể được giảm bằng cách phân tách (decomposing) biểu thứ 2 mức thành nhiều mạch nhỏ hơn.
Mạch nhỏ này có thể được dùng một số nơi trong mạch cuối cùng
Một biểu thức 2 mức có thể được thay thế bởi 2 hay nhiều biểu thức mới.
Các biểu thức mới được tổ hợp để hình thành mạch nhiều mức
Ví dụ về phân tách hàm
Xét biểu thức:
Hàm này yêu cầu 1 cổng AND 3 đầu vào, 2 cổng AND 2 đầu vào và 1 cổng OR 3 đầu vào
COST = 4 cổng + 10 đầu vào = 13. Và COST = 19 nếu cổng NOT được kèm thêm vào
Viết lại hàm f:
Gọi 
Ví dụ về phân tách hàm (cont.)
Hàm trở thành
Mạch được xây dựng như sau với COST=16 bao gồm cả cổng NOT
Các vấn đề thực tế
Phân tách hàm là công cụ mạnh để giảm mức độ phức tạp cho mạch
Nó có thể được dùng để thực hiện hàm logic với các ràng buộc. Ví dụ: thực hiện với PLD cụ thể.
CAD tools dùng nhiều khái niệm này.