| Today’s society is a rapidly developing information society,and people’s lives are increasingly dependent on information technology.Information theory is the theoretical cornerstone of modern information technology,while coding theory is a specialized branch of information theory.The generation of the coding theory stems from the actual needs of modern communication systems,which mainly include channel coding and source coding.Channel coding ensures the reliability of digital information transmission and processing by increasing redundancy.Moreover,source coding improves the effectiveness of digital information storage and transmission by reducing redundancy.Since Shannon pioneered information theory,there have been many developed research results in the fields of channel coding and source coding.However,the rapid growth of massive data,the research and development of 5G mobile communication systems,the development of 8K ultra-high-definition TV technology and other practical needs always require research on channel coding and source coding to keep pace with the times.Therefore,we can only better meet the practical needs of the 5G era and the era of big data by succeeding in the theoretical research and technical application of channel coding and source coding.In addition,channel coding and source coding can also be applied to cryptography,which is beneficial for network security and privacy protection.The main research objects of this dissertation are symmetric ReedMuller(RM)codes in channel coding and universal coding of integers(UCI)in source coding.Symmetric RM code is a new channel error-correcting code proposed in this dissertation,and it is a new variant of generalized RM codes.Generalized RM codes and their variants have been extensively studied for their theoretical and practical value.Therefore,it is valuable to explore the properties of symmetric RM codes in depth.The UCI is suitable for discrete memoryless sources with unknown probability distributions and infinitely countable alphabet sizes.The UCI is a class of variable-length code,such that the ratio of the expected codeword length to max{1,H(P)} is less than or equal to a constant expansion factor KC for any probability distribution P,where H(P)is the Shannon entropy of P.The previous research focused on the case where the Shannon entropy was extremely large,while ignoring the overall compression effect of the UCI.In addition,the definition of the UCI is not perfect;that is,the compression effect is not good when faced with a universal source with an extremely small entropy.This dissertation focuses on the properties of the symmetric RM codes and the shortcomings of the existing work on the UCI.The main research work and innovative results are as follows:1.A new channel error-correcting code,termed symmetric RM code,is proposed.The basic parameters of the bivariate symmetric RM code are studied completely,meaning that the code length,the number of information bits and the minimum distance of the bivariate symmetric RM code are given.The minimum distance characterizes the error correction performance of the code.The locally-correctable property of the bivariate and the multivariable symmetric RM code is proven,and the benefits of the symmetry property in locally-correctable are analyzed.The dual codes of the symmetric RM codes are given,which provides a powerful tool for further studying the coding properties.2.A new research direction of the UCI has opened up.The range of the minimum expansion factor KC*of the optimal UCI is explored,where KC*is the infimum of the set of expansion factors.The minimum expansion factor KC*is a measure of the overall compression effect of the UCI.By proving that the expansion factor of any UCI has a nontrivial lower bound KC*≥2,the trivial lower bound KC*≥1 proved by Elias in 1975 is improved,thereby proving that the minimum expansion factor KC*of the optimal UCI is greater than or equal to 2.The constructed(?)code is currently the best UCI for the expansion factor,and it is currently the only UCI that can achieve the expansion factor equal to 2.5,thus,proving that the minimum expansion factor KC*of the optimal UCI is less than or equal to 2.5.In addition,it is proven that the length of the first codeword of the optimal UCI is 1.Furthermore,a family of asymptotically optimal UCIs with the best values of expansion factors are constructed at present.The upper and lower bounds of the minimum extension factor of several UCIs are improved.3.The concept of the generalized universal coding of integers(GUCI)is proposed,and its specific structure is given.The definition of UCI is not perfect because when the Shannon entropy is extremely small,the ratio of the expected codeword length to the Shannon entropy cannot be controlled within a constant factor.By introducing variable-to-variable length coding,the concepts of GUCI and the asymptotically optimal GUCI are proposed,thus,perfecting the definition of the UCI.A family of GUCIs and asymptotically optimal GUCIs are constructed by using run-length encoding and the UCI.The deep relationship between the UCI and the GUCI is discovered and proved.The related problems of the expansion factor of the GUCI are studied.The size of the relationship between the average codeword length of the original UCI for constructing GUCI and the average codeword lengths of the GUCI is explored.4.The cryptographic applications of symmetric RM codes and the UCI are studied.First,a private information retrieval protocol based on symmetric RM codes is presented.Second,drawing on the research results of the UCI,the measured metrics of the global property of the(2,∞)-threshold secret sharing scheme are reasonably defined,and a scheme with better global properties is proposed.In addition,the reachable lower bound of the sum of shares of the(2,n)-threshold secret sharing scheme is proved. |
