Patent US3725875A successfully refreshed from Google Patents.
US3725875A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Probability sort in a storage minimized optimum processor
Assignee: Texas Instruments Inc
•
Filing: 1972-01-14
•
Granted: 1973-04-03
•
Expires: 1992-01-14
Abstract
Abstract A trainable signal processor having at least one input signal u and one desired output signal z applied thereto during training and having at least one actual output signal derived therefrom during execution is provided. From each member of the input sequence u(ti) a key Ki is generated. Ki may have only a finite number of values and is a single valued function of u. Corresponding to each value of the Ki generated during training, a trained response is derived from samples of the desired output signal z measured at those instances ti at which that value of Ki occurred. This operation is such that the contemporary value of the trained response is maintained in a tree allocated file. The file thereby associates with each key Ki a trained response. Storage is provided for only those Ki which actually occurred during training, which is an important attribute since these typically constitute a small fraction of those values which may theoretically occur, especially when the input is of multidimensional character. During execution the tree allocated file provides for efficient retrieval of the trained responses which are employed in determining the actual output signal of the processor. Whereas the tree allocation can greatly reduce the storage relative to that of the storage-wise inefficient method of direct addressing, the speed of operation is less due to the need to perform a sequence of operations on components of the key. Disclosed herein is a means of greatly improving the speed of the tree allocated file while retaining its advantages. The means involves control of the tree structure through a probability sorting operation which is effected periodically to arrange the nodes within the tree such that the modes of a filial set which are selected most frequently during training are placed near the entry node of the set. Specifically the node most likely to be selected is made the entry node of the set; it is chained to the node next most likely to be selected, etc., leaving the node least likely to be selected the terminal node of the set. This property holds for all sets of nodes within the tree.
Inventors
- 👤 W Choate
- 👤 M Masten
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-10-23 22:25
CPC Classifications
G; G06; G06F; G06F16/00; G06F16/90; G06F16/901; G06F16/9027
Claims Analysis
Total Claims: 9
Claim 1
Independent Claim
185 words
An automatic trainable signal processing system where a plurality of input signals u and corresponding trained responses Z are employed as training signals which comprises: a. means for quantizin samples of said signals u and Z; b. a random access memory having storage locations for storing each different combination of the quantized values of said input training signals; c. means to store said quantized values of said input training signals in said storage locations of said random access memory to establish with an entry node, families of retrievable trained responses Z for related combinations; d. means for comparing the number of times each unique combination is encountered during storage; e. means responsive to said comparing means for interchanging i. the storage location of the response function for one of said combinations, and ii. the storage location of the response function for any said combination whose response function is stored more remote from said entry node of the storage location of said random access memory and which combination is encountered more frequently than the combination whose response function is stored less remote from said entry node.
Claim 2
Dependent Claim
185 words
An automatic trainable signal processing system where a plurality of input signals u and corresponding trained responses Z are employed as training signals which comprises: a. means for quantizin samples of said signals u and Z; b. a random access memory having storage locations for storing each different combination of the quantized values of said input training signals; c. means to store said quantized values of said input training signals in said storage locations of said random access memory to establish with an entry node, families of retrievable trained responses Z for related combinations; d. means for comparing the number of times each unique combination is encountered during storage; e. means responsive to said comparing means for interchanging i. the storage location of the response function for one of said combinations, and ii. the storage location of the response function for any said combination whose response function is stored more remote from said entry node of the storage location of said random access memory and which combination is encountered more frequently than the combination whose response function is stored less remote from said entry node.
Claim 3
Dependent Claim
60 words
The combination set forth in claim 1 wherein means are provided for storing with each of said response functions a. the address of the next node in the filial set of which the response function is a member, and b. the address of the entry node of the next filial set in the storage locations of said random access memory.
Claim 4
Dependent Claim
84 words
The combination set forth in claim 1 wherein means are provided for storing as keys in the quantized values of said training signals as a chain in the storage locating of said ranDom access memory response function along with a. the address of the next node in the filial set to which the key belongs, b. the address of the entry node of the next filial set in said tree, and c. an indicia of the number of times said key has been addressed.
Claim 5
Dependent Claim
37 words
The combination set forth in claim 3 in which said interchange means includes selector means for interchange of a pair of keys, their addresses of the next nodes in the respective filial sets and their respective indicia.
Claim 6
Independent Claim
136 words
The method of training an automatic trainable signal processing machine comprising the steps of a. applying training signals to said automatic trainable signal processing machine, said training signals including at least one input signal along with a desired output signal Z; b. quantizing said training signals; c. in response to said training signals generating a distinctive response function for each new combination of values of said training signals; d. storing said response functions in a tree storage array in a random access memory in said machine; e. storing with each said response function indicia representative of the number of times the corresponding combination of training functions has been encountered, and f. interchanging in a given filial set the storage locations of said response functions to maintain them in said set in descending order of said indicia.
Claim 7
Independent Claim
136 words
The method of training an automatic trainable signal processing machine comprising the steps of a. applying training signals to said automatic trainable signal processing machine, said training signals including at least one input signal along with a desired output signal Z; b. quantizing said training signals; c. in response to said training signals generating a distinctive response function for each new combination of values of said training signals; d. storing said response functions in a tree storage array in a random access memory in said machine; e. storing with each said response function indicia representative of the number of times the corresponding combination of training functions has been encountered, and f. interchanging in a given filial set the storage locations of said response functions to maintain them in said set in descending order of said indicia.
Claim 8
Independent Claim
271 words
The method of training an automatic trainable signal processing machine comprising the steps of a. applying training signals to said automatic trainable signal processing machine, said training signals including at least one input signal along with a desired output signal Z; b. quantizing said training signals; c. in response to said training signals generating a distinctive response function for each new combination of values of said training signals; d. storing in memory and in time sequence the training signals along with a trained response for combination of values of the input signals in a tree storage array having levels corresponding in number with the number of said input signals; e. storing with each said value of the input signal i. the address of the next node in the filial set of which the value is a member, ii. the address of the entry node for the next filial set in said tree, iii. the number of times said value has been addressed at the last node in said tree, and iv. for each said combination of values storing a function representative of the trained response of said processor in dependence upon said combination of values and upon a desired processor output signal, f. intermediate selected storing sequences, comparing the number of times a given value has been addressed with the number of times the value in its filial set next closest the entry node to said filial set has been addressed, and g. in response to said comparison interchanging said values to maintain the values relative to the entry node in each said filial set in decreasing order of said number.
Claim 9
Independent Claim
271 words
The method of training an automatic trainable signal processing machine comprising the steps of a. applying training signals to said automatic trainable signal processing machine, said training signals including at least one input signal along with a desired output signal Z; b. quantizing said training signals; c. in response to said training signals generating a distinctive response function for each new combination of values of said training signals; d. storing in memory and in time sequence the training signals along with a trained response for combination of values of the input signals in a tree storage array having levels corresponding in number with the number of said input signals; e. storing with each said value of the input signal i. the address of the next node in the filial set of which the value is a member, ii. the address of the entry node for the next filial set in said tree, iii. the number of times said value has been addressed at the last node in said tree, and iv. for each said combination of values storing a function representative of the trained response of said processor in dependence upon said combination of values and upon a desired processor output signal, f. intermediate selected storing sequences, comparing the number of times a given value has been addressed with the number of times the value in its filial set next closest the entry node to said filial set has been addressed, and g. in response to said comparison interchanging said values to maintain the values relative to the entry node in each said filial set in decreasing order of said number.
References Cited (Backward Citations)
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 1976-04-02 | 1976-10-02 | 1977-04-03 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 1980-04-02 | 1980-10-02 | 1981-04-03 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 1984-04-02 | 1984-10-02 | 1985-04-03 | $7700.00 | Window Closed / Lapsed |