Protect your bits: Introduction to gr-fec
CC Attribution 2.0 Belgium:
You are free to use, adapt and copy, distribute and transmit the work or content in adapted or unchanged form for any legal purpose as long as the work is attributed to the author in the manner specified by the author or licensor.
Braun, Martin
In the 1940s, Shannon proved that we can transmit data error-free depending on rate and SNR. In practical radios, we need to employ forward error correction (FEC) to achieve those rates. GNU Radio has a built-in component to handle FEC, called gr-fec. After some basics of FEC, we will see how GNU Radio does this, and how it can be extended.
 Yeah, so, welcome. Hello again everyone. I just spoke an hour ago, I realized I didn't actually introduce myself, so my name is Martin. I work for a company called Edis Research, and I'm also involved in the GINradio project. Today I will be talking about GRFEC, and as a German living abroad, I'm trying to get to grips with this concept of humor, so I try and come up with a funny title. But actually, if I do this talk again, I will call it Shocking Tales of Redundancy. It's an even better title. If you don't understand why you might at the end of my talk, I just love this picture too. So, yeah, I'm going to talk about GRFEC. First, before I go into this, so GRFEC is about forward error correction. This is a part of every communication link. However, it's a very, very dense topic. So, this is something where typically you would have two semesters worth of classes just on the theory, but I actually also want to show you how to use it in GINradio in 20 minutes. So, I'm going to have to gloss over things very quickly, and really, this is designed for people who don't actually know a lot about GRFEC or people who don't know how to use it in GINradio, but I just want to sort of tease the topic for you. I don't want to actually give you the introduction because I just don't have the time to do that. Okay. So, let's start at the beginning. So, one of my personal heroes, Claude Shannon, came up with most of information theory in the 1940s. So, I think, I personally, as a scientist, I look up to him for various reasons. He was very smart, obviously. He was not fixated on theory or practice. He could do both. He built computers and whatnot. One of the things that people might have seen is this machine learning little mouse that goes through a labyrinth. It's crazy. But I think the most interesting contribution is this whole concept of information theory. So, I don't know, before he started working, I could have asked you how much information fits on this whiteboard. People would have said, what are you talking about? The question makes no sense. Not only did Shannon come up with the framework to understand and answer that question, he also came up with fundamental things like theories that are still valid today and they will never go away. They will remain. The most important one is the so-called Shannon limit, the Shannon theorem, which states that, given basically a signal to noise ratio and a bandwidth, there's a certain amount of data you can carry across that channel. The interesting thing about this, he did this first. This was basically the first thing in digital communication. He just laid the entire groundwork. He said, now everyone else can go figure out how to actually do that. But I mean, that is amazing. I find even more amazing the doing that the other way around. So, this is like the single equation. I left all the other equations out of this presentation. Very simple to understand. So, P plus n over n, you can also change it to 1 plus P over n. So, P over n being your SNR. If your SNR is 0 in linear, so minus infinity dB, which means you don't get anything across, this term becomes 0. So, obviously you can't transmit anything. If the dB, SNR is 0 dB equals to 1, you have 1 plus 1 equals 2, log 2 of 2 is 1, which means your channel rate is equal to the bandwidth. So, you have 1 megahertz, you get 1 megabit. Very simple. And it's true. And it's not like this is never going to change. Amazing. So, quick in a little bit, so I have some GRC examples. At the end, my final version, I have exactly one GRC example, which is not already in GUNRATIO, and I will upload it to the FOSM website afterwards. But disclaimer, I used main 3.7 for this branch. So, we are currently working on GUNRATIO 3.8. It still has too many bugs for me to actually run this stuff. So, there's a feature called bus ports, which is currently broken. I'm sorry. The point is, GRC files don't have a, I am not quite sure if they have a version detection field, so if you try and run this with master branch, it won't work. All right. So, here's, I'm not good at computer graphics, so this is how I make pictures. This is just a very hypothetical setup. So, we have a transmit antenna, receive antenna. I use the number 10 a lot because in DB, that works out. I have a transmit gain of 10 dB, a receive gain of 10 dB, a noise figure of 10 dB, 10 kilometers distance, and these are all very even numbers. I transmit, I use free space equations to just estimate my receive power. Really, the precise numbers don't really matter. The point is, I'm going to exclude all effects other than thermal noise, which is a very, very strong assumption. Like, you typically, you do worse than that. Then I say, okay, like I put in like sort of the basic like first year electrical engineering equations, and I find that I have a thermal noise of minus one or 3 dBm, and then approximately 10 dB above that, I have my noise power. And I'm going to do some other simplifications, which aren't quite accurate. But hey, I've already graduated, so people can take that away from me. Turns out that the equation earlier states we should be able to achieve about 3 megabits worth of bit rate with an arbitrarily low error rate. And I'm like, okay, arbitrarily low, okay, I want one bit error in like 10 billion years. Like, can we do that? So, wait a minute. Oh yeah, uncoded.grc is here. So, this is like stripped everything that is, this is super, super like simplified. There is no synchronization here. There's not even a channel. Basically, I'm just creating BPSK symbols. And I do that because I can equate SNR and EBOVN0 and add some noise. And then I turn them back to bits, and then I measure the bit error rate. So, and what you care about, which for some reason is failing me right now, is the bit error rate is actually zero. And that's not supposed to happen. So, this number should be higher than that. It should be about 10 to the minus 6 or minus 4 or something like that. Like, this is what I get for doing demos. Oh, I was playing around with the amplitude. Yeah, I'm just going to crank it up for now. Where's my slider? Oh man, this is like the simplest possible. I'm just going to change this to some other random number. Whoops, that's a bit much. Ah, whatever. It doesn't matter. The point is I'm going to add some noise. And you will see, I mean, I kind of gave it a bit of a assume no one else would expect that. If you, let me just stop that for a second and zoom in. So, I have like plus one minus one symbols, but I've added so much noise that it looks like this. And then, like a whole bunch of these bits come out wrong. Okay, so now I fudge the noise amplitude just now. So, I don't actually have that SNR that I mentioned earlier. But if I had the SNR, it would still be like that. So, if Shannon says, well, I can transmit like a whole bunch of bits, like three megabits, like without error, and I'm transmitting one megabit with errors, like what am I doing wrong? And the answer is, well, I guess my transceiver is not sufficiently complicated, because that's the beauty of the original paper by Shannon. He says, a sufficiently complicated encoding system will achieve that. Now, you go find out that encoding system. That's my time. Now, if you look at this setup that I used, like I'm transmitting plus one minus one bits, but I add noise. So, I actually get this probability distribution of received symbols. And as soon as they sort of move over here, I will interpret the plus one symbol as minus one symbol, which is a bit error. This here is something I can actually trivially calculate for simple schemes like mine, using like the error function, like the Gaussian error function. So, I can actually predict accurately my bit error rate. But that doesn't help me, because I wanted to transmit without any bit errors. And that's where we need forward error correction. And what forward error correction does in a nutshell is it adds redundancy. Now, this is where, like the next two slides is where I skip over two semesters of classes in one minute. So, there's no way I can actually sort of relay the full information of it. But consider this case here. I want to transmit four bits, one, one, zero, one. And you might say, okay, well, I'm going to just put them onto plus minus one symbol. So, I can, you know, this could be on a wire or this could be over the air through some other kind of modulation. So, here's my bits, one, one, zero, one, four bits. But like, who says that I have to do that? Like, no one. Like, I can do whatever I want. As long as my receiver knows how I, like, put this into some physically, physical representation, I could do this. One, zero, one, zero, one, zero, one. And you'd say, well, wait a minute, that makes no sense. Like, this bit sequence is not in this bit sequence. And I said, so what? Like, I'm making up my encoder here. So, like, as long as my receiver knows that one, zero, one, zero, one, zero, one, zero equals one, zero, one, one, zero, one. One, I'm done. And you said, okay, well, fine. So, what do we have here? First of all, like I said, we don't have the original bits in this code word, which is not necessary. Like, a lot of forward error correction codes actually do keep the original bits, but it's not a requirement. But what's more interesting is that I have more bits now. And I have to transmit them in the same amount of time if I want to sort of, like, not change my actual setup. Which has some interesting implications. Because if I just transmit these slower, then I might also keep the original one, transmit that a bit slower, which means I have a little bit more power. And that will also increase my bit error rate. So, this is where it gets really, really difficult. And this is where I'm just going to have to jump over it and say, you have to come up with this encoding such that sending more bits in the same amount of time, which increases the bit error rate of the individual symbol is still better than doing this. And that's what people have, you know, many PhD theses have been written on this topic. There's a couple of words that you, I just want to say the words out loud, you've heard them once. If you know forward error correction, then this makes sense. Otherwise, just keep the sort of, like, basically say, I, okay, I heard it in Martin's talk. I don't know what it means, but it doesn't matter. We talk about a systematic code if the uncoded data is included in the encoding. Encoding increases latency. It's a problem. We have to deal with it somehow. We can have multiple codes and we can combine them. And then we typically, you know, we call that concatenation. We, like I said earlier, you have to have a code that is better with more shorter bits than the uncoded one. And if it is better, then we say we have a coding gain. And this is also a concept that I need like two or three slides and I think you'd get it, but I'm just going to skip over that. Puncturing is an interesting feature that we can employ. You know, when we add redundancy, we send more bits. So, but I can just, I can just also leave some of those bits out again. So we first add bits, we take out other bits. Why does that make sense? Yes, it does make sense because it allows us to change the rate at which we encode. Just like I said, this is just a word that I wanted you to have heard. I'm just going to give you a couple of examples. So how, like, like, you would think like someone can figure out the way to do forward error correction, but that is not correct because all applications are different. Consider a satellite talking to a ground station. Like, there is nothing between the satellite and the ground station. This is a point-to-point link. Like, I mean, sure, maybe like a plane or something will fly through the beam briefly, but it's not a big deal. The only thing that matters is that the satellite is moving around a little bit. Like, relative, if it's like a geo-satellite, for example, if it's like any other satellite, it'll move around a lot. Which means like the distance here changes. So we have changes in our SNR, but they are usually predictable. So if we want to have a code for this kind of link, it'll be different than what a CD player does. So if you consider a CD player, like, you have a scratch on a CD, that means like all of these bits are fine, and then like poof, like a whole bunch of bits are gone, and then you continue here with like good bits. Like, this is a different kind of error that you obviously need a different kind of code to work out. And then mobile phones have like the worst constraints of all. Like literally everything matters in a mobile phone. We have bad SNR, typically. You have Doppler shifts. You have all kinds of like channels that look like this. But also people want to watch YouTube immediately, and they want to be on the phone, so they have to do everything quickly. So this is where it gets really interesting. And these are just a couple of other names of codes that you should have heard before. So if you go to school and learn about codes, often they like the first code they talk about are Hamming codes. They're not really that relevant in mobile communications. And convolutional codes, which are used a lot, like Wi-Fi, for example. Turbo codes and polar codes are just names of codes that are used in wireless communications. And then there's a whole bunch of other codes. You can see like people have thought about this a lot. All right, what's my time? Okay, so this was basically the theory. Thank you. This was the theory, except I left out all the theory. But we have most of this in-guna radio in a modular fashion, which is useful because you don't actually have to understand all of the theory. And trust me, most people who do work in wireless communications don't understand all of the theory. Not because they're lazy. It's just a lot of stuff to put inside your head. And if you're building like a point-to-point wireless communication link, like you have so many things to worry about, like understanding every little nuance of the equations, of forward error correction, is a lot to ask. So that is also true for equalizers, synchronizers, etc., which we all have in-guna radio. So a GI-FEC fits well into that category. Okay, so you build a guna radio, you make sure the GI-FEC is enabled. There's usually no reason to disable it. And then you have FEC blocks available. And it also has a bunch of examples, and I will show some of those. So the first example that I want to show you is called FECAPID-CODIS.GRC. And it is actually part of the source stream. This is squashed up a little bit, unfortunately. Even on the newer HD screens, we don't have that much space available. I'll try and untangle it a little bit. So what do we do here? This is effectively the same example that I showed you earlier. Except we don't have any noise anymore. And what we do is we generate bits in this block, and then we send them to the receiver on four different paths. And like I said, this is just an example. This is not actually a useful communication link. So we take bits, we encode them, we turn them into BPSK symbols. Like this was the plus one, minus one representations of our bits. And then we decode those. And then we just look at the result. And we have three different codes here. So, and you will notice that the block is always the same, even though we have different codes. So let me just run this real quick. It's not the most enlightening visualization here, but it is just nice to see that things are obviously working out. So the random bits that I'm generating are coming out. Identically in all four cases. You can see I have my un-coded bits, and I have a thing called a dummy encoder, a repetition encoder, and a convolutional encoder. And it's maybe not obvious, but basically this is just like the representation of the bits, and they're all the same. So that's why you can only see one line here, which is black. Which means our encoding decoding is doing something correctly. But the key concept that I wanted to show you with this example is not like the visualization, rather it's like how the encoders are set up. So like I said, we have bits generated here, and they go into this block called the FEC extended encoder. If you look at its parameters, it has this thing called an encoder object here. And if I scroll down a little bit, I have different encoder definitions. So I have a CCSDS encoder, dummy encoder, I'll talk about that in a sec, and a repetition encoder, and all the code specific details are hidden away in that block. So I'll open this for a sec, and you'll see there's like a frame size, a streaming behavior. These are all parameters that other codes don't necessarily have. And then there's an equivalent decoder object that has a bunch of other settings. But the thing to keep in mind is we have these guys here, these are the actual encoders, and these are the blocks that capture those encoders and actually run them. So the distinction that we make here is blocks versus kernels. I need to hurry up a little bit. So yeah, we have this guy, it's the block, and then you pull in the encoder, and this thing we call a kernel. And these are exchangeable, and you can reload your own and write them very quickly, and you don't have to worry about the radio as much, which makes it easy to integrate it with other libraries and our SIMD extensions. So there's three types of blocks. Actually, there's six types of blocks, and every block has an extended and a non-extended version. And the extended version, for all, like for everyone who's starting, is the only one that you need, because it's the one that adds like a whole bunch of sugar and like adds like some Python to make it easier to use. And then really you just have to ask yourself, do you want like sort of this continuous streaming model? Then you use this guy. Are you using ASIC messages? Then you use this guy. Or are you using tag stream blocks, which are streams with boundaries, then you use this block. But you could pull in the same kernel in all cases. So as you can tell by the signatures here, the purple versus the orange, the encoder takes actual bits and outputs actual bits, and then you modulate, whereas the decoder takes soft bits. So this is a floating point representation of your bit that includes uncertainty. So we differentiate between soft and hard decision decoding, but like no one does hard decision decoding. And in a soft decision decoding, you don't just give it a plus one or a minus one or a one or a zero. Rather, you give it a spectrum of values where the absolute value sort of determines your certainty. You could also give it a zero, which is neither a plus one or a minus one, to indicate that you have no idea what the bit should have been and then the decoder can handle that. The other options that are interesting are the threading model. If you have lots of stuff going on, and you have plenty of cores, there might be some process optimizations that you can get. And puncturing is handled by the blocks and not by the kernels, because that's an identical process. The available kernels that we have are, I mentioned these guys, polar and turbo codes, LDPC codes. So these three codes are important for wireless communications. So polar codes will be in 5G new radio, turbo codes and LDPC codes, and polar codes are in 5G new radio. Turbo codes are used in LTE, for example, convolutional codes in Wi-Fi and in GSM. The dummy encoder is actually not an encoder. It's more of a debugging block. It doesn't actually do anything. The repetition encoder is an encoder that often comes up in classes, where what you do in a repetition encoder is you send the bit multiple times. Turns out that's actually not very useful. I'll show you why in a sec. Now, my first example was very, very brief. There's another one that I picked out as a more useful example, which is the polar encoder. So the polar encoder once again has a comparison between what happens when you encode and when you don't encode. So the right-hand side is what I showed earlier. It's the exact same thing. I have noise and bits, and I don't do anything smart, and I end up with bit errors, 10 to the minus 3. So every thousandth bit is wrong. Whereas if I add polar encoding and decoding, it's fine. Why is that? Because Shannon says it's fine within the parameters that I set, and polar codes actually achieve the Shannon rate at sufficiently long block lengths. That means long latency, but it also means no bit errors. Yes. Eventually, even the polar codes give out advice. I think, yeah, there we go. Eventually, they also start having bit errors, and that's because my block lengths aren't actually that long, and maybe I'm also leaving the Shannon limit, but I have much more space to work with. Yeah, the flow graph is pretty much the same as before, so I'm just going to hurry up because I'm running out of time here. The other thing that you can do with GINradio is BER simulations, but it's questionable whether or not that is actually the right tool to do that. The way you do that is a little bit different than what you would in your typical scripted application, because what it'll do is it'll run all of these at once, and then continuously update this. Why is this useful? Well, because GINradio is a continuous streaming model, and you would really only use this to basically test the various encoders versus one another. Now, I also want to caution people to interpret this correctly. I thought this was interesting. This is a little bit of a dangerous graph. Why is that? The lowest bit error rate is related to the convolutional coder, so LEPC and T-Turbo codes are worse. And also we have this red line versus this blue line. This doesn't make sense. Something is not correct. How on earth can I transmit more data if I repeat bits? And why is this better than this? The reason is I'm not actually comparing apples to apples here. In the red case, I'm actually transmitting less data, like one-third the amount of data per second. And the same is true for the rest. I haven't basically corrected for the different rates that I've achieved. Okay, like I said, running out of time. So this is basically more of a debugging tool. If you want to do a theoretical research, this is one of the rare cases where I would probably not recommend GINradio, but the fact that our kernels are separate from our block model means you can still share code very easily. Oh, no, okay, that was the example I just wanted to show you. And before I conclude, I just wanted to name a couple of people that worked very hard on this. So Nick McCarthy, I think, came up with the original FEC API. Tim was probably involved. But then there's a couple of people who contributed like the really relevant codes. Johannes, Manu and Tracy were actually GSOC students. And Johannes spoke about his codes, his PolarCodes implementation, GICon16. This is a link to the actual talk. There was another talk about PolarCodes at the same conference, but they were not upstreamed into GIFEC. Okay, so some redundancy is good. Some is bad. FEC is definitely of the good variety. I like the modular approach. It fits very well into GUNRATIO. We do need help making sure those. And we have a lot of really good codes in there, but we can always increase their speed. That's something that is very difficult. And as new wireless protocols appear in the wild, we also need more different types of encoders anyway. So yeah, I hope people consider taking a look at GIFEC. And thank you very much. Thank you.
 Yeah, so, welcome.  Hello again everyone.  I just spoke an hour ago,  I realized I didn't actually introduce myself,  so my name is Martin.  I work for a company called Edis Research,  and I'm also involved in the GINradio project.  Today I will be talking about GRFEC,  and as a German living abroad,  I'm trying to get to grips with this concept of humor,  so I try and come up with a funny title.  But actually, if I do this talk again,  I will call it Shocking Tales of Redundancy.  It's an even better title.  If you don't understand why you might at the end of my talk,  I just love this picture too.  So, yeah, I'm going to talk about GRFEC.  First, before I go into this,  so GRFEC is about forward error correction.  This is a part of every communication link.  However, it's a very, very dense topic.  So, this is something where typically you would have  two semesters worth of classes just on the theory,  but I actually also want to show you how to use it  in GINradio in 20 minutes.  So, I'm going to have to gloss over things very quickly,  and really, this is designed for people who don't actually  know a lot about GRFEC or people who don't know how to use it  in GINradio, but I just want to sort of tease the topic for you.  I don't want to actually give you the introduction  because I just don't have the time to do that.  Okay. So, let's start at the beginning.  So, one of my personal heroes, Claude Shannon,  came up with most of information theory in the 1940s.  So, I think, I personally, as a scientist,  I look up to him for various reasons.  He was very smart, obviously.  He was not fixated on theory or practice.  He could do both.  He built computers and whatnot.  One of the things that people might have seen is  this machine learning little mouse that goes through a labyrinth.  It's crazy.  But I think the most interesting contribution is  this whole concept of information theory.  So, I don't know,  before he started working,  I could have asked you how much information fits on this whiteboard.  People would have said, what are you talking about?  The question makes no sense.  Not only did Shannon come up with the framework to understand and answer that question,  he also came up with fundamental things like  theories that are still valid today and they will never go away.  They will remain.  The most important one is the so-called Shannon limit,  the Shannon theorem, which states that,  given basically a signal to noise ratio and a bandwidth,  there's a certain amount of data you can carry across that channel.  The interesting thing about this, he did this first.  This was basically the first thing in digital communication.  He just laid the entire groundwork.  He said, now everyone else can go figure out how to actually do that.  But I mean, that is amazing.  I find even more amazing the doing that the other way around.  So, this is like the single equation.  I left all the other equations out of this presentation.  Very simple to understand.  So, P plus n over n, you can also change it to 1 plus P over n.  So, P over n being your SNR.  If your SNR is 0 in linear, so minus infinity dB,  which means you don't get anything across, this term becomes 0.  So, obviously you can't transmit anything.  If the dB, SNR is 0 dB equals to 1, you have 1 plus 1 equals 2,  log 2 of 2 is 1, which means your channel rate is equal to the bandwidth.  So, you have 1 megahertz, you get 1 megabit.  Very simple.  And it's true.  And it's not like this is never going to change.  Amazing.  So, quick in a little bit, so I have some GRC examples.  At the end, my final version, I have exactly one GRC example,  which is not already in GUNRATIO, and I will upload it to the FOSM website afterwards.  But disclaimer, I used main 3.7 for this branch.  So, we are currently working on GUNRATIO 3.8.  It still has too many bugs for me to actually run this stuff.  So, there's a feature called bus ports, which is currently broken.  I'm sorry.  The point is, GRC files don't have a, I am not quite sure if they have a version  detection field, so if you try and run this with master branch, it won't work.  All right.  So, here's, I'm not good at computer graphics, so this is how I make pictures.  This is just a very hypothetical setup.  So, we have a transmit antenna, receive antenna.  I use the number 10 a lot because in DB, that works out.  I have a transmit gain of 10 dB, a receive gain of 10 dB, a noise figure of 10 dB,  10 kilometers distance, and these are all very even numbers.  I transmit, I use free space equations to just estimate my receive power.  Really, the precise numbers don't really matter.  The point is, I'm going to exclude all effects other than thermal noise, which is a very, very  strong assumption.  Like, you typically, you do worse than that.  Then I say, okay, like I put in like sort of the basic like first year electrical engineering  equations, and I find that I have a thermal noise of minus one or 3 dBm, and then approximately  10 dB above that, I have my noise power.  And I'm going to do some other simplifications, which aren't quite accurate.  But hey, I've already graduated, so people can take that away from me.  Turns out that the equation earlier states we should be able to achieve about 3 megabits worth of  bit rate with an arbitrarily low error rate.  And I'm like, okay, arbitrarily low, okay, I want one bit error in like 10 billion years.  Like, can we do that?  So, wait a minute.  Oh yeah, uncoded.grc is here.  So, this is like stripped everything that is, this is super, super like simplified.  There is no synchronization here.  There's not even a channel.  Basically, I'm just creating BPSK symbols.  And I do that because I can equate SNR and EBOVN0 and add some noise.  And then I turn them back to bits, and then I measure the bit error rate.  So, and what you care about, which for some reason is failing me right now,  is the bit error rate is actually zero.  And that's not supposed to happen.  So, this number should be higher than that.  It should be about 10 to the minus 6 or minus 4 or something like that.  Like, this is what I get for doing demos.  Oh, I was playing around with the amplitude.  Yeah, I'm just going to crank it up for now.  Where's my slider?  Oh man, this is like the simplest possible.  I'm just going to change this to some other random number.  Whoops, that's a bit much.  Ah, whatever.  It doesn't matter.  The point is I'm going to add some noise.  And you will see, I mean, I kind of gave it a bit of a assume no one else would expect that.  If you, let me just stop that for a second and zoom in.  So, I have like plus one minus one symbols, but I've added so much noise that it looks like this.  And then, like a whole bunch of these bits come out wrong.  Okay, so now I fudge the noise amplitude just now.  So, I don't actually have that SNR that I mentioned earlier.  But if I had the SNR, it would still be like that.  So, if Shannon says, well, I can transmit like a whole bunch of bits, like three megabits,  like without error, and I'm transmitting one megabit with errors, like what am I doing wrong?  And the answer is, well, I guess my transceiver is not sufficiently complicated,  because that's the beauty of the original paper by Shannon.  He says, a sufficiently complicated encoding system will achieve that.  Now, you go find out that encoding system.  That's my time.  Now, if you look at this setup that I used, like I'm transmitting plus one minus one bits,  but I add noise.  So, I actually get this probability distribution of received symbols.  And as soon as they sort of move over here, I will interpret the plus one symbol as minus one symbol,  which is a bit error.  This here is something I can actually trivially calculate for simple schemes like mine,  using like the error function, like the Gaussian error function.  So, I can actually predict accurately my bit error rate.  But that doesn't help me, because I wanted to transmit without any bit errors.  And that's where we need forward error correction.  And what forward error correction does in a nutshell is it adds redundancy.  Now, this is where, like the next two slides is where I skip over two semesters of classes in one minute.  So, there's no way I can actually sort of relay the full information of it.  But consider this case here.  I want to transmit four bits, one, one, zero, one.  And you might say, okay, well, I'm going to just put them onto plus minus one symbol.  So, I can, you know, this could be on a wire or this could be over the air through some other kind of modulation.  So, here's my bits, one, one, zero, one, four bits.  But like, who says that I have to do that?  Like, no one.  Like, I can do whatever I want.  As long as my receiver knows how I, like, put this into some physically, physical representation,  I could do this.  One, zero, one, zero, one, zero, one.  And you'd say, well, wait a minute, that makes no sense.  Like, this bit sequence is not in this bit sequence.  And I said, so what?  Like, I'm making up my encoder here.  So, like, as long as my receiver knows that one, zero, one, zero, one, zero, one, zero equals one, zero, one, one, zero, one.  One, I'm done.  And you said, okay, well, fine.  So, what do we have here?  First of all, like I said, we don't have the original bits in this code word, which is not necessary.  Like, a lot of forward error correction codes actually do keep the original bits, but it's not a requirement.  But what's more interesting is that I have more bits now.  And I have to transmit them in the same amount of time if I want to sort of, like, not change my actual setup.  Which has some interesting implications.  Because if I just transmit these slower, then I might also keep the original one, transmit that a bit slower,  which means I have a little bit more power.  And that will also increase my bit error rate.  So, this is where it gets really, really difficult.  And this is where I'm just going to have to jump over it and say, you have to come up with this encoding such that sending more bits in the same amount of time,  which increases the bit error rate of the individual symbol is still better than doing this.  And that's what people have, you know, many PhD theses have been written on this topic.  There's a couple of words that you, I just want to say the words out loud, you've heard them once.  If you know forward error correction, then this makes sense.  Otherwise, just keep the sort of, like, basically say, I, okay, I heard it in Martin's talk.  I don't know what it means, but it doesn't matter.  We talk about a systematic code if the uncoded data is included in the encoding.  Encoding increases latency.  It's a problem. We have to deal with it somehow.  We can have multiple codes and we can combine them.  And then we typically, you know, we call that concatenation.  We, like I said earlier, you have to have a code that is better with more shorter bits than the uncoded one.  And if it is better, then we say we have a coding gain.  And this is also a concept that I need like two or three slides and I think you'd get it,  but I'm just going to skip over that.  Puncturing is an interesting feature that we can employ.  You know, when we add redundancy, we send more bits.  So, but I can just, I can just also leave some of those bits out again.  So we first add bits, we take out other bits.  Why does that make sense?  Yes, it does make sense because it allows us to change the rate at which we encode.  Just like I said, this is just a word that I wanted you to have heard.  I'm just going to give you a couple of examples.  So how, like, like, you would think like someone can figure out the way to do forward error correction,  but that is not correct because all applications are different.  Consider a satellite talking to a ground station.  Like, there is nothing between the satellite and the ground station.  This is a point-to-point link.  Like, I mean, sure, maybe like a plane or something will fly through the beam briefly,  but it's not a big deal.  The only thing that matters is that the satellite is moving around a little bit.  Like, relative, if it's like a geo-satellite, for example,  if it's like any other satellite, it'll move around a lot.  Which means like the distance here changes.  So we have changes in our SNR, but they are usually predictable.  So if we want to have a code for this kind of link,  it'll be different than what a CD player does.  So if you consider a CD player, like, you have a scratch on a CD,  that means like all of these bits are fine, and then like poof,  like a whole bunch of bits are gone, and then you continue here with like good bits.  Like, this is a different kind of error that you obviously need a different kind of code to work out.  And then mobile phones have like the worst constraints of all.  Like literally everything matters in a mobile phone.  We have bad SNR, typically.  You have Doppler shifts.  You have all kinds of like channels that look like this.  But also people want to watch YouTube immediately,  and they want to be on the phone, so they have to do everything quickly.  So this is where it gets really interesting.  And these are just a couple of other names of codes that you should have heard before.  So if you go to school and learn about codes,  often they like the first code they talk about are Hamming codes.  They're not really that relevant in mobile communications.  And convolutional codes, which are used a lot, like Wi-Fi, for example.  Turbo codes and polar codes are just names of codes that are used in wireless communications.  And then there's a whole bunch of other codes.  You can see like people have thought about this a lot.  All right, what's my time?  Okay, so this was basically the theory.  Thank you.  This was the theory, except I left out all the theory.  But we have most of this in-guna radio in a modular fashion,  which is useful because you don't actually have to understand all of the theory.  And trust me, most people who do work in wireless communications  don't understand all of the theory.  Not because they're lazy.  It's just a lot of stuff to put inside your head.  And if you're building like a point-to-point wireless communication link,  like you have so many things to worry about,  like understanding every little nuance of the equations,  of forward error correction, is a lot to ask.  So that is also true for equalizers, synchronizers, etc.,  which we all have in-guna radio.  So a GI-FEC fits well into that category.  Okay, so you build a guna radio, you make sure the GI-FEC is enabled.  There's usually no reason to disable it.  And then you have FEC blocks available.  And it also has a bunch of examples, and I will show some of those.  So the first example that I want to show you is called FECAPID-CODIS.GRC.  And it is actually part of the source stream.  This is squashed up a little bit, unfortunately.  Even on the newer HD screens, we don't have that much space available.  I'll try and untangle it a little bit.  So what do we do here?  This is effectively the same example that I showed you earlier.  Except we don't have any noise anymore.  And what we do is we generate bits in this block,  and then we send them to the receiver on four different paths.  And like I said, this is just an example.  This is not actually a useful communication link.  So we take bits, we encode them, we turn them into BPSK symbols.  Like this was the plus one, minus one representations of our bits.  And then we decode those.  And then we just look at the result.  And we have three different codes here.  So, and you will notice that the block is always the same,  even though we have different codes.  So let me just run this real quick.  It's not the most enlightening visualization here,  but it is just nice to see that things are obviously working out.  So the random bits that I'm generating are coming out.  Identically in all four cases.  You can see I have my un-coded bits,  and I have a thing called a dummy encoder,  a repetition encoder, and a convolutional encoder.  And it's maybe not obvious, but basically this is just like  the representation of the bits, and they're all the same.  So that's why you can only see one line here, which is black.  Which means our encoding decoding is doing something correctly.  But the key concept that I wanted to show you with this example  is not like the visualization,  rather it's like how the encoders are set up.  So like I said, we have bits generated here,  and they go into this block called the FEC extended encoder.  If you look at its parameters,  it has this thing called an encoder object here.  And if I scroll down a little bit,  I have different encoder definitions.  So I have a CCSDS encoder, dummy encoder,  I'll talk about that in a sec,  and a repetition encoder,  and all the code specific details are hidden away in that block.  So I'll open this for a sec,  and you'll see there's like a frame size, a streaming behavior.  These are all parameters that other codes don't necessarily have.  And then there's an equivalent decoder object  that has a bunch of other settings.  But the thing to keep in mind is we have  these guys here, these are the actual encoders,  and these are the blocks that capture those encoders  and actually run them.  So the distinction that we make here is blocks versus kernels.  I need to hurry up a little bit.  So yeah, we have this guy, it's the block,  and then you pull in the encoder,  and this thing we call a kernel.  And these are exchangeable,  and you can reload your own and write them very quickly,  and you don't have to worry about the radio as much,  which makes it easy to integrate it with other libraries  and our SIMD extensions.  So there's three types of blocks.  Actually, there's six types of blocks,  and every block has an extended and a non-extended version.  And the extended version, for all,  like for everyone who's starting,  is the only one that you need,  because it's the one that adds like a whole bunch of sugar  and like adds like some Python to make it easier to use.  And then really you just have to ask yourself,  do you want like sort of this continuous streaming model?  Then you use this guy.  Are you using ASIC messages?  Then you use this guy.  Or are you using tag stream blocks,  which are streams with boundaries,  then you use this block.  But you could pull in the same kernel in all cases.  So as you can tell by the signatures here,  the purple versus the orange,  the encoder takes actual bits and outputs actual bits,  and then you modulate,  whereas the decoder takes soft bits.  So this is a floating point representation  of your bit that includes uncertainty.  So we differentiate between soft and hard decision decoding,  but like no one does hard decision decoding.  And in a soft decision decoding,  you don't just give it a plus one or a minus one  or a one or a zero.  Rather, you give it a spectrum of values  where the absolute value sort of determines your certainty.  You could also give it a zero,  which is neither a plus one or a minus one,  to indicate that you have no idea what the bit should have been  and then the decoder can handle that.  The other options that are interesting are the threading model.  If you have lots of stuff going on,  and you have plenty of cores,  there might be some process optimizations that you can get.  And puncturing is handled by the blocks and not by the kernels,  because that's an identical process.  The available kernels that we have are,  I mentioned these guys, polar and turbo codes, LDPC codes.  So these three codes are important for wireless communications.  So polar codes will be in 5G new radio,  turbo codes and LDPC codes,  and polar codes are in 5G new radio.  Turbo codes are used in LTE, for example,  convolutional codes in Wi-Fi and in GSM.  The dummy encoder is actually not an encoder.  It's more of a debugging block.  It doesn't actually do anything.  The repetition encoder is an encoder that often comes up in classes,  where what you do in a repetition encoder  is you send the bit multiple times.  Turns out that's actually not very useful.  I'll show you why in a sec.  Now, my first example was very, very brief.  There's another one that I picked out as a more useful example,  which is the polar encoder.  So the polar encoder once again has a comparison  between what happens when you encode and when you don't encode.  So the right-hand side is what I showed earlier.  It's the exact same thing.  I have noise and bits, and I don't do anything smart,  and I end up with bit errors, 10 to the minus 3.  So every thousandth bit is wrong.  Whereas if I add polar encoding and decoding, it's fine.  Why is that?  Because Shannon says it's fine within the parameters that I set,  and polar codes actually achieve the Shannon rate at sufficiently long block lengths.  That means long latency, but it also means no bit errors.  Yes.  Eventually, even the polar codes give out advice.  I think, yeah, there we go.  Eventually, they also start having bit errors,  and that's because my block lengths aren't actually that long,  and maybe I'm also leaving the Shannon limit,  but I have much more space to work with.  Yeah, the flow graph is pretty much the same as before,  so I'm just going to hurry up because I'm running out of time here.  The other thing that you can do with GINradio is BER simulations,  but it's questionable whether or not that is actually the right tool to do that.  The way you do that is a little bit different  than what you would in your typical scripted application,  because what it'll do is it'll run all of these at once,  and then continuously update this.  Why is this useful?  Well, because GINradio is a continuous streaming model,  and you would really only use this to basically test  the various encoders versus one another.  Now, I also want to caution people to interpret this correctly.  I thought this was interesting.  This is a little bit of a dangerous graph.  Why is that?  The lowest bit error rate is related to the convolutional coder,  so LEPC and T-Turbo codes are worse.  And also we have this red line versus this blue line.  This doesn't make sense.  Something is not correct.  How on earth can I transmit more data if I repeat bits?  And why is this better than this?  The reason is I'm not actually comparing apples to apples here.  In the red case, I'm actually transmitting less data,  like one-third the amount of data per second.  And the same is true for the rest.  I haven't basically corrected for the different rates that I've achieved.  Okay, like I said, running out of time.  So this is basically more of a debugging tool.  If you want to do a theoretical research,  this is one of the rare cases where I would probably not recommend GINradio,  but the fact that our kernels are separate from our block model  means you can still share code very easily.  Oh, no, okay, that was the example I just wanted to show you.  And before I conclude, I just wanted to name a couple of people  that worked very hard on this.  So Nick McCarthy, I think, came up with the original FEC API.  Tim was probably involved.  But then there's a couple of people who contributed  like the really relevant codes.  Johannes, Manu and Tracy were actually GSOC students.  And Johannes spoke about his codes, his PolarCodes implementation,  GICon16.  This is a link to the actual talk.  There was another talk about PolarCodes at the same conference,  but they were not upstreamed into GIFEC.  Okay, so some redundancy is good.  Some is bad.  FEC is definitely of the good variety.  I like the modular approach.  It fits very well into GUNRATIO.  We do need help making sure those.  And we have a lot of really good codes in there,  but we can always increase their speed.  That's something that is very difficult.  And as new wireless protocols appear in the wild,  we also need more different types of encoders anyway.  So yeah, I hope people consider taking a look at GIFEC.  And thank you very much.  Thank you.
Protect_your_bits__Introduction_to_gr-fec_A_look_into_the_error-correction_capabilities_of_GNU_Radio_0_179.png Protect_your_bits__Introduction_to_gr-fec_A_look_into_the_error-correction_capabilities_of_GNU_Radio_180_2387.png Protect_your_bits__Introduction_to_gr-fec_A_look_into_the_error-correction_capabilities_of_GNU_Radio_2388_7223.png Protect_your_bits__Introduction_to_gr-fec_A_look_into_the_error-correction_capabilities_of_GNU_Radio_7224_9527.png Protect_your_bits__Introduction_to_gr-fec_A_look_into_the_error-correction_capabilities_of_GNU_Radio_9528_9611.png Protect_your_bits__Introduction_to_gr-fec_A_look_into_the_error-correction_capabilities_of_GNU_Radio_9612_9803.png Protect_your_bits__Introduction_to_gr-fec_A_look_into_the_error-correction_capabilities_of_GNU_Radio_9804_10295.png Protect_your_bits__Introduction_to_gr-fec_A_look_into_the_error-correction_capabilities_of_GNU_Radio_10296_10835.png Protect_your_bits__Introduction_to_gr-fec_A_look_into_the_error-correction_capabilities_of_GNU_Radio_10836_11135.png Protect_your_bits__Introduction_to_gr-fec_A_look_into_the_error-correction_capabilities_of_GNU_Radio_11136_12323.png Protect_your_bits__Introduction_to_gr-fec_A_look_into_the_error-correction_capabilities_of_GNU_Radio_12324_17447.png Protect_your_bits__Introduction_to_gr-fec_A_look_into_the_error-correction_capabilities_of_GNU_Radio_17448_19463.png Protect_your_bits__Introduction_to_gr-fec_A_look_into_the_error-correction_capabilities_of_GNU_Radio_19464_21623.png Protect_your_bits__Introduction_to_gr-fec_A_look_into_the_error-correction_capabilities_of_GNU_Radio_21624_23999.png Protect_your_bits__Introduction_to_gr-fec_A_look_into_the_error-correction_capabilities_of_GNU_Radio_24000_24143.png Protect_your_bits__Introduction_to_gr-fec_A_look_into_the_error-correction_capabilities_of_GNU_Radio_24144_25535.png Protect_your_bits__Introduction_to_gr-fec_A_look_into_the_error-correction_capabilities_of_GNU_Radio_25536_27203.png Protect_your_bits__Introduction_to_gr-fec_A_look_into_the_error-correction_capabilities_of_GNU_Radio_27204_28223.png Protect_your_bits__Introduction_to_gr-fec_A_look_into_the_error-correction_capabilities_of_GNU_Radio_28224_31499.png Protect_your_bits__Introduction_to_gr-fec_A_look_into_the_error-correction_capabilities_of_GNU_Radio_31500_32711.png Protect_your_bits__Introduction_to_gr-fec_A_look_into_the_error-correction_capabilities_of_GNU_Radio_32712_32867.png Protect_your_bits__Introduction_to_gr-fec_A_look_into_the_error-correction_capabilities_of_GNU_Radio_32868_34763.png Protect_your_bits__Introduction_to_gr-fec_A_look_into_the_error-correction_capabilities_of_GNU_Radio_34764_34919.png Protect_your_bits__Introduction_to_gr-fec_A_look_into_the_error-correction_capabilities_of_GNU_Radio_34920_39467.png Protect_your_bits__Introduction_to_gr-fec_A_look_into_the_error-correction_capabilities_of_GNU_Radio_39468_39591.png