Efficient peak-to-average-power reduction for ofdm and mimo-ofdm

CROSS REFERENCE TO RELATED APPLICATIONS This application claims priority to U.S. Provisional Application No. 62/536,955, filed July 25, 2017, the entire contents of which are incorporated herein by reference. incorporated.

The following relates generally to wireless communications, and more specifically to precoding multicarrier waveforms.

Wireless communication systems are widely deployed to provide various telecommunication services such as telephony, video, data, messaging and broadcasting. A typical wireless communication system may employ multiple-access techniques capable of supporting communication with multiple users by sharing available system resources (e.g., bandwidth, transmit power, etc.). . Examples of such multiple-access techniques are code division multiple access (CDMA) systems, time division multiple access (TDMA) systems, frequency division multiple access (FDMA) systems, orthogonal frequency division multiple access (OFDMA) systems, single carrier frequency It includes division multiple access (SC-FDMA) systems and time division synchronous code division multiple access (TD-SCDMA) systems.

These multiple-access technologies have been adopted by various telecommunications and wireless networking standards to provide a common protocol that allows different wireless devices to communicate. An example of a telecommunications standard is Long Term Evolution (LTE). LTE improves spectral efficiency, reduces costs, improves services, by using new spectrum, as well as OFDMA on the downlink (DL) and SC-FDMA on the uplink (UL ) and integrated with other open standards using multiple-input multiple-output (MIMO) antenna technology, designed to better support mobile broadband Internet access. A series of enhancements to the telecommunications system (UMTS) mobile standard.

A wireless communication network may include multiple base stations that can support communication for multiple user equipment devices (UE) and/or access terminals of various types. A UE may communicate with a base station via the downlink and uplink. The downlink (or downlink) refers to the communication link from base stations to UEs, and the uplink (or uplink) refers to the communication link from UEs to base stations.

<p>Additional features and advantages of the disclosure are described below. Those skilled in the art should appreciate that they may readily utilize the present disclosure as a basis for modifying or designing other structures for carrying out the same purposes of the present disclosure. Those skilled in the art should also realize that such equivalent constructions do not depart from the teachings of the present disclosure as set forth in the appended claims. The novel features which are believed to be characteristic of the present disclosure, both as to organization and method of operation thereof, together with further objects and advantages thereof, will be better understood from the following description when considered in conjunction with the accompanying drawings. . It is to be expressly understood, however, that the drawings are provided for purposes of illustration and description only, and are not intended to define the scope of the present disclosure.</p>

<p>Aspects disclosed herein exploit partial updates to candidate symbol sequences to enable computationally efficient reduction of the peak-to-average power ratio (PAPR) of OFDM signals. This is applicable to various types of OFDM signals, including (but not limited to) MIMO-OFDM, spread-OFDM, SC-FDMA, and OFDMA signals. In MIMO-OFDM, the PAPR-based metric is N_tall MIMO transmitters, or a predetermined subset of transmitters (N_s&lt;N_t), it is possible to take PAPR measurements into account. Parameter selection (e.g., selective mapping (SLM) symbols, spreading codes, scrambling sequences, dummy data symbols, scheduling of subchannels for PAPR-reducing symbols, etc.) may affect the computed "best" PAPR-based metric. can be selected accordingly. The PAPR response to each transmitter or antenna can be weighted by a corresponding PAPR sensitivity scaling factor to create a PAPR-based metric. Transmitter and/or antenna scheduling is a distributed MIMO antenna array with at least one transmitter or at least one antenna for the optimization problem of finding a good PAPR-based metric with less PAPR-susceptible antennas. It can be configured to provide additional degrees of freedom.</p><p>Aspects disclosed herein can include data independent update schedules, data dependent update schedules, and combinations thereof. Data-dependent update schedules may converge faster than algorithms with data-independent update schedules in some cases (eg, for stationary signals). A step size for updating the parameters can be selected to improve convergence and/or stability. The step size may be constant or variable based on one or more metrics. In some embodiments, conditions on the step size are derived to yield convergence in the mean and root mean square sense.</p><p>In some aspects, the parameters updated in the data independent update schedule are randomly chosen. Aspects may use a probabilistic partial update algorithm. In one example, the parameters to be updated are partitioned into multiple subsets of the total set of parameters, and then the subsets are randomly selected to be updated at each iteration. In some aspects, a predetermined schedule of parameters that are updated at each iteration is provided.</p><p>The partial update algorithm used herein can be configured to reduce the number of computations and take into account the cost for increased program and data memory. For example, reducing the number of execution cycles may be offset by the additional cycles required to store data in intermediate steps. The processing metric optimized by the algorithm can include any combination of these costs. While matrix-vector multiplication is a memory-bound application kernel, aspects disclosed herein provide a partial update method adapted to discrete-time OFDM signals, which allows the generation of candidate discrete-time signals to be , it is possible to benefit from optimized solutions used for sparse processing operations. For example, for sparse matrix and/or vector multiplication, GPU architectures can be configured to optimize global memory accesses, optimize shared memory accesses, and/or exploit reuse and parallelism. Other optimizations result in tuning configuration parameters, such as changing multiple threads per thread block used for execution, changing multiple threads handling a row.</p><p>A common technique begins with a run-time preprocessing of sparse matrix-vector multiplication that identifies and extracts dense sub-blocks. However, the sparse matrices disclosed in the partial update technique herein have a well-defined structure that is known prior to runtime, which simplifies not only pre-processing but also post-processing. be able to.</p><p>In one aspect, {x_n,u} is the input data series and {w_n,uLet } denote the coefficients of an adaptive filter of length N.</p><p>W._u=[W_1,uW._2,u...W_N,u]^T.X_u=[X_1uX_2,u...X_N,u]^T.where the terms defined above are for the instant u and ()^T.will print the transpose operator. The problem is to get the OFDM signal with the lowest PAPR by X_uand/or w_uis to choose In some SLM aspects, multiple candidate symbol sequences X_uIt is possible to provide The SLM converts the input data symbol sequence X into a phase rotation matrix or other complex-valued matrix w_ucan be achieved by multiplying by Symbol series Y_u=w_uIt is possible to generate X, where w_uis the uth^this a candidate phase rotation matrix for .</p><p>A Partial Transmit Sequence (PTS) scheme may be used, where phase optimization seeks the optimal combination of signal sub-blocks. weight value w_umay be selectable from candidate phase sequences in the weight codebook. In some aspects, Dummy Sequence Insertion (DSI) is used. weight matrix w_umay provide dummy symbol insertion, such as by matching dummy symbols within a resource block and/or within a layer. Dummy symbol insertion may use spatial subchannels orthogonal to the signal space used for communication, or subchannels allocated for PAPR reduction, such as signal space projection. A combination of the PAPR reduction techniques described above can be used, such as a combination of DSI and PTS schemes. Other combinations are also possible.</p><p>For OFDM modulation, a block of N data symbols (one OFDM symbol), {x_n,n=1,...,N} means that each symbol has a set {f_n,n=0,1,...,N} are transmitted in parallel to modulate different subcarriers. The N subcarriers are orthogonal, i.e. f_n=nΔf, where Δf=1/NT and T is the symbol period. The complex envelope of the transmitted OFDM signal is:<math num="1"><img file="JP7208917B2_D0001.tif" /></math>(where 0 t NT and X_ncan include weight terms).</p><p>The PAPR of the transmitted OFDM signal is given by<math num="2"><img file="JP7208917B2_D0002.tif" /></math>(where E[] denotes the expected value. The Complementary Cumulative Distribution Function (CCDF) is one of the most commonly used performance metrics for PAPR reduction, and the OFDM symbol of PAPR is a given threshold PAPR₀is the probability of exceeding , which is CCDF=Pr(PAPR&gt;PAPR₀). Other PAPR performance metrics may be used, such as PAPR normalized for peak amplitude, crest factor, or shaping gain. Reduced PAPR allows you to either send more bits per second with the same hardware or the same bits per second with lower power and/or cheaper hardware system can be calculated from).</p><p>The optimization problem of finding the precoded data vector that yields the OFDM signal with the lowest PAPR can be viewed as a combinatorial optimization problem. Suboptimal techniques derive weights w that yield acceptable reductions in PAPR while achieving significant reductions in search complexity. Partial updates can provide an advantageous version of this technique.</p><p>In SLM, one approach is to change all symbols in the candidate symbol sequence at each iteration to minimize the covariance of the average symbol power of the candidate sequence. Zero covariance of a pair of candidate symbol sequences indicates that they are mutually independent. This distributes the U samples widely over the solution space. In some aspects of the present disclosure, the weight sequences provide amplitude variations in addition to phase shifts, which may reduce the covariance of average symbol powers between candidate sequences more than phase shifts alone. . These amplitude variations can reduce the symbol changes between candidate sequences while keeping the covariance values the same (or better), which results in a sparse instead of full (i.e. dense) weight matrix. (eg partial update) It is possible to use a weight matrix. This also allows the use of sparse reversible transform operations. When performing operations such as transforms and multiplications with sparse matrices, it may be advantageous to store only non-zero elements to save memory space and processing time. Sparse arithmetic optimizations have been developed that provide very efficient memory access patterns, and the novelty disclosed herein makes such optimizations for SLM and other PAPR reduction techniques possible. be possible.</p><p>With repeated sampling of the solution space, PAPR measurements can guide the subsequent selection of candidate symbol sequences. This is where partial updates are particularly useful. In many iterative techniques, subsequent samples are close to previous samples, so at least some covariance of average symbol powers between sequences is desired. This approach can adaptively search the solution space and quickly converge to a global or local "best" solution. In this case, the solution space samples tend to cluster around the global or local best solution. For iterative updates, it may be useful if the alternate symbol sequences are at least somewhat correlated. This allows the next update to be determined based on the PAPR measurements of the previous update. For example, it can determine which weight values to update, as well as the magnitude and/or phase of updates that may further reduce PAPR. This can facilitate convergence to an acceptable or best PAPR. In the disclosed aspect, the weight w_uneed not depend on the data series X. Furthermore, the weight w_uneed not constrain the updated symbols to X's symbol constellation.</p><p>In conventional SLM, additional candidate symbol sequences require full (dense) transforms and/or full (dense) matrix multiplications. The number of such dense operations increases with the number of candidate sequences U, whereas in the partial update method subsequent candidate sequences can yield operations with reduced computational complexity. Dense transforms can use fast transform techniques such as IFFT, and dense matrix multiplications can use any of the generalized matrix multiplication (GEMM) techniques. Partial updates can replace the IFFT with a sparse IFFT algorithm. Since the sparse IFFT algorithm operates only on a subset of the input signal, it is not necessary to compute values for all frequencies. By exploiting this property, only a subset of frequencies are computed, thus dramatically reducing the computational complexity of the IFFT. Similarly, wavelet-based approximation IFFTs can exploit sparse inputs and compute more efficiently than conventional IFFTs. Partial updates apply GEMM to a wide variety of sparse matrix multiplications, including sparse matrix vector multiplication (SpMV), sparse matrix sparse vector multiplication (SpMSpV), and matrix sparse vector multiplication techniques that are optimized for GPU and CPU architectures. technique can be replaced. According to aspects of this disclosure, the number of dense transforms, or dense multiplications, may be independent of the constellation size and number U of candidate signals.</p><p>In some aspects, a method performed by a client-side device, an intermediate device, or a server-side device reduces the PAPR of a discrete-time signal by selecting a signal with a low PAPR from a set of multiple candidate discrete-time signals. Reduce. The method includes generating a partially updated discrete-time signal by performing a sparse reversible transform operation on a sequence of basic data symbols; and C. generating a discrete-time signal. The updated discrete-time signal is included in the set of candidate discrete-time signals. The base discrete-time signal may be generated by performing a dense reversible transform operation on the base data symbol sequence, or may be selected from previous updated discrete-time signals. The sparse reversible transform operation can be at least one of sparse IFFT, wavelet-based approximation IFFT, sparse matrix-vector multiplication, sparse matrix-sparse vector multiplication, or matrix sparse-vector multiplication. At least one additional partially updated discrete-time signal is linearly combining the first partially updated discrete-time signal with the second partially updated discrete-time signal or multiplying the partially updated discrete-time signal by a complex-valued scaling factor. , can be generated by at least one of The methods disclosed herein can be optimized to run on GPUs or CPUs.</p><p>In one aspect, the sparse reversible transform operation comprises performing a component-wise multiplication of a base symbol sequence with a sparse weight matrix to produce a sparse update symbol sequence; and performing In another aspect, the sparse lossless transform operation comprises using a sparse weight matrix to select at least one block of elements in a dense lossless transform operator to produce a sparse lossless transform operator; and b. operating on the basic symbol sequence using the transformation operator. In yet another aspect, a sparse reversible transform operation comprises selecting at least one block of elements in a dense reversible transform operator to produce a sparse reversible transform operator; Selecting elements to generate a sparse update symbol sequence; and operating on the sparse update symbol sequence using a sparse reversible transform operator.</p><p>In some aspects, an apparatus comprises means for generating a partially updated discrete-time signal by performing a sparse reversible transform operation on a sequence of basic data symbols; and means for linearly combining to generate an updated discrete-time signal. The apparatus linearly combines a first partially updated discrete-time OFDM signal with a second partially updated discrete-time OFDM signal, or multiplies the partially updated discrete-time OFDM signal by a complex-valued scaling factor. One can further include means for generating at least one additional partial update discrete time OFDM signal.</p><p>An aspect or element thereof disclosed herein is a means for performing one or more of the method steps described herein comprising (i) a hardware module, (ii) a software module or (iii) a combination of hardware and software modules, wherein any of (i)-(iii) are described herein. A software module is stored on a tangible computer-readable storage medium (or multiple such media) that implements certain techniques described herein. Aspects generally comprise a method, apparatus, system, computer program product, non-transitory computer, substantially as herein described with reference to and as illustrated by the accompanying drawings. Includes readable media, user equipment, wireless communication devices, and processing systems.</p><p>The features, properties, and advantages of the present disclosure will become more apparent from the following detailed description when read in conjunction with the drawings listed below. Like reference numerals may be used throughout the drawings and detailed description to identify like elements that appear in one or more of the drawings.</p>

<figref num="1A-1D">FIG. 2 illustrates an example transmitter in accordance with various aspects of the disclosure.</figref><figref num="2A-2D">FIG. 2 illustrates an example receiver in accordance with various aspects of the present disclosure;</figref><figref num="3">FIG. 4 depicts PAPR reduction in a multi-antenna system in accordance with various aspects of the present disclosure;</figref><figref num="4">FIG. 5 illustrates an example of weight selection for PAPR reduction in accordance with various aspects of the present disclosure;</figref><figref num="5A">FIG. 10 illustrates an example weight selector in accordance with various aspects of the disclosure.</figref><figref num="5B-5C">FIG. 2 illustrates a method for reducing PAPR in accordance with various aspects of the present disclosure;</figref><figref num="6">FIG. 2 illustrates a GPU architecture that can be optimized for signal processing functions, in accordance with various aspects of the present disclosure;</figref>

It is contemplated that elements described in one embodiment may be usefully utilized in other embodiments without specific recitation.

The detailed descriptions set forth below, in conjunction with the accompanying drawings, are intended as descriptions of various configurations and are intended to represent the only configurations that may practice the concepts described herein. It has not been. The detailed description includes specific details for the purpose of providing a thorough understanding of various concepts. However, it will be apparent to one skilled in the art that these concepts may be practiced without these specific details. In some instances, well-known structures and components are shown in block diagram form in order not to obscure such concepts.

Aspects of a telecommunications system are presented with reference to various apparatus and methods. These devices and methods are described in the following detailed description and illustrated in the accompanying drawings by various blocks, modules, components, circuits, steps, processes, algorithms, etc. (collectively referred to as "elements"). It is These elements can be implemented using electronic hardware, computer software, or any combination thereof. Whether such elements are implemented as hardware or software depends on the particular application and design constraints imposed on the overall system.

By way of example, an element, or any portion of an element, or any combination of elements, may be implemented by a "processing system" including one or more processors. Examples of processors are microprocessors, microcontrollers, digital signal processors (DSPs), field programmable gate arrays (FPGAs), programmable logic devices (PLDs), state machines, gate control logic, discrete hardware circuits, and throughout this disclosure. It includes other suitable hardware configured to perform the various functionalities described. One or more processors within the processing system may execute software. Software, whether called software, firmware, middleware, microcode, hardware description language, or otherwise, includes instructions, instruction sets, code , code segments, program code, programs, subprograms, software modules, applications, software applications, software packages, routines, subroutines, objects, executables, threads of execution, procedures, functions, etc. and

Accordingly, in one or more exemplary embodiments, the functions described may be implemented in hardware, software, firmware, or any combination thereof. If implemented in software, the functions may be stored on a non-transitory computer-readable medium or encoded as one or more instructions or code. Computer-readable media includes computer storage media. A storage media may be any available media that can be accessed by a computer. By way of example, and not limitation, such computer readable media may be RAM, ROM, EEPROM, CD-ROM or other optical disk storage devices, magnetic disk storage devices or other magnetic storage devices, or in the form of instructions or data structures. It may include any other medium that can be used to carry or store desired program code and that can be accessed by a computer.

Although particular aspects are described herein, many variations and permutations of these aspects fall within the scope of the disclosure. Although some benefits and advantages of the preferred aspects are mentioned, the scope of the disclosure is not intended to be limited to particular benefits, uses, or objectives. Rather, aspects of this disclosure are intended to be broadly applicable to a variety of wireless technologies, system configurations, networks, and transmission protocols, some of which are illustrated by way of example in the drawings and description below. ing. The detailed description and drawings are merely illustrative rather than limiting of the disclosure, the scope of which is defined by the appended claims and equivalents thereof.

FIG. 1A is a block diagram illustrating a schematic configuration of a transmitter for transmitting data to which SLM precoding is applied. The transmitter includes a baseband data processor 101, an SLM precoder 102, a transform precoder 103, a spatial mapper 104, a multiple-input multiple-output (MIMO) precoder 105, a subcarrier mapper 106, and an inverse DFT ( IDFT) module 107 , a cyclic prefix (CP) appender 108 and a digital to analog converter/radio frequency (DAC/RF) module 109 .

Baseband data processor 101 couples the original data symbols (eg, including bit sequences converted to modulation symbols) to SLM precoder 102, which provides SLM weights that reduce the PAPR of the discrete-time OFDM transmit signal. select and apply those selected weights to the original data symbols. For example, the SLM precoder 102 selects a weight matrix from the set of candidate weight matrices such that, when applied to the original data symbols, results in a discrete-time OFDM signal with the lowest PAPR value; A weighted data set can be output that includes the selected weight matrix component-wise multiplied by the data symbols. SLM precoder 102 may compute the PAPR of each discrete-time OFDM signal corresponding to each candidate weight matrix, compare this PAPR to a threshold, and then select the weight matrix that provides a PAPR below the threshold. The SLM precoder 102 outputs a weighted data set containing the selected weight matrix multiplied component by component with the original data symbols.

A transform precoder 103 performs transform precoding on the weighted data set. Transform precoder 103 may be an SC-FDMA precoder comprising one or more DFT modules. For M-point DFT, a block of M input samples is transformed into frequency-domain symbols. Spatial mapper 104 assigns at least one source of original data symbols to multiple antennas. Mapping data to each antenna (port) is called spatial mapping. Spatial mapper 104 is sometimes referred to as a layer mapper. MIMO precoder 105 applies a spatial precoding matrix, such as spatial multiplexing weights calculated from channel state information (CSI) or MIMO weights retrieved from a codebook. For example, MIMO precoder 105 performs precoding on multiple layers output by spatial (or layer) mapper 104 . A subcarrier mapper 106 maps the precoded data to appropriate (eg, scheduled) subcarriers. Subcarrier mapper 106 is sometimes referred to as a resource element mapper. Subcarrier mapper 106 may comprise multiple subcarrier mapper modules, eg, one subcarrier mapper module for each layer or antenna. The IDFT module 107 transforms the mapped frequency domain symbols into discrete time OFDM signals. The IDFT module 107 may comprise a separate IDFT for each layer or antenna. IDFT module 107 can provide an oversampled IDFT. A CP appender 108 adds CP to each discrete-time OFDM signal. DAC/RF module 109 converts the digital signal to analog and transmits the analog signal over the radio channel.

In FIG. 1B, SLM precoder 102 follows transform precoder 103, thus selecting and applying SLM weights to the transform precoded symbols. In FIG. 1C, SLM precoder 102 follows spatial mapper 104, thus selecting and applying SLM weights to the spatially mapped symbols. The SLM precoder 102 may comprise multiple SLM precoder modules, one SLM precoder module for each layer or antenna. In a distributed antenna system, an SLM precoder module resides on each radio access network node or on each antenna of the distributed antenna system if the SLM precoder 102 is located downstream from the spatial mapper 104. good too. In FIG. 1D, SLM precoder 102 follows MIMO precoder 105, thus selecting and applying SLM weights to the MIMO precoded symbols.

In some transmitter configurations, more than one SLM precoder 102 may be provided, such as multiple SLM precoders positioned at different locations within the transmitter chain. Some of the blocks depicted in the figures may be optional in the transmitter configurations disclosed herein. For example, transform precoder 103 can be optional. Spatial mapper 104 and MIMO precoder 105 can be optional. In some aspects, the transmitter is provided without transform precoder 103, spatial mapper 104, and MIMO precoder 105. It should also be appreciated that according to aspects of the present invention, transmitter configurations may be provided that include transmitter blocks not explicitly depicted herein. Transmitters used in the present invention may include encoding, bit-shifting, spreading, scrambling, and/or interleaving blocks, and operations of SLM precoder 102 may include such encoding, bit-shifting, spreading, scrambling, and/or can be configured to support interleaving and perform its function accordingly. The transmitter may include one or more additional or alternative reversible transform operations, and adapt the SLM precoder 102 accordingly to perform the operations as disclosed herein. be able to.

Referring to FIG. 2A, a receiver capable of implementing aspects of the present invention includes an RF/ADC module 201, a CP remover 202, a DFT module 203, a channel estimator/equalizer 204, a secondary It comprises a carrier demapper 205 , a spatial demultiplexer 206 , a transform decoder 207 , an SLM decoder 208 and a data symbol estimator 209 .

The RF/ADC module 201 receives the received radio signal and converts it into a digital baseband signal. CP remover 202 removes the CP of each received discrete-time OFDM signal. DFT module 203 converts (eg, demodulates) the discrete-time OFDM signal into frequency-domain symbols. A channel estimator/equalizer 204 estimates the propagation channel (eg, derives CSI) and performs frequency domain equalization. A subcarrier demapper 205 separates the frequency domain data into subcarrier data (which may correspond to various scheduled transmission channels). A spatial demultiplexer (de-MUX) 206 is optionally provided and performs all decoding on the transmitted data based on the precoding applied to the data. For example, a decoder within spatial de-MUX 206 can use codebook indices shared by the transmitter and receiver to select decoding matrices. Spatial de-MUX 206 can perform spatial demultiplexing to separate data per antenna. A transform decoder 207 performs transform decoding on the data. For example, if transform precoder 103 includes a DFT module, transform decoder 207 includes an IDFT module. The transform-decoded data symbols are processed by SLM decoder 208, which removes the SLM weights from the received data symbols.

SLM decoder 208 may receive an index (possibly a codebook index) corresponding to the selected weight matrix used by SLM precoder 102 in the transmitter. For example, the index is in a control channel (e.g., physical uplink control channel or physical uplink shared channel) derived from syndromes in the received signal or otherwise conveyed to the receiver. Can be sent as side information. The SLM decoder 208 can blindly determine the selected weight matrix. In some aspects, the SLM decoder 208 performs decoding using various possible codes or code segments until the SLM decoder identifies the selected weight matrix. SLM precoder 102 and decoder 208 may use orthogonal SLM codes. Once the SLM decoder 208 identifies the selected weight matrix, the SLM decoder removes the weights (ie, SLM sequences) from the received data. A data symbol estimator 209 determines the original data symbols from the SLM-decoded data.

Figures 2B, 2C and 2D depict receiver configurations with SLM decoder 208 positioned at various positions within the receiver chain. Such positioning corresponds to the order of operations within the corresponding transmitter. As noted above with respect to any block within the transmitter, the corresponding block within the associated receiver configuration may be optional. For example, space de-MUX 206 can be optional. Transform decoder 207 can be optional. Some receiver configurations may include more than one SLM decoder 208, eg, to provide complementary SLM processing for transmitters with multiple SLM precoders.

The transmitters and receivers disclosed herein can include client-side devices, server-side devices, and/or intermediate (eg, relay) devices. Client-side devices include UEs, access terminals, user terminals, Internet of Things (IoT) devices, wireless local area network (WLAN) devices, wireless personal area network (WPAN) devices, unmanned aerial vehicles, and intelligent transportation systems (ITS). Can contain nodes. Power efficiency as provided for uplink communication in aspects disclosed herein, since many client-side devices are battery-powered and may have limited access to computer resources and benefit from lower computational complexity. A client-side device may be configured to perform cooperative MIMO within a distributed antenna configuration with other client-side devices, relays, and/or server-side devices. MIMO precoding can come with additional challenges to power efficiency and can increase computational overhead. Client-side devices with cost, power, and/or computational processing limitations would benefit from PAPR reduction schemes with reduced computational processing.

Server-side devices may include wireless base stations, such as EnodeBs, small cells, femtocells, metro cells, remote radio heads, mobile base stations, cell towers, wireless access points, wireless communication routers, wireless hubs, network controllers. , network manager, radio access network (RAN) node, HetNet node, wireless wide area network (WWAN) node, distributed antenna system, massive MIMO node, and cluster manager. In some aspects, a server-side device may include a client device and/or a relay configured to operate in a server-side mode. Densely deploying server-side devices often comes with power, computing, and/or cost constraints. Such devices would benefit from the computationally reduced PAPR reduction schemes disclosed herein.

Intermediate devices may include fixed and/or movable relays. Intermediate devices may comprise client devices and/or server-side devices as disclosed herein. Intermediate devices may include remote radio heads with wireless backhaul and/or fronthaul. In ad-hoc, mesh, and other distributed network topologies, intermediate devices can provide increased network coverage and improved performance. Intermediate devices include mobile ad-hoc network (MANET) nodes, peer-to-peer nodes, gateway nodes, vehicle ad-hoc network (VANET) nodes, smartphone ad-hoc network (SPAN) nodes, cloud relay nodes, geographically dispersed MANET nodes, flying Including ad-hoc network (FANET) nodes, air relay nodes, and so on. Intermediate devices, whether battery-powered, solar-powered or otherwise, have limited available power. Similarly, intermediate devices may have cost constraints and/or computer processing power limitations. Such devices would benefit from the computationally reduced PAPR reduction schemes disclosed herein.

FIG. 3 is a flow diagram depicting PAPR reduction operation in a multi-antenna system. The blocks depicted in the diagrams may represent operations performed on a centralized processor, or may be distributed across multiple processors, such as in a cloud computing arrangement. The processor may reside on a network node, such as a node corresponding to multiple antennas of a server in a cooperative MIMO configuration and/or in one or more remote data centers.

One or more input data streams are number N corresponding to multiple MIMO transmission channels, such as MIMO subspace channels._tare mapped 301 to layers. Each layer 1~N_tare mapped to a plurality of N OFDM subcarrier frequencies 302.1 to 302.N, for example, according to scheduling information that allocates N subcarriers to the transmitter._tbe done. Mapping 302.1~302.N_tdivides the data symbols into N of size N_tpartitioning into individual blocks. Data selections 303.1 to 303.N are for each frequency f₁from f_N.N corresponding to_tresult in the selection of a set of data symbols. Each frequency f₁from f_N., the corresponding data symbol is the aforementioned N_tare collected from each of the blocks. The data symbols arranged in each process 303.1 to 303.N are of size N_tcan be formatted into N blocks of

frequency f₁N corresponding to_tdata symbols d(f₁) block is N_tantennas (for example, Antenna 1 to Antenna N_t) are processed for This is f_N.for each frequency up to . For simplicity, we assume that the number of transmit antennas is equal to the number of layers. However, for different antenna configurations, e.g. the number of antennas is N_tLarger configurations can be used.

The processing for Antenna 1 is to transfer the PAPR reduction weight matrix (which may contain a phase rotation sequence) to the data block d(f₁)~d(f_N.)304.1,1~304.1,N~304.N_t,1~304.N_t, N. weight matrix W₁(f₁)~W₁(f_N.) can be used for antenna 1, and W_NT(f₁)~W_NT(f_N.) is the antenna N_tcan be used for data symbol block d(f_n), the weight matrix W (indexed by antenna (j) and frequency (n))_j(f_n), each data block 304.1,1~304.1,N~304.N_t,1~304.N_t, N is<math num="3"><img file="JP7208917B2_D0003.tif" /></math>is displayed as

Each antenna (1 to N_t) for each data symbol block corresponding to<math num="4"><img file="JP7208917B2_D0004.tif" /></math>is antenna (j) and frequency (n) 305.1,1~305.1,N~305.N_t,1~305.N_t,N indexed MIMO precoding vector s_i(f_n) to produce the corresponding precoded symbol values. Therefore, for each antenna, size N_t, a set of N symbol blocks d(f_n),n=1,...,N, N precoded symbol values are generated. Each of the N precoded symbol values corresponds to a subcarrier frequency f_nblock d(f_n) of N_tcontains a linear combination of data symbols. The precoded N symbol values for each antenna are IFFT307.1~307.N_tset of input bins mapping 306.1 to 306.N_t, which gives each antenna 1 to N_tgenerates a discrete-time MIMO-OFDM signal for each.

Weight matrix W in Figure 3_j(f_n) will be described with reference to the block diagram shown in FIG. Aspects disclosed herein can be configured for centralized processing in massive MIMO antenna arrays, centralized processing in distributed antenna systems, and distributed processing in distributed antenna systems, for example. Distributed processors, as used herein, can include cloud computing networks, such as machines in a single rack, machines in multiple racks, and/or multiple geographically distributed data centers. may have selectable processors and memories distributed throughout the machine residing in the . A cloud computing network may include software-defined, selectable, and/or configurable network resources, including switches, routers, access points, gateways, and the like. Such selectable and/or configurable network resources can provide selectable and configurable access to the backhaul network. Such selectable and configurable access may include selectable bandwidth, selectable latency, selectable quality of service, and the like. A cloud computing network may comprise cooperative wireless devices that act not only as antennas but also as distributed processors in a cooperative MIMO system. Each cooperating wireless device may include processing resources (which may include cloud storage and virtual network resources) to perform at least some of the PAPR reduction operations disclosed herein. may be configured.

Data mapper 401 can map one or more input data streams to resource blocks and layers. Optionally, the data is represented by one or more weights, e.g. an initial weight set W⁽⁰⁾can be processed by a multiplier 402 configured to multiply by . Multiplier 402 may scramble the data, spread the data with any type of spreading code and/or multiple access code, and/or perform any type of transform precoding (such as SC-FDMA precoding). It may be configured to run. The data symbols output by mapper 401 or multiplier 402 are divided into multiple N_tprocessing branches, where each branch is input to N_tcorresponding to one of the antennas. Processing branches can be implemented in serial or parallel processor architectures, or combinations thereof. A processing branch may employ a centralized processor, a distributed set of processors, or a combination thereof.

A first branch is a first path via reversible transform 404.1 and generating an initial elementary discrete-time MIMO-OFDM signal, a sparse matrix multiplier 407.1 and a reversible transform 409.1, one or more and (U) a second path for generating a partially updated discrete-time MIMO-OFDM signal. Linear combiner 405.1 sums the at least one partial update discrete-time MIMO-OFDM signal with the base discrete-time MIMO-OFDM signal to generate an updated discrete-time MIMO-OFDM signal, which is the PAPR of the signal. is analyzed within the PAPR measurement module 406.1 to determine the . MIMO precoder 403.1 provides a set of MIMO precoding weights to reversible transforms 404.1 and 409.1. A similar process follows for the remaining N_tExecuted in each of -1 (physical or logical) processing branches.

Nth_t^this a reversible transform 404.N_tand a sparse matrix multiplier 407.N for generating an initial fundamental discrete-time MIMO-OFDM signal via_tand reversible transform 409.N_tand a second path for generating one or more (U) fractionally updated discrete-time MIMO-OFDM signals via . linear combiner 405.N to generate an updated discrete-time MIMO-OFDM signal_tsums the at least one partial update discrete-time MIMO-OFDM signal with the base discrete-time MIMO-OFDM signal, which is analyzed within PAPR measurement module 406.1 to measure the PAPR of the signal. MIMO Precoder 403.N_tis a reversible transform 404.N_tand 409.N_tprovides a set of MIMO precoding weights to .

N._tFor each of the branches, a description of the first branch is presented herein for clarity. Linear combiner 405.1 combines the fundamental discrete-time MIMO-OFDM signal y^(u)and/or read from memory 415.1. In one aspect, the initial basic discrete-time MIMO-OFDM signal is the only basic discrete-time MIMO-OFDM signal used in linear combiner 405.1. In other aspects, the updated discrete-time MIMO-OFDM signal can be designated as the base discrete-time MIMO-OFDM signal. PAPR measurement module 406.1 measures PAPR (e.g., PAPR^(u)) and/or update index u to memory 415.1. The index u is the weight matrix w^(u)can be the codebook index corresponding to . PAPR measurement module 406.1 stores the updated discrete-time MIMO-OFDM signal in memory, its PAPR, and the corresponding update index, e.g., in response to comparing its PAPR with a previous PAPR measurement or some threshold. be able to. The PAPR measurement module 406.1 may designate the updated discrete-time MIMO-OFDM signal with low PAPR as the base discrete-time MIMO-OFDM signal and delete any previously written data from memory 415.1. sometimes. (PAPR read from memory 415.1^(u)and possibly index u), sparse matrix multiplier 407.1 generates weight matrix W^(u)may be selected.

Stored value, e.g. u and its corresponding PAPR^(u)etc. can be read from memory 415.1 by module 406.1 and N_tPAPR aggregator 411, which is configured to collect the PAPR and weight index values (and possibly other data) from the branches. Modules 406.1~406.N in each branch_tmay communicate to aggregator 411 data corresponding to all U PAPRs, multiple PAPRs below a predetermined threshold, or a predetermined number of lowest PAPRs.

A PAPR weighting module 412 may optionally be provided to scale each PAPR with a weight value corresponding to the branch from which the weight value was received. For example, the weight may be 1 for branches with high PAPR sensitivity, and the PAPR may be 0 for branches with low PAPR sensitivity. The weighted PAPR values are then processed by weight selector 413, which can select the best set of weights for use by all branches. For example, for each index u, weight selector 413 may sum the corresponding weighted PAPR values from all branches to generate a weighted total PAPR metric. The best weight set index (0uU) can be selected from the sum of the corresponding weighted PAPR metrics with the smallest value. Weight set selector 413 then selects the best weight set index u (or corresponding weight W^(u)) are weighted 304.1, 1 to 304.1, N to 304.N_t,1~304.N_t, N to the processing branches shown in FIG.

In embodiments where PAPR weights 412 are used, each branch weight comprises a measure of the branch antenna's (or corresponding network node's) susceptibility to PAPR. For example, normalized branch weights close to 1 may correspond to high PAPR sensitivity, while normalized branch weights close to zero may correspond to low PAPR sensitivity. Battery-powered nodes may have higher branch weights than nodes with line power, as power efficiency is likely to be more important to the operation of battery-powered devices. Scheduling one or more line-powered nodes to operate in a cluster with a set of battery-powered nodes in a distributed antenna system can increase the flexibility of line-powered nodes with low branch weights. , which is advantageous because it provides a lower PAPR for battery-powered nodes. This allows weight selection 413 to yield lower PAPRs for PAPR-sensitive nodes by allowing high PAPRs for nodes that are not PAPR-sensitive.

In some aspects, the PAPR weighting module 412 calculates the battery life (battery depletion, battery charge level, percentage of full charge, device run time remaining, battery state (e.g., charging or discharge), and combinations thereof). Devices with short battery life may have corresponding branch weights higher than devices with nearly long battery life. Each branch weight may correspond to the inverse of the branch's battery charge level. The PAPR weighting module 412 determines the power scaling factor assigned to each device (e.g., a device transmitting at higher power may have a higher corresponding branch weight), the session duration assigned to each device ( For example, scheduled to have a longer session, or otherwise expected to have a longer session, such as based on the type of their data service or the size of the file they are sending. branch based on priority level (such as based on emergency or non-emergency links), subscription level, or some other metric, or a combination thereof. Weights may also be calculated. When one or more nodes with low PAPR susceptibility are scheduled to operate in a cluster with a set of nodes with high PAPR sensitivity in a distributed antenna system, the low branching weights of the nodes with low PAPR susceptibility result in free This is advantageous because it can increase the sensitivity, which allows lower PAPR for nodes with high PAPR susceptibility.

FIG. 5A is a block diagram illustrating a schematic configuration of an SLM weight selector including a first reversible transform 504, a sparse matrix multiplier 507, a second reversible transform 509, and a linear combiner 505. be. Weight selector can further include an input/output (I/O) processor 501 , a CSI estimator 510 , a memory 502 , a MIMO precoder 508 and a PAPR measurement module 506 .

A first reversible transform 504 operates on the data symbol vector X to produce an initial elementary discrete-time OFDM signal:<math num="5"><img file="JP7208917B2_D0005.tif" /></math>(In the formula,<math num="6"><img file="JP7208917B2_D0006.tif" /></math>is a reversible transformation operator). This operator<math num="7"><img file="JP7208917B2_D0007.tif" /></math>is the inverse DFT matrix F^H.can include The computational complexity of a complex N-point IFFT with oversampling factor K is (KN/2)log₂(KN) complex multiplication and KNlog₂(KN) Includes complex addition. This operator<math num="8"><img file="JP7208917B2_D0008.tif" /></math>may contain one or more additional matrix operators, which usually increase computational complexity. For example, MIMO precoder 508 can provide a set of MIMO precoding weights to reversible transform 504 . A reversible transform 504 can generate a precoding matrix S from the precoding weights and multiply it by the data symbol vector X, the product SX being F^H.:x=F^H.can be transformed by (SX).

A sparse matrix multiplier 507 uses a set of sparse weight vectors w of length N to multiply the symbol vectors X=[X₀X₁...X_N-1]^T.can do. In some aspects, an NXN diagonal weight matrix W may be used. A sparse diagonal matrix W contains diagonal elements with one or more zero values. In one aspect, the first weight matrix corresponding to the first symbol position is w^(1,0,...,0)=[1,0,...,0] and the second weight matrix corresponding to the second symbol position is w^(0,1,...,0)=[0,1,...,0],..., and also the Nth^thΝth corresponding to the symbol position of^thThe weight matrix of w^(0,0,...,1)=[0,0,...,1].

A set of sparse partial update symbol matrices (eg sequences) w^(...)X can be calculated as follows (e.g., w^(...)X is<math num="9"><img file="JP7208917B2_D0009.tif" /></math>is calculated as, where<math num="10"><img file="JP7208917B2_D0010.tif" /></math>displays element-wise multiplication). Each partial update symbol matrix is the result of a Hadamard product (also known as a Schur product, entry-wise product, or component-wise product), which is the result of two matrices of the same dimension (w^(...)and X) and another matrix (w^(...)Χ). Note that each element i, j is the product of the elements i, j of the original two matrices, i.e., (w^(...)X)_{i, j}=(w^(...))_i,j(X)_{i, j}is. It should be appreciated that variations and alternatives of this disclosure may exploit the associative, distributive, and/or commutative properties of the Hadamard product.

In some aspects, multiplication may be performed via addition or subtraction to arrive at an equivalent result. Various corresponding bit-level operations can be used to achieve the multiplication aspects disclosed herein. Multiplication can be performed by mapping the constellation points of the input symbol sequence to another set of constellation points according to the weight sequence.

The second reversible transform 509 is the operator<math num="11"><img file="JP7208917B2_D0011.tif" /></math>for each sparse matrix w^(...)Operate on X to obtain the corresponding partial update discrete-time OFDM signal x^(...)generate In one aspect, reversible transform 509 generates precoding matrix S from precoding weights received from MIMO precoder 508, then operator<math num="12"><img file="JP7208917B2_D0012.tif" /></math>to calculate This operator<math num="13"><img file="JP7208917B2_D0013.tif" /></math>is stored in memory and each sparse matrix w^(...)Can be used to operate on X. This gives the operation x^(...)=(F^H.S)(w^(...)Χ) is obtained. In another aspect, the operator<math num="14"><img file="JP7208917B2_D0014.tif" /></math>is each sparse weight matrix w^(...)can be generated for each and stored in memory. A reversible transform 509 selects a stored operator from memory, e.g., the operation x^(...)=(F^H.SW^(...)) can be operated on the data vector X to perform X. This operator is a sparse matrix and therefore can take advantage of sparse matrix vectors (spMV). In one aspect, F^H.S is computed and stored and each w^(...)every F^H.The corresponding column of S is read, followed by multiplication with X.

The operator disclosed herein can be multiplied by a scaling factor and used to obtain the scaled partial update discrete-time OFDM signal x^(...)may be generated. Linearity properties of reversible transforms can be exploited in combination with scaling factors to reduce the number of reversible transform calculations. A reversible transform 509 transforms the partial update discrete-time OFDM signal x^(...)can be stored in memory and a scaled version of such a signal can be provided to linear combiner 505 .

w^(...)The sparsity of reduces the required number of complex multiplications and additions, thus<math num="15"><img file="JP7208917B2_D0015.tif" /></math>The computational simplification results in a partially reversible transform operation. For example, w^(...)A value of zero in X causes w^(...)operator acting on X<math num="16"><img file="JP7208917B2_D0016.tif" /></math>It is possible to reduce the number of complex multiplications and additions in , compared to the total transform operations required to generate the initial elementary discrete-time OFDM signal. An updated discrete-time OFDM signal is generated by summing the partial updated discrete-time OFDM signal with the base discrete-time OFDM signal. This sum may include another KN (or less) complex additions. Similarly, the operator<math num="17"><img file="JP7208917B2_D0017.tif" /></math>is reduced in complexity by a value of zero in w(...) and is referred to herein as a partially reversible transform operation. This approach can be adapted to other linear transformation operations. For example, the operator<math num="18"><img file="JP7208917B2_D0018.tif" /></math>and its variant is w^(...)can be simplified thanks to the sparsity of , where T and S each represent any number of reversible transformation operators. T and S may include one or more operators such as spreading, precoding, permutation, block coding, space-time coding, and/or constellation mapping operators. F.^H.may include any reversible transform operator, such as wavelet transform, fractional Fourier transform, and so on.

It should be appreciated that first reversible transform 504 and second reversible transform 509 may include common structure. A reversible transform circuit, processor, and/or code segment may operate as a first reversible transform 504 that generates an initial elementary discrete-time OFDM signal using a fully reversible transform operation, and a partially reversible transform operation. can be operated as a second reversible transform 509 using to generate a partially updated discrete-time OFDM signal, each of which includes fewer multiplications and additions than the full reversible transform operation.

Partially updated discrete-time OFDM signal x generated by reversible transform 509^(...)can be stored in memory 502 for subsequent processing along with the scaling factor a. A reversible transform 509 and/or a linear combiner 505 converts the previously generated partial update discrete-time OFDM signal x^(...)by scaling and/or combining the new partial update discrete-time OFDM signal x^(...)may be generated. precomputed partial discrete-time OFDM signal x^(...)each corresponding to a different one of the N symbol positions in X are selected and multiplied by a scaling factor a to yield a new partial updated discrete-time OFDM signal x^(...)can be generated. Aspects disclosed herein can exploit the linearity of reversible transforms to provide low-complexity partial updates to OFDM signals (including spread OFDM signals and MIMO precoded OFDM signals). .

<math num="19"><img file="JP7208917B2_D0019.tif" /></math>where a and b are scalar values and<math num="20"><img file="JP7208917B2_D0020.tif" /></math>and<math num="21"><img file="JP7208917B2_D0021.tif" /></math>is a partial update discrete-time OFDM signal of length KN, and Χ₁(ω) and Χ₂(ω) is a sparse partial update symbol matrix of length N (e.g.,<math num="22"><img file="JP7208917B2_D0022.tif" /></math>and<math num="23"><img file="JP7208917B2_D0023.tif" /></math>where W₁^(...)and W₂^(...)is a sparse weight vector of length N with non-zero values corresponding to the same or different symbol positions in X).

a sparse weight vector w for which the symbol constellation of weight values is predetermined or adaptable^(...), the scaling factors a and b can be selected according to the symbol constellation and used as described above to generate the corresponding partial update discrete-time OFDM signal. For example, x^(1,0,...,0)is the sparse weight vector w^(1,0,...,0)generated by a partially reversible transformation corresponding to w^(a,0,...,0)x corresponding to^(a,0,...,0)is the product x^(a,0,...,0)=ax^(1,0,...,0)generated from Instead of performing an additional transform operation, x^{(a, 0, ..., 0)}is generated by performing no more than KN complex multiplications. A new partial-updated discrete-time OFDM signal can be generated from the sum of the partial-updated discrete-time OFDM signals. For example, a scaling factor (a+b) implementation of the previously calculated signal x^(a,0,...,0)and x^(b,0,...,0):x^{(a+b,0,...,0)}=x^(a,0,...,0)+x^(b,0,...,0), which can involve up to KN complex additions instead of transform operations.

Linear combiner 505 is configured to sum each partial updated discrete-time OFDM signal with a base discrete-time OFDM signal to generate an updated discrete-time OFDM signal. Addition of: y^(u)=y⁽⁰⁾+x^(u)(where x^(u)is the uth^this the partial update discrete-time OFDM signal of , and y⁽⁰⁾is the fundamental discrete-time OFDM signal and y^(u)is the updated discrete-time OFDM signal corresponding to index u. Linear combiner 505 outputs the value y^(u), y⁽⁰⁾, and x^(u)can be stored in memory 502 and the value y⁽⁰⁾and x^(u)can be read. Linear combiner 505 uses the new x^(u)can generate a value) is executed.

In one aspect, the first (u=0) iteration is the initial fundamental discrete-time MFMO-OFDM signal (y⁽⁰⁾) to memory. Linear combiner 505 receives y⁽⁰⁾and convert it to x^(u)can be combined with Linear combiner 505 stores the resulting sum y^(u)may be stored in memory 502.

The PAPR measurement module 506 measures y^(u)and compare it to the previous PAPR and/or at least one PAPR threshold. Based on the comparison, signal y^(u)and/or y⁽⁰⁾may be selected for further processing herein or as the signal to be transmitted. For example, a linear combiner 505 or a reversible transform 509 may be based on the PAPR (eg, the previously generated x^(u)new x^(u), and the linear combiner 505 generates a new x^(u), y⁽⁰⁾or previous y^(u)combine with In some aspects, the PAPR measurement module 506 measures y^(u)the value y to be updated in subsequent iterations⁽⁰⁾, or the PAPR measurement module 506 determines the previous value y⁽⁰⁾may be selected. The PAPR measurement module 506 retrieves values from memory (eg, x^(u),y^(u),y⁽⁰⁾) can be instructed to linear combiner 505 to read . PAPR measurement module 506 measures a value (eg, W^(u), a) and instruct the sparse matrix multiplier 507 to generate new weights.

The PAPR measurement module 506 can include a peak detector, sometimes called a peak hold circuit or full wave rectifier. A peak detector monitors the voltage and holds its peak value. A peak detector circuit tracks or follows the input voltage until an extreme point is reached and holds that value as the input decreases. This can be done in a digital circuit or processor programmed to determine local maxima from a data set corresponding to the discrete-time signal under test. A peak detector can identify the signal with the lowest peak power among the U discrete signals by finding the signal with the lowest local maximum among the LN samples. The PAPR measurement module 506 can perform algorithmic operations on the digital data to determine PAPR. Cumulative Distribution Function (CDF) or Complementary Cumulative Distribution Function (CCDF) can be used as a performance measure for PAPR. CCDF measures the PAPR of OFDM symbols with a given threshold, PAPR₀CCDF=Pr(PAPR&gt;PAPR₀) is displayed. PAPR can include peak, CDF, CCDF, and/or crest factor (the ratio of the peak value to the rms value of the waveform). Other PAPR performance measures may be used.

I/O 501 is configured to write data received from components and/or other nodes to memory 502, and read this data from memory 502 for transmission to components and/or other nodes. , may include a processor. I/O circuitry 501 may include one or more wireless (eg, radio, optical, or some other wireless technology) and/or wired (eg, cable, fiber, or some other wired line technology) A transceiver can be included. The I/O 501 can communicate the PAPR to a PAPR aggregator component (either within the node or external to the node), which is then processed for weight selection. I/O 501 can receive the selected weights (or corresponding indices) from the weight set selector and store the data in memory 502 for use by the OFDM transmitter. For example, sparse matrix multiplier 507 can read the selected weights from memory 502 . I/O501 supports baseband OFDM signals (e.g. y^(u)), and/or other data (including side information such as the index u) can be communicated to the radio transceiver circuitry for processing and transmission.

A CSI estimator 510 can measure the received pilot signals and estimate CSI therefrom. The CSI may be stored in memory 502 for use by MIMO precoder 508 and/or MIMO precoders in other nodes, from which precoding weights may be selected or generated. CSI may be used by PAPR weighting module 412 to generate PAPR scaling weights.

FIG. 5B is a flow diagram illustrating processing steps and/or program elements for performing partial updates on an OFDM signal and selecting therefrom the candidate signal with the best PAPR. The set of sparse operators (F^H.SW^(...)) are computed 511 and each a set of sparse weight matrices w^(...)corresponds to For example, the individual operator F^H.and S are the single dense operator F^H.can be computed together as S and stored in memory. dense operator F^H.S is each sparse weight matrix w^(...)are used as basis functions for the sparse operator corresponding to . a specific operator F^H.SW^(...)but F^H.SW^(...)F corresponding to nonzero blocks in^H.It is used by selecting non-zero blocks in S. For example, the weight matrix w^(...)is a column vector containing a single non-zero row element (e.g., row index n), then F^H.SW^(...)Inside, w^(...)There is a single column (eg, column n) with non-zero elements corresponding to a single non-zero row element in . So row index n and (optionally) corresponding scaling factor a_nis stored in memory as a sparse weight matrix w^(...)and the corresponding sparsity operator F^H.SW^(...)is retrieved, for example, a reversible transform operation x^(...)=(F^H.SW^(...))X to run F^H.Only the block (eg, column n) corresponding to row index n in S is searched and used to generate 512 the partially updated discrete-time OFDM signal. Unless you need to update S, F^H.The sparse operator corresponding to S can be reused by subsequent blocks of data symbols X to generate 512 therefrom the partially updated discrete-time OFDM signal.

The partial updated discrete-time OFDM signal generated at 512 for the first block of data symbols X can be stored in memory. Step 512 may further include generating additional partially updated discrete-time OFDM signals by scaling and/or linearly combining previously generated partially updated discrete-time OFDM signals. If a large symbol constellation is used for the SLM weights, step 512 can scale the partially updated discrete-time OFDM signal to generate a new partially updated discrete-time OFDM signal, so that F^H.No additional operations on S are required. The symmetry of such constellations can be exploited to reduce the number of operations. Step 512 combines the partial update discrete-time OFDM signals to obtain F^H.A new partial update discrete-time OFDM signal can be generated without requiring additional computation of S. Therefore, F^H.The number of S operations can be independent of the size of the constellation and the number U of candidate signals.

Linear combining 513 includes summing at least one partial updated discrete-time OFDM signal with a base discrete-time OFDM signal to generate a new updated (or candidate) discrete-time OFDM signal. The base discrete-time OFDM signal can be the initial base discrete-time OFDM signal or a previous updated discrete-time OFDM signal. The candidate discrete-time OFDM signals (including the base discrete-time OFDM signal) and the index u corresponding to each candidate discrete-time OFDM signal may be stored in memory.

A PAPR 514 is computed for each candidate discrete-time OFDM signal and possibly stored such that it is indexed by u. The decision process 515 includes comparing the PAPR to a threshold and/or at least one previous PAPR and possibly storing the current PAPR in memory indexed by u. A decision 515 may indicate whether to perform subsequent iterations. Decision 515 may include denoting the current candidate discrete-time OFDM signal as the base discrete-time OFDM signal to be used in subsequent iterations. Decision 515 may select to output the discrete-time OFDM signal and/or associated data (eg, weights, indices, etc.) corresponding to the best PAPR or PAPR below threshold.

Subsequent partial updates to the base signal are selected or adapted 516 if subsequent iterations are performed. Selection/adaptation 516 can control the functions of generation 512 and/or linear combination 513 . For example, based on the current PAPR (and previous PAPR), select/adapt 516 can select which partial updates to sum with the base signal and optionally which base signal to use. Select/match 516 corresponds to update n and/or a_ncan be selected. Such data-dependent updates can lead to faster convergence in some cases (eg, for stationary signals) than algorithms using data-independent update schedules. scaling factor a_nYou can choose the step size for updating to improve convergence and/or stability. A new scaled partial update discrete-time OFDM signal can be generated by scaling the previous discrete-time OFDM signal and/or by combining the discrete-time OFDM signals. The step size may be constant or variable based on one or more metrics. Conditions on the step size can be derived to yield convergence in the mean and root-mean-square sense. The step size and other parameters can be stored in memory.

FIG. 5C is a flow diagram of a method and/or computer program for performing partial updates on OFDM signals and selecting candidate signals with the best PAPR. Dense operator (F^H.S) is computed 521 and stored in memory. A dense operator can operate on a dense data matrix X to generate an initial elementary discrete-time OFDM signal. A dense operator operates 522 on the sparse data matrix to generate a partially updated discrete-time OFDM signal. A sparse data matrix is a sparse weight matrix w^(...)may be generated by setting selected values in the dense data matrix to zero, such as for zero values in . A dense data matrix X may be stored in memory. Also, the sparse data matrix (w^(...)X) is w^(...)can be provided by selecting only the non-zero elements of X that correspond to the non-zero elements in . sparse weight matrix w^(...)is the index n corresponding to each non-zero matrix element (e.g., the row index in the column vector), and optionally the nth^ththe complex value a corresponding to the value of_nmay be stored in memory as A sparse data matrix is the element X corresponding to each n from the stored X_n, then X_nor its corresponding partial update discrete-time OFDM signal, a_nmay be provided by scaling with

As in FIG. 5B, the partial updated discrete-time OFDM signal is combined 523 with the base discrete-time OFDM signal, the PAPR of the updated (candidate) discrete-time OFDM signal is calculated 524, and a decision process is performed 525. Decision 525 can include, for example, updating the base discrete-time OFDM signal, such as by designating the current or previous candidate signal as the base signal. Selection/matching 526 can operate similarly to selection/matching 516 . In some aspects, selection/fitting 526 may result in a new sparse data matrix that is computed at step 522 .

FIG. 6 is a diagram illustrating a graphics processing unit (GPU) architecture that can be optimized for the signal processing functions disclosed herein. Hardware and/or software can optimize sparse processing operations enabled by partial update methods for reducing PAPR of discrete-time OFDM signals. These partial update methods allow different optimization solutions specific to sparse processing. GPU architectures can be adapted to optimize global memory access, optimize shared memory access, and exploit reuse and parallelism. Optimizing sparse processing operations can include characterizing memory access costs, access patterns, memory types and levels, and exploiting data locality. Exploiting reuse can include caching each element in on-chip memory, and exploiting parallelism can include using parallelism without synchronization.

Aspects disclosed herein provide for optimizing sparse operations (such as sparse matrix-vector multiplication) on a graphics processing unit (GPU) using model-driven compilation and run-time strategies. can do. By way of illustration, Figure 6 depicts a GPU parallel computing architecture including N levels of streaming multiprocessors (SM) 610.1~610.N (SM 1, SM 2,..., SM N), each with a shared A memory component 612, a level of registers 614.1-614.M and a level of streaming processors (SP) 616.1-616.M (SP 1, SP 2,..., SP M), an instruction unit 618, a constant cache component 620, and a texture cache component 622. GPUs have a variety of memories available, which can be organized in a hierarchy of hybrid caches and local stores. The memories include off-chip global memory, off-chip local memory, on-chip shared memory, off-chip constant memory with on-chip cache, and off-chip texture memory with on-chip cache; on-chip registers; Off-chip device memory component 624 can include global memory and/or constant and texture memory. The GPU architecture may include or be communicatively coupled 601 to a CPU 604 and CPU memory 606, which are adapted to store computer readable instructions and data for performing the operations of CPU 604. good too. CPU 604 may be in operable communication with components of the GPU architecture, or similar components, via a bus, network, or some other communication coupling. CPU 604 may initiate and schedule processing or functions to be performed by the GPU architecture.

Shared memory 612 resides within each SM 610.1-610.N and is organized into banks. A bank conflict occurs when multiple addresses belonging to the same bank are accessed simultaneously. Each SM 610.1-610.N also has a set of registers 614.1-614.M. Constant memory and texture memory are read-only regions in the global memory space, and they have on-chip read-only caches. Although access to constant cache 620 is faster, it has only a single port and is therefore beneficial when multiple processor cores load the same value from cache. The texture cache 624 has higher latency than the constant cache 620, but is less sensitive when memory read accesses are irregular, so it is used for accessing data with two-dimensional (2D) spatial locality. is also useful for GPU computing architectures may use a Single Instruction Multiple Thread (SIMT) execution model. Kernel threads run in groups called warps, where a warp is a unit of execution. The scalar SPs in the SM share a single instruction unit, and the warp threads run on the SPs. All warp threads execute the same instructions, and each warp has its own program counter. Each thread can access memory at different levels in the hierarchy, and threads have private local memory and register spaces. Threads within a thread block can share space in shared memory. Also, the GPU's dynamic random access memory (DRAM) is accessible by all threads of the kernel.

For memory-bound applications, such as matrix-vector multiplication, it is advantageous to optimize memory performance, such as reducing the memory footprint and implementing processing strategies that better tolerate memory access latencies. A number of optimization strategies have been developed to handle the indirect and irregular memory accesses of sparse matrix-vector multiplication. SpMV-specific optimizations rely heavily on the structural properties of sparse matrices, and the problem is often formulated as if these properties are only known at runtime. However, the sparse matrices in this disclosure benefit from a well-defined structure known prior to runtime, and this structure can remain the same for many datasets. This simplifies the problem, thereby allowing a solution with improved performance. With sparse weight vectors, matrix-vector multiplication can be modeled as SpMV with a corresponding sparse operator matrix. For example, matrix elements that multiply only zero-valued vector elements can be set to zero to provide a sparse matrix. Regardless of the data symbols X and operator matrix, if the sparse weight vector w is pre-determined, the structural properties of the sparse operator matrix are known prior to run-time, allowing better hardware and software acceleration strategies. can be precisely defined.

Optimal memory access patterns also depend on how threads are mapped for computation, and the more threads involved, the more helpful it is to hide the latency of global memory accesses. also depends on the number of As a result, thread mapping schemes have been developed to ensure that memory accesses are optimized. Memory optimization may be based on the CSR format. Also, the CSR storage format can be adapted to suit the GPU architecture.

Some aspects can exploit parallel processing without synchronization. Parallelism is available across rows for SpMV computations, as opposed to allocating one thread to perform the computation corresponding to one row and a thread block to handle a set of rows. This allows the computation corresponding to a row or set of rows to be distributed across thread blocks. A useful access strategy for global memory is the hardware-optimized coalesced access pattern, where consecutive threads of a half-warp access consecutive elements. For example, if all the words requested by a half-warp thread are in the same memory segment, and if consecutive threads access consecutive words, then all half-warp memory requests are processed in one memory segment. Coalesced into memory transactions.

One strategy is to map multiple threads per row so that successive threads access successive nonzero elements of the row cyclically and compute the partial products corresponding to these nonzero elements. . Threads mapped to a row can compute the output vector element corresponding to that row from the partial products by parallel sum reduction. Partial products can be stored in shared memory because they are only accessed by threads within a thread block.

Some techniques exploit and reuse data locality. Input and output vectors may indicate data reuse in SpMV calculations. Reuse of output vector elements can be achieved by exploiting synchronization-free parallelism with optimized thread mapping, which ensures that the partial contribution to each output vector element is a specific be computed only by a set of threads, and the final value is written only once. The input vector element reuse pattern depends on the non-zero access pattern of the sparse matrix.

Exploitation of data reuse of input vector elements between threads within a thread or within a thread block can be achieved by caching the elements in on-chip memory. On-chip memory can be, for example, texture (hardware) caches, registers, or shared memory (software) caches. Caching input vector elements using registers or shared memory can include identifying portions of the vector that are being reused, which in turn reduces the identification of dense sub-blocks within a sparse matrix. become necessary. For a given set of sparse weight vectors, this information is already known. It can perform sparse matrix preprocessing to extract dense sub-blocks, and also implements a block storage format suitable for GPU architectures (e.g., enabling fine-grained thread-level parallelism) be able to. If the length of the sequence of data symbols does not change, the sub-block size remains constant. This avoids memory access penalties for reading the block size and block index, as typically required for SpMV optimizations.

Techniques described herein may include tuning configuration parameters, such as varying the number of threads per thread block used for execution and/or varying the number of threads handling rows. To achieve high parallelism and meet latency constraints, SpMV can contain multiple buffers. In one aspect, SpMV may include two sparse matrix buffers, two pointer buffers, and two output buffers. Two sparse matrix buffers are configured to buffer the sparse matrix coefficients in alternating buffer mode, and two pointer buffers are configured to buffer the pointers representing the non-zero coefficient starting positions of each column of the sparse matrix in alternating buffer mode. and the two output buffers are configured to output computation results from the other output buffer while one output buffer is used to buffer computation results in alternate buffer mode. there is

Those skilled in the art will recognize that the various illustrative logical blocks, modules, circuits, and algorithmic steps described in connection with the present disclosure may be implemented as electronic hardware, computer software, or a combination of both. You will realize more of what you can do. To clearly illustrate this interchangeability of hardware and software, various illustrative components, blocks, modules, circuits and steps have been described above largely in terms of their functionality. Whether such functionality is implemented as hardware or software depends on the particular application and design constraints imposed on the overall system. Skilled artisans may implement the described functionality in varying ways for each particular application, but such implementation decisions do not cause a departure from the scope of the present disclosure. shall not be construed as causing

The various exemplary logic blocks, modules, and circuits described in connection with this disclosure are general purpose processors, digital signal processors (DSPs), application specific integrated circuits (ASICs), field programmable gate arrays (FPGA) or other programmable logic device, discrete gate or transistor logic, discrete hardware components, or any combination thereof designed to perform the functions described herein can do. A general-purpose processor may be a microprocessor, but, in the alternative, the processor may be any conventional processor, controller, microcontroller, or state machine. A processor may be implemented as a combination of computing devices, such as a DSP and microprocessor combination, multiple microprocessors, one or more microprocessors cooperating with a DSP core, or any other such configuration. is also good.

The steps of the methods or algorithms described in connection with the disclosure herein can be embodied directly in hardware, in software modules executed by a processor, or in a combination of the two. A software module may reside in RAM memory, flash memory, ROM memory, EPROM memory, EEPROM memory, registers, hard disk, a removable disk, a CD-ROM, or any other form of storage medium known in the art. can. An exemplary storage medium is coupled to the processor such that the processor can read information from, and write information to, the storage medium. In the alternative, the storage medium may be embedded within the processor. The processor and storage medium may reside within the ASIC. ASICs may reside on the client side, server side, and/or intermediate devices. Alternatively, the processor and storage medium may reside as discrete components in the client-side, server-side, and/or intermediate devices.

In one or more exemplary designs, the functions described may be implemented in hardware, software, firmware, or any combination thereof. If implemented in software, the functions may be stored on or transmitted over a computer-readable medium as one or more instructions or code. Computer-readable media includes both computer storage media and communication media including any medium that facilitates transfer of a computer program from one place to another. A storage media may be any available media that can be accessed by a general purpose or special purpose computer. By way of example, and not limitation, such computer readable media may include RAM, ROM, EEPROM, CD-ROM or other optical disk storage, magnetic disk storage or other magnetic storage devices, or any desired program code means for executing instructions. or any other medium that can be used to carry or store data in the form of a data structure and that can be accessed by a general or special purpose computer or processor. can. Also, any connection is properly termed a computer-readable medium. For example, the Software uses coaxial cable, fiber optic cable, twisted pair, Digital Subscriber Line (DSL), or wireless technologies such as infrared, radio, and microwave from a website, server, or other remote source. This coaxial cable, fiber optic cable, twisted pair, DSL, or wireless technologies such as infrared, radio, and microwave are included in the definition of medium when transmitted over this medium. Combinations of the above should also be included within the scope of computer-readable media. As used herein, including in the claims, "at least one of