For many applications, such as cryptography and digital communications, binary sequences with certain specific properties are required. These include a balance of 0's and 1's in a period, ideal runs frequencies, good auto- and cross-correlation spectra, and high linear complexity. Perfect Linear Complexity Profile sequences (PLCPs) have the linear complexity of all subsequences (starting with the first bit) equal to half the length of the subsequence (this is the expected value for a random sequence). We investigate the density - proportion of ones - of finite length PLCPs, both in general and for specific examples. We gain results on the average, maximal and minimal densities, as well as their limits as the length tends to infinity. We also study whether the PLCP property is preserved under various decimations. PLCPs are characterised by a simple linear recurrence modulo 2. We look at similar "nearly" perfect profiles and characterise sequences with these profiles in terms of similar recurrences. Also sequences with a PLCP up to a point and then constant complexity are characterised in terms of the convergents in the continued fraction expansion of the generating function of PLCPs, and we look briefly at their corresponding periods. Sequences with bounded jumps in their linear complexity are discussed and a method of generating them is suggested. The interleaving of shifts of a sequence with out-of-phase auto-correlation equal to -1 and balance, in a specific order, seems to be a fundamental method of generating longer sequences with this auto-correlation property. It is shown that two pairs of families of these sequences, derived in different ways, are in fact equivalent. The analysis highlights the general method mentioned above, and so provides examples of families of sequences with 2-valued auto-correlation by changing the ingredients in the interleaving pattern. We also look at the cross-correlation of sequences with this interleaved structure.
| Identifer | oai:union.ndltd.org:bl.uk/oai:ethos.bl.uk:307031 |
| Date | January 1995 |
| Creators | Houston, Alice Elizabeth Dashwood |
| Publisher | Royal Holloway, University of London |
| Source Sets | Ethos UK |
| Detected Language | English |
| Type | Electronic Thesis or Dissertation |
Page generated in 0.0025 seconds