Take the 2-minute tour ×
Ask Patents is a question and answer site for people interested in improving and participating in the patent system. It's 100% free, no registration required.

Seeking Prior Art on US Patent US 2010030834

Priority Date: Seeking Prior Art from before Aug 1, 2008

Isn't this application US 20100030834 trying to get a patent on half/partial carries? This technique has been used in many microprocessor since the early 70's... Also, the application has this jewel:

"One conventional algorithm for performing BCD calculations involves processing the addition on a nibble-by-nibble basis (a nibble is made up of four binary bits), starting with the least significant nibble (corresponding to the least significant decimal digit), and proceeding to the most significant nibble one nibble at a time."

Which is not even true for many of simplest 8-bit processors available. Take the venerable 8051 for example:

mov a, bcd_x ; load a two nibble bcd number

add a, bcd_y ; add another two nibble bcd number

daa ; The decimal adjust instruction that uses the half carry

mov bcd_r, a ; The two nibble result is stored in bcd_r, with carry indicating overflow

share|improve this question
    
The quoted paragraph is from the 'background' section, it is not a claim. One important detail not mentioned in the question is the filing or 371 (c) Date: 09-22-2008. –  Ron J. Aug 9 '13 at 12:30
1  
Only a side comment: the famous Supreme Court case regarding a disembodied "algorithm" not being patentable, Gottschalk v. Benson (S. Ct. 1972), was about turning BCD into binary in an execution-time efficient way. It was the big "software isn't patentable" milestone before later "software is patentable" major cases and the more recent "I know abstract when I see it" state of affairs. –  George White Aug 9 '13 at 23:15

2 Answers 2

US 2010030834

Title: "Performing A Binary Coded Decimal (BCD) Calculation"

Note that according to Public PAIR the patent was allowed by USPTO on July 19, 2013. Under the AIA it is not be possible to submit prior art under the pre-grant process used by Ask Patents. Prior art which is found below can be easily submitted anytime after grant under 37 C.F.R. 1.501 Citation of prior art in patent files however it will not be looked at by the USPTO unless something else happens. If you want something considered by the USPTO rather than just put in the file, you could submit an ex-parte reexamination request. For a business method patent or for a patent from an application filed after March 15, 2013 one can a petition for a post-grant review during a 9 month window or after that can petition for an interpartes review (These could be done by a company or an individual but all the options are expensive and the PGR and IPR are quasi-litigation proceedings before the board.)

enter image description here

It is very important to look at the Claims of the Patent rather than Abstract or the Title.

Moreover, the claims which were allowed are substantially narrower than the claims listed on the Google Patent page for this application.

Here is the allowed Claim 1:

(Currently Amended) A method of performing a binary-coded decimal (BCD) addition, comprising:

  1. Receiving, in a process, first and second values on which the BCD addition is to be performed;

  2. Adding the first value to sequence of constant digits to produce a modified first value;

  3. Adding the modified first value and the second value to produce a sum having BCD digits;

  4. Determining which of the BCD digits of the sum is not associated with a carry, wherein the determining comprises performing an operation on the modified first value, the second value, and the sum, and using a result of the operation to identify which of the BCD digits of the sum is not associated with a carry;

  5. Storing a carry resulting from the adding of the modified first value and the second value in a flag register of the processor, where the carry stored in the flag register is a value to be transferred to a next most significant BCD digit;

  6. Using the carry stored in the flag register to compute a result of the BCD addition; and

  7. Subtracting corresponding constant digits from BCD digits of the result of the BCD addition for those BCD digits of the result that are not associated with a carry as identified by the determining.

You can see this on Public Pair. I recommend you search by the Publication Number "US 20100030834 A1" not by the Application Number. You'll want to look at the "Image File Wrapper" section of the record:

enter image description here enter image description here

share|improve this answer

First, allow me to express my sheer astonishment that BCD is still even slightly relevant in the 21st century. This appears to be a pure software algorithm designed to work around the fact that modern CPUs no longer include BCD related instructions; for example, AMD64 drops the AAA, AAD, AAM and AAS instructions that were present in x86, and reuses their opcodes for other (much more widely useful) purposes.

The patent is, as usual, very difficult to read for the purposes of understanding the algorithm embodied in it, so rather than provide prior art here, I will simply describe the algorithm more clearly for computer people.

NB: these are the amended claims a described by another answer.

// Claim 1
uint32_t bcdAdd(uint32_t a, uint32_t b)
{
    // Claim 2 - ensures that digit-to-digit carries occur.
    a += 0x66666666;

    // Claim 3
    uint32_t s = a + b;

    // Claim 4 - determine where digit-to-digit carries occurred.
    // I couldn't quickly understand how the patentee did it, so
    // I'm doing it the obvious way instead.  This leaves a flag
    // in the high bit of each nybble, indicating whether a carry
    // did not occur out of that nybble.

    uint32_t c = ~((a | b) & ~s) & 0x88888888;

    // Claim 5 - there are potentially several ways to obtain the
    // overall carry, but this one is easiest in pure C.  In pure
    // assembly, the carry is trivially obtained during the step
    // above for Claim 3, eg. using ADC instead of ADD.
    // Claim 6 is then simply carrying into the next set of digits,
    // which is an obvious and trivial step once you have the carry.

    bool carry = (~c) >> 31;

    // Claim 7 - adjust only the digits that didn't carry.
    // The below code is equivalent to s -= (c >> 3) * 6 but is faster.

    s -= (c >> 1) + (c >> 2);

    return s;
}

It is worth noting that I only had to read the claims and think for a couple of minutes to determine what the "adjustment constant" and the remaining details of the algorithm were. I consider it highly likely that some competent computer scientist has done so before me, without the benefit of the patent claims. The trick, of course, is figuring out who and when.

I did spot a disingenuous comment in the Description of the patent, suggesting that BCD "allows for faster decimal calculations in electronic devices." Since the above code would compile to roughly a dozen instructions (depending on the CPU involved) for a simple addition, and would have execution time comparable to a multiply on conventional binary numbers, this claim is laughable.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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