93% of the 3/4-Conjecture Is Already Verified

被引:6
作者
Aghajan, Adel [1 ]
Khosravifard, Mohammadali [1 ]
机构
[1] Isfahan Univ Technol, Dept Elect & Comp Engn, Esfahan 8415683111, Iran
关键词
3/4-Conjecture; enumerating codelength vectors; fix-free codes; Kraft sum; Yekhanin's constraint; FIX-FREE CODES; NUMBER; TREES;
D O I
10.1109/TIT.2013.2280211
中图分类号
TP [自动化技术、计算机技术];
学科分类号
0812 ;
摘要
One of the most important challenges in the context of fix-free codes is proving the 3/4-conjecture, which guarantees the existence of fix-free codewords of lengths l(1), l(2), ... , l(N) if Sigma(i=1) 2(-li) <= 3/4. Although this conjecture has not become a theorem yet, some researchers have proved the problem with some extra constraints on the codelengths. One of those, we call it Yekhanin's constraint, is Sigma(i:1i) (-) (lambda <= 1) 2(-li) >= 1/2, where lambda= min(k) l(k). In this paper, it is shown that such a constraint is not so restrictive. We prove that almost 93.8% of the N-tuple codelength vectors with Kraft sum 3/4 do satisfy Yekhanin's constraint. One can optimistically interpret this result as almost 93.8% of the road of proving the 3/4-conjecture is paved.
引用
收藏
页码:8182 / 8194
页数:13
相关论文
共 16 条
  • [1] Ahlswede R., 1996, 1st Intas Seminar on Coding Theory and Combinatorics, Thahkadzor, Armenia, P20
  • [2] [Anonymous], 2006, Elements of Information Theory
  • [3] The Number of Huffman Codes, Compact Trees, and Sums of Unit Fractions
    Elsholtz, Christian
    Heuberger, Clemens
    Prodinger, Helmut
    [J]. IEEE TRANSACTIONS ON INFORMATION THEORY, 2013, 59 (02) : 1065 - 1075
  • [4] GENERATION AND ENUMERATION OF ALL SOLUTIONS OF CHARACTERISTIC SUM CONDITION
    EVEN, S
    LEMPEL, A
    [J]. INFORMATION AND CONTROL, 1972, 21 (05): : 476 - 482
  • [5] LEVEL NUMBER SEQUENCES FOR TREES
    FLAJOLET, P
    PRODINGER, H
    [J]. DISCRETE MATHEMATICS, 1987, 65 (02) : 149 - 156
  • [6] CODES BASED ON INACCURATE SOURCE PROBABILITIES
    GILBERT, EN
    [J]. IEEE TRANSACTIONS ON INFORMATION THEORY, 1971, 17 (03) : 304 - +
  • [7] VARIABLE-LENGTH BINARY ENCODINGS
    GILBERT, EN
    MOORE, EF
    [J]. BELL SYSTEM TECHNICAL JOURNAL, 1959, 38 (04): : 933 - 967
  • [8] Harada K, 1999, IEICE T FUND ELECTR, VE82A, P2121
  • [9] An A*-Based Algorithm for Constructing Reversible Variable Length Codes with Minimum Average Codeword Length
    Huang, Yuh-Ming
    Wu, Ting-Yi
    Han, Yunghsiang S.
    [J]. IEEE TRANSACTIONS ON COMMUNICATIONS, 2010, 58 (11) : 3175 - 3185
  • [10] Sufficient conditions for existence of binary fix-free codes
    Kukorelly, Z
    Zeger, K
    [J]. IEEE TRANSACTIONS ON INFORMATION THEORY, 2005, 51 (10) : 3433 - 3444