TRƯỜNG ĐẠI HỌC BÁCH KHOA HÀ NỘI VIỆN ĐIỆN TỬ - VIỄN THÔNG -oOo - ĐỒ ÁN TỐT NGHIỆP CAO HỌC ĐỀ TÀI: KIỂM ĐỊNH HÌNH THỨC THIẾT KẾ PHẦN CỨNG Học viên thực : Nguyễn Thái Bình Mã số học viên : CB110811 Lớp : 11BKTTT2 – Khóa 2011B Giảng viên hướng dẫn : TS NGUYỄN ĐỨC MINH Cán phản biện : Hà Nội, 08 - 2013 Kiểm định hình thức phần cứng MỤC LỤC MỤC LỤC LỜI CAM ĐOAN DANH SÁCH HÌNH VẼ DANH SÁCH BẢNG BIỂU THUẬT NGỮ VÀ TỪ VIẾT TẮT PHẦN MỞ ĐẦU CHƯƠNG TỔNG QUAN VỀ KIỂM ĐỊNH HÌNH THỨC PHẦN CỨNG 10 1.1 Kiểm chứng quy trình thiết kế vi mạch 10 1.2 Kiểm chứng phương pháp mô 13 1.3 Phương pháp kiểm chứng hình thức 15 1.4 So sánh phương pháp kiểm chứng mơ kiểm chứng hình thức 19 CHƯƠNG KIỂM CHỨNG HÌNH THỨC 22 2.1 Biểu diễn logic 22 2.1.1 Biểu diễn hàm logic 22 2.1.2 Mạch logic tổ hợp 25 2.1.3 Gate-net-list 29 2.1.4 Mơ hình hóa mạch 30 2.2 Kiểm chứng tương đương 38 2.2.1 Đồ thị định nhị phân (BDD) 38 2.2.2 Toán tử định nhị phân BDD 41 2.2.3 Kiểm chứng tương đương dựa BDD 44 2.3 Kiểm chứng thuộc tính 49 2.3.1 Thuộc tính ngơn ngữ mơ tả đặc điểm kỹ thuật mạch 49 2.3.2 Kiểm tra công thức CTL 53 CHƯƠNG PHÁT TRIỂN CHƯƠNG TRÌNH TẠO ROBDD TỪ MẠCH LOGIC BIỂU DIỄN BẰNG FCK 56 3.1 Gói phần mềm FCK 56 Kiểm định hình thức phần cứng 3.1.1 Sơ đồ thừa kế 56 3.1.2 Các định nghĩa giao tiếp mạch (Circuit Builder) 58 3.1.3 Circuit 59 3.1.4 Module FCK 61 3.1.5 Component 61 3.1.6 Lớp hàm Function 67 3.2 Gói CUDD (CUDD package) 69 3.2.1 Cấu trúc liệu CUDD 69 3.2.2 Các thao tác với đồ thị định nhị phân BDD CUDD 71 3.3 Biến đổi mạch từ mạch mô tả FCK sang dạng ROBDD 72 3.3.1 Chuyển đổi Component FCK thành Dnode 73 3.3.2 Tạo ROBDD cho mạch Component 76 CHƯƠNG KẾT LUẬN 78 TÀI LIỆU THAM KHẢO 79 Kiểm định hình thức phần cứng LỜI CAM ĐOAN Tơi xin cam đoan cơng trình nghiên cứu tôi, xin chịu trách nhiệm nội dung trình bày luận văn Hà Nội, ngày 15 tháng năm 2013 Sinh viên Nguyễn Thái Bình Kiểm định hình thức phần cứng DANH SÁCH HÌNH VẼ Hình 1-1 Đồ thị mức độ trừu tượng thiết kế 11 Hình 1-2 Mối quan hệ thiết kế kiểm chứng 12 Hình 1-3 Quy trình kiểm chứng mô 14 Hình 1-4 Nguyên tắc kiểm chứng (A) Phương pháp kiểm chứng cách tạo dư thừa, (B) Một biến thể phương pháp bản, (C) Mô kết hợp với kiểm chứng 17 Hình 1-5 Quy trình thơng thường kiểm chứng hình thức 19 Hình 1-6 Không gian trạng thái đầu phương pháp mô phương pháp hình thức 21 Hình 2-1 Ví dụ component netlist 26 Hình 2-2 Một ví dụ mạch tổ hợp 28 Hình 2-3Ví dụ gate-netlist 29 Hình 2-4 Mở rộng gate-net-list thành component-net-list 30 Hình 2-5 Ví dụ component netlist biểu diễn đồ thị có hướng bổ sung thêm phép toán 30 Hình 2-6 JK flip-flop 31 Hình 2-7 Mơ hình mạch .32 Hình 2-8 Mơ hình vi mạch tổng qt 36 Hình 2-9 Cấu trúc mạch đồng 37 Hình 2-10 Quá trình trải mạch .38 Hình 2-11Ví dụ BDD 39 Hình 2-12 Hai BDD (A,B) hàm khác thứ tự biến .40 Hình 2-13 Hai BDD (A,B) hàm 41 Kiểm định hình thức phần cứng Hình 2-14 Sơ đồ kiểm tra tương đương phương pháp sử dụng XOR 45 Hình 2-15 Các mạch cần kiểm tra tương đương (A) mức gate-level (B) mức RTL 46 Hình 2-16 So sánh BDD lớn khơng có khơng có node mapping (A) BDD cho node f (B) BDD cho node x (C) BDD cho node y (D) BDD cho node z (E) BDD cho node f 47 Hình 2-17 Tạo input output trung gian từ điểm cắt 47 Hình 2-18 Giới hạn đầu vào để kiểm tra mạch 48 Hình 2-19 Giới hạn cách buộc đầu input không phép 49 Hình 2-20 Ý nghĩa tốn tử LTL 52 Hình 3-1 Sơ đồ kế thừa lớp Circuit .56 Hình 3-2 Sơ đồ kế thừa lớp TimeFrameExpansion từ lớp Module .56 Hình 3-3 Sơ đồ kế thừa phần tử mạch từ lớp Component 57 Hình 3-4 Mô tả cổng vào biến lớp Component .61 Hình 3-5 Bộ cộng Ripple-carry 76 Hình 3-6 Lưu đồ thuật tốn chuyển từ FCK sang ROBDD 77 Kiểm định hình thức phần cứng DANH SÁCH BẢNG BIỂU Bảng 2.1 Các cổng logic hàm logic tương ứng chúng 28 Bảng 2.2 Toán tử ITE biểu diễn toán tử Boolean 43 Bảng 3.1 Bảng liệt kê component FCK .58 Bảng 3.2 Danh sách mô tả biến lớp Circuit .59 Bảng 3.3 Danh sách ý nghĩa hàm lớp circuit .60 Bảng 3.4 Danh sách mô tả biến Private lớp Module 61 Bảng 3.5 Bảng liệt kê mô tả biến Protect Component .62 Bảng 3.6 Danh sách hàm cấu hình Component 62 Bảng 3.7 Danh sách biến protect biến private Input 63 Bảng 3.8 Danh sách biến Private Pseudo Input 64 Bảng 3.9Các biến Module Input 65 Bảng 3.10 Hàm Private LT 66 Bảng 3.11 Các biến protect lớp Function .68 Bảng 3.12 Các hàm lớp Function 68 Bảng 3.13 Các hàm chung lớp Function 69 Bảng 3.14 Các hàm thao tác BDD gói CUDD 71 Kiểm định hình thức phần cứng THUẬT NGỮ VÀ TỪ VIẾT TẮT ASICs Application-Specific Integrated Circuit AST Abstract Syntax Tree BDD Binary Decision Diagram BFS Vi mạch tích hợp chuyên dụng Cây cú pháp trừu tượng Biểu đồ định nhị phân Breath First Search Tìm kiếm theo chiều rộng CDFG Control Data Flow Graph Đồ thị dòng liệu điều khiển DAG Directed Acylic Graph Đồ thị khơng hồi tiếp có hướng DFS Depth First Search Tìm kiếm theo chiều sâu FSM Finite-State Machine Máy trạng thái hữu hạn FV Formal Verification Kiểm chứng hình thức FF Flip-Flop Mạch lật Field Programable Gate Array Mảng cổng logic lập trình FPGA FST Finite State Transition Structure Chuyển trạng thái hữu hạn HDL Hardware Description Language Ngôn ngữ mô tả phần cứng Integrated Circuit Vi mạch tích hợp Institute of Electrical and Electronics Viện kỹ nghệ Điện Điện tử IC IEEE Engineers ROBDD Reduce order binary decision diagram Cây định nhị phân có thứ tự rút gọn RTL Register Transfer Level Mức dịch chuyển ghi SAT Satisfiability Thỏa mãn SCC Strongly Connected Components Thành phần kết nối chặt chẽ Kiểm định hình thức phần cứng VLSI STG Very-large-scale Integration Vi mạch tích hợp lớn State Transition Graph Đồ thị chuyển trạng thái Kiểm định hình thức phần cứng PHẦN MỞ ĐẦU Để thiết kế mạch tích hợp có độ phức tạp lớn yêu cầu tiên phải có cơng nghệ tổng hợp, tối ưu kiểm tra tự động phần cứng số Ngày nay, mạch tích hợp có hàng triệu cổng logic, phần mềm tự động có khả tối ưu kiểm tra chúng Sử dụng phần mềm thiết kế, kiểm tra tự động cho phép giải vấn đề thiết kế chế tạo mạch tích hợp suất thiết kế chất lượng vi mạch Các mạch tích hợp địi hỏi phải có chất lượng cao Bất lỗi nhỏ phần cứng thiết bị dẫn tới tổn thất to lớn giá thành thời gian thị trường sản phẩm Vì vậy, việc kiểm tra thiết kế phần cứng vi mạch ln vấn đề nóng lĩnh vực chế tạo thiết bị điện tử Mô logic kỹ thuật sử dụng rộng rãi cho việc kiểm chứng thiết kế Mô tính tốn giá trị đầu giá trị đưa vào đầu vào Tuy nhiên, chất lượng việc kiểm chứng phụ thuộc nhiều vào việc lựa chọn giá trị đầu vào nên tồn lỗi thiết kế mà khơng thể tìm phương pháp mơ logic Bởi số lượng giá trị đầu vào yêu cầu tăng theo cấp số nhân kích thước thiết kế tăng lên nên việc kiểm chứng thiết kế cách tổng thể phương pháp mô không khả thi Để giải vấn đề này, việc phát triển kỹ thuật kiểm chứng hình thức (Formal Verification) cần thiết Đồ án tập trung vào việc nghiên cứu tìm hiểu vấn đề liên quan đến kiểm chứng hình thức mơ hình hóa vi mạch, phương pháp chứng minh; ngơn ngữ đặc tả, sau phát triển chương trình minh họa việc mơ hình hóa mạch logic theo định nhị phân rút gọn (ROBDD) Em xin chân thành cảm ơn TS.Nguyễn Đức Minh, người tận tâm giúp đỡ em trình nghiên ln đưa lời khun hữu ích, gia đình, bạn bè giúp em hoàn thành đồ án Kiểm định hình thức thiết kế phần cứng • Tên module (kiểu module) Hàm thiết lập Module Input ConstInput::ConstInput(std::string constValue, int id, Module* module) Bảng 3.9 Các biến Module Input 3.1.5.8 Bộ cộng Add Bộ cộng thực phép toán cộng, kế thừa từ lớp Function Bộ cộng có Fanin nên biến mRequiredFanin = 3.1.5.9 Bộ AND Bộ thực phép toán AND, kế thừa từ lớp Function Bộ AND có Fanin nên biến mRequiredFanin = 3.1.5.10 CONCAT Bộ ghép thực phép toán CONCAT, kế thừa từ lớp Function Bộ CONCAT có Fanin nên biến mRequiredFanin = 3.1.5.11 Bộ tương đương (Equivalence) Bộ Equivalence thực kiểm tra tương đương, kế thừa từ lớp Function Bộ CONCAT có Fanin nên biến mRequiredFanin = 65 Kiểm định hình thức thiết kế phần cứng 3.1.5.12 Bộ ITE (Ifthenelse) ITE thực toán tử Ifthenelse trình bày mục 2.2.2.4.ITE kế thừa từ lớp Function ITE có đầu vào nên có mRequiredFanin = 3.1.5.13 Bộ so sánh nhỏ LT (Less than) Bộ so sánh thực phép so sánh đầu vào, kế thừa từ lớp Function LT có Fanin nên biến mRequiredFanin = LT có hàm Private mơ tả Bảng 3.10 Bảng 3.10 Hàm Private LT 3.1.5.14 Bộ đảo dấu MINUS Bộ đảo dấu thực phép đảo dấu cho đầu vào, kế thừa từ lớp Function MINUS có Fanin nên biến mRequiredFanin = 3.1.5.15 Bộ nhân (MULT) Bộ MULT thực chức nhân đầu vào Nó kế thừa từ lớp Function MULT có Fanin nên biến mRequiredFanin = 3.1.5.16 Bộ NOT Bộ NOT thực đảo logic.Nó kế thừa từ lớp Function NOT có Fanin nên biến mRequiredFanin = 3.1.5.17 Bộ OR Bộ OR thực đảo logic.Nó kế thừa từ lớp Function OR có Fanin nên biến mRequiredFanin = 66 Kiểm định hình thức thiết kế phần cứng 3.1.5.18 Bộ dịch trái SHL (shift left) Bộ SHL thực dịch trái biến logic đầu vào.Nó kế thừa từ lớp Function SHL có Fanin nên biến mRequiredFanin = Các hàm private SHL thể bảng sau: 3.1.5.19 Bộ dịch phải SHR (shift right) Bộ SHR thực dịch phải biến đầu vào.Nó kế thừa từ lớp Function SHR có Fanin nên biến mRequiredFanin = 3.1.5.20 Bộ dịch phải số học SRA (Shift right arithmetic) Bộ SRA thực dịch phải số học biến đầu vào.Nó kế thừa từ lớp Function.SRA có Fanin nên biến mRequiredFanin = 3.1.5.21 Bộ xoay phải bit ROR (Rotate Right) Bộ RORthực quay phải bit biến đầu vào Nó kế thừa từ lớp Function.RORcó Fanin nên biến mRequiredFanin = 3.1.5.22 Bộ xoay trái bit ROL (Rotate Left) Bộ ROL thực quay trái bit biến đầu vào Nó kế thừa từ lớp Function.ROL có Fanin nên biến mRequiredFanin = 3.1.6 Lớp hàm Function Là lớp cha lớp Component chức năng, kế thừa từ lớp Component Các biến Protected Function thể Bảng 3.11 67 Kiểm định hình thức thiết kế phần cứng Bảng 3.11 Các biến protect lớp Function Các hàm Function liệt kê Bảng 3.12.Các hàm thừa kế lớp Bảng 3.12 Các hàm lớp Function Các hàm chung lớp Function liệt kê Bảng 3.13 68 Kiểm định hình thức thiết kế phần cứng Bảng 3.13 Các hàm chung lớp Function 3.2 Gói CUDD (CUDD package) CUDD viết tắt Colorado University Decision Diagram, phát triển vào năm 1995 Fabio Somenzi, Boulder, CO Gói CUDD cung cấp hàm thao tác với BDD (Binary Decision Diagrams) , ADD (Algebraic Decision Diagrams), ZDD (Zero-suppressed Binary Decision Diagrams) Báo cáo quan tâm đến hàm thao tác với BDD để chuyển đổi mạch mô tả theo FCK thành ROBDD Đầu vào CDDD mạch logic tổ hợp mô tả theo cấu trúc liệu định nghĩa sẵn gói Sau CUDD nhận đầu vào phân tích cho đầu đồ thị định nhị phân ROBDD mô tả dạng file “.dot” Để xem đồ thị cách trực quan ta dùng gói phần mềm Graphviz 3.2.1 Cấu trúc liệu CUDD 3.2.1.1 Node BDD, ADD, ZDD tạo nên từ DdNode DdNode cấu trúc C++ bao gồm trường sau: 69 Kiểm định hình thức thiết kế phần cứng struct DdNode { DdHalfWord index; DdHalfWord ref; DdNode *next; /* reference count */ /* next pointer for unique table */ union { CUDD_VALUE_TYPE value; /* for constant nodes */ DdChildren kids; /* for internal nodes */ } type; }; Khi dùng CUDD hộp đen nên quan tâm đến trường : index ( số), value (giá trị), ref(số tham chiếu) Các trường lại trỏ kết nối node với Trường index chứa tên biến mà đánh nhãn cho nút.Chỉ số biến thuộc tính cố định phản ánh thứ tự tạo nó.Chỉ số tương ứng với biến tạo Trên máy tính với trỏ 32-bit, số lượng tối đa biến giá trị lớn lưu trữ kiểu unsigned short int trừ Chỉ số lớn dành riêng cho nút số Khi trỏ 64-bit sử dụng, số lượng tối đa biến giá trị lớn lưu trữ kiểu unsigned int trừ 3.2.1.2 Manager Tất nút sử dụng BDDs, ADDs, ZDDs lưu giữ bảng đặc biệt gọi unique tables (bảng nhất) Mục đích unique tables để đảm bảo nút nhất, khơng có nút khác dán nhãn biến với node giống Các unique tables 70 Kiểm định hình thức thiết kế phần cứng số cấu trúc liệu phụ trợ tạo nên DdManager Mặc dù thế, ứng dụng mà sử dụng hàm xuất cần không cần quan tâm đến hầu hết chi tiết manager.Ứng dụng phải khởi tạo manager cách gọi hàm thích hợp Sau đó, phải qua trỏ đến manager để đến tất hàm hoạt động đồ thị định 3.2.1.3 Khởi tạo giải phóng DdManager Để sử dụng hàm CUDD package, trước tiên phải khởi tạo cách gọi hàm Cudd_Init Hàm có tham số: • numVars : số lượng biến cho BDD ADD • numVars : số lượng biến cho ZDD • numSlots : Xác định kích thước ban đầu cho unique table phụ • cacheSizes : kích thước ban đầu cho đệm • maxMemory : kích thước tối đa cho nhớ bị chiếm chỗ Nếu maxMemory 0, CUDD cố gắng đưa giá trị tối ưu dựa nhớ có sẵn 3.2.2 Các thao tác với đồ thị định nhị phân BDD CUDD Bảng hàm thường dùng cho thao tác với BDD trình bày Bảng 3.14 Bảng 3.14 Các hàm thao tác BDD gói CUDD ST T Tên hàm Chức DdNode* Tạo input cho Cudd_bddIte(manager,…) mạch DdNode* Tạo cổng And Cudd_bddAnd(manager,…) DdNode* hai tín hiệu Tạo cổng Or 71 Kiểm định hình thức thiết kế phần cứng Cudd_bddOr(manager,…) hai tín hiệu DdNode* Tạo cổng Nand Cudd_bddNand(manager,…) DdNode* tín hiệu Tạo cổng Nor Cudd_bddNor(manager,…) DdNode* hai tín hiệu Tạo cổng Xor Cudd_bddXor(manager,…) DdNode* Cudd_Not(…) hai tín hiệu Phủ định tín hiệu ngoặc Để tạo cổng Not manager cho tín hiệu (ví dụ f) ta dùng cổng Nand ( Nor) : Cudd_bddNand(manager, f, f) Với số CUDD ta tạo Xor hai tín hiêu giống Ví dụ cho tạo số : Cudd_bddXor(manager, f, f) 3.3 Biến đổi mạch từ mạch mô tả FCK sang dạng ROBDD Mạch cần chuyển đổi sang ROBDD mạch gồm Component mô tả theo cấu trúc liệu FCK mạch đầu vào CUDD mạch mơ tả DdNode Vì vậy, để tạo ROBDD theo yêu cầu cần phải chuyển đổi tương ứng mạch từ cấu trúc FCK vào mạch DdNode Muốn làm điều đó, trước tiên phải tạo DdNode tương ứng với Component có chức Ngồi ra, ta thấy, tạo DdNode tương ứng với Component mạch đầu vào cần đảm bảo Fanin Component có DdNode tương ứng.Nếu khơng đảm bảo điều xảy xung đột trình chạy chương trình Giải pháp cho vấn đề ta duyệt chuyển đổi Component sang DdNode theo mức cổng logic mạch (gate level) từ thấp đến cao theo thuật 72 Kiểm định hình thức thiết kế phần cứng toán BFS (Breadth-First Search) để ghép DdNode Component thu ROBDD cần tìm 3.3.1 Chuyển đổi Component FCK thành Dnode Trước tiên, tạo hàm ảo lớp sở Component ( file component.h) sau: virtual void Component2ROBDD(DdManager *manager){} Sau lớp dẫn xuất Component sử dụng tính đa hình để tạo hàm riêng cho loại Component khác Do khác cách gọi hàm tạo DdNode tương ứng cổng định nghĩa sẵn CUDD package, nên ta chia Component thành nhóm: 73 Kiểm định hình thức thiết kế phần cứng • Nhóm 1: gồm Input (khơng có Fanin) • Nhóm 2: Component đại diện cho cổng logic bản: and, or, not, xor,…(có Fanin) • Nhóm 3: Component cịn lại (có fanin) 3.3.1.1 Tạo DdNode cho Input Hàm tương ứng CUDD package: DdNode *x = Cudd_bddIthVar(manager,1); Trong hàm “1” số (Index) biến Input, Component khác khơng cần đặt Index Với mục đích tạo Input có số tăng dần ta khai báo biến mNextDdNodeId khởi tạo cho giá trị Đồng thời, ta tạo hàm lấy giá trị mNextDdNodeId DdNode sau: int GetNextDdNodeId(){return mNextDdNodeId++;} //tăng giá trị thêm lần gọi hàm Dựa điều phân tích, có hàm Component2ROBDD(DdManager *manager) cho Component Input đây: void Input::Component2ROBDD(DdManager *manager) { mDdNode.clear(); //mang luu DdNode tương úng với Component for (unsigned int i=0; i< mFanoutWidth;i++) { DdNode *f; f = Cudd_bddIthVar(manager,this->GetModule()->GetParentCircuit()- >GetNextDdNodeId()); //tìm Circuit chứa Input gọi hàm GetNextDdNodeId() 74 Kiểm định hình thức thiết kế phần cứng mDdNode.push_back(f); } } Do Component fanin fanout cấu thành từ nhiều bit, CUDD package cổng logic có fanin fanout gồm bit Vì vậy, để lưu đầy đủ DdNode tương ứng với Component cần phải dùng vector DdNode (std::vector mDdNode) Vector thuộc tính khai báo class Component 3.3.1.2 Tạo DdNode cho Component nhóm Khác với Input Component nhóm có fanin, vậy, muốn tạo DdNode tương ứng cho ta phải có DdNode cho fanin tạo trước Ngồi ra, CUDD định nghĩa cổng ứng với Component nên ta cần gọi hàm tạo DdNode tương ứng với cổng void And::Component2ROBDD(DdManager *manager) { mDdNode.clear(); //mang luu DdNode tương úng với Component for (unsigned int i=0; i< mFanoutWidth;i++) {// chuyển đổi bít fanout vào DdNode DdNode *f; f = Cudd_bddAnd(manager,mFanin[0]->GetMDdNode().at(i),mFanin[1]- >GetMDdNode().at(i)); Cudd_Ref(f); mDdNode.push_back(f); } } 75 Kiểm định hình thức thiết kế phần cứng 3.3.1.3 Tạo DdNode cho Component nhóm Khác với hai nhóm đầu, Component nhóm đại diện cho mạch tổ hợp thực chức như: cộng, trừ, nhân, …Muốn tạo DdNode cho Component nhóm ta cần dựa vào cổng logic định nghĩa sẳn CUDD để ghép nối chúng lại với để tạo thành mạch thực chức Component Ví dụ mạch cộng ta triển khai dựa mơ hình Ripple-carry adder nhưHình 3-5 Hình 3-5 Bộ cộng Ripple-carry Mã nguồn cho Component nằm file “add.cpp”, “minus.cpp”, “multiplier.cpp”, … 3.3.2 Tạo ROBDD cho mạch Component Muốn tạo DdNode cho Component Input phải thõa mãn điều kiện fanin tạo DdNode tương ứng Vì vậy, để tránh xung đột tạo DdNode cho Component, ta phải duyệt Component theo thứ tự mức cổng (gate level) chúng từ thấp đến cao Sau sơ đồ thuật toán duyệt đồ thị dùng BFS áp dụng cho tốn này: 76 Kiểm định hình thức thiết kế phần cứng Hình 3-6 Lưu đồ thuật toán chuyển từ FCK sang ROBDD Mã nguồn cho thuật toán nằm hàm Module2ROBDD file “module.cpp” 77 Kiểm định hình thức thiết kế phần cứng CHƯƠNG KẾT LUẬN Trong đồ án phân tích cần thiết kiểm chứng đặc biệt phương pháp kiểm chứng hình thức Phương pháp kiểm chứng hình thức khác với phương pháp kiểm chứng mơ phương pháp kiểm chứng hình thức khơng cần tạo test vector, kiểm chứng hình thức kiểm chứng đắn thiết kế thông qua phương pháp chứng minh dựa mơ hình mạch Đồ án sâu vào tìm hiểu việc mơ hình hóa mạch logic, phương pháp kiểm chứng tương đương, kiểm chứng thuộc tính Sau đó, xây dựng chương trình dựa gói FCK CUDD để biến mạch mơ hình hóa CUDD thành dạng nhị phân rút gọn (ROBDD) Đầu chương trình dùng để kiểm chứng tương đương đầu vào cho trình xử lý kiểm chứng hình thức 78 Kiểm chứng hình thức thiết kế phần cứng TÀI LIỆU THAM KHẢO [1] Minh D Nguyen, “System-on-Chip Protocol Compliance Verification Using Interval Property Checking”,16 Januar 2009, Germany [2] Alfred V Aho, Monica S Lam, Ravi Sethi ,Jeffrey D.Ullman,“Compilers, principles, techniques , & tools”,second edition [3] Anthony A Aaby, “Compiler Construction using Flex and Bison”,Version of February 25, 2004,aabyan@wwc.edu [4] William K Lam “Hardware Design Verification: Simulation and Formal Method-BasedApproaches”,Publisher Prentice Hall PTR, March 03, 2005, ISBN:0-13-143347-4 [5] Peter Jamieson, Kenneth B Kent, Farnaz Gharibian, and Lesley Shannon,Miami University, “Odin II - An Open-source Verilog HDL Synthesis Tool for CAD Research”,email: lshannon@ensc.sfu.ca [6] GNU, “Bison - GNU parser generator”,http://www.gnu.org/software/bison/, 2009 [7] Erich Hamma,Richard Helm,Raiph Johnson,and John Viissides, “Design Patterns Elements of Reusable Object-Oriented Software”,ISBN 0-201-63442-2 Hardback 416 pages ©1995 [8] http://sourcemaking.com/design_patterns Truy cập lần cuối 25-8-2013 [9] Michael D Ciletti, “Advanced digital verilog with the Verilog HDL”, University of colorado at colorado springs ,New Delhi 2005,ISBN-81-2032-756X [10] http://en.wikipedia.org/wiki/Depth-first_search Truy cập lần cuối 25-82013 [11] David Money Harris , Sarah L Harris ,“Digital design and computer architecture“ [12] Chung V Nguyễn , “Cấu trúc liệu FCK” ,2-2012 [13] http://www.graphviz.org/ 79 ... kiểm tra hình thức phần mềm kiểm tra hình thức tốn nhớ thời gian chạy lâu, kích thước mạch mà kiểm chứng hình thức khơng lớn 21 Kiểm định hình thức thiết kế phần cứng CHƯƠNG KIỂM CHỨNG HÌNH THỨC... thiết kế biến tập hợp yêu cầu kỹ thuật thành triển khai cụ thể 10 Kiểm định hình thức thiết kế phần cứng Hình 1-1 Đồ thị mức độ trừu tượng thiết kế Kiểm chứng thiết kế trình ngược lại thiết kế .Kiểm. .. Kiểm định hình thức phần cứng DANH SÁCH HÌNH VẼ Hình 1-1 Đồ thị mức độ trừu tượng thiết kế 11 Hình 1-2 Mối quan hệ thiết kế kiểm chứng 12 Hình 1-3 Quy trình kiểm chứng mơ 14 Hình