Codifica di sorgente

Note

È necessario rappresentare i risultati di un esperimento aleatorio con una stringa di bit, per farlo bisogna utilizzare delle codifiche.

Codeword prefix-free

Per avere un codice disambiguo, ogni parola di codice non deve essere prefisso di altre parole di codice.

Disuguaglianza di Kraft-McMillan

Note

È possibile trovare un codice prefix-free composto da codewords con lunghezze se e solo se:

Da cui ricaviamo il seguente teorema: data una variabile aleatoria discreta con risultati possibili, per ogni codice prefix-free che assegna una codeword di al risultato si ha:

In generale si ha che è quasi ottima.