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.