Post by thread:Error rates for SCI pic16c74

NEIL GANDLER <spam_OUTPICLISTTakeThisOuTMITVMA.MIT.EDU> wrote: > I plan on using the SCI modules of two PIC16c74 for full duplex > asychronous communication. .... I was wondering if the 9th bit > parity option is adequate for error detection. Just to be safe, I > designed my software to send a 32 bit packet and then resend an > identical copy. If they both matched, the receiver will assume all > bits are correct. That would achieve excellent error detection yet > eat up quite a bit of transmission time, but still could be > practical. Neil: What you're doing, essentially, is sending an even-parity bit for every bit of your original 32-bit message. You may want to examine this solution... Let's say, for the sake of argument, that each bit has a 99% probability of getting through correctly. If you send the message with no error-checking at all, your error rate (the odds of undetectable incorrect reception) will be about 17.5%. Obviously, SOMETHING must be done. Let's say that you just use the built-in "9th-bit parity" option. The error rate for each byte is about 0.34%, so the error rate for the whole 32-bit message will be about 1.36%... A significant improvement, and achieved with only four bits of overhead. Now let's do the math for your "parity bit for each data bit" solution: Each bit has an error rate of 0.01%, so the error rate for the whole packet will be approximately 0.32%. Out of 10,000 messages sent, the "9th-bit parity" method will ensure that 9,863 messages get through correctly. Your method improves this to 9,968 messages -- about 1% more -- but at a cost of eight times the overhead. Keep in mind that all of the above assumes that when a detectable error occurs, the receiver can signal the transmitter to re-send the message. Given our 99%-per-bit probability of sending the correct message, this means that ALMOST 50% OF ALL MESSAGES WILL NEED TO BE RE-SENT. Of course, 99%-correct probability is pretty low... Most communication channels are much more reliable than this. Still, it's something to think about. Something else to consider is that there's a certain error probability for the "resend the last message" signal that the receiver sends to the transmitter. If THAT message has undetectable errors, God only knows what your communication system will do. Ok. What you might want to do is investigate alternative error-control coding methods. My suggestion for this application would be a (7,4) Hamming code, in which 3 parity bits are added to each nibble of your original data. This means that there will only be 24 bits of overhead versus the 32 bits that your scheme requires, BUT... You'll be able to correct any single-bit error without asking the transmitter to resend, OR you'll be able to detect any double-bit errors and ask for a re-transmission. As an added bonus, you'll be able to detect a few triple-bit errors. However, these are very rare -- even with our unrealistically-high 1% error rate per bit, a 3-bit error in a 56-bit message will happen only once in 20,280 messages -- so I wouldn't get too excited about the capability. I posted a message about Hamming codes here a few months ago... If you're interested, let me know and I'll dig it up. Hamming codes (at least the little ones like the one I'm suggesting you use) are real easy to implement on a PIC. -Andy Andrew Warren - .....fastfwdKILLspam@spam@ix.netcom.com Fast Forward Engineering, Vista, California http://www.geocities.com/SiliconValley/2499

On Mon, 1 Jul 1996, Andrew Warren wrote: {Quote hidden}> NEIL GANDLER <PICLISTKILLspamMITVMA.MIT.EDU> wrote: > > > I plan on using the SCI modules of two PIC16c74 for full duplex > > asychronous communication. .... I was wondering if the 9th bit > > parity option is adequate for error detection. Just to be safe, I > > designed my software to send a 32 bit packet and then resend an > > identical copy. If they both matched, the receiver will assume all > > bits are correct. That would achieve excellent error detection yet > > eat up quite a bit of transmission time, but still could be > > practical. > > Neil: > > What you're doing, essentially, is sending an even-parity bit for > every bit of your original 32-bit message. > > You may want to examine this solution... Let's say, for the sake of > argument, that each bit has a 99% probability of getting through > correctly. > > If you send the message with no error-checking at all, your error > rate (the odds of undetectable incorrect reception) will be about > 17.5%. Obviously, SOMETHING must be done. > > Let's say that you just use the built-in "9th-bit parity" option. > The error rate for each byte is about 0.34%, so the error rate for > the whole 32-bit message will be about 1.36%... A significant > improvement, and achieved with only four bits of overhead. > > Now let's do the math for your "parity bit for each data bit" > solution: Each bit has an error rate of 0.01%, so the error rate for > the whole packet will be approximately 0.32%. > > Out of 10,000 messages sent, the "9th-bit parity" method will ensure > that 9,863 messages get through correctly. Your method improves this > to 9,968 messages -- about 1% more -- but at a cost of eight times > the overhead. > > Keep in mind that all of the above assumes that when a detectable > error occurs, the receiver can signal the transmitter to re-send the > message. Given our 99%-per-bit probability of sending the correct > message, this means that ALMOST 50% OF ALL MESSAGES WILL NEED TO BE > RE-SENT. > > Of course, 99%-correct probability is pretty low... Most > communication channels are much more reliable than this. Still, > it's something to think about. > > Something else to consider is that there's a certain error > probability for the "resend the last message" signal that the > receiver sends to the transmitter. If THAT message has undetectable > errors, God only knows what your communication system will do. > > Ok. What you might want to do is investigate alternative > error-control coding methods. My suggestion for this application > would be a (7,4) Hamming code, in which 3 parity bits are added to > each nibble of your original data. This means that there will only > be 24 bits of overhead versus the 32 bits that your scheme requires, > BUT... > > You'll be able to correct any single-bit error without asking the > transmitter to resend, OR you'll be able to detect any double-bit > errors and ask for a re-transmission. > > As an added bonus, you'll be able to detect a few triple-bit errors. > However, these are very rare -- even with our unrealistically-high 1% > error rate per bit, a 3-bit error in a 56-bit message will happen > only once in 20,280 messages -- so I wouldn't get too excited about > the capability. > > I posted a message about Hamming codes here a few months ago... If > you're interested, let me know and I'll dig it up. Hamming codes (at > least the little ones like the one I'm suggesting you use) are real > easy to implement on a PIC. > > -Andy > > Andrew Warren - .....fastfwdKILLspam.....ix.netcom.com > Fast Forward Engineering, Vista, California > http://www.geocities.com/SiliconValley/2499 > >> Correct me if I wrong but, this is how I view this error scheme. If I send a 32 bit word, and then an identical 32 bit word. The odds of those words being corrupted in the EXACT same pattern are extroadinarily low. If the two words do not match, then the packet is discarded and the PIC simply waits for the next one. There is no reason to request a resend. While this substantially increases the amount of packets that may be discarded it almost perfectly assures that the data is not corrupt, which is very important in my application. I don't have any numerical data to substantiate this, but I am basically approximating probability. Again, please correct me if I wrong. Thanks for the advice. Neil Gandler

> Correct me if I wrong but, this is how I view this error scheme. > If I send a 32 bit word, and then an identical 32 bit word. The odds > of those words being corrupted in the EXACT same pattern are > extroadinarily low. If the two words do not match, then the packet is > discarded and the PIC simply waits for the next one. There is no > reason to request a resend. While this substantially increases the amount > of packets that may be discarded it almost perfectly assures that the > data is not corrupt, which is very important in my application. > I don't have any numerical data to substantiate this, but I am basically > approximating probability. Again, please correct me if I wrong. Thanks > for the advice. To be sure, it may seem unlikely that you'd have two identical bad packets come down the pipe, but pathological conditions may make it happen much more frequently than the once every 4*10^9 packets sheer chance would suggest. For example, eight consecutive noise-bursts could be interpreted as eight bytes; depending upon the source of the noise-burst all eight might very well be identical. Even worse, the protocol you've described gives little or no assurance that a packet won't be "off" by a byte; in fact, if packets are sent with less than a byte time between them this could generate systemic errors. To be sure, sending your packet twice is probably going to be fairly reliable if you XOR the second copy with a non-trivial data mask (to make sure that the data bit pattern has to be different to match). On the other hand, there are other methods that yield the same reliability with less overhead, or which provide better error recovery with the same over- head. If speed is not critical, this may not be an issue and the simplicity of sending the data twice (with slight munging the second time) may be an advantage. Note that for the packet sizes you're using, there really isn't any practical way to use an error-correcting code; most bit errors will likely cause framing errors, and ECC's are likely to botch on those.

Neil Gandler <EraseMEgandlerspam_OUTTakeThisOuTACSU.Buffalo.EDU> wrote: > Correct me if I wrong but, this is how I view this error scheme. If > I send a 32 bit word, and then an identical 32 bit word. The odds > of those words being corrupted in the EXACT same pattern are > extroadinarily low. Neil: I believe that I already corrected your assumption in my previous message. Here's the math so you can follow along: If there's an error rate (call it "p") for each bit, the odds of transmitting 64 bits with zero errors is (1-p)**64. For a hypothetical (high) error rate of 1%, this works out to only 52%, which means that NEARLY HALF OF ALL MESSAGES WILL BE RECEIVED WITH ERRORS. Now... To find the number of errors that your scheme will detect, you need (as you know) to find the probability of two errors occurring with a separation of exactly 32 bits. To make this easy, you can treat your transmission as a series of 32 2-bit packets, each of which contains either "00" or "11". This is exactly equivalent to your scheme, and it reduces the problem to discovering the odds of transmitting 32 two-bit packets with fewer than two errors in each packet. Ok... The odds of transmitting a two-bit message and making at most one error in transmission is: (1-p)**2 + 2p(1-p) = 0.99**2 + 2*0.01*0.99 = 0.9999 Since you're transmitting 32 of these packets, the odds of receiving the entire message with no undetectable errors is: 0.9999**32 = 0.9968 This means, as I said in my previous message, that a little more than 3 messages in every 1000 will slip through with undetectable errors. If this sort of error rate is ok in your application, more power to you. > If the two words do not match, then the packet is discarded and > the PIC simply waits for the next one. There is no reason to > request a resend. While this substantially increases the amount of > packets that may be discarded .... Assuming that your error rate is as high as 1% per bit, you'll be discarding nearly half of all received messages. > .... it almost perfectly assures that the data is not corrupt, > which is very important in my application. If correct transmission is very important, take my advice and use a Hamming code. > I don't have any numerical data to substantiate this, but I am > basically approximating probability. Again, please correct me if I > wrong. Thanks for the advice. The first thing you need to do is quantify your communication channel's ACTUAL error rate... Without that information, none of the math can help you decide whether your solution is adequate. -Andy Andrew Warren - fastfwdspam_OUTix.netcom.com Fast Forward Engineering, Vista, California http://www.geocities.com/SiliconValley/2499

At 03:29 07/01/96 -0500, John Payson wrote: Note that for the packet sizes you're using, there really isn't >any practical way to use an error-correcting code; most bit errors will >likely cause framing errors, and ECC's are likely to botch on those. John, you sure got that right. In disk controllers, which tend to use fairly humongous ECCs, sector data can always be located in time relation to a sync pulse which is generated by hardware, at, say, zero degrees of rotation (e.g. floppy disks have little holes at sector 0). Therefore, even if you read incorrect data, at least you WILL be reading data. So ECCs make great sense and work just fine - when's the last time you actually had data corrupted on your hard disk? DBLSPACE users need not reply. UART serial? Not a chance. Data looks just like framing except for context. Lose the context, and you'll lose the data, and all the ECCs in the world won't help. But now you can do something disk controllers can't possibly do: NAK and repeat...

Rich Leggitt <@spam@PICLISTKILLspamMITVMA.MIT.EDU> wrote: > > [Quoting John Payson:] > > Note that for the packet sizes you're using, there really isn't > > any practical way to use an error-correcting code; most bit errors > > will likely cause framing errors, and ECC's are likely to botch on > > those. > > John, you sure got that right. > .... > UART serial? Not a chance. Data looks just like framing except for > context. Lose the context, and you'll lose the data, and all the > ECCs in the world won't help. Guys: Error-correcting codes actually work BETTER with this sort of error. Assuming that you're performing the low-level communications in software (or that your hardware allows you to deal directly with the incoming signal), you'll have three possibilities for each bit: 1. Correct reception, 2. A binary error (in which a "1" bit is incorrectly read as a "0" or vice-versa, or 3. An "erased" bit (in which you read neither a 0 nor a 1). While a simple (7,4) Hamming code like the one I proposed can correct only one "type-2" error per 7-bit codeword, it can correct TWO "type-3" errors. The reason for this somewhat-unintuitive behavior is that the error-correcting code normally has to do two jobs: It has to both FIND the error and CORRECT it. If your errors are of the "erasure" variety, the "FIND" half of its job is already done. If Neil used a (7,4) Hamming code and interleaved the bits of his 8 code words, he'd be able to properly reconstruct his data even if 28% of his transmission were wiped out by burst noise. -Andy Andrew Warren - KILLspamfastfwdKILLspamix.netcom.com Fast Forward Engineering, Vista, California http://www.geocities.com/SiliconValley/2499

But Andy... if you have an error in the UART framing, you probably won't receive anything to correct! I don't know of any way to tell the difference between, say, an 0xFF with an erroroneous start bit, and no data sent at all. Anyway, I do kinda remember that the 7,3 hamming code trick is pretty slick... assuming I'm actually remembering the right thing... can be implemented as a 128 nibble lookup table for receive? - Rich At 01:12 07/02/96 -0800, Andrew Warren wrote: {Quote hidden}>> .... >> UART serial? Not a chance. Data looks just like framing except for >> context. Lose the context, and you'll lose the data, and all the >> ECCs in the world won't help. > >Guys: > >Error-correcting codes actually work BETTER with this sort of error. >Assuming that you're performing the low-level communications in >software (or that your hardware allows you to deal directly with the >incoming signal), you'll have three possibilities for each bit: > > 1. Correct reception, > 2. A binary error (in which a "1" bit is incorrectly read as a > "0" or vice-versa, or > 3. An "erased" bit (in which you read neither a 0 nor a 1). > >

Rich Leggitt <TakeThisOuTPICLISTEraseMEspam_OUTMITVMA.MIT.EDU> wrote: > But Andy... if you have an error in the UART framing, you probably > won't receive anything to correct! I don't know of any way to tell > the difference between, say, an 0xFF with an erroroneous start bit, > and no data sent at all. Rich: John Payson made the same point in private e-mail, so I'll take the blame for being unclear. When I said: "Assuming that you're performing the low-level communications in software (or that your hardware allows you to deal directly with the incoming signal)....", I meant, "If you're not using a UART but are instead controlling the data link yourself". To be fair, actually, it's unlikely that Neil's system (in which he uses the PIC UART to talk to Holtek transmitter/receiver chips) will ever have ANY errors over the PIC-to-Holtek-chip link. It's much more likely that the Holtek -to-Holtek link will have problems, and error-correcting codes WILL help there. > Anyway, I do kinda remember that the 7,3 hamming code trick is > pretty slick... assuming I'm actually remembering the right thing... > can be implemented as a 128 nibble lookup table for receive? The Hamming code I was suggesting can be implemented quickly and easily with no lookup table at all. If decoding speed is important, you can write a really fast decoder using only an eight-byte table. -Andy Andrew Warren - RemoveMEfastfwdTakeThisOuTix.netcom.com Fast Forward Engineering, Vista, California http://www.geocities.com/SiliconValley/2499

{Quote hidden}>Guys: > >Error-correcting codes actually work BETTER with this sort of error. >Assuming that you're performing the low-level communications in >software (or that your hardware allows you to deal directly with the >incoming signal), you'll have three possibilities for each bit: > > 1. Correct reception, > 2. A binary error (in which a "1" bit is incorrectly read as a > "0" or vice-versa, or > 3. An "erased" bit (in which you read neither a 0 nor a 1). > >While a simple (7,4) Hamming code like the one I proposed can >correct only one "type-2" error per 7-bit codeword, it can correct >TWO "type-3" errors. > >The reason for this somewhat-unintuitive behavior is that the >error-correcting code normally has to do two jobs: It has to both >FIND the error and CORRECT it. If your errors are of the "erasure" >variety, the "FIND" half of its job is already done. > >If Neil used a (7,4) Hamming code and interleaved the bits of his 8 >code words, he'd be able to properly reconstruct his data even if >28% of his transmission were wiped out by burst noise. > >-Andy Andy, The logical question I have is what if only the extra data correction code itself is corrupted? Does this result in an "correction" to perfectly good data? Does not the integrity of the system rely on the extra codes not being corrupted themselves? Inherently, there is no real safe guard against this and it seems to me, by sending more bits you are inviting more errors. How does it all work? I know it must make some sort of sense so what am I missing? Forgive my *absolute* ignorance, but late at night, I have laid awake pondering this. Jim

Newfound Electronics <EraseMEPICLISTMITVMA.MIT.EDU> wrote: > The logical question I have is what if only the extra data > correction code itself is corrupted? Does this result in an > "correction" to perfectly good data? No. > Does not the integrity of the system rely on the extra codes not > being corrupted themselves? No. > Inherently, there is no real safe guard against this and it seems > to me, by sending more bits you are inviting more errors. No. > How does it all work? I know it must make some sort of sense so what > am I missing? What you're missing is the Hamming-code information that I'm going to write and put on my company's web page... I'll get to it sometime this afternoon. It'll be in the "Other Processors/Miscellaneous" section of the "Answers" page. -Andy Andrew Warren - RemoveMEfastfwdEraseMEEraseMEix.netcom.com Fast Forward Engineering, Vista, California http://www.geocities.com/SiliconValley/2499