CN107967296B - Improved LZO compression method with rapid low resource overhead - Google Patents

Abstract

An improved LZO compression method with fast and low resource overhead, firstly, a first compression format, a corresponding first compression algorithm, a second compression format and a corresponding second compression algorithm for compressing new characters by the LZO compression method are constructed according to the anaphora distance , and then record the new character length for LZO compression, and perform LZO compression according to the new character length, the compression format selected by the anaphora distance and the corresponding compression algorithm. Based on the LZO algorithm, the present invention performs statistical analysis on the bit file, and proposes a new compression format on the premise of retaining the hash operation. By reducing the anaphora distance, the compression and decompression speeds are greatly improved, which is more convenient for hardware implementation and aerospace applications, and has good use value.

Description

An improved LZO compression method with fast and low resource overhead

technical field

The invention relates to the technical field of bit file compression, in particular to an improved LZO compression method with fast and low resource overhead.

Background technique

The LZO algorithm is based on the traditional dictionary compression algorithm, and uses a hash table to record the dictionary data in the sliding window, which reduces the time to search for the same character and greatly improves the compression speed of the algorithm. , which can make each byte more fully utilized and increase the data compression ratio. In 2004, NASA applied LZO lossless compression to the Mars explorations Opportunity and Spirit.

As shown in Figure 1 is the flow chart of the existing LZO compression algorithm, which firstly performs a hash operation on the input data to determine whether the input data is in the hash table, if the input data is not in the hash table, then expand the hash table, Otherwise, the input data is compressed according to the LZO compression format. The existing LZO compression algorithm compression formats are divided into 5 types according to the offset distance and repetition length, as shown in Figure 2(a), (b), (c), (d), (e) The LZO Compression Algorithm 5 LZO compression formats.

As shown in Figure 2(a), (b), (c), the repetition length of the three compression formats is less than or equal to 8 bytes. 3 back finger distance is greater than 16k, less than or equal to 48k. Format 4, Format 5, is the case where the repetition length is greater than 8 bytes. Format 4 means that the distance is less than or equal to 16k, and format 5 means that the distance is greater than 16k and less than or equal to 48k.

The five compression formats shown in Figure 2 can support a maximum anaphora distance of 48k, so at least 48k of decompressed data must be stored to ensure that the compressed data is correctly decompressed. Excessive RAM depth will slow down the decompression rate, and the RAM itself The refresh rate is reduced during decompression, and single-event flipping is more likely to occur in a space radiation environment. The above five formats are jointly determined by the anaphora distance and the repetition length, which makes the determination process cumbersome and reduces the compression speed; the decompression circuit needs to distinguish the five compression formats, and a large number of control signals are needed to ensure the correctness of the decompression, which makes the decompression process complicated. Increased timing overhead and hardware resource overhead.

SUMMARY OF THE INVENTION

The technical problem solved by the present invention is: overcoming the deficiencies of the prior art and providing an improved LZO compression method with fast and low resource overhead, through the research on the existing LZO compression algorithm, while retaining the hash operation of the LZO compression algorithm, Through statistical analysis of the data characteristics of the bit file and the five compression formats of LZO, a fast and low resource cost lossless compression method is designed. Greatly improved, hardware resource overhead is greatly reduced.

The technical solution of the present invention is: an improved LZO compression method with fast and low resource overhead, comprising the following steps:

(1) Constructing the first compression format and the corresponding first compression algorithm, the second compression format and the corresponding second compression algorithm for compressing the new character by the LZO compression method according to the anaphoric distance; the first compression format is applicable and The anaphora distance of the new character to be compressed is smaller than the anaphora distance of the new character to be compressed to which the second compression format is applicable;

(2) Record the new character length for LZO compression, and perform LZO compression according to the new character length, the compression format selected by the anaphora distance and the corresponding compression algorithm.

The first compression format is applicable and the anaphora distance of the new characters to be compressed is not greater than 1k, and the second compression format is applicable and the anaphora distance of the new characters to be compressed is greater than 1k and less than or equal to 16k.

The first byte t(0) of the first compression format is 8 bits, the highest bit is 1, and 6, 5, and 4 bits of t(0) record the value of the repetition length, 3≤repetition length≤8, 3, 2 bits Record the lower 2 bits of the anaphora distance, 1 and 0 bits record the value of the new character length when the next input is a new character and the new character length is less than or equal to 3, and the last byte u records the last 8 bits of the anaphora distance.

The first compression algorithm corresponding to the first compression format includes the following steps:

Step 1. Determine the anaphora distance of the data to be compressed. If the anaphora distance of the data to be compressed is less than or equal to 1k and the repetition length M_len ≥ 3, go to step 2. If the repetition length of the data to be compressed is less than 3, no compression is performed;

Step 2. When 3≤repetition length M_len≤8, record the value of M_len-1 in bits 6, 5, and 4 of t(0);

When 8<M_len≤263, record bits 6, 5, and 4 of t(0) as 0, respectively, and then record the value of M_len-8 in the second byte t(1);

When 263<M_len≤n*255+263, n≥1, the 6, 5, and 4 bits of t(0) are recorded as 0 respectively, and the second byte t(1) to the (n+1)th byte The 8 bits of t(n) are respectively recorded as 0, and the value of M_len-8-n*255 is recorded in the (n+2)th byte t(n+1);

Step 3. If the next input data is a new character and the new character length is less than or equal to 3, the value of the new character length is recorded in the 1st and 0th bits of t(0). If the new character length is greater than 3, t(0 ), the last two bits are recorded as 0.

The upper two bits of the first byte t(0) of the second compression format are set to 0, 1, respectively, and bits 5, 4, 3, 2, 1, and 0 of t(0) record the value of the repetition length, 4≤ Repeat length ≤ 65, bits 7, 6, 5, 4, 3, and 2 of the penultimate byte u respectively record the lower 6 bits of the anaphora distance, and bits 1 and 0 of u record that the next input data is a new character and the new character length When ≤3, the value of the new character length, the last byte v records the last 8 bits of the anaphoric distance.

The second compression algorithm corresponding to the second compression format includes the following steps:

Step 1. Determine the anaphora distance of the data to be compressed, when 1k<the anaphora distance of the data to be compressed≤16k and the repetition length M_len≥4, go to step 2, when the repetition length M_len<4, do not compress the data;

Step 2. When 4≤M_len≤65, record the value of M_len-2 in bits 5, 4, 3, 2, 1, and 0 of t(0);

When 65<M_len≤320, set bits 5, 4, 3, 2, 1, and 0 of t(0) to 0, respectively, and record the value of M_len-65 in the second byte t(1);

When 320<M_len≤n*255+320, the values of bits 5, 4, 3, 2, and 1 of t(0) are 0, respectively, and the second byte t(1) to the n+1th byte t( The 8 bits of n) are respectively recorded as 0, and the value of M_len-65-n*255 is recorded in the n+2th byte t(n+1).

Step 3. If the next input data is a new character and the new character length is less than or equal to 3, record the value of the new character length in the 1st and 0th bits of u. If the new character length is greater than 3, record the last two bits of u. is 0.

The advantages of the present invention compared with the prior art are:

(1) the present invention is based on the LZO algorithm, carries out statistical analysis to the bit file, improves the LZO algorithm based on the statistical results, and proposes a set of new compression formats under the premise of retaining the hash operation, and the compression format types are less divided, The judgment method is simple, and the anaphora distance is reduced without reducing the compression rate, and the compression and decompression speeds are greatly improved;

(2) The present invention reduces the type of compression format and the anaphora distance, so that the hardware overhead of the decompression circuit (except IO) is only 35% of the LZO algorithm, the SRAM refresh frequency is 3 times that of the traditional LZO algorithm, the working clock frequency is increased, and the solution The compression decoding clock cycle is reduced, which is more convenient for hardware implementation and aerospace applications, and has good use value.

Description of drawings

Fig. 1 is the flow chart of the existing LZO compression algorithm;

Fig. 2 is 5 kinds of LZO compression formats corresponding to the existing LZO compression algorithm;

Fig. 3 is the compression format 1 designed by the method of the present invention;

Fig. 4 is the operation flow of compression format 1;

Figure 5 is the compression format format 2;

Fig. 6 is the operation flow of compression format 2;

Fig. 7 is the new character encoding format of the algorithm of the present invention;

Fig. 8 is the operation flow of the new character encoding format;

Fig. 9 is the compression algorithm design flow chart corresponding to the method of the present invention;

Fig. 10 is the decompression algorithm design flow chart corresponding to the method of the present invention;

11 is a block diagram of a decompression circuit;

FIG. 12 is a flow chart of the method for fast and low resource overhead lossless compression of bit files according to the present invention.

Detailed ways

In order to improve the compression and decompression speed of the LZO compression algorithm, reduce the hardware overhead of the decompression circuit, and improve the circuit's ability to resist single-event flipping, the present invention aims at the shortcomings of the prior art, and proposes an improved LZO compression method with fast and low resource overhead, The method of the invention follows the hash operation of the traditional LZO algorithm, and improves the compression format. The improved compression algorithm includes two compression formats, which are only distinguished by the anaphora distance; the maximum anaphora distance is reduced to 16k. The hardware overhead (excluding IO) of the improved decompression circuit of the present invention is only 35% of the traditional LZO algorithm, the RAM refresh frequency is 3 times that of the traditional LZO algorithm, the compression speed is increased by 18%, the decompression speed is increased by 37%, and the compression rate is reduced by 0.3 % or less.

As shown in FIG. 12, the design flow of a fast and low resource overhead improved LZO compression method of the present invention includes the following steps:

(1) Research the lossless compression technology and choose the appropriate compression algorithm as the basis. Learn about the types of lossless compression algorithms available today and their advantages and disadvantages. The dictionary encoding algorithm theoretically overcomes the problem that other algorithms may rebound the compression rate, and brings about a higher compression rate. The present invention is based on the dictionary encoding algorithm for research.

(2) Study the LZO compression algorithm and analyze its advantages and disadvantages. The traditional dictionary encoding has to compare with the characters in the dictionary one by one, so the compression speed of dictionary encoding is very slow. The LZO algorithm is based on the traditional dictionary compression algorithm, and uses a hash table to record the dictionary data in the sliding window, so that the search complexity is always constant, and the compression speed is greatly improved. However, the LZO algorithm has 5 different compression formats, and the maximum anaphora distance is 48k, which limits the compression and decompression speed of the LZO algorithm, and brings a large hardware overhead when the decompression circuit is implemented, which is not conducive to aerospace. application.

(3) Select a large number of bit files in actual work as samples, and count the law of the anaphoric distance of the data in the bit files.

(4) Analysis of the five LZO compression formats and the statistical results of the bit file, and the refined design of the compression format ensures the compression rate while improving the algorithm speed and theoretically reducing resource consumption.

(5) Design the compression software of the algorithm of the present invention, and verify the compression ratio and compression speed of the algorithm.

(6) Design the decompression software of the algorithm of the present invention, and verify the correctness of the algorithm and the decompression speed in combination with the compression software.

(7) Design the hardware circuit and FPGA implementation of the algorithm, and verify the hardware implementation and resource utilization of the decompression algorithm.

The specific design method of the method of the present invention comprises the following steps:

(1) Analyze the five compression formats of the LZO algorithm and the characteristics of the bit file data, and design an optimization scheme for the compression format;

Format 2 and Format 4, Format 3 and Format 5 have the same encoding method of the first character format, the difference is in judging the repetition length. Therefore, the method of the present invention combines the compression format 2 and the format 4, and the format 3 and the format 5, thereby making the compression and decompression more convenient, reducing the decompression hardware overhead and improving the compression and decompression speed. Statistical anaphora distance, more than 50% of the bit files have anaphora distance less than 1k, and this anaphora distance less than 1k can be compressed according to format 1 and format 4 according to different repetition lengths. The compression result of the first compression format is 2 bytes, while the 4th compression format compresses the result at least 3 bytes. Therefore, it is very effective to compress as much data as possible according to the first compression format to improve the compression rate.

The maximum anaphora distance is 48k, so that at least 48k deep RAM is required to store the decompressed data during decompression to ensure that the compressed data is correctly decompressed. In order to improve the compression and decompression speed, reduce the hardware overhead of the decompression circuit, and improve the circuit's anti-single event flipping capability, the present invention starts from reducing the anaphora distance of the compression format. Since the depth of the hash table is 16k, the hash table will be updated when a maximum of 16k data is read during data compression. At the same time, more than 95% of the bit files have an anaphoric distance of less than 16k. Therefore, the present invention also reduces the anaphoric distance to 16k. Compression formats 3 and 5 can be removed without excessive compression loss.

Combined with the above analysis, the method of the present invention obtains a simplified compression format encoding, that is, the compression format is determined only by the anaphora distance, there are only two compression formats, and the anaphora distance is less than or equal to 16k.

(2) Combined with the above analysis, design a fast and low resource overhead compression algorithm encoding format

Figure 3 shows the first of the two compression formats of the method of the present invention, that is, when the anaphoric distance is less than or equal to 1k, the highest bit (7th bit) of the first byte t(0) of the compression format is The value is 1, the first character is greater than or equal to 128 when decompressing; the 6, 5, and 4 bits of t(0) record the value of the repetition length, 3≤the repetition length (M_len)≤8; the 3 and 2 bits of t(0) Used to record the value of the lower 2 bits of the anaphora distance; bits 1 and 0 of t(0) are used to record the value of N_len when the next input data is a new character (N_len), and N_len≤3; the last byte u is used to record the last 8 bits of the anaphora distance; the number of bytes between t(0) and u is ≥ 0, which is determined by the repetition length. The detailed compression operation flow is shown in Figure 4.

As shown in Figure 4, t(0) is the first byte of the compressed format, M_len is the repetition length (compressed character length), u is the last byte of the compressed format, N_len is the new byte length of the next input, n is the number of 0 bytes between t(0) and u. The anaphora distance of compression format 1 is 10 bits, the range of the anaphora distance is less than or equal to 1k, and the anaphora distance is reduced by 1 and recorded in the offset of the compression format. The repetition length is not limited, but when M_len is less than 3, the data will not be compressed. When M_len is greater than or equal to 3 and less than or equal to 8, M_len minus 1 is recorded in 3 bits of length in the first byte, and the compression result of this compression format is 2 bytes. ; When M_len is greater than 8, the 3 bits of length in the first byte are all 0, and the second byte is M_len minus 8; if M_len minus 8 is still greater than 255, then the second byte is all zero, and the third byte is all zero. byte is M_len minus 8 and then minus 255... and so on. The last two bits of the first byte are used to store the new character length information. When the next input data is a new character and N_len is less than or equal to 3, the last two bits of the first byte t(0) record the length, when N_len When greater than 3, the last two bits of t(0) are 00. The compression format determination method is that the first character is greater than 128.

Step 1: If the anaphora distance (M_off) is less than or equal to 1k, and the repetition length (M_len) is greater than or equal to 3, the repeated characters of this segment are compressed according to the first compression format; (M_len)<3, the segment of characters is not compressed.

The first 2 bits of the value of M_off-1 are recorded in bits 3 and 2 of the first byte t(0), and the last 8 bits are recorded in the last byte u of the compressed format.

Step 2: When 3≤M_len≤8, the value of (M_len-1) is recorded in bits 6, 5, and 4 of t(0);

When 8<M_len≤263, the values of bits 6, 5, and 4 of t(0) are respectively 0, and the value of M_len-8 is recorded in the second byte t(1);

When 263＜M_len≤n*255+263(n≥1), the values of bits 6, 5, and 4 of t(0) are 0 respectively, and the values of 8 bits of the second byte t(1) are all 0... The values of the 8 bits of the (n+1)th byte t(n) are all 0, and the value of M_len-8-n*255 is recorded in the (n+2)th byte t(n+ 1) in.

Step 3: The next input data is a new character (N_len), and when N_len≤3, the value of N_len is recorded in the 1st and 0th bits of t(0); when N_len>3, the last of t(0) Two bits are 00. Repeated characters are compressed according to the first compression format.

Figure 5 shows the second of the two compression formats of the algorithm of the present invention, that is, when the back index distance is greater than 1k and less than or equal to 16k, the highest bit and the penultimate second of the first byte t(0) of the compression format The values of the bits (the 7th bit and the 6th bit) are 0 and 1. When decompressing, the determination method is that the first character is greater than or equal to 64; bits 5, 4, 3, 2, 1, and 0 of t(0) record the value of the repetition length, 4≤repetition length (M_len)≤65; bits 7, 6, 5, 4, 3, and 2 of the penultimate byte u are used to record the value of the lower 6 bits of the anaphora distance; bits 1 and 0 of u are used for Record the value of N_len when the next input data is a new character (N_len) and N_len≤3; the last byte v is used to record the last 8 bits of the anaphora distance; the number of bytes between t(0) and u≥ 0, determined by the repeat length. The detailed compression operation flow is shown in Figure 6.

As shown in Figure 6, t(0) is the first byte of the compressed format, M_len is the repetition length, u is the penultimate byte of the compressed format, v is the last byte of the second compressed format, and N_len is the next The new byte length of the input, n is the number of 0bytes between t(0) and u. The anaphora distance of the second compression format is 14 bits, and the range of the anaphora distance is less than or equal to 16k, which is recorded in the offset of the last two bytes after subtracting 1. The repetition length is not limited, but when M_len is less than 4, the data will not be compressed. When M_len is greater than or equal to 4 and less than or equal to 65, the repetition length minus 2 is recorded in 6 bits of length in the first byte; when M_len is greater than 65, the first The 6 bits of length in a byte are all zero, and the second bit is M_len minus 65; if M_len minus 65 is greater than 255, then the second byte is all zero, and the third byte is M_len minus 65 and then minus 255 ……And so on. When M_len is less than 65, the compressed characters are 3bytes. The determination method is that the first character is greater than or equal to 64. The last two bits of u are used to store new character length information. When the next input data is a new character and N_len is less than or equal to 3, the last two bits of u record the length. When N_len is greater than 3, the last two bits of u are 00.

Step 1: If the anaphora distance is 1k<(M_off)≤16k, and the repetition length (M_len)≥4, this segment of repeated characters is compressed according to the second compression format; (M_len)<4 does not compress this segment of characters.

The first 6 bits of the value of M_off-1 are recorded in the 7, 6, 5, 4, 3, and 2 bits of u, and the last 8 bits are recorded in the last byte v of the compressed format.

Step 2: When 4≤M_len≤65, the value of M_len-2 is recorded in bits 5, 4, 3, 2, 1, and 0 of t(0);

When 65<M_len≤320, the values of bits 5, 4, 3, 2, 1, and 0 of t(0) are respectively 0, and the value of M_len-65 is recorded in the second byte t(1);

When 320＜M_len≤n*255+320(n≥1), the values of bits 5, 4, 3, 2, and 1 of t(0) are 0, respectively, and the values of 8 bits of t(1) are all 0... The values of the 8 bits of the (n+1)th byte t(n) are all 0, and the value of M_len-65-n*255 is recorded in the (n+2)th byte t(n+ 1) in.

Step 3: The next input data is a new character (N_len), and when N_len≤3, the value of N_len is recorded in the 1st and 0th bits of u; when N_len>3, the last two bits of u are 00. Repeated characters are compressed in the second compression format.

Figure 7 is the new character format of the algorithm of the present invention, first record the new character length, the number of bytes occupied by the new character length is determined by the new character length, after completing the recording of the new character length, record the new characters input in turn. The detailed compression operation flow is shown in Figure 8.

As shown in Figure 8, n_len is the new character length. For a new character string, the present invention first calculates how many new characters there are. When n_len is less than 4, if the anaphoric distance is greater than 1k, the last two bit records of the penultimate byte of the above compression format 2 will be used, If the anaphoric distance is less than or equal to 1k, it will be recorded with the last two bits of the first byte of the above compression format 1. When n_len is 4 to 66, first subtract 3 from length and record it in the first byte; if the length of the new character is greater than 66, record 0 in the first byte, and then record the difference between the length of the new character minus 66 in the first byte In two bytes; if it is still greater than 255 after subtracting 66, then record a 0 after the first 0, and subtract 255 from the difference to get a new difference. If it is less than 255, record it in the third byte. If it is greater than 255, record a 0 and then continue to subtract 255 and compare with 255. When the last difference is less than 255, record the last difference. After recording the number of new characters, start recording new characters. The determination method is that the first character is less than 64.

Step 1: Determine whether the character type of the input string is a new character, and calculate the new character length (n_len) if it is a new character.

Step 2: According to the size of n_len, select an appropriate format and record the value of n_len.

When n_len≤3, record n_len in the previous compression format;

When 3<n_len≤66, record (n_len-3) in the first byte n0 of the new character format;

When 66<n_len≤321, n0=00000000, the second byte n1=n_len-66;

When 321<n_len≤321+n*255(n≥1), n0=00000000, n1=00000000... nn=00000000, n(n+1)=n_len-66-n*255.

Step 3: Output new characters of corresponding length.

In the compressed bit file, new characters and compressed characters appear alternately, and the compaction judgment condition can improve the compression rate of the bit file.

(3) The overall design of the compression and decompression algorithm, and verify the correctness, compression rate and rate of the algorithm:

The overall design of the compression part of the algorithm of the present invention is shown in Figure 9:

Step 1: Read the length of the bit file to determine whether the data is over.

Step 2: The first 4 bytes of the bit file do not do any processing, continue to read the data, and record the index in the hash table.

Step 3: Character type judgment.

The next 4 bytes of data are hashed, and the data index is taken from the hash table according to the calculated hash value, and the corresponding character is found through the index and compared with the character for the hash operation. If they are the same, it means that the data is in the hash table. , not a new character, update the character index in the hash table, continue to read data (1 byte each time), repeat the above operations until the read data is not in the hash table, if the read repetition length is less than 3 or repeated If the length is less than 4 and the anaphora distance is greater than 1k, it will be treated as a new character, and skip to step 4; otherwise, skip to step 6. If they are different, do the second hash operation and compare the index value stored in the hash address. If they are the same, continue to read the data and repeat the above operations until the read data is not in the hash table. If the repeat length is less than 3 or the repeat length is less than 4 and the anaphora distance is greater than 1k, it will be treated as a new character, and skip to step 4; otherwise, skip to step 6.

Step 4: Record the number of new characters and encode according to the new character length format

Step 5: Record the new characters, after completing the recording of the number of new characters, record the new characters thereafter. Continue reading in data.

Step 6: Calculate the length of repeated characters and the anaphora distance, and compress the data. If the anaphora distance is less than or equal to 1k, use the first compression format to compress the data, and skip to step 7; otherwise, use the second compression format to compress the data and skip to step 8.

Step 7: 1st Compression Format Encoding

Step 8: 2nd Compression Format Encoding

Step 9: Determine whether the compression is over, output the data and the data length when it is over, or continue to read in the data and repeat the above operations.

The overall design of the decompression part of the algorithm of the present invention is shown in Figure 10:

Step 1: Read the length of the bit file to determine whether the data is over.

Step 2: Judgment of the first character.

If the first character 0≤t(0)<64, it is judged as a new character, and jumps to step 3. Otherwise, it is judged as a repeated character, and jumps to step 5.

Step 3: Calculate the new character length

If 0<t(0)<64, the new character length is equal to t(0)+3 (t(0) to t(n) record the new character length information);

If t(0)=0, when t(1) is not equal to 0, the new character length n_len=66+t(1);

If t(0)=0, when t(1)=0, continue to read the following numbers until t(n)≠0, n_len=(n-1)*255+66+t(n).

Step 4: Record the new character

Record new characters according to the number of new characters

Step 5: Decompress the compressed data

If t≥128, the data is compressed according to the compression format 1, and the repetition length and the anaphora distance are calculated according to the corresponding compression format, and then jump to step 6.

If 64≤t<128, and the data is compressed according to the compression format 2, calculate the repetition length and the anaphora distance according to the corresponding compression format, and skip to step 7.

Step 6: Determination of new character information in compression format 1

If the last two digits of the first byte are not equal to 0, it is the new character length. After decompressing the data, go to step 4. Otherwise, skip to step 8.

Step 7: Judgment of new character information in compression format 2

If the last two digits of the second-to-last byte are not equal to 0, it is the new character length. After the data is decompressed, go to step 4. Otherwise, skip to step 8.

Step 8: Determine whether the compression is over, and output the data and data length when the compression is over, otherwise continue to read in the data and repeat the above operations.

The compression and decompression software is designed on the Visual Studio 2008 platform using C language, and performs compression and decompression operations on 26 sets of bit files generated in actual work. The compression rate is greater than 50%, and the average compression rate is 67.06%. 67.21%, the average compression rate decreased by 0.15%, the compression rate of 26 groups of bit files did not decrease by more than 0.3% compared with the LZO compression rate; the compression rate increased by 18%, and the decompression rate increased by 37%.

(5) The present invention decompresses part of the circuit design, and verifies the function, resource utilization rate and operating frequency;

The bit file is compressed by software, the compressed result is uploaded to the satellite, and the decompression function is realized on the satellite. The bit file compression can be realized on the ground, without FPGA, and only needs to be realized on the computer with the software developed based on the C language of the present invention. The decompression is realized on the satellite, and the FPGA circuit needs to be designed. The basic circuit block diagram is shown in Figure 11:

The circuit includes a new character decoding module, a compressed character decoding module, 1 read and 1 write SRAM16384x8, and an output control module. When data is entered, the first thing to do is to determine whether the data type is a new character or a repeated character. If it is a new character, calculate the length of the new character and output the new character directly. At the same time, these new characters should be written to the SRAM in sequence starting from address 0; if it is a repeated character, determine what compression format it is, and then calculate the anaphoric distance and repetition length. , decompress and output the data by fetching the number from the SRAM through the anaphora distance and repetition length. Due to the uncertainty of the length of the decompressed data and the number of new characters, a judgment signal for valid output data is designed in the output part of the circuit, and the output result is valid when the data is high. Similarly, by designing a feedback circuit to control the input signal, only after the decompression of a certain segment of compressed characters is completed, the characters can continue to be input.

Due to the uncertainty of the character length, new character length and compressed data of different compression formats, a large amount of control logic is required in each module and between modules to make decisions. The decision logic increases several times with the increase of the number of compression formats, and the decoding cycle also increases Therefore, the operating frequency decreases with the increase, so the reduction of the compression format has a good optimization on the hardware overhead and timing overhead of the decompression circuit.

The access time of the SRAM increases as its depth increases, and the SRAM depth of the present invention is only 1/3 of the SRAM depth of the LZO compression algorithm, thus increasing the maximum operating frequency of the circuit. At the same time, the data in the SRAM is refreshed every 16384 clock cycles, and the refresh frequency is three times that of the SRAM refresh frequency of the LZO algorithm, which reduces the risk of the onboard circuit SEU.

The decompression circuit of the present invention is verified by selecting xc4vsx55-12ff1148 device on the ISE9.2i platform. The utilization rate of the trigger resource of the present invention is 1%, the LUT resource utilization rate is 1.3%, the slice resource utilization rate is 2%, and the RAM resource utilization rate is 2%. The rate is 2%, the resource usage of IO is 3%, and the operating frequency is 138.1MHz. Compared with the LZO algorithm, in addition to the IO resource utilization rate of the present invention is comparable, the resource utilization rate of other devices is about 1/3, and the clock frequency is also greatly improved.

The content not described in detail in the specification of the present invention belongs to the well-known technology of those skilled in the art.

Claims (4)

1. an improved LZO compression method of fast and low resource overhead, is characterized in that comprising the steps: (1) Constructing the first compression format and the corresponding first compression algorithm, the second compression format and the corresponding second compression algorithm for compressing the new character by the LZO compression method according to the anaphoric distance; the first compression format is applicable and The anaphora distance of the new character to be compressed is smaller than the anaphora distance of the new character to be compressed to which the second compression format is applicable; (2) Record the new character length for LZO compression, and perform LZO compression according to the compression format selected by the new character length, the anaphora distance and the corresponding compression algorithm; The first byte t(0) of the first compression format is 8 bits, the highest bit is 1, and 6, 5, and 4 bits of t(0) record the value of the repetition length, 3≤repetition length≤8, 3, 2 bits Record the lower 2 bits of the anaphora distance, 1 and 0 bits record the value of the new character length when the next input is a new character and the new character length is less than or equal to 3, and the last byte u records the last 8 bits of the anaphora distance; The first compression algorithm corresponding to the first compression format includes the following steps: Step 1. Determine the anaphora distance of the data to be compressed. If the anaphora distance of the data to be compressed is less than or equal to 1k and the repetition length M_len ≥ 3, go to step 2. If the repetition length of the data to be compressed is less than 3, no compression is performed; Step 2. When 3≤repetition length M_len≤8, record the value of M_len-1 in bits 6, 5, and 4 of t(0); When 8<M_len≤263, record bits 6, 5, and 4 of t(0) as 0, respectively, and then record the value of M_len-8 in the second byte t(1); When 263<M_len≤n*255+263, n≥1, the 6, 5, and 4 bits of t(0) are recorded as 0 respectively, and the second byte t(1) to the (n+1)th byte The 8 bits of t(n) are respectively recorded as 0, and the value of M_len-8-n*255 is recorded in the (n+2)th byte t(n+1); Step 3. If the next input data is a new character and the new character length is less than or equal to 3, the value of the new character length is recorded in the 1st and 0th bits of t(0). If the new character length is greater than 3, t(0 ), the last two bits are recorded as 0. 2. The improved LZO compression method for fast and low resource overhead according to claim 1, characterized in that: the first compression format is applicable and the anaphora distance of the new character to be compressed is not greater than 1k, and the second compression The anaphora distance of the new characters whose format is applicable and is compressed is greater than 1k and less than or equal to 16k. 3. The improved LZO compression method for fast and low resource overhead according to claim 1 or 2, characterized in that: the upper two bits of the first byte t(0) of the second compression format are respectively set to 0 , 1, 5, 4, 3, 2, 1, 0 bits of t(0) record the value of the repetition length, 4≤the value of repetition length≤65, 7, 6, 5, 4, 3 of the penultimate byte u , 2bit respectively record the lower 6 bits of the anaphora distance, 1 and 0bit of u record the value of the new character length when the next input data is a new character and the new character length is less than or equal to 3, the last byte v records the last 8 bits of the anaphora distance bit. 4. The improved LZO compression method for fast and low resource overhead according to claim 3, wherein the second compression algorithm corresponding to the second compression format comprises the following steps: Step 1. Determine the anaphora distance of the data to be compressed, when 1k<the anaphora distance of the data to be compressed≤16k and the repetition length M_len≥4, go to step 2, when the repetition length M_len<4, do not compress the data; Step 2. When 4≤M_len≤65, record the value of M_len-2 in bits 5, 4, 3, 2, 1, and 0 of t(0); When 65<M_len≤320, set bits 5, 4, 3, 2, 1, and 0 of t(0) to 0, respectively, and record the value of M_len-65 in the second byte t(1); When 320<M_len≤n*255+320, the values of bits 5, 4, 3, 2, and 1 of t(0) are 0, respectively, and the second byte t(1) to the n+1th byte t( The 8 bits of n) are respectively recorded as 0, and the value of M_len-65-n*255 is recorded in the n+2th byte t(n+1); Step 3. If the next input data is a new character and the new character length is less than or equal to 3, record the value of the new character length in the 1st and 0th bits of u. If the new character length is greater than 3, record the last two bits of u. is 0.

Images