MIMO signal symbol detection and search method, decoding circuit and receiving antenna system

Abstract

A MIMO symbol detection and search method, a decoding circuit and a receiving antenna system are provided. The signal detection and search method includes the following steps. A symbol search tree is obtained, and a plurality of candidate symbols at each layer of the symbol search tree are sorted. The candidate symbols are traversed in sequence at each layer of the symbol search tree. At each layer of the symbol search tree, if a cumulative partial Euclidean distance is greater than or equal to a threshold, un-scanned candidate symbols are excluded. If the cumulative partial Euclidean distance is less than the threshold, the threshold is updated by the cumulative partial Euclidean distance. When all of the candidate symbols have been calculated, an estimated symbol combination is outputted, and the scan of the symbol search tree is terminated.

Claims

1. A Multi-Input Multi-Output (MIMO) symbol detection and search method, comprising: obtaining a symbol search tree, and sorting a plurality of candidate symbols at each layer of the symbol search tree; traversing the candidate symbols in sequence at each layer of the symbol search tree; excluding un-scanned candidate symbols at each layer of the symbol search tree, if a cumulative partial Euclidean distance is greater than or equal to a threshold; updating the threshold by the cumulative partial Euclidean distance, if the cumulative partial Euclidean distance is less than the threshold; and outputting an estimated symbol combination, and terminating scan of the symbol search tree, when all of the candidate symbols have been calculated.

2. The MIMO symbol detection and search method according to claim 1, wherein the candidate symbols are sorted according to a plurality of geometric distances between the candidate symbols and an estimation symbol.

3. The MIMO symbol detection and search method according to claim 2, wherein the candidate symbols are sorted according to the geometric distances from low to high.

4. The MIMO symbol detection and search method according to claim 1, wherein the candidate symbols are defined via an Amplitude and Phase-Shift Keying modulation (APSK modulation).

5. The MIMO symbol detection and search method according to claim 1, wherein the candidate symbols are defined via a Quadrature Amplitude Modulation (QAM).

6. The MIMO symbol detection and search method according to claim 1, wherein the candidate symbols are searched via a Depth-First-Search (DFS) algorithm.

7. The MIMO symbol detection and search method according to claim 1, wherein a leftmost path of the symbol search tree forms an initial solution.

8. A decoding circuit, comprising: a sorting unit, configured to sort a plurality of candidate symbols at each layer of a symbol search tree; a controlling unit, configured to traverse the candidate symbols in sequence at each layer of the symbol search tree; a distance calculating unit, configured to calculate a cumulative partial Euclidean distance, wherein at each layer of the symbol search tree, if a cumulative partial Euclidean distance is greater than or equal to a threshold, the controlling unit excludes a plurality of un-scanned candidate symbols; and a threshold updating unit, wherein if the cumulative partial Euclidean distance is less than the threshold, the threshold updating unit updates the threshold by the cumulative partial Euclidean distance, and when all of the candidate symbols have been calculated, the controlling unit outputs an estimated symbol combination, and terminates scan of the symbol search tree.

9. The decoding circuit according to claim 8, further comprising: an estimating unit, configured to estimate an estimation symbol according to a receiving signal, wherein the sorting unit sorts the candidate symbols according to a plurality of geometric distances between the candidate symbols and an estimation symbol.

10. The decoding circuit according to claim 9, wherein the candidate symbols are sorted according to the geometric distances from low to high.

11. The decoding circuit according to claim 8, wherein the candidate symbols are defined via an Amplitude and Phase-Shift Keying modulation (APSK modulation).

12. The decoding circuit according to claim 8, wherein the candidate symbols are defined via a Quadrature Amplitude Modulation (QAM).

13. The decoding circuit according to claim 8, wherein the controlling unit searches the candidate symbols via a Depth-First-Search (DFS) algorithm.

14. The decoding circuit according to claim 8, wherein a leftmost path of the symbol search tree forms an initial solution.

15. A receiving antenna system, comprising: a receiving antenna; a RF combining circuit; a plurality of RF chains, connected to the RF combining circuit; a plurality of analog to digital circuits, respectively connected to the RF chains; and a baseband combining circuit, connected to the analog to digital circuits, wherein the baseband combining circuit includes a decoding circuit, and the decoding circuit includes: a sorting unit, configured to sort a plurality of candidate symbols at each layer of a symbol search tree; a controlling unit, configured to traverse the candidate symbols in sequence at each layer of the symbol search tree; a distance calculating unit, configured to calculate a cumulative partial Euclidean distance, wherein at each layer of the symbol search tree, if a cumulative partial Euclidean distance is greater than or equal to a threshold, the controlling unit excludes a plurality of un-scanned candidate symbols; and a threshold updating unit, wherein if the cumulative partial Euclidean distance is less than the threshold, the threshold updating unit updates the threshold by the cumulative partial Euclidean distance, and when all of the candidate symbols have been calculated, the controlling unit outputs an estimated symbol combination, and terminates scan of the symbol search tree.

16. The receiving antenna system according to claim 15, wherein the decoding circuit further comprising: an estimating unit, configured to estimate an estimation symbol according to a receiving signal, wherein the sorting unit sorts the candidate symbols according to a plurality of geometric distances between the candidate symbols and an estimation symbol.

17. The receiving antenna system according to claim 16, wherein the candidate symbols are sorted according to the geometric distances from low to high.

18. The receiving antenna system according to claim 15, wherein the candidate symbols are defined via an Amplitude and Phase-Shift Keying modulation (APSK modulation).

19. The receiving antenna system according to claim 15, wherein the candidate symbols are defined via a Quadrature Amplitude Modulation (QAM).

20. The receiving antenna system according to claim 15, wherein the controlling unit searches the candidate symbols via a Depth-First-Search (DFS) algorithm.

21. The receiving antenna system according to claim 15, wherein a leftmost path of the symbol search tree forms an initial solution.

Description

BRIEF DESCRIPTION OF THE DRAWINGS

(1) FIG. 1 shows a transmitting antenna system and a receiving antenna system according to an embodiment.

(2) FIG. 2 shows a process of the symbol detection and search according to an embodiment.

(3) FIG. 3A shows a schematic diagram of 16-APSK encoding according to an embodiment.

(4) FIG. 3B shows a schematic diagram of 32-APSK encoding according to an embodiment.

(5) FIG. 3C shows a schematic diagram of 32-APSK encoding with unequal symbol radius according to an embodiment.

(6) FIG. 4 shows a symbol search tree.

(7) FIG. 5 shows a flowchart of the MIMO symbol detection and search method according to an embodiment.

(8) FIG. 6 shows the symbol search tree sorted according to an embodiment.

(9) FIG. 7A shows the relationship between the candidate symbols and an estimation symbol.

(10) FIG. 7B shows the relationship between the candidate symbols and another estimation symbol.

(11) FIG. 7C shows the relationship between the candidate symbols and another estimation symbol.

(12) FIG. 7D shows the relationship between the candidate symbols and another estimation symbol.

(13) FIG. 8 shows a block diagram of a decoding circuit according to an embodiment.

(14) FIGS. 9A to 9F show search times comparison charts between the present embodiment and the Maximum Likelihood (ML) algorithm applying to the symbol detection and search for four transmitting antennas and four receiving antennas.

(15) FIGS. 10A to 10F show bit error rate comparison charts between the present embodiment and the ML algorithm applying to the symbol detection and search for four transmitting antennas and four receiving antennas.

(16) In the following detailed description, for purposes of explanation, numerous specific details are set forth in order to provide a thorough understanding of the disclosed embodiments. It will be apparent, however, that one or more embodiments may be practiced without these specific details. In other instances, well-known structures and devices are schematically shown in order to simplify the drawing.

DETAILED DESCRIPTION

(17) Please refer to FIG. 1, which shows a transmitting antenna system 900 and a receiving antenna system 100 according to an embodiment. The transmitting antenna system 900 includes a baseband pre-coding circuit 910, a plurality of digital to analog circuits 920, a plurality of RF chains 930, and a RF pre-coding circuit 940 and a plurality of transmitting antennas TA. The digital to analog circuits 920 are connected to the baseband pre-coding circuit 910. The RF chains 930 are respectively connected to the digital to analog circuits 920. The RF pre-coding circuit 940 is connected to the RF chains 930. The transmitting antennas TA are connected to the RF pre-coding circuit 940.

(18) After the wireless signal is sent out via the transmitting antennas TA of the transmitting antenna system 900, it is transmitted to the receiving antenna system 100. The receiving antenna system 100 includes a plurality of receiving antennas RA, a RF combining circuit 110, a plurality of RF chains 120, a plurality of analog to digital circuits 130 and a baseband combining circuit 140. The RF combining circuit 110 is connected to the receiving antennas RA. The RF chains 120 are connected to the RF combining circuit 110. The analog to digital circuits 130 are respectively connected to the RF chains 120. The baseband combining circuit 140 is connected to the analog to digital circuits 130.

(19) The baseband combining circuit 140 includes a decoding circuit 141. The decoding circuit 141 is used to analyze the transmission signal sent by the transmitting antenna system 900.

(20) Please refer to FIG. 2, which shows a process of the symbol detection and search according to an embodiment. First, in the getting procedure P1, the received signal is got and a channel is estimated.

(21) Next, in the decomposition procedure P2, a QR decomposition is performed on the channel.

(22) Then, in the searching procedure P3, a Maximum Likelihood (ML) algorithm is performed for symbol detection and search.

(23) It could be applied to a hard-decision P4 or a soft-decision P6.

(24) In the searching procedure P3, the iterating procedure P5 could be used to improve the accuracy of the soft-decision P6.

(25) In this embodiment, a new search strategy is used to improve the search speed of the searching procedure P3 and the accuracy of the hard-decision P4 and the soft-decision P6 is lossless.

(26) The symbol detection and search method proposed in this embodiment is applicable to the encoding of the Amplitude and Phase-Shift Keying modulation (APSK modulation), and also applicable to the encoding of the Quadrature Amplitude Modulation (QAM).

(27) Please refer to FIGS. 3A to 3C. FIG. 3A shows a schematic diagram of 16-APSK encoding according to an embodiment. FIG. 3B shows a schematic diagram of 32-APSK encoding according to an embodiment.

(28) FIG. 3C shows a schematic diagram of 32-APSK encoding with unequal symbol radius according to an embodiment. The APSK modulation has been widely adopted in the next-generation satellite broadband communication backbone architectures, such as B5G (Beyond 5G). Each point on the FIGS. 3A to 3C is the candidate symbol to be searched. As shown in FIG. 3A to 3C, the modulation dimension of APSK modulation grows geometrically and the signal radius is not fixed, so the search complexity becomes quite high.

(29) Taking M.sub.T transmitting antennas TA and M.sub.R receiving antennas RA as an example, the relationship between the receiving signal and the transmitting signal is as the following equation (1). H is the channel response, s is the transmitted signal vector, y is the received data vector, and n is the noise vector.
Y=Hs+n  (1)

(30) In the above searching procedure P3, it is mainly required to obtain the ŝ in the following equation (2).

(31) $\begin{array}{cc}\hat{s}=\begin{array}{c}\arg \min \\ s\in {\wedge }^{M_T}\end{array}{.Math.y-\mathrm{Hs}.Math.}^2& \left(2\right)\end{array}$

(32) After H is decomposed by the QR decomposition of the following equation (3), ŷ in the following equation (4) could be obtained. R is the upper triangular matrix.

(33) $\begin{array}{cc}H=\left[Q_1{Q}_2\right]\left[\begin{array}{c}R\\ 0\end{array}\right]& \left(3\right)\end{array}$
ŷ=Q.sub.1.sup.Hy  (4)

(34) ŝ in equation (2) could be replaced by the following equation (5).

(35) $\begin{array}{cc}\hat{s}=\begin{array}{c}\arg \min \\ s\in {\wedge }^{M_T}\end{array}{.Math.y-\mathrm{Rs}.Math.}^2& \left(5\right)\end{array}$

(36) Taking four transmitting antennas TA and four receiving antennas RA as an example, each of the receiving antennas RA corresponds to four candidate symbols SS0, SS1, SS2, SS3. ∥ŷ−Rs∥.sup.2 is, for example, the following equation (6).

(37) $\begin{array}{cc}{.Math.\hat{y}-Rs.Math.}^2=.Math.\begin{array}{c}-\left(R_{00}{s}_0+R_{01}{s}_1+R_{02}{s}_2+R_{03}{s}_3\right)\\ \begin{array}{c}\begin{array}{cc}-& \left(R_{11}{s}_1+R_{12}{s}_2+R_{13}{s}_3\right)\end{array}\\ \begin{array}{cc}-& \left(R_{22}{s}_2+R_{23}{s}_3\right)\end{array}\\ \begin{array}{cc}-& \left(R_{33}{s}_3\right)\end{array}\end{array}\end{array}.Math.& \left(6\right)\end{array}$

(38) Please refer to FIG. 4 which shows a symbol search tree TR0. Taking four transmitting antennas TA and four receiving antennas RA as an example, the symbol search tree TR0 has layer 0 to layer 3. The layer 3 represents the four candidate symbols SS0, SS1, SS2, SS3 of s.sub.3. The layer 2 represents the four candidate symbols SS0, SS1, SS2, SS3 of s.sub.2. The layer 1 represents the four candidate symbols SS0, SS1, SS2, SS3 of s.sub.1. The layer 0 represents the four candidate symbols SS0, SS1, SS2, SS3 of s.sub.0. Any path from the layer 3 to the layer 0 constitutes a set of solutions of s.sub.3, s.sub.2, s.sub.1, s.sub.0.

(39) However, if the symbol detection and search are performed in an exhaustive manner, a large amount of computing resources will be consumed and the computing speed will be delayed.

(40) Please refer to FIG. 5, which shows a flowchart of the MIMO symbol detection and search method according to an embodiment. For the convenience of explanation, an example is illustrated via four transmitting antennas TA and four receiving antennas RA. However, the technique of this embodiment is applicable to N transmitting antennas TA and M receiving antennas RA, and N and M are any positive integers greater than or equal to 2. First, in step S110, the symbol search tree TR1 is obtained and the candidate symbols SS0 to SS3 are sorted at each layer of the symbol search tree TR0. Please refer to FIG. 6, which shows the symbol search tree TR1 sorted according to an embodiment. The order of candidate symbols SS0 to SS3 at each layer is not exactly the same.

(41) Please refer to FIG. 7A, which shows the relationship between the candidate symbols SS0 to SS3 and the estimation symbol . As shown in FIG. 7A, there are several geometric distances l.sub.30 to l.sub.33 between the candidate symbols SS0 to SS3 and the estimation symbol . As shown in the layer 3 of FIG. 6, the candidate symbols SS1, SS3, SS0, SS2 are sorted according to geometric distances l.sub.31, l.sub.33, l.sub.30, l.sub.32 from low to high.

(42) Please refer to FIG. 7B, which shows the relationship between the candidate symbols SS0 to SS3 and the estimation symbol . As shown in FIG. 7B, there are several geometric distances l.sub.20 to l.sub.23 between the candidate symbols SS0 to SS3 and the estimation symbol . As shown in the layer 2 of FIG. 6, the candidate symbols SS1, SS0, SS3, and SS2 are sorted according to the geometric distances l.sub.21, l.sub.20, l.sub.23, l.sub.22 from low to high.

(43) Please refer to FIG. 7C, which shows the relationship between the candidate symbols SS0 to SS3 and the estimation symbol . As shown in FIG. 7C, there are several geometric distances l.sub.10 to l.sub.13 between the candidate symbols SS0 to SS3 and the estimation symbol . As shown in the layer 1 of FIG. 6, the candidate symbols SS0, SS2, SS1, SS3 are sorted according to the geometric distances l.sub.10, l.sub.12, l.sub.11, l.sub.13 from low to high.

(44) Please refer to FIG. 7D, which shows the relationship between the candidate symbols SS0 to SS3 and the estimation symbol . As shown in FIG. 7D, there are several geometric distances l.sub.00 to l.sub.03 between the candidate symbols SS0 to SS3 and the estimation symbol . As shown in the layer 0 of FIG. 6, the candidate symbols SS3, SS2, SS1, SS0 are sorted according to the geometric distances l.sub.03, l.sub.02, l.sub.01, l.sub.00 from low to high.

(45) After sorting in the above manner, the symbol search tree TR1 as shown in FIG. 6 could be obtained. From the layer 3 to the layer 0 of the symbol search tree TR1, the leftmost path of the symbol search tree TR1 forms an initial solution.

(46) Next, in step S120, in each layer of the symbol search tree TR1, the candidate symbols SS0 to SS3 are traversed in sequence. For example, in this embodiment, the candidate symbols SS0 to SS3 are searched via a Depth-First-Search (DFS) algorithm. After obtaining the initial solution (i.e. the leftmost path of the symbol search tree TR1), the bottom layer (i.e. the layer 0) is searched first. When searching at the layer 0, the searching is performed in the order of the candidate symbols SS3, SS2, SS1, SS0. When searching at the layer 1, the searching is performed in the order of the candidate symbols SS0, SS2, SS1, SS3. When searching at the layer 2, the searching is performed in the order of the candidate symbols SS1, SS0, SS3, SS2. When searching at the layer 3, the searching is performed in the order of the candidate symbols SS1, SS3, SS0, SS2.

(47) In step S130, whether all of the candidate symbols SS0, SS2, SS1, SS3 at all of the layers are traversed is determined. If all of the candidate symbols SS0, SS2, SS1, SS3 at all of the layers are traversed, the process proceeds to step S140; if not all of the candidate symbols SS0, SS2, SS1, SS3 at all of the layers are traversed, the process proceeds to step S150.

(48) In the step S140, an estimated symbol combination is outputted, and the scan of the symbol search tree TR1 is terminated.

(49) In step S150, during the scanning at each layer of the symbol search tree TR1, whether the cumulative partial Euclidean distance PED is greater than or equal to a threshold SC is determined. If the cumulative partial Euclidean distance PED is greater than or equal to the threshold SC, the process proceeds to step S160; if the cumulative partial Euclidean distance PED is less than the threshold SC, the process proceeds to step S170.

(50) The initial value of the threshold SC is infinite. After the initial solution is obtained, the threshold SC is updated to the cumulative partial Euclidean distance PED of the initial solution. Taking FIG. 6 as an example, the cumulative partial Euclidean distance PED of the initial solution is the combination of the geometric distances l.sub.31, l.sub.21, l.sub.10, l.sub.03.

(51) In step S160, when scanning at each layer of the symbol search tree TR1, some of the candidate symbols SS0 to SS3 that unscanned are excluded.

(52) In step S170, the threshold SC is updated by the cumulative partial Euclidean distance PED.

(53) Taking FIG. 6 as an example, the node N1 is the initial solution. The current threshold SC is the cumulative partial Euclidean distance PED of the node N1. After searching for node N1, it could be found that the cumulative partial Euclidean distance PED of the node N2 is greater than the threshold SC, so the candidate symbols SS2, SS1, SS0 in the sibling nodes that have not been scanned are excluded.

(54) After the node N3 is searched, it could be found that the cumulative partial Euclidean distance PED of the node N4 is greater than the threshold SC, so the candidate symbols SS2, SS1, SS3 in the sibling nodes that have not been scanned are excluded.

(55) After searching for the node N5, it could be found that the cumulative partial Euclidean distance PED of the node N6 is less than the threshold SC, so the threshold SC is updated by the cumulative partial Euclidean distance PED of the node N6, and the search is continued.

(56) According to the above method, in the search process, many candidate symbols in the sibling nodes that have not been scanned are excluded, so a lot of computing resources could be saved, and the search speed could be greatly increased. In addition, the cumulative partial Euclidean distance PED of the excluded candidate symbols will not be lower than the threshold SC, so the best solution will not be excluded, and the search accuracy is lossless.

(57) Please refer to FIG. 8, which shows a block diagram of the decoding circuit 141 according to an embodiment. The decoding circuit 141 includes a sorting unit 1411, an estimating unit 1412, a controlling unit 1413, a distance calculating unit 1414 and a threshold updating unit 1415.

(58) The sorting unit 1411 is used to sort the candidate symbols SS0 to SS3 at each layer of the symbol search tree TR1. The estimating unit 1412 is used to estimate each of the estimation symbols , , , based on a received signal. As mentioned above, the sorting unit 1411 sorts the candidate symbols SS1, SS3, SS0, SS2 according to the geometric distance l.sub.31, l.sub.33, l.sub.30, l.sub.32 of the candidate symbols SS0 to SS3 and the estimation symbol . The sorting unit 1411 sorts the candidate symbols SS1, SS0, SS3, SS2 according to the geometric distances l.sub.21, l.sub.20, l.sub.23, l.sub.22 of the candidate symbols SS0 to SS3 and the estimation symbol . The sorting unit 1411 sorts the candidate symbols SS0, SS2, SS1, SS3 according to the geometric distances l.sub.10, l.sub.12, l.sub.11, l.sub.13 of the candidate symbols SS0 to SS3 and the estimation symbol . The sorting unit 1411 sorts the candidate symbols SS3, SS2, SS1, SS0 according to the geometric distances l.sub.03, l.sub.02, l.sub.01, l.sub.00 of the candidate symbols SS0 to SS3 and the estimation symbol .

(59) The controlling unit 1413 is used to traverse the candidate symbols SS0 to SS3 in sequence at each layer of the symbol search tree TR1.

(60) The distance calculating unit 1414 is used to calculate the cumulative partial Euclidean distance. At each layer of the symbol search tree TR1, if the cumulative partial Euclidean distance PED is greater than or equal to the threshold SC, the controlling unit 1413 excludes the candidate symbols SS0 to SS3 in the sibling nodes that are un-scanned.

(61) If the cumulative partial Euclidean distance PED is less than the threshold SC, the threshold updating unit 1415 updates the threshold SC by the cumulative partial Euclidean distance PED.

(62) Please refer to FIGS. 9A to 9F, which show search times comparison charts between the present embodiment and the Maximum Likelihood (ML) algorithm applying to the symbol detection and search for four transmitting antennas TA and four receiving antennas RA. As shown in FIG. 9A to 9F, under 8-APSK to 256-APSK, the search times curves C11, C12, C13, C14, C15, C16 corresponding to the present embodiment are significantly lower than the search times curves C21, C22, C23, C24, C25, C26 corresponding to the ML algorithm. In other words, the symbol detection and search method of the present embodiment greatly accelerates the search speed.

(63) Please refer to FIGS. 10A to 10F, which show bit error rate comparison charts between the present embodiment and the ML algorithm applying to the symbol detection and search for four transmitting antennas TA and 4 receiving antennas RA. As shown in FIGS. 10A to 10F, under 8-APSK to 256-APSK, the bit error rate curves B11, B12, B13, B14, B15, B16 corresponding to the present embodiment are equivalent to the bit error rate curves B21, B22, B23, B24, B25, B26 corresponding to the ML algorithm. In other words, the symbol detection and search method of this embodiment greatly accelerates the search speed.

(64) According to the foregoing embodiments, during the searching process of the decoding circuit 141, many candidate symbols in the sibling nodes that have not been scanned are excluded, so a large amount of computing resources could be saved, and the search speed could be greatly accelerated. In addition, the cumulative partial Euclidean distance of the excluded candidate symbol will not be lower than the threshold, so the best solution will not be excluded, and the search accuracy is lossless.

(65) It will be apparent to those skilled in the art that various modifications and variations could be made to the disclosed embodiments. It is intended that the specification and examples be considered as exemplary only, with a true scope of the disclosure being indicated by the following claims and their equivalents.