Square root, somebody knows how its working?

Hello,

This is the code of Square Root from the website -->https://www.cs.umbc.edu/portal/help/VHDL/samples/sqrt8.vhdl

I can't understand it at all so I have some questions...

1.- If its an sqrt8 bits , why is using at the first entity (Sm) only 6 different signals, 4 in and 2 out?

2.- Architecture is using another 6 signals...why? and what it means this line for example: t011 <= (not x) and y and b;

Ofcourser if I can't understand the first Entity and Architecture I cannot understand the others

Thanks guys



-- sqrt8.vhdl unsigned integer sqrt 8-bits computing unsigned integer 4-bits
-- sqrt(00000100) = 0010 sqrt(4)=2
-- sqrt(01000000) = 1000 sqrt(64)=8
library IEEE;
use IEEE.std_logic_1164.all;

entity Sm is -- subtractor multiplexor
port ( x : in std_logic;
y : in std_logic;
b : in std_logic;
u : in std_logic;
d : out std_logic;
bo : out std_logic);
end Sm;

architecture circuits of Sm is
signal t011, t111, t010, t001, t100, td : std_logic;
begin -- circuits of Sm
t011 <= (not x) and y and b;
t111 <= x and y and b;
t010 <= (not x) and y and (not b);
t001 <= (not x) and (not y) and b;
t100 <= x and (not y) and (not b);
bo <= t011 or t111 or t010 or t001;
td <= t100 or t001 or t010 or t111;
d <= td when u='1' else x;
end architecture circuits; -- of Sm

library IEEE;
use IEEE.std_logic_1164.all;

entity psqrt is
port ( P : in std_logic_vector(7 downto 0);
U : out std_logic_vector(3 downto 0));
end psqrt;

architecture circuits of psqrt is
signal zer : std_logic := '0';
signal one : std_logic := '1';
signal x00, x01, x02, x03, x04, x05, u_0 : std_logic;
signal b00, b01, b02, b03, b04, b05 : std_logic;
signal x12, x13, x14, x15, x16, u_1 : std_logic;
signal b12, b13, b14, b15, b16 : std_logic;
signal x24, x25, x26, x27, u_2 : std_logic;
signal b24, b25, b26, b27 : std_logic;
signal x36, x37, u_3 : std_logic;
signal b36, b37 : std_logic;
begin -- circuits of psqrt
-- x y b u d bo
s36: entity work.Sm port map(P(6), one, zer, u_3, x36, b36);
s37: entity work.Sm port map(P(7), zer, b36, u_3, x37, b37);

s24: entity work.Sm port map(P(4), one, zer, u_2, x24, b24);
s25: entity work.Sm port map(P(5), zer, b24, u_2, x25, b25);
s26: entity work.Sm port map(x36 , u_3, b25, u_2, x26, b26);
s27: entity work.Sm port map(x37 , zer, b26, zer, x27, b27);

s12: entity work.Sm port map(P(2), one, zer, u_1, x12, b12);
s13: entity work.Sm port map(P(3), zer, b12, u_1, x13, b13);
s14: entity work.Sm port map(x24 , u_2, b13, u_1, x14, b14);
s15: entity work.Sm port map(x25 , u_3, b14, u_1, x15, b15);
s16: entity work.Sm port map(x26 , zer, b15, zer, x16, b16);

s00: entity work.Sm port map(P(0), one, zer, zer, x00, b00);
s01: entity work.Sm port map(P(1), zer, b00, zer, x01, b01);
s02: entity work.Sm port map(x12 , u_1, b01, zer, x02, b02);
s03: entity work.Sm port map(x13 , u_2, b02, zer, x03, b03);
s04: entity work.Sm port map(x14 , u_3, b03, zer, x04, b04);
s05: entity work.Sm port map(x15 , zer, b04, zer, x05, b05);
u_0 <= not b05;
u_1 <= not b16;
u_2 <= not b27;
u_3 <= not b37;
U(0) <= u_0;
U(1) <= u_1;
U(2) <= u_2;
U(3) <= u_3;
end architecture circuits; -- of psqrt

the actual square root is 8 bits.
The other entity appears to be some sort of mux, I guess a load of muxes creates a square root.

Either way, its pretty poor VHDL code.

You have a best Idea?

Maybe its better to implement a LUT to calculate it?

google this:A New Non-Restoring Square Root Algorithm and Its VLSI Implementations

I have writen this code for the square root of a floating point number. You can take a look at it or use it if you wont.

----------------------------------------------------------------------------------
-- Company: Instituto Superior Técnico
-- Prof: Paulo Alexandre Crisóstomo Lopes
-- paulo.lopes@inesc-id.pt
--
-- Create Date: 15:23:57 01/31/2012
-- Design Name:
-- Module Name: sqrt - Behavioral
-- Project Name:
-- Target Devices:
-- Tool versions:
-- Description: VHDL implementation of a 32 bit floating point square root.
-- Float format: sign | 8 bits exponent + 127 | 23 bits normalized mantissa.
-- Uses IEEE 754-1985, with the following exceptions.
-- NaN is not implemented. Operations that would result in NaN
-- have a non definied result.
-- An exponent of all zeros will always mean zero, and an
-- exponent of all ones will always mean infinity.
-- Rounding is round nearest ties away from zero.
-- Non normalized numbers are not implemented.
--
-- Dependencies:
--
-- Revision: 1.0
-- Additional Comments:
--
----------------------------------------------------------------------------------
library IEEE;
use IEEE.STD_LOGIC_1164.ALL;
use IEEE.STD_LOGIC_ARITH.ALL;
use IEEE.STD_LOGIC_UNSIGNED.ALL;
-- use STD.textio.all; -- basic I/O
-- use IEEE.std_logic_textio.all; -- I/O for logic types

entity sqrt is
Port ( x : in STD_LOGIC_VECTOR (31 downto 0);
y : out STD_LOGIC_VECTOR (31 downto 0));
end sqrt;

architecture Behavioral of sqrt is

function bit2bit_sq(x: STD_LOGIC_VECTOR) return STD_LOGIC_VECTOR is
variable y : STD_LOGIC_VECTOR(2*x'left+1 downto 0);
-- Returns x^2 by intercalating zeros in the argument,
-- were x has only one bit different from zero.
begin
for i in x'left downto 0 loop
-- x'right must be zero
y(2*i):=x(i);
y(2*i+1):='0';
end loop;
return y;
end;

begin
process(x)
variable x_mantissa : STD_LOGIC_VECTOR (22 downto 0);
variable x_exponent : STD_LOGIC_VECTOR (7 downto 0);
variable x_sign : STD_LOGIC;
variable y_mantissa : STD_LOGIC_VECTOR (22 downto 0);
variable y_exponent : STD_LOGIC_VECTOR (7 downto 0);
variable y_sign : STD_LOGIC;

variable ix: STD_LOGIC_VECTOR (25 downto 0);
variable a : STD_LOGIC_VECTOR (51 downto 0);
variable biti : STD_LOGIC_VECTOR (25 downto 0);
variable r : STD_LOGIC_VECTOR (51 downto 0);
variable rt : STD_LOGIC_VECTOR (52 downto 0);

-- variable my_line : line; -- type 'line' comes from textio
begin
x_mantissa := x(22 downto 0);
x_exponent := x(30 downto 23);
x_sign := x(31);

y_sign := '0';

if (x_exponent="00000000") then -- zero
y_exponent := (others=>'0');
y_mantissa := (others=>'0');
elsif (x_exponent="11111111") then -- infinity
y_exponent := (others=>'1');
y_mantissa := (others=>'0');
else

if (x_exponent(0)='1') then -- exponent-127 is even
y_exponent := '0' & x_exponent(7 downto 1) + 64;
ix := "01" & x_mantissa & '0';
else -- exponent-127 is odd
-- shit mantissa one to the left and subtract one from x_exponent
y_exponent := '0' & x_exponent(7 downto 1) + 63;
ix := '1' & x_mantissa & "00";
end if;
-- mantissa is m=ix/2^24
-- (one zero was added to the right to make the power even)
-- let the result of the integer square root algorithm be iy (26 bits)
-- iy = sqtr(ix)*2^13
-- resulting that sqrt(m)=iy/2^25

-- Integer input N bits square root algorithm:
-- r is be the reminder, r=ix-z^2, and z(N+1) the result,
-- with bit(N)=1/2^(N/2), and bit=2^(N/2-n)
-- Test each bit in the result, from the most significative to the least
-- significative: n goes from zero no N.
-- if bit is one: r(n+1) = ix - (z+bit)^2 =
-- r - 2zbit - bit^2
-- else r(n+1) = r
-- bit will be one if the resulting remainder is positive.
-- making a = 2zbit, one has,
-- if bit is one: a(n+1) = 2(z+bit)bit/2 =
-- a/2+bit^2
-- else a(n+1) = a/2
-- and a(N+1) = 2z(N+1)/2^(N/2+1) = z(N+1)/2^(N/2)

-- VHDL Implementation

a := (others=>'0');

biti := "10" & x"000000"; -- 2^(25)
-- biti has the bit being evaluated equal to one
r(51 downto 26):= ix; -- r is in Q26
r(25 downto 0):=(others=>'0');

for i in 25 downto 0 loop
rt := ('0' & r) - ('0' & (a or bit2bit_sq(biti)));
-- trial for the new value for the reminder
a := '0' & a(51 downto 1); -- srl
if (rt(52)='0') then -- rt>=0
r := rt(51 downto 0);
a := a or bit2bit_sq(biti); -- the adder is safelly replaced by an or
end if;
biti := '0' & biti(25 downto 1); -- srl 1
end loop;

a(24 downto 2) := a(24 downto 2)+a(1); -- round
-- even for ix = all '1' a will not oveflow

-- a is the result
y_mantissa := a(24 downto 2);

end if;

y(22 downto 0) <= y_mantissa;
y(30 downto 23) <= y_exponent;
y(31) <= y_sign;
end process;
end Behavioral;