Sunday, May 20, 2012

Morse Code decoding with Self Organizing Maps


Continuing the series of articles on the Morse code decoding using Self Organizing Maps (SOM)  I am covering some new experiments with SOM based learning.

Using the experimental version of FLDIGI setup explained in my previous blog entry  I collected a dataset of  dit/dah durations from the following decoded text:

"<AS>CWDEWFHKJW1HKJW1HKJPSEMCQCQCQDEW1HKJW1HKJW1HKJCQCQCQDEW1HKJW1HKJW1HKJPSEKCQCQCQDEWFHKJW1HNJW1HKJCQCQCQDEW1HKJW1HKJW1HKJPSEKCQCQCQDEW1HKJW1HKJW1HKJCQCQCQDEW1HKJW1HKJW1HNJPSEKCQCQCQDEW1HKJW1HKJW1HKJCQCQCQDEW1HKJW1HKJW1HKJPSEKCQCQCQDEW1HKJW1HKJW1HKJCQCQCQDEW1HKJW1HKJW"  

I used the SOM toolbox to create a 7 x 7 SOM  and learn the 14 different morse characters in the text above based  purely on the dit/dah timing information.  Each morse character is vector with 7 numbers  (6 for dit/dah durations in milliseconds and 7th number as terminating zero).  Here is an example of the data:



56  160 156   0   0 0 0 W
68  162 176 152 154 0 0 1
58   60  66  46   0 0 0 H
174  64 156   0   0 0 0 K
44  154 160 146   0 0 0 J


Once the 7 x 7  rectangular SOM was created and automatic learning process was completed I created a few visualizations to look at the data.  

VISUALIZATIONS 

 Figure 1 below shows a hit histogram in colors and numbers.  For example top left corner node has 26 hits from input vectors matching letter "Q".  SOM was also able to cluster the  learned characters automatically.  Dark lines between nodes depict the clusters that were created by Ward's linkage feature of the SOM toolbox.   


Figure 1.  SOM - hit histogram and clusters


























The next visualization in Figure 2 below  is a SOM nearest neighbourhood graphThe method defines graphs resulting from nearest neighbor- and radius-based distance calculations in the data space, and shows projections of these graph structures on the map. You can observe how relations between the data are preserved by the projection, yielding interesting insights into the topology of the mapping, and helping to identify outliers. 


For example you can see that letters  Q (dah-dah-dit-dah),  M  (dah-dah) and D (dah-dit-dit)  are neighbours and  connected via a graph projected with red line on the SOM map below.  The line segment D <-> M  is quite long indicating a topology violation. You can also see that different variations of H, K, J, W, C are nearest neighbours. 


The original signal contained a lot of noise which was causing jitter on the dit/dah duration, and sometimes even errors.  However,  SOM was able to learn from this dataset the Morse characters having similar patterns. 


Figure 2. SOM Neighbourhood graph k-nn



























Another visualization technique is U-matrix in figure 3 below. U-matrix colors the nodes with the average distance of that unit to other adjacent units. The blueish colors represent close distance whereas red colors represent long distance. The SOM network appears to have clustered the morse characters in distinctive groups. You can compare how U-matrix and  clusters (depicted by black lines) are aligned.  



Figure 3. SOM U-matrix visualization


























CONCLUSIONS 

Self Organizing Maps  is a powerful  method to visualize multidimensional data as it preserves topological properties of the input data.  In this example we used a set of Morse code patterns as training data. Each Morse code consists of  a "dit/dah"  pattern representing tone duration in milliseconds.  The original data was collected from noisy audio files using  FLDIGI  that had experimental matched filter and SOM decoder features enabled.


The author has done similar testing last year with a much larger dataset collected from actual CW contacts recorded in multiple RF bands (7 Mhz, 14 Mhz and 18 Mhz bands)  from multiple stations with different CW styles.  The dataset contained almost  40,000 characters  covering QSOs,  rag chewing, bulletins, and other types of CW communication.   Testing was performed with 20 x 20, 10x 10 and 7 x7 sized SOMs.


SOM was able to cluster similar Morse code patterns together despite noise and jitter on the original data.  We also demonstrated that automatic clustering and character classification would be feasible using the features available in the SOM toolbox.

Looking at the weight vectors created by this automatic learning process they resemble very much the SOM codebook that the author created for the SOM decoder function for FLDIGI software.  Using the  codebook entry for each cluster (see the letters Q,M, H, E, S, D, J, P, W, K, C, 1 in figure 3) and Best Matching Unit (BMU) algorithm would classify the incoming data vector correctly despite some noise and jitter.

There are still multiple unresolved problems in error free automatic detection and decoding of Morse code.  As the signal-to-noise ratio decreases the noise and jitter  makes it more difficult to produce accurate timing information.  Also, some CW stations don't comply with  dit / dah timing standards which creates more variability in the data.  Self Organizing Maps is one approach to tackle these problems  and based on preliminary testing it shows a lot of potential for further improvements.

73
Mauri AG1LE






















2 comments:

  1. Have you considered using digram/trigram frequencies to help guide or disambiguate decoding when several different candidate matches are nearly equiprobable?

    ReplyDelete
  2. Hi Tom

    I have not thought about using digrams or trigrams.

    I did consider creating a dictionary of most commonly used words and acronyms to improve decoding. There is a discussion thread that has some commonly used QSO word lists in here .

    Do you know any other existing digram/trigram material that would be useful in this context? Real life CW QSOs contain many digrams and trigrams so this might be a good strategy to match different candidates if the underlying character matching layer (BMU algorithm) returns higher than usual error value.

    Thanks for the suggestion!

    73 Mauri AG1LE

    ReplyDelete

Popular Posts