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:

TRUTH-TABLE FOR EXPRESSION: '(A & (~C)) | D'

A C D: OUTPUT
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!

2 comments:

  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

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

    ReplyDelete

Followers

Subscribe Now: google

Add to Google Reader or Homepage

Go deh too!

whos.amung.us