CN114614833A - Test data compression and decompression method for self-adaptive run-length coding - Google Patents
Test data compression and decompression method for self-adaptive run-length coding Download PDFInfo
- Publication number
- CN114614833A CN114614833A CN202210256585.8A CN202210256585A CN114614833A CN 114614833 A CN114614833 A CN 114614833A CN 202210256585 A CN202210256585 A CN 202210256585A CN 114614833 A CN114614833 A CN 114614833A
- Authority
- CN
- China
- Prior art keywords
- run
- length
- bit
- data
- current
- 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.)
- Pending
Links
- 238000012360 testing method Methods 0.000 title claims abstract description 48
- 230000006837 decompression Effects 0.000 title claims abstract description 33
- 238000000034 method Methods 0.000 title claims abstract description 28
- 238000013144 data compression Methods 0.000 title claims abstract description 12
- 238000007906 compression Methods 0.000 claims abstract description 31
- 230000006835 compression Effects 0.000 claims abstract description 31
- 238000012549 training Methods 0.000 claims description 14
- 230000003044 adaptive effect Effects 0.000 claims description 5
- 101150047356 dec-1 gene Proteins 0.000 claims description 4
- 238000007781 pre-processing Methods 0.000 claims description 3
- 230000008569 process Effects 0.000 description 3
- 238000013461 design Methods 0.000 description 2
- 238000010586 diagram Methods 0.000 description 2
- 230000006870 function Effects 0.000 description 2
- 238000012545 processing Methods 0.000 description 2
- 230000009467 reduction Effects 0.000 description 2
- 238000013479 data entry Methods 0.000 description 1
- 238000011161 development Methods 0.000 description 1
- 230000000694 effects Effects 0.000 description 1
- 230000010354 integration Effects 0.000 description 1
- 238000004519 manufacturing process Methods 0.000 description 1
- 238000012986 modification Methods 0.000 description 1
- 230000004048 modification Effects 0.000 description 1
- 230000009131 signaling function Effects 0.000 description 1
Images
Classifications
-
- H—ELECTRICITY
- H03—ELECTRONIC CIRCUITRY
- H03M—CODING; DECODING; CODE CONVERSION IN GENERAL
- H03M7/00—Conversion of a code where information is represented by a given sequence or number of digits to a code where the same, similar or subset of information is represented by a different sequence or number of digits
- H03M7/30—Compression; Expansion; Suppression of unnecessary data, e.g. redundancy reduction
- H03M7/46—Conversion to or from run-length codes, i.e. by representing the number of consecutive digits, or groups of digits, of the same kind by a code word and a digit indicative of that kind
Landscapes
- Engineering & Computer Science (AREA)
- Theoretical Computer Science (AREA)
- Compression, Expansion, Code Conversion, And Decoders (AREA)
Abstract
The invention provides a self-adaptive run-length coding test data compression and decompression method, which is characterized in that after irrelevant bits of test data are filled, longer 0 run or 1 run is coded into shorter code words to realize the first-stage compression function; the code word has reducibility, and the chip test is not influenced after decompression. And when the difference value of the adjacent run lengths of the filled test data is the difference value M with the largest occurrence frequency, replacing a longer code word with a shorter special code to realize second-stage compression. The difference M is determined according to the test data, when the difference of adjacent run lengths is M, no matter whether the run types are the same, the special code words can be used, the use frequency is high, and the compression efficiency is further improved. The invention can improve the compression efficiency of the test data and reduce the hardware overhead.
Description
Technical Field
The invention relates to the field of computer information, in particular to a test data compression and decompression method.
Background
Testing is an indispensable process in the field of computer information, and integrated circuit chips are no exception. The test is more and more high in the production process of the integrated circuit chip, and the test cost is increased due to the overlong test time, so that how to reduce the test time and the test cost is a problem which is very concerned by practitioners and scientific researchers in the chip industry.
With the development of integrated circuits, the degree of integration of chips is higher and higher, which greatly increases the test difficulty and the test cost. In order to reduce the test cost, the encoding mode is adopted to losslessly compress the test data, and the common encoding compression method includes Golomb, huffman encoding, FDR, EFDR, AFDR, alternate and continuous length encoding, Variable-Tail encoding, 9-value code, Variable-run encoding, mixed fixed-Variable-length code, double-run alternate encoding, mixed encoding scheme and the like. Most of the above methods adopt fixed coding to correspond to different run lengths one by one, only how to code a single run length is considered, and the relation between the run lengths is not analyzed. It can be seen from the coding tables of the FDR coding, EFDR coding, run-length-variant coding, etc., that the length of the codes in the tables tends to increase stepwise with the increase of the run length, and the longer the run length is, the longer the code length is. And therefore whether a plurality of run lengths having a certain regularity can be replaced by one special encoding, thereby improving the compression rate.
Disclosure of Invention
The technical problem to be solved by the invention is to provide a test data compression and decompression method for adaptive run length coding, which can improve the compression efficiency and reduce the test cost.
In order to solve the technical problem, the method for compressing and decompressing test data of adaptive run-length coding comprises the following steps:
A. a compression step:
(A1) constructing a training coding table:
(1.1) the coding table for training includes the following fields:
group number: expressed in a decimal number k;
run length: expressed in a decimal number L;
0 run prefix: expressed in a set of binary codes consisting of a number of 0's and 1's;
1 run prefix: expressed in a set of binary codes consisting of a number of 1's and 1's 0's;
suffix: expressed in a set of binary codes;
0 run codeword: expressed in a set of binary codes; the 0 run code word is formed by continuously arranging 0 run prefixes and suffixes;
1 run code word: expressed in a set of binary codes; the 1 run code word is formed by continuously arranging a1 run prefix and a suffix;
records in the coding table for training are arranged in an increasing mode according to the run length L and grouped, the group numbers k are arranged in an increasing mode, the run length is 1 at the minimum, and the group numbers are 1 at the minimum;
(1.2) in the code table, the k-th group contains 2kRecording, wherein the kth group 0 run prefix is composed of k 0 s and one 1, the kth group 1 run prefix is composed of k 1 s and one 0, and the kth group suffix is sequentially sequenced from the minimum k-bit binary number to the maximum k-bit binary number;
(A2) preprocessing original test data, and filling irrelevant bits to obtain a double-run sequence;
(A3) obtaining a corresponding run length sequence through the double run sequence obtained in the step (A2), sequentially subtracting the previous run length from the next run length to obtain a difference sequence, finding out a difference M with the highest occurrence frequency in the difference sequence, and setting the difference M as an optimal value;
(A4) constructing coding tables for compression
Reducing the run length of each record in the coding table for training by 1, and keeping the rest parts unchanged to obtain a coding table for compression;
(A5) reading the data obtained in the step (A2) according to bits to obtain a first run, and recording the run type and the run length of the first run; looking up a coding table for compression to obtain a code word and adding the code word into a compressed data queue;
(A6) continuously reading data to obtain a current run, if the difference value of the length of the current run and the length of the previous run is M, obtaining a special code word according to the type of the current run and adding the special code word into a compressed data queue; if the difference value between the current run and the previous run is not M, searching a coding table for compression according to the length and the type of the current run to obtain a code word and adding the code word into a compressed data queue;
if the difference value obtained by subtracting the previous run length from the current run length is M and the current run length is 0 run length, marking the current run length as a special code word 010;
if the difference value obtained by subtracting the previous run length from the current run length is M and the current run length is 1 run length, marking the current run length as a special code word 100;
(A7) and (A6) repeating the step until all the run-length codes are finished, wherein the coded data are compressed data.
The test data compression and decompression method of the self-adaptive run length coding of the invention also comprises the following steps:
B. a decompression step:
(B1) reading data to be decompressed according to bits until a 0 run or a1 run is obtained, wherein the obtained run is a prefix, recording the run type and the prefix length, calculating the suffix length according to the recorded prefix length and reading the data of the corresponding bits as a suffix;
(B2) determining whether the suffix obtained in the step (B1) is a suffix of the special codeword;
if not, adding a1 to the high order of the suffix obtained in the step (B1) to obtain a new binary number, converting the binary number into a decimal number, subtracting 2 to obtain the current run length, wherein the run type obtained in the step (B1) is the current run type, restoring a run as a decompressed run according to the current run type and the current run length, and recording the length of the decompressed run as Lx;
if yes, determining the current decompressed run length according to the length of the previous decompressed run length and the difference value M, wherein the current run length = the previous run length Lx + M; the current decompressed run type is the same as the run type obtained in the step (B1); restoring a group of runs as decompressed runs according to the obtained run types and the run lengths;
decompressing the run length of the obtained decompressed data;
(B3) and (5) repeating the steps (B1) (B2) until the decompression is completed, and obtaining complete decompressed data for chip testing.
As one implementation manner, the program implementation method of the decompression step includes:
(C1) configuring a decoder comprising a Finite State Machine (FSM), a k +1 bit counter, and a log2(k +1) bit counter, 1 m-bit register and oneAn exclusive-or gate;
(C2) and (3) decompression flow:
a) let en =1, the FSM receives the data of bit _ in. inc2 is set high. The first bit of bit _ in is sent to flag, Log2(k +1) bit counter adds 1, v is low level at this time, the output is invalid;
b) the FSM continues to receive data from bit _ in, inc2 high, with each incoming bit Log2Adding 1 to the (k +1) bit counter, and simultaneously sharing the same value with a flag value or when the bit _ in and the flag value are 0, ending the prefix input;
c) the suffix part is shifted from counter _ in into the k +1 bit counter, shift and dec2 are set high, i.e., Log for each shift into one bit of data2(k +1) bit counter is decremented by 1 until Log2The (k +1) bit counter is null, rs2 is 1, and suffix input ends;
d) if the value in the k +1 bit counter is 10 (binary), v is set as low level, the output is invalid, c is set as high level, the M-bit register is controlled to input and output, then according to the value of the difference value M, the FSM shifts in/out M0 to the M-bit register, and then step (f) is executed;
e) the m-bit register is reset and the FSM outputs 0 through d to the m-bit register. dec1 is set to high, and the k +1 bit counter is decremented by 1 each time to output a 0 until the k +1 bit counter value is 2 and rs1 is 1. Finally outputting a 1;
f) setting v as a high level to indicate that the output is effective, and outputting the result of XOR between the data of the m-bit register and a flag in sequence;
g) repeating the steps a) to f) until decompression is finished.
The technical advantages of the method are embodied in that: (1) after filling irrelevant bits of the test data, coding longer 0 run or 1 run into shorter code words to realize a first-stage compression function; the code word has reducibility, and the chip test is not influenced after decompression. (2) When the difference value of the adjacent run lengths of the filled test data is the difference value M with the largest occurrence frequency, a shorter special code is used for replacing a longer code word, the difference value M is determined according to the test data, the method is more flexible in practical application, and the compression efficiency can be further improved. (3) When the difference value of adjacent run lengths is M, the special code words can be used no matter whether the run types are the same or not, the use frequency is high, and the compression effect is further improved. By using the method, the data compression efficiency is improved, so that the chip test cost can be obviously reduced.
Drawings
FIG. 1 is a flow chart of the encoding involved in the compression step of the present invention;
fig. 2 is a diagram of a decoding circuit involved in the decompression step of the present invention.
Detailed Description
The following description will further explain embodiments of the present invention with reference to the accompanying drawings.
The self-adaptive run length coding test data compression and decompression method specifically comprises the following steps:
A. a compression step:
(A1) constructing a training coding table:
(1.1) the coding table for training includes the following fields:
group number: expressed in a decimal number k;
run length: expressed in a decimal number L;
0 run prefix: expressed in a set of binary codes consisting of a number of 0's and 1's;
1 run prefix: expressed in a set of binary codes consisting of a number of 1's and 1's 0's;
suffix: expressed in a set of binary codes;
0 run codeword: expressed in a set of binary codes; the 0 run code word is formed by continuously arranging 0 run prefixes and suffixes;
1 run code word: expressed in a set of binary codes; the 1 run code word is formed by continuously arranging a1 run prefix and a suffix;
records in the coding table for training are arranged in an increasing mode according to the run length L and grouped, the group numbers k are arranged in an increasing mode, the run length is 1 at the minimum, and the group numbers are 1 at the minimum;
(1.2) in the code table, the k-th group contains 2kA bar record, wherein the k 0 run prefix is composed of k 0 and one 1, the k 1 run prefix is composed of k 1 and one 0, and the k suffix is from the minimum k binary number to the maximumThe k-bit binary numbers are sequentially ordered;
at this point, table 1, the coding table for training, is obtained:
TABLE 1 coding table for training
Definition and description:
(1.3) the runs include a 0 run and a1 run; the 0 run refers to a binary code consisting of a plurality of continuous 0 plus 1,1 is a 0 run end mark, and the run length L refers to the number of 0; the 1 run refers to a binary code consisting of a plurality of continuous 1 s plus 10 s, 0 is a1 run end mark, and the run length L refers to the number of 1 s;
(A2) preprocessing original test data, and filling irrelevant bits to obtain a double-run sequence;
(A3) obtaining a corresponding run length sequence through the double run sequence obtained in the step (A2), sequentially subtracting the previous run length from the next run length to obtain a difference sequence, finding out a difference M with the highest occurrence frequency in the difference sequence, and setting the difference M as an optimal value;
in the step (A3), the obtaining of the corresponding run length sequence refers to reading the double run length sequence obtained in the step (a 2) in sequence, recording the run length after each run is read, and adding the run length sequence to the sequence.
(A4) Constructing coding tables for compression
And (3) reducing the run length of each record in the coding table for training by 1, and keeping the rest parts unchanged to obtain a coding table 2 for compression.
TABLE 2 coding table for compression
According to the coding table for compression, each 0 run with different lengths in the data to be compressed can uniquely correspond to one 0 run code word, and each 1 run with different lengths in the data to be compressed can uniquely correspond to one 1 run code word;
in the coding table for compression, a suffix having a run length equal to 2 multiplied by 2 plus converted into a decimal number is added. According to the formula, the run lengths corresponding to the 010 and 100 code words are both 0, but the run length is not likely to be 0 in the test data. Therefore, 010 and 100 code words are used as special code words in the compression and decompression processes.
(A5) Reading the data obtained in the step (A2) according to bits to obtain a first run, and recording the run type and the run length of the first run; looking up a table 2 to obtain a code word, and adding the code word into a compressed data queue;
(A6) continuously reading data to obtain a current run, if the difference value of the length of the current run and the length of the previous run is M, obtaining a special code word according to the type of the current run and adding the special code word into a compressed data queue; if the length difference value between the current run and the previous run is not M, looking up a table 2 according to the length of the current run and the type of the run to obtain a code word and adding the code word into a compressed data queue;
usage rules of special codewords:
if the difference value obtained by subtracting the previous run length from the current run length is M and the current run is 0 run, recording the current run as 010;
if the difference value obtained by subtracting the previous run length from the current run length is M and the current run length is 1 run length, marking the current run length as 100;
(A7) and (A6) repeating the step until all the run-length codes are finished, wherein the coded data are compressed data.
In accordance with the above rules, one skilled in the art can implement data compression in a variety of ways. Referring to fig. 1, one of the program implementation methods of step (a 5) to step (a 7) is shown below:
(A5) reading the data obtained in the step (A2) according to bits, recording the type of the data to a run type queue T [ i ], recording the length of the data to a run length queue L [ i ] when one run is read, recording the total number of the runs as n, and obtaining a difference value M through the step (A3);
defining a loop parameter i =0, defining a compressed data queue ans;
looking up table 2 according to T [ i ] and L [ i ] to obtain the first run code word, and adding the first run code word into a compressed data queue ans;
（A6）i=i+1；
if L [ i ] -L [ i-1] = = M and T [ i ] = =0, codeword 010 results;
if L [ i ] -L [ i-1] = = M and T [ i ] = =1, then codeword 100 results;
if L [ i ] -L [ i-1] < > M, looking up a table 2 to obtain a code word;
the code word obtained in this step continues to be added to the compressed data queue ans;
(A7) repeating step (a 6) until i = n-1.
The present encoding method is illustrated below by two examples:
example 1, test data preprocessed according to step (A2) is set to D1= 11111110000000001111110000001111111011111110 (44 bits), run type queue {1,0,1,0,1,1}, run length queue {7,8,5,5,6,7}, run length difference sequence {7,1, -3,0,1,1}, difference 1 occurs 3 times, so M = 1.
The first run is 11111110, the type of the run is 1 run, the run length is 7, and the code is 1110001 by looking up a table 2;
the second run is 000000001, run length 8, the difference from the previous run length is 1, equal to M, 0 run, thus encoding 010;
the third run is 111110, the run length is 5, the difference with the previous run length is not M, the type is 1 run, and the code is 11011 by looking up the table 2;
the fourth run is 000001, the run length is 5, the difference with the previous run length is not M, the type is 0 run, therefore, the code 00111 is obtained by looking up the table 2;
the fifth run is 1111110, run length 6, and the difference from the previous run length is 1, equal to the M, 1 run, thus encoding 100;
the sixth run is 11111110, the run length is 7, the difference from the previous run length is 1, equal to M, 1 run, thus encoding 100;
the final coding is finished to obtain DE1= 11100010101101100111100100 (26 bits), ratio D1The 18bits are reduced.
Example 2, test data preprocessed according to step (A2) is set to D2= 11100000000010000000000000100000111111111110 (44 bits), run type queue {1,0,0,0,1}, run length queue {3,8,13,5,10}, run length difference sequence {3,5,5, -8,5}, difference 5 occurs 3 times, so M = 5.
The first run is 1110, type 1 run, length 3, coded 11001 according to table 2;
the second run is 000000001, length 8, the difference from the previous run length is 5, equal to the M, 0 run, thus encoding 010;
the third run is 00000000000001, length 13, length difference 5 from the previous run, equal to M, type 0 run, thus encoding 010;
the fourth run is 000001, the length is 5, the difference value with the previous run is not M, and the type is 0 run, so the code 00111 is obtained by looking up the table 2;
the fifth run is 11111111110, length 10, length 5 different from the previous run, equal to the M, 1 run, thus encoding 100;
the final encoding is finished to obtain DE2= 1100101001000111100 (19 bits), ratio D2The reduction is 25 bits.
Special case processing: when the original data is divided into runs to the end, there may be cases where the runs cannot be constructed, for example, leaving the undivided data to contain only 1 or only 0. If the end of the original data cannot constitute a run, a 1-bit binary number 0 or 1 is added to the end as a run end flag. For example, the last undivided data is 11, and 1 bit 0 is added thereafter, which becomes 110; for example, when the undivided data is 00, 1 bit 1 is added to obtain 001. After processing, the invention can continuously work to complete compression coding. In the subsequent decoding step, the original end data and the added run-length end mark can be obtained by decoding, and in the chip test, the length of the test data is required, so that the last added run-length end mark cannot be read in when the test data is read, and the test result is not influenced.
B. A decompression step:
according to the method and table 2, the compressed data queue obtained in step (a 7) is composed of a plurality of groups of 0 run codewords and 1 run codewords; each group of code words comprises a prefix and a suffix, and the prefix is 0 run or 1 run, so that the prefix can be read and distinguished, and the suffix can be continuously read by subtracting one from the digit of the prefix after the prefix is read; the run length and the type before compression can be known according to the prefix and the suffix, and the decompression and the reduction can be carried out according to the prefix and the suffix; 010. 100 two special code words do not appear in the header of the compressed data, so when a special code word is read, the corresponding original data can be restored according to the special code word and the previous run length. The method comprises the following specific steps:
(B1) reading data to be decompressed according to bits until a 0 run or a1 run is obtained, wherein the obtained run is a prefix, recording the run type and the prefix length, calculating the suffix length according to the recorded prefix length and reading the data of the corresponding bit as a suffix, wherein the suffix length = prefix length-1;
(B2) determining whether the suffix obtained in the step (B1) is a suffix of the special codeword;
in the present invention, there are two special codewords "010" and "100", and the suffix is "0", and according to the step (B1), the special codeword and its prefix and suffix can be read and judged.
If not, adding a1 to the high bit of the suffix obtained in the step (B1) to obtain a new binary number, converting the binary number into a decimal number, subtracting 2 to obtain the current run length, wherein the run type obtained in the step (B1) is the current run type, restoring a run as a decompressed run according to the current run type and the current run length, and recording the length of the run as Lx; it should be noted that the decompressed run obtained in this step is not equivalent to a prefix, suffix, or code word in the code table, and although it is also embodied in a run form, only the type and decimal length are recorded in the code table.
If yes, determining the current decompressed run length according to the length of the previous decompressed run length and the difference value M, wherein the current run length = the previous run length Lx + M; the current decompressed run type is the same as the run type obtained in the step (B1); restoring a group of runs as decompressed runs according to the obtained run types and the run lengths; specifically, when the suffix is 0, if the run type is 0, a 0 run is restored; if the run type is 1, restoring a1 run;
decompressing the run length of the obtained decompressed data;
(B3) and (5) repeating the steps (B1) (B2) until the decompression is completed, and obtaining complete decompressed data for chip testing.
The program implementation method comprises the following steps:
when a binary number to be decoded is read, the run type and the prefix end mark of the current run to be decoded can be obtained, then the suffix length of the current run to be decoded can be obtained according to the end mark of the prefix, so that the suffix of the run code word can be obtained, and at this time, the current run length Lx can be obtained, specifically: and adding a1 to the high bit of the suffix binary number to obtain a new binary number, converting the new binary number into a decimal number, and subtracting 2 from the new binary number of the decimal number by the current run length Lx. And finally, storing the run length into an m-bit register. When reading the suffix "0", the run is read directly from the M-bit register and then output according to the run type and the difference M. For example, M =5, for "11001010", the first run to be decompressed is coded as 11001, the first is a1, 1 run, the prefix is 110, the suffix is 01, add 1 in the high of the suffix, get 101, (101)2=（5）105-2=3, the run length is 3, the run length after decompression is 1110, the run to be decompressed next is coded to 010, the suffix is "0", which is a suffix of a special code word, the run length is 0 according to the prefix 01, the run length minus the previous run length is M, the run length is 8, so the run length after decompression is 000000001. That is, on the premise that M =5, 8-bit compressed data "11001010" is decompressed to 13-bit data "1110000000001".
(C1) Configuration decoder
The decompression circuit is a finite state machine based design, and the circuit scale is small without large hardware cost. The decoder mainly comprises a Finite State Machine (FSM), a k +1 bit counter and a Log2(k +1) position meterThe device comprises a counter, 1 m-bit register and an exclusive-OR gate. The decoder has simple structure, is independent of the tested circuit and the test data set, and has a structural block diagram shown in FIG. 2, wherein the signal names and the corresponding functional descriptions are shown in Table 3.
Table 3 signals in decoder and corresponding functions
| Signal | Function(s) |
| bit_in | Test data entry |
| en | The enable terminal is set to 1 and indicates that the data is accepted |
| counter_in | Channel for FSM to input test data to k +1 bit counter |
| shift | Shift-in control bits for k +1 bit counter |
| dec1 | Control k +1 bit counter to decrement 1 |
| rs1 | Reset flag bit of k +1 bit counter |
| inc2 | Control Log2(k +1) bit counter incremented by 1 |
| dec2 | Log2(k +1) bit |
| rs2 | Log2(k +1) bit counter reset flag bit |
| flag | Run indicating which type is currently |
| d | Channel for FSM to input data to m-bit register |
| v | Indicating whether decoder output data is valid |
| c | Controlling input and output of m-bit register |
The decoding process of the present method will be described below with reference to fig. 2.
(C2) And (3) decompression flow:
a) let en =1, the FSM receives the data of bit _ in. inc2 is set high. The first bit of bit _ in is sent to flag, Log2(k +1) bit counter adds 1, v is low level at this time, the output is invalid;
b) the FSM continues to receive data from bit _ in, inc2 high, with each incoming bit Log2Adding 1 to the (k +1) bit counter, and simultaneously sharing the same value with a flag value or when the bit _ in and the flag value are 0, ending the prefix input;
c) the suffix part is shifted from counter _ in into the k +1 bit counter, shift and dec2 are set high, i.e., Log for every bit of data shifted in2(k +1) bit counter is decremented by 1 until Log2The (k +1) bit counter is null, rs2 is 1, and suffix input ends;
d) if the value in the k +1 bit counter is 10 (binary), v is set as low level, the output is invalid, c is set as high level, the M-bit register is controlled to input and output, then according to the value of the difference value M, the FSM shifts in/out M0 to the M-bit register, and then step (f) is executed;
e) the m-bit register is reset and the FSM outputs 0 through d to the m-bit register. dec1 is set to high, and the k +1 bit counter is decremented by 1 each time to output a 0 until the k +1 bit counter value is 2 and rs1 is 1. Finally outputting a 1;
f) setting v as a high level to indicate that the output is effective, and outputting the result of XOR between the data of the m-bit register and a flag in sequence;
g) repeating the steps a) to f) until decompression is finished.
It should be noted that, those skilled in the art can design many decompression methods according to the compression method provided by the present invention, and the embodiments of the present invention include but are not limited to the above embodiments, and those skilled in the art can make various changes and modifications according to the present invention without departing from the spirit and the spirit of the present invention, and still fall into the protection scope of the present invention.
Claims (3)
1. A test data compression and decompression method of adaptive run length coding comprises the following steps:
A. a compression step:
(A1) constructing a training coding table:
(1.1) the coding table for training includes the following fields:
group number: expressed in a decimal number k;
run length: expressed in a decimal number L;
0 run prefix: expressed in a set of binary codes consisting of a number of 0's and 1's;
1 run prefix: expressed in a set of binary codes consisting of a number of 1's and 1's 0's;
suffix: expressed in a set of binary codes;
0 run codeword: expressed in a set of binary codes; the 0 run code word is formed by continuously arranging 0 run prefixes and suffixes;
1 run code word: expressed in a set of binary codes; the 1 run code word is formed by continuously arranging a1 run prefix and a suffix;
records in the coding table for training are arranged in an increasing mode according to the run length L and grouped, the group numbers k are arranged in an increasing mode, the run length is 1 at the minimum, and the group numbers are 1 at the minimum;
(1.2) in the code table, the kth group contains 2kRecording, wherein the kth group 0 run prefix is composed of k 0 s and one 1, the kth group 1 run prefix is composed of k 1 s and one 0, and the kth group suffix is sequentially sequenced from the minimum k-bit binary number to the maximum k-bit binary number;
(A2) preprocessing original test data, and filling irrelevant bits to obtain a double-run sequence;
(A3) obtaining a corresponding run length sequence through the double run sequence obtained in the step (A2), sequentially subtracting the previous run length from the next run length to obtain a difference sequence, finding out a difference M with the highest occurrence frequency in the difference sequence, and setting the difference M as an optimal value;
(A4) constructing coding tables for compression
Reducing the run length of each record in the coding table for training by 1, and keeping the rest parts unchanged to obtain a coding table for compression;
(A5) reading the data obtained in the step (A2) according to bits to obtain a first run, and recording the run type and the run length of the first run; looking up a coding table for compression to obtain a code word and adding the code word into a compressed data queue;
(A6) continuously reading data to obtain a current run, if the length difference value between the current run and the previous run is M, obtaining a special code word according to the type of the current run and adding the special code word into a compressed data queue; if the difference value between the current run and the previous run is not M, searching a coding table for compression according to the length and the type of the current run to obtain a code word and adding the code word into a compressed data queue;
if the difference value obtained by subtracting the previous run length from the current run length is M and the current run length is 0 run length, marking the current run length as a special code word 010;
if the difference value obtained by subtracting the previous run length from the current run length is M and the current run length is 1 run length, marking the current run length as a special code word 100;
(A7) and (A6) repeating the step until all the run-length codes are finished, wherein the coded data are compressed data.
2. The adaptive run-length encoded test data compression and decompression method of claim 1, further comprising:
B. a decompression step:
(B1) reading data to be decompressed according to bits until a 0 run or a1 run is obtained, wherein the obtained run is a prefix, recording the run type and the prefix length, calculating the suffix length according to the recorded prefix length and reading the data of the corresponding bits as a suffix;
(B2) determining whether the suffix obtained in the step (B1) is a suffix of the special codeword;
if not, adding a1 to the high order of the suffix obtained in the step (B1) to obtain a new binary number, converting the binary number into a decimal number, subtracting 2 to obtain the current run length, wherein the run type obtained in the step (B1) is the current run type, restoring a run as a decompressed run according to the current run type and the current run length, and recording the length of the decompressed run as Lx;
if yes, determining the current decompressed run length according to the length of the previous decompressed run length and the difference value M, wherein the current run length = the previous run length Lx + M; the current decompressed run type is the same as the run type obtained in the step (B1); restoring a group of runs as decompressed runs according to the obtained run types and the run lengths;
decompressing the run length of the obtained decompressed data;
(B3) and (5) repeating the steps (B1) (B2) until the decompression is completed, and obtaining complete decompressed data for chip testing.
3. The adaptive run-length encoded test data compression and decompression method of claim 2, wherein said decompression step is implemented by a program comprising:
(C1) configuring a decoder comprising a Finite State Machine (FSM), a k +1 bit counter, and a log2A (k +1) bit counter, 1 m-bit register and an exclusive-or gate;
(C2) and (3) decompression flow:
a) let en =1, the FSM receives the data of bit _ in; inc2 is set to high level; the first bit of bit _ in is sent to flag, Log2(k +1) bit counter adds 1, v is low level at this time, the output is invalid;
b) the FSM continues to receive data from bit _ in, inc2 high, with each incoming bit Log2Adding 1 to the (k +1) bit counter, and simultaneously sharing the same value with a flag value or when the bit _ in and the flag value are 0, ending the prefix input;
c) the suffix part is shifted from counter _ in into the k +1 bit counter, shift and dec2 are set high, i.e., Log for each shift into one bit of data2(k +1) bit counter is decremented by 1 until Log2The (k +1) bit counter is null, rs2 is 1, and suffix input ends;
d) if the value in the k +1 bit counter is 10 (binary), v is set as low level, the output is invalid, c is set as high level, the M-bit register is controlled to input and output, then according to the value of the difference value M, the FSM shifts in/out M0 to the M-bit register, and then step (f) is executed;
e) resetting the m-bit register, and outputting 0 to the m-bit register by the FSM through d; dec1 is set to high level, the k +1 bit counter is decremented by 1 each time, and 0 is output until the value of the k +1 bit counter is 2 and rs1 is 1; finally outputting a 1;
f) setting v as a high level to indicate that the output is effective, and outputting the result of XOR between the data of the m-bit register and a flag in sequence;
g) repeating the steps a) to f) until decompression is finished.
Priority Applications (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| CN202210256585.8A CN114614833A (en) | 2022-03-16 | 2022-03-16 | Test data compression and decompression method for self-adaptive run-length coding |
Applications Claiming Priority (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| CN202210256585.8A CN114614833A (en) | 2022-03-16 | 2022-03-16 | Test data compression and decompression method for self-adaptive run-length coding |
Publications (1)
| Publication Number | Publication Date |
|---|---|
| CN114614833A true CN114614833A (en) | 2022-06-10 |
Family
ID=81862547
Family Applications (1)
| Application Number | Title | Priority Date | Filing Date |
|---|---|---|---|
| CN202210256585.8A Pending CN114614833A (en) | 2022-03-16 | 2022-03-16 | Test data compression and decompression method for self-adaptive run-length coding |
Country Status (1)
| Country | Link |
|---|---|
| CN (1) | CN114614833A (en) |
Cited By (3)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| CN115955569A (en) * | 2023-03-14 | 2023-04-11 | 海伦市动物防疫检疫中心 | Monitoring video data transmission method for animal quarantine center |
| CN116170027A (en) * | 2023-04-26 | 2023-05-26 | 北京索斯克科技开发有限公司 | Data management system and processing method for poison detection equipment |
| CN116708845A (en) * | 2023-08-04 | 2023-09-05 | 佳木斯大学 | Gastrointestinal medical image communication transmission method based on 5G technology |
-
2022
- 2022-03-16 CN CN202210256585.8A patent/CN114614833A/en active Pending
Cited By (6)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| CN115955569A (en) * | 2023-03-14 | 2023-04-11 | 海伦市动物防疫检疫中心 | Monitoring video data transmission method for animal quarantine center |
| CN115955569B (en) * | 2023-03-14 | 2023-05-23 | 海伦市动物防疫检疫中心 | Monitoring video data transmission method for animal epidemic prevention quarantine center |
| CN116170027A (en) * | 2023-04-26 | 2023-05-26 | 北京索斯克科技开发有限公司 | Data management system and processing method for poison detection equipment |
| CN116170027B (en) * | 2023-04-26 | 2023-07-25 | 北京索斯克科技开发有限公司 | Data management system and processing method for poison detection equipment |
| CN116708845A (en) * | 2023-08-04 | 2023-09-05 | 佳木斯大学 | Gastrointestinal medical image communication transmission method based on 5G technology |
| CN116708845B (en) * | 2023-08-04 | 2023-10-31 | 佳木斯大学 | Gastrointestinal medical image communication and transmission method based on 5G technology |
Similar Documents
| Publication | Publication Date | Title |
|---|---|---|
| CN114614833A (en) | Test data compression and decompression method for self-adaptive run-length coding | |
| US9054729B2 (en) | System and method of compression and decompression | |
| US7099884B2 (en) | System and method for data compression and decompression | |
| EP1506619B1 (en) | Method and apparatus for data compression for the lz1 algorithm | |
| US6225922B1 (en) | System and method for compressing data using adaptive field encoding | |
| EP0903866B1 (en) | Method and apparatus for data compression | |
| US5874908A (en) | Method and apparatus for encoding Lempel-Ziv 1 variants | |
| JPH06104767A (en) | Variable length code decoder | |
| JPH0779262B2 (en) | Encoding method of compressed data | |
| US5594435A (en) | Permutation-based data compression | |
| CN104038232B (en) | Testing data compression and decompression method based on secondary exclusive-or operation | |
| CN103746706B (en) | Test data compression based on double distance of swimming alternate coded and decompression method | |
| CN104038233B (en) | Testing data compression and decompression method based on ortho-position exclusive or operation | |
| CN101202548A (en) | A double-run data encoding method | |
| CN114614832A (en) | Test data compression and decompression method based on front and back run length coding | |
| JPH05241777A (en) | Data compression system | |
| KR101023536B1 (en) | Data Lossless Compression Method | |
| CN101325418B (en) | Haffman quick decoding method based on probability table look-up | |
| CN103746704B (en) | Test data of chip transmission methods based on double distance of swimming alternate coded | |
| JPH0779265B2 (en) | Decompression method of compressed data | |
| US6762700B2 (en) | NEO method and system for lossless compression and decompression | |
| CN114866091A (en) | Differential coding compression and decompression method based on grouping reference numbers | |
| US20220416811A1 (en) | Deflate compression using sub-literals for reduced complexity huffman coding | |
| US6778107B2 (en) | Method and apparatus for huffman decoding technique | |
| US20080001790A1 (en) | Method and system for enhancing data compression |
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 | ||
| WD01 | Invention patent application deemed withdrawn after publication | ||
| WD01 | Invention patent application deemed withdrawn after publication |
Application publication date: 20220610 |