The Secretary of State for Defence in Her Britannic Majesty's Government

National Research Development Corporation

Qinetiq Limited

Secretary of State

John G McWhirter

John V McCanny

Terence John Shepherd

Robin Jones

David S Broomhead

Richard A Evans

Paul Daniel Baxter

Simon C Knowles

Kenneth W Wood

Edward R Pike

Ira James Clarke

Roger F Woods

Geoffrey Spence

David J Watson

Jeremy S Ward

A method of blind signal separation of convolutively mixed signals comprises firstly processing signals to produce second order independence. In a second step, and together with ranges of signal delay and rotation parameters, the resulting processed signals are used to determine delay and rotation parameters. These parameters implement at least one elementary paraunitary matrix and transform the processed signals into output signals with improvement in independence to at least a predominant part of a maximum extent obtainable over the parameter ranges. The output signals then become the next processed signals and the second step is iterated until independence ceases to be improved significantly. The latest output signals are then unmixed signals.

Blind signal separation

A method for dynamic blind signal separation generates initialisation information by processing an immediately preceding data window. This information is input at () and used at () to initialize orthogonality of data in an immediately following window. Initialised data are decorrelated at () with small update angles using a Jacobi technique. Steps () and () are collectively a second order stage of processing in statistical terms producing orthonormal signals. The orthonormal signals are initialized at () and then undergo separation at () by ICA with small angle updates using statistics higher than second order to produce separated signals. The method may be implemented in an acquisition phase to separate signals and among them identify desired signals, and a subsequent phase in which only the desired signals are separated. It may also be implemented by obtaining first results, and subsequently iteratively updating immediately preceding results using subsequent data snapshots to produce snapshot results for combing with immediately preceding results weighted to produce exponential fading.

Dynamic blind signal separation

A method of strongly decorrelating signals comprising processing input signals to determine delay and rotation parameters which implement at least one elementary paraunitary matrix. The parameters transform the input signals into output signals with improvement in a measure of strong decorrelation. The improvement in the measure of strong decorrelation is then assessed: if it is significant the latest output signals are, designated as input signals and the process is iterated. Iteration continues until the measure of strong decorrelation ceases to improve significantly, at which point the latest output signals are designated as signals decorrelated in a wide sense.

Decorrelation of signals

A heuristic processor incorporates a digital arithmetic unit arranged to compute the squared norm of each member of a training data set with respect to each member of a set of centers, and to transform the squared norms in accordance with a non-linear function to produce training .phi. vectors. A systolic array arranged for QR decomposition and least means squares processing forms combinations of the elements of each .phi. vector to provide a fit to corresponding training answers. The form of combination is then employed with like-transformed test data to provide estimates of unknown results. The processor is applicable to provide estimated results for problems which are non-linear and for which explicit mathematical formalisms are unknown.

Heuristic digital processor using non-linear transformation

Heuristic processor

A processor suitable for recursive computations is arranged to multiply successive input data words by a co-efficient word to produce results. It incorporates multiplier cells connected to form rows and columns. Each row is arranged to multiply a respective input data digit by the co-efficient. It begins with accumulator cells and continues with multiplier cells each arranged to multiply by an individual co-efficient digit and disposed in the row in descending order of digit significance. Columns other than the first column begin with a multiplier cell, and the higher significance columns terminate at respective accumulator cells. Any intervening multiplier cells are arranged in ascending order of multiplier digit significance. The processor employs radix 2 arithmetic. Each accumulator cell employs redundant radix 2 arithmetic, and each adds the highest significance transfer digit output of its row to at least three digits of equal and higher significance output from a preceding row. Operation of the multiplier and accumulator cells generates sum and transfer digits for output down and between columns in the direction of increasing digit significance in the case of transfer digits. An accumulator cell's computed digit of higher significance becomes the respective row's output result digit. Each result digit is recycled in redundant radix 2 form to provide an input data digit for all multiplier cells of a respective row selected in accordance with result digit significance.

Processor suitable for recursive computations

Digital processor for two's complement computations

A processor is provided which is suitable for constrained least squares computations. It incorporates a systolic array of boundary, internal, constraint and multiplier cells arranged as triangular and rectangular sub-arrays. The triangular sub-array contains boundary cells along its major diagonal and connected via delays, together with above-diagonal internal cells. It computes and updates a QR decomposition of a data matrix X incorporating successive data vectors having individual signals as elements. The rectangular sub-array incorporates constraint cell columns each implementing a respective constraint vector and terminating at a respective multiplier cell. The constraint cells store respective conjugate constraint factors obtained by constraint vector transformation in the triangular sub-array. Rotation parameters produced by QR decomposition in the triangular sub-array are employed by the rectangular sub-array to rotate a zero input and update stored constraint factors. Cumulative rotation of this input and summation of squared moduli of constraint factors are carried out in cascade down constraint columns. The boundary cells are arranged for cumulative multiplication of cosine rotation parameters. Multiplier cells multiply cumulatively multiplied cosine parameters by cumulatively rotated constraint column inputs and divide by summed squared moduli of constraint factors to provide residuals. Each constraint column produces respective residuals in succession corresponding to weighting of the data matrix X to produce minimum signals subject to a respective constraint governing the form of weighting, as required to compute minimum variance distortionless response (MVDR) results.

Processor for constrained least squares computations

A digital processor performs an N-point convolution or correlation of q-bit coefficients with data words guard band extended to p bits. The processor includes an array of one-bit clock-activated gated full adder cells arranged in N rows and q columns. Each cell is arranged to input data, carry and cumulative sum bits and to output the data bit and new carry and cumulative sum bits corresponding to the product of the input data bit with a respective stationary coefficient bit. The output carry bit is recirculated on the respective cell. Cumulative sum generation is cascaded down array columns. Data moves along each row and thence to the next lower row via a delay device providing a delay appropriate for correct partial product formation. Data is input bit and word serially to a first row cell and thereafter moves along successive rows progressively further down the array. Sums of partial products output by the array are accumulated according to bit significance by an accumulator device arranged to accumulate successive convolution or correlation results in different adding device. This avoids erroneous addition of contributions to different results. The array is cascadable to provide larger processors. Cascaded arrays may be arranged to be fault tolerant, and a faulty array may be bypassed without operating speed penalties arising from bypass lines.

Digital processor for convolution and correlation

A bit-slice digital processor for performing an N-point correlation or convolution of N single-bit coefficients with a bit parallel, word serial, bit-staggered stream of M bit data words. The processor includes an N row, M column array of one-bit gated full adders with rows extended by half adders to accommodate word growth. Intercell connections incorporating clock activated latches provide for data and result flow unidirectionally down columns, one at twice the rate of the other. Carries and coefficients move unidirectionally along array rows at the faster (data or result) rate. Complex computations are executed by arrays of processors each with output delaying means and an adder to sum separate processor contributions. The processor may include data and result bypass connections subdivided by clocked latches for bypassing without operating speed penalties, as required for fault-tolerant processor array construction.

Bit-slice digital processor for correlation and convolution

A systolic array of cells for processing a data stream includes an arrangement of nearest-neighbor connected boundary cells, internal cells and a multiplier, arranged as a triangular array and a column. The boundary cells are diagonally interconnected. Each boundary cell evaluates sine and cosine rotation parameters from data received from above for lateral transfer to a neighboring internal cell, and multiplies a diagonal input by the cosine parameter for diagonal output. Each internal cell receives rotation parameters from the left, applies them to data from above to produce an output below, and passes them on laterally. Data input to the column becomes cumulatively rotated before output from the final downstream internal cell. The final downstream boundary cell provides cumulatively multiplied cosine parameters. The multiplier provides the product of the outputs of these final cells. The product is the least squares residual arising from weighted minimization of input signals.

Systolic array

A digital data processor is provided to multiply data elements by coefficients. It includes a systolic array of cells consisting of nearest neighbor connected gated full adders. The cells multiply data bits received from laterally adjacent cells and subsequently pass them on. The product is added to a cumulative sum bit from a cell above and to a carry bit recirculated from an earlier computation. The output is passed to a cell below, and a new carry bit is recirculated for addition in a subsequent computation. Data and coefficients are input in counterflow to opposite sides of the array. An adder tree accumulates non-simultaneously computed contributions to individual output terms. The tree incorporates a delay and switches arranged to implement or bypass the delay according to earlier or later computation of a contribution. By virtue of this accumulation, the processor provides reduced cell redundancy compared to the prior art.

Digital data processor for multiplying data by a coefficient set

A constraint application processor is arranged to apply a linear constraint to signals from antennas. A main antenna signal is fed to constraint element multipliers and then to respective adders for subtraction from subsidiary antenna signals. Delay units delay the subsidiary signals by one clock cycle prior to subtraction. The main signal is also fed via a one cycle delay unit to a multiplier for amplification by a gain factor. Main and subsidiary outputs of the processor may be connected to an output processor for signal minimization subject to the main gain factor remaining constant. The output processor may be arranged to produce recursive signal residuals in accordance with the Widrow LMS (Least Mean Square) algorithm. This requires a processor arranged to sum main and weighted subsidiary signals, weight factors being derived from preceding data, residual and weight factors. Alternatively, a systolic array of processing cells may be employed.

Constraint application processor for applying a constraint to a set of

A digital data processor for matrix/matrix multiplication includes a systolic array of nearest neighbor connected gated full adders. The adders are arranged to multiply two input data bits and to add their product to an input cumulative sum bit and a carry bit from a lower order bit computation. The result and input data bits are output to respective neighboring cells, a new carry bit being recirculated for later addition to a higher order bit computation. Column elements of one matrix and row elements of the other are input to either side of the array bit-serially, least significant bit leading, for mutual counterpropagation therethrough with a cumulative time delay between input of adjacent columns or rows. Bit-level matrix interactions for product matrix computation occur at individual cells. Pairs of intercalated adder trees are connected switchably to the array to accumulate bit-level contributions to product matrix elements.

Pipelined systolic array for matrix-matrix multiplication

The invention provides a digital data processor which has been systemetized down to bit level. The processor includes a regular array of identical processing cells which perform a logic operation on incoming bits. The cells repeatedly perform a cell operation under the control of clocks which govern the inputting to and outputting from the cell of data bits. Each bit takes part in a maximum of one cell operation in one repetition of the clock having the highest repetition frequency. Processing cell arrays for dealing with larger numbers may be readily built up from smaller arrays used for smaller numbers. Having obtained a fully working design for one type of processing cell, the full array consisting of a plurality of cells is proven.

Growing community of inventors

Malvern, United Kingdom

John G McWhirter