Upload
projectmad
View
42
Download
3
Embed Size (px)
DESCRIPTION
electronica digital
Citation preview
7 1 IMPLEMENTACIN SECUENCIAL DE ALGORITMOS
7 .1ALGORITMOSElena ValderramaUniversidad Autnoma de Barcelona
7 .1Implementacinsecuencialdealgoritmos
Algunossistemassonsecuencialespornaturaleza,comoporejemplolossistemasqueincluyenunareferenciaimplcitaoexplcitaaintervalosdetiemposucesivos.
Algunosejemplos quehemosvisto Generadoresodetectoresdesecuencias, Control de secuencias de eventos Controldesecuenciasdeeventos.
Inclusoalgunosalgoritmosquenohacenningunareferenciaainstantesdetiempotambinpuedenimplementarseconcircuitossecuenciales.
2
1.Unprimerejemplo:Clculodelarazcuadrada7 .1
Ejemplo:Mtodoingenuoparacalcularlarazcuadradadeunnmeronaturalx
Algoritmo Raz cuadradaElloop calculatodaslasparejas[r,s =(r+1)2],parar =0,1,2,etc.
[(r+2)2 =((r+1)+1)2 =(r+1)2 +2(r+1)+1=s +2(r+1)+1]
Algoritmo Razcuadradar
1.Unprimerejemplo:Clculodelarazcuadrada7 .1
Controldelloop:s x
Algoritmo Raz cuadradaEjemplo:x =47
Algoritmo Razcuadradar
1.Unprimerejemplo:Clculodelarazcuadrada7 .1
Comentario:noesunbuenalgoritmo(propsitodidctico); Ndepasos=lapropiarazcuadrada;parax 2n:elnmerodepasos
i l l l d d d l d d 2n/2necesariosparacalcularlarazcuadradaesdelordende2n/2.
Algoritmo Razcuadradar
1.Unprimerejemplo:Clculodelarazcuadrada7 .1
2idea:DebemosmodificarelalgoritmoanteriorAlgoritmoequivalente:r
1.Unprimerejemplo:Clculodelarazcuadrada7 .1
Nmerodepasos:
Six
1.Unprimerejemplo:Clculodelarazcuadrada7 .1
IMPLEMENTACIN SECUENCIAL
r
1.Unprimerejemplo:Clculodelarazcuadrada7 .1
Sincronizacin:Cadaoperacinogrupodeoperacionesse
Memoria:Guardamosenlamemoriar yas.r
1.Unprimerejemplo:Clculodelarazcuadrada7 .1
r
1.Unprimerejemplo:Clculodelarazcuadrada7 .1
Six esunnmerodenbits 2.n bitsdememoria(n parar yn paras) 2n/2 estadosreales n entradas x 2n combinaciones
Circuitocombinacional Memoria
n entradasx 2 combinaciones hasta2n .2n/2 arcos n+1 salidas(root yend)
11
2.Implementacinalgortmicacombinacionalvs.i l
7 .1
Circuitos combinacionales
l l l (b d f d ) f
secuencial
Conceptualmentecualquieralgoritmo(biendefinido)quenotengareferenciastemporalespuedeimplementarsemedianteuncircuitocombinacionalconstruyendolatabladeverdadycalculandolasfuncionesbooleanascorrespondientes.
PERO .Muchasveceslatabladeverdadpuederesultarenorme
Hemosvistootraalternativa:Implementarelcircuitodirectamentedesdeelalgoritmo(verleccin3.4:Implementacindeestructurasdeprogramacin)
PERO .Inclusoenestecasolaimplementacinpuederequerirmuchosrecursos(vaselaprimeraimplementacinenestamismaleccin)
12
2.Implementacinalgortmicacombinacionalvs.i l
7 .1secuencial
Circuitos secuenciales
b l l f b l ( b l) d Tambincalculanfuncionesbooleanas(partecombinacional),peroadems Almacenandatos(memoria)y Asignandiferentesintervalosdetiempoadiferentesoperaciones,(sincronizacin)g p p
Comoresultado:Enelcasodelosloops,loscircuitossecuencialespermitensustituirNcomponentesidnticosporunnicocomponentequeejecutaiterativamentelasoperacionesincluidasenelcuerpodelloop
Loscomponentes(espacio)sereemplazanportiempo
13
2.Implementacinalgortmicacombinacionalvs.i l
7 .1
Estemtodonosloesvlidoparalasestructurasloop:
secuencial
Algoritmode4pasos:
1: X1
2.Implementacinalgortmicacombinacionalvs.i l
7 .1
1:X1
Pregunta 7 .1Elalgoritmosiguientecalculalarazcuadradapordefectodex.Six esunnmerode16bits.Culeselmnimonmerodeciclos,N, querequiereelalgoritmoparacalcularr =x1/2 ?
1. N =2532. N =5093. N =1.0214. N =2.045
16
3.Conclusiones7 .1
Losalgoritmospuedenimplementarseutilizandocircuitossecuenciales.
Paraello
Lamemoriaguardaelvalordelasvariables. Seasignanintervalosdetiempoalasoperaciones. Lapartecombinacionalejecutalasoperaciones.p j p
Arquitectura: Circuito combinacionalArquitectura: Circuitocombinacional
Memoria
17
RESUMEN7 .1
Implementacindealgoritmosmediantecircuitossecuenciales Ejemplos de implementaciones secuenciales.Ejemplosdeimplementacionessecuenciales. Comparacinentrelaimplementacincombinacionalylasecuencial(enaquellos
casosenlosqueambassonposibles)
18
7 MQUINAS DE ESTADOS FINITO7 .2Elena ValderramaUniversidad Autnoma de Barcelona
7 .2
Lasmquinasdeestadosfinitos(MEFoFSM:Finite State Machines)modelanloscircuitossecuenciales.Enestaleccinveremos:
1.DefinicindeMEF
2.Implementacionesp
3.DescripcinVHDLdeunaMEF
20
1.DefinicindeMEF7 .2
UnaMEFquedadefinidapor:
(estados de entrada): {combinaciones de valores de las seales de entradas} (estadosdeentrada):{combinacionesdevaloresdelassealesdeentradas} (estadosdesalida):{combinacionesdevaloresdelassealesdesalidas} S (estadosinternos):{combinacionesdevaloresdelamemoria(obiestables)}( ) { ( )} Dosfuncionesquedefinenelfuncionamientodelcircuito:
f:S x S (funcinestadosiguiente),asociaunestadointernoacadapar(estadointerno,estadodeentrada)
h:S x (funcindesalida),asociaunestadodesalidaacadapar(estadointerno,estadodeentrada))
21
7 .21.DefinicindeMEF
CualquiercircuitosecuencialpuedemodelarsepormediodeunaMEF.
Ejemplo:Contadorbinarioascendentede3bitsconunaentradaCE (Count_Enable)
={0,1}(CE =0o1), ={000,001,010,011,100,101,110,111}, S ={000,001,010,011,100,101,110,111},
f(estado_actual,estado_entrada):f(s,0)=sf (s,1)=s+1mod 8,s S,
h(estado_actual,estado_entrada): h (s,0)=h (s,1)=s,s S.22
7 .21.DefinicindeMEF
={0,1}(count_enable =0or1) ={000,001,010,011,100,101,110,111} S ={000,001,010,011,100,101,110,111} f(s,0)=s f (s,1)=s+1mod2n,s Sf( , ) f ( , ) , h (s,0)=h (s,1)=s,s S.
Matiz:EltrminoMEFseutilizasobretodocuandohablamosdemquinascuyoobjetivoescontrolar una secuencia de operaciones ms que implementar dichas operacionescontrolarunasecuenciadeoperacionesmsqueimplementardichasoperaciones.
23
2.Implementaciones:Lafrecuenciadereloj7 .2
2.1MquinadeMoore
h:S Elestadodesalidadependenicamentedelestadointernop
tSUinput:RetardoentreCKylassealesdeentradaestables
t : Tiempo de propagacin del circuito combinacional 1t1 :Tiempodepropagacindelcircuitocombinacional_1
t2 :Tiempodepropagacindelcircuitocombinacional_224
.272.Implementaciones:Lafrecuenciadereloj
Circuito Circuito
Periodomnimodereloj:
TCLK >max {tSUinput + t1,t2}
combinacional_1(t1)
combinacional_2(t2)estado
internoestadosiguiente
estadodeentrada(tSUinput)
estadodesalida
(clk)
clk
internal state
p
Frecuenciamximadereloj:
fCLK
7 .22.Implementaciones:Lafrecuenciadereloj
2.2MquinadeMealy
h:S x Elestadodesalidadependedelestadointernoydelestadodeentradap y
CircuitoCircuito
combinacional 2Circuitocombinacional_1
(t1)
combinacional_2(t2)
estadointerno
estadosiguiente
estadodeentrada
estadodesalida
tSUinput:RetardoentreCKylassealesdeentradaestablest : Tiempo de propagacin del circuito combinacional 1
entrada(tSUinput)
(clk)
t1 :Tiempodepropagacindelcircuitocombinacional_1t2 :Tiempodepropagacindelcircuitocombinacional_2
26
7 .22.Implementaciones:Lafrecuenciadereloj
Circuitobi i l 2Circuito
combinacional_1(t1)
combinacional_2(t2)
estadointerno
estadosiguiente
estadodeentrada(tSUi t)
estadodesalida
(clk)
Periodomnimodereloj:
TCLK >max {tSUinput + t1,tSUinput + t2}
(tSUinput)
Frecuenciamximadereloj:
fCLK
3.DescripcinVHDLdeMEFs7 .2
ArquitecturadeunaMEFtipoMoore :
Circuitocombinacional_1
Circuitocombinacional_2estado
internoestadosiguiente
estadodeentrada estadode
D PROCESOS
internosiguiente salida
(clk)
DosPROCESOS: Funcinestadosiguiente+sincronizacin, Funcindesalida
28
7 .23.DescripcinVHDLdeMEFs
Packagemy_fsm includes library ieee;i td l i 1164 ll definitionoftheset ofinternal states;
forexample:type stateis (S0,S1,S2,);
number N of input signals
use ieee.std_logic_1164.all;use work.my_fsm.all;entity MooreFsm isport ( numberNofinputsignals,
numberMofoutputsignals,
port (clk,reset:in std_logic;x:in std_logic_vector(N1downto 0);y:out std logic vector(M1downto 0)
definitionofthenextstatefunctionFandoftheoutputfunctionH.
y _ g _ ( ));end MooreFsm;
29
7 .23.DescripcinVHDLdeMEFs
architecturebehaviorofMooreFsm isF Hsignalcurrent_state:state;
begin
F Hestadointerno
estadosiguienteX
Y
CLK
output_state:process(current_state)begin
H( t t t )
next_state:process(reset,clk)beginif t '1' th t t t S0 y
7 .23.DescripcinVHDLdeMEFsFyHpuedendefinirseenlapropiaarquitecturadelaentity.Ejemplo:DefinimosexplcitamenteFyHparacadaestadomedianteuncase
next_state:process(reset,clk)beginifreset='1'thencurrent_state < instrucciones que ejecutan current state ;whenS1=>< instruccionesqueejecutancurrent_state ;whenS2=>< instruccionesqueejecutancurrent_state ;end case;end case;
end if;end processnext_state; 31
7 .23.DescripcinVHDLdeMEFs
output_state:process(current_state)beginbegin
case current_state iswhenS0=> ;whenS2=>
7 .23.DescripcinVHDLdeMEFsEjemplo:Contador binario ascendente de3bitconentradacount_enabletypestateis (0,1,2,3,4,5,6,7);input:count_enable;outputy: 3bitvector;
next_state:process(reset,clk)beginifreset='1'thencurrent_state
7 .23.DescripcinVHDLdeMEFs
output_state:process(current_state)begin
casecurrent_state iswhen0=>yy y y< 010 ;when3=>yyyyy
EnladescripcinVHDLdelprocesonext_state deuncontadorbidireccionalde2bits,enelquehemos
PREGUNTA 7 .2
next state:process(reset,clk)
definidoeltipostate iguala0,1,2y3,dosports deentrada,count_enable yup_down (up_down=0cuentahaciaarriba;up_down=1cuentahaciaabajo),sehapedidopartedelcdigo:
_ p ( , )beginif reset='1'then current_state
Qu porcin de cdigo habra que insertar
PREGUNTA 7 .2
1)when0=>ifcount_enable =1then
ifup_down =0thencurrent_state parteacompletarwhen 1=>when 2=>
thencurrent_state ifcount_enable =1thenifup_down =0then
current_state
RESUMEN7 .2
DefinicindelasMquinasdeEstadosFinitos(MEFs oFSMs) Estudiado la frecuencia mxima de funcionamiento de una MSFEstudiadolafrecuenciamximadefuncionamientodeunaMSF HemosvistounmodelogenricodedescripcinVHDLdeunaMEFcondosprocesos
concurrentes,unoquecomputalafuncinestadosiguienteyotroquecomputala
funcindesalida.
37
7 .2
38
7 3 EJEMPLOS DE MQUINAS DE ESTADOS FINITOS
7 .3Elena ValderramaUniversidad Autnoma de Barcelona
7 .31.Temporizadorprogramable(timer)
Entradas:start,reference (ondacuadrada),time (enterodenbits)Salida:done.
Especificacin:
40
7 .31.Temporizadorprogramable(timer)Especificacinformal:
loopdone
7 .31.Temporizadorprogramable(timer)Implementacin:
loopdone
7 .31.Temporizadorprogramable(timer)
MEF:Moore
CE
reference
state operation done 0 00 11 00 1 2 11 0 3 00 0 4 00 0 5 00 05 00 06 01 0
43
7 .31.Temporizadorprogramable(timer)
output_state:process(current_state)b ibegincasecurrent_state iswhen0to1=>operation
7 .31.Temporizadorprogramable(timer)Comentarios
1. UnaaplicacinimportantedelasMEFsonloscircuitosdecontrol(p.e.laUnidaddeC t l d l P d )ControldelProcesador)
2. Hemosconstruidoeltemporizadorcomodosgrandesbloques
Un circuito de clculo (unidad de proceso, data path)Uncircuitode clculo (unidaddeproceso,datapath) Unmquinadeestadosfinitos(unidaddecontrol).
Estaesunaarquitecturamuypotente,yeslabasedeloscircuitosqueimplementanl i d f di (M i d E d Al i )algoritmosdeunaformamsomenosdirecta(Mquinas de Estado Algortmicas).
3. Apesardeello,siempreesposibledescribirelcircuitocompleto(VHDL),sinexplicitarestaparticinenunidaddecontrolyunidaddeproceso
46
7 .31.Temporizadorprogramable(timer)
entity timerisport (
main:process(reset,clk)beginif reset='1'then cs
2.Detectordemovimiento7 .3
Otrotipodeaplicacin:Deteccindesecuencias.
Objetomvilcondossensorespticosquesemuevefrenteaunacintafijaconreasgrisesyblancas.Lossensoresgeneranunasalida:
1sidetectanunazonagris,g , 0sidetectanunazonablanca,
48
7 .32.DetectordemovimientoMovimientoaladerecha:00,01,11,10,00,01,
49
7 .32.DetectordemovimientoMovimientoaladerecha:00,01,11,10,00,01,
50
7 .32.DetectordemovimientoMovimientoaladerecha:00,01,11,10,00,01,
51
7 .32.DetectordemovimientoMovimientoaladerecha:00,01,11,10,00,01,
52
7 .32.DetectordemovimientoMovimientoaladerecha:00,01,11,10,00,01,
53
7 .32.DetectordemovimientoMovimientoaladerecha:00,01,11,10,00,01,
54
7 .32.DetectordemovimientoMovimientoalaizquierda:00,10,11,01,00,10,
55
7 .32.DetectordemovimientoMovimientoalaizquierda:00,10,11,01,00,10,
56
7 .32.DetectordemovimientoMovimientoalaizquierda:00,10,11,01,00,10,
57
7 .32.DetectordemovimientoMovimientoalaizquierda:00,10,11,01,00,10,
58
7 .32.DetectordemovimientoMquinadeMealy:generaunasalida
z =0silasecuenciadeentradaes,00,01,11,10,00,01, z = 1 si la secuencia de entrada es 00 10 11 01 00 10 z =1silasecuenciadeentradaes,00,10,11,01,00,10,
59
7 .32.DetectordemovimientoMquinadeMealy:generaunasalida
z =0silasecuenciadeentradaes,00,01,11,10,00,01,(secuencia de estados: A B C D A B C D )(secuenciadeestados:ABCDABCD)
z =1silasecuenciadeentradaes,00,10,11,01,00,10,(secuenciadeestados:DCBADCBA) Estado x1 x0 Estado siguiente z
A
x1 x0 : 00
01
10
11
A/0 B/0 A/1 D/1
A 0 0 A 0 A 0 1 B 0 A 1 0 A 1 A 1 1 D 1 B 0 0 B 1 B 0 1 B 0
1 0 A 1AB C D
A/0 B/0 A/1 D/1B/1 B/0 A/1 C/0 B/1 C/1 D/0 C/0 A/0 C/1 D/0 D/1
B 1 0 A 1B 1 1 C 0 C 0 0 B 1 C 0 1 C 1 C 1 0 D 0 C 1 1 C 0 D 0 0 A 0D 0 0 A 0D 0 1 C 1 D 1 0 D 0 D 1 1 D 1
60
7 .32.Detectordemovimientooutput_state:process (cs,x1,x0)begincase cs is
A
x1 x0 : 00
01
10
11
A/0 B/0 A/1 D/1
case cs iswhen A=>zzzz
PREGUNTA7 .3
AlaMEFqueacabamosdeconstruir(fsm eneldibujo)lequeremosconectarunasegundaMEF(?eneldibujo)quedetectelaposicindelobjetomvil,en mltiplos de W (W=anchura de las bandas blancas
1)loopif x1+x0=1then ifz=0then position
RESUMEN7 .3
DosejemplosdedescripcinVHDLdeMEFs:Untemporizadorprogramableyundetectordemovimiento.
ParticindecircuitosenunaUnidaddeProceso(oDataPath)yunaUnidaddeControl.ArquitecturadelasMquinasAlgortmicas.
Apesardedichaparticin,ambasunidadespuedendescribirseenunnicoprocesoA pesar de dicha particin, ambas unidades pueden describirse en un nico procesoVHDL.
64