Method and apparatus for efficient synchronization in spread spectrum communications

A method for correlating at a first transceiver a received signal transmitted by a second transceiver, comprising:

• using a matched filter corresponding to a complementary pair of sequences to correlate the received signal with one of the complementary pair of sequences;
• detecting a peak output from the matched filter, and using the detected peak output to generate a timing estimate for synchronizing transmissions between the first and second transceivers,
• wherein the complementary pair of sequences is a complementary pair of sequences determined in accordance with the following:
• a0(k)=δ(k)
• b0(k)=δ(k)
• an(k)=an−1(k)+Wn·bn−1(k−Dn)
• bn(k)=an−1(k)−Wn·bn−1(k−Dn),
• where k=0,1,2, . . . , 2N−1;
• n=1,2, . . . ,N;
• Dn=2Pn;
• an(k) and bn(k) are the complementary pair of sequences of length 2N;
• δ(k) is the Kronecker delta function;
• k is an integer representing the time scale;
• n is the iteration number, Dn is a delay, Pn, n=1,2, . . . , N, is any permutation of numbers {0,1,2, . . . , N−1};
• and Wn is an arbitrary complex number of unit magnitude.

A method for generating a synchronization sequence at a first transceiver for transmission to a second transceiver, comprising:

• generating a sequence from a pair of sequences having minimal aperiodic autocorrelation values for all non-zero delays of that sequence and a maximal autocorrelation value for a zero delay of that binary sequence;
• and
• transmitting a signal from the first transceiver using the sequence to permit a second transceiver to synchronize with the first transceiver,
• wherein the sequence is obtained from a pair of sequences of length L=2N, where N is a positive integer, and
• wherein the pair of sequences is determined in accordance with the following:
• a0(k)=δ(k)
• b0(k)=δ(k)
• an(k)=an−1(k)+Wn·bn−1(k−Dn)
• bn(k)=an−1(k)−Wn·bn−1(k−Dn),
• where k=0,1,2, . . . , 2N−1;
• n=1,2, . . . , N;
• Dn=2Pn;
• an(k) and bn(k) are the pair of sequences of length 2N;
• δ(k) is the Kronecker delta function;
• k is an integer representing the time scale;
• n is the iteration number, Dn is a delay, Pn, n=1,2, . . . , N, is any permutation of numbers {0,1,2, . . . , N−1};
• and Wn is +1 or −1.

A method for synchronizing a first transceiver to a second transceiver, comprising:

• correlating a received signal with one of a pair of sequences using an efficient correlation procedure providing a minimal number of mathematical operations, where the pair of sequences has a property that the sum of their aperiodic autocorrelations equals zero for all non-zero time shifts;
• detecting at what point in time during the correlating a maximal autocorrelation value is obtained;
• and
• synchronizing a next transmission to the second transceiver based on the detected time,
• wherein the pair of sequences are determined in accordance with the following:
• a0(k)=δ(k)
• b0(k)=δ(k)
• an(k)=an−1(k)+Wn·bn−1(k−Dn)
• bn(k)=an−1(k)−Wn·bn−1(k−Dn),
• where k=0,1,2, . . . , 2N−1;
• n=1,2, . . . ,N;
• Dn=2Pn;
• an(k) and bn(k) are the pair of sequences of length 2N;
• δ(k) is the Kronecker delta function;
• k is an integer representing the time scale;
• n is the iteration number, Dn is a delay, Pn, n=1,2, . . . , N, is any permutation of numbers {0,1,2, . . . , N−1};
• and Wn is an arbitrary complex number of unit magnitude.

In a direct sequence, spread spectrum radio transceiver, a sequence correlator efficiently correlating a received spread spectrum signal with a pair of complementary sequences of length L=2N with N being any positive integer, comprising:

• N serially concatenated processing stages, each stage having first and second parallel processing branches;
• each stage of the first processing branch including a delay line having plural memory elements coupled to a corresponding adder;
• wherein in each processing stage, samples of an input signal are successively stored in memory elements of the corresponding delay line, the content of a last memory element being input to the adder and to the subtractor of the same processing stage;
• and
• wherein the input signal is multiplied in the multiplier in the same stage by a corresponding weighting coefficient, and the output of the multiplier is fed as an input to the subtractor and to the adder in the same stage.

A correlator correlating at a first transceiver a received spread spectrum signal transmitted by at a second transceiver using one of the sequences from a pair of sequences of length L=2N, where N is any positive integer, and where the one sequence is represented as a concatenation of two shorter, constituent sequences of length X, each constituent sequence having been repeated L/X times and modulated by +1 or −1 according to a signature sequence of length Y=L/X, comprising:

• a first correlator of a length X receiving the spread spectrum signal and generating an intermediate pair of correlation values corresponding to the constituent sequences;
• a first selector alternately supplying one of the intermediate pair of correlation values during each of successive time windows based on a current value of an interleaving sequence of length Y=L/X whose elements belong to the set {0,1}, where an order of concatenation of the constituent sequences is determined by the interleaving sequence;
• a multiplier multiplying the selected intermediate correlation values with an element of the signature sequence to generate a multiplied correlation output;
• and
• a summer summing the multiplied correlation output with a feedback output of a delay line having X memory elements and providing the resulting sum as an input to the delay line,
• wherein a final correlation value corresponds to the resulting sum after Y successive time windows.

A method for correlating at a first transceiver a received spread spectrum signal transmitted by at a second transceiver using one of the sequences from a pair of Golay complementary sequences of length L=2N, where N is any positive integer, comprising:

• representing the one Golay sequence as a concatenation of two shorter, constituent complementary sequences A(k) and B(k) of length X, each constituent sequence having been repeated L/X times and modulated by +1 or −1 according to a signature sequence of length Y=L/X, where an order of concatenation is determined by an interleaving sequence of length Y=L/X, whose elements are 0 or 1, comprising:
• using a Golay correlator of a length X receiving the spread spectrum signal to generate an intermediate pair of correlation values corresponding to the constituent Golay complementary sequences;
• storing the intermediate correlation values at a first correlation output of the Golay correlator in a first group of Y=(L/X)−1 or less serially concatenated delay lines, where each delay line has X memory elements;
• storing the intermediate correlation values at a second correlation output of the Golay correlator in a second group of Y=(L/X) −1 or less serially concatenated delay lines, where each delay line has X memory elements;
• multiplying the first correlator output and the outputs of the first group of delay lines by respective elements of a reverted version of the signature sequence;
• summing only those multiplied intermediate correlation values from the first correlation output and attached delay lines which correspond to non-zero elements of a reverted version of the interleaving sequence, and only those multiplied intermediate correlation values from the second correlation output and attached delay lines which correspond to non-zero elements of the inverted and reverted version of the interleaving sequence, where the first element of the reverted version of the interleaving sequence corresponds to the correlator output and the last element of such sequence corresponds to the output of the last delay line in the cascade;
• and
• outputting a result of the summing step as a final correlation value.

A correlator for use in a base station to correlate a received signal transmitted by a mobile station, comprising:

• a matched filter corresponding to a complementary pair of sequences to correlate the received signal with one of the complementary pair of sequences, where each of the complementary sequences has minimal aperiodic autocorrelation sidelobe values for all non-zero delays of that complementary sequence and a maximal autocorrelation main lobe value for a zero delay of that complementary sequence;
• a detector detecting a peak output from the matched filter;
• and
• timing circuitry using the detected peak output to generate a timing estimate for synchronizing transmissions between the base station and mobile station;
• wherein the complementary sequences include a primary synchronization sequence and plural secondary synchronization sequences transmitted by the base station and used by the mobile station to attain primary and secondary synchronization with the base station.

A bank of correlators for use in a mobile transceiver to correlate received signals transmitted by a base station with a plurality of Golay complementary sequences, each correlator comprising:

• a matched filter corresponding to a Golay complementary pair of sequences to correlate the received signal with one of the Golay complementary pair of sequences;
• a detector detecting a peak output from the matched filter;
• and
• timing circuitry using the detected peak output to generate a timing estimate for synchronizing transmissions between the mobile transceiver and the base station.

A method for use in synchronizing mobile stations with a base station using a primary synchronization code and plural secondary synchronization codes transmitted by the base station, comprising:

• providing one of a set of Golay complementary sequences as the primary synchronization code;
• providing plural other ones of the set of Golay complementary sequences with minimal cross-correlation with the primary synchronization code as the secondary synchronization codes;
• and
• obtaining a primary synchronization and a secondary synchronization with the base station using the provided primary and secondary synchronization codes.