Universal guessing random additive noise decoding (GRAND) decoder

Patent metadata

Field	Value
Publication number	US-11870459-B2
Application number	US-202117225818-A
Country	US
Kind code	B2
Filing date	Apr 8, 2021
Priority date	Jun 8, 2020
Publication date	Jan 9, 2024
Grant date	Jan 9, 2024

Abstract

Described is a decoder suitable for use with any communication or storage system. The described decoder has a modular decoder hardware architecture capable of implementing a noise guessing process and due to its dependency only on noise, the decoder design is independent of any encoder, thus making it a universal decoder. Hence, the decoder architecture described herein is agnostic to any coding scheme.

First claim

What is claimed is:

1. A universal decoder comprising:
a syndrome calculator for checking membership of received data in a codebook; and
an error generator, coupled to the syndrome calculator, the error generator including a primary error generator and a secondary error generator coupled to the primary error generator, wherein in response to the syndrome calculator detecting an error, the syndrome calculator provides the error to the error generator and the error generator calculates rank-ordered binary symmetric channel noise patterns and checks for membership in the codebook, wherein data is pipelined such that processing of data in the syndrome calculator, primary error generator and secondary error generator result in out-of-order decoded codewords;
a re-ordering circuit configured to receive the out-of-order decoded codewords and configured to re-order the out-of-order decoded codewords; and
wherein the universal decoder utilizes noise statistics to optimize an energy per decoded bit by dynamic clock gating of the primary and secondary error generators based on a probability of error likelihood.

2. The universal decoder of claim 1 wherein the primary and secondary error generators are configured to check errors in parallel to reduce latency in processing codewords.

3. A universal decoder comprising:
a syndrome calculator for checking membership of received data in a codebook, and an error generator, coupled to the syndrome calculator, wherein in response to the syndrome calculator detecting an error, the syndrome calculator provides the error to the error generator and the error generator calculates rank-ordered binary symmetric channel noise patterns and checks for membership in the codebook, wherein the error generator comprises:
an error logic which generates (D 1 , D 2 ) distance pairs to indicate distances between active bits having a first logic value in a guessed noise sequence (E);
a pattern generator coupled to the error logic; and
an error shifter coupled to the error logic and the pattern generator wherein the error logic which generates (D 1 , D 2 ) distance pairs to indicate the distances between active bits having the first logic value in a guessed noise sequence (E) and the pattern generator constructs a bit sequence defined by (D 1 , D 2 ), which is then used as indices of one or more input-seed values having the first logic value for the error shifter and the error shifter creates in parallel variations of a sequence of input-seed values through cyclical shifts for the primary and secondary error generators such that the error generator creates ordered error sequences in parallel.

4. The universal decoder of claim 1 wherein the re-ordering circuit comprises a tag-based re-ordering circuit.

5. A universal decoder comprising:
means for receiving input codewords and H matrix values;
means for multiplexing H matrix values between parallel signal paths each leading to a pair of memories in which H matrix values are stored;
a syndrome calculator configured to receive input codewords and H matrix values;
an error generator, coupled to the syndrome calculator, wherein in response to the syndrome calculator detecting an error, the syndrome calculator provides the error to the error generator and the error generator calculates rank-ordered binary symmetric channel noise patterns and checks for membership in a codebook, wherein data is pipelined such that processing of data in the syndrome calculator and error generator result in out-of-order decoded codewords;
a re-ordering circuit configured to receive the out-of-order decoded codewords and configured to re-order the out-of-order decoded codewords; and
wherein the universal decoder utilizes noise statistics to optimize an energy per decoded bit by dynamic clock gating of the error generator based on a probability of error likelihood.

6. The universal decoder of claim 5 further comprising a pseudo-random number generator coupled to the means for multiplexing H matrix values and causing the means for multiplexing H matrix values to randomly select one of a plurality of H matrices.

7. The universal decoder of claim 5 further comprising a pseudo-random number generator coupled to the means for multiplexing H matrix values and causing the means for multiplexing H matrix values to randomly select one of a plurality of input codewords and one of a plurality of H matrices.

8. The universal decoder of claim 5 wherein the means for receiving input codewords and H matrix values directs a selected input codeword to a first input of a multiplier circuit.

9. The universal decoder of claim 8 further comprising means for providing H matrix values from a first one of the pair of memories to a second input of a multiplier circuit such that the multiplier circuit produces a product of the H matrix values and input codewords.

10. The universal decoder of claim 9 further comprising means for loading H-matrix values into a second one of the pair of memories concurrently with the first one of the pair of memories providing H-matrix values to the second input of the multiplier circuit.

11. The universal decoder of claim 9 further comprising means for loading H-matrix data in the pair of memories in an interleaved manner.

12. A universal decoder comprising:
means for receiving input codewords and H matrix values;
means for multiplexing H matrix values between parallel signal paths each leading to a pair of memories in which H matrix values are stored;
a syndrome calculator configured to receive input codewords and H matrix values;
an error generator, coupled to the syndrome calculator, wherein in response to the syndrome calculator detecting an error, the syndrome calculator provides the error to the error generator and the error generator calculates rank-ordered binary symmetric channel noise patterns and checks for membership in a codebook; and
means for re-randomizing codebooks in real time by concurrently decoding and changing H matrices stored in the pair of memories such that when an H-matrix in a first one of the pair of memories is ready to be used for a decoding operation, the H-matrix in a second one of the pair of memories is being changed.

13. The universal decoder of claim 5 wherein at least one of the syndrome calculator and the error generator comprise a sparse multiplier configured to receive H-matrix values (H) and error vector values (E) and produce a product value HE.

14. The universal decoder of claim 13 wherein the sparse multiplier comprises a memory having H-matrix values stored therein and wherein active bits of the error vector (E) having the first logic value are used to select column addresses for an H matrix and the selected H matrix columns are logically XORed to produce the product value HE.

Assignees

• Massachusetts Inst Technology
• Univ Boston
• Nat Univ Ireland Maynooth

Inventors

• Solomon Amit
• Medard Muriel
• Duffy Kenneth R
• Kirby Rabia Tugce Yazicigil
• Bansal Vaibhav
• An Wei

Classifications

• H04L1/0045

  Arrangements at the receiver end · CPC title

• H03M13/1105 Primary

  Decoding · CPC title

• H03M13/1148

  Structural properties of the code parity-check or generator matrix · CPC title

• H03M13/2778

  Interleaver using block-wise interleaving, e.g. the interleaving matrix is sub-divided into sub-matrices and the permutation is performed in blocks of sub-matrices · CPC title

• H03M13/6575

  Implementations based on combinatorial logic, e.g. Boolean circuits · CPC title