Fast Discrete Krawtchouk Transform Algorithms for Short-Length Input Sequences

This paper presents new fast discrete Krawtchouk transform (DKT) algorithms for input sequences of length 3 to 8. Small-sized DKT algorithms can be utilized in image processing applications to extract local image features formed by a sliding spatial window, and they can also serve as building blocks for developing larger-sized algorithms. Existing strategies to reduce the computational complexity of DKT mainly focus on modifying the recurrence relations for Krawtchouk polynomials, dividing the input signals into blocks or layers, or using different methods to approximate the coefficient values. Algorithms developed using the first two strategies are computationally intensive, which introduces a significant time delay in the computation process. Algorithms based on the approximation of polynomial coefficient values reduce computation time but at the expense of reduced accuracy. We use a different approach based on reducing the block structure of the matrix to one of the previously developed block-structural patterns, which allows us to factorize the resulting matrix in such a way that it leads to a reduction in the computational complexity of the synthesized algorithm. We describe the algorithmic solutions we have obtained through data flow graphs. The proposed DKT algorithms reduce the number of multiplications, additions, and shifts by an average of 58%, 27%, and 68%, respectively, compared to the direct computation of DKT via matrix-vector product. These characteristics were averaged across the considered input sizes (from 3 to 8).