Binary Tree Morse Decoder

7,832

99

22

Introduction: Binary Tree Morse Decoder

About: 55+ years in electronics, computers, and teaching ... now retired.

This instructable explains how to decode Morse Code using an Arduino Uno R3.

The decoder, which automatically adjusts to the send speed, is capable of decoding morse up to at least 80 words per minute.

The incoming code is displayed as text on your Arduino Serial Monitor (or TFT screen if fitted)

A tone oscillator has been included should you wish to practice sending morse.

The decoder features:

  • a 320 x 240 TFT display module [1]
  • a Goertzel digital bandpass filter for separating unwanted signals.
  • a “Binary Morse Tree” for decoding the signal
  • auto-speed tracking
  • an audible output when practicing morse
  • both incoming and outgoing text are displayed.

The following characters and symbols are recognised:

  • [A..Z]
  • [0..9]
  • [. , ? ' ! / ( ) & : ; = + - _ " @]

The estimated cost of the morse decoder shield, less the TFT display, is $25. [1]

Images

  • The cover photo shows a fully assembled unit
  • The video shows the decoder working

Notes

[1]

Step 1: Parts List

The following parts were obtained from https://www.aliexpress.com/

    • 1 only prototype shield for Arduino UNO R3, 2.54mm Pitch

    The following parts were obtained locally:

    • 1 only LM358 dual opamp
    • 1 only LED green
    • 1 only LED clip
    • 1 only electret microphone capsule
    • 1 only normally-open push-button
    • 1 only 8-pin DIP socket
    • 2 only 330 ohm resistors
    • 2 only 2K2 resistors
    • 5 only 10K ohm resistors
    • 2 only 56K ohm resistors
    • 2 only 1uF capacitor
    • 1 only 10uF capacitor

    The following parts are optional:

    • 1 only 2.2 Inch TFT SPI LCD Display Module 240*320 ILI9341 with SD Card Slot for Arduino Raspberry Pi 51/AVR/STM32/ARM/PIC [1]
    • Morse key / push-button
    • 1 only BC548 NPN transistor
    • 1 only 1 inch speaker
    • 1 only 33K ohm resistor
    • 1 only 3.5mm mono plug (for morse key)
    • 1 only 3.5mm mono socket (for morse key)
    • 3 only 9mm M3 tapped nylon spacers
    • 1 only 130 x 68 x 44mm ABS plastic box
    • 5 only 2-pin right-angle connectors

    The estimated cost of the morse decoder shield, less the optional TFT display, is $25. [1]

    Notes

    [1]

    The parts list for the optional 320 x 240 TFT display module is listed in my instructable https://www.instructables.com/id/Arduino-TFT-Grap...

    [2]

    A morse key or sturdy push-button is required if you wish to use the sender.

    Step 2: Circuit Diagram

    Images

    • Photo 1shows the circuit diagram for the morse decoder. The 330 ohm resistor in series with the morse key limits the D4 output current in the event of an accidental short to ground ... increasing its value decreases the audio output from the speaker. For this reason I have not added it to the shield but attached it directly to the morse-key jack for ease of adjustment.
    • Photo 3 shows the completed shield attached to an Arduino. No other components are required if the text is to be viewed on your Arduino “Serial Monitor”.
    • Photo 4 shows the decoder partially boxed. A hole has been cut in the lid for viewing the display. The speaker and microphone have been hot-glued to the case. Drill some speaker-holes in the lid before mounting the speaker. The center socket on the lid is for an extension microphone ... without this the decoder must be placed close to the speaker which is not always possible.
    • Photo 5 shows the TFT screen. Black electrical tape has been attached to the display edges ... this tape prevents light leakage and masks any misalignment between the display and the opening in the lid.

    Important

    [1]

    Arduinos with a large USB connector require a layer of electrical tape between the USB connector and the Arduino shield. Accidental shorts are possible without the tape as the clearance is small. The tape is not required for Arduinos that have small connectors.

    Step 3: Theory

    Each morse code letter comprises a series of short and long duration tones called “dots” and “dashes”.

    • a dot (.) is 1 unit in length
    • a dash (_) is 3 units in length
    • the space between letter elements is 1 unit
    • the space between letters is 3 units
    • the space between words is 7 units

    We can determine whether the incoming tone is dot or a dash by comparing its duration with a reference tone of 2 units in length.

    • a dot is less than 2 units
    • a dash is greater than 2 units

    There are two distinctly different methods for decoding the incoming pattern of dots and dashes:

    • linear search
    • binary tree (also known as a dichotomic search)

    Linear Search

    One common method is to create an array of characters and their matching morse patterns. For example each of the following characters would be saved as:

    • A . _
    • B _ . . .
    • C _ . _ .
    • 0 _ _ _ _ _
    • 1 . _ _ _ _
    • 2 . . _ _ _

    Each letter requires 6 cells ... 1 for the letter itself and 5 for the (.)’s and (_)’s. In order to do this we need a letters[36][6] character array with a total of 216 cells. Unused cells are normally filled with a zero or a blank.

    To decode the incoming dots and dashes we must compare the dot/dash pattern of each incoming letter with our reference character patterns.

    While this method works, it is extremely slow.

    Say we have 26 letters (‘A’, ..’ Z’) and the digits (‘0’, ... ‘9’) stored in an array, then we must perform 36 searches, each with up to 5 sub-searches, which is a total of 36*5=180 searches to decode the numeral ‘9’.

    Binary Tree

    A binary search is far quicker as no searches are required.

    Unlike the linear search, which requires both the character and the morse patterns to be stored, the binary tree only stores the characters which means that the array size is smaller.

    I have split my binary tree (photo1) into two halves (photos 2 and 3) to make it more readable.

    To find a character we move a pointer left each time we hear a dot and move the pointer right every time we hear a dash. After each move we halve the pointer distance for the next move ... hence the name binary tree.

    To decode the letter ‘9’ ( dash, dash, dash, dash, dot) requires 5 moves ... 4 to the right, and 1 to the left which leaves the pointer directly over the ‘9’.

    Five moves is significantly faster than 180 searches !!!!!

    The binary character array is also smaller ... 26 letters and 10 numerals only requires a 64 x 1 line array. I’ve chosen to create a 128 character array so that I can decode punctuation.

    Step 4: Design Notes

    Morse is difficult to decode in the presence of interfering signals. The unwanted signals must be rejected ... this requires some sort of filter.

    There are many possibilities:

    1. Phase-locked loops
    2. Inductor-capacitor filters
    3. Resistor-capacitor active filters
    4. Digital signal processing such as Fast Fourier Transform, or the Goertzel filter.

    Methods 1,2,3 require external components which are bulky.

    Method 4 requires no external components ... the frequencies are detected using mathematical algorithms.

    Fast Fourier Transform (FFT)

    One method of detecting the presence of a tone in a complex waveform is to use the Fast Fourier Transform

    Photo 1 shows how FFT (Fast Fourier Transform) divides the audio spectrum into “bins”.

    Photo 2 shows how the FFT “bins” respond to a signal ... in this case 800Hz. If a second signal of say 1500Hz was present we would see two responses ... one at 800Hz and another at 1500Hz.

    In theory a morse code decoder can be be made by monitoring the output level of a particular FFT frequency bin ... a large number represents the presence of a dot or dash ... a small number represents no signal.

    Such a morse code decoder could be made by monitoring “bin 6” in photo 2 but there are a number of things wrong with this approach:

    • we only want one frequency bin ... the rest are wasted calculations
    • the frequency bins may not appear exactly on the frequency of interest
    • it’s relatively slow (20mS per Arduino loop()

    Another method is to use a Goertzel filter.

    Goertzel Filter

    The Goertzel filter is similar to FFT but only has a single frequency bin.

    Photo3 shows the frequency response of a Goertzel filter to discrete audio steps.

    Photo 4 is a sweep of the same filter over the same frequency range.

    I decided to “go” with the Goertzel algorithm as:

    • The Arduino loop() time using the Goertzel algorithm was 14mS (milliseconds) versus 20mS (milliseconds) for an FFT solution using the Arduino “fix_FFT” library.
    • It is easy to set the center frequency of a Goertzel bandpass filter.
    • The bandwidth is approximately 190Hz.

    Photo 5 shows the numeric output from a 900Hz Goertzel filter when a tone is detected. I have set my tone threshold to a value of 4000 ... values above 4000 indicate a tone.

    In theory you just need to tune your filter to a comfortable listening frequency. Unfortunately the audio output from my 1 inch monitoring speaker drops rapidly below 900Hz. To avoid any issues I’m using a filter frequency of 950Hz. The necessary formulas for calculating alternate filter frequencies are found in my code header.

    Decoding

    Decoding the dots and dashes is not as easy as it first looks.

    Perfect morse is defined as:

    • dot = 1 unit
    • spaces inside letter = 1 unit
    • dash = 3 units
    • space between letters = 3 units
    • space between words = 7 units

    To decode perfect morse we simply need a reference tone duration of 2 units

    • dot < 2 units
    • element space < 2 units
    • dash > 2 units
    • letter _space > 2 units
    • word_space > 6 units (i.e 3 x reference units)

    This works for machine morse but in the “real world” :

    • the sending speed varies
    • the duration of each dots varies
    • the duration of each dash varies
    • the letters E,I,S,H,5 only contain dots which average to the dot duration
    • the letters T,M,O,0 only contain dashes which average to the dash duration
    • word gaps may not arrive
    • fading creates errors from which the decoder must recover.
    • corrupt signals due to interference

    Letters containing only dots and dashes is partially solved if:

    • we estimate the reference duration until we have received a valid dot and a valid dash. I use 200 milliseconds which is valid if the send speed is between 6 WPM (words per minute) and 17 WPM. You may need to increase this value if you are learning morse. A speed table is included in the software.

    Speed variations are solved if:

    • we perform a rolling average on each dot and each dash and
    • recalculate the reference duration after each symbol is received

    Word gaps and word gaps not arriving are solved if we:

    • remember the time of the last trailing-edge (tone to no-tone) transition,
    • restart the algorithm after each letter,
    • calculate the elapsed time while waiting for the next leading-edge (no-tone to tone) transition and
    • insert a space if 6 time units have been exceeded.

    Morse Oscillator

    I initially tried some Piezo buzzers but found:

    • the frequency was fixed
    • the output frequency was too high for prolonged listening
    • the piezos tended to drift out of the Goertzel passband

    I then tried driving an acoustic transducer with a 750Hz squarewave but found it had a resonance that filtered out the 1st and 3rd harmonics. Photo 6 shows the microphone amplifier output to a 750Hz square-wave ... we are seeing the 5th harmonic !!!

    I then resorted to a using a small speaker. Photo 7 shows the microphone output to a 750Hz squarewave that was sent to a small speaker ... this time we are seeing the fundamental ... not the 5th harmonic. The Goertzel filter ignores any harmonics.

    Notes

    [1]

    https://en.wikipedia.org/wiki/Goertzel_algorithm

    https://www.embedded.com/the-goertzel-algorithm/

    Step 5: Software

    Installation

    • Download the attached file MorseCodeDecoder.ino [1]
    • Copy the contents of this file to a new Arduino sketch
    • Save the sketch as "MorseCodeDecoder" (without the quotes)
    • Compile and upload the sketch to your Arduino

    Software Update
    23 July 2020

    The following features have been added to the attached file "MorseCodeDecoder6.ino"

    • an "Exact Blackman" window [2]
    • a "Noise_blanker"

    Adjustment:

    • increase your receiver audio level until the LED starts to flicker then back off
    • now tune your receiver until the LED flashes in step with the the incoming morse
    • the Noise_blanker has been set to ignore noise bursts up to 8mS (one loop time)
    • the Noise threshold can be adjusted by setting Debug=true and watching your Serial Plotter

    Note

    [1]

    Set your Arduino Serial Monitor to 115200 bauds if you wish too view the text.

    [2]

    • Photo 1 ... Exact Blackman window
    • Photo 2 ... Goertzel filter without Exact Blackman window
    • Photo 3 ,,, Goertzel filter with Exact Blackman window applied

    Step 6: Operation

    Decoder

    Place the unit next to your speaker when listening to morse.

    • The electret microphone capsule picks up the morse signal from your speaker.
    • The output of the electret microphone is then amplified 647 times (56dB) before being passed to the Arduino for processing.
    • A Goertzel digital bandpass filter extracts the morse signal from the noise.
    • Decoding is done using a binary tree.
    • The decoder output is displayed as text on a 320 x 240 pixel TFT display. It is also sent to your Arduino “Serial Monitor” if you don’t wish to use a display.

    Morse Sender

    A morse sender has also been included. This allows you to practice sending morse and works as follows:

    • A constant audible tone is generated on Arduino pin 4.
    • We hear this tone via the decoder’s loud-speaker whenever we press the morse-key.
    • The tone is set to the same frequency as the Goertzel filter which fools the decoder into thinking its listening to real morse ... whatever you send will appear as printed text on the display.

    Your sending will improve as the decoder picks up common errors such as:

    • too much space between symbols. (example: Q pinted as MA)
    • too much space beween letters (example: NOW printed as NO W)
    • incorrect code

    Step 7: Summary

    Decoder

    This instructable describes how to make a morse decoder that converts morse code to printed text.

    • The decoder is capable of decoding morse up to al least 80 WPM (words per minute)
    • The decoder automatically tracks variations in received send-speed.
    • The text is displayed on your Serial Monitor (or on a 320 x 240 TFT display module if fitted) [1]

    Sender

    A morse sender has also been included

    • The sender helps you improve the quality of your morse sending.
    • The decoder confirms that what you have sent is correct

    Cost of parts

    The estimated cost of the morse decoder shield, less the optional TFT display, is $25.

      Click here   to view my other instructables.

    Audio Challenge 2020

    Second Prize in the
    Audio Challenge 2020

    Be the First to Share

      Recommendations

      • Water Speed Challenge

        Water Speed Challenge
      • Fandom Contest

        Fandom Contest
      • Stone, Concrete, Cement Challenge

        Stone, Concrete, Cement Challenge

      22 Comments

      0
      WilkoL
      WilkoL

      11 months ago

      While busy building a somewhat similar morse-coder and -decoder I found that in your Symbol table there are characters that are not in the ITU list that I used. E.g. you have a black-slash (\). And the quotation marks (") are not in the place where I expected them.
      What morse code did you use in this instructable?

      edit:
      Aaahhh never mind, the backslash (\) is to "escape" the apostrophe (').
      The (") was a mistake from myself and the (!) and (&) are in some morse tables but not in all.

      0
      sp9mrn
      sp9mrn

      12 months ago

      Very elegant solution.
      'cause input filter is relatively wide, a tuning indicator (zero beat) with 3 leds or somwhere at LCD - showing tuning direction, would be nice addition (for using with trx, not only as standalone reader/trainer).
      Really good job.

      0
      lingib
      lingib

      Reply 12 months ago

      Thank you for your comment and suggestion :)

      In practice a tuning indicator is not required as the LED reaches peak brightness when the signal is centered in the filter. Normally this is enough but an exact tune is possible by pressing the morse key and going for a zero-beat ... this works as the the morse tone() is set to the filter center.

      0
      sp9mrn
      sp9mrn

      Reply 12 months ago

      Of course, generally You're absolutely right. But ;-) I thought that:
      1. if people make a zerobeat indicators (2. and If You have a device (and knowlege) which can do it as a cheap & easy addition
      Then
      it could make your construction more popular - not only for learning code but also in everyday ham radio use.
      It was only suggestion, nothing more.
      I'm just starting to copy your decoder. Thank you for nice piece.
      MAc
      mrn

      0
      lingib
      lingib

      Reply 12 months ago

      Unable to view the link (?????) but I actually like your suggestion and will give it some thought.

      It would be dead easy to implement if I was using FFT ... just attach different colored LEDs to the frequency bins either side of center.

      Bit more of a challenge with a Goertzel filter as it only has one bin.

      The change in brightness I referred to is due to the noise blanker starting to detect the signal as you tune up the filter slope ... the LED flashes to full brilliance when text appears.

      One of the reasons for using the Goertzel filter was to get more samples within each dot period ... FFT is much slower and would limit the maximum decode speed. I just went for simplicity.

      0
      sp9mrn
      sp9mrn

      Reply 12 months ago

      oh, my mistake.
      ( there are several films on youtube - search: son of zerobeat )
      Change in brightness - i didn't think about it...

      0
      lingib
      lingib

      Reply 12 months ago

      I think we have been talking at cross-purposes. It appears that Son of Zero Beat is an aid for putting your transmitter onto the received frequency.

      My comment about zero-beat was to center the audio in the filter passband.

      I have an old iCOM-725. To put the TX onto the RX freuency I just turn the RIT off and go for no tone (which is within 10Hz). I then switch the RIT on to get my desired audio frequency.

      The MorseCodeDecoder doesn't require any setting up for practice morse but it does require an RIT on your communication receiver when listening to morse.

      Thanks again for your suggestion ... will give it some thought :)

      0
      we4sel
      we4sel

      1 year ago

      How well does it handle hand-sent code? With very bad ears, and no software yet found that does well with non-machine sent code, i'm stuck with the other digital kb-2-kb modes.

      0
      lingib
      lingib

      Reply 1 year ago

      Extremely well :)

      The software automatically adjusts to your hand speed once it has received both a dot and a dash ... until it has figured out the length of your hand-sent dots and hand-sent dashes it uses 200mS as the reference 2-unit period for decoding which allows it to decode words such as "his" (.... .. ...) which contain nothing but dots.

      I send the letter K (_ . _) when I first switch on. This instantly sets the 2-unit reference to your hand speed.


      0
      we4sel
      we4sel

      Reply 1 year ago

      Much obliged. copying any form of CW coming in ota has been a terror. This or a version of it is now on my list.

      0
      lingib
      lingib

      Reply 12 months ago

      Glad to have been able to help :)

      0
      ANDRELAS
      ANDRELAS

      12 months ago

      This is a very fine addition to. instructables. Did you buy parts from a particular Aliexpress storefront or several? Can you recommend? Thanks.

      1
      waltercf
      waltercf

      1 year ago

      Impressive project and well-documented explanation! I like the thought behind the design. Thank you for posting it.

      0
      lingib
      lingib

      Reply 1 year ago

      You're welcome ... thanks for your comment :)

      1
      MaciejG17
      MaciejG17

      1 year ago

      I don't really care about Morse, but very happy with your explanation about the digital filters, and signal processing vs. real world. Awesome!

      0
      lingib
      lingib

      Reply 1 year ago

      Thank you for your comment :)

      Have since updated the software by adding a noise blanker and an Exact Blackman window.

      Step 5: Software now contains:
      - MorseCodeDecoder 6.ino
      - photo of Exact Blackman window
      - photo of the Goertzel filter response before applying the Exact Blackman window
      - photo of the Goertzel filer response after applying the Exact Blackman window

      1
      Y-Geo
      Y-Geo

      1 year ago

      well done now i can teach my kids morse and they can see their send and not worry about me laughing too much.

      0
      lingib
      lingib

      Reply 1 year ago

      They will enjoy it :)