Analytical method for optimum non-negative integer bit allocation

摘要

The optimum bit allocation (OBA) problem was first investigated by Huang and Schultheiss in 1963. They solved the problem allowing the bits to be signed real numbers. Later, different algorithms were proposed for OBA problem when the bits were constrained to be integer and non-negative. In 2006, Farber and Zeger proposed new algorithms for solving optimum integer bit allocation (OIBA) and optimum non-negative integer bit allocation (ONIBA). None of the existing algorithms for OIBA and ONIBA problems end with an analytical solution. In this study, a new analytical solution is proposed for OIBA and ONIBA problems based on a novel analytical optimisation approach. At first, a closed form solution is derived for Lagrange unconstraint problem. Then, by removing the Lagrange multiplier, an analytical solution is obtained for OIBA and ONIBA problems. Using the selection and bisection algorithms, a low complexity algorithm is proposed for searching in a group of discrete functions which can reduce the computational complexity of the analytical solution. The complexity of computing the analytical solution is O(k) which is much lower than the complexity of existing ONIBA algorithms.