Page 629 - Engineering Digital Design

12.4 SHIFT-REGISTER COUNTERS 599

Table 12.1 Examples of Feedback Functions for Near-Maximum-Length ALFSR Counters

Feedback function Near maximum length
SR size, n-bits Feedback function /( Q) (literal notation) (In nos. of states)
4 £>i £ BGo C@D 15
5 G2£DGo C ®E 31
8 G493 Gs 0 62 9&Go D®E®F®H 255
12 G695 G40 Gi 95Qo F @H ®K®L 4,095
\\ f\
~Lf /T\ r /T\ fl/f^ /^T\ I>
16 Gs93 G4 0 G3 9L? |^ (J i v \I/ LJ \SJ / "-/ ^17 i. 65,535
24 07 65 G2 0 Gi 95 Go G0V0W0 X 16,777,215
32 Q 22 <B G2 0 Gi <BGo — 4,294,967,295

to an 8-bit near-maximum-length ALFSR counter in literal notation. Or for 12- and 16-
bit near-maximum-length ALFSR counters, the feedback functions F © H © K 0 L and
K © L © M © P apply, respectively. Shown in Table 12.1 are a few feedback functions that
apply to right- shifted, near-maximum-length ALFSR counters. Note that for the numeral
notation Q 0 is always the LSB, and that for the literal notation Q A = A is always the MSB
of the counter.
As has been pointed out earlier, ALFSR counters are very useful in generating pseudo-
random test vectors suitable for testing a variety of machines, combinational and sequential.
16
Take, for example, a 16-bit ALFSR counter. It can sequence through 2 — 1 = 65,535
unique pseudorandom states in iterative fashion if the all-zero state is forbidden, or through
65,536 states if corrected to include the all-zero state. If a 32-bit ALFSR counter is used for
testing, a total of 4,294,967,296 unique pseudorandom states are available with correction
to include the all-zero state. Some large state machines are designed with ALFSR counter
elements in them to provide a built-in- self -test (BIST) capability. BIST capability facilitates
and automates testing of these machines without need for an external testing facility.
Correction for inclusion of the all-zero state in the general case for maximum-length
ALFSR counters is not trivial, but it is not difficult either. Consider that upon initializing
into the all-zero state 00000 • • • 00 the next transition must be into the 10000 • • • 00 state to
begin the pseudorandom sequence. Then, at the end of the 2" sequence, in the 00000 • • • 01
state, the ALFSR counter must return to the all-zero state. For all of this to happen, a
correction function must be found and XORed with the feedback function. Noting that all
feedback functions in Table 12.1 end with <2o, it follows that the correction functionjnust
be the ANDed complements of all ALFSR counter outputs except <2o, that is, Q n-\ • Q n-2 •
---- &2 • Q i • Here, Q n-\ is the MSB and QQ is the LSB. Therefore, the corrected feedback
function is given by

/(corrected) = (£„_, - Q H_ 2 ..... Q 2 • Qi) © /(G), (12.12)

where f(Q) is the numeral feedback function in column 2 of Table 12. 1. Thus, it follows that
the corrected feedback functions for 4-bit, 5-bit, and 8-bit ALFSR counters are(<23<22<2i)©

respectively. Applying Eq. (12.12) to the 16-state ALFSR counter in Fig. 12.36 yields