CDMA Decoder: Deep Dive into Spread-Spectrum Decoding

CDMA (Code Division Multiple Access) is a spread-spectrum technique where multiple users share the same frequency and time, but are separated by code. Each transmitter multiplies its data bit (+1 or -1) with a pseudo-random chip sequence. The receiver sees the sum of all active users. Decoding works because each satellite code is almost orthogonal to the others: the correct code-phase alignment yields a strong correlation peak, while wrong satellites/phases stay near zero.

Mathematically, the receiver computes a circular cross-correlation: R(s, o) = Σ c[i] * g_s[(i + o) mod L], where c[i] is the incoming chip sequence, g_s is satellite s's Gold code, o is code phase offset, and L = 1023. In this project, a satellite is declared active when |R(s, o)| exceeds a threshold. The sign of R maps to the transmitted bit (positive => bit 1, negative => bit 0).

This repository implements the same decoder in three variants: C++ reference, C unoptimized, and C optimized. They all target the same problem: identify active satellites, decoded bit values, and code-phase offsets from one GPS-style frame.

The correlation landscape below shows all 24 satellites across all 1023 offsets. Most values cluster near zero. The decoded satellites stand out as strong positive/negative peaks with large margin above threshold.

For deeper exploration, the interactive version is embedded here. It allows zooming and hovering over any satellite/offset pair:

C++ reference implementation

The C++ version keeps the design clean and close to the algorithm: generate one Gold sequence per satellite, correlate over offsets, and stop on the first valid peak for that satellite.

const uint16_t peak = sequence.size() - MAX_DEVIATION * (satelliteCount - 1);
for (size_t offset = 0; offset < sequence.size(); ++offset) {
    int32_t sum = 0;
    for (size_t i = 0; i < sequence.size(); ++i) {
        const size_t index = (i + offset) % sequence.size();
        sum += sequence[index] ? chipSequence[i] : -chipSequence[i];
    }
    if (std::abs(sum) > peak) {
        // satellite detected, bit is sign(sum), offset is code phase
        break;
    }
}

Gold code generation in C++ uses two 10-bit shift registers and XOR taps:

bool motherFirst = motherSequences.first.back();
bool motherSecond =
    motherSequences.second[registerSumIndices.first] ^
    motherSequences.second[registerSumIndices.second];
sequence.push_back(motherFirst ^ motherSecond);

C unoptimized implementation

The unoptimized C variant is a direct procedural port of the C++ logic. It explicitly allocates all 24 generated sequences and then performs the same modulo-based circular correlation loop.

bool* sequences[NUM_SATELLITES];
for (i = 0; i < NUM_SATELLITES; i++) {
    sequences[i] = malloc(CHIP_SEQUENCE_LENGTH * sizeof(bool));
    CDMA_GenerateSequence(sequences[i], CHIP_SEQUENCE_LENGTH, i);
}
CDMA_decode(sequences, chipSequence, maxElement, correlationResults);

for (offset = 0; offset < CHIP_SEQUENCE_LENGTH; offset++) {
    int32_t accumulatedSum = 0;
    for (i = 0; i < CHIP_SEQUENCE_LENGTH; i++) {
        size_t index = (i + offset) % CHIP_SEQUENCE_LENGTH;
        accumulatedSum += (sequence[index] ? chipSequence[i] : -chipSequence[i]);
    }
}

C optimized: what was optimized and why it matters

The optimized C version focuses on CPU and memory efficiency while preserving decoder behavior:

• Precomputed Gold sequences: runtime sequence generation is removed.
• Doubled sequence layout: each code is stored with length 2*L, so offset access avoids modulo in the inner loop.
• Pointer-based access: contiguous reads improve locality and reduce indexing overhead.
• Early exit: decoding stops once expected active satellites are found.

if (numCorrelationsFound == numSendingSatellites) {
    break; // early exit
}
const int32_t* goldSequencesPtr =
    (const int32_t*)goldSequences + j * 2 * CHIP_SEQUENCE_LENGTH;
for (offset = 0; offset < CHIP_SEQUENCE_LENGTH; ++offset) {
    int32_t accumulatedSum = 0;
    for (i = 0; i < CHIP_SEQUENCE_LENGTH; ++i) {
        accumulatedSum += goldSequencesPtr[i + offset] * chipSequence[i];
    }
}

Visualization and validation

To explain decoder behavior, I built a Python visualization pipeline that reconstructs all Gold sequences, computes the full correlation matrix, marks detections, and verifies parity against executable output.

chip = load_chip_sequence("C++/gps_sequence.txt")
sender_count = np.max(np.abs(chip))
threshold = 1023 - 65 * (sender_count - 1)
seqs = generate_all_gold_sequences(1023)
corr = correlation_landscape(chip, seqs)
detections = detect_from_landscape(corr, threshold)

This makes the project transparent from theory to implementation: you can trace every decoded satellite bit back to a concrete correlation peak and compare algorithmic trade-offs across C++, C unoptimized, and C optimized versions.