Why does a Microcontroller Programmer Need Diophantine Equations?

Prologue

In mathematics there is such a topic as Diophantine equations. In their simplest form they look like this.

$ax+by=d \qquad \qquad\qquad (1)$

There is one equation and two unknowns: x,y. In this case, a, b, d are known constants.

At first glance it may seem like a useless gimmick for MCU programming, but that’s not the case.

When programming a microcontroller, the first thing you have to do is configure the clocking of the processor core. The clocking is controlled by the phase-locked loop (PLL) subsystem of the SoC(a).

And there you need to select three constants: M, N and F. In the Artery microcontroller, this electrical circuit looks like this.

According to formula (2)

$\frac{(N\frac{F_{quartz}}{M}) } {F} = F_{sys} \qquad \qquad (2)$

The system frequency F_sys is calculated. This equation transforms into (3)

$F_{quartz} \frac{N}{M} -F_{sys}F = 0 \qquad \qquad (3)$

And equation (3) is a real Diophantine equation. Here F_quartz – this is the frequency of the quartz resonator, which is set by the circuitry of the electronic board.
F_sys set by the programmer to achieve the desired firmware performance. The remaining integer unknowns are N, M and F.

Further restrictions are imposed by the microcontroller manufacturer. For Artery it's

Variable	Minimum	Maximum
M	1	15
N	31	500
FR (powers of two)	1	32

This is even written in the C source code provided by the manufacturer.


/**
  *    config crm pll
  *                        pll_rcs_freq * pll_ns
  *         pll clock = --------------------------------
  *                           pll_ms * pll_fr_n
  *         attemtion:
  *                  31 <= pll_ns <= 500
  *                  1  <= pll_ms <= 15
  *
  *                       pll_rcs_freq
  *         2mhz <=  ---------------------- <= 16mhz
  *                          pll_ms
  *
  *                       pll_rcs_freq * pll_ns
  *         500mhz <=  -------------------------------- <= 1200mhz
  *                               pll_ms
  * @param  clock_source
  *         this parameter can be one of the following values:
  *         - CRM_PLL_SOURCE_HICK
  *         - CRM_PLL_SOURCE_HEXT
  * @param  pll_ns (31~500)
  * @param  pll_ms (1~15)
  * @param  pll_fr
  *         this parameter can be one of the following values:
  *         - CRM_PLL_FR_1
  *         - CRM_PLL_FR_2
  *         - CRM_PLL_FR_4
  *         - CRM_PLL_FR_8
  *         - CRM_PLL_FR_16
  *         - CRM_PLL_FR_32
  * @retval none
  */
void crm_pll_config(crm_pll_clock_source_type clock_source, 
                    uint16_t pll_ns, 
                    uint16_t pll_ms,
                    crm_pll_fr_type pll_fr)

Formulation of the problem.

There is an electronic board with MCU Artery. A quartz resonator with a frequency of 8 MHz is connected to it. The system frequency must be configured to 100 MHz.

What should the PLL coefficients be: N, M and RF?

Solution

In essence, the task came down to solving this Diophantine equation (4).

$8000000 \frac{N}{M} -100000000F = 0 \qquad \qquad (4)$

You can try using Artificial intelligence (AI) on the Wolfram Alfa website

However, this is not a private solution. In practice, a numerical solution is needed to initialize the function crm_pll_config. In particular, here the range of values of function (2) is quite small, so you can find a solution to equation (3) by ordinary enumeration.

To do this, I wrote my simple numerical Diophantine equation solver for PLL directly in C.

uint64_t ipow(uint32_t base, uint32_t exponenta) {
	uint64_t ret = 1, i = 0;
    if(0 != exponenta) {
        for(i = 1; i <= exponenta; i++) {
            ret *= base;
        }
    }
    return ret;
}

typedef struct{
    uint32_t ms;
    uint32_t ns;
    uint32_t fr;
}PllArtety_t;

bool pll_calc_artery(uint32_t freq_xtal_hz, 
                     uint32_t freq_sys_hz,
                     PllArtety_t* const PllArtety) {
    bool res = false;

    LOG_INFO(PLL_CALC, "FreqXtal:%u Hz,FreqSys:%u  Hz", freq_xtal_hz, 
             freq_sys_hz);
    log_printf("{[(Xtal:%uHz/M)*N]/FR }= Sys:%u Hz" CRLF, 
               freq_xtal_hz, freq_sys_hz);
    if(PllArtety) {
        uint32_t m = 0;
        uint32_t temp_hz = 0;
        uint32_t cur_freq_sys_hz = 0;
        for(m = 1; m <= 15; m++) {
            uint32_t n = 0;
            for(n = 31; n <= 500; n++) {
                uint32_t f = 0;
                for(f = 0; f <= 5; f++) {
                    uint32_t fr = ipow(2, f);
                    cur_freq_sys_hz = ((n * freq_xtal_hz) / (m * fr));
                    if(freq_sys_hz == cur_freq_sys_hz) {
                        temp_hz = freq_xtal_hz * n / m; 
                        /*condition from Artery New Clock Config*/
                        if(500000000 <= temp_hz) {
                            if(temp_hz <= 1200000000) {
                                log_printf("MS:%u,NS:%u,FR:%u" CRLF, m, n, fr);
                                PllArtety->ms = m;
                                PllArtety->ns = n;
                                PllArtety->fr = fr;
                                res = true;
                            }
                        }
                    }
                }
            }
        }
    }
    if(res) {
        LOG_INFO(PLL_CALC, "SpotPllVals!");
    } else {
        LOG_ERROR(PLL_CALC, "NoPllVals!");
    }
    return res;
}