Skip to content

Instantly share code, notes, and snippets.

@bivoje
Last active February 21, 2023 04:32
Show Gist options
  • Save bivoje/3a7c7df95b6b7f91491122db3a0af6b5 to your computer and use it in GitHub Desktop.
Save bivoje/3a7c7df95b6b7f91491122db3a0af6b5 to your computer and use it in GitHub Desktop.
Render k-map & Quine-McClusky table from minterms, doesn't care lists
def int2elem(x):
rep = []
for i in range(n):
rep.append(x&1)
x >>= 1;
return tuple(rep)
def elem2int(block):
x = 0
for i,b in enumerate(block):
x |= b << i
return x
def collect_PIs_kmap(ss):
pis = set()
for x in ss:
el = int2elem(x)
pis |= collect_PIs_from(ss, el)
return pis
def collect_PIs_from(ss, block):
ret = set()
for i,b in enumerate(block):
if b == '-': continue
nblock = list(block)
nblock[i] = '-'
nblock = tuple(nblock)
if not is_block_good(ss, nblock): continue
pis = collect_PIs_from(ss, nblock)
ret |= pis
return ret if ret else set([block])
def is_block_good(ss, block):
for el in block_elems(block):
x = elem2int(el)
if x not in ss: return False
return True
def is_in_block(e, block):
for el in block_elems(block):
if e == el: return True
return False
def block_elems(block):
for i,b in enumerate(block):
if b != '-': continue
nblock = list(block)
nblock[i] = 0
for el in block_elems(tuple(nblock)): yield el
nblock[i] = 1
for el in block_elems(tuple(nblock)): yield el
return
yield block
import math
def kmap_table(greys, x, block):
if not greys: return render_cell(ss, x, block)
ret = []
grey = greys[0]
grest = greys[1:]
width = int(round(math.log2(len(grey))))
for g in grey:
nx = (x << width) | g
sub = kmap_table(grest, nx, block)
ret.append(sub)
return ret
def draw_kmap(tags, greys, block):
table = kmap_table(greys, 0, block)
draw_kmap_(tags, greys, table, [])
def draw_kmap_(tags, greys, table, acc):
if len(tags) == 2:
if acc: print(""); print(' '.join(f"{a}={b}" for a,b in acc))
draw_kmap_table(tags[0], tags[1], greys[0], greys[1], table)
return
grey = greys[0]
grest = greys[1:]
tag = tags[0]
trest = tags[1:]
width = int(round(math.log2(len(grey))))
for i,g in enumerate(grey):
acc.append((tag, f"{g:b}".rjust(width,'0')))
draw_kmap_(trest, grest, table[i], acc)
acc.pop()
def draw_kmap_table(tag1, tag2, grey1, grey2, table):
tagwidth = int(round(math.log2(len(grey1))))
colwidth = int(round(math.log2(len(grey2))))
print(f"{tag1} \ {tag2}")
print(' ' * tagwidth + '|' + ' '.join(f"{g:b}".rjust(colwidth,'0') for g in grey2))
for i,row in enumerate(table):
print(f"{grey1[i]:b}".rjust(tagwidth,'0')+ '|' + (' '*colwidth).join(e for e in row))
def render_cell(ss, x, block):
val = '\x1b[38;5;250mx' if x in dd else ('1' if x in ss else ' ')
e = int2elem(x)
if is_in_block(e, block):
val = '\x1b[1;30;43m' + val
return val + '\x1b[0m'
def showblock(block):
return ''.join(str(b) for b in reversed(block))
def block2mint(tags, block):
ret = []
for i,b in enumerate(reversed(block)):
if b == '-': continue;
ret.append(tags[i])
if b == 0: ret.append("'")
return ''.join(ret)
#n = 4
#ss = set((4,8,10,11,12,15))
#dd = set((9,14))
#
#assert(int2elem( 3) == (1,1,0,0))
#assert(int2elem( 5) == (1,0,1,0))
#assert(int2elem(14) == (0,1,1,1))
#assert(int2elem(10) == (0,1,0,1))
#
#assert(elem2int(int2elem( 3)) == 3)
#assert(elem2int(int2elem( 5)) == 5)
#assert(elem2int(int2elem(14)) == 14)
#assert(elem2int(int2elem(10)) == 10)
#
#print(elem2int([0,0,'-',1,1]))
#for el in block_elems(['-',0,'-',1,0]): print(el) #print(elem2int(el))
#table = kmap_table([[0,1,3,2],[0,1,3,2]], ss, [], 0)
#for l in table: print(l)
#table = kmap_table([[0,1,3,2],[0,1,3,2]], 0)
#draw_kmap_table("AB","CD", [0,1,3,2],[0,1,3,2], table)
#draw_kmap(["Z", "AB","CD"], [[0,1], [0,1,3,2],[0,1,3,2]])
#block = int2elem(15)
#print("from", showblock(block))
#pis = collect_PIs_from(ss|dd, block)
#for pi in pis:
# print(showblock(pi))
# draw_kmap(["AB","CD"], [[0,1,3,2],[0,1,3,2]], pi)
# print('')
#pis = collect_PIs_kmap(ss|dd)
#for pi in pis:
# print("\x1b[7m", showblock(pi), "\x1b[0m")
# draw_kmap(["AB","CD"], [[0,1,3,2],[0,1,3,2]], pi)
# print('')
def cover_order(block):
return sum(b == '-' for b in block)
# is b1 < b2?
def compare_block(b1, b2):
# cover size comp
o1 = cover_order(b1)
o2 = cover_order(b2)
if o1 != o2: return o1 - o2
# lexicographic order
m1 = tuple(reversed(sorted(elem2int(e) for e in block_elems(b1))))
m2 = tuple(reversed(sorted(elem2int(e) for e in block_elems(b2))))
for t1, t2 in zip(m1, m2):
if t1 == t2: continue
return t1 - t2
def compare_bss(bss1, bss2):
# cover size comp
o1 = len(bss1)
o2 = len(bss2)
if o1 != o2: return o1 - o2
# lexicographic order
m1 = tuple(sorted(bss1))
m2 = tuple(sorted(bss2))
for t1, t2 in zip(m1, m2):
if t1 == t2: continue
return t1 - t2
def draw_cover(ss, tags, pis, select):
ret = {s:[] for s in ss}
mints = []
for pi in pis:
mint = block2mint(tags, pi)
mints.append(mint)
for el in block_elems(pi):
x = elem2int(el)
if x in ret:
ret[x].append(mint)
# discard x only in dd
sol_s = []
epis = set()
for s,cover in ret.items():
if len(cover) == 1:
sol_s.append(s)
epis.add(cover[0])
for v in select: epis.add(block2mint(tags, v))
print(epis)
# covered by EPIs
cov_s = { s for s,cover in ret.items() if any(pi in epis for pi in cover) }
tagwidth = int(round(math.log10(n))) + 1
colwidth = max(len(mint) for mint in mints)
def show_mint(mint):
val = mint.center(colwidth)
if mint in epis:
return "\x1b[30;46m" + val + "\x1b[0m"
else: return val
def show_s(s):
#val = f"{s:b}".rjust(tagwidth,'0')
val = str(s).rjust(tagwidth)
if s in sol_s:
return "\x1b[30;46m" + val + "\x1b[0m"
elif s in cov_s:
return "\x1b[36m" + val + "\x1b[0m"
else: return val
def show_ent(s,mint):
val = ("o" if mint in ret[s] else ' ').center(colwidth)
if s in sol_s or mint in epis:
return "\x1b[30;46m" + val + "\x1b[0m"
elif s in cov_s:
return "\x1b[36m" + val + "\x1b[0m"
else: return val
print(' ' * tagwidth + '|' + ' '.join(showblock(pi).center(colwidth) for pi in pis))
print(' ' * tagwidth + '|' + ' '.join(show_mint(mint) for mint in mints))
for s in sorted(ss):
print(show_s(s) + '|' + ' '.join(show_ent(s,mint) for mint in mints))
def collect_PIs_qm(ss):
table = gen_qm_table(ss|dd)
pis = draw_calc_table(table)
print("")
return pis
def count_1s(block):
return sum(b == 1 for b in block)
def gen_I1(ss):
ret = [[] for _ in range(n+1)]
for s in ss:
el = int2elem(s)
i = count_1s(el)
ret[i].append((el,(s,)))
return ret
def gen_In(i1):
ret = [set() for _ in range(n+1)]
covered = set()
for i, (bls1, bls2) in enumerate(zip(i1[0:], i1[1:])):
for block1,ss1 in bls1:
for block2,ss2 in bls2:
nblock = merge_blocks(block1, block2)
if nblock is None: continue
nss = tuple(sorted(set(ss1 + ss2)))
ret[i].add((nblock, nss))
covered.add(block1)
covered.add(block2)
return ret, covered
def merge_blocks(block1, block2):
ret = []
has_been_diff = False
for b1, b2 in zip(block1, block2):
if b1 == b2:
ret.append(b1)
continue
if has_been_diff: return None
has_been_diff = True
ret.append('-')
return tuple(ret)
def gen_qm_table(ss):
mints = gen_I1(ss)
cov = set()
ret = []
while(sum(map(len,mints)) > 0):
new_mints, new_cov = gen_In(mints)
ret.append((mints,new_cov))
mints = new_mints
ret.append((mints,set()))
return ret
from functools import cmp_to_key
def draw_calc_table(_tbl):
def show_cell(block, bss):
return f"{showblock(block)} {','.join(str(s) for s in bss)}"
# transpose
tbl = [
[[] for _ in _tbl]
for _ in range(n+1)
]
colwidth = [0 for _ in _tbl]
pis = []
for order,(Is,cover) in enumerate(_tbl):
for grp,rows in enumerate(Is):
#tbl[i][lvl] = rows
string_rows = []
for block,bss in rows:
string = show_cell(block,bss)
covered = block in cover
if not covered: pis.append(block)
string_rows.append((string,covered,bss))
colwidth[order] = max(colwidth[order], len(string))
string_rows.sort(key=lambda t: cmp_to_key(compare_bss)(t[2]))
tbl[grp][order] = [t[:2] for t in string_rows]
print(f" N | " + ''.join(f"I{order}".rjust(colw)+' | ' for order,colw in enumerate(colwidth)))
for grp,ord_rows in enumerate(tbl): # 0 <= grp <= n
print('-'*(sum(colwidth) + 3*len(colwidth) + 4))
nrows = max(len(rows) for rows in ord_rows)
for i in range(nrows):
if i == 0: print(f"{grp:2d} | ", end='')
else: print(f" | ", end='')
for order,rows in enumerate(ord_rows):
cell,covered = rows[i] if i < len(rows) else ('',True)
colw = colwidth[order]
val = cell.ljust(colw)
if not covered: val = "\x1b[30;42m" + val + "\x1b[0m"
print(val+' | ', end='')
print("")
return pis
# 5
#n = 5
#ss = set([0,2,3,4,9,11,18])
#dd = set([8,10,14,22,23,24,25,26,27,28,29,30,31])
#tags = "ABCDE"
# 6
#n = 5
#ss = set([5,7,10,13,14,15,21,23,29,31])
#dd = set([24,30])
#tags = "ABCDE"
#n = 4
#ss = set([0,1,2,4,5,6,8,9,10,11,12,13,15])
#dd = set()
#tags = "wxyz"
#n = 5
#ss = set([3,8,9,11,12,13,14,15,22,31])
#dd = set([0,2,7,17,20,21,23,30])
#tags = "ABCDE"
n = 4
ss = set([6,7,9,11,13])
dd = set([1,10,15])
tags = "ABCD"
pis_km = collect_PIs_kmap(ss|dd)
for pi in pis_km:
print("\x1b[7m", showblock(pi), "\x1b[0m", "----------------------------")
draw_kmap(["AB","CD"], [[0,1,3,2],[0,1,3,2]], pi)
print('')
pis_qm = collect_PIs_qm(ss|dd)
draw_cover(ss, tags, pis_km, [])
#assert(list(sorted(pis_km)) == list(sorted(pis_qm)))
#select = []
#while True:
# try:
# a = tuple(int(x) if x != '-' else x for x in input().strip())
# select.append(a)
# print(select)
# draw_cover(ss, tags, pis_km, select)
# except Exception as e:
# print(e)
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment