Abstract:
Disclosed herein are various embodiments of circuitry and methods to convert from a binary value to a BCD value.

Description:
BACKGROUND 
   The present invention relates generally to conversion from a binary number to a binary coded decimal (BCD) number. 
   Present-day processors provide hardware support for binary floating-point computation. While this format is suitable for general-purpose applications, it is typically not well suited for financial, commercial applications because the decimal data cannot be exactly represented with binary floating-point values. That is, binary floating-point numbers can only approximate many decimal numbers. For example, the value (0.1) would need an infinitely recurring binary fraction. In contrast, a decimal number system can represent 0.1 exactly, as one tenth (i.e., 10 −1 ). Consequently, binary floating-point, in many cases, cannot be used for financial calculations or for any calculations where the results achieved are required to match those which might be calculated by hand. This problem is avoided by using base ten (decimal) exponents and preserving those exponents where possible. 
   Unfortunately, many existing BCD techniques are inefficient to implement. For example, computation of the digits, d n , d n−1 , d n−2  . . . d 1 , d 0  is generally done by division of the number by 10, 10 2 , 10 3 , 10 4  . . . etc., with quotient and remainder computations at each stage. These operations are difficult to implement in hardware due to the need for an explicit integer divider. Accordingly, an improved BCD approach is desired. 

   
     BRIEF DESCRIPTION OF THE DRAWINGS 
     Embodiments of the invention are illustrated by way of example, and not by way of limitation, in the figures of the accompanying drawings in which like reference numerals refer to similar elements. 
       FIG. 1  is a diagram representing conversion of a 7-bit binary value to two, 4-bit binary-coded-decimal (BCD) values. 
       FIG. 2  is a flow diagram showing a routine for converting a seven-bit binary value to two 4-bit BCD values in accordance with some embodiments. 
       FIG. 3  shows a conversion circuit for implementing the routine of  FIG. 2  in accordance with some embodiments. 
       FIG. 4  is a circuit for implementing a seven-bit carry chain merged with a four-bit summer for the circuit of  FIG. 3  in accordance with some embodiments. 
   

   DETAILED DESCRIPTION 
   In some embodiments, a recursive approach for implementing binary-to-BCD conversion is presented. A divide and conquer approach may be used by recursively approximating the quotient using divisions by a power of 2, instead of powers of 10. This is easier to implement in hardware and in some embodiments, can have the advantage of lower area, lower power, and higher performance. 
     FIG. 1  graphically depicts a binary to BCD conversion of a 7-bit binary value X ( 101 ) to 2 4-bit BCD values D 1 , D 0  ( 103 ,  105 ). The binary value X has seven bits, X 0  to X 6 , in order from least to most significant bits. The BCD result has two digits, D 1  and D 0 , respectively comprising D 3,1  to D 0,1  and D 0,3  to D 0,0 . 
   The 7-bit binary number X ranges in decimal terms from 0 to 99. D 1  is the quotient of X divided by 10, and D 0  is the remainder. It has been discovered that D 1  and D 0  can be derived in the following manner. 
   Preliminary values, D′ 1  and D′ 0  are initially derived and from there, the final values, D 0  and D 1 , can be found. D′ 1 , equals X/16+X/32+Bias, where the Bias is 2 if X 3 =X 4 =1 or 1 otherwise. Stated differently, D′ 1  is: X shifted by four bits (X&gt;&gt;4)+X shifted 5 bits (X&gt;&gt;5)+[2 (if X 3 =X 4 =1) or 1 (otherwise)]. D′ 0  is: X−10 D 1 . If D′ 0  is a positive value, then D 0 =D′ 0  and D 1 =D′ 1 . On the other hand, if D′ 0  is negative, then D 1 =D′ 1 −1 and D 0 =D′ 0 +10. 
     FIG. 2  shows a routine  200  to implement this approach in accordance with some embodiments. At  202 , it determines if the fourth and fifth least significant bits of X (X 4  and X 3 ) equal 1. If so, then at  206 , D′ 1  gets (X&gt;&gt;4)+(X&gt;&gt;5)+2. From here, at  208 , D′ 0  gets X+10 D′ 1 . At  210 , it is determined if D′ 0  is negative. If so, then at  214 , the final value D 1  gets D′ 1 −1 and D 0  gets D′ 0 +10. 
   Returning back to  202 , if X 3  and X 4  are not both equal to ‘1, then at  204 , D′ 1  instead gets (X&gt;&gt;4)+(X&gt;&gt;5)+1. From here, it goes to  208  and proceeds as just discussed until D 1  and D 0  are derived. (It should be appreciated that this routine need not be performed exactly, e.g., in the same order as shown in  FIG. 2 . For example, initial D′ 1  and D′ 0  values could be determined prior to determining if X 4  and X 3  equal ‘1. Along these lines, this routine could be performed using a variety of different circuits including dedicated arithmetic circuits such as is shown in  FIG. 3  or with more general circuits, e.g., general computing circuitry in cooperation with appropriate instructions. Moreover, while this approach converts from a 7-bit binary value X to two 4-bit decimal digits D 1 , D 0 , it is not limited to such conversion. for example, larger values, e.g., 64 or 128 bit binary values X could be converted by parsing subp-portions and converting using approaches, whole or in part, presented herein.) 
     FIG. 3  shows a conversion circuit for converting a 7-bit binary value X to two 4 bit BCD values D 1 , D 0  consistent with the routine of  FIG. 2  in accordance with some embodiments. The summing operation to obtain D 1  is arithmetically represented at  301 . The binary to BCD circuit generally comprises a first row with 3:2 compressors  311 ,  313  and a half adder  315 ; a second row with 3:2 compressors  321 ,  323 ,  325 ,  327 ; a 7-bit carry chain/4-bit adder circuit  331 , a 3-bit adder circuit  336 , four XOR gates  341 , inverter  345 , and 4-bit adders  343  and  346 , all coupled together as shown. 
   The input X (X 0  to X 6 ) are provided to various inputs as shown. The 3:2 compressors ( 311 ,  313 ) compute D′ 1 , i.e. the sum of X&gt;&gt;4+X&gt;&gt;5+1 or 2 in carry-save format. The sum/carry outputs are provided to 3-bit adder  336  for the ultimate calculation of D 1 . In addition to outputs from half adder  315 , they are also provided to the second row of compressors, which provide their results to the 7-bit carry chain/4-bit summer for the calculation of D′ 0 . 
   The second row of 3:2 compressors computes 10 D′ 1  in Carry-Save format. (A decimal multiply by 10 corresponds to X times 1010, which is: X shifted by 1+X shifted by 3.) The 7-bit carry chain/4-bit summer  331  computes a 4-bit-D′ 0  and a sign-bit (represented by the output Carry). 
   The 3-bit adder  336  computes D′, (corresponding to step  206  in  FIG. 2 . The Carry bit from carry chain/adder  331  determines if it is correct or whether 1 must be subtracted from it to arrive at D 1 . The Sum &lt;3:0&gt; output from adder  336  (which corresponds to D′ 1 ) is provided to the inputs of adder  346 , along with the inverted sign bit thereby leaving it unchanged if the Carry bit is ‘1 and adding to it ‘1111 (same as subtracting from it 1) if the Carry bit is ‘0. 
     FIG. 4  shows a circuit to implement the 7-bit carry chain/4-bit adder  331  in accordance with some embodiments. it comprises logic components U 1  to U 17 , coupled together as shown. it comprises a 7-bit carry chain (U 1 -U 10 , U 12 -U 16 ) merged with a 4-bit summing circuit (U 11 , U 17 ). (Note that each represented gate is actually implemented with one or more gates, depending on the number of signals being processed. this is indicated with the “x#” nomenclature. Where no “x#” appears, one gate is used.) 
   The carry-chain adds two 7-bit numbers (A&lt;6:0&gt;, B&lt;6:0&gt;), with an additional bit (C) at bit position  4  (consistent with  FIG. 3 ) to generate an output carry (carry out) at U 16 . The 7-bit carry-chain uses a radix-2 carry-merge to compute the output carry in 4 gate stages, consistent with the formulas depicted in the lower left portion of the figure. In parallel, the 4-bit sum (sum&lt;3:0&gt; at output of U 17 ) is also computed. The PG block is configured to accommodate the extra bit. In this embodiment, the BCD Carry block U 4  computes the Carry 4  term, pursuant to the “Carry i ” equation in the lower left portion of the figure. 
   The invention is not limited to the embodiments described, but can be practiced with modification and alteration within the spirit and scope of the appended claims. For example, it should be appreciated that the present invention is applicable for use with all types of semiconductor integrated circuit (“IC”) chips. Examples of these IC chips include but are not limited to processors, controllers, chip set components, network chips, and the like. 
   Moreover, it should be appreciated that example sizes/models/values/ranges may have been given, although the present invention is not limited to the same. As manufacturing techniques (e.g., photolithography) mature over time, it is expected that devices of smaller size could be manufactured. In addition, well known power/ground connections to IC chips and other components may or may not be shown within the FIGS. for simplicity of illustration and discussion, and so as not to obscure the invention. Further, arrangements may be shown in block diagram form in order to avoid obscuring the invention, and also in view of the fact that specifics with respect to implementation of such block diagram arrangements are highly dependent upon the platform within which the present invention is to be implemented, i.e., such specifics should be well within purview of one skilled in the art. Where specific details (e.g., circuits) are set forth in order to describe example embodiments of the invention, it should be apparent to one skilled in the art that the invention can be practiced without, or with variation of, these specific details. The description is thus to be regarded as illustrative instead of limiting.