Electrical computers: arithmetic processing and calculating – Electrical digital calculating computer – Particular function performed
Reexamination Certificate
2000-06-02
2004-06-15
Ngo, Chuong Dinh (Department: 2124)
Electrical computers: arithmetic processing and calculating
Electrical digital calculating computer
Particular function performed
Reexamination Certificate
active
06751642
ABSTRACT:
FIELD OF THE INVENTION
The invention relates to the field of modulation/demodulation of information signals, and, more particularly, to transforming a stream of complex symbols initially formed of N complex samples into a stream of respective groups of 2N real output data using interleaved type processing. The invention applies to systems for transmitting orthogonal frequency division multiplex (OFDM) coded information. These systems form, for example, the sending portion of a very high speed digital modulation/demodulation device (VDSL modem).
BACKGROUND OF THE INVENTION
In OFDM coding, the signal to be transmitted is coded on N carriers which are phase-modulated and amplitude-modulated as a function of the content of the information to be transmitted. Each carrier has a predetermined frequency and all the frequencies of the carriers are a submultiple of a predetermined sampling frequency. Also each symbol formed of N digital carriers, which are N complex samples sampled at the sampling frequency, must be transformed into a group of 2N real data sampled at twice the sampling frequency. This allows transmission over a transmission channel, such as a telephone line.
The transformation of an initial complex symbol respectively formed of N initial complex samples into a group of 2N real output data can be performed in several ways. A first approach performs an inverse Fourier transform of twice the size, that is, of size 2N. However, this approach requires the addition of an extra processing stage as well as the addition of extra memory.
A second approach performs an inverse Fourier transform of the same size, that is, of size N. This is followed by a complex filtering to eliminate part of the spectrum. However, such an implementation leads to a relatively complicated hardware embodiment.
A third approach also performs an inverse Fourier transform of size N, but this is followed by real filtering. However, this approach, which is simpler to implement than the previous approach, is approximate with regards to the accuracy obtained by the signal-to-noise ratio. The signal-to-noise ratio may turn out to be relatively large, thus leading to signal degradations. Also, the increase in the performance of this approach, that is, the reduction in the signal-to-noise ratio, requires the use of an extremely large real filter. This involves an expensive hardware implementation.
Another approach performs the transformation of the stream of initial complex signals respectively formed of N initial complex samples into a stream of respective groups of 2N real output data. This is done by interleaved type processing whose theoretical formulation is well known to one skilled in the art.
The main characteristics of interleaved type precessing will be discussed for all useful purposes. The real signal x(t) corresponding, for example, to an OFDM symbol, is defined by formula (I):
x
(
t
)
=
∑
k
=
1
N
-
1
M
k
·
cos
(
2
π
f
k
t
+
ϕ
k
)
(
I
)
The symbol M
k
denotes the amplitude of the carrier of rank k, &phgr;
k
denotes its phase, f
k
denotes its frequency and N−1 the number of carriers. When the frequencies of the carriers are all multiples of a frequency f
1
, then formula (I) becomes formula (II) in complex notation:
x
(
t
)
=
Re
[
∑
k
=
1
N
-
1
C
k
·
ⅇ
2
j
π
kf
1
t
]
.
(
II
)
The symbol C
k
denotes the initial complex sample representative of the carrier of rank k. C
k
is defined by the formula (III):
C
k
=M
k
·e
j&phgr;
k
(III)
With a sampling of the signal at the frequency Nf
1
and by extending the length of the symbol to N carriers (by adding the carrier C taken equal to 0), it can then be shown that the N real output data of even ranks, corresponding to the N complex samples of the input symbol are given by formula (IV):
{
x
2
p
}
=
Re
(
IFFT
N
{
(
C
k
+
C
_
N
-
k
)
+
j
(
C
k
-
C
_
N
-
k
)
ⅇ
j
π
N
k
}
)
(
IV
)
The real data of odd ranks x
2p+1
are given by formula (V):
{
x
2
p
+
1
}
=
Im
(
IFFT
N
{
(
C
k
+
C
_
N
-
k
)
+
j
(
C
k
-
C
_
N
-
k
)
ⅇ
j
π
N
k
}
)
(
V
)
In these formulas (IV) and (V), {overscore (C)}
N−k
represents the complex conjugate of the complex number C
N−k
, IFFT
N
represents the inverse Fourier transform of size N operator, Im denotes the imaginary part of a complex number, and Re denotes the real part of a complex number.
The processing of the interleaved type includes a preprocessing phase in which, for each initial symbol received formed of N initial complex samples C
k
, an auxiliary symbol formed of N auxiliary complex samples A
k
is formulated. Each auxiliary complex sample A
k
is defined by formula (VI):
A
k
=(
C
k
+{overscore (C)}
N−k
)+
j
(
C
k
−{overscore (C)}
N−k
)e
j&pgr;&kgr;/N
(VI)
After this preprocessing, a processing phase is performed which includes, for each auxiliary symbol formed of the auxiliary samples A
k
, an inverse Fourier transform calculation of size N. The result of this inverse Fourier transform is a set of N complex output coefficients X
k
which, after rearrangement so as to retrieve the input order, makes it easily possible to obtain the 2N real data corresponding to the input symbol. This is so since the real data of even and odd ranks correspond respectively to the real parts and imaginary parts of the complex output samples successively obtained after rearrangement.
At present, the only known implementation of this interleaved processing is an entirely software implementation which turns out to be relatively complex to use in industrial devices, such as modems, for example. Furthermore, the larger the size of the Fourier transform and the greater the increase in processing speed, the more severe the implementation constraints become.
Moreover, numerous implementations of direct or inverse Fourier transforms which are dedicated or programmed on microprocessors for signal processing have been set out in the literature. Most of these implementations use a variation of the Cooley-Tukey algorithm, which makes it possible to reduce the number of arithmetic operations required to calculate the Fourier transform.
The Cooley-Tukey algorithm will be readily understood by one skilled in the art. This algorithm makes it possible, in particular, to reduce the calculation of a fast Fourier transform of initial size r
p
, where r represents the “radix” according to the terminology customarily used by one skilled in the art, into that of r Fourier transforms of size r
p−1
and of additional complex additions and multiplications. By iteratively repeating this reduction, we arrive at the calculation of Fourier transforms of size r, which are easily achievable, especially if r is chosen equal to 2 or 4.
The Cooley-Tukey algorithm uses a calculation graph exhibiting a general butterfly-like structure, well known to one skilled in the art, and is commonly referred to by the term “butterfly”. Several hardware architectures are then possible to implement a butterfly-like calculation structure.
A first approach constructs a hardware operator capable of performing a butterfly type calculation, i.e., per butterfly of the graph. However, this approach is only conceivable with respect to the implementation of Fourier transforms of small size.
A second approach constructs just a single hardware operator of the butterfly type, and is intended for performing in succession the calculations corresponding to all the butterflies of all the stages of the graph. This approach requires a very fast hardware operator, and an input memory which is separate from the memory serving to write the intermediate calculation results. This is done to avoid access conflicts when a data block enters the operator while the previous block is still undergoing processing.
An intermediate approach constructs a hardware operator of the
Barthel Dominique
Cambonie Joël
Lienard Joël
Mazzoni Simone
Mejean Philippe
Allen Dyer Doppelt Milbrath & Gilchrist, P.A.
Jorgenson Lisa K.
Ngo Chuong Dinh
STMicroelectronics S.A.
LandOfFree
Process and device for transforming complex symbols into... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Process and device for transforming complex symbols into..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Process and device for transforming complex symbols into... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3365005