0

ウィキペディアの手順を使用して、Python でガロア線形フィードバック シフト レジスタを作成しました。

def lfsr(coefficients, state):
    while 1:
        lsb = state.pop()
        state.insert(0, 0)
        if lsb:
            state = app(coefficients, state)

        yield lsb

def app(coefficients, state):
    return [ (coefficients[i]^state[i]) for i in range(len(state)) ]

L = lfsr([1,0,1,1,0,1,0,0,0,0,0,0,0,0,0,0,1], [0]*15+[1])
seq = [ str(L.next()) for i in range(2**16+16) ]

これはうまくいきます。私が今やりたいことは、GF(2) 以外のガロア体を処理できる一般化されたバージョンを作成することですが、非バイナリ LFSRに関するセクションがわかりません。この部分は私には意味がありません:「フィードバック ビット (出力ビット) は、特定のタップ ポイントごとに一定である q-ary 値で乗算 (モジュロ q) されます。」1 つの出力ビットに各タップ ポイントの値を乗算するにはどうすればよいですか?

これは私が思いついたものですが、循環シーケンスを与える代わりに、出力はすぐにすべて 0 に劣化します。

# Multiplication table for GF(4)
mult_4 = [[0, 0, 0, 0],
          [0, 1, 2, 3],
          [0, 2, 3, 1],
          [0, 3, 1, 2]]

def lfsr(coefficients, state):
    while 1:
        lsb = state.pop()
        state.insert(0, 0)
        state = app(coefficients, state)

        yield lsb

def app(coefficients, state):
    return [ mult_4[coefficients[i]][state[i]] for i in range(len(state)) ]

L = lfsr([ 1, 0, 0, 0, 1, 2, 3 ], [1]*6)
seq = [ str(L.next()) for i in range(4**6+6) ]
4

2 に答える 2

1

多項式環の概念を理解しておくことをお勧めします(ただし、ウィキペディアの記事は技術的すぎて最適な紹介にはなりません)。あなたが抱えていると思われる最も基本的な問題は、バイナリシフトレジスタを回路としてではなく離散動的システムとして見たときに何が起こっているのかを完全に理解していないため、バイナリシフトレジスタを厳密に模倣しようとしていることです。

X^Nバイナリ シフト レジスタは、 で割ったときの剰余を計算する巧妙な回路ですf(X)。ここで、 のすべての係数は、 0 と 1 だけを含むf環Z/2Zにあります。これらの剰余は、整数の剰余を計算するのと同じように、ユークリッドのアルゴリズムで計算されます。このモデルの LFSR の状態は、 の次数より小さい次数の多項式ですf。LFSR の最初の状態は で1、2 番目の状態は ですX。XLFSR の各サイクルは、長除算の 1 ステップを掛けたものと等価です。シフト操作は乗算であり、タップは長い除算です。分割はここで本当に重要です。

[余談: 任意の環をこの構成の係数として使用できますが、除数多項式の主係数としてゼロ除数の問題があるため、事態は複雑になります。とにかくフィールドを使用しているので、フィールドを係数として説明します。]

ビット以外の係数のリングを使用している場合は、長除算の 1 ステップがどのように見えるかを考える必要があります。除数多項式fが のようa_k X^k + ...に見え、新しい状態gが のようb_k X^k + ...に見える場合、長い除算の最初のステップは計算b_k / a_kです。フィールドの場合 (私が想定しているように)、これは numbercです。したがって、剰余はg - cfであり、次数 の多項式k-1です。残りはあなたの新しい状態です。

(式は、Wikipedia の記事であなたを混乱させた部分を理解するための鍵です。多項式を先頭の係数で除算して、その数列の倍数である数列を生成する別の多項式を取得cfできることを自分自身に納得させたいと思うかもしれません。最初。）fa_k

于 2012-11-20T06:25:05.500 に答える
0

ガロア体での乗算について math.stackoverflow.com で尋ねることができますが、その要点は、各ビットが 0 または 1 (GF_2) である「ビット」の代わりに、各「ビット」が実際には数値の 1 つであるということです。シンボルの数 -- 正確な数はフィールドのサイズによって異なります。

バイナリ LFSR からガロア LFSR に移行するには、「ビット」と「乗算」の概念を一般化して、その分野で意味をなす必要があります。フィールドの乗算演算Addition は、関数の XOR の代わりにもなりますapp()。

バイナリ バージョンでは、乗算は暗黙的です。タップが存在するかどうかに応じて、出力ビットは 0 または 1 で乗算されます。一般的なフィールドでは、タップ自体に任意のフィールド要素を関連付けることができ、出力で乗算されます。

于 2012-11-15T22:51:04.193 に答える