Lecture 43 | Applied Linear Algebra | Vector Properties | Prof AK Jagannatham

[Music] [Music] hello welcome to another module in this massive open online course ah so we are looking at ifft and the fft and fft ifft operations that is to convert signals and systems and the representation in the time and frequency domain go back back and forth between the time and frequency domains ah let us now of course that by itself has several implications for signals and system on our signals ah and system analysis let us now look at another interesting application of these transform domain representation that is the matrix representation of fft and ifft operations in the context of something that is very very interesting and relevant and that is in a modulation technique or a waveform known as ofdm many of you might have heard about it ofdm stands for orthogonal frequency division multiplexing and this forms the basis for the high data rate transmission that occurs in your mobile phones and even of course through ah via a cellular network or even via wi-fi in your laptop right so ofdm is the dominant modulation or you one one can call it as the physical layer the signaling strategy that is employed in most modern day wireless communication system so let us try to understand this better and see what is the relevance of the fft and ift operations that we have just studied in this context ok so this is again a very interesting and a very relevant application of well ifftn to begin with the ifft and so ofdm is orthogonal frequency division multiplexing which is the dominant essentially the dominant for not only fo g but also five j systems plus your y five for instance your a two two dot eleven n ito root 11 aac all this modern high data rate standards right so enables ofdm enables high data rate wireless transmission in fact i might add ultra high this ofdm enables ultra high data rate ultra high data rate wireless transmission and naturally this is key modern cellular cellular networks and as well as wi-fi and the ifft and fft operations play a very important role in ofdm and that is what we want to understand what we want to explore via this module is what is the role of the ifft and fft operations in ofdm and in fact there is a reason i mentioned ifft followed by 50 look at it not fft followed by fft right we traditionally think of fast fourier transform followed by the inverse but here interestingly it is going to the ifft followed by fft and for reasons that are going to be clear as we go through this module so what essentially is ofdm right so ofdm as i already told you enables ultra high data rates now what is the problem in the wireless system so if you look at a basic high data rate wireless system right what we call as an hdr a high data rate right what is the h d r what is the issue the issue the central issue of the fundamental problem here is h d r high data rate implies you have high bandwidth but the movement you have high bandwidth this implies small ultra small symbol time so it implies so naturally if the data rate is rising the symbol time is decreasing right so this small symbol time now causes significant problems a small symbol time leads to inter [Music] symbol interference which is also termed as isi so this is ultimately the problem that is your high data rate leads to this complicated leads through this chain to inter symbol interference and naturally inter symbol interference implies distortion and so the long and short of the story is that is whenever you go towards a high data rate systems the simple time being is very small the simple time when this symbol terms becomes small the channel sort of spreads these symbols the channel sort of smears these symbols and these symbols start interfering with each other that is essentially inter simple interference which leads to distortion once once the symbols interfere with each other naturally it becomes very difficult to recover or reliably decode these symbols at the receiver right so this inter symbol interference roughly speaking if you want to get a physical feel for it the symbols you can think of it as thus as if the symbols are smeared they interfere with each other implies decoding is very difficult or the decoding error increases right now how to avoid this thing and ofdm does precisely that ofdm is a strategy to overcome this so enable so to put it in a nutshell ofdm is a strategy that enables high data rate transmission without inter symbol interference and therefore there is no distortion and therefore it makes reliable transmission with high data rate possible so what ofdm does is in a nutshell ofdm enables avoids eliminates i think that is implies hdr high data rate transmission possible lm without isi and therefore this implies no this implies no distortion that is the advantage of odm and how does ofdm do that to understand that let us examine the model of the wireless channel let us assume the output of the channel so what is the channel model let us now examine this and this can be understood in the following simple steps let us start with the channel model the channel this is the output symbol output symbol n right let us call this as output symbol or output symbol m this can be represented as h 0 x m plus h 1 x m minus 1 plus so on h n minus one x m minus n plus one now what is y m y m is the output symbol now this x m is input symbol at time right similarly x m minus one is input symbol at time m minus one so this is at time you have the time m minus 1 and so on and these quantities h 0 h 1 so on h n minus 1 these are the channel taps so if you look at this h 0 h one h n minus one point here is that you see y m that is a symbol at time m depends not only on x m but also depends on past symbols x m minus 1 x minus 2 so on therefore these symbols are interfering with each other this interference in x x m from the past symbols ideally you would like y m to depend only on x m so that you would decode x m but now look at this because of the i data rate that we are talking about y m depends on x m as well as there is interference from x n minus 1 x m minus 2 so on that is the past symbols or the inter symbol interference right so y m it can be seen easily depends um not only on x m but also the past symbols right x m minus one so these are your past symbols which means there is inter symbol this cause intercept this interfere with right so these interfere with x m this implies this is precisely i s i and this is essentially a model for your isi channel right so you have a model this is precisely what you are calling as the isi channel ok so this is the channel which has inter symbol interference your ym depends on x m and there is interference from x m minus 1 and so on so how does ofdm acquire overcome this what is the procedure that ofdm employs the procedure is as follows it seems a little tricky to begin with the point is we start in ofdm we start with x 0 x 1 x n minus 1. so what is the ofdm principle and we proceed with the ifft of these symbols so at the transmitter so these are you can think of this as the frequency domain symbols and these are you get the time domain samples that is we do not transmit the symbols directly but perform the ifft unlike conventional communication transmit the time domain sample so these are the time domain samples these are the time domain samples which are eventually transmitted but before that we have to do something else so the point is from the frequency domain symbols you get the time domain samples and this can be shown to be the principle here is the conventional transmission if you look at this conventional transmission right if you look at this conventional transmission it can be shown that this corresponds to this is the frequency axis this corresponds to a single carrier transmission that is the conventional transmission corresponds to a single carrier transmission but in ofdm what is interesting is you move away from the single carrier transmission to essentially one that is multi carrier so ofdm multi carrier so ofdm has so what is happening is this can be thought of as moving away from a single carrier transmission that you have in a conventional communication system which is centered at carrier frequency fc to an ofdm you move to a multi carrier system all right and that is the significant difference so ofdm is also known as an mcm system that is multi carrier modulation all right so this is also known as mcm this is equal to multi carrier this is equal to multi carrier modulation now the point here is now prior to the transmission of these samples x 0 x 1 and in fact if you look at this figure n this n has certain significance this n is basically this number of carriers each of these is known as a sub carrier so you have this multiple sub carriers now n equal to the number of sub carriers and denotes the number of sub carriers so n denotes the number of sub carriers and what is additionally done is this interesting thing where you have x 0 x 1 these are the time domain samples now what samples now what is done is these are repeated again that is you take these things from here and you prefix them this is known as a cyclic so sample so this is a cyclically repeated so it looks give the impression gives the impression of a periodic sequence so what you are taking is you are taking the samples take some samples from the end put them again in the front so it looks as if it is a cyclically repeated sequence this is an important step in ofdm this process is known as the addition of a cyclic prefix this repetition itself is quantity that is prefixed at the head this is known as a cyclic prefix right so this process is known as the addition of a cyclic prefix right so this is essentially the addition so cyclic prefix is also abbreviated as cp this is addition of c p and then follow this is the addition of cyclic prefix followed by transmission now what happens when you transmit this now look at this let us look at the output corresponding to this so we have y zero equals h zero times x zero plus h one times the previous symbol but what is the previous symbol the previous symbol is x n minus one plus h 2 times x n minus 2 plus so on this would be h n minus 1 times x of you can see not very difficult to see h n minus 1 times x of 1 ok so this is essentially what it would be plus of course there is going to be noise i am not concerned about the too much at this point that would be w of zero now let us look at right one more y one equals corresponding to the next point y one equals h zero of x one plus h one of the previous symbol but the previous symbol is x 0 plus h 2 of x n minus 2 or rather n minus 1 that is a previous symbol to x 0 plus plus h n minus 1 times x 2 plus w 1. now if you look at it all you can see all that has happened is x 0 has moved to the right x n minus one has moved to the right everything has moved to the right x one from the right has come to the left most top so x one you can see what has happened x one has come to the left and then x 0 has move to the right x n minus 1 has moved so everything has moved progressively to one step to the right so you can see this is essentially a circular shift right so you are taking x 0 x 1 x n minus 1 and you are circularly shifting this sequence is an important property so if you look at it what is happening is you have x 0 x 1 x 2 or let us write it this way rather x 0 x n minus 1 x n minus 2 so on up to x 1 what is happening is next instant x 1 or you can say x 1 comes over here and x 0 goes to the next part x n minus 1 goes to the next part right so this is your x n minus 1. so on and ultimately here you have x two so this is essentially a circular shift from step to step and it is a circular shift its not a push out its not a linear shift because you are not simply pushing out the last one but you are taking the last one bringing it back to the front that is in fact your x one so this is a circular shift and this process is essentially what is known as a circular convolution now when we represent it as a linear transform you are going to observe something very interesting so essentially this is a circular convolution right so every step there is a circular shift which implies there is a circular convolution this is not very important at this stage because we are going to look at it in terms now if you represent this as a matrix now this can be now let us look at what is going to be the matrix form of this that is going to be very interesting so what is the matrix the matrix form of this is very interesting the matrix form if you write this as y 0 y 1 up to y n minus one times which is essentially this is the output vector right so this is essentially your this is equal to a matrix times the input vector plus of course the noise vector that is your w zero w one w n minus one right and now if you write this input symbols these are going to be your x 0 i am sorry these are the samples x 0 x 1 x 2 x n minus 2 x n minus 1 and if you look at this matrix is going to be something that is very interesting the first row is going to be a zero times x zero h n minus one times a ah x one h n minus 2 and so on last entry is going to be h 1 times x n minus 1 then your next row is going to be h 1 comes to the left as we have seen then h zero moves to the right h n minus one h two then you are going to have h two h two will come from the right then you will have h one then you'll have h0 you have h3 so on and so forth if you look at this the last very last true will be h n minus 1 anyway you do not need to worry too much about this and this is going to be h zero now you see this matrix this is now let us look at the dimensions this is an n cross one vector this is an n cross one vector this is an n cross one vector this is the output vector these are the samples these are the transmitted samples right and this is the noise vector now if you look at this n cross n matrix you will observe something very interesting you will observe that in this matrix there is something very similar now the first column look at this is h zero and h zero h n minus one h n minus two so on second column h one comes from the right every other element h one comes from the right to the left most part every other ah coefficient is push one spot to the right then the next row h2 comes from the right the right most to the left most position and every other coefficient is pushed one spot to the right so if you look at it each subsequent row is obtained by circularly shifting the previous row in fact same thing can be said for the column first column is h zero h one h n minus one you push it down by one coefficient bring h n minus one back to the top next one is h n minus one h zero h one next one be s n minus two h n minus one h zero h one h two so on each column is obtained by circularly shifting the previous column and therefore this matrix has a unique structure this is known as a circulant matrix this is a very interesting aspect so this is known as so i am going this kind of a matrix is known as a circulant matrix this is a very interesting aspect so let us call this as your y bar let me call this matrix as h c let me call this as x bar let me call this as w bar and now if you look at this i can write this as ah y bar in fact i can write this as y bar equal to h c times x bar plus w bar and h c this is a circulant matrix which means that each row is obtained by shifting right shifting the previous row each row is obtained via this is a very special matrix we are going to discover its properties but i am going to write this right away this is a very very special matrix and i would like to say as a mathematician as an engineer a very interesting matrix you would agree its not every day that you see a matrix like this right does not arise very naturally right you have every row circular shift of the previous row so in that sense there is only one unique row every other row is circularly shift of the previous row so second row is the circular shift of the first row third row you get myself so if you know the first row you can write down in fact if you know any row you can write complete the entire matrix in fact if you know any columns for the same logic you can complete the entire matrix and that is true because all the entries are essentially formed from the channel coefficient so if you know the channel filter that that essentially gives you the matrix so this is formed from the channel taps right so this is formed from the channel tabs and has a very interesting formed by the channel taps which are y zero y one up to i am sorry these are not the channel tabs these are the outputs so these are the channel tabs are 0 h 1. now the point is the other minor point here is what happens if the number of channel tabs is not equal to n the number of sub carriers typically the nodes have to tap is much smaller the rest are replaced by zero so you simply zero pad right so if in case you are wondering if you know a little bit already about ofdm and if you are assuming that you know the number of subcarriers is usually about the order of hundreds channel taps might be of the order of tens that the rest of the channel taps can always i can always replace them by zeros ok so it is known as so to make things simple i have simply assumed that the number of channel tabs is equal to the number of sub carriers but this is in no way a limiting assumption right this is essentially something that is i would like to say generalized or simplified depending on which way you would like to or which view point you would like to take ok now this matrix but our our bone of contention or our our admire our gaze at this point rests or our gaze is transfixed on this matrix this wonderful matrix i would like to say which is and i cannot talk enough enough of this this is this circulant matrix i think i already said it a couple of times because it has indeed if you look at it a very very interesting structure and this structure has ah and naturally you see when you see things that are cycles when you think see things that are periodic like cyclic means nothing but essentially cyclic has essentially some relevance to this notion of periodic right the moment you say cycles remember what is cycles cycles is nothing but a unit of frequency right cycles per second something is cycling so cyclic naturally means there is something that is periodic and periodic naturally must inspire in you as an engineer no matter which field of engineering or science management you are from the fourier part of your brain the thing that talks about sinusoid signs and cosines because if you think of periodic waveforms the fundamental i mean the fundamental waveforms that come to your mind are basically signs and cosines in fact every other periodic signal can be expressed as a linear combination of these signs and cosines that is the wonderful thing that fourier fourier theory or harmonic theory tells us the moment you have something that is cyclic something is periodic so so naturally the ifft and fft have a very important role to play in this system now what is that role that is something that i would like to keep aside for the next module so we will stop here look at this cycle structure of the cyclic matrix appreciate it admire it try to assimilate it try to understand it of course we are going to dissect it and we are going to scrutinize it at much greater depth in the subsequent modules and all this naturally ties into ofd thank you thanks very much [Music] do [Music] [Music] you