- Joined
- Feb 16, 2016
- Messages
- 67
- Reaction score
- 42
Target level: beginner-intermediate. It's long, that's why it's hidden in spoilers.
You are warned. Don't reply with "I knew this" or "TLDR", please. Thanks!
Counters:
Subtraction & Addition:
Resetting an FF Chain:
Comparison:
XOR Gate:
RNG:
Bonus (not 2^n counter):
EDIT: You can find the blueprint for all these at FF Chain Arithmetic
You are warned. Don't reply with "I knew this" or "TLDR", please. Thanks!
Counters:
Consider this circuit:
Yeah, this is a binary 16-counter. Probably the first time I saw it I was like 'WOW', but that was so long ago. Now I don't think it's that impressive.
Well actually, this is a reverse or backwards counter. It cycles 0000 - 1111 - 1110 - 1101 - ... - 0001 - 0000 - 1111 - ... which are binary for 0 - 15 - 14 - 13 - ... - 1 - 0 - 15 ...
Now if we change the circuit a bit:
The control input is not linked directly to the first flip-flop but to an array of AND gates. The first AND gate is fed with a 1, the rest with zeros. Activating the control input will feed the first flip-flop with a 1, the rest will be untouched. This has to behave exactly as the simple variant above, and yes it does. It seems like a sub-optimal version of the first circuit, but also looks like it now has a 4 bit input and a 4 bit state, saved in the flip-flops. If we pass 0010 to the flip-flops, the first flip-flop will maintain state because it will be fed with a 0, and the second will act as the beginning of the chain. Thus we have shortened our 16-counter to an 8-counter. The numbers it will cycle now are 0-14-12-10-..-0-14-... (if the first FF is 0) or 1-15-13-11-...-1-15-... (if the first FF is 1).
In other words -- it will subtract 2 from the value stored in the chain. The same is valid for the other two inputs. It will subtract 4 and 8 respectively. Will it subtract any 4 bit int? Like 5 (0101)? Yes it will. It will cycle: 0-11-6-1-12-7-2-13-8-3-14-9-4-15-10-5-0-...
Thus aligning the inputs in a little more complex way our backwards counter became a subtracting thingy. And this is valid for any chain length (8 bit, 16 bit, any-bit).
Yeah, this is a binary 16-counter. Probably the first time I saw it I was like 'WOW', but that was so long ago. Now I don't think it's that impressive.
Well actually, this is a reverse or backwards counter. It cycles 0000 - 1111 - 1110 - 1101 - ... - 0001 - 0000 - 1111 - ... which are binary for 0 - 15 - 14 - 13 - ... - 1 - 0 - 15 ...
Now if we change the circuit a bit:
The control input is not linked directly to the first flip-flop but to an array of AND gates. The first AND gate is fed with a 1, the rest with zeros. Activating the control input will feed the first flip-flop with a 1, the rest will be untouched. This has to behave exactly as the simple variant above, and yes it does. It seems like a sub-optimal version of the first circuit, but also looks like it now has a 4 bit input and a 4 bit state, saved in the flip-flops. If we pass 0010 to the flip-flops, the first flip-flop will maintain state because it will be fed with a 0, and the second will act as the beginning of the chain. Thus we have shortened our 16-counter to an 8-counter. The numbers it will cycle now are 0-14-12-10-..-0-14-... (if the first FF is 0) or 1-15-13-11-...-1-15-... (if the first FF is 1).
In other words -- it will subtract 2 from the value stored in the chain. The same is valid for the other two inputs. It will subtract 4 and 8 respectively. Will it subtract any 4 bit int? Like 5 (0101)? Yes it will. It will cycle: 0-11-6-1-12-7-2-13-8-3-14-9-4-15-10-5-0-...
Thus aligning the inputs in a little more complex way our backwards counter became a subtracting thingy. And this is valid for any chain length (8 bit, 16 bit, any-bit).
Adding some extra wiring, we can turn the subtracting chain into a working subtracting unit:
(Yes. it doesn't seem simple. On the top floor A is entered into an FF chain to get its complement. The complement is injected in the bottom level chain where it's converted back to A. In the bottom level input B is entered into the bottom chain. As a result the bottom chain contains A-B, indicated by the lights. In this case: 6-1 = 5. On the right side there is some delayed wiring to make this happen with a single click. The result is ready within 3 ticks or 1.5s)
How can we make the chain to act as an adder? First lets make it a forward counter. If we feed 1 to 0 we get 15. So 0-1 = 15. This is because we work with 4-bit numbers only. In other words: all our numbers are modulo 16 (2^4). 15 could be interpreted as -1 when in mod 16.
So if we subtract not 1 (0001) but 15 (1111) we will have X =X-15 = X-(-1) = X+1. The chain will cycle: 0-1-2-... -15-0-1-... (We could interpret the example with the step 5 reverse counter as an 11-adder, since 5 is the 2's complement of 11 because 11+5 = 16).
In other words, if we want to use our subtracting chain as an adder, we have to input not the number we want to add, but it's 4 bit 2's complement. Note that the length of the chain here matters: the 2's complement of one in 8 bits is 255 (1111 1111), not 15 (0000 1111). That's because 255 = 2^8-1.
Side note: in any bit length the 2's complement of one is a string of 1s only.
To find the 2's complement Y of any X (X>=0 & X<16): take the inverse bits of X and add 1 to the result. For X=5: 5=0101; inv(5)=1010; inv(5)+1 = 1011 = 11 = Y. (In 8 bits that would give 1111 1011 = 251.)
Doesn't seem very easy at all. But also Y = 16-X = -X (mod 16). And we already can subtract modulo 16: simply take a zeroed chain and feed it with X. The chain will contain 0-X = 16-X (or 2^n-X for n bits) which is the 2's complement of X. The output of this chain could be fed to another chain to perform addition.
(I'm not posting an image here, because it starts to get horrifying at first glance. Wait a little for a more classic adder.)
(Yes. it doesn't seem simple. On the top floor A is entered into an FF chain to get its complement. The complement is injected in the bottom level chain where it's converted back to A. In the bottom level input B is entered into the bottom chain. As a result the bottom chain contains A-B, indicated by the lights. In this case: 6-1 = 5. On the right side there is some delayed wiring to make this happen with a single click. The result is ready within 3 ticks or 1.5s)
How can we make the chain to act as an adder? First lets make it a forward counter. If we feed 1 to 0 we get 15. So 0-1 = 15. This is because we work with 4-bit numbers only. In other words: all our numbers are modulo 16 (2^4). 15 could be interpreted as -1 when in mod 16.
So if we subtract not 1 (0001) but 15 (1111) we will have X =X-15 = X-(-1) = X+1. The chain will cycle: 0-1-2-... -15-0-1-... (We could interpret the example with the step 5 reverse counter as an 11-adder, since 5 is the 2's complement of 11 because 11+5 = 16).
In other words, if we want to use our subtracting chain as an adder, we have to input not the number we want to add, but it's 4 bit 2's complement. Note that the length of the chain here matters: the 2's complement of one in 8 bits is 255 (1111 1111), not 15 (0000 1111). That's because 255 = 2^8-1.
Side note: in any bit length the 2's complement of one is a string of 1s only.
To find the 2's complement Y of any X (X>=0 & X<16): take the inverse bits of X and add 1 to the result. For X=5: 5=0101; inv(5)=1010; inv(5)+1 = 1011 = 11 = Y. (In 8 bits that would give 1111 1011 = 251.)
Doesn't seem very easy at all. But also Y = 16-X = -X (mod 16). And we already can subtract modulo 16: simply take a zeroed chain and feed it with X. The chain will contain 0-X = 16-X (or 2^n-X for n bits) which is the 2's complement of X. The output of this chain could be fed to another chain to perform addition.
(I'm not posting an image here, because it starts to get horrifying at first glance. Wait a little for a more classic adder.)
Flip-flops maintain state and if chained one can trigger the next. Try to reset manually an FF chain and you'll see it's not very easy. There is a simple automatic solution though: if the chain contains X and you feed it with X it should contain X-X = 0. To feed a chain automatically with its state use this:
(all the top AND gates are two way linked to the corresponding flip-flops. The top input is connected to all ANDs)
When you activate the top input, the state of each flip-flop will 'bounce' back to the flip-flop. Zeros will not be changed, ones will toggle and become zeros.
(all the top AND gates are two way linked to the corresponding flip-flops. The top input is connected to all ANDs)
When you activate the top input, the state of each flip-flop will 'bounce' back to the flip-flop. Zeros will not be changed, ones will toggle and become zeros.
Sometimes it's required to compare two binary numbers. Let our numbers X and Y are 4 bit (between 0 and 15 incl.). First, we will add a leading 0 to both thus converting them to 5 bit integers (0-31 incl.). We will feed a 5 long FF chain with them to get the X-Y result. If the result has 1 as it's highest (5th) bit, then Y is greater than X. Example: X=11 (0 1011), Y = 14 (0 1110). X-Y = -3 which has a 5 bit two's complement of 32-3 = 29 = 1 1101. In other words: to have signed 4 bit numbers, we add a 5th bit, which is 0 for positive and 1 for negative. Thus -X (X is 4 bit) is actually the 5 bit long two's complement of X. 16 (1 0000) is the same as its 5 bit complement. For consistency with the sign nature of the highest bit, the mask 1 0000 is interpreted as -16.
Lots of people want to have a separate XOR block in Starmade. XOR returns 1 if an odd number of inputs is 1 and 0 for an even number. In the case of 2 inputs: 01 and 10 return 1, 00 and 11 return 0. To create an XOR gate in Starmade one needs 2 NOR gates, 2 AND gates and an OR gate. And that is for the 2 argument XOR only. Each additional input adds a NOR gate and doubles the number of AND gates.
XOR is a rather useful gate. It could be used to check two signals for equality: in the case of 2 inputs, XOR returns 1 if they are different and 0 if they are equal. Also XOR is useful for addition and subtraction. A two bit adder is a parallel combo of an XOR and an AND gate: the XOR gate will return the result bit, the AND gate will return the carry (overflow) bit. This combo has the following truth table:
00 -> 00
01 -> 01
10 -> 01
11 -> 11
and looks like this:
To add two 4 bit numbers one will need an XOR gate for the least significant bit and two gates per each other bit for a total of 7 XOR gates. Or a battery of 4 units like the above. That's because to get the Ith bit properly, one needs to see if there is an overflow from the (I-1)th bit. In other words: to add 2 binary numbers with XOR gates, one will need to bitwise XOR 3 numbers: the two inputs and one intermediate 'overflow' number.
The full 4 bit adder looks like this:
(Here we have 11 + 2 = 13, as indicated by the lights behind.)
We have seen that to achieve addition/subtraction we don't need any XOR gates at all. Just a simple chain of flip-flops. Can we totally replace the XOR gate with a flip-flop? The XOR gate behaves similarly to the flip-flop. Just like the FF toggles state when an input becomes from 0 to 1, the XOR gate toggles output on toggling ANY of it's inputs. To achieve this, we need to feed the inputs of a flip-flop through AND gates and a Control/Clock input (like our FF chains, but all inputs go to a single FF). Since the FF keeps state, we have to bounce it's state back before operation. Thus to have a N-input XOR gate requires N+1 AND gates (for all the inputs + bounce) and a control input. On activating the control input, the FF will display 1 if an odd number of inputs are on and 0 if an even number of inputs are on.
NOTE: this seems like an exploit and could be fixed in upcoming versions.
( 4 input XOR, control button in the bottom.)
XOR is a rather useful gate. It could be used to check two signals for equality: in the case of 2 inputs, XOR returns 1 if they are different and 0 if they are equal. Also XOR is useful for addition and subtraction. A two bit adder is a parallel combo of an XOR and an AND gate: the XOR gate will return the result bit, the AND gate will return the carry (overflow) bit. This combo has the following truth table:
00 -> 00
01 -> 01
10 -> 01
11 -> 11
and looks like this:
To add two 4 bit numbers one will need an XOR gate for the least significant bit and two gates per each other bit for a total of 7 XOR gates. Or a battery of 4 units like the above. That's because to get the Ith bit properly, one needs to see if there is an overflow from the (I-1)th bit. In other words: to add 2 binary numbers with XOR gates, one will need to bitwise XOR 3 numbers: the two inputs and one intermediate 'overflow' number.
The full 4 bit adder looks like this:
(Here we have 11 + 2 = 13, as indicated by the lights behind.)
We have seen that to achieve addition/subtraction we don't need any XOR gates at all. Just a simple chain of flip-flops. Can we totally replace the XOR gate with a flip-flop? The XOR gate behaves similarly to the flip-flop. Just like the FF toggles state when an input becomes from 0 to 1, the XOR gate toggles output on toggling ANY of it's inputs. To achieve this, we need to feed the inputs of a flip-flop through AND gates and a Control/Clock input (like our FF chains, but all inputs go to a single FF). Since the FF keeps state, we have to bounce it's state back before operation. Thus to have a N-input XOR gate requires N+1 AND gates (for all the inputs + bounce) and a control input. On activating the control input, the FF will display 1 if an odd number of inputs are on and 0 if an even number of inputs are on.
NOTE: this seems like an exploit and could be fixed in upcoming versions.
( 4 input XOR, control button in the bottom.)
If we had a native XOR gate, it would operate instantly. Unfortunately this is not the case with flip-flops. They need resetting, some time to wait for all that flipping and flopping. Sometimes this 'parasite' state kept in the chain could come handy. Like in stack structures: it will keep the stack pointer which you can easily move up (with 1111...11) or down (with 000...01) or even with any amount, like and additional offset input.
Another useful feature are the PRNGs: pseudo-random number generators (and more specifically: Linear Congruential PRNGs)
An LCPRNG returns the next pseudo-random X(i+1) using the following formula:
X(i+1) = (A*X(i) + C) mod M,
based on the value of the previous X(i); A, C and M are constants, 0<A<M & 0<C<M.
These RNGs are not very good, especially for small bit lengths. To achieve best results:
1. M,A and C should be relatively prime. (Easy to achieve: Let M be 2^n, A be odd and C be prime);
2. A-1 should be divisible by all prime factors of M (Let A be 2^k+1, k<n).
3. A-1 should be divisible by 4 if M is divisible by 4 (that's ok, if k>=2).
Our FF chains do automatic modulo 2^n, addition is OK, the previous number is natively stored. How to achieve multiplication? For 4 bits we have M = 16 (2^4). Let A be 9 (not a good choice, but will do). For any X:
X*9 = X*8 + X = X<<3 + X
(<<3 meaning bitwise left shift)
In the case of a 4 bit X this means: add the lowest bit to the highest and keep the rest. In other words: feed the highest bit with the lowest, keep the rest. Well, 'feeding' for FF chains mean subtraction, but 1 bit addition and subtraction are equal modulo 2. For C we can pick any odd number, not divisible by 3, and we will store its complement in the inputs constantly.
A=9 is a poor choice, because it scrambles only 1 bit. If we choose 5 (X<<2 + X), then we have to feed the 3rd with the 1st and the 4th with the 2nd. Which would produce a better scramble, but requires the 2 bit complement of the 1st and 2nd bits. These would require an additional XOR gate for instant calculation or a short FF chain if time is not critical.
Thus we have built a 4 bit LCPRNG. In our case, it will move through each number between 0 and 16 and it will repeat cycling them in the same order.
LCPRNGs of this type have a max period of M. If we use 8 bits, M (and the period) will be 256, A could be 129 (X<<7+X feed the last with the first, keep others). 129 = 3*43, so any odd C, not divisible by 3 and 43 would do.
Or A could be 65: X<<6+X: feed the 8th with the first two XORed, feed the 7th with the first one, keep the rest. In the case of 65 we have to avoid odd multiples of 5 and 13 for C.
In both RNGs above C is 149 which is prime. It's complement is input via the activation blocks. In the second case example (with A=65), pairs of output bits are additionally XORed to create an non-uniform 4 bit RNG. This RNG however has much greater period than 16.
Another useful feature are the PRNGs: pseudo-random number generators (and more specifically: Linear Congruential PRNGs)
An LCPRNG returns the next pseudo-random X(i+1) using the following formula:
X(i+1) = (A*X(i) + C) mod M,
based on the value of the previous X(i); A, C and M are constants, 0<A<M & 0<C<M.
These RNGs are not very good, especially for small bit lengths. To achieve best results:
1. M,A and C should be relatively prime. (Easy to achieve: Let M be 2^n, A be odd and C be prime);
2. A-1 should be divisible by all prime factors of M (Let A be 2^k+1, k<n).
3. A-1 should be divisible by 4 if M is divisible by 4 (that's ok, if k>=2).
Our FF chains do automatic modulo 2^n, addition is OK, the previous number is natively stored. How to achieve multiplication? For 4 bits we have M = 16 (2^4). Let A be 9 (not a good choice, but will do). For any X:
X*9 = X*8 + X = X<<3 + X
(<<3 meaning bitwise left shift)
In the case of a 4 bit X this means: add the lowest bit to the highest and keep the rest. In other words: feed the highest bit with the lowest, keep the rest. Well, 'feeding' for FF chains mean subtraction, but 1 bit addition and subtraction are equal modulo 2. For C we can pick any odd number, not divisible by 3, and we will store its complement in the inputs constantly.
A=9 is a poor choice, because it scrambles only 1 bit. If we choose 5 (X<<2 + X), then we have to feed the 3rd with the 1st and the 4th with the 2nd. Which would produce a better scramble, but requires the 2 bit complement of the 1st and 2nd bits. These would require an additional XOR gate for instant calculation or a short FF chain if time is not critical.
Thus we have built a 4 bit LCPRNG. In our case, it will move through each number between 0 and 16 and it will repeat cycling them in the same order.
LCPRNGs of this type have a max period of M. If we use 8 bits, M (and the period) will be 256, A could be 129 (X<<7+X feed the last with the first, keep others). 129 = 3*43, so any odd C, not divisible by 3 and 43 would do.
Or A could be 65: X<<6+X: feed the 8th with the first two XORed, feed the 7th with the first one, keep the rest. In the case of 65 we have to avoid odd multiples of 5 and 13 for C.
In both RNGs above C is 149 which is prime. It's complement is input via the activation blocks. In the second case example (with A=65), pairs of output bits are additionally XORed to create an non-uniform 4 bit RNG. This RNG however has much greater period than 16.
One could use the techniques described to create a counter which doesn't have a period of 2^n. On any tick compare the current value with the counter limit using bitwise XOR. If the current value equals the limit, reset the counter back to zero
(A forward counter fed with 1111. On reaching 5 = 0101 being the max value, it's reset by subtracting 6 = 0110)
(A forward counter fed with 1111. On reaching 5 = 0101 being the max value, it's reset by subtracting 6 = 0110)
EDIT: You can find the blueprint for all these at FF Chain Arithmetic
Last edited:
