CCSDS Encoding & Decoding

Question

I'm working on a project where I need to encode and decode data frames with Reed Solomon and constitutional encoding as given by the CCSDS standard. I've tried to find some appropriate libraries, but struggling to find one that is complete in C.

I’ve found a Reed Solomon library that works (very similar to the one given in https://scholarworks.calstate.edu/downloads/8336h559x?locale=en), however, I struggle when trying to generate the elements of the code generator polynomial as given by the CCSDS standard. In CCSDS 131.0-B-4, the field generator polynomial F(X)= x^8 + x^7 + x^2 + x + 1, a^11 is a primitive element in GF(256), and 112 is the first consecutive root, and the code generator polynomial is:

In the code, heavily based on the code in the link above, I don't see how I can introduce the primitive element or the first consecutive root:

void encode_rs(int NN, int KK, int* gg, int* alpha_to, int* index_of, int* Data, int* BB)
/* take the string of symbols in Data[i], i=0..(k-1) and encode systematically
   to produce 2*tt parity symbols in BB[0]..BB[2*tt-1]
   Data[] is input and BB[] is output in polynomial form.
   Encoding is done by using a feedback shift register with appropriate
   coNNections specified by the elements of gg[], which was generated above.
   Codeword is   c(X) = Data(X)*X**(NN-KK)+ b(X)          */
{
    register int i, j;
    int feedback;

    for (i = 0; i < NN - KK; i++)   BB[i] = 0;


    for (i = KK - 1; i >= 0; i--)
    {
        feedback = index_of[Data[i] ^ BB[NN - KK - 1]];
        if (feedback != -1)
        {
            for (j = NN - KK - 1; j > 0; j--)
            {
                if (gg[j] != -1)
                    BB[j] = BB[j - 1] ^ alpha_to[(gg[j] + feedback) % NN];
                else
                    BB[j] = BB[j - 1];
            }
            BB[0] = alpha_to[(gg[0] + feedback) % NN];
        }
        else
        {
            for (j = NN - KK - 1; j > 0; j--)
                BB[j] = BB[j - 1];
            BB[0] = 0;
        };
    };
};

I therefore end up having different coefficient of g(x) than as given in Annex G of CCSDS 131.0-B-4. If I copy these coefficient directly the code I get the correct parity bits, but then the decode function is not able to decode. The decode function is the decode_rs function as given in the link above. I have tried to change encode_rs and decode_rs but without luck.

Could anyone please help me to change the functions to work with primitive element and first consecutive root?

Answer 1

Primitive element = alpha^11 = 0x02^0x0b = 0xE8 = 232. E = 16, 128-E = 112, so first consecutive root of g(x) is (primitive element)^112 = 0xE8^0x70 = 0x79 = 121.

For CCSDS, encoding uses a self-reciprocal polynomial (reverse the coefficients and they are the same). This saves on the number of constants needed to encode in hardware. CCSDS uses 32 parity bytes to correct up to 16 errors.

generator roots in hex
79 09 fb e9 02 cd c9 4e c1 5d c2 78 e1 11 ce ec
6d a8 72 3f db a5 0e 59 45 f7 7d 8e 74 75 9d 77

self-reciprocal generator polynomial coefficients in hex
01 d5 b8 6a 84 24 90 c2 09 3b 43 51 38 9e cc 4a
87
4a cc 9e 38 51 43 3b 09 c2 90 24 84 6a b8 d5 01

For the example code you linked to, you would need to change the primitive element to 0xE8 (alpha ^ 11), and change the first consecutive root to 0x79 (0xE8^0x70). Some components of the code are "hard coded" and need to be generalized to handle the changes.

As an alternative, I modified an old ecc demo program of mine to do CCSDS encode and decode, which you can download from the link below. Since it is a demo program, it includes three types of decoders: PGZ matrix, Berlekamp-Massey, and Sugiyama extended Euclid, you only need to use one of them. Defining p as the number of parity bytes, PGZ is the slowest with time complexity O(p^3) due to matrix inversion. The other two have time complexity O(p^2). There is code to handle erasures (known error locations) by modifying the syndromes, but for this case with no erasures, it just does a one time copy of the syndromes, and if wanted you could remove it. This demo program stores polynomial coefficients most significant first (other implementations store least significant first).

The PGZ and Berlekamp-Massey decoders are standard implementations. The Euclid decoder emulates a hardware like pair of large shift registers, where each register holds two polynomials, one most significant first, one least significant first, with an index to the boundary between polynomials. The actual Euclid algorithm is the standard algorithm. A slight advantage of the Euclid decoder it that it's remainder is the Omega polynomial used by the Forney algorithm to generate error values.

https://rcgldr.net/ecc/eccdemoc.c

Unlike the comments in the C code you linked to, if there are more than 16 errors, there is a chance of a bad correction. Say there are 17 errors, then the code could think it's correcting 16 errors but the wrong 16 errors, resulting in a total of 33 errors, more than a RS(255,223) code is guaranteed to detect.