01signal.com

Linear-Feedback Shift Registerの Galois 多項式と Fibonacci 多項式の間の変換

序章

このページは、次の 1 つの文に要約できます。 LFSRの多項式を Galois 形式から Fibonacci 形式に変換する場合は、係数の順序を逆にします。

たとえば、これは scramblersでよく使用される LFSR の図面です。

Scrambler based upon Galois polynomial

D でマークされた各ブロックは、1 つの clock cycleの delay です。 Galois 多項式としてのこの LFSR の表現は次のとおりです。

G(x) = x16 + x5 + x4 + x3 + 1

多項式の指数 (3、4、および 5) は、各 XORの左側にある delay elements の数を反映していることに注意してください。

次の図に示すように、同じ LFSR を Fibonacci 形式で実装できます。

Scrambler based upon Fibonacci polynomial

これらの 2 つの図は類似していますが、矢印の方向が逆になっています。 LFSRs の実装は完全に異なります。

Fibonacci 多項式 (または feedback 多項式) は次のとおりです。

F(x) = x16 + x13 + x12 + x11 + 1

多項式の次数は n=16であるため、 G(x) 内の各 xixn-iによって F(x) で表されます。このページの残りの部分では、これが偶然ではない理由を示しています。

LFSRsに関する一般的な説明については、このトピックのWikipedia ページを参照してください。

LFSR および digital filters

digital filters の背後にある理論 (たとえば、 FIRs および IIRs) は通常、 field of complex numbersに適用されます。ただし、この理論をGF(2)に適用することもできます。これは、2 つの数値で構成される finite field (Galois Field) です。 0 と 1。注意すべき点がいくつかあります。

digital filters の基本理論は、システムが Linear time-invariant (LTI) であることのみを必要とします。 XOR は線形であり、 LFSRの動作は時不変であるため、 LFSR はこれらの要件を満たしています。

最も興味深い結果は、 z-transform を使用して LFSRsを分析できることです。たとえば、次の図を考えてみましょう。

Simple filter with logic delay

これは、次の式で説明できます。

y(t) = x(t) ⊕ x(t-1)

t は時間を表す整数です。

これを FIRとして扱い、この式の z-transform を書くことができます。

Y(z) = X(z) + X(z)z-1=X(z) (1 + z-1)

したがって、「impulse response」は通常どおり定義できます。 H(z) = Y(z)/X(z)、または単に:

H(z) = 1 + z-1

しかし、これらのフィルターを 2 つ並べるとどうなるでしょうか。このフィルターの「impulse response」とは?

Two filters with logic delay in cascade

digital filters の理論には簡単な答えがあります。

H2(z) = H(z)H(z) = (1 + z-1)(1 + z-1) = 1 + 2z-1 + z-2

GF(2)では、偶数の乗算はゼロの乗算に似ていることを思い出してください。によると、

H2(z) = 1 + 2z-1 + z-2 = 1 + 0z-1 + z-2=1 + z-2

これに対応します:

Equivalent filter to two filters with logic delay in cascade

最後の 2 つの図に示されているフィルターが同等であることを確認するのは簡単ではありません。しかし、どちらのフィルターも、同じ x(t)を供給すると、同じ y(t) を生成します。したがって、2 番目の delay element に格納されている値は同じではありませんが、フィルターは同じです。

この例では、 z-transform (および多項式を使用した同様の手法) を使用して logic filtersを解析する利点を示します。

z-1の代わりに D または D-1 のシンボルがよく使用されることに注意してください。実際、 Galois および Fibonacci 多項式での x の使用は、 z-1と同じ意味を持ちます。これらの記号はすべて delayを意味します。

Galois LFSR

Fibonacci 表現を見つけるために、 Galois LFSRを調べることから始めます。

上から見た Galois LFSR の図を考えてみましょう。 delay lines と taps の行は FIR フィルターと見なすことができ、これを A(z)とします。したがって、 Galois LFSR はこれと同等です。

Galois LFSR represented as a FIR and feedback

feedbackのため、 Y(z) の式は次のとおりです。

Y(z) = Y(z)A(z)

では、この FIRのパラメータと Galois 多項式の間の接続は何ですか? Galois 多項式の一般的な形式を書きましょう。

G(x) = xn + gn-1xn-1+ gn-2xn-2+…+ g0

以下の数学を単純化するために、この式には gn が表示されないことに注意してください。また、 gn は常に 1と等しくなります。

G(x) と A(z) の関係は次のとおりです。

A(z) = gn-1z-1+gn-2z-2+…+g1z1-n+g0z-n

なぜこれが正しいのですか?上の図から Galois LFSR を取り出して、この式がどのように機能するかを示しましょう。

まずは g5に対応する XOR から見ていきましょう。 5という数字は、この XORの左側に5台の delay elements があることを意味します。ただし、 z の指数は、 XOR と FIRの outputの間の delay elements の数に依存します。これらは、 XORの右側にある delay elements です。 delay elements は全部で16台。したがって、 g5g5z-11として A(z) に表示されます。これは gn-iz-i パターンと一致します。

これを説明する別の方法は、 A(z) を time domainの FIR と見なすことです。この FIRの input は x(t) であり、その output は y(t)です。

y(t) = x(t–16) ⊕ x(t–13) ⊕ x(t–12) ⊕ x(t–11)

繰り返しますが、 t は時間を表す整数です。この表現は、 feedbackを除いた Galois LFSR を表します。この FIRの transfer function は次のとおりです。

A(z) = Y(z)/X(z) = z-16 + z-13 + z-12 + z-11

これは、 A(z) と G(x) = x16 + x5 + x4 + x3 + 1の一般的な表現と一致しています。

Fibonacci 相当品

Fibonacci 形式の LFSR は、次の多項式で表されます。

F(x) = fnxn+fn-1xn-1+…+f1x + 1

f0 は常に 1に等しいため、この多項式には表示されないことに注意してください。これは、 G(x)に表示されない gn に似ています。

この多項式の実装は次のとおりです。

y(t) = f1y(t-1) + f2y(t-2) +…+ fny(t-n)

したがって、 z transform は次のとおりです。

Y(z) = f1Y(z)z-1+f2Y(z)z-2+…+fnY(z)z-n

B(z) を次のように定義しましょう。

B(z) = f1z-1+f2z-2+…+fnz-n

したがって、Y(z) は次のように記述できます。

Y(z) = Y(z)B(z)

その Y(z) = Y(z)A(z)の上から思い出してください。したがって、 LFSR の Fibonacci 形式が Galois 多項式によって与えられる LFSR と同じように動作する場合、 A(z) = B(z)に従います。これは、次のことも意味します。

fi=gn-i (i=1,2, … , n)

だから私は最初から言ったように: LFSRの多項式を Galois 形式から Fibonacci 形式に変換するには、係数の順序を逆にします。

LFSRの inverse filter

繰り返しますが、これは LFSRの Fibonacci 実装です。

y(t) = f1y(t-1) + f2y(t-2) +…+ fny(t-n)

しかし、この式は次のように書き直すこともできます。

y(t) + f1y(t-1) + f2y(t-2) +…+ fny(t-n) = 0

( + と – は GF(2)で同じであることを思い出してください)

したがって、 Fibonacci 多項式の係数は、常に値ゼロを取得するために、 y(t-i) の値に対して XOR を実行する方法も教えてくれます。つまり、これは興味深い FIRを表しています。

最後の式の z transform は次のとおりです。

Y(z) + f1Y(z)z-1+f2Y(z)z-2+…+fnY(z)z-n = 0

または、同等に:

Y(z)(1+ f1z-1+f2z-2+…+fnz-n) = Y(z)H(z) = 0

Y(z)H(z) は、 Y(z)にフィルター H(z) を適用した場合の output です。そしてこの output はゼロ。

したがって、 H(z) は FIR filterの transfer function です。この FIR に、 F(x)で定義された LFSR の output をフィードすると、 output は常にゼロになります。上記の B(z) の定義から、この FIRの transfer function は次のようになります。

H(z) = 1 + f1z-1+f2z-2+…+fnz-n

または、 time domainで、 input が x(t) で、 output が y(t)の場合:

y(t) = x(t) ⊕ f1x(t-1) ⊕ f2x(t-2) ⊕ … ⊕ fnx(t-n)

x(t) が F(x)によって定義される LFSR の output である場合、 y(t) はすべての tに対してゼロです。

このページは英語から自動翻訳されています。 不明な点は元のページを参照してください。
Copyright © 2021-2024. All rights reserved. (6f913017)