LPWAN COMMUNICATION PROTOCOL DESIGN WITH TURBO CODES

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.

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.

2. The method of claim 1, wherein the predetermined number of iterations is one.

3. The method of claim 1, wherein decoding stops when the error detection determines that an error has not occurred during the transmission.

4. The method of claim 1, wherein a request for retransmission of the message is sent when the error detection determines that an error has occurred during the transmission.

5. The method of claim 4, wherein a further iteration of decoding is carried out in the Turbo Code decoder when the error detection determines that an error has occurred during the transmission.

6. The method of claim 1, wherein the error detection step comprises evaluating an indicator having a value that is related to a probability that an error has occurred during the transmission.

7. The method of claim 6, wherein the analog signal is transmitted at one of a plurality of analog values, and wherein the probability is based on the received analog signal's deviation from the transmitted analog signal.

8. The method of claim 7, wherein the probability relates to P(Y.sub.i-X.sub.i|X.sub.i), where X.sub.i and Y.sub.i represent an analog value of the transmitted analog signal and a value of the received analog value, respectively.

9. The method of claim 8, wherein evaluating the indicator is includes computing: $\underset{i=1}{\overset{L}{.Math.}}.Math.\log .Math..Math.\frac{P\left(Y_i-X_i|X_i\right)}{P\left(Y_i-X_i|X_i\right)+P\left(Y_i-\stackrel{\_}{X_i}|\stackrel{\_}{X_i}\right)}$ where L is a length in number of bits of the Turbo Codes and X.sub.i is an analog value representing a complement of X.sub.i.

10. The method of claim 8, wherein the recovered message is used in a Turbo Code encoder to regenerate a regenerated Turbo Code word, and wherein the probability is computed based on the regenerated Turbo Codes.

11. The method of claim 6, wherein the message comprises an error detection code, and wherein the error detection comprises recovering the error detection code.

12. The method of claim 1, wherein the message includes an error detection code, and wherein the error detection comprises decoding the error detection code.

13. The method of claim 12, wherein the error detection comprises determining that a decoding of the error detection code is successful.

14. The method of claim 12, wherein the error detection code is based on cyclic redundancy check.

15. The method of claim 14, wherein the cyclic redundancy check is based on a generator polynomial given by:
g(x)=x.sup.10+x.sup.9+x.sup.5+x.sup.4+x+1

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.

17. The decoder of claim 16, wherein the predetermined number of iterations is one.

18. The decoder of claim 16, wherein decoding stops when the error detection determines that an error has not occurred during the transmission.

19. The decoder of claim 16, wherein a request for retransmission of the message is sent when the error detection determines that an error has occurred during the transmission.

20. The decoder of claim 19, wherein a further iteration of decoding is carried out in the Turbo Code decoder when the error detection determines that an error has occurred during the transmission.

21. The decoder of claim 16, wherein the error detection comprises evaluating an indicator having a value that is related to a probability that an error has occurred during the transmission.

22. The decoder of claim 21, wherein the analog signal is transmitted at one of a plurality of analog values, and wherein the probability is based on the received analog signal's deviation from the transmitted analog signal.

23. The decoder of claim 22, wherein the probability relates to P(Y.sub.i-X.sub.i|X.sub.i), where X.sub.i and Y.sub.i represent an analog value of the transmitted analog signal and a value of the received analog value, respectively.

24. The decoder of claim 23, wherein evaluating the indicator is includes computing: $\underset{i=1}{\overset{L}{.Math.}}.Math.\log .Math..Math.\frac{P\left(Y_i-X_i|X_i\right)}{P\left(Y_i-X_i|X_i\right)+P\left(Y_i-\stackrel{\_}{X_i}|\stackrel{\_}{X_i}\right)}$ where L is a length in number of bits of the Turbo Codes and X.sub.i is an analog value representing a complement of X.sub.i.

25. The decoder of claim 23, wherein the recovered message is used in a Turbo Code encoder to regenerate a regenerated Turbo Code word, and wherein the probability is computed based on the regenerated Turbo Codes.

26. The decoder of claim 21, wherein the message comprises an error detection code, and wherein the error detection comprises recovering the error detection code.

27. The decoder of claim 16, wherein the message includes an error detection code, and wherein the error detection comprises decoding the error detection code.

28. The decoder of claim 27, wherein the error detection comprises determining that a decoding of the error detection code is successful.

29. The decoder of claim 27, wherein the error detection code is based on cyclic redundancy check.

30. The decoder of claim 29, wherein the cyclic redundancy check is based on a generator polynomial given by:
g(x)=x.sup.10+x.sup.9+x.sup.5+x.sup.4+x+1

Description

BRIEF DESCRIPTION OF THE DRAWINGS

[0019] FIG. 1 shows model 100 of a communication system.

[0020] FIG. 2a shows schematically exemplary Turbo Code encoder 200.

[0021] FIG. 2b shows schematically exemplary Turbo Code decoder 250.

[0022] FIG. 3 shows the probability densities of bit errors per block for erroneous blocks after one iteration of Turbo Code decoding, in the results of a simulation of a Gaussian channel using 210.sup.7 blocks of Turbo Codes, with each block having a 110-bit message frame (i.e., not including the RSC codes), at a coding rate of and a signal-to-noise ratio of 30 dB Hz.

[0023] FIG. 4 shows the distributions of indicator values in decoded blocks without a flipped bit and in blocks found with one or more bits flipped, obtained based on the simulation of FIG. 3.

[0024] FIG. 5 shows probability density functions of a false negative determination (labeled 501) and of a false positive determination (labeled 502) for over the range of indicator threshold.

[0025] FIG. 6 shows a communication protocol that embeds an error detection capability in a transmitted message, while using a near-Shannon capacity Turbo Code encoding scheme, in accordance with one embodiment of the present invention.

[0026] FIG. 7 shows in table form the simulation results of communication using a Turbo Codes encoding scheme, with error detection by CRC included, over a Gaussian channel.

DETAILED DESCRIPTION OF THE PREFERRED EMBODIMENTS

[0027] 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 Code-based communication scheme.

[0028] 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.sub.i is received from modulated analog value X.sub.i (which may be either 1.0 or +1.0, inclusive) for the i-th 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.sub.i deviates from the mean of the transmitted value X.sub.i, P(Y.sub.i-X.sub.i|X.sub.i), has a Gaussian distribution, which can be empirically obtained. Furthermore, for binary values transmitted over a Gaussian channel, the probability that the i-th bit of a message block of length L has the received value X.sub.i, as a result of the value being transmitted as X.sub.i is given by:

[00013]$\frac{P\left(Y_i-X_i|X_i\right)}{P\left(Y_i-X_i|X_i\right)+P\left(Y_i-\stackrel{\_}{X_i}|\stackrel{\_}{X_i}\right)},$

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 i-th bit of the message block, having value X.sub.i, is corrected received. Because of their independence, the log probability that all bits of the message block are correctly received is related to:

[00014]$\underset{i=1}{\overset{L}{.Math.}}.Math.\log .Math..Math.\frac{P\left(Y_i-X_i|X_i\right)}{P\left(Y_i-X_i|X_i\right)+P\left(Y_i-\stackrel{\_}{X_i}|\stackrel{\_}{X_i}\right)}$

[0029] For a sufficient long message block (e.g., L40), this log probability may be estimated by variable S with a Gaussian distribution:

[00015]$S=\frac{-1}{L}.Math.\underset{i=1}{\overset{L}{.Math.}}.Math.\log .Math..Math.\frac{P\left(Y_i-X_i|X_i\right)}{P\left(Y_i-X_i|X_i\right)+P\left(Y_i-\stackrel{\_}{X_i}|\stackrel{\_}{X_i}\right)}$

[0030] 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.

[0031] In one embodiment of the present invention, in which the Turbo Code encoding scheme of FIG. 2a is used, the sequence of received analog values {Y.sub.i}, i=1, 2, . . . L, are digitized to the sequence of binary values {{tilde over (X)}.sub..Math.}. Sequence {{tilde over (X)}.sub..Math.} is then provided to a Turbo Code decoder for decoding over a predetermined number of iterations (e.g., 1) to obtain decoded binary sequence {}, in which is the data portion of the Turbo Codes and are the RSC codes. The binary data sequence {} is then provided to a Turbo Code encoder to replicate the Turbo Coding that occurred on the transmitter side prior to transmission. The Turbo Code encoder provides the sequence {{circumflex over (X)}.sub..Math.}, which is {}, where are the computed RSC codes. {{circumflex over (X)}.sub..Math.} is then used to compute variable S and its deviation from the mean value S provides an indication that the sequence {{circumflex over (X)}.sub..Math.} is a correctly received message block.

[0032] FIG. 3 shows the probability densities of bit errors per block in blocks with one or more errors found after one iteration of Turbo Code decoding in the results of a simulation of a Gaussian channel using 210.sup.7 blocks of Turbo Codes, with each block having a 110-bit message frame (i.e., not including the RSC codes), at a coding rate of and a signal-to-noise ratio of 30 dB Hz. The simulation assumes a 888-chip CDMA code and a carrier frequency at 10.sup.8. FIG. 4 shows the distributions of indicator values in decoded blocks without a flipped bit and in blocks found with one or more bits flipped, obtained based on the simulation of FIG. 3. In FIG. 4, the distribution of indicator values in blocks without a bit flipped is labeled 401 and the distribution of indicator values in blocks with one or more flipped bits is labeled 402. According to one embodiment of the present invention, a threshold value of the indicator may be selected to decide whether a Turbo Code decoded value should be accepted as correct (positive) or not (negative), after a predetermined number of decoding iterations (e.g., one iteration). For example, based on the FIG. 5, one may select a value between 0.5 and 1.0, above which the Turbo Code decoding is accepted as incorrect and below which the Turbo Code decoding is accepted as correct.

[0033] 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). FIG. 5 shows probability density functions of a false negative determination (labeled 501) and of a false positive determination (labeled 502) for over the range of indicator threshold. Using the data in FIG. 6, for example, if one selects an indicator threshold of 0.533, the probability of a false negative determination for a given block is less than 1%, while the probability of a false positive determination is 1.637%.

[0034] 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.

[0035] According to one embodiment of the present invention and as illustrated in FIG. 6, prior to a block of data is encoded into Turbo Codes, the data may first be encoded using a cyclic redundancy check (CRC) encoding scheme (step 601). The CRC-encoded data is then additionally encoded into Turbo Codes (step 602). The Turbo Codes are then modulated and transmitted over the communication channel (step 603). The received signal is first demodulated (steep 604) and decoded in a Turbo Code decoder (step 605). Each iteration of the Turbo Code decoder yields a CRC-encoded data portion and the RSC codes. The CRC-encoded data portion may then be provided to a CRC decoder to recover the original data block (step 606). If the CRC-encoded data portion is successfully decoded, one may conclude that no further Turbo Code decoding iteration is required. However, if the CRC-decoding is not successful, one may conclude that an error may have occurred during transmission or that further iterations of the Turbo Code decoding may be required. At that point, one option may be to request a retransmit from the transmitting side, or to carry out one or more iterations of Turbo Code decoding to see the resulting CRC-encoded data portion can be successfully CRC-decoded.

[0036] FIG. 7 shows in table form the simulation results of communication using a Turbo Codes encoding scheme, with error detection by CRC included, over a Gaussian channel. As in the simulation of FIG. 3, the simulation in FIG. 7 uses 210.sup.7 blocks of Turbo Codes, with each block having 110 bits compose of a 100-bit message frame and CRC parity bits, encoded at a coding rate of and a signal-to-noise ratio of 30 dB Hz. In this instance, the CRC-encoding has a generator polynomial given by:

g(x)=x.sup.10+x.sup.9+x.sup.5+x.sup.4+x+1

[0037] FIG. 7 lists in row order (i) the number of errors in the 210.sup.7 blocks of Turbo Codes, (ii) the corresponding bit error rate, (iii) the number of errors detected by CRC decoding, and (iv) the error rate achieved by accepting a successful CRC-decoding, after each of Turbo Code decoding iterations 1-18 As shown in FIG. 7, 34035 blocks are shown to contain error bits after one iteration of Turbo Code decoding, thereby achieving a bit error rate of 1.7017510.sup.3 bit error rate. However, 34024 of these errors are uncovered by CRC decoding after one iteration of Turbo Code decoding. Thus, the simulation in FIG. 7 shows that embedding the error detection capability of a CRC in Turbo Codes achieves in the example a bit error rate of 5.510.sup.7 after just one iteration of Turbo Code decoding. FIG. 7 shows that, if error detection by CRC is not used, the equivalent error rate is not achieve until after 10 iterations of Turbo Code decoding. Thus, embedding CRC error detection in Turbo Codes saves in this instance at least 9 iterations of Turbo Code decoding.

[0038] In fact, by combining error detection using the indicator with error detection using CRC codes, as taught above, a bit error rate of 9.003510.sup.9 is achieved after one Turbo Code decoding iteration.

[0039] 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 six-folds or more in many practical applications.

[0040] 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.