Slashdot Mirror
IDCT Approximation: Worth a Patent?
Between 1804 and 1807 Jean Fourier discovered the
Fourier
Transform: a means of transforming any function into its
frequency
components. He initially used it to study the
propagation of heat in solids. Since then the Fourier transform has found a
myriad of applications such as the JPEG, MPEG and MP3 formats... It's even been used to multiply polynomials. The main computational cost of the Fourier
transform are the N^2 multiplications it requires. In 1903 Runge noticed that
the number of multiplications required could be reduced to N.log(N) by using
trigonometric symmetries. In 1965 this was applied in computers by Cooley and
Tukey: the fast Fourier transform became
popular. Since computers represent numbers in binary, multiplications and
divisions by powers of 2 are commonly implemented by shifting bits left and
right. Multiplications by constants are easily optimized using the same
trick. In 1999 Trac
Tran of Johns Hopkins University found an
approximation to the
DCT which causes very little error, yet uses only 13 shifts and 31
additions for N=8. Given the recursive nature of the FFT, this transform could be used as part of an FFT with N>8. Apparently, he
has applied for a
patent for this approximation. Do you think this is worth a patent? Do you know of prior art?
From the looks of things this is a valid patent, I don't really have the inclination to look for relavent prior art but there are other fast approaches to the cosine transform. This would represent at the very least an incremental improvement over an existing procedure.
Now, as far as some of the comments that I've seen stating "No, don't patent this" most of them are based on a pretty wild abuse of what is being patented.
This is not like Einstein patenting relativistic effects. This is so wrong I can't even draw a parallel. Slashdot poster credibility goes "Boink".
This isn't like patenting a form of arithmetic. There are patents on fast ways of doing various arithmetic operation, you're still free to do arithmetic. What you're not free to do is to use that particular method of speeding operations. For the average person it doesn't matter. For somebody designing circuitry for fast computer hardware maybe it matters. If so you license the patent, or you hire your own mathematicians or you just use some other method.
Now, is the patent worth much? Probably not. There are other fast discrete cosine transforms. I used to work/share an office with one of the leading experts on that particular transform. Consider that even if this invention is two fold faster than the preceding state of the art Moore's law means the present state of the art will be as fast as this new transform in 18 months. So for this particular operation if there was a 2 times performance increase some company could say they were 18 months ahead of the competition. Big deal since there are enough other factors that are more important to determine performance for most applications. Expecting a 2X improvement is also terribly optimistic. He compared his algorithm to the short hand notation for the DCT/IDCT. In reality a lot of the multiplications would be handled by shifts anyway and there are already other fast implementations.
Here's a good test: give an example of a non-patented software application for lzw where you'd be "perfectly free" to use it. You can't. The basic problem here is that the USPTO and the courts have accepted the idea that software itself is an "application".
But there's such a fine line between the statement of an algorithm in mathematical symbols and the statement of an algorithm in computer language that for all intents and purposes the algorithm itself has been patented. 100 years ago, nobody would have seriously considered a patent for an algorithm's "implementation with pencil and paper", but the USPTO now regularly accepts patents for algorithms "implemented with an electronic digital device".
IAW, if you invented a better algorithm for some common mathematical process 100 years ago, clerks all over the world would use it immediately using the tools at hand, and some might improve it. But today you can effectively prevent that because clerks all use computers, and implementation with a computer is patentable.
Much of the slashdot-type thoughts on software patents come from the way software is viewed. Is software a concrete "thing" like hardware, or is it the virtual manipulation of symbols like math? The public, seeing only the final product, views software the first way, but most programmers see it the second way. The source code is the application; compiling it is only a detail.
We should try to get an interview setup with this guy to see if he can actually defend his position. We always tear down everyone who patents ridiculous things like this, but this guy would probably be willing to open himself up to some (intelligent, not degrading) questions. I'm not asserting that he won't come off looking like an evil anti-open source, copyright-mongering, greedy person, but at least we'll be able to come to that conclusion through reasonable means rather than making assumptions.
Maybe (big maybe) he patented his idea so that it could be used and distributed freely to prevent a company from patenting it and charging licensing fees. Who knows? Certainly, none of us do.
It's worth a shot, in my humble opinion.
The slashdot community thinks that an invention is unworthy of a patent -- all without seeing a single line of any specification or claim. With all due respect, none of us, myself included, can comment on the validity or propriety of an application for a patent until we have seen what in fact is claimed.
Nonetheless, we have already seen posted here vitreolic remarks suggesting USPTO incompetence, unreasonable conduct by the applicant and general remarks about unnamed "abuses" of a Patent system.
I have obtained and enforced patents for clients, and invalidated patents of others. I know what it takes to meet the tremendous burden of showing a patent is invalid, or even the burden for an examiner to make a prima facie case to refuse a claim. Several remarks made here do not come close, and, to be frank, would appear ignorant and empty to any educated student of the patent law.
Several of use who are fighting the fight for real patent reform have had our battles made more difficult, not less, by the conduct of those who randomly assault the USPTO without cause. Such remarks ultimately (and properly) get ignored, and the Office begins to turn a deaf ear to all arguments made for change -- even when they are sound.
The bottom line is this: some patents are valid, and others are not. The determination is made on the merits -- there either is or is not an adequate specification; and there either is or is not invalidating prior art. The very reasonable news story asked for meat, but regrettably all we have seen thus far are whinings, rejecting legitimate arguments of validity as mere "legalese."
For those of you who have undertaken to educate yourselves about the subject of patents and comment on this subject, I regard your comments and cricicisms highly -- you have taught us a great deal, and even where we have disagreed, I have been both enlightened and educated by the discourse. I hope that in time your colleagues will follow your example.
Actually I think that this is exactly the sort of thing that should be patentable - he's not patenting the IDCT per-se - he's patenting a particular implementation of it.
This is exactly like patenting a better machine for (say) canning food rather than patenting the concept of canning food, or a new way to sell canned food. This is what the patent system was set up to do.
Having said all that I personally believe that it's become way too easy to patent little stuff, I firmly believe that patents as they were a hundred years ago were a worthwhile concept - I hold a number of patents on my work over the years - none of them come close to the patents that were granted to Edison - back then people patented 'big ideas' not all the little things that we invent day to day to get our work done.
Over the years my various employers have encourage me to patent lots of stuff I've invented - but frankly I'm only really proud of one of those inventions - and much prouder of other stuff I've done (whole chips, big software systems etc) that in themselves are not patentable.