DW EditSeite anzeigenÄltere VersionenLinks hierherAlles aus-/einklappenNach oben Diese Seite ist nicht editierbar. Sie können den Quelltext sehen, jedoch nicht verändern. Kontaktieren Sie den Administrator, wenn Sie glauben, dass hier ein Fehler vorliegt. CKG Editor ====== 6. Sequential Logic ====== "I Know What You Did Last Cycle" ===== 6.1 State Diagram, State Transition Diagram ===== ==== 6.1.1 Motivation ==== The diagrams of different states are well known from physics for example the state diagram (or better: phase diagram) of water, where its three states are: solid ice, liquid water and gaseous steam. The possible state transitions are due to temperature increase or decrease. In <imgref pic01> image (1) the states of water are shown on the temperature axis. When only the state transistions are relevant, the states are simplified to a circle, showing the state name and behaviour. The transitions are depict as arrows, where the needed condititon is written onto (See <imgref pic01> image (2) ). This diagram is called **state transition diagram**. <WRAP> <imgcaption pic01| States of Water> </imgcaption> {{drawio>SDwater}} </WRAP> For matter not only the dimension "temperature" is important, but also the "pressure". The full phase diagram is shown in <imgref pic02> image (1). By this, another variable is available and more transistions. These can be drawn into the state transition diagram (<imgref pic02> image (2)). <WRAP> <imgcaption pic02| States of Water> </imgcaption> {{drawio>SDwater2}} </WRAP> ==== 6.1.2 Simple logic Example ==== In German, often one has to pay for entering the toilet. An example of such a entrance control system is shown in <imgref pic03>. At this (artificial) example, one can pay either 50ct or 1€. \\ Once paid, the turnstile will release and one can enter. Once the turnstile was pushed the entrance is closed again. <WRAP> <imgcaption pic03| Entrance Control for Toilets> </imgcaption> {{drawio>EntranceFee}} </WRAP> The <imgref pic04> the state transition diagram is drawn. * The two states are that (1) the turnstile is opened and one is able to go through and (2) the turnstile is closed and one cannot enter anymore. * The transitions are given by the done actions: one can either insert a coin or push on the turnstile. Important here are some additional considerations: * For the state transition diagram one has to **look for all possible transitions**. So, also pushing a closed turnstile or inserting more coins have to taken into account. * A state transition diagram is not complete without a **legend** and without an **beginning/reset point**. The reset point is given by an arrow with "reset" written onto it <WRAP> <imgcaption pic04| State Transition Diagramm of the Entrance Control for Toilets> </imgcaption> {{drawio>STDEntranceFee}} </WRAP> Out of this state transition diagram one can create a table-like representation, see <imgref pic05>. <WRAP> <imgcaption pic05| State Transition Diagramm of the Entrance Control for Toilets> </imgcaption> {{drawio>STDEntranceFee2}} </WRAP> the inputs, outputs and states have to be encoded into binary, in order to investigate this table a bit more. How the binary value is connected to the outputs does not matter. We will choose the following coding: * Encoding of the states: turnstile closed ≙ $Q=0$, turnstile opened ≙ $Q=1$, * Encoding of the inputs: no coin inserted ≙ $Xc=0$, coin inserted ≙ $Xc=1$, turnstile not pushed ≙ $Xp=0$, turnstile pushed ≙ $Xp=1$, * Encoding of the outputs: disallow entrance ≙ $Y=0$, allow entrance ≙ $Y=1$, This table is shown in <imgref pic06> and is called **state transition table**. <WRAP> <imgcaption pic06| State Transition Diagramm of the Entrance Control for Toilets> </imgcaption> {{drawio>STDRSFF}} </WRAP> Interestingly, the logic circuit for this state transition table was already part of the course: it is the RS flip-flop! When looking deeper onto the table in <imgref pic06> one can substitute $Xc$ with $S$ (as in Set) and $Xp$ with $R$ (as in Reset) to directly get the truthtable of the RS flip flop. ==== 6.1.3 First Terminology ==== Sequential logic is used to describe logic cicruits which show internal states ("stateful"), and therefore have at least one memory element (= flip-flop). This terminology is used in the following explanations: * The input vector $\overrightarrow{X}$ represents the $k$ inputs $X_0 ... X_{k-1}$ * The output vector $\overrightarrow{Y}$ represents the $l$ outputs $Y_0 ... Y_{l-1}$ * The state vector $\overrightarrow{Q}$ represents the $m$ inputs $X_0 ... X_{m-1}$ * The sign $(n)$ or $n$ marking the current point in time and therefore e.g. the current state $Q_0(n)$ * The sign $(n+1)$ or $n+1$ marking the next upcomming point in time and therefore e.g. the next state $Q_0(n+1)$ The <imgref pic04> shows the different terms in an abstract diagram. The "current" output values are here the values, which are shown after the delay time of the gates (about some nanoseconds). <WRAP> <imgcaption pic04| Abstract View onto a Sequential Logic> </imgcaption> {{drawio>ViewOnSequentialLogic1}} </WRAP> The principle interior of the blackbox in <imgref pic04> was already shown in one practical application in the {{:introduction_to_digital_systems:storage_elements#look_onto_the_problem_reduce_it_down_to_the_relevant_part|previous chapter}}: We saw, that we need the combination of an combinatorial logic and some storage components. Additionally, both have to be connected by feeding back some of the outputs back to the combinatorial logic. This is shown in <imgref pic05> <WRAP> <imgcaption pic05| One Step more into the Sequential Logic> </imgcaption> {{drawio>ViewOnSequentialLogic2}} </WRAP> **Finite Stae Machines** <WRAP><well> <imgcaption pic20|x ></imgcaption>\\ {{url>https://www.falstad.com/circuit/circuitjs.html?hideSidebar=true&ctz=CQAgjCAMB0l3BWcMBMcUHYMGZIA4UA2ATmIxAUgpABZsKBTAWjDACgwEls1xCrsCFHypUEHLiB5VMwwcNlQKEqq2FgMhcJu1aZ1cZxog0eESYzr+S4WInHTFhZac2l4mino1CxmmC0aM389Nk9vXylCYLNsaKgwr1pY+KCpIQTw5PTbKTwzSET6AXzsulEistwygMykn2M44MiQhIB3VwCBXi72qV5FQZdCjscNLXHdPtbFIJlhtg7W3ppiCesR5JlSubzjTd3sPH296bWTBEDzmjgzwNuWe4rR-HAaPzMwd77HFB2zP4FRYmV4oS4gSJg0IAJRATDwAkgxhYYDkSPAJmQMmgSBQOKUMHEABk4ZFeiirPoIAAzACGABsAM4MaibeGIxro3D7YHc8DEOQ9AV9PlgYV8vmbCVc3iS4FMMnWRXPCHGXpqcybZWqi6hDolE5i2zy2o3KiPN48joWr4fS19VTCtJG6afYUal0HN3CNKAzJiiGvF2EFye2jA-gA8GrLRQhIAI364FRJnF1UKif89EEsRQEA1B3OcZjmrYaHICrV1kr4D+tBAAA0y5ByLtZgiTDd6wBFQrlwNRrQIYUoLvGABa7AAHv01ZBvOiwJBAp2QIyAC4AewATrSAOYMNgzhD0DAAr7IYKrgDGm4AtvGAJYAO1pW+3j+vDIAOozv9-n2vR9t2vABXR911-I9aDiZBvFKJcV1HNd1zfQ8Z0IOsl3oEg5yQ4xN1A9cAAciObchIxMUph2cH0QHHL1thieZjSWDs-Uov1CiAA noborder}} </well></WRAP> ==== Moore Machine ==== * Number of flip-flops given by number of states * synchronous output * less logic gates necessary <WRAP><well> <imgcaption pic21|x ></imgcaption>\\ {{url>https://www.falstad.com/circuit/circuitjs.html?hideSidebar=true&ctz=CQAgjCAMB0l3BWcMBMcUHYMGZIA4UA2ATmIxAUgpABZsKBTAWjDACgwEls1xCrsCFHypUEHLiB5VMwwcNlQoEqq2FgMhcJu1aZS8Zxog0eESYzr+S4UkMJjpiwsvOb1cTRT0ahYzTAtGjMAvTYvHz8pQhCzbBjlCNo4hOCpIUTvZPThATwzSHCsvNjaXEyfEPK00IraKPiQqNrCgHc3QIFeTuV26TdFRTaTfF0xjTD22sVgmVdh2p6aYi0ehbw54VmpPGN1vL2dvbYplZMaKmWguF7aM4uqFmvRE5GzMBp-d8-bpxR87L-AqvP4ILRRFBg5QAJRATA2UkgxhYYDkSPAJmQMmgSBQOKUMHEABk4VEeiirPoIAAzACGABsAM4MajDeECdG4Yxc248sDEOTdAW89H8tHc9HDHnS3g8tlk6wKl7tJXgVHmYaqiFQ4YHJRi25PWg3I0fY7tU0-NJm26qYXW4XrcDCtTO3KvB1bMxAxL8kAYDIGvCBN1KGivQhQlAoYwBhQx25xkxQyNaSFhABGUnU6pQwuw5UKWYC9EEcRQEFdCzOMcuZzWbDQ5CYqpbxlRIRAAA1G5ByFdzAOO7QQABFdhN5KbKfnS5jwqTpPR2PxN4jgBaKF75CXUJwaYuG-YAA9s+3ID5RZAgucQIyAC4AewATrSAOYMNinhD0DDej7IJ2CYAMaPgAthmACWAB2tJPs+kHAQyAA6jLIch0HAZBz7AQArpB96oSeZSrBeyTvNeI4Jg+cGfqeWDqGReDYBRN4Jo+uH3gADpxKgUNYEwgIQCaCfoYgSMYCDCumQlRjqmJ2K8YKqNYDjttYwxqYO9YaUpPw9Fpta3IZh5SQoh77G4QjevMSn-FZ0m2e0ymhtZoaafZBpuUMEZRgmqZjJqUKCcJ7Y6IU35gGYWBCRgxDIP2t6gRBMFwS+iEoWhGFYTh+GEYyW5ZggUVqsYhDlVIPDKIuGQ+vubjGOuhQAJIUD8PJmYihyEhQdk2bY9lyn1XVtRK5oUPm6IBUNKpQjyAU+kFaYAkuAKFEAA noborder}} </well></WRAP> ==== Mealy Machine ==== * Number of flip-flops given by number of states * asynchronous output * less logic gates necessary <WRAP><well> <imgcaption pic22|x ></imgcaption>\\ {{url>https://www.falstad.com/circuit/circuitjs.html?hideSidebar=true&ctz=CQAgjCAMB0l3BWcMBMcUHYMGZIA4UA2ATmIxAUgpABZsKBTAWjDACgwEls1xCrsCFHyqiOXEDyqZhg4TKgVxVVsLAZC4DVs3TqCcTRBo8I4xjX9FwpAc5GT5+RafXFBmino1CRmmE0aU39dNk9vX0lCYNNsaKgwr1pY+KDJIQTw5PThATxTSET6PJjaXEyktLoqKoCKiKM44MiQhIB3VwCBXi72yUgHFwUFQo7HdU0JnT7WhSDpF1HaOt6aYkmrJfnXbew8Iy28PIPJfZn14xoai6uxDrXAuBAWR7vjfHAaP1MwL77HFD5bKAgpsMYfFAITSRSGhABKzyO-SMLDAsgG4GMyGk0CQKFxihgBgAMs9Ir1UZY9BAAGYAQwANgBnBjUJZMJG4Rq8Ll9KTgYiyHkY9nkqxit4S8BosxLKUwqF9Y6KMCCvovWhPDW-A5g54rP5pHVKgXCI1qw6m6VqC1681m0wgzKqkAYDKq4R4FYW2h6wiKlAoIxu+RBvoh4yK-2aWEJABGkjUMpQauw5UKCf89EEsRQEFU5xjV1oF16hTQ5CYUqrRjRwRAAA02BWSxtrpNAbQQABFdgt7ZzJFBmo98uQcgRwPBuLvesALRQzfHroysZwRZHc-YAA9E7XIN4MWBIIFLiAmQAXAD2ACc6QBzBhsXcIegYR2-ZD1sMAYyvAFs4wASwAOzpa8byAn9GQAHSZGCYJAn8gJvH8AFcgIvOCdzKSYD2SH4Ty7MNL3Ap9dywNR8LwPZkFPMMrzQi8AAcmOUCgrCmQgwymPQqDsBAjAQNVY2jSNdCxWw9ShFQrEE2tNmkv5VlLRSOnkswNOHPotOLYT5GLQ4FhsTsRmk0yXH01wlhkq0hB+W11M7D0KAs3I-QDMMxN4jzJm0bja20QoXzAUwsBAQgMGIZByAcIw-0A0DwNvKDYPgxDkNQjCsKZRcEwQULpSMQgSskHgEhbScgXXHYQDnJYMAxJ0qtBDpeQUfkzLapqXF5L5WuRWg0kavw0gajF+tdJqgUKLISsCGhyEIQqgmKIoIpWmiNuachZqSZadskd9aEi+oNtil1ltiyAkD2+grs1JASqQL5dvW5bAhdbBtH8aK7qOz7ou+wJTsKIA noborder}} </well></WRAP> ==== Medvedev Machine ==== * Number of flip-flops equal to number of outputs * synchronous output * more logic gates necessary <WRAP><well> <imgcaption pic23|x ></imgcaption>\\ {{url>https://www.falstad.com/circuit/circuitjs.html?hideSidebar=true&ctz=CQAgjCAMB0l3BWcMBMcUHYMGZIA4UA2ATmIxAUgpABZsKBTAWjDACgwEls1xCrsCFHyqiOXEDyqZhg4TKgVxNEGjyS8Khdk2LhVBGxop6OpITogm2CBfqQjJjUgTEk1iK6QPj9DxTcrGwoMYihHP2CEUKsYwk5w31iw+PdgwmjEp38M8hzLHyczAO48cwK2AHdVDGEwfkleerFq3C1amvkOh2qaes7aPGluqtp+5tpiQhFw3qGBmnmdFR7BgxoVJimKDdnJ6ZQUFRptmjg9k+mEBpYwYWuxACUrO-U+6ZYG9-BVZGloJAoAGKGCGAAyVhQeHUryC2GmsLqIAAZgBDAA2AGcGNRViwoWNplJCXtiWBiLJeG1EuSQBghOAKSA8OMmVQaKNLqojnSGYcVqN6fJrhQ7qoRQ4AEbgeiseR4MI0DAC6V9ehKgQoCByi7bfn7GYONB5KEwglMU0gU4gAAabGNBomXNhKgAiih7ZByBt1MtaItJAy3Uavbz5DycAd8LQQAAtD0OoXi6aR1RnGOx9gAD0aKjAkHVkDzkGmWhUmIALgB7ABOqIA5gw2DmEPQMOotcW3mmQABjKsAW0lAEsAHao6s14e9jEAHUxs9no97w5rvYArsOK-Ps7R4ch1dDkKWe5WJ02c1g6gXmTpjzGeVX1xWAA7PznzBQIMUKEPkJOWqmCgqLGqzfvK6gAUeqzUtovC-uI3BUrocgaCsSi9P0fo+mhFz9DhdDCDhqyEf6bw8AaJFLLoizrAKvSnOcXIPOEDq0Qsn7pm67C9AGZzsgG4EXBYFDmvMQjqCRFFckwfHbGBP4dEJKASqMylHkJ-F7JpTF8ecJF6QJvq6DBVJFo07L9KZAi6NoJmjGotDnEwIlaQ4nBUOMuzbGAuzSIohicPI0YTAoEz+S44jBR2HQKL+kgBeInliuSdRMqlejUIFlB8Ko0Z6tGEUYVaCK7I5vn0YydQYFGMI1XsGVgPVjVsqMOpNR8lodQ1P75bV4QeeAP4ihlKnTP5BhtUyY15R2qmDf0lp6tBvyTQtRIMtsqETUoC1itg+4ZQd42rcVjnwnVRKEJJbX1Rd4B3fZ1TdX6FpHn6eKGVYcnjW1Bw8i5Wg8p9bzOQG1J4tsCC7FsBwjNUtx1A04wNKsrLCLDVV7EwSzXVY4kEmjP7phaPJHC0JWzZTCHVHqHQ6jTQ2UlQb2+rwROyJtG36FNsiHdN0G86oR6OZaqyi-T9WM8tl3Czdz1S0e3WM4tHSY4zgNOSzIlCSRWH7jQInHcJKjG4bKgSRcglipruujIjFA3O1qP2yJCia-qaMIua+qwl7kjmbJvrmZDcMYz5rUI7jMJXfLuXG5rxt4kb+4eyMACSkJKz7PJ+1AwKGAjvs52WFOs+APtK-VeJdfV5fEjX728PXT1WK5zkp79QA noborder}} </well></WRAP>