From my quick look at this, I can see that this is based on FFT Fast Fourier Transforms which is a public domain algorithm.
From "The FFT - an algorithm the whole family can use"
A paper by Cooley and Tukey [5] described a recipe for computing Fouri-
er coecients of a time series that used many fewer machine operations than
did the straightforward procedure...What lies over the horizon in digital signal
processing is anyone's guess, but I think it will surprise us all.
We are surprised.
"It seems almost everyone knows that
somehow all the data whizzing over the internet, bustling through our modems
or crashing into our cell phones is ultimately just a sequence of 0's and 1's {
a digital sequence { that magically makes the world the convenient high speed
place it is today. So much of this magic is due to a family of algorithms that
collectively go by the name "The Fast Fourier Transform", or "FFT" to its
friends, among which the version published by Cooley and Tukey [5] is the most
famous. Indeed, the FFT is perhaps the most ubiquitous algorithm used today
in the analysis and manipulation of digital or discrete data."
So it's an obvious choice and the most common used data analysis algorithm known to man and it's in the Public Domain.
"My own research experience with various avors of the FFT is evidence of the
wide range of applicability: electroacoustic music and audio signal processing,
medical imaging, image processing, pattern recognition, computational chem-
istry, error correcting codes, spectral methods for PDEs and last but not least,
in mathematics, as the starting point of my doctoral dissertation in computa-
tional harmonic analysis which investigated group theoretic generalizations of
the Cooley-Tukey FFT. Of course many more could be listed, notably those to
radar and communications. The book 2 is an excellent place to look, especially
pages 2 and 3 which contain a (nonexhaustive) list of seventy-seven applications"
This was written in 1999.
"Despite these early discoveries of an FFT, it wasn't until Cooley and Tukey's
article that the algorithm gained any notice. The story of their collaboration
is an interesting one. Tukey arrived at the basic reduction while in a meeting
of President Kennedy's Science Advisory Committee where among the topics of
discussions were techniques for o-shore detection of nuclear tests in the Soviet
Union. Ratication of a proposed United States/Soviet Union nuclear test ban
depended upon the development of a method for detecting the tests without
actually visiting the Soviet nuclear facilities. One idea was to analyze seismo-
logical time series obtained from o-shore seismometers, the length and number
of which would require fast algorithms for computing the DFT. Other possible
applications to national security included the long-range acoustic detection of
nuclear submarines."
So obviously, FFT was treated with the highest National Security in mind when it was discovered.
"Richard Garwin of IBM was another of the participants at this meeting
and when Tukey showed him this idea he immediately saw a wide range of
potential applicability and quickly set to getting this algorithm implemented.
He was directed to Cooley, and, needing to hide the national security issues,
instead told Cooley that he wanted the code for another problem of interest:
the determination of the periodicities of the spin orientations in a 3-D crystal of
He3. Cooley had other projects going on, and only after quite a lot of prodding
did he sit down to program the "Cooley-Tukey" FFT. In short order, Cooley
and Tukey prepared a paper which, for a mathematics/computer science paper,
was published almost instantaneously (in six months!) [5]. This publication, as
well as Garwin's fervent prosletizing, did a lot to help publicize the existence of
this (apparently) new fast algorithm. (See also [4] and the introductory papers
of [17] for more historical details."
So this obviously caught the eye of the government, along with IBM.
The timing of the announcement was such that now usage spread quickly.
The roughly simultaneous development of analog to digital converters capable
of producing digitized samples of a time-varying voltage at rates of 300,000
samples/second had already initiated something of a digital revolution, and was
also providing scientists with heretofore unimagined quantities of digital data
to analyze and manipulate (just as is the case today!). Even the standard applications of Fourier analysis as an analysis tool for waveforms or solving PDEs,
meant that a priority there would be a tremendous interest in the algorithm. But
even more, the ability to do this analysis quickly allowed scientists from new
areas to try the DFT without having to invest too much time and energy in the
exercise. I can do no better than to quote the introduction to the FFT from
Numerical Recipes, If you speed up any nontrivial algorithm by a factor of a
million or so the world will beat a path towards nding useful applications for
it 3."
Indeed, it's powerful, now free, and non-trivial to use.
Even beyond these direct technological applications, the FFT influenced the
direction of academic research too.
Academic research. Doesn't the app being sued cost a few dollars on the app store? I'd say it's a fair allocation of an FFT algorithm.
"Ironically, the prominence of the FFT may have also contributed to slow oth-
er areas of research. The FFT provided scientists with a big analytic hammer,
and for many, the world suddenly looked as though it was full of nails { even if
this wasn't always so."
Taken out of context perhaps, but I'd say patenting anything that uses the FFT algorithms and re-wording it, without it being actually examined is a "big analytical hammer".
Even now there are still lessons to be learned from the FFT's development.
In this day and age in which almost any new technological idea seems fodder for
internet venture capitalists and patent lawyers, it is natural to ask, Why was
the FFT not patented by IBM?" As Cooley tells the story, on the one hand,Tukey was not an IBM employee, so IBM had some worry that they might not
be able to gain the patent. Consequently, they had great interest in putting
the algorithm in the public domain. The eect of this was that no one else
would be able to patent the algorithm, and even more, like many computer
manufacturers of that time, the thought was that the money was to be made in
hardware, not software. In fact, the FFT was designed as a tool for the analysis
of huge time series, in theory something only tackled by supercomputers. So
by placing in the public domain an algorithm which would make feasible the
analysis of large time series, more big companies might have an interest in buying
supercomputers (like IBM mainframes) to do their work. Times certainly have
changed.
Whether having the FFT in the public domain had the eect IBM hoped for
is moot, but it is certain that it did provide many, many scientists with appli-
cations to work on and apply the algorithm. The breadth of scientic interests
at the Arden workshop (held only two years after publication of the paper) is
truly impressive. In fact, the rapid pace of today's technological developments
is in many ways a testament to the advantage of this open development. This
is a cautionary tale in today's arena of proprietary research, and we can only
wonder which of the many recent private technological discoveries might have
prospered from a similar announcement
There's a very interesting quote, extracted from above:
"In this day and age in which almost any new technological idea seems fodder for
internet venture capitalists and patent lawyers, it is natural to ask, Why was
the FFT not patented by IBM?"
An algorithm for the machine calculation of complex Fourier series Authors James W. Cooley and John W. Tukey 1965
Full PDF Free Access of Cooley and Turkey's Paper
The '060 Patent on FFT
The '060 Patent talks about using Fourier and basically claims that all others do it wrong?
FIG. 6 shows an embodiment of the Power-Spectral Estimator 78 as referenced in FIG. 5. The Power-Spectral Estimator 78 receives a series of buffered time samples from the Buffer 70 in FIG. 5 and optionally conditions the samples with Zero-padding 84 and Windowing 86 prior to converting the time samples to the frequency domain with a Fast Fourier Transform (FFT) 88. Zero-padding 84 refers to adding zero-value samples to the predominately non-zero value series of time samples to increase the size of the FFT and hence the resulting frequency resolution
And then...
The FFT is a specific implementation of a Time-To-Frequency-Transform, defined herein to refer to the conversion of time samples to the frequency domain irrespective of the algorithm used. For example, in other embodiments the Time-To-Frequency-Transform uses either a Discrete Fourier Transform (DFT), a Discrete Cosine Transform (DCT), a Fast Cosine Transform, a Discrete Sine Transform (DST) or a Fast Sine Transform (FST).
And then...
In a preferred embodiment Zero-padding 84 is used with Windowing 86. Because the series of time samples, with or without the Zero-padding 84, only represents a finite observation window, the resulting spectral information will be distorted after performing an FFT due to the ringing or sin(f)/f spectral peaks of the rectangular window. This is also referred to as “spectral leakage.” To correct for this, each sample in a series of time samples is multiplied by a sample from a fixed waveform such as a Hanning, Bartlett or Kaiser window. In this embodiment these window functions have the same number of samples as the FFT (e.g. 4096), have symmetry about N/2 and increase in value from close to zero at the beginning and end of the time series to a maximum value at the center of the time series. In a preferred embodiment, a Blackman-Harris window function is used.
And then...
In a preferred embodiment the time samples are preconditioned with Zero-padding 84 and Windowing 86 and are subsequently converting to the frequency domain with an FFT processor. It is envisioned that any Discrete Fourier Transform (DFT) can be used to perform the frequency conversion without being limited to using an FFT. Following the FFT 88, the series of frequency samples forming an estimate of the frequency spectrum is converted into a power-spectral estimate by squaring each of the frequency samples with a Magnitude Squared function 90.
The description in the '060 talks about FFT in it's digital sense, yet it's claims are overly broad because it's not bound to a specific device by the sense that if you are listening to anything and select the highest frequency, loudest person, loudest sound and focus on it, you are infringing upon '060.
prior-art-request
(from: 