# US 2004/0205052 A1 · Modified binary search for optimizing efficiency of data collection time

> Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt

- Number: US 2004/0205052 A1
- Document ID: US20040205052A1
- Status: Published application
- Kind: A1
- Application number: 10/412,867
- Filed: 2003-04-14
- Published: 2004-10-14
- Earliest claimed: 2003-04-14
- Assignees: LSI Logic Corporation
- Inventors: Cary Gloor; Robert Benware; Robert Madge
- Web page: https://patentgrep.com/patent/US20040205052A1

## CPC

- G05B 19/41875: {characterised by quality surveillance of production}
- G05B 23/0235: {based on a comparison with predetermined threshold or range, e.g. "classical methods", carried out during normal operation; threshold adaptation or choice; when or how to compare with the threshold}
- G05B 2219/45204: Die, mould making
- Y02P 90/02: Total factory control, e.g. smart factories, flexible manufacturing systems [FMS] or integrated manufacturing systems [IMS]
- G05B: CONTROL OR REGULATING SYSTEMS IN GENERAL; FUNCTIONAL ELEMENTS OF SUCH SYSTEMS; MONITORING OR TESTING ARRANGEMENTS FOR SUCH SYSTEMS OR ELEMENTS (systems for controlling or regulating non-electric variables G05D; systems for regulating electric or magnetic variables G05F; control devices or systems insofar as characterised by mechanical features only G05G)
- Y02P: CLIMATE CHANGE MITIGATION TECHNOLOGIES IN THE PRODUCTION OR PROCESSING OF GOODS

## Abstract

A method for a modified binary search includes steps of: selecting a parameter having a distribution of values, selecting a probability density function representative of the distribution of values of the selected parameter, defining a substantially equal probability weighted binary test interval from the probability density function for each of a selected number of test intervals over a selected test range, translating the weighted binary test intervals to obtain a highest resolution at a target point of the selected parameter, and skewing the translated and weighted binary test intervals by a selected scaling function to generate a modified binary test interval for each of the selected number of test intervals over the selected test range.

## Claims

### Claim 1

A method for a modified binary search comprising steps of:
(a) selecting a parameter having a distribution of values;
(b) selecting a probability density function representative of the distribution of values of the selected parameter;
(c) defining a substantially equal probability weighted binary test interval from the probability density function for each of a selected number of test intervals over a selected test range;
(d) translating the weighted binary test intervals to obtain a highest resolution at a target point of the selected parameter; and
(e) skewing the translated and weighted binary test intervals by a selected scaling function to generate a modified binary test interval for each of the selected number of test intervals over the selected test range.

### Claim 2 (depends on 1)

The method of claim 1 further comprising a step of performing a linear search on a device under test to surround a pass/fail value of the selected parameter wherein each linear test interval includes a selected number of the modified binary test intervals.

### Claim 3 (depends on 2)

The method of claim 2 further comprising a step of starting the linear search from a selected starting interval.

### Claim 4 (depends on 2)

The method of claim 2 further comprising a step of performing a binary search from the surrounded pass/fail point using the modified binary test intervals.

### Claim 5 (depends on 1)

The method of claim 1 further comprising a step of maintaining a first cumulative sum of values of the selected parameter and a second cumulative sum of squared values of the selected parameter.

### Claim 6 (depends on 5)

The method of claim 5 further comprising a step of recalculating a mean and a standard deviation of the distribution of the selected parameter from the first cumulative sum and the second cumulative sum for a next device under test.

### Claim 7 (depends on 6)

The method of claim 6 further comprising a step of dynamically adjusting the modified binary test intervals for each device under test from the recalculated mean and standard deviation.

### Claim 8 (depends on 1)

The method of claim 1 wherein step (b) comprises selecting a Gaussian distribution function.

### Claim 9 (depends on 1)

The method of claim 1 wherein the selected scaling function is given substantially by the formula:
4 d ′ ⁡ ( n ) = { d ⁡ ( n ) * ( target ⁢ - ⁢ point - range ⁡ ( min ) ) ∑ 0 15 ⁢ d ⁡ ( n ) if ⁢ ⁢ 0 ≤ n ≤ 15 d ⁡ ( n ) * ( range ⁡ ( max ) - ( target ⁢ - ⁢ point ) ) ∑ 16 31 ⁢ d ⁡ ( n ) if ⁢ ⁢ 16 ≤ n ≤ 31
wherein d′(n) is a difference between two consecutive modified binary test intervals, n is a corresponding one of the selected number of test intervals, d(n) is a difference between two translated and weighted binary test intervals, range(min) is a minimum value in the selected test range, range(max) is a maximum value in the selected test range, and (target-point) is a target point in the selected test range.

### Claim 10 (depends on 1)

The method of claim 1 further comprising a step (f) of feeding forward a starting point and test intervals to a next device under test from one of a single value of a previous search, a mean of values from previous searches, and a nearest neighbor value from a previous search.

### Claim 11

A computer program product for a modified binary search comprising:
a medium for embodying a computer program for input to a computer; and
a computer program embodied in the medium for causing the computer to perform steps of:
(a) selecting a parameter having a distribution of values;
(b) selecting a probability density function representative of the distribution of values of the selected parameter;
(c) defining a substantially equal probability weighted binary test interval from the probability density function for each of a selected number of test intervals over a selected test range;
(d) translating the weighted binary test intervals to obtain a highest resolution at a target point of the selected parameter; and
(e) skewing the translated and weighted binary test intervals by a selected scaling function to generate a modified binary test interval for each of the selected number of test intervals over the selected test range.

### Claim 12 (depends on 11)

The computer program product of claim 11 further comprising a step of performing a linear search on a device under test to surround a pass/fail value of the selected parameter wherein each linear test interval includes a selected number of the modified binary test intervals.

### Claim 13 (depends on 12)

The computer program product of claim 12 further comprising a step of starting the linear search from a selected starting interval.

### Claim 14 (depends on 13)

The computer program product of claim 13 further comprising a step of performing a binary search from the surrounded pass/fail point using the modified binary test intervals.

### Claim 15 (depends on 11)

The computer program product of claim 11 further comprising a step of maintaining a cumulative sum of the selected parameter and a cumulative sum of the squared values of the selected parameter.

### Claim 16 (depends on 15)

The computer program product of claim 15 further comprising a step of recalculating a mean and a standard deviation of the distribution of the selected parameter from the cumulative sum of the selected parameter and the cumulative sum of the squared values of the selected parameter.

### Claim 17 (depends on 16)

The computer program product of claim 16 further comprising a step of dynamically adjusting the modified binary test intervals for each device under test from the recalculated mean and standard deviation.

### Claim 18 (depends on 11)

The computer program product of claim 11 wherein step (b) comprises selecting a Gaussian distribution function.

### Claim 19 (depends on 11)

The computer program product of claim 11 wherein the selected scaling function is given substantially by the formula:
5 d ′ ⁡ ( n ) = { d ⁡ ( n ) * ( target ⁢ - ⁢ point - range ⁡ ( min ) ) ∑ 0 15 ⁢ d ⁡ ( n ) if ⁢ ⁢ 0 ≤ n ≤ 15 d ⁡ ( n ) * ( range ⁡ ( max ) - ( target ⁢ - ⁢ point ) ) ∑ 16 31 ⁢ d ⁡ ( n ) if ⁢ ⁢ 16 ≤ n ≤ 31
wherein d′(n) is a difference between two consecutive modified binary test intervals n and n−1, d(n) is a difference between two consecutive translated and weighted binary test intervals n and n−1, range(min) is a minimum value in the selected test range, range(max) is a maximum value in the selected test range, and (target-point) is a target point in the selected test range.

### Claim 20 (depends on 11)

The computer program product of claim 11 further comprising a step of feeding forward a starting point and test intervals to a next device under test from one of a single value of a previous search, a mean of values from previous searches, and a nearest neighbor value from a previous search.
