IP Library › Granted Patent US 12,451,990
Granted Patent B2
US 12,451,990 · App. 18/390,209 · Granted Oct 21, 2025

System and method for decoding data

Inventors: Huayi Zhou (Montreal, CA); Warren J. Gross (Cote-St-Luc, CA)
Assignee: THE ROYAL INSTITUTION FOR THE ADVANCEMENT OF LEARNING / MCGILL UNIVERSITY
H04L1/0054
View Patent ↗
Loading inventors, assignments & file history…
Monitor This Case
Get email alerts when status or documents change.
Order Certified Copies
Most orders are placed with the USPTO same day — all within 24 business hours.
Order via The Patent Place →
Pre-filled with this patent's details
Quick Facts
Patent No.
US 12,451,990
App. No.
18/390,209
Granted
Oct 21, 2025
Kind
B2
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.

Claims (41)

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.

Assignments (1)
ASSIGNMENT OF ASSIGNOR'S INTEREST Recorded Nov 1, 2024
From: ZHOU, HUAYI; GROSS, WARREN J.
To: THE ROYAL INSTITUTION FOR THE ADVANCEMENT OF LEARNING / MCGILL UNIVERSITY
Reel/Frame 069100/0042 →
Continuity (2)
Provisional Application 63434952 · Dec 23, 2022
Related Publication 20250211364A1 · Jun 26, 2025
References Cited (32)
US 10902216B2 · Lee · 2021 [cited by examiner]
US 10970508B2 · Negro · 2021 [cited by examiner]
US 11259014B2 · Furht · 2022 [cited by examiner]
US 20020122221A1 · Kubo · 2002 [cited by examiner]
US 20060273457A1 · Sel · 2006 [cited by examiner]
US 20080270961A1 · Mead · 2008 [cited by examiner]
US 20110202815A1 · Toda · 2011 [cited by examiner]
US 20150003262A1 · Eder · 2015 [cited by examiner]
US 20200106460A1 · Ku · 2020 [cited by examiner]
US 20210384918A1 · Solomon · 2021 [cited by examiner]
Zhu et al., On performance of sphere decoding and Markov chain Monte Carlo detection methods, IEEE, Signal Processing Letters, vol. 12, No. 10, pp. 669 to 672. (Year: 2005). [cited by examiner]
Duffy et al., “Guessing noise, not code-words”, 2018 IEEE International Symposium on Information Theory, DOI: 10.1109/ISIT.2018.8437648. [cited by applicant]
Duffy et al., “Capacity-Achieving Guessing Random Additive Noise Decoding”, IEEE Transactions on Information Theory, 2019, DOI: 10.1109/TIT.2019.2896110. [cited by applicant]
Duffy et al., “Guessing random additive noise decoding with soft detection symbol reliability information—SGRAND”, 2019 IEEE International Symposium on Information Theory, DOI: 10.1109/ISIT.2019.8849297. [cited by applicant]
Dufy et al., “Guessing Random Additive Noise Decoding With Symbol Reliability Information (SRGRAND)”, IEEE Transactions on Communications (2022), DOI: 10.1109/TCOMM.2021.3114315. [cited by applicant]
Valembois et al., “An Improved Method to Compute Lists of Binary Vectors That Optimize a Given Weight Function With Application to Soft-Decision Decoding”, IEEE Communications Letters, 2001, DOI: 10.1109/4234.966032. [cited by applicant]
Solomon et al., “Soft Maximum Likelihood Decoding using GRAND”, IEEE International Conference on Communications (ICC), 2020, DOI: 10.1109/ICC40277.2020.9149208. [cited by applicant]
Duffy et al., “Ordered Reliability Bits Guessing Random Additive Noise Decoding”, IEEE Transactions on Signal Processing, 2022, DOI: 10.1109/TSP.2022.3203251. [cited by applicant]
Abbas et al., “Hardware Architecture for Guessing Random Additive Noise Decoding Markov Order (GRAND-MO)”, Journal of Signal Processing Systems, 2022, DOI: 10.1007/s11265-022-01775-2. [cited by applicant]
Abbas et al., “GRAND for Rayleigh Fading Channels”, IEEE Globecom Workshops (2022), DOI: 10.1109/GCWkshps56602.2022. 10008698. [cited by applicant]
Sarieddeen et al., “GRAND for Fading Channels using Pseudo-soft Information”, IEEE Global Communications Conference, 2022, DOI: 10.1109/GLOBECOM48099.2022.10001707. [cited by applicant]
Abbas et al., “High-Throughput VLSI Architecture for GRAND”, IEEE Workshop on Signal Processing Systems (SiPS), 2020, DOI: 10.1109/SiPS50750.2020.9195254. [cited by applicant]
Abbas et al., “High-Throughput and Energy-Efficient VLSI Architecture for Ordered Reliability Bits GRAND”, IEEE Transactions on Very Large Scale Integration (VLSI) Systems, 2022, DOI: 10.1109/TVLSI.2022.3153605. [cited by applicant]
Abbas et al., “List-GRAND: A Practical Way to Achieve Maximum Likelihood Decoding”, EEE Transactions on Very Large Scale Integration (VLSI) Systems, 2023, DOI: 10.1109/TVLSI.2022.3223692. [cited by applicant]
Riaz et al., “A Universal Maximum Likelihood GRAND Decoder in 40nm CMOS”, 14th International Conference on Communication Systems & NETworks, 2022, DOI: 10.1109/COMSNETS53615.2022.9668514. [cited by applicant]
Condo, Carlo, “A Fixed Latency ORBGRAND Decoder Architecture With LUT-Aided Error-Pattern Scheduling”, IEEE Transactions on Circuits and Systems I: Regular Papers, 2022, DOI: 10.1109/TCSI.2022.3150583. [cited by applicant]
Kahraman et al., “Code based efficient maximum-likelihood decoding of short polar codes”, IEEE International Symposium on Information Theory Proceedings, 2012, DOI: 10.1109/ISIT.2012.6283643. [cited by applicant]
Guo et al., “Efficient sphere decoding of polar codes”, IEEE International Symposium on Information Theory (ISIT), 2015, DOI: 10.1109/ISIT.2015.7282452. [cited by applicant]
Husmann et al., “Reduced Latency ML Polar Decoding via Multiple Sphere-Decoding Tree Searches”, IEEE Transactions on Vehicular Technology, 2018, DOI: 10.1109/TVT.2017.2761262. [cited by applicant]
Zhou et al., “Efficient Sphere Polar Decoding via Synchronous Determination”, IEEE Transactions on Vehicular Technology, 2020, DOI: 10.1109/TVT.2020.2986915. [cited by applicant]
Trifonov, Peter, “Efficient Design and Decoding of Polar Codes”, IEEE Transactions on Communications, 2012, DOI: 10.1109/TCOMM.2012.081512.110872. [cited by applicant]
Li et al., “A RM-Polar Codes.” ArXiv abs/1407.5483 (2014). [cited by applicant]