Flexible Sweep

This experiment is a refinement of my Detecting Frame Rates Experiment. For a more precise measurement of my DSLR’s video frame rate, I need to generate sweeps with somewhat high frequency resolution. Although this seems a simple requirement it has significant implications.

Here are my design considerations.

First of all I can not use the reset switch for mode switching anymore. I decided to resolve this by setting the frequency through the serial monitor. It follows the resulting setup will not be able to run standalone anymore. This is not an issue for me.

The next thing is that I wanted a frequency resolution of 0.0001 Hz and a range from 0 Hz to 999.9999 Hz. Notice that for the fastest frequency of 999.9999 Hz the resolution is 0.1 ppm. Since my crystal deviation and experiments I am more than aware that his is somewhat pointless. However for frequencies around 30 Hz the resolution is about 3-4 ppm. This is in the order of magnitude of the crystal’s precision. Also I wanted to have some head room in case I will use this setup for other experiments.

Now how does this translate into code?

//
//  www.blinkenlight.net
//
//  Copyright 2012 Udo Klein
//
//  This program is free software: you can redistribute it and/or modify
//  it under the terms of the GNU General Public License as published by
//  the Free Software Foundation, either version 3 of the License, or
//  (at your option) any later version.
//
//  This program is distributed in the hope that it will be useful,
//  but WITHOUT ANY WARRANTY; without even the implied warranty of
//  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
//  GNU General Public License for more details.
//
//  You should have received a copy of the GNU General Public License
//  along with this program. If not, see http://www.gnu.org/licenses/

// TRICK17 is a macro that just repeats its argument.
// From the point of view of the C / C++ language
// TRICK17 does nothing at all. However it tricks
// the Arduino IDE. That is whatever is wrapped by
// the trick macro will not be recognized as a function.
// This in turn will disable the auto prototyping of
// the IDE. Thus it becomes possible to use self 
// defined types in functions signatures without
// refraining to additional files.
// If something comes up with a better name for this
// trick I would be more than happy to use this name.
#define TRICK17(x) x

uint32_t power_of_ten(uint8_t exponent) {
    uint32_t result = 1;
    
    while (exponent > 0) {
        --exponent;
        result *= 10;
    }
    return result;
}

typedef uint32_t fixed_point;

// notice 2^32 = 4 294 967 296 ~ 4*10^9
// 10^3*10^4*phases = 1.6 * 10^8 ==> fits into uint32_t
// ==> At most one more digit might be possible but we will not push this to the limits.
//     It is somewhat pointless anyway because we are right now at the edge of reasonable
//     precision.

const uint8_t max_integer_digits    = 3;
const uint8_t max_fractional_digits = 4;
// constant value for the number 1 in a fixed point represenation with
// max_fractional_digits behind the dot
const fixed_point fixed_point_1 = (fixed_point)power_of_ten(max_fractional_digits);


char get_next_available_character() {
    while (!Serial.available()) {}
    
    return Serial.read();
}

TRICK17(fixed_point parse()) {
    const char decimal_separator     = '.';
    const char terminator[] = " \t\n\r";
  
    enum parser_state { parse_integer_part                = 0,
                        parse_fractional_part             = 1,
                        error_duplicate_decimal_separator = 2, 
                        error_invalid_character           = 3,
                        error_missing_input               = 4,
                        error_to_many_decimal_digits      = 5,
                        error_to_many_fractional_digits   = 6 };
                          
    while (true) {

        fixed_point value = 0;
        uint8_t parsed_digits = 0;        
        parser_state state = parse_integer_part;
    
        while (state == parse_integer_part || state == parse_fractional_part) {
        
            const char c = get_next_available_character();        
            if (c == decimal_separator) {
                if (state == parse_integer_part) { 
                   state = parse_fractional_part;
                   parsed_digits = 0;
                } else {
                    state = error_duplicate_decimal_separator;
                }
            } else             
            if (strchr(terminator, c) != NULL) {
                if (state == parse_integer_part && parsed_digits == 0) {
                    state = error_missing_input;
                } else {
                    return value * (fixed_point)power_of_ten(max_fractional_digits - (state == parse_integer_part? 0: parsed_digits));                                                     
                }
            } else            
            if (c >= '0' and c <= '9') {
                ++parsed_digits;
                value = value * 10 + c - '0';                                     
                if (state == parse_integer_part && parsed_digits > max_integer_digits) {
                    state = error_to_many_decimal_digits;
                } else
                if (state == parse_fractional_part && parsed_digits > max_fractional_digits) {
                    state = error_to_many_fractional_digits;
                }                                
            } else {
                state = error_invalid_character;
            }        
        }
        Serial.print(F("Error: "));
        Serial.println(state);
    }    
}


const uint8_t phases = 16;
const uint64_t system_clock_frequency = ((uint64_t)F_CPU) * fixed_point_1;
const fixed_point default_frequency = 1 * fixed_point_1;  // 1 Hz

const uint16_t delay_block_tick_size = 30000; // must be below 2^15-1 in order for tail ticks to fit into uint16_t
// total delay time will be delay_block_tick_size * delay_blocks + tail_ticks + nominator/denominator
volatile uint32_t delay_blocks = 0;
volatile uint16_t tail_ticks   = 1000;  // will always be <= 2*delay_block_tick_size
volatile fixed_point denominator = 1;
volatile fixed_point nominator = 0;
volatile boolean reset_timer = true;

void advance_phase() {
    const uint8_t max_led = 19;
  
    static uint8_t phase = max_led;
    static uint8_t next_phase = max_led-1;
    
    digitalWrite(phase, LOW);    
    digitalWrite(next_phase, HIGH);
    
    phase = next_phase;    
    next_phase = next_phase > max_led - phases + 1? next_phase - 1: max_led;  
}

void set_timer_cycles(uint16_t cycles) {    
    OCR1A = cycles - 1;
}

ISR(TIMER1_COMPA_vect) {
    // To decrease phase jitter "next_phase" is always precomputed.
    // Thus the start of the ISR till the manipulation of the IO pins 
    // will always take the same amount of time.
       
    static uint32_t blocks_to_delay;
    static fixed_point accumulated_fractional_ticks;

    if (reset_timer) {
        reset_timer = false;
        
        blocks_to_delay = 0;
        accumulated_fractional_ticks = 0;
    }

    if (blocks_to_delay == 0) {    
        advance_phase();              
        
        blocks_to_delay = delay_blocks;
        if (blocks_to_delay > 0) {
            set_timer_cycles(delay_block_tick_size);          
        }        
    } else {
        --blocks_to_delay;
    }
        
    if (blocks_to_delay == 0) {
        accumulated_fractional_ticks += nominator;
        if (accumulated_fractional_ticks < denominator) {                
            set_timer_cycles(tail_ticks);
        } else {
            set_timer_cycles(tail_ticks+1);
            accumulated_fractional_ticks -= denominator;
        }              
    }     
}

TRICK17(void set_target_frequency(const fixed_point target_frequency)) {

    // total delay time will be delay_block_tick_size * delay_blocks + tail_ticks + nominator/denominator  
    cli();

    // compute the integer part of the period length "delay_ticks" as well as its fractional part "nominator/denominator"
    denominator = target_frequency * phases;       
    uint64_t delay_ticks = system_clock_frequency / denominator;    
    nominator = system_clock_frequency - delay_ticks * denominator;
 
    // break down delay_ticks in chunks that can be handled with a 16 bit timer   
    delay_blocks = delay_ticks / delay_block_tick_size;
    tail_ticks   = delay_ticks - delay_block_tick_size * delay_blocks;
    if (delay_blocks > 0) {
        // enforce that tails are always longer than 1000 ticks
        --delay_blocks;
        tail_ticks += delay_block_tick_size;
    }
        
    // tell the timer ISR to reset its internal values
    reset_timer = true;

    sei();    
    
    // attention: the target frequency is fixed_point but output is uint32_t
    Serial.print(F("target frequency: ")); Serial.println(target_frequency); 
    /*
    // debugging only
    Serial.print(F("denominator: ")); Serial.println(denominator); 
    Serial.print(F("nominator: ")); Serial.println(nominator); 
    Serial.print(F("delay ticks: ")); Serial.print((uint32_t)delay_ticks); 
    Serial.print(','); Serial.println((uint32_t)(delay_ticks>>32)); 
    Serial.print(F("delay blocks: ")); Serial.println(delay_blocks);     
    Serial.print(F("tail ticks: ")); Serial.println(tail_ticks);     
    /**/
};


void setup() {
    DDRD = 0b11111111; // set digital  0- 7 to output
    DDRB = 0b00111111; // set digital  8-13 to output
    DDRC = 0b00111111; // set digital 14-19 to output (coincidences with analog 0-5)

   Serial.begin(115200);

    // disable timer0 interrupts to stop Arduino timer functions
    // from introducing jitter in our output
    TIMSK0 = 0;

    // disable timer1 interrupts
    TIMSK1 = 0;

    // do not toggle or change timer IO pins
    TCCR1A = 0;
    // Mode 4, CTC using OCR1A | set prescaler to 1
    TCCR1B = (1<<WGM12) | (1<<CS10);

    set_target_frequency(default_frequency);

    // enable match interrupts
    TIMSK1 = 1<<OCIE1A;    
    
}

void loop() { 
    set_target_frequency(parse());    
}

This looks somewhat complicated, so let us take it into pieces one by one. As I already mentioned I need to set the target frequency. This is the only thing that I will do in the main loop. All of the rest will be interrupt driven.

First of all I need to parse the input from serial. The result will be a “fixed_point” integer. Technically this is an uint32_t but semantically it is a fixed point number with 4 digits after the radix point. Thus I defined this as a type. Unfortunately this can not be used straightforward with function definitions. This is a limitation that is imposed by the Arduino IDE. In order to make it easier for beginners the IDE will extract functions and auto-generate prototypes for them. In plain C you would have to do this on your own. Unfortunately the IDE is not clever enough to account for newly defined types. It sorts all the function definitions to the front. Thus the compiler will complain because it does not yet know the desired type when it tries to compile the prototypes.

In order to trick the IDE to not generate any prototypes I use a special macro “TRICK17″. In Germany “Trick 17″ always denotes an uncommon/unexpected solutions that actually works. In case the uncommon solution does not work this is sometimes called “Trick 17b” ;)

The TRICK17 macro just repeats its argument. The point is that this changes the pattern of the function definitions such that the IDE will not pick them up anymore. Thus it will generate no prototypes. Thus I will have no prototypes. Since I took care to order the functions properly this creates no issues whatsoever. Otherwise I could have used TRICK17 for prototype definitions as well.

With other words

TRICK17(fixed_point parse()) {

will not be touched by the IDE. But for the compiler it looks like

fixed_point parse() {

How does the parser then parse the input? Conceptually the parser is implemented as a state machine. That is it is always in one of several states. Whenever a character is received it will evaluate it and change its state accordingly. See the diagram how the different states interact.

Except for the extensive error handling the parser will just collect digits. Once it receives the terminator character it will add as many trailing zeros as needed to adjust the radix point. Then it will return the desired value.

Now we come to the frequency generation part. This is slightly tricky. The easiest part is the advance_phase() function. Whenever it is called it will cycle to the next LED. After 16 calls it will repeat from where it started. In order to reach a given target frequency it thus must be called at 16 times the desired frequency.

So the ISR(TIMER1_COMPA_vect) should call it with the desired frequency. There are some challenges linked with this. First of all I support very low frequencies. So 2^16 cycles may not be sufficient to delay 1/16 period. Thus the timer will be set for 30 000 ticks (which I call a block). The ISR will process the desired number of blocks to make up for a long enough initial delay. Once the blocks are done it will process a final block of suitable length the reach the total delay. If you look closely there is some magic going on which will extend the last block by one clock cycle every once in a while. This “magic” is also known as Bresenham’s algorithm. Basically this allow me to add “fractional clock cycles”. That is on average my solution will not get out of phase. However since there are no “factional clock cycles” this will add some jitter / phase noise. But for my applications I prefer long term accuracy over low phase noise / jitter. (Of course I know this is overdoing it because the crystal is actually the limiting factor).

The set_target_frequency() function computes all the values required for the ISR. It also ensures that the last block is always longer than 1000 ticks. This can be guaranteed because no period will be shorter than 1000 ticks. On the other hand no period will be longer than 30000 ticks. So it can always combine the tail ticks with the last of the 30000 ticks blocks (if there exists any). Since 2*30000 < 2^16 this can always be handled by the timer.

Quite a lot code. Now have a look how it can be used to really nail down the frame rate of my camera.

Here is what happens. First you can see that the sketch will start to generate a 1 Hz signal. This is just for verification purposes. As you can see with the frequency counter the crystal is 19 ppm to fast. This is within the expected bounds.

13 seconds in the video I switch to 30 Hz. You can see that there is one LED that is dark. This dark spot wanders slowly. This is because the camera’s frame rate is below 30 Hz. Of course this is what we expect. At 31 seconds I switch down to 29.9 Hz. You can see that the spot will change direction, obviously the camera is faster than 29.9 Hz. Then at 50 seconds I switch to 29.97 Hz and the dark sport stops in place. It follows that the frame rate is 29.97 Hz. So my conclusions from previous month were wrong. The camera is running at a 29.97 Hz frame rate which is quite common. However it does definitely not run at the advertised 30 Hz.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s