Venus MFSK - modulation, coding, demodulation ============================================== Numbers below are for the settings: M=4096, RS(9,6), 1.5 Hz bin, 270 s transmissions, and the rx/decoder settings in rx_mfsk.ipynb. Code: venus_mfsk.py, tx_mfsk.ipynb, rx_mfsk.ipynb. 1. Source coding ---------------- Message: 10 characters from A-Z, 0-9 and space (37 symbols), right-padded with spaces. Read as a base-37 number: 37^10 fits in 53 bits. Append CRC-16/CCITT-FALSE (poly 0x1021, init 0xFFFF) over those 53 bits. 53 + 16 = 69 bits, plus 3 leading zero pad bits = 72 bits = k = 6 symbols of 12 bits each. 2. Channel coding ----------------- Reed-Solomon RS(9,6) over GF(4096), systematic (the 6 info symbols come first, then 3 parity symbols). Built as a shortened RS(4095,4092). Rate 2/3. Being MDS, any 6 symbols fix the whole codeword. The decoder relies on this all the time: it guesses 6 (or 5 + 1) symbols and computes the other ones. How it is built (galois library, ReedSolomon(4095, 4092)): field GF(2^12), primitive polynomial x^12+x^7+x^6+x^5+x^3+x+1, primitive element alpha = x (integer 2). A symbol value v is the 12-bit integer whose bits are the polynomial coefficients, so addition is XOR, and v is also the tone number. generator g(x) = (x - alpha)(x - alpha^2)(x - alpha^3) = x^3 + 14 x^2 + 56 x + 64 (narrow sense: roots alpha^1..alpha^3, so 3 parity symbols and minimum distance 4) encoding message symbols m0..m5 are the coefficients of x^8..x^3 of the codeword polynomial c(x); the parity symbols p0..p2 are the remainder of m(x) x^3 mod g(x). Codeword sent: m0 m1 m2 m3 m4 m5 p0 p1 p2 and c(alpha) = c(alpha^2) = c(alpha^3) = 0. Shortening: the full code has 4092 info symbols. The first 4086 of them (the highest powers of x) are fixed at zero and not sent. Leading zeros do not change the remainder mod g(x), so the 9 symbols above are exactly the last 9 of the full 4095-symbol codeword. The receiver knows the zeros and never has to estimate them. Symbols are not shifted or reordered: info symbol j sits at position j, parity at 6..8. The shortened code is no longer cyclic, but nothing relies on that; the decoder uses the 6 x 9 generator matrix G (the encoder applied to the 6 unit vectors) and solves for the codeword from any 6 positions. The repetition over dwells (dwell j carries position j mod 9, section 3) is part of the modulation, not the code. 3. Modulation ------------- 4096-FSK, one code symbol (12 bits) per tone. frame = 166667 samples at 250 ks/s = 0.667 s, so 1 FFT bin = 1.50 Hz (chosen to match the Doppler spread of the Venus echo) tones = 4096, spaced 3 bins = 4.5 Hz, block 18.4 kHz centered on DC dwell = 4 frames = 2.67 s on one tone tx = 101 dwells = 269.3 s Dwell j carries code symbol j mod 9, so the 9 symbols are cycled through the transmission and each one gets 11-12 dwells (29-32 s). Every tone sits on an exact FFT bin and makes a whole number of cycles per frame, so phase is continuous across tone changes without any tracking. Constant envelope, 10 ms raised-cosine ramp at start and end, peak 1 dB below int16 full scale. Output is ci16_le SigMF; all parameters are stored in the mfsk:* fields of the metadata, so the receiver reads them from there. Scrambling (on): in each dwell the transmitted tone is tone = symbol XOR pn(seed, tx index, dwell) with pn taken from SHA-256 of that triple. XOR is addition in GF(4096). Ten tx files (-tx00 .. -tx09) are generated, each with its own pn sequence, so a given symbol lands on different tones in every dwell and every transmission. A fixed carrier is spread over many tone values after descrambling instead of adding up on one. 4. Demodulation --------------- Non-coherent energy detection, no phase or frequency tracking. Recordings come from a directory (rx_dir) or a list of files (rx_files). Only recordings whose tx file has mfsk:* fields are used. A chan0 file brings its chan1 partner along. They are processed in tx time order. Before the FFT the recording must be on the right time and frequency: - Doppler is removed either beforehand by sigmf_dedoppler.py (the _dedop files) or on the fly in rx_mfsk (dedoppler = True), using the SPICE Doppler of the sub-radar point for that receiver. A constant residual can be taken out with freq_offset_hz. - The echo start is tx time + round trip time, from radar:echo_time in a _dedop file or computed from SPICE when dedopplering on the fly. - chan0/chan1 recordings of one dish are combined to circular polarisation: (x0 + w1 e^(j*phi) x1) / sqrt(2), phi = pol_phase_deg. The right phase differs per site and sometimes per day, so it is set per session. With equalize_power, w1 = sqrt(P0/P1), measured over 20 one-second chunks spread over the file. That is mostly noise, so this equalises the noise of the two channels before they are added. Then, per recording: a) Frames. Hann windows of one frame length with 50% overlap, using only windows that lie entirely inside one dwell, so no window mixes two tones. That gives 7 windows per dwell. FFT, |X|^2. b) Noise normalisation. In every frame, divide the power spectrum by median(power over the tone block) / ln 2. For exponentially distributed noise that is the mean, and the median ignores the few bins that hold signal or interference. After this a noise bin has mean 1 and variance 1 in every frame, whatever the gain of the receiver. Take the value at each of the 4096 tone bins (kernel_bins = 1: just the tone's own bin). c) Sum the 7 windows of each dwell -> D (101 dwells x 4096 tones). d) RFI flagging. The signal moves to another tone every dwell; a carrier stays. A tone is flagged in dwell d if its median normalised energy in the 2 dwells before, or in the 2 after, exceeds 1.8x the noise mean (rfi_window_dwells = 2, rfi_threshold = 1.8). Flagged cells are set to the noise mean, so they add nothing either way. The receiver prints the percentage of flagged cells per recording. e) Descramble: value v of dwell d is read from tone v XOR pn[d]. f) Add each dwell row to the row of its code symbol (d mod 9). This builds E (9 positions x 4096 values), plus a noise mean L and noise variance V per row (see metrics below). E keeps growing over all recordings of the tx set, and a decode is tried after each recording is added. 5. Metrics ---------- These numbers appear in the receiver and decoder output. E[i, v] Accumulated normalised energy for value v at code position i. Each frame contributes 1 on average from noise, plus whatever echo power falls in that bin. L[i] Expected value of E[i, v] when it is noise only: the number of frames added into row i (times kernel_bins). One transmission gives 11-12 dwells x 7 windows = 77-84 per row. V[i] Noise variance of E[i, v]. For independent frames it would equal L. The Hann windows overlap by 50%, so neighbouring windows share noise; that raises the variance of a dwell sum by a factor 1.19 (7 windows per dwell). So V = 1.19 L, and sqrt(V) is about 10 per transmission. z[i, v] (E[i, v] - L[i]) / sqrt(V[i]). How many standard deviations a value stands above the noise. With 4096 noise values per row, the strongest noise value is usually around z = 4. A weak echo tone therefore often isn't the strongest in its row, only in the top few. This is why the decoder works with lists. Hard decision The strongest value in each row, argmax_v E[i, v]. Reliability rel[i] (E[i, best] - E[i, second best]) / sqrt(V[i]). A large gap means the hard decision in that row is probably right. Used to choose which positions to trust. Score of a candidate codeword c sum over the 9 positions of E[i, c_i]. Per frame, a noise bin is exponential with mean 1 and a bin holding a Rayleigh-faded echo is exponential with mean 1 + s. The log-likelihood ratio between the two is a constant times the energy, so the energy sum is the maximum-likelihood metric. Candidate z (score - sum L) / sqrt(sum V). The same score, expressed in standard deviations of a random codeword. If all 9 rows are equally strong, this is about 3x the average per-symbol z, because sqrt(9) = 3. Reported as "z = ..." with a decode. n_agree For a decode: in how many of the 9 positions the decoded value equals the hard decision. 9/9 is a strong signal; 5/9 or 6/9 means the decoder found the message even though several symbols were not the strongest tone in their row. Pass and method (printed under a decode) Which pass found the message, which positions it fixed, and where the decoded value ranked in each of those positions' lists. For example: pass 1: OSD basis 0 of 256 (most reliable), positions 1,2,5,6,7,8, list ranks 6,6,1,1,1,1 means the 6 most reliable positions were used and in two of them the right value was only the 6th strongest. A '>' means beyond the list. For pass 2 it also gives the free position and the rank of the decoded value there among all 4096 ("tone rank r of 4096"). This shows how deep the lists really need to be. n_candidates Number of codewords scored, both passes together. best_score Highest score seen, whether or not it passed the CRC. Shown when there is no decode, so you can see the score creeping up. Echo profile (diagnostics in rx_mfsk, after a decode) Average normalised spectrum around the transmitted tone, over all frames. It needs the codeword, so it only works after a decode or with the known message. From it: excess = peak bin - noise mean, the echo power in the bin as a fraction of the noise power in the bin sigma = 1 / sqrt(number of independent frames averaged) SNR = excess / sigma Pr/N0 = excess x bin width, in dB-Hz (echo power that lands in the centre bin only) Averaged symbol spectrogram (rx_mfsk) The frame energies of all recordings, descrambled and averaged per code symbol, shown against symbol value and time within the dwell. The codeword values are marked in red. A visual check that the echo is on the decoded values and not on an interference line. 6. Decoding ----------- Soft symbols The RS code is decoded with soft symbols only. There is no hard-decision step and no algebraic RS decoder (Berlekamp-Massey or similar). A hard decoder would not get far: with distance 4 it corrects 1 wrong symbol, or 3 known erasures, and near the threshold 3 to 5 of the 9 hard decisions are wrong. The soft symbol for code position i is the whole row E[i, 0..4095]: one accumulated, noise-normalised energy for every possible symbol value, together with L[i] and V[i]. It is set up in section 4: - every Hann window gives the power in the bin of each tone, divided by the noise mean of that window (step b) - the windows of a dwell are summed (c), RFI cells are reset to the noise mean (d), and the tone axis is descrambled so the column is the symbol value, not the tone (e) - every dwell is added to the row of the position it carried (f), over all dwells of all recordings So a soft symbol is a 4096-value histogram of energy, not a probability. It is not converted to probabilities or LLRs, because it does not have to be. Per frame, the log-likelihood ratio of "echo on this value" against "noise only" is (s / (1 + s)) x energy - ln(1 + s), with s the echo SNR in the bin. The factor and the constant are the same for every value and every position, so ranking codewords by the plain energy sum gives the same order as ranking them by likelihood. An RFI-flagged cell sits at the noise mean and counts as "no information" for that dwell. That reasoning assumes s is the same in every frame. In reality echo strength varies from recording to recording (several dB), and all recordings are added with equal weight. The optimum would weight each recording by roughly its own s, which is not known before a decode. The decoder uses the soft symbols in three ways: - lists: the strongest values in each row (list_depth, free_depth) - reliability: the gap between the best and second-best value, to decide which positions to trust - scoring: every candidate codeword is scored by summing E over all 9 positions, including positions it was not guessed from The decoder looks for the codeword with the highest score that also passes the message checks. There are 4096^6 codewords, so it cannot try them all. Instead it guesses the values at a few positions from the short lists of strong values, lets the RS code fill in the rest, and scores the result. There are two passes. The second one only runs if the first finds nothing. Settings in rx_mfsk: n_bases = 256, list_depth = 10, n_check = 50, n_free_sets = 16, free_depth = 5 (the last two are defaults). Pass 1: ordered-statistics decoding (OSD) 1. For each of the 9 positions, list the 10 strongest values (list_depth). 2. Choose 6 positions, a "basis". The first basis is the 6 most reliable positions. The others are drawn at random, with the more reliable positions drawn more often. 256 draws (n_bases); repeats are skipped. There are only C(9,6) = 84 possible sets, and in practice about 65 get used. 3. For each basis, try every combination of the listed values at those 6 positions: 10^6 = 1 million combinations. Each one gives exactly one codeword (MDS), which is computed and scored. 4. Keep the 50 best per basis, then go through all of them from the highest score down. The first one that passes the checks (section 7) is the decode. Give up after 50 distinct candidates have failed (n_check). About 65 million candidates (about 65 distinct bases x 1 million). This works if there are 6 positions where the right value is somewhere in the top 10. If only 5 positions are like that, no basis can produce the right codeword, however well it scores. Going from depth 5 to 10 makes that less likely, at 64x more candidates per basis. Pass 2: OSD with one free symbol (n_free_sets, free_depth) The idea: only ask for 5 positions with the right value in their lists, and try all 4096 values for the 6th degree of freedom. 1. Choose sets of 5 positions S. All C(9,5) = 126 sets are ranked by the sum of their reliabilities, and the best 16 are used (n_free_sets). 2. Fix those 5 positions to a combination of their 5 strongest values (free_depth): 5^5 = 3125 combinations. 3. With 5 values fixed, the codewords that fit form a line of 4096 codewords: c = base + u * P_f u = 0 .. 4095 where u is the value at one of the 4 remaining positions (f), base is the codeword with u = 0, and P_f follows from the generator matrix. Addition in GF(4096) is XOR, so all 4096 points on the line are scored at once with table lookups. 4. That is 3125 x 4096 = 12.8 million candidates per set, 205 million for 16 sets. Pass 2 uses its own depth (free_depth = 5), not list_depth; at depth 10 it would be 32x larger. Per set the 50 best are kept; all of those are rescored and checked exactly as in pass 1 (50 distinct, best first). The values at f and at the 3 other positions do not need to be in any list: they follow from the code, and their energy is still part of the score. Without a decode both passes run: about 270 million candidates per attempt. 7. Checks and false decodes --------------------------- Every candidate is a valid RS codeword by construction, so the 3 parity symbols cannot reject a candidate. They help only through the score, because a wrong guess makes the computed parity symbols land on noise. The real filter is in the 6 information symbols: pad bits the top 3 bits must be zero passes 1 in 8 range the value must be < 37^10 passes 0.53 CRC-16 must match passes 1 in 65536 A random wrong codeword passes all three with probability about 1e-6. Each pass checks at most 50 candidates, so a decode attempt has a false-decode chance of at most about 1e-4. A decode is tried after every recording, so over 10 recordings that adds up to about 1e-3. Searches over many subsets of recordings make many more attempts, and the risk grows with them; use a lower n_check there. The candidate z is not used as a threshold (min_z is off). Among 270 million candidates, the best one built purely from noise peaks also reaches z around 10, about the same as a weak real decode. In practice a decode needs the true codeword at z above roughly 11, so that it beats the best noise candidates that also pass the CRC. With n_check = 50 (was 20) a true codeword that ranks between 20th and 50th still gets checked. The gain is small, a few tenths in z, while the false-decode risk grows in proportion (2.5x).