• DocumentCode
    1178008
  • Title

    Sufficient conditions for existence of binary fix-free codes

  • Author

    Kukorelly, Zsolt ; Zeger, Kenneth

  • Volume
    51
  • Issue
    10
  • fYear
    2005
  • Firstpage
    3433
  • Lastpage
    3444
  • Abstract
    Two sufficient conditions are given for the existence of binary fix-free codes (i.e., both prefix-free and suffix-free). Let L be a finite multiset of positive integers whose Kraft sum is at most 3/4. It is shown that there exists a fix-free code whose codeword lengths are the elements of L if either of the following two conditions holds: i) The smallest integer in L is at least 2, and no integer in L, except possibly the largest one, occurs more than 2min(L)-2 times. ii) No integer in L, except possibly the largest one, occurs more than twice. The results move closer to the Ahlswede-Balkenhol-Khachatrian conjecture that Kraft sums of at most 3/4 suffice for the existence of fix-free codes.
  • Keywords
    Huffman codes; binary codes; source coding; Ahlswede-Balkenhol-Khachatrian conjecture; Huffman codes; binary fix-free codes; lossless source coding; reversible codes; Binary codes; Code standards; Decoding; Probability distribution; Robustness; Source coding; Standards development; Sufficient conditions; Video compression; Wireless communication; Huffman codes; Lossless source coding; reversible codes;
  • fLanguage
    English
  • Journal_Title
    Information Theory, IEEE Transactions on
  • Publisher
    ieee
  • ISSN
    0018-9448
  • Type

    jour

  • DOI
    10.1109/TIT.2005.855581
  • Filename
    1512418