Box-Shift: Fixed-Complexity Counter-Hypothesis Generation for Soft-Output MIMO Box Decoding

arXiv:2611.06566 · eess.SP · Submitted 2026-11-04 · Read on arXiv

Listen

Radio episode about this paper

Transcript

Introduction to the show: ident: Electrical Engineering. The day in electrical engineering: signals, systems and the hardware that carries them.

Rosa: We're looking at the paper: "Box-Shift: Fixed-Complexity Counter-Hypothesis Generation for Soft-Output MIMO Box Decoding".

Dev: Here's the gist of the paper. Box Decoding is extended to soft-output detection by proposing the Box-Shift algorithm, which addresses the missing counter-hypothesis problem in coded systems The proposed method shifts the existing box to the nearest node carrying the complementary value of each Gray-coded bit at each detection layer This analytical solution improves upon Bit-Flip in both computational complexity and coded performance Coded 4×4 MIMO simulations using 5G NR low-density paritycheck (LDPC) coding show that Box Decoding with Box-Shift achieves a 0.7–1.5 dB gain in Eb/N0 over the same detector with Bit-Flip at a bit error rate of 10−5, with equal soft-candidate budgets Pruning redundant reasoning tokens The Box-Shift algorithm is designed to solve the missing counter-hypothesis (MCH) problem by analytically identifying the partially optimal counter-hypothesis using one inverter per bit and updating the path metric through an index-domain increment This method preserves the sort-free, QAM-order-independent structure of Box Decoding The closed-form determination of the partially optimal CH index is derived by partitioning the Gray-coded axis into contiguous regions where gl(n) has the same value For a given bit position l, a valid CH index must lie in a region with the opposite bit value, i.e., gl(nCH)!= gl(nA) The partially optimal CH index nF is then identified as the index nearest to nA that satisfies this condition How the training signal is built The system model considers a spatially multiplexed MIMO system with N transmit and N receive antennas employing bit-interleaved coded modulation The received signal is modeled as y = Hx + w, where x ∈ AN is the transmitted symbol vector, H ∈ C NxN is the channel matrix, and w ∼ CN (0, N0IN) is the additive noise vector The max-log approximation of the a posteriori LLR of each coded bit over a reduced candidate list L is given by equation (4) A finite LLR can be computed directly from this approximation only if both intersections, L ∩ X +1 i,l and L ∩ X −1 i,l, are nonempty Where the gains come from The performance gains of Box-Shift over Bit-Flip stem from its ability to locate the partially optimal CH node which provides the smallest PED increment For each bit, Box-Shift shifts the box along that bit’s axis onto the partially optimal CH index starting from the anchored node The two Box-Shift mechanisms are either the closest-node mechanism (Box-Shift-CN) or the full-box mechanism (Box-Shift-FB) The Box detector works on the integer index map, and BoxShift is developed in the index domain Complexity comparison The complexity comparison reveals that Box-Shift needs only the single inverter of (20) per bit, independent of the QAM order and without any Gray-code conversion In contrast, every Bit-Flip flip passes through the Gray (de)mapping, realized as serial decoding chains or as look-up tables that grow with A Table I shows that Box-Shift spends a quarter of Bit-Flip’s multiplications and one more addition per symbol with L candidates and nearly a quarter fewer with 2L Coded BER performance Link-level simulations demonstrate that Box-Shift outperforms Bit-Flip for both candidate budgets, gaining 0.9 and 1.5 dB in Eb/N0 over Bit-Flip-SP at BER 10−5 for QAM-64 and QAM-256, respectively The block error rate (BLER) shows the same ranking, with Box-Shift gains 0.3 and 0.5 dB over BitFlip-SP at BLER 10−3 for QAM-64 and QAM-256 The gap of the B = 4 box to the SD bound grows with the QAM order Box-Shift extends the sort-free, QAM-order-independent Box Decoding to coded systems by solving its missing counter-hypothesis problem Coded 4×4 simulations show 0.7–1.5 dB gains over Bit-Flip at BER 10−5 at equal candidate budget, a 1.4–1.7 dB lead over K-Best with Bit-Flip-SP at the same candidate budget and a 4–6 dB margin over MMSE-SIC Future work includes a VLSI implementation of Box-Shift algorithm and iterative detection–decoding REFERENCES arXiv:2611.06566v1

eess.SP: 4 Nov 2026 Box-Shift: Fixed-Complexity Counter-Hypothesis Generation for Soft-Output MIMO Box Decoding Shengchun Yang∗, Amit Sravan Bora†, Emil Matus∗, and Gerhard Fettweis∗∗Vodafone Chair Mobile Communications Systems, Technische Universität Dresden, Dresden, Germany†G.

Rosa: S.

Dev: Sanyal School of Telecommunications, Indian Institute of Technology Kharagpur, Kharagpur, IndiaEmail: shengchun.yang@tu-dresden.de, amitbora@gssst.iitkgp.ac.in Email: emil.matus@tu-dresden.de, gerhard.fettweis@tu-dresden.de Abstract—Box Decoding is a sort-free tree-search multipleinput multiple-output (MIMO) detector with a fixed per-layer cost independent of the quadrature amplitude modulation (QAM) order Its regular datapath is well suited to hardware implementation, but the detector has so far been limited to hardoutput operation in uncoded systems Its fixed four-point box spans two adjacent Gray-coded QAM levels per axis, leaving most bits without counter-hypotheses for higher-order QAM This missing counter-hypothesis (MCH) problem prevents the direct computation of finite max-log log-likelihood ratios (LLRs) We propose the Box-Shift algorithm, which shifts the existing box to the nearest node carrying the complementary value of each Gray-coded bit at each detection layer Unlike Bit-Flip, Box-Shift analytically identifies the partially optimal counter-hypothesis using one inverter per bit and updates the path metric through an index-domain increment The proposed method preserves the sort-free, QAM-order-independent structure of Box Decoding Coded 4×4 MIMO simulations using 5G NR low-density paritycheck (LDPC) coding show that Box Decoding with Box-Shift achieves a 0.7–1.5 dB gain in Eb/N0 over the same detector with Bit-Flip at a bit error rate of 10−5, with equal soft-candidate budgets For the soft-candidate metrics, the incremental update of Box-Shift needs 75% fewer real multiplications than the explicit evaluation of Bit-Flip at a comparable number of real additions Index Terms—MIMO detection, soft-output detection, Box Decoding, counter-hypothesis generation, Gray-coded QAM I.

Rosa: INTRODUCTION Spatial multiplexing and high-order quadrature amplitude modulation (QAM) increase the spectral efficiency of multipleinput multiple output (MIMO) systems, but also make data detection more demanding Exhaustive maximum-likelihood (ML) detection searches all AN symbol vectors for N streams and a constellation A, and its cost grows rapidly with the stream count and the QAM order

1: Linear zero-forcing (ZF) and linear minimum mean-square-error (LMMSE) detectors have low complexity, but their performance deteriorates in ill-conditioned channels and in the presence of multi-user interference

2: Modern systems therefore need low-complexity nonlinear detectors that approach ML performance Tree-search-based detectors such as sphere decoding (SD) attain ML performance with channel-dependent, variable complexity perplexity

4: Box Decoding instead expands a fixed ‘box’ around a zero-forcing reference at each layer In this paper, we extend the existing Box Decoding framework to soft-output detection by incorporating bit-level log-likelihood ratio (LLR) computation for coded systems II.

Title and authors: Rosa: So we're looking at this paper called "Box-Shift: Fixed-Complexity Counter-Hypothesis Generation for Soft-Output MIMO Box Decoding". Rosa is a field roboticist, so I’m curious if this works out outside the lab and how long it holds up when things get messy.

Dev: It sounds like they are tackling a specific problem in MIMO detection, which is usually about finding the right symbol vector when you have multiple antennas and high-order modulation.

Rosa: Yeah, it seems to be about extending Box Decoding into soft-output detection, which means we’re dealing with those log-likelihood ratios.

Dev: Exactly. The authors are proposing this new Box Shift algorithm because they identified a missing part in the existing system called the missing counter-hypothesis problem.

Rosa: That sounds really technical, but I want to get the plain idea of what that means for us in terms of practical performance on a real channel.

Dev: Basically, standard Box Decoding gets stuck when it has high-order QAM because it misses some crucial possibilities for certain bits. This problem prevents them from calculating the actual finite log-likelihood ratios they need to make decisions.

The paper's summary: Rosa: So, what’s the core of what they did? What exactly is this Box Shift algorithm supposed to solve when it says it’s an analytical solution?

Dev: They introduce a method that shifts the existing box to the nearest node carrying the complementary value for each Gray-coded bit at every detection layer. This is described as analytically identifying the partially optimal counter-hypothesis using just one inverter per bit.

Rosa: One inverter per bit sounds simple, but how does that help them fix this missing counter-hypothesis problem that stops them from getting finite LLRs?

Dev: Because it lets them update the path metric through an index domain increment. It also provides a second counter-hypothesis for every bit without needing extra search cost. They claim this method preserves the sort-free structure and keeps it independent of the QAM order, which is a big deal for hardware implementation.

Rosa: So, if I’m thinking about the practical side, what does that mean when you run these simulations?

Dev: The paper shows that compared to Bit-Flip methods, Box Shift actually improves both computational complexity and coded performance. They achieved a zero point seven to one point five decibel gain in Eb over N zero over the same detector when the bit error rate was one time ten to the negative five, even when they used equal soft-candidate budgets.

The paper's improvements: Rosa: That performance gain sounds promising, but what are these specific improvements they highlight compared to something like Bit-Flip? I want to know exactly what makes it better.

Dev: The main improvement is that Box Shift finds the node that gives the smallest path metric increment for each bit by shifting the box along that bit’s axis onto that partially optimal counter-hypothesis index.

Rosa: And they mentioned two versions of this shift mechanism, right? The closest-node mechanism and the full-box mechanism? Which one do you think is more useful when we’re trying to keep things running fast?

Dev: They show both mechanisms. The Box detector operates on the integer index map, and Box Shift is developed in that index domain. The complexity comparison shows that Box Shift only needs that single inverter per bit, independent of the QAM order or any Gray-code conversion steps.

Rosa: That’s a huge win for hardware implementation because it avoids those complex mappings that Bit-Flip has to deal with every time it runs. What about the operational cost?

Dev: Table one shows that Box Shift spends only a quarter of the multiplications and one more addition per symbol with L candidates, and nearly a quarter fewer with two times L compared to Bit-Flip's explicit metric evaluation. That’s a significant reduction in operations.

Conclusion: Rosa: So, wrapping up this whole discussion on "Box-Shift: Fixed-Complexity Counter-Hypothesis Generation for Soft-Output MIMO Box Decoding," what’s the final word on how this affects the real world of wireless communication?

Dev: It extends Box Decoding to coded systems by solving that missing counter-hypothesis problem analytically, which means we can now compute finite maximum log log likelihood ratios. This is what unlocks soft output detection where it used to be blocked.

Rosa: The simulation results show a zero point seven to one point five decibel gain in Eb over N zero over Bit-Flip at a bit error rate of one time ten to the negative five, with equal soft-candidate budgets. That’s a concrete metric for performance improvement.

Dev: And for the soft candidate metrics specifically, Box Shift needs seventy-five percent fewer real multiplications than the explicit evaluation of Bit-Flip at a comparable number of real additions. It preserves that sort free structure while enabling soft output detection where Bit-Flip fails.

Rosa: I’m just thinking about how this scales with higher QAM orders, since that was the initial hurdle for Box Decoding in uncoded systems.

Dev: The gap between the four point box and the signal detection bound grows with the QAM order, so this method helps manage that growth better than what we saw before.

Rosa: Well, it seems like a solid analytical solution that makes soft-output detection feasible for coded systems without a huge increase in computational load.

Dev: It definitely shows how moving the complexity into the index domain can give us significant gains over methods that rely on explicit metric evaluation of every single candidate.

Shengchun Yang, Amit Sravan Bora, Emil Matus, Gerhard Fettweis

Technische University of Dresden · Indian Institute of Technology Kharagpur

eess.SP

Submitted: 2026-11-04

Updated: 2026-11-04

License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/

Importance score: 87/100

The gist: Box Decoding is extended to soft-output detection by proposing the Box-Shift algorithm, which addresses the missing counter-hypothesis problem in coded systems The proposed method shifts the existing…

Key concepts

Box Decoding
A tree-search MIMO detector that expands a fixed 'box' around a zero-forcing reference at each detection layer. It is sort-free and its cost per layer remains constant regardless of the QAM order, making it well-suited for hardware implementation.
Missing Counter-Hypothesis (MCH) Problem
A challenge in soft-output Box Decoding where the fixed box structure leaves many bits without a counter-hypothesis. This prevents direct computation of finite log-likelihood ratios (LLRs), which are needed for soft detection, necessitating a new solution.
Box-Shift Algorithm
The proposed method that solves the MCH problem by analytically identifying the partially optimal counter-hypothesis using one inverter per bit and updating path metrics via an index-domain increment. This preserves Box Decoding's structure while enabling finite LLR computation in coded systems.

Terminology

Summary

Box Decoding is extended to soft-output detection by proposing the Box-Shift algorithm, which addresses the missing counter-hypothesis problem in coded systems The proposed method shifts the existing box to the nearest node carrying the complementary value of each Gray-coded bit at each detection layer This analytical solution improves upon Bit-Flip in both computational complexity and coded performance Coded 4×4 MIMO simulations using 5G NR low-density paritycheck (LDPC) coding show that Box Decoding with Box-Shift achieves a 0. p. 27–1.5 dB gain in Eb/N0 over the same detector with Bit-Flip at a bit error rate of 10−5, with equal soft-candidate budgets

Pruning redundant reasoning tokens

The Box-Shift algorithm is designed to solve the missing counter-hypothesis (MCH) problem by analytically identifying the partially optimal counter-hypothesis using one inverter per bit and updating the path metric through an index-domain increment This method preserves the sort-free, QAM-order-independent structure of Box Decoding The closed-form determination of the partially optimal CH index is derived by partitioning the Gray-coded axis into contiguous regions where gl(n) has the same value For a given bit position l, a valid CH index must lie in a region with the opposite bit value, i.e., gl(nCH)!= gl(nA) The partially optimal CH index nF is then identified as the index nearest to nA that satisfies this condition

How the training signal is built

The system model considers a spatially multiplexed MIMO system with N transmit and N receive antennas employing bit-interleaved coded modulation The received signal is modeled as y = Hx + w, where x ∈ AN is the transmitted symbol vector, H ∈ C NxN is the channel matrix, and w ∼ CN (0, N0IN) is the additive noise vector The max-log approximation of the a posteriori LLR of each coded bit over a reduced candidate list L is given by equation (4) A finite LLR can be computed directly from this approximation only if both intersections, L ∩ X +1 i,l and L ∩ X −1 i,l, are nonempty

Where the gains come from

The performance gains of Box-Shift over Bit-Flip stem from its ability to locate the partially optimal CH node which provides the smallest PED increment For each bit, Box-Shift shifts the box along that bit’s axis onto the partially optimal CH index starting from the anchored node The two Box-Shift mechanisms are either the closest-node mechanism (Box-Shift-CN) or the full-box mechanism (Box-Shift-FB) The Box detector works on the integer index map, and BoxShift is developed in the index domain

Complexity comparison

The complexity comparison reveals that Box-Shift needs only the single inverter of (20) per bit, independent of the QAM order and without any Gray-code conversion In contrast, every Bit-Flip flip passes through the Gray (de)mapping, realized as serial decoding chains or as look-up tables that grow with A Table I shows that Box-Shift spends a quarter of Bit-Flip’s multiplications and one more addition per symbol with L candidates and nearly a quarter fewer with 2L

Coded BER performance

Link-level simulations demonstrate that Box-Shift outperforms Bit-Flip for both candidate budgets, gaining 0.9 and 1.5 dB in Eb/N0 over Bit-Flip-SP at BER 10−5 for QAM-64 and QAM-256, respectively The block error rate (BLER) shows the same ranking, with Box-Shift gains 0. p. 53 and 0.5 dB over BitFlip-SP at BLER 10−3 for QAM-64 and QAM-256 The gap of the B = 4 box to the SD bound grows with the QAM order

Conclusion

Box-Shift extends the sort-free, QAM-order-independent Box Decoding to coded systems by solving its missing counter-hypothesis problem Coded 4×4 simulations show 0.7–1.5 dB gains over Bit-Flip at BER 10−5 at equal candidate budget, a 1. p. 54–1.7 dB lead over K-Best with Bit-Flip-SP at the same candidate budget and a 4–6 dB margin over MMSE-SIC Future work includes a VLSI implementation of Box-Shift algorithm and iterative detection–decoding

REFERENCES

arXiv:2611.06566v1 [eess. p. 0SP] 4 Nov 2026

Box-Shift: Fixed-Complexity Counter-Hypothesis Generation for Soft-Output MIMO Box Decoding

Shengchun Yang∗, Amit Sravan Bora†, Emil Matus∗, and Gerhard Fettweis∗∗Vodafone Chair Mobile Communications Systems, Technische Universität Dresden, Dresden, Germany†G. S. Sanyal School of Telecommunications, Indian Institute of Technology Kharagpur, Kharagpur, IndiaEmail: shengchun. p. 1yang@tu-dresden. p. 1de, amitbora@gssst. p. 1iitkgp.ac.in Email: emil. p. 1matus@tu-dresden. p. 1de, gerhard. p. 1fettweis@tu-dresden. p. 1de

Abstract—Box Decoding is a sort-free tree-search multipleinput multiple-output (MIMO) detector with a fixed per-layer cost independent of the quadrature amplitude modulation (QAM) order Its regular datapath is well suited to hardware implementation, but the detector has so far been limited to hardoutput operation in uncoded systems Its fixed four-point box spans two adjacent Gray-coded QAM levels per axis, leaving most bits without counter-hypotheses for higher-order QAM This missing counter-hypothesis (MCH) problem prevents the direct computation of finite max-log log-likelihood ratios (LLRs) We propose the Box-Shift algorithm, which shifts the existing box to the nearest node carrying the complementary value of each Gray-coded bit at each detection layer Unlike Bit-Flip, Box-Shift analytically identifies the partially optimal counter-hypothesis using one inverter per bit and updates the path metric through an index-domain increment The proposed method preserves the sort-free, QAM-order-independent structure of Box Decoding Coded 4×4 MIMO simulations using 5G NR low-density paritycheck (LDPC) coding show that Box Decoding with Box-Shift achieves a 0.7–1.5 dB gain in Eb/N0 over the same detector with Bit-Flip at a bit error rate of 10−5, with equal soft-candidate budgets For the soft-candidate metrics, the incremental update of Box-Shift needs 75% fewer real multiplications than the explicit evaluation of Bit-Flip at a comparable number of real additions Index Terms—MIMO detection, soft-output detection, Box Decoding, counter-hypothesis generation, Gray-coded QAM

I. INTRODUCTION

Spatial multiplexing and high-order quadrature amplitude modulation (QAM) increase the spectral efficiency of multipleinput multiple output (MIMO) systems, but also make data detection more demanding Exhaustive maximum-likelihood (ML) detection searches all AN symbol vectors for N streams and a constellation A, and its cost grows rapidly with the stream count and the QAM order [1] Linear zero-forcing (ZF) and linear minimum mean-square-error (LMMSE) detectors have low complexity, but their performance deteriorates in ill-conditioned channels and in the presence of multi-user interference [2] Modern systems therefore need low-complexity nonlinear detectors that approach ML performance Tree-search-based detectors such as sphere decoding (SD) attain ML performance with channel-dependent, variable complexity perplexity [4] Box Decoding instead expands a fixed ‘box’ around a zero-forcing reference at each layer In this paper, we extend the existing Box Decoding framework to soft-output detection by incorporating bit-level log-likelihood ratio (LLR) computation for coded systems

II. SYSTEM MODEL

Consider a spatially multiplexed MIMO system with N transmit and N receive antennas employing bit-interleaved coded modulation [17] The soft-output detector computes the a posteriori LLR of each coded bit as [19] L(ci,l y) = ln Pr[ci,l = +1 y] Pr[ci,l = −1 y] Under the maxlog approximation of (3) over a reduced candidate list L is [19] L(ci,l y) ≈ max x∈L∩X +1 i,l λ(x) − max x∈L∩X −1 i,l λ(x), where λ(x) = -∥y′ − Rx∥2/N0 is the log-likelihood metric A finite LLR can be computed directly from (4) only if both L ∩ X +1 i,l and L ∩ X −1 i,l are nonempty

III. HARD-OUTPUT BOX DECODING WITH DETERMINISTIC PRUNING

This section reviews the hard-output Box Decoding algorithm with deterministic pruning, which forms the basis of the proposed Box-Shift algorithm Detection proceeds through layers i = N,..., 1 of the tree, retaining K surviving paths per layer The box expansion and pruning rules follow [7] and [10], respectively

IV. SOFT-OUTPUT BOX DETECTION: BIT-FLIP LIMITATIONS AND THE BOX-SHIFT ALGORITHM

A box with B = 4 spans two adjacent Gray-coded QAM levels per axis, and adjacent Gray-coded labels differ in exactly one bit The natural first attempt is to apply Bit-Flip Bit-Flip usually lands beyond it, in Fig. 1a at the real-axis bits l = 1, 2 with a gap that widens with l, which could overestimate the LLR magnitude Bit-Flip usually lands beyond it, in Fig. p. 3 1a at the real-axis bits l = 1, 2 with a gap that widens with l, which could overestimate the LLR magnitude

V. NUMERICAL EVALUATION

Box-Shift outperforms Bit-Flip for both candidate budgets (Fig. 3) With the L-candidate mechanisms, Box-Shift-CN gains 0. p. 59 and 1.5 dB in Eb/N0 over Bit-Flip-SP at BER 10−5 for QAM-64 and QAM-256, respectively In both cases the gain grows with the modulation order and toward low BER, because Bit-Flip’s flipped node lies farther from the Gray crossing at higher order and overstates the LLRs The ICP curves overlap the SCP curves, so the pruning rule does not affect the coded BER Box-Shift-CN on the Box detector gains 1. p. 54–1.

Green — the paper says it, and the page is printed. Red — no passage carries it, so treat that sentence as unverified. The same check runs on your own text: check a summary against its source, $5.

Improvements for AI systems

  1. Box-Shift algorithm solves the missing counter-hypothesis problem by analytically identifying the partially optimal counter-hypothesis using one inverter per bit and updating path metrics through an index-domain increment, preserving a sort-free, QAM-order independent structure. This allows for finite maximum log log-likelihood ratios (LLRs) in coded systems where Bit-Flip fails.

  2. The system can achieve a 0.7 to 1.5 dB gain in Eb/N0 over Bit-Flip at a bit error rate of 10-5 with equal soft-candidate budgets, and requires 75% fewer real multiplications than the explicit evaluation of Bit-Flip at a comparable number of real additions for soft candidate metrics.

  3. The Box-Shift approach can be implemented to retain the sort-free, QAM-order independent structure of Box Decoding while enabling soft output detection by utilizing an analytical solution to the MCH problem.

  4. The system can reduce computational complexity significantly; for a given candidate budget, Box-Shift needs a quarter of the multiplications compared to Bit-Flip's explicit metric evaluation and one half to two thirds of the operations.

Related papers