`GF2::Vector` — Convolve Two Bit-Vectors

Computes the convolution of two bit-vectors.

template<std::unsigned_integral Block, typename Allocator>
constexpr bool
convolution(const Vector<Block, Allocator> &u,
            const Vector<Block, Allocator> &v);

If \(\mathbf{u}\) has size \(m\) and \(\mathbf{v}\) has size \(n\) then this method will return a bit-vector \(\mathbf{w}\) of size \(m+n-1\) whose elements are given by the formula

\[w_k = \sum_j u_j v_{k - j + 1}.\]

The sum is over all values of \(j\) such that the indices for \(u\) and \(v\) in that formula are valid.

In the case of bit-vectors, products are replaced by logical AND, and sums by the logical XOR operation.

Interpretation

One use for convolution is polynomial multiplication.
So if \(u_i\) and \(v_i\) are interpreted as the polynomial coefficients

\[\begin{align} u(x) &= u_0 + u_1 x + \cdots + u_{m-1} x^{m-1} \\ v(x) &= v_0 + v_1 x + \cdots + v_{n-1} x^{n-1} \end{align}\]

then the \(w_k\) are the coefficients for the product polynomial

\[ u(x) v(x) \equiv w(x) = w_0 + w_1 x + \cdots + w_{m+n-1} x^{m+n-1}.\]

Example

#include <GF2/GF2.h>
int main()
{
    GF2::Vector<> u("111");
    GF2::Vector<> v("11");
    std::cout << u << " convolved with " << v << " yields " << GF2::convolution(u, v) << '\n';
}

Output

111 convolved with 11 yields 1001  (1)

1 Thinking in terms of polynomials we are computing the product \((1 + x + x^2)(1+ x)\) which is \(1 + 2x + 2x^2 + x^3\). However, in GF(2) all arithmetic is mod 2 so the two middle terms are zero for all \(x\).
Hence the product polynomial in GF(2) is actually \(1 + x^3\) and thus we do get the coefficients 1001 just as shown.

GF2::Vector — Convolve Two Bit-Vectors

`GF2::Vector` — Convolve Two Bit-Vectors