JPS60186979A - Calculating device for extent of difference - Google Patents

Abstract

PURPOSE:To simplify the circuit constitution of the difference extent calculating device by using an exclusive OR circuit which inputs sign bits of two tandem data and the most significant digit carry bit of the sum of one binary data and the other inverted data. CONSTITUTION:An adding circuit 10 adds data Ai expressed as a complement of ''2'' to data Bi' obtained by inverting data Bi through an inverting circuit 16. The most significant digit bits of the data Ai and Bi, i.e. code bits and the most significant carry digit bit outputted from the adding circuit 10 are inputted to the exclusive OR circuit (EOR circuit) 11, which decides which of the data Ai and Bi are larger. Every time the output data of a data converting circuit 12 and the logical output of the EOR circuit 11 are inputted to an adding circuit 13, the adding circuit 13 adds the input data to data stored in a register 14 to calculate the cumulative sum (difference extent).

Description

DETAILED DESCRIPTION OF THE INVENTION (1) Technical Field of the Invention The present invention particularly relates to a device that calculates the degree of dissimilarity between two data groups as a cumulative sum of absolute values of differences between data in both data groups.

(2) Background of the technology In general, in speech recognition or image recognition, an input audio pattern or image pattern is compared with a plurality of predetermined standard patterns, and among these standard patterns, the one with the smallest difference from the input cover pattern is selected. I try to use it as a recognition pattern. Then, as a measure of the difference between this input pattern and a standard pattern, for example, by extracting features in multiple dimensions, an input pattern consisting of multiple data (multidimensional) and a predetermined standard pattern consisting of data of the same dimension are used. It is possible to use a cumulative sum obtained by sequentially decorating the absolute value of the difference between each data value of the corresponding dimension in . That is, if the cumulative sum is large, the difference between the input cover pattern and the standard pattern is large, and if the cumulative sum is small, the phase 3ffl is small.

Therefore, in speech recognition or image recognition, a dissimilarity calculation device is required that calculates the differences between the data groups of the input pattern and the standard pattern as a cumulative sum as described above, and furthermore, the cumulative sum can be calculated as quickly as possible. There is a need for a device that can calculate the number of bars.

(3) Prior Art and Problems Conventionally, an example of this kind of dissimilarity calculation device is shown in FIG. 1, for example. Here, the binary data constituting the two target data groups A=(At) and B=(B+) is a positive or negative value, and its representation is, for example, n+1, for convenience in arithmetic processing. If it is a bit representation, At = an ・2' + A' A -= , + a , -, -2° -' +8, 1 .
e 2''+...+8+ 21 +a.2°a, ~a, :Q or 1, which is a so-called two's complement representation (the same applies to B+).

In Figure 1, 1 is the data group △ expressed in two's complement as described above, and the corresponding dimension data A1 and B of B.
+ A comparison circuit 2 that determines which size is inputted with the 1- data Ai and B1, and based on the determination result of the comparison circuit 1, data A+.

Multiplexer 3 that selects and outputs the more popular one of B1
inputs the inverted data (1's complement) obtained by inverting the data A+ and B+ by the inverting circuits 7a and 7h,
Based on the determination result in comparison circuit 1, data A+, B
A multiplexer 4 selectively outputs the smaller inverted data of 2.3 and the adder circuit 4 constitute a subtraction circuit that subtracts the smaller one from the larger one of the input data A+ and B+. That is, the output from the adder circuit 4 at the final stage is the data A1 and B: The absolute value of the difference is lA+ -F3+ I. The absolute value IA+ -8+ is output from the addition circuit 4 every time data from the data groups A1 and B is input.
1 is added by the adding circuit 5 to the previous addition result stored in the register 6, and this addition result is stored in the register 6 again, so that the final stored data in the register 6 becomes the data group mentioned above. , the cumulative sum of the absolute values of the differences of each data of the corresponding dimension in B, ΣlA+ −B+ l,
In other words, it is the degree of difference between data groups A and B.

In this way, the above difference calculation fj is performed by determining the magnitude of the data A+ and B+ that are sequentially input from the data groups A1 and 8, and then cumulatively adding the results of subtracting the smaller one from the preferred one. By configuring the system using Bartok Air, relatively high-speed processing can be achieved.

However, the dissimilarity calculation device as shown in FIG. This has the disadvantage that the circuit configuration is relatively complicated.

(4) Purpose of the Invention The present invention has been made in view of the above points (in particular, the accumulation of the absolute values of the differences between mutually corresponding data in two data groups consisting of binary data expressed in two's complement). sum of 8
Phase 3 to count by 1! ! The purpose is to realize the power meter paralysis U with a circuit configuration as simple as possible.

(5) Structure of the Invention In order to achieve the above object, the present invention is a device that calculates nl the absolute value of the difference between two binary data tables in which only negative numbers are expressed as two's complement. 2 of one of the binary data
Add the binary data and the inverted data of the other binary data r+
the adder circuit that outputs the sign hit of the two binary data and the highest 1: carry pick 1- output from the adder circuit.
is manually inputted, and a determination circuit that determines whether the two binary data are human or small based on the bit data, and output binary data other than the most significant carry bit from the adder circuit are added to the one binary data. When is larger than the other binary data, it is output as is, and when the one binary data is less than the other binary data, it is inverted and then output as "1".
'' and a circuit that adds and outputs the sum.

(6) Embodiments of the invention First, in the present invention, only negative numbers are 24! I
The basic logic of calculating the absolute value of the difference between two binary data expressed as -'s complement will be explained.

For example, let the sign pits (most significant pits) of two binary data X and Y, in which only negative numbers are expressed as two's complement in n+1 pits, be Xn and Vn, respectively, and the parts expressed by the remaining n pits, respectively. When X' and Y' are assumed, each data X and Y becomes a numerical value expressed as Other pits are treated in the same way, so X=x, .2''+X' Y=yn .2n+Y'.

Here, the inverted data (1's complement) of data X and data Y
Added data s4 with Y! - Considering, S=X+Y = (xn ・2"+X') + (yn ・2n +Y') = (xn > becomes.

In this deduction, if we take the carry from the n+1 (sign) bit as C1, 7, and the carry from n p] to 1] as C7, we get: 1) The end of xn'''01y0=1, that is, X≧ When O>Y, since Xn +Vn -・0, C...=0.

2) When x,=1, yn=o, l11. , ;straw, X<O≦Y, X, +yn =
io (binary value), so C, , , = 1.

3) When xn=Q, yn=o or x, -1, yn=1, the above addition data S is Xo→-yn=1, so S=2' + (X' + Y'), Since Y' is an n-pit representation, Y' = 21-
1-Y', and 3=2''-1+(X'-Y').

3-1 Here, when X>Y, X and Y have the same sign and XT>Y l, so S≧2
n+1, and there is a carry from the n+1 bit in the calculation of formula 0), c n,, = 1 3-2) On the other hand, when X≦Y, X and Y have the same sign and X'≦Y' Therefore, S≦2°＋
1-1 There is no difference in the digits from the n+i-th bit in the above operation, and C, 1, = O.

The following table shows the above relationships.

In other words, when X is larger than Y, the logical output of the exclusive OR of the most significant pits of X and Y and the most significant carry pit of S=X+Y is °゛1'', and when X>Y, ×o■Vn ■c ,,, = 1 ・・・・・・・・・
... (2) On the other hand, when X is less than Y,
Y(7) When the logical output of the exclusive OR of the -L bit and the most significant carry bit of S=X+Y is '0'' and X≦Y, x, ■Vn ■C11,, = O・・・・・・・・・・
... (3) becomes.

1/j (+) Formula C゛The added data S shown is S =
Since X + Y = X-12''' -1-Y, the absolute value of the difference between data X and Y is 1] = l
X-Y l becomes D=X-Y = S +1-2 "' when X>Y. Then, in history, S "' Cn, l" 2°o + S '111111
(4) (S' = s, + 2' +S, -, ・2°-
1+,,.

...10S1 ・21+S.・2°) Therefore, X n −yn s Cr (1 when as = 1)
-C1゜,・2"'+8'+-1-2"'=3
'+1...(5) When Xo=01yn=1, Cn, +=O, 1')=
S'-11-'2°゛1...(6) Expression (6) as n'
+1 p1 ~ Expressed as [)=S'to1. In other words, when X h< Y, there is a crowd, ×.

The absolute value of the difference between Y (r)==l
It is assumed that 71111 degrees of "1" are added to the external binary data S'.

The height of X>Y l"11-8'+1 ... (7) Also, the absolute value 1') = l X-Y l is -Y-X =-2"'- when X≦Y 1-S = 2"'-1-8' -Co,, ・2°", so Xn = Vn, Cnu-0's sword D = 2"-1-8'-8" -(n)× n-1, yn
When =o, Cn,, = 1, D = S -2'''
°°(9) When formula (9) is expressed as 04-1 Hira 1~, D=S. That is, when X is less than or equal to Y, the absolute value of the difference between X and Y D=l The inverted version screams.

When X≦Y, D=S'...(10) - (2) above
From formula, formula (3), formula (7), and formula (10), xo■V
nΦCo,, = 1 toggle 1) = l ).

-4"r', to calculate the absolute value of the difference between two binary data expressed in two's complement, first add one of the binary atters and the inverted data of the other, The exclusive OR output of the most significant carry bit of the addition result and the most significant bit of both binary data expressed as two's complement is ++ 1 +
+, 1"' is added to the binary data other than the most significant carry bit of the above addition result, and when the above exclusive OR output is 0", the most significant carry bit of the above addition result is added. The binary numbers other than 1 are inverted.

Below, -LFli'! An embodiment of the present invention that operates according to Ruimoto's theory will be described based on the drawings. .

FIG. 2 is a 1111 diagram showing an embodiment of Komei Ki.

In the figure, 1 is added to the data of the data group A expressed in 101.12's complement, and the inverted data B1 obtained by inverting the data 11i of the data group t3, which is similarly expressed in the 2's complement table Jlii, by the inverting circuit 16. A boosting circuit that boosts
11 is tenn1j data A1 and 13. The most significant bit of , that is, the sign bit, output from the adding circuit 10, is input, and the data △
1. Exclusive theory 1 to determine the size of B1! I! Sum circuit (1
12 is a data conversion circuit that inputs binary data other than the most significant carry bit output from the addition circuit 10 and converts and outputs the input data based on the logic output from the FOR circuit 11. The data conversion circuit 12 is an exclusive OR group 1- to which bit data is input for each bit output from the adder circuit 10.
12-1 to 12-n (hereinafter referred to as EOR gates) are provided, and the OR output from the EOR circuit 11 is connected to the other input terminal of the EOR gates 12-1 to 12-n.
The inverted bit data inverted by 7 is inputted, and the outputs of the FOR gates 1-12-1 to 12-n are used as the output of the data conversion circuit 12.

Further, 13 is an adder circuit, 14 is a register for storing output data from the adder circuit 13, and this decoration circuit 13,
and the register 14, each time the output data from the data conversion circuit 12 and the logical output from the EOR circuit 11 are input to the adder circuit 13, the adder circuit 13 adds the input data and the data stored in the register 14. The added data is then stored in the register 14 again, forming a so-called cumulative sum circuit.

Here, the adder circuit 10 uses the above formula (+1 (S = X
+ Y), the exclusive OR circuit 11 is a circuit that makes a judgment on the above formula 1 (3), and the data conversion circuit 12 is a circuit that realizes S' or S' in formulas (11) and (12). The adder circuit and the adder circuit 13 are constructed using equations (11) and (12) (D=S'-11, I
)=S').

Next, the three-dimensional data f! The operation will be explained using the tj calculation of the degree of difference in I', A, and B as an example.

A-(2,-3,4) B= (-2,1,2) For example, each data of the above data groups A and B is 2 with 4 pips 1-
Expressed as the complement of, A= (0010,1101,0100)13 = (
It becomes 1110,0001,0010+.

Lisu, △+ −=0010. B+ = 11-1
If 0 is input, the 1st path 10 will be A 1-t B + -0010-1OOO1= 00
11, and this binary data (0011) is manually input to the data conversion circuit 12. A1 and Bl, and the most significant digit from the adder circuit 10, F is rebit is (oio), so the logical output of the FOR circuit 11 is 0■1■0-1, and the input data to the data conversion circuit 12 ( ooii
) is output as is (0011') via the EOR gates 12-i to 12-n. Then, in the adder circuit 13, the output from the data conversion circuit 12, the logical output of the FOR circuit 11, and the data stored in the register 14, which has already been cleared, are added, and 0011→1 +0 = 01
00 The added data (0100) is stored in the register 14.

Next, when A+ = 1101, B, =oooi are input, the output of the adder circuit 10 is A + 1B + -1101-1-1110 = Jl
:'1011E01 (The logic output of the circuit 11 is 1Φ001=0, and the input data (ioii) to the data!ll'1ijl path 12 is
It is inverted via n and output as (0100).

Then, in the adder circuit 13, the output data (0100) from the data conversion circuit vIi12 and F, the logical output ``'0'''' of the OR circuit 11 and the stored data (01
00) is added and 0100+O+0100=1(100) The added data (1000) is stored in the register 14.

Furthermore, when A+ = 0100 and B + = 0010 are input, the output of the adder circuit 10 is A + + 8 + = 010 (Ll" 1101 =
:, 1. :0001 The logical output of the EOR circuit 11 becomes 0ΦOΦ1-1, and the input data (0001) to the data conversion circuit is output as is (0001) via the FOR game 1-. Then, the output of the addition t1 circuit 13 is 0001+
1 +1000=1010, so the added data (
0110) is stored in the register 14.

In this way, the γ-ta (1010) stored in the register 14 when the computation of the f-event group Δ, 13 is completed, the γ-ta (1010) is the data 1! The cumulative sum of the absolute values of the differences between mutually corresponding data in YA and B, that is, the difference ICE, in this case, the degree of difference is rlOJ
(decimal number).

As described above, in this embodiment, the most significant digit of the adder circuit 10 [gari bit] and the most significant bit 1- of the input data A+, B+
-C data A+, B+ by exclusive OR circuit with
The addition circuit 10 determines the magnitude of the
Data A is obtained by adding the conversion data of binary data other than ~ and the exclusive OR output.
＋.

Since the absolute value of the difference in B1 is determined, the multiplexer 2.3 that selects the data A+, 81 as in the '1J device shown in FIG.
The circuit configuration for determining the magnitude of is simplified.

FIG. 3 is a block diagram showing another embodiment of the present invention.

This embodiment has a configuration in which binary data other than the most significant carry bit from the adder circuit 1o and the logic output bit 1- of the EOR circuit 11 are stored in a register 15. Output and storage operations are performed in synchronization with the same clock. With such a configuration, the operation from inputting the data /'z, St to storing the data in the register 15,
After outputting data from register 15, register 14
Since the operations up to data storage are performed in parallel within the same clock synchronization, the clock cycle can be made smaller than in the case shown in Figure 2, and as a result, the overall processing speed of the device is even faster. can be converted into

(7) Effects of the invention [As explained in detail, according to the present invention, the absolute value of the difference between mutually corresponding data in two data groups consisting of binary data expressed in two's complement The dissimilarity liver sieve device that calculates the sum has a higher tr than previously thought.
This can be realized with an illuminating circuit configuration, and as a result, the stem processing speed can be further increased.

[Brief explanation of the drawing]

FIG. 1 is a block diagram showing a conventional phase zero degree calculating device, and FIGS. 2 and 3 are block diagrams showing embodiments of the present invention. 10, 13...Addition circuit 11...Exclusive OR circuit (FOR circuit) 12...
Data conversion circuit 14...Register patent Applicant
Fujitsu Limited

Claims (1)

[Claims] A device that calculates the absolute value of the difference between two pieces of binary data in which only negative numbers are expressed as two's complement, and which calculates the absolute value of the difference between one piece of the binary data and the other piece of binary data. The sign bit of the two binary data and the most significant carry bit 1~ output from the adder circuit are input to the adder circuit that adds the inverted data, and the bit data adds the two binary data. A determination circuit that determines whether it is large or small, and output binary data other than the most significant carry bit from the adder circuit, if the one binary data is greater than the other binary data, output as is. lno, one of the above two
and a circuit for inverting and then adding "1" and outputting the result when the binary data is less than or equal to the other binary data.