CN106877874A - A kind of compaction coding method - Google Patents
A kind of compaction coding method Download PDFInfo
- Publication number
- CN106877874A CN106877874A CN201710036268.4A CN201710036268A CN106877874A CN 106877874 A CN106877874 A CN 106877874A CN 201710036268 A CN201710036268 A CN 201710036268A CN 106877874 A CN106877874 A CN 106877874A
- Authority
- CN
- China
- Prior art keywords
- swimming
- distance
- coding
- frequency
- code word
- 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
- 238000000034 method Methods 0.000 title claims abstract description 29
- 238000005056 compaction Methods 0.000 title claims abstract description 8
- 230000009182 swimming Effects 0.000 claims abstract description 57
- 238000007906 compression Methods 0.000 abstract description 40
- 230000006835 compression Effects 0.000 abstract description 40
- 238000012360 testing method Methods 0.000 abstract description 26
- 230000003044 adaptive effect Effects 0.000 abstract description 6
- 230000002708 enhancing effect Effects 0.000 abstract description 2
- 238000009958 sewing Methods 0.000 abstract description 2
- 238000009826 distribution Methods 0.000 description 8
- 230000000694 effects Effects 0.000 description 6
- 230000001965 increasing effect Effects 0.000 description 5
- 230000008859 change Effects 0.000 description 3
- 238000002474 experimental method Methods 0.000 description 3
- 230000008901 benefit Effects 0.000 description 2
- 238000013144 data compression Methods 0.000 description 2
- 238000004519 manufacturing process Methods 0.000 description 2
- 238000003860 storage Methods 0.000 description 2
- 230000005540 biological transmission Effects 0.000 description 1
- 230000006837 decompression Effects 0.000 description 1
- 230000007547 defect Effects 0.000 description 1
- 238000013461 design Methods 0.000 description 1
- 235000013399 edible fruits Nutrition 0.000 description 1
- 230000005611 electricity Effects 0.000 description 1
- 230000006872 improvement Effects 0.000 description 1
- 230000004048 modification Effects 0.000 description 1
- 238000012986 modification Methods 0.000 description 1
- 230000008569 process Effects 0.000 description 1
- 230000009467 reduction Effects 0.000 description 1
- 239000013598 vector Substances 0.000 description 1
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
Landscapes
- Engineering & Computer Science (AREA)
- Theoretical Computer Science (AREA)
- Compression, Expansion, Code Conversion, And Decoders (AREA)
Abstract
The invention discloses a kind of compaction coding method, using adding suffix to constitute again by flag prefixing, wherein flag is one indicating bit 0 and 1 of increase before each code word to coding, is to the coding of 0 distance of swimming or to the coding of 1 distance of swimming for distinguishing the code word；Prefix is identical during prefix is encoded with EFDR；Suffix lengths differ a N value with prefix length；Code table is worked out based on the distance of swimming；Frequency of occurrences highest distance of swimming quantity Y in the S distance of swimming of statistics past, and exchanged with the distance of swimming of 1 to Y 1 in above-mentioned code table successively by frequency of occurrences order from high to low, S and Y is natural number.The present invention is the adaptive algorithm based on original EFDR codings, by sewing difference parameter N before and after fixed codeword, according to the characteristic of incoming bit stream, assign the frequency of occurrences highest distance of swimming most short code word, voluntarily adjust to realize the lifting of compression ratio and the enhancing of adaptivity, the coding method of selection Y parameter is employed simultaneously, further improves the compression ratio and compression speed of test data.
Description
Technical field
The invention belongs to IC chip test technical field, it is related to a kind of compaction coding method, for integrated electricity
Road test data of chip is compressed.
Background technology
Increasing rapidly for testing cost is a subject matter in current IC design manufacture.On the one hand, with
The reduction of characteristic size, IP kernel and integrated gate increasing number included in integrated circuit so that required test data
Scale increases；And on the other hand, working frequency, I/O number of active lanes, transmission bandwidth, the storage capacity of auto testing instrument (ATE) are but
Increase limited.Contradiction between the two is to cause the testing time to increase, the main cause that testing cost rises.
It is a kind of method that can effectively solve the contradiction that test data is compressed.Current test data compressing method master
It is divided three classes：Compression method based on linear decompression architecture, the compression method based on broadcast scan and the compression based on coding
Method.
Wherein the test data in test set is divided into multiple symbols by code compression method mainly for given test set
(character string), then each symbol is substituted with a new code word, the data after compression are formed, storage is in the ate.Compression coding side
Method is broadly divided into two classes, and one type is the coding method based on the distance of swimming, and its general principle is to connecting in original test data
The length (the referred to as distance of swimming) of continuous 0 or 1 is encoded；Another kind of is the coding method based on data block, and it is by initial data
Fixed length or elongated data block are divided into, the frequency of occurrences according to different pieces of information block is encoded, high-frequency data block is assigned
Give shorter code word.
The code compression method of the distance of swimming is currently based on, is proposed according to the run distribution situation of whole test set,
Do not account between the different test vectors of test set, run distribution has greatest differences.
The initial coding method based on the distance of swimming is FDR codings, is to solve original fixed run length coding in short trip
Inferior position during journey and propose.FDR codings are that an indicating bit is increased before each code word, are to 0 for distinguishing the code word
The coding or the coding to 1 distance of swimming of the distance of swimming, scope is expanded compared to the FDR codings for 0 distance of swimming.
EFDR codings are a kind of important code compression methods based on the distance of swimming.EFDR codings are referred to as FDR codings
Extended code, increased bit-identify position on the basis of FDR codings, and 0 represents that 1 expression is to 1 Run- Length Coding to 0 Run- Length Coding.By
In can be simultaneously to two kinds of Run- Length Codings, therefore by being suitably filled with to independent bit X, the distance of swimming sum of EFDR codings can be much small
Encoded in the FDR for being based only upon 0 distance of swimming, its compression ratio also improves a lot than FDR codings.
However, the advantage of EFDR is embodied in the more code stream of the distance of swimming long, once the distribution of run length is different, compression
Effect can be greatly reduced.Such as EFDR codings are applied to and change on frequently code stream, because the short distance of swimming is especially more, the code after coding
Word is possibly even than more than original data, it is impossible to play the effect of coding.
For this defect, AEFDR (Adaptive EFDR) codings are proposed.AEFDR is encoded on the basis of EFDR
Parameter N is increased, the length difference of prefix of code word and suffix is represented.So, according to the run distribution of input code flow, by selecting to close
Suitable N values just can obtain ideal effect in different input code flow compressions.AEFDR (Adaptive EFDR) is compiled
The average compression ratio of the more former EFDR codings of code has certain raising.
With being increasingly modified for integrated circuit fabrication process, still need to further to improve to the compression ratio of test data of chip and
Compression speed.The present invention is exactly further improved to chip testing number on the basis of AEFDR (Adaptive EFDR) codings
According to compression ratio and compression speed.
The content of the invention
The purpose of the present invention is just being directed to EFDR codings and is being difficult to obtain good compression effectiveness when run distribution is different
Shortcoming, employs the method for sewing length difference N values before and after fixing, and chooses a number of distance of swimming and simultaneously counts the frequency of occurrences, compression effect
Fruit is substantially improved rapidly.
The invention provides a kind of compaction coding method, coding is used and adds suffix to constitute again by flag prefixing, wherein
Flag is one indicating bit 0 and 1 of increase before each code word, is the coding to 0 distance of swimming for distinguishing the code word
Or to the coding of 1 distance of swimming；
Prefix is identical during prefix is encoded with EFDR；
Suffix lengths differ a N value with prefix length；
Code table is worked out based on the distance of swimming；
Statistics frequency of occurrences highest distance of swimming quantity Y in the S distance of swimming in the past, and by frequency of occurrences order from high to low according to
The secondary distance of swimming with 1 to Y-1 in above-mentioned code table is exchanged, and S and Y is natural number.
Preferably, N values are 0 or 1.
The present invention is the adaptive algorithm proposed based on original EFDR codings, by before and after the code word for fixing the adaptive algorithm
Sew difference parameter N, according to the characteristic of incoming bit stream, assign the frequency of occurrences highest distance of swimming most short code word, voluntarily adjust and
Realize the lifting of compression ratio and the enhancing of adaptivity.
Using further lifting IC chip test data compression rate of the invention, compression ratio is at least reachable after tested
More than 10%.Simultaneously because employing the coding method of selection Y parameter, compression ratio and the compression of test data are further improved
Speed.
Brief description of the drawings
Fig. 1 is the histogram of the random distances of swimming of 5-50 in embodiments of the invention；
Fig. 2 is that AEFDR true form tables are converted to new code table of the invention；
Fig. 3 is that the compression ratio of the random distances of swimming of 1-30 that the present invention is encoded with AEFDR compares figure.
In chart：Run-length is the distance of swimming；Coding is coding；Compression Ratio are compression ratio.
Specific embodiment
The present invention is described in further detail below in conjunction with embodiment：
The shortcoming that compaction coding method of the invention is encoded again for EFDR, i.e., be difficult to take when run distribution is different
All good compression effectiveness, remain EFDR coding simultaneously to 0 and 1 Run- Length Coding the characteristics of, while also used for reference AEFDR can
The advantage of code stream that run distribution is unknown or changes over time is applied to by its coded system, further improves test data
Compression ratio.
Therefore, essential characteristic of the coding with original EFDR codings of the invention, is also to use to be added again by flag prefixing
Suffix is constituted.Wherein, flag is one indicating bit 0 and 1 of increase before each code word, is to 0 distance of swimming for distinguishing the code word
Coding or to the coding of 1 distance of swimming.Prefix is identical during prefix is encoded with EFDR, for different group Ak(k=1,2,3), it is preceding
Sew coding (k-1) individual 1 that by k subtract 1 and one 0 is constituted.
Suffix lengths differ a fixed N value with prefix length in the present invention.In coding schedule, the run length of starting is
1, corresponding start code length is (3+N) position, and the Run- Length Coding length of same group is constant, is compiled across the adjacent distance of swimming of group
Code length increment is 2；Each group AkIn, comprising run length number be 2k+NIt is individual.
Under these conditions, code table is worked out based on the distance of swimming.
Statistics frequency of occurrences highest distance of swimming quantity Y in the S distance of swimming in the past, and by frequency of occurrences order from high to low according to
The secondary distance of swimming with 1 to Y-1 in above-mentioned code table is exchanged, and S and Y is natural number.
Here with the characteristics of the extremely short distance of swimming frequency of occurrences 1 is not general high, frequency of occurrences highest is assigned
The most short code word of the distance of swimming, improves greatly compression ratio very much.As it is desirable that the corresponding code word of the frequency of occurrences highest distance of swimming is as far as possible short, i.e.,
Wish that the code word that the distance of swimming in true form table is 1 is as short as possible, so choosing less N values.Effect is preferable when N typically takes 0 or 1.Y value
Compression ratio is bound to be substantially improved when larger, but time loss is also larger, so needs make balance in test experiments.
Embodiment
For a better understanding of the present invention, the present invention is elaborated in conjunction with specific test experiments.
Experiment is chosen by the distance of swimming from 1 code stream at random to 30 as test benchmark (benchmark), respectively using AEFDR
EFDR codings (selected N=0) of coding and Y parameter of the present invention.
During specific selection Y value, distance of swimming change at random is set as 5 to 50, every kind of trip is counted in the distance of swimming sequence of S=500
The occurrence number of journey, can obtain run distribution, as shown in Figure 1.
With reference to the accompanying drawings 1, the most distance of swimming of occurrence number is can obtain after being ranked up by distance of swimming occurrence number (frequency) is
15, secondary is generally 47,36, by that analogy.It is concise explanation principle, Y=3 is taken in this example, successively by 15,47,36 distances of swimming and original
Preceding 3 distances of swimming are exchanged in code table (N=0), and particular content refers to accompanying drawing 2.
Fig. 3 shows that the compression ratio of the random distances of swimming of 1-30 that the present invention is encoded with AEFDR compares figure.
From compression ratio shown in Fig. 3 relatively can be seen that Y it is smaller when, employ the compression effectiveness of coding method of the present invention
Compression effectiveness with AEFDR coding methods is close.But since Y=5, the compression effectiveness of coding method of the present invention is lifted very
Hurry up, it is almost linear.And when Y is more than 30, curve maintain an equal level because only have in the S distance of swimming for being counted 30 kinds it is different
The distance of swimming, code table no longer changes, and compression effectiveness remains unchanged.
Y value hour can be seen that by above-mentioned test, compression coding effect of the invention is almost identical with AEFDR codings, with
Y value must increase, and coding method compression effectiveness of the invention is lifted rapidly, and best compression ratio can reach 10%.
It is obvious to a person skilled in the art that the invention is not restricted to the details of above-mentioned one exemplary embodiment, Er Qie
In the case of without departing substantially from spirit or essential attributes of the invention, the present invention can be in other specific forms realized.Therefore, no matter
From the point of view of which point, embodiment all should be regarded as exemplary, and be nonrestrictive, the scope of the present invention is by appended power
Profit requires to be limited rather than described above, it is intended that all in the implication and scope of the equivalency of claim by falling
Change is included in the present invention.Any reference in claim should not be considered as the claim involved by limitation.
Moreover, it will be appreciated that although the present specification is described in terms of embodiments, not each implementation method is only wrapped
Containing an independent technical scheme, this narrating mode of specification is only that for clarity, those skilled in the art should
Specification an as entirety, the technical scheme in each embodiment can also be formed into those skilled in the art through appropriately combined
May be appreciated other embodiment.
The description to embodiment the invention is not restricted to more than, those skilled in the art according to disclosure of the present invention,
The improvement and modification that need not be carried out by creative work on the basis of the present invention, all should protection scope of the present invention it
It is interior.
Claims (2)
1. a kind of compaction coding method, it is characterised in that：
Coding is used and adds suffix to constitute again by flag prefixing, wherein
Flag is one indicating bit 0 and 1 of increase before each code word, for distinguish the code word be to the coding of 0 distance of swimming or
To the coding of 1 distance of swimming；
Prefix is identical during prefix is encoded with EFDR；
Suffix lengths differ a N value with prefix length；
Code table is worked out based on the distance of swimming；
Statistics frequency of occurrences highest distance of swimming quantity Y in the S distance of swimming in the past, and by frequency of occurrences order from high to low successively with
The distance of swimming of 1 to Y-1 is exchanged in above-mentioned code table, and S and Y is natural number.
2. a kind of compaction coding method according to claim 1, it is characterised in that：
N values are 0 or 1.
Priority Applications (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| CN201710036268.4A CN106877874A (en) | 2017-01-17 | 2017-01-17 | A kind of compaction coding method |
Applications Claiming Priority (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| CN201710036268.4A CN106877874A (en) | 2017-01-17 | 2017-01-17 | A kind of compaction coding method |
Publications (1)
| Publication Number | Publication Date |
|---|---|
| CN106877874A true CN106877874A (en) | 2017-06-20 |
Family
ID=59157971
Family Applications (1)
| Application Number | Title | Priority Date | Filing Date |
|---|---|---|---|
| CN201710036268.4A Pending CN106877874A (en) | 2017-01-17 | 2017-01-17 | A kind of compaction coding method |
Country Status (1)
| Country | Link |
|---|---|
| CN (1) | CN106877874A (en) |
Cited By (1)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| CN116032293A (en) * | 2023-03-28 | 2023-04-28 | 国网山东省电力公司平阴县供电公司 | Community power safety management system with active response function |
Citations (5)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| CN1946185A (en) * | 2001-11-22 | 2007-04-11 | 松下电器产业株式会社 | Variable length coding method and variable length decoding method |
| CN101807926A (en) * | 2010-01-21 | 2010-08-18 | 上海电力学院 | Compressing and encoding method of low energy consumption SOC (System On a Chip) test data |
| US20110084858A1 (en) * | 2009-10-09 | 2011-04-14 | Shiro Suzuki | Encoding apparatus, decoding apparatus, information processing system, encoding method, and program |
| CN104038232A (en) * | 2014-05-09 | 2014-09-10 | 安庆师范学院 | Testing data compression and decompression method based on secondary exclusive-or operation |
| CN104124981A (en) * | 2014-06-26 | 2014-10-29 | 陕西凯鑫源科技有限公司 | K multi-run coding method for storage and transmission of mass information of Internet of vehicles |
-
2017
- 2017-01-17 CN CN201710036268.4A patent/CN106877874A/en active Pending
Patent Citations (5)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| CN1946185A (en) * | 2001-11-22 | 2007-04-11 | 松下电器产业株式会社 | Variable length coding method and variable length decoding method |
| US20110084858A1 (en) * | 2009-10-09 | 2011-04-14 | Shiro Suzuki | Encoding apparatus, decoding apparatus, information processing system, encoding method, and program |
| CN101807926A (en) * | 2010-01-21 | 2010-08-18 | 上海电力学院 | Compressing and encoding method of low energy consumption SOC (System On a Chip) test data |
| CN104038232A (en) * | 2014-05-09 | 2014-09-10 | 安庆师范学院 | Testing data compression and decompression method based on secondary exclusive-or operation |
| CN104124981A (en) * | 2014-06-26 | 2014-10-29 | 陕西凯鑫源科技有限公司 | K multi-run coding method for storage and transmission of mass information of Internet of vehicles |
Non-Patent Citations (1)
| Title |
|---|
| 邝继顺: "一种用于测试数据压缩的自适应EFDR编码方法", 《电子与信息学报》 * |
Cited By (1)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| CN116032293A (en) * | 2023-03-28 | 2023-04-28 | 国网山东省电力公司平阴县供电公司 | Community power safety management system with active response function |
Similar Documents
| Publication | Publication Date | Title |
|---|---|---|
| CN102353894B (en) | Method for testing SOC (System On Chip) based on reference vector and bit mask | |
| US8144037B2 (en) | Blocking for combinatorial coding/decoding for electrical computers and digital data processing systems | |
| US7990289B2 (en) | Combinatorial coding/decoding for electrical computers and digital data processing systems | |
| Iyengar et al. | Built-in self testing of sequential circuits using precomputed test sets | |
| CN100516911C (en) | A block-marked system chip test data compression method | |
| CN102592682B (en) | Test data encoding compression method | |
| CN101807926A (en) | Compressing and encoding method of low energy consumption SOC (System On a Chip) test data | |
| Knieser et al. | A technique for high ratio LZW compression [logic test vector compression] | |
| JP3593884B2 (en) | Encoding device and decoding device | |
| CN106877874A (en) | A kind of compaction coding method | |
| CN101163239A (en) | Novel vector quantization inceptive code book generating method | |
| CN101762782A (en) | Method for compressing built-off self-test data of system-on-a-chip and special decoding unit thereof | |
| Li et al. | On using exponential-Golomb codes and subexponential codes for system-on-a-chip test data compression | |
| CN107026651A (en) | The data compression method of two by stages and the test data storage method of integrated circuit | |
| CN109889204A (en) | Method, the accelerator card of a kind of FPGA and its compressed data | |
| Cai et al. | A novel test data compression approach based on bit reversion | |
| Ng et al. | Test vector compression via statistical coding and dynamic compaction | |
| Lin et al. | On reducing test power and test volume by selective pattern compression schemes | |
| Lu et al. | Efficient test pattern compression techniques based on complementary Huffman coding | |
| Yuan et al. | An Efficiency Partially Compatible Test Decompression Technology Oriented RL-HC | |
| Mehta et al. | Weighted Transition Based Reordering, Columnwise Bit Filling, and Difference Vector: A Power‐Aware Test Data Compression Method | |
| Mehta et al. | Combining unspecified test data bit filling methods and run length based codes to estimate compression, power and area overhead | |
| CN112073069A (en) | Test vector lossless compression method suitable for integrated circuit test | |
| Manimegalai | Efficient test vector volume reduction based on equal run length coding technique | |
| Finta et al. | Transient analysis of virtual dictionary extension compression method |
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 | ||
| RJ01 | Rejection of invention patent application after publication | ||
| RJ01 | Rejection of invention patent application after publication |
Application publication date: 20170620 |