COMPENG 4TS3

INTRODUCTION TO DIGITAL SEQUENCES

Undergraduate

Fall 2025 · C01

Topics

Introduction, Feedback Shift Registers (FSRs), the binary field and finite fields modulo a prime, Linear Feedback Shift Registers (LFSRs)
Generating functions, characteristic polynomials, periodicity, irreducible and primitive polynomials, Pseudo-Noise (PN) sequences (a.k.a. m-sequences)
Correlation: auto/cross, period/aperiodic, real/complex/Hamming, maximum out-of-phase-autocorrelation
Difference sets, quadratic residues, and Legendre sequences
Aperiodic auto-correlation: Barker sequences, Costas arrays (2D sequences)
De-Bruijn sequences: the De-Bruijn graph, existence of De-Bruijn sequences, construction using cycle merging
Linear complexity: definition, properties, the Games-Chan algorithm
Rotating table games, the Berlekamp-Massey algorithm
Gray codes: definition, binary reflected Gray codes, case study: Skew-Tolerant Gray Codes (SkTGCs)
String-Duplication systems: definition and motivation, duplication-free sequences, the Thue-Morse sequence

Sources