Post a Comment On: Ken Shirriff's blog

pre {border:none;background-color:#eee;display:inline-block;min-width:30em;padding:4px;font-size:80%;} code {background-color:#eee; font-size:100%;} This blog post shows how you can generate a video signal with an FPGA, using the FizzBuzz problem as an example. Creating video with an FPGA was easier than I expected, simpler than my previous serial-line FizzBuzz on an FPGA. I got a bit carried away with the project and added animation, rainbow text and giant bouncing words to the display. [Image]FizzBuzz from an FPGA board. The board generates raw VGA video output with the results animated, along with the words "Fizz" and "Buzz" that bounce around the screen. If you're not familiar with the "FizzBuzz test", the problem is to write a program that prints the numbers from 1 to 100, except multiples of 3 are replaced with the word "Fizz", multiples of 5 with "Buzz" and multiples of both with "FizzBuzz". Since FizzBuzz can be implemented in a few lines of code, it can be used as an interview question to weed out people who can't program at all. But it's much more of a challenge on an FPGA. An FPGA (Field-Programmable Gate Array) is an interesting chip that you can program to implement arbitrary digital logic. This lets you build a complex digital circuit without wiring up individual gates and flip flops. It's like having a custom chip that can be anything from a logic analyzer to a microprocessor to a video generator. For this project, I used the Mojo FPGA board (below). [Image]The Mojo FPGA board. The Spartan-6 FPGA chip dominates the board. Generating the VGA signals There's a learning curve to an FPGA, since you're designing circuits, not writing software that runs on a processor. But if you can blink five LEDs with an FPGA, you're most of the way to creating a VGA video signal. The VGA video format is a lot simpler than I expected: just three signals for the pixels (red, green and blue), and two signals for horizontal sync and vertical sync. The basic idea is to use two counters: one to count pixels horizontally and one to count lines vertically. At each spot on the screen, the desired pixel color is generated from these coordinates. In addition, the horizontal and vertical sync signals are produced when the counters are at the right positions. I used the basic 640x480 VGA screen resolution2 which requires counting to 800 and 525.111 Horizontally, there are 800 pixels for each line: 640 visible image pixels, followed by 16 blank pixels, 96 pixels of horizontal sync and 48 more blank pixels. (There are historical reasons for these strange numbers.) Meanwhile, the vertical counter must count out 525 lines: 480 image lines, 10 blank lines, 2 lines of vertical sync and 33 more blank lines. Putting this all together, I created a vga module (source) to generate the VGA signals. This code is in Verilog (a standard language for FPGAs); I won't explain Verilog thoroughly, but hopefully enough to show how it works. The code below implements the x and y counters. The first line indicates action is taken on the positive edge of each (50 MHz) clock signal. The next line toggles clk25 each clock, creating the 25 MHz signal we'll use for the pixel clock. (One confusing thing is that <= indicates assignment, not comparison.) The code increments the x counter from 0 to 799. At the end of each line, y is incremented, running from 0 to 524. Thus, this code generates the necessary pixel and line counters. always @(posedge clk) begin clk25 <= ~clk25; if (clk25 == 1) begin if (x < 799) begin x <= x + 1; end else begin x <= 0; if (y < 524) begin y <= y + 1; end else begin y <= 0; end end end end While Verilog code looks like a standard programming language, its effects are very different. This code doesn't generate instructions that are executed sequentially by a processor, but instead causes circuitry to be instantiated in the FPGA chip. It creates registers from flip flops for clk25, x and y. Binary adders are generated to increment x and y. The if statements turn into logic gate comparators controlling the registers. All this circuitry runs in parallel, triggered by the 50 MHz clock. To understand FPGAs, you need to get out of the sequential program mindset and think of the underlying circuits. Getting back to the vga module, the horizontal and vertical sync signals are generated from the x and y counters by the code below. In addition, a valid flag indicates the 640x480 region where a video signal should be generated; the screen must be blank outside this region. As before, these Verilog statements are generating logic gates to test the conditions, not creating code. assign hsync = x < (640 + 16) || x >= (640 + 16 + 96); assign vsync = y < (480 + 10) || y >= (480 + 10 + 2); assign valid = (x < 640) && (y < 480); The "useful" part of the VGA signal is the red, green, and blue pixel signals that control what appears on the screen. To test everything out, I wrote a few lines to turn r, g and b on for various regions of the screen, blanking them all outside the visible (`valid`) area.3 (The question mark is the ternary conditional operator, as in Java) if (valid) begin rval = (x < 120 || x > 320) ? 1 : 0; gval = (y < 240 || y > 360) ? 1 : 0; bval = (x > 500 && (y < 120 || y > 300)) ? 1 : 0; end else begin rval = 0; gval = 0; bval = 0; end I ran the code on my FPGA board and nothing happened—the monitor stayed black and I wondered what went wrong. Fortunately, after a couple seconds4 the monitor completed its normal startup cycle and displayed the output. I was pleasantly surprised that VGA output worked the first time, even if the output was just arbitrary blocks of color.5 [Image]My first VGA program produced random color blocks on the screen. Not very meaningful, but it showed that everything worked. Putting characters on the screen The next step was to display text characters on the screen. I implemented a character generation module to provides the pixels for an 8x8 character. Rather than include the full ASCII character set, I only used the characters necessary for FizzBuzz: 0 through 9, "B", "F", "i", "u", "z" and blank. Conveniently, this worked out to 16 character values, fitting into a 4-bit input. Thus, the module takes a 4-bit character code and a 3-bit row number (for the 8 lines of each character) and outputs 8 pixels for that row of the character. The code (excerpt below, full code here) is simply a big case statement to output the appropriate bits.6 This code essentially compiles into a ROM, which is implemented in the FPGA by lookup tables. case ({char, rownum}) 7'b0000000: pixels = 8'b01111100; // XXXXX 7'b0000001: pixels = 8'b11000110; // XX XX 7'b0000010: pixels = 8'b11001110; // XX XXX 7'b0000011: pixels = 8'b11011110; // XX XXXX 7'b0000100: pixels = 8'b11110110; // XXXX XX 7'b0000101: pixels = 8'b11100110; // XXX XX 7'b0000110: pixels = 8'b01111100; // XXXXX 7'b0000111: pixels = 8'b00000000; // 7'b0001000: pixels = 8'b00110000; // XX 7'b0001001: pixels = 8'b01110000; // XXX 7'b0001010: pixels = 8'b00110000; // XX 7'b0001011: pixels = 8'b00110000; // XX 7'b0001100: pixels = 8'b00110000; // XX 7'b0001101: pixels = 8'b00110000; // XX 7'b0001110: pixels = 8'b11111100; // XXXXXX ... I updated the top-level program to use the low bits of the X pixel position for the character and pixel index, and the low bits of the Y pixel position for the row index. The results can be seen below; I've magnified the text in the red box so you can see the characters. [Image]My first implementation of text. (Zoomed region in red.) Due to a bug, all the characters are backwards. Oops, I implemented the character generator with bit 7 on the left, while the pixel index values have bit 7 on the right, so the characters were displayed backwards. But a quick fix got the characters to display correctly. Generating a line of FizzBuzz Once I could display characters, I needed to provide the right characters for the FizzBuzz output. The algorithm is the same as my previous FizzBuzz program, so I'll just give the highlights here. Converting the numbers from 1 to 100 into characters is trivial on a microprocessor, but more difficult with digital logic since there's no built-in divide operation; dividing by 10 and 100 requires many logic gates. My solution was to use a binary-coded decimal (BCD) counter, using a separate 4-bit counter for each digit. The next challenge was testing if the number was divisible by 3 or 5. As with division, the modulo operation is easy on a microprocessor, but hard with digital logic. Instead of computing modulo values, I used counters for the value modulo 3 and the value modulo 5. The value modulo 3, for instance, simply counts 0, 1, 2, 0, 1, 2, ... (See the footnote for other approaches.7) A FizzBuzz output line can be up to 8 characters long. The `fizzbuzz` module (source) outputs the appropriate eight 4-bit characters as a 32-bit variable line. (The normal way to generate video would be to store all the screen's characters or pixels into video RAM, but I decided to generate everything dynamically.) An if statement (excerpt below) updates the bits of line to return "Fizz", "Buzz", "FizzBuzz" or the number as appropriate. if (mod3 == 0 && mod5 != 0) begin // Fizz line[3:0] <= CHAR_F; line[7:4] <= CHAR_I; line[11:8] <= CHAR_Z; line[15:12] <= CHAR_Z; end else if (mod3 != 0 && mod5 == 0) begin // Buzz line[3:0] <= CHAR_B; line[7:4] <= CHAR_U; line[11:8] <= CHAR_Z; line[15:12] <= CHAR_Z; ... The FizzBuzz module needed a signal to increment the counts to the next number so I modified the vga module to indicate the start of a new line and used this to move to the next number. When I tried my code, I got very strange output with alien symbols; the photo below shows a detail. [Image]Changing the character every row yields mysterious symbols, not the desired characters. The bug was that I was moving to the next FizzBuzz value after every line of pixels instead of waiting 8 lines to draw a full character. Thus, each displayed character consisted of slices from 8 different characters. Incrementing the FizzBuzz counter every 8 lines instead of every line fixed this problem, as you can see below. (Debugging VGA code is much easier than other FPGA things, since problems are visible on the screen. You don't need to poke around with an oscilloscope trying to figure out what went wrong.) [Image]The FizzBuzz output, as displayed on a VGA monitor. At this point I had the FizzBuzz output appearing on the screen, but the static display was kind of boring. Changing the foreground and background color of each row was easy—just using some bits of the Y value for the red, green and blue colors. This yielded colored text with a 1980s PC aesthetic. [Image]With the foreground and background colors based on the line, the text is more interesting. Next, I added some basic animation. The first step was to add an output from the vga module to indicate when the screen was redrawn, a new field every 60th of a second. I used this to change the colors dynamically. (Tip: don't flash the screen color every 60th of a second unless you want a headache; use a counter and change it less often.) Trying out different graphical effects is fun and addictive, since you get immediate feedback. I decided to have the "Fizz" and "Buzz" lines slide across the screen with a rainbow color trail (inspired by Nyan Cat). To do this, I changed the character's start position based on a counter. For the rainbow color effect, I selected the color based on the row number (so each row of the character could have a different color) and added the rainbow trail. [Image]A closeup of the final output. The final effect I added was giant words "Fizz" and "Buzz" that bounced around the screen. The bouncing effect was based on a bouncing invisible box (inspired by FPGA Pong) that held the word.8 A variable dx keeps track of the X direction and dy keeps track of the Y direction. On each new screen (i.e. 60 times a second), the box's X and Y coordinates are incremented or decremented based on the direction variables. If the box reaches the right or left edges, dx is toggled. Similarly, dy is toggled if the box reaches the top or bottom. The big text is then drawn inside the box using another instantiation of the character generator described earlier. The word is enlarged by a factor of 8 by dropping the three low-order bits from the coordinate. You're probably tired of Verilog code by now so I won't show the code here, but it's on github. The final result is shown in the video clip below. Hardware details For this project, I used the Mojo V3 FPGA board development board (below), which was designed to be an easy-to-use starter board. It uses an FPGA chip from Xilinx's Spartan 6 family. Although the Mojo uses one of the smallest Spartan 6 chips, the chip still contains over 9000 logic cells and 11,000 flip flops, so it can do a lot. (For other options, see this list of cheap FPGA boards.) [Image]Interfacing the FPGA board to VGA is almost trivial: just three 270&ohm; resistors. The perf board is just to attach the cable to a header. If you want to use VGA, it's easier to use a development board that includes a VGA connector. But if your board lacks a connector (like the Mojo), adding VGA is straightforward. Simply put 270&ohm; resistors between the FPGA's red, green and blue output pins and the VGA connection. The horizontal and vertical sync can be wired directly from the FPGA.9 I used Xilinx's development environment (called ISE) to write and synthesize the Verilog code. (For details on writing code and getting it onto the FPGA board, see my previous FPGA article.) To specify which physical FPGA pins to use, I added lines to the mojo.ucf configuration file. This maps the red output pin_r to pin 50 on the board, and so forth. NET "pin_r" LOC = P50 | IOSTANDARD = LVTTL; NET "pin_g" LOC = P40 | IOSTANDARD = LVTTL; NET "pin_b" LOC = P34 | IOSTANDARD = LVTTL; NET "pin_hsync" LOC = P32 | IOSTANDARD = LVTTL; NET "pin_vsync" LOC = P29 | IOSTANDARD = LVTTL; Driving VGA from an FPGA is common, so you can find lots of similar projects on the web such as FPGA Pong, 24-bit color using a DAC chip, the Basys 3 board and displaying an image. If you want a schematic, see this page. The book Programming FPGAs has a whole chapter on VGA. Understanding the VGA format The VGA video format may seem a bit strange, but looking at the history of television and the CRT (cathode ray tube) provides context. In a CRT, a beam of electrons scans across the screen, lighting up the phosphor coating to produce an image. Scanning happens in a raster pattern: the beam scans across the screen left-to-right, and then a horizontal sync pulse causes the beam to rapidly return to the left during the horizontal retrace. The process repeats line-by-line until the bottom of the screen, when a vertical sync pulse triggers vertical retrace and the beam returns to the top. During the horizontal and vertical retrace, the beam is blanked so retrace doesn't draw lines on the screen. The diagram below illustrates the raster scan pattern. [Image]Raster scan pattern for a CRT. (Wikipedia) These characteristics carried over to VGA, resulting in the horizontal and vertical sync pulses, and the long intervals during which the video must be blanked. In 1953, the NTSC standard for color television was introduced.10 VGA, however, is much simpler than NTSC since it uses five wires for the sync and color signals, instead of cramming everything into a single signal with a complex encoding. One strange feature of NTSC that carries over to VGA is the screen refresh rate isn't the claimed 60 Hertz, but actually 59.94 Hertz.11 The oscilloscope trace below shows the VGA video signals across two lines. The horizontal sync pulses (yellow) indicate the start of each line. The brief red, green and blue pulses near the start of the line are white pixels from a FizzBuzz number. The red signal near the middle of the line is the floating red word "Buzz". [Image]Oscilloscope trace of VGA signals, showing red, green, blue and horizontal sync. Conclusion Driving a VGA monitor from an FPGA was much easier than I expected, but I certainly wouldn't get hired if I encountered FizzBuzz as an FPGA interview question! If you're interested in FPGAs, I highly recommend playing around with video output. It's not much harder than blinking an LED and much more rewarding. Creating video output is also much more fun than debugging with an oscilloscope—you get immediate visual feedback and even if things go wrong, they are often entertaining. Follow me on Twitter or RSS to find out about my latest blog posts. My FPGA code is on github. Notes and references The VGA signal is supposed to have a 25.175 MHz pixel clock. Instead, I divided the Mojo board's 50 MHz clock by 2 to get a 25 MHz clock. The VGA standard says that the pixel clock must be 25.175 MHz ± 0.5%. A clock rate of 25 MHz is off by 0.7% so technically is a bit off from the spec. However, monitors are designed to handle signals generated by cheap graphics cards, so they will usually manage to display whatever you throw at them. ↩ The detailed timings for dozens of standard video resolutions can be found here. Page 17 has the 640x480 60 Hz resolution I used. ↩ When I forgot to blank the pixels outside the valid screen area, the monitor still managed to display an image, but it was very dim because the monitor got confused about what voltage represented "dark". Just a tip in case you find your display mysteriously darkened. ↩ It's kind of amazing if you think about what an LCD monitor needs to do in order to display a VGA image designed for a CRT. The monitor has to examine the incoming signals to "guess" what video resolution a computer is sending to it. Then it needs to resample the video signal to match the resolution of the LCD panel. Finally, it sends the new pixel data to the LCD. ↩ For some reason, the output was shifted down about 25 pixels. It worked fine on a different monitor, so I'm not sure if was just something with my monitor's alignment or if I had a bug. I could adjust this by making the vertical sync pulse 25 rows later. ↩ It would be tedious to type all the code for character generation, so I wrote a Python program to create the Verilog code from a font file. The original font is here. ↩ After my last FPGA FizzBuzz, people suggested some other approaches so I tried them out on the VGA project. With modulo counters (my original approach), the entire project used 276 LUTs (lookup tables) and 277 flip flops. One suggestion was to use ring counters (i.e. one shifted bit) instead of binary counters for the modulo counters. This used 277 LUTs and 281 flip flops, so slightly worse. Another suggestion was to add the digits and take the modulo 3 value. The logic to add and perform modulo brought the count to 305 LUTs, much worse. Adding the modulo 3 values (instead of digits) brought it down to 289 LUTs, still worse. ↩ The big floating words are essentially sprites—bitmaps that can be arbitrarily positioned on the screen. Sprites were popular with video games and computers in the 1970s and early 1980s such as Pacman, Atari and Commodore 64. Sprites let slow processors perform animation; instead of moving all the pixels around in memory, the processor would just update the sprite coordinates. The top-level code (source) ties together all the pieces and combines everything onto the screen: the text, the rainbow trail, the giant "Fizz" (in a rainbow pattern) and the giant "Buzz" (in red). ↩ To connect to the VGA monitor, I cut a VGA cable in half and connected its wires to the FPGA board, reusing the cable from my project to read monitor data using I2C. Don't take this approach—the tiny wires inside are difficult to solder and break easily. Instead, just use a VGA connector. The interface to VGA is simply three 270&ohm; resistors, to get the right voltages for the red, green and blue signals. You can use more resistors to get more colors, essentially building 2-bit or more A/D converters. ↩ NTSC was a remarkably clever way to introduce color, while remaining compatible with black-and-white televisions. However, it is very hard to understand. I was scared off from video by the talk of encoding color with phase and quadrature and a color subcarrier synced to a color burst signal. Because NTSC combines the color and sync signals into a single broadcast signal, the encoding is much more complex than VGA. ↩ While monitors say they have a 60 Hz refresh rate, the actual refresh rate is 59.94 Hz, a strange frequency dating back to the origins of color television. A screen refresh frequency of 60 Hz was desirable to cancel out power line interference. However, to prevent the color carrier frequency from interfering with the audio frequency, various frequencies had to be adjusted, resulting in the screen refresh frequency of 59.94 Hertz. It almost seems like numerology, but the frequency choices are explained in detail in this video and in Wikipedia. ↩