DETAILED ACTION
The present application, filed on or after March 16, 2013, is being examined under the first inventor to file provisions of the AIA .
Response to Arguments
Drawings. The objection to the drawings is withdrawn based on amendment to drawings.
Claim Objections. The objections to the claims are withdrawn based on amendment to claims.
35 USC 101.
Applicant asserts that representative claim 20 relates to a data processing system for implementing a discrete Fourier-related transform comprising at least one multiplication operation using a hardware accelerator comprising fixed-function circuitry and using a controller (Remarks p. 9). Applicant therefore asserts claim 20 describes a structural combination of hardware components that form a data processing system that is statutory under 35 USC 101 (Remarks p. 10 top).
Examiner respectfully disagrees. These elements are recited at a very high level of generality, wherein mathematical calculations and mathematical relationships are merely “applied” in a generically recited apparatus system, generically recited circuitry, or generally linked to a particular technological environment, without specifically limiting the functions performed by the apparatus to specific functions performed in a manner integral to the claim. For these reasons, claim 20 is not statutory.
Applicant further asserts that fixed function circuitry is fundamentally different from a generic computer or general-purpose processor, because this refers to a property of circuitry that the logic it implements cannot be reconfigured (or extensively reconfigured) after manufacture (Remarks p. 10). Similarly, Applicant asserts claim 20 recites performing the abstract idea on the input data using the hardware accelerator, and that that this specifies a particular manner of using specialized fixed-function circuitry to achieve a technical result as a new way to perform a previously unavailable function (Fourier-related transform) (Remarks p. 10)
Examiner respectfully disagrees. Whether fixed or programmable, the nature of the circuitry remains equally generic. No specific structure of logic is claimed. What is claimed with specificity is the mathematical function performed by the unknown circuit structure of the fixed-function circuitry in a generically recited hardware accelerator.
Applicant further asserts the claims improve the functionality of the fixed-function circuitry (Remarks p. 11). Applicant asserts the Specification supports this improvement as explained in paragraph [0067] wherein the claimed invention exploits the identification that “part of a DFRT can be modelled as a matrix multiplication between a weight matrix and an input tensor” and that “appropriate shaping of the weight matrix into one or more convolution kernels allow a convolution operation to be used to perform the matrix multiplication. A convolution operation can be performed by convolution hardware of a hardware accelerator” (Remarks p. 11).
Examiner respectfully disagrees. Any purported improvement flows directly from the abstract idea, which is recited above, the modelling of the DFRT as a type of matrix multiplication. “It is important to keep in mind that an improvement in the abstract idea itself (e.g. a recited fundamental economic concept) is not an improvement in technology” (MPEP 2106.05(a)(II)). The 'inventive concept cannot be furnished by the unpatentable law or nature (or natural phenomenon or abstract idea) itself. MPEP 2106.05.I. See also MPEP 2106.05(a). "The judicial exception alone cannot provide the improvement".
Applicant further asserts that the proposed approach is applied to a particular machine as in MPEP 2106.05(b) (Remarks p. 11).
Examiner respectfully disagrees. No particular fixed function circuitry is claimed whatsoever, only generically recited fixed-function circuitry in a hardware accelerator.
Applicant further asserts that PTAB decision related to 16670482 (also referencing 18135715) confirmed that a limitation using “fixed function circuitry configured to perform an act” provides an improvement that “integrates the abstract idea into a practical application (Remarks p. 11-12).
Examiner respectfully disagrees. Each claimed invention turns on its own merits. Furthermore, the cited PTAB decisions are neither precedential nor informative. For example, see also PTAB decisions in applications by Applicant 17854927, and 17853694, which came to an opposite conclusion with respect to fixed-function circuitry.
35 USC 102.
Applicant asserts Lu-Nonuniform does not disclose, suggest or contemplate performing matrix multiplication steps of an FFT using convolution operations, as required by independent claims 1 and 20, therefore failing to disclose executing at least one matrix multiplication of a Fourier-related transform by using convolution hardware to perform convolution operations (Remarks p. 13).
Examiner respectfully disagrees. Lu-Nonuniform discloses a parallel FFT algorithm on the TPU, wherein the FFT algorithm uses the Kaiser-Bessel function used in the interpolation and is selected as the convolution kernel, wherein the interpolation operation comprises a convolution (fig 2(b), section 2.3, introduction last paragraph). Furthermore the interpolation is performed in the frequency domain, which includes a fourier transform of the image, and a fourier transform of the Kaiser-Bessel function into the Kaiser Bessel window (section 2.3, introduction last paragraph, Lu-Nonuniform references using the approach of its citation [16] in the Kaiser-Bessel function, wherein the transformation of the Kaiser-Bessel function to a Kaiser-Bessel window is a fourier transform). See R.M. Lewitt, Multidimensional digital image representations using generalized Kaiser-Bessel window functions, JOSA A, vol 7, no 10, pp. 1834-1846, 1990 (hereinafter “Lewitt”). Furthermore, Lu-Nonuniform discloses all three operations including interpolation being formulated as tensor operations using matrix multiplications (abstract). Therefore, Lu-Nonuniform teaches executing the discrete Fourier-related transform on the input data using the hardware accelerator wherein the at least one matrix multiplication operation of the discrete Fourier-related transform is executed by using he convolution hardware to perform the one or more convolution operations using the at least one convolution kernel.
Applicant further asserts that Neither Lu-Large-Scale nor Redfern make up for the fundamental deficiency of Lu-Nonuniform with respect to independent claims (Remarks p. 13 bottom – 14).
Examiner respectfully disagrees. Examiner does not point to either Lu-Large-Scale or Redfern for any limitation of the independent claims.
Claim Rejections - 35 USC § 101
35 U.S.C. 101 reads as follows:
Whoever invents or discovers any new and useful process, machine, manufacture, or composition of matter, or any new and useful improvement thereof, may obtain a patent therefore, subject to the conditions and requirements of this title.
Claims 1-20 are rejected under 35 U.S.C. 101 because the claimed invention is directed to a judicial exception (i.e., a law of nature, a natural phenomenon, or an abstract idea) without significantly more.
Regarding treatment of claims, apparatus claim 20 will be addressed first, followed by the method claims.
Regarding claim 20, under the Alice framework Step 1, the claim falls within the four statutory categories of patentable subject matter identified by 35 USC 101: a process, machine, manufacture or a composition of matter.
Under the Alice framework Step 2A prong 1, the claim recites mathematical concepts of mathematical calculations and mathematical relationships for implementing a discrete Fourier-related transform. Specifically, claim 20 recites the following mathematical calculations and mathematical relationships:
implementing a discrete Fourier-related transform, wherein the discrete Fourier-related transform comprises at least one multiplication operation, perform one or more convolution operations;
wherein the input data contains values to undergo the discrete Fourier-related transform;
one convolution kernel, wherein each convolution kernel is derived from a weight matrix that represents a multiplicand or multiplier for at least one multiplication operation of the discrete Fourier-related transform; and
execute the discrete Fourier-related transform on the input data, wherein at least one multiplication operation of the discrete Fourier-related transform is executed to perform the one or more convolution operations using the at least one convolution kernel.
See, e.g., [0082-0083], [0099-00101], which describe the discrete Fourier-related transform in terms of mathematical relationships, and mathematical calculations. For these reasons, claim 20 recites mathematical concepts.
Under the Alice framework Step 2A prong 2 analysis, claim 1 recites the following additional elements: a data processing system comprising a hardware accelerator comprising fixed-function circuitry, the fixed-function circuitry comprising at least convolution hardware, and a controller. These elements are recited at a very high level of generality, wherein mathematical calculations and mathematical relationships are merely “applied” in a generically recited apparatus system, generically recited circuitry, or generally linked to a particular technological environment, without specifically limiting the functions performed by the apparatus to specific functions performed in a manner integral to the claim. For these reasons, claim 20 is not integrated into a practical application.
Under the Alice Framework Step 2B analysis, claim 20 considered individually and as an ordered combination does not include additional elements that are sufficient to amount to significantly more than the abstract idea. As stated in the Step 2A prong 2 analysis, the claim does no more than generally link generically recited apparatus to a particular technological environment. For these reasons claim 20 does not amount to significantly more than the abstract idea.
Claim 1 is directed to a method that would be practiced by the apparatus as in claim 20. All steps performed by the method as in claim 1 is performed by the apparatus as in claim 20 as configured. The claim 20 analysis applies equally to claim 1.
Claims 2-18 are rejected for at least the reasons set forth with respect to claim 1. Claims 2-18 merely further mathematically limit the mathematical concepts of claim 1. Claims 2-18 contain no further additional elements beyond those recited in claim 1 that would require further analysis under step 2A prong 2 and step 2B.
Claim 19 is directed to a non-transitory computer readable storage medium storing instructions that when executed on a computer system, cause the computer system to perform the method as in claim 1. The claim 1 analysis applies equally to claim 19.
Claim Rejections - 35 USC § 102
In the event the determination of the status of the application as subject to AIA 35 U.S.C. 102 and 103 (or as subject to pre-AIA 35 U.S.C. 102 and 103) is incorrect, any correction of the statutory basis (i.e., changing from AIA to pre-AIA ) for the rejection will not be considered a new ground of rejection if the prior art relied upon, and the rationale supporting the rejection, would be the same under either status.
The following is a quotation of the appropriate paragraphs of 35 U.S.C. 102 that form the basis for the rejections under this section made in this Office action:
A person shall be entitled to a patent unless –
(a)(1) the claimed invention was patented, described in a printed publication, or in public use, on sale, or otherwise available to the public before the effective filing date of the claimed invention.
Claims 1, 5, 19, and 20 are rejected under 35 U.S.C. 102(a)(1) as being anticipated by T. Lu et al., Nonuniform Fast Fourier Transform on TPUS, 2021 IEEE 18th International Symposium on Biomedical Imaging (ISBI), April 13-16 2021, (hereinafter “Lu-Nonuniform”).
Regarding claim 1, Lu-Nonuniform teaches the following:
a method of implementing a discrete Fourier-related transform using a hardware accelerator comprising fixed-function circuitry including convolution hardware configured to perform one or more convolution operations, wherein the discrete Fourier-related transform comprises at least one matrix multiplication operation (abstract, implementing the nonuniform Fast Fourier Transform on Tensor Processing Units (TPUs), hardware accelerator for deep learning applications, Introduction 2nd-3rd paragraphs, TPU is an application specific integrated circuit (ASIC) for fixed-function circuitry, nonuniform Fourier transform formulated as a discrete Fourier transform (DFT), interpolation function of the FFT builds on a convolution, Kaiser-Bessel function is selected as the convolution kernel, Fourier transform formulated as dense matrix multiplications, section 2.3, introduction last paragraph, Lu-Nonuniform references using the approach of its citation [16] in the Kaiser-Bessel function, wherein the transformation of the Kaiser-Bessel function to a Kaiser-Bessel window is a fourier transform), the method comprising:
obtaining input data, wherein the input data contains values to undergo the discrete Fourier-related transform (Introduction, 1st paragraph, image reconstruction methods in magnetic resonance imaging (MRI) have an extensive usage of NUFFT when the k-space data are sampled, 3rd paragraph, sampled image, section 2. Discrete Fourier transform with unequally sampled data, sampling using TPU fig 1);
obtaining at least one convolution kernel, wherein each convolution kernel is derived from a weight matrix that represents a multiplicand or multiplier for the at least one matrix multiplication operation of the discrete Fourier-related transform (section 2.1 d(.) represents the inverse Fourier transform of a convolution kernel, using the Kaiser-Bessel function as the kernel, wherein D is the apodization operator representing a multiplicand or multiplier for the at least one matrix multiplication operation of the discrete Fourier-related transform as in eqn 2, eqn 3, fig 2); and
executing the discrete Fourier-related transform on the input data using the hardware accelerator (fig 2, fig, abstract), wherein the at least one matrix multiplication operation of the discrete Fourier-related transform is executed by using the convolution hardware to perform the one or more convolution operations using the at least one convolution kernel (abstract, the TPU is a hardware accelerator designed for deep learning applications, section 2 matrix multiplication is a convolution operation, section 2.3, introduction last paragraph, Lu-Nonuniform references using the approach of its citation [16] in the Kaiser-Bessel function, wherein the transformation of the Kaiser-Bessel function to a Kaiser-Bessel window is a fourier transform, abstract all three operations including using matrix multiplications).
Regarding claim 5, in addition to the teachings addressed in the claim 1 analysis, Lu-Nonuniform teaches the following:
wherein the discrete Fourier-related transform is a discrete Fourier transform (Introduction, second paragraph DFT).
Claim 19 is directed to a non-transitory computer readable storage medium having stored thereon computer readable instructions that when executed at a computer system, cause the computer system to perform the method as in claim 1. The claim 1 analysis applies equally to claim 19.
Regarding claim 20, Lu-Nonuniform teaches the following:
a data processing system for implementing a discrete Fourier-related transform, wherein the discrete Fourier-related transform comprises at least one multiplication operation (abstract, implementing the nonuniform Fast Fourier Transform on Tensor Processing Units (TPUs), hardware accelerator for deep learning applications, Introduction 2nd-3rd paragraphs, nonuniform Fourier transform formulated as a discrete Fourier transform (DFT), interpolation function of the FFT builds on a convolution, Kaiser-Bessel function is selected as the convolution kernel, Fourier transform formulated as dense matrix multiplications), the data processing system comprising:
a hardware accelerator comprising fixed-function circuitry configured to perform a set of available to perform a set of available elementary neural network operations, the fixed function circuitry comprising at least convolution hardware to configured to perform one or more convolution operations (abstract, TPU is an application specific integrated circuit (ASIC) hardware accelerator for comprising fixed-function circuitry, hardware accelerator for deep learning applications for to perform a set of available elementary neural network operations, Introduction 2nd-3rd paragraphs, nonuniform Fourier transform formulated as a discrete Fourier transform (DFT), interpolation function of the FFT builds on a convolution, Kaiser-Bessel function is selected as the convolution kernel); and
a controller (abstract, fig 1 TensorFlow) configured to:
obtain input data, wherein the input data contains values to undergo the discrete Fourier-related transform (Introduction, 1st paragraph, image reconstruction methods in magnetic resonance imaging (MRI) have an extensive usage of NUFFT when the k-space data are sampled, 3rd paragraph, sampled image, section 2. Discrete Fourier transform with unequally sampled data, sampling using TPU fig 1);
obtain at least one convolution kernel, wherein each convolution kernel is derived from a weight matrix that represents a multiplicand or multiplier for the at least one matrix multiplication operation of the discrete Fourier-related transform (section 2.1 d(.) represents the inverse Fourier transform of a convolution kernel, using the Kaiser-Bessel function as the kernel, wherein D is the apodization operator representing a multiplicand or multiplier for the at least one matrix multiplication operation of the discrete Fourier-related transform as in eqn 2, eqn 3, fig 2); and
execute the discrete Fourier-related transform on the input data using the hardware accelerator (fig 2, fig, abstract), wherein the at least one multiplication operation of the discrete Fourier-relate transform is executed by using the convolution hardware to perform one or more convolution operations using the at least one convolution kernel (abstract, the TPU is a hardware accelerator designed for deep learning applications, section 2 matrix multiplication is a convolution operation).
Claim Rejections - 35 USC § 103
The following is a quotation of 35 U.S.C. 103 which forms the basis for all obviousness rejections set forth in this Office action:
A patent for a claimed invention may not be obtained, notwithstanding that the claimed invention is not identically disclosed as set forth in section 102, if the differences between the claimed invention and the prior art are such that the claimed invention as a whole would have been obvious before the effective filing date of the claimed invention to a person having ordinary skill in the art to which the claimed invention pertains. Patentability shall not be negated by the manner in which the invention was made.
Claims 2-4 are rejected under 35 U.S.C. 103 as being unpatentable over Lu-Nonuniform in view of T. Lu et al., Large-Scale Discrete Fourier Transform on TPUs, IEEE Access, 7 July 2021 (hereinafter “Lu-Large-Scale”).
Regarding claim 2, Lu-Nonuniform discloses the claim 1 limitations. Lu-Nonuniform discloses the convolution kernel generally but does not explicitly disclose wherein each convolution kernel is generated by reshaping and/or permuting the dimensions of a respective weight matrix. However, in the same field of endeavors, with authors in common with Lu-Nonuniform, Lu-Large-Scale similarly discloses use of TPUs for executing the DFT (abstract, fig 1, section I, section II). Lu-Large-Scale further discloses:
wherein each convolution kernel is generated by reshaping and/or permuting the dimensions of a respective weight matrix (eqn (13), section III.A, eqn 1 rewritten in matrix form eqn (2) then to matrix of eqn (13)).
It would have been obvious to one of ordinary skill in the art before the effective filing date, to rewrite the DFT matrix of Lu-Nonuniform, into the matrix form of Lu-Large-Scale to achieve the benefit of a Kronecker product form can be used to contract the product as matrix multiplications of rank-2 and rank-3.
Regarding claim 3, in addition to the teachings addressed in the 2 analysis, Lu-Nonuniform teaches the following:
the convolution kernel is generated before the input data is obtained (fig 2, the kernel function values are precomputed on the CP host).
Regarding claim 4, in addition to the teachings addressed in the claim 1 analysis, Lu-Nonuniform teaches the following:
the input data comprises two or more sequences of values, each of which is to be individually transformed using a respective instance of the discrete Fourier-related transform (abstract MR image reconstruction for input data comprises two or more sequences of values, section I, sampled image. Section 2.2 FFT operates on image for each of which individually transformed using a respective instance of the discrete Fourier-related transform); and
Lu-Nonuniform discloses the convolution operation generally but does not explicitly disclose a single convolution operation is used to perform a matrix multiplication operation, of the at least one matrix multiplication operations, of multiple instances of the discrete Fourier-related transform on respective sequences of values. However, in the same field of endeavors, with authors in common with Lu-Nonuniform, Lu-Large-Scale similarly discloses use of TPUs for executing the DFT (abstract, fig 1, section I, section II). Lu-Large-Scale further discloses:
a single convolution operation is used to perform a matrix multiplication operation, of the at least one matrix multiplication operations, of multiple instances of the discrete Fourier-related transform on respective sequences of values (abstract. fig 3, section IIB, tensorflow including the convolution operator used for the DFT, fig 4 showing the multiple instances of the discrete Fourier-related transform on respective sequences of values as implemented in the TPU as a matrix multiplication operation).
It would have been obvious to one of ordinary skill in the art before the effective filing date, to formulate the discrete Fourier-related transform of Lu-Nonuniform, into the single convolution operation used by Lu-Large-Scale to perform a matrix multiplication operation, to achieve the benefit of achieving high parallel efficiency on TPUs (Section IV.A.)
Claims 6-7, 9-11, and 13-16 are rejected under 35 U.S.C. 103 as being unpatentable over Lu-Nonuniform in view of US 20180253402 A1 Redfern et al., (hereinafter “Redfern”).
Regarding claim 6, in addition to the teachings addressed in the claim 5 analysis, Lu-Nonuniform discloses wherein the input data comprises a first tensor to undergo the discrete Fourier transform (abstract, Section 1, FFT formulated as tensor operations implemented in TensorFlow), the discrete Fourier transform comprises a first set of matrix multiplications (section 2 first two paragraphs); and the first set of multiplications is executed by using the convolution hardware (abstract, section 1, TPU, TensorFlow).
Lu-Nonuniform does not, however, explicitly disclose wherein the first tensor comprises only the real part of values to undergo the discrete Fourier transform; and wherein the discrete Fourier transform comprises a first set of matrix multiplications comprising: multiplying the first tensor by a first weight matrix to produce a first multiplied tensor; and multiplying the first tensor by a second weight matrix to produce a second multiplied tensor; the at least one convolution kernel comprises a first convolution kernel derived from the first weight matrix and a second convolution kernel derived from the second weight matrix and the first set of matrix multiplications is executed by using the convolution hardware to perform at least two convolutions using the first and second convolution kernels. However, in the same field of endeavor, Redfern discloses and apparatus similar to Lu-Nonuniform wherein a processor comprising a matrix multiplication accelerator (MMA) is configured for FFT and convolutions ([0032], fig 2-12).
Redfern further discloses:
wherein: the input data comprises a tensor, comprising only the real part of values to undergo the discrete Fourier transform ([0087], [0090] XreM,N for first tensor comprising only the real part of the values to undergo the discrete Fourier transform);
the discrete Fourier transform comprises a first set of matrix multiplications comprising (Table 7, [0096-0101]):
multiplying the first tensor by a first weight matrix to produce a first multiplied tensor ([0091], [0098] top equation of the four); and
multiplying the first tensor by a second weight matrix to produce a second multiplied tensor ([0091], [0098] bottom equation of the four);
the at least one convolution kernel comprises a first convolution kernel derived from the first weight matrix and a second convolution kernel derived from the second weight matrix ([0091] top and bottom convolutional kernels, using Fre32, and Fim32).
the first set of matrix multiplications is executed using the convolution hardware to perform at least two convolutions using the first and second convolution kernels ([0091], [0098] top and bottom equations for at least two convolutions).
It would have been obvious to one of ordinary skill in the art before the effective filing date to organize the set of matrix multiplications executed using the convolution hardware (TPUs) of Lu-Nonuniform, to perform a first set of matrix multiplications on input data comprising only real values on first and second multiplied tensors as disclosed by Redfern, to achieve the benefit of performing smaller operations in batches (Redfern [0091-0092]).
Regarding claim 7, in addition to the teachings addressed in the claim 6 analysis, Lu-Nonuniform discloses wherein the input data comprises a tensor to undergo the discrete Fourier transform (abstract, Section 1, FFT formulated as tensor operations implemented in TensorFlow), the discrete Fourier transform comprises a set of matrix multiplications (section 2 first two paragraphs); and the set of multiplications is executed by suing the convolution hardware (abstract, section 1, TPU, TensorFlow).
Lu-Nonuniform does not, however, explicitly disclose wherein the second tensor comprises only the imaginary parts of values to undergo the discrete Fourier transform; and wherein the discrete Fourier transform comprises a second set of matrix multiplications comprising: multiplying the second tensor by a first weight matrix to produce a third multiplied tensor; and multiplying the second tensor by the second weight matrix to produce a fourth multiplied tensor; the second set of matrix multiplications is executed by using the convolution hardware to perform at least two convolutions using the first and second convolution kernel to perform the second set of multiplications. However, in the same field of endeavor, Redfern discloses and apparatus similar to Lu-Nonuniform wherein a processor comprising a matrix multiplication accelerator (MMA) is configured for FFT and convolutions ([0032], fig 2-12).
Redfern further discloses:
the input data further comprises a second tensor comprising only the imaginary parts of values to undergo the discrete Fourier transform ([0087], [0090] XimM,N for second tensor comprising only the imaginary parts of values to undergo the discrete Fourier transform);
the discrete Fourier transform comprises a second set of matrix multiplications (Table 7, [0096-0101]) comprising:
multiplying the second tensor by the first weight matrix to produce a third multiplied tensor ([0091], [0098] second from top equation of the four); and
multiplying the second tensor by the second weight matrix to produce a fourth multiplied tensor ([0091], [0098] second from bottom equation of the four); and
the second set of matrix multiplications is executed by using the convolution hardware to perform at least two convolutions using the first and second convolution kernel to perform the second set of matrix multiplications ([0091], [0098] middle two equations for at least two convolutions, [0091] middle two convolutional kernels, using Fim32, and Fre32) .
The motivation to combine set forth with respect to claim 6 applies equally to claim 7.
Regarding claim 9, Lu-Nonuniform in view of Redfern teach the claim 7 limitations. Redfern further discloses:
wherein the first and second set of matrix multiplications are performed by:
performing a first convolution on the first tensor using the first convolution kernel to produce the first multiplied tensor ([0091] top equation);
performing a second convolution on the first tensor using the second convolution kernel to produce the second multiplied tensor ([0091] second from top equation);
performing a third convolution on the second tensor using the first convolution kernel to produce the third multiplied tensor ([0091] second from bottom equation); and
performing a fourth convolution on the second tensor using the second convolution kernel to produce the fourth multiplied tensor ([0091] bottom equation).
The motivation to combine set forth with respect to claim 6 applies equally to claim 9.
Regarding claim 10, Lu-Nonuniform in view of Redfern teach the claim 6 limitations. Redfern further discloses:
subtracting the fourth tensor from the first tensor to produce the real part of the output of the discrete Fourier transform ([0090] top equation); and
summing the second and third tensors to produce the imaginary part of the output of the discrete Fourier transform ([0090] bottom equation).
The motivation to combine set forth with respect to claim 6 applies equally to claim 10.
Regarding claim 11, Lu-Nonuniform in view of Redfern teach the claim 6 limitations. Redfern further discloses:
the input data comprises only real values to undergo the discrete Fourier transform ([0087], [0090] XreM,N);
the first set of matrix multiplications is performed by:
performing a first convolution on the first tensor using the first convolution kernel to produce the first multiplied tensor ([0091], [0098] top equation of the four); and
performing a second convolution on the first tensor using the second convolution kernel to produce the second multiplied tensor ([0091], [0098] bottom equation of the four).
The motivation to combine set forth with respect to claim 6 applies equally to claim 11.
Regarding claim 13, in addition to the teachings addressed in the claim 5 analysis, Lu-Nonuniform discloses a method of implementing a discrete fast Fourier transform using a hardware accelerator comprising fixed-function circuitry including convolution hardware configured to perform one or more convolution operations (see claim 1 mapping upon which claim 5 depends), the method comprising:
obtaining input data, wherein the input data contains values to undergo the fast Fourier transform (Introduction, 1st paragraph, image reconstruction methods in magnetic resonance imaging (MRI) have an extensive usage of NUFFT when the k-space data are sampled, 3rd paragraph, sampled image)
Lu-Nonuniform does not, however, explicitly disclose dividing the input data into two or more parts; performing a discrete Fourier transform on each part of the input data using the method of claim 5 to produce a respective two or more DFT outputs; and combining the DFT outputs using the hardware accelerator to produce an FFT output that contains a fast Fourier transform of the input data. However, in the same field of endeavor, Redfern discloses and apparatus similar to Lu-Nonuniform wherein a processor comprising a matrix multiplication accelerator (MMA) is configured for FFT and convolutions ([0032], fig 2-12).
Redfern further discloses:
dividing the input data into two or more parts ([0090] xre, xim);
performing a discrete Fourier transform on each part of the input data using the method of claim 5 to produce a respective two or more DFT outputs ([0091]); and
combining the DFT outputs using the hardware accelerator to produce an FFT output that contains a fast Fourier transform of the input data ([0093], completing the steps of the ID FFT, then storing the rows of the resulting matrix in contiguous order for combining the DFT outputs).
It would have been obvious to one of ordinary skill in the art before the effective filing date to implement the discrete fast Fourier transform using the dividing approach of Redfern on the convolution hardware as disclosed by Lu-Nonuniform, to achieve the benefit of performing smaller operations in batches (Redfern [0091-0092]).
Regarding claim 14, Lu-Nonuniform in view of Redfern teach the claim 13 limitations. Redfern further discloses:
wherein the step of dividing the input data into two or more parts comprises processing the input data using two or more convolution kernels, each configured to extract a predetermined part of the input data ([0091] two convolution Kernels Fre, Fim).
The motivation to combine set forth with respect to claim 13 applies equally to claim 14.
Regarding claim 15, Lu-Nonuniform in view of Redfern teach the claim 13 limitations. Redfern further discloses:
wherein the step of dividing the input data into two or more parts comprises processing the input data using a deconvolution ([0101] transpose for deconvolution).
The motivation to combine set forth with respect to claim 13 applies equally to claim 15.
Regarding claim 16, Lu-Nonuniform in view of Redfern teach the claim 13 limitations. Redfern further discloses:
wherein the input data comprises a first tensor containing real parts of the values to undergo the fast Fourier transform ([0087]), and the step of dividing the input data into two or more parts comprises:
processing the first tensor using an odd-sampling convolution kernel to produce an odd tensor containing only the odd-indexed values of the first tensor ([0032]); and
processing the first tensor using an even-sampling convolution kernel to produce an even tensor containing only the even-indexed values of the first tensor ([0032]).
The motivation to combine set forth with respect to claim 13 applies equally to claim 15.
Claims 17-18 are rejected under 35 U.S.C. 103 as being unpatentable over Lu-Nonuniform in view of Redfern.
Regarding claim 17, Lu-Nonuniform teaches the claim 1 limitations. Lu-Nonuniform is silent with respect to a discrete cosine transform. However, in the same field of endeavor, Redfern discloses and apparatus similar to Lu-Nonuniform wherein a processor comprising a matrix multiplication accelerator (MMA) is configured for FFT and convolutions ([0032], fig 2-12).
Redfern further discloses wherein the discrete Fourier related transform is a discrete cosine transform ([0103]).
It would have been obvious to one of ordinary skill in the art before the effective filing date to use the convolution hardware of Lu-Nonuniform to perform a discrete cosine transform because the discrete cosine transform is similar to the FFT, and DCT can be implemented via matrix vector multiplication ([0102]). It is obvious to use a known technique to improve similar devices in the same way. See MPEP 2141.III.(A).
Regarding claim 18, Lu-Uniform in view of Redfern teach the claim 17 limitations. Redfern further discloses:
the input data comprises a first tensor, comprising real values to undergo the discrete cosine transform ([0102] similar to FFT but data is real);
the discrete cosine transform comprises a DCT multiplication operation comprising multiplying the first tensor by a DCT weight matrix to produce an output of the discrete cosine transform ([0102] DCT matrix for DCT weight matrix, data for first tensor multiplication similar to FFT);
the at least one convolution kernel comprises a DCT convolution kernel derived from the DCT weight matrix ([0102] DCT matrix for convolution kernel, similar to FFT); and
the DCT multiplication operation is executed by using the convolution hardware to perform a convolution of the first tensor using the DCT convolution kernel ([0102], [0103] similar to FFT).
The motivation to combine provided with respect to claim 17 applies equally to claim 18.
Allowable Subject Matter
For the reasons set forth in the office action dated 03/23/26, claims 8 and 12 would be allowable if rewritten to overcome the rejections under 35 USC 101, and rewritten in independent form including all of the limitations of the base claim and any intervening claims.
Conclusion
THIS ACTION IS MADE FINAL. Applicant is reminded of the extension of time policy as set forth in 37 CFR 1.136(a).
A shortened statutory period for reply to this final action is set to expire THREE MONTHS from the mailing date of this action. In the event a first reply is filed within TWO MONTHS of the mailing date of this final action and the advisory action is not mailed until after the end of the THREE-MONTH shortened statutory period, then the shortened statutory period will expire on the date the advisory action is mailed, and any nonprovisional extension fee (37 CFR 1.17(a)) pursuant to 37 CFR 1.136(a) will be calculated from the mailing date of the advisory action. In no event, however, will the statutory period for reply expire later than SIX MONTHS from the mailing date of this final action.
The prior art made of record and not relied upon is considered pertinent to applicant's disclosure.
Any inquiry concerning this communication or earlier communications from the examiner should be directed to EMILY E LAROCQUE whose telephone number is (469)295-9289. The examiner can normally be reached on 10:00am - 1200pm, 2:00pm - 8pm ET M-F.
Examiner interviews are available via telephone, in-person, and video conferencing using a USPTO supplied web-based collaboration tool. To schedule an interview, applicant is encouraged to use the USPTO Automated Interview Request (AIR) at http://www.uspto.gov/interviewpractice.
If attempts to reach the examiner by telephone are unsuccessful, the examiner’s supervisor Andrew Caldwell can be reached on 571-272-3701. The fax phone number for the organization where this application or proceeding is assigned is 571-273-8300.
Information regarding the status of an application may be obtained from the Patent Application Information Retrieval (PAIR) system. Status information for published applications may be obtained from either Private PAIR or Public PAIR. Status information for unpublished applications is available through Private PAIR only. For more information about the PAIR system, see http://pair-direct.uspto.gov. Should you have questions on access to the Private PAIR system, contact the Electronic Business Center (EBC) at 866-217-9197 (toll-free). If you would like assistance from a USPTO Customer Service Representative or access to the automated information system, call 800-786-9199 (IN USA OR CANADA) or 571-272-1000.
/EMILY E LAROCQUE/Examiner, Art Unit 2182
Prosecution Insights