Trädvy Permalänk
Medlem
Plats
Stockholm
Registrerad
Mar 2011

Tillståndsdiagram

Hej!

Jag tänkte försöka göra den här uppgiften:

och först rita upp ett tillståndsdiagram men är väldigt dålig på det. Skulle någon kunna förklara för mig hur man ska tänka när man ritar upp det? Vet hur ett tillståndsdiagram fungerar med starttillstånd, sen pilar till nästa tillstånd eller om den loopar till sig själv. Men inte hur man ska rita upp ett utifrån en viss uppgift /information man får. Vore tacksam för all hjälp!

Trädvy Permalänk
Medlem
Registrerad
Apr 2012

För 20 år sedan skulle jag kanske kunnat hjälpa dig men inte nu mera. Du måste väl ha tillgång till någon litteratur som du kan ha hjälp av?

Intel i7-3770K@4,5GHz 1,275V - ASRock P67 Pro3 REV B3 - Corsair Vengeance Pro DDR3 2133MHz 2x8GB - MSI GTX 1080 Gaming X - Samsung 840 EVO 120GB - WD Caviar Black 6TB - Seagate SV35 2TB - Noctua NH-C12P SE14 - LG DVD+-RW - Seasonic Focus+ Gold 750FX - Antec One Hundred - Dell 25" UltraSharp U2515H

Trädvy Permalänk
Hedersmedlem
Plats
Linköping
Registrerad
Apr 2004

Fundera på vad som är det väsentliga med kretsen. Vad krävs för att utsignalen skall bli 0 (efter att ha varit 1) till exempel? Försök rita en minimal graf.

Trädvy Permalänk
Medlem
Plats
Stockholm
Registrerad
Mar 2011
Skrivet av Elgot:

Fundera på vad som är det väsentliga med kretsen. Vad krävs för att utsignalen skall bli 0 (efter att ha varit 1) till exempel? Försök rita en minimal graf.

Är inte helt med på vad det väsentliga är med kretsen. Men OR i uppgiften betyder väl en OR-grinden eller syftar de på något annat? Det som krävs för att utsignalen ska bli 0 efter dne har varit 1 är att det har varit minst 4 ettor tidigare.

Trädvy Permalänk
Hedersmedlem
Plats
Linköping
Registrerad
Apr 2004
Skrivet av mhj:

Det som krävs för att utsignalen ska bli 0 efter dne har varit 1 är att det har varit minst 4 ettor tidigare.

Nja, inte riktigt, men det är denna typ av "minne" man behöver. Hur kan man illustrera det med en graf? Och ja, det är det vanliga OR (se även exempelsekvensen).

Trädvy Permalänk
Medlem
Plats
Stockholm
Registrerad
Mar 2011
Skrivet av Elgot:

Nja, inte riktigt, men det är denna typ av "minne" man behöver. Hur kan man illustrera det med en graf? Och ja, det är det vanliga OR (se även exempelsekvensen).

Såhär kanske?

Känns inte rätt men en OR ger ut en etta om någon eler båda är 1. Så den blir bara 0 om insignalerna är 00.

Trädvy Permalänk
Hedersmedlem
Plats
Linköping
Registrerad
Apr 2004
Skrivet av mhj:

Såhär kanske?

Testa med några insignaler, till exempel:

  • Om x är konstant 1 skall utsignalen också (efter en stund i alla fall) vara det

  • Om x är 1 måste den vara 0 fyra gånger på rad efteråt för att utsignalen skall bli 0

Varför har du till exempel det där långa hoppet?

Tänk också på att man tappar information om hur många gånger något har hänt om man hoppar tillbaka till samma tillstånd som man var i.

Trädvy Permalänk
Medlem
Plats
Stockholm
Registrerad
Mar 2011
Skrivet av Elgot:

Testa med några insignaler, till exempel:

  • Om x är konstant 1 skall utsignalen också (efter en stund i alla fall) vara det

  • Om x är 1 måste den vara 0 fyra gånger på rad efteråt för att utsignalen skall bli 0

Varför har du till exempel det där långa hoppet?

Tänk också på att man tappar information om hur många gånger något har hänt om man hoppar tillbaka till samma tillstånd som man var i.

Okej men vet inte riktigt hur jag ska fixa i tillståndsdiagrammet så att om x är 1 måste den vara 0 fyra gånger på rad. För kommer just nu bara till starttillståndet(har dragit en pil från 01 och en från 10 till startillståndet med en nolla på pilarna). Och där stod den still för den kommer inte ihåg tidigare nollor.

Trädvy Permalänk
Hedersmedlem
Plats
Linköping
Registrerad
Apr 2004
Skrivet av mhj:

Okej men vet inte riktigt hur jag ska fixa i tillståndsdiagrammet så att om x är 1 måste den vara 0 fyra gånger på rad. För kommer just nu bara till starttillståndet(har dragit en pil från 01 och en från 10 till startillståndet med en nolla på pilarna). Och där stod den still för den kommer inte ihåg tidigare nollor.

Koncentrera dig först på att rita något som efter fyra nollor ger utsignalen 0 (man kan inte göra på så många sätt om man konstaterar att cirkulära hopp gör att man tappar räkningen). Detaljerna kan man förhoppningsvis fixa sedan.

Trädvy Permalänk
Medlem
Plats
Stockholm
Registrerad
Mar 2011
Skrivet av Elgot:

Koncentrera dig först på att rita något som efter fyra nollor ger utsignalen 0 (man kan inte göra på så många sätt om man konstaterar att cirkulära hopp gör att man tappar räkningen). Detaljerna kan man förhoppningsvis fixa sedan.

Alright då ritade jag upp såhär:

Jag ritade först upp nollorna så att den skickar ut en nolla när den kommer tillbaks till 00 igen från 11 för då har det precis blivit 4 nollor. Sen går 00 till sig självt för att om du är på 0 och får in en nolla ska du stå kvar och skicka ut ett nolla. Sen ritade jag upp ettorna, är inte säker på om man får ha två pilar från samma tillstånd till ett nytt tillstånd dit båda pilarna gåt, och då kommer den skicka ut 1 så länge det är en etta någonstans.

Trädvy Permalänk
Hedersmedlem
Plats
Linköping
Registrerad
Apr 2004
Skrivet av mhj:

är inte säker på om man får ha två pilar från samma tillstånd till ett nytt tillstånd dit båda pilarna gåt

Det går bra, men däremot får man inte ha fler än två pilar från varje tillstånd. Hur vet man till exempel om man skall stå kvar i 00 eller hoppa till 01 om x = 0?

Om man står i 11 och får x=0 nu kommer man också hoppa direkt till 00 (med u = 0 (alltså utan många nollor i rad först)). Man måste se till att omslaget från u=1 till u=0 alltid blir fördröjt, och att processen kan avbrytas om en etta kommer in. Om man får tre nollor och en etta måste man alltså få fyra nya nollor i rad för att ge u = 0.

Trädvy Permalänk
Medlem
Plats
Stockholm
Registrerad
Mar 2011
Skrivet av Elgot:

Det går bra, men däremot får man inte ha fler än två pilar från varje tillstånd. Hur vet man till exempel om man skall stå kvar i 00 eller hoppa till 01 om x = 0?

Om man står i 11 och får x=0 nu kommer man också hoppa direkt till 00 (med u = 0 (alltså utan många nollor i rad först)). Man måste se till att omslaget från u=1 till u=0 alltid blir fördröjt, och att processen kan avbrytas om en etta kommer in. Om man får tre nollor och en etta måste man alltså få fyra nya nollor i rad för att ge u = 0.

Kommer inte riktigt på hur man kan fixa så det blir fördröjt.

Trädvy Permalänk
Hedersmedlem
Plats
Linköping
Registrerad
Apr 2004
Skrivet av mhj:

Kommer inte riktigt på hur man kan fixa så det blir fördröjt.

Det enda man kan göra är att hoppa mellan tillstånd...

Trädvy Permalänk
Medlem
Plats
Stockholm
Registrerad
Mar 2011
Skrivet av Elgot:

Det enda man kan göra är att hoppa mellan tillstånd...

Aa men då borde man kanske hoppa från 11 till 01 om man får in en nolla vid 11, och sen går den runt ett varv till men frågan är hur den ska veta att den ska hoppa till 00 efter just 4 nollor.

Trädvy Permalänk
Hedersmedlem
Plats
Linköping
Registrerad
Apr 2004
Skrivet av mhj:

Aa men då borde man kanske hoppa från 11 till 01 om man får in en nolla vid 11, och sen går den runt ett varv till men frågan är hur den ska veta att den ska hoppa till 00 efter just 4 nollor.

Nja, man skall kunna få in ett godtyckligt antal ettor utan att utsignalen blir 0 förrän fyra nollor i rad påträffas.

Nedräkningen nollställs varje gång en etta kommer in.

Dold text
Trädvy Permalänk
Medlem
Plats
Stockholm
Registrerad
Mar 2011
Skrivet av Elgot:

Nja, man skall kunna få in ett godtyckligt antal ettor utan att utsignalen blir 0 förrän fyra nollor i rad påträffas.

Nedräkningen nollställs varje gång en etta kommer in.

Dold text

Aa är med på att den ska skicka ut ett så länge det kommer in en etta, och den ska skicka ut en nolla om det varit 4 nollor tidigare. Men vet inte hur jag ska få ihop det med tillståndsdiagrammet.

Trädvy Permalänk
Hedersmedlem
Plats
Linköping
Registrerad
Apr 2004
Skrivet av mhj:

Aa är med på att den ska skicka ut ett så länge det kommer in en etta, och den ska skicka ut en nolla om det varit 4 nollor tidigare. Men vet inte hur jag ska få ihop det med tillståndsdiagrammet.

Se det som att räkna nollor och börja om vid x=1.

Trädvy Permalänk
Medlem
Plats
Stockholm
Registrerad
Mar 2011
Skrivet av Elgot:

Se det som att räkna nollor och börja om vid x=1.

Menar du alltså att den ska gå runt och räkna nollor? Men hur ska utsignalen bli 1 då hela tiden förutom efter 4 nollor, då den ska bli 0? Då måste man ju ha en pil med x=0 från tillståndet 11 till tillståndet 00 men det skulle jag inte ha sa du. Då borde jag kanske inte ha ettor som går till sig själv på tillstånden 01, 10 och 11.

Trädvy Permalänk
Hedersmedlem
Plats
Linköping
Registrerad
Apr 2004
Skrivet av mhj:

Menar du alltså att den ska gå runt och räkna nollor?

Ingen har väl sagt att den nödvändigtvis måste "gå runt"?

Skrivet av mhj:

Men hur ska utsignalen bli 1 då hela tiden förutom efter 4 nollor, då den ska bli 0? Då måste man ju ha en pil med x=0 från tillståndet 11 till tillståndet 00 men det skulle jag inte ha sa du. Då borde jag kanske inte ha ettor som går till sig själv på tillstånden 01, 10 och 11.

Nej, huvudsaken är att nedräkningen fungerar. Lås inte fast dig vid någon speciell konstruktion utan börja med att göra något som ger u=0 efter fyra nollor på rad. Sedan kan man börja tänka på övriga detaljer.

Trädvy Permalänk
Medlem
Plats
Stockholm
Registrerad
Mar 2011
Skrivet av Elgot:

Ingen har väl sagt att den nödvändigtvis måste "gå runt"?

Nej, huvudsaken är att nedräkningen fungerar. Lås inte fast dig vid någon speciell konstruktion utan börja med att göra något som ger u=0 efter fyra nollor på rad. Sedan kan man börja tänka på övriga detaljer.

Nä men den måste väl gå runt om den ska komma ihåg vad tidigare var(om det var en nolla eller en etta). Om jag börjar om ritar upp först så den skickar ut en nolla efter fyra nollor blir det såhär:

Eller nej ser ett fel och det är att den skickar ut en etta efter en nolla, en etta efter två nollor osv. Hur kan man lösa det? För den ska ju inte skicka ut en nolla eller en etta vid tillstånd 01, 10 och 11 nu. Den ska inte heller skicka ut don't care.

Trädvy Permalänk
Hedersmedlem
Plats
Linköping
Registrerad
Apr 2004
Skrivet av mhj:

Nä men den måste väl gå runt om den ska komma ihåg vad tidigare var(om det var en nolla eller en etta).

Fast är det verkligen så noga att hålla reda på vad just till exempel det förra värdet var? Det man måste detektera är fyra (eller fler) nollor på rad.

Skrivet av mhj:

Om jag börjar om ritar upp först så den skickar ut en nolla efter fyra nollor blir det såhär:
http://i61.tinypic.com/jact5l.jpg

Du behöver som sagt inte låsa dig vid att det skall se ut ungefär sådär. Inte ens att det skall vara just fyra tillstånd (eller ja, det kan man kanske lista ut av problembeskrivningen) eller ett Moore-nät.

Trädvy Permalänk
Medlem
Plats
Stockholm
Registrerad
Mar 2011
Skrivet av Elgot:

Fast är det verkligen så noga att hålla reda på vad just till exempel det förra värdet var? Det man måste detektera är fyra (eller fler) nollor på rad.

Du behöver som sagt inte låsa dig vid att det skall se ut ungefär sådär. Inte ens att det skall vara just fyra tillstånd (eller ja, det kan man kanske lista ut av problembeskrivningen) eller ett Moore-nät.

Ja, man måste väl gå runt för du kan väl inte loopa 0 till sig själv för då kan den skriva ut en nolla innan fyra nollor kommit.

Har jag ritat ett Moore-nät? Har aldrig kommit ihåg skillnaden mellan mealy och moore tillståndsdiagram för det är något med vad pilarna och tillstånden är.

Trädvy Permalänk
Hedersmedlem
Plats
Linköping
Registrerad
Apr 2004
Skrivet av mhj:

Ja, man måste väl gå runt för du kan väl inte loopa 0 till sig själv för då kan den skriva ut en nolla innan fyra nollor kommit.

Om det har kommit fyra nollor skulle man ju till exempel kunna hoppa tillbaka till samma om ännu fler kommer, och på liknande sätt spelar det ju inte så stor roll om man får en, två eller 14 ettor efter varandra.

Skrivet av mhj:

Har jag ritat ett Moore-nät? Har aldrig kommit ihåg skillnaden mellan mealy och moore tillståndsdiagram för det är något med vad pilarna och tillstånden är.

Ett Moore-nät har en utsignal per tillstånd medan ett Mealy-nät har en utsignal per pil. Det kan löna sig att testa båda varianterna.

Man kan också som sagt tänka på några sekvenser som nätet skall klara:
0, 0, 0, ..., 0 -> 0, 0, ..., 0
1, 1, 1, ..., 1 -> 1, 1, ..., 1
0, 1, 0,..., 1, 0 -> 1, 1, ..., 1
1, 0, 0, 0, 1, 0, 0, 0, ... -> 1, 1, 1, ..., 1

Trädvy Permalänk
Medlem
Plats
Stockholm
Registrerad
Mar 2011
Skrivet av Elgot:

Om det har kommit fyra nollor skulle man ju till exempel kunna hoppa tillbaka till samma om ännu fler kommer, och på liknande sätt spelar det ju inte så stor roll om man får en, två eller 14 ettor efter varandra.

Ett Moore-nät har en utsignal per tillstånd medan ett Mealy-nät har en utsignal per pil. Det kan löna sig att testa båda varianterna.

Man kan också som sagt tänka på några sekvenser som nätet skall klara:
0, 0, 0, ..., 0 -> 0, 0, ..., 0
1, 1, 1, ..., 1 -> 1, 1, ..., 1
0, 1, 0,..., 1, 0 -> 1, 1, ..., 1
1, 0, 0, 0, 1, 0, 0, 0, ... -> 1, 1, 1, ..., 1

Okej hänger med på vad den ska göra men inte hur man ska få ihop tillståndsdiagrammet för det. Det enda som jag verkar göra rätt med tillståndsdiagrammet är fyra nollor runt som jag postade ovan där det går en 0 till 01, sen en 0:a till 10 osv och sen skickar den ut 0 vid 00. Men sen vet jag inte riktigt hur man ska få ihop det.

Trädvy Permalänk
Hedersmedlem
Plats
Linköping
Registrerad
Apr 2004
Skrivet av mhj:

Okej hänger med på vad den ska göra men inte hur man ska få ihop tillståndsdiagrammet för det. Det enda som jag verkar göra rätt med tillståndsdiagrammet är fyra nollor runt som jag postade ovan där det går en 0 till 01, sen en 0:a till 10 osv och sen skickar den ut 0 vid 00. Men sen vet jag inte riktigt hur man ska få ihop det.

Testa en mealy-lösning istället. Och tänk på att man får hoppa hur man vill mellan tillstånden.