projf / projf-explore

Project F brings FPGAs to life with exciting open-source designs you can build on.
https://projectf.io
MIT License
586 stars 53 forks source link

Some small glitches in fixed point division. #164

Closed Democrito closed 1 year ago

Democrito commented 1 year ago

Hi @WillGreen,

I just wanted you to know that the fixed point division algorithm sometimes throws a little error depending on the numbers used. I've used an old version that you had posted on your website, and I've also tried fixed-point division with Gaussian rounding. I'll give you some examples in case you want to check it out. I have used a fixed point Q16.16

1/5 = 0.1999 should be "0.2" (this is not significant) 32767.9999/7.561 = 4333.8156 should be "4333.8182" (last two decimal places miss significantly) 32766/7.561=4333.5511 should be "4333.5537" (last two decimal places miss significantly) 1/0.1=9.9995 should be "10" 1/0.01=99.9039 should be "100" 1/0.001=992.9848 should be "1000" 1/0.0001=9362.4285 should be "10000"

when the denominator is "0.something" there are problems.

The vast majority of the time it works perfectly or with very acceptable results, especially if you only use integers.

On the other hand, if you could divide by "0.something" your algorithm could serve as a multiplier (inverse operation trick).

Greeting.

WillGreen commented 1 year ago

Thank for your bug report. 🙏 I'll look into this as soon as I can.

WillGreen commented 1 year ago

I can confirm a test failure 1/0.2, but I believe this is an issue with the test model rather than the division module. I suspect this will be the case for the other failures you're seeing. I will run additional higher precision tests once I've looked at the test model for this case.

   505.02ns INFO     cocotb.regression                  running min_5 (23/33)
                                                          Test 1/0.2
   527.02ns INFO     cocotb.div                         dut a:     000010000
   527.02ns INFO     cocotb.div                         dut b:     000000011
   527.02ns INFO     cocotb.div                         dut val:   001010101
   527.02ns INFO     cocotb.div                                    5.3125
   527.02ns INFO     cocotb.div                         model val: 000101.0000
   527.02ns INFO     cocotb.div                                    5
   527.02ns INFO     cocotb.regression                  min_5 failed

0.2 becomes 00000.0011, which is 0.1875 in decimal. 1/0.1875 = 5.3125 at this precision. In this case the test model is wrong. I'm investigating.

WillGreen commented 1 year ago

I've fixed the test model so it correctly converts values into fixed-point prior to division. I have not changed the Verilog division modules.

My example test now passes:

   505.02ns INFO     cocotb.regression                  running min_5 (23/33)
                                                          Test 1/0.2
   527.02ns INFO     cocotb.div                         dut a:     000010000
   527.02ns INFO     cocotb.div                         dut b:     000000011
   527.02ns INFO     cocotb.div                         dut val:   001010101
   527.02ns INFO     cocotb.div                                    5.3125
   527.02ns INFO     cocotb.div                         model val: 000101.0101
   527.02ns INFO     cocotb.div                                    5.3125
   528.02ns INFO     cocotb.regression                  min_5 passed

I believe the problem with your examples is that your inputs can't be precisely represented in binary. For example, if I run 1/0.01 with Q16.16 I get:

                                                          Test 1/0.01
  1332.02ns INFO     cocotb.div                         dut a:     00000000000000010000000000000000
  1332.02ns INFO     cocotb.div                         dut b:     00000000000000000000001010001111
  1332.02ns INFO     cocotb.div                         dut val:   00000000011001000000111000010010
  1332.02ns INFO     cocotb.div                                    100.054962158203125
  1332.02ns INFO     cocotb.div                         model val: 00000000001100100.0000111000010010
  1332.02ns INFO     cocotb.div                                    100.054962158203125

Even with 16 fractional bits, 0.01 comes out as 0.0099945068 (0.0000001010001111 in binary).

I am happy to take a look at your Verilog if you want to share an example here.

I hope that helps. :)

Democrito commented 1 year ago

Hi Will Green,

I use a program called Icestudio. It is a graphical program for designing circuits. It allows you to create very simple and also very complex circuits. You can create specific modules and modules that contain other modules. Of course, you can create a module in verilog, in fact, the basis of everything is verilog.

In case you're curious, here's a link: https://icestudio.io/#lk-download

On that page there is a tab on the right that says "Download", in blue color, from there you can download it. Then there is another tab called "Install", which explains the steps to follow during the installation, but to see only circuits you don't need to follow the steps, it skips the "toolchain" installation.

Once installed, the circuit I use as an example is this: https://github.com/Democrito/repositorios/blob/master/Maths/div_fix_point/Example_Serial_Div_Fix_Point_Q16-16.ice

Right click on "Raw" and choose "Save Link Content" and it will download the example I'm using. Once downloaded, double click and Icestudio will open it.

The example consists of using a serial terminal, where two integer or fixed point values are entered, and its algorithm solves the division, finally, another module converts the fixed point format to ASCII and sends it to the serial terminal as a response.

I was looking to see if I could adjust the input and output of the ASCII converters to fixed point and vice versa, but at the moment I can't get the rounding to be correct in the special cases that we discussed. I will continue to insist.

Thank you very much for your reply.

Greetings.