Simple melody recognition based on a microcontroller
If the individual notes can be sine waves or square waves then you should be able to pin-point each part of the signal as a musical note. I say this because if the signal is a rich blend of many instruments then deciding what is the melody becomes a nightmare. 

You then need to look up what the frequencies are and recognize that in music, one semitone (even-tempered) is approximately 1.0595 higher in frequency than the note below i.e. if one note is 440 Hz then the note immediately above is 466.2Hz.

This can help you provide a noise-gap so you can recognize when a note actually changes.

This all goes wrong when someone is playing violin because of the notes gliding between notes. Ditto on a fret-less bass or trombone.

Good luck - it sounds difficult.