Compression for fixed-width memories
Ori Rottenstreich, A. L. Berman, Yuval Cassuto, Isaac Keslassy · 2013
To enable direct access to a memory word based on its index, memories make use of fixed-width arrays, in which a fixed number of bits is allocated for the representation of each data entry. In this paper we consider the problem of encoding data entries of two fields, drawn independently according to known and generally different distributions. Our goal is to find two prefix codes for the two fields, that jointly maximize the probability that the total length of an encoded data entry is within a fixed given width. We study this probability and develop upper and lower bounds. We also show how to find an optimal code for the second field given a fixed code for the first field.