直接形と転置形

[←]　[↑]　[→]

---

1個ずつシフトインされるN個のデータに対する演算も、データが全部そろってから計算するのがRTL記述としてはわかりやすいが、回路構造を考えると、部分的な演算結果をシフトしていく回路にした方が組合せ回路が小さくなって高速動作する。

(1) 直接形(direct)

(2) 転置形(transpose)

　シフトイン入力のファンアウトが大きくならないように間にFFを挟んでもよい。

例1) FIRフィルタ

入力にフィルタ係数c_nをかけて和をとるには f_n(x,y) = c_n * x + y

dout[i] = c₀ * din[i] + c₁ * din[i+1] + c₂ * din[i+2]

例2) 文字列マッチ検出

入力が文字列 {c₀,c₁,c₂} に一致したら1を立てるには f_n(x,y) = (x==c_n ) & y

dout[i] = (c₀==din[i]) & (c₁==din[i+1]) & (c₂==din[i+2])

例3) 最大値

入力のうち最大のものを出力するには f_n(x,y) = (x>y)? x : y

dout[i] = max(din[i],din[i+1],din[i+2])

◇

入力を出力へ直結すると、Linear Feedback Shift Register (LFSR)の直接形と転置形が得られる。

生成多項式を

g(x) = g[N] x^N + g[N-1] x^N-1 + ... + g[1] x + g[0]

ここで g[N]=g[0]=1  g[*]=0,1

とすると次図のようになる。ただしXOR(+)は係数g[i]=1の所だけにつく。

(1) フィボナッチLFSR

(2) ガロアLFSR

両者においてd[N-1:0]の値は同じシーケンスにならないが、doutは、初期値d[N-1:0]=0...01から始めれば同じシーケンスになる。

ちなみに、なぜフィボナッチとガロアの名前がついているのかはわからない。

---

[←]　[↑]　[→]