8

通信システムには、特別な種類のグレイ コードが必要です。要件は次のとおりです。

  1. すべてのグレー コードと同様に、連続する 2 つの値は 1 ビットだけ異なります。
  2. 同じビットでの 2 つの遷移は、任意の数の値から少なくとも離れている必要があります。この距離は、最小ラン長の mrl と表記されます。
  3. 最後のコードから最初のコードまでの距離は気にしません。コードがロールオーバーするときの mrl に制約はありません。

このようなグレー コードの 1 つの例は、5 ビットおよび mrl = 4 の場合です。

01111000011110000111100001111000
00111100000011111100001111110000
00011110000111100001111000011110
00001111110000111111000000111100
00000000111111110000000011111111

この論文では、さまざまなビット数に対して最適な 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) に近いようです。このコードを改善する方法について何か提案はありますか? より良いアプローチはありますか？

4

2 に答える 2