Basic VGA on an FPGA

I’ve been wanting to get into FPGAs for awhile. The fact that they are in a sense a very powerful carte blanche  for hardware projects is very tantalizing. A major motivation was the desire to understand video signal generation and to be able to do my own VGA projects. I was even thinking doing a scanline doubler for my Apple IIgs (with no RGB monitor) would be a great project.

To get started with FPGAs, I spent a bit of time looking into FPGA options. I really didn’t want to spend too much money but be able to do some reasonably sized. I settled on an older Altera EP2C5T144 clone. I downloaded it, learned a little Verilog and played with PCM blinking LEDs. I will spare you the details of getting the JTAG programmer to work with Ubuntu Linux (jtag needs to run as root). The Altera tools are a little complicated and clunky and compiling is quite slow on my 8 year old Linux box, but it works.

To take it to the next level, I knew I’d have to build some hardware to interface with a VGA port. I thought about it a bunch, designed a perfect R-2R resistor ladder that would take 3.3v in and have .7v nominal voltage when under a 75 ohm VGA spec load.  It seems like you should use opamp buffers or something, but I haven’t really searched hard for what the right chip for that would be. I also looked into DVI driver chips because the EP2CT5144 does not have the high speed differential outputs that I would need to reliably generate DVI. I actually picked up a few and I think when I do a real project, I’ll make a board that supports DVI and VGA for maximum awesome.  I thought about etching my own R-2R board that interfaces with my fpga, and I think that would be a good approach in the future.

Of course like most well-laid out hardware project plans I didn’t have time to do anything on this for a long time. I’ve been trying to cut down my internet “research” (watching other people do their own projects), but youtube is addictive.  Interestingly the reason I started this project was that my son has an obsession with helicopters that I thought would be well served by getting my dead battery containing Syma helicopter working. So, I figured that while I had my soldering iron out to fix the helicopter I should at least build the hardware for the VGA.

Since I had limited time, I decided to solder the minimum possible VGA board. The main question is what resistor to use for the RGB signals. I want a load 75 ohm to achieve about .7 volts so I have
 i_1 = i_2  \Rightarrow .7/75 = (3.3-0.7)/x \Rightarrow x=278\Omega \approx 270\Omega.
Given that we have this schematic:
fpga

That should give us about 8 colors. I’ll solder the leads and feed into a breadboard to put our resistors on. Then, we’ll connect to the EP2CT5144 dev board’s male jacks using a male to female ribbon connector.  (aside: The connectors and wires to use is always a part of electronics that I seem to do badly. In fact, I’d really like to know where I can find ribbon cable connector supplies, or if there is a good tutorial on what kind of connector stuff to use when). The finish product turned out crappy but workable as shown here:

DSC_3622-1

Of course I couldn’t really keep myself to working only the hardware at that point. I had been reading fpga4fun’s intro to VGA, and I had gotten that working to the point where it simulated ok. After hooking this up and reassigning the pins I thought it would just work. Of course it didn’t really work, and after a bunch of debugging, I found that I had swapped the hsync and vsync lines. So I fixed that, and it worked. Then I got to trying to draw a test pattern. I wasn’t really happy white the white level or the accuracy of the pixel placement (my LCD’s auto centering was totally flaking out), so I thought I’d have to play a little less fast and loose with the blanking portion.

I then wanted to be more precise about pixel locations and properly doing the front and back porch. I read the wikipedia page on VGA and I found that it would be smarter to do everything in terms of the pixel clock over the standard number of pixels. Then I played with it a bunch, and I really wasn’t super happy with the implementation. I wanted to try to do a better job of staying in spec, whereas fpga4fun plays really fast and loose, I only wanted to play kinda fast and loose. I modified the verilog implementation to do everything in terms of virtual pixel clock pixels.

Param Horizontal Vertical
Pixel clock 25.175MHz
Pixels 800 525
Sync range (in pixels) [16,112) [10,12)
Image range (in pixels) [160,800) [45,525)
Sync Frequency 25e6/800 = 31.25 kHz 25e6/800/525 = 59.52 Hz

Ideally this should be implementable with two counters and a state machine.  You could up the counters until they get to threshold for a given state and then transition. For now, I just went simpler and use 4 counters, two for the raw pixels and two for the visible pixels.  I am using all kinds of inefficient logic that probably creates adders to do comparisons, so I should try to optimize the number of gates down at some point. FPGAs really make it to waste lots of hardware, but that really is no different than writing in an inefficient scripting language on the software end. On the software side, I know better, I’m a newbie at hardware, so I’m sure I’m doing a lot wrong.

One big deal is this is the first project I’ve been working on using an oscilloscope. Debugging this with the oscilloscope was so much easier (and more fun), and I’m glad I waited to attempt this project until I got one.

pixelDataAndHsync signalGenerationHsyncVsync

Once the signals looked perfect and awesome, I decided to make sure I actually can see the full width of the screen, so I drew a box on the outer edge and I drew some colored boxes. I was having trouble with getting a proper full screen view on my LCD before my rewrite. Now it worked perfectly. Another improvement  that occurred from this rewrite was that the brightness of the whites improved (I had a very dim grey before).

While I was this far and it was only 1am, I decided to make another module that handles bouncing a ball. This was pretty easy, but I needed to make sure to denote my registers for pixel location as signed, so the twos complement addition for the velocity to position update. The final result showing the results is here:

DSC_3612-2

You probably want to checkout the youtube of this in action

Circuit Simulation Part II – Schematic Capture using HTML5 Canvas

Ok, we need to be able to create circuits in the web interface. The basic idea will be how to use a HTML5 canvas to draw the schematic and use mouse events to manipulate the schematic. The first order of business is to have a Component class. This will know where the component is located at, generically know how to draw stuff and also know how to do movement, selection etc. We’ll start with a simple interface. Before we do that we need a class to contain everything about the schematic. We’ll do this with SchematicCapture. This will know about the list of components and it will also know things about how the view is defined.

I’ll warn you ahead of time, my HTML5 experience and prowess is not very strong. I am much more comfortable and accomplished in C++, and I’m sure I’m doing some horrible things that are horribly inefficient and brain damaged. This whole project is really just an educational experiment to see how good a UI made entirely in JavaScript is and how I can create one.

I’ll remark that I did discover a similar project to this one that is part of the MIT open courseware circuit course tool. Undoubtedly they did a better job than I did, but I’m trying to do this on-my-own in true not-invented-here fashion. I am also trying to document how I solve the problem step by step, mistakes and all.

Basic drawing

We’re going to use the notion of a windowing transform. Basically we have device coordinates which are the pixel locations, but we want a virtual canvas so we’re going to have “world” coordinates. The way we transform back and forth is quite simple. First, we have the notion of a xmin, xmax, ymin, ymax window we would like to view and we know our device is from canvas.width by canvas.height. To convert from device to world we make two functions to convert from world to device coordinates as

var xToDevice=function(x){return (x-xmin)/(xmax-xmin)*width};
var yToDevice=function(y){return (y-ymin)/(ymax-ymin)*height};

The first thing we need is a grid. We will make a grid line every dx. To draw the x grid we have the following code. First, we draw the background in yellow and then we draw the x lines in blue. We use floor to figure out where to start drawing the line to define xstart and then we continue until we go past xmax. Even though clipping would allow us to draw beyond, it would inefficient (and infinitely so) to draw everyline everywhere.

SchematicCapture.draw = function(){
    ...
    // draw grid lines
    context.fillStyle = "rgba(255, 255, 180, 255)";
    context.fillRect(0, 0, width, height);
    var dx=1;
    context.strokeStyle = "rgba(100, 100, 255, .5)";
    var xstart = Math.floor(xmin / dx);
    for(var x=xstart;x<xmax;x+=dx){
        context.moveTo(xToDevice(x),yToDevice(ymin));
        context.lineTo(xToDevice(x),yToDevice(ymax));
    }
    ...	

Now we get something that looks like this… I know super exciting…

grid

Once we have that abstraction we can delegate drawing to each component in our list as:

// draw symbols
SchematicCapture.draw = function(){
    ... 
    for(var v in this.symbols){
        this.symbols[v].draw(xToDevice,yToDevice,context);
    }
    ...
}

This is exciting, now we are ready to define a generic component. The main idea is we will have a list of points that the component knows to draw and a generic point that loops through and draws the points. The basic component will store a location and a rotation (0,1,2,3) for no rotation, 90 degrees, 180 degrees and 270 degrees. To do this we need three basic functions on our component: the constructor, the objectToWorld to transform points from object space to world space, and the draw which will draw the component.  Here are the basic three functions for the component

// Construct a component at a given position and rotation
Component = function(x,y,rotation){
    this.x = x; // xlocation of origin in world space
    this.y = y; // ylocation of origin in world space
    this.rotation = rotation; // 0 to 2
    // compute the bounding box
    this.box = [1e7,-1e7,1e7,-1e7];
    for(var ptK in this.points){
        var pt = this.points[ptK];
        if(!pt) continue;
        var pt = this.objectToWorld(pt[0],pt[1]);
        this.box[0]=Math.min(this.box[0],pt[0]);
        this.box[1]=Math.max(this.box[1],pt[0]);
        this.box[2]=Math.min(this.box[2],pt[1]);
        this.box[3]=Math.max(this.box[3],pt[1]);
    }
}

// Transform from object space to world space a point x,y
Component.prototype.objectToWorld=function(x,y){
    if(this.rotation==0) return [x+this.x,y+this.y];
    else if(this.rotation==1) return [this.x+y,this.y-x];
    else if(this.rotation==2) return [this.x-x,this.y-y];
    else if(this.rotation==3) return [this.x-y,this.y+x];
}

// Draw a component at a given location
Component.prototype.draw=function(xToDevice,yToDevice,context){
    context.beginPath();
    //var points=[[0,-1],[0,0],[2,0],[2.5,-1],[3.5,1],[4.5,-1],[5.5,1],[6.5,-1],[7.5,1],[8,0],[10,0]]
    var first=true; // first point has to be a moveTo
    for(var dummy in this.points){
        var ptOrig=this.points[dummy];
        // check if we are at a null point and reset the draw count
        if(ptOrig == null){first = true;continue;}
        // transform the point into world device coordinates
        var pt=this.objectToWorld(ptOrig[0],ptOrig[1]);
        if(first){
            context.moveTo(xToDevice(pt[0]),yToDevice(pt[1]));
            first=false;
        }else{
            context.lineTo(xToDevice(pt[0]),yToDevice(pt[1]));
        }
    }
    context.stroke();
    // draw a label for the value of the component
    var pt=this.objectToWorld(3.5,-3.5);
    context.font = "10pt sans-serif"
    context.fillStyle = "#000000";
    context.fillText(this.value,xToDevice(pt[0]),yToDevice(pt[1]));
}

Now, we just need to define subclasses to define our component types. For example, here is our resistor component definition

ResistorSymbol =  function(x,y,rotation){
    this.points=[[0,-1],[0,0],[2,0],[2.5,-1],[3.5,1],[4.5,-1],[5.5,1],[6.5,-1],[7.5,1],[8,0],[10,0]]
    Component.call(this,x,y,rotation)
    this.value = "1k"
}
ResistorSymbol.prototype = new Component()

We can create definitions for capacitors, voltage sources and everything else we need similarly. If we hard code a few component constructors in our SchematicCapture class instantiation, we get something that looks like this:

components

Not bad!

Basic selection and interaction

Schematic capture is really not very good for anything unless we can move things around and add components. Let’s attack the problem of moving things around. Basically the idea is that we’ll register mouseDown, mouseUp and mouseMove handlers, and in the mouseDown we’ll find if we have selected anything to control how the other handlers work. We’ll use the bounding boxes that we have created as a simple way of knowing whether the given world-space coordinates are inside a component. We’ll just use linear search for now, but one could imagine making a bounding box hierarchy or something smarter to get down to some sub-linear (maybe logarithmic) time.

Highlighting

First thing I implemented was highlighting. This will make sure I have the coordinates transforming properly and the bounding boxes
bounding properly. I needed to do some refactoring, but the main thrust consists of delegating mouseMove to the schematic (which involved storing a pointer to the schematic type from the canvas type). The mouseMove implementation also needs to be augmented to check if we are inside something and if we are make it redraw in a nice color. Here’s mouseMove.

SchematicCapture.prototype.mouseMove =  function(event){
...
        var oldHighlight = this.highlight;
        this.highlight=null;
        for(var v in this.symbols){
            var symbol=this.symbols[v];
            if(symbol.inside(newX,newY)){
                this.highlight=symbol;
            }
        }
        if(this.highlight != oldHighlight) this.draw(); // only draw if we changed highlight
}

Here we have used the inside function on the component to check if a given world coordinate is inside a given world bounding box. Its implementation is this:

Component.prototype.inside=function(xWorld,yWorld){
    return xWorld > this.box[0] && xWorld < this.box[1] && yWorld > this.box[2] && yWorld < this.box[3];
}

In addition to actually affect how drawing happens, we made SchematicCapture.draw() send the highlight flag into the Component.draw. I’ll spare you the annoying details.

Basic movement

Now that we have highlighting working we need to attack the more difficult task of movement. I’m going to just assume we need one selection for now to move. I’d like to have multi-select with shfit and marquee (a.k.a. bounding box) select working but all that jazz is complicated and I want to start simple.

Implementing these mouse interaction routines I’ve done about a billion times now, starting with OpenGL in my intro graphics class using fltk. In javascript it works pretty much the same as fltk, win32, gtk, Qt, and every other graphics library I have ever used. The best way to do these things is to remember the coordinate of the event that you last handled in the schematic class. Then when you get a new mousemove or whatever event you can look at the difference and add that as an offset to the component position you are currently selecting. In pseudocode

mouseDown(){
    this.x,this.y=event.x,event.y
    this.dragging=highlightedObject;
}
mouseMove(){
    offx,offy=event.x-this.x,event.y-this.y
    if(this.dragging){
        this.x,this.y=event.x,event.y
        highlightedObject.addOffset(offx,offy)
    }
}
mouseUp(){
    this.dragging=false;
}

Ok, it turned out to be a little bit more complicated than that. For one thing, I actually store the event x and event y in world space so I don’t need to double transform. Another major thing I wanted for the schematic capture was to clamp to a grid. To do this we might have fractional mouse movements with respect to the snapping grid. To avoid trouble with this and ensure simplicity, during interaction I keep an extra position for each moved component. This is done by the addOffset() function. It basically stores the x,y in this.fracX and this.fracY on the object, but it also rounds to create the this.x and this.y. This makes the rounding hysteresis work properly. In mouseUp I call a routine to drop the fraction in fracX , fracY and synchronize it to be the same as x,y. addOffset() is nice to break into its own function because I can do the handling of fractional positioning while at the same time being sure to update the world bounding box.

Adding wires

Adding wires is an important thing in that we need to be able to connect different components. Connections seem like they are going to be harder. Lets start out less ambitious and just represent line segments. I think that if we can have line segments just be a component like we already had, that will work nicely. Unlike other components, rotation probably doesn’t make sense, but lets just leave that in and ignore that for now. The basic method of representing a wire will be to use the position of the first end point of the wire and then store an offset to the second wire. So we’ll have two points in our base class draw [[0,0],[dx,dy]] where dx,dy = x2-x1,y2-y1.

One challenge is that we need to implement an inside function that will allow us to query whether we are close to the line segment. That turns out to be a simple linear algebra problem which is described in this diagram. Basically we make two vectors between the first point of the wire and the query point of the moues cursor and the second point in wire and compute cross product and dot product. That gives us values that can be used to measure perpendicular and parallel distance. You could also think about it as rotating the coordinates of the cursor position and translating them into a reference frame  where the wire AB is along the x-axis. That begs the question why not just represent the wire with that as the object space, and that might make the inside test easier, but it really is just pushing the problem around and it would force us to support non-axis aligned rotations for components. So we’ll just do this in the inside call

wireInside

 

The code corresponding to the wire component is:

WireSymbol = function(x,y,x1,y1){
    this.points=[[0,0],[x1-x,y1-y]];
    Component.call(this,x,y,0)
}
WireSymbol.prototype = new Component()
WireSymbol.prototype.inside=function(xWorld,yWorld){
    // v1 is vector from first point of wire to the cursor position
    // v2 is the vector from the first point to the second wire normalized
    // dotProduct(v1,v2) = cos(theta) |v1| |v2| = cos(theta) |v1|  must be in the interval [-threshold,v1+threhsold]
    // crossProduct(v1,v2) = sin(theta) |v1| |v2| = sin(theta) |v1| must be within [-threhsold,|v1|+threshold]
    var wireInsideThreshold = 0.5
    var len=Math.sqrt(this.points[1][0]*this.points[1][0]+this.points[1][1]*this.points[1][1]);
    var invLen=1./len;
    var v1=[xWorld-this.x,yWorld-this.y];
    var v2=[this.points[1][0]*invLen,this.points[1][1]*invLen];
    var parallelDistance=Math.abs(v1[0]*v2[1]-v1[1]*v2[0]); // length of perpendicular segment i.e. distance from light containing segment
    var perpendicularDistance=(v1[0]*v2[0]+v1[1]*v2[1]); // projected point parameter
    return Math.abs(parallelDistance) < wireInsideThreshold && perpendicularDistance > -wireInsideThreshold && perpendicularDistance < len+wireInsideThreshold
}

Remaining things to do

I think that is enough for today. Let’s reflect and see where we are. We got a couple of things done.

  • Basic drawing of gridlines and canvas
  • Basic component infrastructure with wires, voltage sources, resistors, and capacitors visualized

We still have a ton to do that we should leave for a future post

  • Interface to add components. Hopefully something like the “tab” convention in node-based graphics tools like Nuke and Houdini. Unobtrusive and fast!
  • Interface to add wires
  • Manage connections between components (need to track pins, wires overlapping pins and other wires)
  • Deletion of components
  • Selection/manipulation of multiple components
  • Zooming and scrolling of virtual schematic
  • The actual simulator!

There are several could be betters (CBBs) that we still have brewing:

  • The code is a mess. Better compartmentalization, naming, commenting would be good
  • We make too many temporaries (arrays). It’s hard to avoid without having functions for each component. I.e. look at transform(), we return an array.
  • We could probably increase abstraction and elegance by having a vector class. In C++ this is really cheap and is the way to go. In JavaScript this blows up the number of temporaries to high hell. In general I find JavaScript makes having abstract and elegant code that is performant much harder than C++. The sub-typing feels expensive compared to C++’s facilities like structs, templatization, inlining, and all that static goodness.

To see what we have go to the page or check it out embedded here (live)

Circuit simulation in Javascript Part I

As I’ve been trying to learn more about electronics, circuit simulation is an interesting route to go. No messy wires, can easily see idealized properties on a virtual oscilloscope, don’t have to wait for parts. Obviously there are limitations to models and nothing beats getting the real thing to work.

There are many SPICE derivatives that one can select. Perhaps the easiest to use is LTspice. The main innovation in the original spice paper was a practical bipolar transistor model that was suitable for simulation. The basic technique of SPICE varies based on what type of simulation. Currently I am interested in the transient analysis which gives a time varying definition of the voltage and current for any point in the circuit. There are other modes and even the simplest operating point analysis (tutorial on the eevblog) is powerful.

The project

SPICE is nice and all, but since I want to learn how things work, I thought I’d write a circuit simulator from scratch in JavaScript. It shouldn’t be that hard, and it should really hone my intuition about how circuits work in a way that is much funner than solving basic circuits. Ideally I’ll do this in phases. For the first version described here I’ll support

  • Ideal voltage sources
  • Manual hard-coded circuits in the javascript file
  • Resistors and capacitors (linear passives)
  • Oscilloscope like view

In a later version these features would be nice to have

  • Inductors and diodes (non-linear passives)
  • Ideal opamps
  • Transistors and FETs
  • Transformers

Theory on solving circuits

The basic method we are going to use is Kirchoff’s Current Law that states that the net incoming and outgoing current is zero. So, basically for any component that has k nodes, it will contribute to k KCL equations in the circuit. Basically we need to solve all of the KCL simultaneously, so this should basically imply we are solving a big matrix. So let’s do a simple circuit example:

circuit

Notice how I have specified a GND to the circuit. This is essential, if you don’t do this you can’t solve for voltages because they won’t be relative to any zero. Now that we have our circuit, we need to write the KCL laws for all the nodes which will form some of the constraints of our circuit solution.

Let’s denote voltage at A, B, GND to be v(A), v(B), v(GND), respectively. The KCL at B is clearly \frac{v(A)-v(B)}{100} - \frac{v(B)-v(GND)}{100} = 0. Note I have used Ohm’s law for R1 and R2 separately and each component incident on B contributed to the KCL for B.

Now the slightly tricky part, writing the KCL laws for GND and A, because we don’t directly know the current going through V1. There is no Ohm’s law to help us here. Probably I should have started this endeavear with current sources, but let’s just go with it. The major observation is that we need to introduce an unknown variable for the current through V1, we’ll call it i(V1). That gives us i(V1) - \frac{v(A)-v(B)}{100} = 0. Notice how this equation’s second term is the negative of the first term of the KCL at B. That is because these circuit elements contribute symmetrically to the linear system and so we will get a symmetric matrix if we do things right. This is a great property to have because there are special matrix solvers that are much more efficient but only apply to positive definite and symmetric matrices (i.e. conjugate gradient).

Next we should write KCL for the GND node. However, that really wouldn’t be particularly interesting, because we already know what v(GND) will be — zero. So we will use v(\textrm{GND})=0.

So now we have three equations but four unknowns v(A),v(B),v(G),i(V1). We need one more equation to have a fully determined linear system,. One fact we haven’t included is that the voltage between A and G should be 5. So that gives us v(A)-v(G)-5=0. If we write these all as a system we get

\begin{matrix}  \frac{v(A)-v(B)}{100} - \frac{v(B)-v(G)}{100} & = & 0 \\ v(G) & = & 0 \\ i(V1) - \frac{v(A)-v(B)}{100} & = & 0 \\ v(A)-v(G) - 5 & = & 0  \end{matrix}

We can rewrite this in matrix form (Ax=b) and we get

matrixUnordered

The rows can be reordered to reflect the symmetry better.

matrixOrdered

If we plug this into our favorite linear solver (in this case I’m using SAGE)

from numpy import arange, eye, linalg
a=1/100;
A=matrix([[-a,a,0,1],[a,-2*a,a,0],[0,0,1,0],[1,0,-1,0]]);
b=matrix([[0],[0],[0],[5]]);
linalg.solve(A,b)

array([[ 5.   ],
       [ 2.5  ],
       [ 0.   ],
       [ 0.025]])

In other words v(A)=5 volts, v(B)=2.5 volts (go voltage divider), v(G)=0 volts, i(V1)=0.025 A. Everything is as we expected. In the next part we see how to code this into something that doesn’t require all this manual effort.