Demodulation technique

Abstract

A technique for assessing the reliability of bits received by a modulation symbol on a channel is provided. A providing circuit provides an input dataset including a plurality of input values. The input values correspond to different transmit hypotheses according to a modulation alphabet used for encoding the bits in the symbol. A computing circuit performs a first computing step and a second computing step. In the first computing step, a first intermediary dataset is computed by combining the input values of the input dataset according to a first combination scheme. In the second computing step, a second intermediary dataset is computed by combining the input values of the input dataset according to a second combination scheme. The second combination scheme is different from the first combination scheme. An assessing circuit assesses the reliability of the bits based on the first intermediary dataset and the second intermediary dataset.

Claims

1. A method of assessing the reliability of bits received via a modulation symbol on a channel, the method performed by a receiver comprising a processor at a receiving side of the channel, the method comprising: receiving, by the receiver, a Multiple Input Multiple Output (MIMO) signal stream comprising different transmit hypotheses according to a modulation alphabet used for encoding the bits in the modulation symbol; determining by the processor, from the MIMO signal stream that was received, an input dataset including a plurality of input values corresponding to the different transmit hypotheses according to the modulation alphabet used for encoding the bits in the modulation symbol; first computing, by the processor, of a first intermediary dataset by combining the input values of the input dataset according to a first combination scheme; second computing, by the processor, of a second intermediary dataset by combining the input values of the input dataset according to a second combination scheme different from the first combination scheme; and assessing, by the processor, the reliability of the bits based on the first intermediary dataset and the second intermediary dataset, wherein the combining the input values of the input dataset includes at least one of applying a Jacobi logarithm, determining a minimum, determining a maximum or determining an approximation thereof.

2. A method of assessing the reliability of bits received via a modulation symbol on a channel, the method performed by a receiver comprising a processor at a receiving side of the channel, the method comprising: receiving, by the receiver, a Multiple Input Multiple Output (MIMO) signal stream comprising different transmit hypotheses according to a modulation alphabet used for encoding the bits in the modulation symbol; determining, by the processor, from the MIMO signal stream that was received, an input dataset including a plurality of input values corresponding to the different transmit hypotheses according to the modulation alphabet used for encoding the bits in the modulation symbol; first computing, by the processor, of a first intermediary dataset by combining the input values of the input dataset according to a first combination scheme; second computing, by the processor, of a second intermediary dataset by combining the input values of the input dataset according to a second combination scheme different from the first combination scheme; and assessing, by the processor, the reliability of the bits based on the first intermediary dataset and the second intermediary dataset, wherein the first computing comprises computing the first intermediary dataset including a first part and a second part, wherein the first part of the first intermediary dataset is based on a combination of a first part and a third part of the input dataset, and wherein the second part of the first intermediary dataset is based on a combination of a second part and a fourth part of the input dataset.

3. A method of assessing the reliability of bits received via a modulation symbol on a channel, the method performed by a receiver comprising a processor at a receiving side of the channel, the method comprising: receiving, by the receiver, a Multiple Input Multiple Output (MIMO) signal stream comprising different transmit hypotheses according to a modulation alphabet used for encoding the bits in the modulation symbol; determining, by the processor, from the MIMO signal stream that was received, an input dataset including a plurality of input values corresponding to the different transmit hypotheses according to the modulation alphabet used for encoding the bits in the symbol; first computing, by the processor, of a first intermediary dataset by combining the input values of the input dataset according to a first combination scheme; second computing, by the processor, of a second intermediary dataset by combining the input values of the input dataset according to a second combination scheme different from the first combination scheme; and assessing, by the processor, the reliability of the bits based on the first intermediary dataset and the second intermediary dataset, wherein the second computing comprises computing the second intermediary dataset including a first part and a second part, wherein the first part of the second intermediary dataset is based on a combination of the first part and the second part of the input dataset, and wherein the second part of the second intermediary dataset is based on a combination of the third part and the fourth part of the input dataset.

4. The method of claim 1, wherein at least one of the first computing or the second computing is iterated.

5. The method of claim 1, wherein the first computing is iterated so that the input dataset used in the iteration of the first computing is the first intermediary dataset resulting from a previous first computation.

6. The method of claim 1, wherein the second computing is iterated so that the input dataset used in the iteration of the second computing is the first intermediary dataset resulting from a previous first computation.

7. The method of claim 1, wherein the second computing is iterated so that the input dataset used in the iteration of the second computing is the second intermediary dataset resulting from a previous second computation.

8. The method of claim 4, wherein each value in the input dataset of a first iteration corresponds to one of the transmit hypotheses for the modulation symbol.

9. A method of assessing the reliability of bits received via a modulation symbol on a channel, the method performed by a receiver comprising a processor at a receiving side of the channel, the method comprising: receiving, by the receiver, a Multiple Input Multiple Output (MIMO) signal stream comprising different transmit hypotheses according to a modulation alphabet used for encoding the bits in the modulation symbol; determining, by the processor, from the MIMO signal stream that was received, an input dataset including a plurality of input values corresponding to the different transmit hypotheses according to the modulation alphabet used for encoding the bits in the modulation symbol; first computing, by the processor, of a first intermediary dataset by combining the input values of the input dataset according to a first combination scheme; second computing, by the processor, of a second intermediary dataset by combining the input values of the input dataset according to a second combination scheme different from the first combination scheme; and assessing, by the processor, the reliability of the bits based on the first intermediary dataset and the second intermediary dataset, wherein at least one of the first computing or the second computing is iterated, wherein each of the intermediary datasets of a last iteration includes pairs of values corresponding to complementary transmit hypotheses for one of the bits encoded in the modulation symbol.

10. The method of claim 4, wherein the input dataset used in a first iteration of the computing steps includes one input value for each of the 2.sup.J transmit hypotheses for the modulation symbol, wherein J denotes a number of the bits encoded in the modulation symbol.

11. A method of assessing the reliability of bits received via a modulation symbol on a channel, the method performed by a receiver comprising a processor at a receiving side of the channel, the method comprising: receiving, by the receiver, a Multiple Input Multiple Output (MIMO) signal stream comprising different transmit hypotheses according to a modulation alphabet used for encoding the bits in the modulation symbol; determining, by the processor, from the MIMO signal stream that was received, an input dataset including a plurality of input values corresponding to the different transmit hypotheses according to the modulation alphabet used for encoding the bits in the modulation symbol; first computing, by the processor, of a first intermediary dataset by combining the input values of the input dataset according to a first combination scheme; second computing, by the processor, of a second intermediary dataset by combining the input values of the input dataset according to a second combination scheme different from the first combination scheme; and assessing, by the processor, the reliability of the bits based on the first intermediary dataset and the second intermediary dataset, wherein at least one of the first computing or the second computing is iterated, wherein a number of intermediary datasets resulting from one iteration of the computing steps increases linearly with a number of the iterations.

12. The method of claim 4, wherein a number of values in each of the intermediary datasets resulting from one iteration of the computing steps decreases exponentially with the number of iterations.

13. The method of claim 4, wherein the iteration is terminated when the number of intermediary datasets computed in one iteration of the computing steps equals a number of the bits.

14. The method of claim 13, wherein the reliability of each of the bits is assessed based on a difference between the values in a corresponding one of the terminating intermediary datasets.

15. The method of claim 1, wherein each value in each of the datasets is indicative of at least one of a likelihood, a log-likelihood and a Euclidean distance.

16. The method of claim 1, wherein the channel is a Multiple-Input Multiple-Output, MIMO, channel and the modulation symbol is a symbol vector including a symbol value for each spatial layer of the MIMO channel.

17. The method of claim 1, further comprising the steps of: receiving the modulation symbol on the channel; and estimating a state of the channel, wherein the channel state is indicative of at least one of gain and noise of the channel.

18. A computer program product comprising a non-transitory computer readable storage medium storing program code that performs the steps operations of claim 1 when the computer program product is executed by a processor if of a computer device.

19. A device for assessing the reliability of bits received by means of via a modulation symbol on a channel, the device comprising: a receiving circuit, configured to receive a Multiple Input Multiple Output (MIMO) signal stream comprising different transmit hypotheses according to a modulation alphabet used for encoding the bits in the modulation symbol; a providing circuit configured to determine, from the MIMO signal stream that was received, an input dataset including a plurality of input values corresponding to different transmit hypotheses according to a modulation alphabet used for encoding the bits in the modulation symbol; a computing circuit configured to perform a first computing of a first intermediary dataset by combining the input values of the input dataset according to a first combination scheme and a second computing of a second intermediary dataset by combining the input values of the input dataset according to a second combination scheme different from the first combination scheme; and an assessing circuit configured to assess the reliability of the bits based on the first intermediary dataset and the second intermediary dataset, wherein the combining the input values of the input dataset includes at least one of applying a Jacobi logarithm, determining a minimum, determining a maximum or determining an approximation thereof.

Description

BRIEF DESCRIPTION OF THE DRAWINGS

(1) In the following, the disclosure is described in more detail with reference to exemplary embodiments illustrated in the drawings, wherein

(2) FIG. 1 is a schematic block diagram illustrating a wireless communication as an exemplary context for an embodiment of a device for assessing the reliability of received bits;

(3) FIG. 2 is a flowchart illustrating an embodiment of a method that can be performed at a receiving side of the communication shown in FIG. 1;

(4) FIG. 3 schematically illustrates a first combination scheme applied in a computation step of the method shown in FIG. 2;

(5) FIG. 4 schematically illustrates a second combination scheme applied in a computation step of the method shown in FIG. 2;

(6) FIG. 5 is a schematic block diagram illustrating further details of the receiving side of the communication shown in FIG. 1;

(7) FIG. 6 schematically illustrates decomposition rules for matrices related to the computation step shown in FIG. 2;

(8) FIG. 7 schematically illustrates iterations of the rules shown in FIG. 6; and

(9) FIG. 8 schematically illustrates a data flow resulting from the method shown in FIG. 2.

DETAILED DESCRIPTION

(10) In the following description, for purposes of explanation and not limitation, specific details are set forth, such as specific device and system configurations and specific methods, steps and functions, in order to provide a thorough understanding of the technique presented herein. It will be appreciated by the skilled person that the technique may be practiced in other embodiments that depart from these specific details. While the embodiments are described in the context of a wireless telecommunications system, e.g., according to Universal Mobile Telecommunications System (UMTS) or Long Term Evolution (LTE), the technique can also be practiced in any other data processing system that demodulates a modulation symbol representing two or more bits. Such systems can include devices for receiving and/or storing data.

(11) Those skilled in the art will further appreciate that the methods, steps and functions described herein may be implemented using individual hardware circuitry, using software functioning in conjunction with a programmed microprocessor or general purpose computer, using one or more Application Specific Integrated Circuits (ASICs), one or more Digital Signal Processors (DSPs) and/or one or more Field Programmable Gate Arrays (FPGAs). It will also be appreciated that the technique disclosed herein may be embodied in a processor and a memory coupled to the processor, wherein the memory stores one or more programs that perform the methods, steps and functions described herein when executed by the processor.

(12) FIG. 1 is a schematic block diagram illustrating a wireless communication 100 from a transmitter 102 via a channel 104 to a receiver 105. Methods and devices described herein can be implemented at the side of the receiver 105. A base station of a telecommunications network and a mobile device can take the roles of the transmitter 102 and the receiver 105, respectively, or vice versa.

(13) While FIG. 1 shows a unidirectional communication 100 for the clarity of the illustration, the technique is readily implemented for a bidirectional communication. Furthermore, while the communication 100 shown in FIG. 1 includes a Multiple Input Multiple Output (MIMO) channel 104, the technique is beneficially applied also for receiving data on a Multiple Input Single Output (MISO) channel or Single Input Single Output (SISO) channel.

(14) The MIMO transmitter 102 includes a plurality of transmit antennas. Generally, the number of one or more transmit antennas is denoted by N (for values N=1, 2, . . . ). The receiver 105 includes M receive antennas (for values M=1, 2, . . . ). The signal received at each of the receive antennas is sampled in the time domain by means of an analog-to-digital converter 106. The digital signal of each of the receive antennas is subjected to a preprocessing unit 108. The preprocessing unit performs channel equalization by decorrelating different spatial layers transmitted via the MIMO channel 104 according to a channel gain, H=(h.sub.1,1, h.sub.1,2, . . . ), and a channel noise variance, v=(v.sub.1,v.sub.2). The channel gain H and the channel noise variance v define the channel state, which is periodically measured by the receiver 105 based on reference signals transmitted from the transmitter 102 via the channel 104.

(15) The MIMO communication 100 shown in FIG. 1 includes two spatial layers. The symbol value r.sub.1 received on the first spatial layer and the symbol value r.sub.2 received on the second spatial layer are collectively referred to as a modulation symbol r. The modulation symbol is provided, e.g., in the form of a tuple, to a device 110 for assessing the reliability of bits, b=(b.sub.1, . . . , b.sub.j, . . . , b.sub.J), encoded in the modulation symbol r received via the channel 104. In the case of an SISO communication, the modulation symbol r may include only one symbol value.

(16) The device 110 comprises a providing unit 112, a computing unit 114 and an assessing unit 116. The providing unit 112 provides one input value for each of the transmit hypotheses according to a modulation alphabet used for the encoding of the bits b in the symbol r. The computing unit computes first and second intermediary datasets based on the input values of the input dataset. The assessing unit 116 assesses the reliability of the bits b based on the first and second intermediary datasets.

(17) The reliability of each of the bits b is expressed in terms of a Log-Likelihood Ratio (LLR), which is also referred to as a softbit. The softbits are subjected to a bit interleaver unit 118. The output of the bit interleaver 118 is still protected by a channel code used as a means of forward error correction on the channel 104. The channel decoder unit 120 optionally provides extrinsic information on the coded bits as a priori knowledge to the device 110. After successfully decoding, the channel decoder unit 120 provides an output stream that is equal to the input stream underlying the transmission.

(18) The device 110 can be implemented in any context requiring the functionality of a soft-output demapper, which is also referred to as a soft-output joint detector in the case of more than one spatial layer. Combining-weight coefficients and gain coefficients can be computed according to a Zero Forcing (ZF) decoding approach, a Minimum Mean Square Error (MMSE) decoding approach or a Sphere decoding approach.

(19) FIG. 2 shows a flowchart illustrating a method embodiment for assessing the reliability of bits received by means of a modulation symbol on a channel. The method comprises the step 202 of providing an input dataset including a plurality of input values. The input dataset includes one input value for each transmit hypothesis of a modulation alphabet, which is used for encoding the bits in the modulation symbol.

(20) The method 200 further comprises a first computing step 204A of computing a first intermediary dataset by combining the input values of the input dataset according to a first combination scheme. In a second computing step 204B, a second intermediary dataset is computed by combining the input values of the input dataset according to a second combination scheme, which is different from the first combination scheme. In a step 206 of the method 200, the reliability of the bits is assessed based on the first intermediary dataset and the second intermediary dataset.

(21) The method 200 can be performed by the device 110 shown in FIG. 1. The steps 202, 204A and 204B, and 206 are performed by the units 112, 114, and 116, respectively.

(22) FIG. 3 is a flow chart schematically illustrating the first combination scheme applied by the computing unit 114 in the step 204A. The input dataset 300 is at least logically subdivided, e.g., by memory re-allocation or by means of pointers, into four equally sized subsequent parts 302, 304, 306 and 308. The first part 302 and the third part 306 are combined into a first part 310 of the first intermediary dataset 314. The second part 304 and the fourth part 308 of the input dataset 300 are combined into a second part 312 of the first intermediary dataset 314.

(23) The input dataset 300 can be an initially provided input dataset d.sub.J.sup.(1, . . . , J) including 2.sup.J input values, each of which is a log-likelihood value for one of the 2.sup.J transmit hypotheses for the symbol r. In the notation of FIG. 3, the latter case corresponds to x=0. The input dataset 300 can also be the first intermediary dataset d.sub.J-x.sup.(1, . . . , J-x) resulting from a previous first computing step 204A. Here, x+1=1, 2, . . . may correspond to a number of iterations of the first computation step 204A. As a result of applying the first computing step 204A, the size of the first intermediary dataset 314 is reduced by a factor of 2 compared to the initial size of 2.sup.J-x input values.

(24) FIG. 4 is a flowchart schematically illustrating the second combination scheme applied in the second computing step 204B. The input dataset 300 is at least logically subdivided into four parts 302 to 308. The input dataset 300 of the form d.sub.J-x.sup.(1, . . . , J-x) (for x=0, 1, 2, . . . ) used in the first computing step 204A is also subjected to the second computation step 204B. In these cases, the logical subdivision is performed once for both the first computing step 204A and the second computing step 204B.

(25) For further applications of the second computing step 204B when the input dataset 300 has the form d.sub.J-y.sup.(J-x) for y>x (for x=0, 1, 2, . . . ), which input datasets 300 are not subjected to the first computing step 204A, the second computing step 204B includes a substep of subdividing the input dataset 300.

(26) According to the second combination scheme, the first part 302 and the second part 304 of the input dataset 300 are combined into a first part 410 of the second intermediary dataset 414. The third part 306 and the fourth part 308 of the input dataset 300 are combined into a second part 412 of the second intermediary dataset 414.

(27) The input dataset 300 used for the second computing step 204B can be any one of an initially provided input dataset d.sub.J.sup.(1, . . . , J), the result 314 of a previous first computing step 204A and the result 414 of a previous second computing step 204B. One application of the second computing step 204B reduces the size 2.sup.J-x or 2.sup.J-y of the input dataset 300 by a factor 2.

(28) FIG. 5 is a block diagram including further details of the receiving side 105. The device 110 is coupled to a turbo-decoding unit 120. The device 110 is provided with estimates 500 for the channel gain H and the variance σ.sup.2.sub.v of the noise v, and the received symbol r indicated by reference sign 502.

(29) For a general communication 100, the received modulation symbol, r, is related the transmitted modulation symbol, s, according to
r=H.Math.s+v.  (1)

(30) The received symbol r is also referred to as observation at the receiver 105. In Eq. (1), Hε.sup.M×N is a complex-valued matrix representing the channel gain. Each element h.sub.m,n of the matrix H represents the complex-valued channel gain from transmit antenna n (for n=1, . . . , N) to receive antenna m (for m=1, . . . , M).

(31) The transmitted symbol sε.sup.N is the complex-valued signal assigned to the bits b according to the modulation. The set represents the finite symbol alphabet of the modulation, such as QPSK, 16-QAM or 64-QAM. Due to the finiteness of the modulation alphabet and the finite number M of receive antennas, the transmitted signal s can be represented as a symbol vector in a finite-dimensional discrete vector space. Note that the logarithm of basis 2 (denoted by log.sub.2) of the cardinality of set .sup.N corresponds to the number, J, of bits carried by the transmitted symbol s and the received symbol r.

(32) The last term in Eq. (1), vε.sup.M, represents the complex-valued noise introduced by the channel 104. The components of the noise have zero mean and are independent identically-distributed Gaussian noise, i.e. ˜(0, σ.sub.v.sup.2.Math.I.sub.M). The variance, σ.sup.2.sub.v, is the mean energy of each noise sample. Herein, I.sub.M denotes the identity matrix of size M.

(33) The providing unit 112 is implemented by a Euclidean distance calculation unit. The providing unit 112 computes Euclidean distances, which define the input values, d.sub.k, in the initial input dataset 300, d.sub.J.sup.(1, . . . , J), according to
d.sub.k=∥H.Math.s.sub.k−r∥.sub.2.sup.2/σ.sub.v.sup.2,  (2)
wherein the denominator normalizes the Euclidean distance with respect to the estimated noise variance. Consequently, the initial input dataset 300 includes 2.sup.J Euclidean distances between the observation r and the transmit hypothesis, H.Math.s.sub.k, for k=1, . . . , 2.sup.J. By way of example, for a 2×2 MIMO communication 100 (i.e., N=2) with QPSK modulation (i.e., ||=2.sup.2), each modulation symbol is carrying a sequence of J=N.Math.log.sub.2||=4 bits. The hypothesis subscript, k, uniquely indicates the bit sequence b.sub.k keyed by the hypothetical symbol s.sub.k via “decimal to binary number conversion”. E.g., the bit sequence b.sub.k associated to k=3 is b.sub.3=(0,0,1,1).

(34) Since Gaussian noise has been assumed, the Euclidean distance between the received symbol 502, r, and the transmit hypothesis, H.Math.s.sub.k, equals the log-likelihood for the transmit hypothesis. The likelihood is a conditional probability for the transmitted symbol s being s.sub.k (which corresponds to the bit sequence b being b.sub.k) given the channel state 500, H, and the received symbol r.

(35) As a preparation for the turbo-decoding unit 120, the receiver 105 has to derive soft values 504 that represent the assessment as to the reliability of each of the transmitted bits. In one implementation, the magnitude of the softbits 504 represents the reliability and the sign of the softbit 504 points to the most likely decision for the corresponding one of the bits being either 0 or 1. In the implementation shown in FIG. 5, the softbits 504 are so-called Log-Likelihood Ratios (LLRs) that satisfy the needs of the turbo-decoding unit 120. The LLR for the j-th bit, b.sub.j, is denoted by L.sub.j.

(36) Conventionally, the LLR of bit b.sub.j is computed according to

(37) $\begin{array}{cc}\begin{array}{c}{L}_{j,\mathrm{APP}}=\log \left(\underset{k\in {\underset{-}{ℬ}}_j}{\overset{}{.Math.}}P\left\{s_k|r\right\}\right)-\log \left(\underset{\ell \in {\stackrel{-}{ℬ}}_j}{.Math.}P\left\{s_{\ell }|r\right\}\right)\\ =\log \left(\underset{k\in {\underset{-}{ℬ}}_j}{\overset{}{.Math.}}\exp \left(-d_k\right)\right)-\log \left(\underset{\ell \in {\stackrel{-}{ℬ}}_j}{.Math.}\exp \left(-d_{\ell }\right)\right),\end{array}& \left(3\right)\end{array}$
wherein the set .sub.j contains all indices of symbol hypotheses with bit b.sub.j=0, whereas the set .sub.j contains the complementary set of indices for the counter hypotheses with bit b.sub.j=1. By means of the Jacobi logarithm,
−log(exp(−a)+exp(−b))=min(a,b)+log(1+exp(−|a−b|)),  (4)

(38) Eq. (3) can be recursively calculated, i.e., the logarithm of the sum having K=2.sup.J exponential summands requires K/2−1 executions of Eq. (4). Due to the logarithm term within Eq. (4), the calculation of LLRs is computationally expensive. A good approximation with significantly reduced computational complexity can be attained by the so-called “max-log” approximation:

(39) $\begin{array}{cc}\begin{array}{c}{L}_{j,\mathrm{MAX}-\mathrm{LOG}}\approx \log \left(\underset{k\in {\underset{-}{ℬ}}_j}{\max }P\left\{s_k|r\right\}\right)-\log \left(\underset{\ell \in {\stackrel{-}{ℬ}}_j}{\max }P\left\{s_{\ell }|r\right\}\right)\\ \approx \underset{\ell \in {\stackrel{-}{ℬ}}_j}{\min }{d}_{\ell }-\underset{k\in {\underset{-}{ℬ}}_j}{\min }{d}_k\end{array}.& \left(5\right)\end{array}$

(40) Similar to Eq. (4), the max-log approximation of LLRs can be recursively calculated by
−log(exp(−a)+exp(−b))≈min(a,b).  (6)

(41) However, the conventional computation becomes infeasible as the number, J, of bits encoded in one modulation symbol (denoted by s on the transmitting side and r on the receiving side) increases. Let K=|.sup.N|=2.sup.J be the cardinality of the symbol set, .sup.N. In other words, K is the number of transmit hypotheses H.Math.s.sub.k for k=1, . . . , K. The number of bits keyed by the symbol is related to K by J=log.sub.2 K=N.Math.log.sub.2||. Hence, in order to obtain LLRs (using the combination APP or MAX-LOG), Eq. (4) or Eq. (6) has to be carried out (J.Math.(2.sup.J−2)) times, i.e., the complexity of the conventional computation is of order O(J.Math.(2.sup.J−2)). For example, for a 4×4 MIMO system (i.e., N=4) with 64-QAM (i.e., ||=64), this number is 402,653,136. This example should point out that the computational effort for the conventional approach might become very huge and not feasible for practical systems. As opposed to the conventional computation, the method 200 performed by the device 110 significantly reduces the computational complexity without reducing the numerical accuracy of the computation, as is described in what follows.

(42) The device 110 and the method 200 are suitable for using in the computing steps 204A and 204B the APP value combination, the MAX-LOG approximate value combination or any other value combination for soft-output demapping. In an advanced embodiment, the value combination used in the computing steps 204A and 204B is a mixture of APP and MAX-LOG.

(43) The following notation is used for a clear presentation of the technique. The value combination is symbolized by an operator ⊕. The ⊕-operator for the Jacobi logarithm according to Eq. (4), i.e., for the APP value combination, is denoted by “⊕.sub.APP”. The ⊕-operator for the min-operation according to Eq. (6), i.e., for the MAX-LOG value combination, is denoted by “⊕.sub.MAX-LOG”. More specifically, the operators are defined by
a⊕.sub.APPb=min(a,b)+log(1+exp(−|a−b|)) and
a⊕.sub.MAX-LOG b=min(a,b).  (7)

(44) When applied onto a pair of datasets including a plurality of values, the value combination operator ⊕ is to be understood as a value-wise combination, e.g., a⊕b=[a.sub.0⊕b.sub.0, . . . , a.sub.K⊕b.sub.K].sup.T.

(45) Since the technique is independent of any details of the value combination, such as the details specified by Eq. (7), the technique is presented most clearly without a subscript “APP”, “MAX-LOG” or any other specification of the detailed combination at the value-level.

(46) Furthermore, a multiplicative operator denoted by “” is used for conveniently explaining the technique. The -operator yields a dataset by relating a dataset and a matrix according to:

(47) $\begin{array}{cc}\left[\begin{array}{ccc}{a}_{0,0}& \mathrm{.Math.}& a_{0,N}\\ \mathrm{.Math.}& & \mathrm{.Math.}\\ a_{M,0}& \mathrm{.Math.}& a_{M,N}\end{array}\right].Math.\left[\begin{array}{c}{b}_0\\ \mathrm{.Math.}\\ b_N\end{array}\right]=\left[\begin{array}{c}{a}_{0,0}.Math.b_0\oplus \mathrm{.Math.}\oplus a_{0,N}.Math.b_N\\ \mathrm{.Math.}\\ a_{M,0}.Math.b_0\oplus \mathrm{.Math.}\oplus a_{M,}.Math.b_N\end{array}\right].& \left(8\right)\end{array}$

(48) The calculation of J softbits associated to the received modulation symbol r can be rewritten using the following two step approach.

(49) In a first step, let c.sub.j denote the left term in Eq. (3) and Eq. (5) for the exemplary value combinations APP and MAX-LOG, respectively:

(50) $\begin{array}{cc}{\underset{-}{c}}_{j,\mathrm{APP}}=-\log \left(\underset{k\in {\underset{-}{ℬ}}_j}{\overset{}{.Math.}}\exp \left(-d_k\right)\right)\mathrm{or}{\underset{-}{c}}_{j,\mathrm{MAX}-\mathrm{LOG}}=\underset{k\in \underset{-}{{ℬ}_j}}{\min }{d}_k.& \left(9\right)\end{array}$

(51) The value c.sub.j bears the information of the LLR L.sub.j with regard to all distances with b.sub.j=0. Its counterpart is denoted by c.sub.j, examples of which are:

(52) $\begin{array}{cc}{\stackrel{-}{c}}_{j,\mathrm{APP}}=-\log \left(\underset{\ell \in {\stackrel{-}{ℬ}}_j}{.Math.}\exp \left(-d_{\ell }\right)\right)\mathrm{or}{\stackrel{-}{c}}_{j,\mathrm{MAX}-L\mathrm{OG}}=\underset{\ell \in {\stackrel{-}{ℬ}}_j}{\min }{d}_{\ell }.& \left(10\right)\end{array}$

(53) Subsequently, the subscript (such as “APP” or “MAX-LOG”) specifying the detailed value combination is avoided, since the presented technique is not limited to a specific value combination. Moreover, c.sub.1, . . . , J is defined to be the tuple of size 2J stacking all terms c.sub.j and c.sub.j associated to received modulation symbol r, e.g.,
c.sub.1, . . . ,J=[c.sub.1,c.sub.1, . . . ,c.sub.j,c.sub.j, . . . ,c.sub.J,c.sub.J].sup.T.  (11)

(54) The initial input dataset d of size K=2.sup.J includes the sorted distances associated to received modulation symbol r as input values, e.g.,
d.sub.j.sup.(1, . . . ,J)=[d.sub.0, . . . ,d.sub.k, . . . ,d.sub.K].sup.T.  (12)

(55) In order to identify and eliminate redundancy in the conventional computation, an indicator matrix, F.sub.J, of rank J consisting of zeroes and ones is used. It is emphasized that above operators and the indicator matrix explain the technique and can be implemented in an embodiment of the technique. However, the operators and/or the indicator matrix are not mandatory features of the technique.

(56) The element f.sub.2j-1,k of F.sub.J equals 0, if the k-th transmit hypothesis is keying b.sub.j=0. The element f.sub.2j-1,k of F.sub.J equals 1, if the k-th transmit hypothesis is keying b.sub.j=1. The element f.sub.2j,k equals 1, if the k-th transmit hypothesis is keying b.sub.j=0. The element f.sub.2j,k equals 0, if the k-th transmit hypothesis is keying b.sub.j=1. In other words, f.sub.2j-1,k equals the bit b.sub.j of the bit sequence b.sub.k. And f.sub.2j,k equals the inverted bit b.sub.j of the bit sequence b.sub.k. For example, the indicator matrix for rank J=3 is given by

(57) $\begin{array}{cc}{F}_3=\left[\begin{array}{cccccccc}0& 1& 0& 1& 0& 1& 0& 1\\ 1& 0& 1& 0& 1& 0& 1& 0\\ 0& 0& 1& 1& 0& 0& 1& 1\\ 1& 1& 0& 0& 1& 1& 0& 0\\ 0& 0& 0& 0& 1& 1& 1& 1\\ 1& 1& 1& 1& 0& 0& 0& 0\end{array}\right].& \left(13\right)\end{array}$

(58) Using the operators and the indicator matrix F.sub.J, the tuple c.sub.1, . . . , J can be expressed by
c.sub.1, . . . ,J=F.sub.Jd.sub.J.sup.(1, . . . ,J).  (14)

(59) In a second step, the LLRs are determined based on the tuple by means of subtraction in the step 206 according to:
L.sub.j=c.sub.j−c.sub.j.  (15)

(60) Apparently, the indicator matrix F.sub.J has a regular structure. Therefore, the indicator matrix allows identifying the redundancy in the conventional computation. By decomposing the indicator matrix, the redundancy is eliminated, resulting in the efficient computation of the method 200. As pointed out before, the decomposition of the indicator matrix F.sub.J illustrates the technique and can be implemented in an embodiment of the technique. Implementing the decomposition is, however, not mandatory for realizing the technique according to the device 110 and the method 200.

(61) The decomposition illustrates how to breaking down the large number of unrelated computation steps in the conventional computation into a number of smaller and efficiently interrelated computing steps 204A and 204B. The indicator matrix F.sub.J is decomposed until it cannot be divided any further when identity matrices of size 2 have been reached.

(62) A recursive decomposition rule for the indicator matrix F.sub.J and for an auxiliary matrix G.sub.J is defined. Let F.sub.J(0) and F.sub.J(1) denote the equally sized left and right parts of indicator matrix F.sub.J so that F.sub.J=[F.sub.J(0) F.sub.J(1)]. Correspondingly, G.sub.J(0) and G.sub.J(1) denote the left and right parts of the auxiliary matrix G.sub.J=[G.sub.J(0) G.sub.J(1)]. Furthermore, the “atomic”, i.e. not further divisible, base elements are defined by F.sub.1=G.sub.1=I.sub.2, wherein I.sub.2 is the identity matrix of size 2.

(63) The indicator matrix F.sub.J of rank J is recursively decomposed into an indicator matrix of rank J−1 by

(64) $\begin{array}{cc}{F}_J=\left[\begin{array}{cccc}{F}_{J-1}\left(0\right)& F_{J-1}\left(1\right)& F_{J-1}\left(0\right)& F_{J-1}\left(1\right)\\ G_{J-1}\left(0\right)& G_{J-1}\left(0\right)& G_{J-1}\left(1\right)& G_{J-1}\left(1\right)\end{array}\right],& \left(16\right)\end{array}$
and the auxiliary matrix G.sub.J is recursively decomposed by
G.sub.J=[G.sub.J-1(0)G.sub.J-1(0)G.sub.J-1(1)G.sub.J-1(1)].  (17)

(65) While Eqs. (16) and (17) have been written for decomposing rank J-matrices into matrices of rank J−1, the decomposition rule holds for any rank j=1, . . . , J. FIG. 6 shows an example of the recursive decomposition rule. The arrows in FIG. 6 indicate a corresponding recursive composition.

(66) Using relation of Eq. (16), the Eq. (14) is rewritten as

(67) $\begin{array}{cc}\left[\begin{array}{c}{c}_{1,\mathrm{.Math.},J-1}\\ c_J\end{array}\right]=\left[\begin{array}{cccc}{F}_{J-1}\left(0\right)& F_{J-1}\left(1\right)& F_{J-1}\left(0\right)& F_{J-1}\left(1\right)\\ G_{J-1}\left(0\right)& G_{J-1}\left(0\right)& G_{J-1}\left(1\right)& G_{J-1}\left(1\right)\end{array}\right].Math.[\begin{array}{c}{d}_J^{\left(1,\mathrm{.Math.},J\right)}\left(0\right)\\ d_J^{\left(1,\mathrm{.Math.},J\right)}\left(1\right)\\ d_J^{\left(1,\mathrm{.Math.},J\right)}\left(2\right)\\ d_J^{\left(1,\mathrm{.Math.},J\right)}\left(3\right)\end{array}],& \left(18\right)\end{array}$
wherein d.sub.J.sup.(1, . . . , J)(0), . . . , d.sub.J.sup.(1, . . . , J)(3) is the partitioning of d.sub.J.sup.(1, . . . , J) into the 4 equally sized parts 302 to 308. Hence, the upper part of Eq. (18) can be compactly summarized by

(68) $\begin{array}{cc}{c}_{1,\mathrm{.Math.},J-1}=\underset{\underset{F_{J-1}}{︸}}{\left[F_{J-1}\left(0\right)F_{J-1}\left(1\right)\right]}.Math.\underset{\underset{d_{J-1}^{\left(1,\mathrm{.Math.},J-1\right)}}{︸}}{\left[\begin{array}{c}{d}_J^{\left(1,\mathrm{.Math.},J\right)}\left(0\right)\oplus d_J^{\left(1,\mathrm{.Math.},J\right)}\left(2\right)\\ d_J^{\left(1,\mathrm{.Math.},J\right)}\left(3\right)\oplus d_J^{\left(1,\mathrm{.Math.},J\right)}\left(1\right)\end{array}\right]}.& \left(19\right)\end{array}$

(69) The combination for the dataset d in Eq. (19) is the first combination scheme applied in the step 204A. The lower part of Eq. (18) can be summarized by

(70) 0$\begin{array}{cc}{c}_J=\underset{\underset{G_{J-1}}{︸}}{\left[G_{J-1}\left(0\right)G_{J-1}\left(1\right)\right]}.Math.\underset{\underset{d_{J-1}^{\left(J\right)}}{︸}}{\left[\begin{array}{c}{d}_J^{\left(1,\mathrm{.Math.},J\right)}\left(1\right)\oplus d_J^{\left(1,\mathrm{.Math.},J\right)}\left(0\right)\\ d_J^{\left(1,\mathrm{.Math.},J\right)}\left(2\right)\oplus d_J^{\left(1,\mathrm{.Math.},J\right)}\left(3\right)\end{array}\right]}.& \left(20\right)\end{array}$

(71) The combination for the dataset d in Eq. (20) is the second combination scheme applied in the step 204B.

(72) After the first decomposition according to Eq. (20), the iterated application of the decomposition rule for the auxiliary matrix according to Eq. (20) leads to a different kind of sub-problem, which is of the type
c.sub.J-x=G.sub.J-yd.sub.J-y.sup.(J-x).  (21)

(73) This second type corresponds to applying the second computing step 204B to an input dataset d.sub.J-y.sup.(J-x) for y>x. By means of the relation according to Eq. (17), Eq. (21) is rewritten as

(74) $\begin{array}{cc}{c}_{J-x}=\left[G_{J-y-1}\left(0\right)G_{J-y-1}\left(0\right)G_{J-y-1}\left(1\right)G_{J-y-1}\left(1\right)\right].Math.\left[\begin{array}{c}{d}_{J-y}^{\left(J-x\right)}\left(0\right)\\ d_{J-y}^{\left(J-x\right)}\left(1\right)\\ d_{J-y}^{\left(J-x\right)}\left(2\right)\\ d_{J-y}^{\left(J-x\right)}\left(3\right)\end{array}\right]& \left(22\right)\end{array}$
which leads to the second combination scheme for d.sub.J-y.sup.(J-x):

(75) $\begin{array}{cc}{c}_{J-x}=\underset{\underset{G_{J-y-1}}{︸}}{\left[G_{J-y-1}\left(0\right)G_{J-y-1}\left(1\right)\right]}.Math.\underset{\underset{d_{J-y-1}^{\left(J-x\right)}}{︸}}{\left[\begin{array}{c}{d}_{J-y}^{\left(J-x\right)}\left(0\right)\oplus d_{J-y}^{\left(J-x\right)}\left(1\right)\\ d_{J-y}^{\left(J-x\right)}\left(2\right)\oplus d_{J-y}^{\left(J-x\right)}\left(3\right)\end{array}\right]}& \left(23\right)\end{array}$

(76) At each level of the decomposition process, there is a unique correspondence to the desired result c.sub.j and c.sub.j, for which reason the decomposition of the indicator matrix and/or the processing of the datasets can be implemented recursively or iteratively.

(77) FIG. 7 illustrates a sequence 700 of iterations of the computing steps 204A and 204B. The computing steps 204A and 204B only have to operate on the datasets d to arrive at the desired pairs of values, c.sub.j, which are subtracted in the step 206 to arrive at the LLR of the j-th bit. It is possible, but not necessary, to implement the decomposition of the matrices F and G.

(78) After the last iteration, which is the (J−1)-th iteration shown on the right of FIG. 7, the pairs of values c.sub.j are equal to the J datasets d.sub.(1).sup.(j) for j=1, . . . , J. After the J-th matrix decomposition, the matrices cannot be split any further.

(79) FIG. 8 graphically illustrates a data flow 800 for the datasets d caused by the method 200. FIG. 8 shows an example for J=4 bits. The data flow 800 starts on the left with the initial input dataset d.sub.J.sup.(1, . . . , J), which includes the complete set of Euclidian distances d.sub.k as the input data values, e.g. according to Eq. (2).

(80) The merging of two lines in the graph indicates an operation between the pair of values represented by the two lines. The corresponding operation is indicated at the top line of the graph, which is either the ⊕-operation for the combination in the steps 204A and 204B, or the (−)-operation for the subtraction in the step 206. Each of the arrows pointing downwards indicates one iteration including one application of the step 204A and one or more applications of the step 204B.

(81) On the right of FIG. 8, the output values of the last iteration are subtracted. The subtraction 206 yields the desired LLRs, L.sub.j, for each of the 4 bits keyed in the modulation symbol s by the transmitter 102.

(82) For a sequence of J bits, the symbol alphabet comprises at least 2.sup.J symbols so that the likelihood values of 2.sup.J symbol hypotheses have to be taken into account for computing the reliability of one bit. Consequently, assessing the reliability of all 3 bits has a computational complexity that scales approximately as J.Math.2.sup.J.

(83) The reduction of the computation complexity achieved by at least some implementations of the technique is exemplified. A comparison of the computation complexity of the conventional computation and the computation according to the method 200 by means of the device 110 is given in below Table.

(84) TABLE-US-00001 Number of ⊕- Number of ⊕- Reduction Number of bits operations in operations of in compu- encoded in the the conventional the presented tational modulation symbol s computation technique complexity J = 4 56 36 35.71% (e.g., 2xQPSK) J = 8 2032 748 63.19% (e.g., 2x16QAM) J = 12 49128 12260 75.04% (e.g., 2x 64-QAM) J = 24 402653136 50331596 87.50% (e.g., 4x 64-QAM)

(85) The second column in above Table evaluates the formula Σ.sub.j=1.sup.J-1(j+1)2.sup.J-j for the number of value combinations. The third column shows the percentage value corresponding to J/2Σ.sub.j-32.sup.J-12.sup.J-j.

(86) A significant reduction of the computational complexity is achieved. The reduction enables mobile implementation not feasible otherwise and/or increases battery runtime. The reduction becomes even the more significant the more bits are encoded per modulation symbol. The latter is particularly valuable for modern telecommunications standards, including LTE.

(87) In accordance with common terminology, in case of a “scalar” modulation symbol of size equal to one, the presented technique can be implemented as a softbit demapper. For any “vector” modulation symbol of size above one, the technique can be implemented as a soft-output joint detector. Moreover, the technique is readily extended towards a post-processing unit for list sphere decoders.

(88) The structure of the presented technique is well suited for parallel processing and pipelining. Consequently, it enables processing even a complete “vector” modulation symbol per cycle.

(89) Furthermore, a device using a hybrid value combination including both MAX-LOG and APP can be readily realized. For example, a tendency of high Hamming distances between pairs of “vector” modulation symbols to be processed within first cycles (say the first 2 or 5 cycles) has been observed. Consequently, a hybrid device can beneficially employ a min-operation (e.g., according to Eq. (4)) within the first cycles and subsequently use a Jacobi logarithm (e.g., according to Eq. (6)) for the value combination.

(90) Moreover, the iterations can be stopped before the (J−1)-th iteration for assessing the reliability of groups of bits in correspondence to a soft-input structure of a decoder downstream of the demapper.

(91) As has become apparent by above exemplary embodiments, at least some implementations of the technique significantly reduce the computational complexity for assessing the reliability of individual bits encoded in a modulation symbol. The reduction in computational complexity is in particular significant for high-order modulation schemes and/or MIMO channels.