Processamento Digital de Sinais, Engenharia de Software, Teoria da Informação e Codificação

Processamento Digital de Sinais e Engenharia de Software

Parte 1 - Processamento Digital de Sinais

1. Introdução ao Processamento Digital de Sinais

1.1Breve Histórico. Por que utilizar processamento digital de sinais?

1.2Alguns Exemplos

- Modems operando em linhas telefônicas - filtragem até 1960 e depois de 1960. Filtragem digital adaptativa

- Filtragem do Sinal de ECG e outras aplicações biomédicas

- Compensação de Canais de Comunicação sem fio. Como funciona na Telefonia Celular, entre assinantes e ERBs

- Tratamento de Imagens e de Sinais emitidos por Sondas Espaciais - Filtragem Autodidata ou Cega

- Aplicações para levantamentos geológicos

1.3 Características desejáveis na abordagem "Digital" de Sistemas

1.4 Um Exemplo de Sistema Analógico e o Discreto e Digital equivalente: um Circuito RC

Prof. Antonio Newtton Licciardi Jr. – Material registrado na Biblioteca Nacional 1


- Sistema Analógico

- Discretização das Equações do Sistema

- Duas abordagens de Implementação: utilizando somente componentes de hardware (somadores, subtratores, multiplicadores, divisores e elementos de atraso) ou hardware e software

2. Caracterização de Sinais

Em aplicações em PDS uma sequência discreta no tempo é gerada pela amostragem periódica de um sinal contínuo no tempo , em intervalos de tempo uniformes:

(2.1)

Frequência de amostragem , respeitando Nyquist , frequência componente limite do sinal .



2.1Tipos de Sequência

2.1.1 Quanto a duração

Sequência Finita

em que e (2.2)

, duração da sequência

Sequência Infinita

em que e, ou (2.3)

Sequência limitada a direita

em que e (2.4)

Sequência limitada a esquerda

em que e (2.5)

2.1.2 Quanto a Simetria

Sequência Par

, (2.6)

sendo que denota o conjugado de .

Ex.:

Sequência Impar

(2.7)

Ex.:

Exercício



2.1.3 Quanto a Peridiocidade

Uma sequência é dita periódica quando

, (2.8)

em N é o período (inteiro positivo) e K é qualquer inteiro.

Exercício

Se periódica, qual o período? Se periódica, qual o período?

Exercício/Laboratório

- Apresentação da Ferramenta/Software de Simulação a ser usado no Curso de PDS e suas funcionalidades- Geração de gráficos contínuos e amostrados a partir de sequências estabelecidas

2.1.4 Outros Tipos de Classificação

Uma sequência é dita limitada quando

(2.9)

Uma sequência é dita absolutamente somável quando

(2.10)



Uma sequência é dita quadraticamente somável quando

(2.11)

A energia de uma sequência discreta é definida como

(2.12)

Exercício

para (0, para os demais casos)


- Verificação da construção de arquivos de Som no padrão .WAV em computadores. - Ferramentas para manipulação de arquivos de Som- Revisão do teorema de Nyquist e aplicação em audio- Verificação dos efeitos de alteração da frequência de amostragem e deslocamento

em frequência das amostras- Sistema de Superposição de Amostras- Construção de um Sistema para transformar uma amostra de Som Estéreo em

Amostra de Som Mono.

2.1.5 Normalização da Potência de Sinais

Considere duas sequências e , de comprimento finito M e quadraticamente somáveis no intervalo em que estão definidas.

Desta forma pode-se definir como Potência Média, das amostras ou energia Média por amostra:

(2.13)

e

(2.14)

Definem-se como as sequências de potência normalizadas das sequências e respectivamente,



(2.15) e

(2.16) Observe que as duas novas sequências assim definidas possuem Energia,

(2.17)

e

, (2.18)

e potência média por amostra,

(2.19)

e

(2.20)

Desta forma, as novas sequ6encias assim definidas possuem potência média por amostra unitária.

Uma maneira de criar uma sequência de mesma potência média que a sequência é então definir a mesma como,

(2.21)

Este ultimo processo é utilizado para a construção de sistemas de equalização ou normalização de potência e ainda sistemas de controle automático de ganho (GAC) digitais, definindo um tamanho de bloco representativo dos sinais (M).



2.2Algumas Sequências Básicas

Impulso Unitário

(2.22)

Degrau Unitário

(2.23)

Exercício

Exercício

Esboçar o gráfico da sequência Representar como Soma de Impulsos - vide próximo conceito!

Qual a Energia da Sequência?Qual o comprimento, se limitada?

Ela é absolutamente e quadraticamente somável?

Representação de uma Sequência Arbitrária



Exercício

Considerando as sequências

e

Representar como Soma de Impulsos Qual a Energia das Sequências?

Qual o comprimento, se limitadas?Qual a Potência Média/

Encontre as sequências normalizadas (em potência média) respectivamente.Calcule a Energia e Potência Média das sequências normalizadas.


- Construção e testes de um sistema Equalizador de Potência de Som, baseado em arquivos .WAV

- Construção e testes de um Sistema de GAC- Verificação do funcionamento do sistema de GAC, quando o sinal a ser recuperado

está adicionado de ruído branco gaussino ou ruído rosa, de potência constante.

3. Sistemas de Tempo Discreto

Média Móvel

(3.1)



Exercício

Dada a sequência

Esboçar o gráfico da média móvel

Representar como Soma de ImpulsosQual a Energia da Sequência?

Qual o comprimento, se limitada?Ela é absolutamente e quadraticamente somável?

Desenhar o Gráfico e Verificar o efeito Passa baixa provocado pelo Filtro


Projetar com o apoio do Software de Simulação um sistema de Dolby Digital. Testar com amostras de som digitalizadas em arquivos .WAV e ruído rosa na faixa [0, 22 K] hz. Verificar a eficiência quando se aumenta e diminui a relação S/R, bem como o número de amostras da média móvel.

Acumulador

(3.2)

3.1Classificação

Linearidade

Considere as respostas resposta do sistema a sequência de entrada e resposta do sistema a sequência de entrada . O sistema é dito linear, se para uma entrada , em que e são constantes a resposta do mesmo será



Exercício

Verifique se a média móvel do exercício anterior repreenta um Sistema LinearIdem para

Idem para o sistema de ECO


Implemente um programa de simulação que seja capaz de introduzir o efeito de ECO em arquivos de som, com tempo de retardo e intensidade a especificar.

Invariância no Tempo

Considere as respostas resposta do sistema a sequência de entrada e resposta do sistema a sequência de entrada . O sistema é dito invariante no tempo, se para uma entrada , a resposta do mesmo será

Exercício

Verifique a invari6ancia no tempo para o sistema e para os demais valores de n.

Causalidade

Um sistema é dito causal se simplesmente as alterações ou reflexos em sua sequência sáida não precedem nunca uma alteração em sua sequência de entrada.

Estabilidade "BIBO" (bounded input, bounded output)

Um sistema é dito estável (do tipo "BIBO") se para todos os valores de n implica em , em que e são constantes finitas.



Passividade

Um sistema é dito passivo se,

(3.3)

Resposta Impulsiva e Relacionamento Entrada-Saída

A resposta impulsiva de um sistema resulta em uma sequência . Para o caso de um sistema acumulador tem-se,

Para sistemas LTI (Linear Time Invariant) - lineares e invariantes no tempo, é possível escrever,

(3.4)

A resposta impulsiva de um sistema resulta em uma sequência . Para o caso de um sistema acumulador tem-se,

Exercício Orientado em Sala de Aula

Sistemas LTI em cascasta e em ParaleloCondição de Estabailidade do Sistema LTI

Condição de CausalidadeSistemas FIR e IIR



4. Estudo de Sinais e Sistemas Discretos no Domínio da Frequência

4.1 Transformada Discreta de Fourier

4.1.1 Definição

A Transformada Discreta de Fourier, , de uma sequência é definida como,

(4.1)

Em geral é uma função complexa da variável real w e pode ser escrita como,

, (4.2)

em que e é a parte real e imaginária de respectivamente.

É bastante usual representar na forma polar, a partir do módulo e do argumento da mesma,

(4.3)

em que ,

(4.4)

Exercício

Calcular a transformada da sequência definida como,

4.1.2 Definição da Transformada Inversa

(4.5)

4.1.3 Condição de Convergência

(4.5)

4.1.4 Transformações de Funções Básicas e Propriedades



Sequência Transformada de Fourier1

, ( )

Tabela 4.1 - Transformações de Funções básicas

Propriedade Sequência Transformada

LinearidadeDeslocamento no Tempo

Deslocamento em Frequência

Diferenciação em Frequência nConvoluçãoModulação

Relação de Perseval

Tabela 4.2 - Propriedades básicas



4.2 Transformada Z

4.2.1 Definição

A Transformada Discreta de Fourier, , de uma sequência é definida como,

(4.6)

Se considerarmos na forma polar,

, (4.7)

que pode ser interpretada como a transformada de Fourier da sequência modificada .

em que e é a parte real e imaginária de respectivamente.

Exercício

Calcular a transformada Z da sequência definida como,

4.2.2 Definição da Transformada Inversa

(4.8)

em que C' é o contorno no sentido horário definido por .

Usando o teorema dos resíduos de Cauchy,

Outra maneira de calcular a transformada inversa é a expansão em frações parciais, da mesma forma que foi estudado no 3.o ano em Circuitos Elétricos.



4.2.3 Condição de Convergência

(4.9)

4.2.4 Transformações de Funções Básicas e Propriedades

Sequência Transformada de Fourier1

,

, ( ),

Tabela 4.3 - Transformações de Funções básicas

Propriedade Sequência Transformada

LinearidadeDeslocamento no Tempo

Multiplicação por uma sequência exponencial

Diferenciação em z nConvoluçãoModulação

Relação de Perseval

Tabela 4.4 - Propriedades básicas

Exercício Orientado em Sala de Aula

Análise de exemplos de Filtros digitais

5. Teoria da Informação



5.1 Introdução

A evolução atual dos Sistemas Digitais exige a disponibilização de enlaces de comunicação com Capacidade de transmissão cada vez maiores, capacidade esta usualmente medida em bits por segundo (bps), através de meios cada vez mais confiáveis (com baixas taxas de erro de bit). Para isto, tão importante como o desenvolvimento de técnicas que viabilizem o melhor aproveitamento de meios de Comunicação existentes é o estudo da forma eficiente de codificar digitalmente fontes de informação. Durante a Segunda Guerra mundial é observado o desenvolvimento de uma série de novas técnicas e dispositivos de Telecomunicações, como o radar por exemplo. Todavia, não haviam ferramentas que indicassem de forma clara como medir a capacidade de sistemas de comunicação e até que limite se pode otimizar um certo sistema do ponto de vista de quantidade informações que e mesmo pode transmitir e receber. Este tema foi endereçado pelo primeira vez por Claude Shannon e Warren Weaver em 1949 com o publicação de dois artigos condensados no livro "The Mathematical Theory of Communication", que deu origem a "Teoria da Informação". A Teoria da Informação estuda, como enfoque central, a maneira que mensagens produzidas por uma fonte de informação devem ser representadas para que as mesmas possam ser transmitidas de forma realizável sobre um canal com suas inerentes limitações físicas. Por limitações físicas entenda como a figura de ruído do canal, sua realizabilidade, sua potência de transmissão e largura de faixa características (vide Figura 5.1).

Fonte

Emissora

Codificador

da Fonte

Canal (Digital)

Equivalente

Decodificador

da FonteReceptor

Limitações Físicas do Canal:

•Realizabilidade

•Largura de Faixa Característica

•Potência de Transmissão

•Figura de Ruído

Nota: dizemos Canal Equivalente - Canal com Cod/Decod de Canalacoplado com a missão de reduzir/eliminar os efeitos provocados peloruído na Comunicação

MENSAGENS

OU

SÍMBOLOS

BINITS

(SÍMBOLOSBINÁRIOS)

BINITS MENSAGENS

OU

SÍMBOLOS

Figura 5.1 - Sistema de Comunicação e a Codificação da Fonte para Transmissão Digital

A maneira através da qual codificamos mensagens emitidas por uma fonte influência então a realizabilidade e eficiência com que se envia informações em um canal de comunicações. A Teoria da Informação oferece o conjunto de ferramentas matemáticas necessário que permite melhor caracterizar este processo e o estudar. Na seqüência são



apresentados e desenvolvidos os conceitos desta Teoria que são trabalhados para entender e medir os processos de Codificação Digital de Fontes de Informação.

5.2. Conceitos Preparatórios

5.2.1 Como Medir Informação de uma Mensagem

Considere uma fonte que emite um conjunto de mensagens possíveis. Para que seja viável maximizar a taxa de emissão de informações por esta fonte é necessário inicialmente medir a quantidade de informação contida em cada das mensagens da fonte. Para tal, considere o exemplo do conjunto de mensagens a seguir, emitida por uma fonte relevante a um Curso de uma Escola:

- mensagem 1:"O Professor dá aula"- mensagem 2:"O Professor virá amanhã"- mensagem 3:"O Professor não virá amanhã"

Observa-se, de forma intuitiva, que a primeira mensagem praticamente não possui ou transmite pouca quantidade de informação, visto que todos esperam em um Curso, que professores lecionem suas aulas. Já a Segunda mensagem possui uma quantidade de informação associada maior que a primeira, tendo em vista que já se saberá com antecipação que o professor irá lecionar amanhã, fato que não é tão comum quanto ao aspecto de saber-se que professores lecionam, de forma que um estudante, ao tomar conhecimento desta mensagem, saberá programar melhor o seu próximo dia. A Terceira mensagem já possui ou transmite uma quantidade de informação ainda maior que a Segunda, visto que é comumente esperado que o professor venha as suas aulas e falte pouco. Observe que para esta fonte que emite estes três tipos de mensagens de um Curso em uma Escola, a freqüência de ocorrência da mensagem 1 (um) ou evento 1 (um) é maior que a da mensagem 2 (dois), sendo que a freqüência de emissão da mensagem 3 (três) deve ser ainda menor que a do evento 2 (dois). Desta maneira, pode-se observar que a quantidade de informação que uma mensagem possui é inversamente proporcional a freqüência de ocorrência desta, emitida por uma fonte de informação. Considerando então duas mensagens, seja P(1) a freqüência ou probabilidade da primeira ocorrer e seja P(2) a probabilidade da segunda ocorrer. Seja I a quantidade de informação associada a uma certa mensagem. Então podemos dizer que:

- I é inversamente proporcional a P;- P(1) > P(2) I(2) > I(1);- P E [0,1] I >= 0;- Se as duas mensagens são estatisticamente independentes, então a quantidade de

informação associada a ocorrência ou emissão da mensagem 1 e da mensagem 2 I(12) será: I(12)= I(1)+I(2). Observe que neste caso P(12)=P(1).P(2).

É possível demonstrar que a única função matemática que satisfaz as condições acima simultaneamente é a função logaritmo.

Então, a quantidade de informação transmitida por uma mensagem será:

I=logb(1/P) (5.1)



Na Eq. (5.1) observamos b depende da escolha da unidade que desejamos medir a quantidade de informações. Por ex.: para b=2 (*), a unidade será bits, contração usual de "binary digits"; para b=10, a unidade será dígitos decimais.

(*) Obs.: Considerando o caso mais trivial de fonte binária que emite mensagens de forma equiprovável (P(1)=P(2)=0,5), I(1) = I(2) = log2(1/0,5) = 1 bit. Isto é, a quantidade de informações transmitida por uma mensagem de uma fonte binária equiprovável é de um bit.

Embora seja necessário caracterizar individualmente a quantidade de informações associada a mensagem de uma fonte, este conceito não é tão relevante quando se pensa em caracterizar uma fonte, que normalmente emite um conjunto de mensagens ou símbolos. Para tanto, desenvolveu-se o Conceito de Entropia de Fontes de Informação que é apresentado a seguir.

5.2.2 Entropia de Fontes de Comunicação

Considere uma fonte capaz de emitir um conjunto M símbolos ou mensagens distintos, {X1, X2, X3, .... Xm} e seja P(1), P(2), ... P(M) a freqüência de emissão associada a cada um dos símbolos, supondo inicialmente que a fonte tenha uma característica estacionária. Se são tomadas N amostras de emissão de mensagens, observa-se que a quantidade total de informação transmitida pela fonte será:

Q.Total = N(1).I(1) + N(2).I(2) + ... + N(M).I(M) [bits] (5.2)

Na Eq. (5.2), N(i) é igual ao número de ocorrências ou emissões da mensagem "i " em N amostras.

O quantidade média de informação por símbolo emitido (medido em [bits/simb.]) nesta amostra de N emissões é obtida dividindo a Eq. (5.2) por N:

Q.Médio = N(1).I(1)/N + N(2).I(2)/N + ... + N(M).I(M)/N [bits/simb.] (5.3)

Se na Eq. (5.3) o número de amostras é grande, pela "Teoria dos Grandes Números" observa-se que N(i)/N P(i), probabilidade de ocorrência da emissão da mensagem "i". Neste caso passa-se a chamar a quantidade média de informações medida de "Entropia da Fonte de Informação" ou simplesmente H(X).

H(X) = P(1).I(1) + P(2).I(2) + ... + P(M).I(M) [bits/simb.] (5.4)

[bits/simb.] (5.5)

Na Eq. (5.5), lembrando a relação (5.1) tem-se que,



[bits/simb.] (5.6)

O nome "Entropia da Fonte" foi dado em função de uma série de analogias, exploradas por diversos autores sobre o tema, entre esta função e a função de mesmo nome da Termodinâmica.

Caso de particular interesse para este estudo, que descreve na sequência do texto a Codificação digital, é a Entropia associada a uma fonte binária de comunicação. Para evitar confusão neste texto, cada um dos símbolos físicos emitidos por uma fonte binária é chamado de "binit" (ao invés de "bit", que é a unidade de medida de informação).

Para uma fonte binária, seja P(1)=p (probabilidade de emissão do binit "Zero") e P(2)= 1-p (probabilidade de emissão do binit "Um"), teremos então a partir da Eq. (5.6),

H.Bin = H(X) = p.Log2(1/p) + (1-p).Log2(1/(1-p)) [bits/binit] (5.7)

A Figura 5.2. a seguir traz o gráfico de H.Bin versus p. Observe que quanto mais p se aproxima de 0 (zero) ou 1 (um), significando que a fonte binária emite quase que na totalidade dos eventos o binit "Um" ou o binit "Zero", a quantidade média de informação emitida H.Bin tende a zero. Este resultado é esperado, visto que se temos certeza de que a fonte sempre emitirá um certo binit, não há informação transmitida na emissão de símbolos. Da mesma forma, observa-se que quanto mais equiprovável for a emissão do binit "Zero" e do binit "Um" (p=0,5), a Entropia tenderá a seu valor máximo (1 bit/binit). De outra maneira pode-se dizer que quando aumenta o grau de "bagunça" de emissão de símbolos (passam a ser equiprováveis) a Entropia da Fonte atinge o seu máximo. Esta última acertiva serve para justificar o nome "Entropia" a H(X), se é considerado que em um sistema termodinâmico, quanto maior a Entropia, maior será o "grau de bagunça deste".

Figura 5.2 - Evolução da Entropia de uma Fonte Binária



É possível demonstrar, generalizando o estudo de fontes binárias, que a função entropia,

(5.8)

A relação (5.8) é válida para uma fonte M-ária qualquer.

5.3. Codificação de Fontes Discretas sem Memória

Neste item são apresentadas as relações que regem a codificação digital de fontes de informação. O nome "fontes discretas" foi dado ao título pelo fato de que são trabalhadas fontes capazes de emitir um número finito de símbolos. As fontes que são trabalhadas também são supostas "sem memória". Isto significa que a emissão de um próximo símbolo pela mesma não depende da emissão de símbolos que já ocorreram (independência estatística). As fontes são consideradas "sem memória" pelo fato de que para as que o efeito de memorização é muito relevante, normalmente a utilização de preditores associados a codificadores de corrida geram uma melhor otimização da taxa de transferência de informações, através da compressão de informações por eliminação de redundâncias na transmissão simbólica, do que a codificação eficiente abordada neste material. A utilização de codificadores eficientes ainda reduzem a performance dos preditores, se estes últimos são usados em cascata aos primeiros, em sistemas que apresentam fontes com memória. As fontes de informação geradas ou associadas diretamente a seres humanos (como a transmissão de arquivos de textos codificados por exemplo) costumam apresentar um efeito de memorização ou dependência de emissão simbólica acentuada. Todavia, como a construção de circuitos e algoritmos preditores é bem mais custosa que a de circuitos e algoritmos codificadores eficientes, normalmente estes últimos são utilizados em casos práticos de Eng. de Telecomunicações ou de Eng. de Computação para tais fontes.

A Figura 5.3 ilustra o esquema geral do codificador que é estudado. A saída de uma fonte M-ária, que emite símbolos do alfabeto {X1, X2, X3, .... Xm}, é acoplada a um codificador binário, para que seus símbolos possam ser corretamente codificados e enviados ao canal/sistema digital de transmissão. A saída do canal de comunicação deve estar ligada ao decodificador binário que irá reconstituir os símbolos M-ários para o Receptor.



Codificador

BinárioCanal (Digital)

Decodificador

BinárioReceptor

MENSAGENS

{X1, X2, ..., XM}

R = r.H(X) [bits/s]

BINITS

(SÍMBOLOSBINÁRIOS: “0”, “1”)

rb.H.bin <= rb [bits/s]

BINITS MENSAGENS

OU

SÍMBOLOS

Fonte

Discreta

M-ária

Canal - possui certa Capacidade de envio de Binits por intervalo de tempo

[binits/s]

Devemos maximizar o possibilidade de envio de informações [bits/s] através doCanal com uma Codificação Eficiente

Cod/Decod - não podem nem criar, nem destruir informações

R = r.H(x) = rb.H.bin <= rb [bits/s]

Nmed ( = rb/r) >= H(X)

Figura 5.3 - Diagrama de Blocos da Codificação Digital de Fontes Discretas

Considerando que a fonte emita símbolos a uma taxa de r [simb./s], então a taxa R de emissão de informações será,

R = r. H(X) [bits/s] (5.9)

Considerando que o codificador binário emita binits a uma taxa rb [binits/s], então a taxa Rb de emissão de informações pelo codificador será,

Rb = rb. H.Bin [bits/s] (5.10)

Como o codificador deve trabalhar sem criar ou destruir informações, pode-se dizer que a quantidade de informações que entram no codificar em um certo intervalo de tempo "T" tem que ser igual a quantidade de informações que saem neste mesmo intervalo,

r. H(X).T = rb.H.Bin.T [bits] (/T) r. H(X) = rb. H.Bin [bits/s] (5.11)

Da Figura 5.2 observamos que H.Bin é sempre menor ou igual a 1 (um), o que permite rescrever a Eq. (5.11) como,

[bits/s] (5.12)

Dividindo a Eq. (5.12) por r, o observando que rb/r [binits/simb.] eqüivale a quantidade média de binits codificados pelo codificador para cada símbolo emitido pela fonte, ou simplesmente Nmed, podemos escrever,

(5.13)



A Eq. (5.13) diz que a entropia da fonte emissora do alfabeto simbólico "X" é sempre o limite inferior para o tamanho médio em binits (Nmed) dos símbolos gerados pelo bloco codificador para cada símbolo emitido. Por outro lado, observe que, dado um canal digital que possui uma certa capacidade de transmissão medida em binits/s, o quanto menor for o Nmed do codificador, mais este otimizará a emissão de informação ou a emissão de símbolos da fonte através deste canal. Diz-se nestas condições que o codificador é "eficiente". Dividindo a Eq. (5.13) por Nmed, podemos definir então a eficiência de uma certa codificação,

(5.14)

Observe na Eq. (5.14), que quanto mais Nmed H(X), maior será a eficiência de codificação (Ef.cod 1) e mais R rb, maximizando a taxa de envio de informações como explicado anteriormente.

O Nmed pode ainda ser calculado através da quantidade de binits que o codificador utiliza para cada símbolo emitido pelo fonte (N(1) para X1, N(2) para X2, etc.). Então,

[binits/simb.]

(5.15)

A busca de códigos eficientes é trabalhada pelo "Teorema da Codificação das Fontes de Shannon", que afirma que dado um certo é sempre possível encontrar um código unicamente dicifrável, isto é, que não crie e nem destrua informações geradas pela fonte, que satisfaça a relação,

(5.16)

Para que seja possível adquirir algum sentimento sobre a Eq. (5.16), basta rescrever a mesma observando as Eq.s (5.15) e (5.6),

(5.17)

Observe que se considerarmos =1, admitindo que é possível escolher para cada símbolo Xi um código N(i) (com um número inteiro de binits) entre I(i) e I(i)+1 (observe que a quantidade de informação em bits de um certo símbolo não é necessariamente um número inteiro) e tomando a somatória para os M símbolos, chegaremos a inequação (5.16). Simplificadamente eqüivale a dizer que símbolos que ocorrem com freqüência elevada (ou I baixo) em uma fonte devem ser codificados com um número de binits menor (N menor) do que aqueles símbolos que ocorrem com uma freqüência mais baixa, se quisermos otimizar a capacidade de transmissão de informação do canal de comunicação. Este conceito foi utilizado por Samuel Morse para gerar a codificação que levou o seu nome



(código Morse) e foi obtida pelo mesmo através da contagem de ocorrência (freqüência) de letras em uma folha escrita em inglês, escolhida aleatoriamente numa pilha de papel. Os exemplos de casos que são desenvolvidos na seqüência deste material ajudam a solidificar os conceitos apresentados nesta seção.

Outro aspecto de igual importância é garantir que os códigos construídos pelo codificador sejam unicamente decifráveis, para que a informação possa ser recuperada corretamente pelo decodificador. Um dos testes utilizados para tal é a desigualdade de Kraft, que é condição necessária a ser obedecida pelos codificadores para que exista a decifrabilidade única.

(5.18)

A Tabela 5.1 abaixo oferece um exemplo de teste da desigualdade de Kraft.

Símbolo Código 1 Código 2A 1 000B 0 001C 10 010D 11 011E 100 100

Kcódigo 1,625 0,625Tabela 5.1 - Exemplo de aplicação de desigualdade de Kraft

Neste exemplo observa-se que o código 1, embora possua códigos de tamanho menor do que o código 2 para símbolos respectivos, não respeita a desigualdade de Kraft, não sendo unicamente dicifrável portanto. Basta também observar que a codificação de um D, poderá ser interpretada pelo decodificador como AA ou D, não existindo unicidade no processo de codificação e decodificação.

A seguir são apresentados os processos construtivos dos Códigos eficientes de Shannon-Fano e de Huffman, bastante usados na prática.

5.4 Codificação eficiente de Shannon-Fano e de Huffman

5.4.1 Códigos Fonte com comprimento variável

A motivação para códigos fontes de comprimento variável baseia-se na intuição de que compressão de dados pode ser alcançada pelo mapeamento de letras de probabilidades maiores com seqüências de bits menores, mesmo que letras com menores probabilidades devam ser mapeadas com seqüências de bits mais longas. Não há necessidade de um modelo probabilístico da fonte muito preciso para haver tanta motivação; por exemplo, o



velho código Morse da telegrafia foi elaborado com esta motivação, tendo-se apenas uma certa idéia das freqüências das letras na Língua Inglesa. Um código fonte de comprimento variável C mapeia cada letra fonte x de um alfabeto fonte X em uma string C(x), chamada de palavra código, de comprimento l(x). Por exemplo, um código para o alfabeto X = {a, b, c} pode ser dado por,

C (a) = 0 C (b) = 10 C (c) = 11

Assume-se que as palavras código de um código fonte de comprimento variável são transmitidas como uma seqüência continua de bits sem nenhuma demarcação de início e fim de cada uma (i.e. sem vírgulas). O decodificador da fonte deve determinar onde estão os limites ou fronteiras; isto é denominado "parsing" (do Inglês).

5.4.2 Unicidade de Decodificação

Para um código fonte C de comprimento variável sem ruído requer-se que C seja unicamente decifrável, significando que a seqüência de letras da fonte de entrada pode sempre ser reconstruída sem ambigüidade a partir da seqüência de bits codificada da fonte.

Nota: sincronização inicial é assumida: o decodificador da fonte sabe qual é o primeiro bit da seqüência codificada.

Claramente, um código fonte C é unicamente decodificável, se e somente, o mapa de codificação da fonte é de 'um para um'.

Exemplo: o código C para o alfabeto X = {a, b, c} dado acima é dito "prefix-free" (livre de prefixo) e assim unicamente decodificável, como veremos a seguir. No entanto, o código C' definido por,

C' (a) = 0C' (b) = 1

C' (c) = 01

não é unicamente decifrável. Por exemplo, se o decodificador fonte observa "01", ele não pode determinar se a fonte emitiu (a, b) ou (c). O problema observado aqui é fundamental e está relacionado com os comprimento das palavras códigos, 1 (um), 1 (um) e 2 (dois), e nenhum código unicamente decodificável pode ter este conjunto de palavras código com estes comprimentos.



5.4.3 Códigos "prefix-free"

Verificar se um código é unicamente decodificável pode ser bem complicado. No entanto, existe um boa classe de códigos unicamente decodificáveis chamados de códigos "prefix-free", que possuem inúmeras vantagens. É muito simples checar se um código é "prefix-free" e assim unicamente decodificável. Códigos "prefix-free" tem a vantagem adicional que o decodificador da fonte pode ser implementado com delay mínimo. Pode ser demonstrado que se existe um código unicamente decifrável com um certo conjunto de comprimentos de palavras, então existe também um código "prefix-free" com o mesmo conjunto de comprimentos.

Definição: Um código é "prefix-free" se nenhuma palavra código for um prefixo de outra palavra código.

Por exemplo, o código C é "prefix-free", mas o C' não é. Qualquer código de comprimento fixo é "prefix-free".

É examinado a seguir que todo código "prefix-free" é unicamente decodificável. A prova é construtiva, e mostra como o decodificador da fonte consegue unicamente determinar os limites da palavra código.

Dado um código C "prefix-free", é construída uma árvore de código binário correspondente, que cresce de uma raiz da esquerda para folhas na direita representando as palavras código. Por exemplo, a árvore abaixo ilustra a árvore binária para o código mostrado. A árvore binária é estendida suficientemente para a representação das palavras código.

Figura 5.4: Árvore de códigos binários para um código "prefix-free".


10

10

10

a

b

ca 0b 11c 101


A condição "livre de prefixo" garante que cada palavra código corresponda a um ramo, porque um ramo intermediário representa um "prefix" para qualquer ramo saindo dele. Note que a árvore da Figura 5.4 tem um ramo, correspondente à string "100" que não representa uma palavra código. A árvore nos mostra que a palavra código para "c" pode ser diminuída para "10" sem destruir a propriedade de "prefix-free", como mostrado na Figura 5.5.

Figura 5.5: Árvore de códigos binários para um código "prefix-free" mais eficiente.

A árvore do código de "prefix-free" será denominada "full", ou cheia, se todos os ramos correspondem a palavras de código. Assim, a árvore da Figura 5.4 não é cheia, mas a da Figura 5.5 é. Como é visto neste exemplo, uma árvore que não é cheia pode sempre ser encurtada para uma árvore cheia mais eficiente.

Figura 5.6: Árvore de códigos binários para duas palavras código.

Para ver intuitivamente porque a condição de "prefix-free" garante decifrabilidade única, considere a árvore para a concatenação de duas palavras código. Utilizando a árvore da Figura 5.5, obtém-se a esquematizada na Figura 5.6. A nova árvore foi formada simplesmente pelo transplante de uma cópia da árvore original para cada ramo desta original. Alguém poderia imaginar que transplantes subsequentes para os ramos da Figura 5.6 para se obter uma árvore representando ainda mais palavras código juntamente concatenadas. Está claro desta construção que cada seqüência de palavras código encontra-se em um nó diferente na árvore e assim será codificada em uma seqüência binária diferente, não importando quão longo o processo continue.


1 0

a

1 0

b

c

a 0b 11c 10

a

aaac

abc

cacc

cb

bb

bcb ba


Assim, todos os códigos "prefix-free" são unicamente decifráveis.

5.4.4 Codificação de Shannon-Fano

A codificação de Shannon-Fano gera uma codificação eficiente na qual o comprimento das palavras aumenta conforme as probabilidades dos símbolos diminuem, mas não necessariamente em estrito acordo com a equação,

(5.19)

O algoritmo provê uma estrutura de árvore de codificação para assegurar decifrabilidade única. É aplicado o algoritmo para a fonte com M = 8 e H(X) = 2,15, cujas estatísticas estão listadas na Tabela 5.2.

xi Pi 1 2 3 4 5 6 CodificaçãoA 0,50 0 0B 0,15 1 0 0 100C 0,15 1 0 1 101D 0,08 1 1 0 110E 0,08 1 1 1 0 1110F 0,02 1 1 1 1 0 11110G 0,01 1 1 1 1 1 0 111110H 0,01 1 1 1 1 1 1 111111H(X) = 2,15

Tabela 5.2: Codificação de Shannon-Fano

O algoritmo de Shannon-Fano envolve uma sucessão de passos de "dividir" e "conquistar". Para o primeiro passo, desenha-se uma linha que divide os símbolos em grupos de dois, tais que as probabilidades dentro dos grupos sejam as mais aproximadas possíveis; então designa-se o dígito "0" para cada símbolo do grupo acima da linha e o dígito "1" para cada símbolo do grupo abaixo da linha. Para todos os passos subseqüentes, deve-se subdividir cada grupo em subgrupos e novamente designar dígitos seguindo a regra anterior. Sempre que um grupo tiver somente um símbolo, como acontece nos passos primeiro e terceiro na Tabela, não dá para seguir adiante com subdivisões e a codificação para aquele símbolo estará completa. Quando todos os grupos tiverem sido reduzidos a um símbolo, as codificações serão dadas pelos dígitos designados lendo da esquerda para a direita. Um exame cuidadoso da Tabela 5.2 deve clarificar este algoritmo.

A codificação de Shannon-Fano resultante neste caso tem , então a eficiência é de 2,15/2,18 ≈ 99%. Assim, se a taxa de símbolo é r = 1000, então rb = = 2180 binits/seg — um pouco maior que R = rH(X) = 2150 bits/seg. Como comparação, um código de comprimento fixo necessitaria de = log 8 = 3 e rb = 3000 binits/seg.


Passos da Codificação


5.4.5 Codificação de Huffman

É interessante saber a codificação ótima da fonte que minimiza L médio (L é o número de bits codificados) para uma dada fonte. A resposta é a codificação de Huffman.

Por conveniência todos os símbolos são listados verticalmente em ordem decrescente de probabilidade. Supõe-se que os símbolos são as oito palavras Inglesas "the", "man", "to", "runs", "house", "likes", "horse", "sells", que ocorrem independentemente com probabilidades de terem sido escolhidas, ou de aparecer, como listado na Tabela 5.3.

Palavra / Mensagem ProbabilidadeThe 0,50Man 0,15To 0,12

Runs 0,10House 0,04Likes 0,04Horse 0,03Sells 0,02

Tabela 5.3: Palavras escolhidas e suas Probabilidades

A Figura 5.7 mostra como se pode construir a codificação eficiente palavra por palavra. As palavras são listadas à esquerda, e as probabilidades estão entre parênteses. Ao construir o código, primeiro encontram-se as duas menores probabilidades, 0,02 (sells) e 0,03 (horse), e desenham-se linhas ao ponto marcado 0,05, a probabilidade de se ter ou "horse" ou "sells". Então passa-se a desconsiderar as probabilidades individuais conectadas pelas linhas e procuram-se pelas duas menores probabilidades, que são 0,04 (like) e 0,04 (house). Desenham-se linhas para a direita ao ponto marcado com 0,08, que é a soma de 0,04 e 0,04. As duas menores probabilidades restantes são agora 0,05 e 0,08, então uma linha para a direita é desenhada conectando a elas, para dar um ponto marcado 0,13. Procede-se assim até que as linhas formem caminhos de saindo de cada palavra até um ponto em comum à direita, o ponto marcado 1,00. Agora cada trilha da parte de cima indo para a esquerda de um ponto é rotulada de "1" e cada uma da parte de baixo, de "0". O código para uma dada palavra é então a seqüência de dígitos encontrados caminhando para a esquerda do ponto em comum 1,00 até a palavra em questão. Os códigos estão listados na Tabela 5.4.



Palavra / Mensagem

Probabilidade p

Código No. de dígitos no Código, N

Np

The 0,50 1 1 0,50Man 0,15 001 3 0,45To 0,12 011 3 0,36

Runs 0,10 010 3 0,30House 0,04 00011 5 0,20Likes 0,04 00010 5 0,20Horse 0,03 00001 5 0,15Sells 0,02 00000 5 0,10

2,26

Tabela 5.4

Na Tabela 5.4 é mostrado não somente cada palavra e seu código mas também a probabilidade de cada código e o número de dígitos em cada código. A probabilidade de uma palavra vezes o número de dígitos no código dá o no. médio de dígitos por palavra em uma longa mensagem devido ao uso daquela palavra em particular. Se os produtos das probabilidades e os números de dígitos para todas as palavras são adicionados, o número médio de dígitos por palavra é obtido, que resulta em 2,26. Isto é um pouco maior que a entropia por palavra, que encontramos ser 2,21 bits por palavra, mas é um número menor de dígitos do que os 3 dígitos por palavra que se teria utilizado meramente fosse designado um código de 3 dígitos qualquer para cada palavra. Não somente pode ser provado que esta codificação de Huffman é a mais eficiente para codificar um conjunto de símbolos tendo diferentes probabilidades, também pode ser provado que ela requisita menos que um dígito binário por símbolo que a entropia (no exemplo acima, a codificação pede por apenas 0,05 dígitos binários extras por símbolo.)

5.5 Estudo de Casos

5.5.1 Codificações possíveis de uma Fonte de Informação

Para este primeiro estudo de Caso considera-se como fonte emissora um Computador Digital que emite para um Canal um alfabeto de 8 símbolos (codificados internamente em ASCII). Deseja-se saber, dada a freqüência característica de emissão destes símbolos, qual as possibilidades de codificação das mensagens para melhor aproveitar a banda de 512 Kbps do Canal de Comunicações.

A Figura 5.7 a seguir mostra um resumo da situação e da análise que é feita neste caso.

- Uma primeira tentativa de transmissão de símbolos, já que estes são codificados e trabalhados internamente no Computador (fonte emissora) em ASCII, é emitir para o canal digital os símbolos com esta codificação pura e simplesmente. Sob a Luz da Teoria da Informação esta situação pode parecer pouco eficaz, porém é válido alertar que é freqüente de ser encontrada em situações práticas de implementações de Sistemas



de Telecomunicações, em que em geral o "custo versus benefício" de implementação de codificadores eficientes não é justificável.

Esta situação é bem pouco eficiente do ponto de vista de codificação, uma vez que a emissão simbólica utiliza um alfabeto de somente 8 símbolos e os mesmos não possuem freqüências de ocorrência iguais (gerando H(X)=2,18 bits/Simb). Este padrão de codificação, com Nmed de 8 binits/simb, possui uma baixa eficiência (aprox. 27%, segundo a Eq. (5.14)) e não otimiza a velocidade de envio de informações pelo canal, de aprox. 139 Kbits/s, calculada usando as Eq.s (5.9), (5.11) e (5.12).

- Uma segunda abordagem para a transmissão de símbolos, é emitir para o canal digital os oito símbolos possíveis com uma codificação binária simples, mais compacta que o ASCII (Nmed = 3 binits/simb.).

Esta situação é mais eficiente eficiente que o primeiro caso analisado do ponto de vista de codificação, com uma eficiência de aprox. 73%, melhorando a velocidade de envio de informações pelo canal, para aprox. 372 Kbits/s, calculada usando as Eq.s (5.9), (5.11) e (5.12).

- Já para as opções três e quatro, utilizam-se técnicas de codificação eficiente dos símbolos (Huffman e Shannon-Fano), que levam em consideração o aspecto de que símbolos que ocorrem muito freqüentemente (como o A, e que transmite baixa quantidade de informação) devem ser codificados com um número baixo de Binits, se se quer aproximar as relações descritas na Eq. (5.17). Observe que a eficiência destas codificações é de 98% (quase uma codificação ótima, onde a relação H(X)/Nmed = 1), o que eleva bastante a taxa de emissão de informação ao canal (aprox. 504 Kbits/s), tornando o processo de comunicação bem mais eficiente.

Pelo aspecto curioso de se estar trabalhando com um Computador, em que os símbolos são codificados tipicamente com ASCII, existe a sensação de que os mesmos são emitidos ao canal numa taxa (em binits ASCII/ s) muito maior (1853 Kbps) que a Capacidade do Canal (512 Kbps). Pode-se ainda calcular o que comercialmente se chama de "Compressão de Dados", relacionando as duas velocidades enxergadas (3,6:1). Vale alertar que, embora este termo seja muito usado comercialmente para softwares e hardwares de codificação eficiente de arquivos e dados respectivamente, ditos "Software ou Hardwares de Compressão", sob a Luz da Teoria da Informação, só estariam habilitados a serem chamados de "Compressores" aqueles dispositivos que se utilizam de algoritmos preditores capazes de reduzir a redundância das informações, devido ao efeito de memorização de fontes.



Fonte Emite 8 Símbolos / Mensagens distintasVelocidade do Canal - rb [Kbinits/s] 512,0

Símbolo FrequênciaQuantidade de

Informação [Bits]Codificação ASCII

Codificação Binária Simples

Codificação Eficiente de Shannon-Fano

Codificação Eficiente de

Huffman

A 0,5 1,000 01000001 000 0 0B 0,15 2,737 01000010 001 100 100C 0,15 2,737 01000011 010 101 101D 0,07 3,837 01000100 011 110 111E 0,07 3,837 01000101 100 1110 1100F 0,04 4,644 01000110 101 11110 11010G 0,01 6,644 01000111 110 111110 110110H 0,01 6,644 01001000 111 111111 110111

Análise:H(X) [bits/simb] 2,177

Nmed [binits/simb] 8,00 3,00 2,21 2,21

Eficiência Código (%) 27,21 72,56 98,50 98,50

Tx. Envio Simbolos - r [KSimb.s/s] 64,00 170,67 231,67 231,67

Tx. Envio de Informação - R [Kbits/s] 139,32 371,51 504,32 504,32

Vel. Equivalente "ASCII" [Kbinits/s] 512,00 1365,33 1853,39 1853,39

1,00 2,67 3,62 3,62

Codificação Digital de Fontes Discretas - Estudo de Caso

Taxa de "Compressão" do Canal vista pela Fonte

Figura 5.7 - Resumo da Análise de Codificações Possíveis de uma Fonte de Informação

5.5.2 Codificador Adaptativo Eficiente de Shannon-Fano

Neste caso, executa-se e se analisa a implementação em simulador (Matlab1) do algoritmo de Shannon-Fano no codificador de uma fonte discreta capaz de emitir 6 símbolos. A fonte é suposta como sendo estacionária. Todavia, como ocorre em codificadores eficientes práticos, o sistema de codificação não conhece inicialmente a freqüência de emissão de símbolos pela fonte. No algoritmo listado na Figura 5.8, o codificador monta internamente uma tabela de freqüências acumulativas de ocorrências dos símbolos.

1 O Matlab é uma marca registrada. Software de Simulação com direitos reservados a MathWorks Inc..



Figura 5.8 - Programa de Simulação do Codificador Adaptativo usando o Algoritmo Eficiente de Shannon-Fano para uma Fonte Discreta capaz de emitir 6 símbolos



Os símbolos emitidos pela fonte (total de 6) são gerados pseudo-aleatoriamente (matriz "O" do algoritmo) com a frequência (probabilidade) especificada no vetor "PS" de inicialização do algoritmo.

Esta tabela de frequências acumulativas (matriz "P" no algoritmo), neste exemplo didático para análise, é atualizada a cada emissão de novo símbolo pela fonte (na prática isto não ocorre, mas sim a cada bloco de N emissões, pois demandaria a alocação de uma parte da banda de comunicação no canal entre o codificador e decodificador excessivamente grande, para que os mesmos pudessem controlar a atualização e a sincronização de suas tabelas de codificação/decodificação eficientes). A cada atualização da tabela, o codificador executa o algoritmo de Shannon-Fano para determinar qual a melhor codificação eficiente que maximizará e emissão de informação entre a fonte emissora e receptor, adaptando sua codificação iterativamente (representada no algoritmo pela multiplicação da matriz "BI" com a matriz "P" e a determinação da codificação que gera o Menor Nmed). As figuras 5.9 a 5.12, mostram o resultado da simulação para as freqüências de emissão de símbolos especificadas. Em duas figuras são executadas várias repetições do algoritmo (40) para que se obtenha a tendência estatística de funcionamento do Codificador e do Decodificador (calculadas no algoritmo através dos vetores "HEM" e "NE" e controladas pela variável "simula").

Figura 5.9 - Evolução do Nmed e H(X) visto pelo Codificador para fonte emissora de 6 símbolos com freqüências {0,9; 0,02; 0,02; 0,02; 0,02; 0,02}. A Execução da Adaptação do

Codificador é repetida 40 vezes e os valores médios estatísticos são apresentados.






Codificador é repetida somente 1 vez.


Codificador é repetida 40 vezes e os valores médios estatísticos são apresentados.




Codificador é repetida 1 vez

Observando os 4 gráficos apresentados, podem ser efetuadas as seguintes análises:

- Os mesmos sempre iniciam (para número de emissões de símbolo igual a 1) com Nmed=1 e H(X)=0, visto que quando somente 1 símbolo é emitido, o codificador assume que a probabilidade de emissão do mesmo é 1 (gerando H(X)=0) e codifica o mesmo com 1 binit.

- Existe sempre uma diferença entre o Nmed obtido pelo codificador e H(X), em obediência a Eq. (5.13) calculada. Caso o codificador conseguisse o caso particular Nmed=H(X), diz-se que o mesmo obteve uma codificação ótima (sua Eficiência, em acordância com a Eq. (5.14) seria de 100% e R = rb, com a máxima transferência de informação possível igual a taxa de emissão de binits no Canal). Como o processo de codificação de Shannon-Fano subdivide o conjunto simbólico em duas partições sucessiva e recursivamente, só existe a possibilidade deste código gerar uma codificação ótima quando o número de símbolos for uma potência de 2 e quando as freqüências de ocorrência são representadas por inversas de potência de dois (nestas condições).

- Mesmo não obtendo uma codificação ótima, o Nmed deste codificador é bem melhor que o de uma codificação binária simples, que geraria Nmed=3 binits, possuindo uma eficiência de codificação maior que esta Segunda (H(X)/Nmed).

- Pelos gráficos 5.9 e 5.11, observa-se que quanto menor a Entropia da fonte (maior a tendência de emissão de certos símbolos), mais iterações/emissões de símbolos são necessárias para que o algoritmo tenha convergência e estabilize em um Nmed



eficiente (50 iterações na figura 5.11 e 100 iterações na figura 5.9 aproximadamente). De uma forma genérica, quanto maior o número de símbolos e menor for a entropia da fonte, mais iterações serão necessárias para depurar os valores de freqüência de emissão de símbolos individualmente e fazer com que Nmed Nmed eficiente.

- Observe que embora a tendência estatística observada nos gráficos das figuras 5.9 e 5.11 indiquem nestes exemplos que existe convergência em 100 e 50 emissões de símbolos em média respectivamente, se forem tomados os gráficos de simulação individual das figuras 5.10 e 5.12, verifica-se que pode ser necessário um número de iterações (emissões) bem mais elevado para convergência (aproximadamente 500 e 350 respectivamente).

5.6 Como Ensaiar a Eficiência de Codificadores Digitais Comerciais

Muitas vezes em situações práticas da Eng. de Telecomunicações ou da Eng. de Computação ocorrem situações em que são usados equipamentos com codificadores comerciais prontos. Existe uma forma indireta de se verificar o desempenho dos mesmos que é relativamente simples. Observando as equações (5.14) e (5.12), verifica-se que na situação de codificação eficiente, isto é, quando Nmed H(x), ou na situação de codificação ótima, quando Nmed = H(X), a entropia da saída do codificador H.bin deve se aproximar de 1 [bit/binit]. Isto significa que o codificador esta emitindo binits "Zeros" e binits "Uns" de forma equiprovável. Basta então medir ou amostrar, com o apoio de um analisador de dados, a freqüência de emissão de binits "Zeros" e binits "Uns" nas diversas situações de operação da fonte emissora e do sistema, para se ter uma medida indireta da eficiência de codificação do equipamento e de sua capacidade de adaptação. O mesmo procedimento pode ser usado medir a eficiência de algoritmos computacionais de codificação eficiente (muitas vezes chamados erroneamente de "Compressores de dados").

5.7 Considerações Finais

Como foi verificado, a Codificação Digital eficiente de Fontes de transmissão é fundamental para otimizar o aproveitamento da Capacidade dos Canais de Comunicação, no que se refere a taxa de envio de informação. Costuma-se evidenciar esta importância chamando o processo de codificação eficiente de fontes ou codificação ótima de "Casamento de Codificação para maximizar a transferência de Informações em um Canal de Comunicação", em analogia ao Teorema da Eng. Elétrica de "Casamento de Impedâncias para Máxima transferência de potência de sinais".



Parte 2 - Engenharia de Software

O Software e seus Processos

Sumário

Software–Definição, Características, Aplicações–Evolução

Problemas Atuais do “Software” Mitos do Software Engenharia de Software e “Verdades”

Software

Aspectos Históricos:

– Década 50 a 70: Hardware era o foco principal do desenvolvimento computacional

» Desafio: aumentar a velocidade de processamento a custos menores e a capacidade de armazenamento de dados

– Atualmente:

» Hardware é visto como “Commodity” » Desafio: reduzir os custos de implementação do Software e a qualidade » Melhorar a Funcionalidade » Tornar o Software mais “Amigável”

Definição - Dicionário

No dicionário é possível encontrar:

– “Aquilo que pode ser executado por um equipamento (o hardware)”

– “Um produto comercializado que é constituído por um sistema de rotinas e funções”



– “Programa”

Do que é constituído?

1- INSTRUÇÕES (programas de computador)

capazes de produzir a função e o desempenho desejados

2 - ESTRUTURAS DE DADOS

quando bem trabalhadas viabilizam que os programas manipulem adequadamente a informação

3 - DOCUMENTOS

descrevem como operar e utilizar os programas

Então, o que é Software?

Para Viabilizar uma definição mais precisa:

Devemos analisar as características que o tornam diferente de outros produtos!

Neste sentido:

– Hardware: produto na forma física

– Software: elemento de sistema lógico» Portanto - conceituações diferentes!

Características

1- É desenvolvido e/ou projetado usando técnicas de engenharia, não sendo manufaturado no sentido clássico

– sucesso é medido pela qualidade e não quantidade

2- Não se “desgasta”, mas se deteriora devido as mudanças!



3- a maioria é feita sob medida em vez de ser montada a partir de catálogos de componentes existentes (visão hardware em engenharia)

- reusabilidade de código ... software

Hardware: Conceito de Falhas

t“desgaste”“mortalidadeinfantil”

%Falhas

Defeitos de Projeto e/ou Manufatura

ProblemasAmbientais:

poeira, oxidação,vibração,

temperaturas, etc.

MTBF– Medium Time Between Failures

MTTR– Medium Time To Restore



t

% FalhasProdutosFísicos

Software: Conceitos de falhas

Alterações%

Falhas Curva Real

Curva Ideal

t

Conceitos de falhas em Hw/Sw

– Um componente de hw ao se desgastar é substituído por uma “peça de reposição”

– Para Sw não existe “peça de reposição”

» Cada falha é ocasionada por um erro no projeto ou no processo de tradução (para o código que é executado)

» A Manutenção do software é mais complexa do que a do hardware



Onde encontrar a falha de Hw? Conceito de perímetro

Onde encontrar a falha de Sw? O que testar? O que validar?

Definição de Software (1)

De acordo com A Von Staa (1987):

– De forma usual são componentes de sistemas automatizados– São compostos por código, dados, documentação e procedimentos– São desenvolvidos com o objetivo de instruir máquinas e pessoas - com o sentido da realização de um conjunto bem definido de tarefas de processamento de dados– São instrumentos para alcançar uma finalidade específica:

transformar dados em resultados confiáveis, úteis e oportunos


De acordo com A Von Mayhauser (1990):

“Software é a designação dada a programas de computadores e todos os documentos associados com eles, tais como os manuais de usuário”


– Quando devemos desenvolver Software?

» ALGORITMO - Aplicável a todo problema onde um conjunto previamente de passos e/ou procedimentos tiver sido definido - o que chamamos de algoritmo!

» Exceto IA - A última definição é válida com exceção de Softwares de Inteligência Artificial - como por exemplo Sistemas Especialistas ou Sistemas Tutores Inteligentes.



Software - Classificação

SOFTWARE BÁSICO coleção de programas escritos para apoiar outros programas. Forte interação com o hardware

– sistema operacional, compiladores, ...

– Windows, Linux, Unix, ...

SOFTWARE DE TEMPO REAL software que monitora, analisa e controla eventos do mundo real

– sistema de controle de tráfego aéreo, relógio digital, ...

SOFTWARE COMERCIAL sistemas de operações comerciais e tomadas de decisões administrativas

– folha de pagamentos, contas a pagar e a receber, ...

– ERP’s: SAP, Microsiga, ...

SOFTWARE CIENTÍFICO E DE ENGENHARIA caracterizado por algoritmos de processamento de números

– análise de estruturas, análise de processos químicos, astronomia, análise de fadiga de aeronaves, projeto CAD, ...

SOFTWARE EMBUTIDO usado para controlar produtos e sistemas para os mercados industriais e de consumo

– Controle de microondas, IE de automóveis, ABS, Sistema DVDs



Evolução Histórica

Hardware

– Primeiros Protótipos - 1930

» Dispositivos de Estado Sólido

Eram tidos como não confiáveis!

» Eletromecânico / Eletrônico valvulado

– Década de 1950 - Computadores de Von Neumann

– Década 1960 - Cérebros eletrônicos (main frames)

– Década 1970 - Invenção do CI - Início da Computação Pessoal

– Década de 1980 - Explosão da Computação Pessoal

– Década de 1990 - Explosão das Redes de Computadores

– Década de 2000 - Otimização!



Software

Software - Road Map

1950 1960 1970 1980 1990 2000

O início•Orientação - batch•Software customizado

A “Segunda” Era•SW Multiusuário•SW Tempo real•BD’s•Desenvolvedores(Software Houses)

A “Terceira” Era•SDs•Hw de baixo custo•Computação Pessoal•Impacto de consumo

A “Quarta” Era• IA - SistemasPesecialistas, RedesNeurais• OO•Computação Paralela(distribuída econcentrada)

Fase 1965 - 75:

Sistemas Multiusuáros e Multiprogramação

Técnicas interativas com usuários

Sistemas de tempo real - chão de fábrica

SGBD’s - 1.a Geração

Software como “Produto” - Software Houses

Cresce número de sistemas - Manutenção difícil!

..... PROBLEMAS! ..... PROBLEMAS!

Fase 1975 - 90:

SDs

Hw de baixo custo

Redes de Computadores - LAN, MANs e WAN

Popularização do uso de microprocessadores

“produtos inteligentes”

Consumo!



Fase Atual:

IA - Inteligência Artificial

Sistemas Especialistas, Redes Neurais, ...

OO - Orientação a Objetos

Computação Paralela - Concentrada e Distribuída em Rede

Problemas atuais do Software

Encontrados no desenvolvimento de software: (não somente SW que não funciona correta ou adequadamente!)

1-1- As estimativas de prazo e custo normalmente imprecisasAs estimativas de prazo e custo normalmente imprecisas

– Não é dedicado tempo para coleta de dados do processo de desenvolvimento de software

– Estimativas são feitas grosseiramente, com resultados ruins

– Os prazos não são cumpridos

– Insatisfação do cliente e falta de confiança

– Sem indicadores de produtividade

» não é possível avaliar com precisão a eficácia

2-2- A produtividade de pessoas envolvidos com software não tem acompanhado a demandaA produtividade de pessoas envolvidos com software não tem acompanhado a demanda por seus serviçospor seus serviços

– Os projetos de desenvolvimento são tipicamente iniciados apenas com um vago indício das exigências do cliente

– Comunicação Cliente-Desenvolvedor é fraca



3-3- A qualidade de software por vezes é inadequadaA qualidade de software por vezes é inadequada

– Não utilização de técnicas de teste - sistemáticas e completas

– Só recentemente - conceitos quantitativos sólidos - Garantia de Qualidade de SW

4- O software existente é muito difícil de manterO software existente é muito difícil de manter

– A atividade de manutenção tem custos muito elevados

– A facilidade de manutenção não foi enfatizada como um critério importante

– Parece evidente ser necessário:

» Que problemas citados sejam corrigidos

» Necessária abordagem de engenharia de software e uso dissiminado de técnicas e ferramentas

Causas dos problemas atuais

PRÓPRIO CARÁTER DO SOFTWARE (INTRINSECO)PRÓPRIO CARÁTER DO SOFTWARE (INTRINSECO)

FALHAS DAS PESSOAS RESPONSÁVEIS PELO DESENVOLVIMENTO DEFALHAS DAS PESSOAS RESPONSÁVEIS PELO DESENVOLVIMENTO DE SOFTWARESOFTWARE

MITOS DO SOFTWAREMITOS DO SOFTWARE



PRÓPRIO CARÁTER DO SOFTWARE (INTRINSECO)PRÓPRIO CARÁTER DO SOFTWARE (INTRINSECO)

O software é um elemento de sistema lógico e não físico. Consequentemente o sucesso é medido pela qualidade de uma única entidade e não pela qualidade de muitas entidades manufaturadas

“O software não se desgasta, mas se deteriora”“O software não se desgasta, mas se deteriora”

FALHAS DAS PESSOAS RESPONSÁVEIS PELO DESENVOLVIMENTO DEFALHAS DAS PESSOAS RESPONSÁVEIS PELO DESENVOLVIMENTO DE SOFTWARESOFTWARE

Gerentes - sem nenhum conhecimento básico em software

Profissionais de software - têm recebido pouco treinamento em novas técnicas para o desenvolvimento de software

Resistência a mudanças!

MITOS DO SOFTWAREMITOS DO SOFTWARE

– Muitas causas estão localizadas na mitologia que apareceu durante a história do desenvolvimento do Software

– Acabam por propagar desinformação e confusão

– Mitos - podem ser classificados como:

» Administrativos, do Cliente e do Profissional



Mitos de Software - Administrativos

Mito : Já temos um manual repleto de padrões e procedimentos para a construção de software. Isso oferecerá ao meu pessoal tudo o que eles precisam saber.

Realidade:

– O manual é realmente usado?

– Os profissionais sabem de sua existência?

– Ele reflete a práticas modernas?

– Ele é completo?

Mito : Meu pessoal tem ferramentas de desenvolvimento de software de última geração; afinal compramos para eles os mais novos computadores.

Realidade:

– É preciso mais do que computadores novos para se fazer um desenvolvimento de software de alta qualidade.

– Ferramentas CASE - de engenharia e software auxiliada por computador (Computer-Aided Software Engineering) ás vezes são mais importantes do que o hardware

Mito: Se nós estamos atrasados nos prazos, podemos adicionar mais programadores e tirar o atraso (conceito de hordas de mongóis).

Realidade:

– O desenvolvimento de software não é um processo mecânico igual à manufatura.

– Acrescentar pessoas em um projeto pode torna-lo ainda mais atrasado.

– Pessoas podem ser acrescentadas, mas de uma maneira planejada e bem coordenada!



Mitos de Software - Clientes

Mito: Uma declaração geral dos objetivos “en passant” é suficiente para se começar a escrever programas - podemos trabalhar os detalhes mais tarde.

Realidade:

– Uma definição inicial ruim é a causa principal de fracassos dos esforços de desenvolvimento de software.

– É fundamental uma descrição formal e detalhada do domínio da informação, função, desempenho, interfaces, restrições de projeto e critérios de validação.

Mito: Os requisitos de projeto modificam-se continuamente, mas as mudanças podem ser facilmente acomodadas, porque o software é flexível.

Realidade:

– Requisitos podem ser modificados, mas o impacto varia de acordo com o tempo que é introduzido (projeto e custo)

– Um mudança, quando solicitada tardiamente num projeto, pode ser mais do que a ordem de magnitude mais dispendiosa da mesma mudança solicitada nas fases iniciais

Custo

Definição Desenvolvimento Manutenção

1 X

1,5 a 6 X

60 a 100 X



Mitos de Software - Profissionais

Mito: Assim que escrever o programa e o colocar em funcionamento meu trabalho estará completo.

Realidade:

– Os dados da indústria apontam que entre 50 e 70% de todo esforço gasto num programa são despendidos depois que ele for entregue pela primeira vez ao cliente

Mito: Enquanto o programa não estiver "funcionando", eu não terei realmente maneira alguma de avaliar sua qualidade.

Realidade:

– Mecanismo (Revisão Técnica Formal) de garantia de qualidade de software deve ser aplicado desde o começo do projeto

– Revisões de software são um “filtro de qualidade” - descobre erros/defeitos

Desenvolvimento de Software - Desafios

Sofisticação do Software

Rápida Evolução do Hardware

Aumento expressivo da demanda

Má administração



SOLUÇÃO

– Reconhecer os problemas e causas

– Desmascarar os mitos do software

São os primeiros passos!

Aplicar Métodos e Técnicas para disciplinar o processo de Software

Engenharia de Software

Engenharia de Software

Definição - F. Bauer,1969

“O estabelecimento e uso de sólidos princípios de engenharia para obter de forma economica um software que seja confiável e que funcione eficientemente em máquinas reais”

Definição - IEEE

“A aplicação de uma abordagem sistemática, disciplinada e quantificável para o desenvolvimento, operação e manutenção do software e o estudo das abordagens para tal”

Definição - A Mayrhauser, 1990

“Trabalha Métodos, Técnicas e Ferramentas para desenvolver e manter Softwares - com alta qualidade para solução de problemas”



Engenharia de Software - Elementos fundamentais:

Métodos, Ferramentas e ProcedimentosMétodos, Ferramentas e Procedimentos

Possibilita ao gerente o controle do processo de desenvolvimento

Oferece ao profissional uma base para a construção de software de alta qualidade

FOCO NA QUALIDADE

PROCEDIMENTOS/PROCESSOS

MÉTODOS

FERRAMENTAS

MÉTODOSMÉTODOS:

Proporcionam os detalhes de “como fazer” para construir o software e envolvem um conjunto de tarefas amplo:

Planejamento e estimativa de projeto

Análise de requisitos de software

Projeto da estrutura de dados

Algoritmo de processamento

Codificação

Teste

Manutenção



FERRAMENTASFERRAMENTAS:

Fornecem suporte automatizado ou semi-automatizado aos métodos.

Ferramentas - para sustentar cada um dos métodos

CASE - Quando as ferramentas são integradas é estabelecido um sistema de suporte ao desenvolvimento de software chamado - Computer Aided Software Engineering

PROCEDIMENTOSPROCEDIMENTOS:

Estabelecem a ligação entre os Métodos e Ferramentas

Seqüência - que os métodos serão aplicados

Produtos (deliverables) - exigidos que sejam entregues

Controles - que ajudam assegurar a qualidade e coordenar as alterações

Marcos de referência - possibilitam administrar o progresso do software

ENGENHARIA DE SOFTWARE:ENGENHARIA DE SOFTWARE:

Compreende um conjunto de etapas que envolve:

MÉTODOS, FERRAMENTAS e PROCEDIMENTOS.

Essas etapas são citadas como CICLOS, MODELOS DE PROCESSO DECICLOS, MODELOS DE PROCESSO DE SOFTWARESOFTWARE



Modelos de Processo

–– Modelo Sequencial (ciclo de vida clássico)Modelo Sequencial (ciclo de vida clássico)

–– Modelo de PrototipaçãoModelo de Prototipação

–– Modelo RAD (Rapid Application Development)Modelo RAD (Rapid Application Development)

–– Modelos EvolutivosModelos Evolutivos

»» Modelo Incremental e EspiralModelo Incremental e Espiral

–– Modelo de Desenvolvimento ConcorrenteModelo de Desenvolvimento Concorrente

–– Modelo de Montagem de ComponentesModelo de Montagem de Componentes

–– Modelo de Métodos FormaisModelo de Métodos Formais

–– Técnicas de 4.a geraçãoTécnicas de 4.a geração

Qualidade no Processo

– Produto com Qualidade

» Requisitos - Processo de Construção - Produto - Atendimento aos Requisitos

– Software com Qualidade

» Requisitos - Processo de Desenvolvimento de Software - Software - Atendimento aos Requisitos

Ciclo de Vida de Software

Critérios para Escolha do Processo:

Adequação do modelo de processo à aplicação

Métodos e ferramentas que serão utilizados

Controles e produtos que precisam ser entregues

Características dos processos: Produtividade, Custos, Qualidade, etc.



Ciclo de Vida Clássico - Linear

Modelo mais antigo e o mais usado

Ciclo da engenharia convencional

Requer uma abordagem sistemática e seqüencial

Cada atividade é uma fase em separado.

A passagem entre fases é formal.

Engenharia deSistemas

Análise deRequisitos

Projeto

CodificaçãoTesteManutenção

ENGENHARIA DE SISTEMASENGENHARIA DE SISTEMAS

Sw faz parte de um sistema mais amplo

Coleta de requisitos

Visão essencial - sempre que software faz interface com outros elementos (Hw, pessoas e BDs)

Tarefas:– Identificação de necessidades dos usuários, executar a análise econômica e técnica, estabelecer restrições de prazo e custo, modelo arquitetônico

PRODUTO: Especificação do Sistema



ANÁLISE DE REQUISITOS DE SOFTWAREANÁLISE DE REQUISITOS DE SOFTWARE

Primeiro passo técnico do processo de engenharia de software

Atividade de descoberta, refinamento, modelagem e especificação

Escopo definido inicialmente é refinado e aperfeiçoado em detalhes

Métodos: Análise Estruturada, Análise Orientada a Objetos, Métodos Formais

PRODUTO: Especificação de Requisitos


Documents

Processamento Digital de Sinais, Engenharia de Software, Teoria da Informação e Codificação