1
00:00:06,960 --> 00:00:12,750
‫Welcomed the linear feedback shift register explain lecturer in this lecture I'm going to explain how

2
00:00:12,750 --> 00:00:21,220
‫linear feedback shift register operates and how like me use digital design what are linear feeback shift

3
00:00:21,220 --> 00:00:22,480
‫registers for.

4
00:00:22,780 --> 00:00:27,940
‫Well the common one is computers use these to generate pseudo random numbers.

5
00:00:28,150 --> 00:00:29,730
‫And what does a pseudo random number.

6
00:00:29,770 --> 00:00:36,730
‫Well I'll read up the definition a pseudo random means that one of a sequence of numbers generated by

7
00:00:36,970 --> 00:00:37,860
‫some algorithm.

8
00:00:37,870 --> 00:00:44,290
‫So as they have an even distribution over some range of values and minimal correlation between successive

9
00:00:44,290 --> 00:00:45,170
‫values.

10
00:00:45,580 --> 00:00:51,960
‫What this means is because we're using a specific algorithm we can't be by definition random.

11
00:00:51,970 --> 00:00:56,920
‫There is an equation that we use to determine what is the next number in this sequence.

12
00:00:56,920 --> 00:01:03,700
‫However if we have an evenly distributed it will appear as random and we use a value we call it a see

13
00:01:03,700 --> 00:01:08,800
‫value to determine what the initial value in our linear feeback shift register is.

14
00:01:08,800 --> 00:01:12,420
‫So you can't guess what the next value will be.

15
00:01:12,730 --> 00:01:15,640
‫And we can do with the pseudo random numbers.

16
00:01:15,640 --> 00:01:18,070
‫We can do the several different things.

17
00:01:18,100 --> 00:01:25,280
‫One most common is random number generation and your computer hasn't been doing a lab on the FPGA Marie-Louise's

18
00:01:25,390 --> 00:01:28,500
‫to generate what appears to be a random number.

19
00:01:28,570 --> 00:01:36,010
‫Also in cryptography this is very commonly used to decode certain messages and encode them so anyone

20
00:01:36,010 --> 00:01:41,710
‫else who looks at it can't make sense of it like encryption and communications it's commonly used to

21
00:01:41,710 --> 00:01:43,510
‫test communication systems.

22
00:01:43,660 --> 00:01:47,800
‫And also you can use these to instantiate very fast counters.

23
00:01:47,800 --> 00:01:52,690
‫Now the counters can be a little bit more confusing because they're not counting one two three four

24
00:01:52,690 --> 00:01:53,630
‫five six.

25
00:01:53,740 --> 00:01:59,380
‫You're kind of jumping all over the place but it's a lot faster than doing an additional processor only

26
00:01:59,380 --> 00:02:03,080
‫doing a shifting which we'll get into and show you here.

27
00:02:04,100 --> 00:02:09,990
‫So linear feedback shift register the input is a linear function of its previous input.

28
00:02:10,190 --> 00:02:15,400
‫And this is where we say it's a pseudo random because you're not by definition completely random.

29
00:02:15,410 --> 00:02:20,660
‫There is a linear relation from your previous input to your next output.

30
00:02:20,690 --> 00:02:27,650
‫So but what it will do is it appears to be random and the initial value reloading and the shift register

31
00:02:27,710 --> 00:02:29,930
‫is called The seed value.

32
00:02:29,930 --> 00:02:35,810
‫If you've ever programmed in C and you use the rand function they will tell you what you want to use

33
00:02:35,810 --> 00:02:41,740
‫the seed value and so they're using some sort of shift register to generate a random number.

34
00:02:41,750 --> 00:02:48,330
‫However you have to apply it with a seed value and you want to make that see value as random as possible.

35
00:02:48,590 --> 00:02:54,710
‫If you design your feedback function really well it will make the shift register have a very long cycle

36
00:02:54,940 --> 00:02:55,260
‫me.

37
00:02:55,300 --> 00:03:00,030
‫It'll take a long time until it repeats the same values over and over.

38
00:03:00,200 --> 00:03:04,550
‫So if it takes a long time to repeat the values over and over it will appear more random and that happens

39
00:03:04,730 --> 00:03:06,120
‫really quickly.

40
00:03:06,170 --> 00:03:09,770
‫People will be able to see that and say OK here's the pattern now.

41
00:03:09,800 --> 00:03:17,070
‫After 20 cycles it repeats the same pattern and therefore it's not really considered random.

42
00:03:17,510 --> 00:03:23,300
‫And as you said before you can use these to instantiate very fast counters because shifting is a lot

43
00:03:23,300 --> 00:03:25,950
‫faster than adding hardware.

44
00:03:26,390 --> 00:03:29,630
‫So let's take a look at a linear feedback shift register design.

45
00:03:29,630 --> 00:03:32,420
‫Here we have a forbit example.

46
00:03:32,570 --> 00:03:40,970
‫We've got four different flip flops and a single exclusive OR gate where we're exclusive offering the

47
00:03:40,970 --> 00:03:50,020
‫Y and Z outputs back to the input and to generator y x A W X Y Z outputs.

48
00:03:50,060 --> 00:03:52,470
‫So the four bits that were coming out.

49
00:03:52,580 --> 00:03:57,660
‫We're taking an exclusive oring the last two back to the input a linear feedback.

50
00:03:57,650 --> 00:04:01,420
‫That's our feedback exclusive OR gate is the feedback.

51
00:04:01,580 --> 00:04:05,930
‫And then our three different 3D flip flops is our shift register.

52
00:04:05,930 --> 00:04:09,430
‫Hence the name of linear feedback shift register.

53
00:04:09,990 --> 00:04:16,160
‫If we take a look at the design we just talked about there and look at the different values we're generating

54
00:04:16,160 --> 00:04:17,690
‫the decimal that we generate.

55
00:04:17,750 --> 00:04:29,900
‫If our seed value is 0 0 0 1 and we use that seclusive or we can see that values are 1 8 4 2 9 12 6

56
00:04:30,050 --> 00:04:36,270
‫11 5 10 13 14 15 7 and 3.

57
00:04:36,380 --> 00:04:38,270
‫If you look through it appears random.

58
00:04:38,270 --> 00:04:42,310
‫There doesn't necessarily appear to be a pattern between all these various numbers.

59
00:04:42,440 --> 00:04:44,350
‫They appear to be randomly generated.

60
00:04:44,350 --> 00:04:50,150
‫However if you go through you'll notice your count from 0 to 15 because there are four bits a total

61
00:04:50,150 --> 00:04:52,200
‫of 16 different combinations.

62
00:04:52,250 --> 00:04:56,230
‫We actually every number was counted from 1 to 15.

63
00:04:56,430 --> 00:05:01,490
‫So that's how you can use it as a fast counter because you know whenever your value repeats where you

64
00:05:01,490 --> 00:05:03,440
‫know you reached a count of 16.

65
00:05:03,680 --> 00:05:08,900
‫However it's a little harder to understand because it's not a success of counting like the humans would

66
00:05:08,900 --> 00:05:09,290
‫think.

67
00:05:09,290 --> 00:05:14,180
‫One two three four and said it's 1 8 4 2 and so on.

68
00:05:14,180 --> 00:05:21,050
‫Now it's a lot cheaper because we're only using four registers in a single exclusive OR gate.

69
00:05:22,010 --> 00:05:25,010
‫Now you understand have linear feedback shift registers operate.

70
00:05:25,010 --> 00:05:26,960
‫Let's start implementing one on your development for.