Factorial solution

B

Bert_Paris

-- Fact_rtl.vhd
-- --------------------------------------------------
-- Factorial Example - Synthesizable & efficient !
-- --------------------------------------------------
-- Author : Bert Cuzeau. ALSE. http://www.alse-fr.com
-- Tested successfully with Quartus II v9.0.
-- but it should be fine with any decent synthesizer.
--
-- Note : added registers in front and after to easily
-- get the Tsu (Fmax) after synthesis
-- Synthesis results : 10 LUTs for the Factorial, as expected !
-- Timing : speed practically unlimited since 1 Logic Level (250Mhz on
Cyclone III)

Library IEEE;
use IEEE.std_logic_1164.all;
use IEEE.numeric_std.all;
-- ---------------------------------------
Entity Factorial is
-- ---------------------------------------
port ( Clk : in std_logic;
Din : in std_logic_vector (2 downto 0); -- 0! .. 7! = 0
... 944
Result : out std_logic_vector (9 downto 0) ); -- 0 .. 1023
End Entity Factorial;

-- ---------------------------------------
Architecture RTL of Factorial is -- yes, this is perfect for
synthesis !
-- ---------------------------------------

-- The usual recursive function
function fact (d : natural) return natural is
variable res : natural;
begin
if d=0 then
res := 0;
elsif d=1 then
res := 1;
else
res := d * fact (d-1);
end if;
return res;
end function fact;

-- Constant table type
type Table_t is array (0 to 7) of unsigned(result'range);

-- Function to initialize a table with the factorial
impure function Init_Table return Table_t is
variable T : Table_t;
begin
for I in T'range loop
T(I) := to_unsigned(fact(I),Result'length);
end loop;
return T;
end function Init_Table;

-- The Table itself, initialized at creation :
signal Table : Table_t := Init_Table;
-- note ;: this table will be smplified in a few Logic Elements

signal Dinr : std_logic_vector (Din'range);
------\
begin -- Architecture
------/
Dinr <= Din when rising_edge(Clk); -- input FFs
result <= std_logic_vector(Table(to_integer(unsigned(Dinr)))) when
rising_edge(Clk);

end RTL;

------------------------------------------
-- Test Bench. Simulate -all
------------------------------------------
-- synopsys translate_off
library IEEE; use IEEE.std_logic_1164.all; use IEEE.numeric_std.all;
Entity factorial_tb is end;
Architecture test of factorial_tb is
signal Clk : std_logic := '0';
signal Din : std_logic_vector (2 downto 0) := "000"; -- 0! .. 7! =
840
signal Result : std_logic_vector (9 downto 0);
begin
assert Clk='0' or now < 500 ns report "Simulation has ended (not an
error)." severity failure;
Clk <= not Clk after 5 ns; -- 100 MHz clock
Din <= std_logic_vector (unsigned(Din)+1) after 40 ns; -- F/4
uut: entity work.factorial port map (Clk,Din,Result);
end architecture TEST;
-- synopsys translate_on
 
B

Bert_Paris

Hi Jonathan :)
Some tools can reduce it to 6 LUTs, but my description without Flops
and no async reset does help them too much ;-)
We should stop doing the students' assignments in this forum (lol)
I guess the next assignment will be the Ackermann's function (if the
teachers keep an eye on this newsgroup) ?

Bert
 
B

Bert_Paris

Before anyone notices ;-)
The previous version didn't handle the last value (7) correctly, which
factorial is 5040 and thus requires a 13 bits output vector.
Or maybe we should leave intentional errors for the teachers (lol) ?

-- Fact_rtl.vhd
-- --------------------------------------------------
-- Factorial Example - Synthesizable & efficient !
-- --------------------------------------------------
-- Author : Bert Cuzeau. ALSE. http://www.alse-fr.com
-- Version : 2.0, handles all values 0..7 -> 0 .. 5040
-- Tested successfully with :
-- * Altera Quartus II v9.0,
-- * Actel Libero 8.5 (Synplify)
-- * Xilinx ISE 10
-- but it should be fine with any decent synthesizer
--
-- Note : added registers in front and after to easily
-- get the Tsu (Fmax) after synthesis.
-- Synthesis results : 8 LUTs for the Factorial !
-- Timing : speed practically unlimited since only 1 Logic Level
(250Mhz on Cyclone III)

Library IEEE;
use IEEE.std_logic_1164.all;
use IEEE.numeric_std.all;
-- ---------------------------------------
Entity Factorial is
-- ---------------------------------------
port ( Clk : in std_logic;
Din : in std_logic_vector (2 downto 0); -- 0! .. 7! = 0
... 5040
Result : out std_logic_vector (12 downto 0) ); -- 0 .. 8191
End Entity Factorial;

-- ---------------------------------------
Architecture RTL of Factorial is -- yes, this is perfect for
synthesis !
-- ---------------------------------------

-- The usual recursive function
function fact (d : natural) return natural is
variable res : natural;
begin
if d=0 then
res := 0;
elsif d=1 then
res := 1;
else
res := d * fact (d-1);
end if;
return res;
end function fact;

-- Constant table type
type Table_t is array (0 to 7) of unsigned(result'range);

-- Function to initialize a table with the factorial
impure function Init_Table return Table_t is
variable T : Table_t;
begin
for I in T'range loop
T(I) := to_unsigned(fact(I),Result'length);
end loop;
return T;
end function Init_Table;

-- The Table itself, initialized at creation :
signal Table : Table_t := Init_Table;
-- note : this table will be simplified into a few LUTs

signal Dinr : std_logic_vector (Din'range);

------\
begin -- Architecture
------/
Dinr <= Din when rising_edge(Clk); -- input FFs
result <= std_logic_vector(Table(to_integer(unsigned(Dinr)))) when
rising_edge(Clk);

End architecture RTL;

--------------------------------------------------
-- Test Bench. Simulate -all, eyeball the results
--------------------------------------------------
-- synopsys translate_off
library IEEE; use IEEE.std_logic_1164.all; use IEEE.numeric_std.all;
Entity factorial_tb is end;
Architecture TEST of factorial_tb is
signal Clk : std_logic := '0';
signal Din : std_logic_vector (2 downto 0) := "000"; -- 0! .. 7! =
840
signal Result : std_logic_vector (12 downto 0);
begin
assert Clk='0' or now < 500 ns report "Simulation has ended (not an
error)." severity failure;
Clk <= not Clk after 5 ns; -- 100 MHz clock
Din <= std_logic_vector (unsigned(Din)+1) after 40 ns; -- F/4
uut: entity work.factorial port map (Clk,Din,Result);
end architecture TEST;
-- synopsys translate_on
 
B

Benjamin Couillard

From Jonathan's Dictionary of Computing Terms:

SEND BUTTON (n):
Powerful design review tool intended to improve
code quality by exposing authors of erroneous
code to public ridicule.  Unfortunately it can be
proven that this tool can only work retrospectively;
this is a consequence of Goedel's Incompleteness
Theorem and is a property shared with related
tools such as BOOK PUBLICATION and PRODUCT RELEASE.


No, we make enough of our own :)
--
Jonathan Bromley, Consultant

DOULOS - Developing Design Know-how
VHDL * Verilog * SystemC * e * Perl * Tcl/Tk * Project Services

Doulos Ltd., 22 Market Place, Ringwood, BH24 1AW, UK
(e-mail address removed)://www.MYCOMPANY.com

The contents of this message may contain personal views which
are not the views of Doulos Ltd., unless specifically stated.
Click to expand...

I might not be as good as you guys are in VHDL and FPGAs, but there's
an error in the code


0! = 1

Therefore, it should be corrected (it's not a big deal)
 
B

Bert_Paris

Argh, I actually modified my code to implement 0!=0,
but you're right : "By convention, 0! = 1".
The code is now two lines shorter ;-)
and I used an attribute for the Table length, so I guess
the port could now use unconstrained vectors. Slick.

-- Fact_rtl.vhd
-- --------------------------------------------------
-- Factorial Example - Synthesizable & efficient !
-- --------------------------------------------------
-- Author : Bert Cuzeau. ALSE. http://www.alse-fr.com
-- Version : 2.1, handles all values 0..7 -> 0 .. 5040
-- By convention, 0! = 1
-- Tested successfully with :
-- * Altera Quartus II v9.0,
-- * Actel Libero 8.5 (Synplify)
-- * Xilinx ISE 10
-- but it should be fine with any decent synthesizer
--
-- Note : added registers in front and after to easily
-- get the Tsu (Fmax) after synthesis.
-- Synthesis results : 8 LUTs for the Factorial !
-- Timing : speed practically unlimited since only 1 Logic Level
(250Mhz on Cyclone III)

Library IEEE;
use IEEE.std_logic_1164.all;
use IEEE.numeric_std.all;
-- ---------------------------------------
Entity Factorial is
-- ---------------------------------------
port ( Clk : in std_logic;
Din : in std_logic_vector (2 downto 0); -- 0! .. 7! = 0
... 5040
Result : out std_logic_vector (12 downto 0) ); -- 0 .. 8191
End Entity Factorial;

-- ---------------------------------------
Architecture RTL of Factorial is -- yes, this is perfect for
synthesis !
-- ---------------------------------------

-- The usual recursive function
function fact (d : natural) return natural is
variable res : natural;
begin
if d<2 then
res := 1;
else
res := d * fact (d-1);
end if;
return res;
end function fact;

-- Constant table type
type Table_t is array (0 to 2**Din'length - 1) of
unsigned(result'range);

-- Function to initialize a table with the factorial
impure function Init_Table return Table_t is
variable T : Table_t;
begin
for I in T'range loop
T(I) := to_unsigned(fact(I),Result'length);
end loop;
return T;
end function Init_Table;

-- The Table itself, initialized at creation :
signal Table : Table_t := Init_Table;
-- note : this table will be simplified into a few LUTs

signal Dinr : std_logic_vector (Din'range);

------\
begin -- Architecture
------/
Dinr <= Din when rising_edge(Clk); -- input FFs
result <= std_logic_vector(Table(to_integer(unsigned(Dinr)))) when
rising_edge(Clk);

End architecture RTL;

--------------------------------------------------
-- Test Bench. Simulate -all, eyeball the results
--------------------------------------------------
-- synopsys translate_off
library IEEE; use IEEE.std_logic_1164.all; use IEEE.numeric_std.all;
Entity factorial_tb is end;
Architecture TEST of factorial_tb is
signal Clk : std_logic := '0';
signal Din : std_logic_vector (2 downto 0) := "000"; -- 0! .. 7! =
840
signal Result : std_logic_vector (12 downto 0);
begin
assert Clk='0' or now < 500 ns report "Simulation has ended (not an
error)." severity failure;
Clk <= not Clk after 5 ns; -- 100 MHz clock
Din <= std_logic_vector (unsigned(Din)+1) after 40 ns; -- F/4
uut: entity work.factorial port map (Clk,Din,Result);
end architecture TEST;
-- synopsys translate_on
 
B

Bert_Paris

I can't resist :)
This is the unconstrained ports version, a breeze to parameterize.
And it handles integers larger than 32 bits.


-- Fact_rtl.vhd
-- --------------------------------------------------
-- Factorial Example - Synthesizable & efficient !
-- --------------------------------------------------
-- Author : (c) Bert Cuzeau. ALSE. http://www.alse-fr.com
-- Version : 3.0, using unconstrained vectors.
-- Handles numbers larger than 2**31
--
-- Synthesis results : 8 LUTs for (0! .. 7!)
-- 32 LUTS for (0! .. 15! = 1307674368000)
-- Tested with Quartus II v 9.0.
-- Should be fine with any synthesis tool.
--
-- Make sure you synthesize "Wrapper" as the top level.

Library IEEE;
use IEEE.std_logic_1164.all;
use IEEE.numeric_std.all;
-- ---------------------------------------
Entity Factorial is
-- ---------------------------------------
port ( Clk : in std_logic;
Din : in std_logic_vector; -- Yep, unconstrained !
Result : out std_logic_vector );
End Entity Factorial;

-- ---------------------------------------
Architecture RTL of Factorial is -- yes, this is perfect for
synthesis !
-- ---------------------------------------

-- The (almost) usual recursive function
function fact (d : unsigned) return unsigned is
variable res : unsigned (d'range);
begin
if d<2 then -- note that, by convention, 0! = 1
res := to_unsigned(1,res'length);
else
res := "*" (d,fact (d-1))(res'range);
end if;
return res;
end function fact;

-- Constant table type
type Table_t is array (0 to 2**Din'length - 1) of
unsigned(Result'range);

-- Function to initialize a table with the factorial
impure function Init_Table return Table_t is
variable T : Table_t;
begin
for I in T'range loop
T(I) := fact(to_unsigned(I,Result'length));
end loop;
return T;
end function Init_Table;

-- The Table itself, initialized at creation :
signal Table : Table_t := Init_Table;
-- note : this table will be simplified into a few LUTs

signal Dinr : std_logic_vector (Din'range);

------\
Begin -- Architecture
------/
Dinr <= Din when rising_edge(Clk); -- input FFs
result <= std_logic_vector(Table(to_integer(unsigned(Dinr)))) when
rising_edge(Clk);

End architecture RTL;


--------------------------------------------------------
-- Wrapper for Synthesis (4 -> 41 bits implementation)
--------------------------------------------------------
Library IEEE; use IEEE.std_logic_1164.all;
Entity Wrapper is -- For Synthesis of 4 bits -> 41 bits
port ( Clk : in std_logic;
Din : in std_logic_vector (3 downto 0); -- 0! .. 15! =
13077775800hex
Result : out std_logic_vector (40 downto 0) ); -- 41 bits
result
End Entity Wrapper;
architecture Wrap of Wrapper is
begin
Fact : entity work.Factorial port map (Clk,Din,Result);
end architecture Wrap;


--------------------------------------------------
-- Test Bench. Simulate -all, eyeball the results
--------------------------------------------------
-- synopsys translate_off
library IEEE; use IEEE.std_logic_1164.all; use IEEE.numeric_std.all;
Entity factorial_tb is end;
Architecture TEST of factorial_tb is
signal Clk : std_logic := '0';
signal Din : std_logic_vector (3 downto 0) := (others=>'0'); -- 0!
... 15!
signal Result : std_logic_vector (40 downto 0);
begin
assert Clk='0' or now < 800 ns report "Simulation has ended (not an
error)." severity failure;
Clk <= not Clk after 5 ns; -- 100 MHz clock
Din <= std_logic_vector (unsigned(Din)+1) after 40 ns; -- F/4
uut: entity work.factorial port map (Clk,Din,Result);
end architecture TEST;
-- synopsys translate_on
 
H

HT-Lab

Bert_Paris said:
I can't resist :)
This is the unconstrained ports version, a breeze to parameterize.
And it handles integers larger than 32 bits.
Click to expand...
...snip

nearly final, add a bit VHDL2008 goodness to remove the error/failure
message....:)

library std;
use std.env.all;
Entity factorial_tb is end;
Architecture TEST of factorial_tb is
signal Clk : std_logic := '0';
signal Din : std_logic_vector (3 downto 0) := (others=>'0'); -- 0! ..
15!
signal Result : std_logic_vector (40 downto 0);
begin
Click to expand...
-- assert Clk='0' or now < 800 ns report "Simulation has ended (not an
-- error)." severity failure;

STOP(1);

Hans
www.ht-lab.com
 
B

Bert_Paris

HT-Lab a exprimé avec précision :
... VHDL2008 goodness ...
Click to expand...
Isn't this an oxymoron ? ;-)

For the purist who doesn't like the failure ending, it's easy to stop
simulation using events starvation (stopping the clock) :
Clk <= '0' when Done else not Clock after (Period / 2);
Done <= true after 800 ns;
I don't think your 2008 code works as is (without a process, and a
wait)

btw: Is anyone using or even still interested in VHDL 2008 ?
I still wouldn't recommend using VHDL2008 yet, and I don't feel it's
going to save the language, but maybe I'm wrong.
 
H

HT-Lab

Bert_Paris said:
HT-Lab a exprimé avec précision :
Isn't this an oxymoron ? ;-)
Click to expand...

No it is a pleonasm :)
For the purist who doesn't like the failure ending, it's easy to stop
simulation using events starvation (stopping the clock) :
Clk <= '0' when Done else not Clock after (Period / 2);
Done <= true after 800 ns;
I don't think your 2008 code works as is (without a process, and a wait)
Click to expand...

you are correct.
btw: Is anyone using or even still interested in VHDL 2008 ?
Click to expand...

Using, no since I am still waiting for Mentor to support it. Interested,
definitely yes since it has some nice additions.
I still wouldn't recommend using VHDL2008 yet, and I don't feel it's going
to save the language, but maybe I'm wrong.
Click to expand...

Saving the language from what? For verification I agree that the ship has
sailed (although you can still see it in the distance) since SV/SC are
simply to far ahead but for design VHDL will be use for a long long
time.....(I hope)

Hans
www.ht-lab.com
 
J

JimLewis

Saving the language from what? For verification I agree that the ship has
sailed (although you can still see it in the distance) since SV/SC are
simply to far ahead but for design VHDL will be use for a long long
time.....(I hope)
Click to expand...

I think you are listening too much to marketing people.

For RTL, VHDL has better math capabilities (unsigned, signed,
signed fixed point, unsigned fixed point, and float). Did SV
even bother?

Yes for verification SV has more built in language features, however,
constrained random, functional coverage, and coverage driven
verification can be achieved in VHDL by writing procedural code.
See: http://www.synthworks.com/downloads/index.htm

This is stuff we are have been teaching for several years in
our VHDL Testbenches and Verification classes. I submitted a
paper on it to DVCon for the last two years, however, they are
so biased that they no longer accept VHDL papers. So if we
want a VHDL conference, we will have to start our own or
better yet, have more webinars.

Best,
Jim

P.S.
In the US at least, WRT job postings, there are more requests
for VHDL (144) than Verilog (101). It has been this way for
quite a while (even before the economy changes in October).
If you further refine the search to
VHDL and not Verilog: 79
Verilog and not VHDL: 36
VHDL and Verilog: 65

So basically almost all of the job postings that have VHDL and
Verilog would have to be for Verilog in order for Verilog to
have a lead in the job market.

Perhaps most of the VHDL users use free tools so the vendors
don't count them?
 

Ask a Question

Want to reply to this thread or ask your own question?

You'll need to choose a username for the site, which only take a couple of moments. After that, you can post your question and our members will help you out.

Ask a Question

Similar Threads

Query related to division of 1.122 in mentioned code. 0
Problem With Mealy Sequence Detector 1
LFSR doesn't generate random values during simulation 1
Array VHDL 3
Synchronous programmable counter 1
Array of Modulation BPSK 0
Shift left register using VHDL shift operator : sll trouble 0
Issue with simulation time - Modelsim PE Student 10.4 1

Members online

No members online now.
Total: 42 (members: 0, guests: 42)
Robots: 204

Forum statistics

Threads
473,766
Messages
2,569,569
Members
45,042
Latest member
icassiem

Latest Threads

Top