Minimize integer round-off error in PLL frequency calculation

Question

On a particular STM32 microcontroller, the system clock is driven by a PLL whose frequency F is given by the following formula:

F := (S/M * (N + K/8192)) / P

S is the PLL input source frequency (1 - 64000000, or 64 MHz).

The other factors M, N, K, and P are the parameters the user can modify to calibrate the frequency. Judging by the bitmasks in the SDK I'm using, the value of each can be limited to a maximum of M < 64, N < 512, K < 8192, and P < 128.

Unfortunately, my target firmware does not have FPU support, so floating-point arithmetic is out. Instead, I need to compute F using integer-only arithmetic.

I have tried to rearrange the given formula with 3 goals in mind:

Expand and distribute all multiplication factors
Minimize the number of factors in each denominator
Minimize the total number of divisions performed
If two expressions have the same number of divisions, choose the one whose denominators have the least maximum (identified in earlier paragraph)

However, each of my attempts to expand and rearrange the expression all produce errors greater than the original formula as it was first expressed verbatim.

To test out different arrangements of the formula and compare error, I've written a small Go program you can run online here.

Is it possible to improve this formula so that error is minimized when using integer arithmetic? Also are any of my goals listed above incorrect or useless?

Another reason to avoid FP is that this code is called from an interrupt service routine, where FP interrupts add complexity and are best to avoid. Remember, I mentioned this is code running on an STM32 microcontroller. — ardnew
– ardnew, Commented May 19, 2021 at 5:26
@StevenPenny Can you explain why you removed your original comment and have now voted to close this question? If I'm doing something wrong it would be helpful to know what not to do in the future to get supportive answers — ardnew
– ardnew, Commented May 19, 2021 at 6:44

Zombo · Accepted Answer · 2021-05-19 15:16:35Z

1

I took your program (your first parentheses is redundant, so I removed):

 S            K
--- * ( N + ------ )
 M           8192
--------------------
        P

and ran through QuickMath [1], and I got this:

S * (8192 * N + K)
------------------
   8192 * M * P

or in Go code:

S * (8192 * N + K) / (8192 * M * P)

So it does reduce the amount of divisions. You could improve it further by pulling out the lower constant:

S * (8192 * N + K) / (M * P) >> 13

https://quickmath.com

edited May 19, 2021 at 15:16

answered May 19, 2021 at 14:52

Zombo

1

Sign up to request clarification or add additional context in comments.

1 Comment

ardnew Over a year ago

Thanks, but the round-off error produced by these solutions is incredibly large! Additionally, in Go, the final expression using a shift requires the operand be typecast to uint64, otherwise it will overflow more often than not. So unfortunately, these do not minimize round-off error at all, but significantly increase it instead. You can see proof of these results here: play.golang.org/p/7ZBXSMN1w_0

ardnew · Accepted Answer · 2021-05-19 21:46:25Z

Looking at the answer by @StevenPerry, I realized the majority of error is introduced by the limited precision we have to represent K/8192. This error then gets propagated into the other factors and dividends.

Postponing that division, however, often results in integer overflow before its ever reached. Thus, the solution I've found unfortunately depends on widening these operands to 64-bit.

The result is of the same form as the other answer, but it must be emphasized that widening the operands to 64-bit is essential. In Go source code, this looks like:

var S, N, M, P, K uint32
...
F := uint32(uint64(S) * uint64(8192*N+K) / uint64(8192*M*P))

To see the accuracy of all three of these expressions, run the code yourself on the Go Playground.

Collectives™ on Stack Overflow

Minimize integer round-off error in PLL frequency calculation

2 Answers 2

1 Comment

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

1 Comment

Comments

Your Answer

Sign up or log in

Post as a guest

Related