Digital Logic Toolkit

Digital Logic Toolkit — About

Source
https://digitallogictoolkit.com/about/
Printed

About the Digital Logic Toolkit

What this is, who made it, and the Shannon–Karnaugh–Hamming lineage behind it.

This is a free, in-browser workbench for the first- and second-year digital logic syllabus: Boolean algebra, truth tables, Karnaugh maps, logic gates, number systems and error-correcting codes. There are no accounts, no paywalls, no result limits and no feature gates. Everything runs in your browser, works offline after the first visit, and prints cleanly.

Why it exists

A student with a homework sheet has a specific, bounded question and about ten seconds of patience for it. The tools that currently answer those questions mostly give a bare result with no working, and several of them are wrong or admit that they might be. One widely used simplifier prints “WARNING: Solution is not complete” when its rewrite rules run out. Another teaches that Karnaugh map groups “must be powers of 2 (1, 2, 4)”, omitting 8 and 16 — which are exactly the groups that produce single-literal answers. A third says of itself: “I have tried to be sure that it is accurate but I can not guarantee it.”

This site is built on the opposite premise. The answer is computed by an algorithm that is known to be exact, the working is generated to narrate that already-proven answer, and the test suite is published rather than replaced by a disclaimer.

The lineage

The algebra. George Boole published An Investigation of the Laws of Thought in 1854, giving a symbolic calculus in which the variables take only two values. Augustus De Morgan, whose Formal Logic had appeared in 1847, contributed the two duality laws that carry his name. For eighty years this remained a branch of logic with no machinery attached to it.

The hinge. In 1937 Claude Shannon, then a twenty-one-year-old master’s student at MIT working on Vannevar Bush’s differential analyser, observed that a network of relay switches obeys exactly Boole’s algebra: a series pair is a conjunction, a parallel pair is a disjunction, a normally-closed contact is a complement. He submitted the argument as his master’s thesis and published it in 1938 as A Symbolic Analysis of Relay and Switching Circuits. It is the reason a truth table and a circuit diagram are two views of one object, and it is why this site can convert any representation into any other. Howard Gardner later called it “possibly the most important, and also the most famous, master’s thesis of the century.”

Minimisation. Edward Veitch published a chart method for simplifying truth functions in 1952; Maurice Karnaugh reorganised the chart’s axes into reflected-binary order the following year, which is the change that makes physical adjacency on the page mean logical adjacency in the algebra. That is the Karnaugh map. Because a map stops being readable past about six variables, Willard Van Orman Quine’s two papers of 1952 and 1955 and Edward McCluskey’s of 1956 gave a tabular method that generalises: generate every prime implicant by pairwise combination, then choose a minimum cover of the minterms. When the cover choice is not forced, Stanley Petrick’s 1956 report gives the exact way to enumerate every minimum cover rather than picking one — which is why this site can tell you that a function has three equally minimal answers instead of showing you one of them.

Information. Shannon’s second contribution, A Mathematical Theory of Communication (1948), defined the entropy H = −Σ pᵢ log₂ pᵢ as the average information per symbol, and with it the floor that no lossless code can beat. Richard Hamming, working at Bell Labs on a relay machine that halted on every detected error over the weekend, published Error Detecting and Error Correcting Codes in 1950: put the parity bits at the power-of-two positions and the syndrome, read as a binary number, is the position of the flipped bit. David Huffman, as a graduate student in Robert Fano’s class at MIT in 1952, found the optimal prefix code by building the tree upward from the two least likely symbols. Frank Gray’s reflected binary code, patented in 1953 from a 1947 filing, is the ordering that makes a Karnaugh map work and that keeps a mechanical encoder from producing a garbage reading mid-transition.

Everything on this site is a consequence of those nine papers.

How we know the answers are right

  • Minimisation is exact, and says so. Two-level minimisation runs Quine–McCluskey with a full prime-implicant chart, essential-implicant extraction, row and column dominance, and Petrick’s method for the cyclic core. The result carries a badge stating the term and literal count and the word exact. Above eight variables the exact path is replaced by the Espresso-II heuristic and the badge says near-minimal (Espresso heuristic) instead. We never print an answer without saying which of those two it is.
  • All minimal forms, not one. Column dominance, which most textbook walkthroughs apply, provably discards alternative minimum covers. We therefore run two pipelines: one with full dominance for the clean narrative, and one with row dominance only to enumerate every minimum cover. Where a function has several equally minimal answers, you get all of them.
  • Product of sums is derived, not dualised. The minimal POS is obtained by minimising the OFF-set as a sum of products with the same don’t-care set and applying De Morgan to each cube. The dual is a different function and using it is a common and silent error.
  • Every step is checked. In test builds, every rewrite step is verified against the original function’s truth-table bitmask before it is shown. A rewriting bug becomes a failing test, not a wrong answer on a student’s screen.
  • The suite is published. All 65,536 Boolean functions of four variables are minimised and checked against brute force. Above that, randomised differential testing runs against Berkeley Espresso’s exact mode and its equivalence checker. The number-systems and coding tools are tested against published vectors: the RevEng CRC catalogue’s check and residue values, IEEE 754-2019’s own encodings, RFC 1071’s worked example, RFC 1951’s canonical Huffman example, and the (7,4) Hamming flip sweep in which flipping bit k must produce syndrome k for every k from 1 to 7.

Notation and standards

Textbooks genuinely differ, so this site states its conventions rather than assuming yours.

  • Operators accepted: AND as ·, *, &, &&, ∧, or juxtaposition (AB); OR as +, |, ||, ∨; NOT as a prefix ¬, ~, ! or a postfix ′, or an overbar on paste; XOR as ⊕, ^, xor; XNOR as ⊙, xnor; NAND as ↑, nand; NOR as ↓, nor; implication as →, ->, =>; biconditional as ↔, <->, <=>. The word forms AND OR NOT XOR XNOR NAND NOR are accepted everywhere.
  • | is OR, never the Sheffer stroke. In pure logic notation | sometimes means NAND; in every programming language it means OR, and that is what we use. NAND is ↑.
  • ^ is XOR, never exponentiation.
  • Default precedence, highest to lowest: parentheses; NOT and the postfix prime; AND (including juxtaposition); XOR and XNOR; NAND and NOR; OR; implication (right associative); biconditional. This matches the Wolfram Language and the C family. There is no universal convention for XOR’s level — VHDL refuses to pick one and makes unbracketed mixing a syntax error — so we always echo the fully parenthesised reading back to you and warn when XOR, XNOR, NAND or NOR is mixed with AND or OR without brackets.
  • The overbar is a grouping symbol. Its extent is its operand, which plain text cannot express. Use ′ or ¬(…) when typing; overbars are rendered in output and accepted on paste.
  • Gate symbols: both ANSI/IEEE Std 91-1984 distinctive shapes and IEC 60617-12 rectangular shapes are provided, and your choice is remembered. The IEEE shapes are drawn on the standard’s own 26-unit grid. IEC 60617-12’s exact metrics are behind a paywall, so our rectangular symbols are drawn from the published module-grid construction and are a reasonable construction rather than quoted dimensions; we say so on the symbols page too.
  • Bit order: in a truth table the leftmost input column is the most significant bit, and minterm indices are numbered accordingly.

Corrections

If a result here disagrees with your textbook, we want to know, and there is a good chance the disagreement is a stated convention rather than an error — tie-breaking in Huffman coding, XOR precedence, and the choice between the position-ordered and systematic Hamming parity-check matrices all differ legitimately between courses. Every page states which convention it uses. Report anything else at corrections@digitallogictoolkit.com (opens in a new tab) and include the exact input.

References

  1. Boole, G. An Investigation of the Laws of Thought, on Which are Founded the Mathematical Theories of Logic and Probabilities. Walton and Maberly, London, 1854. Project Gutenberg (opens in a new tab)
  2. De Morgan, A. Formal Logic: or, The Calculus of Inference, Necessary and Probable. Taylor and Walton, London, 1847. Internet Archive (opens in a new tab)
  3. Shannon, C. E. “A Symbolic Analysis of Relay and Switching Circuits.” Transactions of the American Institute of Electrical Engineers 57(12): 713–723, December 1938. (Submitted as an MIT master’s thesis in electrical engineering, 1937.) doi:10.1109/T-AIEE.1938.5057767 (opens in a new tab)
  4. Veitch, E. W. “A Chart Method for Simplifying Truth Functions.” Proceedings of the 1952 ACM National Meeting (Pittsburgh): 127–133, 1952. doi:10.1145/609784.609801 (opens in a new tab)
  5. Karnaugh, M. “The Map Method for Synthesis of Combinational Logic Circuits.” Transactions of the AIEE, Part I: Communication and Electronics 72(5): 593–599, November 1953. doi:10.1109/TCE.1953.6371932 (opens in a new tab)
  6. Quine, W. V. “The Problem of Simplifying Truth Functions.” The American Mathematical Monthly 59(8): 521–531, October 1952. doi:10.1080/00029890.1952.11988183 (opens in a new tab)
  7. Quine, W. V. “A Way to Simplify Truth Functions.” The American Mathematical Monthly 62(9): 627–631, November 1955. doi:10.2307/2307285 (opens in a new tab)
  8. McCluskey, E. J. “Minimization of Boolean Functions.” Bell System Technical Journal 35(6): 1417–1444, November 1956. doi:10.1002/j.1538-7305.1956.tb03835.x (opens in a new tab)
  9. Petrick, S. R. A Direct Determination of the Irredundant Forms of a Boolean Function from the Set of Prime Implicants. Air Force Cambridge Research Center Technical Report AFCRC-TR-56-110, Bedford, Massachusetts, April 1956.
  10. Shannon, C. E. “A Mathematical Theory of Communication.” Bell System Technical Journal 27: 379–423 (July 1948) and 623–656 (October 1948). doi:10.1002/j.1538-7305.1948.tb01338.x (opens in a new tab)
  11. Hamming, R. W. “Error Detecting and Error Correcting Codes.” Bell System Technical Journal 29(2): 147–160, April 1950. doi:10.1002/j.1538-7305.1950.tb00463.x (opens in a new tab)
  12. Huffman, D. A. “A Method for the Construction of Minimum-Redundancy Codes.” Proceedings of the IRE 40(9): 1098–1101, September 1952. doi:10.1109/JRPROC.1952.273898 (opens in a new tab)
  13. Gray, F. Pulse Code Communication. US Patent 2,632,058, filed 13 November 1947, granted 17 March 1953. US 2,632,058 (opens in a new tab)
  14. Brayton, R. K., Hachtel, G. D., McMullen, C. T., Sangiovanni-Vincentelli, A. L. Logic Minimization Algorithms for VLSI Synthesis. Kluwer, 1984. (The Espresso heuristic used above eight variables.) doi:10.1007/978-1-4613-2821-6 (opens in a new tab)
  15. Moffat, A. “Huffman Coding.” ACM Computing Surveys 52(4), Article 85, August 2019. (The tie-breaking rule this site implements, and the reason it is stated on the page.) doi:10.1145/3342555 (opens in a new tab)
  16. IEEE Std 91-1984 and IEEE Std 91a-1991, IEEE Standard Graphic Symbols for Logic Functions. Institute of Electrical and Electronics Engineers. IEEE Xplore (opens in a new tab)
  17. IEC 60617-12, Graphical Symbols for Diagrams — Part 12: Binary Logic Elements. International Electrotechnical Commission. IEC Webstore (opens in a new tab)
  18. IEEE Std 754-2019, IEEE Standard for Floating-Point Arithmetic. IEEE SA (opens in a new tab)
  19. RFC 1071, Computing the Internet Checksum, September 1988; RFC 1624, Computation of the Internet Checksum via Incremental Update, May 1994. RFC 1071 (opens in a new tab)
  20. RFC 3629, UTF-8, a Transformation Format of ISO 10646, November 2003. RFC 3629 (opens in a new tab)
  21. RFC 1951, DEFLATE Compressed Data Format Specification version 1.3, May 1996. (§3.2.2, canonical Huffman codes.) RFC 1951 (opens in a new tab)
  22. Williams, R. N. A Painless Guide to CRC Error Detection Algorithms, 1993, and the RevEng CRC catalogue (the eight-parameter model this site’s CRC tool uses). RevEng CRC catalogue (opens in a new tab)

Petrick’s 1956 report is cited from the form used consistently in the minimisation literature; the original technical report is not available online from a primary archive. Shannon’s remark about the thesis being “possibly the most important master’s thesis of the century” is Howard Gardner’s, quoted in the secondary literature, not Shannon’s own.

Where to go next

  • Boolean & Minimisation

    Turn one expression into every other form of itself, and reduce it with named laws.

  • Gates & Circuits

    What each gate does, in both symbol standards, and how to build circuits out of them.

  • Numbers & Codes

    Convert between bases and representations, and check the codes that detect and fix errors.