A FEW years ago they dug up our road. They dug up every road in town. They
dug up pretty much every road in the UK They were cable TV companies, and
they were installing fibre-optic cables. The roadworks caused gridlock -
and as demand for digital communications grows, we'll need more cables, and
they'll be digging up the roads again. Demand for information-carrying capacity,
or bandwidth, is always likely to exceed supply, because the more capacity
there is, the more ways we will think of to - use it. High-definition TV,
high-definition DVDs, video phones, video-on-demand downloaded to your computer.
Robotic vacuum cleaners controlled over the internet. Three-dimensional TV...
There is another way. Every home in the developed world already has an older
system of cables, installed to carry electrical power. Why can't we make
power cables carry additional signals? Electricity is transmitted at high
voltages, unlike digital signals?, but that's easy to deal with: tiny variations
can be introduced to modulate the power. The big difficulty is that power
cables are extremely noisy - they suffer from a lot of electrical interference.
This noise does not affect their ability to deliver power to your home, but
it would make television unwatchable, phone calls incomprehensible and internet
connections unreliable. Even so, wouldn't it be great to piggyback digital
communications onto the vast, existing infrastructure of the electrical power
industry? The cables are in place, the distribution system is already present
- even the means of levying charges. And aside from laptops and the like,
every TV, stereo and computer already has to be plugged into the mains to
make it work. The same plug could carry the signals. According to Sophie
Huczynska, a mathematician at the University of St Andrews in the UK, who
recently published a survey of the subject, power-line communication (PLC)
is "a technology whose time has come". That's because researchers have recently
been taking a serious look at possible ways to combat power-line noise. And
it recently dawned on some of them that the answer to their troubles may
lie with an old logic puzzle and the musings of a brilliant mathematician
nearly 300 years ago.
Not all noise is equal
Electrical noise is unwanted swings in voltage or current created in electric
circuits, usually due to the random motion of electrons in an electrical
conductor. Noise is already a problem in conventional digital communication,
though on a much lesser scale than in power lines. For TV and the internet,
the main problem is "white" background noise, which is spread fairly smoothly
over a wide range of frequencies like the sounds produced by a waterfall.
A digital signal consists of a series of 0s and 1s, and white noise corrupts
individual bits randomly and independently of each other.
All is not lost, though. There is a way to encode the signal so that errors
in it can be detected and even corrected. Codes have already been devised
to deal with white noise on television and internet signals. It doesn't always
work: if noise affects too many digits, the message just gets lost, which
is why your satellite TV sometimes locks up in bad weather, displaying a
still frame rather than a moving picture. The set-top box is waiting to receive
a complete frame but it's not getting enough of the incoming signal. So it
goes into a sulk and refuses to do anything.
Coding is vital in today's
communications. Computer scientists are continually thinking up new types
of codes for use in modern communications, but those developed so far won't
work for PLC because they are not sophisticated enough to cope with several
different types of interference. The problem is that power lines can suffer
from many different types of interference at once. Power lines operate at
high voltages and have a tendency to produce sparks. So along with the gentle
hiss of white noise, they can suffer persistent interference at specific
frequencies as well as sudden bangs and crashes of "impulse" noise across
many frequencies. All this means codes will have to get a whole lot better
before we can hook up to the internet through the mains. Which is where that
ancient puzzle comes in.
This year marks the 300th anniversary of the birth of Leonhard Euler, one
of the greatest mathematicians who ever lived, and the most prolific. Euler
was Swiss but he spent much of his working life in Germany and Russia, where
he was attached to the court of Catherine the Great. He ranged over the entire
landscape of mathematics - from pure to applied, from number theory to partial
differential equations. To him, it was all one.
Leonhard Euler became drawn into a curious puzzle known
as the 36 officers problem. It asks if it is possible to arrange 36 soldiers
from six different ranks and six different regiments in a square so that
each row and column contains six officers of different ranks (A-F) and different
regiments (1-6). While it is easy to draw a "latin square" for rank or regiment
alone, fitting them together is different matter. Two squares that can be
superimposed in this way are described as orthogonal, and are now called
Euler squares. Euler tried his best to find two 6x6 squares that are orthogonal
to each other, and failed. Every one contained repeat elements as shown in
the example. This convinced him that the puzzle has no answer. However, he
found it was possible to construct orthogonal latin squares for all of the
odd numbers and all multiples of 4. It is impossible to write down two 2x2
squares that are orthogonal to each other, which is easy to prove. That leaves
just the other even numbers that are not multiples of four: 6,10,14,18 and
so on - and Euler conjectured that for these sizes no orthogonal squares
There are 812 million ways to arrange the 36 officers, and even taking short
cuts you can't just list all possible combinations. Nevertheless, in 1901
French mathematician Gaston Tarry proved Euler was right for 6x6 squares.
As it happens, he was wrong about all the others. Ernest Tilden Parker
constructed two orthogonal 10x10 Euler squares in 1959, and by the following
year Parker, Raj Chandra Bose and Sharadachandra Shankar Shrikhande had proved
that it was possible to create a Euler square for every number over 3 except
Euler created and developed several branches of mathematics, and in 1782
he started thinking about a mathematical game called "magic squares", in
which numbers are arranged in a square grid so that all rows and columns
add up to the same thing. For instance, the numbers 1to 9 can he arranged
so that every row, column, and indeed diagonal, adds up to 15:
This pattern was known to the Chinese more than 3000 years ago. They called
it the Lo Shu and according to legend it first appeared on the shell of a
magic turtle. But Euler's fertile brain was heading in another direction,
and he published a new type of magic square in which each number appears
only once in each column and row:
This square, which will be immediately familiar to any player of sudoku,
is called Latin square, because Euler first created one using Latin characters.
Euler's work on Latin squares and related topics founded a branch of mathematics
known as combinatorics, which deals with ways to arrange things and
how to count such arrangements. Combinatorics has become a major area of
mathematics with real-world applications. One of the earliest uses of Latin
squares was rather unexpected: they turned out to be useful for testing new
vegetable varieties - if you use them to lay out plots for different varieties
it eliminates any variation in results due to soil quality. The new application
to codes in digital electronics is distinctly more high-tech. To see how
it goes, we must take a look at how digital codes work, and what they are
good for. A conventional digital message is a string of binary bits, something
Typically, a block of digits - eight is common - is used to represent a
character. For instance, in ASCII code
the letter G.
There are various ways to create an error-correcting code, and one of the
simplest is to repeat each bit. For instance, 0 and 1 could be represented
as 000 and 111, meaning the letter G would be transmitted as 000111000
000000111111111. Then suppose that the block 101 is received as part of the
signal. Since it's not a possible combination, there must have been an error.
Either the message was 111 and the middle bit has become 0, or it was 000
and the first and third bits have become 1. We can't be certain which, hut
we can be certain that something is wrong. If we - or the hardware and software
in our electronic devices - assume that only one error has occurred, the
most likely scenario, then the block can be corrected to 111.
This rather simple code is not very efficient, however. It amounts to sending
the entire message three times and taking a majority vote on each block.
That's fine for signals that have a relatively low level of noise, such as
the internet, but it's no good for PLC. Interference on power lines is far
from rare, and persistent noise may affect long segments of the message.
Happily, there are more efficient and more cunning error-correcting codes,
and a lot of effort has gone into finding them.
One promising alternative is based on an idea from the early days of radio.
There are two ways to transmit radio signals -
FM. With AM, or amplitude
modulation, the signal has a fixed frequency and its strength, or amplitude,
is varied to represent the sounds. Alternatively, you can fix the amplitude
and vary the frequency; this is frequency modulation, or FM. The advantage
of FM is that unlike AM, the signal is not greatly affected by noise at a
Error-correcting codes for PLC exploit this, by representing a block of bits
from the signal as a series of pulses of various frequencies. The simplest
codes, and the most useful, are called permutation codes. For instance, we
could write a message using a five-letter alphabet A, B, C, D, E and then
send a coded form, where the permutation code represents each letter as a
sequence of five frequencies, transmitted in turn in five successive time
slots (see "How codes remove noise", below).
A good permutation code uses a smallish list of frequencies (to avoid hogging
bandwidth) to represent a large number of characters (to keep coded messages
short) with a large number of time slots (to correct more errors). Of course,
these desirable characteristics conflict with each other.
This is where Euler's work comes in. It drew mathematicians' attention to
orthogonal systems of Latin squares (see "The 36 officers
problem", above). In 2004 Charles Colbourn of Arizona State University
in Tempe, Torleiv Kiave of the University of Bergen, Norway, and A.C.H. Ling
at the University of Waterloo in Ontario, Canada, discovered how to construct
good permutation codes from sets of mutually orthogonal Latin squares.
For instance, with four possible frequencies - 1,2,3 and 4 - to choose from,
and a 12-letter alphabet to work with, a possible code is:
The numbers in the first four rows form a Latin square. The next four rows
form a second Latin square that is orthogonal to the first one. The final
four rows form a Latin square orthogonal to both of the previous squares.
Giving each letter a combination of frequencies determined by orthogonal
Latin squares, as many as 12 letters can be represented using a code constructed
from only four different frequencies in just four time slots.
To see how this type of code can correct errors, suppose you were trying
to transmit the letter A, and there was interference at frequencies 1and
2 in all four time slots. Instead of 1,2,3,4, the signal would be 12,12,123,124.
No other letter in the alphabet agrees with the other possible combinations
created by the error, so it can be detected and corrected to an A.The system
can detect only two errors in a four frequency sequence, but its ability
to create a code from fewer frequencies and time slots than other codes makes
up for that.
Orthogonal squares of larger sizes can be used to create permutation codes
for longer lists of characters, though the procedure is more complicated
than this example. And if the number of frequencies in a row is a prime,
or some power of a prime, then orthogonal squares produce the most effective
error-detecting codes. A code good enough, in fact, to begin to make PLC
feasible. Getting PLC accepted won't be easy, though. New technologies always
have trouble supplanting existing ones. Then, there are unexpected obstacles
- for instance in the UK, lamp posts are just the right size and shape to
act as antennas and create spurious signals. But after nearly three centuries,
for puzzles is helping engineers to overcome the biggest obstacle: noise.
Digital communications are making ever-increasing use of mathematics that
was originally invented because it was interesting, or fun, and had no hint
of application. It pays to let mathematicians play.
Further Reading: "Powerline communication and the 36 officers problem"
by Sophie Huczynska, Philosophical Transactions of the Royal Society A,
vol 364, p3199 .