Cryptography Reference
In-Depth Information
This basic solution from the Fourier transform includes both real
and imaginary values, something that can be confusing and unnec-
cessary in many situations. For this reason, many also use the
dis-
crete cosine transform
and its cousin the
discrete sine transform
.Both
have their uses, but sine transforms are less common because they
do a poor job of modeling the data near the point
x
=0
when
f
=0
. In fact, most users choose their modeling functions based
on their performance near the endpoints.
Figure 14.5 shows the first four basis functions fromone common
set used for the discrete cosine transform:
2
n
(0)
cos(
π
n
+
1
(
k
2
)
x
)
,k
=0
,
1
,
2
,
3
,...
Another version uses the similar version with a different value at
the endpoint:
2
n
cos(
kπ
n
x
)
,k
=0
,
1
,
2
,
3
,...
Each of these transforms also has an inverse operation. This
is useful because many mathematical operations are easier to do
“in the frequency space”. That is, the amount of energy in each
frequency in the data is computed by constructing the transforms.
Then some basic operations are done on the frequency coefficients,
and the data is then restored with the inverse FFT or DCT.
Figure 14.9 shows the 64
different
two-dimensional cosine
functions used as the
basis functions to model
8 × 8
blocks of pixels for
JPEG and MPEG
compression.
Smoothing data is one operation that is particularly easy to do
with the FFT and DCT— if the fundamental signal is repetitive. Fig-
ure 14.10 shows the four steps in smoothing data with the Fourier
transform. The first graph shows the noisy data. The second shows
the absolute value of the Fourier coefficients. Both
y
251
are
large despite the effect of the noise. The third graph shows the coef-
ficients after all of the small ones are set to zero. The fourth shows the
reconstructed data after taking the inverse Fourier transform. Natu-
rally, this solution works very well when the signal to be cleaned can
be modeled well by sine and cosine functions. If the data doesn't fit
this format, then there are usually smaller distinctions between the
big and little frequencies making it difficult to remove the small fre-
quencies.
y
4
and
14.7 Hiding Informationwith FFTs andDCTs
Fourier transforms provide ideal ways to mix signals and hide infor-
mation by changing the coefficients. A signal that looks like
cos
(4
πx
)
