http://iet.metastore.ingenta.com
1887

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

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

For access to this article, please select a purchase option:

Buy article PDF
£12.50
(plus tax if applicable)
Buy Knowledge Pack
10 articles for £75.00
(plus taxes if applicable)

IET members benefit from discounts to all IET publications and free access to E&T Magazine. If you are an IET member, log in to your account and the discounts will automatically be applied.

Learn more about IET membership 

Recommend Title Publication to library

You must fill out fields marked with: *

Librarian details
Name:*
Email:*
Your details
Name:*
Email:*
Department:*
Why are you recommending this title?
Select reason:
 
 
 
 
 
IET Circuits, Devices & Systems — Recommend this title to your library

Thank you

Your recommendation has been sent to your librarian.

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)
      • 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.
    2. 2)
      • 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.
    3. 3)
      • 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.
    4. 4)
      • 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.
    5. 5)
      • 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.
    6. 6)
      • 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.
    7. 7)
      • 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.
    8. 8)
      • 8. Volder, J.E.: ‘The CORDIC trigonometric computing technique’, IRE Trans. Electron. Comput., 1959, 8, (3), pp. 330334.
    9. 9)
      • 9. Walther, J.S.: ‘A unified algorithm for elementary functions’. Proc. of Joint Spring Computer Conf., 1971, pp. 379385.
    10. 10)
      • 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.
    11. 11)
      • 11. Hu, Y.H., Naganathan, S.: ‘Angle recoding method for efficient implementation of the CORDIC algorithm’, IEEE Trans. Comput., 1993, 42, pp. 99102.
    12. 12)
      • 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.
    13. 13)
      • 13. Rodrigues, T., Swartzlander, E.E.: ‘Adaptive CORDIC: using parallel angle recoding to accelerate rotations’, IEEE Trans. Comput., 2010, 59, (4), pp. 522531.
    14. 14)
      • 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.
    15. 15)
      • 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.
    16. 16)
      • 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.
    17. 17)
      • 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.
    18. 18)
      • 18. Kuhlmann, M., Parhi, K.K.: ‘P-CORDIC: a precomputation based rotation CORDIC algorithm’, EURASIP J. Adv. Signal Process., 2002, 2002, (9), pp. 936943.
    19. 19)
      • 19. Lakshmi, B., Dhar, A.S.: ‘VLSI architecture for parallel radix-4 CORDIC’, Microprocess. Microsyst., 2013, 37, (1), pp. 7986.
    20. 20)
      • 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.
    21. 21)
      • 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.
    22. 22)
      • 22. Meher, P.K., Park, S.Y.: ‘CORDIC designs for fixed angle of rotation’, IEEE Trans. VLSI Syst., 2013, 21, (2), pp. 217228.
    23. 23)
      • 23. Shukla, R., Ray, K.C.: ‘Low latency hybrid CORDIC algorithm’, IEEE Trans. Comput., 2014, 63, (12), pp. 30663078.
    24. 24)
      • 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.
    25. 25)
      • 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.
    26. 26)
      • 26. Timmermann, D., Hahn, H., Hosticka, B.J.: ‘Hough transform using CORDIC method’, Electron. Lett., 1989, 25, (3), pp. 205206.
    27. 27)
      • 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.
    28. 28)
      • 28. Hough, P.V.C.: ‘Method and means for recognizing complex patterns’, US Patent 3,069,654, Dec 1962.
    29. 29)
      • 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.
    30. 30)
      • 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.
    31. 31)
      • 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.
    32. 32)
      • 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.
    33. 33)
      • 33. Maharatna, K., Banerjee, S.: ‘A VLSI array architecture for Hough transform’, Pattern Recognit., 2001, 34, (7), pp. 15031512.
    34. 34)
      • 34. Zhou, F., Kornerup, P.: ‘A high speed Hough transform using CORDIC’. Int. Conf. on Digital Signal Processing, June 1995, pp. 482487.
    35. 35)
      • 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.
    36. 36)
      • 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.
    37. 37)
      • 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.
    38. 38)
      • 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.
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