EXTRA BITS/TRITS - Huffman Trees - Computerphile

[@ib9rt]

"Getting your average code length down" is very important when communicating information over data channels. For example ( the rather obsolete now) 14.4 kb/sec modems still operated at 2400 baud (2400 symbols per second). An audio telephone line cannot operate faster than about 2400 baud, but if you encode more than 1 bit of information per symbol you can transmit more information in a given time and thus achieve faster speeds. That's how all the fast modem protocols like V.32 or V.34 worked.

[@DigGil3]

I've been building "trinary" digital circuits and my systems works as in the wikipedia page for 3-state logic: There is "on" when a circuit's output is positive in voltage and it sources current, "off" when the output is negative so it sinks current and there's a third high-impedance state where no current can flow.

[@PiMaster9001]

I believe the main reason that such things have not been pursued lays with diminishing returns. The amount more bits it would take to store the same information as with base n is log(n,2). Say 100 states can be represented, and there are 100 units: 10^200 can then be stored. The number of bits needed to store the same amount is log(10^200,2) i.e.100*log(100,2), ~664.39; log(100,2) times as many as with the base 100 system. Having ~6.64 as many bits is much easier than having 100 states.

[@bigsteamfan]

I swear, this is the first video, the Huffman Trees video, out of all the Computerphile videos, that I didn't understood... at all... My little brain is now a knot, thanks Brady!

[@matrinGD]

I appreciate your interest and feedback. I think we might be talking about different things though. Yes, the data transmited is digital - that is the way it is interpreted and coded. And the devices and protocols that read digital data are refered to as digital. As you pointed out, having digitally encoded data offers many advantages - lower bandwidth, no noise in the data transmited (if it gets transmited) ... My point however is, that the carrying signal transfering the data must be analog.

[@pdieraue]

The published date shows the day that the video went from unlisted to public. When the video was unlisted it would have shown the date it was uploaded, but now that it's public you can only see when it was published.

[@boronguy]

because three is the most efficient base to use. see a bit as using 2 places a trit as 3 a quit as 4 etc. now take a max space of 12. you can fit 6 bits in there 2^6=64 "options". in 12 places you can fit 4 trits. 3^4=81 "options" . and in twelve places you can fit three quits. 4^3=64, same efficiency as bits. also like trits very hard to program and would use more electricity or a very weird system. correct me if i'm wrong

[@LimeC0la]

bits aren't necessarily on/off, usually you're speaking in terms of high/low, whether that be frequencies or voltages. Trits could be represented then with the same bandwidth of high/low, but the margin of error is greatly increased, For it to work within the same tolerance of bits you have to increase your mediums bandwidth by 50% and that brings a whole lot more problems, eg voltage increase = more power usage + more heat.

[@aclima93]

Precisely. Unless you build transistors which can be in N distinct states, you can't actually use another N-nary system. As you mentioned, transistors as we know them can be accurately measured in two different states, "on" and "off" depending on how the current passes through them.

[@matrinGD]

(continued) Depending on our interpretation - the number of levels we assign to the analog signal, we can get bits, trits, ... hexits. To improve our storage or data transfer, we can either increase our base digit, our we can improve the size of the base digits on the media. Right now the improvements in the size of the bit on the media discourage the development of trits and higher bases.

[@matrinGD]

Hm. Well the definition might be based on the data that the signal transmits. So by definition the signals we talked about would be called digital, but that would refer to the data not the signal. I referred to the it as analog, to try to show that bits are really just a trivial choice, and trits would be a very simple extension, since the base signal is actually just analog. So if you want to read three different levels instead of two its not a paradigm shift.

[@lagautmd]

It might be easy to conclude from this that a trinary coding system may be generally more efficient, therefore trinary computers might be generally more efficient. But, one example shows that to not be a generalizable conclusion. I applied the trinary code to the San Franciso weather problem and it showed the entropy is 1.26 trits with length = 1.75 trits, yielding an efficiency of 72.1%. (All this assumes I applied the method correctly, of course.)

[@NickRoman]

I think this is correct. You can encode data all kinds of ways and compress data, which is using the same type of encoding technology to effectively do this. But ultimately, the logic is where it makes a difference. Calculating logic is a very different problem from storing or transmitting data.

[@googolplexbyte]

There's always the hope of spintronics being more conducive to ternary. Spin up, Spin down, & no Spin(as in the absence of an electron).

[@laharl2k]

if it were a square signal referenced to 0V, binary would be 0V for 0, and 5V for 1(not necessarily you could swap that, depends on how you design everything) and in trits, you 0v, 2,5V and 5V for 0, 1 and 2. The problem is that you make the window smaller, making the signal much more difficult to read with the same noise. The fact that your sight has a limit in the minimum change it can detect is because the change is smaller than your eyes' noise floor(close your eye and cover them to see it)

[@marcusmors8485]

I heard that trits were used in the soviet union for their computers at the beginning. I wonder what other algorithms are easier to calculate with trits and whether or not calculation of primes is easier with base hexa units (hexbits?).

[@matrinGD]

Logic is just some mathematical operations, that we have defined in a binary system. Those operations would work perfectly well withing a larger set of logical operations of a trit system. In the end the choices that we make a largely trivial, but as many have pointed out here, come down to one simple thing. The efficiency with which the final product can be: developed, produced and used.

[@matrinGD]

(continued) Once we hit the hard physical limits of the size of the bit, where improvements are impossible, then we might start to develop higher level base digits like trits. Quantum computing is a parallel technology, which is currently also developed with bits in mind. Once it has matured, the development of quantum trit states should be just as trivial as is it for classical computing - although it might not provide any benefits.

[@thehearth8773]

Processing in hexadecimal is certainly possible; you just need a cell to consist of sixteen possible states. For trits, for example (for a simplified explanation) you can have the states 1, 0.5 and 0, where the number represents the proportion of signal voltage to supply voltage. You can further divide up this continuum, but it becomes difficult to differentiate between, for example, the state 1 and the state 0.999. Binary is used because it's simplest, not because it's the only one possible.

[@lordelliott42]

I get it now. Thanks. :) So, what's needed for trinary to work reliably is a medium of transference without that limitation, but I think that if we had such an accurate medium we could just skip to base 12 computing.

[@KuraIthys]

While that's true, if you've ever looked through the electrical specifications for a lot of digital systems you'll note many of them are effectively trinary at an electrical level. The extra state is considered undefined though, and is generally used to determine whether or not there is valid data available, rather than as a state in it's own right. (It is of course still a state. That anything in the circuit can measure it as distinct from the other two proves that.)

[@matrinGD]

Just though of this. Although this video presents a case where trits would be beneficial, this might not be the case in general. In any finite range of integers between 0 and X there are more integers that are powers of 2 that of 3. In a frequentist statistical f/w, where we find probabilities of events by counting them, the number you count is more likely to be the power of 2 than 3, giving the integer entropy we desire.

[@matrinGD]

I guess you have a good point. But again, given your analogy of a trumpet and a trombone, both of them produce analog signals. Any discrete change of state in the operation of the trumpet (we can assume discrete operation is possible) will still result in an analog change in the signal. Air doesn't support the bandwidth to produce a digital signal. Back to punch cards, when does a punch become an error? What if the puncher tore the card a bit? It's impossible to make all perfect punches.

[@Celrador]

Well. I would like to add one little thing to your comment though. The difficult part is to tell the voltages apart. With a 2 base system, it is pretty easy to detect overlapping signals (when instead of +4V or -4V there suddenly comes 0V/8V/-8V), so your "backup circuits" for those situations can start saying "WAIT! STOP! HOLD ON! Something is wrong! Gimme that same shit again, please!" (For those interested: This is called a collision. The Wikis about CSMA/CD and CSMA/CA could be useful.)

[@matrinGD]

The underlying signals must be analog. A digital signal would imply a discontinuity, which would require infinite bandwidth. It is however closely related to the measurement that we make. So this should cover any modulation on a wire. Even though you have a digital interpretation, in the end the signal it produces and the changes in it are analog.

[@braincruser]

There are actually codes that transmit 64 or 256 bits of information in a single tick with different amplitude and frequency modulations mixed in.

[@Kaslai]

You could also go as far as saying that we should be able to represent n amount of data in a given voltage. But as n approaches infinity, you have basically just reverted to analog, which, as you ought to know, is incredibly susceptible to interference like EMI and collisions.

[@matrinGD]

I think that some explanation as to why trits are not yet useful in classical computing would be appreciated. Here is my general understanding as a computer engineer (which might be wrong, as I am not an expert in hardware). The storage and transmission of data is always in an analog format (voltage on a wire, magnetism in the hard drive). The interpretation of this format converts it to digital.

[@googolplexbyte]

It's not directly power consumption that matters here but the heat that higher power would produce, reducing the amount of processing power could you could cram into one spot. So if one used trits they'd actually get less performance overall even if they'd get more performance per unit.

[@matrinGD]

The same reasons should apply to any media, since finite bandwidth applies to the spatial domain as well - punch holes in cards are never perfectly aligned. But they can be more than good enough. Logic gates have the same limitation. If you change on of the input signals to an 'and' gate to change its output, that change in the output signal would be analog.

[@allanrempel437]

If you look at the previous video, you'll notice that 1 and 10 are not on the leaves of the tree, that is, they aren't valid codes for a certain type of fish. This will always be the case in Huffman coding; any longer code is not just an already valid shorter code.

[@AndersBreg]

I don't know if this is a troll or not but hexadecimal IS base 16. That's the reason they have the numbers A to F in them. 15 dec. = F hex. 16^2 - 1 dec. = FF hex.

[@voveve]

Now a video on ternary computing!

[@PandeyNisheeth]

In practice, the two states of a bit are two different voltage levels, or current levels.So in case of trits it would be 3 voltages.

[@gh0stmast3r]

we'll probably finding ourselves retunring to what we learned in trinary logic when we try to start programming for quantum computing.just by looking at the wikipedia page it seems obvious that if 1 and -1 are the polar opposites then both would be the middle and vice versa. this of course can accommodate the utter absurdity of quantum mechanics where a state can actually be both 1 and -1 at the same time.

[@Elbrasch]

because, to have the same error resistance (noise, interference) like binary (when transmitting over a medium), you want to have the same distance between low and null (trinary) as you have between 1 and 0 in binary. Then you need more space in k-Space (frequency) for one trit.

[@jamesusespivot]

Technically, physical entropy is measured in base e in units called nats (no idea how that works) and at the quantum level information is qubits.

[@iismitch55]

If you look at the way QuotePilgrim and AskiiGames explain it, I can see where he would get confused, but yea qubits are the correct answer. Qubits in quantum computing define 0, 1, and everything in between. Thus, Qubits are the resulting data structure as the base of the log approaches infinity.

[@rich1051414]

If we did change to trits instead of bits, it may be more trouble than it is worth, but it does promise more efficiency simply using a different foundation unit(Powers of 3, not 2) When it comes to storage, it is that a bit is on or off, and a trit is off plus two states, so the flexibility of a trit system would be lacking regarding the technologies that could be used to use such a system. If we are speaking purely of a virtual digital communication, then sure trits may be a good idea.

[@JoQeZzZ]

The problem is that our current electronics are not nearly good enough to accommodate for this unless we use enormous currents. In micro controllers, for example, a 0 is usually defined as -2v and a 1 as -5v. We need this amount of room to move around because we just can't measure subtile differences in voltage. As soon as we can, we'd probably skip a ternary system all together, and go straight for an octonary(?) system or higher

[@TheProCactus]

Have a look at MLC and TLC Solid State Harddrives, A single memory gate thingy can store 3 bits in one element on a TLC, Thats 8 different voltages that need to be compared to output 3 bits per cell. Spend the extra get the SLC and be happy.

[@miladbassil2730]

can you do that to the english language to find out what is the optimum amount of letters?? find the probability of use for every word and asigning them the proper name

[@Snyper20]

Higher voltage = more heat. Lower variance = less accuracy. However, I do understand what you're getting at.

[@youtubehandlesareridiculous]

Wow, I though Brady doesn't like to include all of this math in sixty symbols or Numberphile, but this has much more math than the math channel! Lol!

[@coltonmoore6358]

Please cover ternary computing and the potential benefits/costs of using ternary code. It would be (and I'm sure others would agree as well) great if you could cover the history of it's use, especially the Russian computer from 1976 that I can't remember the name of. There's not too many Russian ternary computers from 1976 (might be that the project ended in 1976, bit fuzzy on that) so finding it naught but a Google search away!

[@QuotePilgrim]

Actually, bits are not on/off. Not on a hard disk, at least. They’re more like two different amounts of magnetism. But, since you’re used to interpreting bits like on/off, trits could be explained like this: 0/off = 0% energy. 1/on = 100% energy. So trits could be 0 = 0%; 1 = 50%; 2 = 100%. So 1 and 2 are both “on”, but they differ in the amount of energy.

[@TehGordonFreeman]

Why don't we go past base 3? Because when we get to base 4, we call it quits...

[@QuotePilgrim]

I know all this. I was just trying to explain the in a simple way how trits could theoretically work to someone who didn’t quite understand the concept.

[@JRCSalter]

How do trits work then? My understanding of computing (admittedly rather limited) is that you can have something being either 'on' or 'off' hence the binary everyone's used to. Where can the third signal come from?

[@darrenldlintmain]

Yea, my point was processors cannot process them directly, they are dealt in binaries as I mentioned.

[@darrenldlintmain]

I don't think we can directly process hexadecimal, cause we only have semi-conductors, which deals info in 0 and 1, two states. For trits, I think it's possible because due to quantum processors? The extra state(total 3 states) due to its nature? But I am certainly no expert on this really, so I'm really guessing that we just cannot process in hexadecimal, pardon me if I'm wrong there.

[@Celrador]

Yeah, I also had that in mind - damn 500 character limit forced me to cut a few things out though. ;) You are completely right, though. Electric circuits based on a dual system simply have the most reliability. (There is a reason, why most of our telecommunication is digital instead of analog nowadays... I don't want to dial up with my old modem again. :D)

[@io_loop]

So, does this mean that Quantum Computers should rely on a trinary encoding method in order to account for 0, 1, and 0+1 states?

[@Mettlerfreund]

thanks for the awesome entropy videos!

[@Desmaad]

Some early Soviet computers used polarity to do trinary, thus V+ for 1, V- for 2, and 0V for 0.

[@matrinGD]

Maybe a simple example is required, so that we may reach an agreement. Lets say you want to encode the digital sequence 01. For simplicity lets encode it as voltage, 0V for 0 +1V for 1, but the same principal would apply to any encoding technology. If the encoded signal were digital, the transition from 0V to +1V would be instantanious - a perfect square wave. To jump from 0V to +1V we need infinite bw. Since most media has finite bw, the change from 0V to 1V is gradual - analog.

[@googolplexbyte]

The problem is it would result in LOWER overall performance due to higher power consumption and thus more heat. More heat means less room for the things that actually do the processing and more heat sinks and other cooling.

[@MasterHigure]

Balanced ternary is the more common way to implement it. I don't have much experience with hands-on electronics, but my gut says it's a lot easier to implement than 0, 1, 2.

[@Durakken]

Trinary is more along the lines of what we're use to in real thinking. Think of it as Yes / No / Maybe. Though the higher the base digit the higher the more realistic you could say because the closer it is to a sprectrum of possibilities, but we largely disregard that spectrum and just say maybe when certainty is in the middle often also general response to the video: seems I was right so :P to all those who disagreed! Or may I misunderstood... Hrmmm I'm going to declare i'm right either way!

[@patrusorin]

Are trits what they use in quantum computing?

[@Razzfazz87]

I love your videos but they often are horribly quiet compared to all other programs. If someone calls me on skype while watching one of your videos the police station two blocks away knows about it and I live next to a highway so that's saying something. Could you increase the volume just a bit?

[@richb313]

Current logic states do use increasing negative levels, but not all do. Some use +5 volts as a 1 and 0 and 0 volts as a 0. or -5 volts as 1 and 0 as a 0 or -5 volts as 0 and 0 volts as a 1. A trinary logic state model could use =2.5 to 5 volts as a 1 0 volts as a 0 and -2.5 to -5 volts as a 2 or any combination of those levels and states. The real problem I see is defining the 3 states. Is 1 true 0 not true and 2 I don't know?

[@Kantenkugel]

But how would you send those informations through a fiber optic cable for example. I don't think that you can send the half amount of light through the cable very efficient

[@Noqism]

If you'd have a computer that can use hexadecits, then sure. The problem is that classic computer architectures use binary semi-conductors that have only 2 states (On and Off or 0 and 1 if you will). Going above 2 states is very tricky (search up: quantum computers)

[@matrinGD]

I am not sure how my argument applies to light. Light does not need a traditional medium like air to propagate, therefore as far as I know, light may have infinite bw. This would allow it to shift from 0 - laser off, to 1 - laser on as a true digital signal.

[@OneBiOzZ]

how would it work electronically? on/off/floating?

[@ChantarellGlade]

True but in another video its explained how fiber does not use on or off but interference patterns light waves.

[@endermoney3724]

have a transistor for positive voltage, another for negative voltage, and when both are off you have a 0?

[@MetrikGaming64]

The problem with base 3 - base x is that you have to use analog, and analog isn't really all that stable and would require being calibrated. That's what I think, anyways.

[@roderik1990]

So how would you distinguish between a +8v signal over a wire with high resistance and an +4v signal over a low resistance wire, making them virtually identical when received?

[@ColeslawProd]

So, trit is a three state thing, tri means three. Bi means two, so two states is a bit... So, if uni means one, is that where the word unit comes from?

[@Kabitu1]

In trinary logic the third option is usually thought of as "unknown". Just as boolean operations on binary logic makes intuitive sense, so to does trinary. True and unknown is unknown, true or unknown is true, false and unkown is false & false or unknown is unknown. .

[@penfold-55]

im kinda confused... because if you had to send a code of 1110, how would you know that it wasnt 1 and 1 and 10, how would you know it was its length. would it not be better to have 000 001 010 011 100 101 110 111 and use the unused ones as just unused code...

[@jackaw1197]

logic gets really hard to implement when you go all multi-level on it

[@typo148]

I was under the impression that base 3 computer systems used digits 1, 0 and -1 like www3.telus.net/millerlf/base-3.txt , not 0, 1, 2. Its weird but fun.

[@APaleDot]

No, trinary encoding would defeat the purpose of the 0-1 superposition. The whole point is that the bit can be a 0 and a 1 at the same time. Using trinary doesn't actually make a computer any more powerful, whereas quantum superposition allows programmers to do things that are unthinkable on classical computers. It may be possible to make a quantum computer that can use bits that are 0 and 1 and 2 and the same time, but that's another issue altogether.

[@typo148]

if you have digits 0, 1 and say x for -1 then to represent 2 you say 1x which is 1 in the threes colum and -1 in the units colum add them together and you get 2. so 1xx is 9 - 3 - 1 or 5. you would count like this 0, 1, 1x, 10, 11, 1xx. 1x0, 1x1, 10x, 100, 101 for zero to ten.

[@braincruser]

Transfering data is not a problem. its already solved for multiple bits in a same value using encoding schemes. search wikipedia for QAM

[@darrenldlintmain]

Ah....I never really knew that, thanks for the info! I don't suppose I will ever see that in textbooks.

[@gh0stmast3r]

couldn't we keep true and false values to strictly the polar values of 1 and -1? or could we even easily transfer binary to trinary by making the 1 and the 0 the same in the trinary code? in the first case we'd have to make each true/false gate capable of resolving the undefined variable that comes with the middle state, this could be used by simply routing it straight through the gate so whatever comes in goes out, or we could simply make a value for it further obfuscating the concept of truth.

[@TheGrunt76]

What about the complexity of trits based computational units in modern processor? Dealing with bits, that is 0 and 1, two voltage states practically, is quite simple. And it doesn't actually save any bandwidth using trits, as I've understood. Like on the video, amount of information is always the same, only units change. So, I can't see any benefits from trits. It would just complicate things... Just my 2c.

[@richb313]

0 volts or ground level is often used because of no current flow which is easily detected.

[@MrTridac]

The main problem with trinary logic is that there's no precise definition of true and false. One of the main Turing mechanisms is a solid true/false distinction (branch/don't branch). Although, as a programmer I'd probably like a true-false-whatever logic.

[@MetrikGaming64]

0, 1 , 2, where-as binary is 0, 1. We can't really use it in computers because you would require analog, or need a new state, which is most likely impossible.

[@Salvor_Hardin_42]

Unit actually comes from unity, but that comes from unus, the Latin adjective for one.

[@XxCoolWayKilla]

The only problem i see with using trits is how would it be ran in a world of computers that use bits...

[@smegskull]

or you can use A/C. hardware could easily be adapted to use (+,-,0) quite HDDs for example can be set to north south or neutral.

[@lordelliott42]

Why wouldn't you use high, low, and null?

[@thehearth8773]

Not really; there isn't just one 0+1 state, there's an infinite number of them with different amounts of 0-ness and 1-ness. A qubit could be considered an infinitit.

[@kujmous]

Tic tac toe is a good example of trinary. A square can be X, O, or blank.

[@unvergebeneid]

But who knows, maybe we'll soon throw in spin in addition to charge and use base 4 "crumbs" (which I'd like because they are so easy to convert to binary) or use optical computers and trits with polarization. The end of Moore's Law is near so you never know what people will come up with to make processing power keep on doubling for just a little while.

[@Ferrus91]

All this talk of entropy makes me think you should do a video on Landauer's principle

[@superjugy]

I would implement a system for trinary in volts like this: -5V, 0V and +5V for example.

[@googolplexbyte]

0 1 2 ?! I think you'll find that's -(1) 0 +(1). Balanced Ternary is the most beautiful base.

[@Tat2ice]

Good thing I saw your comment, because I didn't, then thought about it more :D Kudos!

[@DigGil3]

Now that's the real question! Someone will have to figure out a new boolean-like logic and computer architecture for this. I wonder what would Turing do... I guess that "High-Z" for the 3rd state and the recycling of common logic gates won't cut it.

[@Kelimion]

That would be 6 states in a hexit. The deci in hexadecimal takes care of the other 10.

[@OoJxShadow]

The real world is not as perfect as you might think, so thresholds are used. I belive there are more reasons why we use bits and not trits. For example, transistors have only 2 states and could only handle binary data; noise is a real pain in the ass and creates problems even when you have only 2 states. Telecommunications with 3 states would require either higher bandwidth, either higher signal amplitudes, depending on the technique.

[@philippest-pierre7470]

I love this guy!

[@Tribune12345]

I was in an argument with some guy over this. He was sure that bits are 100% power = on and 0% power = off. With bits, isn't it more like 0% power = off and > 0% power = on?