Would having 4 states per "bit" rather than 2 mean twice the storage space?

Question

Pretty straightforward fundamental, albeit naive, question:

Would having 4 states per "bit" rather than 2 mean twice the storage space? In case that isn't clear, I mean as in if every "storage structure", rather than only representing 2 values, (base 2 : 0, 1), could represent 4 values (base 4 : 0, 1, 2, 3).

Answer 1

The word you are looking for is not "bit" but "symbol." "Symbol" is the word used to describe the process of mapping hardware signals (such as voltages or magnetic patterns) into logical bits. If a symbol may have 4 states, it can encode 2 bits worth of information.

Of course, we aren't saying anything about the resource usage of the symbol in that argument. If you're sending symbols along a wire as voltages, the different symbols look more and more similar as you increase the number of states per symbol. If I have a 0-5V wire, and 2 states per symbol (1 bit), my two states are 0V and 5V, with 5V between each symbol. If I have the same wire, but encode 4 states per symbol (2 bits), my states are 0V, 1.66V, 3.33V and 5V. That's 1.66V between each symbol. It's now easier for noise to corrupt my signal.

There is a law relating these, known as Shannon's Law which relates the bandwidth (in bits) to the rate of errors which occur due to noise on the line. It turns out that there's a limit to how many bits you can cram across a wire. Using more symbols leads to more errors, requiring more error correction.

We do use this technique in real life. Digital television uses QAM-64, with 64 states (and thus 6 bits per symbol). Ethernet uses 4 voltage levels, so 2 bits per symbol.

Edit: I used bit transmission rates rather than storage because it's more common to see symbols with more states in transmission, so I could make the story more clear. If one wishes to specifically look at storage and storage alone, one could look at Multi-Level Cells in flash memory, as Someone Somewhere mentioned in the comments. Such memory uses the exact same approach, storing 3 bits as 16 different charge levels of a capacitor. (or more!)

Answer 2

One quarternary memory cell can store exactly as much information as 2 binary memory cells:

Quaternary Binary
0          00
1          01
2          10
3          11

So if you have same number of memory cells, but they are quarternary, then you have twice as much memory. But if this quad cell takes twice as much space on a chip, then there is no benefit.

Or another way, if you had 1 gigaquad of some quartenary storage, it could store as much information as 2 gigabits of normal binary memory, because each quad could be expressed with two bits.

---

In a way this whole line of though is just of academic interest. You can already think that memory chips store for example 2^32 state cells, because you can not fetch 1 bit from them, you always get a full word. And if in future someone came up a way to store that word in 4-state physical cells more efficiently than in 2-state cells, then that would be used, but it wouldn't be visible outside the memory chip, it would still handle full memory words only, which can have for example 2^32 different states.

Answer 3

In basic theory, yes. In reality, no - because we don't actually store data in bits anyway (on HDDs). Cort Ammon covers the issues in data transmission very well. RAM, cache, and SSDs store data as bits, but HDDs are different due to the nature of their physical material and our efforts to pack more data onto them. Most data is still stored on HDD's, so I'll focus on those. I'll go well beyond the explanation that you'll find from most sources, but will try to cite sources where I can. These sources must be dug up from the ancient depths of the internet because it is - to a large extent - truly forgotten knowledge.

First, hard drives store information with magnetic fields on the surface of the drive platters. The drive head reads these by sensing the flux from the change in that field - this is far easier to measure than the actual direction and strength of the magnetic field. but if the field is 50 of the same segments in a row, it can't actually count that there were 50 - it read a flux spike when reading the first segment, then no flux for a while after that, and it cannot track time accurately enough to be certain that the field was unchanged for 50 segments.

So, the basic (oversimplified) model is to store a bit as a pair of magnetic fields. The first would always be a switch from the prior segment, and the second would be a flip to represent 1 or no flip to represent 0. So a 0 is FN (flip-null) and a 1 is FF (flip-flip). The drive's timing is accurate enough to recognize the difference between one flux spike and two flux spikes within a segment. This format is called Frequency Modulation. So this gives clear signals, BUT it means that every bit of memory requires two spaces on the drive - that's very inefficient. So no hard drive actually had this most basic form of encoding; it used simple compression tricks instead. The simplest is Modified Frequency Modulation, which changes the pattern so that the extra magnetic flip is used only if a 0 is preceded by another 0. This lets the engineers cram nearly twice as much data into the same space, and thus was used on the first HDDs, and is the format on floppy disks. After that, a more advanced system called Run Length Limited was developed with a similar general idea, which I won't go into because it gets much more complicated and there are multiple implementations.

But we don't use any system like that today. Instead, we use a system called Partial Response, Maximum Likelihood (PRML). PRML requires the head to read a length and collect the magnetic sample, then it compares it to a reference set of stored samples to determine which one it matches best. It forgoes the entire concept of flux spikes, and instead uses pattern matching (I oversimplify, but the oversimplification is worth it), and the pattern corresponds to a set of bits. It uses noise filters and other tech to remove potential errors. It's best to think of it as a complex waveform, and the HDD knows how to translate each waveform into a set of bits. In this sense, the data is actually stored more in an analog format than a digital one, because the physical material can support the gradual variations of analog better than the sudden jumps of digital.

The best guide to this is at http://www.pcguide.com/ref/hdd/geom/data.htm (hit the Next button a few times to read all of it) and there are a few other sources - mostly from people who created massive repositories of computer knowledge that no one has any reason to know. A decent additional source (which is good but not quite 100% perfect as far as I can tell) is at http://www.tomshardware.com/reviews/hard-drive-magnetic-storage-hdd,3005-6.html

TL;DR: Hard drive disks don't store data in a format anything like 1's and 0's; they instead use complex signal processing to cram signals into the smallest space possible, and decode it when reading. So, they are really base-agnostic.

I wouldn't be surprised in base-4 storage was attempted on SSDs or RAM at some point. It all depends on the physics and chemistry of the materials. The engineers and scientists will push those materials as far as they can, and will pursue whatever route yields the best results.

Answer 4

Yes having more states will allow each "cell" of storage or each symbol on a data transmission line to carry more information.

But there is no free lunch, we need to actually be able to distinguish those states. Turns out it's easy to build binary logic gates and much harder to build gates that distinguish, process and regenerate more than two logic levels.

And then there is the issue of attenuated signals. On a two level system you can simply design your threshold so that it works with worst-case attenutation, on a four state system where significant attenation is expected you need to adapt your thresholds to the particular attenuation of your system, not just to the worst-case attenuation. In practice that then means you need to add an attenuation measurement system to your communications system.

All that said there are situations where the extra complexity DOES make sense. A lot of SSDs now use more than two levels per flash cell (known as MLC or TLC), modern high speed communication protocols also nearly always use multi-level encodings.

Answer 5

You may be interested to know that the Russians developed a chip that was ternary, instead of binary. That means that each symbol could have the values of -1, 0, or 1. So each physical gate could store "three" values, instead of "two".

Potential future applications

With the advent of mass-produced binary components for computers, ternary computers have diminished in significance. However, Donald Knuth argues that they will be brought back into development in the future to take advantage of ternary logic's elegance and efficiency.

As you start to suspect, there may be a more efficient way to implement a base numbering system. (Although this ability to express this more efficiently depends on our ability to physically manufacturing on material.) It turns out that the constant e, the base of natural log (~2.71828), has the best radix economy, followed by 3, then 2, then 4.

Radix economy is how much number you can represent versus how many symbols you need to take up to do it.

For instance, the mathematical number three is represented as 3 in base 10, but as 11 in base 2 (binary). Base 10 can express larger numbers with less symbols than binary can, but the symbol table of base 10 is 5x larger (0...9) than the symbol table of base 2 (0, 1). Comparing the expressive power to the size of the symbol set is called "radix economy" (radix being the number of the base, for example, 2 in binary, or "base 2"). The natural question that follows is, where do I want to be in terms of this tradeoff? What number should I adopt as the radix? Can I optimize the tradeoff between expressive power and size of symbol set?

If you look at the chart in the radix economy article in wikipedia, you can compare the economies of various bases. In our example, base 2 has a radix economy of 1.0615, while base 10 has an economy of 1.5977. The lower the number the better, so base 2 is more efficient than base 10.

Your question of base 4 has an efficiency of 1.0615, which is the same size as base 2 (or binary), so adopting it over base 2 only gets you the exact same size of storage per number, on average.

If you're wondering, then is there an ideal number to adopt as a base, this chart shows you that, it's not a whole number, but the mathematical constant e (~ 2.71828) which is the best, having an economy of 1.0. This means that it's efficient as possible. For any set of numbers, on average, base e will give you the best representation size of it, given its symbol table. It's the best "bang for your buck".

So, while you think your question is perhaps simple and basic, it is actually subtly complex, and a very worthwhile issue to consider when designing computers. If you could design an ideal discrete computer, using base 4 offers the same deal-- the same space for cost-- as binary (base 2); using base 3, or ternary, offers a better deal over binary (and the Russians did build a physical, working computer with base 3 representation in transistors); but ideally, you would use base e. I don't know if anyone's built a working physical computer with base e, but mathematically, it would offer a better deal of space over binary and ternary-- in fact, the best deal out of all the real numbers.

Answer 6

Would you believe I can encode the sum total of human knowledge with a single match?

If I encode a bit in a single match the symbols might look like this:

With enough matches I can say anything. But I can say twice as much with the same match if I add two more symbols. Which might look like this:

Twice as much info with the same match! Well why not? Well why stop? Rotate every symbol 45 degrees and we double again. 30, 15, on and on. Soon I have enough symbols that I can say anything and everything with only one match! Once I do that we have a problem though. What does this match say?

How can you be sure exactly which symbol that is now? How much time do you need to be sure? That's the rub. The more symbols I add the more effort it takes you to tell them apart.

Would having 4 states per “bit” rather than 2 mean twice the storage space?

If we're talking about per match then sure. But, even if that didn't slow down our match read speed, now we're taking up more of my kitchen counter space. It's always something.

Answer 7

If a bit had 4 states instead of two in a symbol (bit), then yes you would have twice the amount of memory. This might or might not take twice as much space, depending on the technology used.

There is a real-life example that you have in front of your eyes every day: Ethernet (which is not memory, but it's similar insofar as it transmit data) you have, among others, the ordinary "fast ethernet" at 100 MBit 100BASE-TX, and you have 1GbE ethernet.

Clearly, 1GbE requires 10 times higher frequencies than 100 MBit (as 100 MBit requires 10 times higher frequency than 10 MBit), that's why you need more expensive cables, too. Obviously.

Oops... that isn't true at all.

100 MBit ethernet transmits over two cable pairs at 100 MHz whereas GbE transmits at 125 MHz over 4 cable pairs.

Wait, so GbE is really only 2 1/2 times faster than 100 Mbit ethernet? I only get 250 MBit/s out?

No, it also uses 5-PAM coding, which can encode 2.32 bits per pulse per cable pair, of which 2 bits are used as actual information, and the remainder makes the signal more resilient to noise. Thanks to those fractional bits, 1000BASE-T is able to drop 8B10B coding, too.

So you've doubled the number of wires, and slightly increased frequency, but you get 10 times more throughput!

Now if you thought this is sheer magic, look at how digital cable television works, and if you are still not convinced, look into ADSL, which uses 32768-QAM to encode 15 bits in one symbol.
Same old copper wire, same frequency band, 15 times more stuffs going through.

EDIT:
Another very obvious real life example which I completely forgot about (since it is just too obvious, apparently!) that you have in front of your eyes every day is: USB pendrives.
Those commonly use MLC flash memory. What's that? It is a type of memory cell that stores one of four different charge levels. That's the smallest unit that you can access on a hardware level. So you could say your "bits" indeed have 4 states (they don't, you really just get out two bits instead of one, and you can only read complete sectors from the device anyway... but you could arguably look at it that way).
Same number of cells, but double the memory. Cheaper, smaller, somewhat less reliable, but... first and foremost, cheaper.

Answer 8

Having 4 symbols per digit instead of two means that you can store twice as much information in a single digit. However, as you increase the amount of digits, you can store exponentially more information:

Any n digits in base 2 can encode 2^n states whereas base 4 can encode 4^n.