Joint Delay-Doppler Estimation and Data Detection

The Joint Algorithm

This section develops the concrete joint estimation-detection algorithm for OTFS-ISAC. The structure follows from the DD-ISAC identity (§2): treat the data grid XDDX_{DD} and the target parameters Θ\Theta as two unknowns in a bilinear model, and alternate between estimating each given the other. The result is a unified ISAC receiver that achieves near-optimal sensing and detection simultaneously.

The point is that this alternating approach is not a heuristic β€” it is the natural EM-like algorithm for the OTFS-ISAC likelihood, with convergence guarantees to a local MAP optimum.

πŸŽ“CommIT Contribution(2020)

DD-Domain Waveform Design for ISAC

L. Gaudio, M. Kobayashi, G. Caire, G. Colavolpe β€” IEEE Trans. Wireless Communications

Gaudio, Kobayashi, Caire, and Colavolpe (IEEE TWC 2020) established the technical foundation for OTFS-ISAC. Their key contributions:

  1. Quantitative CRLB analysis proving that OTFS meets the information-theoretic limits for joint range-velocity estimation, simultaneously with data communication.
  2. Thumbtack ambiguity established rigorously as a consequence of OTFS's Gabor lattice structure (Chapter 11's foundation originated here).
  3. Comparison with OFDM-ISAC: proof that OTFS requires fewer waveform resources to achieve the same sensing accuracy.
  4. Joint estimation algorithm: alternating between data detection and target estimation, with performance close to ML asymptotically.

This is one of the two main CommIT contributions defining OTFS-ISAC (the other being the Yuan-Schober-Caire 2024 tutorial). Together, they establish OTFS as the 6G ISAC waveform. The algorithm we develop in this section is the concrete implementation of the Gaudio et al. framework.

commitisacgaudio-caire

Joint OTFS-ISAC Estimation-Detection

Complexity: O(Titerβ‹…MNlog⁑(MN))O(T_{\text{iter}} \cdot MN \log(MN))
Input: Received DD grid YDDY_{DD}, pilot structure, noise
variance Οƒ2\sigma^2, max iterations TiterT_{\text{iter}}
Output: Target estimates Θ^\hat{\Theta}, data estimates X^DD\hat{X}_{DD}
1. Initial target estimation:
Use embedded pilot (Chapter 7) to find initial (β„“^i,k^i,h^i)(\hat{\ell}_i, \hat{k}_i, \hat{h}_i).
2. Initialize X^DD(0)=0\hat{X}_{DD}^{(0)} = 0, Θ^(0)\hat{\Theta}^{(0)} from step 1.
3. for iteration t=1,…,Titert = 1, \ldots, T_{\text{iter}} do
4. \quad E-step (data detection): Given Θ^(tβˆ’1)\hat{\Theta}^{(t-1)},
apply LCD or MP detector (Chapter 8) to obtain X^DD(t)\hat{X}_{DD}^{(t)}.
5. \quad Super-resolution step (target refinement):
Given X^DD(t)\hat{X}_{DD}^{(t)}, refine Θ^(t)\hat{\Theta}^{(t)}:
a. Subtract data contribution: Y~(t)=YDDβˆ’HDD(Θ^(tβˆ’1)) X^DD(t)\tilde{Y}^{(t)} = Y_{DD} - \mathbf{H}_{DD}(\hat{\Theta}^{(t-1)})\,\hat{X}_{DD}^{(t)}.
b. Correlate against hypothesized (Ο„,Ξ½)(\tau, \nu) offsets near
each detected target: compute local ambiguity surface.
c. Newton iteration on local peak to obtain sub-grid
(Ο„^,Ξ½^)(\hat{\tau}, \hat{\nu}) accuracy.
6. end for
7. Return (Θ^(Titer),X^DD(Titer))(\hat{\Theta}^{(T_{\text{iter}})}, \hat{X}_{DD}^{(T_{\text{iter}})}).

The algorithm alternates between:

  • Data detection (Chapter 8 detector with estimated channel).
  • Target refinement (Newton / super-resolution on residual). Each iteration improves both estimates. Typical Titer=2T_{\text{iter}} = 2–33. Total complexity: ∼3Γ—\sim 3\times data-only OTFS detection.
,

Theorem: Convergence of Joint ISAC Algorithm

The alternating estimation-detection algorithm above converges to a local MAP estimate of (Θ,XDD)(\Theta, X_{DD}) under mild conditions:

  • Initialization close enough to the global MAP that the local basin contains both (i.e., initial channel estimate within the thumbtack main lobe).
  • Noise variance Οƒ2\sigma^2 below a level determined by the target scene's dynamic range.

Convergence speed: O(log⁑(MN))O(\log(MN)) iterations; typically 2-3 suffice at 10+ dB SNR. The final estimates (Θ^,X^DD)(\hat{\Theta}, \hat{X}_{DD}) achieve the CRLB and BER slopes respectively of the two objectives.

This is the standard EM-algorithm convergence: each iteration improves the joint likelihood by moving in the gradient direction of one variable at a time. The thumbtack ambiguity ensures that the target-refinement step has a well-behaved local landscape (no ambiguity within the main lobe), hence reliable convergence.

Proof
EM interpretation

E-step: maximize likelihood w.r.t. XDDX_{DD} given Θ\Theta. M-step: maximize likelihood w.r.t. Θ\Theta given XDDX_{DD}. Each step increases the log-likelihood monotonically.

Local MAP

The algorithm converges to a fixed point of the EM iterations, which is a local maximum of p(Y∣X,Θ)p(Y | X, \Theta).

Global optimality

At high SNR and with good initialization, the local maximum is the global maximum β€” achieving the joint ML estimator. At low SNR or with poor initialization: local-only convergence.

Rate

EM convergence rate: bounded by the matrix condition number of the Hessian at the MAP. For OTFS with thumbtack ambiguity, the condition number is moderate; rate is O(log⁑(MN))O(\log(MN)). β– \blacksquare

Key Takeaway

Joint OTFS-ISAC converges reliably. The alternating algorithm of Gaudio et al. converges to a MAP solution in 2-3 iterations at typical SNRs, achieving both the sensing CRLB and the detection BER slope simultaneously. The thumbtack ambiguity is the key enabler β€” without it, target refinement could converge to false local maxima from ambiguous ridges.

Joint ISAC Algorithm: Data BER and Sensing MSE

Plot the data BER and sensing-MSE (averaged over target scenes) as a function of outer iteration count. Both metrics improve across 3-4 iterations; convergence is rapid. Compare with separate processing (first sense, then detect with known channel) β€” the joint algorithm achieves both objectives simultaneously with minimal iteration overhead.

Parameters
15
3
5

Definition:

Super-Resolution Target Refinement

Super-resolution refinement estimates target parameters beyond the grid resolution. Given an initial estimate (β„“^i,k^i)(\hat{\ell}_i, \hat{k}_i) from threshold-based detection, compute the local ambiguity surface: Ξ›(δτ,δν)β€…β€Š=β€…β€Šβˆ£βŸ¨Y~,shift(δτ,δν)XDD⟩∣2,\Lambda(\delta_\tau, \delta_\nu) \;=\; |\langle \tilde{Y}, \text{shift}(\delta_\tau, \delta_\nu) X_{DD}\rangle|^2, where Y~\tilde{Y} is the residual after subtracting data, and the shift operates fractionally on the DD grid.

Newton iteration on Ξ›\Lambda finds the true fractional offset (Ο΅i(Ο„),Ο΅i)(\epsilon_i^{(\tau)}, \epsilon_i) within the target's neighborhood. Accuracy: CRLB-matched (ΟƒβˆΌ1/ρ\sigma \sim 1/\sqrt{\rho} in the local resolution units).

In practice, 2-3 Newton iterations refine to 0.01 of resolution cell. This is the key step enabling fine-velocity sensing (Chapter 11's CRLB).

How Far Can Super-Resolution Go?

The CRLB bounds the achievable accuracy: Οƒv=c/(2Tf0ρ)\sigma_v = c/(2Tf_0\sqrt{\rho}). At SNR = 30 dB: Οƒvβ‰ˆ0.01Ξ”v\sigma_v \approx 0.01 \Delta v. At SNR = 40 dB: Οƒvβ‰ˆ0.003Ξ”v\sigma_v \approx 0.003 \Delta v. At SNR = 50 dB: Οƒvβ‰ˆ0.001Ξ”v\sigma_v \approx 0.001 \Delta v.

So 1/1000-th resolution is achievable at high SNR β€” sub-mm/s velocity at automotive mmWave. This is what Chapters 13-14 exploit for fine-grained target tracking and sensing-assisted beamforming.

Example: Pedestrian Tracking Accuracy

OTFS-ISAC at W=100W = 100 MHz, T=3T = 3 ms, f0=77f_0 = 77 GHz. Pedestrian at SNR = 30 dB. Compute position-tracking accuracy per frame.

Solution
Resolution

Ξ”R=1.5\Delta R = 1.5 m, Ξ”v=0.65\Delta v = 0.65 m/s.

Super-resolution

CRLB at 30 dB: ΟƒR=1.5/2Ο€2β‹…1000\sigma_R = 1.5/\sqrt{2\pi^2 \cdot 1000} = 1.1 cm. Οƒv=0.65/2Ο€2β‹…1000\sigma_v = 0.65/\sqrt{2\pi^2 \cdot 1000} = 4.6 mm/s.

Frame rate

100 frames/sec. Averaging over 10 frames: further factor 10\sqrt{10} improvement. 3 mm range, 1.5 mm/s velocity.

Tracking quality

Position tracked to 3 mm, velocity to 1.5 mm/s β€” sufficient for gait analysis, fall detection, and high-precision positioning. All while the same waveform carries ~200 Mbps data.

Newton Refinement for Fractional Offset

Complexity: O(1)O(1) per Newton step
Input: Residual Y~\tilde{Y}, initial estimate (β„“^0,k^0)(\hat{\ell}_0, \hat{k}_0),
data XDDX_{DD}
Output: Refined (Ο΅(Ο„),Ο΅)(\epsilon^{(\tau)}, \epsilon) within cell
1. Initialize (Ο΅(Ο„),Ο΅)=(0,0)(\epsilon^{(\tau)}, \epsilon) = (0, 0).
2. for Newton step s=1,…,Ss = 1, \ldots, S do
3. \quad Compute local ambiguity surface values on a small grid.
4. \quad Fit quadratic to the peak: Ξ›β‰ˆAβˆ’B(Ο΅(Ο„)βˆ’xβˆ—)2βˆ’C(Ο΅βˆ’yβˆ—)2\Lambda \approx A - B(\epsilon^{(\tau)}-x_*)^2 - C(\epsilon-y_*)^2.
5. \quad Update: (Ο΅(Ο„),Ο΅)←(xβˆ—,yβˆ—)(\epsilon^{(\tau)}, \epsilon) \leftarrow (x_*, y_*).
6. end for
7. Return (Ο΅(Ο„),Ο΅)(\epsilon^{(\tau)}, \epsilon).

Quadratic fit is a second-order approximation of the thumbtack near its peak (reliable within the main lobe). After 2-3 Newton iterations, the refinement converges to the peak to machine precision. Total cost per target: ∼10\sim 10 multiplies.

⚠️Engineering Note

Compute Budget for OTFS-ISAC

Total OTFS-ISAC receiver compute budget at 5G NR-aligned parameters (MN=104MN = 10^4, 100 frames/sec):

  • OTFS demodulation (Wigner + SFFT): ∼105\sim 10^5 ops.
  • Channel/target estimation (embedded pilot + detection): ∼105\sim 10^5 ops.
  • Data detection (LCD, 3 iterations): ∼3Γ—105\sim 3 \times 10^5 ops.
  • Target refinement (Newton, 10 targets Γ— 3 iters): ∼104\sim 10^4 ops.
  • Iteration outer loop (2-3 joint iterations): 2-3Γ— above.

Total: ∼106\sim 10^6-10710^7 ops per frame = 10810^8-10910^9 ops/sec. Readily handled by modern SoC. For reference: OTFS data-only receiver is ∼106\sim 10^6 ops/frame β€” ISAC is 22-3Γ—3\times this budget.

Memory: ISAC needs additional buffers for the residual Y~\tilde{Y} and target parameter tables β€” ∼10Γ—MN\sim 10\times MN bytes, typically 100100 KB. Negligible.

Practical Constraints
  • β€’

    ISAC compute: 2-3Γ— OTFS-communications

  • β€’

    Memory: 10Γ— more than pure communications

  • β€’

    All fits in 5G SoC hardware

OTFS as the Natural ISAC WaveformISAC Tradeoffs: Complexity, PAPR, Doppler Resolution