A new universal coding scheme for the binary memoryless source

Abstract

A coding scheme for the binary memoryless source is presented. The scheme is an extension of a scheme discovered by Lynch and Davisson and developed by Schalkwijk, and is based upon the Schalkwijk algorithm for the Lynch-Davisson (LD) code. The new coding scheme is shown to be asymptotically optimal as the block length approaches infinity, regardless of the source statistics. Although the LD scheme is minimax-universal, it is not optimal for low source entropies and finite block lengths. Run length coding is shown to be closer to optimal for low source entropies, and the new scheme is shown to be practically equivalent to run length coding in this range.