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

NGUYỄN ĐỨC HƯƠNG QUỲNH

THUẬT TOÁN TỔNG HỢP MẠCH KHẢ ĐẢO ĐA
NGÕ RA HOÀN CHỈNH

Chuyên ngành: Kỹ thuật Điện Tử
Mã số: 60520203

LUẬN VẪN THẠC SĨ

TP. HỒ CHÍ MINH, THÁNG 7 NĂM 2019


CÔNG TRÌNH ĐƯỢC HOÀN THÀNH TẠI:
Trường Đại học Bách Khoa - ĐHQG-HCM
Cán bộ hướng dẫn khoa học: TS. Trần Hoàng Linh
Cán bộ chấm nhận xét 1: TS. Bùi Trọng Tú (ĐH KHTN)
Cán bộ chấm nhận xét 2: TS. Nguyễn Minh Son (ĐH CNTT)

Luận văn thạc sĩ được bảo vệ tại Trường Đại học Bách Khoa, ĐHQG TP. Hồ Chí
Minh, ngày 05 tháng 07 năm 2019.
Thành phần Hội đồng đánh giá luận văn thạc sĩ gồm:
1. PGS. TS. Hoàng Trang
2. TS. Bùi Trọng Tú
3. TS. Nguyễn Minh Sơn
4. TS. Trương Quang Vinh
5. TS. Nguyễn Lý Thiên Trường
Xác nhận của Chủ tịch Hội đồng đánh giá LV và Trưởng Khoa quản lý chuyên ngành

sau khi luận văn đã được sửa chữa (nếu có).
CHỦ TỊCH HỘI ĐỒNG

TRƯỞNG KHOA ĐIỆN - ĐIỆN TỬ


ĐẠI HỌC QUỐC GIA TP.HCM

CỘNG HÒA XÃ HỘI CHỦ NGHĨA VIỆT NAM

ĐỘC Lập - Tự Do - Hạnh Phúc

TRƯỜNG ĐẠI HỌC BÁCH KHOA

NHIỆM VỤ LUẬN VĂN THẠC SĨ
Họ tên học viên: Nguyễn Đức Hương Quỳnh

MSHV: 1670847

Ngày, tháng, năm sinh: 12/02/1992

Nơi sinh: TP.HỒ Chí Minh

Chuyên ngành: Kỹ thuật Điện Tử

Mã số: 60520203
I. TÊN ĐỀ TÀI: THUẬT TOÁN TÔNG HỢP MẠCH KHẢ ĐẢO ĐA NGÕ RA
HOÀN CHỈNH
II. NHIỆM VỤ VÀ NỘI DUNG:
-


Xây dựng được thuật toán tổng hợp mạch khả đảo cho hàm hoàn chỉnh đa ngõ ra.

-

Xây dựng công cụ tổng hợp mạch dựa trên thuật toán trên.
III. NGÀY GIAO NHIỆM VỤ: 11/02/2019
IV. NGÀY HOÀN THÀNH NHIỆM VỤ: 02/06/2019.
V.

CÁN BỘ HƯỚNG DẪN: TS. Trần Hoàng Linh
Tp. HCM, ngày ... tháng ... năm 2019

CÁN BỘ HƯỚNG DẪN

CHỦ NHIỆM BỘ MÔN ĐÀO TẠO
(Họ tên và chữ ký)

(Họ tên và chữ ký)

TRƯỞNG KHOA ĐIỆN - ĐIỆN TỬ
(Họ tên và chữ ký)


Luận văn thạc sĩ

GVHD: TS. Trần Hoàng Linh

i


LỜI CẢM ƠN
Lời đầu tiên, xin gửi lời cảm ơn chân thành và sâu sắc nhất đến Thầy hướng dẫn
luận văn của tôi, TS. Trần Hoàng Linh. Trong suốt quá trình thực hiện đề tài này, Thầy
đã nhiệt tình giúp đỡ và hỗ trợ tôi rất nhiều về kiến thức cũng như tinh thần. Là một kỹ
sư Điện Tử Viễn Thông chưa từng nghiên cứu về các thuật toán tổng hợp mạch lượng
tử, khi nhận đề tài đã đem lại nhiều khó khăn đối với tôi. Tuy nhiên, qua các buổi thảo
luận cũng như học thêm từ các tài liệu quý giá của Thầy, đã giúp cho tôi có cái nhìn cụ
thể hơn về nhiệm vụ của đề tài và có thêm phần cảm hứng trong lĩnh vực này.
Ngoài ra, xin được gửi lời cảm ơn đến tất cả các Thầy Cô trong khoa Điện - Điện
Tử, bộ môn Điện Tử đã truyền thụ kiến thức và kinh nghiệm của mình để giúp tôi có
thêm kiến thức về lĩnh vực điện tử và tự tin để thực hiện đề tài.
Bên cạnh đó tôi cũng xin cảm ơn đến các đồng nghiệp trong công ty Bosch RBVH/ESS4 đã hỗ trợ công việc để tôi có thêm thời gian hoàn thành đề tài này.
Cuối cùng, xin dành lời cảm ơn chân thành đến gia đình tôi, những người đã ở bên
cạnh động viên tôi vào những lúc khó khăn nhất.
Tp Hồ Chí Minh, tháng 6 năm 2019

Nguyễn Đức Hương Quỳnh

Lời cảm ơn

HVTH: Nguyễn Đức Hương Quỳnh


Luận văn thạc sĩ

ii

GVHD: TS. Trần Hoàng Linh

TÓM TẮT LUẬN VĂN

Trong nhưng năm gần đây, logic khả đảo đã được thúc đẩy phát triển bởi những
nghiên cứu lý thuyết và tính ứng dụng mà nó mang lại. Đặc biệt là trong thiết kế mạch
công suất thấp và tính toán lượng tử. Với động lực đó, các nhà nghiên cứu đã phát triển
ra nhiều thuật toán tổng hợp mạch khả đảo với nhiều cách tiếp cận khác nhau như Binary
Decision Diagram (BDD), transformation-based, cycle-based,... Một số phương pháp
tổng hợp một cách chính xác, một số dựa trên phương pháp suy nghiệm và một số khác
đáp ứng với các hàm ngõ vào.
Trong luận văn này sẽ trình bày các phương pháp tổng hợp các hàm boolean về dạng
EXOR-sums-Product-of-EXOR-sums (EPOE), và kết hợp với cổng Toffoli âm trong
quá trình hiện thực hóa mạch khả đảo. Mục tiêu của sự kết hợp này là làm giảm chi phí
lượng tử so với cách tổng hợp mạch chỉ sử dụng cổng Toffoli dương. Các bước tối ưu
hóa về thời gian tổng hợp mạch hay tối ưu hóa chi phí lượng tử hơn nữa có thể thực
hiện tiếp tục ở các nghiên cứu thiếp theo.

Tóm tăt luận văn

HVTH: Nguyễn Đức Hương Quỳnh


Luận văn thạc sĩ

GVHD: TS. Trần Hoàng Linh

3

ABSTRACT
Recently, the reversible logic has been promoted by research and application that it
brings. Especially in low power circuit design and quantum computing. With that
motivation, researchers have developed many reversible chcuit synthesis algorithms
with various approaches such as Binary Decision Diagram (BDD), transformationbased, cycle-based, and so on. Some methods synthesis are exact, some base on

heuristicc, and some rely on function representations.
This thesis will present an improvement of reversible chcuit sysnthesis algorithms
with single output boolean functions and multiple output boolean functions. These
functions is completely specific functions. We will combine the algorithms which
transforming functions into EXOR-sum of Products-of-EXOR-sums (EPOE) form and
the negative Toffoli gates. The purpose of this combination is reduce the quantum cost
compare with the classical EPOE algorithms which only use NOT gates and positive
Toffoli gates.

Tóm tăt luận văn

HVTH: Nguyễn Đức Hương Quỳnh


Luận văn thạc sĩ

GVHD: TS. Trần Hoàng Linh

iv

LỜI CAM ĐOAN
Tôi tên Nguyễn Đức Hương Quỳnh, là học viên cao học ngành Kỹ thuật Điện Tử tại
trường Đại học Bách Khoa, thành phố Hồ Chí Minh. Tôi xin cam đoan công trình nghiên
cứa ngày là do chính tôi thực hiện trong suốt quá trình thực hiện đề tài này, các tư liệu
tham khảo sử dụng được trích dẫn từ các nguồn thực tế, uy tín và chất lượng. Kết quả
thu được đươc thực hiện một cách độc lập và hoàn toàn trung thực.
Tp. Hồ Chí Minh, tháng 6 năm 2019

Nguyễn Đức Hương Quỳnh


Lời cam đoan

HVTH: Nguyễn Đức Hương Quỳnh


Luận văn thạc sĩ

GVHD: TS. Trần Hoàng Linh

V

MỤC LỤC

LỜI CẢM ƠN.............................................................................................................. i
TÓM TẮT LUẬN VĂN .............................................................................................. ii
ABSTRACT ................................................................................................................ iii
LỜI CAM ĐOAN ........................................................................................................ iv
MỤC LỤC .....................................................................................................................V
DANH SÁCH HÌNH VẼ........................................................................................... viii
DANH SÁCH BẢNG BIỂU ....................................................................................... X
DANH SÁCH CÁC TỪ VIẾT TẮT ........................................................................... xi
CHUƠNG 1: MỞ ĐẦU ................................................................................................ 1
1.1. Lý do chọn đề tài ....................................................................................... 1
1.2. Mục tiêu và nhiệm vụ của luận văn ........................................................... 2
1.3. Đối tượng và phạm vi nghiên cứu ............................................................. 2
1.4. ........................................................................................................ Ý
nghĩa khoa học và thực tiễn ......................................................................................... 3
CHUƠNG 2: TỔNG QUAN ........................................................................................ 4
2.1. Các khái niệm cơ bản ................................................................................ 4
2.1.1. Hàm khả đảo và mạch khả đảo ........................................................... 4

2.1.2. Các cổng khả đảo cơ bản .................................................................... 6
2.1.3. Đường Ancilla và Garbage ................................................................. 7
2.1.4. Chi phí lượng tử ................................................................................. 7
2.2. Các phương pháp tổng hợp mạch hiện tại ................................................. 8
2.2.1. Phương pháp transformation-based .................................................... 8
2.2.2. Phương pháp cycle-based ................................................................... 9
2.2.3. Phương pháp graphical [7] ............................................................... 10
2.2.4. Phương pháp tối ưu hóa mạch sửu dụng template matching............ 16
2.2.5. Phương pháp giảm chi phí trong mạch khả đảo Toffoli ................... 17
2.3. Hàm affine tuyến tính ............................................................................... 17
Mục lục

HVTH: Nguyễn Đức Hương Quỳnh


Luận văn thạc sĩ

vi

GVHD: TS. Trần Hoàng Linh

2.4. Các biểu thức Product-of-EXOR-sums (POE) và tập hỗ trợ................... 18
CHƯƠNG 3: TỔNG HỢP HÀM BOOLEAN HOÀN CHỈNH MỘT NGÕ RA ...... 19
3.1. Thuật toán tổng hợp mạch dạng EPOE ................................................... 19
3.1.1. Phương pháp template matching ..................................................... 19
3.1.2. Phương pháp tạo ra thư viện POE với N biến ngõ vào .................... 20
3.2. Thuật toán EPOEM-ls ............................................................................. 21
3.2.1. Thuật toán ......................................................................................... 21
3.2.2. Ví dụ ................................................................................................ 22
3.3. Thuật toán EPOEM-lf.............................................................................. 24

3.3.1. Thuật toán ......................................................................................... 24
3.3.2. Ví dụ ................................................................................................. 24
3.4. Kết quả thực nghiệm................................................................................ 26
CHƯƠNG 4: TÔNG HỢP MẠCH EPOE CHO HÀM KHÔNG HOÀN CHỈNH MỘT
NGÕ RA ..................................................................................................................... 28
4.1. Giới thiệu tổng quan ................................................................................ 28
4.2. Thuật toán EPOEM-l-DC ........................................................................ 28
4.2.1. Thuật toán ......................................................................................... 29
4.2.2. Ví dụ ................................................................................................. 29
4.3. Thuật toán EPOEM-l-DC-tree................................................................. 32
4.3.1. Thuật toán ......................................................................................... 32
4.3.2. Ví dụ ................................................................................................. 32
4.4. Kết quả thực nghiệm ............................................................................... 38
CHƯƠNG 5: TỔNG HỢP MẠCH EPOE CHO CÁC HÀM HOÀN CHỈNH ĐA NGÕ
RA............................................................................................................................... 40
5.1. Thuật toán EPOEM-MO-1 ...................................................................... 40
5.1.1. Bước 1 .............................................................................................. 41
5.1.2. Bước 2 .............................................................................................. 44
5.1.3. Bước 3 .............................................................................................. 46
5.1.4. Kết quả thực nghiệm ........................................................................ 50
5.2. Thuật toán EPOEM-MO-2 ...................................................................... 52

Mục lục

HVTH: Nguyễn Đức Hương Quỳnh


Luận văn thạc sĩ

vii


GVHD: TS. Trần Hoàng Linh

5.2.1. Tổng hợp dựa trên mạng lưới Exclusive-OR ................................... 52
5.2.2. Thuật toán EP0EM-M0-2 ................................................................. 55
5.2.3. Kết quả thực nghiệm ........................................................................ 60
CHƯƠNG 6: KẾT LUẬN .......................................................................................... 63
6.1. Kết luận .................................................................................................... 63
6.2. Hướng phát triển ...................................................................................... 63
PHỤ LỤC: BẢNG CHÚ THÍCH CÁC MẤU THỬ .............................................. 64
Tài Liệu Tham Khảo .................................................................................................. 67

Mục lục

HVTH: Nguyễn Đức Hương Quỳnh


Luận văn thạc sĩ

viii

GVHD: TS. Trần Hoàng Linh

DANH SÁCH HÌNH VẼ
Hình 2-1 Mạch khả đảo với cổng NOT, CNOT và Toffoli

5

Hình 2-2 Cổng NOT


6

Hình 2-3 a) cổng CNOT, b) cổng CNOT âm

6

Hình 2-4 a) cổng Toffoli, b) cổng Toffoli bán âm, c) cổng Toffoli âm

6

Hình 2-5 Cổng multicontrol Toffoli

6

Hình 2-6 4 cổng Toffoli cho cùng một vị trí XOR

12

Hình 2-7 Mạch khả đảo của hàm đã cho

16

Hình 3-1 Mạch khả đảo của hàm fa, b,c,d = a®d®a®b®ld®l®b®lc®la®d®l chỉ sử
dụng các cổng dương.

23

Hình 3-2 Mạch khả đảo của hàm fa, b,c,d = a®d®(a®b}d(&bca(&d có sử dụng cổng
âm


23

Hình 3-3 Mạch hiện thực hóa của hàm f chỉ sử dụng toàn cổng dương

25

Hình 3-4 Mạch hiện thực hóa của hàm f có kết hợp với cổng Toffoli bán âm và
CNOT âm

26

Hình 4-1 Quá trình so sánh giữa các template trên bìa Karnaugh

30

Hình 4-2 Quá trình biến đổi hàm qua các template được chọn

30

Hình 4-3 Quá trình biến đổi hàm qua các template được chọn

31

Hình 4-4 Quá trình biến đổi hàm khi sử dụng template a®bb®cc® d

31

Hình 4-5 Minh họa bằng bìa Karnaugh cho việc so sách giữa các template trong thuật
toán EPOEM-l-DC-tree ở level 1


34

Hình 4-6 Mịnh bằng bìa Karnaugh cho quá trình tìm kiếm template ở level 2 và level 3
35
Hình 4-7 Minh họa bằng bìa Karnaugh cho quá trình so sánh các template trong thuật
toán EPOEM-l-DC-tree ở level 2

36

Hình 4-8 Minh họa bằng bìa Karnaugh quá trình tìm tìm Check-set mới của các
template trong thuật toán EPOEM-1 -DC-tree

37

Hình 4-9 Minh họa bằng bìa Karnaugh quá trình so sánh giữa các template khác nhau
trong thuật toán EPOEM- 1-DC-tree ở level 3

38

Hình 5-1 Bảng sự thật minh họa sự chuyển đổi từ hàm đa ngõ ra sang các hàm một
Danh sách hình vẽ

HVTH: Nguyễn Đức Hương Quỳnh


Luận văn thạc sĩ

GVHD: TS. Trần Hoàng Linh

ix


ngõ ra của ví dụ 1.

42

Hình 5-2 Bảng sự thật minh họa sự chuyển đổi từ hàm đa ngõ ra sang các hàm một
ngõ ra của ví dụ 2.

44

Hình 5-3 Mạch của ví dụ 1 được tạo ra bời thuật toán EP0EM-M0-1 không thực hiện
chia sẻ biểu thức POE

47

Hình 5-4 Mạch của ví dụ 1 được tạo ra bời thuật toán EP0EM-M0-1 không thực hiện
chia sẻ biểu thức POE có sử dụng cổng Toffoli âm.

47

Hình 5-5 Mạch của ví dụ 1 được tạo ra bời thuật toán EP0EM-M0-1 áp dụng bước
chia sẻ biểu thức POE

48

Hình 5-6 Mạch của ví dụ 1 được tạo ra bời thuật toán EP0EM-M0-1 áp dụng bước
chia sẻ biểu thức POE có sử dụng cổng Toffoli âm

48


Hình 5-7 Mạch của ví dụ 2 được tạo ra bời thuật toán EP0EM-M0-1 áp dụng bước
chia sẻ biểu thức POE

50

Hình 5-8 Cây EXOR (Kiểu mạng lưới EXOR đặc biệt)

52

Hình 5-9 Biểu diễn bìa Karnaugh của các hàm ngõ ra A, B, c

53

Hình 5-10 Bìa Karnaugh thực hiện các hàm logic EXOR của chúng

54

Hình 5-11 Hiện thực hóa mạch có kết hợp cổng Toffoli âm

54

Hình 5-12 Mạch hoàn chỉnh của A, B và c

55

Hình 5-13 Ví dụ 1 hàm được dùng để tổng hợp EPOEM-MO-2

56

Hình 5-14 Sơ đồ cây EXOR của hàm ví dụ trong hình 5-13


57

Hìn-h 5-15 Thực hiện mạch của các hàm trong hình trong trường hợp không sử dụng
hàm (A®D)

59

Hình 5-16 Thực hiện mạch của các hàm trong hình trong trường hợp sử dụng hàm
(A©D)

Danh sách hình vẽ

60

HVTH: Nguyễn Đức Hương Quỳnh


Luận văn thạc sĩ

GVHD: TS. Trần Hoàng Linh

X

DANH SÁCH BẢNG BIỂU
Bảng 2-1 a) Hàm hoàn chỉnh một ngõ ra; b) hàm hoàn chỉnh đa ngõ ra

4

Bảng 2-2 Bảng sự thật của hàm khả đảo 3 biến


5

Bảng 2-3 Chi phí lượng tử của các cổng cơ bản

7

Bảng 2-4 Ví dụ về phương pháp transformation-based

8

Bảng 2-5 Ví dụ biểu diễn hàm khả đảo bằng các k-cycle

9

Bảng 2-6 Bảng sự thật của hàm khả đảo f

11

Bảng 2-7 s-maps của ngõ vào a,b và c

11

Bảng 2-8 smap của các ngõ ra X, y và z

11

Bảng 2-9 Bảng sự thật của cổng Toffoli t0-lp2p

12


Bảng 2-10 Các cổng Toffoli 3 biến và cặp hoán đổi của chúng

13

Bảng 2-11 Bảng tính điểm lần 1

14

Bảng 2-12 smaps sau khi sử dụng cổng T0-lp2p

14

Bảng 2-13 Bảng tính điểm lần 2

14

Bảng 2-14 smaps sau khi sử dụng cổng Tl-0p2p

15

Bảng 2-15 Bảng tính điểm lần 3

15

Bảng 2-16 smaps sau khi sử dụng cổng T0-lp2p

15

Bảng 3-1 Ví dụ về thư viện đơn thức và thư viện đa thức


21

Bảng 3-2 Kết quả thực nghiệm của thuật toán EPOEM-1

26

Bảng 4-1 Kết quả thực nghiệm của thuật toán EPOEM-1

39

Bảng 5-1 Danh sách các biểu thức POE được khởi tạo

46

Bảng 5-2 Tập POE phụ-1

47

Bảng 5-3 Danh sách các POE khởi tạo

49

Bảng 5-4 Kết quả thực nghiệm của thuật toán EPOEM-MO-1

51

Bảng 5-5 Các biểu thức EPOE của các hàm trong hình 5-14

57


Bảng 5-6 Chi phi lượng tử của các biểu thức EPOE

58

Bảng 5-7 Kết quả thực nghiệm của thuật toán EPOEM-MO-2

60

Danh sách bảng biểu

HVTH: Nguyễn Đức Hương Quỳnh


Luận văn thạc sĩ

GVHD: TS. Trần Hoàng Linh

xi

DANH SÁCH CÁC TỪ VIẾT TẮT

BDD - Binary Decision Diagram
CMOS - Complementary Metal-Oxide-Semiconductor
ESOP - Exclusive-Or-Sum-of-Products
EPOE - EXOR-sum of Products-of-EXOR-sums
EPOEM - EXOR-sum of Products-of-EXOR-sums Method
EPOEM-MO - EXOR-sum of Products-of-EXOR-sums Method-Multiple Output
EPOEM-ls - EPOEM-1 single library
EPOEM-lf- EPOEM-1 full library

EPOEM-l-DC - EPOEM-1- Don’t care
PPRM - Possitive Polarity Read-Muller

Danh sách các từ viêt tăt

HVTH: Nguyễn Đức Hương Quỳnh


Luận văn thạc sĩ

GVHD: TS. Trần Hoàng Linh

1

CHƯƠNG 1: MỞ ĐẦU
1.1. Lý do chọn đề tài
Trong những năm gần đây, các mạch logic khả đảo đã được thúc đẩy phát triển
bời những nghiên cứu lý thuyết trong mạch điện tử công suất thấp cũng như sự cải tiến
thực tế của biến đổi điều khiển bit trong kỹ thuật mã hóa và đồ họa máy tính. Gần đây,
các mạch khả đảo đã thu hút được sự chú ý và được xem như các thành phần của các
thuật toán lượng tử, cũng như trong lượng tử ánh sáng và các công nghệ tính toán nano,
nơi mà các thiết bị chuyển mạch không cần độ lợi tín hiệu. Các nghiên cứu về logic khả
đảo thường được phân biệt giữa tổng hợp mạch, tối ưu sau khi tổng hợp mạch và công
nghệ ánh xạ.
Logic khả đảo là một lĩnh vực nghiên cứu cấp thiết. Điểm thú vị trong logic khả
đảo là các ứng dụng của nó trong tính toán lượng tử, CMOS công suất thấp, công nghệ
nano, và tính toán quang. Kiến trúc duy nhất của mạch khả đảo là dạng cascade của các
cổng khả đảo [ 1].
Với sự phát triển không ngừng của khoa học công nghệ, tính toán lượng tử đã
trở thành một công cụ hỗ trợ hết sức mạnh mẽ cho các nhà khoa học, một số ứng dụng

tuyệt vời của tính toán lượng tử như Machine Learning, giải quyết các bài toán tối ưu
vận tải, mô phỏng y sinh và các dịch vụ tài chính [2].
Tuy đây không phải là một chủ đề mới nhưng do các ứng dụng của nó nền vẫn
luôn thu hút được các nhà nghiên cứu. Một số thuật toán tổng hợp mạch khả đảo đã
được nghiên cứu và phát triển điển hình như search-based, cycle-based, transformationbased và BDD-based, cũng như các thuật toán tổng hợp đặc biệt khác, chúng đều là
thuật toán chính xác và suy nghiệm. Nhưng dù là cách tiếp cận nào đi nữa thì mục đích
cuối cùng cũng là để có được một giải thuật tổng hợp ra mạch khả đảo tối ưu nhất, có
thể là về chi phí, kích thước mạch hay là về thời gian tổng hợp.
Do đó, việc chọn đề tài “Thuật toán tổng hợp mạch khả đảo đa ngỏ ra hoàn
chỉnh” nhằm mục đích kế thừa và phát triển các thuật toán tổng hợp mạch khả đảo đến
mức tối ưu nhất có thể, làm tăng thêm sự phong phú về thuật toán trong lĩnh vực này.

Chương 1: Mở đầu

HVTH: Nguyễn Đức Hương Quỳnh


Luận văn thạc sĩ

2

GVHD: TS. Trần Hoàng Linh

1.2. Mục tiêu và nhiệm vụ của luận vãn
Các kiến thức và kết quả cần đạt được ở đề tài này là:
• Tìm hiểu và phân tích một số thuật toán tổng hợp mạch phổ biến và có liên quan
đến đề tài. Thu thập các tài liệu về lý thuyết mạch khả đảo, các phương pháp
tổng hợp mạch khả đảo trước đây.
• Tìm hiểu và nghiên cứu cách tổng hợp mạch của giải pháp EPOE đối với hàm
boolean một ngõ ra và đa ngõ ra hoàn chỉnh. Kết hợp với các cổng lượng tử âm

như: CNOT âm, Toffoli bán âm và Toffoli âm nhằm làm giảm số lượng cổng sử
dụng và giảm chi phí lượng tử của mạch.
• Dựa trên các thuật toán đã nghiên cứu để xây dựng nên công cụ tổng hợp mạch,
nhằm mục đích kiểm chứng và đo lường các thông số đánh giá thuật toán.
• Tiến hành thử nghiệm và đo đạc các mẫu thử để xác định các thông số liên quan,
đặc biệt là chi phí lượng tử để so sánh với các thuật toán trước đây. Thực hiện
việc tối ưu hoá trong và sau khi tổng hợp để cải tiến thuật toán hơn nếu thời gian
cho phép.
1.3. Đối tượng và phạm vỉ nghiên cứu
Đối tượng nghiên cứu của đề tài: Các nghiên cứu của đề tài nhằm tối ưu hóa
các thuật toán tổng hợp mạch cho các hàm boolean hoàn chỉnh bằng cách kết hợp nhiều
thuật toán đã có sẵn lại với nhau. Đưa ra phương thức chuyển đổi hàm logic khả đảo đa
ngõ ra hoàn chỉnh cho hàm âm để cho ra các thuật toán có thể tổng hợp với chi phí thấp
nhất có thể và thời gian nhanh nhất có thể. Đối tượng nghiên cứu của đề tài là:
• Ket hợp phương pháp tổng hợp trước đây và tính chất hoán đổi của cổng CNOT,
CNOT âm, Toffoli, Toffoli âm để tạo ra một thuật toán tổng hợp mạch khả đảo
hàm âm EPOE đối với hàm âm.
• Chuyển đổi từ hàm boolean hoàn chỉnh đa ngõ ra sang hàm boolean hoàn chỉnh
đơn ngõ ra để xây dựng nên một thuật toán tổng hợp mạch khả đảo âm áp dụng
cho các hàm logic đa ngõ ra hoàn chỉnh.
• Tạo ra một thuật toán tổng hợp mạch khả đảo âm với thời gian tổng hợp nhanh, ổn
định và chi phí hợp lí.
Phạm vi nghiên cứu: Phạm vi nghiên cứu của đề tài sẽ xây dựng được thuật toán
Chương 1: Mở đầu

HVTH: Nguyễn Đức Hương Quỳnh


Luận văn thạc sĩ


GVHD: TS. Trần Hoàng Linh

3

đã nêu phía trên. Xây dựng công cụ tổng hợp mạch khả đảo dựa trên thuật toán đã nghiên
cứu thành công. Kết quả thí nghiệm đo đạt được sẽ so sánh với các kết quả ở các thuật
toán cùng loại để đánh giá tính khả dụng của giải thuật.
1.4. Ý nghĩa khoa học và thực tiễn
Ý nghĩa khoa học:
Chủ đề logic khả đảo tuy đã xuất hiện khá lâu nhưng vẫn còn mới ở trong nước.
Việc tìm hiểu và nghiên cứu về các thuật toán tổng hợp mạch khả đảo này giúp người
đọc có thêm sự hiểu biết về lĩnh vực này, đặc biệt là các nhà nghiên cứu trong nước.
Đưa ra phương pháp giúp tổng hợp mạch khả đảo một cách nhanh nhất có thể.
Ngoài ra, còn giúp cho người đọc có thêm một hướng nghiên cứu mới về sự kết hợp
giữa các phương pháp tổng hợp mạch đã có sẵn.
Ý nghĩa thực tiễn:
Luận văn đưa ra một thuật toán tổng hợp mới với sự kết hợp của phương pháp
EPOE và tính chất hoán đổi của cổng Toffoli bán âm, Toffoli âm, góp phần tối ưu hóa
về thời gian tổng hợp mạch. Đồng thời cũng đưa ra thêm một sự lựa chọn khi tổng hợp
mạch. Tùy theo yêu cầu của ứng dụng mà các nhà thiết kế có thể lựa chọn thuật toán
tổng hợp mạch phù hợp.

Chương 1: Mở đầu

HVTH: Nguyễn Đức Hương Quỳnh


Luận văn thạc sĩ

4


GVHD: TS. Trần Hoàng Linh

CHƯƠNG 2: TỔNG QUAN
2.1. Các khái niệm cơ bản
2.1.1. Hàm khả đảo và mạch khả đảo
Hàm boolean hoàn chỉnh là một hàm boolean mà ở tất cả các giá trị của ngõ vào
đều có giá trị của ngõ ra tương ứng. Trong luận văn này, hàm boolean hoàn chỉnh là đối
tượng chính trong việc tổng hợp mạch và được chia làm hai loại dựa theo số ngõ ra. Hai
loại đó là hàm boolean hoàn chỉnh một ngõ ra, sẽ được gọi tắt là là hàm một ngõ ra, và
hàm boolean hoàn chỉnh đa ngõ ra, sẽ được gọi tắt là hàm đa ngõ ra. Một ví dụ về hàm
boolean hoàn chỉnh được thể hiện trong Bảng 2-1.
Bảng 2-1 a) Hàm hoàn chỉnh một ngõ ra; b) hàm hoàn chỉnh đa ngõ ra
a)
Ngõ vào
a
b
c

b)
Ngõ ra
F

Ngõ vào
a
b
c

Ngõ ra
fl

f0

0
0
0
0
0
0
0
1
1
0
0
1
0
0
0
1
0
1
0
1
0
1
0
1
0
0
1
0

1
1
0
0
1
1
1
0
1
0
0
1
1
0
0
0
0
1
0
1
1
1
0
1
1
1
1
1
0
1

1
1
0
1
0
1
1
1
1
1
1
0
0
0
Với các hàm có số biến ngõ vào nhỏ thì có thể thể hiện bằng bảng sự thật cũng như bìa
Kanaugh. Tuy nhiên với các hàm có số biến ngõ vào lớn thì việc thể hiện như thế rất bất
tiện và gây khó khăn cho người đọc. Vì vậy, để dễ dàng theo dõi, các hàm trong luận
văn này sẽ được quy ước cách viết như sau:
•

Đối với hàm f trong ví dụ ở Bảng 2-la, f(a, b, c) = m(2, 4, 5, 6)

•

Đối với hàm Y1 và YO trong ví dụ ở Bảng 2-lb, fl(a, b, c) = m(0, 3, 5, 6) và f2(a,
b, c) = m(0, 1, 2, 5).

Chương 2

HVTH: Nguyễn Đức Hương Quỳnh



Luận văn thạc sĩ

GVHD: TS. Trần Hoàng Linh

5

Hàm boolean không hoàn chỉnh là một hàm boolean có các giá trị tùy định ở ngõ
ra. Và hàm boolean không hoàn chỉnh này cũng được chia ra thành hai loại dưa theo số
ngõ ra. Tuy nhiên, đây không phải là đối tượng chính trong luận văn này nên sẽ không
được đề cập nhiều.
Hàm khả đảo là một hàm boolean có số ngõ ra bằng với số ngõ vào và ánh xạ giữa
ngõ ra và ngõ vào là 1-1. Hàm khả đảo n biến là một hàm khả đảo có n ngõ vào và n
ngõ ra. Bảng 2-2 là một ví dụ về hàm khả đảo 3 biến:
Bảng 2-2 Bảng sự thật của hàm khả đảo 3 biến
Ngõ vào
Ngõ ra
a
b
c
f2
fl
f0
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
1
0
0
1
0
0


0
0
1
0
0
1
1
1

0
1
0
1
0
1
0
1

Và biểu diễn ở dạng công thức theo quy ước của các hàm f2, f 1 và fo lần lượt là:
•

f2(a, b, c) = m(0, 1, 2, 5)

•

fl(a, b, c) = m(2, 5, 6, 7)

•

fO(a, b, c) = m(l, 3, 5, 7)


Mạch khả đảo là mạch hiện thực hóa của hàm khả đảo. Trong logic khả đảo cổ
điển, mỗi cặp ngõ vào/ngõ ra thường được gọi là một đường hoặc một dây, trong khi ở
logic lượng tử, nó được gọi là một qubit. Một ví dụ về mạch khả đảo được thể hiện trong
Hình 2-1.
x2

*2

x2

*2

*1
*1

*1

%O©*1

CD x° c

x0

Q

ỳ-

Q


I *1 r I *1
KI? A1A 2

Hình 2-1 Mạch khả đảo với cống NOT, CNOT và Toffoli

Chương 2

HVTH: Nguyễn Đức Hương Quỳnh


Luận văn thạc sĩ

GVHD: TS. Trần Hoàng Linh

6

2.1.2. Các cổng khả đảo cơ bản
Một số cổng khả đảo cơ bản thường được sử dụng như:
x

*

• NOT: (%) -> (%)
Hình 2-2 Cổng NOT
• CNOT: (%; y) -* (%; y ® %)
1 ------------ • ----------- %!

%

%!


0 —Q— %0® i

%

x

%0®xi

a
b

Hình 2-3 a) cổng CNOT, b) cổng CNOT
âm
• Toffoli: (%, y; z) -> (x, y;z © xy)
x2

•

x2

x2

X1

X1

%0®X1%2

XQ®X1X2


XQ®X1X2

Hình 2-4 a) cổng Toffoli, b) cổng Toffoli bán âm, c) cổng Toffoli âm

Multicontrol Toffoli:
xn

xn
xn-l

*1

X1

-0- xo©x.
•1 ■■■ xn-lxn
Hình 2-5 Cổng multicontrol Toffoli
Xo

Chương 2

HVTH: Nguyễn Đức Hương Quỳnh


Luận văn thạc sĩ

7

GVHD: TS. Trần Hoàng Linh


2.1.3. Đường Ancilla và Garbage
Có 2nỉ hàm khả đảo phân biệt n biến với các hoán vị của 2n phần tử. Tuy nhiên,
cũng tồn tại 2P=1(2Ể)21 — 2n2" hàm không khả đảo từ 1 đến n ngõ ra. Để chuyển đổi các
hàm đó thành hàm khả đảo cần phải thêm các ngõ vào/ ngõ ra. Các đường thêm vào ở
ngõ vào được gọi là đường anciỉỉa và thường là hằng số 0 hoặc 1. Các đường ancilla mà
giá trị của nó không bị đặt lại thành một hằng số ở cuối quá trình tính toán được gọi là
các đường garbage. Ngõ ra của các đường ancilla không bị ràng buộc trong bảng sự
thật được gọi là tùy định (DC). Với một hàm bất khả đảo có số tổ hợp của mỗi ngõ ra
có thể được lặp lại đến M lần, thì cần g = ịlog2M] đường ancilla để xây dựng được mạch
khả đảo [3].
2.1.4. Chi phí lượng tử
Chi phí lượng tử là một thông số đo lường quan trọng trong việc so sánh các
mạch khả đảo. Chi phí lượng tử của một cổng được định nghĩa như là số lượng các
lượng tử cơ bản cần thiết để tạo nên cổng đó [1]. Chi phí lượng tử của một cổng n-bit
Toffoli âm với ít nhất một đường điều khiển dương bằng với chi phí của một cổng nbit Toffoli. Nếu tất cả các đường điều khiển điều là âm thì chi phí lượng tử sẽ phải cộng
thêm 2 [1].
Chi phí lượng tử của một mạch được định nghĩa là tổng chi phí của tất cả các
cổng trong mạch. Trong đó, chi phí các cổng cơ bản được định nghĩa trong bảng 2-3.
Bảng 2-3 Chi phí lượng tử của các cổng cơ bản
Tên cổng
NOT
CNOT
CNOT âm
Toffoli
Toffoli bán âm
Toffoli âm
NxN Toffoli (bán âm)
NxN Toffoli âm
2.2. Các phương pháp tổng họp mạch hiện tại


Chương 2

Chi phí
1
1
3
5
5
7
N
2 -3
2N - 1

HVTH: Nguyễn Đức Hương Quỳnh


Luận văn thạc sĩ

8

GVHD: TS. Trần Hoàng Linh

2.2.1. Phương pháp transformation-based
Phương pháp transformation-based lần đầu được đưa ra bởi Miller et al [4] dựa
trên sự tương quan giữa ngõ vào và ngõ ra trong bảng sự thật. Các thuật toán dựa trên
phương pháp này sẽ quét qua tất cả các hàng trong bảng sự thật, tìm kiếm sự khác biệt
giữa các ngõ vào và ngõ ra, và sửa chữa các điểm khác biệt đó bằng cách áp dụng các
cổng multicontrol Toffoli nhưng chỉ với các điều khiển dương [5]. Một ví dụ về phương
pháp này được miêu tả ở bảng 2-4:

Bảng 2-4 Ví dụ về phương pháp transformation-based
Ngõ vào Ngõ ra 1
2
3
4
5
6
7
stt
abc
xyz xyz xyz xyz xyz xyz xyz xyz
0
000
011 010 000 000 000 000 000 000
1
001
000 000 010 011 001 001 001 001
2
010
101 101 111 110 110 010 010 010
3
011
010 011 001 001 011 111 011 011
4
100
001 001 011 010 010 110 110 100
5
101
111 110 100 100 100 100 100 110
6

110
110 111 101 101 111 011 111 101
7
111
100 100 110 111 101 101 101 111

8
9
xyz xyz
000 000
001 001
010 010
011 011
100 100
111 101
101 111
110 110

1) Ở hàng 0, ngõ vào và ngõ ra khác nhau 2 bit, nên sử dụng 1 cổng CNOT (y;z) để
thay đổi bit thấp nhất từ 1 thành 0. Các giá trị in đậm là các giá trị ngõ ra sẽ bị
thay đổi theo. Kết quả sau khi qua cổng CNOT được thể hiện ở cột 1.
2) Lúc này hàng 0 chỉ còn lại bit thứ y là 1 nên sử dụng 1 cổng NOT (y) để chuyển
bit này về 0. Kết quả được thể hiện ở cột 2.
3) Ngõ ra ở hàng 0 đã giống với ngõ vào, nên ở bước này cần chọn cổng mà không
làm ảnh hưởng đến hàng 0. Ỏ hàng 1, cần chuyển đổi bit z thành 1 trước nên
cổng CNOT (y;z) được chọn. Kết quả được thể hiện ở cột 3.
4) Lúc này cần chuyển bit y ở hàng 1 về 0, cổng CNOT (z;y) được chọn.
5) Tiếp tục lặp lại như các bước trên cho đến cột 5, bit X ở hàng 3 cần phải chuyển
về 0, vì để không ảnh hưởng đến các hàng trên nên cổng Toffoli (y,z;x) được
chọn.

6) Như vậy, cứ lặp lại từng hàng cho đến khi ngõ ra giống với ngõ vào. Lúc này chỉ
cần viết lại các cổng từ cột 1 đến cột 9 theo chiều từ phải sang trái. Lý do phải
viết ngược lại là vì thuật toán này đang biến đổi ngõ ra sao cho giống với ngõ
vào, nên để từ ngõ vào thành ngõ ra, mạch phải được đảo lại.
Thuật toán này được cải tiến bời Maslov, tác giả tổng hợp mạch một cách trực
tiếp bởi sự phức tạp của phổ Reed-Muller thay vì sử dụng khoảng cách Hamming. Cổng

Chương 2

HVTH: Nguyễn Đức Hương Quỳnh


Luận văn thạc sĩ

GVHD: TS. Trần Hoàng Linh

9

Toffoli với cả hai điều khiển âm và dương đều được áp dụng. Sau khi tổng hợp mạch
thì có thể tối ưu bởi các template của cổng Toffoli [3].
2.2.2. Phương pháp cycle-based
Một số khái niệm cơ bản trong phương pháp cycle-based:
Cycle là một tâp hoán vị (Ọp a2,..., dfc) mà trong đó /(ai) = a2,/(a2) = a3,..., f(ak)
= di. Chiều dài của một cycle được tính bằng số phần tử trong tập hoán vị của cycle đó.
Một cycle có chiều dài k được gọi là k-cycle. Với cycle có chiều dài bằng 2 được gọi là
một transposition.
Hai cycle được gọi là phân biệt (disjoint) nếu chúng không có chung bất kì một
phần tử nào. Và hai cycle phân biệt có thể hoán đổi vị trí cho nhau. Ví dụ (1, 2)(3, 4) =
(3, 4)(1, 2). Tính chất hoán đổi này sẽ không còn đúng nếu hai cycle có ít nhất một phần
tử chung [3].

Ngoài ra, một cycle có thể được viết theo nhiều cách khác nhau bằng cách thay
đổi vị trí các phần tử trong cycle một cách tuần tự. Ví dụ như cycle (1, 2, 3) còn có thể
được viết theo cách khác là (2, 3, 1) hay (3,1,2) [6].
Biểu diễn hàm bằng các k-cycle: Ngoài cách biểu diễn hàm khả đảo bằng bảng
sự thật thì có thể sử dụng cách biểu diễn bằng k-cycle. Với số biến càng lớn thì kích
thước của bảng sự thật càng lớn nên biểu diễn bằng các k-cycle là một sự lựa chọn dễ
nhìn hơn. Ví dụ như hàm khả đảo f có 3 biến như sau:
Bảng 2-5 Ví dụ biểu diễn hàm khả đảo bằng các k-cycle
Ngõ vào
Ngõ ra
a
b
c
y
X
0
0
0
0
0
0
1
0
0
1
1
0
2
0
1

0
1
0
3
0
1
1
0
1
4
1
0
0
1
1
5
1
0
1
0
1
6
1
1
0
1
1
7
1
1

1
0
0
f = (1,4,7)(2,5)

z
0
0
1
1
1
0
0
1

0
4
5
3
7
2
6
1

Trong khi phương pháp transformation-based tập trung vào mỗi giá trị riêng lẻ

Chương 2

HVTH: Nguyễn Đức Hương Quỳnh



Luận văn thạc sĩ

GVHD: TS. Trần Hoàng Linh

10

của ngõ vào so với ngõ ra, thì phương pháp cycle-based tập trung vào các cycles khi
ngõ ra được chuyển về lại thành ngõ vào. Ví dụ như với một cổng Toffoli 3 biến a, b, c
với a là bit cao nhất, T(a,b;c) thì sẽ tạo thành một transposition (6,7). Điều này có nghĩa
là nếu ngõ vào là 6 thì ngõ ra sẽ là 7 và ngược lại, nếu ngõ vào là 7 thì ngõ ra tương ứng
sẽ là 6.
Các thuật toán của phương pháp cycle-based này tập trung ở việc phân tách các
k-cycle có chiều dài lớn thành các 2-cycles, 3-cycles,.. .Phần xử lí phía sau phụ thuộc
vào các công thức tính toán của riêng mỗi thuật toán.
Yêu cầu để sử dụng được phương pháp cycle-based là hàm đưa vào phải là một
hàm khả đảo hoàn chỉnh.
2.2.3. Phương pháp graphical [7]
Phương pháp này dựa trên tính chất hoán đổi của cổng Toffoli để tổng hợp mạch.
Để chọn là cổng tối ưu nhất, tác giả đã sử dụng s-maps để đo các thông số tối ưu, từ đó
lựa chọn cổng tối ưu nhất có thể. Các bước thực hiện thuật toán này như sau:
Xây dựng s-maps: s-map của bit thứ i là một bảng có 2 hàng và có 2n_1 cột với
n là số biến của ngõ vào cũng như ngõ ra. Hàng phía trên là hàng chứa các giá trị của
ngõ ra mà tại đó, bit thứ i của ngõ vào tương ứng bằng 0, và ngược lại hàng phía dưới
chứa các giá trị của ngõ ra mà tại đó, bit thứ i của ngõ vào tương ứng bằng 1. Ví dụ, cho
hàm khả đảo f với bảng sự thật như sau:

Chương 2

HVTH: Nguyễn Đức Hương Quỳnh



Luận văn thạc sĩ

GVHD: TS. Trần Hoàng Linh

11

Bảng 2-6 Bảng sự thật của hàm khả đảo f
Ngõ vào
a
b
c
X
0
0
0
0
0
1
0
0
1
0
2
0
1
0
0
3

0
1
1
0
4
1
0
0
1
5
1
0
1
1
6
1
1
0
1
7
1
1
1
1

Ngõ ra
y
1
1
0

0
0
1
0
1

z
0
1
0
1
0
0
1
1

2
3
0
1
4
6
5
7

Vẽ s-map cho bit a gồm 2 hàng và 4 cột. Ở hàng trên điền từ trái sang phải các
giá trị thập phân của ngõ vào mà bit a bằng 0, và điền các giá trị còn lại ở hàng dưới.
Tương tự cho các s-map của bít b và c như hình 2-7.
Bảng 2-7 s-maps của ngõ vào a,b và c
b


a
0
4
1

1
5
k

2
6
j

3
7
i

c

0
2

1
3

4

5


6

h

g

f

2
3

4

7

0
1

5

6
7

e

d

c

b


a

Thay các giá trị thập phân trong mỗi bảng bằng giá trị thập phân tương ứng ở
ngõ ra. Ví dụ với ngõ vào là 2 thì ngõ ra là 5, thực hiện thay thế số 2 trong tất cả các smap từ 2 thành 5. Thực hiện tương tượng cho các giá trị còn lại để được s-maps của ngõ
ra như hình 2-8. So sánh với s-maps của ngõ vào, nếu các giá trị nào của ngõ ra nằm
không đúng hàng thì sẽ bị tô đen. Các ô đã đúng hàng thì không tô màu.
Bảng 2-8 smap của các ngõ ra X, y và z
X
2
4
1

3
6
k

Chương 2

z

y
0
5
j

1
7
i


2
0
h

3
1
g

4
5
f

6
7
e

2
3
d

0
1
c

4
6
b

5
7

a

HVTH: Nguyễn Đức Hương Quỳnh