US 7624138

US Patent 7624138: Method and Apparatus for Efficient Integer Transform

Title: Method and apparatus for efficient integer transform

Assignee: Intel Corp

Inventors: Eric Debes, William W. Macy, Jonathan J. Tyler

Filing Date: December 30, 2003

Issue Date: November 24, 2009

Abstract:
A method and apparatus for efficient integer transforms of content data are disclosed. The invention involves generating multiple sums of product pairs within a destination data storage device by executing a multiply-add instruction. These product pairs are formed by multiplying data from the destination storage device with coefficients from a coefficient data storage device. The process can generate a second set of summed product pairs in another destination storage device using a second multiply-add instruction. Furthermore, adjacent summed-product pairs from the first and second storage devices can be added together by executing a horizontal-add instruction, with the results being stored in a destination storage device and optionally in a memory device.

Plain-Language Overview of Independent Claims:

This patent includes numerous claims, with several independent claims across different categories (method, apparatus, computer program product). Here's a plain-language overview of the primary independent claims:

Claim 1 (Method):
This claim describes a method for efficiently performing integer transforms on data. It involves:

1. Using a "multiply-add" instruction to multiply individual data elements from one source with corresponding coefficients from another source, creating intermediate products. These intermediate products are then grouped into pairs and added together to produce a set of sums (sums of product pairs). These sums are stored in a designated memory area (destination data storage device).
2. Using a "horizontal-add" instruction to take the adjacent sums of product pairs (generated in the previous step) and add them together. The results of these additions are stored back into the destination memory area. The process can be applied to implement an integer transform for content data.

Claim 10 (Apparatus):
This claim describes a computing device (processor) designed for efficient integer transforms. This processor includes:

1. An execution unit capable of running instructions.
2. A decoder that interprets instructions, including a specific "multiply-add" instruction and a "horizontal-add" instruction.
3. The multiply-add instruction, when executed, causes the processor to multiply data elements from a source with coefficients and then sum pairs of these products, storing the results.
4. The horizontal-add instruction, when executed, causes the processor to add together adjacent results (e.g., adjacent 16-bit elements) produced by the multiply-add operations, and store these new results.

Claim 14 (Computer Program Product):
This claim covers a computer-readable storage medium (like a disk or flash drive) that contains instructions. When a computer runs these instructions, it performs the method described in Claim 1, meaning it executes the steps of:

1. Generating sums of product pairs using a multiply-add instruction.
2. Adding adjacent summed-product pairs using a horizontal-add instruction to achieve an integer transform.

Claim 15 (Method - focusing on a 4x4 transform):
This method claim focuses on performing a 4x4 integer transform specifically for content data. It involves:

1. Executing a first multiply-add instruction to generate initial sums of products within a destination device by multiplying data from that device with coefficients.
2. Executing a second multiply-add instruction to generate more sums of products in a second destination device.
3. Executing a first horizontal-add instruction to add adjacent pairs of sums from the first destination device and store the results.
4. Executing a second horizontal-add instruction to add adjacent pairs of sums from the second destination device and store the results.
5. Storing these final results in a memory device.

Claim 20 (Apparatus - focusing on a 4x4 transform):
This apparatus claim describes a processor configured to perform a 4x4 integer transform on content data. It has:

1. A memory for storing data and instructions.
2. A processor coupled to the memory, containing an execution unit and a decoder.
3. The processor is configured to perform the steps outlined in Claim 15, specifically executing the two multiply-add and two horizontal-add instructions to compute the 4x4 transform.

There is no authoritative information from the CAFC 2026 dockets indicating any ongoing legal challenges or appeals related to US patent 7624138. The patent's legal status is "Expired - Lifetime", with an expiration date of May 5, 2024.

As of April 26, 2026, based on the conducted searches of patent litigation resources, no specific litigation cases involving US patent 7624138 are known. The search results primarily discuss the general activities of patent monitoring organizations like Unified Patents or provide broad lists of patent cases without specific details for this patent number.

Proceedings overview

There are no AIA trial proceedings on file for US Patent 7,624,138 as of 2026-05-29, according to both the USPTO ODP API and supplementary web searches. This gives a defendant a posture where the patent has not been subjected to PTAB challenges, meaning all claims remain untested by the AIA trial process.

Strategic summary

As of the current date, all claims of US Patent 7,624,138 are UNTESTED by AIA trial proceedings. This means that no claims have been canceled or sustained through an IPR, PGR, or CBM. The estoppel landscape is entirely open, as there are no previous PTAB decisions to bar any petitioner (or their privies) from raising any ground they raised or reasonably could have raised against any claim of the patent. There are no pattern signals to discern regarding this patent owner's behavior in PTAB proceedings, nor any involvement from defensive aggregators.

Recommended next steps

The absence of PTAB activity suggests that the patent has not yet been rigorously challenged in post-grant proceedings. If facing assertion of this patent, a potential defendant could consider initiating an IPR against the patent, as the claims are currently untested and no prior art grounds have been foreclosed by previous PTAB decisions.

Inventors

• Eric Debes: Intel Corp
• William W. Macy: Intel Corp
• Jonathan J. Tyler: Intel Corp

All inventors were employed by Intel Corp at the time of filing, as Intel Corp is listed as the original assignee and the entity that filed the application.

Original assignee

The original assignee is Intel Corp. Intel Corp designs and manufactures microprocessors, chipsets, and other computing and communications components. They have shipped and continue to ship products, such as CPUs with SIMD instruction sets, that embody the claims described in US7624138, which relates to efficient integer transforms for multimedia processing. Intel Corp is currently an operating company.

Assignment timeline

A search of the USPTO Assignment Center for patent number US7624138 yielded no recorded assignments. The Google Patents record shows an assignment to Intel Corporation on 2004-07-02 (Reassignment), where the assignors were the inventors Eric Debes, William W. Macy, and Jonathan J. Tyler. This is a common practice where inventors assign their rights to their employer and is not a post-issuance transfer to a third party. Therefore, there are no post-issuance assignments recorded for this patent in the USPTO Assignment Center.

Timeline diagram

timeline
    title Ownership of US 7624138
    2003 : Filed by Intel Corp
    2009 : Issued to Intel Corp

NPE / troll-pattern signals

1. Shell-entity transfer - Not present. There are no recorded transfers from Intel Corp to a shell entity.
2. Known asserter in the chain - Not present. There is no indication of any known patent asserter (NPE) in the ownership chain.
3. Repeat correspondent across the chain - Not present. With no post-issuance assignments, there is no recurring correspondent.
4. Cascading transfers - Not present. No transfers are recorded.
5. Pre-litigation transfer - Not present. No transfers are recorded, and the patent has expired.
6. Bankruptcy fire-sale - Not present. Intel Corp remains an operating company.
7. Privateering - Not present. No transfers or assertion patterns suggest privateering.
8. Defensive aggregator (anti-NPE) - Not present. The patent remains with the original operating company, Intel Corp, as of its expiration.

Verdict

Insufficient data. There are no recorded post-issuance assignments in the USPTO Assignment Center for US7624138. The patent was granted to and remained with the original operating company, Intel Corp, until its expiration in 2024. Therefore, no NPE or patent troll patterns can be identified from assignment records.

USPTO Assignment Center Search for US7624138

US patent 7624138, titled "Method and apparatus for efficient integer transform," describes a method and apparatus for performing integer transforms on content data efficiently, particularly using Single-Instruction-Multiple-Data (SIMD) operations. The core of the invention involves specific instructions: a multiply-add instruction that generates sums of product pairs from packed data, and a horizontal-add instruction that adds adjacent summed-product pairs. These instructions are applied to perform integer transforms, such as 4x4 or 8x8 approximations of Discrete Cosine Transforms (DCTs).

The following are the most relevant prior art patent citations for US7624138, along with their details and potential anticipation under 35 U.S.C. § 102:

Most Relevant Prior Art

1. US7085795B2

   • Full Citation: US7085795B2, "An Apparatus and Method for Efficient Filtering and Convolution of Content Data," invented by Eric Debes, William W. Macy, Jonathan J. Tyler (assignee: Intel Corp.). Issued August 1, 2006.
   • Publication/Filing Date: Filed October 29, 2001.
   • Brief Description: This patent describes a system and method for efficient filtering and convolution of content data using packed data. It introduces specialized instructions, including those for performing "horizontal-add" operations that sum adjacent data elements (e.g., bytes, words, doublewords) within a register or between registers. The patent explicitly mentions a horizontal-add instruction capable of adding two word values to produce a 16-bit result.
   • Potential Anticipation (35 U.S.C. § 102): US7085795B2, sharing the same inventors and assignee, directly anticipates the "horizontal-add instruction" aspect of US7624138. Specifically, claims 2, 8, 11, 19, 28, 35, 44, 51, and 58 of US7624138, which cover adding adjacent summed-product pairs using a horizontal-add instruction, are potentially anticipated by the teaching of similar horizontal addition on packed data elements. The use of 16-bit results from such operations, as detailed in claims 4, 5, and 9, is also described within US7085795B2.

2. US5794017A

   • Full Citation: US5794017A, "Processor and method for performing multiplication and addition operations on a plurality of data elements in parallel," invented by Alexander Peleg, Shinya Shimada, Robert P. Colwell (assignee: Intel Corp.). Issued August 11, 1998.
   • Publication/Filing Date: Filed March 29, 1996.
   • Brief Description: This patent discloses a processor and corresponding method for executing a single instruction that performs both multiplication and addition operations on multiple packed data elements in parallel. It describes instructions like PMADDWD (Packed Multiply and Add Word) where corresponding 16-bit words from two source operands are multiplied, and the 32-bit products are then summed in pairs to produce 32-bit results in a destination register.
   • Potential Anticipation (35 U.S.C. § 102): US5794017A directly anticipates the "multiply-add instruction" central to US7624138. Claims 1, 7, 10, 18, 27, 34, 43, 50, and 57 of US7624138, which define generating sums of product pairs in response to a multiply-add instruction, are potentially anticipated. The concept of multiplying packed data elements (e.g., words) and summing adjacent products is explicitly taught. While US7624138 emphasizes byte data elements producing 16-bit sums (claims 4, 9), the core functionality of a single SIMD instruction performing a combined multiply-add on packed data elements is present.

3. US5727147A

   • Full Citation: US5727147A, "Method and apparatus for operating on packed data," invented by Seshadri Dattatri, Karl M. Guttag, Alexander Peleg, Shinya Shimada, Roman Shvets (assignee: Intel Corp.). Issued March 10, 1998.
   • Publication/Filing Date: Filed August 31, 1995.
   • Brief Description: This patent describes a foundational SIMD architecture for operating on packed data. It details a processor capable of storing multiple data elements (e.g., bytes, words, doublewords) in a single register and executing a single instruction to perform parallel operations (e.g., addition, subtraction, multiplication) on these elements. This patent lays the groundwork for packed data instructions.
   • Potential Anticipation (35 U.S.C. § 102): This patent broadly anticipates the fundamental concept of using SIMD operations on packed data, which is a core underlying technology for US7624138. Specifically, the general idea of packed arithmetic operations and manipulation of different data element sizes (e.g., bytes, words) as referenced in claims 1, 4, 10, 14, 15, 18 and related claims in US7624138 is anticipated. While it describes separate packed multiply and packed add instructions rather than a single multiply-add instruction, the enabling technology for such combined operations is disclosed.

4. US6360312B1

   • Full Citation: US6360312B1, "Method and apparatus for performing horizontal operations on packed data," invented by William W. Macy, Eric Debes, Jonathan J. Tyler (assignee: Intel Corp.). Issued March 19, 2002.
   • Publication/Filing Date: Filed January 20, 2000.
   • Brief Description: This patent, also by some of the inventors of US7624138 and assigned to Intel, focuses on horizontal operations on packed data. It describes methods and apparatus for combining adjacent data elements within a packed data operand (e.g., summing or subtracting adjacent words) using specific instructions. This directly relates to the horizontal-add and horizontal-subtract functionalities.
   • Potential Anticipation (35 U.S.C. § 102): US6360312B1 specifically teaches the "horizontal-add" operation on packed data. Claims 2, 8, 11, 19, 28, 35, 44, 51, and 58 of US7624138, which describe adding adjacent summed-product pairs using a horizontal-add instruction, are potentially anticipated. The patent provides detailed descriptions of performing such operations on various packed data types, including words, which aligns with the 16-bit data element operations mentioned in claims 4, 5, and 9 of US7624138.

These prior art documents, particularly those from Intel with overlapping inventors, demonstrate that the underlying SIMD instructions for packed data, including multiply-add and horizontal-add operations, were known before the priority date of US7624138. The novelty of US7624138 likely resides in the specific application and sequence of these operations for efficient integer transforms approximating discrete cosine transforms, especially the specific data widths and saturation logic implemented for that purpose.

US Patent 7624138, titled "Method and apparatus for efficient integer transform," describes a method and apparatus for performing efficient integer transforms of content data, particularly for compression and decompression of audio, images, and video. The core of the invention, as outlined in the claims and disclosure, involves using a sequence of specific Single-Instruction-Multiple-Data (SIMD) operations: primarily a "multiply-add instruction" and a "horizontal-add instruction." [cite: "a method and apparatus for efficient integer transforms of content data include generating, in response to executing a multiply-add instruction, a plurality of sums of product pairs within a destination data storage device.", "adjacent summed-product pairs may be added in response to executing a horizontal-add instruction."]

The patent itself identifies several relevant pieces of prior art and general knowledge, which form the basis for an obviousness analysis under 35 U.S.C. § 103.

Identified Prior Art and General Knowledge:

1. Prior Art 1 (PA-PackedData): "A Set of Instructions for Operating on Packed Data," filed on Aug. 31, 1995, application number 521,360. This reference describes a packed instruction set (e.g., set 140) that includes instructions for supporting "a packed add operation" and "a packed multiply operation" on packed data formats. [cite: "Packed instruction set 140 may also include instructions for supporting: a pack operation, an unpack operation, a packed add operation, a packed subtract operation, a packed multiply operation, a packed shift operation, a packed compare operation, a population count operation, and a set of packed logical operations (including packed AND, packed ANDNOT, packed OR, and packed XOR) as described in “A Set of Instructions for Operating on Packed Data,” filed on Aug. 31, 1995, application number 521,360."] It teaches the general concept of processing multiple data elements in parallel using SIMD operations.
2. Prior Art 2 (PA-Filtering): "An Apparatus and Method for Efficient Filtering and Convolution of Content Data," filed on Oct. 29, 2001, application Ser. No. 09/952,891. This application is explicitly referenced in US7624138 and is also noted as a priority document for US7624138. [cite: "Priority claimed from US09/952,891"] It teaches a packed instruction set that "may also include one or more instructions for supporting: ... a horizontal-add instruction for adding adjacent bytes, words and doublewords, two word values, two words to produce a 16-bit result, two quadwords to produce a quadword result." [cite: "Packed instruction set 140 may also include one or more instructions for supporting: a move data operation; a data shuffle operation for organizing data within a data storage device; a horizontal-add instruction for adding adjacent bytes, words and doublewords, two word values, two words to produce a 16-bit result, two quadwords to produce a quadword result; and a register merger operation as are described in “An Apparatus and Method for Efficient Filtering and Convolution of Content Data,” filed on Oct. 29, 2001, application Ser. No. 09/952,891."] The title of this reference indicates its applicability to efficient processing of content data, similar to the objective of US7624138.
3. General Knowledge: The patent itself states that "Discrete transforms such as the discrete cosine transform (DCT) used in prior compression techniques have made use of floating-point or fixed-point number representations to approximate real irrational coefficients." [cite: "Discrete transforms such as the discrete cosine transform (DCT) used in prior compression techniques have made use of floating-point or fixed-point number representations to approximate real irrational coefficients."] It also highlights the known benefits of "integer transforms," which "have integer basis components and permit coefficients to be accurately represented by integers" [cite: "integer transforms which have integer basis components and permit coefficients to be accurately represented by integers."] and can be implemented efficiently. Furthermore, the concept of a "multiply-add" or "multiply-accumulate" (MAC) operation as a common and efficient instruction in digital signal processing (DSP) architectures for combining multiplication and addition is well-known in the art.

Obviousness Analysis based on 35 U.S.C. § 103:

A person having ordinary skill in the art (POSITA) in the field of computer architecture, instruction set design, and digital signal processing for multimedia applications, facing the challenge of efficiently implementing integer transforms, would have been motivated to combine the teachings of PA-PackedData and PA-Filtering.

Combination of PA-PackedData and PA-Filtering:

1. Deriving the Multiply-Add Instruction: PA-PackedData teaches the existence of both a "packed multiply operation" and a "packed add operation" for processing packed data elements in parallel. [cite: "Packed instruction set 140 may also include instructions for supporting: a pack operation, an unpack operation, a packed add operation, a packed subtract operation, a packed multiply operation, a packed shift operation, a packed compare operation, a population count operation, and a set of packed logical operations (including packed AND, packed ANDNOT, packed OR, and packed XOR) as described in “A Set of Instructions for Operating on Packed Data,” filed on Aug. 31, 1995, application number 521,360."] In DSP applications, which include transforms for multimedia content, the multiplication of data by coefficients (as described in US7624138) is frequently followed by an accumulation (addition). The combination of a multiply and an add into a single "multiply-add" or "multiply-accumulate" (MAC) instruction is a well-established architectural optimization to reduce instruction count, improve pipeline efficiency, and enhance performance. Therefore, it would have been obvious for a POSITA, seeking to optimize computations involving packed data (as taught by PA-PackedData), to implement a "packed multiply-add instruction" by combining the known packed multiply and packed add operations. The patent itself mentions support for "multiply-add and/or multiply-subtract operations" within its packed instruction set. [cite: "Packed instruction set 140 includes instructions for supporting multiply-add and/or multiply-subtract operations."]
2. Incorporating the Horizontal-Add Instruction: PA-Filtering directly teaches the "horizontal-add instruction for adding adjacent bytes, words and doublewords" within packed data registers. [cite: "Packed instruction set 140 may also include one or more instructions for supporting: a move data operation; a data shuffle operation for organizing data within a data storage device; a horizontal-add instruction for adding adjacent bytes, words and doublewords, two word values, two words to produce a 16-bit result, two quadwords to produce a quadword result; and a register merger operation as are described in “An Apparatus and Method for Efficient Filtering and Convolution of Content Data,” filed on Oct. 29, 2001, application Ser. No. 09/952,891."] Transforms, filters, and convolutions often require summing intermediate products across a data vector or matrix. A horizontal-add instruction is perfectly suited for this purpose, enabling efficient accumulation of results within a single packed register.

Motivation for Combination:

A POSITA, skilled in optimizing multimedia processing on SIMD architectures, would be strongly motivated to combine these elements to achieve the "efficient integer transform processing of content data" claimed by US7624138. The patent itself identifies the problem of "Discrete transforms... used in prior compression techniques have made use of floating-point or fixed-point number representations to approximate real irrational coefficients" [cite: "Discrete transforms such as the discrete cosine transform (DCT) used in prior compression techniques have made use of floating-point or fixed-point number representations to approximate real irrational coefficients."] and proposes "integer transforms" as a solution. [cite: "integer transforms which have integer basis components and permit coefficients to be accurately represented by integers."]

To implement these desired integer transforms efficiently on a processor with SIMD capabilities (as described in PA-PackedData), a POSITA would naturally consider:

• Performance Improvement: Combining multiplication and addition into a single instruction (packed multiply-add) directly addresses the computational core of transforms, which are rich in multiply-accumulate operations. This reduces the number of instructions executed and improves data throughput.
• Completing Transform Computations: After initial packed multiply-add operations generate "sums of product pairs" (often representing partial sums or intermediate terms of a transform), these partial results frequently need to be summed together horizontally to produce the final transform coefficients. The "horizontal-add instruction" from PA-Filtering provides precisely the mechanism to perform these necessary intra-register summations efficiently. The applicability of PA-Filtering to "Efficient Filtering and Convolution" further suggests its relevance to the broader domain of signal processing that includes transforms.

Thus, the combination of a packed multiply-add instruction (a straightforward evolution from the packed multiply and packed add of PA-PackedData for performance in DSP) and the explicitly taught horizontal-add instruction of PA-Filtering, applied to the known problem of efficient integer transforms for content data, would have been obvious to a POSITA at the time of the invention. The predictable result would be a more efficient implementation of integer transforms, fulfilling a recognized need in multimedia processing.