27 May 2021

FPGA Sine Lookup Table

In this FPGA recipe, we’re going to look at a straightforward method for generating sine and cosine using a lookup table. There are more precise methods, but this one is fast and simple and will suffice for many applications.

This post is part of a series of handy recipes to solve common FPGA development problems. There are also posts on fixed-point numbers, division, and square root.

Updated 2021-06-28. Get in touch with @WillFlux or open an issue on GitHub.

Source

The SystemVerilog designs featured in this post are available from the Project F Library under the open-source MIT licence: build on them to your heart’s content. The rest of the blog content is subject to standard copyright restrictions: don’t republish it without permission.

Don’t Calculate, Lookup!

A lookup table can produce a result directly without complex calculation for both sine and cosine.

Sine & Cosine

Graph image by Geek3 in the public domain.

Sine Quadrants

Sine has a simple symmetry to it (see diagram above), so our table only needs to cover a quarter of a circle: 0 to 90 degrees. Our Verilog will handle a complete circle using simple adjustment for each of the four quadrants.

The following diagram shows the quadrants and how angles are measured anti-clockwise from the three o’clock position on the circle.

Sine Quadrants

Wikipedia has a summary of properties relating to the quadrants.

Generate Table

The Project F maths library includes a 64 entry sine table you can use: [sine_table_64x8.mem].

If you’re happy to use this table, you can skip ahead to Sine Table Module.

Alternatively, I’ve created a short Python script that can generate tables to your specification [sine2fmem]:

#!/usr/bin/env python3

from math import ceil, sin, pi
import sys

# math.sin works in radians: 0-90° == π/2 radians

if (len(sys.argv) > 1):
    rows = int(sys.argv[1])
else:
    rows = 256

if (len(sys.argv) > 2):
    width = int(sys.argv[2])
else:
    width = 16

print("// Generated by sine2fmem.py from Project F")
print("// Learn more at https://github.com/projf/fpgatools")

fmt_width = str(ceil(width/4))  # four bits per hex digit
fmt_string = "{:0" + fmt_width + "X}  // {:03}: sin({:.4f}) = {:.4f}"

for i in range(rows):
    val = (pi/(2*rows)) * i
    res = sin(val)
    res_scaled = round((2**width) * res)
    if res_scaled == 2**width:  # maximum value uses too many bits
        res_scaled -= 1;        # accompanying Verilog module handles this
    print(fmt_string.format(res_scaled, i, val, res))

You specify the number rows in your table and their width in bits. I strongly recommend using a power of two for the rows, so the values wrap naturally.

The sine2fmem README has more details on the workings of the script, including examples.

Sine Table Module

I’ve created a simple Verilog module that looks up the correct value, adjusting for the quadrant of the circle it falls in [sine_table.sv]:

module sine_table #(
    parameter ROM_DEPTH=64,  // number of entries in sine ROM for 0° to 90°
    parameter ROM_WIDTH=8,   // width of sine ROM data in bits
    parameter ROM_FILE="",   // sine table file to populate ROM
    parameter ADDRW=$clog2(4*ROM_DEPTH)  // full circle is 0° to 360°
    ) (
    input  wire logic [ADDRW-1:0] id,  // table ID to lookup
    output      logic signed [2*ROM_WIDTH-1:0] data  // answer (fixed-point)
    );

    // sine table ROM: 0°-90°
    logic [$clog2(ROM_DEPTH)-1:0] tab_id;
    logic [ROM_WIDTH-1:0] tab_data;
    rom_async #(
        .WIDTH(ROM_WIDTH),
        .DEPTH(ROM_DEPTH),
        .INIT_F(ROM_FILE)
    ) sine_rom (
        .addr(tab_id),
        .data(tab_data)
    );

    logic [1:0] quad;  // quadrant we're in: I, II, III, IV
    always_comb begin
        quad = id[ADDRW-1:ADDRW-2];
        case (quad)
            2'b00: tab_id = id[ADDRW-3:0];                //  I:    0° to  90°
            2'b01: tab_id = 2*ROM_DEPTH - id[ADDRW-3:0];  // II:   90° to 180°
            2'b10: tab_id = id[ADDRW-3:0] - 2*ROM_DEPTH;  // III: 180° to 270°
            2'b11: tab_id = 4*ROM_DEPTH - id[ADDRW-3:0];  // IV:  270° to 360°
        endcase
    end

    always_comb begin
        if (id == ROM_DEPTH) begin  // sin(90°) = +1.0
            data = {{ROM_WIDTH-1{1'b0}}, 1'b1, {ROM_WIDTH{1'b0}}};
        end else if (id == 3*ROM_DEPTH) begin  // sin(270°) = -1.0
            data = {{ROM_WIDTH{1'b1}}, {ROM_WIDTH{1'b0}}};
        end else begin
            if (quad[1] == 0) begin  // positive in quadrant I and II
                data = {{ROM_WIDTH{1'b0}}, tab_data};
            end else begin
                data = {2*ROM_WIDTH{1'b0}} - {{ROM_WIDTH{1'b0}}, tab_data};
            end
        end
    end
endmodule

NB. This module outputs combinational logic, so you may want to register the results depending on your design and FPGA. I may change this in future versions if it proves to be too much of a timing headache.

Test Bench

There is a Vivado test bench available in the library: [sine_table_tb.sv]. A Verilator test example will be added later.

Module Usage

The output is signed fixed-point, with twice the width of the ROM data. For example, if you have an 8-bit table, you’ll get a 16-bit signed result with eight integer and eight fractional bits (Q8.8). If you’re new to fixed point, check out Fixed Point Numbers in Verilog.

    localparam ROM_DEPTH=64;    // number of entries in sine ROM for 0° to 90°
    localparam ROM_WIDTH=8;     // width of sine ROM data
    localparam ROM_FILE="sine_table_64x8.mem";  // file to populate ROM
    localparam ADDRW=$clog2(4*ROM_DEPTH);  // full circle is 0° to 360°

    logic [ADDRW-1:0] id;  // table ID to lookup
    logic signed [2*ROM_WIDTH-1:0] data; // answer
    sine_table #(
        .ROM_DEPTH(ROM_DEPTH),
        .ROM_WIDTH(ROM_WIDTH),
        .ROM_FILE(ROM_FILE)
    ) sine_table_inst (
        .id,
        .data
    );

Practical usage is straightforward; let’s look at some examples.

Sine 30°

First, you find the id that equates to 30 degrees.

Our ROM has 64 entries covering 90°, so we want 30 x 64/90 = 21.333, which rounds to 21.

For id=21 the module returns: 00000000.01111110 == 0.492188

As you may know, sin(30) = 0.5 exactly. Out value isn’t quite right, but we can’t represent 30 degrees exactly using a power of two. You can increase your accuracy by using a larger table at the cost of more logic. However, for exact values, you’re probably better of calculating them in logic, a topic we plan to cover at a later date.

Sine -45°

How about -45°, which is equivalent to 315° (360-45)?

315 x 64/90 = 224, an exact value!

For id=224 the module returns: 11111111.01001011 == -0.707031

My HP 35s calculator gives a value of -0.707107. In this case, our accuracy is limited by using only 8-bits for the fractional part of the answer: the smallest value we can represent is 1/256 = ~0.004, so we can’t expect more than two decimal places of accuracy.

Cosine 30°

Cosine is offset from sine by 90°. Calculating cosine is as simple as subtracting the angle from 90° before determining the id.

For example, to calculate the cosine of 30°:

Subtract the angle from 90: 90-30 = 60, then convert to id: 60 x 64/90 = 42.666, which rounds to 43.

For id=43 the module returns: 00000000.11011111 == 0.871094

My HP 35s calculator gives a value of 0.8660254.

Practical Examples

We’ll be using this module in our FPGA Graphics series over summer 2021.

ROM Implementation

The sine table module loads the sine table data into an asynchronous ROM [rom_async.sv]:

module rom_async #(
    parameter WIDTH=8,
    parameter DEPTH=256,
    parameter INIT_F="",
    localparam ADDRW=$clog2(DEPTH)
    ) (
    input wire logic [ADDRW-1:0] addr,
    output     logic [WIDTH-1:0] data
    );

    logic [WIDTH-1:0] memory [DEPTH];

    initial begin
        if (INIT_F != 0) begin
            $display("Creating rom_async from init file '%s'.", INIT_F);
            $readmemh(INIT_F, memory);
        end
    end

    always_comb data = memory[addr];
endmodule

Small tables work well with rom_async. For more substantial lookup tables, block ram (BRAM) is a better choice. To use BRAM, substitute rom_sync into the design and add a clock signal. Beware of the additional cycle of latency when using BRAM.

That wraps up this recipe, but you might like to check out other FPGA recipes for tasty logic goodness.

Constructive feedback is always welcome. Get in touch with @WillFlux or open an issue on GitHub.

Sponsor Project F
If you like what I do, consider sponsoring me on GitHub.
I’ll use contributions to spend more time creating open-source FPGA designs and tutorials.

©2021 Will Green, Project F