Orthogonal Frequency Division Multiplexing (OFDM) is a multi-carrier modulation technique that employs frequency diversity to overcome the noise inherent in typical radio channels. The principal barrier to the widespread acceptance of OFDM has been the high power of uncoded OFDM transmissions: the peak power can be as much as n times the mean power, where n is the number of carriers. This results in inefficient amplifier usage and undesirable spectral characteristics.

It is known that using a codeword taken from a Golay complementary set of size k to modulate the carriers results in an OFDM signal with peak-to-mean power ratio at most k. But to obtain a high code rate, a large number of such OFDM codewords are needed. Recently, J.A. Davis and J. Jedwab have shown a striking connection between Golay complementary pairs of sequences (k = 2) and Reed-Muller codes. They exhibited m!/2 cosets of the binary code RM(1,m) lying in RM(2,m) which consist entirely of binary Golay complementary pairs. These cosets yield m!2^m binary OFDM codewords for n = 2^m carriers which have a peak-to-mean power ratio of only 2 and which enjoy (as a consequence of the code structure) good error-correcting capability and efficient encoding and decoding. They also generalised this result to 2^h-ary pairs, introducing along the way generalisations of the binary Reed-Muller code that are closely related to the now famous quaternary codes of Hammons et al.

We show how these results fit into a larger theoretical picture. We prove that any second order coset of an appropriate q-ary generalisation of the first order Reed-Muller code can be partitioned into Golay complementary sets of a certain size. It turns out that the set size depends on a property of the graph associated with the quadratic form defining the coset; the previous results of Davis and Jedwab are then easy corollaries. As well as shedding new light on existing constructions for Golay pairs, the proof of this result answers a long-standing open problem of Tseng and Liu concerning the explicit construction of Golay complementary sets. It also leads to a number of fascinating open questions concerning Golay complementary sets and Reed-Muller codes.

Back to Workshop Schedule