Differential Pulse Code Modulation

An extension of pulse code modulation which differentially encodes the data to increase transmission efficiency, differential PCM (DPCM) is used in many image and video compression algorithms, including JPEG.

The principle behind differential pulse code modulation is that the source data is likely to be an analogue signal, which is likely to change in amplitude quite gradually; there are unlikely to be any large jumps in amplitude over a short time. Therefore, the signal can be efficiently represented by an initial value, and incremental deltas against this value thereafter. Since these differences are likely to be small, fewer bits may be used to encode such a signal, and therefore throughput may be increased.

For the given sampled signal:

A 9|           #
m 8|           #
p 7|           # #
l 6|         # # #             #
i 5|       # # # #           # #
t 4|     # # # # # #         # #
u 3|     # # # # # # #     # # #
d 2|   # # # # # # # #   # # # #
e 1| # # # # # # # # #   # # # #
  0 ---------------------------->
                Time

the sampled values are 1, 2, 4, 5, 6, 9, 7, 4, 3, 0, 2, 3, 5, 6. Encoded using standard pulse code modulation, this data set would require ceil(log₂(9))¹ = 4 bits per sample.

Notice, however, that the delta between two samples is never less than -3 or greater than +3. This gives a range of 7 values, which can be encoded in ceil(log₂(7))¹ = 3 bits per sample. If the encoding scheme used was differential pulse code modulation, the output would be:

 ------------------------------------------------------
| Source    | 1  2  4  5  6  9  7  4  3  0  2  3  5  6 |
| Prev. Out | 0  1  2  4  5  6  9  7  4  3  0  2  3  5 |
 ------------------------------------------------------
| Delta     | 1  1  2  1  1  3 -2 -3 -1 -3  2  1  2  1 |
 ------------------------------------------------------

In a more generous case, where the source signal's peak amplitude is higher, and the average differences are lower, differential PCM becomes far more efficient than PCM. However, it can be a lossy encoding method: in the case given, should a delta of more than ±3 occur in the source, the differential pulse code modulation output will not be able to represent it accurately.

However, differential PCM need not necessarily be lossy. If a scheme is chosen such that the largest possible difference is encodable, the signal may be fully and accurately reconstituted. This is counter-intuitive: allowing for differences of this magnitude makes DPCM even less efficient than vanilla PCM! It is possible, however, to use Shannon-Fano encoding or run length encoding to encode signals which have unequally likely deltas in a more efficient manner than PCM: the more common changes are encoded with fewer bits, and so the average length of a symbol is lower.

Differential pulse code modulation is used in the JPEG image compression algorithm to compress the DC component of each 8x8 block after the "quantization" step. For images with large blocks of similar colour, as most photographs have, this is a highly efficient method of compression.

¹: The minimum number of bits required to encode N values is log₂(N), rounded up; therefore, ceil(log₂(N)).

Sources:

Digital Compression and Coding of Continuous-Tone Still Images (JPEG standard), ITU Recommendation T.81, CCITT
Introduction to Communication Systems, Ferrel G. Stremler, Addison-Wesley
Data Communications and Networks: An Engineering Approach, Irvine & Harle, Wiley