Method and system for error correction in transmitting data using low complexity systematic encoder
View Patent ↗A systematic polar encoder with data checks includes a data mapper receiving input data containing information to be polar coded for transmission and generating modified data, and a nonsystematic polar encoder implementing a transform matrix encoding the modified data to produce a codeword x such that, for some sub-sequence of coordinates S, x S =d. For nonsystematic encoding, a transform input u includes first and second parts for words independent of the data, the second part for an inverse puncture word, a third part carrying the modified data, and a non-null part carrying a check word derived from the modified data. A transform output includes a punctured part for a puncture word, a part carrying the data, and a part serving as redundant symbols, with the codeword x related to the transform output by x=z Q where Q is the complement of the punctured part P.
1. A systematic polar encoder with data checks in a transmission system, comprising:
an input configured to receive an input data word d containing information to be transmitted;
an encoder circuit configured to produce a codeword x such that an encoding operation by the encoder circuit utilizes
a transform matrix G, and
a transform input u that includes
a part u F satisfying u F =b for a fixed word b that is independent of the data word d,
a part u T satisfying u T =t for an inverse puncture word t that is a fixed word independent of the data word d,
a part u I satisfying u I =d′ for a modified data word d′ that is derived from the data d, and
a part u C satisfying u C =f (d′) where f is a check generator function that operates on the modified data word d′ and generates a non-void check word, the transform input u having associated with it a transform output z,
wherein the transform output z is related to the transform input u by z=uG, the transform output z including
a punctured part z P satisfying z P =p for a puncture word p that is one of a void fixed word and a non-void fixed word,
a part z J satisfying z J =d, and
a part z R serving as redundant symbols,
wherein systematic encoding of the data word d is achieved by combining the part z J =d and the part z R of the transform output z in a predetermined order to form the codeword x; and
an output in the transmission system for transmission of the codeword x.
2. The systematic polar encoder with data checks according to claim 1 , wherein the encoding operation comprises forming a vector w with w T =t, w J =d and w R =e for some arbitrary word e, computing v=wG −1 , and obtaining the modified data word d′ by setting d′=v I .
3. The systematic polar encoder with data checks according to claim 1 , wherein the transform matrix G has a form A(F 1 ⊗G 1 )B T , wherein A is a permutation matrix, F 1 is a first kernel transform, G 1 is a first-tier transform, B is a permutation matrix, the first kernel transform F 1 has a size greater than one, the first-tier transform has a size smaller than a size of the transform G, and the computation of v is simplified by taking advantage of the special structure of G.
4. The systematic polar encoder with data checks according to claim 3 , wherein the first-tier transform G 1 is the Kronecker product of a plurality of kernel transforms: G 1 =F 2 ⊗ . . . ⊗F n , wherein each of the plurality of kernel transforms has a size greater than one.
5. The systematic polar encoder with data checks according to claim 4 , wherein F i =F 1 , for all 2≤i≤n.
6. The systematic polar encoder with data checks according to claim 5 , wherein
F
1
=
[
1
0
1
1
]
.
7. The systematic polar encoder with data checks according to claim 6 , wherein A or B is the identity matrix.
8. A systematic polar encoder with data checks in a transmission system, comprising:
a data mapper configured to receive an input data word d containing information to be polar coded for transmission and generate a modified data word d′;
a nonsystematic polar encoder configured to receive the modified data word d′ and generate a transform output z for a codeword x, the nonsystematic polar encoder implementing a transform matrix G that encodes the modified data word d′ to produce the transform output z for the codeword x such that, for some sub-sequence of coordinates S, x S =d,
wherein the transform matrix G is constrained by an input partition (F, C, I, T), where |C|>0, and an output partition (P, J, R) so that G I,P =0, G C,P =0, G F,P =0, and G T,P is invertible; and
a transceiver in the transmission system configured to transmit the codeword x.
9. The systematic polar encoder with data checks according to claim 8 , further comprising:
a polar transform configured to implement a transform matrix G to produce a transform output z,
wherein the systematic polar encoder is configured to determine the codeword x at least in part from the transform output z of the transform matrix G, wherein the transform output z comprises
a punctured part z P satisfying z P =p for a puncture word p, the puncture word p being independent of the data word d and one of a void fixed word and a non-void fixed word,
a part z J serving to carry data corresponding to the input data word d, and
a part z R serving as redundant symbols to protect the carried data, the part z J and the part z R combined in a predetermined order to form the codeword x.
10. The systematic polar encoder with data checks according to claim 9 , wherein a transform input u for the transform matrix G, related to the transform output z by u=zG −1 , has a part u F satisfying u F =b for a frozen word b that is a fixed word independent of the data word d, a part u C comprising a data check c comprising an output of a check generator function f operating on the modified data word d′ and having at least one element that depends on the modified data word d′, a part u I comprising the modified data word d′, and a part U T satisfying u T =p(G T,P ) −1 .
11. The systematic polar encoder with data checks according to claim 10 , wherein the transform matrix G, the input partition (F, C, I, T), and the output partition (P, J, R) are selected such that the check generator function f is an affine function.
12. The systematic polar encoder with data checks according to claim 10 , wherein the transform matrix G, the input partition (F, C, I, T), and the output partition (P, J, R) are selected such that G I,J is invertible, G C,J =0, and G F,J =0.
13. The systematic polar encoder with data checks according to claim 12 , wherein the generator matrix G has a form A(F 1 ⊗G 1 )B T , wherein A is a permutation matrix, F 1 is a first kernel transform, G 1 is a first-tier transform, B is a permutation matrix, the first kernel transform F 1 has a size greater than one, the first-tier transform has a size smaller than a size of the transform G, and the computation of the transform output z is simplified by taking advantage of the special structure of G.
14. The systematic polar encoder with data checks according to claim 13 , wherein the first-tier transform G 1 is the Kronecker product of a plurality of kernel transforms: G 1 =F 2 ⊗ . . . ⊗F n , wherein each of the plurality of kernel transforms has a size greater than one.
15. The systematic polar encoder with data checks according to claim 14 , wherein F i =F 1 , for all 2≤i≤n.
16. The systematic polar encoder with data checks according to claim 15 , wherein
F
1
=
[
1
0
1
1
]
.
17. The systematic polar encoder with data checks according to claim 16 , wherein A or B is the identity matrix.
18. A method for systematic polar encoding with data checks in a transmission system, comprising:
receiving an input data word d containing information to be polar coded for transmission at a data mapper;
generating a modified data word d′ using the data mapper;
receiving the modified data word d′ at a nonsystematic polar encoder;
generating, using the nonsystematic polar encoder, a transform output z for a codeword x by a transform matrix G that encodes the modified data word d′ to produce the transform output z for the codeword x such that, for some sub-sequence of coordinates S, x S =d, wherein the transform matrix G is constrained by an input partition (F, C, I, T), where |C|>0, and an output partition (P, J, R) so that G I,P =0, G C,P =0, G F,P =0, and G T,P is invertible; and
transmitting the codeword x using a transceiver in the transmission system.
19. The method according to claim 18 , further comprising:
employing a polar transform implementing the transform matrix G to produce a transform output z,
wherein the codeword x is determined at least in part from the transform output z, wherein the transform output z comprises
a punctured part z P satisfying z P =p for a puncture word p, the puncture word p being independent of the data word d and one of a void fixed word and a non-void fixed word,
a part z J serving to carry data corresponding to the input data word d, and
a part z R serving as redundant symbols to protect the carried data, the part z J and the part z R combined in a predetermined order to form the codeword x.
20. The method according to claim 19 , wherein a transform input u for the transform matrix G, related to the transform output z by u=zG −1 , has a part u F satisfying u F =b for a frozen word b that is a fixed word independent of the data word d, a part u C comprising a data check c comprising an output of a check generator function f operating on the modified data word d′, and having at least one element that depends on the modified data word d′, a part u I comprising the modified data word d′, and a part u T satisfying u T =p(G T,P ).
21. The method according to claim 20 , wherein the transform matrix G, the input partition (F, C, I, T), and the output partition (P, J, R) are selected such that the check generator function f is an affine function.
22. The method according to claim 20 , wherein the transform matrix G, the input partition (F, C, I, T), and the output partition (P, J, R) are selected such that G I,J is invertible, G C,J =0, and G F,J =0.
23. The method according to claim 22 , wherein the transform matrix G has a form A(F 1 ⊗G 1 )B T , wherein A is a permutation matrix, F 1 is a first kernel transform, G 1 is a first-tier transform, B is a permutation matrix, the first kernel transform F 1 has a size greater than one, the first-tier transform has a size smaller than a size of the transform G, and the computation of the transform output z is simplified by taking advantage of the special structure of G.
24. The method according to claim 23 , wherein the first-tier transform G 1 is the Kronecker product of a plurality of kernel transforms: G 1 =F 2 ⊗ . . . ⊗F n , wherein each of the plurality of kernel transforms has a size greater than one.
25. The method according to claim 24 , wherein F 1 =F 1 , for all 2≤i≤n.
26. The method according to claim 25 , wherein
F
1
=
[
1
0
1
1
]
.
27. The method according to claim 26 , wherein A or B is the identity matrix.