Your browser does not support JavaScript!
http://iet.metastore.ingenta.com
1887

access icon free Precomputation-based radix-4 CORDIC for approximate rotations and Hough transform

Vector rotation is an important component of algorithms in digital signal processing and robotics. Often, the rotation does not require very high accuracy. This study presents a lowoverhead sign-precomputation-based architecture for approximate rotation using the coordinate rotation digital computer (CORDIC) algorithm. The proposed architecture is independent of Z-datapath, and involves precomputation of the direction of rotation for each micro-rotation angle. The approach involves selecting the optimal micro-rotation angles from a set of elementary angles in run time. Careful selection and elimination of the redundant micro-rotation angles leads to a maximum of three iterations for a majority of the input angles while also simultaneously reaching within 0:45 (of the desired rotation angle). An field programmable gate array (FPGA) implementation of the proposed rotation mode CORDIC on XC7K70T-3FBG676 Kintex-7 using Xilinx ISE 13.2 achieves roughly 50% reduction in slice-delay product and power-delay product compared to recent designs. An application of approximate rotation to Hough transform-based lane detection is presented. An efficient algorithm for generation of vote addresses in the parameter space is proposed. It is shown that accurate lane detection is possible along with resource savings using the proposed CORDIC. The proposed architecture reduces the number of additions roughly by a factor of 20 compared with the conventional method of computing a parameter for each feature point.

References

    1. 1)
      • 9. Walther, J.S.: ‘A unified algorithm for elementary functions’. Proc. of Joint Spring Computer Conf., 1971, pp. 379385.
    2. 2)
      • 24. Nawandar, N.K., Garg, B., Sharma, G.K.: ‘Rico: a low power repetitive iteration CORDIC for DSP applications in portable devices’, J. Syst. Archit., 2016, 70, pp. 8292.
    3. 3)
      • 27. Maharatna, K., Banerjee, S., Grass, E., et al: ‘Modified virtually scaling-free adaptive CORDIC rotator algorithm and architecture’, IEEE Trans. Circuits Syst. Video Technol., 2005, 15, (11), pp. 14631474.
    4. 4)
      • 31. Voisin, V., Avila, M., Emile, B., et al: ‘Road markings detection and tracking using Hough transform and kalman filter’. Proc. of the 7th Int. Conf. on Advanced Concepts for Intelligent Vision Systems, ACIVS'05, 2005, pp. 7683.
    5. 5)
      • 35. Suchitra, S., Satzoda, R.K., Srikanthan, T.: ‘Accelerating CORDIC for Hough transform’. Proc. of 12th Int. Symp. on Integrated Circuits, December 2009, pp. 167170.
    6. 6)
      • 15. Srikanthan, T., Gisuthan, B.: ‘A novel technique for eliminating iterative based computation of polarity of micro-rotations in CORDIC based sine-cosine generators’, Microprocess. Microsyst., 2002, 26, (5), pp. 243252.
    7. 7)
      • 2. Parfieniuk, M., Vashkevich, M., Petrovsky, A.: ‘Short-critical-path and structurally orthogonal scaled CORDIC-based approximations of the eight-point discrete cosine transform’, IET Circuits Devices Syst., 2013, 7, (3), pp. 150158.
    8. 8)
      • 32. Cualain, D.O., Hughes, C., Glavin, M., et al: ‘Automotive standards-grade lane departure warning system’, IET Intell. Transp. Syst., 2012, 6, (1), pp. 4457.
    9. 9)
      • 21. Vachhani, L., Sridharan, K., Meher, P.K.: ‘Efficient CORDIC algorithms and architectures for low area and high throughput implementation’, IEEE Trans. Circuit Syst.-II: Express Briefs, 2009, 56, (1), pp. 6165.
    10. 10)
      • 33. Maharatna, K., Banerjee, S.: ‘A VLSI array architecture for Hough transform’, Pattern Recognit., 2001, 34, (7), pp. 15031512.
    11. 11)
      • 16. Ravichandran, S., Asari, V.: ‘Pre-computation of rotation bits in unidirectional CORDIC for trigonometric and hyperbolic computations’. Proc. of IEEE Computer Society Annual Symp. on VLSI., February 2003, pp. 215216.
    12. 12)
      • 22. Meher, P.K., Park, S.Y.: ‘CORDIC designs for fixed angle of rotation’, IEEE Trans. VLSI Syst., 2013, 21, (2), pp. 217228.
    13. 13)
      • 25. Garrido, M., Kallstrom, P., Kumm, M., et al: ‘CORDIC II: a new improved CORDIC algorithm’, IEEE Trans. Circuits Syst. II, Express Briefs, 2016, 63, (2), pp. 186190.
    14. 14)
      • 29. Duda, R.O., Hart, P.E.: ‘Use of the Hough transformation to detect lines and curves in pictures’, Commun. ACM, 1972, 15, (1), pp. 1115.
    15. 15)
      • 14. Antelo, E., Villalba, J., Bruguera, J.D., et al: ‘High performance rotation architectures based on the radix-4 CORDIC algorithm’, IEEE Trans. Comput., 1997, 46, (8), pp. 855870.
    16. 16)
      • 8. Volder, J.E.: ‘The CORDIC trigonometric computing technique’, IRE Trans. Electron. Comput., 1959, 8, (3), pp. 330334.
    17. 17)
      • 12. Juang, T.B.: ‘Low latency angle recoding methods for the higher bit-width parallel CORDIC rotator implementations’, IEEE Trans. Circuits Syst. II, Express Briefs, 2008, 55, (11), pp. 11391143.
    18. 18)
      • 3. Han, B., Yang, Z., Zheng, Y.R.: ‘Efficient implementation of iterative multi-input multi-output orthogonal frequency-division multiplexing receiver using minimum-mean-square error interference cancellation’, IET Commun., 2014, 8, (7), pp. 990999.
    19. 19)
      • 1. Jridi, M., Meher, P.: ‘A scalable approximate DCT architecture for efficient HEVC compliant video coding’, IEEE Trans. Circuits Syst. Video Technol., 2016, 27, (8), pp. 18151825.
    20. 20)
      • 10. Andraka, R..: ‘A survey of CORDIC algorithms for FPGA based computers’. Proc. of ACM/SIGDA sixth international symp. on Field Programmable Gate Arrays, 1998, pp. 191200.
    21. 21)
      • 5. Cualain, D.O., Glavin, M., Jones, E.: ‘Multiple-camera lane departure warning system for the automotive environment’, IET Intell. Transp. Syst., 2012, 6, (3), pp. 223234.
    22. 22)
      • 28. Hough, P.V.C.: ‘Method and means for recognizing complex patterns’, US Patent 3,069,654, Dec 1962.
    23. 23)
      • 26. Timmermann, D., Hahn, H., Hosticka, B.J.: ‘Hough transform using CORDIC method’, Electron. Lett., 1989, 25, (3), pp. 205206.
    24. 24)
      • 18. Kuhlmann, M., Parhi, K.K.: ‘P-CORDIC: a precomputation based rotation CORDIC algorithm’, EURASIP J. Adv. Signal Process., 2002, 2002, (9), pp. 936943.
    25. 25)
      • 19. Lakshmi, B., Dhar, A.S.: ‘VLSI architecture for parallel radix-4 CORDIC’, Microprocess. Microsyst., 2013, 37, (1), pp. 7986.
    26. 26)
      • 7. Thomaidis, G., Kotsiourou, C., Grubb, G., et al: ‘Multi-sensor tracking and lane estimation in highly automated vehicles’, IET Intell. Transp. Syst., 2013, 7, (1), pp. 160169.
    27. 27)
      • 6. Li, C., Dai, B., Wang, R., et al: ‘Multi-lane detection based on omnidirectional camera using anisotropic steerable filters’, IET Intell. Transp. Syst., 2016, 10, (5), pp. 298307.
    28. 28)
      • 36. Bruguera, J.D., Guil, N., Lang, T., et al: ‘CORDIC based parallel/pipelined architecture for the Hough transform’, J. VLSI Signal Process. Syst. Signal, Image Video Technol., 1996, 12, (3), pp. 207221.
    29. 29)
      • 17. Hsiao, S.F., Hu, Y.H., Juang, T.B.: ‘A memory-efficient and high-speed sine/cosine generator based on parallel CORDIC rotations’, IEEE Signal Process. Lett., 2004, 11, (2), pp. 152155.
    30. 30)
      • 11. Hu, Y.H., Naganathan, S.: ‘Angle recoding method for efficient implementation of the CORDIC algorithm’, IEEE Trans. Comput., 1993, 42, pp. 99102.
    31. 31)
      • 34. Zhou, F., Kornerup, P.: ‘A high speed Hough transform using CORDIC’. Int. Conf. on Digital Signal Processing, June 1995, pp. 482487.
    32. 32)
      • 37. Jolly, E.K., Fleury, M.: ‘Multi-sector algorithm for hardware acceleration of the general Hough transform’, Image Vis. Comput., 2006, 24, (9), pp. 970976.
    33. 33)
      • 38. Chen, Z.H., Su, A.W.Y., Sun, M.T.: ‘Resource-efficient FPGA architecture and implementation of Hough transform’, IEEE Trans. Very Large Scale Integr. (VLSI) Syst., 2012, 20, (8), pp. 14191428.
    34. 34)
      • 20. Khurshid, B., Mir, R.N., Kumar, A., et al: ‘A hybrid-radix approach for efficient implementation of unfolded CORDIC architectures for FPGA platforms’. In IEEE Int. Conf. on Signal Processing and Integrated Networks (SPIN), 2014, pp. 453457.
    35. 35)
      • 30. Li, Q., Zheng, N., Cheng, H.: ‘Springrobot: a prototype autonomous vehicle and its algorithms for lane detection’, IEEE Trans. Intell. Transp. Syst., 2004, 5, (4), pp. 300308.
    36. 36)
      • 13. Rodrigues, T., Swartzlander, E.E.: ‘Adaptive CORDIC: using parallel angle recoding to accelerate rotations’, IEEE Trans. Comput., 2010, 59, (4), pp. 522531.
    37. 37)
      • 4. Hwang, Y.T., Chen, W.D.: ‘Design and implementation of a high-throughput fully parallel complex-valued QR factorisation chips’, IET Circuits Devices Syst., 2011, 5, (5), pp. 424432.
    38. 38)
      • 23. Shukla, R., Ray, K.C.: ‘Low latency hybrid CORDIC algorithm’, IEEE Trans. Comput., 2014, 63, (12), pp. 30663078.
http://iet.metastore.ingenta.com/content/journals/10.1049/iet-cds.2017.0492
Loading

Related content

content/journals/10.1049/iet-cds.2017.0492
pub_keyword,iet_inspecKeyword,pub_concept
6
6
Loading
This is a required field
Please enter a valid email address