ポリノミアルカウンタ

以前、仕事でIC設計に関わった時に使ったカウンタ。ふと思い出したので、記録。

そのカウンタは次のような感じで定義されるものです。

Kビットからなる値xの各ビットをx[i]、つまりx=(x[K-1], x[K-2],...,x[0])として、
数列x₀,x₁,...,x_nを次のように定義する。

x_n+1[i] = x_n[i-1]
(ただし、iは0より大きくKより小さい値)

x_n+1[0] = ~(x_n[K-1]^x_n[0])
(~は否定(ビット反転)、^は排他的論理和)

このカウンタの特徴は、たとえば4ビットのカウンタであれば0,1,2,5,10,4,9,3,6,13,11,7,14,12,8,0,1,...というように、数値が大小順では並ばないところと、全ビットが1になる値(この場合は15)が現れないところにあります(全ビットが1の値は、この計算を当てはめてもずっと同じ値…15ならずっと15…しか生成しません)。

このカウンタの利点は、加算器が不要というところにあります。Kビットのシフトレジスタと排他的論理和の否定があればよいわけで、ICのロジックを減らしたいときに重宝したみたいです。わたしが関わったのは電卓用の4ビットICでした。

Haskellで再現。ちょっと不格好な気がする。

import Data.Bits

polynomialCounter :: Int -> Int -> [Int]
polynomialCounter n m = m:(polynomialCounter n next)
  where
    next = ((shift m 1) .|. ((complement $ xor (shift m (1-n)) m) .&. 1)) .&. (bit n - 1)

-- 4ビットで初期値が0のカウンタの、最初の16個の値
take 16 $ polynomialCounter 4 0

追記

投稿してから調べてみたら。やっぱりいくつか種類があるみたいですね。