Device for computing eigenvalues of matrices

 

(57) Abstract:

The invention relates to computer technology and can be used in specialized solvers for the solution of problems, including digital processing of signals and images. The technical result of the claimed invention is enhanced functions when solving problems of digital processing of signals and images by obtaining the eigenvalues of matrices in the form of a single microoperation. For this purpose, the claimed device comprises registers, switches, block transformation matrix, the memory block is constant and the control unit. 2 C.p. f-crystals, 3 ill.

The invention relates to computing, is designed to obtain the eigenvalues by bringing the original matrix to a special form and can be used for solving problems of digital processing of signals and images in specialized computing systems operating in real time.

A device for module definition three-dimensional vector, containing the first, second, and third registers, the first, second and third adders-myCitadel, the first and second switches, the first decoder snottily connected to information inputs respectively of the first, the second and third registers, the control inputs of the first and second switches connected to the input of the number of iteration of the device, and providing the module definition three-dimensional vector (A. C. 1142830, Ál. G 06 F 7/544, 1985).

The disadvantage of this device is the input number of iteration that requires an external control circuits and complicates the management device.

Closest to the invention is a device for the module-definition three-dimensional vector containing the three cases, three switches, the unit changes sign, decoder, three arithmetic unit, two adder-vicites and the memory block constants, and the first and second inputs of the first vicites i-th arithmetic unit (i = 1, 3) are the first and second information inputs of the i-th arithmetic unit, the output of the first adder-vicites i-th arithmetic unit connected to the first input of the second adder-vicites block whose output is the output of the i-th arithmetic unit, the fifth information the input of which is connected to the second input of the second adder-vicites unit, the control inputs of the first and second adders-vychitala block are first and second symbolic inputs of the i-th Arif the ski unit, the second and fifth information inputs which are connected respectively with the first output of the first switch and the first output of the third switch, the output of the first arithmetic unit is connected with the first information input of the first register, the second outputs of the first, second and third registers respectively connected to information inputs of the first, second and third switches, the output of the second arithmetic unit is connected with the information input unit changes sign, the first output of the third switch is connected to a second information input of the third arithmetic unit (A. C. 2040039, Ál. G 06 F 7/544, 1995).

The disadvantage of this device is the presence of arithmetic units that transform individual component of the vector that does not provide a solution to the problem of computing eigenvalues of matrices and limits the scope of application of the device.

These devices have low technical level, due to the presence of arithmetic units, which are designed to handle a separate component of three-dimensional vectors, and thus can not provide parallel processing component of the matrix, leading to increased time spent Soi processing of signals and images.

In this regard, the most important task is the creation of a new device for computing eigenvalues of matrices with a new block matrix transformations for parallel processing of its components. The unit transformation matrix performs serial conversion of the original matrix with fixed arguments, which allows you to perform these transformations in one step with any prescribed accuracy. The resulting conversion values are used to update the component transform matrix.

The technical result of the claimed device is enhanced functions when solving problems that require finding the eigenvalues of a large number of matrices in real time, namely the possibility of finding the eigenvalues of matrices in the form of a single microoperation by introducing a new transformation matrix. This can improve performance when solving problems of digital signal processing and simplifies the management device.

The invention consists in that in a device for computing eigenvalues of matrices, containing four of the register, the four switches, the memory block covino with the information inputs of the first, second, third and fourth switches, input and output control unit connected respectively to the input of the start of the calculation and output of completing calculation of the control inputs of the first, second, third and fourth registers are connected to first control the output control unit, output the number of iteration which is connected to the input of the memory block is constant, the output of which is connected to control inputs of the first, second, third and fourth switches, put the unit transformation matrix, the first and twelfth informational inputs which are connected respectively with the first and second outputs of the fourth switch, the second and the fourth information unit conversion matrix are connected respectively with the first and second outputs of the first switch, the eleventh, ninth, fifth, and third information input unit conversion matrix are connected respectively to the outputs of the first, second, third and fourth registers, the eighth and the sixth information input unit conversion matrix are connected respectively with the first and second outputs of the second switch, the seventh and tenth the information input unit conversion matrix are connected respectively with the first inany respectively with the second and third control outputs of the control unit, the first, second, third and fourth outputs of the conversion unit matrixes respectively connected to information inputs of the fourth, third, second and first registers.

The unit transformation matrix contains three myCitadel, seven adders-vychitala and three elements of addition modulo two, and the first and second information input unit conversion matrix are connected respectively with the first and second inputs of the first myCitadel, the output of which is connected with the first inputs of the first, second and third elements of addition modulo two and second information inputs of the fifth and sixth adders-vychitala, third and fourth information unit conversion matrix are connected respectively with the first and second information inputs of the first adder-myCitadel, the output of which is connected to the first information input of the fourth adder-myCitadel, the fifth and sixth information input unit conversion matrix are connected respectively with the first and second inputs of the second myCitadel, the output of which is connected to the first information input of the fifth adder-myCitadel, seventh and eighth informational inputs conversion unit matrix soedinenie with the second inputs of the first, the second and third elements of addition modulo two and second information inputs of the fourth and seventh adders-vychitala, ninth and tenth informational inputs conversion unit matrix are connected respectively with the first and second inputs of the third myCitadel, the output of which is connected to the first information input of the sixth adder-myCitadel, eleventh and twelfth informational inputs conversion unit matrix are connected respectively with the first and second information input of the third adder-myCitadel, the output of which is connected to the first information input of the seventh adder-myCitadel, the first control input of the conversion unit matrixes connected to control inputs of the first, the second and third adders-vychitala and with the third input of the second element of addition modulo two, the second control input of the conversion unit matrixes connected to the third input of the third element of addition modulo two, the output of the first element addition module but two connected with the control input of the fifth adder-myCitadel, the output of the second element of addition modulo two is connected with the control input of the fourth adder-myCitadel, the output of the third element, W is Oh, fifth, sixth and seventh adders-vychitala connected respectively to the first, second, third and fourth outputs of the block transformation matrix.

The control unit includes a pulse generator, two elements And two trigger, counter, and two decoder, the beginning of the calculation control unit is connected to the input of the first trigger and the inverting input of the first element And whose output is connected to the reset input of the first trigger, the inverted output of which is connected to the output end of the calculation control unit, the direct output of the first flip-flop is connected to a second input of the second element And the output of the pulse generator is connected to the first input of the second element And whose output is connected to first control the output control unit and a counter input the output of which is connected to the output of the number of iteration control unit and inputs of the first and second decoders, the output of the first decoder is connected to the input of the second trigger, the output of the second decoder is connected to reinvestiruet the input of the first element And the reset input of the second trigger, direct and inverted outputs of which are connected respectively with the second and third control outputs of the unit upravni information sources and identify sources contains information about the equivalents of the claimed solution, allowed to establish that the applicant is not detected similar, characterized by signs, identical to all the essential features of the claimed invention. The definition from the list of identified unique prototype as the closest solutions to the totality of symptoms revealed a set of essential towards perceived by the applicant to the technical result of the distinctive features in the claimed object set forth in the claims.

Therefore, the claimed requirement meets the requirement of "novelty" by applicable law.

To verify compliance of the claimed invention to the requirement of "inventive step", the applicant conducted an additional search of the known solutions with the purpose of revealing of signs consistent with a non-prototype features of the claimed invention, the results of which show that the claimed invention for a specialist does not follow from the prior art.

Therefore, the claimed invention meets the requirement of "inventive step".

In Fig. 1 presents a functional diagram of the device of Fig. 2 - the inherent values of the matrix (Fig. 1) includes first to fourth registers 1-4, first to fourth switches 5-8, block 9 transformation matrix, block 10 memory constants, the control block 11, and the input 12 of the beginning of the computation and the output 13 of the completion of the computation.

The conversion unit matrixes (Fig. 2) contains the first myCitadel 14, the first adder-myCitadel 15, the second myCitadel 16, the second adder-myCitadel 17, the third myCitadel 18, the third adder-myCitadel 19, from first to third elements 20-22 addition modulo two, the fifth to seventh adders-myCitadel 23-26, and from the first to the twelfth inputs 27-38 information, the first and second inputs 39-40 managers and first to fourth outputs 41-44 information.

The first 27 and second 28 information input unit 9 to convert the matrix are connected respectively with the first and second inputs of the first vicites 14, the output of which is connected with the first inputs of the first 20, second 21 and third 22 elements of addition modulo two and second information inputs 24 fifth and sixth adders 25-vychitala. Third 29 and 30 fourth information input unit 9 transformation matrix are connected respectively with the first and second information inputs of the first adder-vicites 1 32 information input unit 9 transformation matrix are connected respectively with the first and second inputs of the second vicites 16, the output of which is connected to the first information input of the fifth adder-vicites 24. Seventh 33 and 34 eighth informational inputs of block 9 in the transformation matrix are connected respectively with the first and second information inputs of the second adder-vicites 17, the output of which is connected to the second inputs of the first 20, second 21 and third 22 elements of addition modulo two and second information inputs 23 fourth and seventh 26 adders-vychitala. Ninth 35 and tenth 36 information input unit 9 transformation matrix are connected respectively with the first and second inputs of the third vicites 18, the output of which is connected to the first information input of the sixth adder-vicites 25. Eleventh 37 and twelfth 38 information input unit 9 transformation matrix are connected respectively with the first and second information input of the third adder-vicites 19, the output of which is connected to the first information input of the seventh adder-vicites 26. The first control input 39 of the block 9 transformation matrix is connected to control inputs of the first 15, second 17 and third 19 adders-vychitala and with the third input of the second element 21 of addition modulo two. The second control is the I the d the first element 20 of the addition modulo two is connected with the control input of the fifth adder-vicites 24. The output of the second element 21 of addition modulo two is connected with the control input of the fourth adder-vicites 23. The output of the third element 22 of addition modulo two is connected to control inputs of the sixth 25 and 26 seventh adders-vychitala. The outputs 23 fourth, fifth, 24, 25 sixth and seventh 26 adders-vychitala connected respectively with the first 41, second 42, 43 third and fourth 44 outputs of block 9 in the transformation matrix.

The control unit (Fig. 3) consists of a generator 45 pulses of the first element And 46, the first flip-flop 47, the second element And 48, the counter 49, the first and second decoders 50 and 51, the second trigger 52. In addition, there are the first output 53 managing, exit 54 rooms iteration, second and third outputs 55 and 56 control, the input 12 of the beginning of the computation and the output 13 of the completion of the computation.

The input 12 of the beginning of the calculations connected with the input set the first flip-flop 47 and the inverting input of the first element And 46, the output of which is connected to the reset input of the first trigger 47, the inverted output of which is connected to the output 13 of the completion of the computation. Direct the output of the first flip-flop 47 is connected to a second input of the second element And 48. The output of the generator 45 pulses is connected to the first input of Vtorov the output of which is connected to the output 54 of the number of iteration unit 11 and control inputs of the first 50 and second 51 decoders. The output of the first decoder 50 is connected to the input of the second trigger 52. The output of the second decoder 51 is connected to reinvestiruet the input of the first element And 46 and the reset input of the second trigger 52, the direct and inverted outputs of which are connected respectively with second 55 and 56 third control outputs of the control block 11.

The output of the first register 1 (Fig. 1) is connected with the eleventh information input unit 9 transformation matrix and an information input of the first switch 5, the first and second outputs of which are connected respectively with the second and fourth information input unit 9 transformation matrix. The output of the second register 2 is connected to the ninth information input unit 9 transformation matrix and an information input of the second switch 6. the first and second outputs of which are connected respectively with the eighth and the sixth information input unit 9 transformation matrix. The output of the third register 3 is connected with the fifth information input unit 9 transformation matrix and an information input of the third switch 7, the first and second outputs of which are connected respectively with the seventh and tenth the information input unit 9 transformation matrix. Fourth fourth switch 8, the first and second outputs of which are connected respectively with the first and twelfth informational inputs of block 9 in the transformation matrix. The fourth, third, second and first outputs of block 9 in the transformation matrix are connected respectively with the information inputs of the first, second, third and fourth registers 1-4, the control inputs of which are connected to first control the output of the control block 11. Output the number of iteration of the control block 11 is connected to the input unit 10 memory constants, the output of which is connected to control inputs of the first, second, third and fourth switches 5-8. The second and third control outputs of the control block 11 are connected respectively with the first and second control inputs of block 9 in the transformation matrix.

The proposed device performs serial conversion of the original matrix with fixed arguments, which allows to bring the matrix to one of the special types, namely diagonal or block-diagonal, and get her own values with any prescribed accuracy.

The device operates as follows.

The operation of the device is expressed by dependency

< / BR>
< / BR>
Calculating aczeniami are components of the original matrix, eigenvalues which you want to receive.

Before beginning the iterative process in the registers 1, 2, 3 and 4 respectively are logged asynchronously components (a22and21, a12and a11the original matrix (Fig. 1). After that, you must generate a pulse at the input 12 of the beginning of the calculation. With the beginning of the next iteration output the number of iteration unit 11 of the control signal to the block 10 memory constants, with which i parameter dependencies (1) and (2) is supplied to control inputs of the switches 5, 6, 7 and 8, configuring them so that their first shot number (a22and21, a12and a11respectively), shifted by i bits toward the least significant bits, and the second - 2i bits toward the least significant bits. Thus, for informational inputs from the first to the twelfth block 9 transformation matrix serves a11(i)2-i, a22(i)2-i, a11(i), a22(i)2-2i, a12(i), a21(i)2-2i, a12(i)2-i, a21(i)2-i, a21(i), a12(i)2-2i, a22(i)and a11(i)2-2iand outputs first to fourth polulitra 4, 3, 2 and 1, respectively. The second and third control outputs of the control block 11 serves respectively to the first and second control inputs of the block 9 transformation matrix and set it to the dependencies (1) or (2). After all iterations, the matrix is drawn in a diagonal or block-diagonal form, its components contain their own values, and the output 13 of the completion of the computation is set active high level. The computed eigenvalues are stored in registers 1-4.

Unit 9 transformation matrix operates in the following way (Fig. 2).

The outputs of the first vicites 14, the first adder-vicites 15, the second vicites 16, the second adder-vicites 17, the third vicites 18 and the third adder-vicites 19 are respectively (a11(i)- a22(i))2-i(a11(i)+ a22(i)2-2i), (a12(i)- a21(i)2-2i), (a12(i)+ a21(i))2-i), (a21(i)- a12(i)2-2i) and (a22(i)+ a11(i))2-2i), where = 1 or = -1, depending on the feed to the first control input 39 of values. When = 1 is vychislitelaaunoi value at the first control input 39. The outputs from the first through third elements 20, 21 and 22 of the addition modulo two are formed respectively(i),(i)and(i)that set with the fourth to seventh adders-myCitadel 23, 24, 25 and 26 so that their outputs receive a11(i+1), a12(i+1), a21(i+1)and a22(i+1).

Unit 11 functions as follows (Fig. 3).

First 47 and second 52 triggers the reset. Feed a pulse to the input 12 is set to begin calculating the first trigger 47, and its direct access permit the passage of clock pulses from generator 45 pulses through the second And gate 48. The clock pulses increment the counter by 1. The counter value is the number of the iteration and output 54 rooms iteration. The first 50 and second 51 decoders check iteration pas equality first iteration dependencies (1) and (2) respectively, setting and resetting the second trigger 52, the direct and inverted outputs of which are respectively the second 55 and 56 third control outputs of the control block 11. After the last iteration counter 49 is reset. This leads to the triggering of the second decoder 51 and initiates sabrepulse to the input of the counter 49 through the second And gate 48. The inverse output of the first flip-flop is the output 13 of the completion of the computation, which is installed before the next calculation. The calculation of the eigenvalues is completed.

Thus, the above shows the implementation of the use of the claimed device the following cumulative conditions:

device for computing eigenvalues of matrices, embodying the claimed invention in its implementation, is intended for use in systems of digital processing of signals and images for computing eigenvalues of matrices, thereby extending the functionality when solving problems that require finding the eigenvalues of a large number of matrices in real time;

for the claimed invention in the form as it is characterized in the claims, confirmed the possibility of its implementation in accordance with the description and the proposed drawing;

device for computing eigenvalues of matrices, embodying the claimed invention in its implementation, is able to achieve perceived by the applicant of the technical result.

Therefore, the claimed invention sootvetstviis, containing four of the register, the four switches, the memory block is constant and the control unit, and outputs first, second, third and fourth registers respectively connected to information inputs of the first, second, third and fourth switches, input and output control unit connected respectively to the input of the start of the calculation and output of completing calculation of the control inputs of the first, second, third and fourth registers are connected to first control the output control unit, output the number of iteration which is connected to the input of the memory block is constant, the output of which is connected to control inputs of the first, second, third and fourth switches, characterized in that it contains the unit conversion matrix, the first and twelfth informational inputs which are connected respectively with the first and second outputs of the fourth switch, the second and the fourth information unit conversion matrix are connected respectively with the first and second outputs of the first switch, the eleventh, ninth, fifth, and third information input unit conversion matrix are connected respectively to the outputs of the first, second, third and fourth registers, the eighth and mi of the second switch, the seventh and tenth the information input unit conversion matrix are connected respectively with the first and second outputs of the third switch, the first and second control inputs of the conversion unit matrixes are connected respectively with the second and third control outputs of the control unit, the first, second, third and fourth outputs of the conversion unit matrixes respectively connected to information inputs of the fourth, third, second and first registers.

2. The device under item 1, characterized in that the conversion unit matrix contains three myCitadel, seven adders-vychitala and three elements of addition modulo two, and the first and second information input unit conversion matrix are connected respectively with the first and second inputs of the first myCitadel, the output of which is connected with the first inputs of the first, second and third elements of addition modulo two with the second information inputs of the fifth and sixth adders-vychitala, third and fourth information unit conversion matrix are connected respectively with the first and second information inputs of the first adder-myCitadel, the output of which is connected with the first information whodo is received respectively from the first and second inputs of the second myCitadel, the output of which is connected to the first information input of the fifth adder-myCitadel, seventh and eighth informational inputs conversion unit matrix are connected respectively with the first and second information inputs of the second adder - myCitadel, the output of which is connected with the second inputs of the first, second and third elements of addition modulo two with the second information inputs of the fourth and seventh adders-vychitala, ninth and tenth informational inputs conversion unit matrix are connected respectively with the first and second inputs of the third myCitadel, the output of which is connected to the first information input of the sixth adder-myCitadel, the eleventh and twelfth informational inputs conversion unit matrix are connected respectively with the first and second information input of the third adder-myCitadel, the output of which is connected to the first information input of the seventh adder-myCitadel, the first control input of the conversion unit matrixes connected to control inputs of the first, second and third adders-vychitala and with the third input of the second element of addition modulo two, the second control input of the conversion unit matrix connection is connected with the control input of the fifth adder-myCitadel, the output of the second element of addition modulo two is connected with the control input of the fourth adder-myCitadel, the output of the third element of addition modulo two is connected to control inputs of the sixth and seventh adders-vychitala, the outputs of the fourth, fifth, sixth and seventh adders-vychitala connected respectively to the first, second, third and fourth outputs of the block transformation matrix.

3. The device under item 1, characterized in that the control unit includes a pulse generator, two elements And two trigger, counter, and two decoder, the beginning of the calculation control unit is connected to the input of the first trigger and the inverting input of the first element And whose output is connected to the reset input of the first trigger, the inverted output of which is connected to the output end of the calculation control unit, the direct output of the first flip-flop is connected to the second input of the second element And the output of the pulse generator is connected to the first input of the second element, And the output of which is connected to first control the output of the control unit and the input counter, the output of which is connected to the output of the number of iteration control unit and inputs of the first and second decoders, the output vertrouwen the input of the first element And the reset input of the second trigger, direct and inverted outputs of which are connected respectively with the second and third control outputs of the control unit.

 

Same patents:

The invention relates to analog computing devices and can be used for the erection of the signal values in the degree

The invention relates to automation and computer engineering and can be used for signal processing, represented in code and pulse-width forms

The invention relates to the field of computer engineering and can be used in the development of specialized devices ACS operational level of ITWO when solving the problem of recognition tactical situations

The invention relates to computing and is designed to build on the basis of a special computer

The invention relates to computing and can be used in specialized calculators to solve problems involving coordinate transformations in space

The invention relates to computing and is designed to build on the basis of specialized computers

The invention relates to computer technology and can be used in digital computing, control and simulation systems, both General and special purpose, using multiplicative algorithms for computing functions, transformations of coordinates, rotation vector

The invention relates to the field of computer engineering and can be used in specialized computer systems for computing the eigenvalues of the matrix (nn)

The invention relates to computer technology and can be used in specialized computer systems to calculate the two-dimensional convolution

The invention relates to the field of computer engineering and can be used in specialized computer systems to calculate swerski

Matrix setprocessor // 2079879
The invention relates to computing and is designed to build on the basis of specialized computers

The invention relates to computer technology and can be used in specialized computer systems to calculate the two-dimensional convolution

The invention relates to computer technology and can be used in specialized computing systems, in particular, in digital signal processing for multiplying two matrices

FIELD: computer science.

SUBSTANCE: device has block of registers of first memory, block of registers of second memory, block for controlling reading of columns, block for controlling reading of rows, block for controlling reverse recording; according to second variant, device has same elements excluding block for controlling reverse recording. Third variant of device is different from second variant by absence of block for controlling reading of columns, and fourth variant of device is different from second one by absence of block for controlling reading of rows.

EFFECT: higher efficiency.

4 cl, 9 dwg

FIELD: computer science, possible use for engineering devices meant for processing numeric information arrays, in particular, for permutation of rows of two-dimensional array (matrix) stored in memory of computing device.

SUBSTANCE: device contains matrix of unary first memory registers and matrix of unary registers of second memory, which are identical to each other. Between them a commutator is positioned. Unary memory registers, positioned conditionally in one row, are connected between each other as shifting row registers. Commutator on basis of law given externally connects output of shifting register of first memory, corresponding to i-numbered row, to input of shifting register of second memory, corresponding to j-numbered row in second memory. After sending a packet of shifting pulses to shifting input of i-numbered shifting register of first memory, information from it moves to j-numbered shifting register of second memory. Therefore, transfer of i-numbered row to j-numbered position in new array occurs. Transfer of rows can be realized row-wise, or simultaneously for all, while structure of commutator is different for different cases.

EFFECT: realization of given permutation of rows and/or columns of two-dimensional array.

7 cl, 10 dwg, 1 tbl

FIELD: computer engineering, possible use for parallel computation by digit cuts of sums of paired productions of complex numbers, may be used for solving problems of digital signals processing, solving problems of spectral analysis and hydro-location, automatic control systems.

SUBSTANCE: device contains adder-subtracter, two blocks for computing sums of products, each one of which comprises multiplier registers, multiplicand registers, matrix multiplexers, transformer of equilibrium codes to positional codes, matrix adders.

EFFECT: expanded functional capabilities, increased speed of operation.

5 dwg

FIELD: information technology.

SUBSTANCE: device has a matrix comprising m rows and n columns of a homogeneous medium, n blocks for counting units, unit for finding the maximum, adders, a memory unit, a lower-bound estimate search unit which has a pulse generator, element selection multiplexers, row selection decoder, incidental vertex decoders, fixed arc decoders, row and column counters, fixed arc counters, incidental vertex counters, mode triggers, group of m triggers, group of m inhibit circuit units, matrix (i.j) (i=1.2,…, m, j=1.2,…,n) of fixed arc counters, matrix (i.j) (i=1.2,…, m, j=1.2,…,n) of OR elements, matrices (i.j) (i=1.2,…,m, j=1.2,…,n) of AND elements, an OR element, inverters, AND elements, group of m OR elements.

EFFECT: broader functional capabilities.

2 dwg

Up!