09 April 2012

An Analysis of the CSIRO WLAN Patent

Patent front pageIn all of the debate over the past week around the CSIRO wireless LAN patent, there has been very little information – and much misinformation – about what the patent actually covers.

Various vague assertions have been bandied about, such as that the patent describes nothing much more than a few techniques that were well-known at the time (the priority date of the patent is 27 November 1992).

And some commenters on the various articles have complained that none of the authors have actually gone into any technical detail about the patent.

There is a good reason for this – it is not simple to explain in detail the technical and legal scope of a patent.  While patent attorneys actually do this all the time, in order to advise clients on various matters, we tend to charge significant sums for the service, because it takes great expertise and many hours to do it right.

The part of a patent that actually defines the extent of the monopoly is the section at the end containing a series of numbered statements, called ‘claims’.  If you do something which is actually within the entirety of the language of at least one claim, then you infringe the patent.  However, if you do something which is described in the patent specification, but which is not the entire subject matter of a claim, then you do not infringe.  Ideally, this would all be very clear-cut.  In practice, with the best will (and the best patent drafting) in the world, language is an imprecise and sometimes ambiguous tool!

Most patents describe many things that are not new.  However, granted patents (hopefully) describe and claim some combination of things which is new and inventive.

So in this article we will – at no charge, with no obligation, and with the strong disclaimer that this is not legal advice and cannot be relied upon for any purpose – take a look at what the CSIRO WLAN patent is actually all about.

The Patent

The CSIRO patent is no. 5,487,069.  However, this original published version no longer represents the current state of the patent.  Following re-examination initiated in 2008 by Intel (control number 90/010,367), the patent was amended to delete some claims, amend some others, and add about 80 new ones!  We have obtained a copy of the re-examination certificate, and made it available via Google docs (PDF, 1.25 MB).  The certificate shows the claim amendments, along with all of the prior art raised in the re-examination – an eight-page listing!

The more recent re-examinations, initiated in 2010, are complete, although a further re-examination certificate is yet to issue.  Only minor additional amendments have resulted from these proceedings.

The patent, as it currently stands at the conclusion of all re-examination proceedings, contains about 140 claims.  Most of these are directed to minor variations and specific features of the particular implementation which is described in detail within the specification.

But to understand the maximum extent of CSIRO’s patent rights, it is sufficient to look only at one of the broadest claims of the patent.  We have chosen claim 68, which is a method claim defining a procedure for transmitting data in a wireless LAN which is implemented within devices employing the invention:

68. A method for transmitting data in a confined multipath transmission environment of radio frequencies, said data being provided by an input data channel coupled to transmission signal processing means in turn coupled to antenna means, said method comprising the steps of:
  1. applying data reliability enhancement to said data;
  2. interleaving, by means for interleaving, blocks of said enhanced data;
  3. modulating said data, by modulation means of said transmission signal processing means, into a plurality of sub-channels comprised of a sequence of data symbols such that the period of a sub-channel symbol is longer than a predetermined period representative of significant ones of non-direct transmission paths; and
  4. transmitting, by said antenna means, said sub-channel symbols.
The underlined portion highlights the only amendment which has been made to this claim in the course of the various re-examinations to which the patent has been subjected.  Theoretically, this amendment could have an impact on the scope of the claim, although for our purposes here we can assume that it actually makes little difference in practical terms.

Preamble

The opening portion of the claim is known as the ‘preamble’.  It does not usually define anything new and inventive, but rather sets the context for the combination of features which actually constitute the claimed invention.

Here, the preamble tells us that the claim is going to define a ‘method’ (i.e. a sequence of steps), which are useful for transmitting information via radio waves in a confined space.  It further informs us that, in practice, the information will arrive in the form of some ‘input data’, which will be processed by a signal processor (electronic hardware and/or software, as the term is normally understood) and then transmitted via an antenna.

None of this is new in itself.  What is said to be new is the particular signal processing steps employed.

‘…confined multipath transmission environment…’

Figure 1 of the patent illustrates what is meant by a ‘confined multipath transmission environment’.

Multipath Environment

The drawing shows a room (1) in which the box (2) represents an item of furniture.  The circles (3) and (4) represent a transmitter and receiver.  The solid arrow is the direct path from transmitter to receiver, while the dotted lines represent possible indirect paths resulting from reflections of the radio waves from walls, furniture, and other objects.

The environment is generally dynamic, because radio waves will be reflected, diffused and/or absorbed by temporary and moving objects, such as people and their belongings.

It is easy to imagine how these reflections result in various copies of the transmitted signals (‘echoes’) arriving at the receiver at different times.  Information arriving via the direct path will become confused with delayed copies of earlier-transmitted information.  However, this is a vastly oversimplified, and incomplete, picture of the damage done by multipath interference.

Regardless of the information content, delayed copies of transmitted radio waves interfere with one another to cause what is known as frequency-selective fading.  Particular delays correspond with interference at particular frequencies, which may significantly attenuate the receive signals at those frequencies.  Waves have ‘peaks’ and ‘troughs’, and in a worst-case scenario, a delayed ‘trough’ arrives at the receiver at the same time as a direct ‘peak’, and the two cancel each other out completely.

Figure 3 of the patent shows a ‘channel frequency response’ which illustrates just how severe this problem can be.

Channel frequency response

Ideally, the jagged line above would be dead flat – all frequencies arriving at the receiver with the same peak power.  However it is far from flat.  The dB scale on the vertical axis is logarithmic: the difference between the strongest and weakest signals is not ‘about 30’, it is a factor of over 1000!  The dotted line shows how things have changed at a slightly later time.

The patented CSIRO WLAN solves the multipath problem by combining three techniques, in an inter-related fashion.  It is easiest to explain these in a different order from that in which they are applied, because it is then possible to see how each part of the solution in turn creates a need for the next part.

Multi-channel modulation

An aside: Orthogonal Frequency Division Multiplexing (OFDM)

Many of the criticisms of the CSIRO patent have contended that it just claims ‘OFDM’, which was well-known at the time. OFDM, for those not in the know, is a clever way of generating multiple channels which are very closely spaced (in fact, they overlap), while still being possible to separate them at the receiver.

Because OFDM makes very efficient use of radio spectrum, it is clearly the best choice for a multi-channel modulation scheme. It is, in fact, the method described in detail within the patent specification.

But OFDM, as critics have pointed out, was a known technique. CSIRO’s invention was not the use of OFDM per se, but rather the choice of channel number and symbol length to overcome the multipath problem in the typical WLAN environment.

CSIRO's broadest claims are not limited to OFDM, and cover any multi-channel transmission technique. Limiting to OFDM would make it too easy for somebody to bypass the patent by using a slightly less-efficient multi-channel modulation scheme. The key to the invention is how many channels, and what symbol length, are used.
The third step in the claimed method is:
  1. modulating said data, by modulation means of said transmission signal processing means, into a plurality of sub-channels comprised of a sequence of data symbols such that the period of a sub-channel symbol is longer than a predetermined period representative of significant ones of non-direct transmission paths.
If you use one channel to transmit data at, say, 50 Mb/s, then each bit requires a transmission period of 1/50,000,000 seconds (20 nanoseconds).  In that time, light (or radio waves) travels around six metres, i.e. far less than the dimensions of the spaces in which WiFi is commonly used.  So the ‘delayed copy’ problem is extremely severe.

You can be a little clever, and transmit ‘symbols’ representing multiple bits, so that the symbol periods are longer than an individual bit period, but such symbols are more susceptible to noise, and in practice you cannot reduce the problem by more than a factor of about 4.

Far better is to transmit many channels in parallel, each using a slightly different frequency.  Say you use 12 channels, and you modulate each channel with symbols encoding two bits, your symbol rate on each channel is now only 2.08 Msymbols/s.  Light travels 144 metres in the corresponding time period, and in most spaces echoes which have travelled this far are not a problem.

So this is what the above element of the claim tells you to do: divide the signal up into multiple ‘sub-channels’ with parameters chosen such that the period of each transmitted symbol on each sub-channel is greater than the time delay corresponding with any significant echoes.  This way, adjacent symbols no longer interfere with each other.

Error Correction

Multi-channel modulation solves the ‘echo’ problem, but then some of the individual sub-channels will suffer horribly from the frequency-selective fading shown in the graph above, while others will be unaffected.  Some data loss and errors are inevitable.

The solution to this is to include some redundancy in the transmitted signal.  This means adding bits to the transmitted data which can be used to detect and correct certain kinds of errors.

The relevant step in the claim is:
  1. applying data reliability enhancement to said data.
This does not specify exactly how this should be done.  There are many choices which might work, and limiting the claim to one in particular would make it far too easy to bypass the patent.  The specific method described in most detail in the specification is known as ‘Rate 1/2 Trellis Coded Modulation (TCM)’.  ‘Rate 1/2’ means that for every information bit sent, one additional bit of redundant coding information is sent.

Interestingly, TCM was invented by IBM scientist Gottfried Ungerboeck, who described it in a conference paper in 1976.  While it did not achieve a great deal of recognition at the time, it became prominent in the 1980s, and ultimately enabled the jump in dial-up speeds from 9.6 kbit/s to over 30 kbit/s.  Even simple Trellis Coding schemes have the power to reduce the occurrence of uncorrectable errors by a factor of more than 1000!

Interleaving

The fading behaviour of the channel in a confined environment creates a further problem for most error correction schemes: the frequency channels with the worst performance tend to group together (you can see this in the above graph).  If you simply modulate and transmit the sub-channels with bits in the order they come out of the encoder, any errors are likely to affect adjacent groups of symbols.  A bunch of errors in a group of consecutive bits or symbols is commonly known as a ‘burst’.

Bursts of errors are quite common in all telecommunications channels.  Errors are most likely to occur if there happens to be a ‘spike’ in the random background noise, and such spikes typically affect multiple bits.  So most error coding schemes are designed to be reasonably burst-tolerant.  Indeed, a commonly quoted characteristic of any error coding scheme is the maximum length burst error it is able to correct.

So things would probably be fine if we were only concerned about spikes in background noise over time.  But in the scheme we are building here, errors are going to occur amongst groups of symbols because of fading in adjacent frequency channels.

The CSIRO solution to this problem is interleaving, i.e. the step of:
  1. interleaving, by means for interleaving, blocks of said enhanced data
The basic idea is to ‘shuffle’ the symbols amongst the sub-channels (like a deck of cards), so that consecutive symbols are no longer located on adjacent sub-channels.  As always, there are ‘better’ and ‘worse’ ways to perform this step.  The patent specification describes the process this way:

Link data interleaving schemes [distribute] the encoded data between the carriers in such a way that the correlation in error probability of those carriers associated with any given element of uncoded input data is minimised. On average, this corresponds to maximising the minimum frequency spacing between those carriers.

For example, with a 5-bit constraint length, half rate trellis coded QPSK modulation on the carriers of a 12 carrier ensemble, a suitable interleaving scheme is

Carrier number (1-12) modulated by successive encoder output di-bits:
1, 3, 5, 7, 9, 11, 2, 4, 6, 8, 10, 12, 1, 3, . . . etc.

Putting it all together

The invention – the actual innovation on which CSIRO holds a patent monopoly – is what is claimed.  No more, no less.  It is the particular combination of processing steps described above, followed by actually transmitting the resulting signal via an antenna.

There are other claims covering transmitters, receivers, transceivers and wireless LANs.  But all of these claims incorporate versions of this same combination of features.

CSIRO does not own ‘WiFi’, nor does it own, or claim to own, multi-frequency modulation, OFDM, the Fast Fourier Transform, forward error correction, Trellis Coded Modulation, or interleaving.

As explained above, the CSIRO WLAN patent claims define particular combinations of these techniques which solve the specific problem of making a wireless LAN work in a confined space with potentially extreme multipath propagation problems.  This problem had not been solved before CSIRO’s scientists did it, and the reason it forms the basis for the 802.11a/g WiFi standards is because no better solution was put forward to the committee.

Was CSIRO’s claimed combination ‘obvious’ on 27 November 1992 (the priority date of the WLAN patent)?  Well, unless you were the person skilled in the relevant art on that date, your opinion on this question is completely irrelevant to the patent law.  Many things are obvious with the benefit of hindsight.

However, the original examiner at the USPTO did not think it obvious.  And in re-examination the claim discussed above was upheld, despite having a selection of prior art references thrown at it, which was so extensive required eight pages of the re-examination certificate to list them all!

So the legal answer to the questions, as matters stand, is no – CSIRO’s WLAN patent claims are not obvious.

2 comments:

tim said...

Very clear, helpful and persuasive analysis - particularly for electronic ignoramuses like me!

Patentology (Mark Summerfield) said...

Thanks for your comment, Tim.  I am glad you found the article useful!

Post a Comment