19
\$\begingroup\$

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.

\$\endgroup\$
  • 2
    \$\begingroup\$ For a different perspective on packing values in a smaller digit-space, check out Ternary computers (en.wikipedia.org/wiki/Ternary_computer) If it's good enough for Knuth, it's good enough for me! \$\endgroup\$ – RLH Nov 24 '14 at 19:25
  • 3
    \$\begingroup\$ Better still to recognize that you can compute (10 * first_digit) + second_digit and encode that into 7 bits, representing 0...99, with the codes 100-127 left over for other things. And there's even more savings with 3 digits compressed into 10 bits. \$\endgroup\$ – Hot Licks Nov 24 '14 at 20:59
  • \$\begingroup\$ To send all 100 different values separately, the best you can get is packing into 7 bits. If you have more digits the packing will be more efficient. If you have less than 64 values to send you can send it using only 6 bits \$\endgroup\$ – phuclv Nov 25 '14 at 4:43

10 Answers 10

22
\$\begingroup\$

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).

\$\endgroup\$
  • 1
    \$\begingroup\$ One nice usage case for packing pairs of digits into seven bits is when transmitting ASCII files that consist of mostly-numeric data. Any byte value below 128 represents a single ASCII character, while 128-227 represent two ASCII digits. Easy to encode or decode, and doesn't require that data contain mostly digits (or even any digits), but can compress strings of digits by 50% very easily. \$\endgroup\$ – supercat Nov 22 '14 at 21:36
  • \$\begingroup\$ Or that PDP11 format that packed 3 alphanumeric characters into 16 bits with one bit spare... \$\endgroup\$ – Brian Drummond Nov 23 '14 at 22:25
  • \$\begingroup\$ @BrianDrummond: One could use 16 bits to store exactly three characters from a set of 40, or up to three from a set of 39, but there wouldn't be a spare bit. Normally "alphanumeric" would imply a set of at least 36, but the only way there would be a spare bit would be if the set was limited to 32. \$\endgroup\$ – supercat Nov 25 '14 at 20:22
  • \$\begingroup\$ I thought it was 5 bits/char. Alphanumeric was split across two codesets, with one symbol reserved for "switch code set". I was wrong : en.wikipedia.org/wiki/DEC_Radix-50 Freaky enough though, only saw it one night when I had to decode a report someone gave me on 8" floppy, on a CP/M system, with only a dim recollection of Z80 asm. \$\endgroup\$ – Brian Drummond Nov 25 '14 at 20:24
19
\$\begingroup\$

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

\$\endgroup\$
12
\$\begingroup\$

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).

\$\endgroup\$
10
\$\begingroup\$

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

\$\endgroup\$
  • \$\begingroup\$ Even if decimal digits are grouped by three, correct decimal-floating-point semantics may require that either (1) scaling a mantissa by non-multiple-of-three power of ten entails multiplying or dividing all constituents by 10 or 100; (2) some bits can be used for either the upper or lower portion of the number, depending upon (exponent mod 3); (3) If the exponent is stored base-1000, then the bottom group of three digits may sometimes have to be rounded to the nearest 10 or the nearest 100, rather than the nearest unit. \$\endgroup\$ – supercat Nov 22 '14 at 21:29
  • \$\begingroup\$ I personally believe that types like BigDecimal would for many purposes be more efficient if each word held 9 decimal digits rather than 32 bits, but rounding behaviors should not be affected by digit grouping. \$\endgroup\$ – supercat Nov 22 '14 at 21:32
4
\$\begingroup\$

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.

\$\endgroup\$
4
\$\begingroup\$

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.

\$\endgroup\$
2
\$\begingroup\$

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 (((n1 * 3 + n2) * 3 + n3) * 3 + n4) * 3 + n5

\$\endgroup\$
  • \$\begingroup\$ Is there a name for this method of encoding? \$\endgroup\$ – Keegan Jay Mar 27 at 23:10
1
\$\begingroup\$

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.

\$\endgroup\$
1
\$\begingroup\$

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.

\$\endgroup\$
1
\$\begingroup\$

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 1/3 bits on average. Actually, it's a bit better than this, since the math says you can get log2(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 log2(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.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.