Monday, 5 November 2012

Programming &Math: Wherever you go, “number theory” follows....

I was in to a perl script and some part of my code required this logic:
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???