Re: [wsjt-devel] wsprd Fano Decoder Optimizations

[Tolboom, Ryan via wsjt-devel]

Hello,

Thank you very much for taking an in-depth look at it. I really appreciate
it. If I were to change my patch, I'd probably change the type from
unsigned to uint32_t as after doing a bit more reading I see the int size
isn't the same for different architectures. That being said, your testing
has confirmed that it doesn't really seem to make any difference (even
possibly increasing the decode time!).

I also found it interesting that the OSD is doing so much work. I'll have
to dig into how that works.

Thanks for putting these tools out there in the open source world so people
can learn how they work. It's really quite enlightening.

-Ryan N2BP

On Sat, May 4, 2024 at 2:23 PM Franke, Steven J 
wrote:

> Ryan, Thanks for your suggestions. Your observation of a 0. 6% change
> seems to be down in the noise, i. e. comparable to changes that you would
> expect to see from run to run even without any code changes. I tried your
> patch here on MacOS and
> 
> Ryan,
>
> Thanks for your suggestions. Your observation of a 0.6% change seems to be
> down in the noise, i.e. comparable to changes that you would expect to see
> from run to run even without any code changes. I tried your patch here on
> MacOS and the results showed that the patch doesn’t provide any significant
> change in execution time. On 3 consecutive runs I saw original->patched
> execution time changes of -1.0%, +0.1%, and +2.4% in 3 successive runs. The
> average change was an increase of 0.5%.
>
> BTW, I noticed that your test script calls the wspr decoder using the
> default value for the timeout value (1 decoder cycles per bit). This
> default value is not recommended as it will produce an unacceptably high
> false decode rate while providing little, if any, improvement in good
> decodes compared to more reasonable values.  You will see much better
> results if you call the decoder with the following command-line options:
>  “-C 500 -o 4 -d”.
>
> For example, using your test.sh
> <https://urldefense.com/v3/__http://test.sh__;!!DLa72PTfQgg!O9j2nBBJFUjnWvGOTnCIKX8BwyEvabwnQMu2rXDVulMlOjHdeaFu1bOufMPwi5od3SpxStGBil1HWxT7I2jchc4oUA$>
> script as-is I saw 63 good decodes out of 100 attempts and the total
> execution time was around 40 seconds on my Mac laptop. Using the
> command-line options “-C 500 -o 4 -d” I saw 87 good decodes and the
> execution time was about 9 seconds, less than 1/4 of the time that it took
> using the default settings.  It’s also worth noting that with my suggested
> settings, the decoding time is dominated by time spent in the Ordered
> Statistics Decoder (OSD). The time spent in the Fano decoder is almost
> negligible (0.63 seconds).
>
> Steve k9an
>
> On May 3, 2024, at 11:07 AM, Tolboom, Ryan via wsjt-devel <
> wsjt-devel@lists.sourceforge.net> wrote:
>
> Good Afternoon,
>
> Here is a patch that eeks out a tiny performance boost for the fano
> decoder in lib/wsprd/fano.c. It does two things:
>
>1.  It removes an ENCODE call when initializing the root node since
>encstate is set to zero so you know lsym will end up being zero.
>2. Since the ENCODE macro is operating on 32 bits (POLY1 and POLY2 are
>32 bits and the XOR based parity calcs are 32 bits) encstate in the node
>struct and _tmp in the ENCODE routine are changed to 32 bit integers
>(unsigned int), instead of unsigned long integers. This makes for slightly
>faster bitwise operations.
>
> With these changes I'm getting the same amount of decodes a 0.6% decrease
> in the time spent in the Fano decoder:
>
> === Original ===
> 69 decodes
>0.000.000.040.060.90   29.380.00   31.47
>
> Code segmentSeconds   Frac
> ---
> readwavfile   0.000.00
> Coarse DT f0 f1   0.000.00
> sync_and_demod(0) 0.040.00
> sync_and_demod(1) 0.060.00
> sync_and_demod(2) 0.900.03
> Stack/Fano decoder   29.380.93
> OSDdecoder0.000.00
> ---
> Total31.471.00
>
> === New ===
> 69 decodes
>0.000.000.040.060.90   29.170.00   31.31
>
> Code segmentSeconds   Frac
> ---
> readwavfile   0.000.00
> Coarse DT f0 f1   0.000.00
> sync_and_demod(0) 0.040.00
> sync_and_demod(1) 0.060.00
> sync_and_demod(2) 0.900.03
> Stack/Fano decoder   29.170.93
> OSDdecoder0.000.00
> ---
> Total31.311.00
>
> Given that it has to do with what instructions are used for different word
> sizes you might see more dramatic results on different architectur

[wsjt-devel] wsprd Fano Decoder Optimizations

[Tolboom, Ryan via wsjt-devel]

Good Afternoon,

Here is a patch that eeks out a tiny performance boost for the fano decoder
in lib/wsprd/fano.c. It does two things:

   1.  It removes an ENCODE call when initializing the root node since
   encstate is set to zero so you know lsym will end up being zero.
   2. Since the ENCODE macro is operating on 32 bits (POLY1 and POLY2 are
   32 bits and the XOR based parity calcs are 32 bits) encstate in the node
   struct and _tmp in the ENCODE routine are changed to 32 bit integers
   (unsigned int), instead of unsigned long integers. This makes for slightly
   faster bitwise operations.

With these changes I'm getting the same amount of decodes a 0.6% decrease
in the time spent in the Fano decoder:

=== Original ===
69 decodes
   0.000.000.040.060.90   29.380.00   31.47

Code segmentSeconds   Frac
---
readwavfile   0.000.00
Coarse DT f0 f1   0.000.00
sync_and_demod(0) 0.040.00
sync_and_demod(1) 0.060.00
sync_and_demod(2) 0.900.03
Stack/Fano decoder   29.380.93
OSDdecoder0.000.00
---
Total31.471.00

=== New ===
69 decodes
   0.000.000.040.060.90   29.170.00   31.31

Code segmentSeconds   Frac
---
readwavfile   0.000.00
Coarse DT f0 f1   0.000.00
sync_and_demod(0) 0.040.00
sync_and_demod(1) 0.060.00
sync_and_demod(2) 0.900.03
Stack/Fano decoder   29.170.93
OSDdecoder0.000.00
---
Total31.311.00

Given that it has to do with what instructions are used for different word
sizes you might see more dramatic results on different architectures.

I've also attached the scripts I used to test it out.

On a related note, does anyone still have this dataset?

http://physics.princeton.edu/pulsar/K1JT/wspr_data.tgz

It would be nice to have some non-simulated data.

73,

Ryan N2BP


test.sh
Description: Binary data


generate.sh
Description: Binary data


fano.patch
Description: Binary data
___
wsjt-devel mailing list
wsjt-devel@lists.sourceforge.net
https://lists.sourceforge.net/lists/listinfo/wsjt-devel

[wsjt-devel] FST4 Doppler Spread Overshoot Calculation

[Tolboom, Ryan via wsjt-devel]

Good Evening,

I'm looking at lib/fst4_decode.f90, specifically the code where it
calculates the frequency in the channel gain function, *g*, at which it
reaches a certain percentage of the signal power. This can be found on line
999 of lib/fst4_decode.f90

.

To prevent zero Doppler Spreads it uses a linear interpolation to get a
floating point "index" between bins of the FFT. It does this by setting xi1
(and xi2, xi3 in a similar fashion) to the current index minus one plus the
difference between the current power (sum2) and the power we're looking for
(sum2 * 0.25, for xi1) divided by the difference between the current power
(sum2) and the previous power (sum2z):

xi1=i - 1 + (sum2-0.25*sum1)/(sum2-sum2z)

If I'm interpreting this correctly this will not yield a correct result.

Let me give you an example:

For simplicity, assume we have four bins with powers 1, 2, 9, 2, and 1
respectively. Assume the bins are enumerated from zero.

[image: image.png]

The total power would be 15 and 25% of that would be 3.75. As we look for
that 25% mark, we'd find it in the do loop when i hits 2, sum2 is 12, and
sum2z is 3. xi1 would then be set to:

xi1 = 2 - 1 + (12 - 3.75)/(12 - 3) = 1 + 8.25/9 = 1.92

In other words, 92% of the way to bin 1 from bin 2. Shouldn't this be the
other way around? Shouldn't it be 92% of the way working backwards from bin
2 to bin 1 or 8% of the way from bin 1 to bin 2? It seems like 3.25 is only
slightly larger than 3 and significantly less than 12.

i believe the overshoot correction should be the difference between the
power we're looking for and the previous power divided by the difference
between the current power and the previous power:

xi1 =  i - 1 + (0.25 * sum1) - sum2z)/(sum2 - sum2z)

Which in this case would yield:

xi1 = 2 - 1 + (3.75 - 3)/(12 - 3) = 1 + 0.75/9 = 1.08

Please let me know if I'm missing something and thanks for your time,

-Ryan Tolboom N2BP
___
wsjt-devel mailing list
wsjt-devel@lists.sourceforge.net
https://lists.sourceforge.net/lists/listinfo/wsjt-devel

[wsjt-devel] Patch to Add No Drift Option to wsprd

[Tolboom, Ryan via wsjt-devel]

Good Afternoon,

The following patch adds an option to wsprd that prevents it from doing
frequency drift searches:
https://github.com/rxt1077/wspr_spread/blob/main/nodrift.patch

I wanted to post it here in case anyone else might find it useful.

73,

Ryan N2BP
___
wsjt-devel mailing list
wsjt-devel@lists.sourceforge.net
https://lists.sourceforge.net/lists/listinfo/wsjt-devel

[wsjt-devel] Doppler Spread Calculations in wsprd

[Tolboom, Ryan via wsjt-devel]

Hello,

Researchers have been using FST4 Doppler spread
 calculations at sites that experienced the
recent annular eclipse to document some pretty interesting ionospheric
effects . The question as to whether
Doppler spread could be calculated from WSPR data came up and I took a look.

Most of what's needed is already implemented in wsprd.c's subtract_signal2
function: creating a reference signal and multiplying it's conjugate by the
received signal. I created a patch
 that
computes the Doppler spread in wsprdl and adds it to the ALL_WSPR.txt
output. I wanted to post it here in case anyone would find it useful.

Thanks for all of your hard work on this software.

73,

Ryan N2BP
___
wsjt-devel mailing list
wsjt-devel@lists.sourceforge.net
https://lists.sourceforge.net/lists/listinfo/wsjt-devel

Re: [wsjt-devel] c2 files written after signals subtracted

[Tolboom, Ryan via wsjt-devel]

Steve,

Thanks for the clarification and the reasoning behind c2 files. I can work
with WAV files to get the data I need using the routines you mentioned and
I now have a better understanding of what c2 files are for.

Much appreciated,

Ryan N2BP


On Wed, Jul 19, 2023, 9:27 AM Steven Franke via wsjt-devel <
wsjt-devel@lists.sourceforge.net> wrote:

> Ryan,
>
> The -c option does what it was designed to do: "-c write .c2 file at the
> end of the first pass". It writes a .c2 file after signals decoded in the
> first pass have been subtracted. This .c2 file is useful for studying the
> effectiveness of signal subtraction, i.e. to study the residuals left after
> subtracting signals. It can also be re-analyzed by wsprd to study the
> effectiveness of a 2nd pass over the data and then again to do a 3rd pass,
> etc.
>
> If you need a .wav to .c2 converter, you might consider using the routines
> provided with wsjtx to create one.  WSJT-X does the conversion from 12000
> samples/sec to 375 samples/sec in src/widgets/mainwindow.cpp by calling the
> fortran routines in these files:
>
> /src/lib/wspr_downsample.f90:q
> /src/lib/savec2.f90
>
> Subroutine wspr_downsample() downsamples from 12000 integer samples/sec to
> 1500 complex samples/sec and function savec2() downsamples from 1500 to 375
> complex samples/s and writes out the .c2 file.
>
> Steve k9an
>
> On Jul 18, 2023, at 4:07 PM, Tolboom, Ryan via wsjt-devel <
> wsjt-devel@lists.sourceforge.net> wrote:
>
> Good Evening,
>
> When using wsprd in multi-pass mode (no '-s' option) and passing it
> the '-c' option to write a c2 file, it
> writes the c2 file at the end of the main loop on the first pass AFTER
> it subtracts out the decoded
> candidates. This means if you're using the c2 file to do analysis of
> the IQ data that was decoded you
> don't have the actual signals available (at least the ones decoded on
> the first pass).
>
> Is there any particular reason the c2 file is written after the first
> pass? The only real changes I noted
> to idat and qdat within the main loop were signals being subtracted.
> Could it be written before the
> main loop after idat and qdat are created from a wav or c2 file? If
> so, I've attached a patch for
> wsprd.c that moves the logic that calls writec2file to right before
> the main loop.
>
> Thanks for your time,
>
> Ryan Tolboom N2BP
> ___
> wsjt-devel mailing list
> wsjt-devel@lists.sourceforge.net
> https://lists.sourceforge.net/lists/listinfo/wsjt-devel
> <https://urldefense.com/v3/__https://lists.sourceforge.net/lists/listinfo/wsjt-devel__;!!DLa72PTfQgg!P0Z0BfA7H_2-3YejyeU8AgOzQaFg1hGXYWWzaWEXWGWE1g-2unLJNWNRdLqbGI4A1g5ByRt0JO6w5NpQuXNWr6pEnowSyhsU$>
>
>
> ___
> wsjt-devel mailing list
> wsjt-devel@lists.sourceforge.net
>
> https://urldefense.com/v3/__https://lists.sourceforge.net/lists/listinfo/wsjt-devel__;!!DLa72PTfQgg!P0Z0BfA7H_2-3YejyeU8AgOzQaFg1hGXYWWzaWEXWGWE1g-2unLJNWNRdLqbGI4A1g5ByRt0JO6w5NpQuXNWr6pEnowSyhsU$
>
___
wsjt-devel mailing list
wsjt-devel@lists.sourceforge.net
https://lists.sourceforge.net/lists/listinfo/wsjt-devel

[wsjt-devel] c2 files written after signals subtracted

[Tolboom, Ryan via wsjt-devel]

Good Evening,

When using wsprd in multi-pass mode (no '-s' option) and passing it
the '-c' option to write a c2 file, it
writes the c2 file at the end of the main loop on the first pass AFTER
it subtracts out the decoded
candidates. This means if you're using the c2 file to do analysis of
the IQ data that was decoded you
don't have the actual signals available (at least the ones decoded on
the first pass).

Is there any particular reason the c2 file is written after the first
pass? The only real changes I noted
to idat and qdat within the main loop were signals being subtracted.
Could it be written before the
main loop after idat and qdat are created from a wav or c2 file? If
so, I've attached a patch for
wsprd.c that moves the logic that calls writec2file to right before
the main loop.

Thanks for your time,

Ryan Tolboom N2BP


c2_before_subtract.patch
Description: Binary data
___
wsjt-devel mailing list
wsjt-devel@lists.sourceforge.net
https://lists.sourceforge.net/lists/listinfo/wsjt-devel

Re: [wsjt-devel] wsprd.c Subtracting Signals on the Final Pass

[Tolboom, Ryan via wsjt-devel]

This is exactly what I was missing! Thanks for explaining it.

Have a great day,

Ryan N2BP

On Tue, May 9, 2023, 1:57 PM Steven Franke  wrote:

> Ryan,
>
> See my comment, inline below:
>
> > On May 9, 2023, at 11:19 AM, Tolboom, Ryan 
> wrote:
> >
> > Good Morning,
> >
> > First of all thank you for taking the time to explain the process. I
> > know it can be exhausting and I greatly appreciate it.
> >
> > Secondly, I'd point out that the noncoherent_sequence_detection
> > function is called before  (line 1330) the subtract_signal2 function
> > (line 1430) in the pass loop. This means that on the last pass the
> > idat and qdat which were modified by subtract_signal2 are not used
> > anywhere (except if you have to write a C2 file).
>
> No. Look again and consider that the “pass” loop contains the “candidate”
> loop; i.e. in each pass we first identify the signal candidates (signals
> which are likely to decode) and then in the candidate processing loop we
> step over the candidates from highest to lowest SNR and try to decode each
> candidate.
>
> The routines noncoherent_sequence_detection and subtract_signal2 are
> inside of the candidate loop. The candidate loop starts at line 1304 and
> the closing brace for the loop is at line 1478.
>
> After each decode, subtract_signal2 modifies [idat,qdat] when it subtracts
> the decoded signal. Then, unless there are no more candidates, execution
> proceeds back to the top of the candidate loop so that when processing the
> next candidate noncoherent_sequence_detection will use the modified
> [idat,qdat].
>
> Steve k9an
>
> > Again, apologies if I'm mistaken.
> >
> > Ryan Tolboom N2BP
> >
> > On Tue, May 9, 2023 at 12:08 PM robert evans LAST_NAME 
> wrote:
> >>
> >> I used to code that signal processing in fortran
> >> because of the complex data type matrix
> >>
> >> I now code that in python for the same reason.
> >>
> >> K9AN DE N2LO~>
> >>
> >>
> >>> On 05/09/2023 10:10 AM Steven Franke via wsjt-devel <
> wsjt-devel@lists.sourceforge.net> wrote:
> >>>
> >>>
> >>> Hi Ryan,
> >>>
> >>> On each pass signal candidates are sorted in order of decreasing
> signal-to-noise ratio (SNR) and then wsprd sequentially attempts to decode
> each candidate. If a decoding attempt is successful, then a reconstructed
> version of the signal is subtracted from the data vector and the algorithm
> moves on to try to decode the next candidate.
> >>>
> >>> Even on the last pass, subtraction of high-SNR signal “A” may remove
> enough interference from low-SNR signal “B” so as to render signal “B”
> decodable when signal “B” would not have been decodable otherwise.
> >>>
> >>> You stated that “The updated I/Q data isn’t used as the loop doesn’t
> execute again.”. This isn’t true. On each pass the [idat,qdat] vector is
> updated in subtract_signal2 after each successful decode and the updated
> [idat,qdat] vector is then used to find the bit metrics for subsequent
> candidates in routine noncoherent_sequence_detection.
> >>>
> >>> 73 Steve k9an
> >>>
> >>>> On May 8, 2023, at 7:05 PM, Tolboom, Ryan via wsjt-devel <
> wsjt-devel@lists.sourceforge.net> wrote:
> >>>>
> >>>> Hello,
> >>>>
> >>>> When wsprd runs multiple passes, it still calls subtract_signal2() as
> >>>> well as get_wspr_channel_signals() on the last pass.
> >>>> The updated I/Q data isn't used as the loop doesn't execute again.
> >>>>
> >>>> When I modified wsprd.c to skip subtraction on the last pass I noticed
> >>>> better timing numbers (since subtract_signal2() is called one less
> >>>> time) and no detriment to my decodes.
> >>>> This was my change on line 1430 of wsprd.c
> >>>>
> >>>>   if( subtraction && !noprint && (ipass != (npasses - 1))) {
> >>>>
> >>>> Please let me know if there's something I'm not thinking of.
> >>>>
> >>>> 73,
> >>>>
> >>>> Ryan Tolboom N2BP
> >>>>
> >>>>
> >>>> ___
> >>>> 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

Re: [wsjt-devel] wsprd.c Subtracting Signals on the Final Pass

[Tolboom, Ryan via wsjt-devel]

Good Morning,

First of all thank you for taking the time to explain the process. I
know it can be exhausting and I greatly appreciate it.

Secondly, I'd point out that the noncoherent_sequence_detection
function is called before  (line 1330) the subtract_signal2 function
(line 1430) in the pass loop. This means that on the last pass the
idat and qdat which were modified by subtract_signal2 are not used
anywhere (except if you have to write a C2 file).

Again, apologies if I'm mistaken.

Ryan Tolboom N2BP

On Tue, May 9, 2023 at 12:08 PM robert evans LAST_NAME  wrote:
>
> I used to code that signal processing in fortran
> because of the complex data type matrix
>
> I now code that in python for the same reason.
>
> K9AN DE N2LO~>
>
>
> > On 05/09/2023 10:10 AM Steven Franke via wsjt-devel 
> >  wrote:
> >
> >
> > Hi Ryan,
> >
> > On each pass signal candidates are sorted in order of decreasing 
> > signal-to-noise ratio (SNR) and then wsprd sequentially attempts to decode 
> > each candidate. If a decoding attempt is successful, then a reconstructed 
> > version of the signal is subtracted from the data vector and the algorithm 
> > moves on to try to decode the next candidate.
> >
> > Even on the last pass, subtraction of high-SNR signal “A” may remove enough 
> > interference from low-SNR signal “B” so as to render signal “B” decodable 
> > when signal “B” would not have been decodable otherwise.
> >
> > You stated that “The updated I/Q data isn’t used as the loop doesn’t 
> > execute again.”. This isn’t true. On each pass the [idat,qdat] vector is 
> > updated in subtract_signal2 after each successful decode and the updated 
> > [idat,qdat] vector is then used to find the bit metrics for subsequent 
> > candidates in routine noncoherent_sequence_detection.
> >
> > 73 Steve k9an
> >
> > > On May 8, 2023, at 7:05 PM, Tolboom, Ryan via wsjt-devel 
> > >  wrote:
> > >
> > > Hello,
> > >
> > > When wsprd runs multiple passes, it still calls subtract_signal2() as
> > > well as get_wspr_channel_signals() on the last pass.
> > > The updated I/Q data isn't used as the loop doesn't execute again.
> > >
> > > When I modified wsprd.c to skip subtraction on the last pass I noticed
> > > better timing numbers (since subtract_signal2() is called one less
> > > time) and no detriment to my decodes.
> > > This was my change on line 1430 of wsprd.c
> > >
> > >if( subtraction && !noprint && (ipass != (npasses - 1))) {
> > >
> > > Please let me know if there's something I'm not thinking of.
> > >
> > > 73,
> > >
> > > Ryan Tolboom N2BP
> > >
> > >
> > > ___
> > > 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] wsprd.c Subtracting Signals on the Final Pass

[Tolboom, Ryan via wsjt-devel]

Hello,

When wsprd runs multiple passes, it still calls subtract_signal2() as
well as get_wspr_channel_signals() on the last pass.
The updated I/Q data isn't used as the loop doesn't execute again.

When I modified wsprd.c to skip subtraction on the last pass I noticed
better timing numbers (since subtract_signal2() is called one less
time) and no detriment to my decodes.
This was my change on line 1430 of wsprd.c

if( subtraction && !noprint && (ipass != (npasses - 1))) {

Please let me know if there's something I'm not thinking of.

73,

Ryan Tolboom N2BP


___
wsjt-devel mailing list
wsjt-devel@lists.sourceforge.net
https://lists.sourceforge.net/lists/listinfo/wsjt-devel

[wsjt-devel] wsprd.c Negative Index in Coarse Estimates Section

[Tolboom, Ryan via wsjt-devel]

Good Morning,

In the coarse estimates section of the /lib/wsprd/wsprd.c decoder the
kindex for the time search is negative for the first few iterations.
It's set on line 1167:

kindex=k0+2*k;

Where k0 is iterating from -10 to 21 and k is iterating over all
symbols (0 to 161).
A negative index isn't common in C, but does compile without warning
and I assume it references something earlier in the 2D ps array.
If this is an oversight, you could add an additional guard to line 1168:

if(( kindex < nffts ) && ( kindex > 0)) {

I've tried this on my machine and it doesn't seem to affect the
decodes in any negative way.
Please let me know if there's something I'm missing.

73,

Ryan Tolboom N2BP


___
wsjt-devel mailing list
wsjt-devel@lists.sourceforge.net
https://lists.sourceforge.net/lists/listinfo/wsjt-devel