Generator polynomial

[davnat]

Hello, I'm trying to use your library in an Aztec (https://en.wikipedia.org/wiki/Aztec_Code) encoder/decoder.

I already coded the encoder, and it works, but I had to change the generator polynomial for the 255 and the 4095 codecs (to be honest, for now I'm just using the 255 codec, as you require to statically create all the needed codecs at compile-time, and the 255 codecs alone take ~14MB), because the Aztec spec requires one that is different from what you choose.

1. is there a way to instantiate a RS codec using a custom generator polynomial, or do I need to edit your code?
2. can I ask how you choose the generator polynomials? are there any constraints?

Thanks, Cheers

[pjkundert]

Hi, davnat;

You can create a Reed-Solomon Codec with any generator polynomial you wish. The "defaults" are just those I've pre-defined in c++/ezpwd/rs. See the code there to define new RS... macros with different generator polynomials.

Is this for a memory-constrained embedded application? If so, you can trade off space for speed, and use the excellent Phil Karn implementation (LGPL and GPLv2 licensed). They are not quite as fast as my C++ implementation, because it generates encode/decode routines for specific table sizes (hence the size).

For the Aztec encoder/decoder, you'll need only 5 distinct R-S codecs. See: https://github.com/delimitry/aztec_code_generator/blob/master/aztec_code_generator.py for the 5 sizes, and the polynomials required.

[davnat]

See the code there to define new RS... macros with different generator polynomials

So, you mean that I'm required to modify your code, right?

Thanks

[pjkundert]

Nope; you can copy the way define new RS...<> type templates. For example, the default polynomial for RS(255,...) Reed-Solomon codecs is 0x11d It is defined in c++/ezpwd/rs as:

template < size_t SYMBOLS, size_t PAYLOAD > struct RS;
....
template < size_t PAYLOAD > struct RS<  255, PAYLOAD> : public __RS( RS, uint8_t,    255, PAYLOAD,   0x11d,  1,  1 );

Later, I define the RS_CCSDS type -- also an RS(255,...) codec, but with the polynomial 0x187:

template < size_t SYMBOLS, size_t PAYLOAD > struct RS_CCSDS;
template < size_t PAYLOAD > struct RS_CCSDS<255, PAYLOAD> : public __RS( RS_CCSDS, uint8_t, 255, PAYLOAD, 0x187, 112, 11 );

You can do the same thing -- create your own RS_... type, with your own polynomial. Just create the base type, and then a specialization with the correct generator polynomial. You'll need to know the correct "First Consecutive Root" and "Primitive Root" for the generator polynomial. As a non-mathematician, I don't know how to derive such things, but they should be available in other Aztec documentation (perhaps by different names?).

[davnat]

I'll give it a try, thank you.