Open AccessAnalytical method for optimum non‐negative integer bit allocation
Author(s) -
Hatam Mahdi,
MasnadiShirazi Mohammad Ali
Publication year - 2016
Publication title -
iet signal processing
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.384
H-Index - 42
eISSN - 1751-9683
pISSN - 1751-9675
DOI - 10.1049/iet-spr.2014.0336
Subject(s) - lagrange multiplier , integer (computer science) , computational complexity theory , mathematical optimization , bisection method , algorithm , integer programming , mathematics , computer science , programming language
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.