DETAILED PROGRESS REPORT

SYSTEM OVERVIEW

The following system overview is reprinted for reference and for those new to this technology.

Our communication and position location technology is based on the transmission of coded sequences of Gaussian impulses, and selective reception using correlation. The transmitted signal is generated by applying current steps through a Large-Current Radiator antenna. An impulse is launched when the current is turned on or is turned off. The code sequences are pseudo-random codes like those used for direct-sequence spread spectrum systems such as GPS. Different sequences provide separate channels roughly equivalent to frequency bands. Correlation is used to discriminate a particular code sequence from other signals, both nonsinusoidal and sinewave frequency-based. For communication, the simplest modulation of code sequences is "antipodal" modulation: either a given code sequence or its inverse is sent to represent one bit of information.

The basic principle Localizers use for position location is cooperative ranging. Localizers cooperate in pairs to determine their separation, and five or more Localizers share information to determine the 3-dimensional relative location of each. The distance between two Localizers is determined by measuring the round-trip transit time for a signal and multiplying by the speed of light.

Other localization systems give absolute position on the geoid (i.e. GPS), location relative to fixed beacons (e.g. LORAN), or location relative to a starting point (i.e. inertial platforms). For a host of applications, what is really desired is location within a building or an area, or location relative to other people or objects, whether moving or stationary. Most localization systems allow autonomous position location, yet this information must be communicated by a separate mechanism in order to be shared. Knowing one's latitude and longitude is useless without additional information such as a map.

ULTRA-WIDEBAND / NONSINUSOIDAL SIGNALS 

Using the transit time of a signal to gauge distance requires an accurate measurement of the arrival time of the signal. The more sharply defined a signal is in time, the more spread out the signal is in the frequency domain. This is true for nonsinusoidal impulses as well as for the pulse-modulated sinewaves used in conventional radar. In either case, to measure distance to centimeter-level accuracy requires approximately 1 GHz of bandwidth (or more). The difference is that most of the energy of a nonsinusoidal 1 ns wide Gaussian impulse is spread over frequencies below 1 GHz (Fig. 4), whereas pulse-modulated sinewaves require a carrier frequency of at least 30-60 GHz to get this bandwidth. Expensive microwave (GaAs MMIC) technology is needed for sinusoidal transmission at a carrier frequency where it is possible to have sufficient bandwidth. Nonsinusoidal impulses are baseband signals, which means there is no carrier frequency.

The development of the ultra-wideband Large-Current Radiator (LCR) antenna by Dr. Henning Harmuth has made it possible to radiate nanosecond wide impulses with inexpensive CMOS chips. The LCR is a current-mode antenna which radiates outwards from the surface of a flat square conductor. The only restriction on its size is that it cannot be made larger than the equivalent width of the impulse being transmitted.

Applying a step change in the current through an LCR causes an impulse to be radiated, since radiation power launched is proportional to the square of the derivative of current flow. The impulse is narrower and has more radiated power when the current can be changed more quickly. The polarity of the impulse is determined by the sign of the derivative of current. Thus, turning off the current through an LCR generates an impulse which has the opposite polarity of the impulse generated when the current is turned on.

FIGURE 4. A Gaussian impulse of width d and its amplitude spectrum. Note that if d = 1 ns, most of the energy in the frequency domain is below 1/d = 1 GHz.

CODING

A coded sequence of Gaussian impulses means a series of electromagnetic impulses, each with the electric field vector pointing in one of two opposite directions. Correlators are used by Localizers to extract the signal from noise, even when the signal amplitude is less than the noise amplitude. The output of a correlator is a function of the relative shift between two signals. When the shift of the input signal matches that of the reference code, a correlation peak is produced. A signal spread out in time can thus be time-compressed to the resolution of a single impulse.

Ideally, codes should be chosen so that the correlation of a code sequence against itself will have a single peak, making it easy to determine when the proper sequence has arrived. Maximal Sequence codes and Complementary codes approach this ideal. The cross-correlation of one code sequence with a different sequence should not have correlation peaks in order for multiple Localizers to operate at the same time. Fortunately, families of codes exist with tens of thousands of members that have both good autocorrelation and good cross-correlation properties.

DOUBLETS

A series of impulses can be launched by stepping the current through the transmit antenna up or down. Unfortunately, consecutive impulses of the same polarity require stepping the antenna current higher and higher. Launching an arbitrary sequence of impulses can be very power consumptive, because the running difference in the number of positive and negative impulses determines the "DC" current, and this can become very large with almost all codes. The minimum total current occurs when, starting from zero current, a negative impulse immediately follows a positive impulse, and vice versa. We refer to such pairs of impulses as "doublets" (Fig. 5). Doublets can be generated from a single supply by using switching circuits to control the direction of current flow through the transmit antenna.

FIGURE 5. A "doublet" with impulse separation t0 and its amplitude spectrum. For t0 = 5 ns, the nulls are spaced 200 MHz apart with a null at 0 Hz (i.e. DC).
We have discovered that doublets can be used in a manner that both obviates the apparent restriction on having arbitrary code sequences, and that can be easily detected. For each bit in any code sequence, we generate a doublet which starts with either a positive impulse or a negative impulse. An example is shown in Figure 6. (In spread spectrum terminology, a doublet is our "chip".) If the autocorrelation of a sequence of impulses has a single correlation peak, then the autocorrelation of the same sequence encoded using doublets has a central peak bracketed by two negative peaks (Fig. 10). As discussed later, this complex pattern is much easier to recognize than a single peak, especially when the signal is contaminated with considerable noise.

An additional advantage of using doublet-encoded sequences is that the choices of the time separation between impulses in a doublet and the time separation between doublets allows the frequency spectrum to be manipulated (Fig. 5). For instance, nulls can often be placed at frequencies which harbor high intensity narrowband interference.

FIGURE 6. The 15-bit Maximal Sequence "100011011010111" encoded using doublets. Here the impulses are 1 ns wide and separated by 5 ns. Thus, most of the energy is below 1 GHz, with nulls every 200 MHz.

TIME-INTEGRATING CORRELATOR

The usual method for implementing correlators "slides" the analog input signal past the reference code sequence. The input signal is delayed, and taps weighted (+1, Ø, -1) by the reference code sequence are taken at successive delay stages. This Sliding Correlator (or matched filter) topology requires some sort of memory for the input signal. This may take the form of digital memory for the output of an analog-to-digital converter or a tapped delay line. Delay lines may be discrete, such as charge coupled devices (CCD's), or analog. Analog delay may take the form of coax, optical fiber, glass rods, surface acoustic wave (SAW) devices, all-pass filters, etc. All of these are unsuited for our purposes. ADC's and CCD's are too slow, and CCD's are also too power consumptive, SAW's have limited programmability, and active delays such as all-pass filters cannot handle long codes. The rest cannot be inexpensively integrated.

We have chosen to use the dual form of the usual Sliding Correlator implementation, known as a Time-Integrating Correlator (TIC). The reference code sequence is shifted past the changing analog input signal and the product of the code and signal is summed in a set of analog integrators (Fig. 7). The output of each integrator represents a different alignment ("phase") between the reference code sequence and the input signal (Fig. 8). The outputs of the TIC correspond nearly to the sampled output of a Sliding Correlator as a function of time.

The chief advantage of a TIC is that all of the difficulties of achieving precise and distortionless analog delay are replaced by the simple task of delaying a digital code sequence. The only limitations on the length of the code sequence are the stability of the timebase and the quality of the integrators. In fact, code sequences a million long have been used for satellite ranging. The disadvantage of a TIC is that a separate integrator is needed for what represents one sample of the output of a Sliding Correlator.

FIGURE 7. This diagram illustrates the operation of a Time-Integrating Correlator. The top row shows the received code sequence "110" encoded using impulse doublets. The second row shows the accumulation of charge in the nth integrator. The third row represents the +1/-1 values of the reference code sequence. The fourth row shows the overlap of the integration periods of the nth integrator with the (n+1)th integrator.
FIGURE 8. This diagram illustrates how the outputs of 17 integrator phases are generated by different alignments of the reference code i(t) with the received signal e(t). In this example, the integration period equals the impulse period, and adjacent integrator phases are overlapped by half of the impulse period.


With multiple integrators, a Time-Integrating Correlator (TIC) captures only a fraction of what would be the output of a Sliding Correlator. A continuously-operating Sliding Correlator can detect the arrival of a code sequence on the fly. A TIC needs to know roughly when to look, so as to position its window of integrator phases. Acquiring this knowledge is known as synchronization. The process can take time, but once synchronization is achieved, a TIC consumes much less power than a Sliding Correlator. Synchronization can be maintained by scheduling communication exchanges frequently enough to compensate for any drift in the relative clock rates among a group of Localizers.

 

DETECTION


A key feature of a Time-Integrating Correlator is that the process of detecting a correlation peak does not have to be done in real time. The correlation results are saved in the outputs of the integrator phases, which we then digitize. The complex TIC patterns that result can subsequently be analyzed with a microprocessor over a substantial period of time. This allows sophisticated recognition processes to be used such as neural nets and maximum entropy.

 

TIME DOMAIN FILTERING

For receiving a nonsinusoidal signal, a Time-Integrating Correlator integrates the product of the code and received signal over a period which is less than or equal to the separation of the transmitted impulses. The width of the integration period can be chosen for different purposes. When the integration period is as wide as the separation between impulses, the received impulses cannot fall outside the integration period for any integrator phase. If the integrator phases are also non-overlapping, then the set of integrator phases spans the largest time window, which is best for synchronization. When the integration period is reduced, the signal-to-noise ratio is improved, because less noise is integrated where there is no signal (Fig. 9).

Thus, this time domain filtering can be used, when the position of the received impulses is known quite accurately, to "mask out" noise where no signal is present. This works to increase signal-to-noise ratio until the integration window is approximately the size of the impulses and is straddling them.

FIGURE 9. This diagram illustrates the operation of a Time-Integrating Correlator (TIC) where the integration period is half of the impulse period. The top row shows the received signal with noise. The second row shows the accumulation of charge in the nth integrator. The third row represents the +1/0/-1 values of the reference code sequence. The fourth row shows the reference code sequence for the (n+1)th integrator. Note how the input signal is effectively masked out when the reference is zero, with no loss in the signal contribution.



 
 

COMPLEX TIC PATTERNS FOR HIGH-SENSITIVITY TIME MEASUREMENTS

The pattern formed by the output phases of the Time-Integrating Correlator can be made very sensitive to slight shifts in the alignment of the received signal versus the reference code. This is achieved when the integration period for the TIC is as wide as the impulse period and the adjacent phases overlap by one half of the impulse period, as shown in Figure 7. This figure also illustrates the fact that the TIC performs the cross-correlation of two related but different signals the received signal, consisting of Gaussian impulses, and the reference code which has a rectangular pulse for each impulse in the received signal. The continuous time cross-correlation of these two signals is shown as the trace labeled (t) in the left-hand column of Figure 10. The outputs of the TIC are shown as the trace labeled (n) in the right-hand column. The values of (n) correspond to samples of (t) separated by the spacing of adjacent phases of the TIC. The sample points are shown as delta functions in the left-hand column.

The output phases of the TIC which are the most sensitive to time shifts are those that correspond to samples of (t) where it is changing most rapidly. In Figure 10, these are the two outputs to either side of the central correlation peak in the (n) trace as well as the other "odd" numbered samples, where the central peak is "even". Also, the fact that the central peak is essentially constant over a broad range of time shifts is important, since it serves as a reference level for automatic gain control functions.

FIGURE 10. The trace labeled (t) on the left-hand side is the continuous time cross-correlation function. The trace labeled (n) on the right-hand side is the correlation results produced by a Time-Integrating Correlator, with "time sample" separations of 125 ps. Note how the "even" samples (e.g. the peak at 0 ns) are essentially unchanged with the relative time shift of the received signal versus the reference code, while the "odd" samples change significantly with even a 125 ps time shift.

 

FIGURE 11. Evolution of the pattern of output phases of the Time-Integrating Correlator as the alignment of the received signal and reference code shifts in increments of 1/8-phase. These are for a 31-doublet maximal sequence with phases (i.e. time shift bins) separated by 2.5 ns, and each graph representing an additional 312 ps relative time shift between received signal and reference code. The pattern differences are quite easily detected using neural networks in software. Note that a time shift of 2.5 ns produces the same pattern in the lower right graph as in the upper left graph, except the pattern is centered in bin 9 instead of bin 8.

 
 

MULTIPLEXING AND ADAPTIVE POWER CONTROL

The use of correlation for reception of different code sequences allows multiple Localizers to transmit at the same time in the same area. In spread spectrum parlance this is Code Division Multiple Access (CDMA), which suffers from what is known as the near-far problem. Essentially, a nearby Localizer transmitting at the same time as a far away Localizer can overwhelm the distant signal. As with other spread spectrum CDMA systems, Localizers can handle this problem by adaptively reducing their transmit power when communicating with other nearby Localizers. Since Localizers communicate in bursts with low duty cycle, Time Division Multiple Access (TDMA) can also be used to deal with the near-far problem. As with Aloha Net, Localizers that find too much noise at one instant can move to another "time slot".

 

COMMUNICATION

Our cooperative ranging approach to localization requires communication between Localizers. To send information, code sequences have to be modulated in some fashion. The simplest technique is to use "antipodal" modulation. This means either a given code sequence or its inverse is sent to represent one bit of information. The receiver will then detect a positive or a negative correlation peak. To eliminate the ambiguity of what is a "Ø" and what is a "1", certain sequences of bits are used as a preamble, yet never appear in the message.

Other forms of modulation can also be used, such as transmitting one of several possible codes, or delaying the impulse sequence by fixed amounts in order to place the received peak in one of several possible TIC phases.

CLOCKS AND TIMING

GPS satellites carry atomic clocks that are synchronized to an absolute standard. In principle, a GPS receiver can determine the range to a satellite by comparing the absolute time broadcast by the satellite to a local absolute time standard. Fortunately, GPS receivers can use the signals from four satellites to determine the absolute time by finding a consistent solution. Still, GPS requires extremely accurate and stable master clocks because it is a broadcast beacon system.

Localizers can use ordinary crystal oscillators for two reasons:

For example, assume two Localizers have determined the relative clock rate of each other's clocks. Each Localizer can then measure range with a fractional error given by the fractional error in its clock during an exchange of signals. Within a network of Localizers, only one Localizer needs to have a very accurate clock for other Localizers to absolutely calibrate their clocks. Independently knowing the distance between two Localizers can also be used for calibrating the clocks of all communicating Localizers.

Even with a perfectly accurate clock, a Localizer will have unknown circuit delays that will affect the measured time-of-flight delay for a signal. As long as these delays are relatively stable, they can be measured and factored out of the range computation. The technique for doing this requires a Localizer to receive the same signal it sends. All the measured delay will then be due to circuit delays.


 

PROTOCOLS FOR SYNCHRONIZATION

Before a pair of Localizers can perform ranging transactions, they must become synchronized. Each Localizer must know when it can transmit a code and when it should be receiving a code from the other Localizer. In a typical synchronization protocol, one of the Localizers (B) would broadcast a code on a regular periodic basis. Another Localizer (A) would have to do an exhaustive search to receive one of these beacon codes. Because the reception window (the span of the Time-Integrating Correlator phases) is small, synchronizing can take on the order of several seconds. Once a beacon is found, Localizer A can "track" the following beacons. Because the clocks on the Localizers are presumed to be slightly different, Localizer A must analyze the time difference between pairs of beacons and compare this to the expected beacon period. This allows Localizer A to calculate the ratio of its clock rate to the clock in Localizer B. This clock ratio can be used to correct for the inaccuracy of Localizer B's clock in all following transactions.

After this analysis, Localizer A has half of the information necessary for synchronization (when to listen to hear Localizer B), but Localizer B needs to find a time when it can receive from Localizer A. After Localizer A finds the beacon, it could start transmitting a return code on a periodic basis. Localizer B would have to continuously do an exhaustive search for such a return beacon, waiting for both A's search and analysis to finish, and then waiting for its own search to complete. When Localizer B completes the search, it can indicate synchronization has been achieved by modifying the next beacon, such as by antipodally modulating the code in the beacon. Alternately, Localizer B could continuously wait for a return code at a fixed phase in the beacon period, and require Localizer A to perform this second search as well as the first one.

Since the time between beacons will typically be on the order of a millisecond, the time to do the second half of the synchronization search can be greatly reduced by placing the return codes at a small known delay before or after the beacon code. For example, if Localizer A always transmits the return code immediately after receiving the beacon, then Localizer B will only have to search a small time span after the beacons to find the return codes. Assuming that Localizers have a range less than a kilometer, only the first 3 microseconds of the millisecond beacon period must be searched. This decreases the second search of the synchronization process from seconds down to tens of milliseconds. Also, knowing that Localizer A turned the beacon back immediately, Localizer B can calculate a round trip time and use that to generate an approximate distance to Localizer A. In a slightly different protocol that makes Localizer A do most of the work, Localizer B always listens for a return code immediately before each beacon, and Localizer A is required to search backwards from the beacon to find the correct time to hit Localizer B's fixed reception window. This protocol allows A to calculate the first approximate distance instead of Localizer B. As mentioned above, Localizer A will know when the search is complete when Localizer B responds by modifying the next beacon.

PROTOCOLS FOR COOPERATING LOCALIZERS TO DETERMINE RANGE

Figure 12 shows the simplest ranging transaction. Ranging requires sending a code from a first Localizer to a second one, and then getting another code back. Note that unlike RADAR, the return signal is not the echo, but a retransmission of a new code. In Figures 12, 13, and 14, a positive pulse on the timeline represents the transmission of a code, and the reception of a code is represented by a negative pulse. Localizer A transmits a code at time T1 in Figure 12, a time which is known to hit a prearranged reception window centered around time T2 on Localizer B's timeline. The shaded boxes in the figures represent calculation times, when the processors on the Localizers are analyzing the results of receptions. Localizer B must do a calculation to determine the actual arrival time of the code from Localizer A, which may not have arrived exactly in the center of the reception window. This calculated actual time is labeled as time T2a. The protocol for ranging includes a fixed time delay, called DTc, which is large enough to allow a Localizer to determine the actual arrival time, plus a small safety margin. Localizer B delays this DTc time after the actual arrival time T2a, and sends the return code at a time called T3. Localizer A knows the value of the DTc delay, and has an approximate distance to B (to within ±10 meters) from previous synchronization procedures. This allows Localizer A to calculate an arrival time and schedule a reception window centered around this time, called T4. Then Localizer A must calculate the actual arrival time, T4a, during a calculation time represented by a gray box on A's timeline. The difference between time T4a and T1, minus the known DTc delay, is the round trip propagation time of the signal between the two Localizers. Half of this propagation time, times the speed of light, is the distance between the two Localizers. The calculations are complicated somewhat by the fact that the clock rates of the two Localizers are assumed to be different. But an approximation of the ratio of the speeds of the clocks of the two Localizers is available (from previous synchronization procedures) and this can be taken into account.

FIGURE 12. Timeline representation of simple ranging protocol. A positive pulse on the timeline represents the transmission of a code, and a negative pulse represents the reception of a code.
Figure 13 shows an improved ranging protocol. The total time between all measurements is decreased, making it less susceptible to drift in the clock rates of the two Localizers. Also, a layer of digital communication is shown, indicating how the accuracy can be increased when the Localizers share information. Localizer A sends a code at time T1 in Figure 13, which Localizer B expects to receive around time T2. A small fixed delay DTd after the expected reception window, but before taking the time to analyze it, Localizer B sends a return code. Localizer A schedules to receive this return code at a time T4 that is calculated from the approximate distance and the known value of DTd. Both Localizers then calculate the actual arrival times, T2a and T4a, of their respective received signals. If Localizer A's transmission did in fact arrive exactly at time T2, Localizer A could calculate the round trip propagation time from the difference between time T4a and time T1, minus the known DTd delay.

Localizer B's return transmission time was based on the expected reception time, T2, instead of the actual reception time T2a. The difference between these two times is calculated, and transmitted from Localizer B to Localizer A as a series of codes after the two ranging calculations are complete. These data codes are transmitted a fixed delay time DTc after the start of the return transmission, which gives Localizer B time to do all the calculation necessary. When Localizer A has received this time difference, it can be used to correct the round trip propagation time to take the actual arrival time at Localizer B into account. Note that Localizers A and B have different clocks, running at perhaps slightly different rates, and the "actual arrival time" on either Localizer's clock would be meaningless. Only the difference between times on one Localizer's clock is ever sent to the other Localizer. Even this time difference must be corrected for known clock rate ratios in a complete algorithm.

FIGURE 13. Timeline representation of an improved ranging protocol, which measures a round trip delay with quick turn-around by Localizer B and post-correction of the predicted reception time after an accurate calculation of the real reception time by Localizer B.
Figure 14 shows a more complicated, and thus more complete, ranging transaction protocol. Localizer A sends a ranging code to Localizer B, which replies immediately with a return code. Both Localizers analyze the codes to calculate the actual arrival times. Then the Localizers reverse roles, and Localizer B initiates a similar ranging exchange: Localizer B sends a ranging code, which Localizer A receives and immediately returns. Again, both Localizers analyze the codes to calculate the actual arrival times. Finally, Localizer B sends its results to Localizer A as a series of codes containing digital bits of information. The information sent would include the difference between the expected and actual arrival time of the first ranging code received at Localizer B, and the round trip time of the second complete ranging exchange. With this information, in addition to its own measured values, Localizer A has enough information to solve two equations for two unknowns, and calculate both the distance and the ratio of the clock rates between the two Localizers.

FIGURE 14. Timeline representation of a more complicated ranging protocol, again using quick turn-around and digital post-correction.
Back