線形帰還シフトレジスタ(LFSR)のガロア多項式とフィボナッチ多項式の変換

はじめに

このページは、次の 1 文に要約できます。LFSR の多項式をガロア形式(Galois form)からフィボナッチ形式(Fibonacci form)へ変換したいなら、係数の並びを逆順にすればよい、ということです。

たとえば、次の図はスクランブラ(scrambler)でよく使われる LFSR の回路図です。

D の印が付いた各ブロックは、1 クロック分の遅延を表します。この LFSR をガロア多項式で表すと、次のようになります。

G(x) = x¹⁶ + x⁵ + x⁴ + x³ + 1

この多項式の指数(3、4、5)が、各 XOR(排他的論理和)の左側にある遅延素子の数を表していることに注意してください。

同じ LFSR は、次の図のようにフィボナッチ形式でも実装できます。

この 2 つの図はよく似ていますが、矢印の向きが逆です。LFSR の実装はまったく異なります。

フィボナッチ多項式(またはフィードバック多項式)は、次のとおりです。

F(x) = x¹⁶ + x¹³ + x¹² + x¹¹ + 1

この多項式の次数は n=16 です。そこで、G(x) の各 xⁱ は、F(x) の中では x^n-i に対応します。このページの残りの部分では、これが偶然ではない理由を説明します。

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

LFSR とデジタルフィルタ

デジタルフィルタ(たとえば FIR や IIR)の理論は、通常は複素数体上で考えられます。しかし、この理論は、GF(2) の上でも適用できます。GF(2) は、0 と 1 の 2 つの数だけからなる有限体(ガロア体、Galois Field)です。注意すべき点がいくつかあります。

• この体における加算演算子は XOR に相当します。
• ここでの乗算には整数しか登場しません。実際、偶数を掛けることは 0 を掛けることと同じです。同様に、奇数を掛けることは 1 を掛けることと同じです。その数が正であっても負であっても構いません。
• この乗算の規則により、加算と減算は同じ意味になります。どちらも ⊕(XOR)で置き換えることができます。

デジタルフィルタの基本理論では、対象のシステムが線形時不変(Linear time-invariant、LTI)であることだけが求められます。LFSR はこの要件を満たします。XOR は線形ですし、LFSR の動作は時不変だからです。

最も興味深い帰結は、z 変換(z-transform)を使って LFSR を解析できることです。たとえば、次の図を考えてみましょう。

これは次の式で表せます。

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

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

これは FIR として扱えます。この式の z 変換は次のように書けます。

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

したがって、「インパルス応答」も通常どおり、H(z) = Y(z)/X(z) として定義できます。すなわち、次のようになります。

H(z) = 1 + z^-1

では、このフィルタを 2 つ縦続接続するとどうなるでしょうか。このフィルタの「インパルス応答」はどうなるでしょう?

デジタルフィルタの理論には、簡単な答えがあります。

H₂(z) = H(z)H(z) = (1 + z^-1)(1 + z^-1) = 1 + 2z^-1 + z^-2

GF(2) では、偶数を掛けることが 0 を掛けることと同じになることを思い出してください。すると、

H₂(z) = 1 + 2z^-1 + z^-2 = 1 + 0z^-1 + z^-2 = 1 + z^-2

これは次の図に対応します。

最後の 2 つの図のフィルタが同等であることは、一目では分かりにくいかもしれません。しかし、どちらのフィルタも、同じ x(t) を与えれば同じ y(t) を出力します。つまり、2 番目の遅延素子に保存されている値は異なっていても、フィルタとしては同じなのです。

この例は、z 変換(および多項式を使った同様の手法)によってロジックフィルタ(logic filter)を解析することの利点を示しています。

ちなみに、z^-1 の代わりに D や D^-1 という記号が使われることもよくあります。実際、ガロア多項式やフィボナッチ多項式に現れる x も、z^-1 と同じ意味です。これらの記号はすべて遅延を表しています。

ガロア型 LFSR

フィボナッチ形式での表し方を見つけるため、まずはガロア型 LFSR から見ていきます。

先ほどのガロア型 LFSR の図を考えてみましょう。遅延段とタップの並びは FIR フィルタと見なせます。この FIR フィルタを A(z) とします。したがって、ガロア型 LFSR は次のように等価になります。

フィードバックがあるため、Y(z) の式は次のようになります。

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

では、この FIR のパラメータとガロア多項式の間には、どのような関係があるのでしょうか。ガロア多項式の一般形を書いてみましょう。

G(x) = xⁿ + g_n-1x^n-1+ g_n-2x^n-2+…+ g₀

なお、この式では後々の計算を簡単にするために、g_n を表に出していません。そもそも g_n は常に 1 です。

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

A(z) = g_n-1z^-1+g_n-2z^-2+…+g₁z^1-n+g₀z^-n

なぜこれで正しいのでしょうか。先ほどの図のガロア型 LFSR を使って、この式がどのように働くかを見てみましょう。

まず、g₅ に対応する XOR を見てみましょう。添字の 5 は、この XOR の左側にある遅延素子の数が 5 であることを意味します。ところが、z の指数は、XOR から FIR の出力までの間にある遅延素子の数に依存します。つまり、XOR の右側にある遅延素子の数です。遅延素子は全部で 16 個あります。したがって、g₅ は A(z) の中では g₅z^-11 として現れます。これは g_n-iz^-i というパターンと一致します。

別の説明として、A(z) を時間領域の FIR と見る方法もあります。この FIR の入力が x(t)、出力が y(t) だとします。

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

ここでも、t は時刻を表す整数です。この式は、フィードバックを含まないガロア型 LFSR を表しています。この FIR の伝達関数は次のとおりです。

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

これは、G(x) = x¹⁶ + x⁵ + x⁴ + x³ + 1 に対する A(z) の一般式と整合しています。

フィボナッチ型 LFSR

フィボナッチ形式の LFSR は、次の多項式で表されます。

F(x) = f_nxⁿ+f_n-1x^n-1+…+f₁x + 1

この多項式には f₀ が現れないことに注意してください。f₀ は常に 1 だからです。これは、G(x) に g_n が現れないのと似ています。

この多項式の実装は次のようになります。

y(t) = f₁y(t-1) + f₂y(t-2) +…+ f_ny(t-n)

これを z 変換すると、次のようになります。

Y(z) = f₁Y(z)z^-1+f₂Y(z)z^-2+…+f_nY(z)z^-n

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

B(z) = f₁z^-1+f₂z^-2+…+f_nz^-n

すると、Y(z) は次のように書けます。

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

先ほど、Y(z) = Y(z)A(z) となることを確認しました。したがって、フィボナッチ形式の LFSR が、ガロア多項式で与えられる LFSR と同じ動作をするなら、A(z) = B(z) が成り立ちます。すなわち、次の関係が得られます。

f_i=g_n-i (i=1,2, … , n)

つまり、最初に述べたとおりです。LFSR の多項式をガロア形式からフィボナッチ形式に変換するには、係数の並びを逆順にすればよいのです。

LFSR の逆フィルタ

もう一度、LFSR のフィボナッチ実装を示します。

y(t) = f₁y(t-1) + f₂y(t-2) +…+ f_ny(t-n)

この式は、次のように書き換えることもできます。

y(t) + f₁y(t-1) + f₂y(t-2) +…+ f_ny(t-n) = 0

(GF(2) ではプラスとマイナスが同じ意味になることを思い出してください)

つまり、フィボナッチ多項式の係数は、y(t-i) の値に対してどのように XOR をとれば常にゼロが得られるかも教えてくれます。言い換えれば、これは興味深い FIR を表しています。

最後の式を z 変換すると、次のようになります。

Y(z) + f₁Y(z)z^-1+f₂Y(z)z^-2+…+f_nY(z)z^-n = 0

あるいは、同じ意味で次のようにも書けます。

Y(z)(1+ f₁z^-1+f₂z^-2+…+f_nz^-n) = Y(z)H(z) = 0

Y(z)H(z) は、フィルタ H(z) を Y(z) に適用したときの出力です。そして、この出力はゼロになります。

したがって、H(z) は FIR フィルタの伝達関数です。この FIR に F(x) で定義される LFSR の出力を入力すれば、出力は常にゼロになります。上記の B(z) の定義から、この FIR の伝達関数は次のようになります。

H(z) = 1 + f₁z^-1+f₂z^-2+…+f_nz^-n

時間領域で表すなら、入力が x(t)、出力が y(t) のとき、次式になります。

y(t) = x(t) ⊕ f₁x(t-1) ⊕ f₂x(t-2) ⊕ … ⊕ f_nx(t-n)

x(t) が F(x) で定義される LFSR の出力である場合、y(t) はすべての t についてゼロになります。