Open Research Institute 2021 Space and Satellite Symposium, 26 Oct 2021

Previous Meeting Next Meeting

⏯

youtube image

►

From YouTube: Space and Satellite Symposium 2021 Anshul Makkar

Description

Space and Satellite Symposium 2021 Anshul Makkar, covering LDPC on FPGA for amateur space applications.

A

Hi, uh I am angel merker uh working as a software engineer at ori, uh I'm open source collaborator at open source institute and my collaboration areas result relate to implementation of ldpc on hardware. uh It's not the complete implementation of all the modules of ltpc I have. I have contributed to gsc encoder, bb frame formation and few more modules of ldpc implementation.

A

Apart from that, I have also been contributing to debris research uh again as part of ori. We just a couple of days back. We presented our paper to fcc and my another collaboration relates to a dynamic scheduler for again for a spacecraft which allows a spacecraft to to switch the task dynamically at runtime.

A

um So if it's performing task x and effect ground station, it's realized that uh it needs to do why suppose it's taking uh it's doing altitude, control and um and it's neat it needs to immediately switch some to some other task. Then that's possible with my dynamic scheduler. So that's my another contribution uh today um I'll be uh today. My the topic of my presentation is uh coding theory uh why we need it and or basically what it's application in space, um what at ori how we have implemented?

A

uh Ldpc, which is a form of uh forward error correction code, uh how we have implemented uh this at ori uh in fpga, so uh it's uh coding, theory star. uh I will start with, as I mentioned, uh why we need codes, then simple codes, then uh going further deep. What are ldpc that's a particular particular class of codes that we have implemented and approach that we have used for its implementation, uh the coding theory or encoding.

A

A message using ldpc in codes involves huge calculations, so we have to efficiently implement it, and so here I'll be focusing on uh how we have implemented how it or we have implemented this.

A

uh You would appreciate that uh this in itself. Each of this is in itself a big topic. uh There are various research papers uh uh put forward for each of these topics, uh so in 30 minutes it won't be impo. It won't be possible for me to go into depth of each of the topic.

A

So my aim here is to get uh to uh get you interested or to give you some pointers or to give you some basic understanding of how we can use these codes or why this codes are needed for long distance communication, how they will? How they are beneficial and how they can be efficiently implemented in fpga, so starting with uh first of all, why we need it uh with the communication link between uh satellite or long distance communication link, you talk of leo to earth or geo to earth.

A

Any communication link it's expensive, limited in bandwidth and also error prone. So we have three criterias error, expense, expensive and error, expensive and limited bandwidth.

A

So all these factors asks for efficient utilization.

A

And that's where the answer comes from codes.

A

So, in a normal scenario, we send a message through a noisy channel: it gets scripted and the receiver.

A

We expect that it to detect the error and then convey the message back to the transmitter and transmitter resets the message and that's how it happens in tcp communication, but here things are different due to these three factors.

A

So here we expect that a receiver should be able to detect error and also it should be able to connect us first, focusing on detection part.

A

We have initially we had some class. uh We have this error detection mechanism via crc, so we have code bits, c1, c2, cn. uh We do some calculation here and based on the result. We insert that calculation result here and let's and we we have this crc bits here so this is transmitted receiver receives the bits again calculates the crc and finds out.

A

If there is corrupted bits or not easy, but there is again it will convey the message, but there is no way that, but the only solution now is the transmitter has to send a message again, which is again a wastage of.

A

A

So what we want is that receiver is able to detect and correct error, and that's where the forward direct forward error correction codes come into picture, so they control the message before it has been transmitted by means of introducing some redundancy.

A

So putting forward in another way with.

A

Fec or forward error correcting codes. They allow us to introduce some redundant bits that allows receiver not only to detect but also correct errors. Now, starting with the simplest form.

A

And simplest form simple error: correction. We say if we are transmitting and sky text, which is of 7 bits: c1 c2, c3, c4, c5, c6 c7. We add an extra bit here so that the sum of all the bits is zero sum here means xor, so c1, c2, c3, c4, refine.

A

Simple error, error, detection.

A

You send the bit 7 bits, add an extra bit and the result should be zero. Receiver receives the message checks if there is if the result is not zero. There is an error again, it detects an error, but the correction part is still missing.

A

A

To introduce the correction part.

A

With with this simplistic equation, it's clear that receiver will only be able to detect there, but not correct, so we have to make the equations a bit more complex so that we can also build in the capability of connection now.

A

Here comes the concept of parity check. Equations now see and.

A

Even uh before moving to parity check equations, I want to give you another example just to make you understand the scale of the problem. So suppose we have 1 0 1 and we introduced like in previous case. We introduced one bit extra now here. Let's repeat the complete message in itself, so one zero one, one zero one. Instead of one zero one or let's say uh to make things clear: 1, 1, 0, 1, 1, 0, 1, 1, 0, we transmit 1, 1, 0 or another form of redundancy can be 1.

A

1 1 1, 0 0 each bit is replicated.

A

So this is a simplistic form of error, correction and error, detection and correction that can be done at the receiver and receiver's end. So receiver receives this message.

A

A

If this bits get flipped, then it has this, which is the correct one. Similarly, if this bits get flipped to zero or this bits get flipped to zero, then it has this redundant bit to fall back upon.

A

I don't think so. You are able to see this one. So what I'm saying is that other form of redundancy can be like this, so we have one one. Each bit is replicated.

A

So if this bits get corrupted, then heat has this bit. If this bits get corrected, it has this bit and yeah. Similarly, it can find out here. If none is corrected, then it can take one another again, a simplistic form where you are duplicating the message or duplicating the bits so that if one gets corrupted then at least receiver has another bit. That is correct, but again what happens if both get both the bits get corrupted.

A

That's that's, furthermore, harder. A receiver will think that if this boat gets flipped to one one, the receiver will think that the one was transferred again it's next process of evaluation. uh So now we have um for more complex equations or parity check equations.

A

So if the message bits are 1 1 0, then let's say c: we have c1 c2 c3, so we say that we introduce redundant bits in such a way that they satisfy this equation. C4 is equal to c1 xor c2 c5 is equal to c2, plus c3 and c6.

A

It's not visible. C6 is equal to.

A

C1 plus c2 plus c3.

A

Or we can say, c1 plus c2 plus c4 is equal to zero c2 plus c3 plus c5 equal to 0 and c1, plus c2 plus c3 plus c6 is equal to 0.. So with this code word so with this message, bits 1, 1, 0, 1, 1 0. What we have the encoded message will be in the form of c4 is c1 plus c2, which is 0. C5 is c2, plus c3, which is 1 and c6, is equal to c1, plus c2 plus c3, which is again 0.

A

So now for information, uh one one: zero: we have the codified message or the encoded messages one one: zero: zero one: zero with these equations with these two uh or check equations.

A

Now, if some, if suppose, this bits, if this bit gets corrupted or flipped to zero, then we have, then it will violate these equations. We have c1 plus c2 plus c4. This is c1 c2, c3 c4, c5 c6. So so we have this c1, plus c2, c1, plus c2, plus c4. This will be now one which will indicate to the receiver that there is an error. Similarly c2 plus c3, plus c5 c2, plus c3 plus c1 c2, plus c3 plus c5.

A

It will be again 1, which again will help the receiver to detect an error, and now it has two equations.

A

To detect error and correct it, but correction again require more equations. More parity check equations to correct errors.

A

A

As you would appreciate, uh as you can see as we are, equations are becoming bit complex, but the probability of error, detection and correction is better as compared to when we were doing simple redundancy and gallagher and mckay and other researchers have shown that, with a limited amount of redundancy introduced along with message bits, it's still possible to achieve the shannon limits for a channel.

A

And this is this is the basic fundamental principle that's utilized for ltpc.

A

Before moving to ldpc, uh I want to show that these equations can also be represented in a matrix form, and it's in this form that we basically uh do. We basically represent it in the hardware and do all the calculations. So given this, so I will rub these equations.

A

And we have this code word, and this is the message. This is the original message, and this is the code word, so this can also be represented as matrix multiplication of message, vector message, vector.

A

Of k, bits along with identity matrix, which we call as h and the identity matrix will be in the form of 1 0 0 1 0 1 0, 1, 0, 1, 1 1 and 0 0 1 zero one one. This is h and length n so for message bits, uh let's call it k bit. So we have two. There are total possible of two raised to power k, message, combinations which will result in 2 raised to power n codewords, and this 2 raised to power n code.

A

Words will be a subset of the combinations of uh it will result in two raised to power k code words, uh which will be a subset of two raised to power n, and we can say that each code word not visible. So each code word.

A

Can be represented as u dot h, with a multiplication of message, bits or message vector along with h, matrix now. The next question is how to find that so we'll come to that, because that plays a very important role and this matrix will, with this matrix multiplication, this vector matrix multiplication will give us the same parity check equations that we studied in the previous.

A

Few minutes back yeah.

A

A

This will also form the basis for ldpc.

A

Ldpc encoding because ldpc encoding is also a type of it's it's a type of encoding by doing matrix. Multiplication of this factor message, vector and h matrix, but the only condition on edge is that h should be sparse and what a sparse means is that a number of ones uh should be less, and this is to make this is to ensure that computational capacity uh computational complexity, while uh calcul while encoding the message is less.

A

But there are few more constraints which I will go through when I am at ldpc.

A

And another thing that I want to mention here is that uh the codes that are given by this product are symmetric code uh and what a symmetric means is that the initial initial three bits or initial k bits of the code words are same as the message bits.

A

So that's why this is a symmetric code and to get a symmetric code.

A

We need to have this identity matrix. Then only the product will give us a code in this form so now coming to uh ldpc. So, as I mentioned, ldpc is again uh it's it's. A symmetric code again represented in form of uh codeword, is equal to, uh but there are some special constraints placed on the h or the identity matrix. And what are these constraints?

A

It says that each row contains a fixed number of k, number of ones which is called.

A

Row constraint or row weight. Similarly, each column contains j, number of or again a fixed number of ones, which is called uh column, constraint or column weight, and the number of ones common to any two rows is 0 and 1.. Now why these factors are important?

A

um First of all, fixed number of rows, row weight, fixed number of row, weight and column weight ensures that the complexity is less and the constraint that says that the number of ones common to any rose is zero and one it prevents cycles.

A

Now, um if you go, uh if you dig uh deep into this topic, uh you will you will see how cycles are harmful for this encoding and how we can avoid that, and you will study into 10 other graph that will that can clearly shows cycles but yeah, I'm not touching the topic here again, so how to form this parity-check matrix again.

A

Various researchers have shown their different approaches, like mckay has shown that you start with all zero metrics and then introduce once at random places, but introduce ones once one in once in in such a way that uh all these constraints are satisfied. Similarly, gallagher showed another way of parity check uh how you can form your parity check, matrix.

A

Now, coming to how at ori we have implemented ldpc.

A

Ldpc implementation was part of our uh dvbs2 protocol. Implementation. Dvbs2 protocol specifies that ldpc specifies ldpc as one of the encoding mechanism, which you can use to codify your message bits once they are transmitted for transmitter and we are working on transmitters, so ldp's we've implemented ldbc, so uh the implementation of ldpc uh it has to be. uh It has to be efficient because uh continuously messages are coming from the source and how it's forming. We have this source, uh it does some encryption, then we it goes to encoding.

A

uh Here we have ldpc, then we have then it goes here. Then it follows the reverse form of.

A

A

Decryption and again, the message bits.

A

So there is continuous stream of this message coming to our box, which is doing which is encoder.

A

So the wave and.

A

In this case, we don't have to form parity check metrics, because parity checks matrix or its positioning, where the number of where the ones should be there in that matrix, is provided by dvbs to protocol and extra, b and c. So we store that table that parity check, stable or parity checks matrix in b ram. So we have this b ram where we have parity check.

A

Where we have parity check matrix, so this is the beta, so we have continuous stream of axis stream.

A

Of message bits, so we get that message bits we divide this table or ram into frames, so we don't fetch the complete ram at one time we get only a frame of uh a ram frame, let's call it a ram frame which is a part of the complete matrix. uh We get only a ram frame, whatever is needed at that moment to do the equation or to to do the calculation to the computation.

A

So we have message bits we get frame ram from here. We do calculation here and then it's outputted to the next step or next unit. So here we we follow a parallel pipelining architecture where this is coming parallely. This is coming parallely, then do the calculation forward? It again next step here here and forward it. So that's how we implement uh our.

A

We do the implementation fpga and I have the numbers for uh be a b ram utilization, lut utilization, uh which I can share. So that's all for my presentation uh feel free to ask any questions. uh Thanks for listening. Thank you. Bye.