You could write a complete from-scratch decoder, and be sued if you distribute it.
This is the case with MPEG-2 formats used in DVD Video, and the reason that the VLC Media Player exists as a French student research project distributed as source code instead of a normal library.
IANAL, but as far as my understanding goes, it means that the algorithm is patented and therefore requires you to pay a license fee if you want to redistribute the code in a country where software patents are practically enforceable (like the USA).
In other parts of the world (like large parts of Europe, for example) software patents are practically unenforceable and you can probably distribute your code as you see fit. Code is still copyrightable, so you can't just redistribute someone else's library, but your own code does not violate their copyright.
Some greedy American companies will probably still sue you if you do, hoping to enforce their patents regardless or at least scare you into paying them, but at legally you _should_ be in the clear.
When it comes to dedicated hardware for an algorithm, though, like hardware accelerated video codecs, you'll likely run into patent trouble in most of the world if you choose to build your own hardware for a patented system.
