I�m developing an application running on a PIC 18F.tbd that has to find (positive-going) zero crossing points on a sine input with slowly varying frequency. The frequency/sampling regime is such that successive samples of the waveform are not more than 70 degrees apart. Linear interpolation between sample points therefore gives zero crossing estimates within about 2 degrees of the actual crossing point, which is good enough. What I am looking for is a quicker way of performing the linear interpolation. As background � the PIC 18F series have a multiplier which will do an 8-bit*8-bit unsigned multiply in 1 cycle. The microchip 16*16 bit unsigned multiply takes about 25 cycles, their 16/16 bit division takes about 80 cycles. Simple instructions, adds, bit tests etc take 1 cycle but are only 8-bit. I�m trying to keep the code in C so that it can be quickly changed easily, or ported if the PIC can�t cope. 1) For a simple first approximation, I divided the sample time by the voltage difference over a zero crossing to get a gradient approximation, so I can interpolate the zero value. A 16-bit division, a 16-bit multiplication. This is fine but I want more speed. 2) Next I used the short-term stability of the waveform to maintain a period estimate. I can estimate the present crossing point from the previous one. I can then calculate the sample voltage that would correspond to the estimated crossing point. Subtracting this from the actual sample voltage gives me an error term that I can use to correct the initial crossing point estimate. This approach replaces the division above with 3 16-bit multiplications and runs more slowly. 3) I tried to replace 16-bit multiplies with 8-bit multiplies but so much extra work was involved in retaining significance within the 8-bits that this approach was not much quicker. 4) I did a binary chop approach, but despite the simplicity of the code, over the 5 iterations it takes to reach the desired time accuracy, it takes the same execution time as the above. 3 and 4 above could probably have their time at least halved by assembly coding, so I should be able to get a working solution, but I�m interested to know if there�s any other solution � a simple-ish algorithm that estimates the crossing in 2 iterations maybe, or something that enables me to use the multiplier, which effectively can only be used to multiply 2 4-bit numbers to make an 8-bit number if you want to access its 1-cycle speed. Thanks for any help � Christian Tiburtius This message was sent using the Comp.DSP web interface on www.DSPRelated.com
Efficient zero crossing/interpolation calculation
Started by ●April 4, 2005
Reply by ●April 4, 20052005-04-04
dbmole wrote:> I'm developing an application running on a PIC 18F.tbd that has tofind> (positive-going) zero crossing points on a sine input with slowlyvarying> frequency. The frequency/sampling regime is such that successivesamples> of the waveform are not more than 70 degrees apart. Linearinterpolation> between sample points therefore gives zero crossing estimates withinabout> 2 degrees of the actual crossing point, which is good enough. What Iam> looking for is a quicker way of performing the linear interpolation. > > As background - the PIC 18F series have a multiplier which will doan> 8-bit*8-bit unsigned multiply in 1 cycle. The microchip 16*16 bitunsigned> multiply takes about 25 cycles, their 16/16 bit division takes about80> cycles. Simple instructions, adds, bit tests etc take 1 cycle but areonly> 8-bit. I'm trying to keep the code in C so that it can be quicklychanged> easily, or ported if the PIC can't cope. > > 1) For a simple first approximation, I divided the sample time by the > voltage difference over a zero crossing to get a gradientapproximation,> so I can interpolate the zero value. A 16-bit division, a 16-bit > multiplication. This is fine but I want more speed. > > 2) Next I used the short-term stability of the waveform to maintain a > period estimate. I can estimate the present crossing point from the > previous one. I can then calculate the sample voltage that would > correspond to the estimated crossing point. Subtracting this from the > actual sample voltage gives me an error term that I can use tocorrect the> initial crossing point estimate. This approach replaces the divisionabove> with 3 16-bit multiplications and runs more slowly. > > 3) I tried to replace 16-bit multiplies with 8-bit multiplies but somuch> extra work was involved in retaining significance within the 8-bitsthat> this approach was not much quicker. > > 4) I did a binary chop approach, but despite the simplicity of thecode,> over the 5 iterations it takes to reach the desired time accuracy, it > takes the same execution time as the above. > > 3 and 4 above could probably have their time at least halved byassembly> coding, so I should be able to get a working solution, but I'minterested> to know if there's any other solution - a simple-ish algorithmthat> estimates the crossing in 2 iterations maybe, or something thatenables me> to use the multiplier, which effectively can only be used to multiply2> 4-bit numbers to make an 8-bit number if you want to access its1-cycle> speed. > > Thanks for any help - Christian Tiburtius > > > > > > This message was sent using the Comp.DSP web interface on > www.DSPRelated.comDoes your processor have an Input Capture function like on the 68HC11? It can record the time at which a zero crossing occurs. Jo
Reply by ●April 6, 20052005-04-06
Reply - Not as such, but I'm anyway recording the time that each sample is started, which is a known time delay from the sample point. This message was sent using the Comp.DSP web interface on www.DSPRelated.com
Reply by ●April 6, 20052005-04-06
dbmole wrote:> Reply - Not as such, but I'm anyway recording the time that each sample is > started, which is a known time delay from the sample point. > > This message was sent using the Comp.DSP web interface on > www.DSPRelated.comIn one application, I detect the zero crossings by using a comparator to make a square wave which drives an edge-sensitive, direction selectable interrupt pin. That same pin can trigger a capture register for later use, but I don't need that. One way or another, measuring the zero crossing directly rather than computing where it was can often be simpler. Jerry -- Engineering is the art of making what you want from things you can get. �����������������������������������������������������������������������
Reply by ●April 7, 20052005-04-07
>In one application, I detect the zero crossings by using a comparator to>make a square wave which drives an edge-sensitive, direction selectable >interrupt pin. That same pin can trigger a capture register for later >use, but I don't need that. One way or another, measuring the zero >crossing directly rather than computing where it was can often besimpler.> >Jerry >-- >Engineering is the art of making what you want from things you can get. >����������������������������������������������������������������������� >Yup, that would be the simplest thing to do, but the philosophy of the project is that we've got a PIC microcontroller anyway, so we can save the cost of a comparator if we get the PIC to do the zero crossing calculation, so it's really a software solution I'm looking for. - Christian This message was sent using the Comp.DSP web interface on www.DSPRelated.com
Reply by ●April 7, 20052005-04-07
dbmole wrote:>>In one application, I detect the zero crossings by using a comparator to > > >>make a square wave which drives an edge-sensitive, direction selectable >>interrupt pin. That same pin can trigger a capture register for later >>use, but I don't need that. One way or another, measuring the zero >>crossing directly rather than computing where it was can often be > > simpler. > >>Jerry >>-- >>Engineering is the art of making what you want from things you can get. >>����������������������������������������������������������������������� >> > > > Yup, that would be the simplest thing to do, but the philosophy of the > project is that we've got a PIC microcontroller anyway, so we can save the > cost of a comparator if we get the PIC to do the zero crossing calculation, > so it's really a software solution I'm looking for. > > - Christian > > This message was sent using the Comp.DSP web interface on > www.DSPRelated.comJohn's asked if your processor has input capture like the 68HC11. If it does, you can do what I described. Two diodes would serve in place of the comparator if the drive signal were large enough. Jerry -- Engineering is the art of making what you want from things you can get. �����������������������������������������������������������������������
Reply by ●April 11, 20052005-04-11
> >John's asked if your processor has input capture like the 68HC11. If it >does, you can do what I described. Two diodes would serve in place of >the comparator if the drive signal were large enough. > >Jerry >-- >Engineering is the art of making what you want from things you can get. >����������������������������������������������������������������������� >Well, thank you for getting me to actually go and read the datasheet for the 68HC11 - a useful chip that I hadn't been exposed to. Event triggered timer capture is a thing that PICs don't seem to have - in my last project it was just what I needed. I'll keep the 68HC11 in mind in case the hardware/software balance of power changes on the project (as it is likely to). For the moment though, my brief is still to find out how clever the software can be made, while someone else is looking at hardware, so I'm still interested in low operation-count algorithms I may have overlooked. - Christian This message was sent using the Comp.DSP web interface on www.DSPRelated.com
Reply by ●April 11, 20052005-04-11
dbmole wrote:>>John's asked if your processor has input capture like the 68HC11. If it >>does, you can do what I described. Two diodes would serve in place of >>the comparator if the drive signal were large enough. >> >>Jerry >>-- >>Engineering is the art of making what you want from things you can get. >>����������������������������������������������������������������������� >> > > > Well, thank you for getting me to actually go and read the datasheet for > the 68HC11 - a useful chip that I hadn't been exposed to. Event triggered > timer capture is a thing that PICs don't seem to have - in my last project > it was just what I needed. I'll keep the 68HC11 in mind in case the > hardware/software balance of power changes on the project (as it is likely > to). For the moment though, my brief is still to find out how clever the > software can be made, while someone else is looking at hardware, so I'm > still interested in low operation-count algorithms I may have overlooked. > > - ChristianI'm glad to be potentially useful. You night also want to look at the 68HC12 and 68HC16. Jerry -- Engineering is the art of making what you want from things you can get. �����������������������������������������������������������������������
Reply by ●April 12, 20052005-04-12
"Jerry Avins" <jya@ieee.org> wrote in message news:EqadnWslIo12icbfRVn-jg@rcn.net...> dbmole wrote: >>>John's asked if your processor has input capture like the 68HC11. If it >>>does, you can do what I described. Two diodes would serve in place of the >>>comparator if the drive signal were large enough. >>> >>>Jerry >>>-- >>>Engineering is the art of making what you want from things you can get. >>>����������������������������������������������������������������������� >>> >> >> >> Well, thank you for getting me to actually go and read the datasheet for >> the 68HC11 - a useful chip that I hadn't been exposed to. Event triggered >> timer capture is a thing that PICs don't seem to have - in my last >> project >> it was just what I needed. I'll keep the 68HC11 in mind in case the >> hardware/software balance of power changes on the project (as it is >> likely >> to). For the moment though, my brief is still to find out how clever the >> software can be made, while someone else is looking at hardware, so I'm >> still interested in low operation-count algorithms I may have overlooked. >> >> - Christian > > I'm glad to be potentially useful. You night also want to look at the > 68HC12 and 68HC16. >I have a 68HC16Z1EVB development kit I could let go for real cheap if anyone is interested. Clay
Reply by ●April 12, 20052005-04-12
Assuming you are working on fixed point code, you can do following: 1. Breaking 16x16 bit multiplication into 8x8 takes just 4 mult and 3 adds. inline your C function and enable the optimization of the cross-compiler and the gains should be good enough. 2. The time difference between successive samples t2 - t1 will be a constant. So why dont you invert it and use mult in place of div. What I mean is that calculate 1/(t2 - t1) as a constant and then use this everytime. Hope that helps. "dbmole" <martin.welbank@ultracontrols.aero> wrote in message news:<hqednYaeqPIdyczfRVn-gA@giganews.com>...> I?m developing an application running on a PIC 18F.tbd that has to find > (positive-going) zero crossing points on a sine input with slowly varying > frequency. The frequency/sampling regime is such that successive samples > of the waveform are not more than 70 degrees apart. Linear interpolation > between sample points therefore gives zero crossing estimates within about > 2 degrees of the actual crossing point, which is good enough. What I am > looking for is a quicker way of performing the linear interpolation. > > As background ? the PIC 18F series have a multiplier which will do an > 8-bit*8-bit unsigned multiply in 1 cycle. The microchip 16*16 bit unsigned > multiply takes about 25 cycles, their 16/16 bit division takes about 80 > cycles. Simple instructions, adds, bit tests etc take 1 cycle but are only > 8-bit. I?m trying to keep the code in C so that it can be quickly changed > easily, or ported if the PIC can?t cope. > > 1) For a simple first approximation, I divided the sample time by the > voltage difference over a zero crossing to get a gradient approximation, > so I can interpolate the zero value. A 16-bit division, a 16-bit > multiplication. This is fine but I want more speed. > > 2) Next I used the short-term stability of the waveform to maintain a > period estimate. I can estimate the present crossing point from the > previous one. I can then calculate the sample voltage that would > correspond to the estimated crossing point. Subtracting this from the > actual sample voltage gives me an error term that I can use to correct the > initial crossing point estimate. This approach replaces the division above > with 3 16-bit multiplications and runs more slowly. > > 3) I tried to replace 16-bit multiplies with 8-bit multiplies but so much > extra work was involved in retaining significance within the 8-bits that > this approach was not much quicker. > > 4) I did a binary chop approach, but despite the simplicity of the code, > over the 5 iterations it takes to reach the desired time accuracy, it > takes the same execution time as the above. > > 3 and 4 above could probably have their time at least halved by assembly > coding, so I should be able to get a working solution, but I?m interested > to know if there?s any other solution ? a simple-ish algorithm that > estimates the crossing in 2 iterations maybe, or something that enables me > to use the multiplier, which effectively can only be used to multiply 2 > 4-bit numbers to make an 8-bit number if you want to access its 1-cycle > speed. > > Thanks for any help ? Christian Tiburtius > > > > > > This message was sent using the Comp.DSP web interface on > www.DSPRelated.com
