LPWAN COMMUNICATION PROTOCOL DESIGN WITH TURBO CODES

0Associated
Cases 
0Associated
Defendants 
0Accused
Products 
0Forward
Citations 
0
Petitions 
0
Assignments
First Claim
1. A method for receiving a message encoded in Turbo Codes and modulated for transmission as an analog signal, comprising:
 demodulating the analog signal to recover the Turbo Codes; and
decoding the Turbo Codes to recover the message using an iterative Turbo Code decoder, wherein the decoding performs an error detection after a predetermined number of iterations of the Turbo Code decoder to determine whether or not an error has occurred during the transmission.
0 Assignments
0 Petitions
Accused Products
Abstract
A method and a decoder for receiving a message encoded in Turbo Codes and modulated for transmission as an analog signal includes: (a) demodulating the analog signal to recover the Turbo Codes; and (b) decoding the Turbo Codes to recover the message using an iterative Turbo Code decoder, wherein the decoding includes performing an error detection after a predetermined number of iterations of the Turbo Code decoder to determine whether or not an error has occurred during the transmission. The predetermined number of iterations may be, for example, two. Depending on the result of the error detection, the decoding may stop, a request for retransmission of the message may be sent, or further iterations of decoding in the Turbo Code decoder may be carried out.
0 Citations
No References
No References
30 Claims
 1. A method for receiving a message encoded in Turbo Codes and modulated for transmission as an analog signal, comprising:
demodulating the analog signal to recover the Turbo Codes; and decoding the Turbo Codes to recover the message using an iterative Turbo Code decoder, wherein the decoding performs an error detection after a predetermined number of iterations of the Turbo Code decoder to determine whether or not an error has occurred during the transmission.  View Dependent Claims (2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15)
 16. A decoder for receiving a message encoded in Turbo Codes and modulated for transmission as an analog signal, comprising:
a demodulator that demodulates the analog signal to recover the Turbo Codes; and an iterative Turbo Code decoder that decodes the Turbo Codes to recover the message, wherein the decoding includes performing an error detection after a predetermined number of iterations of the Turbo Code decoder to determine whether or not an error has occurred during the transmission.  View Dependent Claims (17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30)
1 Specification
The present application claims priority of U.S. provisional application Ser. No. 62/749,793, filed on Oct. 23, 2018, entitled “LPWAN Communication Protocol Design With Turbo Codes.”
The present invention relates to communication protocols. In particular, the present invention relates to communication protocols that are suitable for use in wireless communication applications, such as LowPower WideArea Networks (LPWANs).
At step 107, the receiver demodulates the signal received from the communication channel to recover the encoded signal, which is then decoded at step 108 to recover binary data 109. An error that occurs along the signal path represented by steps 102107 may cause binary data 109 and binary data 101 to be different.
In communication model 100, noise in the communication channel between transmission at step 106 and reception at step 107 may be modeled by a Gaussian noise model (“Gaussian channel”). In some instances, modulation step 105 and demodulation step 107 may be lumped for the purpose of analysis into the communication channel (“binary channel”).
In this detailed description, embodiments of the present invention are described using a CDMA modulation scheme, which may be characterized by the carrier frequency f_{0 }and the number of chips (i.e., bits) N in the code assigned to a signal source. The noise in the Gaussian channel under a CDMA modulation scheme may be characterized by a signaltonoise ratio (SNR) defined as:
where ϕ represents a modulation schemeindependent noise measured expressed in dB Hz. The Gaussian channel has a channel capacity C_{g }defined as:
where C_{s }(N, ϕ) is defined as:
For a sufficiently small
Similarly, the binary channel has a capacity C_{B }defined as:
where C_{b }(N, ϕ) is the greatest coding rate achieved in an optimal coding scheme, defined as:
C_{b}=1+p logp+(1−p)log(1−p),
where p is the probability that a bit in a transmitted code word is flipped, given by:
The information transmit rate and the decoding energy are two figures of merit that are often used in the analysis of a communication channel It is desirable to have a high information transmit rate, while keeping the decoding energy low.
Suppose an encoded message frame of length K, resulting from encoding rK bits of information (r being the “information rate,” typically less than 1.0) is provided for transmission. The additional bits under the encoding scheme enable error detection, error correction, or both. Suppose further that the message frame is transmitted using a CDMA modulation scheme with a channel coding rate η (i.e., the Kbit message frame is encoded into a K/ηbit blocks for transmission), and the communication channel has an error rate P_{er }per block, the effective information rate R is given by:
The decoding energy per information bit is given by:
for small P_{er}, where E_{0 }(η) is the computational energy per input bit.
The “Turbo code” encoding scheme is illustrated by Turbo Code encoder 200 of
Delay line 202 delays sequence {d_{k}} by 5 bits, so that both RSC encoders 201a and 201b operate on the same set of input bits. Interleaver 203 permutates the delayed sequence at RSC encoder 201b before coding. Permutating the input sequence provides higher performance in the presence of burst noise in the communication channel. In this example, the coding rate is nominally ⅓, as the nominal coding rate is
where n is the number of RSC codes. In some embodiments, a predetermined number of bits may be removed (“punctured”) from subsequences Y_{1k }and Y_{2k}, so as to achieve a higher coding rate. In some embodiments, additional RSC encoders may be provided for greater noise immunity. Turbo Codes have been shown to achieve a channel capacity that is closest to the theoretical Shannon limit.
Using the BJCR algorithm, known to those of ordinary skill in the art, one of the probabilities p(d_{k}=1) and p(d_{k}=0) increases while the other decreases with the number of iterations. The number of iterations necessary to achieve a given error bit rate can be determined empirically for a communication channel. After the requisite number of iterations, the sign of Λ(d_{k}) can be used to determine if the decoded bit is ‘1’ (positive A(d_{k)) or ‘}0’ (negative Λ(d_{k})).
While the complexity of Turbo Code encoding grows linearly with both the coding rate and the number of unit delay elements in the RSC code encoder, the complexity of Turbo Code decoding grows exponentially with the number of unit delay elements in the RSC code encoder. For this reason, in practical applications, the number of unit delay elements in the RSC code encoder seldom exceeds 4. Furthermore, for many applications, it is not uncommon to find that the number of required decoding iterations exceeds 10 to achieve an acceptable bit error rate, resulting in a long decoding latency. Therefore, it is long desired to provide an encoding and decoding scheme that achieves the nearShannon capacity of Turbo codes, while having a shorter decoding latency.
According to one embodiment of the present invention, a decoder and a method for receiving a message encoded in Turbo Codes and modulated for transmission as an analog signal are provided. The method includes: (a) demodulating the analog signal to recover the Turbo Codes; and (b) decoding the Turbo Codes to recover the message using an iterative Turbo Code decoder, wherein the decoding includes performing an error detection after a predetermined number of iterations of the Turbo Code decoder to determine whether or not an error has occurred during the transmission. The predetermined number of iterations may be, for example, two. When the error detection determines that an error has likely not occurred during the transmission, the decoding may stop. Such an error detection may include, for example, (i) computing the RSC codes from the decoded message portion of the Turbo Codes, and (ii) evaluating the computed RSC codes against the decoded RSC codes portion. When the error detection determines that an error has occurred during the transmission, a request for retransmission of the message may be sent or, alternatively, one or more further iterations of decoding in the Turbo Code decoder may be carried out.
According to one embodiment of the present invention, the error detection step may include evaluating an indicator which provides a probability that an error has occurred during the transmission. The analog signal may be transmitted at one of a plurality of analog values (e.g., 1.0 and −1.0). The error detection may involve evaluating a probability P (Y_{i}X_{i}X_{i}), which is the probability of receiving, for the ith bit of a Turbo Code block an analog value Y_{i}, given a transmitted analog signal X_{i}. In one implementation using a binary modulation scheme, in which the values X_{i }and
where L is a length in number of bits of the Turbo Code block.
Alternatively, or in addition to evaluating the indicator, the Turbo Code block encodes an error detection code word (e.g., a cyclic redundancy check (CRC) code word), which is recovered by Turbo Code decoding. After a predetermined number of iterations, the data portion of the decoded Turbo Codes is decoded by an appropriate error detection code decoder (e.g., a CRC decoder). Successful decoding by the error detection code decoder provides an error detection.
The present invention is better understood upon consideration of the detailed description below in conjunction with the accompanying drawings.
Certain encoding scheme, such as Turbo Codes, do not have an error detection capability. The present invention provides an error detection ability to a Turbo Codebased communication scheme.
According to one embodiment of the present invention, one may design an indicator that, when evaluated from the received modulated signal, can be used to determine to some level of confidence that a transmitted signal is correctly received. For example, suppose an analog value Y_{i }is received from modulated analog value X_{i }(which may be either −1.0 or +1.0, inclusive) for the ith bit of a transmitted message block. The modulation may be, for example, a CDMA in conjunction with a phase shift key modulation scheme. For a Gaussian channel, the probability received signal Y_{i }deviates from the mean of the transmitted value X_{i}, P(Y_{i}X_{i}X_{i}), has a Gaussian distribution, which can be empirically obtained. Furthermore, for binary values transmitted over a Gaussian channel, the probability that the ith bit of a message block of length L has the received value X_{i}, as a result of the value being transmitted as X_{i }is given by:
for i=1, 2, . . . L. This probability for each bit is independent from the same probability for any of the other bits in the message block, although they have the same probability distribution. This probability may be interpreted to represent the probability that the ith bit of the message block, having value X_{i}, is corrected received. Because of their independence, the log probability that all bits of the message block are correctly received is related to:
For a sufficient long message block (e.g., L≥40), this log probability may be estimated by variable S with a Gaussian distribution:
For a given message block, the amount the value of variable S relative to its mean indicates the probability that one or more bits are incorrectly received. Thus, variable S may be used as an indicator that can serve as error detection.
In one embodiment of the present invention, in which the Turbo Code encoding scheme of
The indicator threshold thus should be selected to simultaneously contain both false positives (i.e., accepting as incorrect value as correct) or false negative (i.e., rejecting a correct value as incorrect).
When a block is rejected as incorrectly received based on the indicator, a decoder may send a resend request. Alternatively, if the communication protocol sends an acknowledgement for an accepted block, an unacknowledged block is automatically resent after a predetermined time period has elapsed.
According to one embodiment of the present invention and as illustrated in
g(x)=x^{10}+x^{9}+x^{5}+x^{4}+x+1
In fact, by combining error detection using the indicator with error detection using CRC codes, as taught above, a bit error rate of 9.0035×10^{−9 }is achieved after one Turbo Code decoding iteration.
As one can see from the above, by augmenting Turbo Codes with an error detection capability, the number of iterations necessarily for decoding Turbo Codes can be significantly reduced, thereby shortening decoding latency by sixfolds or more in many practical applications.
The above detailed description is provided to illustrate the specific embodiments of the present invention and is not intended to be limiting. Numerous modification and variations of the present invention is possible within the scope of the present invention. The present invention is set forth in the following claims.