8: Karnaugh Mapping
- Page ID
- 944
\( \newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } \)
\( \newcommand{\vecd}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}} \)
\( \newcommand{\dsum}{\displaystyle\sum\limits} \)
\( \newcommand{\dint}{\displaystyle\int\limits} \)
\( \newcommand{\dlim}{\displaystyle\lim\limits} \)
\( \newcommand{\id}{\mathrm{id}}\) \( \newcommand{\Span}{\mathrm{span}}\)
( \newcommand{\kernel}{\mathrm{null}\,}\) \( \newcommand{\range}{\mathrm{range}\,}\)
\( \newcommand{\RealPart}{\mathrm{Re}}\) \( \newcommand{\ImaginaryPart}{\mathrm{Im}}\)
\( \newcommand{\Argument}{\mathrm{Arg}}\) \( \newcommand{\norm}[1]{\| #1 \|}\)
\( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\)
\( \newcommand{\Span}{\mathrm{span}}\)
\( \newcommand{\id}{\mathrm{id}}\)
\( \newcommand{\Span}{\mathrm{span}}\)
\( \newcommand{\kernel}{\mathrm{null}\,}\)
\( \newcommand{\range}{\mathrm{range}\,}\)
\( \newcommand{\RealPart}{\mathrm{Re}}\)
\( \newcommand{\ImaginaryPart}{\mathrm{Im}}\)
\( \newcommand{\Argument}{\mathrm{Arg}}\)
\( \newcommand{\norm}[1]{\| #1 \|}\)
\( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\)
\( \newcommand{\Span}{\mathrm{span}}\) \( \newcommand{\AA}{\unicode[.8,0]{x212B}}\)
\( \newcommand{\vectorA}[1]{\vec{#1}} % arrow\)
\( \newcommand{\vectorAt}[1]{\vec{\text{#1}}} % arrow\)
\( \newcommand{\vectorB}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } \)
\( \newcommand{\vectorC}[1]{\textbf{#1}} \)
\( \newcommand{\vectorD}[1]{\overrightarrow{#1}} \)
\( \newcommand{\vectorDt}[1]{\overrightarrow{\text{#1}}} \)
\( \newcommand{\vectE}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash{\mathbf {#1}}}} \)
\( \newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } \)
\(\newcommand{\longvect}{\overrightarrow}\)
\( \newcommand{\vecd}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}} \)
\(\newcommand{\avec}{\mathbf a}\) \(\newcommand{\bvec}{\mathbf b}\) \(\newcommand{\cvec}{\mathbf c}\) \(\newcommand{\dvec}{\mathbf d}\) \(\newcommand{\dtil}{\widetilde{\mathbf d}}\) \(\newcommand{\evec}{\mathbf e}\) \(\newcommand{\fvec}{\mathbf f}\) \(\newcommand{\nvec}{\mathbf n}\) \(\newcommand{\pvec}{\mathbf p}\) \(\newcommand{\qvec}{\mathbf q}\) \(\newcommand{\svec}{\mathbf s}\) \(\newcommand{\tvec}{\mathbf t}\) \(\newcommand{\uvec}{\mathbf u}\) \(\newcommand{\vvec}{\mathbf v}\) \(\newcommand{\wvec}{\mathbf w}\) \(\newcommand{\xvec}{\mathbf x}\) \(\newcommand{\yvec}{\mathbf y}\) \(\newcommand{\zvec}{\mathbf z}\) \(\newcommand{\rvec}{\mathbf r}\) \(\newcommand{\mvec}{\mathbf m}\) \(\newcommand{\zerovec}{\mathbf 0}\) \(\newcommand{\onevec}{\mathbf 1}\) \(\newcommand{\real}{\mathbb R}\) \(\newcommand{\twovec}[2]{\left[\begin{array}{r}#1 \\ #2 \end{array}\right]}\) \(\newcommand{\ctwovec}[2]{\left[\begin{array}{c}#1 \\ #2 \end{array}\right]}\) \(\newcommand{\threevec}[3]{\left[\begin{array}{r}#1 \\ #2 \\ #3 \end{array}\right]}\) \(\newcommand{\cthreevec}[3]{\left[\begin{array}{c}#1 \\ #2 \\ #3 \end{array}\right]}\) \(\newcommand{\fourvec}[4]{\left[\begin{array}{r}#1 \\ #2 \\ #3 \\ #4 \end{array}\right]}\) \(\newcommand{\cfourvec}[4]{\left[\begin{array}{c}#1 \\ #2 \\ #3 \\ #4 \end{array}\right]}\) \(\newcommand{\fivevec}[5]{\left[\begin{array}{r}#1 \\ #2 \\ #3 \\ #4 \\ #5 \\ \end{array}\right]}\) \(\newcommand{\cfivevec}[5]{\left[\begin{array}{c}#1 \\ #2 \\ #3 \\ #4 \\ #5 \\ \end{array}\right]}\) \(\newcommand{\mattwo}[4]{\left[\begin{array}{rr}#1 \amp #2 \\ #3 \amp #4 \\ \end{array}\right]}\) \(\newcommand{\laspan}[1]{\text{Span}\{#1\}}\) \(\newcommand{\bcal}{\cal B}\) \(\newcommand{\ccal}{\cal C}\) \(\newcommand{\scal}{\cal S}\) \(\newcommand{\wcal}{\cal W}\) \(\newcommand{\ecal}{\cal E}\) \(\newcommand{\coords}[2]{\left\{#1\right\}_{#2}}\) \(\newcommand{\gray}[1]{\color{gray}{#1}}\) \(\newcommand{\lgray}[1]{\color{lightgray}{#1}}\) \(\newcommand{\rank}{\operatorname{rank}}\) \(\newcommand{\row}{\text{Row}}\) \(\newcommand{\col}{\text{Col}}\) \(\renewcommand{\row}{\text{Row}}\) \(\newcommand{\nul}{\text{Nul}}\) \(\newcommand{\var}{\text{Var}}\) \(\newcommand{\corr}{\text{corr}}\) \(\newcommand{\len}[1]{\left|#1\right|}\) \(\newcommand{\bbar}{\overline{\bvec}}\) \(\newcommand{\bhat}{\widehat{\bvec}}\) \(\newcommand{\bperp}{\bvec^\perp}\) \(\newcommand{\xhat}{\widehat{\xvec}}\) \(\newcommand{\vhat}{\widehat{\vvec}}\) \(\newcommand{\uhat}{\widehat{\uvec}}\) \(\newcommand{\what}{\widehat{\wvec}}\) \(\newcommand{\Sighat}{\widehat{\Sigma}}\) \(\newcommand{\lt}{<}\) \(\newcommand{\gt}{>}\) \(\newcommand{\amp}{&}\) \(\definecolor{fillinmathshade}{gray}{0.9}\)- 8.1: Introduction to Karnaugh Mapping
- This page discusses Karnaugh maps as a useful tool for simplifying digital logic with four or more Boolean variables, alleviating the tedium of Boolean algebra. While easier for two or fewer variables, Karnaugh maps efficiently handle up to six variables and can accommodate eight. For complex cases, automated design tools like PALASM and Verilog are suggested. The chapter also introduces Venn diagrams as a foundational concept for understanding Karnaugh maps.
- 8.2: Venn Diagrams and Sets
- This page covers Venn diagrams as visual tools for depicting logical relationships between sets in mathematics. It explains the distinctions between "OR" and "AND" in relation to "union" and "intersection," linking these ideas to Boolean algebra and Karnaugh maps.
- 8.3: Boolean Relationships on Venn Diagrams
- This page covers Venn diagrams and Boolean expressions, demonstrating how to visualize overlapping regions for Boolean functions. It details deriving AND and OR functions and complements through these diagrams while emphasizing the link between Venn diagrams and Boolean algebra for formal proofs. Examples such as A'B and (A' + B')' are provided to illustrate the concepts, along with a note on how the size of regions changes with additional variables.
- 8.4: Making a Venn Diagram Look Like a Karnaugh Map
- This page explains how to convert Venn diagrams into Karnaugh maps for one and three variables. It starts by transforming circle A into a rectangular space and defining the regions A and A’. It then shows how to overlay diagrams for variables A and B, pointing out overlaps such as AB. The page emphasizes that Karnaugh maps help simplify Boolean expressions by organizing cells based on variable combinations, concluding with two equivalent versions of a 3-variable Karnaugh map for convenience.
- 8.5: Karnaugh Maps, Truth Tables, and Boolean Expressions
- This page explains the Karnaugh map, created by Maurice Karnaugh in 1953, and its effectiveness in simplifying digital logic functions compared to Boolean algebra. It describes the layout of K-maps, their relation to truth tables, and provides examples for transferring truth table outputs to K-maps, grouping cells, and formulating simplified Boolean expressions.
- 8.6: Logic Simplification With Karnaugh Maps
- This page explains the importance of Karnaugh maps (K-maps) in simplifying Boolean logic, highlighting their real-world applications. It introduces the Gray code sequence, which helps organize K-map outputs by ensuring adjacent cells differ by one bit. The page includes examples of 3-variable K-map simplifications and features a case study on using K-maps for a toxic waste incinerator, showcasing their advantages over traditional Boolean algebra methods.
- 8.7: Larger 4-variable Karnaugh Maps
- This page explains how Karnaugh maps (K-maps) simplify Boolean expressions, especially with four variables. It compares K-maps favorably to Boolean algebra for their efficiency in handling complex reductions. The page illustrates grouping strategies, such as pairing and forming larger groups, and stresses the significance of grouping in powers of two. It also mentions the possibility of multiple minimal solutions, contributing to effective logic designs with reduced gate usage.
- 8.8: Minterm vs. Maxterm Solution
- So far we have been finding Sum-Of-Product (SOP) solutions to logic reduction problems. For each of these SOP solutions, there is also a Product-Of-Sums solution (POS), which could be more useful, depending on the application. Before working a Product-Of-Sums solution, we need to introduce some new terminology.
- 8.9: Sum and Product Notation
- This page introduces key terminology for minterms and maxterms in Karnaugh maps, explaining symbols like "Σ" for sums and "Π" for products. It describes how to represent lists of minterms and maxterms using K-map cell addresses and emphasizes that Sum-Of-Products and Product-Of-Sums solutions are unaffected by the terminology. Examples are provided to illustrate the listing process in K-map format.
- 8.10: Don’t Care Cells in the Karnaugh Map
- This page covers logic reduction using "don't cares" in incomplete truth tables and Karnaugh maps, highlighting its practical application in BCD encoding and real-world scenarios. It illustrates how ignoring certain input combinations simplifies logic design, exemplified by creating optimized logic equations for a stationary bicycle lamp display using an analog-to-digital converter.
- 8.11: Larger 5 and 6-variable Karnaugh Maps
- This page explains the use of Karnaugh maps (K-maps) for simplifying logic designs, recommending a maximum of six inputs for effectiveness. It contrasts older and newer K-map styles and details their application in identifying prime numbers and creating digital circuits, such as a 3-bit magnitude comparator. The page also discusses logic simplification techniques, K-map cell organization, and their role in achieving cost-effective circuit design solutions.