# Coding proposal

• Subject: [amsat-bb] Coding proposal
• From: "MCGWIER ROBERT" <rwmcgwier@xxxxxxxx>
• Date: Sat, 10 Feb 2001 14:39:10 -0500

I have discussed with others a way to do coding
of the telemetry on AO-40 that would be
backward compatible with the existing
some data storage that may not exist.  My
ignorance of the layout of the  IHU memory
prevents me from knowing if this is workable.

An analysis of the fading patterns shows that
we get several fades per revolution.

With 17.7-ish RPM rotation rate, this will give
35 fades per frame and if we assume that
bits wiped.  If we assume that we can identify
the likely bad bits and call most of them erasures
we have a chance with a scheme that will fix
most of the errors.

Suppose we send the A (or any other frame)
AS IS.   Nothing is changed.   After the frame
is sent we make parity bits up that enable
us to correct errors.   Since we are sending
a systematic code ( that is we send the
data without change)  and attach coding
information,   this mitigates against using
convolutional codes since the systematic
convolutional codes are uniformly pretty
weak.  There is a lot to speak for the
systematic approach since it will be
backwards compatible.

Since we have existing implementations of
Reed Solomon codes:

http://people.qualcomm.com/karn/code/fec/

Let me make a concrete proposal using
this code as a basis.  This is C code and
would have to be adapted.  On board the
spacecraft, all the code  needed on board is

/* From the link above */

for(i = KK - 1; i >= 0; i--) {
feedback = Index_of[data[i] ^ bb[NN - KK - 1]];
if (feedback != A0) {       /* feedback term is non-zero */
for (j = NN - KK - 1; j > 0; j--)
if (Gg[j] != A0)
bb[j] = bb[j - 1] ^ Alpha_to[modnn(Gg[j] + feedback)];
else
bb[j] = bb[j - 1];
bb[0] = Alpha_to[modnn(Gg[0] + feedback)];
} else {    /* feedback term is zero. encoder becomes a
* single-byte shifter */
for (j = NN - KK - 1; j > 0; j--)
bb[j] = bb[j - 1];
bb[0] = 0;
}
}

where  Gg is the 83 byte table, and Alpha_to is
a 256 byte table, and Index_of is a 256 byte table.

modnn(int x)
{
while (x >= NN) {
x -= NN;
x = (x >> MM) + (x & NN);
}
return x;
}

As you can see, you need to make a couple
of assumptions. Let's  assume that storage
on the order of the size of the frame can be
found.  I have no knowledge concerning this,
I only hope that it is so.  Assume this area is
856 bytes.

(514 bytes is the size of the frame).  This
proposal is that we use a (255,172) Reed
Solomon code.

We need 256 bytes to store a table needed
for exponents in the encoding, 85 bytes for
polynomial needed in the encoder, and
256 bytes for the Index array.  This
is all one time work for these arrays, done
on the ground and uploaded with the IHU
code.

We then encode 172 bytes of the frame per
time and this would be done 3 times.  This
will generate 255-172 = 83 bytes of parity
for each of the 172 byte blocks.  3*172
is 516.  We could stuff zeroes but for simplicity's
sake,  we assume that we simply recode
2 of the bytes in the last encoding.  This makes
the encoding routine identical for each
of the codeword computations.

In the 256 bytes of the storage area NOT used
for storing tables needed for encoding, we
store the 83 bytes for each of the  three codewords.
That is 249 bytes.   I suggest that we simply
copy this 249 bytes twice into the "frame transmit
buffer".  We could even transmit a computed
CRC if you like or fake one.

This code will correct 41 errors in each codeword,
or 83  erasures or some combination where
errors + (erasures/2  ) <=  41 for a total of
(say)  123 bit errors per frame.  There are
514 bytes per frame,  or 4112 bits so we
can correct up to 3% errors, even if they
occur in bursts.  We are sending the
parity bits twice, so we can get a little bit
fancier if we need to.  We can go UP from
here.  If we find this is not enough
error correction,  then we increase the
amount of storage required but get much
better error correction.  For example,  if we
go to  (255,86) code, we will need to send
TWO frames of parity bits to get the code
words in ONCE.   Furthermore, we will
now need 1700 extra bytes of storage.

I hope somebody will take the time to check this
for stupidity and comment.

Bob

----
Via the amsat-bb mailing list at AMSAT.ORG courtesy of AMSAT-NA.
To unsubscribe, send "unsubscribe amsat-bb" to Majordomo@amsat.org

AMSAT Home