Pyramid vector quantization

As a form of vector quantization, PVQ defines a codebook of M quantization points, each of which is assigned an integer codeword from 0 to M−1. The goal of the encoder is to find the codeword of the closest vector, which the decoder must decode back into a vector.

The PVQ codebook consists of all N-dimensional points ${\displaystyle {\vec {p}}}$ with integer-only coordinates whose absolute values sum to a constant K (i.e. whose L1-norm equals K). In set-builder notation:

${\displaystyle S(N,K)=\left\{{\vec {p}}\in \mathbb {Z} ^{N}:\left\|{\vec {p}}\right\|_{1}=K\right\}}$

where ${\displaystyle \left\|{\vec {p}}\right\|_{1}}$ denotes the L1-norm of ${\displaystyle {\vec {p}}}$.

As it stands, the set S tesselates the surface of an N-dimensional pyramid. If desired, we may reshape it into a sphere by "projecting" the points onto the sphere, i.e. by normalizing them:

${\displaystyle S_{\text{sphere}}(N,K)=\left\{{\frac {\vec {p}}{\left\|{\vec {p}}\right\|_{2}}}:{\vec {p}}\in S(N,K)\right\}}$

where ${\displaystyle \left\|{\vec {p}}\right\|_{2}}$ denotes the L2-norm of ${\displaystyle {\vec {p}}}$.

Increasing the parameter K results in more quantization points, and hence typically yields a more "accurate" approximation of the original unit vector ${\displaystyle {\vec {v}}}$ at the cost of larger integer codewords that require more bits to transmit.

import itertools
import math
from typing import List, NamedTuple, Tuple


class PVQEntry(NamedTuple):
    codeword: int
    point: Tuple[int, ...]
    normalizedPoint: Tuple[float, ...]


def create_pvq_codebook(n: int, k: int) -> List[PVQEntry]:
    """
    Naive algorithm to generate an n-dimensional PVQ codebook
    with k pulses.
    Runtime complexity: O(k**n)
    """
    ret = []
    for p in itertools.product(range(-k, k + 1), repeat=n):
        if sum(abs(x) for x in p) == k:
            norm = math.sqrt(sum(x ** 2 for x in p))
            q = tuple(x / norm for x in p)
            ret.append(PVQEntry(len(ret), p, q))

    return ret


def search_pvq_codebook(
    codebook: List[PVQEntry], p: Tuple[float, ...]
) -> Tuple[PVQEntry, float]:
    """
    Naive algorithm to search the PVQ codebook. Returns the point in the
    codebook that's "closest" to p, according to the Euclidean distance.)
    """
    ret = None
    min_dist = None
    for entry in codebook:
        q = entry.normalizedPoint
        dist = math.sqrt(sum((q[j] - p[j]) ** 2 for j in range(len(p))))
        if min_dist is None or dist < min_dist:
            ret = entry
            min_dist = dist

    return ret, min_dist


def example(p: Tuple[float, ...], k: int) -> None:
    n = len(p)
    codebook = create_pvq_codebook(n, k)
    print("Number of codebook entries: " + str(len(codebook)))
    entry, dist = search_pvq_codebook(codebook, p)
    print("Best entry: " + str(entry))
    print("Distance: " + str(dist))


phi = 1.2
theta = 5.4
x = math.sin(phi) * math.cos(theta)
y = math.sin(phi) * math.sin(theta)
z = math.cos(phi)
p = (x, y, z)
example(p, 2)
example(p, 5)
example(p, 20)

The PVQ codebook can be searched in ${\displaystyle O(KN)}$.[4] Encoding and decoding can likewise be performed in ${\displaystyle O(KN)}$ using ${\displaystyle O(K+N)}$ memory.[5]

The codebook size obeys the recurrence[4]

${\displaystyle V(N,K)=V(N-1,K)+V(N,K-1)+V(N-1,K-1)}$

with ${\displaystyle V(N,0)=1}$ for all ${\displaystyle N\geq 0}$ and ${\displaystyle V(0,K)=0}$ for all ${\displaystyle K\neq 0}$.

A closed-form solution is given by[6]

${\displaystyle V(N,K)=2N\cdot {}_{2}F_{1}(1-K,1-N;2;2).}$

where ${\displaystyle {}_{2}F_{1}}$ is the hypergeometric function.

• Vector quantization
• ACELP
• Opus (audio format)