A generalized of conjuncterms simplification rules in polynomial settheoretical format has been considered. These rules are based on the proposed theorems for different initial conditions transform of pair conjuncterms, Hamming distance between them can be arbitrary. These rules may be useful to minimize in polynomial set-theoretical format of arbitrary logic functions with n variables. Advantages of the proposed rules of simplification are illustrated by several examples.
Investigations [1–8] have shown that it is economically profitable to build digital devices such as arithmetic units, coding-error detectors as well as devices with programmed logic, etc. on logical elements AND-EXOR, which realize polynomial basis {&, ⊕, 1}, that is AND, EXCLUSIVE OR (EXOR) logical operations and constant 1. It is easier to test and diagnose [9–11] digital devices on AND-EXOR if compared to the devices built on AND-OR. However, in spite of the mentioned advantages it is more difficult to minimize a function in polynomial format, i. e. in ESOP (EXOR SumOf-Product), than in disjunctive format, i. e. in SOP (Sum-Of-Product). If the merge operation of adjacent conjuncterms (conjunction of literals) is only applied in the SOP minimization, than, in addition, the same operations can be applied in the ESOP minimization [1, 2].
A precise solutions of a minimization problem in ESOP generally are based on analytical [2] or on visual transformations [1–3]. Respectively, such methods are suitable only for functions from small amount of variables [5, 7, 10–13] and only for special classes for functions with up to 10 variables [14]. Heuristic methods have comparatively wider practical application [1, 8, 16–23]. Among them there are minimization method based on a coefficient of generalized canonical Reed-Muller forms using of matrix transformations [1, 8, 11, 16] and the method based on iterative execution of operations with conjuncterms of different ranks of the given function. To the last belongs the algorithm [17], which after transformation of the given function in Positive Polarity Reed-Muller expression minimizes it on the basis of three operations with conjuncterms. Better results have been shown by algorithm based on the procedure of so-called linked product terms [18, 19]. Later, on the basis of this procedure, the algorithms have been developed and completed with more perfect operations (that is primary xlink, secondary xlink, unlink, exorlink), which can be used for minimization of a system of complete and incomplete functions [20, 21].
However, the mentioned above algorithms have one drawback in common. They involve the procedure of linking in pairs only conjuncterms of the same rank r ∈ {1, 2, . . . , n}, which differs between each other by binary positions. Correspondingly, this limits the use of such algorithms to functions given in SOP or ESOP, which can have triple conjuncterms in the different part. In these cases to conjuncterms that differ in ranks certain procedures of transformation are applied leading to an increase of procedural steps and processing time. Besides, the above mentioned operations of conjuncterms linking and other rules of simplification [24–26] do not have generalized character as to Hamming distance between any two conjuncterms of different ranks of a given function that does not guarantee the final minimized result.
In this paper we consider a new method of minimization of Boolean functions with n variables in polynomial set-theoretical format (PSTF), based on a procedure of splitting of conjuncterms [27–29] and on usage of generalized set-theoretical rules of conjuncterms simplification [30]. The suggested rules guarantee better (as to costs of realization and number of procedure steps) results of minimization of logic functions proved by the numerous examples that are borrowed from publications of other authors for comparison purposes. 2
Boolean function f (x1, x2, . . . , xn) that undergoes minimization, will be given by a set of binary minterms or in perfect set-theoretical form (STF) as a Y 1 = {m1, m2, . . . , mk}1, or in perfect polynomial set-theoretical form (PSTF) as a Y ⊕ = {m1, m2, . . . , mk}⊕ [30, 31].
The generalized set-theoretical rules of simplification [30] of a conjuncterm set of any function f , given in PSTF Y ⊕, are based on iterative process of simplification of two conjuncterms θ1r1 = (σ1σ2 · · · σn) and θ2r2 = (σ1σ2 · · · σn), σi ∈{0, 1, –}, r1, r2 ∈{1, 2, . . ., n}, which differ in Hamming difference d = 1, 2, . . ., n it is number of different in value α, β, γ, δ, . . . ∈ {0, 1, −} of onename positions. Here the different part α, β, γ, δ, . . . of these conjuncterms may have a different total number of literals kl. For example, two pairs of conjuncterms 1011––0110 and 1011––1–01 have d = 3, but the first has kl = 6, and the second kl = 5. Therefore, different initial conditions of transformation of two conjuncterms are possible.
We will consider the following conditions: • when kl = 2d, here two conjuncterms are of the same r-rank θ1r and θ2r but differ in d onename binary positions α, β, γ, δ, . . . ∈ {0, 1}; • when kl = 2d−1, here one conjuncterm of (r−1)-rank θ1r−1 and the second of r-rank θ2r differ in d onename positions α, β, γ, δ, . . . ∈ {0, 1, –}, where dash (–) belongs to θr−1; 1 • when kl = 2(d − 1), here two conjuncterms are of the same (r − 1)-rank θr−1 and 1 θr−1 differ in d onename positions α, β, γ, δ, . . . ∈ {0, 1, –} and each of them has 2 one dash (–).
As a result of transformation of two conjuncterms in PSTF a transformed PSTF Y ⊕ will be formed, where power kY will depend on distance d. Efficiency of simplification of two different conjuncterms for the mentioned above initial conditions will be estimated on the basis of comparison of interrelation k∗/kl∗, obtained on the ground of data θ of transformed PSTF Y ⊕, where kθ∗ is number of transformed conjuncterms and kl∗ is number of their literals, with initial interrelation kθ/kl, where in this case kθ = 2. 3
Three Theorems about Conjuncterms Transformation Theorem 1. Two conjuncterms of r-rank θ1r and θ2r, r ∈ {1, 2, . . ., n}, of the function f (x1, x2, . . ., xn), that differ in values d of onename binary positions α, β, γ, δ, . . . ∈ {0, 1}, in polynomial set-theoretical format form a set of transformed PSTF Y ⊕ of ipnowdieffrekreYnt=padr!t, tehaecthotoafltnhuemmbceornosfisltisteorfaklsθ∗k=l∗ =d cdo(ndj−un1ct)e.rms of (r −1)-rank and has Proof. To determine kθ∗/kl∗ and kY let us consider the transformation of conjuncterms θ1r and θ2r for d = 0, 1, 2, 3, 4. Here it should be mentioned that initial interrelation kθ/kl = 2/2d. • If d = 0, than θ1r = θ2r. So, transformed PSTF Y ⊕ = {θ1r, θ2r}⊕ = ∅, that corresponds to analytical expression a ⊕ a = 0. In this case kθ∗/kl∗ = 0/0; kY = 1. • Let d = 1. Then θ1r = (σ1 · · · α¯i · · · σn) and θ2r = (σ1 · · · αi · · · σn), αi ∈ {0, 1}. Respectively, for analytical expression a¯ ⊕ a = 1 we can write:
Y ⊕ = {(σ1 ··· α¯i ··· σn), (σ1 ··· αi ··· σn)}⊕ = (σ1 ··· −i ··· σn),
(
For (
To simplify the writing of the conjuncterms of the given and transformed PSTF
Y ⊕ will be considered only for their different positions which will be written down in
a column. In (
αα¯ ⇒⊕ (–), (
a ⊕ b
obtain
(
For (
For (
In the case of necessity for any pair of conjuncterms of r-rank of a function f , that have distance d > 4, one can in similar way form a set of d! of transformed PSTF Y ⊕; d = 1, 2, ..., n.
Based on the considered above, one can state that two conjuncterms of r-rank θr 1 and θ2r function f , that differ d = 1, 2,..., n in different by values onename binary positions α, β, γ, δ, ... ∈ {0, 1}, form in polynomial format a set with kY = d! of transformed PSTF Y ⊕, each of them consisting of different conjuncterms of (r−1)-rank with kθ∗/kl∗ =d/d(d−1), that is the proof of Theorem 1. ⊔⊓ Theorem 2. Two conjuncterms of the function f(x1, x2, ..., xn), one of which of (r−1)rank θr−1 differs from another r-rank θ2r in the number of d different in values one1 name positions α, β, γ, δ, ... ∈ {0, 1, –}, among which the dash (–) belongs to θr−1, 1 r ∈ {1, 2, ..., n}, in polynomial set-theoretical format create kY = (d − 1)! of sets of transformed PSTF Y ⊕, each of them has power kθ∗ = d and the total number of literals in different part kl∗ = d(d − 1) − (d − 2), here: • if d = 1, then α–˜ ⇒⊕ (α¯˜);
α¯– ⊕
• if d = 2, then αβ˜ ⇒
––
αβ˜¯ ,
α¯–––β¯–
• if d = 3, then αα¯ββ¯γ–˜ ⇒⊕α–ββ–γ˜¯,ααβ–γ–˜¯,
–β¯ ⊕ ––
α˜β ⇒ α˜¯β ;
α¯––––γ¯ –β¯–––γ¯
αα¯β–˜γ¯γ ⇒⊕––¯γ ,α–¯–, α–˜ββ¯γ¯γ ⇒⊕α–˜¯β–γγ,α¯˜–ββ–γ, (
α¯β¯––α¯β¯––α¯–γ¯–α¯–γ¯––β¯γ¯––β¯γ¯– α¯β¯γ¯– ⇒⊕α¯–γ–,–β¯γ–,α¯β––,–βγ¯– αβ¯––,α–γ¯– αβγδ˜ –βγ–α–γ––βγ–αβ––,α–γ–αβ–– , αβγδ˜¯αβγδ˜¯αβγδ˜¯αβγδ˜¯αβγδ˜¯αβγδ˜¯
α¯β¯––α¯β¯––α¯––δ¯α¯––δ¯ –β¯–δ¯ –β¯–δ¯ α¯β¯–δ¯ ⇒⊕α¯––δ, –β¯–δ ,α¯β––, –β–δ¯,αβ¯––,α––δ¯ αβγ˜δ α–ββ–γ˜¯δδααβ–γ–˜¯δδα–ββ–γ˜¯δδααββ–γ˜¯δ–ααβ–γ–˜¯δδααββ–γ˜¯δ–, α¯–γ¯–α¯–γ¯–α¯––δ¯α¯––δ¯––γ¯δ¯––γ¯δ¯ α¯–γ¯δ¯ ⇒⊕α¯––δ,––γ¯δ,––γδ¯,α¯–γ–,α–γ¯–,α––δ¯ αβ˜γδ α–β–˜¯γγδδααβ–˜¯γ–δδααβ–˜¯γγ–δα–β–˜¯γγδδααβ–˜¯γ–δδααβ–˜¯γγ–δ, –β¯γ¯––β¯γ¯––β¯–δ¯–β¯–δ¯––γ¯δ¯––γ¯δ¯ –β¯γ¯δ¯ ⇒⊕–β¯–δ¯ ––γ¯δ,–β¯γ–,––γδ¯,–βγ¯–,–β–δ¯ α˜βγδ ––γ¯δ¯,–β–δ ––γδ–βγ––β–δ –βγ– , α˜¯βγδα˜¯βγδα˜¯βγδα˜¯βγδα˜¯βγδα˜¯βγδ where α˜, β˜, γ˜, δ˜ are binary positions of any value 0 or 1.
Proof. In this case the given PSTF Y ⊕ has interrelation kθ/kl = 2/(2d − 1). • Let d = 1. Then θ1r−1 = (σ1 ··· −i ··· σn), θ2r = (σ1 ··· α˜i ··· σn), α˜i ∈ {0, 1}, and respectively for the expression 1 ⊕ a˜ = a˜¯, a˜ ∈ {a, a¯}, we can write down such PSTF catioAnsoinfttehreregliavteionnPkSθ∗T/Fkl∗Y =⊕ d1u/e1,t othreenmcoovmalpoafreodnwecitohnkjuθn/cktler=m;2k/Y1 w=e1h.ave simplifi• Let d = 2. Then for θ1r−1 = (σ1 ··· α¯i ··· –j ··· σn) and θ2r = (σ1 ···αi ··· β˜j ··· σn) and θr−1 = (σ1 ··· –i···β¯j ···σn) and θ2r = (σ1···α˜i···βj ···σn), αi, βj∈{0, 1}, we will obtain 1 ¯ Y ⊕ = {(σ1···α¯i···–j···σn),(σ1···αi···β˜j···σn)}⊕ = {(σ1···–i···–j···σn),(σ1···αi···β˜j···σn)}⊕ and Y ⊕ = {(σ1···–i···β¯j···σn),(σ1···α˜i···βj···σn)}⊕ = {(σ1···–i···–j···σn),(σ1···α˜¯i···βj···σn)}⊕.
Comparing the obtained interrelation kθ∗/kl∗ = 2/2 with kθ/kl = 2/3, we see that transformed PSTF Y ⊕ is simpler than the given PSTF Y ⊕ for one literal. It should be noted, that a number of transformed PSTF Y ⊕ is determined by a number of binary positions in different part θ1r−1 and θ2r, that conforms to Theorem 1. Therefore, for d = 2 we have kY = 1. • Let d = 3. Then for θ1r−1= (σ1···α¯i···β¯j ···–k ···σn) and θ2r= (σ1···αi···βj ···γ˜k ···σn), θr−1= (σ1···α¯i···–j···γ¯k···σn) and θ2r= (σ1···αi···β˜j···γk···σn), θ1r−1= (σ1···–i···β¯j···γ¯k···σn) 1 and θ2r= (σ1 ···α˜i ···βj ···γk ···σn), we have: = ((σσ11·····α·¯–Yii·⊕····=·–β¯{j(j·σ····1·–·–k·k··α¯····i·σ·σ·nn·)β¯,),(j(σ·σ·11··–···k··–α·i·i····σ···nβ–)jj,(··σ····1––k·k·····α···σiσn·n)·,)·(,(βσσj11········γ˜·ααkii········σβ·βnjj·)}····⊕·γ˜¯γ=˜¯kk······σσnn)) ⊕,
Y ⊕={(σ1 ···α¯i ···–j ···γ¯k ···σn),(σ1 ···αi ···β˜j ···γk ···σ¯n)}⊕= ⊕ =((σ1 ···α¯i ···–j ···–k ···σn),(σ1 ···–i ···–j ···γk ···σn),(σ1 ···αi ···β¯˜j ···γk ···σn)) , (σ1 ···–i ···–j ···γ¯k ···σn),(σ1 ···αi ···–j ···–k ···σn),(σ1 ···αi ···β˜j ···γk ···σn) = ((σσ11······––iYi···⊕···β=¯–j{j(···σ···1–γ¯·kk·····–···iσσ·n·n·)β),¯,((jσσ·1·1···γ¯···k·––·i·i····σ···n–βj),j·(··σ···γ1kk········α˜·σσin·n·),)·,(β(σσj1·1·······γ·α˜¯kα˜¯i·i·······σ·ββnjj)·}··⊕···γ=γkk······σσnn)) ⊕.
The obtained kθ∗/kl∗ = 3/5 indicates on an increase by one conjuncterm, since
kθ/kl = 2/5; kY = 2.
• Let d = 4. Based on the considered above and taking into account the rule (
Thus, if a conjuncterm of (r − 1)-rank θr−1 differs from a conjuncterm of r-rank 1 θ2r in the number d of different by value onename positions α, β, γ, δ, . . . ∈ {0, 1, –}, here dash (–) belongs to θ1r−1, r ∈ {1, 2, . . ., n}, then (d − 1)! of sets transformed PSTF Y ⊕ will be formed, each of which having the interrelation kθ∗/kl∗ = d/(d(d − 1) − (d − 2)), that is the proof of Theorem 2. ⊔⊓ Theorem 3. Two conjuncterms of (r − 1)-rank θr−1 and θr−1, r ∈ {1, 2, . . ., n}, 1 2 of the function f (x1, x2, . . ., xn) differ in d onename binary positions • if d = 2, then • if d = 3, then α, β, γ, δ, ... ∈ {0, 1, –}, where each conjuncterm has one (–), in polynomial settheoretical format starting with d = 2, create kY = (d − 2)! of sets transformed PSTF Y ⊕, each of which has power kθ∗ = d and the total number of literals in the different part kl∗ = d(d − 1) − 2(d − 2) and : – – – α¯β˜– ⊕ ¯ α–γ˜ ⇒α¯β˜–, α–γ˜¯
(
–β¯– ––β– – α˜β¯γ¯– ⇒⊕α¯˜β¯γ¯–,α¯˜β¯γ¯– ,
– –γ– – –γ¯– –βγδ˜
–βγδ˜¯–βγδ˜¯
α¯– – –α– – –
α¯β¯γ˜– ⇒⊕–β– – –β¯– –
αβ–δ˜ α¯β¯γ˜¯–,α¯β¯γ˜¯– ,
αβ–δ˜¯αβ–δ˜¯
α¯– – –α– – –
αα¯β–˜γ˜–δδ¯ ⇒⊕α–α¯–β–¯˜γ˜¯––δδδ¯,α–α¯–β–¯˜γ˜¯––δδδ¯¯,
–β¯– ––β– –
α˜β¯–δ¯ ⇒⊕– – –δ – – –δ¯
–βγ˜¯δ α–˜¯ββ¯γ˜¯–δδ¯,α–˜¯ββ¯γ˜¯–δδ¯, (
– –γ¯–– –γ–
α˜–γ¯δ¯ ⇒⊕–α¯˜––γ¯–δδ¯,α¯˜–γ¯δ¯ , (
– – –δ¯
–β˜γδ –β˜¯γδ–β˜¯γδ where α˜, β˜, γ˜, δ˜ are binary positions of any value 0 or 1.
Proof. Given PSTF Y ⊕ has the initial interrelation kθ/kl = 2/2(d − 1).
• Let d = 2. Then θ1r = (σ1· · ·α˜i · · · –j · · · σn) and θ2r = (σ1 · · · –i · · · β˜j · · · σn),
¯
α˜i, β˜j ∈ {0, 1}. For f (a, b) respectively to (
Y ⊕ = {(σ1 ··· α˜i ··· β¯j ··· –k ··· σn), (σ1 ··· –i ··· βj ··· γ˜k ··· σn)}⊕ = = {(σ1 ··· –i ··· –j ··· –k ··· σn), (σ1 ··· α˜¯i ··· β¯j ··· –k ··· σn), (σ1 ··· –i ··· βj ··· γ˜¯k ··· σn)}⊕, Y ⊕ = {(σ1 ··· α¯i ··· β˜j ··· –k ··· σn), (σ1 ··· αi ··· –j ··· γ˜k ··· σn)}⊕ = = {(σ1 ··· –i ··· –j ··· –k ··· σn), (σ1 ··· α˜¯i ··· –j ··· γ¯k ··· σn), (σ1 ··· –i ··· β˜¯j ··· γk ··· σn)}⊕.
Compared with kθ/kl = 2/4 here kθ∗/kl∗ = 3/4 means that the transformed PSTF Y ⊕ has one more conjuncterm, here its rank is (r − 3); kY = 1. • Let d = 4. Then θ1r = (σ1 · · · α˜i · · · β¯j · · · γ¯k · · · –l · · · σn) and θ2r= (σ1 ··· –i ··· βj ··· γk ··· δ˜l ··· σn), θ1r= (σ1 ··· α¯i ··· β˜j ··· γ¯k ··· –l ··· σn) and θ2r= (σ1 ··· αi ··· –j ··· γk ··· δ˜l ··· σn), θ1r= (σ1 ··· α¯i ··· β¯j ··· γ˜k ··· –l ··· σn) and θ2r= (σ1 ··· αi ··· βj ··· –k ··· δ˜l ··· σn), θ1r=(σ1 ··· α˜i ··· β¯j ··· –k ··· δ¯l ··· σn) and θ2r= (σ1 ··· –i ··· βj ··· γ˜k ··· δl ··· σn), θ1r= (σ1 ··· α¯i ··· β˜j ··· –k ··· δ¯l ··· σn) and θ2r= (σ1 ··· αi ··· –j ··· γ˜k ··· δl ··· σn), θ1r= (σ1 ··· α˜i ··· –j ··· γ¯k ··· δ¯l ··· σn) and θ2r= (σ1 ··· –i ··· β˜j ··· γk ··· δl ··· σn). Here, for d = 4 the interrelation kθ∗/kl∗ = 4/8 is greater than the initial one kθ/kl = 2/6; kY = 2.
So, if two conjuncterms of (r−1)-rank θ1r−1 and θ2r−1, r ∈ {1, 2, . . ., n}, of the function f (x1, x2, . . ., xn) differ in d different by values onename positions α, β, γ, δ, . . . ∈ {0, 1, –}, among which each of these conjuncterms has one dash (–), then in polynomial set-theoretical format, starting with d = 2, they form kY = (d − 2)! of the sets transformed PSTF Y ⊕, each of them has interrelation kθ∗/kl∗ = d/(d(d−1)−2(d−2)), that is the proof of Theorem 3. ⊔⊓ Example 1. To apply Theorems 1, 2 and 3 to the function f (x1, x2, x3, x4), that is given by perfect STF Y 1 = {0, 3, 5, 6, 7, 8, 9, 10, 12, 15}1, which is minimized in polynomial format by K-maps method to the expression f = x1 ⊕ x2x3 ⊕ x2x4⊕ ⊕x3x4 ⊕ x1x2x3x4 ⊕ x¯1x¯2x¯3x¯4 [32, p. 97].
Solution. This function has PSTF Y ⊕ = {(1– – –),(–11–),(–1–1),(– –11),(1111),
(0000)}⊕. To the pair (1111) and (0000), that has d = 4, we will apply, for
example, the fourth PSTF from the rule (
Y ⊕ = (1– – –), (–11–), (–1–1), (– –11), 01–1
–111
Applying the rule (
Minimization of Complete and Incomplete Functions The proposed method of Boolean functions minimization in the polynomial settheoretical format is based on the idea of minterms splitting of a given function f (x1, x2, . . ., xn) in the disjunctive format [27–29].
The algorithm of minimization of a function f in the polynomial set-theoretical format is realized on two stages:
1-st stage: the procedure of splitting of minterms of a given function f and the obtaining of a set of covering of a matrix of splitting;
2-nd stage: the procedure of iterative simplification of conjuncterms of a set of covering (obtained on the 1-st stage) on the basis of generalized rules of Theorems 1, 2 and 3 and formation of a minimal PSTF Y ⊕ of a given function f .
The 1-st stage is realized by sequence of such steps:
Step 1: the given binary minterms m1, m2, . . .mk of the perfect PSTF Y ⊕ = {m1, m2, . . .mk}⊕ of the function f are split (operator ⇒S) by using the matrixcolumn of the masks of literals of rank r ≥ n − log2 k, r = 1, 2, . . ., n, as a result of n! this a matrix of splitting Mnr of Cnr × k dimension is formed, where Cnr = (n−r)!r! ; for example, let n = 5; if the number k of minterms is 8 ≤ k < 16, then we use the matrix of masks of rank r = 2, and as a result the matrix M52 of the dimension C52 × k is formed;
Step 2: in the matrix Mnr (in our example M52) for execution of the procedure of covering (operator ⇒C) the conjuncterms-copies of r-rank, the number of which 2n−r−1 < kr ≤ 2n−r (4 < kr ≤ 8) are highlighted by underlining; priority is given to conjuncterms-copies and their number is kr = 2n−r (kr = 8); if k = kr, then the matrix is covered with a conjuncterms-copy of r-rank; if kr < 2n−r (kr < 8), then the covering of the matrix will be made of the conjuncterms-copies the number of which 2n−r−1 < kr < 2n−r, and if there are not enough of them, then together with generating minterms of the matrix Mnr; if kr < 2n−r−1, then the transition to step 1 is done for realization of similar procedures with application of the matrix of masks of the rank r = 3 and etc. until to getting in the covering of the matrix Mnr of the minterms splitting of which provides its covering, if such minterms > 2, then the transition to step 1 is done.
The 1-st stage of algorithm is completed when there are not only minterms in the set of covering of the matrix Mnr or when the split elements do not provide its covering.
The 2-nd stage of the minimization algorithm is the procedure of iterative simplification. It is done with the conjuncterms of the set of the covering in sequence of the following steps:
Step 1: for every pair with d = 1 (pairs with d = 0 are not taken into account) either
the rule (
Step 2: for every pair with d = 2 we apply either one from the sets of the rule (
Step 3: for every pair with d = 3 we apply either one from the sets of the rule (
Step 4: for every pair with d = 4 we apply one from the sets of the rule (
Step 5: if further transformation does not lead to the simplification of the set of conjuncterms, then this set is the found minimal PSTF Y ⊕ of the function f , the cost of realization of which is determined by the interrelation kθ∗/kl . ∗ Example 2. To minimize the function f (x1, x2, x3, x4) in the polynomial format by using the splitting method. This function has perfect STF Y 1 = {0, 6, 14, 15}1 (this function is borrowed from [21, p. 28]).
000– 000– 001– 011– 010– 011– 00101010 ⇒00–1,01–1,00–0,00–0,01–1,01–0 .
0–11 0–01 0–11 0–10 0–00 0–00
After replacement of minterms (0000) and (0111) by the underlined sets in the set of
covering, we obtain two equal as to the realization cost of solutions of minimization of
the given function which is reflected by the minimal PSTF:
⊕
(
Y ⊕ = {(–11–),(0000),(0111)}⊕⇒ (–11–),(011–),
(1. (00–0),(
Answer. The cost of realization of the minimized function determines the interrelation kθ∗/kl∗ = 3/9 that is a better result than in [21], where the PSTF Y ⊕ = {(−11−), (0000), (0111)}⊕ that is equal to 3/10.
In [27, 28], the incomplete function f (x1, x2, . . ., xn) can be given by the perfect STF {Y 1, Y ∼}, where Y 1 and Y ∼ there are subsets of the complete set E2n, on which the function f takes the value respectively 1 and ∼ (so-called “don’t-care”). In the polynomial set-theoretical format the sets Y ⊕ and Y ⊕˜ correspond to the sets Y 1 and Y ∼, the elements of which are binary minterms. Thus, incomplete function f can be given by the perfect PSTF {Y ⊕, Y ⊕˜}.
Similarly, [27, 29] the procedure of splitting of conjuncterms of incomplete function . f is realized by the matrix of splitting Mnr, which is designated as M r⊕..M r ⊕˜, where .
M r⊕ that is basic submatrix, M r ⊕˜ that is additional submatrix, and .. that is a symbol of separation of the matrix Mnr. As a result of covering of the matrix Mnr a set of the . splitting conjuncterms Y ⊕..Y ⊕˜ is be obtained.
An algorithm of minimization of an incomplete function in the polynomial settheoretical format is realized in the same way as for a complete function in two stages. On the 1-st stage the minterms of the perfect PSTF {Y ⊕, Y ⊕˜} are split by using of the matrix Mnr, where the main role in its cover is played by the conjuncterms-copies of the basic submatrix M r⊕. Whereas the 2-nd stage of the algorithm of minimization of an incomplete function is realized in similar way as for a complete function. Example 3. To minimize incomplete function f (x1, x2, x3, x4) in the polynomial format by using splitting method. This function is has perfect STF (Y 1= {3, 5, 6, 9, 12, 15}1
(this function is borrowed from [33, p. 460]).
Y ∼= {1, 2, 8, 11}∼
(Y ⊕ = {(0011), (0101), (0110), (1001), (1100), (1111)}⊕ S ⇒
Y ⊕˜ = {(0001), (0010), (1000), (1011)} ⊕˜ l l – – 00– – 01– – 01– – 10– – 11– – 11– – 00– – 00– – 10– – 10– – l – l – 0–1– 0–0– 0–1– 1–0– 1–0– 1–1– 0–0– 0–1– 1–0– 1–1– =0– –1 0– –1 0– –0 1– –1 1– –0 1– –1 0– –1 0– –0 1– –0 1– –1⇒C ⇒S l– –l –ll– –01– –00– –11– –00– –10– –11– –00– –01– –00– –01– –l–l –0–1 –1–1 –1–0 –0–1 –1–0 –1–1 –0–1 –0–0 –0–0 –0–1 – –ll – –11 – –01 – –10 – –01 – –00 – –11 – –01 – –10 – –00 – –11 . ⊕ ⇒C {l–l–} = n((0–1–),(0111)), (1–0–),(1101) ,(0101),(1111)..(0001),(1011)o ⇒ ⇒ {(0–1–),(–111),(1–0–),(–101)}⊕⇒ {(0–1–),(–1–1),(1–0–)}⊕.
After the transformation of the pair of highlighted conjunñterms by the rule
(
Minimization of System of Complete and Incomplete Functions In general, the system F (X ), X = {x1, x2, . . ., xn}, of Boolean functions, fi(X ), i = 1, 2, . . ., s can be represented in the polynomial set-theoretical format as a perfect PSTF {Yi⊕, Yi⊕∗} [27, 29]:
Y1⊕={m11, m12, . . ., m1k1 }⊕ , Y1⊕∗={mk1+1, mk1+2, . . ., m2n−k1−ν1 }⊕∗ ,
F (X ) = Y2⊕={m21, m22, . . ., m2k2 }⊕ , Y2⊕∗={mk2+1, mk2+2, . . ., m2n−k2−ν2 }⊕∗ ,
Y.s.⊕. =..{. m..s.1., .m. .s.2., .. ....,.m. .s.k.s.}.⊕. ., .Y.s⊕..∗.=.{. m..k.s.+. 1. ,. m.. k.s. +..2., .. ....,. m..2.n.−.k.s.−. ν.s. }.⊕..∗.,. .
(
Similarly as in SOP form [27, 29] compatible minimization of the system of
PSTF {Yi⊕, Yi⊕∗} (
The algorithm of compatible minimization of the system F (X ) of complete functions given by the perfect PSTF Yi⊕ , Yi∗ ≡ ∅, is realized in the following way. On the first stage the system minterms (m)1,2,. . .,s′ of the set YI⊕ , I ∈ {1, 2, . . ., s}, are split by using the matrix Mnr creating a system conjuncterms of (n−1)-rank (θin−1)1,2,. . .,s′ . The minimal covering of the matrix Mnr is done in similar way [27, 29] by the identical system conjuncterms-copies of (n−1)-rank. But among them, a decisive role for realization of compatible minimization of the given system will be played by those ones the indices of which contain the greatest quantity of numbers with the set {1, 2, . . ., s}. Herewith, if (θir−1)1,2,. . .,s′ and (θjr−1)1,2,. . .,s′′ , s′, s′′ ∈ {1, 2, . . ., s}, these are identical system conjuncterms-copies of (r−1)-rank of the matrix Mnr, r = 1, 2, . . ., n−1, then they can be elements of its covering if the indices of their generative form (θir)1,2,. . .,s′ and (θjr)1,2,. . .,s′′ will form a not empty intersection, i. e. {1, 2, . . ., s′} T{1, 2, . . ., s′′} 6= ∅. For example, let the system minterms (100)1,2,4, (110)1,3, (010)1,2,3 be generative elements of the matrix Mnn−1. For the mask {l–l} the identical system conjunctermscopies will be (1–0)1 and (1–0)1, the index of which determines the intersection {1, 2, 4} T {1, 3} = {1}, and for the mask {–ll} will be (–10)1,3 and (−10)1,3 because {1, 3} T {1, 2, 3} = {1, 3}. So, in this case for covering of the matrix Mnn−1 it is recommended to choose the pair of the mask {–ll} because the power |{1, 3}| > |{1}|. Example 4. In the polynomial set-theoretical format to minimize the system F (X ) of complete functions fi(x1, x2, x3), i = 1, 2, 3, by the splitting method. This has perY11= {(000),(010),(101),(110)}1 fect STF Y21= {(001),(011),(101)}1 . This example is borrowed from [21, p. 35] Y31= {(000),(001),(010),(011)}1 where the author illustrates efficiency of xlinking method. Solution. Having transformed the given system of the perfect STF {Y11,2,3} into the system of the perfect PSTF {Y1⊕,2,3} and, having formed from it a set of system minterms, we will execute the splitting procedure by using the matrix M31 and its covering procedure:
Y1⊕,2,3 = (000)1,3, (001)2,3, (010)1,3, (011)2,3, (101)1,2, (110)1 ⊕ S ⇒ ⇒Sl––l––= 0––0––1,3 0––0––2,3 0––1––1,3 0––1––2,3 1––0––1,2 1––1––1⇒C – –l – –0 – –1 – –0 – –1 – –1 – –0 ⊕ ⇒Cn (0– –)1,3, (001)1,3, (011)1,3 , (0– –)2,3, (000)2,3, (010)2,3 , (101)1,2, (110)1o . We will do the splitting procedure with system minterms of the formed set by using the matrix M32 and its covering procedure: ll– S (001)1,3, (011)1,3, (000)2,3, (010)2,3, (101)1,2, (110)1 ⇒ l–l = –ll 01–
00–
=0–11,3 0–11,3 0–02,3 0–02,3 1–1 1–0 ⇒C{(
–01 –11 –00 –10 –01 –10
Having distributed system conjuncterms in the functions we obtain the system of the
PSTF {Y1⊕,2,3}, with the underlined elements of which we will do step by step the
transformations according to the rules (
Y3⊕ = {(0– –)}⊕
In case of the system of incomplete functions (
I a b c f1 f2 0 0 0 0 1 0 1 0 0 1 ∼ ∼ 2 0 1 0 0 1 3 0 1 1 1 ∼ 4 1 0 0 ∼ ∼ 5 1 0 1 ∼ 0 6 1 1 0 1 0 7 1 1 1 0 1 , with which we will do the Example 5. [37, p. 228, example 5.1] To minimize the system F (X) of incomplete functions f1(a, b, c) and f2(a, b, c), given by the truth table (see right) with the help of splitting method in the polynomial set-theoretical format.
Solution. The given system F (X) has the perfect PSTF (Y ⊕ 1˜= {(001), (100), (101)} ⊕˜ 1 = {(000), (011), (110)}⊕, Y ⊕
2˜= {(001), (011), (100)} ⊕˜ Y2⊕= {(010), (111)}⊕, Y ⊕ . ˜ We will form a set of system minterms i.e. Y1⊕,2..Y1⊕,2 splitting procedure by using the matrix M31 and the procedure of its covering, for example, for the mask {–l–}: Y1⊕,2...Y1⊕˜,2 = {(000)1,(010)2,(011)1,(110)1,(111)2...(001)1,2,(011)2,(100)1,2,(101)1}⊕ ⇒S l– – 0– – 0– – 0– – 1– – 1– – 0– – 0– – 1– – 1– – ⇒S–l–= –0–1 –1–2 –1–1 –1–1 –1–2 –0–1,2 –1–2 –0–1,2 –0–1 ⇒C {–l–} = – –l – –0 – –0 – –1 – –0 – –1 – –1 – –1 – –0 – –1 . ⊕ =n(000)1, (–1–)2,(011)2,(110)2 , (–1–)1,(010)1,(111)1 ..(001)1,2,(011)2,(100)1,2,(101)1o . After removal of the system minterm (011)2 the set of covering will look like . ˜ . ⊕ Y1⊕,2..Y1⊕,2=n(000)1, (–1–)2,(110)2 , (–1–)1,(010)1,(111)1 ..(001)1,2,(011)2,(100)1,2,(101)1o . Having distributed the system conjuncterms on the functions, we obtain the system . .
PSTF Y1⊕..Y1⊕˜ = {(–1–), (000), (010), (111)..(001), (100), (101)}⊕
. . .
Y2⊕..Y2⊕˜ = {(–1–), (110) .. (001), (011), (100)}⊕
We will do the splitting procedure with the minterms of the PSTF of the function f1 by using the matrixM31 and the procedure of its covering:
. l– – 0– – 0– – 1– – 0– – 1– – 1– – {(000),(010),(111)..(001),(100),(101)}⊕ ⇒S –l–=–0– –1– –1– –0– –0– –0–⇒C – –l – –0 – –0 – –1 – –1 – –0 – –1 ⇒C n (0– –), (011) , (– –1), (011) o
⇒ {(0– –), (– –1)}⊕.
⊕
Having taken into account the rule (
We will do similar procedures for the minterms of the PSTF of the function f2 by
applying the matrix M32 for their splitting:
{(110)...(001), (011), (100)}⊕ ⇒S lll–−l = 11–10– 000––1 001––1 11–00– ⇒C {(1–0), (
–ll –10 –01 –11 –00
After the transformation according to the rule (
(f1(a, b, c) = b ⊕ c¯ ⊕ a f2(a, b, c) = b ⊕ c¯ ⊕ a¯ .
Cost of realization of the system for the both solutions is equal to kθ∗/kl∗ = 4/4. If compared with [37] it is a better result, where cost of realization is equal to kθ∗/kl∗ = 4/7, namely: 6
(f1(a, b, c) = b ⊕ c¯ ⊕ ab
.
f2(a, b, c) = b ⊕ abc¯ A new minimization method in the polynomial set-theoretical format of complete and incomplete logic functions with n variables and their system has been presented. It consists in the splitting procedure of given minterms and iterative simplification of conjuncterms on the based set-theoretical rules. The method’s efficiency has been proved by numerous examples borrowed from well-known publications (see References) related to different minimization methods. The vast majority of functions and their systems minimized by the proposed method showed better results. This is due to the fact that in the process of transformation are involved the conjuncterms with Hamming distance d ≥ 3, the transformed PSTF of which may have elements for which in the given set there will be a pair with smaller d. The search procedure of such elements has s combinative character: after each replacement of a chosen pair of conjuncterms of the given PSTF Y ⊕ for certain set of the transformed PSTF Y ⊕ we obtain a new set where it is necessary to determine distance d between new pairs and, having chosen from them the elements with minimal d, to apply the rules of respective theorem and build again a new set and so on. As a result, the probability of effective simplification of conjuncterms set increases through the use of appropriate transformation rules that reduce the implementation cost of realization of minimized function.