Adaptive Differential Pulse Code Modulation (ADPCM)

ADPCM (Adaptive Differential Pulse Code Modulation) is a lossy data compression technique used for encoding audio data. It works by predicting the next sample value based on previous samples and encoding only the difference between the predicted value and the actual value. The 'adaptive' part refers to the prediction mechanism, which dynamically adjusts itself based on the characteristics of the audio signal. This article will provide a detailed explanation of ADPCM, including its core principles, implementation, and analysis.

Fundamental Concepts / Prerequisites

To understand ADPCM, you should have a basic understanding of the following concepts:

• Pulse Code Modulation (PCM): A standard digital representation of analog signals, where the amplitude of the analog signal is sampled at regular intervals, and each sample is quantized to the nearest value within a range of digital levels.
• Differential Pulse Code Modulation (DPCM): Encodes the difference between successive samples rather than the absolute values. This exploits the correlation between adjacent samples, leading to better compression.
• Quantization: The process of mapping a continuous range of values (e.g., the difference between samples) to a discrete set of values. Quantization introduces quantization error, which is a source of loss in lossy compression.

Implementation in C

This C code snippet demonstrates a simplified ADPCM encoder and decoder.

#include <stdio.h>
#include <stdlib.h>

// ADPCM step size table
const int step_table[] = {
    7, 9, 11, 13, 16, 19, 21, 23,
    26, 29, 31, 34, 37, 41, 45, 50,
    55, 60, 66, 73, 80, 88, 97, 107,
    118, 130, 142, 156, 171, 187, 205, 225,
    246, 270, 297, 327, 360, 396, 435, 480,
    528, 580, 638, 702, 772, 849, 934, 1028,
    1131, 1244, 1368, 1505, 1656, 1822, 2004, 2205,
    2426, 2668, 2934, 3227, 3550, 3905, 4296, 4726
};

// ADPCM index adjustment table
const int index_table[] = {
    -1, -1, -1, -1, 2, 4, 6, 8,
    -1, -1, -1, -1, 2, 4, 6, 8
};

// ADPCM encoder function
int adpcm_encode(int sample, int* predicted, int* step_index) {
    int diff = sample - *predicted;
    int sign = (diff < 0) ? 8 : 0;  // Sign bit
    int abs_diff = abs(diff);
    int level = 0;
    int step = step_table[*step_index];

    // Find quantization level
    for (int i = 3; i >= 0; i--) {
        if (abs_diff >= step) {
            level |= (1 << i);
            abs_diff -= step;
        }
        step = step >> 1; // Divide step by 2
    }

    // Calculate encoded value (4 bits)
    int encoded = sign | level;

    // Update predicted value
    int delta = step_table[*step_index] * ((2 * (level & 7) + 1) / 2); // Calculate difference to add
    if (sign) delta = -delta; // Apply sign
    *predicted += delta;

    // Clip predicted value
    if (*predicted > 32767) *predicted = 32767;
    if (*predicted < -32768) *predicted = -32768;

    // Update step index
    *step_index += index_table[encoded & 0x0F]; // Update index using lower 4 bits of encoded value

    // Limit step index
    if (*step_index < 0) *step_index = 0;
    if (*step_index > 88) *step_index = 88;

    return encoded;
}

// ADPCM decoder function
int adpcm_decode(int encoded, int* predicted, int* step_index) {
    int sign = encoded & 8;
    int level = encoded & 7;
    int delta = step_table[*step_index] * ((2 * level + 1) / 2); // Calculate the increment

    if (sign) delta = -delta; //Apply sign
    *predicted += delta; //Update prediction

    // Clip predicted value
    if (*predicted > 32767) *predicted = 32767;
    if (*predicted < -32768) *predicted = -32768;


    // Update step index
    *step_index += index_table[encoded & 0x0F]; // Update index using lower 4 bits of encoded value

    // Limit step index
    if (*step_index < 0) *step_index = 0;
    if (*step_index > 88) *step_index = 88;

    return *predicted;
}

int main() {
    // Example usage
    int samples[] = {1000, 1100, 1200, 1300, 1250, 1200, 1150, 1100};
    int num_samples = sizeof(samples) / sizeof(samples[0]);
    int predicted = 0;  // Initial predicted value
    int step_index = 0; // Initial step index
    int encoded_data[num_samples];
    int decoded_data[num_samples];

    printf("Original Samples:\n");
    for (int i = 0; i < num_samples; i++) {
        printf("%d ", samples[i]);
    }
    printf("\n");

    // Encoding
    printf("Encoded Data:\n");
    for (int i = 0; i < num_samples; i++) {
        encoded_data[i] = adpcm_encode(samples[i], &predicted, &step_index);
        printf("%d ", encoded_data[i]);
    }
    printf("\n");

    // Reset for Decoding
    predicted = 0;
    step_index = 0;

    // Decoding
    printf("Decoded Data:\n");
    for (int i = 0; i < num_samples; i++) {
        decoded_data[i] = adpcm_decode(encoded_data[i], &predicted, &step_index);
        printf("%d ", decoded_data[i]);
    }
    printf("\n");

    return 0;
}

Code Explanation

The code provided above implements a simplified ADPCM encoder and decoder. Let's break down the key parts:

`step_table` and `index_table`: These are crucial for the adaptive nature of ADPCM. The `step_table` contains a set of quantization step sizes. The `index_table` is used to adjust the index into the `step_table`, effectively increasing or decreasing the quantization step size based on the encoded value. This allows the algorithm to adapt to the dynamic range of the audio signal.

`adpcm_encode(int sample, int* predicted, int* step_index)`:

1. Calculates the difference (`diff`) between the current `sample` and the `predicted` value.
2. Determines the sign of the difference and stores it in the `sign` bit.
3. Quantizes the absolute difference (`abs_diff`) using the current `step_size` from `step_table`. The `level` variable represents the quantized level.
4. Combines the `sign` and `level` to form the 4-bit `encoded` value.
5. Updates the `predicted` value based on the `encoded` value and the current `step_size`. The `delta` is added to the predicted value.
6. Clips the `predicted` value to prevent overflow.
7. Updates the `step_index` using the `index_table`, adapting the quantization step size for future samples.

`adpcm_decode(int encoded, int* predicted, int* step_index)`:

1. Extracts the `sign` and `level` from the `encoded` value.
2. Calculates the difference `delta` to be added to the current predicted value, using the `step_table` and the `level`.
3. Applies the sign to delta.
4. Updates the `predicted` value by adding delta.
5. Clips the `predicted` value to ensure it remains within the valid range.
6. Updates the `step_index` using the `index_table` for the next decoding step.

`main()`: This function demonstrates how to use the `adpcm_encode` and `adpcm_decode` functions with a sample set of data. It encodes the samples, prints the encoded data, and then decodes the data, printing the decoded samples.

Complexity Analysis

Time Complexity: The `adpcm_encode` and `adpcm_decode` functions have a time complexity of O(1). The loops inside the encoder and decoder (for finding the quantization level) iterate a fixed number of times (at most 4), independent of the input size. Therefore, each encoding and decoding operation takes constant time.

Space Complexity: The space complexity is also O(1). The algorithm uses a fixed number of variables regardless of the number of input samples. The `step_table` and `index_table` are constant-sized arrays and do not depend on the input data.

Alternative Approaches

One alternative to ADPCM is **Mu-law or A-law companding**. These are non-adaptive compression techniques that compress the dynamic range of an audio signal before PCM encoding. While simpler to implement than ADPCM, Mu-law and A-law companding are less efficient at higher compression ratios because they do not adapt to local signal characteristics. They offer less sophisticated compression compared to ADPCM's adaptive prediction.

Conclusion

ADPCM is a versatile and widely used audio compression technique that leverages the correlation between adjacent audio samples and adaptive prediction to achieve good compression ratios while maintaining acceptable audio quality. Its constant time and space complexity make it efficient for real-time applications. While alternative methods exist, ADPCM strikes a balance between complexity and performance, making it suitable for various audio encoding scenarios.