• AVR Freaks

Hot!Need help creating quantizer

Page: < 1234 > Showing page 2 of 4
Author
1and0
Access is Denied
  • Total Posts : 9756
  • Reward points : 0
  • Joined: 2007/05/06 12:03:20
  • Location: Harry's Gray Matter
  • Status: offline
Re: Need help creating quantizer 2019/09/20 12:42:49 (permalink)
0
NorthGuy
As 1and0 says, this involves slow division, but it's still faster than doing it in the loop.

That depend.  My loop in Post #2 involves only integer addition (and subtraction for the compare).  I have not timed it but I think it is faster than a slow division and a multiplication.
 
<edit> Corrected it here:
 
uint16_t half = x >> 1;
uint16_t value = 0;
uint8_t i = 60;
do {
    if (inputValue < (value + half)) {
        PWM1_LoadDutyValue(value);
        break;
    }
    value += x;
} while (--i);

post edited by 1and0 - 2019/09/20 12:46:03
#21
didierleplae
Starting Member
  • Total Posts : 43
  • Reward points : 0
  • Joined: 2019/03/31 16:57:50
  • Location: 0
  • Status: offline
Re: Need help creating quantizer 2019/09/20 12:43:20 (permalink)
0
1and0
didierleplae
Am I doing this correctly?
If for example:
inputValue = 500
x=17
 
(inputValue / x + 1) * x
(500/17+1)*17
(500/18)*17
(27.777)*17
 
Or would the 27.7777 get rounded up to 28?

You really need to go back to elementary school. ;)  Division comes before addition!!!
 
As inputValue and x are integer, the result is integer; so 
 
500 / 17 = 29
29 + 1 = 30
30 * 17 = 510
 
 




 
Haha! OK, got it. Thank you!
#22
didierleplae
Starting Member
  • Total Posts : 43
  • Reward points : 0
  • Joined: 2019/03/31 16:57:50
  • Location: 0
  • Status: offline
Re: Need help creating quantizer 2019/09/20 17:52:47 (permalink)
0
What do you all think of this solution, using an array?
 

int array[15] = {
0,80,160,200,280,360,440,480,560,640,680,760,840,920,960
};


for (int i = 0; i <= 15; i++)
{
if (inputValue <= array[i])
{
PWM1_LoadDutyValue(array[i]);
break;
}
}

#23
NorthGuy
Super Member
  • Total Posts : 5667
  • Reward points : 0
  • Joined: 2014/02/23 14:23:23
  • Location: Northern Canada
  • Status: online
Re: Need help creating quantizer 2019/09/20 18:34:58 (permalink)
+1 (1)
1and0
NorthGuy
As 1and0 says, this involves slow division, but it's still faster than doing it in the loop.

That depend.  My loop in Post #2 involves only integer addition (and subtraction for the compare).  I have not timed it but I think it is faster than a slow division and a multiplication.



You only need one division. Roughly comparing the division to your loop, the division is a binary search implemented in highly optimized assembler, while your loop is a brute force scan written in C.
 
#24
NorthGuy
Super Member
  • Total Posts : 5667
  • Reward points : 0
  • Joined: 2014/02/23 14:23:23
  • Location: Northern Canada
  • Status: online
Re: Need help creating quantizer 2019/09/20 19:05:11 (permalink)
0
didierleplae
What do you all think of this solution, using an array?

 
You can do a binary search on an array:
 
int a, b, m;
 
// bounds
a = 0;
b = 15;
 
do {
  m = (a + b) >> 1;
  if (inputValue < array[m]) {
    b = m; // restricting search to the bottom half
  } else {
    a = m; // restricting search to the top half
  }
} while ((a - b) > 1);
 
PWM1_LoadDutyValue(a);

 
 
post edited by NorthGuy - 2019/09/20 19:06:56
#25
NorthGuy
Super Member
  • Total Posts : 5667
  • Reward points : 0
  • Joined: 2014/02/23 14:23:23
  • Location: Northern Canada
  • Status: online
Re: Need help creating quantizer 2019/09/21 06:34:43 (permalink)
0
Or you can do a binary search without the array with very little modification:
 
int a, b, m;
 
// bounds
a = 0;
b = x << 4; // shift enough to the left to cover the full range
 
do {
  m = (a + b) >> 1;
  if (inputValue < m) {
    b = m; // restricting search to the bottom half
  } else {
    a = m; // restricting search to the top half
  }
} while ((a - b) > x);
 
PWM1_LoadDutyValue(a);

#26
1and0
Access is Denied
  • Total Posts : 9756
  • Reward points : 0
  • Joined: 2007/05/06 12:03:20
  • Location: Harry's Gray Matter
  • Status: offline
Re: Need help creating quantizer 2019/09/21 07:28:07 (permalink)
0
NorthGuy
Or you can do a binary search without the array with very little modification:

} while ((a - b) > 1);


} while ((a - b) > x);


Shouldn't these be (b - a) ?
post edited by 1and0 - 2019/09/21 07:29:40
#27
NorthGuy
Super Member
  • Total Posts : 5667
  • Reward points : 0
  • Joined: 2014/02/23 14:23:23
  • Location: Northern Canada
  • Status: online
Re: Need help creating quantizer 2019/09/21 07:41:36 (permalink)
0
1and0
NorthGuy
Or you can do a binary search without the array with very little modification:

 
} while ((a - b) > 1);
 


 
} while ((a - b) > x);
 


Shouldn't these be (b - a) ?




 
No doubts. Thanks for the correction.
#28
davea
Senior Member
  • Total Posts : 153
  • Reward points : 0
  • Joined: 2016/01/28 13:12:13
  • Location: 0
  • Status: offline
Re: Need help creating quantizer 2019/09/22 19:30:56 (permalink)
+1 (1)
multiplication is always faster
if you want to do a divide
 
if the number is to big it will not work
 
say  10000 / 23.55 = 424.6
1/23.55 = 0.0424628450106157
take 1/23.55 X 2n until you get a int as close to 65535 as you can
44525.5
so use
A = 44525 * 10000 (must use a double for A)
A >>= 20  
A is 424
or leave it boosted for next operation
PS: I hope the math is correct
#29
1and0
Access is Denied
  • Total Posts : 9756
  • Reward points : 0
  • Joined: 2007/05/06 12:03:20
  • Location: Harry's Gray Matter
  • Status: offline
Re: Need help creating quantizer 2019/09/22 20:07:38 (permalink)
0
davea
multiplication is always faster
if you want to do a divide
if the number is to big it will not work
 
say  10000 / 23.55 = 424.6
1/23.55 = 0.0424628450106157
take 1/23.55 X 2n until you get a int as close to 65535 as you can
44525.5
so use
A = 44525 * 10000 (must use a double for A)
A >>= 20  
A is 424

That works only when the divisor is a constant, which I don't think is the case here.
#30
davea
Senior Member
  • Total Posts : 153
  • Reward points : 0
  • Joined: 2016/01/28 13:12:13
  • Location: 0
  • Status: offline
Re: Need help creating quantizer 2019/09/23 11:20:14 (permalink)
0
1and0
That works only when the divisor is a constant, which I don't think is the case here.

I was referring to scaling the ADC 
my 2 cents  
#31
1and0
Access is Denied
  • Total Posts : 9756
  • Reward points : 0
  • Joined: 2007/05/06 12:03:20
  • Location: Harry's Gray Matter
  • Status: offline
Re: Need help creating quantizer 2019/09/23 11:54:37 (permalink)
0
davea
1and0
That works only when the divisor is a constant, which I don't think is the case here.

I was referring to scaling the ADC 

... and what does that have to do with the topic of this thread?
 
#32
didierleplae
Starting Member
  • Total Posts : 43
  • Reward points : 0
  • Joined: 2019/03/31 16:57:50
  • Location: 0
  • Status: offline
Re: Need help creating quantizer 2019/09/26 12:02:08 (permalink)
0
So, what I am trying to do at this point is write a code for which I can switch between several different scales, ie different sets of intervals, not being all same interval as in the previous version.
 
I'm quite sure that how I'm doing this is extremely inefficient again, but it is working, except for the fact that I get errors when I add beyond around 40 or 50 values into my arrays. So, am I running out of memory again?
Can anyone point me to a better way of doing this?
 
FYI, ANA0 has the un-quantized voltage source connected to it, ANA4 has a switch with varying voltages connected to it so I can switch between the 2 scales (arrays). I would like to eventually have the ability to switch between several scales but this is just a starting point:
 

int inputValue;
int scale;

while (1)
{
ADC_Initialize();
ADC_StartConversion(channel_ANA0);
while(!ADC_IsConversionDone());
inputValue = ADC_GetConversionResult()/64;

ADCON0 = 0x11;
ADC_StartConversion(channel_ANA4);
while(!ADC_IsConversionDone());
scale = ADC_GetConversionResult()/64;


int array[36] = {
//major//
0,34,68,85,119,153,187,204,238,272,289,323,357,391,408,442,476,493,527,561,595,612,646,680,697,731,765,799,816,850,884,901,935,969,1003,1020
};



int minorp[36] = {
//minor pentatonic//
0,0,51,85,119,119,170,204,204,255,289,323,323,374,408,408,459,493,527,527,578,612,612,663,697,731,731,782,816,816,867,901,935,935,986,1020
};

if(scale < 510){
for (int i = 0; i <= 36; i++)
{
if (inputValue <= array[i])
{
PWM1_LoadDutyValue(array[i]);
break;
}
}

}

if(scale > 510){
for (int i = 0; i <= 36; i++)
{
if (inputValue <= minorp[i])
{
PWM1_LoadDutyValue(minorp[i]);
break;
}
}
}

}

#33
didierleplae
Starting Member
  • Total Posts : 43
  • Reward points : 0
  • Joined: 2019/03/31 16:57:50
  • Location: 0
  • Status: offline
Re: Need help creating quantizer 2019/09/26 16:19:03 (permalink)
0
Ahh, adding const before my arrays seems to fix the issue
#34
pcbbc
Super Member
  • Total Posts : 1323
  • Reward points : 0
  • Joined: 2014/03/27 07:04:41
  • Location: 0
  • Status: offline
Re: Need help creating quantizer 2019/09/26 16:22:46 (permalink)
+1 (1)
didierleplae
Ahh, adding const before my arrays seems to fix the issue

Yes, then they go in program ROM rather than copied into precious RAM.
#35
NorthGuy
Super Member
  • Total Posts : 5667
  • Reward points : 0
  • Joined: 2014/02/23 14:23:23
  • Location: Northern Canada
  • Status: online
Re: Need help creating quantizer 2019/09/26 20:02:55 (permalink)
+1 (1)
pcbbc
didierleplae
Ahh, adding const before my arrays seems to fix the issue

Yes, then they go in program ROM ...



where you cannot change them (well, you can, but not easily and not often).
 
#36
1and0
Access is Denied
  • Total Posts : 9756
  • Reward points : 0
  • Joined: 2007/05/06 12:03:20
  • Location: Harry's Gray Matter
  • Status: offline
Re: Need help creating quantizer 2019/09/26 20:40:58 (permalink)
+1 (1)
didierleplae
I'm quite sure that how I'm doing this is extremely inefficient again, but it is working, ...

int array[36] = {
int minorp[36] = {
 
for (int i = 0; i <= 36; i++)
for (int i = 0; i <= 36; i++)


Your code can loop past the end of the arrays.
 
Anyway, try this:
    int16_t *p;
    if (scale < 510)
        p = array;
    else
        p = minorp;
 
    uint8_t i = 36;
    do {
        if (inputValue <= *p) {
            PWM1_LoadDutyValue(*p);
            break;
        }
        p++;
    } while (--i);

#37
didierleplae
Starting Member
  • Total Posts : 43
  • Reward points : 0
  • Joined: 2019/03/31 16:57:50
  • Location: 0
  • Status: offline
Re: Need help creating quantizer 2019/09/27 22:14:15 (permalink)
0
1and0
didierleplae
I'm quite sure that how I'm doing this is extremely inefficient again, but it is working, ...

 
int array[36] = {
 
int minorp[36] = {
 
 
 
for (int i = 0; i <= 36; i++)
 
for (int i = 0; i <= 36; i++)
 


Your code can loop past the end of the arrays.
 

 
Can you explain? I thought the for loop would stop once "i" gets to 36, which would be the end of the array, no?
So far it doesn't seem to have caused a noticeable issue. 
#38
didierleplae
Starting Member
  • Total Posts : 43
  • Reward points : 0
  • Joined: 2019/03/31 16:57:50
  • Location: 0
  • Status: offline
Re: Need help creating quantizer 2019/09/27 22:26:20 (permalink)
0
1and0
[Anyway, try this:
    int16_t *p;
    if (scale < 510)
        p = array;
    else
        p = minorp;
 
    uint8_t i = 36;
    do {
        if (inputValue <= *p) {
            PWM1_LoadDutyValue(*p);
            break;
        }
 
        p++;
    } while (--i);





If I have arrays of different sizes, could I just do?:
 

uint8_t i = p.size();

#39
ric
Super Member
  • Total Posts : 23855
  • Reward points : 0
  • Joined: 2003/11/07 12:41:26
  • Location: Australia, Melbourne
  • Status: offline
Re: Need help creating quantizer 2019/09/28 04:56:33 (permalink)
+1 (1)
didierleplae
Can you explain? I thought the for loop would stop once "i" gets to 36, which would be the end of the array, no?

No.
The highest element in an array with 36 elements is #35, not #36. Remember they start at zero.
 

I also post at: PicForum
Links to useful PIC information: http://picforum.ric323.co...opic.php?f=59&t=15
NEW USERS: Posting images, links and code - workaround for restrictions.
To get a useful answer, always state which PIC you are using!
#40
Page: < 1234 > Showing page 2 of 4
Jump to:
© 2019 APG vNext Commercial Version 4.5