
	ECE4253 Digital Communications

	Department of Electrical and Computer Engineering - University of New Brunswick, Fredericton, NB, Canada

Linear Recursive Sequence Generator

Shift registers with feedback essentially divide polynomials to create distinctive binary sequences.

This online tool draws and analyzes digital circuits which generate Linear Recursive Sequences (LRS) based on a defining polynomial P(x). A complete state table is derived for the sequential circuit shown below.

Galois Implementation

alternate configuration Galois

Circuit based on P(x) = x⁴+x³+x²+x+1

The circuit taps generally correspond to P(x) = (11111) in reversed order, although this specific ordering is not evident when the bit sequence is symmetric as in this example.

State Table

This circuit may be analyzed by considering what would happen when the shift register is clocked for each possible state of the circuit. In the state table below, the shift register is filled with each possible value and the contents after the next clock are computed. Results are shown in binary and in decimal. A sequence of states may be traced by following the states from any starting value. The least significant bit is shifted out to create a bitstream output sequence.

Taps: (11111) (prime)

THIS STATE		⇒	NEXT STATE
0 0 0 0	0	⇒	0 0 0 0	0
0 0 0 1	1	⇒	1 1 1 1	15
0 0 1 0	2	⇒	0 0 0 1	1
0 0 1 1	3	⇒	1 1 1 0	14
0 1 0 0	4	⇒	0 0 1 0	2
0 1 0 1	5	⇒	1 1 0 1	13
0 1 1 0	6	⇒	0 0 1 1	3
0 1 1 1	7	⇒	1 1 0 0	12
1 0 0 0	8	⇒	0 1 0 0	4
1 0 0 1	9	⇒	1 0 1 1	11
1 0 1 0	10	⇒	0 1 0 1	5
1 0 1 1	11	⇒	1 0 1 0	10
1 1 0 0	12	⇒	0 1 1 0	6
1 1 0 1	13	⇒	1 0 0 1	9
1 1 1 0	14	⇒	0 1 1 1	7
1 1 1 1	15	⇒	1 0 0 0	8

See the various output sequences for this circuit.

Specify the taps for your sequence

Modulo 2 addition is shown schematically equivalent to Exclusive-OR gates.


2024-05-18 10:18:56 ADT Last Updated: 04-09-25	Richard Tervo [ tervo@unb.ca ]	Back to the course homepage...