Turing Complete - User contributions [en]

K-map

2023-11-21T19:21:27Z

BlockOG: A couple typos fixed, and Is capitalized

{{guide|narrow=1}}
=== What are Karnaugh-Veitch maps? ===
A Karnaugh-Veitch map is a modified truth table for 4 bits, which allows to derive simplified circuits for this table just by looking at it. So every time you come across a logic, that has 3 or 4 bits of input, you can plug its truth table into a KV map and build the circuit.

=== Okay, so how does it look like? ===
Usually you start with a truth table with 4 inputs and an output column with values that are either {{Off}} or {{On}}. In this example the output values doesn't matter (yet), but notice that I gave them numbers from 0 to 15 that matches their corresponding input bit pattern.

[[File:4bit_TruthTable_decimal_output.png]]

A Karnaugh map is a truth table, where each bit combination is represented in 2D form.
So the outputs are not a straight line like above, but like a square:

[[File:KMap_undefined_output.png]]

As a careful observer, you may have noticed something strange: The input combinations are not numbered 0-1-2-3 (in binary), but '''0-1-3-2'''!

<blockquote>Why though?!</blockquote>

The answer: We make sure, that '''only 1 bit changes in each step'''. So if we would go 0-1-2-3, then the step from 1 to 2 in binary would be 01 to 10. '''Both''' bits would change, but we only want 1 bit to change at max. This is why we swap the order of the inputs, but make sure, that we still have all possible combinations available.

<blockquote>BUT WHYYY?!</blockquote>
Yes, yes... later...

Changing the order of the input also changes the order in which we fill in the outputs. Going from left to right, skipping the third column and going from top to bottom, skipping the third row. The white numbers are the order in which you plug in the output values.

[[File:KMap_undefined_output_graycode.png]]
[[File:KMap_decimal_output_graycode.png]]

=== How does this help me in any way? ===
'''BLOCKS!'''

The answer is blocks.

Let me explain...

Humans are very good at visual pattern recognition (if the layout favors it). By using the ''only-1-bit-change'' trick, we can now combine bits in blocks of size 1,2,4 and 8. When forming blocks, we only focus on the {{On}} bits! Leaving the {{Off}} bits alone.

Lets say there are the following 2 green output bits that we are interested in:

[[File:KMap_Example1.png]]

Question is: How can we describe these two bits using the bits from the columns and rows?

[[File:KMap_Example2.png]]
[[File:KMap_Example3.png]]

'''Row:''' 
The bits that we are interested in, are in the row where:

{| class="truthtable" style="border: 2px solid darkgray; padding: 2px"
| [[File:D_boxed.png]] || [[File:C_boxed.png]]
|-
| [[File:Off.png|24px]] || [[File:On.png|frameless|24px]]
|}

'''Column:''' 
The bits that we are interested in, are in the columns where:

{| class="truthtable" style="border: 2px solid darkgray; padding: 2px"
| [[File:A_boxed.png]]
|-
| [[File:On.png|24px]]
|}

We don't need [[File:B_boxed.png]] to describe the two columns, because [[File:A_boxed.png]] = {{On}} already covers both columns.

By putting those together, we can describe the {{On}} bits as '''2-bit block'''. The bigger the block, the less inputs we need to describe it! So we want to make the blocks as big as possible. To describe a 2-bit block, we need 3 inputs - the 4th does not matter (also a feature of our ''1-bit-change-only trick'').

[[File:KMap_Example4.png]]

The block is described by this combined input conditions:

{| class="truthtable" style="border: 2px solid darkgray; padding: 2px"
| [[File:D_boxed.png]] || [[File:C_boxed.png]] || [[File:B_boxed.png]] || [[File:A_boxed.png]]
|-
| [[File:Off.png|24px]] || [[File:On.png|24px]] || [[File:Cross_gray.png|24px]] || [[File:On.png|24px]]
|}

So now we can '''AND''' everything together and the block is done.

[[File:KMap_circuit_block.png]]

=== Any more block limitations? ===

Only the 1,2,4,8 block size rule.

Additional note: The blocks can also '''''go around''''' from left to right, and from top to bottom. So for example, you can do an 8-bit block from left to right (using only one input variable to describe it).

[[File:KMap_around.png]]

This block is described only by one input variable

{| class="truthtable" style="border: 2px solid darkgray; padding: 2px"
| [[File:D_boxed.png]] || [[File:C_boxed.png]] || [[File:B_boxed.png]] || [[File:A_boxed.png]]
|-
| [[File:Cross_gray.png|24px]] || [[File:Cross_gray.png|24px]] || [[File:Cross_gray.png|24px]] || [[File:Off.png|24px]]
|}

'''Question for you:''' ''Can you do a block, that covers only the 4 corners?''

=== So this is it? ===
Not quite.

Since we can only do 1,2,4 and 8 bit blocks, we have to combine multiple blocks together, to cover all {{On}} outputs. Each one of them has to be part of a block. Overlapping blocks are no problem, they are actually quite helpful to create big blocks for missing bits.

==== Example ====
This is our truth table, that we already plugged into our Karnaugh map:

[[File:KMap_Example5.png]]

Now we have to do blocks of 1,2,4 or 8 (as big as possible) to cover all {{On}} output bits.

We can do it like this:

[[File:KMap_Example9.png]]

We need 3 blocks to cover all bits:

#[[File:YellowBox.png|14px]] A yellow 2-bit block
#[[File:BlueBox.png|14px]] A blue 4-bit block
#[[File:WhiteBox.png|14px]] A white 4-bit block

Combined they look like this:

{| class="truthtable" style="border: 2px solid darkgray; padding: 2px"
| || [[File:D_boxed.png]] || [[File:C_boxed.png]] || [[File:B_boxed.png]] || [[File:A_boxed.png]]
|-
| [[File:YellowBox.png]] || [[File:Cross_gray.png|24px]] || [[File:On.png|24px]] || [[File:On.png|24px]] || [[File:On.png|24px]]
|-
| [[File:BlueBox.png]] || [[File:On.png|24px]] || [[File:Cross_gray.png|24px]] || [[File:Off.png|24px]] || [[File:Cross_gray.png|24px]]
|-
| [[File:WhiteBox.png]] || [[File:On.png|24px]] || [[File:Cross_gray.png|24px]] || [[File:Cross_gray.png|24px]] || [[File:On.png|24px]]
|}

To build the blocks, we '''AND''' the inputs and after that we '''OR''' the blocks together

[[File:KMap_circuit_combining_blocks.png|640px]]

And that's it! We created a circuit that describes the truth table completely!

=== Final notes ===
The whole idea is based on the fact that a circuit like this:

<code>
(SuperComplexExpression AND a) OR (SuperComplexExpression AND NOT a)
</code>

is the same as just

<code>
(SuperComplexExpression)
</code>

Because it doesn't matter if A is {{On}} or {{Off}} - either the first part of the bracket is passed through, or the second part. So if only one bit changes, then we can remove that bit from the equation. (I was asked about that fact in my exam, so maybe it is good to know).

----

You can do a Karnaugh map for 3 bits, by throwing away the two rows on the bottom and the D input.

----

You can also do a Karnaugh map for 5 bits, by creating two 4-bit maps. One where the 5th bit is {{Off}} and one where the 5th bit is {{On}}. Then imagine you lay both maps on top of each other, so you can do additional blocks by piercing through both maps.

----

The way we collected the bits and put together the blocks is called ''Disjunctive Normal Form (DNF)'' which focuses on the {{On}} output bits, which are then '''OR'''d together. There is also a ''Conjunctive Normal Form (CNF)'' where you focus on the {{Off}} bits and then '''AND''' the blocks together (a bit more complicated - you have to look it up).

----

If you have two potential blocks of {{On}} bits, but the intersection of those two blocks are {{Off}}, then you can '''XOR''' them together instead of '''OR'''.

[[File:KMap_Example10.png]]

----

If you have a ''chess board pattern'' in your KV map, you can just XOR all inputs together.

=== Now its your turn! ===
Here is a task for you:

You get a 4 bit number as input, and you have to display the number in decimal. For this purpose there is the 7-Segment display in the sandbox, which has 7 segments that you can turn on and off.

Fill a Karnaugh map for each segment (Seg1 to Seg7) and build a circuit, so that the correct decimal number is displayed for each binary input number. If you want, you can also display 10 as A, 11 as b etc. up to 15 (hex converter). Otherwise the numbers 10-15 do not matter and can be used to build bigger blocks.

In this picture the input number is a binary 6. Build the circuit in the purple box (the box is way to small, I know), so that for the binary 6 the segments 1,6,7,5,4, and 3 are ''"glowing"''. (And for the rest of the binary numbers as well from 0 to 9). You need a KV map for each segment. Create the "normal" truth table first, and then fill the map, create blocks and OR them together.

[[File:KMap_Exercise.png|640px]]

----

Happy wiring! Hope you learned something :)

State Machines -or- How to solve the maze with 2 gates

2023-11-21T13:34:33Z

BlockOG: Fixed some typos, non-capitalized Is and... some British English

{{guide|narrow=1}}

'''Prerequisites: ''' 
''Make sure you completed '''The Maze''' level. I also use KV diagrams later on, so you might check out this guide before: '''[[K-map]]'''
== The idea - what is a state machine? ==

Imagine you have to build a circuit to control some kind of device. You don't have a full computer - only basic gates, and need to come up with a solution, so that your device behave the way you want it to.

The idea is, that we go over all possible things that our device can do step-by-step. We draw a circle for each of those steps and call it a '''state'''. Usually every possible output that our device can have has at least one state. We then connect this circles by arrows that have a certain condition assigned to it (called '''transitions'''). These conditions are usually a specific configuration of input signals (What shall the device do when certain inputs arrive).

This means something like that: 
''We go from state A to state B, when the condition on the arrow from A to B is met.''

[[File:State basic.png]]

By doing so, we can construct a picture where the complete behavior is visible for us and we can understand it easily (= '''state machine'''). The cool thing is: There is a completely deterministic way to convert this pictures to circuits by following a few steps, and your device will do exactly what you specified in the picture. It is so straight forward, that you can technically write a program that converts state machines to circuits.

If That's to easy for you, you can then go and optimize your state machine to get an even better result with super few gates (That's the fun part).

== Step 1: Draw a simple state machine ==
We have a perfect example for a level which we can solve using a state machine:

'''The Maze'''

In the level description, we find a hint where the exact behavior is described

1: Step forward
2: Turn left
3: Turn right as long as there is a wall ahead
4: Press use after each turn (in case the exit is ahead)
5: Repeat

This is the behavior we want to implement, but we don't want to use a computer or any programming. Only basic gates are allowed!

We start with line 1: <code>Step forward</code>

[[File:Step forward.png]]

Simple enough.

Let's go on with line 2: <code>Turn left</code>

We always do that after we take a step forward, so '''always''' is our condition, that we write on the transition arrow. There is no right and wrong, it only has to make sense for us as humans.

[[File:Turn_left.png]]

Makes sense?

Here comes line 3: <code>Turn right as long as there is a wall ahead</code>

Now we have our first 'real' condition. As soon as our input tells us ''"There is a wall ahead"'', we go from '''Turn left''' to '''Turn right''', and stay there as long as our input sees a wall.

[[File:Turn right.png]]

Note: In each tick the machine has to use one of the arrows, based on its input values.

Let's continue: <code>Press use after each turn (in case the exit is ahead)</code>

Basically what this means is: <blockquote>If you see a door after you turned, then use the action command</blockquote>

So we add an ''Action'' state that we enter, when we see a door, after we turned

[[File:SM Door.png]]

Since the door is the end, we don't need any arrows going out from there.

Time for the last line: <code>Repeat</code>

It means, we start over with the first step, if we see a free space. Let's add that:

[[File:Repeat.png]]

And that's it! That's all we need. In each tick, we check the roboters inputs and take the transition that matches that condition. Now we have to convert that into a circuit.

== Step 2: Add Outputs ==
Since we now know which states there are, we also know which output signals we have to send during a particular state.

Let's take a look at all the output signals, that the robot understands

[[File:Robot out.png]]

In each state, we send one of these signals to the output. E.g. when we are in state '''Turn Right''', then we send the corresponding signal to the output, which is {{Off}}{{On}}{{Off}}.

We can add that information to our graph for each state:

[[File:SM Outputs.png]]

== Step 3: Number the states ==
Each state needs a unique id (bit pattern), so that we can identify in which state we are currently in. This id is completely arbitrary - we can choose whatever we want, the only thing that matters is, that it is unique for each state.

The easiest (but not necessary the smartest) way to do that is to simply assign a number to each state. By doing so, each state can be referenced using that number.

Let's do it and add that information to our graph: we have 4 states, so we count from 0 to 3 - and we need 2 bits to represent every number.

[[File:SM Number.png]]

What does this mean for our circuit?
Somewhere in our circuit there are 2 wires that represent our state number. We can access these wires at any time if we want to know which state is currently active.

'''HOLD ON! '''

That also means that we can already start building things! We can access the state wires, and we already plugged in our output signals, that we want to send in a particular state...
So assuming that the state wires are already there - we can build the part, that sends output signals!

== Step 4: Build the output circuit ==
Okay, we know that there are 2 wires [[File:Symbol S1.png|20px]][[File:Symbol S0.png|20px]] that provide the number of a state. And if we know the state number, we can determine which of the output bits [[File:Symbol O2.png|20px]][[File:Symbol O1.png|20px]][[File:Symbol O0.png|20px]] has to be {{On}}.

So Let's start with [[File:Symbol O0.png|20px]] and see in which state it needs to be {{On}}. Look at the graph and write down all state numbers in which this bit is {{On}}.

[[File:SM O0green.png]]

It is {{On}} in only one state, so Let's write that down:

{| class="truthtable" style="border: 2px solid darkgray; padding: 2px"
! rowspan="2" style="width: 30px;" | [[File:Symbol O0.png]]
! StateName
| [[File:Symbol S1.png]]
| [[File:Symbol S0.png]]
|-
| style="text-align: center;" | Step forward || [[File:Off.png|24px]] || [[File:Off.png|24px]]
|}

It's only one state here, but there could be more in theory - leading to a bigger table.

Let's continue with [[File:Symbol O1.png|20px]]:

[[File:SM O1green.png]]

Writing down all states where it is {{On}}

{| class="truthtable" style="border: 2px solid darkgray; padding: 2px"
! rowspan="2" style="width: 30px;" | [[File:Symbol O1.png]]
! StateName
| [[File:Symbol S1.png]]
| [[File:Symbol S0.png]]
|-
| style="text-align: center;" | Turn Right || [[File:On.png|24px]] || [[File:Off.png|24px]]
|}

And finally for [[File:Symbol O2.png|20px]]:

[[File:SM O2green.png]]

Again, there is only one state where the bit is {{On}}

{| class="truthtable" style="border: 2px solid darkgray; padding: 2px"
! rowspan="2" style="width: 30px;" | [[File:Symbol O2.png]]
! StateName
| [[File:Symbol S1.png]]
| [[File:Symbol S0.png]]
|-
| style="text-align: center;" | Action || [[File:On.png|24px]] || [[File:On.png|24px]]
|}

We are almost done - we just have to build our tables now. For each state that we have written down, '''AND''' all signals together. If you have more than one state in a table, then '''OR''' these ANDs (for each state) together, to get the final signal. (In short: '''AND''' the columns for each row, and '''OR''' all rows)

Our circuit for all 3 bits [[File:Symbol O2.png|20px]][[File:Symbol O1.png|20px]][[File:Symbol O0.png|20px]] looks like this:

[[File:SM Outputcircuit.JPG]]

Okay great - we build the output. But we need the s-Signals for that... so how do we do that?

== Step 5: Translate the transition conditions ==
The [[File:Symbol S1.png|20px]][[File:Symbol S0.png|20px]] signals represent our state. So we have to make sure, that the signal on these wires change, whenever we take a transition from one state to another (so they represent the new state).

That means we have to translate the words, that are written on our arrows into bits.

All these words represent some kind of input value, that the roboter sees. So Let's take a look at all the things that we can find in the maze:

[[File:SM Inputs.png]]

How do these inputs correspond to the words we wrote on our arrows?
''Door'' and ''Wall'' are obvious. But what does '''Free''' mean?

Well, it means either ''Nothing'' or ''Coin'', because we can walk over a coin as if its nothing. But that also means that we only have to focus on the first two input bits, because they are both {{Off}}{{Off}} for ''Nothing'' and ''Coin'', but different for any other input.

That means in the end we have the following conditions, based on the first two input bits [[File:Symbol I1.png|20px]][[File:Symbol I0.png|20px]]:

{| class="truthtable" style="border: 2px solid darkgray; padding: 2px;"
| [[File:Symbol I1.png]]
| [[File:Symbol I0.png]]
|
! style="text-align: left; padding-left:5px;" | means
|-
| [[File:Off.png|24px]] || [[File:Off.png|24px]] || || style="padding-left:5px;" | Free
|-
| [[File:Off.png|24px]] || [[File:On.png|24px]] || || style="padding-left:5px;" | Wall
|-
| [[File:On.png|24px]] || [[File:On.png|24px]] || || style="padding-left:5px;" | Door
|-
| [[File:Symbol Dc.png|24px]] || [[File:Symbol Dc.png|24px]] || || style="padding-left:5px;" | Always (we don't care about the value of the input)
|}

Alright, Let's put that into our graph!

[[File:SM Condition.png]]

'''Note:''' There can be multiple conditions on a single arrow (e.g. Door + Wall). You can write that in a little table as we did above (and later you '''OR''' all the conditions together)

== Step 6: Build the transition circuit ==
We now have all the information that we need to build the circuit for our [[File:Symbol S1.png|baseline|20px]][[File:Symbol S0.png|20px]] wires.

We begin with the wire for [[File:Symbol S0.png|20px]]

Here is what we do:
#We look at all the states where [[File:Symbol S0.png|20px]] is {{On}}
#We look at all the arrows that go into these states (because these arrows are the reason, that our bit is now {{On}})
#For all these arrows, we write down from which state they are coming from, and which condition the arrow has

So Let's see: 
''We have to look at all states where [[File:Symbol S0.png|20px]] is {{On}} and all arrows that lead to this state''

[[File:SM Condition1.png]]

Now Let's write down all these arrows together with the state where they start
{| class="truthtable" style="border: 2px solid darkgray; padding: 2px"
! style="text-align: right; padding-left:8px; padding-right:8px;" | Origin State
| [[File:Symbol S1.png]]
| [[File:Symbol S0.png]]
|
| [[File:Symbol I1.png]]
| [[File:Symbol I0.png]]
! style="padding-left:8px; padding-right:8px;" | Condition
|-
| style="text-align: right; padding-left:8px; padding-right:8px;" | Step Forward || [[File:Off.png|24px]] || [[File:Off.png|24px]] || || [[File:Symbol Dc.png|24px]] || [[File:Symbol Dc.png|24px]] || style="padding-left:8px; padding-right:8px;" | Always
|-
| style="text-align: right; padding-left:8px; padding-right:8px;" | Turn Left || [[File:Off.png|24px]] || [[File:On.png|24px]] || || [[File:On.png|24px]] || [[File:On.png|24px]] || style="padding-left:8px; padding-right:8px;" | Door
|-
| style="text-align: right; padding-left:8px; padding-right:8px;" | Turn Right || [[File:On.png|24px]] || [[File:Off.png|24px]] || || [[File:On.png|24px]] || [[File:On.png|24px]] || style="padding-left:8px; padding-right:8px;" | Door
|}

Each combination would turn [[File:Symbol S0.png|20px]] to {{On}}.

Let's interpret what we just wrote down:

The first row says:
<blockquote>"If we were in state 'Step Forward' last tick, then whatever is at the input - we will turn the s0 bit on in this tick"</blockquote>

The second row says: 
<blockquote>"If we were in state 'Turn Left' last tick, and our input now sees a door, then we turn the s0 bit on"</blockquote>

The third row says: 
<blockquote>"If we were in state 'Turn Right' last tick, and our input now sees a door, then we turn the s0 bit on"</blockquote>

So the bit [[File:Symbol S0.png|20px]] turns {{On}} if any one of those three statements is true, so we simply '''OR''' them together. Like before: '''AND''' all columns and '''OR''' all rows.

So Let's build it! (We once again just have to implement the table from above).

[[File:SM ConditionCircuit1.png|650px]]

As a careful observer you may have seen that you can reuse the AND gate that detects the ''door'' - but Let's continue and optimize later.

Alright, [[File:Symbol S0.png|20px]] is done - Let's do the same with [[File:Symbol S1.png|20px]]

Same as before: Collect all arrows, that lead to a {{On}} s1-bit

The relevant arrows are the yellow ones:

[[File:Condition2.png|650px]]

Let's write down the table for it
{| class="truthtable" style="border: 2px solid darkgray; padding: 2px"
! style="text-align: right; padding-left:8px; padding-right:8px;" | Origin State
| [[File:Symbol S1.png]]
| [[File:Symbol S0.png]]
|
| [[File:Symbol I1.png]]
| [[File:Symbol I0.png]]
! style="padding-left:8px; padding-right:8px;" | Condition
|-
| style="text-align: right; padding-left:8px; padding-right:8px;" | Turn Left || [[File:Off.png|24px]] || [[File:On.png|24px]] || || [[File:Off.png|24px]] || [[File:On.png|24px]] || style="padding-left:8px; padding-right:8px;" | Wall
|-
| style="text-align: right; padding-left:8px; padding-right:8px;" | Turn Left || [[File:Off.png|24px]] || [[File:On.png|24px]] || || [[File:On.png|24px]] || [[File:On.png|24px]] || style="padding-left:8px; padding-right:8px;" | Door
|-
| style="text-align: right; padding-left:8px; padding-right:8px;" | Turn Right || [[File:On.png|24px]] || [[File:Off.png|24px]] || || [[File:Off.png|24px]] || [[File:On.png|24px]] || style="padding-left:8px; padding-right:8px;" | Wall
|-
| style="text-align: right; padding-left:8px; padding-right:8px;" | Turn Right || [[File:On.png|24px]] || [[File:Off.png|24px]] || || [[File:On.png|24px]] || [[File:On.png|24px]] || style="padding-left:8px; padding-right:8px;" | Door
|}

We already build some of those arrows, but Let's optimize later and expand our circuit:

[[File:SM ConditionCircuit2.png|650px]]

All the rows in our table have '''AND'''s, that are '''OR'''d together.

We are almost done! We just need to put it all together.

== Step 7: Put everything together ==
Now there are two more things left to do. The fist one is kinda obvious:

In the last step we produced our state bits [[File:Symbol S1.png|20px]][[File:Symbol S0.png|20px]] based on the value they had in the tick before. So Let's make sure, that the signal we produced is available on these wires in the next tick for us to calculate again. We simply have to add a delay line like this:

[[File:SM Final1.png|650px]]

Last, but not least: we have to add our output circuit.
Note: We have to decide if we want to react on our new values immediately, or one tick later (like in saving gracefully). We basically have to decide if we want to pick up the s-Values before the delay line, or after it. Of course our robot has to act in the same tick, as he sees a wall or an opening - so we need to pick up the signals from our current tick (before the delay line).

Just copy paste the output circuit that we build before:

[[File:SM Final2.png|650px]]

That's it - That's all we need. Go an try it - the robot can now solve the maze!

Now the question is: Where can we get better?

== Let's get better ==
It's time for optimizing our state machine!

'''Note:''' All the things we do here are dependent on the particular state machine that you have in front of you. There a general things that you can look at, but this time, there is no ''"Step1/Step2/Step3-Guide"'' to get to the best solution. So don't be discouraged if you have an ''"How should I see that?!"''-moment. This all comes down to practice and getting a feeling for the things you have to look out for.

== Optimizing 1: State numbers ==
Remember when I stopped you from optimizing redundant wires? Of course you can do that, but if you really want to improve the circuit, we have to start somewhere else: with the numbering of the states.

The number that we assign to each individual state is completely up to us. We can choose whatever we want as long as each state number is unique. This is where we can improve.

Let's take a look at the graph that we had after ''Step 2: Add Outputs'' before we assigned any numbers to the states. Do you see that the output values themselves already produce unique numbers?

[[File:SM Outputs1.png]]

That's great, because that means, if we assign these numbers to their states, then the state variables are equal to the output signals and we don't need any logic to translate state signals to output signals - only straight wires from our s-wires to the output!

'''Note:''' The fact that our output signals are unique in each state is a special case! If you come across a state machine where multiple states have the same output, then you still have to give them a unique id - but it's a good idea to keep the numbers as close to your output signals as possible.

So what does this look like?

[[File:SM Number1.png]]

Now our outputs are equal to our s-wires. The output circuit therefore looks like this:

[[File:SM OutputCircuit1.png]]

Of corse this comes at the cost of adding a new state variable that we didn't need before, but maybe That's not so bad. We have to rewire our s-circuit anyways, so Let's do that and apply more optimizations there.

== Optimizing 2: Simplify your s-circuit ==
We changed our state codes so now we have to change our s-circuit as well, so that it matches the graph again. Let's do the same as we did in ''Step 6: Build the transition circuit''.

For each bit in our state code, we look at all the states where it is {{On}}, and ''"collect"'' all the arrows (transitions) that led to that state.

But this time, we organize the signals for the arrows in a KV diagram. An arrow is defined by the state in which it emerges (3 bits for the origin state) and by the conditions that are assigned to it (2 bits because each condition is represented by 2 bits). So we need a KV diagram with 3+2=5 variables to represent each possible arrow. A 5-bit KV diagram consists of two 4-bit KV maps in which the 5th bit [[File:Symbol S2.png|20px]] is considered {{Off}} in the first map, and considered {{On}} in the second map.

The raw KV diagram looks like this and it has a place for each possible arrow in the graph. '''These are not two different KV diagrams!''' They belong to each other so that we have a spot for each possible combination.

[[File:SM KV.png]]

Let's begin with our circuit to create the signal [[File:Symbol S0.png|20px]]. Look at all arrows that lead to a state where it is {{On}}.

[[File:SM O0green2.png]]

Now we take all these arrows (where they are coming from, and under what condition) and set it to {{On}} in our KV diagram, because that are exactly the conditions in which our [[File:Symbol S0.png|20px]] should turn {{On}}. All other positions are {{Off}}.

[[File:SM KV2.png]]

The two arrows produce 2 {{On}} bits in our KV diagram, that are right next to each other - creating a 2-bit block. This means that we need 1 bit fewer to describe that block than if we were to describe each arrow individually.

The table that describes this block looks like this (we don't need [[File:Symbol S1.png|20px]]):

{| class="truthtable" style="border: 2px solid darkgray; padding: 2px"
! rowspan="2" style="width: 30px;" | [[File:Symbol S0.png]]
| [[File:Symbol S2.png]]
| [[File:Symbol S1.png]]
| [[File:Symbol S0.png]]
| [[File:Symbol I1.png]]
| [[File:Symbol I0.png]]
|-
| [[File:Off.png|24px]] || [[File:Cross_gray.png|24px]] || [[File:Off.png|24px]] || [[File:Off.png|24px]] || [[File:Off.png|24px]]
|}

And when we build that, it would lead to the following s-circuit:

[[File:SM S circuit.png|650px]]

We could now go ahead and do the same with the two other bits as well, '''BUT''' we stop right here, because there are more things that we can do to get even better...

== Optimizing 3: Things that can never happen ==
When we filled out our KV diagram for [[File:Symbol S0.png|20px]], we turned all the bits that corresponded to an arrow to {{On}} and left every other bit at {{Off}}.

But there are some combinations that can '''never ever happen!'''

For example:
'''There is no way that an arrow can start from a state where [[File:Symbol S2.png|20px]] = [[File:On.png|24px]].'''
Why? Because when s2 is {{On}}, the only existing state is {{On}}{{Off}}{{Off}}, which is ''"Action"''. In that state, we are about to open the door and the level is over! We can not use another arrow from that state.

[[File:SM KV3.png]]

'''That means, we can ignore the whole second KV map and also [[File:Symbol S2.png|20px]] in all other KV diagrams'''

Knowing that, our KV diagram for [[File:Symbol S0.png|20px]] turns into this:

[[File:SM KV dc0.png]]

{| class="truthtable" style="border: 2px solid darkgray; padding: 2px"
! rowspan="2" style="width: 30px;" | [[File:Symbol S0.png]]
| [[File:Symbol S1.png]]
| [[File:Symbol S0.png]]
| [[File:Symbol I1.png]]
| [[File:Symbol I0.png]]
|-
| [[File:Cross_gray.png|24px]] || [[File:Off.png|24px]] || [[File:Off.png|24px]] || [[File:Off.png|24px]]
|}

So we got rid of the [[File:Symbol S2.png|20px]] gate - yay! But there is more

Let's take another look at our state machine:

[[File:SM State.png]]

We can ignore [[File:Symbol S2.png|20px]] and see that there is no state, where [[File:Symbol S1.png|20px]][[File:Symbol S0.png|20px]] is {{On}}{{On}}. But in our KV diagram, there is a whole row for potential arrows, coming out of {{On}}{{On}}, which can never happen (because there is no state for it).

So let's overwrite that row with a ''"don't care"'' signal, that we can use to build bigger blocks:

[[File:SM KV dc1.png]]

<blockquote>>>Waaait! You said we get bigger blocks, this doesn't help to get bigger blocks! SCAM!</blockquote>

Yes, yes - but keep in mind that this also applies for our other 2 bits [[File:Symbol S2.png|20px]] and [[File:Symbol S1.png|20px]], that we haven't looked at, yet. And also, we are still not done...

Let's revisit the inputs, that our robot can have:

[[File:SM Inputs.png]]

''Nothing'' and ''Coin'' is the same for us (= ''"Free"''), so we can ignore i3 and i2 - so far so good. But if you look closely, you can see that the input combination [[File:Symbol I1.png|20px]][[File:Symbol I0.png|20px]] = {{On}}{{Off}} also never happens!
This is a whole column in our KV diagram, that we can ignore! More ''don't care'' signals for us!

[[File:KV dc2.png]]

Do you see the 4-bit block, that we can build now?

[[File:SM KV dc3.png]]

This block is described by the following table:

{| class="truthtable" style="border: 2px solid darkgray; padding: 2px"
! rowspan="2" style="width: 30px;" | [[File:Symbol S0.png]]
| [[File:Symbol S1.png]]
| [[File:Symbol S0.png]]
| [[File:Symbol I1.png]]
| [[File:Symbol I0.png]]
|-
| [[File:Cross_gray.png|24px]] || [[File:Off.png|24px]] || [[File:Cross_gray.png|24px]] || [[File:Off.png|24px]]
|}

So we cut off yet another gate - nice!

[[File:SM S circuit1.png|650px]]

== Optimizing 3.5: Interim result ==
It's getting better and better! And I think it's time, that we apply our optimization to our other 2 missing state bits [[File:Symbol S1.png|20px]] and [[File:Symbol S2.png|20px]].

Alright - time for [[File:Symbol S1.png|20px]]! What are the conditions, to turn that bit to {{On}}? Let's see...

[[File:SM O1green2.png]]

All yellow arrows go directly in our modified KV diagram

[[File:SM KV dc4.png]]

Which leads to the following table

{| class="truthtable" style="border: 2px solid darkgray; padding: 2px"
! rowspan="2" style="width: 30px;" | [[File:Symbol S1.png]]
| [[File:Symbol S1.png]]
| [[File:Symbol S0.png]]
| [[File:Symbol I1.png]]
| [[File:Symbol I0.png]]
|-
| [[File:Cross_gray.png|24px]] || [[File:Off.png|24px]] || [[File:Off.png|24px]] || [[File:On.png|24px]]
|}

Expanding our circuit...

[[File:SM S circuit2.png|650px]]

And finally the same again for [[File:Symbol S2.png|20px]]

[[File:SM O2green2.png]]

Collecting all the arrows again and building blocks:

[[File:SM KV dc5.png]]

Leading to a table...

{| class="truthtable" style="border: 2px solid darkgray; padding: 2px"
! rowspan="2" style="width: 30px;" | [[File:Symbol S2.png]]
| [[File:Symbol S1.png]]
| [[File:Symbol S0.png]]
| [[File:Symbol I1.png]]
| [[File:Symbol I0.png]]
|-
| [[File:Cross_gray.png|24px]] || [[File:Off.png|24px]] || [[File:On.png|24px]] || [[File:Cross_gray.png|24px]]
|}

Which again expands our circuit:

[[File:SM S circuit3.png|650px]]

That's our complete s-circuit for all 3 bits.
So just for fun - let's wire that up with our output circuit and see if it still solves our maze:

[[File:SM Final3.png|650px]]

Spoiler: It does :)

Do you think it's time to finally optimize some gates using de'morgans law? Nope! There is still more fancy stuff that we can do!

== Optimizing 4: Things that are allowed to happen ==
We have 3 KV diagrams now, one for each s-Bit. Each {{On}} bit in one of these diagrams represents an arrow in our graph. All {{Off}} bits represent arrows, that are either not visible or leading to a state, where its corresponding s-Bit is {{Off}}.

Let's take a look at our three KV diagrams. Note that in each one of them, there is a {{Off}} bit, which, if turned into {{On}}, would allow us to build bigger blocks.

[[File:SM Arrow s0.png]]

Suppose that this bit was {{On}}, what would that mean? It means that there is an arrow in our picture, starting from state {{Off}}{{Off}}{{On}} '''(Step)''' and when the condition {{Off}}{{Off}} '''(Free)''' is active, it would lead to a state, where [[File:Symbol S0.png|20px]] is {{On}} - so before the change we landed in {{Off}}{{Off}}{{Off}}, and now we turn s0 on, and we would land in {{Off}}{{Off}}{{On}} '''(Step)''' again.

So this is the arrow, that we would create, and we now have to interpret, if that is ok for us.

[[File:SM Arrowstate s0.png]]

So is it ok to add this arrow?
Answer: '''NO!''' That would totally ruin our robot behavior, because when we are in state '''Step''', we would take another step if we see nothing and probably pass the door and/or miss intersections.

So we can not turn that bit to {{On}} to get bigger blocks :(

Maybe on [[File:Symbol S1.png|20px]], let's see...

[[File:SM Arrow s1.png]]

Which arrow does that bit describe?
We start at '''Step''' again, and when we see a '''Wall''', we usually would go to {{Off}}{{Off}}{{Off}} '''(Turn left)''', but this time we turn [[File:Symbol S1.png|20px]] on, so we land in {{Off}}{{On}}{{Off}} '''(Turn Right)'''.

[[File:SM Arrowstate s1.png]]

So is it ok to add this arrow?
Answer: '''Again NO!''' The first thing that we have to do after we take a step, is to check our left hand side, or we won't reach the end. So again nothing to get us bigger blocks :(

But have still one bit left, let's check out [[File:Symbol S2.png|20px]]

[[File:SM Arrow s2.png]]

So again: Which arrow is that?
We start in '''Step''' yet again, but this time we see a '''Door'''. Usually, we would go to {{Off}}{{Off}}{{Off}} '''(Turn left)''', but this time, the arrow turns the [[File:Symbol S2.png|20px]] bit on. So we land in {{On}}{{Off}}{{Off}} '''(Action)'''.
Sounds promising! Let's take a look at the state machine:

[[File:SM Arrowstate s2.png]]

'''YES!''' That could work! Assume that we just stepped forward and see a door, then it's totally fine to go to the '''Action''' state and open it, finishing the level.

But there is one last thing that we have to take care of, before we can add that arrow: We have to adjust the conditions of the other arrows, because before our change, that condition was part of the '''"Always"''' arrow! Taking it away from there also changes the s-circuits for all bits, what would be turned {{On}}, using the '''"Always"''' arrow. If it had been {{On}} in their KC diagrams, it would be {{Off}} now, because we took it away. Luckily '''"Always"''' leads to {{Off}}{{Off}}{{Off}}, so there is no s-Bit that is affected by our change. But nevertheless, we have to ''"cut out"'' the '''"Door"'''-condition from the '''"Always"''' arrow. We do that by listing all conditions except '''"Door"''' (which is only '''Wall''' and '''Free''').

So a quick adjustment and our state machine looks like this:

[[File:SM State final.png]]

With this change, the interesting bit, that we had in our [[File:Symbol S2.png|20px]] KV diagram turns {{On}} and we can build an 8-bit block:

[[File:SM Arrow s2 final.png]]

Which leads us to an even smaller table:

{| class="truthtable" style="border: 2px solid darkgray; padding: 2px"
! rowspan="2" style="width: 30px;" | [[File:Symbol S2.png]]
| [[File:Symbol S1.png]]
| [[File:Symbol S0.png]]
| [[File:Symbol I1.png]]
| [[File:Symbol I0.png]]
|-
| [[File:Cross_gray.png|24px]] || [[File:Cross_gray.png|24px]] || [[File:On.png|24px]] || [[File:Cross_gray.png|24px]]
|}

So our optimized s-circuit for [[File:Symbol S2.png|20px]] looks like this:

[[File:SM S circuit4.png|650px]]

Slow but steady we are reaching a point where we can't get any better.

== Optimizing 5: De'Morgan and boolean laws ==
It's time to polish our circuit by doing some boolean algebra. We don't do any high level tricky stuff here - just the application of a few rules, so that we can get rid of the '''NOT''' gates in our circuit.

=== De'Morgans Law ===
De'Morgans law says, that we can turn an '''AND''' into an '''OR''', by surrounding it with '''NOT'''s and vice versa.

So these two circuits behave exactly the same

[[File:SM Morgan1.png]]

And so do these

[[File:SM Morgan2.png]]

Our [[File:Symbol S0.png|20px]] circuit looks almost like a de'morgen circuit:

[[File:SM S circuit4.png|650px]]

So here is what we do: we take the '''AND''' there and replace it with an '''OR''' as in De'Morgans law.

[[File:SM Morgan3.png|650px]]

Now the double '''NOT'''s cancel out, and the remaining '''OR''' , followed by a '''NOT''' turns into a '''NOR''':

[[File:SM Morgan4.png|650px]]

=== Boolean laws ===
There are more laws around to simplify circuits, [https://en.wikipedia.org/wiki/Boolean%20algebra <here is the wikipedia page>], if you want a full list (De'morgans laws are in there as well), but the one we need to simplify our [[File:Symbol S1.png|20px]] circuit is the ''"Associativity of AND"''. Which means, that if you have and '''AND''' with more that 2 inputs, then it doesn't matter in which order you '''AND''' first.

So these two circuits are the same:

[[File:SM Morgan5.png]]

Let's apply that to our circuit, because there, we have 2 '''AND'''s chained up. The idea is, to plug both '''NOT'''-inputs into the same '''AND''', so that we can apply De'Morgan again.

[[File:SM Morgan6.png|650px]]

With the now reordered '''AND''', we can do the same as we did with s0: De'Morgan the '''AND''' into an '''OR''':

[[File:SM Morgan7.png|650px]]

And finally the '''NOT'''s cancel out again and the '''OR''' followed by a '''NOT''' turns into a '''NOR''':

[[File:SM Morgan8.png|650px]]

=== Put everything together and remove dead wires ===

So let's put everything back together:

[[File:SM_Morgan9.png|650px]]

Looks good, but the wires ''"s2 last_tick"'' and ''"s1 last_tick"'' are not connected to anything! So we can just delete them and get rid of the delay line.

[[File:SM Morgan10.png|650px]]

'''And this is it! That's our state machine that can't get any better, with a score of 4/4!

How cool is that :D'''

This is the end.

''<roll credits>''

... or is it?!

== Optimizing 6: A different solution ==
There is no way we can get any better for our solution to the algorithm. But let's go all the way back and read the level description again. Maybe there '''IS''' a way to get better.

Here is the description again, and I have subtly highlighted the hint for you:

[[File:SM Right hint.png]]

<blockquote>>> You are kidding right?! How's that gonna change anything - it's just mirrored! I don't wanna do everything again :( </blockquote>

Luckily we don't have to. We take all the good ideas from before - modify our state machine a little bit, and see how the s-circuits change.

So where did we leave off last time with our state machine?

[[File:SM State final2.png]]

So let's swap ''Turn left'' and ''Turn right''. So our robot watches to its right first, then turn left to look for an opening. Everything else stays the same.

[[File:SM Right state.png]]

Time to collect arrows again, starting with [[File:Symbol S0.png|20px]]

[[File:SM Right s0.png]]

The KV diagram for [[File:Symbol S0.png|20px]] stays the same, which makes sense, because the left and right state both fed into '''Step''' with {{Off}}{{Off}}, so by just flipping them, nothing happens.

[[File:SM KV dc3.png]]

{| class="truthtable" style="border: 2px solid darkgray; padding: 2px"
! rowspan="2" style="width: 30px;" | [[File:Symbol S0.png]]
| [[File:Symbol S1.png]]
| [[File:Symbol S0.png]]
| [[File:Symbol I1.png]]
| [[File:Symbol I0.png]]
|-
| [[File:Cross_gray.png|24px]] || [[File:Off.png|24px]] || [[File:Cross_gray.png|24px]] || [[File:Off.png|24px]]
|}

Let's go on with [[File:Symbol S1.png|20px]]

[[File:SM Right s1.png]]

Notice that the arrow, that goes into ''Turn Right'', has 2 conditions - we put both in our diagram

[[File:SM Right KV s1.png]]

{| class="truthtable" style="border: 2px solid darkgray; padding: 2px"
! rowspan="2" style="width: 30px;" | [[File:Symbol S1.png]]
| [[File:Symbol S1.png]]
| [[File:Symbol S0.png]]
| [[File:Symbol I1.png]]
| [[File:Symbol I0.png]]
|-
| [[File:Cross_gray.png|24px]] || [[File:On.png|24px]] || [[File:Off.png|24px]] || [[File:Cross_gray.png|24px]]
|}

And for [[File:Symbol S2.png|20px]]

[[File:SM Right s2.png]]

With this KV diagram (again, the same that we had last time, because the conditions stayed the same)

[[File:SM Arrow s2 final.png]]

{| class="truthtable" style="border: 2px solid darkgray; padding: 2px"
! rowspan="2" style="width: 30px;" | [[File:Symbol S2.png]]
| [[File:Symbol S1.png]]
| [[File:Symbol S0.png]]
| [[File:Symbol I1.png]]
| [[File:Symbol I0.png]]
|-
| [[File:Cross_gray.png|24px]] || [[File:Cross_gray.png|24px]] || [[File:On.png|24px]] || [[File:Cross_gray.png|24px]]
|}

So the only real difference is in in [[File:Symbol S1.png|20px]], where we moved from a 2-bit block to a 4-bit block. It's something, I guess - let's build it:

[[File:SM Right circuit.png|650px]]

Because [[File:Symbol S0.png|20px]] and [[File:Symbol S2.png|20px]] have the same KV diagram as before, we only have to modify our [[File:Symbol S1.png|20px]] circuit, which cuts off a '''NOR''', but we still need the '''NOT'''. This time however, we can't get rid of the '''NOT''' :( De'Morgan is only useful when both inputs have a '''NOT''' - not just one. And that means, that this is sill a 4/4 solution, like the one we had before.

<blockquote>>> WAAIT!! I FOUND IT!!! GO BACK TO THE S1 DIAGRAM!</blockquote>

Okay?! Nice - what did you find? Show me

<blockquote>>> HAH! I learned something in "Optimizing 4: Things that are allowed to happen"! We can turn that bit to green without breaking our robot and get a 8 bit block</blockquote>

[[File:SM Right KV suggest.png]]

<blockquote>>> Turning that bit to green means, that we go to "Turn right" after a step when we see a door, which is allowed, because we can open the door later, when we turn left again. That's how it's described in the algorithm anyways. And I tested it - and it works!</blockquote>

Good idea - but how does your state machine looks like now, when you add that arrow?

<blockquote>>> Uhm... the bit says that we come from "Step" under the condition "Door"... so like this:</blockquote>

[[File:SM Right state suggest.png]]

So far so good, but have you also thought about the fact, that the '''"door"''' arrow already points to '''"Action"'''? And when you take it away from '''"Action"''' - it turns its bit to {{Off}} in the "Action" KV diagram? We would lose the 8-bit block there.

<blockquote>>> But it works!</blockquote>

Yes - you found the right solution! But it doesn't work for the reason you think it does. The circuit you build no longer matches our state machine, and we have to explain, why it still works. (And hope that in the future no self-destruction action is implemented on output {{On}}{{On}}{{Off}}...

<blockquote>>> What???</blockquote>

We have to figure out why that works. Let me explain...

== Optimizing 7: Try ideas - but do it properly ==
Let's look at the state machine that you came up with and its KV diagrams
(I have separated the door arrow from the other two conditions)

[[File:SM Contra state.png]]

Here are the KV diagrams

[[File:SM Contra KV origin.pgn.png|650px]]

Nice blocks there - the circuit would definitely be better than ours!
But now you have a '''contradiction''' in your machine. What is the machine supposed to do, when it sees a door? Go to '''"Action"''' and open the door, or go to '''"Turn right"'''?

Here is the thing: '''Contradictions''' are only a thing in our graph. There is no contradiction in the circuit - every step is perfectly described by the equations (and KV diagrams) that we build. The question is: what does the circuit do in this situation? Which state does it prefer?

The state that we land in is determined by the 3 s-Variables for our next state. So let's see which signals [[File:Symbol S2.png|20px]][[File:Symbol S1.png|20px]][[File:Symbol S0.png|20px]] we get, when we come from '''"Step: {{Off}}{{On}}"''' and see '''"Door: {{On}}{{On}}"''':

[[File:SM Contra KV.png|650px]]

This is what each s-Bit would do. We would land in state {{On}}{{On}}{{Off}}, which does not exists! At least not in our graph... yet.

You know what? Let's go on and see what happens in that state...

So instead of two contradicting arrows, what really happens is that we go in a '''new mysterious state''' {{On}}{{On}}{{Off}}.

[[File:SM Contra state2.png|650px]]

Okay we may have opened pandoras box here...
Remember when we build our KV diagrams and said ''"We can ignore s2, because there is no state where an arrow can come out of a state where s2 ={{On}}"''?

Well, now we have such a state.
That means our 3 KV diagrams become three-dimensional again, with a second half where [[File:Symbol S1.png|20px]] is {{On}}.

But before we adjust our KV diagrams, let's quickly analyze what can happen when we are in the '''Mystery''' state.

The output, that we send to the robot is {{On}}{{On}}{{Off}} = 6, which does not exist (would be a pity if this was the self-destruct command). So the robot does nothing. But that also means, that the input signals doesn't change! Hence, we can only see '''"Door"''' and nothing else - everything else turns into ''"don't care"'' in out KV diagrams, since it can never happen!

Let's apply these findings to our KV diagrams. The only thing we know is, that the combination '''"Mystery"''' with condition '''"Door"''' is no longer ''"don't care"''. Very other bit in the second KV map is still ''"don't care"'' because they can never happen.

What we DON'T know is the value of these bits, so let's put a placeholder there.

[[File:SM Mystery kv s2.png|650px]]

[[File:SM Mystery kv s0.png|650px]]

[[File:SM Mystery kv s1.png|650px]]

The value of these bits is determined by our s-circuit = our blocks that we built from the KV diagrams. If a bit is in a block, it turns {{On}}, if it is not in a block it turns {{Off}}. So let's take the same blocks that we had before and put it back in, because we want to see what the circuit does, without us changing anything (the blocks now extend over both maps combined). This turns our placeholders into fix values, depending on whether they are in a block or not.

[[File:SM Final kv s2.png|650px]]

[[File:SM Final kv s1.png|650px]]

[[File:SM Final kv s0.png|650px]]

Now the bits are fixed, and we see which state is going to be active, when we come from '''"Mystery"''' and see a door:

[[File:SM Final target s2.png|650px]]

[[File:Final target s1.png|650px]]

[[File:SM Final target s0.png|650px]]

We would land in [[File:Symbol S2.png|20px]][[File:Symbol S1.png|20px]][[File:Symbol S0.png|20px]] = {{On}}{{Off}}{{Off}} = '''Action!'''

So our final state machine, that is actually underlying our KV blocks is this:

[[File:SM Final state.png|650px]]

When the robot is in '''"Step"''' sees a door, we output {{On}}{{On}}{{Off}} first (which fortunately doesn't break anything), and '''then''' go to '''"Action"''' and open the door. It works!

Now we just have to finish it!

== The End ==
So this is our final state machine

[[File:SM Final state.png|650px]]

Which is described by these KV diagrams:

[[File:SM Final kv s0.png|650px]]

{| class="truthtable" style="border: 2px solid darkgray; padding: 2px"
! rowspan="2" style="width: 30px;" | [[File:Symbol S0.png]]
| [[File:Symbol S2.png]]
| [[File:Symbol S1.png]]
| [[File:Symbol S0.png]]
| [[File:Symbol I1.png]]
| [[File:Symbol I0.png]]
|-
| [[File:Cross_gray.png|24px]] || [[File:Cross_gray.png|24px]] || [[File:Off.png|24px]] || [[File:Cross_gray.png|24px]] || [[File:Off.png|24px]]
|}

[[File:SM Final kv s1.png|650px]]

{| class="truthtable" style="border: 2px solid darkgray; padding: 2px"
! rowspan="2" style="width: 30px;" | [[File:Symbol S1.png]]
| [[File:Symbol S2.png]]
| [[File:Symbol S1.png]]
| [[File:Symbol S0.png]]
| [[File:Symbol I1.png]]
| [[File:Symbol I0.png]]
|-
| [[File:Cross_gray.png|24px]] || [[File:Cross_gray.png|24px]] || [[File:On.png|24px]] || [[File:Cross_gray.png|24px]] || [[File:Cross_gray.png|24px]]
|}

[[File:SM Final kv s2.png|650px]]

{| class="truthtable" style="border: 2px solid darkgray; padding: 2px"
! rowspan="2" style="width: 30px;" | [[File:Symbol S2.png]]
| [[File:Symbol S2.png]]
| [[File:Symbol S1.png]]
| [[File:Symbol S0.png]]
| [[File:Symbol I1.png]]
| [[File:Symbol I0.png]]
|-
| [[File:Cross_gray.png|24px]] || [[File:Cross_gray.png|24px]] || [[File:Cross_gray.png|24px]] || [[File:On.png|24px]] || [[File:Cross_gray.png|24px]]
|}

The only thing left for us to do is to build the circuits described by the tables

[[File:SM Final circuit1.png|650px]]

Or, if you clean it up a little bit:

[[File:SM Final circuit2.png]]

'''Result:''' To solve the maze - you need only 2 gates (one of which is a delay line).

<Roll credits... again>

=== A few final notes ===

You may have noticed that the end of chapter ''"Optimization 6"'' and the whole chapter of ''"Optimization 7"'' was just an expansion of chapter ''"Optimizing 4: Things that are allowed to happen"'' with its only purpose of ''"Is that bit-change ok for us?"''. So keep in mind that this is not always an easy question to answer.

However, I was very surprised about the amount of stuff and things that happen in this level. My original goal was to go all the way down to the 4/4 solution (end of Chapter ''"Optimizing 5"'') and leave the 2/2 solution to the reader as an exercise. Well... by doing this "exercise" myself, I simply had to explain it in detail, because this contradiction, that we had with the two door signals is easy to ignore when it solves the level. In reality however, you have to be really careful with that, because this hidden mystery state (that you encounter when you leave the contradiction in place) can trigger something completely unexpected.

Hope that gives you a glimpse on how state machines work. There is a lot more to state machines than presented here. Especially when you want to use this concept in real life, you have to deal with signal synchronization, stability of states and so on.

Feel free to leave a comment and tell me if there are parts, where my explanation isn't detailed enough, or things that I rushed over, but actually need more pictures etc. Also spelling and grammar mistakes please :)

Well - that's it! Thanks for reading!