Digital Signal Processing/Discrete Operations

From Wikibooks, open books for an open world
Jump to: navigation, search

There are a number of different operations that can be performed on discrete data sets.

Arithmetic[edit]

Let's say that we have 2 data sets, A[n] and B[n]. We will define these two sets to have the following values:

A[n] = [W X& Y Z]
B[n] = [I J& K L]

Arithmetic operations on discrete data sets are performed on an item-by-item basis. Here are some examples:

Addition[edit]

A[n] + B[n] = [(W+I) (X+J)& (Y+K) (Z+L)]

If the zero positions don't line up (like they conveniently do in our example), we need to manually line up the zero positions before we add.

Subtraction[edit]

A[n] - B[n] = [(W-I) (X-J)& (Y-K) (Z-L)]

Same as addition, only we subtract.

Multiplication[edit]

In this situation, we are using the "asterisk" (*) to denote multiplication. Realistically, we should use the "\times" symbol for multiplication. In later examples, we will use the asterisk for other operations.

A[n] * B[n] = [(W*I) (X*J)& (Y*K) (Z*L)]

Division[edit]

A[n] / B[n] = [(W/I) (X/J)& (Y/K) (Z/L)]

Even though we are using the square brackets for discrete data sets, they should NOT be confused with matrices. These are not matrices, and we do not perform matrix operations on these sets.

Time-Shifting[edit]

If we time-shift a discrete data set, we essentially are moving the zero-time reference point of the set. The zero point represents "now", creates the starting point of our view of the data, and the point's location is typically established by a need of the processing we're involved in.

Let's say we have the data set F[n] with the values:

F[n] = [1 2 3& 4 5 ]

Then we can shift this set backwards by 1 data point as such:

F[n-1] = [1 2& 3 4 5]

We can shift the data forward by 1 data point in a similar manner:

F[n+1] = [1 2 3 4& 5]

Discrete data values are time oriented. Values to the right of the zero point are called "future values", and values to the left are "past values". When the data set is populated on both sides of the zero reference, "future" and "past" are synthetic terms relative to the zero point "now", and don't refer to current physical time. In this context, the data values have already been collected and, as such, can only come from our past.

It is important to understand that a physically-realizable digital system that is still receiving data cannot perform operations on future values. It makes no sense to require a future value in order to make a calculation, because such systems are often getting input from a sensor in real-time, and future values simply don't exist.

Time Inversion[edit]

Let's say that we have the same data set, F[n]:

F[n] = [1 2 3& 4 5]

We can invert the data set as such:

F[-n] = [5 4 3& 2 1]

We keep the zero point in the same place, and we flip all the data items around. in essence, we are taking a mirror image of the data set, and the zero point is the mirror.

Convolution[edit]

This operation can be performed using this MATLAB command:
conv

Convolution is a much easier operation in the discrete time domain than in the continuous time domain. Let's say we have two data sets, A[n] and B[n]:

A[n] = [1& 0 1 2]
B[n] = [2& 2 2 1]

We will denote convolution with the asterisk (*) in this section; it isn't "multiplication" here. Our convolution function is shown like this:

Y[n] = A[n] * B[n]

and it specifies that we will store our convolution values in the set named Y[n].

Convolution is performed by following a series of steps involving both sets of data points. First, we time invert one of the data sets. It doesn't matter which one, so we can pick the easiest choice:

A[n]  = [1& 0 1 2]
B[-n] = [1 2 2 2&]

Next, we line up the data vertically so that only one data item overlaps:

A[n]  ->       [1& 0 1 2]
B[-n] -> [1 2 2 2&]

Now, we are going to zero-pad both sets, making them equal length, putting zeros in open positions as needed:

A[n]  -> [0 0 0 1& 0 1 2]
B[-n] -> [1 2 2 2& 0 0 0]

Now, we will multiply the contents of each column, and add them together:

A[n]  -> [0 0 0 1& 0 1 2]
B[-n] -> [1 2 2 2& 0 0 0]
Y[m] = 1 \times 2

This gives us the first data point: Y[m] = [2].

Next, we need to time shift B[-n] forward in time by one point, and do the same process: multiply the columns, and add:

A[n]    -> [0 0 0 1& 0  1 2]
B[-n-1] ->   [1 2 2  2& 0 0 0]
Y[m+1] = 1 \times 2

Repeat the "time shift, multiply, and add" steps until no more data points overlap.

A[n]    -> [0 0 0 1& 0 1  2]
B[-n-2] ->     [1 2  2 2& 0 0 0]
Y[m+2] = 1 \times 2 + 1 \times 2
A[n]    -> [0 0 0 1& 0 1 2]
B[-n-3] ->       [1  2 2 2& 0 0 0]
Y[m+3] = 1 \times 1 + 1 \times 2 + 2 \times 2
A[n]    -> [0 0 0 1& 0 1 2]
B[-n-4] ->          [1 2 2 2& 0 0 0]
Y[m+4] = 1 \times 2 + 2 \times 2
A[n]  -> [0 0 0 1& 0 1 2]
B[-n] ->            [1 2 2 2& 0 0 0]
Y[m+5] = 1 \times 1 + 2 \times 2
A[n]    -> [0 0 0 1& 0 1 2]
B[-n+6] ->              [1 2 2 2& 0 0 0]
Y[m+6] = 1 \times 2

Now we have our full set of data points, Y[m]:

Y[m] = [2 2 4 7 6 5 2]

We have our values, but where do we put the zero point? It turns out that the zero point of the result occurs where the zero points of the two operands overlapped in our shift calculations. The result set becomes:

Y[n] = [2& 2 4 7 6 5 2]

It is important to note that the length of the result set is the sum of the lengths of the unpadded operands, minus 1. Or, if you prefer, the length of the result set is the same as either of the zero-padded sets (since they are equal length).

Discrete Operations in Matlab/Octave[edit]

These discrete operations can all be performed in Matlab, using special operators.

Division and Multiplication 
Matlab is matrix-based, and therefore the normal multiplication and division operations will be the matrix operations, which are not what we want to do in DSP. To multiply items on a per-item basis, we need to prepend the operators with a period. For instance:
Y = X .* H  %X times H 
Y = X ./ H  %X divided by H

If we forget the period, Matlab will attempt a matrix operation, and will alert you that the dimensions of the matrixes are incompatible with the operator.

Convolution 
The convolution operation can be performed with the conv command in Matlab. For instance, if we wanted to compute the convolution of X[n] and H[n], we would use the following Matlab code:
Y = conv(X, H);

or

Y = conv(H, X);

Difference Calculus[edit]

When working with discrete sets, you might wonder exactly how we would perform calculus in the discrete time domain. In fact, we should wonder if calculus as we know it is possible at all! It turns out that in the discrete time domain, we can use several techniques to approximate the calculus operations of differentiation and integration. We call these techniques Difference Calculus.

Derivatives[edit]

What is differentiation exactly? In the continuous time domain, the derivative of a function is the slope of the function at any given point in time. To find the derivative, then, of a discrete time signal, we need to find the slope of the discrete data set.

The data points in the discrete time domain can be treated as geometrical points, and we know that any two points define a unique line. We can then use the algebraic equation to solve for the slope, m, of the line:

m = \frac{\Delta f(t)}{\Delta t}

Now, in the discrete time domain, f(t) is sampled and replaced by F[n]. We also know that in discrete time, the difference in time between any two points is exactly 1 unit of time! With this mind, we can plug these values into our above equation:

m = \frac{\Delta F\left[n\right]}{1}

or simply:

m = F\left[n+1\right] - F\left[n\right]

We can then time-shift the entire equation one point to the left, so that our equation doesn't require any future values:

m = F\left[n\right] - F\left[n-1\right]

The derivative can be found by subtracting time-shifted (delayed) versions of the function from itself.

Difference Calculus Equations[edit]

Difference calculus equations are arithmetic equations, with a few key components. Let's take an example:

Y\left[n\right] = X\left[n\right] - 2X\left[n-1\right] + 5X\left[n-2\right]

We can see in this equation that X[n-1] has a coefficient of 2, and X[n-2] has a coefficient of 5. In difference Calculus, the coefficients are known as "tap weights". We will see why they are called tap weights in later chapters about digital filters.