Balanced Gray code and Z3 SMT solver

(The following text has been moved to the article at https://yurichev.com/tmp/SAT_SMT_DRAFT.pdf.)

Suppose, you are making a rotary encoder. This is a device that can signal its angle in some form, like:

( Taken from Wikipedia: https://en.wikipedia.org/wiki/Gray_code )

Click on bigger image: https://raw.githubusercontent.com/dennis714/yurichev.com/master/blog/gray/Gray_code_rotary_encoder_13-track_opened.jpg.

This is a rotary (shaft) encoder: https://en.wikipedia.org/wiki/Rotary_encoder. This picture is a cropped and photoshopped version:

( Source: http://homepages.dordt.edu/~ddeboer//S10/304/c_at_d/304S10_RC_TRK.HTM )

Click on bigger one: https://raw.githubusercontent.com/dennis714/yurichev.com/master/blog/gray/Rotary_Encoder_track_detail.gif.

There are pins and tracks on rotating wheel. How would you do this? Easiest way is to use binary code. But it has a problem: when a wheel is rotating, in a moment of transition from one state to another, several bits may be changed, hence, undesirable state may be present for a short period of time. This is bad. To deal with it, Gray code was invented: only 1 bit is changed during rotation. Like:

Decimal Binary  Gray
0 	0000 	0000
1 	0001 	0001
2 	0010 	0011
3 	0011 	0010
4 	0100 	0110
5 	0101 	0111
6 	0110 	0101
7 	0111 	0100
8 	1000 	1100
9 	1001 	1101
10 	1010 	1111
11 	1011 	1110
12 	1100 	1010
13 	1101 	1011
14 	1110 	1001
15 	1111 	1000

Now the second problem. Look at the picture again. It has a lot of bit changes on the outer circles. And this is electromechanical device. Surely, you may want to make tracks as long as possible, to reduce wearing of both tracks and pins. This is a first problem. The second: wearing should be even across all tracks (this is balanced Gray code).

How we can find a table for all states using Z3:

#!/usr/bin/env python

from z3 import *

BITS=5

# how many times a run of bits for each bit can be changed (max).
# it can be 4 for 4-bit Gray code or 8 for 5-bit code.
# 12 for 6-bit code (maybe even less)
CHANGES_MAX=8

ROWS=2**BITS
MASK=ROWS-1 # 0x1f for 5 bits, 0xf for 4 bits, etc

def bool_to_int (b):
    if b==True:
        return 1
    return 0

s=Solver()

# add a constraint: Hamming distance between two bitvectors must be 1
# i.e., two bitvectors can differ in only one bit.
# for 4 bits it works like that:
#    s.add(Or(
#        And(a3!=b3,a2==b2,a1==b1,a0==b0),
#        And(a3==b3,a2!=b2,a1==b1,a0==b0),
#        And(a3==b3,a2==b2,a1!=b1,a0==b0),
#        And(a3==b3,a2==b2,a1==b1,a0!=b0)))
def hamming1(l1, l2):
    assert len(l1)==len(l2)
    r=[]
    for i in range(len(l1)):
        t=[]
        for j in range(len(l1)):
            if i==j:
                t.append(l1[j]!=l2[j])
            else:
                t.append(l1[j]==l2[j])
        r.append(And(t))
    s.add(Or(r))

# add a constraint: bitvectors must be different.
# for 4 bits works like this:
#    s.add(Or(a3!=b3, a2!=b2, a1!=b1, a0!=b0))
def not_eq(l1, l2):
    assert len(l1)==len(l2)
    t=[l1[i]!=l2[i] for i in range(len(l1))]
    s.add(Or(t))

code=[[Bool('code_%d_%d' % (r,c)) for c in range(BITS)] for r in range(ROWS)]
ch=[[Bool('ch_%d_%d' % (r,c)) for c in range(BITS)] for r in range(ROWS)]

# each rows must be different from a previous one and a next one by 1 bit:
for i in range(ROWS):
    # get bits of the current row:
    lst1=[code[i][bit] for bit in range(BITS)]
    # get bits of the next row.
    # important: if the current row is the last one, (last+1)&MASK==0, so we overlap here:
    lst2=[code[(i+1)&MASK][bit] for bit in range(BITS)]
    hamming1(lst1, lst2)

# no row must be equal to any another row:
for i in range(ROWS):
    for j in range(ROWS):
        if i==j:
            continue
        lst1=[code[i][bit] for bit in range(BITS)]
        lst2=[code[j][bit] for bit in range(BITS)]
        not_eq(lst1, lst2)

# 1 in ch[] table means that run of 1's has been changed to run of 0's, or back.
# "run" change detected using simple XOR:
for i in range(ROWS):
    for bit in range(BITS):
        # row overlapping works here as well:
        s.add(ch[i][bit]==Xor(code[i][bit],code[(i+1)&MASK][bit]))

# only CHANGES_MAX of 1 bits is allowed in ch[] table for each bit:
for bit in range(BITS):
    t=[ch[i][bit] for i in range(ROWS)]
    # this is a dirty hack.
    # AtMost() takes arguments like:
    # AtMost(v1, v2, v3, v4, 2) <- this means, only 2 booleans (or less) from the list can be True.
    # but we need to pass a list here.
    # so a CHANGES_MAX number is appended to a list and a new list is then passed as arguments list:
    s.add(AtMost(*(t+[CHANGES_MAX])))

result=s.check()
if result==unsat:
    exit(0)
m=s.model()

# get the model.

print "code table:"

for i in range(ROWS):
    for bit in range(BITS):
        # comma at the end means "no newline":
        print bool_to_int(is_true(m[code[i][BITS-1-bit]])),
    print ""

print "ch table:"

stat={}

for i in range(ROWS):
    for bit in range(BITS):
        x=is_true(m[ch[i][BITS-1-bit]])
        if x:
            # increment if bit is present in dict, set 1 if not present
            stat[bit]=stat.get(bit, 0)+1
        # comma at the end means "no newline":
        print bool_to_int(x),
    print ""

print "stat (bit number: number of changes): ", stat


( The source code: https://github.com/dennis714/yurichev.com/blob/master/blog/gray/gray.py )

For 4 bits, 4 changes is enough:

code table:
0 1 0 1 
0 0 0 1 
0 0 1 1 
0 0 1 0 
1 0 1 0 
1 0 1 1 
1 1 1 1 
1 1 0 1 
1 0 0 1 
1 0 0 0 
0 0 0 0 
0 1 0 0 
1 1 0 0 
1 1 1 0 
0 1 1 0 
0 1 1 1 
ch table:
0 1 0 0 
0 0 1 0 
0 0 0 1 
1 0 0 0 
0 0 0 1 
0 1 0 0 
0 0 1 0 
0 1 0 0 
0 0 0 1 
1 0 0 0 
0 1 0 0 
1 0 0 0 
0 0 1 0 
1 0 0 0 
0 0 0 1 
0 0 1 0 
stat (bit number: count of changes):  {0: 4, 1: 4, 2: 4, 3: 4}

8 changes for 5 bits: https://github.com/dennis714/yurichev.com/blob/master/blog/gray/5.txt. 12 for 6 bits (or maybe even less): https://github.com/dennis714/yurichev.com/blob/master/blog/gray/6.txt.

Duke Nukem 3D from 1990s

Another application of Gray code:

with.inspiring@flair.and.erudition (Mike Naylor) wrote:

>In Duke Nukem, you often come upon panels that have four buttons in a row,
>all in their "off" position. Each time you "push" a button, it toggles from
>one state to the other. The object is to find the unique combination that
>unlocks something in the game.

>My question is: What is the most efficient order in which to push the
>buttons so that every combination is tested with no wasted effort?

A Gray Code. :-)

(Oh, you wanted to know what one would be?  How about:
0000
0001
0011
0010
0110
0111
0101
0100
1100
1101
1111
1110
1010
1000
1001
1011

Or, if you prefer, with buttons A,B,C,D: D,C,D,B,D,C,D,A,D,C,D,B,C,D,C
It isn't the "canonical" Gray code (or if it is, it is by Divine
Providence), but it works.

Douglas Limmer -- lim...@math.orst.edu
"No wonder these mathematical wizards were nuts - went off the beam -
he'd be pure squirrel-food if he had half that stuff in _his_ skull!"
E. E. "Doc" Smith, _Second Stage Lensmen_

( https://groups.google.com/forum/#!topic/rec.puzzles/Dh2H-pGJcbI )

Obviously, using our solution, you can minimize all movements in this ancient videogame, for 4 switches, that would be 4*4=16 switches. With our solution (balanced Gray code), wearing would be even across all 4 switches.


→ [list of blog posts, my twitter/facebook]

Please drop me email about any bug(s) and suggestion(s): dennis(@)yurichev.com.