【《面向FPGA的开关互联网格综合、优化实现分析案例》4700字】

面向FPGA的开关互联网格综合、优化实现分析案例目录TOC\o"1-3"\h\u22212面向FPGA的开关互联网格综合、优化实现分析案例 1242751.1开关互联网格的数据结构表示 1287501.2开关互联网格的优化实现原理 1196071.3真值表计算及输入输入信号数量和逻辑表达式识别的实现 372961.4对开关按列化简的实现 5311431.5整体组合逻辑电路的化简实现 7189441.6.系统测试 9对系统程序的设计主要分三大部分，即逻辑表达式识别并计算其对应的真值表部分，自定义可复用二选一选择器化简函数和组合逻辑电路的化简并构建电路部分。1.1开关互联网格的数据结构表示栈是属于一种线性表，对数据的存储遵循先进后出原则，即一组数据存储依次存入到栈中，如果要读取或删除栈中的数据则只能读取或删除这组数据的最后一个数据，依次往前，类似将枪械的弹匣压入子弹和子弹出匣，我们将栈的顶端表示为栈顶，而栈的底端表示为栈底，对栈的操作主要有出栈操作和入栈操作。在C语言中要设计一个栈结构的线性表用来存储数据，需要大量的运用指针操作，我们在设置一个栈时要分配一定的空间来存储我们的数据，这个空间需要我们自己定义。通过指针我们需要首先设置栈顶、栈底，当利用指针将栈顶指针和栈底指针相重合，即栈顶减去栈底的空间为0时，这里表示当前栈为空，即为空栈；而当栈顶指针和栈底指针相减，即栈顶减去栈底的空间等于我们所设置的空间时，这里表示当前栈为满，即为满栈。对于数据进行入栈，只需要将数据的分配空间，将数据放入，然后将栈顶上移加一，这样就存入数据；而出栈则反之，将数据释放，并且栈顶指针需要下移减一。通过这种操作完成对数据的存储读取。1.2开关互联网格的优化实现原理对组合逻辑电路的化简由于存在对一个二选一选择器在将对应的真值表对比后，若能化简则需要对本二选一选择器保留，而其关联的两个二选一选择器我们在进行下一级的化简时，需要分别单独进行化简查看，如果能化简，则其相对应二叉树的右节点的二选一选择器以及它所关联的所有二选一选择器都可以省略，然后对于下一级则可以直接查看相对应二叉树的左节点的二选一选择器。由于组合逻辑电路是类似于二叉树的结构，我们对三输入的组合逻辑电路F=ab’c+a’c’，其电路结构与真值表如表4-1所示。我们采取先对编号SW[0]的二选一选择器对比真值表化简，可以看到由于将其所对应的真值表拆分两半后，上下不一致，所以我们需要将SW[0]置1，表示在电路中需要保留，对于下一列来说，其与SW[0]关联的SW[1]和SW[2]二选一选择器需要分别进行化简，然后第一列判断完毕，接下来我们利用二叉树中父子节点的关系，由循环结构将数组SW中的元素序号满足X=2X+1的关系把SW[0]转换成SW[1]，由于SW[2]也需要化简，我们这里将SW[2]的序号设置中断保留，等完成SW[1]化简完成后再来对SW[2]化简，接着又利用真值表判断SW[1]是否需要化简，我们可以看到可以化简，这意味这SW[1]和SW[4]置零，再由循环结构将数组SW中的元素序号满足X=2X+1的关系把SW[1]转换成SW[3]，对SW[3]的化简中由于两个真值结果不同，则需要保留，置1。这时由于我们返回到先前中断标记的待化简的序号SW[2]二选一选择器，以同样的真值表对比我们保留SW[2]，转向查看序号SW[5]的二选一选择器，对SW[6]再设置中断保留，之后SW[5]由真值表对比后需要保留置1，我们查看SW[6],对比真值表我们将SW[6]置1。这样我们完成对此组合逻辑电路的化简。因此，通过上述规律，我们发现对任意输入的组合逻辑电路化简时，得益于二叉树结构，我们对于上述采取的化简顺序类似于二叉树的前序序列进行化简。表41逻辑式F=ab’c+a’c’电路结构与真值表真值表电路结构abcF00010010010101101000101111001110DADABCEFG图4-1三层满二叉树结构图1.3真值表计算及输入输入信号数量和逻辑表达式识别的实现代码如下： intIn_put=0; intdex=0; printf("请输入逻辑电路输入个数：\n"); scanf("%d",&In_put); for(;dex<pow(2,In_put)-1;dex++)//所有开关置零 { sw[dex]=0; } inti=1; intf[12]={0};//这里代表f[0]=a,f[1]=b,f[2]=c...以此类推 //计算给定逻辑表达式的真值表 sqStackTT; InitStack(&TT); charstr[100]={0}; size_tchar_len; printf("请输入逻辑表达式(以‘#’为结束标志)：\n"); scanf("%s",str);char_len=strlen(str); for(dex=0;dex<pow(2,In_put);dex++) { intTT_sum=0; intk,result=1,j=dex; intm=In_put; for(;m>0;m--) { f[m-1]=j%2; if(dex>1){j=j/2;} elsebreak; } for(k=0;k<char_len;k++) { if(str[k]>=97&&str[k]<=108)//如果字符是‘a’到‘l’ { intbianhao=str[k]-97; if(str[k+1]==39)//判断字符后是否需要非运算 { result=result&&(!f[bianhao]); } elseresult=result&&f[bianhao]; } elseif(str[k]==43||str[k]==35)//判断字符是否为‘+’ { Push(&TT,result); result=1; } } intstacklen=StackLen(TT); for(;stacklen>0;stacklen--) { Pop(&TT,&TT_sum); truetable[dex]=truetable[dex]||TT_sum; } printf("真值表：%d\n",truetable[dex]); }程序解释：这里为了做到程序能对任意的逻辑表达式进行化简，设计了键盘输入表达式。先确定逻辑变量的个数，将各个逻辑变量用数组f中元素替代，依照顺序，f[0]代表a，f[1]代表b，以此类推，这里将逻辑变量改成数组是为了方便能识别表达式中的逻辑变量，否则在计算机上只代表ASCII码，无法进行计算。之后利用gets函数键入需要化简的表达式，对于这一段字符串，我们先确定字符串的长度，这里对输入的逻辑表达式格式为两个逻辑变量a，b之间进行与运算（&&）直接写成ab，对于非运算（！）则在相应的逻辑变量后加上单引号（’），而逻辑变量a、b之间或运算（||）则写成a+b，用加号替换或运算。由于逻辑变量都是在0或1之间改变，同时对于n输入的逻辑表达式则有2n个真值结果，利用for函数循环将0到2n−1接着对逻辑表达式的运算关系进行识别并计算，若字符是字母则采用乘运算，并将结果赋值给变量result，但字符后如果识别到单引号字符，则表示非，需要先让此字符非运算后再相乘，把结果赋值给result，若字符识别为加号，则需要将上述乘积项的结果存入到我们我们准备的栈中，采用“#”作为我们对字符串表达式的识别结束，这时，我们把栈中的数据出栈、相加，其结果为布尔量，即为当前的真值表结果，这样循环完成对任意组合逻辑表达式的真值表求解，都存入定义的数组truthtable的元素中。1.4对开关按列化简的实现代码如下：intcmp(intstart,intdistance)//带入起始值(start)和间隔(distance){ inttime=0; intk; for(k=0;k<distance;k++) { if(truetable[start]==truetable[start+distance]) { time++; start++; } else break; } returntime;}intJudge(ElemTypexuhao,intJ_In_put)//xuhao表示为开关序号{ intrank=1;//存放当前开关所在列数 intJ_num=0;//存放需要分开比较的下节点开关序号 while(xuhao+1-pow(2,rank-1)>=pow(2,rank-1))//判断开关序号在第几列 { rank++; } intt=cmp((xuhao+1-pow(2,rank-1))*pow(2,J_In_put-rank+1),pow(2,J_In_put-rank)); if(t==pow(2,J_In_put-rank)){J_num=-1;} else { sw[xuhao]=1;//当前开关置1 J_num=2*xuhao+2; } returnJ_num;}程序解释：上述自定义了一个cmp函数，主要是利用真值表比较，根据比较的次数返回一个结果来为后续判断对应的二选一选择器的化简，是通过比较其对应的真值表对半拆分相互比较，我们对任意二选一选择器的比较时真值表拆分的两部分标注为上下两部分，对于一个n输入的组合逻辑电路，第一列的二选一选择器只有一个，需要比较真值表中的上部分真值表第1个数据和下部分真值表第1个比较，接着上部分真值表第2个数据和下部分真值表第2个比较，以此增加序号，需要比较2n−1次，这些上下部分真值表相互比较的数据之间的序号间隔为2n−1，通过规律我们看到只有满足2n−1次结果相同才能让此二选一选择器化简，而第二列的任意一个二选一选择器需要比较2n−2次，第三列的二选一选择器需要比较2n−3（2通过如此方式我们设计Judge函数来方便我们通过对二选一选择器标记0或1来判断该项是否需要化简。对于置1的二选一选择器，其相连的两个二选一选择器需要进一步分开做出判断。1.5整体组合逻辑电路的化简实现代码如下：ElemTypetab1=0;//定义从哪个开关开始判断的标号 sqStacks;//定义栈名 intlen,number,tab2;//len表示栈中容量，number表示放入栈中数字，tab2表示放入栈中开关标号 InitStack(&s);//栈初始化 while(tab1<=pow(2,In_put)-2) { tab2=Judge(tab1,In_put); tab1=2*tab1+1; if(tab2<=pow(2,In_put)-2) { if(tab2!=-1) { Push(&s,tab2); } } } len=StackLen(s); while(len!=0) { Pop(&s,&number); while(number<=pow(2,In_put)-2) { tab2=Judge(number,In_put); number=2*number+1; if(tab2<=pow(2,In_put)-2) { if(tab2!=-1) { Push(&s,tab2); } } elsebreak; } len=StackLen(s); } printf("各开关化简结果：\n"); for(dex=0;dex<pow(2,In_put)-1;dex++) {printf("sw[%d]=%d\n",dex,sw[dex]);} return0;}程序解释：利用栈数据结构对组合逻辑电路进行化简，对于第一个开关先通过算法比较，若本开关不能化简，则输出其右子节点开关序号放入栈中，反之则不需要此操作，然后转入到其左子节点开关进行比较化简，以此重复上述步骤比较到该电路最后一层开关；接着取栈中数据一个序号作为开始，重复第一个开关化简的过程，以此往复，将所有开关化简完成。1.6.系统测试 任意输入一个6输入的FPGA组合逻辑电路，其实现的逻辑功能用逻辑表达式如下：F图4-2F=a'bc+cf'+acd'+bc'e'+ef的化简结果图4-2F=a'bc+cf'+acd'+bc'e'+ef的化简结果图4-4F=a'bc+cf'+acd'+bc'e'+ef查找表再优化图4-4F=a'bc+cf'+acd'+bc'e'+ef查找表再优化图4-3F=a'bc+cf'+acd'+bc'e'+ef优化后电路再任意输入一个12输入的FPGA组合逻辑电路，其实现的逻辑功能用逻辑表达式如下：F图4-512输入逻辑程序优化结果以及电路结构图4-512输入逻辑程序优化结果以及电路结构源程序：#include<stdio.h>#include<stdlib.h>#include<math.h>#include<stdbool.h>#defineSTACK_INIT_SIZE20//栈的空间设置为20#defineSTACKINCREMENT10//如果空间不够就加大10个空间booltruetable[4050];//定义真值表输出数组intsw[4050];//定义开关初始数组typedefintElemType;//将字符型定义为关键字ElemTypetypedefstruct{ ElemType*base;//栈底 ElemType*top;//栈顶 intstackSize;//栈的容量}sqStack;//定义结构体命名为sqStack，也是此栈的名称//栈的初始化函数voidInitStack(sqStack*s)//sqStack类型的指针{ s->base=(ElemType*)malloc(STACK_INIT_SIZE*sizeof(ElemType));//栈底地址分配 if(!s->base)//地址分配失败就退出 { exit(0); } s->top=s->base;//成功就栈顶与栈底指向同一位置 s->stackSize=STACK_INIT_SIZE;//初始栈空间为20}//压栈函数voidPush(sqStack*s,ElemTypee)//指针s和要压入栈的数据e{ if(s->top-s->base>=s->stackSize)//检查栈是否满了，用顶指针减去基指针是否大于容量 { s->base=(ElemType*)realloc(s->base,(s->stackSize+STACKINCREMENT)*sizeof(ElemType));//扩大容量 if(!s->base)//检查是否分配失败 { exit(0); } } *(s->top)=e;//取地址将e赋值给栈顶 s->top++;//栈顶上移}//出栈函数voidPop(sqStack*s,ElemType*e){ if(s->top==s->base)//检查栈是否取空 { return;//是则返回 } *e=*--(s->top);}//求栈当前容量的函数intStackLen(sqStacks){ return(s.top-s.base);}//比较函数intcmp(intstart,intdistance)//带入起始值(start)和间隔(distance){ inttime=0; intk; for(k=0;k<distance;k++) { if(truetable[start]==truetable[start+distance]) { time++; start++; } else break; } returntime;}//判断开关是否为0/1函数intJudge(ElemTypexuhao,intJ_In_put)//xuhao表示为开关序号{ intrank=1;//存放当前开关所在列数 intJ_num=0;//存放需要分开比较的下节点开关序号 while(xuhao+1-pow(2,rank-1)>=pow(2,rank-1))//判断开关序号在第几列 { rank++; } intt=cmp((xuhao+1-pow(2,rank-1))*pow(2,J_In_put-rank+1),pow(2,J_In_put-rank)); if(t==pow(2,J_In_put-rank)){J_num=-1;} else { sw[xuhao]=1;//当前开关置1 J_num=2*xuhao+2; } returnJ_num;}//主函数intmain(){ intIn_put=0; intdex=0; printf("请输入逻辑电路输入个数：\n"); scanf("%d",&In_put); for(;dex<pow(2,In_put)-1;dex++)//所有开关置零 { sw[dex]=0; } inti=1; intf[12]={0};//这里代表f[0]=a,f[1]=b,f[2]=c...以此类推 //计算给定逻辑表达式的真值表 sqStackTT; InitStack(&TT); charstr[100]={0}; size_tchar_len; printf("请输入逻辑表达式(以‘#’为结束标志)：\n"); scanf("%s",str);char_len=strlen(str); for(dex=0;dex<pow(2,In_put);dex++) { intTT_sum=0; intk,result=1,j=dex; intm=In_put; for(;m>0;m--) { f[m-1]=j%2; if(dex>1){j=j/2;} elsebreak; } for(k=0;k<char_len;k++) { if(str[k]>=97&&str[k]<=108)//如果字符是‘a’到‘l’ { intbianhao=str[k]-97; if(str[k+1]==39)//判断字符后是否需要非运算 { result=result&&(!f[bianhao]); } elseresult=result&&f[bianhao]; } elseif(str[k]==43||str[k]==35)//判断字符是否为‘