TC – DEI, 2005/2006
Representação de Informação
-- Texto --
Paulo Marques
[email protected]
http://www.dei.uc.pt/~pmarques
Tecnologia dos Computadores 2005/2006
Representação de Informação
Até agora vimos...
 Como é que se representam números inteiros
 Como é que se representam fracções
Vamos ver...





Como é que se representa texto
Como é que se representam imagens
Como é que se representa som
Técnicas simples de correcção de erros
Dispositivos de armazenamento de informação
TC – DEI, 2005/2006
Representação de Caracteres
ASCII = American Standard Code for
Information Interchange
Tradicionalmente, utilizava-se 7 bits para
representar os diversos caracteres
 7 bits  128 combinações diferentes possíveis
Exemplo:
‘A’ = (1000001)2 = (65)10
Mais tarde, os 7 bits foram extendidos a 8,
permitindo representar 256 caracteres
diferentes
TC – DEI, 2005/2006
Tabela de ASCII (7 bits)
TC – DEI, 2005/2006
Texto
A representação de texto é simplesmente uma
sequência de caracteres
“
O
L
A
79
76
65
1001111
1001100
1000001
”
Código ASCII
TC – DEI, 2005/2006
UNICODE
Na prática, 256 caracteres diferentes não
chegam para todas as línguas
Formou-se um consórcio internacional para
definir um standard que para codificação de
caracteres aplicável a todas as línguas
 UNICODE (http://www.unicode.org)
Cada caracter é representada por 16 bits
 16 bits  216 combinações diferentes (65536!)
 Na verdade, o que são representados não são
exactamente os caracteres...
 Os primeiros 256 caracteres têm o mesmo valor do
que em ASCII
TC – DEI, 2005/2006
UNICODE – Um Exemplo
TC – DEI, 2005/2006
Compressão de Texto
Apesar do espaço de armazenamento estar
continuamente a aumentar, é desejável por
vezes comprimir os dados
 Transmissão pela rede
 Armazenamento de longa duração
 Em geral... Maior eficiência e aproveitamento de
recursos
Três métodos comuns de comprimir texto
 Keyword encoding
 Run-length encoding
 Huffman codes
TC – DEI, 2005/2006
Keyword Encoding
Substituir palavras muito comuns por
caracteres especiais ou sequências especiais
de caracteres
As palavras são substituídas de acordo com
uma tabela de frequência de ocorrência
Chave
Significado
%
carro
$
acidente
&
senhor
#
do
TC – DEI, 2005/2006
Aplicando a codificação...
“No acidente estiveram envolvidos três carros. O carro
do senhor António ficou destruído. O carro do senhor
José não sofreu grandes danos no acidente. O carro do
senhor Carlos... bom, depois do acidente, nem se pode
chamar aquilo um carro....”
 241 bytes
“No $ estiveram envolvidos três carros. O % # &
António ficou destruído. O % # & José não sofreu
grandes danos no $. O % # & Carlos... bom, depois #
$, nem se pode chamar aquilo um %....”
 185 bytes (76%)
TC – DEI, 2005/2006
Run-length Encoding (RLE)
Tipicamente utilizando quando o mesmo
padrão/letra surge muitas seguido numa
sequência de dados
 Não é comum em texto, mas em muitos outros tipos
de dados (imagem, vídeo)
 Este tipo de algoritmo é a origem dos métodos de
compressão utilizados em muitos utilitários comuns
Neste tipo de compressão, uma sequência de
caracteres que se repetem é substituída por
um marcador especial, pelo caracter em
questão, seguido do número de vezes que ele
aparece.
TC – DEI, 2005/2006
RLE – Exemplos
AAAAAAAAAA
*A10

AABBBBBBBBAMMKKKKKKKKKM
AA*B8AMM*K9M

Nestes dois exemplos o texto é ASCII, no
entanto pode-se fazer em binário, o princípio é
o mesmo
 De facto, ASCII é binário! 
TC – DEI, 2005/2006
Huffman Codes
A letra mais frequente no alfabeto português é
o ‘e’
Ao comprimir um texto, porque é que o ‘e’ tem
de ocupar o mesmo número de bits que... o ‘x’,
por exemplo?
Os códigos de Huffman representam os
diferentes caracteres utilizando um número
diferentes de bits
 Os caracteres mais comuns utilizam menos bits!
TC – DEI, 2005/2006
Huffman Codes - Exemplo
“VOU A CASA”
111100110000100101101101001
Chave
Significado
00

ESPAÇO
01

A
100

O
110

U
111

V
1010

S
1011

C
TC – DEI, 2005/2006
Huffman Codes - Exemplo
Analisemos o exemplo...
 “VOU A CASA”  10 bytes de ASCII
 11110011 00001001 01101101 001  < 4 bytes
 Compressão de 60%!
Existem técnicas especiais que permitem
construir as tabelas de codificação a utilizar
 Nós não as estudaremos aqui...
Uma característica fundamental é que
nenhuma dos códigos utilizados é prefixo
de nenhum outro código!
TC – DEI, 2005/2006
Representação de Informação
-- Imagens --
Percepção da cor
O nosso olho tem dois tipos de sensores:
CONES e BASTONETES
Os CONES percepcionam a cor, sendo
sensíveis a três frequências: “vermelho”,
“verde” e “azul”
TC – DEI, 2005/2006
Percepção da cor
A percepção da cor é possível porque as várias cores
podem ser vistas como uma mistura de outras cores,
nomeadamente: VERDE, VERMELHO e AZUL
Existem outros sistemas de coloração...
 RGB = Red Green Blue
 CYMK = Cyan Yellow Magenta Black
 HSL = Hue Saturation Luminosity
RGB
CYMK
TC – DEI, 2005/2006
Representação da cor
Tipicamente os sistemas informáticos utilizam o
sistema RGB  Red, Green, Blue
A cada cor é atribuído um número
 8 bits por cor  cada cor de 0 a 255
 Total = 24 bits de cor (TRUE COLOR)
Exemplos:
(255,0,0)
(255,255,255)
(0,255,255)
(0,255,0)
(0,0,0)
(255,0,255)
(0,0,255)
(255,255,0)
(150,150,150)
TC – DEI, 2005/2006
Imagens
As imagens são formadas por um conjunto
muito grande de pontos  pixels
A cada pixel corresponde uma cor
i.e. três números RGB
TC – DEI, 2005/2006
Armazenamento de imagens
Existem imensos formatos de armazenamento
de imagens
 GIF, JPEG, BMP, PNG, TIFF, ...
Na maior parte dos casos as imagens são
comprimidas antes de serem armazenadas...
 ... 1600x1200x24bits cor = 5.5Mbytes!
Dois tipos de compressão
 Com perda de qualidade (e.g JPEG)
 Sem perca de qualidade (e.g. Compressed-TIFF)
TC – DEI, 2005/2006
Desenhos/Imagens Vectoriais
Em vez de se armazenar os pixels, guarda-se
uma descrição do gráfico/imagem
Muitos programas de desenho/edição
electrónica utilizam este método (e.g.
CorelDraw, fontes TTF, AutoCAD)
Os desenhos podem ser escalados de forma
transparente
= poly[(0,0) -> (50,30) -> (40,80) -> (0,0)]
TC – DEI, 2005/2006
Video
Em video, o princípio é o mesmo
 Guarda-se um conjunto de imagens sucessivas
(e.g. 25 imagens por segundo)
Devido ao imenso espaço que ocupam, tem de se
compactar as imagens de uma forma eficiente
 CODEC = COmpressor/DECompressor
 E.g. DivX! 
Dois métodos de compressão...
 Compressão temporal  Não considerar as diferenças entre
duas imagens sucessivas
 Compressão espacial  Eliminar a redundância dentro de uma
imagem
TC – DEI, 2005/2006
Som
Os sons que ouvimos correspondem às
vibrações que o ar transmite ao tímpano
1.2
f ( t)
 1.2
0
t
12.566
TC – DEI, 2005/2006
Som - Digitalização
1.2
Nos computadores o
som é digitalizado
fazendo-o corresponder
a números discretos.
Quando se digitaliza som
existe uma certa taxa de
amostragem
f ( t)
 1.2
0
t
12.566
t
TC – DEI, 2005/2006
12.566
1.2
f ( t)
 1.2
0
Armazenamento de Som
Duas formas de armazenamento
 Sem perdas, tipicamente não comprimida (e.g. wav)
 Com perdas, comprimida (e.g. mp3)
Nas formas comprimidas é tido em conta a
forma como nós, humanos, ouvimos o som!
 O formato mp3 é codificado de acordo com o que
nós conseguimos ouvir em cada momento. As
partes que não conseguimos ouvir são eliminadas.
 Em mp3 a compressão é feita por códigos de
Huffman
TC – DEI, 2005/2006
Resposta do Ouvido Humano...
TC – DEI, 2005/2006
25
29
45
56
6
8
http://www.toledo-bend.com/colorblind/Ishihara.html
TC – DEI, 2005/2006
Técnicas Básicas de
Correcção de Erros
Correcção de Erros
Quando se armazena ou transmite informação,
podem existir erros
E.g. 01101010  01100010
É necessário garantir que, com uma elevada
probabilidade, os erros conseguem ser
detectados e se possível corrigidos
TC – DEI, 2005/2006
Bits de Paridade
Dada uma sequência de bits, adiciona-se um
bit extra que torna o número de bits resultante
de uma certa paridade
 Paridade PAR: O conjunto resultante tem de ter um
número par de bits
 Paridade ÍMPAR: O conjunto resultante tem de ter
um número ímpar de bits
Número original
Bit de paridade
1 1 0 0 0 0 1
1
PARIDADE PAR
1 1 0 0 0 0 1
0
PARIDADE ÍMPAR
TC – DEI, 2005/2006
Checksums
É uma forma evoluída dos bits de paridade
 Dado um conjunto de dados junta-se um número
que é obtido fazendo uma certa operação sobre
esses dados
 Um exemplo simples: somar e calcular o resto da
divisão pelo número máximo que se quer
representar
 Outro exemplo simples: ... A prova dos nove! 
12 32 34 12 43 54 12 54 65 76 87 12 45
38
12+32+34+12+43+54+12+54+65+76+87+12+45=538
538 MOD 100 = 38
TC – DEI, 2005/2006
Checksums
Alguns tipos de checksums muito conhecidos
 CRC = Cyclic Redundancy Check
 MD5 = Message Digest 5
Nota 
 O algarismo que está junto ao número do bilhete de
identidade é um checksum!
TC – DEI, 2005/2006
Códigos de Correcção de Erros
Existem códigos que permitem não só detectar
erros, como corrigi-los!
Distância de Hamming  Número de bits
diferentes entre duas cadeias
0 0 1 1 1 1
Distância de
Hamming de 3
0 1 0 0 1 1
TC – DEI, 2005/2006
Um código de correcção simples...
Neste código, a distância
de Hamming é sempre,
pelo menos, 3
Se houver um bit errado,
consigo detectá-lo e corrigi-lo
Se houver dois bits errados,
consigo detectar que houve
um erro, mas ao corrigir, o
resultado é incorrecto
Se houver três bits errados,
não consigo detectá-lo nem
corrigi-lo
TC – DEI, 2005/2006
Exemplos (envia D – 011100)
Recebe...
011000  Há apenas um erro, é
detectado e corrigido
correctamente. O que está mais
próximo é o D (distância 1).
010000  Detectado, mas ao
corrigir, é corrigido para o valor
errado (corrige para A!)
000000  Três bits errados! Não
detectado, nem corrigido, assumese que é o A!
O código de Hamming é pensado para situações de erros
não burst. Exemplos de utilização: memórias dos computadores
(memória ECC), modems, satélites planetários!
TC – DEI, 2005/2006
Armazenamento de Informação
Disco Rígido
TC – DEI, 2005/2006
CD-ROM
TC – DEI, 2005/2006
Tape
TC – DEI, 2005/2006
Flash Memory Pen
Non-volatile Flash
Memory
TC – DEI, 2005/2006
Para Saber Mais...
Computer Science, An Overview
 Capítulo 1 (1.3, 1.4, 1.8, 1.9)
Computer Science Iluminated
 Capítulo 3 (3.1, 3.3, 3.4, 3.5, 3.6)
 Embora este não seja o livro principal, tem a matéria
um pouco melhor explicada
http://computer.howstuffworks.com/
TC – DEI, 2005/2006
TC – DEI, 2005/2006