Answers.Body: <p>I am teaching part of a Maths module that includes boolean logic- the assessment included creating digital circuits, labelling each point to derive the final expression, applying boolean logic (De Morgens etc) to the expression to minimise the term (which is by far the most difficult part for learners), creating the truth table, SOP and POS, creating the K-Map and deriving the expressions, and creating the minified circuit.</p>
  <p>After explaining the logic of each of the gates, they build some circuits using an emulator of sorts. As it happens two of the circuits are equivalent, and they result in an XOR function.  Learning point 1- XOR is useful as it can replace a bunch of other gates.</p>
  <p>As an aside, XOR could be used to rebuild a drive bit level</p>
  <pre><code>HD1: 0110
  HD2: 1100
  HD3: 1010 (HD1 Xor HD2)
  </code></pre>
  <p>so if any one drive is destroyed, the data can be rebuilt- e.g. HD2 gets fried- rebuild new drive H4</p>
  <pre><code>HD1: 0110
  HD3: 1010 
  HD4: 1100
  </code></pre>
  <p>It's an interesting and pretty cool application of XOR.</p>
  <p>In practise XOR can yield some nice circuit reduction but learners do tend to find it difficult using XOR in minimising.</p>
  <p>In terms of the importance if minimising, I look at the reduction in complexity and the real-life reduction in cost- number of gates and thus the number of chips, board space and layout time.</p>
  <p>Here is a completed labelled circ from a previous assignment completed in <a href="https://sourceforge.net/projects/circuit/" rel="nofollow noreferrer">Logisim</a>:</p>
  <p><a href="https://i.sstatic.net/intq6.png" rel="nofollow noreferrer"><img src="https://i.sstatic.net/intq6.png" alt="Sample circuit" /></a>
  Now, this can be reduced to 2 NOT gates and one OR. I should 'warn' that Logisim can generate the minified (SOP or POS) term, the K-Map and terms and generate circuits as well- which might be more than you want it to do.  At worst you could use it for creating some useful examples.</p>
  <p><a href="https://i.sstatic.net/8zwC9.jpg" rel="nofollow noreferrer"><img src="https://i.sstatic.net/8zwC9.jpg" alt="Space Invaders PCB, 1970s" /></a></p>
  <p>Here's a board from the 1970s. It's hard to make out any gates but there is a 74LD274 (3-input NOR gates) on there- hard to read. Given that the hardware &quot;is&quot; the software to a large degree here, the importance of reducing complexity and chip count was important. As already pointed out- it's not as important these days, but application of logical thought is just as important in software design.  An appreciation of the complexity implemented in hardware design is important, I think.</p>
  <p>I hope this might help with linking these elements together with K-Maps, since I suspect that you also cover these other topics.  As to how much focus you place on each part, you'll have to decide how much importance you place on each.  I think the outline of sub-topics is pretty good.</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2021-01-17T14:22:43.273Z
Answers.LastActivityDate: 2021-01-17T14:22:43.273Z
Answers.UserDisplayName: srattigan
Answers.Body: <blockquote>
  <p>What should I cover re Karnaugh maps in my processor course?</p>
  </blockquote>
  <p>Some more context perhaps about logic minimization??</p>
  <p>To convey the general sense and idea of minimization, karnaugh maps are fine.</p>
  <p>But pragmatically beyond 4-5 variables they're useless. At which point you begin to need the more program oriented <a href="https://en.m.wikipedia.org/wiki/Quine%E2%80%93McCluskey_algorithm" rel="nofollow noreferrer">Quine McCluskey method</a></p>
  <p>Even that runs out of steam rapidly due to combinatorial explosion — a 32 variable minimization would result in hundreds of billions on min-terms!</p>
  <p>Leads to
  <a href="https://en.wikipedia.org/wiki/Espresso_heuristic_logic_minimizer" rel="nofollow noreferrer">Espresso</a> : strictly speaking heuristic not optimization
  though generally found good enough.</p>
  <blockquote>
  <p>Should xor spotting be covered?</p>
  </blockquote>
  <p><a href="https://www.springer.com/gp/book/9781461279242" rel="nofollow noreferrer">Dijkstra</a>
  / <a href="https://www.springer.com/gp/book/9780387941158" rel="nofollow noreferrer">Gries</a>
  have some zany stuff on an equivalence-centered approach to logic. And equivalence is just the negation of xor.
  That's book length in itself!</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2021-01-06T05:33:21.793Z
Answers.LastActivityDate: 2021-01-06T12:56:18.520Z
Answers.LastEditDate: 2021-01-06T12:56:18.520Z
Answers.UserDisplayName: Rushi
Body: <p>I'm adding a bit about k-maps to my processors course, but being unfamiliar with them until now, I want to check that I am covering the correct things.  Here is what I am currently covering:</p>
  <ol>
  <li>How k-maps can be created and read (up through 4 variables -- I have decided to skip the 5th variable for now)</li>
  <li>The importance of the funny ordering in the axis (<span class="math-container">$00$</span>, <span class="math-container">$01$</span>, <span class="math-container">$11$</span>, <span class="math-container">$10$</span>) as a way to ensure that only one bit must be transformed to arrive at any neighboring position</li>
  <li>To derive expressions from k-maps, rectangles of 1s can be of size 1, 2, 4, or 8 only.</li>
  <li>How to actually derive an expression from a k-map</li>
  <li>How to derive expressions from k-maps when there are undefined regions within the k-map.</li>
  <li>Using k-maps to derive a Sum of Products (a.k.a. Disjunctive Normal Form) and a Product of Sums (Conjunctive Normal Form)</li>
  <li>The inverse relationship between the size of a rectangle and the number of variables that define it.</li>
  <li>Spotting xor values (perhaps I don't need this?  It doesn't seem much emphasized in materials I've found, since they mostly focus on finding SoP and PoS)</li>
  <li>k-maps wrap around, so you can make a rectangle that starts on the left edge and wraps leftwards to the right edge, or from the top and wrap upwards to the bottom.</li>
  </ol>
  <p>So, should I skip xor?  Is there something I should add?  Am I covering the right things?</p>
  
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2021-01-09T12:39:22.557Z
Comments.Text: Karnaugh maps were useful in the past. I'm not sure they're still useful. Would you spend time teaching about vacuum tubes just because it's in the curriculum?
Comments.UserDisplayName: Yuval Filmus
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2021-01-09T14:51:34.580Z
Comments.Text: @YuvalFilmus I'm teaching a processor design class to 16 year olds who haven't ever seen an `and` gate before. The idea of a manageable set of steps to find a minimum number of terms is the important part here, and this one is simple enough to cover in about 35 minutes. I mean, I could do Quine–McCluskey, but I would have to dramatically increase the time I provide to delve into it, and then it becomes more of a course focus and less of a side idea to whet the appetite. Plus, the processor that we will be designing is simple and small enough that k-maps are certainly useful here.
Comments.UserDisplayName: Ben I.
Tags: <boolean-algebra><curriculum-review>
Title: Subtopics to cover within Karnaugh Maps
ThreadText: # Subtopics to cover within Karnaugh Maps
  
  (Asked by: username_0 on 2021-01-04)
  
  I'm adding a bit about k-maps to my processors course, but being unfamiliar with them until now, I want to check that I am covering the correct things. Here is what I am currently covering:
  
  1. How k-maps can be created and read (up through 4 variables -- I have decided to skip the 5th variable for now)
  2. The importance of the funny ordering in the axis ($00$, $01$, $11$, $10$) as a way to ensure that only one bit must be transformed to arrive at any neighboring position
  3. To derive expressions from k-maps, rectangles of 1s can be of size 1, 2, 4, or 8 only.
  4. How to actually derive an expression from a k-map
  5. How to derive expressions from k-maps when there are undefined regions within the k-map.
  6. Using k-maps to derive a Sum of Products (a.k.a. Disjunctive Normal Form) and a Product of Sums (Conjunctive Normal Form)
  7. The inverse relationship between the size of a rectangle and the number of variables that define it.
  8. Spotting xor values (perhaps I don't need this? It doesn't seem much emphasized in materials I've found, since they mostly focus on finding SoP and PoS)
  9. k-maps wrap around, so you can make a rectangle that starts on the left edge and wraps leftwards to the right edge, or from the top and wrap upwards to the bottom.
  
  So, should I skip xor? Is there something I should add? Am I covering the right things?
  
  **Tags:** boolean-algebra, curriculum-review
  
  > **Comments:**
  > **username_1**: Karnaugh maps were useful in the past. I'm not sure they're still useful. Would you spend time teaching about vacuum tubes just because it's in the curriculum?  
  > **username_0**: @username_1 I'm teaching a processor design class to 16 year olds who haven't ever seen an `and` gate before. The idea of a manageable set of steps to find a minimum number of terms is the important part here, and this one is simple enough to cover in about 35 minutes. I mean, I could do Quine–McCluskey, but I would have to dramatically increase the time I provide to delve into it, and then it becomes more of a course focus and less of a side idea to whet the appetite. Plus, the processor that we will be designing is simple and small enough that k-maps are certainly useful here.  
  
  ---
  
  ## 2 answers
  
  ### Answer by username_2 on 2021-01-17. Score: 2
  
  I am teaching part of a Maths module that includes boolean logic- the assessment included creating digital circuits, labelling each point to derive the final expression, applying boolean logic (De Morgens etc) to the expression to minimise the term (which is by far the most difficult part for learners), creating the truth table, SOP and POS, creating the K-Map and deriving the expressions, and creating the minified circuit.
  
  After explaining the logic of each of the gates, they build some circuits using an emulator of sorts. As it happens two of the circuits are equivalent, and they result in an XOR function. Learning point 1- XOR is useful as it can replace a bunch of other gates.
  
  As an aside, XOR could be used to rebuild a drive bit level
  
  ```
  HD1: 0110
  HD2: 1100
  HD3: 1010 (HD1 Xor HD2)
  
  ```
  
  so if any one drive is destroyed, the data can be rebuilt- e.g. HD2 gets fried- rebuild new drive H4
  
  ```
  HD1: 0110
  HD3: 1010 
  HD4: 1100
  
  ```
  
  It's an interesting and pretty cool application of XOR.
  
  In practise XOR can yield some nice circuit reduction but learners do tend to find it difficult using XOR in minimising.
  
  In terms of the importance if minimising, I look at the reduction in complexity and the real-life reduction in cost- number of gates and thus the number of chips, board space and layout time.
  
  Here is a completed labelled circ from a previous assignment completed in [Logisim](https://sourceforge.net/projects/circuit/):
  
  [![Sample circuit](https://i.sstatic.net/intq6.png)](https://i.sstatic.net/intq6.png)
  Now, this can be reduced to 2 NOT gates and one OR. I should 'warn' that Logisim can generate the minified (SOP or POS) term, the K-Map and terms and generate circuits as well- which might be more than you want it to do. At worst you could use it for creating some useful examples.
  
  [![Space Invaders PCB, 1970s](https://i.sstatic.net/8zwC9.jpg)](https://i.sstatic.net/8zwC9.jpg)
  
  Here's a board from the 1970s. It's hard to make out any gates but there is a 74LD274 (3-input NOR gates) on there- hard to read. Given that the hardware "is" the software to a large degree here, the importance of reducing complexity and chip count was important. As already pointed out- it's not as important these days, but application of logical thought is just as important in software design. An appreciation of the complexity implemented in hardware design is important, I think.
  
  I hope this might help with linking these elements together with K-Maps, since I suspect that you also cover these other topics. As to how much focus you place on each part, you'll have to decide how much importance you place on each. I think the outline of sub-topics is pretty good.
  
  
  ---
  
  ### Answer by username_3 on 2021-01-06. Score: 1
  
  > What should I cover re Karnaugh maps in my processor course?
  
  Some more context perhaps about logic minimization??
  
  To convey the general sense and idea of minimization, karnaugh maps are fine.
  
  But pragmatically beyond 4-5 variables they're useless. At which point you begin to need the more program oriented [Quine McCluskey method](https://en.m.wikipedia.org/wiki/Quine%E2%80%93McCluskey_algorithm)
  
  Even that runs out of steam rapidly due to combinatorial explosion — a 32 variable minimization would result in hundreds of billions on min-terms!
  
  Leads to
  [Espresso](https://en.wikipedia.org/wiki/Espresso_heuristic_logic_minimizer) : strictly speaking heuristic not optimization
  though generally found good enough.
  
  > Should xor spotting be covered?
  
  [Dijkstra](https://www.springer.com/gp/book/9781461279242)
  / [Gries](https://www.springer.com/gp/book/9780387941158)
  have some zany stuff on an equivalence-centered approach to logic. And equivalence is just the negation of xor.
  That's book length in itself!
  
  
  ---
  
  