Odrębnym problemem jest dekodowanie. Kod o dobrych parametrach teoretycznych nie musi być użyteczny, jeśli brak dla niego szybkiego algorytmu dekodowania albo jeśli algorytm wymaga zbyt dużej pamięci i energii. Z tego powodu nowoczesna teoria kodowania bada nie tylko istnienie kodów o dobrych parametrach, lecz także ich konstruktywność, strukturę algebraiczną lub grafową oraz podatność na dekodowanie w warunkach rzeczywistych.
Kodowanie źródłowe Kodowanie źródłowe opisuje metody reprezentowania wiadomości przy możliwie małej liczbie symboli lub bitów. W wersji bezstratnej pozwala odtworzyć dane dokładnie, natomiast w kompresji stratnej dopuszcza kontrolowaną utratę informacji, jeśli jest ona akceptowalna dla odbiorcy. Granicą efektywnej kompresji bezstratnej jest entropia źródła: im bardziej przewidywalne są komunikaty, tym więcej nadmiarowości można usunąć.
Klasyczne przykłady metod bezstratnych obejmują kody prefiksowe, kodowanie Huffmana i kodowanie arytmetyczne. Historycznie szczególne znaczenie miało kodowanie Huffmana, które dało optymalny kod prefiksowy dla znanych prawdopodobieństw symboli i stało się punktem odniesienia dla bezstratnej kompresji danych.