Its always bothered me to read about inventors who discovered beautiful and amazing things, only to die penniless while powerful interests reaped all of the financial benefits. Hopefully the people who discovered these codes have been richly rewarded for their work.
1. Is it non-obvious enough?
2. Would the patent realistically benefit the inventor?
3. Would the patent benefit the society at large?
1 - Physical devices often require lots of engineering work, prototyping, testing and refinement before they really work. Patents aim to protect your investment of money and time into all that stuff. This is not applicable to pure ideas. Once you thought of something like fountain codes, you instantly know they will work and you even know how. There is no investment to protect.
2 - Just because something is useful doesn't mean people will use it, even for free, and the act of patenting a generic algorithm will certainly drive most potential users away. Not because licensing costs money, but because it's a hassle and a liability.
3 - This was covered in many other posts here. I'll add one thing. The fact that it's just an idea (and a generic one that that) means other bright people who need that idea are likely to come up with it on their own. In that case a patent would be clearly counter-productive for the society. Why should the first 'inventor' of the algorithm has all the rights to it, while the second would have none?
I put creation in quotes, because of an issue that nicely demonstrates how fundamentally different ideas are from physical property: consider the many scientific/mathematic discoveries that were made in parallel around the world, with no communication between the parties, who gains the right to "own" these ideas, and why should they? Did not somebody else take exactly the same amount of effort and process to create the exact same idea? This even applies to very complex systems that are far from obvious, quite novel, and form the foundations of our modern world.
People need to get past the idea that somebody has a brilliant idea one day out of the blue, and the world is changed forever because of it. Every idea anyone has ever had owes almost everything to what proceeded it, and the environment it arose in, co-discovery/invention is very solid proof of that.
"If I have seen a little further it is by standing on the shoulders of Giants."
When you take the time to realize the very thing that propels us forward is the ability to build on existing ideas, you realize how patents and IP law in general are impeding, not encouraging.
(there are several more, but i do not have the time just now to find them)
I'd suggest that the usefulness of algorithms like fountain codes (and other innovative algorithms like RSA and many compression techniques) leads to the opposite conclusion: such algorithms prove so broadly useful that patents on them have even more of a negative effect than usual.
With 3), the inventor never gets a chance to commercialize his invention: as soon as he publishes the algorithm, he will be destroyed (or assimialted) by large players. With 2), we never know how many cool, useful algorithms are rotting away in commercial products. As far as the society is concerned, the algorithm in question does not exist. With 1), the inventor benefits, AND also the society (in the long-term).
IMO, the patent system should be reformed so that having a large portfolio of unused patents becomes a liability. For example, the patent holder would have to periodically (e.g., every 2 years) apply [with fee, of course] for patent renewal. For this, the holder must be able to document that he is actively exploiting the patent (1). There should also probably be a minimum limit for the required income from patent exploitation. Failing to do so, the patent would automatically expire. The patent office should publish an on-line database of expired patents.
There should also be restrictions on what can be patented: for example, work funded by government funds must not be patentable: the inventors' (in this case, mostly researchers at universities) day job is by definition designing things that will benefit society, are paid for that by the society, and therefore have no further rights to patent protection. (This is, IMO, fair since research is [should be] free, so the society has no firm guarantees that the researchers will produce something valuable, or anything at all.)
(1) By exploitation I mean either making a device covered by the patent, or licensing it to somebody who making such device.
Aside from that, I'd point out that in the rare case when an algorithm does get published as a patent and licensed, that makes it entirely unusable in Free and Open Source Software as well as in open standards, for a period of ~20 years. At least when the algorithm remains unpublished, someone can re-discover it (or something more useful that would build on it); patents force willful ignorance of an entire class of algorithms, as well as anything in the general vicinity of those algorithms.
So you would like to have had eg. any useful non-obvious algorithm or data structure which at some point in history was novel been patented ? Yikes.