Time goes fast, new and more powerful microprocessors are introduced, and the favourites of a year ago are fading and starts to collect dust in a draver filled with useful but not quite exciting boards. These days the Cortex M3 of the Maple board feels a bit old, the Teensy 3.1 is a great board and the Arduino type libraries and support is superb, but it has a bit limited memory and no hardware floating point.The boards I use mostly for audio generation at the moment are the Netduino plus 2, without the Netduino bootloader and .Net libraries, the STM32F4 Discovery and the XMC4500 Relax Kit Lite. All of these have Cortex-M4F processors, more than 128KB RAM and 1024KB of flash, they are all cheap and good value for money.
I need stable USB MIDI and after wrangling with the device libraries and development platforms, endless hierachies of folders and files that are usually targeted at Windows and often lacking USB MIDI, I decided to write yet another lightweight USB implementation. I know this might sound stupid and a waste of effort but having some time free due to vacation times and a bit of rainy summer I went ahead.
The code is written from scratch and uses only some MCU specific header files borrowed unchanged from the manufaturer supplied code libraries. When time allows and I have done some more testing a few minimal example programs will be added.
I have uploaded the code to my Cortal Dendrites repository on Github:
https://github.com/mlu/cortal_dendrites/tree/master/cortex_m/usblib
Happy Coding :)
Showing posts with label xmc4500. Show all posts
Showing posts with label xmc4500. Show all posts
Monday, August 10, 2015
Friday, May 22, 2015
Computing fractional multipliers and divisors using continued fractions.
This blog post will discuss how to find the best rational approximation with bounded numerator or denominator to a a preferred frequency ratio. This will be a bit mathematical but actually nothing more than standard addition, subtraction, multiplication and division will be used. Some example code is given at the end.
An example is the USIC in the Infineon XMC1100 and XMC4500 family microprocessors. Here the clock for the bitslices is derived from the system clock, slightly simplified, as
DCQT gives the oversampling count, typically set to 15. PDIV and STEP are register values controlling the frequency division. On the XMC1100 PDIV and STEP are 10 bit wide so they have values from 0 to 1023. Rearranging the above we see that we must find a good approximation
with values of PDIV and STEP between 0 and 1023.
Working by hand we would now factor out common factors from numerator and denominator, but for computer implementations that is unnecessary extra work. As we shall see the algorithm works as well without that step.
Now we calculate the signed integer division with remainder using the rounded value 20 as quotient.
Rewrite the denominator in the last fraction by carrying out the division with remainder
We enter this value 3 in the previous formula (3) to get the approximation
This is good, after one iteration the error is less than 0.008 or about 300ppm.
We can improve this by using a better using a more precise value
This approximation is better, error is about 3ppm, but the STEP value 1101 is to large for the 10 bit range, so we keep the previous approximation of 59/3.
So we are given a rational number p/q and we want to find succesive approximations \( a_n/b_n \) to p/q with smaller values for \( a_n \) and \(b_n \) than p and q. For the baud rate generations we want the best approximation where \( a_n \) and \(b_n \) fits in the respective fractional multiplier and divisor registers.
For the first few values of n we get:
\[ a_{-1} =0, b_{-1}=1 \]
\[ a_0 =1, b_0=0 \]
\[ \frac {a_{1}}{b_{1}} = c_0 = \frac {0 + 1 \cdot c_0}{1 + 0 \cdot c_0} = \frac {a_{-1} + a_0 \cdot c_0}{b_{-1} + b_0 \cdot c_0} \]
\[ a_1 =c_0, b_1=1 \]
\[ \frac {a_{2}}{b_{2}} = c_0 + \frac {1}{c_1} = \frac {c_0 \cdot c_1 + 1}{c_1} = \frac {a_{0} + a_1 \cdot c_1}{b_{0} + b_1 \cdot c_1} \]
\[ \frac {a_{3}}{b_{3}} = \frac {a_{0} + a_1 ( c_1+ \frac 1 {c_2})}{b_{0} + b_1 ( c_1+ \frac 1 {c_2})} = \frac {(a_{0} + a_1 c_1 ) c_2+ a_1}{(b_{0} + b_1 c_1 ) {c_2}+ b_1} = \frac {a_1 + a_{2}{c_2}}{b_1+b_{2}{c_2}} \]
We now can see the recursion formula develop
\[ \frac {a_{4}}{b_{4}} = \frac {a_{1} + a_2 ( c_2+ \frac 1 {c_3})}{b_{1} + b_2 ( c_2+ \frac 1 {c_3})} = \frac {(a_{1} + a_2 c_2 ) c_3+ a_2}{(b_{1} + b_2 c_2 ) {c_3}+ b_2} = \frac {a_2 + a_{3}{c_3}}{b_2+b_{3}{c_3}} \]
\[ \frac {a_{n+1}}{b_{n+1}} = \frac {a_{n-2} + a_{n-1} ( c_{n-1}+ \frac 1 {c_n})}{b_{n-2} + b_{n-1} ( c_{n-1}+ \frac 1 {c_{n}})} = \frac {(a_{n-2} + a_{n-1} c_{n-1} ) c_n+ a_{n-1}}{(b_{n-2} + b_{n-1} c_{n-1} ) {c_n}+ b_{n-1}} = \frac {a_{n-1} + a_{n}{c_n}}{b_{n-1}+b_{n}{c_n}} \]
Startup:
\( r_0 = r \)
\( p_0 = p, q_0 = q \)
\( a_{-1} =0, b_{-1}=1 \)
\( a_0 =1, b_0=0 \)
Loop until q_n+1 is 0 or an or bn are to large
\( c_{n} = round(r_{n}) = round ( p_{n}/q_{n} ) \)
\( r_{n+1} = 1/(r_n-c_n) \) This is done calculated terms of \(p_n\) and \(q_n\)
\( p_{n+1} = q_n \)
\( q_{n+1}=p_{n}-c_n \cdot q_n \)
\( a_{n+1}=a_{n-1}+a_{n} \cdot c_{n} \)
\( b_{n+1}=b_{n-1}+b_{n} \cdot c_{n} \)
The rounding operations can be done downwards, keeping all values positive, or towards the nearest integer improving precision but also introducing negative numers and extra complexity. Note that the \(c_n\) value is calculated before updating \(p_n\) and \(q_n\) and is not remembered and used in the next iteration but recalculated.
void cfractr(int32_t p, int32_t q,int32_t alim, uint32_t * ares, uint32_t * bres) {
Fractional baudrate generation
Some microprocessors uses fractional multipliers and divisors to generate accurate baud rates from system clocks that are not an integer multiple of the bitslice clock frequency. The bitslice frequency is the baudrate times an oversampling count.
\[ f_{bitslice} = oversample \cdot baudrate = ratio \cdot f_{sysclock} \tag{1} \]
An example is the USIC in the Infineon XMC1100 and XMC4500 family microprocessors. Here the clock for the bitslices is derived from the system clock, slightly simplified, as
\[ f_{bitslice} = (DCQT+1) baudrate = \frac 1 {(PDIV+1)} \cdot \frac {STEP} {1024} \cdot f_{sysclock} \]
DCQT gives the oversampling count, typically set to 15. PDIV and STEP are register values controlling the frequency division. On the XMC1100 PDIV and STEP are 10 bit wide so they have values from 0 to 1023. Rearranging the above we see that we must find a good approximation
\[ \frac {STEP} {(PDIV+1)} \approx \frac {(DCQT+1) baudrate \cdot 1024} { f_{sysclock} } \tag{2} \]
with values of PDIV and STEP between 0 and 1023.
Example: 38400 baud from a 32MHz clock and 16 times oversampling
We enter the values in (2) to find
\( \frac {STEP} {(PDIV+1)} = \frac {16 \cdot 38400 \cdot 1024} { 32000000 } = \frac {629145600} { 32000000 } = 19.6608 \)
Now we calculate the signed integer division with remainder using the rounded value 20 as quotient.
\( \frac {16 \cdot 38400 \cdot 1024} { 32000000 } = 20 - \frac {10854400} { 32000000 } = 20 - \frac {1} { \frac { 32000000 } {10854400} } \tag{3} \)
Rewrite the denominator in the last fraction by carrying out the division with remainder
\( \frac { 32000000 } {10854400} = 3 - \frac {563200}{ 10854400 } \approx 2.948 \approx 3 \)
We enter this value 3 in the previous formula (3) to get the approximation
\[ \frac {16 \cdot 38400 \cdot 1024} { 32000000 } \approx 20 - \frac {1} { 3 } = \frac {59} {3} = 19.6667 \]
We can improve this by using a better using a more precise value
\(\frac { 32000000 } {10854400} = 3 - \frac {563200}{ 10854400} = 3 - \frac 1 { \frac { 10854400 }{563200}} = 3 - \frac 1 {19 + \frac {153600 }{563200}} \approx 3 - \frac 1 { 19 } = \frac {56}{19}\)
Inserted into (3) this gives
\( \frac {16 \cdot 38400 \cdot 1024} { 32000000 } \approx 20 - \frac {1} { \frac {56}{19} } = 20 - \frac {19} {56} = \frac {1101} {56} = 19.6607 \)
This approximation is better, error is about 3ppm, but the STEP value 1101 is to large for the 10 bit range, so we keep the previous approximation of 59/3.
Best rational approximation with continued fractions
In order to find a general method to calculate good rational approximations as in the previous example we use the theory of partial quotients, or convergents, of continued fraction expansions and best rational approximation theory. [TO DO add links ] This is a well developed general theory for finding the best rational apprimations to a number with a given size of the denominator. There are recursive algoritms for calculating succusively better approximations.So we are given a rational number p/q and we want to find succesive approximations \( a_n/b_n \) to p/q with smaller values for \( a_n \) and \(b_n \) than p and q. For the baud rate generations we want the best approximation where \( a_n \) and \(b_n \) fits in the respective fractional multiplier and divisor registers.
The formula
\[ \frac p q = c_0 + \frac {1}{c_1 + \frac {1}{c_2 + \ddots \frac {1}{c_n + \frac {1} {r_{n+1}}}}} \approx c_0 + \frac {1}{c_1 + \frac {1}{c_2 + \ddots \frac {1}{c_n }}} = \frac {a_{n+1}}{b_{n+1}} \]For the first few values of n we get:
\[ a_{-1} =0, b_{-1}=1 \]
\[ a_0 =1, b_0=0 \]
\[ \frac {a_{1}}{b_{1}} = c_0 = \frac {0 + 1 \cdot c_0}{1 + 0 \cdot c_0} = \frac {a_{-1} + a_0 \cdot c_0}{b_{-1} + b_0 \cdot c_0} \]
\[ a_1 =c_0, b_1=1 \]
\[ \frac {a_{2}}{b_{2}} = c_0 + \frac {1}{c_1} = \frac {c_0 \cdot c_1 + 1}{c_1} = \frac {a_{0} + a_1 \cdot c_1}{b_{0} + b_1 \cdot c_1} \]
\[ \frac {a_{3}}{b_{3}} = \frac {a_{0} + a_1 ( c_1+ \frac 1 {c_2})}{b_{0} + b_1 ( c_1+ \frac 1 {c_2})} = \frac {(a_{0} + a_1 c_1 ) c_2+ a_1}{(b_{0} + b_1 c_1 ) {c_2}+ b_1} = \frac {a_1 + a_{2}{c_2}}{b_1+b_{2}{c_2}} \]
We now can see the recursion formula develop
\[ \frac {a_{4}}{b_{4}} = \frac {a_{1} + a_2 ( c_2+ \frac 1 {c_3})}{b_{1} + b_2 ( c_2+ \frac 1 {c_3})} = \frac {(a_{1} + a_2 c_2 ) c_3+ a_2}{(b_{1} + b_2 c_2 ) {c_3}+ b_2} = \frac {a_2 + a_{3}{c_3}}{b_2+b_{3}{c_3}} \]
\[ \frac {a_{n+1}}{b_{n+1}} = \frac {a_{n-2} + a_{n-1} ( c_{n-1}+ \frac 1 {c_n})}{b_{n-2} + b_{n-1} ( c_{n-1}+ \frac 1 {c_{n}})} = \frac {(a_{n-2} + a_{n-1} c_{n-1} ) c_n+ a_{n-1}}{(b_{n-2} + b_{n-1} c_{n-1} ) {c_n}+ b_{n-1}} = \frac {a_{n-1} + a_{n}{c_n}}{b_{n-1}+b_{n}{c_n}} \]
The algorithm
We start with a rational number r = p/q. We will generate a sequence of five values \(a_n, b_n, c_n, p_n\) and \(q_n\). The quotients \(a_n/b_n\) will be our succesive approximations to r. The values \(r_n\) are defined as \(p_n/q_n\) but they need not be explicitly calculated, the formula for \(r_n\) is used as the template for how \(p_n\) and \(q_n\) are updated.Startup:
\( r_0 = r \)
\( p_0 = p, q_0 = q \)
\( a_{-1} =0, b_{-1}=1 \)
\( a_0 =1, b_0=0 \)
Loop until q_n+1 is 0 or an or bn are to large
\( c_{n} = round(r_{n}) = round ( p_{n}/q_{n} ) \)
\( r_{n+1} = 1/(r_n-c_n) \) This is done calculated terms of \(p_n\) and \(q_n\)
\( p_{n+1} = q_n \)
\( q_{n+1}=p_{n}-c_n \cdot q_n \)
\( a_{n+1}=a_{n-1}+a_{n} \cdot c_{n} \)
\( b_{n+1}=b_{n-1}+b_{n} \cdot c_{n} \)
The rounding operations can be done downwards, keeping all values positive, or towards the nearest integer improving precision but also introducing negative numers and extra complexity. Note that the \(c_n\) value is calculated before updating \(p_n\) and \(q_n\) and is not remembered and used in the next iteration but recalculated.
A skeleton C implementation
Following code lacks error handling and only checks limit for numerator, but it illustrates the algorithm. It does lack a few comments, but follows the algortithm structure closely.void cfractr(int32_t p, int32_t q,int32_t alim, uint32_t * ares, uint32_t * bres) {
int ap = 0;
int a1 = 1;
int bp = 1;
int b1 = 0;
int cn = a1, anext, bnext, pnext;
while (1) {
/* Signed rounded rational division */
if ((q>0)&&(p>0)||(q<0)&&(p<0))
cn = (p+q/2)/q;
else
cn = (p-q/2)/q;
/* Next value for partial quotients and remainder */
anext = ap + cn*a1;
bnext = bp + cn*b1;
pnext = p-cn*q;
/* Exact value, remainder is 0, break */
if (pnext == 0) {
a1 = anext;
b1 = bnext;
break;
}
/* Numerator too large, break */
if ((anext<-alim)||(anext>alim)) {
break;
}
/* Shift one step before next iteration */
ap = a1;
bp = b1;
a1 = anext;
b1 = bnext;
p = q;
q = pnext;
}
if (a1<0){a1=-a1;b1=-b1;}
*ares = a1;
*bres = b1;
}
Subscribe to:
Posts (Atom)