ad: dxeng

Forward Error Correction

Discussion in 'Ham Radio Discussions' started by KX4Z, Jul 11, 2019.

ad: L-HROutlet
ad: l-rl
ad: Left-2
ad: Subscribe
ad: L-MFJ
ad: MessiPaoloni-1
  1. KV6O

    KV6O Ham Member QRZ Page

    Is that your best effort?
     
    AG6QR likes this.
  2. N8OHU

    N8OHU Ham Member QRZ Page

    Nope, since the compression in question is well documented and open source.
     
  3. K0IDT

    K0IDT Ham Member QRZ Page

    Perennial question, where's the decoder for any of it?
     
  4. KX4Z

    KX4Z Ham Member QRZ Page

    Decoder? For what?
    if you're talking about pactor -- the decoder is available off the shelf in products made and sold freely just like ham radios, cell phones, and automobiles are. The manufacturer has even volunteered to come up with a software decoder, something that wasn't technologically feasible (without a Cray!) a few years back.

    There's even a volunteer group that GIVES away software to utilize the manufacturer's product! Amazing. But there are lots of generous people in ham radio today.

    If you're talking about LZHUF.....well, the software is public domain and available on github and a zillion other places. Google-fu is your friend! A teenager with a raspberry pi could gin it up for you -- or you could yourself, I'm sure. The idea is inside your computer with your unzipping abilities, and probably in your cell phone, for listening to music or compressing data... The initial technique of the compression was done in 1949...and then improved upon by a college student for a college paper in 1951. Then a couple of other guys improved it further in the 80's, and it became available to just about everyone over 30 years ago.
     
  5. K2CAJ

    K2CAJ XML Subscriber QRZ Page

    Any percentage of overhead may occur, if the channel is noisy enough.

    For simple channels, we have a number called the (Shannon) channel capacity. It tells you the number of bits of information that can be reliably communicated for each channel use. This number doesn't depend on any particular FEC or other method---it's the theoretical limit regardless of how you try to send.

    For example, if every transmitted bit has a P probability of being destroyed, and the receiver can tell which bits were destroyed, the capacity is 1-P bits per transmitted bit. In that case if every bit has a 50% chance of being blocked, and the blocking is obvious, optimal FEC will give you 100% overhead.

    On the other hand, if every bit has a P probability of being flipped, and the receiver can't tell which bits were flipped, then the capacity is 1-H(P), or 1+(p)log(p)+(1-p)log(1-p), with the logs taken in base 2. In that case if every bit has a 50% chance of being unknowingly flipped, then the capacity is 0, and it is theoretically impossible to send any information on the channel, with any error correction at all!

    Also, to answer your earlier question: while it's impossible to absolutely guarantee transmission (there might be a chipmunk in the transceiver), Shannon proved that we can always find an FEC method that gets arbitrarily close to the capacity, with an arbitrarily small probability of error. So if the capacity is 0.877 bits per channel use, you can demand a one-in-a-billion chance of a bit error and a data rate of 0.8765, and someone can produce an FEC method that achieves that.
     
  6. K0IDT

    K0IDT Ham Member QRZ Page

    Gordon, can you ever answer a question without all the deflection and obscuration? It's a simple question, where's the over the air decoder for any of the modes as used by Winlink today?
     
  7. KX4Z

    KX4Z Ham Member QRZ Page

    As to Shannon's proof.... what were the assumptions?
    We always have to ask that in medicine. If you don't allow people with XYZ into a clinical trial....then how do you know the medicine works on XYZ?
    Answer: you don't.

    I'm not an expert on Shannon's Theorem (http://www.cs.cmu.edu/~aarti/Class/10704/lec16-shannonnoisythrm.pdf ) but I suspect it is based on a stationary system (time-invariant). (It also presumes that you KNOW the probability of the signal corruption....how do you know that without having some form of acknowledgement coming back???) Our problem in real communications is that we have an incredibly TIME-VARYING channel, so in order to approximate a stationary system, we have to increase the time interval of inspection to enormous lengths -- like 30 minutes or so. Then the error rate can be better modeled. There will be time periods where the probability of reception is 0.000 In other words, the signal disappears below the quantized detector. And with no acknowledgement/request system....you will have to design for the WORST.

    My suspicion (you could prove it right or wrong) is that in order to handle a l o o o n g period of completely absent signal, which is quite possible and randomly located within the time of message throughput -- you would end up having to inject SUCH AN INCREDIBLE OVERHEAD that you make the system non-useful. And you will always have to use that...because you don't have any acknowledge/request informaiton to measure the CURRENT channel.

    In other words -- if you refuse to do the simple thing that ham radio operators have done for scores ofyears, "Hey, chap, I missed that last part, could you repeat it?" (ARQ)....then in order to guarantee success to a useful degree of accuracy -- sufficient to reduce your liability for non-trivial purposes -- then you may end up with an overhead of 1000% or even larger.....when it would be much simpler -- and more efficient -- to ask for a repeat. that may be why NO ONE previously in this thread argued that FEC alone would suffice, and you also agree that you can APPROACH various things.

    So the real queston is a proof of real world experience that convinces normal SSB and CW operators (and winlink, and wireless manufacturers of all sorts) that they have been doing it incorrectly all these years -- -that asking for repeats and fills is the wrong way to go about it -- and that with sufficient overhead, you can ALWAYS get the message through. Sometimes the information to be transmitted is NON TRIVIAL. And there are consequences if it gets through improperly, or doesn't get through at all.

    I hope I explained that sufficiently. I suspect you could build a time-varying FEC system....but in order to be time varying, it would basically have to do ARQ....or it would never know that it needs to CHANGE the overhead due to a changing noise channel.

    Believe me, I've watched digital systems try awfully hard to move data through a very noisy channel many, many times. If you added enough overhead to deal with the sudden arrival of a QRM station....etc etc etc.... I believe an ordinary 30 second message would take an hour to get through....and if you have NO arq system built in....you would always have to use the most enormous overhead possible, because you wouldn't have the necessary measurement of the channel to start with, would you?

    And of course I could be wrong. The manufacturers of wifi systems could all be wrong. A bunch of manufacturers could ALL be wrong. There may be a way to build a FEC system...without any acknowledgment at all, ever....that can beat all these systems out there which have been so prosperous by using FEC *and* ARQ. if so, you can pick up your patent, and your Nobel and retire a very very wealthy man!!!

    Cheers,
    Gordon
     
  8. K0RGR

    K0RGR XML Subscriber QRZ Page

    A lot of us ARES types use NBEMS (Narrow Band Emergency Messaging System). This is a suite of applications added on to the FLDIGI program.

    One of those is FLMSG, which does a checksum on the entire message. On the receiving end, if the message checksum doesn't agree with the received message, the message is not verified. FEC depends on which protocol you choose to send the message. Olivia 8/500 is pretty bulletproof due to it's aggressive FEC. The message will get through under very adverse conditions.

    Another interesting tool is FLAMP, which works like the 'Radio Mirror' developed by the folks at US Packet. The idea is for one station to send PC files via NVIS to multiple receiving stations. The file is broken into short segments, each of which has a checksum. On the receiving end, if a segment is not received correctly, the receiving stations can take turns requesting fills for the specific segments they missed. The receiving stations will keep requesting fills until the entire file is correctly received. FLAMP can also do it's own virtual FEC by sending the file repeatedly how ever many times you specify.
     
  9. KX4Z

    KX4Z Ham Member QRZ Page

    Wow, when you ask a question, you manage to get specific on the 2nd try, huh? So why are you asking? You already know the answer. The decoder for massive over the air decoding of the modes such as used in winlink today was not built by the people who said it absolutely had to be done, or the security of all americans was at risk. [but maybe the government has one? gee....if they thought it was IMPORTANT they would have done it, right? -- or they would have shut this all down years and years ago, right? ]

    I have no idea why the civilians who said it was so incredibly important.... didn't build it. It makes no sense to me. We have conclusively proven that it COULD have been built. In fact, it is obvious to those skilled in the art that it could have been built, and you have had the chance to read that from them. So you know also that it could have been built. At least one person had all the resources -- but didn't do it.

    The $64,000 question is WHY didn't they do it? Gee...I don't know. Do you?

    In the meantime, the same information is now available on a web viewer. So maybe the rest of the world now realizes
    (a) the people who said it had to be done, didn't do it.
    (b) the people who said it didn't need to be done, presented an alterntive that satisfies the majority of the people.

    And they've gone on to other things? I dunno. But I had a ton of fun and learned a LOT in the process -- and I've conclusively proven that it could have been done.

    Cheers!
    Gordon
     
  10. KX4Z

    KX4Z Ham Member QRZ Page

    Thanks! I see that you agree that some sort of fill or acknowledgement or repeat is generally utilized....or you simply may end up with no message. I think most people understand that. Different systems get their acknowledgements differnt ways. In amateur radio contensts, the other side says "R" or "QSL" or "I copy" or something like that. I have never seen anyone in a contest switch to pure FEC --- sending their contest information with huge huge overhead so the receiving station might increase their probability of reception to 99.999999% --- and then refuse to observe whether or not the other station actually received it or not, just go ahead and log them.... does that fly in contests these days?
     

Share This Page