One of the properties of Fourier Transform is that the derivative of a signal in time domain gets translated to multiplication of the signal spectrum by in frequency domain. This property is usually derived as follows.
For a signal with Fourier Transform
which is the inverse Fourier Transform of .
Now we want to understand this relation one level deeper, i.e., the reason behind the factor ? There are two parts of this expression: one is and the other is . We start with .
Notice from the definition of Fourier Transform that this operation decomposes a signal into a sequence of complex sinusoids with frequencies ranging from to . This is shown in Figure 1 below.
Figure 1: Three complex sinusoids and their decomposition into sines and cosines
By Euler’s formula,
Naturally, the higher the frequency, the steeper the slope and hence larger the derivative. After all, a derivative is nothing but the slope of the line tangent to the curve at a point. This is where the factor comes from (simply put, the derivative of is ).
The term is more interesting. The derivative of is while that of is . So from Euler’s formula and using ,
Remembering that , the factor is therefore necessary to rotate and by their corresponding angles such that we get our basis signals back. This results in getting the same signal at the output with multiplication by .
I am in the process of writing Volume II of my book. As explained in Volume I, its contents are
Phase locked loop
Carrier phase synchronization
Carrier frequency synchronization
Receiver DSP design
I have finished the chapters on phase locked loop, carrier phase synchronization and carrier frequency synchronization. And currently, I am writing the chapter on symbol timing synchronization. My thought process is to explain the fundamental concepts from a unifying theory which I hope will enable the reader to understand the visualization behind each mathematical equation. Writing is easy, making these figures takes a long time.
There are two updates on the book.
My previous book Synchronization in Wireless Sensor Networks was published through Cambridge University Press. Now I think that the future will converge more towards self-publishing just like democratising of the video. So my publishing of Volume I was to test the process of independent publication. Now instead of having Volume I and II, I am combining them in one book that makes far more sense.
I am including examples from GNU Radio as the community really needs an understanding of software radio beyond the heavily mathematical approach in communications books. Please comment below if you have any comments regarding this suggestion, or something else.
Subscribe to my email list below to receive an update when it is published.
In another article on correlation, we said that correlation is the Master Algorithm for a digital communication system, not only for data detection but for parameter estimation of various kinds as well. We applied it to derive the matched filter for optimal detection. Here, we apply the principle of maximum correlation for solving our phase synchronization problem. The discussion in this context usually considers QPSK modulation but the extension to higher-order modulation schemes is a straightforward task. A similar framework is used for finding and compensating for other distortions as well such as carrier frequency offset and symbol timing offset, the examples of which we will see later.
Correlation with what?
In order to implement correlation, one signal is obviously the Rx signal . It is correlated with a clean version of what is expected at the Rx, the expected signal template. That is the most logical solution to detect the signal and estimate the desired parameters. For example, in case of a carrier phase offset, the Rx signal will be correlated with a perfect Tx signal but rotated in phase by an unknown offset. This procedure then generates an algorithm to estimate that phase offset.
In the presence of noise, the received and sampled signal is
where (in a DFT size of ) corresponds to carrier frequency and and are the inphase and quadrature waveforms (each time we define the inphase and quadrature waveforms, there is a reason behind choosing index or index that becomes clear as we progress through that particular derivation).
The correlation between and its expected template is defined as
We face three problems in implementing the above relation.
[1. Observation interval] The above sum is computed from to , which implies that we could theoretically continue computing this correlation with every received sample . However, the useful component of the received signal is given by a span of symbols while every sample outside this interval is noise only. The time duration of such symbols is
Thus, the finite observation interval is given by
where is samples/symbol, or . Therefore, the observation window consists of samples. It is understood in this calculation that the group delay arising from pulse shaping and matched filtering on either side of the transmission sequence has been taken care of by the Rx.
[2. Start of frame] The second problem is to determine the starting point of the useful component in a sampled signal, as many of its initial samples are noise only. It is the job of a frame synchronization unit to determine the symbol level boundaries of the Rx signal, while the symbol timing synchronization block establishes the optimal sampling instant within a symbol. This will be explained in detail in another article but Figure below illustrates this alignment problem for a visual clarification.
[3. Distortion at edges] Due to the pulse shape spreading beyond a single symbol and actually extending to symbols in each direction, there is a distortion introduced at the edges of the observation interval in the correlation result. However, it can be ignored if is sufficiently long.
We also assume downconversion with perfect frequency recovery, i.e., Tx and Rx oscillators have the same frequency , to emphasize on phase recovery problem. After perfect downconversion, our expected signal template is the complex sequence , with which the correlation of needs to be implemented. The overall setup is drawn in Figure below.
Continuing from the article on effect of a phase offset and ignoring the double frequency terms (the higher frequency terms as a product of downconversion process are either filtered by an analog filter in the RF frontend or a digital filter in the digital frontend and furthermore, the matched filter also suppresses such terms, as it is also a lowpass filter due to the pulse shape originally designed to restrict the spectral contents of the wireless signal), the downconverted complex signal is expressed as
Next, the correlation between the Rx signal and our expected template signal is
where the conjugate arises due to the signals being complex. Having determined through frame synchronization block, we can write Eq (5) as
Using the complex multiplication rule, the actual computations can be written as
Recall that two complex signals are most similar when the inphase part of their correlation at time zero is maximum. Consequently, we ignore the component above and plug the definition of from Eq (4) above.
Substituting the expressions for and yields
Ignoring the distortion at the edges of the summation, the above relation can be simplified recalling the fact that are the samples of a square-root Nyquist pulse with support samples.
Notice that after the received signal is downconverted to baseband, it is correlated with a similar pulse shape to the Tx, . As we saw in the details of matched filter, another way of implementing this correlation is through filtering the signal with its flipped version, (convolution operation in a filter flips again back to and the operation becomes correlation). This is known as matched filtering. Clearly, after summing over the sample index , we are left with a signal with symbol rate spaced samples at times .
Owing to the above description, we can identify the following terms as matched filtered outputs, one in the inphase and other in the quadrature arm.
Now the expression for inphase part of the correlation is simplified as
The above expression is important. As we proceed, this Eq (9) will form the basis of many types of phase estimators, both in feedforward and feedback schemes.
A question at this stage is: starting from correlation, what have we achieved so far? While not clear as of now, we are on our way to solve the fundamental problem of the synchronization process. In a few other articles, we will discuss data-aided, decision-directed and non-data-aided techniques for phase synchronization.
With the growth in the Internet of Things (IoT) products, the number of applications requiring an estimate of range between two wireless nodes in indoor channels is growing very quickly as well. Therefore, localization is becoming a red hot market today and will remain so in the coming years.
One question that is perplexing is that many companies now a days are offering cm level accurate solutions using RF signals. The conventional wireless nodes usually implement synchronization techniques which can provide around level accuracy and if they try to find the range through timestamps, the estimate would be off by
where is the approximate speed of an electromagnetic wave. So how are cm level accurate solutions being claimed and actually delivered?
This is a classic example of the simplest of signals solving the most complex of problems.
In this article, my target is to explain the fundamentals behind this high resolution ranging in the easiest of manners possible. Needless to say, while each product would have its own unique signal processing algorithms, the fundamentals still remain the same.
The Big Picture
For the sake of providing the big picture, remember that there are other methods available, the best of which are based on optical interferometry. Then, there are ultrasound, optical and hybrid options available as well. RF is the cheapest solution though and there is nothing better than getting accurate measurements using the RF waves.
The following techniques are most widely used in RF domain.
Rx Signal Strength Indicator (RSS)
Time of arrival (ToA)
Phase of arrival (PoA) – a special case of ToA
Time Difference of Arrival (TDoA)
Angle of Arrival (AoA)
While I do not explain each of the above in detail (Google is your friend), I summarize their pros and cons below (anchors are wireless nodes with known positions).
Simple hardware, no synchronization required, info provided by most PHY chips
Highly inaccurate and environment specific
Time synchronization required among anchors and target node
Extremely accurate, low cost
Sensitive to phase noise and impairments
Great accuracy, no target node synchronization
Tight synchronization among all anchors
Extra dimension relaxes timing and phase constraints
Expensive hardware and less accurate
As a final comment, all range estimation methods need a reference point. Anchors provide this reference when an accurate measurement of position is needed. If it is just the range from another node that is of interest, any node can use its own reference. This is the situation we assume in this article.
What is a Timestamp?
A typical embedded device comes with a counter and a register. The value of the counter increments/decrements as driven by an oscillator. When an increment counter reaches the maximum value (0xF…FF), or a decrement counter reaches the minimum value (0x0…00), it overflows and starts counting again. If a desirable event occurs, say a message arrival event driven by a Rx start interrupt, the value of the counter can be captured and stored in a register that can be later accessed to find the time of that event – according to the node’s own reference clock.
As an example, consider the following Figure where
the timestamp value is captured in Register
the Counter is an incremental counter
Tx Start is an event that resets the counter, and
Rx Start is an event that captures the Counter value to Register.
Figure 1: The counter, register and Tx and Rx start events
If you don’t know much about electronics, it is enough to know that event times can be recorded at a node and accessed for processing later.
If you want to subscribe to my email list below to receive new articles.
The ranging setup in this discussion consists of two nodes that can exchange timestamps with each other through the wireless medium as shown in Figure below.
Figure 2: Two nodes exchanging timestamps with each other
The distance between the two nodes is while the time of flight from one node to another is . Consequently,
We denote the real time by , Node A’s time by and Node B’s time by . Since each node starts at a random time, there is a clock offset between its time as compared to the real time.
Refer to the next Figure to observe how the chain of events unfolds.
Figure 3: The chain of events with their corresponding timestamps exchanged between Node A and Node B
Any node can start its counter at any given time. So to set a reference point at an arbitrary real time 0, the time offset of Node A is while that of of Node B is .
1. Node A sends its local timestamp to Node B at real time , where
2. Node B receives this packet at real time and records its local time , where
Therefore, we can write
Defining as and as (the clock offset between two nodes),
It is important to write the equation in the above form because all we know is the observation . We do not know , , , and .
3. After a processing delay, Node B sends its local timestamp at real time to Node A.
4. Node A records it at at actual time . Since ,
which can be written in terms of as
Adding Eq (1) and Eq (2) yields the estimate of delay.
Now it is clear that the time base of Node A serves as the reference for estimating this delay. Research literature refers to this approach as a ‘two-way message exchange‘. To pay tribute to Tolkien, I call it ‘There and Back Again‘.
I performed some ranging experiments with a wireless device with a clock rate of 8 MHz. That implies that one such tick takes . In terms of distance, this is m. Gradually increasing the distance, a divide by two operation and rounding off the results generated the following results.
Figure 4: Results for a ranging experiment with an 8 MHz clock
Assume that a 100x accuracy, say cm, is needed. Then, we need a clock generating timestamps at a rate of 800 MHz. That kind of expense and power, however, is more suited to computing applications and not to an embedded device.
In conclusion, we cannot afford a high rate clock but still desire a high resolution.
In the meantime, if you found this article useful, you might want to subscribe to my email list below to receive new articles.
The Arrival of the Phase of Arrival
In the spirit of time of arrival, this method is known as the phase of arrival. First, observe that we already have access to something similar to a high resolution clock – a continuous wave (CW). Consider a simple sinusoid at GHz frequency and just plot its sign. It looks very much like a very high rate clock.
Figure 5: Sign of a simple continuous wave is similar to a high rate clock
Now again consider two wireless nodes that are exchanging continuous waves instead of timestamps in the following manner.
1. Node A sends a continuous wave of frequency at its time (real time ) to Node B. Using , its phase is given by
where is just a constant and could easily be expressed as a single term . As opposed to timestamps case, it is not required, neither it is easy, to measure the phase explicitly.
2. Node B receives this continuous wave at real time when the phase of its own local reference at frequency at its local time , where , is
Using , Node B employs some signal processing algorithm to measure the phase difference between the two continuous waves as
It is important to write the equation in the above form because all
we know is the phase difference . We do not know anything else.
3. After a processing delay, Node B sends a continuous wave in the reverse direction.
4. Node A measures the phase difference
Adding Eq (3) and Eq (4) yields the estimate of delay.
That was so easy, so fast and so accurate. But the world is not that simple.
The Rollover Problem
The solution to the accuracy problem creates a problem of its own. Remember we said that when an increment counter reaches the maximum value (0xF…FF), or a decrement counter reaches the minimum value (0x0…00), it overflows and starts counting again. So if a clock is very fast, it overflows more quickly and resets again. It might even do so when the signal on the reverse path might not have returned! The same is the case with the sinusoids.
For example, a continuous wave at 2.4 GHz would roll over every cm. Any distance greater than 12.5 cm would be impossible to measure.
Introducing More Carriers
To solve this rollover problem, assume and start with plugging Eq (5) in the range expression.
This can be simplified using as
Now we can break the phase into an integer part and a fractional part because , where is the number of integer wavelengths spanning the distance while is the phase corresponding to the remaining fractional distance. Thus, the above equation can be written as
Writing the fractional phase as a function of range
The rollover unwrapping problem is now reduced to cancelling from the above equation. This can be easily accomplished by sending another tone at frequency that would generate the result
The above two equations can now be solved to cancel and create an effect equivalent to sending a single tone with a very large wavelength or very low frequency .
The range is now found to be
Having eliminated the phase rollover, we are interested in maximum range that can be unambiguously estimated through the above equation. Clearly, this depends on the frequency difference between the two continuous waves. Also, remember that can attain a maximum value of . Then, for example, for a 2 MHz difference, i.e., , the unambiguous range is
The Phase Slope Method
To cover all possible ranges, a number of difference continuous waves can be used and their results can be stitched together to form a precise range estimate. This is plotted in Figure below.
Figure 6: Phase vs frequency plot
After taking a number of measurements, a plot of phases versus frequencies is drawn. Similar to Eq (6), we can write
where the constant term arises instead of as it might not be the same for all frequencies. However, the slope of the curve is still given by
from which the range can be found as
This is why it is known as the Phase Slope method. It is relatively costly to implement due to a number of back and forth transmissions (equal to the number of CWs employed) but it is very accurate because indoor channels are frequently susceptible to interference. A wider range of frequencies ensures resilience against interference through the added redundancy.
The radio spectrum is a very precious resource like real estate and must be utilized judiciously. Pulse shaping filters control the spectral leakage of the transmitted signal in a wireless channel due to the strict restrictions to comply with a spectral mask. This is even more important for the upcoming 5G wireless systems which are based on a variety of wireless transmission protocols (such as mobile networks, Internet of Things (IoT) and machine to machine communications) combined in one comprehensive standard. Even for wired channels, there is always a natural bandwidth of the medium (copper wire, coaxial cable, optical fiber) that imposes upper limits on its utilization.
The design of a good pulse shaping filter starts with the smallest possible bandwidth exhibited by a rectangular spectrum. However, that abrupt transition in the frequency domain gives rise to long tails in the time domain. To avoid this problem, a smoother rolloff of the spectrum is desired for which we can extend the bandwidth in any shape as long as it has odd symmetry around half the symbol rate to satisfy Nyquist no-ISI (Inter-Symbol Interference) criterion. This extension can be logically conceived as a convolution between the rectangular mass of width and an even symmetric taper of width where . This even symmetry preserves the odd symmetry around in the resultant filter.
The smoothest spectral shape one can imagine is a sine or cosine. A half-cosine of width — an even symmetric shape — is convolved in frequency domain with a rectangular spectrum to generate the most commonly used pulse known as a Raised Cosine (RC) filter. The parameter is the excess bandwidth or rolloff factor in the resultant desired spectrum.
Since the convolution in time domain is multiplication in frequency domain, an RC filter is divided into two parts in frequency domain: one at the Tx and one at the Rx, both of which are square-root of the original RC filter and are known as Square-Root Raised Cosine (SRRC) filters. The Tx SRRC filter implements the shaping filter that determines the spectral mask while the Rx SRRC filter implements the matched filter that maximizes the SNR at the Rx.
The Raised Cosine concept is a good starting point for pulse shape design and its closed-form mathematical expression is good for analytical purpose. Nevertheless, there are two major drawbacks in using an SRRC pulse for shaping the spectrum.
Since the transition band of an RC pulse is half cycle of a cosine, the transition band of an SRRC pulse is a quarter cycle of a cosine. Its abrupt termination at the stopband results in a discontinuity causing a limit to the sidelobe (SL) suppression that an SRRC pulse can achieve.
As a consequence of truncation in time domain, the pulse is no more absolutely band-limited within and assumes infinite support in frequency in the form of sidelobes. This is because the truncation in time domain (i.e., multiplication by a rectangular window) causes subsequent convolution in frequency domain between the SRRC spectrum and a sinc signal. This operation moves the half amplitude values away from the odd symmetry points of violating the Nyquist no-ISI criterion and inducing increased ISI.
This leads us to other pulse shape design procedures that produce a Nyquist filter with improved stopband attenuation preferably without any degradation in peak ISI. We discuss two main design techniques for finding a superior pulse shaping filter: transformation of a lowpass filter based on Parks-McClellan algorithm to a Nyquist filter, and convolution of a frequency domain window with a rectangular spectrum.
Transformed lowpass filter
The standard method is by starting with an initial lowpass filter that is designed according to the Parks-McClellan algorithm whose passband and stopband edges are matched to the rolloff boundaries of the Nyquist spectrum. The Parks-McClellan algorithm is an iterative algorithm for finding the optimal FIR filter based on Remez exchange algorithm and Chebyshev approximation theory such that the maximum error between the desired and the actual frequency response is minimized. Filters designed this way exhibit an equiripple behavior in their frequency responses and thus are also known as equiripple filters, where equiripple implies equal ripple within the passband and the stopband that are not necessarily the same (in fact, mostly they are not).
Naturally, this lowpass filter crosses the band edge with more attenuation than dB level required for a Nyquist spectrum. Since the transition band belongs to the filter designer, the passband edge frequency can be pushed forward towards dB level. This can be implemented in a software routine through a few iterations of increasing the passband edge frequency based on a gradient descent method, just like an offline adaptive filter.
For a sampling rate , passband frequency , stopband frequency and a positive constant that controls the rate of convergence and the approximation error, the procedure in the -th iteration is listed below:
design a lowpass filter using Parks-McClellan algorithm with frequency set ,
find the error between dB and the filter attenuation in dB at as
update the passband frequency as
For most cases, a few iterations are enough for transforming it into a Nyquist filter. There is a weighting option available as well that can place more emphasis on a desired frequency band at the expense of the remaining bands. For example, more stopband attenuation can be achieved by weighting it at a cost of increased in-band ripple.
For a better visual understanding, we create a length square-root Nyquist filter using a transformed lowpass filter with three different excess bandwidths, namely and a group delay equal to . Next, their frequency response is plotted along with the measure of sidelobe attenuation. Finally, two square-root Nyquist filters are convolved and downsampled at sample/symbol to observe the respect peak ISI levels. The results are drawn in Figure below.
In the meantime, if you found this article useful, you might want to subscribe to my email list below to receive new articles.
Window based filter
The other procedure, devised by fred harris, is based on the convolution of a smooth taper of width with a rectangular spectrum of width . To affect maximum smoothness, this taper should simply be a good spectral window with a narrow mainlobe width and low sidelobe levels. One such candidate is a Kaiser window which is an approximation to the prolate-spheroidal window for which the ratio of the mainlobe energy to the sidelobe energy is maximized. Given a fixed length, a parameter controls the sidelobe height which decreases with at a cost of increase in the mainlobe width. The coefficients for Kaiser window are given by
where is the zero-order modified Bessel function of the first kind. Again, we create a length square-root Nyquist filter using a frequency domain window based filter with similar excess bandwidths , and a group delay of . Next, their frequency response is plotted along with the measure of sidelobe attenuation. Finally, two square-root Nyquist filters are convolved and downsampled at sample/symbol to observe the respect peak ISI levels. The results are drawn in Figure above and compared with the lowpass based design.
Since Parks-McClellan algorithm minimizes the error in the pass and stop bands, it generates optimal filter coefficients and has consequently become the standard method in FIR filter design. Moreover, the iterative lowpass process is more flexible because any sidelobe level can be exchanged with the in-band ripple by utilizing the penalty weights. On the other hand, the Kaiser window technique is not as flexible. Due to the convolution of the spectra, the stopband ripple and the in-band ripple are always the same amplitude.
Figure above also demonstrated in each case that the sidelobe attenuations exhibited by the lowpass filter are significantly better than the window based filter, along with its peak ISI being either comparable or even better. In reality, however, the lowpass filter design is overall superior with respect to sidelobe levels and window based technique is superior in terms of peak ISI. There is room for choosing one over another depending on the system requirements.