Abstract:
The present invention provides a turbo-code block message tailing method and the turbo-code encoder employing the same and having two recursive systematic convolution encoders. Each recursive systematic convolution encoder comprises M registers, counted from the input side nearest to the block message; the sequence is m 0  register, m 1 , register, . . . , m M−1 , register. After the related data of the block message sequentially had been input, the input of the register m 0  is set and fastened to 0 by using the switch device, and sequentially outputs the data that are temporally stored in all registers, and makes the final state of all registers back to the 0 state. The present invention is applied in the short block length communication system. The error-correcting performance is manifestly excellent. Since the present invention dose not have to check the data temporally stored in the registers. Thus, the encoder structure is simple and regular.

Description:
BACKGROUND OF THE INVENTION  
         [0001]    1. Field of Invention  
           [0002]    The present invention generally relates to a method and system for error control coding, and more particularly, to a turbo-code encoder and a method for the turbo-code block message tailing. Wherein, both of the encoders in the turbo-code encoder have the message tail.  
           [0003]    2. Description of Related Art  
           [0004]    The turbo-code is widely used in the communication system, the computer media storage system or other application system nowadays, such as the CDMA transmission system. As shown in FIG. 1 and FIG. 2, the major reason is the encoding structure of the turbo-code has two convolution code encoders having the same structure encode in parallel. Thus, the receiving end is able to decode the message repeatedly. Therefore, it provides excellent error-correcting capability. The error-correcting capability nears the Shannon limited error-correcting. FIG. 1 schematically shows a conventional turbo-code encoding structure, FIG. 2 schematically shows a conventional turbo-code decoding structure. Please be noted that the turbo-code encoding structure in FIG. 1 comprises two recursive systematic convolution encoders  110 ,  120  (hereafter abbreviated as RSC). Please refer to “Near Shannon limit error-correcting coding and decoding: Turbo-codes (I)”, in Proc. ICC &#39;93, May 1993 proposed by C. Berrou, A. Glavieux and P. Thitimajshima. Since the turbo-code encoding structure mentioned above does not indicate any method for message tailing. Thus, the decoding performance is reduced because the final state of the register can not be obtained.  
           [0005]    A conventional method for turbo-code block message tailing only provides the message tailing for the second encoder, please refer to “Performance evaluation of turbo codes for short frame transmission systems” Electronics letters, vol. 30, pp 111-112, Sept 1994 proposed by P. Jung and M. Na β han. The initial parameters of both decoders are all the same in this method. Wherein, the initial value of the forward recursion α 0 (0)=1, α 0 (m≠0)=0. Wherein, the subscript 0 of α 0  denotes time 0, the 0 in parentheses denotes status m=0, α 0 (0)=1 means the probability of the encoder initial state at time 0 equals to 0 is 1, α 0 (m≠0)=0 denotes the probability of the initial state equals to non-zero is 0. Whereas, the initial value of the backward recursion β N+T (0)=1, β N+T (m≠0)=0. Wherein, β N+T (0)=1 denotes the probability of the encoder final state at time N+T equals to 0 is 1, β N+T (m≠0)=0 denotes the probability of the final state equals to non-zero is 0. Herein, N stands for the block length; T stands for the message tail length, and also denotes the register size.  
           [0006]    Another conventional method for turbo-code block message tailing only provides the message tailing for the first encoder, please refer to “Illuminating the structure of Code and Decoder of Parallel Concatenated Recursive Systematic (Turbo) Codes” in Proc. IEEE GLOBECOM Conf., San Francisco, Calif. pp1298-1303, DEC. 1994 proposed by Patrick Robertson. In this method, the initial parameters of the first decoder, wherein, the initial value of the forward recursion α 0 (0)=1, α 0 (m≠0)=0; whereas, the initial value of the backward recursion β N+T (0)=1, β N+T (m≠0)=0. The initial parameters of the second decoder, wherein, the initial value of the forward recursionα 0 (0)=1, α 0 (m≠0)=0; whereas, the initial value of the backward recursion β N (m)=α N (m). For all state m, herein, N stands for the block length; T stands for the message tail length.  
           [0007]    There is also another method that does not add any message tail after the transmission of the block message is finished. This is the so called “NOTAIL” method. Please refer to “Near Optimum error correcting coding and decoding: Turbo-codes” IEEE Trans. On Commun., Vol. 44, NO. 10. PP. 1261-1271, OCT 1996 proposed by C. Berrou and A. Glavieux, and “Turbo-Code Termination Schemes and A Novel Alternative for Short Frames”. PIMRC. 96. Seventh IEEE International Symposium on Personal Indoor and Mobile Radio Communications, vol.2, Page(s): 354-358, 1996 proposed by Mark C. Reed and Steven S. Pietrobon. The initial parameters of both decoders are all the same when using this method. Wherein, the initial value of the forward recursion α 0 (0)=1, α 0 (m≠0)=0. Whereas, the initial value of the backward recursion β N (m)=1/(2 M ). For all state m, herein, N stands for the block length; 2 M  stands for the summation of all states of the decoding trellis diagram.  
         SUMMARY OF THE INVENTION  
         [0008]    The present invention provides a method for turbo-code block message tailing and the turbo-code encoder employing the same. It provides better error-correcting performance when block length is medium length (N=1024) or short block length (N=256, N=64). Especially when applying in the short block length communication system, the error-correcting performance is manifestly excellent. In addition, since the present invention does not have to check the data stored in the register, the structure of the encoder is simple and regular.  
           [0009]    The present invention provides a turbo-code encoder, receives a small block of the block message, encodes the received block message into the turbo-code and outputs it. The turbo-code encoder at least comprises two RSC encoders, each RSC encoder comprises M registers, counted from the input side nearest to the block message, the sequence is m 0  register, m 1 , register, . . . , m M−1  register. The output of the RSC encoder at time k C k  is denoted as:  
           [0010]    C k =(x k ,y 1k ,y 2k )  
           [0011]    x k =d k   
               y   tk     =       ∑     i   =   0     M                       g   tfi          a     k   -   i                         a   k     =       d   k     +       ∑     i   =   1     M                       g   tbi          a     k   -   i                                         
 
           [0012]    In the equation, t denotes the number of the RSC encoder, wherein t normally can be 1 or 2,  
           [0013]    d k  denotes the input bit at time k,  
           [0014]    k is from 1 to N,  
           [0015]    N stands for the block length of the block message,  
           [0016]    define G tf  is (g tf1 , . . . , g tfM ), stands for the feed-forward generator of the t th  RSC encoder, further defines G tb  is (g tb1 , . . . , g tbM ), stands for the feedback generator of the t th  RSC encoder. The characteristics of the turbo-code encoder according to the present invention are: after all the related data of the block message had been sequentially input into the RSC encoders, the input of the m 0  register of the RSC encoders is set and fastened to 0. And makes the feedback value of the feedback generator of the RSC encoders that is originally feedback to the input terminal of the RSC encoder divert and send to the x k  channel of the RSC encoder. The turbo-code encoder subsequently sends out the message tail.  
           [0017]    According to the preferred embodiment of the present invention. Wherein, the turbo-code encoder further comprises a gate to control the input of the block message. After all the data d k  of each block message had been input, where k is 1 to N, the gate is opened to suspend the input. Moreover, the RSC encoders output the data of all M registers that still stored in the encoders and use them as the message tail. The message tail has 4 times of M bits, they are x 1 ,x 2 ,y 1  and y 2 , each has M bits.  
           [0018]    According to the preferred embodiment of the present invention. Wherein, each RSC encoder further comprises a first switch and a second switch. The output terminal of the first switch is coupled to the input of the m 0  register. The input terminal of the second switch is coupled to the feedback generator. After all the related data of the block message had been sequentially input into the RSC encoders, the output terminal of the first switch diverts and connects to the input terminal of the grounded. Thus, to make the input of the m 0  register of the RSC encoder set and fasten to 0. In addition, the input terminal of the second switch diverts and connects to the output terminal of the x k  channel. Thus, to make the feedback value of the feedback generator of the RSC encoders that is originally feedback to the input terminal of the RSC encoder divert and send to the x k  channel of the RSC encoder.  
           [0019]    According to the preferred embodiment of the present invention. Wherein, the turbo-code encoder further comprises an output switch. The output switch connects to the x 1  channel in the initial state to sequentially output data x 1,k , where k is 1 to N+3. After N+3 clocks, the output switch connects to x 2  channel to sequentially output data X 2,k , where k is from N+1 to N+3.  
           [0020]    According to the preferred embodiment of the present invention. Wherein, the initial value of the RSC encoders forward recursion α 0 (0)=1, α 0 (m≠0)=0. Wherein, the subscript 0 of α 0  denotes time 0, the 0 in parentheses denotes status m=0, α 0 (0)==1 means the probability of the encoder initial state at time 0 equals to 0 is 1, α 0 (m≠0)=0 denotes the probability of the initial state equals to non-zero is 0. Moreover, the initial value of the RSC encoders backward recursion β N+T (0)=1, α N+T (m≠0)=0. Wherein, β N+T (0)=1 denotes the probability of the encoder final state at time N+T equals to 0 is 1, β N+T (m≠0)=0 denotes the probability of the final state equals to non-zero is 0. T stands for the message tail length.  
           [0021]    The present invention further provides a turbo-code encoder. The difference of this encoder from the turbo-code encoder mentioned above is this encoder uses the fast RSC encoder to replace the conventional RSC encoder. The output of these fast RSC encoders at time k Ck is denoted as:  
           [0022]    C k =(x k ,y 1k , y 2k )  
           [0023]    x k =d k   
               y   tk     =       d   k     +       ∑     i   =   1     M                       g   tdi          a     k   -   i                           G     1      d       ≡     1                 ∑     i   =   1     M                     g     1      di         =   1                 ∑     i   =   1     M          (       g     1        b      i         +     g     1      f                 i         )                                     
 
           [0024]    In the equation, ∥ denotes two binary numbers are concatenated together,  
           [0025]    t denotes the number of the fast RSC encoder, wherein t normally can be 1 or 2,  
           [0026]    d k  denotes the input bit at time k,  
           [0027]    k is from 1 to N,  
           [0028]    N stands for the block length of the block message,  
           [0029]    define G td  is (g td1 , . . . , g tdM ), stands for the direct-feed-forward generator of the t th  fast RSC encoder, define G tf  is (g tf1 , . . . , g tfM ), stands for the feed-forward generator of the t th  fast RSC encoder, define G tb  is (g tb1 , . . . , g tbM ), stands for the feedback generator of the t th  fast RSC encoder.  
           [0030]    A method for the turbo-code block message tailing and the turbo-code encoder employing the same according to the present invention, making the final state of the first RSC encoder and the final state of the second RSC encoder converge to the 0 state clearly, and making the initial value of the forward recursion and the initial value of the backward recursion needed for decoding is unique and a known value. Thus, it does not have to check the data temporarily stored in the register, and is able to sequentially output all the data temporarily stored in the registers. Therefore, the decoder is able to obtain the final state of the register, thus, having the excellent error-correcting performance. 
       
    
    
     BRIEF DESCRIPTION OF THE DRAWINGS  
       [0031]    The accompanying drawings are included to provide a further understanding of the invention, and are incorporated in and constitute a part of this specification. The drawings illustrate embodiments of the invention, and together with the description, serve to explain the principles of the invention. In the drawings,  
         [0032]    [0032]FIG. 1 schematically shows a conventional encoding structure of the turbo-code;  
         [0033]    [0033]FIG. 2 schematically shows a conventional decoding structure of the turbo-code;  
         [0034]    [0034]FIG. 3 schematically shows a structure of the recursive systematic convolution encoder applied in the first RSC encoder;  
         [0035]    [0035]FIG. 4 schematically shows a structure of the fast recursive systematic convolution encoder applied in the first RSC encoder;  
         [0036]    [0036]FIG. 5 schematically shows a structure of the recursive systematic convolution encoder having register size M=3;  
         [0037]    [0037]FIG. 6 schematically shows a structure of the fast recursive systematic convolution encoder having register size M=3;  
         [0038]    [0038]FIG. 7 schematically shows the trellis diagram of the encoder having register size M=3;  
         [0039]    [0039]FIG. 8 schematically shows the turbo-code encoder including the message tailing circuit and having register size M=3 of the preferred embodiment according to the present invention;  
         [0040]    [0040]FIG. 9 schematically shows another fast turbo-code encoder including the message tailing circuit and having register size M=3 of the preferred embodiment according to the present invention;  
         [0041]    [0041]FIG. 10 schematically shows the simulation result of the turbo-code encoder according to the present invention, wherein, register size M=3, block length N=1024;  
         [0042]    [0042]FIG. 11 schematically shows the simulation result of the turbo-code encoder according to the present invention, wherein, register size M=3, block length N=256;  
         [0043]    [0043]FIG. 12 schematically shows the simulation result of the turbo-code encoder according to the present invention, wherein, register size M=3, block length N=64. 
     
    
     DESCRIPTION OF THE PREFERRED EMBODIMENTS  
       [0044]    Before describing the method for turbo-code block message tailing and the turbo-code encoder employing the same according to the present invention, the RSC encoder structure must be introduced first. FIG. 3 schematically shows a structure of the recursive systematic convolution encoder applied in the first RSC encoder. Referring to FIG. 3, wherein, the sequence of input bit is denoted as d=(d 1 , d 2 , . . . , d k , . . . , d N ), where d k  is the input bit of the encoder at time k, from 1 to N, and N is the block length. The output of the first encoder at time k is denoted as C k =(x k ,y 1k ). Since the encoder is systematic, so x k =d k . Another parity output is denoted as  
           y     1      k       =       ∑     i   =   0     M            g     1      fi            a     k   -   i             ,                         
 
         [0045]    wherein M stands for the register size. Defining (g 1f1 , . . . , g 1fM ), G 1f  is the feed-forward generator of the first encoder, the element is either 0 or 1. The equation  
         a   k     =       d   k     +       ∑     i   =   1     M                       g     1        b      i              a     k   -   i                                   
 
         [0046]    can be obtained from the encoder. With the same reason, (g 1b1 , . . . , g 1bM )=G 1b  is called as the feedback generator of the first encoder.  
         [0047]    Another invention application corresponding to the present invention proposes a structure of the fast recursive systematic convolution encoder. Referring to FIG. 4, FIG. 4 schematically shows a structure of the fast recursive systematic convolution encoder applied in the first RSC encoder. Wherein, defining:  
         G     1      d       ≡     1                 ∑     i   =   1     M                     g     1      di         =   1                 ∑     i   =   1     M          (       g     1        b      i         +     g     1        f      i           )                               
 
         [0048]    as the direct-feed-forward generator parameter of the first encoder, wherein, represents two binary numbers concatenated together, such as 1∥001=1001.  
         [0049]    Considering the state of the binary RSC code having register size equal to M at time k is S k , so S k =(a k , a k−1 , . . . , a k−M+1 ). It is assumed the initial state of the encoder is the 0 state, that is, S 0 =(0,0 , . . . , 0)=0. In the general convolution code structure, as long as M units of 0 are input at the last, the final state is converged to the 0 state. However, since the RSC encoder is recursive, simply input M units of 0 can not make the final state converged to the 0 state.  
         [0050]    For easy to describe, the turbo-code of the third generation CDMA mobile communication standard is exemplified here. Referring to FIG. 5, FIG. 5 schematically shows a structure of the recursive systematic convolution encoder having register size M=3. Wherein, the register size of the first RSC encoder M=3, and the second encoder is the same as the first encoder. So, g 1bi =g 2bi ≡g bi  and g 1fi =g 2fi ≡g fi . Wherein, the code ratio R=⅓, the feedback generator parameter and the feed-forward generator parameter is G b =1011, G f =1101 respectively. Please refer to FIG. 6 for using (equal) fast RSC encoder structure. FIG. 6 schematically shows a structure of the fast recursive systematic convolution encoder having register size M=3. The feedback generator parameter and the direct-feed-forward generator parameter is G b =1011, G d =1110 respectively.  
         [0051]    [0051]FIG. 7 schematically shows the trellis diagram having register size M=3. Referring to FIG. 7, it is known that the possible conditions that make the final state converge to the 0 state at message tailing are as follows:  
                                                           Time point:   N       N + 1       N + 2       N + 3                   State:   (0,0,0) 0     →   (0,0,0) 0     →   (0,0,0) 0     →   (0,0,0)           (0,0,1) 1     →   (0,0,0) 0     →   (0,0,0) 0     →   (0,0,0)           (0,1,0) 1     →   (0,0,1) 1     →   (0,0,0) 0     →   (0,0,0)           (0,1,1) 0     →   (0,0,1) 1     →   (0,0,0) 0     →   (0,0,0)           (1,0,0) 0     →   (0,1,0) 1     →   (0,0,1) 1     →   (0,0,0)           (1,0,1) 1     →   (0,1,0) 1     →   (0,0,1) 1     →   (0,0,0)           (1,1,0) 1     →   (0,1,1) 0     →   (0,0,1) 1     →   (0,0,0)           (1,1,1) 0     →   (0,1,1) 0     →   (0,0,1) 1     →   (0,0,0)                  
 
         [0052]    Wherein, (x,x,x) 1  denotes S k =(a k ,a k−1 ,a k−2 ) binary state, k is from N to N+3, i is the input value that makes S k+3  back to the 0 state, and N is a block length. One of the major marrows of the method of turbo-code block message tailing according to the present invention is outputting the data still stored in the registers to use as the message tail, and makes the final state converge to the 0 state. Wherein, the message tail has 4 times of M bits, they are x 1 ,x 2 ,y 1  and Y 2  each has M bits.  
         [0053]    [0053]FIG. 8 schematically shows the turbo-code encoder including the message tailing circuit and having register size M=3 of the preferred embodiment according to the present invention. Referring to FIG. 8, the turbo-code encoder of the embodiment is composed of two RSC encoders in parallel. After all block data d k  had been input, k is from 1 to N, the gate  810  is opened to suspend the input. After all block messages had been input into these two RSC encoders, the output terminal of the switch  802  and the switch  804  diverts and connects to the input terminal of the grounded. Since the output terminal of the switch  802  and the switch  804  is coupled to the input terminal of the m 0  register  812 ,  814 , thus, the input of the m 0  register  812 ,  814  of these two RSC encoders is fastened to 0. The input terminal of the switch  806  diverts and connects to the output terminal of the x 1  channel. Moreover, the input terminal of the switch  808  also diverts and connects to the output terminal of the x 2  channel. Therefore, no matter SN is in which state, after 3 clocks, the final register state by all means equals to (0,0,0). Since the output terminal of the switch  802  and the switch  804  diverts and connects to the input terminal of the grounded, the input of the m 0  register  812 ,  814  by all means equals to 0. In addition, the data stored in m 0  register  812 , m 1  register  816 , m 2  register  820  are sequentially output from x 1  channel and y 1  channel. Whereas, the data stored in m 0  register  814 , m 1  register  818 , m 2  register  822  are sequentially output from x 2  channel and y2 channel.  
         [0054]    The switch  830  connects to x 1  channel in the initial state, sequentially outputs data x 1,k , where k is from 1 to N+3, after N+3 clocks, the switch  830  connects to x 2  channel, sequentially outputs data X 2,k , where k is from N+1 to N+3. The message tailing method makes the final state of the first RSC encoder and the second RSC encoder all converge to the 0 state. In other words, the parameter initial state and the parameter final state needed for the first decoder and the second decoder in the receiving side are all the known values. The initial value of the forward recursion α 0 (0)=1, α 0 (m≠0)=0. Wherein, the subscript 0 of α 0  denotes time 0, the 0 in parentheses denotes status m=0, α 0 (0)=1 means the probability of the encoder initial state at time 0 equals to 0 is 1, α 0 (m≠0)=0 denotes the probability of the initial state equals to non-zero is 0. Whereas, the initial value of the backward recursion β N+T (0)=1, β N+T (m≠0)=0. Wherein, β N+T (0)=1 denotes the probability of the encoder final state at time N+T equals to 0 is 1, β N+T (m≠0)=0 denotes the probability of the final state equals to non-zero is 0. T stands for the message tail length. The message tailing method proposed by the present invention clearly makes the final state of the first RSC encoder and the final state of the second RSC encoder converge to the 0 state, and both the initial value of the forward recursion and the initial value of the backward recursion needed for decoding are all the known values. Thus, the method of the present invention can be called as the dual encoder message tailing method.  
         [0055]    [0055]FIG. 9 schematically shows another fast turbo-code encoder including the message tailing circuit and having register size M=3 of the preferred embodiment according to the present invention. The major difference between FIG. 9 and FIG. 8 is the fast turbo-code encoder is used in FIG. 9 to replace the conventional turbo-code encoder. Those who skilled in the related arts should understand the operation method of FIG. 9 by referring to FIG. 8, here will not say more than is needed.  
         [0056]    Although the embodiment mentioned above uses the turbo-code encoder having register size M=3 to explain the operation of the message tailing circuit. Those who skilled in the related arts can readily deduct other turbo-code encoder having different number of the register size M, as long as the marrow of the turbo-code block message tailing method of the present invention is grasped. When the related data of the block message are sequentially input into these RSC encoders, the turbo-code encoder encodes and outputs normally. After all the related data of the block message had been sequentially input into the RSC encoders, the RSC sequentially outputs the data stored in M registers, and makes the final state of these M registers back to the 0 state. This is major accomplished by setting and fastening the input value of the m 0  register of the RSC encoder to 0, and by making the feedback value of the feedback generator of the RSC encoders that is originally feedback to the input terminal of the RSC encoder divert and send to the x k  output channel of the RSC encoder. The turbo-code encoder subsequently sends out the message tail. Wherein, the message tail has 4 times of M bits, they are X 1 ,X 2 ,y 1  and y 2 , each has M bits. The output of the turbo-code encoder connects to the x 1  channel of the first RSC encoder in the initial state to sequentially output data x 1,k , where k is 1 to N+M. After N+M clocks, the output of the turbo-code encoder connects to the x 2  channel of the second RSC encoder to sequentially output data x 2,k , where k is from N+1 to N+M.  
         [0057]    It is known for those who skilled in the related arts that the NOTAIL method is better than other conventional methods in many signal/noise ratio (SNR) intervals. Therefore, the present invention compares the dual encoder message tailing method and the NOTAIL method hereafter. In order to prevent from having too long latency for decoding, the medium or short block length are chosen, they are N=1024, 256 and 64 respectively. Further choosing register size all equal to 3, the code ratio R=⅓, the feedback generator and the feed-forward generator is G f =1101,G d =1110 respectively, the iterative decoding times is 6 times. The random interleaving method is adopted between the first RSC encoder and the second RSC encoder. The simulation results obtained are shown in FIG. 10, FIG. 11 and FIG. 12. They are N=1024, 256 and 64 with different size of block length respectively. The vertical axis in these three diagrams is the decoding performance represented by the bits error rate (BER), the horizontal axis is the communication environment represented by the signal/noise ratio (SNR). As we can see from the diagrams, under the same SNR situation, the bigger the N, the better the decoding performance, this is accorded with the theory.  
         [0058]    [0058]FIG. 10 schematically shows the simulation result of the turbo-code encoder according to the present invention, wherein, register size M=3, block length N=1024. It is known from FIG. 10, the dual encoder message tailing method of the present invention is better than the NOTAIL method. The decoding performance improves about 0.1 dB in BER is 10 −5 . Furthermore, in order to prevent having too long decoding latency, N should not be to long. FIG. 11 schematically shows the simulation result of the turbo-code encoder according to the present invention, wherein, register size M=3, block length N=256. It is known from FIG. 11, the decoding performance improves about 0.2 dB in BER is 10 −5 . The other N that is smaller than this should be chosen. FIG. 12 schematically shows the simulation result of the turbo-code encoder according to the present invention, wherein, register size M=3, block length N=64. It is known from FIG. 12, the decoding performance improvement of the dual encoder message tailing method according to the present invention is further manifest. The decoding performance improves about 0.8 dB in BER is 10 −5 .  
         [0059]    A turbo-code block message tailing method and the turbo-code encoder employing the same according to the present invention, at least have following advantages:  
         [0060]    1. Clearly makes the final state of the first RSC encoder and the final state of the second RSC encoder all converge to the 0 state, and makes the initial value of the backward recursion needed for decoding to be unique and a known value.  
         [0061]    2. Through the observation of the simulation results, no matter the block length is medium or short length, the decoding performance of the dual encoder message tailing method is better than others&#39;. The shorter the block length, the bigger the performance improve. Therefore, it is best suitable for the CDMA mobile communication system that can not tolerate the long decoding latency.  
         [0062]    Although the invention has been described with reference to a particular embodiment thereof, it will be apparent to one of the ordinary skill in the art that modifications to the described embodiment may be made without departing from the spirit of the invention. Accordingly, the scope of the invention will be defined by the attached claims not by the above detailed description.