DPRG
DPRG List  



DPRG: Error correction/detection

Subject: DPRG: Error correction/detection
From: Aaron and Hifumi aaron_hifumi at bigfoot.com
Date: Fri Jun 18 15:31:59 CDT 1999

Hi Matt. I haven't done anything too elaborate. The amount of information that
gets transmitted back and forth is usually fairly short, so I've broken it into
10 byte packets. I'm not sure what this type of protocol is called. I'll outline
what I've done below.

I send 8 bytes of information, and 2 bytes of parity information. Imagine the 8
bytes as an X by Y grid with 64 cells. One parity byte checks the X columns, and
one parity byte checks the Y rows. The advantage to this over a simple 7 bits and
1 parity bit every byte is that I can not only find errors, but can fix the
errors in most cases without having to re-transmit.

Ascii drawing.... I hope this comes thru...

O.O.O.O.O.O.O.O - Y
O.O.O.O.O.O.O.O - Y
O.O.O.O.O.O.O.O - Y
O.O.O.O.O.O.O.O - Y
O.O.O.O.O.O.O.O - Y
O.O.O.O.O.O.O.O - Y
O.O.O.O.O.O.O.O - Y
O.O.O.O.O.O.O.O - Y
X.X.X.X.X.X.X.X

The O's are my transmitted bits, and the Y and X are my parity bits/bytes. Now,
suppose the an error occurs on the first byte that I transmit in the 4th
position, like so...

O.O.O.E.O.O.O.O - Y
O.O.O.O.O.O.O.O - Y
O.O.O.O.O.O.O.O - Y
O.O.O.O.O.O.O.O - Y
O.O.O.O.O.O.O.O - Y
O.O.O.O.O.O.O.O - Y
O.O.O.O.O.O.O.O - Y
O.O.O.O.O.O.O.O - Y
X.X.X.X.X.X.X.X

My first Y bit will show a parity error, and my 4th X bit will show a parity
error. Thus, I know that the 4th bit in the first byte is the wrong value, and I
just switch it.... ie- from a 1 to a 0 or visa versa.

With this scheme, as long as I don't end up with 2 errors in the same row or
column, I can correct up to 8 bit errors in the 8 bytes of information. Now, if
something happens, and the X and Y parity errors don't match up for some reason
(ie- transmit error in the parity bytes transmitted) , or I have 2 errors on the
same row/column, I have a serious problem. In these cases, I have to either
re-transmit the entire 10 bytes again, or if my algorithms are smart, I can just
re-transmit the troublesome columns or rows.

I hope you get what I mean. Parity, if you have never run across the term, means
to make the bits that you are transmitting either even or odd. For example, if I
decided to use even parity, and I was transmitting a 11001010 byte, i would be
sending 4 1's, which is an even number of ones, therefore my parity bit would be
a 0, because I don't need to add any 1's to make the number of 1's even. Using
the same byte, 11001010 with odd parity, I would transmit a 1 to bring the number
of 1's to 5.

So, using my 8x8 thing above, suppose I using even parity, and transmitting these
8 bytes:

1.0.0.0.0.0.0.0
1.1.0.0.0.0.0.0
1.1.1.0.0.0.0.0
1.1.1.1.0.0.0.0
1.1.1.1.1.0.0.0
1.1.1.1.1.1.1.0
1.1.1.1.1.1.1.1

My Y parity byte would be 1.0.1.0.1.0.1.0 and my X parity byte would be
0.1.0.1.0.1.0.1

Probably most often when people talk about parity bits, they are talking about
using 7 data bits and 1 parity bit, so that everything fits all in one byte. For
example, the seven bits 1.1.0.1.1.0.1 need to be transmitted, with even parity,
the parity bit would be 1 (the 7 bits contain 5 1's, we need one more to make a
nice even 6), so the byte transmitted would be 1.1.0.1.1.0.1.1

I sent this to the list too, in case anyone else was interested in some type of
autocorrecting parity scheme. Sorry i can't remember the official name of it.

Aaron

(hope I didn't make any mistakes....)

Matt Minnis wrote:

> Aaron,
>
> How are you dealing with error correction/detection?
>
> I have the Linx Technologies 900Mhz links, and they get sporadic bursts of
> noise.
>
> I was just wondering how others are dealing with this?
>
> Thanks,
>
> Matt Minnis

------------------------------

More information about the DPRG mailing list