bit::vector — Convolutions

Computes the convolution of two bit-vectors.

template<std::unsigned_integral Block, typename Allocator>
constexpr bit::vector<Block, Allocator>
1convolution(const bit::vector<Block, Allocator> &u,
            const bit::vector<Block, Allocator> &v);
1
Non-member function that returns the convolution of the two bit-vectors u and v.

If \(\mathbf{u}\) has size \(m\) and \(\mathbf{v}\) has size \(n\) then these methods 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.

One use for convolution is to do polynomial multiplication:
Interpreting \(u_i\) and \(v_i\) 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 <bit/bit.h>
int main()
{
    auto u = bit::vector<>::ones(3);
    auto v = bit::vector<>::ones(2);
    std::cout << u << " convolved with " << v << " yields " << bit::convolution(u, v) << '\n';
}

Output

[1 1 1] convolved with [1 1] yields [1 0 0 1]

Note, in terms of polynomials, we are computing the product: \[ (1 + x + x^2)(1+ x) = 1 + 2x + 2x^2 + x^3. \] However, in \(\mathbb{F}_2\), all arithmetic is mod 2, so the two middle terms are zero for all \(x\). Hence the product polynomial in \(\mathbb{F}_2\) is \(1 + x^3\) and we get the coefficients [1 0 0 1] exactly as shown.

Back to top