Timer prescaler and clock division in Embedded C - Time & Space Complexity

Time Complexity: Timer prescaler and clock division

O(n)

Understanding Time Complexity

When using timers in embedded C, the prescaler changes how fast the timer counts. This affects how many steps the timer takes for a given time.

We want to understand how the timer's counting speed changes as we adjust the prescaler.

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

// Set timer prescaler
void Timer_SetPrescaler(int prescaler) {
    TIMER->PSC = prescaler;  // Prescaler register
    TIMER->CNT = 0;          // Reset counter
    TIMER->CR1 |= 1;         // Enable timer
}

// Wait for timer to reach a value
void Timer_Wait(int target) {
    while (TIMER->CNT < target) {
        // wait
    }
}
    

This code sets a prescaler to slow down the timer clock and waits until the timer counter reaches a target value.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: The while loop in Timer_Wait repeatedly checks the timer counter.
• How many times: The loop runs until the timer counter reaches the target value, which depends on the target.

How Execution Grows With Input

The number of loop checks grows roughly with the target value.

Input Size (target)	Approx. Loop Checks
10	About 10
100	About 100
1000	About 1000

Pattern observation: Increasing the target increases loop checks linearly. The prescaler slows the timer clock but does not increase the number of loop iterations.

Final Time Complexity

Time Complexity: O(n)

This means the waiting time grows linearly with the target count, but the prescaler slows the timer, effectively reducing the speed of counting.

Common Mistake

[X] Wrong: "The prescaler changes the time complexity class of the timer wait loop."

[OK] Correct: The prescaler only changes the speed of counting, not how the number of steps grows with the target. The loop still grows linearly with the target value.

Interview Connect

Understanding how timer prescalers affect counting speed helps you reason about delays and timing in embedded systems, a key skill for real-world device programming.

Self-Check

"What if we changed the waiting condition to check for an interrupt flag instead of polling the counter? How would the time complexity change?"

Practice

1. What is the main purpose of a timer prescaler in embedded C programming?

easy

A. To generate an interrupt on every clock cycle

B. To increase the CPU clock speed

C. To divide the main clock frequency and slow down the timer counting

D. To reset the timer counter automatically

Solution

1. Step 1: Understand the role of a prescaler

   A prescaler divides the main clock frequency to slow down the timer's counting speed.

2. Step 2: Compare options with prescaler function

   Only To divide the main clock frequency and slow down the timer counting correctly describes this function; others describe unrelated timer features.

3. Final Answer:

   To divide the main clock frequency and slow down the timer counting -> Option C

4. Quick Check:

   Prescaler divides clock = To slow timer [OK]

Hint: Prescaler always divides clock to slow timer [OK]

Common Mistakes:

• Confusing prescaler with timer reset
• Thinking prescaler speeds up the clock
• Assuming prescaler triggers interrupts

2. Which of the following is the correct way to set a prescaler value of 8 for a timer in embedded C?

easy

A. TCCR0 |= (1 << CS01);

B. TCCR0 |= (1 << CS00);

C. TCCR0 |= (1 << CS02);

D. TCCR0 |= (1 << CS01) | (1 << CS00);

Solution

1. Step 1: Recall prescaler bits for timer0

   For prescaler 8, only bit CS01 must be set.

2. Step 2: Match bits to options

   TCCR0 |= (1 << CS01); sets CS01 bit, correctly configuring prescaler 8.

3. Final Answer:

   TCCR0 |= (1 << CS01); -> Option A

4. Quick Check:

   Prescaler 8 = CS01 set only [OK]

Hint: Check datasheet bits for prescaler values [OK]

Common Mistakes:

• Setting multiple bits for prescaler 8
• Confusing bit positions for prescaler values
• Using wrong register for timer control

3. Given a microcontroller clock of 16 MHz and a timer prescaler set to 64, what is the timer tick frequency?

medium

A. 1,000,000 Hz

B. 250,000 Hz

C. 16,000,000 Hz

D. 64 Hz

Solution

1. Step 1: Calculate timer tick frequency

   Timer tick frequency = CPU clock / prescaler = 16,000,000 / 64 = 250,000 Hz.

2. Step 2: Compare with options

   250,000 Hz matches the calculated frequency exactly.

3. Final Answer:

   250,000 Hz -> Option B

4. Quick Check:

   16MHz/64 = 250kHz [OK]

Hint: Divide clock by prescaler for tick frequency [OK]

Common Mistakes:

• Multiplying instead of dividing clock by prescaler
• Using wrong prescaler value
• Confusing frequency units

4. Identify the error in this code snippet setting a prescaler of 256 for Timer1:

  TCCR1B = (1 << CS12) | (1 << CS10);

medium

A. CS12 bit is missing

B. No error, code is correct

C. TCCR1B register is incorrect for prescaler

D. CS10 should not be set for prescaler 256

Solution

1. Step 1: Check prescaler bits for 256 on Timer1

   Prescaler 256 requires only CS12 bit set; CS10 must be cleared.

2. Step 2: Analyze given code

   Code sets both CS12 and CS10 bits, which corresponds to prescaler 1024, not 256.

3. Final Answer:

   CS10 should not be set for prescaler 256 -> Option D

4. Quick Check:

   Prescaler 256 = only CS12 set [OK]

Hint: Only set bits matching prescaler exactly [OK]

Common Mistakes:

• Setting extra bits causing wrong prescaler
• Confusing prescaler bit combinations
• Assuming code is correct without checking datasheet

5. You want to measure a 1-second delay using a 16-bit timer with a 16 MHz clock. Which prescaler value should you choose to make the timer count up to 1 second without overflow? (Timer max count = 65535)

hard

A. Prescaler 1024

B. Prescaler 64

C. Prescaler 128

D. Prescaler 8

Solution

1. Step 1: Calculate timer tick frequency for each prescaler

   Tick frequency = 16,000,000 / prescaler. For 1024: 16,000,000 / 1024 ≈ 15,625 Hz.

2. Step 2: Calculate max timer duration

   Max duration = max count / tick frequency = 65535 / 15,625 ≈ 4.19 seconds, which covers 1 second.

3. Step 3: Check smaller prescalers

   Prescaler 128 gives 125,000 ticks per second, 64 gives 250,000, and 8 gives 2,000,000--all exceeding 65,535, causing overflow before 1 second.

4. Final Answer:

   Prescaler 1024 -> Option A

5. Quick Check:

   Prescaler 1024 allows 1s count without overflow [OK]

Hint: Choose prescaler so max count ≥ ticks in 1 second [OK]

Common Mistakes:

• Ignoring timer max count limit
• Choosing prescaler too small causing overflow
• Not calculating ticks per second correctly