Re: [wsjt-devel] FT8 Soft Demapper in WSJT-X
Steve, Thank you very much for taking the time to answer my question in detail. I will dig out the papers you reference and take a read. Re the Gray map, that all makes perfect sense now with the hindsight of your explanation! There are clearly a lot of things to learn in the source code of WSJT-X. James (VK3JPK) > On 30 Jul 2019, at 1:37 am, Steven Franke via wsjt-devel > wrote: > > Hi James, > >> The source code in question is lines 168 through 215 of lib/ft8/ft8b.f90 >> (Git tag wsjtx-x 2.1). This source code appears to implement a “soft >> demapper” that takes groups of 1, 2 or 3 successive symbol observations and >> turns these into groups of 3, 6 or 9 log likelihood ratios that are >> subsequently consumed by one of the LDPC decoders. As part of the demapping >> process, the Gray code permutation applied to symbols at the transmitter is >> removed. >> >> Is there a textbook or specific journal/conference papers that describe how >> this demapper works? I can figure out the algorithm being used, but I am >> looking for an explanation as to why that algorithm generates a good >> approximation to the LLR for FT8’s 8-GFSK modulation, and what specific >> channel impairments it is trying to deal with. > > The code that you referenced implements noncoherent sequence estimation for > groups of symbols of length, N, for N = 1, 2, 3. When the channel happens to > be coherent over times that span several symbols this technique can > significantly improve sensitivity. > > A reference that discusses this technique is: > > Simon, M.K., and D. Divsalar, “Maximum-Likelihood Block Detection of > Noncoherent Continuous Phase Modulation,” IEEE Trans. on Communications, Vol. > 41, No. 1, January 1993, p.90. > > As you might expect, there are dozens of articles on the topic — but this one > is a good overview. > > After sequence estimation has determined a soft metric for each of the 2^N > possible symbol sequences, the next step is to derive soft bit metrics (“log > likelihoods”) for each of the 3*N bits that are conveyed by the sequence of > length N. > > There are many ways to do this and no one way is best for all possible > channels. We use a max-log approximation to the numerator and denominator of > the metric given in equation (17) of this reference: > > Souryal, M. R., E. G. Larsson, B. Peric and B. R. Vojcic, “Soft-Decision > Metrics for Coded Orthogonal Signaling in Symmetric Alpha-Stable Noise,” IEEE > Transactions on Signal Processing, Vol. 56, No. 1, January 2008, p. 266. > >> I was also wondering how the specific Gray code mapping in FT8 was chosen? >> It is clearly not the “reflected binary code” that normally passes for a >> Gray code, so clearly it is something else that I don’t yet understand. > > The Gray mapping is defined such that the bit sequences associated with > neighboring tones differ in only one position. > > With reference to subroutine genft8.f90, note that the 8 successive entries > in the graymap vector are indexed by indices formed from 3 successive bits, > and each graymap vector element represents a tone. > > The graymap vector is defined like this: > > integer graymap(0:7) > data graymap/0,1,3,2,5,6,4,7/ > > For example, graymap(6)=4. This means that the bit sequence 110 (6) is mapped > to tone 4. > > Here’s the correspondence between tones and bits that results from the > graymap definition given above: > > tone bits > 0000 > 1001 > 2011 > 3010 > 4110 > 5100 > 6101 > 7111 > > I hope that this addresses your questions. > > Steve k9an > >> >> James (VK3JPK) >> >> >> >> ___ >> 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] FT8 Soft Demapper in WSJT-X
Hi James, > The source code in question is lines 168 through 215 of lib/ft8/ft8b.f90 (Git > tag wsjtx-x 2.1). This source code appears to implement a “soft demapper” > that takes groups of 1, 2 or 3 successive symbol observations and turns these > into groups of 3, 6 or 9 log likelihood ratios that are subsequently consumed > by one of the LDPC decoders. As part of the demapping process, the Gray code > permutation applied to symbols at the transmitter is removed. > > Is there a textbook or specific journal/conference papers that describe how > this demapper works? I can figure out the algorithm being used, but I am > looking for an explanation as to why that algorithm generates a good > approximation to the LLR for FT8’s 8-GFSK modulation, and what specific > channel impairments it is trying to deal with. The code that you referenced implements noncoherent sequence estimation for groups of symbols of length, N, for N = 1, 2, 3. When the channel happens to be coherent over times that span several symbols this technique can significantly improve sensitivity. A reference that discusses this technique is: Simon, M.K., and D. Divsalar, “Maximum-Likelihood Block Detection of Noncoherent Continuous Phase Modulation,” IEEE Trans. on Communications, Vol. 41, No. 1, January 1993, p.90. As you might expect, there are dozens of articles on the topic — but this one is a good overview. After sequence estimation has determined a soft metric for each of the 2^N possible symbol sequences, the next step is to derive soft bit metrics (“log likelihoods”) for each of the 3*N bits that are conveyed by the sequence of length N. There are many ways to do this and no one way is best for all possible channels. We use a max-log approximation to the numerator and denominator of the metric given in equation (17) of this reference: Souryal, M. R., E. G. Larsson, B. Peric and B. R. Vojcic, “Soft-Decision Metrics for Coded Orthogonal Signaling in Symmetric Alpha-Stable Noise,” IEEE Transactions on Signal Processing, Vol. 56, No. 1, January 2008, p. 266. > I was also wondering how the specific Gray code mapping in FT8 was chosen? > It is clearly not the “reflected binary code” that normally passes for a Gray > code, so clearly it is something else that I don’t yet understand. The Gray mapping is defined such that the bit sequences associated with neighboring tones differ in only one position. With reference to subroutine genft8.f90, note that the 8 successive entries in the graymap vector are indexed by indices formed from 3 successive bits, and each graymap vector element represents a tone. The graymap vector is defined like this: integer graymap(0:7) data graymap/0,1,3,2,5,6,4,7/ For example, graymap(6)=4. This means that the bit sequence 110 (6) is mapped to tone 4. Here’s the correspondence between tones and bits that results from the graymap definition given above: tone bits 0000 1001 2011 3010 4110 5100 6101 7111 I hope that this addresses your questions. Steve k9an > > James (VK3JPK) > > > > ___ > 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] FT8 Soft Demapper in WSJT-X
WSJT-X Developers, I have been studying the WSJT-X source code to learn how it decodes FT8 signals to enhance my rather outdated (1980s) understanding of DSP and information theory. There is one part of the source code that I can’t figure out and I was hoping that one of the WSJT-X developers could point me in the right direction. The source code in question is lines 168 through 215 of lib/ft8/ft8b.f90 (Git tag wsjtx-x 2.1). This source code appears to implement a “soft demapper” that takes groups of 1, 2 or 3 successive symbol observations and turns these into groups of 3, 6 or 9 log likelihood ratios that are subsequently consumed by one of the LDPC decoders. As part of the demapping process, the Gray code permutation applied to symbols at the transmitter is removed. Is there a textbook or specific journal/conference papers that describe how this demapper works? I can figure out the algorithm being used, but I am looking for an explanation as to why that algorithm generates a good approximation to the LLR for FT8’s 8-GFSK modulation, and what specific channel impairments it is trying to deal with. I was also wondering how the specific Gray code mapping in FT8 was chosen? It is clearly not the “reflected binary code” that normally passes for a Gray code, so clearly it is something else that I don’t yet understand. James (VK3JPK) ___ wsjt-devel mailing list wsjt-devel@lists.sourceforge.net https://lists.sourceforge.net/lists/listinfo/wsjt-devel