Luận Văn Thạc Sĩ Kỹ Thuật Điện Tử Về Thuật Toán Tổng Hợp Mạch Khả Đảo Đa Ngõ Ra

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

• Tác giả: Nguyễn Hải Đăng
• 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 Không 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 chung về luận văn

Luận văn thạc sĩ Kỹ thuật điện tử này tập trung vào việc phát triển thuật toán tổng hợp mạch khả đảo đa ngõ ra không hoàn chỉnh. Mục tiêu chính là tối ưu hóa quá trình tổng hợp mạch, nhằm đáp ứng nhu cầu ngày càng cao trong lĩnh vực công nghệ điện tử và tính toán lượng tử. Các nghiên cứu trước đây cho thấy rằng logic khả đảo có nhiều ứng dụng quan trọng, đặc biệt là trong thiết kế mạch công suất thấp và hệ thống điện tử phức tạp. Do đó, việc phát triển một thuật toán mới nhằm cải thiện hiệu suất tổng hợp mạch là rất cần thiết. Các phương pháp tổng hợp hiện tại thường gặp khó khăn trong việc xử lý các hàm không hoàn chỉnh, điều này dẫn đến việc cần thiết phải nghiên cứu và phát triển một phương pháp mới có khả năng tối ưu hóa chi phí và thời gian tổng hợp.

1.1 Tầm quan trọng của nghiên cứu

Nghiên cứu về thuật toán tổng hợp mạch không chỉ giúp nâng cao hiệu suất tổng hợp mà còn mở ra nhiều cơ hội ứng dụng trong các lĩnh vực như tính toán lượng tử, công nghệ nano và hệ thống viễn thông. Qua đó, luận văn này không chỉ mang lại giá trị lý thuyết mà còn có ý nghĩa thực tiễn sâu sắc trong việc phát triển các sản phẩm công nghệ mới. Việc tối ưu hóa chi phí lượng tử và độ sâu mạch sẽ giúp các nhà thiết kế có thể xây dựng các mạch khả đảo hiệu quả hơn, từ đó thúc đẩy sự phát triển của ngành kỹ thuật điện tử.

II. Tổng quan về các phương pháp tổng hợp

Luận văn trình bày các phương pháp tổng hợp mạch hiện tại, bao gồm các phương pháp như transformation-based, cycle-based và graphical. Mỗi phương pháp đều có những ưu điểm và nhược điểm riêng, do đó việc lựa chọn phương pháp phù hợp là rất quan trọng. Phương pháp transformation-based được áp dụng để sửa chữa các điểm khác biệt giữa ngõ vào và ngõ ra trong bảng sự thật, trong khi phương pháp cycle-based tập trung vào việc tối ưu hóa các chu kỳ trong mạch. Các nghiên cứu trước đây đã chỉ ra rằng việc kết hợp giữa các phương pháp này có thể mang lại kết quả tốt hơn trong việc tổng hợp mạch khả đảo.

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. Nó hoạt động bằng cách quét qua bảng sự thật và tìm kiếm sự khác biệt giữa ngõ vào và ngõ ra, từ đó áp dụng các cổng như multicontrol Toffoli để sửa chữa các điểm khác biệt. Điều này giúp tạo ra một mạch khả đảo chính xác hơn, đáp ứng yêu cầu của hàm logic. Tuy nhiên, phương pháp này cũng gặp phải một số hạn chế khi xử lý các hàm không hoàn chỉnh, điều này đã dẫn đến việc nghiên cứu các phương pháp mới hơn.

III. Phương pháp chuyển đổi hàm khả đảo

Luận văn đề xuất một phương pháp chuyển đổi hàm khả đảo đa ngõ ra không hoàn chỉnh sang hàm hoàn chỉnh, nhằm làm ngõ vào cho thuật toán tổng hợp. Phương pháp này không chỉ giúp cải thiện tính chính xác của mạch tổng hợp mà còn giảm thiểu chi phí lượng tử. Việc chuyển đổi này rất quan trọng vì các thuật toán tổng hợp hiện tại thường yêu cầu ngõ vào phải là hàm khả đảo hoàn chỉnh. Phương pháp chuyển đổi này bao gồm các bước như thêm đường ancilla và garbage, từ đó đảm bảo rằng tất cả các ngõ ra đều có giá trị xác định.

3.1 Các bước chuyển đổi

Quá trình chuyển đổi bao gồm việc xác định số ngõ vào và ngõ ra, sau đó thêm các đường ancilla cần thiết. Các ngõ ra không xác định sẽ được đánh dấu là garbage. Việc này giúp đảm bảo rằng hàm khả đảo hoàn chỉnh được tạo ra từ hàm không hoàn chỉnh, từ đó tạo điều kiện thuận lợi cho các thuật toán tổng hợp tiếp theo. Nghiên cứu cho thấy rằng việc áp dụng phương pháp này có thể làm giảm đáng kể chi phí lượng tử và tăng tốc độ tổng hợp, từ đó mở ra nhiều khả năng ứng dụng trong thực tế.

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

Luận văn trình bày các kết quả thí nghiệm cho thấy hiệu quả của thuật toán tổng hợp mới được đề xuất. Kết quả cho thấy rằng thuật toán này không chỉ cải thiện tốc độ tổng hợp mà còn giảm chi phí lượng tử so với các phương pháp hiện tại. Việc so sánh với các thuật toán khác cho thấy rằng phương pháp mới có thể cung cấp một lựa chọn tối ưu hơn cho các nhà thiết kế mạch. Các thí nghiệm được thực hiện trên nhiều loại hàm khác nhau, từ đó khẳng định tính khả thi và hiệu quả của thuật toán.

4.1 Đánh giá hiệu suất

Các kết quả thí nghiệm chỉ ra rằng thuật toán tổng hợp mạch khả đảo mới có thể đạt được tín hiệu điện tử cao hơn, thời gian tổng hợp ngắn hơn và chi phí lượng tử thấp hơn so với các phương pháp truyền thống. Điều này chứng tỏ rằng việc kết hợp giữa các phương pháp tổng hợp khác nhau có thể mang lại những cải tiến đáng kể trong thiết kế mạch. Từ đó, luận văn khuyến nghị việc áp dụng phương pháp này trong các nghiên cứu và ứng dụng thực tế trong lĩnh vực kỹ thuật điện tử.

V. Kết luận và hướng phát triển

Luận văn đã trình bày một thuật toán tổng hợp mạch khả đảo đa ngõ ra không hoàn chỉnh mới, với mục tiêu tối ưu hóa thời gian và chi phí tổng hợp. Các kết quả đạt được cho thấy tính khả thi và hiệu quả của phương pháp mới. Trong tương lai, có thể mở rộng nghiên cứu để cải thiện hơn nữa các thuật toán tổng hợp, đặc biệt là trong việc xử lý các hàm không hoàn chỉnh phức tạp hơn. Hướng phát triển tiếp theo có thể bao gồm việc áp dụng các công nghệ mới trong thiết kế mạch và tính toán lượng tử.

5.1 Hướng phát triển tiếp theo

Nghiên cứu có thể tiếp tục mở rộng với việc áp dụng các công nghệ mới và các phương pháp học máy để tối ưu hóa quy trình tổng hợp mạch. Việc phát triển các công cụ phần mềm hỗ trợ cho việc tổng hợp mạch khả đảo cũng là một hướng đi tiềm năng, giúp các nhà nghiên cứu và kỹ sư có thể dễ dàng áp dụng các thuật toán mới vào thực tế.

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

Mở đầu HVTH: Nguyễn Hải Đăng 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 Một hàm boolean được gọi là khả đảo nếu 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. Ví dụ như hàm F có bảng sự thật như sau: Bảng 2-1 Bảng sự thật của hàm khả đảo 3 biến Ngõ vào Ngõ ra X2 X1 X0 Y2 Y1 Y0 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ì bảng sự thật của các hàm có số biến lớn sẽ rất lớn nên thông thường, các ngõ ra sẽ được biểu diễn ở dạng chính tắc để dễ dàng quan sát và xử lí. Trong ví dụ trên có 3 ngõ ra Y2, Y1 và Y0 được biểu diễn như sau:  Y2 = ∑(𝟎, 𝟏, 𝟐, 𝟓) Y1 = ∑(𝟐, 𝟓, 𝟔, 𝟕) Y0 = ∑(𝟏, 𝟑, 𝟓, 𝟕) Hàm khả đảo hoàn chỉnh là một hàm khả đảo mà ở tất cả các giá trị của ngõ vào đều có giá trị của ngõ ra tương ứng. Hàm F ở ví dụ trên là một hàm khả đảo hoàn chỉnh.

Hàm khả đảo không hoàn chỉnh là một hàm khả đảo có các giá trị tùy định ở ngõ ra. Ví dụ với hàm khả đảo không hoàn chỉnh 2 ngõ vào, 2 ngõ ra: Bảng 2-2 Bảng sự thật của hàm khả đảo không hoàn chỉnh 2 biến Ngõ vào Ngõ ra X1 X0 Y1 Y0 0 0 x 1 0 1 x 0 1 0 1 0 1 1 0 x Chương 2: Tổng quan HVTH: Nguyễn Hải Đăng Luận văn thạc sĩ 5 GVHD: TS. Trần Hoàng Linh  Y1 = ∑(𝟐) + 𝒅(𝟎, 𝟏) Y0 = ∑(𝟎) + 𝒅(𝟑) Mạch khả đảo là mạch hiện thực 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 2. Cổng khả đảo Một số cổng khả đảo cơ bản:  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 Chương 2: Tổng quan HVTH: Nguyễn Hải Đăng Luận văn thạc sĩ 6 GVHD: TS. Trần Hoàng Linh  Multicontrol Toffoli: 𝑥𝑛 𝑥𝑛 𝑥𝑛−1 𝑥𝑛−1 … … … …𝑥 … … 𝑥 1 1 𝑥0 𝑥0 ⨁𝑥1 … 𝑥𝑛−1 𝑥𝑛 Hình 2-5 Cổng multicontrol Toffoli 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. Chương 2: Tổng quan HVTH: Nguyễn Hải Đăng Luận văn thạc sĩ 7 GVHD: TS. Trần Hoàng Linh 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 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 Chương 2: Tổng quan HVTH: Nguyễn Hải Đăng Luận văn thạc sĩ 8 GVHD: TS. Trần Hoàng Linh 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 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]. Chương 2: Tổng quan HVTH: Nguyễn Hải Đăng Luận văn thạc sĩ 9 GVHD: TS. Trần Hoàng Linh 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 x y z 0 0 0 0 0 0 0 0 1 0 0 1 1 0 0 4 2 0 1 0 1 0 1 5 3 0 1 1 0 1 1 3 4 1 0 0 1 1 1 7 5 1 0 1 0 1 0 2 6 1 1 0 1 1 0 6 7 1 1 1 0 0 1 1  f = (1, 4, 7)(2, 5) Trong khi phương pháp transformation-based tập trung vào mỗi giá trị riêng lẻ 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.