On the arithmetic required in the computation of orthonormal transforms

摘要

This paper considers one of the problems encountered in the definition of video coding algorithms for moving and still pictures due to the finite length arithmetic in the computation of orthonormal transforms. In particular two aspects are taken into account: mismatch and reversibility. The different causes which influence the final representation of the reconstructed video samples are examined and a formula is given, expressing said final error as a function of the errors introduced at the different stages of the computation. From an upper bound of said final error the minimum number of bits required for the representation of the quantities appearing at the different stages of the computation are derived for two cases of particular interest. Alternatively, assigning the length of the arithmetic registers, it is possible to know the worst case error. With some care the results are valid for any type of fast algorithms and not only for the matrix multiplication case which is used here to attain the widest validity of the results.