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.
|
|
|
|
|
---|---|---|---|---|
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:
classificar em:
- Comprimento: fixo ou variável
- Classe: singular (não injetor) ou não–singular (injetor)
- Se é unicamente decodificável ou não
- 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
A→0, B→0, C→0, D→0
- Comprimento: todos têm 1 bit ⇒ fixo.
- Singularidade: todos mapeiam para “0”, há colisão ⇒ singular.
- Decodificabilidade: se eu recebo “0” não sei se foi A, B, C ou D ⇒ não unicamente decodificável.
- Instantaneidade: o mesmo “0” é prefixo de si mesmo ⇒ não instantâneo.
Passo 3
Analisando
:
A→0, B→010, C→01, D→10
A→0, B→010, C→01, D→10
- Comprimento: tamanhos
⇒ variável. - Singularidade:
são todos distintos ⇒ não-singular. - Instantâneo? “0” é prefixo de “01” e de “010” ⇒ não instantâneo.
- 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
A→10, B→00, C→11, D→110
- Comprimento:
⇒ variável. - Singularidade:
são distintos ⇒ não-singular. - Instantâneo? “11” é prefixo de “110” ⇒ não instantâneo.
- 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
A→0, B→10, C→110, D→111
- Comprimento:
⇒ variável. - Singularidade:
são distintos ⇒ não-singular. - 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.
- 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.
•
•
•