Saturday, January 5, 2013

Towards Bayesian Morse Decoder


I had an email exchange with Alex, VE3NEA who is the author of the popular CW Skimmer software. Since CW Skimmer is well known for its ability to decode Morse code even in tough pile-up, noise and contest situations I was asking Alex for any advice how to improve FLDIGI CW decoder functionality. In his response Alex stated that he had worked on the problem for 8 years and tried hundreds of algorithms before he got the first version of the software that worked the way he wanted.

 Alex said: "The best advice I can give you is to try to approach every problem in the Bayesian framework. Express all your prior knowledge in the form of probabilities, and use observed data to update those probabilities. For example, instead of making a hard decision at every input sample whether the signal is present or not, compute the probability that the signal is present. At a later stage you will combine that probability with other probabilities using the Bayes formula and pass the new probabilities to the subsequent stages, all the way to the word recognition unit."

Since this was written by a man who really knows how to make great Morse decoder software I started digging deeper in what this Bayesian Framework is all about. I needed to freshen up my memories about probability theory as it has been some 30+ years since I studied this at the university. Perhaps the most clear and concrete examples on conditional probabilities and how to use Bayesian Rule I found from this University of Michigan Open Textbook.

Quick Bayesian Primer 

Before applying Bayesian Rule for FLDIGI Morse decoder we need to define some terms first. In the context of Morse code we are dealing with temporal elements like 'dits' and 'dahs' and time between them - these are the short and long audio pulses that Morse code characters consists of when we listen CW on ham bands. Morse decoder would have to break signals into these basic elements to figure out what character was just received. The elements and timing rules are well explained in this Wikipedia article.

Bayes' theorem is named for Thomas Bayes (1701–1761), who first suggested using the theorem to update beliefs.  To illustrate  the Bayes Rule in ham radio context I created a simple picture below in figure 1.  I collected some 'dits' and 'dahs' as well as inter-element gaps in between  from noisy Morse code signals and used histogram to plot the distribution of the timing of these.  The horizontal axis is in milliseconds and vertical is number of occurrences captured in this session.  On the right side we see two peaks - at 60 milliseconds and at 180 milliseconds.  These corresponds to 'dit'  (60 ms) and  'dah' (180 ms). On the negative side I also plotted the inter-character gap  - peak is at 60 milliseconds as expected and number of occurrences is roughly double as expected.

Fig 1.  Bayes Rule used in Morse Code decoder




To really make use of the Bayesian Framework we need to collect these numbers to make the probability calculations on the elements. I took existing CW.CXX as basis and completely re-wrote the lower level state machine that does the heavy lifting in dealing with the above timing rules. My focus was to enable collection of these timing elements -- both signals and gaps in between. I also added some code to build statistics on these elements while the decoder is running.

I called the new state machine "edge_recorder()" and it is responsible for detecting KEY DOWN / KEY UP edges and capturing 'dit','dah' and inter-character gap durations into a timecode buffer. It also keeps statistics of these durations in a histogram for Bayesian analysis of the Morse code. GNU Scientific Library (GSL) has well documented libraries for histograms so I used GSL Histogram package.


Bayesian Classifier 

I was struggling when writing the classifier software. Baysian Rule P(dit|x) =  P(x|dit)*P(dit) / P(x) basically requires you to compute the probability of 'dit' given observed element "x" - this probability could then be passed to the next stage for character classification. The following diagram helped me to formulate how to approach this.  We get a continuous stream of numbers representing possible 'dits' and 'dahs'.  We need to calculate first a conditional probability of  P(x |dit)  - like the shaded intersection in figure 2.


Fig 2. Conditional Probability















We need to define what 'dit'  really means.   In my case I set the limits so that 'dit' duration can be anything between  0.5 *  DIT  and  2 * DIT   where DIT is the expected duration based on the speed of the received   Morse code.  For example  at 20 WPM  (words per minute)  DIT would correspond to T = 1200/WPM so 1200/20 = 60 milliseconds.   Therefore in my classifier any received element "x" between  30 msec to 120 msec would be classified as 'dit'.  To calculate the probability P(x|dit)  I need to just look up from histogram values from all the bins between 30 and 120 and divide their total by the sum of  bin values from 0 to 300.  That gives us the conditional probability of  P(x|dit).  Same logic applies for 'dahs'.  In my classifier any element "x" bigger or equal to 2 * DIT and smaller than 4 * DIT is considered a 'dah'.

Obviously if the Morse speed changes you need to collect a new histogram and re-calculate the probabilities.  We have still couple additional items to deal with before we can apply Bayes rule.  P(x) is the overall probability of  element "x"  across all occurrences.  I limited this duration between  2*DIT and 4*DIT to remove outliers and impact due to noise.  We can calculate P(x) from histogram like we did above.  The final missing piece is  P(dit).   Based on my limited observations  P(dit) and P(dah)  have roughly equal probabilies in normal (English) ham Morse traffic so I gave them value  0.5.    Now we can use the Bayes formula to calculate P(dit|x) =  P(x|dit)*P(dit) / P(x).  In the software I calculate probabilities P(dit|x) and P(dah|x)  and pass these values to the next stage which does character matching.

To illustrate the value of this approach please look at the following figure 3.  This is a plot of the demodulated noisy signal coming from FFT filtering.  It is hard even for humans to decide whether the characters below match with "I N E T"  or "I R E A"  or "Z N U" or something else.  Humans have amazing capability to build beliefs  and updating these beliefs based on observations.    We are trying to emulate this human behavior.  Bayesian rule is frequently used in machine learning systems.

Figure 3.  Noisy Morse code








Character Classifier 

Next step was to build a Morse character classifier that uses the probabilities coming from the previous stage as described above.  To simplify the problem I created a simple codebook table that encodes the 'dit' and 'dah' probabilities of each character.  Now I just need to multiply incoming number vector representing 'dit'/'dah' probabilities against each codebook entry and then find the best match.



//  26 ASCII 7bit letters
{'A', "A", {{1,0},{0,1},{0,0},{0,0},{0,0},{0,0},{0,0}}},
{'B', "B", {{0,1},{1,0},{1,0},{1,0},{0,0},{0,0},{0,0}}},
{'C', "C", {{0,1},{1,0},{0,1},{1,0},{0,0},{0,0},{0,0}}},
{'D', "D", {{0,1},{1,0},{1,0},{0,0},{0,0},{0,0},{0,0}}},
{'E', "E", {{1,0},{0,0},{0,0},{0,0},{0,0},{0,0},{0,0}}},
{'F', "F", {{1,0},{1,0},{0,1},{1,0},{0,0},{0,0},{0,0}}},
{'G', "G", {{0,1},{0,1},{1,0},{0,0},{0,0},{0,0},{0,0}}},
        .......


Above is a small section of the codebook. Each character has a set of two numbers  - (1,0) means probability of  dit is 100%  and dah is 0%.   Character "E" that has a single 'dit'  has this in the first column.  This way we can represent the characters as a sequence of probabilities  of various 'dit' / 'dah' patterns.

We could also apply the Bayes  Rule at this level if we collect additional data on character statistics. For  example if we have statistics on the usage frequency of each character we could use that as an additional parameter to multiply the calculated probability coming from the character matching algorithm. This would just require additional frequency histogram, some code to pre-populate this based on selected language and perhaps code to update histogram when we are using the FLDIGI program. I have not implemented these yet.

Word Classifier 

The last stage would be the word classifier.   As we calculate the probabilities of each character in the previous stage  we could send these probabilities upstream to the word classifier.   There are a commonly used phrases, acronyms and ham radio jargon that could be used as a corpus  to match against received characters.

For example if  we receive BALAN  where the possible 4th letter in order of probabilities are  A = 0.2345, U = 0.2340, V=0.1234,  R=0.10235   we could use Bayes Rule to figure out probability of  BALUN  vs. BALAN  and emit the most probably word.   Similarly we could use a database of contest ham stations  and try to match probabilities of received characters to most probably station call sign using Bayes Rule.   This is yet another area that would be nice to implement in the future.

Conclusions 

I want to thank  Alex VE3NEA  for opening a whole new avenue of learning about Mr. Bayes and his ideas.   Based on my initial results the Bayesian Framework provides new rich data on how to model and improve the performance of the FLDIGI Morse Decoder.

The new software I created produces a ton of useful data to analyze  what is really happening under extremely noisy  conditions and also helps to separate different problems like  signal processing & filtering, signal power detection, signal edge detection, classification of  'dits' and 'dahs'  and finally  also character and word classification.

I have a alpha quality version of  Bayesian classifier  coded for FLDIGI  v.3.21.64 and I will work with Dave W1HKJ and any volunteers  to use these ideas to improve FLDIGI Morse decoder even further.

You can leave comments here or  you can also find me from linuxham Yahoo mailing list or from http://eham.net


73
Mauri  AG1LE






Tuesday, January 1, 2013

Morse Decoder SNR vs CER Testing

FLDIGI Morse Decoder  CER vs SNR Testing

Summary 

I wanted to get more factual data on how different FLDIGI  CW options influence the character error rate (CER)  at different signal-to-noise ratios (SNR).  In this test I focused on comparing SOM decoder to legacy decoder option and Matched Filter to  FFT filter option. I also tested a few cases where I used ~ 2x wider FFT filter  (68 Hz  vs. 35 Hz bandwidth).  Otherwise I used the default options of FLDIGI.

Based on the test results below the following appears to be true:
  • Adjusting FFT filter bandwidth has much bigger impact on CER than changing between legacy and SOM decoder. 
  • Matched filter automatically sets the filter bandwidth to optimal for given CW speed. 
  • SOM decoder gives about 5% better CER compared to legacy decoder @ -13dB SNR, but this advantage gets smaller as SNR decreases. 
The test results are summarized in the figure 1 below. With 3 kHz wide audio signals you can get near perfect copy (CER below 0.02) at  SNR  -10 dB  using  Matched filter or setting FFT filter at 34 Hz  corresponding to 20 WPM Morse speed.

Fig 1.  FLDIGI  Morse Code decoder CER vs. SNR





Test Cases and Setup


My goals for this this experiment were to
  • Compare FLDIGI legacy  vs. SOM decoder CER at different SNR levels. 
  • Compare  FLDIGI Matched Filter  vs.  FFT filter (bandwidth set to 35Hz)  CER  at different SNR levels. 
  • Compare CER with  FFT filter bandwith  set to 68 Hz  vs.  35 Hz.

I used the following software versions to conduct this test:
First  I generated a test audio file with 20 WPM Morse code using WinMorse and converted it to 16 bit  8 Khz Mono Wav file using Audacity.  I played the audio file with PathSim  configured for AWGN S/N Test simulation.  Both AWGN Noise source and "Input Source" have 3 kHZ band pass filter after them as demonstrated in the figure below.

Fig 2. PathSim Configuration





















Sound output from PathSim  (8 kHz 16 Bit Mono) was connected to  FLDIGI  input using Virtual Audio cable  and level was adjusted at 10 in Windows 7 volume mixer so that FLDIGI waterfall is not saturated.  Audio signal had 3 Khz bandwidth as verified on FLDIGI  waterfall display.

Audio file length was 11 min 27 seconds.  PathSim "RunTime" was adjusted to 11 minutes - this provided only 869  of 904 total character in the file.  The lack of last 27+ seconds creates a systematic error of 35 missing characters causing baseline error of CER 0.03871 -  this is already subtracted from results below.

I changed audio SNR  in PathSim in steps from -20 dB, -15 dB, -14dB, -13 dB,  -10 dB and 0 dB also did a reference test case without any injected noise. I compared FLDIGI decoded characters against sent characters using RTTY Text Comparison tool by Alex VE3NEA.  As FLDIGI sometimes emitted prosigns (like <AR> ) I edited these to a single  '*' character before entering to 'received' field in the RTTY Text Comparison tool. Note that this tool was designed for RTTY characters so BER numbers are not applicable for Morse code as RTTY has fixed bit length baudot code whereas Morse code bit length  varies by character. The character error rate (CER)  is still be applicable.

I plotted the following measured CER results against SNR values with Graph.

Test Results 

Reference case 
No noise    CER 0.0011     First character incorrectly coded 

Test cases 
SNR            CER      Test
  0 db          0.00001   SOM Decoder with FFT Filter @68 Hz

-10 dB         0.01219   Legacy decoder  with Matched Filter @35 Hz
-10 dB         0.01439   SOM decoder    with Matched Filter @35 Hz
-10 dB         0.01439   Legacy decoder with FFT Filter @35 Hz
-10 dB         0.00999   SOM Decoder with FFT Filter @35 Hz
-10 db          0.20799   SOM Decoder with FFT Filter @68 Hz

-13 dB         0.19469   Legacy decoder  with Matched Filter @35 Hz
-13 dB         0.18589   SOM decoder    with Matched Filter @35 Hz
-13 dB         0.16149   Legacy decoder with FFT Filter @35 Hz
-13 dB         0.15379   SOM Decoder with FFT Filter @35 Hz
-13 db          0.66479   SOM Decoder with FFT Filter @68 Hz


-14 dB         0.37499   Legacy decoder  with Matched Filter @35 Hz
-14 dB         0.35729   SOM decoder    with Matched Filter @35 Hz
-14 dB         0.30199   Legacy decoder with FFT Filter @35 Hz
-14 dB         0.30089   SOM Decoder with FFT Filter @35 Hz

-15 dB         0.50669   Legacy decoder  with Matched Filter @35 Hz
-15 dB         0.49779   SOM decoder    with Matched Filter @35 Hz
-15 dB         0.47899   Legacy decoder  with FFT Filter @35 Hz
-15 dB         0.46569   SOM Decoder   with FFT Filter @35 Hz
-15 db          0.71789   SOM Decoder with FFT Filter @68 Hz

-20 dB         0.74229   Legacy decoder  with Matched Filter @35 Hz
-20 dB         0.68479   SOM decoder    with Matched Filter @35 Hz
-20 dB         0.72569   Legacy decoder with FFT Filter @35 Hz
-20 dB         0.68029   SOM Decoder with FFT Filter @35 Hz
-20 db          0.75439   SOM Decoder with FFT Filter @68 Hz

Other Observations on FLDIGI Performance

At low SNR values (-20 dB) FLDIGI seemed to lose CW speed tracking, especially if Matched filter was used.  The RxWPM display showed received speed variation between 23 and 30 WPM  while sent signal was at steady 20 WPM.   This may explain some of the decoding errors.  In real life cases if you know the Morse speed it is probably better to set it manually when trying to decode very noisy signals.


73
Mauri  AG1LE





Popular Posts