Square root extractor

An extractor of a square root of a number with a given bit length comprising:

• a plurality of identical first arithmetic elements, each having a first input data terminal, a second input data terminal, a first output data terminal and a second output data terminal, a carry input data terminal, a carry output data terminal and a selection data terminal, each of said plurality of first arithmetic elements receiving respective input data at the input data terminals and outputting respective output data at the output data terminals, and each respectively comprising:
• an adder used for subtraction based on bit data, inverted data obtained by inverting binary one and carry input data input thereto at the carry input data terminal, to output carry output data to the carry output data terminal and to output addition result data,
• a first selection circuit receiving said addition result data from said adder and said bit data and outputting either said addition result data or said bit data as first output data at said first output data terminal based on selection data from the selection data terminal, and
• a second selection circuit for selecting either one or zero based on said selection data from the selection data terminal and outputting the selected data as second output data at said second output data terminal;
• a plurality of identical second arithmetic elements, each having a first input data terminal, an increment input data terminal, a first output data terminal, an increment output data terminal, an increment carry input data terminal, a carry input data terminal, an increment carry output data terminal, a carry output data terminal and a selection data terminal, each of said plurality of second arithmetic elements receiving respective input data at the input data terminals and outputting respective output data at the output data terminals, and each respectively comprising:
• an incrementer receiving increment carry input data from the increment carry input data terminal to effect increment of increment input data at the increment input data terminal and outputting increment output data at the increment output data terminal and increment carry output data at the increment carry output data terminal,
• an adder used for subtraction of the increment output data output from the incrementer from the first input data input to the first input data terminal based on carry input data at the carry input data terminal to output addition result data and to output carry output data to the carry output data terminal, and
• a selection circuit selecting one of said addition result data from said adder and said bit data based on selection data at the selection data terminal and outputting the selected data as first output data at the first output data terminal;
• the plurality of first arithmetic elements and the plurality of second arithmetic elements being arranged in a plurality of rows, wherein each of said plurality of rows comprises one of said plurality of first arithmetic elements and at least one of said plurality of second arithmetic elements;
• the increment carry input data terminal and the carry input data terminal of each second arithmetic element in a row being respectively connected to the increment carry output data terminal and the carry output data terminal of the second arithmetic element of next lower rank in the row, and the carry input data terminal of the second arithmetic element of the lowest rank in the row being connected to the carry output data terminal of the first arithmetic element in the row;
• the first output data terminal and the second output data terminal of the one of said plurality of first arithmetic elements and the first output data terminal and the second output data terminal of the second arithmetic elements in each row being respectively connected to the first input data terminals and the second input data terminals of the second arithmetic elements in another row;
• the first input data terminal of the first arithmetic element and the first input data terminal of the second arithmetic element of the lowest rank in each row being supplied with either bit data or a binary number zero;
• and
• the increment carry input data terminal of the second arithmetic element of the lowest rank in each row being connected to its own second input data terminal.

An extractor of a square root comprising:

• a plurality of identical first arithmetic elements, each having a first input data terminal, a second input data terminal, a first output data terminal and a second output data terminal, a carry input data terminal, a carry output data terminal and a selection data terminal, each of said plurality of first arithmetic elements receiving respective input data at the input data terminals and outputting respective output data at the output data terminals;
• and each including an adder, a first selection circuit and a second selection circuit, one of the input terminals and a carry output terminal of the adder being respectively connected to the first input data terminal and the carry output data terminal of the first arithmetic element, two input terminals and an output terminal of the first selection circuit being respectively connected to the first input data terminal of the first arithmetic element, a sum output terminal of the adder and the first output data terminal of the first arithmetic element, and two input terminals and an output terminal of the second selection circuit being respectively supplied binary numbers one and zero and connected to the second output data terminal of the first arithmetic element;
• a plurality of identical second arithmetic elements, each having a first input data terminal, a second input data terminal, a first output data terminal, a second output data terminal, an increment carry input data terminal, a carry input data terminal, an increment carry output data terminal, a carry output data terminal and a selection data terminal, each receiving respective input data at the input data terminals and outputting respective output data at the output data terminals, and each including an incrementer, an adder and a selection circuit, an input terminal and an output terminal of the incrementer being respectively connected to the second input data terminal and the second output data terminal of the second arithmetic element, input terminals of the adder being respectively connected to the first input data terminal of the second arithmetic element and the increment output data terminal of the incrementer through an inverter, and input terminals and an output terminal of the selection circuit being respectively connected to the first input data terminal of the second arithmetic element, sum output terminal of the adder and the first output data terminal of the second arithmetic element;
• the plurality of first arithmetic elements and the plurality of second arithmetic elements being arranged in n rows, the first row comprising a first arithmetic element, the second row comprising a first arithmetic element and two second arithmetic elements and the n-th row comprising a first arithmetic element and n second arithmetic elements;
• the increment carry input data terminal and the carry input data terminal of each second arithmetic element in each row being respectively connected to the increment carry output data terminal and the carry output data terminal of a second arithmetic element of next lower rank in the row, the carry input data terminal of the second arithmetic element of the lowest rank in each row being connected to the carry output data terminal of the first arithmetic element in the row;
• the carry output data terminal of the second arithmetic element of the highest rank in each row being connected to an output terminal of the row and the carry output data terminal of the first arithmetic element in the first row being connected to the output terminal of the most significant bit data of the square root;
• the first output data terminal and the second output data terminal of the one of said plurality of first arithmetic elements and the first output data terminal and the second output data terminal of the second arithmetic elements in each row being respectively connected to the first input data terminals and the second input data terminals of the second arithmetic elements in another row that outputs less significant bit data of the square root;
• each of the first input data terminals of the first arithmetic element and the second arithmetic element of the lowest rank in each row being supplied either bit data or a binary number zero;
• the increment carry input data terminal of the second arithmetic element of the lowest rank in each row being connected to its own second input data terminal;
• and
• the selection data terminals of the first arithmetic element and the second arithmetic elements in each row being connected to the output terminal of the row.