On 8/9/21 02:39, William Smith wrote:
Personally I want my stuff to be _able_ to operate independently of
the Internet, though I'm happy to have it around for normal operation,
and to detect (for a recent instance) things like my external GPS
antenna on my local Pi4-based NTP server failing.
Right. I feel the same way about repeater linking. It's fun to link ham
repeaters over the Internet, but if we're at all serious about the
EmComm aspect of ham radio we should at least be aware of how dependent
we are on it. One of my absolute favorite Prof. Andrew Tannenbaum
quotes: "Distributed computing is when a computer you didn't even
realize you were using is keeping you from getting any work done."
Would it make any sense to try the decoding over several settings for
the decoding limit, or is that too meta?
No. A Fano decoder explores (part of) a binary tree representing all
possible messages. WSPR messages are 50 bits so there are 2^50 possible
messages -- many more than you could ever fully explore even with
today's computers, so it can only search a small subset of paths through
the tree. It starts at the root (the beginning of the message) and,
using the noisy received symbols, chooses which branch -- message bit 0
or 1 -- looks like the "better" one. It continues down that branch,
decoding additional bits, as long as it seems to be on the right path.
But if it has made a wrong turn, neither choice will match what it's
getting; nothing will "make sense". So it backs up and explores down
another path. If that doesn't work, it backs up even more and repeats
the process.
When things go well (the SNR is high) it rarely if ever makes a wrong
turn, so it zips right through. The average number of decoder "moves"
per decoded bit is 1 or only slightly more. But when the signal is
noisy, it will spend a lot of time running into dead ends, repeatedly
backing out and exploring alternate paths. If the signal is *very*
noisy, it may never make it through before it exceeds some preset limit
on how many total moves are allowed. That's the decoding limit you set
at the start. If you try several times with successively higher decoding
limits, you're just wasting the CPU time you spent on the earlier
aborted attempts. You might as well just pick a large decoding limit to
start with.
If you're concerned about spending too much CPU time in a difficult
decode and holding up other messages that may decode more easily, the
answer here is to run each decoder in its own thread and let the
operating system handle the scheduling. You'll still want to set a limit
on the decoding effort just to avoid false decodes.
Sequential decoding (of which the Fano and stack algorithms are two
versions) is very much like solving a Sudoku puzzle. With the easy
puzzles it is always fairly obvious what number goes next in what
square, and you rarely find yourself in a dead end that requires you to
back up, erase earlier guess(es) and try others. The really hard puzzles
are designed to make you do that a lot. (Personally, solving Sudoku
puzzles by hand seemed awfully tedious, so I wrote a program to solve
them using basically this same algorithm. Works in milliseconds even on
the "monster" puzzles. My wife thinks that's cheating. "Why? I had to
think hard about how I'd solve *every* Sudoku puzzle ever created, or
will be created, not just the one in front of me. How is that cheating?")
Or is it actually time spent running over the dataset, and there's no
way to tell how 'well' the decode worked? Obviously, getting a result
sooner rather than later gives you a better 'quality metric' (or
whatever it would be called), so is it worth keeping the data and this
score and using a running average of the score to set your threshold?
[Or am I, more likely, talking through my hat and just muddying the
waters?]
No, these are all very reasonable questions. 'wsprd' includes all this
information in its output files, though they don't seem terribly well
documented. Look at the log file ALL_WSPR.txt. The second-to-last column
is the average number of decoder cycles per bit (truncated down to an
integer; ideally it would be shown as a float) and the last column is
the 'path metric'.
The 'path metric' is a measure of how closely the noisy received symbols
match what they should be for the decoded message. I.e., it's a measure
of how confident the decoder is in its result. During decoding, the
decoder uses the path metric up to that point to decide its next move;
it keeps moving forward as long as the metric is improving. If it keeps
getting worse it'll back up and try another path until it improves
again. (I wrote this code so long ago I can't even remember if a "good"
metric is positive or negative!)
Path metrics can be very tricky with sequential decoding, as it
implicitly compares paths of different lengths and this requires
accurate estimates of the signal and (especially) noise levels -- which
is basically what you're trying to figure out! I haven't dug too deeply
into the code yet but I suspect that the SNR values we see from wsprd
are actually computed from the synchronization sequences, not the Fano
decoder metrics.
One of the main reasons that sequential decoding fell out of favor when
Viterbi discovered his algorithm was that the Viterbi algorithm only
compares paths of equal lengths. This makes the Viterbi algorithm much
less sensitive to errors in the SNR estimate, especially when "soft
decision decoding" is used. wsprd is one of a relative few applications
of sequential decoding that uses soft decision decoding. Most sequential
decoding applications I found in the literature seemed to just punt.
They use it in a "hard decision" mode, which loses about 2 dB in SNR
performance.
Viterbi also runs at a constant speed no matter how noisy the input
stream may be. But Viterbi is limited to short constraint lengths (less
coding gain) and it will gladly decode garbage from pure noise, so you
need another layer of FEC to correct or at least detect uncorrected
errors from the Viterbi decoder. This is usually done by "concatenating"
a Reed Solomon block code on top of Viterbi. This was developed for the
Voyager spacecraft, where it stood as the state of the art until the
discovery of turbo coding in the early 1990s and the rediscovery of LDPC
a little later. Both the Voyager concatenated code and the sequentially
decoded convolutional code used in wspr require about the same per-bit
SNR, about 2.5 - 3 dB.
Phil
_______________________________________________
wsjt-devel mailing list
[email protected]
https://lists.sourceforge.net/lists/listinfo/wsjt-devel
