Numerical Method of Multiplexer Implementation

Introduction Introduction

Introduction Numerical Method Theory

Examples Examples

Introduction Introduction

 When functions of many variables are being considered it is possible to cascade circuits using multiplexers of any desired size. Karnaugh map and algebraic methods then become unwieldy and a numerical approach is adopted. Different methods have been proposed to effect implementation; we shall employ a technique proposed by Whitehead.

In order to understand the numerical method, you should be familiar with the Forms and Definitions of Boolean Expressions and the don't care condition where for certain combinations of the variables one does not care what the value of the function becomes (either 0 or 1).

Theory Numerical Method Theory

 To simplify the theory the function is defined in binary, with a true form of a variable denoted by a 1, and conversely, a false form denoted by a 0. The system can expect to deal with variables being missing, or a don't care condition, which is denoted by a dash (-). This can be expressed clearly by the following functions of three variables, i.e. f(A,B,C).
Figure 1
Essentially the method is one of factoring using the relationship in which the variable allowing the maximum number of terms to be so factored is sought. That variable(s) is then used as the multiplexer data input variable.

Consider Figure 2
Listing the two minterms we have Figure 3
Now consider the following function.Figure 4
Note that these variables cannot be combined.
Figure 5
This is because the FIRST RULE of the numerical method for two terms is that they must differ in only one digit position.

The number of variables that are true form, i.e. the number of 1's in a term, is significant and is referred to as its index.

For example: f(A, B, C, D)

0000...................Index 0
0010, 1000.............Index 1
1010, 0011, 1001.......Index 2
1110, 1011.............Index 3
1111...................Index 4

For each minterm in the function the index is found. The minterms are arranged in order of index starting with the lowest index entries. Those term-pairs with only a difference in the least weighted variable are listed. The process is repeated with a new list for those term-pairs with a difference of the next weighted variable. This continues with a further list for term-pairs, and so on.

The variable with the greatest list of pairs becomes the data input variable.

To obtain the data input values, all the minterms possible are listed in a table with the data input variable set as true and as false. Each minterm pair with its data variable value has a difference equal to the binary weight of the selected data variable. The minterms appearing in the original function are then noted.

If both terms of a pair correspond to those in the original function, the data input value is set to 1.
If both terms of a pair do not correspond to those in the original function, the data input value is set to 0.
For pairs with only one term corresponding to those in the original function, the data input value is set to the data variable value.

The approach resembles the tabular method of minimisation but differs in a number of respects. Instead of attempting to reduce the product terms by checking for a difference in the least weighted variable and removing this variable, and so on for the next weighted variable, each variable term is checked and these differences noted. The variable yielding the greatest number of isolated differences is the one that will provide the most efficient solution when used as the multiplexer data input variable.

Examples Examples

Previous Next Previous Index Map
To submit your questions and queries please click here: Queries
Composed by David Belton - April 98