25 June 1993 0 IEE 1993 Electronics Letters Online No: 19931128 N. F. Zein and T. G. Clarkson (Communications Research Group, King’s College London, Strand, London, WCZR ZLS, United Kingdom) b References MATSUMODO, I., and HIGASHI,A.: ‘Performance analysis of RScoded M-ary FSK for frequency-hopping spread spectrum mobile radios’, IEEE Trans., 1992, VT-Il, (3) pp. 266-270 FRANKS, L.E.: ‘Camer and hit synchronization in data communication-tutorial review’, IEEE Truns., 1980, COM-28, (8), pp. 1107-I120 PURSLEY, t a m . : ‘New approaches for error correction in frequencyhopping spread-spectrum receivers’, IEEE Second Int. Symp. on Spread Spectrum Techniques and Applications (ISSSTAYZ), 29-2 November-December 1992 SKLAR, m.: ‘Digital communications, fundamentals and applications’ (Prentice-Hall International Editions, New Jersey USA, 1988) 1:- 1.m L )538111 Fig. 1 Definition of basic cell (array 3 ) Fig. 2 Systolic allpass digitalfilter (array 3) Realisation of high-speed systolic IIR decimators and interpolators H.K. Kwan Indexinl: terms: Systolic arrays, Diniral filters Two novel systolic allpass digital filtering arrays for realising high-speed systolic IIR decimators and interpolators are described. The sampling period at the input of such a decimator by N and at the output of such an interpolator by N can he reduced to (TM+2T,)I(N-I)and (T,,,+3Ta)/N,respectively, by the two arrays. (T,,,and T., respectively, represent the times for twoinput real multiplication and two-input real addition.) Other advantages include reduced latencies, and reduced numbers of multipliers and adders. where AArY represents the ith distinct allpass digital filter of H ( r ’ ) . The order of the allpass filters, AArN) (for i = 0 to N - l), can be any integer value of M . A high-speed systolic decimator realised using either array 2 or array 3 is shown in Fig. 3. In this systolic decimator, a delay of z-I is inserted at the output of each of the N arrays as well as at the output of the decimator for pipelining purpose. The input commutator switch operates in a round-robin fashion. The minimum sampling rates at the decimator input, T,,,,., are (T, + 2T,)/(N-l) and (T, + 3T,)/N, respectively, for arrays 2 and 3. The latencies of this systolic decimator are ((N - 1)M + 2)Tm,and (NM + 2)T,,,,, respectively, for arrays 2 and 3. U&$ \ introduction: Decimators and interpolators are key subsystems in FDM to TDM and TDM to FDM translations, and other multirate digital systems [l]. Systolisation [2-31 is a useful technique for high-speed digital processing. The application of systolisation to decimation and interpolation is of special interest in high-speed processing [45]. N-slow allpass digital filters present an important class of digital fiters which can be used as building blocks for IIR decimators and interpolators [5]. In [5], a systolic realisation of a decimator and an interpolator using a cascaded systolic first-order N-slow allpass digital filtering array, without an optimal number of multipliers, was proposed. For simplicity, we shall call this array ‘array 1’. In [6], a novel systolic array for realising an Mthorder N-slow allpass digital filter with an optimal number of multipliers was presented. We shall call this array ‘array 2’. In this Letter a new systolic allpass digital filtering array is presented. We shall call this array ‘array 3’. Also shown in this Letter is a systolic approach in which either array 2 or array 3 can be used as building blocks for realising high-speed systolic decimators and interpolators. Details of array 2 can be found in [6]. In the following Section we focus on the description of array 3. New systolic allpass digital filter: Array 3: An N-slow allpass digital filter A,{rY of arbitrary order M can be represented by M = M b,,M-,Z-mN / b,,,t-”N (1: ,=O WL=O where b,,, = 1.0. Define a basic cell as shown in Fig. 1. The basic cell consists of one multiplier and two adders. A systolic array realisation of A,&? as defined in eqn. 1 can be obtained by connecting M basic cells in the way as shown in Fig. 2. \\ . array 0 Fig. 3 High-speed systolic IIR decimator High-speed systolic interpolator: A high-speed systolic interpolator using either array 2 or array 3 is shown in Fig. 4. An additional delay of 2.’ is inserted at the output of each of the N arrays for pipelining purposes. The output commutator switch operates in a round-robin fashion. The minimum sampling rates at the systolic interpolator output, T,,,,, are (T, + 2T,)/(N - 1) and (T, + 3T,)/N, respectively, for arrays 2 and 3. The latencies of this systolic interpolator are ((N - l)M + l ) T m mand ( N M + l)Tmm,respectively, for arrays 2 and 3. x(kN) ~j < A (i~ array ) o A, (z+)array 0 ANjiN) array High-speed systolic decimator; The transfer function of an IIR decimator and interpolator can be expressed as N-1 1748 m Fig. 4 High-speed systolic IIR interpolator ELECTRONICS LETTERS 30th September 1993 Vol. 29 No. 20 Comparisons: The major differences among arrays 1-3 are summarised in Table I . In both systolic decimator and interpolator, array 2 cannot operate at a clock rate of N times T,,,,, whereas arrays 1 and 3 can. In terms of hardware requirements, Contractivity of fractal transforms for image coding B. Hiirtgen Table 1: Comparisons of three allpass systolic arrays 1 [SI T,,,+2Ta) Yes 8M No (3N-I) Indexing terms: Fractals, Image codinn Latency Number Number of of ultiulie adders 2NMT,,,," 4 M 4M ii:$ 1 aj 1 -~ In the Letter the contractivity of existing fractal transforms for use in image compression schemes is examined. The coding process is described as nonlinear transformation in the finitedimensional Euclidean vector space. Sufticient conditions are derived for contractivity based on the spectral norm and the spectral radius of the transformation matnx. As a result hounds for the encoding parameters can be formulated which are tighter than those ones known so far /N 2 [6] 3 Tm+2T,) Yes (N-I) 3 M lN z k l l M 2M+I M 2M+1 array 3 is the lowest, followed by array 2, and then array 1. In terms of T,,,, of the systolic decimator and interpolator, array 3 is slightly faster than arrays 1 and 2 for N below (T,JT,)+3. The situation is the reverse for N above (T,,,/T,)+3.However, this T,," difference is not significant, especially for large N . The latency of array 2 is marginally shorter than that of array 3 hut is much shorter than that of array I . Array 3 is the only array that has broadcasting recursive output. However, this is not a critical factor for small M and especially when N is large. Overall, array 3 is the best choice in terms of simplicity in both its N-slow operations (especially for large N) and hardware requirements. Conclusion: In this Letter, two allpass systolic arrays for the realisation of high-speed systolic IIR decimators and interpolators has been presented. Both arrays 2 and 3 are characterised by having an optimal number of multipliers, and only one type of basic cell (which makes the design modular), and all basic cells are nearestneighbour-connected. The overall structures of the systolic decimator and interpolator are systolic and regular. All the above features are attractive for circuit integration. Through the use of arrays 2 and 3 , the sampling rates at the decimator input and at the interpolator output are, respectively, reduced to (T, + 2T,)/(N - 1) and (T, + 3 T J N . This is significant in high-speed decimation and interpolation applications especially when N is large. Other high-speed applications of array 3 include delayed N-path digital filtering 161. 28 June 1993 Electronics Letters Online No: 19931129 H. K. Kwan (Department of Electrical Engineering, University of Windsor, 401 Sunset Avenue, Windsor, Ontario N9B 3P4, Canada ) Infroduction: Barnsley's idea to exploit self-similar structures in real world images [I] for compression purposes found its first practical implementation capable of encoding grey-scale images in Jacquin's approach [2]. Several improvements and modifications, e.g. [3-71 have been reported, where the basic concept of blockwise approximation of the image by parts of itself is adopted. In this Letter we restrict our considerations to the contractivity of the used transformation which is a vital presupposition for the functionality of these schemes. The results of OUT investigations provide us more freedom in the choice of the encoding parameters which leads to distinct improvements in terms of convergence speed, reconstruction quality and compression ratio. Theory: Let x = (x,, x2, ..., x.),' he an image of size n = n p y pixels which we consider as a point in the n-dimensional Euclidean vector space R". The components x,; 1 5 i s n; x, E R represent the pixels of the image. By defining the Euclidean norm 1 1 ~ 1 1:= %4 and inducing a metric Q(X,Y) := Ilx -YII, (2: mations within this space are described by linear operators A : +R ',for which the spectral- or Hilbert-norm defined by IIAllsp := R" (3: SUP itc(ATA) is a consistent operator norm in the sense that llkrll 5 IIAII llxll holds. U ( A r A ) is called the spectrum of the matrix ArA which is the set of its eigenvalues h. Additionally, for every linear operator A the spectral radius T, ( A ) is defined by References ~ ~ ( := - 4 )SUP R.E., and RABINER, LR.: 'Multirate digital signal processing' (Prentice Hall, New Jersey, 1983) HUNG, H T : 'Why systolic architectures'. IEEE Comput. Mag., January 1982, pp. 3 7 4 6 KUNG, s.Y.: 'VLSI array processors' (Prentice Hall, New Jersey, 1988) KWAN. H K , and OKULLO-OBALLA, T.s.: 'Systolic array implementation of linear phase FIR decimators and interpolators'. Proc. of 31st Midwest Symp. on Circuits and Systems, August 1988, (St. Louis, Missouri, USA) pp. 59-62 KWAN, H K, and OKULLO-OBALLA, T.S : 'Systolic array implementation of a decimator and an interpolator', IEE Proc E, 1988, 135, ( l ) , pp. 7&72 KWAN. H.K: 'Improved systolic allpass digital filters for very highspeed applications', Electron. Lett., 1992, 28, (22), pp. 2061-2062 VX,Y E R" R' becomes a normed metric space denoted by (R",p). Transfor- 0 IEE 1993 CROCHIERE, (1: AWA) 1x1 I IIAll (4: which is a lower bound for any norm ( ( A ( ( . Most implementations emerge from a blockwise defined nonlinear affine transformation W : R" + R" a x + A x + b (5) of the entire image x consisting of a linear part Ax and an additive part b. The encoding process of the given image x now consists in finding a matrix A and a vector b such that the approximation error e(W(x),z)= Q(AX+ 6 , s ) (6: becomes as small as possible. Data compression can he achieved if A and b can he stored more efficiently than the image x itself. Banach's fmed point theorem gives us an idea as to how the decoding process works: Let R" he a metric space with metric p and W : R" + R" a contractive transformation; this is if there exists a constants < 1, for which e(W(x),w(y))I s e(x,y) V ~ , EY R" (7) holds. Then the sequence of images ( x x ) constructed by xx+, = W(x,) converges for any arbitrary initial image xo E R" to the unique fixed point ~f ELECTRONICS LE77ERS 30th September 7993 I I Vol. 29 No. 20 zz W ( Z ~= ) AX, + b; ~f E R" (8) 1749

1/--страниц