</>EmbeddedInterview
← All problems · Signal Processing

Q15 Fixed-Point Multiply with Saturation

Hard

Many MCUs lack an FPU, so DSP code uses Q15 fixed point: an int16_t represents a value in [-1, 1) as value × 32768. Write:

  • int16_t q15_mul(int16_t a, int16_t b): the product, rounded to nearest, saturated to the Q15 range.
  • int16_t q15_add(int16_t a, int16_t b): the sum, saturated instead of wrapping.

Write your code on the right and press Run (or Ctrl + Enter). Hidden tests check your functions and print the result below the editor.

Multiply in 32 bits: the product of two Q15 numbers is Q30. Add half an LSB (1 << 14) for rounding, shift right by 15, then clamp to INT16_MIN..INT16_MAX.

#include <stdio.h>
#include <stdint.h>

static inline int16_t sat16(int32_t x)
{
    if (x > INT16_MAX) return INT16_MAX;
    if (x < INT16_MIN) return INT16_MIN;
    return (int16_t)x;
}

int16_t q15_mul(int16_t a, int16_t b)
{
    int32_t p = (int32_t)a * b;          /* Q30 */
    p += 1 << 14;                         /* round to nearest */
    return sat16(p >> 15);                /* back to Q15 */
}

int16_t q15_add(int16_t a, int16_t b)
{
    return sat16((int32_t)a + b);
}

The only product that overflows Q15 is −1 × −1 = +1, which cannot be represented, so it saturates to 0x7FFF. Saturation is preferred over wrap-around in signal processing because wrapping turns a slightly too-loud sample into a huge negative spike, which is audible and can destabilise control loops.

p >> 15 on a negative value relies on arithmetic right shift (implementation-defined but universal on GCC/Clang/Arm compilers). Cortex-M4 and later provide QADD, SSAT and SMULBB instructions (exposed through CMSIS intrinsics and CMSIS-DSP's arm_mult_q15) that do this in a cycle or two.

solution.c
OutputPress Run to compile and test your code.
Show the hidden tests
/* ---- tests ---- */
static int fails;
#define CHECK(c) do { if (!(c)) { printf("FAIL line %d: %s\n", __LINE__, #c); fails++; } } while (0)
#define Q15(x) ((int16_t)((x) * 32768.0))
int main(void)
{
    CHECK(q15_mul(Q15(0.5), Q15(0.5)) == Q15(0.25));
    CHECK(q15_mul(Q15(-0.5), Q15(0.5)) == Q15(-0.25));
    CHECK(q15_mul(INT16_MIN, INT16_MIN) == INT16_MAX);   /* -1 * -1 saturates */
    CHECK(q15_mul(INT16_MIN, INT16_MAX) == -32767);
    CHECK(q15_add(Q15(0.75), Q15(0.5)) == INT16_MAX);
    CHECK(q15_add(Q15(-0.75), Q15(-0.5)) == INT16_MIN);
    CHECK(q15_add(100, -50) == 50);
    puts(fails ? "Some tests failed" : "All tests passed");
    return fails != 0;
}