CN1535021A - Information entropy preserving coding method and device - Google Patents

Abstract

The invention discloses an encoding method and device for maintaining information entropy. The two-dimensional joint information entropy-preserving variable-length coding for variables X ₁ and X ₂ is realized by searching the two-dimensional code table. If there is a combination of code words and input information in the code table {X ₁ =x _n , X ₂ =y _m } one-to-one correspondence, use this code word to encode the input information combination; otherwise, use a control code word to identify the input information combination, and use other methods to encode the input information combination. The invention improves the coding method for the combination of input information that cannot be coded directly by looking up a table. The results show that this method has higher compression efficiency than traditional methods. The present invention is mainly applied in an encoder for performing two-dimensional joint information entropy preserving variable length coding on digital signals, and can also be extended to the application of multidimensional joint information entropy preserving variable length coding. The invention is especially suitable for image or video compression coding.

Description

Information entropy preserving coding method and device

Technical field

The invention relates to the technical field of electrical digital data processing, in particular to an information entropy preserving encoding method and device.

Background technique

The two-dimensional joint information entropy-preserving variable-length coding of the variables X ₁ and X ₂ is often realized by looking up the two-dimensional code table. When the value range of variables X ₁ and X ₂ is very large, if the two-dimensional information combination {X ₁ , X ₂ } is used for one-to-one correspondence with code words, the two-dimensional code table will be very large, which is not conducive to storage and search. The usual method is to use a look-up table to implement encoding for the information combination {X ₁ , X ₂ } with a high probability of occurrence, and to obtain a control code word by looking up the table for the combination {X ₁ , X ₂ } with a low probability of occurrence. This control code word is only used to mark that the encoding of the event cannot be directly realized by looking up the table, and the information of X ₁ and X ₂ will be carried by other symbols immediately after the control code word.

For the {X ₁ , X ₂ } combination that cannot be coded directly by looking up the table, the commonly used coding method is to code X ₁ and X ₂ separately in sequence after the control codeword. This encoding device is shown in Figure 1. The signals X ₁ and X ₂ are input to the table look-up device, and the code words obtained by the table look-up are output. When the output code word is a control code word, the control signal makes the switch turn down, otherwise, the control signal makes the switch turn up. When the switch is turned down, it means that X ₁ and X ₂ cannot be coded directly by looking up the table. At this time, the three signals of the control code word, X ₁ and X ₂ must be successively transmitted through the time division multiplexing device. The disadvantage of this method is that the correlation between X ₁ and X ₂ is not utilized, and the control code word is only used as a mark, and does not carry some information about X ₁ or X ₂ . This leads to the fact that when the event cannot be encoded directly by looking up the table, three symbols—control codeword, X ₁ , X ₂ —are needed to complete the encoding of X ₁ and X ₂ , and the compression efficiency is not high.

Contents of the invention

The purpose of the present invention is to provide an information entropy preserving encoding method and device with higher information compression efficiency. Improvement is put forward on the encoding method and device of the small probability signal {X ₁ =x _n , X ₂ =y _m } that occurs during the two-dimensional joint variable-length encoding _{of the} variables X 1 and X 2 and cannot be directly encoded by looking up the table .

In order to achieve the above object, the technical scheme adopted in the present invention is as follows:

1. An information entropy-preserving coding method, comprising checking the input signal {X ₁ =x _n , X ₂ =y _m } into a two-dimensional variable-length coding table, if there is a code word corresponding to the input signal one-to-one in the code table, Then use the code word to encode the input signal, if there is no code word corresponding to the input signal one by one, use a unified control code word to identify the input signal; if the input signal {X ₁ =x _n , X ₂ =y _m } is identified by the control codeword, the encoding steps are as follows:

1) Combining the information obtained by mapping _X1 through the function f(x) and the information obtained by mapping _X2 through the function g(x) and the control codeword into a first composite signal;

2) Combining the information obtained by mapping _X1 through the function u(x) and the information obtained by mapping _X2 through the function v(x) into a second synthetic signal;

3) Serially output the first composite signal and the second composite signal.

Combining the information obtained by mapping X ₁ through the function f(x) and the information obtained by mapping X ₂ through the function g(x) and the control codeword into the first composite signal, the method is as follows:

The first composite signal=control codeword+f(X ₁ )+g(X ₂ ),

Among them, f(x) is a function whose independent variable is X ₁ , and g(x) is a function whose independent variable is X ₂ .

The information that X ₁ is mapped through function u(x) and the information that X ₂ is mapped through function v(x) is combined into the second composite signal, the method is as follows:

Second composite signal = v(X ₂ )-u(X ₁ ),

Among them, u(x) is a function whose independent variable is X ₁ , and v(x) is a function whose independent variable is X ₂ .

The said serial output of the first composite signal and the second composite signal means outputting the first composite signal and the second composite signal in sequence to form a coded stream.

2. A device for information entropy preserving encoding method, comprising:

A table look-up device for checking the input signal {X ₁ =x _n , X ₂ =y _m } into a two-dimensional code table; and:

1) an information synthesis device that combines the information obtained by mapping _X1 through the function f(x) and the information obtained by mapping _X2 through the function g(x) and the control codeword into a first composite signal;

2) Combining the information obtained by mapping _X1 through the function u(x) and the information obtained by mapping _X2 through the function v(x) into a residual information encoding device for the second composite signal;

3) A time-division multiplexing device that sequentially outputs the first composite signal and the second composite signal.

Said information synthesis device includes:

1) a first mapping device (601) for realizing the function f(x);

2) A second mapping device (602) for realizing the function g(x);

3) adding means (605) for constructing the first composite signal;

The signal X ₁ is input into the first mapping device (601); the first mapping device (601) is connected with the adding device (605) as an input of the adding device (605); the signal X ₂ is input into the second mapping device (602); Two mapping devices (602) are connected with the addition device (605) as an input of the addition device (605); the control code word is connected with the addition device (605) as an input of the addition device (605); the addition device (605) A first synthesized signal is output.

Said residual information encoding device includes:

1) a third mapping device (603) for realizing the function u(x);

2) a fourth mapping device (604) for realizing the function v(x);

3) Subtraction device (606);

The signal X ₁ is input to the third mapping device (603); the third mapping device (603) is connected to the subtraction device (606) as an input of the subtraction device (606); the signal X ₂ is input to the fourth mapping device (604); The four-mapping means (604) is connected to the subtracting means (606) as an input to the subtracting means (606); the subtracting means (606) outputs the second composite signal.

Said time-division multiplexing device (607) uses the first composite signal and the second composite signal as two inputs of the time-division multiplexing device (607), and the time-division multiplexing device (607) time-division serializes these two signals output.

Compared with the background technology, the present invention has beneficial effects: the method utilizes the correlation between X ₁ and X ₂ , and at the same time modifies the control code word so that it carries partial information of X ₁ and X ₂ . The result shows: the present invention divides the information of X ₁ , X ₂ into two parts and codes, wherein a part is added on the control code word; The number of bits required like this is less than the traditional method separately for 3 parts of symbols - control code word, X ₁ , X ₂ - the number of bits required for encoding, thereby overcoming the shortcomings of the traditional method. The present invention is mainly applied in an encoder that performs two-dimensional joint information entropy preserving variable length coding on digital signals, and can also be extended to multidimensional joint information entropy preserving variable length coding.

Description of drawings

Fig. 1 is the coding device block diagram of traditional method;

Fig. 2 is the functional block diagram of device of the present invention;

Fig. 3 is a structural block diagram of components of the device of the present invention.

Detailed ways

In the process of compressing and encoding image data and video data, the one-dimensional coefficients after transformation, quantization and scanning are composed of n (n≥0) 0s and one non-zero coefficient appearing alternately. The value of a non-zero coefficient is level, and the number of coefficients whose value is 0 before the non-zero coefficient is called the run length run. Coding of transformed and quantized scanned coefficients is often implemented through {run, level} two-dimensional joint coding. The present invention is suitable for performing two-dimensional joint information entropy-preserving variable-length coding on the signal {run=x _n , level=y _m }, and the following is an embodiment of the present invention:

Example 1

1. A kind of information entropy keeps encoding process, comprises the following steps:

1) Input the input signal {run=x _n , level=y _m } into the table look-up device, look up the two-dimensional variable-length code table, if there is a code word corresponding to the input signal one-to-one in the code table, use the code word to code For the input signal, if there is no code word corresponding to the input signal one by one, a unified control code word is used to identify the input signal;

2) If the input signal {run=x _n , level=y _m } is identified by the control codeword, the encoding steps are as follows: input run into the information obtained by mapping the function f(x) into the first mapping device 601 and input level into the first mapping device 601 The information mapped by the second mapping means 602 through the function g(x) and the control codeword are combined into the first composite signal through the addition means 605;

The information obtained by mapping run into the third mapping device 603 through the function u(x) and the information obtained through the mapping of level into the fourth mapping device 604 through the function v(x) is combined into a second composite signal through the subtraction device 606;

The first composite signal and the second composite signal are serially output through the time division multiplexing device 607 .

2. As mentioned in the first point, input run into the first mapping device 601 through the function f(x) to map the information and level into the second mapping device 602 through the function g(x) to map the information and the control code word Adding device 605 is combined into the first synthetic signal, and the method is as follows:

控制码字为59。First composite signal=control codeword+f(x _n )+g(y _m ), where f(x)=2*x,

The control code word is 59.

3. As mentioned in the first point, the information obtained by mapping run into the third mapping device 603 through the function u(x) and the information obtained through the mapping of level into the fourth mapping device 604 through the function v(x) are combined through the subtraction device 606 into The second synthetic signal, the method is as follows:

The second composite signal=v(ym ₎ -u(x _n ), wherein the function realized by the function u(x _n ) is to find |y _l | for run=x _n , so that {run=x _n , level=|y _l |} cannot be coded by looking up a table but {run=x _n , level=|y _l |-1} can be coded by looking up a table, then u(x _n )=|y _l |; where the function v(x) = |y _m |.

4. As mentioned in the first point, the first composite signal and the second composite signal are serially output through the time-division multiplexing device 607, that is, the first composite signal and the second composite signal are sequentially output through the time-division multiplexing device 607 to form a coded code flow.

Example 2

1. A kind of information entropy keeps coding method, comprises the following steps:

1) Input the input signal {run=x _n , level=y _m } into the table look-up device, look up the two-dimensional variable-length code table, if there is a code word corresponding to the input signal one-to-one in the code table, use the code word to code For the input signal, if there is no code word corresponding to the input signal one by one, a unified control code word is used to identify the input signal;

2) If the input signal {run=x _n , level=y _m } is identified by the control codeword, the encoding steps are as follows:

The information obtained by mapping run into the first mapping device 601 through the function f(x) and the information obtained through the mapping of level into the second mapping device 602 through the function g(x) is combined with the control code word through the adding device 605 to form the first synthesis Signal;

The information obtained by mapping run into the third mapping device 603 through the function u(x) and the information obtained through the mapping of level into the fourth mapping device 604 through the function v(x) is combined into a second composite signal through the subtraction device 606;

The first composite signal and the second composite signal are serially output through the time division multiplexing device 607 .

2. As mentioned in the first point, input run into the first mapping device 601 through the function f(x) to map the information and level into the second mapping device 602 through the function g(x) to map the information and the control code word Adding device 605 is combined into the first synthetic signal, and the method is as follows:

The first composite signal=control codeword+f(x _n )+g(y _m ),

in The control code word is 59.

3. As mentioned in the first point, the information obtained by mapping run into the third mapping device 603 through the function u(x) and the information obtained through the mapping of level into the fourth mapping device 604 through the function v(x) are combined through the subtraction device 606 into The second synthetic signal, the method is as follows:

Second composite signal = v(y _m )-u(x _n ),

in

4. As mentioned in the first point, the first composite signal and the second composite signal are serially output through the time-division multiplexing device 607, that is, the first composite signal and the second composite signal are sequentially output through the time-division multiplexing device 607 to form a coded code flow.

The above-mentioned device for improving information entropy and maintaining variable-length coding compression efficiency can use a processor system, a microcontroller, a programmable logic device or a hardware circuit to realize part or all of the operations. Some of the operations described above can be implemented in software, while others can be implemented in hardware.

For convenience, these operations are described as different interconnected functional units or as different software modules. However, this is not necessary. In some applications, these functional units or modules may be integrated into a single logic device, program or operation without sharp boundaries. In any case, the functional units and software modules or described features may be implemented independently or in hardware or software together with other operations.

Claims (8)

1. a comentropy keeps coding method, comprises input signal { X ₁=x _n, X ₂=y _mLook into the two-dimensional variable length coding schedule, if exist in the code table and input signal code word one to one, then use this codeword coding input signal; If do not exist and input signal code word one to one, then with a unified control code sign knowledge input signal; It is characterized in that if input signal { X ₁=x _n, X ₂=y _mBe Controlled code word sign, then coding step is as follows:

1) with X ₁Information and X through function f (x) mapping gained ₂Information through function g (x) mapping gained is combined into first composite signal with the control code word;

2) with X ₁Information and X through function u (x) mapping gained ₂Information through function v (x) mapping gained is combined into second composite signal;

3) with first composite signal, second composite signal serial output.

2. a kind of comentropy according to claim 1 keeps coding method, it is characterized in that: said with X ₁Information and X through function f (x) mapping gained ₂Information through function g (x) mapping gained is combined into first composite signal with the control code word, and method is as follows:

First composite signal=control code word+f (X ₁)+g (X ₂),

Wherein, f (x) is that independent variable is X ₁Function, g (x) is that independent variable is X ₂Function.

3. a kind of comentropy according to claim 1 keeps coding method, it is characterized in that: said with X ₁Information and X through function u (x) mapping gained ₂Information through function v (x) mapping gained is combined into second composite signal, and method is as follows:

Second composite signal=v (X ₂)-u (X ₁),

Wherein, u (x) is that independent variable is X ₁Function, v (x) is that independent variable is X ₂Function.

4. a kind of comentropy according to claim 1 keeps coding method, it is characterized in that: said with first composite signal, second composite signal serial output, form encoding code stream.

5. a kind of comentropy according to claim 1 keeps the device of coding method, comprises input signal { X ₁=x _n, X ₂=y _mLook into the table look-up device of two-dimentional code table; It is characterized in that:

1) with X ₁Information and X through function f (x) mapping gained ₂Shine upon the information of gained and the information synthesizer that the control code word is combined into first composite signal through function g (x);

2) with X ₁Information and X through function u (x) mapping gained ₂Be combined into the remaining information code device of second composite signal through the information of function v (x) mapping gained;

3) export the TDMD time division multiplex device of first composite signal, second composite signal successively.

6. a kind of comentropy according to claim 5 keeps the device of coding method, and it is characterized in that: said information synthesizer comprises:

1) is used to realize first mapping device (601) of function f (x) function;

2) be used to realize second mapping device (602) of function g (x) function;

3) be used to construct the adder (605) of first composite signal;

Signal X ₁Import first mapping device (601); First mapping device (601) links to each other with adder (605), as an input of adder (605); Signal X ₂Import second mapping device (602); Second mapping device (602) links to each other with adder (605), as an input of adder (605); The control code word links to each other with adder (605), as an input of adder (605); Adder (605) output first composite signal.

7. a kind of comentropy according to claim 5 keeps the device of coding method, it is characterized in that said remaining information code device, comprising:

1) is used to realize the 3rd mapping device (603) of function u (x) function;

2) be used to realize the 4th mapping device (604) of function v (x) function;

3) substracting unit (606);

Signal X ₁Import the 3rd mapping device (603); The 3rd mapping device (603) links to each other with substracting unit (606), as an input of substracting unit (606); Signal X ₂Import the 4th mapping device (604); The 4th mapping device (604) links to each other with substracting unit (606), as an input of substracting unit (606); Substracting unit (606) output second composite signal.

8. a kind of comentropy according to claim 5 keeps the device of coding method, it is characterized in that: said TDMD time division multiplex device (607), with two inputs as TDMD time division multiplex device (607) of first composite signal, second composite signal, TDMD time division multiplex device (607) is with these two signal timesharing serials outputs.

Images