Author |
Topic: Upsampling and Downsampling (Read 14538 times) |
|
william wu
wu::riddles Administrator
Gender: 
Posts: 1291
|
 |
Upsampling and Downsampling
« on: Jan 8th, 2003, 6:53pm » |
 Quote  Modify
|
You are given a number sequence xn = { ... , a-2, a-1, a0, a1, a2, ... }. We will refer to the terms of the sequence as "samples."
Define DOWNL( ) to be a downsampling operator. This operator takes a sequence xn as input and removes samples such that only every Lth sample remains. Another way of phrasing this behavior is the downsampler keeps only samples whose indices are multiples of L. So for example, if L = 2:
DOWN2( xn ) = { ... , a-2, a0, a2, a4, ... }
Now define UPM( ) to be a upsampling operator. This operator takes a sequence xn as input and inserts M-1 zeroes in between each sample. For example, if L = 3, we insert 2 zeroes in between each sample:
UP3( xn ) = { ... , a-2, 0, 0, a-1, 0, 0, a0, 0, 0, a1, 0, 0, a2, ... }
Puzzle: Under what conditions can one interchange upsampling and downsampling operators, and still end up with the same sequence? That is, when is the following true, for an arbitrary x[n]:
DOWNL( UPM ( x[n] )) = UPM( DOWNL ( x[n] ))
|
| « Last Edit: Jan 8th, 2003, 7:02pm by william wu » |
 IP Logged |
[ wu ] : http://wuriddles.com / http://forums.wuriddles.com
|
|
|
Pietro K.C.
Full Member
 
Gender:
Posts: 213
|
|
Re: Upsampling and Downsampling
« Reply #1 on: Jan 8th, 2003, 10:38pm » |
Quote Modify
|
First of all, if either M = 1 or L = 1, the commutative law holds, so we will restrict our attention to the cases where both L and M are greater than 1.
Consider the sequence x(n) = 1 for all n. Then UPM( DOWNL( x[n] ) ) is a sequence with 1's on every m-th position, the rest being 0's. Now, it is easy to see that DOWNL( UPM( x[n] ) ) will achieve the same result if, and only if, gcd(L,M) = 1.
Hence, gcd(L,M) = 1 is a necessary condition for the general commutative law to hold. "Is it sufficient?", one might ask. "Yes," one might answer, but people say all sorts of things, so let's check to see.
Suppose gcd(L,M) = 1.
The n-th element of UPM( DOWNL( x[n] ) ) is x(L*n/M) if M divides n, and 0 otherwise.
The index n of potentially nonzero elements of DOWNL( UPM( x[n] ) ) are those for which L*n = M*k for some integer k; because, before downsampling, the index n had to be a multiple of M. Since gcd(L,M) = 1, we must have n divisible by M - so all the 0's are where they're supposed to be. Now, notice that, in the above equation, k was the original index of the element at position n; it used to be k, got multiplied by M, then divided by L. It follows that the n-th element after the transformation is x(k), if n is divisible by M. But, from the above, we have k = L*n/M, so that the n-th element is x(L*n/M), as in the previous case.
Therefore, the commutative law holds if, and oly if, gcd(L,M) = 1.
|
|
IP Logged |
"I always wondered about the meaning of life. So I looked it up in the dictionary under 'L' and there it was --- the meaning of life. It was not what I expected." (Dogbert)
|
|
|
william wu
wu::riddles Administrator
Gender:
Posts: 1291
|
|
Re: Upsampling and Downsampling
« Reply #2 on: Jan 26th, 2003, 12:44pm » |
Quote Modify
|
Just thought I'd add that this result is perhaps more surprising at first to electrical engineers than people in other fields. Upsamplers and downsamplers operate on discrete-time sequences, such as perhaps a digital soundtrack. EE people usually think of upsamplers and downsamplers in the context of what they can do for us in the frequency domain (if you're really interested in what they're good for you can google for "signal processing upsampling downsampling"). Turns out that in the frequency domain, upsampling causes figures to be shrunk, whereas downsampling causes figures to be widened and repeated. This is illustrated below for the cases of upsampling and downsampling by factors of 2. The weird X(ejw) represents the Fourier Transform of the discrete sequence xn.
Note that if the downsampling factor is high enough, the figures may stretch so much that they overlap, as shown below when the factor is increased to 3:
When this overlap happens some information is lost, and this is the effect of aliasing. So just looking at the frequency domain, it's not expected at all that you can always interchange upsamplers and downsamplers as long as the factors are relatively prime, regardless of how much aliasing happens. In fact when the professor told us this in one of my EE courses last year, we didn't believe it and he assigned the problem for extra credit. Turns out the proof is not that difficult if you analyze the process in the time domain (I only gave time domain definitions here), but it's difficult when you're used to thinking in the frequency domain.
|
| « Last Edit: Jan 26th, 2003, 12:56pm by william wu » |
IP Logged |
[ wu ] : http://wuriddles.com / http://forums.wuriddles.com
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print