CN111159968B - Area optimization method of MPRM circuit - Google Patents

Abstract

The invention discloses an area optimization method of an MPRM circuit, which comprises the steps of firstly expressing the MPRM circuit by adopting a function expression, then converting the function expression of the MPRM circuit into an MPRM expression with P polarity by utilizing a polarity conversion method to obtain the MPRM expression with P polarity, then associating each parameter of the area optimization of the MPRM circuit with each parameter of a discrete three-value particle swarm algorithm to construct an adaptability function of the area optimization, and finally carrying out the area optimization by adopting the discrete three-value particle swarm algorithm based on the adaptability function; the method has the advantages of high searching efficiency, strong local optimizing capability and good optimizing effect.

Description

An Area Optimization Method for MPRM Circuits

Technical Field

The present invention relates to an area optimization method, and in particular to an area optimization method for an MPRM circuit.

Background Art

Fixed-polarity Reed-Muller (FPRM) circuits usually have two types of logic function expressions. In the first type of logic function expression of the FPRM circuit, the variables only exist in the original variable state or only exist in the inverse variable state. In the second type of logic function expression of the FPRM circuit, the variables can exist in both the original variable state and the inverse variable state. The difference in the states of variables in the logic function expression of the FPRM circuit leads to differences in the sizes of the polarity spaces they correspond to. Taking the logic function of the MPRM circuit with n input variables as an example, the polarities of its logic function are as high as ³ⁿ , and the total number of logic function expressions of the MPRM circuit under different polarities is also as high as ³ⁿ . The complexity of the logic function expressions of MPRM circuits with different polarities is different, and the area size of the corresponding MPRM circuits is also large or small.

At present, the area optimization of MPRM circuits is essentially to search for an optimal polarity (or a group of polarities) in the entire polarity space, so that the MPRM circuit corresponding to the polarity uses the smallest number of gate circuits, thereby minimizing the area. For small and medium-sized MPRM circuits, we can use an exhaustive algorithm to search the entire small polarity space, but for large-scale or even ultra-large-scale MPRM circuits, there are too many polarities, and the search polarity space increases dramatically, so the exhaustive algorithm is not feasible in terms of running time. Genetic algorithm is a commonly used intelligent algorithm with high search efficiency. It can be used for area optimization of large-scale MPRM circuits, but it has a slow convergence speed, weak local optimization ability, and the final area optimization effect is poor.

Summary of the invention

The technical problem to be solved by the present invention is to provide an area optimization method for an MPRM circuit with high search efficiency, strong local optimization capability and good optimization effect.

The technical solution adopted by the present invention to solve the above technical problem is: an area optimization method of an MPRM circuit, comprising the following steps:

(1) The MPRM circuit is represented by a function expression, which is expressed by formula (1):

式中

的出现形式和i_k相关，若i_k＝1，

若i_k＝0，

其中

为x_k的反变量；a_i,c为第i个最小项系数，且a_i,c∈{0，1}，若m_i在f(x_n-1,x_n-2,…,x₀)中出现，则a_i,c＝1，否则a_i,c＝0；Where n is the number of input variables of the function f( _xn-1 , _xn-2 , ..., _xk , ..., _x0 ), (xn _-1 , _xn-2 , ..., _xk , ..., x0) is the n input variables of the function f(xn _-1 , _xn-2 , ..., _xk , ..., _x0 ), _xk is the k+1th input variable, k = 0, 1, 2, ...n- ₁ , ∑ represents the OR operator, i is the ordinal number of the largest term, i is represented in binary as _{in-1 in-2} ...i _k ...i ₀ ; _mi is the i-th smallest term, and its symbolic representation is

In the formula

The appearance of is related to i _k . If i _k = 1,

If i _k = 0,

in

is the inverse variable of x _k ; a _i,c is the coefficient of the ith minimum term, and a _i,c ∈{0, 1}, if _mi appears in f(x _n-1 ,x _n-2 ,…,x ₀ ), then a _i,c ＝1, otherwise a _i,c ＝0;

(2) The function expression of the MPRM circuit is converted into the MPRM expression of P polarity by using the polarity conversion method, and the MPRM expression of P polarity is obtained. The MPRM expression of P polarity is expressed by formula (2):

为异或运算符号，π_i为第i个与项，用符号表示为

P为极性值，其三进制数的表示形式为(P_n-1P_n-2…P_k…P₀)，i_k和p_k一起决定

的形式，如果π_i在f^(P)(x_n-1,x_n-2,…,x₀)中存在，那么与项系数b_i,c＝1，否则b_i,c＝0；

与ik和p_k的关系为：当p_k＝0，i_k＝0或1时，

以原变量x_k出现；当p_k＝1，i_k＝0或1时，

以反变量

出现；当p_k＝2，i_k＝1时，

以原变量x_k的形式出现；当p_k＝2，i_k＝0时，

以反变量

的形式出现；in,

is the XOR operator symbol, π _i is the ith AND term, and is represented by

P is the polarity value, and its ternary number representation is (Pn _{- 1Pn-2} … _Pk … _P0 ), i _k and p _k together determine

In the form of, if π _i exists in f ^(P) (x _n-1 ,x _n-2 ,…,x ₀ ), then the coefficient of the term b _i,c ＝1, otherwise b _i,c ＝0;

The relationship between ik and p _k is: when p _k = 0, i _k = 0 or 1,

appears as the original variable x _k ; when p _k = 1, i _k = 0 or 1,

Inverse variable

appears; when p _k = 2, i _k = 1,

Appears in the form of the original variable x _k ; when p _k = 2, i _k = 0,

Inverse variable

Appear in the form of;

(3) Associate the parameters of the MPRM circuit area optimization with the parameters of the discrete ternary particle swarm algorithm: define the number of input variables n in the MPRM expression of P polarity as the search space dimension of the discrete ternary particle swarm, define the polarity in the MPRM expression of P polarity as the particle of the ternary diversity particle swarm, and define the ternary number of the polarity value P in the MPRM expression of P polarity of the MPRM circuit as the particle position;

(4) The number of particles in the discrete three-value particle swarm is set to D, where D is an integer greater than or equal to 50 and less than or equal to 100, and the maximum number of iterations is set to T, where T is an integer greater than or equal to 100 and less than or equal to 150;

(5) Set the fitness function of the MPRM circuit area, and record the fitness as fitness(area). Fitness(area) is expressed using formula (3):

fitness(area)＝1.0/(no_of_and+no_of_xor)*1000 (3)

In formula (3), * is the multiplication symbol, “/” is the division symbol, no_of_and is the number of AND terms in the MPRM expression of P polarity, and no_of_xor is the number of XOR terms in the MPRM expression of P polarity;

(6) Initializing the discrete three-valued particle swarm: randomly initializing the speed of each particle in the discrete three-valued particle swarm, the position of each particle, the current individual optimal position of each particle, the current global optimal position of the discrete three-valued particle swarm, and the fitness value of the MPRM circuit area corresponding to the MPRM expression corresponding to the polarity of each particle position;

(7) Set the number of iterations, record it as t, perform an initial transformation on t, and set t = 1;

(8) Perform the tth generation update of discrete ternary particle swarm, specifically:

A. Use the motion equation of particles in the discrete three-valued particle swarm to update the velocity and position of each particle in the ion swarm. The motion equation of particles in the discrete three-valued particle swarm is shown in equations (4), (5) and (6):

v _fd (t)＝wv _fd (t-1)+c ₁ r ₁ (p _fd (t-1)-x _fd (t-1))+c ₂ r ₂ (p _gd (t-1)-x _fd (t-1)) (4)

x _fd (t)＝round(S _fd +2×σ×randn()) (5)

式中w_start表示初始权重，w_end表示最终权重，初始惯性权重w_start＝0.9，终止惯性权重w_end＝0.4。T表示最大迭代数，v_fd(t)表示第t代更新得到的第f个粒子的速度，x_fd(t)表示第t代更新得到的第f个粒子的位置，f＝1,2,…,D，当t＝1时，x_fd(t-1)表示第f个粒子的初始位置，p_fd(t-1)表示第f个粒子初始的个体最优位置，p_gd(t-1)表示粒子群初始的全局最优位置，v_fd(t-1)表示第f个粒子的初始速度，当t≥2时，x_fd(t-1)表示第f个粒子在第t-1代更新得到的位置，p_fd(t-1)表示第f个粒子在第t-1代更新完成后的个体最优位置，p_gd(t-1)表示粒子群在第t-1代更新完成后的全局最优位置，v_fd(t-1)为表示第f个粒子在第t-1代更新后的速度，e表示自然对数的底，σ为权值且σ＝0.2，randn()为标准正态分布函数，round()表示四舍五入取整，上式(5)中，当计算得到的x_fd(t)为大于2的整数时，令x_fd(t)＝2,当计算得到的x_fd(t)为小于0的整数时，令x_fd(t)＝0，当计算得到的x_fd(t)为大于等于1且小于等于2的整数时，x_fd(t)的取值为其计算值。Where c ₁ and c ₂ are learning factors, c ₁ = c ₂ = 1.5, r ₁ and r ₂ are random numbers greater than or equal to 0 and less than or equal to 1, w is the inertia weight,

Where w _start represents the initial weight, w _end represents the final weight, the initial inertia weight w _start = 0.9, and the final inertia weight w _end = 0.4. T represents the maximum number of iterations, v _fd (t) represents the velocity of the fth particle updated in the tth generation, x _fd (t) represents the position of the fth particle updated in the tth generation, f = 1, 2, …, D, when t = 1, x _fd (t-1) represents the initial position of the fth particle, p _fd (t-1) represents the initial individual optimal position of the fth particle, p _gd (t-1) represents the initial global optimal position of the particle swarm, v _fd (t-1) represents the initial velocity of the fth particle, when t ≥ 2, x _fd (t-1) represents the position of the fth particle updated in the t-1th generation, p _fd (t-1) represents the individual optimal position of the fth particle after the t-1th generation update, p _gd (t-1) represents the global optimal position of the particle swarm after the t-1th generation update, v _fd (t-1) represents the velocity of the f-th particle after being updated in the t-1th generation, e represents the base of the natural logarithm, σ is the weight and σ=0.2, randn() is the standard normal distribution function, and round() represents rounding. In the above formula (5), when the calculated _xfd (t) is an integer greater than 2, let _xfd (t)=2; when the calculated _xfd (t) is an integer less than 0, let _xfd (t)=0; when the calculated _xfd (t) is an integer greater than or equal to 1 and less than or equal to 2, the value of _xfd (t) is its calculated value.

B. Map the position of each particle after the t-th generation update to polarity, calculate the fitness value of the MPRM circuit area under each polarity after the t-th generation update, and use the fitness value of the MPRM circuit area under each polarity as the fitness value of the particle corresponding to it;

C. Compare the currently calculated fitness value of each particle with the fitness value corresponding to the individual optimal position of the particle after the t-1 generation update. If the currently calculated fitness value of the particle is greater than the fitness value corresponding to the individual optimal position of the particle after the t-1 generation update, then the position of the particle after the t-1 generation update replaces the individual optimal position of the particle after the t-1 generation update as the individual optimal position of the particle after the t-1 generation update. Otherwise, the individual optimal position of the particle after the t-1 generation update is used as the individual optimal position of the particle after the t-1 generation update. When t=1, the individual optimal position of the particle after the t-1 generation update is its initial individual optimal position.

D. Compare the fitness values corresponding to the individual optimal positions of all particles after the t-th generation update, and take the individual optimal position of the particle with the largest fitness value after the t-th generation update as the global optimal position after the t-th generation update;

E. The tth generation update is completed;

(9) Determine whether the value of t is equal to T. If not, update the value of t by adding 1 to the current value of t, and then return to step (8) to perform the next generation update. If equal, the iteration is completed and step (10) is entered;

(10) The global optimal position obtained after the T-th generation update of the discrete three-valued particle swarm is completed is output as the optimal polarity, and the area of the MPRM circuit corresponding to the optimal polarity is output as the optimal area.

Compared with the prior art, the advantage of the present invention lies in that the MPRM circuit is represented by a function expression, and then the function expression of the MPRM circuit is converted into a P-polarity MPRM expression by a polarity conversion method to obtain a P-polarity MPRM expression, and then the parameters of the MPRM circuit area optimization are associated with the parameters of the discrete three-value particle swarm algorithm, and a fitness function for area optimization is constructed. Finally, based on the fitness function, the discrete three-value particle swarm algorithm is used to perform area optimization, which has high search efficiency, strong local optimization capability, and good optimization effect.

DETAILED DESCRIPTION

The present invention is further described in detail below with reference to the embodiments.

Embodiment: A method for optimizing the area of an MPRM circuit comprises the following steps:

(1) The MPRM circuit is represented by a function expression, which is expressed by formula (1):

式中

的出现形式和i_k相关，若i_k＝1，

若i_k＝0，

其中

为x_k的反变量；a_i,c为第i个最小项系数，且a_i,c∈{0，1}，若m_i在f(x_n-1,x_n-2,…,x₀)中出现，则a_i,c＝1，否则a_i,c＝0；Where n is the number of input variables of the function f( _xn-1 , _xn-2 , ..., _xk , ..., _x0 ), (xn _-1 , _xn-2 , ..., _xk , ..., x0) is the n input variables of the function f(xn _-1 , _xn-2 , ..., _xk , ..., _x0 ), _xk is the k+1th input variable, k = 0, 1, 2, ...n- ₁ , ∑ represents the OR operator, i is the ordinal number of the largest term, i is represented in binary as _{in-1 in-2} ...i _k ...i ₀ ; _mi is the i-th smallest term, and its symbolic representation is

In the formula

The appearance of is related to i _k . If i _k = 1,

If i _k = 0,

in

is the inverse variable of x _k ; a _i,c is the coefficient of the ith minimum term, and a _i,c ∈{0, 1}, if _mi appears in f(x _n-1 ,x _n-2 ,…,x ₀ ), then a _i,c ＝1, otherwise a _i,c ＝0;

(2) The function expression of the MPRM circuit is converted into the MPRM expression of P polarity by using the polarity conversion method, and the MPRM expression of P polarity is obtained. The MPRM expression of P polarity is expressed by formula (2):

为异或运算符号，π_i为第i个与项，用符号表示为

P为极性值，其三进制数的表示形式为(P_n-1P_n-2…P_k…P₀)，i_k和p_k一起决定

的形式，如果π_i在f^(P)(x_n-1,x_n-2,…,x₀)中存在，那么与项系数b_i,c＝1，否则b_i,c＝0；

与i_k和p_k的关系为：当p_k＝0，i_k＝0或1时，

以原变量x_k出现；当p_k＝1，i_k＝0或1时，

以反变量

出现；当p_k＝2，i_k＝1时，

以原变量x_k的形式出现；当p_k＝2，i_k＝0时，

以反变量

的形式出现；in,

is the XOR operator symbol, π _i is the ith AND term, and is represented by

P is the polarity value, and its ternary number representation is (Pn _{- 1Pn-2} … _Pk … _P0 ), i _k and p _k together determine

In the form of, if π _i exists in f ^(P) (x _n-1 ,x _n-2 ,…,x ₀ ), then the coefficient of the term b _i,c ＝1, otherwise b _i,c ＝0;

The relationship between i _k and p _k is: when p _k = 0, i _k = 0 or 1,

appears as the original variable x _k ; when p _k = 1, i _k = 0 or 1,

Inverse variable

appears; when p _k = 2, i _k = 1,

Appears in the form of the original variable x _k ; when p _k = 2, i _k = 0,

Inverse variable

Appear in the form of;

(3) Associate the parameters of the MPRM circuit area optimization with the parameters of the discrete ternary particle swarm algorithm: define the number of input variables n in the MPRM expression of P polarity as the search space dimension of the discrete ternary particle swarm, define the polarity in the MPRM expression of P polarity as the particle of the ternary diversity particle swarm, and define the ternary number of the polarity value P in the MPRM expression of P polarity of the MPRM circuit as the particle position;

(4) The number of particles in the discrete three-value particle swarm is set to D, where D is an integer greater than or equal to 50 and less than or equal to 100, and the maximum number of iterations is set to T, where T is an integer greater than or equal to 100 and less than or equal to 150;

(5) Set the fitness function of the MPRM circuit area, and record the fitness as fitness(area). Fitness(area) is expressed using formula (3):

fitness(area)＝1.0/(no_of_and+no_of_xor)*1000 (3)

In formula (3), * is the multiplication symbol, “/” is the division symbol, no_of_and is the number of AND terms in the MPRM expression of P polarity, and no_of_xor is the number of XOR terms in the MPRM expression of P polarity;

(6) Initializing the discrete three-valued particle swarm: randomly initializing the speed of each particle in the discrete three-valued particle swarm, the position of each particle, the current individual optimal position of each particle, the current global optimal position of the discrete three-valued particle swarm, and the fitness value of the MPRM circuit area corresponding to the MPRM expression corresponding to the polarity of each particle position;

(7) Set the number of iterations, record it as t, perform an initial transformation on t, and set t = 1;

(8) Perform the tth generation update of discrete ternary particle swarm, specifically:

A. Use the motion equation of particles in the discrete three-valued particle swarm to update the velocity and position of each particle in the ion swarm. The motion equation of particles in the discrete three-valued particle swarm is shown in equations (4), (5) and (6):

v _fd (t)＝wv _fd (t-1)+c ₁ r ₁ (p _fd (t-1)-x _fd (t-1))+c ₂ r ₂ (p _gd (t-1)-x _fd (t-1)) (4)

x _fd (t)＝round(S _fd +2×σ×randn()) (5)

式中w_start表示初始权重，w_end表示最终权重，初始惯性权重w_start＝0.9，终止惯性权重w_end＝0.4。T表示最大迭代数，v_fd(t)表示第t代更新得到的第f个粒子的速度，x_fd(t)表示第t代更新得到的第f个粒子的位置，f＝1,2,…,D，当t＝1时，x_fd(t-1)表示第f个粒子的初始位置，p_fd(t-1)表示第f个粒子初始的个体最优位置，p_gd(t-1)表示粒子群初始的全局最优位置，v_fd(t-1)表示第f个粒子的初始速度，当t≥2时，x_fd(t-1)表示第f个粒子在第t-1代更新得到的位置，p_fd(t-1)表示第f个粒子在第t-1代更新完成后的个体最优位置，p_gd(t-1)表示粒子群在第t-1代更新完成后的全局最优位置，v_fd(t-1)为表示第f个粒子在第t-1代更新后的速度，e表示自然对数的底，σ为权值且σ＝0.2，randn()为标准正态分布函数，round()表示四舍五入取整，上式(5)中，当计算得到的x_fd(t)为大于2的整数时，令x_fd(t)＝2,当计算得到的x_fd(t)为小于0的整数时，令x_fd(t)＝0，当计算得到的x_fd(t)为大于等于1且小于等于2的整数时，x_fd(t)的取值为其计算值。Where c ₁ and c ₂ are learning factors, c ₁ = c ₂ = 1.5, r ₁ and r ₂ are random numbers greater than or equal to 0 and less than or equal to 1, w is the inertia weight,

Where w _start represents the initial weight, w _end represents the final weight, the initial inertia weight w _start = 0.9, and the final inertia weight w _end = 0.4. T represents the maximum number of iterations, v _fd (t) represents the velocity of the fth particle updated in the tth generation, x _fd (t) represents the position of the fth particle updated in the tth generation, f = 1, 2, …, D, when t = 1, x _fd (t-1) represents the initial position of the fth particle, p _fd (t-1) represents the initial individual optimal position of the fth particle, p _gd (t-1) represents the initial global optimal position of the particle swarm, v _fd (t-1) represents the initial velocity of the fth particle, when t ≥ 2, x _fd (t-1) represents the position of the fth particle updated in the t-1th generation, p _fd (t-1) represents the individual optimal position of the fth particle after the t-1th generation is updated, p _gd (t-1) represents the global optimal position of the particle swarm after the t-1th generation is updated, v _fd (t-1) represents the velocity of the f-th particle after being updated in the t-1th generation, e represents the base of the natural logarithm, σ is the weight and σ=0.2, randn() is the standard normal distribution function, and round() represents rounding. In the above formula (5), when the calculated _xfd (t) is an integer greater than 2, let _xfd (t)=2; when the calculated _xfd (t) is an integer less than 0, let _xfd (t)=0; when the calculated _xfd (t) is an integer greater than or equal to 1 and less than or equal to 2, the value of _xfd (t) is its calculated value.

B. Map the position of each particle after the t-th generation update to polarity, calculate the fitness value of the MPRM circuit area under each polarity after the t-th generation update, and use the fitness value of the MPRM circuit area under each polarity as the fitness value of the particle corresponding to it;

C. Compare the currently calculated fitness value of each particle with the fitness value corresponding to the individual optimal position of the particle after the t-1 generation update. If the currently calculated fitness value of the particle is greater than the fitness value corresponding to the individual optimal position of the particle after the t-1 generation update, then the position of the particle after the t-1 generation update replaces the individual optimal position of the particle after the t-1 generation update as the individual optimal position of the particle after the t-1 generation update. Otherwise, the individual optimal position of the particle after the t-1 generation update is used as the individual optimal position of the particle after the t-1 generation update. When t=1, the individual optimal position of the particle after the t-1 generation update is its initial individual optimal position.

D. Compare the fitness values corresponding to the individual optimal positions of all particles after the t-th generation update, and take the individual optimal position of the particle with the largest fitness value after the t-th generation update as the global optimal position after the t-th generation update;

E. The tth generation update is completed;

(9) Determine whether the value of t is equal to T. If not, update the value of t by adding 1 to the current value of t, and then return to step (8) to perform the next generation update. If equal, the iteration is completed and step (10) is entered;

(10) The global optimal position obtained after the T-th generation update of the discrete three-valued particle swarm is completed is output as the optimal polarity, and the area of the MPRM circuit corresponding to the optimal polarity is output as the optimal area.

The area optimization method of the MPRM circuit of the present invention is programmed in C language, using Windows 7 operating system and compiled by Microsoft Visual C++6.0. The hardware environment of the program is Intel(R)Core(TM)i5-2415M CPU (2.30GH _Z ) 4G RAM. The area optimization method of the MPRM circuit of the present invention is tested using a PLA format test circuit.

In the experiment, the parameters are set as follows: learning factor c ₁ = c ₂ = 1.5, initial inertia weight w _start = 0.9, final inertia weight w _end = 0.4, σ = 0.2. The particle swarm size and the maximum number of iterations are input by the keyboard.

In order to determine the correctness and effectiveness of the area optimization method of the MPRM circuit of the present invention, the circuit is first verified by three different three-input variable test circuits. The three different three-input variable test circuits are: mytest1247: f(x ₂ ,x ₁ ,x ₀ )=∏(1,2,4,7), mytest3467: f(x ₂ ,x _{1 ,x 0 )=∏(3,4,6,7), mytest3567: f(x 2 ,x 1 ,x 0 ) = ∏} (3,5,6,7). First, all 27 polarities of the three test circuits are traversed according to the exhaustive idea to determine the optimal polarity of the circuit, and then the area optimization method of the MPRM circuit of the present invention is used to search for the optimal polarity of the circuit, and finally the two results are compared. Among them, the list of XOR and AND terms under all polarities of the mytest1247 circuit is shown in Table 1, the list of XOR and AND terms under all polarities of the mytest3467 circuit is shown in Table 2, and the list of XOR and AND terms under all polarities of the mytest3567 circuit is shown in Table 3.

Table 1 Number of XOR and AND terms in all polarities of mytest1247 circuit

As shown in Table 1, after traversing the 27 polarities of mytest1247, it is found that the polarity with the least sum of XOR and AND operation items is polarity 0 (4, 10, 12), and the sum of XOR and AND gates required under this polarity is only 2. The area optimization method of the MPRM circuit of the present invention is used to search the polarity of mytest1247, and the result shows that the best polarity is polarity 0, and the sum of XOR and AND gates required is 2.

Table 2 Number of XOR and AND terms in all polarities of mytest3467 circuit

polarity XOR AND polarity XOR AND polarity XOR AND 0(000) ₃ 2 2 9(100) ₃ 4 2 18(200) ₃ 3 5 1(001) ₃ 2 2 10(101) ₃ 3 2 19(201) ₃ 4 7 2(002) ₃ 1 2 11(102) ₃ 2 2 20(202) ₃ 2 5 3(010) ₃ 3 2 12(110) ₃ 3 2 21(210) ₃ 2 5 4(011) ₃ 4 2 13(111) ₃ 3 2 22(211) ₃ 6 7 5(012) ₃ 2 2 14(112) ₃ 3 2 23(212) ₃ 4 7 6(020) ₃ 4 7 15(120) ₃ 6 7 24(220) ₃ 2 5 7(021) ₃ 3 5 16(121) ₃ 3 5 25(221) ₃ 3 6 8(022) ₃ 2 5 17(122) ₃ 4 7 26(222) ₃ 3 8

From the analysis of Table 2, it can be seen that: after traversing the 27 polarities of mytest3467, the polarity with the least number of XOR and AND operation items is polarity 2, and the sum of XOR and AND gates required under this polarity is 3. The area optimization method of the MPRM circuit of the present invention is used to search the polarity of mytest3467, and the result shows that the best polarity is polarity 2, and the sum of XOR and AND gates required is 3.

Table 3 Number of XOR and AND terms in all polarities of mytest3567 circuit

polarity XOR AND polarity XOR AND polarity XOR AND 0(000) ₃ 2 3 9(100) ₃ 4 3 18(200) ₃ 3 6 1(001) ₃ 4 3 10(101) ₃ 5 3 19(201) ₃ 4 6 2(002) ₃ 3 6 11(102) ₃ 4 6 20(202) ₃ 2 5 3(010) ₃ 4 3 12(110) ₃ 5 3 21(210) ₃ 4 6 4(011) ₃ 5 3 13(111) ₃ 3 3 22(211) ₃ 5 6 5(012) ₃ 4 6 14(112) ₃ 5 6 23(212) ₃ 4 7 6(020) ₃ 3 6 15(120) ₃ 4 6 24(220) ₃ 2 5 7(021) ₃ 4 6 16(121) ₃ 5 6 25(221) ₃ 4 7 8(022) ₃ 2 5 17(122) ₃ 4 7 26(222) ₃ 3 8

From the analysis of Table 3, we can see that: after traversing the 27 polarities of mytest3567, the polarity with the least number of XOR and AND operation items is polarity 0, and the sum of XOR and AND gates required under this polarity is 5. The DTPSO algorithm is used to search the polarity of mytest3567, and the result shows that the best polarity is polarity 0, and the sum of XOR and AND gates required is 5.

From the comparison results of the above three test circuits, it can be seen that the correctness of the area optimization method of the MPRM circuit of the present invention is beyond doubt. Six PLA format test circuits are randomly selected to obtain the sum of the number of XOR and AND items under the optimal polarity of the circuit. By comparing with the experimental results of the discrete binary particle swarm optimization algorithm (BPSO), the effect of the area optimization method of the MPRM circuit of the present invention is determined. In order to eliminate the interference of random factors on the experimental results, the selected circuit is randomly tested 5 times, and the results are averaged for 5 times. The experimental results are shown in Table 4.

Table 4.4 Comparison of experimental data between the method of the present invention and the BPSO algorithm

From the comparison with the BPSO operation results, it can be seen that the sum of the number of XOR and AND terms under the optimal polarity searched by the area optimization method of the MPRM circuit of the present invention is generally less than the number of terms searched by BPSO, and the average area saving percentage is 29.56%. The area optimization method of the MPRM circuit of the present invention has better optimization ability and good area optimization effect.

Claims (1)

1. A method for optimizing the area of an MPRM circuit, comprising the following steps: (1) The MPRM circuit is represented by a function expression, which is expressed by formula (1):

Where n is the number of input variables of the function f( _xn-1 , _xn-2 , ..., _xk , ..., _x0 ), (xn _-1 , _xn-2 , ..., _xk , ..., x0) is the n input variables of the function f(xn _-1 , _xn-2 , ..., _xk , ..., _x0 ), _xk is the k+1th input variable, k = 0, 1, 2, ...n- ₁ , ∑ represents the OR operator, i is the ordinal number of the largest term, i is represented in binary as _{in-1 in-2} ...i _k ...i ₀ ; _mi is the i-th smallest term, and its symbolic representation is

In the formula

The appearance of is related to i _k . If i _k = 1,

If i _k = 0,

in

is the inverse variable of x _k ; a _i,c is the coefficient of the ith minimum term, and a _i,c ∈{0, 1}, if _mi appears in f(x _n-1 ,x _n-2 ,…,x ₀ ), then a _i,c ＝1, otherwise a _i,c ＝0; (2) The function expression of the MPRM circuit is converted into the MPRM expression of P polarity by using the polarity conversion method, and the MPRM expression of P polarity is obtained. The MPRM expression of P polarity is expressed by formula (2):

in,

is the XOR operator symbol, π _i is the ith AND term, and is represented by

P is the polarity value, and its ternary number representation is (Pn _{- 1Pn-2} … _Pk … _P0 ), i _k and p _k together determine

In the form of, if π _i exists in f ^(P) (x _n-1 ,x _n-2 ,…,x ₀ ), then the coefficient of the term b _i,c ＝1, otherwise b _i,c ＝0;

The relationship between i _k and p _k is: when p _k = 0, i _k = 0 or 1,

appears as the original variable x _k ; when p _k = 1, i _k = 0 or 1,

Inverse variable

appears; when p _k = 2, i _k = 1,

Appears in the form of the original variable x _k ; when p _k = 2, i _k = 0,

Inverse variable

Appear in the form of; (3) Associate the parameters of the MPRM circuit area optimization with the parameters of the discrete ternary particle swarm algorithm: define the number of input variables n in the MPRM expression of P polarity as the search space dimension of the discrete ternary particle swarm, define the polarity in the MPRM expression of P polarity as the particle of the ternary diversity particle swarm, and define the ternary number of the polarity value P in the MPRM expression of P polarity of the MPRM circuit as the particle position; (4) The number of particles in the discrete three-value particle swarm is set to D, where D is an integer greater than or equal to 50 and less than or equal to 100, and the maximum number of iterations is set to T, where T is an integer greater than or equal to 100 and less than or equal to 150; (5) Set the fitness function of the MPRM circuit area, and record the fitness as fitness(area). Fitness(area) is expressed using formula (3): fitness(area)＝1.0/(no_of_and+no_of_xor)*1000 (3) In formula (3), * is the multiplication symbol, “/” is the division symbol, no_of_and is the number of AND terms in the MPRM expression of P polarity, and no_of_xor is the number of XOR terms in the MPRM expression of P polarity; (6) Initializing the discrete three-valued particle swarm: randomly initializing the speed of each particle in the discrete three-valued particle swarm, the position of each particle, the current individual optimal position of each particle, the current global optimal position of the discrete three-valued particle swarm, and the fitness value of the MPRM circuit area corresponding to the MPRM expression corresponding to the polarity of each particle position; (7) Set the number of iterations, record it as t, perform an initial transformation on t, and set t = 1; (8) Perform the tth generation update of discrete ternary particle swarm, specifically: A. Use the motion equation of particles in the discrete three-valued particle swarm to update the velocity and position of each particle in the ion swarm. The motion equation of particles in the discrete three-valued particle swarm is shown in equations (4), (5) and (6): v _fd (t)＝wv _fd (t-1)+c ₁ r ₁ (p _fd (t-1)-x _fd (t-1))+c ₂ r ₂ (p _gd (t-1)-x _fd (t-1)) (4) x _fd (t)＝round(S _fd +2×σ×randn()) (5)

Where c ₁ and c ₂ are learning factors, c ₁ = c ₂ = 1.5, r ₁ and r ₂ are random numbers greater than or equal to 0 and less than or equal to 1, w is the inertia weight,

Wherein w _start represents the initial weight, w _end represents the final weight, the initial inertia weight w _start = 0.9, and the final inertia weight w _end = 0.4; T represents the maximum number of iterations, v _fd (t) represents the velocity of the f-th particle updated in the t-th generation, x _fd (t) represents the position of the f-th particle updated in the t-th generation, f = 1, 2, …, D, when t = 1, x _fd (t-1) represents the initial position of the f-th particle, p _fd (t-1) represents the initial individual optimal position of the f-th particle, p _gd (t-1) represents the initial global optimal position of the particle swarm, v _fd (t-1) represents the initial velocity of the f-th particle, when t ≥ 2, x _fd (t-1) represents the position of the f-th particle updated in the t-1th generation, p _fd (t-1) represents the individual optimal position of the f-th particle after the t-1th generation update is completed, p _gd (t-1) represents the global optimal position of the particle swarm after the t-1th generation update is completed, v _fd (t-1) represents the velocity of the f-th particle after being updated in the t-1th generation, e represents the base of the natural logarithm, σ represents the weight and σ=0.2, randn() represents the standard normal distribution function, and round() represents rounding. In the above formula (5), when the calculated x _fd (t) is an integer greater than 2, let x _fd (t)=2; when the calculated x _fd (t) is an integer less than 0, let x _fd (t)=0; when the calculated x _fd (t) is an integer greater than or equal to 1 and less than or equal to 2, the value of x _fd (t) is its calculated value; B. Map the position of each particle after the t-th generation update to polarity, calculate the fitness value of the MPRM circuit area under each polarity after the t-th generation update, and use the fitness value of the MPRM circuit area under each polarity as the fitness value of the particle corresponding to it; C. Compare the currently calculated fitness value of each particle with the fitness value corresponding to the individual optimal position of the particle after the t-1 generation update. If the currently calculated fitness value of the particle is greater than the fitness value corresponding to the individual optimal position of the particle after the t-1 generation update, then the position of the particle after the t-1 generation update replaces the individual optimal position of the particle after the t-1 generation update as the individual optimal position of the particle after the t-1 generation update. Otherwise, the individual optimal position of the particle after the t-1 generation update is used as the individual optimal position of the particle after the t-1 generation update. When t=1, the individual optimal position of the particle after the t-1 generation update is its initial individual optimal position. D. Compare the fitness values corresponding to the individual optimal positions of all particles after the t-th generation update, and take the individual optimal position of the particle with the largest fitness value after the t-th generation update as the global optimal position after the t-th generation update; E. The tth generation update is completed; (9) Determine whether the value of t is equal to T. If not, update the value of t by adding 1 to the current value of t, and then return to step (8) to perform the next generation update. If equal, the iteration is completed and step (10) is entered; (10) The global optimal position obtained after the T-th generation update of the discrete three-valued particle swarm is completed is output as the optimal polarity, and the area of the MPRM circuit corresponding to the optimal polarity is output as the optimal area.