Implementation of SAD Algorithm with Folded Tree Architecture using VHDL

International Journal of Electronics and Communication Engineering
© 2015 by SSRG - IJECE Journal
Volume 2 Issue 7
Year of Publication : 2015
Authors : Resma S and Ragimol
How to Cite?

Resma S and Ragimol, "Implementation of SAD Algorithm with Folded Tree Architecture using VHDL," SSRG International Journal of Electronics and Communication Engineering, vol. 2,  no. 7, pp. 16-21, 2015. Crossref,


The trend of smaller, portable and more capable electronic devices give rise to a number of design and implementation problem, mainly due to the energy consumption. The highest energy consumption in radio communication, so in order to reduce the energy and power, Folded tree architecture is beneficial. The existing architecture known as Binary tree architecture, is a tree data structure in which each node has at most two children, but this architecture requires large number of processing elements. Thus the Folded tree architecture is used, which has two phases, trunk and twig, this help in reducing the number of processing elements. Wireless Sensor Network (WSN) has wide range of application in medical monitoring, environmental sensing, industrial inspection and military surveillance. The data-driven nature of Wireless Sensor Nodes applications requires a specific data processing approach. Motion estimation is the most critical component of video coding system. Sum of Absolute Difference (SAD) algorithm is the most common matching criteria choosen for motion estimation because of its low complexity and good performance and it is a tree structure. Due to the structural similarity of Sum of Absolute Difference (SAD) algorithm, motion estimation can implement using binary tree and folded tree architectures. The area, power and delay are reduced in the proposed architecture. This paper describes the design and implementation of the newly proposed folded-tree architecture with Sum of Absolute Difference (SAD) algorithm for motion estimation.


Wireless Sensor Network (WSN), parallel prefix operation, binary tree, folded tree, Sum of Absolute Difference (SAD) algorithm, motion estimation.


[1] V. Raghunathan, C. Schurgers, S. Park, and M. B. Srivastava, “Energyawarewireless microsensor networks,” IEEE Signal Process. Mag., vol. 19, no. 2, pp. 40–50, Mar. 2002.
[2] G. Blelloch, “Scans as primitive parallel operations,” IEEE Trans.Comput., vol. 38, no. 11, pp. 1526–1538, Nov. 1989.
[3]  Cedric Walravens, Wim Dehaene, “Low-Power Digital Signal Processor Architecture for Wireless Sensor Nodes” , IEEE transactions on very large scale integration (vlsi) systems, vol. 22, no. 2, february 2014.
[4] S.C.Hsia, P.Y.Hong, “ Very large scale integretion(VLSI)  implementation of low-complexity variable block size motion estimation for H.264/AVC coding” , IET Circuits Devices  Syst., 2010, Vol. 4.Iss. 5, pp. 414-424.
[5] J. Hennessy and D. Patterson, Computer Architecture A Quantitative Approach, 4th ed. San Mateo, CA: Morgan Kaufmann, 2007.
[6] P. Sanders and J. Träff, “Parallel prefix (scan) algorithms for MPI,” in Proc. Recent Adv. Parallel Virtual Mach. Message Pass. Interf., 2006, pp. 49–57.
[7] N. Weste and D. Harris, CMOS VLSI Design: A Circuits and Systems Perspective. Reading, MA, USA, Addison Wesley, 2010.
[8] M. Hempstead, J. M. Lyons, D. Brooks, and G.-Y. Wei, “Survey of hardware systems for wireless sensor networks,” J. Low Power Electron., vol. 4, no. 1, pp. 11–29, 2008.
[9]  C. Walravens and W. Dehaene, “Design of a low-energy data processing architecture for wsn nodes,” in Proc. Design, Automat. Test Eur. Conf. Exhibit., Mar. 2012, pp. 570–573.
[10] H. Karl and A. Willig, Protocols and Architectures for Wireless SensorNetworks, 1st ed. New York: Wiley, 2005
[11]  S. Mysore, B. Agrawal, F. T. Chong, and T. Sherwood, “Exploring the processor and ISA design for wireless sensor network applications,” in Proc. 21th Int. Conf. Very-Large-Scale Integr. (VLSI) Design, 2008, pp. 59–64
[12] Yu-Wen Huang, Shao-Yi Chien, Bing-Yu Hsieh, and Liang-Gee Chen, “Global Elimination Algorithm and Architecture Design for Fast Block Matching Motion Estimation” , IEEE transactions on circuits and systems for video technology, vol. 14, no. 6, june 2004
[13]  J. Vanne, et al., .A high-performance sum of absolute difference implementation for motion estimation,. IEEE Transactions on Circuits and Systems for Video Technology, vol. 16, no. 7, pp. 876.883, July 2006.
[14] Y.S. Jehng, L.G. Chen and T.D. Chiueh, "An efficient and simple VLSI tree architecture for motion estimation algorithms," IEEE Trans. on Signal Processin.g, vol. 41,     no.2,pp.889-900,Feb.1993.
[15] Y. H. Yeh and C. Y. Lee, “Cost-effective VLSI architectures and buffer size optimization for full-search block matching algorithms,” IEEE Trans. VLSI Syst., vol. 7, pp. 345–358, Sept. 1999.