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.

Bamboo Bicycle Construction....

Some of my more faithful and observant readers (all four of you) might remember the Electric Hub Motor Bicycle Prototype that I built. Down at the bottom of that post I mentioned that I had designed a bicycle  rear dropout for a friend of mine. Here is a picture of the CAD model that I did:

  

 

Bicycles and similar things are interesting and fun to design because almost no part of it is at right angles, straight or intuitive. There are a lot of compound angles to deal with and of course it has to be comfortable which usually means adjustable. Bamboo makes it even more interesting thing to use because you have to assume that the bamboo will be straight. At least unlike metal tubes you can't really bend it around  the tires and other places. Because all the frame tubes have to be straight it makes the angles in the dropouts even trickier.

  

Well my friend has started construction of the bicycles that these will be used on and I thought that I would share some pictures of the process. The frame of the bike is being make with bamboo instead of steel or aluminum tube. Bamboo is a really cool material and I use it myself in a lot of my lathe projects because it's cheap, the grain is tight, it's strong and did I mention that it is cheap?

  

 

The above picture is the frame being assembled and glued together on a jig. The dropouts are in the lower left corner and are where the rear wheel attaches and the frame tubes (seat and chain stay tubes) come together.
  

 

The jig is built on a wood base that has a 1:1 printout of the bicycle frame with holes drilled through the wood and the paper in all the important places. Above is a picture of the jig holding the dropouts with the adjustable pivot's to allow some play in the angles. The bamboo is attached to the metal components of the bike using 2 part epoxy.

  

Just a quick post to close the loop and answer all the questions that I had (none) from the mention of Dropout design in the Electric Bike post!!!