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:
Đăng nhận xét