(12) INTERNATIONAL APPLICATION PUBLISHED UNDER THE PATENT COOPERATION TREATY (PCT)
`
`(19) World Intellectual Property Organization
`International Bureau
`
`1111111111111111 IIIIII 111111111111111111111111111111111111111111111111111 IIII IIII IIII
`
`(43) International Publication Date
`12 September 2003 (12.09.2003)
`
`PCT
`
`(10) International Publication Number
`WO 03/075500 A2
`
`(51) International Patent Classification 7:
`
`H04L
`
`(21) International Application Number:
`
`PCT/IL03/00166
`
`(22) International Filing Date:
`
`4 March 2003 (04.03.2003)
`
`(25) Filing Language:
`
`(26) Publication Language:
`
`English
`
`English
`
`(30) Priority Data:
`60/362,299
`
`7 March 2002 (07.03.2002) US
`
`(71) Applicant (for all designated States except US): ALVAR(cid:173)
`ION LTD. [IL/IL]; 21A Habarzel St., P.O.Box 13139,
`61131 Tel Aviv (IL).
`
`(71) Applicants and
`(72) Inventors: CHAYAT, Naftali [IL/IL]; 18/8 Hameyasdim
`St., 4420 Kfar Sava (IL). KAITZ, Tai [IL/IL]; 58 Brener
`St., 55201 Kiryat Ono (IL).
`
`(81) Designated States (national): AE, AG, AL, AM, AT, AU,
`AZ, BA, BB, BG, BR, BY, BZ, CA, CH, CN, CO, CR, CU,
`CZ, DE, DK, DM, DZ, EC, EE, ES, FI, GB, GD, GE, GH,
`GM, HR, HU, ID, IL, IN, IS, JP, KE, KG, KP, KR, KZ, LC,
`LK, LR, LS, LT, LU, LV, MA, MD, MG, MK, MN, MW,
`MX, MZ, NO, NZ, OM, PH, PL, PT, RO, RU, SC, SD, SE,
`SG, SK, SL, TJ, TM, TN, TR, TT, TZ, UA, UG, US, UZ,
`VC, VN, YU, ZA, ZM, ZW.
`
`(84) Designated States (regional): ARIPO patent (GH, GM,
`KE, LS, MW, MZ, SD, SL, SZ, TZ, UG, ZM, ZW),
`Eurasian patent (AM, AZ, BY, KG, KZ, MD, RU, TJ, TM),
`European patent (AT, BE, BG, CH, CY, CZ, DE, DK, EE,
`ES, FI, FR, GB, GR, HU, IE, IT, LU, MC, NL, PT, SE, SI,
`SK, TR), OAPI patent (BF, BJ, CF, CG, CI, CM, GA, GN,
`GQ, GW, ML, MR, NE, SN, TD, TG).
`
`Published:
`without international search report and to be republished
`upon receipt of that report
`
`(74) Agent: NAOMI ASSIA LAW OFFICES; 32 Habarzel
`St., Ramat Hachyal, 69710 Tel Aviv (IL).
`
`For two-letter codes and other abbreviations, refer to the "Guid(cid:173)
`ance Notes on Codes and Abbreviations" appearing at the begin(cid:173)
`ning of each regular issue of the PCT Gazette.
`
`iiiiiiii
`
`-iiiiiiii
`iiiiiiii -iiiiiiii --!!!!!!!!
`
`== -iiiiiiii
`iiiiiiii ----
`
`O ________________________________________ _
`~ (54) Title: HIERARCHICAL PREAMBLE CONSTRUCTIONS FOR OFDMA BASED ON COMPLEMENTARY SEQUENCES
`ln
`~ (57) Abstract: A method of implementing OFDMA systems with enhanced preamble properties is presented. The transmit pow(cid:173)
`--.. eris boosted during a preamble transmission, by utilizing preambles with a low Peak-to-Average Power Ratio (PAPR) property, as
`~ opposed to higher PAPR during the data portion of the transmission. Further, sets of preambles satisfying good PAPR properties in
`OFDMA systems are presented. The preambles satisfy a low Peak-to-Average Power Ratio (PAPR) property for numerous subsets of
`0 the usable subcarrier set. A method for generating a hierarchical set of preamble for OFDMA communication systems is described.
`> The method hinges on the good PAPR properties of Golay's complementary sequences, and on hierarchical construction methods
`
`;;, of larger complementary sequences out of smaller ones.
`
`VWGoA EX1013
`U.S. Patent No. 8,467,366
`
`

`

`WO 03/075500
`
`PCT/IL0J/00166
`
`1
`
`HIERARCHICAL PREAMBLE CONSTRUCTIONS FOR OFDMA
`BASED ON COMPLEMENTARY SEQUENCES
`
`5
`
`FIELD OF THE INVENTION
`
`The present invention relates to Orthogonal Frequency Division Multiple
`
`Access (OFDMA) systems, and in particular to construction of preambles for
`transmission of message bursts.
`
`10
`
`BACKGROUND OF THE INVENTION
`
`15
`
`The Orthogonal Frequency Division Multiple Access (OFDMA) systems are
`similar to Orthogonal Frequency Division Multiplex (OFDM) systems in the sense that
`
`the information is spread over multiple subcarriers in the frequency domain and is
`
`transmitted after converting the information to the time domain using a Fourier
`transform. The amount of subcarriers available to a system is determined by a ratio
`
`of the assigned frequency channel to the frequency spacing between the subcarriers.
`The main difference between OFDM and OFDMA is that with OFDM a single
`transmitter uses a whole range of subcarriers to transmit its information, while in
`OFDMA different transmitters are assigned disjoint sets of subcarriers, and each user
`
`sends his information on the subcarriers assigned to him.
`
`20
`
`25
`
`The amount of subcarriers assigned to each transmitter may vary according
`to the traffic demands of each user in a multiple access system. The assignment is
`usually performed in groups of subcarriers, denoted as subchannels. The OFDMA
`
`idea became popular recently in the context of wireless access systems. There are
`
`30
`
`several variants of division of the subcarriers into subchannels, starting from irregular
`methods such as in IEEE802.16a [4] and in DVB-RCT [5], through contiguous
`
`clusters of subcarriers [3] and concluding with regularly interleaved sets.
`
`In burst communication systems each transmission typically starts with a
`
`35
`
`preamble, which is used for synchronization and channel estimation. Usually such
`preamble is structured as one or two OFDM symbols with predefined values
`
`

`

`WO 03/075500
`
`PCT/IL03/00166
`
`2
`
`modulating each of the subcarriers. The set of predefined values is chosen to satisfy
`
`several criteria. One is that all the values have the same modulus, to ease the
`
`channel estimation. Only the values corresponding to the assigned subcarriers are
`non-zero. Another criterion is that the preamble time domain waveform has a low
`
`5
`
`Peak-to-Average Power Ratio (PAPR) property, to avoid excessive distortion in the
`
`power amplifier.
`
`Typically OFDM systems produce high PAPR waveforms, since at each time
`
`instant numerous data-dependent contributions add up to a Gaussian-like waveform.
`
`10 As a result, the OFDM transmitters utilize their power amplifiers at a small fraction of
`their peak output, typically at 8-11 dB backoff. By using as a preamble, a carefully
`crafted set of subcarrier modulation values, the PAPR of the preamble can be kept at
`
`about 3 dB, significantly less than the values typical to data. This property is
`beneficial in that during the channel estimation phase the signal experiences smaller
`
`15
`
`distortion, resulting in a more accurate estimate.
`
`The preambles in OFDMA systems are designed do excite only the
`subcarriers that are assigned to the user. The OFDMA adds a new twist to the
`problem, since not only a single preamble with good PAPR properties needs to be
`designed, but rather a family of preambles for each subset of subcarriers that can be
`allocated to a single transmitter.
`
`PRIOR ART
`
`20
`
`25
`
`There are several recent works searching for families of waveforms with low
`
`PAPR. One set of waveforms is based on Golay's complementary sequences, which
`
`have the property that their Fourier transform has a PAPR of at most 2, which is
`
`equivalent to 3 dB. Van Nee has shown [1] how to use sets of complementary
`
`30
`
`sequences in conjunction with OFDM modulation for conveying information with low
`
`PAPR waveforms. This invention was implemented in the "Magic Wand" wireless
`
`ATM demonstrator [2].
`
`In this work the aim was to achieve low PAPR property for
`
`the data portion of the signal rather than for the preamble. Similarly, Awater and van
`Nee, in US patent 6,005,840, disclose a!J OFDM transmitter system that uses
`complementary codes to reduce the power-to-average power (PAP) ratio of the
`
`35
`
`transmitted signal. Sets of complementary sequences are also used to convey
`
`

`

`WO 03/075500
`
`PCT/IL03/00166
`
`3
`
`information in time domain, which is not OFDM, in a popular 802.11 b Wireless LAN
`
`standard, where a dual property is used. The low PAPR of the Fourier transform in
`
`frequency domain results in better immunity to interference and to multipath.
`
`5
`
`In all the above applications the goal is to convey data by selecting one out of
`
`several sequences, all the sequences having the same length. By contrast, in
`
`OFDMA systems, a set of sequences of different sizes
`
`is needed, each
`
`corresponding to a possible allocation of a different subcarrier set to each user.
`
`10
`
`REFERENCES
`
`[1] R.D.J. van Nee, "OFDM codes for peak-to-average power reduction and error
`
`correction", Global Telecommunications Conference, London, Nov.1996.
`
`15
`
`[2] Awater, G.A.; van Nee, D.J.R., "Implementation of the Magic WAND wireless A TM
`
`modem", ICC '99.
`
`[3] IEEE 802.11 b standard, High Rate Direct Sequence PHY extension for Wireless
`
`LANs.
`
`[4] IEEE 802.16a, "Air Interface for Fixed Broadband Wireless Access Systems -
`20 Medium Access Control Modifications and Additional Physical Layer Specifications
`for 2-11 GHz", Draft 7, Nov. 2002
`
`[5] ETSI EN301 958, "Digital Video Broadcasting (DVB); Interaction channel for
`
`Digital Terrestrial Television (RCT) incorporating Multiple Access OFDM", Aug. 2001
`
`[6] Y. Li, N. Sollenberger, "Clustered OFDM With Channel Estimation for High Rate
`25 Wireless Data", IEEE Trans. on Comm., Dec. 2001, pp. 2071-2076
`
`[7] M.J.E. Golay, Complementary Series, IRE Trans. On Information Th., Apr 1961,
`
`pp. 82-87
`
`[8] R. Frank, "Polyphase Complementary Codes", IEEE Trans. on Information Th.,
`
`Nov. 1980,pp.641-647
`
`30
`
`[9] A. Gavish and A. Lempe!, "On Ternary Complementary Sequences", IEEE Trans.
`
`on Information Th., Mar. 1994, pp. 522-526.
`
`

`

`WO 03/075500
`
`PCT/IL03/00166
`
`4
`
`SUMMARY OF THE INVENTION
`
`Therefore, it is a principal object of the present invention to create a
`
`5
`
`hierarchical set of preambles of different size
`
`in order to serve as
`
`low(cid:173)
`
`Peak-to-A verage Power Ratio (PAPR) preambles for an Orthogonal Frequency
`
`Division Multiple Access (OFDMA) system.
`
`A method is disclosed of implementing OFDMA systems with enhanced
`
`10
`
`preamble properties. The transmit power is boosted during a preamble transmission,
`
`by utilizing preambles with a low Peak-to-Average Power Ratio (PAPR) property, as
`
`opposed to higher PAPR during the data portion of the transmission. Further, sets
`
`of preambles satisfying good PAPR properties in OFDMA systems are presented.
`
`The preambles satisfy a low Peak-to-Average Power Ratio (PAPR) property for
`numerous subsets of the usable subcarrier set. A method for generating a
`hierarchical set of preambles for OFDMA communication systems is described. The
`method hinges on the good PAPR properties of Golay's complementary sequences,
`
`and on hierarchical construction methods of larger complementary sequences out of
`smaller ones.
`
`15
`
`20
`
`BRIEF DESCRIPTION OF THE DRAWINGS
`
`These and further features and advantages of the invention will become more
`
`25
`
`clearly understood in the light of the ensuing description of a preferred embodiment
`
`thereof, given by way of example only, with reference to the accompanying drawings,
`wherein:
`
`Fig. 1 is a flow chart illustrating a method of constructing a sequence of values to be
`
`30
`
`used for modulating the subcarriers of a preamble in an OFDMA system, constructed
`
`in accordance with the principles of the present invention.
`
`Figs. 2a and 2b are illustrations of time domain effect, incurred without and with
`boosting of a low-PAPR preamble, respectively., constructed in accordance with the
`
`35
`
`principles of the present invention.
`
`

`

`WO 03/075500
`
`PCT/IL03/00166
`
`5
`
`5
`
`DETAILED DESCRIPTION OF THE PREFERRED EMBODIMENTS
`
`The first element of the invention relates to the utilization of the low-PAPR
`
`preamble waveforms in an Orthogonal Frequency Division Multiple (OFDM) system,
`
`10
`
`not only for the purpose of reducing the power amplifier distortion, but rather
`
`extracting higher average power during the preamble. According to the present
`
`invention it is suggested that the average power of the preamble is boosted relative
`to the data region in order to improve, for example, the channel estimation accuracy
`
`and burst detection probability. The benefits of this technique are independent of the
`15 method used to construct the low-PAPR sequence, whether it is generated by
`mathematical construction or it is a result of computer search.
`
`Fig. 1 is a flow chart illustrating a method of constructing a sequence of
`values to be used for modulating the subcarriers of a preamble in an OFDMA system
`100, constructed in accordance with the principles of the present invention. The
`purpose is to have low PAPR both for the whole sequence and for numerous subsets
`
`20
`
`of the sequence based a series of steps. The first step is to select the basic pair of
`
`complementary sequences 110. The next step is to interleave the sequences with
`zeroes according to the desired spread of subcarriers over frequency in a basic
`
`25
`
`subcarrier group 120. This is followed by repeating the step of creating new
`
`complementary sequence pairs with twice the number of nonzero elements 130, by
`
`applying the steps of shifting 140 and adding-subtracting 150 until a sequence is
`created containing all the desired nonzero subcarriers at the desired locations 160.
`
`30
`
`Figs. 2a and 2b are illustrations of time domain effect, incurred without and
`
`with boosting of a low-PAPR preamble, respectively, constructed in accordance with
`the principles of the present invention. Fig. 2a shows the linear region of a power
`amplifier 231 without preamble boosting 241 . By contrast, Fig. 2b shows the linear
`region of a power amplifier 232 with preamble boosting 242. The data regions 250
`
`35
`
`are seen to be the same for both.
`
`

`

`WO 03/075500
`
`PCT/IL03/00166
`
`6
`
`The second element of the invention is related
`
`to
`
`implementation of
`
`constructed preamble families in OFDM and OFDMA systems, wherein all members
`
`of the family achieve the low-PAPR property by the virtue of being complementary
`
`sequences.
`
`According to the preferred embodiment of the present invention, the method
`
`of generating sets of OFDMA preambles utilizes the methods for hierarchical
`
`construction of long complementary sequences from short seed sequences,
`
`developed initially by Golay in his seminal paper [7]. Golay initially dealt with binary
`
`sequences; his work was generalized to polyphase, and in particular quadriphase,
`sequences by R. Frank [8] and to three valued (-1, 0 and +1) sequences by Gavish
`and Lempe! [9].
`The present invention utilizes and further generalizes the
`
`abovementioned works
`
`towards construction of hierarchical sets of OFDMA
`
`preambles.
`
`5
`
`10
`
`15
`
`Complex valued, discrete time, finite length sequences A and B are called a
`
`complementary pair, if their autocorrelations add up to a delta-function. An example
`
`of such a pair is:
`
`A= (+1, +1, +1, -1); B = (+1, +1, -1, +1)
`
`20 Corr(A, A)= (-1, 0, 1, 4, 1, 0, -1);
`Corr(B, B) = ( 1, 0, -1, 4, -1, 0, 1)
`Corr(A, A) + Corr(B, B) = (0,0,0, 8, 0,0,0) = delta function.
`If both sequences have same the energy, then their Fourier transforms exhibit the
`
`property proved in the appendix, that its PAPR is at most 2, which is equivalent to 3
`
`25
`
`dB.
`
`The following
`
`is an overview of several properties of complementary
`
`sequences and several construction methods of longer sequences from shorter ones:
`
`30
`
`1) If A and B are a complementary pair, then so are A and B, each interleaved with
`zeros. For example, if:
`
`A= (+1, +1, +1, -1)
`B = (+1, +1, -1, +1)
`are a complementary pair, so are:
`35 A'= (+1, 0, +1, 0, +1, 0, -1)
`B' = (+1, 0, +1, 0, -1, 0, +1)
`
`

`

`WO 03/075500
`
`and also the pair:
`
`7
`
`PCT/IL03/00166
`
`A"= (+1, 0, 0, 0, +1, 0, 0, 0, +1, 0, 0, 0, -1)
`
`B" = (+1, 0, 0, 0, +1, 0, 0, 0, -1, 0, 0, 0, +1)
`2) If A and B are a complementary pair, then appending or prepending zeros to either
`
`5 A or 8, creates a complementary pair. For example, if:
`
`A= (+1, +1, +1, -1)
`
`B = (+1, +1, -1, +1)
`are a complementary pair, so are:
`
`A'= (+1, +1, +1, -1, 0, 0, 0, 0) (four zeros appended)
`
`10 B' = (0, 0, 0, 0, +1, +1, -1, +1) (four zeros prepended)
`
`Another example: if
`A= (+1, 0, +1, 0, +1, 0, -1)
`B = (+1, 0, +1, 0, -1, 0, +1)
`are a complementary pair, so are:
`
`15 A'= (+1, 0, +1, 0, +1, 0, -1, 0) (a zero appended)
`8' = (0, +1, 0, +1, 0, -1, 0, +1) (a zero prepended)
`
`20
`
`3) If A and B are a complementary pair, so are A+B and A-8. Example: since
`A= (+1, +1, +1, -1, 0, 0, 0, 0)
`B = (0, 0, 0, 0, +1, +1, -1, +1)
`are a complementary pair, therefore so are:
`Pt= (+1, +1, +1, -1, +1, +1, -1, +1)
`B' = (+1, +1, +1, -1, -1, -1, +1, -1)
`Another example: since
`
`A'= (+1, 0, +1 , 0, +1, 0, -1, 0)
`
`25 B' = (0, +1, 0, +1, 0, -1, 0, +1)
`are a complementary pair, so are:
`A'= (+1, +1, +1, +1 , +1 , -1 , -1, +1) (sum)
`
`B' = (+1, -1 , +1, -1, +1, +1, -1, -1) (difference)
`4) If A and B are a complementary pair, so are a concatenation of A and B and the
`
`30
`
`concatenation of A and -8. This results from previous properties, and actually is
`
`shown in the first example of 3.
`
`5) If A and 8 are a complementary pair, so are the element-wise interleaving of A and
`~,
`B and the element-wise interleaving of A and -8. This results from previous
`properties, and actually is shown in the second example of 3.
`
`35
`
`6) Property 4 can be expanded to contain zeros between A and 8 during
`
`concatenation. This can be shown by the following two-stage process:
`
`

`

`WO 03/075500
`
`A= (+1, +1, +1, -1)
`
`8 = (+1, +1, -1, +1)
`
`8
`
`PCT/IL03/00166
`
`In the first stage six zeroes are appended and prepended, correspondingly:
`
`A'=(+1, +1,+1,-1, 0, 0,0,0,0, 0)
`8' = (0, 0, 0, 0, 0, 0, +1, +1, -1, +1)
`
`5
`
`In second stage the sum and the difference are formed:
`
`A"= (+1, +1, +1, +1, 0, 0, +1, +1, -1, +1) (sum)
`B" = (+1, +1, +1, -1, 0, 0, -1, -1, +1, -1) (difference)
`
`Although the properties above were exemplified with binary values of +1 and -1,
`
`10
`
`those properties carry towards sequences composed of complex numbers. After the
`
`mathematical preliminary an example can be shown of generating a set of preambles
`
`for an OFDMA communication system. Assume that the communication system
`
`utilizes 12 subcarriers out of 13, with the middle one being unused. The restriction
`
`on not using the middle subcarrier is encountered in several OFDM systems for
`
`15
`
`implementation considerations related to carrier leakage in quadrature modulators. It
`
`is preferable to assign subcarriers to users in groups of three consecutive subcarriers
`
`(clusters). This is done by starting with a pair of quadriphase complementary
`sequences of length 3 (see [5]):
`A= (+1, +1, -1)
`20 B = (+1, +j, +1)
`From here is formed four subsequences:
`
`S1 = (+1 , +1, -1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0)
`
`S2 = (0, 0, 0, 0, 0, 0, 0, +1, +j, +1, 0, 0, 0)
`
`S3 = (0, 0, 0, +1, +1, -1, 0, 0, 0, 0, 0, 0, 0)
`S4 = (0, 0, 0, 0, 0, 0, 0, 0, 0, 0, -1, -j, -1)
`
`25
`
`Note that due to the sum-difference property, the following sequences are also
`
`complementary:
`
`S1+82= (+1, +1, -1, 0, 0, 0, 0, +1, +j, +1, 0, 0, 0)
`
`S3+S4= (0, 0, 0, +1, +1, -1, 0, 0, 0, 0, -1, -j, -1)
`
`30
`
`Such groups of six subcarriers, comprising two clusters, can be assigned to a
`
`user demanding a higher data rate. A user with an even higher data rate demand
`
`can be assigned all four clusters. The preamble sequence, which consists of all four
`
`parts, is also one of a complementary pair, cased on the sum-difference property,
`
`35
`
`S1+82+83+84= (+1, +1, -1, +1, +1, -1, 0, +1, +j, +1, -1, -j, -1)
`
`and so is S2 + S3:
`
`

`

`WO 03/075500
`
`9
`
`PCT/IL0J/00166
`
`82+83= (0, 0, 0, +1, +1, -1, 0, +1, +j, +1, 0, 0, 0)
`
`In the example created above, a hierarchical set of preambles, in which four
`
`subsequences with good PAPR properties in the transform domain, were aggregated
`
`5
`
`into longer sequences with 6 and 12 subcarriers, each satisfying the good PAPR
`
`property.
`
`Another example assumes that for some reason it is desired to spread apart
`
`the subcarriers in each of the groups. Then one can start with interleaving with
`
`10
`
`zeros, and then continue with utilization of the sum-difference property to maintain
`
`complementarity:
`
`S1 = (+1, 0, +1, 0, -1, 0, 0, 0, 0, 0, 0, 0, 0)
`82 = (0, 0, 0, 0, 0, 0, 0, +1, 0, +j, 0, +1, 0)
`
`15
`
`83 = (0, +1, 0, +1, 0, -1, 0, 0, 0, 0, 0, 0, 0)
`S4 = (0, 0, 0, 0, 0, 0, 0, 0, -1, 0, -j, 0, -1)
`
`Resulting in
`
`20 S1+82 = (+1, 0, +1, 0, -1, 0, 0, +1, 0, +j, 0, +1, 0)
`S3+84 = (0, +1, 0, +1, 0, -1, 0, 0, -1 , 0, -j, 0, -1)
`
`S1+S2+S3+S4= (+1, +1, +1, +1, -1, -1, 0, +1, -1, +j, -j, +1, -1)
`
`Note that in the examples above a hierarchy is created of complementary
`
`25
`
`sequences: S1, S2, S3 and S4; then S1+82 and S3+S4, which is actually a shifted
`
`S1-S2, and then the uppermost level is (S1+S2)+(S3+S4). The creation of the
`
`hierarchy utilizes the steps of shifting and add-subtract operations to generate the
`
`desired set of values.
`
`30
`
`The constructions shown above generalize naturally to a large variety of
`
`cases. While the focus is on a "trivial example" of four groups with a basic group of
`size 3, the hierarchical construction generalizes to any hierarchy with 2K groups, and
`
`any basic subcarrier group size for which a complementary pair is available. The
`
`basic groups can be clustered or spread apart; can be modified to include extra
`
`35
`
`spaces, such as by skipping the center subcarrier and using different ways of
`
`ordering groups into pairs.
`
`

`

`WO 03/075500
`
`PCT/IL03/00166
`
`10
`
`In the examples above aggregation of three clusters does not yield a
`
`complementary sequence, and indeed, the PAPR properties of such combinations
`
`are worse.
`
`In general, if the system designer desires to use only preambles with 3
`
`5
`
`dB maximum PAPR, then there are restrictions, which need to be imposed on the
`
`allocation of subcarrier groups to users. Another limitation of the described method
`
`is that it does not address the case of irregularly spaced subcarriers.
`
`For completeness, the following sizes for which pairs are known to exist are
`
`10
`
`listed:
`
`any power of 2;
`
`binary sequences of length 10, 26;
`
`quadriphase sequences of length 3, 5, 13; and
`if a sequence of length M exists, then also sequences of length M*2K exist.
`
`15
`
`For example, binary sequences of length 20 and 52 and quadriphase
`
`sequences of length 6 do exist.
`
`If pairs of sequences of lengths M, N exist, then also sequences of length
`
`2MN exist. For example, quadriphase sequences of length 18 (2*3*3), 30(2*3*5) arid
`
`20
`
`50 (2*5*5) exist, as well as binary sequences of length 200 (2*10*10).
`
`There
`
`are
`
`additional
`
`important
`
`transformations
`
`preserving
`
`the
`
`complementarity property, such as sign change or complex rotation of one of the
`
`sequences, as well as order reversal and conjugation of one of the sequences.
`
`25
`
`Those additional transformations can be used in conjunction with previously
`
`described methods to enrich the amount of preamble sets, or to search for
`
`combinations which yield better properties when sets of subcarrier groups, which are
`
`of a size other than a power of 2, need to be used.
`
`30
`
`Two examples of practical importance are now introduced. Assume an
`
`OFDMA system, which utilizes FFT size of 256, and has 208 active subcarriers. It is
`
`preferable to use 4 subchannels of 52 subcarriers each.
`
`It is assumed that the
`
`subcarriers in each subchannel are contiguous, and that the center subcarrier is not
`
`used. In such case the following construction is used:
`
`35
`
`

`

`WO 03/075500
`
`PCT/IL03/00166
`
`11
`
`S2 = (025, 025, A2s,-825, 0, 025, 02s, 026, 025)
`
`S3 = (026, 02s, 02s, 02s, 0, A2s, 82s, 02s, 02s)
`
`S4 = (A26, 825, 025, 025, 0, 025, 025,-A26, 825)
`
`5 S1+82= (A26, 82s, A26, -825, 0, 025, 025, 025, 025)
`S3+84= (026, 025, 025, 025, 0, A2s, 826, -A25, 825)
`
`S1+S2+S3+S4= (A25, 826, A2s, -825, 0, A25, 825, -A26, 825),
`Where 026 is a vector of 26 zeros.
`In this case the A26 and 82s are binary Golay sequences of length 26, and all
`the sequences above can be shown to be complementary due to the properties of
`concatenation or spaced concatenation of shorter sequences. The same goal can be
`achieved with quadriphase sequences starting with a kermel of length 13. For the
`case of 200 active subcarriers, quadriphase sequences of length 50 can be used as
`a kernel.
`
`The following exemplifies a design for a clustered OFDMA system, as in (3].
`Assume FFT size of 256 of which 208 are active subcarriers. It is preferable to use 4
`subchannels of 52 subcarriers each, however this time the subcarriers of each
`subchannel are arranged in 4 clusters of 13 subcarriers.
`In the example below the
`center subcarrier is not used. In such case the following construction is used:
`
`10
`
`15
`
`20
`
`S 1 = (A13, 013, 013, 013, 813, 013, 013, 013, 0, A13, 013, 013, 013, -813, 013, 013, 013)
`S2= (013, 013, A13, 013, 013, 013, 813, 013, 0, 013, 013, -A13, 013, 013, 013, 813, 013)
`S3= (013, A13, 013, 013, 013, 813, 013, 013, 0, 013, A13, 013, 013, 013, -813, 013, 013)
`25 S4= (013, 013, 013, -A13, 013, 013, 013, -813, 0, 013, 013, 013, A13, 013, 013, 013, -B13)
`
`S1+82=
`(A13, 013, A13, 013, 813, 013, 813, 013, 0, A13, 013, -A13, 013, -813, 013, 813, 013)
`S3+S4=
`
`S1+S2+S3+S4=
`
`(A13, A13, A13, -A13, 813, 813, 813, -813, 0, A13, A13, -A13, A13, -813, -813, 813, -813),
`where A13 and B13 are quadriphase complementary sequences reported by Frank [5],
`and 013 is a vector of 13 zeros.
`
`35
`
`

`

`WO 03/075500
`
`12
`
`PCT/IL03/00166
`
`Finally, designation is done of all the subsets of subcarriers satisfying the
`
`complementary property for possible OFDMA allocation for a set of preambles 270.
`
`5
`
`The present invention does not derive all the cases of subcarrier allocation
`
`strategies. Nevertheless, it allows generating sets of preambles for numerous
`
`practical and important scenarios.
`
`While the above description contains many specifities, and is mainly based on
`
`10
`
`examples. These should not be construed as limitations on the scope of the
`
`invention, but rather only as examples of the preferred embodiments. Those skilled
`
`in the art will envision other possible variations that are within its scope. Accordingly,
`
`the scope of the invention should be determined not by the embodiment illustrated,
`
`but by the appended claims and their legal equivalents.
`
`15
`
`20
`
`APPENDIX - PAPR PROPERTY OF COMPLEMENTARY SEQUENCES
`
`The proof of the PAPR property is presented as follows:
`
`By applying Parseval's identity, it follows that the sum of their power spectra
`
`is a constant over frequency.
`SA (w) + Ss (w) = const(w),
`RA(t) + Rs (t) = delta(t) -
`the autocorrelation of sequence X(t) and Sx(w)
`where Rx(t)
`is
`
`is
`
`the
`
`25 magnitude-squared of the Fourier transform of sequence X.
`
`From here it is concluded that if A and B have equal energy,
`then avg(SA (w)) = avg(Ss (w)) = const(w)/2, and since O =< S(w), then
`O =< SA (w) =< 2*avg(SA (w)),
`
`30
`
`0 =< Sa (w) =< 2*avg(Sa (w)),
`
`meaning that neither SA(w) nor Ss(w) exGeed twice their average value over
`
`frequency.
`
`35
`
`Note that in the proof above the sequences A and B are described as time
`
`domain sequences, and the PAPR property is satisfied in the frequency domain. In
`
`

`

`WO 03/075500
`
`PCT/IL03/00166
`
`13
`
`the OFDM application the dual property is used in which the sequences are in
`
`frequency domain, and the conclusion is that the time domain waveforms satisfy the
`
`PAPR < 2 property.
`
`

`

`WO 03/075500
`
`What is claimed is:
`
`14
`
`PCT/IL03/00166
`
`1.
`
`An Orthogonal Frequency Division Multiple (OFDM) based multiple access
`
`communication system, characterized by preambles with low Peak-to-Average Power
`
`5
`
`Ratio (PAPR), wherein the average power of the preamble-carrying OFDM symbols
`
`is boosted relative to the average power of data-carrying OFDM symbols.
`
`2.
`
`The OFDM based multiple access communication system according to claim
`
`1, wherein the preambles are to boosted in order to improve the channel estimation
`
`10
`
`accuracy and burst detection probability.
`
`The OFDM based multiple access communication system according to claim
`3.
`1, wherein the preambles are generated by mathematical construction.
`
`15
`
`4.
`The OFDM based multiple access communication system according to claim
`1, wherein the preambles are generated as a result of computer search.
`
`The OFDM based multiple access communication system according to claim
`
`5.
`1, wherein the preambles are arranged in a hierarchal set of different size.
`
`20
`
`The OFDM based multiple access communication system according to claim
`6.
`1, wherein the preambles are complementary sequences.
`
`An Orthogonal Frequency Division Multiple Access (OFDMA) based multiple
`7.
`access communication system with low-PAPR preambles, in which the preambles
`
`25
`
`are complementary sequences for any allowed allocation of subcarriers to at least
`
`one user.
`
`8.
`
`The OFDMA based multiple access communication system according to
`
`claim 7, wherein the subcarriers are assigned to the at least one user in groups of
`
`30
`
`three consecutive numbers
`
`9.
`
`The OFDMA based multiple access communication system according to
`
`claim 7, wherein
`
`the preambles are hierarchically generated complementary
`
`sequences based on seed complementary sequences.
`
`

`

`WO 03/075500
`
`15
`
`PCT/IL03/00166
`
`10.
`
`The OFDMA based multiple access communication system according to
`
`claim 9, based on a complementary pair, wherein their autocorrelations add up to a
`
`delta function.
`
`11.
`
`The OFDMA based multiple access communication system according to
`
`5
`
`claim 9, based on a complementary pair, wherein the element-wise interleavings of
`
`the complementary pair are another complementary pair.
`
`12.
`
`The OFDMA based multiple access communication- system according to
`
`claim 9, wherein the complementary sequences include complex numbers.
`
`10
`
`A method of constructing a sequence of values, starting from a basic pair of
`13.
`complementary sequences, the sequence of values to be used for modulating the
`
`subcarriers of a preamble in an OFDMA system, with the purpose of having low
`
`PAPR both for the whole sequence and for numerous subsets of the sequence
`based on the following steps:
`selecting the basic pair of complementary sequences;
`interleaving the sequences with zeroes according to the desired spread of
`
`subcarriers over frequency in a basic subcarrier group;
`repeating the step of creating new complementary sequence pairs with
`twice the number of nonzero elements, by applying the steps of
`shifting; and
`
`adding-subtracting until a sequence is created containing
`all the desired nonzero subcarriers at the desired
`locations; and
`
`designating all the subsets of subcarriers satisfying the complementary
`
`property as possible OFDMA allocation.
`
`15
`
`20
`
`25
`
`The method of constructing a sequence of values according to claim 13,
`
`14.
`wherein the complementary sequences are quadriphase sequences.
`
`

`

`WO 03/075500
`
`1/2
`
`PCT/IL03/00166
`
`Start constructing a sequence
`
`(100)
`
`Select a basic pair of complementary sequences
`(110)
`
`Interleave the sequences with zeroes
`
`(120)
`
`Create a new complementary sequence pair
`with twice the number of nonzero elements
`(130)
`
`Apply the step of shifting
`
`(140)
`
`Apply the step of adding-subtracting
`
`(150)
`
`No
`
`Designate all subsets of subcarriers satisfying the
`complementary property for possible OFDMA
`(170)
`allocation for a set of preambles
`
`F~;J- 1
`
`

`

`WO 03/075500
`WO 03/075500
`
`2/2
`2/2
`
`PCT/IL0J/00166
`PCT/1L03/00166
`
`231
`231
`
`232
`232
`
`
`
`241
`
`250
`
`Fig. 2a
`
`
`
`242
`
`250
`
`Fig. 2b
`Fig. 2b
`
`