Is there any way to use half-bits?

Question

As most people here know, by using 4 bits, we are able to count from 0 to 15 (0123456789ABCDEF in hexadecimal). But if we were to only count up to 9, we would still be using 4 bits, and the digits from A through F would be wasted.

However, Wikipedia's QR-Code page states that using only numerical digits from 0 to 9 uses 3⅓ bits per character, which is correct from a statistical stand point. And yet a third of a bit is not a physical object, and sending a number from 0 to 9 uses at least 4 bits to my knowledge.

Is there any way to use the wasted combinations to effectively send a character with fractions of bits?

OK, let me give an example: The two digits "27" must be sent. With normal coding techniques, the bits sent would be 00100111. We could then imagine a system that would replace the digit '2' by the digit 'E' or 'F', depending on the next bit; in this case the next bit is 0, so the '2' is replaced by 'E'. The resulting bit-string would then be 11010111. On the other hand if the digits "28" must be sent, the first bit after the '2' is a 1, so it is replaced by the digit 'F' instead, yielding the string 11111000.

In both case, an economy of 1 bit has been effected, because one nibble was used for two different characters. In other word, three and a half bits are used on each character.

Answer 1

You can't send half a bit, but you can effectively pack two half bits in one bit before transmission or storage.

You give an example yourself, so you effectively have answered your own question with a YES.

A maybe somewhat easier way is to simple encode the value of two decimal digits in 7 bits. (Sort of binary coded dual-decimal).

Answer 2

You can use huffman coding so the numbers are with varying bit length. if you are aware of a digit that will occur more often than others it will help.

example(with equal occurrence):

0 - 1111

1 - 1110

2 - 110

3 - 101

4 - 100

5 - 011

6 - 010

7 - 001

8 - 000

receiving-end example for getting the number 1:

The first bit comes in and leaves only 0 to 4 as options.

the second bit comes in and leaves only 0 to 2 as options.

the third bit comes in and leaves 0 to 1 as options.

the forth bit comes in and the incoming number is 1

Answer 3

Perhaps what you are looking for is Arithmetic Coding, which can efficiently encode a string of symbols, each of which in principle might require a fractional (non-integer) number of bits. (though the total message must be a whole number of bits)

Quoting Wikipedia:

Arithmetic coding differs from other forms of entropy encoding such as Huffman coding in that rather than separating the input into component symbols and replacing each with a code, arithmetic coding encodes the entire message into a single number, a fraction n where (0.0 ≤ n < 1.0).

Answer 4

The new IEEE P754 for floating point arithmetic now defines decimal formats in addition to binary. One of the encoding proposes to group digital digits by 3 into 10 bits.

encoding 0 to 999 using 10bits = 1024 possible codes is quite efficient, and decimal digits are often grouped by three anyway.

Densely Packed Decimal : http://en.wikipedia.org/wiki/Densely_packed_decimal

Answer 5

A 1:1 correspondence of binary (or Hexadecimal) is but one symbol encoding for bits. So yes, as you showed it is possible. Another place this is used is (but slightly differently) is in trellis encoding/decoding in communication systems in which bit transitions are kept farther apart to ease the decoding. And of course 8b/10b and 64b/66b etc. etc. encoding is a similar idea, in which a smaller symbol space is encoded in a slightly redundant larger space to get DC balance, symbol separation and control codes in sub-bands.

Answer 6

Data representation depends on the interpretation you or your program gives to it.

We could send '27' also as ASCII characters, for example, yielding 0x3237 = 0b0011001000110111.

The way you want to represent the data in bits depends on your application. In the end, with a variable \$x\$ with \$n(x)\$ different possible values, you're going to need \${\lceil\log_2{n(x)}\rceil}\$ bits.

Now suppose you have two variables \$x_1,x_2\$ with \$n(x_1),n(x_2)\$ possible values. If you store them separately, you're going to need \$\lceil\log_2n(x_1)\rceil+\lceil\log_2n(x_2)\rceil\$ bits. However, if you store them together, you will need only \$\left\lceil\log_2\left(n(x_1)\cdot n(x_2)\right)\right\rceil\$ bits.

In your example with sending two digits, both digits can have 10 different values. If you store them separately, you need \$2\cdot\lceil\log_2(10)\rceil=2\cdot4=8\$ bits. If you store them together however, you need \$\lceil\log_2(10\cdot10)\rceil=7\$ bits.

It always depends on the application, but normally when you 'join' variables like you suggest, it's going to cost more computational power if you want to perform operations on these variables. Adding and subtracting operations on 'joined' variables are more complex than normally, and may require more space in hardware, or cause longer delays.

---

Note: \$\lceil\dots\rceil\$ is the notation for rounding up.

Answer 7

The usual way to pack values is by multiplying each value with its range, so you end up with one large number that you can efficiently represent in bits. When unpacking you divide by range, the remainder is the digit, and the result is the remaining packed digits.

If you have 5 values in the range of 0 to 2, you can represent that in 8 bits (you need at least 7.92 bits to represent the values) instead of the 10 bits used by the naive way of using 2 bits for each value, by doing (((n₁ * 3 + n₂) * 3 + n₃) * 3 + n₄) * 3 + n₅

Answer 8

In theory, if you're willing to spend circuit space and power for the high-impedance detector you can send 3 states down a digital wire (1, 0, and high-Z). Disclaimer: this works great in the simulator. I don't know if the circuit has some problems that make it impractical, like say it can't really switch as fast as a normal pair of gates.

My normal term for a signal transition from high-Z to signal (where signal is usually ground in silicon) is a half-bit signal.

Answer 9

I think you're misunderstanding what is meant in the linked wiki article. What is meant is that for a string of characters that is completely numeric (without spaces, commas, or periods), using ideal compression, you can represent each character using 3 ¹/₃ bits on average. Actually, it's a bit better than this, since the math says you can get log₂(10) = 3.3219 bits/character in the long run.

Similarly, for the set of alphanumeric plus some symbols (uppercase only, and 9 symbols), or 45 characters, you need log₂(45) = 5.4918 bits/character, which is rounded up to 5.5 in the article.

The reduced bits/character is achieved using compression, either with a preset encoding or a compression scheme specified by the QR standard (I'm not sure which is used). It represents the average number of bits a character will need in order to be encoded, so an individual character will be encoded using more or less bits. Also realize the values listed above are the ideal values for infinite, random strings. It's possible to get compression ratios that are better or worse for specially crafted strings.

Answer 10

You want to send one decimal digit, needing 3⅓ bits. But you will have to use 4 bits, because you can't send a third of a bit.

So, to find out what 3⅓ bits really means, you need two (or three) digits of 3⅓ bits each. If you want to send 2 (3) decimal digits between 0 and 9, each needing slightly less than 3⅓ bits, you can do so using 7 (10) bits. Constructive proof is easy:

7 (10) bits allow you to encode a number between 0 and 128 (1023) - but you will only need 00 (000) to 99 (999), which are all possible encodings of two (three) decimal digits. Q.E.D.