Układy logiczne

Rejestr liczący to układ pokazany na Rys.3.

Rys.3. Rejestr liczący

Rejestr liniowy nazywamy też rejestrem LFSR ( ang. Linear Feedback Shift Register). Jest to rejestr liczący z funkcją boolowską \(f\) zadaną wzorem

\(f(Q_n,Q_{n-1},...,Q_0)=k_nQ_n \oplus k_{n-1}Q_{n-1} \oplus .... \oplus k_0Q_0 \qquad\qquad\qquad (^*)\)

gdzie \((k_n,k_{n-1},...,k_0)\in\{0,1\}^{n+1}\) jest ustalonym słowem binarnym definiującym rejestr liniowy. Funkcja \(f:\{0,1\}^{n+1}\rightarrow\{0,1\}\) zdefiniowana wzorem (*) jest przekształceniem liniowym stąd nazwa rejestru. Rejestr liniowy jest szczególnym przypadkiem tzw. maszyny liniowej lub automatu liniowego (Linear Sequential Machine). Każdy rejestr liniowy jest scharakteryzowany przez swój tzw. wielomian charakterystyczny

\(w(x)=k_nx^n\oplus k_{n-1}x^{n-1}\oplus ... \oplus k_1x\oplus k_0\)

Jest to wielomian o współczynnikach w ciele \(Z_2\). Jeśli wielomian charakterystyczny jest nierozkładalny, to rejestr liniowy wychodzący z dowolnego stanu różnego od samych zer przechodzi przez \(2^{n+1}-1\) stanów.

Rejestry liniowe stosowane są między innymi jako generatory liczb pseudolosowych.