Login| Sign Up| Help| Contact|

Patent Searching and Data


Title:
PILOT STRUCTURE TO SUPPORT A VIRTUAL DIVERSITY RECEIVER SCHEME
Document Type and Number:
WIPO Patent Application WO/2014/053980
Kind Code:
A2
Abstract:
Devices and methods for providing a pilot structure for a virtual diversity receiver (VDR) scheme are disclosed. In order to improve the performance of a communication network, a VDR scheme is implemented to facilitate the exchange of information between user devices via an intermediary device, such as a base station. The pilot structure supports estimation of channel parameters at the receivers, including true channel taps, as well as estimations of the virtual channels created by the VDR scheme in order to enable the use of receive-diversity signal processing techniques.

Inventors:
KHAYRALLAH ALI S (US)
WANG YI-PIN ERIC (US)
Application Number:
PCT/IB2013/058984
Publication Date:
April 10, 2014
Filing Date:
September 30, 2013
Export Citation:
Click for automatic bibliography generation   Help
Assignee:
ERICSSON TELEFON AB L M (SE)
International Classes:
H04L25/02
Domestic Patent References:
WO2013088377A12013-06-20
Other References:
PETER LARSSON; NICKLAS JOHANSSON: "IEEE", 2006, VTC SPRING, article "Multi-User JRQ"
Attorney, Agent or Firm:
GUPTA, Rishi et al. (MS EVR 1-C-11Plano, Texas, US)
Download PDF:
Claims:
WHAT IS CLAIMED IS:

i . A method for improving performance in a communication network, comprising: receiving, at a first user device, a first pluraiity of received information symbols intended for said first user device, including a first set of dat symbols and a first plurality of pilot sequences;

receiving, at said first user device, a second plurality of received information symbols intended for a second user device, including a second set of data symbols and a second plurality of pilot sequences;

detennining, at said first user device, a first channel estimate based on a first sequence of said second plurali !y of pilot sequences;

determining, at said first user device, a second channel estimate based on a second sequence of said second plurality of pilot sequences;

transmitting, front said first user device, said first and second channel estimates; receiving, at said first user device, one or more composite symbols, including one or more composite pilot sequences based on said first and second plurality of pilot sequences; and

determining, at said first user device, an estimated effective signal value based on at least one of said received composite symbols. 2. The method of claim 1, further comprising:

demodulating, at said first user device, said first set of data symbols based on said first plurality of received information symbols and said estimated effective signal value. 3. The method of claim I , wherein said first plurality of received information symbols is received from a base station having a first transmit antenna and a second transmit antenna, and further comprising

determining, at said first user device, said first channel estimate, fin [2], by correlating said second plurality of received information symbols with a first sequence of said second plurality of pilot sequences; and deierraining, at said first user device, said second channel estimate, J½[ 3, by correlating said second plurality of received information symbols with a second sequence of said second plurality of pilot sequences.. 4. The method of claim 3, wherein said first channel estimate, Hi t[2], is determined according to where Np is the number of received pilot symbols.. ρ ¾[2] is the conjugate of the k symbol of said first, sequence of said second plurality of pilot sequences, and i \ .-.. \ 2 j is the k* symbol of said second plurality of received information symbols, and said second channel estimate, H ι?[2], is determined according to

where Np is the number of received pilot symbols, *2^[ ] is the conjugate of the km symbol of said second sequence of said second plurality of pilot sequences, and fj A[2] is the k* symbol of said second plurality of received Information symbols.

5. The method of claim 3, wherein said first sequence of said second plurality of pilot sequences is received from said first transmit antenn and said second sequence of said second plurality of pilot sequences is received from said second transmit antenna.

6. The method of claim 1 , wherei a first sequence of said first pl orality of pilot sequences and a second sequence of said first plurality of pilot sequences are recei ved in the same set of resource elements. 7, The method of claim L wherein said first sequence is received from a first transmit antenna and said second sequence is received from a second transmit antenna at the same time. 8, The method of claim I , wherein said first plurality of pilot sequences is received at a first time and said second plurality of pilot sequences is received at a second time and said first plurality of pilot sequences is orthogonal to said second plurality of pilot sequences.

9, The method of claim 1 , wherein at least one of said first and second plurality of pilot sequences is based on Walsh-Hadaruard sequences.

10, The method of claim I. wherein at least one of said first and second plurality of pilot sequences is based on Zadoff-Chu sequences,

.1.1. The method of claim I, wherein said first plurality of received information symbols is received from a base station having a first transmit antenna and second transmit antenna,

a first sequence of said first plurality of pilot sequences is received from said iirst transmit antenna, and

a second sequence of said first plurality of pilot sequences is received from said second transmit antenna. 12. The method of claim I, wherein a first component of said first plurality of received Information symbols is received from a first base station and a second component of said first plurality of received information symbols is received from a second base station. 13. The method of claim 12, wherein said one or more composite symbols are received from said first base station and from said second base station.

14. The method of claim 12, wherein said communication network is a heterogeneous network and said second base staticm is not a macroce!t base station and is within a cell of said first base station.

15. The method of claim 8, further comprising: deie iining a channel tap product Hn[3]Hu[2], given by:

¾ where , p*u[2] is the conjugate of the kw symbol, of said first portion of said second plurality of pilot sequences, and rn 2 is the klfe symbol of said second plurality of received information symbols

1.6, The method of claim 8, further comprising:

determining a estimate of channel conditions. Hup], given by:

where H,,/ fj is representative of the channel condition between a receive antenna /' and a transmit, antenna at a time t.

17. A method for improving performance in a communication. network, comprising:

transmitting a first transmission comprising a first plurality of information symbols intended for a first user device, including a first set of data symbols and a first plurality of pilot sequences;

receiving a first set of channel estimates from a second user device based on the first transmission;

transmitting a second transmission comprising a second plurality of information symbols intended for said second user device, including a second set of data symbols and a second lurality of pilot sequences;

receiving a second set of channel estimates from said first user device based on the second transmission;

determining one or more composite symbols based on said first and second sets of channel estimates and said first and second sets of data symbols, including one or more composite pilot sequences based on said first and second plurality of pilot sequences; and

transmitting said one or more composite symbols to said first and second user devices.

18. The method of claim 17, wherein detenmning the one or more composite symbols comprises;

svnihesizins a first estimated receive value indicative of one or more signals received at said first user device;

synthesizing a second estimated receive value indicative of one or more signals recei ed at said second user device; and

combining said first and second synthesized values to determine said one or more composite symbols. 19. The method of claim 18, wherei

said first estimated receive value, is given by the expression:

r2[l] - e21[l]us [l | + H22[iju2[.l J

where said first plurality of information symbols includes mp ] and usp ], f f ;[] I represents channel conditions between said second user device and a first antenna of said base station for the first transmission, and Hull] represents channel conditions between said second user device and a second antenna of said base station for the first transmission, and

said second estimated receive value, rj[2 , is given by the expression: where said second plurality of information symbols includes «i[2] and «?[2],

Hi sf2] represents channel conditions between said first user device and a first antenna of said base station for the second transmission, and Ηι2[ ] represents channel conditions between said first user device and a second antenna of said base station for the second transmission.

20. The method of claim 19; wherein at least one of said one or more composite symbols, tij [3], is given by:

u, [33 = r, [23 + r2[13

where ra ] is said first estimated receive value and s 2] is said second estimated receive value.

21. The method of cla m 17, wherein the first set of channel estimates is based on at least one of said first plurality of pilot sequences and the second set of channel estimates is based on at least one of said second plurality of pilot sequences. 22. The method of claim 1.7, wherein a first sequence of said first phiraiity of pilot sequences and a second sequence of said first plurality of pilot sequences are transmi tted in the same set of resource elements.

23. The method of claim 22, wherein said first sequence of said first plurality of pilot sequences is transmitted from a first transmit antenna and said second sequence of said first phiraiity of pilot sequences is transmitted from a second transmit antenna at the same time.

24. The method of claim 17. wherein said first plurality of pilot sequences is transmitted at a first time and said second plurality of pilot sequences is transmitted at a second time and said first plurality of pilot sequences is orthogonal to said second plurality of pilot sequences.

25. The method of claim 17, wherein at least one of said first and second plurality of pilot sequences is based on Walsh-Hadamard sequences.

26. The method of claim 17, wherein at least one of said first and second plurality of pilot sequences is based on ZadofP-Chu sequences. 27. The method of claim 17. further comprising:

transmitting a first sequence of said first plurality of piiot sequences on a first antenna of said base station; and

transmitting a second sequence of said first plurality of pilot sequences on a second antenna of said base station,

28. The method of claim 17, wherein at least one of said one or more composite pilot sequences, p [3 j, is given by Ρι*Ρ1 - Hn[2]pl !k[2] + H12[2]p2#k[23 + ¾[l}p [l] + r½[l ]p¾[ l]

for k - 1 ... Np, where Np is the number of transmitted pilot symbols,

p! ,¾P 3 s ie k,!i symbol in a first sequence of said first plurality of pilot sequences, which is transmitted from a first antenna of said base station,

pi.fc[2] is the k* symbol in a first sequence of said second plurality of pilot sequences, which is transmitted from said first antenna of said base station,

P2.k[l 3 is the k* symbol in a second sequence of said first plurality of pilot sequences, which is transmitted from a second antenna of said base station,

P2,ji 2] is the kkl symbol in a second sequence of said second plurality of pilot sequences, which is transmitted from said second antenna of said base station,

Hn [2] represents channel conditions between said first user device and said first antenna of said base station for the second transmission, I½[2] represents channel conditions between said first user device and said second antenna of said base station for the second transmission, 1½[13 represents channel conditions between said second user device and said first antenna of said base station for the first transmission, and f½[lj represents channel conditions between said second user device and said second antenna of said base station for the first transmission,

29. The method of claim 17, wherein said first plurality of pilot sequences and said second plurality of pilot sequences are not orthogonal across time, and said one or more composite pi lot sequences, pi,k[3], Is based at least in part on a fourth pilot sequence, p' ], and is given by

pLk[3j === Hi {[2]p [23 + ¾[2]Rk[2] + i½[l]pu[l] + l½[i Jpu[l] f p\k[3j for k ~ I ... Np, where Np is the number of transmitted pilot symbols,

pi,k[lj is the k, l symbol in a portion of said first plurality of pilot sequences, which i transmitted from a first antenna of said base station,

pt i 2] is the k:is symbol i a portio of said second plurality of pilot sequences, which is transmitted from said first antenna of said base station,

2.kP 3 is the k,i! symbol in a portion of said first plurality of pilot sequences, which is transmitted from a second antenna of said base station,

P2jt 2] is the kib symbol in a portion of said second plurality of pilot sequences, which is transmitted from said second antenna of said base station. Hi i 2] represents channel conditions between said first device and said first antenna of said base station for the second transmission, Hi2 2] represents channel conditions between said first user device and said second antenna of said base station for the second transmission, represents channel conditions between said second user device and said first antenna of said base station for the first transmission, and I½[J 3 represents channel conditions between said second user device and said second antenna of said base station for die first transmission.

30. The method of claim 17, further comprising:

transmitting a first component of said first plurali ty of information symbols on a first antenna of said base station; and

transmitting a second component of said first plurality of information symbols on a second antenna of said base station, and

transmitting at least one of said one or more composite symbols on said first antenna,

wherein said second antenna is silenced during transmission of said at least one composite symbol ,

3 1. A method for improving performance in a communication network having a plurality of base stations and a plurality of user devices, comprising:

transmitting, from a first of said plurality of base stations, a first transmission comprising a first plurality of information symbols intended for a first of said plurality of user devices, including a first set of data symbols and a first pilot sequence;

transmitting, from said first base station, a second transmission comprising a second plurality of information symbols intended for a second of said plurality of user devices, including a second set of data symbols and a second pilot sequence;

receiving, at said first base station, a first channel estimate and a second channel estimate from said first user device based on the second transmission;

receiving, at said first base station, one or more inter-base station messages comprising channel estimates and information symbols transmitted from a second of said plurality of base stations; and transmitting, from said first base station, one or more composite symbols based on said first and second pluralit of information symbols, said first and second channel estimates, and said inter -base station messages.. 32. The method of claim 31, wherein said one or more communications are received from said second base station.

33. The method of claim 31 , wherein at least one of said one or more communications is information symbols previously transmitted from said second base station.

34. The method of claim 31 , further comprising:

determining an estimated receive value based on said first and second channel estimates and said inter-base station messages,

wherein at least one of said composite symbols includes said estimated receive value.

35. The method of claim 34, further comprising:

transmitting said estimated receive value from said first base station to said second base station.

36. The method of claim 31 , further comprising:

transmitting said fust plurality of information symbols from said first base station to said second base station.

37. The method of claim 31. wherein said communication network is a heterogeneous network and said second base statio is not a macrocell base station and is wi thin a ceil of said first base station. 38. The method of claim 1 , wherein a first sequence of said first plurality of pilot sequences and a second sequence of said first plurality of pilot sequences are orthogonal.

39. The method of claim 17, wherein a first sequence of said first plurality of pi Sot sequences and a second sequence of said first plurality of pilot sequences are orthogonal. 40. The method of claim 1 , wherein determining said estimated effective signal value includes detennming, at said first user device, a third channel estimate based on said one or more received composite symbols.

41. The method of claim 40, wherein determining said estimated effective signal value further includes generating a plurality of virtual antenna information symbols based on said third channel estimate, said second plurality of received information symbols, and said one or more received composite symbols.

42. The method of claim 2, wherein said first set of data symbols is demodulated based on one or more channel estimates.

Description:
PILOT STRUCTURE TO SUPPORT A

VIRTUAL DIVERSITY RECEIVER SCHEME

TECHNICAL FIELD

The present invention relates generally to improving data transmission on te!ecomtrcu catioH networks and, more particularly, to a method and device for providing a pilot structure to support a virtual diversity receiver scheme in a telecommunication network. BACKGROUND

3GPP Long Term Evolution (LTE) is a standard for mobile phone network technology, LTE is a set of enhancements to the Universal Mobile Telecommunications System (UM TS), and is a technology for realizing high-speed packet-based communication that can reach high data rates on both downlink and uplink channels. As illustrated in FIG. 1 , LTE transmissions are sent from base stations 102, such as Node Bs ( Bs) and evolved Node Bs (eMBs) in a telecommunication network 106, to mobile stations 1 4 (e.g., user equipment (UE)), Examples of wireless UE communication devices include mobile telephones, personal digital assistants, electronic readers, portable electronic tablets, personal computers, and laptop computers.

The L E standard is primarily based on Orthogonal Frequency Division Multiplexing (OFDM) in the downlink, which splits the signal into multiple parallel sub-carriers in frequency, and Single Carrier Frequency Domain Multiple Access (SC- FDMA) in the uplink. A transmit time interval (TTl) is the basic logical unit. A radio resource element (RE) is the smallest addressable iocation within a TTl , corresponding to a certain time Iocation and a certain frequency iocation. For instance, as iliostratedm ' FIG. 2, a sub-frame 200 comprised of REs 202 may be transmitted in a TTl in accordance with the LTE standard, and may consist of sub-carriers 204 in the frequency domain. In the time domain, the sub-f ame may be divided into a number of OFDM (or SC-FDMA) symbols 208. An OFDM (or SC-FDMA) symbol 208 may include a cyclic- prefix 206. Thus, the unit of one sub-carrier and one symbol is a resource unit or element 202. Wireless communication systems may be deployed in a number of configurations, such as, for example, a Multiple-Input, Multiple-Output (MIMO) radio system. An exemplary MIMO system including a base station 302, such as an eNB, and user equipment 304 is shown in FIG. 3. When a signal is transmitted by the e B 30.2 in a downlink, i.e. , the link carrying transmissions from the eNB to the UE 304, a sub- frame may be transmitted from multiple antennas 306, 308 and the signal may he received at a UE 304, which has one or more antennas. The radio channel distorts the transmitted signals from the multiple antenna ports. UE 304 may use receiver-diversity signal processing schemes to improve performance.

In an LTE system, transmissions intended for a first user are often overheard by a second, unintended user. The second user may utilize overheard data packets in various ways. For instance, "Completely Stale Transmitter Channel State information is Still Very Usefid " by . Maddah-Ali and D. Tse, Alierton Conference, 2010, describes a multi-user downlink MIMO scheme with a mechanism for information exchange between single antenna terminals, where the terminals feedback channel state information (CSl) to the serving base station. The serving base station exploits this CSl to broadcast an additional signal, which each terminal uses to create a virtual diversity receiver (VDR). This type of information exchange may be referred to as "stale feedback," since the channel may have changed significantly by the time the base station transmits the extr signal. In this scheme, a mobile device that receives signals on only a single antenna ma stiil take advantage of simple receive-diversity processing techniques. Similarly, "Multi-User ARQ " by Peter Larsson and icklas Johansson, IEEE VTC Spring, 2006, discusses an Automated Repeat request (AR.Q) control scheme that exploits the fact that users frequently overhear each other's information.

Absent from the presently known schemes is an explicit pilot structure that can be effectively used to facilitate the estimation of channel parameters at the receivers, including true channel taps, as well as estimations of the virtual channels created by the VDR scheme. The lack of pilot structure renders these schemes incomplete and unusable in practice.

Accordingly, there is a need for a pilot structure to support a virtual diversity receiver scheme in an LTE communication network in order to improve transmission quality. SUMMARY

Particular embodiments of the present invention are directed to devices and methods for providing a pilot structure for a virtual diversity receiver ( VDR) scheme in order to improve the performance of a communication network. The VDR scheme is comprised of information exchanges between user devices (terminals) via an intermediary device, such as a base station, which enables each terminal to access the received signal of another terminal. The use of a VDR boosts performance for each terminal; each terminal perforins as if it has more receive antennas than it actually does, enabling the use of recei e-di ersity signal processing techniques.

In one particular aspect, a method for improving performance in a communication network is provided. The method includes receiving, at a first user device, a first plurality of received information symbols thai are intended for the first user device. These received information symbols include a first set of data symbols and a first plurality of pilot sequences. The method also includes receiving, at the first user device, a second plurality of received information symbols intended for a second and different user device, which include a second set of data symbols and a second plurality of pilot sequences. The first user device then determines a first channel estimate based on a first sequence of the second plurality of pilot sequences, and determines a second channel estimate based on a second sequence of the second plurality of pilot sequences. The first and second channel estimates are then transmitted from the first user device, for example, to a base station. The method may also include determining the first channel estimate by correlating the second plurality of received information symbols with a first sequence of the second plurality of pilot sequences and detennining the second channel estimate by correlating the second plurality of received information symbols with a second sequence of the second plurality of pilot sequences,

The method further includes receiving, at the first user device, one or more composite symbols, including one or more composite pilot sequences based on the first and second plurality of pilot sequences. The first user device may then determine an estimated effective signal value based on at least one of said received composite symbols. For instance, the first user device determines a third channel estimate based oft the received composite symbols, and forms a plurality of effective signal values using V'DR processing based on the third channel estimate, the second plurality of received information symbols, and the received composite symbols. Based on the first plurality of received information symbols, the effective signal values, and the estimated effective virtual, antenna channels, the first user device may then demodulate the first set of data symbols.

Particular embodiments of the present invention provide a device operable in a communication network to receive a first plurality of recei ved information symbols that are intended for the device. These received information symbols include a first set of data symbols and a first plurality of pilot sequences. The device is also configured to receive a second plurality of received information symbols intended for a second and different user device, which include a second set of data symbols and a second plurality of pilot sequences. The device includes an antenna configured to receive the received information symbols, and a processor coupled to the antenna. The processor is configured to determine a first channel estimate based on a first sequence of the second pluralit of pilot sequences, and determine a second channel estimate based on a second sequence of the second plurality of pilot sequences. The device is further configured to transmit the first and second channel estimates, for example, to a base station. The processor may he farther configured to determine the first channel estimate by correlating the second plurality of received information symbols with a first sequence of the second plural ity of pi lot sequences and determine the second c hannel estimate by correlating the second plurality of received information symbols with a second sequence of the second plurality of pilot sequences..

In certain aspects, the device is also configured to receive one or more composite symbols, including one or more composite pilot sequences based on the first and second plurality of pilot sequences. The processor may then determine an estimated effective signal value based on at least one of said received composite symbols. Based on the first plurality of received information signals and the estimated effective signal value, the first user device may then demodulate the first set of data symbols using the processor.

In another aspect, particular embodiments of the present invention provide a method for improving performance in a communication network, which includes transmitting a first plurality of information symbols that are intended for a first user device, including a first set of data symbols and a first plurality of pilot sequences. The method also includes transmitting a second plurality of information symbols intended for a second user device, including a second set of data symbols and a second plurality of pilot sequences. A. first set of channel estimates is received from the second user device, and a second set. of channel estimates is received front the first user device. According to certain aspects, the first set of channel estimates is based on the first transmission and the second set of channel estimates is based on the second transmission. The method further includes determining one or more composite symbols based on the first and second sets of channel estimates and the first and second sets of data symbols. The composite symbols include one or more composite pilot sequences, which are based on the first and second plurality of pilot sequences. For instance, the composite piiot sequence may be a linear combination of the first and second plurality of pilot sequences. The method also includes transmitting the one or more composite symbols to both the first and second user devices.

According to certain aspects, determining the composite symbols include synthesizing a first estimated receive value indicative of one or more signals received at the first user device, and synthesizing a second estimated receive value indicative of one or more signals received at the second user device. These synthesized values are combined to determine the composite symbols.

Particular embodiments of the present invention provide a base station device operabie in a communication network to transmit information to a plurality of user devices. The base station includes a plurality of transmit antennas and a processor coupled to the antennas and configured to transmit a first plurality of information symbols intended for a first user device, including a first set of data symbol and a first plurality of pilot sequences. The processor is also configured to transmit a second plurality of information symbols intended for a second user device, including a second set of data symbols and a second plurality of pilot sequences. A first set of channel estimates is received from the second user device, and a second set of channel estimates is received from the first user device. The processor is further configured to determine one or more composite symbols based on the first and second sets of channel estimates and the first and second sets of data symbols. The composite symbols include one or more composite pilot sequences, which are based on the first and second plurality of pilot sequences. For instance, the composite pilot sequence may be a linear combination of the first and second plurality of pilot sequences. The processor is also configured to transmit the one or more composite symbols to both the first and second user devices.

In another aspect, particular embodiments of the present invention are directed to a method for improving performance in. a communication network that has a plurality of base stations and a plurality of user devices. The method includes transmitting, from a first of the plurality of base stations, a first plurality of information symbols intended for a first of the plurality of user devices. The information symbols include a first, set of data symbols and a first pilot sequence. The method also includes transmitting, from the first base station, a second plurality of information symbols intended for a second, and different, user device, which includes a second set of data symbols and a second pilot sequence. A first channel estimate and a second channel estimate are received at the first base station from the first user device. Additionally, one or more inter-base station messages, comprising of channel estimates and information symbols, from a second of said plurality of base stations are received at the first base station. The first base station then transmits one or more composite symbols based on the first and second channel estimates, first and second plurality of information symbols, and the inter-base station messages transmitted from the second base station.

According to certain aspects, the one or more communications are received from the second base station. These communications may be comprised of the information symbols previously transmitted from the second base station.

Particular embodiments of the present invention provide a base station device operable in a communication network to transmit information to a plurality of user devices. The base station includes a plurality of transmit antennas and a. processor coupled to the antennas and configured to transmit a first plurality of information symbols intended for a first user device. The information symbols include a first set of data symbols and a first pilot sequence. The processor is also configured, to transmit a second plurality of information symbols intended for a second, and different, user device, which includes a second set of data symbols and a second pilot sequence. A first channel estimate and a second channel estimate for a second transmission are received by the base station from the first user device. Additionally, one o more inter- base station messages, comprising of channel estimates and information symbols, transmitted from a second of said plurality of base stations are received by the base station. The processor is further configured to transmit or more composite symbols based on the first and second channel estimates, first and second plurality of information symbols, and the inter-base station messages transmitted from the second base station. BRIEF DESCRI PTION OF THE DRAWINGS

The accompanying drawings, which are incorporated herein and form part of the specification, illustrate various embodiments of the present disclosure and, together with the description, further serve to explain the principles of the disclosure and to enable a person skilled in the pertinent art to make and use the embodiments disclosed herein, in the drawings, like reference numbers indicate identical or functionally similar elements.

FIG. 1 is an illustration of a wireless communication system.

FIG. 2 is an exemplary sob-frame of art LTE transmission.

FIG. 3 is a block diagram of an exemplary MIMO system.

FIG. 4 is an illustration of a wireless communication system in accordance with exemplary embodiments of the present invention.

FIG. 5 is a block diagram of a user device in accordance with exemplary embodiments of the present invention.

FIG. 6 is a block diagram of a base station in accordance with exemplary embodiments of the present invention.

FIG. 7 is a flow chart illustrating a process for improving performance in a communication network, in accordance with exemplary embodiments of the present invention.

FIG. 8 is an illustration of pilot sequences in accordance with exemplary embodiments of the present invention. FIG. 9 is a .flow chart illustrating a process for improving performance in a communication network in accordance with exemplary embodiments of the present invention.

FIG. 10 is an illustration of a wireless eonirauiiication system in accordance with exemplary embodiments of the present invention.

FIG. 1 1 is an illustration of a wireless communication system in accordance with exemplary embodiments of the present invention.

FIG. 12 is a How chart illustrating a process for improving performance in a communication network in accordance with exemplary embodiments of the present invention.

DETAILED DESCRIPTIO

Particular embodiments of the present invention are directed to devices and methods for providing a pilot structure for a virtual diversity receiver (VDR) scheme.

In order to improve the performance of a communication network, a VDR scheme may be implemented to exchange information between user devices via an intermediary device, such as a base station, as shown for example in PIG. 4. The pilot structure supports estimation of channel parameters at the receivers, including true channel taps, as well as estimations of the virtual channe ls created by the VDR scheme. Accordingly, each terminal performs as if it has more receive antennas tha it actually does, enabling the use of recei ve-di versity signal processing techniques,

FIG. 5 illustrates a block diagram of an exemplar UE communication device 404. As shown in FIG. 5, the UE communication device may include: one or more antennas 502, a data processing system 506, which may include one or more microprocessors and/or one or more circuits, such as an application specific integrated circuit ( ASIC), field-programmable gate arrays (FPGAs), or the like, and a data storage or memory system 508, which ma include one or more non-volatile storage devices and/or one or more volatile storage devices (e.g., random access memory (RAM)). The one or more antennas 502 are connected to transceiver 504, which is configured to transmit and receive signals via the one or more antennas 502.

In embodiments where data processing system 506 includes a microprocessor, computer readable program code may be stored in a computer readable medium, such as, but not limited to, magnetic media (e.g., a hard disk), optical media (e.g., a DVD), memory devices (e.g., random access memory), and the like. In some embodiments, computer readable program code is configured such that when executed by a processor, the code cause the data processing system 506 to perform steps described below (e.g., steps described below with reference to the flow charts shown in FIG. 7). In other embodiments, the UE communication device 404 is configured to perform steps described above without the need for code. That is, for example, data processing system 506 may consist of one or more ASICs. Hence, the features of the present invention described above may be implemented in hardware and/or software. For example, in particular embodiments, the functional components of the UE communication device 404 described above may be implemented by data processing system 506 executing computer instructions, by data processing system 506 operating independent of any computer instructions, or by any suitable combination of hardware and or software.

FIG. 6 illustrates a block diagram of an exemplary base station 402. As shown in FIG. 6, the base station 402 may include: a data processing system 608, which may include one or more microprocessors and/or one or more circuits, such as art application specific integrated circuit (ASIC), fieki-programmable gate arrays (FPGAs), and the like; a network interface 606; and a data storage system 61.0, which may include one or more non-volatile storage devices and/or one or more volatile storage devices (e.g., random access memory (RAM)). The network interface 606 is connected to transceiver 604, which is configured to transmit and receive signals via one or more antennas 602, In particular embodiments , the antennas may be configured to include one or more antenna ports. For instance, antennas 602 may include a first antenna port 0, and a second antenna port 1, which correspond to ports 0 and 1 of the LTE specification. In an exemplary embodiment of the disclosed devices and methods, the base station 402 is a Node B or Evolved Node B.

In embodiments where data processing system 608 includes microprocessor, computer readable program code may be stored in a computer readable medium, such as, but not limited, to magnetic media (e.g., a hard disk), optical media (e.g., a DVD), memory devices (e.g., random access memory), and the like, in some embodiments, computer readable program code is configured such that when executed by a processor, the code causes the- data processing system 608 to perform steps described below (e.g. , steps described below with reference to the flow chart shown in FIGS. 9 and 12), In other embodiments, the base station 402 is configured to perform steps described above without the need for code. That is. for example, data processing system 608 may consist merely of one or more ASICs, Hence, the features of the present invention described above may be implemented in hardware and/or software. For example, hi particular embodiments, the functional components of the base station described above may be implemented by data processing system 608 executing computer instructions, by data processing system 608 operating independent of any computer instructions, or by any suitable combination of hardware and/or software.

Referring to FIG. 7, a flow chart 700 is shown, which illustrates a process for communicating information between a base station and user devices in a wireles communication network. According to certain embodiments of the present invention, the base station may include multiple transmit antennas while each of the user devices has only a single receive antenna. One of ordinary skill in the art will recognize that this scenario may be extended to the case of K transmit antennas and K. user devices, for K > 2. Similarly, the process 700 also applies to user devices that have more than one receive antenna.

For example, as illustrated in FIG. 4, a base station 402 havin at least two transmit antennas transmits information to two user devices, 404 and 406. The user devices 404 and 406 each have a single receive antenna and can communicate with the base station 402 via one or more communication channels. However, they cannot communicate with each other.

In step 702, the base station 402 transmits a first plurality of information symbols intended for a first of the user devices 404. For instance, at a first time, / :::: 1 , base station 402 transmits two sets of information symbols, uj [ lj and « 2 [i], which are intended for the first terminal, user device 404. (Here and in the description below, boldfaced variables indicate vectors representin a set of symbols.) The first set of information symbols, may be transmitted from a first transmit antenna of the base station 402, while the second set of information symbols, u l j, may be transmitted from a second transmit antenna of the base station 402. These signals are not only received by the intended user device, 404, but also by a second terminal, user -π- device 406. Each set of information symbols, u ? [t], include a set of dat symbols and a set of pilot symbols. A set of pilot symbols forms a pilot sequence.

Similarly, in step 706, at * ::: 2, the base station 402 transmits a second plurality of information symbols mciuding two sets of information symbols, uj[2] and u-i 2 ' j, which are intended for the second terminal, user device 406. This transmission will be overheard by the unintended recipient, user device 404. Each set of information symbols include a set of data symbols and a set of pilot, symbols.

The resulting system is given by for / ::: Ϊ , 2, where u > [t] denotes the set of miormation symbols transmitted from antenna /, H. [f I denotes the channel from transmit, antenna , / to terminal i, r ] denotes the set of received information symbols at terminal /, and z; t] denotes the noise at terminal i.

The term symbol may be understood to the present context as representative of either a single symbol in a particular RE or as a block of multiple symbols, such as in the time, frequency, or code domains, or any combination thereo In order to facilitate channel estimation, a pilot symbol structure is incorporated into the information symbols of the transmitted signal. The pilot symbols should be known to the receiving user devices. This pilot structure complements the stale feedback scheme and enables the estimation of both true and virtual channel taps. Exemplary pilot sequences are shown in FIG, 8.

According to particular embodiments, the set of information symbols u,i t] is comprised of N individual symbols, occupying N resource units. Those resource units may be distributed in time, frequency or code space, and may be contiguous or spread out. independent of how the symbols are placed physically, without any loss of generality, one may consider aj t as a 1 -dimensional sequence of length Λ with elements a, j t ] , k ~ 1-- -N .

According to particular embodiments, the set of information symbols Ujjt] is comprised of data symbols, denoted by d.[t], and N ~ N ··· N a pilot symbols, denoted by p t tj. A set of pilot symbols p,|t] may occupy a first portion of u,ft], e.g., the first N p resource units of ti;[fj. A set of data symbols d,[t] may occupy the last N a resource units of u,[t]. This configuration may be defined by the following; ρ^ Μ^ Μ» ^'- ί 2 ) and

di,*r I ~ "i ff* j f ] . * ~ 1 (3)

Pilot symbols may be strategically placed within a given transmission in order to faciiitate certain aspects of channel estimation. For instance, in an OFDM system, pilot symbols may be spread out in time and frequency, to capture frequency variations. Alternatively, m a GSM system, they may be lumped together in the middle of a time slot to capture time dispersion.

In one embodiment, the pilot symbols of two pilot sequences

are placed in the same air interface resource units. Accordingly, they will overlap completely at the receiver. In addition, the two pilot sequences may be chosen to be orthogonal to each other, i.e., that the inner product between the pilot sequences is zero:

The orthogonality property improves channel estimation at the receivers, user devices 404 and 406.

A. received signal r f [l] at terminal may be given by equation (I), with elements r< dYL k ~ i- - - N . According to an embodiment, the first W, symbols correspond to pilot symbol locations. A terminal, for instance user devices 404 and 406, can compute the estimate H s [f] - r ¾ \ t) p^ \ f] (5) which may be scaled by **, \ t " jp' i k jYJ . Other channel estimation schemes may be used alternatively. For example, the characteristics of the impairment component in the received information symbols may be accounted for in the channel estimation process as in the case of minimum mean-square error (MMSE), maximum-likelihood (ML), or maximum-a-posteriori (M AP) channel estimation. Although ff jY] may be distorted by noise, it is not distorted by the other channel's signal, in the case of pilot orthogonality. Also, N can be chosen large enough to ensure that H ;! I t ] is close to the desired

H s I r ] . Such a selection reduces the number of data symbols that may be transmitted.

According to one embodiment of the present invention, each of the terminals, user devices 404 and 406, communicate channel information to the base station 402 after receiving the received information symbols discussed above. For example, user device 404 has received while user device 406 has received i¾[2j, each containing the respective intended information symbols. Similarly, user device 404 has received r_[2], while user device 406 lias received r 2 [l], each containing the respective unintended information symbols.

In steps 704 and 708, the base station 402 receives feedback; information from the user devices 404 and 406. For instance, in step 704 the base station 402 receives a first set of channel estimates from the second user device 406, and in step 708 the base station 402 receives a set of channel estimates from the first user device 404. The first set may be based on a first transmission, such as the first plurality of information symbols transmitted in step 702. while the second set may be based on a second transmission, such as the second plurality of information symbols transmitted in step 706. According to particular embodiments, each terminal, L feeds back the channel values for t≠ i . These values are received by the base station 402 before a third time, / = 3,

Using the channel estimates, the base station 402 can synthesize received values r i [2 ] and £ 2 f 1 ] according to

f (6)

These values may be transmitted to the user devices 404 and 406 so that each can recover the parts it needs in order to form a virtual antenna.

In step 710, the base station 402 determines one or more composite values based on the channel estimates. For instance, the base station 402 may combine the synthesized values according to

« t [3J » r,[2] + r 2 [1 ] (7)

I step 712, the composite value, which includes one or more composite pilot sequences, is transmitted from base station 402, it may be transmitted, for example, at ::: 3 from the first antenna. According to particular embodiments, the second antenna may be silent during transmission of the combined symbol. The set of composite symbols uj[3], described by equation

(7) may be expanded to yield u 5 3] =?,[2J + r 3 l] (8)

-HnPjujPJ +

where is used in place of Wjf ' J to maintain consistency. According to particular embodiments , the pilot and data symbols within each set of the infonnation symbols « ; itj, are the same as in the original transmissions at / ~ 1 and 2. In one embodiment, the first N g resource units of the set of composite syrabols are occupied by pilot symbols and form the pilot sequence / t [3], where the km symbol in the pilot sequence

p u [3] - H„ [2]ρ [2] + [2] ÷

H w [1]p 1A [1 + H M [1]p w {

for k~V--N n . In this scheme, the pilot sequence itself is a linear combination of pilot sequences,

According to certain embodiments, the first user device 404 receives the set of composite symbols at time t :::: 3. The received signal, i's[3], may be defined as

r ; [3] = Hui3]a,[3] + z ,[3] = H n \3]( fi[2] + f 2 [ij) + Zl [3] (10)

Because the expression of equation (10) includes f 2 [ i j, user device 404 can use rj[3] to create a signal at a second virtual antenna, labeled 2, at time 1, r 2 [l]. This signal may be used to complement the true signal, rj[l], of user device 404. User device 404 received nj ' 2i earlier; thus, it can use it to eliminate f t i2{ from equation (10) to obtain the effective signal at virtual antenna 2, which is denoted r 2 [1] and given by r 3 v [l] -r f [3]™H fJ [3]ri[2]

= H. u [3]H 2l [?]u { [lJ + Η 5 [3]Η 22 [1]¾[Π + ( ζ ι[3] ~ H„[3]*,[2]) (11)

- H 2l 11]ui l] + H 2 2 v 1]«2 i] + ¾ ¥ [1]

where H^ ; [l]^« tl [3]« 2f [1] (12) is the effective channel to virtual antenna 2, and

ζ [1 ] - Ζ! [3] ~ Η π [3]¾[2] (13) is the effective noise at virtual antenna 2. Essentially, r /[I] looks like a received signal at a virtual second antenna at user device 404 at time t~l. The processing described in equations (I I )-(I3) may he referred to as "VDR processing."

Similarly, the second user devic 406 can utilize u.i 3], because it contains f i [2j. At time user device 406 receives

i¾[3] - Ha,[3J«i[3] + ¾[3] === i½[3]( f f [2] + f ,[! ]) + ¾[3J (14).

The second user device 406 can then use r 2 [3] to estimate a signal at a second virtual antenna, labeled 1 , at time r ::: 2, to complement its true signal ι· 2 [2]. User device 406 eliminates f ?[1 } from r 2 [3] to obtain its own signal from virtual antenna 1 at time t ~ 2, given by

r 5 [2] - r 2 [3] - H 25 [3]r 2 [l]

- Η 5 Γ[2] in [2] + H l2 v [2] u 2 [2J + * | 2] (15)

where

H [2] - W 2 , [3]H lf [2] (16) is the effecti ve channel to virtual antenna 1 , and

z, v [2] - z 2 [3] ~- H 2 j[3]z 2 [l ] (17)

is the effective noise at virtual antenna 1.

Overall, the above-described scheme requires 3 channel uses to transmit 4 information symbols. The total rate is R ~ 4 / 3 symbols per channel use. Because each user device feeds back information to the base station, the base station can exploit the multi-user nature of the scenario to efficiently pack information for more than one terminal in subsequent transmissions, e.g. , composite symbols, and minimize the number of time peri ods.

According to particular embodiments, a base station, such as the device illustrated in .FIG. 6, includes one or more antennas 602, one or more transceivers 604, and data processing resources 608, which together are configured to improve data transmission in a communication network as detailed in flow chart 700.

With reference to FIG. 9, a flow chart 900 is shown, whic illustrates a process for improving performance in a communication network that includes one or more base stations and a plurality of user devices. In step 902, a user device, for instance, user device 404, receives a first plurality of received information symbols. These received information symbols include a first set of data symbols and a first plurality of pilot sequences. For instance, the received information symbols ma include pilot sequences pj[l] and pj [2] shown in FIG. 8, They may be received from a base station, such as base station 402.

In step 904, user device 404, receives a second plurality of received information, symbols. These received information symbols include a second set of data symbols and a second plurality of pilot sequences. For instance, the second plurality of received information symbols may include pilot sequences pi [2j and pa[2] shown in FIG. 8. According to particular embodiments, the first plurality of information symbols was intended for the first user device 404, while the second plurality of information symbols was intended for a different terminal in the communication network, for instance, user device 406.

In step 906, the user device 404 determines a first channel estimate based, at least in part, on a first sequence of the second plurality of pilot sequences by correlating the second plurality of received information symbols wit the first pilot sequence. For instance, user device 404 may determine a first channel estimate, Hn[2], according to where N p is the number of received pilot symbols, p*i.k[2] is the conjugate of the k <h symbol of the first sequence of the second plurality of pilot sequences, and i"i ;k [2] is the m symbol of the second plurality of received information symbols.

Similarly, in step 908, the user device 404 determines a second channel estimate based, at least in part, on a second sequence of the second plurality of pilot sequences by correlating the second plurality of received information symbols with the second pilot sequence. For instance, user device 404 may determine a second channel estimate. 1½[2], according to where N p is the number of received pilot .symbols, *2λ[2) s the conjugate of the k i f symbol of the second sequence of the second plurality of pilot ' sequences, and r [2] is the k* symbol of the second plurality of received information symbols.

In step 910, the user device 404 transmits the first and second channel estimates. These may be transmitted directly to a base station, such as base station 402, or to an intermediary network location that is in communication with the base station 402. One or more composite symbols are the determined and transmitted to user device 404. The symbols may be determined, for example, in accordance with the process described in flow chart 700.

In step 912, the user device 404 receives one or more composite symbols, which include one or more composite pilot sequences based on the first and second plurality of pilot sequences. The pilot sequence may be a combination of the first and second plurality of pilot sequences, for instance, as shown in equation (9).

In step 914, user device 404 implements the VD scheme and determines an estimated effective signal value based on at least one of the received composite symbols. This value may be determined, for instance, using equations (10)~(13) as discussed with respect to flow chart. 700. Step 914 may include, for example, determining a third channel estimate based on the one or more received composite symbols and forming a plurality of virtual antenna estimated effective signal values. The estimated effective signal values are based on the third channel estimate, the second plurality of received information symbols, and the one or more received composite symbols.

In step 916. user device 404 is able to demodulate the first set of data symbols using the first plurality of received information symbols and the estimated effective signal value.

According to particular embodiments, user equipment (UE), such as the device illustrated in FIG. 5, includes one or more antennas 502, one or more transceivers 504, and data processing resources 506, which together are configured to improve data transmission in a communication network as detailed, in flow chart 900.

According to certain embodiments, further constraints regarding orthogonality ma be placed on the pilot sequences. For instance, it may be a requirement that the pilot sequences also be orthogonal across time; ie., that pi IJ and pjfl ] are orthogonal to i [2] and j¾[2]. in this scenario, and given that user device 404 has already computed the estimates W„ j 2 ] and H i3 \ 2 | , it can now compute the estimate of the channel, tap product H \ S \H \ 2 \ , which is given by

H„[3lH„[2 Xr TA [3lp [2] (20)

Accordingly, there will not be any distortion from the other signal components (see equation 9), since all pilot sequences are orthogonal. Additionally, the product estimate

(20) can be divided by H t1 [ 2 | to obtain an estimate H^ j S j .

Also, as with the result of equation (5), the product may be scaled by

Alternatively, user device 404 can compute the channel tap product estimate H, t [3 \H n \ 2] using pilot sequence ρ 2 [2]„ and divide it by W 12 [2] to obtain another estimate of H [3] .

Also, in order to take advantage of the pilot energy to the largest extent, user devic 404 can compute the estimate H 3 ] as an average:

Any of the above-identified estimates enables user device 404 to complete the VDR transformation.

User device 406 may operate in a similar fashion. For example, at time ( - 3, it already has H 3i f 1] and \ 1] , and it can estimate H \ 3]H 21 [ ~ 1] , H \ SlH^ 1] , or both, and get the corresponding estimate H \ 3 | .

According to certain embodiments of the present invention, user device 404 may determine virtual channel taps. For instance, given that user device 404 has the virtual antenna signal r 2 ¾ [l.]. for instance, as determined with respect to equation (10), it may estimate the virtual channel tap [1] . This may be accomplished by computing the iirner product with pilot sequence pi [ l]. Similarly, user device 404 may use pilot sequence p?[i ] to estimate Ηϊ 2 | 1 ] , which enables it to complete the VDR.

Thus, user device 404 can demodulate the symbols d ! k [1] using 2-anienna receiver teehniques such as, for example, minimum mean-square error ( MSE) or successive interference cancellation (SIC), User device 406 may operate in a imilar way, first estimating the true channel tapW 2 , [ 3] , and then the virtual taps W [2] and v i \ 2 \ .

According to particular embodiments, the requirement of orthogonality across time may be lifted, in this case, it may be necessary to introduce an additional sequence |} ! i [3 ' j ; with N p symbols p k \ 3], that can be placed in the same resource units as the previously discussed pilot sequences. The additional sequence should be orthogonal to the other sequences, and equation (9) may be modified as follows:

Pu P] 31 H ^ [ 2 ] Pw [ 2 ] + H « [ 2 ]¾* [2] ÷ p ,

H2i [2] [¾ + ¾ [2] ¾ . [ ] * [3]

In this embodiment, the composite pilot sequence is a combination of five pilot sequences. A user device 404, 406 (terminal ) can compute the channel estimate according to

¾ 3 >¾*[ 3 K[ 3 ] (23)

Again, this value may be scaled, and enables the receiver to complete the VDR transformation.

In certain embodiments, the pilot sequences }>; ! ] . }>; i ] . |>; j 21. p;[2j. and ρΊ[3] can be based on Walsh-Hadamard sequences or Zadoff-Chu sequences. These sequences may all share the same set of radio resource elements (time, frequency) as illustrated in Figure 8.

The VDR scheme described above can be generalized to involve more than two terminals and more than two transmit antennas. The pilot structure also generalizes accordingly.

According to certain embodiments of the present in vention, the disclosed VDR concept can be applied to a network including transmit antennas on different base stations and multiple user devices. For instance, the VDR concept may be adapted to a cell-edge scenario, as shown in FIG. 10. I» this case, different user devices 1006, 1012 may belong to different base stations 1002, 1 08, as shown by their respective cells 1004, I0I0. instead of signals from adjacent base stations fighting one another, they can be used constructively. For instance, at time / - 1 , base stations 1002 and 1008 ma simultaneously transmit different components of a set of information symbols. sueh as symbols u \ [l] and usjTj respectively, both intended or a first terminal, user device 1006. The second terminal, user device 1012. also listens. Similarly, at time - 2, base stations .1002 and 1008 simultaneously transmit symbols u 3 [2] and u^[2] intended for user device 1012, while user device 1006 listens.

In the scenario where each terminal communicates with its own serving base station, user device 1006 feeds back two channel values H {2] to its serving base station 1002, and user device 1012 feeds back two channel values H 2i [1] to its serving base station 1008. It is presumed that the base stations 1002, 1008 can communicate directly or through the infrastructure. After the necessary exchange of information, a composite super-symbol is transmitted simultaneously from both base stations 1002, 1008 at time /

The transmission of a common super symbol is possible due to the exchange of information between the base stations and terminals. For instance, at a minimum, base station 1002 knows H 1t [2] , ., j 2j . «i[l ] and ti2[2], while base station 1008 knows H 21 [1] , H 22 [1] , u? l J and u 2 j. in order to synthesize a received value f t[2] according to equation (6), it is necessary to have H,, [2] , N 12 [2] , uj[2] and uz[2] known by a single device. Therefore, if base station 1008 {or a higher layer in the network) sends «2[2] to base station 1002, the latter can construct ? i[2].

Similarly, in order to synthesize r 2p ], it is necessary to have H 21 [1] , H ¾ [1] , M - l i and 2 [ ij known by a single device. If base station 1002 sends u t i l I to base station 1 08, the latter ca construct r Finally, base station 1002 can send f f [2] to base station 1008, and base station 1008 ca send r a[l j to base station 1002. At time ;:: 3, both base stations transmit the same combined symbol, for instance,

u^aj - ^Pj - f i PI + r slI] (24)

This transmission may be done in broadcast mode, so that the received signal appears to come from one base station.

The pilot design described above readily applies to the two base station models illustrated in FIGS. 1.0 and 1 1. For / 1 and 2, base station / transmits pilot |> 5 tj. For t - 3, the network uses the channel feedback values received at both base stations to construct and transmit the pilot super-symbol according to equatio (9) or (22). Referring now to FIG. 12, a flow chart 1200 of a process for improving performance in a communication network that has a plurality of base stations and a plurality of user devices is shown.

In step 1202, a first base station 1002 transmits a first plurality of information symbols, which are intended for a first user device 1006. The information symbols include a first set of data symbols and a first pilot sequence. At step 1204, the first base station 1 02 transmits a second plurality of information symbols intended for a second, and different, user device, 1012. The second information symbols include a second set of data symbols and a second pilot sequence.

In step 1206, base station 1002 receives a first channel estimate and a second channel estimate from the first user device 1006. Additionally, in step Ϊ 208, one or more communications indicating information transmitted from a second of the plurality of base stations, 1008, is received at the first base station 1002.

In step 1210, the first base station 1002 transmits one or more composite symbols based on the first and second plurality of information symbols.

The scheme described by flow chart 1200 also applie to the scenario illustrated in FIG. 1 1 , where the network is a heterogeneous network and the second base station is not a macrocell base station and is within a cell of the first base station. This is essentially an extreme version of the cell-edge scenario shown in FIG, 10.

According to particular embodiments, a base station, such as the device illustrated in FIG. 6, includes one or more antennas 602, one or more transceivers 604, and data, processing resources 60S, which together are configured to improve data transmission in a communication network as detailed in flow chart 1200.

While various embodiments have been described above, it should be understood that they have been presented by way of example only, and not limitation. Thus, the breadth and scope of the present disclosure should not limited by an of the above- described exemplary embodiments. Moreover, any combination of the above-described elements i all possible variations thereof is encompassed by the disclosure unless otherwise indicated herein or otherwise clearly contradicted b context.

Additionally, while the processes described above and illustrated in the drawings are shown as a sequence of steps, this was done solely for the sake of illustration. Accordingly, it is contemplated that some steps may be added, some steps raa be omitted, the order of the steps may be re-arranged, and some steps may be performed in parallel.