FPGA Central - World's 1st FPGA / CPLD Portal

FPGA Central

World's 1st FPGA Portal

 

Go Back   FPGA Groups > NewsGroup > Verilog

Verilog comp.lang.verilog newsgroup / usenet

Reply
 
LinkBack Thread Tools Display Modes
  #1 (permalink)  
Old 07-30-2006, 03:42 PM
Nevo
Guest
 
Posts: n/a
Default Divide-by-14 in Xilinx Spartan FPGA's

First off, I'm completely new to FPGA's and Verilog. I'm also self-taught,
with no formal education in digital electronics. So if I'm asking a question
with an obvious answer, that's probably why.

I need to implement a divide-by-14 operation in a Xilinx Spartan FPGA. I
thought it would be a simple matter of using the Verilog / operator, but XST
throws an error since it only supports division by powers of 2.

Can someone point me to a tutorial or other resource for helping me
understand how to implement a divide-by-14 in hardware?

Thanks,

-Nevo


Reply With Quote
  #2 (permalink)  
Old 07-30-2006, 05:34 PM
John_H
Guest
 
Posts: n/a
Default Re: Divide-by-14 in Xilinx Spartan FPGA's

Nevo wrote:
> First off, I'm completely new to FPGA's and Verilog. I'm also self-taught,
> with no formal education in digital electronics. So if I'm asking a question
> with an obvious answer, that's probably why.
>
> I need to implement a divide-by-14 operation in a Xilinx Spartan FPGA. I
> thought it would be a simple matter of using the Verilog / operator, but XST
> throws an error since it only supports division by powers of 2.
>
> Can someone point me to a tutorial or other resource for helping me
> understand how to implement a divide-by-14 in hardware?
>
> Thanks,
>
> -Nevo


Resource? I don't have one handy. I recall "egyption division
algorithm" from one of the previous posts on this newsgroup but that's
more for information, not your specific problem.

Division requires one add/sub per result bit with a delay for the full
carry output before the next stage can begin. It's not a fast
algorithm. What is fast and virtually free in most Spartan 2, 2E, 3,
3E, 3L, 3A designs is multiplies. Rather than doing a divide by 4'd14,
consider doing a multiply by 17'h12492 which is 2^20/14. Your result
will be the product shifted by 20 bits.

If you need to divide by various values, the situation is different. If
the number of result bits you need is small, binary division algorithms
aren't too bad. A 16-bit/16-bit divide with 16-bit result times in
around 50 ns in a Spartan3E, -5 speed grade and takes up about 256 LUTs.

- John_H
Reply With Quote
  #3 (permalink)  
Old 07-30-2006, 06:36 PM
Nevo
Guest
 
Posts: n/a
Default Re: Divide-by-14; I really need mod 14

> I need to implement a divide-by-14 operation in a Xilinx Spartan FPGA. I
> thought it would be a simple matter of using the Verilog / operator, but
> XST throws an error since it only supports division by powers of 2.
>


Actually, after thinking more about this problem, I don't really need a
division. What I really need is to know whether "x mod 14" equals zero. (I
need to know if x is evenly divisible by 14.)

John_H, thank you for your input. I have to go run errands at the moment
but as soon as I get the chance I'll investigate your suggestion. At first
glance, it sure seems appropriate for me!

-Nevo


Reply With Quote
  #4 (permalink)  
Old 07-30-2006, 07:19 PM
John_H
Guest
 
Posts: n/a
Default Re: Divide-by-14; I really need mod 14

Nevo wrote:
>> I need to implement a divide-by-14 operation in a Xilinx Spartan FPGA. I
>> thought it would be a simple matter of using the Verilog / operator, but
>> XST throws an error since it only supports division by powers of 2.
>>

>
> Actually, after thinking more about this problem, I don't really need a
> division. What I really need is to know whether "x mod 14" equals zero. (I
> need to know if x is evenly divisible by 14.)
>
> John_H, thank you for your input. I have to go run errands at the moment
> but as soon as I get the chance I'll investigate your suggestion. At first
> glance, it sure seems appropriate for me!
>
> -Nevo


How large are your numbers?

You can tell if the number is divisible by 2 just by checking the LSbit.
For the remaining digits, you can see if the result is divisible by 7
by counting octal digits (3 bits each). You know how to tell if a
number is divisible by 9 from grade school, don't you? You add up all
the base-10 digits to see if the resulting sum is divisible by 9. If
your result is a large number that you can't easily tell if it's
divisible by 9, you add those digits together. You can keep doing this
until you either get 9 or something that's not nine. This works for all
base-x numbers where you're looking for whether the number is divisible
by x-1.

So, take your large number 3 bits at a time and add those 3-bit values
together in a small tree of adders. Keep doing this until you get a
3-bit result that's either 7 or it isn't. Just like with base-10
divide-by-9, you can figure out if a base-8 divide-by-7 produces a
remainder of 0.

With other numbers you might not be so lucky but with a divide-by-14,
arbitrarily large numbers are easy to deal with.

If you only have 14 bits to begin with, maybe a simple BlockRAM lookup
is quicker & simpler, the only complication being the INIT generation.

- John_H
Reply With Quote
  #5 (permalink)  
Old 07-30-2006, 08:46 PM
RobJ
Guest
 
Posts: n/a
Default Re: Divide-by-14; I really need mod 14

"John_H" <[email protected]> wrote in message
news:[email protected]
>
> How large are your numbers?
>
> You can tell if the number is divisible by 2 just by checking the LSbit.
> For the remaining digits, you can see if the result is divisible by 7 by
> counting octal digits (3 bits each). You know how to tell if a number is
> divisible by 9 from grade school, don't you? You add up all the base-10
> digits to see if the resulting sum is divisible by 9. If your result is a
> large number that you can't easily tell if it's divisible by 9, you add
> those digits together. You can keep doing this until you either get 9 or
> something that's not nine. This works for all base-x numbers where you're
> looking for whether the number is divisible by x-1.
>
> So, take your large number 3 bits at a time and add those 3-bit values
> together in a small tree of adders. Keep doing this until you get a 3-bit
> result that's either 7 or it isn't. Just like with base-10 divide-by-9,
> you can figure out if a base-8 divide-by-7 produces a remainder of 0.
>
> With other numbers you might not be so lucky but with a divide-by-14,
> arbitrarily large numbers are easy to deal with.
>
> If you only have 14 bits to begin with, maybe a simple BlockRAM lookup is
> quicker & simpler, the only complication being the INIT generation.
>
> - John_H


Very clever, John!


Reply With Quote
  #6 (permalink)  
Old 07-30-2006, 09:42 PM
Nevo
Guest
 
Posts: n/a
Default Re: Divide-by-14 in Xilinx Spartan FPGA's

"John_H" <[email protected]> wrote in message news:[email protected]
>
> Rather than doing a divide by 4'd14,
> consider doing a multiply by 17'h12492 which is 2^20/14. Your result
> will be the product shifted by 20 bits.
>


John,

I can't tell you how much I appreciate your assistance. Unfortunately, I'm doing the math and the light hasn't clicked on. I don't want to abuse your generosity but I do want to understand your lesson. I'd appreciate it if you could hang in there with me for another round.

Let's take the decimal value 9876538. (This is decimal 14 * 705467.) Or in hex, 0x96B43A. (I just chose some random number that's evenly divisible by 14.)

The following were all done in Windows calc.exe.

Using your method of multiplying by 2^20/14:

0x96B43A * 0x12492 = 0xAC3B84F114 = b1010110000111011100001001111000100010100

Actual division:

0x96B43A / 0x0E (decimal 14) = 0xAC3BB (decimal 705467) = 10101100001110111011

If I shift the result of my calculation right 20 bits, and line it up with the expected result, however, the results differ:

got: 10101100001110111000 01001111000100010100
expected: 10101100001110111011 (decimal 705467)

The two least significant bits differ from the expected result.

Now, in all honesty, this is probably 'good enough' for my application. However, I'm very leery of implementing this approach when I don't understand it. Is the off-by-3 result of the calculation expected? What's the maximum error in this calculation? I tried to do some quick simulation in Excel, but Excel balks at 20-digit binary numbers.

(After some more studying...)

Okay, I see that 2^2-/14 is not EXACTLY 0x12492. (Odd; calc.exe doesn't seem to do fractional numbers in hex...) I think that explains the rounding error. So then, why did you choose 2^20/14? Why not, say, 2^19/14? Or 2^29/14? Or something else? Does this technique get any more accurate if we keep appending bits to it?

In any case... thank you for your time! I really think this technique is going to be the solution to my problem! I really do appreciate your assistance.

-Nevo
Reply With Quote
  #7 (permalink)  
Old 07-31-2006, 02:56 PM
John_H
Guest
 
Posts: n/a
Default Re: Divide-by-14 in Xilinx Spartan FPGA's

response embedded:

Nevo wrote:
> "John_H" <[email protected] <mailto:[email protected]>> wrote in
> message news:[email protected]
> >
> > Rather than doing a divide by 4'd14,
> > consider doing a multiply by 17'h12492 which is 2^20/14. Your result
> > will be the product shifted by 20 bits.
> >

> John,
>
> I can't tell you how much I appreciate your assistance. Unfortunately,
> I'm doing the math and the light hasn't clicked on. I don't want to
> abuse your generosity but I do want to understand your lesson. I'd
> appreciate it if you could hang in there with me for another round.
>
> Let's take the decimal value 9876538. (This is decimal 14 * 705467.) Or
> in hex, 0x96B43A. (I just chose some random number that's
> evenly divisible by 14.)


This is why I asked "How large are your numbers?"
Multiplying by the reciprocal will have an error. I chose a 17-bit
number (2^20/14) to represent the fraction because Xilinx multipliers do
unsigned 17-bit multipliers with ease in one clock cycle.

> The following were all done in Windows calc.exe.
>
> Using your method of multiplying by 2^20/14:
>
> 0x96B43A * 0x12492 = 0xAC3B84F114 =
> b1010110000111011100001001111000100010100
>
> Actual division:
>
> 0x96B43A / 0x0E (decimal 14) = 0xAC3BB (decimal 705467) =
> 10101100001110111011
>
> If I shift the result of my calculation right 20 bits, and line it up
> with the expected result, however, the results differ:
>
> got: 10101100001110111000 01001111000100010100
> expected: 10101100001110111011 (decimal 705467)
>
> The two least significant bits differ from the expected result.
>
> Now, in all honesty, this is probably 'good enough' for my application.
> However, I'm very leery of implementing this approach when I don't
> understand it. Is the off-by-3 result of the calculation expected?
> What's the maximum error in this calculation? I tried to do some quick
> simulation in Excel, but Excel balks at 20-digit binary numbers.


The error in the multiplier will be +/-1/2 out of (2^20/14) which means
- for the example you gave - the error in the product will be +/-
(14*705467)/2 or - when shifted 20 bits - +/-9.419.

> (After some more studying...)
>
> Okay, I see that 2^2-/14 is not EXACTLY 0x12492. (Odd; calc.exe doesn't
> seem to do fractional numbers in hex...) I think that explains the
> rounding error. So then, why did you choose 2^20/14? Why not, say,
> 2^19/14? Or 2^29/14? Or something else? Does this technique get any more
> accurate if we keep appending bits to it?


The technique does get more accurate with more bits. you need to do
more than one multiply to get the more accurate number. You just need
to ask yourself what the largest number you expect would be and figure
out the error in your product based on the error in your reciprocal.

> In any case... thank you for your time! I really think this technique is
> going to be the solution to my problem! I really do appreciate your
> assistance.
>
> -Nevo



Since you just want the modulus and the numbers can be quite large, you
may just want to stick with the digit-adding I spoke of:

0x96B43A is even.
0x96B43A/2 is 0x4B5A1D
0x4B5A1D = 0o22655035 (0o for octal, might not be the "right" notation)

2+2+6+5+5+0+3+5 = decimal 28 = 0o34

Rather than adding 3 and 4 to get 7, a simpler check would be that
3==(~4). This shows the value 0x4B5A1D is divisible by 7. You don't
have to do another level of addition (because of more than 2 octal
digits) for numbers up to 24 bits. If you need more than 24 bits, you
just need to do the addition again in the octal digits of your first
sum-of-digits result.
Reply With Quote
Reply

Bookmarks

Thread Tools
Display Modes

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is On
Smilies are On
[IMG] code is On
HTML code is Off
Trackbacks are On
Pingbacks are On
Refbacks are On


Similar Threads
Thread Thread Starter Forum Replies Last Post
How to Divide a clock by 2 [email protected] Verilog 8 02-17-2006 05:10 AM
32/16 divider, ASIC(Designware) Vs Xilinx FPGA(Coregen) [email protected] Verilog 4 06-06-2005 04:55 PM
NEW ARM + XILINX MEGAGATE FPGA DEVELOPMENT PLATFORM Rick Verilog 0 11-22-2004 06:32 PM
NEW ARM + XILINX MEGAGATE FPGA DEVELOPMENT PLATFORM Rick Verilog 0 11-22-2004 06:31 PM
Xilinx FPGA routing question Heliboy Verilog 1 07-06-2004 09:44 AM


All times are GMT +1. The time now is 05:13 AM.


Powered by vBulletin® Version 3.8.0
Copyright ©2000 - 2019, Jelsoft Enterprises Ltd.
Search Engine Friendly URLs by vBSEO 3.2.0
Copyright 2008 @ FPGA Central. All rights reserved