Binary to decimal coder/decoder

Details Binary to decimal coder/decoder Binary to decimal coder/decoder

2002-05-20

2003-02-25

Young, Brian (Department: 2819)

Coded data generation or conversion

Digital code to digital code converters

Binary to decimal

C341S065000, C341S067000, C341S105000

Reexamination Certificate

active

06525679

ABSTRACT:

FIELD OF THE INVENTION
The present invention relates to converting from decimal numbers to binary numbers and vice versa, particularly for use in computing systems and such like.
BACKGROUND OF THE INVENTION
Human mathematics is largely based on the decimal system, presumably due to the biological fact (or accident) that we have five fingers on each of two hands. In contrast, for physical reasons, modern digital computer systems use binary numbers for their internal processing, with a one represented by the presence of a signal, and zero by the absence of a signal (or vice versa). Consequently most numerical input data will be presented to a computer in decimal form. This must then be converted to binary for processing, and them converted back to decimal for output.
There are several known methods of representing decimal numbers as binary numbers. If we simply are considering integers, then clearly there is a direct mapping from a decimal integer to its corresponding binary integer (for example 235 goes to 11101011). Moving on to real numbers, possibly the most natural approach is to introduce a “decimal” point into a binary number, so that the first digit to the right of the “decimal” point represents ½, and the nth digit
½n. One problem with this approach is that
0.1 (in decimal) is a recurring fraction in binary, and so cannot be represented exactly. This leads to the possibility of rounding errors, which can be exacerbated by repeated conversions from decimal to binary and back again.
A slightly different approach is to extend the integer representation to cope with real numbers by separately recording a decimal point position using an integer exponent (this can be regarded as floating point real numbers rather than fixed point). Thus 235 could 23.5, 2.35, 0.235 etc according to the value of the exponent. This overcomes the recurring fraction problem mentioned above, but is still not completely satisfactory. The conversion between binary and decimal is not particularly simple in terms of hardware design (this sort of facility is nearly always provided in hardware for speed). The reason for this in general terms is that such conversion requires binary addition rather than simple bit manipulation. Also, it is relatively common to have to truncate or round decimal numbers for output, and there is no quick way of performing in such truncation or rounding with this coding technique (ie without first performing a conversion of a full number). For example 01111111, as representing 1.27 with a suitable exponent, rounds to 1.3, but 01111100, representing 1.24, round to 1.2.
One way around these problems is to use binary coded decimal. Here each decimal digit (0-9) is encoded by a corresponding four bit binary number, so that a sequence of decimals digits can then be represented by concatenating the four-bit binary numbers. This allows quick retrieval of any given decimal digit independently from the others, and so provides for simple rounding and truncation. However, this has been achieved at the expense of a significant loss of storage efficiency. Thus potentially four bits can store 0-15, rather than 0-9.
We can formally measure storage efficiency by observing that the number of digits N
r
need to store an integer X using base r goes as N
r
|log
r
(X). Asymptotically therefore (ie for very large numbers) the ratio of digits used for binary storage of a given number to decimal storage of that number is
N
2
N
10
|log
2
(X)/log
10
(X)
|(log
10
(X) log
10
(2)/log
10
(X)
|1/log
10
(2)|/3:322
Since binary coded decimal has a ratio of 4 between the number of binary digits and the number of decimal digits, this gives an efficiency of only 3.322/4=0.83. Expressed another way, a 32 bit system, which in theory could store 4,294,967,295 as a binary integer, can now only store 99,999,999 as a decimal integer, a reduction in terms of maximum number of a factor |40. In order to overcome this deficiency, a sort of hybrid algorithm was developed by Chen and Ho (see Communications of the ACM, January 1975, v18/1, p49-52). This is based on the fact that 2
10
=1024|10
3
(this correspondence of course underlies all computer storage sizings—thus 8 kBytes really corresponds to 8*1024 Bytes rather than 8000 Bytes). Accordingly, the Chen-Ho algorithm takes three decimal digits, and then encodes them into 10 binary bits. This allows relatively quick retrieval of the decimal digits in any given location, by simply decoding the corresponding 10 binary bits, but retains a high (asymptotic maximum) storage efficiency of 3.322/(10/3)=99.66%.
The Chen-Ho algorithm is best understood as a mapping from a decimal coded binary number having 12 bits, corresponding to 3 decimal digits each represented by 4 binary bits, into a 10 bit binary number. Thus the input to the algorithm can be written as (abcd), (efgh), (ijkl), where each bracketed group of four letters corresponds to the decimal coded binary representatives of the equivalent decimal digit. The 10 output bits can then be denoted as pqrstuvwxy. The details of the mapping from the input string to the output string are set out in Table 1 below.
TABLE 1
a
e
i
p
q
r
s
t
u
v
w
x
y
0
0
0
0
b
c
d
f
g
h
j
k
l
1
0
0
1
0
0
d
f
g
h
j
k
l
0
1
0
1
0
1
d
b
c
h
j
k
l
0
0
1
1
1
0
d
f
g
h
b
c
l
0
1
1
1
1
1
d
0
0
h
b
c
l
1
0
1
1
1
1
d
0
1
h
f
g
l
1
1
0
1
1
1
d
1
0
h
j
k
l
1
1
1
1
1
1
d
1
1
h
0
0
1
The Chen-Ho algorithm is based on the observation that decimal digits 0-7 can be encoded in 3 binary bits; these decimal digits are therefore considered as “small”, whilst decimal digits 8 and 9 are considered as “large”. If a decimal digit is small, then its first bit (when represented in binary) is zero; if it is large, then its first bits is one, but the next two bits are always zero (since individual numbers above 9 are not required in the decimal system). Thus the first bit for each binary coded decimal determines whether the number is small (zero) or large (one), and is known as the indicator bit. For three decimal digits there are a total of 2
3
=8 possibilities as to the values of the three indicator bits, and these correspond to the 8 lines in Table 1. In other words, which line of the table is used to perform the mapping depends on the values of the indicator bits. If all three decimal digits are small (51.2% of possibilities), corresponding to the first line in the table, then this is indicated by a 0 in the p output position. The remaining 9 bits are then divided into three groups of 3, which indicate in standard fashion the value of each of the decimal digits (these must all be in the range 0-7, since all of the decimal digits are small). If just one of the decimal digits is large (38.4% of possibilities), then p is set to 1. The next two bits (q and r) are then set to 00, 01, or 10, to indicate which of the three decimal digits is large (the first, second or third respectively). The remaining 7 bits are split up into two groups of 3, to encode the two small digits, plus 1 additional bit to encode the large digit. (It will be appreciated that since there are only two possibilities for a large decimal, 8 or 9, then the actual value can be represented by a single bit, corresponding to the final bit in the binary coded digital—ie d, h or l as appropriate).
If two of the decimal digits are large (9.6% of possibilities), then p, q, and r are all set to 1. A further two bits (t and u) are then set to 00, 01, 10 to indicate the position of the one small decimal digit (first, second or third digit). This leaves a final 5 bits, of which 3 are used to encode the one small digit, and each of the remaining 2 bits is assigned to one of the two large digits.
Finally, if all three of the decimal digits are large (0.8% of possibilities) then p, q, r, t and u are all set to 1. If the remaining 5 bits, three are used to encode one each of the three large digits, and the remaining two (w and x) are set to zero.
An appropriate decoding algorithm for going back from Chen-Ho to binary coded decimal

Affiliated with

Also associated with

Rating

Binary to decimal coder/decoder does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Binary to decimal coder/decoder, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Binary to decimal coder/decoder will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-3143167