Mainly Tech projects on Python and Electronic Design Automation.

Tuesday, March 16, 2010

Expressions to Truth-Tables

I had a need for the data in the truth tables for a standard cell library, rather like that shown here if you look at say page 35 you will see that for for every Cell it gives the cell name; the cell function as a boolean expression, and the truth-table for the cell.

My cell library was an Infineon one and I had the pdf version of the databook. A quick squirt through pdftotext scrambled the truth table, but did preserve the boolean expression of each cells' function, and the cell name.

I wrote a Python script that used a multi-line regexp to extract each cells info including the boolean equation.

The equation from the Infineon databook uses +,*, and ! for boolean or, and and not operators, but also used lots of parentheses so that operator precedence did not affect the value of the infix expression. I realised that I could substitute for the Python bitwise operators, and form a python expression that could then be evaluated with appropriate values for any input names to create a truth table.

I have left out the parsing and present a function to create a truth-table from a boolean expression:

from itertools import product

def truthtable(expressionstring):
comp = compile(expressionstring.strip(), '-', 'eval')
inputs = sorted(comp.co_names)
table = {}
for values in product( *([(0,1)] * len(inputs)) ):
valuedict = dict(zip(inputs, values))
answer = eval(comp, valuedict)
table[values] = answer
return expressionstring.strip(), inputs, table

def pptable(ex, inputs, table):
print("\nTRUTH-TABLE FOR EXPRESSION: %r\n" % ex)
print(' ' + ' '.join('%2s' % inp for inp in inputs) + ': OUTPUT')
fmt = ' %i' * len(inputs) + ': %i'
for inp, ans in sorted(table.items()):
print(fmt % tuple(list(inp) + [ans]))

ex, inputs, table = truthtable('(A & (~C)) | D')
pptable(ex, inputs, table)

Going through function truthtable:
  • compile() gives access to all the names in the compiled expression via attribute .co_names - this is all the names used in the expression.
  • product() allows you to quickly generate the 1/0 value combinations for the input names.
  • valuedict assigns a value to each name used in the expression.
  • eval evaluates the expression with the given values on each name
The output of the program is:


0 0 0: 0
0 0 1: 1
0 1 0: 0
0 1 1: 1
1 0 0: 1
1 0 1: 1
1 1 0: 0
1 1 1: 1

- No separate parser required!


  1. No separate parser is required if you only use the three boolean operators that your language supports. There're sixteen boolean infix operators, not counting various boolean comparators and negation.
    ________________________ Gerard Schildberger

  2. Unfortunately the standard cell library truth-table equations were not written in python - hence the need for translation.



Subscribe Now: google

Add to Google Reader or Homepage

Go deh too!