PVQ Encoding/Decoding

One of the pieces of technology in the Opus audio codec (RFC 6716) is Pyramid Vector Quantization (PVQ). In PVQ is a vector quantization with an algebraic codebook. The 2 parameters to the PVQ are N and K, wherin N is the number of integers and K is the sum of integers without the sign:

# for a given vector X
N = len(X)
K = sum(abs(c) for c in X)

Choosing the nearest valid vector is comparatively easy, as validating K is rather trivial. Where things get more ghastly is, when a N,K-PVQed vector has to be coded. The process of encoding is documented in the RFC, section 5.3.8.2. PVQ Encoding:

V = lambda N, K: ....
i = 0
k = 0
j = N
while j > 0: # for j = N-1 down to 0
  j -= 1
  if k > 0: i += (V(N-j-1,k-1) + V(N-j,k-1)) // 2
  k += abs(X[j])
  if X[j] < 0: i += (V(N-j-1,k) + V(N-j,k)) // 2
# k must be K, else the vector wasn't properly quantized.
if k != K: raise Error("k!=K")
encode_mod(i, V(N,K))

Get Dat Sword’s stories in your inbox

Join Medium for free to get updates from this writer.

Remember me for faster sign in

The process of decoding is documented in the RFC, section 4.3.4.2 PVQ Decoding:

V = lambda N, K: ....
i = decode_mod(V(N,K)) # decode i so that 0 <= i < V(N,K)
k = K
X = [0 for i in range(0,N)]
for j in range(0,N):
  p = (V(N-j-1,k) + V(N-j,k)) // 2
  if i < p:
    sgn = 1
  else:
    sgn = -1
    i -= p
  k0 = k
  p -= V(N-j-1,k)
  while p > i:
    k -= 1
    p -= V(N-j-1,k)
  X[j] = sgn * (k0-k)
  i -= p

Now the hard part: The function V(N,K). This function is recursively defined as follows:

def V(N,K): # recursively compute V(N-1,K) + V(N,K-1) + V(N-1,K-1)
  if K == 0: return 1 # with V(N,0) = 1
  if N == 0: return 0 # and V(0,K) = 0, K != 0
  return V(N-1,K) + V(N,K-1) + V(N-1,K-1)

If you think about computing this function on the fly, forget it! This function is usually implemented as a lookup table.