A parallel complex divider architecture based on DCD iterations for computing complex division in MVDR beamformer

doi:10.21629/JSEE.2018.06.02

Journal of Systems Engineering and Electronics ›› 2018, Vol. 29 ›› Issue (6): 1124-1135.doi: 10.21629/JSEE.2018.06.02

• Electronics Technology • Previous Articles Next Articles

A parallel complex divider architecture based on DCD iterations for computing complex division in MVDR beamformer

Jayaraj U KIDAV^1,^2,*(), Mangai N M SIVA¹(), Pillai PERUMAL M²()

¹ Karunya Institute of Technology and Sciences, Coimbatore 641114, India
² National Institute of Electronics and Information Technology, Calicut 673601, India

Received:2017-06-17 Online:2018-12-25 Published:2018-12-26
Contact: Jayaraj U KIDAV E-mail:jayaraj@calicut.nielit.in;sivamangai@karunya.edu;mppillai@calicut.nielit.in
About author:KIDAV Jayaraj U received his B.E. degree in electronics and communication engineering from Madurai Kamaraj University, India in 2000, and his M.E. degree in very-large-scale integrotion (VLSI) design from PSG College of Technology, Bharathiar University, India in 2002. Currently, he is pursuing his Ph.D. degree from Karunya Institute of Technology and Sciences, Coimbatore, India. His research focuses on high performance VLSI signal processing architecture development for adaptive beamformer in high sampling rate applications like medical ultrasound imaging, radar, etc. He joined as a scientist in Defense Research and Development Organization (DRDO), Ministry of Defense, Government of India in 2002, where he worked in signal processing systems development for defense applications. From 2008 to 2010, he worked as an R & D engineer in Systems and Technology Group at IBM India Pvt. Ltd and currently he is working as a scientist at National Institute of Electronics and Information Technology (NIELIT) Calicut, Government of India. E-mail: jayaraj@calicut.nielit.in|SIVA Mangai N M received her B.E. degree in electronics and communication engineering with distinction from the Madurai Kamaraj University, India in 2000, and her M.E. degree in VLSI design from PSG College of Technology, Bharathiar University, India in 2002. She completed her Ph.D. degree in information and communication engineering under Anna University, Chennai, India in 2011, focusing on power optimization and failure detection techniques for memory. She is a member of VLSI Society of India (VSI), International Association of Engineers (IAENG), International Association of Computer Science and Information Technology (IACSIT), International Congress for Global Science and Technology (ICGST) Academic Community and the Society of Digital Information and Wireless Communications (SDIWC), Institute of Doctors, Engineers and Scientists (IDES). She is currently working as an associate professor in electronics and communication engineering, Karunya University, Coimbatore, India. E-mail: sivamangai@karunya.edu|PERUMAL M Pillai received his Ph.D. degree in electronics (laser and EO engineering) from Dr. Babasaheb Ambedkar Marathwada University, Aurangabad India in 2006. He worked as a project/research associate in IIT Madras from 1989 to 1993, availed Swiss co-operation fellowship for eight months in 1996 and worked at Swiss Federal Institute of Technology, Lausanne. From 1993 to 1998, he worked as a senior design engineer, from 1998 to 2006 as a principal design engineer and 2006 to 2010 as an additional director at CEDTI Aurangabd. From 2010 to 2013, he worked as a director in charge NIELIT Chennai. Currently he is working as an executive director of NIELIT Calicut. His research interests are in VLSI technologies, image processing techniques for medical imaging, fiber sensors & distributed sensing, smart sensors, photonic & fiber Bragg grating (FBG) devices. E-mail: mppillai@calicut.nielit.in
Supported by:
Microelectronics Division of the Ministry of Electronics and Information Technology, Government of India, under SMDP-C2SD Project(9(1)/2014-MDD);This work was supported by Microelectronics Division of the Ministry of Electronics and Information Technology, Government of India, under SMDP-C2SD Project (9(1)/2014-MDD)

Abstract

Abstract:

This paper presents a hardware architecture using mixed pipeline and parallel processing for complex division based on dichotomous coordinate descent (DCD) iterations. The objective of the proposed work is to achieve low-latency and resource optimized complex divider architecture in adaptive weight computation stage of minimum variance distortionless response (MVDR) algorithm. In this work, computation of complex division is modeled as a 2×2 linear equation solution problem and the DCD algorithm allows linear systems of equations to be solved with high degree of computational efficiency. The operations in the existing DCD algorithm are suitably parallel pipelined and the performance is optimized to 2 clock cycles per iteration. To improve the degree of parallelism, a parallel column vector read architecture is devised. The proposed work is implemented on the field programmable gate array (FPGA) platform and the results are compared with state-of-art literature. It concludes that the proposed architecture is suitable for complex division in adaptive weight computation stage of MVDR beamformer. We demonstrate the performance of the proposed architecture for MVDR beamformer employed in medical ultrasound imaging applications.

Key words: minimum variance distortionless response (MVDR) beamformer, adaptive weight, dichotomous coordinate descent (DCD) algorithm, medical ultrasound imaging

Jayaraj U KIDAV, Mangai N M SIVA, Pillai PERUMAL M. A parallel complex divider architecture based on DCD iterations for computing complex division in MVDR beamformer[J]. Journal of Systems Engineering and Electronics, 2018, 29(6): 1124-1135.

Figures/Tables 17

Table 1

Fig 1

Table 2

Table 3

Fig 2

Fig 3

Fig 4

Fig 5

Fig 6

Fig 7

Fig 8

Fig 9

Fig 10

Fig 11

Table 4

Table 5

Fig 12

References 12

1	SYNNEVẢG J, AUSTENG A, HOLM S. Benefits of minimum-variance beamforming in medical ultrasound imaging. IEEE Trans. on Ultrasonics, Ferroelectrics, and Frequency Control, 2009, 56(9): 1868-1879.
2	PARK J, WI S M, LEE J S. Computationally efficient adaptive beamformer for ultrasound imaging based on QR decomposition. IEEE Trans. on Ultrasonics, Ferroelectrics, and Frequency Control, 2016, 63(2): 256-265.
3	HOLFORTI K, GRAN F, JENSEN J A. Minimum variance beamforming for high frame-rate ultrasound imaging. Proc. of IEEE Ultrasonics Symposium, 2007: 1541-1544.
4	HOLFORTI K, GRAN F, JENSEN J A. Broadband minimum variance beamforming for ultrasound imaging. IEEE Trans. on Ultrasonic, Ferroelectrics, and Frequency Control, 2009, 56(2): 314-325.
5	WANG D, REN P J, LIU L B. A high-throughput fixed point complex divider for FPGAs. IEICE Electronic Express, 2013, 10 (4): 1- 8.
6	EDMAN F, ÖWALL V. Fixed-point implementation of a robust complex valued divider architecture. Proc. of the European Conference on Circuit Theory and Design, 2005: 143-146.
7	LIU J, WEAVER B, ZAKHAROV Y. FPGA implementation of multiplication-free complex division. Electronics Letters, 2008, 44 (2): 95- 96.
8	WRIGHTS J. Coordinate descent algorithms. Mathematical Programming: Series A and B, 2015, 151 (1): 3- 34. doi: 10.1007/s10107-015-0892-3
9	LIU J, ZAKHAROV Y, WEAVER B. Architecture and FPGA design of dichotomous coordinate descent algorithms. IEEE Trans. on Circuits Systems Part I: Regular Papers, 2009, 56(11): 2425-2438.
10	HEMA N, KIDAV J, LAKSHMI B. VLSI architecture for broadband MVDR beamformer. Indian Journal of Science and Technology, 2015, 8 (19): 1- 10.
11	MA L, DICKSON K, MCALLISTER J. QR decomposition based matrix inversion for high performance embedded MIMO receivers. IEEE Trans. on Signal Processing, 2011, 59(4): 1858-1867.
12	UNNIKRISHNAN M, KIDAV J U. Broadband beamformer combined with DCDweighting. International Journal of Engineering Research in Electronic and Communication Engineering, 2015, 2 (10): 7- 11.

Algorithm	Iteration time	Latency (Cycles)	Area
Newton Raphson	2 serial multiplications	$\left(2\left[\log_2\dfrac{n}{i}\right]+1\right)t_{mul}+1 $	1 mul + table + control
Series expansion	2 parallel multiplications	$\left(\left[\log_2\dfrac{n}{i}\right]+2\right)t_{mul}+1 $	1 mul + table + control
Accurate quotient approx.	1 multiplication	$\left(\left[\dfrac{n}{i}\right]+1\right)t_{mul} $	3 muls + table + control
Short reciprocal	2 serial multiplications	$\left(2\left[\dfrac{n}{i}\right]\right)t_{mul}+1 $	1 short mul + table + control
Round/ pre scale	1 multiplication	$\left(\left[\dfrac{n}{i}\right]+2\right)t_{mul}+1 $	1 mul + table + control
DCD algorithm	Bit-shift operations, component transpositions and negations	$(3Mb+n+2) $	No mul and add

State	Operation	Cycle
0	$\begin{array}{c}{\rm Initialization{:}}\; {{{\mathit{\boldsymbol{h}}}}} = 0, {{{\mathit{\boldsymbol{r}}}}} = \mathit{\boldsymbol{\beta}}, m = M{{{\mathit{\boldsymbol{b}}}}}, \\k = 0, \Delta m = 0, s = 1, n = 1\end{array}$
1	$\begin{array}{c}{\rm If}\ m = 0, \mbox{algorithm; stops; else}, \\m = m-1, \alpha = 2\, \widehat{\ }\, m, \Delta m = \Delta m+1\end{array}$	1
2	$\begin{array}{c}{\rm If}\ s = 1, \mbox{then}\ rtmp = R(rn); \\ {\rm else}, {\rm real}(r(n)) = {\rm img}(rn)c = Rn, \\n/2-\|{\rm img}(r(n))\|\times2\Delta m\end{array}$	1
3	$\begin{array}{c}{\rm If}\ c < 0, \mbox{then; go; to; state}\ 4, \ \mbox{else}, \\ \mbox{go; to; state}\ 5\end{array}$	1
4	$\begin{array}{c}hn = hn+{\rm sign}(rtmp)s\alpha\\ r = r\times2\Delta m-{\rm sign}(rtmp)s{{{\mathit{\boldsymbol{R}}}}}(:, n)\\ \Delta m = 0, k = k+1, {\rm flag} = 1\\ {\rm If}\ K = Nu, \mbox{algorithm; stops} \end{array}$	N
5	$\begin{array}{c}{\rm If} s = 1, \mbox{then}\ s = j, \mbox{go; to; state}\ 2\\ {\rm else}, s = 1, n = (n)mod(N/2)+1\\ {\rm If}\ n = 1\ {\rm \mbox{and}\ flag = 1, \mbox{then}\ flag = 0}, \\ \mbox{go; to; state}\ 2, {\rm \mbox{else}\; if}\ n = 1\ {\rm and\; flag} = 0, \\ \mbox{then go; to; state}\ 1\; \mbox{else, go; to; state}\ 2\end{array}$	1
Total	${\leqslant}7NNu/2+3N(Mb-1)+Mbcycles$

State	Operation	Cycle
0	Initializations: $h = 0, k = 0, $ Nu =Number of iterations. $ {{{\mathit{\boldsymbol{r}}}}} = \mathit{\boldsymbol{\beta}}; {\rm flag} = 0;delm = 0;s = 1;$<break/> $n = 1;m = Mb; N = {\rm length}({{{\mathit{\boldsymbol{r}}}}});$
1	if$(k = =Nu)$ Go; to State 0 else if $s = =1$ $Rtmp = {\rm real}(r(n))$; else $Rtmp = {\rm imag}(r(n))$; $c = R(n, n)/2-\|Rtmp\|*2\, \widehat{\ }\, delm$ if$(s = =1)$ $n = mod(n, N)+1$; increment read_counter$(n)$ if$(c < 0)$ generate read $h(n)$ signal generate read ${{{\mathit{\boldsymbol{R}}}}}(:, n)$ signal generate write $h(n)$ signal generate write ${{{\mathit{\boldsymbol{r}}}}}$ signal Go; to State 2	1
2	if $c < 0$ $h(n) = h(n)+{\rm sign}(Rtmp)s\alpha; $ ${{{\mathit{\boldsymbol{r}}}}} = {{{\mathit{\boldsymbol{r}}}}}2\, \widehat{\ }\, delm-({\rm sign}(Rtmp)s*{{{\mathit{\boldsymbol{R}}}}}(:, n)); $ $delm = 0;$ $k = k+1;$ $\rm flag = 1$; end if $s = =1$ $s = j$; Go to State 1 else $s = 1;$ $n = mod(n, N)+1$; increment write_counter$(n)$ if $\left({{\rm{n = = 1\ & \ & ; flag = = 1}}} \right)$ $\rm flag = 0$; go to state 1: else if $\left({{\rm{n = = 1\ & \ & ; flag = = 0}}} \right)$ If $m = 0$ Go to State 0 else $m = m-1;$ $\alpha = 2\, \widehat{\ }\, m; $ $delm = delm+1;$ else Go to State 1

FPGA resource	Total available	Used by logic
Slice registers	407 600	8 083
Slice LUTs	203 800	26 485
Block RAMs	445	96

Scheme	Latency/ ns	Average throughput/ MOPS	Device	Area /LUT	Algorithm	Accuracy	Number of complex divisions	Precision/ bit
The proposed work	201	160(32 div. units) 5(Single div. unit)	Xilinx Kintex-7 FPGA	26 485(32 div. units + control) 621(Single div. unit)	DCD(Modified complex cyclic valued)	Very good	32	16
Wang et al. [5]	167	113	Altera Straitix- FPGA	4 863	CORDIC	Very good	1	16
Adman et al. [6]	80	16.67	Xilinx Virtex-II FPGA	117 (slices)	Smith	Poor	1	16
Liu et al. [7]	620	1.6	Xilinx XC2VP30 FPGA	527 (slices)	DCD	Very good	1	16

A parallel complex divider architecture based on DCD iterations for computing complex division in MVDR beamformer

RichHTML

PDF (PC)

Knowledge

Abstract

Cite this article

Share this article

Figures/Tables 17

References 12

Related Articles 2

Recommended Articles

Metrics

Comments

[1]	Bo WANG, Junwei XIE, Jing ZHANG, Haowei ZHANG. Beamforming analysis based on CSB sin-FDA [J]. Journal of Systems Engineering and Electronics, 2020, 31(1): 73-84.
[2]	Miaohui Zhang, Ming Xin, and Jie Yang. Adaptive multi-feature tracking in particle swarm optimization based particle filter framework [J]. Journal of Systems Engineering and Electronics, 2012, 23(5): 775-783.