[Challenge] Smallest ALU?

[idkwhoiam129]

I'd love to see who comes up with the smallest ALU design. Let's say the guidelines are:
8 bit bus, both inputs and output
6 functions: OR, NOR, AND, NAND, XOR, NXOR (do addition if you want as well)
3 bit function selection (0 defaults no function)

Here's my design:

Spoiler: ALU

size is 39 x 118 blocks

Have at it! Smallest ALU gets bragging rights!

 

[ZeroGravitas]

Here's my design:

Very pretty. So you use the two sets of 8 switches to input two 8 bit binary strings, before/after selecting the logical operator (via 3 bit binary address bus), and the result is output directly to the 8 torches on the right. Cool. Handy set of extra instruction, ready for a CPU. But is this not just a "LU", since it doesn't do any (traditional) arithmetic operations (Add, subtract, multiply, divide)? Waiting for the first multiplication machine to drop, still...

But go for the challenge people, absolutely!

 

[idkwhoiam129]

Very pretty. So you use the two sets of 8 switches to input two 8 bit binary strings, before/after selecting the logical operator (via 3 bit binary address bus), and the result is output directly to the 8 torches on the right. Cool. Handy set of extra instruction, ready for a CPU. But is this not just a "LU", since it doesn't do any (traditional) arithmetic operations (Add, subtract, multiply, divide)? Waiting for the first multiplication machine to drop, still...

But go for the challenge people, absolutely!

Yeah I do suppose you're right.. Although these functions could technically still be done with it, if there were RAM and a program to do it. I'm not too familiar on how to do anything other than addition. I could add the arithmetic through full adders, but then there's a 9th bit for the output.
[doublepost=1464842085,1464829320][/doublepost]I added 8 full adders, so I also had to add a 9th output bit. Makes it quite larger though

Spoiler: ALU With Addition

 

[DownsPath]

Waiting for the first multiplication machine to drop, stil...

@ZeroGravitas i have no idea now it could work in A logic way, only hardcoded. i have A look maybe i can build one

 

[crawlr]

A few thoughts for everyone:

I'm not too familiar on how to do anything other than addition. I could add the arithmetic through full adders, but then there's a 9th bit for the output. I added 8 full adders, so I also had to add a 9th output bit. Makes it quite larger though

In fixed bit systems the extra bit that you get from a ripple adder is usually connected to an overflow flag. Many operations could result in output greater than our fixed bit system can handle, which is fine, we just ignore the extra but leave a way to signify to the user that the data was truncated. To handle subtraction you just invert and add one to get the two's compliment then add as normal. For example 5 - 3 (101b - 011b):

011 (3 in binary)
100 (inverted aka the one's compliment)
101 (after adding 1 we have the two's compliment)

101 + 101 = (1) 010 (the anser is 10b aka 2, with a single overflow bit which is ignored).

This is normally achieved at the circuit level by having a conditional inverter before your full adder input. If you want to do subtraction you invert one of the inputs and set its carry bit to high (signifying the +1 to reach two's compliment).

@ZeroGravitas i have no idea now it could work in A logic way, only hardcoded. i have A look maybe i can build one

Multiplication isn't that difficult at the logic level. For example to multiply two, two-bit numbers we just shift and add like so (3x2 or 11b x 10b):

This approach requires that you total each partial sum in an accumulator as you go. In modern architecture we use Wallace Trees or Dada Multipliers which look like this:

So depending on the bit size of your system you can just expand that circuit as needed.

 

[DownsPath]

A few thoughts for everyone:



In fixed bit systems the extra bit that you get from a ripple adder is usually connected to an overflow flag. Many operations could result in output greater than our fixed bit system can handle, which is fine, we just ignore the extra but leave a way to signify to the user that the data was truncated. To handle subtraction you just invert and add one to get the two's compliment then add as normal. For example 5 - 3 (101b - 011b):

011 (3 in binary)
100 (inverted aka the one's compliment)
101 (after adding 1 we have the two's compliment)

101 + 101 = (1) 010 (the anser is 10b aka 2, with a single overflow bit which is ignored).

This is normally achieved at the circuit level by having a conditional inverter before your full adder input. If you want to do subtraction you invert one of the inputs and set its carry bit to high (signifying the +1 to reach two's compliment).



Multiplication isn't that difficult at the logic level. For example to multiply two, two-bit numbers we just shift and add like so (3x2 or 11b x 10b):

We can model a simple 2 bit multiplier like so:

So depending on the bit size of your system you can just expand that circuit as needed.

wow thank you for the easy explaination

but why are ther 4 Outputs in the picture?

 

[crawlr]

Oops. I mixed up my images, that one is of a wallace tree approach which you can read about here.

I can't find my simple accumulator pic atm. But the idea is to total each partial sum in an accumulator as you go. I will modify the original post to fix the image. If you need me to put together the other logic diagram I can remake it...

 

[Statue of Libroty]

That is one pretty looking piece of work.

However, that's an odd set of instructions to put on an ALU. It seems more reasonable to put AND, OR, XOR, and then toss in a NOT rather than all their complement functions. The remaining three opcodes to be used could be addition, logical shift right, and arithmetic shift right. A bit shift left could be done by adding a number to itself, iterated if so needed. It'd be a waste to add another bit to the opcode just for a single new operation :V

Also, status register! Can't have branch instructions (and thus, conditional logic) without it.

I'll be sure to start working on it !