标题： 关于3/4猜想的无固定码——综述 显示英文标题

标题： On the 3/4-Conjecture for Fix-Free Codes -- A Survey

摘要： 在本综述中，我们关注的问题是，给定的码字长度序列是否存在一个无前缀的码。 对于给定的字母表，如果我们对每个长度，将该长度在码中的码字数量除以该长度的所有可能单词的总数，然后对码中出现的所有码字长度进行求和，就可以得到码的{\em 克劳夫特和}。 同样地，长度序列的 Kraft 和为$(l_1,..., l_n) $，由$\sum_{i=1}^n q^{-l_i} $给出，其中$q$是字母表中的字母数。 Kraft 和 McMillan 在\cite{kraft}（1956）中证明，如果长度序列的 Kraft 和小于或等于一，则存在一个具有特定长度序列的前缀码。 此外，他们还证明了对于所有（唯一可解码）码，逆命题也成立。 \footnote{在本次综述中，一个码指的是一个单词集合，使得用这些单词编码的任何消息都可以被唯一解码。 因此，今后我们省略“唯一可解码的”，只写“码”。}问题在于，Kraft 和 McMillan 的结果能否推广到其他类型的码？ 我们试图针对无前缀码的类别给出对此问题的答案。 由于任何码的 Kraft 和都小于或等于一，这回答了 Kraft-McMillan 定理第二个蕴含的问题。 因此，我们主要关注第一个蕴含。 显示英文摘要

摘要： In this survey we concern ourself with the question, wether there exists a fix-free code for a given sequence of codeword lengths. For a given alphabet, we obtain the {\em Kraftsum} of a code, if we divide for every length the number of codewords of this length in the code by the total number of all possible words of this length and then take summation over all codeword lengths which appears in the code. The same way the Kraftsum of a lengths sequence $(l_1,..., l_n) $ is given by $\sum_{i=1}^n q^{-l_i} $, where $q$ is the numbers of letters in the alphabet. Kraft and McMillan have shown in \cite{kraft} (1956), that there exists a prefix-free code with codeword lengths of a certain lengths sequence, if the Kraftsum of the lengths sequence is smaller than or equal to one. Furthermore they have shown, that the converse also holds for all (uniquely decipherable) codes.\footnote{In this survey a code means a set of words, such that any message which is encoded with these words can be uniquely decoded. Therefore we omit in future the "uniquely decipherable" and write only "code".} The question rises, if Kraft's and McMillan's result can be generalized to other types of codes? Throughout, we try to give an answer on this question for the class of fix-free codes. Since any code has Kraftsum smaller than or equal to one, this answers the question for the second implication of Kraft-McMillan's theorem. Therefore we pay attention mainly to the first implication.