Dismiss
InnovationQ will be updated on Sunday, Oct. 22, from 10am ET - noon. You may experience brief service interruptions during that time.
Browse Prior Art Database

Table Lookup Algorithm for ADPCM Audio Codecs

IP.com Disclosure Number: IPCOM000008780D
Original Publication Date: 2002-Jul-11
Included in the Prior Art Database: 2002-Jul-11
Document File: 4 page(s) / 5K

Publishing Venue

Motorola

Related People

Richard Cutler: INVENTOR [+2]

Abstract

This document describes an algorithm for doing a fast table lookup in an ADPCM Codecs such as the ITU-T G.726 speech vocoder. G.726 is finding wide acceptance as a standard codec for transporting voice over packet networks such as IP, ATM, and Frame Relay. In order to be competitive, a packet telephony system must be able to operate within tight real-time constraints. The method presented here will quantize a 12-bit signal in about half the time as a binary search, uses less memory, and is time-invariant in processor uses (an important feature in real-time systems).

This text was extracted from an ASCII text file.
This is the abbreviated version, containing approximately 50% of the total text.

Table Lookup Algorithm for ADPCM Audio Codecs

Richard Cutler and Priyadarshan Kolte

Abstract:

This document describes an algorithm for doing a fast table lookup in an ADPCM Codecs such as the ITU-T G.726 speech vocoder. G.726 is finding wide acceptance as a standard codec for transporting voice over packet networks such as IP, ATM, and Frame Relay. In order to be competitive, a packet telephony system must be able to operate within tight real-time constraints.

The method presented here will quantize a 12-bit signal in about half the time as a binary search, uses less memory, and is time-invariant in processor uses (an important feature in real-time systems).

Problem:

Both small memory size and fast operation are essential in order to obtain the high channel densities required in this marketplace. A major function in the G.726 encoder and decoder is a speech quantizer. This typically involves doing costly table lookups, linear searches, binary searches, and direct table lookups.

The G.726 speech vocoder for 40 kbit/second speech quantizes values in the range -2048 to 2047 as shown in the following table. ITU-T G.726 also defines 32kbps, 24kbps and 16kbps, but only the 40kbps case will be demonstrated here as it is the most difficult to quantize.

Table 1. 40kbps quantization

Signal (d)        Quantized result (Q)

-------------     --------------------

-2048 to -123     31

-122 to -17       1

-16 to 67         2

68 to 138         3

139 to 197        4

198 to 249        5

250 to 297        6

298 to 338        7

339 to 377        8

378 to 412        9

413 to 444        10

445 to 474        11

475 to 501        12

502 to 527        13

528 to 552        14

553 to 2047       15

Direct table lookup is fast but requires one entry for each possible signal d. For each rate, 4k of memory would be required. This is generally unacceptable for DSP applications.

Linear search and binary search are two other classical methods of doing these table lookups. Binary search is the typical method of a sample DSP), available today.

Table 2. Classical Table Lookup Methods

                      Mean   Min    Max

Function Name  Memory Clocks Clocks Clocks

-------------  ------ ------ ------ ------

Direct lookup  4124   4      4      4

Linear search  80     85     5      194

Binary search  192    39     5      84

Another problem is the wide variance of clocks that the binary search takes. The scheduling of the algorithim must be built around the worst-case CPU consumption of 84 clocks.

The problem is to find a table method that is faster than a binary search, t...