maehw / wokwi-lookup-table-generator

Generator for wokwi schematics that implement lookup tables in conjunctive normal form (CNF), i.e. with AND and OR gates

Wokwi lookup table (LUT) generator

What is this all about?

This git repository contains a generator for wokwi schematics that implement lookup tables (defined by a truth table and some more meta data in a JSON file, see the ./demos subdirectory.

But what is wokwi? Wokwi is a free, browser-based simulator that supports different Arduino and several other boards and components (such as LEDs, buttons, switches, sensors, ...).

It can also be used during #TinyTapeout events. TinyTapeout is an educational project that "aims to make it easier and cheaper than ever to get your digital designs manufactured on a real chip". So oversimplified you can also easily simulate and generate ASIC designs - from a very simple boolean algebra design description (truth tables). Actually, this script started during the first #TinyTapeout event in August/September 2022

How does this work internally? See a separate section below the "Usage" section

Language: This project is written in Python3.

Note This project is work in progress. It is known that not all designs are generated correctly, so there are still some bugs.

Usage

To get a list of the available options, use option --help:

% python generate.py --help
usage: generate.py [-h] [-v] [-f IN_FILE] [-o OUT_FILE] [-p] [-c] [-t] [-tt] [-tt3]

generate.py is a lookup table generator tool for wokwi

options:
  -h, --help            show this help message and exit
  -v, --verbose         log level (-v: INFO, -vv: DEBUG) (default: 0)
  -f IN_FILE, --file IN_FILE
                        path to JSON logic input file; if none is given, stdout is used (default: logic.json)
  -o OUT_FILE, --outfile OUT_FILE
                        path to generated wokwi schematic file (default: None)
  -p, --parts_only      dump wokwi parts list only (default: False)
  -c, --connections_only
                        dump wokwi connections list only (default: False)
  -t, --test            add an Arduino MEGA as test framework and generate Arduino verification code (default: False)
  -tt, --tinytapeout    add default parts used in tinytapeout 1/2 wokwi template schematic (default: False)
  -tt3, --tinytapeout3  add default parts used in tinytapeout 3 wokwi template schematic (default: False)

Examples:

Specifying an input file name (using option -f) and an output file (using option -o) for the wokwi schematic:

python3 generate.py -f ./demos/2bit_half_adder.logic.json -o 2bit_half_adder.diagram.json

You specifically want to generate a design that can be used for #TinyTapeout 3? Use option --tinytapeout3/-tt3 to add the default parts. Example:

python3 generate.py -f ./demos/2bit_half_adder.logic.json -o 2bit_half_adder.diagram.json -tt3

Only specifying the input file name (using option -f) and leaving out the optional output file specification, will dump the wokwi schematic via stdout:

python3 generate.py -f ./demos/2bit_half_adder.logic.json

Only specifying the input file name (using option -f), will dump the wokwi schematic via stdout (piped to /dev/null), log level DEBUG:

python3 generate.py -f ./demos/2bit_half_adder.logic.json -vv > /dev/null

Specify an output file for the wokwi schematic externally but also show contents on stdout by piping it through tee:

python3 generate.py -f ./demos/2bit_half_adder.logic.json | tee 2bit_half_adder.diagram.json

Switches -p and -c allow to limit the dump to wokwi parts ony respectively wokwi connections only.

This feature can be used to modify existing designs only. The following command can be used on Mac OS X to copy the parts of the design into the paste buffer:

python3 generate.py -f ./demos/bcd_7segment_lut.logic.json -p | sed 's/[{}]//' | pbcopy

Specify an output file for the wokwi schematic; also generate an Arduino sketch for automated verification and add and connect an Arduino MEGA in the wokwi schematic:

python3 generate.py -f ./demos/2bit_half_adder.logic.json -o 2bit_half_adder.diagram.json -t

Using generated designs

After having generated your output diagram JSON file, ...

1. go to wokwi.com
2. start a new project (e.g. choosing "Arduino Nano", that's not really relevant for the logic designs unless you want to control/test them with an Arduino or other microcontroller; however, all components will be deleted in the next steps)
3. switch the editor view from tab sketch.ino to tab diagram.json
4. select all the text in the editor and delete it
5. paste the contents of the generated JSON files
6. add components on the input and output side of your design
7. have fun simulating everything

Warning When using an 8-pin DIP switch for the inputs, make sure to connect one end to VCC and the other end to a pull-down resistor (connected to GND). Otherwise the output may act in a non-deterministic way.

Note

• You currently need to optimize the wires of your layout manually.
• You can add textual descriptions to your schematic using parts of type wokwi-text.

Installation and dependencies

Resolve all requirements using pip3:

pip3 install -r requirements.txt

This project depends on the package quine-mccluskey a Python implementation of the Quine McCluskey algorithm.

The author says:

This implementation of the Quine McCluskey algorithm has no inherent limits (other than the calculation time) on the size of the inputs.

Warning The Quine McCluskey algorithm currently does not give deterministic results. An issue has been opened here.

Demo designs

For descriptions of the demo designs, inspect their JSON files in the ./demos subdirectory of this repo.

Warning The Quine McCluskey algorithm currently does not give deterministic results. An issue has been opened here.

Some demos are working, some seem to cause trouble.

Working demos

• 2bit_half_adder.logic.json: 2-bit half adder; (Wokwi demo project)

• 2bit_full_adder.logic.json: 2-bit full adder; (Wokwi demo project)

• 2bit_and.logic.json: 2-bit AND (Wokwi demo project); (as simple as an AND gate, but generated using a truth table)

• 2bit_or.logic.json: 2-bit OR (Wokwi demo project); (as simple as an OR gate, but generated using a truth table)

• limited-ascii_7segment_lut.logic.json: limited ASCII character range to 7-segment Wokwi display; (basic Wokwi demo project, advanced Wokwi demo project cycling through the character set with an Arduino and showing the outputs on a common cathose 7-segment display)

Non-working demos

• 4bit_popcount.json: 4-bit popcount (makes the generator hang up)

Termination of unused gate inputs

I have basically identified two termination strategies:

The unused input pin of a 2 input AND gate can

1. either be pulled HIGH or
2. be connected to the other input

The unused input pin of a 2 input OR gate can

1. either be pulled LOW or
2. be connected to the other input

In the past I had used the first approach which takes more effort (adding a GND and a VCC block and adding connections to it). I've switch to the second approach as this can be realized by adding a short wire connection from one inport to the other - and it's generic for AND and OR gates.

How does this work internally?

The generator is fed with a truth table describing the boolean algebra to be implemented.

The generator implements the lookup tables (truth tables) in conjunctive normal form (CNF)**, i.e. with AND and OR gates.

Let's have a look at the example of a 2-bit half adder: "Logic that adds two numbers and produces a sum bit (S) and carry bit (C)."

The truth table looks as follows (a and b are inputs, S (sum) and C (carry) are outputs):

a	b	S	C
0	0	0	0
0	1	1	0
1	0	1	0
1	1	0	1

This can also be written as equations with functions of boolean algebra (using so called minterms):

S = ~a*b + a*~b
C = a*b

where

• ~ represents inversion (a NOT gate),
• * represents a logical AND(an AND gate),
• + represents a logical OR an OR gate).

That also explains the term "sum of products" (SOP).

For better readability the * are often omitted, leaving us with:

S = ~ab + a~b
C = ab

The conversion from truth table to boolean algebra is done with a Python implementation of the Quine McCluskey algorithm. Please note that these optimizations are not really required as the ASIC toolchain will take care of optimization (and know the kind of hardware cells being available on the target hardware), but it helps to understand own digital designs and their implementation.

The algorithm basically performs the following steps (be careful as this concept image does not match the previously used example):

• Insert buffers for the inputs and NOT gates for the inverted inputs (green step)
• Insert AND gates and connect pairs of inputs to those AND gates (make products of two multiplicands; first yellow step)
• Insert more AND gates and connect them so that a single product ends with one final AND gate to get a summand for the additional stage (second yellow step)
• Insert OR gates and connect pairs of inputs to those OR gates (make sums of two summands; first blue step)
• Insert more OR gates and connect them so that a single sum ends with one final OR gate to get the final output for the boolean algebraic function

Further read: Département d'informatique et de recherche opérationnelle - Université de Montréal: LOGIC SYNTHESIS AND TWO LEVEL LOGIC OPTIMIZATION

Tiny Tapeout

See also:

• https://tinytapeout.com/
• Tiny Tapeout 2 Guide - Generating and verifying wokwi designs with combinational logic

Contribution

Feel free to contribute, open issues, work on existing issues, etc. To contribute to the project, fork this GitHub repository and create a pull request. Detailed instructions can be found at https://docs.github.com/en/get-started/quickstart/contributing-to-projects. I'll be happy to review the code diff and eventually merge it into the original repo here.

Some TODOs or ideas are already visible in the issues tab. Especially have a look at the issues labeled good first issue and help wanted.

TODOs

• document limitations
• add assertions
• use a more object-oriented approach for everything
• implement interactive mode
• perform sanity checks to see if all parts are connected, some may be unused due to bugs (probably rounding)

wokwi-lookup-table-generator's Issues

C bit not set for 8

wokwi-lookup-table-generator/demos/bcd_7segment_lut.logic.json

Line 8 in 2b20f96

"C": [1, 1, 0, 1, 1, 1, 1, 1, 0, 1, 0, 0, 0, 0, 0, 0],

generate.py failure case

This input file causes generate.py to crash:

{
  "version": 1,
  "description": "Generates patterns.",
  "inputs": ["t", "u"],
  "outputs": {
    "A": [1, 0, 0, 0],
    "G": [0, 0, 0, 1]
  }
}

Here is the output from the failing run:

$ python3 generate.py -v -f logic.json -o logic.wokwi
[    INFO] Log level: INFO
[    INFO] Data is read from input file 'logic.json'
[    INFO] Inputs:     2 ['t', 'u']
[    INFO] Outputs:    2 ['A', 'G']
[    INFO]   Output A: [1, 0, 0, 0]; ones: [0]
[    INFO]   Output G: [0, 0, 0, 1]; ones: [3]
Traceback (most recent call last):
  File "/home/osboxes/src/wokwi-lookup-table-generator/generate.py", line 441, in <module>
    logic_meta[output]["qm_terms_raw"] = list( q.simplify(logic[output]) ) # convert set into list (to allow indexing)
  File "/home/osboxes/venvs/py/lib/python3.9/site-packages/quine_mccluskey/qm.py", line 130, in simplify
    return self.simplify_los(ones, dc)
  File "/home/osboxes/venvs/py/lib/python3.9/site-packages/quine_mccluskey/qm.py", line 193, in simplify_los
    essential_implicants = self.__get_essential_implicants(prime_implicants, set(dc))
  File "/home/osboxes/venvs/py/lib/python3.9/site-packages/quine_mccluskey/qm.py", line 419, in __get_essential_implicants
    perms[t] = set(p for p in self.permutations(t) if p not in dc)
  File "/home/osboxes/venvs/py/lib/python3.9/site-packages/quine_mccluskey/qm.py", line 419, in <genexpr>
    perms[t] = set(p for p in self.permutations(t) if p not in dc)
  File "/home/osboxes/venvs/py/lib/python3.9/site-packages/quine_mccluskey/qm.py", line 532, in permutations
    if value[i] == '0' or value[i] == '1':
IndexError: string index out of range

If I change the line for "A" to:

    "A": [0, 0, 1, 0],

then generate.py succeeds:

$ python3 generate.py -v -f logic.json -o logic.wokwi
[    INFO] Log level: INFO
[    INFO] Data is read from input file 'logic.json'
[    INFO] Inputs:     2 ['t', 'u']
[    INFO] Outputs:    2 ['A', 'G']
[    INFO]   Output A: [0, 0, 1, 0]; ones: [2]
[    INFO]   Output G: [0, 0, 0, 1]; ones: [3]
[    INFO] Calculated CNF for output A: t~u
[    INFO] Calculated CNF for output G: tu
[    INFO] Estimated parts usage:
[    INFO]     *   4 buffers (for the inputs and the outputs)
[    INFO]     *   2 NOT gate(s) (for the negated inputs)
[    INFO]     *   2 two-input AND gate(s), in max. 1 stages
[    INFO]     * number of two-input OR gate(s) not estimated yet
[    INFO] 
[    INFO] Connecting inputs with first stage of AND gates for every output.
[    INFO] Connecting input inside the wokwi design to first AND gate stage (later used for output A)...
[    INFO] All AND gates required in the first AND gate stage for output A: [[0]]
[    INFO] Connecting input inside the wokwi design to first AND gate stage (later used for output G)...
[    INFO] All AND gates required in the first AND gate stage for output G: [[1]]
[    INFO] Connecting inputs with first stage of AND gates for every output completed.
[    INFO] 
[    INFO] Merges all first stage AND gates down to a single 'root' AND gate (for every term of every output)
[    INFO] Single AND gate #0 does not need to be merged.
[    INFO] Remaining AND gates (final stage): [0] for the output A to be connected to OR gates
[    INFO] Single AND gate #1 does not need to be merged.
[    INFO] Remaining AND gates (final stage): [1] for the output G to be connected to OR gates
[    INFO] Merges of all first stage AND gates down to a single 'root' AND gate completed.
[    INFO] 
[    INFO] Combining mini terms: Create first stage of OR gates (in order to OR all terms for every output) 
[    INFO] and connect the AND gate from the previous stage (=the final AND stage) to it.
[ WARNING] Single mini term for output A: AND gate output (AND gate #0)
[ WARNING] Creating a dummy OR gate (which does not need to be then merged down).
[    INFO] First stage of OR gates (connected to AND gates): [0] for output A
[ WARNING] Single mini term for output G: AND gate output (AND gate #1)
[ WARNING] Creating a dummy OR gate (which does not need to be then merged down).
[    INFO] First stage of OR gates (connected to AND gates): [1] for output G
[    INFO] Done combining mini terms (AND gates) by first stage of OR gates.
[    INFO] 
[    INFO] Merges all first stage OR gates down to a single 'root' OR gate and connect them to the output buffers
[    INFO] Performing the merges of all OR gates for output A
[    INFO] Number of OR gates to be merged: 1, i.e. [0]
[    INFO] Only single OR gate, therefore directly connect it to the output buffer
[    INFO] Identified #0 as final OR gate for the output A to be connected to output buffer
[    INFO] Performing the merges of all OR gates for output G
[    INFO] Number of OR gates to be merged: 1, i.e. [1]
[    INFO] Only single OR gate, therefore directly connect it to the output buffer
[    INFO] Identified #1 as final OR gate for the output G to be connected to output buffer
[    INFO] Max AND gate stages: 1
[    INFO] Max  OR gate stages: 1
[    INFO] Finished the wokwi design!
[    INFO] Writing final wokwi design file 'logic.wokwi'...

(PS: Love the idea of this tool. Thank you for writing it!!)

Tool to generate the JSON input file from the truth table

It would even be easier if nobody would have to write the JSON input files themselves but just add columns and all values in the truth table and then generate the JSON input file from it.

Any ideas & implementations are welcome!

Replace warnings about potential endless loops by timeouts and error messages

The generator may spit out several warning messages like the following:

[ WARNING] Entering potential endless loop (trying to merge AND gates)

This has been added as the generator is known to hang for some designs. The root cause is currently unknown - as it simply has not been analyzed yet.

Design to reproduce: https://github.com/maehw/wokwi-lookup-table-generator/blob/main/demos/4bit-popcount.logic.json

This may be helpful, but is also annoying as the warning messages will appear for every design.

A better way to detect endless loops would be to use timeouts (wait for some time and abort when the loop has not finished yet). Those timeouts may be dynamic as they should grow with the design complexity (or input/output size). But we could also use a static timeout as the machines to run the generator on should not be too low.

Add support for automated in-circuit verification

Wokwi is a great tool. It does not only allow to simulate digital designs and then run some magic to get your own ASIC design out of it. It also allows to write and simulate software on an embedded target such as an Arduino Nano or Arduino Mega.

The designs generated by wokwi-lookup-table-generator are pure combinatorial logic designs. One entry from the truth table (combination of input signals, ones and zeros) directly generates a specific combination of logic levels on the outputs (ones and zeros). This makes testing the designs generated by the generator quite easy:

• The test stimuli can be used from the truth table which is an input for the generator
• The expected outputs of the digital design can also be taken from the truth table

The idea for automated verification is currently experimented with here: https://wokwi.com/projects/342092183606657619

Basic concept:

• Add an Arduino to the wokwi sketch with plenty of I/Os, best choice seems to be the Arduino Mega at the moment
• In the sketch.ino: Configure input and output pins in the setup() routine using the pinMode() function
• Also configure a serial interface by calling Serial.begin(); make sure that the RX and TX pins are not used as input or outputs, but stay reserved to control the inputs of your digital design/ read the outputs from it
• Add support for serialMonitor in your Wokwi design
• Set the inputs of your digital design using a series of calls to digitalWrite()
• Read back the outputs of your digital design using a series of calls to digitalRead()
• Verify that the measured output signals match the logic levels as definged by the output signals in the truth table
• Generate outputs and a test report using the serial console (several calls to Serial.print())

This can all be automated.

I suggest to add a command line flag -t/--in-circuit-test to switch between the normal design generation and a verification design generation with the additional Arduino and the additional connections required for in-circuit verification.

Add support for ABEL (Advanced Boolean Equation Language) truth table design description

"ABEL (Advanced Boolean Equation Language) allows you to enter behavior-like descriptions of a logic circuit. ABEL is an industry-standard hardware description language (HDL) that was developed by Data I/O Corporation for programmable logic devices (PLD). There are other hardware description languages such as VHDL and Verilog. ABEL is a simpler language than VHDL which is capable of describing systems of larger complexity.

ABEL can be used to describe the behavior of a system in a variety of forms, including logic equations, truth tables, and state diagrams using C-like statements. The ABEL compiler allows designs to be simulated and implemented into PLDs such as PALs, CPLDs and FPGAs."

https://web.archive.org/web/20071012234417/http://www.seas.upenn.edu/~ese201/abel/abel_primer.html#Truth

As mentioned on the tinytypeout Discord, it would be nice to support ABEL truth table syntax for inputs.

I would add a preprocessing stage that converts ABEL truth table syntax to the expected JSON format (see demo design progects).

Add command line switch aka flag to add template parts of Tiny Tapeout

This generator has been born as part of Tiny Tapeout 1.
Currently Tiny Tapeout 2 is going on: https://tinytapeout.com/

TinyTapeout is an educational project that makes it easier and cheaper than ever to get your digital designs manufactured on a real chip!

We ran TinyTapeout-01 in August and received 150 submissions in just a couple of weeks. Now we’re getting ready to open submissions for Tiny Tapeout 2!

The wokwi template for Tiny Tapeout 2 can be found here: https://wokwi.com/projects/339800239192932947

It would be useful if the generator also generated the following default parts (and their interconnection):

"parts": [
   {
     "type": "wokwi-dip-switch-8",
     "id": "sw1",
     "top": -178.4,
     "left": -102.9,
     "rotate": 90,
     "attrs": {}
   },
   {
     "type": "wokwi-clock-generator",
     "id": "clock1",
     "top": -278.4,
     "left": -134.4,
     "attrs": {}
   },
   { "type": "wokwi-gnd", "id": "pwr2", "top": -76.8, "left": 892.2, "attrs": {} },
   { "type": "wokwi-vcc", "id": "pwr1", "top": -229.64, "left": -115.2, "attrs": {} },
   {
     "type": "chip-input-8-pins",
     "id": "chip1",
     "top": -190.98,
     "left": -4.8,
     "attrs": { "verilogRole": "input" }
   },
   {
     "type": "chip-output-8-pins",
     "id": "chip2",
     "top": -190.98,
     "left": 686.4,
     "attrs": { "verilogRole": "output" }
   },
   {
     "type": "wokwi-7segment",
     "id": "sevseg1",
     "top": -183.24,
     "left": 878.68,
     "attrs": { "common": "cathode" }
   },
   {
     "type": "wokwi-slide-switch",
     "id": "sw2",
     "top": -302.8,
     "left": -35.3,
     "attrs": { "value": "1" }
   },
   {
     "type": "wokwi-pushbutton",
     "id": "btn1",
     "top": -354.6,
     "left": -146,
     "attrs": { "color": "grey", "label": "Step", "bounce": "0" }
   }

The generated design should also be auto-connected to the "Digital Input Breakout" and "Digital Output Breakout" boards as this is where the digital design should go.

Improve layout of wokwi schematic diagram

The wokwi layout is generated automatically.

At the moment of writing, ...

• ... the OR gates of every stage are only aligned horizontally. Their vertical position can be improved by moving them to a them to the half height (field "top") of the two predecessor gates.
• ... the AND gates cannot even be distinguished by their stage. All AND gates are in the same horizontal position and just laid out one under each other. Both the vertical and horizontal position should be improved.

The goal is to have more tree-like structure in the layout that also helps to visually understand the schematic better. Best: at a first glance.

I would put this as a separate file, so it's more easily updateable when the template changes.

wokwi-lookup-table-generator/generate.py

Line 71 in 2b20f96

wokwi_design = {