Limitations of distinctive states in the eight-bit byte?
August 18, 2006 9:11 PM Subscribe
Is there a way to put more than eight distinctive states in an 8-bit byte?
Consider each bit is a state (1 or 0, on or off). Is there a way to do more than eight separate or distinctive states in one byte? What about more than 16 states in a two-byte word? More than 32 states in a 32-bit double word?
Consider each bit is a state (1 or 0, on or off). Is there a way to do more than eight separate or distinctive states in one byte? What about more than 16 states in a two-byte word? More than 32 states in a 32-bit double word?
No. You're basically asking whether it's possible to control more than 8 lights independently with only 8 switches.
posted by kindall at 9:15 PM on August 18, 2006
posted by kindall at 9:15 PM on August 18, 2006
Best answer: The answer is no, but your question recalls the Amiga's ability to squeeze out a bunch of colors from a bit-limited palette through a process called hold and modify.
posted by herrdoktor at 9:20 PM on August 18, 2006
posted by herrdoktor at 9:20 PM on August 18, 2006
Ah. Interpreting the question as kindall has, the answer is "it depends". For most sufficiently large collections of completely independent zeros and ones, some sort of lossless compression scheme is possible.
It's most likely not possible for single bytes and words without a translation dictionary, however.
posted by tkolar at 9:24 PM on August 18, 2006
It's most likely not possible for single bytes and words without a translation dictionary, however.
posted by tkolar at 9:24 PM on August 18, 2006
If the states are independent, and if you want to be able to represent every possible combination of states, then the answer is no. It's not too hard to show this using a pigeonhole-style argument. There are 256 possible values for that 8-bit byte; there are 256 possible combinations of 8 binary states; each possible byte value can represent at most one combination-of-states. If you have more than 256 possible situations to represent, then you run out of byte values to represent them with.
But if your states aren't independent or you don't need to represent every possible combination, then you can squeeze more out of an 8-bit byte. The HAM mode that herrdoktor mentions is an example. In general, thinking along these lines leads you to data compression.
posted by hattifattener at 9:28 PM on August 18, 2006
But if your states aren't independent or you don't need to represent every possible combination, then you can squeeze more out of an 8-bit byte. The HAM mode that herrdoktor mentions is an example. In general, thinking along these lines leads you to data compression.
posted by hattifattener at 9:28 PM on August 18, 2006
tkolar: Lossless compression (that always compresses instead of expanding) is not, in fact, possible for a general input. It's only possible if you're willing to accept an expansion in some cases --- presumably, you use an algorithm that only produces an expansion for inputs you expect not to see.
posted by hattifattener at 9:30 PM on August 18, 2006
posted by hattifattener at 9:30 PM on August 18, 2006
Best answer: Both of the answers above would be correct, depending upon one's interpretation of your question.
It is possible to control 256 lights independantly with only 8 switches. You could use three types of gates to accomplish this: a gate that completes a connection if it is connected to a wire that is on, a gate that completes a connection if the switch is of, and an 8 to 1 AND gate that completes a circuit if all 8 inputs are 'on'. In a simplified implementation, each light would have 9 gates. The first light would have a series of OR and NOR gates which would correspond to the binary representation of the decimal digit '1'. (NOR NOR NOR NOR NOR NOR NOR OR), The second light would have the gates correspond to the decimal digit '2' (NOR NOR NOR NOR NOR NOR OR NOR), 33 (N N O N N N N O) and so on. Each of these 8 gates would then be connected to the 8 to 1 AND gate which would permit the light to turn on if all 8 connections or circuits were 'on'.
So my question to you would be: are your states detirmed by the on-or-off-ness of the switches, or by which light is currently lit?
posted by sleslie at 9:32 PM on August 18, 2006
It is possible to control 256 lights independantly with only 8 switches. You could use three types of gates to accomplish this: a gate that completes a connection if it is connected to a wire that is on, a gate that completes a connection if the switch is of, and an 8 to 1 AND gate that completes a circuit if all 8 inputs are 'on'. In a simplified implementation, each light would have 9 gates. The first light would have a series of OR and NOR gates which would correspond to the binary representation of the decimal digit '1'. (NOR NOR NOR NOR NOR NOR NOR OR), The second light would have the gates correspond to the decimal digit '2' (NOR NOR NOR NOR NOR NOR OR NOR), 33 (N N O N N N N O) and so on. Each of these 8 gates would then be connected to the 8 to 1 AND gate which would permit the light to turn on if all 8 connections or circuits were 'on'.
So my question to you would be: are your states detirmed by the on-or-off-ness of the switches, or by which light is currently lit?
posted by sleslie at 9:32 PM on August 18, 2006
hattifattener wrote...
Lossless compression (that always compresses instead of expanding) is not, in fact, possible for a general input.
What, "For most sufficiently large collections..." didn't include enough weasel words for you? :-)
Seriously, the questioner has asked if it's possible to store more than N-bits of information in N-bits. The answer is "most of the time, yes".
You might have to change which compression algorithm you use, but barring truly pathological input (I.E. already compressed or encrypted data), if the data set is large enough you can usually do it.
posted by tkolar at 9:43 PM on August 18, 2006
Lossless compression (that always compresses instead of expanding) is not, in fact, possible for a general input.
What, "For most sufficiently large collections..." didn't include enough weasel words for you? :-)
Seriously, the questioner has asked if it's possible to store more than N-bits of information in N-bits. The answer is "most of the time, yes".
You might have to change which compression algorithm you use, but barring truly pathological input (I.E. already compressed or encrypted data), if the data set is large enough you can usually do it.
posted by tkolar at 9:43 PM on August 18, 2006
Seriously, the questioner has asked if it's possible to store more than N-bits of information in N-bits.
The answer is that you can't, ever. It's possible that what appears to you to be N bits of data is actually less. There may patterns or redundant data in a data set that mean that that set can be represented in less that N bits but that just you had less than N bits of data to begin with.
posted by rdr at 10:12 PM on August 18, 2006
The answer is that you can't, ever. It's possible that what appears to you to be N bits of data is actually less. There may patterns or redundant data in a data set that mean that that set can be represented in less that N bits but that just you had less than N bits of data to begin with.
posted by rdr at 10:12 PM on August 18, 2006
C'mon ostranenie, explain what you want. tkolar is correct that you can represent 256 states or numbers with one byte. However, your assumption that there are only eight states is so far off the mark that you must be thinking of something else. What is it you are really asking?
posted by caddis at 12:05 AM on August 19, 2006
posted by caddis at 12:05 AM on August 19, 2006
(slight derail while we wait for ostranenie to get back to us)
rdr wrote...
The answer is that you can't, ever. It's possible that what appears to you to be N bits of data is actually less. There may patterns or redundant data in a data set that mean that that set can be represented in less that N bits but that just you had less than N bits of data to begin with.
Whoa. It's been a while since my last computational theory class, but that's a pretty radical definition of data that you're pushing there.
To use a real world example: you're saying that if I had 1024 bits of information representing the genders of 1024 people, if I could compress the stream of 1024 bits down to 768 bits, then I really only had 768 bits of data to begin with?
Do you happen to have a reference for this view? I remember various definitions for "bit" and "data" being put forth in my theory classes, but this one is not familiar to me. (as I say, it's been a long time)
posted by tkolar at 12:30 AM on August 19, 2006
rdr wrote...
The answer is that you can't, ever. It's possible that what appears to you to be N bits of data is actually less. There may patterns or redundant data in a data set that mean that that set can be represented in less that N bits but that just you had less than N bits of data to begin with.
Whoa. It's been a while since my last computational theory class, but that's a pretty radical definition of data that you're pushing there.
To use a real world example: you're saying that if I had 1024 bits of information representing the genders of 1024 people, if I could compress the stream of 1024 bits down to 768 bits, then I really only had 768 bits of data to begin with?
Do you happen to have a reference for this view? I remember various definitions for "bit" and "data" being put forth in my theory classes, but this one is not familiar to me. (as I say, it's been a long time)
posted by tkolar at 12:30 AM on August 19, 2006
Best answer: You can read 16 switches or write 16 lights in a 4x4 array if you allow time multiplexing. With two bytes you can access 64 switches or lights. That is, (N/2)^2.
posted by JackFlash at 12:34 AM on August 19, 2006
posted by JackFlash at 12:34 AM on August 19, 2006
To use a real world example: you're saying that if I had 1024 bits of information representing the genders of 1024 people, if I could compress the stream of 1024 bits down to 768 bits, then I really only had 768 bits of data to begin with?
"Data" is different than "information". If I store the string "male" or "female" in a data structure for, say, a customer in a database, I'm using 6 bytes of data (48 bits) to store just 1 bit of information.
Getting back to your example, assuming each person is male or female, the gender of 1024 random people is 1024 bits of information.
The obvious way, of course, to represent these 1024 bits of information are as 1024 bits of data.
However, assuming you know anything at all about the probable contents of the data, you can 'compress' it, by essentially constructing a lookup table which maps more probable data sets (e.g., 512 males and 512 females) to smaller-than-1024-bit representations. However, when you do this, you must pay the piper, and map less likely data sets (like, say, 1024 females) to larger-than-1024-bit representations. So, on average, with _expected_ data sets, you can 'win,' but in the worst case, you can lose. However, since the information you're expressing is 1024 bits, you cannot _guarantee_ that your representation will take up less than 1024 bits of data.
If you happen to _know_ that, say, there aren't more than 100 females in the group of 1024, then you actually have less than 1024 bits of information. (for example, if you know that only one person is female, you only have 10 bits of information.. the number, 0-1023, of the female.)
posted by blenderfish at 12:52 AM on August 19, 2006
"Data" is different than "information". If I store the string "male" or "female" in a data structure for, say, a customer in a database, I'm using 6 bytes of data (48 bits) to store just 1 bit of information.
Getting back to your example, assuming each person is male or female, the gender of 1024 random people is 1024 bits of information.
The obvious way, of course, to represent these 1024 bits of information are as 1024 bits of data.
However, assuming you know anything at all about the probable contents of the data, you can 'compress' it, by essentially constructing a lookup table which maps more probable data sets (e.g., 512 males and 512 females) to smaller-than-1024-bit representations. However, when you do this, you must pay the piper, and map less likely data sets (like, say, 1024 females) to larger-than-1024-bit representations. So, on average, with _expected_ data sets, you can 'win,' but in the worst case, you can lose. However, since the information you're expressing is 1024 bits, you cannot _guarantee_ that your representation will take up less than 1024 bits of data.
If you happen to _know_ that, say, there aren't more than 100 females in the group of 1024, then you actually have less than 1024 bits of information. (for example, if you know that only one person is female, you only have 10 bits of information.. the number, 0-1023, of the female.)
posted by blenderfish at 12:52 AM on August 19, 2006
to be clear, I'm agreeing with you tkolar (except by "768 bits of data to begin with", I think you meant "768 bits of information to begin with.")
posted by blenderfish at 12:58 AM on August 19, 2006
posted by blenderfish at 12:58 AM on August 19, 2006
To use a real world example: you're saying that if I had 1024 bits of information representing the genders of 1024 people, if I could compress the stream of 1024 bits down to 768 bits, then I really only had 768 bits of data to begin with?
Yes.
Let's say you flip an unbiased coin 1024 times. You will have 1024 bits of information. But what if the coin is weighted, so you get heads 2/3 of the time and tails 1/3? Then you will be able to compress the results down to less than 1024 bits, and so you will really have less than 1024 bits of information.
It's the same with genders of people. If you could compress the data down to 768 bits, then the data must not be completely random. You "really" only have 768 bits of information (or less!).
To know how much information you have you cannot just count how much data you have. You have to factor in expected patterns/probabilities. Consider the extreme case of coin flipping, where the probability of a head is 1 and the probability of a tail is 0. You will get a head every time you flip the coin. You can flip that coin all day long and you will not be gathering any new information. If you flipped it 1024 times, and had 1024 bits of data, you would have 0 bits of information. 0 bits.
posted by Khalad at 5:56 AM on August 19, 2006
Yes.
Let's say you flip an unbiased coin 1024 times. You will have 1024 bits of information. But what if the coin is weighted, so you get heads 2/3 of the time and tails 1/3? Then you will be able to compress the results down to less than 1024 bits, and so you will really have less than 1024 bits of information.
It's the same with genders of people. If you could compress the data down to 768 bits, then the data must not be completely random. You "really" only have 768 bits of information (or less!).
To know how much information you have you cannot just count how much data you have. You have to factor in expected patterns/probabilities. Consider the extreme case of coin flipping, where the probability of a head is 1 and the probability of a tail is 0. You will get a head every time you flip the coin. You can flip that coin all day long and you will not be gathering any new information. If you flipped it 1024 times, and had 1024 bits of data, you would have 0 bits of information. 0 bits.
posted by Khalad at 5:56 AM on August 19, 2006
The problem here is the ambiguity of the word "states".
You can represent *1 state*, which can have any of 256 values, *8 states*, each either true or false, or any binary combination thereof.
But you can only fit 8 bits of information into one byte, no matter how you slice it.
Unless it's an old Honeywell, in which case your bytes were 9 bits long.
posted by baylink at 9:06 AM on August 19, 2006
You can represent *1 state*, which can have any of 256 values, *8 states*, each either true or false, or any binary combination thereof.
But you can only fit 8 bits of information into one byte, no matter how you slice it.
Unless it's an old Honeywell, in which case your bytes were 9 bits long.
posted by baylink at 9:06 AM on August 19, 2006
Let's say you flip an unbiased coin 1024 times. You will have 1024 bits of information. But what if the coin is weighted, so you get heads 2/3 of the time and tails 1/3? Then you will be able to compress the results down to less than 1024 bits.
Not true. Even though probabilities have shifted, all possible combinations can still occur, so it is impossible to guarantee compression below 1024 bits, based on a simple application of the Pidgeonhole Priniciple.
Of course, the entropy is lower, so on average you will be able to represent the state with fewer than 1024 bits. If we define information as 'entropy', and add 'on average' to your statement, it is more accurate.
posted by blenderfish at 4:59 PM on August 19, 2006
Not true. Even though probabilities have shifted, all possible combinations can still occur, so it is impossible to guarantee compression below 1024 bits, based on a simple application of the Pidgeonhole Priniciple.
Of course, the entropy is lower, so on average you will be able to represent the state with fewer than 1024 bits. If we define information as 'entropy', and add 'on average' to your statement, it is more accurate.
posted by blenderfish at 4:59 PM on August 19, 2006
What, "For most sufficiently large collections..." didn't include enough weasel words for you? :-)Right. :-) Because the size of the collection isn't relevant. What's relevant is that you know ahead of time that certain members of the collection are more probable than others, and that you're willing to accept either an expansion or a complete failure of the algorithm for the less-common inputs, in return for a compression of the more-common inputs.
Take sleslie's 1-of-N example. You have 256 lights, which should normally take 256 bits to represent. But by disallowing all situations in which more than one (or fewer than one) of the lights are lit, you can represent the relatively few remaining situations using only 8 bits. But if you try to represent a situation in which two lights are lit, then you simply can't do it.
All compression algorithms work like this. Fortunately, there are some kinds of redundancy which are very very common in real-world data, which means that there are "general-purpose" compression algorithms like LZW or bzip that compress most real-world inputs, and produce only small expansions for the rest.
posted by hattifattener at 6:05 PM on August 19, 2006
Of course, the entropy is lower, so on average you will be able to represent the state with fewer than 1024 bits. If we define information as 'entropy', and add 'on average' to your statement, it is more accurate.
Damn, I knew I'd get called out on that.
posted by Khalad at 6:50 PM on August 19, 2006
Damn, I knew I'd get called out on that.
posted by Khalad at 6:50 PM on August 19, 2006
« Older Sightseeing on the Garden Route | What are some positive hip hop songs to play for... Newer »
This thread is closed to new comments.
2^16 and 2^32 in 16 bit and 32 bit words respectively.
Perhaps I'm not understanding the question?
posted by tkolar at 9:14 PM on August 18, 2006