Alternative algorithm to finding minimum??

Hello,

I am going to implement an algorithm on a DSP. Part of the algorithm
tracks the minimum amplitude of each frequency bin in a power spectrum.
However, the array that I am using to calculate the minimum is too big
and I was wondering if there is an alternative way of calculating the 
minimum
and still obtaining the same results as the following algorithm generates 
(or at
least something that is close)?

In MATLAB this "minimum"-algorithm looks like this:

clc
close all
clear

% Number of observations
N_observations=1000;

% FFT points
N_fft=512;

% Generate random power spectra
LPC_order=10;
power_spectra=zeros(N_observations,N_fft);
for n=1:N_observations;
    f_cut=abs(randn(1));
    if or(f_cut<=0, f_cut>=1)
        f_cut=0.5;
    end

    [b,a]=butter(10,f_cut);
    tmp_input=filter(b,a,randn(1,N_fft));
    tmp_lpccoeff=lpc(tmp_input,LPC_order);
    power_spectra(n,:)=abs(freqz(1,tmp_lpccoeff));
end


% Array to store past 300 spectras
N_history=300;
observations_array=zeros(N_history,N_fft);

% init counter
tmp_cnt=1;


for n=1:N_observations
    % load n'th power spectrum
    spectrum_input=power_spectra(n,:);

    % store in history array
    observations_array(tmp_cnt,:)=spectrum_input;

    % calculate minimum
    min_powerspectrum=min(observations_array);

    % display results
    plot(spectrum_input);
    hold
    plot(min_powerspectrum,'r--');
    hold
    xlim([0 512])
    ylim([0 5])
    drawnow;

    % counter control
    tmp_cnt=tmp_cnt+1;
    if tmp_cnt>N_history
        tmp_cnt=1;
    end

end

"Jack" <jack@nospammers.please> wrote in message
news:43fe1347$0$67255$157c6196@dreader2.cybercity.dk...
> Hello,
>
> I am going to implement an algorithm on a DSP. Part of the algorithm
> tracks the minimum amplitude of each frequency bin in a power spectrum.
> However, the array that I am using to calculate the minimum is too big
> and I was wondering if there is an alternative way of calculating the
> minimum
> and still obtaining the same results as the following algorithm generates
> (or at
> least something that is close)?

All you need is this
min_powerspectrum = min(power_spectra);

You don't need all the for loops and arrays after you calculate your 1000
power spectra observations.
The min function computes the min from each column of power_spectra. So you
have your result in one operation. If you are interested in only a subset of
observations, you can invoke min with the appropriate sub-matrix of
power_spectra.

BTW, you need a transpose operator in this line (atleast my matlab
complains)
> power_spectra(n,:)=abs(freqz(1,tmp_lpccoeff))';

Cheers
Bhaskar


> In MATLAB this "minimum"-algorithm looks like this:
>
> clc
> close all
> clear
>
> % Number of observations
> N_observations=1000;
>
> % FFT points
> N_fft=512;
>
> % Generate random power spectra
> LPC_order=10;
> power_spectra=zeros(N_observations,N_fft);
> for n=1:N_observations;
>     f_cut=abs(randn(1));
>     if or(f_cut<=0, f_cut>=1)
>         f_cut=0.5;
>     end
>
>     [b,a]=butter(10,f_cut);
>     tmp_input=filter(b,a,randn(1,N_fft));
>     tmp_lpccoeff=lpc(tmp_input,LPC_order);
>     power_spectra(n,:)=abs(freqz(1,tmp_lpccoeff));
> end
>
>
> % Array to store past 300 spectras
> N_history=300;
> observations_array=zeros(N_history,N_fft);
>
> % init counter
> tmp_cnt=1;
>
>
> for n=1:N_observations
>     % load n'th power spectrum
>     spectrum_input=power_spectra(n,:);
>
>     % store in history array
>     observations_array(tmp_cnt,:)=spectrum_input;
>
>     % calculate minimum
>     min_powerspectrum=min(observations_array);
>
>     % display results
>     plot(spectrum_input);
>     hold
>     plot(min_powerspectrum,'r--');
>     hold
>     xlim([0 512])
>     ylim([0 5])
>     drawnow;
>
>     % counter control
>     tmp_cnt=tmp_cnt+1;
>     if tmp_cnt>N_history
>         tmp_cnt=1;
>     end
>
> end
>
>
>
>
>
>
>
>

The array is too big? Too big how/why?

Dirk

In article <43fe1347$0$67255$157c6196@dreader2.cybercity.dk>, "Jack"
<jack@nospammers.please> wrote:

> Hello,
> 
> I am going to implement an algorithm on a DSP. Part of the algorithm
> tracks the minimum amplitude of each frequency bin in a power spectrum.
> However, the array that I am using to calculate the minimum is too big
> and I was wondering if there is an alternative way of calculating the 
> minimum
> and still obtaining the same results as the following algorithm generates 
> ......
------------------
  If memory is your problem, why not do everything in smaller "chunks" (as
you appear to have already done, in part, with your N_history count) and
update an "overall" minimum for each frequency at the end of each chunk? 
In other words, don't attempt to deal with a 1000 x 512 array all at one
time.  Or am I not understanding you correctly?

  To take a very simple example, if I were required to generate one
million random numbers with 'rand' and display the smallest of them on my
ancient student version 4a, which has a limit of 8192 for maximum array
size (sob!), I would have to do this:

mn = inf;
for N = 1:125
 mn = min([mn;rand(8000,1)]);
end
disp(mn)

You could do something analogous to this on a grander scale with your 512
frequencies.  (In fact I could probably do your problem if I used chunks
of only 16 observations at a time.)

(Remove "xyzzy" and ".invalid" to send me email.)
Roger Stafford

Jack wrote:
>
> I am going to implement an algorithm on a DSP. Part of the algorithm
> tracks the minimum amplitude of each frequency bin in a power spectrum.
> However, the array that I am using to calculate the minimum is too big
> and I was wondering if there is an alternative way of calculating the minimum
> and still obtaining the same results as the following algorithm generates
> (or at least something that is close)?

is your basic question about getting MATLAB to calculate
min(power_spectra(:,m)) where 1 <= m <= N_fft (geez i hate MATLAB
indexing particularly of spectra) ?

> In MATLAB this "minimum"-algorithm looks like this:

this is a MATLAB function or your function?

> for n=1:N_observations;
>     f_cut=abs(randn(1));
>     if or(f_cut<=0, f_cut>=1)
>         f_cut=0.5;
>     end
>

this random f_cut signal is curious.

>     [b,a]=butter(10,f_cut);
>     tmp_lpccoeff=lpc(tmp_input,LPC_order);
>     power_spectra(n,:)=abs(freqz(1,tmp_lpccoeff));
> end

--

r b-j

>
> All you need is this
> min_powerspectrum = min(power_spectra);

I'm sorry, but you misunderstand the problem. I am not trying
to implement the function in a MATLAB environment. The MATLAB
program is just a simulation to show you what the function does.

I am looking for a way to get rid of the big array but without
loosing the functionality - that is: to always be able to calculate
the minimum power spectrum among the 300 latest power
spectra (I am doing this so I can adaptively estimate the background noise
of a speech signal).

I have thought a long and hard time about how I can get rid of
the array and still be able to track the minimum power spectrum,
but it doesn't look like it's possible. If it is I would love to hear
about how I can do it...if not: then I would like to hear about better
ways of doing it.

Thank you.

> The array is too big? Too big how/why?

The array is too big for the internal memory of a SHARC
DSP (21364). I get "out of memory" when I compile. At
the moment I would like to _not_ use the external memory
if possible.

>  If memory is your problem, why not do everything in smaller "chunks" (as
> you appear to have already done, in part, with your N_history count) and
> update an "overall" minimum for each frequency at the end of each chunk?
> In other words, don't attempt to deal with a 1000 x 512 array all at one
> time.  Or am I not understanding you correctly?

Well, the simulations I have done in MATLAB show that a history of
300 power spectra are needed to estimate the background noise of
a speech signal.

I am looking for a way to get rid of the big array but without
loosing the functionality - that is: to always be able to calculate
the minimum power spectrum among the 300 latest power
spectra. As mentioned, I am doing this so I can adaptively
estimate the background noise of a speech signal.

I have thought a long and hard time about how I can get rid of
the array and still be able to track the minimum power spectrum,
but it doesn't look like it's possible. If it is I would love to hear
about how I can do it...if not: then I would like to hear about better
ways of doing it.

> is your basic question about getting MATLAB to calculate
> min(power_spectra(:,m)) where 1 <= m <= N_fft (geez i hate MATLAB
> indexing particularly of spectra) ?

No. Please see the replies I have given to the other people in this thread.

> this is a MATLAB function or your function?

It's my own function.


> this random f_cut signal is curious.

It's just a funny way to generate random filters.

"Jack" <jack@nospammers.please> wrote in message
news:43fe4465$0$67262$157c6196@dreader2.cybercity.dk...
> >
> > All you need is this
> > min_powerspectrum = min(power_spectra);
>
> I'm sorry, but you misunderstand the problem. I am not trying
> to implement the function in a MATLAB environment. The MATLAB
> program is just a simulation to show you what the function does.
>
> I am looking for a way to get rid of the big array but without
> loosing the functionality - that is: to always be able to calculate
> the minimum power spectrum among the 300 latest power
> spectra (I am doing this so I can adaptively estimate the background noise
> of a speech signal).

Well...you could just do a running minimum calculation.
You'll definitely need atleast 1 array of 512 points (assuming that's the
length of your spectrum). Initialize this one array (call it min_spectrum)
to zeros.
After every spectrum calculation, compare each point of your new spectrum
with your min_spectrum array. If a point on your new spectrum is smaller,
then update that element.

This will give you the minimum for all spectra (not just the last 300). I'd
assume that if you need atleast 300 for your results, having more will only
make it work better.
If you do need to make your min calculation a sliding window over the last
300...you're going to need the extra memory (and the computation to
repeatedly calculate minimums) - no way around it.

Cheers
Bhaskar

> I have thought a long and hard time about how I can get rid of
> the array and still be able to track the minimum power spectrum,
> but it doesn't look like it's possible. If it is I would love to hear
> about how I can do it...if not: then I would like to hear about better
> ways of doing it.
>
> Thank you.
>
>
>
>
>
>
>