Generating long-run Gray codes

Question

For a communication system, I need a special kind of gray codes. The requirements are:

1. Two successive values differ in only one bit, like all gray codes.
2. Two transitions on the same bit should be at least distant of some arbitrary number of values. this distance is noted mrl for minimum run length.
3. I don't care about the distance form the last code to the first code, there is no constraint on the mrl when the code roll-over.

One example of such Gray code is, for 5 bits and mrl = 4:

01111000011110000111100001111000
00111100000011111100001111110000
00011110000111100001111000011110
00001111110000111111000000111100
00000000111111110000000011111111

This paper give the best mrl values for different number of bits. Howerver, those values are found "By use of exhaustive computer searches"

I have python code that work well for small number of bits, up to 6:

N = 5 # number of bit
mrl = 4 # minimum run length
first_transition = [0]
first_code = [0]

def Recur(previous_transitions, previous_codes):
  if len(previous_codes) == (2**N):
    for b in xrange(N):
      print ''.join([str((code >> (N-b-1)) & 1) for code in previous_codes])
    print
    return
  new_transition_list = range(N)
  for new_transition in new_transition_list:
    ok = True
    for i in xrange(mrl-1): #look back for transitions that are too close
      try:
        if new_transition == previous_transitions[-1-i]:
          ok = False
          break
      except: break
    if ok:
      new_code = previous_codes[-1] ^ 2**new_transition #look back for repeated code
      if not (new_code in previous_codes):
        Recur(previous_transitions+[new_transition], previous_codes+[new_code])

Recur(first_transition, first_code )
raw_input('[end]')

My problem is that I would like a code of 20 bits, and the complexity of the basic approach seems close to O(n^3). Any suggestions on how to improve this code? Is there a better approach?

Passifloraceous

It seems like the balanced gray codes might be useful — if the transitions are distributed evenly among all the bits, you have the best chance of maximizing the minimum transition distance for any given bit. – Hydrokinetics

Do you want the gray codes as strings, or integers? – Ephemera

@Hydrokinetics Long-run gray codes are probably balanced, but I am not sure the opposite is true. The Wikipedia example have an mrl of 2, witch the worst possible result. Do you suggest to generate (or get a table of) balanced Gray codes and check each of them? – Passifloraceous

@CommuSoft Do you mean for output format or you talking about n-ary Gray codes? I need binary Gray codes, any output format. – Passifloraceous

@Passifloraceous something like that. I'm not sure, which is why I'm posting as a comment rather than an answer. But if you did have to do an exhaustive search, at least it would be over a smaller space :) – Hydrokinetics

@Passifloraceous I'm wondering if math.se or cs.se would be better for this question. – Hydrokinetics

I also agree that Math.SE or (Theorical) Computer Science.SE may be more appropriate. Some people also find some interesting ways to optimize things on Code Review.SE. Since your code is working, it would be on-topic :) – Curse

@Curse Not on CR it wouldn't. It's off-topic there to ask for help with implementing a new feature, and an entirely new algorithm (if I'm reading the question right) is certainly a new feature. – Pirozzo

@QPaysTaxes I was refering about the "Any suggestions on how to improve this code?" part of the question. Sometimes, improving a piece of code actually includes suggesting another algorithm or another way to do this. You can often find this kind of answers in the algorithm on CR. What I mean is that it could be a good fit if reworded and an answer to this SO question could appear in the CR answer as a side effect. – Curse

@Curse ...I totally saw and didn't entirely miss that whole part. Apologies. (And my point is that if the question is solely asking "how can I implement this with a different algorithm" it's off-topic. People can supply that information if the question isn't asking for it, though; the answers don't change the question.) – Pirozzo

The easy way of generating gray codes is x ^ (x >> 1) for linearly increasing x. I have no idea how to modify that to fit your constraints. – Pileous

Answer 1

This is a (poor) python implementation of Method 1 described in Gray Codes with Optimized Run Lengths with special case for n=10 bits from Binary gray codes with long bit runs

I tried to use same terminology and variable names as in mentioned paper. I believe method 2 from the 1st paper might be able to improve some of the found gaps.

Let me know if useful, I can wrap it in a python package, or make a faster implementation in say rust.

import numpy as np

def transition_to_code( transition_sequence ):
    code_sequence = [0]
    
    n = np.int( np.log2( len(transition_sequence) ) )
    
    code = 0
    
    for pos in transition_sequence:
        code ^= 1 << int(pos)
        code_sequence.append(code)
        
    return code_sequence[:-1]

def print_code_from_transition( transition_sequence ):
    n = np.int( np.log2( len(transition_sequence) ) )
    
    codes = transition_to_code( transition_sequence )
    
    format_string = "b: {:0"+ str(n) +"b}"
    
    for c in codes:
        print( format_string.format( c ) )
        
def gap( transition_sequence ):
    as_array = a = np.array( transition_sequence )
    gap = 1
    
    while gap < len(transition_sequence):
        if np.any( as_array == np.roll(as_array, gap) ):
            return gap
        gap += 1
        
    return 0

def valid_circuit( transition_sequence ):
    n = np.int( np.log2( len(transition_sequence) ) )

    if not len(transition_sequence) == 2**n:
        print('Length not valid')
        return False
    
    if not np.all(np.array(transition_sequence) < n):
        print('Transition codes not valid')
        return False
    
    sorted_codes = np.sort( transition_to_code( transition_sequence ) )
    
    if not np.all( sorted_codes == np.arange(0,2**n) ):
        print('Not all Unique')
        return False
    
    return True

transitions = {
    2 : [0, 1, 0, 1],
    3 : [0, 1, 0, 2, 0, 1, 0, 2],
    4 : [0, 1, 2, 3, 2, 1, 0, 2, 0, 3, 0, 1, 3, 2, 3, 1],
    5 : [0, 1, 2, 3, 4, 1, 2, 3, 0, 1, 4, 3, 2, 1, 4, 3, 0, 1, 2, 3, 4, 1, 2, 3, 0, 1, 4, 3, 2, 1, 4, 3],
    6 : [0, 1, 2, 3, 4, 5, 0, 2, 4, 1, 3, 2, 0, 5, 4, 2, 3, 1, 4, 0, 2, 5, 3, 4, 2, 1, 0, 4, 3, 5, 2, 4, 0, 1, 2, 3, 4, 5, 0, 2, 4, 1, 3, 2, 0, 5, 4, 2, 3, 1, 4, 0, 2, 5, 3, 4, 2, 1, 0, 4, 3, 5, 2, 4]
}

def interleave(A, B):
    n = np.int( np.log2( len(A) ) )
    m = np.int( np.log2( len(B) ) )
    
    M = 2**m
    N = 2**n
    
    assert N >= M
    
    gap_A = gap(A)
    gap_B = gap(B)
    
    assert gap_A >= gap_B
    
    st_pairs = [ (i, M-i) for i in range(M) if i % 2 == 1]
    
    sorted_pairs = sorted(st_pairs, key=lambda p: np.abs(p[1]/p[0] - gap_B/gap_A) )
    
    best_pair = sorted_pairs[0]
    
    s, t = best_pair
    
    ratio = t/s
    
    P = "b"
    
    while len(P) < M:
        b_to_a_ratio = P.count('b') / (P.count('a') + 1)
        
        if b_to_a_ratio >= ratio :
            P += 'a'
        else:
            P += 'b'

    return P * N


def P_to_transition(P, A, B):
    Z = []
    
    pos_a = 0
    pos_b = 0
    
    n = np.int( np.log2( len(A) ) )
    
    delta = n
    
    for p in P:
        if p == 'a' :
            Z.append( A[pos_a % len(A)] )
            pos_a += 1
        else :
            Z.append( B[pos_b % len(B)] + delta )
            pos_b += 1
        
    return Z

"""
Code for special case for 10-bits to fabric a gap of 8.

From: Binary gray codes with long bit runs
by: Luis Goddyn∗ & Pavol Gvozdjak

"""

T0 = [0, 1, 2, 3, 0, 1, 2, 3, 0, 1, 2, 3, 0, 1, 2, 3]

def to_4( i, sequence ):
    
    permutations = []
    
    indices = [j for j, x in enumerate(sequence) if x == i]
    
    for pos in indices:
        permutation = sequence.copy()
        permutation[pos] = 4
        permutations.append( permutation )
        
    return permutations

def T_to_group(T):
    
    state = np.array([0,0,0,0,0])
    
    cycle = []
    
    for pos in T:
        cycle.append( state.copy() )
        state[pos] += 1
        state[pos] %= 4
        
    return np.array( cycle )

def T_to_transition(T):
    
    ticker = [False, False, False, False, False]
    
    transitions = []
    
    for t in T:
        transistion = 2*t + 1*ticker[t]
        ticker[t] = not ticker[t]
        
        transitions.append( transistion )
    return transitions
        

T1 = to_4( 0, T0)[3] * 4
T2 = to_4( 1, T1)[0] * 4
T3 = to_4( 2, T2)[1] * 4

transitions[10] = T_to_transition(T3)


for bits in range(2,21):
    if bits in transitions:
        print( "gray code for {} bits has gap: {}".format(bits, gap(transitions[bits]) ) )
    else:
        print( "finding code for {} bits...".format(bits) )
        
        all_partitions = [ (i, bits-i) for i in range(bits) if i > 1]
        partitions = [ (n, m) for (n,m) in all_partitions if n >= m and m > 1]        
        current_gap = 0
        for n,m in partitions:
            P = interleave( transitions[n], transitions[m])
            Z = P_to_transition(P,  transitions[n], transitions[m])
            candidate_gap = gap( Z )
            
            if candidate_gap > current_gap:
                current_gap = candidate_gap
                transitions[bits] = Z
        if valid_circuit(transitions[bits]):
            print( "gray code for {} bits has gap: {}".format(bits, gap(transitions[bits]) ) )
        else:
            print( "found in-valid gray code")

The loop above produces

gray code for 2 bits has gap: 2
gray code for 3 bits has gap: 2
gray code for 4 bits has gap: 2
gray code for 5 bits has gap: 4
gray code for 6 bits has gap: 4
finding code for 7 bits...
gray code for 7 bits has gap: 5
finding code for 8 bits...
gray code for 8 bits has gap: 5
finding code for 9 bits...
gray code for 9 bits has gap: 6
gray code for 10 bits has gap: 8
finding code for 11 bits...
gray code for 11 bits has gap: 8
finding code for 12 bits...
gray code for 12 bits has gap: 8
finding code for 13 bits...
gray code for 13 bits has gap: 9
finding code for 14 bits...
gray code for 14 bits has gap: 9
finding code for 15 bits...
gray code for 15 bits has gap: 11
finding code for 16 bits...
gray code for 16 bits has gap: 11
finding code for 17 bits...
gray code for 17 bits has gap: 12
finding code for 18 bits...
gray code for 18 bits has gap: 12
finding code for 19 bits...
gray code for 19 bits has gap: 13
finding code for 20 bits...
gray code for 20 bits has gap: 15

use transitions[3] or print_code_from_transition( transitions[3] ) to display the gray codes (in this example for 3 bits)

Cormick

Thank you! I generated these codes and pasted the values for 2-bit through 13-bit into a gist here gist.github.com/kylemcdonald/8c03de4ae1928ab5f3d203245549e802 – Spain

Cool - I want to mention it is possible to improve the result for 19 from 13 to 14. This is quite some extra work but wanted to let the reader to know this in case there is a case. – Cormick

Maybe numba would be a good (and easy) choice to further speed this up? – Ursulina

Answer 2

I have exactly the same problem, and has ben unable to find a solution, but there is a good enough one I use.

The book "The Art of Computer Programming, Volume 4, Fascicle 2", by Donald E. Knuth has an image with an 8 bit Long Run Gray Code (no information on how to make it).

Screenshot of Knuth's 8 bit Long Run Gray Code

I extracted the binary sequence, and permutated some rows (it doesn't affects the result, because any row permutation is the same type of code). It is made of the binary representation of the numbers:

0, 1, 3, 7, 15, 31, 30, 62, 126, 254, 246, 247, 245, 213, 209, 145, 153, 152, 136, 8, 40, 42, 43, 35, 99, 103, 71, 70, 68, 76, 204, 220, 252, 253, 189, 185, 177, 179, 178, 146, 210, 82, 90, 91, 75, 107, 111, 109, 101, 100, 36, 164, 132, 134, 135, 143, 159, 155, 187, 186, 250, 242, 114, 112, 80, 81, 17, 21, 29, 13, 12, 44, 46, 174, 166, 167, 231, 199, 195, 193, 201, 200, 216, 88, 120, 56, 57, 49, 51, 55, 23, 22, 86, 94, 222, 206, 238, 239, 237, 233, 225, 161, 160, 128, 130, 2, 10, 11, 27, 59, 63, 127, 119, 118, 116, 244, 212, 148, 149, 157, 141, 137, 169, 168, 170, 162, 34, 98, 66, 67, 65, 69, 77, 93, 92, 124, 60, 188, 180, 181, 183, 151, 147, 211, 219, 218, 202, 74, 106, 104, 105, 97, 33, 37, 5, 4, 6, 14, 142, 158, 190, 191, 255, 251, 243, 241, 240, 208, 144, 16, 24, 25, 9, 41, 45, 47, 39, 38, 102, 230, 198, 196, 197, 205, 221, 217, 249, 248, 184, 176, 48, 50, 18, 19, 83, 87, 95, 79, 78, 110, 108, 236, 228, 229, 165, 133, 129, 131, 139, 138, 154, 26, 58, 122, 123, 115, 113, 117, 85, 84, 20, 28, 156, 140, 172, 173, 175, 171, 163, 227, 226, 194, 192, 64, 72, 73, 89, 121, 125, 61, 53, 52, 54, 182, 150, 214, 215, 223, 207, 203, 235, 234, 232, 224, 96, 32

Screenshot

here is the Hamming distance map

Hamming distance

A hack that allows to enlarge it, is to "gray code" this Long Run Gray Code.

To continue the sequence, you reverse the order, and join the binary representation of the second element on the sequence, then reverse the entire sequence again, and join the next

Screenshot, how to extend the code

Is not a perfect solution, but works very well.
It doesn't have the best long runs that could be achieved with more bits (which are in the order of O(log_2(n)), but at least has the long runs of Knuth's 8 bit example.

If you got a solution to your problem, please, inform us. It is really hard to find one.

(will add code later)

Gavage

There are heuristics to get for instance gap of 13 for 20 bits – Cormick

@user3184950 I cannot comment on your answer, because of low reputation, but THANK YOU A LOT. That's a life saver – Gavage

thx - I improved the gap for a few. For n=20 the gap is now 15. It could be further improved but its quite some just for this special case. – Cormick