生成长运行格雷码
Generating long-run Gray codes
对于通信系统，我需要一种特殊的格雷码。
要求是：
- 两个连续的值只有一位不同，就像所有格雷码一样。
- 同一位上的两次转换应该至少远离某个任意数量的值。此距离记为最小 运行 长度的 mrl。
- 我不关心最后一个代码到第一个代码的距离，代码翻转时对mrl没有约束
此类格雷码的一个示例是，对于 5 位且 mrl = 4：
01111000011110000111100001111000
00111100000011111100001111110000
00011110000111100001111000011110
00001111110000111111000000111100
00000000111111110000000011111111
This paper 给出不同位数的最佳 mrl 值。然而，这些值被发现 "By use of exhaustive computer searches"
我有 python 代码可以很好地处理少量位数，最多 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]')
我的问题是我想要一个20位的代码，基本方法的复杂度似乎接近O(n^3)。关于如何改进此代码的任何建议？有没有更好的方法？
我有完全相同的问题，一直找不到解决方案，但我使用的是一个足够好的解决方案。
Donald E. Knuth 的书“计算机编程艺术，第 4 卷，分册 2”有一个 8 位长 运行 格雷码的图像（没有关于如何制作它的信息） .
Screenshot of Knuth's 8 bit Long Run Gray Code
我提取了二进制序列，并排列了一些行（它不影响结果，因为任何行排列都是同一类型的代码）。它由数字的二进制表示组成：
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
这里是汉明距离图
Hamming distance
一个允许放大它的技巧，就是对这个长 运行 格雷码进行“格雷码”。
要继续这个序列，你反转顺序，加入序列中第二个元素的二进制表示，然后再次反转整个序列，加入下一个
Screenshot, how to extend the code
不是完美的解决方案，但效果很好。
它没有用更多位（按 O(log_2(n) 的顺序）可以实现的最佳长跑，但至少有 Knuth 的 8 位示例的长跑。
如果您找到了问题的解决方案，请告知我们。真的好难找。
（稍后会添加代码）
这是 Gray Codes with Optimized Run Lengths with special case for n=10 bits from Binary gray codes with long bit runs
中描述的方法 1 的（差）python 实现
我尝试使用与上述论文中相同的术语和变量名称。
我相信第 1 篇论文中的方法 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位）
对于通信系统，我需要一种特殊的格雷码。 要求是：
- 两个连续的值只有一位不同，就像所有格雷码一样。
- 同一位上的两次转换应该至少远离某个任意数量的值。此距离记为最小 运行 长度的 mrl。
- 我不关心最后一个代码到第一个代码的距离，代码翻转时对mrl没有约束
此类格雷码的一个示例是，对于 5 位且 mrl = 4：
01111000011110000111100001111000
00111100000011111100001111110000
00011110000111100001111000011110
00001111110000111111000000111100
00000000111111110000000011111111
This paper 给出不同位数的最佳 mrl 值。然而，这些值被发现 "By use of exhaustive computer searches"
我有 python 代码可以很好地处理少量位数，最多 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]')
我的问题是我想要一个20位的代码，基本方法的复杂度似乎接近O(n^3)。关于如何改进此代码的任何建议？有没有更好的方法？
我有完全相同的问题，一直找不到解决方案，但我使用的是一个足够好的解决方案。
Donald E. Knuth 的书“计算机编程艺术，第 4 卷，分册 2”有一个 8 位长 运行 格雷码的图像（没有关于如何制作它的信息） .
Screenshot of Knuth's 8 bit Long Run Gray Code
我提取了二进制序列，并排列了一些行（它不影响结果，因为任何行排列都是同一类型的代码）。它由数字的二进制表示组成：
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
这里是汉明距离图
Hamming distance
一个允许放大它的技巧，就是对这个长 运行 格雷码进行“格雷码”。
要继续这个序列，你反转顺序，加入序列中第二个元素的二进制表示，然后再次反转整个序列，加入下一个
Screenshot, how to extend the code
不是完美的解决方案，但效果很好。
它没有用更多位（按 O(log_2(n) 的顺序）可以实现的最佳长跑，但至少有 Knuth 的 8 位示例的长跑。
如果您找到了问题的解决方案，请告知我们。真的好难找。
（稍后会添加代码）
这是 Gray Codes with Optimized Run Lengths with special case for n=10 bits from Binary gray codes with long bit runs
我尝试使用与上述论文中相同的术语和变量名称。 我相信第 1 篇论文中的方法 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位）