Schnorr-euchner expansions and their fast implementations

Abstract

Methods and apparatus reducing or eliminating the number of multipliers in Schnorr-Euchner expansion algorithms are disclosed. Methods and apparatus for implementing Schnorr-Euchner expansion algorithms with a reduced number of multipliers or without any multipliers are also disclosed. Also disclosed is a Schnorr-Euchner expansion method for a multiple-input multiple-output communication system. The method includes receiving, by a plurality of input terminals, a plurality of input signals. The method also includes detecting a symbol transmitted by each input signal. The detection includes identifying a list of possible symbols that may be transmitted by each input signal. A cost value for each possible symbol is determined based on a cost function. The cost function is implemented without requiring a multiplier. The possible symbol with a lowest cost value is identified as the transmitted symbol.

Claims

1. A Schnorr-Euchner (SE) expansion method for a multiple-input multiple-output (MIMO) communication system that includes a plurality of antennas at a transmitter side and a plurality of antennas at a receiver side, comprising: receiving, by the plurality of antennas at the receiver side of the MIMO communication system, a plurality of input signals, each input signal containing a symbol; and identifying a list of first 9 possible symbols that may be contained in each input signal received by each antenna at the receiver side; checking conditions when identifying 2.sup.nd to 9.sup.th possible symbols of the list of the first 9 possible symbols, the checking conditions being implemented by shifting and addition operations; determining a cost value for each of the first 9 possible symbols based on a cost function, the cost function being implemented without requiring a multiplier; and identifying the possible symbol with a lowest cost value as the symbol contained in the input signal, wherein the cost function has a mathematical representation of c=|yrz|.sup.p, wherein y is the output, r is a system implementing the SE method, z is an input, c is the cost, and an integer p denotes a l.sub.p-norm, wherein p=2.

2. The method of claim 1, wherein the cost function is based on a recursive equation.

3. The method of claim 1, wherein the cost function has a real domain.

4. The method of claim 1, wherein the cost function has a complex domain.

5. The method of claim 1, wherein multiplication in the cost function is implemented using a multiplexer.

6. The method of claim 1, wherein multiplication in the cost function is implemented using a shift register.

7. The method of claim 1, further comprising arranging the list of possible symbols in an ascending order of their cost values.

8. An apparatus implementing a Schnorr-Euchner expansion method without requiring a multiplier for handling signal processing in multiple-input multiple-output signal transmission detection, comprising: a plurality of antennas each configured to receive a wireless signal; and a processor in connection with the antennas configured to detect a symbol contained in each wireless signal received by each antenna, by: identifying a list of fist 9 possible symbols that may be contained in the wireless signal; checking conditions when identifying 2.sup.nd to 9.sup.th possible symbols of the list of the first 9 possible symbols, the checking conditions being implemented by shifting and addition operations; determining a cost value for each of the fist 9 possible symbols based on a cost function; and identifying the possible symbol with a lowest cost value as the symbol contained in the wireless signal, wherein the cost function has a mathematical representation of c=|yrz|.sup.p, wherein y is the output, r is a system implementing the SE method, z is an input, c is the cost, and an integer p denotes a l.sub.p-norm, wherein p=2.

9. The apparatus of claim 8, wherein the cost function has a real domain.

10. The apparatus of claim 8, wherein the cost function has a complex domain.

11. A multiple-input multiple-output communication system, comprising: a plurality of antennas each configured to receive an input signal; and an integrated circuit implementing a Schnorr-Euchner expansion algorithm without requiring a multiplier, the integrated circuit configured to detect a symbol contained in each input signal received by each antenna, by: estimating a list of first 9 possible symbols that may be contained in the input signal; checking condition when identifying 2.sup.nd to 9.sup.th possible symbols of the list of the first 9 possible symbols, the checking conditions being implemented by shifting and addition operations; determining a cost value for each of the first possible symbols based on a cost function; and identifying the possible symbol with a lowest cost value as the symbol contained in the input signal, wherein the cost function has a mathematical representation of c=|yrz|.sup.p, wherein y is the output, r is a system implementing the SE method, z is an input, c is the cost, and an integer p denotes a l.sub.p-norm, wherein p=2.

12. The system of claim 11, wherein the cost function has a real domain.

13. The system of claim 11, wherein the cost function has a complex domain.

14. The system of claim 11, wherein multiplication in the cost function is implemented using a multiplexer or a shift register.

Description

BRIEF DESCRIPTION OF THE DRAWINGS

(1) The following Detailed Description technology is better understood when read in conjunction with the appended drawings. For the purposes of illustration, there is shown in the drawings exemplary embodiments, but the subject matter is not limited to the specific elements and instrumentalities disclosed.

(2) FIG. 1 provides a block diagram of a system model, in accordance with an exemplary embodiment of the disclosed technology.

(3) FIG. 2 illustrates a hardware implementation of an SE expansion without early evaluation, in accordance with an exemplary embodiment of the disclosed technology.

(4) FIG. 3 illustrates a hardware implementation of an SE expansion with early evaluation, in accordance with an exemplary embodiment of the disclosed technology.

(5) FIG. 4 illustrates another hardware implementation of an SE expansion with early evaluation, in accordance with an exemplary embodiment of the disclosed technology.

(6) FIG. 5 illustrates yet another hardware implementation of an SE expansion, in accordance with an exemplary embodiment of the disclosed technology.

(7) FIG. 6 illustrates 2nd and 3rd SE solutions, in accordance with an exemplary embodiment of the disclosed technology.

(8) FIG. 7 illustrates a decision boundary of 4th, 5th and 6th SE solutions, in accordance with an exemplary embodiment of the disclosed technology.

(9) FIG. 8 illustrates layers of SE expansions, in accordance with an exemplary embodiment of the disclosed technology.

(10) FIG. 9 illustrates a decision boundary of 4th SE solution, in accordance with an exemplary embodiment of the disclosed technology.

(11) FIG. 10 illustrates a decision boundary of 5th SE solution, in accordance with an exemplary embodiment of the disclosed technology.

(12) FIG. 11 illustrates a decision boundary of 6th SE solution, in accordance with an exemplary embodiment of the disclosed technology.

(13) FIG. 12 illustrates a decision boundary of 8th SE solution, in accordance with an exemplary embodiment of the disclosed technology.

(14) FIG. 13 illustrates a decision boundary of 9th SE solution, in accordance with an exemplary embodiment of the disclosed technology.

(15) FIG. 14 is a flow diagram of a method, according to an exemplary method of the disclosed technology.

DETAILED DESCRIPTION

(16) To facilitate an understanding of the principles and features of the disclosed technology, various illustrative embodiments are explained below. In particular, the disclosed technology is described in the context of systems and methods for MIMO communication systems. Certain embodiments of the disclosed technology may be applied to many wireless MIMO communication system standards known in the art, including, but not limited to, IEEE 802.11 (Wi-Fi), 4G, 3GPP, Long Term Evolution, Wi-MAX, HSPA+, and the like. Embodiments of the disclosed technology, however, are not limited to use in wireless MIMO communication systems. Rather, embodiments of the disclosed technology can be used for processing other MIMO communication systems, including, but not limited to, optical MIMO systems or other transmission systems having an architecture incorporating multiple transmitters and/or multiple transceivers.

(17) The components described hereinafter as making up various elements of the disclosed technology are intended to be illustrative and not restrictive. Many suitable components or steps that would perform the same or similar functions as the components or steps described herein are intended to be embraced within the scope of the disclosed technology. Such other components or steps not described herein can include, but are not limited to, for example, similar components or steps that are developed after development of the disclosed technology.

(18) FIG. 1 illustrates a system model 100 according to one embodiment of the disclosed technology. The system model 100 may include an input z, a system r, and an output y. In one embodiment, the SE method may have a mathematical representation as provided in the following equation:
c=|yrz|.sup.p,(1)
where y and r0 may be known real numbers, z may be an unknown integer parameter, c may represent the cost of the SE algorithm, and integer p may denotes the l.sub.p-norm.

(19) When p=1, the above equation may compute an l.sub.1-norm cost. When p=2, the above equation may compute an l.sub.2-norm cost. The methods described herein may be applicable to other values of p. In some embodiments, there may exist a sequence of all possible z, i.e., {z.sup.(1), z.sup.(2), . . . } (z.sup.(n)z.sup.(m), nm), costs for all possible z may be disclosed by {c.sup.(n)=(yrz.sup.(n)).sup.2}.sub.n=1.sup. where costs are arranged in an ascend order such that c.sup.(1)<c.sup.(2)< . . . .

(20) Given r and y, the SE method disclosed herein may find K best candidates z in a fast way. For instance, the SE method may find the top k z's, i.e., {z.sup.(n)}.sub.n=1.sup.k such that their corresponding costs {c.sup.(n)}.sub.n=1.sup.k are smallest in a sequential way.

(21) 1. Conventional SE Method

(22) 1.1 Real Case

(23) In real domain, to achieve the goal with low complexity, the SE method may calculate z.sup.(n) and c.sup.(n) with two stagesthe initial stage and the expansion stage. The initial stage of the SE method may obtain z.sup.(1) and initializes a step variable s.sup.(1) to help determine the next z as
z.sup.(1)=y/r,(2)
s.sup.(1)=sgn(y/rz.sup.(1)),(3)
c.sup.(1)=|yrz.sup.(1)|.sup.p,(4)
where .Math. denotes the rounding function.

(24) At the expansion stage, the SE method may expand z.sup.(n), n2 using the following recursive formula:
z.sup.(n)=z.sup.(n1)+s.sup.(n1),(5)
s.sup.(n)=s.sup.(n1)sgn(s.sup.(n1)),(6)
c.sup.(n)=|yrz.sup.(n)|.sup.p,(7)
where s.sup.(n) is a step variable to help determine the next z.sup.(n+1).

(25) Table 1 illustrates a conventional SE method. The main complexity of the SE expansion is in Eq. (7). In the conventional SE method, two multipliers are required for p=2 and one multiplier is required for p=1. Since multipliers usually result in much longer latency compared to adders and multiplexers in hardware implementation, especially when the bit width is large, a raw implementation of Eq. (7) can become a critical path that lowers the maximum achievable frequency, i.e., maximum throughput of VLSI implementation.

(26) TABLE-US-00001 TABLE 1 Original SE method SE Initialization Input: y, r, p Output: z.sup.(1), s.sup.(1), c.sup.(1) Line 1 z.sup.(1) = y/r Line 2 s.sup.(1) = sgn(y/r z.sup.(1)) Line 3 c.sup.(1) = | y rz.sup.(1) |.sup.p SE Expansion at z.sup.(n), n 2 Input: y, r, p, z.sup.(n 1), s.sup.(n 1) Output: z.sup.(n), s.sup.(n), c.sup.(n) Line 1 z.sup.(n) = z.sup.(n 1) + s.sup.(n 1) Line 2 s.sup.(n) = s.sup.(n 1) sgn(s.sup.(n 1)) Line 3 c.sup.(n) = | y rz.sup.(n) |.sup.p
1.2 Complex Case

(27) Unlike the SE expansion in real domain that can be easily computed using recursive equations, existing complex SE methods require a candidate list that contains all possible next expansions. For instance, to find z.sup.(n), n>1, existing complex SE method maintains a list of possible SE expansions and classifies the expansions into two categories: Type I, where the imaginary part of z.sup.(n) is the same as the imaginary part of z.sup.(1). Type II, otherwise.

(28) If a Type I expansion is chosen as the next expansion of z.sup.(n), both the real and imaginary SE expansions may be executed to guarantee that the next smallest solution is in the candidate list , while for a Type II expansion, only imaginary SE expansion may be used. An example of the existing complex SE method is given in Table 2, where s.sup.(n) is an auxiliary variable to help determine the SE expansion in real or imaginary direction.

(29) TABLE-US-00002 TABLE 2 Original Complex SE method Complex SE Initialization Input: y, r Output: .sup.(1) Line 1 z = y/r Line 2 s = sgn(y/r z) Line 3 c =| y rz |.sub.1 Line 4 .sup.(1) = {(z,c,s)} Note, for complex arguments, sgn operates independently on the real and imaginary parts. Complex SE Expansion at z.sup.(n), n 1 Input: [z.sup.(1)], y, r, .sup.(n) Output: z.sup.(n), s.sup.(n), c.sup.(n), .sup.(n+1) Line 1 (z.sup.(n), c.sup.(n), s.sup.(n)) = arg min.sub.c(z, c, s) .sup.(n) Line 2 .sup.(n+1) = .sup.(n)/{(z.sup.(n), c.sup.(n), s.sup.(n))} Line 3 z.sub.1 = z.sup.(n) + I[s.sup.(n)]j Line 4 s.sub.1 = [s.sup.(n)] + (I[s.sup.(n)] sgn(I[s.sup.(n)]))j Line 5 c.sub.1 =| y rz.sub.1 |.sub.1 Line 6 .sup.(n + 1) = .sup.(n + 1) {(z.sub.1, s.sub.1, c.sub.1)} Line 7 If I[z.sup.(n)] = I[z.sup.(1)] then Line 8 z.sub.2 = z.sup.(n) + [s.sup.(n)] Line 9 s.sub.2 = [s.sup.(n)] sgn ( [s.sup.(n)]) + I[s.sup.(n)]j Line 10 c.sub.2 =| y rz.sub.2 |.sub.1 Line 11 .sup.(n+1) = .sup.(n+1) {(z.sub.2, s.sub.2, c.sub.2)} Line 12 End if

(30) Complex SE method has been discussed in L. Zhang, H. Lei, X. Zhang, and D. Yang, Efficient complex sphere decoding framework for linear dispersion space-time block codes, in Proc. IEEE Int. Symp. on Personal, Indoor and Mobile Radio Commun. (PIMRC), Athens, Greece, September 2007, pp. 1-4. Complex SE method has also been discussed in M. Mahdavi and M. Shabany, Novel MIMO detection algorithm for high-order constellations in the complex domain, IEEE Trans. VLSI Syst., vol. 21, no. 5, pp. 834-847, May 2013.

(31) 2. Multiplier Reduction 1 (MR1): Updating the Crossing Multiplication Recursively

(32) In one aspect, the disclosed technology improves the existing SE method by eliminating or reducing the use of multipliers. According to one embodiment of the disclosed technology, rz.sup.(n) in Eq. (7) may be reduced as follows to avoid the use of multipliers. For instance, by introducing an auxiliary variable A.sup.(n)=rz.sup.(n), rz.sup.(n) may be represented by the following recursive equation:

(33) $\begin{array}{cc}\begin{array}{c}{A}^{\left(n\right)}=r\left(z^{\left(n-1\right)}+s^{\left(n-1\right)}\right)\\ =r\left(z^{\left(n-2\right)}+s^{\left(n-2\right)}-s^{\left(n-2\right)}-\mathrm{sgn}\left(s^{\left(n-2\right)}\right)\right)\\ =A^{\left(n-2\right)}+r\mathrm{sgn}\left(s^{\left(n-1\right)}\right),\end{array}& \left(8\right)\end{array}$
which is based on the fact that sgn(s.sup.(n2))=sgn(s.sup.(n1)).

(34) As a result, c.sup.(n) may be recursively computed using the following formula
c.sup.(n)=|yA.sup.(n)|.sup.p.(9)

(35) Table 3 illustrates one embodiment of the SE method according to the disclosed technology.

(36) TABLE-US-00003 TABLE 3 Proposed SE method with MR1 (without early evaluation). SE Initialization Input: y, r, p Output: z.sup.(1) , s.sup.(1), c.sup.(1) , A.sup.(0), A.sup.(1) Line 1 z.sup.(1) = y/r Line 2 s.sup.(1) = sgn(y/r z.sup.(1)) Line 3 A.sup.(0) = A.sup.(1) = rz.sup.(1) Line 4 c.sup.(1)| = y A.sup.(1) |.sup.p SE Expansion at z.sup.(n), j 2 Input: y, r, p, z.sup.(n1), s.sup.(n1), A.sup.(n2) Output: z.sup.(n), s.sup.(n), c.sup.(n), A.sup.(n) Line 1 z.sup.(n) = z.sup.(n1) + s.sup.(n1) Line 2 s.sup.(n) = s.sup.(n1) sgn(s.sup.(n1)) Line 3 A.sup.(n) = A.sup.(n2) + rsgn(s.sup.(n1)) Line 4 c.sup.(n) =| y A.sup.(n) |.sup.p

(37) As illustrated in Table 3, at the initial step, A.sup.(0)=A.sup.(1)=rz.sup.(1) may ensure that the SE method described herein reaches the exact solution as the original SE method. In Table 3, lines 3-4 may be regarded as the critical path of the SE expansion, which may lower the maximum frequency.

(38) To shorten the critical path, Table 4 illustrates another embodiment of the SE method where an early evaluation (EE) may be performed on A.sup.(n). As shown in Table 4, the early evaluation may be calculated in the initial stage or previous expansions.

(39) TABLE-US-00004 TABLE 4 Proposed SE method with MR1 (with early evaluation). SE Initialization Input: y, r, p Output: z.sup.(1), s.sup.(1), c.sup.(1), A.sup.(2), A.sup.(3) Line 1 z.sup.(1) = y/r Line 2 s.sup.(1) = sgn(y/r z.sup.(1)) Line 3 A.sup.(2) = r(z.sup.(1) + s.sup.(1)) Line 4 A.sup.(3) = r(z.sup.(1) s.sup.(1)) Line 5 c.sup.(1) =| y rz.sup.(1) |.sup.p SE Expansion at z.sup.(n), j 2 Input: y, r, p, z.sup.(n .sup.1), s.sup.(n .sup.1), A.sup.(n) Output: z.sup.(n), s.sup.(n), c.sup.(n), A.sup.(n + 2) Line 1 z.sup.(n) = z.sup.(n .sup.1) + s.sup.(n .sup.1) Line 2 s.sup.(n) = s.sup.(n .sup.1) sgn(s.sup.(n .sup.1)) Line 3 A.sup.(n + 2) = A.sup.(n) + rsgn(s.sup.(n .sup.1)) Line 4 c.sup.(n) =| y A.sup.(n) |.sup.p

(40) The multiplication with sgn(s.sup.(n1)) in Eq. (8) and the absolute operation for p=1 in Eq. (9) may be efficiently implemented without the use of any multiplier. For instance, these operations may be implemented simply by using a multiplexer. Therefore, in this embodiment, for p=1, no multiplier is required for the proposed SE expansion. For instance, FIGS. 2-3 each illustrate an exemplary hardware implementation of the SE method described herein where no multiplier is used. Specifically, FIG. 2 illustrates a hardware implementation of the SE method represented by Table 3 without early evaluation, in which the critical path is indicated by dashed lines. FIG. 3 illustrates a hardware implementation of the SE method represented by Table 4 with early evaluation. As shown in FIGS. 2-3, additional input and output are included, such as A.sup.(n1) in FIG. 2 and A.sup.(n+1) in FIG. 3, such that the output may be directly connected to the input of the next (n+1)st expansion without any control code.

(41) Further, for p=2, the number of multipliers may be reduced to one because of the square operation.

(42) In some embodiments, a further improvement of the SE method may reduce the multiplier in r sgn(s.sup.(n1)) by defining R.sup.(n1)=r sgn(s.sup.(n1)) and using the recursive equation R(n)=R(n1). FIG. 4 illustrates an exemplified hardware implementation of the SE expansion in this regard.

(43) 3. Multiplier Reduction 2 (MR2): Calculating l.sub.2-Norm Recursively

(44) In one aspect, the disclosed technology improves the existing SE method by eliminating the use of multipliers when calculating l.sub.2-norm. For instance, the calculation of l.sub.2-norm based on Eq. (7) with p=2 may be disclosed as follows:

(45) $\begin{array}{cc}\begin{array}{c}{c}^{\left(n\right)}={\left(y-{\mathrm{rz}}^{\left(n-1\right)}-{\mathrm{rs}}^{\left(n-1\right)}\right)}^2\\ ={\left(y-{\mathrm{rz}}^{\left(n-2\right)}-r\mathrm{sgn}\left(s^{\left(n-1\right)}\right)\right)}^2\\ ={\left(y-{\mathrm{rz}}^{\left(n-2\right)}\right)}^2+r^2-\mathrm{sgn}\left(s^{\left(n-1\right)}\right)\left(2\mathrm{ry}-2r^2{z}^{\left(n-2\right)}\right)\\ =c^{\left(n-2\right)}+c-2\mathrm{sgn}\left(s^{\left(n-1\right)}\right)\left(D-B^{\left(n-2\right)}\right),\end{array}& \left(10\right)\end{array}$
where B.sup.(n2)=r.sup.2z.sup.(n2), C=r.sup.2, and D=ry.

(46) Similar to A.sup.(n), B.sup.(n) may be determined based on the following recursive equation:

(47) $\begin{array}{cc}\begin{array}{c}{B}^{\left(n\right)}=r^2{z}^{\left(n-2\right)}\\ =r^2\left(z^{\left(n-3\right)}+s^{\left(n-3\right)}\right)\\ =r^2\left(z^{\left(n-4\right)}+s^{\left(n-4\right)}-s^{\left(n-4\right)}-\mathrm{sgn}\left(s^{\left(j-n\right)}\right)\right)\\ =B^{\left(n-2\right)}+C\mathrm{sgn}\left(s^{\left(n-1\right)}\right).\end{array}& \left(11\right)\end{array}$

(48) Table 5 illustrates an exemplary pseudo code of the SE method according to this embodiment.

(49) TABLE-US-00005 TABLE 5 Proposed SE with MR2 for p = 2 SE Initialization Input: y, r Output: z.sup.(1) , s.sup.(1), c.sup.(0), c.sup.(1), B.sup.(0), B.sup.(1), C, D Line 1 z.sup.(1) = y/r Line 2 s.sup.(1) = sgn(y/r z.sup.(1)) Line 3 B.sup.(0) = B.sup.(1) = r.sup.2z.sup.(1) Line 4 c.sup.(0) = c.sup.(1) = (y rz.sup.(1)).sup.2 Line 5 C = r.sup.2 Line 6 D = ry SE Expansion at z.sup.(j), j 2 Input: z.sup.(n 1), s.sup.(n 1), c.sup.(n 2), B.sup.(n 2), C, D Output: z.sup.(n), s.sup.(n), c.sup.(n), B.sup.(n) Line 1 z.sup.(n) = z.sup.(n 1) + s.sup.(n 1) Line 2 s.sup.(n) = s.sup.(n 1) sgn(s.sup.(n 1)) Line 3 B.sup.(n) = B.sup.(n .sup.2) + Csgn(s.sup.(n 1)) Line 4 c.sup.(n) = c.sup.(n 2) + C 2sgn(s.sup.(n 1))(D B.sup.(n 2))

(50) In Table 5, for the initial step, B.sup.(0)=B.sup.(1)=r.sup.2z.sup.(1) and c.sup.(0)=c.sup.(1) may yield the same results as the original SE method in Eqs. (2)-(7).

(51) Further, as illustrated in Table 5, C=r.sup.2 and D=ry may be constants in the expansion stage, and their values may be pre-computed in the initialization stage. Further, as illustrated in Table 5, the multiplication with 2 may be implemented using a shift register without any multiplier. As a result, this embodiment of the SE expansion method may not require any multiplier in calculating c.sup.(n) and B.sup.(n) for p=2. FIG. 5 illustrates a hardware implementation of the SE expansion according to this embodiment where no multiplier is used therein.

(52) In another embodiment, the l.sub.2-norm may be calculated as follows:

(53) $\begin{array}{cc}{c}^{\left(n\right)}=y^2-2{\mathrm{yrz}}^{\left(n\right)}+{r^2\left(z^{\left(n\right)}\right)}^2=y^2-E^{\left(n\right)}+F^{\left(n\right)},& \left(12\right)\end{array}$
where E.sup.(n)=2yrz.sup.(n) and F.sup.(n)=r.sup.2(z.sup.(n)).sup.2, both of which can be recursively updated according to the following formulas:

(54) $\begin{array}{cc}\begin{array}{c}{E}^{\left(n\right)}=2\mathrm{yr}\left(z^{\left(n-2\right)}+\mathrm{sgn}\left(s^{\left(n-1\right)}\right)\right)\\ =E^{\left(n-2\right)}+2D\mathrm{sgn}\left(s^{\left(n-1\right)}\right),\end{array}& \left(13\right)\\ \begin{array}{c}{F}^{\left(n\right)}={r^2\left(z^{\left(n-2\right)}+\mathrm{sgn}\left(s^{\left(n-1\right)}\right)\right)}^2\\ ={r^2\left(z^{\left(n-2\right)}\right)}^2+2r^2{z}^{\left(n-2\right)}\mathrm{sgn}\left(s^{\left(n-1\right)}\right)+r^2\\ =F^{\left(n-2\right)}+2B^{\left(n-2\right)}\mathrm{sgn}\left(s^{\left(n-1\right)}\right)+C.\end{array}& \left(14\right)\end{array}$

(55) In this embodiment, the SE method again may be implemented without multipliers. In some aspects, the early evaluation (EE) method may be applied to E.sup.(n) and F.sup.(n) to reduce the length of critical path.

(56) 3.1 Cases for p>2

(57) In some embodiments, for p>2, multipliers may be reduced or eliminated according to similar concept presented above. For example, when p=3, G.sup.(n)=(yrz.sup.(n)).sup.3 may be introduced and determined as follows:

(58) $\begin{array}{cc}\begin{array}{c}{G}^{\left(n\right)}={\left(y-{\mathrm{rz}}^{\left(n-1\right)}-{\mathrm{rs}}^{\left(n-1\right)}\right)}^3\\ ={\left(y-{\mathrm{rz}}^{\left(n-2\right)}-r\mathrm{sgn}\left(s^{\left(n-1\right)}\right)\right)}^3\\ ={\left(y-{\mathrm{rz}}^{\left(n-2\right)}\right)}^3-3{\left(y-{\mathrm{rz}}^{\left(n-2\right)}\right)}^{2}r\mathrm{sgn}\left(s^{\left(n-1\right)}\right)+\\ 3\left(y-{\mathrm{rz}}^{\left(n-2\right)}\right)r^2-{\left(r\mathrm{sgn}\left(s^{\left(n-1\right)}\right)\right)}^3\\ =G^{\left(n-2\right)}-H^{\left(n-2\right)}\mathrm{sgn}\left(s^{\left(n-1\right)}\right)+3{\mathrm{yr}}^2-3r^3{z}^{\left(n-2\right)}-r^3\mathrm{sgn}\left(s^{\left(n-1\right)}\right),\end{array}& \left(15\right)\end{array}$
where H.sup.(n2)=3(yrz.sup.(n2)).sup.2r, which may be computed in a recursive way similar to SE method discussed above without any multipliers. Therefore, c.sup.(n)=|yrz.sup.(n)|.sup.3=|E.sup.(n)| may be computed without any multipliers.
4. Fast Schnorr-Euchner Expansions for l.sub.1 Norm
4.1 Real Case

(59) According to one embodiment of the disclosed technology, a fast SE expansion for l.sub.1 cost function may be developed based on the following recursive equations:
c.sup.(n)=c.sup.(n2)+|r|(16)
z.sup.(n)=z.sup.(n2)+.sup.(n)(17)
with .sup.(n)=sgn(z.sup.(n2)z.sup.(1))=.sup.(n1).

(60) Table 6 illustrates an exemplified pseudo code of the SE method according to this embodiment. In this embodiment, the SE expansion method may eliminate the multiplier and is very simple to implement.

(61) TABLE-US-00006 TABLE 6 Proposed Fast SE for cost. SE Initialization Input: y, r Output: z.sup.(0), z.sup.(1), c.sup.(0), c.sup.(1), .sup.(1) Line 1 z.sup.(0) = z.sup.(1) = y/r Line 2 .sup.(1) = sgn(z.sup.(1) y/r) Line 3 c.sup.(1) =| y rz.sup.(1) | Line 4 c.sup.(0) = c.sup.(1) SE Expansion at z.sup.(j), j 2 Input: r, z.sup.(n 2), z.sup.(n 1), c.sup.(n 2), c.sup.(n .sup.1), .sup.(n .sup.1) Output: z.sup.(n .sup.1), z.sup.(n), c.sup.(n .sup.1), c.sup.(n), .sup.(n) Line 1 .sup.(n) = .sup.(n .sup.1) Line 2 z.sup.(n) = z.sup.(n .sup.1) + .sup.(n) Line 3 c.sup.(n) = c.sup.(n .sup.2) + | r |

(62) As illustrated in Table 6, for the initialization, with z.sup.(0)=y/r and c.sup.(0)=|yrz.sup.(1)|, the SE method may yield the exactly same sequence of z.sup.(j) and c.sup.(j) as the original SE method.

(63) Table 7 illustrates an exemplified pseudo code of the SE method using early evaluation. Here, the performance of the SE method may be improved by performing early evaluation on z.sup.(n) by calculating .sup.(n) in earlier stage.

(64) TABLE-US-00007 TABLE 7 Proposed Fast SE for l.sub.1 cost with early evaluation. SE Initialization Input: y, r Output: z.sup.(0), z.sup.(1), c.sup.(0), c.sup.(1), .sup.(2) Line 1 z.sup.(0) = z.sup.(1) = y/r Line 2 .sup.(2) = sgn(y/r z.sup.(1)) Line 3 c.sup.(1) =| y rz.sup.(1) | Line 4 c.sup.(0) = c.sup.(1) SE Expansion at z.sup.(j) , j 2 Input: r, z.sup.(n 2), z.sup.(n 1), c.sup.(n 2), c.sup.(n 1), .sup.(n) Output: z.sup.(n .sup.1), z.sup.(n), c.sup.(n 1), c.sup.(n), .sup.(n + 1) Line 1 .sup.(n + 1) = .sup.(n) Line 2 z.sup.(n) = z.sup.(n 1) + .sup.(n) Line 3 c.sup.(n) = c.sup.(n 2) + | r |

(65) In some embodiments, by exploiting .sup.(n)=sgn(z.sup.(n2)z.sup.(n1)), n3, .sup.(n) may be removed from SE method for l.sub.1 cost at the cost of possible longer latency.

(66) 4.2 Complex Case

(67) According to one embodiment of the disclosed technology, a complex SE expansion method for l.sub.1 norm cost may be implemented in a manner such that by checking some simple conditions, the sequence of SE expansion for l.sub.1 cost may be uniquely determined without maintaining the candidate list.

(68) In this embodiment, the cost function may be computed according to the following equation:

(69) $\begin{array}{c}c={.Math.y-\mathrm{rz}.Math.}_1\\ =.Math.\left[y\right]-r\left[z\right].Math.+.Math.I\left[y\right]-rI\left[z\right].Math.,\end{array}$
Where y may be a complex number, r0 is a real number, z is an unknown Gaussian integer in the form of +j, is the integer set, j={square root over (1)}, c is the cost, and [.Math.] and I[.Math.] denote the real and imaginary parts of a variable, respectively.

(70) The first SE solution may be obtained as
z.sup.(1)=y/r,
c.sup.(1)=|yrz.sup.(1)|.sub.1,

(71) In this embodiment, by denoting .sub.1=|[y]r[z.sup.(1)]|, .sub.2=|I[y]rI[z.sup.(1)]|, .sub.1=sgn([y]/r[z.sup.(1)]), and .sub.2=sgn(I[y]/rrI[z.sup.(1)]), SE solutions may be computed according to the following propositions.

(72) Proposition 1

(73) The 2nd and 3rd SE solutions may be determined as

(74) $\begin{array}{cc}{z}^{\left(2\right)}=\{\begin{array}{cc}{z}^{\left(1\right)}+{}_1,& \mathrm{if}{}_1>{}_2\\ z^{\left(1\right)}+{}_{2}j,& o.w.\end{array}& \left(18\right)\\ c^{\left(2\right)}=\{\begin{array}{cc}.Math.r.Math.-{}_1+{}_2,& \mathrm{if}{}_1>{}_2\\ {}_1+.Math.r.Math.-{}_2,& o.w.\end{array}& \left(19\right)\\ z^{\left(3\right)}=\{\begin{array}{cc}{z}^{\left(1\right)}+{}_{2}j,& \mathrm{if}{}_1>{}_2\\ z^{\left(1\right)}+{}_1,& o.w.\end{array}& \left(20\right)\\ c^{\left(3\right)}=\{\begin{array}{cc}{}_1+.Math.r.Math.-{}_2,& \mathrm{if}{}_1>{}_2\\ .Math.r.Math.-{}_1+{}_2,& o.w.\end{array}& \left(21\right)\end{array}$

(75) FIG. 6 illustrates the 2nd and 3rd SE solutions determined according to Proposition 1. In FIG. 6, denotes y/r.

(76) Proposition 2

(77) If |r|<2.sub.1+2.sub.2, the 4th SE solution may be determined by
z.sup.(4)=z.sup.(1)+.sub.1+.sub.2j,(22)
c.sup.(4)=2|r|.sub.1.sub.2,(23)
and the 5th and 6th SE solutions are in the set
z.sup.(5),z.sup.(6){z.sup.(1).sub.1,z.sup.(1).sub.2j}(24)
with the same cost |r|+.sub.1+.sub.2. Otherwise, if |r|>2.sub.1+2.sub.2, the 4th and 5th SE solutions are in the set
z.sup.(4),z.sup.(5){z.sup.(1).sub.1,z.sup.(1).sub.2j}(25)
with the cost |r|+.sub.1+.sub.2, and the 6th SE solution is given by
z.sup.(6)=z.sup.(1)+.sub.1+.sub.2j,(26)
c.sup.(6)=2|r|.sub.1.sub.2.(27)

(78) FIG. 7 provides an illustration of the decision boundary |r|<2.sub.1+2.sub.2 according to this embodiment, where the possible solutions are shown by solid circles and x sign.

(79) A sequence of complex SE expansions for l.sub.1 norm based on the conditions .sub.1.sub.2 and |r|2.sub.1+2.sub.2 may be determined.

(80) Proposition 3

(81) If |r|<2.sub.1+2.sub.2, the sequence of complex SE expansions may be determined by
z.sup.(1),z.sup.(2),z.sup.(3),z.sup.(4),layer 1
{z.sup.(1).sub.1,z.sup.(1).sub.2j},{z.sup.(2)+.sub.2,1,z.sup.(2)+.sub.2,2j},
{z.sup.(3)+.sub.3,1,z.sup.(3)+.sub.3,2j},{z.sup.(4)+.sub.1,z.sup.(4)+.sub.2j},layer 2
.
.
.
{z.sup.(1)i.sub.1k.sub.2j|i+k=l1,i0,k0},
{z.sup.(2)+i.sub.2,1+k.sub.2,2j|i+k=l1,i0,k0},
{z.sup.(3)+i.sub.3,1+k.sub.3,2j|i+k=l1,i0,k0},
{z.sup.(4)+i.sub.1+k.sub.2j|i+k=l1,i0,k0},layer l
.
.
.
and the costs are
c.sup.(1),c.sup.(2),c.sup.(3),c.sup.(4),layer 1
c.sup.(1)+|r|,c.sup.(2)+|r|,c.sup.(3)+|r|,c.sup.(4)+|r|,layer 2
.
.
.
c.sup.(1)+(l1)|r|,c.sup.(2)+(l1)|r|,c.sup.(3)+(l1)|r|,c.sup.(4)+(l1)|r|,layer l
.
.
.
where the expansions with smaller layers may have smaller cost than those with higher layers, the SE solutions may be grouped in {.Math.} if they have the same cost, and

(82) $\begin{array}{cc}{}_{2,1}=\{\begin{array}{cc}{}_1,& \mathrm{if}{}_1>{}_2\\ -{}_1,& o.w.\end{array}& \left(28\right)\\ {}_{2,2}=\{\begin{array}{cc}-{}_2,& \mathrm{if}{}_1>{}_2\\ {}_2,& o.w.\end{array}& \left(29\right)\\ {}_{3,1}=\{\begin{array}{cc}-{}_1,& \mathrm{if}{}_1>{}_2\\ {}_1,& o.w.\end{array}& \left(30\right)\\ {}_{3,2}=\{\begin{array}{cc}{}_2,& \mathrm{if}{}_1>{}_2\\ -{}_2,& o.w.\end{array}& \left(31\right)\end{array}$

(83) If |r|>2.sub.1+2.sub.2, the sequence of complex SE expansions may be given by
z.sup.(1),layer 0
z.sup.(2),z.sup.(3),z.sup.(4),z.sup.(5),z.sup.(6)layer 1
{z.sup.(2)+.sub.2,1,z.sup.(2)+.sub.2,2j},{z.sup.(3)+.sub.3,1,z.sup.(3)+.sub.3,2j},
{z.sup.(1)2.sub.1,z.sup.(1).sub.1.sub.2j,z.sup.(1)2.sub.2j},{z.sup.(4)+.sub.1,z.sup.(4)+.sub.2j},layer 2
.
.
.
{z.sup.(2)+i.sub.2,1+k.sub.2,2j|i+k=l1,i0,k0},
{z.sup.(3)+i.sub.3,1+k.sub.3,2j|i+k=l1,i0,k0},
{z.sup.(1)i.sub.1k.sub.2j|i+k=l,i0,k0},
{z.sup.(6)+i.sub.1+k.sub.2j|i+k=l1,i0,k0},layer l
.
.
.
and the costs are
c.sup.(1),layer 0
c.sup.(2),c.sup.(3),c.sup.(4),c.sup.(5),c.sup.(6),layer 1
c.sup.(2)+|r|,c.sup.(3)+|r|,c.sup.(1)+2|r|,c.sup.(6)+|r|,layer 2
.
.
.
c.sup.(2)+(l1)|r|,c.sup.(3)+(l1)|r|,c.sup.(1)+l|r|,c.sup.(6)+(l1)|r|,layer l
.
.
.

(84) FIG. 8 illustrates exemplary layers of SE expansions when |r|<2.sub.1+2.sub.2 according to this embodiment.

(85) 4.3 SE Methods with Bound Constraint

(86) According to some embodiments of the disclosed technology, the value of z may be bounded as follows:
c=|yrz|,s.t.,azb,(32)
where a and b are integers indicating the lower and upper bound of z. The disclosed technology may implement the SE method with the bound constraint.
5. Fast SE Expansion for l.sub.2 Norm

(87) According to one embodiment of the disclosed technology, a complex SE expansion method for l.sub.2 norm cost may generate the first 9 complex SE expansions with some simple conditions. By checking the conditions, the first 9 complex SE expansions may be uniquely determined. The checking equations may only require shifting and addition operations, which are very easy to be implemented in hardware.

(88) In this embodiment, the cost function may be computed according to the following equation:

(89) 0$\begin{array}{c}c={.Math.y-\mathrm{rz}.Math.}^2\\ ={\left(\left[y\right]-r\left[z\right]\right)}^2+{\left(I\left[y\right]-rI\left[z\right]\right)}^2,\end{array}$
Where y may be a complex number, r0 is a real number, z is an unknown Gaussian integer in the form of +j, is the integer set, j={square root over (1)}, c is the cost, and [.Math.] and I[.Math.] denote the real and imaginary parts of a variable, respectively.

(90) The first SE solution may be obtained as
z.sup.(1)=y/r,
c.sup.(1)=|yrz.sup.(1)|.sup.2,

(91) To simplify the equations in deriving the following 2nd to 9th SE solutions, denote .sub.1=|[y]r[z.sup.(1)]|, .sub.2=|I[y]rI[z.sup.(1)]|, .sub.1=sgn([y]/r[z.sup.(1)]), and .sub.2=sgn(I[y]/rI[z.sup.(1)]). The 2nd to 9th SE solutions may be determined according to the following propositions:

(92) Proposition 4

(93) The 2nd and 3rd SE solutions may be determined as

(94) $\begin{array}{cc}{z}^{\left(2\right)}=\{\begin{array}{cc}{z}^{\left(1\right)}+{}_1,& \mathrm{if}{}_1>{}_2\\ z^{\left(1\right)}+{}_{2}j,& o.w.\end{array}& \left(33\right)\\ c^{\left(2\right)}=\{\begin{array}{cc}{\left(.Math.r.Math.-{}_1\right)}^2+{}_2^2,& \mathrm{if}{}_1>{}_2\\ {}_1^2+{\left(.Math.r.Math.-{}_2\right)}^2,& o.w.\end{array}& \left(34\right)\\ z^{\left(3\right)}=\{\begin{array}{cc}{z}^{\left(1\right)}+{}_{2}j,& \mathrm{if}{}_1>{}_2\\ z^{\left(1\right)}+{}_1,& o.w.\end{array}& \left(35\right)\\ c^{\left(3\right)}=\{\begin{array}{cc}{}_1^2+{\left(.Math.r.Math.-{}_2\right)}^2,& \mathrm{if}{}_1>{}_2\\ {\left(.Math.r.Math.-{}_1\right)}^2+{}_2^2,& o.w.\end{array}& \left(36\right)\end{array}$

(95) An illustration of the 2nd and 3rd SE solutions is given in FIG. 6.

(96) Without loss of generality, the following propositions are based on the assumption that .sub.1>.sub.2.

(97) Proposition 5

(98) The 4th SE solution is given by

(99) $\begin{array}{cc}{z}^{\left(4\right)}=\{\begin{array}{cc}{z}^{\left(1\right)}+{}_1+{}_{2}j,& \mathrm{if}2{}_1+4{}_2>.Math.r.Math.\\ z^{\left(1\right)}-{}_{2}j,& o.w.\end{array}& \left(37\right)\\ c^{\left(4\right)}=\{\begin{array}{cc}{\left(.Math.r.Math.-{}_1\right)}^2+{\left(.Math.r.Math.-{}_2\right)}^2,& \mathrm{if}2{}_1+4{}_2>.Math.r.Math.\\ {}_1^2+{\left(.Math.r.Math.+{}_2\right)}^2,& o.w.\end{array}& \left(38\right)\end{array}$

(100) FIG. 9 provides an illustration of a decision boundary of the 4th SE solution according to this proposition, where the possible solutions for the 4th are illustrated by x sign.

(101) Proposition 6

(102) If 2.sub.1+4.sub.2>|r|, the 5th SE solution may be determined as
z.sup.(5)=z.sup.(1).sub.2j,(39)
c.sup.(5)=.sub.1.sup.2+(|r|+.sub.2).sup.2,(40)
else the 5th SE solution is

(103) $\begin{array}{cc}{z}^{\left(5\right)}=\{\begin{array}{cc}{z}^{\left(1\right)}+{}_1+{}_{2}j,& \mathrm{if}4{}_1+2{}_2>.Math.r.Math.\\ z^{\left(1\right)}-{}_1,& o.w.\end{array}& \left(41\right)\\ c^{\left(5\right)}=\{\begin{array}{cc}{\left(.Math.r.Math.-{}_1\right)}^2+{\left(.Math.r.Math.-{}_2\right)}^2,& \mathrm{if}4{}_1+2{}_2>.Math.r.Math.\\ {\left(.Math.r.Math.+{}_1\right)}^2+{}_2^2,& o.w.\end{array}& \left(42\right)\end{array}$

(104) FIG. 10 provides an illustration of the 5th SE solution when 2.sub.1+4.sub.2<|r|, where possible solutions for the 5.sup.th are illustrated by x sign.

(105) Proposition 7

(106) If 4.sub.1+2.sub.2<|r|, the 6th SE solution may be determined as follows:
z.sup.(6)=z.sup.(1)+.sub.1+.sub.2j,(43)
c.sup.(6)=(|r|.sub.1).sup.2+(|r|.sub.2).sup.2,(44)
else the 6th SE solution is

(107) $\begin{array}{cc}{z}^{\left(6\right)}=\{\begin{array}{cc}{z}^{\left(1\right)}+{}_1+{}_{2}j,& \mathrm{if}4{}_1+2{}_2>.Math.r.Math.\\ z^{\left(1\right)}-{}_1,& o.w.\end{array}& \left(45\right)\\ c^{\left(6\right)}=\{\begin{array}{cc}{\left(.Math.r.Math.-{}_1\right)}^2+{\left(.Math.r.Math.+{}_2\right)}^2,& \mathrm{if}4{}_1+2{}_2>.Math.r.Math.\\ {\left(.Math.r.Math.+{}_1\right)}^2+{}_2^2,& o.w.\end{array}& \left(46\right)\end{array}$

(108) FIG. 11 provides an illustration of the 6th SE solution when 4.sub.1+2.sub.2>|r|, where the possible solutions for the 6.sup.th are illustrated by x sign.

(109) With regard to propositions 4-7, the first 6 SE solutions may be uniquely determined by the following conditions: .sub.1.sub.2, 2.sub.1+4.sub.2|r|, 4.sub.1+2.sub.2|r|, 4.sub.12.sub.2|r|, and 2.sub.14.sub.2|r|. According to the disclosed technology, the multiplications with 2 and 4 may be implemented as shifting operations. As such, all these conditions may be efficiently checked in hardware implementation.

(110) Proposition 8

(111) The 7th SE solution may be determined as follows:

(112) $\begin{array}{cc}{z}^{\left(7\right)}=\{\begin{array}{cc}{z}^{\left(1\right)}-{}_1,& \mathrm{if}4{}_1+2{}_2>.Math.r.Math.\\ z^{\left(1\right)}+{}_1+{}_{2}j,& o.w.\end{array}& \left(47\right)\\ c^{\left(7\right)}=\{\begin{array}{cc}{\left(.Math.r.Math.+{}_1\right)}^2+{}_2^2,& \mathrm{if}4{}_1+2{}_2>.Math.r.Math.\\ {\left(.Math.r.Math.-{}_1\right)}^2+{\left(.Math.r.Math.-{}_2\right)}^2,& o.w.\end{array}& \left(48\right)\end{array}$
Proposition 9

(113) The 8th SE solution may be determined as follows:

(114) $\begin{array}{cc}{z}^{\left(8\right)}=\{\begin{array}{cc}{z}^{\left(1\right)}+{}_1,& \mathrm{if}.Math.r.Math.<3{}_1-{}_2\\ z^{\left(1\right)}-{}_1+{}_{2}j,& o.w.\end{array}& \left(49\right)\\ c^{\left(8\right)}=\{\begin{array}{cc}{\left(2.Math.r.Math.-{}_1\right)}^2+{}_2^2,& \mathrm{if}.Math.r.Math.<3{}_1-{}_2\\ {\left(.Math.r.Math.+{}_1\right)}^2+{\left(.Math.r.Math.-{}_2\right)}^2,& o.w.\end{array}& \left(50\right)\end{array}$

(115) FIG. 12 illustrates a decision boundary of the 8th SE solution, where the 7th SE solution is in solid circles, and the possible solutions for the 8th are shown by x sign.

(116) Proposition 10

(117) If |r|<3.sub.1.sub.2, then the 9th SE solution may be determined as follows:
z.sup.(9)=z.sup.(1).sub.1+.sub.2j,(51)
c.sup.(9)=(|r|+.sub.1).sup.2+(|r|.sub.2).sup.2,(52)
else the 9th SE solution is given by

(118) $\begin{array}{cc}{z}^{\left(9\right)}=\{\begin{array}{cc}{z}^{\left(1\right)}+2{}_1,& \mathrm{if}.Math.r.Math.<3{}_1+{}_2\\ z^{\left(1\right)}-{}_1-{}_{2}j,& o.w.\end{array}& \left(53\right)\\ c^{\left(9\right)}=\{\begin{array}{cc}{\left(2.Math.r.Math.-{}_1\right)}^2+{}_2^2,& \mathrm{if}.Math.r.Math.<3{}_1+{}_2\\ {\left(.Math.r.Math.+{}_1\right)}^2+{\left(.Math.r.Math.+{}_2\right)}^2,& o.w.\end{array}& \left(54\right)\end{array}$

(119) FIG. 13 provides an illustration of a decision boundary of the 9th SE solution when |r|>3.sub.1.sub.2, where the 8.sup.th SE solution is shown by solid circles, and the possible solutions for the 9.sup.th are shown by x sign.

(120) It is noted that the disclosed technology described above may be further applied to obtain the kth (k>9) SE solutions.

(121) 6 Hardware Implementation and Synthesized Results

(122) Various embodiments of the SE methods of the disclosed technology may be implemented in MIMO communication systems. According to one embodiment of the disclosed technology, the SE methods described herein may be implemented with hardware, such as a VLSI implementation. In some instances, an integrated circuit that implements the SE methods may be part of a MIMO communication system. According to another embodiment of the disclosed technology, the SE methods described herein may be implemented with software on a reconfigurable processor.

(123) In some embodiments of the disclosed invention, the various SE methods may be implemented as logic instructions stored on memory that can be executed by a processor. The instructions can be configured to cause the system to perform the various steps of the various SE methods described herein.

(124) An exemplary embodiment of the disclosed invention may provide a MIMO communication system comprising a plurality of input terminals, a processor, and logic. The various embodiments of the disclosed technology may comprise many types of input terminals capable of receiving an input signal, including, but not limited to, radio-frequency signals, electromagnetic signals, optical signals, and the like. The input terminals can be many input terminals known in the art. In an exemplary embodiment of the disclosed technology, the input terminals comprise antennas. The logic may be stored in memory. The memory may be many types of memory known in the art. In an exemplary embodiment of the disclosed invention, the logic may be stored in a non-transitory computer readable media. In various embodiments of the disclosed invention, the processor may be configured to execute the logic. When executed, the logic may be configured to cause the MIMO system to perform one or more of the steps of the SE methods described herein.

(125) 6.1 Implementation for MR1 and MR2

(126) According to some aspects of the disclosed technology, SE methods illustrated in Tables 1-5 may be implemented in Verilog. VLSI implementations of the SE methods may be synthesized on Xilinx XC7VX690T-2FFG1761C FPGA board. The implementations may be synthesized using Xilinx XST. All the methods discussed herein may be implemented in the form of combinatorial logic. Tables 8-9 list the maximum frequencies (1/latencies of all logics) of the SE methods discussed herein after place and route. In Tables 8-9, the fixed-point setting for all real numbers (e.g., c.sup.(n), A.sup.(n), B.sup.(n)) are in the form of [a,b], where a is the length of integer bits and b is the length of fractional bits, while the fixed-point setting for all integer numbers (e.g., z.sup.(n), s.sup.(n)) are in the form of [a], where a is the length of integer bits. As shown in Tables 8-9, the proposed SE methods of the disclosed technology have about 2-5 times maximum frequency improvement over the original SE method. As shown in Tables 8-9, for p=1, the maximum frequency of the proposed SE method with MR1 may reach 300 MHz, and for p=2, the maximum frequency of the proposed SE method with MR2 may also reach around 300 MHz.

(127) TABLE-US-00008 TABLE 8 Maximum achievable frequency of various SE methods for p = 1. Fixed-point setting Original MR1 w.o. EE MR1 with EE MR2 FP [8, 8] INT [8] 163.880 MHz 206.696 MHz 341.646 MHz N/A FP [10, 10] INT [10] 148.942 MHz 196.96 MHz 324.254 MHz N/A FP [16, 16] INT [16] 118.539 MHz 202.922 MHz 288.101 MHz N/A

(128) TABLE-US-00009 TABLE 9 Maximum achievable frequency of various SE methods for p = 2. MR1 MR1 Fixed-point setting Original w.o. EE with EE MR2 FP [8, 8] INT [8] 127.080 153.139 212.404 298.685 MHz MHz MHz MHz FP [10, 10] INT [10] 100.603 130.770 172.741 280.662 MHz MHz MHz MHz FP [16, 16] INT [16] 63.946 98.029 118.793 320.924 MHz MHz MHz MHz
6.2 Implementation for l.sub.1 Norm

(129) Different SE methods illustrated in Tables 1 and 7 may be implemented in Verilog. The VLSI implementations may be synthesized on Xilinx XC7VX690T-2FFG1761C FPGA board. The implementations may be synthesized using Xilinx XST. All the methods described herein may be implemented in the form of combinatorial logic. Table 10 lists the maximum frequencies (1/latencies of all logics) after place and route. Similar to Tables 8-9, the fixed-point setting for all real numbers (e.g., c.sup.(n), A.sup.(n), B.sup.(n)) are in the form of [a,b], where a is the length of integer bits and b is the length of fractional bits, while the fixed-point setting for all integer numbers (e.g., z.sup.(n), s.sup.(n)) are in the form of [a], where a is the length of integer bits. As illustrated in Table 10, the proposed fast l.sub.1 SE method has about 3 times maximum frequency improvement over the original SE method. In particular, for p=1, the maximum frequency of the proposed SE method may reach around 400 MHz.

(130) TABLE-US-00010 TABLE 10 Maximum achievable frequency of various SE methods. Fixed-point setting Original Proposed Fast SE FP [8, 8] INT [8] 163.880 MHz 535.906 MHz FP [10, 10] INT [10] 148.942 MHz 442.282 MHz FP [16, 16] INT [16] 118.539 MHz 379.75 z

(131) FIG. 14 is a flow-diagram 1400 of an example method, in accordance with an exemplary embodiment of the disclosed technology. In block 1402, the method 1400 may include receiving, by a plurality of input terminals, a plurality of input signals. Each input signal may transmit a symbol. In block 1404, the method 1400 may include identifying a list of possible symbols that may be transmitted by each input signal. In block 1406, the method 1400 may include determining a cost value for each possible symbol based on a cost function. The cost function may be implemented without requiring a multiplier. In block 1408, the method 1400 may include identifying the possible symbol with a lowest cost value as the transmitted symbol.

(132) In one example implementation, the cost function may be an l.sub.1 cost function. In another example implementation, the cost function may be an l.sub.2 cost function. In some implementations, the cost function may be based on a recursive equation. In some instances, the cost function may have a real domain. In some examples, the cost function may have a complex domain.

(133) In one example implementation, the l.sub.2 cost function may generate a first 9 complex SE expansions. The method of the disclosed technology may check conditions for the first 9 complex SE expansions. In some example implementations, the checking conditions may be implemented by shifting and addition operations.

(134) According to some aspects of the disclosed technology, the list of possible symbols may be arranged in an ascending order of their cost values.

(135) In one example implementation, the cost function may have a mathematical representation of
c=|yrz|.sup.p,
wherein y is the output, r is a system implementing the SE method, z is an input, c is the cost, and an integer p denotes a l.sub.p-norm; wherein when p=1, the above equation is an l.sub.1 cost function; and wherein when p=2, the above equation is an l.sub.2 cost function.

(136) According to some aspects of the disclose technology, multiplication in the cost function may be implemented using a multiplexer. In some instances, multiplication in the cost function may also be implemented using a shift register.

(137) It is to be understood that the embodiments and claims disclosed herein are not limited in their application to the details of construction and arrangement of the components set forth in the description and illustrated in the drawings. Rather, the description and the drawings provide examples of the embodiments envisioned. The embodiments and claims disclosed herein are further capable of other embodiments and of being practiced and carried out in various ways. Also, it is to be understood that the phraseology and terminology employed herein are for the purposes of description and should not be regarded as limiting the claims. For instance, the term exemplary used herein does not mean best mode, but rather, example.

(138) Accordingly, those skilled in the art will appreciate that the conception upon which the application and claims are based may be readily utilized as a basis for the design of other structures, methods, and systems for carrying out the several purposes of the embodiments and claims disclosed in this application. It is important, therefore, that the claims be regarded as including such equivalent constructions.

(139) Furthermore, the purpose of the foregoing Abstract is to enable the public generally, and especially including the practitioners in the art who are not familiar with patent and legal terms or phraseology, to determine quickly from a cursory inspection the nature and essence of the technical disclosure of the application. The Abstract is neither intended to define the claims of the application, nor is it intended to be limiting to the scope of the claims in any way.