针对通信系统,我需要一种特殊类型的格雷码。
- 两个连续的值仅在一个位上不同,就像所有的格雷码一样。
- 同一位上的两次转换应至少相隔一些任意数量的值。此距离被记为mrl以表示最小运行长度。
- 当编码翻转时,我不关心最后一个编码到第一个编码的距离,mrl没有限制。
一个这样的格雷码示例是,对于5位和mrl = 4:
01111000011110000111100001111000
00111100000011111100001111110000
00011110000111100001111000011110
00001111110000111111000000111100
00000000111111110000000011111111
这篇论文给出了不同比特数的最佳mrl值。然而,这些值是通过“使用穷举式计算机搜索”找到的。
我有一段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)。有什么建议可以改进这段代码吗?是否有更好的方法?