Digital computer sliding-window minimum filter

• US 5,319,583 A
• Filed: 06/22/1992
• Issued: 06/07/1994
• Est. Priority Date: 06/22/1992
• Status: Expired due to Fees

• Current Assignee: General Electric Company
• Original Assignee: General Electric Company
• Inventors: Wildes, Douglas G.
• Primary Examiner(s): Malzahn, David H.
• Application Number:
  US07/902,171
• Time in Patent Office: 715 Days
• Field of Search: 364/724.01, 364/715.06
• US Class Current: 708/303
• CPC Class Codes: G01D 1/16 giving a value which is a function of two or more values, e.g. product or ratio
• CPC Class Codes: G06F 17/18 for evaluating statistical data , e.g. average values, frequency distributions, probability functions, regression analysis forecasting specially adapted for a specific administrative, business or logistic context G06Q10/04
• CPC Class Codes: H03H 17/026 Averaging filters

Abstract

The present invention comprises a buffer containing the signal values (digital data) currently within the sliding window, a list of data structures containing information about local minima and/or maxima within the buffer, and a method for updating the buffer and list as new signals are added to the window.

Claims

1. A method providing a sliding window filter with an average response time that is independent of the length of the sliding window which comprises:

adding new signal values to a digital data buffer; and

generating data structures and a list of the data structures, each data structure having information pertaining to local extreme digital data within said buffer, said local extreme digital data corresponding to a plurality of local extremes of said digital signal values;

storing said list of data structures;

adding new signal values to the buffer; and

updating said buffer and said list as new signal values are further added to said buffer; and

wherein said updating includes;

removing an oldest signal value from said buffer and from said data structure; and

adding a new signal to one of said data structures; and

wherein said local extremes include minimum signals and wherein;

said new signal is compared to a previous new minimum signal whereby the new signal becomes the new minimum if the new signal is less than or equal to the previous new minimum; and

a first search through the list of data structures whereby any minima greater than or equal to the new minimum are removed from said list; and

a second search where the maximum value of the next newest structure is compared to the minimum value of the newest structure whereby all maximum values greater than or equal to the new minimum are transferred into the new structure.

2. A method providing a sliding window filter with an average response time that is independent of the length of the sliding window which comprises:

adding new signal values to a digital data buffer; and

generating data structures and a list of the data structures, each data structure having information pertaining to local extreme digital data within said buffer, said local extreme digital data corresponding to a plurality of local extremes of said digital signal values;

storing said list of data structures;

adding new signal values to the buffer; and

updating said buffer and said list as new signal values are further added to said buffer; and

wherein said updating includes;

removing an oldest signal value from said buffer and from said data structure; and

adding a new signal to one of said data structures; and

wherein said local extremes include maximum signals and wherein;

said new signal is compared to a previous new maximum signal whereby the new signal becomes the new maximum if the new signal is greater than or equal to the previous new maximum; and

a first search through the list of data structures whereby any maxima less than or equal to the new maximum are removed from said list; and

a second search where the minimum value of the next newest structure is compared to the maximum value of the newest structure whereby all minimum values greater than or equal to the new maximum are transferred into the new structure.

3. A method providing a sliding window filter with an average response time that is independent of the length of the sliding window which comprises:

adding new signal values to a digital data buffer; and

generating data structures and a list of the data structures, each data structure having information pertaining to local extreme digital data within said buffer, said local extreme digital data corresponding to a plurality of local extremes of said digital signal values;

storing said list of data structures;

adding new signal values to the buffer; and

updating said buffer and said list as new signal values are further added to said buffer; and

wherein said updating includes;

removing an oldest signal value from said buffer and from said data structure;

adding a new signal to one of said data structures; and

wherein said local extremes include maximums and minimums and where the new signal is compared with a previous newest minimum and a previous newest maximum wherein;

if said new signal is less than or equal to the previous newest minimum the new signal becomes the new minimum, a first search is then conducted through the list of data structures during which all prior minima that are equal to or greater than the new minimum are removed from said list and absorbed into the new minimum structure and a second search through the list of data structures which transfers all maximum values of the next newest structure which are greater than or equal to the new minimum of the newest structure into the newest structure; and

if said new signal is greater than or equal to the previous maximum, the new signal becomes the new maximum; and

if the new signal is greater than the previous minimum and less than the previous maximum it becomes a new local minimum whereby a new structure is created and all maximum values of the previous structure which are greater than or equal to the new local minimum are transferred into said new structure.

4. A method providing a sliding window filer with an average response time that is independent of the length of the sliding window which comprises:

adding new signal values to a digital data buffer; and

generating data structures and a list of the data structures, each data structure having information pertaining to local extreme digital data within said buffer, said local extreme digital data corresponding to a plurality of local extremes of said digital signal values;

storing said list of data structures;

adding new signal values to the buffer; and

updating said buffer and said list as new signal values are further added to said buffer; and

wherein said updating includes;

removing an oldest signal value from said buffer and from said data structure;

adding a new signal to one of said data structures; and

wherein said local extremes include maximums and minimums and where the new signal is compared with a previous newest maximum and a previous newest minimum wherein;

if said new signal is greater than or equal to the previous newest maximum the new signal becomes the new maximum, a first search is then conducted through the list of data structures during which all prior maxima that are equal to or less than the new maximum are removed from said list and absorbed into the new maximum structure and a second search through the list of data structures which transfers all minimum values of the next newest structure which are greater than or equal to the new maximum of the newest structure into the newest structure; and

if said new signal is greater than or equal to the previous minimum, the new signal becomes the new minimum; and

if the new signal is less than the previous maximum and greater than the previous minimum it becomes a new local maximum whereby a new structure is created and all minimum values of the previous structure which are less than or equal to the new local maximum are transferred into said new structure.