Digital Signal Processing is the branch of engineering that, in the space of just a few decades, has enabled unprecedented levels of interpersonal communication and of on-demand entertainment. By reworking the principles of electronics, telecommunication and computer science into a unifying paradigm, DSP is a the heart of the digital revolution that brought us CDs, DVDs, MP3 players, mobile phones and countless other devices. The goal, for students of this course, will be to learn the fundamentals of Digital Signal Processing from the ground up. Starting from the basic definition of a discrete-time signal, we will work our way through Fourier analysis, filter design, sampling, interpolation and quantization to build a DSP toolset complete enough to analyze a practical communication system in detail. Hands-on examples and demonstration will be routinely used to close the gap between theory and practice. To make the best of this class, it is recommended that you are proficient in basic calculus and linear algebra; several programming examples will be provided in the form of Python notebooks but you can use your favorite programming language to test the algorithms described in the course.
1.3.b The Karplus-Strong algorithm
Loading...
Из курса от партнера École Polytechnique Fédérale de Lausanne
Digital Signal Processing
457 оценки
Из урока
Module 1: Basics of Digital Signal Processing
Познакомьтесь с преподавателями
Paolo PrandoniLecturer
School of Computer and Communication Science
Martin VetterliProfessor
School of Computer and Communication Sciences
Perhaps some of you are familiar with the Meccano toy.
You open the box, you have a bunch of little metal parts, of nuts and bolts.
And then you can use your imagination to create fancical little contractions.
Well, did you know signal processing is a little bit like that?
You have a few fundamental building blocks and if you are creative,
you can combine them to build arbitrarily complex circuitry that performs
analysis or synthesis.
In this module, we will see what the building blocks are and
we will see how we can combine them to explain some simple phenomena like
the accruing of bank interest or to synthesize musical sounds.
Let's review the blocks in turn, we have seen before.
The first one is the adder, it takes two sequences as the inputs and
creates a third sequence, which is the sum of the input.
As an example, imagine the first sequence is a decreasing ramp like so and
the second sequence is an increasing ramp like so.
If you sum them together, you get a constant sequence.
This is actually a general result when the slopes
of the ramps are the negative of each other.
The second building block is a multiplier.
It takes one sequence as the input and
provides a scaled version of that input as the output.
So for instance, the same decreasing ramp is shown here.
And if the factor is one half, what you get at the output is the same shape but
scaled by one half.
The third building block is the delay.
Here we see the unit delay, so we take an input sequence here and
what we get at the output is the same sequence delayed by one sample.
Now, the notation z to the minus 1 inside this block might seem a little obscure.
But it will be clear in a few weeks.
You have to think of this block as a memory cell, as a buffer that keeps
the current value in storage and returns you instead the previous value.
So if we apply the delay to our usual decrease in ramp,
we get that the delay by one sequence will look like so.
So here we are assuming that all the sequences are finite supports signals,
there are zeros everywhere outside of the shown portion of the signal.
A simple generalization of the delay is the arbitrary delay where we delay
the input by N samples.
So here, the memory cell is actually N memory cells.
You can think of it as a circular buffer where you store the current sample and
return the sample that you have gotten N steps before.
So if we apply this to the usual signal and
use a delay of four, we have a shift to the right by four samples.
If capital N is negative, then we would have a shift to the left and
we would say that we are anticipating the signal rather than delaying it.
Of course, anticipation implies that you know the future.
This is not really the case in general, but if your data is already stored
on disc, imagine your sequence is, for instance a recorded musical sound,
then you can probably go backwards or forwards arbitrarily.
Okay, now let's see how you can use those building blocks to perform
a very simple operation, on a sequence, computing the moving average.
The simple average of two numbers, well we don't need to define it,
it's simply the sum, of the two numbers, divided by two.
A moving average, is a local average,
that you perform, every step of the way in a sequence.
So you take the current sample, you take the previous sample,
you sum them together, and you divide by two.
How would you implement this?
So here we could write some lines of code in your favorite programming languages but
instead, we will use the graphical notation that we have introduced before.
We will use these building blocks these mechaniblocks so
that the structure shows you an abstract implementation of the algorithm
that you can then convert to your favorite language.
This is a very powerful descriptive paradigm for
signal processing that we will use all through the course.
So here's how we would represent the moving average with building blocks.
Remember y of n is equal to x of n + x of n- 1, divided by two.
So here we have x of n, okay?
Here we have an adder.
We need to get x of n minus one.
We get that by a delay operator.
So outside here, so x of n c goes in here.
Here we get x of n- 1.
We put it here, x of n also goes through here.
Here is the sum of the two.
And here we multiply by 1/2 and here we have the output.
Okay, so this is the representation with building blocks of the moving average.
Let's apply this to a signal and see how that works.
Let's pick the simplest possible discreet time signal, the delta sequence,
which is 0 everywhere except for N = 0, where the value is one.
If we apply the moving average to the signal, well nothing really happens before
N reaches zero because for all negative values of N, the input is zero and
the average of two zeros will be zero.
When N is equal to zero, then we have that y of zero
will be equal to x of zero + x of zero- 1 divided by 2.
So, x of zero, we know is equal to one, x of minus one is equal to zero, and so
this is equal to 1/2 and end 0., the output would be equal to 1/2.
In 1, y of 1 will be equal to x of 1 plus
x of 1 minus 1, 0 divided by 2.
And again this is equal to 0, this is equal to 1 and
this will be equal to one half.
And then for all values of n greater than one,
we will have the two inputs that we use in the average are zero and
so the output will be identical to zero for eternity.
Another example the unit step.
What happens here is that again nothing happens for
the negative values of the index.
The first time something moves is when n is equal to 0 at which point the first
output sample will be exactly like in the case of the delta sequence.
The average of 0 here and 1 here.
And we will get one half.
Then for n equal to 1 onwards, we will be averaging two equal values and
so of course the average will be equal to the value itself.
And we will have one for all values of the index greater than one.
Let's now try to compute the moving average of a sinozoid,
here we have cos(omega n) with omega = pi/10.
But the frequency is in, to see what the moving average of this signal is,
we will have to use a little bit of trigonometry.
In general, the output will be equal to cos of omega n- cos omega( n- 1) / 2.
We can use trigonometric formulas to show that this is equal to
show that this is equal to cos(omega n) + face term theta.
So surprisingly, the output of the moving average applied to a sinusoid is
a sinusoid at the same frequency of the, just a phase turn is added.
This is actually a general result that holds whenever we apply a linear
transformation to a sinusoidal input.
Another sequence could be the alternating sequence where we switch continuously
between plus one and minus one.
At this point, when we average,
we're always doing a local average of two values with opposite signs so they're
average will be zero and therefore the output sequence will be identically zero.
Okay, so the moving average is a very simple piece of circuitry.
But remember it's like the Meccano toy, so we can take these pieces and
change the way we combine them.
So a legitimate question is, what happens if here we reverse the loop?
You can see here in the flow of signals in the moving average circuitry,
everything moves forward, okay?
So what if we reverse one of the branches and obtain something like this?
In this case, the signal goes in, finds another, then goes through the other and
then goes back via delay to the other.
We have reversed the loop and
created a feedback path from the output because the signal here is
equal to the output y of n back to the input section of the circuit.
The equation that describes the transformation operated by this circuit
is the following.
We have that the output at time n is equal to the input times n plus alpha,
where alpha is simply a scaling factor in this case,
times the output at the precedence depth.
So, were we using the previous output rather than using a previous input sample.
Whenever we use previous output samples in our formula,
we say that the algorithm is recursive and perhaps this picture by Azure
captures really the essence of recursion, and its fundamental problem.
If we need previous output samples, where do we start?
This is the chicken and the egg problem of recursion, and
we solve it in signal processing by setting 0 Initial conditions.
In other words, we set a start time for the computation of our algorithm.
We assume that all inputs and outputs are identically zero for
all values of the index before the start time and we say that at that point,
usually the start time is n equal to zero, all the buffers,
all the memory cells in our circuitry are filled with zeroes.
With that, we can start the process.
So let's exemplify recursion by explaining how interest accrues in your bank account.
It's a very simple model for banking.
Let's assume that the interest is constant and
is, say, 5%, which is [LAUGH] rather generous.
And it's accrued once per year, on December 31.
The deposit and withdrawals during their year are modeled by an input sequence,
x(n), so x(n) for every year will be positive, if you have deposited
money in your bank account, and negative if you have withdrawn money.
And the balance at year end will be given by 1.05 times the capital
that you had in your bank account in the previous year plus
the balance of deposits and withdrawals.
If we draw this banking algorithm as a DSB circuit,
we have the standard feedback loop with the delay of 1.
Here we have our operations
that we perform our bank account during the year and the output here
is the total sum that we find at the end of year in our bank account.
A simple example is the one-time investment.
Suppose that the year is zero, you put a 100 units of cash in your bank account,
then the capital at year zero is 100.
At year one, you will have accumulated 5% interest on the capital at that year.
Since we are not touching the capital,
at the end of the first year we will have 105 units.
And at the second year, we'll have accrued 5% on the accrued capitals.
So 5% of 105, and so y(2) will be 110.25 y (3)
will be the previous sum times 1.05% and so on and so forth.
If you work out the math, you see that the capital,
if you don't touch it, will increase exponentially as 100,
your initial investment times 1.05 to the power of n.
So it's an exponential growth of course,
the ratio of the exponent is very, very small.
And so you will not get rich very quick.
Okay, so let's go back to the Meccano board and do a little substitution.
Replace in the feedback loop the delay,
that was a delay by one, by a delay by Capital M.
So that the output will be now alpha times the output computed
capital M steps before plus the input.
This is really equivalent to replacing the single delay by cascade of three delayed
blocks.
So three memory cells and we can use the structure now to create loops.
Let's see how this works by using the delta sequence as the input and
alpha equal = 1.
The initial conditions are 0 and the delays are filled with 0s.
When n = 0, our input will be equal to 1 and so
we have that a one transits in the system, okay?
It will be here, here.
It will be at the output here and
it will replace the content of the first delay line.
And y of zero will be equal to one.
Okay, now we are at n equal to one.
So the situation now is like so.
For n = 1, everything advances.
The input will be zero, so it will be zero here,
it will be a zero here coming from this delay.
This will be 0 and this 0 will transit into the delay line, this will be replaced
by 0, this will advance and put a 1 here, this will advance and put a 0 here.
So in the end, we have that y(1) = 0 and
the delay line situation will be 0, 1, 0.
The next step for n = 2, we have 0 here because of
course x of two is equal to zero, that will transit everywhere.
0 will come from this delay, y(2) = 0, so this zero will go in here,
this will be 0, 0, and 1, because everything has been shifted by 1.
The next step, y(3), well this will be always 0 from now on,
but now the 1 that was in the delay here will transit up,
will sum 0 and 1 here, and so the output will be equal to 1.
And the 1 will also go into the delay here and everything will be shifted back.
So in this way, we have created a loop that will periodically put out
a 1 every three samples.
We can experiment with loop generator by changing some of
the parameters in the structure.
So for instance, let's pick alpha here equals to 0.7,
let's leave the delay at 3 and the input sequence to the delta sequence.
So the first time we go around the loop, we'll get the same output as in
the previous examples so y(0) = 1, y(1) = 0, and y(2) = 0.
For M = 3, the value 1 that has transitted through
the delay line will pop out and will be multiplied by 0.7.
So we got y(3) = 0.7 and then we got two 0s again.
And then when we go around the loop once more, the 0.7 has transited through
the delay line will be multiplied by 0.7 again and we have 0.7 to the power of 2.
The result in output is a pseudo periodic sequence in the sense
that we have the same three sample pattern but every time we go through the loop,
the amplitude of the non-zero sample in the pattern is 0.7 to the power of n/3.
Another way to play with the structure is to keep alpha = 1, so
no attenuation, and use an input signal that is a finite support
signal whose length is equal to the length of the buffer.
I encourage you to do this with pen and paper and
you will see if you match the length of the input to the length of the buffer,
what you get is a truly periodic sequence where the initial pattern
gets repeated an infinite number of times, starting at zero.
Interestingly, we can use this simple structure
to build an elementary music synthesizer that in spite of its simplicity,
can produce quite interesting simulations of real musical instruments.
So we build a recursion loop with a delay of capital M samples.
We will choose an input signal that is by the support and
that is nonzero, only between 0 and capital M minus one.
So this is the length of the support coincides with the length of
the delay line.
We will choose a decay factor, either one for
no decay or less than one to have decay envelope for the node.
We will input this finite support sequence to the system and
play the output using the strategy that we have seen in the previous module.
So let's start with a very simple example.
We will chose M = 100 samples.
Alpha = 1, so there will be no decay.
And we will prepare an input signal which is just one full period of a sinusoid.
So we take a sinusoid at a frequency omega = 2 Pi / 100.
So a full period will complete over a 100 samples.
We will input the sequence to the system and we will get the following waveform
where you see the periods are joined perfectly every 100 samples.
If we play this waveform using a sampling frequency of 48 kilohertz,
we will have 48,000 samples per seconds,
the pattern repeats every 100 samples and so the result in pitch that we will
perceive will be equal to 480 hertz and this is how it sounds.
[SOUND] Okay, this is not an extremely interesting sounds so,
let's try to introduce some realism.
Remember, capital M, the length of the delayed buffer controls the frequency,
the pitch of the proceed sound.
Alpha controls the envelope whether we have the decay or not, and
the initial sample of our finite support signal will control the timbre,
the color of the sound.
So let's try and change the timbre by, instead of using a sign wave,
using what is called a sawtooth wave.
A sawtooth wave tries to capture the mechanics of say, a violin.
When you drag a bow across the string of the violin, the little teeth in the bow's
strings are picking the string, displacing it and then when the tension gets too big,
the strings jumps back in the original position.
So here we have a situation where we modeled displacement and
then a sudden return to the original position.
So each period will just be a linearly increasing ramp from -1 to 1.
So we build this hundred sample ramp, it goes from -1 to 1.
We will pick a decay factor of 0.95.
We will put this into the recursion loop,
and we will get a pseudo-periodic signal that looks like so.
Because the decay factor is very close to 1,
you're not going to be able to see the envelope in this small window of samples.
But if we were to plot the signal on a longer scale, it would look like this.
So now if we play the sound, we get a completely different color.
[SOUND] All right, that wasn't really the best violin sound
you've ever heard, but this algorithm actually
works remarkably well to simulate the sound of plucked strings.
This is actually the context in which it was invented by Carplus and
Strong and they found out that the best way to initialize the algorithm, so
the best way to fill the finite support of the input signal you
see is random values compared to a sufficiently fast decay factor.
So here we will pick alpha = 0.9.
We will use 100 random values between -1 and 1 over the finite
support of the input and run the algorithm to obtain a waveform that looks like this.
Here you can see the decay factor because we're plotting
the signal on a longer window.
The sound is this [SOUND] and it's remarkably similar to a harpsichord.
Ознакомьтесь с нашим каталогом
Присоединяйтесь бесплатно и получайте персонализированные рекомендации, обновления и предложения.
Coursera делает лучшее в мире образование доступным каждому, предлагая онлайн-курсы от ведущих университетов и организаций.
© Coursera Inc., 2019 Все права защищены.
