Subversion Repositories dblclockfft

////////////////////////////////////////////////////////////////////////////////

//

// Filename:    rounding.cpp

//

// Project:     A General Purpose Pipelined FFT Implementation

//

// Purpose:     To create one of a series of modules to handle dropping bits

//              within the FFT implementation.

//

// Creator:     Dan Gisselquist, Ph.D.

//              Gisselquist Technology, LLC

//

////////////////////////////////////////////////////////////////////////////////

//

// Copyright (C) 2015-2018, Gisselquist Technology, LLC

//

// This program is free software (firmware): you can redistribute it and/or

// modify it under the terms of  the GNU General Public License as published

// by the Free Software Foundation, either version 3 of the License, or (at

// your option) any later version.

//

// This program is distributed in the hope that it will be useful, but WITHOUT

// ANY WARRANTY; without even the implied warranty of MERCHANTIBILITY or

// FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License

// for more details.

//

// You should have received a copy of the GNU General Public License along

// with this program.  (It's in the $(ROOT)/doc directory.  Run make with no

// target there if the PDF file isn't present.)  If not, see

// <http://www.gnu.org/licenses/> for a copy.

//

// License:     GPL, v3, as defined and found on www.gnu.org,

//              http://www.gnu.org/licenses/gpl.html

//

//

////////////////////////////////////////////////////////////////////////////////

//

//

#define _CRT_SECURE_NO_WARNINGS // ms vs 2012 doesn't like fopen

#include <stdio.h>

#include <stdlib.h>

#include <string.h>

#include <string>

#include <math.h>

#include <ctype.h>

#include <assert.h>

#include "legal.h"

#include "rounding.h"

#define SLASHLINE "////////////////////////////////////////////////////////////////////////////////\n"

void    build_truncator(const char *fname) {

        printf("TRUNCATING!\n");

        FILE    *fp = fopen(fname, "w");

        if (NULL == fp) {

                fprintf(stderr, "Could not open \'%s\' for writing\n", fname);

                perror("O/S Err was:");

                return;

        }

        fprintf(fp,

SLASHLINE

"//\n"

"// Filename:\ttruncate.v\n"

"//\n"

"// Project:\t%s\n"

"//\n"

"// Purpose:    Truncation is one of several options that can be used\n"

"//             internal to the various FFT stages to drop bits from one\n"

"//     stage to the next.  In general, it is the simplest method of dropping\n"

"//     bits, since it requires only a bit selection.\n"

"//\n"

"//     This form of rounding isn\'t really that great for FFT\'s, since it\n"

"//     tends to produce a DC bias in the result.  (Other less pronounced\n"

"//     biases may also exist.)\n"

"//\n"

"//     This particular version also registers the output with the clock, so\n"

"//     there will be a delay of one going through this module.  This will\n"

"//     keep it in line with the other forms of rounding that can be used.\n"

"//\n"

"//\n%s"

"//\n",

                prjname, creator);

        fprintf(fp, "%s", cpyleft);

        fprintf(fp, "//\n//\n`default_nettype\tnone\n//\n");

        fprintf(fp,

"module truncate(i_clk, i_ce, i_val, o_val);\n"

        "\tparameter\tIWID=16, OWID=8, SHIFT=0;\n"

        "\tinput\twire\t\t\t\ti_clk, i_ce;\n"

        "\tinput\twire\tsigned\t[(IWID-1):0]\ti_val;\n"

        "\toutput\treg\tsigned\t[(OWID-1):0]\to_val;\n"

"\n"

        "\talways @(posedge i_clk)\n"

                "\t\tif (i_ce)\n"

                "\t\t\to_val <= i_val[(IWID-1-SHIFT):(IWID-SHIFT-OWID)];\n"

"\n"

"endmodule\n");

}

void    build_roundhalfup(const char *fname) {

        FILE    *fp = fopen(fname, "w");

        if (NULL == fp) {

                fprintf(stderr, "Could not open \'%s\' for writing\n", fname);

                perror("O/S Err was:");

                return;

        }

        fprintf(fp,

SLASHLINE

"//\n"

"// Filename:\troundhalfup.v\n"

"//\n"

"// Project:\t%s\n"

"//\n"

"// Purpose:\tRounding half up is the way I was always taught to round in\n"

"//             school.  A one half value is added to the result, and then\n"

"//     the result is truncated.  When used in an FFT, this produces less\n"

"//     bias than the truncation method, although a bias still tends to\n"

"//     remain.\n"

"//\n"

"//\n%s"

"//\n",

                prjname, creator);

        fprintf(fp, "%s", cpyleft);

        fprintf(fp, "//\n//\n`default_nettype\tnone\n//\n");

        fprintf(fp,

"module roundhalfup(i_clk, i_ce, i_val, o_val);\n"

        "\tparameter\tIWID=16, OWID=8, SHIFT=0;\n"

        "\tinput\twire\t\t\t\ti_clk, i_ce;\n"

        "\tinput\twire\tsigned\t[(IWID-1):0]\ti_val;\n"

        "\toutput\treg\tsigned\t[(OWID-1):0]\to_val;\n"

"\n"

        "\t// Let's deal with two cases to be as general as we can be here\n"

        "\t//\n"

        "\t//   1. The desired output would lose no bits at all\n"

        "\t//   2. One or more bits would be dropped, so the rounding is simply\n"

        "\t//\t\ta matter of adding one to the bit about to be dropped,\n"

        "\t//\t\tmoving all halfway and above numbers up to the next\n"

        "\t//\t\tvalue.\n"

        "\tgenerate\n"

        "\tif (IWID-SHIFT == OWID)\n"

        "\tbegin // No truncation or rounding, output drops no bits\n"

"\n"

                "\t\talways @(posedge i_clk)\n"

                        "\t\t\tif (i_ce)\to_val <= i_val[(IWID-SHIFT-1):0];\n"

"\n"

        "\tend else // if (IWID-SHIFT-1 >= OWID)\n"

        "\tbegin // Output drops one bit, can only add one or ... not.\n"

                "\t\twire\t[(OWID-1):0] truncated_value, rounded_up;\n"

                "\t\twire\t\t\tlast_valid_bit, first_lost_bit;\n"

                "\t\tassign\ttruncated_value=i_val[(IWID-1-SHIFT):(IWID-SHIFT-OWID)];\n"

                "\t\tassign\trounded_up=truncated_value + {{(OWID-1){1\'b0}}, 1\'b1 };\n"

                "\t\tassign\tfirst_lost_bit = i_val[(IWID-SHIFT-OWID-1)];\n"

"\n"

                "\t\talways @(posedge i_clk)\n"

                "\t\t\tif (i_ce)\n"

                "\t\t\tbegin\n"

                        "\t\t\t\tif (!first_lost_bit) // Round down / truncate\n"

                        "\t\t\t\t\to_val <= truncated_value;\n"

                        "\t\t\t\telse\n"

                        "\t\t\t\t\to_val <= rounded_up; // even value\n"

                "\t\t\tend\n"

"\n"

        "\tend\n"

        "\tendgenerate\n"

"\n"

"endmodule\n");

}

void    build_roundfromzero(const char *fname) {

        FILE    *fp = fopen(fname, "w");

        if (NULL == fp) {

                fprintf(stderr, "Could not open \'%s\' for writing\n", fname);

                perror("O/S Err was:");

                return;

        }

        fprintf(fp,

SLASHLINE

"//\n"

"// Filename:\troundfromzero.v\n"

"//\n"

"// Project:    %s\n"

"//\n"

"// Purpose:    Truncation is one of several options that can be used\n"

"//             internal to the various FFT stages to drop bits from one\n"

"//     stage to the next.  In general, it is the simplest method of dropping\n"

"//     bits, since it requires only a bit selection.\n"

"//\n"

"//     This form of rounding isn\'t really that great for FFT\'s, since it\n"

"//     tends to produce a DC bias in the result.  (Other less pronounced\n"

"//     biases may also exist.)\n"

"//\n"

"//     This particular version also registers the output with the clock, so\n"

"//     clock, so there will be a delay of one going through this module.\n"

"//     This will keep it in line with the other forms of rounding that can\n"

"//     be used.\n"

"//\n"

"//\n%s"

"//\n",

                prjname, creator);

        fprintf(fp, "%s", cpyleft);

        fprintf(fp, "//\n//\n`default_nettype\tnone\n//\n");

        fprintf(fp,

"module roundfromzero(i_clk, i_ce, i_val, o_val);\n"

        "\tparameter\tIWID=16, OWID=8, SHIFT=0;\n"

        "\tinput\twire\t\t\t\ti_clk, i_ce;\n"

        "\tinput\twire\tsigned\t[(IWID-1):0]\ti_val;\n"

        "\toutput\treg\tsigned\t[(OWID-1):0]\to_val;\n"

"\n"

        "\t// Let's deal with three cases to be as general as we can be here\n"

        "\t//\n"

        "\t//\t1. The desired output would lose no bits at all\n"

        "\t//\t2. One bit would be dropped, so the rounding is simply\n"

        "\t//\t\tadjusting the value to be the closer to zero in\n"

        "\t//\t\tcases of being halfway between two.  If identically\n"

        "\t//\t\tequal to a number, we just leave it as is.\n"

        "\t//\t3. Two or more bits would be dropped.  In this case, we round\n"

        "\t//\t\tnormally unless we are rounding a value of exactly\n"

        "\t//\t\thalfway between the two.  In the halfway case, we\n"

        "\t//\t\tround away from zero.\n"

        "\tgenerate\n"

        "\tif (IWID == OWID) // In this case, the shift is irrelevant and\n"

        "\tbegin // cannot be applied.  No truncation or rounding takes\n"

        "\t// effect here.\n"

"\n"

                "\t\talways @(posedge i_clk)\n"

                        "\t\t\tif (i_ce)\to_val <= i_val[(IWID-1):0];\n"

"\n"

        "\tend else if (IWID-SHIFT == OWID)\n"

        "\tbegin // No truncation or rounding, output drops no bits\n"

"\n"

                "\t\talways @(posedge i_clk)\n"

                        "\t\t\tif (i_ce)\to_val <= i_val[(IWID-SHIFT-1):0];\n"

"\n"

        "\tend else if (IWID-SHIFT-1 == OWID)\n"

        "\tbegin // Output drops one bit, can only add one or ... not.\n"

        "\t\twire\t[(OWID-1):0]\ttruncated_value, rounded_up;\n"

        "\t\twire\t\t\tsign_bit, first_lost_bit;\n"

        "\t\tassign\ttruncated_value=i_val[(IWID-1-SHIFT):(IWID-SHIFT-OWID)];\n"

        "\t\tassign\trounded_up=truncated_value + {{(OWID-1){1\'b0}}, 1\'b1 };\n"

        "\t\tassign\tfirst_lost_bit = i_val[0];\n"

        "\t\tassign\tsign_bit = i_val[(IWID-1)];\n"

"\n"

        "\t\talways @(posedge i_clk)\n"

                "\t\t\tif (i_ce)\n"

                "\t\t\tbegin\n"

                        "\t\t\t\tif (!first_lost_bit) // Round down / truncate\n"

                                "\t\t\t\t\to_val <= truncated_value;\n"

                        "\t\t\t\telse if (sign_bit)\n"

                                "\t\t\t\t\to_val <= truncated_value;\n"

                        "\t\t\t\telse\n"

                                "\t\t\t\t\to_val <= rounded_up;\n"

                "\t\t\tend\n"

"\n"

        "\tend else // If there's more than one bit we are dropping\n"

        "\tbegin\n"

                "\t\twire\t[(OWID-1):0]\ttruncated_value, rounded_up;\n"

                "\t\twire\t\t\tsign_bit, first_lost_bit;\n"

                "\t\tassign\ttruncated_value=i_val[(IWID-1-SHIFT):(IWID-SHIFT-OWID)];\n"

                "\t\tassign\trounded_up=truncated_value + {{(OWID-1){1\'b0}}, 1\'b1 };\n"

                "\t\tassign\tfirst_lost_bit = i_val[(IWID-SHIFT-OWID-1)];\n"

                "\t\tassign\tsign_bit = i_val[(IWID-1)];\n"

"\n"

                "\t\twire\t[(IWID-SHIFT-OWID-2):0]\tother_lost_bits;\n"

                "\t\tassign\tother_lost_bits = i_val[(IWID-SHIFT-OWID-2):0];\n"

"\n"

                "\t\talways @(posedge i_clk)\n"

                        "\t\t\tif (i_ce)\n"

                        "\t\t\tbegin\n"

                        "\t\t\t\tif (!first_lost_bit) // Round down / truncate\n"

                                "\t\t\t\t\to_val <= truncated_value;\n"

                        "\t\t\t\telse if (|other_lost_bits) // Round up to\n"

                                "\t\t\t\t\to_val <= rounded_up; // closest value\n"

                        "\t\t\t\telse if (sign_bit)\n"

                                "\t\t\t\t\to_val <= truncated_value;\n"

                        "\t\t\t\telse\n"

                                "\t\t\t\t\to_val <= rounded_up;\n"

                        "\t\t\tend\n"

        "\tend\n"

        "\tendgenerate\n"

"\n"

"endmodule\n");

}

void    build_convround(const char *fname) {

        FILE    *fp = fopen(fname, "w");

        if (NULL == fp) {

                fprintf(stderr, "Could not open \'%s\' for writing\n", fname);

                perror("O/S Err was:");

                return;

        }

        fprintf(fp,

SLASHLINE

"//\n"

"// Filename:   convround.v\n"

"//\n"

"// Project:    %s\n"

"//\n"

"// Purpose:    A convergent rounding routine, also known as banker\'s\n"

"//             rounding, Dutch rounding, Gaussian rounding, unbiased\n"

"//     rounding, or ... more, at least according to Wikipedia.\n"

"//\n"

"//     This form of rounding works by rounding, when the direction is in\n"

"//     question, towards the nearest even value.\n"

"//\n"

"//\n%s"

"//\n",

                prjname, creator);

        fprintf(fp, "%s", cpyleft);

        fprintf(fp, "//\n//\n`default_nettype\tnone\n//\n");

        fprintf(fp,

"module convround(i_clk, i_ce, i_val, o_val);\n"

"\tparameter\tIWID=16, OWID=8, SHIFT=0;\n"

"\tinput\twire\t\t\t\ti_clk, i_ce;\n"

"\tinput\twire\tsigned\t[(IWID-1):0]\ti_val;\n"

"\toutput\treg\tsigned\t[(OWID-1):0]\to_val;\n"

"\n"

"\t// Let's deal with three cases to be as general as we can be here\n"

"\t//\n"

"\t//\t1. The desired output would lose no bits at all\n"

"\t//\t2. One bit would be dropped, so the rounding is simply\n"

"\t//\t\tadjusting the value to be the nearest even number in\n"

"\t//\t\tcases of being halfway between two.  If identically\n"

"\t//\t\tequal to a number, we just leave it as is.\n"

"\t//\t3. Two or more bits would be dropped.  In this case, we round\n"

"\t//\t\tnormally unless we are rounding a value of exactly\n"

"\t//\t\thalfway between the two.  In the halfway case we round\n"

"\t//\t\tto the nearest even number.\n"

"\tgenerate\n"

// What if IWID < OWID?  We should expand here ... somehow

        "\tif (IWID == OWID) // In this case, the shift is irrelevant and\n"

        "\tbegin // cannot be applied.  No truncation or rounding takes\n"

        "\t// effect here.\n"

"\n"

                "\t\talways @(posedge i_clk)\n"

                        "\t\t\tif (i_ce)\to_val <= i_val[(IWID-1):0];\n"

"\n"

// What if IWID-SHIFT < OWID?  Shouldn't we also shift here as well?

"\tend else if (IWID-SHIFT == OWID)\n"

"\tbegin // No truncation or rounding, output drops no bits\n"

"\n"

"\t\talways @(posedge i_clk)\n"

"\t\t\tif (i_ce)\to_val <= i_val[(IWID-SHIFT-1):0];\n"

"\n"

"\tend else if (IWID-SHIFT-1 == OWID)\n"

// Is there any way to limit the number of bits that are examined here, for the

// purpose of simplifying/reducing logic?  I mean, if we go from 32 to 16 bits,

// must we check all 15 bits for equality to zero?

"\tbegin // Output drops one bit, can only add one or ... not.\n"

"\t\twire\t[(OWID-1):0] truncated_value, rounded_up;\n"

"\t\twire\t\t\tlast_valid_bit, first_lost_bit;\n"

"\t\tassign\ttruncated_value=i_val[(IWID-1-SHIFT):(IWID-SHIFT-OWID)];\n"

"\t\tassign\trounded_up=truncated_value + {{(OWID-1){1\'b0}}, 1\'b1 };\n"

"\t\tassign\tlast_valid_bit = truncated_value[0];\n"

"\t\tassign\tfirst_lost_bit = i_val[0];\n"

"\n"

"\t\talways @(posedge i_clk)\n"

"\t\t\tif (i_ce)\n"

"\t\t\tbegin\n"

"\t\t\t\tif (!first_lost_bit) // Round down / truncate\n"

"\t\t\t\t\to_val <= truncated_value;\n"

"\t\t\t\telse if (last_valid_bit)// Round up to nearest\n"

"\t\t\t\t\to_val <= rounded_up; // even value\n"

"\t\t\t\telse // else round down to the nearest\n"

"\t\t\t\t\to_val <= truncated_value; // even value\n"

"\t\t\tend\n"

"\n"

"\tend else // If there's more than one bit we are dropping\n"

"\tbegin\n"

"\t\twire\t[(OWID-1):0] truncated_value, rounded_up;\n"

"\t\twire\t\t\tlast_valid_bit, first_lost_bit;\n"

"\t\tassign\ttruncated_value=i_val[(IWID-1-SHIFT):(IWID-SHIFT-OWID)];\n"

"\t\tassign\trounded_up=truncated_value + {{(OWID-1){1\'b0}}, 1\'b1 };\n"

"\t\tassign\tlast_valid_bit = truncated_value[0];\n"

"\t\tassign\tfirst_lost_bit = i_val[(IWID-SHIFT-OWID-1)];\n"

"\n"

"\t\twire\t[(IWID-SHIFT-OWID-2):0]\tother_lost_bits;\n"

"\t\tassign\tother_lost_bits = i_val[(IWID-SHIFT-OWID-2):0];\n"

"\n"

"\t\talways @(posedge i_clk)\n"

"\t\t\tif (i_ce)\n"

"\t\t\tbegin\n"

"\t\t\t\tif (!first_lost_bit) // Round down / truncate\n"

"\t\t\t\t\to_val <= truncated_value;\n"

"\t\t\t\telse if (|other_lost_bits) // Round up to\n"

"\t\t\t\t\to_val <= rounded_up; // closest value\n"

"\t\t\t\telse if (last_valid_bit) // Round up to\n"

"\t\t\t\t\to_val <= rounded_up; // nearest even\n"

"\t\t\t\telse   // else round down to nearest even\n"

"\t\t\t\t\to_val <= truncated_value;\n"

"\t\t\tend\n"

"\tend\n"

"\tendgenerate\n"

"\n"

"endmodule\n");

}