Binary decoder

Post pictures and videos of your factories.
If possible, please post also the blueprints/maps of your creations!
For art/design etc. you can go to Fan Art.

piriform
Fast Inserter
Fast Inserter
Posts: 117
Joined: Mon Jan 25, 2016 10:02 pm
Contact:

Binary decoder

Post by piriform »

I'm trying do so some work with boo lean operations in Factorio, and of course the first thing to do is design a binary decoder.
Well, this is my stab at it.


The picture shows an 8 bit decoder capable of translating 0-255.
Description of operation
-each bit is translated by a row of 4 (except msb) combinators. Bit 8 is on top, Bit 1 on the bottom.
-data enters on a green wire to the divider. Carry (from above) is subtracted from input and divided by -2^(n-1) (for bit 8 that would be -2^7 =-128)
-the result is fed to a decider that looks for anything <0. If that is true, decider will generate an appropriate bit ( e.g. "8"=1),
-combinator to the right of the divider generates the carry by multiplying result by 2^(n-1)
-the carry is then propagated to the lower bits via adder on the left.
So the good, the bad and the ugly
The good part is it works
The bad part is it's slow. The ripple carry is brutal (on the order of 3n ticks)
The ugly part, apart from the size, it''s really slow (almost 1/2 second for 8 bits?)
If there is any interest I'll be happy to post the blueprint, although I would not recommend it for anything but a quasi static application.
On the other hand, if anyone knows of a really clever way of doing it with say 10 combinators in 2-3 ticks, I'm all ears.

---------------------------------------------------------------------------------------------------------------------------------------------------------------
PS

Poor Decoder has gone through a lot. From a slow,flabby kid he's become something
If you want to know the real story please click the spoiler. read. Otherwise skip to the end and look at the pictures (sorry I couldn't spoiler the text)

Decoders Tale
Attachments
Original
Original
binarydecoder1.gif (252.53 KiB) Viewed 40700 times
Second Pass
Second Pass
Binarydecoder2.gif (289.08 KiB) Viewed 40700 times
Third Version
Third Version
xkdecoder3.gif (52.84 KiB) Viewed 40700 times
Last edited by piriform on Thu Feb 25, 2016 4:15 am, edited 3 times in total.

User avatar
DaveMcW
Smart Inserter
Smart Inserter
Posts: 3699
Joined: Tue May 13, 2014 11:06 am
Contact:

Re: Binary decoder

Post by DaveMcW »

Here is a decoder for the 2^4 bit that runs in 3 ticks. You can make a similar one for the other bits and run them in parallel.

The + combinator is just a no-op that adds zero.
Attachments
binary-decoder.jpg
binary-decoder.jpg (312.3 KiB) Viewed 41070 times

piriform
Fast Inserter
Fast Inserter
Posts: 117
Joined: Mon Jan 25, 2016 10:02 pm
Contact:

Re: Binary decoder

Post by piriform »

Nice! Many thanks. I'll give it a shot ASAP.

--------------------------------------------

Here it is, 8 bits at 30 60 cps!

https://drive.google.com/file/d/0B3I2uZ ... sp=sharing
And the string
https://drive.google.com/file/d/0B3I2uZ ... sp=sharing
Thanks again!

XKnight
Filter Inserter
Filter Inserter
Posts: 329
Joined: Thu May 28, 2015 10:40 pm
Contact:

Re: Binary decoder

Post by XKnight »

Try to think out of the box... Factorio is a game and this game is inside computer, use your advantage.
1.png
1.png (307.49 KiB) Viewed 40931 times

User avatar
DaveMcW
Smart Inserter
Smart Inserter
Posts: 3699
Joined: Tue May 13, 2014 11:06 am
Contact:

Re: Binary decoder

Post by DaveMcW »

Very nice, fast modulo arithmetic using integer overflow. :)

piriform
Fast Inserter
Fast Inserter
Posts: 117
Joined: Mon Jan 25, 2016 10:02 pm
Contact:

Re: Binary decoder

Post by piriform »

I hate those "think out of the box" as I always get distracted wandering about the colour. But, OK, I'll bite if you tell me how many combinators.


-------------------------------------------------------------------------------------------------------------------------------------------------------------------------
lol. So, when is Combinators 201 coming out?
p.s. I smell BIG numbers


-------------------------------------------------------------------------------------------------------------------------------------------------------------------------
It's been a trip, but well worth it I think. Thanks for all the help.
Attachments
xkdecoder.gif
xkdecoder.gif (160.73 KiB) Viewed 40758 times

Fatmice
Filter Inserter
Filter Inserter
Posts: 808
Joined: Thu Dec 04, 2014 11:03 pm
Contact:

Re: Binary decoder

Post by Fatmice »

Does this overflow trick still work? If I am reading this decoder right, you are doing Each * Blue-square, where Each is the signal 0-B, with values 2^(32-n) where n is 1 through 12.

Thus
0 => 2147483648
1 => 1073741824
2 => 536870912
etc...
B => 1048576

Certain numbers do not display right anymore in their binary form since 2147483648 can not be put in.
Maintainer and developer of Atomic Power. See here for more information.
Current release: 0.6.6 - Requires 0.14.x
Example build - Requires 0.14.x

Neotix
Filter Inserter
Filter Inserter
Posts: 599
Joined: Sat Nov 23, 2013 9:56 pm
Contact:

Re: Binary decoder

Post by Neotix »

I tried to understand that decoder and to do that I reconstructed calculations step by step in excel.
So the combinator multiply all channels signals with input signal. When result is greater than 2^31 then INT is oveflowed and start from -2^31 (it can be overflowed multiple times). That's why some of the channels signals have negative number.
Each light have condition to light up when specific channel signal is < 1.

piriform
Fast Inserter
Fast Inserter
Posts: 117
Joined: Mon Jan 25, 2016 10:02 pm
Contact:

Re: Binary decoder

Post by piriform »

Certain numbers do not display right anymore in their binary form since 2147483648 can not be put in.
Correct, this is due to the integer definition that Factorio uses where 2^31 is the largest positive #. Decoder should work up to 2^30 (i.e. 30 bits) and maybe up to 2^31-1.
. When result is greater than 2^31 then INT is oveflowed and start from -2^31 (it can be overflowed multiple times). That's why some of the channels signals have negative number.
Exactly, those channels are of course, bits. If you look at my post on Booleans, you will see that I convert them to 1's and then do some bit manipulation.
I tried to understand that decoder and to do that I reconstructed calculations step by step in excel.
+1



PS Normally I try to post an explanation of my circuits. In this case I did not, as the circuit was invented by XKnight.

Neotix
Filter Inserter
Filter Inserter
Posts: 599
Joined: Sat Nov 23, 2013 9:56 pm
Contact:

Re: Binary decoder

Post by Neotix »

In 0.12.29 it's impossible to set 2147483648 number.

Fatmice
Filter Inserter
Filter Inserter
Posts: 808
Joined: Thu Dec 04, 2014 11:03 pm
Contact:

Re: Binary decoder

Post by Fatmice »

Neotix wrote:In 0.12.29 it's impossible to set 2147483648 number.
That was what I was saying. Thus numbers like 1, 3, 5, etc. can not be decoded correctly. 2^31 in the current version is a 0.
Maintainer and developer of Atomic Power. See here for more information.
Current release: 0.6.6 - Requires 0.14.x
Example build - Requires 0.14.x

XKnight
Filter Inserter
Filter Inserter
Posts: 329
Joined: Thu May 28, 2015 10:40 pm
Contact:

Re: Binary decoder

Post by XKnight »

Fatmice wrote:
Neotix wrote:In 0.12.29 it's impossible to set 2147483648 number.
That was what I was saying. Thus numbers like 1, 3, 5, etc. can not be decoded correctly. 2^31 in the current version is a 0.
Nope.
1.png
1.png (608.39 KiB) Viewed 34841 times
Although you can find the answer on this question in my contraptions, but I strictly recommend you to come to this answer by yourself. Otherwise you won't understand something important.

Neotix
Filter Inserter
Filter Inserter
Posts: 599
Joined: Sat Nov 23, 2013 9:56 pm
Contact:

Re: Binary decoder

Post by Neotix »

I think I get it.
Image

Fatmice
Filter Inserter
Filter Inserter
Posts: 808
Joined: Thu Dec 04, 2014 11:03 pm
Contact:

Re: Binary decoder

Post by Fatmice »

XKnight wrote:
Fatmice wrote:
Neotix wrote:In 0.12.29 it's impossible to set 2147483648 number.
That was what I was saying. Thus numbers like 1, 3, 5, etc. can not be decoded correctly. 2^31 in the current version is a 0.
Nope.
1.png
Although you can find the answer on this question in my contraptions, but I strictly recommend you to come to this answer by yourself. Otherwise you won't understand something important.
I do get what is going on, but 2^31 still can't be set directly. I assumed Piriform had set signal-0 to 2^31...maybe it was possible to do that in the past.. Maybe he set it to 2^31-1, but whatever it was the output confused me.

Anyways, the correct signal-0 is two signal-0's, one of 2^31-1, one of + 1. This gives -2^31, which will give the right overflow pattern.
Last edited by Fatmice on Thu Mar 24, 2016 9:46 pm, edited 2 times in total.
Maintainer and developer of Atomic Power. See here for more information.
Current release: 0.6.6 - Requires 0.14.x
Example build - Requires 0.14.x

User avatar
DaveMcW
Smart Inserter
Smart Inserter
Posts: 3699
Joined: Tue May 13, 2014 11:06 am
Contact:

Re: Binary decoder

Post by DaveMcW »

Fatmice wrote:Anyways, the correct signal-0 is two signal-0's, one of 2^31-1, one of + 1. This gives -2^31.
Or you could just enter -2147483648 directly. ;)

Fatmice
Filter Inserter
Filter Inserter
Posts: 808
Joined: Thu Dec 04, 2014 11:03 pm
Contact:

Re: Binary decoder

Post by Fatmice »

Meh, might just make a mistake. =P
Maintainer and developer of Atomic Power. See here for more information.
Current release: 0.6.6 - Requires 0.14.x
Example build - Requires 0.14.x

User avatar
siggboy
Filter Inserter
Filter Inserter
Posts: 988
Joined: Tue Mar 29, 2016 11:47 am
Contact:

Re: Binary decoder

Post by siggboy »

Here's another, technical, explanation for how the binary decoder by XKnight works (the design that abuses the integer overflow after adding large values):
  • Factorio combinators use signed, 32-bit integers.
  • Signed integers use "two's complement" notation to store negative values in binary.
  • Negative values have the most significant bit set to "1" (that's the bit corresponding to a value of 2^31, because we're dealing with 32-bit integers).
  • Multiplying and dividing by 2 (or powers of 2) will shift the bits in a value to the left and right (it's like multiplying and dividing by 10 in the decimal system by way of adding/removing zeroes, only in binary).
So, by repeated doubling you can shift any bit into the most significant position, and if the result is negative, you know that the original value did have a "1" in that position. Repeated doubling is the same as multiplying with a power of two, so it's easy to multiply any bit into the MSB position if you keep the needed powers of two as constants.

This is extremely quirky, although not as bad a looping combinator outputs :-). On the other hand, it's also very stable and unlikely to stop working unless the size of Factorio registers increases to 64 bits at some point.
Is your railroad worrying you? Doctor T-Junction recommends: Smart, dynamic train deliveries with combinator Magick

User avatar
siggboy
Filter Inserter
Filter Inserter
Posts: 988
Joined: Tue Mar 29, 2016 11:47 am
Contact:

Re: Binary decoder

Post by siggboy »

Fatmice wrote:I do get what is going on, but 2^31 still can't be set directly. I assumed Piriform had set signal-0 to 2^31...maybe it was possible to do that in the past.. Maybe he set it to 2^31-1, but whatever it was the output confused me.

Anyways, the correct signal-0 is two signal-0's, one of 2^31-1, one of + 1. This gives -2^31, which will give the right overflow pattern.
32-bit signed integers have a range of -2^31 to 2^31-1. This is because positive values have the most significant bit (2^31) set to zero, so the biggest positive value is 0111...111 (a 0 followed by 31 1s).

2^31 not only cannot be set "directly", it actually does not exist. 2^31 exists internally, but for us it is actually the number -2^31.

The highest value you can set manually in a combinator is 2^31-1 (which makes sense, because it's the highest value that actually fits into the combinator...). You can then add "1" to this and it will appear to, kind of, "underflow" to -2^31. In reality, no overflow happens at all (see below), but the convention that the MSB in a signed integer signifies a negative value gives you the appearance that huge overflow took place.

Nice trick of setting two signals to create an implicit sum (and "overflow"), but actually not necessary at all since you can simply set -2^31 directly. You don't have to "trick" the game into generating "2^31" for you (which doesn't exist), because for all intents and purposes "-2^31" is the value you're looking for and you can set it directly; "-2147483648" is accepted as a constant by combinators.

A case could be made for the game simply disallowing overflowing, and adding to a value of 2^31-1 would then do nothing, i.e. result in 2^31-1 again. The same for negative values in the other direction.

To be honest I'm still surprised that the game behaves like plain C and not like a safe language in this area. Somebody who only knows safe languages will probably not ever get the idea and try to abuse two's complement notation to make a bit decoder.

It's wrong to even talk about "integer overflow" in the current context (multiplying until you make the number negative), because no overflow happens. Setting the 32nd bit by way of adding 1 to 2^31-1 is not overflowing, it's a simple carry operation happening.

Overflow happens when you add -1 to -2^31, because what actually happens is that a "1" followed by 31 "0" (the number -2^31) is added to a number consisting of all 1s (the number -1):

Code: Select all

  10000000000000000000000000000000    (32 digits)
+ 11111111111111111111111111111111    (32 digits)
--------------------------------------------------
 101111111111111111111111111111111    (33 digits)
The leftmost "1" in the result above is the 33rd bit, so it does not fit into the result anymore and gets dropped. That's what's commonly known as "a register overflowing" in computer science.

After we drop that extra "1" we end up with

Code: Select all

   01111111111111111111111111111111
which is 2^31-1, the largest positive number. So by subtracting 1 from -2^31 you actually wrap around all the way to 2^31-1...
Is your railroad worrying you? Doctor T-Junction recommends: Smart, dynamic train deliveries with combinator Magick

Amegatron
Long Handed Inserter
Long Handed Inserter
Posts: 52
Joined: Sun Mar 06, 2016 4:12 am
Contact:

Re: Binary decoder

Post by Amegatron »

XKnight wrote:Try to think out of the box... Factorio is a game and this game is inside computer, use your advantage.
1.png
Still can't get it how do you manage do decode a signal using just one combinator :/ All I came to myself is chained combinator pairs, each deviding by 2 and determining whether theres is 1 left after division. This means I have 8 pairs for 8-bit decoding, also working for 8 ticks to decode the value.
Image
The first "/" combinator in row devides the incoming value by 2.
The second "*" combinator multiplies the result of previous one by -2.
Then the output then goes to the third "*" combinator which converts the signal (which is 1 or 0) into another signal, which is used as a bit for the screen e.g.
The output from first comb-r goes to the next row, chaining the division by 2 further.

EDIT: I think I got it, read carefully previous comments )

Amegatron
Long Handed Inserter
Long Handed Inserter
Posts: 52
Joined: Sun Mar 06, 2016 4:12 am
Contact:

Re: Binary decoder

Post by Amegatron »

At last I reproduced the decoder.
Image
But I met some strange thing. For first 13 signals, their value must be ((2^(31-n)) + 1), and first signal equalling -2147483647. But the rest signals must be (2^(31-n)), without additional 1. Though I could not explain why :) I noticed that while testing on different values and I also suppose there can be some incorrect decodings with these signals ...

Post Reply

Return to “Show your Creations”