I was in to a perl script
and some part of my code required this logic:
A chip designer would not worry about assigning priorities. He depends on truth table and k-map to arrive at appropriate Boolean expression. What are these truth table and k-map doing here???
For a particular mobile
number, if data (customer name, address etc) is available in MySQL table and if
image (scanned application form) is also available in the server, then display data
and image. If data is available and image is not available, then display data.
If data is not available and image is available, then display nothing. Here the
point is more precedence is given for ‘data’.
Algorithm:
If(data is available)
{
if(image is available)
Display ‘data’ and ‘image’
Else
Display ‘data’
}
Else
{
// no action
}
This is the simple
algorithm for the program.
I want to relate this to a
mathematical model. Let us assume a simulator which assigns values to two
variables X and Y and adds them up. This assignment depends on the availability
of ‘data’ and ‘image’ respectively. The default value of X and Y is ‘0’.
If ‘data’ is available,
then X can be assigned ‘2’ and if ‘image’ is available, then Y can be assigned ‘1’.
Here as I have more precedence for ‘data’, I design the simulator to assign a higher
value (ie ‘2’ as against ‘1’ which is assigned to Y if ‘image’ is available).
Now the simulator adds up X
and Y and depending on the Sum, it decides which is to be displayed. If Sum is ‘3’,
then both ‘data’ and ‘image’ are displayed. If the Sum is ‘2’, then only ‘data’
is displayed. If the Sum is ‘1’ or ‘0’, then nothing is displayed.
Now to design a circuit
for this logic, I need to talk in ‘binary’ language (0’s and 1’s):
Default value of X and Y is
binary ‘00’. If ‘data’ is available, then X can be assigned ‘10’ and if ‘image’
is available, then Y can be assigned ‘01’. If Sum is ‘11’, then both ‘data’ and
‘image’ are displayed. If the Sum is ‘10’, then only ‘data’ is displayed. If the
Sum is ‘01’ or ‘00’, then nothing is displayed. We can implement the whole
thing with some logic gates (like a ‘Full Adder’ or whatever it may be). I don’t
want to go more in to the circuit designing stuff.
Coming back to the
mathematical model, let us extend the logic to three variables with three
different weightages. If we assign weightages 1,2,3 to X,Y,Z then the possible
outcomes are:
X
|
Y
|
Z
|
Sum
|
0
|
0
|
0
|
0
|
0
|
2
|
0
|
2
|
0
|
0
|
3
|
3
|
0
|
2
|
3
|
5
|
1
|
0
|
0
|
1
|
1
|
2
|
0
|
3
|
1
|
0
|
3
|
4
|
1
|
2
|
3
|
6
|
But there is an ambiguity here.
Sum is same for two different scenarios (0,0,3) and (1,2,0). So we can’t assume
1,2,3 for X,Y,Z. Then what else...
Let us try with 1,2,4...
X
|
Y
|
Z
|
Sum
|
0
|
0
|
0
|
0
|
0
|
2
|
0
|
2
|
0
|
0
|
4
|
4
|
0
|
2
|
4
|
6
|
1
|
0
|
0
|
1
|
1
|
2
|
0
|
3
|
1
|
0
|
4
|
5
|
1
|
2
|
4
|
7
|
Yes, here it works.
Now if we have four variables,
then what is the sequence of weightages a circuit designer considers?
We can easily guess...
“1,2,4,8” – this gives all
possible 16 combinations (0 to 15).
I say it again.....
Wherever you go, “number
theory” follows.....
My cousin Mr.Aditya, a chip designer commented like this:
"When implemented in
hardware though we do it somewhat differently. When we want to implement a
priority encoder like this, we usually come up with a truth table first and
minimize the terms using a karnaugh map."
A chip designer would not worry about assigning priorities. He depends on truth table and k-map to arrive at appropriate Boolean expression. What are these truth table and k-map doing here???
Truth table maps the inputs into either 0-to-3 or 0-to-7 or 0-to-15 etc... possible values and assigns one out put (0 or 1) to each input. K-map
arranges the output values (0's or 1's) of truth table into cells (each cell corresponds to one possible input combination) arranged in a
mesh-form of size 2X2 or 2X4 or 4X4 etc.. So, every time, the total number of
cells in the k-map is either 4 or 8 or 16 etc...
My
insistence on importance of "number theory" originates exactly
from here. If I take 1,2,3 as inputs, I can have the following possible sums:
1, 2, 3, 4(1+3), 5(2+3) and 6(1+2+3). For three inputs we have six outputs.
But
if we consider 1,2,4 as inputs, we can have the following possible sums:
1, 2, 3(1+2), 4, 5(1+4), 6(2+4) and 7(1+2+4). For three inputs here we have seven outputs. And this advantage is more clear as the number of inputs increases. If I consider 1,2,4,8 as inputs, I can have all possible values from 1 to 15. Using binary logic in truth-table & k-map concept naturally takes this advantage as 1,2,4,8,16,... are the respective place-values of the binary-system.
Relating
this to our discussion of assigning priorities... Is not the k-map internally
assigning 1,2,4 priorities to X,Y and Z terms respectively???
No comments:
Post a Comment