About Reed-Solomon decoding of PEGASUS satellite

[OE3ALA]

Hi community!
Hi Daniel!

I have a question related to the "Satellite Reed-Solomon Decoder" block of gr-satellites (maint-3.8). As a small part of my Master thesis I am trying to briefly summarize how to decode the satellite. Here the FEC decoding plays a big roll. I am not very into FEC or RS decoding, but I want to give a short insight on how to get from the information provided in the "Ham Operator Manual" of PEGASUS to the actuall implementation into GNURadio for a users point of view. Moreover, with respect to our next satellite mission "CLIMB" I would like to improve the information provided for decoding of the satellite by ham operators (for PEGASUS especially information for CRC and FEC is missing :/ )

Following information is provided by the satellite team:

• n = 64 (total number of symbols)
• k = 48 (number of data symbols)
• code generator polynomial g(x) coefficients = 79,44,81,100,49,183,56,17,232,187,126,104,31,103,52,118 (16 in total)

RS Implementation of gr-satellites:

• Bits per symbol: 8
• Generator polynomial: 285 = 0x11d
• First consecutive root: 1
• Primitive element: 1
• Number of roots: 16
• Interleave depth: 1

What I have got so far (Am I true with my conclusions?):

• Within PEGASUS telemetry, 1 symbol is equal to 1 byte, therefore the number of bits per symbol m = 8
• Total number of parity symbols 2t = n-k = 16 --> RS is therefore capable of correcting t = 8 symbols
• The field generator polynomial p(x) is a primitive polynomial (irreducible polynomial) of degree m (p(x) = x^8 + x^4 + x^3 + x^2 + 1 = 285 (decimal notation))

Here I have some questions:

1. Is the "number of roots" directly related to the "number of code generator polynomial g(x) coefficients" and "total number of parity symbols (2t)", meaning "number of roots" = "number of code generator polynomial g(x) coefficients" = "total number of parity symbols (2t)" = 16?
2. How do I come to the values for "First Consecutive Root", "Primitive Element" and "Interleave Depth"? In the case of the TT-64 deframer the standard values are used.
3. Is the information provided by the satellite team sufficient for RS decoding? If not, what information is missing from your or the community's point of view?
4. Is it necessary to provide the code generator polynomial g(x) coefficients? Wouldn't it be better and sufficient to provide the field generator polynomial p(x) --> giving the information m = 8 bits/symbol if it is of degree m?

Many thanks in advance! :)

73 de
Alex, OE3ALA

[daniestevez]

Hi Alex,

Here are some answers:

1. The number of roots is equal to the degree of the code generator polynomial. These roots are the roots of the code generator polynomial, indeed. However, note that a polynomial of degree 16 has 17 coefficients. I think the leading coefficient is missing in your list, just because it should be 1 (the code generator polynomial is a monic polynomial).

2. The roots of a Reed-Solmon code must be of the form $\beta^j$, $\beta^{j+1}$, $\beta^{j+2}$, etc., where $\beta$ is a primitive element. This $j$ is what is called the "first consecutive root", and writing $\beta = \alpha^k$, where $\alpha$ is the root of the field generator polynomial (which must be primitive), the number $k$ is what is denoted as the "primitive element". So to find these two values from the code generator polynomial coefficients, factor this polynomial, look at the roots, and find an element $\beta$ such that the roots are consecutive powers of $\beta$. Then solve $\beta = \alpha^k$. This procedure is usually done the other way around (one starts with the roots and the computes the code generator polynomial coefficients). The interleave depth is 1 because there is no interleaving. A single 64-byte packet is an RS(64, 48) codeword.

3. No. You have already guessed some things that are missing from the specification. What is missing is the following:

• The fact that the Reed-Solmon code works over $GF(2^8)$ (i.e., with 8-bit symbols).

• How 8-bit elements are mapped to $GF(2^8)$ elements. Defining this mapping requires defining the field generator polynomial, since otherwise it is not possible to single out field elements and speak about them.

• An unambiguous description of the code generator polynomial (it is necessary to mention that when writing field elements as integers we use the aforementioned 8-bit representation for field elements, to mention that the leading term of the polynomial is omitted, and to mention the order in which the coefficients are listed, since the first element listed might well be the coefficient of $x^{15}$ or the coefficient of $x^0$. However, to avoid having people solve math calculations to actually use that code, instead (or in addition to) listing the code generator polynomial, it is better to define the primitive element $\beta$ (as a polynomial in $\alpha$ or preferably as a power of $\alpha$) and the first consecutive root (preferably as a power of $\beta$).

• It is also helpful to mention that the code doesn't use interleaving and that it uses the conventional rather than the dual basis. This is mainly because CCSDS supports interleaving and requires the use of the dual basis. To be fair, if interleaving or the dual basis are not mentioned, I assume that they are not used, and I typically guess right. So it's not strictly needed to mention these.

4. No. For a fixed field generator polynomial, there are many possible code generator polynomials, each of which gives a different Reed-Solomon code.

By the way, this particular Reed-Solomon code construction dates back to Voyager-1 (maybe it was the first place where it was used, I don't know). You can see how I define this code construction near the beginning of this post, though there I'm omitting some of the things that I said that should be specified (such as the mapping between 8-bit elements and field elements), because this is a post and not formal documentation.

Annex F in the Galileo SIS ICD 2.0 is an example of how one can specify a Reed-Solomon code in all glory of detail (Maybe too much detail! Although it never hurts to have some redundancy in ICDs). It's again the same code construction, though they order the message bytes in the opposite order compared to what most of the world does (but this is completely clear if you read their documentation carefully).

[OE3ALA]

Many thanks for your fast and detailed answer including the references! This helped a lot. :) To clarifiy some things and to avoid some wrong assumptions due to my half-knowledge I have some short questions:

1. If I understood correct, $\beta^j$, $\beta^{j+1}$, ... are the roots of the code generator polynomial g(x) (You denoted them as the roots of the RS code). $\beta$ can be written as $\alpha^k$, where k is the primitive element requested by the RS Decoder. Since k = 1 for PEGASUS and $\beta = \alpha^k$ this also means that $\alpha = \beta$ in that special case. Is that true?
2. RS(64,48) has 16 parity check symbols. Is the degree of the code generator polynomial g(x) always equal to the number of parity check symbols?
3. PEGASUS uses 8-bit symbols. Is the degree of the field generator polynomial p(x) always equal to the bits per symbol?

As a short summary of the most important parameters for the RS code, I have came up with following table which should have all the information needed for using the RS Decoder and Encoder blocks:

[daniestevez]

The answer to each of your three questions is 'yes'.

[OE3ALA]

Many thanks for your help! :) I have some other questions related to the FSK demodulator, but that I will discuss in a seperat discussion.