Homework 4

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Bruce Yen

ECE572: Adv. Logic Synth.

Fall 2003

Professor Perkowski

Symmetric Functions

Due: 10/29/2003

 

Part 1: Four Variable Symmetric Functions

 

Figure 1a.                                 Figure 1b.                                  Figure 1c.

 

  

 

Figure1a is a symmetric function with polarity (1111), and coefficients S1,2,4 = 1. The coefficients are numbered from S0 to S4 from outermost to innermost. Figure 1b is a symmetric function with polarity 0100, and coefficients S1,2,4 = 1. In figure 1c, we can better see the geometrical symmetry when the last column cd = 10 is rotated to the left, next to cd = 00. The functions are realized as follows:

 

F1111 = a’d Å ac’ Å abc Å cd’     OR     F1111 = ac’ + a’c + a’d + bd

F0100 = a’b’ Å c’d’ Å a’bc Å ab

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Part 2: Lattice Diagrams

 

Figure 2a.                                                      Figure 2b.

 

 

Figure 2a is the lattice diagram for F1111, with Shannon expansion. The nodes actually never had to be joined. By the third row, the variables had already eliminated themselves sufficiently to result in just 3 nodes, one of which is 1. Figure 2b. is the positive Davio expansion of the same function. At the third level, d’ was naturally joined as a result of the original choice of “a” as the first variable to be expanded by. Notice that there are the same number of levels as the Shannon expansion, since the positive Davio expansion needs a new level for the “b” selection. However, the positive Davio expansion requires less gates.

 

Figure 2c.                                                     Figure 2d.

 

 

As a comparison, Figure 2d is the lattice diagram for F1111, with Shannon expansion, but done using an AND/OR topology rather than XOR. Again, the nodes actually never had to be joined. By the third row, the variables had already eliminated themselves sufficiently to result in just 3 nodes. This is because d + c + bd expanded into d + c for both cases of b = 0 and b = 1. However, for the sake of joining nodes, Figure 2d shows what would happen if we kept the b = 0 and b = 1 decision separate, and joined the central node. We can see that it actually ends up being less efficient, with an extra row of expansions where we expand by “b” again.

 

Figure 2e.                                                        Figure 2f.

  

 

In figure 2e, we have the Shannon lattice structure of F0100. We can see that one of the nodes was joined at the fourth level, bd’ Å b’d’, and it reduced to d’. Figure 2i is the positive Davio expansion of the function, and we can see that it requires only 8 gates instead of 9, over the Shannon lattice (without nodes combined. If nodes are combined, there would be 7 and 8 gates required, respectively). Notably, again, these lattices either naturally combined like nodes, or reduced sufficiently such that they did not require node joining (one of the nodes reduced to 1 or 0).

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Part 3: BDD Generation, Comparisons to the K-Map

Figure 3a.                                                 Figure 3b.

 

 

Figure 3a is the reduced BDD for the Shannon expansion of the function F1111 and Figure 3b is the reduced BDD for the positive Davio expansion for the same function. We can implement the first of these with two input multiplexers as in Figure 3c. Figure 3d implements the second of these with a positive Davio specific gate, comprised of 1 AND and 1 XOR. Since the font is so small, for convenience: the order of variable names are: A, C, B, D, 0, 1, top to bottom for figure 3d. Constructing the implicants of the positive Davio expansion, we find that the selected implicants are all centered about the polarity 1111. That is, each implicant adds a different permutation of 1’s (if we use an even/odd counting technique to resolve the final XOR expression) that all overlap at the polarity. It is akin to the summing of a series expansion.

 

Figure 3c.                                      Figure 3d.

 

 

 

Figure 3e.                                                   Figure 3f.

 

Figure 3e is the BDD for the Shannon expansion of the function F 0100 and Figure 3f is the BDD for the positive Davio expansion for the same function. Again, in the Davio expansion, we see a construction of the K-map with a center of 1111, which can be attributed to the fact that the Davio expansion is positive and can only use a, b, c, d, and no negations of the variables. The logical BDDs can be realized directly using the same toplogies as for the symmetric function of polarity 1111. Again, because of the size of the font, the order of variables in Figure 3h is, from top to bottom: A, D, C, B, 0, 1.

 

Figure3g.                                                            Figure 3h.

 

 

 

 

 

 

Part 4: Ashenhurst Decomposition

 

Choosing the original function with symmetry polarity 1111, I tried different combinations of abcd to find a Karnaugh map that would give a visual solution to an Ashenhurst decomposition. The Karnaugh map with “ab” against “cd” had one pair of meshable columns and two independent columns. However, rearrangement of variables in a Karnaugh map of “ac” against “bd” gave two pairs of meshable columns. This can be seen with the color codes in Figures 4a and 4b.

 

Figure 4a.                      Figure 4b.                   Figure 4c.

 

From Figure 4b, I coded the grey as A = 0 and red as B = 1. This effectively gave me an intermediary function X as a function of “bd,” as shown in Figure 4c. As we can see from this figure, X = b Å d. After finding this intermediary function X, I simply needed to use a Karnaugh map relating this intermediary function with “a” and “c.” This relationship is shown in figure 4d. I chose the groupings as shown and the direct expression for function F was

 

            F = a’c + ac’ + ax’ + a’x

 

which can be simplified to:

 

            F = (a Å c) + (a Å x).

 

The physical realization is shown in figure 4e.

 

Figure 4d.                Figure 4e.