Patent Document ID: 10108663
Application ID: 15252306
Patent Flag: 1

Claim One:
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: f p ⁡ ( x n - 1 , x n - 2 , … ⁢ , x 0 ) = ⊕ ∑ i = 0 3 n - 1 ⁢ a i * ∏ j = 0 n - 1 ⁢ x. j i j ( 1 ) where n is the number of variables of the function ƒ p (x n-1 , x n-2 ,. .. , x 0 ), x n-1 , x n-2 ,. .. , x 0 denotes the n input variables of the function ƒ p (x n-1 , x n-2 ,. .. , x 0 ), p denotes a polarity of the function ƒ p (x n-1 , x n-2 ,. .. , x 0 ), the polarity p is expressed in ternary form as p n-1 p n-2. .. p 0 , p j ϵ{0, 1, 2}, j=0, 1, 2,. .. , n−1, ⊕ represents a modulo-3 addition operation, Σ is a summation sign, the symbol “*” represents multiplication, subscript i=0, 1, 2,. .. , 3 n −1, i is expressed in ternary form as i n-1 i n-2. .. i 0 , a i is a coefficient of FPRM expansion, a i ϵ{0, 1, 2}; Π represents a modulo-3 multiplication operation, ∏ j = 0 n - 1 ⁢ x. j i j has its expansion as follow: ∏ j = 0 n - 1 ⁢ x. j i j = x. n - 1 i n - 1 ⁢ x. n - 2 i n - 2 ⁢ ⁢ … ⁢ ⁢ x. 0 i 0 , where i j ∈{0, 1, 2}, {dot over (x)} j =(x j ⊕p j ), {dot over (x)} j 0 =1={dot over (x)} j 1 ={dot over (x)} j , {dot over (x)} j 2 ={dot over (x)} j *{dot over (x)} j , polarity p and subscript i determine the representation of the variable {dot over (x)} 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 h ._of_Mod 3−A 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 w ._of_Mod 3−M p , w=1, 2,. .. , W; represent S = ∑ h = 1 N ⁢ No h • ⁢ _of ⁢ _Mod3 - A p + ∑ w = 1 W ⁢ No w • ⁢ _of ⁢ _Mod3 - M p be an area estimation model of the ternary FPRM circuit, where S represents the area; ∑ h = 1 N ⁢ No h • ⁢ _of ⁢ _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; ∑ w = 1 W ⁢ No w • ⁢ _of ⁢ _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: attraction = ( 1 / S ) * α = ( 1 / ( ∑ h = 1 N ⁢ No h • ⁢ _of ⁢ _Mod3 - A p + ∑ w = 1 W ⁢ No w • ⁢ _of ⁢ _Mod3 - M p ) ) * α ( 2 ) 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 s /s 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.