Perfect Sequences

One approach for the identification of unkown linear systems relies on the least mean square (LMS‐type) algorithm in combination with its optimal excitation signal, i.e., a perfect sequence (PSEQ) [Antweiler 1995], [Antweiler 2008]. PSEQs are time discrete, binary, ternary or polyphase sequences of length M. The distinctive attribute is, that they show an (ideal) impulse‐like periodic autocorrelation function, i.e., the autocorrelation function vanishes for all out‐of‐phase values.

Within our studies we applied two different classes of PSEQs, odd‐perfect sequences [Lüke 1995] and perfect sweeps [Telle 2010], [Antweiler 2012]. To enable easy access to PSEQs, the software for generation, is published here as open source under a BSD‐style license for

• the odd‐perfect sequences
• the perfect sweeps.

Odd‐perfect sequences [Lüke 1995] represent one interesting class of perfect sequences. Odd‐perfect sequences are symmetrical, quasi‐binary sequences, which, except for a (leading) zero, only take two amplitudes {‐a, a}. An odd‐perfect sequence of length M=6, e.g., is p(k) = {0, a, a, a, ‐a, a}. Thus, odd‐perfect sequences are almost binary and exhibit a high energy efficiency of (M‐1)/M.

In contrast to classical ternary PSEQs, such as Ipatov sequences [Ipatov 1979] or perfect sweeps [Telle 2010], [Antweiler 2012], odd‐perfect sequences have to be applied periodically in an odd‐cyclic manner, which means that the sign is alternated in each period. The example above would lead to the periodic excitation signal p(k) = {0, a, a, a, ‐a, a, 0, ‐a, ‐a, ‐a, a, ‐a, 0, a, a, ... }.

As the period length must match length M of the adaptive filter, it is of interest that they can be generated for every length M=q^w+1, where q denotes a prime number, q>2, and w denotes a natural number.

The code is tested to compile and run under Linux (CentOS 5.2, GCC 4.1.2), Windows (Windows XP, Visual Studio 2008 with Feature Pack) and Mac OS X (10.5.6, GCC 4.0.1). Other Platforms and/or compilers are not supported. For more information on the software see the documentation in the source package provided at the bottom of this page.

At the moment not all of the code is optimized for speed, so for lengths larger than 20 000 the implementation gets quite slow (10 s on Intel Core 2 Duo 2,4 GHz for length of about 20 000).

• CMake 2.6 or newer to generate the makefiles or project files.
• A C++ compiler supporting the TR1 extension <array>, e.g., GCC version 4.0 and newer or Visual Studio 2008 with VC++ 2008 Feature Pack.

• oddpseq-1.0.0-Windows.exe (Binary for Windows, 206 KB)
• oddpseq-1.0.0-Linux.zip (Binary for Linux, 330 KB)
• oddpseq-1.0.0-Darwin.dmg (Binary for Mac OS X (Darwin), 28 KB)
• oddpseq-1.0.0-Source.zip (Source code, 20 KB)

Sweep signals can also be constructed such that they meet the orthogonality requirements for an optimal excitation signal of the LMS algorithm [Telle 2010]. For the system identification approach the perfect sweep has to be scaled and periodically applied to the system under test. The period of the perfect sweep must match the length M of the adaptive filter. Perfect sweeps can be generated for each length M.

In contrast to odd‐perfect sequences, the energy efficiency of perfect sweeps is much lower. However, for sound reproduction, the perfect sweep is superior in terms of robustness against nonlinear acoustic distortions or, in other words, perfect sweeps can be passed with less distortions through the measurement system than odd‐perfect sequences.

The code is a simple MATLAB function with the call

s = perfectsweep(f_s, M) or s = perfectsweep(f_s, M, range),

which basically creates a “prototype” perfect sweep of length M with normalized amplitude and sampling rate fs with a perfectly constant magnitude spectrum. It covers all frequencies from 0 to fs/2 and runs from the first to the last sample.

perfectsweep.m 3 KB 

[antweiler95a]
Christiane Antweiler and Markus Antweiler
System Identification with Perfect Sequences Based on the NLMS Algorithm
International Journal of Electronics and Communications (AEÜ), May 1995

[antweiler08]
Christiane Antweiler
Multi-Channel System Identification with Perfect Sequences - Theory and Applications -
Advances in Digital Speech Transmission, January 2008

[antweiler12]
Christiane Antweiler, Aulis Telle, Peter Vary, and Gerald Enzner
Perfect-Sweep NLMS for Time-Variant Acoustic System Identification
Proceedings of IEEE International Conference on Acoustics, Speech, and Signal Processing (ICASSP), March 2012

[telle10]
Aulis Telle, Christiane Antweiler, and Peter Vary
Der perfekte Sweep - Ein neues Anregungssignal zur adaptiven Systemidentifikation zeitvarianter akustischer Systeme
Proceedings of German Annual Conference on Acoustics (DAGA), March 2010