Thuật Toán Quine MCCluskey
Mạch logic tổ hợp là một phần công cụ để chúng ta thiết kế các mạch điện tử. Bởi thế các phương pháp rút gọn mạch logic tổ hợp là một phần quan trọng trong kiến thức môn học Điện tử số. Nó có nhiều ứng dụng lớn trong nhiều lĩnh vực của điện tử.
Phương pháp Quine MC Cluskey là phương pháp rút gọn mạch logic tổ hợp có thể tối thiểu được hàm nhiều biến và có thể tiến hành rút gọn nhờ chương trình lập trình được trên máy tính.
Các bước tối thiểu hóa:
Gồm 4 bước cơ bản sau:
1. Lập bảng liệt kê các hạng tích dưới dạng nhị phân theo từng nhóm với số bit 1 giống nhau và xếp chúng theo số bit 1 tăng dần.
2. Gộp 2 hạng tích của mỗi cặp nhóm chỉ khác nhau 1 bit để tạo các nhóm mới. Trong mỗi nhóm mới, giữ lại các biến giống nhau, biến bỏ đi thay bằng một dấu ngang (-).
3. Lặp lại cho đến khi trong các nhóm tạo thành không cịn khả năng gộp nữa. Mỗi lần rút gọn, ta đánh dấu # vào các hạng ghép cặp được. Các hạng không đánh dấu trong mỗi lần rút gọn sẽ được tập hợp lại để lựa chọn biểu thức tối giản.
4. Lập bảng lựa chọn hàm.
Ta thiết lập các số hạng có thể có trong biểu thức bằng cách thay dấu gạch ngang bằng các giá trị 0 và 1 sau đó đánh dấu ký hiệu “x” dưới vị trí mà nó chứa số hạng đó.
Sau đó ta xem xét các cột chỉ chứa một dấu “x”. Các dấu “x” này đã bao quát hết tất cả các hạng tích của hàm đã cho. Do vậy, các biểu thức đó là các hạng tích đã tối giản.
Chương trình giải quyết được các bài toán phức tạp một cách nhanh chóng, kết quả được lưu trong file *.txt cùng thư mục của chương trình.
Mã nguồn:
#include<stdio.h>
#include<conio.h>
#include<math.h>
#include<string.h>
#define line printf("\n===================\n");
void doinhiphan(int x,int n,int minterm[],int nhiphan[][100]);
void nhap(int n,int minterm[]);
void sosanh(int x,int n,int nhiphan[][100],int &a,int &b);
void hienthi(int x,int nhiphan[][100],int b);
void ketqua(int x,int n,int nhiphan[][100],int a,int b,int &d);
void inraFILEhamnhap(int minterm[],int x,int n);
void inraFILErutgon(int nhiphan[][100],int b,int x);
void inraFILECACNHOM(int nhiphan[][100],int a,int b,int x,int d);
void inraFILEkq(int nhiphan[][100],int a,int b,int x,int d);
int main()
{
int x,n;
printf("Nhap vao so bien cua ham: ");
scanf("%d",&x);
printf("Nhap vao so minterm cua ham: ");
scanf("%d",&n);
int minterm[n],nhiphan[1000][100],a=0,b=n;//2 bien a,b danh dau lai khoang dau va cuoi mang sau 1 lan sosanh
int d=0;//dem so thu tu cac NHOM TUY CHON co the dai dien het cac phan tu con sot lai.
nhap(n,minterm);
inraFILEhamnhap(minterm,x,n);
doinhiphan(x,n,minterm,nhiphan);
line;
hienthi(x,nhiphan,b);
sosanh(x,n,nhiphan,a,b);
line;
hienthi(x,nhiphan,b);
inraFILErutgon(nhiphan,b,x);
line;
ketqua(x,n,nhiphan,a,b,d);
inraFILECACNHOM(nhiphan,a,b,x,d);
line;
hienthi(x,nhiphan,b);
inraFILEkq(nhiphan,a,b,x,d);
getch();
}
void doinhiphan(int x,int n,int minterm[],int nhiphan[][100])
{
for(int i=0;i<n;i++)
for(int j=0;j<x+1;j++)
{
nhiphan[i][j]=0;
}
for(int i=0;i<n;i++)
for(int j=0;minterm[i]>0;j++)
{
nhiphan[i][x-1-j]=minterm[i]%2;
minterm[i]=minterm[i]/2;
}
}
void nhap(int n,int minterm[])
{
for(int i=0;i<n;i++)
{
printf("Nhap minterm %d: ",i+1);
scanf("%d",&minterm[i]);
}
}
void hienthi(int x,int nhiphan[][100],int b)
{
for(int i=0;i<b;i++)
{
for(int j=0;j<x+1;j++)
{
printf("%d ",nhiphan[i][j]);
}
printf("\n");
if(nhiphan[i][x]==3) printf("\n----\n");
}
}
void sosanh(int x,int n,int nhiphan[][100],int &a,int &b)
{
int g,count2,kt=0,i,count2B/*khai bao o day de dung dc cho while*/;
do
{
count2B=0;//chi dung trong 1 chu ky cua vong for(i),neu count2B>0 tuc la van phai rut gon tiep
count2=0;//de dem so luot ghi lai 2minterm chi #nhau 1bit,sau do thay b=b+count2;
for(i=a;i<b;i++)
{
int count4=0;//kt minterm sot hay ko
for(int j=a;j<b;j++)
{
int count=0;//kiem tra 2 day minterm khac nhau 1 hay nhieu bit.
for(int k=0;k<x;k++)
{
if(nhiphan[i][k]!=nhiphan[j][k])
{
g=k;//danh dau k bang g, g chi co y nghia trong TH count==1.
count++;
}
}
if(count>1) count4++;
//truong hop # nhau 1 bit:
if(count==1)//lenh if trong vong for cua 'j'.
{
for(int k=0;k<x;k++)//coppy minterm da rut gon vao cuoi mang nhiphan[][].
{
if(k!=g)
nhiphan[b+count2][k]=nhiphan[i][k];
else nhiphan[b+count2][g]=2;//=2 thay cho dau '-', nhiphan[j][g] ko can phai =2.
}
//kiem tra xem da ton tai minterm nao giong no chua:
for(int m=b;m<b+count2;m++)
{
int count3=0;//kt ton tai minterm giong nhau ko.
for(int n=0;n<x;n++)
{
if(nhiphan[m][n]==nhiphan[b+count2][n])
count3++;
}
if(count3==x)
nhiphan[b+count2][g]=3;
}
if(nhiphan[b+count2][g]!=3)//neu ko co cai nao giong thi tang cac chi so len<=>luu no.
{
count2++;
count2B++;
nhiphan[b-1][x]=3;/*chu y trong vai TH*/ //danh dau cho~ cuoi cua 1 chu trinh ss de ham deplay chia khoang cho dep^^.
}
}//ket thuc TH #1.
}//ket thuc for(j)
//TH con sot minterm trong luot ss dau tien vi sai # >1 bit voi tat ca cac minterm con lai:
if(count4==b-a-1) //de dam bao: minterm nay #>2bit voi tat ca.
{
for(int k=0;k<x;k++)
{
nhiphan[b+count2][k]=nhiphan[i][k];//coppy minterm (#nhau 2bit tro len)nay vao cuoi mang nhiphan[][].
}
count2++;
}
}//ket thuc for(i)
if(count2!=0&&count2B>0)//dam bao luc ket thuc chu trinh (tuc count2==0&&count2B==0) thi ko can thay doi a,b
{
a=b;//2 bien a,b danh dau lai khoang dau va cuoi mang sau 1 lan sosanh
b=b+count2;
}
}while(count2B>0);//neu sau 1 chu ky sosanh ma count2B van =0 => ket thuc.
}
void ketqua(int x,int n,int nhiphan[][100],int a,int b,int &d)
{
int i,j,k,count;
printf("%d_%d_%d\n",n,a,b);
//1.reset cac minterm nhiphan[0->b][x]=0:
for(i=0;i<b;i++)
nhiphan[i][x]=0;
//2.danh dau cac cot chi chua 1 dau X:
for(i=a;i<b;i++)
{
for(j=0;j<n;j++)
{
count=0;
for(k=0;k<x;k++)
{
if(nhiphan[i][k]!=2&&nhiphan[i][k]!=nhiphan[j][k])
count++;
}
if(count==0)
nhiphan[j][x]++;//DANH DAU = SO LAN LAP LAI PHAN TU DO
}
}
//3.tu cac cot chi chua 1 dau X tim lai cac minterm tao ra dau X do:
for(i=0;i<n;i++)
{
if(nhiphan[i][x]==1)
for(j=a;j<b;j++)
{
count=0;
for(k=0;k<x;k++)
{
if(nhiphan[j][k]!=2&&nhiphan[i][k]!=nhiphan[j][k])
count++;
}
if(count==0)
nhiphan[j][x]=3;//DANH DAU (=3)
}
}
//4.DANH DAU CAC PHAN TU XUAT HIEN >1 LAN, NHUNG DA NAM TRONG CAC NHOM BAT BUOC:
for(i=a;i<b;i++)
{
if(nhiphan[i][x]==3)
for(j=0;j<n;j++)
{
count=0;
for(k=0;k<x;k++)
{
if(nhiphan[i][k]!=2&&nhiphan[i][k]!=nhiphan[j][k])
count++;
}
if(count==0)
nhiphan[j][x]=77;//DANH DAU: THUOC NHOM BAT BUOC (=77)
}
}
//5.TU CAC PHAN TU CON SOT LAI - CHUA NAM TRONG NHOM BAT BUOC(#77), DANH DAU TAM THOI CAC NHOM CO THE DAI DIEN CHO NO(=4):
for(i=0;i<n;i++)
{
if(nhiphan[i][x]!=77)
for(j=a;j<b;j++)
{
count=0;
for(k=0;k<x;k++)
{
if(nhiphan[j][k]!=2&&nhiphan[i][k]!=nhiphan[j][k])
count++;
}
if(count==0)
nhiphan[j][x]=4;//DANH DAU TAM THOI(=4), DE KT TIEP XEM CO DU DK DAI DIEN KO!
}
}
//6.KIEM TRA LAI CAC NHOM VUA DANH DAU (=4) XEM CO DAI DIEN HET CHO CAC PHAN TU CON SOT LAI KO:
for(i=a;i<b;i++)
{
if(nhiphan[i][x]==4)
{
count=0;
for(j=0;j<n;j++)
{
if(nhiphan[j][x]!=77)
for(k=0;k<x;k++)
{
if(nhiphan[i][k]!=2&&nhiphan[i][k]!=nhiphan[j][k])
count++;
}
}
if(count==0)
{
d++;
nhiphan[i][x]=30+d;//neu NHOM do dai dien dc het, thi danh dau (=3X) de tien sau nay in ra het cac TH KQ co the co.
}
}
}
//+++++++++++++++++++++++++++
//7A.hien thi cac minterm vua danh dau xong(CA NHOM BAT BUOC VA TUY CHON):
if(d==0)
{
count=0;
for(i=a;i<b;i++)
{
if(nhiphan[i][x]==3)
{
if(count==1) printf(" + ");
for(j=0;j<x;j++)
{
if(nhiphan[i][j]==1)
{
printf("%c",65+j);
count=1;
}
if(nhiphan[i][j]==0)
{
printf("%c",97+j);
count=1;
}
}
}
}
}
if(d!=0)
{
for(int e=1;e<=d;e++)
{
//7B.HIEN THI CAC NHOM BAT BUOC:
count=0;
for(i=a;i<b;i++)
{
if(nhiphan[i][x]==3)
{
if(count==1) printf(" + ");
for(j=0;j<x;j++)
{
if(nhiphan[i][j]==1)
{
printf("%c",65+j);
count=1;
}
if(nhiphan[i][j]==0)
{
printf("%c",97+j);
count=1;
}
}
}
}
//7C.HIEN THI CAC NHOM TUY CHON:
for(i=a;i<b;i++)
{
if(nhiphan[i][x]==30+e)
{
printf(" + ");
for(j=0;j<x;j++)
{
if(nhiphan[i][j]==1)
{
printf("%c",65+j);
count=1;
}
if(nhiphan[i][j]==0)
{
printf("%c",97+j);
count=1;
}
}
}
}
if(e!=d) printf("\nHOAC:\n");
}
}
}
void inraFILEhamnhap(int minterm[],int x,int n)
{
FILE *dtv;
dtv=fopen("DTV.txt","a+");
fprintf(dtv,"\n\nF(");
for(int i=0;i<x;i++)
{
if(i>0) fprintf(dtv,",");
fprintf(dtv,"%c",65+i);
}
fprintf(dtv,")= {");
for(int i=0;i<n;i++)
{
if(i>0) fprintf(dtv,",");
fprintf(dtv,"%d",minterm[i]);
}
fprintf(dtv,"}\n");
fclose(dtv);
}
void inraFILErutgon(int nhiphan[][100],int b,int x)
{
FILE *dtv;
dtv=fopen("DTV.txt","a+");
for(int i=0;i<b;i++)
{
if(i+1<10) fprintf(dtv,"0%d ",i+1);
if(i+1>=10) fprintf(dtv,"%d ",i+1);
for(int j=0;j<x;j++)
{
if(nhiphan[i][j]==2) fprintf(dtv,"-");
else
fprintf(dtv,"%d",nhiphan[i][j]);
}
fprintf(dtv,"\n");
if(nhiphan[i][x]==3) fprintf(dtv,"----\n");
}
//fprintf(dtv,"========================\n");
fclose(dtv);
}
void inraFILECACNHOM(int nhiphan[][100],int a,int b,int x,int d)
{
FILE *dtv;
dtv=fopen("DTV.txt","a+");
if(d==0)
{
fprintf(dtv,"----\n");
fprintf(dtv,"NHOM BAT BUOC: ");
for(int i=a;i<b;i++)
{
for(int j=0;j<x;j++)
{
if(nhiphan[i][x]==3)
if(nhiphan[i][j]==2) fprintf(dtv,"-");
else fprintf(dtv,"%d",nhiphan[i][j]);
}
if(nhiphan[i][x]==3&&i!=b-1) fprintf(dtv," ; ");
}
}
if(d!=0)
{
fprintf(dtv,"----\n");
fprintf(dtv,"NHOM BAT BUOC: ");
for(int i=a;i<b;i++)
{
for(int j=0;j<x;j++)
{
if(nhiphan[i][x]==3)
if(nhiphan[i][j]==2) fprintf(dtv,"-");
else fprintf(dtv,"%d",nhiphan[i][j]);
}
if(nhiphan[i][x]==3&&i!=b-1) fprintf(dtv," ; ");
}
fprintf(dtv,"\nNHOM TUY CHON: ");
for(int i=a;i<b;i++)
{
for(int j=0;j<x;j++)
{
if(nhiphan[i][x]>=31)
if(nhiphan[i][j]==2) fprintf(dtv,"-");
else fprintf(dtv,"%d",nhiphan[i][j]);
}
if(nhiphan[i][x]>=31&&nhiphan[i][x]!=30+d) fprintf(dtv," ; ");
}
}
fprintf(dtv,"\n========================\n");
fclose(dtv);
}
void inraFILEkq(int nhiphan[][100],int a,int b,int x,int d)
{
FILE *dtv;
dtv=fopen("DTV.txt","a+");
//TH CHI CO CAC NHOM BAT BUOC, KO CO NHOM TUY CHON!
if(d==0)
{
fprintf(dtv,"F(");
for(int i=0;i<x;i++)
{
if(i>0) fprintf(dtv,",");
fprintf(dtv,"%c",65+i);
}
fprintf(dtv,")= ");
int count=0;
for(int i=a;i<b;i++)
{
if(nhiphan[i][x]==3)
{
if(count==1) fprintf(dtv," + ");
for(int j=0;j<x;j++)
{
if(nhiphan[i][j]==1)
{
fprintf(dtv,"%c",65+j);
count=1;
}
if(nhiphan[i][j]==0)
{
fprintf(dtv,"%c",97+j);
count=1;
}
}
}
}
}
//TH CO CA NHOM BAT BUOC VA NHOM TUY CHON!
if(d!=0)
{
for(int e=1;e<=d;e++)
{
fprintf(dtv,"F(");
for(int i=0;i<x;i++)
{
if(i>0) fprintf(dtv,",");
fprintf(dtv,"%c",65+i);
}
fprintf(dtv,")= ");
//HIEN THI CAC NHOM BAT BUOC:
int count=0;
for(int i=a;i<b;i++)
{
if(nhiphan[i][x]==3)
{
if(count==1) fprintf(dtv," + ");
for(int j=0;j<x;j++)
{
if(nhiphan[i][j]==1)
{
fprintf(dtv,"%c",65+j);
count=1;
}
if(nhiphan[i][j]==0)
{
fprintf(dtv,"%c",97+j);
count=1;
}
}
}
}
//HIEN THI CAC NHOM TUY CHON:
for(int i=a;i<b;i++)
{
if(nhiphan[i][x]==30+e)
{
fprintf(dtv," + ");
for(int j=0;j<x;j++)
{
if(nhiphan[i][j]==1)
{
fprintf(dtv,"%c",65+j);
count=1;
}
if(nhiphan[i][j]==0)
{
fprintf(dtv,"%c",97+j);
count=1;
}
}
}
}
if(e!=d) fprintf(dtv,"\nHOAC:\n");
}
}
fprintf(dtv,"\n========================\n");
fclose(dtv);
}
//14s/2a/2010d
//tjtanja
0 nhận xét: on "[Code C] Thuật Toán Quine MCCluskey"
Đăng nhận xét