# A Novel Graphical Technique for Combinational Logic Representation and Optimization

Authors: Vedhas Pandit; Björn Schuller
Journal: Complexity
 (2017)

---

## Abstract

We present a new technique for defining, analysing, and simplifying digital functions, through hand-calculations, easily demonstrable therefore in the classrooms. It can be extended to represent discrete systems beyond the Boolean logic. The method is graphical in nature and provides complete ‘‘implementation-free” description of the logical functions, similar to binary decision diagrams (BDDs) and Karnaugh-maps (K-maps). Transforming a function into the proposed representations (also the inverse) is a very intuitive process, easy enough that a person can hand-calculate these transformations. The algorithmic nature allows for its computing-based implementations. Because the proposed technique effectively transforms a function into a scatter plot, it is possible to represent multiple functions simultaneously. Usability of the method, therefore, is constrained neither by the number of inputs of the function nor by its outputs in theory. This, being a new paradigm, offers a lot of scope for further research. Here, we put forward a few of the strategies invented so far for using the proposed representation for simplifying the logic functions. Finally, we present extensions of the method: one that extends its applicability to multivalued discrete systems beyond Boolean functions and the other that represents the variants in terms of the coordinate system in use.


---

## Body

## 1. Introduction and Literature Overview

Combinational logic optimization is one of the first steps when designing any digital circuit. This practice helps chip designer save on number of transistors, chip area, and helps reduce logic delays and power requirements. It is no surprise therefore that many efforts have been made to develop fully functional, interactive programs for the industry even in the 80s, such as MIS [1] and SOCRATES [2] and the field has only grown ever since with the advent of many companies competing in this domain. In this section, we discuss various logic optimization methods. Advantages and drawbacks associated with each of these popular methods, especially the ones that offer graphical representation of a function or are simple enough for humans to hand-calculate, is the primary focus of this section. In view of the listed advantages and drawbacks, characteristic features of an ideal methodology are then presented.A Karnaugh-map (K-map) [3, 4] is a graphical technique for combinational logic optimization, which offers a very intuitive way to hand-calculate the proposed graphical representation of a Boolean function and its reduction. Using different colour schemes, multiple output functions involving the same inputs can be represented on a single K-map. However, it is only ideal for a function where the number of inputs is less than five. To represent functions involving more than four variables, one of the proposed implementations splits the graph into subgraphs—each subgraph representing only four variables at a time [5]. Another extension of the K-maps does not require splitting the graph into smaller units to represent functions with more than four variables, but some of the variable inversions can no longer remain adjacent to each other [6]—like in the case of K-maps for four inputs.A binary decision diagram (BDD) [7–10] is also a graphical method that is easy enough to implement and visualise. BDDs are often put to use as a data structure to both represent the Boolean functions and to perform the operations efficiently. Unlike K-maps, usability of this approach is not constrained by the number of inputs. Optimization is primarily about choosing the correct ordering of input variables and about reducing the number of “nodes” by merging equivalent nodes and by removing redundant ones. Diagram complexity depends a lot on the ordering of the input variables and the respectively applied decomposition type [7, 11], and it is not always easy to devise the correct order by mere visual inspection. This however, to a limited extent, is also a downside of the graphical approaches presented in this paper. As for BDDs, moreover, one cannot translate a given graphical representation back to its Boolean expression just by a quick visual skimming through—it is imperative to trace the entire paths starting from the output nodes back to the first input in order.Typed decision graphs (TDGs) [12] offer reduction of BDDs into a graph with a lot fewer nodes and connections. The advantages and drawbacks of the method are therefore mostly similar to those of BDDs, including dependence of the size/complexity of the representation on the ordering of the variables. Also closely related to BDDs are graphical techniques called “implicit graph based method” [13–15] and signal transition graphs (STGs) [16].The Quine–McCluskey algorithm [17–19] (or method of prime implicants) is functionally identical to Karnaugh mapping and is a deterministic way to check that the minimal form of a Boolean function has been reached. The tabular form makes it more efficient for use in computer algorithms, but, not being graphical, it is not as simple or as intuitive as Karnaugh-maps for use by the designer himself/herself. Petrick’s method (the branch-and-bound method) [20] is a technique for determining all minimum sum-of-products solutions from a prime implicant chart and could be looked upon as an extension to the Quine–McCluskey algorithm. The process gets tedious for a human for a large number of inputs and does not scale well on computers likewise. The Espresso algorithm [21] uses a radically different approach by applying heuristics, manipulating the “cubes” representing the product terms in the ON-, DC-, and OFF-covers iteratively, instead of expanding the minterms. Recently, a new paradigm has been proposed called “Majority-Inverter Graph” [22], which is a directed acyclic graph consisting of three-input majority nodes and direct/negated edges.Keeping classroom education of Boolean functions at the focus, several methodologies [23–27] that are mostly nongraphical and can best be demonstrated with systems with only a limited number of inputs have been proposed, in addition to more generalised software implementations [28–32] not directly useful for demonstrating the concepts through easy hand-calculations. Karnaugh-maps—due to the method’s graphical nature—continue to be used as the first method to explain the optimization process in the switching theory textbooks [33] still today.In the context of the comparison of the methods noted so far, we propose that the following are the desired characteristics of an ideal logic representation methodology:(i)
It is not constrained by the number of inputs or outputs and can in theory handle an infinite number of inputs and outputs. That is to say, multiple output functions can be represented simultaneously.(ii)
The optimization process should be intuitive; ideally visual inspection should be enough to establish input-output relationship. Or it should be based on a paradigm that is intuitive enough for a human to simply hand-calculate. Graphical methods like K-maps do offer that advantage.(iii)
If it is graphical, an equivalent numerical method should exist, which can effectively be used as a data structure to optimally represent combinational logic through conventional programming.(iv)
Translating a Boolean equation into the graphical representation (or vice versa) is a simple process.(v)
Ordering of variables should play no role in the complexity of the representation.The proposed technique satisfies all of the desired characteristics listed, except the very last one. Ordering of variables contributes to the ease with which a human can optimize a function without using any computing resources.


## 2. Definitions

(i)
The logical operators/symbols “¬”, “+”, “·”, “⊕”, and “⊙” denote the logical negation, OR, AND, XOR, and XNOR operations, respectively.
(ii)
The symbols “∏” and “∑” denote the logical AND and OR operations of the variables in iteration, respectively.
(iii)
a
0
,
a
1
,
a
2
,
…
,
a
i
,
…
,
a
n is a set of inputs to the combinational logic block under consideration.
(iv)
ϕ denotes an empty set.
(v)
SOP = sum of products.
(vi)
POS = product of sums.


## 3. Proposed Technique (Pandit-Plot)

Every Boolean equation is represented by a scatter plot in two dimensions. In effect, in its simplest version, corresponding to four quadrants, four Boolean expressions can simultaneously be represented and optimized on a single plane. By using different markers, one for each function, multiple logic functions may be represented in a single plane and subsequently reduced.


### 3.1. Coordinate System and Input Correspondence

Every integer coordinate “p” corresponds to an input combination ai1,ai2,…,aim such that(1)p=∑k=1m2ikp∈Z,ik∈N.One axis (say x-axis) represents a condition where the designated inputs are all True(T) (also called High(H) or logic level 1), while the other represents a case where those inputs are all False(F) (also called Low(L) or logic level 0). There is, therefore, a one-to-one correspondence between the set of all of combinations of the inputs and the set of points on the plane with integer coordinates. With such a representation system in place, every point on the plot with integer coordinates signifies a single product (in a SOP representation) or a single sum (in a POS representation). As an example, for a system with three inputs (a0,a1,anda2), the template of the plot that is restricted to the first quadrant (p≥0) will be as shown in Figure 1.Figure 1
Pandit-Plot (forn=3) with redundant data-points.Throughout the discussion henceforth, we only consider the template in the first quadrant. The templates in four quadrants are symmetric to each other, withx- and y-axes and the “x=y” and “x=-y” lines as the axes of symmetry. We observe that, in the scatter plot from Figure 1, certain data-points have been marked distinctively using the filled circles. These will be called “redundant” input combinations—for the reasons that will be explained in Section 3.3.


### 3.2. Representing an Input Combination

Representation of the combinational function “f” in graphical form may be done for “f” either in POS or in SOP form; the choice lies with the logic designer/user of the plot.To represent a function in SOP form, every constituent product term is separated into two products, one containing exclusively the direct inputs and the other only the negated inputs. The overall product is represented by a point(x,y), where, for example, the x-coordinate corresponds to the set of input combinations coming only from the direct inputs, while the y-coordinate corresponds to the set of input combinations from only the negated inputs, using (1). The absence of inputs implies that the corresponding coordinate is 0.As an example, let us consider the following sum of products:(2)f=a0a1+a0¬a1a2,represented by points (3,0) and (5,2), shown in Figure 2.(i)
For the first product “a0a1” to be True, both a0 and a1 need to be True. Therefore, the x-coordinate = 20+21=3, as per (1). Because there are no negated inputs in the first product, no ak needs to be False for f to be True. Therefore, the y-coordinate is 0. The product “a0a1” is, therefore, represented by point (3,0).(ii)
Similarly, for the product “a0¬a1a2” to be True, both a0 and a2 need to be True. Therefore, the x-coordinate = 20+22=5, as per (1). Also, a1 needs to be False for function f to be True. Therefore, the y-coordinate =21=2. The product “a0¬a1a2” is, therefore, represented by point (5,2).Figure 2
Pandit-Plot forf=a0a1+a0¬a1a2.Points(3,0) and (5,2) will be called “data-points” as they summarise the function by transforming it into numerical data, corresponding to the chosen coordinate system.Similarly, for a POS-based representation, we look forFalse (0/F/L) logic outputs to mark the points transforming every sum in the expression.Every Boolean function can therefore be represented by only two parameters alone in this way, namely, the coordinates of the representative points, irrespective of the number of inputs. This is a huge data compression in itself, where instead of storing the entire truth table, or even all of the combinations for which the output is either T or F (whichever count is less), we can simply represent a function with a few data-points. The system can further be optimized to remove extraneous information as will be explained in Sections3.3, 3.5, and 3.6.


### 3.3. Existence of Redundant Data-Points

It can easily be observed that there exist points on the plot with integer coordinates that correspond to a Boolean product or a Boolean sum that can never occur in a reduced SOP or a reduced POS expression, respectively.As an example, point(1,1) corresponds to the (a0¬a0) product in SOP which evaluates to 0/F, and the same point corresponds to the (a0+¬a0) sum in POS which evaluates to 1/T. These input combinations do not have any effect on the final expression evaluation, as the output corresponding to these input combinations is preknown and therefore redundant to be included as part of any Boolean expression (e.g., f+a0¬a0=f). We therefore discard such input cases and term these as “redundant points” in the discussions below, while the rest will be called “valid” points, except the origin, which falls into neither of the two categories, representing simply the trivial case of the output being independent of the inputs.


### 3.4. Generation of the Template

To translate any logic function to this plot, the first step is to build the necessary template or the canvas with all the input redundancies indicated (Figure1). Such a template may be generated by exploiting patterns for which the redundancies appear (Algorithm 1).Algorithm 1:Redundant set generation for Pandit-Plot.
(
1
)  procedure GENERATE1(n)   ⊳n= number of inputs
(
2
)   RedundantSet=ϕ
(
3
)   for  x←0,2n-1  do   ⊳ Represents direct inputs
(
4
)     for  y←0,2n-1  do  ⊳ Represents negated inputs
(
5
)       xbinary←(x)2
(
6
)       ybinary←(y)2
(
7
)       D←elementwise(xbinary∧ybinary)
(
8
)       if  any(D)=1  then
(
9
)         RedundantSet=RedundantSet∪(x,y)
(
10
)      end if
(
11
)      end for
(
12
)    end for
(
13
)  end procedureFor example, we note the following for a system withn inputs:(i)
Thex- and y-axes extend from 0 to 2n-1.(ii)
The points on the linex=y are redundant points.(iii)
All of the upper diagonal elements are redundant points.(iv)
Redundant points because of thea0 input’s logic level extend along both the x and y directions skipping every other point, that is, skipping the odd integer coordinates. The redundant points associated with a0 input are therefore of the form (2i+1,2j+1), where i,j are integers.(v)
Alternatively, the template may be generated using cellular automata rules on a brick-wall-like automata template as devised in Figure3 (in contrast to the typical cellular automata template as used in Conway’s game of life [34, 35]—where the borders of the individual cells coincide). This gives rise to the Sierpinski triangle [36, 37] pattern, as desired. The captions for the individual blocks indicate the (x,y) coordinates of the points that the blocks represent.Figure 3
Template generation from 2 different kinds of rules, signifying its relation to the Sierpinski triangle/fractals and the cellular automata.


### 3.5. Logic Laws

The logic optimization process is visual, intuitive, and simple—just as for Karnaugh-maps. It may alternatively be easily implemented using a computer program by understanding the strategies in place numerically. The basic idea of optimization is to get rid of excess of information by inspecting the scatter plot and bring the data-points as close to the axes as possible. There exist patterns that need to be utilised to effectively carry out this “reduction.” These patterns need to be formulated into a compilation of “logic laws.” A few examples of a logic law or an optimization strategy follow.Theorem 1 (2-integer-multiple hypotenuse rule).
If two of the data-points are vertices of an upright right angled isosceles triangle with its equal sides having length =2k  (k∈N) and if the third vertex is not to the right of any of those two data-points, then the two data-points could effectively be represented by that third vertex alone, so long as the third vertex is not a redundant point.Proof.
Let data-points beA(x1,y1) and B(x2,y2), such that x1>x2 and y1<y2 and (x1-x2)=(y2-y1)=2k,  k∈N, without loss of generalisation.
Because none of the three points,A(x1,y1), B(x2,y2), and C(x2,y1), is a redundant point and because x1+2k=x2, it follows that(3)x1=∑i=indx12i=2k+∑i=indx22i,where ind(p) is set of suffixes corresponding to inputs associated with coordinate “p.”
Similarly, it follows that(4)y2=∑i=indy22i=2k+∑i=indy12i.
Therefore, the pointB(x2,y2) represents both the direct and negated inputs corresponding to the point C(x1,y2), along with the input ¬ak. Similarly, the point A(x1,y1) represents both the direct and negated inputs corresponding to the point C(x1,y2), along with the input ak. The two points, A and B, therefore, effectively represent the inputs corresponding to the point C and, in addition, either the direct or the negated version of the input ak.
Therefore, in SOP form,(5)f≔fA+fB=akfC+¬akfC=fC,and, in POS form,(6)f≔fAfB=ak+fC¬ak+fC=fC,where fG≔  function associated with point G.
Thus, as per (5) and (6), this rule is simply a manifestation of the two well-known equalities (1)  P(q)+P(¬q)=P and (2)  (S+q)(S+¬q)=S for the template we present here—where P and S are, respectively, the product terms and the summation terms consisting of variables excluding q.As an illustration, if the plot in Figure4 represents a Boolean function f in SOP form with the points A and B as its “data-points,” then per the definitions earlier(7)f=a0¬a1a2+a0¬a1¬a2.This is because point A(5,2) translates to “a0¬a1a2,” while point B(1,6) represents “a0¬a1¬a2.”Figure 4
Diagonal optimization for SOP.Per the law proposed, pointsA and B are represented together by point C(1,2) alone, since the right angled triangle ABC is an isosceles triangle with its congruent sides having length 2k, k∈N(l(CA)=l(CB)=4).We find here that the hypothesis is true, since(8)f=a0¬a1a2+a0¬a1¬a2=a0¬a1a2+¬a2=a0¬a1⟹C1,2.If the scatter plot in Figure4 were to correspond to a POS representation, then the plot would have been represented as(9)f=a0+¬a1+a2a0+¬a1+¬a2.Effectively,(10)f=a0+¬a1+a0+¬a1a2+¬a2+a2¬a2=a0+¬a1⟹C1,2.In either case, pointsA(5,2) and B(1,6) are together represented by C(1,2) alone.Theorem 2 (symmetry about “x=y” line).
Two “valid” points symmetric about the “x=y” line in an SOP plot can be effectively represented by a newly defined logical operation represented by operator ⋆, where(11)ai⋆aj=∏ai·∏¬aj+∏¬ai·∏ajsuch  thatai∩aj=ϕ.Two “valid” points symmetric about the “x=y” line in a POS plot can be effectively represented by a newly defined logical operation represented by operator ⋆~, where(12)ai⋆~aj=∑ai+∑¬aj·∑¬ai+∑ajsuch  thatai∩aj=ϕ.Proof.
Two points symmetric about the “x=y” line will be of the forms A(x0,y0) and B(y0,x0). It follows that the set of direct inputs corresponding to the point A  (≔ai) is the same as the set of negated inputs that are represented by point B and vice versa (≔aj).
Because pointsA and B are not redundant points, it follows that ai∩aj=ϕ.
Therefore, for SOP,(13)∵fA=∏ai·∏¬aj,∴fB=∏¬ai·∏aj,such  thatai∩aj=ϕ,⇓f=fA+FB=∏ai·∏¬aj+∏¬ai·∏aj.
Similarly, for POS,(14)∵fA=∑ai+∑¬aj,∴fB=∑¬ai+∑aj,such  thatai∩aj=ϕ,⇓f=fA·FB=∑ai+∑¬aj·∑¬ai+∑aj.For a system with just two inputs, the “⋆” operator represents simply an “XOR” (⊕) operation, while the “⋆~” operator represents an “XNOR” (⊙) operation. The “NAND-only” implementation of “⋆/⋆~” operation is shown in Figure 5. This newly defined logic gate can then be optimized for given fan-in and fan-out values as necessary to be used as a building block in the subsequent logic design.Figure 5
“NAND-only” implementation of the newly defined logical operations “⋆ and ⋆~” that are essentially ⊕ (XOR) and ⊙ (XNOR) operations, respectively, for a two-input system.


### 3.6. Process of Optimization

While there is much scope for further research in this area for effective algorithm development in terms of logic optimization, including the ones targeted to novel topologies such as the ones involving IMPLY(¬A+B) gates alone, for example (instead of SOP/POS forms presented here, effectively implemented using “NAND alone” and “NOR alone” topologies, resp.), one of the most likely logic flows for such optimization is presented next.Steps involved in this example algorithm are as follows:(i)
“Generate” the template and plot the function.(ii)
“Expand” the expression to include every possible product in SOP form (every possible sum for a POS form).(iii)
“Reduce” the expression using logic laws.(iv)
“Repeat” the above two steps in iteration until no further reduction is possible, as illustrated in Figure6.Figure 6
Process of optimization; the steps in order are illustrated.
(a)
“Generate” step illustrated forf=(¬a1)+(a0)(a1)(a2)
(b)
“Expand” step illustrated for the product “(¬a1)”
(c)
‘‘Reduction” using the “2-integer-multiple hypotenuse rule”
(d)
The final optimized expression;f=(¬a1)+(a0)(a2)As an example, letf=(¬a1+a0a1a2), and let the representation form chosen be SOP-based as well. f ultimately gets reduced to f=¬a1+a0a2 as shown in Figure 6.(1)
Generate: plot the product terms (Figure6(a)).(2)
Expand: plot points relevant to each of the current data-points (Figure6(b)). Here, ¬a1 is expanded to include points wherever ¬a1=1⟹f=1.(3)
Reduce: reduce the expression using logic laws. If a new data-point, replacing one or some of the original data-points, is obtained through this process and if this data point cannot be further reduced, then it is noted and kept for the next iteration. (We note an example of such data-point with a label “NEW” in Figure6(c).)(4)
Repeat: repeat steps(2) and (3) until no new replacement data-point closer to the origin can be obtained (Figure 6(d)).Similar to the Karnaugh-maps, the “do not care” input combinations could be exploited for logic reduction [3, 38].


### 3.7. As a Data Structure

Because the individual Boolean terms are represented by only two coordinates (irrespective of the number of inputs), any combinational logic may be represented by two parameters alone. This can be viewed as a conversion of a graphical scheme to an equivalent nongraphical numerical scheme, to be handled by computing systems efficiently. The two coordinates may be stored in the memory as a single unit.Because one can represent any logic expression through a set of coordinates alone, we now investigate the number of bits required to store each of the numbered coordinates. While a proposed template forn inputs consists of 4n points (including the origin), the number of valid coordinates is only 3n-1. This is because a variable can manifest itself in an input combination in its original form (ak) or as a negated version (¬ak) or it could simply be absent. Thus, there are three possibilities for every input ak. The number of valid points is, therefore, 3n-1 (excluding the origin indicative of a trivial case where the output is independent of all of the inputs under consideration). Both the total number of points (τ=4n-1) in a template and the number of valid points (υ=3n-1) grow exponentially with n. The ratio of the number of bits thus required (with and without considering the redundant points) = ceil(log2(3n-1))/ceil(log2(4n-1)) which varies between 0.75 and 0.85 and eventually converges to 0.8 for large n. As an example, for n=3, υ=26, and τ=63, while, for n=6, υ=728, and τ=4095. Memory savings, thus, grow with n if we effectively take into account the redundancies in the template.However, in comparison to K-maps (=2n cells for an n-input system), our proposed method requires a much higher number of points (=3n-1, if we consider only the valid input combinations, excluding the origin). This is because the K-maps do not take into account all of the input combinations, but only the ones where each of the inputs manifests itself by its presence in its original or in its negated form (thus, 2n possibilities). In the proposed method, we explicitly take into account also the reduced input combinations where some of the inputs are absent.


### 3.8. Possible Extensions and Further Research Scope

(i)
Beyond SOP/POS paradigms: more patterns and the resulting optimization strategies need to be investigated in different logic gate methodologies, for example, SOP (“AND-OR”, which is “NAND-only”), POS (“OR-AND”, which is “NOR-only”), and “IMPLY-only” realisations.
(ii)
Multilevel logic: the concept could be extended to three dimensions to represent a ternary logic system, where both inputs and outputs can have three possible logic levels(0,1,2). The resulting representation is, thus, in the form of a “logic lattice” instead of the two-dimensional grid presented here, where the third dimension would serve a dual purpose. First, it represents a condition where all the inputs are logical level “2” (just as Z and Y represented states “1” and “0,” resp.). Secondly, the z-axis may also represent an output logic level within such a “logic slice.” As an example, output level-1 may correspond to a point with integer (X,Y,Z) coordinates, level-0 may correspond to a point just beneath this point, and level-2 just above (Figure 7).
(iii)
Alternate coordinate systems: every data-point symbolises a huge degree of information, but with only two or three parameters (coordinates). Because this information need not necessarily come about using a Cartesian coordinate system alone, one can choose to alternatively employ some other coordinate system and look for patterns and laws for optimization within such schemes. For example, a 2D polar system may be used, where the(x,y) to (r,θ) transformation is governed by the equations r=x, θ=2πy/(2n-1), and x,y∈[0,2n-1]. Note that θ remains in the range [0,2π] irrespective of the number of inputs (Figure 8). The logic laws for such alternate coordinate systems—where every coordinate of interest ψ follows the equation ψ=f(∑k=1m2ik),  ik∈N—can be devised by recognising the inherent patterns, which remains an open problem with further scope for research.Figure 7
Ternary logic representation (x0,y0,z0∈N). The point (x0,y0,z0±Δz or z0) represents the input condition, where all inputs corresponding to x-coordinate = 1, all inputs corresponding to y-coordinate = 0, and all inputs corresponding to z-coordinate = 2.Figure 8
Cartesian(x,y) coordinate system converted into polar (r,θ) system, where r=x, θ=2πy/(2n-1), and x,y∈[0,2n-1]. Filled circles indicate the “redundant points.”


### 3.9. Implications to Other Fields of Study

One can use the template to establish three algebraic equalities, as will be discussed in detail in this section. The method, in general, is useful for alternative representation and processing of data whenever there is representation of information (i.e., encoding or decoding) in the form of distinct or discrete states. The basic representation strategy can therefore be extended to represent and optimize operations on qubits [39] or to represent codon tables [40, 41] or design digital synthetic gene circuits [42]. Using the template used in the method proposed, we have derived the following three equalities in relation to (4n-3n). The method gives practical evidence of the equalities invented and presented next.Theorem 3.
(15)
3
n
+
∑
i
=
0
n
-
2
3
n
-
2
-
i
2
i
2
i
+
1
-
1
+
2
n
-
1
2
n
-
1
=
4
n
,
∀
n
∈
N
,
n
≥
2
,or, in other words,(16)3n+∑i=0n-23n-2-i2i+12+2n2=4n,∀n∈N,n≥2.Theorem 4.
(17)
3
n
+
∑
i
=
0
n
-
1
3
i
4
n
-
1
-
i
=
4
n
,
∀
n
∈
N
,
n
≥
2
.Theorem 5.
As a consequence,(18)∑i=0n-13i4n-1-i=∑i=0n-23n-2-i2i+12+2n2∀n∈N,n≥2∵Equations16and17.Let us first establish that the equalities being discussed are true, using induction.Proof.
For Theorem3, we observe that the equalities presented in (15) or (16) are true for n=2 and n=3.Forn=2,(19)L.H.S.=32+∑i=0030-i2i+1-12i+22-121=9+12-11+4-12=9+1+6=16=42=R.H.S.Forn=3,(20)L.H.S.=33+∑i=0131-i2i+1-12i+23-122=27+3121-120+3022-121+74=27+311+132+74=27+9+28=64=43=R.H.S.Now, say, for some n=m≥2,(21)3m+∑i=0m-23m-2-i2i+1-12i+2m-12m-1=22m=4m.Therefore,(22)3m+3m-221-120+3m-322-121+⋯+312m-2-12m-3+302m-1-12m-2+2m-12m-1=22m.For n=m+1≥2, therefore,(23)L.H.S.=3m+1+∑i=0m-13m-1-i2i+1-12i+2m+1-12m=3m+1+3m-121-120+3m-222-121+⋯+312m-1-12m-2+302m-12m-1+2m+1-12m=33m+3m-221-120+3m-122-121+⋯+302m-1-12m-2+2m-12m-1+2m+1-12m=2+1×22m-2m-12m-1+2m-12m-1+2m+1-12m∵Equation22=22m+1-22m+2m+22m-22m-1+2m-1+22m-1-2m-1+22m+1-2m=22m+2=4m+1=R.H.S.Therefore, if the statement is true for n=m, then the statement is true for n=m+1 (n,m∈N). Because the statement is true for n=2 and 3, it is true for every n∈N and n≥2.Proof.
For Theorem4 similarly, we observe that the equality presented in (17) is true for n=2:(24)L.H.S.=32+∑i=013i42-1-i=32+3041+3140=16=42=R.H.S.Now, say, for some n=m≥2,(25)3m+∑i=0m-13i4m-1-i=4m.For n=m+1≥2, therefore,(26)L.H.S.=3m+1+∑i=0m3i4m-i=3m+1+4×∑i=0m-13i4m-1-i+3m40=3m+1+4×4m-3m+3m40=3m+1+4m+1-3+1×3m+3m=4m+1=R.H.S.Because the statement is true for n=2, it is true for every n∈N and n≥2.In the context of the template for the method proposed, the two theorems can be proven graphically by simply counting the number of valid and redundant points, via different formulations. If3n+f(n)=4n for all n∈N, we know the following:(i)
4n=2n2n = (axisrange)2 = total number of points.(ii)
3n= total number of “valid” data-points, including the origin.(∵ Every input ai can manifest itself in the input combination represented by (X,Y), either in its original form (input combination represented by th X-coordinate) or as a negated input (input combination represented by the Y-coordinate) or may not manifest itself at all.)(iii)
f(n) = total number of redundant points.(∵ Total number of points = total number of “valid” points including the origin + total number of “redundant” points).Proof.
To establish equality presented in the Theorem3, we use the formulation of f(n) as presented in Figure 9. From Figure 9, it is evident that(27)∵∑l=1kl=kk+12∀k∈N,k=2j∀j∈N,0≤j<n,∴fn=∑i=0n-23n-2-i2i2i+1-1+2n-12n-1.The exponent of 3 translates to a multiplier that represents the frequency of occurrence of the constituent triangle of that specific size in the template.Figure 9
Total number of “redundant points”/the points in the darkened region, by counting the number of points in constituent triangles separately.Proof.
Alternately, Theorem4 can be proven using a recursive formula for f(n), as obtained from Figure 10.(28)∵fn=3fn-1+4n-1∴fn=33fn-2+4n-2+4n-1=32fn-2+3×4n-2+4n-1=3n-1f1+∑i=0n-23i4n-1-i=∑i=0n-13i4n-1-i∵f1=1.Figure 10
Total number of “redundant points”/the points in the darkened region, by deriving a recursive formula forf(n). Thus, f(n)=3×f(n-1)+(2n-1)2.This method can be used in classrooms to quickly hand-calculate an optimized form of the logic function using a ruler and a compass alone (Figure11).Figure 11
A compass and a ruler (marked with2n units) can be effectively used to quickly find the points that can be merged together to generate a more optimized logic representation using the logic laws proposed earlier (Section 3.5).


## 3.1. Coordinate System and Input Correspondence

Every integer coordinate “p” corresponds to an input combination ai1,ai2,…,aim such that(1)p=∑k=1m2ikp∈Z,ik∈N.One axis (say x-axis) represents a condition where the designated inputs are all True(T) (also called High(H) or logic level 1), while the other represents a case where those inputs are all False(F) (also called Low(L) or logic level 0). There is, therefore, a one-to-one correspondence between the set of all of combinations of the inputs and the set of points on the plane with integer coordinates. With such a representation system in place, every point on the plot with integer coordinates signifies a single product (in a SOP representation) or a single sum (in a POS representation). As an example, for a system with three inputs (a0,a1,anda2), the template of the plot that is restricted to the first quadrant (p≥0) will be as shown in Figure 1.Figure 1
Pandit-Plot (forn=3) with redundant data-points.Throughout the discussion henceforth, we only consider the template in the first quadrant. The templates in four quadrants are symmetric to each other, withx- and y-axes and the “x=y” and “x=-y” lines as the axes of symmetry. We observe that, in the scatter plot from Figure 1, certain data-points have been marked distinctively using the filled circles. These will be called “redundant” input combinations—for the reasons that will be explained in Section 3.3.


## 3.2. Representing an Input Combination

Representation of the combinational function “f” in graphical form may be done for “f” either in POS or in SOP form; the choice lies with the logic designer/user of the plot.To represent a function in SOP form, every constituent product term is separated into two products, one containing exclusively the direct inputs and the other only the negated inputs. The overall product is represented by a point(x,y), where, for example, the x-coordinate corresponds to the set of input combinations coming only from the direct inputs, while the y-coordinate corresponds to the set of input combinations from only the negated inputs, using (1). The absence of inputs implies that the corresponding coordinate is 0.As an example, let us consider the following sum of products:(2)f=a0a1+a0¬a1a2,represented by points (3,0) and (5,2), shown in Figure 2.(i)
For the first product “a0a1” to be True, both a0 and a1 need to be True. Therefore, the x-coordinate = 20+21=3, as per (1). Because there are no negated inputs in the first product, no ak needs to be False for f to be True. Therefore, the y-coordinate is 0. The product “a0a1” is, therefore, represented by point (3,0).(ii)
Similarly, for the product “a0¬a1a2” to be True, both a0 and a2 need to be True. Therefore, the x-coordinate = 20+22=5, as per (1). Also, a1 needs to be False for function f to be True. Therefore, the y-coordinate =21=2. The product “a0¬a1a2” is, therefore, represented by point (5,2).Figure 2
Pandit-Plot forf=a0a1+a0¬a1a2.Points(3,0) and (5,2) will be called “data-points” as they summarise the function by transforming it into numerical data, corresponding to the chosen coordinate system.Similarly, for a POS-based representation, we look forFalse (0/F/L) logic outputs to mark the points transforming every sum in the expression.Every Boolean function can therefore be represented by only two parameters alone in this way, namely, the coordinates of the representative points, irrespective of the number of inputs. This is a huge data compression in itself, where instead of storing the entire truth table, or even all of the combinations for which the output is either T or F (whichever count is less), we can simply represent a function with a few data-points. The system can further be optimized to remove extraneous information as will be explained in Sections3.3, 3.5, and 3.6.


## 3.3. Existence of Redundant Data-Points

It can easily be observed that there exist points on the plot with integer coordinates that correspond to a Boolean product or a Boolean sum that can never occur in a reduced SOP or a reduced POS expression, respectively.As an example, point(1,1) corresponds to the (a0¬a0) product in SOP which evaluates to 0/F, and the same point corresponds to the (a0+¬a0) sum in POS which evaluates to 1/T. These input combinations do not have any effect on the final expression evaluation, as the output corresponding to these input combinations is preknown and therefore redundant to be included as part of any Boolean expression (e.g., f+a0¬a0=f). We therefore discard such input cases and term these as “redundant points” in the discussions below, while the rest will be called “valid” points, except the origin, which falls into neither of the two categories, representing simply the trivial case of the output being independent of the inputs.


## 3.4. Generation of the Template

To translate any logic function to this plot, the first step is to build the necessary template or the canvas with all the input redundancies indicated (Figure1). Such a template may be generated by exploiting patterns for which the redundancies appear (Algorithm 1).Algorithm 1:Redundant set generation for Pandit-Plot.
(
1
)  procedure GENERATE1(n)   ⊳n= number of inputs
(
2
)   RedundantSet=ϕ
(
3
)   for  x←0,2n-1  do   ⊳ Represents direct inputs
(
4
)     for  y←0,2n-1  do  ⊳ Represents negated inputs
(
5
)       xbinary←(x)2
(
6
)       ybinary←(y)2
(
7
)       D←elementwise(xbinary∧ybinary)
(
8
)       if  any(D)=1  then
(
9
)         RedundantSet=RedundantSet∪(x,y)
(
10
)      end if
(
11
)      end for
(
12
)    end for
(
13
)  end procedureFor example, we note the following for a system withn inputs:(i)
Thex- and y-axes extend from 0 to 2n-1.(ii)
The points on the linex=y are redundant points.(iii)
All of the upper diagonal elements are redundant points.(iv)
Redundant points because of thea0 input’s logic level extend along both the x and y directions skipping every other point, that is, skipping the odd integer coordinates. The redundant points associated with a0 input are therefore of the form (2i+1,2j+1), where i,j are integers.(v)
Alternatively, the template may be generated using cellular automata rules on a brick-wall-like automata template as devised in Figure3 (in contrast to the typical cellular automata template as used in Conway’s game of life [34, 35]—where the borders of the individual cells coincide). This gives rise to the Sierpinski triangle [36, 37] pattern, as desired. The captions for the individual blocks indicate the (x,y) coordinates of the points that the blocks represent.Figure 3
Template generation from 2 different kinds of rules, signifying its relation to the Sierpinski triangle/fractals and the cellular automata.


## 3.5. Logic Laws

The logic optimization process is visual, intuitive, and simple—just as for Karnaugh-maps. It may alternatively be easily implemented using a computer program by understanding the strategies in place numerically. The basic idea of optimization is to get rid of excess of information by inspecting the scatter plot and bring the data-points as close to the axes as possible. There exist patterns that need to be utilised to effectively carry out this “reduction.” These patterns need to be formulated into a compilation of “logic laws.” A few examples of a logic law or an optimization strategy follow.Theorem 1 (2-integer-multiple hypotenuse rule).
If two of the data-points are vertices of an upright right angled isosceles triangle with its equal sides having length =2k  (k∈N) and if the third vertex is not to the right of any of those two data-points, then the two data-points could effectively be represented by that third vertex alone, so long as the third vertex is not a redundant point.Proof.
Let data-points beA(x1,y1) and B(x2,y2), such that x1>x2 and y1<y2 and (x1-x2)=(y2-y1)=2k,  k∈N, without loss of generalisation.
Because none of the three points,A(x1,y1), B(x2,y2), and C(x2,y1), is a redundant point and because x1+2k=x2, it follows that(3)x1=∑i=indx12i=2k+∑i=indx22i,where ind(p) is set of suffixes corresponding to inputs associated with coordinate “p.”
Similarly, it follows that(4)y2=∑i=indy22i=2k+∑i=indy12i.
Therefore, the pointB(x2,y2) represents both the direct and negated inputs corresponding to the point C(x1,y2), along with the input ¬ak. Similarly, the point A(x1,y1) represents both the direct and negated inputs corresponding to the point C(x1,y2), along with the input ak. The two points, A and B, therefore, effectively represent the inputs corresponding to the point C and, in addition, either the direct or the negated version of the input ak.
Therefore, in SOP form,(5)f≔fA+fB=akfC+¬akfC=fC,and, in POS form,(6)f≔fAfB=ak+fC¬ak+fC=fC,where fG≔  function associated with point G.
Thus, as per (5) and (6), this rule is simply a manifestation of the two well-known equalities (1)  P(q)+P(¬q)=P and (2)  (S+q)(S+¬q)=S for the template we present here—where P and S are, respectively, the product terms and the summation terms consisting of variables excluding q.As an illustration, if the plot in Figure4 represents a Boolean function f in SOP form with the points A and B as its “data-points,” then per the definitions earlier(7)f=a0¬a1a2+a0¬a1¬a2.This is because point A(5,2) translates to “a0¬a1a2,” while point B(1,6) represents “a0¬a1¬a2.”Figure 4
Diagonal optimization for SOP.Per the law proposed, pointsA and B are represented together by point C(1,2) alone, since the right angled triangle ABC is an isosceles triangle with its congruent sides having length 2k, k∈N(l(CA)=l(CB)=4).We find here that the hypothesis is true, since(8)f=a0¬a1a2+a0¬a1¬a2=a0¬a1a2+¬a2=a0¬a1⟹C1,2.If the scatter plot in Figure4 were to correspond to a POS representation, then the plot would have been represented as(9)f=a0+¬a1+a2a0+¬a1+¬a2.Effectively,(10)f=a0+¬a1+a0+¬a1a2+¬a2+a2¬a2=a0+¬a1⟹C1,2.In either case, pointsA(5,2) and B(1,6) are together represented by C(1,2) alone.Theorem 2 (symmetry about “x=y” line).
Two “valid” points symmetric about the “x=y” line in an SOP plot can be effectively represented by a newly defined logical operation represented by operator ⋆, where(11)ai⋆aj=∏ai·∏¬aj+∏¬ai·∏ajsuch  thatai∩aj=ϕ.Two “valid” points symmetric about the “x=y” line in a POS plot can be effectively represented by a newly defined logical operation represented by operator ⋆~, where(12)ai⋆~aj=∑ai+∑¬aj·∑¬ai+∑ajsuch  thatai∩aj=ϕ.Proof.
Two points symmetric about the “x=y” line will be of the forms A(x0,y0) and B(y0,x0). It follows that the set of direct inputs corresponding to the point A  (≔ai) is the same as the set of negated inputs that are represented by point B and vice versa (≔aj).
Because pointsA and B are not redundant points, it follows that ai∩aj=ϕ.
Therefore, for SOP,(13)∵fA=∏ai·∏¬aj,∴fB=∏¬ai·∏aj,such  thatai∩aj=ϕ,⇓f=fA+FB=∏ai·∏¬aj+∏¬ai·∏aj.
Similarly, for POS,(14)∵fA=∑ai+∑¬aj,∴fB=∑¬ai+∑aj,such  thatai∩aj=ϕ,⇓f=fA·FB=∑ai+∑¬aj·∑¬ai+∑aj.For a system with just two inputs, the “⋆” operator represents simply an “XOR” (⊕) operation, while the “⋆~” operator represents an “XNOR” (⊙) operation. The “NAND-only” implementation of “⋆/⋆~” operation is shown in Figure 5. This newly defined logic gate can then be optimized for given fan-in and fan-out values as necessary to be used as a building block in the subsequent logic design.Figure 5
“NAND-only” implementation of the newly defined logical operations “⋆ and ⋆~” that are essentially ⊕ (XOR) and ⊙ (XNOR) operations, respectively, for a two-input system.


## 3.6. Process of Optimization

While there is much scope for further research in this area for effective algorithm development in terms of logic optimization, including the ones targeted to novel topologies such as the ones involving IMPLY(¬A+B) gates alone, for example (instead of SOP/POS forms presented here, effectively implemented using “NAND alone” and “NOR alone” topologies, resp.), one of the most likely logic flows for such optimization is presented next.Steps involved in this example algorithm are as follows:(i)
“Generate” the template and plot the function.(ii)
“Expand” the expression to include every possible product in SOP form (every possible sum for a POS form).(iii)
“Reduce” the expression using logic laws.(iv)
“Repeat” the above two steps in iteration until no further reduction is possible, as illustrated in Figure6.Figure 6
Process of optimization; the steps in order are illustrated.
(a)
“Generate” step illustrated forf=(¬a1)+(a0)(a1)(a2)
(b)
“Expand” step illustrated for the product “(¬a1)”
(c)
‘‘Reduction” using the “2-integer-multiple hypotenuse rule”
(d)
The final optimized expression;f=(¬a1)+(a0)(a2)As an example, letf=(¬a1+a0a1a2), and let the representation form chosen be SOP-based as well. f ultimately gets reduced to f=¬a1+a0a2 as shown in Figure 6.(1)
Generate: plot the product terms (Figure6(a)).(2)
Expand: plot points relevant to each of the current data-points (Figure6(b)). Here, ¬a1 is expanded to include points wherever ¬a1=1⟹f=1.(3)
Reduce: reduce the expression using logic laws. If a new data-point, replacing one or some of the original data-points, is obtained through this process and if this data point cannot be further reduced, then it is noted and kept for the next iteration. (We note an example of such data-point with a label “NEW” in Figure6(c).)(4)
Repeat: repeat steps(2) and (3) until no new replacement data-point closer to the origin can be obtained (Figure 6(d)).Similar to the Karnaugh-maps, the “do not care” input combinations could be exploited for logic reduction [3, 38].


## 3.7. As a Data Structure

Because the individual Boolean terms are represented by only two coordinates (irrespective of the number of inputs), any combinational logic may be represented by two parameters alone. This can be viewed as a conversion of a graphical scheme to an equivalent nongraphical numerical scheme, to be handled by computing systems efficiently. The two coordinates may be stored in the memory as a single unit.Because one can represent any logic expression through a set of coordinates alone, we now investigate the number of bits required to store each of the numbered coordinates. While a proposed template forn inputs consists of 4n points (including the origin), the number of valid coordinates is only 3n-1. This is because a variable can manifest itself in an input combination in its original form (ak) or as a negated version (¬ak) or it could simply be absent. Thus, there are three possibilities for every input ak. The number of valid points is, therefore, 3n-1 (excluding the origin indicative of a trivial case where the output is independent of all of the inputs under consideration). Both the total number of points (τ=4n-1) in a template and the number of valid points (υ=3n-1) grow exponentially with n. The ratio of the number of bits thus required (with and without considering the redundant points) = ceil(log2(3n-1))/ceil(log2(4n-1)) which varies between 0.75 and 0.85 and eventually converges to 0.8 for large n. As an example, for n=3, υ=26, and τ=63, while, for n=6, υ=728, and τ=4095. Memory savings, thus, grow with n if we effectively take into account the redundancies in the template.However, in comparison to K-maps (=2n cells for an n-input system), our proposed method requires a much higher number of points (=3n-1, if we consider only the valid input combinations, excluding the origin). This is because the K-maps do not take into account all of the input combinations, but only the ones where each of the inputs manifests itself by its presence in its original or in its negated form (thus, 2n possibilities). In the proposed method, we explicitly take into account also the reduced input combinations where some of the inputs are absent.


## 3.8. Possible Extensions and Further Research Scope

(i)
Beyond SOP/POS paradigms: more patterns and the resulting optimization strategies need to be investigated in different logic gate methodologies, for example, SOP (“AND-OR”, which is “NAND-only”), POS (“OR-AND”, which is “NOR-only”), and “IMPLY-only” realisations.
(ii)
Multilevel logic: the concept could be extended to three dimensions to represent a ternary logic system, where both inputs and outputs can have three possible logic levels(0,1,2). The resulting representation is, thus, in the form of a “logic lattice” instead of the two-dimensional grid presented here, where the third dimension would serve a dual purpose. First, it represents a condition where all the inputs are logical level “2” (just as Z and Y represented states “1” and “0,” resp.). Secondly, the z-axis may also represent an output logic level within such a “logic slice.” As an example, output level-1 may correspond to a point with integer (X,Y,Z) coordinates, level-0 may correspond to a point just beneath this point, and level-2 just above (Figure 7).
(iii)
Alternate coordinate systems: every data-point symbolises a huge degree of information, but with only two or three parameters (coordinates). Because this information need not necessarily come about using a Cartesian coordinate system alone, one can choose to alternatively employ some other coordinate system and look for patterns and laws for optimization within such schemes. For example, a 2D polar system may be used, where the(x,y) to (r,θ) transformation is governed by the equations r=x, θ=2πy/(2n-1), and x,y∈[0,2n-1]. Note that θ remains in the range [0,2π] irrespective of the number of inputs (Figure 8). The logic laws for such alternate coordinate systems—where every coordinate of interest ψ follows the equation ψ=f(∑k=1m2ik),  ik∈N—can be devised by recognising the inherent patterns, which remains an open problem with further scope for research.Figure 7
Ternary logic representation (x0,y0,z0∈N). The point (x0,y0,z0±Δz or z0) represents the input condition, where all inputs corresponding to x-coordinate = 1, all inputs corresponding to y-coordinate = 0, and all inputs corresponding to z-coordinate = 2.Figure 8
Cartesian(x,y) coordinate system converted into polar (r,θ) system, where r=x, θ=2πy/(2n-1), and x,y∈[0,2n-1]. Filled circles indicate the “redundant points.”


## 3.9. Implications to Other Fields of Study

One can use the template to establish three algebraic equalities, as will be discussed in detail in this section. The method, in general, is useful for alternative representation and processing of data whenever there is representation of information (i.e., encoding or decoding) in the form of distinct or discrete states. The basic representation strategy can therefore be extended to represent and optimize operations on qubits [39] or to represent codon tables [40, 41] or design digital synthetic gene circuits [42]. Using the template used in the method proposed, we have derived the following three equalities in relation to (4n-3n). The method gives practical evidence of the equalities invented and presented next.Theorem 3.
(15)
3
n
+
∑
i
=
0
n
-
2
3
n
-
2
-
i
2
i
2
i
+
1
-
1
+
2
n
-
1
2
n
-
1
=
4
n
,
∀
n
∈
N
,
n
≥
2
,or, in other words,(16)3n+∑i=0n-23n-2-i2i+12+2n2=4n,∀n∈N,n≥2.Theorem 4.
(17)
3
n
+
∑
i
=
0
n
-
1
3
i
4
n
-
1
-
i
=
4
n
,
∀
n
∈
N
,
n
≥
2
.Theorem 5.
As a consequence,(18)∑i=0n-13i4n-1-i=∑i=0n-23n-2-i2i+12+2n2∀n∈N,n≥2∵Equations16and17.Let us first establish that the equalities being discussed are true, using induction.Proof.
For Theorem3, we observe that the equalities presented in (15) or (16) are true for n=2 and n=3.Forn=2,(19)L.H.S.=32+∑i=0030-i2i+1-12i+22-121=9+12-11+4-12=9+1+6=16=42=R.H.S.Forn=3,(20)L.H.S.=33+∑i=0131-i2i+1-12i+23-122=27+3121-120+3022-121+74=27+311+132+74=27+9+28=64=43=R.H.S.Now, say, for some n=m≥2,(21)3m+∑i=0m-23m-2-i2i+1-12i+2m-12m-1=22m=4m.Therefore,(22)3m+3m-221-120+3m-322-121+⋯+312m-2-12m-3+302m-1-12m-2+2m-12m-1=22m.For n=m+1≥2, therefore,(23)L.H.S.=3m+1+∑i=0m-13m-1-i2i+1-12i+2m+1-12m=3m+1+3m-121-120+3m-222-121+⋯+312m-1-12m-2+302m-12m-1+2m+1-12m=33m+3m-221-120+3m-122-121+⋯+302m-1-12m-2+2m-12m-1+2m+1-12m=2+1×22m-2m-12m-1+2m-12m-1+2m+1-12m∵Equation22=22m+1-22m+2m+22m-22m-1+2m-1+22m-1-2m-1+22m+1-2m=22m+2=4m+1=R.H.S.Therefore, if the statement is true for n=m, then the statement is true for n=m+1 (n,m∈N). Because the statement is true for n=2 and 3, it is true for every n∈N and n≥2.Proof.
For Theorem4 similarly, we observe that the equality presented in (17) is true for n=2:(24)L.H.S.=32+∑i=013i42-1-i=32+3041+3140=16=42=R.H.S.Now, say, for some n=m≥2,(25)3m+∑i=0m-13i4m-1-i=4m.For n=m+1≥2, therefore,(26)L.H.S.=3m+1+∑i=0m3i4m-i=3m+1+4×∑i=0m-13i4m-1-i+3m40=3m+1+4×4m-3m+3m40=3m+1+4m+1-3+1×3m+3m=4m+1=R.H.S.Because the statement is true for n=2, it is true for every n∈N and n≥2.In the context of the template for the method proposed, the two theorems can be proven graphically by simply counting the number of valid and redundant points, via different formulations. If3n+f(n)=4n for all n∈N, we know the following:(i)
4n=2n2n = (axisrange)2 = total number of points.(ii)
3n= total number of “valid” data-points, including the origin.(∵ Every input ai can manifest itself in the input combination represented by (X,Y), either in its original form (input combination represented by th X-coordinate) or as a negated input (input combination represented by the Y-coordinate) or may not manifest itself at all.)(iii)
f(n) = total number of redundant points.(∵ Total number of points = total number of “valid” points including the origin + total number of “redundant” points).Proof.
To establish equality presented in the Theorem3, we use the formulation of f(n) as presented in Figure 9. From Figure 9, it is evident that(27)∵∑l=1kl=kk+12∀k∈N,k=2j∀j∈N,0≤j<n,∴fn=∑i=0n-23n-2-i2i2i+1-1+2n-12n-1.The exponent of 3 translates to a multiplier that represents the frequency of occurrence of the constituent triangle of that specific size in the template.Figure 9
Total number of “redundant points”/the points in the darkened region, by counting the number of points in constituent triangles separately.Proof.
Alternately, Theorem4 can be proven using a recursive formula for f(n), as obtained from Figure 10.(28)∵fn=3fn-1+4n-1∴fn=33fn-2+4n-2+4n-1=32fn-2+3×4n-2+4n-1=3n-1f1+∑i=0n-23i4n-1-i=∑i=0n-13i4n-1-i∵f1=1.Figure 10
Total number of “redundant points”/the points in the darkened region, by deriving a recursive formula forf(n). Thus, f(n)=3×f(n-1)+(2n-1)2.This method can be used in classrooms to quickly hand-calculate an optimized form of the logic function using a ruler and a compass alone (Figure11).Figure 11
A compass and a ruler (marked with2n units) can be effectively used to quickly find the points that can be merged together to generate a more optimized logic representation using the logic laws proposed earlier (Section 3.5).


## 4. Conclusion

A novel graphical technique for digital logic representation and optimization has been proposed, which makes optimization algorithm much more instinctive and easy. Multiple equations can be optimized simultaneously using the template presented. One can, theoretically, therefore optimize simultaneously multiple combinational logic circuits with any number of inputs or outputs. We propose a data structure transformation that can compress a truth table into a few parameters. The approach and the fundamentals involved are likely to generate many novel solutions applicable to other disciplines. A new paradigm is being proposed, which opens up new avenues for research in terms of new methodologies and pattern identification towards better logic reduction tailored to different implementation topologies such as SOP (“AND-OR”/“NAND-only”), POS (“OR-AND”/“NOR-only”), and “IMPLY-only” realisations or the newer methodologies such as “reconfigurable asynchronous logic automata (RALA)” [43] and the search for most suited template for each in terms of the coordinate system of choice and the template generation rules.Our proposed technique currently establishes a one-to-one mapping between all of the possible variable combinations and the corresponding output states—representing the absence and presence of every variable (in its original and the negated form) for each of the variable combinations. One possible future research direction is to investigate the relationship between the proposed technique herein and other representation techniques—such as QMDDs which, too, rely on quadrants and one-to-one mappings and which rather extend way beyond the proposed technique to represent transformation matrices featuring complex entries useful for logic involving qubits. Further research may also be targeted towards multilevel discrete systems beyond Boolean algebra and reversible [44, 45] and hazard-free logic synthesis [9].



---

*Source: 9696342-2017-12-31.xml*