# 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-10-19. 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. Graph image by Geek3 in the public domain.

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. 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

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

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

print("// Generated by sine2fmem.py from Project F")

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 (
.data(tab_data)
);

always_comb begin
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 == 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 use this module for rotation in Animated Shapes.

### 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="",
) (
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);
end
end

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.