scieee AI-readable full text Open interactive document viewer

Integral equation mei applied to three-dimensional arbitrary surfaces

Rius Casals, Juan Manuel,Parrón Granados, Josep,Úbeda Farré, Eduard,Mosig, J R

Abstract

The authors present a new formulation of the integral equation of the measured equation of invariance (MEI) as a confined field integral equation discretised by the method of moments, in which the use of numerically derived testing functions results in an approximately sparse linear system with storage memory requirements and a CPU time for computing the matrix coefficients proportional to the number of unknowns.

Full text

In Table 1, we show the fault coverage as the number of unscanned flip-flips in circuit S5378 increases. As shown in Table 1, the fault coverage does not drop significantly until as many as 50 flip-flops are scanned. Table 2 Fault coverage with unscanned flip-flops Total Original Self Unscanned Unscanned FFs coverage loop FFs ratio Circuit Fault coverage I S27 13 S298 114 I 100 3 2 66.7 100 100 14 2 14.3 93.57 In Table 2, we show the fault coverage of each circuit with the given number of flip-flops unscanned. The third column gives the full scan fault coverage using our implementation of the original FAN algorithm. The fifh column gives the number of unscanned flip-flops. The seventh column gives the fault coverage. We stopped unscanning when the fault coverage dropped significantly. When the circuit contains enough self-loop free flip-flops, the proposed partial scan selection method allows more than 20% flipflops to be unscanned with little decrease in the fault coverage. For the 838 circuit, with only one unscanned flip-flop, the fault coverage dropped from 100 to 91.74%, but when we assumed the preset signal at the unscanned flip-flop, we were able to obtain 100% fault coverage. S382 s444 Conclusion: We have introduced an interesting partial scan test method with no data holding overhead. The experimental results show that the proposed method can achieve almost full scan fault coverage while having a significant number of flip-flops unscanned. The proposed test method will be most effectively used for circuits in which the area occupied by memory elements dominates. These kinds of circuits are prevalent in multimedia applications. We will study the partial scan selection algorithm more and will improve the ATPG algorithm by adopting various techniques of more advanced ATPGs [l, 21. 21 100 15 4 19.0 95.32 21 97.34 15 3 14.3 90.11 0 IEE 1997 Electronics Letters Online No: 19971414 Dong Ho Lee and Hyun Chul Noh (School of’ Electronics and Electrical Engineering, KyungPook National University, Tuegu, 701- 702, Korea) 26 August 1997 References POMERANZ, I., REDDY, L.N., and REDDY, s.M.: ‘COMPACTEST: A method to generate compact test sets for combinational circuits’. Proc. Int. Test Conf., 1991, pp. 194203 SCHULZ, M., TRISCHLER, E., and SARFERT, T.: ‘SOCRATES: A highly efficient automatic test pattern generation system’. Proc. Int. Test Conf., 1987, pp. 101&1026 CHENG, K.T., and AGRAWAL, v.D.: ‘A partial scan method for sequential circuits with feedback‘, IEEE Trans., 1990, C-39, pp. 546548 LEE, D.H., and REDDY, s.M.: ‘On determining scan flip-flops in partial scan designs’. Proc. Int. Conf. Computer-Aided Design, November 1990, pp. 322-325 PARIKH, P.s., and ABRAMOVICI, M.: ‘Testability-based partial scan analysis’, J. Electron. Test., 1995, 7, pp. 61-70 FUJIWARA, H., and SHIMONO, T.: ‘On the acceleration of test generation algorithms’. Proc. 13th Int. Symp. Fault Tolerant Computing, 1983, pp. 98-105 Integral equation ME1 apiplied to threedimensional arbitrary surfaces J.M. Rius, J. Parron, E. Ubeda and J.R. Mosig Indexing term: Method of momtmts, Boundary element method, Numerical methods, Electromagnetic wave scattering The authors present a new formulation of the integral equation of the measured equation of invariance as a confrned field integral equation discretised by the method of moment, in which the use of numerically derived testing functions results in an approximately sparse linear system with storage memory requirements and a CPU time for computing the matrix coefficients proportional to the number of unknowns. Introduction: Boundary element methods (BEMs) are widely used for the numerical analysis of electromagnetic radiation and scattering. However, their application is limited to electrically small or resonant size objects due to the fact that the computational requirements increase rapidly with 1.he electrical size. One recent approach for achieving more efficient BEMs is the integral equation formulation of the measured equation of invariance (IE-MEI) [l - 31. This Letter presents the formulation of the IE-ME1 for 3D arbitrary scattering surfaces as a special case of a combined field integral equation (CFIE), discretised Iby the method of moments (MOM), in which the choice of different testing functions for the electric and magnetic fields results iri an approximately sparse linear system to solve for the induced current, where most of the matrix elements can be neglected. These new testing functions are numerically derived by a procedure borrowed from the measured equation of invariance (MEI) method [4] originally developed to numerically find the truncation boundary coefficients of finite difference and finite element meshes [5]. A significant feature of numerically derived testing functions is that they are adaptive, i.e. specific to the particular shape of the scatterer boundary and to the location of the function in the boundary. Formulation: The electric field integral equation (EFIE) and the magnetic field integral equation (MIFIE) discretised by the MOM may each be expressed in matrix form, respectively, as If di are the (subdomain) basis functions, J’, = Zi c, 2, and Gm are the (subdomain) testing functions, the matrix elements in eqn. 1 are em = (Gm,Ei) zEi = (Gm,lA~~Ct) d,i = (Gm,.i;Z) where LEJ and LHJ are, respectively, the linear operators that obtain the electric and magnetic fields due to an electric current. We left-multiply the EFIE and the MFIE in eqn. 1 by two arbitrary matrices [A] and [B], respectively, and add the two equations to form a CFIE -[E9 = [ZE][C] - [W] = ([ZH] - [D]) [C] (I) +. +. hk = (Gm,fi x ErL) z,”; = (Gm,fi x LHJGZ) (2) -[AI[@] - [Bl[Hil = ([Al[ZEl + [Bl[ZHl - [BI[Dl) [Cl (3) Left-multiplication of the EFIE or the MFIE by a matrix is equivalent to changing the testing functions. For instance: m \m I suggests that the new testing functions are Zm a,,, $, for the EFIE and Zm b,,, G, for the MFIE. The rows of [A] and [B] matrices are the coefficients of the new testing functions expanded in the old ones w,. Sparse [A], [B] matrices represent subdomain testing functions: the zeros correspond to original testing functions (col- LUIUI index) that do not overlap with the new ones (row index). We defme the ‘combined impedance matrix’ as [Zq = [A][Zq + [B][Zq. Now, eqn. 3 becomes --t -[AlPt1 - PI[W = ELECTRONICS LETTERS 20th November 1997 Vol. 33 No. 24 2029 where matrix [Zc] is full, [D] is sparse (because 2 and 2, are subdomain functions) and [A] and [B] are arbitrarily chosen as sparse and such that [Zq[Cl = 0. Therefore, eqn. 5 can be approximated by the sparse system of equations where [Cj is the unknown vector. The above is the 3D formulation of the IE-MEI, equivalent to a CFIE-type equation with different testing of the EFIE and the MFIE, such that the electric and magnetic impedance matrices cancel each other. The 2D formulation of the IE-ME1 [I, 21, [q = [B]-' [A][EI + [w, is a special case of eqn. 6 with [D] = [I] (identity matrix), due to the use of pulse basis and delta testing. [AI[E"l + PI[ff7 = [BI[DI[Cl (6) CoefJicient computation (MEImethod): In eqn. 5, we need [Zq[q 0. Since [E] = [Zq[q and [PI = [Zq[q, where [E] and [PI are, respectively, the discretisation of electric and magnetic scattered fields, it follows that [Zq[q = [A][E] + [BI[Hsl = 0. To numerically find the coefficients of matrices [A] and [B], the ME1 method enforces [A][E;] + [B][H;] = 0, where [E;] = [Z7[opl,, [Hi] = [Zq[o] are the discretisation of the fields due to P arbitrary currents %p called metrons. [CY J is a matrix whose columns are the discretisation of the metrons 2 for p = 1, ..., P. The result is a set of linear systems, one for each row of the matrix equation [Al[ZE1[%l + [Bl[aHI[%l = [ZC1[.Pl = 0 (7) where the unknowns are the elements of [A] and [B] matrices. Obviously, eqn. 7 does not guarantee that [Zc} [q 0, especially If the systems (eqn. 7) are overdetermined and cannot be exactly satisfied. However, it has been observed that in the 2D case, some metron sets produce a negligible residual [Zq[q in the IE-ME1 eqn. 6 [1, 2, 6, 71 or in the equivalent truncation boundary condition [4, 81. Metrons: For 3D arbitrary scatterer surfaces, the easiest metrons to implement are delta metrons. Each delta metron is equal to a basis function, .', = zp, and thus [CYJ = [I]. With this set of metrons, eqn. 7 becomes [Zq = 0. Row n of eqn. 7 corresponds to the linear system CL,,^:, + bnmzii) = z,", = 0 i = 1, ..., N (8) m where the non-zeros of a,, and b,, are the unknowns. To avoid the trivial solution, one of the coefficients must be arbitrarily set, for instance a,, = 1. Since it is desirable that matrices [A] and [B] are sparse, the number of unknowns in eqn. 8 is much smaller than N. Conversely, there are N delta metrons, and thus N equations in the system eqn. 8. This makes the system overdetermined and, in general, it cannot be solved exactly, [Z,q # 0. The minimum ~~[Zn~~~* is obtained by the least squares procedure. It must be noted that delta metrons are equivalent to the G* metrons of Jbvtic and Lee [SI, taking into account the fact that the combined impedance matrix Zc plays the role of the null-field En",, in [8]. 2.5 al m 0. - 2 1.5 c ._ I . 7x 1 .o ' c r 0 0.5 . 0' I -200 -1 00 0 100 200 e 187411 Fig. 1 Induced current in a sphere of diameter 2h for incident plane wave IE-ME1 results compared with analytical solution analytical IE-ME1 ____ With delta metrons, the operation count to obtain [A] , [B] matrices is proportional to Nz: For each row of [A] and [B], a system of N simultaneous equations (eqn. 8) must be solved by least squares with an operation count of the order of aN x 1Mz + /3M, where M is the number of a,,, On, coefficients to compute. However, we have found that forcing z,", = 0 only for the P - 2M basis functions i closest to testing function n leads to the same values of coefficients a,,, barn. That is, forcing z,"I = 0 only for near field mutual impedances makes it also true for far field ones. Now, the number of simultaneous equations P does not increase with the number of unknowns N: we need aP x Mz + pM3 = AF operations for each row of [A], [B] and the total operation count is thus proportional to N. Results: The proposed IE-ME1 technique has been applied to several scattering 3D problems. It has been found that the accuracy obtained with our current formulation is problem-dependent, which confiis that the selection of the metron set is the critical step. As a typical-case example, Fig. 1 shows the current induced in a sphere of diameter 2 h by a plane wave incident along the z axis, with the electric field polarised along the 2 direction. The IFME1 results are compared with the analytical solution. The plot corresponds to a cut of J, in the yz plane, with the origin at the centre of the sphere. The surface has been discretised in 2048 triangles with sides ranging from 0.1 h to 0.15 h. The number of unknowns for Rao, Wilton & Glisson basis functions [9] is N = 3072. The sparsity of [A], [B] matrices is 1.2%. The total amount of memory used is 6MB. The accuracy of the IE-ME1 result is reasonably good, but pointwise accuracy could not be enough for some angles. For these cases, a substantial improvement could certainly be obtained by using a different set of metrons that produces a smaller residual [ZTCl. Acknowledgments: The author is indebted to K.K. Mei of City University of Hong Kong for the valuable discussions on the ME1 method. This work was partially supported by the Spanish 'Comisibn Interministerial de Ciencia y Tecnologia' (CICYT) under project TIC 95-0983. Part of the work was done at City University of Hong Kong, where J.M. Rius was a visiting fellow from January 4 to February 3, 1997. Graduate students J. Parrbn and E. Ubeda are supported by the Generalitat de Catalunya, Comissionat per a Universitats i Recerca, under grants 1997 FI 00679 and 1997 FI 00747, respectively. 0 IEE 1997 Electronics Letters Online Nol: 19971419 J.M. Rius, J. Parron and E. Ubeda (Department of TSC, Ed$ci 0-3, Universitat Polit&cnica de Catalunya, Jordi Girona 1-3, 08034 Barcelona, Spain) 5 August 1997 J.R. Mosig (LEMA, ELB, Ecole Polytechnique FkdPrale de Lausanne (EPFL), CH-IO15 Lausanne, Switzerland) References 1 RIUS, J.M.: 'Integral formulation of the measured equation of invariance', Electron. Lett., 1996, 32, (l), pp. 23-25 2 RIUS, J.M., POUS, R., and CARDAMA, A.: 'Integral formulation of the measured equation of invariance: a novel sparse-matrix boundary element method', ZEEE Trans. Magn., 1996, 32, (3), pp. 962-967 3 RIUS, J.M., CARPINTERO, c.P., CARDAMA, A., and MOSIG, J.R.: 'Frquency extrapolation in the integral equation MEI', Electron. Lett., 1996, 32, (25), pp. 2324-2326 4 MEI, KK., POUS, R., CHEN, z., LIU, Y.W, and PROUTY, M.D.: 'The measured equation of invariance: a new concept in field computations', IEEE Trans. Antennas Propag., 1994, 42, (3), pp. 320-328 absorbing boundary conditions', IEEE Trans. Antennas Propag., 1995, 43, (5), pp. 478437 6 RIUS, J.M., CARPINTERO, c.P., CARDAMA, A., and MOSIG, J.R.: 'The theoretical error in the integral equation MEI', Electron. Lett., 1996, 32, (23), pp. 2131-2132 7 RIUS, J M., CARPINTERO, c P , CARDAMA, A., and MICHALSKI, K.A.: 'Analysis of electrically large concave scatterers with the integral equation MEI', Microw. Opt. Technol. Lett., 1997, 14, (5), pp. 287- 289 5 STUPFEL, B., and MITTRA, R.: 'A theoretical study Of numerical 2030 ELECTRONICS LETTERS 20th November 7997 Vol. 33 No. 24 8 JEVTIC, J.O., and LEE, R.: 'A theoretical and numerical analysis of the measured equation of invariance', IEEE Trans. Antennas Propag., 9 RAO, s.M., WILTON, D.R., and GLISSON, A.w.: 'Electromagnetic scattering by surfaces of arbitrary shape', IEEE Trans. Antennas Propag., 1982, 30, (3), pp. 409418 1994, 42, (8), pp. 1097-1105 Measuring image edge detector accuracy using realistically simulated edges R.C. Staunton Indexing terms: Edge detection, Image processing Edge detector tests using edges derived from the acquisition system's edge spread function are described. The test edges used are the most difficult that could exist in a practical system. The results were significantly different to those obtained by traditional methods, indicating that simpler detectors may suffice for some applications. Introduction: The analogue front end components of a digital imaging system lowpass filter the signals they process. The camera's lens and its charge coupled device (CCD) array are twodimensional (2D) filters, whereas the camera electronics and the digitiser's antialiasing fdter are one-dimensional (ID). Their combined effect, the front end modulation transfer function (MTF), can be measured in 2D [I] and has been used here to enable the simulation of realistic edges on which to test and compare detectors. Edge model: Step edges are considered to be the most difficult edges to detect accurately [2] and, after modification to allow for a pixel shaped windowing of the data while sampling, have been used to test detectors [3, 41. Here, the windowing is replaced by a realistic physical model for modifying the step edge based on the system's edge spread function (ESF). The ESF can be measured uniquely for each system and is one step in the calculation of the MTF. Results from the two edge models have been compared here, as have the gradient and angular accuracy of a number of commonly used first-order detectors. The high resolution ESF was scanned vertically through a 2D space to produce an effectively continuous image of an edge. A sampling grid was then applied at ten thousand random positions and orientations with respect to ~ A 60 50 40 30 20 signal-to-noise ratio, dB Fig. I Effect of noise on SD of gradient estimation (each mean value scaled to 100) (i) standard cubic facet 5 x 5 (ii) Sobel 3 X 3 (iii) Prewitt 5 X 5 (iv) Sobel 5 X 5 (v) Integrated directional derivative (IDD) 5 X 5 (vi) IDD 7 X 7 Edge contrast = 255 units ELECTRONICS LETTERS 20th November 1997 Vol. this edge. The resampled images were constrained so that the edge always passed through the central pixel, and were used to provide accurate test data. The new edge model was obtained from the ID ESF by combining the results from many CCD elements, and the test data were reasonably noise free. Gaussian distributed random noise was added to the sampled intensity values. The signal-to-noise ratio was defined as SNR = 2010g,, (5) [dB] CT where c = 255 is the edge contrast and CJ the standard deviation (SD) of the noise. L ioo .- I .- a rl I (vi) _,., ," I ," 60 50 40 30 20 signal-to-mise mtio 1764/2/ Fig. 2 Effect of noise on SD of angle ewer Traces labelled as in Fig. 1. Edge contrast = 255 units Operator performance: For first derivative detectors, errors occur in gradient and angle measurements. Pairs of detectors were used to return horizontal and vertical gradlient vectors. These were analysed in the usual way to provide the magnitude of the edge gradient and the angle information. The 2D MTF for the acquisition system [I] was consulted in choosing the most suitable ESF, the sharpest and hence most difficult to detect, on which to test the operators. The operator templates vaned in size from 3 x 3 to 7 x 7 pixels and are described in [4]. A 1,arger template should have a higher noise immunity and produce more accurate results, but may take longer to compute. 10' a ?i C .- I '5 U E U m c L OI - ioo 60 50 4CI 30 20 signal-to-noise ratio, dB /7Mi3] Pig. 3 Comparison of effect of noise on SD of gradient estimation for two edge models (each mean value scaled to 100) Pixel average model: (i) Sobel 3 x 3 (ii) IDD 5 x 5 (iii) IDD 7 x 7 ESF model: (iv) Sobel 3 X 3 (v) IDD 5 X 5 (vi) IDD 7 X 7 33 No. 24 203 1