Báo-cáo - yyyyyy PDF

Preview

Summary

TRƯỜNG ĐẠI HỌC BÁCH KHOA HÀ NỘI---VIỆN ĐIỆN TỬ - VIỄN THÔNG---BÁO CÁO MÔN ĐIỆN TỬ SỐĐề tài: Thuật toán Quine-MCcluskeyGVHD: Hoàng Mạnh ThắngSINH VIÊN THỰC HIỆN:Lê Trần Huy (70%) 20182581 Điện tử - 4Phạm Tuấn Hùng (30%) 20182559 Điện tử - 4I. Tóm tắt giải thuật dưới dạng sơ đồSĐNhập số biến: nNhập số...

Description

TRƯỜNG ĐẠI HỌC BÁCH KHOA HÀ NỘI ---VIỆN ĐIỆN TỬ - VIỄN THÔNG---

BÁO CÁO MÔN ĐIỆN TỬ SỐ Đề tài: Thuật toán Quine-MCcluskey GVHD: Hoàng Mạnh Thắng SINH VIÊN THỰC HIỆN: Lê Trần Huy (70%)

20182581

Điện tử - 4

Phạm Tuấn Hùng (30%)

20182559

Điện tử - 4

I. Tóm tắt giải thuật dưới dạng sơ đồ Bắt đầu

Nhập số biến: n Nhập số minterm: m Chuyển các phần tử về dạng nhị phân và sắp xếp theo thứ tự tăng dần Tạo class QM chứa các thuộc tính:minterm,xau,sobit1. Tạo class PI chứa các thuộc tính:index,xau,biến check. Tạo danh sách chứa các đối tượng trong class QM,DSPI để lưu PI

So sánh lần lượt từng cặp nhị phân với nhau S

Khác nhau đúng 1 bit END Đ Lập thành nhóm mới, giữ lại các biến giống nhau, biến còn lại thay bằng dấu “_” Tạo 1 biến là so PI để đếm prime implicant,có giá trị bằng kích thước DSPI Lập bảng lựa chọn hàm Tìm các essential và PI cần thiết để ra hàm tối ưu

Hàm fmin

Tạo danh sách tên esential để chứa các essential,tạo mảng 2 chiều arrPI để lưu vị trí các minterm trong DSPI.Duyệt mảng những hàng nào mà phần tử có giá trị bằng 1 duy nhất trong cột tương ứng sẽ là essential,thêm PI vừa tìm đc vào danh sách esential,tại những ô có giá trị bằng 1 của các PI gán tất cả giá trị của cột chứa ô đó bằng 0

II. Kết quả thực hiện 1.Nhập đầu vào 3 biến

2.Nhập đầu vào 5 biến

III. Nhận xét: + Thuật toán chưa thực hiện được với trạng thái don’t care. + Thuật toán chưa tối ưu và dài. + Thuật toán mới chỉ thực hiện trên các minterm. + Thuật toán có thể thực hiện với nhiều biến. IV. CODE C++ QUINE MSCLUSKEY #include #include #include #include #include using namespace std; // Ham de chuyen tu thap phan sang he nhi phan string decToBin(int n, int sobien) { string nhiphan = ""; while (n != 0) { int i = n % 2; if (i == 0) nhiphan = "0" + nhiphan; else nhiphan = "1" + nhiphan; n = n / 2; }

int so_bit_thieu = sobien - nhiphan.length();

while (so_bit_thieu != 0) { nhiphan = "0" + nhiphan; so_bit_thieu--; }

return nhiphan; } class QM { public: int minterm; string xau;

int Sobit1(); QM() {};

// Day la ham tao

~QM() {};

// Day la ham huy

};

int QM::Sobit1() { int dem = 0; for (int i = 0; i < xau.length(); i++) { if (xau[i] == '1') dem++; } return dem; } bool Sosanh(QM a, QM b) { return (a.Sobit1() < b.Sobit1()); } string Ghep_2_xau(string a, string b) {

for (int i = 0; i < a.length(); i++) { if (a[i] != b[i]) a[i] = '-'; } return a; } // Ham de kiem tra xem 2 chuoi khac nhau may bit int Kiemtra(string a, string b) { int ktra = 0; for (int i = 0; i < a.length(); i++) { if (a[i] != b[i]) ktra++; }

return ktra; } // Ham tinh tong tat ca phan tu trong ma tran int sum_matrix(int** arr, int m, int n) { int sum = 0; for (int i = 0; i < m; i++) for (int j = 0; j < n; j++) sum += arr[i][j]; return sum; } string In_ra_dang_xau(string s) { string xau = ""; int dodai = s.length(); for (int i = 0; i < dodai; i++) { if (s[i] == '1') {

char c = 'a' + i; string x(1, c); xau += x; } else if (s[i] == '0') { char c = 'a' + i; string x(1, c); xau = xau + x + "'"; } else continue; } return xau; } int Tim_he_so_max(int* arr, int m) { int index = 0; int max = arr[0]; for (int i = 0; i < m; i++) { if (arr[i] > max) { max = arr[i]; index = i; } } return index; } class PI { public: vector index; string xau;

int check; nhom chua

// bien nay de kiem tra xem minterm da duoc cho vao

PI() { check = 0; }

}; void Tao_nhom(int sominterm, vector& DSPI, vector List, int& so_PI) { // Nhom cac minterm, tim ra PI bool ktrasophantuconlai = true; vector DScacnhom; vector DScopy; nhung o dang PI

// tao 1 danh sach moi lay tat ca thong tin tu danh sach QM ban dau

for (int i = 0; i < sominterm; i++) { PI pi; pi.index.push_back(List[i].minterm);

// Them chi so minterm vao danh

sach moi pi.xau = List[i].xau; DScopy.push_back(pi); } // Tim ra cac doi tuong ma chi khac nhau 1 phan tu, Ghep 2 xau va them vao danh sach cac nhom while (ktrasophantuconlai) { for (int i = 0; i < DScopy.size() - 1; i++) { for (int j = i + 1; j < DScopy.size(); j++) { if (Kiemtra(DScopy[i].xau, DScopy[j].xau) == 1) { PI b; b.xau = Ghep_2_xau(DScopy[i].xau, DScopy[j].xau); DScopy[i].check++; DScopy[j].check++;

for (int k = 0; k < DScopy[i].index.size(); k++) { b.index.push_back(DScopy[i].index[k]); } for (int l = 0; l < DScopy[j].index.size(); l++) { b.index.push_back(DScopy[j].index[l]); } DScacnhom.push_back(b); } } }

// Nhung doi tuong chua duoc danh dau se la PI for (int i = 0; i < DScopy.size(); i++) { if (DScopy[i].check == 0) { PI pi = DScopy[i]; DSPI.push_back(pi); } }

DScopy.clear(); // Xoa het du lieu trong danh sach copy va gan gia tri moi = danh sach cac nhom for (int i = 0; i < DScacnhom.size(); i++) { PI bienmoi = DScacnhom[i];

// sao chep du lieu tu DScacnhom[i] sang

bienmoi DScopy.push_back(bienmoi); }

// Kiem tra xem do dai danh sach cac nhom co rong hay khong if (DScacnhom.size() == 0) {

ktrasophantuconlai = false; } DScacnhom.clear();

// Xoa het du lieu trong danh sach cac nhom de tao lai tu dau

}

// Xoa cac phan tu bi trung trong danh sach PI for (int i = 0; i < DSPI.size() - 1; i++) { for (int j = i + 1; j < DSPI.size(); j++) { if (DSPI[i].xau == DSPI[j].xau) { DSPI.erase(DSPI.begin() + j); j--; } } }

// in ra danh sach PI so_PI = DSPI.size(); cout...