Hi Pete, I don’t think that there is any bug in the FT8 CRC.
As I pointed out back when we were having this discussion some time ago, the tables in Koopman and Chakravarty do not directly apply to our application. Any codeword produced by either of the FT8 decoders is a valid codeword. That is, the returned codeword always satisfies all 87 of the parity check equations associated with our LDPC code. We use the CRC to detect cases where the (valid) codeword returned from the decoder happens to be the wrong codeword. If the LDPC code is any good to begin with, any valid but incorrect codeword will differ from the correct one in many bits, i.e. the Hamming distance between an incorrect codeword and the correct one will be large - significantly larger than the Hamming distances considered in Koopman and Chakravarty. The same holds true for the Hamming distance between the “message” portion of any incorrect codeword and the correct message. The bottom line is that we had to rely on long simulations based on our particular (174,87) LDPC code to determine how well any particular CRC polynomial would work. Based on these simulations, we determined that the polynomial that we chose gave excellent performance, commensurate with the performance that we expect for an effective 12-bit CRC. In particular, we find that the chosen CRC reduces the undetected error rate by a factor of about 2^12. Finally, perhaps it’s worth pointing out that the use of a 12-bit CRC is what enabled us to use the very effective, but computationally intensive, “ordered-statistics” decoding (OSD) algorithm to gain about 1 dB beyond what the iterative soft-decision belief-propagation decoding algorithm can provide. We realize even more gain from the OSD approach when doing “AP” decoding. The high sensitivity of the OSD approach comes with a downside — the ordered-statistics decoder is a complete decoder, that is, it always produces a codeword, even if you feed it pure noise. To use such a decoder it is necessary to have a very effective way to recognize when the returned codeword could not possibly be correct. It would not have been feasible to use this more sensitive decoder if we had used anything much shorter than a 12-bit CRC. Steve K9AN > On Nov 27, 2017, at 12:50 AM, Pete <pete...@shaw.ca> wrote: > > Just for fun I've been trying to implement an FT8 encoder that would run on a > Teensy (or Arduino) microcontroller. As part of that effort, I've run into a > problem trying to replicate the CRC12 used in WSJTX. I've come to the > conclusion that the use of 0xC06 in crc12.cpp is a mistake/bug. > I notice that Mike W9MDB pointed out this problem on the wsjt-devel list back > in March when he wrote: > > You may want to check your polynomial. I do believe 0xc06 should be 0xc07 > > -- > > you never want a zero x^0 term. > > Although I agree with him that when specifying a CRC to BOOST, it must be an > odd number - i.e. low order bit is set - I disagree that 0xC06 should be > 0xC07. > > When specifying a polynomial to BOOST, the highest-order term of the > polynomial is omitted. But in the paper by Koopman & Chakravarty (K&C), the > low-order term is omitted. If it were decided to use the K&C polynomial 0xC07 > (which is a much better choice than 0xC06), this would have to be specified > as 0x80F to BOOST. > > Mike also asked: > > What's the logic behind using a 12-bit CRC? Is there a plan of some sort > > here? > > If I understand Table 4 in K&C correctly, any one of the 8-bit polynomials > 0x97, 0x98, 0x83 or 0xCD would perform better than the 12-bit 0xC06 even if > it had been correctly specified to BOOST. An 8-bit polynomial would also free > up four bits in the message. > > If the polynomial as currently implemented in 1.8.0 is indeed incorrect, what > is involved in getting it changed to a better 12-bit or 8-bit polynomial? > > 73 > Pete VE5VA > > > ------------------------------------------------------------------------------ > Check out the vibrant tech community on one of the world's most > engaging tech sites, Slashdot.org! http://sdm.link/slashdot > _______________________________________________ > wsjt-devel mailing list > wsjt-devel@lists.sourceforge.net > https://lists.sourceforge.net/lists/listinfo/wsjt-devel ------------------------------------------------------------------------------ Check out the vibrant tech community on one of the world's most engaging tech sites, Slashdot.org! http://sdm.link/slashdot _______________________________________________ wsjt-devel mailing list wsjt-devel@lists.sourceforge.net https://lists.sourceforge.net/lists/listinfo/wsjt-devel
