Average PSD of QAM signals

August 8, 2009 at 10:29 am · Filed under Signal Processing

The previous post showed that the “periodogram” can be applyed on WSCS signals.

Linear digital modulation signals are generally represented (in base-band) as:

x(t)=\underset{-\infty}{\overset{\infty}{\sum}}I_{n}\cdot g(t-nT)

where T is the trasnmission period, I_{n} are the information symbols (which are complex in the case of QAM) and g(t) is the shaping filter.

Calculating R_{xx}(t+\tau,t), the auto-correlation function of the base-band signal, shows that the process is WSCS. Note that the signal is a random process since the information symbols are assumed to be random. Moreover, we assume that the symbols are a discrete-time WSS process.

Let’s try to find the average PSD “directly”, i.e. not through the auto-correlation.

Define:

x_{N}(t)\equiv\overset{N}{\underset{n=-N}{\sum}}I_{n}\cdot g(t-nT),

which is x(t) bounded by a window of size \bar{T}=(2N+1)\cdot T.

Taking the Fourier transform yields:

X_{N}(w)=\overset{N}{\underset{n=-N}{\sum}}I_{n}\cdot G(w)e^{-jw(nT)}

Now comes the interesting part:

E[|\frac{X_{N}(w)}{\sqrt{\bar{T}}}|^{2}]=\frac{1}{\bar{T}}E[|X_{N}(w)|^{2}]=\frac{1}{\bar{T}}E[X(w)\cdot X^{*}(w)]=

=\frac{1}{\bar{T}}E[\overset{N}{(\underset{n=-N}{\sum}}I_{n}\cdot G(w)e^{-jw(nT)})\overset{N}{\cdot(\underset{k=-N}{\sum}}I_{k}^{*}\cdot G^{*}(w)e^{+jw(kT)})]=

=\frac{1}{\bar{T}}\underset{n}{\sum}\underset{k}{\sum}|G(w)|^{2}\cdot e^{jwT(k-n)}E[I_{n}I_{k}^{*}]=

=\frac{1}{\bar{T}}|G(w)|^{2}\underset{n}{\sum}\underset{k}{\sum}R_{II}[n-k]\cdot e^{-jwT(n-k)}=

=\frac{1}{\bar{T}}|G(w)|^{2}\underset{k}{\sum}\underset{n}{(\sum}R_{II}[n-k]\cdot e^{-jwTn)})e^{jwTk}=

=\frac{1}{\bar{T}}|G(w)|^{2}\underset{k}{\sum}(S_{II}(wT)\cdot e^{-jwTk})e^{jwTk}=

=\frac{1}{\bar{T}}|G(w)|^{2}\underset{k=-N}{\overset{N}{\sum}}S_{II}(wT)=

=\frac{1}{(2N+1)T}|G(w)|^{2}\cdot S_{II}(wT)\cdot(2N+1)=

=\frac{1}{T}\cdot S_{II}(wT)\cdot|G(w)|^{2}

Using the previous post results, we get:

\mathbf{\bar{S}_{xx}(w)=lim_{N\rightarrow\infty}E[|\frac{X_{N}(w)}{\sqrt{(2N+1)T}}|^{2}]=\frac{1}{T}\cdot S_{II}(wT)\cdot|G(w)|^{2}}

Which is the average-PSD of linearly modulated signals (e.g. QAM).

Only 1 note: You probably ask yourself where we  used the limit N\rightarrow\infty. The answer is that this allowed us to treat the summations as from -\infty to +\infty, yielding the Fourier transform of R_{II}[l].

Leave a Comment

Average Power Spectrum Density

August 7, 2009 at 8:01 pm · Filed under Signal Processing

While going over some topics in digital communication, I came across the
Average-PSD (Average Power Spectrum Density) term; the A-PSD is a statistical
character of WSCS (Wide Sense Cyclo-Stationary) random process much
like the PSD is a statistical character of WSS (Wide Sense Stationary) random
process. Following, I will talk about the PSD, how it is calculated,
and how it represents the average power density of a WSS process. Later,
I will do the same with A-PSD and WSCS process.

1. PSD (of a WSS process)

When a random process is said to be Wide-Sense Stationary (WSS) – it has a time-invariant mean and a 1D auto-correlation function; that is, for a WSS process x(t) we have:

\mu_{x}(t)=E[x(t)]=\mu_{x}

\tilde{R}_{xx}(t+\tau,t)\equiv E[x(t+\tau)x^{*}(t)]=R_{xx}(\tau)

And the PSD is defined as the Fourier transform of R_{xx}(\tau):

S_{xx}(w)=F\{R_{xx}(\tau)\}=\underset{-\infty}{\overset{\infty}{\int}}R_{xx}(\tau)\cdot e^{-jw\tau}d\tau

Let us do some math:

S_{xx}(w)=F\{R_{xx}(\tau)\}=\underset{-\infty}{\overset{\infty}{\int}}R_{xx}(\tau)\cdot e^{-jw\tau}d\tau=

=\underset{-\infty}{\overset{\infty}{\int}}E[x(t+\tau)x^{*}(t)]e^{-jw\tau}d\tau=\underset{-\infty}{\overset{\infty}{\int}}E[x(t+\tau)x^{*}(t)e^{-jw\tau}]d\tau=

=E[\underset{-\infty}{\overset{\infty}{\int}}x(t+\tau)x^{*}(t)e^{-jw\tau}d\tau]=E[x^{*}(t)\cdot\underset{-\infty}{\overset{\infty}{\int}}x(t+\tau)e^{-jw\tau}d\tau]=

=E[x^{*}(t)\cdot X(w)\cdot e^{jwt}]=E[X(w)\cdot(x(t)e^{-jwt})^{*}]

And this is true for every w and every t !

Note, that even though t appears on the right hand side of the equality, the result will be independent of t (since we assume that the process is WSS). Also note that we consider X(w) to be the Fourier transform of x(t) in the sense that it is a new “random process” of variable w. We also assume that all realizations of x(t) are bounded in time [-0.5T,0.5T], in order to avoid convergence issues. However, the boundaries shall meet the requirement of T being “very large” . Thus, from now on we will refer to the latter as X_{T}(w), as to point out that the Fourier transform is taken over a window with a size T.

Let us now integrate both sides of the equation with respect to t:

\underset{-0.5T}{\frac{1}{T}\overset{0.5T}{\int}}S_{xx}(w)dt=\underset{-0.5T}{\frac{1}{T}\overset{0.5T}{\int}}E[X_{T}(w)\cdot(x(t)e^{-jwt})^{*}]dt

S_{xx}(w)=E[X_{T}(w)\cdot\underset{-0.5T}{\frac{1}{T}\overset{0.5T}{\int}}(x(t)e^{-jwt})^{*}]

Now since T\rightarrow\infty, we get:

\mathbf{S_{xx}(w)=lim_{T\rightarrow\infty}\{E[\mid\frac{X_{T}(w)}{\sqrt{T}}\mid^{2}]\}}

To summaries, if we look at the Fourier transform of a “very long” (T\rightarrow\infty) window of x(t), we get X_{T}(w) which is a random variable for every w. The result shows that the PSD is essentially the mean of |X_{T}(w)|^{2}, thus being the “mean power” of the random process for every frequency w.

2. (Time) Averaged PSD (of a WSCS process)

When a random process is said to be Wide-Sense Cyclo-Stationary (WSCS) – it has a periodic mean and a 2D auto-correlation function which is periodic as well. That is, for a WSCS process x(t) we have:

\mu_{x}(t)=E[x(t)]=\mu_{x}(t+k\cdot T)

R_{xx}(t+\tau,t)\equiv E[x(t+\tau)x^{*}(t)]=R_{xx}(t+\tau+k\cdot T,t+k\cdot T)

where T is the “period”‘ of the random process.

Note that WSCS processes are very common in the field of digital communication, e.g. QAM signal.

Let us now define:

S_{xx}(w;t)\equiv F\{R_{xx}(t+\tau,t)\}\equiv\underset{-\infty}{\overset{\infty}{\int}}R_{xx}(t+\tau,t)\cdot e^{-jw\tau}d\tau

From here we go on pretty much like in the case of a WSS processes as shows in section 1, only this time we get:

\alpha\equiv\frac{1}{\bar{T}}\overset{0.5\bar{T}}{\underset{-0.5\bar{T}}{\int}}S_{xx}(w;t)dt=E[X(w)\cdot\frac{1}{\bar{T}}\overset{0.5\bar{T}}{\underset{-0.5\bar{T}}{\int}}(x(t)e^{-jwt})^{*}]=

=lim_{\bar{T}\rightarrow\infty}\{E[\mid\frac{X_{\bar{T}}(w)}{\sqrt{\bar{T}}}\mid^{2}]\}

Note that while the right han side remain un-changed, the spectrum is now a function of t as well – making the integral not-so-trivial as in the case of WSS processes.

However, by definition we can show that the spectrum is periodic T:

S_{xx}(w;t+k\cdot T)\equiv\underset{-\infty}{\overset{\infty}{\int}}R_{xx}(t+k\cdot T+\tau,t+k\cdot T)\cdot e^{-jw\tau}d\tau\underset{WSCS}{=}

=\underset{-\infty}{\overset{\infty}{\int}}R_{xx}(t+\tau,t)\cdot e^{-jw\tau}d\tau=S_{xx}(w;t)

Without the loss of generality, we assume \bar{T}=T\cdot M; thus, we can re-write the right hand side:

\alpha=\frac{1}{\bar{T}}\overset{0.5\bar{T}}{\underset{-0.5\bar{T}}{\int}}S_{xx}(w;t)dt=\frac{1}{TM}\cdot\underset{i=0}{\overset{M-1}{\sum}}\overset{(i+1)T}{\underset{iT}{\int}}S_{xx}(w;t)dt=

=\frac{1}{TM}\cdot\underset{i=0}{\overset{M-1}{\sum}}T\cdot S_{xx}^{AV}(w)=\alpha

where we define S_{xx}^{AV}(w)\equiv\frac{1}{T}\cdot\underset{<T>}{\int}S_{xx}(w;t)dt, the (time-) “average” PSD.

\alpha=\frac{1}{M}\cdot M\cdot S_{xx}^{AV}(w)=S_{xx}^{AV}(w)

So we get:

\mathbf{S_{xx}^{AV}(w)=lim_{\bar{T}\rightarrow\infty}\{E[\mid\frac{X_{\bar{T}}(w)}{\sqrt{\bar{T}}}\mid^{2}]\}\equiv\bar{S}_{xx}(w)}

Beautiful. The latter equation shows that the mean of |X_{\bar{T}}(w)|^{2} is essentially the “average” PSD for a WSCS process.

3. Conclusions

The result is interesting since:

  1. One way to compute the average PSD is to first compute the time-average autocorrelation function (averaged over a single period), and then take the Fourier transform. However, if one is not interested in the autocorrelation function,but only in the average PSD, he may want to use the method previously shown.
  2. The results also show that if we have a lab equipment such as a “spectrum analyzer” which finds the PSD of a WSS process by averaging |X_{\bar{T}}(w)|^{2}, it will find the average PSD of a WSCS process as well.

OK, it has been a long post already. Next time I will talk a little bit about WSCS processes in digital communication, and show how to use the results of the current post on QAM signals.

Leave a Comment

No-Cost Useful Software

July 9, 2009 at 8:05 pm · Filed under PC Software

Hi There,

Long time no post…

This time something a little bit different. There’s a list of some free (as in freedom)

and free (as in free beer) software that my dear friend Idan and myself have been

maintaining for some time now.

The idea began as a list of s/w, divided by category,  to install once you format your

computer. However, I think you might find it interesting – so here it is:

– Security –
AVG Antivirus
Ad-aware
Spybot
Zonealarm Firewall

– Utils –
7-Zip
SIW – System Information for Windows
Hashcalc – Calculate MD5/SHA1/CRC32 ….
RealVNC Server / Viewer – remote desktop

– PDF/PS –
FoxitReader (PDF reader)
CutePDF Writer (PDF Printer)
pdftk – pdf manipulator
Ghostscript – for viewing postscript files

– File Manipulation / Documentation Tools –
TKDiff – Excellent linux/windows application for comparing files
Scite (Enhanced Text Editor)
Notepad++ (Supports almost every language)
OpenOffice
Dia
KHexEdit (Linux) (Binary file editor)
Kompozer (HTML editor)
Lyx (Latex editor)

– Internet –
Firefox + Thunderbird (Browser + Mail)
- Firefox Addons: Noia 2 extreme (theme); fireFTP; DownThemAll; FlashBlock; Gmarks; Greasemonkey; Xmarks; Answers.com
- Thunderbird Addons: Nioa 2 extreme (theme); Enigmail; Lightning
NVU (Website editor/WYSIWYG)
GPG4Win
Free Download Manager
WinSCP – GUI for scp (copy files via SSH)
PuTTY – SSH client
KeePassX – Manage passwords for websites

– Chat –
Skype
Pidgin

– Development Accessories –
Wireshark/Ethereal (Network Sniffer)
Visual Studio Express 2008 – The microsoft free version of VS
Poderosa (Terminal supposting COM/Telnet etc.)

– Backup Tools –
CDBurnerXP – CD/DVD burning program (also compatible with Windows Vista)
Daemon Tools (load an ISO to a virtual CD drive, as if you’ve just burned that CD and put it into your CD drive)

– Video / Sound –
Avidemux – Manipulate video files (very useful if you need to convert formats, or some basic editing)
Audacity (Greate Audio editing program)
Gom player / VLC player (both are MP3 / movies players. Quite good)
VLC media player – Cross Platform media (also DVD!) player
Bytessence MPxConverter 1.1 (MP4 to AMV converter – for MP4 player)
HandBrake – Ripping video DVDs and converting them
IsoBuster – Also rips video DVDs, but can also handle problematic DVDs (e.g. if you didn’t finalize the disc)

– Image Manipulation –
Gimp – Photoshop replacement
IcoFX – Icon editor

– Cad –
KiCad (Linux) (Schematics + PCB Editor)

Leave a Comment

Stability Of Discrete-Time LTI Systems

April 12, 2009 at 9:24 pm · Filed under Signal Processing

This time I’d like to show you an insight that I thought of a long time ago; it was during a semester in which I was taking both “Complex Analysis” and “Linear Systems” classes.

Let’s look at a discrete-time LTI system h[n], with a Z-Transform H(z)=\frac{N(z)}{D(z)}, where N(z) and D(z) are both polynomials.

Assuming that h[n] is causal, it is stable iff all poles of H(z) are inside the unit circle; i.e. all zeros of D(z) are inside the unit circle.

Since D(z) could be a polynomial of some degree, finding its zeros could be “difficult”. This gives rise to the need for systems stability criterion, which will not require finding them explicitly.

There is a direct Routh method for discrete-time systems, made up by Prof. Yuval Bistriz. However, what I would like to talk about is not a method, but rather a little “trick” which can be useful in certain cases.

Let D(z) be a polynomial of degree n:

D(z)=a_{n}z^{n}+a_{n-1}z^{n-1}+...+a_{1}z^{1}+a_{0}

Lemma:

Pick the coefficient a_{i} with the highest absolute value.

If |a_{i}|>\underset{j\neq i}{\sum}|a_{j}| then:

1. If i=n than the system is stable since all D(z) zeros are inside the UC.

2. If i\neq n than the system is unstable, since D(z) has zeros outside the UC.

Now comes the part in which Complex Analysis met Linear Systems in my mind -

Proof:

Let me define:

I(z)=a_{i}z^{i},

J(z)=\underset{\underset{j\neq i}{j=0}}{\overset{n}{\sum}}a_{j}z^{j}

Where

|a_{i}|>\underset{j\neq i}{\sum}|a_{j}|,

and obviously,

D(z)=I(z)+J(z).

What we are interested in is the number of zeros D(z) has inside the closed contour |z|=1, i.e the unit circle (alternatively: z=e^{jw}).

|I(z)|_{z=e^{jw}}=|a_{i}e^{jw}|=|a_{i}|\underset{given}{>}\underset{j\neq i}{\sum}|a_{j}|\underset{(1)}{\geq}|J(z)|_{z=e^{jw}}

While (1) is true since

|J(z)|_{z=e^{jw}}=|\underset{\underset{j\neq i}{j=0}}{\overset{n}{\sum}}a_{j}z^{j}|_{z=e^{jw}}\leq\underset{\underset{j\neq i}{j=0}}{\overset{n}{\sum}}|a_{j}e^{jw}|=\underset{\underset{j\neq i}{j=0}}{\overset{n}{\sum}}|a_{j}|.

What we have shown is that |I(z)|>|J(z)| anywhere on the unit circle. By Rouché’s theorem, we can conclude that I(z) and D(z)=I(z)+J(z) have the same number of zeros inside the unit circle.

Thus,

if i=n, than I(z) has n zeros inside the unit circle (all of them at z=0). It follows that D(z) also has n zeros inside the unit circle, i.e. all of its zeros are in it (as a polynomial of degree n, it has exactly n zeros).

However,

if i\neq n than I(z) has i zeros inside the unit circle (again, all of them at z=0), where i<n. It follows that D(z) also has only i zeros inside the unit circle, thus must have (n-i) zeros outside of it.

Q.E.D.

Note that this is Not a general method for checking whether a system is stable or not, but can be a nice trick for that purpose when one of the coefficients’ absolute value is “very large”.

Leave a Comment

Linear Systems – Point of View

March 20, 2009 at 5:51 pm · Filed under Signal Processing

This post is going to be much shorter than the previous one, and might be very obvious to the most of you. However, I still found it worth writing.

A continuous time linear system can be described using a function of 2 variables, i.e.

h(t,\tau),

which is the impulse response (a function of t) for an impulse signal input arriving at time \tau.

The figure below describes a general linear system:

LinearSystem

The output is calculated by convolving the input and the impulse response of the system, with respect to \tau:

y(t)=\overset{+\infty}{\underset{-\infty}{\int}}h(t,\tau)\cdot x(\tau)d\tau\equiv A,

which is actually a superposition of all impulse responses.
However, a linear system can be observed in a slightly different manner (yet equivalent).

Let me re-write the integral by changing variables:

A\underset{\tau=t-\alpha}{=}\overset{-\infty}{\underset{+\infty}{\int}}h(t,t-\alpha)\cdot x(t-\alpha)d(-\alpha)=\overset{+\infty}{\underset{-\infty}{\int}}h(t,t-\alpha)\cdot x(t-\alpha)d\alpha\equiv B

Now lets define a new function, \overset{\sim}{h}(t,\tau), as the impulse response at time t for an impulse arriving at time t-\tau.

We can say that \overset{\sim}{h}(t,\tau) is a different representation of the system, yet fully describes it.

Note that the relation between \overset{\sim}{h}(t,\tau) and h(t,\tau) is given by:

\overset{\sim}{h}(t,\tau)=h(t,t-\tau)

It follows that:

B=\overset{+\infty}{\underset{-\infty}{\int}}\overset{\sim}{h}(t,\alpha)\cdot x(t-\alpha)d\alpha

Replacing \alpha with \tau, we get that:

y(t)=\overset{+\infty}{\underset{-\infty}{\int}}\overset{\sim}{h}(t,\tau)\cdot x(t-\tau)d\tau.

The latter shows the output of a linear system as a superposition of functions,each is a delayed variation of the input signal, x(t), multiplied by some function of t, \overset{\sim}{h}(t,\tau).

This way is sometimes preferable, for example in wireless communication systems involving multipath channel.

Comments (2)

Sampling – Projection Onto a Sinc(.) Basis ?

March 13, 2009 at 10:34 pm · Filed under Signal Processing

The idea for my first post – the one you’re reading right now – came to my mind after I attended a guest lecture at Tel-Aviv University. The latter was given by Prof. Alan V. Oppenheim from MIT. His lecture carried the title “sampling, sampling”, so you can guess what it was about. What I would like to talk about this time is a brief note, made by Prof. Oppenheim during his lecture, which yet caught my attention. Let me quickly refresh your memory with the basics of uniform sampling model, and I promise to get back to that point right afterwards.

Lets assume a continuous-time signal, X(t); sampling it yields a discrete-time signal, X[n] = X(nT), where T is the sampling period. The mathematical model commonly used to describe the sampler is multiplication of X(t) by an impulse train, I(t)=\underset{n}{\sum}\delta(t-nT), and then converting every Dirac delta function (continuous time impulse) to a Kronecker delta function (discrete time impulse).

Under the assumption that X(t) satisfies the Nyquist–Shannon criterion, i.e. band-limited (-\frac{\pi}{T},\frac{\pi}{T}), it can be fully recovered from its samples X[n] by using an ideal interpolator. The latter first converts every Kronecker delta function of X[n] to a Dirac delta function, and then applies an ideal LPF with a cut-off frequency of \frac{\pi}{T}.

The figure below describes this model:

Sampler and Interpolator Figure

Sampler and Interpolator Figure

The formula for the recovered signal,X_{r}(t) , is given by:

X_{r}(t)=\underset{n=-\infty}{\overset{\infty}{\sum}}X[n]\cdot Sinc(\frac{\pi(t-nT)}{T}),

which is sometimes referred to as Whittaker–Shannon interpolation formula.

If X(t) satisfies the Nyquist–Shannon criterion, we get X_{r}(t)=X(t). The common proof is achieved in the frequency domain.

Let’s now go back to the point. Prof. Oppenheim wanted us to think of X[n] as a projection of X(t) onto a Sinc(.) basis – \{Sinc(\frac{\pi(t-nT)}{T})\}_{n=-\infty}^{\infty}. This seems very logical when one’s looking at the interpolation formula; \{Sinc(\frac{\pi(t-nT)}{T})\}_{n=-\infty}^{\infty}is the basis, and X[n] are the coefficients. The equality X_{r}(t)=X(t) is proven (for X(t) functions that satisfy the Nyquist–Shannon criterion), and everything seems to fall into place.

However, I was wondering to myself, how could it be that sampling a continuous-time signal is the same as projecting it onto a Sinc(.) basis ?

How would a “straight-forward” proof of this claim look like ? How would the given data of X(t) (band limitation) be used in that proof ?

Here are my notes, hope you find them interesting:

Let’s define:

\varphi_{n}(t)\equiv Sinc(\frac{\pi(t-nT)}{T})

Its Fourier transform is:

\phi_{n}(w)\equiv F\{\varphi_{n}(t)\}=T\cdot e^{-jwnT}\cdot\left\{ \begin{array}{ccc} 1 & , & |w|<\frac{\pi}{T} \\ 0 & , & o.w \end{array}\right.

Let’s also define:

<\varphi_{n}(t),\varphi_{m}(t)>\equiv\int\varphi_{n}(t)\varphi_{m}^{*}(t)dt

(who has just said “inner product” ?)

By Parseval’s/Plancherel’s theorem:

<\varphi_{n}(t),\varphi_{m}(t)>=A\cdot<\phi_{n}(w),\phi_{m}(w)>=B\cdot\overset{+\frac{\pi}{T}}{\underset{-\frac{\pi}{T}}{\int}}e^{-jw(n-m)T}dw=

=\left\{ \begin{array}{ccc} -B\cdot\frac{1}{j(n-m)T}e^{-jw(n-m)T}\mid_{-\frac{\pi}{T}}^{+\frac{\pi}{T}}=0 & , & n\neq m \\ C & , & n=m\end{array}\right.=C\cdot\delta[n-m]

This shows that the functions \{Sinc(\frac{\pi(t-nT)}{T})\}_{n=-\infty}^{\infty} are orthogonal to one another. Now we would like to examine the projection of X(t) on Sinc(\frac{\pi(t-nT)}{T}):

<X(t),\varphi_{n}(t)>=\alpha\cdot<X(w),\phi_{n}(w)>=\alpha\cdot T\overset{+\frac{\pi}{T}}{\underset{-\frac{\pi}{T}}{\int}}X(w)\cdot e^{+jwnT}dw\equiv R,

where X(w)=F\{X(t)\} is the Fourier transform of X(t).

Thus, if X(t) is band-limited (-\frac{\pi}{T},\frac{\pi}{T}), i.e. X(w)=0,w\notin(-\frac{\pi}{T},\frac{\pi}{T}), R can be re-written as:

R=\alpha\cdot T\overset{+\infty}{\underset{-\infty}{\int}}X(w)\cdot e^{+jw(nT)}dw=\beta\cdot F^{-1}\{X(w)\}\mid_{t=nT}=\beta\cdot X(nT),

meaning that the projection of X(t) (which satisfies the Nyquist–Shannon criterion) on Sinc(\frac{\pi(t-nT)}{T}) is equivalent to sampling X(t) at t=nT !

Nice, isn’t it?

Only one comment: What I have shown here is not a proof. It is merely an insight. A rigorous proof will have to show that the set of functions \{Sinc(\frac{\pi(t-nT)}{T})\}_{n=-\infty}^{\infty} is a complete orthogonal system, with an inner product as (not) defined above.

Comments (5)