CN107797541A - The light decompression algorithm of image file based on ZigBee firmware upgrades in smart home environment - Google Patents
The light decompression algorithm of image file based on ZigBee firmware upgrades in smart home environment Download PDFInfo
- Publication number
- CN107797541A CN107797541A CN201710758394.0A CN201710758394A CN107797541A CN 107797541 A CN107797541 A CN 107797541A CN 201710758394 A CN201710758394 A CN 201710758394A CN 107797541 A CN107797541 A CN 107797541A
- Authority
- CN
- China
- Prior art keywords
- decoding
- node
- array
- pathfinding
- child nodes
- Prior art date
- Legal status (The legal status is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the status listed.)
- Granted
Links
- 230000006837 decompression Effects 0.000 title claims abstract description 30
- 238000000034 method Methods 0.000 claims abstract description 18
- 230000008569 process Effects 0.000 claims description 10
- 238000013507 mapping Methods 0.000 claims description 6
- 238000005516 engineering process Methods 0.000 abstract description 10
- 238000013461 design Methods 0.000 abstract description 8
- 238000007906 compression Methods 0.000 abstract description 7
- 230000006835 compression Effects 0.000 abstract description 7
- 230000005540 biological transmission Effects 0.000 abstract description 2
- 238000002474 experimental method Methods 0.000 abstract description 2
- 230000009467 reduction Effects 0.000 abstract description 2
- 238000004364 calculation method Methods 0.000 description 4
- 230000006870 function Effects 0.000 description 3
- 238000005457 optimization Methods 0.000 description 3
- 230000003044 adaptive effect Effects 0.000 description 2
- 238000003491 array Methods 0.000 description 2
- 238000004891 communication Methods 0.000 description 2
- 239000012141 concentrate Substances 0.000 description 2
- 230000008520 organization Effects 0.000 description 2
- 238000012545 processing Methods 0.000 description 2
- 208000019901 Anxiety disease Diseases 0.000 description 1
- 241001269238 Data Species 0.000 description 1
- 230000001133 acceleration Effects 0.000 description 1
- 238000004458 analytical method Methods 0.000 description 1
- 230000036506 anxiety Effects 0.000 description 1
- 238000013459 approach Methods 0.000 description 1
- 238000010276 construction Methods 0.000 description 1
- 238000013144 data compression Methods 0.000 description 1
- 238000013500 data storage Methods 0.000 description 1
- 238000010586 diagram Methods 0.000 description 1
- 230000006872 improvement Effects 0.000 description 1
- 230000010365 information processing Effects 0.000 description 1
- 238000009434 installation Methods 0.000 description 1
- 238000007726 management method Methods 0.000 description 1
- 239000000203 mixture Substances 0.000 description 1
- 238000012544 monitoring process Methods 0.000 description 1
Classifications
-
- G—PHYSICS
- G05—CONTROLLING; REGULATING
- G05B—CONTROL OR REGULATING SYSTEMS IN GENERAL; FUNCTIONAL ELEMENTS OF SUCH SYSTEMS; MONITORING OR TESTING ARRANGEMENTS FOR SUCH SYSTEMS OR ELEMENTS
- G05B23/00—Testing or monitoring of control systems or parts thereof
- G05B23/02—Electric testing or monitoring
- G05B23/0205—Electric testing or monitoring by means of a monitoring system capable of detecting and responding to faults
- G05B23/0218—Electric testing or monitoring by means of a monitoring system capable of detecting and responding to faults characterised by the fault detection method dealing with either existing or incipient faults
- G05B23/0243—Electric testing or monitoring by means of a monitoring system capable of detecting and responding to faults characterised by the fault detection method dealing with either existing or incipient faults model based detection method, e.g. first-principles knowledge model
-
- G—PHYSICS
- G05—CONTROLLING; REGULATING
- G05B—CONTROL OR REGULATING SYSTEMS IN GENERAL; FUNCTIONAL ELEMENTS OF SUCH SYSTEMS; MONITORING OR TESTING ARRANGEMENTS FOR SUCH SYSTEMS OR ELEMENTS
- G05B2219/00—Program-control systems
- G05B2219/20—Pc systems
- G05B2219/24—Pc safety
- G05B2219/24065—Real time diagnostics
Landscapes
- Physics & Mathematics (AREA)
- General Physics & Mathematics (AREA)
- Engineering & Computer Science (AREA)
- Automation & Control Theory (AREA)
- Compression Or Coding Systems Of Tv Signals (AREA)
- Compression, Expansion, Code Conversion, And Decoders (AREA)
Abstract
The design of the light decompression algorithm of intelligent household terminal firmware upgrade mirror image based on ZigBee technology, belongs to Intelligent internet of things field.Firmware image file is passed through Huffman encoding compression transmission to ZigBee terminals by the home gateway of smart home, and terminal embedded equipment needs to be decompressed and updates existing firmware.The present invention is based on Huffman tree for ZigBee built-in terminals design of node one kind of resource-constrained, finds a Hamilton loop and then constructs a kind of algorithm of bit stream progress light decoding of specific decompression array to compressed file.The space that the Huffman tree of the algorithm takes will be small than the data store organisation of traditional order storage and linked list type storage, in addition experiments verify that decoding time loss is than nearly 20 times of traversal coding schedule reduction.The generation method of decoding array and the design of decoding algorithm of the present invention is a kind of innovation.
Description
Technical field
Realized the present invention relates to the ZigBee node firmware upgrade process in smart home environment a kind of to image file
Light decompression algorithm, and in particular to a kind of for by the ZigBee firmware upgrades mirror image text of Huffman encoding compression
Part, decompression is carried out to it in ZigBee intelligent nodes, belongs to Intelligent internet of things field.
Background technology
Modern science and technology make the living environment of individual more convenient, comfortably, automatic and safety.Smart home is gradually come into
The life of people.Document 1：Han D M, Lim J H. Smart Home Energy Management System
using IEEE 802.15.4 and ZigBee [J]. Consumer Electronics, IEEE Transactions
on, 2010, 56[3]:1403-1410. proposes that smart home is that one family monitoring system has that installation is simple, operation side
Just the characteristics of.All it is being widely used in many of smart home environment technology, such as bluetooth, WIFI, 6LoWPAN,
ZigBee etc..The characteristics of ZigBee technology is closely low-complexity, self-organizing, low-power consumption and low data rate thus quilt
It is widely used in and automatically controls, remote control and various embedded devices.Therefore ZigBee technology is selected herein as support technology
To build smart home environment.Due to the resource-constrained of ZigBee terminal nodes, such as memory size, communication bandwidth and processing energy
Power etc. factor, the firmware for how completing resource-conserving are modernized into a kind of challenge.Commonly used approach be by
Image file needed for upgrading is compressed before transmission is sent, and the decompression of firmware image is carried out in intelligent ZigBee end points
And upgrade the current application program of chip with it.Mirror image sender is typically the home gateway of resource relative abundance.Compared to it
Under receiver end, i.e. ZigBee end points is the embedded chip of resource-constrained.As shown in Fig. 1, based on ZigBee technology
Smart home environment include an intelligent domestic gateway, first, ZigBee-network softdog node and gateway pass through wired company
Connect, at the same with other ZigBee end points wireless connections.Firmware image will compress in home gateway and be passed by ZigBee softdogs
Transport to the ZigBee end points for needing to upgrade.ZigBee end points decompresses new firmware and replaces original program code
Into whole renewal process.
Therefore a challenge in ZigBee firmware renewal is how to make to use money as few as possible in decompression procedure
Source is possibly realized.This paper purpose is to design a flexible light decompression algorithm, to meet limited resource firmware upgrade
Situation.Document 2：D. Huffman, “A method for the construction of minimum redundancy
Code ", Proc. IRE, vol. 40, pp. 1098-1101,1952. propose that Huffman codings are one very typical
Compression coding technology, the present invention determine first using Huffman encoding come to compress firmware image, then ZigBee softdogs will
It is broadcast to ZigBee-network, and the algorithm of subsequent ZigBee terminals using flexible encodes the firmware mirror compressed to decompress Huffman
Picture.Groundwork concentrates on how end points effectively decompresses mirror image.
Document 3：Lin Y K, Huang S C, Yang C H. A fast algorithm for Huffman
decoding based on a recursion Huffman tree [J]. Journal of Systems and
Software, 2012, 85(4):974-980. is absorbed in the time efficiency of Huffman decodings, and it make use of numeric value analysis to add
Fast decoding process.Document 4：Aggarwal M, Narayan A. Efficient Huffman decoding[C]//Image
Processing, 2000. Proceedings. 2000 International Conference on. IEEE, 2000,
1:The Huffman tree that 936-939. proposes a kind of memory efficient arrays to represent, so as to reduce memory size and
The process of Huffman tree symbol in acceleration search.They all concentrate on decoding process.In addition, also it is related to setting for coded treatment
Meter, to lift the work of decoding efficiency.Document 5：Faller, N. 1973. An Adaptive System for Data
Compression. Record of the 7th Asilomar Conf. on Circuits, Systems and
Computers (Pacific Grove, Ca. Nov.), 593-597. propose a kind of adaptive Huffman encoding to cause
The memory space of Huffman encoding tree is reduced to zero.In the case of certain specific constraint, decoder is dynamically rebuild
With decoders-Synchronous Huffman encoding tree, without any additional data.Document 6：Moffat A. and Turpin A., "
On the Implementation of minimum redundancy prefix codes", IEEE Transactions
On Communications, vol. 45, it is that need not be limited by bit manipulation the advantages of No. 10,1200-1207.
System, disposably multidigit bit stream can be read, improve decoding efficiency to a certain extent.For the algorithm, document 7：
Nekrich Y., "On efficient decoding of Huffman codes", Technical Report
No.85190-CS, Department of Computer Science, Bonn University, April 1998. is proposed
Minimum code length can be made one binary tree by being improved on identified code length, by using this binary tree
Code length can quickly be determined.Although such improvement is the problem of optimizing bitwise operation, stills need to calculate and compile
The length of code, document 8：Shmuel T.Klein, "Space- and time- efficient decoding with
canonical Huffman trees", 8th Annual Symposium on Combinatorial Pattern
Matching, Aarhus, Denmark, 30 June-2 July 1997, Lecture Notes in Computer
Science, vol. 1264,65-75. are discussed based on and need not be calculated the inquiring arithmetic of fixed code length.The decoding algorithm
Although efficient, when maximum code length is larger, the initialization of table can take more time and space cost, and this is not
It is adapted to the scene of small-scale data decoding and memory space anxiety.In consideration of it, document 9：Sieminski A., "Fast
decoding of the Huffman codes", Information Processing Letters, vol.26, 1988,
237-241. proposes a kind of algorithm for optimizing look-up table.The algorithm proposes first to decode using a fixed code length, then the code length
It can directly decode or other decoding prefixes, can be decoded by continuing to read several bit datas, so greatly reduced
The space of table.Although spatially all having done many work in reduction table, it is required for reconstructing Huffman tree in decoding end, it is right
In the storage of Huffman tree be unavoidable.The present invention proposes what a Hamilton loop based on Huffman tree was built
Decode array, it is contemplated that ZigBee embedded resource limited environments, the present invention with traditional Huffman decompression algorithm after contrasting
Optimization aim has two：
(1) meet that the memory space of minimum Huffman tree takes.
(2) optimal decoding efficiency.
The major contribution of the present invention is in the following aspects:
(1) it is directed to embedded device, it is proposed that an effective ZigBee mirror image data decompression algorithm：The Chinese of Huffman tree
Milton loop decompression algorithm（HHD）.
(2) the decoding array generating algorithm for decompression is given for HHD decompression algorithms.
(3) the decoding array generated by compareing HHD algorithms carries out light decompression to image file.
The content of the invention
Typically there are two methods i.e. sequential storage and storage of linked list for the storage mode of Huffman tree.Due to sequential storage
Structure is characterized in being stored binary tree using array thus being taken less internal memory, and this feature is well suited for embedded scheme
In.It can pass through array index and the corresponding relation of logical address, order with random read take data additionally, due to storage of array structure
Storage carries out corresponding decoding.But the shortcomings that sequentially storing be when code length is longer or during single branch structure Huffman tree,
Occur many empty occupy-place units in array, sequential storage space will significantly increase.And in decoding, according to reading
A string of bit streams are traveled through to Huffman binary tree to find corresponding code word, are wasted in the case of dummy cell occupy-place is more a large amount of
The lookup time and comparing calculation time loss.Although however, storage of linked list can accurately according to pointer carry out decoding interrogation,
But it but takes substantial amounts of memory space to store the pointer of father node or child node, this larger memory consumption discomfort
Close embedded environment.Therefore, the present invention is sent out according to the advantages of the data structure for contrasting both the above Huffman tree with shortcoming, design
Understand a kind of data store organisation of new Huffman tree.By using storage of array Huffman tree information, specific number is established
The mapping relations of group subscript and logical address, it is possible to achieve accurately redirect function of search as pointer.This new types of data
Storage organization had both met the characteristics of occupying little space of storage of array, and colleague also meets the work(that pointer precisely redirects decoding
Energy.Finally, the code word that can be easily decompressed very much according to this decoding array.
Technical scheme is as follows：The light solution of image file based on ZigBee firmware upgrades in smart home environment
Press algorithm, it is characterised in that comprise the following steps：
Step 1: recording the attribute of all non-leaf nodes using a two-dimensional array, each row vector unit has four numbers
Value, address and the code value of the left-side child nodes of the node, the address of right-side child nodes and code value are recorded respectively；Left-side child
It is 1 for 0 right-side child, setting the first root node numbering is 1, and left-side child is 2, and right-side child is 3, and right-side child nodes are marked
Pathfinding start node is designated as, left-side child nodes are marked as pathfinding end node and provide that being in more high-rise pathfinding starts
Node possesses higher priority and set, and is in more high-rise pathfinding end node and possesses relatively low priority；
Step 2: laid down a regulation for the mark in the binary tree of a unit, after all nodes are indicated, according to seeking
Road rule is painted out the Hamilton loop of a closure, when Hamilton loop is closed to No. 2 nodes, numbering work completion；
Step 3: recording the information of node using an array, N [x] [y] example is taken to represent array：0<x<N,0<y<
5.The two-dimensional array is defined as follows:Nodal community is recorded using unit row vector：N [x] [1] stores left child node value; N
The value of the storage right-side child nodes of [x] [2];N [x] [3] stores left child node numbering;On the right side of N [x] [4] storage
Child nodes are numbered.If node is not leaf, its value is null, if node is leaf, the value is its decoded word and its volume
Number it is zero, indicates the end of this section of bit stream decoding.After one section of bit stream decoding terminates, start from ratio new N [x] [1]
Special stream carries out re-searching for decoding；
Step 4: according to HHD array generating algorithms, Huffman tree is by the sequential core-pulling of the decoding array regenerated, i.e.
The physical address and array indexed address be mapping relations and can random read take data.
The decoding decoding process of step 4 is to read binary bit stream, by compareing new decoding array.According to the number
Setting in group, the left side 0, the right are 1.The binary bit stream of input, such as 10110101110000 ... search array:The
One bit is 1, reads N [1] [4] and assignment x=N [1] [4].Then bit is 0, reads N [x] [3] and assignment x
=N [x] [3], until when bit is 0, x=0, decoding code value is equal to N [x] [1] or when bit is 1, x=0
When, decoding code value afterwards, continues to read next bit, restarts to redirect search from [1] [y] equal to N [x] [2]
Decoding, and circulate operation is performed, until decoding is completed.In decompression algorithm array " LV " be left-side child nodes code value with
" RV " is the code value of right-side child nodes, " LN " be the numbering of left-side child nodes and " RN " be right-side child nodes volume
Number.
The rule of the mark of step 2 is as follows:Left-side child nodes are marked as the end mark of binary tree pathfinding, right side
Child nodes are pathfinding opening flag；When having in two child nodes and only one is leaf node, the node of another non-leaf
Inherit the Information sign of its father node；When two child nodes are all leaf nodes, its code value is marked；The pathfinding of higher starts to save
Point with higher priority and the end node of higher after all nodes are indicated, is pressed with relatively low priority
The Hamilton loop for a closure of being painted out according to pathfinding rule；The pathfinding rule of Hamilton loop is:Starting point is set out closure
To terminal, terminal is connected with next nearest starting point；Start node branch pathfinding direction is end node from the top to the bottom
Direction be from bottom to top；It is big in nearest same branch, any end node of priority ratio of any start node；Node
Priority get over that Gao Yuexian is numbered and node serial number is sequential in accordance with pathfinding order.
The attribute of non-leaf nodes is recorded as a data cell herein by this array is built.Experimental result table
It is bright, the advantages of the algorithm：
(1) in ZigBee mirror image compressed files, compression mean code length is about 6.Therefore, average six steps need to be only spent
Obtain it and decode code word, more than 20 times are improved in the performance of decoding time loss.By reducing the decoding time, exist accordingly
Reduce calculating, search, jump procedure on embedded device, this will also save some energy.
(2) Huffman tree storage mode is stored using array, and the memory space is than storage of linked list and sequential storage mode
Will be small.The algorithm of the apparent present invention reduces the consumption of the space cost of Hafman decoding process.Because there are many skies
Placeholder data, while also provide space for following further optimization.
The algorithm innovation of the present invention is that it generates Huffman tree the decoding array of one special agreement, Ke Yigen
Data are directly decoded according to the array index random read take, decoding efficiency greatly increases.But the cost of this design is increase
The amount of calculation and codec complexity at compressed encoding end.And in smart home ZigBee firmware upgrade scenes, cataloged procedure
Work is carried out in gateway, and general home gateway resource is relatively abundant, this cost acceptable, so the algorithm
Such application environment is just catered to.However, the structure of the array is the key of success decoding.
Brief description of the drawings
Below in conjunction with the accompanying drawings, the preferred embodiment of the present invention is described further by non-limiting citing,
In accompanying drawing：
Fig. 1 is that the present invention is based on ZigBee technology smart home composition schematic diagram；
Fig. 2 is Huffman binary tree mark figure；
Fig. 3 is the Hamilton loop pathfinding path tag of Huffman binary tree；
Fig. 4 is HHD decoding algorithm flow charts；
Fig. 5 is for ZigBee sample mirror images, the memory space consumption contrast of sequential storage, storage of linked list and HHD algorithms；
Fig. 6 is contrasted for the linked list type storage of different number of elements and the space consuming of HHD algorithms；
Fig. 7 is to be directed to different most long codes code lengths, the minimum and maximum memory space contrast of sequential storage；
Fig. 8 is binary tree traversal decoding and HHD decoding time loss contrasts.
Embodiment
The present invention is described in further detail below in conjunction with the accompanying drawings.
First, we set set Huffman tree, and left-side child is that 0 right-side child is 1, is drawn in Huffman tree such as figure
It is shown.Our target is to establish an orderly configuration decoding table, and requires that its logical address is closure.As above
Discuss how to cause array interior joint indexed address and logical address to form mapping relations and be closed-loop path be the present invention into
The key point of work(design.Solves this problem using Hamilton loop.It is 1 to set the first root node numbering, left-side child
It is 2, right-side child is 3.Right-side child nodes are marked as pathfinding start node, and left-side child nodes, which are marked as pathfinding, to be terminated
Node and regulation are in more high-rise pathfinding start node and possess higher priority setting, and are in more high-rise pathfinding knot
Shu Jiedian possesses relatively low priority.So, Huffman tree should be marked as to be as shown in Figure 3.
It is as follows for the rule of the mark in the binary tree of a unit:Left-side child nodes are marked as binary tree and sought
The end mark on road, right-side child nodes are pathfinding opening flag；
When having in two child nodes and only one is leaf node, the node of another non-leaf inherits the information of its father node
Mark；
When two child nodes are all leaf nodes, its code value is marked；
The pathfinding start node of higher is with higher priority and the end node of higher is with relatively low priority.
After all nodes are indicated, the Hamilton loop for a closure of being painted out according to pathfinding rule.Chinese Mill
The pathfinding rule in loop is:
Starting point, which is set out, is closed into terminal, and terminal is connected with next nearest starting point；
Start node branch pathfinding direction is that from the top to the bottom, the direction of end node is from bottom to top；
It is big in nearest same branch, any end node of priority ratio of any start node；
The priority of node gets over that Gao Yuexian is numbered and node serial number is sequential in accordance with pathfinding order.
When Hamilton loop is closed to No. 2 nodes, numbering work is completed.At this moment we just need to use an array
The information of node is recorded, takes N [x] [y] example to represent array：0<x<N,0<y<5.The two-dimensional array is defined as follows:Make
Nodal community is recorded with unit row vector：N [x] [1] stores left child node value;N [x] [2] storage right-side child nodes
Value;N [x] [3] stores left child node numbering;N [x] [4] storage right-side child nodes numbering.If node is not
Leaf, its value are null.If node is leaf, the value is its decoded word and its numbering is zero, indicates this section of bit stream solution
The end of code.After one section of bit stream decoding terminates, start to carry out re-searching for decoding from the new bit streams of N [x] [1].More than
Huffman tree sample N [x] [y] it is as shown in the table I.
According to HHD array generating algorithms, Huffman tree is by the sequential core-pulling of the decoding array regenerated, i.e. the thing
Reason address and array indexed address be mapping relations and can random read take data.Decoding process is to read binary bit stream,
Such as the table of comparisons, by compareing new decoding array.
According to the setting in the array, the left side 0, the right is 1.The binary bit stream of input, such as
10110101110000 ... search arrays in table:First bit is 1, reads N [1] [4] and assignment x=N [1]
[4].Then bit is 0, reads N [x] [3] and assignment x=N [x] [3].Until when bit is 0, x=0, decoding code value
Equal to N [x] [1] or when bit is 1, x=0, decoding code value is equal to N's [x] [2].Afterwards, continue to read next
Individual bit, restart to redirect search decoding from [1] [y], and perform circulate operation, until decoding is completed.Decompression algorithm
" LV " is the code value of left-side child nodes and " RV " is the code value of right-side child nodes in array.It is left-side child nodes at " LN "
Numbering and " RN " be right-side child nodes numbering.
How the key of structure two-dimensional array is according to Huffman encoding tree generation Hamilton circuit.Then using decoding
The data that array is decompressed can make it more rapidly and conveniently.Because most calculating cost is to create decompression
During array, the decompression for making to meet contribution target herein is very flexible.In summary, HHD algorithms use number
Storage organization is organized to store Huffman binary tree, realizes logical address mapping array indexing address.In other words, it uses array
Pointer turn function is realized in storage.By this way, ZigBee end points can neatly decompress the firmware image of renewal,
HHD algorithm flow charts are as shown in Figure 4.
The estimation flow of algorithm is as follows.First, ZigBee firmware renewal source file has 256 elements, and it is by Hough
Graceful compression.Most long code length is 11 and averagely code length is 6.Data take memory space and are 1 bytes and refer in array
It is 2 bytes that pin, which takes memory space,.
(1) it according to its most long code length is k that the size of sequence storage Huffman tree, which is,.Herein, breathe out completely
The graceful binary tree number order of husband is from top to bottom, from left to right.If Huffman tree coding extreme length is Dan Zuozhi, its scale
It is minimum：
If Huffman tree coding extreme length is single right branch, its scale is maximum：
In general, most long code length will be more than 8.In the condition of the compression ZigBee of present invention image file, k=
11.Therefore, minimum dimension is：（2 ^ 10 + 2 ^ 10 + 1）The byte of * 1 byte=2049;
(2) if child pointers are only used only without father's pointer, general storage of linked list structure space cost in linked list type storage
For：
Without father's pointer data structure, the memory space cost of chained list is smaller to be the pointer that we only need to record left and right child：
（The byte of+1 byte of 2 byte+2）*（256 + 256-1）=2555 bytes;
(3) HHD algorithms are the information of the non-leaf nodes recorded, and its number of elements only has N-1, and each element needs 4 words
Save memory space.Then the total memory space cost of HHD Huffman trees is：
So the space cost size of this decompression algorithm is：（256-1）* the byte of 4 bytes=1020, above three compare
As a result it is as shown in Figure 5.Represent the space cost of storage of linked list using y1, and using y2 represent the spaces of HHD decompression algorithms into
This.From Fig. 6, it shows that y1 is bigger than y2.The cost of HHD decompression algorithms takes smaller space than other algorithms.Because
The memory space cost of order is determined by the code length most grown.In general, most long code length is nearly all bigger than 8, no
The file of same type has different most long codes length.It may be seen that its relation with coding extreme length k from Fig. 7.
In sample data of the present invention, most long codes length is 11, and the minimum memory space cost of sequence is 2049 bytes, and this still compares
HHD 1020 bytes will be twice more.
Decompression time Cost comparisons, decompression algorithm of the invention, the index of array is mapped to by reading logical address
Number realize the function of array pointer.In sample data of the present invention, average code length is 6, then shows that we averagely need
Six redirect search step to decode corresponding encoded word.Therefore, average time cost is 6* T, and comparing result is as follows:
In an experiment, ZigBee upgrade images file has 256 elements, and set decompression redirects search unit time loss
For T.Traditional Hafman decoding is decoded by binary tree traversal, and inefficient practical application scene is few.More
It is that coding schedule is generated according to binary tree, by searching for coding schedule control decoding corresponding codewords.So traditional decompression mode should search for
256 elements and code word corresponding to them are decoded.Ideally, searched for for a decoding table for there are 256 elements
When redirecting decoding, calculated according to average probability, traditional coding schedule is stored in search Huffman tree and code word is successfully decoded
Time cost is：（256/2）* T.If using sequentially being set to store Huffman tree and traversal, search time is than this value more
Greatly.Because binary tree traversal has three kinds：Preamble travels through, middle order traversal and postorder traversal.They are required for undergoing more multistep
It is rapid to search decoded word.In the case of preferably, average code length is 6, it would be desirable to jumps six words for finding a decoding.
But we need to travel through 256 units, average decoding time cost when traveling through decoding（256/2）* 6T.In HHD calculation
Method, we simply accurately redirect the code word that six steps find decoding.So simply spend 6 * T times decoding corresponding encoded
Word.Due to travel through Huffman tree time cost than traversal coding schedule it is big, the present invention simply contrast travel through coding schedule time into
This and HHD algorithm time costs are as shown in Figure 8.It will be seen that HHD, which averagely decompresses elapsed time cost, is less than ergodic solutions
About 20 times of code table time loss.
The attribute of non-leaf nodes is recorded as a data cell herein by this array is built.Experimental result table
It is bright, the advantages of the algorithm：
(1) in ZigBee mirror image compressed files, compression mean code length is about 6.Therefore, average six steps need to be only spent
Obtain it and decode code word, more than 20 times are improved in the performance of decoding time loss.By reducing the decoding time, exist accordingly
Reduce calculating, search, jump procedure on embedded device, this will also save some energy.
(2) Huffman tree storage mode is stored using array, and the memory space is than storage of linked list and sequential storage mode
Will be small.The algorithm of the apparent present invention reduces the consumption of the space cost of Hafman decoding process.Because there are many skies
Placeholder data, while also provide space for following further optimization.
The algorithm innovation of the present invention is that it generates Huffman tree the decoding array of one special agreement, Ke Yigen
Data are directly decoded according to the array index random read take, decoding efficiency greatly increases.But the cost of this design is increase
The amount of calculation and codec complexity at compressed encoding end.And in smart home ZigBee firmware upgrade scenes, cataloged procedure
Work is carried out in gateway, and general home gateway resource is relatively abundant, this cost acceptable, so the algorithm
Such application environment is just catered to.However, the structure of the array is the key of success decoding.
Claims (10)
1. the light decompression algorithm of image file based on ZigBee firmware upgrades in smart home environment, it is characterised in that including
Following steps：
Step 1: recording the attribute of all non-leaf nodes using a two-dimensional array, each row vector unit has four numbers
Value, address and the code value of the left-side child nodes of the node, the address of right-side child nodes and code value are recorded respectively；Left-side child
It is 1 for 0 right-side child, setting the first root node numbering is 1, and left-side child is 2, and right-side child is 3, and right-side child nodes are marked
Pathfinding start node is designated as, left-side child nodes are marked as pathfinding end node and provide that being in more high-rise pathfinding starts
Node possesses higher priority and set, and is in more high-rise pathfinding end node and possesses relatively low priority；
Step 2: laid down a regulation for the mark in the binary tree of a unit, after all nodes are indicated, according to seeking
Road rule is painted out the Hamilton loop of a closure, when Hamilton loop is closed to No. 2 nodes, numbering work completion；
Step 3: recording the information of node using an array, N [x] [y] example is taken to represent array：0<x<N,0<y<
5。
2. the two-dimensional array is defined as follows:Nodal community is recorded using unit row vector：N [x] [1] stores left child node value;
The value of N [x] [2] storage right-side child nodes;N [x] [3] stores left child node numbering;N [x] [4] storage is right
Side child nodes numbering.
3. if node is not leaf, its value is null, if node is leaf, the value is its decoded word and its numbering is zero,
Indicate the end of this section of bit stream decoding.
4. after one section of bit stream decoding terminates, start to carry out re-searching for decoding from the new bit streams of N [x] [1]；
Step 4: according to HHD array generating algorithms, Huffman tree is by the sequential core-pulling of the decoding array regenerated, i.e.
The physical address and array indexed address be mapping relations and can random read take data.
5. the light decompression algorithm of the image file of ZigBee firmware upgrades in smart home environment according to claim 1,
Characterized in that, the decoding decoding process of step 4 is to read binary bit stream, by compareing new decoding array.
6. according to the setting in the array, the left side 0, the right is 1.
7. the binary bit stream of input, such as 10110101110000 ... search array:First bit is 1, reads N [1]
[4] and assignment x=N [1] [4].
8. then bit is 0, N [x] [3] and assignment x=N [x] [3] is read, until when bit is 0, x=0, decoding code
Equal to N [x] [1] or when bit is 1, x=0, decoding code value afterwards, continues under reading value equal to N [x] [2]
One bit, restart to redirect search decoding from [1] [y], and perform circulate operation, until decoding is completed.
9. " LV " is the code value of left-side child nodes and " RV " is the code value of right-side child nodes in decompression algorithm array,
" LN " is the numbering of left-side child nodes and " RN " is the numbering of right-side child nodes.
10. the light decompression algorithm of the image file of ZigBee firmware upgrades in smart home environment according to claim 1,
Characterized in that, the rule of the mark of step 2 is as follows:Left-side child nodes are marked as the end mark of binary tree pathfinding, right
Side child nodes are pathfinding opening flag；When having in two child nodes and only one is leaf node, the section of another non-leaf
Point inherits the Information sign of its father node；When two child nodes are all leaf nodes, its code value is marked；The pathfinding of higher starts
Node is with higher priority and the end node of higher is with relatively low priority, after all nodes are indicated,
The Hamilton loop for a closure of being painted out according to pathfinding rule；The pathfinding rule of Hamilton loop is:Starting point, which is set out, closes
Terminal is closed, terminal is connected with next nearest starting point；Start node branch pathfinding direction is from the top to the bottom, to terminate section
The direction of point is from bottom to top；It is big in nearest same branch, any end node of priority ratio of any start node；Section
The priority of point gets over that Gao Yuexian is numbered and node serial number is sequential in accordance with pathfinding order.
Applications Claiming Priority (2)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| CN2016107444549 | 2016-08-29 | ||
| CN201610744454 | 2016-08-29 |
Publications (2)
| Publication Number | Publication Date |
|---|---|
| CN107797541A true CN107797541A (en) | 2018-03-13 |
| CN107797541B CN107797541B (en) | 2020-11-10 |
Family
ID=61531646
Family Applications (1)
| Application Number | Title | Priority Date | Filing Date |
|---|---|---|---|
| CN201710758394.0A Active CN107797541B (en) | 2016-08-29 | 2017-08-29 | Image file portable decompression algorithm based on ZigBee firmware upgrading in smart home environment |
Country Status (1)
| Country | Link |
|---|---|
| CN (1) | CN107797541B (en) |
Cited By (1)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| CN112988211A (en) * | 2021-02-25 | 2021-06-18 | 广东省安心加科技有限公司 | Equipment upgrading method and control device based on Zigbee |
Citations (9)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| CN1441555A (en) * | 2002-02-28 | 2003-09-10 | 三星电子株式会社 | Improved huffman decoding method and device |
| CN101051845A (en) * | 2007-05-09 | 2007-10-10 | 上海广电（集团）有限公司中央研究院 | Huffman decoding method for quick extracting bit stream |
| CN101908891A (en) * | 2010-08-23 | 2010-12-08 | 南京信息工程大学 | Medical image ROI compression method based on lifting wavelet and PCNN |
| CN102255617A (en) * | 2010-05-19 | 2011-11-23 | 鸿富锦精密工业（深圳）有限公司 | Storage method of Huffman tree and method of decoding data by using arrays |
| US20120139763A1 (en) * | 2010-12-07 | 2012-06-07 | International Business Machines Corporation | Decoding encoded data |
| US20120319875A1 (en) * | 2010-05-19 | 2012-12-20 | Hon Hai Precision Industry Co., Ltd. | Method for storing node information of huffman tree and corresponding decoding method |
| CN103731154A (en) * | 2013-11-01 | 2014-04-16 | 陕西理工学院 | Data compression algorithm based on semantic analysis |
| CN105447546A (en) * | 2015-11-25 | 2016-03-30 | 林蔚 | Two-dimensional code capable of being embedded with large-ratio graph as well as coding and decoding method and device therefor |
| CN105577539A (en) * | 2016-01-27 | 2016-05-11 | 中国科学院计算技术研究所 | A routing method and system for an irregular three-dimensional integrated circuit on-chip network |
-
2017
- 2017-08-29 CN CN201710758394.0A patent/CN107797541B/en active Active
Patent Citations (9)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| CN1441555A (en) * | 2002-02-28 | 2003-09-10 | 三星电子株式会社 | Improved huffman decoding method and device |
| CN101051845A (en) * | 2007-05-09 | 2007-10-10 | 上海广电（集团）有限公司中央研究院 | Huffman decoding method for quick extracting bit stream |
| CN102255617A (en) * | 2010-05-19 | 2011-11-23 | 鸿富锦精密工业（深圳）有限公司 | Storage method of Huffman tree and method of decoding data by using arrays |
| US20120319875A1 (en) * | 2010-05-19 | 2012-12-20 | Hon Hai Precision Industry Co., Ltd. | Method for storing node information of huffman tree and corresponding decoding method |
| CN101908891A (en) * | 2010-08-23 | 2010-12-08 | 南京信息工程大学 | Medical image ROI compression method based on lifting wavelet and PCNN |
| US20120139763A1 (en) * | 2010-12-07 | 2012-06-07 | International Business Machines Corporation | Decoding encoded data |
| CN103731154A (en) * | 2013-11-01 | 2014-04-16 | 陕西理工学院 | Data compression algorithm based on semantic analysis |
| CN105447546A (en) * | 2015-11-25 | 2016-03-30 | 林蔚 | Two-dimensional code capable of being embedded with large-ratio graph as well as coding and decoding method and device therefor |
| CN105577539A (en) * | 2016-01-27 | 2016-05-11 | 中国科学院计算技术研究所 | A routing method and system for an irregular three-dimensional integrated circuit on-chip network |
Cited By (1)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| CN112988211A (en) * | 2021-02-25 | 2021-06-18 | 广东省安心加科技有限公司 | Equipment upgrading method and control device based on Zigbee |
Also Published As
| Publication number | Publication date |
|---|---|
| CN107797541B (en) | 2020-11-10 |
Similar Documents
| Publication | Publication Date | Title |
|---|---|---|
| US6122378A (en) | Data compression/encryption method and system | |
| Crochemore et al. | Data compression using antidictionaries | |
| US8937564B2 (en) | System, method and non-transitory computer readable medium for compressing genetic information | |
| Hu et al. | Worst-case redundancy of optimal binary AIFV codes and their extended codes | |
| CN107295070A (en) | The distributed coding caching laying method and system of file size isomery | |
| CN103546161A (en) | Lossless compression method based on binary processing | |
| CN103701470B (en) | Stream intelligence prediction differencing and compression algorithm and corresponding control device | |
| Zhu et al. | Fractional repetition codes with optimal reconstruction degree | |
| Alrabiah et al. | An exponential lower bound on the sub-packetization of minimum storage regenerating codes | |
| Zhang et al. | RETCAM: An efficient TCAM compression model for flow table of OpenFlow | |
| US6748520B1 (en) | System and method for compressing and decompressing a binary code image | |
| CN107797541A (en) | The light decompression algorithm of image file based on ZigBee firmware upgrades in smart home environment | |
| CN105791832B (en) | Data-encoding scheme and data decoding method and its system | |
| CN111600610B (en) | Universal coding method, system and electronic equipment for variable-length integers | |
| KR20050053996A (en) | Method and apparatus for decoding huffman code effectively | |
| US6411714B1 (en) | Data decompression/decryption method and system | |
| CN110113402B (en) | WEB service communication method and device | |
| WO2020114283A1 (en) | Data processing method and device | |
| CN108829930B (en) | Lightweight method for designing MBD model by three-dimensional digital process | |
| US10762281B1 (en) | Prefix compression for keyed values | |
| CN104765790B (en) | Method and device for data query | |
| CN115801021A (en) | ANS (answer System) grouping coding and decoding method, computer equipment and storage medium | |
| CN102377438A (en) | Channel decoding method and tail biting convolutional decoder | |
| CN100401671C (en) | Method for transmitting files | |
| Feng et al. | A nimble decompression algorithm for ZigBee firmware update in smart home environment |
Legal Events
| Date | Code | Title | Description |
|---|---|---|---|
| PB01 | Publication | ||
| PB01 | Publication | ||
| SE01 | Entry into force of request for substantive examination | ||
| SE01 | Entry into force of request for substantive examination | ||
| GR01 | Patent grant | ||
| GR01 | Patent grant |