Hi Steve, Edson, and all,
I'm happy with setting bias = 0.42, given that several quite different
tests show that it results in a rate of false decodes smaller than 1 in
1000.
As for reporting to WSPRnet: my preference is to report all decodes to
the database site. It's not so very unusual for a new callsign to turn
up -- perhaps to be decoded only once, especially if band-hopping is in
use. The occasional long distance paths with unusual propagation can be
especially interesting, even (or especially?) when they are one-off
events. It's relatively easy to and apply further sanitizing of data at
the database site, or elsewhere when any analysis of the data is done.
-- Joe, K1JT
On 8/1/2015 7:33 PM, Steven Franke wrote:
> Hi Joe,
>
>> On Aug 1, 2015, at 1:02 PM, Joe Taylor<j...@princeton.edu> wrote:
>>
>> Hi Steve,
>>
>> Visiting family are arriving later than expected, so I found some
>> unexpected time to play with wsprd and wsprd_exp. To make the KA9Q fano
>> decoder work with your change, I had to increase the size of the node[]
>> structure by one bit:
>
>>
>
> Oops - you are right. Why didn’t I get into trouble? Presumably, there was
> some slack space after the malloc that allowed me to write outside of the
> allocation without clobbering anything?
>
>> ##############################################################################
>>
>> pulsar:~/jtsdk/src/wsjtx/lib/wsprd$ svn diff
>> Index: fano.c
>> ===================================================================
>> --- fano.c (revision 5745)
>> +++ fano.c (working copy)
>> @@ -105,7 +105,7 @@
>> unsigned int lsym;
>> unsigned int i;
>>
>> - if((nodes = (struct node *)malloc(nbits*sizeof(struct node))) == NULL) {
>> + if((nodes = (struct node *)malloc((nbits+1)*sizeof(struct node))) ==
>> NULL) {
>> printf("malloc failed\n");
>> return 0;
>> }
>> @@ -172,7 +172,7 @@
>> }
>> np[1].gamma = ngamma; // Move forward
>> np[1].encstate = np->encstate<< 1;
>> - if(++np == lastnode) {
>> + if(++np == lastnode+1) {
>> break; // Done!
>> }
>> ##############################################################################
>>
>>
>> Here are some new results, which essentially confirm your findings.
>> Both programs (wsprd and wsprd_exp) were compiled with the above changes
>> made to fano.c. Just for fun, I timed each run separately after
>> compilation with clang-3.5 and gcc.
>>
>> Command T B G Time Time
>> clang gcc
>> ---------------------------------------------------------------
>> 1. wsprd 124 0 124 25.1 24.2
>> 2. wsprd_exp 130 7 123 33.7 32.2
>> 3. wsprd_exp -J -C 5000 125 3 122 33.1 32.3
>> 4. wsprd_exp -z 0.46 122 0 122 34.8 33.3
>> 5. wsprd_exp -z 0.46 -J -C 5000 122 0 122 33.8 33.5
>> 6. wsprd_exp -z 0.5 120 0 120 34.6 33.3
>> 7. wsprd_exp -z 0.5 -J -C 5000 119 0 119 34.0 33.1
>>
>> T = total decodes
>> B = bad decodes
>> G = good decodes
>>
>> Some history concerning fano.c may be informative. Phil Karn's code had
>>
>> tail =&nodes[nbits-33];
>>
>> where we now have
>>
>> tail =&nodes[nbits-31];
>>
>> I made this change a long time ago, for reasons that seemed right to me
>> at the time. Probably I should also have changed the "Done" condition
>> as you have now done.
>>
>> Why did I need to increase the memory allocation for nodes, while you
>> did not? Possibly the whole thing is not quite right, yet, though your
>> test on the final metric seems to indicate that it's OK.
>
> I think that it’s working correctly now. At least, it is visiting the same
> nodes and coming up with the same path metrics as Jelinek. And the Jelinek
> algorithm is so simple that I’m pretty sure that it’s doing the right thing.
>
> I find the fano.c book-keeping approach confusing (though it makes sense from
> an efficiency/execution time point of view). Specifically, in fano.c each
> node entry stores an encoder state that includes up to the i’th bit, but it
> stores the metric only up through the previous (i-1)th bit.
>
> This quirk is why we need to malloc space for one extra node, because the
> final metric (for the 81-bit long frame) is actually stored in the 82nd entry
> of the node[] struct array...
>
> Jelinek works differently - because it never backtracks, it can efficiently
> store the i’th bit and the metric up through the i’th bit in the same node.
>
>>
>>
>> One more thing escapes me at the moment. Why does case 2 give different
>> results from case 1? They both use the corrected fano decoder with
>> maxcycles=10000 and bias=0.42.
>
> wsprd_exp uses a different sync algorithm - basically a nested-grid approach
> in an attempt to improve the efficiency of the sync search. It also tries to
> refine the drift estimate. This means that the candidate symbol vectors that
> are submitted to the decoder are somewhat different in wsprd and wsprd_exp.
> Up until I saw your files I was convinced that wsprd_exp was the superior
> sync algorithm. Now, not so much.
>
> I’m happy with how fano.c is behaving now. I intend to make the
> malloc/lastnode changes unless I hear otherwise.
>
> Perhaps we should turn attention to the philosophical question of where to
> set the bias. I ran some simulations to study how bias affects the
> probability of decode and probability of bad decode under controlled
> conditions.
>
> First I ran tests using wsprsim-generated files with -31 dB snr to test the
> effect of the change in the fano decoder. For each simulation run I generated
> and decoded 10000 .c2 files. Since all simulated files have the message “K9AN
> EN50 33”, it was easy to find and count all frames with errors, not just the
> ones with a forward slash. Here are the results:
>
> wsprd (original fano.c, bias=0.42)
> 5599 decodes, 25 bad decodes (13 bad with “/“), in 1750s (total of 5574 good
> decodes, 55.7%)
>
> wsprd (modified fano.c, bias=0.42)
> 5578 decodes, 17 bad decodes (4 bad with “/“), in 2225s (total of 5571 good
> decodes, 55.7%)
>
> This shows that decoding the 81st zero decreased the probability of a bad
> frame by 33% while having a negligible affect on the probability of
> successfully decoding a frame.
>
> If, in addition, we raise the bias to 0.46:
>
> wsprd (modified fano.c, bias=0.46)
> 4690 decodes, 8 bad decodes (1 bad with “/“), in 2510s
>
> And with bias=0.50 wsprd (modified fano.c)
> 4174 decodes, 3 bad decodes (1 bad with “/“), in 2669s
>
> In raising the bias from 0.42 to 0.46 we lose more than 900 good decodes just
> to suppress 9 bad decodes, a 100:1 ratio. From 0.42 to 0.50 we lose more than
> 1400 to suppress 14 bad ones - still 100:1. Personally, I don’t like to give
> away so many good decodes.
>
> This brings me back to Edson’s suggestion… Why not run with low bias and just
> use Edson’s mechanism to filter what gets sent to wsprnet.org?
>
> Steve k9an
>
>
>>
>> -- Joe
>>
>> On 7/31/2015 11:45 PM, Steven Franke wrote:
>>> Joe,
>>>
>>>> On these files I ran test cases like yours, plus two more, with the
>>>> following results:
>>>>
>>>> Command T B G time
>>>> -----------------------------------------------------------
>>>> 1. wsprd 125 2 123 25 s
>>>> 2. wsprd_exp 126 13 113 29
>>>> 3. wsprd_exp -J -C 5000 115 3 112 30
>>>> 4. wsprd_exp -J -C 5000 -z 0.5 112 0 112 30
>>>> 5. wsprd_exp -z 0.5 113 1 112 30
>>>> 6. wsprd5000 120 0 120 23
>>>> 7. wsprd -z 0.5 119 0 119 26
>>>>
>>>> T = total decodes
>>>> B = bad decodes
>>>> G = good decodes
>>>>
>>>> Case #6 used a re-compiled wsprd with maxcycles=5000.
>>>>
>>>> On these files, at least, it seems that the best performer is the
>>>> deafult wsprd, Case #1: 123 good decodes, 2 false decodes. With
>>>> maxcycles=5000 (Case #6) it yields 120 good decodes and 0 false decodes.
>>>> With bias=0.5 (Case #7) it gives 119 good decodes and 0 false decodes.
>>>>
>>>> Seems to me we should probably go back to bias=0.5, and possibly reduce
>>>> maxcycles a bit.
>>>
>>> I’m on the same page regarding the need to decrease the number of
>>> bit-errors in the decoded frames. But the thing that has been bothering me
>>> the most is the vastly different results from Fano and Jelinek when
>>> presented with the same candidates. All of my background reading suggests
>>> that these two algorithms should visit the same nodes, given enough cycles.
>>> And yet, I was unable to get Jelinek to produce the same bad decodes, even
>>> when I allowed a huge number of cycles and a huge stack size. So I’ve been
>>> suspicious about a programming error or bug.
>>>
>>> I think that I’ve found at least a partial explanation for the bad behavior
>>> of Fano. I’ve concluded that fano.c, as configured, is not decoding all 31
>>> tail bits. It is stopping at 30 bits. I discovered this after printing out
>>> the final metric for decoded frames. I noticed that on a clean high-snr
>>> test file, as generated by wsprsim, the final metric for a Fano decode was
>>> 800, whereas it is 810 for Jelinek. Similarly all of the final metrics
>>> produced by Fano were smaller than those produced by Jelinek.
>>>
>>> The following change makes the high-snr final metric 810 for Fano, and in
>>> fact makes all final metrics from Fano and Jelinek identical:
>>>
>>> $ svn diff
>>> Index: wsprd/fano.c
>>> ===================================================================
>>> --- wsprd/fano.c (revision 5740)
>>> +++ wsprd/fano.c (working copy)
>>> @@ -172,7 +172,7 @@
>>> }
>>> np[1].gamma = ngamma; // Move forward
>>> np[1].encstate = np->encstate<< 1;
>>> - if(++np == lastnode) {
>>> + if(++np == lastnode+1) {
>>> break; // Done!
>>> }
>>>
>>>
>>> With this change, the results for cases 1 and 2 improve to:
>>> 1.wsprd 124 0 124
>>> 2. wsprd_exp 130 7 123 (compare to your case 2 — it is counter to my
>>> intuition that we get more good decodes by decoding further into the tail)
>>>
>>> Also, I got different results for your case 3. This shouldn’t be affected
>>> by the fano.c change, so I wonder if you just mis-copied the numbers on
>>> this one:
>>>
>>> 3. wsprd_exp -JC 5000 125 3 122
>>>
>>> Finally, note that a metric bias of 0.46 eliminates bad decodes with either
>>> decoder in wsprd_exp (using the modified fano.c):
>>> wsprd_exp -z 0.46 122 (0) in 19s
>>> wsprd_exp -Jz 0.46 -C 5000 122 (0) in 19s
>>>
>>> So - at this point I am inclined to make the change to fano.c so that we
>>> decode all 31 tail zeros (provided that you agree with my interpretation of
>>> what’s going on). I’m also inclined to raise the default bias in wsprd to
>>> at least 0.46. Or even 0.5 if you prefer, though this may be less necessary
>>> with the fano fix.
>>>
>>> I also like Edson’s idea. I think that his suggestion could be a win-win by
>>> essentially eliminating bad decodes in the database and allowing us to run
>>> a little closer to the ragged edge in terms of what is displayed locally. I
>>> imagine that spots that are not in ALL_WSPR and therefore are not
>>> uploadable could be displayed in a different color to make it clear that
>>> they are only for local consumption.
>>>
>>> Steve k9an
>>>
>>>>
>>>> -- Joe
>>>>
>>>> ------------------------------------------------------------------------------
>>>> _______________________________________________
>>>> wsjt-devel mailing list
>>>> wsjt-devel@lists.sourceforge.net
>>>> https://lists.sourceforge.net/lists/listinfo/wsjt-devel
>>>
>>>
>>> ------------------------------------------------------------------------------
>>> _______________________________________________
>>> wsjt-devel mailing list
>>> wsjt-devel@lists.sourceforge.net
>>> https://lists.sourceforge.net/lists/listinfo/wsjt-devel
>>
>> ------------------------------------------------------------------------------
>> _______________________________________________
>> wsjt-devel mailing list
>> wsjt-devel@lists.sourceforge.net
>> https://lists.sourceforge.net/lists/listinfo/wsjt-devel
>
>
> ------------------------------------------------------------------------------
> _______________________________________________
> wsjt-devel mailing list
> wsjt-devel@lists.sourceforge.net
> https://lists.sourceforge.net/lists/listinfo/wsjt-devel
------------------------------------------------------------------------------
_______________________________________________
wsjt-devel mailing list
wsjt-devel@lists.sourceforge.net
https://lists.sourceforge.net/lists/listinfo/wsjt-devel
