Sistemas e Sinais (LEIC)

Sistemas e Sinais (LEIC)Sistemas e Sinais (LEIC)Carlos CardeiraCarlos Cardeira

Sistemas e SinaisSistemas e Sinais

As Engenharias (Electrotécnica, As Engenharias (Electrotécnica, Mecânica, etc) estão a perder o Mecânica, etc) estão a perder o contacto com o mundo físico.contacto com o mundo físico.

Microelectromecânica o que é ? Microelectromecânica o que é ? Engª Mecânica ? Electrotécnica ? Engª Mecânica ? Electrotécnica ? Processamento de Sinal ? Processamento de Sinal ? Matemática ? Redes ?Matemática ? Redes ?

Onde existem sistemas ?Onde existem sistemas ?

Sistemas aeronáuticosSistemas aeronáuticos Mecânica estruturalMecânica estrutural Sistemas eléctricosSistemas eléctricos Futuros e Opções Futuros e Opções ……

CircuitosCircuitos

Os circuitos são o coração de um Os circuitos são o coração de um Engenheiro (especialmente Engenheiro (especialmente electrotécnico)electrotécnico)

Mas hoje já existem técnicas Mas hoje já existem técnicas analíticas que evitam o desenho de analíticas que evitam o desenho de circuitoscircuitos

Circuitos em si passaram a ser uma Circuitos em si passaram a ser uma área de especializaçãoárea de especialização

SinaisSinais

Tradicionalmente, um sinal é uma Tradicionalmente, um sinal é uma tensão que varia ao longo do tensão que varia ao longo do tempo.tempo.

Actualmente é mais provável que Actualmente é mais provável que seja uma sequência de bits enviada seja uma sequência de bits enviada pela internet através de TCP/IPpela internet através de TCP/IP

EstadoEstado

O estado de um sistema poderia O estado de um sistema poderia ser bem determinado pelas ser bem determinado pelas variáveis de uma equação variáveis de uma equação diferencialdiferencial

Agora é mais provável que seja um Agora é mais provável que seja um conjunto de registos de um conjunto de registos de um computador.computador.

SistemaSistema

Um sistema era razoavelmente Um sistema era razoavelmente bem modelizado por uma função de bem modelizado por uma função de tranferência linear e invariante no tranferência linear e invariante no tempo.tempo.

Agora, parece ser mais Agora, parece ser mais adequadamente descrito através adequadamente descrito através de uma máquina de Turing !de uma máquina de Turing !

Sistemas e SinaisSistemas e Sinais Sinais, Sistemas e FunçõesSinais, Sistemas e Funções Noção de EstadoNoção de Estado Não Determinismo e EquivalênciaNão Determinismo e Equivalência Composição de Máquinas de EstadoComposição de Máquinas de Estado Sistemas LinearesSistemas Lineares Resposta de Sistemas LinearesResposta de Sistemas Lineares Sistemas HíbridosSistemas Híbridos Resposta em frequênciaResposta em frequência FiltragemFiltragem ConvoluçãoConvolução Transformadas de FourierTransformadas de Fourier AmostragemAmostragem

Sinais e SistemasSinais e Sistemas

Os sinais transportam informaçãoOs sinais transportam informação Os sistemas transformam sinaisOs sistemas transformam sinais

SinaisSinais

SomSom ImagemImagem Sequência de comandosSequência de comandos Lista de nomesLista de nomes

……

FunçõesFunções

SistemasSistemas

Realçar uma imagemRealçar uma imagem Amplificar um somAmplificar um som ……

Funções !Funções !

Matematicamente …Matematicamente …

Um sinal é uma função que mapeia Um sinal é uma função que mapeia um domínio (frequentemente um domínio (frequentemente tempo ou espaço) num tempo ou espaço) num contradomínio (frequentemente contradomínio (frequentemente uma medida física como pressão, uma medida física como pressão, intensidade de luz …)intensidade de luz …)

Um sistema é uma função que Um sistema é uma função que mapeia sinais (entradas) em sinais mapeia sinais (entradas) em sinais (saídas). São funções de funções.(saídas). São funções de funções.

SinaisSinais

Sinais são funções que transportam Sinais são funções que transportam informação:informação: Radio e TV chegam-nos através de Radio e TV chegam-nos através de

sinais que são ondas sinais que são ondas electromagnéticaselectromagnéticas

Imagens são sinais que transportam Imagens são sinais que transportam informação através de pontos de informação através de pontos de intensidade e cor variáveisintensidade e cor variáveis

SensoresSensores

Sensores de pressão, temperatura, Sensores de pressão, temperatura, velocidade, convertem estas velocidade, convertem estas grandezas físicas em tensão (sinais)grandezas físicas em tensão (sinais)

FunçõesFunções

Sinais e Sistemas serão encarados como Sinais e Sistemas serão encarados como funções.funções.

Cada função é sempre constituída por:Cada função é sempre constituída por: Um nomeUm nome Um domínioUm domínio Um contradomínioUm contradomínio A regra que converte cada elemento do A regra que converte cada elemento do

domínio em um e só um elemento do domínio em um e só um elemento do contradomíniocontradomínio

(ver apêndice A do livro de referência)(ver apêndice A do livro de referência)

Exemplo:Exemplo:

Nome: CubeNome: Cube Domínio: ReaisDomínio: Reais Contradomínio: Contradomínio:

ReaisReais Regra: Regra:

Sinais de Audio: Domínio e Sinais de Audio: Domínio e ContradomínioContradomínio

Sinusoide puraSinusoide pura

Soma de SinusoidesSoma de Sinusoides

Onda sonoraOnda sonora

A pressão não pode assumir valores A pressão não pode assumir valores negativos.negativos.

Na figura aparecem valores Na figura aparecem valores negativos porque normalmente se negativos porque normalmente se subtrai a pressão atmosférica (10subtrai a pressão atmosférica (105 5

N/mN/m22) uma vez que os nossos ) uma vez que os nossos ouvidos não “ouvem” a pressão ouvidos não “ouvem” a pressão atmosféricaatmosférica

ExemploExemplo

x=0:pi/8192:2*pix=0:pi/8192:2*pi sound(sin(1000*x))sound(sin(1000*x)) sound(sin(10000*x))sound(sin(10000*x)) sound(sin(1000*x)+sin(10000*x))sound(sin(1000*x)+sin(10000*x))

Representação discretaRepresentação discreta

Mas num computador não se guardam Mas num computador não se guardam sinais contínuos (numa cassete sim, sinais contínuos (numa cassete sim, embora com distorção…)embora com distorção…)

É usual guardá-los em palavras de 16 bit É usual guardá-los em palavras de 16 bit gravadas a intervalos regularesgravadas a intervalos regulares

Com 16 bit é possível distinguir 65536 Com 16 bit é possível distinguir 65536 níveis de intensidade diferentesníveis de intensidade diferentes

Guardando esses valores a um ritmo de Guardando esses valores a um ritmo de 44 Khz obtém-se uma boa representação 44 Khz obtém-se uma boa representação do sinal contínuo (som) originaldo sinal contínuo (som) original

Representação DiscretaRepresentação Discreta

Representação Discreta Representação Discreta (Exemplo)(Exemplo)

0 0.5 1 1.5 2 2.5 3

x 105

-0.8

-0.6

-0.4

-0.2

0

0.2

0.4

0.6

0.8Bocelli 44.1 Khz

Canal Esquerdo

Canal Direito

Se amostrado a 4.41 Khz:Se amostrado a 4.41 Khz:

[Bocelli44, SampleFreq, Bits]=wavread('bocelli');siz=size(Bocelli44);ratio=10for i=ratio:ratio:siz(1) Bocelli4(i/ratio) = (Bocelli44(i, 1) + Bocelli44(i, 2))/2; iend

Bocelli amostrado a 4.41 Bocelli amostrado a 4.41 KhzKhz

0 0.5 1 1.5 2 2.5 3

x 104

-0.6

-0.4

-0.2

0

0.2

0.4

0.6

0.8Bocelli 4.41 Khz

ComparaçãoComparação

2 4 6 8 10 12 14

-0.1

-0.05

0

0.05

0.1

0.15Bocelli 4.41 Khz

20 40 60 80 100 120 140-0.2

-0.15

-0.1

-0.05

0

0.05

0.1

0.15Bocelli 44.1 Khz

Canal Esquerdo

Canal Direito

ImagensImagens

Foto a preto e brancoFoto a preto e branco

Exemplo de imagemExemplo de imagem

Imagens a coresImagens a cores

Olhos e ouvidosOlhos e ouvidos

O ouvido consegue distinguir sons O ouvido consegue distinguir sons de frequências diferentes quando de frequências diferentes quando somadossomados

O olho não consegue distinguir cores O olho não consegue distinguir cores diferentes quando somadasdiferentes quando somadas

O ouvido pode ser modelizado por O ouvido pode ser modelizado por um sistema linear enquanto que o um sistema linear enquanto que o olho nãoolho não

Filme: Domínio e Filme: Domínio e ContradomínioContradomínio

Filme: Domínio e Filme: Domínio e ContradomínioContradomínio

Alternativamente:Alternativamente:

Sequência de imagens forma Sequência de imagens forma um filmeum filme

Sequência de imagens forma Sequência de imagens forma um filmeum filme

Olhos e ouvidosOlhos e ouvidos

Uma amostragem de 30 Hz é Uma amostragem de 30 Hz é suficiente para reconstruir um filmesuficiente para reconstruir um filme

Uma amostragem de 8 KHz ainda é Uma amostragem de 8 KHz ainda é insuficiente para reconstituir um sominsuficiente para reconstituir um som

Conclusão: não fossem os volumes de Conclusão: não fossem os volumes de informação a tratar serem bem informação a tratar serem bem diferentes, dir-se-ia que somos muito diferentes, dir-se-ia que somos muito melhor a “ouvir” do que a “ver”.melhor a “ouvir” do que a “ver”.

Qual a representação mais Qual a representação mais favorável ?favorável ?

Video:TempoDiscretoVideo:TempoDiscreto → → ImagensImagens

DiscreteTime={0, 1/30, 2/30, …}DiscreteTime={0, 1/30, 2/30, …}

Video(t) Video(t) Imagens Imagens

Video(t)(i,j) Video(t)(i,j) Intensidade Intensidade33

(é o pixel i,j da frame t)(é o pixel i,j da frame t)

Qual a representaçao mais Qual a representaçao mais favorávelfavorável

AltVideo: TempoDiscreto x Linhas x AltVideo: TempoDiscreto x Linhas x Colunas Colunas →→ Intensidade Intensidade33

AltVideo(t,i,j) é a intensidade do pixel i, j AltVideo(t,i,j) é a intensidade do pixel i, j da frame tda frame t

AltVideo(t,i,j) = Video(t)(i,j)AltVideo(t,i,j) = Video(t)(i,j)

A representação mais favorável A representação mais favorável dependerá do que pretendemos caso a dependerá do que pretendemos caso a caso. Depende do Engenho …caso. Depende do Engenho …

Sinais que representam Sinais que representam atributos físicosatributos físicos

Posição de um Posição de um aviãoavião

Posição e Posição e velocidade de um velocidade de um aviãoavião

Sinais que representam Sinais que representam atributos físicosatributos físicos

Posição de um Posição de um pêndulopêndulo

Sinais compostos por Sinais compostos por eventoseventos

Sequência de eventos que ocorre durante Sequência de eventos que ocorre durante a realização de uma chamada telefónicaa realização de uma chamada telefónica

Sequência de comandos para uma Sequência de comandos para uma impressãoimpressão

Domínio e ContradomínioDomínio e Contradomínio

Exemplo: ConduçãoExemplo: Condução

Condução: IndicesCondução: Indices→ → EventosEventos

Índices = {0,1,2,…,N}Índices = {0,1,2,…,N}

Eventos: {Ligar, Acelerar, Travar, 1ª, Eventos: {Ligar, Acelerar, Travar, 1ª, 2ª, 3ª, 4ª, 5ª, Marcha-Atrás, Virar 2ª, 3ª, 4ª, 5ª, Marcha-Atrás, Virar Esquerda, Virar Direita, Parar}Esquerda, Virar Direita, Parar}

Domínio e ContradomínioDomínio e Contradomínio

Exemplo: Entrada e Saída de Pessoas na Exemplo: Entrada e Saída de Pessoas na salasala

Porta_de_entrada: IndicesPorta_de_entrada: Indices→ → EventosEventosÍndices = {0,1,2,…,N}Índices = {0,1,2,…,N}Eventos: {Entrada, Saída}Eventos: {Entrada, Saída}

Exemplo: Número de Pessoas na salaExemplo: Número de Pessoas na salaPessoas_na_sala: Índices Pessoas_na_sala: Índices → → InteirosInteiros

Os índices representam uma sucessão ou Os índices representam uma sucessão ou ordem de eventos e não o tempoordem de eventos e não o tempo

SISTEMASSISTEMAS

SistemaEntradas (u) Saídas (y)

Sinais

DTMFDTMF

DTMF:{0,1,2,3,…,9,*,#}DTMF:{0,1,2,3,…,9,*,#}→→soundsound

SISTEMAS: SISTEMAS: Pessoas_na_salaPessoas_na_sala

Sala(1 p. início)

u=(e,e,e,s,e,…)

Pessoas_na_sala:[Índices→{entrada,saída}] →[Índices →N.Pessoas_na_sala]

y=(2,3,4,3,4,…)

Sistema : FunçãoSistema : Função

O sistema “Pessoas na sala” pode ser O sistema “Pessoas na sala” pode ser descrito através da funcão:descrito através da funcão: y(0)=1+1(u(0)==e)-1(u(0)==s)=2y(0)=1+1(u(0)==e)-1(u(0)==s)=2 ……

(Sistemas deste tipo têm a ver com o (Sistemas deste tipo têm a ver com o dimensionamento de buffers)dimensionamento de buffers)

0)(1,1)(1

0,1,:1

))((1))((11)(0

falsoverdadeiro

falsoverdadeiro

skuekunyn

k

Sistema ContínuoSistema Contínuo

Velocidades:[0,5]Velocidades:[0,5]→→Reais, Reais, Posição:Posição:[0,5][0,5]→→ReaisReais

S:VelocidadesS:Velocidades→ → PosiçãoPosição

Sy(0)= pos. ini.

u Velocidades y Posição

t

duytytuS

tsVelocidadeu

0

)()0()())((

5,0,

Sistemas que dependem do Sistemas que dependem do passadopassado

Nestes sistemas, o sinal de saída Nestes sistemas, o sinal de saída depende não apenas do valor do depende não apenas do valor do sinal de entrada nesse instante, sinal de entrada nesse instante, mas de todo o passado do sistemamas de todo o passado do sistema

n

k

skuekuny0

))((1))((11)(

t

duytytuS0

)()0()())((

Nota:Nota:

S(u)(t) faz sentido porque S(u) é S(u)(t) faz sentido porque S(u) é uma função de t. uma função de t.

S(u(t)) não faz sentido porque u(t) é S(u(t)) não faz sentido porque u(t) é apenas um número e a função S apenas um número e a função S depende de todo o passado de u(t)depende de todo o passado de u(t)

t

duytytuS0

)()0()())((

Nota:Nota:

Neste sistema, y(t) só depende do valor Neste sistema, y(t) só depende do valor de u(t) no mesmo instante.de u(t) no mesmo instante.

Neste caso, S(u)(t) e S(u(t)) já fazem Neste caso, S(u)(t) e S(u(t)) já fazem sentido.sentido.

tutytuSalst 2,Re

Composição de sistemasComposição de sistemas

S1v y

y(0)

S2a v

v(0)

dsdavy

dssvytytaSS

posiçãoaceleraçãoSS

t s

t

0 0

021

21

00

0

:

Máquinas de estadosMáquinas de estados

Sinais de entrada e de saída são Sinais de entrada e de saída são eventoseventos

Representa-se graficamente a Representa-se graficamente a dependencia do passadodependencia do passado

Reconhecedor de Reconhecedor de SequênciasSequências

Máquina de estadosMáquina de estados


Tem um número de círculos igual Tem um número de círculos igual ao número de estadosao número de estados

De cada estado saem tantas setas De cada estado saem tantas setas quantos os diferentes símbolos de quantos os diferentes símbolos de entradaentrada

Cada seta tem o símbolo de Cada seta tem o símbolo de entrada / valor da saída que produz entrada / valor da saída que produz caso o sistema esteja nesse estado caso o sistema esteja nesse estado e receba essa entradae receba essa entrada


No caso do reconhecedor:No caso do reconhecedor: Update (init, ‘0’) = (a, f)Update (init, ‘0’) = (a, f) Update (a, ‘1’) = (init, f)Update (a, ‘1’) = (init, f) ……

Máquina de EstadosMáquina de Estados

ReconhecedorReconhecedor

O reconhecedor de sequências O reconhecedor de sequências anterior detecta uma sequência de anterior detecta uma sequência de 3 símbolos ‘0’ seguidos3 símbolos ‘0’ seguidos

Aceita um alfabeto maior que o Aceita um alfabeto maior que o primeiro reconhecedor apresentadoprimeiro reconhecedor apresentado

Reconhecedor com 4 Reconhecedor com 4 estadosestados

Reconhecedor com 4 Reconhecedor com 4 estadosestados

Embora tenha mais estados este Embora tenha mais estados este reconhecedor produz exactamente reconhecedor produz exactamente o mesmo resultadoo mesmo resultado

Apenas os nomes dos estados são Apenas os nomes dos estados são mais intuitivosmais intuitivos

Definição formal de máquina Definição formal de máquina de estadosde estados

StateMachine = (States, Inputs, Outputs, update, initialState) States é o espaço de estados Inputs é o conjunto de símbolos de entrada

(alfabeto de entrada) Outputs é o conjunto dos símbolos de saída

(alfabeto de saída) initialState ∈ States é o estado inicial update: States x Inputs → States x Outputs é

a função que mapeia os sinais de entrada nos sinais de saída

Entradas e Sinais de Entradas e Sinais de entradaentrada

Não confundir Entradas com Sinais Não confundir Entradas com Sinais de entrada.de entrada.

Um sinal de entrada é uma Um sinal de entrada é uma sequência de elementos do sequência de elementos do conjunto de entradasconjunto de entradas

Analogamente em relação às Analogamente em relação às saídas.saídas.

ReconhecedorReconhecedor

Máquinas de estadoMáquinas de estado

Por vezes é conveniente separar a função update em duas: update = (nextState, output), nextState: States x Inputs → States output: States x Inputs → Outputs

Ou: update(s(n), x(n)) = (s(n+1), y(n)) nextState(s(n), x(n)) = s(n+1) output(s(n), x(n)) = y(n)

Funcionamento da MEFuncionamento da ME S = (States, Inputs, Outputs, update, initialState) InputSignals = [Nats0 → Inputs] OutputSignals = [Nats0 → Outputs]

Um sinal de entrada x = (x(0), x(1), … , x(n), …) provoca mudanças de estado s: Nats0 → States e mudanças nas saídas y: Nats0 → Outputs

s(0) = initState, and n ≥ 0, e recursivamente teremos (s(n+1), y(n)) = update (s(n), x(n))

Assim S define um sistema F: InputSignals → OutputSignals

ExemploExemplo

Reconhecedor: InputSignals = [Nats0 → {0,1}] OutputSignals = [Nats0 → {t,f}] F: ∀x ∈ InputSignals, ∀ n ∈ Nats0 y(n) = F(x)(n)

= t, se (x(n-2), x(n-1)), x(0)) = (0,0,0) = f, se não

Símbolo ‘Absent’ Símbolo ‘Absent’

absent ∈ Inputs and absent ∈ Outputs

s ∈ States, update(s, absent) = (s, absent)

Reconhecedor ModificadoReconhecedor Modificado

Reconhecedor ModificadoReconhecedor Modificado

O reconhecedor modificado produz O reconhecedor modificado produz apenas a saída “true” quando apenas a saída “true” quando encontra a sequência e não produz encontra a sequência e não produz nada (absent) enquanto não nada (absent) enquanto não encontrar a sequência.encontrar a sequência.

Simplificações (else e absent Simplificações (else e absent implícitos)implícitos)

GuardasGuardas

Em cada estado, as guardas devem Em cada estado, as guardas devem ser disjuntasser disjuntas

Diz-me que se trata de uma Diz-me que se trata de uma máquina determinística porque a máquina determinística porque a cada entrada só pode corresponder cada entrada só pode corresponder um estado seguinte.um estado seguinte.

A união de todas as guardas em A união de todas as guardas em cada estado deve ser igual ao cada estado deve ser igual ao conjunto das entradasconjunto das entradas

Máquina de Estados - Máquina de Estados - TabelaTabela

Se o número de entradas e de Se o número de entradas e de estados for finito, a função update estados for finito, a função update pode ser dada por uma tabelapode ser dada por uma tabela

Exemplo : ParquímetroExemplo : Parquímetro

ParquímetroParquímetro

InputSequence = coin25, tick 20, coin5, tick 15, ... StateResponse = 0, 25, 24, ..., 6, 5, 10, 9, 8, ..., 2, 1, 05

OutputSequence = expired, safe, safe, ..., safe, safe, safe, safe, safe, ..., safe, safe, expired5

Formas de representar Formas de representar máquinas de estadosmáquinas de estados

Modelo de conjuntos / funçõesModelo de conjuntos / funções Diagrama de estados/transiçõesDiagrama de estados/transições TabelaTabela

As duas últimas formas não As duas últimas formas não permitem representar máquinas permitem representar máquinas infinitasinfinitas

Exemplo: Gravador de Exemplo: Gravador de ChamadasChamadas

Uma empresa quer especificar um Uma empresa quer especificar um gravador de chamadas.gravador de chamadas.

Normalmente especifica em Normalmente especifica em linguagem natural (português), que linguagem natural (português), que pode ser ambígua.pode ser ambígua.

Se especificasse em Máquinas de Se especificasse em Máquinas de Estados não haveria ambiguidade.Estados não haveria ambiguidade.

Especificação e Especificação e ImplementaçãoImplementação

Normalmente especifica-se as Normalmente especifica-se as relações entre as entradas e saídas, relações entre as entradas e saídas, só que esse conjunto pode ser só que esse conjunto pode ser infinito.infinito.

Passar de máquinas de estados a Passar de máquinas de estados a uma implementação é cada vez uma implementação é cada vez mais automáticomais automático

Gravador de ChamadasGravador de Chamadas


Entrada: ring, ring, ring, end greeting , end message, …Estado: idle, count1, count2, play greeting, recording , …Saída: absent, absent, answer, record, recorded, …


Se alguém atender, a máquina vai Se alguém atender, a máquina vai para idle.para idle.

As máquinas normais continuam a As máquinas normais continuam a gravar porque não reconhecem o gravar porque não reconhecem o evento “levantar do auscultador”.evento “levantar do auscultador”.

Funções como gravar, etc, não são Funções como gravar, etc, não são feitas pela máquina de estados. feitas pela máquina de estados. Alguém se encarrega disso.Alguém se encarrega disso.

Exemplo: DelayExemplo: Delay

Delay unitárioDelay unitário

Delay 2Delay 2

Delay nDelay n

Delay 2 implica 4 estadosDelay 2 implica 4 estados Delay n implica 2Delay n implica 2nn estados estados

Se ligarmos dois delays e os Se ligarmos dois delays e os combinarmos o número total de combinarmos o número total de estados é quanto ?estados é quanto ?

Atenção que o estado passa a ser a Atenção que o estado passa a ser a combinação dos estados.combinação dos estados.

Máquinas de Estados Não Máquinas de Estados Não DeterminísticasDeterminísticas

São máquinas em que a uma entrada pode São máquinas em que a uma entrada pode corresponder mais do que um estado ou corresponder mais do que um estado ou saída.saída.

Exemplo: parquímetro em que se reduz o Exemplo: parquímetro em que se reduz o número de estados. Fica não número de estados. Fica não determinística mas bastante simplificada.determinística mas bastante simplificada.

No entanto a máquina não determinística No entanto a máquina não determinística deve manter o mesmo comportamento da deve manter o mesmo comportamento da máquina determinística.máquina determinística.

Máquinas não Máquinas não DeterminísticasDeterminísticas

As guardas já não são disjuntas.As guardas já não são disjuntas.

A um sinal de entrada podem corresponder A um sinal de entrada podem corresponder muitos sinais de saída. Exemplo: x(n)= 0, 1, 0, 1, muitos sinais de saída. Exemplo: x(n)= 0, 1, 0, 1, 0, 10, 1

Transição de estadosTransição de estados

Se a máquina for não Se a máquina for não determinística, pode haver uma determinística, pode haver uma probabilidade de ir para um ou para probabilidade de ir para um ou para outro estado.outro estado.

Se assim for estamos perante Se assim for estamos perante “Cadeias de Markov”.“Cadeias de Markov”.

No nosso caso, o não determínismo No nosso caso, o não determínismo pode ser usado para situações não pode ser usado para situações não modeladas.modeladas.

UpdateUpdate

Em máquinas não determinísticas, a Em máquinas não determinísticas, a função update não gera um estado mas função update não gera um estado mas um conjunto de estados. Não deixa de um conjunto de estados. Não deixa de ser uma função.ser uma função.

Estados PossíveisEstados Possíveis

possibleUpdates(a, 0) = { (a, 0) }possibleUpdates(a, 1) = { (b, 1) }

possibleUpdates(b, 0) = { (a, 0), (b, 1) } possibleUpdates(b, 1) = { (b, 1) }

FunçãoFunção

Possibleupdate continua a ser uma Possibleupdate continua a ser uma função, porque gera sempre um função, porque gera sempre um elemento do contradomínio.elemento do contradomínio.

Em contrapartida, a relação entre Em contrapartida, a relação entre os sinais de entrada e os sinais de os sinais de entrada e os sinais de saída deixa de ser uma função.saída deixa de ser uma função.

Funções e Funções e ComportamentosComportamentos

Uma máquina determinística pode ser definida por uma função.

Uma máquina não determinística define um comportamento

Behaviors = {(x,y) | y is a possible output signal corresponding to x} ⊂ InputSignals x OutputSignals

Parquímetro Não Parquímetro Não DeterminísticoDeterminístico

ComparaçãoComparação

A máquina não determinística é mais A máquina não determinística é mais simples.simples.

No entanto, as saídas possíveis da No entanto, as saídas possíveis da máquina não determinística, incluem máquina não determinística, incluem as da máquina deterministica.as da máquina deterministica.

A máquina não determinística pode A máquina não determinística pode fazer o que a máquina determinística fazer o que a máquina determinística faz e possívelmente algo mais.faz e possívelmente algo mais.

AbstracçãoAbstracção

A máquina ND esconde detalhes da A máquina ND esconde detalhes da máquina Dmáquina D

As duas máquinas não são As duas máquinas não são equivalentes.equivalentes.

A máquina ND é uma abstracção da A máquina ND é uma abstracção da máquina Dmáquina D

Interesse das Máq. NDInteresse das Máq. ND

Por outro lado, se se provar que a Por outro lado, se se provar que a Máquina não Determinística não pode ter Máquina não Determinística não pode ter um certo comportamento, então, um certo comportamento, então, garantidamente, a Máquina Determinística garantidamente, a Máquina Determinística também não o poderá ter.também não o poderá ter.

Se a ND for segura, a D também o será, Se a ND for segura, a D também o será, admitindo que, por segura se entende que admitindo que, por segura se entende que determinados estados não sucederão. determinados estados não sucederão. Exemplos: Deadlock. Livelock, etc.Exemplos: Deadlock. Livelock, etc.

EquivalênciaEquivalência

Máquina Máquina determinísticdeterminísticaa

Máquina não Máquina não determinísticdeterminísticaa

Equivalência e SimulaçãoEquivalência e Simulação Ambas respondem com (1, 0, 1, 0 …) à Ambas respondem com (1, 0, 1, 0 …) à

entrada (1, 1, 1, 1 …)entrada (1, 1, 1, 1 …) Consideram-se máquinas bisimilares Consideram-se máquinas bisimilares

(mutuamente similares) porque uma máquina (mutuamente similares) porque uma máquina simula a outra e reciprocamente.simula a outra e reciprocamente.

Considera-se que uma máquina simula outra Considera-se que uma máquina simula outra quando consegue fazer o mesmo que a outra e quando consegue fazer o mesmo que a outra e talvez mais.talvez mais.

A máquina não determinística para o A máquina não determinística para o parquímetro simulava a máquina parquímetro simulava a máquina determinística do mesmo parquímetro.determinística do mesmo parquímetro.

A e B são mutuamente similares se A simula B A e B são mutuamente similares se A simula B e B simula Ae B simula A

SimulaçãoSimulação

Uma máquina simula outra se conseguir Uma máquina simula outra se conseguir ganhar o jogo da igualdade (matching ganhar o jogo da igualdade (matching game)game)

Regras do jogo da igualdade:Regras do jogo da igualdade: Inicialmente ambas as máquinas estão Inicialmente ambas as máquinas estão

prontas no seu estado inicial.prontas no seu estado inicial. Apresenta-se uma entrada a ambas. B Apresenta-se uma entrada a ambas. B

simula A se for capaz de produzir a mesma simula A se for capaz de produzir a mesma saída sempre.saída sempre.

Se B não for capaz, perdeu o jogo e não Se B não for capaz, perdeu o jogo e não simula Asimula A

Simulação (formal)Simulação (formal) Considere as seguintes máquinas não Considere as seguintes máquinas não

determinísticasdeterminísticas

Simulação (formal)Simulação (formal)

Ilustração da SimulaçãoIlustração da Simulação

TeoremaTeorema

Se B simula ASe B simula A ComportamentosComportamentosBB ככ

ComportamentosComportamentosAA

exemploexemplo

ComportamentosComportamentosBB == ComportamentosComportamentosAA

Mas B não simula A !Mas B não simula A !

Combinações de MECombinações de ME

Tendo um sistema descrito por uma Tendo um sistema descrito por uma máquina Amáquina A

Um sistema descrito pela máquina BUm sistema descrito pela máquina B Se as saídas de A forem ligadas a B Se as saídas de A forem ligadas a B

deve ser possível conhecer o sistema deve ser possível conhecer o sistema final com base nos seus componentes.final com base nos seus componentes.

Se a saída realimentar para a entrada, Se a saída realimentar para a entrada, também deverá ser possível fazer a também deverá ser possível fazer a mesma análise.mesma análise.

Hipótese de Hipótese de funcionamentofuncionamento

Quando uma entrada chega ao sistema Quando uma entrada chega ao sistema ela é imediatamente consumida e é ela é imediatamente consumida e é gerada a saída correspondente.gerada a saída correspondente.

Essa saída é consumida no mesmo Essa saída é consumida no mesmo instante pelo sistema a jusante.instante pelo sistema a jusante.

Cada componente só reage uma vez ao Cada componente só reage uma vez ao sinal de entrada.sinal de entrada.

Se houver realimentação, o sinal de Se houver realimentação, o sinal de saída aparece à entrada no mesmo saída aparece à entrada no mesmo instante.instante.

Trivial: Composição Trivial: Composição paralelaparalela

Composição paralelaComposição paralela

Composição paralelaComposição paralela

Composição em cascataComposição em cascata

Composição em cascataComposição em cascata

Composição em cascata: Composição em cascata: exemploexemplo

Composição em cascata: Composição em cascata: exemploexemplo

No exemplo anterior, os estados No exemplo anterior, os estados (1,0) e (0,1) não são alcançáveis.(1,0) e (0,1) não são alcançáveis.

Numa composição em cascata, Numa composição em cascata, podem existir estados não podem existir estados não alcancáveis.alcancáveis.

Composição: Produto de Composição: Produto de Entradas/SaídasEntradas/Saídas


Como no caso do atendedor, há sinais Como no caso do atendedor, há sinais que podem ter proveniências que podem ter proveniências diferentes e saídas que podem ter diferentes e saídas que podem ter destinos diferentes.destinos diferentes.

O sinal de play e o de record podem O sinal de play e o de record podem ser destinados a máquinas diferentes.ser destinados a máquinas diferentes.

O Sinal de Chamada (ring) pode O Sinal de Chamada (ring) pode provir de uma entrada diferente do provir de uma entrada diferente do sinal de fim de chamada (end sinal de fim de chamada (end message)message)


Composição: Produto de Composição: Produto de E/SE/S

Por vezes, há entradas específicas para Por vezes, há entradas específicas para determinados elementos do alfabeto.determinados elementos do alfabeto.

FeedbackFeedback

O Problema consiste em calcular a função update.

Ponto FixoPonto Fixo

A função update define-se através A função update define-se através de iterações que conduzam ao de iterações que conduzam ao “ponto fixo”.“ponto fixo”.

O que é o ponto fixo (Fixed O que é o ponto fixo (Fixed Point)Point)



Ponto Fixo: HipótesesPonto Fixo: Hipóteses

Não há soluções: significa que não há Não há soluções: significa que não há sinais que possam colocar o sistema a sinais que possam colocar o sistema a funcionar. O sistema não funciona.funcionar. O sistema não funciona.

Há mais do que uma solução: significa Há mais do que uma solução: significa que o problema não é “bem formado” e que o problema não é “bem formado” e não pode ser resolvido (not well formed)não pode ser resolvido (not well formed)

Há uma solução única: significa que o Há uma solução única: significa que o sistema é “bem formado” (well formed)sistema é “bem formado” (well formed)

Ponto Fixo: ExemploPonto Fixo: Exemplo

X=Y=ReaisX=Y=Reais f(x)=2x-1f(x)=2x-1 Solução do ponto fixo:Solução do ponto fixo:

X=f(x)X=f(x) 2x-1 = x2x-1 = x Tem uma solução única: x = 1Tem uma solução única: x = 1 Se f(x) = xSe f(x) = x22 o sistema tem duas soluções o sistema tem duas soluções

(seria no máximo, uma máquina não (seria no máximo, uma máquina não determinística)determinística)

Se f(x) = x+1 não tem soluçãoSe f(x) = x+1 não tem solução

Realimentação sem entradas Realimentação sem entradas externas: exemplo 1externas: exemplo 1

Sistema “bem formado”Sistema “bem formado” Se estiver no estado 1 e a entrada for Se estiver no estado 1 e a entrada for

verdadeiro, o sistema não tem solução.verdadeiro, o sistema não tem solução. Se estiver no estado 1 e a entrada for falsa, ele Se estiver no estado 1 e a entrada for falsa, ele

consome a entrada e passa ao estado 2 consome a entrada e passa ao estado 2 gerando a saída falsa que é igual à entrada.gerando a saída falsa que é igual à entrada.

Se estiver no estado 2 e a entrada for falsa, o Se estiver no estado 2 e a entrada for falsa, o sistema não tem solução.sistema não tem solução.

Se estiver no estado 2 e a entrada for Se estiver no estado 2 e a entrada for verdadeira, ele consome a entrada e passa ao verdadeira, ele consome a entrada e passa ao estado 1 gerando a saída verdadeira que é estado 1 gerando a saída verdadeira que é igual à entrada.igual à entrada.

O sistema é bem formado porque para cada O sistema é bem formado porque para cada estado há uma única solução x=f(x)estado há uma única solução x=f(x)

Realimentação sem entradas Realimentação sem entradas externasexternas

Sistema “bem formado”Sistema “bem formado”

O sistema não tinha entradas.O sistema não tinha entradas. A entrada react é criada A entrada react é criada

artificialmente para representar que artificialmente para representar que quando surge a máquina pode quando surge a máquina pode avançar para o estado seguinte avançar para o estado seguinte (correr a sua função update).(correr a sua função update).

As duas máquinas são equivalentes As duas máquinas são equivalentes porque quando a entrada react surge, porque quando a entrada react surge, as únicas hipóteses de evolução são as únicas hipóteses de evolução são as indicadas na máquina inferior.as indicadas na máquina inferior.


Sistema “mal formado” (not Sistema “mal formado” (not well-formed)well-formed)

Se estiver no estado 1 e a entrada for Se estiver no estado 1 e a entrada for verdadeiro, o sistema não tem solução.verdadeiro, o sistema não tem solução.

Se estiver no estado 1 e a entrada for falsa, ele Se estiver no estado 1 e a entrada for falsa, ele consome a entrada e passa ao estado 2 consome a entrada e passa ao estado 2 gerando a saída falsa que é igual à entrada.gerando a saída falsa que é igual à entrada.

Para o estado 1 há portanto uma solução única Para o estado 1 há portanto uma solução única e o sistema está no bom caminho para ser e o sistema está no bom caminho para ser considerado “bem-formado”considerado “bem-formado”

Se estiver no estado 2 e a entrada for Se estiver no estado 2 e a entrada for verdadeira ou falsa, a saída gerada é diferente verdadeira ou falsa, a saída gerada é diferente da entrada.da entrada.

O sistema é mal formado porque há um estado O sistema é mal formado porque há um estado em que não há solução para x=f(x)em que não há solução para x=f(x)


Sistema “mal formado” (not Sistema “mal formado” (not well-formed)well-formed)

Se estiver no estado 1 e a entrada for Se estiver no estado 1 e a entrada for verdadeiro, a máquina consome a verdadeiro, a máquina consome a entrada e gera uma saída igual. entrada e gera uma saída igual.

Se estiver no estado 1 e a entrada for Se estiver no estado 1 e a entrada for falsa, ele consome a entrada e passa ao falsa, ele consome a entrada e passa ao estado 2 gerando a saída falsa que é estado 2 gerando a saída falsa que é igual à entrada.igual à entrada.

O sistema é mal formado porque há um O sistema é mal formado porque há um estado em que há mais do que uma estado em que há mais do que uma única solução x=f(x).única solução x=f(x).

Máquinas em que a saída Máquinas em que a saída depende apenas do estadodepende apenas do estado


Nestes casos, qualquer que seja a Nestes casos, qualquer que seja a entrada, a saída é sempre a mesma entrada, a saída é sempre a mesma para cada estado.para cada estado.

output(s, y) = y terá sempre uma output(s, y) = y terá sempre uma única solução que corresponderá à única solução que corresponderá à guarda cuja entrada for igual a yguarda cuja entrada for igual a y

Desta forma, estas máquinas são Desta forma, estas máquinas são sempre “bem formadas”.sempre “bem formadas”.

Interesse das máquinas “bem Interesse das máquinas “bem formadas”formadas”

Máquina B bem formada (saída depende do estado)

yzw

Se uma máquina é Bem formada (as saídas dependem apenas do estado), então sistema é bem formado

A B C


Suponhamos que a máquina B está num Suponhamos que a máquina B está num certo estado e gera a saída y.certo estado e gera a saída y.

A máquina C (que pode não ser bem A máquina C (que pode não ser bem formada), gera z.formada), gera z.

A máquina A gera w.A máquina A gera w. Mas w será uma das guardas desse Mas w será uma das guardas desse

estado da máquina B. Então ela estado da máquina B. Então ela continuará a gerar y.continuará a gerar y.

O sistema todo é bem formado porque O sistema todo é bem formado porque um dos seus elementos o era.um dos seus elementos o era.

DelayDelay

A máquina delay tem saídas A máquina delay tem saídas determinadas pelo estado. É bem determinadas pelo estado. É bem formada.formada.

Bem formado ou mal formado Bem formado ou mal formado ? Método geral? Método geral

Bem formado ou mal formado Bem formado ou mal formado ? Método geral? Método geral

Começa-se com uma saída alguresComeça-se com uma saída algures Para cada máquinaPara cada máquina

Se a saída puder ser determinada, produzi-laSe a saída puder ser determinada, produzi-la Se a mudança de estado puder ser Se a mudança de estado puder ser

determinada, fazê-ladeterminada, fazê-la Repetir até dar a voltaRepetir até dar a volta

Se todas as saídas estão determinadas – Se todas as saídas estão determinadas – Bem formadoBem formado

Se alguns sinais estiverem indefinidos – Mal Se alguns sinais estiverem indefinidos – Mal formadoformado

Bem formado ou mal formado Bem formado ou mal formado ? Exemplo? Exemplo

Bem formado ou mal formado Bem formado ou mal formado ? Exemplo? Exemplo

Começar com o estado AComeçar com o estado A O estado A gera sempre a saída y2=1O estado A gera sempre a saída y2=1 Como y2 é realimentada, teremos Como y2 é realimentada, teremos

update (a, 1) = (b, (1,1)) O estado B gera sempre a saída y2=0O estado B gera sempre a saída y2=0 Como y2 é realimentada, teremos Como y2 é realimentada, teremos

update (b, 0) = (b, (0,0))

Realimentação com Realimentação com entradasentradas

Realimentação com Realimentação com entradasentradas

A máquina tem dois portos de saída, outputM1 e outputM2. Escolher um estado s.

∀x1 ∈ Inputs1, resolver: outputM2 (s, (x1, y2)) = y2; se y2 for única, então nextState (s, x1) = (nextStateM(s, (x1, y2)) output(s, x1) = outputM1(x1, y2)

Passará a haver uma equação de ponto Passará a haver uma equação de ponto fixo para cada valor da entrada.fixo para cada valor da entrada.

Sumário dos Caps. I a IVSumário dos Caps. I a IV

Vimos até agora:Vimos até agora: Sinais que são funções com domínio e Sinais que são funções com domínio e

contradomínio: exemplo: sons, contradomínio: exemplo: sons, imagensimagens

Sistemas que transformam sinais, são Sistemas que transformam sinais, são funções de funções: exemplo: filtros, funções de funções: exemplo: filtros, máquinas de faxmáquinas de fax

Máquinas de estado (determinísticas Máquinas de estado (determinísticas ou não) que descrevem a evolução dos ou não) que descrevem a evolução dos sistemas.sistemas.

Documents

Sistemas e Sinais (LEIC)