Dr.MohitBansal Profile Pic
Published Date:25-10-2017
Your Website URL(Optional)
ARQ In closed-loop systems the usage of feedback channel allows the transmission characteristics to be improved. The idea of utilizing the feedback channel is that in case of receiving a very noisy message it is possible not to make a decision, but rather ask the transmitter to repeat the transmission. In the most general cases such organization of communication allows a decision concerning transmitted message to be made only under conditions of noise absence (or very low noise level), repeating the message when the noise level is high. Surely, usage of repeated transmission decreases the overall transmission rate. However, in most cases such rate decreasing is not significant. Communication systems utilizing the feedback channel are called systems with repeat request (ARQ, Automatic Repeat reQuest) or systems with feedback 10, 16, 18. 6.1 Basic ARQ Schemes 6.1.1 Basic Concepts Among the variety of algorithms for data transmission over the feedback channels the two basic classes of such systems may be distinguished: systems with decision feedback and systems with data feedback. In systems with decision feedback the decision of repeated message transmission is made by the receiving side of the system as the result of analyzing the received data. In systems with data feedback the decision is made by the transmitter based on the information transmitted over the feedback channel. Systems in which the decision of repeated transmission can be made both on receiving and transmitting sides are called combined or hybrid transmission systems with feedback. Consider the simplest model of the system with decision feedback, see Figure 6.1. Let the transmission be made using the linear (n, k)-code. The code is used in detection mode (this may be, for example, standard CRC code), that is, during the decoding process the belonging of the received word to the code is verified, and the repeat request is made when the received word does not belong to the code. In this case the transmission over the feedback channel consists of the repeat request signal (positive acknowledgment, ACK, or negative acknowledgment, NACK or NAK).Figure 6.1 Basic ARQ scheme Denote as P the probability that an error detected during the decoding process, let Q be the probability o of correct receive, and let P be the probability of erroneous decoding. Then it is clear that: 1 P + P + Q = 1 (6.1) o 1 Since in the system with feedback the number of symbols obtained by the receiver depends on the channel properties and is a random variable, we define the system transmission rate R as the ratio of mathematical expectation of the number of information symbols obtained by the receiver to the overall number of symbols sent to the forward communication channel. After obtaining every noncorrupted codeword of length n receiver obtained k information symbols, and in the case of receiving the word which does not belong to code, the receiver obtains no information, so the transmission rate is: k R = (1 − P ) (6.2) o n The probability of error P in such a system is the sum of probabilities that after decoding the user will e obtain the wrong codeword without repeat request, after one repeat, after second repeat and so on. This probability is: P 1 2 P = P + P · P + P · P +... = (6.3) e 1 1 0 1 0 1 − P 0 The described simplest model of the system with feedback shows the basic advantages of the feedback channel usage. Firstly, from (6.3) one can see that with the reasonable repeat request probability P  1, the error o probability is defined by the value of the non-detection probability P . Since the detection capability 1 of the code is much higher than the error-correcting capability, much shorter codes may be used in the system with feedback compared to systems without feedback. This in turn allows the complexity of communication system to be significantly decreased. Secondly, it follows from (6.2) that in the system with feedback the transmission rate is changing together with the change of the detection probability. This is not a special advantage in the channel withARQ 265 constant parameters, when the value of P is constant. However, in channels with variable parameters, o as is the case of all wireless channels, the mentioned above property of systems with feedback provides adaptation of communication systems to the communication channel. Considering the simplest model, we did not take into account many effects arising in real systems with feedback. In particular, we did not consider errors occurring in feedback channel. As a rule, there are much less information transmitted over the feedback channel, compared to the forward channel, thus the error probability in the feedback channel is usually much less. Nevertheless, errors in the feedback channel are possible, that is, the situations are possible when the positive acknowledgment (ACK) of successful transmission would be considered as repeat request (NAK) and vice versa. In this case some special errors specific for systems with feedback may occur: some transmissions may be sent twice, and some may be lost. To combat such deletions and insertions in the systems with feedback the special mechanisms are used. The problem of forward and feedback channels synchronization also requires investigation. After receiving the erroneous word, the repeat request signal is transmitted over the feedback channel. If the duration of transmission over the feedback channel is comparable to the duration of transmission over the forward channel, then before obtaining the repeated word the receiver may obtain one or more words following the requested. There are several synchronization strategies for forward and feedback channels. All the strategies of data transmission with repeat requests in the case of detecting the receive errors may be divided into three types:  Stop and Wait (SAW);  in case of error repeat last N packets (Go Back N,GBN);  Selective Repeat (SR). 6.1.2 Stop-and-Wait ARQ As has been noted, the implementation of the simplest system with repeat request involves some difficul- ties caused by message delay both in forward and feedback channels. During the period of transmission the repeat request signal over the feedback channel there may be some subsequent messages transmitted over the forward channel. The delivery of messages to the user in the initial order requires the buffering. Of course the buffer size must be big enough to allow the whole sequence of messages that came before the successful transmission of repeated message to be stored. At that, if several retransmissions are needed for successful receive, then the buffer size may become quite large. Equation (6.3) is correct for infinite buffer length. Stop and Wait (SW) method allows avoiding the buffering (or using a very small buffer size), see Figure 6.2. The idea of the method is that the transmitter is waiting for either positive acknowledgment or repeat request before starting the transmission of the next block. The complexity of Stop and Wait ARQ system implementation is minimal. The receiver should be able to detect errors, but it need not contain the buffer. If the transmitter has sent the packet, it is waiting for the receiver’s answer. If the receiver detects no errors, it sends positive acknowledgment (ACK), otherwise the negative acknowledgment (NAK) is sent. In case of ACK reception the transmitter flushes the buffer containing the last sent packet. Otherwise, in case of NAK reception, the transmitter repeats the transmission of the packet containing the buffer. Clearly, this strategy is not efficient, especially when the delay δ of forward and feedback channels RT is high. Here the delay of forward and feedback channels is the sum of all time period durations between transmission of the last symbol and receiver’s positive acknowledgment. Suppose that the packets of n bits, including k information bits, are transmitted with the physical rate V (bits/s), i.e. Vδ bits will be transmitted during time period nδ . Then by analogy with (6.2) the RT RT transmission rate for Stop and Wait systems will be: k n R = (1 − P ) · (6.4) SW o n n + Vδ RT266 Modulation and Coding Techniques in Wireless Communications Figure 6.2 Stop-and-Wait ARQ The value of rate R defined by (6.4) becomes lower than that provided by the expression in (6.3) with SW the increase of the delay in channels and the transmission physical rate. Since the delay of the forward and feedback channels and data transmission rate are usually determined by the channel, the transmission rate in (6.4) may be somewhat improved by means of increasing the packet length. However, this leads to increasing the value P , which limits the increasing of n. o Besides the low implementation complexity, the advantage of systems with waiting is low cost of service information which is needed for every transmission. There is no need for packets numbering, since the packets order is inherently preserved. Unfortunately, reliability of transmission of the one bit of acknowledgment is not as simple as it seems. Moreover, due to the protocol’s nature it is impossible to collect some determined number of acknowledgments. The effectiveness of systems with waiting may be significantly improved by means of organization of the system with separated virtual channels. Multichannel ARQ protocol with waiting. In multichannel ARQ with waiting (MC-SW-ARQ) N Stop and Wait systems are used, see Figure 6.3. Each system is functioning on its own virtual channel, which are independent from each other. For example, the channel separation by time, frequency or code is used. The packets in multichannel ARQ are uniformly distributed over N channels. If the number of channels is selected as:   V · δ RT (6.5) N ≥ k then during the repeat request period in each channel there will be no new messages. Thus, the rate achieved in multichannel Stop and Wait system is determined by expression (6.3). The main problem in using the multichannel system is the necessity of establishing the correct order of packets incoming. To achieve this, the buffer, intended for packets reordering is still needed at the receive side. There are different strategies for packets ordering and reordering when distributing packets over the parallel channels. For example, the fixed procedure may be used, when the i-th packet is directed to the channel with number i mod N. Surely, reordering device should always have the information aboutARQ 267 Forward Channel packet 1 Buffer 1 Check packet 2 Buffer 2 Check input packets N-Channel Reordering Sequencer ... ... ... packet N Buffer N Check Feedback Channel Figure 6.3 Multichannel SW-ARQ packets distribution at the transmitter side. Differences in ordering techniques affect the amount of memory required by the system and the delay during the messages transmission. 6.1.3 ARQ with N Steps Back (Go Back N,GBN) The mechanism of Go Back N (GBN) ARQ system does not require confirmation of every data block: the transmission is performed continuously. But if the transmitter receives the message about the lost or erroneous packet, it repeats the transmission starting from the corrupted packet. In this case even successfully transmitted packets are sent repeatedly. Such mechanism is convenient in that it does not require buffering and storing the data at the receiving side, but in case of error the channel load significantly increases. Because of the one erroneous packet correctly received data may be retransmitted many times, see Figure 6.4. In GBN ARQ system the packets are numbered and sent to channel continuously, that is, the next packet is transmitted before the confirmation of successful receiving of the previous packet is obtained. If the receiver detects an error, the number of erroneous packet is sent back as the signal for repeat transmission. As a result the transmitter goes back to send an erroneous packet and every subsequent packet. If there are buffers for N packets at the transmitter and receiver, then the transmission in forward channel is continuous, if the condition in (6.5) is satisfied. In the considered scheme the feedback communication system may be in two states: k 1. Error is not detected; the probability of this state is 1 − P , transmission rate is ; o n k 1 2. Error is detected; the probability of this state is P , transmission rate is · ,since N packets are o n N transmitted for the transmission of one packet. Then, assuming independent packets transmission, the transmission rate in GBN-ARQ scheme is: k 1 − P k 1 − P o o R = · = · (6.6) GBN n 1 − P + P · N n 1 + P · (N − 1) o o o It is clear that the GBN-ARQ scheme is not optimal, since some packets will be retransmitted even in case of successful reception. This drawback is addressed in the ARQ scheme with selective repeat.268 Modulation and Coding Techniques in Wireless Communications Communication channel Packet 1 OK Packet 2 Error ACK Packet 3 ... NAK Packet 4 ... Packet 2 OK Packet 3 OK ACK Packet 4 ... ACK Packet 5 ... Figure 6.4 Go Back N ARQ 6.1.4 ARQ with Selective Repeat (SR) When transmitting messages with high rates and on large distances, the value of N in (6.5) may turn out to be very large; this leads to significant decrease of the transmission rate (6.6). The effectiveness of communication may be improved by means of selective repeat request. In the ARQ scheme with Selective Repeat (SR) all the packets have their sequence number, and the receiver is equipped with buffer. Thus only packets which are received with errors should be retransmitted, see Figure 6.5. The feedback signal leads to retransmission of only one packet, so the transmission rate is determined by (6.3), which makes this scheme preferable compared to SW and GBN systems. Theoretically, under some conditions the multichannel SAW-ARQ and SR-ARQ may have the same transmission rate. However, in MC-SAW-ARQ the costs of service information (packet numbers, Communication channel Packet 1 OK Packet 2 Error ACK Packet 3 OK NAK Packet 4 ... ACK Packet 2 ... Packet 5 ... Figure 6.5 Selective Repeat ARQARQ 269 acknowledgments, etc.) may not be significant. This is explained by the structure of virtual channels, which guarantees the preserving of the packets order. In ARQ with selective repeat the persistent failure in transmission of one of the previous packets would prevent the transmission of subsequent packets. In this situation the channel is used ineffectively, since there will be no data sending until the blocking packet has been successfully transmitted. On the contrary, the persistent denial in transmission of one block in MC-SW-ARQ system does not affect the transmissions being performed in parallel. Surely, the delay in multichannel system will also increase, since the delay in particular channels is possible. However, delayed packets affect the transmission only in their channels, which decreases the rate much less than in SR-ARQ. The mentioned drawbacks of SR-ARQ comparing to MC-SW-ARQ do not mean the definite compar- ison result of these ARQ schemes in favour of multichannel systems, since in practice the organization of a multichannel scheme is not always possible. The SR algorithm allows the transmission of only those packets which are corrupted or lost to be repeated. But in this case the transmitter should store some number of the last sent packets. Nevertheless, since this method is the most efficient regarding the channel resources, it is the basic technique in wireless telecommunications systems. 6.2 Hybrid ARQ The classical ARQ scheme described in Section 6.1 may not be very efficient in practice, when the noise level is relatively large (when functioning in the area of low- or medium-SNR). In this case the packet transmission would always be erroneous, so the receiver should always request for retransmission, which greatly reduces the transmission throughput or even makes it impractical. The idea of the Hybrid ARQ (HARQ) scheme is to combine the error-detecting ARQ scheme with the error-correcting FEC scheme. To achieve this, prior to the transmission the message is encoded by some error-correcting code. At the receiving side the decoding attempt is made, after which the ARQ scheme of the receiver should make the decision whether the decoding was successful or not, depending on this decision the ACK or NAK signal is transmitted over the feedback channel. The detection properties for the ARQ scheme may be provided either by special ARQ detecting procedures like CRC computation or by capabilities of the error-correcting code itself. For example, symbol-by-symbol iterative decoding for some classes of codes (convolutional codes, turbo-codes, LDPC codes) in case of decoding error may lead not to the wrong codeword, but to some word which does not belong to the code (and usually contains less errors than the received word, that is, which is “closer” to the correct codeword than the received word), and this situation may be easily detected. In the following sections we consider the basic variants of Hybrid ARQ schemes. 6.2.1 Type-I Hybrid ARQ (Chase Combining) The most straightforward technique of combining the ARQ and FEC is called Type-I Hybrid ARQ 3, 4, 14 and is shown in Figure 6.6. The transmitted packet consists of the message (information) part, and the correspondent redundant parity bits calculated by means of some error-correcting code. After the packet being transmitted and the symbols are demodulated (usually providing soft-decisions of received signals or their log-likelihood ratios, LLRs), they are fed into a FEC decoder. The decoder’s output should be checked by some means to determine whether a decoding error occurred. As mentioned at the beginning of Section 6.2, this may be achieved by applying the CRC check, or in some cases this may be directly followed from the syndrome of the decoder’s output. In the case of successful decoding the decoded message bits are sent to the user, the ACK signal is sent over the feedback channel, and the next packet is prepared for transmission. In the case of a decoder’s failure, the NAK signal is sent to the transmitter, and the encoded packet is repeated.270 Modulation and Coding Techniques in Wireless Communications Communication channel message bits Decoding error Packet 1 message bits parity bits Decoder check ACK OK Decoding error Packet 2 message bits parity bits Decoder check NAK Error Packet 2 message bits parity bits Combiner Decoder message bits Decoding error check ACK OK Packet 3 message bits parity bits ... Figure 6.6 Type-I HARQ When the receiver receives the second response of the same packet (this is the case for Packet 2 in Figure 6.6), it may decode the packet independently on the previously received version (in this case there is no need for a buffer at the receiving side), or the receiver may combine the first received packet with the second one. Usually such combining is made by means of Chase combining 2, when the LLRs (soft demodulated decisions) of the correspondent bits from two received copies of transmitted packet are simply added to provide better decoding quality. Due to Chase combining procedure, the Type-I HARQ is sometimes called CC-HARQ. In fact such combining is analogous to diversity combining using MRC scheme, when two received copies of the same transmitted data are combined to provide better signal-to-noise ratio for the received symbols, see Chapter 8. The main drawback of this HARQ scheme is the low throughput when functioning in the area of relatively large SNRs, when the decoding errors sometimes occurred, but the number of errors at the decoder’s output is low and the retransmission of the whole packet is redundant and leads to throughput decreasing. 6.2.2 Type-II Hybrid ARQ (Full IR) The idea of Type-II HARQ systems is to use the variable level of redundant bits to ensure the correction of errors at the receiving side using no more parity-check bits than is actually required in current channel conditions 7, 11, 12. This scheme is depicted in Figure 6.7. In fact, to ensure the Type-II HARQ scheme, the set of T “nested” error-correcting codes is required. For the fixed number of k information symbols, for the information word m different sequences of parity- check symbols r , r ,..., r are calculated, thus providing the set of possible rates R ≥ R ≥ ... ≥ R . 1 2 T 1 2 T The decoding procedure should be possible for any rate from this set.ARQ 271 Communication channel message bits Decoding error Packet 1 message bits parity bits 1 Decoder check ACK OK Decoding error Packet 2 message bits parity bits 1 Decoder check NAK Error Packet 2 parity bits 2 Combiner Decoder Decoding error check NAK Error Packet 2 parity bits 3 Combiner Decoder message bits Decoding error check ACK OK Packet 3 message bits parity bits 1 ... Figure 6.7 Type-II HARQ (Incremental Redundancy) Then, during the first transmission attempt, only the message bits m and the parity bits r are sent, 1 that is, the code with rate R is used. This code is decoded at the receiver side, and in the case of success 1 the ACK is sent over the feedback channel. Otherwise, the NAK is sent, and during the second attempt only the parity-check bits r are sent (without repeating the message). At the receiver, these parity-check 2 bits are combined with m and r , thus obtaining the code with rate R ≤ R and higher error-correcting 1 2 1 capability (the combination and decoding procedures here depend on the type of codes being used). If necessary, during the subsequent retransmissions only the extra (new) redundant bits are sent. So, this scheme is often called the Incremental Redundancy (IR) HARQ. In fact, this scheme provides adaptation of the code rate (and corresponding error-correcting power) to the channel conditions: for better channel state only the small portion of redundant bits are used, and the transmission rate is supported at high level, but if the channel state becomes worse, extra redundant bits are sent and the errors are corrected by cost of rate decreasing. The most common approaches to construct such rate-compatible families of codes use the codes on trellis (convolutional codes or turbo-codes) 6, 13, 15, or LDPC codes 5, 17, 20. For these codes it is possible to “separate” the overall redundant bits into portions and to decode the message using only part of the initial code’s redundancy. Let us give an example of throughput estimation for Type-II HARQ scheme for some basic scenario 7, 9. We assume that the rate-compatible family of convolutional codes for Type-II HARQ transmission272 Modulation and Coding Techniques in Wireless Communications is used for BSC or AWGN channel with BPSK or QPSK. The information sequence of k bits is first encoded by the (n, k)-code for error detection, where n = k + r. For error correction after the i-th transmission the i-th (2 + i, 1, m)-convolutional code C from the family is used, where i = 0 i corresponds to the initial rate-1/2 code with memory n and generator polynomials G (x), G (x). The m 1 2 information word m is encoded by the error-detection code into codeword c, let the polynomial c(x) is correspondent to this codeword, then at each subsequent transmission either c(x)G (x)or c(x)G (x) 1 2 are sent, each containing n = n + n bits. Then, if the decoding attempts for c(x)G (x)and c(x)G (x) 0 m 1 2 fail, the c(x)G (x) is sent again and combined with previously received sequences for decoding with 1 (3, 1, m)-code with generator polynomial G (x), G (x), G (x). If this decoding is also in error, then the 1 2 1 c(x)G (x) is sent again and combined with previously received sequences for decoding with (4, 1, m)- 2 code with generator polynomial G (x), G (x), G (x), G (x), and so on. So, the i-th code C has the 1 2 1 2 i rate 1/(2 + i), i = 1, 2,... 7. Suppose that the SR-ARQ scheme is used (Section 6.1.4). Let R be the event received packet is 0 error-free, R be the eventthe received packet contains undetected error and R corresponds tothe u det received packet contains detected error. Clearly: PrR = 1 − PrR − PrR (6.7) det 0 u If the codeword contains n = n + n = (k + r) + n bits, where k is the number of information bits, 0 m m r is the number of parity-check bits and n is the number of tail bits for trellis termination, then: m n 0 PrR = (1 − p) (6.8) 0 where p is the bit error probability for BSC channel, or:    2E b p = Q N 0 for AWGN channel (see (2.73)), where E is the transmitted energy per bit, N is the noise power, and b 0 Q-function is defined in (2.63):  ∞ 2 1 −y 2 Q(x) = √ e dy 2π x If we assume that the probability of non-detected error in channel PrP is negligible, then from (6.7) u and (6.8) we have: n 0 PrR ≈ 1 − PrR = 1 − (1 − p) det 0 Now consider the sequences obtained after the Viterbi decoding procedure after i-th transmission. Let’s (i) (i) (i) define another set of events D , D and D as decoded sequence contains no errors, decoded 0 u det sequence contains undetected errors,anddecoded sequence contains detected errors correspondingly. (i) Again we assume that PrD is negligible. The probability of correct decoding may be limited as: u (i) (i) n PrD ≥ (1 − PrE ) 0 (i) where E is decoding error event for Viterbi decoding. Then the probability of detected errors after decoding is: (i) (i) (i) n PrD ≈ 1 − PrD ≥ 1 − (1 − PrE ) (6.9) 0 det (i) The value of PrE may be bounded as 19: ∞  (i) (i) PrE ≤ a P d d (i) d=d freeARQ 273 (i) (i) where d is the free distance of C , a is distance spectra of C ,and P is the probability of selection i i d d free the wrong path at distance d. For the BSC channel: ⎧ d  ⎪ d ⎪ j d− j ⎪ p (1 − p) d odd, ⎪ ⎨ j j=(d+1)/2 P = d d ⎪  1 ⎪ d d ⎪ j d− j d/2 d/2 ⎪ p (1 − p) + p (1 − p) d even ⎩ j d/2 2 j=d/2+1 and for AWGN channel:    2dE b P = Q d N 0 ¯ The average number of transmissions N is 7:     (1) (1) (2) ¯ N = 1 + PrR + Pr R , R , D + Pr R , R , D , R , D + det det det det det det det det det   (1) (2) (3) + Pr R , R , D , R , D , R , D +... det det det det det det det   (1) (2) (3) (i) ... + Pr R , R , D , R , D , R , D ,..., R , D +... det det det det det det det det det This value may be bounded as: ∞ i ∞        ( j) (i) i+1 ¯ 1 + PrR + PrR Pr D ≤ N ≤ 1 + PrR + Pr D (6.10) det det det det det i=1 j=1 i=1 ¯ In fact, the lower and upper bounds on N in (6.10) are approximately the same, so we may approximate this value as: ∞    (i) ¯ N ≈ 1 + PrR + Pr D det det i=1 The throughput η is defined as: R η = ¯ N where R is code rate, which is in our case R = k/n ,sowehave: 0   R k 1 ≈ · η =  ∞ (i) ¯ N k + r + n m 1 + PrR + PrD det i=1 det The drawback of the Incremental Redundancy scheme is the case when the initial transmission containing the message bits fall under very bad channel conditions, and the number of errors occurred is very high. First, in this case extra parity bits may not be helpful, and second, during subsequent transmissions there is no new information about the message part itself, which would allow combining as in Type-I HARQ. This problem is partly overcome in Type-III HARQ. 6.2.3 Type-III Hybrid ARQ (Partial IR) Themainpropertyof Type-III HARQ system 1, 8 (which is also sometimes referred to as Partial Incremental Redundancy) is that all transmitted packets are self-decodable. This scheme is shown in Figure 6.8. With this type of HARQ transmission, all the transmitted packets contain the message part, and in all cases (including retransmission) the decoding attempt of the receiving packet is first made. If the attempt fails, then NAK is sent over the feedback channel (if no retransmissions of this packet are available), or274 Modulation and Coding Techniques in Wireless Communications Figure 6.8 Type-III HARQ (Partial Incremental Redundancy) the packet is consequently combined with the previously received versions and new decoding attempts are made. If all the decoding attempts are failed, the NAK is sent. In some sense, this type of transmission may be considered as a version of Type-I HARQ, when all the repeated packets contain the same message part, but with different parity-checks, and in some sense, since the parity-checks are changed, this scheme may be considered as Incremental Redundancy scheme. Since all the packets should transfer information part and parity-check part, there is no rate adaptation to the variable channel conditions in Type-III scheme as compared to Type-II scheme. In the situation when the noise level is relatively high, Type-III HARQ may overcome the Type-II HARQ systems with full Incremental Redundancy, but with the increasing of SNR it become worse in terms of throughput since there is no need for multiple transmission of the same information part. Again, we will estimate the throughput of the Type-III HARQ scheme for the Gaussian channel using the same family of convolutional codes as in Section 6.2.2 8. In this case, q puncturing patterns P , i = 1, 2,..., q are used to obtain the codes C of rate R = b/V from the original convolutional i iARQ 275 ( j) code of rate 1/V . The combination of j such codes C is obtained using the puncturing matrix 0 ( j) P = P + P +... + P . Each packet of n = k + r + n bits, where k is information length, r is the 1 2 j 0 m number of redundant bits for error detection and n is the memory of the encoder, is encoded with the m rate-1/V code. Then the coded bits from C , C , ... are sent (until ACK is obtained from the feedback 0 1 2 channel) and decoded at the receiver side using the patterns P (after the first transmission), P and, in 1 2 (2) case of error, P (after the second transmission), and so on. At step i 1, first the decoding attempt (i) (i) for code C with pattern P is made, and then, in case of error, the combined code C with pattern P i i is applied. If after q attempts decoding is failed, then the received sequence for C is discarded and the 1 procedure continues with sending the bits from C again, and so on. 1 (i) (i) Let F be the event decoding error after i transmissions,and D be the event error detected det (i) ¯ after decoding in C . Then the average number of transmissions N is: (1) (1) (2) ¯ N = 1 + PrF + PrF , F + (1) (2) (3) + PrF , F , F +... (6.11) (1) (2) (3) (i) ... PrF , F , F ,..., F +... (1) (i) (1) (q) (i) Event F is equivalent to joint event D , D for i q andtojoint event D , D for i ≥ q. det det det det Each term in (6.11) may be bounded as: ⎧ (i) PrD , i ≤ q ⎪ det ⎪ ⎨ (1) (i) (q) j PrF ,..., F ≤ PrD , i = jq, j = 1, 2,... (6.12) det ⎪ ⎪ ⎩ (q) (i−jq) j PrD PrD , jq i ( j + 1)q, j = 1, 2,... det det From (6.11) and (6.12) obtain:  q−1 (i) 1 + PrD i=1 det ¯ N ≤ (q) 1 − PrD det (i) wherethe valueofPrD may be estimated as in (6.9). Finally, the estimation of throughput for the det considered example is: (q) R(1 − PrD ) R det η = ≥  q−1 (i) ¯ N 1 + PrD i=1 det References 1 3GPP TSG RAN WG12 Tdoc R1-99061, “Hybrid ARQ techniques for efficient support of packet data”, Panasonic, Japan, Feb. 1999. Available: ftp/ tsg ran/ WG1 RL1/ TSGR1 02/ Docs/ pdfs/ R1-99061.pdf 2 Chase, D. Code combining. A maximum likelihood decoding approach for combining an arbitrary number of noisy packets, IEEE Transactions on Communications, vol. 33, pp. 385–393, May 1985. 3 Chockalingam, A., Zorzi, M., Tralli, V. Wireless TCP performance with link layer FEC/ARQ, Proceedings, IEEE ICC’1999, vol. 2, pp. 1212–1216, Canada, 1999. 4 Deng, R. H. Hybrid ARQ scheme using TCM and code combining, IEE Electronics Letters, vol. 27, no. 10, pp. 866–868, May 1991. 5 Ha, J., Kim, J., McLaughlin, S. W. Rate-compatible puncturing of low-density parity-check codes, IEEE Trans. on Information Theory, vol. 50, no. 1, pp. 2824–2836, 2004. 6 Hagenauer, J. Rate Compatible punctured convolutional codes (RCPC) and their applications, IEEE Transac- tions on Communications, vol. 36, no. 4, pp. 389–400, 1988. 7 Kallel, S. Analysis of a type-II Hybrid ARQ scheme with code combining, IEEE Transactions on Communications, vol. 38, no. 8, pp. 1133–1137, Aug. 1990.276 Modulation and Coding Techniques in Wireless Communications 8 Kallel, S. Complementary punctured convolutional (CPC) codes and their applications, IEEE Transactions on Communications, vol. 43, no. 6, pp. 2005–2009, June 1995. 9 Kallel, S, Haccoun, D. Generalized type II Hybrid ARQ scheme using punctured convolutional coding, IEEE Transactions on Communications, vol. 38, no. 11, pp. 1938–1946, 1990. 10 Lin, S., Costello, D. J. Error control coding, second ed., Prentice Hall, Englewood Cliffs, NJ, 2004. 11 Lin, S., Yu, P. S. A hybrid ARQ scheme with parity retranmission for error control of satellite channels, IEEE Transactions on Communications, vol. COM-30, no. 7, pp. 1701–1719, 1982. 12 Mandelbaum, D. M. An adaptive-feedback coding scheme using incremental redundancy, IEEE Trans. on Information Theory, vol. 20, pp. 388–389, 1974 13 Rowitch, D., Milstein, L. On the performance of hybrid FEC/ARQ systems using rate compatible punctured turbo (RCPT) codes, IEEE Transactions on Communications, vol. 48, pp. 948–959, 2000. 14 Schmitt, M. P. Hybrid ARQ scheme employing TCM and packet combining, IEE Electronics Letters, vol. 34, no. 18, pp. 1725–1726, September 1998. 15 Schmitt, M. P. Improved retransmission strategy for hybrid ARQ schemes employing TCM, Proceedings, IEEE Wireless Communications and Networking Conference, vol. 3, pp. 1226–1228, September 1999. 16 Schmitt, M. P. ARQ systems for wireless communications, Ph.D. Thesis, Technical University Darmstadt, Darmstadt, 2002. 17 Sesia, G. C. S., Vivier, G. Incremental Redundancy Hybrid ARQ Schemes Based on Low-Density Parity-Check Codes, IEEE Transactions on Communications, vol. 52, no. 8, pp. 1311–1321, Aug. 2004. 18 Stender, B. Signaling Aspects for Wireless Communications, Ph.D. Thesis, University of Ulm, Germany, 2007 19 Viterbi, A. J. Convolutional codes and their performance in communication systems, IEEE Transactions on Communications, vol. COM-19, Oct. 1971. 20 Yazdani, M., Banihashemi, A. On construction of rate-compatible low-density parity-check codes, IEEE Com- munications Letters, 8 (3), 2004.7 Coded Modulation Andrey Trofimov St. Petersburg State University of Aerospace Instrumentation, Russia 7.1 Principle of Coded Modulation For uncoded M-ary transmission using signals, belonging to a signal set, or signal alphabet S, M = S, m M = 2 , m is integer, data transmission rate is equal to: log M 2 R = , bit/s (7.1) u T where T is signalling interval. Hereafter the narrowband signalling is assumed, for example, PSK and QAM as most important cases. For such signal sets the bandwidth W used for transmission does not depend on number of signals M in signal set S, and it can be evaluated as: α W = (7.2) T where α is a pulse shape dependent constant. In particular, for signals of duration T with a constant envelope α = 2, for signals with envelope of sinc(·), transmitted with period T , α = 1. In further consideration we assume that the pulse shape is chosen and remains unchangeable, hence the value of α is constant for all cases of uncoded and coded systems considered in this chapter. Ratio of transmission rate to bandwidth is called spectral efficiency. For uncoded transmission the spectral efficiency is equal to: R u η = , bit/(s · Hz) (7.3) u W and as it follows from (7.1) and (7.2): log M 2 η = , bit/(s · Hz) (7.4) u α For coded data transmission the structure of the transmitting part of the system can be presented (with a minor loss of generality negligible for practice) as it is shown in Figure 7.1 Modulation and Coding Techniques in Wireless Communications Edited by Evgenii Krouk and Sergei Semenov  C 2011 John Wiley & Sons, Ltd278 Modulation and Coding Techniques in Wireless Communications Correcting Modulation Pulse code mapping shaping encoder sequence of n /m sequence of n /m k data bits n coded bits signal points signals Figure 7.1 General structure of transmitting part of coded system (t) (t) (t) k Let us denote input data block at time t as u = (u ,..., u )∈0, 1 , and coded block at 0 k−1 (t) (t) (t) n (t) time t as v = (v ,...,v )∈0, 1 .Codedblock v before mapping is divided into (n/m) 0 n−1 (t) (t) (t) 1 (t) m sub-blocks of length m bits as follows v = (v ,..., v ), where v ∈0, 1 , l = 0 n/m−1 l m (t) (t) (t) 0, 1,..., n/m − 1. Modulation mapping M : 0, 1 → S can be defined as s = s(v ), where s 2 ∈ S .Sincethepulseshapingisassumedtobefixedthe set of signal points (signal constellation)and signal set are isomorphic. From here on we assume the set S as subset of D-dimensional real Euclidean D space, that is, S ⊂ R . For most important in practice examples of PSK and QAM signal space dimension D = 2. Transmission rate R for coded transmission can be computed as: c k R log M 2 R = = , bit/s (7.5) c (n/m)T T where R is the correcting code rate, R = k/n. The spectral efficiency η for coded transmission can be c expressed as: R R log M c 2 η = = , bit/(s · Hz) (7.6) c W α It immediately follows from comparison between (7.6) and (7.4) that η = η if R = 1, i.e. for nonredun- c u dant transmission. It also follows from (7.6) and (7.4) that error correcting coding decreases the spectral efficiency 1/R times. In practice that means decreasing data transmission rate and/or increasing the bandwidth. Positive outcome of error correcting coding is an improved reliability of data transmission. For years the trade-off “spectral efficiency – reliability” was considered as an unavoidable feature of error correcting coding. In 1 G. Ungerboeck has suggested a scheme of combined design of error correcting code and modulation mapping of coded subblocks into an extended signal set. This combination of coding and modulation does not cause the spectral efficiency to decrease, but it has an improved performance in comparison with uncoded transmission. In other words, the coding in such cases does not cause either bandwidth extension, or slowing down of the transmission rate. This effect is achieved by using an extended signal set (extended signal constellation). be the extended signal set with M signal points. M = S M. In this case (7.6) can be Let S c c c c written down as: R log M c s η = , bit/(s · Hz) (7.7) c α Equating the right hand parts of (7.7) and (7.4) we get the condition for rate R of the error correcting code: log M 2 R = (7.8) log M 2 c 1 We assume that m is divisor of n. 2 Distinguish Greek M for mapping and italic M for cardinality of signal set.Coded Modulation 279 PSK8 PSK16 PSK4 E E E δ (S ) = (2 − 2 − 2 )E ≈ δ (S) = 2E ≈ 1.414 E δ (S ) = (2 − 2)E ≈ 0.765 E c c 0.390 E Figure 7.2 Signal constellations for PSK4 (basic signal set) and PSK8 and PSK16 (extended signal sets) which keeps the spectral efficiency unchangeable in comparison with uncoded transmission. For example, if for uncoded transmission M = 4, and for coded transmission M = 8, then for code with rate R = c log M/ log M = 2/3 there is no loss of spectral efficiency. If the signal alphabet is extended up to c 2 2 M = 16 signal points then the code with R = 1/2 can be used. c From general principles of coding theory it follows that decreasing of code rate leads to increasing of correcting capability. On the other hand, minimum distance in signal set diminishes with increasing the number of signal points and keeping energy (or average energy) of the signal constant. D Let d(x, y) be the Euclidean distance between any points x, y ∈ R . Let us introduce minimum distance δ in signal set S as: δ(S) = min d(x, y) x=y,x,y,∈S Examples of signal constellations and their minimum distances for PSK4, PSK8 and PSK16 are shown in Figure 7.2. Signal energy, or Euclidean norm of signal points is denoted as E. Examples of signal constellations and their minimum distances for QAM4, QAM8 and QAM16 are given in Figure 7.3. Here E is average signal energy, or average squared Euclidean norm of signal points. It follows from Figure 7.2 that the minimum distance decreases 1.848 times and 3.624 times with increasing the signal points in PSK signal constellation from 4 to 8 and to 16 respectively. For QAM constellation, see Figure 7.3, the corresponding factors are 1.158 and 2.236. Nevertheless, it is possible QAM4 QAM8 QAM16 E E E 2E 4E δ (S ) = ≈ 0.633 E c δ (S ) = ≈ 0.894 E δ (S) = 2E ≈ 1.414 E c 5 5 Figure 7.3 Signal constellations for QAM4 (basic signal set) and QAM8 and QAM16 (extended signal sets)280 Modulation and Coding Techniques in Wireless Communications (t) (t ) u v 0 0 Convolutional n k (t ) … 0 0 … s Modulation encoder mapping k 1 … … (t ) (t) u v k −1 n−1 “Full” encoder (t) (t ) (t ) (t ) (t) (t) v = (v ,...,v ) u = (u ,...,u ) 0 n−1 0 k−1 Figure 7.4 Trellis coded modulation scheme to increase the minimum distance between sequences of signal points, using the specially designed correcting code and modulation mapping. A general scheme of combined trellis coded modulation (TCM) using an extended signal set is shown in Figure 7.4. The scheme consists of encoder of convolutional code of rate k /n with memory of ν bits, and 0 0 modulation memoryless mapper. Encoder produces n coded bits and after combining them with k 0 1 uncoded bits forms n = n + k bits coming into modulation mapping. The overall code rate is k/n, 0 1 where k = k + k . 0 1 (t) (t) ν Let σ be an encoder state at time t, σ ∈0, 1 for all t. State transitions of the encoder can (t+1) (t) (t) (t) be defined as σ = σ (u ,σ ), where σ (·,·) is time-invariant state transition function, and u (t) is the encoder input at time t as shown in Figure 7.4. Encoded block v at time t can be defined (t) (t) (t) as v = v(u ,σ ), where v(·, ·) is time-invariant output function. For convolutional encoder these functions are linear over GF(2), that is: (t) (t) (t) (t) (t) (t) (t) (t) σ (u + u ,σ + σ ) = σ (u ,σ ) + σ (u ,σ ), (t) (t) (t) (t) (t) (t) (t) (t) (t) v = v(u + u ,σ + σ ) = v(u ,σ ) + v(u ,σ ) In this scheme it is assumed that m = n (see Figure 7.1), that is, each coded block is mapped into one of n M = 2 signals. c Decoding for TCM is usually implemented as Viterbi algorithm (VA) 2 on the trellis of the en- coder with edges labelled according to modulation mapping. The VA accepts the soft decisions from demodulator and searches for the path in trellis minimizing squared Euclidean distance between received ν sequence and coded signal sequence. The trellis at each level has 2 nodes, and every node is connected k k 1 0 by 2 parallel edges with each of 2 previous nodes. Any edge corresponds to one signal belonging to extended signal set S . c 7.1.1 Illustrative Example In this example we assume transmission with PSK at rate 2/T bit/s, where T is signal interval duration. In this example we examine minimum distances between two signal sequences. Let u and v(u)bedataCoded Modulation 281 10 δ(S) 00 11 01 Figure 7.5 Example of modulation mapping for uncoded transmission sequence and corresponding coded sequence respectively, and s(v(u)) be signal sequence at the mapper output. A. Uncoded transmission. The PSK4 signals conform to transmission rate 2/T bit/s. For uncoded  transmission v(u) = u, and min d (s(v(u)), s(v(u )) = δ(S). Example for modulation mapping for PSK4  u=u (Gray mapping) is shown in Figure 7.5. It is easy to see that the squared minimum distance between two signal sequences is equal to squared minimum distance between signal points: 2  2  2 d (s(v(u)), s(v(u) )) = d (s(u), s(u )) = d (s(00), s(10)) = δ(S) = 2E (7.9) B. Coded transmission. An example of encoder and modulation mapping is shown in Figure 7.6. (t) (t) (t) (t) (t) The encoder state in time t is σ = (σ ,σ ), σ ,σ ∈0, 1. It is easy to see from Figure 7.6 0 1 0 1 (t) (t−1) (t) (t−1) (t−2) (t+1) (t) (t) that σ = u , σ = σ = u . State transition function is defined as σ = σ (u ,σ ) = 0 0 1 0 0 (t) (t) (t) (t) (t) (t) (t) (t) (t) (t) (t) (u ,σ ). Output coded block v = (v ,v ,v ) is computed as v = v(u ,σ ) = (σ , u + 0 0 0 1 2 0 0 (t) (t) σ , u ). 1 1  Let us consider transmission of the data sequences u = (00, 00, 00,...)and u = (10, 00, 00,...)by  this code. Evidently, v(u) = (000, 000, 000,...). For data sequence u the encoder state transitions and encoder outputs are shown in Table 7.1. It can be easily computed that squared Euclidean distance between the signal sequences corrresponding  to data sequences u and u is: 2  2 2 2 d (s(v(u)), s(c(u ))) = d (s(010), s(000)) + d (s(100), s(000)) + d (s(010), s(000))     √ √ = 2E + 2 + 2 E + 2E = 6 + 2 E ≈ 7.414E (t ) v 0 (t) u 101 0 000 011 (t) (t) (t ) s = s(v ) (t ) σ σ 0 1 Modulation 110 111 mapping + (t) δ (S ) v c 1 001 (t) u 1 (t) 010 100 v 2 Figure 7.6 Example of trellis coded modulation scheme282 Modulation and Coding Techniques in Wireless Communications Table 7.1 Example of two coded signal sequences (t) v = (t) (t) (t) (t) (t) (t) (t) (t) (t)  t u = (u , u ) σ = (σ ,σ ) (v ,v ,v ) s(v(u )) s(0, 0,...) 0 1 0 1 0 1 2 1 1 0 0 0 010 2 0 0 1 0 100 3 0 0 0 1 010 4 0 0 0 0 000 ... ... ... ... Comparing this value with (7.9) we see that in this case the first data bit is protected much better.  Trellis for this example is depicted in Figure 7.7. The paths corresponding to s(v(u)) and s(v(u )) are shown as bold lines. They differ in the first three transitions and merge together later on. Free Euclidean distance d is a principal parameter for trellis codes and decoding with VA. It can be f 2 shown that for the code and modulation mapping shown in Figure 7.6 d = 4E. That means 3 dB energy f gain in comparison with uncoded transmission (see (7.9)). 7.2 Modulation Mapping by Signal Set Partitioning The Ungerboeck coded modulation scheme is based on a) modulation mapping by set partitioning, and b) especially designed convolutional codes. Let us consider modulation mapping suggested in 1. Modulation mapping can be described as a step-by-step procedure. The number of steps is equal to m, m = log M . For the Ungerboeck TCM c 2 scheme m = n,where n is number of output coded symbols. At each step of the procedure the signal subset is divided into two subsets. On the very first stage the signal subset is equal to the whole signal set S containing M signal points. After last step of partitioning the signal subset consists of a single signal c c point. Any subset derived on l-th step of partitioning corresponds to a l−bit binary vector. Therefore l l number of subsets on l-thstepisequalto2 .Let v be a binary vector of length l,thatis, v ∈0, 1 , l l l l = 1, 2,..., n.Let S (v , l) be one of 2 signal subsets derived on l-th step of partitioning. Then the c l t 1 2 3 … 00 01 … 10 11 Figure 7.7 Example of code trellis

Advise: Why You Wasting Money in Costly SEO Tools, Use World's Best Free SEO Tool Ubersuggest.