Lecture 09

[Music] welcome to the class and we are going to continue learning about transport block segmentation and then in context of the segmentation we'll very very briefly discuss ltpc encoding also okay and I'm not an expert on ldpc encoding but we will cover whatever is required for us to understand this okay now this is where we are okay Mac gives us transport block to the physical layer which needs to do all these tasks okay and so our focus is only on the physical layer now as soon as the transport block comes the physical layer append this transport block CRC and based on certain condition this transfer block is segmented okay and once this is segmented this code block CRC is appended each of this segmented transer block is called a code block okay and then the code block CRC is appended okay now there is this filler bit also which are appended to this code block we are going to see why these bits are appended we understood why this CRC is appended okay along with transer block CRC okay this is called code block CRC and C is the total number of segmented code blocks okay if C is one only only transport block CRC is used if C is greater than one then additional L is equal to 24bit CRC is attached to each of this code block okay so this is what we understood yesterday and we discussed this also that before we actually understand how to correctly segment a transform block how not to segment a transform block okay right so this is also a recap so this is the example which we have been using so user is allocated 70 resource blocks over slot of 14 symbols okay example from yesterday's class and it is given MC 16 which is a Cod rate of this okay based on this the transport block is calculated we will see how to calculate it but later and the transport block size is 28168 bits okay as soon as it comes to the physical layer the transport Lo CRC is appended okay right and now we saw that could be segmented into three code blocks of size 8448 because that's what ldpc encoder can handle but the size of the residual code block will be 2848 okay and the BL performance is limited by the smallest code block size and we don't want that to happen Okay so we have to this segmentation block has to ensure that this transort block is segmented into equal size code blocks okay and there is a reason because because you don't want to get limited by the smallest size code block right so we will see that how standard enables that and we actually go through the standard also in today's class and the class after this okay so this actually the total number of code block is how is it determined in the standard and that's what we are going to see and this is like from the standard standard details okay so what is this b b is transport block size plus CRC if this is KC B this is kcb is the maximum encoder size okay L is 24 we know that L is a CRC size then the number of code blocks will be how much let's read that carefully okay what is this B total length of Transport Block Plus CRC right divided by kcb kcb is that 81 8448 number okay and why are we subtracting minus L from from here because we want to make space for the CRC also right okay if we simply divide it by kcb then you are not left for the CRC which needs to be appended okay to each code block right so you need to create space for that so this is this okay divided by the seal okay so you want more number of code block so once you have this C we calculate B Dash what is B Dash look at this okay B is the transport Block Plus CRC then what what is this you are appending C extra crc's of length 24 right okay so your actual payload which needs to be transmitted now becomes this B Dash okay and this is what needs to be like actually segmented correct so we know how many code blocks are there now again four code blocks and this will be the total through length Okay total payload which needs to be transmitted so if B is less than kcb 8448 then what happens what is this L isal to Z this is that code block CRC which will not be appended right simple to understand okay then what happens in this case C is one Cod log is one right and B Das become equals to 1 because what happens here C is L is zero okay because extra CRC is zero so all these formulas are coming from the standard okay I'm not developing them myself I'm just like encoding or decoding it for you okay how to read that okay so this is understandable right okay so what is this B- called it is called the effective payload length we understand why it is called effective so this is our example right okay so C is basically B by kcb minus l so what is this B is 2819 2 right we are actually inserting the numbers here now minus L is 24 what is the value of C 4 correct okay now what will B Das be b + C into L right and what is this 281 92 this is B plus 4 extra CRC you need to Happ 28 288 this is the effective payload length right okay now I should basically segment it each code block K Dash right this is the payload I need to transmit and it contains all the crcs which we need to append right plus this transport block CRC also so what should my code block size should be K Das should be this divided by 4 7072 okay is less than kcb 8448 so I satisfy that condition okay there's a Twist they not done like this there's a slight change okay and they are practical constraints okay and that's where the notion of this filler bits come into picture okay so why these filler bits are appended that's what we are going to discuss okay this is I'll jump the gun I'll discuss that also but this is to make sure that ldpc encoder gets implemented ldpc encoder is designed in the standard in such a way that like it can only number of given input length Okay for example it'll turn out then it cannot encode this particular length input sequence okay right it is it it is not designed for that okay and there is a reason and that's what I'm going to tell you in the next slide okay so it cannot decode it cannot encode this so certain number of filler bits or certain extra bits need to be appended to this so that it can actually the ldpc encoder can encode this input sequence okay so that's what we'll see and that's what we are going to understand about ldpc encoding only that bit like why uh ldpc encoder is designed in a certain way okay which and it cannot encode this right if ldpc you're all set to encode this okay but ldpc like then because of the implementation constraints okay let's see that now why do these implementation constraints come into picture that's what is this like ldpc code okay how does it work okay right so ldpc encoder should it takes in some input bits and it gives you a what is it called it's called a code word okay right where in like output is basically the encoded code word okay so it has to it has to basically generate that encoded output correct okay that's the job of ldpc encoder now that output is generated using something called parity check Matrix we denote it by H okay the Matrix and we denote it by H okay and the code word v which is the output of this ldpc encoder is chosen such that this H into V is zero okay so V is a vector H is a matrix okay you do their product and that should give you an all zero Vector okay which essentially says that V Should lie in the null space of this Matrix H this comes from linear jebra but what are we saying here H into V should be equal to Zer okay right now if you have to basically what is happening in the encoding that you need to generate this encoded output you need this parity check Matrix okay right so encoder should be able to generate this parity check Matrix first and then only it can encode this input sequence okay so how does this 5G NR designs this parity check Matrix okay so what does it use it use a something called base graph Matrix get used to these terms okay very simple terms immediately become clear what is happening okay so it uses a base graph Matrix U to Define this parity check Matrix H H is a so what is happening here H is a bigger size Matrix okay and because the input code block length can run into 8448 right okay so you should be able to generate that big size Matrix from a smaller size Matrix to store these matrices is a huge requires a lot of memory okay so the way typically it is done is you store a smaller size Matrix and generate this bigger size Matrix using a formula right it's a trade off between computation complexity and the memory okay you'll see this so what is happening here I'll take you through all these arrows okay so what's happening you look at this I'm taking an example to to tell you how this parity check Matrix is generated from this base graph Matrix okay that's once I know this once I'm able to generate this parity check Matrix it is assumed that I'll be able to generate the encoder output okay so what we will learn in these slides is how this parity check Matrix is generated from this base graph Matrix and that will essentially tell us why do you need these filler bits okay right because our what are we trying to understand we are trying to understand how segmentation is done and why do you need these additional filler bits okay because the output of segmentation block needs to be encoded okay so I take this example U okay this is some a two cross to base graph Matrix is a base okay from there you are going to generate this Matrix H parity check Matrix okay so I have to generate this like what is this 6 CR 6 parity check Matrix okay right so what am I going to do this is a 2 cross2 Matrix I'm going to take a 3 cross 3 identity Matrix suppose I've been given this objective of generating the 6 cross 6 parity check Matrix okay take this base graph which is given to you what the step two is take an identity Matrix what is identity Matrix right all its diagonal elements are zero okay now how are you going to generate this H from here okay look at this carefully what is happening okay you take this identity Matrix fine okay you cyclically permute The Columns of it by two okay so what is basically so what is happening here I I'll go through these terms also okay so you look at this what is happening so take this identity Matrix okay I have cyclically permuted The Columns of this by two okay let's uh one second it comes here circularly shifted according to the base graft entry yeah okay let's so what is this we are you take take this column okay so you are cyclically shifting it by factor of two what will happen this column when you once you shift it it one shift it'll come here second shift will come here right so what is you'll replace this two okay with this identity Matrix which is cyclically shifted by a by two okay right see this so This column has come here this column where will this column go first you'll shift here it'll come here you shift it by two you're getting it okay and then you shift so what happens to this column if you shift it by one it comes here and then you again shift it by one it comes here so this column you see this is sitting here this column is sitting here and this column is sitting in the middle right so what am I doing I'm just shift I'm looking at this number I have to replace this number by this identity Matrix okay right and cyclically shifted identity Matrix so here it shifted by two here you see this if you shift this Matrix so I have to replace this three by again by cyclically shifted identity Matrix shifted by three if you shift it by three what will happen you'll get back the same Matrix you shift it by zero you get back the same matter right okay then you shift it by one what will happen this column will go here this column will come here and this column will go here right so this is cyclically shifted version of identity Matrix how much cyclic shift is there one how much is the cyclic shift here look at cyclic shift is zero how much is the cyclic shift here cyclic shift is three right this how it is generated okay you can generate as big a matrix as you want okay by looking at this that's all correct this is Three cross I can if you want to generate a bigger size Matrix okay depending on what your requirement is I can take a 25 Cross 25 identity Matrix I'll be able to generate a like 100 cross 100 parity check Matrix correct so what do I need I need to Only store this not a 100 cross 100 Matrix I need to Only Store 2 cross two Matrix but I need to be told right what is the size of this I need to generate that's all correct I'm done and these are the technical terms which are used in the standard and that's I'm going to show to you okay the recipe which follows after this is basically whatever we have just discussed so what is objective U needs to be transformed into a parity check Matrix H okay using a lifting Factor z c what is a lifting Factor you have to lift this Matrix to a bigger size Matrix that's why it is called the term is called lifting okay so what is you are basically blowing up this Matrix okay into a bigger size matrix by this lifting Factor zc what do you think that c should be in this case okay that c should be three right so lifting okay what is this lifting each integer entry of the base graph is replaced by a permuted zc cross z c identity Matrix okay so how are we lifting this base graph Matrix okay we are replacing each of its entry by a corresponding permuted zc cross z c identity Matrix that's an example we just took do we understand this so what how do you obtain H start with an identity Matrix H and circularly shifts his entries according to the base graph entry UI J right okay what is this is u11 take an identity Matrix shift it by two so take this shift it by three okay right so we consider an examp example 2 cross2 base graph Matrix and the lifting size was z c is equal to 3 okay so is this clear what we are saying here okay so I don't I don't have to store H I have to store only U look at the tremendous reduction in the memory yes I'm Computing it look at this computation as like very simple and it can be easily implemented in a fpga okay right so that's the reason okay now what is happening here okay that uh 5G pdsh what is pdsh the shared Channel which transmits the data okay right so it supports two base graphs to ensure good performance okay and that will tell us what like we introduced two different sizes yesterday of this ldpc encoder okay so there are these two different base graphs okay which are given in the standard now base graph one is optimized for large information block sizes and high Cod rates okay right so this is basically the base graph which we are going to use mostly in our studies okay what is the maximum qu rate which this base graph can allow is 8x 9 okay and the minimum Cod rate is 1x3 okay this this is first base graph base graph two is optimized for smaller information block sizes and lower Cod rate okay and this lowest Cod rate for this base graph 2 is 1x 5 here it is 1x 3 here it is 1x 5 okay and base graph 2 has a much lower decoding complexity than base graph 1 okay now what is we have to understand this why this is done the way I'm telling you why two different base graphs okay right so look at this what is happening here this base graph we are saying that it is optimized for large information block sizes okay and high code rates okay so where will this happen where will a user observe this kind of scenario is basically High SNR scenario right okay correct where where and like when will you transmit a higher code rate to a user when the user is observing good SNR okay and and then when will you transmit large information block when that user has basically High data rate requirement okay so typically what happens if you are in a good like SNR area you are able to observe good signal from the base station okay you can actually watch high quality videos okay that's natural if you are in a basement you of a building you will not be you're not in a situation where you can like watch high quality videoos okay right so what is happening here is that typically this such a user will have high volume of data which needs to be transmitted okay and it's observing a high SNR okay this encoder which is designed okay can give you better performance okay for these scenarios right because there are two different regimes one is height like you'll consistently the ldpc encoder will consistently observe highest block sizes and it'll have to encode at the highest rate correct so Design One encoder for that okay other is basically The Other Extreme where in like a user is observing low SNR and because the SNR is low you cannot give like it cannot ask for like high data rate Traffic okay even if it ask it will not be able to base station will not be able to provide it because the SNR is not that high okay so the ldpc encoder is basically going to observe lower size encoding block and lower data rate okay and then lower code rate also okay because SNR is poor okay so designing a common ldpc encoder for these two extremes what people felt was not a like practical move okay right so you'll have to make too many compromises on the performance of these ldpc encoders okay if you design a single one for these extreme scenarios okay right that's why the standardization body said okay we will Design two different encoders and what is different here only these two base graphs right and so there are these two base graphs and so if you remember right we introduced two numbers one was 8448 other one was a smaller number right I gave you these numbers and that's primarily for this okay right so ldpc encoder is designed to cater widely different demands and one of them like designing a single one for them was not practically desirable okay right now this is some bit about ldpc encoder okay now what why are we studying this why did we actually come to this ldpc encoding we wanted to understand this our segmentation part don't forget about that right okay correct and we said that cannot simply take this like transport block plus the extra CRC which you need to append and divide it by C okay because ldpc encoder cannot encode that okay right need to append those filler bits so we have understood only part of that what I have told you is how ldpc encoder works right okay how is it coupled to this segmentation that's what I'm going to teach you in the next class okay but what are the key information what you need to remember from this class is that the notion of base graph okay and the lifting side zc correct okay that is one key thing we one key aspect which we'll take over to the next class okay then this is a number which I'm introducing okay this is called KB this number what is this this number of systematic columns which ldpc encoder forms okay right so this number is fixed okay what this ldpc encoder does is let's say you feed 8448 size uh input data to it okay it will form 22 Columns of data okay right and each column will be of length how much 844 let's say the input size is 8448 okay right how much will be the size of each column 8448 by 32 right okay so that's how this ldpc encoder Works takes in this data okay then it arranges these data into these many columns right and the the number of column remain fixed and what is this this is KB is equal to 22 okay it's just that the length of each of this column will change depending on how much input bits you are feeding correct okay so that is we will have to recall remember this number this is number is going to come back okay and that's what is going to decide actually the number of filler bits okay because this number is fixed that and there is an implementation constraint okay right so what have we learned in this class is just to summarize we are segmenting a code block okay now this segmented code block need to be fed to the ldpc encoder okay and the ldpc encoder cannot encode any arbitrary size in input and that it can only encode certain fixed size input okay and those input length are basically constrained by what is coming here is the lifting size okay because you need to why this zc will impose a constraint because you need you need to generate the parity check Matrix a suitable parity check Matrix to generate the encoded output okay and you can generate these parity check Matrix for not any arbitrary zc you can only generate these parity check Matrix for certain zc right and that's why you cannot feed in any arbitrary input to the input length to the ldpc encoder okay so these are the two key messages from this class which you have to take back home and then we will use this message to basically understand how many filler bits need to be appended okay why part we have understood okay that it cannot ldpc and cannot encode any arbitrary length input because it has to generate a fixed parity check Matrix and that parity check Matrix is encoded is generated by lifting the base graph Matrix okay right so remember this and we'll continue discussing this in the next class and we'll start exactly here by giving you some brief introduction about how this will happen okay so we'll stop here and then we'll continue [Music] [Music] [Music]