 # FPGA Central

## World's 1st FPGA Portal

 Verilog comp.lang.verilog newsgroup / usenet  Nevo Guest Posts: n/a 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

 John_H Guest Posts: n/a 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
 Nevo Guest Posts: n/a 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.
>

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

 John_H Guest Posts: n/a 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.
>>

>
> 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

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
 RobJ Guest Posts: n/a 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!

 Nevo Guest Posts: n/a 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
 John_H Guest Posts: n/a 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.)

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.

 Thread Tools Show Printable Version Email this Page Display Modes Linear Mode Switch to Hybrid Mode Switch to Threaded Mode 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 OffTrackbacks are On Pingbacks are On Refbacks are On Forum Rules Similar Threads Thread Thread Starter Forum Replies Last Post [email protected] Verilog 8 02-17-2006 06:10 AM [email protected] Verilog 4 06-06-2005 05:55 PM Rick Verilog 0 11-22-2004 07:32 PM Rick Verilog 0 11-22-2004 07:31 PM Heliboy Verilog 1 07-06-2004 10:44 AM

All times are GMT +1. The time now is 08:04 AM. Copyright 2008 @ FPGA Central. All rights reserved