CN1747330A - Coding method of symmetric reversible long code - Google Patents

Abstract

The present invention is a coding method of a symmetrical reversible long code, which includes: step A: according to the occurrence probability of each different symbol in the data, calculate the shortest average code word length that can be obtained theoretically, and construct all codes with the The codeword with the shortest average codeword length is used as the current candidate codeword; step B: judge whether the current candidate codeword satisfies the symmetric condition, select all candidate codewords satisfying the symmetric condition as the symmetric reversible long codeword, and construct Sub-codewords of all candidate codewords that do not satisfy the symmetry condition are used as new current candidate codewords; step C: judge whether N symmetric reversible long-code codewords have been obtained through the selection process of step B, if so , then end this process, otherwise, return to step B until N symmetric reversible long code words are generated; wherein, N is the number of types of different symbols appearing in the data to be encoded, which is a natural number.

Description

A Coding Method of Symmetric Reversible Inverted Length Code

technical field

The invention belongs to the technical field of encoding in communication technology, and in particular relates to an encoding method of a symmetrical reversible reversible long code (RVLC).

Background technique

Entropy coding is the basic information source coding technology in communication technology. The use of entropy coding can change the information source from any symbol to binary form, which is convenient for communication transmission; at the same time, entropy coding uses the essential characteristics of entropy, and can fully eliminate the redundancy in the data and achieve compressed data, thereby saving communication needs The purpose of resources such as time or bandwidth. In entropy coding, variable length codes are widely used codewords, and are widely used in text, data, voice, image and video, and other media coding. For example, in still image and video coding standards, the coding system includes three parts: source image data input, DCT coder and output of compressed image data stream, wherein, DCT coder includes forward DCT transformer, quantizer and entropy The three parts of coding also include quantization table and entropy coding table. Through entropy coding and entropy coding table, entropy coding is performed on the result of motion prediction, DCT transformation and quantization of source image data, so as to eliminate data redundancy on the one hand, On the other hand, the source image data is converted into a binary form that is easy to communicate.

In the entropy coding technology, Huffman coding is a classic entropy coding method. With this method, the average code word length can be optimized, so it is the highest in terms of transmission efficiency. Therefore, in the early entropy In coding applications, this Huffman coding method is widely used. However, with the development of variable-length codes, people gradually realized that besides the coding transmission efficiency, there are many other factors that determine the pros and cons of variable-length codes in specific applications. One of the important factors is: due to the variable-length code itself characteristics and is very sensitive to bit errors. Based on this analysis, when the variable-length code is transmitted on a channel with a high bit error rate, the transmission efficiency will be significantly reduced due to its sensitivity to bit errors, which is not conducive to the realization of communication. Since the anti-error performance of the Huffman code itself is not outstanding, the transmission efficiency may be reduced due to its own sensitivity to bit errors.

In order not to reduce the transmission efficiency significantly due to the sensitivity of variable-length codes to bit errors, variable variable-length codes are currently proposed. The variable variable length code has excellent anti-error performance, so it has been adopted by recent video standards, such as H.263+, MPEG-4 and so on. Reversible variable length codes refer to variable-length codes that can be decoded in real time from both forward and backward directions; among them, being able to be decoded in real time refers to a group of codes that meet the prefix-free condition, and the prefix-free condition It means that in a group of codes, no complete codeword is the prefix of other codewords, for example, a group of instant codes C=(0, 10, 110, 111) is exactly a codeword satisfying the different prefix condition. From the above analysis, it can be obtained that a reversible long code is a codeword in which all codewords satisfy both the forward different prefix condition and the backward different prefix condition. According to whether there is symmetry in the code word itself, reversible long codes can also be divided into symmetric reversible long codes and asymmetric reversible long codes. The combination of symmetric reversible long codes and synchronization technology can achieve a lot Good decoding performance. For variable variable length codes, its working principle is:

Among all kinds of data that needs to be compressed, entropy is used to measure the amount of information contained in the incompressible part of these data; at the same time, in these data, the same symbol appears repeatedly according to different occurrence probabilities, thus forming these compressed data Redundancy in . By adopting the entropy encoding method of reversible long code, the redundancy in the data is compressed and the entropy of the data is kept unchanged. On the other hand, it achieves the purpose of compressing the data length; among them, this kind of compression is carried out in accordance with the statistical model of the data itself, which describes the occurrence probability distribution of each symbol in the data. Models with characteristics, such as exponential distribution and Poisson distribution, are common. Since this compression is based on these statistical models, it can be optimal in a statistical sense.

In the prior art, in order to construct variable variable length codes according to the occurrence probability of symbols in the data, the following two methods are usually adopted, both of which adopt the indirect construction method. First, construct according to the occurrence probability of symbols in the data Get the Huffman code, and then get the symmetric reversible long code from the Huffman code:

method one:

In this method, first construct the Huffman code according to the occurrence probability of the symbols in the data, and obtain the Huffman code tree shown in Figure 1. The tree used here is defined in discrete mathematics, graph theory and other theories An abstract graph, or understood as a data structure in a computer algorithm, is actually an inverted "tree" with the root node at the top. After obtaining the tree, use the Huffman code tree to start from the root of the tree. Convert the code word into a symmetric reversible long code from top to bottom, and obtain the code tree of the symmetric reversible long code shown in Figure 2; In the process of the code tree, it is necessary to judge whether the reversible long code condition is satisfied on each layer of the Huffman code tree, but this method does not define a high-efficiency judgment method, so, in When inspecting a candidate codeword, it is first necessary to judge whether it satisfies the symmetric condition, and if so, compare it with the selected codeword to determine whether it satisfies the forward and backward different prefix conditions. Only then can the candidate codeword be determined as the codeword in the reversible variable length code; it can be seen that this method has the following disadvantages:

(1) Since this method does not give an efficient definition of the judgment method, the above judgment process is very complicated, which will greatly increase the complexity of calculation, which is not conducive to practical application;

(2) Due to the limitations of the algorithm itself involved in this method, when judging a layer of nodes in the Huffman code tree, it will inevitably cause some nodes that meet the conditions of the variable variable length code to be mistakenly Omission, resulting in the failure of this method to make full use of short codewords, resulting in waste of short codewords, the direct consequence is to increase the average codeword length, and entropy coding should give priority to using short codes to obtain the minimum average codeword length. deviate from

(3) For symbols with the same probability of occurrence, if the constructed Huffman codes are different, the obtained symmetric reversible long codes are also different, which will cause non-uniform coding effects;

Method 2:

This method has made some improvements to method 1. For symbols with the same occurrence probability, even if the constructed Huffman codes are different, the obtained symmetric reversible long codes are still the same, and this method can also obtain smaller The average codeword length; however, since this method is an improvement over method 1, it is still impossible to completely avoid the insufficient use of short codewords, resulting in the waste of short codewords. In addition, this method still has no solution high computational complexity.

Contents of the invention

In view of this, the main purpose of the present invention is to provide a coding method of a symmetric reversible long code, which can be directly constructed according to the occurrence probability of symbols in the data to obtain a symmetric reversible long code, which can make full use of short The codeword has low computational complexity, and at the same time, the method can realize the same symmetric reversible long code for symbols with the same probability.

In order to achieve the above object, the present invention provides a kind of encoding method of symmetrical reversible long code, and this method comprises:

Step A: Calculate the theoretically obtainable shortest average codeword length according to the occurrence probability of each symbol in the data, and construct all codewords with the shortest average codeword length as current candidate codewords;

Step B: Determine whether the current candidate codeword satisfies the symmetry condition, select all candidate codewords that satisfy the symmetry condition as a symmetric reversible long codeword, and construct subcodewords of all candidate codewords that do not satisfy the symmetry condition as the current candidate codeword;

Step C: Judging whether N symmetric reversible long code words have been obtained through the selection process of step B, if yes, then end this process, otherwise, return to step B until N symmetric reversible long codes are obtained ; Wherein, N is the number of types of different symbols appearing in the data to be encoded, which is a natural number.

Wherein, the calculation in step A obtains the theoretically obtainable shortest average codeword length including:

其中，p(x)表示要进行编码的数据中各个符号所对应的发生概率，运算符号

表示不超过被运算数的最大整数。

Among them, p(x) represents the occurrence probability corresponding to each symbol in the data to be encoded, and the operation symbol

Represents the largest integer that does not exceed the operand.

Wherein, the construction described in step A has all the codewords with the shortest average codeword length as the current candidate codewords including:

Using the full permutation method, all sequences of 0 and 1 whose length is the shortest average codeword length are generated, and these sequences are used as the current candidate codewords.

Wherein, step B includes:

Step B1: Create a queue, use the shortest average codeword length described in step A as the initial codeword length of the queue, and put the current candidate codeword into the queue;

Step B2: Determine whether all the current candidate codewords in the queue meet the symmetric conditions, select all the candidate codewords that meet the symmetric conditions as symmetric reversible long code codewords, and select these candidate codewords that meet the symmetric conditions The word is deleted from the queue, and the sub-codewords of the candidate codewords that do not satisfy the symmetric condition are constructed as the current candidate codewords. After the queue is cleared, these constructed current candidate codewords are put into the queue.

Wherein, the subcodewords of all candidate codewords that do not satisfy the symmetry condition include:

Add 0 or 1 behind the candidate codeword to form a sub-codeword of the candidate codeword.

Visible, the present invention has following beneficial effect:

(1) The algorithm maximizes the use of all nodes in the shorter code length layer that satisfy the symmetry and bidirectional different header conditions, reducing the average code word length, especially under some specific symbol occurrence probability distributions, The average codeword length obtained by this algorithm is very close to the theoretical entropy, almost equal, such as exponential distribution;

(2) When the codeword is generated, there is no need to perform Huffman coding on it first, and then construct a symmetrical codeword, thereby reducing the complexity of implementation;

(3) The code word selection mechanism is greatly simplified: in the existing two algorithms at present, the complexity of implementation is very high, and after adopting the present invention, we can find that after a certain node is selected as a code word, its child nodes The corresponding codewords will no longer be considered. When the other nodes do not meet the symmetric conditions, the codewords corresponding to its child nodes will be put into the queue and judged in turn. That is to say, all the candidate codewords in the queue have automatically satisfied the different The prefix condition, we only need to discuss its symmetry.

Description of drawings

Fig. 1 is the schematic diagram of Huffman code tree;

Fig. 2 is the schematic diagram of the code tree of symmetric reversible long code;

Fig. 3 is the schematic diagram of queue of the present invention;

Fig. 4 is a flowchart for realizing the present invention.

Detailed ways

The present invention relates to a coding method of a symmetrical reversible long code. The reversible long code is a symmetrical reversible long code. The method of the present invention is directly constructed according to the occurrence probability of symbols in data to obtain a symmetrical reversible code. Variable length codes, the method has definite rules for selecting variable variable length codes, and its computational complexity is low. In addition, due to the inherent characteristics of the algorithm used in this method, it can make full use of the short codeword length, thus conforming to the fundamental principle that entropy coding should use short codewords first to obtain the minimum average codeword length. In addition, for the same occurrence probability symbol, this method can construct the same variable variable length code.

The present invention will be described in detail below in conjunction with the accompanying drawings.

In the present invention, introduce this concept of queue, queue is the terminology in the data structure, is the linear table of a kind of operation restriction, and Fig. 3 shows the schematic diagram of a queue, wherein, a _i is an element in the queue, The queue only allows insertion (entry) at the end of the queue and deletion (exit) at the head.

The present invention first obtains a code tree according to the occurrence probability of symbols in the data, and the code tree is similar to the Huffman code tree shown in FIG. 1 .

Before the present invention constructs the reversible length code, it is first necessary to determine the number N of different symbols appearing in the data to be coded, where N is a natural number, and then realize the construction of the reversible length code through the steps shown in Figure 4 code:

Step 400:

Construct a queue and calculate the initial codeword length of the queue. The queue is used to complete the construction of the reversible long code. The initial codeword length of the queue is calculated by the following method:

By the distribution of the occurrence probability of each symbol in the data, calculate the theoretically obtainable shortest average codeword length, then, use the shortest average codeword length as the initial codeword length of the formation; in the present invention, adopt the formula ( 1) Calculate the shortest average codeword length:

运算符号

表示不超过被运算数的最大整数；Formula 1):

calculating signs

Indicates the largest integer not exceeding the operand;

This formula is a shorthand formula, each source symbol corresponds to a probability of occurrence, denoted by p(x), x represents each symbol in the source; this formula represents the shortest code that can be achieved by entropy coding in information theory Long, Huffman coding can reach this optimal lower limit; the average code length of any other entropy coding will not be lower than this value. Therefore, for our variable variable length code here, its average code length must be higher than this value; therefore, it is appropriate to use this value as the initial code length;

Step 401: Construct all codewords with the initial codeword length of the queue described in step 400, and then put these constructed codewords into the queue as current candidate codewords; wherein, in the embodiment of the present invention, the following The method implements the construction codeword described in this step:

Let the initial codeword length of the queue be L _Initial , adopt the method of full arrangement, under the condition that the codeword length is L _Initial , perform full arrangement on the binary code 0 and 1, and obtain all 0s whose length is L _Initial , 1 sequence, so as to construct the codeword with the length of the initial codeword of the queue; wherein, different codewords with the length of the initial codeword of the queue have 2 ^LInitial ;

Steps 400 to 401 realize the process of constructing and initializing the queue, so as to obtain a queue with the theoretically obtainable shortest average codeword length as the initial codeword length of the queue; wherein, refer to the subsequent steps, because the queue process is The process that the length of the output code word increases, that is to say, in the present invention, construct the short code word first, then construct the long code word, therefore, the initialization process of queue needs to determine the shortest code length as the initial code word length; In the present invention , enqueue all candidate codewords with a length of L _Initial , that is, the L _Initial in the code tree obtained according to the occurrence probability of symbols in the data. All nodes on the layer are stored in the queue as the initial state of the queue, thereby realizing the initialization of the queue;

Steps 402 to 405: judge whether all the current candidate codewords in the queue satisfy the symmetric condition, select all the codewords satisfying the symmetric condition among these candidate codewords as symmetric reversible long codewords, and select All the codewords that do not meet the symmetric conditions in these candidate codewords are constructed to obtain the sub-codewords of these codewords that do not meet the symmetric conditions. After the original queue is cleared, these newly constructed sub-codewords are put into the current candidate codewords as the current candidate codewords. queue;

Wherein, the codewords to be selected in the present invention need to satisfy the symmetric condition and the different prefix condition respectively. After adopting the above-mentioned queue operation rules, it can be found that the candidate codewords entering the team all satisfy the different prefix condition. List the way of enqueuing. If and only if all the parent codewords of a candidate codeword are not in the queue, the candidate codeword can be selected into the queue. Therefore, any prefix of the candidate codeword is not a queue The middle codeword satisfies the different prefix condition; therefore, for the candidate codeword, it is not necessary to judge whether the different prefix condition is satisfied, but only needs to judge whether it is symmetrical, thereby greatly simplifying the complexity of calculation;

Step 406: Judging whether all the N symbols have been allocated to qualified codewords, if so, then end the process and construct a symmetric reversible long code, otherwise, skip to step 402 until all symbols have been allocated to the qualified codeword.

The above descriptions are only preferred embodiments of the present invention, and are not intended to limit the present invention. Any modifications, equivalent replacements, improvements, etc. made within the spirit and principles of the present invention shall be included in the scope of the present invention. within the scope of protection.

Claims (5)

1, a kind of coding method of symmetric form reversible long code is characterized in that, this method comprises:

Steps A: be compressed the probability of happening of each symbol in the coded data as required, calculate the shortest average code length, construct all have this code word of short average code length as current candidate codewords;

Step B: judge whether current candidate codewords satisfies symmetric condition, all candidate codewords that satisfy symmetric condition are selected not satisfy the subcode word of all candidate codewords of Symmetry Condition as current candidate codewords as symmetric form reversible long code code word and structure;

Step C: judge whether to have obtained N symmetric form reversible long code code word by the selection course of step B, if, process ends then, otherwise, step B returned, until obtaining N symmetric form reversible long code code word; Wherein, N is natural number for carrying out occurring in the coded data species number of distinct symbols.

2, method according to claim 1 is characterized in that, the described the shortest average code length that can obtain in theory that calculates of steps A comprises:

Wherein, p (x) indicates to carry out the pairing probability of happening of each symbol in the data of compressed encoding; Oeprator

Expression is no more than the maximum integer of operand.

3, method according to claim 1 is characterized in that, the described structure of steps A all have this code word of short average code length comprise as current candidate codewords:

Utilize full method of arranging, produce all length and be 0,1 sequence of described the shortest average code length, with these sequences as described current candidate codewords.

4, method according to claim 1 is characterized in that, step B comprises:

Step B1: create a formation,, described current candidate codewords is put into this formation with the initial code word length of steps A the shortest described average code length as this formation;

Step B2: all the current candidate codewords in this formation are judged whether to satisfy symmetric condition respectively, all candidate codewords that satisfy symmetric condition are selected as symmetric form reversible long code code word, and these candidate codewords that satisfy symmetric condition are deleted from formation, the subcode word of constructing the candidate codewords that does not satisfy symmetric condition is as current candidate codewords, after emptying formation, these current candidate codewords that construct are put into formation.

According to claim 1 or 4 described methods, it is characterized in that 5, the subcode word that described structure does not satisfy all candidate codewords of Symmetry Condition comprises:

Add 0 or 1 in the back of described candidate codewords, form the subcode word of described candidate codewords.

Images