close

Вход

Забыли?

вход по аккаунту

?

el%3A19931164

код для вставкиСкачать
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
Документ
Категория
Без категории
Просмотров
0
Размер файла
201 Кб
Теги
3a19931164
1/--страниц
Пожаловаться на содержимое документа