Divide-by-14 in Xilinx Spartan FPGA's

[Nevo]

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]

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]

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

 

[John_H]

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

 

[RobJ]

"John_H" <johnhandwork@mail.com> wrote in message
news:5L6zg.1336$ee1.1015@trnddc06...

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]

"John_H" <johnhandwork@mail.com> wrote in message news:mc5zg.6344$c11.1445@trnddc08...

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]

response embedded:

Nevo wrote:

"John_H" <johnhandwork@mail.com <mailto:johnhandwork@mail.com>> wrote in
message news:mc5zg.6344$c11.1445@trnddc08...

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.