Vector quantizer based on N-dimensional spatial dichotomy

• US 20070122048A1
• Filed: 01/25/2006
• Published: 05/31/2007
• Est. Priority Date: 11/16/2005
• Status: Active Grant

• Current Assignee: Atmel Corporation (Microchip Technology Incorporated)
• Original Assignee: Atmel Corporation (Microchip Technology Incorporated)
• Inventors: Fievet, Sebastien
• Granted Patent: US 7,729,553 B2
• Time in Patent Office: Days
• US Class Current: 382/253
• CPC Class Codes: G06F 18/24323 Tree-organised classifiers
• CPC Class Codes: H03M 1/066 by continuously permuting the elements used, i.e. dynamic element matching
• CPC Class Codes: H03M 1/0668 the selection being based on the output of noise shaping circuits for each element
• CPC Class Codes: H03M 3/464 Details of the digital/analogue conversion in the feedback path
• CPC Class Codes: H03M 3/502 Details of the final digital/analogue conversion following the digital delta-sigma modulation
• CPC Class Codes: H03M 7/3008 by averaging out the errors, e.g. using dither

Abstract

A method and system for quantizing a vector corresponding to an input signal is described. The vector has a plurality of components corresponding to an N-dimensional space. In one aspect, the method and system include recursively dividing the space into equal spaces having one dimension less than a previous recursion until end spaces are formed. Each end space is two-dimensional. The method and system also include asynchronously comparing the components in each end space to determine a sub-space of a particular end space having a closest match to the vector. In another aspect, the method and system include providing tree(s) including a plurality of nodes and asynchronously traversing the tree(s) to determine a closest match to the vector. The nodes correspond to ANDs of comparisons between the components. Each comparison determines whether a first component is greater than a second component.

Claims

1. A method for quantizing a vector corresponding to an input signal, the vector having a plurality of components corresponding to an n-dimensional space comprising:

recursively dividing the n-dimensional space into a plurality of equal spaces having one dimension less than a previous recursion until a plurality of end spaces is formed, each of the plurality of end spaces being two-dimensional; and

asynchronously comparing the plurality of components in each of the plurality of end spaces to determine a sub-space of a particular end space of the plurality of end spaces having a closest match to the vector.

2. A method for quantizing a vector corresponding to an input signal, the vector having a plurality of components corresponding to an N-dimensional space comprising:

providing at least one tree including a plurality of nodes, the plurality of nodes corresponding to a plurality of ANDs of a plurality of comparisons between each of the plurality of components, each of the plurality of comparisons determining whether a first component of the plurality of components is greater than a second component of the plurality of components; and

asynchronously traversing the at least one tree to determine a closest match to the vector.

3. The method of claim 2 wherein the plurality of components including N components, wherein a comparison of the plurality of comparisons is C_k=u₁>

u_j where k=an integer from 0 to N(N−

1)/2−

1, i and j=integers from 0 to N−

1 and i is not equal j; and

barC_k=u_i<

u_j.

4. The method of claim 3, the at least one tree providing further includes:

providing a plurality of sub-trees, a first portion of the plurality of sub-trees searching a first portion of the plurality of components including an M greatest of the plurality of components, a second portion of the plurality of sub-trees searching a second portion of the plurality of components including an N-M smallest of the plurality of components.

5. The method of claim 4 wherein each of a portion of the plurality of nodes corresponding to the first portion of the plurality of sub-trees includes a comparison for node n, gtu_x-1[n]=AND(C_k, barC_k).

6. The method of claim 5 wherein each of a portion of the plurality of nodes corresponding to the second portion of the plurality of sub-trees includes a comparison for node n, ltu_x-1[n]=AND(C_k, barC_k).

7. The method of claim 6 further comprising:

providing an output vector having components V[i]=OR(ltu_k), where i=an integer from zero to (N−

1)/2−

1 and k=is an integer from zero to x−

1 and V[i]=OR(gtu_k), where i=an integer from (N−

1)/2 to N−

1 and k=is an integer from zero to x−

1, and x is a level of the at least one tree.

8. A system for quantizing a vector corresponding to an input signal, the vector having a plurality of components corresponding to an N-dimensional space comprising:

at least one tree including a plurality of nodes, the plurality of nodes corresponding to a plurality of ANDs of a plurality of comparisons between each of the plurality of components, each of the plurality of comparisons determining whether a first component of the plurality of components is greater than a second component of the plurality of components; and

logic for asynchronously traversing the at least tree to determine a closest match to the vector.

9. The system of claim 8 wherein the plurality of components including N components, wherein a comparison of the plurality of comparisons is C_k=u_i>

u_j where k=an integer from 0 to M(M−

1)/2−

1, i and j=integers from 0 to N−

1 and i is not equal j; and

barC_k=u_i<

u_j.

10. The system of claim 9 wherein the at least one tree further includes:

a plurality of sub-trees, a first portion of the plurality of sub-trees searching a first portion of the plurality of components including an M greatest of the plurality of components, a second portion of the plurality of sub-trees searching a second portion of the plurality of components including an N-M smallest of the plurality of components.

11. The system of claim 10 wherein each of a portion of the plurality of nodes corresponding to the first portion of the plurality of sub-trees includes a comparison for node n, gtu_x-1[n]=AND(C_k, barC_k).

12. The system of claim 11 wherein each of a portion of the plurality of nodes corresponding to the second portion of the plurality of sub-trees includes a comparison for node n, ltu_x-1[n]=AND(C_k, barC_k).

13. The system of claim 12 wherein the system further provides an output vector having components V[i]=OR(ltu_k), where i=an integer from zero to (N−

1)/2−

1 and k=is an integer from zero to x−

1 and V[i]=OR(gtu_k), where i=an integer from (N−

1)/2 to N−

1 and k=is an integer from zero to x−

1, where x is a level of the at least one tree.

14. A mismatch shaping engine comprising:

a scalar to vector converter;

a vector quantizer coupled with the scalar to vector converter, the vector quantizer idling at least one tree and logic, the at least one tree including a plurality of nodes, the plurality of nodes corresponding to a plurality of ANDs of a plurality of comparisons between each of the plurality of components, each of the plurality of comparisons determining whether a first component of the plurality of components is greater than a second component of the plurality of components, the logic for asynchronously traversing the at least one tree to determine a closest match to the vector;

a loop filter coupled with the vector quantizer; and

a vector to scalar converter coupled with the loop filter.