Disclaimer: This is a more advanced tutorial that builds on skills learned in projects 1-3. If this does not make sense at first glance, don’t be afraid! You are more than capable of designing circuits for complex problems like these. Spend some time reading over each step in detail, always referring back to the truth table. You will use the skills from this tutorial to design a thermometer circuit in Requirement 3.

Background

K-maps are excellent tools for creating minimized circuits with a small number of independent variables. Using super k-maps, we can have up to 6 independent variables, and using entered variables, we might be able to add an additional two more. But what if we have a circuit with 32 inputs? How would we use a k-map for that?

In truth, we can’t. But we can break the problem down into smaller parts that can be solved using k-maps. First, we should identify when the circuit should output a 1 (i.e. identify the minterms). Then, identify which input variables do not change, and which variables have no effect on the circuit.

Step 1 - Understand the Problem

Consider this example: our boss tasks us with designing a circuit that turns on an LED whenever a valid memory address within a certain range is written to a 32-bit address bus. The valid range is from 32'h43C0_0400 to 32'h43C0_0FFF inclusive.

begin_addr: 32'h43C0_0400 (32'b0100_0011_1100_0000_0000_0010_0000_0000)
end_addr:   32'h43C0_0FFF (32'b0100_0011_1100_0000_0000_1111_1111_1111)

Our boss also tells us that memory addresses are only valid when the lower two bits are both zeros.

Step 2 - Create a Truth Table

Always start by constructing a truth table. The full truth table is not shown, as there would be over 4 billion rows (2^32 = 4,294,967,296). The reader should imagine what the rest of the truth table looks like. The bolded rows indicate when the circuit outputs a 1.

Our strategy will be to find patterns in the truth table when the LED is on. We will then create pattern detector circuits, and finally AND the pattern detector circuits together.

Step 3 - Identify Fixed Inputs

We observe that we should only turn on the LED when the upper 20 bits are 20'h43C00. These bits are “fixed”. If the upper 20 bits are not this value, then our circuit should output a zero. So, we create a special 20-input detector circuit that detects when the upper 20 bits equal 20'43C00. This is implmented with an AND gate with inverters.

Also, since memory addresses are only valid when the lower two bits are zeros, we need to detect when the lower two bits are both zero. For this, we can use a NOR gate.

Step 4 - Identify Don’t Cares

Now we notice that bits [8:2] can take on any value and not affect the output of our circuit. To show this, start at address 32'h43C0_0400 and scan to 32'h43C0_07FC in the truth table, holding bits [1:0] at 2'b00. You will notice we swept through every possible combination of 1s and 0s for bits [8:2] without affecting the output of the circuit. Continue sweeping through address 32'h43C0_0FFC and you will see the same behavior repeated a few more times. Therefore, bits [8:2] do not affect the circuit, and we can remove these bits as inputs to our circuit. We replace these inputs with don’t cares in our compact truth table.

Step 5 - Create K-Map (if needed)

After considering which input variables are constant, and which inputs do not affect our circuit, we are left with only 3 input variables: bits [11:9]. We look for how these bits affect the output when the upper 20 bits equal 20'h43C00 and the lower two bits equal 2'b00. Bits [8:2] are shown as don’t cares.

Look carefully at the yellow section in the truth table. This is the truth table for a 3-input OR gate. Sometimes, the resulting truth table is not as simple. In that case, a K-map is required.

Step 6 - Create a Circuit

Finally, we AND the 3-input OR gate with the 20-input detector and 2-input detector to create the final circuit. Remember, the LED should turn on when the upper 20 bits equal 20'h43C00, the lower two bits equal 2'b00, AND the 3-input OR gate outputs a 1.

We can write this behavior in Verilog as follows. We used conditional expressions to make this easier to read.

assign LED = (addr[1:0] == 2'b00) & (addr[11:9] != 3'b000) & (addr[31:12] == 20'h43C00);

We could also use reduction NOR and reduction OR operators to make our code more compact and correlate with our schematic better. Both methods work, but the first might be easier to read.

assign LED = (~|addr[1:0]) & (|addr[11:9]) & (addr[31:12] == 20'h43C00);

Some readers might ask, “Why go through all of this trouble when I can just use the < and > operators?” While Vivado will always try to create a functional minimized circuit during synthesis, the resulting circuit is not guarenteed to be as simple or efficient. A bloated circuit will use more configurable logic blocks, have longer delays, and could result in timing-related bugs. For reference, code using the < and > operators is provided below:

assign LED = (addr >= 32'h43C0_0400) && (addr <= 32'h43C0_0FFF) && (addr[1:0] == 2'b00);

Important Ideas

• Many times, a circuit can be greatly simplified to require less inputs.
• Spending time simplifying a circuit before jumping into Verilog will result in cleaner, less buggy code.
• Understanding how to simplify complex circuits intuitively will make you a valuable digital engineer. Millions of people know how to code, but far fewer know how to use their intuition to create better circuits.