python - 生成长期运行的格雷码

Question

对于通信系统，我需要一种特殊的格雷码。
要求是:

两个连续的值只有一位不同，就像所有的格雷码一样。

同一位上的两个转换应该至少远离某个任意数量的值。对于最小运行长度，此距离记为 mrl。

我不关心从最后一个代码到第一个代码的距离，代码翻转时对 mrl 没有限制。

这种格雷码的一个例子是，对于 5 位和 mrl = 4:

01111000011110000111100001111000
00111100000011111100001111110000
00011110000111100001111000011110
00001111110000111111000000111100
00000000111111110000000011111111

This paper给出不同位数的最佳 mrl 值。但是，这些值是通过“使用详尽的计算机搜索”找到的

我有适用于少量位(最多 6 位)的 Python 代码:

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]')

我的问题是我想要一个 20 位的代码，基本方法的复杂性似乎接近 O(n^3)。有关如何改进此代码的任何建议？有没有更好的方法？

Answer 1

这是 Gray Codes with Optimized Run Lengths 中描述的方法 1 的(糟糕的)python 实现带有 n=10 的特殊情况来自 Binary gray codes with long bit runs 的位
我尝试使用与上述论文中相同的术语和变量名称。
我相信第一篇论文中的方法 2 可能能够改善一些发现的差距。
如果有用，请告诉我，我可以将它包装在一个 python 包中，或者在说 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")

上面的循环产生

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

使用 transitions[3]或 print_code_from_transition( transitions[3] )显示格雷码(在本例中为 3 位)