Apparatus for synchronizing linear PN sequences

What is claimed is:

1. Apparatus for synchronizing the linear PN sequences contained in the heavy noise background of a receiver data-carrying spread spectrum signal, comprising

(a) demodulator means (106, 109) for separating from the received signal the noisy wideband PN spread spectrum component, and for generating a chip rate clock signal;

(b) resident PN generator means (110) responsive to said chip rate clock signal for producing a replica of the PN sequence with arbitrary phase;

(c) running matrix inverse means (112) for obtaining the inverse (R.sup.-1) of the matrix (R) that is formed by n successive observations of the register of the resident generator;

(d) matrix vector product means (118) for multiplying the running inverse by a column vector of noisy chips, thereby to obtain a plurality of estimates of the phase vector;

(e) means (122) for smoothing and averaging the phase vector estimates, thereby to produce the smoothed phase vector (c.sub.j);

(f) dot product means (114) responsive to said smoothed phase vector and to the contents of the resident shift register for producing the properly phased PN sequence; and

(g) despreading means (108) for combining the noisy chips with the properly phased PN sequence, whereby the narrowband digital data carried by the spread spectrum signal may be recovered.

2. Apparatus as defined in claim 1, and further including phase delay computer means (130) for converting the smoothed phase vector to actual phase delay, thereby affording range computation.

3. Apparatus as defined in claim 1, wherein said matrix vector product means includes

(1) a plurality of AND gates having output terminals, first input terminals [d.sub.1 . . . d.sub.n ] receiving the data signals, and second input terminals connected with corresponding D stages of the running matrix inverse (R.sub.ij, where j=1 through n, i=1 through n);

(2) a plurality of mod 2 adders connected with the output terminals of a plurality of said AND gates, respectively, thereby to provide a plurality of phase vector estimates, respectively;

(3) means for smoothing the individual components of the phase vector; and

(4) threshold means for deciding polarity of the individual phase vector components.

4. Apparatus as defined in claim 3, wherein said smoothing means comprises an up/down counter.

5. Apparatus as defined in claim 3, wherein said smoothing means comprises an up/down accumulator, and zero counter means for determining the amount by which the up/down accumulator is incremented or decremented.

6. Apparatus as defined in claim 1, wherein said resident PN generator means (110) includes a shift register (4), and recursion means connected with said shift register for producing the next bit depending on the n prior bits, said recursion means having a plurality of known coefficients of recursion (X.sub.1 . . . X.sub.n-1); and further wherein said running matrix inverse means includes a plurality of columns i (where i=1 . . . m) each including

(1) a plurality of D stage registers (14);

(2) a plurality of mod 2 adders (12) connected between said registers, respectively;

(3) a plurality of AND gates (10) having outputs connected with said mod 2 adders, respectively, each of said AND gates having a pair of input terminals;

(4) means for applying said known coefficients of recursion (X.sub.1 . . . X.sub.n-1) to one input terminal of said AND gates, respectively;

(5) means for applying to the other input terminal of each of said AND gates a feedback signal provided by a connection between the output of the last D stage and the input of the first D stage of said column; and

(6) means for loading in parallel to the D stages of each column, respectively, second signals (Y.sub.li . . . Y.sub.ni) that are known a' priori functions of said coefficients of recursion, thereby loading the initial inverse (R.sub.o.sup.-1).

7. Apparatus as defined in claim 6, wherein the initial inverse matrix has the form ##EQU61##

8. Apparatus as defined in claim 1, wherein said resident PN generator means includes

(1) a plurality of D stage registers (314);

(2) a plurality of mod 2 adders (312) connected between said registers, respectively;

(3) a plurality of AND gates (310) having outputs connected with said mod 2 adders, respectively, each of said AND gates having a pair of input terminals;

(4) means for applying said known coefficients of recursion (X.sub.1 . . . X.sub.n-1) to one input terminal of said AND gates, respectively; and

(5) means for applying to the other input terminal of each of said AND gates a feedback signal provided by a connection between the output of the last D stage and the input of the first D stage of said column;

and further wherein said running matrix inverse means includes a plurality of columns i (where i=1 . . . m) each including

(1) a shift register (304), and recursion means connected with said shift register for producing the next bit depending on the n prior bits, said recursion means having a plurality of known coefficients of recursion (X.sub.1 . . . X.sub.n-1); and

(2) means for loading in parallel to the D stages of each column, respectively, second signals (Y.sub.1i . . . Y.sub.ni) that are known a' priori functions of said coefficients of recursion, thereby loading the initial inverse (R.sub.o.sup.-1).

9. Apparatus as defined in claim 1, wherein said running matrix inverse means (112) includes a plurality of rows i (where i=1 . . . m), each of said rows including

(1) a plurality of D stage registers (404);

(2) a plurality of mod 2 adders (412) connected between said registers, respectively;

(3) a plurality of AND gates (410) having outputs connected with said mod 2 adders, respectively, each of said AND gates having a pair of input terminals;

(4) means for applying said known coefficients of recursion (X.sub.1 . . . X.sub.n-1) to one input terminal of said AND gates, respectively;

(5) means for applying to the other input terminal of each of said AND gates a feedback signal providing by a connection between the output of the last D stage and the input of the first D stage of said row; and

(6) means for loading in parallel to the D stages of each row, respectively, second signals (Y.sub.i1 . . . Y.sub.in) that are known a' priori functions of said coefficients of recursion, thereby loading the initial inverse (R.sub.o.sup.-1).

10. Apparatus as defined in claim 5, wherein said zero counter means is operable to count also the number and weight of soft decisions which are used in each matrix vector dot product, thereby to obtain a more accurate up-date of the accumulation.

11. The method for synchronizing the linear PN sequences contained in the heavy noise background of a received data-carrying spread spectrum signal, comprising the steps of

(a) demodulating the received signal to separate therefrom the noisy widebank PN spread spectrum component and to generate a chip rate clock signal;

(b) producing by resident PN generator means in response to the chip rate signal a replica of the PN sequence with arbitrary phase;

(c) obtaining the running matrix inverse (R.sub.o.sup.-1) of the matrix (R) that is formed by n successive observations of the shift register of the resident PN generator means;

(d) multiplying the running inverse by a column vector of noisy chips, thereby to obtain a plurality of estimates of the phase vector;

(e) smoothing and averaging the phase vector estimates to produce the smoothed phase vector (c.sub.j);

(f) producing from the smoothed phase vector and the contents of the resident generator shift register a properly phased PN sequence; and

(g) combining the noisy chips with the properly phased PN sequence, thereby to permit recovery of the narrowband digital data carried by the spread spectrum signal.

12. The method as defined in claim 11, and further including the step of delaying the phase of the smoothed averaged phase vector for use in range computation.

13. The method as defined in claim 12, and further including the step of combining phase-advanced adn phase-retarded versions of the properly phased PN sequence to produce a combined control signal (V.sub.1 -V.sub.2) for synchronizing the chip rate clock.

Description Submit all comments and votes

BRIEF DESCRIPTION OF THE PRIOR ART

Spread spectrum communication systems are well known in the prior art, as described, for example, in the treatise Spread Spectrum Systems, by Robert C. Dixon, John Wiley & Sons, Inc., New York, N.Y., 1976. Literally, a spread spectrum system is one in which the transmitted signal is spread over a frequency band wider than the minimum bandwidth required to transmit the information being sent. Thus, a baseband signal (i.e., a voice channel) with a bandwidth of only a few kiloHertz may be distributed over a band that may be many megaHertz wide. This is accomplished by modulating with the information to be sent and with a wideband encoding signal.

Code synchronization is required in all spread spectrum systems, since the code is the key to despreading desired information and to spreading any undesired signals.

In a variety of communications and ranging systems a linear pseudo noise sequence is used. These sequences are valuable for spreading the bandwidth and for providing timing signals for ranging. Spreading is usually done in order to combat intentional or unintentional narrowband jamming. Once the receiver has synchronized to the sequence, the signal may be despread and the data demodulated with attendant processing gain.

In the past, the receiver was forced to slew the clock for a linear PN sequence to line up the receiver generator with the transmitted sequence. For long sequences or sequences received in heavy noise (i.e., noise power density which is of the order of, or exceeds the energy per chip), such typical methods as "the sliding correlation" are impractical because of the large number of phases which must be tested with attendant dwell time required in heavy noise.

SUMMARY OF THE INVENTION

The present invention was developed to avoid the above and other drawbacks of the known synchronizing systems, and for synchronizing a linear PN sequence directly without slewing a generator and correlating. The system is algebraic and has been proven to work even if the received noise is larger than 40 db greater than the signal.

In accordance with a primary object of the invention, the system includes demodulator means for separating from the received signal the noisy wideband PN spread spectrum component, and for generating a chip clock rate signal, resident PN generator means responsive to the chip rate clock signal for producing a replica of the PN sequence with arbitrary phase, running matrix inverse means for obtaining the inverse of the matrix (R) formed by n successive observations of the register (4) of the resident generator, matrix vector product means for multiplying the running inverse by a column vector of noisy chips, thereby to obtain a plurality of estimates of the phase vector, means for smoothing and averaging the phase vector estimates, thereby to produce the smoothed phase vector (c.sub.j), dot product means responsive to the smooth phase vector and to the contents of the resident shift generator for producing the properly phased PN sequence, and despreading means for combining the noisy chips with the properly phased PN sequence, whereby the narrowband digital data carried by the spread spectrum signal may be recovered.

According to one embodiment of the invention, the running matrix means includes a plurality of columns i (where i=1 . . . n) each including a plurality of D stage registers, a plurality of mod 2 adders connected between the registers, respectively, a plurality of AND gates having outputs connected with the mod 2 adders, respectively, each of the AND gates having a pair of input terminals, means for applying the known coefficients of recursion (X . . . X.sub.n-1) of the resident PN generator to one input terminal of the AND gates, respectively, means for applying to the other input terminal of each AND gate a feedback signal provided by a connection between the output of the bottom D stage and the input of the top D stage of the column, and means for loading in parallel to the D stages of each column, respectively, second signals (Y.sub.1i . . . Y.sub.n-1) that are known a' priori functions of the coefficients of recursion thereby loading the initial running matrix inverse (R.sub.o.sup.-1). This initial running matrix inverse has the form: ##EQU1##

In a second embodiment of the invention, the running matrix inverse means includes a plurality of rows each including a plurality of D stage registers, a plurality of mod 2 adders connected between the registers, respectively, a plurality of AND gates having outputs connected with the mod 2 adders, respectively, each of said AND gates having a pair of input terminals, means for applying the known coefficients of recursion (X.sub.1 . . . X.sub.n-1) to one input terminal of the AND gates, respectively, means for applying to the other input terminal of each of said AND gates a feedback signal provided by a connection between the output of the last D stage and the input of the first D stage of the row, and means for loading in parallel to the D stages of each row, respectively, second signals (Y.sub.i1 . . . Y.sub.in) that are known a' priori functions of the coefficients of recursion, thereby loading the initial inverse (R.sub.o.sup.-1).

According to a further object of the invention, phase delay computer means are provided for converting the smoothed phase vector [c.sub.j ] to actual phase delay, thereby affording means for range computation.

According to another object of the invention, the matrix vector product means includes a plurality of AND gates having first inputs to which are applied the data signals [d.sub.1 . . . d.sub.n ], and second input terminals connected with corresponding D stages of the running matrix inverse. A plurality of mod 2 adders are connected with the output terminals of a plurality of the AND gates, respectively, thereby providing a plurality of phase vector estimates that are smoothed for transmission to threshold means which determine the polarity of the individual phase vector components. In one embodiment, the smoothing means comprises an up/down counter, while in another embodiment, the soothing means comprises an up/down accumulator in combination with a zero counter that determines the amount by which the up/down accumulator is incremented or decremented.

In accordance with another feature, the invention can be incorporated into a phase delay-lock loop system of the type wherein two reference signals are generated for comparison with a single incoming signal in two separate correlators. The summed correlator outputs are filtered and are used to control the operation of a voltage controlled oscillator that produces the chip rate clock signal.

In a further modification, the resident PN generator means includes a plurality of D stage registers, a plurality of mod 2 adders connected between the registers, respectively, a plurality of AND gates (310) having outputs connected with the mod 2 adders, respectively, each of the AND gates having a pair of input terminals, means for applying the known coefficients of recursion (X.sub.1 . . . X.sub.n) to one input terminal of the AND gates, respectively, and means for applying to the other input terminal of each of said AND gates a feedback signal provided by a connection between the output of the last D stage and the input of the first D stage of the column. The running matrix inversion means, in this embodiment, includes a plurality of columns each including a shift register, and recursion means connected with the shift register for producing the next bit depending on the n prior bits, the recursion means having a plurality of known coefficients of recursion (X.sub.1 . . . X.sub.n-1), and means for loading in parallel to the D stages of each column, respectively, second signals (Y.sub.1i . . . Y.sub.ni) that are known a' priori functions of the coefficients of recursion, thereby loading the initial inverse (R.sub.o.sup.-1).

BRIEF DESCRIPTION OF THE FIGURES

Other objects and advantages of the invention will become apparent from a study of the following specification, when viewed in the light of the accompanying drawings, in which:

FIG. 1 is a schematic diagram of a spread spectrum system including the PN synchronizer of the present invention.

FIG. 2 is a schematic diagram illustrating the apparatus for starting the generator with arbitrary phase and for obtaining correct phase by mod 2 summing certain bits in the shift register of the generator.

FIG. 3 is a schematic diagram of one column of a multi-column matrix inversion means.

FIG. 4 is a diagrammatic illustration of a particular state of operation of the apparatus of FIG. 2.

FIGS. 5 and 6 are block diagrams illustrating the manner extracting tap weights to generate proper phase, and the refined averaging method for tap weights, respectively.

FIG. 7 is a graphic representation comparing acquisition times as a function of generator register length n and SNR converted via Gaussian densities to raw bit error probability p.

FIG. 8 is a modification of the apparatus of FIG. 2.

FIG. 9 is a circuit diagram illustrating another embodiment of the invention for synchronizing the PN sequence in a phase locked loop, and FIG. 10 illustrates the voltage signals sketched as a function of chip clock phase.

FIG. 10 illustrates a modification of the apparatus of FIG. 2.

FIG. 11 is a diagrammatic illustration of another embodiment of the resident PN generator means of FIG. 1, and FIG. 12 illustrates a corresponding modification of the running inverse means.

FIG. 13 is a diagrammatic illustration of the structure of the row weight enumerator of the system of FIGS. 11 and 12.

FIG. 14 is a diagrammatic illustration of another modification of the resident PN generator means.

FIGS. 15 and 16 are diagrammatic illustrations of the system for utilizing soft decisions on the noisy chips.

DETAILED DESCRIPTION

As a glossary for use by the reader, in the following specification, certain terms have been used which have well-known meanings in the art, as follows:

"chips"--1's and 0's which have characteristics of randomness and are drawn from a linear PN sequence, generated at many times the data rate, and are Mod 2 added to the data to create the wideband spread spectrum signal;

"noisy chips"--chips contaminated with background noise, resulting in errors;

"noisy wideband"--chips generated at a rate higher than the data rate, and contaminated with noise, causing them to be received with errors; and

"heavy noise"--noise power density which is on the order of, or exceeds the energy per chip.

Referring first more particularly to FIG. 1, the spread spectrum transmitter 100 includes a source of narrow band digital data upon which the pseudo noise (PN) sequence is added by the MOD 2 ADDER 102, thereby to produce wideband digital data, as is known in the art. This spread spectrum base band data is then modulated with the carrier signal by modulator 104 in a known manner, such as amplitude modulation, phase modulator or frequency modulation.

At the receiver, the transmitted signal is fed to the demodulator and chip rate clock extractor 106 which produces a wideband chip output that is fed to one input terminal of the MOD 2 ADDER 108. The chip rate clock signal 109 is supplied to a resident PN generator 110 having outputs connected with the running matrix inverse 112 and with the dot product matrix 114, respectively. The output of the running matrix inverse 112 applied to one input of the matrix product 118 the other input of which is supplied via conduit 120 with a portion of the noisy chips produced by the demodulator and chip rate clock extractor 106.

The matrix product 118 produces noisy phase vector estimates that are supplied to the smoother/averager 122 to produce the smoothed phase vector c.sub.j that is supplied to the dot product device 114.

More particularly, the resident generator 110 runs synchronously with the incoming noise sequence at any arbitrary phase of the possible 2.sup.n -1 phases. Any other phase can be constructed by taking a mod 2 sum of the states of the shift register generator of the resident PN generator 110. The problem is to compute which mod 2 sums of the register to take. To this end, the running inverse of the matrix of the successive observations of the shift register of the resident generator is computed, whereupon a matrix product is formed of the inverse with a vector of incoming noisy chips. The resulting phase vector estimate is smoothed to obtain [c.sub.j ]. A dot product of the resident register with [c.sub.j ] then transforms the resident register into a noise free version of the incoming PN sequence with the proper phase.

(1) The Resident Generator (FIG. 2)

Referring now to FIG. 2, in order to find the phase of a linear PN sequence when received in heavy noise, any phase of a linear PN sequence is made by taking a mod 2 sum by adder 2 of some of the bits in the resident generator shift register 4. More particulary, there is a one-to-one correspondence between any of the 2.sup.n -1 phases and one of the non-trivial mod 2 sums of n bits of the generator register. Therefore, the problem of finding the correct phase corresponds to finding which mod 2 sum to take of the n bit shift register. The clock 109 is not slewed, but rather is kept in lock condition.

FIG. 2 illustrates the manner of starting the generator off with arbitrary phase and still obtaining the correct phase by mod 2 summing certain bits in the shift register of the generator. The problem is to determine which switch closures [c.sub.j ] to make to get the correct phase. The switch closures are usually implemented with logical AND gates. The set of inputs that determine the switch closures is called a phase vector.

For a given noisy received sequence [d], an estimate of the proper phase vector on the register [c.sub.j ] is obtained by solving the system of equations

R[c]=[d] (1)

A separate estimate is obtained every chip time, which estimates are averaged to obtain the correct estimate. Because R is known at all times, and can be shown to be invertable, [c] can be obtained as follows:

[c]=R.sup.-1 [d] (2)

R is in principle obtained by n successive observations of the resident shift register 4 of FIG. 2.

(2) The Running Inverse (FIG. 3)

In accordance with a characterizing feature of the present invention, a fast running matrix inverse is provided having columns implemented as shown in FIG. 3. This structure avoids the otherwise enormous amount of computation which would be required every chip time for matrix inversion. More particularly, the coefficients [X] in the recursion equation of the circuit of FIG. 2 are applied to one leg of the AND gates 10, respectively, of the column of FIG. 3. The outputs of these AND gates are applied to the inputs of the MOD 2 ADDERS 12 that are connected between the shift register D stages 14. The output from the last D stage is connected with the input to the first D stage unit and to the other legs of the AND gates 10, respectively. The Y inputs are supplied to initially load the D stages, respectively. They are generally different for each column and are described below for various embodiments of the invention.

This may be mathematically explained, as follows:

The original equations for solving c can be written for any time q:

R.sub.o S.sup.q [c]=[d] (3)

where [d] is the time varying input noisy chips of the PN sequence and R.sub.o is some initial matrix obtained by observing the generator register the first n successive times. (There is a convenient time to make this initial set-up for R.sub.o which will be discussed below).

The right shifting matrix S of equation (3) is simple and takes the form ##EQU2## Solving (3) for the tap weights we have

[c]=[S.sup.-1 ].sup.q R.sub.o.sup.-1 [d] (5)

Where S.sup.-1 is equally simple and is given by ##EQU3## Thus, the matrix S.sup.-1 is a row operation whose columns are implemented as shift register depicted in FIG. 3 and as described above.

(3) Z Generation (FIG. 4)

A second discovery is the fact that the initial R.sub.o.sup.-1 loading of the stages in FIG. 3 can be facilitated by observing certain states of the resident generator register. It turns out that if either the 0000 . . . 01 state or 1000 . . . 00 state is decoded, the initial inverse matrix is a trivial function of the coefficients [X.sub.j ] in the generator polynomial. Consider first the matrix equation for the tap weights c. Thus, ##EQU4## or, succinctly:

[R.sub.o ].times.[c]=[d] (7b)

Where the arrow indicates direction of movement of data with time. The matrix on the LHS is lower triangular with constant diagonals. As such, it has a simple inverse.

This matrix has an inverse which is also lower triangular with constant diagonals. ##EQU5## The matrices in (7) and (8) will be inverses if and only if

Z.sub.1 =X.sub.1

Z.sub.2 =X.sub.2 +X.sub.1 Z.sub.1 =X.sub.1 +X.sub.2 (9)

Z.sub.3 =X.sub.3 +X.sub.2 Z.sub.1 +X.sub.1 Z.sub.2

or in general ##EQU6##

This is derived by forming row reductions on (8) and can be easily verified. The shift register generator of FIG. 4 illustrates how the Zs are formed, which shift register corresponds with that of FIG. 2.

Thus: ##EQU7## and the X.sub.j is used to load R.sub.o.sup.-1 exactly n-1 bit delays after decoding the 1000 . . . 0 state. It is somewhat easier to use the 000 . . . 01 state. Then the inverse is upper triangular and takes the form: ##EQU8##

This is equally easy to verify. This R.sub.o.sup.-1 is loaded immediately after decoding the 0000 . . . 01 state. Equation (11) is an example of the set of Y's that is loaded into the D stages 14 of FIG. 3.

(4) The Matrix Product and Smoother Averager (FIGS. 5-7)

After obtaining the running inverse, the matrix produces noisy estimates which are smoothed to obtain good estimates of the tap weights [c.sub.i ] as illustrated in FIG. 5. A refinement which takes into account the accuracy of each individual estimate is depicted in FIG. 6.

The reasoning behind this refinement is described next.

As indicated above, the present invention performs an inverse of a binary matrix, and updates this inverse R.sub.n.sup.-1 at the chip rate. The "tap weights" [c] which are used to form the phase shifted sequence were then estimated every chip time by forming the matrix vector product

[c]=R.sub.n.sup.-1 [d], (12)

where the data [d] is noisy. In the originally proposed system of FIG. 4, the separate estimates of the tap weights [c] were averaged together by means of up/down counters. The time varying accuracy of each estimate was not taken into account. It has been proven that a very good estimate of the accuracy is available by just counting the number of "ones" or "zeroes" which are in any row of R.sub.n.sup.-1. Ideally, the accumulators which are combining the extimates of the tap c.sub.j should contain a number .lambda..sub.j proportional to the log liklihood ratio: ##EQU9## where these probabilities are conditioned on all observations. Now, since all the estimates are independent every chip time, the log likelihood ratios add. To see the weighting as a function of the number of ones, q (in say, the j.sup.th row of R.sub.n.sup.-1 at any chip time), one needs only to compute the probability of correctly adding mod 2, q noisy data bits. Let p be the raw data bit error rate, then the addition will be correct if no errors are made, or an even number of errors. The probability of correct computations P.sub.1 is easily proved to be: ##EQU10## and the probability of error is: ##EQU11## the log likelihood ratio for this observation: ##EQU12## The approximation on the RHS of (16) is valid for small 1-2p or for heavy noise.

This says the decrement or increment of the j.sup.th accumulator should decay exponentially with the number of ones in the j.sup.th row of the inverse matrix. Now to compute the advantage of the system of FIG. 5 against the old, the following information-theoretic argument is used.

Assume that the operations on the noisy data can be regarded as communications channel. At each chip time, transinformation is obtained about the taps [c.sub.j ]. As a good approximation to acquisition time in bits, the reciprocal of the average transinformation obtained per chip can be used.

The classic formula for transinformation reads:

I=1+P.sub.1 log.sub.2 P.sub.1 +(1-P.sub.1) log.sub.2 (1-P.sub.1)

where P.sub.1 is the probability of correct computations. We are going to be dealing with heavy noise so let

P.sub.1 =(1+.delta.)/2

for small .delta. and substitute into (17) to get

I=1+(1+.delta./2) log .sub.2 (1+.delta./2)+(1-.delta./2) log .sub.2 (1-.delta./2) (19)

Now using log.sub.2 (1+.delta.)=.delta./ln 2 we obtain ##EQU13## For the system of FIG. 5, .delta.=(1-2p).sup.q where q is the number of terms required to add to get the estimate of c.sub.j. Substituting this expression in (21), there is obtained:

I(g)=(1-2p).sup.2q /ln 2 (22)

But q of n bits in the inverse matrix is binomially distributed with the all zeroes case excluded. Therefore, one can write: ##EQU14## for the average transinformation in the new system. 1/H is the estimated acquisition time. For the prior system, an average probability P.sub.1 of error for transinformation is used since the computations were not weighted according to their probability of being correct. To calculate P.sub.1, one needs only to convolve P.sub.1 of equation (14) with the modified binomial distribution to get: ##EQU15## and using equation (21) and noting that .delta..sup.2 =(1/2-P.sub.1).sup.2 the transformation is approximately: ##EQU16##

A comparison of acquisition times as a function of n and SNR converted via Gaussian densities to raw bit error probability p is plotted in FIG. 7.

(5) Factorable Generators

Another concern in determining the phase of noisy PN sequences is what to do about factorable generators such as the Gold Code and the 1+x.sup.2 factor of ambiguously detected QPSK.

At first it was believed that one could use the ordinary system and ignore the fact that the generator polynomials are factorable, but such is not the case.

For example, assume that the PN sequence is received through a QPSK demodulator. The following four possible effects results:

(1) every bit can be received unaltered;

(2) every other bit can be inverted;

(3) every other bit can be inverted in opposite phase to (2); and

(4) all bits can be inverted.

If the original sequence S(x) satisfies the recursion equation

S(x)P.sub.n (x)=0 mod x.sup.2.spsp.n -1 (26)

then any of the ambiguously received sequences S* will satisfy

S*(x)(1+x.sup.2)P.sub.n (x)=0 mod x.sup.2.spsp.n -1 (27)

This fact can be seen since the sum of the individual sequences which satisfy (26) also satisfy (26) and

S(x)P.sub.n (x)=0 (28)

while the sequences ##EQU17## are all zero factors of 1-x.sup.2.

If one were to blindly multiply the (1+x.sup.2)P.sub.n (x) in equation (27) and attempt to use the simplest of the invention to solve for the "phase vector", not every sequence could be derived from mod 2 sums of delayed versions of any other sequences. Instead, we have to adjoin two systems together (one for each factor). The Gold Codes and the generalizations thereof are also formed by summing a few independent linear PN sequences. Consequently, the generator polynomial can be expressed as a product of irreducable* (usually also primitive) polynomials.

*If factors are repeated such as 1+X.sup.2 =(1+X) (1+X) they must be treated as a single factor

For concreteness, consider the generating polys as being composed of two factors (P.sub.A (x) and P.sub.B (x)). The free running shift register at the receiver will now be replaced by two separate registers whose lengths are equal to the degrees of P.sub.A and P.sub.B. It is linear sums of both register outputs (mod 2) that will reproduce any phase of the composite sequence. The matrix equations are partitions in the form: ##EQU18## where A and B represent successive entries in the shift registers which implement P.sub.Z and P.sub.B just as in applicant's prior development.

A* and B* represent entries in the registers which are observed after further shifting operations. The matrix on the left hand side of equation (30) is partioned in such a manner that A is square and B* is square. Remember than at any time, applicant's matrix equation could be described by just multiplying by a very simple column operator shift matrix. This situation is stil true. For all time k: ##EQU19## where the S.sub.A and S.sub.B are exactly as before and take the form: ##EQU20## the inverses are the same as before and are uncoupled row operations ##EQU21## Consequently, the inverse can be implemented almost identically as in applicant's prior system except the initial value is coupled and must be computed off line. For this system, a variable length "column" shift register in the inverse must be constructed where length is equal to the degree of the factors.

To find the initial inverses equations like ##EQU22## are solved for W, X, Y, and Z.

For example, consider the two equations for W and Y

AW+BY=I (35)

A*W+B*Y=O (36)

Since both A and B* have inverses, their equations, can be solved by substituting (36) into (35):

AW-BB*.sup.-1 A*W=I (37)

or

W=(A=BB*.sup.-1 A*).sup.-1 (38)

and

Y=-B*.sup.-1 A*(A-BB*.sup.-1 A*).sup.-1 (39)

(6) Extraction of PN Sequence with Data Modulation (FIG. 8)

In accordance with another important feature of the invention, with regard to the extractor of the PN sequence with data modulation, in the prior art it was known to remove the modulation by adding successive bits, which has the drawback that the addition mod 2 has a penalty in noise, together with the nuisance of finding the multiplicative inverse of (1+X) to recreate the correct phase of the PN sequence. This inverse is required to undo the operation of successive addition.

For this special case, the initial loading of the inverse matrix is given in closed form.

If a PN sequence S(X) satisfies S(X)P(X)=0 mod X.sup.2n -1 then the sequence S(X) or its complement S(X) satisfies S(X)(1+X)P(X)=0 mod X.sup.2n -1.

Since the sequence Q(X)=1 1 1 1 1 1 satisfies Q(X) (1+X)=0:

(1+X)P(X){Q(X)+S(X)}=(1+X)P(X)S(X) (40)

The distributive law still holds in polynomial rings.

While it may appear necessary to add the incoming data bits first, such is not the case, since the sequence is reconstituted without the operator (1+X) and stripped of the modulation.

The phase vector for the data modulated sequence is used exactly in the same way as the ordinary system.

The overall polynomial factors into P(X) (1+X). Recall that the free running generators are segmented into separate generators for each factor, linear sums of the generator registers are taken to form the reconstituted sequence.

The generator for P(X) has the same Structure as the generator for the original sequence. The generator for (1+X) is the simple constant "1". It is not surprising then that any phase of the true or the complement can be constructed as depicted in FIG. 8. However, since it is not desired to reconstitute the complement sequence, the constant output is never used in the sum. It is clear that if closing the switch of the constant would create the complement sequence with the proper phase, the same tap weights without the constant would create the same phase of the true sequence.

Even though the constant's output is not used to form the proper phase, to solve for the tap weights [c.sub.i ] it is necessary to solve a system of equations with one more dimension.

The system of equations can b partioned in the following matrix: ##EQU23## R is the square matrix of shift register entries of the free running shift register. r.sup.T is the vector of shift register entries which occur one shift after the bottom row of R. c.sub.1 through c.sub.n are the tap weights on the main register. c.sub.n+1 is the tap weight (unused) for the constant te