CN110868223A - A Numerical Operation Implementation Method and Circuit of Huffman Coding - Google Patents

Abstract

A method for realizing numerical operation of Huffman coding provided by the present invention includes: counting the occurrence probability of each character in 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, The code length sequence of characters is referred to as the code length set for short, and the code length sequence is calculated according to the probability set and the code length set; according to the code length sequence, the Huffman code is output by numerical operation, and the character to be encoded is calculated in a particularly convenient way. The code length sequence of the set, and then sort the code length sequence to directly generate the encoding of the character set; in the case of avoiding the construction of Huffman tree, the same encoding effect as the classic Huffman paradigm encoding can be obtained, eliminating the need to construct Huffman Redundant computation and storage in the Mann tree improves coding efficiency. The invention also provides a numerical operation realization circuit of Huffman coding, the realization circuit is simple and easy to realize, and the energy consumption is low.

Description

A Numerical Operation Implementation Method and Circuit of Huffman Coding

technical field

The invention relates to the technical field of data compression, and more particularly, to a method and a circuit for realizing numerical operation of Huffman coding.

Background technique

Huffman coding is a compression coding technique that removes statistical redundancy of information sources. Taking binary coding as an example, it is coded according to the coincidence of two source words with the smallest statistical frequency (probability) as two as one.

In the classic Huffman coding method, the coding table is mainly generated by constructing a Huffman tree, or in other words, according to the index of the parent and child nodes. The existing main steps for constructing a Huffman tree and generating an encoding table are as follows:

_{1 )} Construct _a binary _tree set F _{: {} 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 two trees with the smallest root 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 the tree set F, and add the new binary tree to the tree set F.

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

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

This Huffman coding method must be realized by constructing a Huffman tree. There are a lot of redundant computations, occupying a lot of storage space, and the coding efficiency is low. The circuit implementation requires more components and is highly complex.

SUMMARY OF THE INVENTION

In order to overcome the technical defects of a large amount of calculation, a large amount of storage space and low coding efficiency in the existing Huffman coding method realized by constructing a Huffman tree, the present invention provides a numerical operation realization method of Huffman coding and circuit.

For solving the above-mentioned technical problems, the technical scheme of the present invention is as follows:

A numerical operation implementation method of Huffman coding, comprising the following steps:

S1: Count the occurrence probability of each character in the data, and obtain the character set and the corresponding probability set;

S2: Calculate the encoding length of each character in the character set of the data, abbreviating the encoding length sequence of each character as the code length set, and calculate the code length sequence according to the probability set and the code length set;

S3: According to the code length sequence, the Huffman code is output by numerical operation.

Wherein, the step S1 is specifically: to count the occurrence probability of each character in the data, to obtain the character set {s ₁ , s ₂ ,...,s _n } and the corresponding probability set {p ₁ , p ₂ ,... ,p _n }.

Wherein, 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 that the two nodes with the smallest weight actually contain 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 of 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 character number k is:

i＝2,3,L,n-1；其中，q_i的码长为m_i的二进制即表示第i个字符对应的范式哈夫曼编码。Wherein, the step S3 is specifically: packing the character set and the code length set, and sorting them according to the code length _mi from small to large, to obtain a data sequence: q ₁ =0,

i=2, 3, L, n-1; wherein, the binary code of q _i whose code length is m _i represents the normal form Huffman coding corresponding to the ith character.

A circuit for implementing a numerical operation method using Huffman coding, comprising a single-chip microcomputer, a memory, a display, an oscillation circuit, a reset circuit and an adder module; wherein:

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

The output end of the single-chip microcomputer is electrically connected with the display;

The single-chip microcomputer is electrically connected with the memory and the adder module to realize the interaction of data, and the combination of the adder module and the single-chip microcomputer is used to realize the numerical operation realization method of Huffman coding.

Wherein, 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 with the output end of the single-chip microcomputer;

The output end of the 74HC595 serial-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 single-chip microcomputer.

Wherein, the single-chip microcomputer adopts P87C51RD single-chip microcomputer.

Wherein, the memory adopts AT24C02 memory.

Wherein, the display adopts LCD4002 liquid crystal display.

In the above scheme, the 74LS283 full adder submodule is an adder composed of two 4-bit full adders, which is used to realize the code length sequence of step S23 plus 1 operation, and used to realize the k value of step S24 plus 1 operation , which is used to realize the addition operation of the parameter count in step S25, and other algorithms including matrix operation, sorting, and conversion from decimal to binary, etc., are all implemented in the single-chip microcomputer.

Compared with the prior art, the beneficial effects of the technical solution of the present invention are:

The 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 convenient way, and then sorts the code length sequence to directly generate the code of the character set; In the case of avoiding the construction of Huffman tree, the same encoding effect as the classic Huffman paradigm encoding can be obtained, the redundant calculation and storage in the construction of the Huffman tree are eliminated, and the encoding efficiency is improved; the implementation circuit is simple and easy to implement , low energy consumption.

Description of drawings

Fig. 1 is the schematic flow chart of the method of the present invention;

Fig. 2 is the schematic diagram of directly reading Huffman coding according to code length set;

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

Detailed ways

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

In order to better illustrate this embodiment, some parts of the drawings are omitted, enlarged or reduced, which do not represent the size of the actual product;

It will be understood by those skilled in the art that some well-known structures and their descriptions may be omitted from the drawings.

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

Example 1

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

S1: Count the occurrence probability of each character in the data, and obtain the character set and the corresponding probability set;

S2: Calculate the encoding length of each character in the character set of the data, call the encoding length sequence of each character a code length set for short, and calculate the code length sequence according to the probability set and the code length set;

S3: According to the code length sequence, the Huffman code is output by numerical operation.

More specifically, the step S1 is specifically as follows: the occurrence probability of each character in the data is counted to obtain the character set {s ₁ , s ₂ ,...,s _n } and the corresponding probability set {p ₁ , p ₂ ,. ..,p _n }.

Wherein, 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 that the two nodes with the smallest weight actually contain 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 of 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 the step S23, the specific expression of the character number k is:

i＝2,3,L,n-1；其中，q_i的码长为m_i的二进制即表示第i个字符对应的范式哈夫曼编码。More specifically, the step S3 is specifically: packing the character set and the code length set, and sorting them from small to large according to the code length m _i to obtain a data sequence: q ₁ =0,

i=2, 3, L, n-1; wherein, the binary code of q _i whose code length is m _i represents the normal form Huffman coding corresponding to the ith character.

在转化后的二进制不足的位数通过在前面补0的方式凑齐，例如数值0的码长为2的二进制表示为00，电路设计中可存个存入码长集的数据单元中。In the specific implementation process, in the step S3, the data unit cache of the probability set can be directly cleared; at the same time, a recursive expression of the data sequence obtained is equivalent to the general expression

After the conversion, the insufficient number of digits in the binary system is made up by adding 0 in front. For example, the binary representation of the code length of 2 of the value 0 is 00, which can be stored in the data unit of the code length set in the circuit design.

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

In the specific implementation process, as shown in FIG. 2 , it is a schematic diagram of directly reading the Huffman code according to the code length set in step S3 . Among them, when referring to the positive real axis and positive angle of polar coordinates, offset the angle from the positive real axis in turn, and pass 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 single-chip microcomputer, a memory, a display, an oscillation circuit, a reset circuit and an adder module; wherein:

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

The output end of the single-chip microcomputer is electrically connected with the display;

The single-chip microcomputer is electrically connected with the memory and the adder module to realize the interaction of data, and the combination of the adder module and the single-chip microcomputer is used to realize the numerical operation realization method of Huffman coding.

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

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

The output end of the 74HC595 serial-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 single-chip microcomputer.

More specifically, the single-chip microcomputer adopts P87C51RD single-chip microcomputer.

More specifically, the memory adopts AT24C02 memory.

More specifically, the display adopts 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 realize the code length sequence plus 1 operation in step S23, and is used to realize the k value addition in step S24. 1 operation is used to realize the addition operation of the parameter count in step S25, and other algorithms including matrix operation, sorting, and decimal conversion to binary, etc. are all implemented in the single-chip microcomputer.

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

Obviously, the above-mentioned embodiments of the present invention are only examples for clearly illustrating the present invention, rather than limiting the embodiments of the present invention. For those of ordinary skill in the art, changes or modifications in other different forms can also be made on the basis of the above description. The algorithm can also be implemented in full hardware by using full adders, half adders, shift registers, flip-flops, etc.; through FPGA, full hardware implementation is implemented in Verilog language, and it is unnecessary and impossible to list all implementations here. Any modification, equivalent replacement and improvement made within the spirit and principle of the present invention shall be included within the protection scope of the claims of the present invention.

Claims (10)

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

s1: counting the occurrence probability of each character in the data to obtain a character set and a corresponding probability set;

s2: calculating the code length of each character in the character set of the data, simply referring the code length sequence of each character to a code length set, and calculating the code length sequence according to the probability set and the code length set;

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

2. The method for implementing numerical operation of huffman coding according to claim 1, wherein the step S1 specifically comprises: counting the occurrence probability of each character in the data to obtain a character set s₁,s₂,...,s_nAnd the corresponding probability set p₁,p₂,...,p_n}。

3. The method for implementing numerical operation of huffman coding according to claim 2, wherein the step S2 specifically comprises the following steps:

s21: set the code length set corresponding to the character set as { m₁,m₂,...,m_nThe initial values are all 1;

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

s23: calculating the number k of characters essentially contained by the two nodes with the minimum weight in the process of combining two Huffman codes into one;

s24: the code length of the first k characters in the code length set is increased by 1 bit, namely m_i＝m_i+1,i＝1,2,L,k；

S25: setting an intermediate variable count p₁+p_kModifying the k data before the probability set into count;

s26: the steps S22-S25 are repeatedly executed, n-2 times are executed, and the calculation of the code length sequence is completed.

4. The method for implementing huffman coding numerical operation according to claim 3, wherein in step S23, the specific expression of the number of characters k is:

5. the method for implementing numerical operation of huffman coding according to claim 4, wherein the step S3 specifically comprises: packing the character set and the code length set and according to the code length m_iAnd (3) sequencing from small to large to obtain a data sequence: q. q.s₁＝0，

Wherein q is_iCode length of m_iThe binary system of (a) represents the normal huffman coding corresponding to the ith character.

6. A circuit for implementing a numerical operation using Huffman coding according to claim 5, comprising a single chip, a memory, a display, an oscillating circuit, a reset circuit and an adder module; wherein:

the input end of the single chip microcomputer is electrically connected with the output ends of the oscillating circuit and the reset circuit;

the output end of the single chip microcomputer is electrically connected with the display;

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

7. The huffman-coded numerical operation realization circuit of claim 6, wherein: the adder module comprises a 74HC595 serial-to-parallel submodule, a 74LS283 full adder submodule and a 74HC165 parallel-to-serial submodule; wherein:

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

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

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

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

8. The huffman-coded numerical operation realization circuit of claim 7, wherein: the single chip microcomputer is a P87C51RD single chip microcomputer.

9. The huffman-coded numerical operation realization circuit of claim 7, wherein: the memory employs AT24C02 storage.

10. The huffman-coded numerical operation realization circuit of claim 7, wherein: the display adopts an LCD4002 liquid crystal display.

Images