Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]
Groups > comp.lang.forth > #54229 > unrolled thread
| Started by | Dale Scott <dalescottnet@gmail.com> |
|---|---|
| First post | 2017-01-21 11:27 -0800 |
| Last post | 2017-01-23 18:46 -0300 |
| Articles | 20 on this page of 138 — 21 participants |
Back to article view | Back to comp.lang.forth
embedded forth Dale Scott <dalescottnet@gmail.com> - 2017-01-21 11:27 -0800
Re: embedded forth Paul Rubin <no.email@nospam.invalid> - 2017-01-21 11:31 -0800
Re: embedded forth stephen@mpeforth.com - 2017-01-22 00:52 -0800
Re: embedded forth anton@mips.complang.tuwien.ac.at (Anton Ertl) - 2017-01-22 17:09 +0000
Re: embedded Forth Dale Scott <dalescottnet@gmail.com> - 2017-01-22 09:43 -0800
Re: embedded Forth stephen@mpeforth.com - 2017-01-22 12:19 -0800
Re: embedded Forth albert@cherry.spenarnc.xs4all.nl (Albert van der Horst) - 2017-01-22 21:25 +0100
Re: embedded Forth john <anon@example.com> - 2017-01-22 21:04 +0000
Re: embedded Forth "Elizabeth D. Rather" <erather@forth.com> - 2017-01-22 12:30 -1000
Re: embedded Forth hughaguilar96@gmail.com - 2017-01-22 20:45 -0800
Re: embedded Forth stephen@mpeforth.com - 2017-01-22 14:08 -0800
Re: embedded Forth Paul Rubin <no.email@nospam.invalid> - 2017-01-22 14:55 -0800
Re: embedded Forth Dale Scott <dalescottnet@gmail.com> - 2017-01-22 20:41 -0800
Re: embedded Forth Paul Rubin <no.email@nospam.invalid> - 2017-01-22 21:19 -0800
Re: embedded Forth hughaguilar96@gmail.com - 2017-01-22 21:36 -0800
Re: embedded Forth Dale Scott <dalescottnet@gmail.com> - 2017-01-22 22:09 -0800
Re: embedded Forth rickman <gnuarm@gmail.com> - 2017-01-23 04:15 -0500
Re: embedded Forth Dale Scott <dalescottnet@gmail.com> - 2017-01-23 08:41 -0800
Re: embedded Forth rickman <gnuarm@gmail.com> - 2017-01-23 14:32 -0500
Re: embedded Forth Dale Scott <dalescottnet@gmail.com> - 2017-01-23 11:53 -0800
Re: embedded Forth rickman <gnuarm@gmail.com> - 2017-01-23 15:10 -0500
Re: embedded Forth Paul Rubin <no.email@nospam.invalid> - 2017-01-23 14:34 -0800
Re: embedded Forth Andrew Haley <andrew29@littlepinkcloud.invalid> - 2017-01-24 03:14 -0600
Re: embedded Forth rickman <gnuarm@gmail.com> - 2017-01-23 03:43 -0500
Re: embedded Forth john <anon@example.com> - 2017-01-23 10:32 +0000
keep secrets (was Re: embedded Forth) "Wolfgang Allinger" <all2001@spambog.com> - 2017-01-23 08:58 -0300
Re: keep secrets (was Re: embedded Forth) Rod Pemberton <NeedNotReplyHere@xrsevnneqk.cem> - 2017-01-23 07:47 -0500
Re: keep secrets (was Re: embedded Forth) "Wolfgang Allinger" <all2001@spambog.com> - 2017-01-23 18:18 -0300
Re: keep secrets (was Re: embedded Forth) rickman <gnuarm@gmail.com> - 2017-01-23 19:15 -0500
Re: keep secrets (was Re: embedded Forth) rickman <gnuarm@gmail.com> - 2017-01-23 14:38 -0500
Re: keep secrets (was Re: embedded Forth) "Wolfgang Allinger" <all2001@spambog.com> - 2017-01-23 18:43 -0300
Re: keep secrets (was Re: embedded Forth) rickman <gnuarm@gmail.com> - 2017-01-23 19:48 -0500
Re: keep secrets (was Re: embedded Forth) "Elizabeth D. Rather" <erather@forth.com> - 2017-01-23 16:30 -1000
Re: keep secrets (was Re: embedded Forth) rickman <gnuarm@gmail.com> - 2017-01-23 22:23 -0500
Re: embedded forth rickman <gnuarm@gmail.com> - 2017-01-22 13:44 -0500
Re: embedded forth Paul Rubin <no.email@nospam.invalid> - 2017-01-22 13:38 -0800
Re: embedded forth rickman <gnuarm@gmail.com> - 2017-01-23 00:45 -0500
Re: embedded forth Dale Scott <dalescottnet@gmail.com> - 2017-01-22 22:44 -0800
Re: embedded forth Paul Rubin <no.email@nospam.invalid> - 2017-01-23 00:48 -0800
Re: embedded forth rickman <gnuarm@gmail.com> - 2017-01-23 03:51 -0500
Re: embedded forth john <anon@example.com> - 2017-01-23 10:02 +0000
Re: embedded forth anton@mips.complang.tuwien.ac.at (Anton Ertl) - 2017-01-23 09:01 +0000
Re: embedded forth albert@cherry.spenarnc.xs4all.nl (Albert van der Horst) - 2017-01-23 13:05 +0100
Re: embedded forth rickman <gnuarm@gmail.com> - 2017-01-23 14:40 -0500
Re: embedded forth Mark Wills <markwills1970@gmail.com> - 2017-01-24 01:12 -0800
Re: embedded forth albert@cherry.spenarnc.xs4all.nl (Albert van der Horst) - 2017-01-24 14:38 +0100
Re: embedded forth rickman <gnuarm@gmail.com> - 2017-01-24 19:51 -0500
Re: embedded forth albert@cherry.spenarnc.xs4all.nl (Albert van der Horst) - 2017-01-25 11:34 +0100
Re: embedded forth rickman <gnuarm@gmail.com> - 2017-01-25 22:13 -0500
Re: embedded forth albert@cherry.spenarnc.xs4all.nl (Albert van der Horst) - 2017-01-26 11:36 +0100
Re: embedded forth rickman <gnuarm@gmail.com> - 2017-01-26 14:07 -0500
Re: embedded forth Ilya Tarasov <ilya74.tarasov@gmail.com> - 2017-01-26 00:19 -0800
Re: embedded forth rickman <gnuarm@gmail.com> - 2017-01-26 14:15 -0500
Re: embedded forth Ilya Tarasov <ilya74.tarasov@gmail.com> - 2017-01-27 13:08 -0800
Re: embedded forth rickman <gnuarm@gmail.com> - 2017-01-27 17:54 -0500
Re: embedded forth Paul Rubin <no.email@nospam.invalid> - 2017-01-27 15:29 -0800
Re: embedded forth Ilya Tarasov <ilya74.tarasov@gmail.com> - 2017-01-27 16:28 -0800
Re: embedded forth rickman <gnuarm@gmail.com> - 2017-01-27 23:58 -0500
Re: embedded forth Ilya Tarasov <ilya74.tarasov@gmail.com> - 2017-01-28 11:58 -0800
Re: embedded forth rickman <gnuarm@gmail.com> - 2017-01-28 15:36 -0500
Re: embedded forth Ilya Tarasov <ilya74.tarasov@gmail.com> - 2017-01-28 15:05 -0800
Re: embedded forth Paul Rubin <no.email@nospam.invalid> - 2017-01-28 15:57 -0800
Re: embedded forth rickman <gnuarm@gmail.com> - 2017-01-28 21:51 -0500
Re: embedded forth Ilya Tarasov <ilya74.tarasov@gmail.com> - 2017-01-29 09:53 -0800
Re: embedded forth albert@cherry.spenarnc.xs4all.nl (Albert van der Horst) - 2017-01-29 19:32 +0100
Re: embedded forth Ilya Tarasov <ilya74.tarasov@gmail.com> - 2017-01-29 11:53 -0800
Re: embedded forth rickman <gnuarm@gmail.com> - 2017-01-30 01:10 -0500
Re: embedded forth Ilya Tarasov <ilya74.tarasov@gmail.com> - 2017-01-29 23:11 -0800
Re: embedded forth Paul Rubin <no.email@nospam.invalid> - 2017-01-29 23:34 -0800
Re: embedded forth albert@cherry.spenarnc.xs4all.nl (Albert van der Horst) - 2017-01-30 12:42 +0100
Re: embedded forth albert@cherry.spenarnc.xs4all.nl (Albert van der Horst) - 2017-01-30 12:36 +0100
Re: embedded forth ctmalan@gmail.com - 2017-01-30 11:02 -0800
Re: embedded forth Paul Rubin <no.email@nospam.invalid> - 2017-01-30 11:04 -0800
Re: embedded forth Andrew Haley <andrew29@littlepinkcloud.invalid> - 2017-01-31 04:34 -0600
Re: embedded forth Ilya Tarasov <ilya74.tarasov@gmail.com> - 2017-01-30 12:15 -0800
Re: embedded forth rickman <gnuarm@gmail.com> - 2017-01-30 10:15 -0500
Re: embedded forth Ilya Tarasov <ilya74.tarasov@gmail.com> - 2017-01-30 12:20 -0800
Re: embedded forth Paul Rubin <no.email@nospam.invalid> - 2017-01-30 14:09 -0800
Re: embedded forth albert@cherry.spenarnc.xs4all.nl (Albert van der Horst) - 2017-01-31 03:04 +0100
Re: embedded forth Paul Rubin <no.email@nospam.invalid> - 2017-01-30 20:19 -0800
Re: embedded forth rickman <gnuarm@gmail.com> - 2017-01-30 17:10 -0500
Re: embedded forth Ilya Tarasov <ilya74.tarasov@gmail.com> - 2017-01-30 14:38 -0800
Re: embedded forth rickman <gnuarm@gmail.com> - 2017-01-30 23:09 -0500
Re: embedded forth Ilya Tarasov <ilya74.tarasov@gmail.com> - 2017-01-31 09:32 -0800
Re: embedded forth rickman <gnuarm@gmail.com> - 2017-02-08 18:22 -0500
Re: embedded forth Ilya Tarasov <ilya74.tarasov@gmail.com> - 2017-02-09 01:46 -0800
Re: embedded forth rickman <gnuarm@gmail.com> - 2017-02-09 05:11 -0500
Re: embedded forth rickman <gnuarm@gmail.com> - 2017-02-12 01:30 -0500
Re: embedded forth Ilya Tarasov <ilya74.tarasov@gmail.com> - 2017-02-12 10:21 -0800
Re: embedded forth rickman <gnuarm@gmail.com> - 2017-02-12 19:37 -0500
Re: embedded forth Ilya Tarasov <ilya74.tarasov@gmail.com> - 2017-02-14 13:26 -0800
Re: embedded forth Gary Bergstrom <forthprgrmr@gmail.com> - 2017-02-14 11:36 -0800
Re: embedded forth rickman <gnuarm@gmail.com> - 2017-02-14 18:13 -0500
Re: embedded forth rickman <gnuarm@gmail.com> - 2017-01-28 21:51 -0500
Re: embedded forth Ilya Tarasov <ilya74.tarasov@gmail.com> - 2017-01-29 10:20 -0800
Re: embedded forth Cecil Bayona <cbayona@cbayona.com> - 2017-01-29 12:38 -0600
Re: embedded forth Ilya Tarasov <ilya74.tarasov@gmail.com> - 2017-01-29 11:49 -0800
Re: embedded forth rickman <gnuarm@gmail.com> - 2017-02-04 04:22 -0500
Re: embedded forth Ilya Tarasov <ilya74.tarasov@gmail.com> - 2017-02-04 17:54 -0800
Re: embedded forth hughaguilar96@gmail.com - 2017-02-04 20:26 -0800
Re: embedded forth Ilya Tarasov <ilya74.tarasov@gmail.com> - 2017-02-05 07:53 -0800
Re: embedded forth hughaguilar96@gmail.com - 2017-02-05 11:08 -0800
Re: embedded forth hughaguilar96@gmail.com - 2017-02-05 11:39 -0800
Re: embedded forth Ilya Tarasov <ilya74.tarasov@gmail.com> - 2017-02-08 06:46 -0800
Re: embedded forth luser droog <mijoryx@yahoo.com> - 2017-02-13 19:17 -0800
Re: embedded forth Ilya Tarasov <ilya74.tarasov@gmail.com> - 2017-02-15 06:23 -0800
Re: embedded forth hughaguilar96@gmail.com - 2017-02-15 11:09 -0800
Re: embedded forth Ilya Tarasov <ilya74.tarasov@gmail.com> - 2017-02-15 15:24 -0800
Re: embedded forth jkn_gg@nicorp.f9.co.uk - 2017-02-16 09:49 -0800
Re: embedded forth hughaguilar96@gmail.com - 2017-02-17 09:12 -0800
Re: embedded forth Ilya Tarasov <ilya74.tarasov@gmail.com> - 2017-02-17 12:47 -0800
Re: embedded forth hughaguilar96@gmail.com - 2017-02-17 16:18 -0800
Re: embedded forth luser droog <mijoryx@yahoo.com> - 2017-02-16 08:43 -0800
Re: embedded forth Alex <alex@rivadpm.com> - 2017-02-05 20:47 +0000
Re: embedded forth hughaguilar96@gmail.com - 2017-02-05 13:36 -0800
Re: embedded forth Alex <alex@rivadpm.com> - 2017-02-05 23:18 +0000
Re: embedded forth hughaguilar96@gmail.com - 2017-02-05 21:10 -0800
Re: embedded forth Alex <alex@rivadpm.com> - 2017-02-06 11:12 +0000
Re: embedded forth hughaguilar96@gmail.com - 2017-02-05 21:15 -0800
Re: embedded forth hughaguilar96@gmail.com - 2017-02-05 22:45 -0800
Re: embedded forth albert@cherry.spenarnc.xs4all.nl (Albert van der Horst) - 2017-02-06 12:04 +0100
Re: embedded forth Ilya Tarasov <ilya74.tarasov@gmail.com> - 2017-02-08 03:08 -0800
Re: embedded forth rickman <gnuarm@gmail.com> - 2017-02-08 06:39 -0500
Re: embedded forth Ilya Tarasov <ilya74.tarasov@gmail.com> - 2017-02-08 07:15 -0800
Re: embedded forth rickman <gnuarm@gmail.com> - 2017-02-08 15:49 -0500
Re: embedded forth Ilya Tarasov <ilya74.tarasov@gmail.com> - 2017-02-09 01:14 -0800
Re: embedded forth rickman <gnuarm@gmail.com> - 2017-02-09 05:19 -0500
Re: embedded forth Ilya Tarasov <ilya74.tarasov@gmail.com> - 2017-02-09 03:48 -0800
Re: embedded forth rickman <gnuarm@gmail.com> - 2017-02-05 16:08 -0500
Re: embedded forth rickman <gnuarm@gmail.com> - 2017-02-07 21:59 -0500
Re: embedded forth albert@cherry.spenarnc.xs4all.nl (Albert van der Horst) - 2017-01-28 11:10 +0100
Re: embedded forth rickman <gnuarm@gmail.com> - 2017-01-28 06:15 -0500
Re: embedded forth albert@cherry.spenarnc.xs4all.nl (Albert van der Horst) - 2017-01-28 19:48 +0100
Re: embedded forth rickman <gnuarm@gmail.com> - 2017-01-28 14:37 -0500
Re: embedded forth mhx@iae.nl - 2017-01-28 07:48 -0800
Re: embedded forth albert@cherry.spenarnc.xs4all.nl (Albert van der Horst) - 2017-01-28 19:53 +0100
Re: embedded forth mhx@iae.nl - 2017-01-28 15:49 -0800
Re: embedded forth "Wolfgang Allinger" <all2001@spambog.com> - 2017-01-23 18:46 -0300
Page 5 of 7 — ← Prev page 1 2 3 4 [5] 6 7 Next page →
| From | rickman <gnuarm@gmail.com> |
|---|---|
| Date | 2017-01-30 17:10 -0500 |
| Message-ID | <o6odhv$qg4$1@dont-email.me> |
| In reply to | #54555 |
On 1/30/2017 3:20 PM, Ilya Tarasov wrote: > >> I don't understand what you are going on about. This will do the job to >> any level of accuracy required. Are you saying you don't like thinking >> about your work? What you call approximation, I call engineering. > > Engineering is a way to solve a task, but task must be stated first. Let's think about angle rotating. Ok, we have a way to calculate sin(a+b), so we can represent any angle as a sum of several angles, with sin and cos values listed in a table. What is an optimal way to choose that angles? From the first look, we may list degrees, minutes and seconds, but is it optimal? I've already explained the division is done in the phase angle representation. The high order bits are used for the gross angle and the low order bits are used for the fine angle. No math required. You can pick how many bits in each to suit your precision requirements. If you need a formal description of how to do that I will leave you to the many sources available through a Google search. -- Rick C
[toc] | [prev] | [next] | [standalone]
| From | Ilya Tarasov <ilya74.tarasov@gmail.com> |
|---|---|
| Date | 2017-01-30 14:38 -0800 |
| Message-ID | <453ff717-47e2-4b43-87e5-38d3b6d05f89@googlegroups.com> |
| In reply to | #54557 |
> I've already explained the division is done in the phase angle > representation. The high order bits are used for the gross angle and > the low order bits are used for the fine angle. No math required. You > can pick how many bits in each to suit your precision requirements. If > you need a formal description of how to do that I will leave you to the > many sources available through a Google search. Try to think deeper and you will reinvent the idea of CORDIC :) This is what you are trying to 'explain' to me, but angles in CORDIC just properly chosen, with no interpolation required. This is like the dichotomy algorithm compared to randomly selected additions. I don't need to search Google for things that I'm know good enough. Now you are near starting point and it is possible to improve your implementation, if you really need this.
[toc] | [prev] | [next] | [standalone]
| From | rickman <gnuarm@gmail.com> |
|---|---|
| Date | 2017-01-30 23:09 -0500 |
| Message-ID | <o6p2ij$fll$1@dont-email.me> |
| In reply to | #54559 |
On 1/30/2017 5:38 PM, Ilya Tarasov wrote: > >> I've already explained the division is done in the phase angle >> representation. The high order bits are used for the gross angle and >> the low order bits are used for the fine angle. No math required. You >> can pick how many bits in each to suit your precision requirements. If >> you need a formal description of how to do that I will leave you to the >> many sources available through a Google search. > > Try to think deeper and you will reinvent the idea of CORDIC :) This is what you are trying to 'explain' to me, but angles in CORDIC just properly chosen, with no interpolation required. This is like the dichotomy algorithm compared to randomly selected additions. I don't need to search Google for things that I'm know good enough. Now you are near starting point and it is possible to improve your implementation, if you really need this. You still don't get it. CORDIC is implemented using a large amount of FPGA fabric. Sines can be calculated much more efficiently using hard IP multipliers which use a much smaller area on the chip and so cost less in real estate and so chip cost. They also operate very fast. You seem to be accustomed to designing in the days when multipliers were either not available or to be avoided and so the "no multiplier" aspect of the CORDIC algorithm sounded like a good idea. We are way beyond that with today's chips. -- Rick C
[toc] | [prev] | [next] | [standalone]
| From | Ilya Tarasov <ilya74.tarasov@gmail.com> |
|---|---|
| Date | 2017-01-31 09:32 -0800 |
| Message-ID | <473c8a9d-752c-40c1-ad66-0a6fd368de02@googlegroups.com> |
| In reply to | #54563 |
> You still don't get it. CORDIC is implemented using a large amount of
> FPGA fabric. Sines can be calculated much more efficiently using hard
> IP multipliers which use a much smaller area on the chip and so cost
> less in real estate and so chip cost. They also operate very fast.
>
> You seem to be accustomed to designing in the days when multipliers were
> either not available or to be avoided and so the "no multiplier" aspect
> of the CORDIC algorithm sounded like a good idea. We are way beyond
> that with today's chips.
Not only multipliers are cheap. Words are cheap too :)
Ok, let me do your job. Let's create a project for calculating sin with 16-bit argument. Divide that argument to 8-bit coarse and fine parts. We will need to implement: sin(a+b) = sin(a)*cos(b) + cos(a)*sin(b);
Assume Kintex-7 Xilinx FPGA. First, we will need to create sin annd cos tables, otherwises synthesizer will optimize out empty tables to simple constants.
Here is a Forth script to generate VHDL initialization lines
===================================================================
{
" sin_coarse.dat" NEWFILE TO HF-OUT
256 0 DO
I .F " => " PRINTF
I S>F 256.0 F/ PI F* 2.0 F/ FSIN 65535.0 F* F>S
.F
" ," PRINTF CRF
LOOP
HF-OUT CLOSE
" cos_coarse.dat" NEWFILE TO HF-OUT
256 0 DO
I .F " => " PRINTF
I S>F 256.0 F/ PI F* 2.0 F/ FCOS 65535.0 F* F>S
.F
" ," PRINTF CRF
LOOP
HF-OUT CLOSE
" sin_fine.dat" NEWFILE TO HF-OUT
256 0 DO
I .F " => " PRINTF
I S>F 256.0 F/ PI F* 2.0 F/ 256.0 F/ FSIN 65535.0 F* F>S
.F
" ," PRINTF CRF
LOOP
HF-OUT CLOSE
" cos_fine.dat" NEWFILE TO HF-OUT
256 0 DO
I .F " => " PRINTF
I S>F 256.0 F/ PI F* 2.0 F/ 256.0 F/ FCOS 65535.0 F* F>S
.F
" ," PRINTF CRF
LOOP
HF-OUT CLOSE
}
===================================================================
VHDL code
----------------------------------------------------------------------------library IEEE;
use IEEE.STD_LOGIC_1164.ALL;
use IEEE.NUMERIC_STD.ALL;
entity top is
Port ( clk : in STD_LOGIC;
phase : in STD_LOGIC_VECTOR (15 downto 0);
result : out STD_LOGIC_VECTOR (31 downto 0));
end top;
architecture Behavioral of top is
type TTable is array(0 to 255) of integer range 0 to 65535;
signal SinCoarse : Ttable := (
0 => 0 ,
-- skipped lines generated by Forth
others => 0);
signal SinFine : Ttable := (
0 => 0 ,
-- skipped lines generated by Forth
others => 0 );
signal CosCoarse : Ttable := (
0 => 65535 ,
-- skipped lines generated by Forth
others => 0);
signal CosFine : Ttable := (
0 => 65535 ,
-- skipped lines generated by Forth
others => 0);
signal sina, sinb, cosa, cosb : integer range 0 to 65535;
signal sin : integer;
begin
-- sin(a+b) = sin(a)*cos(b) + cos(a)*sin(b);
process(clk)
begin
if rising_edge(clk) then
sina <= SinCoarse(to_integer(unsigned(phase(15 downto 8))));
end if;
end process;
process(clk)
begin
if rising_edge(clk) then
sinb <= SinFine(to_integer(unsigned(phase(7 downto 0))));
end if;
end process;
process(clk)
begin
if rising_edge(clk) then
cosa <= CosCoarse(to_integer(unsigned(phase(15 downto 8))));
end if;
end process;
process(clk)
begin
if rising_edge(clk) then
cosb <= CosFine(to_integer(unsigned(phase(7 downto 0))));
end if;
end process;
process(clk)
begin
if rising_edge(clk) then
sin <= sina*cosb + cosa*sinb;
end if;
end process;
result <= std_logic_vector(to_unsigned(sin, 32));
end Behavioral;
=========================================================================
Report Cell Usage:
+------+--------+------+
| |Cell |Count |
+------+--------+------+
|1 |BUFG | 1|
|2 |DSP48E1 | 2|
|3 |LUT2 | 2|
|4 |LUT3 | 2|
|5 |LUT4 | 1|
|6 |LUT5 | 10|
|7 |LUT6 | 145|
|8 |MUXF7 | 64|
|9 |MUXF8 | 32|
|10 |IBUF | 17|
|11 |OBUF | 16|
+------+--------+------+
Finally, this project requires two multipliers, and this is clearly from the source formula. All tables goes to distributed memory, since they are not so large. LUT are required for this. BRAM usage can be switched by synthesys options or will be applied automatically when larger tabel size will required.
I have several questions here.
1. If you want to go to 32-bit phase, can we simple change MSB of angle parts, increase table sizes and keep this code? How many DSP blocks will be used in this case? What about memory size?
2. If we will go to (a+b+c) approach, are there any hidden traps? Can we simple double the number of calculating resources, i.e. assume d = a+b, calculate sin(a+b), when calculate finale angle as d + c. How many resources will be used in this case?
[toc] | [prev] | [next] | [standalone]
| From | rickman <gnuarm@gmail.com> |
|---|---|
| Date | 2017-02-08 18:22 -0500 |
| Message-ID | <o7g948$huf$1@dont-email.me> |
| In reply to | #54577 |
On 1/31/2017 12:32 PM, Ilya Tarasov wrote:
>
>> You still don't get it. CORDIC is implemented using a large amount of
>> FPGA fabric. Sines can be calculated much more efficiently using hard
>> IP multipliers which use a much smaller area on the chip and so cost
>> less in real estate and so chip cost. They also operate very fast.
>>
>> You seem to be accustomed to designing in the days when multipliers were
>> either not available or to be avoided and so the "no multiplier" aspect
>> of the CORDIC algorithm sounded like a good idea. We are way beyond
>> that with today's chips.
>
> Not only multipliers are cheap. Words are cheap too :)
> Ok, let me do your job. Let's create a project for calculating sin with 16-bit argument. Divide that argument to 8-bit coarse and fine parts. We will need to implement: sin(a+b) = sin(a)*cos(b) + cos(a)*sin(b);
>
> Assume Kintex-7 Xilinx FPGA. First, we will need to create sin annd cos tables, otherwises synthesizer will optimize out empty tables to simple constants.
>
> Here is a Forth script to generate VHDL initialization lines
> ===================================================================
> {
> " sin_coarse.dat" NEWFILE TO HF-OUT
> 256 0 DO
> I .F " => " PRINTF
> I S>F 256.0 F/ PI F* 2.0 F/ FSIN 65535.0 F* F>S
> .F
> " ," PRINTF CRF
> LOOP
>
> HF-OUT CLOSE
>
> " cos_coarse.dat" NEWFILE TO HF-OUT
> 256 0 DO
> I .F " => " PRINTF
> I S>F 256.0 F/ PI F* 2.0 F/ FCOS 65535.0 F* F>S
> .F
> " ," PRINTF CRF
> LOOP
>
> HF-OUT CLOSE
>
> " sin_fine.dat" NEWFILE TO HF-OUT
> 256 0 DO
> I .F " => " PRINTF
> I S>F 256.0 F/ PI F* 2.0 F/ 256.0 F/ FSIN 65535.0 F* F>S
> .F
> " ," PRINTF CRF
> LOOP
>
> HF-OUT CLOSE
>
> " cos_fine.dat" NEWFILE TO HF-OUT
> 256 0 DO
> I .F " => " PRINTF
> I S>F 256.0 F/ PI F* 2.0 F/ 256.0 F/ FCOS 65535.0 F* F>S
> .F
> " ," PRINTF CRF
> LOOP
>
> HF-OUT CLOSE
> }
> ===================================================================
>
> VHDL code
>
> ----------------------------------------------------------------------------library IEEE;
> use IEEE.STD_LOGIC_1164.ALL;
> use IEEE.NUMERIC_STD.ALL;
>
> entity top is
> Port ( clk : in STD_LOGIC;
> phase : in STD_LOGIC_VECTOR (15 downto 0);
> result : out STD_LOGIC_VECTOR (31 downto 0));
> end top;
>
> architecture Behavioral of top is
>
> type TTable is array(0 to 255) of integer range 0 to 65535;
>
> signal SinCoarse : Ttable := (
> 0 => 0 ,
> -- skipped lines generated by Forth
> others => 0);
>
> signal SinFine : Ttable := (
> 0 => 0 ,
> -- skipped lines generated by Forth
> others => 0 );
>
> signal CosCoarse : Ttable := (
> 0 => 65535 ,
> -- skipped lines generated by Forth
> others => 0);
>
> signal CosFine : Ttable := (
> 0 => 65535 ,
> -- skipped lines generated by Forth
> others => 0);
>
> signal sina, sinb, cosa, cosb : integer range 0 to 65535;
> signal sin : integer;
>
> begin
>
> -- sin(a+b) = sin(a)*cos(b) + cos(a)*sin(b);
>
> process(clk)
> begin
> if rising_edge(clk) then
> sina <= SinCoarse(to_integer(unsigned(phase(15 downto 8))));
> end if;
> end process;
>
> process(clk)
> begin
> if rising_edge(clk) then
> sinb <= SinFine(to_integer(unsigned(phase(7 downto 0))));
> end if;
> end process;
>
> process(clk)
> begin
> if rising_edge(clk) then
> cosa <= CosCoarse(to_integer(unsigned(phase(15 downto 8))));
> end if;
> end process;
>
> process(clk)
> begin
> if rising_edge(clk) then
> cosb <= CosFine(to_integer(unsigned(phase(7 downto 0))));
> end if;
> end process;
>
> process(clk)
> begin
> if rising_edge(clk) then
> sin <= sina*cosb + cosa*sinb;
> end if;
> end process;
>
> result <= std_logic_vector(to_unsigned(sin, 32));
>
> end Behavioral;
> =========================================================================
>
> Report Cell Usage:
> +------+--------+------+
> | |Cell |Count |
> +------+--------+------+
> |1 |BUFG | 1|
> |2 |DSP48E1 | 2|
> |3 |LUT2 | 2|
> |4 |LUT3 | 2|
> |5 |LUT4 | 1|
> |6 |LUT5 | 10|
> |7 |LUT6 | 145|
> |8 |MUXF7 | 64|
> |9 |MUXF8 | 32|
> |10 |IBUF | 17|
> |11 |OBUF | 16|
> +------+--------+------+
>
> Finally, this project requires two multipliers, and this is clearly
from the source formula. All tables goes to distributed memory, since
they are not so large. LUT are required for this. BRAM usage can be
switched by synthesys options or will be applied automatically when
larger tabel size will required.
>
> I have several questions here.
>
> 1. If you want to go to 32-bit phase, can we simple change MSB of
> angle parts, increase table sizes and keep this code? How many DSP
> blocks will be used in this case? What about memory size? 2. If we
> will go to (a+b+c) approach, are there any hidden traps? Can we
> simple double the number of calculating resources, i.e. assume d =
> a+b, calculate sin(a+b), when calculate finale angle as d + c. How
> many resources will be used in this case?
Somehow I missed this post. But your code is wrong in that it is
directly implementing the literal trig equation without taking advantage
of any of the simplifications.
The actual equation implemented is:
sin(a+b) = sin(a) + cos(a)*(pi/2)*b,
where a and b are msbs and lsbs of the phase word, each half. The LUT
is indexed by (a) with each entry having a value for sin(a) and
(pi/2)*cos(a). Or call it two tables, both indexed by (a). While
sin(a) is of width N, (pi/2)cos(a) is only of width N/2.
The amount of memory should decrease to 3/2 N width and 2^(N/2) depth.
I don't see memory in your utilization list unless it is the MUXF8 and
MUXF7 items? I don't see anything else in your code that would cause
multiplexers to be used. Perhaps you should invoke the block RAMs.
Given the wide nature of the RAM required, there is no reason to use
distributed memory. 256 x 16 fits nicely in a block RAM.
For this calculation the multiply will only be an 8x8, so one
multiplier. Even with a 32 bit sine word it will only use a single
18x18 bit multiplier.
Regardless, I think you can see even from your data above the savings in
real estate that will result from using the hard IP of block RAMs and
multipliers. That's why they are there.
--
Rick C
[toc] | [prev] | [next] | [standalone]
| From | Ilya Tarasov <ilya74.tarasov@gmail.com> |
|---|---|
| Date | 2017-02-09 01:46 -0800 |
| Message-ID | <8de550af-17ab-4b84-8238-a180ee59e324@googlegroups.com> |
| In reply to | #54728 |
> Somehow I missed this post. But your code is wrong in that it is > directly implementing the literal trig equation without taking advantage > of any of the simplifications. Of course it is 'wrong'! :) Not because I have errors in VHDL (indeed I test in with logic simulator and check sinus wave from 0 to 90 degrees). You told me about vector rotating, I point to existing formula and write an RTL for you. It is from your words. You have something else? Show me and let's compare results. > The actual equation implemented is: > > sin(a+b) = sin(a) + cos(a)*(pi/2)*b, > > where a and b are msbs and lsbs of the phase word, each half. The LUT > is indexed by (a) with each entry having a value for sin(a) and > (pi/2)*cos(a). Or call it two tables, both indexed by (a). While > sin(a) is of width N, (pi/2)cos(a) is only of width N/2. Can you show me the way to achieve this? > The amount of memory should decrease to 3/2 N width and 2^(N/2) depth. > I don't see memory in your utilization list unless it is the MUXF8 and > MUXF7 items? I don't see anything else in your code that would cause > multiplexers to be used. Perhaps you should invoke the block RAMs. > Given the wide nature of the RAM required, there is no reason to use > distributed memory. 256 x 16 fits nicely in a block RAM. Please don't copy my analysis. All of there I wrote in my previous message. You told you don't need to know about FPGA and I show results to you. Small memory size leads to distributed memory instead of block RAM with default synthesizer options (and this is my point, not you are revealing for me). > For this calculation the multiply will only be an 8x8, so one > multiplier. Even with a 32 bit sine word it will only use a single > 18x18 bit multiplier. Hmm. Let's test it. 0xFE * 0xFE = 0xFC04 0xFE7F will rounds to 0xFE, so it should give us the same result 0xFE7F * 0XFE7F = 0xFD004301. Discards lower bits and result is 0xFD00 0xFD00 <> 0xFC04 Comments? You still miss a very important thing from sin calculation in DSP. It is very important and not so clear. Where we need to have 16 bits instead of 8? :) > Regardless, I think you can see even from your data above the savings in > real estate that will result from using the hard IP of block RAMs and > multipliers. That's why they are there. Ok, show me :)
[toc] | [prev] | [next] | [standalone]
| From | rickman <gnuarm@gmail.com> |
|---|---|
| Date | 2017-02-09 05:11 -0500 |
| Message-ID | <o7hf54$b33$1@dont-email.me> |
| In reply to | #54741 |
On 2/9/2017 4:46 AM, Ilya Tarasov wrote: >> Somehow I missed this post. But your code is wrong in that it is >> directly implementing the literal trig equation without taking >> advantage of any of the simplifications. > > Of course it is 'wrong'! :) Not because I have errors in VHDL (indeed > I test in with logic simulator and check sinus wave from 0 to 90 > degrees). You told me about vector rotating, I point to existing > formula and write an RTL for you. It is from your words. You have > something else? Show me and let's compare results. I have been talking about the simplifications for some time now. Regardless, the code you produced shows how simple the design is when using the multipliers. >> The actual equation implemented is: >> >> sin(a+b) = sin(a) + cos(a)*(pi/2)*b, >> >> where a and b are msbs and lsbs of the phase word, each half. The >> LUT is indexed by (a) with each entry having a value for sin(a) and >> (pi/2)*cos(a). Or call it two tables, both indexed by (a). While >> sin(a) is of width N, (pi/2)cos(a) is only of width N/2. > > Can you show me the way to achieve this? I'm not sure what you are asking. I'm just saying that you created three tables when only two are needed. One is the full 32 bit width and the other is only 16 bit width since the upper bits of the 32 bit product will all be zero. >> The amount of memory should decrease to 3/2 N width and 2^(N/2) >> depth. I don't see memory in your utilization list unless it is the >> MUXF8 and MUXF7 items? I don't see anything else in your code that >> would cause multiplexers to be used. Perhaps you should invoke the >> block RAMs. Given the wide nature of the RAM required, there is no >> reason to use distributed memory. 256 x 16 fits nicely in a block >> RAM. > > Please don't copy my analysis. All of there I wrote in my previous > message. You told you don't need to know about FPGA and I show > results to you. Small memory size leads to distributed memory instead > of block RAM with default synthesizer options (and this is my point, > not you are revealing for me). Don't copy your analysis??? I don't know what you mean. Are you sure you wish to continue this discussion? >> For this calculation the multiply will only be an 8x8, so one >> multiplier. Even with a 32 bit sine word it will only use a single >> 18x18 bit multiplier. > > Hmm. Let's test it. > > 0xFE * 0xFE = 0xFC04 0xFE7F will rounds to 0xFE, so it should give us > the same result > > 0xFE7F * 0XFE7F = 0xFD004301. Discards lower bits and result is > 0xFD00 > > 0xFD00 <> 0xFC04 > > Comments? > > You still miss a very important thing from sin calculation in DSP. It > is very important and not so clear. Where we need to have 16 bits > instead of 8? :) > >> Regardless, I think you can see even from your data above the >> savings in real estate that will result from using the hard IP of >> block RAMs and multipliers. That's why they are there. > > Ok, show me :) You have the numbers. What more do you need? -- Rick C
[toc] | [prev] | [next] | [standalone]
| From | rickman <gnuarm@gmail.com> |
|---|---|
| Date | 2017-02-12 01:30 -0500 |
| Message-ID | <o7ovau$66h$1@dont-email.me> |
| In reply to | #54537 |
On 1/30/2017 2:11 AM, Ilya Tarasov wrote: > >> I don't know why you label this an approximation. The level of accuracy >> is controlled by the tradeoff of how many of the total phase bits you >> assign to a and b. Any level of accuracy required can be obtained. You >> need to appreciate fully how close to a straight line the small section >> of a sine function is over very short angles. It is not at all hard to >> get the accuracy within a single lsb. > > Because of 'for small b'. This is a limitation. Approximation is not > a disadvantage by default, but we may face a problem attempting to > improve precision. Exact formula don't require any kind of > improvement, because it provide any accuracy by default. If it is not > exact, we must always answer a question 'how small b must be to > obtain desired accuracy?'. Also, different ways to approximation may > be applied - what about playing with polynom order? I did a little digging and found why there seemed to be something about CORDIC that didn't quite sit. The algorithm for CORDIC iterates calculations on the sine and cosine of an angle by rotating the vector, adding and subtracting from the angle until the angle is zero... or approximately zero. The way the math works, the sine and cosine will always be *exact*, that is true. But it will just be for the wrong angle! Yep, the angle is adjusted by adding and subtracting table values until it is close to zero. But each table value has a built in error of up to ±0.5 lsbs. For a 32 bit value there will be at least 32 iterations which means the errors can combine to as much as ±16 counts in the lsb of the phase angle. This is on top of the potential ±1 lsb due to the angle not resolving fully. This has a quirk where in the next to last iteration the angle can have resolved perfectly and the final step throws it off by 1. Of course the rounding errors are likely uncorrelated so the typical error will be 0.5*sqrt(32) or around 2.8 plus the resolution error. The analysis I've done with the trig approach indicates maximum errors in the range of ±1.5 lsbs and a lower typical and average. Is this wrong? BTW, the small b "approximation" is not a source of significant error. This simply determines where you divide the angle into the (a) bits and (b) bits. Choose (a) to be large enough and cos(b) is as close to 1 as you like. -- Rick C
[toc] | [prev] | [next] | [standalone]
| From | Ilya Tarasov <ilya74.tarasov@gmail.com> |
|---|---|
| Date | 2017-02-12 10:21 -0800 |
| Message-ID | <78a6cb97-3479-42ea-ade2-03c22b4d69d4@googlegroups.com> |
| In reply to | #54804 |
> I did a little digging and found why there seemed to be something about > CORDIC that didn't quite sit. The algorithm for CORDIC iterates > calculations on the sine and cosine of an angle by rotating the vector, > adding and subtracting from the angle until the angle is zero... or > approximately zero. The way the math works, the sine and cosine will > always be *exact*, that is true. But it will just be for the wrong angle! I don't think 'wrong' is applicable here. Every kind of iterative approaching algorithms has a built-in error, which decreased by every iteration. The real power of iterarive approach is an ability to decrease this error. > Yep, the angle is adjusted by adding and subtracting table values until > it is close to zero. But each table value has a built in error of up to > ±0.5 lsbs. For a 32 bit value there will be at least 32 iterations > which means the errors can combine to as much as ±16 counts in the lsb > of the phase angle. This is on top of the potential ±1 lsb due to the > angle not resolving fully. This has a quirk where in the next to last > iteration the angle can have resolved perfectly and the final step > throws it off by 1. > > Of course the rounding errors are likely uncorrelated so the typical > error will be 0.5*sqrt(32) or around 2.8 plus the resolution error. The > analysis I've done with the trig approach indicates maximum errors in > the range of ±1.5 lsbs and a lower typical and average. > > Is this wrong? This number looks real anough. Of course, performing math operations with numbers with errors will lead to error propagation, and more iterations means more error. Every approach has its own range of optimal characteristics by time, area, memory size etc. If you reach 1.5 LSBS tolerance, but need more, you can add two iterations and that 1.5 LSBS will related to 34 bits, not 32. > BTW, the small b "approximation" is not a source of significant error. > This simply determines where you divide the angle into the (a) bits and > (b) bits. Choose (a) to be large enough and cos(b) is as close to 1 as > you like. In average, approaches sequence usually looks like 'tables -> approximation/series -> iterations'. Table size typically growing by 2^N law (with some tricks maybe), approximation typically has a kind of saturation (can you provide 64 bits?). More important another question you still didn't answer. For 32-bit angle and 32-bit datawidth, what is more important to keep at their level? Here we have time and (typically) voltage from ADC - that value has better precision?
[toc] | [prev] | [next] | [standalone]
| From | rickman <gnuarm@gmail.com> |
|---|---|
| Date | 2017-02-12 19:37 -0500 |
| Message-ID | <o7qv0f$oo0$1@dont-email.me> |
| In reply to | #54812 |
On 2/12/2017 1:21 PM, Ilya Tarasov wrote: >> I did a little digging and found why there seemed to be something >> about CORDIC that didn't quite sit. The algorithm for CORDIC >> iterates calculations on the sine and cosine of an angle by >> rotating the vector, adding and subtracting from the angle until >> the angle is zero... or approximately zero. The way the math >> works, the sine and cosine will always be *exact*, that is true. >> But it will just be for the wrong angle! > > I don't think 'wrong' is applicable here. Every kind of iterative > approaching algorithms has a built-in error, which decreased by every > iteration. The real power of iterarive approach is an ability to > decrease this error. The point is that the answer is not an exact answer to the question because while the calculation of the answer *is* exact, it is answering the wrong question even if only by a small amount. So in the end the CORDIC is no more exact than other methods and is ill suited in most cases because of the large resource usage. >> Yep, the angle is adjusted by adding and subtracting table values >> until it is close to zero. But each table value has a built in >> error of up to ±0.5 lsbs. For a 32 bit value there will be at >> least 32 iterations which means the errors can combine to as much >> as ±16 counts in the lsb of the phase angle. This is on top of the >> potential ±1 lsb due to the angle not resolving fully. This has a >> quirk where in the next to last iteration the angle can have >> resolved perfectly and the final step throws it off by 1. >> >> Of course the rounding errors are likely uncorrelated so the >> typical error will be 0.5*sqrt(32) or around 2.8 plus the >> resolution error. The analysis I've done with the trig approach >> indicates maximum errors in the range of ±1.5 lsbs and a lower >> typical and average. >> >> Is this wrong? > > This number looks real anough. Of course, performing math operations > with numbers with errors will lead to error propagation, and more > iterations means more error. Every approach has its own range of > optimal characteristics by time, area, memory size etc. If you reach > 1.5 LSBS tolerance, but need more, you can add two iterations and > that 1.5 LSBS will related to 34 bits, not 32. Of course, any method can be done in extended precision and the result rounded. >> BTW, the small b "approximation" is not a source of significant >> error. This simply determines where you divide the angle into the >> (a) bits and (b) bits. Choose (a) to be large enough and cos(b) is >> as close to 1 as you like. > > In average, approaches sequence usually looks like 'tables -> > approximation/series -> iterations'. Table size typically growing by > 2^N law (with some tricks maybe), approximation typically has a kind > of saturation (can you provide 64 bits?). I don't need 64 bits <grin>. I still haven't heard the use case for 32 bits. Why do you need 32 bits of accuracy? BTW, a 32 bit address lookup table is not really a bit issue. That is just 4 giga-entries. Or it can be broken down to a pair of tables using the same trig algorithm but this time with a full two multiplies as the cos(b)=b identity won't be true. Still, that's a total of three multiplies which is the same complexity as the CORDIC. The difference is it doesn't implement it all using FPGA fabric. Don't think that CORDIC doesn't have issues with word size. It is order N^2 complexity. So a 64 bit calculation would be rather huge in an FPGA using some 14,000 LUTs if I recall your earlier numbers correctly. That's actually more than four times larger than the FPGA I am generating sines from to do testing on interface boards. > More important another question you still didn't answer. For 32-bit > angle and 32-bit datawidth, what is more important to keep at their > level? Here we have time and (typically) voltage from ADC - that > value has better precision? Sorry, I don't understand the question. "Their level" and "that value has better precision" don't make sense to me. Who is "they" and what is "that"? -- Rick C
[toc] | [prev] | [next] | [standalone]
| From | Ilya Tarasov <ilya74.tarasov@gmail.com> |
|---|---|
| Date | 2017-02-14 13:26 -0800 |
| Message-ID | <46de8e59-9208-4178-acb1-3184bcac1013@googlegroups.com> |
| In reply to | #54820 |
> The point is that the answer is not an exact answer to the question > because while the calculation of the answer *is* exact, it is answering > the wrong question even if only by a small amount. > > So in the end the CORDIC is no more exact than other methods and is ill > suited in most cases because of the large resource usage. CORDIC IP-core is useful for FPGA, so it is definitely not a blind lead. I don't know what is 'large', because it is not a number :) We need to evaluate parameters from other points of view, and CORDIC is not simply larger, it is just use logic cells instead of multipliers and BRAMs. > Of course, any method can be done in extended precision and the result > rounded. Having just two more iterations looks acceptable. > I don't need 64 bits <grin>. I still haven't heard the use case for 32 > bits. Why do you need 32 bits of accuracy? BTW, a 32 bit address This don't equal to 'nobody needs it'. I know how to use 32 and even more bits for harmonic functions. > lookup table is not really a bit issue. That is just 4 giga-entries. > Or it can be broken down to a pair of tables using the same trig > algorithm but this time with a full two multiplies as the cos(b)=b > identity won't be true. Still, that's a total of three multiplies which > is the same complexity as the CORDIC. The difference is it doesn't > implement it all using FPGA fabric. 4G is not an issue? Really? Do you think DDR3 interfacing is simple just because we can see gigabytes of memory everywhere? PCB routing challenges are very difficult and it is not so simple to design and test high-speed boards with DDR memory. No matter we can see it in every desktop, notebook and phone. Implementing module inside FPGA is much more easier than route high-speed traces and provide signal integrity. > Don't think that CORDIC doesn't have issues with word size. It is order > N^2 complexity. So a 64 bit calculation would be rather huge in an FPGA > using some 14,000 LUTs if I recall your earlier numbers correctly. > That's actually more than four times larger than the FPGA I am > generating sines from to do testing on interface boards. Than _your_ FPGA - this is a key point. Many developers may have other FPGAs and requirements. Do you want to force them to forget CORDIC because your requirements is simpler? > > More important another question you still didn't answer. For 32-bit > > angle and 32-bit datawidth, what is more important to keep at their > > level? Here we have time and (typically) voltage from ADC - that > > value has better precision? > > Sorry, I don't understand the question. "Their level" and "that value > has better precision" don't make sense to me. Who is "they" and what is > "that"? You have 16-bit argument (angle) and 16-bitsin value. With 32-bit,what is more valuable for generic DSP task - to have 32-bit angle or to have 32-bit sin value? Why?
[toc] | [prev] | [next] | [standalone]
| From | Gary Bergstrom <forthprgrmr@gmail.com> |
|---|---|
| Date | 2017-02-14 11:36 -0800 |
| Message-ID | <dc91cd2f-ba4b-4e8e-990b-b004bdb8dbc6@googlegroups.com> |
| In reply to | #54804 |
On Sunday, February 12, 2017 at 1:30:36 AM UTC-5, rickman wrote: > On 1/30/2017 2:11 AM, Ilya Tarasov wrote: > > > >> I don't know why you label this an approximation. The level of accuracy > >> is controlled by the tradeoff of how many of the total phase bits you > >> assign to a and b. Any level of accuracy required can be obtained. You > >> need to appreciate fully how close to a straight line the small section > >> of a sine function is over very short angles. It is not at all hard to > >> get the accuracy within a single lsb. > > > > Because of 'for small b'. This is a limitation. Approximation is not > > a disadvantage by default, but we may face a problem attempting to > > improve precision. Exact formula don't require any kind of > > improvement, because it provide any accuracy by default. If it is not > > exact, we must always answer a question 'how small b must be to > > obtain desired accuracy?'. Also, different ways to approximation may > > be applied - what about playing with polynom order? > > I did a little digging and found why there seemed to be something about > CORDIC that didn't quite sit. The algorithm for CORDIC iterates > calculations on the sine and cosine of an angle by rotating the vector, > adding and subtracting from the angle until the angle is zero... or > approximately zero. The way the math works, the sine and cosine will > always be *exact*, that is true. But it will just be for the wrong angle! > > Yep, the angle is adjusted by adding and subtracting table values until > it is close to zero. But each table value has a built in error of up to > ±0.5 lsbs. For a 32 bit value there will be at least 32 iterations > which means the errors can combine to as much as ±16 counts in the lsb > of the phase angle. This is on top of the potential ±1 lsb due to the > angle not resolving fully. This has a quirk where in the next to last > iteration the angle can have resolved perfectly and the final step > throws it off by 1. > > Of course the rounding errors are likely uncorrelated so the typical > error will be 0.5*sqrt(32) or around 2.8 plus the resolution error. The > analysis I've done with the trig approach indicates maximum errors in > the range of ±1.5 lsbs and a lower typical and average. > > Is this wrong? It's been a while since I did Cordic routines, but if you're going from table values, given an exact angle and reading out a table value for the sin/cos terms to add/substract you don't have an error in the angle as the tables are created for specific angles, not approximate angles. On the other hand, there is only so much information in the amplitude. Try to make a sine wave oscillator run continuously by rotating for a few 100 or 1000 million cycles and your amplitudes won't be very accurate anymore. About doing a minimax polynomial: My lowly DSP56k cpu can be made to evaluate an nth order polynomial in n+5 cycles. If you're going for a processor rather than a hardware solution, it's difficult to beat this sort of speed. But if you don't have a multiply (who doesn't?) or you're deeply embedded within a logic array, then Cordic can make a lot of sense. Generating near zero distortion audio sine waves is an interesting hobby. gary
[toc] | [prev] | [next] | [standalone]
| From | rickman <gnuarm@gmail.com> |
|---|---|
| Date | 2017-02-14 18:13 -0500 |
| Message-ID | <o802qq$oud$1@dont-email.me> |
| In reply to | #54853 |
On 2/14/2017 2:36 PM, Gary Bergstrom wrote: > On Sunday, February 12, 2017 at 1:30:36 AM UTC-5, rickman wrote: >> On 1/30/2017 2:11 AM, Ilya Tarasov wrote: >>> >>>> I don't know why you label this an approximation. The level of >>>> accuracy is controlled by the tradeoff of how many of the total >>>> phase bits you assign to a and b. Any level of accuracy >>>> required can be obtained. You need to appreciate fully how >>>> close to a straight line the small section of a sine function >>>> is over very short angles. It is not at all hard to get the >>>> accuracy within a single lsb. >>> >>> Because of 'for small b'. This is a limitation. Approximation is >>> not a disadvantage by default, but we may face a problem >>> attempting to improve precision. Exact formula don't require any >>> kind of improvement, because it provide any accuracy by default. >>> If it is not exact, we must always answer a question 'how small b >>> must be to obtain desired accuracy?'. Also, different ways to >>> approximation may be applied - what about playing with polynom >>> order? >> >> I did a little digging and found why there seemed to be something >> about CORDIC that didn't quite sit. The algorithm for CORDIC >> iterates calculations on the sine and cosine of an angle by >> rotating the vector, adding and subtracting from the angle until >> the angle is zero... or approximately zero. The way the math >> works, the sine and cosine will always be *exact*, that is true. >> But it will just be for the wrong angle! >> >> Yep, the angle is adjusted by adding and subtracting table values >> until it is close to zero. But each table value has a built in >> error of up to ±0.5 lsbs. For a 32 bit value there will be at >> least 32 iterations which means the errors can combine to as much >> as ±16 counts in the lsb of the phase angle. This is on top of the >> potential ±1 lsb due to the angle not resolving fully. This has a >> quirk where in the next to last iteration the angle can have >> resolved perfectly and the final step throws it off by 1. >> >> Of course the rounding errors are likely uncorrelated so the >> typical error will be 0.5*sqrt(32) or around 2.8 plus the >> resolution error. The analysis I've done with the trig approach >> indicates maximum errors in the range of ±1.5 lsbs and a lower >> typical and average. >> >> Is this wrong? > > It's been a while since I did Cordic routines, but if you're going > from table values, given an exact angle and reading out a table value > for the sin/cos terms to add/substract you don't have an error in the > angle as the tables are created for specific angles, not approximate > angles. That is not accurate. The tables are created for rotations so the math in the matrix operations are simple shifts and adds. This does *not* give exact binary multiples for the actual angles. > On the other hand, there is only so much information in the > amplitude. Try to make a sine wave oscillator run continuously by > rotating for a few 100 or 1000 million cycles and your amplitudes > won't be very accurate anymore. About doing a minimax polynomial: My > lowly DSP56k cpu can be made to evaluate an nth order polynomial in > n+5 cycles. If you're going for a processor rather than a hardware > solution, it's difficult to beat this sort of speed. But if you don't > have a multiply (who doesn't?) or you're deeply embedded within a > logic array, then Cordic can make a lot of sense. Generating near > zero distortion audio sine waves is an interesting hobby. I'm not clear on what the amplitude error you are referring to would be. Both methods track time with a phase incrementer and use the circuits being discussed to convert that to a sine value. The only error in the phase over many cycles would be the limitation of the size of the phase step value. The amplitude would be true to the accuracy of the sine conversion. -- Rick C
[toc] | [prev] | [next] | [standalone]
| From | rickman <gnuarm@gmail.com> |
|---|---|
| Date | 2017-01-28 21:51 -0500 |
| Message-ID | <o6jl7s$dm6$1@dont-email.me> |
| In reply to | #54500 |
On 1/28/2017 6:05 PM, Ilya Tarasov wrote: >> I think you are still not getting it, but I can't tell for sure. >> The point is that either the CORDIC or a multiplier uses pretty >> much the same resources if designed in the fabric. Don't focus on >> one insignificant part (the shifting which is always free in an >> FPGA). What is important is what is done with the data after it is >> shifted. > > Please specify. Do you mean approach, based on sin(a+b)? If so, we > use sin(a+b) = sin(a)*cos(b) + cos(a)*sin(b), and this require > multiplication of sin and cos values. Is it what you talking about? I am talking about the fact that you are making a big distinction between a CORDIC computation and a multiplier when there is only one real difference. A CORDIC computation will use virtually the same resources in the FPGA fabric as an equivalent multiply, likely more. But the difference is that most FPGAs include hard IP multipliers! Hard IP uses *much* less silicon area than anything done in the fabric. Altera has recently announced hard IP floating point ALUs. >> Both the multiplier and the CORDIC can be done time sequentially >> using logic for one layer of operation or can be pipelined with N >> layers of logic and registers producing a result on every clock >> cycle. > > We need to compare algorithm with algorithm and implementation with > implementation. CORDIC is an implementation, where sequental applying > of sin(a+b) formulae is an algorithm. Multiplication is an > implementation. What algorithm you use? At this point I have lost my interest in debating this much further. CORDIC is not the only method of calculating rotating vectors. It is useful where you have a lack of computing resources. If multiplication is readily available other methods compare very favorably. >>> This is not too much resources for serious system. For example, >>> 32-bit sin/cos use 403 LUTs in word serial and 3411 in parallel >>> mode. For Kintex-7, the ratio of LUT/DSP is about 200-300. >> >> That is a pretty large usage. I can do the same thing using a >> handful of multipliers. In 403 LUTs I can build a CPU. In 3400 >> LUTs I can build a RISC pipelined CPU with advanced features. > > This corresponds with what I know. However, area itself is not an > indicator. We need to know what else is located inside FPGA, and what > resources are most important to save. With several approaches we can > consider a workaround when certain type of FPGA resources is running > low. > >> The FPGAs I use in a product that generate sine waves (among other >> things) has a total of 3000 LUTs. Of course it only runs at 8 >> ksps and these are 16 bit samples. > > What about performance index of you approach? For example, (bits * > samples_per_second)/LUT. We can calculate this from Xilinx table. In > general, if FPGA is not very large, we may start from serial > algorithms. > >>> Simplest way based on the wide phase accumulator and control the >>> phase increment value. Also, you can change base frequency of >>> overall DSP path in hardware using dynamic reconfiguration port >>> in Clock Management Tile (I mean Xilinx chips). >> >> That sounds like any other DDS. You either change the phase step >> or change the reference frequency. So the phase step size can be >> changed on the fly for frequency modulation? > > Yes, with control registers. If we write phase <= phase + > phase_delta; it is possible to connect phase_delta register to CPU > system bus (and directly control phase register on the fly too). We > use Forth CPU for control. > > Task of such kind are very informative. Forth CPU allows to connect > devices very easy with no overhead on complex system buses like AXI. > In this case, it is not so important, what is the performance or area > of Forth CPU, because it used for real task with it's own > valuability. I'm sure you can imagine the power of hardware module, > running on FPGA. With any CPU it's functionality is greatly improving > because of reconfiguration capabilities. With Forth CPU we can > additionally adapt this system to the man who works with hardware and > tightly connect CPU to hardware. What exactly is a "Forth CPU"? -- Rick C
[toc] | [prev] | [next] | [standalone]
| From | Ilya Tarasov <ilya74.tarasov@gmail.com> |
|---|---|
| Date | 2017-01-29 10:20 -0800 |
| Message-ID | <4b343d40-7252-4919-8e0d-aeace01a87cd@googlegroups.com> |
| In reply to | #54509 |
> > Please specify. Do you mean approach, based on sin(a+b)? If so, we > > use sin(a+b) = sin(a)*cos(b) + cos(a)*sin(b), and this require > > multiplication of sin and cos values. Is it what you talking about? > > I am talking about the fact that you are making a big distinction > between a CORDIC computation and a multiplier when there is only one > real difference. A CORDIC computation will use virtually the same > resources in the FPGA fabric as an equivalent multiply, likely more. > But the difference is that most FPGAs include hard IP multipliers! Hard > IP uses *much* less silicon area than anything done in the fabric. > Altera has recently announced hard IP floating point ALUs. You still don't list your algorithm details. Maybe it will consume LUTs in other parts, for control structures or so on. Of course, I know about hard multipliers (with 10+ years experience of approved Xilinx trainer it is very hard to miss something important). You need to store angles, sin/cos values and provide datapath control (sequental, pipelined or mixed). If you still can provide maximum error with 1 LSB for any datawidth, it is interesting. If not, it is an approximation, suitable for some purposes. > At this point I have lost my interest in debating this much further. > CORDIC is not the only method of calculating rotating vectors. It is > useful where you have a lack of computing resources. If multiplication > is readily available other methods compare very favorably. So what is your method? > > because of reconfiguration capabilities. With Forth CPU we can > > additionally adapt this system to the man who works with hardware and > > tightly connect CPU to hardware. > > What exactly is a "Forth CPU"? I have several designs. Now it is 7th generation of microarchitecture, with hardware multithreading, targeting Spartan-6 and 7-series Xilinx FPGAs. > How fast can a CORDIC be done? From 175 MHz to 300-400, depends on FPGA famuly, function calculated, datawidth and serial/parallel architecture.
[toc] | [prev] | [next] | [standalone]
| From | Cecil Bayona <cbayona@cbayona.com> |
|---|---|
| Date | 2017-01-29 12:38 -0600 |
| Message-ID | <o6lcoq$kqg$1@dont-email.me> |
| In reply to | #54523 |
On 1/29/2017 12:20 PM, Ilya Tarasov wrote: >>> Please specify. Do you mean approach, based on sin(a+b)? If so, we >>> use sin(a+b) = sin(a)*cos(b) + cos(a)*sin(b), and this require >>> multiplication of sin and cos values. Is it what you talking about? >> >> I am talking about the fact that you are making a big distinction >> between a CORDIC computation and a multiplier when there is only one >> real difference. A CORDIC computation will use virtually the same >> resources in the FPGA fabric as an equivalent multiply, likely more. >> But the difference is that most FPGAs include hard IP multipliers! Hard >> IP uses *much* less silicon area than anything done in the fabric. >> Altera has recently announced hard IP floating point ALUs. > > You still don't list your algorithm details. Maybe it will consume LUTs in other parts, for control structures or so on. Of course, I know about hard multipliers (with 10+ years experience of approved Xilinx trainer it is very hard to miss something important). You need to store angles, sin/cos values and provide datapath control (sequental, pipelined or mixed). If you still can provide maximum error with 1 LSB for any datawidth, it is interesting. If not, it is an approximation, suitable for some purposes. > >> At this point I have lost my interest in debating this much further. >> CORDIC is not the only method of calculating rotating vectors. It is >> useful where you have a lack of computing resources. If multiplication >> is readily available other methods compare very favorably. > > So what is your method? > >>> because of reconfiguration capabilities. With Forth CPU we can >>> additionally adapt this system to the man who works with hardware and >>> tightly connect CPU to hardware. >> >> What exactly is a "Forth CPU"? > > I have several designs. Now it is 7th generation of microarchitecture, with hardware multithreading, targeting Spartan-6 and 7-series Xilinx FPGAs. > >> How fast can a CORDIC be done? > > From 175 MHz to 300-400, depends on FPGA famuly, function calculated, datawidth and serial/parallel architecture. > Do you have a website that discuses the CPUs? I would be interested in looking to get ideas which considered by many as a bad idea to begin with. -- Cecil - k5nwa
[toc] | [prev] | [next] | [standalone]
| From | Ilya Tarasov <ilya74.tarasov@gmail.com> |
|---|---|
| Date | 2017-01-29 11:49 -0800 |
| Message-ID | <256e62ab-ec2e-4d63-9664-aa27b8e85597@googlegroups.com> |
| In reply to | #54525 |
> > From 175 MHz to 300-400, depends on FPGA famuly, function calculated, datawidth and serial/parallel architecture. > > > Do you have a website that discuses the CPUs? I would be interested in > looking to get ideas which considered by many as a bad idea to begin with. www.fforum.winglion.ru Write me your nick for manual approving (too many bots attempting to register). I ay note there is no 'perfect CPU'. I have no plans to sell my designs or call others to take part. More effective is to explain how to create CPU and make it optimized for certain purpose.
[toc] | [prev] | [next] | [standalone]
| From | rickman <gnuarm@gmail.com> |
|---|---|
| Date | 2017-02-04 04:22 -0500 |
| Message-ID | <o746dg$mbj$1@dont-email.me> |
| In reply to | #54523 |
On 1/29/2017 1:20 PM, Ilya Tarasov wrote: >>> Please specify. Do you mean approach, based on sin(a+b)? If so, >>> we use sin(a+b) = sin(a)*cos(b) + cos(a)*sin(b), and this >>> require multiplication of sin and cos values. Is it what you >>> talking about? >> >> I am talking about the fact that you are making a big distinction >> between a CORDIC computation and a multiplier when there is only >> one real difference. A CORDIC computation will use virtually the >> same resources in the FPGA fabric as an equivalent multiply, likely >> more. But the difference is that most FPGAs include hard IP >> multipliers! Hard IP uses *much* less silicon area than anything >> done in the fabric. Altera has recently announced hard IP floating >> point ALUs. > > You still don't list your algorithm details. Maybe it will consume > LUTs in other parts, for control structures or so on. Of course, I > know about hard multipliers (with 10+ years experience of approved > Xilinx trainer it is very hard to miss something important). You need > to store angles, sin/cos values and provide datapath control > (sequental, pipelined or mixed). If you still can provide maximum > error with 1 LSB for any datawidth, it is interesting. If not, it is > an approximation, suitable for some purposes. You mean I don't have a fully coded VHDL example at 32 bits word width to show you? No, I don't. But that is not needed. The control logic would be trivial compared to thousands of LUTs. The only extra logic required is on the order of a handful of adders and/or multiplexers. I took the time to do some calculations which show to get results accurate to all but the last bit of a 32 bit word would require a sin() table with a quarter of a million values. That would put it outside the realm of most FPGAs and require external memory. However if external memory is used, this is not only feasible but simple. The only issue is to get the step sizes small enough so the two approximations do apply, sin(b)=b and cos(b)=1.0 to within the required accuracy. I've never seen an application that needed 32 bits of sin/cos. The DDS work I've done was related to real world signals which are limited to some 20 to 24 bits of SNR when converting between analog and digital at very best. I was pretty happy when I showed myself I could get 20 bits without any real trouble. >> At this point I have lost my interest in debating this much >> further. CORDIC is not the only method of calculating rotating >> vectors. It is useful where you have a lack of computing >> resources. If multiplication is readily available other methods >> compare very favorably. > > So what is your method? > >>> because of reconfiguration capabilities. With Forth CPU we can >>> additionally adapt this system to the man who works with hardware >>> and tightly connect CPU to hardware. >> >> What exactly is a "Forth CPU"? > > I have several designs. Now it is 7th generation of > microarchitecture, with hardware multithreading, targeting Spartan-6 > and 7-series Xilinx FPGAs. But that doesn't tell me what a Forth CPU is. I assume you really mean a stack machine. When you say "hardware multithreading", I expect this is using the pipeline to facilitate multiple threads rather than concurrent instructions in a single thread? >> How fast can a CORDIC be done? > > From 175 MHz to 300-400, depends on FPGA famuly, function calculated, > datawidth and serial/parallel architecture. Yeah, that would be a typical pipelined speed. -- Rick C
[toc] | [prev] | [next] | [standalone]
| From | Ilya Tarasov <ilya74.tarasov@gmail.com> |
|---|---|
| Date | 2017-02-04 17:54 -0800 |
| Message-ID | <5feb22db-9f9c-46df-bdc8-9ae4e14d275d@googlegroups.com> |
| In reply to | #54623 |
> You mean I don't have a fully coded VHDL example at 32 bits word width > to show you? No, I don't. But that is not needed. The control logic > would be trivial compared to thousands of LUTs. The only extra logic > required is on the order of a handful of adders and/or multiplexers. So you can't show me a code and utilization report, but still claiming area will be small? How small? What about 'only extra logic' and how you can estimate the size of adders/multiplexers for you code? > I took the time to do some calculations which show to get results > accurate to all but the last bit of a 32 bit word would require a sin() > table with a quarter of a million values. That would put it outside the > realm of most FPGAs and require external memory. However if external > memory is used, this is not only feasible but simple. The only issue is > to get the step sizes small enough so the two approximations do apply, > sin(b)=b and cos(b)=1.0 to within the required accuracy. Again, I don't see you 'required accuracy'. Can you list your results and explain how you got it? > I've never seen an application that needed 32 bits of sin/cos. The DDS > work I've done was related to real world signals which are limited to > some 20 to 24 bits of SNR when converting between analog and digital at > very best. I was pretty happy when I showed myself I could get 20 bits > without any real trouble. The fact you don't need it is not a fact nobody need it. ADC resolution matters, but this is not the only factor to choose sin/cos resolution. Results with single precision and double-precision floats are not the same for given ADC. Again, I can write a piece of Forth code to show the difference... but maybe you will switch from thinking to coding? > > I have several designs. Now it is 7th generation of > > microarchitecture, with hardware multithreading, targeting Spartan-6 > > and 7-series Xilinx FPGAs. > > But that doesn't tell me what a Forth CPU is. I assume you really mean > a stack machine. When you say "hardware multithreading", I expect this > is using the pipeline to facilitate multiple threads rather than > concurrent instructions in a single thread? Yes, I really mean a stack machine, i.e. words like DUP DROP + - AND OR are executed in one clock cycle with all appropriate modifications to stack pointers etc. Multiple threads are supported by time multiplexing, so one data memory and one ALU are shared between all threads, but each clock cycle belongs to its own thread.
[toc] | [prev] | [next] | [standalone]
| From | hughaguilar96@gmail.com |
|---|---|
| Date | 2017-02-04 20:26 -0800 |
| Message-ID | <16c24a97-fe0f-4e16-967b-6e3b058ba4e7@googlegroups.com> |
| In reply to | #54632 |
On Saturday, February 4, 2017 at 6:54:16 PM UTC-7, Ilya Tarasov wrote: > Yes, I really mean a stack machine, i.e. words like DUP DROP + - AND OR are executed in one clock cycle with all appropriate modifications to stack pointers etc. Multiple threads are supported by time multiplexing, so one data memory and one ALU are shared between all threads, but each clock cycle belongs to its own thread. What you have is nothing like the MiniForth (now known as the RACE). What you have is like Paysan's B16 or my Stundurd design. The MiniForth had an assembly-language. Primitives such as DUP DROP + - AND OR etc. were written in this assembly-language. It was Harvard Architecture --- the machine-code had a different memory from the data and threaded code --- the two memories could be accessed simultaneously. There was no CALL primitive --- the 16-bit cfa compiled in the threaded code had one bit that indicated if it was a primitive or a colon word. The machine-code had up to 5 instructions packed into a single opcode, all of which executed in one clock cycle. My assembler would rearrange the instructions in such a way as to pack as many into the opcodes together as possible (minimize how many NOPs had to be inserted) while still guaranteeing that the code did the same thing as if the instructions were assembled one per opcode in the order that they appeared in the source-code. This is more robust than your method because there can be any number of primitives --- I had hundreds --- you are limited to 32 or 64 primitives (some small number that can't be increased). P.S. Do you really think that Rickman has actually built an FPGA processor? Or is this all fantasy on his part? Does he seem like he actually knows VHDL, or did he just read a book on it but never attain any actual experience? I know that he's faking his Forth software expertise, which makes me think he is faking his FPGA expertise too.
[toc] | [prev] | [next] | [standalone]
Page 5 of 7 — ← Prev page 1 2 3 4 [5] 6 7 Next page →
Back to top | Article view | comp.lang.forth
csiph-web