CN110868223B - Numerical operation implementation method and circuit for Huffman coding - Google Patents

Abstract

The invention provides a method for realizing numerical operation of Huffman coding, which comprises the following steps: counting the occurrence probability of each character in the data to obtain a character set and a corresponding probability set; calculating the coding length of each character in the character set of the data, and calculating the coding length sequence of each character to be simply called a code length set according to the probability set and the code length set; according to the code length sequence, huffman codes are output in a numerical operation mode, the code length sequence of a character set to be coded is calculated in a particularly simple mode, then the code length sequences are ordered, and codes of the character set are directly generated; under the condition of avoiding constructing the Huffman tree, the same coding effect as that of classical Huffman form coding is obtained, redundant calculation and storage in constructing the Huffman tree are eliminated, and the coding efficiency is improved. The invention also provides a Huffman coding numerical operation realization circuit, which is simple and easy to realize and has low energy consumption.

Description

A numerical operation implementation method and circuit for Huffman coding

Technical field

The present invention relates to the field of data compression technology, and more specifically, to a numerical operation implementation method and circuit for Huffman coding.

Background technique

Huffman coding is a compression coding technology that removes statistical redundancy from the source. Taking binary coding as an example, it is coded based on the two source words with the smallest statistical frequency (probability) matching two to one.

In the classic Huffman coding method, it mainly relies on building a Huffman tree, or generating a coding table based on the index of parent and child nodes. The existing main steps to construct a Huffman tree and generate a coding table are as follows:

1) Construct a binary tree set F according to the character set to be encoded {s ₁ , s ₂ , L, s _n } and their probabilities (frequencies) {p ₁ , p ₂ , L, p _n }: {T ₁ , T ₂ , L,T _n }, where there is only one weighted root node in the tree T _i , and its probability is equal to the probability of the corresponding character _si .

2) Find the two trees with the smallest root node probability in the tree set F, and use them as the left and right subtrees to construct a new binary tree. The probability of the root node of the new binary tree is the sum of the root node probabilities of its left and right subtrees.

3) Delete these two trees in tree set F and add the new binary tree to tree set F.

4) Repeat steps 2) and 3) until there is only one tree left in the tree set F. This tree is the Huffman tree.

5) Traverse the entire tree from top to bottom and output the coding table.

This Huffman coding method must be implemented by constructing a Huffman tree. It involves a lot of redundant calculations, takes up a lot of storage space, and has low coding efficiency. Its circuit implementation requires a lot of components and is highly complex.

Contents of the invention

In order to overcome the technical defects of the existing Huffman coding method implemented by constructing a Huffman tree, which has a large amount of calculation, takes up a large amount of storage space and has low coding efficiency, the present invention provides a numerical operation implementation method of Huffman coding. and circuits.

In order to solve the above technical problems, the technical solutions of the present invention are as follows:

A numerical operation implementation method for Huffman coding, including the following steps:

S1: Statistics the occurrence probability of each character in the data, and obtains the character set and the corresponding probability set;

S2: Calculate the coding length of each character in the character set of the data, refer to the coding length sequence of each character as the code length set, and calculate the code length sequence based on the probability set and the code length set;

S3: According to the code length sequence, the Huffman code is output through numerical operations.

Among them, the step S1 is specifically: counting the occurrence probability of each character in the data, and obtaining the character set {s ₁ , s ₂ ,..., s _n } and the corresponding probability set {p ₁ , p ₂ ,... ,p _n }.

Among them, the step S2 specifically includes the following steps:

S21: Set the code length set corresponding to the character set to {m ₁ , m ₂ ,..., m _n }, and the initial values are all 1;

S22: Pack the character set, probability set, and code length set, and sort them in ascending order of probability p _i ;

S23: Calculate the number of characters k actually contained in the two nodes with the smallest weight in the process of combining each Huffman code into one;

S24: Increase the code length of the first k characters in the code length set by 1 bit, that is, m _i = m _i +1, i = 1, 2, L, k;

S25: Set an intermediate variable count=p ₁ +p _k , and modify the first k data in the probability set to count;

S26: Repeat steps S22-S25 for n-2 times to complete the calculation of the code length sequence.

Wherein, in the step S23, the specific expression of the number of characters k is:

Among them, the step S3 is specifically: package the character set and the code length set, and sort them according to the code length m _i from small to large to obtain the data sequence: q ₁ =0, i=2,3,L,n-1; among them, the binary code length of q _i is m _i , which represents the normal form Huffman code corresponding to the i-th character.

A circuit that implements a numerical operation method using Huffman coding, including a microcontroller, a memory, a display, an oscillation circuit, a reset circuit and an adder module; wherein:

The input terminal of the single-chip microcomputer is electrically connected to the output terminals of the oscillation circuit and the reset circuit;

The output end of the microcontroller is electrically connected to the display;

The single-chip computer is electrically connected to the memory and adder module to realize data interaction, and the adder module is combined with the single-chip computer to realize the numerical operation implementation method of Huffman coding.

Among them, the adder module includes 74HC595 serial-to-parallel sub-module, 74LS283 full adder sub-module and 74HC165 parallel-to-serial sub-module; wherein:

The input end of the 74HC595 serial-to-parallel sub-module is electrically connected to the output end of the single-chip microcomputer;

The output end of the 74HC595 series-to-parallel sub-module is electrically connected to the input end of the 74LS283 full adder sub-module;

The output end of the 74LS283 full adder sub-module is electrically connected to the input end of the 74HC165 parallel-to-serial sub-module;

The output end of the 74HC165 parallel-to-serial sub-module is electrically connected to the microcontroller.

Among them, the single-chip computer adopts P87C51RD single-chip computer.

Among them, the memory uses AT24C02 memory.

Among them, the display adopts LCD4002 liquid crystal display.

In the above scheme, the 74LS283 full adder sub-module is an 8-bit adder composed of two 4-bit full adders, which is used to implement the code length sequence addition operation of step S23 and the k value addition operation of step S24. , used to implement the addition operation of parameter count in step S25. The remaining algorithms including matrix operations, sorting, decimal to binary conversion, etc. are all implemented in the microcontroller.

Compared with the existing technology, the beneficial effects of the technical solution of the present invention are:

The present invention provides a numerical operation implementation method and circuit for Huffman coding, which calculates the code length sequence of the character set to be encoded in a particularly simple way, and then sorts the code length sequence to directly generate the encoding of the character set; While avoiding the construction of a Huffman tree, the same coding effect as the classic Huffman paradigm coding is obtained, the redundant calculation and storage in the construction of the Huffman tree are eliminated, and the coding efficiency is improved; the implementation circuit is simple and easy to implement , low energy consumption.

Description of the drawings

Figure 1 is a schematic flow diagram of the method according to the present invention;

Figure 2 is a schematic diagram of directly reading the Huffman code according to the code length set;

Figure 3 is a schematic diagram of circuit connection according to the present invention.

Detailed ways

The drawings are for illustrative purposes only and should not be construed as limitations of this patent;

In order to better illustrate this embodiment, some components in the drawings will be omitted, enlarged or reduced, which does not represent the size of the actual product;

It is understandable to those skilled in the art that some well-known structures and their descriptions may be omitted in the drawings.

The technical solution of the present invention will be further described below with reference to the accompanying drawings and examples.

Example 1

As shown in Figure 1, a numerical operation implementation method for Huffman coding includes the following steps:

S1: Statistics the occurrence probability of each character in the data, and obtains the character set and the corresponding probability set;

S2: Calculate the coding length of each character in the character set of the data, refer to the coding length sequence of each character as the code length set, and calculate the code length sequence based on the probability set and the code length set;

S3: According to the code length sequence, the Huffman code is output through numerical operations.

More specifically, the step S1 is: counting the occurrence probability of each character in the data, and obtaining the character set {s ₁ , s ₂ ,..., s _n } and the corresponding probability set {p ₁ , p ₂ ,. ..,p _n }.

Among them, the step S2 specifically includes the following steps:

S21: Set the code length set corresponding to the character set to {m ₁ , m ₂ ,..., m _n }, and the initial values are all 1;

S22: Pack the character set, probability set, and code length set, and sort them in ascending order of probability p _i ;

S23: Calculate the number of characters k actually contained in the two nodes with the smallest weight in the process of combining each Huffman code into one;

S24: Increase the code length of the first k characters in the code length set by 1 bit, that is, m _i = m _i +1, i = 1, 2, L, k;

S25: Set an intermediate variable count=p ₁ +p _k , and modify the first k data in the probability set to count;

S26: Repeat steps S22-S25 for n-2 times to complete the calculation of the code length sequence.

More specifically, in step S23, the specific expression of the number of characters k is:

More specifically, the step S3 is as follows: package the character set and code length set, and sort them according to the code length m _i from small to large to obtain the data sequence: q ₁ =0, i=2,3,L,n-1; among them, the binary code length of q _i is m _i , which represents the normal form Huffman code corresponding to the i-th character.

In the specific implementation process, the data unit cache of the probability set can be directly cleared in step S3; at the same time, a recursive expression of the data sequence is obtained, which is equivalent to a general expression The insufficient number of digits in the converted binary is made up by adding 0 in front. For example, the binary representation of the value 0 with a code length of 2 is 00. In the circuit design, one data unit can be stored in the code length set.

In the specific implementation process, the present invention provides a numerical operation implementation method for Huffman coding, which calculates the code length sequence of the character set to be encoded in a particularly simple way, and then sorts the code length sequence to directly generate characters. Encoding of sets; while avoiding the construction of a Huffman tree, the same encoding effect as the classic Huffman paradigm encoding is obtained, the redundant calculation and storage in the construction of the Huffman tree is eliminated, and the encoding efficiency is improved.

In the specific implementation process, as shown in Figure 2, it is a schematic diagram of directly reading the Huffman code according to the code length set in step S3. When referring to the positive real axis and positive angle of the polar coordinates, the angles are shifted from the positive real axis in sequence, and through each code length, it is determined that a set of prefix codes can be obtained.

Example 2

More specifically, on the basis of Embodiment 1, a circuit for implementing a numerical operation method using Huffman coding is provided, including a microcontroller, a memory, a display, an oscillation circuit, a reset circuit and an adder module; wherein:

The input terminal of the single-chip microcomputer is electrically connected to the output terminals of the oscillation circuit and the reset circuit;

The output end of the microcontroller is electrically connected to the display;

The single-chip computer is electrically connected to the memory and adder module to realize data interaction, and the adder module is combined with the single-chip computer to realize the numerical operation implementation method of Huffman coding.

More specifically, the adder module includes 74HC595 serial-to-parallel sub-module, 74LS283 full adder sub-module and 74HC165 parallel-to-serial sub-module; wherein:

The input end of the 74HC595 serial-to-parallel sub-module is electrically connected to the output end of the single-chip microcomputer;

The output end of the 74HC595 series-to-parallel sub-module is electrically connected to the input end of the 74LS283 full adder sub-module;

The output end of the 74LS283 full adder sub-module is electrically connected to the input end of the 74HC165 parallel-to-serial sub-module;

The output end of the 74HC165 parallel-to-serial sub-module is electrically connected to the microcontroller.

More specifically, the microcontroller adopts P87C51RD microcontroller.

More specifically, the memory uses AT24C02 memory.

More specifically, the display uses an LCD4002 liquid crystal display.

In the specific implementation process, the 74LS283 full adder submodule is an 8-bit adder composed of two 4-bit full adders, which is used to implement the code length sequence addition operation of step S23 and the k value addition operation of step S24. 1 operation is used to implement the addition operation of the parameter count in step S25. The remaining algorithms including matrix operations, sorting, decimal to binary, etc. are all implemented in the microcontroller.

In the specific implementation process, the implementation circuit is simple and easy to implement and has low energy consumption.

Obviously, the above-mentioned embodiments of the present invention are only examples to clearly illustrate the present invention, and are not intended to limit the implementation of the present invention. For those of ordinary skill in the art, other different forms of changes or modifications can be made based on the above description. This algorithm can also be fully implemented in hardware by using full adders, half adders, shift registers, flip-flops, etc.; through FPGA, full hardware implementation can be achieved in Verilog language. It is not necessary and impossible to exhaustively list all implementation methods here. Any modifications, equivalent substitutions and improvements made within the spirit and principles of the present invention shall be included in the protection scope of the claims of the present invention.

Claims (8)

1. The method for realizing the numerical operation of the Huffman code is characterized by comprising the following steps of:

s1: counting the occurrence probability of each character in the data to obtain a character set and a corresponding probability set; the method comprises the following steps: counting the occurrence probability of each character in the data to obtain a character setAnd the corresponding probability set->；

S2: calculating the coding length of each character in the character set of the data, and calculating the coding length sequence of each character to be simply called a code length set according to the probability set and the code length set; the method specifically comprises the following steps:

s21: setting the code length set corresponding to the character set asThe initial values are all 1;

s22: packing character set, probability set and code length set according to probabilitySequencing from small to large;

s23: in the process of calculating the two-in-one of each Huffman code, the character number substantially contained by two nodes with minimum weight is calculated；

S24: before the code length is concentratedThe code length of the individual characters is increased by 1 bit, i.e. +.>；

S25: setting an intermediate variableBefore the probability set>Data modification to->；

S26: repeating the stepsS22-S25, execution ofSecondly, completing the calculation of the code length sequence;

s3: and outputting Huffman codes in a numerical operation mode according to the code length sequence.

2. The method for realizing Huffman encoded numerical operations according to claim 1, wherein in the step S23, the character number isThe specific expression is: />。

3. The method for implementing the numerical operation of huffman coding according to claim 2, wherein the step S3 is specifically: packing character set and code length set according to code lengthSequencing from small to large to obtain a data sequence: />，The method comprises the steps of carrying out a first treatment on the surface of the Wherein (1)>Is +.>Binary meaning +.>And (5) carrying out a normal form Huffman coding corresponding to the individual characters.

4. A circuit for implementing a numerical operation method using huffman coding according to claim 3, comprising a single chip microcomputer, a memory, a display, an oscillating circuit, a reset circuit and an adder module; wherein:

the input end of the singlechip is electrically connected with the output end of the oscillating circuit and the reset circuit;

the output end of the singlechip is electrically connected with the display;

the singlechip is electrically connected with the memory and the adder module to realize data interaction, and the adder module and the singlechip are combined to realize the numerical operation realization method of Huffman coding.

5. The huffman-coded numerical operation realization circuit according to claim 4, wherein: the adder module comprises a 74HC595 serial-parallel sub-module, a 74LS283 full adder sub-module and a 74HC165 parallel-serial sub-module; wherein:

the input end of the 74HC595 serial-parallel sub-module is electrically connected with the output end of the singlechip;

the output end of the 74HC595 serial-parallel sub-module is electrically connected with the input end of the 74LS283 full adder sub-module;

the output end of the 74LS283 full adder sub-module is electrically connected with the input end of the 74HC165 parallel-serial sub-module;

the output end of the 74HC165 parallel-serial sub-module is electrically connected with the singlechip.

6. The huffman-coded numerical operation realization circuit according to claim 5, wherein: the singlechip adopts a P87C51RD singlechip.

7. The huffman-coded numerical operation realization circuit according to claim 5, wherein: the memory employs an AT24C02 memory.

8. The huffman-coded numerical operation realization circuit according to claim 5, wherein: the display employs an LCD4002 liquid crystal display.