Starting to build an FFT core generator for FPGAs

C++ codeI have begun working on a new project and would like to take a moment and tell you about it, if you don’t mind. I have been working on it for about a month now, and have been continuing to become more excited about it as I have started to see some of the foundation pieces fall into place.


My senior project, to finish my Computer Engineering degree at Oregon Institute of Technology was supposed to be an audio spectrum visualizer using an FFT processor in an FPGA. If you don’t know what an audio spectrum analyzer is, check out this video below.

Anyway, it turned out that an FFT is a major pain to build from scratch, especially for a person like me who has no clue what he’s doing when it comes to digital signal processing (DSP) techniques. I learned a great deal by reading many technical papers and articles on the subject, but could not get anything to work. I even tried using Altera’s (as was it’s name at the time) proprietary FFT IP core but the user guide was not built for a beginner and neither myself nor my professors could get the core to function properly.

Long story short, I altered my senior project to simply display audio volume in a fancy way and proceeded to market the product as a very, uh, expandable platform that could easily implement features like frequency analysis and whatnot.

Ever since that time, this whole idea of an FFT processing core in an FPGA has been haunting me, so now that I have some more time this summer, I have set out with a goal of building an application which generates a completely customizable FFT core in the form of SystemVerilog compliant HDL modules, for use in Altera or Xilinx FPGAs and CPLDs.

Design concept

This project ultimately would allow a developer to provide the width and length of the FFT they need for their system and then the program would generate all the SystemVerilog modules required for that system and the developer would then only need to interface his design with the input and output of the top-level FFT module and he would be ready to roll in a matter of minutes.

I have been designing this project in the ever-so-popular object-oriented C++ and have been compiling with “mingw” in Code::Blocks.

I know that both the Altera and Xilinx FFT IP core configuration wizards presented the user with some nice extra features like being able to select presets which modify the design to consume more or less memory or have a higher or lower throughput, for example.

This design, for the time being, will not have such features. I think it’s better to focus on one FFT architecture and generate a nice pipelined FFT core that is simple to configure and very easy to integrate into a synthesize design. Once I have one FFT architecture working well, then I might consider expanding the idea to generate different kinds of FFT architectures.

Multipliers are a very important part of calculating an FFT. Most FPGA I have encountered are manufactured with physical multiplier hardware on the silicon. This conserves the Logic Elements (LEs) or Logic Cells (LCs) to be used for other things in the design. It also means that (ideally) highly-optimized hardware multipliers are readily available to the developer. However, from the little I have seen of the FPGA market, it seems like access to these multipliers is not allowed unless your design uses a piece of the vendor’s proprietary code. In Altera’s world, this code is called a macrofunction. I’m not sure what it’s called in the Xilinx world just yet.

With all of that in mind, this project will probably use custom multiplier modules for the time being, simply because it simplifies the cross-vendor compatibility a great deal. While I haven’t gotten quite that far yet, I will probably implement it as a Booth multiplier, but I am still doing a little bit more research before a really settle on a multiplier architecture.

Current progress

So far, I have implemented and tested code to generate a SystemVerilog compatible ROM module and then attached that code on to new code which calculates twiddle factors, based on the length and width of the desired FFT. Reworded, basically right now I can generate both the real and imaginary twiddle factor ROMs required to process an FFT of (almost) any length and bit width.The output I’ve been getting matches the twiddle values which George Slade calculated and published in his paper/tutorial on this subject, so that has been promising.


The simple future plan, of course, is to finish the project. But what does that mean? Well, from what I know based on what I have read online, I will need to expand my C++ program to generate the following SystemVerilog modules:

  • 2-port RAM module
  • Booth multiplier module
  • Address generator module
  • Butterfly module
  • Top-level module (which wires most of the sub-modules together correctly)

So we’ll see how this goes! Again, I’m pretty excited about this project and really hope I can build a usable FFT core by the end of this. If not, it has already been a great review of some C++ programming skills I haven’t used for over a year, so that’s always a good thing.

I am keeping this project hosted up in my (currently private) Bitbucket repository. If I do make the repository public, please go check it out over here:

If you made it this far, thank you so much for reading this! I really appreciate it! Please ask any questions or leave any comments you might have below!

Rate this Post/Page

Open-source DIY Greenhouse Project

In a college class this last year, a group of us were assigned to design a system that would collect and graph environmental data from our campus greenhouse. We would take this data, graph it, and display those graphs on a public website. We’d also use current data to control the greenhouse (i.e. watering, heating, cooling…). Hopefully this information helps you if you are wanting to start your own DIY project and automate your greenhouse.

We decided to use an Arduino UNO, a PICAXE-14M2, and a desktop computer running Windows Vista. The Arduino functioned as the main interface and brain. We dedicated the PICAXE to simply reading sensors and sending that data in a continuous stream to the Arduino via a serial communication protocol.

The Arduino would format and send data to be logged to the PC, which runs MegunoLink. The Arduino would also decide, based on environmental conditions, if the heater/cooler/water should be turned on. Future groups working on the project would have to decided whether the Arduino would do this by sending a command to a dedicated microcontroller (reverse of what we did with the PICAXE being dedicated to sensors) or by directly controlling equipment in the greenhouse.

So, in essence, for this project, we figured out how to set up data logging and automation of the greenhouse environment using cheap materials and open source equipment.

In our report, we provide example code for both microcontrollers and discuss difficulties we ran into along the way. You can read this report by clicking on the PDF link below.

Final Report – COCC Greenhouse IT Group.pdf

IT Budget/Component Pricing.pdf



Open-source DIY Greenhouse Project
3(60%) 1 votes

Frequency Harmonic Calculator in C++

I just came up with a little Frequency Harmonic Calculator in C++. Calculating harmonics isn’t hard, but if your doing a bunch of calculations, this might come in handy. To calculate a harmonic, simply take the fundamental frequency (F) and multiply it by an integer value (i.e. 3). So, for example, if F = 520 KHz, then the 3rd harmonic would be (Fx3) = (520×3) = 1560 KHz.

I also wrote a section of this program to calculate frequencies that have a harmonic of the frequency you enter. So if you enter 520, it will let you know that 260 KHz has a harmonic of 520 KHz. I needed something like this for a project I’m working on, so I decided to share what I came up with.

There is something funny/nice that occurs. If you enter both the value (i.e. 520) and the measurement (i.e. KHz) when it asks for the fundamental frequency, it will somehow write the frequency to the ‘freq’ variable and the measurement to the ‘unit’ variable and skip the step where I ask for the unit of measurement. All the calculations are correct and everything. I might know why this is, but I’m not sure enough to spit it out. Anyway, kinda cool.

I also put up this code here:

#include <iostream>
#include <stdio .h>
#include <string>

using namespace std;

class calculator

int highArray[15];
int lowArray[15];
int freq;

void harmonics(int);
void lowFreq(int);


void calculator::harmonics(int freq)

for (int i; i < = 15; i=i+1)
highArray[i] = freq*(i+1);


void calculator::lowFreq(int freq)
for (int i=0; i<=15; i=i+1)
lowArray[i] = freq/(i+1);

int main()
int freq;
string unit;

cout << "What is the fundamental frequency?\n\n";
cin >> freq;
cout < < "\nWhat unit of measure are you useing? (Hz, KHz, MHz,... )\n\n";
cin >> unit;
cout < < "\n\n";

calculator related_freqs;


cout << "The harmonics of " << freq << " ";
cout << unit << " are...\n\n";

for (int i=0; i<=15; i=i+1)
cout << "Harmonic #"<< (i+1) << " " << related_freqs.highArray[i];
cout << " " << unit << "\n";

cout << "\n\n\nNow I'll calculate frequencies that have a harmonic of " << freq;
cout << " " << unit << "\n\n";


for (int i=0; i<=15; i=i+1)
cout << "Frequency #"<< (i+1) << " " << related_freqs.lowArray[i];
cout << " " << unit << "\n";

cout << "\n\n\nPress any key and hit ENTER to quit.\n";
cin >> freq;
// getchar();    // For some reason or another, this command has never worked for me. That's why I wrote the above line so that the user can actually read the data output. It's not as nice, but it works.
return (0);

Rate this Post/Page

Age Calculator in C++

This is my first program in C++ that truly uses object oriented programming capabilities. Some of the code is a little redundant. I wrote it this way to help me understand what is really going on when your passing data around.

I thought I’d throw the code up here for anyone who would like to use it. Here you go.

If you find an error/bug, please leave me a comment!

Age Calculator.txt

#include <iostream>
#include <stdio .h>
#include <time .h>
#include <string>

using namespace std;

class date
int day;
int month;
int year;
int daysold;
int monthsold;
int yearsold;

//I defined two methods. The "birth" method and "age" method both accept three integer variables.
void birth(int, int, int);
void age(int, int, int);

void date::birth(int b_day, int b_month, int b_year)
// This mearly takes the birthday (DD MM YYYY) entered and writes it to the class's variables for the other method to use.

day = b_day;
month = b_month;
year = b_year;

//cout < < day << "/" << month << "/" << year << "\n";           // This was for me to test what data is really reaching those three variables.


void date::age(int c_day, int c_month, int c_year)
//This method actually does something useful! Useing both the current date and the birthdate, it will calculate "monthsold", "daysold", and "yearsold."


monthsold = (((c_year*12) + c_month) - ((year*12) + month));

daysold = (monthsold*30) + day;

yearsold = monthsold/12;

int main()
// -----------------   VARIABLES   -------------------
int b_day;
int b_month;
int b_year;
int c_day;
int c_month;
int c_year;

//------------------ GET SYS TIME  -------------------

time_t tim;  //create variable of time_t
time(&tim); //pass variable tim to time function
cout << "Program initiated on " << ctime(&tim) << "\n\n"; // this translates what was returned from time() into a readable format

time (&tim);
struct tm * ptm= localtime(&tim);
c_day = ptm->tm_mday;
c_month = (ptm->tm_mon)+1;
c_year = ptm->tm_year + 1900;

//------------------ START ASKING QUESTIONS -------------------

cout < < "In what year was the subject born? (i.e. 1982)\n";
cin >> b_year;
cout < < "\nIn what month was the subject born? (i.e. 09)\n";
cin >> b_month;
cout < < "\nOn what day was the subject born? (i.e. 27)\n";
cin >> b_day;
cout < < "\n";

//------------------ VERIFY INFORMATION ------------------
//Define an object from the "date" class. I'll call my object "human."
date human;

// Send the collected data to the "birth" method
human.birth(b_day, b_month, b_year);

//Put a confirmation message up.
cout << "You said that the subject was born on " << human.month << "/" << << "/" << human.year << " if I'm not mistaken.\n";

//Send current date to AGE method to run calculations
human.age(c_day, c_month, c_year);

//------------------ DISPLAY CALCULATIONS --------------------

cout << "\nOk. In case you were wondering, the subject is somewhere around\n\n";
cout << human.yearsold << " years \n\n";
cout << "...or...\n\n";
cout << human.monthsold << " months \n\n";
cout << "...or...\n\n";
cout << "aprox. " << human.daysold << " days old\n\n\n";
cout << " - - - | - - -\n\n";
cout << "Sorry, that's my best extimate.\n";

//---------------------- QUIT MAIN PROGRAM ----------------------cout << "\n Press any key and hit ENETER to close." << endl;

cin >> c_day;
//int getchar();    // For some reason or another, this command has never worked for me. That's why I wrote the above line so that the user can actually read the data output. It's not as nice, but it works.
return (0);


Rate this Post/Page