Binary code converters and comparators

Details Binary code converters and comparators Binary code converters and comparators

1999-08-05

2001-07-17

Young, Brian (Department: 2819)

Coded data generation or conversion

Digital code to digital code converters

To or from constant distance codes

Reexamination Certificate

active

06262676

ABSTRACT:

BACKGROUND OF THE INVENTION
1. Field of the Invention
This invention relates to apparatus and methods for converting a weightless tuple or vector into thermometer code and also to apparatus and methods for determining the Hamming value comparator relationship of two thermometer codes or weightless vectors. The invention also extends to arrangements for converting 2-dimensional arrays of data into aggregate code in which set bits are aggregated or clustered around a focal bit position, in a manner analogous to that of converting 1-dimensional tuples or vectors, and such aggregate code is also referred to herein generally as thermometer code.
2. Discussion of 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 No. 9726752.0 or our co-pending International Patent Applications Nos. PCT/GB98/. . . , PCT/GB98/. . . , PCT/GB98/. . . , or PCT/GB98/. . . (our References XA1000, XA1154, XA1155, XA1156).
Terminology
The term “Hamming value” is used to define the number of bits set (i.e. 1's set) in 1-dimensional arrays such as a binary number, tuple, vector, or in 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”.
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.
Thermometer code converters may be used in the processing of two weightless vectors to compare 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 because 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.
SUMMARY OF THE INVENTION
Although of particular use in effecting Hamming value comparison, the thermometer code converters described herein may be used in many different applications.
According to one aspect this invention provides an encoder for converting a weightless binary array of one or more dimensions into a thermometer code as herein defined, said encoder comprising means for inputting said binary weightless array into processing means having a succession of one or more layers of bit manipulation cells each cell including at least two inputs and at least two outputs, and arranged to shift set bits in said array in the direction of a selected portion of said array, thereby to provide said thermometer code.
In some arrangements said processing means is operable to shift said set bits to one end of the array. Alternatively, said processing means may be operable to shift said set bits towards the centre of the array.
The bit manipulation cells may each have just two inputs and two outputs. In this instance on application of inputs, (a, b), the manipulator cell preferably provides outputs (Ya, Yb) as follows:
Ya=a # b
Yb=a & b,   (Equation Set (1))
where
190
is the OR function and & is the AND function
In another arrangement, the bit manipulation cells may have three inputs and three outputs. Here, on application of three inputs (a, b, c,) the manipulation cell preferably provides outputs (Ya, Yb, Yc), as follows:
Ya=a # b # c
Yb=(b & c) # (a & c) # (a & b)
Yc=a & b & c   (Equation Set (2))
In yet a further arrangement, the bit manipulation cells may have four inputs and four outputs. Here on application of four inputs (a, b, c, d), the manipulation cell preferably provides outputs (Ya, Yb, Yc, Yd) as follows:
Ya=a # b # c # d
 Yb=(d & c) # (d & b) # (d & a) # (c & b) # (c & a) # (b & a)
Yc=(d & c & b) # (d & c & a) # (d & b & a) # (c & b & a)
Yd=a & b & c & d   (Equation Set (3))
The parallel processing preferably means comprises alternate odd and even layers of respective odd and even numbers of bit manipulation cells, wherein in the odd layers the bit manipulation cells operate on adjacent bits starting on an even boundary of the binary string, and in the even layers, the bit manipulation cells preferably operate on adjacent bits s

Affiliated with

Also associated with

Rating

Binary code converters and comparators does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Binary code converters and comparators, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Binary code converters and comparators will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-2466403