Ternary circuits: R=3 is not the Optimal Radix for Computation (2019)(arxiv.org)
arxiv.org
Ternary circuits: R=3 is not the Optimal Radix for Computation (2019)
https://arxiv.org/abs/1908.06841
87 comments
The way we use transistors does not leave any room for tri-level circuits to be more efficient.
The high clock speeds we get rely on fast switching of power levels, this is generally done by targeting a voltage well beyond the switching threshold. The smallest transistors we produce generally have a big variability in amplification, they would be really bad for analogue circuitry, but in digital they just have to amplify enough, and it is ok if some of them amplify way better than that.
Now consider tri-state, we have to target a voltage in the middle band if we are to produce the middle signal, so less room for over-targeting means slower switching. We probably also need to supply the whole circuit a higher voltage to make proper room for the signal levels, that is a big L in efficiency.
One could build a circuit with three levels of input current, but that ends up more or less doubling the transistor count, so not an obvious win. I guess that is what the Setun did. If adding this complexity to a tube doesn't increase its cost much I guess that makes sense, but in the transistor world it is just a doubling.
The high clock speeds we get rely on fast switching of power levels, this is generally done by targeting a voltage well beyond the switching threshold. The smallest transistors we produce generally have a big variability in amplification, they would be really bad for analogue circuitry, but in digital they just have to amplify enough, and it is ok if some of them amplify way better than that.
Now consider tri-state, we have to target a voltage in the middle band if we are to produce the middle signal, so less room for over-targeting means slower switching. We probably also need to supply the whole circuit a higher voltage to make proper room for the signal levels, that is a big L in efficiency.
One could build a circuit with three levels of input current, but that ends up more or less doubling the transistor count, so not an obvious win. I guess that is what the Setun did. If adding this complexity to a tube doesn't increase its cost much I guess that makes sense, but in the transistor world it is just a doubling.
Well, the way we use CMOS logic is like this. But we have a bunch of other logic families inplemented with MOSFETs. Dynamic logic is seldom complementary. CML too. There's no reason to not have 3-state CML.
Ternary logic is used in data converters (Analog-to-digital and digital-to-analog) with succes. This is because these circuits are often differential, so for each 1 there is a -1 on the complementary side. Let's say it's a current steering DAC. For 1 the positive end will sink +1 unit current while negative end is sourcing +1 (effectively -1). We get -1 if we flip the positive and negative. 0 can be created by turning off the currents. The beauty of it is the 3-levels we created are inherently linear, which doesn't extend to higher bases! The DAC unit in this example is in logic terms a CML ternary inverter! It doesn't consume any power when in 0 state, so it improves CML power cobsumption too (>50% for uniform data activity).
Now we established that it is possible to implement ternary logic: why is it not used? Because CMOS logic only consumes power during transition (dynamic power) while CML consumes quite a bit higher static power always. Actually CML can work at much higher speeds but it's gobe out of fashion because Moore's law till recently gave more transistors in the same area operating faster than the previous generation. When the Moore's law is died a slow death we went for increasing the die sizes by doing more in parallel than faster logic, because for complicated reasons CMOS is quite efficient when operating much slower than the speed limits of technology. This being said, there might be areas CMOS logic can be replaced but people don't do it because they don't think about the possibility. At least this is my observation in the field.
Ternary logic is used in data converters (Analog-to-digital and digital-to-analog) with succes. This is because these circuits are often differential, so for each 1 there is a -1 on the complementary side. Let's say it's a current steering DAC. For 1 the positive end will sink +1 unit current while negative end is sourcing +1 (effectively -1). We get -1 if we flip the positive and negative. 0 can be created by turning off the currents. The beauty of it is the 3-levels we created are inherently linear, which doesn't extend to higher bases! The DAC unit in this example is in logic terms a CML ternary inverter! It doesn't consume any power when in 0 state, so it improves CML power cobsumption too (>50% for uniform data activity).
Now we established that it is possible to implement ternary logic: why is it not used? Because CMOS logic only consumes power during transition (dynamic power) while CML consumes quite a bit higher static power always. Actually CML can work at much higher speeds but it's gobe out of fashion because Moore's law till recently gave more transistors in the same area operating faster than the previous generation. When the Moore's law is died a slow death we went for increasing the die sizes by doing more in parallel than faster logic, because for complicated reasons CMOS is quite efficient when operating much slower than the speed limits of technology. This being said, there might be areas CMOS logic can be replaced but people don't do it because they don't think about the possibility. At least this is my observation in the field.
So you suggest transferring a trit using 3 wires. Wires for data transfer already take up a tremendous amount of space in a lot of CMOS logic.
The primary point of CML is that a differential signal is interference resistant. Therefore it can be used for higher data rates in out-of-chip buses. It does not provider faster ALUs than CMOS.
The primary point of CML is that a differential signal is interference resistant. Therefore it can be used for higher data rates in out-of-chip buses. It does not provider faster ALUs than CMOS.
CML is mainly used for the speed. In a dense logic circuit interference doesn't matter that much since local routing is short. For the high speed clock generation (not only routing) and logic of high frequency data converters it's used because you can get 3-4x more speed compared to CMOS logic. If the Operation frequency is so high it's worth to switching to CML. That being said, my expertise isn't in ALU design but in data converter design for chip-to-chip interconnect. So you might be right that it doesn't result in a faster ALU for whatever other reason. I'd love to know why though.
CMOS logic can also be differentially routed, and often is routed against interference. That + a full shield around sensitive routing like clock lines are standard practice. Both have the advantage of cobtaining the return current too.
I'm not suggesting we switch to 3 wires for ternary. That would be stupid. Ternary CML is 2 wires. 10, 00, 01 with 11 being the forbidden state or having the same functionality of 00. This isn't efficient from routing perspective compared to single-ended CMOS.
For large routing distances any kind of encoding can be used. I often use 2 dimensional (row-column) encoding/decoding for multi-GHz data busses travelling over long distances (like 500um to couple of mm). It's very easy to calculate the power cost and routing area cost of not using any emcoding with respect to doing an n-dimensional encoding (incl. the power and area of encoder/decoder). I even used a 3D encoding which reduced total routing channel area and power in a routing dense setup like 50%. Using a simple kind of coding like parity bit and multiplying the data with a random sequence is also used against interference but people often don't do this and regret it..
Anyhow, the point I'm trying to make is local logic and long distance routing are two problems with different optimization parameters.
CMOS logic can also be differentially routed, and often is routed against interference. That + a full shield around sensitive routing like clock lines are standard practice. Both have the advantage of cobtaining the return current too.
I'm not suggesting we switch to 3 wires for ternary. That would be stupid. Ternary CML is 2 wires. 10, 00, 01 with 11 being the forbidden state or having the same functionality of 00. This isn't efficient from routing perspective compared to single-ended CMOS.
For large routing distances any kind of encoding can be used. I often use 2 dimensional (row-column) encoding/decoding for multi-GHz data busses travelling over long distances (like 500um to couple of mm). It's very easy to calculate the power cost and routing area cost of not using any emcoding with respect to doing an n-dimensional encoding (incl. the power and area of encoder/decoder). I even used a 3D encoding which reduced total routing channel area and power in a routing dense setup like 50%. Using a simple kind of coding like parity bit and multiplying the data with a random sequence is also used against interference but people often don't do this and regret it..
Anyhow, the point I'm trying to make is local logic and long distance routing are two problems with different optimization parameters.
> a bit like using the number of fingers we have to argue that decimal is the best number system to work in.
Fun fact unrelated to your main point: some ancient peoples counted on their knuckles, using their thumb to point to each one. This let them count in multiples of 12 (3 knuckles on each of 4 fingers), then use their other hand to count out multiples! You can count as high as 72 this way, which was great for ancient cultures oriented around highly composite numbers like 12, 24, and 60.
Fun fact unrelated to your main point: some ancient peoples counted on their knuckles, using their thumb to point to each one. This let them count in multiples of 12 (3 knuckles on each of 4 fingers), then use their other hand to count out multiples! You can count as high as 72 this way, which was great for ancient cultures oriented around highly composite numbers like 12, 24, and 60.
I like to believe this is true because it makes sense, but it was a theory invented in the 20th century to try to explain how they did math in everyday settings. We don’t actually know if it is true. We just know that they used base-60 systems.
Yeah, 60 was likely used because it divides by 2,3,4,5,6 and 10, 12 and 15. I imagine it makes dealing with fractions much easier.
Oh, good to know!
> some ancient peoples counted on their knuckles, using their thumb to point to each one.
I don’t know how “ancient” you’re talking about: my mother (b. 1937) used such a system and taught it to us as kids. FWIW she grew up in south east Asia.
I don’t know how “ancient” you’re talking about: my mother (b. 1937) used such a system and taught it to us as kids. FWIW she grew up in south east Asia.
Can’t you count as high as 156?
12 knuckles/finger segments, incrementing by 1 on the left hand for each completed counting of 12 on the right = 12 * 12 + 12 = 144 + 12
I may have misunderstood the proposed counting method however.
12 knuckles/finger segments, incrementing by 1 on the left hand for each completed counting of 12 on the right = 12 * 12 + 12 = 144 + 12
I may have misunderstood the proposed counting method however.
I mean, even without knuckles you have 10 bits to play with. If you also curl your toes, that's 12 bits. So an average person could count to 4095.
I actually figured out how to count up in binary on my fingers and you can get way higher if you use your thumbs for the lowest two bits, and bent fingers as bits differentiated from a fully extended finger. All the way to 262,143.
A variable resistor has only 2 values where the power dissipation becomes negligible, when the resistance is null or infinite.
Therefore any transistor, triode or any other controllable device has only 2 states, i.e. on and off, where the power consumption is negligible.
Any kind of logic circuits that use transistors or triodes that stay in any other intermediate states between on and off (like in analog circuits) would consume too much power and would overheat. A MOSFET can have any intermediate state between on and off, the current through it can be varied continuously as a function of the gate voltage, but it will dissipate a great amount of power in any of the intermediate states. There is no difference from this point of view between MOSFETs and vacuum tubes. Setun just had too few and too big vacuum tubes to worry about the power consumption.
The kinds of logic circuits where not all transistors or triodes are on or off have been abandoned 40 years ago and there is no chance for them to ever come back, because at the current component densities their power consumption would be enormous.
The only way to use devices with more than 2 states in logic circuits would be to use devices with a variable reactance, for instance varicap diodes, because those do not consume active power.
However the devices with controllable reactance cannot use DC power supplies, they need AC power supplies, which creates a lot of problems for which there are no known solutions at this time, so nobody has designed yet a complex logic circuit based on controllable reactances instead of transistors.
As long as electronic devices with DC power supplies will be used, binary logic is the only kind of logic permitted by the energetic constraints.
Only in the non-volatile flash memories, multiple values of electric charge can be stored in a capacitor, because it does not consume any power for storage.
Therefore any transistor, triode or any other controllable device has only 2 states, i.e. on and off, where the power consumption is negligible.
Any kind of logic circuits that use transistors or triodes that stay in any other intermediate states between on and off (like in analog circuits) would consume too much power and would overheat. A MOSFET can have any intermediate state between on and off, the current through it can be varied continuously as a function of the gate voltage, but it will dissipate a great amount of power in any of the intermediate states. There is no difference from this point of view between MOSFETs and vacuum tubes. Setun just had too few and too big vacuum tubes to worry about the power consumption.
The kinds of logic circuits where not all transistors or triodes are on or off have been abandoned 40 years ago and there is no chance for them to ever come back, because at the current component densities their power consumption would be enormous.
The only way to use devices with more than 2 states in logic circuits would be to use devices with a variable reactance, for instance varicap diodes, because those do not consume active power.
However the devices with controllable reactance cannot use DC power supplies, they need AC power supplies, which creates a lot of problems for which there are no known solutions at this time, so nobody has designed yet a complex logic circuit based on controllable reactances instead of transistors.
As long as electronic devices with DC power supplies will be used, binary logic is the only kind of logic permitted by the energetic constraints.
Only in the non-volatile flash memories, multiple values of electric charge can be stored in a capacitor, because it does not consume any power for storage.
> Only in the non-volatile flash memories, multiple values of electric charge can be stored in a capacitor, because it does not consume any power for storage.
DRAM also uses a capacitor to store data so it could support more than one bit per cell too.
DRAM also uses a capacitor to store data so it could support more than one bit per cell too.
That is unlikely to work because the DRAM capacitor is lossy, the charge stored in it diminishes quickly and soon it would become impossible to guess which was the initial value of the charge.
Using multiple values for the stored charge would force a drastic reduction in the refresh time, which would increase the power consumption and diminish the read/write throughput.
Using multiple values for the stored charge would force a drastic reduction in the refresh time, which would increase the power consumption and diminish the read/write throughput.
> From memory the Setun used vacuum tubes which could natively handle three states at the hardware level.
That was the original intent, but they could never make it work reliably. The machine that ran had all the ternary logic implemented on top of the usual binary circuits (effectively wasting one state out of four).
That was the original intent, but they could never make it work reliably. The machine that ran had all the ternary logic implemented on top of the usual binary circuits (effectively wasting one state out of four).
Seems pretty relevant to me, based on the fact that transistors in switching mode are so superior to other computing technologies (see sibling comment for explanation of why) that all computers in recent decades are using it exclusively. And for those, paper's conclusions are valid.
A paper about high efficiency tri-level logic cell which is cheap and energy-efficient would be very interesting but sadly I don't think this is possible, at least I haven't seen one nor even have a clue about how one would go about making one. And I have been watching this area with interest.
A paper about high efficiency tri-level logic cell which is cheap and energy-efficient would be very interesting but sadly I don't think this is possible, at least I haven't seen one nor even have a clue about how one would go about making one. And I have been watching this area with interest.
A bit (trit?) of background: https://web.williams.edu/Mathematics/sjmiller/public_html/10...
I'd be curious whether the same result holds for balanced ternary, as used in some early Soviet computers. https://en.wikipedia.org/wiki/Balanced_ternary
I'd be curious whether the same result holds for balanced ternary, as used in some early Soviet computers. https://en.wikipedia.org/wiki/Balanced_ternary
It doesn't matter what the voltage levels represent ([-1,0,1] in balanced ternary or [0,1,2] in "normal" ternary). The only thing that matters is that you're working with 3 voltage levels instead of 2, which as the paper shows increases the circuit complexity above the "break even" point of log(3)/log(2).
The paper shows that a worse implementation is possible, sure. It's not obvious that it shows that a better implementation is impossible. Logic tells us that these are very different things, and the latter is vastly harder than the former.
I did notice the paper hinging on a lot of implementation details. For one, they only propose using voltage dropping resistors, but no discussion of having three power rails (eg +1, 0, -1), or some hybrid approach. Maybe some part of power regulation belongs outside the chip, folks!
They also implement a ternary adder by.... converting it back and forth to binary! They justify this by saying this is the only way to implement an "arbitrary" truth table. Okay. You don't need an arbitrary table, just one! The truth table, of course, depends on the choice of balanced vs. unbalanced. This seems like an unforced error.
The paper's result (if confirmed) might indeed hold for balanced ternary, but it's not immediately clear that this is a trivial extension of the existing paper.
I did notice the paper hinging on a lot of implementation details. For one, they only propose using voltage dropping resistors, but no discussion of having three power rails (eg +1, 0, -1), or some hybrid approach. Maybe some part of power regulation belongs outside the chip, folks!
They also implement a ternary adder by.... converting it back and forth to binary! They justify this by saying this is the only way to implement an "arbitrary" truth table. Okay. You don't need an arbitrary table, just one! The truth table, of course, depends on the choice of balanced vs. unbalanced. This seems like an unforced error.
The paper's result (if confirmed) might indeed hold for balanced ternary, but it's not immediately clear that this is a trivial extension of the existing paper.
Better url for the Hayes article: https://www.americanscientist.org/article/third-base
Note that this paper does not mention balanced ternary and only presents tables, diagrams and results for unbalanced ternary with values 0, 1 and 2.
The Setun computer, mentioned in the introduction, however, used balanced ternary with values -1, 0 and 1. Balanced odd bases consist of digits centered around zero.
Could balanced ternary redeem it's position with logic cirtuits in mind?
The Setun computer, mentioned in the introduction, however, used balanced ternary with values -1, 0 and 1. Balanced odd bases consist of digits centered around zero.
Could balanced ternary redeem it's position with logic cirtuits in mind?
Trits in Setun were ultimately implemented using 2 bits with the state (1,1) going unused.
Using positive and negative voltages to represent balanced ternary requires both positive and negative power supply. They do mention that having additional Vcc is problematic. At least on our 2D chips, but we don't have any high density integration alternative, vacuum tubes are irrelevant.
Yeah, I mean until we have ternary transistors, emulating ternary circuits will be less efficient than actual binary circuits. If we ever have ternary transistors, then ternary circuits will be an improvement over binary ones.
Here's a little ternary logic riddle for the HN community:
Two people are sitting at a restaurant, deciding what to order. Neither had communicated with one another when the waiter appears and asks one of them "Is everyone ready to order?". They reply "Hm, I don't know". The other person immediately then says "Now we are." Why?
(As in, how did the second person know?)
Here's a little ternary logic riddle for the HN community:
Two people are sitting at a restaurant, deciding what to order. Neither had communicated with one another when the waiter appears and asks one of them "Is everyone ready to order?". They reply "Hm, I don't know". The other person immediately then says "Now we are." Why?
(As in, how did the second person know?)
Spoiler:
If the first person did not want to eat, he would have answered "No, we are not ready". Him not being ready is enough to negate the whole thing. He doesn't know if the both of them are ready to eat though, because he doesn't know that the second man is ready or not (the second man hasn't revealed his state yet).
Therefore, the second man knows that the first is ready to eat, since the first's answer is "I don't know". Since the second man knows that he himself is ready to eat, he can answer: "we are both ready to eat".
If the first person did not want to eat, he would have answered "No, we are not ready". Him not being ready is enough to negate the whole thing. He doesn't know if the both of them are ready to eat though, because he doesn't know that the second man is ready or not (the second man hasn't revealed his state yet).
Therefore, the second man knows that the first is ready to eat, since the first's answer is "I don't know". Since the second man knows that he himself is ready to eat, he can answer: "we are both ready to eat".
Person A does not know because they don't whether Person B is ready. If Person A was not ready themselves they would know the answer is No. We assume here that people know wherher they themselves are ready.
Person B then can safely assume Person A is ready and if they are ready themselves they are now indeed ready.
Person B then can safely assume Person A is ready and if they are ready themselves they are now indeed ready.
If the first person was not ready to order, he would know that everyone is not ready to order. Since he doesn’t know, that means he is ready to order, but is not aware of the second person readiness.
So the second person knows that the first person is ready
So the second person knows that the first person is ready
Added fun: This riddle can be generalized to N people sitting at a restaurant :)
O haha, yeah, that one is super mind bending. I heard a riddle that used that trick once about people being able to leave an island when they know what their eye color is. It's super cool because it feels like you're basically embedding memory into a purely logical expression, since you're allowed to assume that all the islanders (or in the case above, diners) are perfectly logical, and therefore by logic alone a counter of sorts emerges.
Not sure if I explained that part well, but I can write the riddle somewhere and share it one day, since it needs to be explained more precisely to demonstrate this N-people effect.
Not sure if I explained that part well, but I can write the riddle somewhere and share it one day, since it needs to be explained more precisely to demonstrate this N-people effect.
That assumes person A has figured out if person A is ready, and assuming that is not a good idea in the real world.
It also assumes they're directly answering the question instead of indirectly answering it.
It also assumes they're directly answering the question instead of indirectly answering it.
> That assumes person A has figured out if person A is ready
Not sure I understand that. Did you mean it assumes that person B has figured out that person A is ready?
Not sure I understand that. Did you mean it assumes that person B has figured out that person A is ready?
I didn't have a typo. Also I'm going to use names now because letters are hard to read.
The way Bob found out that Alice was ready was because Alice was uncertain about group readiness.
Maybe Alice was uncertain because she knew her own readiness but not Bob's readiness. This is the way the riddle works.
But maybe Alice wasn't sure of her own readiness. In that case Bob should not answer.
-
And, second issue, what if Alice was saying "Hm, I don't know [what to pick]." as a way to tell the waiter that no, everyone is not ready.
The way Bob found out that Alice was ready was because Alice was uncertain about group readiness.
Maybe Alice was uncertain because she knew her own readiness but not Bob's readiness. This is the way the riddle works.
But maybe Alice wasn't sure of her own readiness. In that case Bob should not answer.
-
And, second issue, what if Alice was saying "Hm, I don't know [what to pick]." as a way to tell the waiter that no, everyone is not ready.
> But maybe Alice wasn't sure of her own readiness
I'm not sure I understand how Alice could be unsure of her own readiness. If she's not ready, then she would have said "no, everybody is not ready to order."
> And, second issue, what if Alice was saying "Hm, I don't know [what to pick]." as a way to tell the waiter that no, everyone is not ready.
Because the riddle is "how did he [Bob] know?". We are told from the start that Bob is right, and asked to explain why.
I'm not sure I understand how Alice could be unsure of her own readiness. If she's not ready, then she would have said "no, everybody is not ready to order."
> And, second issue, what if Alice was saying "Hm, I don't know [what to pick]." as a way to tell the waiter that no, everyone is not ready.
Because the riddle is "how did he [Bob] know?". We are told from the start that Bob is right, and asked to explain why.
> I'm not sure I understand how Alice could be unsure of her own readiness. If she's not ready, then she would have said "no, everybody is not ready to order."
You don't understand how someone can be unsure if they're ready? Have you never been kind of anxious or indecisive before? (The answer is definitely not "you're not ready until the anxiety and indecision are gone".)
> Because the riddle is "how did he [Bob] know?". We are told from the start that Bob is right, and asked to explain why.
There's a reason I said "in the real world".
You don't understand how someone can be unsure if they're ready? Have you never been kind of anxious or indecisive before? (The answer is definitely not "you're not ready until the anxiety and indecision are gone".)
> Because the riddle is "how did he [Bob] know?". We are told from the start that Bob is right, and asked to explain why.
There's a reason I said "in the real world".
For best results, generalise to N, and have everyone remain silent for a short time, before someone (or everyone simultaneously, your choice) answers “yes”.
To me it's pretty clear that continuously variable (ie. base infinity) is optimal for computation per unit energy when you have additive thermal noise and quantization by the plank energy.
Modern comms systems are heading in that direction with OFDM and large QAM constellations with lots of ECC to get more data throughput for the same transmit power on the same channel.
One day we might get to need to do that for computation too - but for now, binary is doing well.
Modern comms systems are heading in that direction with OFDM and large QAM constellations with lots of ECC to get more data throughput for the same transmit power on the same channel.
One day we might get to need to do that for computation too - but for now, binary is doing well.
OFDM and QAM are techniques that increase the data throughput through a channel of fixed bandwidth, but this is achieved by increasing the transmission power more than the increase in speed.
They are not at all efficient from the point of view of the energy consumption.
The best energy efficiency is achieved with quadrature phase modulation (QPSK), which allows very low transmission powers relative to the noise of the communication channel.
Any increase of speed above that is obtained by a worse energy efficiency.
Despite that, OFDM and large QAM constellations are very frequently used because for the modern WiFi or mobile phone communication it is typical to be very close to the access point or to the cell phone tower so the transmitter is able to use a power much greater than the minimum necessary, in order to increase the data throughput.
For logic circuits, the constraints are very different than for communication channels. If the logic circuits use DC power supplies, then the controllable elements, like transistors or vacuum tubes, must use only 2 states, on and off, otherwise they would consume too much power. So even if one would want to make a gate with ternary logic, it would have to be composed of transistors with binary states, otherwise it will overheat at the current circuit densities.
They are not at all efficient from the point of view of the energy consumption.
The best energy efficiency is achieved with quadrature phase modulation (QPSK), which allows very low transmission powers relative to the noise of the communication channel.
Any increase of speed above that is obtained by a worse energy efficiency.
Despite that, OFDM and large QAM constellations are very frequently used because for the modern WiFi or mobile phone communication it is typical to be very close to the access point or to the cell phone tower so the transmitter is able to use a power much greater than the minimum necessary, in order to increase the data throughput.
For logic circuits, the constraints are very different than for communication channels. If the logic circuits use DC power supplies, then the controllable elements, like transistors or vacuum tubes, must use only 2 states, on and off, otherwise they would consume too much power. So even if one would want to make a gate with ternary logic, it would have to be composed of transistors with binary states, otherwise it will overheat at the current circuit densities.
For a fixed average transmission power, bandwidth and noise power, QAM provides more goodput than QPSK, and at larger constellation sizes the gap increases.
In fact, QPSK is just a type of QAM with a constellation size of 2.
In fact, QPSK is just a type of QAM with a constellation size of 2.
I'm not sure how logic and circuit design would look in that case. For communications, you're ultimately trying to get a representation of a bit stream from point A to B.
At some point, maybe you end up not doing exact computation but basically creating neural-like architectures that learn responsibilities, which compose up to a fully functional computer.
At some point, maybe you end up not doing exact computation but basically creating neural-like architectures that learn responsibilities, which compose up to a fully functional computer.
It's tricky because as noise increases, large constellations, although perhaps in theory with advanced statistical decoding (where you consider P(Symbol|Received signal)) they're advantageous, become less viable and more demanding computationally. Usually the gains are a small factor. At one point, the energy cost of computation required to make statistical decoding[1] surpasses any gains from increases in complexity.
More than that, the ratio of channel energy (or cost) requirement to computational energy can vary :) For example, if you're transmitting a message to a space probe, the energy and costs associating with message transmission are enormous, such that the decoding energy will be a lower proportion (favoring more complex decoding systems). For a computer bus transmitting signals internally at short distances, the energy cost of encoding (and even using QAM or non-binary encoding at all) and statistical decoding will probably be less than the energy gains.
Credit to Christopher Blake et. al in this paper: (as seen on Canadian Workshop on Information Theory :) )
https://tspace.library.utoronto.ca/bitstream/1807/69482/1/IT...
From the abstract: "This implies that the average energy per decoded bit must approach infinity for any sequence of decoders that approaches capacity" (valid for the VLSI model in question, and binary channel model, but I'd guess this generalizes to any physical computational medium)[2]
It's really interesting how in the context more complex isn't always better.
[1] Usually the complexity of the whole system, in more practical terms, is determinant as well -- because engineering and maintaining complex systems is difficult
[2] More precisely: "It is shown that for any sequence of increasing-block-length decoder circuits implemented according to this model, if the probability of block error is asymptotically less than 1/2 then the energy of the computation scales at least as Ω (n√log n), and so the energy of decoding per bit must scale at least as Ω (√log n)"
More than that, the ratio of channel energy (or cost) requirement to computational energy can vary :) For example, if you're transmitting a message to a space probe, the energy and costs associating with message transmission are enormous, such that the decoding energy will be a lower proportion (favoring more complex decoding systems). For a computer bus transmitting signals internally at short distances, the energy cost of encoding (and even using QAM or non-binary encoding at all) and statistical decoding will probably be less than the energy gains.
Credit to Christopher Blake et. al in this paper: (as seen on Canadian Workshop on Information Theory :) )
https://tspace.library.utoronto.ca/bitstream/1807/69482/1/IT...
From the abstract: "This implies that the average energy per decoded bit must approach infinity for any sequence of decoders that approaches capacity" (valid for the VLSI model in question, and binary channel model, but I'd guess this generalizes to any physical computational medium)[2]
It's really interesting how in the context more complex isn't always better.
[1] Usually the complexity of the whole system, in more practical terms, is determinant as well -- because engineering and maintaining complex systems is difficult
[2] More precisely: "It is shown that for any sequence of increasing-block-length decoder circuits implemented according to this model, if the probability of block error is asymptotically less than 1/2 then the energy of the computation scales at least as Ω (n√log n), and so the energy of decoding per bit must scale at least as Ω (√log n)"
Oh yes the data will homomorphically encoded into white noise, then computed stored and decoded, all near planck energy per bit :)
Isnt that analogue computation
Doesn't it depend on what problem you are solving and which building blocks you are starting with? Say you have a reversible electric motor. This will likely enable lighter/cheaper/more efficient/more reliable designs than one or two unidirectional motors and transmission to redirect the torque in desired direction. And if you can come up with tranary circuits for the controller, you again have fewer elements and less power losses compared to binary circuits.
Now, if you are going to build trenary circuits out of binary flip flops, you are wasting one state available out of 4 with two flip flops, so clearly suboptimal. You need unique interfaces and physics for each element to benefit from efficiency. Even unique programming languages - binary if/else logic is common, it could be that in real world if/else/unknown is common and can be handled more efficiently by trenary circuits, or new algorithms can be created to utilize a hardware-implemented trenary bit.
Of course, a likely answer is that, now that binary hardware and software is highly developed, it's not worth it to do complete redesigns for modest efficiency gains.
Now, if you are going to build trenary circuits out of binary flip flops, you are wasting one state available out of 4 with two flip flops, so clearly suboptimal. You need unique interfaces and physics for each element to benefit from efficiency. Even unique programming languages - binary if/else logic is common, it could be that in real world if/else/unknown is common and can be handled more efficiently by trenary circuits, or new algorithms can be created to utilize a hardware-implemented trenary bit.
Of course, a likely answer is that, now that binary hardware and software is highly developed, it's not worth it to do complete redesigns for modest efficiency gains.
Physics is pretty harsh, and it really likes two-state circuits. One reason is well described in [0]: power consumption P=I*V.. With binary logic, one state means V=0 so power is zero; other state means I=0 so power is zero again; any sort of intermediate values means non-zero power consumption, which, when multiplied by a huge number of elements per IC means extreme heat and power wasting.
And "existing software" never stopped innovations: we get all-new computation models all the time.. there are FPGAs and IRAMs and transputers and memristors and analog AI, and perhaps even GPU and DSP. None of them can use existing binary software and some of them have non-binary hardware. They don't all work well all the time, and yet people keep innovating and trying to find ways to make them work.
And yet no one (outside of hobbyists) works on ternary computers. Physics is harsh.
[0] https://news.ycombinator.com/item?id=38984009
And "existing software" never stopped innovations: we get all-new computation models all the time.. there are FPGAs and IRAMs and transputers and memristors and analog AI, and perhaps even GPU and DSP. None of them can use existing binary software and some of them have non-binary hardware. They don't all work well all the time, and yet people keep innovating and trying to find ways to make them work.
And yet no one (outside of hobbyists) works on ternary computers. Physics is harsh.
[0] https://news.ycombinator.com/item?id=38984009
I'm pretty skeptical of this scenario. Motors are quite high power and require big dedicated amplifiers. I would expect a negligible difference from the amplifier input being two bits, or one trit, or a separate wire per state.
> A demonstration that e=2.718 rounded to 3 is the best radix for computation is disproved.
Is this some weird attempt at humour, or meant as a serious statement? I mean the mention of e of course.
Is this some weird attempt at humour, or meant as a serious statement? I mean the mention of e of course.
2 line explanation of where e comes from here: to represent a number x in base b, you need roughly log_b(x) digits. If you weight that by the number of different digits in base b, you get b * log_b(x) = b * log(x)/log(b) = b/log(b) * log(x) (where now the log is any base you care to choose).
So assuming x > 1, this is minimized precisely when b/log(b) is minimized. The derivative of b/log(b) is (log(b) - log(e))/log(b)^2, so this is zero when b = e. (The second derivative is 1/(e log(e)) > 0, so this is a minimum).
So assuming x > 1, this is minimized precisely when b/log(b) is minimized. The derivative of b/log(b) is (log(b) - log(e))/log(b)^2, so this is zero when b = e. (The second derivative is 1/(e log(e)) > 0, so this is a minimum).
Why should we weigh by the number of different digits? I.e. is there an argument why the cost of a single digit is linearly proportional to the number of values it can hold?
To me this seems like the weak point in the argument.
To me this seems like the weak point in the argument.
[deleted]
Why does the number of digits in the base should matter?
It's called radix economy. Different radices have different efficiencies as defined by the ratio of number of digits in a radix alphabet over the number of placeholders required.
Simple example, base 1 is obviously inefficient once counting past 1. Similarly base 1 million is inefficient (until you're counting in the bazillions)
Simple example, base 1 is obviously inefficient once counting past 1. Similarly base 1 million is inefficient (until you're counting in the bazillions)
If you can store one digit of a number base million in one physical element then it's exactly as efficient when it comes to storage of digits as binary. One element per one digit.
But it's about 20 times more efficient when it comes to storage of whole numbers because you can store number up to a million in a single physical elements while binary needs 20 elements.
But it's about 20 times more efficient when it comes to storage of whole numbers because you can store number up to a million in a single physical elements while binary needs 20 elements.
I see what you're trying to say, like I understand the intuition, but like I was saying earlier this is an already understood topic https://en.wikipedia.org/wiki/Radix_economy and that point has been addressed. Sorry, not trying to be a jerk. Just wanted to point that out in case you're interested in this subject.
In the example you gave, I'm assuming by 'physical element' you mean 'placeholder' or digit. Storing more numbers in a single placeholder seems like you're just getting efficiency for free, but that's not how information works. You have to come up with a unique symbol for one million numbers (0 - 999,999). Which you have to pay for.
base 64 is a more realistic example. With 64 characters per digit, it may seem like it's more efficient, since you require less digits to express the same number as base 10 or 2, but you still have to encode 64 unique characters, and it ends up being less efficient. That doesn't mean less efficient is worse. It just means it is more specialized and used for different things. For example, base64 gets used when you want to encode information in a small amount of space. Otherwise, for the actual storage and computation of data, lower bases are preferred, and base 64 is still obviously stored as binary.
For what it's worth, the base integer with the best radix economy is 3, followed by 2.
In the example you gave, I'm assuming by 'physical element' you mean 'placeholder' or digit. Storing more numbers in a single placeholder seems like you're just getting efficiency for free, but that's not how information works. You have to come up with a unique symbol for one million numbers (0 - 999,999). Which you have to pay for.
base 64 is a more realistic example. With 64 characters per digit, it may seem like it's more efficient, since you require less digits to express the same number as base 10 or 2, but you still have to encode 64 unique characters, and it ends up being less efficient. That doesn't mean less efficient is worse. It just means it is more specialized and used for different things. For example, base64 gets used when you want to encode information in a small amount of space. Otherwise, for the actual storage and computation of data, lower bases are preferred, and base 64 is still obviously stored as binary.
For what it's worth, the base integer with the best radix economy is 3, followed by 2.
Thanks. I should have googled this when you mentioned it.
I see that radix economy makes some sense if you assume that the "cost" of the "element" is not fixed but linearly proportional to the number of different states it needs to hold. It was apparently linear for the computers built with triodes but log2(n) to hold n states seems more realistic in electronics. Maybe little more for error resiliency.
I see that radix economy makes some sense if you assume that the "cost" of the "element" is not fixed but linearly proportional to the number of different states it needs to hold. It was apparently linear for the computers built with triodes but log2(n) to hold n states seems more realistic in electronics. Maybe little more for error resiliency.
I think the b factor is due to the analog representation: if the base has b values, you use on average b/2 voltage for representation. I would think the mean square value in might have been more appropriate though? (as voltage energy losses usually are V^2 / R or C V^2)
Repeating the calculation (for k bits and b values) using square values, you get E = b^2 * log_b(k) and dE/db = 2b/ln(b) - b^2 / (ln(b))^2 / b = b/ln(b) * (2 - 1/ln(b)). Setting dE/db to 0, we get 2 - 1/ln(b) = 0, ln(b) = 1/2,
b_opt = sqrt(e) = 1.6487...
Repeating the calculation (for k bits and b values) using square values, you get E = b^2 * log_b(k) and dE/db = 2b/ln(b) - b^2 / (ln(b))^2 / b = b/ln(b) * (2 - 1/ln(b)). Setting dE/db to 0, we get 2 - 1/ln(b) = 0, ln(b) = 1/2,
b_opt = sqrt(e) = 1.6487...
In our computers, to hold b states we are using elements which cost is not proportional to b or b^2 but log2(b).
Which base is optimal then? 2? Any?
Which base is optimal then? 2? Any?
That's true, if you use binary encoding to represent the b states. I were referring to base b representation, in which by definition we use b states to represent log2(b) bits: for example, 4 states to represent bits 00,01,10,11, which could correspond to voltage levels 0V,1V,2V,3V of a variable (analogous for other values of b).
In this case, the average voltage used would be the average of 0, 1, 2^2, 3^2, which is 0+1+...+(b-1)^2 / b ~ b^2 (proportional to b^2). I showed that in this case in theory the "optimal" base would be sqrt(e), but I can't think of simple representations of a variable with less than 2 states (you could have say 2 variables representing less than 4 states, for example the 3 pairs { 0V/1V, 1V/0V, 0V/0V }, but that seems a tad complicated![1]), so the least non-trivial integer base is just 2.
I think in reality this kind of argument doesn't apply to real computers in a straightforward way, because there are many other factors at play than what I would call a 'dynamic power consumption' associated with the square voltage. There are things like leakage currents (that consume some fixed power per transistor) and other effects that significantly complicates things, so that such simple claims of being "optimal" don't apply (so I agree with the other comment about avoiding absolute claims!). But they can inspire designs and we can see if there are any advantages in more realistic cases.
[1] Further analysis: In our example, the 3 voltage pairs have mean square voltage 1/3. If we instead use the pairs { 0V/0V, 0V/1V, 1V/0V, 1V/1V }, the mean squared voltage is 1/2. In the first case, we encode log2(3)/2 bits of information per voltage value, in the second, 1 bit per value. So the energy per bit is (energy per value)/(bits per value) = (1/3)/(log2(3)/2) = 0.420... for the first case, and 0.5 for the second case. Unfortunately, it's a loss!
As an exercise, I believe that if we delete the state 1V/1V/.../1V of a k-voltage tuple, for large enough k-tuple, we come out ahead (probably not by much), although again that's not necessarily useful in practice.
In this case, the average voltage used would be the average of 0, 1, 2^2, 3^2, which is 0+1+...+(b-1)^2 / b ~ b^2 (proportional to b^2). I showed that in this case in theory the "optimal" base would be sqrt(e), but I can't think of simple representations of a variable with less than 2 states (you could have say 2 variables representing less than 4 states, for example the 3 pairs { 0V/1V, 1V/0V, 0V/0V }, but that seems a tad complicated![1]), so the least non-trivial integer base is just 2.
I think in reality this kind of argument doesn't apply to real computers in a straightforward way, because there are many other factors at play than what I would call a 'dynamic power consumption' associated with the square voltage. There are things like leakage currents (that consume some fixed power per transistor) and other effects that significantly complicates things, so that such simple claims of being "optimal" don't apply (so I agree with the other comment about avoiding absolute claims!). But they can inspire designs and we can see if there are any advantages in more realistic cases.
[1] Further analysis: In our example, the 3 voltage pairs have mean square voltage 1/3. If we instead use the pairs { 0V/0V, 0V/1V, 1V/0V, 1V/1V }, the mean squared voltage is 1/2. In the first case, we encode log2(3)/2 bits of information per voltage value, in the second, 1 bit per value. So the energy per bit is (energy per value)/(bits per value) = (1/3)/(log2(3)/2) = 0.420... for the first case, and 0.5 for the second case. Unfortunately, it's a loss!
As an exercise, I believe that if we delete the state 1V/1V/.../1V of a k-voltage tuple, for large enough k-tuple, we come out ahead (probably not by much), although again that's not necessarily useful in practice.
Correction: I've just realized I've drawn an incorrect conclusion, the energy per bit in the case I've shown is indeed lower than the standard 2 bit encoding, so it's actually a win! Again, for a myriad reasons, I'm not sure you'd want to use that encoding in real life, but it does consume a little under 20% less power in terms of V^2 losses.
It's not a joke. e is theoretically the most efficient base. Of course you can't actually have fractional bases so the most efficient real base (again, theoretically) is 3.
This paper is just showing that with real technology it's still less efficient than 2. I don't think anyone was really suggesting that we switch to base 3 hardware so it's a completely academic result, but still interesting.
This paper is just showing that with real technology it's still less efficient than 2. I don't think anyone was really suggesting that we switch to base 3 hardware so it's a completely academic result, but still interesting.
No there has been such a demonstration, which they quote and from which they show the results:
S.L. Hurst, “Multiple-Valued Logic - Its Status and Its Future“, IEEE Trans. on Computers, VOL. C-33, No 12, December 1984.
According to that demonstration, e would be optimal, but it is impossible because it is not integer. Among integers, 3 is best, followed by 2 and 4, which are equally good.
However, as mentioned in the article, the difference between 2 and 3 is very small and that classic demonstration does not take into account the difference in the complexity of the logic gates and registers for binary and ternary logic.
S.L. Hurst, “Multiple-Valued Logic - Its Status and Its Future“, IEEE Trans. on Computers, VOL. C-33, No 12, December 1984.
According to that demonstration, e would be optimal, but it is impossible because it is not integer. Among integers, 3 is best, followed by 2 and 4, which are equally good.
However, as mentioned in the article, the difference between 2 and 3 is very small and that classic demonstration does not take into account the difference in the complexity of the logic gates and registers for binary and ternary logic.
[deleted]
It‘s a fringe idea put forward by a German cryptocurrency (of course), and loosely based on some old result by Knuth.
So no, some people really clamor for all of us to switch to ternary logic.
So no, some people really clamor for all of us to switch to ternary logic.
Not too fringe of an idea, IMO. The idea of tri-state logic is fairly ubiquitous in analog electronics. Also, was a family of Soviet ternary computers[1] that were fairly competitive with their contemporary binary logic based counterparts.
[1]: https://en.wikipedia.org/wiki/Setun
[1]: https://en.wikipedia.org/wiki/Setun
Setun is very heavily mythologized as "groundbreaking", but the reality is that it was never a true ternary machine on hardware level. They tried to make it work, but couldn't, so in the end each hardware trit was implemented as a pair of ferromagnetic bits.
Okay, let me more precise: the fringe idea in Iota was to insist on ternary logic implemented in software on binary logic hardware.
I didn't know what IOTA is and had to look it up. And I agree with your assessment, I suspect their decision was motivated by marketing reasons and not technical reasons.
Sure, but what does the number e rounded up to 3 have to do with it?
If you assume the complexity of an elements grows linearly with the number of states it can assume (e.g. if complexity of a bit is 2a then complexity of a trit is 3a). Then the total complexity of for example representing a number N is log{N}_{B} \times B \times a. Minimizing this with respect to B yields B=e.
The article explains this:
> For computation, radix R = 3 would be more economical than R = 2 because the “optimal” radix would be R = e = 2.718, according to a demonstration presented in [1].
Where [1] is "S.L. Hurst, “Multiple-Valued Logic - Its Status and Its Future“, IEEE Trans. on Computers, VOL. C-33, No 12, December 1984." I can't find that one for free anywhere, but there's your lead.
> For computation, radix R = 3 would be more economical than R = 2 because the “optimal” radix would be R = e = 2.718, according to a demonstration presented in [1].
Where [1] is "S.L. Hurst, “Multiple-Valued Logic - Its Status and Its Future“, IEEE Trans. on Computers, VOL. C-33, No 12, December 1984." I can't find that one for free anywhere, but there's your lead.
IEEE754 enters chat - synthwave starts banging
The golden ratio rounded up is 2. QED.
It’s not quite nonsense:
“100 in decimal has three digits, so its radix economy is 10×3 = 30; its binary representation has seven digits (1100100 2) so it has radix economy 2×7 = 14 in base 2; in base 3 its representation has five digits (10201 3) with a radix economy of 3×5 = 15; in base 36 (2S 36) its radix economy is 36×2 = 72.” https://en.wikipedia.org/wiki/Radix_economy
The idea being that there’s a tradeoff between the cost of each digit vs the number of digits you need. However we use base 2 because the cost of base 3 is more than 50% higher than using base 2.
“100 in decimal has three digits, so its radix economy is 10×3 = 30; its binary representation has seven digits (1100100 2) so it has radix economy 2×7 = 14 in base 2; in base 3 its representation has five digits (10201 3) with a radix economy of 3×5 = 15; in base 36 (2S 36) its radix economy is 36×2 = 72.” https://en.wikipedia.org/wiki/Radix_economy
The idea being that there’s a tradeoff between the cost of each digit vs the number of digits you need. However we use base 2 because the cost of base 3 is more than 50% higher than using base 2.
Best mic drop.
I do not follow the theory. But in implementation there is a counter example: https://en.m.wikipedia.org/wiki/Setun
This was a ternary computer built by Soviet mathematicians
> Between 1965 and 1970, a regular binary computer was used at Moscow State University to replace it [setun] Although this replacement binary computer performed equally well, it was 2.5 times the cost of the Setun.[2]
This was a ternary computer built by Soviet mathematicians
> Between 1965 and 1970, a regular binary computer was used at Moscow State University to replace it [setun] Although this replacement binary computer performed equally well, it was 2.5 times the cost of the Setun.[2]
does not look like counter-example to me:
> Due to the low reliability of the computer elements on vacuum tubes and inaccessibility of transistors the fast elements on miniature ferrite cores and semiconductor diodes were designed.
Perhaps trinary is a good idea if you don't have access to transistors or to reliable vacuum tubes, but do have access to diodes and miniature ferrite cores.
I don't see however how this is relevant today - we certainly have access to great transistors now, and as the paper shows with transistors, binary rules.
> Due to the low reliability of the computer elements on vacuum tubes and inaccessibility of transistors the fast elements on miniature ferrite cores and semiconductor diodes were designed.
Perhaps trinary is a good idea if you don't have access to transistors or to reliable vacuum tubes, but do have access to diodes and miniature ferrite cores.
I don't see however how this is relevant today - we certainly have access to great transistors now, and as the paper shows with transistors, binary rules.
There are three kinds of people in this world.
Those who understand ternary. Those who don't understand ternary. And...
Those who understand ternary. Those who don't understand ternary. And...
The ones who are kinda split on it
Those who resort to spelling the number 10.
Both??
Not sure what the author was thinking when he wrote the paper but this is one of the cases where peer review would have helped him a lot to make less grand statements.
>Until tri-state transistors are mass produced binary encoding of numbers is the natural system for computers to work in.
From memory the Setun used vacuum tubes which could natively handle three states at the hardware level.