Linear interpolation between regularly spaced digital samples

• US 4,446,529 A
• Filed: 09/23/1981
• Issued: 05/01/1984
• Est. Priority Date: 01/26/1981
• Status: Expired due to Fees

• Current Assignee: Lockheed Martin Corporation (Martin Marietta Corporation)
• Original Assignee: RCA Corporation
• Inventors: Strolle, Christopher H.
• Primary Examiner(s): Malzahn, David H.
• Assistant Examiner(s): Huang, Karl
• Application Number:
  US06/304,924
• Time in Patent Office: 951 Days
• Field of Search: 364/723, 364/577, 364/721, 364/719, 318/573, 340/728, 84/1.03
• US Class Current: 708/290
• CPC Class Codes: G06F 1/0307 Logarithmic or exponential functions G06F1/0314, G06F1/035 take precedence
• CPC Class Codes: G06F 17/175 of multidimensional data
• CPC Class Codes: G06F 2101/04 Trigonometric functions
• CPC Class Codes: G06F 2101/08 Powers or roots
• CPC Class Codes: G06F 2101/10 Logarithmic or exponential functions
• CPC Class Codes: G11C 7/00 Arrangements for writing information into, or reading information out from, a digital store G11C5/00 takes precedence; auxiliary circuits for stores using semiconductor devices G11C11/4063, G11C11/413
• CPC Class Codes: G11C 8/04 using a sequential addressing device, e.g. shift register, counter
• CPC Class Codes: G11C 8/16 Multiple access memory array, e.g. addressing one storage element via at least two independent addressing line groups
• CPC Class Codes: H04N 9/78 for separating the brightness signal or the chrominance signal from the colour television signal, e.g. using comb filter

Abstract

The process of linearly interpolating between data taken from adjacent storage locations in a memory non-integrally addressed has the initial subtraction and final addition steps eliminated from it, and the partial products to be summed in the intervening multiplication process are modified to compensate for the elimination of these steps. This modification is done with a relatively fast select-one-of-four process, reducing the time for linear interpolation to that required for a simple multiplication--or, in the case of a single-bit multiplier, to the time for selection of the modified multiplicand to be used as linear interpolation result.

Claims

1. In combination:

means for supplying binary numbers descriptive of a variable, each binary number having an integral portion and at least some of them, at times having fractional portions;

a memory, having storage locations addressable in terms of integral portions of said variable for storing plural-bit-binary-number digital samples of a function of said variable, and responding to the integral portion of each number descriptive of said variable to supply a pair of digital samples associated with that integral portion and with that integral portion as incremented by unity; and

means for accumulating a number of terms corresponding to the number of bits in said digital samples to generate a linear interpolation between each pair of samples, each successive term being shifted in all its places in the direction of increased significance by a number of bits equal to the power of two which is described by each successive place in both of said pair of digital samples, and each successive term being generated responsive to those places in said both of said pair of digital samples, said means for accumulating including

means for selecting zero for each term for which the corresponding places in both digital samples are ZEROs,

means for selecting unity for each term for which the corresponding places in both digital samples are ONEs,

means for selecting the fractional portion of said variable for each term for which the corresponding place of the digital sample associated with the integral portion of said variable is a ZERO and the corresponding place of the digital sample associated with the integral portion of said variable as incremented by unity is a ONE,

means for generating the complements of the fractional portions of said binary numbers, and

means for selecting the complement of the fractional portion of said variable for each term for which the corresponding place of the digital sample associated with the integral portion of said variable is a ONE and the corresponding place of the digital sample associated with the integral portion of said variable as incremented by unity is a ZERO.

2. In the combination set forth in claim 1 said means for generating the complements of the fractional portions of said binary numbers being of a type which generates the complements on a continuous basis.

3. In the combination set forth in claim 1 said means for generating the complements of the fractional portions of said binary numbers being of a type which generates the complements only when they are selected.

7. A combination as set forth in claim 1 or 4 wherein the function of said variable stored in said memory is a one-dimensional function that is a function of no other variable.

4. In combination:

means for supplying binary numbers descriptive of a variable, each binary number having an integral portion and at least some of them at times having fractional portions;

a memory, having storage locations addressable in terms of integral portions of said variable for storing single-bit-binary-number digital samples of a function of said variable, and responding to the integral portion of each number descriptive of said variable to supply a pair of digital samples associated with that integral portion and with that integral portion as incremented by unity; and

means for performing linear interpolation between each pair of samples including

means for selecting zero as the linear interpolation result when both digital samples are ZEROs,

means for selecting unity as the linear interpolation result when both digital samples are ONEs,

means for selecting the fractional portion of the number responsive to the integral portion of which the digital samples are extracted, as the linear interpolation result, when the digital sample associated with the integral portion of that number is a ZERO and the digital sample associated with the integral portion of that number as incremented by unity is a ONE,

means for generating the complements of the fractional portions of said binary numbers, and

means for selecting the complement of the fractional portion of the number responsive to the integral portion of which the digital samples are extracted, as the linear interpolation result, when the digital sample associated with the integral portion of that number is a ONE and the digital sample associated with the integral portion of that number as incremented by unity is a ZERO.

5. In the combination set forth in claim 4 said means for generating the complements of the fractional portions of said binary numbers being of a type which generates the complements on a continuous basis.

6. In the combination set forth in claim 4 said means for generating the complements of the fractional portions of said binary numbers being of a type which generates the complements only when they are selected.

8. In combination:

means for supplying successive pairs of binary numbers respectively descriptive of first and second variables, each variable having a respective integral portion and at least at times having a respective fractional portion;

means for generating the complements of the fractional portions of said first and second variables;

a memory having storage locations for storing single-bit-binary-number digital samples of a two-dimensional function of said first and second variables said memory being responsive to integral portions of such successive pair of binary numbers respectively descriptive of said first and second variables for supplying digital samples of said two-dimensional function at first storage location coordinates equal to those integral portions, at second storage location coordinates respectively equal to the integral portion of the first variable incremented by unity and to the integral portion of the second variable, at third storage location coordinates respectively equal to the integral portion of the first variable and to the integral portion of the second variable incremented by unity, and at fourth storage location coordinates respectively equal to the integral portion of said first variable incremented by unity and to the integral portion of said second variable as incremented by unity;

means for obtaining a first intermediate interpolation result by linearly interpolating between the digital samples at said first coordinates and at said second coordinates in accordance with the fractional portion of said first variable, which means includes

means for selecting zero as said first intermediate interpolation result responsive to the digital samples at said first coordinates and at said second coordinates both being ZEROs,

means for selecting unity as said first intermediate interpolation result responsive to the digital samples at said first coordinates and at said second coordinates both being ONEs,

means for selecting the fractional portion of said first variable as said first intermediate interpolation result responsive to the digital samples at said first coordinates and at said second coordinates being respectively a ZERO and a ONE, and

means for selecting the complement of the fractional portion of said first variable as said first intermediate interpolation result responsive to the digital samples at said first coordinates and said second coordinates being respectively a ONE and a ZERO;

means for obtaining a second intermediate interpolation result by linearly interpolating between the digital samples at said third coordinates and at said fourth coordinates in accordance with the fractional portion of said first variable, which means includes

means for selecting zero as said second intermediate interpolation result responsive to the digital samples at said third coordinates and at said fourth coordinates both being ZEROs,

means for selecting unity as said second intermediate interpolation result responsive to the digital samples at said third coordinates and at said fourth coordinates both being ONEs,

means for selecting the fractional portion of said first variable as said second intermediate interpolation result responsive to the digital samples at said third coordinates and at said fourth coordinates being respectively a ZERO and a ONE, and

means for selecting the complement of the fractional portion of said first variable as said second intermediate interpolation result responsive to the digital samples at said third coordinates and at said fourth coordinates being respectively a ONE and a ZERO; and

means for obtaining a final interpolation result, which is the interpolated value of said two-dimensional function, by linearly interpolating between the said first and said second intermediate interpolation results in accordance with the fractional portion of said second variable.

9. In the combination set forth in claim 8 said means for generating the complements of the fractional portions of said binary numbers being of a type which generates the complements on a continuous basis.

10. In the combination set forth in claim 8 said means for generating the complements of the fractional portions of said binary numbers being of a type which generates the complements only when they are selected.

11. In combination:

means for supplying binary numbers descriptive of a variable, each variable having an integral portion and at least at times having a fractional portion;

means for generating the complement of the fractional portion of said variable;

a memory, having storage locations addressable in terms of integral portions of said variable for storing plural-bit-binary-number digital samples of a function of said variable, and responding to the integral portion of each number descriptive of said variable to supply the pair of digital samples associated with that integral portion and with that integral portion as incremented by unity;

apparatus for summing modified partial products for generating a linear interpolation between said pair of digital samples; and

a respective one-of-four selection apparatus controlled by bit places of like power of two from each of said digital samples, for selecting zero for the modified partial product associated with those bit places when they both are ZEROs, for selecting unity for the modified partial product associated with these bit places when they both are ONEs, for selecting the fractional portion of said variable for the modified partial product associated with those bit places when the bit place, from the digital sample at the storage location associated the integral portion of said variable is ZERO and the bit place from the other digital sample is ONE, and for selecting the complement of the fractional portion of said variable for the modified partial product associated with those bit places when the bit place from the digital sample at the storage location associated with the integral portion of said variable is ONE and the bit place from the other digital sample is ZERO.

12. In the combination set forth in claim 11 said means for generating the complements of the fractional portions of said binary numbers being of a type which generates the complements on a continuous basis.

13. In the combination set forth in claim 11 said means for generating the complements of the fractional portions of said binary numbers being of a type which generates the complements only when they are selected.