US 5,473,731 AGranted

Lattice based dynamic programming classification system

AssigneeIntel Corporation

InventorDaniel Seligson

Life of this patent

Estimating the term…

Loading patent…

Abstract

An integrated circuit lattice chip for computation of dynamic programming (DP) recursions uses identical nodal processor units arranged in regular lattice form. Interconnections between processor units on the chip are programmable using non-volatile EEPROM connections. The nodal processor units have computing element for generating a distance metric representative of the difference between the i.sup.th and j.sup.th elements of the unknown and prototype vectors that is combined with a maximum partial or minimum cumulative distance metric of preselected set of lower order nodal processors to produce an optimal (maximum or minimum) cumulative distance value for unknown and prototype vector elements with indices equal to or less than (i, j). A network is also provided for identifying the optimal path through the lattice for use in designing a DP classification system.

Claims25

Dependent claims

A lattice-based dynamic programming (DP) classification system that compares an unknown vector with a prescribed set of prototype vectors comprising:

a) a lattice controller for system control, for system configuration, for selecting a prescribed prototype vector for comparison with the unknown vector for storing of processed results of a DP lattice network, for determining an optimal lattice path, and for determining an optimal cumulative distance value corresponding to the optimal lattice path;
b) a DP lattice network controlled by the lattice controller for producing processed results by use of processing means operating on the prescribed prototype vector and the unknown vector, the processing means comprising means for computing a cumulative distance between the unknown vector and a prototype vector, means for providing optimal path information to the lattice controller, a first set of input terminals for accepting the unknown vector, a second set of input terminals for accepting a prototype vector, a set of processed data output terminals for outputting the processed results, and a set of control terminals connected to the lattice controller for transmitting controlled lattice path information;
c) a vector generator controlled by the lattice controller comprising means for generating at the vector generator output terminals a prototype vector selected from the prescribed set of prototype vectors, the output terminals connected to the second set of the DP lattice network input terminals;
and
d) a vector quantizer (VQ) comprising a VQ code book of prescribed prototype vectors, with the VQ data input connected to the lattice controller for classifying the unknown vector based on the optimal lattice path by outputting a VQ code corresponding to a prescribed prototype vector that most closely corresponds to the unknown vector.

2 more elements

A modular chip large-scale integrated circuit, lattice-based dynamic programming nodal processor array for use in a vector classification system, the modular chip comprising:

a) a set of M-input terminals, indexed 1.ltoreq.i.ltoreq.M, for inputting an M-component unknown data vector;
b) a set of N-input terminals, indexed 1.ltoreq.j.ltoreq.N, for inputting an N-component prototype data vector;
c) a set of N-output terminals for outputting an N-component cumulative distance vector;
d) a set of lattice controller terminals for receiving control and configuration signals from a lattice controller and for sending status signals to a lattice controller;
e) a controller interface connected to the set of lattice controller terminals, the controller interface for formatting and sending status signals to a lattice controller, for generating and distributing control signals to on-chip nodal processors;
and
f) a lattice network having MXN nodal processors, each nodal processor indexed by a two-dimensional coordinate index (i,j) where index 1.ltoreq.i.ltoreq.M corresponds to the i.sup.th component of the M-component unknown data vector, and index 1.ltoreq.j.ltoreq.N corresponds to the j.sup.th component of the N-component prototype data vector, the (i,j) nodal processor comprising:
i) an output terminal for outputting a cumulative distance output signal;
ii) a first input terminal connected to the i.sup.th terminal of the set of M-input terminals;
iii) a second input terminal connected to the j.sup.th terminal of the set of N-input terminals;
iv) a local distance processor connected to the first input terminal and to the second input terminal, the local distance processor for producing at an output terminal a distance metric representative of the distance between the i.sup.th unknown vector component and the j.sup.th prototype vector component;
v) a comparator/selector circuit having a multiplicity of input cumulative distance terminals connected to the output terminal of a set of lower-order nodal processors having an unknown vector component index of i-1 and prototype vector component indices equal to (j-l) for 0.ltoreq.l.ltoreq.L where L represents a prescribed limit of elasticity, and an output data terminal, the comparator/selector circuit for presenting at the output data terminal a lower-order input cumulative signal distance corresponding to a smallest value of the set of lower-order processor output signals;
vi) an adder circuit with a first input connected to the local distance processor output terminal, a second input connected to the output data terminal of the comparator/selector circuit for producing at the adder circuit output a sum signal combining a signal from the first input and a signal from the second input, the sum signal being the (i,j) nodal processor output cumulative distance signal;
and
g) each (M,j) nodal processor adder circuit output connected to the j.sup.th terminal of the set of N-output terminals.

12 more elements

Dependencies are inferred from the claim text.