Digital Signal Processing

By Steven W. Smith, Ph.D.

- 1: The Breadth and Depth of DSP
- 2: Statistics, Probability and Noise
- 3: ADC and DAC
- 4: DSP Software
- 5: Linear Systems
- 6: Convolution
- 7: Properties of Convolution
- 8: The Discrete Fourier Transform
- 9: Applications of the DFT
- 10: Fourier Transform Properties
- 11: Fourier Transform Pairs
- 12: The Fast Fourier Transform
- 13: Continuous Signal Processing
- 14: Introduction to Digital Filters
- 15: Moving Average Filters
- 16: Windowed-Sinc Filters
- 17: Custom Filters
- 18: FFT Convolution
- 19: Recursive Filters
- 20: Chebyshev Filters
- 21: Filter Comparison
- 22: Audio Processing
- 23: Image Formation & Display
- 24: Linear Image Processing
- 25: Special Imaging Techniques
- 26: Neural Networks (and more!)
- 27: Data Compression
- 28: Digital Signal Processors
- 29: Getting Started with DSPs
- 30: Complex Numbers
- 31: The Complex Fourier Transform
- 32: The Laplace Transform
- 33: The z-Transform
- 34: Explaining Benford's Law

Your laser printer will thank you!

Solving Mystery #2

The second mystery is: * Why does one set of numbers follow Benford's law,
while another set of numbers does not?* Again we can answer this
question by examining Fig. 34-5. Our goal is to find the characteristics
of

For *ost(g)* to be a flat line it must have no sinusoidal components. In the
frequency domain this means that *OST(f)* must be equal to zero at all
frequencies above f=0. However, *OST(f)* is equal to *SF(f) × PSF(f)*, and
*SF(f)* is nonzero only at the integer frequencies, f = 0, 1, 2, 3, 4, and so
on. Therefore, *ost(g)* will be flat, if and only if, *PSF(f)* has a value of
zero at the integer frequencies. The particular example in Fig. 34-5
clearly does not meet this condition, and therefore does not follow
Benford's law. In Fig. (d), *PDF(1)* has a value of 0.349. Multiplying this
by the value of *SF(1)* = 0.516, we find *OST(1)* = 0.18. Therefore, *ost(g)*
has a sinusoidal component with a period of one, and an amplitude of
0.18. This is a key result, describing what criterion a distribution must
meet to follow Benford's law. This is important enough that we will
express it as a theorem.

Benford's Law Compliance Theorem

Let P be a random process generating numbers in base B on the linear number line, pdf(g) its probability density function expressed on the base B logarithmic number line, and PDF(f) the Fourier transform of pdf(g). The numbers generated by P will follow Benford's law, if and only if, PDF(f) = 0 at all nonzero integer frequencies.

Our next step is to examine what type of distributions comply with this
theorem. There are two distinct ways that *PDF(f)* can have a value of
zero at the nonzero integer frequencies. As shown in Fig. 34-6b, *PDF(f)*
can be oscillatory, periodically hitting zero at frequencies that include the
integers. In the logarithmic domain this corresponds to two or more
discontinuities spaced an integer distance apart, such as sharp edges or
abrupt changes in the slope. Figure (a) shows an example of this, a
rectangular pulse with edges at -1 and 1. These discontinuities can easily
be created by human manipulation, but seldom occur in natural or
unforced processes. This type of distribution does follow Benford's law,
but it is mainly just a footnote, not the bulk of the mystery.

Figure (d) shows a far more important situation, where *PDF(f)* smoothly
decreases in value with increasing frequency. This behavior is more than
common, it is the rule. It is what you would find for most any set of
random numbers you examine. The key parameter we want to examine is
how fast the curve drops to zero. For instance, the curve in Fig. 34-6d
drops so rapidly that it has a negligible value at f=1 and all higher
frequencies. Therefore, this distribution will follow Benford's law to a
very high degree. Now compare this with Fig. 34-5d, an example where
*PDF(f)* drops much slower. Since it has a significant value at f=1, this
distribution follows Benford's law very poorly.

Now look at *pdf(g)* for the above two examples, Figs. 34-6c and 34-5a.
Both of these are normal distributions on the logarithmic scale; the only
difference between them is their width. A key property of the Fourier
transform is the compression/expansion between the domains. If you
need to refresh your memory, look at Figure 10-12 in chapter 10. In
short, if the signal in one domain is made narrower, the signal in the
other domain will become wider, and vice versa. For example, in Fig.
34-5a the standard deviation of *pdf(g)* is σ_{g} = 0.25. This results in *PDF(f)*
having a standard deviation of: σ_{f} = 1/(2πσ_{g}) = 0.637. In Fig. 34-6 the
log domain is twice as wide, σ_{g} = 0.50, making the frequency domain
twice as narrow, σ_{f} = 0.318. In these figures the width of the distribution
is indicated as 2σ, that is, -σ to σ. This is common, but certainly not the
only way to measure the width.

In short, if *pdf(g)* is narrow, then *PDF(f)* will be wide. This results in
*PDF(f)* having a significant amplitude at f=1, and possibly at higher
frequencies. Therefore, the distribution will not follow Benford's law.
However, if *pdf(g)* is wide, then *PDF(f)* will be narrow. This results in
*PDF(f)* falling near zero before f=1, and Benford's law is followed.

A key issue is how wide or narrow *pdf(g)* needs to be to toggle between
the two behaviors. To follow Benford law, *PDF(f)* must drop to near zero
by f=1. Further, f=1 in the frequency domain corresponds to a sinusoid
with a period of one on the log scale, making this the critical distance.
This gives us the answer to our question. **With a few caveats, Benford's
law is followed by distributions that are wide compared with unit
distance along the logarithmic scale. Likewise, the law is not followed
by distributions that are narrow compared with unit distance.**

To be clear, one exception occurs when *PDF(f)* is oscillatory such as in
Fig. 34-6b. The other exception is when *PDF(f)* does not smoothly
decreases in value with increasing frequency. Also, the definition of
"width" used here is slightly fuzzy. We will improve upon this in the next
section. However, these are minor issues and details; do not let them
distract from your understanding of the mainstream phenomenon.