OREGON STATE UNIVERSITY

You are here

On systematic variable length unordered codes

TitleOn systematic variable length unordered codes
Publication TypeConference Paper
Year of Publication2009
AuthorsPezza, L., L. G. Tallini, and B. Bose
Conference Name2009 IEEE International Symposium on Information Theory - ISIT2009
Pagination2708 - 2712
Date Published06/2009
PublisherIEEE
Conference LocationSeoul, South Korea
ISBN Number978-1-4244-4312-3
Keywordsasymmetric errors, Berger codes, unidirectional error, unordered/AUED codes
Abstract

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 =⌈ log2(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) log2(∏ek/2) = (1/2) log2 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.

DOI10.1109/ISIT.2009.5205871