Odd-perfect Sequences
Several approaches have addressed the problem of measuring linear and time-invariant (LTI) system responses. In 1994/95 we introduced an alternative approach for the identification of an unknown linear system given the input and the output signal. This method can be grouped into the class of cross-correlation based methods. It relies on the well-known normalized least-mean-square (NLMS) algorithm excited by a periodic so called perfect sequence (PSEQ) [Antweiler, Antweiler 1995], [Antweiler 2008].
One interesting class of PSEQs are the odd-perfect sequences [Lüke, Schotten 1995]. 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 N=6, e.g., is
p(k) = {0, a, a, a, -a, a}.
For the system identification approach the odd-perfect sequence is periodically applied in an odd-cyclic manner, i.e., 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 the length N of the adaptive filter, it is of particular advantage that odd-perfect sequences can be generated for every length
N = qw+1 with q>2 prime, w natural number.
To enable easy access to odd-perfect sequences, the software we use to generate odd-perfect sequences ourselves is published here as open source under a BSD-style license.
References
- Antweiler, C. and Antweiler, M.:System Identification with Perfect Sequences Based on the NLMS Algorithm,
in: International Journal of Electronics and Communications (AEÜ), vol. 3, May 1995, pp. 129–134. - Multi-Channel System Identification with Perfect Sequences - Theory and Applications -,
in: Advances in Digital Speech Transmission, ed. by Martin, R., Heute, U., and Antweiler, C., Chichester, UK: John Wiley & Sons, Ltd., Jan. 2008, ch. 7, pp. 171–198, ISBN: 978-0-47051-739-0.
- Lüke, H.; Schotten, H.:
Odd-Perfect, Almost Binary Correlations Sequences
,
Transactions on Aerospace and Electronic Systems, vol. 31, pp. 495-498, 1995.
Provided Software
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).
Prerequisites for building from source
- 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.
Downloads
|
Binary for Windows |
206 K |
|
Binary for Linux |
330 K |
|
Binary for Mac OS X (Darwin) |
28 K |
|
Source code |
19.9 K |
Version History
(v1.0.0) - First official release