Tamiya 1/16 Scale Leopard Chassis....

I have a couple of updates relating to robotics to share this week. Below is a picture of a Tamiya 1/16 scale model tank that was given to me as a gift. It is actually one tank with the upper plastic tank looking parts on the right and the metal mechanical motorized chassis on the left. I want to thank my friend DV here for giving it to me - Thanks!

Looking at it in detail it is clear that this is a quality kit but it has seen better days. The metal treads are not rolling smoothly and the tread tension adjustment is maxed out and the treads are still loose (maybe they have a few too many links!) There is also some missing screws and other things that at first glance I thought were missing parts but now I believe they were removed in an attempt to make this thing go.

 

The drive mechanism for this is pretty sophisticated considering that it is a model. There is one drive motor that is running all metal gears that is connected to two mechanical clutches (black cylinders in the picture). The clutches are activated by a servo (missing in this tank) similar to the servos that I used in My Robot.

 

The really neat thing about this kit and what really caught my eye initially is the quality of the gearbox and the fact that most of the entire chassis is metal.  The suspension for the treads actually works with each idler wheel in the tread being supported with a torsion spring. Additionally the plastic top seems to have amazing detail and a 'real' look to it. I'm not a tank expert but it appears that everything looks right...

 

These days I'm not spending a lot of time in the freezing cold garage where I can work on this but as soon as the weather warms up a bit (or at least the garage) I'm going to carefully photograph the entire chassis, gears etc... strip it down, clean it, paint and re-assemble it all to at least the point that it's at now. The action of the clutches seems to be really stiff and it needs a lot of work but I think that this is the beginning of a really cool project. I'm not sure if I'll rebuild it as a tank but I will figure it out and get it running.

 

On a similar and related note my son built up a tank as well as you can see in the second picture. He got his designed and 'running' in a matter of several minutes! Similar scale but it has a much more flexible architecture!!

As my son works on his vehicle I'll work on mine and post the progress of each as they progressively progress onward....

Linear Power Supply (Hot Glue and High Voltage)

I'm sure that you have heard the old saying "you can never have enough power supplies".... I have found this to be true on many occasions. It seems that when trying to build something new and exciting I am lacking the required voltages and currents to make it go. So whenever I get the chance to build a power supply I take it (or if I have nothing better to do).

 

This one started with a power supply that had been modified by someone, then thrown in the garbage. It looked like it had a bunch of good parts, including a Variac, so I took it home. The first thing that I noticed  after getting it home was it had stickers all over the front of it in what appeared to be Korean. These were above and below a bunch of holes that looked like they were for switches and lights etc... Most of the holes were empty or had obviously incorrect switches and lights stuck in them. After opening it up it was clear that the insides had been cut, drilled, replaced, burned up, replaced again, drilled, cut, glued and burned up (again). I think it started out as a power supply and was then 'improved' in such a way that the 'improvements' came bursting out.

 

I decided to take all the major components out and clean and check each one. For the most part it all seemed to work. I tried to figure out what the previous owner was thinking when they added / changed everything but it was such a mess inside that I figured it wasn't worth the time. There were all kinds of connections made by twisting wires together and hot-gluing them very near 'weld spots' on the steel enclosure - those fun looking weld spots that happen when you get a lot of current flowing from a wire into the metal chassis and the paint burns off and blobs of molten copper go splattering all over.

 

Anyway after cleaning it all up I cut some new holes and mounted some new switches and lights. The original filter section seemed to be OK so I left that alone. It needed a new cooling fan, capacitors and some other things. The Variac was not an original piece in this so I changed how it was mounted and slipped some 0.09"  thick PTFE sheet between the coil windings and the metal chassis. Oh yeah  - I also added a ground so the chassis would actually be grounded and not 'live' as it was when I got it.

 

 

There is a lot of junk crammed inside at this point but it seems safe and doesn't look like it's going to catch fire or electrocute me. I don't think I would run it unsupervised for any length of time but these kinds of unknowns and uneasy feelings just make life spicy and interesting, exactly what garage experimentation is all about.

 

 

Above is a photo of the schematic of what I ended up hooking up. I decided to tap into the AC output from the Variac so I could get some variable AC voltage if I need it someday. The DC output is just the rectified and filtered AC. I can get 0 to 200 volts DC out of it and about 0 to 140 volts AC with no load with 120 volts AC input from the wall. Nothing special but may be useful for something one of these days. The DC seems to be filtered really well as under load with my oscilloscope there is no ripple. I haven't bothered figuring out what the power factor is to get a better idea of what the real output will be but I don't care right now... it works! The easiest way to figure out it's capabilities is crank it up until it glows red inside then back off a quarter turn on the Variac.

More Excel Fun (nothin better on a rainy day)

Continuing in the pursuit of things I'm not very good at or understand very well, I decided to mess around a bit more with Excel and the Diffusion "thing" that I have been thinking and writing about. I got a bit bored with the 'Sawtooth' idea and decided to play with the Pseudo-Hadamard Transform. Specifically I decided to see how it works on 32 bit words or 4 bytes at a time. It's an easy thing to do with 16 bits or two bytes but 4 bytes isn't as straight forward in Excel. So to do this I wrote another Visual Basic script in Excel that will take the values in 4 cells (each a byte) then combine them into two 16 bit values. It then does the math Mod 2^16 and parses the values out into 4 new cells (each a byte). The code accepts 5 values from Excel, the first 4 are the byte values to do the calculation with and the 5th value is to determine which of the 4 output bytes to return. I posted the code at the end of this post.

What I noticed once I had done this is how crappy it seems to be at mixing or diffusing the  changes in the values when you are looking at one byte at a time. I shouldn't say crappy because I probably wrote the code wrong and I'm not doing the math correctly!! Ha Ha! Anyway what I got was a function that seems to work when I check the math by hand. Below is a few examples of what happens when you change various Input Values and how the Output Values change.

INPUT		1	0	0	0
OUTPUT		2	0	1	0

INPUT		0	2	0	0
OUTPUT		0	4	0	2

INPUT		0	0	3	0
OUTPUT		3	0	3	0

INPUT		0	0	0	4
OUTPUT		0	4	0	4

The interesting thing is that if you change one value in the input, two values change in the outputs. You can change the values of the inputs to whatever you want but almost always each input changes just the values in the locations above. For example looking at the first chart above with the value of 1 in the left input row it is changing the values in the locations noted by the 2 and the 1 in the output row below it. In the second chart the value of 2 in the input row is changing the values in the locations marked with the 4 and the 2. In fact I created a spreadsheet that runs through all the input values and for every input value the changes follow the above charts with the exception below:

INPUT		0	128	0	0
OUTPUT		1	0	0	128

INPUT		0	129	0	0
OUTPUT		1	2	0	129

So looking at the two above charts the value of 128 in the second input byte from the left is changing different output values than it did in the first set of charts. When the second input value from the left goes to 129 and above it is back to changing the second and fourth output values from the left. (but it leaves the first output byte larger by 1 from then on). Wow!! This is exciting!

I suppose another way to look at what is going on here is this:

INPUT		A	B	C	D
OUTPUT		(A|C)	(D|B)	(A|C)	(D|B)

So the input in each location noted with a letter is having an effect on the output that has the same letter. Assuming you ignore the oddball change when the second input from the left is 128 and it changes the first output from the left by 1.

One problem in my opinion with doing this is only one input value is changing two of the output values. Ideally I would like to have all the output values change if one of the input values has changed. Thinking about this I decided to make two transforms in parallel with each acting on the input bytes rotated by location to the left one place. Here is a similar chart showing that:

INPUT		B	C	D	A
OUTPUT		(B|D)	(C|A)	(B|D)	(A|C)

Notice that the locations of A, B, C and D are all shifted. So imagine you have 4 input values A, B, C and D. They are 'loaded' into the chart locations above and simultaneously calculated causing the outputs to change in each location. Then the outputs from both transforms are Exclusive Or'd together to get the 4 output byte values:

OUTPUT	(A|C)	(D|B)	(A|C)	(D|B)
OUTPUT	(B|D)	(C|A)	(B|D)	(A|C)
XOR	(ABCD)	(ABCD)	(ABCD)	(ABCD)

Or something like that anyway. The reason I bring it up is because I did just that in a spreadsheet ;) So anyway it's not very interesting if you just take the exact same values for A, B, C, and D and put them into the same transforms and exclusive or the outputs together. What I decided to do is take the values A,B,C and D and put them into the first transform then take those values and swap the upper and lower bits (Nibble Swap). That way the the inputs to the two transforms are different but related to each other. If A changes then it's "Nibble Swapped" value will change too. An example is the value 12 decimal which  = 1100 in Binary. If you look at 12 in 8 bit binary (with the nibbles separated for clarity) it's 0000 1100. If you swap the nibbles it becomes 1100 0000 which = 192 decimal.

One obvious thing to mention is some values don't change when you swap the nibbles.

Obviously 0 = 0000 0000 and 255 = 1111 1111 don't change when you swap the nibbles. Neither does 17 = 0001 0001 or 85 = 0101 0101. In fact anything that is a multiple of 17 doesn't change when you swap the nibbles so I decided to fix that by performing a logical NOT (inversion) on all the values that don't change when you swap them. So 0 becomes 255, 255 becomes 0, 17 becomes 238 and 85 becomes 170. Wow!! This is exciting!! I posted the code for doing this special Nibble Swap at the end of this post.

Anyway that is what I have been up to this rainy weekend. I have not done a whole lot of testing on the above idea to see if it really does mix up the data and 'diffuse' it over the entire 4 byte output. I did write some simple scripts to run through a few thousand input values and checked for output changes and it seems to work pretty good.

On interesting thing to note about this is that the two transforms could actually be done in parallel if this were to be implemented in some kind of real time encryption system. I suppose that one method would be to take the 4 input values and substitute them with two different substitution (look-up) tables. This would be a lot better than using the Nibble Swap to get a different value for the second transform. So the A value could be substituted in two tables for 2 new values with each new value going into a transform - one being position rotated to the left. That way the values are different but would change if the A byte value changed. The subject of cryptographic substitution tables is best left for another day.

Visual Basic Code for Pseudo-Hadamard Transform (32 bit word)

Function PHT(A As Long, B As Long, C As Long, D As Long, Place As Long)
' Pseudo Hadamard Transform 16 bit words
' Shift A <<8 and C <<8 then Or C and D with them
' create Temp to hold left value
' check Place to figure out which byte is req'd as output
' December 2009 http://ottobelden.blogspot.com
Dim Left As Long
Dim Temp As Long
Dim Right As Long
Left = (A * 256) Or B
Right = (C * 256) Or D
Temp = Left
Left = (2 * Left) + Right Mod 65536
Right = Temp + Right Mod 65536
If Place = 1 Then
    Left = Int(Left And 65280) / 256
    PHT = Left
    End If
If Place = 2 Then
    Left = Left And 255
    PHT = Left
    End If
If Place = 3 Then
    Right = Int(Right And 65280) / 256
    PHT = Right
    End If
If Place = 4 Then
    Right = Right And 255
    PHT = Right
    End If
End Function

Nibble Swap with logical Not

Function SHIFTD(Value As Byte)
' Swap upper nibble for lower
' if swapping doesn't change value
' then invert (NOT) value
' December 2009 http://ottobelden.blogspot.com
Dim LN As Byte
Dim RN As Byte
RN = Int(Value / 16)
LN = (Value And 15) * 16
If Value = (LN Or RN) Then
    Value = Not (LN Or RN)
    SHIFTD = Value
Else
    SHIFTD = LN Or RN
End If
End Function

Yet one more Sawtooth development update... (The first few were not boring enough)

Let me start this post with one of the first things I said when I created the Cryptography and Math category: "The subject (cryptography) is interesting to me but I am not a cryptographer and I don't have the time and computing power to be one. Having said that I have decided to put some of my ideas and screwball calculations on this blog"
  
The main goal for me here is to learn Visual Basic for Excel and because I am interested in math and cryptography this seems like a good way to do it. I want to restate that because I don't want to get a bunch of comments and nasty emails from people pointing out that "You don't really know what you are doing" and the most obvious one "Why design your own when there are so many free open source crypto-systems out there??" - Answer: I'm doing this for fun and to learn more about tricky Excel trickery.

OK now that I got that out of the way....
 

Sawtooth is possibly a component of an algorithm and the idea behind it is only to provide Cryptographic Diffusion. Click on that link for a nice Wikipedia page describing what that is if you are interested. The design goals that I set out for this and later modified slightly (are now also being modified again) are:
 

a) If you change any one of the Input bytes by even 1 bit, all the Output bytes should change

b) In addition to all the Output bytes changing (with a 1 bit input change) about half of the 64 Output bits should change

c) Ideally about half of the bits in each Output byte should change (4 bits of the 8 bits in each byte)

d) If all the Input bytes are 0's then the Output bytes should not all be 0's

e) Keep it really simple because I want to do all the tricky stuff in Microsoft Excel
f) There should be (ideally) a 1 to 1 mapping from any input string of bytes to a unique output string of bytes. In other words two different inputs shouldn't produce the same output.

g) It would be nice if the input string size could be varied to any length, not set at 64 bits (8 bytes)

Another good thing for me to mention is that I have no intention of trying to figure out an inverse of whatever I come up with here. If I decide to pursue this and use it in some kind of crypto-system it would be implemented in something like a Feistel type algorithm. Click on that link for another nice Wikipedia page for more info if you are interested. I may or may not bother to do that depending on how much fun it is.

 

So back to what I was talking about... Over the last month or so I have been messing around with lots and lots of spreadsheets and different ideas on how to accomplish the above stated design goals, and modifying the goals as I feel like it. What I have come up with is what I think I'm going to call the "final" design for this until at which time I decide to revise it.

For the Sawtooth Forward and Sawtooth Reverse functions I was using some basic math like addition and multiplication and I experimented with various combination's of things. Overall I wanted to keep these calculations as simple as possible and so what I finally decided to do was use an idea based on the 'dreaded' Linear Congruential Generator or LCG for short (again a link to Wikipedia for more info about LCG's). I say 'dreaded' because LCG's have been used over the years for generating pseudo-random numbers and they tend not to do that very well. As a side note I wonder why anyone would think a function with the word 'linear' in it's name would be good at generating random numbers... but that is off topic.
 
I'll add a little explanation of why I choose the numbers that I did because any time you use a numeric constant someone always asks "Why did you use that specific number and not some other?" There are several kinds of LCG's but the most straightforward and simple is something called the Multiplicative Linear Congruential Generator (or MLCG) and is the recurrence of this:
  
Xn = A * Xn-1 mod M
  
Where:
Xn is the new number
Xn-1 is the previous number in the sequence
A is a multiplier
M is the Modulus
  
Without going into too much detail because there is tons of detail on the web like THIS (click the link for more than you ever wanted to know) The M number is best if it is a prime number and the A number is a 'generator number'.  That is not a requirement, but for what I am doing I want M to be a prime number.  One drawback of using a prime number is it's slower for computers to use than a even power of 2 number. I tried a bunch of those and they didn't work as good as a prime number seems to.  I'm doing this for fun and prime numbers are fun so that is what I'll use! I decided to pick a prime M number that was as close to 16 bits in length as possible because 16 is a nice computer bus width friendly number and that number is: 65521. So M = 65521 for what I am doing.

For any M number there are lot's of possible A numbers and each has it's own pro's and con's. I decided to use 2 different numbers for A. One for the Saw Forward function and the other for Saw Reverse. The reason I chose the numbers that I did was because one is good at some random number tests that the other one isn't. Without going on any more about this, here is the A value for Saw Forward = 47104 and A for Saw Reverse = 32236.
  
I should make a point here that I'm not using the recursive form of the formula above so these numbers don't matter that much and more importantly I'm not trying to generate a sequence of random numbers. I just wanted numbers that won't 'lock up' and form patterns too easily when running through all the calculations. I picked the numbers that I did because random or pseudo-random numbers are not a bad thing for what I am doing and the numbers I choose have been studied and found to be good numbers to use. Even if I'm not using them in a traditional LCG formula. LCG's don't work by themselves for cryptographic purposes but as a (small) part of one they are OK.
  

As in the last iteration of the design I decided to use a Pseudo-Hadamard Transform or PHT for short. Click on that link for another nice Wikipedia page describing what PHT is if you are interested. It is a pretty easy way to mix two numbers together. Again I won't go into any in depth explanation of why but here is specifically what I used:
  
O' = X + Y mod 256
O" = 2*X + Y mod 256
  
So if X and Y are the two numbers you want to mix to get the two output numbers (O' and O") then you just do the above math. Because the Saw Forward and Saw Reverse function is 16 bit (mod 65521) and I want 8 bit outputs I am doing the PHT mod 256. That will give me two 'mixed numbers' between the values 0 and 255.
  
Last but not least in keeping with the cryptographic theme of all this I decided to introduce some key data into the mix. I think it's cool and nifty if the Cryptographic Diffusion is based not only on the input data you are encrypting but also some of the secret key. One way and the most often used would be to Exclusive Or 8 bytes of the key with the 8 bytes of either input or output data. I thought about that but decided that if I want the design goal (restated here):
  
"g) It would be nice if the input string size could be varied to any length, not set a 64 bits (8 bytes)"
  
to hold true I would have to have really long keys. Each time the input data string got longer the key would have to get longer too and that is a pain. So at the beginning of the Saw Forward function I decided to add  in a key byte and at the beginning of the Saw Reverse function do the same. Please note that for all the calculations that I have done thus far the key values have been 0. I didn't want to add another variable into all this so I just ignored the key and changed the 8 input bytes.

OK at this point I think it's time for a picture. You can click on it to get a bigger and clearer view. (In the legend above the picture the blue and orange horizontal arrows are reversed....) 

 

In the next paragraph I'm going to explain in detail what is going on in the picture. If  you are not that interested skip the next few paragraphs (or this entire blog post for that matter!!)

In the picture there are a bunch of colored arrows and what looks like three different Excel ranges. In reality it's all one range and I just copied it three times for the picture to make it a bit clearer and easier to explain.  This is essentially the same 'structure' that I had originally come up with just done with different calculations (and fewer of them) than before.
  
So in the top picture there is a Key 1 on the left with a blue arrow pointing up to the first blue Input cell with a value of 0 in it. Look at the top legend and it tells you what the blue arrows are mathematically (look at the orange one because I goofed in the picture and don't want to fix it). So in that first case the Key 1 is added to 0 (that's the X+Y part) then then multiplied by one of the generator numbers, the answer is put below it, 0 in this case. Then it repeats until it hits the 1 in the input and (0 + 1) * 47104 = 47104 so that is what is in the cell below the 1. It goes on like that to the right hand side of the range and all 8 input values have been assimilated.
  
On the far right second row there is a value of 10580. That value is added to Key 2 (set to 0 for this example) and then multiplied by 32236 mod 65521 to get 20075. Once that has been done the same pattern as before goes from right to left as shown in the middle range in the picture. Once all that has been done the PHT part is done to each pair of values as shown in the bottom range in the picture. Boy Oh Boy I give you a lot of credit if you read all that.

As mentioned before in the previous posts I built a spreadsheet that has two of the above ranges built into it. In the blue input areas I checked for the difference between the two inputs by taking the Exclusive Or of each cell and representing it in binary form with the Excel =DEC2BIN() function. The Exclusive Or was something I had to add in Visual Basic for Excel and the code for that is at the bottom of this post if you are interested. So each of the 8 pairs on input cells were checked with this formula:
  
=DEC2BIN(EXCLUSIVEOR(G16,G25),8)
  
So that would give me the 8 bit binary difference between the inputs (cells G16 and G25 in this case). I could then count the number of 1's in each cell to give me the binary difference or the Hamming Weight in computer vernacular with this Excel code:
  
=LEN(G5)-LEN(SUBSTITUTE(G5,"1",""))
  
At the same time I did the same thing with the output values of each range, Exclusive Or them, convert them to binary and count the 1's to give the difference (Hamming Weight). Click HERE of the original Sawtooth post for a picture of what this looks like and a visual of the "walking 1" that I am going to mention a bunch of times in the next paragraph. Walking a 1 is just multiplying by factors of 2.

Once I had all that working I wrote some more Visual Basic code to get 8 byte strings of random numbers and automatically copy and paste them into each of the input ranges. After each copy and paste of random numbers, the code then "walked a 1" through one of the input ranges and copied the binary output differences between the two into an empty area of the spread sheet. I set the code to loop through 82 iterations then let it rip. After that was done I filled one input range with all 0' and "walked a 1" and then 255 and "walked a 1".
  
This gave me a total of 87 different inputs, each with 64 "walking 1" differences for a total of 5568 different outputs. This spreadsheet suddenly got really really big (I can't understate that last comment).
 
Once I had all that data in the spreadsheet I then compiled it into some statistics. On thing I did is I looked at how many bits changed in each 8 byte output by counting the 1's of the Exclusive Or's with the above =LEN code and divided by 64 * 100 to get a percentage of bits changed. As mentioned above in design goal  (restated here):
  
"b) In addition to all the Output bytes changing (with a 1 bit input change) about half of the 64 Output bits should change"
  
What I found was on Average 51.091% of the bits changed. The Median value was 51.563% with a Mode of 50.000%. The Minimum value was 28.125%; Maximum was 76.563% and a Standard Deviation of 5.183%. I guess what all that means is there is a relatively balanced bell curve with good grouping around the Average (standard deviation is low).

So far so good. Then I looked at the total number of output byte, bit differences by byte location. (that's a confusing sentence). In other words one might ask the question: "How many bytes in the first byte location (Byte 1) had 8 bits change?" Look below for the answer!!! (Hint it's 27, upper left corner)

			Totals By Byte Location					# Bits Diff	Totals
27	22	28	25	21	27	19	26	8	195
191	183	208	188	188	184	186	202	7	1530
622	637	603	630	632	648	567	690	6	5029
1380	1333	1242	1329	1311	1199	1125	1233	5	10152
1577	1593	1571	1701	1569	1512	1444	1490	4	12457
1206	1129	1166	1183	1166	1275	1307	1131	3	9563
486	535	546	486	557	599	713	538	2	4460
79	135	204	26	124	124	207	258	1	1157
0	1	0	0	0	0	0	0	0	1
Byte 1	Byte 2	Byte 3	Byte 4	Byte 5	Byte 6	Byte 7	Byte 8

 
If you have read the previous Sawtooth posts you are sick and tired of looking at the above text chart so I took the trouble of making some cool graphs below. But to understand the graphs you need to see the data and there it is.
  
In the orange column the descending numbers from 8 to 0 are the number of bits that changed. The Byte 1 through Byte 8 along the bottom show the bytes and the numbers above each show how many times each changed by 8 bits, 7 bits, 6 bits etc... As you can see from the data the numbers are bigger in the 4 Bits Diff row and get smaller as you go down to 0 Bits Diff and up toward 8 Bits Diff. This is not an even distribution centered around 4 bits as there are many more 8 bit differences than 0 bit differences. In fact there was only 1 byte that had 0 bit's different in the entire test. (Byte 2). This satisfies design goal (restated here):

  
"c) Ideally about half of the bits in each Output byte should change (4 bits of the 8 bits in each byte)"
and it almost satisfies design goal (restated here):
  
"a) If you change any one of the Input bytes by even 1 bit, all the Output bytes should change"
 
I say it almost satisfied design goal a) because Byte 2 didn't change that one time. 0 Bits Diff row with a value of 1 as mentioned above.
  
This is much better than all the last Sawtooth attempts and it's good enough by the following equation that has a divide by zero error: = (1 / FUN) When fun approaches and finally reaches zero I stop messing with this spreadsheet. Fun now = 0 so I'm calling a single 0 byte difference in 5568 different output differences good enough.
 
As promised to summarize the above confusing and boring text chart I have created a couple of full color graphs that are as exciting as they are colorful. (click on it for a bigger clearer view)
 

There are three graphs in the picture. The upper left one with the red bars is a graph of the red Totals column data from the text chart above. That graph is showing the totals for all the byte locations and the biggest red bar is in the middle representing that most of the byte changes were 4 bit/byte changes. As can be seen the chart is skewed slightly to the left where the higher bit/byte changes are.
  
The next graph on the top right is the remaining data from the above text chart. Similar to the first graph the number of bit changes is across the bottom but in this one each byte location is shown with a separate colored bar.

The last graph on the bottom of the picture is the actual output values, NOT the Exclusive Or differences. of the outputs as in the other two charts. That is the actual values that came out of the Sawtooth function as the "walking 1" changed the random numbers that were entered as inputs. In that case I ran only 2288 sample iterations to get the data. I did that because I wanted to be sure that the values that came out of the Sawtooth function spanned the full 0 to 255 possible output values for each byte location and they did. I also wanted to get an idea of how evenly distributed the output values would be.
  
That bottom chart is a histogram of each value with the frequency of occurrence in the Y axis and the byte values 0 to 255 in the X value. They are pretty evenly distributed with a numeric Average of the actual values =  127.764; Median of 128; Mode of 221 and a standard deviation of 74.192. Not too bad considering that this data was created with 1 bit differences of random numbers. So the initial numbers were random but each set of random numbers changes 64 times in a very linear way.
 
This leaves me with one last design goal (restated here):
  
"f) There should be (ideally) a 1 to 1 mapping from any input string of bytes to a unique output string of bytes. In other words two different inputs shouldn't produce the same output."
  
This is a tricky one and I have not thought of an easy way to check this one. I'm going to write some code to test the data that I have already generated to look for this not happening but I'm not sure there is an easy way to test to see if it will happen.  As long as FUN not equal to zero I'll keep looking into that but for now I'll just think about it.
 
I think the next thing I am going to do with this is run some tests on keeping the input data fixed and just change the key values and see what happens. As I mentioned up to this point the key values were 0 to keep things simple. Knowing how the key values change the output with the input data held constant would be a good thing to know.
 
Below is the Exclusive Or code that I added in Visual Basic to get that function in Excel. Below that is the Visual Basic Code I wrote to generate all the data for everything I talked about here. The Exclusive Or code has pretty colors to help understand it. If you paste it into the Visual Basic Developer window in Excel the  function =EXCLUSIVEOR( ) will be added to the list of things you can type into any cell. It will give you the Exclusive Or value of the two numbers (8 bits or less) that you reference. It works like that because it's a Function.
  
The other code doesn't have pretty colors because I have to add the color manually and I don't feel like  doing it. If you copy and paste it into Excel it will recognize all the code words and color it for you, making it easier to follow. That code will run as a Macro because it is defined as a Sub and you will see it in the list of macro's with the name "Walk_Diff_Multiple1"

Email me or leave a comment in the blog and I'll detail how it works or clean it up with colors or something to make it easier to read.
 
Enjoy!
.........................................  
Exclusive Or Code:

Function EXCLUSIVEOR(Byte1 As Integer, Byte2 As Integer)
'
' EXCLUSIVEOR (Byte1 , Byte2)
' XOR Exclusive Or of Two 8 bit Byte's
' November 2009 http://ottobelden.blogspot.com
'
    EXCLUSIVEOR = Byte1 Xor Byte2

End Function

...........................................
Sub Walk_Diff_Multiple1()
'
' This code will get rnd numbers generated by Excel from one range in sheet
'   then copy values only to three locations, Top Input To Change,
'   Bottom Input To Change and where current output row is for Reference
' Once Rnd values have been copied, "walk a one" thru all Input to Change values
'   copying output value differences to output rows and Top Raw Outputs
'   then go back and do it again
' November 2009 http://ottobelden.blogspot.com
'
' Rnd Numbers range     C31, D31, E31, F31, G31, H31, I31, J31
' Input to Change       C9, D9, E9, F9, G9, H9, I9, J9
' Input Diff to Copy    C2, D2, E2, F2, G2, H2, I2, J2
' Output Diff to Copy   C5, D5, E5, F5, G5, H5, I5, J5
' Top Raw Output Valus  C12, D12, E12, F12, G12, H12, I12, J12
'
    Dim Multi As Long  ' This is the walking 1 valut to Xor
    Dim Orig As Long   ' This will be the Origional value of cell before Xor
    Dim Row As Long   ' This keeps track of what row the output goes to
    Dim Col As Long     ' This keeps track of the column that Multi will change
    Row = 73                ' Row to start pasting 73 is in unused rows range
        For SampleSize = 1 To 42  ' Number of samples
                    Col = 10      ' Start in Column "J" 10th letter
                    Multi = 1     ' Value to start Xor'ing with
                    Orig = 0      ' Set to 0 in case I have to initialize variables
                    ' Select Rnd values to copy
                    Range("C31:J31").Select
                    Selection.Copy
                    ' Paste Rnd values for Reference
                    Range(Cells(Row, 3), Cells(Row, 10)).Select
                    Selection.PasteSpecial Paste:=xlPasteValues, Operation:=xlNone, SkipBlanks _
                    :=False, Transpose:=False
                    ' Select Rnd values to copy from Reference because Rnds have changed
                    Range(Cells(Row, 3), Cells(Row, 10)).Select
                    Selection.Copy
                    ' Paste Rnd values to Top Input
                    Range(Cells(9, 3), Cells(9, 10)).Select
                    Selection.PasteSpecial Paste:=xlPasteValues, Operation:=xlNone, SkipBlanks _
                    :=False, Transpose:=False
                    ' Select Rnd values to copy from Reference because Rnds have changed
                    Range(Cells(Row, 3), Cells(Row, 10)).Select
                    Selection.Copy
                    ' Paste Rnd values to Bottom Input
                    Range(Cells(18, 3), Cells(18, 10)).Select
                    Selection.PasteSpecial Paste:=xlPasteValues, Operation:=xlNone, SkipBlanks _
                    :=False, Transpose:=False
                    ' Start walking a one thru the input to change values
                        For ColCount = 1 To 8
                            For Counter = 1 To 8
                        'Copy and Paste Input Values Only to Output range
                            Orig = Cells(9, Col)                     ' Set the current value of the cell to Orig
                            Cells(9, Col) = Cells(9, Col) Xor Multi ' Xor Cells(ROW=9, COL) with Multi
                            Range("C2:J2").Select                   ' Select Input Diff range to copy
                            Selection.Copy
                            Range(Cells(Row, 12), Cells(Row, 19)).Select
                            Selection.PasteSpecial Paste:=xlPasteValues, Operation:=xlNone, SkipBlanks _
                            :=False, Transpose:=False
                        'Copy and Paste Output Values Only to Output range
                            Range("C5:J5").Select     ' Select Input Diff range to copy
                            Selection.Copy
                            Range(Cells(Row, 21), Cells(Row, 28)).Select
                            Selection.PasteSpecial Paste:=xlPasteValues, Operation:=xlNone, SkipBlanks _
                            :=False, Transpose:=False
                        'Copy and paste Raw output values
                            Range("C12:J12").Select     ' Select Raw output range to copy
                            Selection.Copy
                            Range(Cells(Row, 52), Cells(Row, 59)).Select
                            Selection.PasteSpecial Paste:=xlPasteValues, Operation:=xlNone, SkipBlanks _
                            :=False, Transpose:=False
                            Row = Row + 1
                            Multi = Multi * 2
                            Cells(9, Col) = Orig ' Set the cell that just got Xor'd back to it's Orig value
                            Next Counter
                        Multi = 1                  ' Reset Multi for next input byte
                        Cells(9, Col) = Orig ' Set current input cell to Col
                        Col = Col - 1           ' Move back one column
                    Next ColCount
        Next SampleSize
End Sub

Pseudo-Hadamard Transforms Sawtooth

Hard to believe that I am still at this but as I mentioned in the last post about a week ago I'd keep messing with this. Yes this started out as something to do on the weekend, just a passing idea and now I can't stop. I have fallen in love with my excel spreadsheet and the "statistical quagmire" my sawtooth idea has turned into. Anyway on to the latest developments...

What I have come up with is a modification of the initial Sawtooth idea. HERE is the first idea so if you have not read that post this one probably wont make any sense (if any of this can make sense). So from here on out I'll assume that my faithful readers have been keeping up with what I have been doing and I'll jump right in with a picture. (You can click on it to see it in detail)

This is very similar to what I was doing in the first post. I changed the math a little by using the same modulus  (257) for both the Saw Forward and the Saw Reverse parts that you can see in the Excel rows 10, 11, 13 and 14 in the picture above. The same thing is going on below on rows 19, 20, 22 and 24. As in the first spreadsheet (origional post) the same exact mathematical functions are goin on in the 'upper' and the 'lower' part of the picture. The significant part that I changed was I got rid of one Saw Forward and one Saw Reverse function and replaced it with 2 'layers' of a Pseudo-Hadamard Transform. I decided to do this because I wasn't getting the diffusion that I wanted with just three layers, iterations or rounds  (whatever you call 'em) of the Sawtooth idea.

Anyway at first glance this looks to be much better. I still am not sure what (if anything) I am going to do with this when (if) I am ever finished but it is fun... The PHT part is being done mod 257 as well by the way. So if you take a look again at the picture you can see that on row 9 there is a blue Input row with seven 0's and one number 2 in it. If you compare that to row 18 there are also seven 0's and a number 1. Up at the top  of the picture there is a box where there is the I' * I" and you can see the binary Exclusive OR of the inputs which are all mostly 0's with just a couple of 1's. That is because 2 (00000010) exclusive OR'd with 1 (00000001) is 3 (00000011). The numbers under all the 0's are the number of 1' in each number (or the number of different bits) And below that is another similar box with O' * O" with a bunch more binary numbers. That box is showing the difference between the outputs (rows 16 and 25 in the spreadsheet). What I am getting at here is in the picture the difference of the inputs is 2 bits and the difference of the outputs is a bunch of bits (38 to be exact) spread out all over the place. That is what I want.

So to repeat the same experiments that I did in the previous posts I ran a "walking 1" input bit difference through all 64 input bits with 8 different input values giving me a total of 512 outputs. The first input values were all 0's and the second input values all 255 woth the remaining 6 random numbers. Go back to THIS post if this doesn't make sense and to get the source code for Visual Basic for Excel that does the walking 1.

As in the other posts I created a chart to show the number of output bits that changed per byte with one input bit flipped through all the input values:

 

									# Bits Diff	Totals
2	5	4	1	2	3	1	2		8	20
25	7	23	11	21	16	18	19		7	140
59	39	54	54	70	83	63	69		6	491
98	93	135	117	87	142	110	155		5	937
137	112	176	143	148	155	134	164		4	1169
106	112	72	134	149	113	116	63		3	865
85	111	48	52	35	0	70	40		2	441
0	32	0	0	0	0	0	0		1	32
0	1	0	0	0	0	0	0		0	1

 

That is a confusing chart! Well not really confusing... if you look at the green 1 on the left hand side (under the 32) and follow that row across you see a green 0 and a green 1. What that is saying is that one byte had 0 bits different for a total of one time, and that one byte was the second from the left. Now go to the row above that with the 32 in it. That row is saying that there were 32 bytes that had only 1 bits different for a total of 32 times and they too were all the second bytes from the left. You can go up the rows and see how many bytes had bits different, the number of bits different, which bytes they were and the total number of bytes...etc... you get the idea. The thing I wanted to point out  is unlike the same charts in the previous posts there are much fewer unchanged bytes - one in fact. Also in looking at the Totals column mostly there were bytes that had 4 bits different (1196 of them) and the distribution is weighted toward 8 bits changing and not 0 bits changing.

Wow that is a huge waste of my time doing this but it is fun and like I said I have fallen in love with my Excel spreadsheet. I don't like the fact that the 1 bit change 32 times and the 0 bit change 1 time were in the same byte location. I'll figure out why that is happening and also the distribution by # of bits change  by byte location isn't as smooth as I would like or expect. Something isn't working right. Enough of this for now.

I have another exciting electronic project brewing in the garage so stay tuned. 

16 bits with Excel DEC2BIN and other stuff...

Continuing along with the Sawtooth Idea might be a bit insane but I thought that I would anyway. What started out as something to do on the weekend has turned into a statistical quagmire... well not actually I just think that  statistical quagmire sounds neat. Anyway I have messed around with it a bit more and tried a dozen or so different approaches all similar and along the same lines as the origional.

CLICK HERE FOR A PICTURE OF THE ORIGIONAL

As I mentioned I have tried a bunch of different formulas and silly math for the forward and reverse parts and I have decided that the origional might just be the best. I'm not quite at that decision yet and I'll save all the details for another post but while I am here I thought I'd share a interesting thing about Excel. As so many people have found out the DEC2BIN function in Excel will convert a decimal number into binary but it only works up to 10 bits. That sucks in a way especially for what i was trying to do the other day - convert decimal numbers as big as 16 bits and put the upper 8 bits in one cell and the lower 8 bits in another. But wait there is more!

As if that wasn't enough I wanted the decimal equivalent of the upper 8 bits in one cell and the decimal equivalent of the lower 8 bits in another. I thought about a visual basic for Excel Sub routing to create a custom function in Excel but I opted for just doing it in Excel. Here it is for your enjoyment:
 
=BIN2DEC(DEC2BIN(MOD(BE7/256,256),8))
=BIN2DEC(DEC2BIN(MOD(BE7,256),8))
 
Yes friends that is nuts bit it works! What the above does is it takes the value in cell BE7 and puts the upper 8 bits converted into a decimal number in one cell and the lower 8 bits converted to decimal in the other cell. If you get rid of the BIN2DEC parts you will of course get the bits themselves... like this:
 
=DEC2BIN(MOD(BE7/256,256),8)
=(DEC2BIN(MOD(BE7,256),8)
 
I'm sure that there probably is another way of doing it but that worked for me. You would think that they would give the DEC2BIN conversion more range than 10 bits but for some reason they don't.
 
Those lines came in handy when messing around with the Sawtooth idea and I'll explain more why later but for now that is about all I have to say.

The Saw is Sharp (and I'm dull)

I've had some time to mess around a bit more with the Sawtooth 'thing' that I created a couple of weeks ago. In looking at it and re-reading my post I realized that there were some boo boo's in it that I should have seen right away but I was to pre-ocupied with the programming. Anyway HERE is a link to the post with all the pretty pictures. You can click on any of them for a bigger view or just trust me that there were some problems. Before i go any farther you should at least look at This Picture from that post. In this picture you get the basic idea of where I am going with this line of thought and why I decided to call this Sawtooth.

In the picture you can see the upper row labeled Saw Forward with the numbers 1, 2, 3 going off to the right etc... Below that is another row labeled Saw Reverse and on top of both of them is a bunch of blue arrows. In the picture the blue arrows pointing to the right (mostly) in the Saw Forward row are representing modular addition of two values plus 1 with a modulus of 257. Below that in the Saw Reverse row the same thing is happening but in the opposite direction (right to left). Finally the very last row of numbers was copied down to the Output but taken mod 256 to make them 8 bits. A quick and preliminary look at this as I mentioned in the first post seemed encouraging.

But... while thinking about it shortly after posting I realized that there were some serious and obvious problems with doing this. First of all there are a whole bunch of "equivalent inputs" that is, inputs that give the same output. Here are a few for your enjoyment:

All of these inputs make an output of all 0's
Input 1	8	231	30	224	31	225	25	241
Input 2	255	255	5	241	19	241	5	255
Input 3	245	24	225	31	224	31	226	19
Input 3	3	246	10	240	19	241	5	255
Input 4	8	231	30	225	25	240	5	255
Input 5	8	231	30	225	24	246	248	12
Input 6	8	232	24	240	4	4	242	13
Input 7	3	241	19	241	4	4	242	13
Input 8	254	5	241	19	240	11	241	13

  
This should have been obvious with very little thought but anyway... I wrote an inverse of the math that is in the picture and created a whole bunch of equivalent inputs which If I am thinking right means that there a whole bunch of outputs that are not valid. In other words no matter what the input is you can't get the output to certain 8 byte strings. Although I didn't specifically mention it in the original post this isn't what I am going for. What I do want is a direct and unique (1 to 1) mapping from any input string to an output string. So here are the original Design Goals with a new addition:

a) If you change any one of the Input bytes by even 1 bit, all the Output bytes should change

b) In addition to all the Output bytes changing about half of the 64 Output bits should change

c) In addition to that ideally about half of the bits in each Output byte should change (4 bits of the 8 bits in each byte)

d) If all the Input bytes are 0's then the Output bytes should not all be 0's

e) Keep it really simple because I want to do all the tricky stuff in Microsoft Excel
f) That stuff I said above about 1 to 1 mapping

One thing that bothered me was I did do a "walking 1" through an input of all 0's as I mentioned in the origional post but didn't see any problems. Then I started thinking a bit more about what I was doing and decided that in addition to walking a 1 across all 0's I should also walk a 0 across all 1' in the input. If you are wondering what I am talking about with the 'walking 1' talk look at THIS picture. Specifically look to the right where there is a column of a bunch of 00000000 values under the heading of  I' * I" . If you look very carefully in that column you can see on the far right (of that column) a value of 00000001 and right under it: 00000010 followed by 00001000 and so on. In other words the input difference (I' * I") is 1 bit and that bit is moving or "walking" from right to left.

Anyway before I went any farther into this I modified the Microsoft Excel Visual Basic code a bit to make the "walking 1" task a bit easier to try with more input values. The original code in the first post literally walked a 1 across an input of all 0's. Now the code walks a difference of 1 bit across any input values I choose to put in the spreadsheet. So I can test all 0's as the input or all 1' as the input or all random numbers as the input.

Here is the Visual Basic Code for your personal enjoyment:

Sub Walk_Dif_Bit()
'
' Set up a loop then exclusive or a "walking 1" through the Input range
' After Xor into the Input range, paste values to Output range from Formula range
' Go back and change Input range and paste new Output values into NEXT row of Output range
' November 2009 http://ottobelden.blogspot.com
'
' Input to Change       C9, D9, E9, F9, G9, H9, I9, J9
' Input Diff to Copy    C2, D2, E2, F2, G2, H2, I2, J2
' Output Diff to Copy   C5, D5, E5, F5, G5, H5, I5, J5
    Dim Multi As Long       ' This is the walking 1 valut to Xor
    Dim Orig As Long        ' This will be the Origional value of cell before Xor
    Dim Row As Long        ' This keeps track of what row the output goes to
    Dim Col As Long          ' This keeps track of the column that Multi will change
    Col = 10                ' Start in Column "J" 10th letter
    Multi = 1               ' Value to start Xor'ing with
    Orig = 0                ' Set to 0 in case I have to initialize variables
    Row = 201            ' Row to start pasting
        For ColCount = 1 To 8
                For Counter = 1 To 8
                'Copy and Paste Input Values Only to Output range
                    Orig = Cells(9, Col)                              ' Set the current value of the cell to Orig
                    Cells(9, Col) = Cells(9, Col) Xor Multi ' Xor Cells(ROW=9, COL) with Multi
                    Range("C2:J2").Select                          ' Select Input Diff range to copy
                    Selection.Copy
                    Range(Cells(Row, 12), Cells(Row, 19)).Select
                    Selection.PasteSpecial Paste:=xlPasteValues, Operation:=xlNone, SkipBlanks _
                    :=False, Transpose:=False
                'Copy and Paste Output Values Only to Output range
                    Range("C5:J5").Select     ' Select Input Diff range to copy
                    Selection.Copy
                    Range(Cells(Row, 21), Cells(Row, 28)).Select
                    Selection.PasteSpecial Paste:=xlPasteValues, Operation:=xlNone, SkipBlanks _
                    :=False, Transpose:=False
                    Row = Row + 1
                    Multi = Multi * 2
                    Cells(9, Col) = Orig
                Next Counter
            Multi = 1                 ' Reset Multi for next input byte
            Cells(9, Col) = Orig ' Set current input cell to Col
            Col = Col - 1           ' Move back one column
        Next ColCount
End Sub

Anyway enough of that. I posted it because someone might want to know how to do it (like me for instance when I forget how I did it).

So I tried several different variations (3 total) of the Sawtooth idea using different math to avoid the pesky "equivalent inputs" problem. For each of these three all I did was change the formulas for the Saw Forward and Saw Reverse parts. Refer to this picture for a refresher of what those are. For each of the three I ran a total of 8 different input strings and 'walked the one' across each of them giving a total of 512 unique input - output differences. Of the 8 different input strings one was all 0's, another was all 1's and the remaining 6 were random bytes selected by Excel.

  

The first thing I tried was a Saw Forward with simple addition mod 257 and a Saw Reverse with simple addition mod 256. Here is a table of the the number of bits/byte differences:

 

		Bytes	Diff						# Bits Diff	Tot # Bytes
3	3	1	1	4	2	2	2		8	18
13	15	20	14	14	10	22	16		7	124
55	45	63	53	53	50	52	50		6	421
120	100	111	114	110	119	119	134		5	927
137	151	138	137	136	152	140	147		4	1138
116	106	99	110	124	97	99	94		3	845
48	71	65	68	53	61	53	58		2	477
19	21	12	14	16	20	24	10		1	136
1	0	3	1	2	1	1	1		0	10

This isn't great as there are 10 instances of 0 bit changes in 1 out of 8 output bytes. (see  green in chart)  In other words changing one bit in the input caused only 7 of the 8 output bytes to change 10 different times.  Because of a) in the design goals this is poopie. This also isn't the best because with the Saw Forward and Saw Reverse using no addition of 1's anywhere all 0' in the input creates all 0's in the output. and this is in direct violation of another design goal. Although not really a bad thing I don't want that. So I added a +1 in the first Saw Forward row and got:

		Bytes Diff							# Bits Diff	Tot # Bytes
5	2	1	5	3	3	2	5		8	26
7	12	21	16	16	15	16	13		7	116
61	60	72	48	51	56	59	65		6	472
119	100	109	128	122	119	92	117		5	906
125	138	132	151	139	149	142	138		4	1114
116	124	96	98	100	97	110	107		3	848
64	61	61	47	62	52	71	58		2	476
12	13	18	18	17	19	18	9		1	124
3	2	2	1	2	2	2	0		0	14

Interesting but the 0 byte difference got worse with a 14 total instances out of the 512 inputs. Note that the random numbers are the same for all three of these tries. They were randomly picked by the Excel random function but I didn't change them with each formula change. If you want to know why email me because I'm getting tired of typing and want to wrap this post up pronto.

So without delay here is the last iteration that I tried.

I tried a Saw Forward addition mod 257 with 2* the second value like this in Excel:

=MOD(C10+(2*D9),$C$8)

and Saw Reverse addition mod 256 with 2* the second value like this in Excel:

=MOD(F11+(2*E10),$C$7)

The multiplication should remove all the 0 bit changes in the output byte differences unless there happens to be a strange occurrence where because of the modular addition there is an equivalent value after the multiplication. What are the odds of that happening you ask? Well here is your answer:

		Bytes Diff							# Bits Diff	Tot # Bytes
0	1	0	0	0	2	0	0		8	3
7	12	9	8	5	8	9	8		7	66
21	47	23	24	45	24	26	28		6	238
52	49	45	61	51	60	49	51		5	418
80	63	76	69	70	70	69	80		4	577
57	57	59	61	44	56	50	50		3	434
34	21	35	27	32	29	38	30		2	246
5	6	8	4	9	7	14	8		1	61
0	0	1	2	0	0	1	1		0	5

It happened 5 times in the first 256 steps... never with all 0's and once with all 1's then 4 times in the second set of random bytes.

So now that I have a much better idea of what is going on with this I'm wondering what value it has (Ha Ha!) First off it has been fun to write the Visual Basic code and I have learned a lot about Microsoft Excel in that regard. Second I'm not ready to give up on this idea. I have yet to see two bytes of any output string not change at the same time and for awhile I considered leaving it at that. There are some other things to try other than the multiply by 2 idea so I'll try those and see what happens. Adding a substitution table and actually substitute the sum of the values would be neat too. More to come as I get time and feel like messing around with this.