METHOD FOR OPTIMIZING AREA OF TERNARY FPRM CIRCUIT USING POPULATION MIGRATION ALGORITHM

Abstract

A method for optimizing an area of a ternary FPRM circuit using population migration algorithm, the method including: 1) establishing an area estimation model of the ternary FPRM circuit; 2) establishing a corresponding relationship between the ternary FPRM circuit and population migration algorithm; 3) setting an attraction function for calculating the attraction of the population location in population migration algorithm; 4) setting relevant parameters of population migration algorithm; and 5) employing population migration algorithm to calculate and obtain the greatest attractive site and the greatest attraction.

Claims

1. A method for optimizing an area of a ternary FPRM circuit using population migration algorithm, the method comprising: 1) establishing an area estimation model of the ternary FPRM circuit, wherein 1.1) the ternary FPRM circuit is expressed by a ternary FPRM logic function expression as follows: $\begin{array}{cc}{f}^p\left(x_{n-1},x_{n-2},\mathrm{.Math.}.Math.,x_0\right)=\underset{i=0}{\overset{3^n-1}{.Math.}}.Math.a_i*\underset{j=0}{\overset{n-1}{.Math.}}.Math.{\stackrel{.}{x}}_j^{i_j}& \left(1\right)\end{array}$ where n is the number of variables of the function .sup.p(x.sub.n-1, x.sub.n-2, . . . , x.sub.0), x.sub.n-1, x.sub.n-2, . . . , x.sub.0 denotes the n input variables of the function .sup.p(x.sub.n-1, x.sub.n-2, . . . , x.sub.0), p denotes a polarity of the function .sup.p(x.sub.n-1, x.sub.n-2, . . . , x.sub.0), the polarity p is expressed in ternary form as p.sub.n-1 p.sub.n-2 . . . p.sub.0, p.sub.j{0, 1, 2}, j=0, 1, 2, . . . , n1, represents a modulo-3 addition operation, is a summation sign, the symbol * represents multiplication, subscript i=0, 1, 2, . . . , 3.sup.n1, i is expressed in ternary form as i.sub.n-1 i.sub.n-2 . . . i.sub.0, a.sub.i is a coefficient of FPRM expansion, a.sub.i{0, 1, 2}; represents a modulo-3 multiplication operation, $\underset{j=0}{\overset{n-1}{.Math.}}.Math.{\stackrel{.}{x}}_j^{i_j}$ has its expansion as follow: $\underset{j=0}{\overset{n-1}{.Math.}}.Math.{\stackrel{.}{x}}_j^{i_j}={\stackrel{.}{x}}_{n-1}^{i_{n-1}}.Math.{\stackrel{.}{x}}_{n-2}^{i_{n-2}}.Math..Math.\mathrm{.Math.}.Math..Math.{\stackrel{.}{x}}_0^{i_0},$ where i.sub.j{0, 1, 2}, {dot over (x)}.sub.j=(x.sub.jp.sub.j), {dot over (x)}.sub.j.sup.0=1={dot over (x)}.sub.j.sup.1={dot over (x)}.sub.j, {dot over (x)}.sub.j.sup.2*{dot over (x)}.sub.j, polarity p and subscript i determine the representation of the variable {dot over (x)}.sub.j; 1.2) the ternary FPRM logic function under polarity p is composed of two types of multi-input operations which are a multi-input modulo-3 addition operation and a multi-input modulo-3 multiplication operation respectively; based on expansion of a ternary FPRM logic function, the ternary FPRM logic function is decomposed into several multi-input modulo-3 addition operations and several multi-input modulo-3 multiplication operations, then each multi-input operation is individually decomposed into 2-input operations, to obtain 2-input modulo-3 addition operations and 2-input modulo-3 multiplication operations; wherein, the decomposition process is as follows: a 1st and a 2nd input variables of a multi-input operation are taken as two input variables of a first 2-input operation, to obtain an output variable of the first 2-input operation; the output variable of the first 2-input operation and the 3rd input variable of the multi-input operation are taken as two input variables of a second 2-input operation, to obtain an output variable of the second 2-input operation; the output variable of the second 2-input operation and the 4th input variable of the multi-input operation are taken as two input variables of a third 2-input operation, to obtain an output variable of the third 2-input operation; and so forth, till all the input variables of the multi-input operation have been taken as an input variable of a 2-input operation, thereby accomplishing the decomposition of the multi-input operation; the ternary FPRM logic function under polarity p is decomposed into several multi-input modulo-3 addition operations (also referred to as multi-input modulo-3 addition gates) and several multi-input modulo-3 multiplication operations (also referred to as multi-input modulo-3 multiplication gates), then represent N to denote the number of the multi-input modulo-3 addition gates resulted from the decomposition of the ternary FPRM logic function under polarity p, and represent W to denote the number of the multi-input modulo-3 multiplication gates resulted from the decomposition of the ternary FPRM logic function under polarity p; each multi-input modulo-3 addition operation is decomposed into several 2-input modulo-3 addition operations (also referred to as 2-input modulo-3 addition gates), and each multi-input modulo-3 multiplication operation is decomposed into several 2-input modulo-3 multiplication operations (also referred to as 2-input modulo-3 multiplication gates); the number of the 2-input modulo-3 addition gates resulted from the decomposition of the hth multi-input modulo-3 addition gate is denoted as No.sub.h._of_Mod 3A.sub.P, h=1, 2, . . . , N; the number of the 2-input modulo-3 multiplication gates resulted from the decomposition of the wth multi-input modulo-3 multiplication gate is denoted as No.sub.w._of_Mod 3M.sub.p, w=1, 2, . . . , W; represent $S=\underset{h=1}{\overset{N}{.Math.}}.Math.{\mathrm{No}}_h.\mathrm{\_of}.Math.\mathrm{\_Mod3}-A_p+\underset{w=1}{\overset{W}{.Math.}}.Math.{\mathrm{No}}_w.\mathrm{\_of}.Math.\mathrm{\_Mod3}-M_p$ be an area estimation model of the ternary FPRM circuit, where S represents the area; $\underset{h=1}{\overset{N}{.Math.}}.Math.{\mathrm{No}}_h.\mathrm{\_of}.Math.\mathrm{\_Mod3}-A_p$ represents the total number of 2-input modulo-3 addition gates resulted from the decomposition of the ternary FPRM logic function under polarity p; $\underset{w=1}{\overset{W}{.Math.}}.Math.{\mathrm{No}}_w.\mathrm{\_of}.Math.\mathrm{\_Mod3}-M_p$ represents the total number of 2-input modulo-3 multiplication gates resulted from the decomposition of the ternary FPRM logic function under polarity p; 2) establishing a corresponding relationship between the ternary FPRM circuit and population migration algorithm: population migration algorithm includes the following key factors: population location, attraction of population location, the greatest attractive site, the greatest attraction, ground space of population mobility, concession region, population mobility, population migration and population disperse; the area optimization of the ternary FPRM circuit includes the following key factors: polarity, area size corresponding to polarity, optimal polarity, minimum area, optional polarity space, the zone where the optimal polarity exists, polarity jump to the zone where the optimal polarity exists and jump out of the local optimal polarity; the population location is mapped to area optimization of the ternary FPRM circuit, and represented as polarity; the attraction of the population location is mapped to area optimization of the ternary FPRM circuit, and represented as the area size corresponding to the polarity; the greatest attractive site is mapped to area optimization of the ternary FPRM circuit, and represented as the optimal polarity; the greatest attraction is mapped to area optimization of the ternary FPRM circuit, and represented as the minimum area; the ground space of population mobility is mapped to area optimization of the ternary FPRM circuit, and represented as an optional polarity space; the concession region is mapped to area optimization of the ternary FPRM circuit, and represented as the zone where the optimal polarity exists; the population mobility is mapped to area optimization of the ternary FPRM circuit, and represented as polarity transition; the population migration is mapped to area optimization of the ternary FPRM circuit, and represented as polarity jump to the zone where the optimal polarity exists; the population disperse is mapped to area optimization of the ternary FPRM circuit, and represented as polarity jump out of the local optimal polarity; 3) setting an attraction function for calculating the attraction of the population location in population migration algorithm: according to the area estimation model, an attraction function for calculating the attraction of the population location in population migration algorithm is set as follows: in population migration algorithm, greater attraction indicates higher economic level of the population location, whereas the area-optimal polarity requires the area to be as small as possible, and therefore, in order to combine both conditions, the reciprocal of the area is employed to represent the attraction, and the attraction function is obtained as follows: $\begin{array}{cc}\mathrm{attraction}=\left(1/S\right)*=\left(1/\left(\underset{h=1}{\overset{N}{.Math.}}.Math.{\mathrm{No}}_h.\mathrm{\_of}.Math.\mathrm{\_Mod3}-A_p+\underset{w=1}{\overset{W}{.Math.}}.Math.{\mathrm{No}}_w.\mathrm{\_of}.Math.\mathrm{\_Mod3}-M_p\right)\right)*& \left(2\right)\end{array}$ where the symbol / denotes a division operation, and attraction represents attraction value, greater attraction value indicates better area optimization effect of the circuit; is a magnification coefficient, its value is equal to a natural number greater than 1000; 4) setting relevant parameters of population migration algorithm, wherein population migration algorithm has five parameters to be set: population scale s, the number of population mobility times 1, population pressure parameter q, shrinkage factor c, and the number of population disperse times z; represent the population scale s be equal to the number of input variables of the ternary FPRM logic function, i.e., s=n; the number of population mobility times 1 is the radius of the region where the population exists, and the radius where the population exists is denoted as t, l=t, t=3.sup.s/s.sup.2; the population pressure parameter q is t/10; the shrinkage factor c=0.3; when the ternary FPRM circuit is a small-scale circuit, the number of population disperse times z=15, and when the ternary FPRM circuit is a large-scale circuit, the number of population disperse times z=2; and 5) employing population migration algorithm to calculate and obtain the greatest attractive site and the greatest attraction, wherein the greatest attractive site is the optimal polarity of the ternary FPRM circuit, and the greatest attraction is the minimum area of the ternary FPRM circuit.

2. The method of claim 1, wherein in the step 5), the calculation process of population migration algorithm is as follows: 5.1) in the ground space of population mobility, a random function rand( ) is employed to generate population locations in number S, and the population locations in number S are denoted as P1, P2, . . . , Ps, then the P1, P2, . . . , Ps are taken as center points respectively, so that the regions in number S where the population exists are determined, according to the radiuses of the regions where the population exists; 5.2) the attraction function is used to calculate the attraction of the population location Pv, v=1, 2, 3, . . . , s, to obtain the attraction of the population locations P1, P2, . . . , Ps; 5.3) by comparing the attraction of the population locations P1, P2, . . . , Ps, the population location with the greatest attraction is selected as the greatest attractive site, then the greatest attractive site and the greatest attraction are recorded; 5.4) population mobility is performed: in the population region corresponding to the population location Pv, a random function is employed to randomly generate a population location Pv, to obtain P1, P2, . . . , Ps then P1, P2, . . . , Ps is used to update the population locations P1, P2, . . . , Ps, namely P1=P1, P2=P2, . . . , Ps=Ps, where Pv=2*t*rand ( )+(Pvt), the symbol * denotes multiplication operation, t denotes the radius of the population region; rand( ) is the random function; 5.5) the updated population locations P1, P2, . . . , Ps in the step 5)-4 are processed by following the steps 5.2) 5.3), to obtain the updated greatest attractive site and the updated greatest attraction; 5.6) population migration is performed: the updated greatest attractive site in step 5.5) is taken as the center point, so that the concession region is determined according to the radius t of the population region, then a random function rand( ) employed to generate population locations in number S in the concession region, so that the obtained population locations in number S are used to again update the population locations P1, P2, . . . , Ps; 5.7) the updated population locations P1, P2, . . . , Ps in the step 5.6) are processed by following the steps 5.2) 5.3), to obtain the again updated greatest attractive site and the again updated greatest attraction; 5.8) shrinkage of the concession region is performed: Represent t=(1c)*t and employ t to update t, the steps 5.6) 5.7) are repeated until t<q; 5.9) after the concession region is shrunk to a certain extent that t<q, population disperse is performed: the steps 5.1) 5.8) are repeated, until the number of population disperse times z is met, and so the algorithm ends, to obtain the last updated greatest attractive site and the last updated greatest attraction; 5.10) the last updated greatest attractive site and the last updated greatest attraction are output, wherein the greatest attractive site is the optimal polarity of the ternary FPRM circuit, and the greatest attraction is the minimum area of the ternary FPRM circuit.

3. The method of claim 1, wherein in the step 1), a ternary-FPRM-polarity transform technology is employed to obtain the ternary FPRM logic function, and the specific process is as follows: A) the required polarity of the ternary FPRM circuit is denoted as p, and p is expressed in ternary form as p=p.sub.n-1 p.sub.n-2 . . . p.sub.0, where n represents the number of the input variables; B) for p.sub.j, its corresponding fixed-polarity GF transformation matrix G.sub.3.sup.<p.sup.j.sup.> is generated; where, $p_j\left\{p_{n-1},p_{n-2},\mathrm{.Math.}.Math.,p_0\right\},j\left\{n-1,n-2,\mathrm{.Math.}.Math.,0\right\};\mathrm{when}.Math..Math.p_j=0,G_3^{<p_j>}=G_3;\mathrm{when}.Math..Math.p_j=1,G_3^{<p_j>}=G_3^{<1>};\mathrm{when}.Math..Math.p_j=2,G_3^{<p_j>}=G_3^{<2>};G_3=\left[\begin{array}{ccc}1& 0& 0\\ 0& 2& 1\\ 2& 2& 2\end{array}\right],G_3^{<1>}=\left[\begin{array}{ccc}0& 0& 1\\ 2& 1& 0\\ 2& 2& 2\end{array}\right],G_3^{<2>}=\left[\begin{array}{ccc}0& 1& 0\\ 1& 0& 2\\ 2& 2& 2\end{array}\right];$ C) the minterm M is expressed in ternary form as a sequence M=M.sub.n-1 M.sub.n-2 . . . M.sub.0, M.sub.j{0, 1, 2}, and its corresponding function value is denoted as (M); D) according to the formula (3), for each minterm, a new term .sub.j is generated, .sub.j{0, 1, 2}; according to the formula (4), the contribution of the new item to the FPRM coefficients is calculated, and the contribution value is denoted as v();
.sub.j={t|G.sub.3.sup.<p.sup.j.sup.>[t,M.sub.j]0},t{0,1,2}(3)
v()=(v.sub.n-1.Math.v.sub.n-2 . . . v.sub.0).Math.(M)(4) where =.sub.n-1 .sub.n-2 . . . .sub.0, v.sub.j=G.sub.3.sup.<p.sup.j.sup.>[.sub.j,M.sub.j]; E) an index table is employed to record the generated new term and the contribution value of each new tem, if the generated new term already exists, then the contribution values of the identical new items are superimposed and presented as the contribution value of that new item; F) the steps 3)-4) are repeated for all the minterms, and the contribution values corresponding to respective new terms are the FPRM expansion coefficients; and G) according to the FPRM expansion coefficients, the ternary FPRM logic function expression under polarity p is obtained.

Description

DETAILED DESCRIPTION OF THE EMBODIMENTS

[0050] For further illustrating the invention, experiments detailing a method for optimizing an area of a ternary FPRM circuit using population migration algorithm are described below. It should be noted that the following examples are intended to describe and not to limit the invention.

Example 1

[0051] A method for optimizing an area of a ternary FPRM circuit using population migration algorithm, comprises the following steps:

[0052] 1) Establishing an area estimation model of the ternary FPRM circuit:

[0053] 11) The ternary FPRM circuit is expressed by a ternary FPRM logic function expression as follows:

[00009]$\begin{array}{cc}{f}^p\left(x_{n-1},x_{n-2},\mathrm{.Math.}.Math.,x_0\right)=\underset{i=0}{\overset{3^n-1}{.Math.}}.Math.a_i*\underset{j=0}{\overset{n-1}{.Math.}}.Math..Math.{\stackrel{.}{x}}_j^{i_j}& \left(1\right)\end{array}$

[0054] where n is the number of variables of the function .sup.p(x.sub.n-1, x.sub.n-2, . . . , x.sub.0), x.sub.n-1, x.sub.n-2, . . . , x.sub.0 denotes the n input variables of the function .sup.p(x.sub.n-1, x.sub.n-2, . . . , x.sub.0), p denotes a polarity of the function .sup.p(x.sub.n-1, x.sub.n-2, . . . , x.sub.0), the polarity p is expressed in ternary form as p.sub.n-1 p.sub.n-2 . . . p.sub.0, p.sub.j{0, 1, 2}, j=0, 1, 2, . . . , n1, represents a modulo-3 addition operation, is a summation sign, the symbol * represents multiplication, subscript i=0, 1, 2, . . . , 3.sup.n1, i is expressed in ternary form as i.sub.n-1 i.sub.n-2 . . . i.sub.0, a.sub.i is a coefficient of FPRM expansion, a.sub.i{0, 1, 2}; represents a modulo-3 multiplication operation,

[00010]$\underset{j=0}{\overset{n-1}{.Math.}}.Math..Math.{\stackrel{.}{x}}_j^{i_j}$

has its expansion as follow:

[00011]$\underset{j=0}{\overset{n-1}{.Math.}}.Math..Math.{\stackrel{.}{x}}_j^{i_j}={\stackrel{.}{x}}_{n-1}^{i_{n-1}}.Math.{\stackrel{.}{x}}_{n-2}^{i_{n-2}}.Math.\mathrm{.Math.}.Math..Math.{\stackrel{.}{x}}_0^{i_0},$

where i.sub.j{0, 1, 2}, {dot over (x)}.sub.j=(x.sub.jp.sub.j), {dot over (x)}.sub.j.sup.0=1, {dot over (x)}.sub.j.sup.1={dot over (x)}.sub.j, {dot over (x)}.sub.j.sup.2={dot over (x)}.sub.j*{dot over (x)}.sub.j, polarity p and subscript i determine the representation of the variable {dot over (x)}.sub.j;

[0055] 12) The ternary FPRM logic function under polarity p is composed of two types of multi-input operations which are a multi-input modulo-3 addition operation and a multi-input modulo-3 multiplication operation respectively; based on expansion of a ternary FPRM logic function, the ternary FPRM logic function is decomposed into several multi-input modulo-3 addition operations and several multi-input modulo-3 multiplication operations, then each multi-input operation is individually decomposed into 2-input operations, to obtain 2-input modulo-3 addition operations and 2-input modulo-3 multiplication operations; specifically, the decomposition process is as follows:

[0056] The 1.sup.st and the 2.sup.nd input variables of a multi-input operation are taken as two input variables of a first 2-input operation, to obtain an output variable of the first 2-input operation; the output variable of the first 2-input operation and the 3.sup.rd input variable of the multi-input operation are taken as two input variables of a second 2-input operation, to obtain an output variable of the second 2-input operation; the output variable of the second 2-input operation and the 4.sup.th input variable of the multi-input operation are taken as two input variables of a third 2-input operation, to obtain an output variable of the third 2-input operation; and so forth, till all the input variables of the multi-input operation have been taken as an input variable of a 2-input operation, thereby accomplishing the decomposition of the multi-input operation;

[0057] The ternary FPRM logic function under polarity p is decomposed into several multi-input modulo-3 addition operations (also referred to as multi-input modulo-3 addition gates) and several multi-input modulo-3 multiplication operations (also referred to as multi-input modulo-3 multiplication gates), then represent N to denote the number of the multi-input modulo-3 addition gates resulted from the decomposition of the ternary FPRM logic function under polarity p, and represent W to denote the number of the multi-input modulo-3 multiplication gates resulted from the decomposition of the ternary FPRM logic function under polarity p; each multi-input modulo-3 addition operation is decomposed into several 2-input modulo-3 addition operations (also referred to as 2-input modulo-3 addition gates), and each multi-input modulo-3 multiplication operation is decomposed into several 2-input modulo-3 multiplication operations (also referred to as 2-input modulo-3 multiplication gates); the number of the 2-input modulo-3 addition gates resulted from the decomposition of the h.sup.th multi-input modulo-3 addition gate is denoted as No.sub.h._of_Mod 3A.sub.p, h=1, 2, . . . , N; the number of the 2-input modulo-3 multiplication gates resulted from the decomposition of the w.sup.th multi-input modulo-3 multiplication gate is denoted as No.sub.w._of_Mod 3M.sub.p, w=1, 2, . . . , W;

[0058] Represent

[00012]$S=\underset{h=1}{\overset{N}{.Math.}}.Math.{\mathrm{No}}_{h^{*}}.Math.\mathrm{\_of}.Math.\mathrm{\_Mod}.Math..Math.3-A_p+\underset{w=1}{\overset{W}{.Math.}}.Math.{\mathrm{No}}_{w^{*}}.Math.\mathrm{\_of}.Math.\mathrm{\_Mod}.Math..Math.3-M_p$

be an area estimation model of the ternary FPRM circuit, where S represents the area;

[00013]$\underset{h=1}{\overset{N}{.Math.}}.Math.{\mathrm{No}}_{h^{*}}.Math.\mathrm{\_of}.Math.\mathrm{\_Mod}.Math..Math.3-A_p$

represents the total number of 2-input modulo-3 addition gates resulted from the decomposition of the ternary FPRM logic function under polarity p;

[00014]$\underset{w=1}{\overset{W}{.Math.}}.Math.{\mathrm{No}}_{w^{*}}.Math.\mathrm{\_of}.Math.\mathrm{\_Mod}.Math..Math.3-M_p$

represents the total number of 2-input modulo-3 multiplication gates resulted from the decomposition of the ternary FPRM logic function under polarity p;

[0059] 2) Establishing a corresponding relationship between the ternary FPRM circuit and population migration algorithm:

[0060] Population migration algorithm includes the following key factors: population location, attraction of population location, the greatest attractive site, the greatest attraction, ground space of population mobility, concession region, population mobility, population migration and population disperse; the area optimization of the ternary FPRM circuit includes the following key factors: polarity, area size corresponding to polarity, optimal polarity, minimum area, optional polarity space, the zone where the optimal polarity exists, polarity jump to the zone where the optimal polarity exists and jump out of the local optimal polarity;

[0061] The population location is mapped to area optimization of the ternary FPRM circuit, and represented as polarity; the attraction of the population location is mapped to area optimization of the ternary FPRM circuit, and represented as the area size corresponding to the polarity; the greatest attractive site is mapped to area optimization of the ternary FPRM circuit, and represented as the optimal polarity; the greatest attraction is mapped to area optimization of the ternary FPRM circuit, and represented as the minimum area; the ground space of population mobility is mapped to area optimization of the ternary FPRM circuit, and represented as an optional polarity space; the concession region is mapped to area optimization of the ternary FPRM circuit, and represented as the zone where the optimal polarity exists; the population mobility is mapped to area optimization of the ternary FPRM circuit, and represented as polarity transition; the population migration is mapped to area optimization of the ternary FPRM circuit, and represented as polarity jump to the zone where the optimal polarity exists; the population disperse is mapped to area optimization of the ternary FPRM circuit, and represented as polarity jump out of the local optimal polarity;

[0062] 3) Setting an attraction function for calculating the attraction of the population location in population migration algorithm:

[0063] According to the area estimation model, an attraction function for calculating the attraction of the population location in population migration algorithm is set as follows: in population migration algorithm, greater attraction indicates higher economic level of the population location, whereas the area-optimal polarity requires the area to be as small as possible, and therefore, in order to combine both conditions, the reciprocal of the area is employed to represent the attraction, and the attraction function is obtained as follows:

[00015]$\begin{array}{cc}\mathrm{attraction}=\left(1.Math.\text{/}.Math.S\right)*=\left(1.Math.\text{/}.Math.\left(\underset{h=1}{\overset{N}{.Math.}}.Math.{\mathrm{No}}_{h^{*}}.Math.\mathrm{\_of}.Math.\mathrm{\_Mod}.Math..Math.3-A_p+\underset{w=1}{\overset{W}{.Math.}}.Math.{\mathrm{No}}_{w^{*}}.Math.\mathrm{\_of}.Math.\mathrm{\_Mod}.Math..Math.3-M_p\right)\right)*& \left(2\right)\end{array}$

[0064] where the symbol / denotes a division operation, and attraction represents attraction value, greater attraction value indicates better area optimization effect of the circuit; is a magnification coefficient, its value is equal to a natural number greater than 1000;

[0065] 4) Setting relevant parameters of population migration algorithm:

[0066] Population migration algorithm has five parameters to be set: population scale s, the number of population mobility times l, population pressure parameter q, shrinkage factor c, and the number of population disperse times z;

[0067] Represent the population scale s be equal to the number of input variables of the ternary FPRM logic function, i.e., s=n; the number of population mobility times l is the radius of the region where the population exists, and the radius where the population exists is denoted as t, l=t, t=3.sup.s/s.sup.2; the population pressure parameter q is t/10; the shrinkage factor c=0.3; when the ternary FPRM circuit is a small-scale circuit, the number of population disperse times z=15, and when the ternary FPRM circuit is a large-scale circuit, the number of population disperse times z=2; a large-scale circuit usually refers to a circuit having 4 or more input variables, and a small-scale circuit usually refers to a circuit having 4 or less input variables;

[0068] 5) Employing population migration algorithm to calculate and obtain the greatest attractive site and the greatest attraction, wherein the greatest attractive site is the optimal polarity of the ternary FPRM circuit, and the greatest attraction is the minimum area of the ternary FPRM circuit.

[0069] In this embodiment, an existing mature ternary-FPRM-polarity transform technology is employed to obtain expansion of the ternary FPRM logic function, and population migration algorithm also utilizes an existing mature technology.

Example 2

[0070] A method for optimizing an area of a ternary FPRM circuit using population migration algorithm, comprises the following steps:

[0071] 1) Establishing an area estimation model of the ternary FPRM circuit:

[0072] 11) The ternary FPRM circuit is expressed by a ternary FPRM logic function expression as follows:

[00016]$\begin{array}{cc}{f}^p\left(x_{n-1},x_{n-2},\mathrm{.Math.}.Math.,x_0\right)=\underset{i=0}{\overset{3^n-1}{.Math.}}.Math.a_i*\underset{j=0}{\overset{n-1}{.Math.}}.Math..Math.{\stackrel{.}{x}}_j^{i_j}& \left(1\right)\end{array}$

[0073] where n is the number of variables of the function .sup.p(x.sub.n-1, x.sub.n-2, . . . , x.sub.0), x.sub.n-1, x.sub.n-2, . . . , x.sub.0 denotes the n input variables of the function .sup.p(x.sub.n-1, x.sub.n-2, . . . , x.sub.0), p denotes a polarity of the function .sup.p(x.sub.n-1, x.sub.n-2, . . . , x.sub.0), the polarity p is expressed in ternary form as p.sub.n-1 p.sub.n-2 . . . p.sub.0, p.sub.j{0, 1, 2}, j=0, 1, 2, . . . , n1, represents a modulo-3 addition operation, is a summation sign, the symbol * represents multiplication, subscript i=0, 1, 2, . . . , 3.sup.n1, i is expressed in ternary form as i.sub.n-1 i.sub.n-2 . . . i.sub.0, a.sub.i is a coefficient of FPRM expansion, a.sub.i{0, 1, 2}; represents a modulo-3 multiplication operation,

[00017]$\underset{j=0}{\overset{n-1}{.Math.}}.Math..Math.{\stackrel{.}{x}}_j^{i_j}$

has its expansion as follow:

[00018]$\underset{j=0}{\overset{n-1}{.Math.}}.Math.{\stackrel{.}{x}}_j^{i_j}={\stackrel{.}{x}}_{n-1}^{i_{n-1}}.Math.{\stackrel{.}{x}}_{n-2}^{i_{n-2}}.Math..Math.\mathrm{.Math.}.Math..Math.{\stackrel{.}{x}}_0^{i_0},$

where i.sub.j{0, 1, 2}, {dot over (x)}.sub.j=(x.sub.jp.sub.j), {dot over (x)}.sub.j.sup.0=1, {dot over (x)}.sub.j.sup.1={dot over (x)}.sub.j, {dot over (x)}.sub.j.sup.2={dot over (x)}.sub.j*{dot over (x)}.sub.j, polarity p and subscript i determine the representation of the variable {dot over (x)}.sub.j;

[0074] 12) The ternary FPRM logic function under polarity p is composed of two types of multi-input operations which are a multi-input modulo-3 addition operation and a multi-input modulo-3 multiplication operation respectively; based on expansion of a ternary FPRM logic function, the ternary FPRM logic function is decomposed into several multi-input modulo-3 addition operations and several multi-input modulo-3 multiplication operations, then each multi-input operation is individually decomposed into 2-input operations, to obtain 2-input modulo-3 addition operations and 2-input modulo-3 multiplication operations; specifically, the decomposition process is as follows:

[0075] The 1.sup.st and the 2.sup.nd input variables of a multi-input operation are taken as two input variables of a first 2-input operation, to obtain an output variable of the first 2-input operation; the output variable of the first 2-input operation and the 3.sup.rd input variable of the multi-input operation are taken as two input variables of a second 2-input operation, to obtain an output variable of the second 2-input operation; the output variable of the second 2-input operation and the 4.sup.th input variable of the multi-input operation are taken as two input variables of a third 2-input operation, to obtain an output variable of the third 2-input operation; and so forth, till all the input variables of the multi-input operation have been taken as an input variable of a 2-input operation, thereby accomplishing the decomposition of the multi-input operation;

[0076] The ternary FPRM logic function under polarity p is decomposed into several multi-input modulo-3 addition operations (also referred to as multi-input modulo-3 addition gates) and several multi-input modulo-3 multiplication operations (also referred to as multi-input modulo-3 multiplication gates), then represent N to denote the number of the multi-input modulo-3 addition gates resulted from the decomposition of the ternary FPRM logic function under polarity p, and represent W to denote the number of the multi-input modulo-3 multiplication gates resulted from the decomposition of the ternary FPRM logic function under polarity p; each multi-input modulo-3 addition operation is decomposed into several 2-input modulo-3 addition operations (also referred to as 2-input modulo-3 addition gates), and each multi-input modulo-3 multiplication operation is decomposed into several 2-input modulo-3 multiplication operations (also referred to as 2-input modulo-3 multiplication gates); the number of the 2-input modulo-3 addition gates resulted from the decomposition of the h.sup.th multi-input modulo-3 addition gate is denoted as No.sub.h._of_Mod 3A.sub.P, h=1, 2, . . . , N; the number of the 2-input modulo-3 multiplication gates resulted from the decomposition of the w.sup.th multi-input modulo-3 multiplication gate is denoted as No.sub.w._of_Mod 3M.sub.p, w=1, 2, . . . , W;

[0077] Represent

[00019]$S=\underset{h=1}{\overset{N}{.Math.}}.Math.{\mathrm{No}}_h.\mathrm{\_of}.Math.\mathrm{\_Mod3}-A_p+\underset{w=1}{\overset{W}{.Math.}}.Math.{\mathrm{No}}_w.\mathrm{\_of}.Math.\mathrm{\_Mod3}-M_p$

be an area estimation model of the ternary FPRM circuit, where S represents the area;

[00020]$\underset{h=1}{\overset{N}{.Math.}}.Math.{\mathrm{No}}_h.\mathrm{\_of}.Math.\mathrm{\_Mod3}-A_p$

represents the total number of 2-input modulo-3 addition gates resulted from the decomposition of the ternary FPRM logic function under polarity p;

[00021]$\underset{w=1}{\overset{W}{.Math.}}.Math.{\mathrm{No}}_w.\mathrm{\_of}.Math.\mathrm{\_Mod3}-M_p$

represents the total number of 2-input modulo-3 multiplication gates resulted from the decomposition of the ternary FPRM logic function under polarity p;

[0078] 2) Establishing a corresponding relationship between the ternary FPRM circuit and population migration algorithm:

[0079] Population migration algorithm includes the following key factors: population location, attraction of population location, the greatest attractive site, the greatest attraction, ground space of population mobility, concession region, population mobility, population migration and population disperse; the area optimization of the ternary FPRM circuit includes the following key factors: polarity, area size corresponding to polarity, optimal polarity, minimum area, optional polarity space, the zone where the optimal polarity exists, polarity jump to the zone where the optimal polarity exists and jump out of the local optimal polarity;

[0080] The population location is mapped to area optimization of the ternary FPRM circuit, and represented as polarity; the attraction of the population location is mapped to area optimization of the ternary FPRM circuit, and represented as the area size corresponding to the polarity; the greatest attractive site is mapped to area optimization of the ternary FPRM circuit, and represented as the optimal polarity; the greatest attraction is mapped to area optimization of the ternary FPRM circuit, and represented as the minimum area; the ground space of population mobility is mapped to area optimization of the ternary FPRM circuit, and represented as an optional polarity space; the concession region is mapped to area optimization of the ternary FPRM circuit, and represented as the zone where the optimal polarity exists; the population mobility is mapped to area optimization of the ternary FPRM circuit, and represented as polarity transition; the population migration is mapped to area optimization of the ternary FPRM circuit, and represented as polarity jump to the zone where the optimal polarity exists; the population disperse is mapped to area optimization of the ternary FPRM circuit, and represented as polarity jump out of the local optimal polarity;

[0081] 3) Setting an attraction function for calculating the attraction of the population location in population migration algorithm:

[0082] According to the area estimation model, an attraction function for calculating the attraction of the population location in population migration algorithm is set as follows: in population migration algorithm, greater attraction indicates higher economic level of the population location, whereas the area-optimal polarity requires the area to be as small as possible, and therefore, in order to combine both conditions, the reciprocal of the area is employed to represent the attraction, and the attraction function is obtained as follows:

[00022]$\begin{array}{cc}\mathrm{attraction}=\left(1/S\right)*=\left(1/\left(\underset{h=1}{\overset{N}{.Math.}}.Math.{\mathrm{No}}_h.\mathrm{\_of}.Math.\mathrm{\_Mod3}-A_p+\underset{w=1}{\overset{W}{.Math.}}.Math.{\mathrm{No}}_w.\mathrm{\_of}.Math.\mathrm{\_Mod3}-M_p\right)\right)*& \left(2\right)\end{array}$

[0083] where the symbol / denotes a division operation, and attraction represents attraction value, greater attraction value indicates better area optimization effect of the circuit; is a magnification coefficient, its value is equal to a natural number greater than 1000;

[0084] 4) Setting relevant parameters of population migration algorithm:

[0085] Population migration algorithm has five parameters to be set: population scale s, the number of population mobility times l, population pressure parameter q, shrinkage factor c, and the number of population disperse times z;

[0086] Represent the population scale s be equal to the number of input variables of the ternary FPRM logic function, i.e., s=n; the number of population mobility times l is the radius of the region where the population exists, and the radius where the population exists is denoted as t, l=t, t=3.sup.s/s.sup.2; the population pressure parameter q is t/10; the shrinkage factor c=0.3; when the ternary FPRM circuit is a small-scale circuit, the number of population disperse times z=15, and when the ternary FPRM circuit is a large-scale circuit, the number of population disperse times z=2; a large-scale circuit usually refers to a circuit having 4 or more input variables, and a small-scale circuit usually refers to a circuit having 4 or less input variables;

[0087] 5) Employing population migration algorithm to calculate and obtain the greatest attractive site and the greatest attraction, wherein the greatest attractive site is the optimal polarity of the ternary FPRM circuit, and the greatest attraction is the minimum area of the ternary FPRM circuit.

[0088] In this embodiment, in the step 5), the calculation process of population migration algorithm is as follows:

[0089] 51) In the ground space of population mobility, a random function rand( ) is employed to generate population locations in number S, and the population locations in number S are denoted as P1, P2, . . . , Ps, then the P1, P2, . . . , Ps are taken as center points respectively, so that the regions in number S where the population exists are determined, according to the radiuses of the regions where the population exists;

[0090] 52) The attraction function is used to calculate the attraction of the population location Pv, v=1, 2, 3, . . . , s, to obtain the attraction of the population locations P1, P2, . . . , Ps;

[0091] 53) By comparing the attraction of the population locations P1, P2, . . . , Ps, the population location with the greatest attraction is selected as the greatest attractive site, then the greatest attractive site and the greatest attraction are recorded;

[0092] 54) Population mobility is performed: In the population region corresponding to the population location Pv, a random function is employed to randomly generate a population location Pv, to obtain P1, P2, . . . , Ps, then P1, P2, . . . , Ps is used to update the population locations P1, P2, . . . , Ps, namely P1=P1, P2=2, . . . , Ps=Ps, where Pv=2*t*rand( )+(Pvt), the symbol * denotes multiplication operation, t denotes the radius of the population region; rand( ) the random function;

[0093] 55) The updated population locations P1, P2, . . . , Ps in the step 54) are processed by following the steps 52)-53), to obtain the updated greatest attractive site and the updated greatest attraction;

[0094] 56) Population migration is performed: the updated greatest attractive site in step 55) is taken as the center point, so that the concession region is determined according to the radius t of the population region, then a random function rand( ) is employed to generate population locations in number S in the concession region, so that the obtained population locations in number S are used to again update the population locations P1, P2, . . . , Ps;

[0095] 57) The updated population locations P1, P2, . . . , Ps in the step 56) are processed by following the steps 52)-53), to obtain the again updated greatest attractive site and the again updated greatest attraction;

[0096] 58) Shrinkage of the concession region is performed: Represent t=(1c)*t and employ t to update t, the steps 56)-57) are repeated until t<q;

[0097] 59) After the concession region is shrunk to a certain extent that t<q, population disperse is performed: the steps 51)-58) are repeated, until the number of population disperse times z is met, and so the algorithm ends, to obtain the last updated greatest attractive site and the last updated greatest attraction;

[0098] 510) The last updated greatest attractive site and the last updated greatest attraction are output, wherein the greatest attractive site is the optimal polarity of the ternary FPRM circuit, and the greatest attraction is the minimum area of the ternary FPRM circuit.

[0099] In this embodiment, in the step 1), a ternary-FPRM-polarity transform technology is employed to obtain the ternary FPRM logic function, and the specific process is as follows:

[0100] 1) The required polarity of the ternary FPRM circuit is denoted as p, and p is expressed in ternary form as p=p.sub.n-1 p.sub.n-2 . . . p.sub.0, where n represents the number of the input variables;

[0101] 2) For p.sub.j, its corresponding fixed-polarity GF transformation matrix G.sub.3.sup.<p.sup.j.sup.> is generated; where,

[00023]$p_j\left\{p_{n-1},p_{n-2},\mathrm{.Math.}.Math.,p_0\right\},j\left\{n-1,n-2,\mathrm{.Math.}.Math.,0\right\};\mathrm{when}.Math..Math.p_j=0,G_3^{<p_j>}=G_3;\mathrm{when}.Math..Math.p_j=1,G_3^{<p_j>}=G_3^{<1>};\mathrm{when}.Math..Math.p_j=2,G_3^{<p_j>}=G_3^{<2>};G_3=\left[\begin{array}{ccc}1& 0& 0\\ 0& 2& 1\\ 2& 2& 2\end{array}\right],G_3^{<1>}=\left[\begin{array}{ccc}0& 0& 1\\ 2& 1& 0\\ 2& 2& 2\end{array}\right],G_3^{<2>}=\left[\begin{array}{ccc}0& 1& 0\\ 1& 0& 2\\ 2& 2& 2\end{array}\right];$

[0102] 3) The minterm M is expressed in ternary form as a sequence M=M.sub.n-1 M.sub.n-2 . . . M.sub.0, M.sub.j{0, 1, 2}, and its corresponding function value is denoted as (M);

[0103] 4) According to the formula (3), for each minterm, a new term .sub.j is generated, .sub.j{0, 1, 2}; According to the formula (4), the contribution of the new item to the FPRM coefficients is calculated, and the contribution value is denoted as v();

.sub.j={t|G.sub.3.sup.<p.sup.j.sup.>[t,M.sub.j]0},t{0,1,2}(3)

v()=(v.sub.n-1.Math.v.sub.n-2 . . . v.sub.0).Math.(M)(4) [0104] where =.sub.n-1 .sub.n-2 . . . .sub.0, v.sub.j=G.sub.3.sup.<p.sup.j.sup.>[.sub.j,M.sub.j].

[0105] 5) An index table is employed to record the generated new term and the contribution value of each new tem, if the generated new term already exists, then the contribution values of the identical new items are superimposed and presented as the contribution value of that new item;

[0106] 6) The steps 3)-4) are repeated for all the minterms, and the contribution values corresponding to respective new terms are the FPRM expansion coefficients;

[0107] 7) According to the FPRM expansion coefficients, the ternary FPRM logic function expression is obtained.

[0108] The area optimization method of the present invention is compared with whole annealing genetic algorithm in regard to their optimization results, through simulation and verification on 10 MCNC Benchmark circuits in Windows 7 64-bit operating system, under the operating environment of Intel Core i3-2130 CPU 3.40 GHZ, 4G RAM, with implementation of C programs compiled with VC6.0.

[0109] The search results for the area-optimal polarity of the ternary FPRM circuit are shown in Table 1. in Table 1, column 1 shows the names of the circuits; column 2 indicates the number of input variables of the ternary circuits, respectively; column 3, column 4, column 5 and column 6 indicate the searched optimal polarity, the number of modulo-3 addition operations, the number of modulo-3 multiplication operations and the running time of whole annealing genetic algorithm in order, respectively; column 7, column 8, column 9 and column 10 indicate the searched optimal polarity, the number of modulo-3 addition operations, the number of modulo-3 multiplication operations and the algorithm running time of the method of the present invention in order, respectively.

TABLE-US-00001 TABLE 1 Search result for area-optimal polarity of ternary FPRM circuit Whole Annealing Genetic The method of the present Algorithm invention Number Number Number of Number of of of Number modulo-3 modulo-3 modulo-3 modulo-3 Circuit of input addition multiplication Time addition multiplication Time name variables Polarity operations operations (s) Polarity operations operations (s) Sqn 4 5 33 135 4.89 53 27 118 1.66 Z5xp1 4 50 26 119 5.06 71 23 110 3.38 Con1 4 23 10 49 5.65 77 9 47 2.21 Misex1 4 43 14 64 6.2 70 15 60 4.05 Tms 4 80 32 146 7.2 35 22 107 3.54 Sex 5 158 34 160 14.23 155 30 159 5.85 Apla 5 242 19 136 17 74 19 120 0.5 Br1 6 26 15 104 32.35 467 15 96 1.21 T4 6 385 9 54 33.28 397 8 47 29.68 Table3 7 850 737 5465 1191.3 1345 644 4960 509.64

[0110] Compared with whole annealing genetic algorithm, the area-saving and time-saving (in percentage) achieved by the optimization method of the present invention are as shown in Table 2. The percentages of area-saving and time-saving are defined respectively as follows:

[00024]$\begin{array}{cc}{\mathrm{Save}}_{\mathrm{Area}}.Math..Math.\%=\frac{{\mathrm{Area}}_{\mathrm{WAGA}}-{\mathrm{Area}}_{\mathrm{PMA}}}{{\mathrm{Area}}_{\mathrm{WAGA}}}100.Math.\%& \left(5\right)\\ {\mathrm{Save}}_{\mathrm{Time}}.Math..Math.\%=\frac{{\mathrm{Time}}_{\mathrm{WAGA}}-{\mathrm{Time}}_{\mathrm{PMA}}}{{\mathrm{Time}}_{\mathrm{WAGA}}}100.Math.\%& \left(6\right)\end{array}$

[0111] where, Save.sub.Area represents the area-saving, Save.sub.Time represents the time-saving in running the algorithm; Area.sub.WAGA represents the optimized area achieved by whole annealing genetic algorithm, Time.sub.WAGA represents the optimization time of whole annealing genetic algorithm; Area.sub.PMA represents the optimized area achieved by the method of the present invention, Time.sub.PMA represents the optimization time of the optimization method of the present invention.

TABLE-US-00002 TABLE 2 Percentages of area-saving and time-saving in area optimization of ternary FPRM circuit Area Whole Savings % (in Number Annealing The method of percentage) Circuit of input Genetic the present Area- Time- name variables Algorithm invention. saving saving Sqn 4 168 145 13.69 66.05 Z5xp1 4 145 133 8.28 33.20 Con1 4 59 56 5.08 60.88 Misex1 4 78 75 3.85 34.68 Tms 4 178 129 27.53 50.83 Sex 5 194 189 2.58 58.89 Apla 5 155 139 10.32 97.06 Br1 6 119 111 6.72 96.26 T4 6 63 55 12.70 10.82 Table3 7 6202 5604 9.64 57.22 Average savings % 10.04 56.59

[0112] As inferred from analysis of data in Table 2, the area optimization method of the present invention has an obvious effect of optimization. Compared with whole annealing genetic algorithm, the method of the present invention leads to average area-saving of 10.04% and average time-saving of 56.59% on 10 testing circuits.

[0113] Unless otherwise indicated, the numerical ranges involved in the invention include the end values. While particular embodiments of the invention have been shown and described, it will be obvious to those skilled in the art that changes and modifications may be made without departing from the invention in its broader aspects, and therefore, the aim in the appended claims is to cover all such changes and modifications as fall within the true spirit and scope of the invention.