PaperlayerView exact revision on arXiv

Source-linked AI summary

Efficient Decoders for Short Block Length Codes in 6G URLLC

Chentao Yue, Vera Miloslavskaya, Mahyar Shirvanimoghaddam, Branka Vucetic, Yonghui Li

arXiv:2206.09572v2cs.ITmath.IT

TL;DR

URLLC requires short-code decoding that balances reliability, low complexity, and flexibility, yet strong short codes can be difficult to decode efficiently. This paper reviews and compares candidate decoders on structured and random short codes, finding that the SCL-based sequential decoder has the best performance-complexity trade-off among those compared. It also identifies decoder-specific recommendations and research needs, including improving OSD's high-SNR complexity floor.

  • Problem

    Short block-length codes can have degraded BLER, while codes approaching the normal approximation bound may lack efficient decoders, complicating URLLC's reliability and latency demands.

    Source: §I · p. 1

  • Method

    The paper compares OSD, GRAND, SCL, and variations on structured and random short codes, and discusses decoder selections and research directions.

    Source: §I · pp. 1–2

  • Results

    The SCL-based sequential decoder has the best performance-complexity trade-off among compared schemes, while OSD closely approaches ML at high SNRs and GRAND's gap varies by code.

    Source: §I · p. 1, 1) Length-128 codes · p. 4

  • Takeaways & Limitations

    The paper recommends near-optimal short rate-compatible random codes for universal decoding and identifies decoder-specific choices for URLLC settings.

    Source: A. Rate-Compatible Codes with Near… · p. 6, §VI · p. 7

    OSD's Gaussian-elimination overhead creates a high-SNR complexity floor that precludes its application where BLER below 10−5 is required.

    Source: B. Enhancement of Universal Decoders · p. 6

Abstract

from arXiv · show

This paper reviews the potential channel decoding techniques for ultra-reliable low-latency communications (URLLC). URLLC is renowned for its stringent requirements including ultra-reliability, low end-to-end transmission latency, and packet-size flexibility. These requirements exacerbate the difficulty of the physical-layer design, particularly for the channel coding and decoding schemes. To satisfy the requirements of URLLC, decoders must exhibit superior error-rate performance \black{and} low decoding complexity. \black{Also, it is desired that decoders be universal} to accommodate various coding schemes. This paper provides a comprehensive review and comparison of different candidate decoding techniques for URLLC in terms of their error-rate performance and computational complexity for structured and random short codes. We further make recommendations of the decoder selections and suggest several potential research directions.

I. INTRODUCTION

URLLC couples very short latency and high reliability with flexible block lengths and coding rates, making short-code reliability and low-complexity decoding central design challenges. The paper compares candidate decoders and reports that the SCL-based sequential decoder offers the best performance-complexity trade-off among those compared.

I. INTRODUCTION

  • URLLC requires end-to-end latency of 25µs ∼1ms and BLER of 10−5 ∼10−7, supporting applications from augmented reality to mission-critical automation.The cited applications include tactile internet, augmented reality, metaverse, telesurgery, and factory automation.Source: §I · p. 1
  • Short block lengths can degrade BLER relative to longer blocks at the same code rate, creating a trade-off between block length and reliability.The normal approximation bound indicates that the maximum information-to-coded-bit ratio drops as block length decreases for a given error probability.Source: §I · p. 1
  • Codes approaching the normal approximation bound can lack efficient decoders; CRC-polar SCL decoding can approach ML performance but requires a large, computationally costly list.The introduction also notes that CRC-polar and PAC codes have reported gaps below 0.5 dB at BLER = 10−4, while turbo codes degrade severely and short-block LDPC codes have a gap above 1 dB to the bound.Source: §I · p. 1
  • Universal decoders can decode any binary linear code, accommodating bit-level block-length and rate granularity, including rate-compatible codes for IR-HARQ.The paper identifies OSD and GRAND as candidate universal decoders.Source: §I · p. 1
  • The SCL-based sequential decoder has the best performance-complexity trade-off among the compared schemes, while universal decoders still need efficiency improvements.The comparison covers OSD, GRAND, SCL, and their variations on short structured and random codes.Source: §I · p. 1

II. PERFORMANCE METRICS AND BENCHMARKS

The benchmarks assess decoder optimality and complexity, with universality also identified as desirable for URLLC. Optimality concerns achieving code ML performance, while low decoding complexity matters because decoding dominates processing latency.

II. PERFORMANCE METRICS AND BENCHMARKS

  • The paper frames optimality and complexity as key decoder metrics and identifies decoding universality as desirable for URLLC.Universality is addressed in the following subsection.Source: §II · p. 2

1) Optimality:

  • Optimality means a decoder achieves the code's ML performance, helping short codes exploit their error-correction capability.For example, near-ML OSD shortens a half-rate length-128 LDPC code's gap to the normal approximation bound from 1.75 dB under BP to 0.5 dB.Source: 1) Optimality · p. 2

2) Complexity:

  • Decoding complexity should be as low as possible because decoding latency dominates processing latency within URLLC's less-than-1-ms end-to-end budget.Processing latency also includes channel estimation and detection.Source: 2) Complexity · p. 2

3) Universality:

Decoding universality permits use of linear codes with flexible lengths and rates, while the paper introduces candidate decoding algorithms and describes OSD's reliability-based processing.

3) Universality:

  • Universality means decoding any linear block code, which supports bit-level block-length and rate granularity and use of best-known short codes.It also supports optimal short rate-compatible codes for IR-HARQ; conventional rate matching can yield suboptimal codes and unnecessary decoding complexity, such as SCL processing a shortened polar code's longer mother code.Source: 3) Universality · p. 2

III. CANDIDATE UNIVERSAL DECODING ALGORITHMS FOR URLLC

  • The paper introduces candidate URLLC decoders and defines C(n, k) as a binary linear code with length n, information length k, and rate k/n.The stated evaluation setting uses an AWGN channel with QPSK modulation.Source: §III · p. 2

A. Ordered-Statistics Decoding (OSD)

  • OSD reliability-orders received symbols, applies the same permutation to the generator matrix, uses Gaussian elimination, tests error patterns on the k most reliable bits, and re-encodes them.TEPs are processed by increasing Hamming weight up to the selected decoding order; order m = ⌈dH/4−1⌉ approaches ML performance for minimum distance dH.Source: A. Ordered-Statistics Decoding (OSD) · p. 2

B. Guessing Random Additive Noise Decoding (GRAND)

GRAND searches for a valid codeword by guessing noise sequences, and the first valid estimate is ML when queries follow strict descending likelihood. Its efficiency depends on channel and code conditions, while practical ordering approximations can affect performance.

B. Guessing Random Additive Noise Decoding (GRAND)

  • For memoryless channels, GRAND's first valid codeword is the ML estimate when noise sequences are queried in strict descending order of exact likelihood.For a binary symmetric channel, it guesses a noise sequence, subtracts it from the received vector, and checks codebook membership by syndrome.Source: B. Guessing Random Additive Noise… · p. 2
  • GRAND is intuitively efficient at high SNR or coding rate k/n; for a binary code in a BSC, it satisfies the ML criterion with 2^(n min(H_1/2, 1−k/n)) noise queries.H_1/2 is Rényi entropy that decreases as SNR increases.Source: B. Guessing Random Additive Noise… · p. 2
  • Ordered-reliability GRAND generates noise sequences offline by ascending logistic weights, providing acceptable BLER and computational complexity, but exact likelihood ordering is difficult to perform on the fly.The supplied Fig. 1 caption identifies BLER comparisons for length-128 eBCH, CRC-11 polar, PAC, and random codes decoded by OSD, GRAND, SCL, SCS, and SQ.Source: B. Guessing Random Additive Noise… · p. 3, Figure 1 · p. 3

C. Successive Cancellation List (SCL), Successive Cancellation Stack (SCS) and Sequential (SQ) Decoding

SCL, SCS, and SQ improve on successive cancellation by exploring multiple or selectively extended paths, but their near-ML decoding of unstructured random codes is prohibitively complex. Their performance and complexity also depend on code structure.

C. Successive Cancellation List (SCL), Successive Cancellation Stack (SCS) and Sequential (SQ) Decoding

  • SCL can reach ML performance with a sufficiently large list, while SCS and SQ use sequential path exploration to avoid fruitless low-probability paths.SCL retains up to L paths; SCS and SQ extend one path at a time, and the Fano-based sequential decoder trades lower space use for added time complexity.Source: C. Successive Cancellation List (SCL),… · p. 3
  • Near-ML decoding of unstructured random codes is prohibitively complex for SCL, SCS, and SQ, so they are not universal decoders.These techniques can apply to binary linear codes whose length is a power of two, but performance and complexity depend substantially on code structure.Source: C. Successive Cancellation List (SCL),… · p. 3

IV. COMPARISON OF DECODERS FOR URLLC

  • The comparison evaluates decoder BLER and complexity for short eBCH, CRC-polar, PAC, and random codes.The BLER evaluation includes lengths 64 and 128, near-ML list sizes up to 32768, and an ML lower bound estimated from observed ML errors.Source: §IV · p. 3, A. BLER Performance · p. 3

A. BLER Performance

  • SCL, SCS, and SQ have almost identical BLER for the considered short codes when using the same list size.Their behavior is assessed alongside OSD and GRAND in the decoder comparisons.Source: A. BLER Performance · p. 3

1) Length-128 codes:

For length-128 codes, OSD and list/sequential decoders approach ML performance for rate-1/2 structured codes, while high-rate code performance differs. For length-64 codes, eBCH outperforms CRC-polar and random codes.

1) Length-128 codes:

  • The (128, 64) eBCH, CRC-polar, and PAC codes have similar ML BLER, which OSD and SCL/SCS/SQ approach; random codes perform closely to eBCH under OSD.GRAND is used only for the high-rate (128, 106) codes because its complexity for (128, 64) codes is prohibitively high.Source: 1) Length-128 codes · p. 4
  • At high SNR, eBCH outperforms CRC-polar and random (128, 106) codes; random and CRC-polar perform similarly.OSD closely approaches ML for all considered codes, while GRAND is about 0.1 dB from the eBCH and CRC-polar ML bounds; its gap is attributed to suboptimal noise-query ordering.Source: 1) Length-128 codes · p. 4

2) Length-64 codes:

  • At BLER = 10^-5, CRC-polar and random (64, 36) codes lose 0.25 dB of coding gain to eBCH, whose ML bound OSD and SCL/SCS/SQ reach.For eBCH, GRAND is about 0.4 dB from the ML bound at high SNR; CRC-polar and random codes perform similarly under the considered decoders.Source: 2) Length-64 codes · p. 4

B. Performance-Complexity Trade-offs

The paper compares decoder complexity against BLER performance while varying decoder parameters. The results distinguish code-structure-dependent decoders from universal decoders and show that complexity can vary with SNR.

B. Performance-Complexity Trade-offs

  • Decoder trade-offs are measured by operations per information bit, counting additions, multiplications, and comparisons.Complexity can be adjusted through decoder parameters, trading increased operations for improved BLER.Source: B. Performance-Complexity Trade-offs · p. 4

1) Length-128 codes:

  • For length-128 codes at BLER = 10^-4, PB-OSD and GRAND have nearly unvaried complexity across codes of the same rate, whereas SCL, SCS, and SQ rely heavily on code structure.The comparison varies list size, PB-OSD threshold probability, BMA control-band cardinality, and GRAND query limit.Source: 1) Length-128 codes · p. 4
  • At fixed SNR for the (128, 106) eBCH code, GRAND has the highest operations-per-information-bit complexity and SQ the lowest.GRAND and OSD can exploit parallel noise-query and test-error-pattern processing, while parallelizing SCL, SCS, and SQ is more complicated; operation counts therefore need not represent latency.Source: 1) Length-128 codes · p. 4

2) Length-64 codes:

  • For length-64 codes, universal decoders PB-OSD, BMA, and GRAND have complexity determined by block length and information length, not code structure.PB-OSD can decode selected random codes that perform similarly to eBCH and significantly better than pure random codes; SQ is also notably efficient on eBCH.Source: 2) Length-64 codes · p. 5

C. Other Considerations for Decoding Complexity

Decoder complexity is evaluated across SNRs for a shortened polar code and a best-known code. The relative complexity of the decoders changes with SNR.

1) Complexity of near ML Decoders Operating at Different SNRs:

2) Worst-Case Complexity:

Worst-case decoding complexity varies substantially across decoders, and block-length scaling further limits the suitability of some universal decoders to short codes.

2) Worst-Case Complexity:

  • For the (82, 68) 5G CRC-11 polar code, PB-OSD has the lowest simulated worst-case complexity, followed by SQ and GRAND.SCL has constant worst-case complexity; SCS and SQ have worst-case complexity similar to SCL, while PB-OSD and BMA are bounded by original OSD complexity.Source: 2) Worst-Case Complexity · p. 5
  • GRAND has very high worst-case complexity unless the code rate is close to 1, while early termination typically causes negligible performance degradation.Early termination can stop decoding after a set operation limit, such as visited tree nodes, OSD TEPs, or GRAND noise queries.Source: 2) Worst-Case Complexity · p. 5

3) Complexity Scaling with Block-Length:

  • SC scales as O(n log n), SCL as O(Ln log n), and SCS and SQ approach O(n log n) at high SNR; OSD variants and GRAND can scale rapidly with block-length.OSD variants grow faster than O(n min(k, n − k)^2), and the text notes that universal OSD and GRAND are better suited to short block-length codes.Source: 3) Complexity Scaling with Block-Length · p. 5

V. RECOMMENDATIONS AND POTENTIAL RESEARCH DIRECTIONS

The recommendations favor universal decoding for flexible short-code choices and propose near-optimal rate-compatible codes for incremental-redundancy HARQ. Selected random rate-compatible codes outperform several structured alternatives at half to high rates.

A. Rate-Compatible Codes with Near Optimal Performance

  • Universal decoders can use best-known linear codes with strong error-correction capability across flexible block-lengths and rates.The paper recommends designing near-optimal short rate-compatible codes for universal decoders by optimizing minimum Hamming distance and weight spectrum.Source: A. Rate-Compatible Codes with Near… · p. 6

V. RECOMMENDATIONS AND POTENTIAL RESEARCH DIRECTIONS

  • Rate-compatible codes keep the information block-length fixed and use nested generator matrices, supporting bit-level granularity for URLLC.The recommendations target rate-compatible codes for incremental-redundancy HARQ.Source: A. Rate-Compatible Codes with Near… · p. 6, §V · p. 6

A. Rate-Compatible Codes with Near Optimal Performance

  • Selected random rate-compatible codes outperform RC eBCH at half to high rates, as well as RC polar and RC CRC-polar codes.The comparison uses k = 16 and block-lengths from n = 17 to n = 64 under ML decoding; the random codes are constructed by sequentially selecting and appending columns.Source: Figure 6 · p. 6, A. Rate-Compatible Codes with Near… · p. 6

B. Enhancement of Universal Decoders

The paper identifies complexity and noise-query ordering as unresolved challenges for universal decoders, while recommending different code-decoder pairs for different operating conditions. Its conclusion highlights improved OSD and SQ-decoded CRC-polar codes, alongside further complexity research.

B. Enhancement of Universal Decoders

  • OSD's Gaussian-elimination complexity floor precludes its use where BLER below 10^-5 is required, and a prototype exploiting TEP parallelism is still lacking.The paper identifies breaking the floor and demonstrating an efficient real-world prototype as research needs.Source: B. Enhancement of Universal Decoders · pp. 6–7
  • GRAND is efficient only for high-rate short codes at high SNRs, and suboptimal noise-query ordering leaves a gap to ML BLER performance.The paper says optimal on-the-fly query ordering may remove GRAND's low-complexity feature, motivating an efficient ordering algorithm.Source: B. Enhancement of Universal Decoders · p. 7

C. Pairs of Codes and Decoders

  • Code-decoder pairs can be selected for latency and complexity budgets, while efficient universal decoders could simplify otherwise complicated hybrid systems.The paper recommends SQ with CRC-polar codes at low-to-moderate rates and eBCH with SQ for high rates or very short blocks.Source: C. Pairs of Codes and Decoders · p. 7

VI. CONCLUSION

  • Length-128 CRC-polar codes decoded by SQ offer an excellent performance-complexity trade-off, while eBCH with SQ suits high rates and very short blocks.PB-OSD is suggested at low SNRs.Source: §VI · p. 7
Loading 2206.09572v2…