US2020007170A1PendingUtilityA1
System and method for early termination of decoding in a multi user equipment environment
Est. expiryJun 6, 2037(~10.9 yrs left)· nominal 20-yr term from priority
Inventors:Noam Presman
H03M 13/13H03M 13/2927H04L 1/0057H03M 13/3746H04L 1/0042H04L 1/0061H04L 1/0051H04L 1/0045H03M 13/31
48
PatentIndex Score
0
Cited by
0
References
0
Claims
Abstract
A device system and method is provided for early termination of a decoding process performed at a receiving user device. A user-specific message may be received, from a communication channel shared by multiple user devices. The user-specific message may include an error correction codeword generated by shifting an original codeword by an offset codeword uniquely associated with a target user device. The error correction codeword may be shifted based on an offset codeword uniquely associated with the receiving user device. The received message may begin to be decoded. If the receiving device is the target device, the offsets respectively associated therewith are equal and cancel, and the original message is decoded to completion. If, however, the receiving device is not the target device, the offsets respectively associated therewith are not equal and combine to form an above threshold decoding error and decoding is terminated before completion.
Claims
exact text as granted — not AI-modified1 . A method for encoding input information as a polar codeword, the method comprising:
constructing one or more values f (n) of a generating matrix G (n) for a polar codeword of length 2 n by:
in each of a plurality of recursive steps m=2, . . . , n compute the values f (m) of the generating matrix G (m) at a coordinate (i,j) as follows:
when the most significant bit (i m−1 , j m−1 ) of a binary representation of a row index i=[i 0 , i 1 , . . . , i m−1 ]∈{0,1} and a column index j=[j 0 , j 1 , . . . j m−1 ]∈{0,1} is (0,0), (1,0), or (1,1), the value f (m) at coordinate (i,j) in the generating matrix G (m) is the value f (m−1) of the generating matrix G (m−1) of the previous step at the next most significant bits ([i m−2 , . . . , i 0 ], [j n−m , . . . j 0 ]) of the binary representations of the row and column indices;
when the most significant bit (i m−1 , j m−1 ) of the binary representation of the row and column indices is (0,1), the value f (m) at coordinate (i,j) of the generating matrix G (m) is zero; and
multiplying the one or more values f (n) of the generating matrix G (n) by input information to generate bits of a polar codeword of length 2 n .
2 . The method of claim 1 comprising constructing each generating matrix G (m) of a subsequent step m as the product of the generating matrix G (m−1) of the previous step m−1 and the Kronecker power matrix
[
1
0
1
1
]
,
such that,
G
(
m
)
=
[
1
0
1
1
]
⊗
G
(
m
-
1
)
=
[
G
(
m
-
1
)
0
G
(
m
-
1
)
G
(
m
-
1
)
]
.
3 . The method of claim 1 comprising, when the most significant bit j m−1 of the binary representation of the column index is one, constructing the value f (m) at the coordinate (i,j) of the generating matrix G (m) to be the product of the most significant bit i m−1 of the binary representation of the row index i=[i 0 , i 1 , . . . i m−1 ]∈{0,1} and the value f (m−1) of the generating matrix G (m−1) of the previous step at the next most significant bits ([i m−2 , . . . , i 0 ], [j m−2 , . . . , j 0 ]) of the binary representation of the row and column indices.
4 . The method of claim 1 , wherein multiplying the one or more values f (n) by the input information comprises executing a plurality of respective combinational circuits operating in parallel, wherein executing each sequential circuit (q) comprises:
computing the values f (n) of the (qth) column of the generating matrix G (n) ; and multiplying the (qth) column of values f (n) by a row vector of the input information to generate the (qth) value of the polar codeword.
5 . The method of claim 1 comprising skipping computing and multiplying for frozen bits of the polar codeword or for non-frozen bits that are zero.
6 . The method of claim 1 , wherein the input information is user-generated information and identification information uniquely associated with a target user device in a multi-user communication system.
7 . The method of claim 1 comprising:
shifting the polar codeword generated based on the user-generated information by the polar codeword generated based on the identification information; and
transmitting the shifted polar codeword over a communication channel shared by multiple user devices.
8 . The method of claim 1 , wherein the input information is identification information uniquely associated with a receiving user device in the multi-user communication system.
9 . The method of claim 1 comprising:
receiving, from a communication channel shared by multiple user devices, a user-specific message comprising a polar codeword generated by shifting the original polar codeword of length 2 n by an offset polar codeword of identification information uniquely associated with a target user device in a multi-user communication system;
shifting the received polar codeword based on an offset polar codeword of identification information uniquely associated with the receiving user device; and
decoding the received message, wherein:
if the receiving device is the target device, the offset polar codewords respectively associated therewith are equal and cancel, and the decoding the original polar codeword of user-generated information proceeds to completion, and
if the receiving device is not the target device, the offset polar codewords respectively associated therewith are not equal and combine to form an above threshold decoding error and the decoding terminates before completion.
10 . A system for encoding input information as a polar codeword, the system comprising:
one or more processors configured to:
construct one or more values f (n) of a generating matrix G (n) for a polar codeword of length 2 n , wherein in each of a plurality of recursive steps m=2, . . . , n, the processors are configured to compute the values f (m) of the generating matrix G (m) at a coordinate (i,j) as follows:
when the most significant bit (i m−1 , j m−1 ) of a binary representation of a row index i=[i 0 , i 1 , . . . i m−1 ]∈{0,1} and a column index j=[j 0 , j 1 , . . . j m−1 ]∈{0,1} is (0,0), (1,0), or (1,1), the value f (m) at coordinate (i,j) in the generating matrix G (m) is the value f (m−1) of the generating matrix G (m−1) of the previous step at the next most significant bits ([i m−2 , . . . , i 0 ], [j n−m , . . . , j 0 ]) of the binary representations of the row and column indices;
when the most significant bit (i m−1 , j m−1 ) of the binary representation of the row and column indices is (0,1), the value f (m) at coordinate (i,j) of the generating matrix G (m) is zero; and
multiply the one or more values f (n) of the generating matrix G (n) by input information to generate bits of a polar codeword of length 2 n .
11 . The system of claim 10 , wherein the one or more processors are further configured to construct each generating matrix G (m) of a subsequent step m as the product of the generating matrix G (m−1) of the previous step m−1 and the Kronecker power matrix
[
1
0
1
1
]
,
such that,
G
(
m
)
=
[
1
0
1
1
]
⊗
G
(
m
-
1
)
=
[
G
(
m
-
1
)
0
G
(
m
-
1
)
G
(
m
-
1
)
]
.
12 . The system of claim 10 , wherein the one or more processors are further configured to, when the most significant bit j m−1 of the binary representation of the column index is one, construct the value f (m) at the coordinate (i,j) of the generating matrix G (m) to be the product of the most significant bit i m−1 of the binary representation of the row index i=[i 0 , i 1 , . . . i m−1 ]∈{0,1} and the value f (m−1) of the generating matrix G (m−1) of the previous step at the next most significant bits ([i m−2 , . . . , i 0 ], [j m−2 , . . . , j 0 ]) of the binary representation of the row and column indices.
13 . The system of claim 10 , wherein the one or more processors are further configured to multiply the one or more values f (n) by the input information by executing a plurality of respective combinational circuits operating in parallel, wherein executing each sequential circuit (q) comprises:
computing the values f (n) of the (qth) column of the generating matrix G (n) ; and multiplying the (qth) column of values f (n) by a row vector of the input information to generate the (qth) value of the polar codeword.
14 . The system of claim 10 , wherein the one or more processors are further configured to skip computing and multiplying for frozen bits of the polar codeword or for non-frozen bits that are zero.
15 . The system of claim 10 , wherein the input information is user-generated information and identification information uniquely associated with a target user device in a multi-user communication system.
16 . The system of claim 10 , wherein the one or more processors are further configured to:
shift the polar codeword generated based on the user-generated information by the polar codeword generated based on the identification information; and transmit the shifted polar codeword over a communication channel shared by multiple user devices.
17 . The system of claim 10 , wherein the input information is identification information uniquely associated with a receiving user device in the multi-user communication system.
18 . The system of claim 10 , wherein the one or more processors are further configured to:
receive, from a communication channel shared by multiple user devices, a user-specific message comprising a polar codeword generated by shifting the original polar codeword of length 2 n by an offset polar codeword of identification information uniquely associated with a target user device in a multi-user communication system; shift the received polar codeword based on an offset polar codeword of identification information uniquely associated with the receiving user device; and decode the received message, wherein:
if the receiving device is the target device, the offset polar codewords respectively associated therewith are equal and cancel, and the processors decode the original polar codeword of user-generated information proceeds to completion, and
if the receiving device is not the target device, the offset polar codewords respectively associated therewith are not equal and combine to form an above threshold decoding error and the processor terminates decoding before completion.Cited by (0)
No later patents cite this yet.
References (0)
No backward citations on record.