DETAILED ACTION
Notice of Pre-AIA or AIA Status
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 Amendment
Applicant’s arguments are moot based on new grounds of rejection.
Claim Rejections - 35 USC § 103
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 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.
Claim(s) 1-2, 6, 7, 9, 10, 16-18 is/are rejected under 35 U.S.C. 103 as being unpatentable by Gupta et. al. (US 20200319296) (hereinafter "Gupta"), in view of Wu et al (US 20210132215 A1, hereinafter “Wu”)
Regarding claim 1, Gupta teaches a radar system (paragraph 0019: “One example of an application that benefits from efficient 2D FFT computation is a frequency-modulated continuous wave (FMCW) radar system”) comprising: an analog to digital converter (ADC) (paragraph 0025: “An analog-to-digital converter (ADC) 116 in the receive channel 114 digitizes the IF signals”); a digital processing unit coupled to the ADC (paragraph 0025: “The digital IF signals are sent by the ADC 116 to a digital signal processor (DSP) 118 for further processing”), the digital processing unit comprising: a plurality of Fast Fourier Transform (FFT) elements (paragraphs 0040, 0041: “In a first step, a 1D FFT is computed along a first dimension […] In a second step, a 1D FFT is computed along a second dimension”); and a plurality of memory storage devices coupled to the plurality of FFT elements, wherein the plurality of FFT elements and the plurality of memory storage devices are configured in a pipeline (paragraph 0040: “The butterfly units 302 […] includes a first input 306 that is either coupled to a memory (not shown for simplicity, but for example storing data upon which a FFT is to be performed)”) comprising a number of stages, wherein each of the plurality of stages comprises a number of FFT elements of the plurality of FFT elements (paragraph 0038); an address remapping unit configured to digit reverse input indices (see ¶[0037, 0049], fig. 4) prior to feeding the input to the digital processing unit (see fig. 4 step 2); a twiddle factor table comprising a plurality of twiddle factors (paragraph 0036: “The twiddle factor tables 316 include twiddle factors stored in memory, for example read-only memory (ROM)”), wherein the twiddle factor table comprises at least each twiddle factor of the plurality of twiddle factors corresponding to an FFT element in the plurality of FFT elements (paragraph 0023: “through application of twiddle factor addressing logic, the initial group of stages effectively performs an N-point 1D FFT in a transpose direction.” and paragraph 0065: “operations carried out by the butterfly unit 302 of Stage 1 correspond to the first add/subtract operations of each of the M columns, all of which would conventionally be multiplied with the first element of the twiddle factor table for an N-point 1D FFT”) and a twiddle factor lookup stage corresponding to each one of the plurality of stages, the twiddle lookup factor lookup stage configured to determine a twiddle factor from the twiddle factor table based on a stage number (paragraph 0003), a size of the FFT element (paragraph 0060), and a current index (paragraph 0003).
Gupta fails to specifically disclose wherein each of the plurality of stages comprises two or more FFT elements of the plurality of FFT elements, wherein the two or more FFT elements in each of the plurality of stages are configured to run in parallel, however Wu as discloses the well known process of parallel processing.
In the same field of endeavor, Wu discloses wherein the two or more FFT elements in each of the plurality of stages are configured to run in parallel, however Wu as discloses the well known process of parallel processing (see Wu, ¶ 0015 and 0038, In still further embodiments, the FFT circuits include a plurality of hardware cores configured to process the FFT data in parallel to output the interpolated FFT data.)
It would have been obvious to someone of ordinary skill in the art before the effective filing date of the claimed invention to have modified Gupta’s system with the parallel processing of Wu, thereby increasing speed of processing.
Regarding claim 2, Gupta teaches the radar system of claim 1. Gupta also teaches a control unit coupled to the digital processing unit and configured to control each of the plurality of FFT elements a predetermined number of times (paragraph 0043: “ In particular, the R2SDF hardware accelerator 300 and associated logic 502, 504 are configured to perform a pipelined 2D FFT on an M×N array (e.g., M×N array 402) with a R2SDF hardware accelerator 300 having at least log.sub.2 M×N stages”).
Claim 3 (Cancelled).
Regarding claim 6, Gupta teaches the radar system of claim 1. Gupta also teaches at least one twiddle factor of the twiddle factor table is a multiplier in FFT processing (paragraph 0032: “the butterfly unit 302 includes a first input 306 that is either coupled to a memory (not shown for simplicity, but for example storing data upon which a FFT is to be performed) or to a previous stage output. The butterfly unit 302 includes a second input 308, which is the output of the FIFO buffer 304a. The butterfly unit 302 includes a first output 310, which is the input of the FIFO buffer 304a. Finally, the butterfly unit 302 includes a second output 312, which is provided as an input to a multiplier 314. The other input to the multiplier 314 is data from a twiddle factor table 316”).
Regarding claim 7, Gupta teaches the radar system of claim 1. Gupta also teaches the plurality of FFT elements process data iteratively (paragraph 0035: “During the first 16 cycles, the butterfly unit 302 is operated in bypass mode, which has the effect of filling the FIFO buffer 304a with the first 16 elements on which the 1D FFT is being computed. During the next 16 cycles, the butterfly unit 302 is operated in add/subtract mode”).
Regarding claim 9, Gupta teaches the radar system of claim 1. Gupta also teaches an input to the pipeline is provided in increments (paragraph 0002: “an output of a last stage of the final group of stages is provided as an input to a first stage of the initial group of stages”).
Regarding claim 10, Gupta teaches the radar system of claim 9. Gupta also teaches a final stage of the pipeline accesses multiple increments (paragraph 0032: “Each stage includes a butterfly unit 302 coupled to a first-in first-out (FIFO) buffer 304. The butterfly units 302 for each stage are functionally the same, while the FIFO buffers 304a-e are similar in function but differ in their size. Referring to stage 1, the butterfly unit 302 includes a first input 306 that is either coupled to a memory (not shown for simplicity, but for example storing data upon which a FFT is to be performed) or to a previous stage output. The butterfly unit 302 includes a second input 308, which is the output of the FIFO buffer 304a. The butterfly unit 302 includes a first output 310, which is the input of the FIFO buffer 304a. Finally, the butterfly unit 302 includes a second output 312, which is provided as an input to a multiplier 314. The other input to the multiplier 314 is data from a twiddle factor table 316, which will be explained in further detail below”).
Regarding claim 16, the limitations have been addressed in the rejection of claim 1.
Regarding claim 17, Gupta teaches the method of claim 16. Gupta also teaches the digital processing method is a Fast Fourier Transform (FFT) processing (paragraph 0040, 0041: “In a first step, a 1D FFT is computed along a first dimension […] In a second step, a 1D FFT is computed along a second dimension”).
Regarding claim 18. Gupta teaches the method of claim 17. Gupta also teaches prior to determining the number of cycles for each stage, calculating an operational coefficient for each of the stages, wherein the operational coefficient comprises a twiddle factor (paragraph 0036: “The twiddle factor tables 316 include twiddle factors stored in memory, for example read-only memory (ROM). The twiddle factor table 316 for Stage 1 includes 32 elements (e.g., to be applied to the 16 sums and 16 differences generated by the butterfly unit 302 during the 16 cycles in add/subtract mode and the subsequent 16 cycles in bypass mode), while the twiddle factor table 316 for Stage 3 includes 8 elements, and so on. The values in such twiddle factor tables 316 are known in the art. For example, when the output from the butterfly unit 302 is a summed output, the twiddle factor values are 1, effectively bypassing the multiplier 314. Then, when the output from the butterfly unit 302 is a subtracted output, the twiddle factor values are complex numbers, which are multiplied with the subtracted output by the multiplier 314.”).
Claim 20, Cancelled.
Claim(s) 4 is/are rejected under 35 U.S.C. 103 as being unpatentable over Gupta and Wu further in view of Lerner (CN 108701119).
Regarding claim 4, Gupta teaches the radar system of claim 1.
Gupta does not teach at least a portion of the plurality of FFT elements are base 4 elements. However, Lerner teaches at least a portion of the plurality of FFT elements are base 4 elements (paragraph 0073: “For example, one FFT algorithm may include 6 stages, and the other FFT algorithm may include 8 stages, and/or one FFT algorithm may include a base -2 stage, and the other may include a base -4 stage”).
It would have been obvious to someone of ordinary skill in the art before the effective filing date of the claimed invention to have modified the combination Gupta and Wu with Lerner’s base-4 FFT elements to achieve different levels and meet requirements of efficiency.
Claim(s) 5 and 8 is/are rejected under 35 U.S.C. 103 as being unpatentable over Gupta and Wu further in view of He et. al. (WO 9719412) (later referred to as He).
Regarding claim 5, Gupta teaches the radar system of claim 1. Gupta further teaches each FFT element is cycled four times (paragraph 0035: “For example, Stage 3 operates four cycles in each of the bypass and add/subtract modes, and so forth”) to generate an output (paragraph 0038: “For example, an 8-point 1D FFT is computed by inserting input elements from memory to the butterfly unit 302 of Stage 3”).
The combination of Gupta and Wu do not teach the pipeline comprises four stages or each stage comprising four FFT elements. However, He teaches the pipeline comprises four stages (page 10, lines 2-3: “and said processor may have four processing stages in said pipeline,”) and each stage (page 8, lines 15-22: “According to a first aspect of the present invention, there is provided a real-time pipeline fast fourier transform processor, characterised in that said processor includes a plurality of paired first and second butterfly means, each of said first butterfly means and each of said second butterfly means having a feedback path between an output therefrom to an input thereto” and page 2, lines 21-23: “The architecture of the processor is described as a single-path delay feedback because only a single data path exists between butterfly stages”) comprising four FFT elements (page 18 line 35-page 19 line 2: “The butterfly unit comprises two adders, 21, two subtractors, 22, and four multiplexers 23, connected as shown in Figure 10”).
It would have been obvious to someone of ordinary skill in the art before the effective filing date of the claimed invention to have modified the combination of Gupta and Wu with He’s four stages and FFT elements to compartmentalize and streamline the processing pipeline.
Regarding claim 8, Gupta teaches the radar system of claim 1.
The combination of Gupta and Wu do not teach the plurality of memory storage devices includes a set of registers. However, He teaches the plurality of memory storage devices includes a set of registers (page 20, lines 16-20: “In a practical implementation of the radix-2 SDF processor, pipeline registers should be inserted between each multiplier and butterfly stage to improve performance. Shimming registers are also needed so that the control signals comply with the revised timing”).
It would have been obvious to someone of ordinary skill in the art before the effective filing date of the claimed invention to have modified the combination Gupta and Wu system with He’s registers to improve performance and comply with timing requirements.
Claim(s) 11-12, 14 is/are rejected under 35 U.S.C. 103 as being unpatentable over Gupta and Wu in view of Jaber (US 20010032227).
Regarding claim 11, Gupta teaches a digital processing system (paragraph 0025: “The digital IF signals are sent by the ADC 116 to a digital signal processor (DSP) 118 for further processing. The DSP 118 may perform signal processing on the digital IF signals”), comprising: a plurality of stages of processing elements configured in a sequence (paragraph 0032: “As shown, the R2SDF hardware accelerator 300 includes multiple stages, labeled Stage 1-5. Each stage includes a butterfly unit 302 coupled to a first-in first-out (FIFO) buffer 304”), wherein a number of stages (paragraph 0002: “The hardware accelerator includes log.sub.2 M×N pipeline stages“) is a function of a number of inputs and the plurality of stages form a processing pipeline (paragraph 0001-0002: “The hardware accelerator also includes butterfly control logic to provide elements of the M×N element array to the initial group of stages in an N direction of the array, and twiddle factor addressing logic to, for the twiddle factor tables of the initial group of stages, apply an indexed entry of the twiddle factor table to the associated multiplier. The indexed entry begins as a first entry and advances by N entries after every N cycles. [...] The hardware accelerator also includes twiddle factor addressing logic configured to, for the twiddle factor tables of the initial group of stages, apply an indexed entry of the twiddle factor table to the associated multiplier. The indexed entry begins as a first entry and advances by M entries after every M cycles”), wherein each of the plurality of stages comprises a number of FFT elements (paragraph 0038), a twiddle factor table comprising a plurality of twiddle factors (paragraph 0036), and a twiddle factor lookup stage corresponding to each one of the plurality of stages, the twiddle factor lookup stage configured to determine a twiddle factor from the twiddle factor table based on a stage number (paragraph 0003), a size of the FFT (paragraph 0060), and a current index (paragraph 0003); an address remapping module coupled to the plurality of stages (see ¶[0037, 0049], fig. 3 and 4) prior to feeding the input to the digital processing unit (see fig. 4 step 2); a plurality of memory storage devices coupled to each stage of the plurality of stages, the plurality of memory storage devices adapted to store interim results (paragraph 0032: “Each stage includes a butterfly unit 302 […] the butterfly unit 302 includes a first input 306 that is either coupled to a memory (not shown for simplicity, but for example storing data upon which a FFT is to be performed) or to a previous stage output”); and a controller adapted to iteratively process data through the processing elements (paragraph 0035: “During the first 16 cycles, the butterfly unit 302 is operated in bypass mode, which has the effect of filling the FIFO buffer 304a with the first 16 elements on which the 1D FFT is being computed. During the next 16 cycles, the butterfly unit 302 is operated in add/subtract mode”).
Gupta does not teach a final stage of processing elements configured to combine outputs from the sequence of the plurality of stages. However, Jaber teaches a final stage of processing elements configured to combine outputs from the sequence of the plurality of stages (paragraph 0011: “The outputs of the first stage 1302 are combined in 2 additional stages 1304, 1306 to form a complete 8-point DPT output, X.sub.n.”)
It would have been obvious to someone of ordinary skill in the art before the effective filing date of the claimed invention to have modified Gupta’s system with Jaber’s output combination to complete Fourier processing and to compress results for ease of access or interpretation.
The combination of Gupta and Jaber fail to specifically disclose wherein each of the plurality of stages comprises two or more FFT elements of the plurality of FFT elements, wherein the two or more FFT elements in each of the plurality of stages are configured to run in parallel, however Wu as discloses the well known process of parallel processing.
In the same field of endeavor, Wu discloses wherein the two or more FFT elements in each of the plurality of stages are configured to run in parallel, however Wu as discloses the well known process of parallel processing (see Wu, ¶ 0015 and 0038, In still further embodiments, the FFT circuits include a plurality of hardware cores configured to process the FFT data in parallel to output the interpolated FFT data.)
It would have been obvious to someone of ordinary skill in the art before the effective filing date of the claimed invention to have modified Gupta and Jaber with the parallel processing of Wu, thereby increasing speed of processing.
Regarding claim 12, Gupta and Jaber teach the system of claim 11. Gupta further teaches a lookup table coupled to the controller, the lookup table storing a plurality of operational coefficients comprising twiddle factors (paragraph 0036: “The twiddle factor tables 316 include twiddle factors stored in memory, for example read-only memory (ROM). The twiddle factor table 316 for Stage 1 includes 32 elements (e.g., to be applied to the 16 sums and 16 differences generated by the butterfly unit 302 during the 16 cycles in add/subtract mode and the subsequent 16 cycles in bypass mode), while the twiddle factor table 316 for Stage 3 includes 8 elements, and so on. The values in such twiddle factor tables 316 are known in the art. For example, when the output from the butterfly unit 302 is a summed output, the twiddle factor values are 1, effectively bypassing the multiplier 314. Then, when the output from the butterfly unit 302 is a subtracted output, the twiddle factor values are complex numbers, which are multiplied with the subtracted output by the multiplier 314”.
Claim 13 (Cancelled)
Regarding claim 14, Gupta and Jaber teach the system of claim 13. Gupta further teaches an address remapping module coupled to the plurality of stages (paragraph 0042: “In the example of FIG. 4, the butterfly units 302 of Stages 1 and 2 are not used, since first an 8-point 1D FFT is performed across columns (involving Stages 3-5), the result is stored to memory (e.g., after a bit-reversal algorithm is applied), and then a 4-point 1D FFT is performed across rows (involving Stages 4-5).”)
Claim(s) 15 is/are rejected under 35 U.S.C. 103 as being unpatentable over Gupta, Jaber and Wu further in view of Marchant (US 6035313).
Regarding claim 15, Gupta and Jaber teach the system of claim 14.
Neither Gupta, Wu nor Jaber teach each stage of the plurality of stages includes radix-4 FFT elements. However, Marchant teaches each stage of the plurality of stages (paragraph 57: “The butterfly input and output indices are shown grouped within `boxes`, with the box size indicating the radix of the butterfly. For radix-4, for example, the inputs and outputs are shown in groups of 4. This `boxing` convention then explicitly conveys the radix for each stage”) includes radix-4 FFT elements (paragraph 119: “Consider now FIG. 3, which shows FFT time flow diagram 40 for a radix-4,3,2 FFT; i.e., a 24-point FFT”).
It would have been obvious to someone of ordinary skill in the art before the effective filing date of the claimed invention to have modified the system of Gupta, Wu and Jaber with Marchant’s radix-4 FFT elements to meet efficiency requirements.
Claim 19 is rejected under 35 U.S.C. 103 as being unpatentable over Gupta and Wu in view of Jacob (US 20180253399).
Regarding claim 19, Gupta teaches the method of claim 18.
Gupta does not teach the twiddle factor is a trigonometric constant. However, Jacob teaches the twiddle factor is a trigonometric constant (paragraph 0005: “A twiddle factor, in FFT algorithms, is any of the trigonometric constant coefficients that are multiplied by the data in the course of the algorithm”).
It would have been obvious to someone of ordinary skill in the art before the effective filing date of the claimed invention to have modified the combination of Gupta and Wu Jacob’s trigonometric twiddle factor because twiddle factors are known in the art to include trigonometric constants.
Conclusion
The prior art made of record and not relied upon is considered pertinent to applicant's disclosure. Mundhada US 20170103042 A1.
Any inquiry concerning this communication or earlier communications from the examiner should be directed to VLADIMIR MAGLOIRE whose telephone number is (571)270-5144. The examiner can normally be reached 9-5 PM 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, Namrata Boveja can be reached at (571) 272-8105. The fax phone number for the organization where this application or proceeding is assigned is 571-273-8300.
Information regarding the status of published or unpublished applications may be obtained from Patent Center. Unpublished application information in Patent Center is available to registered users. To file and manage patent submissions in Patent Center, visit: https://patentcenter.uspto.gov. Visit https://www.uspto.gov/patents/apply/patent-center for more information about Patent Center and https://www.uspto.gov/patents/docx for information about filing in DOCX format. For additional questions, contact the Electronic Business Center (EBC) at 866-217-9197 (toll-free). If you would like assistance from a USPTO Customer Service Representative, call 800-786-9199 (IN USA OR CANADA) or 571-272-1000.
/VLADIMIR MAGLOIRE/Supervisory Patent Examiner, Art Unit 3648
Prosecution Insights