# US 6,952,671 B1 · Vector quantization with a non-structured codebook for audio compression

> Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt

- Number: US 6,952,671 B1
- Document ID: US6952671B1
- Status: Granted
- Kind: B1
- Application number: 09/649,143
- Filed: 2000-08-25
- Granted: 2005-10-04
- Earliest claimed: 1999-10-04
- Assignees: XVD Corporation
- Inventors: Victor Kolesnik; Boris Kudryashov; Eugeny Ovsjannikov; Sergey Petrov; Boris Trojanovsky
- Web page: https://patentgrep.com/patent/US6952671B1

## CPC

- G10L 19/07: Line spectrum pair [LSP] vocoders
- G10L: SPEECH ANALYSIS TECHNIQUES OR SPEECH SYNTHESIS; SPEECH RECOGNITION; SPEECH OR VOICE PROCESSING TECHNIQUES; SPEECH OR AUDIO CODING OR DECODING

## Abstract

According to one embodiment of the invention, a multistage vector list quantizer comprises a first stage quantizer to select candidate first stage codewords from a plurality of first stage codewords, a reference table memory storing a set of second stage codewords for each first stage codeword, and a second stage codebook constructor to generate a reduced complexity second stage codebook that is the union of sets corresponding to the candidate first stage codewords selected by the first stage quantizer.

## Claims

### Claim 1

An apparatus for audio compression comprising:
a searching unit including a non-structured codebook, said searching unit having an input to receive a source vector and an output to provide a reduced version of a non-structured codebook; and
a first quantizer having a first input coupled to receive said source vector and coupled to said output of said searching unit.

### Claim 2 (depends on 1)

The apparatus of claim 1 wherein said searching unit comprises:
said non-structured codebook with codewords broken into a plurality of overlapping sets, each of said sets being mapped to a representative codeword, said representative codewords forming a first codebook;
a second quantizer coupled to said first codebook, said second quantizer having an input to receive said source vector and having an output to provide a list identifying a subset of said representative codewords; and
a codebook constructor unit coupled to said non-structured codebook and said first quantizer to form said reduced version of said non-structured codebook.

### Claim 3

An apparatus for audio compression comprising:
a first quantizing unit having an input to receive a source vector and having an output to identify different ones of a plurality of representative codewords based on said source vector;
a storage unit having stored therein a non-structured codebook whose codewords are broken into sets, each set being mapped to a different one of said representative codewords;
a codebook constructor coupled to said first quantizing unit and said storage unit and having an output to provide a reduced version of said non-structured codebook; and
a second quantizing unit coupled to said codebook constructor and having an input to receive said source vector.

### Claim 4 (depends on 3)

The apparatus of claim 3, wherein
said codebook constructor generates said reduced version of said non-structured codebook from the union of the sets corresponding to the currently identified representative codewords.

### Claim 5 (depends on 3)

The apparatus of claim 3 wherein said sets overlap.

### Claim 6 (depends on 3)

The apparatus of claim 3, wherein said first stage quantizing unit provides at said output a list of indices for the ones of said plurality of representative codewords closest to said source vector.

### Claim 7

An apparatus for audio compression comprising:
a storage unit having stored therein a set of candidates including
a set of standard codewords; and
a set of predicted codewords;
a first stage quantizer coupled to said storage unit and having an input to receive a source vector and a new predicted codeword, said first stage quantizer having an output to generate a list of error vectors based on said candidates and said source vector and generate a list of indices of said candidates corresponding to said error vectors;
a logic unit coupled to said first stage quantizer and having an output to transmit a first subset of error vectors including each error vector from said list of error vectors with an index from said list of indices corresponding to one of said predicted codewords, and a second subset of error vectors including each error vector from said list of error vectors with an index from said list of indices corresponding to one of said standard codewords;
a first splitting unit coupled to said logic unit and having an output to generate a plurality of subvectors from said first subset of error vectors;
a second splitting unit coupled to said logic unit and having an output to generate a plurality of subvectors from said second subset of error vectors;
a plurality of multistage vector list quantizers (MSLQ), certain of said plurality of MSLQ coupled to said first splitting unit and certain of said plurality of MSLQ coupled to said second splitting unit, said plurality of MSLQ having output to generate a plurality of quantized subvectors; and
a quantizer coupled to said plurality of MSLQ and having an input to receive said source vector and having an output to generate an index from said list of indices of a best candidate and to generate a list of indices for said plurality of quantized subvectors from said plurality of MSLQ.

### Claim 8

A method of audio compression comprising:
selecting from a non-structured codebook a subset of codewords to form a reduced complexity codebook based on said source vector; and
quantizing said source vector with said reduced complexity codebook.

### Claim 9 (depends on 8)

The method of claim 8, wherein said selecting includes quantizing said source vector with a first-stage codebook, said first stage codebook having codewords based on said non-structured codebook.

### Claim 10 (depends on 8)

The method of claim 8, wherein said selecting comprises:
searching a first stage non-structured codebook for a list of codewords closest to a source vector; and
constructing the reduced complexity non-structured codebook based on said list of codewords.

### Claim 11 (depends on 10)

The method of claim 10, wherein said constructing comprises:
selecting a different set of codewords from a main non-structured codebook for each codeword identified by said list.

### Claim 12

A method of audio compression comprising:
searching a first stage non-structured codebook for a predetermined number of codewords based on a source vector;
looking up a plurality of sets of codewords in a table based on the codewords selected as the predetermined number, each set of codewords from said plurality corresponding to a different codeword in said first stage non-structured codebook;
constructing a non-structured codebook from a union of said plurality of sets of codewords; and
quantizing said source vector with said non-structured codebook.

### Claim 13 (depends on 12)

The method of claim 12 wherein said searching includes selecting as the predetermined number the codewords of said first-stage non-structured codebook that are closest to said source vector.

### Claim 14 (depends on 12)

The method of claim 12 wherein said plurality of sets of codewords overlap.

### Claim 15 (depends on 12)

The method of claim 12, wherein said quantizing includes selecting the one of said codewords in said non-structured codebook closest to said source vector.

### Claim 16

A method of audio compression comprising:
selecting from a first stage codebook a list of codewords closest to a source vector, wherein a main non-structured codebook was used to create the non-structured first stage codebook, wherein the first stage codebook has fewer codewords than the main non-structured codebook;
using said list of codewords to select a plurality of sets of codewords from the main codebook;
creating a reduced codebook from the union of said plurality of sets of codewords; and
selecting from said reduced codebook a codeword closest to said source vector.

### Claim 17 (depends on 16)

The method of claim 16 wherein each of said sets of codewords from the main codebook correspond to a different codeword from said first stage codebook.

### Claim 18 (depends on 16)

The method of claim 16 wherein said plurality of sets of codewords overlap.

### Claim 19

A method of audio compression comprising:
quantizing a source vector with a codebook comprising a set of standard codewords and a set of predicted codewords;
selecting a list of smallest error vectors based on said quantizing and a list of indices for codewords corresponding to the error vectors on said list;
splitting an error vector from said list of smallest error vectors into multiple subvectors with a first splitting unit if said error vector's index from said list of indices corresponds to one of said set of predicted codewords;
splitting an error vector from said list of smallest error vectors into multiple subvectors with a second splitting unit if said error vector's index from said list of indices corresponds to one of said set of standard codewords;
quantizing said multiple subvectors with multiple multistage vector list quantizers into multiple quantized subvectors;
selecting a best candidate based on said multiple quantized subvectors and said source vector; and
transmitting an index for said best candidate and indices for said multiple quantized subvectors.

### Claim 20 (depends on 19)

The method of claim 19 wherein each of said multiple multistage vector list quantizers utilizes a different codebook.

### Claim 21

An apparatus for audio compression comprising:
a searching unit including a non-structured codebook, said searching unit having an input to receive a source vector and an output to provide a reduced version of a non-structured codebook, said non-structured codebook with codewords broken into a plurality of overlapping sets, each of said sets being mapped to a representative codeword, said representative codewords forming a first codebook;
a first quantizer having a first input coupled to receive said source vector and a second input coupled to said output of said searching unit, and an output based on said source vector and said reduced version of said non-structured codebook;
a second quantizer coupled to said first codebook, said second quantizer having an input to receive said source vector and having an output to provide a list identifying a subset of said representative codewords; and
a codebook constructor unit coupled to said non-structured codebook and said first quantizer to form said reduced version of said non-structured codebook.

### Claim 22

An apparatus for audio compression comprising:
a first quantizing unit having an input to receive a source vector and having an output to identify different ones of a plurality of representative codewords based on said source vector;
a storage unit having stored therein a non-structured codebook whose codewords are broken into overlapping sets, each set being mapped to a different one of said representative codewords;
a codebook constructor coupled to said first quantizing unit and said storage unit and having an output to provide a reduced version of said non-structured codebook; and
a second quantizing unit coupled to said codebook constructor and having an input to receive said source vector and an output based on said reduced version of said non-structured codebook and said source vector.

### Claim 23 (depends on 22)

The apparatus of claim 22 wherein said codebook constructor generates said reduced version of said non-structured codebook from the union of the sets corresponding to the currently identified representative codewords.

### Claim 24 (depends on 22)

The apparatus of claim 22 wherein said first stage quantizing unit provides at said output a list of indices for the ones of said plurality of representative codewords closest to said source vector.

### Claim 25

A method of audio compression comprising:
searching a first stage non-structured codebook for a predetermined number of codewords;
looking up a plurality of overlapping sets of codewords in a table based on the codewords selected as the predetermined number, each set of codewords from said plurality corresponding to a different codeword in said first stage non-structured codebook;
constructing a non-structured codebook from a union of said plurality of sets of codewords; and
quantizing a source vector with said non-structured codebook.

### Claim 26 (depends on 25)

The method of claim 25 wherein said searching includes selecting as the predetermined number the codewords of said first-stage non-structured codebook that are closest to said source vector.

### Claim 27 (depends on 25)

The method of claim 25 wherein said quantizing includes selecting the one of said codewords in said non-structured codebook closest to said source vector.

### Claim 28

A method of audio compression comprising:
selecting from a first stage codebook a list of codewords closest to a source vector, wherein a main non-structured codebook was used to create the non-structured first stage codebook, wherein the first stage codebook has fewer codewords than the main non-structured codebook;
using said list of codewords to select a plurality of overlapping sets of codewords from the main codebook;
creating a reduced codebook from the union of said plurality of sets of codewords; and
selecting from said reduced codebook a codeword closest to said source vector.

### Claim 29 (depends on 28)

The method of claim 28 wherein each of said sets of codewords from the main codebook correspond to a different codeword from said first stage codebook.