BACKGROUND OF THE INVENTION

1. Field of the Invention

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 Low-Power Wide-Area Networks (LPWANs).

2. Discussion of the Related Art

Figure 1 shows model 100 of a communication system. As shown in Figure 1, binary data 101 is encoded into a sequence of binary code words at step 102. Examples of encoding include error detecting codes, error correction codes and turbo codes. In the detailed description below, an encoding scheme that uses turbo codes, or any of several selected types of error detecting codes, illustrates the present invention. The encoded sequence of binary code words is modulated at step 103 onto a carrier signal for transmission at step 104. One example of a modulation scheme may be code division multi-access (CDMA), combined with either quadrature phase-shift keying (QPSK) modulation or binary phase-shift keying (BPSK) modulation. The modulated signal may be transmitted over a noisy communication channel and received at a receiver at step 106.

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 102-107 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 fo 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 signal-to-noise ratio (SNR) defined as: F_ N

SNR = lOio x—

fo where f represents a modulation scheme-independent noise measured expressed in dB Hz. The Gaussian channel has a channel capacity C _g defined as:

C _g = min C _S (N, f) where C _s (N,<j>) is defined as:

For a sufficiently small 10m c—

fo

Similarly, the binary channel has a capacity CB defined as: where C _b (N, f) is the greatest coding rate achieved in an optimal coding scheme, defined as:

C _b = 1 T p logp + (1 - p) log(l - p), where p is the probability that a bit in a transmitted code word is flipped, given by:

H ^{(1 erf} t¾

with

1 -f N_

= 10 ² ° ^X /o

L,/SNR

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 hits 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 h (i.e., the K- bit message frame is encoded into a K/h -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 ₀ ( ή) is the computational energy per input bit.

The“Turbo code” encoding scheme is illustrated by Turbo Code encoder 200 of Figure 2a. As shown in Figure 2a, Turbo Code encoder 200 receives an input sequence { d _k } to provide an output sequence {¾, Y _k }, where ¾ reproduces sequence {d _k } and Y _k is the concatenation of two subsequences, Y i _k and Y 2 _k . The output sequence is then transmitted. In Figure 2a, subsequences Yi _k and Y 2 _k are recursive systematic convolutions (RSC) codes. In the example of Figure 2a, RSC encoders 20la and 20lb each include 4 unit-delay shift registers and both implement the finite state machine:

1 + D ⁴ X

h(x ) =

1 + Dx + D ² x + D ³ x+D ⁴ x

Delay line 202 delays sequence {d _k } by 5 bits, so that both RSC encoders 20la and 20lb operate on the same set of input bits. Interleaver 203 permutates the delayed sequence at RSC encoder 20 lb 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

1

nominally 1/3, 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 Yi _k and Y 2 _k , 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.

Figure 2b shows schematically exemplary Turbo Code decoder 250 for decoding turbo codes that are generated from Turbo Code encoder 200. As shown in Figure 2b, Turbo Code decoder 250 includes two decoders 25 la and 25 lb, each of which may be a BCJR decoder, as known to those of ordinary skill in the art. Each decoder provides an output value A(dk), computed based on input bit Xk, yk, and A {dk), where xi_ and yk are corresponding received bits from transmitted sequence {¾, Y _k } and A (d ) is a previous computed output value from decoding the same X _k and y*. In Figure 2b, decoder 25 la operates on X _k and y _// . and the preceding output value of decoder 251b from the previous iteration, and decoder 25 lb operate on X _k and yii, and the output value of decoder 25 la in the current iteration. In the example of Figure 2b, A (d _k ) may be the log likelihood ratio:

p(< = i)

A(d _k ) = log

p(< = 0)

Using the BJCR algorithm, known to those of ordinary skill in the art, one of the probabilities p(d _fc = 1) and p(c/ _fe = 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 A(d _k ) can be used to determine if the decoded bit is‘1’ (positive A(d _k )) or Ό’ (negative A(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 near-Shannon capacity of Turbo codes, while having a shorter decoding latency.

SUMMARY OF THE INVENTION

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 — Xi \ X{), which is the probability of receiving, for the i-th bit of a Turbo Code block an analog value Y,, given a transmitted analog signal X,. In one implementation using a binary modulation scheme, in which the values ¾ and X _l are the analog representations of complementary binary values‘G and O’, one may calculate an indicator of error occurrence during transmission using the expression: 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.

BRIEF DESCRIPTION OF THE DRAWINGS

Figure 1 shows model 100 of a communication system.

Figure 2a shows schematically exemplary Turbo Code encoder 200.

Figure 2b shows schematically exemplary Turbo Code decoder 250.

Figure 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 2 x 10 ⁷ 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 1/3 and a signal-to-noise ratio of 30 dBHz.

Figure 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 Figure 3.

Figure 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. Figure 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.

Figure 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

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.

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, is received from modulated analog value X, (which may be either -1.0 or +1.0, inclusive) for the z-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, deviates from the mean of the transmitted value X, P(Yi— X _; | X _; ), has a Gaussian distribution, which can be empirically obtained. Furthermore, for binary values transmitted over a Gaussian channel, the probability that the z-th bit of a message block of length L has the received value Y,, as a result of the p(Y—X

value being transmitted as X„ is given by:— -—— ^{1 1} _ _ , for i=l, 2, L. This probability

P(Yi~Xi\ Xi)+P( Yi-Xi\ Xi)

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„ 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 Figure 2a is used, the sequence of received analog values {Yij, i = 1 , 2, ... L. are digitized to the sequence of binary values {XJ. Sequence jX is then provided to a Turbo Code decoder for decoding over a predetermined number of iterations (e.g., 1) to obtain decoded binary sequence {d- _k yi _k i _k ! i ⁿ which d _k is the data portion of the Turbo Codes and y± _k ,y2 _k ^arc the RSC codes. The binary data sequence { d _k } 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 { }, which is \ d _k , y^ _k , y^ _k } . where y^ _k , y^ _k are the computed RSC codes. { X _l } is then used to compute variable S and its deviation from the mean value S provides an indication that the sequence {X _t } is a correctly received message block.

Figure 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 2 x 10 ⁷ 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 1/3 and a signal-to-noise ratio of 30 dB Hz. The simulation assumes a 888-chip CDMA code and a carrier frequency at 10 ⁸ . Figure 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 Figure 3. In Figure 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 Figure 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.

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). Figure 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 Figure 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%.

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 Figure 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.

Figure 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 Figure 3, the simulation in Figure 7 uses 2 x 10 ⁷ 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 1/3 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 ¹⁰ + x ⁹ + x ⁵ + x ⁴ + x + 1

Figure 7 lists in row order (i) the number of errors in the 2 x 10 ⁷ 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 Figure 7, 34035 blocks are shown to contain error bits after one iteration of Turbo Code decoding, thereby achieving a bit error rate of 1.70175 x 10 ³ bit error rate. However, 34024 of these errors are uncovered by CRC decoding after one iteration of Turbo Code decoding. Thus, the simulation in Figure 7 shows that embedding the error detection capability of a CRC in Turbo Codes achieves in the example a bit error rate of 5.5 x 10 ⁷ after just one iteration of Turbo Code decoding. Figure 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.

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 x 10 ⁹ 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 six-folds 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.