What Is a Compression Algorithm?

A compression algorithm refers to an algorithm for data compression. It is also often referred to as signal coding in the electronics and communications fields, and includes two steps of compression and reduction (or decoding and encoding).

A compression algorithm refers to an algorithm for data compression. It is also often referred to as signal coding in the electronics and communications fields, and includes two steps of compression and reduction (or decoding and encoding).

Because the data volume of multimedia signals is huge, it needs to be compressed; at the same time, because there is various redundancy in multimedia data, it can be compressed.

There are many compression methods for multimedia data, which can be divided into different types according to their main characteristics.

(1) Non-destructive and lossy

1. Lossless compression: It can reconstruct the compressed data without distortion and accurately restore the original data. It can be used in occasions that require strict data accuracy, such as compression of executable files and ordinary files, compression of disks, and compression of multimedia data. The compression of this method is relatively small. Such as differential coding, RLE, Huffman coding, LZW coding, arithmetic coding.

2. Lossy compression: There is distortion, and the original data cannot be recovered completely and accurately. The reconstructed data is only an approximation of the original data. It can be used in occasions where the accuracy of the data is not high, such as the compression of multimedia data. The compression of this method is relatively large. For example, predictive coding, audio coding, fractal compression, wavelet compression, JPEG / MPEG.

(2) Symmetry

If the complexity of the codec algorithm is similar to the time required, it is a symmetric encoding method, and most compression algorithms are symmetric. But there are also asymmetries, which are generally difficult to encode and easy to decode, such as Huffman encoding and fractal encoding. However, the encoding method used for cryptography is the opposite. It is easy to encode, and it is very difficult to decode.

(3) Inter-frame and intra-frame

In video coding, both intra-frame and inter-frame coding methods are used. Intra-frame coding refers to a coding method that is independently completed within a frame of image. It is the same as the coding of still images, such as JPEG. Inter-frame coding requires reference Frames can be encoded and decoded, and temporal redundancy between frames is considered during the encoding process, such as MPEG.

(4) Real-time

In some multimedia applications, you need to process or transmit data in real time (such as on-site digital recording and video recording, MP3 / RM / VCD / DVD playback, video / audio on demand, network live broadcast, video phone, video conference), coding Generally requires a delay of 50ms. This requires simple / fast / efficient algorithms and high-speed / complex CPU / DSP chips.

(5) Classification processing

Some compression algorithms can simultaneously process multimedia data with different resolutions, different transmission rates, and different quality levels, such as JPEG2000, MPEG-2 / 4.

Compression algorithm entropy coding and hybrid coding

Entropy encoding (Entropy Encoding) is a type of lossless encoding of non-semantic data streams that is compressed using data statistics. Information entropy is the average amount of information (a measure of uncertainty) of the source. Common entropy codes are RLE, LZW, Shannon, Huffman, and Arithmetic coding.

Hybrid coding is a combination of entropy coding and (signal) source coding. Most compression standards use hybrid coding to compress data. Generally, source coding is used for lossy compression, and then entropy coding is used for further lossless compression.

Compression algorithm source coding

(Signal) Source Coding is a type of lossy coding that uses the correlation and redundancy of the original signal data in the time and frequency domains to compress it. There are many types, which can be further divided into the following types.

1. Predictive coding: Use the previous and limited data to predict the next or subsequent data adjacent in time or space, so as to achieve the purpose of compression. Such as incremental modulation (DM), differential and adaptive coding (ADPCM);

2. Transform coding: Various mathematical transformation methods are used to transform the data in the original time or space domain to the frequency domain or other domains, and the redundancy of the data in the transformation domain or the characteristics of human perception is used for compression. Common transform codes are FFT (Fast Fourier Transform), DCT (Discrete Cosine Transform), DWT (Discrete Wavelet Transform), and IFS (Iterative Function System);

3. Hierarchical coding: divide the original data into several sub-regions in the space-time or frequency domain, use human-sensing features to compress and encode, and then merge them, such as binary bit, sub-sampling, and sub-band coding; ^[1]