Let's light things up ( with an FPGA )!
Finally got around to learn the tools and implement the project on to the DE0 Nano. Check it out!
The Idea: Restate and test MILP model for determining the parameters of the clap algorithm.
With the help of GNU Glpk and PyGlpk, the mixed integer linear programming (MILP) model that was described in the last several logs has finally been implemented! And, in doing so, several issues with the original model were discovered and fixed. The prior logs on the system model may even be removed in the future. However, in attempt to reduce the amount of time spent writing these logs, many of those details are glossed over here; writing these logs take a significant amount of time, unfortunately. Instead, much of the model is simply restated in this log. In addition to the restating the model, this log includes a brief example demonstrating the model works as intended. The example and the respective Python code can be found in the project's repository!
And, like the last log, the equivalent inline latex is used to refer to the symbols presented in the images. Hope this isn't too confusing!
The Theory: Model description.
The signal $x_n$ represents the sampled audio.
The clap that needs identification is defined as a sudden spike in the energy of $x_n$, where each energy $e_m$ is defined over a small interval.
A spike in energy can be regarded as a sudden increase in energy over a period, and then a sudden decrease over another period of time. The sudden changes are signified by either the energy $e_m$ exceeding the threshold $e_H$ or falling under the threshold $e_L$, for their respective durations.
$\sigma_{H,k,m}$ and $\sigma_{L,k,m}$ are both indicators that represent the aforementioned durations. Specifically, $\sigma_{H,k,m}$ represents the duration for which $e_m \ge e_H$ is true for each clap $k$.
The three unknowns are $\Delta m_k$, $\Delta m_H$, and $\Delta m_{H,k}$. $\Delta m_k$ represents the amount of time---measured in samples $m$---between each clap $k$. $\Delta m_H$ is the minimum amount of time $e_m \ge e_H$ needs to be true for clap $k$. $\Delta m_{H,k}$ allows $e_m \ge e_H$ for clap $k$ to be true longer than $\Delta m_H$. And, since it's probably not very clear, assume $m_{L,UB,-1} = 0$.
Next, $\sigma_{L,k,m}$ represents the duration for which $e_m \le e_L$ is true for each clap $k$.
The unknowns are $\Delta m_{L,k}$ and $\Delta m_L$. $\Delta m_{L,k}$ for clap $k$ allows $e_m$ to fall in between $e_H$ and $e_L$ before $e_m \le e_L$ needs to be true. Similar to $\Delta m_H$, $\Delta m_L$ is the minimum amount of time $e_m\le e_L$ needs to be true.
In order to progress with this explanation, consider the following definitions.
Assume the domain of variables that begin with $\Delta$ are $M$. With these definitions, the indicators $\sigma_{H,k,m}$ and $\sigma_{L,k,m}$ are reduced to a single indicator.
To further simplify, $\sigma_{t,k,m}$ is true if and only if the conditions $0 \le m - m_{t,LB,k}$ and $0 \le m_{t,UB,k} - m$ are true. Taking advantage of the if-then constraint, the aforementioned conditions are represented with the following.
The conditions $\beta_{t,LB,k,m}$ and $\beta_{t,UB,k,m}$ are further simplified with a logical-AND operation. The result is $\sigma_{t,k,m}$.
Finally, the objective is to find the values of the unknowns that maximize the difference between $e_H$ and $e_L$. The variables that need solving are the following.
The Implementation: PyGlpk and GNU Glpk
For those who have seen the logs on the embedded systems project, GNU Glpk has already been used in other projects as a way to solve LP models, albeit the application was for flow-network problems. Instead of the LEMON Glpk interface as described in the embedded system logs, the presented MILP model is solved with Glpk via the PyGlpk interface. As stated earlier, the source code of the first completed version can be found in the project's repository. There will be one more version of the source code since the current model does not take into consideration multiple sets of audio signals ( and the source code is somewhat messy, admittedly ).
Let's start with...
Read more »SO, just to extend the brief introduction from the project's home page, this project can be described as an introductory experience for both me and @Neale Estrella. In his case, he's new to the world of RTL design for FPGAs and wants to learn Verilog for behavioral synthesis. For me, my entire FPGA-related experience is with Xilinx FPGAs and for the first time, I want to do a project with an Altera FPGA!
In later projects, I hope to check out Altera's OpenCL support and their Nios II softcore processor! But, similar to how I initially started out, we plan to implement this entire project in Verilog. Once we have the design running over the DE0 Nano, I hope to add circuitry to allow the FPGA toggle an actual lap!
( The lap I want to toggle!!!... Just really wanted to throw in a picture somewhere. )
At this point, we already have a few aspects of the project figured out. As briefly mentioned, we both bought the Terasic DE0 Nano development board. The Nano contains the Altera FPGA, however the board was mainly selected for it's decent cost, peripheral components, and it appears to be fairly popular among other hobbyists who work with FPGAs. As for the development environment, I've started to learn Quartus Prime 16 Lite, but I believe Neale needed to get Quartus II Web instead since he uses a 32-bit system. Pretty sure both are nearly identical! And, of course, we are in the process of learning ModelSim Altera for simulation!
( Looks pretty sweet!!!... Can't wait to actually turn it on! )
As of now, the entire RTL design is, in a way, "finished". In the repository, you can see all the modules. However, only the GetSignal module was fully tested, simulation and deployment. As for the others, my hope is to have a few of them replaced with Neale's implementations.
Finally, in the next several logs, I will explain the theory of operation!