Month: March 2022

How is portable AM radio possible?

Posted on by John

The length of antenna you need to receive a radio signal is proportional to the signal’s wavelength, typically 1/2 or 1/4 of the wavelength. Cell phones operate at gigahertz frequencies, and so the antennas are small enough to hide inside the phone.

But AM radio stations operate at much lower frequencies. For example, there’s a local station, KPRC, that broadcasts at 950 kHz, roughly one megahertz. That means the wavelength of their carrier is around 300 meters. An antenna as long as a quarter of a wavelength would be roughly as long as a football field, and yet people listen to AM on portable radios. How is that possible?

looking inside a portable radio

There are two things going on. First, transmitting is very different than receiving in terms of power, and hence in terms of the need for efficiency. People are not transmitting AM signals from portable radios.

Second, the electrical length of an antenna can be longer than its physical length, i.e. an antenna can function as if it were longer than it actually is. When you tune into a radio station, you’re not physically making your antenna longer or shorter, but you’re adjusting electronic components that make it behave as if you were making it longer or shorter. In the case of an AM radio, the electrical length is orders of magnitude more than the physical length. Electrical length and physical length are closer together for transmitting antennas.

Here’s what a friend of mine, Rick Troth, said when I asked him about AM antennas.

If you pop open the case of a portable AM radio, you’ll see a “loop stick”. That’s the AM antenna. (FM broadcast on most portables uses a telescoping antenna.) The loop is tuned by two things: a ferrite core and the tuning capacitor. The core makes the coiled wiring of the antenna resonate close to AM broadcast frequencies. The “multi gang” variable capacitor coupled with the coil forms an LC circuit, for finer tuning. (Other capacitors in the “gang” tune other parts of the radio.) The loop is small, but is tuned for frequencies from 530KHz to 1.7MHz.

Loops are not new. When I was a kid, I took apart so many radios. Most of the older (tube type, and AM only) radios had a loop inside the back panel. Quite different from the loop stick, but similar electrical properties.

Car antennas don’t match the wavelengths for AM broadcast. Never have. That’s a case where matching matters less for receivers. (Probably matters more for satellite frequencies because they’re so weak.) Car antennas, whether whip from decades ago or embedded in the glass, probably match FM broadcast. (About 28 inches per side of a dipole, or a 28 inch quarter wave vertical.) But again, it does matter a little less for receive than for transmit.

In the photo above, courtesy Rick, the AM antenna is the copper coil on the far right. The telescoping antenna outside the case extends to be much longer physically than the AM antenna, even though AM radio waves are two orders of magnitude longer than FM radio waves.

Applications of continued fractions

Posted on by John

At first glance, continued fractions look more like a curiosity than like useful mathematics. And yet they come up surprisingly often in applications.

For an irrational number x, the numbers you get by truncating the infinite continued fraction for x are the optimal rational approximations to x given the size of their denominators. For example, since

π = 3.141592…

you could obviously approximate π by 31/10, but 22/7 is more accurate and has a smaller denominator. Similarly, if you wanted to approximate π using a fraction with a four-digit denominator, you could use 31415/10000 = 6283/2000, but 355/113 is much more accurate and uses a smaller denominator. Continued fractions are how you find optimal approximations like 22/7 and 355/113. More examples here.

Optimal rational approximations have widespread uses. They explain, for example, why some complicated calendar systems are the way they are. The ratios of astronomical periods, such as that of the earth’s orbit around the sun to that of the earth’s notation, are not rational, and calendar systems amount to constructing rational approximations. More on that here.

Aside from constructing rational approximations, continued fractions are often used to efficiently evaluate mathematical functions. For example, I’ve written about how continued fractions are used in computing hazard functions and entropy.

 

Smoothed step function

Posted on by John

I mentioned smoothed step functions in the previous post. What would you do if you needed to concretely use a smoothed step function and not just know that one exists?

We’ll look at smoothed versions of the signum function

sgn(x) = x / |x|

which equals −1 for negative x and +1 for positive x. We could just as easily looked at the Heaviside function H(x), which is 0 for negative x and 1 for positive x, because

H(x) = (1 + sgn(x))/2

and so if we can approximate signum we can approximate the Heaviside function.

We want our approximation of sgn(x) to be −1 for x < −c and +1 for x > c. We also want our approximation to be smooth everywhere and monotone increasing on [−c, c].

Approximate solution

Things are much simpler if we’re willing to tolerate a small error in the flat regions. Then we could use

f(x; k) = 2 arctan(kx)/π

or

g(x; k) = tanh(kx).

The parameter k controls how sharply the function rises in the transition interval [−c, c], with larger values of k corresponding to steeper transitions. You could solve for the value of k that gives you the desired slope at 0, or that meets your error tolerance at ±c.

Here’s a plot of hyperbolic tangent, i.e g(x; 1).

hyperbolic tangent tanh

Solving for the parameter k

The derivative of f(x; k) at zero is 2k/π. So if your desired slope is m, then

k = πm/2.

The derivative of g(x; k) at zero is simply k, so set k = m.

If you want the value of your approximation to be between 1 − ε and 1 for x > c, and by symmetry between −1 and -1 + ε for x < −c, you can solve

f(c, k) = 1 − ε

to get

k = tan(π(1 − ε)/2)/c

or solve

g(c, k) = 1 − ε

to get

k =  arctanh(1 − ε)/c.

If you don’t have a way to directly compute arctanh, you can use

arctanh(x) = log( (1 + x) √(1/(1 − x²)) ).

The equation above and similar equations can be found here.

Exact solution

It would be unusual to need an exact explicit solution. In applications, you need to be explicit but not exact. In theoretical work, you often need to be exact but not explicit. I will outline a way to create an smoothed step function that is n times differentiable.

Let f(x; a) be the PDF of a Beta(a, a) random variable and let F(x; a) be the corresponding CDF. Then F(x; a) = 0 for x < 0 and F(x; a) = 1 for x > 1.

If a is greater than n then F is n-times differentiable at 0, and by symmetry the same holds at 1. For integer a, F(x; a) is a polynomial over [0, 1], but a needs to be large enough that the first n derivatives are all 0 at the ends.

The larger a is, the steeper F is in the middle. F has a transition zone over [0, 1], but you can shift and scale F to transition over [−c, c].

Related posts

Partitions of unity, smooth ramps, and CW clicks

Posted on by John

Partitions of unity are a handy technical device. They’re seldom the focus of attention but rather are buried in the middle of proofs.

The name sounds odd, but it’s descriptive. A partition of unity is a set of smooth functions into the interval [0, 1] that add up to 1 at every point. The functions split up (partition) the number 1 (unity) at each point. The functions are chosen to have properties that let you glue together local results to create a global result.

Smooth ramp functions

Proving the existence of partitions of unity with the desired properties isn’t trivial. One of the steps along the way is to prove that you can create functions than ramp up smoothly between constant values. You want to show there are functions f that equal 0 on one side of a closed interval [a, b] and equal 1 on the other side. That is, you can choose f such that f(x) = 0 for x ≤ a and f(x) = 1 for x ≥ b. You can also require f to be monotone increasing over the interval [a, b].

It may seem obvious that smooth ramp functions exist, but they do not exist if you require your functions to have a power series at every point. Ramp functions can be infinitely differentiable, but they cannot be analytic.

Smooth ramp functions are used everywhere, but they’re complicated to write down explicitly.

CW clicks

Morse code is sent over a radio using CW, continuous wave. The name is historical, contrasting with an early method known as damped wave.

To send a dot or a dash, you send a short or a long pulse of a fixed pitch. If you abruptly turn this tone on and off you’ll create noisy side effects called clicks. As I wrote about in this post, an abrupt change in frequency creates broad spectrum side effects, but smoothing the transition greatly reduces the bandwidth.

The recommended rise and fall time for a CW pulse is between 2 and 4 milliseconds. So if a dot is transmitted as a 50 ms pulse, your equipment might shape the pulse to be a 42 ms pulse at full amplitude with 4 ms transitions on each side where the amplitude smoothly rises and falls. That is, you multiply your pulse by a couple of smooth ramp functions as described above.

Here’s a plot for a pulse of a 800 Hz tone.

This minor modification of pulses makes no audible difference to the desired signal but greatly reduces unwanted effects.

Related posts

Looking for the next prime

Posted on by John

Suppose you start with some large number x and want to find a prime number at least as big as x. First you test whether x is prime. Then you test whether x + 1 is prime. Then you test whether x + 2 is prime, and so on until you find a prime. Of course you would just test odd numbers, but how far might you have to look? How much larger than x might your result be?

Bertrand conjectured, and Chebyshev proved, that you’ll find a prime before you get to 2x. Said another way, the width of the interval you need to explore is no larger than x.

Note that if we just want to find a prime of a certain order of magnitude, the most efficient approach is to try numbers at random until you find one. But if you want to find the next prime you have to search more methodically. Maybe there’s a better way to do this than sequentially testing odd numbers. In any case, this post looks at an upper on the result you get, regardless of how you go about finding it.

New results

In [1] the authors prove that the length of the interval to search can be orders of magnitude smaller than x. For example, if

x > e60

then the interval can be of length x/1016.

The authors state their results in the form of an interval up to x rather than an interval starting at x, so their theorems immediately apply to starting at x and searching backward for the largest prime no greater than x. But by changing what you call x you could apply the results to looking forward for the smallest prime no smaller than x.

Illustration related to cryptography

Let’s see what the results in [1] might say about primes of the size used in cryptography. For example, RSA and Diffie-Hellman work with primes on the order of 22048 or 23072. More on that here.

If x is a 2048-bit integer x, then log x is around 1420. The authors in [1] show that if

log x > 1200

then the length of the interval to explore has width less than x/Δ where Δ = 3.637×10263.

Now if x is a 2048-bit number then we need to explore an interval of length less than

22048 / 3.637 × 10263 ≈ 22048/ 2857.5 = 21172.5.

So for a 2048-bit number, the length of the interval to search is a 1173 bit number. Said another way, we can turn x into a prime number by only changing the last 1173 bits, leaving the top 875 bits alone.

The number of bits in the length of the interval to search is a little more than half the number of bits in x; we can turn x into a prime by modifying a little more than half its bits.This is a general result for sufficiently large x.

The key contribution of [1] is that they’re explicit about what “sufficiently large” means for their theorems. There are other theorems that are not explicit. For example, in [2] the authors prove that for large enough x, the interval to search has width x0.525, but they don’t say how large x has to be.

If 22048 is large enough for the theorem in [2] to hold, then the length of our interval could be a 1076-bit integer.

Related posts

[1] Michaela Cully-Hugill and Ethan S. Lee. Explicit interval estimates for prime numbers. Mathematics of Computation. https://doi.org/10.1090/mcom/3719. Article electronically published on January 25, 2022

[2] R. C. Baker, G. Harman, and J. Pintz, The difference between consecutive primes. II, Proc. London Math. Soc. (3) 83 (2001), no. 3, 532–562.

Series for π

Posted on by John

Here’s a curious series for π that I ran across on Math Overflow.

\sum_{j=1}^\infty \frac{(2j-3)!! \, (2j-1)!!}{(2j-2)!! \,(2j+2)!!} = \frac{2}{3\pi}

In case you’re unfamiliar with the notation, n!! is n double factorial, the product of the positive integers up to n with the same parity as n. More on that here.

When n is 0 or −1, n!! is defined to be 1, which is needed above. You could justify this by saying the product is empty, and an empty product is 1. More on that here.

Someone commented on Math Overflow that Mathematica could calculate this sum, so I gave it a try.

    f[j_] := (2 j - 3)!! (2 j - 1)!! /((2 j - 2)!! (2 j + 2)!!)
    Sum[f[j], {j, 1, Infinity}]

Sure enough, Mathematica returns 2/3π.

It’s a slowly converging series as Mathematica can also show.

    In:  N[Sum[f[j], {j, 1, 100}]]
    Out: 0.210629
    In:  N[2/(3 Pi)]
    Out: 0.212207

If you’re curious about series for calculating π that converge quickly, here’s an algorithm that was once used for a world record calculation of π.

Related posts

Morse code numbers and abbreviations

Posted on by John

Numbers in Morse code seem a little strange. Here they are:

    |-------+-------|
    | Digit | Code  |
    |-------+-------|
    |     1 | .---- |
    |     2 | ..--- |
    |     3 | ...-- |
    |     4 | ....- |
    |     5 | ..... |
    |     6 | -.... |
    |     7 | --... |
    |     8 | ---.. |
    |     9 | ----. |
    |     0 | ----- |
    |-------+-------|

They’re fairly regular, but not quite. That’s why a couple years ago I thought it would be an interesting exercise to write terse code to encode and decode digits in Morse code. There’s exploitable regularity, but it’s irregular enough to make the exercise challenging.

Design

As with so many things, this scheme makes more sense than it seems at first. When you ask “Why didn’t they just …” there’s often a non-obvious answer.

The letters largely exhausted the possibilities of up to 4 dots and dashes. Some digits would have to take five symbols, and it makes sense that they would all take 5 symbols. But why the ones above? This scheme uses a lot of dashes, and dashes take three times longer to transmit than dots.

A more efficient scheme would be to use binary notation, with dot for 0’s and dash for 1’s. That way the leading symbol would always be a dot and usually the second would be a dot. That’s when encoding digits 0 through 9. As a bonus you could use the same scheme to encode larger numbers in a single Morse code entity.

The problem with this scheme is that Morse code is intended for humans to decode by ear. A binary scheme would be hard to hear. The scheme actually used is easy to hear because you only change from dot to dash at most once. As Morse code entities get longer, the patterns get simpler. Punctuation marks take six or more dots and dashes, but they have simple patterns that are easy to hear.

Code golf

When I posed my coding exercise as a challenge, the winner was Carlos Luna-Mota with the following Python code.

    S="----.....-----"
    e=lambda x:S[9-x:14-x]
    d=lambda x:9-S.find(x)

Honorable mention goes to Manuel Eberl with the following code. It only does decoding, but is quite clever and short.

    d=lambda c:hash(c+'BvS+')%10

It only works in Python 2 because it depends on the specific hashing algorithm used in earlier versions of Python.

Cut numbers

If you’re mixing letters and digits, digits have to be five symbols long. But if you know that characters have to be digits in some context, this opens up the possibility of shorter encodings.

The most common abbreviations are T for 0 and N for 9. For example, a signal report is always three digits, and someone may send 5NN rather than 599 because in that context it’s clear that the N’s represent 9s.

When T abbreviates 0 it might be a “long dash,” slightly longer than a dash meant to represent a T. This is not strictly according to Hoyle but sometimes done.

There are more abbreviations, so called cut numbers, though these are much less common and therefore less likely to be understood.

    |-------+-------+-----+--------+----|
    | Digit | Code  |  T1 | Abbrev | T2 |
    |-------+-------+-----+--------+----|
    |     1 | .---- |  17 | .-     |  5 |
    |     2 | ..--- |  15 | ..-    |  7 |
    |     3 | ...-- |  13 | ...-   |  9 |
    |     4 | ....- |  11 | ....-  | 11 |
    |     5 | ..... |   9 | .      |  1 |
    |     6 | -.... |  11 | -....  | 11 |
    |     7 | --... |  13 | -...   |  9 |
    |     8 | ---.. |  15 | -..    |  7 |
    |     9 | ----. |  17 | -.     |  5 |
    |     0 | ----- |  19 | -      |  3 |
    |-------+-------+-----+--------+----|
    | Total |       | 140 |        | 68 |
    |-------+-------+-----+--------+----|

The space between dots and dashes is equal to one dot, and the length of a dash is the length of three dots. So the time required to send a sequence of dots and dashes equals

2(# dots) + 4(# dashes) – 1

In the table above, T1 is the time to transmit a digit, in units of dots, without abbreviation, and T2 is the time with abbreviation. Both the maximum time and the average time are cut approximately in half. Of course that’s ideal transmission efficiency, not psychological efficiency. If the abbreviations are not understood on the receiving end and the receiver asks for numbers to be repeated, the shortcut turns into a longcut.

Related posts

Multiple Frequency Shift Keying

Posted on by John

A few days ago I wrote about Frequency Shift Keying (FSK), a way to encode digital data in an analog signal using two frequencies. The extension to multiple frequencies is called, unsurprisingly, Multiple Frequency Shift Keying (MFSK). What is surprising is how MFSK sounds.

When I first heard MFSK I immediately recognized it as an old science fiction sound effect. I believe it was used in the original Star Trek series and other shows. The sound is in once sense very unusual, which is why it was chosen as a sound effect. But in another sense it’s familiar, precisely because it has been used as a sound effect.

Each FSK pulse has two possible states and so carries one bit of information. Each MFSK pulse has 2n possible states and so carries n bits of information. In practice n is often 3, 4, or 5.

Why does it sound strange?

An MFSK signal will jump between the possible frequencies in no apparent; if the data is compressed before encoding, the sequence of frequencies will sound random. But random notes on a piano don’t sound like science fiction sound effects. The frequencies account for most of the strangeness.

MFSK divides its allowed bandwidth into uniform frequency intervals. For example, a 500 Hz bandwidth might be divided into 32 frequencies, each 500/32 Hz apart. The tones sound strange because they are uniformly on a linear scale, whereas we’re used to hearing notes uniformly spaced on a logarithmic scale. (More on that here.)

In a standard 12-note chromatic scale, the ratios between consecutive frequencies is constant, each frequency being about 6% larger than the previous one. More precisely, the ratio between consecutive frequencies equals the 12th root of 2. So if you take the logarithm in base 2, the distance between each of the notes is 1/12.

In MFSK the difference between consecutive frequencies is constant, not the ratio. This means the higher frequencies will sound closer together because their ratios are closer together.

Pulse shaping

As I discussed in the post on FSK, abrupt frequency changes would cause a signal to use an awful lot of bandwidth. The same is true of MFSK, and as before the solution is to taper the pulses to zero on the ends by multiplying each pulse by a windowing function. The FSK post shows how much bandwidth this saves.

When I created the audio files below, at first I didn’t apply pulse shaping. I knew it was important to signal processing, but I didn’t realize how important it is to the sound: you can hear the difference, especially when two consecutive frequencies are the same.

Audio files

The following files are a 5-bit encoding. They encode random numbers k from 0 to 31 as frequencies of 1000 + 1000k/32 Hz.

Here’s what a random sample sounds like at 32 baud (32 frequency changes per second) with pulse shaping.

32 baud

Here’s the same data a little slower, at 16 baud.

16 baud

And here it is even slower, at 8 baud.

8 baud

Examples

If you know of examples of MFSK used as a sound effect, please email me or leave a comment below.

Here’s one example I found: “Sequence 2” from
this page of sound effects sounds like a combination of teletype noise and MFSK. The G7 computer sounds like MFSK too.

Related posts

Dial tone and busy signal

Posted on by John

Henry Lowengard left a comment on my post Phone tones in musical notation mentioning dial tones and busy signals, so I looked these up.

Tones

According to this page, a dial tone in DTMF [1] is a chord of two sine waves at 350 Hz and 440 Hz. In musical notation:

According to the same page, a busy signal is a combination of 480 Hz and 620 Hz with pulses of 1/2 second.

Note that the bottom note is an B half flat, i.e. midway between a B and a B flat, denoted by the backward flat sign. The previous post on DTMF tones also used quarter tone notation because the frequencies don’t align well with a conventional chromatic scale. The frequencies were chosen to be easy to demodulate rather than to be musically in tune.

Audio files

Here are audio files corresponding to the notation above.

dial tone

busy signal.

 

Lilypond code for music

Here is the Lilypond code that was used to make the images above.

    \begin{lilypond}
       \new Staff \with { \omit TimeSignature} { 
           \relative c'{ 1 \fermata | }  
       }
       \new Staff {
            \tempo 4 = 120
            \relative c''{
            <beh dis> r4 <beh dis> r4 | <beh dis> r4 <beh dis> r4 |
            }
        }
    \end{lilypond}

Related posts

[1] Dual-tone multi-frequency signaling, trademarked as Touch-Tone