Hi Mike,
it is not cleared automatically. TBH it's not a big deal as hash
collisions that cause incorrect decodes are rare since the vast majority
of WSPR transmissions are Type 1 messages. We normally suggest deleting
it if someone reports an unexplained incorrect decode. Many wspr systems
run 24/7 so there are no system restarts, or at least very few.
73
Bill
G4WJS.
On 14/08/2021 14:50, Black Michael via wsjt-devel wrote:
So is the hash table cleared automagically or does the user need to do it?
It would seem one might want to clear it during "system" startup perhaps?
Mike W9MDB
On Saturday, August 14, 2021, 08:05:30 AM CDT, Bill Somerville via
wsjt-devel <wsjt-devel@lists.sourceforge.net> wrote:
Mike,
there is no CRC in the WSPR protocol, details are here:
https://www.physics.princeton.edu/pulsar/K1JT/WSPR_2.0_User.pdf
<https://www.physics.princeton.edu/pulsar/K1JT/WSPR_2.0_User.pdf>
Hash codes are using in WSPR Type 2 and Type 3 messages where the call
or locator specified to send does not fit into the 28-bit or 15-bit
respective source encodings. Hash codes are needed to carry call
information between a pair of transmissions allowing the second to be
decoded using a hash code lookup.
Hash values would be useless if they were not saved, the lookup relies
on the relatively low probability of a hash collision if the hash
table is maintained in a MRU (most recently used) ordering. Also wsprd
is used stand-alone by several systems to decode each received period,
without a file of hash codes it could never do a successful hash lookup!
Hash collision likelihood increases if the hash table is allowed to
get too big, this is because a message with the hash code may be
received having never received the first message with the matching
call. It makes sense to clear the hash table file occasionally to
avoid this happening too often.
73
Bill
G4WJS.
On 14/08/2021 13:40, Black Michael via wsjt-devel wrote:
Doesn't WSPR also use the CRC in messages? So it would be a
combination of collision + valid CRC.
The 50/50 point for 32768 values is 214.
Why does WSPR remember the hash value?
We do see bogus matches in FT8 modes and such -- not real often but
every once in while a callsign hash will match a random
decode....same 15 bit hash being used for that too.
Given the much lower WSPR counts I would expect "valid" collisions to
be pretty rare.
Mike W9MDB
On Friday, August 13, 2021, 05:41:12 PM CDT, Phil Karn via wsjt-devel
<wsjt-devel@lists.sourceforge.net>
<mailto:wsjt-devel@lists.sourceforge.net> wrote:
The hash function used in wspr is 15 bits wide, i.e., there can be
32,768 values. This may seem like a lot, but the "birthday paradox" says
that the probability of a collision grows faster than you might expect
as the set size grows. It comes from the fact that you only need ~23
people to have a 50% probability that two of them have the same birthday.
A very rough approximation is that the probability of a collision is 1/2
when the set size is equal to the square root of the hash size. For 15
bits, that's about 180. My hashtable.txt for 40m currently has 353
entries.
Has anyone seen a collision in practice? If one occurs, the most recent
duplicate entry is most likely the correct one. Requiring a match in the
first 4 characters of the grid square would also seem to greatly reduce
the problem.
Phil
_______________________________________________
wsjt-devel mailing list
wsjt-devel@lists.sourceforge.net
https://lists.sourceforge.net/lists/listinfo/wsjt-devel
