On systematic variable length unordered codes

In an unordered code no codeword is contained in any other codeword. Unordered codes are all unidirectional error detecting (AUED) codes. In the binary case, it is well known that among all systematic codes with k information bits, Berger codes are optimal unordered codes with r = ¿log₂(k+1)¿ check bits. This paper gives some new theory on variable length unordered codes and introduces a new class of systematic unordered codes with variable length check symbols. The average redundancy of these new codes is r ¿ (1/2) log₂(¿ek/2) = (1/2) log₂ k + 1.047, where k¿IN is the number of information bits. It is also shown that such codes are optimal in the class of systematic unordered codes with fixed length information symbols and variable length check symbols. The generalization to the non-binary case is also given.