## Computing Fixed-Point Square Roots and Their Reciprocals Using Goldschmidt Algorithm

Introduction

A well known algorithm for computing square roots by iteration is provided by the Newton-Raphson Algorithm. The algorithm determines the square root using iteration until the root has been determined to some user-defined level of accuracy. The method is easily derived. First, describe a number in terms of its square root:

$$a = y ^ {2} ,$$

where $y = \sqrt{a}$. The value of the $\sqrt{a}$ can be written as $y = y_0 + \epsilon$, where $y_0$ is the value of the square root and...

## Dealing With Fixed Point Fractions

Fixed point fractional representation always gives me a headache because I screw it up the first time I try to implement an algorithm. The difference between integer operations and fractional operations is in the overflow.  If the representation fits in the fixed point result, you can not tell the difference between fixed point integer and fixed point fractions.  When integers overflow, they lose data off the most significant bits.  When fractions overflow, they lose data off...

## Polynomial Inverse

One of the important steps of computing point addition over elliptic curves is a division of two polynomials.  When working in $GF(2^n)$ we don't have large enough powers to actually do a division, so we compute the inverse of the denominator and then multiply.  This is usually done using Euclid's method, but if squaring and multiplying are fast we can take advantage of these operations and compute the multiplicative inverse in just a few steps.

The first time I ran across this...

## One Clock Cycle Polynomial Math

Error correction codes and cryptographic computations are most easily performed working with $GF(2^n)$  polynomials.  By using very special values of $n$ we can build circuits which multiply and square in one clock cycle on an FPGA. These circuits come about by flipping back and forth between a standard polynomial basis and a normal basis representation of elements in $GF(2^n)$.

A normal basis is yet another form of polynomial but instead of adding powers of $\beta$ we add...

In this article I will take a look at the wonderful MuPDF viewer and present a small modification that saves bookmarks alongside the pdf files, making it infinitely more useful.

Some days I sit down to work and wonder how anything ever gets done. A simple example.  When I work on an FPGA design, I wind up with 3 or 4 screens full of documentation, generally in PDF format.  There are the Xilinx manuals, the various tool manuals, language reference manuals, you name it.  While...

## Inside the Spartan-6: Using LUTs to optimize circuits

While building a small CPU on a Spartan-6 chip I came across the same old problem: my Verilog was mapping to a lot of slices . Way more then seems reasonable. So let's dig in and see what's really going on.

The J1 CPU (see Messing Around with a J1) is an amazingly streamlined design expressed in just over 100 lines of Verilog, and is reasonably compact at 150 Spartan-6 slices (half of that with the modifications described in the article).  But the Picoblaze is...

## Makefiles for Xilinx Tools

Building a bitstream from an HDL is a complicated process that requires the cooperation of a lot of tools.  You can hide behind an IDE or grow a pair and use command line tools and a makefile to tie your build process together.  I am not a huge fan of makefiles either (I believe a language should be expressive enough to automate the build process), but the alternatives are dismal.

Command-line driven workflow is easier on the hands and faster.  The example...

## Use Microprogramming to Save Resources and Increase Functionality

Introduction

Microprogramming is a design approach that every FPGA designer should have in their bag of tricks. I subscribe to the concept that microprogramming is a structured approach to the design of state machines. This is essentially the view of Maurice Wilkes when he first proposed microprogramming in 1951 as an alternative method for the implementation of the control section of a computer. Wilkes was interested in improving the reliability and reducing time needed to implement...

## I don’t often convert VHDL to Verilog but when I do ...

VHDL to Verilog

I don’t often convert VHDL to Verilog but when I do it is not the most exciting task in the world (that is an understatement).  For the most part I am HDL agnostic.  Well that is not true, I have a strong preference for MyHDL, and an insubstantial preference for VHDL over Verilog.  The choice of HDL for a project is often complicated, irrational, sometimes rational, but most often random.  It is often not a choice of the developer - for...

## MyHDL Interface Example

MyHDL Interfaces Example

With the next release of MyHDL, version 0.9, conversion of interfaces will be supported.  In this context an interface is any object with a Signal attribute.  This can be used to simplify connection between modules and port definitions.  For example, if I want to define a simple memory-map bus, the Signals for the bus can be defined as follows:

class BareBoneBus: def __init__(self): self.wr = Signal(False) self.rd =...

## BGA and QFP at Home 1 - A Practical Guide.

It is almost universally accepted by the hobbyists that you can't work with high-density packages at home.  That is entirely incorrect.  I've been assembling and reflowing BGA circuit boards at home for a few years now.  BGAs and 0.5mm-pitch QFPs are well within the realm of a determined amateur.

This series of articles presents practical information on designing and assembling boards with high-density packages at home.  While the focus is on FPGA packages, most of...

## I don’t often convert VHDL to Verilog but when I do ...

VHDL to Verilog

I don’t often convert VHDL to Verilog but when I do it is not the most exciting task in the world (that is an understatement).  For the most part I am HDL agnostic.  Well that is not true, I have a strong preference for MyHDL, and an insubstantial preference for VHDL over Verilog.  The choice of HDL for a project is often complicated, irrational, sometimes rational, but most often random.  It is often not a choice of the developer - for...

## An Editor for HDLs

Unless you're still living in the '90s and using schematics, your FPGA designs are entered into text files as VHDL or Verilog source. Which, of course, implies you're using some form of text editor. Now, right after brace placement in C, the choice of an editor is the topic most likely to incite a nerd civil war (it's a bike-shed issue). I won't attempt to influence your choice because it really makes no difference to me. But if you are using the same editor I do, then maybe I can help you...

## MyHDL FPGA Tutorial II (Audio Echo)

Introduction

This tutorial will walk through an audio echo that can be implemented on an FPGA development board.  This tutorial is quite a bit more involved than the previous MyHDL FPGA tutorial.  This project will require an FPGA board with an audio codec and the interface logic to the audio codec.

Review the Previous Tutorial

The previous MyHDL FPGA tutorial I posted a strobing LED on an FPGA board.  In that tutorial we introduced the basics of a MyHDL module....

## VGA Output in 7 Slices. Really.

Ridiculous? Read on - I will show you how to generate VGA timing in seven XilinxR Spartan3R slices.Some time ago I needed to output video to a VGA monitor for my Apple ][ FPGA clone.  Obviously (I thought), VGA's been done before and all I had to do was find some Verilog code and drop it into my design.  As is often the case (with me anyway), the task proved to be very different from my imagined 'couple of hours to integrate the IP'.I found some example code for my board.  I...

## Dealing With Fixed Point Fractions

Fixed point fractional representation always gives me a headache because I screw it up the first time I try to implement an algorithm. The difference between integer operations and fractional operations is in the overflow.  If the representation fits in the fixed point result, you can not tell the difference between fixed point integer and fixed point fractions.  When integers overflow, they lose data off the most significant bits.  When fractions overflow, they lose data off...

## Inside the Spartan-6: Using LUTs to optimize circuits

While building a small CPU on a Spartan-6 chip I came across the same old problem: my Verilog was mapping to a lot of slices . Way more then seems reasonable. So let's dig in and see what's really going on.

The J1 CPU (see Messing Around with a J1) is an amazingly streamlined design expressed in just over 100 lines of Verilog, and is reasonably compact at 150 Spartan-6 slices (half of that with the modifications described in the article).  But the Picoblaze is...

## How to start in FPGA development? - Some tips

Introduction

The aim of this tutorial is to show some useful tips for people like me that one day started from zero to work with FPGA's. Why FPGA's? Because they are easy to use and they are not too expensive, and they are usually used in lab courses to let students "play" with them.

1: How to choose the right FPGA?

As you may know there are a lot of different FPGA's, brands and models. How to choose the right one? It's very difficult to say that before knowing which will be the...

## How to start in FPGA development? - Simulation software tools

Introduction

This post is related to the first post How to start in FPGA development? - Some tips which aimed to show other options to work on the simulation of your project. In this first approach will be explained some advantages and disadvantages of using Xilinx ISE (+ModelSim) or using ModelSim, Precision and Xilinx ISE. And finally my opinion of which are the ones I...

## Computing Fixed-Point Square Roots and Their Reciprocals Using Goldschmidt Algorithm

Introduction

A well known algorithm for computing square roots by iteration is provided by the Newton-Raphson Algorithm. The algorithm determines the square root using iteration until the root has been determined to some user-defined level of accuracy. The method is easily derived. First, describe a number in terms of its square root:

$$a = y ^ {2} ,$$

where $y = \sqrt{a}$. The value of the $\sqrt{a}$ can be written as $y = y_0 + \epsilon$, where $y_0$ is the value of the square root and...