YODA TOPICS!

Introduction

Procedure to Select a Topic

YODA Project Topics

The procedure for selecting a project is listed at the end of this page.

Note that each topic can be done by two separate teams (i.e., a TeamA and a TeamB). If there are already two teams working on a topic, please contact the lecture to motivate why a third team should be assigned to the same topic.

Project supervisors will be assigned to each group after the teams have been decided.

 List of Topics:   (click on an item to jump to the description)

  SF - Smoothing Filter P01

  TLUA – Table look-up accelerator P02

  IF – interpolation filter P03

` PRNG – Parallel Random Number Generator P04

` DM - Delta modulator P05

  ASG - Arithmetic series generator P06

  SALG – Selection Address List Generator P07

  FSG - Function Samples Generator P08

  BSS – Bit Sequence Sniffer P09

  BCDC - Binary Coded Decimal Convertor P10

  NCSM - Nonlinear Check Sum Module P11

  CRCC - Cyclic Redundancy Check Calculator P12

  MMA - Matrix Multiplier Accelerator P13

  IMA - Image Masking Accelerator P14

  PSA - Pattern Seek Accelerator P15

  DE – Data Encryption Accelerator P16

  VADER – Versatile Accelerated Digital Encryption Recovery P17

  PADAWAN - Parallel Accelerator for Digitising Audio with Attenuation of Noise P18

 If you don't see any topic that interests you, consider taking a look at the numerical recipes online book (url: http://www.nrbook.com/nr3/) or books in the library.

 Project briefs follow...

 SF - Smoothing Filter P01

Send the src address and len to indicate the starting address of an input sample and its length in words. Also send a dest value to indicate where the smoothed value is to be stored. Toggle the activate bit to perform the smoothing (i.e., could do an average of m elemenents). The SF sets it done bit to true when complete.

Inputs: unsigned src, unsigned len, unsigned dest, bit activate Output: bit done

Return to Yoda Topics

TLUA – Table look-up accelerator P02

Send the TLUA a start address of table, the rsize of each record in a table element, and the number of elements in the table (nelements). The table elements are in form:

  unsigned  key;

  byte record[rsize];

};

 The table itself is in the form:

struct TableElement table[nelements];

 The TLUA is sent a key for the value to look up in the table, and the TLUA return the index of the table element with that key if found, otherwise the value 0xFFFFFFFF. The activate input starts the TLUA lookup procedure. Note that the TLUA should be able to store the start and rsize information so that subsequent uses of the TLUA, using the same table, doesn’t need to resent the table address info.

 Inputs: unsigned start, unsigned rsize, unsigned nelements, bit activate Output: unsigned key, bit done

Return to Yoda Topics

IF – interpolation filter P03

Tell the IF the start address and len of a src float array to upsample, tell the IF the dst array that is 2x(end-start) elements, tell the IF to start. The IF then adds a value between each sample of src, saving the new sample in array dst (and sets done to true when finished). i.e. the C code would look like this:

int j = 0;

for (i=0; i<len-1; i++) {

   dst[j] = src[j];

   dst[j+1] = src[j] + (dst[j+1]- src[j])/2.0

  j = j + 2;

}

 Inputs: unsigned start, unsigned dst, unsigned len, bit start Outputs: bit done

Return to Yoda Topics

PRNG – Parallel Random Number Generator P04

Generate N random numbers in one go. The idea is that the PNRG could write directly to RAM, and a soft processor can access it. Generates numbers in range 0 to 2^32-1.

 Inputs: unsigned seed, unsigned start_address, unsigned count (i.e., num of random numbers to generate), bit activate Output: bit busy

Return to Yoda Topics

DM - Delta modulator P05

Send a stream of 8 bytes to the DM device, and it returns 1 byte, where the bits in sequence from lsb to msb represents the delta modulation.

 The delta modulator is pretty easy, so you might want to add additional features, for example:

 Optional extra feature 1: Make the LEDs on the FPGA board indicate the half wavelength (e.g. for a sinusoidal signal, the delta value is only going to change at the turning points, so counting the number of inputs from one change in delta to the next, and showing that number of the LEDs, will give a approximation for the wavelength).

 Optional extra feature 2: Add flow control. Assume that the DM might take a long time to complete. So, in this case, the processor needs to wait for the DM to be ready for input, then send the input, waits for the result, and then goes back to waiting for the DM to be ready for more input. You could add pushbutton control to either clock the DM or to control how fast it is clocked. The combination of Extra feature 1 and 2 will make it easier for humans to see the LEDs display wave length information.

 Inputs: byte byteIn, bit clock, Output: modOut

Return to Yoda Topics

ASG - Arithmetic series generator P06

This accelerator generates the series:

 a(n) =a1 + (n-1)d

 The inputs saddr indicates the starting address in memory where the generated sequence is to be stored. A activate input bit will be needed to tell the ASG to start processing; the ASG will return done when complete.

 Inputs: float a1, float d, unsigned n, unsigned saddr, bit activate Outputs: done

Return to Yoda Topics

SALG – Selection Address List Generator P07

The SALG is sent the starting address of a table in memory. The table has n elements. Each element of the table is in the form TableElement shown below. The SALG is sent a second address, called inds, which it will use to store the addresses (i.e., the starting address of the relevant record field) that matches the selection criteria (which is hardcoded).

struct TableElement {

  unsigned  key;

  byte record[rsize];

};

TableElement table[n];

 Example implementation of SALGA function that returns the address of all records that have odd numbered keys:

oid SALGA (TableElement* table, unsigned* inds, unsigned n)

{

  unsigned n_inds = 0;

  for (int i=0; i<n; i++) {

    if (table[n]->key & 1)

      inds[n_inds++] = &table[n]->record[0];

  }

  inds[n_inds]=0; // set last one to null to indicate end of list

}

 As is the case with the other accelerators, an activate input and done output would be needed.

 Inputs: unsigned table, unsigned n, unsigned inds, bit activate

Outputs: bit done

Return to Yoda Topics

FSG - Function Samples Generator P08

The FSG is used to generate a sequence of samples from a hard-coded function. The FSG is given two float inputs, xstart and xend, which indicates the range for the x values that you want to samples for the function, as well as an unsigned nsamp input indicating the number of samples you want to obtain. A fourth parameter, p indicates the memory address to write the sampled values to.

 The FSG implements a FPGA equivelent of the following C code. Note that the function fn would be hard-coded, it's just easier to show a function there to help the explanation in C.

void FSG ( float xstart, float xend, unsigned nsamp, float* p )

{

   unsigned i;

   done = 0; // clear the done signal

   for (i=0; i<nsamp; i++) p[i] = fn ( xstart + i*(xend-xstart)/nsamp );

   done = 1; // raise the done signal to indicate to the softprocessor that the operation is finished

}

float fn ( float x )

{

  // This example just returns a polynomial

  return 5*x*x + 3*x;

}

 Inputs: float xstart, float xend, unsigned nsamp, float* p, bit activate

 Outputs: bit done

    Return to Yoda Topics

BSS – Bit Sequence Sniffer P09

 The Bit Sequence Sniffer (BSS) device is connected onto a series binary data transmission line, for example a RS232 data line or (with an appropriate differential signal   demodulator unit) onto data lines of a USB connector. A ‘sniffer’ device has many real-work applications, and these type of thing exist in reality. ‘Data sniffers’ can be generally divided into a variety of types, such as: transmission line sniffers, debug sniffers, security sniffers, self-diagnostic sniffer module. Transmission line sniffers are perhaps the most general case; these could for example simply record data that is sent along data lines – these would generally be used for reputable purposes such as monitoring utilization levels of connections. Debug sniffers could for instance be JTAG-like devices that could be used to gain useful debugging data, for example checking that the bits sent from an ADC to the CPU are all successfully obtained by the CPU. Security sniffers have many applications, for example to detect threats to a network (e.g., a computer jamming the network with junk messages, or probing attacks from an unrecognized IP or stack overflow attacks). A basic sniffers is not a particularly complex piece of equipment, but they generally need to operate at high speed in order to capture the bits of data. For this project, the objective is to develop a RS232 transmission line sniffer that will be able to connect to either the RX or TX line and be able to capture bytes of data sent. To simplify things, the protocol can be assumed to be something easy like one start bit, 8 data bits, 1 parity and 1 stop bit (i.e., 11 bits per 8 bytes of data sent). Added to this should be detecting a particular sequence, say a series of bytes such as {0xA0, 0xB5, 0xFF}; and if such a sequence is detected, then a LED flashes. If time permits, a more sophisticated version could be constructed that detects a start sequence (e.g., 0xA0} and then captures the next 10 bytes and sends them out the USB / debug channel to be displayed on the attached PC. A small breadboard circuit will likely be needed in order to adjust voltage levels for the sniffer if one of the PIO pin on the FPGA is going to be used to sense the input.

 Notes on inputs and outputs:

 ·         SniffIn – this would be the input bit connected to one of the RS232 RT/TX data lines.

 ·         Seqdetect – output bit (to turn on LED also) to record that a preprogrammed sequence was detected.

 ·         DataOut – ability to dump a suspect sequence to a connected PC for recording (i.e., for if the last part of the description above is implemented).

Return to Yoda Topics

BCDC - Binary Coded Decimal Convertor P10

The BCDC converts a sequence of bytes into binary coded decimal format. Inputs the the device is a starting address, input src, and len indicating the number of bytes to convert. A third input ~dst~ indicates the address where the converted values are stored. As with the other proposed projects, when the active input changes from low to high, the BCDC starts, and then raises the done output to indicate completion.

 Notes on inputs and outputs:

 ·         Assume array bcd = {0000,0001,0010,0011,0100,0101,0110,0111,1000,1001,1010} // note each element is in base2

 ·         Each input x is one byte (i.e. range 0 to 255)

 ·         Each output is two bytes, call them a and b as follows:

 o    a = bcd[x/100]

 o    b = 16*bcd[(x-100*a)/10]

 o    b += bcd[x%10]

 Clearly, it's not all that efficient, because part of a is not used - but to keep it simple, you can leave output a as only half used.

 Example scenario: src: {20,101,96} dst: {0,32,1,1,0,150}

Return to Yoda Topics

NCSM - Nonlinear Check Sum Module P11

Most checksums are simple, just summing each input value, call it x(n) that comes in; so the function would read something like y = Sum x(n) for n = 1..n.

 This project aims to experiment with nonlinear checksums functions as a means to create a check value that is perhaps more robust but also more platform specific. The NCSM project probably sounds quite simple, and for the most part is. It implements 32-bit fixed point calculations of the input steam of bytes sent to the NCSM module. If you'd prefer a more intense challenge (that would also improve performance and look more impressive), then attempt to do the checksum on a block of RAM memory. The nonlinear function, called funct below must be implemented to account for wrapping and suitable use of mapping a 8-bit input to the 32-bit output range.

 The implementation in C-style pseudocode is as follows:

unsigned funct (input byte x, output unsigned y)

{

 y = 100*sin((x-128)*M_PI/32);

}

void checksum (input byte x, input bit reset, input bit clk, output unsigned result)

{

  static unsigned sum = 0;

  if (reset clocked) {

    sum = 0;

    return;

    }

  if (clk clocked) {

    sum = sum + funct(input,n);

    result = sum;

   }

}

 An graph of the suggested funct is provided below:

Inputs: unsigned x, bit reset, bit clk    Outputs: unsigned result

Return to Yoda Topics

CRCC - Cyclic Redundancy Check Calculator P12

As you probably know already, a cyclic redundancy check (CRC) is a polynomial code checksum for detecting errors in data given a certain pattern input (commonly used in communication protocols). You can decide on the specific CRC algorithm to implement, I'd suggest something simple, at least to start with. Ideally, the CRCC should work on a memory address range (i.e., a starting address, src, and number of bytes, len), and perform a CRC calculation on the memory, allowing the soft processor to do other things while the CRC is being calculated. The CRC

 Inputs: unsigned src, unsigned pattern, unsigned len

 Outputs: unsigned crc

 For suggestions on implementing CRC in hardware see: http://www3.rad.com/networks/1994/err_con/crc_hard.htm (described in http://www3.rad.com/networks/1994/err_con/crc_how.htm)

Return to Yoda Topics

MMA - Matrix Multiplier Accelerator P13

The MMA works on square matrices (if you feel inspited, you can revise it to work on appropriately sized rectangular matrices). Two memory addresses are passed to MMA, namely A and B, in indicate the starting addresses of the matrices to be multiplied. A third memory address, C indicates the address to save the resultant matrix. Input n indicates the size of the matrices. Assume the matrices contain floats. Assume that the matrix elements are indexed in the standard way, i.e.:

 index of A(i,j) = j * n + i (where i and j are in the range 0 to n-1)

 The activate bit input will be clocked to tell the MMA to start multiplying. The MMA will raise the done output high when it is complete.

Return to Yoda Topics

IMA - Image Masking Accelerator P14

The IMA overlays an image mask on a larger image using the XOR operation. Assume both the mask and the larger image are in RGB 24-bit color uncompressed format.

 Inputs:

·          mask : address of the image mask in memory

 ·         mw, mh : width and height in pixels of the mask.

 ·         mx, my: (x,y) offset from top left of image that the mask is to be applied

 ·         img : the image that the mask is to be overlaid on

·          iw, ih: the width and height in pixels of the image.

 ·         activate : bit input to be clocked to activate the IMA

 Outputs:

·         done : set high once the mask has been overlaid

Return to Yoda Topics

PSA - Pattern Seek Accelerator P15

The PSA searches for a particular sequence of bytes in a block of memory.

Inputs:

 unsigned p : the pattern to be searched for

 unsigned pl : length of the pattern in bytes

 unsigned b : address of the block of memory to search

 unsigned bl : number of bytes in b

 bit activate : clock to activate the PSA, and tell it to continue searching from last address

 bit reset : set b and clock reset to tell the PSA to start searching from address b

 Outputs:

·          bit done : the PSA sets this to high when it is complete

 ·         unsigned found : that the pattern started at (note that you might find it easier to set found to pl + the start of the patter that was found.

 ·          found could be set to 0xFFFFFFFF if nothing was found. Otherwise, you could add a success bit to indicate if the pattern was found.

 Simplification: if you want, you can simplify the topic. For example, the PSA could just respond with a found set to 1 or 0 depending whether the pattern was found. Further simplifications could be to look for a single byte in a block of memory (i.e., only using one address input, namely b).

 Example operation:

 will use:

    o        p = 0xFF00 pl = 2

     o       b = 0xFF10, bl = 8

     o      memory location 0xFF00: {101,102}

           o    memory location 0xFF10: {99,100,101,102,103,101,102,100}

steps:

     o    first the p will be reset

           o    PSA.b = 0xFF10; PSA.reset = 0; PSA.reset = 1; PSA.reset = 0;

           o    next the inputs are specified

 Ø  PSA.p = 0xFF00; PSA.pl = 2;

Ø  PSA.b = 0xFF10; PSA.pl = 8;

           o    The activate is clocked

 Ø  PSA.activate = 0; PSA.activate = 1; PSA.activate = 0;

           o    The PSA now proceeds to do the first search

           o    PSA sets done=1, and found=0xFF12 (i.e., the 3rd entry matched the pattern)

           o    The activate is clocked again to continue the search

 Ø  PSA.activate = 0; PSA.activate = 1; PSA.activate = 0;

           o    PSA sets done=1, and found=0xFF15 (i.e., another match was found)

 Ø  PSA.activate = 0; PSA.activate = 1; PSA.activate = 0;

           o    PSA sets done=1 and found=0xFFFFFFFF (i.e., no further matches were found)

 Return to Yoda Topics

DE – Data Encryption Accelerator P16

The objective the Data Encryption Accelerator (DEA) is to accelerate the process of encrypting a data stream. First the rst (reset) control line is clocked, this causes the DEA to reset any internal buffers and storage. Next, an encryption key is set by writing the (a single byte value) of the key to the din (data input) 8-bit data input bus, and then sending a positive edge to the kset (key set) control line. The dclk (data clock) is kept low. After this, the actual encryption starts, which involves iterating through all the data, one byte at a time, by writing a byte of data to the din input lines, then clock dclk clock line. The encrypted data is (pretty much) immediately available on the DEA's dout 8-bit output lines. The latter process is repeated for each item of data.

 To start with, you could use simple XOR encryption. If time permits, you could then take it further using some sort of repeating pattern based on the key input.

Return to Yoda Topics

VADER – Versatile Accelerated Digital Encryption Recovery P17

The VADER system is a digitally accelerated add-on hardware device designed to recover passwords using an acquired hashed password and hashing function. Uses of such a device could be to speed up computationally expensive recovery of passwords for forensic purposes such as instances where a victim or suspects password protected information could assist in an investigation. In order for the system to begin the specific hashing function used to create the password hashes would need to be acquired; it is assumed that this is available and many commonly used hashing functions are indeed widely available. The hashed version of the password itself would also need to be acquired. The system will run parallelized functions on an FPGA to accelerate the recovery of the password. The system will first run a dictionary type cracking attempt and following this if it is unsuccessful a brute force algorithm will be applied. A schematic flow diagram of how the system operates is shown below.

Return to Yoda Topics

PADAWAN - Parallel Accelerator for Digitising Audio with Attenuation of Noise P18

Defining the problem and suggested solution: The problem to be solved is performing filtering and processing on audio in near real-time using a FPGA

 Real-time filtering can be achieved in software, however when many filters are cascaded one after the other there will be a delay between audio input and output. For many applications this is an undesirable side-effect, stopping the system from being real time.

 Some types of filters that can be implemented are: Low-pass, high-pass, band-pass and band-stop. Some effects that can be implemented are: Echo, flange, chorus, reverb, vibrato, phaser, delay and distortion.