变长码的组合半群理论

In coding theory, a code is called a variable-length code if the lengths of code words are not necessarily identical. Variable-length codes have very extensive applications in many areas of science and technology, and attract more and more people’s attentions. In the project, we mainly study some common used subclasses of veriable-length codes such as prefix codes, bifix codes, maximal codes, complete simple codes. We shall involve algebraic and combinatorial properties, structures and classifications of those classes of codes. The contents of this project can be partitioned into five parts. They are investigations of syntactic groups of codes; relationship among codes, infinite words and symbolic dynamics; researches of some problems on structures and algebraic closure properties of completely simple codes and some subclasses; characterizations of general maximal codes; characterizations of length distributions of some classes of codes. We shall mainly use the combined methods of algebraic theory of semigroups and combinatorial analysis to study these problems.

在编码理论中，如果一个码的所有码字的长度不一定相同，则称其为变长码。变长码在科学技术的诸多领域中有着非常广泛的应用，是一个倍受人们关注的研究对象。本项目主要对变长码中的前缀码、双缀码、极大码、完全单码等一些常见码类进行研究，主要研究其代数与组合性质、结构和分类等问题。项目的研究内容主要包括码的句法群的研究；码与无限字、符号动力学的关系；完全单码及其若干子类的结构、代数封闭性等问题的研究；一般极大码刻画；若干码类的长度分布刻画五个部分。主要用半群代数理论与组合分析相结合的方法对这些问题进行研究。

变长码一直是计算机科学中最基本的研究对象. 其理论不仅在计算机科学和数学的许多领域中有重要意义, 而且在信息化程度越来越高的现代社会中也有着广泛应用. 本项目主要利用半群、置换群等代数工具与自动机、形式幂级数、图论等组合与分析工具相结合的方法对前缀码、双缀码、极大码、完全单码、[弱] Bernoulli码等码类以及一些相关的半群进行刻画, 研究其构造与分类. 项目的研究内容主要包括码的句法结构；码与无限字、符号动力学的关系；完全单码及其若干子类的结构、代数封闭性等；一般极大码的刻画；码的长度分布刻画等. 研究所取得的主要结果如下:.(1) 对三次极大双缀码进行了系统研究, 给出了核为一致码的三次极大双缀码的构造..(2) 给出路语言的概念, 并利用它建立了三次有限极大双缀码与有向无圈图的一一对应关系, 解决了三次有限极大双缀码的计数问题..(3) 对平均长度为常数的极大前缀码进行了研究, 证明了这种码关于“语言的乘积”和“码的复合”两种运算封闭; 完全确定了二元字母表上所有平均长度为3的有限极大前缀码的构造 (平均长度为1和2的情形是平凡的), 这些有无穷多个, 被分为九个系列. .(4) 通过研究完全单码的代数与组合性质, 对完全单码与极大码、完全码、Bernoulli集、弱Bernoulli集等语言类和码类之间的关系、层次结构给出了刻画..(5) 对有限极大前缀码的长度分布数量进行研究, 给出了此数量上下界的一个估计; 给出了有限信号码、平均长度为常数的有限极大前缀码的长度分布的若干刻画..(6) 对华半群进行研究、给出了华半群及其四个子类, 以及其它五个相关半群类之间的层次关系图; 证明了可消半群是第二型强华半群, 从而推广了C. M。 Reis和石煇然关于自由半群的一个定理; 对完全正则华半群进行了详细地刻画.