There is no connection between these two things. Codecs are not software. They are signal processing techniques. Whilst they are most commonly implemented as software on programmable signal processors, they can also be implemented in pure hardware, or even as a written description for non-real time implementation on an abacus.

You cannot patent a codec, as such. You patent some techniques which the codec embodies. These generally fall into one of two categories. They may be pure mathematical techniques for speeding up the computations involved (most codecs require a lot of computation). These generally exist only in the US, since such pure maths is definitely not patentable in most other countries. Pure maths is not supposed to be patentable in the US, but it seems carefully wording it in terms of "algorithms" will usually get a patent through. The second group are signal processing patents, covering devices with particular behaviour. In general terms, exactly how that behaviour is achieved is not important for the patent. In constructing one of these patent claims you try hard to make sure the codec specification cannot be implemented in any other way than to use your patented techniques. If you are any good, you succeed. Generally, the patents do not mention the word software. They can be, and have been, granted in most major markets. They generally apply to any software or hardware implementation of the techniques. If, say, you have a purely software implementation of G.729 it might not be considered to be infringing as it stands. However, you would have a hard time convincing a judge and jury that they were not seeing a device performing patented functions once the sooftware is loaded into a computer and run.