Search

US-20260127069-A1 - DECODING DEVICE AND METHOD FOR PERFORMING MOST RELIABLE BASIS-LIKE DECODING

US20260127069A1US 20260127069 A1US20260127069 A1US 20260127069A1US-20260127069-A1

Abstract

A decoding device for performing most reliable basis-like (MRB-like) decoding of a code having length N and dimension K and method are provided. The decoding device is configured to receive a sequence of one or more channel observations. Then, the decoding device orders one or more reliability values in a decreasing order, each reliability value corresponding to the channel observations of the received sequence. The decoding device determines an MRB-like basis of the code based on the ordered reliability values. The MRB-like basis is defined by K independent positions that are obtained from the ordering. The decoding device further constructs a generator matrix from an ordering determined by the MRB-like basis using Gaussian elimination performed on a submatrix of a first matrix. The first matrix is derived from a reduced echelon form generator matrix of the code. Then, the decoding device performs decoding based on the constructed generator matrix.

Inventors

  • Marc Fossorier

Assignees

  • HUAWEI TECHNOLOGIES CO., LTD.

Dates

Publication Date
20260507
Application Date
20260106

Claims (20)

  1. 1 . A decoding device ( 100 ) for performing most reliable basis-like, MRB-like, decoding of a code having length N and dimension K, the decoding device ( 100 ) being configured to: receive a sequence y ( 101 ) of one or more channel observations; order one or more reliability values ( 102 ) in a decreasing order, each reliability value ( 102 ) corresponding to the channel observations of the received sequence y ( 101 ); determine a MRB-like basis ( 103 ) of the code based on the ordered reliability values ( 102 ), wherein the MRB-like basis ( 103 ) is defined by K independent positions that are obtained from the ordering; construct a generator matrix ( 105 ) from an ordering determined by the MRB-like basis ( 103 ) using Gaussian elimination, GE, performed on a submatrix of a first matrix ( 104 ), the first matrix ( 104 ) being derived from a reduced echelon form generator matrix of the code; and perform decoding ( 106 ) based on the constructed generator matrix ( 105 ).
  2. 2 . The decoding device ( 100 ) according to claim 1 , wherein the submatrix defines at most K information positions of the code.
  3. 3 . The decoding device ( 100 ) according to claim 1 , wherein determining the MRB-like basis ( 103 ) of the code based on the ordered reliability values ( 102 ) comprises: defining a first permutation function λ 1 as the ordered reliability values ( 102 ); constructing the first matrix G 1 ( 104 ) based on the ordered reliability values ( 102 ) and based on a generator matrix of the code.
  4. 4 . The decoding device ( 100 ) according to claim 3 , wherein constructing the first matrix G 1 ( 104 ) based on the ordered reliability values ( 102 ) and based on the generator matrix of the code comprises: obtaining the first matrix G 1 ( 104 ) by applying the first permutation function λ 1 to a matrix G REF as λ 1 (G REF ), wherein the matrix G REF is the reduced echelon form generator matrix of the code, and wherein K columns of G REF are related to information positions of the code and one or more N−K columns of G REF are related to parity positions of the code; and performing one or more permutations in the first matrix G 1 ( 104 ), comprising: performing one or more column permutations to bring |B K,MR | columns of the first matrix G 1 ( 104 ) to first |B K,MR | positions, and performing one or more row permutations to form an identity matrix in the first |B K,MR | positions, wherein |B K,MR | is a cardinality of a set of indices B K,MR , the set of indices B K,MR comprising a set of indices of the information positions in G REF that belongs to a set of the K most reliable positions; and performing one or more column permutations to bring |B K,LR | columns of the first matrix G 1 ( 104 ) to bring first |B K,LR | positions in last N−K positions, and performing one or more row permutations to form an identity matrix in the first |B K,LR | positions, wherein |B K,LR | is a cardinality of a set of indices B K,LR , the set of indices B K,LR being a set of indices of the information positions in G REF that belongs to a set of the N−K least reliable positions.
  5. 5 . The decoding device ( 100 ) according to claim 1 , wherein constructing the generator matrix ( 105 ) from the ordering determined by the MRB-like basis ( 103 ) using GE performed on the submatrix of the first matrix ( 104 ) comprises: obtaining a second matrix G 1 2 by performing GE of the first matrix G 1 ( 104 ); defining a second permutation function λ 2 by performing one or more column permutations on the second matrix G 1 2 to bring |B K,LR | columns of G 1 2 to first |B K,LR | positions, and performing one or more row permutations on G 1 2 to form an identity matrix in the first |B K,LR | positions; and constructing the generator matrix ( 105 ) as the permuted second matrix G 1 2 .
  6. 6 . The decoding device ( 100 ) according to claim 1 , wherein the first submatrix comprises a K×(|B K,LR |+N−K) submatrix ( 304 ) of the first matrix G 1 ( 104 ) and the constructed generator matrix ( 105 ) is a matrix G 2 ( 205 ); or wherein the first submatrix comprises a |B K,LR |×(|B K,LR |+N−K) submatrix ( 504 ) of the first matrix G 1 ( 104 ) and the constructed generator matrix is a matrix G 2 ′ ( 405 ).
  7. 7 . The decoding device ( 100 ) according to claim 1 , wherein performing decoding ( 106 ) based on the constructed generator matrix ( 105 ) comprises: constructing one or more error vectors; determining one or more codewords based on the constructed generator matrix ( 105 ) and based on the one or more error vectors; and estimating a message based on the determined one or more codewords and based on a decision rule.
  8. 8 . The decoding device ( 100 ) according to claim 7 , wherein constructing the one or more error vectors comprises: determining an ordered received sequence of channel observations y ′ = ( y 0 ′ , y 1 ′ , ... , y N - 1 ′ ) corresponding to the generator matrix of the code G 2 ′ ( 405 ), wherein y i ′ with i=0, 1, . . . , N−1 denotes an i-th element of the ordered sequence y′; determining a hard decision decoding z ′ = ( z 0 ′ , z 1 ′ , ... , z N - 1 ′ ) corresponding to the ordered received sequence y′, wherein z i ′ with i=0, 1, . . . , N−1 denotes an i-th element of the hard decision decoding z′; creating a list of candidates of a transmitted message comprising one or more elements j, wherein each element j is obtained by adding a respective error vector e j ′ = ( e j , 0 ′ , e j , 1 ′ , ... , e j , K - 1 ′ ) to a vector z K ′ = ( z 0 ′ , z 1 ′ , ... , z K - 1 ′ ) , wherein ⁢ e j , i ′ with i=0, 1, . . . , K−1 denotes an i-th element of a respective j-th error vector e j ′ .
  9. 9 . The decoding device ( 100 ) according to claim 7 , wherein each error vector is constructed based on a corresponding decreasing likelihood; or wherein each error vector is constructed in a deterministic order within one or more families of increasing Hamming weight.
  10. 10 . The decoding device ( 100 ) according to claim 7 , wherein determining the one or more codewords based on the constructed generator matrix ( 405 ) and based on the one or more error patterns comprises: determining an order-zero codeword c 0 ′ for the vector z K ′ = ( z 0 ′ , z 1 ′ , ... , z K - 1 ′ ) based on the constructed generator matrix G 2 ′ ( 405 ); and determining a codeword c j ′ for each of a respective j-th error vector e j ′ in the list , based on the calculated order-zero codeword c 0 ′ and based on the constructed generator matrix G 2 ′ .
  11. 11 . The decoding device ( 100 ) according to claim 10 , wherein determining the order-zero codeword c 0 ′ for the vector z K ′ = ( z 0 ′ , z 1 ′ , ... , z K - 1 ′ ) based on the constructed generator matrix G 2 ′ ( 405 ) comprises: decomposing z K ′ based on G 2 ′ ( 405 ) as z K ′ = ( z K , MR ′ ⁢ z K , LR ′ ) , with z K , MR ′ = ( z 0 ′ , z 1 ′ , … , z ❘ "\[LeftBracketingBar]" B K , MR ❘ "\[RightBracketingBar]" - 1 ′ ) ⁢ and z K , LR ′ = ( z | B K , MR | ′ , z | B K , MR | + 1 ′ , … , z K - 1 ′ ) ; and calculating the order-zero codeword as c 0 ′ = c MR ′ + c LR ′ ; wherein c M ⁢ R ′ is determined based on a product of z K , MR ′ and |B K,MR | rows of G 2 ′ ( 405 ); and wherein c LR ′ is determined based on a product of z K , LR ′ and the remaining |B K,LR | rows of G 2 ′ .
  12. 12 . The decoding device ( 100 ) according to claim 10 , wherein determining the codeword c j ′ , for each of the respective j-th error vector e j ′ in the list based on the calculated order-zero codeword c 0 ′ and based on the calculated generator matrix G 2 ′ ( 405 ) comprises: decomposing the j-th error vector e j ′ in the list based on G 2 ′ ( 405 ) as e j ′ = ( e j , K , MR ′ e j , K , LR ′ ) with e j , K , MR ′ = ( e j , 0 ′ , e j , 1 ′ , ... , e j , ❘ "\[LeftBracketingBar]" B K , MR ❘ "\[RightBracketingBar]" - 1 ′ ) ⁢ and ⁢ e j , K , LR ′ = ( e j , ❘ "\[LeftBracketingBar]" B K , MR ❘ "\[RightBracketingBar]" ′ , e j , ❘ "\[LeftBracketingBar]" B K , MR ❘ "\[RightBracketingBar]" + 1 ′ , ... , e j , K - 1 ′ ) ; calculating the respective codeword c j ′ for the j-th error vector e j ′ as c j ′ = c 0 ′ + e j , MR ′ + e j , LR ′ ; wherein e j , MR ′ is determined based on a product of e j , K , MR ′ and |B K,MR | rows of G 2 ′ ( 405 ); and wherein e j , LR ′ is determined based on a product of e j , K , LR ′ and the remaining |B K,LR | rows of G 2 ′ ( 405 ).
  13. 13 . The decoding device ( 100 ) according to claim 7 , wherein estimating the message based on the determined one or more codewords comprises: choosing a j-th candidate message in the list having a maximum likelihood decision, the maximum likelihood decision being defined as j = argmax ⁢ P ⁡ ( c j ′ | y ) , wherein P ⁡ ( c j ′ | y ) denotes a probability of transmitting the codeword c j ′ given the received sequence y ( 101 ).
  14. 14 . The decoding device ( 100 ) according to claim 1 , wherein the constructed generator matrix ( 105 ) comprises a parity matrix ( 805 ) in a dual space of the code.
  15. 15 . A method ( 1000 ) for performing most reliable basis-like, MRB-like, decoding of a code having length N and dimension K, the method ( 1000 ) comprising: receiving ( 1001 ) a sequence y ( 101 ) of one or more channel observations; ordering ( 1002 ) one or more reliability values ( 102 ) in a decreasing order, each reliability value ( 102 ) corresponding to one of the channel observations of the received sequence y ( 101 ); determining ( 1003 ) a MRB-like basis ( 103 ) of the code based on the ordered reliability values ( 102 ), wherein the MRB-like basis ( 103 ) is defined by K independent positions that are obtained from the ordering; constructing ( 1004 ) a generator matrix ( 105 ) from an ordering determined by the MRB-like basis ( 103 ) using Gaussian elimination, GE, performed on a submatrix of a first matrix ( 104 ), the first matrix ( 104 ) being derived from a reduced echelon form generator matrix of the code; and performing ( 1005 ) decoding based on the constructed generator matrix.
  16. 16 . The method ( 1000 ) according to claim 15 , wherein the submatrix defines at most K information positions of the code.
  17. 17 . The method ( 1000 ) according to claim 15 , wherein determining the MRB-like basis ( 103 ) of the code based on the ordered reliability values ( 102 ) comprises: defining a first permutation function λ 1 as the ordered reliability values ( 102 ); constructing the first matrix G 1 ( 104 ) based on the ordered reliability values ( 102 ) and based on a generator matrix of the code.
  18. 18 . The method ( 1000 ) according to claim 17 , wherein constructing the first matrix G 1 ( 104 ) based on the ordered reliability values ( 102 ) and based on the generator matrix of the code comprises: obtaining the first matrix G 1 ( 104 ) by applying the first permutation function λ 1 to a matrix G REF as λ 1 (G REF ), wherein the matrix G REF is the reduced echelon form generator matrix of the code, and wherein K columns of G REF are related to information positions of the code and one or more N−K columns of G REF are related to parity positions of the code; and performing one or more permutations in the first matrix G 1 ( 104 ), comprising: performing one or more column permutations to bring |B K,MR | columns of the first matrix G 1 ( 104 ) to first |B K,MR | positions, and performing one or more row permutations to form an identity matrix in the first |B K,MR | positions, wherein |B K,MR | is a cardinality of a set of indices B K,MR , the set of indices B K,MR comprising a set of indices of the information positions in G REF that belongs to a set of the K most reliable positions; and performing one or more column permutations to bring |B K,LR | columns of the first matrix G 1 ( 104 ) to bring first |B K,LR | positions in last N−K positions, and performing one or more row permutations to form an identity matrix in the first |B K,LR | positions, wherein |B K,LR | is a cardinality of a set of indices B K,LR , the set of indices B K,LR being a set of indices of the information positions in G REF that belongs to a set of the N−K least reliable positions.
  19. 19 . The method ( 1000 ) according to claim 15 , wherein constructing the generator matrix ( 105 ) from the ordering determined by the MRB-like basis ( 103 ) using GE performed on the submatrix of the first matrix ( 104 ) comprises: defining a second matrix G 1 2 by performing GE on a submatrix of the first matrix G 1 ( 104 ); defining a second permutation function λ 2 by performing one or more column permutations on the second matrix G 1 2 to bring |B K,LR | columns of G 1 2 to first |B K,LR | positions, and performing one or more row permutations on G 1 2 to form an identity matrix in the first |B K,LR | positions; and constructing the generator matrix ( 105 ) as the permuted second matrix G 1 2 .
  20. 20 . A computer program product comprising a program code for carrying out, when implemented on a processor, the method ( 1000 ) for performing most reliable basis-like, MRB-like, decoding of a code having length N and dimension K according to the following is performed: receive a sequence y ( 101 ) of one or more channel observations; order one or more reliability values ( 102 ) in a decreasing order, each reliability value ( 102 ) corresponding to the channel observations of the received sequence y ( 101 ); determine a MRB-like basis ( 103 ) of the code based on the ordered reliability values ( 102 ), wherein the MRB-like basis ( 103 ) is defined by K independent positions that are obtained from the ordering; construct a generator matrix ( 105 ) from an ordering determined by the MRB-like basis ( 103 ) using Gaussian elimination, GE, performed on a submatrix of a first matrix ( 104 ), the first matrix ( 104 ) being derived from a reduced echelon form generator matrix of the code; and perform decoding ( 106 ) based on the constructed generator matrix ( 105 ).

Description

CROSS-REFERENCE TO RELATED APPLICATIONS This application is a continuation of International Application No. PCT/EP2023/068895, filed on Jul. 7, 2023, the disclosure of which is hereby incorporated by reference in its entirety. TECHNICAL FIELD The present disclosure relates to a decoding device for performing most reliable basis-like (MRB-like) decoding. The disclosure further provides a method for performing MRB-like decoding and a computer program product to perform the method. BACKGROUND Some conventional decoders of linear block codes depend on the particular code considered and become code dedicated, while others are universal and can be applied to a large class of codes. Current universal decoders are developed in conjunction with the most reliable basis (MRB) that is defined as the set of the most reliable independent positions (MRIPs) thus forming an information set. The existing MRB-based universal decoders may have a large computational complexity, which limits the role of the universal decoders in the current standards. Moreover, current MRB-based universal decoders rely on Gaussian elimination (GE) to put the generator matrix of the code considered into systematic form with respect to the MRB for encoding the MRIPs. Such a GE operation adds a significant computational complexity to the decoder. For a (N, K) linear block code, the complexity of GE is O (N min {K, N−K}2). SUMMARY In view of the above, this disclosure aims to improve conventional MRB-based decoders. An objective is to provide a MRB-based universal decoder for all linear block codes that has a significantly lower computational complexity and that provides the same decoding performance. This and other objectives are achieved by the solutions of this disclosure as described in the independent claims. Advantageous implementations are further defined in the dependent claims. According to a first aspect, a decoding device for performing MRB-like decoding of a code having length N and dimension K is provided. The decoding device is configured to: receive a sequence y of one or more channel observations; order one or more reliability values in a decreasing order, each reliability value corresponding to the channel observations of the received sequence y; determine a MRB-like basis of the code based on the ordered reliability values, where the MRB-like basis is defined by K independent positions that are obtained from the ordering; construct a generator matrix from an ordering determined by the MRB-like basis using GE performed on a submatrix of a first matrix, the first matrix being derived from a reduced echelon form generator matrix of the code; and perform decoding based on the constructed generator matrix. The MRB-like basis may not be exactly the same as the MRB; however, a discrepancy between them is small. This enables to separate most of the information positions from the parity positions of the original representation of the code based on the ordering owing to the MRB-like basis. As a result, the original information positions in the MRB-like basis do not need to be considered by the GE, that is, a full GE may not be needed and only a restricted GE can be performed. The decoding process can be modified accordingly, if needed. This enables a significant reduction in the computational complexity. In this disclosure, restricted GE refers to performing GE only in matrix with a size smaller than the full size of a generator matrix of the code. In an implementation form of the first aspect the submatrix defines at most K information positions of the code. In an implementation form of the first aspect, determining the MRB-like basis of the code based on the ordered reliability values comprises: defining a first permutation function λ1 as the ordered reliability values; and constructing the first matrix G1 based on the ordered reliability values and based on a generator matrix of the code. In an implementation form of the first aspect, constructing the first matrix G1 based on the ordered reliability values and based on the generator matrix of the code comprises: obtaining the first matrix G1 by applying the first permutation function λ1 to a matrix GREF as λ1 (GREF), where the matrix GREF is the reduced echelon form generator matrix of the code, and where K columns of GREF are related to information positions of the code and one or more N−K columns of GREF are related to parity positions of the code; and performing one or more permutations in the first matrix G1. Performing one or more permutations in the first matrix G1 comprises performing one or more column permutations to bring |BK,MR| columns of the first matrix G1 to first |BK,MR| positions, and performing one or more row permutations to form an identity matrix in the first |BK,MR| positions, where |BK,MR| is a cardinality of a set of indices BK,MR, the set of indices BK,MR comprising a set of indices of the information positions in GREF that belongs to a set of the K most reliable