Luận văn thạc sĩ về thuật toán tổng hợp mạch khả đảo đa ngõ ra trong kỹ thuật điện tử

Khám phá luận văn thạc sĩ về kỹ thuật điện tử, tập trung vào thuật toán tổng hợp mạch khả đảo đa ngõ ra hoàn chỉnh và ứng dụng thực tiễn.

• Tác giả: Nguyễn Đức Hương Quỳnh
• Người hướng dẫn: TS. Trần Hoàng Linh
• Trường học: Đại học Bách Khoa
• Chuyên ngành: Kỹ thuật Điện Tử
• Đề tài: Thuật Toán Tổng Hợp Mạch Khả Đảo Đa Ngõ Ra Hoàn Chỉnh
• Loại tài liệu: luận văn thạc sĩ
• Năm xuất bản: 2019
• Địa điểm: TP. Hồ Chí Minh

Tóm tắt

I. Giới thiệu về thuật toán tổng hợp mạch khả đảo

Thuật toán tổng hợp mạch khả đảo là một lĩnh vực nghiên cứu quan trọng trong kỹ thuật điện tử, đặc biệt là trong thiết kế mạch logic. Thuật toán tổng hợp giúp chuyển đổi các hàm boolean thành các mạch khả đảo, từ đó tối ưu hóa chi phí và hiệu suất. Mạch khả đảo có khả năng thực hiện các phép toán mà không mất thông tin, điều này rất quan trọng trong các ứng dụng tính toán lượng tử và thiết kế mạch logic. Việc nghiên cứu và phát triển các thuật toán tổng hợp mới là cần thiết để cải thiện hiệu suất và giảm chi phí của các mạch này. Đặc biệt, trong bối cảnh công nghệ hiện đại, nhu cầu về các mạch điện tử có khả năng tiêu thụ năng lượng thấp và hiệu quả cao ngày càng gia tăng. Các mạch khả đảo có thể được sử dụng trong nhiều lĩnh vực khác nhau, từ điện tử tiêu dùng đến các hệ thống tính toán phức tạp.

1.1. Mục tiêu nghiên cứu

Mục tiêu của nghiên cứu này là phát triển một thuật toán tổng hợp cho mạch khả đảo đa ngõ ra, nhằm tối ưu hóa chi phí lượng tử và thời gian tổng hợp. Nghiên cứu sẽ tập trung vào việc xây dựng các công cụ tổng hợp mạch dựa trên thuật toán mới, từ đó đánh giá hiệu suất của các phương pháp tổng hợp hiện tại. Việc tối ưu hóa này không chỉ giúp giảm thiểu chi phí mà còn cải thiện hiệu suất tổng thể của các mạch khả đảo. Hơn nữa, nghiên cứu sẽ cung cấp các phương pháp mới trong việc xử lý các hàm boolean phức tạp, góp phần nâng cao khả năng ứng dụng của thuật toán tổng hợp trong thực tế.

II. Các phương pháp tổng hợp mạch hiện tại

Hiện nay, có nhiều phương pháp tổng hợp mạch khả đảo khác nhau, bao gồm phương pháp transformation-based, cycle-based, và Binary Decision Diagram (BDD). Mỗi phương pháp đều có những ưu điểm và nhược điểm riêng. Phương pháp transformation-based thường được sử dụng để chuyển đổi các hàm boolean thành các dạng dễ xử lý hơn, trong khi phương pháp cycle-based tập trung vào việc tối ưu hóa các chu trình trong mạch. BDD là một công cụ mạnh mẽ giúp biểu diễn các hàm boolean một cách hiệu quả và dễ dàng hơn trong việc thực hiện các phép toán logic. Tuy nhiên, các phương pháp này vẫn còn tồn tại những hạn chế, đặc biệt là khi áp dụng cho các hàm boolean có số ngõ ra lớn. Nghiên cứu này sẽ đề xuất các cải tiến cho các phương pháp hiện tại, nhằm nâng cao khả năng tổng hợp mạch khả đảo đa ngõ ra.

2.1. Phương pháp transformation based

Phương pháp transformation-based là một trong những phương pháp phổ biến nhất trong tổng hợp mạch khả đảo. Phương pháp này dựa trên nguyên tắc biến đổi các hàm boolean thành các dạng dễ xử lý hơn, giúp đơn giản hóa quá trình tổng hợp mạch. Một trong những ưu điểm của phương pháp này là khả năng tối ưu hóa chi phí lượng tử, giúp giảm thiểu số lượng cổng cần thiết trong mạch. Tuy nhiên, phương pháp này cũng có những hạn chế nhất định, đặc biệt là khi áp dụng cho các hàm boolean phức tạp với nhiều ngõ ra. Nghiên cứu này sẽ phân tích sâu hơn về phương pháp transformation-based và đề xuất các cải tiến nhằm nâng cao hiệu suất tổng hợp mạch.

III. Kết quả thực nghiệm và phân tích

Trong nghiên cứu này, các thuật toán tổng hợp mạch khả đảo đã được thử nghiệm trên nhiều mẫu hàm boolean khác nhau. Kết quả cho thấy rằng thuật toán mới phát triển có khả năng tổng hợp mạch với chi phí lượng tử thấp hơn so với các phương pháp hiện tại. Đặc biệt, việc sử dụng cổng Toffoli âm trong quá trình tổng hợp đã giúp giảm thiểu số lượng cổng cần thiết, từ đó tối ưu hóa chi phí tổng thể của mạch. Các kết quả thực nghiệm cũng cho thấy rằng thời gian tổng hợp mạch đã được cải thiện đáng kể, cho phép thực hiện nhanh chóng và hiệu quả hơn. Những kết quả này không chỉ khẳng định tính khả thi của thuật toán tổng hợp mới mà còn mở ra hướng đi mới trong nghiên cứu và phát triển các mạch khả đảo.

3.1. Đánh giá hiệu suất

Đánh giá hiệu suất của thuật toán tổng hợp mạch khả đảo mới cho thấy sự cải thiện rõ rệt về chi phí và thời gian tổng hợp. Các thử nghiệm đã chỉ ra rằng thuật toán mới không chỉ giảm thiểu số lượng cổng cần thiết mà còn tối ưu hóa chi phí lượng tử, từ đó nâng cao hiệu suất tổng thể của mạch. Việc so sánh với các phương pháp hiện tại cho thấy rằng thuật toán mới có thể tổng hợp các hàm boolean phức tạp một cách hiệu quả hơn, đồng thời giữ được tính khả đảo của mạch. Những kết quả này chứng minh rằng việc áp dụng các cải tiến trong thuật toán tổng hợp có thể mang lại lợi ích lớn trong thực tế, đặc biệt trong các ứng dụng yêu cầu hiệu suất cao và chi phí thấp.

IV. Hướng phát triển tương lai

Nghiên cứu về thuật toán tổng hợp mạch khả đảo vẫn còn nhiều tiềm năng để phát triển. Các hướng nghiên cứu tương lai có thể bao gồm việc mở rộng các thuật toán hiện tại để xử lý các hàm boolean phức tạp hơn, hoặc phát triển các công cụ tổng hợp mạch tự động hóa hoàn toàn. Hơn nữa, việc tích hợp các công nghệ mới như trí tuệ nhân tạo và học máy vào quá trình tổng hợp mạch có thể mở ra những khả năng mới trong việc tối ưu hóa chi phí và hiệu suất. Những nghiên cứu này không chỉ góp phần nâng cao hiểu biết về mạch khả đảo mà còn tạo ra những ứng dụng thực tiễn trong lĩnh vực điện tử và tính toán lượng tử.

4.1. Tích hợp công nghệ mới

Tích hợp các công nghệ mới vào thuật toán tổng hợp mạch khả đảo có thể mang lại nhiều lợi ích. Việc sử dụng trí tuệ nhân tạo và học máy để tối ưu hóa quá trình tổng hợp có thể giúp cải thiện đáng kể hiệu suất và giảm thiểu chi phí. Những công nghệ này có khả năng phân tích và xử lý các hàm boolean phức tạp một cách nhanh chóng và hiệu quả, từ đó tạo ra các mạch khả đảo tối ưu hơn. Hướng nghiên cứu này không chỉ giúp nâng cao khả năng tổng hợp mà còn mở ra cơ hội mới cho các ứng dụng trong lĩnh vực điện tử và tính toán lượng tử.

Trích đoạn nội dung tài liệu

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. Các khái niệm cơ bản 2. 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) b) Ngõ vào Ngõ ra Ngõ vào Ngõ ra a b c F a b c f1 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 0 1 1 1 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-1a, f(a, b, c) = m(2, 4, 5, 6)  Đối với hàm Y1 và Y0 trong ví dụ ở Bảng 2-1b, f1(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ĩ 5 GVHD: TS. Trần Hoàng Linh 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 f1 f0 0 0 0 1 0 0 0 0 1 1 0 1 0 1 0 1 1 0 0 1 1 0 0 1 1 0 0 0 0 0 1 0 1 1 1 1 1 1 0 0 1 0 1 1 1 0 1 1 Và biểu diễn ở dạng công thức theo quy ước của các hàm f2, f1 và f0 lần lượt là:  f2(a, b, c) = m(0, 1, 2, 5)  f1(a, b, c) = m(2, 5, 6, 7)  f0(a, b, c) = m(1, 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. 𝑥2 𝑥2 𝑥2 𝑥2 𝑥1 𝑥1 𝑥1 𝑥1 𝑥0 𝑥0 ⨁𝑥1 𝑥0 𝑥0 ⨁𝑥1 ⨁𝑥1 𝑥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ĩ 6 GVHD: TS.

Trần Hoàng Linh 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ư: 𝑥 𝑥̅  NOT: (𝑥) → (𝑥̅ ) Hình 2-2 Cổng NOT  CNOT: (𝑥; 𝑦) → (𝑥; 𝑦 ⊕ 𝑥) 𝑥1 𝑥1 𝑥1 𝑥1 𝑥0 𝑥0 ⨁𝑥1 𝑥0 𝑥0 ⨁𝑥1 a b Hình 2-3 a) cổng CNOT, b) cổng CNOT âm  Toffoli: (𝑥, 𝑦; 𝑧) → (𝑥, 𝑦; 𝑧 ⊕ 𝑥𝑦) 𝑥2 𝑥2 𝑥2 𝑥2 𝑥2 𝑥2 𝑥1 𝑥1 𝑥1 𝑥1 𝑥1 𝑥1 𝑥0 𝑥0 ⨁𝑥1 𝑥2 𝑥0 𝑥0 ⨁𝑥1 𝑥2 𝑥0 𝑥0 ⨁𝑥1 𝑥2 a b c Hình 2-4 a) cổng Toffoli, b) cổng Toffoli bán âm, c) cổng Toffoli âm  Multicontrol Toffoli: 𝑥𝑛 𝑥𝑛 𝑥𝑛−1 𝑥𝑛−1 … … … … 𝑥 … …𝑥 1 1 𝑥0 𝑥0 ⨁𝑥1 … 𝑥𝑛−1 𝑥𝑛 Hình 2-5 Cổng multicontrol Toffoli 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. Đường Ancilla và Garbage Có 2𝑛 ! hàm khả đảo phân biệt n biến với các hoán vị của 2𝑛 phần tử.

Tuy 𝑖 𝑛 nhiên, cũng tồn tại ∑𝑛𝑖=1(2𝑖 )2 ≃ 2𝑛2 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 ancilla 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 𝑔 = ⌈𝑙𝑜𝑔2 𝑀⌉ đường ancilla để xây dựng được mạch khả đảo [3]. 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 n- bit 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 Chi phí NOT 1 CNOT 1 CNOT âm 3 Toffoli 5 Toffoli bán âm 5 Toffoli âm 7 𝑁 𝑁𝑥𝑁 Toffoli (bán âm) 2 −3 𝑁𝑥𝑁 Toffoli âm 2𝑁 − 1 Chương 2 HVTH: Nguyễn Đức Hương Quỳnh Luận văn thạc sĩ 8 GVHD: TS. Trần Hoàng Linh 2. Các phương pháp tổng hợp mạch hiện tại 2. 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 8 9 stt abc xyz xyz xyz xyz xyz xyz xyz xyz xyz xyz 0 000 011 010 000 000 000 000 000 000 000 000 1 001 000 000 010 011 001 001 001 001 001 001 2 010 101 101 111 110 110 010 010 010 010 010 3 011 010 011 001 001 011 111 011 011 011 011 4 100 001 001 011 010 010 110 110 100 100 100 5 101 111 110 100 100 100 100 100 110 111 101 6 110 110 111 101 101 111 011 111 101 101 111 7 111 100 100 110 111 101 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. Chương 2 HVTH: Nguyễn Đức Hương Quỳnh Luận văn thạc sĩ 9 GVHD: TS. Trần Hoàng Linh 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 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]. 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ị (𝑎1 , 𝑎2 , … , 𝑎𝑘 ) mà trong đó 𝑓 (𝑎1 ) = 𝑎2 , 𝑓 (𝑎2 ) = 𝑎3 , … , 𝑓 (𝑎𝑘 ) = 𝑎1. 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.

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