Euler's Revolution

A 300-year-old sudoku puzzle could herald a new digital age. Mathematician Ian Stewart reports

Look carefully,no column or row contains the same combination of coloured squares - perfect for codes

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.

The 36 officers problem

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 existed.
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 6.

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:

4

9

2

3

5

7

8

1

6

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:

1

2

3

2

3

1

3

1

2

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 like 0100011101110101011101101000010111000111. Typically, a block of digits - eight is common - is used to represent a character. For instance, in ASCII code 01000111 represents 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.

Radio days
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 - AM and 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 single frequency.

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:

A 1234 E 1342 I 1423
B 2143 F 2431 J 2314
C 3412 G 3124 K 3241
D 4321 H 4213 L 4132

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.

How codes remove noise

Transmitting a message in code means that we can decipher it even when there is lots of noise. In this example, the permutation code represents a letter as a sequence of five frequencies, transmitted in turn in five successive time slots.The important feature of this code is that its design means it can correct up to four errors in each sequence. For instance, if there is no noise when the letter 'A' is transmitted then the receiver will detect a pulse at frequency 1,then pulses at frequencies 2,3,4,5 in turn. Suppose that the channel suffers from interference,which creates spurious signals on frequencies 3,4,and 5. Then in each time slot, the receiver will detect the intended frequency, along with frequencies 3,4,and 5. So the received signal, in successive time slots, looks like this: 1or3or4or5, 2or3or4or5, 3or4or5, 3or4or5, 3or4or5

This agrees with 12345(A) in all five time slots. But it disagrees with 23451(B) in the first and last slots; with 34512(C) in the last two slots; with 45123(D) in the third and fourth slots; and with 51234(E) in the second and third slots. So, though distorted, the signal must be A,and not any of the other letters. By comparing the received signal with all the possibilities and then choosing the best agreement, the signal is decoded correctly. Now suppose that, as well as this interference, there is a sharp 'bang!' in the fourth time slot that produces all five frequencies. Now the received signal looks like this: 1or3or4or5,2or3or4or5,3or4or5,1or2or3or4or5,3or4or5. Again, this agrees with 12345(A) in all five slots. But it disagrees with 23451 (B) in the first and last slots; with 34512(C) in the last slot; with 45123(D) in the third slot; and with 51234(E) in the second and third slots. Again, by choosing the best agreement we can decode the signal correctly. This five time-slot code can identify up to four errors in each sequence. In fact, the number of errors the code can spot is always one less than the number of time slots, so the greater their number, the more noise the code can cope with.

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, Euler's passion 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 .


MAIN INDEX

REFERENCE GUIDE

TRANSCRIPTS

GLOSSARY

Maths Physics Biology Chemistry Computing Science Electronics Belief Art Philosophy

000webhost logo