杏吧原创

LISTEN to two people talking and focus on one voice. Now, swap over and
listen to the other person. What you have just done baffles scientists. When
they reach your ears, the sounds of both voices are superimposed. How does your
brain tease them apart? It鈥檚 as if you鈥檝e been shown a large number and asked
which two smaller numbers were added together to produce it. How could you work
it out? But with voices, your brain somehow gets it right. This ability to
single out one voice from a general hubbub is called the cocktail party effect.
Nobody is sure how the brain does it. Worse, nobody is even sure how to start
finding an answer.

Which is why the machine devised by Tom Ngo and Neal Bhadkamkar of Interval
Research in Palo Alto is remarkable. It doesn鈥檛 calculate the solution directly,
but uses trial and error to crack the problem. It consists of two small
microphones roughly a centimetre apart connected to a computer. Feed these
microphones the racket of two voices and the computer spits out cleaned-up
versions of either one. 鈥淭his is the first time this has been done in real time,
with conversations mixed by the complex acoustics of a real room,鈥� says Ngo.

In theory, splitting up two combined voices is straightforward: take one
voice away from the superposition and you are left with the other. With a few
bells and whistles, this is Ngo鈥檚 approach. Imagine two people, say Andy and
Barbara, talking at the same time and whose combined voices are being recorded
by two microphones X and Y. Because the microphones are a small distance apart,
Andy鈥檚 voice arrives first at microphone X, and a short time later at Y. The
trick to separating them is to work out the delay. Record Andy鈥檚 voice at X,
wait until it arrives at Y and subtract it. What鈥檚 left is Barbara鈥檚 voice.

But how do you work out the delay? After all, it depends on Andy鈥檚 position
relative to the microphones and the computer doesn鈥檛 know where he is. A similar
problem exists for Barbara鈥攚ithout knowing the delay associated with her
voice, the computer cannot remove it from the mix to reveal Andy鈥檚 voice. This
is the challenge. Calculate the right delays and you have solved most of the
problem.

Ngo鈥檚 device tackles the problem by making lots of guesses about what both
Andy鈥檚 and Barbara鈥檚 delays might be. The guesses are generated by a genetic
algorithm which uses the principles of evolution to exploit information learned
on the way. The guesses can be tested and then 鈥渕ated鈥� to produce better
offspring.

The computer evaluates the guesses using a mathematical test known as an
error function. It works by comparing the outputs when the computer guesses both
Andy鈥檚 and Barbara鈥檚 delays. If it guesses right, the two signals should be
entirely dissimilar and summing them over time should produce an average of
zero. But if the guesses are wrong, both outputs contain elements of both voices
and summing them will produce a nonzero average.

In practice, finding the correct delay is tricky. 鈥淚t鈥檚 as if we are trying
to find the bottom of a mathematical ravine,鈥� says Ngo. 鈥淲e drop algorithms into
the ravine and the error function measures how far down they are.鈥� On this
mathematical landscape, the error function can measure the depth at any one
point鈥攖he success of any one guess, that is鈥攂ut it cannot tell where
to go to find a deeper spot. For this, Ngo relies on evolution. The deepest
guesses are 鈥渕ated鈥� to produce offspring鈥攏ew guesses that are similar to
their 鈥減arents鈥�. These new guesses are then dropped into the ravine to see if
they go down deeper than their parents. So it goes on: the cycle of breeding and
testing continues until the guess evolves that produces a zero error
function.

How does the computer know when it has found the very deepest part of the
ravine? It turns out that there are lots of quite wrong delays that give a zero
error function鈥攂ut none of these stay zero for any length of time. So the
computer decides it has found the best guess when the error function remains
zero for a while. 鈥淚magine standing at the bottom of the Grand Canyon with the
world moving around you. That鈥檚 what it is like at the very bottom of the
mathematical ravine.鈥� It usually takes the computer only a few dozen
generations鈥攏o more than 250鈥攖o find the mathematical sweet spot. So
Ngo鈥檚 computer needs just 3 or 4 seconds before it spits out both Andy鈥檚 and
Barbara鈥檚 voice, crystal clear.

For the moment, Ngo鈥檚 device is designed to separate one voice from
another鈥攊t can鈥檛 easily cope with background noises such as the roar of a
passing bus or the hiss of an air conditioning system. But if these sounds could
also be filtered out, then the potential is huge. Today, the slightest
background noise throws voice recognition programs into confusion. Ngo鈥檚 device
would clean up voice signals before they pass into a voice recognition program.
Whether you鈥檙e on a busy trading floor, a shopping mall or on a bus or train,
your computer would understand your commands. Cocktail parties may never be the
same again.

Warts and all

Badly flawed they may be, but molecular computers will still purr

HERE鈥橲 a riddle. I鈥檓 the face of the future but use 1930s technology. I鈥檓
peppered with defects yet work perfectly. I鈥檓 the size of a refrigerator but
inside I鈥檓 like the smallest of computers. What am I?

The answer is Teramac, an experimental computer like nothing you鈥檝e ever
seen. Made from hundreds of damaged chips, it purrs away deep inside
Hewlett-Packard鈥檚 research centre in Palo Alto. That it works at all is
astonishing. But for its inventors, it has much greater significance: it is the
template for a new generation of molecular computers that will surpass anything
built from silicon.

Ever since Eric Drexler introduced nanotechnology to the masses in his book
Engines of Creation in 1986, there鈥檚 been a widely held view that
computers will one day be built from molecules that behave just like transistors
and wires. These components will be snapped together like bricks from some
fantastic construction kit and, just like chips coming off a production line,
every completed device will be perfect.

But there鈥檚 a big problem with that view. 鈥淎s any practising chemist knows,
there鈥檚 no such thing as a 100 per cent reaction yield,鈥� says Stan Williams,
head of basic research at Hewlett-Packard. 鈥淵ou throw a bunch of chemicals into
a pot and it鈥檚 a completely probabilistic issue as to what you鈥檙e going to get
out. You鈥檙e going to get out 50 per cent of what you want, maybe, and then
you鈥檙e going to get ten other products that you don鈥檛 want.鈥�

So what makes nanotechnologists think they can fashion reliable computers
using a process that is inherently unreliable? This is where Teramac fits in.
Though its hardware is unreliable, its software compensates for the flaws.
Williams and his colleagues hope that, shrunken down 1000 million times to the
molecular scale, Teramac鈥檚 architecture will work reliably, regardless of the
vagaries of chemistry.

Much of their optimism is based on a 鈥渟hape-changing鈥� chip called a field
programmable gate array. Like other chips, an FPGA processes binary signals by
feeding them through a series of logic circuits. But, unlike other chips, an
FPGA鈥檚 logic circuits are not hardwired. Instead, they can be connected in any
order thanks to an array of switches that are controlled by a program, called a
compiler. These simple switches make for a very flexible machine. With the right
compilers, an FPGA can take on the logical shape of other chips鈥攕o one
minute it could be word-processing chip and the next a digital signal
processor.

FPGAs and their extraordinary capabilities are both the model and the heart
of Teramac, as designed by Phil Kuekes and Greg Snider at Hewlett-Packard. More
than 250 FPGAs provide its logic circuits, while 608 more are used just for
their switches, which are arranged in a vast hierarchical network. Williams and
his colleague James Heath of the University of California, Los Angeles, realised
that this was the key concept required to build a reliable electronic circuit by
chemical assembly.

At the lowest level, a group of logic circuits are connected to a series of
nodes via a grid-like structure, called a crossbar, which has a switch at every junction
(see Diagram). This structure, which would be horribly familiar
to a 1930s telephone engineer, provides myriad routes between any of the logic
circuits and any of the nodes. In turn, groups of nodes are connected to a
鈥渉igher鈥� level of nodes via other crossbars. So it goes on through five layers
of hierarchy. In practice, this means there are billions of possible routes from
any one logic circuit to another.

When Snider and Kuekes proposed building Teramac (as a way to test different
computer architectures), they were told that their idea was too expensive. So
they made their machine from both perfect and defective FPGAs. Snider reckoned
that with so many pathways inside Teramac it should be possible to work around
any defects, so long as he could dream up bright enough software. Sure enough,
he wrote a program that maps out defects in the hardware, and compilers that
avoid these defects.

鈥淭he big surprise was how well the thing worked,鈥� says Williams. Even with
all its defects, Teramac still manages as many as 10¹² operations a
second鈥攆aster than 100 workstations. The team has created a number of
different parallel computers on it, including one that translates data from a
magnetic resonance imager into three-dimensional images of the brain.

But for Williams and Heath, the real value of Teramac is as a model for how
to make a chemical computer. Unlike other researchers, they鈥檙e not focusing on
individual molecular transistors and wires. 鈥淎lthough people have come up with
ones and twos of these devices,鈥� says Williams, 鈥渘obody has seriously thought
about how you connect up 10¹⁵ of them. Now we鈥檝e got the architecture. We know
what the overall thing is going to look like.鈥�

Williams and Heath are searching for collections of molecules that will
assemble themselves into the circuits found in Teramac, and behave like them
too. They want to simply throw these collections into a beaker and stir. The
haphazard nature of chemistry will mean that some circuits will not assemble
correctly, but that doesn鈥檛 matter.

With Snider鈥檚 defect-seeking programs and a variety of compilers, Williams
reckons that every molecular chemical computer coming off his production line
will be good for something. One may have so many defects that it could control
only a toaster, but the next one off may turn into a supercomputer. William says
they already have some of their chemical components in hand, but won鈥檛 say more
because the team is in the process of patenting them.

If this all seems a little unlikely, consider a project at the nearby
University of California, Berkeley. Here physicists Marvin Cohen, Alex Zettl and
Steven Louie have produced 鈥渃ube tubes鈥�, structures made by compressing vast
numbers of entangled carbon nanotubes. The team calculated that one type of
molecular flaw in a nanotube turns it into a diode, and researchers elsewhere
have found other transistor-like behaviours. 鈥淲ith 50 atoms we could probably
make a radio,鈥� jokes Cohen.

Like Williams and his colleagues, the Berkeley researchers are looking at
ways to encourage nanotubes to organise themselves into regular structures. But
simply by sticking input and output wires into the randomly arranged tube cubes,
Zettl has already found a variety of potentially useful electronic behaviours.
Perhaps his cube tubes have already formed into tiny computers just waiting for
a variant of Snider鈥檚 trouble-shooting software to make them work. Now there鈥檚 a
thought.

Flash of brilliance

Who needs a hard disc when you鈥檝e got a transparent sugar cube?

HANS COUFAL has a holographic memory. He keeps it in a metal canister in his
office. To the naked eye it looks just like a piece of pinkish glass about the
size of a sugar cube. But shine laser light of just the right wavelength on this
chunk of lithium niobate, and it reveals a complete holographic record of a
television commercial鈥�450 video frames in all, without a pixel out of
place.

The idea of using holograms to store information has been around for some
time (see 鈥淭he trillion bit cube鈥�, New 杏吧原创, 13 August 1994, p
22). But only recently have researchers like Coufal developed the special
materials and technologies needed to make them work. Coufal鈥檚 data crystal is
capable of storing gigabytes of information鈥攁s much as almost 200
CD-ROMs鈥攁nd transferring data at a blazing 125 megabytes per
second鈥攆ast enough to download Shakespeare鈥檚 complete works in a fraction
of a second. Even more amazing, Coufal has cracked the problem of how to search
this vast amount of information almost instantaneously.

Holographic memory is important because the magnetic memories used in
virtually every computer are about to hit a fundamental barrier. The tiny
magnetic crystals that store each bit of data cannot be made much smaller
without data being destroyed by thermal energy from their surroundings. This
physical limit on how densely data can be stored will be reached within the next
few years, so a new technology needs to be found to meet the burgeoning demand
for memory. Holographic storage is one of the leading candidates. 鈥淭his would
mean a completely new industry,鈥� says Coufal, who works at IBM鈥檚 Almaden
Research Center near San Jose.

The holograms inside the crystal are like any other. They are produced by
splitting green laser light into two beams. The first beam passes through a
high-resolution liquid crystal display that imprints the image to be recorded
onto the laser wavefront which then passes into the crystal. The second
beam鈥攖he reference beam鈥攊s shone directly into the crystal where it
interferes with the first beam, creating a complex pattern of light and dark
that fills the cube. Because lithium niobate is photosensitive, the lasers alter
its optical properties and create a permanent record of the interference
pattern. In effect, the image is stored throughout the entire cube.

To read the image, the reference beam is shone into the crystal where it
interacts with the stored interference pattern and generates a perfect replica
of the original image beam. A camcorder records the image, which can then be fed
to a computer for processing.

One of the key challenges that Coufal is working on is to develop a material
that can reliably and repeatedly record, store and read out data. Lithium
niobate doped with iron does the trick but it is expensive. Coufal believes that
polymeric materials hold great promise for the future.

Holograms, of course, have the near-magical ability to record
three-dimensional information. Look at a hologram from a different angle and you
see a different view. But there is no reason for the images seen at each angle
to show the same object鈥攐r that they be conventional images at all.
Instead, Coufal stores a different page of data at each angle. To go from one
page to the next, he rotates the read-out laser by a fraction of a degree.

The 鈥渘onlocality鈥� of the data has exciting consequences. Because each bit of
data is stored throughout the entire volume of the crystal, not in one location,
it is less vulnerable should small faults develop in the crystal. By comparison,
any data stored in a sector of a magnetic disk that becomes corrupt is lost.

But the most amazing thing about Coufal鈥檚 crystal is that the data it
contains can be searched simultaneously. Just as a reference beam projected into
an ordinary hologram generates the image stored inside it projecting that image
back into the hologram generates the reference beam at the angle at which it was
recorded.

This is hugely significant because it works also for partial images or data.
So a sunset image can be found by projecting a rough image of a sunset鈥攕ay
a picture with red blob in the centre鈥攊nto the crystal. This will interact
with the recorded interference patterns to produce reference beams at angles
that correspond to matching images. The best match will be the brightest
reference beam.

There鈥檚 still some way to go before you鈥檒l be able buy a holographic storage
device. But Coufal has made big advances, and he believes that Silicon Valley
has played an important role. The abundance of technical talent, the presence of
small companies with specialised abilities such as growing of lithium niobate
crystals and the entrepreneurial ethos make his work much easier. 鈥淭hat鈥檚 why
Silicon Valley is a unique place,鈥� he says.

The right connections

Treat the Web mathematically and a fantastic order emerges

WHEN you鈥檙e looking for information, the World Wide Web can seem like the
World Wide Jungle. It鈥檚 a chaotic, anarchic place where the guides are dumb
creatures called search engines. Ask for directions and they鈥檒l give hundreds of
suggestions but only a few of real value.

So the hunt is on for more intelligent ways to search the Web. Most attempts
to do this have focused on new ways of analysing or labelling the contents of websites
(see 鈥淎 new dawn鈥�, New 杏吧原创, 30 May, p 34). But computer
scientists at the IBM Almaden Research Center near San Jose are improving on
this with a double-barrelled approach that also takes into account the network
of connections entering and exiting each site. They treat this network as
mathematical entities which sift out the truly authoritative sites from the
irrelevant, irreverent and bogus. Treat these entities with care and they spit
out special solutions which turn out to have extraordinary counterparts in the
real world鈥攖hey represent special interest communities on the Web. It鈥檚 as
if IBM鈥檚 computer scientists have found a way to root out the undiscovered
tribes of the World Wide Jungle.

The search program that the IBM researchers have developed is called Clever.
It starts with the results of a keyword search on a standard search engine such
as Alta Vista. This produces a list of around 200 results, which the researchers
call core websites. The program searches these sites for links to other pages
and adds these pages to its list. Next, the program searches Alta Vista for
pages that point towards the core sites鈥攁 standard feature of this search
engine鈥攁nd adds these to its list too. The result is a list of a few
thousand websites that are core sites, point to core sites or are pointed to by
core sites.

The program then looks at the connections between these sites. Any site that
other sites frequently point to is called an 鈥渁uthority鈥� and receives an
authority score based on the number of pointers. The authority score indicates
how relevant this site is to the original search.

Clever鈥檚 inventor, Jon Kleinberg, now at Cornell University, realised that
any site that points to lots of good authorities is itself a valuable resource.
He called such a site a 鈥渉ub鈥� and gave each hub a score based on the sum of the
authority scores of the sites it points to.

And this is only the first step. Kleinberg assumed that the authorities
linked to by the best hubs would be the best authorities, so his next step was
to recalculate the authority scores to take into account the hub scores. He then
repeated this process many times reasoning that it would give better and better
ratings of the top hubs and authorities.

鈥淲hen Jon came to me with this algorithm, I said this is never going to work,
because it won鈥檛 converge,鈥� says Prabhakar Raghavan, the computer scientist at
IBM who manages the research on Clever. Raghavan was worried that each iteration
would produce a different set of ratings and that it would never be possible to
determine which sites were best. Yet in experiments, the hub and authority
scores always settled down into a stable set of ratings after fewer than 50
iterations. Later versions of Clever have been made more sensitive to a site鈥檚
content as well as its connections.

Others seem to agree. Monika Henzinger at Compaq, the company that owns Alta
Vista, asked human users to rate the top 10 鈥渉ubs鈥� produced by a modified
version of Kleinberg鈥檚 algorithm in terms of their relevance to a particular
search. According to Henzinger, people rated up to 81 per cent of the
suggestions as relevant鈥攗nusually high for any search engine.

When Kleinberg and Raghavan scoured the linear algebra textbooks, they soon
discovered why their method was so successful. The process of iteration they
used is called a linear dynamical system. As Kleinberg observed, these systems
always behave in a predictable way.

In the world of mathematics, each list of hub scores and each list of
authority scores is a vector, and each cycle of revising the hub scores and then
revising the authority scores is called a linear transformation. What Kleinberg
had stumbled on was a method of finding vectors that are unchanged by a linear
transformation. These special vectors are called eigenvectors, and for a
mathematician, finding eigenvectors is a bit like finding the solutions to
equations.

Raghavan reasoned that if the Web can be thought of as a mathematical entity,
then it can be manipulated like one. The eigenvectors in Kleinberg鈥檚 algorithm
represent one community鈥檚 consensus on the authorities and hubs it considers
most important. But other communities are likely to have a different consensus.
The community that 鈥渨ins鈥� in Kleinberg鈥檚 algorithm is simply the one that has
the most hyperlinks and sites鈥攖he community that is most 鈥渨ired鈥�. But the
mathematics of linear transformations allows Raghavan to find the eigenvectors
for other communities too, if they are there.

He and his colleagues set about searching for these communities using more
complex and computationally intensive mathematical techniques. It turns out
there are thousands of communities of interlinked Web users, possibly tens of
thousands. These are the undiscovered tribes hidden in the World Wide
Jungle.

Raghavan gives the example of one query he carried out using the term
鈥渁bortion鈥�. The eigenvector produced by Kleinberg鈥檚 algorithm turns out to be a
community of people in favour of allowing abortion. But Raghavan found another
eigenvector dominated by sites wishing to ban it. Each community has a dense
internal network of links but rarely link to each other.

鈥淚鈥檓 always amazed by what I find,鈥� says Raghavan. One of his favourite
discoveries is the tribe of 鈥渇un sumo wrestlers鈥濃�攑eople who rent plastic
outfits and push each other around like sumo wrestlers. 鈥淭here are all sorts of
communities out there on the Web whose existence we don鈥檛 know of.鈥� Now the
search has begun.

Protein paparazzi

For perfect pictures of giant molecules, just tickle those atoms

THERE鈥橲 a little secret that molecular biologists like to keep to themselves.
They spend years studying big, complex molecules鈥攖he stuff of life. They
search for the tissues in which these molecules are produced and study the role
they play in organisms. But ask molecular biologists what these structures look
like and they will stare at the floor, shuffle their feet and change the
subject. The awful truth is that mapping the three-dimensional shape of gigantic
biological molecules is more difficult than scientists would like to admit.

So a technique that could take snapshots of a single molecule in a more or
less its normal environment would be valuable to say the least. And that鈥檚
exactly what Dan Rugar and his colleagues are developing at IBM鈥檚 Almaden
Research Center near San Jos茅. Rugar鈥檚 approach combines magnetic
resonance imaging (MRI), which already gives stunning pictures of organs inside
the body, with those of atomic force microscopy, the technique that produces
pictures of surfaces on the atomic scale. If he can perfect this approach, Rugar
and his team will have a microscope capable not only of resolving individual
molecules, but of mapping their composition and 3D structure with unheard of
precision.

Today, most biological imagery is done by creating very pure crystals of the
target molecules and recording the way X-rays scatter off them. Working
backwards from this pattern can reveal the structure. Unfortunately, the shape
of many biological molecules depends on their environment鈥攖he solvent
they鈥檙e in, for example, or the other chemicals attached to them鈥攁nd in
some of these states it can be very difficult to crystallise them. Another
option is to make very pure solutions of the molecules and analyse them with
traditional magnetic resonance. But this needs billions of molecules to work,
and it鈥檚 not always possible to make plentiful supplies of the target
molecules.

Rugar鈥檚 approach should overcome some of these drawbacks. It is designed to
work with single molecules, so none of the special techniques of purification
and crystallisation should be needed. Called magnetic resonance force
microscopy, it uses a minuscule cantilevered probe that resembles a springboard
120 micrometres long and only 170 nanometres thick. Like standard MRI, it relies
on a quantum mechanical property called spin, which makes atomic nuclei behave
like tiny magnets.

The probe has a tiny magnet at its end that causes nearby atomic nuclei to
align themselves either with the field or against it. There is a slight energy
difference between these two spin states and by adding energy, in the form of
radio waves, the nucleus can be made to flip back and forth between them. As it
oscillates, it attracts and repels the magnet on the probe, making the
cantilever vibrate.

How can this idea by used to map molecules? The key idea is that the energy
difference between the spin states depends on the strength of the magnetic field
created by the probe鈥檚 magnet. Because this drops off rapidly, only nuclei in a
very thin slice of the sample have an energy difference that matches the energy
of the incoming radio waves. Any nuclei in a stronger or weaker part of the
magnetic field are not affected.

In practice, the slice is shaped like a thin hemispherical shell centred on
the magnetic tip of the cantilever. By measuring the frequency that causes the
cantilever to resonate, and by physically moving the probe so that the slice
moves through the sample molecule, Rugar can build a picture of all the nuclei
present and the way they are connected. It is only a matter of image procesing
to calculate the 3D structure of the molecule.

At least, that鈥檚 the theory. The problem is that the forces involved are
tiny. 鈥淭hink of two electrons about the same distant apart as the cantilever
would be from the sample,鈥� says Rugar. 鈥淭he electrostatic force between them
would be about a million times bigger than the magnetic force we want to
measure.鈥� These tiny forces are measured in 鈥渁ttonewtons鈥�, 10^-18 newtons.
鈥淎ttonewtons are so small that we have to be very careful we鈥檙e not swamped by
other forces.鈥�

Despite the enormous problems with working on such a tiny scale, Rugar is
making steady progress. Last year, he and his team announced the first
attonewton measurements, an important step towards proving that the concept is
feasible. His next goal is to measure the spin of a single electron, which
involves forces a few hundred times stronger than those of single nuclei.

Single unpaired electrons are created when semiconductors are 鈥渄oped鈥� with
impurities, so if Rugar can measure their spin, this technique could be used to
spot dopant atoms. This potential spin-off could be very useful to chip makers.
鈥淧retty soon there will be countable numbers of dopant atoms in transistor
gates,鈥� says Rugar. This is one of the reasons why IBM is funding the work.

After spotting single electrons, Rugar hopes to move on to mapping molecules.
鈥淏ut it鈥檚 still a long way off,鈥� he admits. Molecular biologists can hardly
wait.