Error detection/correction and fault detection/recovery – Pulse or data error handling – Error/fault detection technique
Reexamination Certificate
1999-08-10
2001-12-11
Baker, Stephen M. (Department: 2133)
Error detection/correction and fault detection/recovery
Pulse or data error handling
Error/fault detection technique
C340S146200
Reexamination Certificate
active
06330702
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention
This invention relates to methods and apparatus for determining the Hamming values of binary vectors or arrays in general and in particular, but not exclusively, to methods and apparatus for use in determining the Hamming value relationship of a set of weightless bits otherwise referred to herein as a weightless tuple or weightless vector. The invention also relates to apparatus and methods for determining the Hamming value relationship of two thermometer codes or weightless vectors. The invention further extends to a Hamming value comparator for comparing the Hamming value relationship of two 2-dimensional arrays of data. The invention still further extends to sum and threshold devices using Hamming value comparators of this invention.
2. Discussion of the Prior Art
The apparatus and methods described herein may usefully incorporate, utilise, be used with or be incorporated into any of the apparatus or methods described in our co-pending U.K. Patent Application Nos. 9726752.0, 9823361.2, 9823385.1, 9823322.8, and U.S. patent application Ser. Nos. 09/366,568, 09/371,270, and 09/368,585 which is now U.S. Pat. No. 6,262,676, the entire contents of which are incorporated herein by reference.
Terminology
The term “Hamming value” is used to define the number of logic 1's set in 1-dimensional arrays such as a binary number, tuple, vector, or 2 or higher dimensional arrays. The Hamming value relationship of two binary numbers or arrays indicates which has the greater Hamming value or whether the Hamming values are the same.
The term “weighted binary” is used in the conventional sense to indicate that successive bit positions are weighted, particularly . . . 16, 8, 4, 2, 1, although other weighted representations are possible. “Weightless binary” is a set of binary digits 1 and 0, each representing just “1” and “0” respectively. There is no least significant bit (LSB) or most significant bit (MSB). The set of bits may be ordered or without order. If all the 1's are grouped together e.g. [111000] then the code is referred to as a thermometer code, thermocode or bar graph code, all collectively referred to herein as “thermometer codes”.
The term thermometer code is also used herein to describe arrays where the set bits are aggregated around a preset bit within the tuple, rather than aggregating towards one of the ends of the tuple. Likewise the term is also used to describe 2, 3 or higher dimensional arrays in which the set bits are clustered or aggregated around a preset focal bit position which may be anywhere within the array, e.g. at one corner or in the centre in a 2 or 3 dimensional array.
A set of weightless bits is referred to herein as a “weightless tuple” or “weightless vector” and these terms are not intended to be restricted to ordered sets.
In traditional neural networks, a real-valued synaptic value is multiplied by a synaptic connection strength or weight value, and summed with other similarly treated synapses before they are all summed and thresholded to form a neural output. The weight value is a real-valued synaptic connection strength and hence the common usage of the term “weighted neural network”. However, it is also possible to have binary RAM-based neural networks that do not employ real-valued connection weights but instead rely on the values of the binary bits being either 0 or 1. Accordingly, there are two contexts of weightlessness: without synaptic connection strength, and without binary code weighting. The arrangements described herein employ weightless binary manipulation mechanisms and may be used to engineer weightless artificial neural networks, otherwise referred to as weightless-weightless artificial neural networks.
In one context, this invention is concerned with the comparison of two weightless vectors in terms of their Hamming values. This process is broadly equivalent to the function of a binary neuron. If the neuron receives a vector, A, of weightless synaptic values (e.g. [10110010]), and a vector, T, of weightless neural threshold values (e.g. [00101000]), the neuron may be required to fire, when the Hamming value of A is greater than the Hamming value of T. In this example, the threshold, T, can be thought of as a set of inhibitory synaptic values which must be exceeded if the neuron is to be fired. This is one particular example of an instance where it is required to determine the Hamming value relationship between two binary vectors, but there are very many other types of systems requiring this or similar processing. For example, this comparison and the other techniques disclosed herein may be used in flight control systems, voting systems with redundancy, safety critical systems, telecommunications systems, decision making systems, and artificial intelligence systems, such as neural networks.
In a prior art arrangement, a state machine based system is used to count the number of 1's set and digital arithmetic units are used for the binary comparison. For each weightless vector, each bit is scanned sequentially and a counter or arithmetic register incremented accordingly to evaluate the Hamming value. Thereafter, the contents of the respective counters or arithmetic registers are compared to determine the Hamming value relationship. This prior art technique is suited to implementation in software, using a microprocessor or similar state machine.
However, this technique is slow and prone to both conductive and emissive radio frequency interference (RFI) as it relies principally on clocks, counters and microprocessors. Both the speed of operation and susceptibility to disruption or corruption by other noise makes such a system ill-suited for safety critical systems such as flight control systems. By way of illustration, a flight control system may need to make rapid decisions based on the instantaneous “HIGH” or “LOW” state of several transducers reporting various aspects of the aircraft operation; corruption of one of the inputs to the decision making process (caused e.g. by noise or RFI disruption) could result in misinterpretation of one of the inputs with the result that the decision making processor or neural network make the wrong decision with potentially catastrophic consequences.
British Patent No. 1,588,535 discloses an arrangement in which file words are searched one at a time and the Hamming distance between a file word and a search word measured. It is noted that the Hamming distance (i.e. the number of bits in which the two words differ), is quite different from the Hamming value comparison, which typically determines which of two binary vectors or tuples has the greatest number of logic 1's set.
SUMMARY OF THE INVENTION
Accordingly, disclosed herein are various mechanisms for determining the Hamming value relationships of two binary vectors which use asynchronous Boolean logical bit cell manipulation schemes which are very fast for small weightless systems. In addition these tend to be more RFI resilient and more fault-tolerant than the weighted binary alternatives.
In the first described arrangement, two weightless binary vectors are first converted separately into thermometer code and thereafter the thermometer codes are compared by a thermocode comparator to determine the Hamming value relationship.
In the two subsequent related schemes, two weightless vectors are compared in parallel, without requiring separate conversion into thermometer code and subsequent comparison. However, the thermometer code converter and the thermocode comparator may each be used in different applications and the invention extends to these per se.
According to one aspect of this invention there is provided a Hamming value comparator for determining the Hamming value relationship (as herein defined) of two one or more dimensional arrays of bits, which comprises means for applying said arrays to one or more bit manipulation cells or logic elements for performing at least one of a shift operation and a bit elimination operation to determine the Hamm
BAE Systems plc
Baker Stephen M.
Nixon & Vanderhye P.C.
LandOfFree
Hamming value determination and comparison does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Hamming value determination and comparison, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Hamming value determination and comparison will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2583027