一种Reed-Muller逻辑电路极性快速转换方法

摘要

本发明公开了一种Reed-Muller逻辑电路极性快速转换方法，通过删除不同乘积项对应的逻辑覆盖中公共部分的方法实现RM逻辑的固定极性转换，提出的方法避免了以往RM逻辑极性转化过程中采用乘积项展开、搜索和删除等步骤，整个搜索过程不需要对乘积项进行多次展开和重复乘积项搜索和删除操作，整个过程只需要1次的乘积项展开且不需要重复性检查，从而使得提出的方法在RM逻辑极性转换时转换速度更快，能处理的电路规模更大，本发明的方法在极性搜索方面具有更高的效率。

主权项

一种RM逻辑电路极性转化的方法，其特征在于定义被转换的电路对应的逻辑函数为f；电路的输入变量数定义为m，输出变量数定义为n；定义构成f的乘积项的集合为C；p_i,p_j为属于集合C的任意一对乘积项；定义对于集合C中任一乘积项中的任一变量，用“0”表示该变量以反变量形式出现，“1”表示该变量以原量形式出现，“2”表示该变量不出现；定义符号[p_i]_k表示乘积项p_i的第k位的取值，且0≤k≤m‑1；将f的各位变量极性用H表示；H中的“0”表示该位变量在f中以原变量形式出现；H中的“1”表示该位变量在f中以反变量形式出现；将H中第k位的取值用[H]_k表示；乘积项p_i与极性H之间的第k位“位极性”运算用Υ_k(p_i,H)表示，并规定当[p_i]_k＝[H]_k时，有Υ_k(p_i,H)＝4，否则Υ_k(p_i,H)＝[p_i]_k；用Λ_k([p_i]_k,[p_j]_k,[H]_k)表示乘积项p_i,p_j关于H的第k位相交运算，并规定Λ_k(2,4,1)＝2，Λ_k(2,4,0)＝2，Λ_k(2,2,1)＝2，Λ_k(2,2,0)＝2，Λ_k(4,2,1)＝0，Λ_k(4,2,0)＝1，Λ_k(4,0,1)＝2，Λ_k(4,1,0)＝2，Λ_k(1,4,0)＝1，Λ_k(0,4,1)＝0，Λ_k(1,1,0)＝1，Λ_k(0,0,1)＝0；其他[p_i]_k，[p_j]_k和[H]_k的取值组合下，乘积项p_i,p_j关于H不相交，并用表示；用Γ_k(Υ_k(p_i,H),Υ_k(p_j,H),[H]_k)表示乘积项p_i,p_j关于H的第k位互斥运算，其中Υ_k(p_i,H),Υ_k(p_j,H)的取值为0，1，2或4，[H]_k的取值为0或1；并规定Γ_k(4,0,1)＝2，Γ_k(4,2,1)＝0，Γ_k(4,1,0)＝2，Γ_k(4,2,0)＝1，Γ_k(4,4,1)＝4，Γ_k(4,4,0)＝4，其他Υ_k(p_i,H),Υ_k(p_j,H)和[H]_k取值组合下，Γ_k(Υ_k(p_i,H),Υ_k(p_j,H),[H]_k)运算结果定义为空；具体步骤为：步骤⑴.定义一个空的集合，用C_p表示，执行步骤⑵；步骤⑵.利用不相交乘积项转换方法将集合C中的乘积项转换成不相交乘积项，执行步骤⑶；步骤⑶.在集合C中任取一个乘积项p′_i，对p′_i逐位进行“位极性”运算，将p′_i的第k位取值[p′_i]_k用Υ_k(p′_i,H)替代，完成p′_i中的每一位变量的“位极性”运算后，将结果存于C_p中，并在集合C中删除p′_i；步骤⑷.检查集合C中的每一个乘积项是否都与H进行“位极性”运算，如果是，删除集合C，并执行步骤⑸，否则，执行步骤⑶；步骤⑸.在集合C_p中任取一对乘积项，记为p″_i和p″_j，判断p″_j和p″_j中是否存在某一位变量使得0≤k≤(m‑1)；如果不存在，执行步骤⑹，否则执行步骤⑻；步骤⑹.依次检查p″_i中各位取值，如p″_i中第k位取值为4，k≤m‑1，则生成一个新的乘积项，用p_k表示；其中p_k的前(k‑1)位取值等于p″_i和p″_j关于H的相交结果，即[p_k]_u＝Λ_u([p″_i]_u,[p″_j]_u,[H]_u)，0≤u≤k‑1，p_k的第k位取值等于Γ_k(Υ_k(p″_i,H),Υ_k(p″_j,H),[H]_k)，p_k的第(k+1)位到(m‑1)位的值等于p″_i的第(k+1)位到(m‑1)位的值；若p_k≠p″_i，则将p_k存储到集合C_p中，否则不存储；步骤⑺.判断是否对p″_i全部m个位的取值情况进行了检查，如果是，则执行步骤⑻，否则执行步骤⑹；步骤⑻.依次检查p″_j中各位取值，如p″_j中第s位取值为4，s≤m‑1，则生成一个新的乘积项，用p_s表示；其中p_s的前s‑1位取值等于p″_j和p″_i关于H的相交结果，即[p_s]_t＝Λ_t([p″_j]_t,[p″_i]_t,[H]_t)，0≤t≤s‑1，p_s的第s位取值等于Γ_s(Υ_s(p″_j,H),Υ_s(p″_i,H),[H]_s)，p_s的第(s+1)位到(m‑1)位的值等于p″_j的第(s+1)位到(m‑1)位的值；若p_s≠p″_j，则p_s存储到C_p中，否则不存储；步骤⑼.判断是否对p″_j全部m个位的取值情况进行了检查，如果是，则删除p″_i和p″_j并执行步骤⑽，否则执行步骤⑻；步骤⑽.判断是否对C_p中所有任意二个乘积项都进行了关于H的相交检查，如果是，执行步骤⑾，否则执行步骤⑸；步骤⑾.极性为H的RM逻辑表达式中乘积项的个数定义为其中w表示C_p中乘积项个数，v表示一个乘积项中“4”的个数，(2^v)_r表示C_p中第r个乘积项展开为对应的RM逻辑表达式中乘积项个数为2^v；将C_p中每个乘积项中取值为“4”的位分别用“0”和“1”代替，然后以二进制方式展开，并将展开位中取值与极性表达式H中对应位相同的位用“‑”替换，同时将“2”对应的位也用“‑”替换，得到极性为H的RM逻辑表达式。