PaperlayerView exact revision on arXiv

Source-linked AI summary

Soft-Input Soft-Output Single Tree-Search Sphere Decoding

Christoph Studer, Helmut Bölcskei

arXiv:0906.0840v1cs.IT

TL;DR

The paper addresses the significant complexity cost of SISO detection while seeking strong MIMO detection performance. It presents a tunable SISO STS-SD algorithm with integrated LLR processing and correction, achieving close-to-outage-capacity performance and broad performance/complexity tradeoffs.

  • Problem

    SISO detection performance gains come at the cost of significant, often prohibitive, complexity.

  • Method

    The paper develops a tunable SISO STS-SD algorithm, using radius reduction and LLR correction within the tree-search framework.

  • Results

    The SISO STS-SD algorithm achieves close-to-outage-capacity performance and clearly outperforms state-of-the-art SISO detectors.

  • Takeaways & Limitations

    The algorithm offers a wide range of performance/complexity tradeoffs that can be adjusted through a single tunable detection parameter.

Abstract

from arXiv · show

Soft-input soft-output (SISO) detection algorithms form the basis for iterative decoding. The computational complexity of SISO detection often poses significant challenges for practical receiver implementations, in particular in the context of multiple-input multiple-output (MIMO) wireless communication systems. In this paper, we present a low-complexity SISO sphere-decoding algorithm, based on the single tree-search paradigm proposed originally for soft-output MIMO detection in Studer, et al., IEEE J-SAC, 2008. The new algorithm incorporates clipping of the extrinsic log-likelihood ratios (LLRs) into the tree-search, which results in significant complexity savings and allows to cover a large performance/complexity tradeoff region by adjusting a single parameter. Furthermore, we propose a new method for correcting approximate LLRs --resulting from sub-optimal detectors-- which (often significantly) improves detection performance at low additional computational complexity.

I. INTRODUCTION

SISO detection underpins iterative decoding, but its computational cost makes practical MIMO receiver implementation difficult. The paper develops a tunable single-tree-search sphere decoder that reduces complexity while retaining strong soft-output performance.

  • Motivation: SISO detection forms the basis for iterative decoding, while its complexity challenges practical MIMO receiver implementations.Different algorithms optimized for particular detection efforts or configurations would also entail considerable circuit complexity.
  • Motivation: A practical SISO MIMO detector should cover a wide performance/complexity range and be adjustable through a single tunable algorithm.The existing STS-SD concept is presented as a promising basis for efficient SISO detection.
  • Contributions: The proposed SISO STS-SD algorithm is tunable between max-log optimal SISO and hard-output MAP detection performance.It extends soft-output STS-SD by incorporating a priori information into the tree search and modifying list administration and pruning.
  • Contributions: Clipping extrinsic LLRs inside the tree search reduces tree-search complexity and enables performance/complexity tuning.The approach avoids transcendental-function computation and is described as significantly reducing complexity compared with several existing methods.
  • Contributions: The paper proposes direct compensation for channel-matrix-regularization self-interference and correction of approximate LLRs from sub-optimal detectors.The LLR correction method improves detection performance at low additional computational complexity.
  • Results: Simulation results show close-to-outage-capacity operation at remarkably low complexity and a larger performance/complexity tradeoff region than soft-output-only STS-SD.The algorithm also clearly outperforms state-of-the-art SISO detectors for MIMO systems according to the conclusion.

B. Tightening of the Tree-Pruning Criterion

The section tightens the tree-pruning criterion by exploiting a bias in partial-distance metrics, reducing search complexity while preserving max-log optimality.

  • B. Tightening of the Tree-Pruning Criterion: The approach is motivated by the desirability of reducing tree-search complexity without sacrificing max-log optimality.Alternative approaches such as semi-definite relaxation and H∞-estimation are described as poorly suited to practical VLSI implementation because of high complexity.
  • B. Tightening of the Tree-Pruning Criterion: The proposed alternative exploits a generally non-zero bias in the distance metrics to tighten tree pruning.The bias is defined as the minimum remaining metric over descendants of a node.
  • B. Tightening of the Tree-Pruning Criterion: Computing the full bias can itself lead to prohibitive complexity because it requires enumerating descendants and Euclidean distance terms.The Euclidean distance contribution to the bias is reported as negligible in the corresponding simulations.
  • B. Tightening of the Tree-Pruning Criterion: Statistical independence among symbols enables a less complex computation of the tightened pruning criterion.For independent symbols, the right-hand side requires significantly less complexity than the full-bias computation.
  • B. Tightening of the Tree-Pruning Criterion: The tightened criterion preserves max-log optimality and generally yields significant complexity savings relative to the standard criterion.The savings arise because tighter pruning, especially near the root, reduces the number of visited nodes.

C. Tree Search in the Case of Statistically Independent Bits

For statistically independent bits, the detector modifies prior terms to obtain tighter, bias-free pruning without transcendental functions while retaining max-log-optimal LLRs.

  • C. Tree Search in the Case of Statistically Independent Bits: The derivation assumes statistically independent transmitted bits, including the equally likely case when no a priori information is available.Equal constellation-point probabilities are identified as an example of the no-a-priori-information case.
  • C. Tree Search in the Case of Statistically Independent Bits: Statistical independence across bit levels can be exploited to obtain further computational-complexity reductions.The detector receives a priori LLRs from an external device such as a SISO channel decoder.
  • C. Tree Search in the Case of Statistically Independent Bits: The modified prior term avoids transcendental-function computation and guarantees nonnegative branch metrics for pruning.Setting the auxiliary term to zero directly would produce branch metrics that are not necessarily nonnegative.
  • C. Tree Search in the Case of Statistically Independent Bits: The modified distance increments are bias-free, enabling tight pruning with the standard criterion and avoiding explicit evaluation of the tighter criterion.Their use often significantly reduces tree-search complexity because the modified bound is at least as large.
  • C. Tree Search in the Case of Statistically Independent Bits: Using the modified distance increments still yields max-log-optimal LLRs because only intrinsic-LLR differences are needed.The neglected logarithmic term does not depend on the transmitted bit variable.

III. EXTRINSIC LLR COMPUTATION IN A SINGLE TREE SEARCH

SISO STS-SD computes extrinsic LLRs directly in one tree search, incorporating a priori information and extrinsic-LLR clipping to reduce complexity.

  • III. EXTRINSIC LLR COMPUTATION IN A SINGLE TREE SEARCH: The search jointly tracks the MAP solution and counter-hypotheses, pruning a subtree when it cannot update either relevant metric.This allows each tree node to be visited at most once.
  • III. EXTRINSIC LLR COMPUTATION IN A SINGLE TREE SEARCH: A repeated-tree-search implementation can compute the required quantities but revisits substantial parts of the search tree and performs redundant computations.The single-tree-search paradigm avoids this repeated traversal.
  • III. EXTRINSIC LLR COMPUTATION IN A SINGLE TREE SEARCH: SISO STS-SD directly computes extrinsic LLRs through a tree search rather than first computing intrinsic LLRs.The method extends the single-tree-search paradigm to account for a priori information.
  • III. EXTRINSIC LLR COMPUTATION IN A SINGLE TREE SEARCH: Clipping the extrinsic LLRs inside the tree search reduces complexity and provides a complexity-performance tradeoff controlled by one clipping parameter.The search for counter-hypotheses is constrained to a hypersphere whose radius depends on λMAP and Lmax.
  • III. EXTRINSIC LLR COMPUTATION IN A SINGLE TREE SEARCH: The SISO extension requires modified list administration, pruning, and clipping rules because soft-output STS-SD otherwise delivers intrinsic LLRs.The algorithm is explicitly designed to produce extrinsic rather than intrinsic LLRs.

A. List Administration

List administration updates MAP and counter-hypothesis metrics during one tree traversal, while clipping constrains counter-hypothesis search and spans soft-to-hard output behavior.

  • A. List Administration: The algorithm searches a subtree only when it can update the MAP metric or at least one counter-hypothesis metric.The maintained list contains the current MAP hypothesis and associated counter-hypothesis metrics.
  • A. List Administration: When a leaf has a metric below the current MAP metric, the detector updates the counter-hypothesis metrics before replacing the MAP hypothesis.The former MAP hypothesis metric becomes the extrinsic metric of the new counter-hypothesis.
  • A. List Administration: When a leaf metric exceeds the MAP metric, only counter-hypothesis metrics may be updated.This separates MAP-hypothesis updates from extrinsic-metric updates during list administration.
  • A. List Administration: Extrinsic-LLR clipping is applied after MAP-hypothesis list updates to ensure the delivered extrinsic LLRs satisfy the clipping constraint.The constrained counter-hypothesis search uses a hypersphere of radius λMAP + Lmax around the transformed received signal.
  • A. List Administration: Lmax = ∞ gives max-log-optimal SISO performance, whereas Lmax = 0 yields the hard-output MAP solution.Thus, the clipping parameter includes both soft-output and hard-output endpoints.

C. The Tree-Pruning Criterion

The tree-pruning criterion tracks intrinsic metrics that may change within a subtree and explores that subtree only when it could update the MAP metric or an extrinsic metric. Column sorting can reduce sphere-decoding complexity by placing higher-effective-SNR streams nearer the root.

  • The pruning criterion compares partial-label bits with the current MAP hypothesis to determine which extrinsic metrics may change.
  • The criterion identifies intrinsic metrics that may be affected while searching the subtree rooted at node s(i).
  • A node and its subtree are explored only if they could update λ_MAP or at least one extrinsic metric Λ_MAP_i,b.
  • 1) Column-sorting:: QR-decomposition based on the received vector requires symbol-vector-rate computation, whereas channel-only sorting and regularization require QRD only when H changes.
  • 1) Column-sorting:: Column-sorted QRD reduces sphere-decoding complexity when levels near the root correspond to larger diagonal entries of R and higher effective SNR.

2) Regularization:

Regularized SQRD reduces tree-search complexity but produces approximate LLRs because regularization introduces self-interference. The proposed compensation incorporates the correction into the tree search, recovering near-max-log performance with marginal complexity increase.

  • 2) Regularization:: Regularization provides further complexity reduction at the cost of slightly reduced performance.
  • 2) Regularization:: Regularized SQRD costs approximately 50% more than non-regularized SQRD, but QRD is needed only when the channel matrix changes.
  • 2) Regularization:: Approximate LLRs result because regularization makes the effective noise dependent on s and generally non-i.i.d. Gaussian, while Q_a is not unitary.
  • 2) Compensation in the SISO STS-SD algorithm:: Self-interference compensation is incorporated directly into the tree search, improving performance over the uncorrected approximate LLRs with negligible complexity increase.
  • 2) Compensation in the SISO STS-SD algorithm:: Non-negative distance increments compensate self-interference directly in the search; their complexity increase is marginal because regularization usually reduces complexity significantly.
  • 2) Compensation in the SISO STS-SD algorithm:: Compensation recovers regularization-induced performance loss to near-max-log optimal performance and adds no complexity for constant-modulus alphabets.

V. LLR CORRECTION

The paper introduces post-processing to correct approximate extrinsic LLRs from sub-optimal detectors. Correction functions use quantized side information and can substantially improve iterative MIMO-decoder performance at low application complexity.

  • Max-log approximation, regularization, and early termination produce approximate LLRs even though channel decoders rely on exact LLRs for optimum performance.
  • A. The Basic Idea: The proposed method corrects approximate extrinsic LLRs using side information that reflects the mechanisms causing approximation.
  • The method often significantly improves iterative MIMO-decoder performance while requiring low additional computational complexity.
  • A. The Basic Idea: Side information may include receive SNR, channel singular values, channel rank, and whether early termination occurred, with continuous quantities quantized.
  • B. Computation of the LLR Correction Function: For each side-information instance, Monte Carlo simulations estimate correction functions from conditional histograms, followed by linear interpolation.
  • B. Computation of the LLR Correction Function: Correction-function storage depends on the number of side-information instances and LLR bins, while applying a correction requires low-complexity lookup and interpolation.

C. An Example

The example addresses sphere decoding’s prohibitive worst-case complexity by allocating an aggregate node budget across symbol vectors. A scheduling parameter controls the remaining budget, while early termination motivates LLR correction.

  • C. An Example: Sphere decoding’s prohibitive worst-case complexity can prevent meeting throughput requirements in communication standards.
  • C. An Example: Maximum-first scheduling imposes an aggregate budget of N D_avg visited nodes over a block of N symbol vectors.
  • C. An Example: The termination policy lets the current symbol vector use the remaining budget after reserving at least M nodes for each later vector.
  • C. An Example: Choosing M = M_T and D_avg ≥ M_T ensures that each remaining vector can find at least the hard-output SIC solution.
  • C. An Example: Early termination can yield LLRs with higher apparent reliability than unconstrained detection, motivating correction and a termination-state variable in Z.
  • C. An Example: The simulations use a rate-1/2 convolutional code, a 4×4 MIMO-OFDM system, 16-QAM, 64 tones, and a TGn type C channel model.

A. Tightening of the Tree-Pruning Criterion

The section evaluates tighter tree-pruning criteria and related implementation choices for SISO STS-SD, showing that prior-only tightening provides substantial complexity savings while Euclidean-distance tightening is not worthwhile. LLR clipping and detector configurations further shape the performance/complexity tradeoff.

  • Impact of the bias term: Removing the Euclidean-distance component of the bias produces only marginal complexity reduction despite its computational cost.The stated comparison uses zero prior information and contrasts tightened and standard pruning criteria.
  • Impact of the prior term: Removing the bias |p_i| leads to a dramatic complexity reduction when individual bits x_i,b are statistically independent.The paper links this result to the independence condition used in its complexity analysis.
  • Impact of the prior term: 65.9% to 99.5% complexity reduction is obtained from prior-only tightening, with a less pronounced but still significant effect in the second iteration.The impact generally decreases with increasing iteration number.
  • Design choice: Prior-only tightening requires no additional computational complexity and is retained throughout the paper.The authors contrast this with the effort required for Euclidean-distance-based tightening.
  • LLR clipping: LLR clipping incorporated into the tree search provides a smooth performance/complexity tradeoff controlled by the single parameter Lmax.Post-search clipping corresponds to Lmax = ∞, whereas in-search clipping substantially reduces complexity.
  • Channel processing: MMSE-SQRD is Pareto-optimal in the low-complexity regime, whereas un-regularized SQRD is superior in the high-complexity regime.Regularization incurs performance loss, making the preferred configuration depend on the operating regime.
  • Comparison with LSD: SISO STS-SD outperforms LSD for all SNR operating points while generally requiring less memory than LSD.LSD needs relatively large lists to approach max-log optimum SISO performance, and list administration can add substantial implementation complexity.

D. Impact of LLR Correction

This section studies correction functions for approximate extrinsic LLRs produced by clipping, early termination, and channel-matrix regularization. The correction method can improve the SNR operating point substantially, especially when runtime constraints and early termination dominate.

  • Correction functions: With unconstrained complexity, clipped LLRs at ±Lmax are corrected to values with larger magnitude.This compensates for the clipping operation, with nearby values also affected by binning and interpolation.
  • Correction functions: With MF-scheduling and early termination, LLRs near Lmax are corrected to smaller magnitudes because their reliability is reduced.Early termination can produce less reliable LLR values that require down-correction.
  • Sources of approximation: Column-sorting alone requires little correction, while channel-matrix regularization produces stronger deviations from the uncorrected LLRs.Column-sorting preserves max-log optimality, whereas regularization approximates max-log LLRs.
  • Performance impact: Up to 3 dB SNR operating-point improvement is achieved by LLR correction under average runtime constraints.The correction uses binned functions with linear interpolation and side information describing detector conditions.
  • Performance impact: Correction gains are more pronounced for larger clipping parameters because runtime constraints and early termination then dominate performance.Small clipping levels still show slight gains even when runtime constraints do not affect performance.
  • Decoder interaction: For aggressive clipping, the sum-product turbo decoder requires precise corrected LLRs, whereas max-log-based decoders are more robust.The comparison concerns decoder behavior under the evaluated clipping conditions.
  • Channel-code evaluation: The PCTC has a significantly better tradeoff than the convolutional code in the first iteration, but their tradeoffs are nearly identical in the second.For more than two iterations, the convolutional code slightly outperforms the PCTC, possibly because of the short block length and correlated channel model.

E. Information Transfer Characteristics

The section characterizes SISO detector information transfer and compares SISO STS-SD with LSD and outage capacity. It finds that modest clipping can preserve near-max-log information transfer, while SISO STS-SD remains close to outage-capacity performance.

  • Information transfer and clipping: Lmax = 0.4 achieves almost the same information transfer characteristic as max-log optimal SISO STS-SD with Lmax = ∞.Increasing Lmax above 0.4 adds complexity without further detector-performance improvement in the reported simulations.
  • Comparison with LSD: SISO STS-SD has a fundamental information-transfer advantage over LSD, especially when a priori information is close to one.LSD requires large list sizes to approach the max-log-optimal SISO STS-SD characteristic, while even hard-output MAP detection can outperform small-list LSD in that regime.
  • Conclusion: The proposed detector combines single-tree-search sphere decoding with tighter pruning, in-search extrinsic-LLR clipping, and compensation for regularization effects.These design choices target low-complexity soft-input soft-output MIMO detection.
  • Conclusion: LLR correction substantially improves performance at low additional computational complexity.The correction addresses approximate LLRs associated with the detector's suboptimal processing.
  • Conclusion: The simulations report a wide range of performance/complexity tradeoffs and state that SISO STS-SD clearly outperforms state-of-the-art SISO detectors.The supplied conclusion passage states this paper-level comparative outcome without specifying an individual benchmark value.
Loading 0906.0840v1…