PaperlayerView exact revision on arXiv

Source-linked AI summary

One-Bit Sphere Decoding for Uplink Massive MIMO Systems with One-Bit ADCs

Yo-Seb Jeon, Namyoon Lee, Song-Nam Hong, Robert W. Heath Jr

arXiv:1709.04163v2cs.ITmath.IT

TL;DR

One-bit ADCs make conventional Euclidean sphere decoding unsuitable for MIMO detection, while exact MLD remains NP-hard. OSD searches reduced, weighted-Hamming spheres, and simulations report near-MLD performance with lower complexity.

  • Problem

    Conventional Euclidean-distance sphere decoding does not extend to one-bit ADCs, while exact MLD is NP-hard because of its integer constraint.

    Source: §I · pp. 2–3

  • Method

    OSD applies weighted-Hamming detection within a sphere, splitting the received vector into lower-dimensional sub-vectors to construct parallel lists of sub-codewords.

    Source: §I · p. 3

  • Results

    At Td=8192, OSD reduces MLD real multiplications by 89%, 88%, and 68% for N=28, 32, and 100, with negligible SER loss; coded FER gap versus MWD is less than 1 dB.

    Source: A. Uncoded Performance · p. 21, B. Coded Performance · p. 24

  • Takeaways & Limitations

    Sphere dimension and sub-codeword-list size expose a performance-complexity tradeoff, while simulations show near-MLD performance for coded and uncoded systems.

    Source: §I · p. 4, discrete nature of received signals.… · p. 25

Abstract

from arXiv · show

This paper presents a low-complexity near-maximum-likelihood-detection (near-MLD) algorithm called one-bit-sphere-decoding for an uplink massive multiple-input multiple-output (MIMO) system with one-bit analog-to-digital converters (ADCs). The idea of the proposed algorithm is to estimate the transmitted symbol vector sent by uplink users (a codeword vector) by searching over a sphere, which contains a collection of codeword vectors close to the received signal vector at the base station in terms of a weighted Hamming distance. To reduce the computational complexity for the construction of the sphere, the proposed algorithm divides the received signal vector into multiple sub-vectors each with reduced dimension. Then, it generates multiple spheres in parallel, where each sphere is centered at the sub-vector and contains a list of sub-codeword vectors. The detection performance of the proposed algorithm is also analyzed by characterizing the probability that the proposed algorithm performs worse than the MLD. The analysis shows how the dimension of each sphere and the size of the sub-codeword list are related to the performance-complexity tradeoff achieved by the proposed algorithm. Simulation results demonstrate that the proposed algorithm achieves near-MLD performance, while reducing the computational complexity compared to the existing MLD method.

I. INTRODUCTION

One-bit ADCs offer practical advantages, but conventional Euclidean sphere decoding does not extend naturally to quantized MIMO detection, whose exact MLD is NP-hard. The paper proposes OSD, analyzes its performance-complexity tradeoff, and reports near-MLD performance with lower complexity in simulations.

I. INTRODUCTION

  • One-bit ADCs simplify circuitry by removing automatic gain control, whereas detection with multi-bit ADCs faces quantization-level selection challenges.A fixed quantization level also makes capacity characterization tractable, as described in the introduction.Source: §I · p. 2
  • Earlier Euclidean-distance sphere-decoding methods do not extend to one-bit ADCs, and exact one-bit MLD remains NP-hard because of its integer constraint.With quantized reception, the initial estimate can be inaccurate and Euclidean distance is not optimal for constructing the sphere.Source: §I · pp. 2–3
  • OSD applies approximate MWD with closed-form weights over weighted-Hamming spheres, splitting received vectors into lower-dimensional sub-vectors to build parallel sub-codeword lists.The paper compares OSD detection complexity with existing MLD and characterizes an upper bound on the probability OSD performs worse than MWD using the sphere-list-error probability and system parameters.Source: §I · pp. 3–4
  • For uncoded MIMO systems with one-bit ADCs, simulations show OSD achieves near-MLD detection performance while significantly reducing detection complexity compared with MLD.For coded MIMO, OSD uses a soft-output decoder applying [28] and achieves significant FER reduction compared with a hard-output decoder.Source: §I · p. 4

A. System Model

  • The model has U single-antenna users sending constellation symbols over a frequency-flat, block-fading channel to an N-antenna BS, with perfect synchronization and power control, then separately sign-quantizes real and imaginary samples.The channel is time-invariant during each coherence interval, and Td denotes the number of data-detection time slots.Source: A. System Model · pp. 5–6

B. Definitions

The definitions establish binary codewords from transmitted symbol vectors and a weighted Hamming distance for comparing codewords. The following MLD section uses that distance to relate MLD to MWD and motivate an approximate baseline.

B. Definitions

  • A codeword vector is sign(Hx_k), the binary pattern associated with symbol vector x_k; the codebook collects these vectors.The paper interprets each codeword as the noise-free received signal for its symbol vector.Source: B. Definitions · p. 6
  • Weighted Hamming distance assigns separate positive weight vectors to differing-sign and same-sign elements of two binary codewords.With positive same-sign weights, the distance between identical codewords can be nonzero.Source: B. Definitions · pp. 6–7

III. MLD FOR MIMO SYSTEM WITH ONE-BIT ADCS

  • Section III reviews MLD, establishes its equivalence to MWD using weighted Hamming distance, and develops a tightly approximating MWD as the baseline for Section IV..Source: §III · p. 7

A. Maximum-Likelihood Detection (MLD)

  • The MLD formulation evaluates the likelihood of the received vector for each candidate transmitted symbol vector.The section presents this likelihood-based optimization for one-bit ADCs.Source: A. Maximum-Likelihood Detection (MLD) · p. 7

B. Minimum Weighted-Hamming-Distance Detection (MWD) as an Exact MLD

The MLD log-likelihood can be rewritten as a weighted Hamming distance, making minimum weighted-Hamming-distance detection (MWD) exactly equivalent to MLD. A near-MLD variant then approximates the exact weights with closed-form weights.

B. Minimum Weighted-Hamming-Distance Detection (MWD) as an Exact MLD

C. MWD as a Near MLD

  • The near-MLD method replaces the exact MWD weights with closed-form approximations based on a Q-function approximation with absolute error below 10^-3.Source: C. MWD as a Near MLD · p. 9

k,i that approximate the original weights w′

The MWD weights distinguish sign mismatches from matches and depend on received SNR. The paper uses this structure to simplify weight computation and motivate one-bit sphere decoding.

near-MLD performance. Specifically, in the MIMO system with one-bit ADCs, the weighted

0. This motivates us to further simplify the detection

  • The MWD computation can reduce complexity by computing weights only for received elements whose signs differ from the candidate codeword.Source: §0 · p. 10

IV. ONE-BIT SPHERE DECODING

  • The proposed one-bit sphere decoding (OSD) uses the MWD method to provide a low-complexity near-MLD algorithm for uplink massive MIMO with one-bit ADCs.The section also compares OSD's computational complexity with MLD and MWD.Source: §IV · p. 10

A. Proposed Algorithm

One-bit sphere decoding (OSD) builds a candidate codeword list and applies minimum weighted-Hamming-distance detection only within that list. It uses channel-state-information preprocessing and subdivided received vectors to reduce the search, with list size and sub-vector dimension controlling the performance-complexity tradeoff.

A. Proposed Algorithm

  • OSD constructs a sphere list of candidate codewords, then performs minimum weighted-Hamming-distance detection only over that list.The proposed distance differs from conventional sphere decoding, which uses Euclidean distance to find codewords in the sphere.Source: A. Proposed Algorithm · pp. 11–12
  • The receiver constructs lists using channel-state-information preprocessing, enabled by the finite set of possible received vectors under one-bit ADCs.List construction is performed once per channel coherence block.Source: A. Proposed Algorithm · pp. 11–12
  • The receiver divides the received vector into sub-vectors and selects the L closest sub-codeword vectors for each, then unions the sub-lists.The resulting sphere list has cardinality between L and GL.Source: A. Proposed Algorithm · pp. 11–12
  • Under equiprobable received vectors in the example, OSD reduces codeword-search complexity by 56% versus MWD.The example’s search-count comparison assumes each possible received vector occurs with equal probability.Source: A. Proposed Algorithm · pp. 14–15
  • Larger sub-vector dimension Ns can support a smaller list size L, while smaller Ns requires a larger L to improve detection performance.The paper also notes that varying Ns across sub-vectors can further tune the performance-complexity tradeoff.Source: A. Proposed Algorithm · p. 15
  • OSD extends to multi-precision ADCs by changing the weight definitions while retaining the detection rule; that approximate rule reaches exact MLD as ADC precision decreases.The multi-precision weights are based on the quantizer-bin boundaries.Source: A. Proposed Algorithm · pp. 15–16

selective channels with some modifications. Suppose that the number of channel-impulse-response

The proposed OSD can be applied to frequency-selective channels by representing the received signal as an equivalent uplink MIMO system. The resulting detection complexity can still be significant when both the number of users and block length are large.

selective channels with some modifications. Suppose that the number of channel-impulse-response

  • Frequency-selective reception is equivalent to an uplink MIMO system with UB users and N(B + L − 1) receive antennas.The construction concatenates received signals over the block transmission.Source: selective channels with some… · p. 17
  • This extension can require significant detection complexity when both U and B are large, motivating lower-complexity methods for practical frequency-selective systems.The paper identifies this as future work.Source: selective channels with some… · p. 17

B. Computational Complexity Comparison

The comparison evaluates detection complexity using the number of real multiplications. With suitable OSD design parameters, the method can reduce detection complexity relative to both MLD and MWD.

B. Computational Complexity Comparison

V. DETECTION PERFORMANCE OF ONE-BIT SPHERE DECODING

The section analyzes OSD detection performance by characterizing an upper bound on the probability that OSD performs worse than MWD.

V. DETECTION PERFORMANCE OF ONE-BIT SPHERE DECODING

  • The analysis characterizes an upper bound on the probability that OSD performs worse than MWD.The passage states the analysis objective but does not provide the bound or its findings.Source: §V · p. 18

We first demonstrate that this probability is upper bounded by the sphere-list-error-probability

The analysis bounds the probability that OSD performs worse than MWD by the sphere-list-error probability (SEP). The SEP upper bound decreases as the sub-vector dimension or sub-list size increases.

We first demonstrate that this probability is upper bounded by the sphere-list-error-probability

  • The OSD failure probability is bounded using the probability that the transmitted codeword is absent from the sphere list, defined as the SEP.If MWD detects the transmitted symbol and it is in the sphere list, OSD also detects it.Source: We first demonstrate that this… · pp. 18–19
  • Theorem 1 provides an upper bound on the SEP for a fixed channel matrix.The bound depends on the sub-vector dimension Ns and sphere sub-list size L.Source: We first demonstrate that this… · p. 19
  • The SEP upper bound decreases as either the sub-vector dimension Ns or sub-list size L increases.The argument relates both increases to an increase in the L-th-smallest-distance term used in the bound.Source: We first demonstrate that this… · p. 19

min,k(e, L) is defined as the L-th smallest value, so d(g)

The analysis and simulations show that OSD’s performance-complexity tradeoff depends on sub-vector dimension and sphere-list size. Across uncoded tests, OSD retains near-MLD symbol-error performance while reducing detection complexity, including with pilot-based channel estimation.

min,k(e, L) is defined as the L-th smallest value, so d(g)

  • Increasing L raises both relative SER performance and relative complexity, while increasing sub-vector dimension also increases the distance term in the SEP bound.The analytic discussion characterizes how the design parameters affect the bound.Source: min,k(e, L) is defined as the L-th… · p. 19
  • The approximate SEP upper bound is very tight to simulated SEP, and SEP decreases with larger Ns and L.For (Ns, L) = (8, 4), SEP is significantly lower than for (4, 2), with only 12.5% higher computational complexity when Td = 4096.Source: min,k(e, L) is defined as the L-th… · p. 20, Figure 3 · p. 20

VI. SIMULATION RESULTS

  • Simulation results are averaged over 5000 channel realizations drawn independently from a zero-mean, unit-variance complex Gaussian distribution.The simulations evaluate OSD for uplink massive MIMO with one-bit ADCs.Source: §VI · p. 20

A. Uncoded Performance

B. Coded Performance

For coded systems, OSD can supply soft outputs to a belief-propagation decoder and offers a better performance-complexity tradeoff than MWD. The paper concludes that OSD achieves near-MLD performance with reduced complexity in both coded and uncoded systems.

B. Coded Performance

  • OSD and MWD provide soft outputs as LLRs that serve as inputs to the belief-propagation decoder.The coded evaluation uses a rate-1/2 LDPC code of blocklength NB = 672.Source: B. Coded Performance · pp. 23–24
  • The soft-input belief-propagation decoder yields almost 10-dB FER reduction over the hard-input bit-flipping decoder for both MWD and OSD.The FER gap between OSD and MWD is less than 1 dB, while OSD reduces MWD detection complexity by 72.6% when Td = NB.Source: B. Coded Performance · p. 24, Figure 7 · p. 24

VII. CONCLUSION

  • Simulations show that OSD reduces MLD detection complexity while achieving near-MLD performance in coded and uncoded systems.The proposed sphere decoding uses weighted Hamming distance to construct its codeword list because received signals are discrete.Source: §VII · p. 24, discrete nature of received signals.… · p. 25

discrete nature of received signals. We have also characterized the performance-complexity tradeoff achieved by the proposed OSD, in terms of its design parameters.

  • Future work includes extending OSD to frequency-selective channels and to low-resolution ADCs beyond one-bit precision.The paper also identifies lower-complexity sphere-list construction as a possible extension.Source: discrete nature of received signals.… · p. 25

APPENDIX A

The proof bounds the probability that the transmitted codeword falls outside the sphere list by expressing received-sign errors as events and enlarging the associated sets. It then approximates the resulting probability using the OSD weights.

PROOF OF THEOREM 1

  • The proof assumes equally likely transmitted symbol vectors and uses independent noise components to factor the pairwise probability.The channel matrix is fixed, making the OSD weight vectors deterministic.Source: PROOF OF THEOREM 1 · p. 25
  • A binary error vector marks received-signal sign flips, and its events represent whether a sub-vector falls outside the sphere list.The proof rewrites the probability using sets of error vectors satisfying the indicator condition, then extends those sets to obtain an upper bound.Source: PROOF OF THEOREM 1 · pp. 26–27

k (L). For this, let d(g)

  • The extended-set bound is approximated using the OSD weights; the Q-function approximation has bounded error below 10^-3.Substitution yields the approximate SEP upper bound in (44).Source: k (L). For this, let d(g) · p. 27
Loading 1709.04163v2…