A Wavelet Transform Approach to the Design of Complementary Sequences for Communications

A wavelet transform approach to the design of complementary sequences for communications

Todor Cooklev, Keh-Gang Lu

School of Engineering, San Francisco State University, San Francisco CA 94132, USA

Abstract: In this paper we study the relationship between filter banks and complementary sequences. Non-periodic and periodic complementary sequences are identified to be special cases of non-periodic and periodic (or cyclic) wavelet transforms. These wavelet transforms are non-regular. A systematic approach for the generation of periodic symmetric and anti-symmetric sequences is advanced. The novel approach is based on analytic formulae. A systematic approach for the generation of all Golay sequences of a given length is also described.

Keywords: Correlation, Discrete Fourier transforms, Orthogonal functions, Sequences, Transforms, Wavelet transforms.

1. Introduction

There is a wealth of literature on the theory and design of pseudo-random (or pseudo-noise) sequences for communications with different properties of their autocorrelation and cross-correlation functions (ACF and CCF) [1-4], [11-26].

The theory of filter banks was developed completely independently and it is widely believed that it dates back to 1976, when Croisier, Esteban and Galand designed the first aliasing-free filter bank. Perfect-reconstruction was initially thought to be impossible, and was achieved by three research groups independently around 1984 (for a collection of references see [6]). The discovery of I. Daubechies that orthogonal filter banks provide orthogonal bases for the Hilbert space of square-summable sequences stimulated a tremendous research activity in the area. Furthermore I. Daubechies showed that provided the filters satisfy constraints additional to PR, regular (or smooth) continuous-time functions (scaling functions and wavelets) can be obtained, which are orthogonal bases for the space of square-integrable functions [5].

The main purpose of this paper is firstly to demonstrate the relationship between wavelet transform theory and the theory of complementary sequences, and secondly to develop novel formulae for the analytic construction of complementary sequences using wavelet (or filter bank) theory. We shall consider one important class of sequences, namely complementary sequences. These sequences were recently found to be efficient in a new modulation for wireless communications, called spread-signature CDMA [10]. The connection between two-channel orthogonal FIR filter banks and aperiodic complementary sequences was observed by several researchers [7, 9] and is not novel. Periodic complementary sequences were advanced in [26]. It is shown here that they can be approached using the cyclic wavelet transform. This allows us to develop systematic algorithms for their generation. These two new sets of orthogonal sequences are generalizations of the Golay sequences in the sense that the Golay sequences are members of both of these sets. The novel approach allows to derive formulae for the systematic generation of Golay sequences, which are also given. Previously these sequences could only be generated using computer searches.

The paper is organized as follows. In Section 2 we review filter bank theory. Section 3 is a review of Golay (non-periodic complementary sequences) and Section 4 is a review of various generalizations of these sequences. Section 5 is devoted to orthogonal periodic symmetric codes, and Section 6 - to anti-symmetric codes. Section 7 is devoted to a systematic synthesis of Golay complementary pairs.

2. Two-channel orthogonal FIR filter banks

Two-channel orthogonal FIR filter banks are the most fundamental and widely used class of filter banks [5, 6]. They consist of two parts (Fig. 1): an analysis part of two filters and , each followed by downsampling, and a synthesis part, consisting of upsampling in each channel followed by two filters and . It is easily shown that the output signal, is given by

(1)

In perfect-reconstruction (PR) filter banks we have = X(z) and therefore

(2)

(3)

The transform which represents the computation of the two subband signals and from x[n] is called a forward wavelet transform. The transform which computes the signal (which is equal to x[n]) is called an inverse wavelet transform. In orthogonal filter banks the impulse response together with its integer translates forms an orthogonal basis for the Hilbert space of square summable sequences. The aperiodic auto-correlation function (ACF) of the impulse responses and are half-band functions:

(4)

(5)

while the cross-correlation is identically zero

(6)

Any two sequences and with the auto-correlation and cross-correlation properties in (5), (6) and (7) define an orthogonal wavelet transform and the two sequences are an orthogonal basis for the Hilbert space of square-summable sequences. The synthesis filters are completely determined from the analysis filters:

(7)

(8)

where the operation means transposition, conjugation of the coefficients and replacing z by z−1. In the time-domain is related to according to

(9)

where N is the order of the filters and is necessarily odd. A necessary and sufficient condition for perfect-reconstruction is that the product P(z) = = = be half-band:

(10)

Splitting the even-indexed and odd-indexed coefficients is called a polyphase decomposition:

(11)

(12)

3