DEMODULATING MODULATED SIGNALS

Abstract

An apparatus for demodulating a frequency-modulated signal comprises a joint frequency-offset & modulation-index estimator, and a signal demodulator. The joint estimator receives data representative of a preamble portion of the signal, modulated with predetermined preamble data. It jointly determines a frequency-offset estimate and a modulation-index estimate by using an optimization process that minimizes a cost function that is a function of the received data and that is parameterised by a frequency-offset parameter and by a modulation-index parameter. The signal demodulator receives data representative of a message portion of the signal, modulated with message data, and uses the frequency-offset estimate to demodulate the message.

Claims

1. An apparatus for demodulating a frequency-modulated signal, the apparatus comprising: a joint frequency-offset and modulation-index estimator; and a signal demodulator, wherein the joint frequency-offset and modulation-index estimator is configured to: receive data representative of a preamble portion of the frequency-modulated signal, wherein the preamble portion is modulated with predetermined preamble data; and jointly determining a frequency-offset estimate and a modulation-index estimate by using the received data to perform an optimization process, wherein the optimization process minimizes a cost function that is a function of the received data and that is parameterised by a frequency-offset parameter and by a modulation-index parameter, and wherein the signal demodulator is configured to: receive data representative of a message portion of the frequency-modulated signal, wherein the message portion is modulated with message data; and use the frequency-offset estimate to demodulate the message.

2. The apparatus of claim 1, wherein the signal demodulator is configured to use the modulation-index estimate, as well as the frequency-offset estimate, when demodulating the message portion.

3. The apparatus of claim 1, wherein the data representative of the preamble portion comprise a sequence of complex sample values, and wherein the joint frequency-offset and modulation-index estimator is configured to calculate a phase angle for each of the complex sample values, for performing the optimization process in a phase domain.

4. The apparatus of claim 1, wherein the cost function is a least-squares cost function.

5. The apparatus of claim 1, configured to store or access stored data relating to the predetermined preamble data, wherein the cost function is a function of both the stored data and the received data, and wherein the joint frequency-offset and modulation-index estimator is configured to use the stored data when performing the optimization process.

6. The apparatus of claim 5, wherein the stored data represents a sequence, of a function of a sequence, of accumulated phase offsets for a signal modulated with the predetermined preamble data.

7. The apparatus of claim 5, wherein the stored data encodes a matrix that is a function of one or more matrices, wherein at least one of the matrices has a row or column containing a series of accumulated phase-offset values that are dependent on the predetermined preamble data.

8. The apparatus of claim 1, wherein the cost function is further parameterised by a phase-unwrapping parameter and wherein the joint frequency-offset and modulation-index estimator is configured to minimize the cost function over the phase-unwrapping parameter.

9. The apparatus of claim 8, wherein the joint frequency-offset and modulation-index estimator is configured to keep the frequency-offset parameter constant when performing the optimization process, and is further configured to determine the frequency-offset estimate by back-substitution after determining an optimal value for the phase-unwrapping parameter using the optimization process.

10. The apparatus of claim 9, wherein the joint frequency-offset and modulation-index estimator comprises a frequency estimator configured to determine a first estimate of the frequency offset; and is configured to perform the optimization process with the frequency-offset parameter set to the first estimate, or is configured to use the first estimate to apply frequency-offset compensation to the data representative of the preamble portion and to perform the optimization process with the frequency-offset parameter set to zero.

11. The apparatus of claim 8, wherein the joint frequency-offset and modulation-index estimator is configured to keep the modulation-index parameter constant during the optimization process, and is further configured to determine the modulation-index estimate by back-substitution after determining an optimal value for the phase-unwrapping parameter.

12. The apparatus of claim 1, wherein the joint frequency-offset and modulation-index estimator is configured to determine the frequency-offset estimate and the modulation-index estimate by performing the optimization process a plurality of times, with the frequency-offset parameter and the modulation-index parameter set to a different pair of constant values each time, and to determine a pair of the pairs of constant values that resulted in a lowest minimum cost for the cost function.

13. The apparatus of claim 1, wherein the joint frequency-offset and modulation-index estimator is configured to minimize the cost function by performing a closest-lattice-point search to identify a closest point in a lattice.

14. The apparatus of claim 13, wherein the joint frequency-offset and modulation-index estimator is configured to search for a closest point over the lattice An*, for an integer n, using an algorithm having O(N) complexity.

15. The apparatus of claim 1, wherein the frequency-modulated signal is a radio signal and wherein the apparatus comprises a radio receiver for receiving the modulated radio signal and for generating the data representative of the preamble and message portions.

16. The apparatus of claim 1, wherein the frequency-modulated signal is a Gaussian frequency-shift-key (GFSK) modulated signal.

17. The apparatus of claim 1, wherein the frequency-modulated signal is modulated with constant amplitude.

18. A method of demodulating a frequency-modulated signal, the method comprising: receiving data representative of a preamble portion of the frequency-modulated signal, wherein the preamble portion is modulated with predetermined preamble data; jointly determining a frequency-offset estimate and a modulation-index estimate by using the received data to perform an optimization process, wherein the optimization process minimizes a cost function that is a function of the received data and that is parameterised by a frequency-offset parameter and by a modulation-index parameter; receiving data representative of a message portion of the frequency-modulated signal, wherein the message portion is modulated with message data; and using the frequency-offset estimate when demodulating the message portion.

19. The method of claim 18, wherein the frequency-modulated signal is a Gaussian frequency-shift-key (GFSK) modulated signal.

20. The method of claim 18, wherein the frequency-modulated signal is modulated with constant amplitude.

Description

BRIEF DESCRIPTION OF THE DRAWINGS

[0052] Certain preferred embodiments of the invention will now be described, by way of example only, with reference to the accompanying drawings, in which:

[0053] FIG. 1 is a schematic drawing of a radio communication system including a radio receiver embodying the invention;

[0054] FIG. 2 is a schematic drawing of functional units within the receiver circuitry of the radio receiver of FIG. 1; and

[0055] FIG. 3 is a flow chart of operations performed by the receiver circuitry of the radio receiver of FIG. 1.

DETAILED DESCRIPTION

[0056] FIG. 1 shows a radio transmitter device 1 which is in communication with a radio receiver device 15. The radio receiver device 15 embodies the present invention.

[0057] The radio transmitter device 1 has a sensor 3 (e.g. a temperature sensor) which is connected to a system-on-chip (SoC) 5. The SoC 5 comprises radio transceiver circuitry 7 and a microprocessor 9, such as an ARM™ Cortex M-series processor, for executing software stored in a memory 11. The device 1 may also contain other components, such as a battery, crystal oscillator, discrete components, etc., which are omitted from the FIG. 1 for simplicity. The radio transceiver circuitry 7 is connected to a radio antenna 13, for transmitting and receiving radio signals.

[0058] The radio receiver device 15 has a system-on-chip (SoC) 17, comprising radio transceiver circuitry 19, a microprocessor 21, such as an ARM™ Cortex M-series processor, and a memory 23 for storing software to be executed by the microprocessor 21. The radio transceiver circuitry 19 is connected to an antenna 25 for receiving and transmitting radio signals. The SoC 17 is connected to an output peripheral 27, such as a display screen, for outputting a response which may be based, at least in part, on data received by the radio transceiver circuitry 19 through the antenna 25. The receiver device 15 may contain other components (not shown), such as a battery, crystal oscillator, discrete components, further microprocessors, etc.

[0059] In use, the radio transmitter device 1 transmits data packets from the antenna 13, modulated on a radio-frequency carrier (e.g. at around 2.4 GHz), using two-level GFSK with a modulation index h. (The modulation index h is the difference between the two frequencies in the two-level FSK signal, divided by the bitrate of the encoded data stream.) The data packet comprises a predetermined synchronization sequence and a message-data portion. It may also include one or more of address data, a link-layer identifier, packet-length data, and any other appropriate elements. A preamble portion of the packet, for the purposes of the cross-correlations described below, may comprise some or all of the synchronization sequence and/or some or all of the address or link-layer data. The radio receiver device 15 is configured to receive, demodulate (i.e. detect) and decode such data packets. It may also transmit similar data packets. The data packets may comply with some or all parts of a version of the Bluetooth Low Energy (BLE)™ core specification, e.g. Bluetooth™ 5. The radio receiver device 15 may be a BLE receiver.

[0060] The radio transceiver circuitry 19 in the radio receiver device 15 uses a matched filter bank (MFB) to implement non-coherent detection (i.e. non-coherent demodulation) of incoming data. The MFB may observe a number, K, of bits at a time. This observation interval could be K = 3, 5 or 7 bits long, or any other suitable length.

[0061] The radio transceiver circuitry 19 uses a clock reference (e.g. derived from a quartz crystal in the receiver device 15) to demodulate incoming signals. This clock reference is intended to match a clock reference used by the transceiver circuitry 7 in the transmitter device 1. However, there will typically some mismatch in these clock references, resulting in a frequency offset between an expected frequency of the incoming signal received at the antenna 25 of the receiver device 15 and the actual incoming frequency. This offset may change during the transmission of a data packet-e.g. due to clock drift at the transmitter 1 or receiver 15, or due to changing channel conditions such as relative motion between the transmitter 1 and the receiver 15 (e.g. Doppler shift).

[0062] The receiver device 15 can determine an preamble-based frequency offset estimate, as described in more detail below. It can also periodically generate updated estimates of the frequency offset, while receiving message data, in order to improve the accuracy of the demodulation.

[0063] The modulation index h is the difference between the two FSK frequencies, divided by the bitrate of the encoded data stream. In order to demodulate a received data packet accurately, the receiver 15 needs to have an accurate estimate of the modulation index used by the transmitter 1. However, the exact modulation index may not be known to the receiver 15. In some situations, the transmitter 1 may be able to use any modulation index within a range of values—e.g. in the range [0.45, 0.55]. The modulation index it uses may also change over time.

[0064] If the receiver 15 does not have an accurate estimate h of the actual modulation index h, the sensitivity of the receiver 15 can be reduced. This is because a phase error can accumulate over an observation interval, thereby affecting detector performance. If ĥ is inaccurate by 0.05, for example, this can result in a potential phase offset in the received signal of +/-0.05.K.Π, which equals π/4 for K=5. For a K=5 detector, the performance loss may be of the order of 0.7 dB loss for BLE at 1Mbps data rate, and may be even greater for some other radio protocols.

[0065] This problem is mitigated in embodiments described herein, in which the receiver 15 uses a novel approach to jointly estimate a modulation index offset and a frequency offset. The estimated modulation index may then be used to improve the accuracy of the demodulation of later parts of the received signal-e.g. by adjusting the coefficients in the MFB 37 according to the estimated modulation index.

[0066] FIG. 2 shows various functional blocks provided by the system-on-chip (SoC) 17 that are used in demodulating an incoming two-level CP-FSK encoded radio signal. In other embodiments, different types of modulation may be used. Each of these blocks may be implemented using dedicated circuitry in the radio transceiver circuitry 19— e.g. as blocks comprising application-specific registers and logic gates. However, in some embodiments, one or more operations of one or more blocks may be implemented by software, e.g. executing on the microprocessor 21. A pure software implementation is possible, but may be undesirable for performance reasons.

[0067] The radio transceiver circuitry 19 may use any combination of amplifiers, mixers, filters, analogue-to-digital converters, etc. to generate a sampled radio signal, from a received analogue radio signal, comprising a sequence of complex-valued digital samples, l & Q, at baseband. These samples represent the radio signals received around a particular carrier frequency-e.g. in a band within the 2.4 GHz spectrum. The signal may be oversampled by a factor R. In some examples, R = 8, although it could take any suitable value.

[0068] The principal signal path for payload message data, through the components of FIG. 2, is shown using solid arrows, while control, calibration and feedback paths are shown using dashed arrows.

[0069] The stream of complex baseband samples is input to each of a frequency correction block 31, a preamble correlator 33, and a joint frequency-offset and modulation index estimator 34 (also referred to herein as a “joint estimator” for short).

[0070] The preamble correlator 33 detects the presence of a relevant data packet. The preamble correlator 33 performs timing recovery and frame synchronization, to enable the receiver 15 to demodulate the signal more accurately. It does this by cross-correlating the incoming samples against a stored template. The template comprises a sequence of (complex) coefficients that represents the modulated baseband waveform of a fixed preamble that is included in each data packet intended for the receiver 15.

[0071] The preamble may comprise part or all of a constant synchronization sequence that is present in every data packet within the system, and/or part or all of an address of the receiver 15 and/or part or all of a channel or link identifier and/or any other appropriate data. When receiving BLE data packets, the preamble correlator 33 may, for example, use 16-bit preamble sequences, consisting of the last two bits of the BLE Preamble field and the first fourteen bits of the Address field. The preamble used by the correlator may, at least for some packets, precede message data encoded in the data packet.

[0072] Symbol and frame (i.e. packet) timing information determined by the preamble correlator 33 is output to the frequency correction block 31, as well as to other modules that require it. The frequency correction block 31 performs complex rotation of the samples to compensate for any frequency offset, based on frequency-offset estimate information received from the joint estimator 34, and also received from a separate frequency offset estimator 35. The frequency correction block 31 may comprise one or more CORDIC circuits for performing the complex rotation.

[0073] The joint estimator 34 is described in greater detail below. It uses the fixed preamble to generate a preamble-based frequency offset estimate (e.g. arising from an offset between an oscillator of the receiver 15 and an oscillator of the transmitter 1) and a modulation index estimate. The modulation index estimate may be expressed as an offset from a nominal modulation index expected by the receiver-e.g. as an offset from h.sub.0 = 0.5. The preamble-based frequency offset estimate may be subsequently refined or superseded by the output of the frequency estimator 35 which determines further frequency offset estimates periodically, as the payload message data portion of the data packet is demodulated.

[0074] The joint estimator 34 provides the modulation index to a matched filter bank (MFB) 37, where it is used to adjust the correlation coefficients, and to the frequency estimator 35. The matched filter bank (MFB) 37 and the frequency estimator 35 also receive timing information from the preamble correlator 33.

[0075] The matched filter bank 37 receives the stream of frequency-corrected samples from the frequency correction block 31. It applies a set of filters, each K bits long, to the incoming samples. In FIG. 2, K = 5, but K could be 3, 4, 7, 11 or any other length. Each filter of the MFB 37 performs a complex cross-correlation between the sampled signal and a respective filter sequence of coefficients that represents a baseband waveform modulated according to a respective bit pattern. The MFB 37 uses the modulation index estimate, ĥ.sub.TX, received from the joint estimator 34 to select appropriate filter sequence coefficients.

[0076] At each time step, the matched filter bank 37 generates a set of 2.sup.K complex correlation coefficients, one for each filter in the selected set, representing the degree of correlation between a window of the incoming samples and the respective template. The MFB 37 computes a real-valued modulus of each coefficient and outputs these as a set of 2.sup.K correlation strength values to a decision unit 39. In some embodiments, the MFB 37 may be implemented similarly to the MFB disclosed in the applicant’s earlier application WO 2019/134947, the entire contents of which are hereby incorporated by reference, with the modulation index h being determined from the estimate output by the joint estimator 34.

[0077] The decision unit 39 receives this correlation-strength data and processes it to generate a sequence of detected hard bits (i.e. 0 or 1 values). This processing may be similar or the same as that described for the decision unit in the applicant’s earlier application WO 2019/207009, the entire contents of which are hereby incorporated by reference. In other embodiments, the MFB output may be processed using majority voting principles as disclosed in WO 2014/167318. In some embodiments, the decision unit 39 may comprise a Viterbi decoder. The decision unit 39 outputs a demodulated bit value at each bit period. The value of each demodulated bit may be determined from the outputs of the MFB 37 at K different symbol (bit) periods, since the same bit position is considered K times at K different bit positions within the filter sequences.

[0078] In some embodiments, the detected bits are fed back to the MFB 37 along a feedback path 41. In such embodiments, these bits may be used by the MFB 37 to help refine the filter sequences that the MFB 37 cross-correlates with the received samples-e.g. as described in WO 2019/207009.

[0079] The complex correlation coefficients from the matched filter bank 37 are also sent to the frequency estimator 35, while the data packet is demodulated. The frequency estimator 35 uses them to detect on-going frequency drift, subsequent to the preamble-based frequency offset estimated by the joint estimator 34. Such drift, if not corrected for, may negatively impact the performance of the demodulation. Estimates of frequency drift are used to send control signals to the frequency correction block 31.

[0080] The demodulated bit stream, output by the decision unit 39, may be stored in the memory 23 and/or may be processed further by the radio receiver 15 or by some other device, as appropriate. It may, in some applications, determine an output from the peripheral 27-e.g. decoded data from a variable message portion of a data packet may control what is displayed on a display screen of the receiver device 15.

[0081] FIG. 3 is a flow chart which summarises some of the key operations that are performed by the SoC 17 when demodulating a data packet, with a focus on the novel joint frequency offset and modulation index estimation process.

[0082] A physical radio signal is received 301 and sampled 303. Earlier samples are processed as later samples are still being received. The incoming samples are cross-correlated 305 with a set of one or more templates by the preamble correlator 33 to detect a preamble portion of the received packet, and to determine bit-level and frame-level synchronization.

[0083] The joint estimator 34 determines 307 initial values for estimates of the frequency offset and of the modulation index offset (i.e. as an offset from a preconfigured default modulation index value). In some embodiments, these initial offset value are simply both set to zero; in other embodiments, a plurality of different values are used; while in further embodiments, the modulation index offset is set to zero and a correlator is used to determine a crude frequency offset estimate, which may determine an initial frequency offset value or which may be used to perform an initial rotation of the incoming samples.

[0084] The initial offset values are then used by the joint estimator 34 to jointly determine 311 a modulation index offset estimate and a preamble-based frequency offset estimate by solving one or more least-squares minimization problems, holding the initial offset values as constants. The minimization process is implemented in the joint estimator 34 as a lattice point search.

[0085] The frequency correction block 31 uses the preamble-based (and any subsequent) frequency offset estimate to apply 313 frequency correction by rotating the incoming samples by a corresponding amount, to compensate for the frequency offset.

[0086] The MFB 37 is used, in conjunction with decision circuitry 39, to demodulate 313 a message portion of the data packet. The frequency offset estimator 35 calculates 315 updated estimates of the frequency offset based on the output of the MFB 37 as the message portion is decoded. These are fed back to the frequency correction block 31 which uses the updated estimates to apply 313 frequency correction to subsequent incoming samples.

[0087] The process is repeated at every incoming sample until the end of the data packet.

[0088] More details of the operation and implementation of the joint estimator 34 are provided below.

System Model

[0089] A frequency shift keying (FSK) signal with modulation index h and oversampling ratio R, can be defined as

[00001]$\begin{array}{cc}{x}_{nR+r}=x_{nR}\exp \left\{j\pi h{\beta }_n\frac{r}{R}\right\}& \text{­­­(1)}\end{array}$

[00002]$\begin{array}{cc}=\sqrt{P_x}\exp \left\{j\pi h\left({\beta }_k\frac{r}{R}+{\displaystyle \underset{l=1}{\overset{n-1}{.Math.}}{\beta }_l}\right)\right\}& \text{­­­(2)}\end{array}$

where: [0090] x.sub.k is the transmitted signal at sample time k = nR + r, [0091] n is the number of bits that have been sent within a data packet; [0092] r ∈ [0, R-1] indexes the samples within each bit; [0093] j = √-1; [0094] h is the modulation index; [0095] β.sub.n = 2.b.sub.n - 1 is the sign of the instantaneous phase shift corresponding to bit b.sub.n which is the nth bit of the data packet (i.e. with values in {-1, 1}, instead of {0,1}); and [0096] P.sub.x is the power at x.sub.0.

[0097] The summand inside the exponential represents the accumulated phase offset of all the bits leading up to the current bit, accumulated over the whole stream thus far-i.e. from the first bit (I = 0) of the data packet up to and including the bit (I = n-1) that immediately precedes the current bit (n).

[0098] In some cases, the transmitted signal may employ pulse-shaping, such as Gaussian filtering. In such cases this model is only approximate; however, it can still be possible for the coefficients of the MFB 37 to be based on this model and successfully demodulate such a signal.

[0099] The received signal is given by

[00003]$\begin{array}{cc}{y}_{nR+r}=x_{nR+r}\exp \left\{j\left(\theta +2\pi {\Delta }_f\left(n+\frac{r}{R}\right)\right)\right\}+v_{nR+r}& \text{­­­(3)}\end{array}$

where: [0100] y.sub.k is the received signal at sample time k = nR + r, [0101] x.sub.k is the transmitted signal at sample time k = nR + r, [0102] θ is a constant phase offset due to the channel; [0103] Δ.sub.f is a constant frequency offset between the transmitter 1 and the receiver 15; and [0104] v.sub.k is zero-mean complex additive white complex Gaussian noise (AWGN).

[0105] The MFB 37 demodulates data from such a received signal by non-coherently correlating the sampled radio signal with 2.sup.K filters that have coefficients corresponding to the modulated signal for all possible K-bit sequences.

[0106] The following definition, representing the accumulated phase over the transmitted data packet up to a sample nR+r, will be useful in the explanation below:

[00004]$s_{nR+r}\triangleq {\beta }_k\frac{r}{R}+{\displaystyle \underset{l=1}{\overset{n-1}{.Math.}}{\beta }_l}$

[0107] The first term represents the phase offsets across the r samples of the current bit, while the summand accumulates the phase offset due to all the received bits that precede the current bit.

Joint Frequency and Modulation Index Estimation

[0108] The joint estimator 34 implements a method to perform joint modulation index and frequency offset estimation on a known transmitted FSK signal (e.g. a predetermined preamble portion of a data packet), using phase unwrapping and a nearest-point lattice algorithm.

[0109] Several variant embodiments are described below, some of which use suboptimal but lower-complexity variations of the main algorithm.

Phase-Domain Representation of System Model

[0110] The algorithms described below are implemented in the phase domain within the joint estimator 34.

[0111] Define z.sub.nR+r as a version of the transmitted signal in equation (1) with the nominal expected modulation index h.sub.0:

[00005]$\begin{array}{cc}{z}_{nR+r}=z_{nR}\exp \left\{j\pi h_0{\beta }_n\frac{r}{R}\right\}& \text{­­­(4)}\end{array}$

[00006]$\begin{array}{cc}=\sqrt{P_x}\exp \left\{j\pi h_0\left({\beta }_k\frac{r}{R}+{\displaystyle \underset{l=1}{\overset{n-1}{.Math.}}{\beta }_l}\right)\right\}& \text{­­­(5)}\end{array}$

[0112] For a fixed preamble portion, the values of z.sub.nR+r are constants that are known in advance of receiving the data packet.

[0113] Considering the phases of the system model in eq. (3), it can be seen that

[00007]$\begin{array}{cc}\angle y_k={\left[\angle x_k+\theta +2\pi {\delta }_f+{\eta }_k\right]}_{\mathrm{mod}2\pi }& \text{­­­(6)}\end{array}$

where: [0114] ∠ denotes the angle of the complex argument; [0115] [.].sub.mod .sub.2π is a modulo operation with the range [0; 2π); [0116] δ.sub.f ≜ Δ.sub.f/R represents a frequency offset error at the receiver, which it is desired to estimate; and [0117] η.sub.k is a noise term due to applying the angle operation to the received signal affected by v.sub.nR+r.

[0118] Now, define

[00008]${\gamma }_k=\angle y_k{z}_k^{\ast }/\left(2\pi \right),\text{and}\varphi =\theta /\left(2\pi \right)$

It follows that

[00009]$\begin{array}{cc}{\gamma }_k={\left[{\delta }_h{s}_k+\varphi +{\delta }_f\frac{k}{R}+{\eta }_k\right]}_{\mathrm{mod}1}& \text{­­­(7)}\end{array}$

where δ.sub.h ≜ h - h.sub.0 represents a modulation index error at the receiver, which it is desired to estimate.

[0119] Note that the s.sub.k are predetermined, corresponding to the fixed preamble portion as transmitted by the transmitter 1, whereas the γ.sub.k can be determined from the complex I & Q samples, y.sub.k, by a correlator in the joint estimator 34, which cross-correlates the received samples, y.sub.k, with stored coefficients representative of the transmitted preamble, z.sub.k. If the joint estimator 34 receives timing information from the preamble correlator 33, it may not need to perform a sliding cross-correlation operation, but may instead just perform a vector dot product operation since the samples are already aligned.

[0120] In vector form, collating N symbols (and therefore n = NR samples):

[00010]$\begin{array}{cc}\gamma =\left[{\delta }_h\text{s+}\varphi \text{1+}{\delta }_f\text{n+}\eta \right]{}_{\mathrm{mod}1}& \text{­­­(8)}\end{array}$

where

[00011]$\gamma =\left[{\gamma }_1{\gamma }_2.Math.{\gamma }_{\text{NR}}\right]\prime ,$

[00012]$S=\left[S_1{S}_{2.Math.}{S}_{NR}\right]\prime ,$

1 is the column vector of all ones,

[00013]$\text{n}=\left[12.Math.NR\right]\prime ,\text{and}$

[00014]$\eta =\left[{\eta }_1{\eta }_{2.Math.}{\eta }_{NR}\right]\prime .$

Connection to Closest Lattice Point Search

[0121] The joint estimator 34 is designed to find estimates for the unknown parameters δ.sub.h, δ.sub.f and θ using a least squares approach, based on the incoming I & Q samples of a preamble portion of the data packets.

[0122] Note that the effect of the modulo operation implies that there exists an integer vector a ∈ ℤ such that:

[00015]$\begin{array}{cc}\gamma ={\delta }_h\text{s+}\varphi \text{1+}{\delta }_f\text{n}+\eta -\text{a}& \text{­­­(9)}\end{array}$

where the elements of a represent the numbers of times the phase has wrapped.

[0123] In fact, a vector a ∈ ℤ can be chosen that minimizes the least-squares distance on the unit circle between γ and the noise-free signal, i.e. that minimizes the cost function

[00016]$\begin{array}{cc}\text{Λ}\left(\gamma \left|\varphi ,{\delta }_h,{\delta }_f,\text{a}\right)\right)\triangleq \underset{{\delta }_h\in \text{R}}{\min }\underset{{\delta }_f\in \text{R}}{\min }\underset{\varphi \in \left[0,1\right)}{\min }\underset{\text{a}\in {\mathbb{Z}}^N}{\min }{‖{\delta }_h\text{s}+\varphi 1+{\delta }_f\text{n}-\left(\gamma +\text{a}\right)‖}^2& \text{­­­(10)}\end{array}$

[0124] A minimization over a ∈ ℤ.sup.N determines the optimal phase unwrapping. For simplicity the metric will hereafter be denoted simply as:

[00017]$\text{Λ}\triangleq \text{Λ}\left(\gamma \left|\varphi ,{\delta }_h,{\delta }_f,\text{a}\right)\right).$

[0125] The metric Λ can be thought of as a type of suboptimal log-likelihood function. The vector of parameters can be denoted as:

[00018]$\begin{array}{cc}\text{M}=\left[\text{s}1\text{n}\right]& \text{­­­(11)}\end{array}$

[0126] The metric Λ then becomes

[00019]$\begin{array}{cc}\text{Λ}\triangleq \underset{{\delta }_h\in \text{R}}{\min }\underset{{\delta }_f\in \text{R}}{\min }\underset{\varphi \in \left[0,1\right)}{\min }\underset{\text{a}\in {\mathbb{Z}}^N}{\min }{‖\text{M}{\left[{\delta }_h\varphi {\delta }_f\right]}^{\prime }-\left(\gamma +\text{a}\right)‖}^2& \text{­­­(12)}\end{array}$

where [.]’ denotes matrix transpose.

[0127] The optimization problem then becomes to minimize the cost function:

[00020]$\begin{array}{cc}\text{Λ}\triangleq \underset{{\delta }_h\in \text{R}}{\min }\underset{{\delta }_f\in \text{R}}{\min }\underset{\varphi \in \left[0,1\right)}{\min }\underset{a\in {\mathbb{Z}}^N}{\min }{‖\left(\text{M}{\left({\text{M}}^{\prime }\text{M}\right)}^{-1}{\text{M}}^{\prime }-\text{I}\right)\left(\gamma +\text{a}\right)‖}^2& \text{­­­(13)}\end{array}$

where I is the identity matrix of dimension NR.

[0128] Once the joint estimator 34 has found a solution â to eq. (13), it uses this to compute the unknown parameters according to:

[00021]$\begin{array}{cc}{\left[{\widehat{\delta }}_h\widehat{\varphi }{\widehat{\delta }}_f\right]}^{\prime }={\left({\text{M}}^{\prime }\text{M}\right)}^{-1}{\text{M}}^{\prime }\left(\gamma +\widehat{\text{a}}\right)& \text{­­­(14)}\end{array}$

[0129] In embodiments in which the data used for the joint estimation is known in advance of receiving the data packet-e.g. being a fixed preamble or sync word-the matrix M(M.sup.TM).sup.-1M.sup.T can be calculated before packet reception and stored in a memory for reuse across multiple data packets.

[0130] The search for â is implemented in the joint estimator 34 using an algorithm for searching for a closest lattice point.

[0131] A lattice can be defined as a grid of points that have been generated by applying a transform to the integer grid. Here the transform is specified by a generator matrix. In the general case the nearest lattice point problem can be solved using sphere-decoding and is of complexity O(2.sup.N). Algorithms are known in the context of multiple-input multiple-output (MIMO) decoding and precoding, where the generator matrix generally has random elements resulting in high complexity. Such algorithms could be used in embodiments of the joint estimator 34, but most of these algorithms require some matrix computations, e.g. inverses and reductions, which it may be desirable to avoid using here in the interests of complexity and numerical stability.

[0132] Instead, the joint estimator 34 may solve a simplified problem, in which the dependence on the phase is removed, and in which the problem is changed from an N-dimensional “square” grid search to an N-dimensional “hexagonal” grid search.

[0133] The paper “Frequency Estimation by Phase Unwrapping” by McKilliam et al., IEEE Transactions on Signal Processing, vol. 58, no. 6, pp. 2953-2963, 2010 describes a nearest lattice-point search over a lattice A.sub.n*.

[0134] A general introduction to the A.sub.n* lattice can be found in, for example, “Fast Quantizing and Decoding Algorithms for Lattice Quantizers and Codes” by Conway & Sloane, IEEE Transactions on Information Theory, vol. 28, no. 2, pp. 227-232, 1982.

[0135] The joint estimator 34 may implement an algorithm based on methods disclosed in the McKilliam paper. The McKilliam algorithm has complexity of only O(N) so it can be implemented efficiently compared with generic-case algorithms.

[0136] However, in some embodiments, the joint estimator 34 may implement one or more optimizations, described below, which may trade off optimal performance for reduced complexity.

[0137] The dependence on the unknown channel phase φ can be removed by differentiating Λ(γ|φ, δ.sub.h, δ.sub.f, a) with respect to φ, to obtain the estimate φ̂, assuming the other unknown parameters have been estimated:

[00022]$\begin{array}{cc}\widehat{\varphi }=\frac{1^{\prime }\left(\gamma +\text{a}-{\widehat{\delta }}_h\text{s}-{\widehat{\delta }}_f\text{n}\right)}{1^{\prime }1}& \text{­­­(15)}\end{array}$

[0138] Substituting this back into eq. (10) gives

[00023]$\begin{array}{cc}\text{Λ=}\underset{{\delta }_h\in \text{R}}{\min }\underset{{\delta }_f\in \text{R}}{\min }\underset{\text{a}\in {\mathbb{Z}}^N}{\min }{‖{\delta }_h\tilde{\text{s}}+{\delta }_f\tilde{\text{n}}-\left(\tilde{\gamma }+\tilde{\text{a}}\right)‖}^2& \text{­­­(16)}\end{array}$

where

[00024]$\begin{array}{cc}\tilde{\gamma }\triangleq \gamma -\frac{11^{\prime }}{NR}\gamma =Q_{\overline{\varphi }}\gamma & \text{­­­(17)}\end{array}$

[00025]$Q_{\overline{\varphi }}\triangleq \text{I}-\frac{11^{\prime }}{NR}$

can be considered as a phase-removal transformation. The matrix

[00026]$Q_{\overline{\varnothing }}$

also projects vectors onto the hyperplane where the sum of all elements are zero. The ‘phase-free’ vectors s̃, ñ and ã are defined similarly:

[00027]$\begin{array}{cc}\tilde{\text{s}}\triangleq \text{s}-\frac{11^{\prime }}{NR}\text{s}\text{=}{\text{Q}}_{\overline{\varphi }}\text{s}& \text{­­­(18)}\end{array}$

[00028]$\begin{array}{cc}\tilde{\text{n}}\triangleq \text{n}-\frac{11^{\prime }}{NR}\text{n}=Q_{\overline{\varphi }}\text{n}& \text{­­­(19)}\end{array}$

[00029]$\begin{array}{cc}\tilde{\text{a}}\triangleq \text{a}-\frac{11^{\prime }}{NR}\text{a}=Q_{\overline{\varphi }}\text{a}& \text{­­­(20)}\end{array}$

[00030]$Q_{\overline{\varnothing }}$

is a generator matrix for the well-studied lattice A.sub.n*, which is a regular set on points in ℝ.sup.n. A lattice with generator matrix G is defined as the set of points Gz where z has integer values. The lattice A.sub.n* can be defined in terms of the lattice A.sub.n, which consists of all vectors of integers in ℤ.sub.n+1 whose elements sum to zero. The lattice A.sub.n* consists of A.sub.n, as well as an extra n+1 versions of this set of points, each offset by a different glue vector:

[00031]$\begin{array}{cc}\left[g\right]=\frac{1}{n+1}\left[\underset{\text{n+1-g}\text{times}}{\underbrace{-g,.Math.,-g,}}\underset{\text{g}\text{times}}{\underbrace{n+1-g,.Math.,n+1-g}}\right]& \text{­­­(21)}\end{array}$

where g ∈ {0, 1, ..., n}. The lattices A.sub.2*, A.sub.2 are two-dimensional hexagonal grids lying on the plane in three dimensions where the sum of all elements are zero.

[0139] Therefore the problem can be rewritten as

[00032]$\begin{array}{cc}\text{Λ=}\underset{{\delta }_h\in \text{R}}{\min }\underset{{\delta }_f\in \text{R}}{\min }\underset{\tilde{\text{a}}\in A_{NR-1}^{\ast }}{\min }{‖{\delta }_h\tilde{\text{s}}+{\delta }_f\tilde{\text{n}}-\left(\tilde{\gamma }+\tilde{\text{a}}\right)‖}^2& \text{­­­(22)}\end{array}$

If δ.sub.h, δ.sub.f, are known then ã can be solved using an algorithm for finding the closest lattice point to δ.sub.hs̃+δ.sub.fñ-γ̃.

Closest Lattice Point Algorithm

[0140] Approaches to solving this lattice point search in O(N) complexity are known-see, for example, “A linear-time nearest point algorithm for the lattice A.sub.n*” by McKilliam et al., ISITA, International Symposium on Information Theory and Its Applications, IEEE, pp. 1-5, 2008,

[0141] Given some initial estimates of δ.sub.h and δ.sub.f, the joint estimator 34 can use such an approach to perform a lattice point search.

[0142] This algorithm makes use of a theorem which is described in “An Algorithm to Compute a Nearest Point in the Lattice A.sub.n*” by Vaughan & Clarkson, Applied Algebra, Algebraic Algorithms and Error-Correcting Codes, Springer, 1999, pp. 104-120, and which is used below when describing a lower complexity variant.

Clarkson’s Theorem

[0143] Define

[00033]$\begin{array}{cc}\text{p}\left(\gamma \right)=-Q_{\overline{\varphi }}\left[\gamma \right]& \text{­­­(23)}\end{array}$

[0144] Then the nearest lattice point in A.sub.N-1* to γ is p or p + r where r is a relevant vector.

[0145] A relevant vector r ∈ A.sub.N-1* is a lattice point whose polyhedral Voronoi region (i.e. nearest neighbour region) shares a face with the Voronoi region of the point at the origin, 0. That is, r is a neighbour to 0.

[0146] The algorithm first proceeds by taking [γ] as an initial estimate and then sorting the vector of associated rounding errors i.e. [γ] - γ. The sorting operation is used to successively increment the individual elements of [γ] in a specific order so as to iterate through all the relevant vectors when calculating the metrics. Because the elements being sorted are the indices 1, ..., N, a bucket sort can be employed which has a complexity of only O(N) compared to a sorting algorithm for generic elements which has a complexity of no less than O(N log N). In addition, apart from the initialization, vector operations are avoided.

Implementations

[0147] The algorithm implemented by the joint estimator 34 can be divided into two steps: [0148] step 1: a nearest lattice point search to obtain ã; and [0149] step 2: back-substitution in order to obtain δ.sub.h and δ.sub.f.

[0150] Various different implementations of step 1 are possible, including: [0151] algorithm 1a: a grid search over the tuple (δ.sub.h, δ.sub.f), over a sensible range; [0152] algorithm 1b: a single grid point search over the tuple (δ.sub.h, δ.sub.f) = (0, 0); and [0153] algorithm 1c: assume δ.sub.h=0 and obtain a first estimate of δ.sub.f.

[0154] Additionally, various different implementations of step 2 are possible, including: [0155] algorithm 2a: grid search; [0156] algorithm 2b: full back-substitution; and [0157] algorithm 2c: inverse-free back-substitution.

[0158] These different algorithms will now be described in more detail.

Algorithm 1a: Grid Search

[0159] This algorithm uses one or more trial tuples of (δ.sub.h, δ.sub.f). Note that δ.sub.h and δ.sub.f are, for practical reasons, typically restricted to a predetermined range-for example, due to requirements imposed by a radio communication standard, or the bandwidth of the analog receiver. In some embodiments, these tuples may be drawn from regular points restricted to a specific range, e.g. a square or hexagonal grid. For each trial tuple, a respective lattice point search is performed-e.g. using the McKilliam algorithm mentioned above-and the value of Λ with the minimizing lattice point ã is obtained.

Algorithm 1b: Single Grid Point Search

[0160] A variant that may be useful when receiving signals for which the deviation from the expected values of δ.sub.h and δ.sub.f will be relatively small-e.g. when receiving BLE signals. The BLE specification requires that |δ.sub.h| < 0.05, while the use of clock sources with accuracy of ≤ 50 ppm results in a maximum offset between transmitter and receiver of 2 × 50 ppm x 2.48e9 = 248 kHz, such that |δ.sub.f| < 248e3/1e6 = 0.248. Thus, in some embodiments, the joint estimator 34 performs only a single lattice point search using (δ.sub.h, δ.sub.f) = (0, 0) as an initial estimate.

Algorithm 1c: Suboptimal A.SUB.N-1.* lattice search

[0161] In another variant, instead of performing a search over multiple (δ.sub.h, δ.sub.f), the joint estimator 34 instead sets δ.sub.h = 0 and first performs a frequency correction on the incoming data using a low-complexity coarse frequency estimator. One embodiment uses a Meyr D-spaced estimator, using only N = 4 symbols with a spacing of D = 1, as described on page 488 of “Digital Communication Receivers: Synchronization and Channel Estimation Algorithms” by Meyr et al., ISBN 0-471-50275-8, John Wiley & Sons, 1998. The residual δ.sub.f is typically small. After obtaining a coarse frequency estimate and rotating the incoming samples accordingly, the lattice search is then performed on the compensated samples using initial values of δ.sub.h = δ.sub.f = 0, similarly to algorithm 1b.

[0162] For all these approaches, once the lattice search is complete,

[00034]$Q_{\overline{\varnothing }}\gamma$

is then used as the estimate of ã.

[0163] Simulations have shown that, if the signal-to-noise ratio is sufficiently high, and N, δ.sub.h, δ.sub.f are sufficiently small, and the phase rotation is supplied, then ã is usually given by

[00035]$Q_{\overline{\varnothing }}\left[\text{γ}\right].$

(Note that Clarkson’s Theorem implies that if p(y) is not the optimal solution, then p + g will be, for some glue vector g).

Algorithm 2a: Grid Search

[0164] When using algorithm 1a, the values of δ.sub.h and δ.sub.f in the grid which minimize the value of Λ can be identified and provided as the estimates. This is not useful if only a single grid point is used (algorithms 1b and 1c). If searching over (δ.sub.h, δ.sub.f) and also solving for lattice point ã, the tuple (δ.sub.h, δ.sub.f, ã) that minimizes the metric is identified.

Algorithm 2b: Full Back-substitution

[0165] In some embodiments, the value of ã that minimizes the value of Λ is back-substituted into eq. (14), enabling new estimates of φ.sub.h, δ̂.sub.h and δ̂.sub.f to be obtained.

[0166] Alternatively, by defining M = [ s̃ ñ ] and following similar steps to obtaining eq. (14), the joint estimator 34 may determine

[00036]$\begin{array}{cc}{\left[{\widehat{\text{δ}}}_h{\widehat{\text{δ}}}_f\right]}^{\prime }={\left(\widetilde{{\text{M}}^{\prime }}\tilde{\text{M}}\right)}^{-1}\widetilde{{\text{M}}^{\prime }}\left(\widetilde{\text{γ}}+\widehat{\text{a}}\right)& \text{­­­(24)}\end{array}$

Algorithm 2c: Inverse-free Back-substitution

[0167] An alternative way to obtain the solution in eq. (24) while avoiding the need for the inverse operation is to obtain the phase-free and frequency-free estimates by further differentiating Λ with respect to δ.sub.h and solving:

[00037]$\begin{array}{cc}{\widetilde{\text{γ}}}_h=\widetilde{\text{γ}}-\frac{{\tilde{\text{n}}}^{\prime }\widetilde{\text{γ}}}{{\tilde{\text{n}}}^{\prime }\tilde{\text{n}}}\tilde{\text{n}}& \text{­­­(25)}\end{array}$

[00038]$\begin{array}{cc}{\tilde{\text{s}}}_h=\tilde{\text{s}}-\frac{{\tilde{\text{n}}}^{\prime }\tilde{\text{s}}}{{\tilde{\text{n}}}^{\prime }\tilde{\text{n}}}\tilde{\text{n}}& \text{­­­(26)}\end{array}$

[0168] The modulation index offset estimate is then

[00039]$\begin{array}{cc}{\text{δ}}_h=\frac{{\widetilde{{\text{s}}^{\prime }}}_h{\widetilde{\text{γ}}}_h}{{{\tilde{\text{s}}}^{\prime }}_h{\tilde{\text{s}}}_h}& \text{­­­(27)}\end{array}$

[0169] The joint estimator 34 can then obtain the modulation index-free and frequency-free estimates by further differentiating Λ with respect to δ.sub.f and solving:

[00040]$\begin{array}{cc}{\widetilde{\text{γ}}}_f=\widetilde{\text{γ}}-\frac{\widetilde{{\text{s}}^{\prime }}\widetilde{\text{γ}}}{{\tilde{\text{s}}}^{\prime }\tilde{\text{s}}}\tilde{\text{s}}& \text{­­­(28)}\end{array}$

[00041]$\begin{array}{cc}{\tilde{\text{n}}}_f=\tilde{\text{s}}-\frac{\widetilde{{\text{s}}^{\prime }}\tilde{\text{n}}}{{\tilde{\text{s}}}^{\prime }\tilde{\text{s}}}\tilde{\text{s}}& \text{­­­(29)}\end{array}$

[0170] The frequency offset estimate is then

[00042]$\begin{array}{cc}{\text{δ}}_f=\frac{{\widetilde{{\text{n}}^{\prime }}}_h{\widetilde{\text{γ}}}_h}{{\widetilde{{\text{n}}^{\prime }}}_h{\tilde{\text{n}}}_h}& \text{­­­(30)}\end{array}$

[0171] Note that many of the terms in this equation can be calculated in advance of receiving a data packet, and may be stored in a memory accessible to the joint estimator 34. In particular, the term n′n in eq. (25), the entirety of eq. (26), the term s’s in eq. (28), and the entirety of eq. (29), may be precomputed. This could be done by the receiver 15, or on a computer away from the receiver 15 with the results being loaded onto the receiver 15.

Pseudocode

[0172] The following exemplary pseudocode implements algorithms 1b and 1c. In both cases algorithm 2b is employed for step 2.

TABLE-US-00001  // Closest Lattice Point Search  if Algorithm1b  gammapf = gamma - ones(N*R,1)/(N*R)*sum(gamma);  apf = clpAnStar(deltah*spf+deltaf*npf-gammapf,length=N*R-1);  elseif Algorithm 1c  gamma = gamma - deltafest*(1:N*R)/R; // Apply frequency correction from Meyr estimator  gammapf = gamma - ones(N*R,1)/(N*R)*sum(gamma);  wpfr = round(-gammapf);  apf = wpfr-(sum(wpfr))/(N*R)ones(N*R,1);  end  ypf = gammapf + apf;  // Backsubstitution  ypff = ypf - npf*(npf*ypf)/(npf*npf);  spff = spf - npf*(npf*spf)/(npf*npf);  hest = spff′*ypff/(spff′*spff); // Modulation index offset estimate  yphf = ypf - spf*(spf′*ypf)/(spf′*spf);  nphf = npf - spf*(spf′*npfy)/(spf′*spf);  fest = nphf′*yphf/(nphf′*nphf); // Frequency offset index estimate

[0173] The joint estimator 34 may comprise hardware logic which implements some or all of the steps represented in this pseudocode, or similar steps for any of the other algorithms or variants thereof. In other embodiments, the joint estimator 34 may be implemented at least partly by software executing on a processor-e.g. the processor 21.

Simulation Results

[0174] Simulation results are provided in the table below. These simulate receiving FSK signals with a symbol rate of 1 MSymbols/s, and a transmitted modulation index, h.sub.TX = 0.45 or 0.5. The nominal carrier frequency is assumed to be 2.5 GHz. The nominal receiver modulation index, h.sub.RX, is 0.5 for the Meyr D-spaced estimator. The maximum frequency offset between transmitter and receiver is defined in parts per million (ppm), and is simulated over a uniform distribution of +/-50 ppm or +/-150 ppm. The resulting offset in Hz can be calculated by multiplying the ppm figures by 2.5 × 10.sup.9 × 10.sup.-6. The SNR is 15 dB. Timing synchronization is assumed (i.e. genie timing sync).

[0175] Simulations are shown for search algorithm 1b (single point) and algorithm 1c (Meyr D-spaced estimator), both employing the back-substitution algorithm 2b. These are denoted “Lattice+Back” and “Meyr N=4, D=1, Round + back, N=16” respectively.

[0176] Frequency offset estimates obtained directly from a D=1 spaced Meyr estimator of length N=4, and from a D=2 spaced Meyr estimator of length N=16, are also shown for comparison purposes.

TABLE-US-00002 Meyr N=4, D=1 Meyr N=16, D=2 Alg. 1b Lattice + Back, N=16 Alg. 1c Meyr N=4, D=1, Round+back, N=16 Meyr N=4, D=1 Meyr N=16, D=2 Alg. 1b Lattice + Back, N=16 Alg. 1c Meyr N=4, D=1, Round+back, N=16 h.sub.TX=0.5 Max offset 50 ppm 150 ppm sqrt((f.sub.0-f.sub.est)^2) [ppm] 21.4 4.46 5.85 7.27 21.8 720 5.75 7.64 sqrt((h.sub.TX-h.sub.est)^2) [ppm] 0.0137 0.0149 0.0128 0.0142 h.sub.TX=0.45 Max offset 50 ppm 150 ppm sqrt((f.sub.0-f.sub.est)^2) [ppm] 35.3 16.1 5.86 11.6 36.2 711 5.8 9.42 sqrt((h.sub.TX-h.sub.est)^2) [ppm] 0.0137 0.0196 0.0137 0.0185

[0177] It can be seen that the algorithms 1b and 1c both results in a slightly worse estimate, f.sub.est, of the true frequency offset, f.sub.0, than Meyr N=16 at 50 ppm offset (“5.85” and “7.27” vs “4.46”) when there is no modulation index offset-i.e. when h.sub.TX=0.5. However, when there is a modulation index offset, both algorithms produce significantly better frequency estimates at 50 ppm (“5.86” and “11.6” vs “16.1”).

[0178] Algorithm 1b outperforms algorithm 1c for all scenarios. This is expected since algorithm 1c is a suboptimal lower complexity variation of algorithm 1b. Note also that when the maximum frequency offset increases to 150 ppm, algorithms 1b and 1c still provide accurate estimates, and algorithm 1c does not underperform algorithm 1b by much, whereas Meyr’s D=2 spaced estimator fails. This is because Meyr’s algorithm can only provide an estimate within a specific tuning range which reduces as D increases.

[0179] Although some of the above disclosure has been described in the context of binary symbols (i.e. bits), it will be appreciated that the same principles can also be applied to systems that use higher-order modulation, such as quadrature modulation, where each symbol may have four or more possible values.

[0180] Although some of the above disclosure has been described in the context of frequency-modulated signals, it will be appreciated that the same underlying principles can also be applied to phase-modulated signals, especially signals that maintain an amplitude within a limited range such that their phase does not traverse the unit circle. In this case, the joint frequency-offset and modulation-index estimator will consider only the phase of the received data.

[0181] It will be appreciated by those skilled in the art that the invention has been illustrated by describing one or more specific embodiments thereof, but is not limited to these embodiments; many variations and modifications are possible, within the scope of the accompanying claims.