Hi I am trying to implement a linear convolution of FIR IR and a large input sequence. The IR is symmetrical (L=11). I receive the data in frames of say 128 samples (could be less or more than this). The output exhibits problems at the frame boundaries. What is the best way of overcoming these boundary effects. I have tried saving L-1 input samples from the end of the previous frame, which I tag onto the front of the current frame, but the problems still exist. Thanks
Linear Convolution of input seuence split into frames
Started by ●May 13, 2009
Reply by ●May 13, 20092009-05-13
mistvan wrote:> Hi > > I am trying to implement a linear convolution of FIR IR and a large input > sequence. The IR is symmetrical (L=11). I receive the data in frames of say > 128 samples (could be less or more than this). The output exhibits problems > at the frame boundaries. What is the best way of overcoming these boundary > effects. I have tried saving L-1 input samples from the end of the previous > frame, which I tag onto the front of the current frame, but the problems > still exist.You haven't described your difficulty. If you receive your data in frames and then concatenate the frames, how is that different from receiving the data continuously? You aren't using FFT convolution for a mere 11-point convolution, are you? Jerry -- Engineering is the art of making what you want from things you can get. �����������������������������������������������������������������������
Reply by ●May 13, 20092009-05-13
>mistvan wrote: >> Hi >> >> I am trying to implement a linear convolution of FIR IR and a largeinput>> sequence. The IR is symmetrical (L=11). I receive the data in frames ofsay>> 128 samples (could be less or more than this). The output exhibitsproblems>> at the frame boundaries. What is the best way of overcoming theseboundary>> effects. I have tried saving L-1 input samples from the end of theprevious>> frame, which I tag onto the front of the current frame, but theproblems>> still exist. > >You haven't described your difficulty. If you receive your data in >frames and then concatenate the frames, how is that different from >receiving the data continuously? You aren't using FFT convolution for a >mere 11-point convolution, are you? > >Jerry >-- >Engineering is the art of making what you want from things you can get. >����������������������������������������������������������������������� >#No not using fft. I'm afraid it is not possible to concatenate the frames. It is real time 2d data. I apply the fir to each row of data within this 2d frame. Then wait for the next frame to process. I have plotted the input and output of one of the rows,this shows that the filtering is not happening at the frame boundaries. It is ok before and after. I'm new to dsp, so I might be barking up the wrong tree, but I thought this would work My procedure for a row within a frame is as follows a. filter the row (typically 128 samples, but this varys) b. save L-1 samples from end of current row for next row c. append the L-1 samples to the beginning of the next row d goto (a) Any ideas? Thanks
Reply by ●May 13, 20092009-05-13
mistvan <miklos@dbresearch.co.uk> wrote: <>mistvan wrote: <>> I am trying to implement a linear convolution of FIR IR and a <>> large input sequence. The IR is symmetrical (L=11). <>> I receive the data in frames of say 128 samples (could be less <>> or more than this). The output exhibits problems at the frame <>> boundaries. What is the best way of overcoming these boundary <>> effects. I have tried saving L-1 input samples from the end of <>> the previous frame, which I tag onto the front of the current <>> frame, but the problems still exist. (snip) < No not using fft. < I'm afraid it is not possible to concatenate the frames. < It is real time 2d data. I apply the fir to each row of data < within this 2d frame. Then wait for the next frame to process. < I have plotted the input and output of one of the rows,this < shows that the filtering is not happening at the frame < boundaries. It is ok before and after. I think you need to explain more about the data source. You describe it in rows, and as 2D data. If it is rows of 2D data then you should not save points from the end of the previous row to prepend to the beginning of the next row. Well, if you do it with FFT then you transform rows and then columns (or the other way around), as FFT is separable in rectangular coordinates. It seems that it should also be separable if done with IIR, but you will also want filters in the Y direction. Otherwise, I would recommend considering non-linear deconvolution. I only mentioned it here last week or so, but there is a book: "Deconvolution of Images and Spectra" by Jansson. Assuming your 2D data is image data, but even if it isn't. Well, the important thing about image and optical spectra is that intensity can never go negative, but linear deconvolution in signals with noise can easily go negative. That constraint in non-linear deconvolution makes a big difference in the result. In either case, explain what you mean by 2D data and rows. -- glen
Reply by ●May 14, 20092009-05-14
>mistvan <miklos@dbresearch.co.uk> wrote: ><>mistvan wrote: > ><>> I am trying to implement a linear convolution of FIR IR and a ><>> large input sequence. The IR is symmetrical (L=11). ><>> I receive the data in frames of say 128 samples (could be less ><>> or more than this). The output exhibits problems at the frame ><>> boundaries. What is the best way of overcoming these boundary ><>> effects. I have tried saving L-1 input samples from the end of ><>> the previous frame, which I tag onto the front of the current ><>> frame, but the problems still exist. >(snip) > >< No not using fft. > >< I'm afraid it is not possible to concatenate the frames. >< It is real time 2d data. I apply the fir to each row of data >< within this 2d frame. Then wait for the next frame to process. >< I have plotted the input and output of one of the rows,this >< shows that the filtering is not happening at the frame >< boundaries. It is ok before and after. > >I think you need to explain more about the data source. > >You describe it in rows, and as 2D data. If it is rows of >2D data then you should not save points from the end of the >previous row to prepend to the beginning of the next row. > >Well, if you do it with FFT then you transform rows and then >columns (or the other way around), as FFT is separable in >rectangular coordinates. It seems that it should also be separable >if done with IIR, but you will also want filters in the Y direction. > >Otherwise, I would recommend considering non-linear deconvolution. > >I only mentioned it here last week or so, but there is a book: >"Deconvolution of Images and Spectra" by Jansson. Assuming your >2D data is image data, but even if it isn't. Well, the important >thing about image and optical spectra is that intensity can never >go negative, but linear deconvolution in signals with noise can >easily go negative. That constraint in non-linear deconvolution >makes a big difference in the result. > >In either case, explain what you mean by 2D data and rows. > >-- glen > >Hi The data is from a radar source. The 2 dimensions are range (columns) and azimuth angle (rows). We require filtering in azimuth not range. The system receives a 2d frame of azimuth samples (typically 128) for all range (typically 1024 samples). I process this frame row by row, filtering in azimuth (rows) only The entire scan (every 2s) consists of 2048 azimuth samples. I need to maintain proper filtering across the frame boundaries Thanks
Reply by ●May 14, 20092009-05-14
mistvan wrote:>> mistvan <miklos@dbresearch.co.uk> wrote: >> <>mistvan wrote: >> >> <>> I am trying to implement a linear convolution of FIR IR and a >> <>> large input sequence. The IR is symmetrical (L=11). >> <>> I receive the data in frames of say 128 samples (could be less >> <>> or more than this). The output exhibits problems at the frame >> <>> boundaries. What is the best way of overcoming these boundary >> <>> effects. I have tried saving L-1 input samples from the end of >> <>> the previous frame, which I tag onto the front of the current >> <>> frame, but the problems still exist. >> (snip) >> >> < No not using fft. >> >> < I'm afraid it is not possible to concatenate the frames. >> < It is real time 2d data. I apply the fir to each row of data >> < within this 2d frame. Then wait for the next frame to process. >> < I have plotted the input and output of one of the rows,this >> < shows that the filtering is not happening at the frame >> < boundaries. It is ok before and after. >> >> I think you need to explain more about the data source. >> >> You describe it in rows, and as 2D data. If it is rows of >> 2D data then you should not save points from the end of the >> previous row to prepend to the beginning of the next row. >> >> Well, if you do it with FFT then you transform rows and then >> columns (or the other way around), as FFT is separable in >> rectangular coordinates. It seems that it should also be separable >> if done with IIR, but you will also want filters in the Y direction. >> >> Otherwise, I would recommend considering non-linear deconvolution. >> >> I only mentioned it here last week or so, but there is a book: >> "Deconvolution of Images and Spectra" by Jansson. Assuming your >> 2D data is image data, but even if it isn't. Well, the important >> thing about image and optical spectra is that intensity can never >> go negative, but linear deconvolution in signals with noise can >> easily go negative. That constraint in non-linear deconvolution >> makes a big difference in the result. >> >> In either case, explain what you mean by 2D data and rows. >> >> -- glen >> >> > > Hi > > The data is from a radar source. The 2 dimensions are range (columns) and > azimuth angle (rows). We require filtering in azimuth not range. The system > receives a 2d frame of azimuth samples (typically 128) for all range > (typically 1024 samples). > > I process this frame row by row, filtering in azimuth (rows) only > > The entire scan (every 2s) consists of 2048 azimuth samples. > > I need to maintain proper filtering across the frame boundariesFilters have startup and ending transients. there is nothing to be done about that. Since 11 samples are needed to fill your filter, the first and last ten outputs will be parts of the transients. You may be able to mitigate it, but you can't avoid it. Jerry -- Engineering is the art of making what you want from things you can get. �����������������������������������������������������������������������
Reply by ●May 14, 20092009-05-14
On May 13, 7:03�pm, "mistvan" <mik...@dbresearch.co.uk> wrote: Jerry sez:> > ...You aren't using FFT convolution for a > > mere 11-point convolution, are you?...> > No not using fft. > > I'm afraid it is not possible to concatenate the frames. It is real time > 2d data. I apply the fir to each row of data within this 2d frame. Then > wait for the next frame to process. I have plotted the input and output of > one of the rows,this shows that the filtering is not happening at the frame > boundaries. It is ok before and after. > > I'm new to dsp, so I might be barking up the wrong tree, but I thought > this would work > > My procedure for a row within a frame is as follows > a. filter the row (typically 128 samples, but this varys) > b. save L-1 samples from end of current row for next row > c. append the L-1 samples to the beginning of the next row > d �goto (a) > > Any ideas?well, this is the overlap-save technique which is what you would have to do frame-by-frame, whether you were using the FFT or not. so each time you filter a row, how many samples do you get out? 128 or 128-(L-1)? r b-j
Reply by ●May 14, 20092009-05-14
>On May 13, 7:03=A0pm, "mistvan" <mik...@dbresearch.co.uk> wrote: > >Jerry sez: >> > ...You aren't using FFT convolution for a >> > mere 11-point convolution, are you? >... >> >> No not using fft. >> >> I'm afraid it is not possible to concatenate the frames. It is realtime>> 2d data. I apply the fir to each row of data within this 2d frame.Then>> wait for the next frame to process. I have plotted the input and outputo=>f >> one of the rows,this shows that the filtering is not happening at thefra=>me >> boundaries. It is ok before and after. >> >> I'm new to dsp, so I might be barking up the wrong tree, but I thought >> this would work >> >> My procedure for a row within a frame is as follows >> a. filter the row (typically 128 samples, but this varys) >> b. save L-1 samples from end of current row for next row >> c. append the L-1 samples to the beginning of the next row >> d =A0goto (a) >> >> Any ideas? > >well, this is the overlap-save technique which is what you would have >to do frame-by-frame, whether you were using the FFT or not. > >so each time you filter a row, how many samples do you get out? 128 >or 128-(L-1)? > >r b-j > >Hi Thanks everyone for taking the time to respond. For each frame, I append (L-1) samples to the beginning of the current frame from the previous frame. So my input frame is now 128 + (11-1)= 138 samples. I convolve this with my filter, resulting in an ouput of 138 + (10 -1) = 147 output samples. I take my 128 output samples starting at sample number 11. The remaining output samples at the end are discarded. I then save the end 10 samples from the 'input' ready for the arrival of the next frame. Is this the correct procedure? Thanks
Reply by ●May 14, 20092009-05-14
mistvan wrote:>> On May 13, 7:03=A0pm, "mistvan" <mik...@dbresearch.co.uk> wrote: >> >> Jerry sez: >>> > ...You aren't using FFT convolution for a >>>> mere 11-point convolution, are you? >> ... >>> No not using fft. >>> >>> I'm afraid it is not possible to concatenate the frames. It is real > time >>> 2d data. I apply the fir to each row of data within this 2d frame. > Then >>> wait for the next frame to process. I have plotted the input and output > o= >> f >>> one of the rows,this shows that the filtering is not happening at the > fra= >> me >>> boundaries. It is ok before and after. >>> >>> I'm new to dsp, so I might be barking up the wrong tree, but I thought >>> this would work >>> >>> My procedure for a row within a frame is as follows >>> a. filter the row (typically 128 samples, but this varys) >>> b. save L-1 samples from end of current row for next row >>> c. append the L-1 samples to the beginning of the next row >>> d =A0goto (a) >>> >>> Any ideas? >> well, this is the overlap-save technique which is what you would have >> to do frame-by-frame, whether you were using the FFT or not. >> >> so each time you filter a row, how many samples do you get out? 128 >> or 128-(L-1)? >> >> r b-j >> >> > > Hi > > Thanks everyone for taking the time to respond. > > For each frame, I append (L-1) samples to the beginning of the current > frame from the previous frame. So my input frame is now 128 + (11-1)= 138 > samples. I convolve this with my filter, resulting in an ouput of 138 + (10 > -1) = 147 output samples.Are the appended samples in any way related to the rest, or are they arbitrary filler?> I take my 128 output samples starting at sample number 11. The remaining > output samples at the end are discarded. I then save the end 10 samples > from the 'input' ready for the arrival of the next frame. > > Is this the correct procedure?I don't think so. If the frames are independent, you can't avoid losing the margins. Jerry -- Engineering is the art of making what you want from things you can get. �����������������������������������������������������������������������
Reply by ●May 15, 20092009-05-15
>mistvan wrote: >>> On May 13, 7:03=A0pm, "mistvan" <mik...@dbresearch.co.uk> wrote: >>> >>> Jerry sez: >>>> > ...You aren't using FFT convolution for a >>>>> mere 11-point convolution, are you? >>> ... >>>> No not using fft. >>>> >>>> I'm afraid it is not possible to concatenate the frames. It is real >> time >>>> 2d data. I apply the fir to each row of data within this 2d frame. >> Then >>>> wait for the next frame to process. I have plotted the input andoutput>> o= >>> f >>>> one of the rows,this shows that the filtering is not happening atthe>> fra= >>> me >>>> boundaries. It is ok before and after. >>>> >>>> I'm new to dsp, so I might be barking up the wrong tree, but Ithought>>>> this would work >>>> >>>> My procedure for a row within a frame is as follows >>>> a. filter the row (typically 128 samples, but this varys) >>>> b. save L-1 samples from end of current row for next row >>>> c. append the L-1 samples to the beginning of the next row >>>> d =A0goto (a) >>>> >>>> Any ideas? >>> well, this is the overlap-save technique which is what you would have >>> to do frame-by-frame, whether you were using the FFT or not. >>> >>> so each time you filter a row, how many samples do you get out? 128 >>> or 128-(L-1)? >>> >>> r b-j >>> >>> >> >> Hi >> >> Thanks everyone for taking the time to respond. >> >> For each frame, I append (L-1) samples to the beginning of the current >> frame from the previous frame. So my input frame is now 128 + (11-1)=138>> samples. I convolve this with my filter, resulting in an ouput of 138 +(10>> -1) = 147 output samples. > >Are the appended samples in any way related to the rest, or are they >arbitrary filler? > >> I take my 128 output samples starting at sample number 11. Theremaining>> output samples at the end are discarded. I then save the end 10samples>> from the 'input' ready for the arrival of the next frame. >> >> Is this the correct procedure? > >I don't think so. If the frames are independent, you can't avoid losing >the margins. > >Jerry >-- >Engineering is the art of making what you want from things you can get. >����������������������������������������������������������������������� >Yes , the frames are related. It is one long sequence. When you say 'you cant avoid losing the margins'. Could you elaborate. I thought that with an FIR filter the current output sample is the convolution sum of a number of previous input samples multiplied by the corresponding coefficients. If I save these previous input samples (in my case this would be 11 -1 samples) then why will I have problems at the margins. Thanks for your time, much appreciated
