[Next] [Up] [Previous] [Index]

Decimal Armor

Since

 2^93 =  9,903,520,314,283,042,199,192,993,792 and, of course,
10^28 = 10,000,000,000,000,000,000,000,000,000

twenty-eight digits can represent 93 bits with fairly good efficiency.

The method devised by IBM for representing three decimal digits in 10 binary bits which we saw previously will serve as part of the basis for doing this.

Encoding 3 Digits in 10 Bits

Let ooo (or ppp, qqq) represent a digit from 0 to 7 represented by the following code:

000  0
001  1
010  2
011  3
100  4
101  5
110  6
111  7

and let d (or e, f) represent a digit from 8 to 9 in the following code:

0    8
1    9

then, any three decimal digits can be represented within 10 bits as follows:

0ooopppqqq (3 digits with 3 bits - 1 way)
100dpppqqq (2 digits with 3 bits, 1 digit with 1 bit - 3 ways)
101oooeqqq
110ooopppf
11100deqqq (1 digit with 3 bits, 2 digits with 1 bit - 3 ways)
11101dpppf
11110oooef
1111100def (3 digits with 1 bit - 1 way)

with 24 unused combinations remaining.

As, again, previously noted, the table illustrating the decimal to binary code is based on ooo, ppp, and qqq representing the first, second, and third digits respectively (if they are from 0 to 7) and on d, e, and f representing the first, second, and third digits respectively if they are instead either 8 or 9. This same notational convention will be used in outlining the method to be explained on this page.

Since 2^10 is 1,024, slightly greater than a power of 10, this method cannot serve directly for storing binary bits in decimal digits; it is instead useful for performing the reverse task of storing decimal digits in binary bits.

The coding scheme I propose works as follows:

oAAABBBCCCDDDEEEFFFGGGHHHIII

Here, o represents a digit from 0 to 7, representing the first three bits of the 93 bits to be represented. AAA through III each represent three digits, from 000 to 999, representing 10 bits of the 93 bits to be represented, provided that each group of 10 bits belongs to one of the 1,000 codes out of 1,024 that can be so represented.

nnn0BBBCCCDDDEEEFFFGGGHHHIII
nnn1AAACCCDDDEEEFFFGGGHHHIII
nnn2AAABBBDDDEEEFFFGGGHHHIII
nnn3AAABBBCCCEEEFFFGGGHHHIII
nnn4AAABBBCCCDDDFFFGGGHHHIII
nnn5AAABBBCCCDDDEEEGGGHHHIII
nnn6AAABBBCCCDDDEEEFFFHHHIII
nnn7AAABBBCCCDDDEEEFFFGGGIII
nnn8AAABBBCCCDDDEEEFFFGGGHHH

Here, nnn is a series of three digits from 800 to 999. This involves 200 possible values, 192 of which are used, to represent the 8 possible values of the first three bits of the 93 to be encoded, times 24 possible values for one of the groups of 10 bits in the remaining 90 bits. The value will be generated by the formula 800 + 24 * a + b, where a is the value of the first three bits from 0 to 7, and b is a number from 0 to 23 representing each of the 10 bit codes, which did not correspond to three digits in the coding of three digits to ten bits given above, in the numerical order of these codes, as shown in the table below:

 0 1111101000
 7 1111101111
 8 1111110000
15 1111110111
16 1111111000
23 1111111111

Thus, these codes cover the case where exactly one of those groups has one of the 24 values which is not covered by the first encoding. Once we cover all possible cases where any combination of those groups, even all of them, can have such a value, we will have our complete encoding of 93-bit values into decimal digits. Note that the eight nnn values of 992 through 999 are not used so far.

nnn90ppCCCDDDEEEFFFGGGHHHIII (00)   nnn95ppAAABBBCCCDDDEEEHHHIII
       BBBDDDEEEFFFGGGHHHIII (25)          BBBCCCDDDEEEFFFGGGIII
       AAADDDEEEFFFGGGHHHIII (50)          AAACCCDDDEEEFFFGGGIII
       BBBCCCEEEFFFGGGHHHIII (75)          AAABBBDDDEEEFFFGGGIII
nnn91ppAAACCCEEEFFFGGGHHHIII        nnn96ppAAABBBCCCEEEFFFGGGIII
       AAABBBEEEFFFGGGHHHIII               AAABBBCCCDDDFFFGGGIII
       BBBCCCDDDFFFGGGHHHIII               AAABBBCCCDDDEEEGGGIII
       AAACCCDDDFFFGGGHHHIII               AAABBBCCCDDDEEEFFFIII
nnn92ppAAABBBDDDFFFGGGHHHIII        nnn97ppBBBCCCDDDEEEFFFGGGHHH
       AAABBBCCCFFFGGGHHHIII               AAACCCDDDEEEFFFGGGHHH
       BBBCCCDDDEEEGGGHHHIII               AAABBBDDDEEEFFFGGGHHH
       AAACCCDDDEEEGGGHHHIII               AAABBBCCCEEEFFFGGGHHH
nnn93ppAAABBBDDDEEEGGGHHHIII        nnn98ppAAABBBCCCDDDFFFGGGHHH
       AAABBBCCCEEEGGGHHHIII               AAABBBCCCDDDEEEGGGHHH
       AAABBBCCCDDDGGGHHHIII               AAABBBCCCDDDEEEFFFHHH
       BBBCCCDDDEEEFFFHHHIII               AAABBBCCCDDDEEEFFFGGG
nnn94ppAAACCCDDDEEEFFFHHHIII
       AAABBBDDDEEEFFFHHHIII
       AAABBBCCCEEEFFFHHHIII
       AAABBBCCCDDDFFFHHHIII

Here, nnn represents the first 3 bits, and the additional combination from the set of 24 from the first of the two groups of 10 bits that are of that form. pp, a series of two digits from 00 to 99, has 100 possible values, 96 of which are used to represent the combination from the set of 24 from the second of the two groups of 10 bits, and which of the 4 arrangements of which groups of 10 bits have these additional codes allocated to the current numeric code is present. The numbers in parentheses after the first set of four arrangements show the displacements to be added in the pp field to the number from 0 to 23 containing the information about the second group with an auxilliary value.

nnn990ppqqDDDEEEFFFGGGHHHIII (00 00)
          CCCEEEFFFGGGHHHIII (00 25)
          BBBEEEFFFGGGHHHIII (00 50)
          AAAEEEFFFGGGHHHIII (00 75)
          CCCDDDFFFGGGHHHIII (25 00)
          BBBDDDFFFGGGHHHIII (25 25)
          AAADDDFFFGGGHHHIII (25 50)
          BBBCCCFFFGGGHHHIII (25 75)
          AAACCCFFFGGGHHHIII (50 00)
          AAABBBFFFGGGHHHIII (50 25)
          CCCDDDEEEGGGHHHIII (50 50)
          BBBDDDEEEGGGHHHIII (50 75)
          AAADDDEEEGGGHHHIII (75 00)
          BBBCCCEEEGGGHHHIII (75 25)
          AAACCCEEEGGGHHHIII (75 50)
          AAABBBEEEGGGHHHIII (75 75)
nnn991ppqqBBBCCCDDDGGGHHHIII
          AAACCCDDDGGGHHHIII
          AAABBBDDDGGGHHHIII
          AAABBBCCCGGGHHHIII
          CCCDDDEEEFFFHHHIII
          ...
nnn995ppqqAAABBBCCCEEEFFFGGG
          AAABBBCCCDDDFFFGGG
          AAABBBCCCDDDEEEGGG
          AAABBBCCCDDDEEEFFF

Now we are dealing with the case where three of the nine groups of ten bits have a representation from the additional 24 combinations. Together, pp and qq mean that sixteen different arrangements of these three groups can be indicated. The displacements added to pp and qq are noted in the parentheses after the first group of 16 combinations. One additional digit lets us cope with 160 possibilities, but in fact we only need to worry about 84 possibilities.

nnn9990ppqqrrEEEFFFGGGHHHIII (00 00 00)
             DDDFFFGGGHHHIII (00 00 25)
             CCCFFFGGGHHHIII (00 00 50)
             BBBFFFGGGHHHIII (00 00 75)
             AAAFFFGGGHHHIII (00 25 00)
             DDDEEEGGGHHHIII (00 25 25)
             CCCEEEGGGHHHIII (00 25 50)
             CCCDDDGGGHHHIII (00 25 75)
             ...
             BBBCCCEEEGGGIII (75 75 75)
nnn9991ppqqrrBBBCCCDDDGGGIII
             CCCDDDEEEFFFIII
             BBBDDDEEEFFFIII
             BBBCCCEEEFFFIII
             BBBCCCDDDFFFIII
             BBBCCCDDDEEEIII
             DDDEEEFFFGGGHHH
             ...
             AAABBBCCCDDDEEE

Here, four of the nine groups of ten bits use one of the additional codes. This involves 126 possibilities. pp, qq, and rr together allow sixty-four combinations to be indicated, so the additional digit need only be either 0 or 1.

nnn99990ppqqrrssFFFGGGHHHIII
nnn999990ppqqrrssttGGGHHHIII
nnn9999990ppqqrrssttuuHHHIII
nnn99999990ppqqrrssttuuvvIII
nnn999999990ppqqrrssttuuvvww

And there is no problem continuing the encoding, without needing to go back and use the eight unused nnn values, since we are now dealing with 126, 84, 36, 9, and 1 combinations again, which we have already seen comfortably fits in the space available, and we now have even more space with more two-digit fields, each of which contributes a factor of four.


[Next] [Up] [Previous] [Index]

Next
Table of Contents
Home Page