Lost bytes and reed-solomon


#1

I’m working on a self-educational project to replace the simple CRC in
the tunnel apparatus with a very heavy reed-solomon encoding for very
lossy and low-bandwidth links. One thought just occurred to me.
Originally, I was going to group up all of my data in 127 byte blocks,
r/s encode it with a 255,127, and just shove each 255 byte block into a
new payload string which would basically be twice as long with reed
solomon parity stuff every other 127/128 bytes from each respective
block and then just grab each 255 bytes and run them through the decoder
on the receive and do the opposite, shoving each decoded 127 bytes into
a decoded payload.

But the thought was, what if a byte is completely obliterated- then
everything would be shifted over one (or more) and my groupings wouldn’t
align so I’d be looking in the wrong places for parity and not know that
there was a total deletion rather than just a corruption? Is there any
way to prevent/identify this case, or can it even happen?


#2

Brett L. Trotter wrote:

removed_email_address@domain.invalid
http://lists.gnu.org/mailman/listinfo/discuss-gnuradio

Partially answering myself here (and expanding on my question/thought)

I suppose a simple answer would be to check the length of the received
payload and if not a multiple of 255, just discard the whole thing- then
we can at least identify the deletion. Since we can’t pinpoint where it
was, we can’t just fill it in with a 0 that would get repaired
(hopefully)… If this is the right move, then the question becomes, how
often can a byte be lost in transmission, and is it more often than only
corruption occurs? If it is rare enough, then the loss of the entire
packet is acceptable (and no worse than the current CRC), but if it
isn’t so rare, would the reed-solomon do much good in the first place?


#3

The receiver doesn’t ‘loose’ symbols; it will clock through the correct
amount of data, assuming it is tracking the signal bauding rate. The
symbols will be in error, though. So, your length should be constant
for good packets as well as bad. If the baud tracking loop is having
trouble, you will typically stuff or delete a symbol (maybe), which then
garbles up everything until you re-establish time sync.
Kent Torell


#4

— “Brett L. Trotter” removed_email_address@domain.invalid wrote:

But the thought was, what if a byte is completely obliterated- then
everything would be shifted over one (or more) and my groupings
wouldn’t align

No it’s not like that. The transmitter clocks out
bits at a fixed rate. When some of the bits are
covered with noise and “lost” the following bits
are not send backwards in time to take the place of
the “lost” bits. So if I send “Hello World” and one
characters is lost you might get “Hello W rld” you
would not get “Hello Wld”. Bits come in fixed
“windows” of time and in every window you either
see a 1, 0, or “X” but the window of time does not
disappear. Ok not a perfect example because if the
data drops out for more than a few bits the clock on
the receiver could loose sync and you would not know
how many bits were lost but there is typically a
pattern in the frame headers that allows the clock to
re-sync.

Chris Albertson
Home: 310-376-1029 removed_email_address@domain.invalid
Office: 310-336-5189 removed_email_address@domain.invalid


The fish are biting.
Get more visitors on your site using Yahoo! Search Marketing.
http://searchmarketing.yahoo.com/arp/sponsoredsearch_v2.php


#5

Got a few good replies on my question about lost bytes. I appreciate the
input, that sounds like it’ll work great in conjunction with the error
correction then. I’m hoping to have that in place within the next couple
of hours and start testing.


#6

— “Brett L. Trotter” removed_email_address@domain.invalid wrote:

But the thought was, what if a byte is completely obliterated- then
everything would be shifted over one (or more) and my groupings
wouldn’t align

No it’s not like that. The transmitter clocks out
bits at a fixed rate. When some of the bits are
covered with noise and “lost” the following bits
are not send backwards in time to take the place of
the “lost” bits. So if I send “Hello World” and one
characters is lost you might get “Hello W rld” you
would not get “Hello Wld”. Bits come in fixed
“windows” of time and in every window you either
see a 1, 0, or “X” but the window of time does not
disappear. Ok not a perfect example because if the
data drops out for more than a few bits the clock on
the receiver could loose sync and you would not know
how many bits were lost but there is typically a
pattern in the frame headers that allows the clock to
re-sync.

Chris Albertson
Home: 310-376-1029 removed_email_address@domain.invalid
Office: 310-336-5189 removed_email_address@domain.invalid

  ____________________________________________________________________________________Fussy? 

Opinionated? Impossible to please? Perfect. Join Yahoo!'s user panel
and lay it on us.
http://surveylink.yahoo.com/gmrs/yahoo_panel_invite.asp?a=7


#7

Brett L. Trotter wrote:

Got a few good replies on my question about lost bytes. I appreciate the
input, that sounds like it’ll work great in conjunction with the error
correction then. I’m hoping to have that in place within the next couple
of hours and start testing.

Two words … preambles and frame sync.

One thing to be aware of … it is possible with most software PLLs …
under crummy signal conditions … to drop single bits (but not whole
bytes). If the PLL is completely out of phase from where the mid
point(s) of the symbol stream are located … it can correct by either
speeding up or slowing down. Depending upon the previous state and
symbol history up to that point … it can have the effect of inserting
an erroneous bit or dropping a bit from the stream.

Any frames of data where this occurs are very likely trashed and not
recoverable. You’ll want a mechanism to reliably detect the start of
each frame. For fixed sized frames of “N” bits … bits added or missing
distory the bit count for one frame. If you assume the next “N” bits
belong to the next frame … the bits in the next frame will be shifted
by one bit … effectively trashing the follow-on frames too.

Most protocols use a fixed bit pattern … a frame sync … to mark the
beginning of each frame. You’ll lose some bandwidth … but it makes the
job of recovering from a lost frame much easier.

If your protocol calls for short bursts of data … you may want to pad
the start of each transmission with an alternating symbol pattern. This
gives the software PLL time to synchronize at the symbol level and
accept the real data that follows.

-rick