In a digital communications system, such as a CDMA (Code Division Multiple Access) system, a data bit stream comprising a stream of binary bits representing a message is transmitted by a transmitter, travels through a data channel, and is received by a receiver. The data bit stream is generally composed of a number of message blocks. If the length of a message block is not fixed, the system may be referred to as a variable-length communications system. In such a variable-length system, additional length information of each message block is generally required for the receiver to identify each message block and extract the message from the received data bit stream. A conventional method of a variable-length communications system designates a separate channel as a control channel for transmitting length information of each message block. Thus, when the receiver receives both the length information and the data bit stream, the receiver identifies the corresponding message blocks based on the length information, and de-blocks the data bit stream.
The conventional method also generally utilizes cyclic redundancy check (CRC) bits for error detection purposes. In particular, a fixed number of CRC bits are appended to the end of each message block and have a predetermined relationship with the corresponding message block. The receiver receives both the message block and the CRC bits following that message block, and tries to re-establish the relationship therebetween. If the relationship is satisfied, the message block is considered without error. Otherwise, an error has occurred during the transmission of that block. This method is further explained in greater detail below.
First, a CRC generating polynomial, gl(x), of order l, is chosen. A common way of choosing the CRC generating polynomial is that gl(x) should satisfy gcd(gl(x),xi)=1 for each and every i between 0 and l, inclusive, wherein l and i are integers, and the function gcd(A(x),B(x)) is defined as the greatest common divider of polynomials A(x) and B(x). Examples of suitable gl(x) include g4(x)=x4+x3+x2+x+1 for l=4; g7(x)=x7+x6+x4+1 for l=7; g8(x)=x8+x7+x4+x3+x+1 for l=8; and g12(x)=x12+x11+x3+x2+x+1 for l=12. The information of CRC generating polynomial is stored in both the transmitter and the receiver.
For illustration purposes, a binary polynomial is defined for each binary bit stream as follows: if a binary bit stream A includes t binary bits, at−1, at−2, . . . , a0, wherein t is an integer, the binary polynomial of A is denoted as A(x) and A(x)=at−1xt−1+at−2xt−2+ . . . +a0. Also for illustration purposes, binary bit stream A is said to satisfy the CRC condition if A(x) is divisible by gl(x). Two binary bit streams A and B are said to satisfy the CRC condition if xsA(x)+B(x) is divisible by gl(x), wherein s is the number of bits contained in bit stream B. It is well known to one skilled in the art that when, for example, a polynomial A(x) is divisible by another polynomial gl(x), remainder of A(x) divided by gl(x) is 0, and it may be said that gl(x) divides A(x), denoted as gl(x)|A(x).
Next, for a message block M containing k bits of binary information, mk−1, mk−2, . . . , m0, a parity check bit stream P including l parity check bits, or CRC bits, pi−1, pt−2, . . . , p0, is generated such that M and P satisfy the CRC condition, or gl(x)|(xlM(x)+P(x)). A parity check bit stream may also be called a parity block, a parity check block, or a CRC block. For each message block M, it may be proved that there is only one corresponding parity check bit stream P. The proof is understood by one skilled in the art and is not discussed in detail herein.
According to the standard CRC method, parity check bit stream P may be generated using either hardware or software. Examples of hardware implementations are shown in FIGS. 1–2, and an example of a software implementation is shown in FIG. 3. Both FIGS. 1 and 2 assume l=8 and CRC generating polynomial gl(x)=x8+x7+x4+x3+x+1.
FIG. 1 illustrates a first hardware implementation of generating parity check bit stream P. Referring to FIG. 1, a feedback shift register circuit 100 is used for generating parity check bit stream P based on CRC generating polynomial gl(x)=x8+x7+x4+x3+x+1. Circuit 100 includes a plurality of delay circuits 102, which may be implemented as flip-flops. The number of delay circuits 102 is equal to the order of gl(x), i.e., l=8. Thus, in FIG. 1, there are 8 delay circuits, 1021, 1022, . . . , 1028. Several XOR gates 104 are inserted between delay circuits 102. Each XOR gate 104 corresponds to a coefficient of CRC generating polynomial gl(x). For example, as shown in FIG. 1, an XOR gate 1041 to the left side of the first delay circuit 1021 indicates that the coefficient of x0=1 of gl(x) is 1; the absence of XOR gate 104 between delay circuits 1022 and 1023 indicates that the coefficient of x2 of gl(x) is 0; and an XOR gate 1045 between delay circuits 1027 and 1028 indicates that the coefficient of x7 of gl(x) is 1. A clock signal (not shown) shifts register circuit 100 from left to right one bit at a time. Also shown in FIG. 1 is that the output of delay circuit 1028 is fed back to each of XOR gates 1041–1045. The parity check bit stream P is generated by feeding into the left side of circuit 100 the message block M followed by eight bits of 0. The output of delay circuit 1028 then comprises message block M followed by its corresponding parity check bit stream P.
A second hardware implementation of generating parity check bit stream is illustrated in FIG. 2. Similarly, a feedback shift register circuit 200 includes a plurality of delay circuits 202, each of which may be implemented as a flip-flop circuit. Several XOR gates 204 are inserted between delay circuits 202 according to CRC generating polynomial gl(x). However, as compared to FIG. 1, an XOR gate 204 is added to the right end of circuit 200, rather than the left end of circuit 200, and the message block M is input into the rightmost XOR gate 204. A switch 206 switches the output of feedback shift register circuit 200 between message block M and the output of the rightmost XOR gate 204. Feedback shift register circuit 200 first outputs message block M and then outputs the parity bits by switching switch 206 to the output of the rightmost XOR gate 204.
FIG. 3 illustrates a software implementation of generating parity check bit stream P. Rather than generating the parity check bit stream P bit by bit, a lookup table is used in the software implementation. The lookup table contains an entire list of CRC bit streams for all possible messages of a certain length. For example, when l=8, the lookup table includes 28=256 entries of CRC bit streams, each bit stream containing eight binary bits. As shown in FIG. 3, a message including 3 bytes (24 bits), Byte 1, Byte 2, and Byte 3, is encoded using the lookup table. At step 302, Byte 1 is considered and the lookup table is searched for a matching entry for Byte 1. An XOR operation is performed on the outcome of the search and Byte 2 at step 304 to generate an intermediate CRC bit stream CRC 2. An entry that matches CRC2 is looked up in the lookup table (step 306) and is XOR'ed with Byte 3 (step 308), to generate the CRC bit stream, CRC 3, of the message.
The above three implementations will be readily understood by one skilled in the art and, therefore, the details thereof are not further discussed herein.
After the parity check bit stream P is generated, the parity check bits thereof are appended to the end of the message block M to form a concatenated bit stream C including k+l bits, mk−, mk−2, . . . , m0, pl−1, pl−2, . . . , p0. In view of the above conditions, gl(x) divides C(x)=xlM (x)+P(x).
For each message block contained in the message, the above encoding process is repeated to generate a corresponding concatenated bit stream, and a data bit stream including the concatenated bit streams and length information of each message block are then transmitted through a data channel and a control channel, respectively.
At the receiver side, both the data bit stream and the length information are received. A received message block M′ and a parity check bit stream P′ are extracted based on the length information, wherein M′ includes k bits, m′k−1, m′k−2, . . . , m′0, and P′ includes l bits, p′l−1, p′l−2, . . . , p′0. The receiver then performs a so-called CRC test to determine if M′ and P′ satisfy the CRC condition. If the condition is satisfied, then the message block is received with no error.
A system using a separately designated control channel for transmitting length information as discussed above could be very inefficient when the data rate is slow. For example, in a standard UMTS (universal mobile telecommunications system) WCDMA (wideband code division multiple access) mode, AMR (Adaptive Multi-Rate) 12.2 kbps mode, the overhead for transmitting the length information may be as large as 3 kbps, or almost 25% of the total transmission rate of 12.2 kbps.
To reduce the overhead incurred by separately transmitting the length information, there has been proposed a CRC method (hereinafter “standard CRC method”) that uses the CRC bits for message length detection, rather than transmitting the length information of each message block through a separate channel. According to the standard CRC method, the transmitter only transmits the data bit stream, and the receiver receives the data bit stream with no length information. Thus, the receiver may not directly identify the message blocks or extract the message. Instead, the receiver repeats a trial-and-error step to search the received data bit stream for a pair of message block and parity check bit stream that satisfy the CRC condition. First, the receiver guesses a number, for example, {circumflex over (k)}, as the block length, and treats the first {circumflex over (k)} bits of the received bit stream as the message block, and the following l bits as parity check bit stream. The receiver then performs the CRC test to determine if the guessed message block and the guessed parity check bit stream satisfy the CRC condition. If the result is affirmative, the receiver has successfully identified a message block and continues to identify the next message block. Otherwise, the message block has not been identified, the guessed block length {circumflex over (k)} is increased by 1, and the CRC test is repeated. Theoretically, after a few trials, the correct message block will be identified.
However, the standard CRC method has an inherent problem of probable false detection. Assuming a noise-free transmission and a uniformly distributed message, the probability of a false detection by the standard CRC method is given by Expression (1):
                                          P            F                    ⁡                      (            i            )                          =                  {                                                    0                                                                                                        for                      ⁢                                                                                          ⁢                      i                                        =                    0                                    ;                                                                                                                          2                                          -                      i                                                        ,                                                                                                                        for                      ⁢                                                                                          ⁢                      1                                        ≤                    i                    ≤                                          l                      -                      1                                                        ;                                                                                                                          2                                          -                      i                                                        ,                                                                                                                        for                      ⁢                                                                                          ⁢                      i                                        ≥                    l                                    ,                                                                                        (        1        )            
wherein i=k−{circumflex over (k)} is the message length offset. A brief explanation of Expression (1) is provided below.
Since the transmission is assumed noise-free, all the bits transmitted are received without error. Therefore, if i=k−{circumflex over (k)}=0, the CRC condition is satisfied and a correct message block is identified. No false detection occurs, i.e., PF(0)=0.
If i=k−{circumflex over (k)}=1, the wrongly guessed message block M′ includes k−1 bits, mk−1, mk−2, . . . , m1, and the guessed parity block P′ includes l bits, m0, pl−1, p1−2, . . . , p1. The CRC test therefore decides whether gl(x) divides
                                          C            ′                    ⁡                      (            x            )                          =                ⁢                                            x              l                        ⁢                                          M                ′                            ⁡                              (                x                )                                              +                                    P              ′                        ⁡                          (              x              )                                                              =                ⁢                                            m                              k                -                1                                      ⁢                          x                              l                +                k                -                2                                              +                                    m                              k                -                2                                      ⁢                          x                              l                +                k                -                3                                              +          …          +                                    m              1                        ⁢                          x              l                                +                                    m              0                        ⁢                          x                              l                -                1                                              +                                                ⁢                                            p                              l                -                1                                      ⁢                          x                              l                -                2                                              +                                    p                              l                -                2                                      ⁢                          x                              l                -                3                                              +          …          +                                    p              1                        .                              Because gcd(gl(x),x)=1, deciding whether gl(x)|C′(x) is equivalent to deciding whether gl(x)|xC′(x). Comparing C′(x) with C(x), there is xC′(x)=C(x)−p0. Thus, if p0=0, because gl(x)|C(x), then gl(x)|xC′(x), and g1(x)|C′(x). The receiver regards the wrong message block M′ as the correct message block, and there is a false detection. Otherwise, if p0=1, the CRC condition is not satisfied, the receiver concludes that M′ is not the correct message block, and there is no false detection. For a uniformly distributed message, the probability of p0=0 is ½, and, therefore, the probability of a false detection is ½.
Similarly, if 1<i≦i−1, the wrongly guessed message block M′ includes k−i bits, mk−1, mk−2, . . . , mi, and the wrongly guessed parity block P′ includes l bits, mi−1, mi−2, . . . , m0, pi−1, pi−2, . . . , pi. The CRC test therefore decides whether gl(x) divides
                                          C            ′                    ⁡                      (            x            )                          =                ⁢                                            x              l                        ⁢                                          M                ′                            ⁡                              (                x                )                                              +                                    P              ′                        ⁡                          (              x              )                                                              =                ⁢                                            m                              k                -                1                                      ⁢                          x                              l                -                i                +                k                -                1                                              +                                    m                              k                -                2                                      ⁢                          x                              l                -                i                +                k                -                2                                              +          …          +                                    m              0                        ⁢                          x                              l                -                i                                              +                                                ⁢                                            p                              l                -                1                                      ⁢                          x                              l                -                i                -                1                                              +                                    p                              l                -                2                                      ⁢                          x                              l                -                i                -                2                                              +          …          +                                    p              i                        .                              Comparing C′(x) with C(x), there is
            x      i        ⁢                  C        ′            ⁡              (        x        )              =            C      ⁡              (        x        )              -                  ∑                  j          =          0                          i          -          1                    ⁢                                    p            j                    ⁡                      (            x            )                          .            Because the order of gl(x), l, is greater than i, gl(x) does not divide
            ∑              j        =        0                    i        -        1              ⁢                  p        j            ⁡              (        x        )              ,unless p0=p1= . . . =pi−1=0. Further because gl(x)|C(x), and gcd(gl(x),xi)=1, gl(x)|C′(x) is satisfied only when p0=p1= . . . =pi−1=0. Thus, the probability of a false detection when 1<i≦l−1 is equal to the probability of p0=p1= . . . =pi−1=0, which, for a uniformly distributed message, is 2−i.
Finally, if i≧l, the guessed message block M′ includes k−i bits, mk−1, mk−2, . . . , mi, and the guessed CRC bit stream P′ includes, mi−1, mi−2, . . . , mi−l. Since there is only one possible CRC bit stream that corresponds to M′, the probability of P′ satisfying the CRC condition of gl(x)|(xlM′(x)+P′(x)), i.e., the probability of a false detection, is 2−l for a uniformly distributed message block.
FIG. 4 shows a simulation result of the probability of passing the CRC test for the standard CRC method with different guessed message lengths. The simulation conditions include that the order of the CRC generating polynomial is 8 and that the actual message length is 15. As shown in FIG. 4, as the estimated message size approaches the actual message length, i.e., the length offset i approaches 0, the probability of passing the CRC test increases exponentially.
In view of the large probability of false detection for a standard CRC method, a modified CRC method with a reduced probability of false detection has been proposed by NTT DoCoMo, Inc., and may be referred to as the DoCoMo's Modification of the CRC method. According to the DoCoMo's Modification, after the parity check bit stream P is generated, the parity check bits are appended to the message block in a reversed order, to form a concatenated bit stream, mk−1, mk−2, . . . , m0, p0, p1, . . . , pi−1. FIG. 5 shows simulation results for the DoCoMo's Modification as compared to the standard CRC method. The conditions are the same as those in FIG. 4, i.e., the order of the CRC generating polynomial is 8 and the actual message length is 15. As shown in FIG. 5, the probability of passing the CRC test, i.e., the probability of false detection is reduced to 2−l for all message length offset i>0.