CCSDS Reed Solomon Encoding

Question

I am working on a project where I need to encode 896 bytes of data into a 128 byte codeword. All the specifications for my project are defined by CCSDS in this paper on about page 15 of the pdf. http://public.ccsds.org/publications/archive/101x0b3s.pdf A few things not explicitly specified in that document are J=8, E=16 (255/223) and I=4.

I've read through this (and numerous other articles) multiple times but I don't seem to be grasping what's going on in the slightest. I've even tried the code found at http://zxingnet.codeplex.com/SourceControl/latest#trunk/Source/lib/common/reedsolomon/GenericGF.cs

and it's not working for me either. Has anyone worked with this? I need some direction as I'm feeling lost after grinding on this for so long.

The best solution for me would be if I was just imputing the information into zxing code wrong.

Answer 1

I'm late to this question, but just in case this can help anyone else:

The easiest and most common method of implementing Reed Solomon on digital computers is using the RS (255, 223) CCSDS encoding. This encoding is specified by the CCSDS and has been widely used for decades in hardware like deep space probes and satellites.

RS (255, 223) has the following characteristics:

• Each symbol has 2^8 combinations (J = 8), so each symbol is a byte.
• Each codeword has 2^8 - 1 symbols, so each encoded block is 255 bytes long.
• The amount of data you can encode per block is 223 bytes
• Each block contains 32 bytes of parity data for FEC (223 data bytes + 32 parity bytes = 255 byte block)
• Without knowing erasures (error locations), up to 16 errors can be corrected per block (E = 16, this always equals the number of parity bytes / 2)
• When error locations are known, up to 32 errors can be corrected per block (this always equals the number of parity bytes)
• CCSDS specifies use a field generator polynomial of 1 + X + X^2 + X^7 + X^8, a code generator with first consecutive root = 112, and a primitive element of 11.
• CCSDS also specify a dual-basis polynomial representation in order to simplify encoder/decoder implementations in dedicated hardware. This is one feature that is omitted from many modern software implementations of RS (255, 223) because it serves no practical use for general purpose CPUs, but it's still required when communicating with legacy hardware. Definitely figure out whether you need this - it can be accomplished by running the normal polynomial output through a lookup table before/after encoding/decoding.

A 255 symbol codeword can be interleaved four times (I = 4) to give a total block size of 892. This can be done to spread out transmission burst errors between each of the codewords, increasing the chances of successful codeword correction. See the spec linked below for the exact details.

I'm not sure what you meant by the "128 byte codeword", but it might have something to do with padding:

Since the symbol size of 2^8 is a fairly hard constraint, each codeword must be 255 bytes long. However, if you can't send a 255 byte block in one go, or prefer more error protection, padding can be used to effectively shorten the 255 byte block.

Padding works by simply defining some of the 223 data bytes as padding instead of data. Padding is just some fixed sequence of values that both the sender and receiver know ahead of time (the CCSDS refers to this as "virtual fill"). When encoding, a short amount of data is added to the start of the data to form the full 223 "data" bytes, and these are fed into the encoder as normal. After encoding, the padding is stripped from the start of the block, producing a shorter block (or rather, the data and parity may be copied to a smaller array). This is then transmitted.

When decoding, the padding is then inserted back at the start of the block before the decoder is run. Since the padding sequence has known fixed values, there is a 0% chance that these bytes will contain errors. This means that the 16 bytes of error protection will shift to the rest of the block.

So, to get a 127 byte block from RS (255, 223), you could pad all but 95 bytes of data out of the original 223 bytes, and then encode that. Your block will look like:

padding[128] + data[95] + parity[32] = 255 bytes

Then remove the padding before sending the block:

data[95] + parity[32] = 127 bytes

And finally on the decoder side, add the padding back in before decoding:

padding[128] + data[95] + parity[32] = 255 bytes

This is effectively an RS(127, 95) code, and offers 16 bytes of FEC per 127 byte block.

The CCSDS standard specifies that the virtual fill:

• Must consist of all zeros
• Must not be transmitted
• Must not change in length for a Mission Phase on a particular Physical Channel
• Must be inserted only at the beginning of the codeblock
• Must be inserted only in integer multiples of 8I bits.

You only need to adhere to these if the legacy device you're talking to implements these strictly as well (and if it's strictly CCSDS, it will).

For a C# implementation of RS (255, 223), I have a small library here:

https://github.com/crozone/ReedSolomonCCSDS

This was based on Phil Karn's C implementation which is found everywhere, including GNURadio and Android OS.

CCSDS Summary: "TM SYNCHRONIZATION AND CHANNEL CODING— SUMMARY OF CONCEPT AND RATIONALE" (Section 5)

https://public.ccsds.org/pubs/130x1g2.pdf

CCSDS Reference: "TM SYNCHRONIZATION AND CHANNEL CODING" Section 4.

https://public.ccsds.org/Pubs/131x0b3e1.pdf

Answer 2

Here is my interpretation of the CCSDS protocol:

J=8, means 8-bits per symbol (=1 byte). E=16, means 16 errors corrected by the RS code.

This requires 32 parity symbols and the RS codeword is thus 255 bytes long with 223 information bytes.

I=4, means that one interleaver block consists of 4 code words.

The total number of information bytes available in one block is thus 4*223 = 892 bytes. This is four bytes less than the 896 stated in your question. I'm quite sure you misread the 128 byte codeword, so maybe you misread the number bytes as well.