FIR Filter

In this tutorial, we will use HazardFlow HDL to describe an FIR (finite impulse response) filter, which is very commonly used in digital signal processing applications.

Specification

The FIR filter of order N performs the following operation:

It receives input signals from the stream x and outputs the weighted sum of the most recent N+1 input signals to the stream y. It can be expressed with the following formula:

\[ y[n] = b_0 x[n] + b_1 x[n-1] + ... + b_N x[n-N] = \sum^{N}_{i=0} b_i x[n-i] \]

where \( x[n] \) and \( y[n] \) represent the input and output signals, \( N \) represents the filter order, and \( b_i \) represents the i-th filter coefficient.

For example, the IO signals of a FIR filter of order 2 with coefficients [4, 2, 3] are as follows:

For more details, please refer to Wikipedia.

Modular Design

We could represent the FIR filter of order 2 in modular way as follows:

As in the above figure, it can be divide into 3 submodules: window, weight, and sum.

window submodule:

• It serves as a sliding window, always returning the latest 3 valid input signals as an array.
• For example, if 1, 4, 3 are given as input signals, [1, 0, 0], [4, 1, 0], [3, 4, 1] will be returned as output signals.

weight submodule:

• It keeps the weight vector [b0, b1, b2] persistent throughout the program.
• It takes the input vector [v0, v1, v2] and returns the output vector [b0·v0, b1·v1, b2·v2].
• This submodule can be simply represented by a map combinator.

sum submodule:

• It takes the input vector and returns the sum of them as an output vector.

Implementation

Based on the above submodules, we can implement the FIR filter in a concise and modular way:

fn fir_filter(input: Valid<u32>) -> Valid<u32> {
    let weight = Array::<u32, 3>::from([4, 2, 3]);

    input
        .window::<3>()
        .map(|ip| ip.zip(weight).map(|(e, wt)| e * wt))
        .sum()
}

We can describe the FIR filter with window, map, and sum combinators in the HazardFlow HDL and we assume the input interface Valid<u32> is provided. Valid<u32>, which is an alias of I<ValidH<u32, ()>> is a valid interface where its payload is u32, the resolver is empty (), and its ready function always returns true. In other words, as long as the input interface's forward signal is Some(u32) at a specific clock cycle, the receiver receives a valid payload. We can interpret this input interface as a stream of signal values flowing through the wires.

window combinator:

The window combinator is defined as follows:

impl<P: Copy + Default> Valid<P> {
    fn window<const N: usize>(self) -> Valid<Array<P, N>> {
        self.fsm_map(P::default().repeat::<{ N - 1 }>(), |ip, s| {
            let ep = ip.repeat::<1>().append(s).resize::<N>();
            let s_next = ep.clip_const::<{ N - 1 }>(0);
            (ep, s_next)
        })
    }
}

It takes an Valid<P> and returns Valid<Array<P, N>>. It tracks the latest N valid input signals. The fsm_map interface combinator is provided by the HazardFlow HDL standard library. It computes the egress payload and the next state based on the ingress payload and the current state, and updates the state when the ingress tranfser happens. The initial state is defined as P::default().repeat::<{ N - 1 }>() in our example. The anonymous function is where we specify the fsm logic from the (ingress payload, current state) to the (egress payload, next state).

map combinator:

The map combinator is used to represent the weight submodule.

map(|ip| ip.zip(weight).map(|(e, wt)| e * wt))

It takes an Valid<Array<u32, N>> and returns an egress hazard interface Valid<Array<u32, N>>. It transforms the i-th element of ingress payload ip[i] into ip[i] * weight[i], and leaves the resolver as untouched. The map interface combinator is provided by the HazardFlow HDL standard library. We can interpret it as stateless version of fsm_map. In the application-specific logic in map interface combinator, we use zip and map methods for manipulating the ingress payload signal.

sum combinator:

The sum combinator is defined as follows:

impl<const N: usize> Valid<Array<u32, N>> {
    fn sum(self) -> Valid<u32> {
        self.map(|ip| ip.fold(0, |acc, e| acc + e))
    }
}

It takes an Valid<Array<u32, N>> and returns Valid<u32>. It transforms the ingress payload to sum of them. In the application-specific logic in map interface combinator, we use fold method which aggregates the data within array of signal.

You can find the implementation in fir_filter.rs.

You can generate the Verilog codes with the following commands:

# Generate a separate Verilog file for each submodule.
$ cargo run --release -- --target fir_filter --deadcode --wire-cache

# Generate an integrated Verilog file combining all submodules.
$ cargo run --release -- --target fir_filter --deadcode --wire-cache --merge