Fixed-Point Arithmetic (Q Notation)

1. Why Not Just Use float?

In desktop or server-side programming, using float or double for fractional numbers is the default. However, in the embedded world, especially on cost-sensitive microcontrollers, this is often not a viable option.

There are three primary reasons for this:

1. Cost and Power: Many microcontrollers, particularly low-power or low-cost ones, do not include a hardware Floating-Point Unit (FPU). Adding one increases the silicon die size, cost, and power consumption.
2. Performance: If there's no FPU, floating-point operations must be emulated in software using library functions. These software routines are orders of magnitude slower than native integer instructions.
3. Determinism: Integer arithmetic operations typically have a fixed, predictable execution time, which is critical for real-time systems. Floating-point operations, especially in software, can have variable timing.

This is where fixed-point arithmetic becomes an essential tool. It allows us to perform fractional math using only the processor's native integer hardware.

2. Fixed-Point Representation: The "Q" Notation

The core idea of fixed-point is simple: we take an integer data type (like int32_t) and pretend there's an imaginary binary point somewhere within its bits. The bits to the left of this point represent the integer part, and the bits to the right represent the fractional part.

This format is commonly described using Q notation. A number in Qm.n format has:

• m bits for the integer part.
• n bits for the fractional part.
• The total number of bits is m + n. For signed numbers using two's complement, the most significant bit of the integer part serves as the sign bit.

A common format is Q15.16 for a 32-bit signed integer. This gives us:

• 1 sign bit.
• 15 integer bits.
• 16 fractional bits.

This provides an integer range of approximately [-32768, 32767] and a fractional precision of 2^-16 (about 0.000015).

3. Conversions

To work with fixed-point numbers, you need to convert back and forth between standard integer/float types and your fixed-point representation. Let's assume we're using a Q15.16 format with a int32_t, where the number of fractional bits (n) is 16.

Here's a summary of the operations, which we can implement as C macros for convenience. Let FRAC_BITS = 16.

• Integer to Fixed-Point: We shift the integer left to place it in the integer part of the fixed-point number.
  fixed_val = integer_val << FRAC_BITS;

• Float to Fixed-Point: We multiply the float by 2^n to scale it up, then cast to an integer.
  fixed_val = (int32_t)(float_val * (1 << FRAC_BITS));

• Fixed-Point to Integer: We shift right to discard the fractional part.
  integer_val = fixed_val >> FRAC_BITS;

• Fixed-Point to Float: We cast the fixed-point number to a float and divide by 2^n to scale it back down.
  float_val = (float)fixed_val / (1 << FRAC_BITS);

4. Basic Arithmetic Operations

Now for the core of the lesson: implementing the arithmetic.

Addition and Subtraction

This is the simplest case. If two fixed-point numbers share the same Q format, their binary points are aligned. This means you can add or subtract their underlying integer representations directly.

// a and b are fixed-point numbers of the same Q format
fixed_t result = a + b;
fixed_t result = a - b;

Interview Gotcha: What happens if you add a fixed-point number and a raw integer?
fixed_t c = FTOFIX(20.0f); int a = 10; fixed_t result = c + a;
The result will be incorrect. The raw integer 10 is treated as a very small fractional value because its bits occupy the lowest part of the number. You must first convert the raw integer to the fixed-point format: fixed_t result = c + ITOFIX(a);.

Multiplication

Multiplication is where it gets interesting and is a favorite interview topic. When you multiply two fixed-point numbers, their scaling factors also get multiplied.

Let a_fix = A * 2^n and b_fix = B * 2^n.
If we just multiply them: a_fix * b_fix = (A * B) * 2^(2n).

The result is scaled by 2^(2n), not 2^n. To correct this, we must right-shift the product by n.

There's another critical detail. Multiplying two n-bit numbers can result in a 2n-bit product. If we multiply two int32_t values, the result can require up to 64 bits. If you perform the multiplication using only int32_t, you will likely overflow and get a wrong result.

The correct procedure for multiplying two 32-bit fixed-point numbers is:

1. Cast both operands to a 64-bit integer type (int64_t).
2. Perform the multiplication to get a 64-bit intermediate product.
3. Right-shift the 64-bit product by FRAC_BITS to rescale it.
4. Cast the result back to a 32-bit fixed-point number.

5. C Implementation and Practical Example

Let's put this all together in a practical C implementation and apply it to a common embedded scenario.

5.1 Fixed-Point Library

Here is a minimal set of definitions and functions for a Q15.16 fixed-point system.

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

// Use a 32-bit signed integer for our fixed-point type.
typedef int32_t fixed_t;

// Define the number of fractional bits.



#define FRAC_BITS 16

// Conversion macros



#define INT_TO_FIXED(x) ((fixed_t)((x) << FRAC_BITS))
#define FLOAT_TO_FIXED(x) ((fixed_t)((x) * (1 << FRAC_BITS)))
#define FIXED_TO_INT(x) ((x) >> FRAC_BITS)
#define FIXED_TO_FLOAT(x) ((float)(x) / (1 << FRAC_BITS))

// Arithmetic functions
// Addition and subtraction can be done directly with '+' and '-'

// Fixed-point multiplication
fixed_t fixed_mul(fixed_t a, fixed_t b) {
    // Use a 64-bit intermediate to prevent overflow
    int64_t temp = (int64_t)a * (int64_t)b;
    // Rescale the result
    return (fixed_t)(temp >> FRAC_BITS);
}

5.2 Use Case: ADC Voltage Conversion

A classic embedded task is reading a value from an Analog-to-Digital Converter (ADC) and converting it to a real-world unit, like voltage.

Imagine you have a 12-bit ADC with a 3.3V reference voltage. A raw reading of 2048 would correspond to:
Voltage = (2048 / 4095.0) * 3.3V = 1.6508V

Let's perform this calculation using our fixed-point library, completely avoiding floating-point math at runtime.

int main() {
    // --- Setup constants ---
    // These conversions would happen once at initialization, or even be pre-calculated
    // and stored as constants in your code.
    const fixed_t V_REF = FLOAT_TO_FIXED(3.3); // Reference voltage 3.3V
    const fixed_t ADC_MAX = INT_TO_FIXED(4095); // Max 12-bit ADC value

    // --- Runtime calculation ---
    uint16_t adc_raw_reading = 2048;
    
    // Convert the raw reading to a fixed-point number
    fixed_t adc_fixed = INT_TO_FIXED(adc_raw_reading);

    // To perform (A / B) * C, it's better to do (A * C) / B to preserve precision.
    // However, our fixed_mul function already handles the rescaling. A direct division
    // is more complex. So, let's restructure for multiplication.
    // We want to calculate: adc_fixed * (V_REF / ADC_MAX)
    // The term (V_REF / ADC_MAX) is a scaling factor.
    
    // For division: `a / b`, we do `(a << FRAC_BITS) / b`
    int64_t temp_scaled_vref = (int64_t)V_REF << FRAC_BITS;
    fixed_t scaling_factor = (fixed_t)(temp_scaled_vref / 4095);

    // Now, multiply the reading by the scaling factor
    fixed_t voltage_fixed = fixed_mul(adc_fixed, scaling_factor);

    printf("Raw ADC Reading: %u\n", adc_raw_reading);
    printf("Fixed-point Voltage: %d (internal representation)\n", voltage_fixed);
    printf("Calculated Voltage: %fV\n", FIXED_TO_FLOAT(voltage_fixed));

    // --- For comparison, the floating point calculation ---
    float voltage_float = ((float)adc_raw_reading / 4095.0f) * 3.3f;
    printf("Floating-point Voltage: %fV\n", voltage_float);

    return 0;
}

Output:

Raw ADC Reading: 2048
Fixed-point Voltage: 108179 (internal representation)
Calculated Voltage: 1.650787V
Floating-point Voltage: 1.650806V

As you can see, the result is extremely close to the floating-point calculation, but achieved using only integer arithmetic. The small difference is due to the inherent precision limits of the chosen fixed-point format.

Conclusion

In this lesson, you've mastered a technique that is fundamental to high-performance, low-cost embedded systems. You can now confidently explain and implement fixed-point arithmetic, a skill that signals strong foundational knowledge in an interview setting.

Key Takeaways:

• Fixed-point arithmetic is a method to perform fractional math using only integer operations, which is crucial for systems without a hardware FPU.
• The Q notation (Qm.n) defines the trade-off between the integer range (m bits) and fractional precision (n bits).
• Addition and subtraction are straightforward integer operations if the Q format is consistent.
• Multiplication requires special handling: using a wider intermediate data type (e.g., int64_t for int32_t operands) to prevent overflow, followed by a right-shift to rescale the result.

Preview of the Next Lesson:

We will continue our focus on resource-constrained algorithms. In the next lesson, you will implement in-place heapsort and analyze its guaranteed O(1) auxiliary space complexity versus quicksort's worst-case. This is another classic algorithm that is highly relevant to embedded systems where both memory and predictability are paramount.