METHOD FOR WIRELESS X2X ACCESS AND RECEIVERS FOR LARGE MULTIDIMENSIONAL WIRELESS SYSTEMS

Abstract

Estimating transmit symbol vectors transmitted in an overloaded communication channel includes receiving a signal represented by a received signal vector, the received signal vector corresponding to a superposition of signals representing transmitted symbols selected from a constellation of symbols and transmitted from one or more transmitters.

Claims

1. A computer-implemented receiver method of estimating transmit symbol vectors transmitted in an overloaded communication channel that is characterized by a channel matrix of complex coefficients, the method including: receiving, in a receiver, a signal represented by a received signal vector, the received signal vector corresponding to a superposition of signals representing transmitted symbols selected from at least one constellation of symbols and transmitted from one or more transmitters, defining a search space in a convex domain including at least a differentiable and convex function in a closed form of the received signal vector and of transmit symbol vectors for all symbols of the at least one constellation, obtaining the differentiable and convex function in a closed form by changing the first optimization formulation given by a first function into a second optimization formulation given as a second function by applying a quadratic approximation of l.sub.o-Norm given as third function and after obtaining the second function a fourth function is calculated, and applying an iterative procedure to find the optimal solution for the estimation of transmitting symbols is performed.

2. The method of claim 1, wherein differentiable and convex function in a closed form of the received signal vector and of transmit symbol vectors is obtained by applying the setting of the Wingerts derivative of the fourth function.

3. The method of claim 1, wherein the optimal solution calculated via a matrix multiplication for the fixed elements of the second function.

4. A computer-implemented receiver method of estimating transmit symbol vectors transmitted in an overloaded communication channel that is characterized by a channel matrix of complex coefficients, the method including: receiving, in a receiver, a signal represented by a received signal vector, the received signal vector corresponding to a superposition of signals representing transmitted symbols selected from at least one constellation of symbols and transmitted from one or more transmitters, defining a search space in a convex domain including at least closed-form solution providing s and penalty parameter λ fifth function of the received signal vector and of transmit symbol vectors for all symbols of the at least one constellation, obtaining a closed-form fifth function providing s and penalty parameter λ by changing the first optimization formulation given as a sixth function, which is a real-valued quadratically constrained quadratic program version of a seventh function, which is recalculated into a generalized eigenvalue formulation and the Möbus transformed function, applying an iterative procedure to find the optimal solution for the estimation of transmitting symbols is performed.

5. The method of claim 1, wherein within the iterative procedure the coefficients β's, which are given in terms on the estimate solution s, the constellation alphabet, and the tightening parameter α are determined.

6. The method of claim 1, wherein an incrementation of the iteration number i of the iterative procedure is proceeded.

7. The method of claim 1, wherein the calculation of solution variation d using the Euclidian distance between the solution of the current and previous iteration is proceeded.

8. The method of claim 1, wherein the convergence criteria is controlled in a way, if d<e or the maximum number of iterations has been reached, the iteration is terminated and the solution of the solution of the estimated transmitted vector s is determined and created.

9. A receiver of a communication system having a processor, volatile and/or non-volatile memory, at least one interface adapted to receive a signal in a communication channel, wherein the non-volatile memory stores computer program instructions which, when executed by the microprocessor, configure the receiver to estimate transmit symbol vectors transmitted in an overloaded communication channel that is characterized by a channel matrix of complex coefficients operations by performing operations comprising: receiving in a receiver, a signal represented by a received signal vector, the received signal vector corresponding to a superposition of signals representing transmitted symbols selected from at least one constellation of symbols and transmitted from one or more transmitters, defining a search space in a convex domain including at least a differentiable and convex function in a closed form of the received signal vector and of transmit symbol vectors for all symbols of the at least one constellation, obtaining the differentiable and convex function in a closed form by changing the first optimization formulation given by a first function into a second optimization formulation given as a second function by applying a quadratic approximation of l.sub.o-Norm given as third function and after obtaining the second function a fourth function is calculated; and applying an iterative procedure to fin the optimal solution for the estimation of transmitting symbols is performed.

10. (canceled)

11. (canceled)

12. The receiver of claim 9, wherein differentiable and convex function in a closed form of the received signal vector and of transmit symbol vectors is obtained by applying the setting of the Wingerts derivative of the fourth function.

13. The receiver of claim 9, wherein the optimal solution calculated via a matrix multiplication for the fixed elements of the second function.

14. The receiver of claim 9, wherein an Incrementation of the iteration number i of the iterative procedure is proceeded.

15. The receiver of claim 9, wherein the calculation of solution variation d using the Euclidian distance between the solution of the current and previous iteration is proceeded.

16. The receiver of claim 9, wherein the convergence criteria is controlled in a way, if d<e or the maximum number of iterations has been reached, the iteration is terminated and the solution of the solution of the estimated transmitted vector s is determined and created.

17. A receiver configured for estimating transmit symbol vectors transmitted in an overloaded communication channel that is characterized by a channel matrix of complex coefficients, by performing operations including: receiving, in a receiver, a signal represented by a received signal vector, the received signal vector corresponding to a superposition of signals representing transmitted symbols selected from at least one constellation of symbols and transmitted from one or more transmitters, defining a search space in a convex domain including at least closed-form solution providing s and penalty parameter λ fifth function of the received signal vector and of transmit symbol vectors for all symbols of the at least one constellation, obtaining a closed-form fifth function providing s and penalty parameter λ by changing the first optimization formulation given as a sixth function, which is a real-valued quadratically constrained quadratic program version of a seventh function, which is recalculated into a generalized eigenvalue formulation and the Möbus transformed eighth function, and applying an iterative procedure to find the optimal solution for the estimation of transmitting symbols is performed.

18. The receiver of claim 17, wherein within the iterative procedure the coefficients β's, which are given in terms on the estimate solution s, the constellation alphabet, and the tightening parameter α are determined.

19. The receiver of claim 17, wherein the optimal solution calculated via a matrix multiplication for the fixed elements of the second function.

20. The receiver of claim 17, wherein a Incrementation of the iteration number i of the iterative procedure is proceeded.

21. The receiver of claim 17, wherein the calculation of solution variation d using the Euclidian distance between the solution of the current and previous iteration is proceeded.

22. The receiver of claim 17, wherein the convergence criteria is controlled in a way, if d<e or the maximum number of iterations has been reached, the iteration is terminated and the solution of the solution of the estimated transmitted vector s is determined and created.

Description

BRIEF DESCRIPTION OF THE DRAWINGS

[0042] The invention will be further explained with reference to the drawings in which

[0043] FIG. 1 shows a simplified schematic representation of orthogonal multiple access to a shared medium,

[0044] FIG. 2 shows a simplified schematic representation of non-orthogonal access to a shared medium,

[0045] FIG. 3 shows an exemplary generalized block diagram of a transmitter and a receiver that communicate over a communication channel,

[0046] FIG. 4 shows an exemplary flow diagram of method steps implementing embodiments 4 of the present invention,

[0047] FIG. 5 shows details of method steps of the embodiments 4 of the present invention,

[0048] FIG. 6 shows exemplary and basic examples of a constellation, a transmitted and a received signal,

[0049] FIG. 7 shows a simplified exemplary graphical representation of the third function determined in accordance with the present invention, that can be effectively solved using fractional programming.

[0050] FIG. 8 shows an exemplary flow diagram of core method steps implementing embodiments 1 of the present invention of the receiver method 3,

[0051] FIG. 9 shows an exemplary flow diagram of method steps implementing embodiments 1 of the present invention of the receiver method 3,

[0052] FIG. 10 shows an exemplary flow diagram of core method steps implementing embodiments 2 of the present invention,

[0053] FIG. 11 shows an exemplary flow diagram of method steps implementing embodiments 2 of the present invention,

[0054] FIG. 12 shows an exemplary flow diagram of core method steps implementing embodiments 3 of the present invention,

[0055] FIG. 13 shows an exemplary flow diagram of method steps implementing embodiments 3 of the present invention.

DETAILED DESCRIPTION

[0056] In the following, the general theoretical base of the inventive receiver methods will be explained with reference to an exemplary underdetermined wireless system with N.sub.T transmitters and N.sub.R<N.sub.T receive resources, such that the overloading ratio of the system is given by y=N.sub.T/N.sub.R and the received signal, after well-known signal realization, can be modelled as

[00001]$\begin{array}{cc}y=\mathrm{Hs}+n& \left(1\right)\end{array}$$\mathrm{where}$$\begin{array}{ccc}H\stackrel{△}{=}\left[\begin{array}{cc}\mathrm{Re}\left\{H\right\}& -\mathrm{Im}\left\{H\right\}\\ \mathrm{Im}\left\{H\right\}& \mathrm{Re}\left\{H\right\}\end{array}\right],& s\stackrel{△}{=}\left[\begin{array}{c}\mathrm{Re}\left\{s\right\}\\ \mathrm{Im}\left\{s\right\}\end{array}\right],& n\stackrel{△}{=}\left[\begin{array}{c}\mathrm{Re}\left\{n\right\}\\ \mathrm{Im}\left\{n\right\}\end{array}\right],\end{array}$

[0057] s=[s.sub.1, . . . sN.sub.T].sup.T ∈.sup.N.sup.T is a transmit symbol vector with each element sampled from a constellation set C of cardinality 2.sup.b, with b denoting the number of bits per symbol, n ∈.sup.N.sup.R.sup.×1 is a circular symmetric complex additive white Gaussian noise (AWGN) vector with zero mean and covariance matrix σ.sub.n.sup.2I.sub.N.sub.R, and H ∈.sup.N.sup.R.sup.×N.sup.T describes a flat fading channel matrix between the transmitter and receiver sides.

[0058] In conventional detectors a ML detection may be used for estimating a transmit signal vector s.sup.ML for a received signal y. The ML detection requires determining the distances between the received signal vector y and each of the symbol vectors s of the symbols c.sub.i of the constellation C. The number of calculations exponentially increases with the number N.sub.T of transmitters.

[0059] The discreteness of the target set to the ML function prevents using effective FP algorithms, which are known to be effective for finding minima in functions having continuous input, for estimating the transmit signal vector ŝ for a received signal y.

[0060] In accordance with the present invention the discrete target set for the ML function is first transformed into a sufficiently similar continuous function, which is open to solving through FP algorithms.

[0061] To this end, the alternative representation of the discrete ML function

[00002]$\begin{array}{cc}{s}^{\mathrm{ML}}=\underset{s\in {ℝ}^{2N_t}}{\mathrm{argmin}}{.Math.y-\mathrm{Hs}.Math.}_2^2& \left(2a\right)\end{array}$$s.t.$$\begin{array}{cc}\stackrel{2^{\frac{b}{2}}}{\underset{i=1}{.Math.}}{.Math.s-x_{i}1.Math.}_0=2N_T.Math.\left(2^{\frac{b}{2}}-1\right)& \left(2b\right)\end{array}$

[0062] is first transformed into a penalized mixed l.sub.0-l.sub.2 minimization problem that retains ML-like performance for the approximation of the constraint:

[00003]$\begin{array}{cc}{\tilde{s}}^{\mathrm{ML}}=\underset{s\in {ℝ}^{2N_t}}{\arg \min }\underset{i=1}{\overset{2^{\frac{b}{2}}}{.Math.}}{w}_i{.Math.s-x_{i}1.Math.}_0+\lambda {.Math.y-\mathrm{Hs}.Math.}_2^2& \left(3\right)\end{array}$$\mathrm{Function}7$

[0063] where w.sub.i and λ are weighting parameters. The notation {tilde over (s)}.sup.ML indicates that the approximation still has the potential to achieve near-ML performance, as long as the weights w.sub.i and λ are properly optimized. N.sub.T is the number of transmitters and may also be referred to by N.sub.T. Furthermore we name equation 2 as function 7.

[0064] Aiming to tackle the intractable non-convexity of l.sub.0-norm in the novel reformulation of the ML detection without resorting to the l.sub.1-norm, it proves convenient to first introduce two different techniques. The former is an adoptable approximation of the l.sub.0-norm function,

[00004]$\begin{array}{cc}{.Math.x.Math.}_0=\underset{\alpha .fwdarw.0^{+}}{\lim }\underset{j=1}{\overset{N}{.Math.}}\frac{.Math.x_j.Math.}{.Math.x_j.Math.+\alpha }=N-\underset{\alpha .fwdarw.0^{+}}{\lim }\underset{j=1}{\overset{N}{.Math.}}\frac{\alpha }{.Math.x_j.Math.+\alpha }=\underset{\alpha .fwdarw.0^{+}}{\lim }\underset{j=1}{\overset{N}{.Math.}}\frac{{.Math.x_j.Math.}^2}{{.Math.x_j.Math.}^2+\alpha }=N-\underset{\alpha .fwdarw.0^{+}}{\lim }\underset{j=1}{\overset{N}{.Math.}}\frac{\alpha }{{.Math.x_j.Math.}^2+\alpha }& \left(9\right)\end{array}$$\mathrm{Function}9$

[0065] where x is an arbitrary sparse vector of length N. Notice that unlike the relaxation by l.sub.1-norm substitution, the expression in equation (9) can be made arbitrarily tight by making a sufficiently small. On the other hand, the latter technique, referred to as quadratic transform (QT) is a transformation to solve an optimization problem involving sum of-ratio non-convex functions. While several methods such as the Taylor series approximation and the semidefinite relaxation (SDR) are known for the transformation of non-convex ratios functions in the past decade, the QT has shown superior performance in different optimization setups and wide applicability due to its tractable expression. Consider a generic maximization problem with a sum of ratios as objective, such as

[00005]$\begin{array}{cc}\underset{x}{\max }\underset{m=1}{\overset{M}{.Math.}}{a}_m^H\left(x\right)B_m^{-1}\left(x\right)a_m\left(x\right)& \left(10a\right)\end{array}$$\begin{array}{cc}s.t.x\in 𝒳& \left(10b\right)\end{array}$

[0066] where a.sub.m (x) denotes an arbitrary complex vector function, B.sub.m (x) is an arbitrary symmetric positive definite matrix, and x is a variable to be optimized in a constraint set .

[0067] In the sequel, we propose QT-based several novel receiver method 1 to 4 via the flexible l.sub.0-norm approximation given in equation (9), aiming at the bit error rate (BER) performance asymptotically close to the optimal ML detection while

[0068] General Theoretical Base for Receiver Method 1 (DAFZF)

[0069] It might be a practical bottleneck to compute a large number of iterations since the maximal number of iterations is not determined for known solutions while guaranteeing convergence. Motivated by the this, we therefore tackle equation/function (7) with the aim of reducing the algorithmic complexity as much as possible, proposing a new simple iterative algorithm/method with a closed-form solution to equation/function (7). To this end, we combine the quadratic approximation of the l.sub.0-norm, resulting in

[00006]$\begin{array}{cc}\begin{array}{c}\left(P3\right)\Leftarrow \{{\tilde{s}}^{\mathrm{ML}}=\underset{s\in {ℂ}^{N_T}}{\arg \min }\underset{i=1}{\overset{2^b}{.Math.}}{w}_i{.Math.s-c_{i}1.Math.}_0+\lambda {.Math.y-\mathrm{Hs}.Math.}_2^2\\ \approx \underset{s\in {ℂ}^{N_T}}{\arg \min }{s}^H\hat{B}s-2Re\left\{{\hat{b}}^{H}s\right\}+\lambda {.Math.y-\mathrm{Hs}.Math.}_2^2\\ =\underset{s\in {ℂ}^{N_T}}{\arg \min }{s}^H\underset{\underset{\stackrel{△}{=}f\left(s\right)}{︸}}{\left(\hat{B}+\lambda H^{H}H\right)s-2Re\left\{\left({\hat{b}}^H+\lambda y^{H}H\right)s\right\}}\end{array}& \left(35\right)\end{array}$$\mathrm{Function}35$$\mathrm{where}\hat{B}=\underset{i=1}{\overset{2^b}{.Math.}}{w}_i\mathrm{diag}\left({\beta }_{i,1}^2,{\beta }_{i,2}^2,.Math.,{\beta }_{i,N_t}^2\right)\mathrm{and}\hat{b}=\underset{i=1}{\overset{2^b}{.Math.}}{w}_i{c_i\left[{\beta }_{i,1}^2,{\beta }_{i,2}^2,.Math.,{\beta }_{i,N_t}^2\right]}^T$

[0070] One may notice that the above penalized minimization problem in (35) is a simple convex quadratic minimization, which can be efficiently solved by taking Wirtinger derivatives with respect to s* that is,

[00007]$\begin{array}{cc}\frac{\partial f\left(s\right)}{\partial s^{*}}=\left(\hat{B}+\lambda H^{H}H\right)s-\left(\hat{b}+\lambda H^{H}y\right)=0,& \left(36\right)\end{array}$ [0071] which yields

s.sup.opt=({circumflex over (B)}+λH.sup.HH).sup.−1({circumflex over (b)}+λH.sup.Hy).  (37)

[0072] The simple and closed-form solution in equation (37) enables us to compute the optimal s.sup.opt via only one matrix multiplication for a fixed B. Given the above, a pseudo code developed is illustrated.

[0073] Input y: Received signal vector; [0074] H: Measurement compressive matrix: [0075] λ: Balancing parameter; [0076] α: Tightening parameter for l.sub.0-norm approximation; [0077] i.sub.max: Maximum number of iterations [0078] ε: Iteration stop criterion

[0079] 1 Set iteration counter i=0;

[0080] 2 Generate uniformly distributed initial signal vector s.sup.(i);

[0081] 3 repeat:

[00008]${\beta }_{i,j}=\frac{\sqrt{\alpha }}{{\left(s_j-x_i\right)}^2+\alpha };$

[0082] 8 until δ<ε or reach the maximum iteration i.sub.max;

[0083] General theoretical base for Receiver Method 2 (DAGED)

[0084] It can be noticed that as pointed out Receiver Method 3 and 1 have tackled the two different bottlenecks of Receiver Method 4, respectively. In other words, the ADMM-based approach in Receiver Method 3, described later, has been proposed to be a standalone method, in which the time efficiency might be limited due to the unlimited iterative mechanism, whereas Receiver Method 1 has rather aimed to improve the time efficiency by avoiding the iterative inner loop, imposing optimization of the penalty parameter λ before running the algorithm. Considering the above, in this subsection we therefore propose a non-iterative, in the sense of avoiding the inner loop, and stand-alone approach for equation (6) based on the generalized eigenvalue problem. Recalling equation (6), it can be formulated as a real-valued QCQP-1, that is,

[00009]$\begin{array}{cc}\left(P4\right)\Leftarrow \{\underset{s\in {ℝ}^{2N_t}}{\arg \min }{s}^T{G}_{H}s-2y^T\mathrm{Hs}& \left(38\right)\end{array}$$\begin{array}{cc}s.t.g\left(s\right)=s^T{G}_{B}s-2v^{T}s+K\le 0& \left(39\right)\end{array}$$\mathrm{Function}38$$\begin{array}{cc}\mathrm{where}{G}_H=H^{T}H{G}_B={.Math.}_{i=1}^{2^{\frac{b}{2}}}\mathrm{diag}\left({\beta }_{i,1}^2,{\beta }_{i,2}^2,.Math.,{\beta }_{i,2N_t}^2\right)\mathrm{and}v=\underset{i=1}{\overset{2^{\frac{b}{2}}}{.Math.}}{x_i\left[{\beta }_{i,1}^2,{\beta }_{i,2}^2,.Math.,{\beta }_{i,2N_t}^2\right]}^T& \left(39\right)\end{array}$ [0085] with now

[00010]${\beta }_{i,j}=\frac{\sqrt{\alpha }}{{\left(s_j-x_i\right)}^2+\alpha }\mathrm{and}K={.Math.}_{i=1}^{2^{\frac{b}{2}}}{.Math.}_{j=1}^{2N_t}{\beta }_{i,j}^2\left(x_i^2+\alpha \right)-2{\beta }_{i,j}\sqrt{\alpha }+2N_t$

[0086] Given the More's theorem, assuming that the Slater's condition is satisfied, namely, there exists at least one feasible solution satisfying constraint (38b), s.sup.opt is the global solution to equation (38) if and only if there exist μ.sup.opt≥0 such that

[00011]$\begin{array}{cc}\left(G_H+{\mu }^{\mathrm{opt}}{G}_B\right)s^{\mathrm{opt}}=\left(H^{T}y+{\mu }^{\mathrm{opt}}v\right)& \left(40a\right)\end{array}$$\begin{array}{cc}g\left(s^{\mathrm{opt}}\right)\le 0& \left(40b\right)\end{array}$$\begin{array}{cc}{\mu }^{\mathrm{opt}}g\left(s^{\mathrm{opt}}\right)=0,& \left(40c\right)\end{array}$

[0087] which yield

(G.sub.H+μ.sup.optG.sub.B)s.sup.opt=(H.sup.Ty+μ.sup.optv)  (41a)

g(s.sup.opt)=0,  (41b) [0088] or equivalently

[00012]$\begin{array}{cc}\{\begin{array}{c}K\theta -v^T{z}_1+{\left(H^{T}y+{\mu }^{\mathrm{opt}}v\right)}^T{z}_2=0\\ -v\theta +G_B{z}_1-\left(G_H+{\mu }^{\mathrm{opt}}{G}_B\right)z_2=0\\ \left(H^{T}y+{\mu }^{\mathrm{opt}}v\right)\theta -\left(G_H+{\mu }^{\mathrm{opt}}{G}_B\right)z_1=0\end{array}\mathrm{where}{s}^{\mathrm{opt}}=\frac{z_1}{\theta }& \left(42\right)\end{array}$

[0089] One may readily notice that the simultaneous equations in (42) can be rewritten as a generalized eigenvalue problem, namely,

[00013]$\begin{array}{cc}{M}_0+{\mu }^{\mathrm{opt}}{M}_1=\left[\begin{array}{ccc}K& -v^T& {\left(H^{T}y+{\mu }^{\mathrm{opt}}v\right)}^T\\ -v& G_B& -\left(G_H+{\mu }^{\mathrm{opt}}{G}_B\right)\\ \left(H^{T}y+{\mu }^{\mathrm{opt}}v\right)& -\left(G_H+{\mu }^{\mathrm{opt}}{G}_B\right)& 0_{2N_t}\end{array}\right]z=0& \left(43\right)\end{array}$$\mathrm{Function}43$$\mathrm{where}{M}_0=\left[\begin{array}{ccc}K& -v^T& y^{T}H\\ -v& G_B& -G_H\\ H^{T}y& -G_H& 0_{2N_t}\end{array}\right]\mathrm{and}{M}_1=\left[\begin{array}{ccc}0& 0_{1\times 2N_t}& v^T\\ 0_{2N_t\times 1}& 0_{2N_t}& -G_B\\ v& -G_B& 0_{2N_t}\end{array}\right]$

[0090] It proves convenient to apply a Möbius transformation to the matrix pencil in equation (43), resulting in the following inverted matrix pencil

[00014]$\begin{array}{cc}\left(M_1+{\xi }^{\mathrm{opt}}{M}_0\right)z=0,& \left(44\right)\end{array}$$\mathrm{Function}44$$\mathrm{where}{\xi }^{\mathrm{opt}}=\frac{1}{{\mu }^{\mathrm{opt}}}.$

[0091] For the transformed generalized eigenvalue problem in equation (44), it has been shown that the optimal ξ.sup.opt is the largest real finite generalized eigenvalue of the matrix pencil (44). Notice that the Mobius transformation technique enables us to avoid calculating the smallest real positive eigenvalue due to the well-known fact that computing the smallest eigenvalue may be inaccurate compared with the largest one. Given all the above, we summarize our method 4 as a pseudo code.

[0092] Input y: Received signal vector; [0093] H: Measurement compressive matrix: [0094] λ: Balancing parameter; [0095] α: Tightening parameter for l.sub.0-norm approximation; [0096] i.sub.max: Maximum number of iterations [0097] ε: Iteration stop criterion

[0098] 1 Set iteration counter i=0;

[0099] 2 Generate uniformly distributed initial signal vector s.sup.(i);

[0100] 3 repeat:

[00015]${\beta }_{i,j}=\frac{\sqrt{\alpha }}{{\left(s_j-x_i\right)}^2+\alpha };$

[0101] 8 until δ<ε or reach the maximum iteration i.sub.max;

[0102] General theoretical base for Receiver Method 3 (DAPZF)

[0103] In order to improve the aforementioned receiver methods 3 overcomes the problem of the predefinition/optimization before running of receiver method 4. The suggested first step to obtaining a lower-complexity and stand-alone alternative to Receiver Method 4 is to recognize that the l.sub.0-norm regularizer can be reformulated into a simple quadratic function with the aid of equation (9) and the QT technique. Plugging the second line of equation (9) into equation (5). The obtained result is:

[00016]$\begin{array}{cc}\left(P2\right)\Leftarrow \{\underset{s\in {ℂ}^{N_t}}{\arg \min }{.Math.y-\mathrm{Hs}.Math.}_2^2& \left(18a\right)\end{array}$$\begin{array}{cc}s.t.N_t-\underset{i=1}{\overset{2^b}{.Math.}}\underset{j=1}{\overset{N_t}{.Math.}}\frac{\alpha }{{.Math.s_j-c_i.Math.}^2+\alpha }\le 0,& \left(18b\right)\end{array}$ [0104] with a«1 and the identity

[00017]$\begin{array}{cc}{.Math.s-c_{i}1.Math.}_0\ge N_t-\underset{j=1}{\overset{N_t}{.Math.}}\frac{\alpha }{{.Math.s_j-c_i.Math.}^2+\alpha }.& \left(19\right)\end{array}$

[0105] Since equation (18b) is a differentiable concave-over-convex function with respect to s, QT can be directly applied to the above constraint, resulting in

[00018]$\begin{array}{cc}\underset{s\in {ℂ}^{N_t}}{\arg \min }{.Math.y-\mathrm{Hs}.Math.}_2^2& \left(20a\right)\end{array}$$\begin{array}{cc}s.t.N_t-\underset{i=1}{\overset{2^b}{.Math.}}\underset{j=1}{\overset{N_t}{.Math.}}\left(-{\beta }_{i,j}^2{.Math.s_j.Math.}^2+2{\beta }_{i,j}^2\mathrm{Re}\left\{c_i{s}_j^{*}\right\}-{\beta }_{i,j}^2\left({.Math.c_i.Math.}^2+\alpha \right)+2{\beta }_{i,j}\sqrt{\alpha }\right)\le 0,\mathrm{where}{\beta }_{i,j}=\frac{\sqrt{\alpha }}{{.Math.s_j-c_i.Math.}^2+\alpha }& \left(20b\right)\end{array}$

[0106] For further simplification and tractability, the constraint in equation (20b) can be reformulated in a matrix form as follows:

[00019]$\begin{array}{cc}\underset{i=1}{\overset{2^b}{.Math.}}\underset{j=1}{\overset{N_t}{.Math.}}{\beta }_{i,j}^2{.Math.s_j.Math.}^2-2\underset{i=1}{\overset{2^b}{.Math.}}\underset{j=1}{\overset{N_t}{.Math.}}Re\left\{{\beta }_{i,j}^2{c}_i{s}_j^{*}\right\}+\underset{i=1}{\overset{2^b}{.Math.}}\underset{j=1}{\overset{N_t}{.Math.}}\stackrel{\stackrel{\Delta }{=}\delta }{\overbrace{{\beta }_{i,j}^2\left({.Math.c_i.Math.}^2+\alpha \right)-2{\beta }_{i,j}\sqrt{\alpha }+N_t\le 0}}& \left(21\right)\end{array}$$\begin{array}{cc}\iff \underset{\mathrm{Convex}\mathrm{quadratic}\mathrm{function}ins}{\underbrace{s^H\mathrm{Bs}-2Re\left\{b^{H}s\right\}+\delta \le 0}}\mathrm{where}B=\underset{i=1}{\overset{2^b}{.Math.}}\mathrm{diag}\left({\beta }_{i,1}^2,{\beta }_{i,2}^2,.Math.,{\beta }_{i,N_t}^2\right)⪰0\mathrm{And}b=\underset{i=1}{\overset{2^b}{.Math.}}{c_i\left[{\beta }_{i,1}^2,{\beta }_{i,2}^2,.Math.,{\beta }_{i,N_t}^2\right]}^T& \left(22\right)\end{array}$

[0107] Considering the above, equation (18) can be rewritten as a convex QCQP-1, that is,

[00020]$\begin{array}{cc}\underset{s\in {ℂ}^{N_t}}{\arg \min }{.Math.y-\mathrm{Hs}.Math.}_2^2& \left(23a\right)\end{array}$$\begin{array}{cc}s.t.s^H\mathrm{Bs}-2Re\left\{b^{H}s\right\}+\delta \le 0& \left(23b\right)\end{array}$

[0108] which can be equivalently rewritten as

[00021]$\begin{array}{cc}𝒬C𝒬P-2=1\Leftarrow \{\underset{s\in {ℂ}^{N_t}}{\arg \min }{s}^H{H}^H\mathrm{Hs}-2Re\left\{y^H\mathrm{Hs}\right\}& \left(24a\right)\end{array}$$\begin{array}{cc}s.t.s^H\mathrm{Bs}-2Re\left\{b^{H}s\right\}+\delta \le 0.& \left(24b\right)\end{array}$

[0109] Although the above QCQP-1 in equation (24) can be efficiently solved via interior point method by using numerical convex solvers, we remark that such black-box dependent algorithms often lead to not only an impractical in real-world implementation but also time inefficient solution for relatively large-scale problems. To efficiently solve the latter problem, the ADMM is leveraged below. ADMM algorithm has been invented to solve convex problems of the type

[00022]$\begin{array}{cc}\underset{x,s}{\mathrm{minimize}}f\left(x\right)+g\left(s\right)& \left(25a\right)\end{array}$$\begin{array}{cc}s.t.D_{s}s+D_{x}x-c=0& \left(25b\right)\end{array}$

[0110] where f(x): C.sup.n.fwdarw.R and g(s): C.sup.n.fwdarw.R are closed, proper and convex functions with complex inputs x ∈ C.sup.n and s ∈ C.sup.n, respectively. D.sub.x∈R.sup.n×n and D.sub.s∈R.sup.n×n denote arbitrary matrices and c ∈R.sup.n is an arbitrary vector. Although in the above ADMM problem no assumption on finiteness and differentiability of ƒ(x) and g(z) has been made, the convergence of the iterative (scaled) ADMM algorithm for convex problems such as equation (25) has been shown with the following updates

[00023]$\begin{array}{cc}s\leftarrow \underset{s}{\arg \min }f\left(s\right)+\rho {.Math.D_{s}s+D_{x}x-c+u.Math.}^2,& \left(26a\right)\end{array}$$\begin{array}{cc}x\leftarrow \underset{x}{\arg \min }g\left(x\right)+\rho {.Math.D_{s}s+D_{x}x-c+u.Math.}^2,& \left(26b\right)\end{array}$$\begin{array}{cc}u\leftarrow u+D_{s}s+D_{x}x-c,& \left(26c\right)\end{array}$

[0111] With ρ>0 denoting the augmented Lagrangian parameter, Equation (24) can be rewritten as the following alternating optimization problem

[00024]$\begin{array}{cc}\underset{s,x\in {ℂ}^{N_t}}{\arg \min }{s}^H{H}^H\mathrm{Hs}-2Re\left\{y^H\mathrm{Hs}\right\}& \left(27a\right)\end{array}$$\begin{array}{cc}s.t.x^H\mathrm{Bx}-2Re\left\{b^{H}x\right\}+\delta \le 0,& \left(27b\right)\end{array}$$\begin{array}{cc}x=s& \left(27c\right)\end{array}$

[0112] which yields the updates

[00025]$\begin{array}{cc}s\leftarrow s^H\left(H^{H}H+\rho I_{N_t}\right)s-2Re\left\{\left(y^{H}H+{\rho \left(x+u\right)}^H\right)s\right\},& \left(28a\right)\end{array}$$\begin{array}{cc}x\leftarrow \underset{x\in {ℂ}^{N_t}}{\arg \min }{.Math.x-s+u.Math.}^2& \left(28b\right)\end{array}$
subject to x.sup.HBx−2 Re{b.sup.Hx}+δ≤0,

u.fwdarw.u+x−s  (28c)

[0113] For the update of s, the derivative simply yields a closed-form solution

s.sup.opt.fwdarw.(H.sup.HH+ρI.sub.N.sub.t).sup.−1(H.sup.Hy+ρ(x+u)).  (29)

[0114] For the update of x, however, it is difficult to obtain a closed-form solution due to the quadratic constraint, resorting to the Lagrangian multiplier method with an objective function

(x,μ)=x.sup.H(μB+I)x−2 Re{(μb+s−u).sup.Hx}+μδ  (30)

[0115] from which the optimal can be obtained by taking derivative

x.sup.opt=(μB+I).sup.−1(μb+s−u)  (31)

[0116] Notice that if the global minimizer x=s.Math.u satisfies the inequality constraint in equation (28b), x=s.Math.u is the solution; otherwise, the inequality must be satisfied as equality. Given the above discussion, substituting equation (31) into the equality constraint, we obtain

[00026]$\begin{array}{cc}\stackrel{\stackrel{\stackrel{\Delta }{=}\gamma \left(\mu \right)}{︷}}{\underset{i=1}{\overset{N_t}{.Math.}}\mathrm{diag}\left(B_i\right)\frac{{.Math.\mu b_i+s_i-u_i.Math.}^2}{{\left(\mu \mathrm{diag}\left(B_i\right)+1\right)}^2}-2Re\left\{\underset{i=1}{\overset{N_t}{.Math.}}\frac{b_i^{*}\left(\mu b_i+s_i-u_i\right)}{\mu \mathrm{diag}\left(B_i\right)+1}\right\}+\delta }=0& \left(32\right)\end{array}$

[0117] where diag(.Math.) denotes the i.sup.th diagonal element of a matrix and (.Math.) is i.sup.th element of a vector. To find the optimal μ satisfying the above equality, in what follows we reveal that y(μ) is a strictly decreasing function over μ by showing (d y(μ)/d<0. To this end we obtain

[00027]$\begin{array}{cc}\begin{array}{c}\frac{d\gamma \left(\mu \right)}{d\mu }=\begin{array}{c}\underset{i=1}{\overset{N_t}{.Math.}}\frac{d}{d\mu }\left(\mathrm{diag}\left(B_i\right)\frac{{.Math.\mu b_i+s_i-u_i.Math.}^2}{{\left(\mu \mathrm{diag}\left(B_i\right)+1\right)}^2}\right)-\\ \frac{d}{d\mu }\left(\frac{b_i^{*}\left(\mu b_i+s_i-u_i\right)}{\mu \mathrm{diag}\left(B_i\right)+1}\right)-\frac{d}{d\mu }\left(\frac{{b_i\left(\mu b_i+s_i-u_i\right)}^{*}}{\mu \mathrm{diag}\left(B_i\right)+1}\right)\end{array}\\ =-2\underset{i=1}{\overset{N_t}{.Math.}}\frac{{.Math.b_i.Math.}^2+{\mathrm{diag}\left(B\right)}_i^2{.Math.s_i-u_i.Math.}^2}{{\left(1+\mu \mathrm{diag}\left(B_i\right)\right)}^3}<0.\end{array}& \left(33\right)\end{array}$

[0118] Note that due to the fact that all the diagonal elements of B are nonnegative real values, y(μ) is a non-increasing function in μ≥0. Therefore, the optimal μ* satisfying y(μ*)=0 can be found via iterative root-finding algorithms such as bi-section and Newton's method.

s.fwdarw.(H.sup.HH+ρI.sub.N.sub.t).sup.−1(H.sup.Hy+ρ(x+u)),  (34a)

x.fwdarw.(μB+I).sup.−1(μb+s−u)   (34b) [0119] With optimal g vis solving (32)

u.fwdarw.u+x−s  (34c)

[0120] Input y: Received signal vector; [0121] H: Measurement compressive matrix: [0122] α: Tightening parameter for l.sub.0-norm approximation; [0123] i.sub.max.sup.out: Maximum number of outer iterations [0124] i.sub.max.sup.in: Maximum number of inner (ADMM) iterations [0125] ε: Iteration stop criterion

[0126] 1 Set iteration counter i=0;

[0127] 2 Generate uniformly distributed initial signal vector {tilde over (s)}.sup.(i);

[0128] 3 repeat:

TABLE-US-00001 Input: y: Received signal vector; H: Measurement compressive matrix; a: Tightening parameter for  -norm approximation; i.sub.max.sup.out: Maximum number of outer iterations i.sub.max.sup.in: Maximum number of inner (ADMM) iterations E: Iteration stop criterion 1 Set interation counter i = 0; 2 Generate uniformly distributed initial signal vector  .sup.(i); 3 repeat 4 | [00028]$\mathrm{Update}{\beta }_{\mathrm{ij}}\forall i,j\mathrm{by}{\beta }_{\mathrm{ij}}=\frac{\sqrt{a}}{t_{2N}\text{?}+a};$ 5 | i ← i + 1 and i ← 0; 6 | repeat 7 | | t ← t + 1 8 | | s.sup.(t) ← (H.sup.HH + ρI.sub.N  ).sup.−1(H.sup.Hy + ρ(x.sup.(t−1) + u.sup.(t−1))) 9 | | μ.sup.(t) ← Solve equation (32) via bi-section or Newton’s method 10 | | x.sup.(t) ← (μ.sup.+(t)B + I).sup.−1(μ.sup.(t)b + s.sup.(t) − u.sup.(t−1)) 11 | | u.sup.(t) ← u.sup.(t−1) + x.sup.(t) − s.sup.(t) 12 | | Check convergence δ = ||s.sup.(t) − s.sup.(t−1)||.sub.2 13 | until δ < ε or reach the maximum iteration i.sub.max.sup.in; 14 | .sup.(i) ← s.sup.(t) 15 | Check convergence {circumflex over (δ)} = ||  .sup.(t) −   .sup.(t−1)||.sub.2 16 until {circumflex over (δ)} < ε or reach the maximum interation i.sub.max.sup.out; indicates data missing or illegible when filed

[0129] 16 until δ<ε or reach the maximum iteration i.sub.max.sup.out;

[0130] General Theoretical Base for Receiver Method 4

[0131] In order to address the intractable non-convexity of the l.sub.0-norm without resorting to the l.sub.1-norm, the l.sub.0-norm is replaced with the asymptotically tight expression:

[00029]$\begin{array}{cc}{.Math.x.Math.}_0=\underset{\alpha .fwdarw.0^{+}}{\lim }\underset{j=1}{\overset{N}{.Math.}}\frac{.Math.x_j.Math.}{.Math.x_j.Math.+\alpha }=N-\underset{\alpha .fwdarw.0^{+}}{\lim }\underset{j=1}{\overset{N}{.Math.}}\frac{\alpha }{.Math.x_j.Math.+\alpha }& \left(4\right)\end{array}$

[0132] where x is an arbitrary sparse vector of length T. The tight approximation of the l.sub.0-norm is then used as a substitute of the l.sub.0-norm in the penalized mixed l.sub.0-l.sub.2 minimization problem, and a slack variable t.sub.ij, with the constraint |s.sub.j−c.sub.i|≤t.sub.ij is introduced, yielding

[00030]$\begin{array}{cc}\hat{s}=\underset{\begin{array}{c}s\in {ℝ}^{2N_t};\\ t\in {ℝ}^{2^{\frac{b}{2}+1}{N}_t}\end{array}}{\arg \min }-\underset{i=1}{\overset{2^{\frac{b}{2}}}{.Math.}}{w}_i\underset{j=1}{\overset{2N_t}{.Math.}}\frac{\alpha }{t_{2N_t\left(i-1\right)+j}+\alpha }+\lambda {.Math.y-\mathrm{Hs}.Math.}_2^2& \left(5a\right)\end{array}$$\begin{array}{cc}s.t..Math.s_j-x_i.Math.\le t_{2N_t\left(i-1\right)+j}.& \left(5b\right)\end{array}$

[0133] with now α«1. [0134] Since the ratios

[00031]$\frac{\alpha }{\alpha +t_{2N_t\left(i-1\right)+j}}$  in equation (5a) possess a concave-over-convex structure due to the convex non-negative nominator and concave (linear) positive denominator, the required condition for convergence of the quadratic transform (QT) is satisfied, as has been shown by K. Shen and W. Yu in “Fractional programming for communication systems—Part I: Power control and beamforming,” IEEE Trans. Signal Process., vol. 66, no. 10, pp. 2616-2630, May 2018, such that equation (5a) can be reformulated into the following convex problem:

[00032]$\begin{array}{cc}\hat{s}=\underset{\begin{array}{c}s\in {ℝ}^{2N_t};\\ t\in {ℝ}^{2^{\frac{b}{2}+1}{N}_t}\end{array}}{\arg \min }\underset{i=1}{\overset{2^{\frac{b}{2}}}{.Math.}}{w}_i\underset{j=1}{\overset{2N_t}{.Math.}}{\beta }_{\mathrm{ij}}^2{t}_{2N_t\left(i-1\right)+j}+\lambda {.Math.y-\mathrm{Hs}.Math.}_2^2& \left(6a\right)\end{array}$$\begin{array}{cc}s.t..Math.s_j-x_i.Math.\le t_{2N_t\left(i-1\right)+j}\mathrm{where}{\beta }_{\mathrm{ij}}\stackrel{△}{=}\frac{\sqrt{\alpha }}{t_{2N_t\left(i-1\right)+j}+\alpha }.& \left(6b\right)\end{array}$

[0135] Thanks to the convergence of β.sub.ij the equation can be solved through FP by iteratively updating β.sub.ij and solving the equation for a given β.sub.ij. The equation obtained by transforming the initial non-convex optimization problem into a convex optimization problem can be efficiently solved using known algorithms, such as augmented Lagrangian methods.

[0136] Thus, a computer-implemented method in accordance with the present invention of estimating transmit symbol vectors s transmitted in an overloaded communication channel that is characterized by a channel matrix H of complex coefficients includes receiving, in a receiver R, a signal represented by a received signal vector y. The received signal vector y corresponds to a superposition of signals representing transmitted symbol vectors s selected from a constellation C of symbols c.sub.i that are transmitted from one or more transmitters, plus any distortion and noise added by the channel.

[0137] In case of more than one transmitter the transmitters T are temporally synchronized, i.e., a common time base is assumed between the transmitters T and the receiver R, such that the receiver R receives transmissions of symbols from different transmitters T substantially simultaneously, e.g., within a predetermined time window. The symbols being received simultaneously or within a predetermined time window means that all temporally synchronized transmitted symbols are received at the receiver R before subsequent symbols are received, assuming that a transmitter T transmits a sequence of symbols one by one. This may include settings in which transmitters T adjust the start time of their transmission such that a propagation delay, which depends on the distance between transmitter T and receiver R, is compensated for. This may also include that a time gap is provided between transmitting subsequent symbols.

[0138] The method further comprises defining a convex search space including at least the components of the received signal vector y and of the transmit symbol vectors s for all symbols c.sub.i of the constellation C. Further, continuous first and second functions ƒ.sub.1 and f.sub.2 are defined in the search space. In this context, defining may include selecting factors or ranges of variables or the like for or in an otherwise predetermined function.

[0139] The continuous first function ƒ.sub.1 is a function of the received signal vector y and the channel characteristics H and has a global minimum where the product of an input vector s from the search space and the channel matrix H equals the received signal vector y.

[0140] The continuous second function ƒ.sub.2 is a function of input vectors s from the search space and has a significant low value for each of the transmit symbol vectors s of the symbols c.sub.i of the constellation C.

[0141] In accordance with the invention the first function ƒ.sub.1 and the second function ƒ.sub.2 are combined into a third function h by weighted adding, and a fractional programming algorithm FP is applied to the third function ƒ.sub.3, targeted to finding an input vectors that minimizes the third function ƒ.sub.3. In other words, ŝ is the optimal solution or outcome of applying the FP algorithm to the third function h for which the third function ƒ.sub.3 has a minimum.

[0142] Once an input vector ŝ that minimizes the third function h is found, a mapping rule is applied thereto that translates the input vectors into an estimated transmit vector ŝ.sub.C, in which the index “C” indicates that every single component belongs to the constellation C. In other words, if the vector has two components, A and B, each of the components A and B of the input vectors that minimizes the third function h can have any value in the search space. These values are translated into values A′ and B′ of the estimated transmit vector gc, each of which can only have a value that occurs in any one of the transmit symbol vectors s for the symbols c.sub.i of the constellation C. The components may be mapped separately, e.g., by selecting the closest value of a corresponding component of any of transmit symbol vectors s of the symbols c.sub.i of the constellation C.

[0143] After the mapping the estimated transmit symbol vector ŝ.sub.C is output to a decoder to obtain the data bits of the transmitted message.

[0144] In one or more embodiments the second function ƒ.sub.2 has a tuneable factor that determines the gradient of the function in the vicinity of the significant low value at each of the vectors of the symbols of the constellation. The tuneable factor may help the FP algorithm to converge faster and/or to skip local minima that may be farther away from an optimal or at least better solution.

[0145] In some embodiments the tuneable factor may be different for different symbols of the constellation. For example, the gradient in the vicinity of a vector for a symbol that is farther away from the global minimum of the first function ƒ.sub.1 may be very steep, but may be so only very close to the significant low value. Depending on the FP algorithm and the start value used this may help skipping local minima located at a greater distance from the global minimum of the first function ƒ.sub.1 On the other hand, the gradient in the vicinity of a vector for a symbol that is located close to the global minimum of the first function ƒ.sub.1 may be rather shallow at a certain distance to the significant low value and growing steeper as the distance shrinks. Depending on the FP algorithm used this may help the function to quickly converge to a significant low value.

[0146] In some embodiments the first function ƒ.sub.1 is monotonously increasing from the global minimum. The first function may be considered a coarse guidance function for the FP algorithm, which helps the FP algorithm to converge. It is, thus, advantageous if the first function itself does not have any local minima.

[0147] A receiver of a communication system has a processor, volatile and/or non-volatile memory and at least one interface adapted to receive a signal in a communication channel. The non-volatile memory may store computer program instructions which, when executed by the microprocessor, configure the receiver to implement one or more embodiments of the method in accordance with the invention. The volatile memory may store parameters and other data during operation. The processor may be called one of a controller, a microcontroller, a microprocessor, a microcomputer and the like. And, the processor may be implemented using hardware, firmware, software and/or any combinations thereof. In the implementation by hardware, the processor may be provided with such a device configured to implement the present invention as ASICs (application specific integrated circuits), DSPs (digital signal processors), DSPDs (digital signal processing devices), PLDs (programmable logic devices), FPGAs (field programmable gate arrays), and the like.

[0148] Meanwhile, in case of implementing the embodiments of the present invention using firmware or software, the firmware or software may be configured to include modules, procedures, and/or functions for performing the above-explained functions or operations of the present invention. And, the firmware or software configured to implement the present invention is loaded in the processor or saved in the memory to be driven by the processor.

[0149] The present method addresses difficulties in applying effective FP algorithms for estimating candidates of transmitted symbol vectors arising from the discrete nature of the constellation by transforming the discrete constraint present in the known ML method for determining the Euclidian distance between the received signal's vector and the vectors of symbols of the constellation into a first function in a convex domain that presents significant low values for the vectors of symbols of the constellation. A minimum of the function in the convex domain can be found by applying known FP methods or algorithms that are more effective for finding a good estimate of a transmitted signal's vector than brute-force calculations. A second continuous function in the convex domain is added to the first function that penalizes estimation results with increasing distance from the received signal's vector.

[0150] While the invention has been described hereinbefore for detecting superimposed signals from transmitters that are all using the same constellation C it is also applicable to situations in which different transmitters use different constellations CT, i.e., if the symbols of a constellation C are considered letters of an alphabet, each transmitter may use a different alphabet.

[0151] Those of ordinary skilled in the art will realize that the following detailed description of the exemplary embodiment(s) is illustrative only and is not intended to be in any way limiting. Other embodiments will readily suggest themselves to such skilled persons having the benefit of this disclosure. Reference will now be made in detail to implementations of the exemplary embodiment(s) as illustrated in the accompanying drawings. The same reference indicators will be used throughout the drawings and the following detailed description to refer to the same or like parts. In the drawings identical or similar elements may be referenced by the same reference designators.

[0152] In accordance with the embodiment(s) of the present invention, the components, process steps, and/or data structures described herein may be implemented using various types of operating systems, computing platforms, computer programs, and/or general-purpose machines. In addition, those of ordinary skill in the art will recognize that devices of a less general purpose nature, such as hardwired devices, field programmable gate arrays (FPGAs), application specific integrated circuits (ASICs), or the like, may also be used without departing from the scope and spirit of the inventive concepts disclosed herein. Where a method comprising a series of process steps is implemented by a computer or a machine and those process steps can be stored as a series of instructions readable by the machine, they may be stored on a tangible medium such as a computer memory device (e.g., ROM (Read Only Memory), PROM (Programmable Read Only Memory), EEPROM (Electrically Erasable Programmable Read Only Memory), FLASH Memory, Jump Drive, and the like), magnetic storage medium (e.g., tape, magnetic disk drive, and the like), optical storage medium (e.g., CD-ROM, DVD-ROM, paper card and paper tape, and the like) and other known types of program memory.

DETAILED DESCRIPTION

[0153] The making and using of embodiments of this disclosure are discussed in detail below. It should be appreciated, however, that the concepts disclosed herein can be embodied in a wide variety of specific contexts, and that the specific embodiments discussed herein are merely illustrative and do not serve to limit the scope of the claims. Further, it should be understood that various changes, substitutions and alterations can be made herein without departing from the spirit and scope of this disclosure as defined by the appended claims.

[0154] FIGS. 1 and 2 illustrate basic properties of orthogonal multiple access and non-orthogonal multiple access, respectively. FIG. 1 shows one exemplary embodiment of the ordered access of transmit resources to channels of a shared transmission medium, e.g., in a wireless communication system. The available frequency band is split into several channels. A single channel or a combination of contiguous or non-contiguous channels may be used by any one transmitter at a time. Different transmitters, indicated by the different hashing patterns, may transmit in discrete time slots or in several subsequent timeslots and may change the channels or combination of channels in which they transmit for each transmission. Note that, as shown in FIG. 1, any transmitter may use one channel resource over a longer period of time, while another transmitter may use two or more channel resources simultaneously, and yet another transmitter may to both, using two or more channel resources over a longer period of time. In any case, only one transmitter uses any channel resource or combination thereof at a time, and it is relatively easy to detect and decode signals from each transmitter.

[0155] FIG. 2a shows the same frequency band as shown in FIG. 1, but there may not always be a temporary exclusive assignment of one or more individual channels to a transmitter. Rather, at least a portion of the frequency band may concurrently be used by a plurality of transmitters, and it is much more difficult to detect and decode signals from individual transmitters. Again, different hashing patterns indicate different transmitters, and the circled portions indicate where wo or more transmitters concurrently use a resource. While, beginning from the left, at first three transmitters use temporary exclusive channel resources in an orthogonal manner, in the next moment two transmitters transmit in channels that partially overlap. The transmitter represented by the horizontal hashing pattern has exclusive access to the channel shown at the bottom of the figure, while the next three channels used by this transmitter are also used by another transmitter, represented by diagonal hashing pattern in the dashed-line oval. The superposition is indicated by the diagonally crossed hashing pattern. A similar situation occurs in the following moment, where each of two transmitters exclusively uses two channel resources, while both share a third one. It is to be noted that more than two transmitters may at least temporarily share some or all of the channel resources each of them uses. These situations may be called partial-overloading, or partial-NOMA.

[0156] In a different representation, FIG. 2b shows the same frequency band as FIG. 2a. Since there is no clear temporary exclusive assignment of one or more individual channels to a transmitter, and at least a portion of the frequency band is at least temporarily concurrently used by a plurality of transmitters, the difficulty to detect and decode signals from individual transmitters is indicated by the grey filling pattern that does not allow for identifying any single transmitter. In other words, all transmitters use all channels.

[0157] Signals from some transmitters may be transmitted using higher power than others and may consequently be received with a higher signal amplitude, but this may depend on the distance between transmitter and receiver. FIGS. 2a and 2b may help understanding the situation found in non-orthogonal multiple access environments.

[0158] FIG. 3 shows an exemplary generalized block diagram of a transmitter T and a receiver R that communicate over a communication channel 208. Transmitter T may include, inter alia, a source 202 of digital data that is to be transmitted. Source 202 provides the bits of the digital data to an encoder 204, which forwards the data bits encoded into symbols to a modulator 206. Modulator 206 transmits the modulated data into the communication channel 208, e.g. via one or more antennas or any other kind of signal emitter (not shown). The modulation may for example be a Quadrature Amplitude Modulation (QAM), in which symbols to be transmitted are represented by an amplitude and a phase of a transmitted signal.

[0159] Channel 208 may be a wireless channel. However, the generalized block diagram is valid for any type of channel, wired or wireless. In the context of the present invention the medium is a shared medium, i.e., multiple transmitters and receivers access the same medium and, more particularly, the channel is shared by multiple transmitters and receivers.

[0160] Receiver R receives the signal through communication channel 208, e.g., via one or more antennas or any other kind of signal receiver (not shown). Communication channel 208 may have introduced noise to the transmitted signal, and amplitude and phase of the signal may have been distorted by the channel. The distortion may be compensated for by an equalizer provided in the receiver (not shown) that is controlled based upon channel characteristics that may be obtained, e.g., through analysing pilot symbols with known properties transmitted over the communication channel. Likewise, noise may be reduced or removed by a filter in the receiver (not shown). A signal detector 210 receives the signal from the channel and tries to estimate, from the received signal, which signal had been transmitted into the channel. Signal detector 210 forwards the estimated signal to a decoder 212 that decodes the estimated signal into an estimated symbol. If the decoding produces a symbol that could probably have been transmitted it is forwarded to a de-mapper 214, which outputs the bit estimates corresponding to the estimated transmit signal and the corresponding estimated symbol, e.g., to a microprocessor 216 for further processing. Otherwise, if the decoding does not produce a symbol that is likely to have been transmitted, the unsuccessful attempt to decode the estimated signal into a probable symbol is fed back to the signal detector for repeating the signal estimation with different parameters. The processing of the data in the modulator of the transmitter and of the demodulator in the receiver are complementary to each other.

[0161] While the transmitter T and receiver R of FIG. 3 appear generally known, the receiver R, and more particularly the signal detector 210 and decoder 212 of the receiver in accordance with the invention are adapted to execute the inventive method described hereinafter with reference to FIG. 4 and thus operate different than known signal detectors.

[0162] FIG. 4 shows an exemplary flow diagram of method steps implementing embodiments of the present invention. In step 102 a signal is received in an overloaded communication channel. The signal corresponds to a superposition of signals representing transmitted symbols selected from a constellation C of symbols c.sub.i and transmitted from one or more transmitters T. In step 104 a search space is defined in a convex domain including at least the components of the received signal vector y and of transmit symbol vectors s for all symbols c.sub.i of the constellation C. In step 106 a continuous first function ƒ.sub.1 is defined, which is a function of the received signal vector y and the channel characteristics H. The first function ƒ1 has a global minimum where the product of an input vector s from the search space and the channel matrix H equals the received signal vector y. Further, in step 108 a continuous second function ƒ.sub.2 is defined in the search space, which is a function of input vectors s from the search space. The second function ƒ.sub.2 has a significant low value for each of the transmit symbol vectors s of the symbols c.sub.i of the constellation C. It is to be noted that steps 104, 106 and 108 need not be executed in the sequence shown in the figure, but may also be executed more or less simultaneously, or in a different sequence. The first and second functions ƒ.sub.1, ƒ.sub.2 are combined to a third continuous function h in step 110 through weighted adding. Once the third function h is determined a fractional programming algorithm is applied thereto in step 112 that is targeted to finding an input vector that minimizes the third function h. The input vectors that is the result output from the fractional programming algorithm is translated, in step 114, into an estimated transmit vector Sc, in which every single component has a value from the list of possible values of corresponding components of transmit symbol vectors s of the symbols c.sub.i of the constellation C. The translation may include selecting the value from the list that is nearest to the estimated value. The estimated transmit vector Sc is then output in step 116 to a decoder for decoding into an estimated transmitted symbol c from the constellation C. The transmitted symbol c may be further processed into one or more bits of the data that was transmitted, step 118.

[0163] FIG. 5 shows details of the method steps of the present invention executed for finding an input vectors that minimizes the third function h, in particular the function according to equation 6 described further above. In step 112-1 the fractional programming is initialised with a start value for the estimated transmit signal's vector ŝ.sub.start, and β.sub.ij is determined in step 112-2 for the start value of the estimated transmit vector ŝ.sub.start. Then, a new candidate for ŝ is derived in step 112-3 by solving the equation for the value β.sub.ij determined in step 112-2. If the solution does not converge, “no”-branch of step 112-4, the value β.sub.ij is determined based on the new candidate derived in step 112-3 and the equation-solving process is repeated. If the solution converges, “yes”-branch of step 112-4, ŝ forwarded to step 114 of FIG. 4, for mapping the estimated transmit vector Sc whose components assume values from vectors s of symbols c.sub.i from the constellation C.

[0164] FIG. 6 a) shows exemplary and very basic examples of symbols c.sub.1, c.sub.2, c.sub.3 and c.sub.4 from a constellation C. The symbols c.sub.1, c.sub.2, c.sub.3 and c.sub.4 may represent symbols of a QAM-modulation. FIG. 6b) shows a symbol that was actually transmitted over a channel, in this case symbol c.sub.2. FIG. 6c) shows the signal that was actually received at a receiver. Due to some distortion and noise in the channel the received signal does not lie exactly at the amplitude and phase of symbol c.sub.2 that was sent. A maximum likelihood detector determines the distances between the received signal and each of the symbols from the constellation and would select that one as estimated symbol that is closest to the received signal. In the very simple example, this would be symbol c.sub.2. This process requires performing calculations for all discrete pairs of received signal and symbols from the constellation, and may result in a number of calculations that exponentially increases with the number of symbols in the constellation and the number of transmitters that possibly transmitted the signal.

[0165] FIG. 7 shows a simplified exemplary graphical representation of the third function determined in accordance with the present invention that can be effectively solved using fractional programming.

[0166] The graphical representation is based on the same constellation as presented in FIG. 6a), and it is assumed that the same signal c.sub.2 was transmitted. The bottom surface of the three-dimensional space represents the convex search space for amplitudes and phases of signal vectors. The vertical dimension represents the values for the third function. Since the search space is convex, the third function has values for any combination of amplitude and phase, even though only 4 discrete symbols c.sub.1, c.sub.2, c.sub.3 and c.sub.4 are actually in the constellation. The surface having a shape of an inverted cone represents the results of the continuous first function over the convex search space and has a global minimum at the location of the received signal. The 4 spikes protruding downwards from the cone-shaped surface represent the continuous second function that has significant low values at the phases and amplitudes of the symbols from the constellation. The first and second function have been combined into the third function, which is still continuous, and which can now be subjected to a fractional programming algorithm for finding the amplitude and phase that minimizes the third function. It is to be borne in mind that this representation is extremely simplified, but it is believed to help understanding the invention.

[0167] FIGS. 8 and 9 are the embodiment of a computer-implemented receiver method 3 of estimating transmit symbol vectors transmitted in an overloaded communication channel that is characterized by a channel matrix of complex coefficients, is described. The method receives 102, in a receiver R, a signal represented by a received signal vector. This received signal vector corresponding to a superposition of signals representing transmitted symbols selected from at least one constellation of symbols and transmitted from one or more transmitters T. Furthermore a defining 104 of a search space in a convex domain including at least a differentiable and convex function 37 in a closed form of the received signal vector and of transmit symbol vectors for all symbols of the at least one constellation is done.

[0168] In order obtaining the differentiable and convex function 37 in a closed form the first optimization formulation given by a first function 7 in recalculated into a second optimization formulation given as a second function 35. This is done by applying a quadratic approximation of l.sub.0-norm given as third function 9 and after obtaining the second function 35 a forth function 36 is calculated. In order to obtain the differentiable and convex function 37, which is the core element of the receiver method 3, in a closed form of the received signal vector and of transmit symbol vectors is obtained by applying the setting of the Wingerts derivative of the forth function 36. Afterward the optimal solution (s.sup.opt) calculated via a matrix multiplication for the fixed elements of the second function 35 is done, like it is shown in FIG. 9 step 306. By checking the convergence 6 given in step 307 iterative procedure is performed to find the optimal solution (s.sup.opt) for the estimation of transmitting symbols.

[0169] FIGS. 10 and 11 are illustrating the second embodiment of the computer-implemented receiver method 4 of estimating transmit symbol vectors transmitted in an overloaded communication channel. The channel is characterized by a channel matrix of complex coefficients.

[0170] This second the method 4 includes the received signal vector corresponding to a superposition of signals representing transmitted symbols selected from at least one constellation of symbols and transmitted from one or more transmitters T. Furthermore defining 104 of a search space in a convex domain including is done by defining 104 a search space in a convex domain including at least closed-form solution providing s and penalty parameter λ covering fifth function 44 of the received signal vector and of transmit symbol vectors for all symbols of the at least one constellation. This fifth function 44 is the core element of the receiver method 4.

[0171] In order to obtain a closed-form fifth function 44 providing s and penalty parameter λ by changing the first optimization formulation given as a sixth function 38, which is a real-valued quadratically constrained quadratic program (QCQP) version of a seventh function 6, which is recalculated into a generalized eigenvalue formulation and the Maus transformed eighth function 43. If this is done applying an iterative procedure to find the optimal solution (s.sup.opt) for the estimation of transmitting symbols is performed. This is illustrated in step 406 of FIG. 11.

[0172] Furthermore in order to obtain the estimate solution of the methods 3 and 4 are calculated if the iterative procedure the coefficients β's, which are given in terms on the estimate solution s (s), the constellation alphabet (x), and the tightening parameter α are determined.

[0173] FIGS. 12 and 13 are illustrating the third embodiment of the of a computer-implemented receiver method 5.

[0174] FIGS. 12 and 13 are illustrating the third embodiment of the computer-implemented receiver method 5 of estimating transmit symbol vectors transmitted in an overloaded communication channel. The channel is characterized by a channel matrix of complex coefficients.

[0175] This third the method 5 includes the received signal vector corresponding to a superposition of signals representing transmitted symbols selected from at least one constellation of symbols and transmitted from one or more transmitters T. Furthermore a defining 104 of a search space in a convex domain including is done by defining 104 a search space in a convex domain including at least closed-form solution providing s and penalty parameter λ covering fifth function 44 of the received signal vector and of transmit symbol vectors for all symbols of the at least one constellation. This fifth function 34 is the core element of the receiver method 5.

[0176] The non closed-form ninth function (34) providing s and penalty parameter λ is obtained by changing the third optimization formulation given as a combination of a tenth function (9) and eleventh function (5), wherein the tenth function (9) is combined with the eleventh function (5) via a Quadratic Transform in order to obtain a twelfth function (18), wherein thirteenth function (24) is determined with a QCQP-1 transformation of the twelfth function (18) and Alternating Direction Method of Multipliers (ADMM) is applied the iterative procedure to find the optimal solution (s.sup.opt) for the estimation of transmitting symbols is performed.

[0177] Furthermore in order to obtain the estimated solution of the method 5 is calculated if the iterative procedure the coefficients 13 as, which are determined by equation 20, with the loops and which have a special convergence criteria's to solve ninth function (34), which are given in terms on the estimate solution s (s), the constellation alphabet (x), and the tightening parameter α are determined.

[0178] This means, that the computer-implemented receiver method 5 of estimating transmit symbol vectors transmitted in an overloaded communication channel that is characterized by a channel matrix of complex coefficients, the method including, receiving 102, in a receiver R, a signal represented by a received signal vector, the received signal vector corresponding to a superposition of signals representing transmitted symbols selected from at least one constellation of symbols and transmitted from one or more transmitters T, defining 104 a search space in a convex domain including at least closed-form solution providing s and penalty parameter λ fifth function 44 of the received signal vector and of transmit symbol vectors for all symbols of the at least one constellation, obtaining a non closed-form ninth function 34 providing s and penalty parameter λ by changing the third optimization formulation given as a combination of a tenth function 9 and eleventh function 5, wherein the tenth function 9 is combined with the eleventh function 5 via a Quadratic Transform in order to obtain a twelfth function 18, wherein thirteenth function 24 is determined with a QCQP-1 transformation of the twelfth function 18 and Alternating Direction Method of Multipliers (ADMM) is applied and applying an iterative procedure to find the optimal solution (s.sup.opt) for the estimation of transmitting symbols is performed.

[0179] Table I the relative performance of the first three proposed receivers in terms of their computational complexities are shown. For reference, it is included in that table the complexity of the SOAV and as well as the SBR decoders, while omitting that of SCSR since SOAV is the one that has lower cost, and since the BER performance of both is identical. The complexity performance assessment is carried out by counting the elapsed time of all compared receivers running 64-bit MATLAB 2018b in a computer with an Intel Core i9 processor, clock speed of 3.6 GHz and 32 GB of RAM memory. The results so obtained and summarized in Table I, elucidate that the complexity of the DAPZF receiver is not only the smallest amongst the three new methods, but in fact significantly lower (by a factor of almost l.sub.0) than that of the SOAV decoder. And since DAPZF achieves similar BER performance as the ADMM-DAPSD and the DAGED methods in underloaded and fully loaded scenarios, it can be concluded that that scheme is the method of choice in those cases.

[0180] Table I also reveals that after DAPZF, DAGED is the second least computationally demanding of the new receivers, which when taken together with its BER performance, leads to the conclusion that the DAGED scheme is the trade-off method of choice amongst the three receivers here developed. Finally, the ADMM-DAPSD solution is found according to Table I to be the most computationally demanding of the all, which is non-surprising since this approach is also the one that yields the best BER performance in overloaded scenarios. All in all, the contributed methods therefore demonstrate feasibility of concurrently overloaded multidimensional systems, while offering three different choices according to the system setup.

TABLE-US-00002 TABLE I RUNTIME COMPARISON OF PROPOSED RECEIVER METHODS 1-3 AND State of the Art Receiver SOAV SBR Receiver Receiver Method 3 State State Method 1 Method 2 (ADMM- of the of the (DAGED) (DAFZF) DAPSD) Art Art Average 0.2663 0.0034 0.5207 0.0166 0.2040 Runtime sec sec sec sec sec E.sub.b/N.sub.0 0 14 [dB] (N.sub.T = 60 & N.sub.R = 40)