Evolution of loosely synchronized spreading codes in code-division multiple-access systems

Student thesis: Doctoral Thesis


Loosely Synchronized (LS) codes can be used as spreading codes in quasi­ synchronous code-division multiple-access (QS-CDMA) systems. In such CDMA systems, close control of synchronization is achieved at the chip level, interme­ diate between that in synchronous CDMA and that in asynchronous CDMA. The LS code can then capitalize on zero correlation in a limited synchronization window to reduce code correlations and so reduce interference. LS codes are {O, +1, -1} codes constructed using Hadamard matrices and Golay pairs. A variation of LS codes inserts short strings of zeros between the components of the Golay pairs to increase the number of codewords, with only limited dete­rioration in the correlations. These strings of zeros are known as internal padding.

One of the advantages normally claimed for CDMA systems is resistance to eavesdropping and jamming. It might appear at first sight that the structure of LS codes is rather predictable in comparison with codes constructed using linear feedback shift registers, such as m-sequences or Gold codes. One way to overcome any such difficulty would be to evolve the code very quickly, in such a way that by the time a generation of the code is determined (or determined to a moderate correlation value) it is too late to exploit it. This thesis explores the way that LS codes can be evolved in order to achieve resistance to eavesdropping and jamming.

The thesis starts with a detailed account of the necessary background and of the construction of Loosely Synchronized codes. The early part of the thesis then concentrates on showing that many generations of LS code can be constructed in such a way that the correlation between distinct generations is small. This prevents one observed generation of the code from being used for jamming or prediction in another generation. Specifically:
- The construction of Golay pairs is investigated and a search is carried out over all possible Golay pairs and their mates to find a set of pairs that leads to the satisfaction of a suitable correlation criterion;
- Bent functions, almost bent functions and other second order Boolean functions are used to create sets of Hadamard matrices that are guaranteed to satisfy the same correlation criterion;
- A sequential search method to generate a set of arrangements of the internal padding that satisfies the same correlation criterion is described. Later in the thesis this approach is replaced by a recency list approach. This ensures that the correlation criterion is satisfied against recently used generations of the code, in place of all generations of the code;
- The way in which these evolutions of the components combine together is also explored.

Attention turns in the second part of the thesis to the mechanisms for evolution and the way that these might be predicted by a third party observer. Transform methods that the third party might use are described. Detailed simulations quantify the ability of the third party to identify the code during the transmission of a single bit. It is shown that theoretical resistance to early code prediction is not possible, although it might be possible to demonstrate security arising from the relative speed of the necessary computations for the user and the observer. This would require a detailed hardware study, and this is listed as future work. In fact it is shown here that LS codes are actually better than linear feedback shift register codes, as a result of the Berlekamp-Massey algorithm.

Attention is also focussed on the scenario in which details of the algorithms of one user are obtained by the third party. Only the Hadamard matrix provides protection against this scenario, as all other components of the construction are shared between all users. From this second viewpoint the true weakness of LS codes becomes apparent. Although the Hadamard matrix constructions are satisfactory if the order of the Hadamard matrix is not too small, it seems that the sequence of Hadamard matrix rows of each user must be computed centrally and distributed to users as private keys if this scenario is not to remain a major concern. The volume of private key distribution necessary may seem unattractive to operators.

Ultimately it seems that evolution of the Golay pairs may have little real role except to increase the workload of the observer. The recency list based evolution of internal padding can take the main role in ensuring low correlation between close generations of the code. The evolution of the Hadamard matrix should be designed to concentrate on the second viewpoint, where the third party has obtained details of the algorithms of one user.
Date of AwardJul 2008
Original languageEnglish
SupervisorDerek Smith (Supervisor) & Stephanie Perkins (Supervisor)


  • Code division multiple access
  • Mobile communication systems

Cite this