Classifique os códigos abaixo em relação ao comprimento (fixo ou variável) e classe (singular/não-singular, unicamente decodificável, instantâneo/nãoinstantâneo). Justifique cada resposta.
X C1 C2 C3 C4
A 0 0 10 0
B 0 010 00 10
C 0 01 11 110
D 0 10 110 111

Passo 1

Beleza, vamos lá. O enunciado pede para cada código

classificar em:
  1. Comprimento: fixo ou variável
  2. Classe: singular (não injetor) ou não–singular (injetor)
  3. Se é unicamente decodificável ou não
  4. Se é instantâneo (propriedade prefixa) ou não
O que precisamos saber:
  • Um código tem comprimento fixo se todos os seus códigos de símbolo têm o mesmo tamanho; senão é variável.
  • Singular = dois símbolos podem ter o mesmo código (falha de injeção). Não-singular = todos distintos.
  • Instantâneo = nenhum código de símbolo é prefixo de outro (propriedade prefixa).
  • Unicamente decodificável = qualquer sequência de bits resultante tem só uma maneira de ser dividida em símbolos; podemos usar o alg. de Sardinas–Patterson ou exemplos diretos.

Passo 2

Analisando :
A→0, B→0, C→0, D→0
  1. Comprimento: todos têm 1 bit ⇒ fixo.
  2. Singularidade: todos mapeiam para “0”, há colisão ⇒ singular.
  3. Decodificabilidade: se eu recebo “0” não sei se foi A, B, C ou D ⇒ não unicamente decodificável.
  4. Instantaneidade: o mesmo “0” é prefixo de si mesmo ⇒ não instantâneo.

Passo 3

Analisando :
A→0, B→010, C→01, D→10
  1. Comprimento: tamanhos variável.
  2. Singularidade: são todos distintos ⇒ não-singular.
  3. Instantâneo? “0” é prefixo de “01” e de “010” ⇒ não instantâneo.
  4. Decodificabilidade?
    Aplicando Sardinas–Patterson rápido:
    R₁ = {sufixos quando um código é prefixo de outro} = {01–0 ⇒ “1”, 010–0 ⇒ “10”, 010–01 ⇒ “0”} = {“1”,“10”,“0”}.
    Logo já aparece “10” que é código de D ⇒ código não unicamente decodificável.

Passo 4

Analisando :
A→10, B→00, C→11, D→110
  1. Comprimento: variável.
  2. Singularidade: são distintos ⇒ não-singular.
  3. Instantâneo? “11” é prefixo de “110” ⇒ não instantâneo.
  4. Decodificabilidade?
    R₁ = {110–11 ⇒ “0”}.
    R₂ com “0” gera só “0” de novo, não surge cadeia vazia nem código ⇒ unicamente decodificável.

Passo 5

Analisando :
A→0, B→10, C→110, D→111
  1. Comprimento: variável.
  2. Singularidade: são distintos ⇒ não-singular.
  3. Instantâneo? ninguém é prefixo de outro (todos começam “0” só em A, e os que começam “1” têm vários bits antes de fechar) ⇒ instantâneo.
  4. Instantâneo ⇒ automaticamente unicamente decodificável.

Resposta

: comprimento fixo; singular; não unicamente decodificável; não instantâneo.
: comprimento variável; não-singular; não unicamente decodificável; não instantâneo.
: comprimento variável; não-singular; unicamente decodificável; não instantâneo.
: comprimento variável; não-singular; unicamente decodificável; instantâneo.

Exercícios relacionados