Variable Length Unordered Codes
Laura Pezza, Luca G. Tallini, Bella Bose · IEEE Transactions on Information Theory · 2012
In an unordered code, no code word is contained in any other code word. Unordered codes are all unidirectional error detecting (AUED) codes. In the binary case, it is well known that among all systematic codes withkinformation bits, Berger codes are optimal unordered codes withr=[log2(k+1)] ≅ log2kcheck bits. This paper gives some new theory on variable length unordered codes and introduces a new class of systematic (instantaneous) unordered codes with variable length check symbols. The average redundancy of the new codes presented here isr≅ (1/2)log2k+c, wherec∈ (1.0470,1.1332) ⊆IRandk∈INis the number of information bits. Whenkis large, it is shown that such redundancy is at most 0.6069 bits off the redundancy of an optimal systematic unordered code design with fixed length information symbols and variable length check symbols; and, at most 2.8075 bits off the redundancy of an optimal variable length unordered code design. The generalization is also given for the nonbinary case and it is shown that similar results hold true.