wu :: forums - Print Page


    
      
        wu :: forums
        (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi)
      

        riddles >> medium >> Upsampling and Downsampling
        
(Message started by: william wu on Jan 8^th, 2003, 6:53pm)

Title: Upsampling and Downsampling
Post by william wu on Jan 8^th, 2003, 6:53pm

You are given a number sequence x_n = { ... , a_-2, a_-1, a₀, a₁, a₂, ... }. We will refer to the terms of the sequence as "samples."

Define DOWN_L( ) to be a downsampling operator. This operator takes a sequence x_n 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:

DOWN₂( x_n ) = { ... , a_-2, a₀, a₂, a₄, ... }

Now define UP_M( ) to be a upsampling operator. This operator takes a sequence x_n as input and inserts M-1 zeroes in between each sample. For example, if L = 3, we insert 2 zeroes in between each sample:

UP₃( x_n ) = { ... , a_-2, 0, 0, a_-1, 0, 0, a₀, 0, 0, a₁, 0, 0, a₂, ... }

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]:

DOWN_L( UP_M ( x[n] )) = UP_M( DOWN_L ( x[n] ))

Title: Re: Upsampling and Downsampling
Post by Pietro K.C. on Jan 8^th, 2003, 10:38pm

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 UP_M( DOWN_L( 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 DOWN_L( UP_M( 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 UP_M( DOWN_L( x[n] ) ) is x(L*n/M) if M divides n, and 0 otherwise.

The index n of potentially nonzero elements of DOWN_L( UP_M( 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.

Title: Re: Upsampling and Downsampling
Post by william wu on Jan 26^th, 2003, 12:44pm

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(e^jw) represents the Fourier Transform of the discrete sequence x_n.

http://www.ocf.berkeley.edu/~wwu/images/riddles/upsampling_freqdomain.gif

http://www.ocf.berkeley.edu/~wwu/images/riddles/downsampling_freqdomain.gif

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:

http://www.ocf.berkeley.edu/~wwu/images/riddles/downsampling_overlap_freqdomain.gif

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.