Blind identification of single-frequency-network transmitters

Description

CROSS-REFERENCE TO RELATED APPLICATIONS

This application claims benefit of U.S. Provisional Patent Application Ser. No. 60/866,886 filed Nov. 22, 2006, the disclosure of which is incorporated by reference herein in its entirety.

BACKGROUND

The present invention relates generally to single-frequency networks. More particularly, the present invention relates to blind identification of single-frequency-network transmitters.

In many conventional broadcast transmission systems, a transmitter can be identified based on the signal it transmits. For example, in a frequency-division multiple access (FDMA) broadcast television (TV) network, individual TV channels can be identified by their transmit frequencies, and linked to their corresponding points of broadcast.

In contrast, single-frequency networks (SFN) transmit virtually identical signals from multiple points of transmission. Broadcasts from the various transmitters are generally synchronized, for example by GPS, to within tens of nanoseconds. While this type of macro-scale diversity has shown great merit in combating fading, in terms of positioning this method poses a significant problem in that an SFN signal does not identify its transmitter.

SUMMARY

In general, in one aspect, the invention features an apparatus comprising: an input module adapted to receive a plurality of pseudoranges each determined by a receiver based on one of a plurality of wireless single-frequency network (SFN) signals transmitted at a predetermined frequency from a corresponding plurality of transmitters; and a transmitter identification module adapted to identify one of the transmitters for each of the pseudoranges based on the pseudoranges and a plurality of ranges each predetermined between one of the transmitters and one of a plurality of predetermined geographic locations.

In some embodiments, the transmitter identification module comprises: an error module adapted to generate an error for each of the geographic locations based on the ranges for the respective geographic locations and the pseudoranges; wherein the transmitter identification module identifies the transmitters based on the errors. Some embodiments comprise a location module adapted to determine a location of the receiver based on locations of the transmitters identified by the transmitter identification module and the pseudoranges. In some embodiments, the transmitter identification module selects a subset of the predetermined geographic locations based on one or more non-SFN signals received by the receiver; and the transmitter identification module identifies the transmitters based on the pseudoranges, the subset of the predetermined geographic locations, and the ranges corresponding to the subset of the predetermined geographic locations. Some embodiments comprise the receiver.

In general, in one aspect, the invention features an apparatus comprising: input means for receiving a plurality of pseudoranges each determined by a receiver based on one of a plurality of wireless single-frequency network (SFN) signals transmitted at a predetermined frequency from a corresponding plurality of transmitters; and transmitter identification means for identifying one of the transmitters for each of the pseudoranges based on the pseudoranges and a plurality of ranges each predetermined between one of the transmitters and one of a plurality of predetermined geographic locations.

In some embodiments, the transmitter identification means comprises: error means for generating an error for each of the geographic locations based on the ranges for the respective geographic locations and the pseudoranges; wherein the transmitter identification means identifies the transmitters based on the errors. Some embodiments comprise location means for determining a location of the receiver based on locations of the transmitters identified by the transmitter identification means and the pseudoranges. In some embodiments, the transmitter identification means selects a subset of the predetermined geographic locations based on one or more non-SFN signals received by the receiver; and the transmitter identification means identifies the transmitters based on the pseudoranges, the subset of the predetermined geographic locations, and the ranges corresponding to the subset of the predetermined geographic locations. Some embodiments comprise the receiver.

In general, in one aspect, the invention features a method comprising: receiving a plurality of pseudoranges each determined by a receiver based on one of a plurality of wireless single-frequency network (SFN) signals transmitted at a predetermined frequency from a corresponding plurality of transmitters; and identifying one of the transmitters for each of the pseudoranges based on the pseudoranges and a plurality of ranges each predetermined between one of the transmitters and one of a plurality of predetermined geographic locations.

Some embodiments comprise generating an error for each of the geographic locations based on the ranges for the respective geographic locations and the pseudoranges; wherein the transmitters are identified based on the errors. Some embodiments comprise determining a location of the receiver based on locations of the transmitters and the pseudoranges. Some embodiments comprise selecting a subset of the predetermined geographic locations based on one or more non-SFN signals received by the receiver; and identifying the transmitters based on the pseudoranges, the subset of the predetermined geographic locations, and the ranges corresponding to the subset of the predetermined geographic locations. Some embodiments comprise receiving the wireless SFN signals.

In general, in one aspect, the invention features computer-readable media embodying instructions executable by a computer to perform a method comprising: receiving a plurality of pseudoranges each determined by a receiver based on one of a plurality of wireless single-frequency network (SFN) signals transmitted at a predetermined frequency from a corresponding plurality of transmitters; and identifying one of the transmitters for each of the pseudoranges based on the pseudoranges and a plurality of ranges each predetermined between one of the transmitters and one of a plurality of predetermined geographic locations.

In some embodiments, the method further comprises: generating an error for each of the geographic locations based on the ranges for the respective geographic locations and the pseudoranges; wherein the transmitters are identified based on the errors. In some embodiments, the method further comprises: determining a location of the receiver based on locations of the transmitters and the pseudoranges. In some embodiments, the method further comprises: selecting a subset of the predetermined geographic locations based on one or more non-SFN signals received by the receiver; and identifying the transmitters based on the pseudoranges, the subset of the predetermined geographic locations, and the ranges corresponding to the subset of the predetermined geographic locations. In some embodiments, the method further comprises: receiving the wireless SFN signals.

The details of one or more implementations are set forth in the accompanying drawings and the description below. Other features will be apparent from the description and drawings, and from the claims.

DESCRIPTION OF DRAWINGS

FIG. 1 shows a communication system comprising a user terminal receiving SFN signals from a plurality of respective SFN transmitters in an SFN network according to an embodiment of the present invention.

FIG. 2 shows detail of an apparatus according to an embodiment of the present invention.

FIG. 3 shows a process for the apparatus of FIG. 2 according to an embodiment of the present invention.

FIG. 4 shows a process for transmitter identification according to an embodiment of the present invention.

The leading digit(s) of each reference numeral used in this specification indicates the number of the drawing in which the reference numeral first appears.

DETAILED DESCRIPTION

As used herein, the terms “client” and “server” generally refer to an electronic device or mechanism, and the term “message” generally refers to an electronic signal representing a digital message. As used herein, the term “mechanism” refers to hardware, software, or any combination thereof. These terms are used to simplify the description that follows. The clients, servers, and mechanisms described herein can be implemented on any standard general-purpose computer, or can be implemented as specialized devices.

Embodiments of the present invention provide blind identification of single-frequency-network (SFN) transmitters. Various embodiments include an input module adapted to receive a plurality of pseudoranges each determined by a receiver based on one of a plurality of wireless SFN signals transmitted at a predetermined frequency from a corresponding plurality of transmitters, and a transmitter identification module adapted to identify one of the transmitters for each of the pseudoranges based on the pseudoranges and a plurality of ranges each predetermined between one of the transmitters and one of a plurality of predetermined geographic locations, also referred to herein as “survey points.” Some embodiments include a location module adapted to determine a location of the receiver based on locations of the transmitters identified by the transmitter identification module and the pseudoranges.

FIG. 1 shows a communication system 100 comprising a user terminal 102 receiving SFN signals 110A-C from a plurality of respective SFN transmitters 104A-C in an SFN network according to an embodiment of the present invention. Although in the described embodiments, the elements of communication system 100 are presented in one arrangement, other embodiments may feature other arrangements, as will be apparent to one skilled in the relevant arts based on the disclosure and teachings provided herein. For example, the elements of communication system 100 can be implemented in hardware, software, or combinations thereof.

The phrase “user terminal” is meant to refer to any object capable of implementing the techniques described herein. Examples of user terminals include PDAs, mobile phones, cars and other vehicles, and any object which could include a chip or software implementing the techniques described herein. Further, the term “user terminal” is not intended to be limited to objects which are “terminals” or which are operated by “users.”

In some embodiments, user terminal 102 performs the techniques described herein. In other embodiments, some or all of the techniques are performed by a location server 106 based on data collected by user terminal 102 and relayed by a relay station 108 such as a cellular base station and the like. The locations of SFN transmitters 104 can be stored in a SFN transmitter location database 112. The location of user terminal 102 can be transmitted to an E911 location server 116 for emergencies.

FIG. 2 shows detail of an apparatus 200 according to an embodiment of the present invention. Although in the described embodiments, the elements of apparatus 200 are presented in one arrangement, other embodiments may feature other arrangements, as will be apparent to one skilled in the relevant arts based on the disclosure and teachings provided herein. For example, the elements of apparatus 200 can be implemented in hardware, software, or combinations thereof. As another example, some elements of apparatus 200 can be implemented in user terminal 102, while other elements are implemented elsewhere, for example in location server 106.

Referring to FIG. 2, apparatus 200 includes a receiver 202 adapted to receive a plurality of SFN signals 110 at a predetermined frequency, a correlator 204 adapted to correlate the SFN signals 110 with a predetermined reference signal 206 to produce a plurality of correlation peaks, a pseudorange module 208 adapted to generate a respective pseudorange based on each of the correlation peaks, an input module 210 to receive the pseudoranges from pseudorange module 208, a transmitter identification module 212 adapted to identify one of transmitters 104 for each of the pseudoranges, and a location module 214 adapted to determine a position of user terminal 102. Transmitter identification module 212 comprises an error module 216 that is described in detail below.

FIG. 3 shows a process 300 for apparatus 200 of FIG. 2 according to an embodiment of the present invention. Although in the described embodiments, the elements of process 300 are presented in one arrangement, other embodiments may feature other arrangements, as will be apparent to one skilled in the relevant arts based on the disclosure and teachings provided herein. For example, in various embodiments, some or all of the steps of process 300 can be executed in a different order, concurrently, and the like.

Referring to FIG. 3, receiver 202 receives a plurality of SFN signals 110 at a predetermined frequency (step 302). The predetermined frequency can be selected by any means. For example, receiver 202 can receive a plurality of signals on a single 5 MHz DVB-H channel. Correlator 204 correlates received SFN signals 110 with reference signal 206 (step 304), thereby generating a series of correlation peaks. Reference signal 206 represents a repeating pattern in SFN signals 110, as is well-known in the relevant arts. In some embodiments, correlator 204 processes signals 110 in real time. In other embodiments, correlator 204 processes a previously-stored version of signals 110.

Pseudorange module 208 generates a pseudorange for each of the correlation peaks (step 306). Input module 210 receives the pseudoranges from pseudorange module 208. Transmitter identification module 212 matches SFN transmitters 104 with the pseudoranges (step 308). That is, for each pseudorange, transmitter identification module 212 identifies the SFN transmitter 104 that transmitted the SFN signal used by apparatus 200 to produce the pseudorange, as described in detail below. After the pseudoranges and transmitters have been matched, location module 214 can determine the location of user terminal 102 based on the pseudoranges and transmitter locations (step 310).

FIG. 4 shows a process 400 for transmitter identification according to an embodiment of the present invention. Although in the described embodiments, the elements of process 400 are presented in one arrangement, other embodiments may feature other arrangements, as will be apparent to one skilled in the relevant arts based on the disclosure and teachings provided herein. For example, in various embodiments, some or all of the steps of process 400 can be executed in a different order, concurrently, and the like.

Process 400 employs predetermined ranges between a plurality of predetermined survey points and SFN transmitters 104. The survey points can be selected according to any technique. For example, the survey points can be points in a grid, although any arrangement can be used.

The ranges between the selected survey points and SFN transmitters can be determined by any technique, for example such as conventional survey techniques. Each range can be a measure of the time required for an SFN signal 110 to travel from a given SFN transmitter 104 to a given survey point. The ranges can be stored for each survey point with transmitter identifiers, for example as shown in Table 1.

Referring to FIG. 4, process 400 sorts and de-biases the ranges (step 402). The ranges are sorted in ascending order. Then the first (that is, shortest) range is subtracted from each range. Note that the resulting first range is now zero. This subtraction has the effect of eliminating any constant systematic bias from the ranges. Of course, this step can be performed in advance to reduce the computational load on transmitter identification module 212. Process 400 also sorts and de-biases the pseudoranges (step 404), in the same manner as described for the ranges.

In some embodiments, transmitter identification module 212 reduces the search space by selecting a subset of the predetermined survey points based on one or more non-SFN signals received by receiver 202 (step 406). For example, when user terminal 102 is implemented as a mobile telephone, transmitter identification module 212 can select the subset of the survey points that fall within the cell within which the mobile telephone is currently located.

Next, for each of the survey points used, error module 216 of transmitter identification module 212 generates an error for each of the survey points based on the sorted and de-biased pseudoranges and the sorted and de-biased ranges for that survey point (step 408). In some embodiments, the error for each survey point is calculated as a sum of squared errors (SSE) between the pseudoranges and the ranges for that survey point, as shown in equation (1).

SSE s = ∑ i = 2 N ⁢ ⁢ ( ( d s ( i ) - d s ( 1 ) ) - ( τ ^ ( i ) - τ ^ ( 1 ) ) ) 2 ( 1 )

where each {circumflex over (τ)} is a pseudorange determined by pseudorange module 208 based on one of SFN signals 110, each d is a range predetermined between the survey point and an SFN transmitter 104, N is the number of measurements, and the subscript s is an index of the survey points.

Transmitter identification module 212 selects one or more of the survey points based on the error values (step 410). For example, in some embodiments, transmitter identification module 212 simply selects the survey point with the lowest SSE. In other embodiments, transmitter identification module 212 selects multiple survey points with low SSE.

Based on the selected survey point(s), transmitter identification module 212 associates one of SFN transmitters 104 with each of the pseudoranges (step 412). For example, in the case of a single survey point, transmitter identification module 212 matches the pseudoranges with the ranges predetermined for the selected survey point based on their magnitudes. That is, each pseudorange is matched with the range having the value closest to that of the pseudorange. The pseudorange is then associated with the SFN transmitter 104 associated with the matched range, for example using a table such as Table 1 above. Once the pseudoranges are associated with SFN transmitters 104, location module 214 can determine a location of receiver 202 based on the locations of SFN transmitters 104 and the associated pseudoranges (step 414). Receiver position can also be inferred directly from equation (1), because it is likely the receiver is in the location with the lowest SSE.

Other non-SFN radio signals can be used to constrain the search space for process 400 of FIG. 4. These non-SFN signals can include ATSC/NTSC/PAL/SECAM TV signals, GPS, VOR, FM, DME, Loran-C, and the like. An example where the SFN measurements are augmented with two GPS satellite measurements, j and k, is now described. The GPS navigation equations are:
{circumflex over (τ)}_u,GPS^(j)=d_u,GPS^(j)+B^(j)−b_u,GPS+I_u,GPS^(j)+T_u,GPS^(j)+υ_u,GPS^(j)
{circumflex over (τ)}_u,GPS^(k)=d_u,GPS^(k)+B^(k)−b_u,GPS+I_u,GPS^(k)+T_u,GPS^(k)+υ_u,GPS^(k)  (2)

where {circumflex over (τ)} is pseudorange, d is true range, B is GPS clock bias, b is user clock bias, I is ionospheric delay, T is tropospheric delay and υ is noise. After calibrating out the GPS clock bias, the ionospheric and tropospheric delays, a TDOA representation of the equations (2) reads:
{circumflex over (τ)}_u,GPS^(k)−{circumflex over (τ)}_u,GPS^(j)=d_u,GPS^(k)−d_u,GPS^(j)+υ_u,GPS^(k)−υ_u,GPS^(j)  (3)

Equation (3) sets up a constraint region in the space between two hyperboloids, where the base-line thickness corresponds to the measurement uncertainty of the TDOA measurement. The resulting search space is the intersection of the original search space with the hyperboloid slice. Hybrid ranging measurements can be included in the SSE calculation of equation (1) in the following way:

SSE s = ∑ i = 2 N SFN ⁢ ⁢ ( ( d s ( i ) - d s ( 1 ) ) - ( τ ^ SFN ( i ) - τ ^ SFN ( 1 ) ) ) 2 + ∑ j = 1 N HYB ⁢ ∑ k = j + 1 N HYB ⁢ ( ( d s ( k ) - d s ( j ) ) - ( τ ^ HYB ( k ) - τ ^ HYB ( j ) ) ) 2 ( 4 )

The techniques described above for SFN transmitter identification can be validated using the statistical tools described below. Equation (5) is a generalized navigation equation.
τ_u⁽ⁱ⁾=d_u⁽ⁱ⁾+α_u⁽ⁱ⁾+β_u⁽ⁱ⁾  (5)
Where:

τ is the measured quantity

d is the true quantity, for example range

α is a random error ˜N(0,σ²)

β is a bias

The sum of squared errors (SSE) from equation 5 is given by equation (6).

R u 2 = ∑ i = 1 N ⁢ ⁢ ( τ u ( i ) - d u ( i ) ) 2 R u 2 = ∑ i = 1 N ⁢ ⁢ ( α u ( i ) - β u ( i ) ) 2 ( 6 )

Equation (7) gives the probability that the SSE at the true location (that is, the actual location of user terminal 102) is larger than that at a test point (that is, a survey point) in the search space. A small probability indicates that there is a small probability that ambiguous “truth” positions exist.

P ⁡ ( R grid 2 ≤ R true 2 ) = ⁢ P ⁡ ( ∑ i = 1 # ⁢ DVB g ⁢ ( α g ( i ) + β g ( i ) ) 2 ≤ ∑ j = 1 # ⁢ DVB t ⁢ ( α t ( j ) ) 2 ) = ⁢ P ⁡ ( ∑ i = 1 # ⁢ DVB g ⁢ ( ( α g ( i ) ) 2 + 2 · α g ( i ) · β g ( i ) + ( β g ( i ) ) 2 ) ≤ ∑ j = 1 # ⁢ DVB t ⁢ ( α t ( j ) ) 2 ) = ⁢ P ( ∑ i = 1 # ⁢ DVB g ⁢ ( α g ( i ) ) 2 - ∑ j = 1 # ⁢ DVB t ⁢ ( α t ( j ) ) 2 + 2 · ∑ i = 1 # ⁢ DVB g ⁢ α g ( i ) · ⁢ β g ( i ) ≤ - ∑ i = 1 # ⁢ DVB g ⁢ ( β g ( i ) ) 2 ) = ⁢ P ( ∑ j = 1 # ⁢ DVB t ⁢ ( α t ( j ) σ ) 2 - ∑ i = 1 # ⁢ DVB g ⁢ ( α g ( i ) σ ) 2 - 2 · ⁢ ∑ i = 1 # ⁢ DVB g ⁢ α g ( i ) · β g ( i ) σ 2 ≥ ∑ i = 1 # ⁢ DVB g ⁢ ( β g ( i ) σ ) 2 ) = ⁢ 1 - P ( ∑ j = 1 # ⁢ DVB t ⁢ ( α t ( j ) σ ) 2 - ∑ i = 1 # ⁢ DVB g ⁢ ( α g ( i ) σ ) 2 - 2 · ⁢ ∑ i = 1 # ⁢ DVB g ⁢ α g ( i ) · β g ( i ) σ 2 ≤ ∑ i = 1 # ⁢ DVB g ⁢ ( β g ( i ) σ ) 2 ) ( 7 )

All α's are assumed to be independent of each other and identically Gaussian distributed N(0,σ²). β's are residuals between the arrivals at the true location and the arrivals at the test points in the search grid. Equation (8) breaks out and re-names the left-hand terms inside the probability in equation (7).

X = ∑ j = 1 # ⁢ DVB t ⁢ ( α t ( j ) σ ) 2 ∼ χ # ⁢ DVB t 2 Y = ∑ i = 1 # ⁢ DVB g ⁢ ( α g ( i ) σ ) 2 ∼ χ # ⁢ DVB g 2 Z = 2 · ∑ i = 1 # ⁢ DVB g ⁢ α g ( i ) · β g ( i ) σ 2 ∼ N ⁡ ( 0 , 4 · ∑ i = 1 # ⁢ DVB g ⁢ ( β g ( i ) σ ) 2 ) ( 8 )

While X and Y in equation (8) are Chi-square distributed, Z is normal distributed. The right-hand term inside the probability of equation (4) is identified as a constant.

The set of variables {X,Y,Z} can be re-arranged into another set of variables {V,W,X}.
W=X−Y−Z
V=Y+Z
W=X−V  (9)

Using equations (7)-(9) yields:

P ⁡ ( R g 2 ≤ R t 2 ) = 1 - P ⁡ ( X - Y - Z ≤ w ) = 1 - P ⁡ ( W ≤ w ) = 1 - P ⁡ ( X - V ≤ w ) ( 10 )

From equation (10) and the definition of conditional probability, it follows that

P ⁡ ( X - V ≤ w ) = ∫ - ∞ ∞ ⁢ P ⁡ ( X - V ≤ w | X = x ) · f X ⁡ ( x ) · ⁢ ∂ x = ∫ - ∞ ∞ ⁢ P ⁡ ( x - V ≤ w ) · f X ⁡ ( x ) · ⁢ ∂ x = ∫ - ∞ ∞ ⁢ P ⁡ ( - V ≤ w - x ) · f X ⁡ ( x ) · ⁢ ∂ x = ∫ - ∞ ∞ ⁢ P ⁡ ( V ≥ x - w ) · f X ⁡ ( x ) · ⁢ ∂ x = ∫ - ∞ ∞ ⁢ ( 1 - P ⁡ ( V ≤ x - w ) ) · f X ⁡ ( x ) · ⁢ ∂ x = ∫ - ∞ ∞ ⁢ f X ⁡ ( x ) · ⁢ ∂ x - ∫ - ∞ ∞ ⁢ P ⁡ ( V ≤ x - w ) · f X ⁡ ( x ) · ⁢ ∂ x = 1 - ∫ - ∞ ∞ ⁢ F V ⁡ ( x - w ) · f X ⁡ ( x ) · ⁢ ∂ x ( 11 )

F_V is the cumulative distribution function (CDF) of the random variable V. This CDF can be found as a function of the CDF and probability density function (PDF) of random variables Y and Z from a similar deduction to the one of equation (11). f_X is the PDF of the random variable X.

Combining equations (10) and (11) yields

P ⁡ ( R g 2 ≤ R t 2 ) = 1 - F W ⁡ ( w ) = 1 - ( 1 - ∫ - ∞ ∞ ⁢ F V ⁡ ( x - w ) · f X ⁡ ( x ) · ⁢ ∂ x ) = ∫ - ∞ ∞ ⁢ F V ⁡ ( x - w ) · f X ⁡ ( x ) · ⁢ ∂ x ( 12 )

While there may be no analytical solution to the integral of equation (11), the probability of equation (9) can be calculated numerically with knowledge of PDFs and CDFs of Gaussian and Chi-square distributions.

Note that the above method makes no distinction between SFN measurements and other navigation measurements. As long as the fundamental measurement adheres to the format of equation (5), any hybrid measurement source may be used.

Embodiments of the invention can be implemented in digital electronic circuitry, or in computer hardware, firmware, software, or in combinations of them. Apparatus of the invention can be implemented in a computer program product tangibly embodied in a machine-readable storage device for execution by a programmable processor; and method steps of the invention can be performed by a programmable processor executing a program of instructions to perform functions of the invention by operating on input data and generating output. The invention can be implemented advantageously in one or more computer programs that are executable on a programmable system including at least one programmable processor coupled to receive data and instructions from, and to transmit data and instructions to, a data storage system, at least one input device, and at least one output device. Each computer program can be implemented in a high-level procedural or object-oriented programming language, or in assembly or machine language if desired; and in any case, the language can be a compiled or interpreted language. Suitable processors include, by way of example, both general and special purpose microprocessors. Generally, a processor will receive instructions and data from a read-only memory and/or a random access memory. Generally, a computer will include one or more mass storage devices for storing data files; such devices include magnetic disks, such as internal hard disks and removable disks; magneto-optical disks; and optical disks. Storage devices suitable for tangibly embodying computer program instructions and data include all forms of non-volatile memory, including by way of example semiconductor memory devices, such as EPROM, EEPROM, and flash memory devices; magnetic disks such as internal hard disks and removable disks; magneto-optical disks; and CD-ROM disks. Any of the foregoing can be supplemented by, or incorporated in, ASICs (application-specific integrated circuits).

A number of implementations of the invention have been described. Nevertheless, it will be understood that various modifications may be made without departing from the spirit and scope of the invention. Accordingly, other implementations are within the scope of the following claims.