Generalised GMW Sequences

Families of binary sequences with low correlation are required in applications such as wireless communications, ranging and time delay measurement and digital watermarking, among others. Many constructions have been proposed that employ m-sequences as basic building blocks, such as the Gordon-Mills-Welch (GMW) sequences. In this work we present a unified construction of GMW sequences derived from suitable m-sequences by using the method of composition, producing sequences of length
$2^{n}-1$
with
$n$
being an integer composite number. A given m-sequence is folded using the Chinese remainder theorem (CRT) into a two dimensional array, whose columns are either constant or cyclic shifts of a short
$m$
-sequence. Then, the array can be summarized by a short
$m$
-sequence and the sequence of shifts (shift sequence). By looking at array interpretation, we avoid using Trace representation of intermediate fields, which makes its implementation more straightforward and secure. Pseudonoise arrays can be produced by constructing all the valid columns and shift sequences, the latter obtained by proper decimations and proper multiplication. Equivalences are removed by selecting a cyclotomic set leader from the degenerate conjugacy class. The window properties of these sequences can be exploited to construct generalized GMW sequence generators for lengths as large as the long codes in GPS i.e.
$2^{42}-1$
. A similar generalisation of the small Kasami sets can be constructed using this algorithm. The complexity of the algorithms is
$\sqrt{L}$
where
$L$
is the length of the sequence, improving known algorithms. Finally, the shift sequences constructed in this work are good candidates to frequency hopping and time hopping sequences in UWB wireless communications and localisation systems.