Processor suitable for recursive computations

A processor for calculating results from computations involving multiplying input data words composed of input data digits by a coefficient word including a higher significance part, said coefficient word composed of coefficient digits, the processor including:

• (a) an array of multiplier cells, said cells forming rows and columns, each cell comprising a means for multiplying an input digit by an individual one of said coefficient digits, said multiplier cells comprising a means for implementing radix 2 arithmetic,
• said array has a first row arranged to receive highest significance input data digits, and each multiplier cell in said first row is arranged to pass output sum and transfer digits to a neighboring second row of said array,
• each multiplier cell which is not in said first row of the array and which corresponds to a coefficient digit of highest significance comprises a means for providing transfer output to the respective adding means corresponds to said multiplier cell's respective row and for providing sum digit output to a succeeding row where available,
• each multiplier cell which is not in said first row of the array and which corresponds to a coefficient digit of less than highest significance is connected to a succeeding row and comprises means for passing output sum and transfer digits to said succeeding row;
• (b) a respective common input connection means for each row arranged for supplying to said row a respective input data digit for multiplication by each multiplier cell in that row, each row being arranged to multiply such input data digit by at least said higher significance part of said coefficient word and for producing sum and transfer digits;
• (c) column interconnection line means for connecting pairs of adjacent columns for passing transfer digits therebetween to enable addition of sum and transfer digits of like digit significance arising from multiplication in neighboring columns where available, and
• (d) accumulating means for adding together digits produced in multiplier cells which are in neighboring pairs of rows and which corresponds to coefficient digits of highest significance, the accumulating means comprising means for computing digits of said results, most significant digit first and in descending order of digit significance in accordance with a redundant arithmetic scheme, said accumulating means comprises:
• a plurality of adding means, and each of said adding means corresponds to a respective array row other than said first row and comprises means for addition of said respective row's highest digit significance output with digits of significance at least equal therewith generated in the respective preceding row, and for producing from each said addition a digit of a respective one of said results, which digit is of redundant binary form and is of a digit significance corresponding to the respective row.

A processor for calculating results from computations involving multiplying input data words composed of input data digits by a coefficient word including a higher significance part, said coefficient word composed of coefficient digits, the processor including:

• (a) an array of multiplier cells, said cells forming rows and columns, each cell comprising a means for multiplying an input digit by an individual one of said coefficient digits, said multiplier cells comprising a means for implementing radix 2 arithmetic,
• the array has a first row of multiplier cells responsive to highest significance input data digits, said multiplier cells are responsive to input data digits in redundant binary form, and comprise means for passing to respective succeeding rows where available all sum and transfer digits other than highest significance transfer digits output to the accumulating means from rows of the array other than said first row,
• those of the multiplier cells which form said first row are responsive to a respective subsidiary input digit of each subsidiary input word in non-redundant binary form, and comprise a means for performing one of, according to sign, addition and subtraction, involving a respective subsidiary input digit and an intermediate product resulting from multiplication of an input data digit by a coefficient digit;
• (b) a respective common input connection means for each row arranged for supplying to said row a respective input data digit for multiplication by each multiplier cell in that row, each row being arranged to multiply such input data digit by at least said higher significance part of said coefficient word and for producing sum and transfer digits;
• (c) column interconnection line means for connecting pairs of adjacent columns for passing transfer digits therebetween to enable addition of sum and transfer digits of like digit significance arising from multiplication in neighboring columns where available, and
• (d) accumulating means for adding together digits produced in multiplier cells which are in neighboring pairs of rows and which correspond to coefficient digits of highest significance, the accumulating means comprising means for computing digits of said results, most significant digit first and in descending order of digit significance in accordance with a redundant arithmetic scheme, said accumulating means further comprises:
• a plurality of adding means, each of said adding means corresponds to a respective row other than said first row and comprises means for addition of said respective row's highest digit significance output with at least three digits of significance at least equal therewith generated in the respective preceding row where available, and for producing from each said addition a digit of a respective one of the said results, which digit is of redundant binary form and is of a digit significance corresponding to the respective row.