Abstract: Walsh-Haar function system is a new kind of function systems that has good global/local property. Discrete Walsh-Haar transformation is an orthogonal transformation that can be widely used in signal processing. In this paper, a new type of transformation,discrete Walsh-Haar transformation, is proposed, and the fast algorithm of discrete Walsh-Haar transformation is studied based on the dichotomous technique. The idea and method used to design the fast algorithm in this paper can be used to study the fast algorithms of other order discrete Walsh-Haar transformations and other discrete orthogonal transformations.