ĐẠI HỌC QUỐC GIA THÀNH PHỐ HỒ CHÍ MINH
TRƯỜNG ĐẠI HỌC BÁCH KHOA
XX

NGUYỄN VĂN TÂN

TỐI ƯU HÓA VI MẠCH HAI LỚP
VỚI CÁC PHƯƠNG PHÁP DÀNH CHO
BÀI TOÁN SET COVERING
Chuyên ngành: Khoa học Máy tính

LUẬN VĂN THẠC SĨ

TP. HỒ CHÍ MINH, THÁNG 11 NĂM 2007


Tối ưu hóa vi mạch hai lớp với các phương pháp dành cho bài toán set covering

ĐẠI HỌC QUỐC GIA TP. HCM
TRƯỜNG ĐẠI HỌC BÁCH KHOA
XW

CỘNG HOÀ XÃ HỘI CHỦ NGHIÃ VIỆT NAM
Độc Lập - Tự Do - Hạnh Phúc
X›W

Tp. Hồ Chí Minh, ngày 05 tháng 11 năm 2007.

NHIỆM VỤ LUẬN VĂN THẠC SĨ
Họ và tên học viên : Nguyễn Văn Tân..............................Giới tính : Nam ;/ Nữ …
Ngày, tháng, năm sinh : 18 - 05 - 1971 ..............................Nơi sinh : Khánh Hịa ...............

Chun ngành : Khoa học Máy tính......................................................................................
Khố : 2005 - 2007 ..............................................................................................................
1- TÊN ĐỀ TÀI : TỐI ƯU HÓA VI MẠCH HAI LỚP VỚI CÁC PHƯƠNG PHÁP

DÀNH CHO BÀI TOÁN SET COVERING.

...........................................................................................................................................
2- NHIỆM VỤ LUẬN VĂN : Phân tích bài tốn tối ưu vi mạch hai lớp, xây đựng
mơ hình tốn theo dạng SET COVERING, xây dựng giải thuật giải mơ hình của
bài tốn. Dựa trên cơ sở lý thuyết đó, hiện thực chương trình tối ưu vi mạch hai
lớp. Lý thuyết được kiểm chứng bằng chương trình và chương trình được kiểm
thử bởi các dữ liệu đầu vào đã phổ biến trên thế giới. Kết quả kiểm thử cũng
được so sánh với các chương trình hiện thời trên thế giới. ........................................
...........................................................................................................................................
...........................................................................................................................................
3- NGÀY GIAO NHIỆM VỤ : 05/01/2007 ........................................................................
4- NGÀY HOÀN THÀNH NHIỆM VỤ : 05/11/2007 .......................................................
5- HỌ VÀ TÊN CÁN BỘ HƯỚNG DẪN : TS. Trần Văn Hoài ......................................
Nội dung và đề cương Luận văn thạc sĩ đã được Hội Đồng Chuyên Ngành thông qua.

CÁN BỘ HƯỚNG DẪN
(Họ tên và chữ ký)

CHỦ NHIỆM BỘ MÔN
QUẢN LÝ CHUYÊN NGÀNH
(Họ tên và chữ ký)

TS. Trần Văn Hoài

TS. Đinh Đức Anh Vũ


Nguyễn Văn Tân - 00705153

Trang 2


Tối ưu hóa vi mạch hai lớp với các phương pháp dành cho bài tốn set covering

CƠNG TRÌNH ĐƯỢC HỒN THÀNH TẠI
TRƯỜNG ĐẠI HỌC BÁCH KHOA
ĐẠI HỌC QUỐC GIA TP HỒ CHÍ MINH

Cán bộ hướng dẫn khoa học : TS. TRẦN VĂN HOÀI..............................................
.....................................................................................................................................
.....................................................................................................................................
.....................................................................................................................................
.....................................................................................................................................
Cán bộ chấm nhận xét 1 : PGS, TS NGUYỄN HỮU PHƯƠNG .............................
.................................................................................................................................
.................................................................................................................................
.................................................................................................................................
.................................................................................................................................
Cán bộ chấm nhận xét 2 : GVC, TS. ĐINH ĐỨC ANH VŨ.....................................
.....................................................................................................................................
.....................................................................................................................................
.....................................................................................................................................
.....................................................................................................................................
Luận văn thạc sĩ được bảo vệ tại: Trường Đại học Bách Khoa Tp Hồ Chí Minh ........
...........................................................................................................................................
...........................................................................................................................................

...........................................................................................................................................
...........................................................................................................................................
...........................................................................................................................................

HỘI ĐỒNG CHẤM BẢO VỆ LUẬN VĂN THẠC SĨ
TRƯỜNG ĐẠI HỌC BÁCH KHOA, ngày 05 tháng 11 năm 2007.

Nguyễn Văn Tân - 00705153

Trang 3


Tối ưu hóa vi mạch hai lớp với các phương pháp dành cho bài tốn set covering

LỜI CAM ĐOAN
Tơi cam đoan rằng, ngoại trừ các kết quả tham khảo từ các cơng trình khác như đã ghi rõ
trong luận văn, các cơng việc trình bày trong luận văn này là do chính tơi thực hiện và
chưa có phần nội dung nào của luận văn này được nộp để lấy một bằng cấp ở trường này
hoặc trường khác.

Thành phố Hồ Chí Minh, ngày 05 tháng 11 năm 2007.
Tác giả

Nguyễn Văn Tân

Nguyễn Văn Tân - 00705153

Trang 4



Tối ưu hóa vi mạch hai lớp với các phương pháp dành cho bài tốn set covering

LỜI CÁM ƠN
Tơi rất cám ơn nhà trường, thầy cô, cán bộ quản lý đã xây dựng nền tảng cho trường ngày
một vững chắc hơn. Xin chân thành cám ơn đến quý thầy cô trong hai năm qua đã truyền
tải một lượng tri thức rất thực tế và hữu dụng cho các học viên Cao học khóa 2005-2007.
Các mơn học này là cơ sở nền tảng để học viên nghiên cứu tiếp theo.

Chân thành cám ơn TS. Trần Văn Hồi đã dày cơng nghiên cứu và hướng dẫn tận tình
giúp tơi hồn thành tốt luận văn.

Cám ơn sự góp ý và động viên của các bạn học viên Cao học khóa 2004-2006 và khóa
2005-2007. Đã giúp tơi một phần làm luận văn được hồn hảo hơn.

Một điểm tựa không thể thiếu trong nghiên cứu khoa học đó là gia đình. Cám ơn gia đình
tơi đã góp sức và chia sẽ bớt cơng việc gia đình để tơi có đủ thời gian theo học và làm
luận văn.

Tác giả: Nguyễn Văn Tân.

Nguyễn Văn Tân - 00705153

Trang 5


Tối ưu hóa vi mạch hai lớp với các phương pháp dành cho bài tốn set covering

MỤC LỤC
TĨM TẮT ...........................................................................................................................8
ABSTRACT ......................................................................................................................10

CHƯƠNG 1: CHƯƠNG MỞ ĐẦU.................................................................................12
1.1 QUY TRÌNH THIẾT KẾ VÀ SẢN XUẤT VI MẠCH (CHIP) ..................................... 12
1.2 VẤN ĐỀ TỐI ƯU VI MẠCH HAI LỚP .......................................................................... 14
1.3 GIẢI QUYẾT VẤN ĐỀ ..................................................................................................... 15

CHƯƠNG 2: KHÁI NIỆM CƠ BẢN .............................................................................18
2.1 HÀM LUẬN LÝ (BOOLEAN HAY LOGIC FUNCTION)........................................... 18
2.2 CÁC PHÉP TOÁN TRÊN HÀM LUẬN LÝ................................................................... 19
2.2.1 PHẦN BÙ (COMPLEMENT) ..............................................................................................19
2.2.2 TÍCH (INTERSECTION-PRODUCT) .................................................................................19
2.2.3 HIỆU (DIFFERENCE-SUBTRACT) ...................................................................................19
2.2.4 TỔNG (UNION-SUM) .........................................................................................................19
2.2.5 HẰNG ĐÚNG (TAUTOLOGY) ..........................................................................................20

2.3 BIỂU DIỄN ĐẠI SỐ CỦA HÀM LUẬN LÝ................................................................... 20
2.4 CUBE, COVER VÀ MINTERM...................................................................................... 21
2.4.1 CUBE ..................................................................................................................................21
2.4.2 COVER .................................................................................................................................21
2.4.3 MINTERM............................................................................................................................22

2.5 CÁC PHÉP TOÁN TRÊN CUBE .................................................................................... 23
2.5.1 CHỨA (CONTAIN)..............................................................................................................23
2.5.2 TÍCH (INTERSECTION-AND-PRODUCT) .......................................................................23
2.5.3 TỔNG (UNION-OR-SUM) ..................................................................................................24
2.5.4 HIỆU (DISTANCE-SUBTRACT)........................................................................................25
2.5.5 PHẦN BÙ (COMPLEMENT) ..............................................................................................27
2.5.6 KHOẢNG CÁCH (DISTANCE) ..........................................................................................27
2.5.7 SỰ LIÊN KẾT (CONSENSUS)............................................................................................28

2.6 IMPLICANT, PRIME VÀ ESSENTIAL PRIME .......................................................... 29

2.6.1 IMPLICANT (TOÁN HẠNG HAY TÍCH)..........................................................................29
2.6.2 PRIME IMPLICANT (TỐN HẠN HAY TÍCH LỚN NHẤT) ..........................................30
2.6.3 ESSENTIAL PRIME (TỐN HẠN HAY TÍCH LỚN NHẤT CẦN THIẾT).....................30
2.6.4 IRREDUNDANT hay MINIMAL (TẬP PHỦ TỐI THIỂU)................................................30
2.6.5 SINGLE CUBE CONTAINMENT (SỰ CHỨA BỞI MỘT CUBE ĐƠN) ..........................30

CHƯƠNG 3: CÁC CƠNG TRÌNH LIÊN QUAN .........................................................31
3.1 PHƯƠNG PHÁP KARNAUGH MAP (K-MAP)............................................................ 31
3.1.1 GIẢI THUẬT KARNAUGH MAP ......................................................................................31
3.1.2 NHẬN XÉT ..........................................................................................................................32
3.1.3 VÍ DỤ ..................................................................................................................................32

Nguyễn Văn Tân - 00705153

Trang 6


Tối ưu hóa vi mạch hai lớp với các phương pháp dành cho bài toán set covering

3.1.4 CÁC LUẬT ĐƠN GIẢN HÓA CỦA KARNAUGH ...........................................................33
3.1.5 ÁP DỤNG PHƯƠNG PHÁP KARNAUGH VỚI MƠ HÌNH ĐỒ THỊ ...............................34
3.1.6 ÁP DỤNG PHƯƠNG PHÁP KARNAUGH VỚI MƠ HÌNH “CÂY RÚT GỌN” ..............35

3.2 PHƯƠNG PHÁP QUINE-MCCLUSKEY ...................................................................... 37
3.2.1 GIẢI THUẬT........................................................................................................................37
3.2.2 NHẬN XÉT ..........................................................................................................................40
3.2.3 VÍ DỤ ..................................................................................................................................40
3.2.4 ÁP DỤNG PHƯƠNG PHÁP QUINE-MCCLUSKEY VỚI MƠ HÌNH ĐỒ THỊ ................48
3.2.5 ÁP DỤNG PHƯƠNG PHÁP QUINE-MCCLUSKEY VỚI MƠ HÌNH “CÂY RÚT GỌN”48


3.3 PHƯƠNG PHÁP ESPRESSO .......................................................................................... 50
3.3.1 GIẢI THUẬT ESPRESSO-I.................................................................................................50
3.3.2 GIẢI THUẬT ESPRESSO-II................................................................................................50
3.3.3 NHẬN XÉT ..........................................................................................................................51
3.3.4 VÍ DỤ ..................................................................................................................................52
3.3.5 ÁP DỤNG PHƯƠNG PHÁP ESPRESSO VỚI MƠ HÌNH ĐỒ THỊ ...................................54
3.3.6 ÁP DỤNG PHƯƠNG PHÁP ESPRESSO VỚI MƠ HÌNH “CÂY RÚT GỌN”..................54

CHƯƠNG 4:
PHƯƠNG PHÁP QUY HOẠCH NGUYÊN CHO MẠCH HAI
LỚP ...............................................................................................................56
4.1 NHẬN XÉT CÁC THUẬT TỐN ĐANG CĨ ............................................................... 56
4.2 MƠ HÌNH SET COVERING CHO MẠCH HAI LỚP.................................................. 58
4.3 GIẢI THUẬT ..................................................................................................................... 59

CHƯƠNG 5:

HIỆN THỰC CHƯƠNG TRÌNH ......................................................65

5.1 HIỆN THỰC MODULE TẠO PRIME IMPLICANTS................................................. 65
5.2 HIỆN THỰC MODULE TẠO ESSENTIAL PRIME IMPLICANTS ......................... 67
5.3 HIỆN THƯC MODULE TÌM HIỆU CỦA HAI HÀM ĐẠI SỐ LUẬN LÝ................. 68
5.4 HIỆN THỰC MODULE TẠO MINTERMS .................................................................. 68
5.5 HIỆN THỰC MODULE TẠO TẬP TIN ĐỊNH DẠNG MPS ....................................... 70
5.6 HIỆN THỰC MODULE GIẢI MÔ HÌNH SET COVERING ...................................... 71
5.7 HIỆN THỰC MODULE TỔNG HỢP KẾT QUẢ.......................................................... 73
5.8 HIỆN THỰC MODULE SO SÁNH KẾT QUẢ.............................................................. 73

CHƯƠNG 6:


TỔNG KẾT VÀ SO SÁNH KẾT QUẢ.............................................74

6.1 TỔNG KẾT ........................................................................................................................ 74
6.2 SO SÁNH KẾT QUẢ......................................................................................................... 74

CHƯƠNG 7:

KẾT LUẬN VÀ HƯỚNG PHÁT TRIỂN.........................................83

7.1 KẾT LUẬN......................................................................................................................... 83
7.2 HƯỚNG PHÁT TRIỂN CỦA LUẬN VĂN..................................................................... 84

PHỤ LỤC .........................................................................................................................85
PHỤ LỤC 1: TỐI ƯU VI MẠCH THEO MƠ HÌNH ĐỒ THỊ ........................................... 85
PHỤ LỤC 2: TỐI ƯU VI MẠCH THEO MƠ HÌNH “CÂY RÚT GỌN” ......................... 90

TÀI LIỆU THAM KHẢO................................................................................................92
Nguyễn Văn Tân - 00705153

Trang 7


Tối ưu hóa vi mạch hai lớp với các phương pháp dành cho bài tốn set covering

TĨM TẮT
Luận văn này tập trung vào việc tối ưu hóa vi mạch hai lớp, đây cũng là một dạng hàm
đại số luận lý dạng tổng các tích. Như chúng ta đã biết bài tốn tối ưu hàm luận lý là bài
tốn khó thuộc dạng NP-Hard. Vì vậy việc giải nó là vấn đề nan giải từ trước đến nay. Đã
có những cơng trình liên quan giải vấn đề này như: Karnaugh, Quine-McCluskey và
Espresso. Đề tài luận văn muốn giải bài toán này bằng một phương pháp khác đó là đưa

bài tốn tối ưu mạch hai lớp về mơ hình set covering và giải mơ hình này bằng việc phối
hợp một số phương pháp khác nhau như: sử dụng các phép toán biến đổi của hàm luận lý,
sử dụng kỹ thuật dominance columns và dominance rows, sử dụng giải thuật Branch and
Bound và dùng kỹ thuật Cutting plane.
Để thực hiện việc này tác giả đã tìm hiểu lại lý thuyết và khái niệm cơ bản về đại số luận
lý, các phép toán trên toán hạng và hàm luận lý được thể hiện trong chương 2. Người đọc
có những kiến thức nền tảng về đại số luận lý có thể bỏ qua chương này. Tuy nhiên, trong
chương 2, tác giả cũng đóng góp một phần vào việc tính hiệu trực tiếp giữa hai tốn hạng
và hai hàm luận lý. Trước đây việc tính hiệu hai tốn hạng hay hai hàm thì thường nhờ
vào phép tốn nhân và phép toán lấy phần bù: C = A – B = A ∩ B’.
Sau đó tác giả tìm hiểu về các cơng trình và sản phẩm có liên quan trên thế giới như:
Karnaugh, Quine-McCluskey và Espresso được trình bày trong chương 3. Sau khi nghiên
cứu giải thuật và sự hiện thực các cơng trình liên quan đến đề tài, tác giả luận văn đã mơ
hình hóa các cơng trình này bằng lý thuyết đồ thị và mơ hình cây rút gọn. Ngồi ra tác giả
cịn xây dựng cơ sở lý thuyết đồ thị cho việc tối ưu vi mạch trong phụ lục 1 và xây dựng
mơ hình cây rút gọn để tối ưu vi mạch bằng hình ảnh trong phụ lục 2.
Giải thuật chính của luận văn được đề cập trong chương 4. Trong chương này tác giả đã
trình bày tổng qt vấn đề mà bài tốn tối ưu vi mạch cần quan tâm. Sau đó tác giả xây
dựng mơ hình cho bài tốn và cuối cùng là trình bày giải thuật phù hợp để giải mơ hình
này. Trong phần này tác giả đã sử dụng các công cụ toán học phù hợp cho từng giai đoạn
tối ưu như: các phép toán trên toán hạng và hàm, kỹ thuật dominance columns và

Nguyễn Văn Tân - 00705153

Trang 8


Tối ưu hóa vi mạch hai lớp với các phương pháp dành cho bài toán set covering

dominance rows, kỹ thuật chọn vùng trọng điểm của mơ hình set covering, giải thuật

brand and bound và cutting plane.
Phần hiện thực thể hiện trong chương 5. Trong chương này tác giả cũng có một số đóng
góp nho nhỏ cho khoa học về việc cải tiến các giải thuật như: giải thuật tìm essential
prime implicants, giải thuật tìm minterms, giải thuật tìm hiệu hai hàm và đặc biệt là kỹ
thuật chọn vùng dữ liệu chính của mơ hình set covering.
Trong chương 6, tác giả đã so sánh kết quả với các cơng trình khác. Ở đây chủ yếu so
sánh với chương trình Espresso. Vì chương trình Karnaugh và Quine-McCluskey chạy
với số biến nhập rất hạn chế và dữ liệu đầu vào là dạng bảng luận lý khơng phù hợp với
dữ liệu của chương trình luận văn. Tác giả đã dùng bộ “test bench” của hệ thống quốc tế
để kiểm tra chương trình. Đồng thời tác giả cũng trung thực so sánh kết quả với chương
trình espresso.
Tổng kết cơng việc đã làm và hướng phát triển của luận văn được đề cập ở chương 7.
Trong chương này tác giả cũng nêu lên những kết quả đạt được và những thiếu sót trong
lúc nghiên cứu thực hiện luận văn. Hướng phát triển của đề tài cũng được xây dựng theo
hai tiêu chí: thứ nhất là nghiên cứu sâu hơn về lý thuyết mơ hình set covering và các kỹ
thuật ứng dụng cho giải thuật Brand and Bound. Và thứ hai là hoàn chỉnh và phát triển
phần ứng dụng, cải tiến việc tổ chức cấu trúc dữ liệu cho phù hợp, xây dựng thành
module để tích hợp vào hệ thống mô phỏng thiết kế và chế tạo vi mạch.
Sau đây là nội dung chi tiết của luận văn.

Tác giả: Nguyễn Văn Tân.

Nguyễn Văn Tân - 00705153

Trang 9


Tối ưu hóa vi mạch hai lớp với các phương pháp dành cho bài toán set covering

ABSTRACT

The thesis concentrates on two-levels of circuit optimization, which is boolean algebra
sum of the products. As we know, optimal solution of boolean algebra is NP-Hard
problem. Therefore, to find its solution is a difficult problem. There were a lot of related
projects: Karnaugh, Quine-McCluskey and Espresso methods. The thesis wants to solve
the problem by other methods which is to convert two-levels of circuit optimization
problem to set covering model and solve the model by combining a few of the methods
as: operations transform logic functions, dominance columns and dominance rows
technics, Branch-and-Bound algorithm and Cutting plane technics.
To do that, we learned about Boolean Algebra theory and basic concepts, the operations
of operands and function which are showed in chapter 2. If you know about basic boolean
algebra you can ignore the chapter. However, in this chapter, we contribute a part in
Boolean Algebra that is directly subtracted computing between two operands or between
two functions. Before the subtracted computing between two operands or between two
functions are used product operation and complement operation: C = A – B = A ∩ B’.
After we find out about related researches and products in the world: Karnaugh, QuineMcCluskey and Espresso that are showed in chapter 3. After studying the algorithms and
projects that are related to my thesis, I remodeled these projects by graph theory model
and reduce tree model. Besides, we also built based graph theory for circuit optimization
in the first appendix and built reduced tree model to optimize circuit by the flowchart in
the second appendix.
The main algorithm of the thesis was mentioned in chapter 4. In this chapter, we show
general problems which optimization circuit needs care about. After, we build computing
model for this problem and we show the suitable algorithms for solving this model. In this
part, we use suitable mathematical tools for optimal steps: operand and function
operations, dominance columns and dominance rows technics, choosen technics main
data area of set covering model, brand and bound algorithm and cutting plane technics.
The implementation was showed in chapter 5. In this chapter, we also contribute a little to
science as to improve algorithms: algorithm to find essential prime implicants, find
minterms, find subtraction of two functions, choosen technics main data area for set
covering model.


Nguyễn Văn Tân - 00705153

Trang 10


Tối ưu hóa vi mạch hai lớp với các phương pháp dành cho bài toán set covering

In 6th chapter, we compared the result with different projects, the main comparison is
Espresso program. Because Karnaugh and Quine-McCluskey programs work with little
number variable input and input data is logic table which is not suitable with data of this
thesis. We used "test bench" of international systems to test the project and we also
honestly compared the result with the espresso program.
The summary and developing of this thesis was mentioned in chapter 7. In this chapter,
we have talked about good results and mistakes in research. The developing of this thesis
was built on 2 criterions: The first criteria is careful research about the theory set covering
model and the technics that are used for Brand-and-Bound algorithms, the second criteria
is fully and developable applications, improved data organization which were more
suitable, built to modules to integrate chip design system and chip production system.
The details of this thesis are mentioned below.

Writer: Nguyen Van Tan

Nguyễn Văn Tân - 00705153

Trang 11


Tối ưu hóa vi mạch hai lớp với các phương pháp dành cho bài toán set covering

CHƯƠNG 1: CHƯƠNG MỞ ĐẦU

1.1 QUY TRÌNH THIẾT KẾ VÀ SẢN XUẤT VI MẠCH (CHIP)

Hình 1.1: Quy trình sản xuất vi mạch.
Quy trình sản xuất chip vi mạch chia làm 4 giai đoạn chính: thiết kế, kiểm tra, sản xuất và
đóng gói sản phẩm. Trong giai đoạn thiết kế gồm có: phát thảo ý tưởng, xây dựng mơ
hình, tổng hợp vi mạch, tối ưu vi mạch, và kiểm tra tính đúng đắng của mơ hình. Tối ưu là
cơng đoạn quan trọng trong việc thiết kế hướng đến việc làm cho vi mạch thiết kế tốt hơn
theo một hay nhiều tiêu chí nào đó. Vì vậy vấn đề tối ưu vi mạch mức luận lý đươc nhiều
nhà sản xuất và thiết kế chú trọng vào.
Tối ưu vi mạch là một trong những công đoạn quan trọng trong tự động hóa thiết kế vi
mạch. Các vi mạch được thiết kế dựa trên các ý tưởng có tính trừu tượng hay thể hiện
mục đích thỏa mãn nhu cầu một số chức năng của hệ thống. Vì vậy chúng có tính khái
Nguyễn Văn Tân - 00705153

Trang 12


Tối ưu hóa vi mạch hai lớp với các phương pháp dành cho bài toán set covering

quát rất cao và có rất nhiều điểm chưa hợp lý. Tự động hóa quá trình tối ưu vi mạch sẽ
giúp điều chỉnh vi mạch theo những tiêu chí mong muốn của nhà sản xuất. Như tối ưu về
hàm số biểu diễn vi mạch, tối ưu hóa về tần số đáp ứng, tối ưu về thời gian trễ, tối ưu về
công suất tiêu thụ, tối ưu về diện tích vi mạch, tối ưu về công nghệ rút ngắn khoảng cách
giữa hai điểm. Tối ưu hàm biểu diễn vi mạch là một trong những công đoạn rất cần thiết
để hoàn chỉnh vi mạch. Một trong những yếu tố quan trọng nhất ảnh hưởng đến chức
năng của chip, mà q trình tự động hóa thiết kế vi mạch quan tâm, đó là kiểm tra tính
chính xác và tối ưu về hàm ở mức luận lý hay sử dụng số cổng thật hợp lý cho một chip vi
mạch.
Trong sản xuất chip, người ta chia vi mach làm 2 loại chính: mạch tổ hợp (combination
circuit) và mạch tuần tự (sequent circuit). Mạch tổ hợp là sự kết hợp các cổng luận lý

(NOT, AND, OR) và không dùng hệ thống xung clock để đồng bộ tín hiệu. Mạch tổ hợp
chia làm hai nhóm chính là: mạch hai lớp (Two-Level Circuits) và mạch nhiều lớp (MultiLevel Circuits), mạch nhiều lớp là sự kết hợp nhiều khối của mạch hai lớp. Mạch tuần tự
là mạch được kết hợp từ nhiều khối mạch tổ hợp lại với nhau và có xung clock để đồng
bộ tín hiệu giữa các khối. Mạch tuần tự lại được chia làm hai nhóm chính là: mạch đồng
bộ (synchronous circuits – single clock) và mạch bất đồng bộ (asynchronous circuits –
multiple clock).
Qua phân tích hệ thống vi mạch ta nhận thấy hệ thống vi mạch hai lớp là cơ sở nền tảng
cho các hệ thống khác như: mạch tổ hợp nhiều lớp, mạch tuần tự đồng bộ và mạch tuần tự
bất đồng bộ. Do vậy việc tối ưu vi mạch hai lớp rất có ý nghĩa và cơng việc này được
dùng lại nhiều lần khi thiết kế tất cả các loại vi mạch.
Để biểu diễn hàm chức năng của vi mạch hai lớp chúng ta có nhiều cách đặt tả: bảng chân
trị cho hàm luận lý, biểu diễn bằng cơng thức hàm luận lý tổng các tích (Sum Of Product
– SOP), vẽ sơ đồ khối hình học nhiều chiều, tạo bảng Karnaugh, biểu diễn bằng sơ đồ cậy
quyết định nhị phân BDD (Binary Decision Diagram) hay mã hóa chúng bằng sự xuất
hiện của các tốn hạng (các tích: products hay cubes). Trên cơ sở đó ta có thể mã hóa hàm
luận lý thành một tập tin dữ liệu đầu vào và tập tin kết quả để xử lý tối ưu (tập tin định

Nguyễn Văn Tân - 00705153

Trang 13


Tối ưu hóa vi mạch hai lớp với các phương pháp dành cho bài toán set covering

dạng BLIF “Berkeley Logic Interchage Format” của Đại học Bekerley, SLIF “Stanford
Logic Interchage Format” của Đại học Stanford hay dạng ESPRESSO).
Để hiện thực mạch tổ hợp hai lớp thì ta có thể biểu diễn qua các cổng luận lý cơ bản:
NOT, AND và OR. Các cổng luận lý này được tạo lập từ đơn vị cơ sở là transistor và
transistor được tạo từ chất bán dẫn silicon N hay P mang điện tích âm hay mang điện tích
dương (N+, N-, P+, P-).

Trên đây là sơ lược cơ sở nền của nguyên lý thiết kế và sản xuất vi mạch từ chất bán dẫn
và cũng thể hiện vị trí và vai trị của việc tối ưu vi mạch hai lớp trong các tiến trình này.

1.2 VẤN ĐỀ TỐI ƯU VI MẠCH HAI LỚP
Ta xem mạch luận lý hai lớp như là một hàm đại số luận lý dạng tổng các tích. Để phủ hết
hàm này ta dùng các minterms1. Nhưng việc phủ hàm đại số luận lý bằng các minterms
thì số cổng biểu diễn hàm hay hiện thực mạch là rất lớn khoảng. Do đó ta rút gọn các
minterms thành các implicants nhờ phép biến đổi đại số. Số lượng các implicants này còn
lớn hơn số minterms, và ta lại tìm số lượng implicants nhỏ nhất để bao phủ hết các
minterms thể hiện chức năng của hàm luận lý, sự bùng nổ tổ hợp này tăng theo hàm mũ.
Vì vậy bài tốn rất lớn về khối lượng tính tốn và lưu trữ khi số biến nhập đủ lớn. Đây là
bài toán thuộc họ bài toán NP-Hard (Nondeterministic Polynomial-time Hard).
Vấn đề tối ưu vi mạch hai lớp có thể đưa về mơ hình tốn set covering. Nếu ta chỉ biến
đổi bài toán tối ưu vi mạch hai lớp sang mơ hình tốn set covering để giải mà khơng có
những xử lý cần thiết trước khi giải thì số lượng biến (cột) và ràng buộc (hàng) rất lớn. Số
lượng biến là số implicants của vi mạch, ta có khoảng 3n – 2n implicants với n là số biến
nhập. Và số ràng buộc là số minterms, ta có khoảng 2n minterms. Một mặt là việc tạo dữ
liệu đầu vào không cho phép, mặt khác các các công cụ giải bài toán set covering ngày
nay chỉ giới hạn khoảng 10.000 hàng và 10.000 cột là tối đa. Vì vậy trước khi giải mơ
hình set cevering bằng một giải thuật cụ thể, chúng ta cần có những phương pháp làm
giảm kích thước của bài tốn.
Ví dụ: Một hàm đại số luận lý chứa khoảng 2121 minterms (khoảng 2 giga giga giga giga
minterms) thì ta khơng thể liệt kê hết số lượng minterms để đưa vào mơ hình tốn set
1

Tích đầy đủ.

Nguyễn Văn Tân - 00705153

Trang 14



Tối ưu hóa vi mạch hai lớp với các phương pháp dành cho bài tốn set covering

covering với cơng nghệ máy tính ngày nay (khoảng vài giga bytes RAM và vài trăm giga
bytes Hard Disk).

1.3 GIẢI QUYẾT VẤN ĐỀ
Sử dụng mơ hình set covering để mơ hình hóa bài tốn tối ưu vi mạch hai lớp:

Tìm min CTx = ?
thỏa Ax ≥ 1, với aij ∈{0,1}.
Với A là ma trận nhị phân aij ∈ {0, 1}. Nếu minterm hàng i được chứa trong implicant cột
j thì aij = 1, ngược lại aij = 0.
Vector x với xi ∈ {0, 1} là thể hiện sự hiện diện các cột. Kết quả sau khi giải, nếu
implicant thứ i là nghiệm thì xi = 1, ngược lại xi = 0.
Để giải quyết vấn đề trên bao gồm giảm các cột, giảm các hàng và chọn phần dữ liệu
quan trọng phù hợp với công cụ giải mơ hình tốn Integer Programming (IP) ngày nay.
Tác giả luận văn đã xây dựng cách giải quyết vấn đề như sau:
Từ hàm đại số luận lý đã cho ta thực hiện các thao tác:
-

Dùng các phép toán biến đổi của đại số luận lý tạo ra các prime implicants.

-

Loại trừ các dominance columns.

-


Đưa các essential prime implicants vào hàm kết quả.

-

Loại trừ các dominance rows.

-

Chọn vùng dữ liệu quan trọng và phù hợp của bài toán để xậy dựng giải thuật lặp.

-

Chọn công cụ giải vấn đề Integer Programming phù hợp để giải.

Ví dụ: Ta có hàm f với 1 biến xuất và 3 biến nhập a, b, c cần tối ưu như sau:
f = a’b’c’ + a’b’c + ab’c + abc + abc’1
Giải:
Bước 1: Xây dựng bảng implicant nhờ phép kết hợp.
Minterms
abc
000
001
101
110
1

Implicants bậc 1
a b c
0 0 - 0 1
1 - 1

1 1 -

Implicant bậc 2
a b c

Ký hiệu: a’ là NOT(a), b’ là NOT(b), c’ là NOT(c).

Nguyễn Văn Tân - 00705153

Trang 15


Tối ưu hóa vi mạch hai lớp với các phương pháp dành cho bài toán set covering

111
Sau khi tạo các implicants, hàm đã cho có thể viết lại như sau:
f = a’b’ + b’c + ac + ab
Tuy nhiên đây cũng chưa là hàm tối ưu.
Bước 2: Biểu diễn lại hàm đã cho theo mơ hình set covering
a’b’c’
a’b’c
ab’c
abc
abc’

a’b’
1
1
0
0

0

b’c
0
1
1
0
0

ac
0
0
1
1
0

ab
0
0
0
1
1

Bước 3: Loại bỏ các essential prime implicants
Ta thấy có 2 essential prime implicants là: a’b’ và ab. Đưa các essential prime implicants
này vào hàm kết quả.
Ta có hàm hết quả là:
fkq = a’b’ + ab.
Bước 4: Kiểm tra điều kiện lặp.
Ta kiểm tra hàm kết quả có phủ kín các minterms của hàm ban đầu hay khơng? Nếu phủ

kín thì dừng. Ngược lại ta chọn thêm vùng dữ liệu chưa bị phủ để giải tiếp. Trong trường
hợp này vì hàm kết quả chưa phủ kín (f – fkq = ab’c) nên ta tiếp tục giải.
Bước 5: Đưa các essential prime implicants vào hàm kết quả và loại các dominance rows.
ab’c

b’c
1

ac
1

Ta còn lại mơ hình tương đối nhỏ.
Bước 6: Chọn một phần dữ liệu của mơ hình set covering để giải.
Giả sử chọn vùng:
ab’c

b’c
1

Bước 7: Giải vấn đề Integer Programming trên.
Sau khi giải ta có nghiệm là b’c. Đưa b’c vào hàm kết quả.
Bước 8: Tổng hợp kết quả.
Ta có hàm hết quả là:
fkq = a’b’ + b’c + ab.
Nguyễn Văn Tân - 00705153

Trang 16


Tối ưu hóa vi mạch hai lớp với các phương pháp dành cho bài toán set covering


Bước 9: Kiểm tra điều kiện lặp.
Ta kiểm tra hàm kết quả có phủ kín các minterms của hàm ban đầu hay khơng? Nếu phủ
kín thì dừng. Ngược lại ta chọn thêm vùng dữ liệu chưa bị phủ. Trong trường hợp này vì
hàm kết quả phủ kín (f – fkq = ∅) nên ta dừng.
Bước 10: Kết luận nghiệm.
Hàm đã cho được tối ưu thành hàm sau:
fkq = a’b’ + b’c + ab.
kết quả này phụ thuộc vào việc ta chọn vùng dữ liệu để giải và kết quả của việc giải vấn
đề Integer Programming.
Tuy nhiên bài toán trên cho hai kết quả tối ưu là:
f = a’b’ + b’c + ab và
f = a’b’ + ac + ab.

Nguyễn Văn Tân - 00705153

Trang 17


Tối ưu hóa vi mạch hai lớp với các phương pháp dành cho bài toán set covering

CHƯƠNG 2: KHÁI NIỆM CƠ BẢN
2.1 HÀM LUẬN LÝ (BOOLEAN HAY LOGIC FUNCTION)
Cho B={0,1}, Y={0,1,2}. Một hàm luận lý ff trong n biến nhập1 x1, x2, …, xn và m biến
xuất2 y1, y2, …, ym là một hàm:
ff : Bn Ỉ Ym
ở đây x = [x1, x2, …, xn ] ∈ Bn là bộ biến nhập của ff, và
y = [ y1, y2, …, ym ] ∈ Ym là bộ biến xuất của ff.
Các biến xuất yi thường nhận giá trị là 0 (false) hay 1 (true), đôi khi cũng nhận giá trị
không xác định là 2 (don’t-care value).

Hàm luận lý đặc tả không hồn tồn (incompletely specified) ff là hàm trong đó tồn tại i
mà giá trị của yi là 2.
Một hàm luận lý đặc tả hoàn toàn (completely specified) ff là một hàm luận lý với tất cả
biến xuất yi là 0 hay 1.
Mỗi thành phần của ff ký hiệu là ffi, i=1, 2, …, m. Chúng ta định nghĩa:
• Tập on-set XiON ⊆ Bn, là tập các giá trị nhập x thỏa ffi(x)=1.
• Tập off-set XiOFF ⊆ Bn, là tập các giá trị nhập x thỏa ffi(x)=0.
• Tập don’t-care-set XiDC ⊆ Bn, là tập các giá trị nhập x thỏa ffi(x)=2.
Một hàm luận lý với m=1 được gọi là hàm một giá trị xuất (single-output).
Một hàm luận lý với m>1 được gọi là hàm nhiều giá trị xuất (multiple-output).
Có nhiều cách thể hiện hàm luận lý: dạng đại số (Algebraic form), dạng bảng chân trị
(tabular form hay truth table), dạng bìa Karnaugh, dạng đồ thị (Graph), sơ đồ cây
quyết định nhị phân BDD (Binary Dicision Diagram), dạng khối hình học nhiều chiều
hay dạng tập tin blif, slif, espresso, …
Một ví dụ về hàm luận lý biểu diễn dạng bảng chân trị. Cho ff: B3 Ỉ Y2 được đặc tả bởi:

1
2

x1

x2

x3

y1

y2

0

0
0
0
1
1
1
1

0
0
1
1
0
0
1
1

0
1
0
1
0
1
0
1

1
1
0
0

1
1
1
2

1
0
1
1
0
2
1
1

Input variables.
Output variables.

Nguyễn Văn Tân - 00705153

Trang 18


Tối ưu hóa vi mạch hai lớp với các phương pháp dành cho bài tốn set covering

Ta có: ff = ff1 + ff2.
Hàm ff1 được thể hiện bởi:
X1ON = {[0,0,0], [0,0,1], [1,0,0], [1,0,1], [1,1,0]},
X1OFF = {[0,1,0], [0,1,1]},
X1DC = {[1,1,1]}.
Và hàm ff2 được thể hiện bởi:

X2ON = {[0,0,0], [0,1,0], [0,1,1], [1,1,0], [1,1,1]},
X2OFF = {[0,0,1], [1,0,0]},
X2DC = {[1,0,1]}.

2.2 CÁC PHÉP TOÁN TRÊN HÀM LUẬN LÝ
Trong trường hợp hàm luận lý ff nhiều biến xuất thì các phép tốn luận lý được thực hiện
trên các thành phần ffi của mỗi biến xuất.
2.2.1 PHẦN BÙ (COMPLEMENT)
Phần bù của hàm đặc tả hoàn toàn
ff: Bn Æ Bm,
là hàm đặ tả hoàn toàn
ff’: Bn Æ Bm
với các thành phần của nó ff1, ff2, …, ffm có on-set bằng off-set của thành phần tương ứng
của ff và off-set bằng on-set của thành phần tương ứng của ff.
2.2.2 TÍCH (INTERSECTION-PRODUCT)
Tích của hai hàm luận lý đặc tả hồn toàn f và g là:
h=f∩g
là hàm luận lý đặc tả hồn tồn với các thành phần của nó hi có on-set bằng tích của onset của các thành phần tương ứng của f và g.
2.2.3 HIỆU (DIFFERENCE-SUBTRACT)
Hiệu của hai hàm luận lý đặc tả hoàn toàn f và g là:
h = f – g = f ∩ g’
là hàm luận lý đặc tả hồn tồn h cho bởi tích của f với phần bù của g. Tập on-set của các
thành phần của h là các phần tử on-set của các thành phần tương ứng của f mà khơng có
trong on-set của các thành phần tương ứng của g.
2.2.4 TỔNG (UNION-SUM)
Tổch của hai hàm luận lý đặc tả hoàn toàn f và g (với f: Bn Ỉ Bm và g: Bn Æ Bm) là:
h=f+g
Nguyễn Văn Tân - 00705153

Trang 19



Tối ưu hóa vi mạch hai lớp với các phương pháp dành cho bài toán set covering

là hàm luận lý đặc tả hoàn toàn h với on-set của các thành phần của h, hi là tổng on-set
của các thành phần tương ứng fi và gi của f và g.
2.2.5 HẰNG ĐÚNG (TAUTOLOGY)
Một hàm đặc tả hoàn toàn f là hằng đúng viết là f ≡ 1, nếu off-set của tất cả các thành
phần là rỗng hay nói cách khác tất cả biến xuất của f nhận giá trị là 1 với tất cả biến nhập.
Trong trường hợp hàm luận lý đặc tả khơng hồn tồn thì ta tách thành ba hàm đặc tả
hoàn toàn: ffON, ffDC và ffOFF, đây là cách thể hiện 1-1 của nguyên bản hàm đặc tả khơng
hồn tồn. Với:
• ffON có on-set của các thành phần của nó bằng on-set của các thành phần tương ứng
của ff và off-set của các thành phần của nó bằng tổng don’t-care-set và off-set của
các thành phần tương ứng của ff.
• ffDC có on-set của các thành phần của nó bằng don’t-care-set của các thành phần
tương ứng của ff và off-set của các thành phần của nó bằng tổng on-set và off-set
của các thành phần tương ứng của ff.
• ffOFF có on-set của các thành phần của nó bằng off-set của các thành phần tương
ứng của ff và off-set của các thành phần của nó bằng tổng don’t-care-set và on-set
của các thành phần tương ứng của ff.
Chúng ta có thể dùng ký hiệu (f,d,r) để thay cho bộ ba (ffON, ffDC, ffOFF) cho bởi ff. Để ý
rằng f ∪ d ∪ r bao phủ m không gian luận lý kết hợp với ff. Cho mỗi thành phần i, 1≤ i ≤
m, tập on-set của fi, di và ri là hằng đúng của thành phần ffi. Vì vậy f ∪ d ∪ r là một hằng
đúng của hàm ff.

2.3 BIỂU DIỄN ĐẠI SỐ CỦA HÀM LUẬN LÝ
Gọi ffi là một thành phần của ff. Một biểu diễn đại số của ffi hay fi là một biểu thức luận lý
với:
0 cho tất cả các biến nhập trong XiOFF, và

1 cho tất cả các biến nhập trong XiON, và
0 hay 1 cho tất cả các biến nhập trong XiDC.
Ví dụ: Cho ff : B3 Ỉ Y2 như sau :
x1

x2

x3

y1

y2

0
0
0
0
1
1
1
1

0
0
1
1
0
0
1
1


0
1
0
1
0
1
0
1

1
1
0
0
1
1
1
2

1
0
1
1
0
2
1
1

Nguyễn Văn Tân - 00705153


Trang 20


Tối ưu hóa vi mạch hai lớp với các phương pháp dành cho bài tốn set covering

Ta có thể biểu diễn bảng chân trị trên thành dạng đại số như sau:
ff1≡ x’1x’2x’3 + x’1x’2x3 + x1x’2x’3 + x1x’2x3 + x1x2x’3.
ff2≡ x’1x’2x’3 + x’1x2x’3 + x’1x2x3 + x1x2x’3 + x1x2x3.
Sau khi rút gọn ta được:
ff1≡ x’2 + x1x’3.
ff2≡ x2 + x’1x’3.
Thay x1, x2, x3 bằng A, B, C ta được:
ff1≡ B’ + AC’.
ff2≡ B + A’C’.

2.4 CUBE, COVER VÀ MINTERM
2.4.1 CUBE
Nhìn theo góc độ hình học: cube trong khơng gian luận lý n biến nhập kết hợp với một
hàm nhiều biến xuất ff là tập các đỉnh mà nó được bao phủ bởi các thành phần ffi của hàm
ff hoặc khơng.
Nhìn theo dạng biểu diễn đại số: cho p là một tích kết hợp với biểu thức tổng các tích đại
số của một hàm luận lý với n biến nhập và m biến xuất thì một cube p được đặc tả bởi
một vector hàng: c = [c1, c2, …, cn, cn+1, …, cn+m].
với:
0 nếu xi xuất hiện trong p dạng đảo.
1 nếu xi xuất hiện trong p dạng không đảo.
ci =

2 nếu xi không xuất hiện trong p.
3 nếu p không xuất hiện trong fi-n.

4 nếu p xuất hiện trong fi-n.

Ví dụ: Cho p = x’2 trong ví dụ trên, nó chỉ xuất hiện trong f1 và không xuất hiện trong f2.
Do đó ta có: c = [2 0 2 4 3]
Phần biến nhập của c hay biến nhập của cube c là I(c), là vector con của c chứa n phần tử
đầu của c. Trong ví dụ trên I(c) là [2 0 2]. Với 2 là giá trị không xác định (don’t-care).
Phần biến xuất của c hay biến xuất của cube c là O(c), là vector con của c chứa m phần tử
cuối của c. Trong ví dụ trên O(c) là [4 3]. Với 3 là 0 trong f1 và 4 là 1 trong f2.
2.4.2 COVER
Một tập của cubes V = {c1, c2, …, ck} được gọi là một cover cho hàm luận lý ff với n
biến nhập và m biến xuất, nếu, cho j = 1, …, m tập phần biến nhập của cubes có một giá
trị 4 trong vị trí thứ j. chứa tất cả các đỉnh tương ứng với on-set của ffj và không chứa đỉnh
Nguyễn Văn Tân - 00705153

Trang 21


Tối ưu hóa vi mạch hai lớp với các phương pháp dành cho bài toán set covering

tương ứng với off-set của ffj, cũng có nghĩa là một cover thể hiện tổng của on-set và vài
don’t-care-set. Cover và biểu diễn đại số là tương ứng 1-1 vì vậy ta có thề thay việc biểu
diễn cover bằng biểu diễn đại số và ngược lại.
Một tập cubes V xác định một hàm luận lý đặc tả hoàn toàn được viết là b(V).
Chúng ta sử dụng ma trận để biểu diễn cover hay biểu diễn dạng đại số. Ma trận M(V) kết
hợp với cover V = {c1, c2, …, ck} là ma trận đạt được bằng cách xếp chồng các vector
hàng biểu diễn cubes V.
Ví dụ: Ma trận biểu diễn cubes V tương ứng hàm ff = ff1 + ff2, với:
ff1≡ x’2 + x1x’3.
ff2≡ x2 + x’1x’3.
là:

F=

M(V) =

2
1
2
0

0
2
1
2

2
0
2
0

4
4
3
3

3
3
4
4

2.4.3 MINTERM

Minterm ei là một cube mà phần biến nhập của nó khơng chứa giá trị 2 và phần biến xuất
của nó chứa (m-1) giá trị 3 và một giá trị 4 tại vị trí i. Minterm khơng chứa bất kỳ cube
nào trừ nó hay nói cách khác minterm là phần tử nhỏ nhất của cube hay nguyên tử tạo
thành cube.
Nếu một cube c chứa minterm ei, c ⊇ ei, chúng ta nói rằng ei là một phần tử của c, ei ∈ c.
Ví dụ: [1 1 1 4 3] là một minterm và là một phần tử của [2 2 1 4 4].
Mỗi cube có thể phân rã thành tập của các minterms, các minterm này được gọi là những
phần tử của cube.
Ví dụ: Cube c = [2 2 1 4 4] được phân rã thành các minterms sau:
m1 = [0 0 1 4 3], m2 = [0 0 1 3 4], m3 = [1 0 1 4 3],
m4 = [1 0 1 3 4], m5 = [0 1 1 4 3], m6 = [0 1 1 3 4],
m7 = [1 1 1 4 3], m8 = [1 1 1 3 4].
Một tập của cube V = {c1, c2, …, ck} chứa một cube c (ta viết c ⊆ V ) nếu mỗi minterm
của c được chứa bởi ít nhất một cube của V.
• Một số cube đặc biệt:
o Cube uj biểu diễn tập phổ quát tại không gian luận lý thứ j.
o Cube U biểu diễn tổng phổ quát hay ff là hằng đúng.
o Cube xj biểu diễn nữa không gian dương của xj.
o Cube `xj biểu diễn nữa không gian âm của xj.
Nguyễn Văn Tân - 00705153

Trang 22


Tối ưu hóa vi mạch hai lớp với các phương pháp dành cho bài toán set covering

1 2 … j ... n

n+1


n+2

n+2

n+j

n+m

uj

2 2 ... 2 ... 2

3

3

3

... 4 ...

3

U

2 2 ... 2 ... 2

4

4


4

... 4 ...

4

j

2 2 ... 1 ... 2

4

4

4

... 4 ...

4

`xj 2 2 ... 0 ... 2

4

4

4

... 4 ...


4

x

2.5 CÁC PHÉP TOÁN TRÊN CUBE
2.5.1 CHỨA (CONTAIN)
Cube c chứa cube d ký hiệu c ⊇ d. Cho c = {c1, c2, …, cn+m} và d = {d1, d2, …, dn+m} là
hai cubes. Chúng ta nói rằng thành phàn cj của cube c chứa (contains hay ⊇), không chứa
(!⊇) hoặc chứa hoàn toàn (⊃) thành phần dj của cube d phù hợp với bảng sau:
dj

cj

⊇

0

1

2

0

⊇

!⊇

!⊇

1


!⊇

⊇

!⊇

2

⊃

⊃

⊇

1≤j≤n

dj

cj

⊇
3

3

4

⊇


!⊇

4

⊃

⊇

n < j≤ n+m

Cube c chứa cube d, c ⊇ d, nếu mỗi phần tử của c chứa tương ứng phần tử của d, cube c
chứa hoàn toàn cube d, c ⊃ d, nếu c chứa d và tồn tại j sao cho: cj ⊃ dj.
Tập cubes C chứa tập cubes D nếu tất cả cube trong D bị chứa bởi một hoặc nhiều
cubes trong C. Tập cubes C chứa hoàn toàn tập cubes D nếu tất cả cube trong D bị
chứa bởi một hoặc nhiều cubes trong C và tồn tại một cube trong D bị chứa hoàn
toàn bởi một hoặc nhiều cubes trong C.
2.5.2 TÍCH (INTERSECTION-AND-PRODUCT)
Tích của 2 cubes c và d là cube e, được viết là e = c ∩ d hay e = cd. Các thành phần ei của
cube e có được từ các thành phần tương ứng của c và d dựa theo bảng sau:
di

ci

∩
0

0

1


2

0

0

1

∅
0

∅
1
1

2

2
Nguyễn Văn Tân - 00705153

1

1≤i≤n

Trang 23


Tối ưu hóa vi mạch hai lớp với các phương pháp dành cho bài toán set covering

di

∩

3

4

3

3

3

4

3

4

ci

n ≤ i ≤ n+m

Khi có một chỉ số i tại ci và di cho ∅ thì cube e là rỗng (empty cube). Nếu phần biến xuất
của e tồn là 3 thì e cũng là cube rỗng. Về mặt hình học, cube có được bởi việc giao 2
cubes là cube mà phần biến nhập của nó tương ứng với các đỉnh chung của c và d, và
phần biến xuất của nó hiện diện nếu cả hai c và d hiện diện.
Do đó, nếu 2 cubes khơng có đỉnh chung hoặc một trong hai đều không hiện diện trong
cùng hàm thành phần ffi của ff thì tích của nó là rỗng, hai cubes này được gọi là trực giao
(orthogonal cubes), và chúng ta viết c∩d = ∅.
Tích của 2 tập cubes là tập của các cubes đạt được bởi thực hiện tích từng cặp cubes

trong 2 tập. Hai tập cubes là trực giao nếu tích của chúng là rỗng. Chú ý rằng cover
f trực giao với cover f’.
Ví dụ: Cho 2 cubes: c = {2 1 1 4 3} và d = {0 1 1 4 4} thì: c ∩ d = {0 1 1 4 3}.
Cho 2 cubes: c = {2 1 0 4 3} và d = {0 1 1 4 4} thì: c ∩ d = ∅.
2.5.3 TỔNG (UNION-OR-SUM)
Tổng của 2 cubes c và d là cube e, được viết là e = c ∪ d hay e = c + d, là tập các đỉnh
phủ bởi phần biến nhập của cà 2 cubes c và d trong không gian luận lý n chiều mà chúng
hiện diện. Nếu chúng ta dùng ma trận để biểu diễn cube thì c ∪ d là ma trận gồm 2 hàng
lần lượt tương ứng của c và d.
Trường hợp đặc biệt:
9 Nếu c ⊂ d thì c ∪ d =d.
9 Nếu d ⊂ c thì c ∪ d =c.
9 Nếu d = c thì c ∪ d =c hay c ∪ d =d
Ví dụ: c = {2 1 0 4 3} và d = {0 1 2 3 4} thì:
c∪d=

2 1 0 4 3
0 1 2 3 4

Trong phép tổng hai cubes, ta có thể kết hợp tổng hai cube c và d thành một cube e nếu
phần biến xuất của chúng giống nhau và phần biến nhập chỉ khác nhau tại một vị trí. Các
thành phần ei của cube e có được từ các thành phần tương ứng của c và d dựa theo bảng
sau:

Nguyễn Văn Tân - 00705153

Trang 24


Tối ưu hóa vi mạch hai lớp với các phương pháp dành cho bài toán set covering


di

ci

∪

0

1

2

0

0

2

2

1

2

1

2

2


2

2

2

1≤i≤n

di
ci

∪

3

4

3

3

∅

4

∅

4


n ≤ i ≤ n+m

Ví dụ: c = {2 1 0 4 3} và d = {0 1 0 4 3} thì: c ∪ d = {2 1 0 4 3}.
c = {2 1 0 4 3} và d = {1 1 0 4 3} thì: c ∪ d = {2 1 0 4 3}
c = {0 1 0 4 3} và d = {1 1 0 4 3} thì: c ∪ d = {2 1 0 4 3}
Tổng của hai tập hợp cubes là tập hợp cubes có được từ việc thực hiện phép tổng
từng cube của hai tập cubes.
2.5.4 HIỆU (DISTANCE-SUBTRACT)
Hiệu của hai cubes c và d, được viết là c – d, là tập đỉnh phủ bởi phần biến nhập của cube
c mà không phủ bởi cube d trong không gian luận lý n chiều mà chúng hiện diện. Hiệu
của 2 cubes là một tập cubes và cũng có thể là tập rỗng.
Dựa vào định nghĩa ta có cơng thức: c – d = c - c ∩ d.
Suy ra:
9 Nếu: c ∩ d = ∅ thì c – d = c.
9 Nếu c ⊆ d thì c – d = ∅.
9 Nếu e = c + d thì c = e – d hay d = e – c.
Trong phép hiệu hai cubes, ta có thể kết hợp hiệu hai cube c và d thành một cube e nếu
phần biến xuất của chúng giống nhau và phần biến nhập chỉ khác nhau tại một vị trí. Các
thành phần ei của cube e có được từ các thành phần tương ứng của c và d dựa theo bảng
sau:
di

ci

Nguyễn Văn Tân - 00705153

-

0


1

2

0

0

0

∅

1

1

∅

∅

2

1

0

∅

1≤i≤n


Trang 25