Counter

TEA has some iterations to do multiple rounds of mixing and shuffling the data values.  To achieve this, we'll use some looping.  There are only 64 rounds, so were this algorithm designed for hardware, we might be able to unroll them into 64 parallel operations.  But, this algorithm was designed for software and it seems very little parallelism can be enlisted to speed things up.  The results of each round feedback into the previous.  Feedback loops like this are important for good mixing and permuting.  Also, since this is a Feistel cipher, half of the data block is mixed/shuffled with the other half.  Each round jumbles and mixes from one side to the other.  This dependency makes parallelization very difficult at very best to impossible.  I imagine determining any required structure or method to parallelize this is equivalent to cryptanalizing it.   Finding a usable result would probably crack it.

So, since we need to iterate, we need a counter.  Below is a counter implemented with a 32bit adder, a 32bit  register/memory and an extra chooser to feed the value 0 in when the reset signal is sent.  The 7 segment decoder + display is just for debugging.

The inc signal increments the counter.  Reset sets it to 0.  q is the output.  I forgot to change the output name, but it is the only one, so it doesn't really matter.  I'm not sure why 'q' is the default.  Maybe it is some standard.

8,32 bit Selectors

When passing data around to different destinations, we need to select where it goes.  There is an opcode that selects the operational unit.  The input registers are decoded from the operands, and directed using selectors to push the input to the operator component.  After decode happens, the pathway is enabled by data path selectors.  Here is an 8 bit selector.

You can see we use tri-state gates only send the output when the select line is enabled.  When not selected, the output's are tri-stated and won't interfere with the input they are connected to.  This way we can have many selectors connected to a common input line without interference.

With the 8 bit selector we build up a 32bit to help shuttle our data around.

7 segment decoder

Peeking at memory and using traces is fine, but for output and checking numeric values, 7 segment displays are nice.

Here's a Numitron, a 7 segment incandescent filament display made by RCA in 1970.

"Incandescent light seven-segment display prPNr°17" by D-Kuru - Own work. Licensed under CC BY-SA 3.0 at via Wikimedia Commons 


To display digits on these, you need to convert a binary encoding to the physical layout for the digit positions.

Number	Binary	Segments
0	0000	a,b,c,d,e,f
1	0001	a,b
2	0010	a,b,d,e,g
3	0011	a,b,c,d,g
4	0100	b,c,f,g
5	0101	a,c,d,f,g
6	0110	a,c,d,e,f,g
7	0111	a,b,c
8	1000	a,b,c,d,e,f,g
9	1001	a,b,c,d,f,g

There are probably more clever ways to wire this up to reduce the gates and connections required.  For example, the only time segment a is not lit up is for the number 4.  But I'm going to just brute force it and hook up logic for it that says "If all the 1's in the binary number are on AND all the 0's in the binary number are off, then set the signal high for the segments for that number."  As an example, for the number 1, we'll check that bit 0 is on and then use a NOR for bits 1-7 to make sure none of them are on.  If 0 is on and 1-7 are off, then we know that is 00000001 which is the number 1 (base 10).  When that is the case, we'll want to turn the signal on for segments 'a' and 'b' which connect on the right via those OR gates.  Each number that needs to activate a segment attaches to the OR gate for that segment.  So the top OR on the right goes to segment 1 and the bottom one to segment 2.

 With a seven segment display, you can show hexadecimal numbers beyond 0-9 which include a,b,c,d,e,f, but I've only hooked my 7 segment decoder to do 0-9.  Maybe I'll add a-f later.  Below is the full decoder.

32bit XOR

Tiny Encryption Algorithm needs a 32 bit XOR.  XOR is basic gate type, so we just chain 8 of those together to make an 8bit version (byte).

From there we just chain 4 of those to get a 32 bit version.

Adtractor

To implement subtraction, one takes the one's compliment of number you want negative.  Then you add the two numbers together as normal.  This of course means that your representation is ones compliment and anything with the high bit set is negative.

To construct this, one needs to first make some IC's to make a 32bit compliment.  We do this by making an 8bit compliment and then group 4 of these to make a 32 bit compliment.

Finally, we can make an adtractor by adding a signal to choose the normal input or, a compliment for subtraction of the chosen input.  Note, adtractor is not an standard word for this.  It is normally called a adder-subtractor, but I like adtractor better.

One quick note.  When there is a choice of two outputs to an given single input, we need a special gate to disable the logical output of inputs we are not interested in.  If one were high and another connected that was low, the result is indeterminate.  The solution is a tri-state gate that, when desired, will pass the signal through.  Otherwise the output is High-Z (floating, tri-state) and does not affect the result of other connected gates to the input.  More on this later.

Here is the 8bit compliment:

And here is a 32 bit compliment composed of 4 - 8bit compliments.

Now that we have the compliment, we can make the adtractor.  Here it is:

You'll notice the addend coming in (middle input line) and going straight to the 32bit adder.  Below is the addend or possibly subtracthend.  We convert to the 32bit compliment and then pass both values to the IC named "32bit choose".  This selects one of the inputs to pass through depending on the mode flag.  This is the top value coming in and chooses the mode, addition or subtraction.  Let's see how this 32bit chooser is implemented.

   

 Here we have two 32 bits values coming in on the left.  Each is broken into 4 8it bytes and divided up to these IC's named "2 byte selector".  The 2 byte selectors get the "select in" signal and then output to be recombined to the final 32 bit value.  I don't really like the name "2 byte selector", maybe "byte selector" would be better.  The select signal chooses which of two input bytes is passed out.

Now on to the "2 byte selector"...

Here we see the use of tri-state gates.  The value of Select In determines which of the tri-state's are allowed to pass their value through to the final output.  You can see the NOT gate above the "b In" group that inverts the selection value.  Only the values of the group with a logical 1 values will allow the values to pass through.  Otherwise they are High-Z and have no influence on what they are connected to.  Without this, were one to output both high and low to the same input, the result is indeterminate.  Might they cancel?  Might it cause a short circuit?  Are there specific types of hardware that behave in specific ways?  If anyone knows, leave a comment.  I certainly don't, this is just a theoretical exercise to me.

So, returning to the adtractor you can see the compliment and chooser in action again and see how they work together to make a normal adder perform subtraction.

adders

Below is a 1 bit full adder I made.  If you are unsure what a full adder does, you can read up on it on wikipedia.  http://en.wikipedia.org/wiki/Adder_%28electronics%29

This is certainly over-complicated and not optimized.  The route to optimize it would be to either write out the boolean equations for this (or just come up with them from a truth table) and then simply the expression into fewer gates.  Looking on wikipedia from the link above, I just noticed  how inefficient this is.  But my implementation will only have a few of these, so as long as it functions properly, I'm not interested in this point in optimizing.

After that is a stack of 8 of them wired up to make an 8 bit IC.  And then after that, 4 of those to make a 32bit adder.  32bit addition is needed for TEA, so this is one of the foundational ICs.

The mathematical operations TEA needs are (all 32 bit): 

• addition
• subtraction (for decryption)
• left bit-shift (by 4 bits)
• right bit-shift (by 5 bits)
• XOR

1 bit full adder (highly unoptimized)

8 bit full adder

32 bit full adder

Intro

Hi folks,

Well, it started out as a small exercise when I was doodling with my daughter.  I wanted to see if I could make a full adder with just basic logic gates without any help.  I worked on it a bit and then a couple days later found an online program where I could model it up and try it.

After that I made a basic calculator.  As I moved to more complicated stuff, I decided rather than make yet another simple computer, I wanted to implement an ASIC for Tiny Encryption Algorithm.  See http://en.wikipedia.org/wiki/Tiny_Encryption_Algorithm.

The goal was to not look anything up and just see what I could get done on my own from scratch.  I tried a few programs, but am now using LogicCircuit, http://www.logiccircuit.org/.

This series of posts will be to show the IC's making and employing to construct it and also to document my progress.

Maybe someone will find this interesting.  Either way, I think this is just a lot of fun.

-Casten