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?
Two reasons:
1) Slashdot posters have no problem commenting on something they know nothing about.
2) Slashdot moderators have no problems giving points to comments on something they know nothing about.
The result is that uninformed posts go straight to the top if they sound halfway reasonable. It's like peer review by a bunch of monkeys. Sure it's been reviewed, but that doesn't really give the content any more validity.
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.
This looks like a case of yas/.spa.
Yes, the trick of using shift-and-add to do multiplies is well known. Yes, using it in the context of a FFT (or DCT, as in this case) is obvious. But that's not what they've done here.
It looks to me like they've invented (or discovered) a new transform which is similar to the DCT, and shares many properties with the DCT, but is not simply an approximate DCT. In other words, you'd use this for designing a new video coder in which high processing speed is more important than compression ratio (they take about a 1dB hit in compression, my brain is too fuzzy convert this into percent right now).
The transform has some other interesting properties, such as the fact that the transform and its inverse are in fact exact even when you use limited-precision arithmetic, unlike DCT. This would seem to imply that repeatedly compressing and decompressing aren't going to lead to any quality degradation. Also, it might make for a more efficient lossless coder. Neither of these is a very big deal, but still interesting.
So it looks like what we have is something new, interesting, and primarily useful for video compression in hardware. I don't see a compelling reason why it shouldn't be patentable, and it certainly seems well within the scope of what the current patent system allows. Believe me, I've seen far worse in issued patents.
Lest you think I'm defending the patent system, I'm not. It's badly in need of reform. A very large fraction of issued software patents are simply bad patents. I actually believe that no software patents at all would be better than the current system, although I'm idealistic enough to hope that fixing the patent system to prevent abuses would be even better. I'm just saying that if you're going to pick on an invention, choose a better scapegoat than this one.
Finally, a shameless plug: since the discussion of patents and intellectual property on Slashdot seems to be as misinformed as it is lively, one of the explicit goals for my new site, Advogato is to host intelligent discussion of these issues. From the discussion so far, I have reason to be encouraged.
LILO boot: linux init=/usr/bin/emacs
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.
Was there ever a forum anywhere that had less of a clue regarding patents than Slashdot? I doubt it. I wish Rob Malda and friends would implement some reasonable standard of journalism to weed out these speculative and clue-less stories.
Let's look at this story from a factual basis (I know it's a bit much to expect from slashdot, but we can try):
Apparently, he has applied for a patent for this approximation.
Apparently is the key word here. The author is engaging in rank speculation and rumor-mongering.
Unfortunately there is no actual text to the application to review, only a speculative statement and a journal publication. What can we say about this from known law?
The first is:
1. YOU CANNOT PATENT A MATHEMATICAL ALGORITHM.
Yes Virginia, despite the wild statements by many contributors to this forum, US Patent law contains a specific provision that includes a ban on patents of mathematical laws and algorithms. There are in fact no valid patents of mathematical algorithms in existance.
This rules out the speculation of the article statement.
2. IT IS POSSIBLE TO OBTAIN A PATENT ON PRACTICAL APPLICATIONS OF MATHEMATICAL ALGORITHMS
Such cases are well know, such as RSA for encryption applications, and LZW for image compression. THESE ARE NOT PATENTS OF ALGORITHMS, MERELY AN APPLICIATION OF THE ALGORITHM you are perfectly free to use RSA or LZW algorithms in non-patented applications for the algorithms themselves are not the subject of the patent.
If in fact the author is filing an application as speculated by the article author on the approximation, it will be quickly rejected by the USPTO. HOWEVER, if the author is filing on an application of the algorithm to some common problem, say deconvolution of Fourier Transfor Infrared Spectra, then I think there is a good chance that the application will become a patent.
Time will of course show what is the actual case here.
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.
Very useful. The question is, can we viably extend mathematics should this "thing" be patented. This is the same thing we have to evaluate in Artificial Intelligence -- does someone get to benefit from having patents in AI, when in fact, giving these patents out practically undermines any further research in that particular direction, overall inhibiting the growth of that field.
It's not my place to say, but I'm quite sure that this is a very, very bad thing. Look at LZW -- no one really benefited from that patent, but it sure as hell made life very difficult for many, many people. It's fine to patent something if it's a specific end-process, but if it is a *foundation* for furthering a field, then patenting it cause undue harm to the exploration of that field.
So, my opinion is, if this thing is an "end process", as in unable to extend the field further, then it being patented should be of no harm. However, my understanding of this leads me to believe that patenting this thing will hinder the furthering of mathematics.
We cannot afford to put up barriers in mathematics, there is too much to explore, and we know too little, to put up artificial anthropocentric monetary induced barriers.
Y'all have been talking about algorithms, math,etc. But a quick look at the guys page clearly shows the focus on design for VLSI implementation. He doesn't need to patent math ...he's patenting the circuit.
Yes, he deserves a patent
Well, no offense, but if the patents coming out lately are typical, you and your colleagues are doing a terrible job reforming the patent system.
Are they? I have read every patent-related article in Slashdot in recent months and have yet to see a single patent subjected to anything close to an invalidating analysis.
While you may enjoy the lawyer-bashing, and the suggestion that we somehow all "dance to corporate marketing jingles," nothing is proved by that. While you are wrong about me, personally, that is wholly beside the point. Even if I were in someone's pocket, how would that make my arguments more or less valid? Why would the ignorance and naivete of the attacks made on the patent system by those who have not studied the law be any more meaningful or correct?
Come off it. No one can reasonably suggest that a person is qualified or unqualified to discuss patent policy merely because he or she is a lawyer. That's just another straw man in defense of the naive attacks. I am suggesting that one who *DOES* attack the patent system should first undertake to learn something about how it works.
Apparently that is too controversial a point to raise in this forum.
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.
What I'm really trying to say here is that it's easy to patent small ideas - but often hard to tell when your patent is being violated. Conversly it's hard to patent big ideas (because it's hard to think up something that's truely revolutionary) - but easy to track down violators. So maybe there is some little justice in the patent world :-)
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.