shortened Reed-Solomon (10,6) code

[vinnitu]

I need subj for CCSDS AOS Space Data Link Protocol for generating the Frame Header Error Control

I am trying

const static uint16_t correct_rs_primitive_polynomial_shortened = 0x13;

size_t min_distance = 4;
correct_reed_solomon *rs = correct_reed_solomon_create(correct_rs_primitive_polynomial_shortened, 1, 1, min_distance);

uint8_t msg[6];
uint8_t msg_out[10];

correct_reed_solomon_encode(rs, msg, sizeof(msg), msg_out);

and seems I am wrong )

Tell me please is it possible usage your library out of box for this task or we need make some patch?

Thx.

[brian-armstrong]

Hi @vinnitu,

Libcorrect only supports RS with 8 bits per symbol.

[vinnitu]

Thx! can you help me add support of this feature?

[brian-armstrong]

I think this might be doable, but you'll have to do some careful testing to be sure.

Basically, any place where 255 and 256 (and 510 too!) show up in the codebase need to be replaced with instance variables. Probably something like width which defaults to 8. Then you do # elements = (1 << width). Just try to make sure the math works once you've replaced everything and that the tests still pass.

You can probably deduce the intended width in the existing constructor by inspecting the polynomial, which means the API itself doesn't need to change, most likely. The number of bits is just the highest bit set in the polynomial. You can see this in https://github.com/quiet/libcorrect/blob/master/include/correct.h#L133 -- all of the 8 bit polys have x^8 set, so we can infer that these are for RS(2^8). In your case x^4 is the highest set, so we know it's RS(2^4). So when correct_reed_solomon_create() is called, the width can just be inferred from the poly.

Finally, the way the bytes themselves are packed will be kind of problematic. Internally RS walks along the message one byte at a time. You can fix this either as the caller or in RS itself. Basically you'll want to unpack each byte of 2 nibbles into 2 bytes with the lower 4 bits set. If you do this in RS, you'll probably want to do it as soon as you are called with the message so that the rest of the internals don't need to know about it.

Good luck, and let me know if you have questions.

Edit: I think these are all the files with constants that need changed https://github.com/quiet/libcorrect/blob/master/include/correct/reed-solomon/field.h#L32 many lines here https://github.com/quiet/libcorrect/blob/master/src/reed-solomon/decode.c#L215 handful of lines in this one https://github.com/quiet/libcorrect/blob/master/src/reed-solomon/reed-solomon.c#L9 some here And I think that may be it

[brian-armstrong]

Hi @vinnitu

I went ahead and made some of the changes suggested above. I put the changes into a new branch. https://github.com/quiet/libcorrect/pull/18

Could you try the changes out and see if they work for you? I decided that libcorrect should not unpack the bytes since it's ambiguous how it should unpack them (some users might want low nibble first, others high nibble first). So when you use it, make sure that you unpack the bytes. Libcorrect will check the decoded message and immediately quit out if any of the bytes has a value greater than 15.

The API itself hasn't changed. As I mentioned, the polynomial can be inspected to deduce the width, so that's what I've done. Using the polynomial you've provided tells libcorrect to go to GF(2^4) mode, and there's a new test for this.

If everything works for you, I'll go back and clean up the branch and merge it into master.

[vinnitu]

Hello!

What is wrong?

#include <correct.h>
#include <stdint.h>
#include <stdio.h>

#include "print_mc.h"

int main(int argc, char* argv[]) {

    size_t min_distance = 2;
    correct_reed_solomon *rs = correct_reed_solomon_create(0x13, 1, 1, min_distance);

    uint8_t msg[6];
    uint8_t msg_out[10];
    uint8_t msg_in[6];

    for (int i = 0; i < sizeof(msg); i++) msg[i] = i;
    correct_reed_solomon_encode(rs, msg, sizeof(msg), msg_out);

    print_mc(msg_out, 10);

    msg_out[3] = 0xff;
    print_mc(msg_out, 10);

    int code = correct_reed_solomon_decode(rs, msg_out, sizeof(msg_out), msg_in);
    printf("code: %d\n", code);
    print_mc(msg_in, 6);

    return 0;
}

00 01 02 03 | 04 05 00 04 | A0 07 

00 01 02 FF | 04 05 00 04 | A0 07 

code: -1
00 00 00 00 | 00 00 

[brian-armstrong]

It looks like you may be simulating an error in transmission with 0xFF? Libcorrect doesn't like this because it's outside the range for GF(2^4) - only values between 0 and 15 are really valid.

If you want to simulate an error, your best bet might be to use 0-15 only. Alternately if you want to simulate transmission, do encode, then pack every 2 values into a byte, then apply error and finally unpack the bytes and then decode.

My assumption is that anyone using this mode will pack the bytes since they'd be wasting 50% of their bits if not, but if that's not the case, let me know and I can change the behavior. I guess libcorrect could treat these invalid values as erasures instead.

[vinnitu]

Thank you very much.

    int j = 4;
    int e = 2;
    size_t min_distance = e * 8 / j;

    int fx = (2 << 3) + 2 + 1; // x4 + x + 1
    correct_reed_solomon *rs = correct_reed_solomon_create(fx, 1, 1, min_distance);

    uint8_t msg[3] = {0x12, 0x34, 0x56};
    uint8_t msg2[6];
    uint8_t msg3[10];
    uint8_t msg4[5];

    for (int i = 0; i < sizeof(msg); i++) {
        msg2[i * 2] = msg[i] >> 4;
        msg2[i * 2 + 1] = msg[i] & 0xf;
    }

    correct_reed_solomon_encode(rs, msg2, sizeof(msg2), msg3);

    for (int i = 0; i < sizeof(msg4); i++) {
        msg4[i] = (msg3[i * 2] << 4) | (msg3[i * 2 + 1]);
    }

msg: 12 34 56 
msg2: 01 02 03 04 05 06 
msg3: 01 02 03 04 05 06 0D 02 04 0E 
msg4: 12 34 56 D2 4E

[brian-armstrong]

Awesome, glad to hear it.

Let me know if you get it decoding transmissions. Sounds really cool :+1:

[vinnitu]

Hello! In discussion with developer of yamcs was found incorrect place in my example

correct_reed_solomon *rs = correct_reed_solomon_create(fx, 1, 1, min_distance);

must be

correct_reed_solomon *rs = correct_reed_solomon_create(fx, 6, 1, min_distance);

[MCE66-GitHub]

Hello, I'm trying to use this lib for CCSDS frame RS (10,6) checking. May I ask why the "short_rs" branch is not "merged" into the master? Are there any drawbacks in using this branch instead of master? Best regards and thanks for your work.

[rahul-aeg]

hey @vinnitu i am trying to use it for ccsds RS(255,223) and polynomial is x^8+x^7+x^2+x+1 which is 0x187 now what should be the other 2 terms in correct_reed_solomon_create() what is first_consecutive_root and generator gap here i can't understand

[MCE66-GitHub]

Hello @rahul-aeg , I used this code for CCSDS RS(255,239). I think the RS(255,223) should work in a similar way, as follow: ccsds_255_239 = correct_reed_solomon_create(0x187, 120, 11, 16); ccsds_255_223 = correct_reed_solomon_create(0x187, 112, 11, 32);

[rahul-aeg]

@MCE66-GitHub ok but how is it calculated ? that's what i want to know in reference when i couldn't understand what to put i just put 1 in both and corrupted 16 bytes of data from encoded data knowingly and then decoded it and it recovered fully but i want to know how this came to 1 how is it calculated, also if i tried to corrupt more than 16 bytes the decoded returned nothing in the output array

[MCE66-GitHub]

Hello @rahul-aeg , when I used this code I made some reserch. These numbers are given in CCSDS specifications. I do not remember the exact document, but if you serch on internet you can find some references, for example a description is in https://github.com/crozone/ReedSolomonCCSDS. Remember that for a complete CCSDS transfer frame encoding and decoding you shall also implement the interleaving and the dual basis conversion.