Method, apparatus, and system for reducing memory requirements for echo cancellers

• US 7,079,498 B2
• Filed: 06/14/2002
• Issued: 07/18/2006
• Est. Priority Date: 06/14/2002
• Status: Expired due to Fees

• Current Assignee: Intel Corporation
• Original Assignee: Intel Corporation
• Inventors: Ubale, Anil W.
• Primary Examiner(s): Jung, Min
• Application Number:
  US10/172,269
• Publication Number:
  US 20030231617A1
• Time in Patent Office: 1,495 Days
• Field of Search: 370/286, 370/352, 370/356, 370/401, 370/287, 379/406.01
• US Class Current: 370/286
• CPC Class Codes: H04B 3/23 using a replica of transmitted signal in the time domain, e.g. echo cancellers

Abstract

According to one embodiment of the invention, a method is provided in which a first set of coefficients is generated for performing echo cancellation in a voice-over-packet (VoP) system. Each coefficient is represented by a first number of bits which includes a first portion representing the sign of the respective coefficient and a second portion representing the magnitude of the respective coefficient. The first set of coefficients is compressed to generate a second set of coefficients which requires less memory storage than the first set of coefficients, in which coefficients which have higher values are encoded before coefficients which have lower values until a predetermined compression ratio is satisfied or until all coefficients in the first set have been encoded.

Claims

1. A method comprising:

generating a first set of coefficients, each coefficient being represented by a first number of bits, the first number of bits including a first portion representing the sign of the respective coefficient and a second portion representing the magnitude of the respective coefficient; and

compressing the first set of coefficients to generate a second set of coefficients which requires less memory storage than the first set of coefficients, wherein coefficients which have higher values are encoded before coefficients which have lower values until a predetermined compression ratio is satisfied or until all coefficients in the first set have been encoded.

2. The method of claim 1 further including:

determining a memory requirement for the first set of coefficients; and

setting a memory requirement for the second set of coefficients based on the memory requirement for the first set and the predetermined compression ratio.

3. The method of claim 1 wherein compressing the first set includes:

performing a set of operations iteratively until the predetermined compression ratio is satisfied or until all coefficients in the first set have been processed, including;

identifying those coefficients in the first set which have higher values relative to other coefficients in the first set;

encoding the identified coefficients; and

marking the coefficients in the first set that have been encoded so that they are not processed again in subsequent iterations.

4. The method of claim 3 wherein identifying includes:

traversing the first set of coefficients unit a coefficient in the first set whose most significant bit having a non-zero value is detected; and

encoding the relative position of the respective coefficient.

5. The method of claim 4 wherein encoding the identified coefficients includes:

encoding the respective coefficient with full precision in the second set of coefficients including the relative position of the respective coefficient.

6. The method of claim 5 wherein marking includes:

removing the respective coefficient from the first set.

7. The method of claim 6 wherein marking includes:

replacing the respective coefficient in the first set by a zero value.

8. A method comprising:

receiving a first array of coefficients each being represented by a first number of bits which includes a first portion representing the sign of the respective coefficient and a second portion representing the magnitude of the respective coefficient; and

performing compression operations on the first array of coefficients to obtain a second array of coefficients which requires less memory storage than the first set of coefficients, wherein coefficients in the first array which have higher values relative to other coefficients in the first array are given higher priority for being encoded in the second array.

9. The method of claim 8 further including:

determining an amount of memory that is required for storing the second array based on the size of the first array and a predetermined compression ratio.

10. The method of claim 9 wherein the first array includes a first sub-array for holding the sign data of the corresponding coefficients and a second sub-array for holding the magnitude data of the corresponding coefficients.

11. The method of claim 10 wherein performing compression operations on the first array includes:

performing a set of operations on the second sub-array iteratively starting from the most significant bit (MSB) of a first predetermined entry in the second sub-array until a first condition is met, including;

detecting whether the current bit of the current entry in the second sub-array has a non-zero value;

if the current bit has a non-zero value, encoding the corresponding coefficient in the second array; and

marking the corresponding entry in the second sub-array so that it will not be processed again.

12. The method of claim 11 wherein the first predetermined entry corresponds to the lowest indexed entry in the second sub-array.

13. The method of claim 11 wherein the first predetermined entry corresponds to the highest indexed entry in the second sub-array.

14. The method of claim 11 wherein the first condition is met when the amount of memory required for storing the second array has been reached.

15. The method of claim 11 wherein the first condition is met when all coefficients in the first array have been processed.

16. An apparatus comprising:

logic to generate a first set of coefficients, each coefficient being represented by a first number of bits, the first number of bits including a first portion representing the sign of the respective coefficient and a second portion representing the magnitude of the respective coefficient; and

logic to compress the first set of coefficients to generate a second set of coefficients which requires less memory storage than the first set of coefficients, wherein coefficients which have higher values are encoded before coefficients which have lower values until a predetermined compression ratio is satisfied or until all coefficients in the first set have been encoded.

17. The apparatus of claim 16 further including:

logic to determine a memory requirement for the first set of coefficients;

logic to determine a memory requirement for the second set of coefficients based on the memory requirement for the first set and the predetermined compression ratio.

18. The apparatus of claim 16 wherein logic to compress the first set includes:

logic to perform a set of operations iteratively until the predetermined compression ratio is satisfied or until all coefficients in the first set have been processed, including;

logic to identify those coefficients in the first set which have higher values relative to other coefficients in the first set;

logic to encode the identified coefficients; and

logic to mark the coefficients in the first set that have been encoded so that they are not processed again in subsequent iterations.

19. The apparatus of claim 18 wherein logic to identify includes:

logic to traverse the first set of coefficients unit a coefficient in the first set whose most significant bit having a non-zero value is detected; and

logic to encode the relative position of the respective coefficient.

20. An echo canceller comprising:

logic to receive a first array of coefficients each being represented by a first number of bits which includes a first portion representing the sign of the respective coefficient and a second portion representing the magnitude of the respective coefficient; and

logic to perform compression operations on the first array of coefficients to obtain a second array of coefficients which requires less memory storage than the first set of coefficients, wherein coefficients in the first array which have higher values relative to other coefficients in the first array are given higher priority for being encoded in the second array.

21. The echo canceller of claim 20 wherein logic to perform compression includes:

logic to determine an amount of memory that is required for storing the second array based on the size of the first array and a predetermined compression ratio.

22. The echo canceller of claim 21 wherein the first array includes a first sub-array for holding the sign data of the corresponding coefficients and a second sub-array for holding the magnitude data of the corresponding coefficients.

23. The echo canceller of claim 22 wherein logic to perform compression operations on the first array includes:

logic to perform a set of operations on the second sub-array iteratively starting from the most significant bit (MSB) of a first predetermined entry in the second sub-array until a first condition is met, including;

logic to detect whether the current bit of the current entry in the second sub-array has a non-zero value;

if the current bit has a non-zero value, logic to encode the corresponding coefficient in the second array; and

logic to mark the corresponding entry in the second sub-array so that it will not be processed again.

24. A system comprising:

an echo canceller coupled to perform echo cancellation with respect to input signals received from one or more channels;

a memory including a plurality of dynamic memory blocks that are used by the echo canceller to perform its corresponding functions; and

a memory controller coupled to the echo canceller and the memory, the memory controller to facilitate data transfer between the echo canceller and the memory,

wherein the echo canceller includes logic to perform compression operations on a first array of coefficients to obtain a second array of coefficients which requires less memory storage in the memory than the first set of coefficients, and wherein coefficients in the first array which have higher values relative to other coefficients in the first array are given higher priority for being encoded in the second array.

25. The system of claim 24 wherein the first array includes a first sub-array for holding the sign data of the corresponding coefficients and a second sub-array for holding the magnitude data of the corresponding coefficients.

26. The system of claim 24 wherein logic to perform compression includes:

logic to determine an amount of memory that is required in the global memory for storing the second array based on the size of the first array and a predetermined compression ratio.

27. The system of claim 25 wherein logic to perform compression operations on the first array includes:

logic to perform a set of operations on the second sub-array iteratively starting from the most significant bit (MSB) of a first predetermined entry in the second sub-array until a first condition is met, including;

logic to detect whether the current bit of the current entry in the second sub-array has a non-zero value;

if the current bit has a non-zero value, logic to encode the corresponding coefficient in the second array; and

logic to mark the corresponding entry in the second sub-array so that it will not be processed again.

28. A machine-readable medium comprising instructions which, when executed by a machine, cause the machine to perform operations including:

generating a first set of coefficients to be used for performing echo cancellation in a voice-over-packet (VoP) system, each coefficient being represented by a first number of bits, the first number of bits including a first portion representing the sign of the respective coefficient and a second portion representing the magnitude of the respective coefficient; and

compressing the first set of coefficients to generate a second set of coefficients which requires less memory storage than the first set of coefficients, wherein coefficients which have higher values are encoded before coefficients which have lower values until a predetermined compression ratio is satisfied or until all coefficients in the first set have been encoded.

29. The machine-readable medium of claim 28 further including:

determining a memory requirement for the first set of coefficients; and

setting a memory requirement for the second set of coefficients based on the memory requirement for the first set and the predetermined compression ratio.

30. The machine-readable medium of claim 28 wherein compressing the first set includes:

performing a set of operations iteratively until the predetermined compression ratio is satisfied or until all coefficients in the first set have been processed, including;

identifying those coefficients in the first set which have higher values relative to other coefficients in the first set;

encoding the identified coefficients; and

marking the coefficients in the first set that have been encoded so that they are not processed again in subsequent iterations.