On 2011-03-28, ChrisQ <meru@devnull.com> wrote:> Simon Clubley wrote: >> >> The Phase IV documents can be found at: >> >> http://linux-decnet.sourceforge.net/docs/doc_index.html >> >> I don't know what the current status of the DECnet code in Linux is however >> as I never use it. >> > > A dec document describing the low level protocol, crc, retries and > states etc can be found at: > > http://decnet.ipv7.net/docs/dundas/aa-d599a-tc.pdf >I'll have a read through it thanks; it's been a long time since I really did anything with DECnet Phase IV.> I had a previous life working with dec kit and thought I recognised the > name, perhaps from the vms group, but were you by any chance a > contractor in the mid to late 80's ?... >No, but late 80s/early 90s was the start of my career and I was writing code for the PDP-11 before moving onto VAX then Alpha and taking in a range of other environments along the way. It's quite possible you ran across me as part of that, especially if you attended the annual DECUS conferences. Simon. -- Simon Clubley, clubley@remove_me.eisner.decus.org-Earth.UFP Microsoft: Bringing you 1980s technology to a 21st century world
error detection rate with crc-16 CCITT
Started by ●March 27, 2011
Reply by ●March 28, 20112011-03-28
Reply by ●March 29, 20112011-03-29
On Mar 28, 5:48=A0pm, Shane williams <shane.2471...@gmail.com> wrote:> On Mar 28, 6:54=A0pm, "robertwess...@yahoo.com" > > > > > > <robertwess...@yahoo.com> wrote: > > On Mar 27, 5:31=A0pm, Shane williams <shane.2471...@gmail.com> wrote: > > > > Interesting points, thanks. =A0The environment can be just about > > > anything. =A0I suspect we'll back off the baud rate fairly quickly on=ce> > > errors start occurring. =A0I'm also thinking we could raise the secur=ity> > > for some of the critical messages, like double transmissions perhaps. > > > Use a proper forward error correction scheme. =A0You'll be able to > > monitor the increase in error rate while still getting most packets > > through. =A0A Reed-Solomon code will allow you to (for example) add 20 > > bytes to a 235 byte message and correct any 10 bad bytes (and all > > detect all bad messages with no more than 19 bad bytes). =A0If you're > > getting a bit corrected every few dozen packets, it's probably safe to > > bump up the data rate. =A0If it's a couple dozen bits in every packet, > > it's time to back off. =A0In fact, this can substantially increase your > > effective data rate, as you can continue to run in the presence of a > > moderate number of errors (disk drives, for instance, run well into > > that region, and it's relatively rare these days that *any* sector > > actually reads "clean," and a very heavy duty ECC code is used to > > compensate). > > > You can also improve things by using a multi level scheme, which could > > be a simple duplication (think disk RAID-1), or some combined code > > over multiple packets (simply parity like RAID-5, or Reed-Solomon-ish > > like RAID-6), which would provide added recovery, at the expense of > > added latency (mainly in the presence of errors). =A0Since you mentione=d> > that you have at least two classes of data (critical and nice to > > have), apply the second level of FEC to just the critical data (after > > protecting each packet with an appropriate RS code), and even a > > substantial spike in error rate, you're likely to get the critical > > stuff through. > > Thanks. =A0Error correction sounds like it would be too CPU intensive. > I'd be happy just to detect errors. > > Do you have any idea how many bytes we would have to add to a 60 byte > message to detect 19 bad bytes or less and how CPU intensive it is?To detect (but not correct) all errors of 152 (19*8) or fewer, you'd have to add at least 152 bits of check code. If you're only looking to detect errors occurring in no more than 19 bytes of the message, it would be a bit less, but not hugely so. Remember that to detect n bits of error, the block has to be different enough from any other valid block that errors in n bit do not make it look like a different valid block. If you're asking about a RS code as I described above, the short message really doesn't buy you anything, since you need about twice the number of bits worth of RS symbols as the number of error bits you hope to correct. RS is moderately computationally intensive, but that clearly depends on your data rates, and that hardware you're running on. In fact it has a worse reputation that it really deserves. But to toss some numbers out there, a decent implementation in C, on a 1GHz x86, for a RS(255, 239) encoding (239 bytes of data, plus 16 bytes of check code, or a bit weaker than what was discussed above =96 that=92s a commonly used code in broadcasting, so is well studied and you should be able to find plenty of benchmarks and samples and whatnot), should come in at 100-200Mb/s for encoding (or 10K-20K cycles per block), about half that for decoding blocks without errors, and about a fifth the encoding rate for decoding blocks with the maximum correctable amounts of error. Shorter blocks require less work to process, but it's sub- linear, so your net data rate for a fixed CPU load will go down as block size decreases. And note that 255 bytes is the longest possible block for RS with 8 bit symbols. On something like an ARM 9, quadruple the cycle counts.
Reply by ●March 29, 20112011-03-29
Shane williams wrote:> On Mar 29, 4:04 am, Vladimir Vassilevsky <nos...@nowhere.com> wrote: > >>Shane williams wrote: >> >>>On Mar 28, 6:51 am, Tim Wescott <t...@seemywebsite.com> wrote: >> >>>Switching rates seems fairly easy to me. One end tells the other what >>>rate they're switching to, the other acknowledges, if no ack then >>>retry a couple of times. If one end switches and the other doesn't, >>>after one second or so of no communication, they both switch back to >>>the slowest rate. >> >>Some people are just looking to find trouble for their ass. Perhaps, >>they are masochists; they like to be fucked. Good luck with that; there >>are almost limitless possibilities for the protocol malfunctioning. >> > > > Can you describe just one possibility?For starters: for the efficient operation, the transmit and the receive chains should be buffered. In order to change the rate, you have to make sure the buffers are flushed. If you are planning switching the rate back and forth, that would incur significant penalty in efficiency. VLV
Reply by ●March 29, 20112011-03-29
On Mar 29, 6:03=A0pm, Vladimir Vassilevsky <nos...@nowhere.com> wrote:> > For starters: for the efficient operation, the transmit and the receive > chains should be buffered. In order to change the rate, you have to make > sure the buffers are flushed. If you are planning switching the rate > back and forth, that would incur significant penalty in efficiency.The hardware handles the sending of a whole message at a time. The software gives the hardware a whole message to send and gets told when a whole message has been received. This is done by an interrupt routine. The interrupt routine will decide when to switch baud rates or check when the other end is asking to switch so the only penalty is a couple of extra messages and a short delay if the switch works. If the switch doesn't work there's a slightly bigger penalty but we won't be switching often enough for it to matter.
Reply by ●March 29, 20112011-03-29
On Mon, 28 Mar 2011 10:04:29 -0500, Vladimir Vassilevsky <nospam@nowhere.com> wrote:> > >Shane williams wrote: >> On Mar 28, 6:51 am, Tim Wescott <t...@seemywebsite.com> wrote: >> >>>On 03/27/2011 07:21 AM, Vladimir Vassilevsky wrote: >>> >>> >>> >>> >>>>Shane williams wrote: >>> >>>>>Thanks. I'm trying to figure out whether it's possible/ viable to >>>>>dynamically determine the fastest baud rate we can use by checking the >>>>>error rate. >>> >>>>Yes. But: >>> >>>>1) It is easier, faster and more reliable to evaluate the channel by >>>>transmitting a known pseudo-random test pattern rather then the actual >>>>data. >>> >>>I've done this -- and it is. >>> >>> >>>>2) If the baud rate is changed dynamically, how would the receivers know >>>>the baud rate of the transmitters? >>> >>>There's ways. Any good embedded programmer should be able to figure out >>>half a dozen before they even put pen to napkin. >>> >>> >>>>3) Since the system is intended to be operable even at the lowest baud, >>>>why not always use the lowest baud? >>> >>>If it's like ones that I've worked with, the data over the link is a >>>combination of high-priority "gotta haves" like operational data, and >>>lower-priority "dang this would be nice" things like diagnostics, faster >>>status updates, and that sort of thing. >>> >>>So the advantages of going up in speed are obvious. For that matter, >>>there may be advantages to being able to tell the a maintenance guy what >>>not-quite-fast-enough speed can be achieved, so he can make an informed >>>choice about what faults to look for. >>> >> >> >> Didn't think about that. >> >> You're exactly right about the need for speed. Background data is >> fine at the slower rate but when an operator is doing something on the >> system we want the response to be faster than the slowest rate gives >> us. >> >> Switching rates seems fairly easy to me. One end tells the other what >> rate they're switching to, the other acknowledges, if no ack then >> retry a couple of times. If one end switches and the other doesn't, >> after one second or so of no communication, they both switch back to >> the slowest rate. > >Some people are just looking to find trouble for their ass. Perhaps, >they are masochists; they like to be fucked. Good luck with that; there >are almost limitless possibilities for the protocol malfunctioning.In the CAN environment (at least when using some sensible controllers like SJA1000 listen only mode) autobauding is trivial. Adding some Modbus RTU slaves to some existing RS-485 Modbus network only requires listening for the traffic for a second or two.
Reply by ●March 29, 20112011-03-29
On Tue, 29 Mar 2011 00:03:01 -0500, Vladimir Vassilevsky <nospam@nowhere.com> wrote:>For starters: for the efficient operation, the transmit and the receive >chains should be buffered.Most industrial protocols (like Modbus) are simple half duplex request/response systems. At any significant line rates, the troughput is severely limited by the line turn-around delays at both ends. The additional delay (due to autobauding) at new device insertion should not be a significant issue.
Reply by ●March 29, 20112011-03-29
Shane williams <shane.2471958@gmail.com> wrote:>Packet length is max 270 bytes / 2700 bits or so but critical messages >are more like about 50 bytes / 500 bits.As someone else has previously noted you can get CRC performance data from this paper: http://www.ece.cmu.edu/~koopman/roses/dsn04/koopman04_crc_poly_embedded.pdf You are interested in CRC CCITT-16 x^16 + x^12 + x^5 + 1 At 2700 or fewer bits you get Hamming Distance of 4 which means detects all 1, 2, & 3 bit errors but not all 4 bit errors. Because of the factorization of this polynomial it also detects all odd numbers of bit errrors, but at the price that all even numbers of bit errors are twice as likely to escape detection (roughly 1 - 2^-15 probability of detection). It also detects any burst error that corrupts any combination of 16 or fewer bits in a row, assuming you get endian-ness and order of the CRC right. At 500 bits the properties are pretty much the same. To clarify an earlier discussion point, the number of errors you are guaranteed to detect depends on the polynomial and the message length. So you can't just say any particular polynomial detects all x-number of bit errors without giving a maximum length. In the case of CCITT-16 you you get this performance (HD=4) up to 32751 data bits (not counting CRC bits) and after that it only detects odd number of bit errors (2-bit errors will be undetected if they are more than about 32 K bits apart). -- Phil Koopman http://betterembsw.blogspot.com/ Phil Koopman -- koopman@cmu.edu -- http://www.ece.cmu.edu/~koopman
Reply by ●March 29, 20112011-03-29
upsidedown@downunder.com wrote:> In the CAN environment (at least when using some sensible controllers > like SJA1000 listen only mode) autobauding is trivial.The whole point of using CAN is the hardware arbitration and collision avoidance of the bus. This won't work with autobauding. Vladimir Vassilevsky DSP and Mixed Signal Design Consultant http://www.abvolt.com
Reply by ●March 29, 20112011-03-29
Shane williams wrote:> On Mar 29, 6:03 pm, Vladimir Vassilevsky <nos...@nowhere.com> wrote: > >>For starters: for the efficient operation, the transmit and the receive >>chains should be buffered. In order to change the rate, you have to make >>sure the buffers are flushed. If you are planning switching the rate >>back and forth, that would incur significant penalty in efficiency. > > The hardware handles the sending of a whole message at a time. The > software gives the hardware a whole message to send and gets told when > a whole message has been received. This is done by an interrupt > routine. The interrupt routine will decide when to switch baud rates > or check when the other end is asking to switch so the only penalty is > a couple of extra messages and a short delay if the switch works. If > the switch doesn't work there's a slightly bigger penalty but we won't > be switching often enough for it to matter.* Having protocol logic in the Tx/Rx ISRs is a bad idea already. * How a hub type device would work? * What if a node somehow missed the correct baud rate, receiving garbage and responding to it? * How would you verify, troubleshoot and prove the operation? VLV
Reply by ●March 29, 20112011-03-29
On Tue, 29 Mar 2011 08:15:17 -0500, Vladimir Vassilevsky <nospam@nowhere.com> wrote:> > >upsidedown@downunder.com wrote: > > >> In the CAN environment (at least when using some sensible controllers >> like SJA1000 listen only mode) autobauding is trivial. > >The whole point of using CAN is the hardware arbitration and collision >avoidance of the bus. This won't work with autobauding.CAN bus standard does not include any autobauding feature. However, SJA1000 style controllers can be put into listen mode (in which case it does not disrupt the network traffic, if a CRC error is detected). A new autobauding CAN slave can listen for the bus traffic at various speeds, until it receives messages without CRC errors and hence concludes that the correct speed has been found. In any serial line protocol with CRC, this can be used by slaves for autobaud detection.