What I Have Built So Far



Simple Oscilloscope

This is an implementation of a simple oscilloscope running on Cerebot-MX7cK board. The goal of the system is create an oscilloscope by utilizing the on-board analog to digital converter (ADC), the timer peripheral, rotary encoder, and the OLED output device. The user provides inputs such as sampling time and trigger through the rotary encoder and the on-board buttons. Watch this video if you are new to sampling theorem.



System Level Architecture

This section describes the higher level architecture of the system. The rotary encoder, OLED output, and the input from a function generator, are connected to port JA, JD, and JC respectively. The OLED provides the user with options to select the time division and trigger. The desired selections are made using the encoder. After all the inputs are selected, voltage values are sampled and displayed on the OLED.



Demo Time

The system is tested out using multiple functions at different frequencies. The minimum time division allowed is 0.2 msecs/div. The presented demo is shown working on the minimum time division with two functions: square and triangle. Both of them are at frequency 1KHz peek to peek.


Triangle Function

Square Function

Data Structures

AVL Tree

A recursive implementation of a self-balancing node-based AVL binary search tree.

   AVLTree.java    AVLTreeTest.java
   AVLTree.py    AVLTreeTest.py

HashTable

Implementation of a Hash Table using quadratic probing. Maps identifying keys to their associated values.

   HashTable.java    HashTableTest.java

Quadtree

A recursive implementation of a node based tree that partitions a two dimensional spatial domain by recursively dividing it into four quadrants.

   QuadTree.java    QuadTreeTest.java


SHA-256 Collision Search

SHA-256 is a hash function that takes an input string and converts it into a 256-bit digest.


For example, the SHA-256 digest of the word HOKIES as follows:


9c2683014faf646b2326de83f3e27546f4c51e5536a2e6373ac83dc4db7e4cb9


A hash function maps the set of all (ie. an infinite number of) possible input strings to a finite set of 2256 digests. So, there are an infinite amount of collisions. Why is it so hard to find a collision? Because 2256 is an astronomical number! The chance of hitting any particular chosen digest with an arbitrary input message is very small: about 2−256. In a collision search problem, we try to do exactly that: the digest output of SHA-256 is chosen, and next we try to find an input string that will map into the selected digest. Of course, an exact SHA-256 collision is extremely hard and improbable: the probability of finding one is 2−256!. So instead, we define an easier problem as follows:


Find an input string that yields a digest in which the leading n bits are zero, and the remaining (256-n) bits are don’t cares.


Therefore, the challenge is :

  • Pick a reference string, for example: XXXX Keep your head cool and your FPGA spinning!
  • Pick a target, for example 14 bits.
  • Replace the XXXX at the front of the string with a 32-bit counter value, starting from 0.
  • Compute the digest and if the first 14 bits of the digest are 0 then you have found a valid collision for the target.
  • Otherwise, if the number of leading zeroes does not meet the target, then increase the counter and repeat from step 3.
    •
    System Level Architecture

    The diagram on the right describes the system level architecture of the custom instruction that was implemented on the DE2-115 FPGA board. The role of the collision detector is simply to examine the output digest produced by the collision searcher and generate a found signal. The role of the collision searcher is to compute output digests on various different counts until a found signal is generated by the detector. For this implementation 42 collision searchers were used each counting [0-41, 42-83, 84-125 ...]. The entire design used about around 98% of the entire board (LE elements). The software provides the string, target "N", and a start signal. The hardware co-processor starts computing and generates a done signal upon completion. The software constantly polls the co-processor and finishes when the done signal is high. The counter value can be read anytime after the co-processor finishes.



    Joystick

    Android application that connects with the RN-XV WiFly Module. The WiFly chip hosts a TCP/IP server that listens to incoming connections. Instructions to setup the server can be found here. The android application connects with the chip by connecting to the broadcasting network and then providing the server IP and port. For more information about the project read this.

       Controller.java    MainActivity.java

    Connect Activity

    Control Activity


    DE2-115 FPGA

    Mini projects running on the DE2-115 FPGA board.


    Custom Instruction Example

    Simple example on setting up a custom instruction on NIOS II processor. It can be used to accelerate time critical software applications. Custom instructions allows the developer to reduce a complex sequence of standard instructions to a single instruction implemented in hardware. Here is the detailed documentation.

       main.c    xor_module.v