Apparatus and method for random linear code encoding and guessing random additive noise decoding (GRAND)

1 . An apparatus, comprising:

at least one processor; and

a non-transitory computer-readable medium including computer-executable instructions that, when executed by the at least one processor, cause the apparatus to carry out a method including:

initializing a current vector as being an information word of size N; and

running T times, T being a predetermined integer greater than or equal to 1, a loop comprising:

generating a scrambled vector by interleaving values of the current vector;

grouping values of the scrambled vector into N/m input vectors of size m, where m≥2;

multiplying each of the input vectors by an encoding matrix of size m×m to obtain output vectors; and

setting the current vector with a concatenation of the output vectors; and

a transceiver configured to transmit a codeword through a communication channel, the codeword being a last current vector in the loop, wherein the codeword is a non-systematic random linear code codeword configured for decoding by a Guessing Random Additive Noise Decoder (GRAND).

2 . The apparatus according to claim 1 , wherein the method further includes:

receiving a message comprising K bits, with K<N; and

forming the information word by storing the K bits of the message in the information word according to an information set of size K, and padding the information word with N-K padding values.

3 . The apparatus according to claim 1 , wherein the encoding matrix is an invertible binary matrix.

4 . The apparatus according to claim 1 , wherein the encoding matrix is an involutive matrix.

5 . The apparatus according to claim 1 , wherein the encoding matrix is the following 2×2 polar kernel:

[

1

0

1

1

]

.

6 . The apparatus according to claim 5 , wherein the encoding matrix used at least in a first run of the loop and for multiplying at least one of the input vectors in the first run of the loop, is different than the encoding matrix used at least in a second run of the loop for multiplying at least one of the input vectors in the second run of the loop.

7 . The apparatus according to claim 1 , wherein the encoding matrix used, for at least at a first run of the loop, to multiply at least a first one of the input vectors, is different than the encoding matrix used for multiplying at least a second one of the input vectors in the first run of the loop.

8 . A method, comprising:

initializing a current vector as being an information word of size N; and

running T times, with T being predetermined and greater than or equal to 1, a loop comprising:

generating a scrambled vector by interleaving values of the current vector;

grouping values of the scrambled vector into N/m input vectors of size m, with m≥2;

multiplying each of the input vectors by an encoding matrix of size m×m to obtain output vectors; and

setting the current vector with a concatenation of the output vectors; and

transmitting a codeword through a communication channel, the codeword being a last current vector in the loop, wherein the codeword is a non-systematic random linear code codeword configured for decoding by a Guessing Random Additive Noise Decoder (GRAND).

9 . The method according to claim 8 , further comprising:

receiving a message comprising K bits, with K<N; and

forming the information word by storing the K bits of the message in the information word according to an information set of size K, and padding the information word with N-K padding values.

10 . The method according to claim 9 , wherein the encoding matrix is an invertible binary matrix.

11 . The method according to claim 8 , wherein the encoding matrix is an involutive matrix.

12 . The method according to claim 11 , wherein the encoding matrix is the following 2×2 polar kernel:

[

1

0

1

1

]

.

13 . The method according to claim 8 , wherein the encoding matrix used at least in a first run of the loop to multiply at least one of the input vectors in the first run of the loop, is different than the encoding matrix used at least in a second run of the loop to multiply at least one of the input vectors of the second run of the loop.

14 . The method according to claim 8 , wherein for at least at a first run of the loop, the encoding matrix used to multiply at least a first one of the input vectors is different than the encoding matrix used to multiply at least a second one of the input vectors in the first run of the loop.

15 . An apparatus, comprising:

at least one processor; and

one or more memories coupled to the at least one processor, wherein the one or more memories store programming instructions for execution by the at least one processor to perform operations comprising:

receiving a symbol vector through a communication channel, the symbol vector corresponding to a transmitted non-systematic random linear code codeword;

extracting a hard decision vector from the symbol vector, to initialize an error vector;

running a decoding loop comprising:

generating a candidate codeword by adding the error vector to the hard decision vector;

initializing a current codeword as being the candidate codeword; and

running T times, with T being predetermined and greater or equal to 1, a backward encoding loop comprising:

grouping values of the current codeword into N/m input vectors of size m, with m≥2 and m divides N;

multiplying each of the input vectors by a decoding matrix of size m×m to obtain output vectors, and concatenating the output vectors to obtain concatenated output vectors;

generating a scrambled vector by interleaving the values of the concatenated output vectors; and

setting the current codeword as being the scrambled vector; and

checking entries in the last current codeword in the backward encoding loop outside of an information set;

in response to at least one of the entries in the last current codeword not being zero, changing the error vector and starting running further the decoding loop with the changed error vector; and

in response to all of the entries in the last current codeword being zero, stopping the decoding loop and setting the last current codeword in the backward encoding loop as a decoded codeword, the decoded codeword being of size N associated with the information set of size K, K<N, wherein the decoding loop implements Guessing Random Additive Noise Decoding (GRAND).

16 . The apparatus according to claim 15 , wherein the decoding matrix is an invertible binary matrix.

17 . The apparatus according to claim 15 , wherein the decoding matrix is an involutive matrix.

18 . The apparatus according to claim 15 , wherein the decoding matrix is an inverse of the following 2×2 polar kernel:

[

1

0

1

1

]

.

19 . The apparatus according to claim 15 , wherein the decoding matrix used, at least in a first run of the backward encoding loop of at least one of the runs of the decoding loop, for multiplying at least one of the input vectors in the first run of the backward encoding loop, is different than the decoding matrix used at least in a second run of the backward encoding loop of said at least one of the runs of the decoding loop, for multiplying at least one of the input vectors in the second run of the backward encoding loop.

20 . The apparatus according to claim 15 , wherein the decoding matrix used, for at least at a first run of the backward encoding loop of at least one of the runs of the decoding loop, to multiply a first one of the input vectors in the first run of the backward encoding loop, is different than the decoding matrix used for multiplying at least a second one of the input vectors in the first run of the backward encoding loop.