Optimal prefix codes for sources with two-sided geometric distributions

A complete characterization of optimal prefix codes for off-centered, two-s ided geometric distributions of the integers is presented. These distributi ons are often encountered in lossless image compression applications, as pr obabilistic models for image prediction residuals. The family of optimal co des described is an extension of the Golomb codes, which are optimal for on e-sided geometric distributions. The new family of codes allows for encodin g of prediction residuals at a complexity similar to that of Golomb codes, without recourse to the heuristic approximations frequently used when modif ying a code designed for nonnegative integers so as to apply to the encodin g of any integer. Optimal decision rules for choosing among a lower complex ity subset of the optimal codes, given the distribution parameters, are als o investigated, and the relative redundancy of the subset with respect to t he full family of optimal codes is bounded.