Tag: OEM

Using HD Radio Signals for Navigation

By Ananta Vidyarthi, H. Howard Fan and Stewart DeVilbiss

THE YEAR WAS 1906. On Christmas Eve of that year, Canadian inventor Reginald Fessenden carried out the first amplitude modulation (AM) radio broadcast of voice and music. He used a high-speed alternator capable of rotating at up to 20,000 revolutions per minute (rpm). Connected to an antenna circuit, it generated a continuous wave with a radio frequency equal to the product of the rotation speed and the number of magnetic rotor poles it had. With 360 poles, radio waves of up to about 100 kHz could be generated. However, Fessenden typically used a speed of 10,000 rpm to produce 60 kHz signals. By inserting a water-cooled microphone in the high-power antenna circuit, he amplitude-modulated the transmitted signal. On that Christmas Eve, he played phonograph records, spoke and played the violin with radio operators being amazed at what they heard.

Fessenden had earlier worked with spark-gap transmitters, as these were standard at the time for the transmission of Morse code, or telegraphy, the wireless communication method already in use. But they couldn’t generate a continuous wave and couldn’t produce satisfactory AM signals. But as telegraphy was the chief means of communication, they remained in use for many years along with high-powered alternators and the Poulsen arc transmitter, which could also generate continuous waves.

Although other experimental AM broadcasts were carried out using alternators or arc transmitters, voice transmissions — and in particular sound broadcasting — didn’t take off until the invention of amplifying vacuum tubes. Just before World War I, it was found that they could be used in an oscillator circuit to produce continuous waves, which could be easily modulated to make an AM transmitter. Such transmitters could be used for point-to-point communications but also for broadcasting, and a number of experimental broadcasting stations were established in Europe and North America during and just after the war. Tubes were also instrumental for improvements in receiver technology. “Where there was one licensed station in America in 1920, there were nearly 600 stations just five years later, and the number of radio receivers went from thousands of crystal sets to millions of vacuum-tube circuits.” — from The Science of Radio by Paul J. Nahin, one of my favorite writers on electronics and mathematics.

AM radio broadcasting used frequencies in the long-wave, medium-wave and short-wave frequency bands, and still does. But AM signals often have low audio quality due to bandwidth limitations imposed by regulators and interference from other stations, atmospheric disturbances and electrical noise. So, over the past decade or so, many broadcasters have abandoned long-wave and medium-wave frequencies and moved to the frequency modulation or FM broadcast band with its superior signal capability.

However, this migration pattern might be slowed or stopped if digital broadcasting were to be fully embraced on the AM broadcast bands. A digital technique developed by the iBiquity Digital Corporation is gradually being adopted by broadcasters in the United States and elsewhere. The technique provides FM-quality sound in the medium-wave band by supplementing existing AM signals or replacing them altogether. It can also supply data about the transmitting station and its broadcast. Some 240 AM radio stations in the U.S. already use the technology. (It can also be used in the FM band to provide CD-like quality.)

But these digital signals in the AM broadcast band might serve an additional purpose beyond improving the listening experience. In this month’s column, our authors tell us about some extensive simulation work they have carried out to demonstrate the feasibility of using digital radio signals for navigation. In the future, you may be able to turn on your radio and tune in to get to where you’re going.

---

“Innovation” is a regular feature that discusses advances in GPS technology and its applications as well as the fundamentals of GPS positioning. The column is coordinated by Richard Langley of the Department of Geodesy and Geomatics Engineering, University of New Brunswick. He welcomes comments and topic ideas. Email him at lang @ unb.ca.

---

It is well known that the GPS signals are weak and are therefore subject to interference and blockage due to obstruction. Signals of opportunity (SOO), on the other hand, which are designed for other purposes such as communication, may also be used for navigation and have relatively greater signal power than GPS. They are plentiful and relatively more resistant to blockage and jamming compared to GPS. Many authors have presented methods and algorithms utilizing SOO such as AM and FM broadcast signals, TV broadcast signals and 3G/4G wireless communication signals (see Further Reading for examples). These signals are robust and have very good received power levels compared with GPS, and are capable of penetrating through buildings. In addition, these signals are readily available and there is no need for any additional installation of transmitting devices or infrastructure.

In this article, we present the results of a study using AM HD Radio, digital radio in the 540–1700 kHz band of the frequency spectrum, with known transmitter locations, to locate and track receiver locations that are otherwise unknown. HD Radio, originally meaning hybrid-digital radio, is a trademarked term for iBiquity Digital Corporation’s digital radio technology. Unlike analog AM radio signals, digital radio signals are well structured and more immune to co-channel interference, and hence could be better adapted for navigation. In addition, with the proliferation of software-defined radios (SDRs), digital AM radio may eventually replace analog AM radio.

The challenges of navigation using digital radio signals include narrow signal bandwidths, long symbol durations and lack of synchronization among transmitters. Therefore, digital radio signals are not an ideal choice for accurate position estimation, similar to many other SOO that aren’t designed for navigation. Nevertheless, in this work, we have designed algorithms to overcome such difficulties to obtain a good level of location accuracy, making it a feasible alternative for SOO navigation.

Signal Format of Digital AM Radio

Digital AM signals have a well-defined structure called in-band-on-channel (IBOC) that can be exploited for localization purpose. It employs sophisticated digital radio waveforms, which can deliver compact-disc-like sound quality, free of interference and noise, to radio listeners. It uses the existing AM and FM analog broadcasting bands and channel schemes to transmit digital signals. The IBOC digital radio transmitter system encodes analog audio into binary form for transmission.

The design provided by IBOC AM radio has two service modes with two new waveform types: hybrid (denoted by MA1) and all-digital (denoted by MA3). The hybrid waveform retains the analog AM signal, while the all-digital waveform completely replaces the analog AM signal. In the hybrid service mode, the bandwidth of the analog audio signal waveform can be 5 kHz or 8 kHz. The digital signal is transmitted on both sides of the analog host signal in the primary and secondary sidebands. It is also transmitted on the tertiary sidebands, which are 20 dB beneath the analog signal as shown in FIGURE 1.

For the 8-kHz configuration, the secondary sidebands are also beneath the analog host signal. The greatest system enhancements are realized with the all-digital system, as shown in FIGURE 2. In this system, the analog signal is replaced with the all-digital primary sidebands whose power is increased relative to the hybrid system levels. Secondary and tertiary sideband powers are also increased to the level of the hybrid waveform. Reference subcarriers are also provided to convey system control information. The end result is a higher power digital signal with an overall bandwidth reduction.

Digital radio offers distinct advantages over analog, including mitigation of transmission artifacts and improved audio quality. These changes provide a more robust digital signal that is less susceptible to adjacent channel interference, thereby reducing the noise in the system. An overview of the AM digital system for both the service modes, MA1 and MA3, is given in the following paragraphs. However, in the simulation study we carried out, we used the all-digital AM (MA3) mode. The all-digital AM system has a smaller bandwidth than the hybrid signal. If reasonable localization results can be obtained with it, then we can predict that better localization results may be obtained with the hybrid signal.

IBOC uses an orthogonal frequency-division multiplexing (OFDM) waveform for signal modulation. Each OFDM subcarrier channel has a spacing of 181.7 Hz. The hybrid MA1 service mode comprises 163 subchannels indexed from -81 to 81 over a total bandwidth of 29.4 kHz as shown in Figure 1. The all-digital MA3 service mode has only 105 subchannels indexed from -52 to 52 over a total bandwidth of 18.9 kHz as shown in Figure 2. Therefore, when compared to the all-digital mode, hybrid mode contains more training symbols per OFDM symbol duration. The training symbols are important since these symbols are known and will be used to perform correlation to estimate the signal time of arrival. We predict that since the hybrid mode contains more training symbols than the all-digital mode, detection accuracy will be higher for the hybrid mode. Hence, choosing the all-digital MA3 service mode for the localization will be more challenging, and this is another reason for our decision to use MA3. Demonstrating the capability of the all-digital MA3 service mode for localization would imply that the hybrid mode could be used for the same, with at least the same or better performance.

Interleaving in time and frequency is used to mitigate the effects of burst errors. The interleaver output is according to a structured matrix (not shown here). Each interleaver matrix consists of information associated with a specific portion of the transmitted spectrum, and consists of eight interleaver blocks, with each block of size of 32 × 25. Hence, each block has 800 symbols to be filled, out of which 50 are known training symbols. Since this work entirely relies on training symbols, understanding interleaving is important so we know exactly where the training symbols are in a signal data stream. From the interleaving matrix, the positions of all training symbols are given, which have a periodic appearance of every 16 rows.

The OFDM subcarrier mapping transforms interleaver output into scaled 16 quadrature amplitude modulation (QAM) and 64 QAM and binary phase-shift keying (BPSK) symbols and then maps them to specific OFDM subcarriers. The inputs to OFDM subcarrier mapping are according to the interleaver matrices, which map respective symbols to the primary, secondary, tertiary, Primary IBOC Data Service (PIDS) and reference subcarriers. One row of each active interleaver matrix and one bit of the system control vector are mapped into each OFDM symbol (every T_s seconds) to produce one output vector X, where T_s = 5.805 × 10^-3 seconds.

OFDM signal generation takes the complex frequency domain OFDM symbol X as generated above and outputs a time-domain representation of the digital signal. Let X_n be the vector X for the nth OFDM symbol, and X_n[k] be the kth element of X_n, which is the complex scaled constellation points for the subcarrier mapping for the nth symbol, where k = 0, 1,…, L-1 is the subcarrier index in the frequency-domain input to the signal generation for transmission. The input vector X is transformed into a shaped time-domain baseband pulse y_n(t) defining the nth OFDM symbol as

where n = 0, 1, …, ∞, .  Note that n indexes consecutive OFDM symbols, L = 105 is the maximum number of OFDM subcarriers, T_s and ∆f are the OFDM symbol period and OFDM subcarrier spacing, respectively, and W(t) is the time-domain pulse shaping function.

Time of Arrival Acquisition

Since the training symbols are known, a local copy can be generated at a receiver to correlate with the received digital AM signal to measure signal time of arrival (TOA). Measuring TOA accurately from a correlation peak is crucial, since any error in TOA measurement directly affects localization accuracy. The relatively narrow bandwidths and hence long symbol durations of the digital AM radio signals pose a challenge as they give rise to potentially large timing errors, thereby greater localization errors. To improve the location accuracy, strong digital AM signal levels are used to our advantage so methods such as curve fitting and time averaging can be performed. Moreover, unlike the structures of the civil GPS signals, which are all known, only the training symbols and their positions in the digital AM signals are known. Other data in the digital AM signals are random and cannot be used for correlation. Therefore, using long correlation vectors will help in detecting peaks as there will be more training symbols.

Sampling. Correlation is performed, of course, after sampling. So we first discuss how to choose an appropriate sampling frequency. After correlation, if we detect the peak and record it as TOA only at the corresponding sampling instant, a maximum distance error of c/2f_s can occur between two adjacent samples, where c is the speed of light and f_s is the sampling frequency. At the Nyquist sampling frequency, say 40 kHz, this error could be as large as 3,750 meters. Sampling at a frequency much higher than the Nyquist can help to improve accuracy, but this improvement diminishes as the sampling frequency increases beyond a certain value, because the narrow signal bandwidth makes the peak of its correlation function rounded, so detection of the actual peak becomes less accurate. In our simulations, we found that this point of diminishing returns is at about f_s = 10 MHz, at which the error between two adjacent samples is 15 meters, much better than that at the Nyquist sampling rate. This high sampling rate is easily doable with today’s digital technologies. However, this 15-meter error is the ranging error between one transmitter and one receiver. Five or more transmitters have to be considered for the location algorithm presented in a later section. Then, the ranging error of 15 meters may magnify to the order of a few kilometers as location errors. Clearly, there is a need to detect TOA of a correlation peak between two adjacent samples; that is, we need interpolation to achieve a smaller TOA error.

Interpolation. To calculate the TOA between two adjacent samples, we interpolate by curve fitting the correlation data and estimate the TOA by solving polynomial functions. It was observed that the correlation peak is asymmetric, so the correlation curve is shaped differently to the left and right of the peak value. This is illustrated in FIGURE 3. Therefore, we need to fit two different curves on each side of the correlation peak. By a trial-and-error process, we determined that a quadratic polynomial is sufficient to fit the correlation values close to the peak. Therefore two simple quadratic functions are fitted for the correlation data points to the left and right of the peak.

FIGURE 4 shows curve fitting for the correlation of a received signal and a local signal sampled at 10 MHz. The maximum time error due to sampling is T_samp/2, which equals 5 ×10^-8 seconds. This translates into a distance error of 15 meters and localization error of a few kilometers as mentioned before. From Figure 4, it is seen that the intersection point, which is taken as the measured TOA, is much closer to the actual TOA resulting in a much smaller distance error.

Based on the HD Radio documentation, a normal signal-to-noise ratio (SNR) is calculated to be 52 dB. However, in case of adverse channel conditions, lower SNR levels of 30 dB and 10 dB have also been considered. Our simulations show that, with additive white Gaussian noise, the TOA estimation errors are affected by SNR very little above 10 dB, and are improved by an order of magnitude compared with no curve fitting. To make sure the TOA estimation error for the 10 dB SNR case can be used for the purpose of localization, we carried out a Monte Carlo simulation. Twenty-one different random signals were simulated, and the TOA measurement errors after curve fitting were recorded at different delays. The ensemble average of these TOA estimation errors was within 2 ×10^-9 seconds. These results confirm that a 10 dB SNR signal can be very well used for localization. Thus, we used an SNR of 10 dB for all the simulations discussed later in this article.

Differential Time-Difference of Arrival

Once all the TOAs from different transmitters are obtained, they are sent to a processing station, which could be one of the receivers. Due to lack of synchronization in digital AM radio transmitters as well as unknown clock offsets in digital AM radio receivers, the obtained TOAs are not aligned, so they cannot be directly used for location determination. A technique called differential time-difference of arrival (dTDOA), which is similar to GPS double differencing and was published by the authors elsewhere (see Further Reading), is employed here to overcome this problem.

Consider the case where there are two transmitters, A and B, and two receivers, C and D, as shown in FIGURE 5.

When transmitter A is transmitting, its signal is received at different time instances by receivers C and D due to different propagation delays. The internal clock of each receiver records the correlation peak with respect to its local time at the corresponding receivers. TOAs of the signal from transmitter A at both receivers C and D are recorded as  and , which also contain the unknown transmitter A clock time offset. Differencing these two TOAs  , the unknown transmitter A clock time offset is cancelled. But this TDOA is unsynchronized, so it cannot be used for location determination. Then we find the similar unsynchronized TDOA from transmitter B, . To eliminate the unknown receiver clock offsets we difference the two TDOAs, resulting in a dTDOA:

Thus, by using a minimum of two transmitters and two receivers, a dTDOA cancels receiver clock offsets and transmitter clock offsets, thus avoiding the need of precise clock synchronization. The number of independent dTDOA equations required to solve for the locations of n receivers is given by (m-1)(n-1) where m is the number of transmitters, and n is the number of receivers. For two receivers, there are four unknowns in a two-dimensional positioning plane, so we need a minimum of five transmitters to obtain four independent equations to solve for four unknown location parameters. If one of the receivers is permanently stationary with a known location such as in differential GPS, then we only need three transmitters to solve for two unknown horizontal location parameters, or four transmitters for three unknown location parameters in 3-D .

The above dTDOA equations, when expressed in terms of receiver locations, are non-linear. The non-linear over-determined or exact system of equations can be solved using iterative procedures, such as non-linear least squares or the Levenberg-Marquardt (LM) technique. In the simulations we ran, we found that the LM method was more robust than the Gauss-Newton method because it was capable of converging to the solution in the global minimum even if the initial guess was relatively far away. But a reasonable initial estimate of the solution can help with faster convergence. If the initial estimate is too far away, the solution often converges to a local minimum instead of the global minimum.

Therefore, a good initial estimate of the solution is crucial. An approximate initial estimate can be calculated in several ways. For example we can solve linearized equations based on the non-linear dTDOA equations. Or we can use a simple table lookup if we have some a priori knowledge of roughly where the receivers are located.

Once the initial locations are found, the next step is to track the locations of the receivers when they are moving. A Kalman filter should be used for tracking. A Kalman filter can also incorporate the non-linear dTDOA equations with TOA measurement as input for close coupling between localization and tracking. Or, for simplicity, short of using a Kalman filter, the previous locations can be fed into the LM method to find the next locations. The LM method for this kind of tracking has faster convergence than for repeated initialization, so the next locations can be calculated quickly.

Time Averaging. Due to error in tracking, the computed locations are not exact but are usually around the actual location. Time averaging is then used to further improve tracking performance. Time averaging can also be used to smooth the TOA measurements or the locations computed from dTDOA equations as input to a Kalman filter.

Repeated use of the LM method, as shown in FIGURE 6, for estimating a stationary receiver’s coordinates always forms an error ellipsoid because of the noise and computation error. The estimated points are depicted by black points in Figure 6. The small yellow circle in the middle corresponds to the actual location. By simulation, it was found that averaging all the possible estimated locations produced a location much closer to the actual location, as depicted by the red cross in Figure 6. Obviously the more points to average — that is, the larger the time-averaging window — the more accurate the averaged location will be. In general, such time averaging can improve location and tracking performance by an order of magnitude.

For a moving receiver, there is a trade off in choosing the time-averaging window. The larger the time-averaging window, the better the averaged location accuracy, but the larger the resulting time delay in the averaged location. This time delay is also affected by how frequently we update the tracked locations. Receiver velocity and the Doppler effect also affect the choice of the time-averaging window.

Simulation Results

We performed a comprehensive computer simulation study. The primary aim of this simulation study was to prove that the accuracy of digital AM signals for navigation can be improved using the methods introduced in the previous sections, despite the narrow bandwidth of the signals, thereby making digital AM a viable choice for navigation. A number of factors will affect the performance of navigation using digital AM signals including the sampling frequency, SNR, time-averaging window and location update frequency. In this simulation study, these factors have been taken into consideration.

To simulate a realistic environment, we chose the city of Chicago, where there are many digital AM transmitters providing good coverage to the city. We chose the six best transmitters in Chicago based on the power of the signal and location. The working range of the receivers is large enough to perform a detailed study of all the navigation techniques. The locations of the radio station transmitters are shown in FIGURE 7. All figure axes are in kilometers. Colored dots are transmitter locations; colored circles are their ranges. Green tracks are the chosen routes for a fast-moving receiver. Short brown tracks are those of the other receiver, somewhere in the same zone and traveling slowly.

We simulated two receivers moving along the chosen green and brown routes, but we will only show the navigation results of the faster moving receiver along the green routes. A minimum of five transmitters is needed. The entire simulation was done in Matlab. The time-domain digital AM received signals were modeled according to the specifications described previously. Delays corresponding to transmitter and receiver locations were calculated and simulated into the signals received at the two receivers. An SNR of 10 dB was used for all received signals. Along Route 1 (upper left corner of Figure 7), five transmitter signals can be received, whereas along Route 2 (center right in Figure 7), six transmitter signals are received. Simulation conditions and results for these two routes are given in TABLES 1 and 2.

In addition, the tracking results for the fast-moving receiver are laid on top of photo maps of the routes, and are shown in FIGURES 8 and 9. The worst-case situation happens when, for example, transition of zones or handover of transmitters happen, for which no specific additional measures were taken in the simulations as shown in Figure 8.

However, the typical tracking result in Figure 9 happens most of the time. Clearly, the more transmitters that can be used, the better the accuracy results. Use of more than two receivers or use of a stationary receiver with a known location can reduce this demand on the number of transmitters.

The fast sampling frequency, the curve fitting and the time-averaging window are the most important factors affecting the accuracy of this work, and are easily adjustable. In our simulations we used a time-averaging window of 1 second. We expect that the accuracy would further improve as the time-averaging window is increased, but this would result in increased latency. The velocity of the receiver is one limiting factor in choosing the time-averaging window. For a receiver traveling at a maximum speed of 145 kilometers per hour, a time-averaging window of 1 second corresponds to 20.14 meters of tracking lag. Any greater tracking lag may become intolerable. In general, our simulations show that curve fitting alone and time averaging alone each improved localization accuracy by an order of magnitude. When curve fitting and time averaging were combined, the localization accuracy was improved by two orders of magnitude. If a Kalman filter were used for tracking, we would expect further accuracy improvement.

Other challenges that deserve further study to make this concept a mature technology include multipath propagation and its mitigation, incorporation of estimating digital AM carrier phase, and incorporation of a Kalman filter for tracking. Further increased location accuracy is expected by incorporation of these techniques.

Acknowledgment

This article is based, in part, on the paper “A Navigation Solution Using HD Radio Signals” presented at the 2015 International Technical Meeting of The Institute of Navigation, Dana Point, Calif., Jan. 26–28, 2015.

---

ANANTA VIDYARTHI graduated from Anna University, India, in 2009 with a B. Tech. degree in electronics and communication engineering. She came to the University of Cincinnati in the fall of 2009 and earned her M.S. degree in 2012 in electrical engineering. Currently, she is working with Cummins Inc. in Columbus, Ind.

H. HOWARD FAN graduated from the University of Illinois in Urbana-Champaign with a Ph.D. in electrical engineering in 1985. He has been on the faculty of the University of Cincinnati since then, where he is a professor of electrical engineering and computing systems. His research interests are in digital signal processing, system identification, signal processing for communications, interference mitigation, direction finding, and navigation and location.

STEWART DEVILBISS graduated from Ohio State University with a Ph.D. in electrical engineering in 1994. Since 2007 he has served as the technical advisor for the Navigation and Communication Branch at the Sensors Directorate of the Air Force Research Laboratory, headquartered at Wright-Patterson Air Force Base, Ohio. His primary research interest is in technologies to improve navigation robustness and accuracy.

FURTHER READING

• Authors’ Conference Paper

“Navigation Solution Using HD Radio Signals” by A. Vidyarthi and H.H. Fan in Proceedings of ION ITM 2015, the 2015 International Technical Meeting of The Institute of Navigation, Dana Point, Calif., Jan. 26–28, 2015, pp. 285–292.

• HD Radio

The IBOC Handbook: Understanding HD Radio Technology by D.P. Maxson. Published by Focal Press, Burlington, Mass., 2013.

HD Radio Air Interface Design Description – Layer 1 AM, Doc. No. SY_IDD_1012s, Revision E. Published by iBiquity Digital Corporation, Columbia, Md., March 22, 2005.

HD Radio AM Transmission System Specifications, Doc. No SY_SSS_1082s, Revision F. Published by iBiquity Digital Corporation, Columbia, Md., Aug. 24, 2011.

• Differential Time-Difference of Arrival

“Asynchronous Differential TDOA for Non-GPS Navigation Using Signals of Opportunity” by C. Yan and H.H. Fan in Proceedings of ICASSP 2008, the IEEE 2008 International Conference on Acoustics, Speech and Signal Processing, Las Vegas, Nev., March 31–April 4, 2008, pp. 5312–5315, doi: 10.1109/ICASSP.2008.4518859.

• Positioning Using Analog AM Signals of Opportunity

“Opportunistic Navigation: Finding Your Way with AM Signals of Opportunity” by J. McEllroy, J.F. Raquet and M.A. Temple in GPS World, Vol. 18, No. 7, July 2007, pp. 44–49.

“Phase Measurements Using Direct Conversion AM Radio Navigation” by A. Dinh, R. Mason, R. Palmer and K. Runtz in Proceedings of WESCANEX 97, the IEEE 1997 Conference on Communications, Power and Computing, 22–23 May 1997, pp. 280–285, doi: 10.1109/WESCAN.1997.627154.

• Positioning Using TV Signals of Opportunity

“Cooperative position location with signals of opportunity” by C. Yang, T. Nguyen, D. Venable, M. White and R. Siegel in Proceedings of NAECON 2009, the IEEE 2009 National Aerospace and Electronics Conference, Dayton, Ohio, July 21–23, 2009, pp. 18–25, doi: 10.1109/NAECON.2009.5426658.

“Prime Time Positioning: Using Broadcast TV Signals to Fill GPS Acquisition Gaps” by M. Martone and J. Metzler in GPS World, Vol. 16, No. 9, Sept. 2005, pp. 52–60.

“A New Positioning System Using Television Synchronization Signals” by M. Rabinowitz and J. J. Spilker, Jr. in IEEE Transactions on Broadcasting, Vol. 51, No. 1, March 2005, pp. 51–61, doi: 10.1109/TBC.2004.837876.

• Positioning Using 3G Cellar Signals of Opportunity

“A Signals of Opportunity Based Cooperative Navigation Network” by M.A. Enright and C.N. Kurby in Proceedings of NAECON 2009, the IEEE 2009 National Aerospace and Electronics Conference, Dayton, Ohio, July 21–23, 2009, pp. 213–218, doi: 10.1109/NAECON.2009.5426626.