Pseudorandom binary sequence

Transcription

Welcome to the course on 3G and 4G wireless mobile communication systems. We are discussing code division for multiple access or we said that CDMA. Code division for multiple access is a multiple access technology on which third generation wireless communication systems are based. Last lecture we looked at the fundamentals of how C DMA decouples or distinguishes, the received signal of different users on the common air interface using different codes. We said that is possible through the use of the orthogonal code for instance. I have here two codes; C 0 C 1, which are orthogonal that is that dot product or inner product is 0. Hence, using such orthogonal codes CDMA can multiplex or enable multiple access on the different users on the same interface. Last class we also saw that these sets of orthogonal codes for instance C 0, C 1, C 2, C 3 look like random sequences of plus and minus 1s. We said such long random sequences can be generated using what are known as linear feedback shift registers or LFSR A. A linear feedback shift register architecture consists of set of registers. I take two outputs combine them linearly. For instance, here I am taking X i minus 3 X i minus 4. I am combining then linearly. Then I am feeding it back as X i to the set of registers. Hence, this is set of registers there is the linear combination and then there is the feedback. Hence, this is a linear feedback shift register also abbreviated as LFSR. And the equation of this register that is X i is generated as X i minus 3, x or with X i minus 4. So, that equation defining equation of this feedback register or LFSR is X i equals X i minus 3 x or with X i minus 4. And we were about tabulate the difference state and the outputs of this linear shift back register. So, let us start with this lecture with basically going through the different states and the different outputs of the linear feedback shift register. But before I go with that let me again illustrate that in this linear feedback shift register the output here of this LFSR is X i minus 4. So, the X i minus 4 is one is where is the output of this linear feedback shift register. With that let us go into let us discuss the output and the behavior of this linear feedback shift register alright. So, I will write here four columns X i minus 1 X i minus 2 X i minus 3 X i minus 4 and x i is generated remember as X i minus 3 x or with X i minus 4. This X i minus 2 X i minus 3 X i minus 4, they are also known as that state. So, this is also essentially known as the state of the linear feedback shift register. Let us assume that I am starting from the all 1 state that is X i equals 1 X i minus 1 equals 1 X i minus 2 equals 2 X i minus 3 equals 1 and X i minus 4 also equals 1. Hence, the output in this state is X i minus 4, which is 1 and remember X i is X i minus 3 x or with X i minus 4. Both X i minus 3 and X i minus 4 are 1. Hence X i minus 3 x or with X i minus four is 1, x or 1 which is 0. Hence, X i is 0. Now in the next cycle, X i will go through the feedback will register to become X i minus 1, X i minus 1 will become X i minus 2, X i minus 2 will become X i minus, 3 X i minus 3 will become X i minus 4 and that defines the next sate. So, we started from the state of all 1s the next state is 0 1 1 1. The output in this state is X i minus 4 which is 1 and X I, which corresponds to the X i of this state is X i minus 3 x or X i minus 4 which is 1 x or 1 which is again 0. Now, we can again continue the same process again, X i becomes X i minus 1. So, this will become 0, this will become X i minus 1 become X i minus 2, which is 0. This is 1, this is 1, the output is the X i for the next state is 0. So, continuing this fashion let me fill out the rest of the entries the next is 0 0 0 1 and X i is now 1 x or with 0. So, X i is 1. The next state is 1 0 0 0 and X i is 0. The next sate is 0 1 0 0 and X i is 0. The next is 0 0 1 0 and X i is look at this X i is X i minus 3 x or X i minus 4. So, X i minus 3 x or X i minus 4 is 1 x or 0, which is 1. This 1 will again go here or define the next state which is 1 1 0 0 1 X i minus 3 becomes X i minus 4. So, this will become 1 and this X i is 1. So, at every state please verify that where it is easy to verify, how the next state is generate from the current state. So, at every state please ensure that the calculations that we are doing correct. If you can go through this table again just to understand enhance your understanding. I mean if you can go this computation from yourself you will understand this better. How this LFSR or linear feedback shift register is functioning. The next state is 1 1 0 0 and the output corresponding to this is 0 the next state is 0 1 1 0 and the output corresponding to this is 1 I will continue on the next page. So, I will write X i X i minus 2 X i minus 3 X i minus 4 and here I will write this as X i. So, the previous state is 0 1 1 0 and the output is 1. This 1 will come over here. Next state is going to be 1 0 1 1. So, the next state is 1 0 1 1 and output and X i is 0. The next state is 0 1 0 1, X i is 1. The next state is 1 0 1 0 and X i is 1. The next state is 1 1 0 1 and X i is 1. The next state is 1 1 10 and X i is again 1 and now you can see X i will come over here, which will become X i minus 1. And the next state is simply 1 1 1 1, which is the all one state. You go back to this slide, look at this we started with there all one state, and we are coming and we are coming back to the all one state. So, we have start here we come back to the state with which we have started. At this point the linear feedback shift register and the outputs will again go through the same cycle that we seen because we agree the state that all 1 state that which we started. Hence, we have come to that state at this point it will start repeating. In fact no matter which state we start with over here we can see, if I start with for instances the state 0 1 1 1. If we go through all these states following all 1 it will come to the 0 1 1 1 state and again it will start giving same output. Hence, this linear feedback shift registers generated a set of its periodic the outputs are periodic and essentially the output sequence as we have said. Remember we already said the output is nothing but X i minus 4. Hence, the output sequence I am boxing this output sequence over here. The output sequence of this linear feedback shift register is this column of X i minus 4. That is I am taking a single period of X i minus 4 calling this about sequence. Remember, this is also a pseudo noise sequence or this is in other words a P N sequence and why are you again, let me remind you why? We are want this P N sequence because we want to generate codes that can be used for CDMA. We want to generate these orthogonal codes that can be used among multiple users for multiple access. So, now let us look, let us first examine this linear feedback shit register. First let us look at this let us count the number of states in this linear feedback shift register. The all 1 state is the first state then 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15. It goes through 15 distinct states before it starts repeating again. Look at this we started with the all 1 state after 15 states, again we end up with the all 1 state now. Now, remember the state has 4 different quantities; X i minus 1 X i minus 2 X i minus 3 X i minus 4 and each X i can take two different values. Hence, the total number of states is 16. The total number of states this LFSR is 16. However, it only goes through the 15 of the 16 states that is, it does not go through every state. Why is that happening? If you look at this carefully observe this it goes through all states except the all 0 state, so let me write that down clearly. The LFSR the linear feedback shift register goes through all states except this is the big except the all 0 state that is, it does not go through this all 0 state. So, look at this we have four register corresponding to X i minus 1, X i minus 2, X i minus 3, X i minus 4. So, if D is the number of registers in the LFSR, then the number of states is 2 power D minus 1. In this case, D equals power. Hence, the number of states is 2 power 4 minus 1 which is 16 minus 1. So, in this case D equals 4, hence the number of states equals 2 power 4 minus 1 equals 15. So, the number of states is 2 power 4 minus 1 which is 15. Now let us look a little bit more closely at all 0 states. Let us take X i minus 1 X i minus 2 X i minus 3 X i minus 4 as the all 0 state. Let us see what happens if the register is in the all 0 state. So, X i minus 1 is 0, X i minus 2 is 0, X i minus 3 is 0 X i minus 4 is 0. Now, if I look at the X i, X i is X i minus 3 xor minus four which is 0 xor 0 which is 0. Now, in the next cycle X i will become X i minus 1 which will become 0 X i minus 1 will become X i minus 2 which is 0 0 0. Again X i is 0 and then this will go into again the 0 state. Hence, if you start in the all zero state the LFSR continues to be in all 0 states. So, it continues in the all 0. So it is the LFSR becomes locked in the all 0 states of it gets in somehow it gets into the all 0 state. It will never get out of the all 0 state. So, it hence the LFSR can never start in an all 0 state and in fact during the cycle. It can during its period it can never enter the all 0 states also because if it is once it is enters the all 0 states it will never get out of the all 0 state. This is the reason the all 0 state does not it visits all the state except the all 0 state. Hence in LFSR which goes through all states except the all 0 state is known as a maximal length LFSR. Hence, LFSR which it goes through all states except the all 0 states is known as the maximal length is known as the maximal length. LFSR is known as a maximal is known as the maximal length linear feedback shift register. The sequence that is generated by this maximal length linear feedback shift register is known as the maximal length sequence. So, the PN sequence generated by the maximal by the maximal length LFSR is known as a maximal length sequence. Now, in this case as we have seen it generates, it visits all states expect the all 0 state. Hence, the number of state 2 power D minus 1. Hence maximal length sequence is of length 2 power D minus 1. This is sequence consider if I have if a linear feedback shift register with D register the length of the maximal sequence that can be generated is 2 power D minus 1. In the previous case the number of registers was poor hence the length was 2 power 4 minus 1 which 15. So, that is how a long P N sequences are generated. Let us look at some properties of this P N sequences. The P N sequence that was generated was, let me write down that p n sequence that is 1 1 1 1 0 0 0 1 0 0 1 1 0 1 0 . So, the sequence that is been generated is 1 1 1 1 0 0 0 1 0 0 1 1 0 1 0. You can verify this from this table if you take this outputs together that is X i minus 4. I will take them for one period that is the P N sequence that is, over here. Now, I have to map them to voltage levels. So, I will map 1 to a minus 1 and 0 to a plus 1. I am taking this information symbols 1 and 0 and I am mapping them to voltage levels either plus 1 or minus 1. I am mapping 1 to a minus 1 i am mapping 0 to a plus 1. So, I will have the code that is given as minus 1 minus 1 minus 1 minus 1 1 1 minus 1 1 1 minus 1 minus 1 1 minus 1 1. This is the code so the given the P N sequence I am mapping 1 to a minus 1 0 to a 1 to generate the code. Now let us look at the properties of code. Let us count the number 1's and minus 1's in this code. The number of minus 1's is 1 2 3 4 5 6 7 8. So, there are 8 minus 1's in this code. And the number of 1's is therefore, 15 minus 8 is 7. So, there are 7 1's or plus 1's in the code. Hence, what we can see is with this code is roughly balanced the number of minus 1's and the number of 1's is approximately equal except the number of minus 1's is 1 more than the number of 1's. That is what you would expect if you have random sequence and if you are computing the number of plus 1's and minus 1's. Then you would find that because of the probability of 1 and probability of minus 1 is that is approximately is equal to half the number of 1's. It is approximately equal to the number of minus 1's and that is what we observe here. The number of minus 1's in the code is simply 1 more than the number of 1's that is the defining property of the P N sequence. So, let me write the property the number of minus 1's in the code is always 1 greater than the number of 1's in the codes. So, this is the first properties, let me label this is property. Now property two is also known as the run length property. Let me illustrate that property two here a run is any string of continues values that is if I have string of 1 1 1 that is 1 run, if I have a string of minus 1 minus 1 minus 1 that is 1 run. So, a run so let me write property two. This is known as run length property, a run is the string of continues values. So let us look at the runs in this run in this P N code pseudo random code random code of plus 1's and minus 1. I have first a run 1 run of minus 1's. I then have 1 run of 3 of plus 1's. That is second run, I then have 1 run of a single quantity of 1 run of 1 minus 1. So, that is the third run then I have a 1 run of 2 plus 1's that is the fourth run then I have 1 run of 2 minus 1 that is the fifth run. Then I have 3 runs of 1 minus 1 that is I have 1 run of 1 that is 6 1 run of minus 1 that is 7 1 run of 1. That is 8. So, there are 8 total runs in this P N sequence. Let me write that there are total of 8 runs in this P N sequence. The number of runs, run is continues string of values we counted the number of runs in this P N sequence and we are saying that there are a total of 8 runs. Now, let us look further at this runs there is 1 run of length 4. So, let me write classify or categorize these runs as different runs. So, there are 8 runs out of which there is 1 run of length 4 or basically out of all the runs one eighth. Remember there are 8 runs, 1 is length 4, which means one eighth of the runs are of length 4. One eighth of runs are of length four out of this 8 runs 2 are of length 2 look at this there is 1 run of 1's of length 2 1 run of 1 run again of length 2 which is comprises of 2 minus 1. So, there are 2 runs of length 2, which means out of the 8 run 2 runs are of length 2 which means one fourth of all runs are of length 2. So, one fourth of runs are of length 2. Also, now I have you can count here I have 4 runs; 1, 2, 3, 4 runs of length 4. So, there are four runs of length 1, which means half of the runs are of length 1. So, half because 4 is half of 8, which is the total number of runs, so half runs are of length 1. That is a very interesting property. So, half of the runs are of length 1. One fourth of the runs are of length 2. One eight of the of the runs are of length 4 and so on and so forth. So, if write this thing half runs of length 1. One fourth runs of length 2 one-eighth runs of length 4 and so on and so forth. hat I half of the runs are of length one forth are of length 2 one eighth of length 4. Then for longer p n sequences, you can say one sixteenth of the runs of length 8 and so on and so forth. For that you can continue so this is known as the run length property of p n sequences. This has we said the name of this is the run length the earlier property that we have seen that the number of plus ones and minus ones are balanced is known as the balanced property, we called it property 1. But that is also known as the balance property the second property know as the run length property of the p n sequence any p n sequence. That is generated by the linear feedback shift register obese this run length property, and the third property is the most important property of p n sequences, which is known as the cyclic shift property. So, let us look at the third property of P N sequences property. 3 of P N sequences which is known also as the cyclic shift property. Now, let me write down again, the same P N sequence that I had written before that is minus 1 minus 1 minus 1 minus 1 1 1 minus 1 1 1 minus 1 minus 1 1 minus 1 1. Now, I will do so let me call this as code C 0 of n. This is the code C 0 of n. Now, what I am going to do is, I am going to take this code and shift it in time. So, I am going to consider C 0 of n minus 2 which is I am taking each shift of this code and shifting it to the right by 2 units. Remember f of t minus t naught is a shift in time by t naught similarly, C 0 n minus 2 is shifting in time by 2 chips. So, here the shifted code will look like this minus 1 will come over here this minus 1 will go over here. I am writing down under neat. so this is minus 1 minus 1 1 1 minus 1 1 1 minus 1 minus 1 1. I will take this last 2 chips and shift them to the front because this is the cyclic shift I am taking. I am shifting cyclically which is that I am shifting by 2 units and the last 2 chips, I will shift to the front. So, in the front I will have minus 1 comma 1, all right? I have C 0, so what I had now is I have a P N sequence and I have shifted P N sequence cyclically shifted in time by 2 units. Now, I am going to compute the correlation of these two shifted sequences. If these two sequences I define the correlation as 1 over n summation C 0 of n C 0 of n minus 2, that is I am taking C 0 n minus 2, which is what I have written down. I am going to compute the correlation that is how going to take the product chip by chip summation, sum all thus the products and then divide by n which in this cases is 15, because the length of the sequence is 15. So, let me first take the product minus 1 into minus 1 is plus 1 minus 1 into 1 is minus 1 minus 1 into minus 1 is 1 minus 1 into minus 1 is 1 1 into minus 1 is minus 1 1 into minus 1 is minus 1 1 into 1 is 1 minus 1 into 1 is minus 1 1 into 1 is 1 1 into minus 1 is minus 1 minus 1 into 1 is minus 1 1 into minus 1 is minus 1 minus 1 1 1. Now, let me add all this up when I sum all this thing up sum C 0 n C 0 n minus 2. You can verify this is 1 minus 1 0 1 2 minus 2 0 ,1 minus 1 0, 1 minus 1, 0 minus 3 1s minus 3 plus 2 this is minus 1. So, 1 over n summation C 0 n C 0 n minus 2 is simply minus 1 over n which in this case is minus 1 over 15. So, whatever is done let me recalculate because I went over a couple of steps i took the P N sequence C 0 of n I shifted the P N sequence by 2 chips. I am computing the correlation with the shifted sequence, which is defined as C 0 n. C 0 n minus 2 summation over n divided by capital N, which is the total length of the P N sequence I have to compute. The product chip by chip add this products and then divide by n which is fifteen and I am saying that sums C 0 n C 0 n minus 2 is minus 1 so that correlation is minus 1 over 15. You will find this is not unit to a shift by 2. If I take any shift other than the trivial shift which is 0 is no shift. So, if I take any finite shift that is 1 2 or even if I shift to the left if I take minus 1 minus 2 and I compute the correlation. The correlation will exactly the minus 1 over 15. So, the shift property states that the correlation for any shift other than 0 is minus 1 over, hence the correlation for any shift other than trivial 0 shift is minus 1 over n. In this case n is 15 the length is 15. So, the correlation is the correlation for the shift of 2 is minus 1 over 15. So, how about the correlation for any shift for the shift 0? We have not addressed that, but the correlation for the shift 0 is simple. That is for shift 0 the correlation is 1 over n C 0 n summation C 0 n into C 0 n itself because the shift is 0. So, C 0 n into the shifted which is C 0 of n itself, which is 1 over n summation C 0 square of n which is now if you look at it each C 0 of n is either plus 1 or minus 1 on both cases. C 0 square of n is 1 itself. Hence, summation C 0 square is nothing but, 1 over n summation of 1, which is essentially n over n which is equal to 1. Now, we have a much clear picture of the correlation structure for no shift. It is perfectly correlated that is the correlation is 1 as soon as you have any shift that is other than 0 that is 1 2 or minus 1 minus 2 the correlation falls down to minus 1 over n. And the larger the n the smaller is correlation is.. So, in fact let me write down here correlation of P N sequence this is 1 if the shift equal 0. It is minus 1 over n for any other non 0. For any other non 0 shift the correlation falls down to minus 1 over n. So, if I draw this, if I represent this pictorially at 0 the correlation is 1 and then it falls down to minus 1 over n for any other shifts. To the correlation looks like this is 1. At 0, the correlation is 1, at 1 2 or any other value it any other value it falls down to minus 1 to over n. So, this is minus 1 over n so it is 0 it is 1 outside of 0 that is for a either correlation that is for a lack that is delay that is positive or negative, it falls down to minus 1 over n and this is the correlation. Correlation diagram for a P N sequence this is how the correlation structure looks the P N sequence. And it is important to keep this in mind because code such P N sequences. Such codes form the heart of every C D M A system of the key component of every C D M A system. Hence, it is very important to understand the properties of this P N sequences in details. Hence, I urge you again to go back take a look at the several properties that he has discussed in P N sequences regarding linear feedback shift register and length of the sequences and the property of the P N sequences generated by this linear feedback shift registers or LFSR. Now, we will move on to studying some more properties of random sequences, which are going to be useful to us namely the cross correlation and the variance property. We can model these sequence during the study of C D M A. So, let me start this discussion on random spreading sequences. So, I will first start with random spreading sequence. Now, let me consider random sequence C i for 1 less than or equal to i less than equal to n, that is I am considering total of n such chips such that each C i is plus 1 or minus 1 with probability half. That is each chip is either plus 1 or minus 1 with probability half it is like tossing a coin. If the coin lands on heads it is minus 1 if the coin lands on a tails it is plus 1, so each chip is plus 1 or minus 1 with probability half and more importantly, each C i is independent of another chip C j each chip C i is independent of C j; that is why I do that, two different chips C 1 that is the C 1 C 2 C 3 or C 100. These chips are independent that is the random event that generates these two chips are event. It is like, I am tossing the coin every time I want to generate a chip. Now, I will consider two such spreading sequences C 0 i where C 0 is the sequence which contains n chips. Each chip plus or minus 1 independently will equal property of half and another sequence C 1 i also having the same property that C 1also has chips which are independent and plus or minus 1 with probability half. So, I will write here these are of length n that is 1 less than i less than equal to n 1 less than i less than equal to n and further C 0 and C 1 are themselves independent. Let us say C 0 and C 1 are independent that is the chips of C 0 have no relation to the chips of C 1that is both the sequence generated as independent random events. Now, let us look first at some property let us start with the very basic property. Let us say I take any single chip of any sequence let us say I take a chip of C 0. What is the expected value of a chip of a sequence? Let us say I take expected value of C 0 of i. I take some i th chip, I ask you what is expected value of this i th chip you can see that the each C i is plus 1 with the probability half minus 1 with the probability half. Hence, the expected value is nothing but, half into 1 plus half into minus 1 which is 0. Let us say expected else I take plus 1 and minus 1 with the equal probability. So, on average its value is 0. The expected value is half probability into value half into minus 1 into probability into value which is 0. Now, let me ask this question what is the time lag correlation of this chips sequence. For instance let me take a chip sequence C 0 correlated with the shifted version of the same chip sequence. Now, this is we are talking about it truly random sequence. We are not talking about the pseudo noise sequence. We are in fact talking about truly random chip sequence. The idea is for large sequences the pseudo noise sequences behave as if they are truly random sequence. Hence, we are studying the properties of this truly random sequence early. So, let us ask if I take a lag of k and compute the correlation, what is the expected value of or what is the second order moment of this. So let us start with the correlation. Let me define r of 0 0 of k that is for some lag k the self correlation of sequence 0 with itself as 1 over N summation C 0 i into C 0 i plus k, that is I am looking at the self correlation of the chip sequence and the chip sequence shifted by k. Now, if I look at the average expected value of this expected r 0 0 of k is expected value of 1 over N summation C 0 i C 0 i plus k. I will take, since the expectation operator is linear I will take the expectation inside that is 1 over N summation expected C 0 i into C 0 i plus k. Now, I will use the property that I have assumed before which is I assumed that each chip C i is independent of another chip C j. Hence C 0 i here is independent of C 0 i plus k. This means if there are two independent random variable expected of x comma y where a x and y are two independent random variables, which is simply expected x times expected y. Hence, I am going to simply write this as 1 over N sigma expected C 0 i expected C 0 i plus k which is equal to 1 over n. Now, we have seen in the previous case that expected C 0 i is 0 for any chip. Hence, each of this C 0 i expected C 0 i plus k are 0. Hence, this is 1 over N summation 0. This is 0, so the expected value of this correlation for any shift k remembers this is a non 0 shift, k is 0. Now, let us compute something that is more interesting and more useful, which is what is the variance of this? So, I will define r 0 0 square of k is nothing but take two such terms, take r 0 0 and take its product so r 0 0 k into r 0 0 k; that is summation over i C 0 i into C 0 i plus k into summation over j C 0 j C 0 j plus k. I am taking 2 r 0 0 terms multiplying them with each other these i and j are simply summation indexes, so do not kind get confused with them. They are simply same term represented by different summation indexes and i will write them as a double summation as summation over i summation over j C 0 i C 0 i plus k C 0 of j C 0 of j plus k. This r 0 0 of square of k alright there is also a factor I am sorry there is also a factor of 1 over N square that become 1 over N square and that also 1 over N square. Hence, expected value of r 0 0 square of k, which is the expected value, which is the second order moment of the correlation at the lag k is nothing but 1 over N square expected or I will take the expected value inside summation i summation j expected value of C 0 i C 0 i plus k C 0 j C 0 j plus k. Now, look at this expressions C 0 i C 0 i plus k C 0 j C 0 j plus k expected value. Now, if I is not equal to j then these chips are independent we said C 0 i is independent of C 0 of j. Because any two chips if an i is not equal to j the two chips are independent. Hence, expected value is expected value C 0 i into expected value C 0 j and so on. However, if i equals j then we have that is the only term that survives that will become 1 over N square sigma i expected of C 0 square i C 0 square C 0 square of i plus k, when i equals j. So, when i is not equal to j all such terms will becomes 0. When i equals j we have something interesting we have C 0 square of i C 0 square of i plus square. Remember C 0 i C 0 i plus k are both plus or minus 1. So, C 0 square i and C 0 square i plus k are both equal to 1. Hence this product is 1 so this will become 1 over N square summation of 1 which is essentially N over N square which is 1 over. Hence, expected let me write this down clearly over here expected r 0 0 square of k is 1 over N. So, given two random sequences first we have derived that expected r 0 0 k is 0 and the second moment expected r 0 0 square that is the variance of the shifted correlation is 1 over n. It decays as a function of N as the length, N increases this variance goes to 0. This is an important property when we study the behavior of C D M A system. So I urge you again to revise these concepts. I will end this lecture over here and we will continue starting with this in the next lecture. Thank very much.