Digital Communications

DAST Code

Q: How does the DAST detector differ from a plain decorrelating detector?

A linear decorrelating detector inverts the code cross-correlation matrix R and makes a hard decision on each user independently, which fully removes multiple-access interference but amplifies noise by a factor proportional to the diagonal of R-inverse. DAST uses the decorrelator only as a soft front end: it forms the decorrelated statistics and an ordering, then builds a search tree where each level corresponds to one user's bit. Rather than committing to the noise-amplified hard decision, DAST explores the most promising branches and keeps the candidate sequence that minimizes the maximum-likelihood metric. This recovers most of the matched-filter-bound performance lost to noise enhancement, typically 2 to 4 dB at a bit error rate of 0.001 for a moderately loaded system, while staying far cheaper than an exhaustive maximum-likelihood search.

Q: What is the computational complexity of DAST compared with optimal maximum-likelihood detection?

Optimal maximum-likelihood multiuser detection requires evaluating 2 to the power K candidate sequences for K synchronous BPSK users, so its complexity grows exponentially and becomes impractical beyond roughly 15 to 20 users. DAST prunes the tree using the decorrelator ordering and a best-first or breadth-limited search, so its average complexity is polynomial in K, often modeled as order K-squared to K-cubed for the matrix operations plus a search cost that depends on the retained branch count M. For a 16-user system, exhaustive ML evaluates 65,536 hypotheses, whereas a DAST search with M equal to 8 retained paths typically evaluates a few hundred metric updates while staying within a few tenths of a dB of the ML bit error rate.

Q: Why does the decorrelator ordering improve the tree search?

The reliability of each decorrelated decision statistic varies with its effective signal-to-noise ratio, which depends on the corresponding diagonal element of the inverse cross-correlation matrix. By sorting users from most reliable to least reliable and placing the most reliable users at the top of the tree, DAST commits early to decisions that are almost certainly correct and reserves the costly branching for the ambiguous, low-reliability users near the leaves. This ordering is mathematically similar to the BLAST nulling-and-ordering principle and to the preprocessing used in sphere decoding; it dramatically reduces the number of nodes visited because the partial-path metrics stay tight, allowing aggressive pruning without discarding the true sequence.

/dast kohd/ (Decorrelating Adaptive Search Tree)

Short for Decorrelating Adaptive Search Tree, this is a near-optimal multiuser detection algorithm for CDMA receivers. A decorrelating front end first inverts the code cross-correlation matrix to produce soft, reliability-ranked decision statistics; the algorithm then builds a search tree, one level per active user, and explores only the most promising branches. By committing early to high-reliability users and branching only on ambiguous ones, DAST recovers 2 to 4 dB of the noise-enhancement loss that a hard matched filter bank suffers, landing within a few tenths of a dB of true maximum-likelihood detection while keeping complexity polynomial rather than exponential in the user count.

Category: Digital Communications

Complexity: ~O(K²) to O(K³)

BER gap to ML: < 0.5 dB

How the Decorrelating Adaptive Search Tree Works

Optimal multiuser detection in a synchronous code-division channel is a combinatorial optimization: given the bank of matched-filter outputs y and the K-by-K code cross-correlation matrix R, the receiver must find the bit vector b that maximizes the maximum-likelihood correlation metric. Evaluating all 2^K candidate vectors is the Verdu optimal detector, but its cost explodes beyond about 15 to 20 simultaneous users. DAST sidesteps the explosion by recasting the problem as a guided tree search rather than an exhaustive enumeration.

The "decorrelating" stage applies R⁻¹ to the matched-filter vector, which perfectly cancels multiple-access interference but amplifies the background noise. Instead of taking the sign of each decorrelated statistic as a final hard decision, DAST treats these statistics, and the reliability ranking that comes from the diagonal of R⁻¹, as guidance. Users are sorted from most reliable to least reliable and assigned to tree levels in that order. The "adaptive search" stage then walks the tree, retaining at most M partial paths per level by their accumulated metric, much like the M-algorithm used in sequential decoding.

Because the highest-reliability users sit near the root, their bits are almost always correct on the first branch, so the search spends its effort only where genuine ambiguity exists. This is the same nulling-and-ordering insight that underpins V-BLAST receivers and the preprocessing in sphere decoding: ordering tightens the partial-path metrics and lets the detector prune aggressively without discarding the true sequence.

Governing Relations

Matched-filter / decorrelator model:
y = R·A·b + n → b̂_dec = sgn(R⁻¹y)

ML metric maximized over the tree:
b̂ = arg max_b ( 2·b^TA·y − b^TA·R·A·b )

Decorrelator noise enhancement (user k):
η_k = [R⁻¹]_kk ≥ 1 (asymptotic efficiency = 1 / η_k)

R = code cross-correlation matrix, A = diagonal amplitude matrix, b = ±1 bit vector, n = noise, K = active users. Exhaustive ML evaluates 2^K hypotheses; DAST retains M paths per level for an average cost ≈ O(K²) preprocessing plus O(M×K) search.

Detector Comparison

Detector	Complexity (K users)	BER vs. single-user bound	Near-far resistance	Notes
Matched filter bank	O(K)	Poor under load	None	Conventional, interference-limited
Decorrelator (linear)	O(K³) (one R⁻¹)	2 to 4 dB loss from noise gain	Optimal	Hard decisions, no search
DAST tree search	~O(K²) to O(K³) + O(M·K)	< 0.5 dB from ML	Optimal	Reliability-ordered, M paths kept
Sphere decoding	Polynomial avg, exp. worst case	Exact ML	Optimal	Radius-bounded lattice search
Optimal ML (Verdu)	O(2^K)	Reference (best)	Optimal	Impractical beyond ~15 to 20 users

Common Questions

Frequently Asked Questions

How does the DAST detector differ from a plain decorrelating detector?

A linear decorrelator inverts R and makes an independent hard decision per user, fully removing multiple-access interference but amplifying noise by [R⁻¹]_kk. DAST uses the decorrelator only as a soft front end and reliability ranking, then searches a tree to keep the sequence minimizing the ML metric. This recovers roughly 2 to 4 dB at a BER of 0.001 in a moderately loaded system while staying far cheaper than exhaustive ML.

What is the computational complexity of DAST compared with optimal maximum-likelihood detection?

Optimal ML evaluates 2^K sequences and is impractical beyond about 15 to 20 users. DAST prunes via decorrelator ordering and a breadth-limited search, giving polynomial average cost: roughly O(K²) to O(K³) for the matrix work plus an O(M×K) search. A 16-user case where ML tests 65,536 hypotheses is handled by DAST with M = 8 in a few hundred metric updates, within a few tenths of a dB of the ML BER.

Why does the decorrelator ordering improve the tree search?

Each decorrelated statistic's reliability scales with its effective SNR, set by the diagonal of R⁻¹. Sorting users most-reliable-first puts near-certain decisions at the top of the tree and reserves branching for ambiguous, low-reliability users near the leaves. This is the same nulling-and-ordering principle as V-BLAST and sphere-decoding preprocessing; it keeps partial-path metrics tight and lets DAST prune hard without losing the true sequence.

Related Terms

← DARPA Data Association →

Digital Receiver Front Ends

Build a Cleaner Signal Chain

Advanced multiuser detectors like DAST only deliver their gain behind a low-noise, well-matched front end. RF Essentials supplies the LNAs, frequency converters, and integrated assemblies that feed your CDMA and MIMO receiver DSP.

Get in Touch