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:
##############################################################################
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.
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.
-- 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
