Method and apparatus for fast decoding of polar codes
View Patent ↗The present method relates to a method by which a device receives a signal in a communication system, and an apparatus therefor, and to a method by which a reception device processes a signal in a communication system, and an apparatus therefor, the method comprising the steps of: receiving an encoded bit sequence; and decoding the encoded bit sequence in the direction from a root node to the lowest node on the basis of a binary tree structure, wherein, in the decoding step, decoding for a child node is skipped on the basis that a syndrome of a parent node satisfies a predetermined condition, and decoding for the child node is performed on the basis that the syndrome of the parent node does not satisfy the predetermined condition.
1 . A method by a receiving device comprising:
receiving a downlink channel,
wherein the downlink channel includes a bit sequence encoded based on a channel coding and interleaving;
performing decoding the bit sequence, and
obtaining a transport block based on the bit sequence that has been decoded,
wherein the channel coding is a polar coding,
wherein the decoding of the bit sequence includes performing error detection on the bit sequence through a cyclic redundancy check (CRC) related to the bit sequence,
wherein, based on the channel coding being the polar coding, the decoding of the bit sequence is performed in a direction from a highest node to a lowest node based on a binary tree structure,
wherein based on a syndrome of a parent node satisfying a predetermined condition, decoding of a child node is omitted in the decoding, and
wherein based on the syndrome of the parent node not satisfying the predetermined condition, the child node is decoded.
2 . The method of claim 1 , wherein the predetermined condition includes that the syndrome of the parent node is all zeros.
3 . The method of claim 2 , wherein the syndrome of the parent node is determined based on a following equation:
σ
=
α
^
F
⊗
n
V
T
,
where σ represents the syndrome, {circumflex over (α)} represents a soft decision result, F ⊗n represents a polar code matrix with a dimension of N*N, V represents a constraint matrix satisfying Z*V T =0, and Z represents a pre-coding matrix with a dimension of k*N.
4 . The method of claim 3 , wherein V has a following structure:
V
=
[
V
1
0
V
3
V
2
]
,
where V1 is a constraint matrix with a dimension of nm*N/2, each of V2 and V3 is a constraint matrix with a dimension of n f2 *N/2, and n fi represents a sum of frozen and parity lengths of child node i.
5 . The method of claim 4 , wherein a syndrome of child node i is determined based on a following equation:
σ
1
=
α
^
1
F
⊗
n
-
1
V
1
T
σ
2
=
α
^
2
F
⊗
n
-
1
V
2
T
⊕
β
1
F
⊗
n
-
1
V
3
T
,
where i is 0 or 1, σ i is the syndrome of child node i, F ⊗n−1 is a polar code matrix with a dimension of N/2*N/2, and β1 is a bit decision value of child node 1.
6 . A receiving device used in a communication system, the receiving device comprising:
at least one radio frequency (RF) unit;
at least one processor; and
at least one non-transitory computer memory operably connected to the at least one processor and including instructions that, when executed, cause the at least one processor to perform operations comprising:
receiving a downlink channel,
wherein the downlink channel includes a bit sequence encoded based on a channel coding and interleaving;
performing decoding the encoded bit sequence, and
obtaining a transport block based on the bit sequence that has been decoded,
wherein the channel coding is a polar coding,
wherein the decoding of the bit sequence includes performing error detection on the bit sequence through a cyclic redundancy check (CRC) related to the bit sequence,
wherein, based on the channel coding being the polar coding, the decoding of the bit sequence is performed in a direction from a highest node to a lowest node based on a binary tree structure,
wherein based on a syndrome of a parent node satisfying a predetermined condition, decoding of a child node is omitted in the decoding, and
wherein based on the syndrome of the parent node not satisfying the predetermined condition, the child node is decoded.
7 . The receiving device of claim 6 , wherein the predetermined condition includes that the syndrome of the parent node is all zeros.
8 . The receiving device of claim 7 , wherein the syndrome of the parent node is determined based on a following equation:
σ
=
α
^
F
⊗
n
V
T
,
where σ represents the syndrome, {circumflex over (α)} represents a soft decision result, F ⊗n represents a polar code matrix with a dimension of N*N, V represents a constraint matrix satisfying Z*V T =0, and Z represents a pre-coding matrix with a dimension of k*N.
9 . The receiving device of claim 8 , wherein V has a following structure:
V
=
[
V
1
0
V
3
V
2
]
,
where V1 is a constraint matrix with a dimension of n f1 *N/2, each of V2 and V3 is a constraint matrix with a dimension of n f2 *N/2, and n fi represents a sum of frozen and parity lengths of child node i.
10 . The receiving device of claim 9 , wherein a syndrome of child node i is determined based on a following equation:
σ
1
=
α
^
1
F
⊗
n
-
1
V
1
T
σ
2
=
α
^
2
F
⊗
n
-
1
V
2
T
⊕
β
1
F
⊗
n
-
1
V
3
T
,
where i is 0 or 1, σ i is the syndrome of child node i, F ⊗n−1 is a polar code matrix with a dimension of N/2*N/2, and β1 is a bit decision value of child node 1.
11 . A non-transitory computer-readable storage medium comprising at least one computer program that, when executed, causes at least one processor to perform operations comprising:
receiving a downlink channel,
wherein the downlink channel includes a bit sequence encoded based on a channel coding and interleaving;
performing decoding the bit sequence, and
obtaining a transport block based on the bit sequence that has been decoded,
wherein the channel coding is a polar coding,
wherein the decoding of the bit sequence includes performing error detection on the bit sequence through a cyclic redundancy check (CRC) related to the bit sequence,
wherein, based on the channel coding being the polar coding, the decoding of the bit sequence is performed in a direction,
wherein based on a syndrome of a parent node satisfying a predetermined condition, decoding of a child node is omitted in the decoding, and
wherein based on the syndrome of the parent node not satisfying the predetermined condition, the child node is decoded.
12 . The computer-readable storage medium of claim 11 , wherein the predetermined condition includes that the syndrome of the parent node is all zeros.
13 . The computer-readable storage medium of claim 12 , wherein the syndrome of the parent node is determined based on a following equation:
σ
=
α
^
F
⊗
n
V
T
,
where σ represents the syndrome, {circumflex over (α)} represents a soft decision result, F ⊗n represents a polar code matrix with a dimension of N*N, V represents a constraint matrix satisfying Z*V T =0, and Z represents a pre-coding matrix with a dimension of k*N.
14 . The computer-readable storage medium of claim 13 , wherein V has a following structure:
V
=
[
V
1
0
V
3
V
2
]
,
where V1 is a constraint matrix with a dimension of n f1 *N/2, each of V2 and V3 is a constraint matrix with a dimension of n f2 *N/2, and n fi represents a sum of frozen and parity lengths of child node i.
15 . The computer-readable storage medium of claim 14 , wherein a syndrome of child node i is determined based on a following equation:
σ
1
=
α
^
1
F
⊗
n
-
1
V
1
T
σ
2
=
α
^
2
F
⊗
n
-
1
V
2
T
⊕
β
1
F
⊗
n
-
1
V
3
T
,
where i is 0 or 1, σ i is the syndrome of child node i, F ⊗n−1 is a polar code matrix with a dimension of N/2*N/2, and β1 is a bit decision value of child node 1.