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?

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)