Reserch On Data Coding Method Based On Combinatorics

Developing along with the information technology, data coding technology,active in various fields such as computer science, multimedia and communications, has become a basic tool and one of the basal problems to study. It now plays an important role in all kinds of studies and applications. Based on the theory of combinatorics, a new coding method---combinatorics coding is put forward in this dissertation. Due to its unique properties and advantages, it is applicable in various fields such as data compression, data secrecy, and so on. It is of great significance to information disposing, data storage, and data transmission.Combinatorics coding refers to the coding method that is based on the combinatorics theory and makes use of the relation between the space of the ordinal number and the space of the sequence. This method requires a benchmark sequence that is agreed on by the coder and the decoder. Based on the same benchmark sequence, an ordinal number corresponding to the character sequence is computed in the coding process and the primary character sequence is deduced from the ordinal number in the decoding process. Ordinal number computing is the core in the combinatorics coding technology. Therefore, the property of the ordinal number is studied in this dissertation. It argues that the value of the ordinal number lies in the benchmark sequence and the size of the ordinal number lies in the distribution of the character frequency.Because of the huge computing quantity in the combinatorics coding method, the technology of time optimization is put forward to improve the computing efficiency. At first, number system infection to ordinal number computing is studied in this dissertation. It finds out that computing word length related to number system directs ratio to computing speed in ordinal number computing. Moreover, the proportion computing method is adopted to replace the permutation and combination computing method whose computing quantity is huge. Some proportion formulas are also educed. As a result, the procedure of ordinal number computing is optimized by the proportion computing method and the computing quantity is reduced, thus advancing the ordinal number computing speed. Furthermore, some special cases are closely examined. In a word, these optimized algorithms improve the computing efficiency of the combinatorics coding method.To further improve computing efficiency, this dissertation puts forward the parallel technology. There are two kinds of parallel methods: parallel coding within the section and parallel coding among sections. For the first method, multi-thread technology is adopted and the key technology is how to split the sequence. For the second method, the primary study is made in the case of the multi-computer.The study and application of the combinatorics coding technology can be used in many fields. The character in the combinatorics coding technology that the ordinal number space is smaller than the sequence space to compress data is made use of in this dissertation. That is to say, when the saved character space from the sequence length and the ordinal number length counteracts the space occupied by the frequency table and other affixation information, the combinatorics compression can be applied. The combinatorics compression technology fully demonstrates the fact that if only repetition exists, redundancy is inevitable. To better facilitate the experiment, a suitable subsection length is required. Therefore, the research begins with the study on the distributing rule of the subsection byte frequency in stochastic file. This study is the key to the frequency table compression optimization and even to the realization of the combinatorics compression technology.The relation among the combinatorics compression, the algorithm compression, and the dictionary compression is also studied in this dissertation. The combinatorics compression is a kind of dictionary compression that bears the characteristic of the algorithm compression. It is a universal compression technology independent of the probability characteristics. It can be adopted to compress memoryless source, especially memoryless source with similar character frequencies. Theory analysis indicates that when the sequence length is big enough, the combinatorics compression comes much nearer to the compression limit than the directory compression. Cooperating with other compression methods, this compression method can make the compression efficiency approach information entropy and store as many data as possible in the given space. Consequently it can save many resources.Despite the method put forward in this dissertation, much room is left for future study in the combinatorics compression, especially in the optimization technology and the parallel technology. There is also much space for future exploration in other applications such as encryption and decryption.