System and method for decoding data

Patent metadata

Field	Value
Publication number	US-12451990-B2
Application number	US-202318390209-A
Country	US
Kind code	B2
Filing date	Dec 20, 2023
Priority date	Dec 23, 2022
Publication date	Oct 21, 2025
Grant date	Oct 21, 2025

Abstract

A method for decoding data comprises receiving a sequence of symbols from a data sender over a noisy data channel. At a first decoder, a first search for a candidate error pattern is performed, within a search region, among a plurality of candidate error patterns, and an indication of a failure of the first search is output to a second decoder when no candidate error pattern is found within the search region. At the second decoder, a second search is performed, in parallel with the first search, for the candidate error pattern by evaluating the candidate error patterns for codebook membership based on the sequence of symbols, one or more of the candidate error patterns being skipped from the second search based on the indication of the failure of the first search. The sequence of symbols is decoded based on an outcome of the first search and the second search.

First claim

What is claimed is:

1. A method for decoding data, the method comprising:
at a data receiver comprising at least one first decoder and at least one second decoder configured to run in parallel with the first decoder:
receiving a sequence of symbols from a data sender over a noisy data channel;
at the at least one first decoder:
performing, within a search region, a first search for a candidate error pattern among a plurality of candidate error patterns; and
outputting, to the at least one second decoder, an indication of a failure of the first search when no candidate error pattern is found within the search region;
at the at least one second decoder:
performing, in parallel with the first search, a second search for the candidate error pattern by evaluating the plurality of candidate error patterns for codebook membership based on the sequence of symbols, one or more of the plurality of candidate error patterns being skipped from the second search based on the indication of the failure of the first search; and
decoding the sequence of symbols based on an outcome of the first search and the second search.

2. The method of claim 1 , wherein the at least one first decoder implements a Sphere Decoding (SD) technique and the at least one second decoder implements a Guessing Random Additive Noise Decoding (GRAND) technique.

3. The method of claim 2 , wherein the at least one first decoder implements one of multiple tree search SD (MSD), SD with fixed lower bound, list SD, stack SD, and cyclic redundancy check (CRC)-aided SD.

4. The method of claim 3 , wherein the at least one first decoder implements an efficient multiple tree search SD (EMSD) decoding technique.

5. The method of claim 2 , wherein the at least one second decoder implements one of soft GRAND (SGRAND), ordered reliability bits GRAND (ORBGRAND), ORBGRAND, GRAND with abandonment (GRANDAB), GRAND with symbol reliability information (SRGGRAND), GRAND Markov Order (GRAND-Mo), and List-GRAND.

6. The method of claim 2 , wherein the search region is defined by a radius, further wherein performing the first search for the candidate error pattern comprises progressively expanding the radius of the search region until the candidate error pattern is found within the search region.

7. The method of claim 1 , wherein receiving the sequence of symbols comprises receiving a code having a triangular generator matrix.

8. The method of claim 7 , wherein receiving the sequence of symbols comprises receiving one of a polar code and a Read-Muller (RM) code.

9. The method of claim 1 , wherein receiving the sequence of symbols comprises receiving a Bose-Chaudhuri-Hocquenghem (BCH) code.

10. A data receiver comprising:
a receiving unit configured for receiving a sequence of symbols from a data sender over a noisy data channel;
a decoding unit comprising at least one first decoder and at least one second decoder configured to run in parallel with the first decoder,
the at least one first decoder configured for:
performing, within a search region, a first search for a candidate error pattern among a plurality of candidate error patterns; and
outputting, to at least one second decoder, an indication of a failure of the first search when no candidate error pattern is found within the search region; and
the at least one second decoder configured for:
performing, in parallel with the first search, a second search for the candidate error pattern by evaluating the plurality of candidate error patterns for codebook membership based on the sequence of symbols, one or more of the plurality of candidate error patterns being skipped from the second search based on the indication of the failure of the first search; and
the decoding unit configured for decoding the sequence of symbols based on an outcome of the first search and the second search.

11. The data receiver of claim 10 , wherein the at least one first decoder implements a Sphere Decoding (SD) technique and the at least one second decoder implements a Guessing Random Additive Noise Decoding (GRAND) technique.

12. The data receiver of claim 11 , wherein the at least one first decoder implements one of multiple tree search SD (MSD), SD with fixed lower bound, list SD, stack SD, and cyclic redundancy check (CRC)-aided SD.

13. The data receiver of claim 12 , wherein the at least one first decoder implements an efficient multiple tree search SD (EMSD) decoding technique.

14. The data receiver of claim 11 , wherein the at least one second decoder implements one of soft GRAND (SGRAND), ordered reliability bits GRAND (ORBGRAND), ORBGRAND, GRAND with abandonment (GRANDAB), GRAND with symbol reliability information (SRGGRAND), GRAND Markov Order (GRAND-Mo), and List-GRAND.

15. The data receiver of claim 11 , wherein the search region is defined by a radius, further wherein the at least one first decoder is configured for performing the first search for the candidate error pattern comprising progressively expanding the radius of the search region until the candidate error pattern is found within the search region.

16. The data receiver of claim 10 , wherein the receiving unit is configured for receiving the sequence of symbols comprising receiving a code having a triangular generator matrix.

17. The data receiver of claim 16 , wherein the receiving unit is configured for receiving the sequence of symbols comprising receiving one of a polar code and a Read-Muller (RM) code.

18. The data receiver of claim 10 , wherein the receiving unit is configured for receiving the sequence of symbols comprising receiving a Bose-Chaudhuri-Hocquenghem (BCH) code.

19. The data receiver of claim 10 , further comprising an output unit configured for receiving a decoded sequence of symbols from the decoding unit and for transmitting the decoded sequence of symbols to an external device.

20. A non-transitory computer readable medium having stored thereon program code executable by at least one processor for:
receiving a sequence of symbols over a noisy data channel;
performing, within a search region, a first search for a candidate error pattern among a plurality of candidate error patterns;
outputting an indication of a failure of the first search when no candidate error pattern is found within the search region;
performing, in parallel with the first search, a second search for the candidate error pattern by evaluating the plurality of candidate error patterns for codebook membership based on the sequence of symbols, one or more of the plurality of candidate error patterns being skipped from the second search based on the indication of the failure of the first search; and
decoding the sequence of symbols based on an outcome of the first search and the second search.

Assignees

• The Royal Institution For The Advancement Of Learning / Mcgill Univ

Inventors

• Zhou Huayi
• Gross Warren J

Classifications

• H03M13/6511

  Support of multiple decoding rules, e.g. combined MAP and Viterbi decoding · CPC title

• H03M13/451

  using a set of candidate code words, e.g. ordered statistics decoding [OSD] · CPC title

• H03M13/3944

  for block codes, especially trellis or lattice decoding thereof · CPC title

• H03M13/3707

  Adaptive decoding and hybrid decoding, e.g. decoding methods or techniques providing more than one decoding algorithm for one code · CPC title

• H03M13/2975

  Judging correct decoding, e.g. iteration stopping criteria · CPC title