Abstract:
A method for selecting a signal to noise ratio for a communications code includes obtaining extrinsic information transfer (EXIT) information for a repeat-zigzag Hadamard (RZH) code responsive to a Hadamard order and a signal to noise ratio, determining code parameters for an irregular repeat zigzag Hadamard (IRZH) code for a corresponding code rate in response to the obtained EXIT values, and repeating the step of obtaining the EXIT information for a different signal to noise ratio if the corresponding code rate is other than a selected rate. The corresponding code rate is related to a bit error rate. In a preferred embodiment, the step of obtaining EXIT information includes one of obtaining an EXIT curve for repeat-zigzag Hadamard code by Monte Carlo simulation using serial decoding or obtaining an EXIT function for parallel decoding of the repeat-zigzag Hadamard code by using equations.

Description:
[0001]     This application claims the benefit of U.S. Provisional Application No. 60/806,152, entitled “Code Design Methods for Repeat-Zigzag Hadamard Codes”, filed on Jun. 29, 2006, and U.S. Provisional Application No. 60/806,149, entitled “Low-Complexity High-performance Low-Rate-Code”, filed on Jun. 29, 2006, the contents of both which are incorporated by reference herein. 
     
    
     BACKGROUND OF THE INVENTION  
       [0002]     The present invention relates generally to coding techniques for communications and, more particularly, to code designing for repeat-zigzag Hadamard codes.  
         [0003]     For communication systems operating in the low signal-to-noise ratio (SNR) regime (e.g., code-spread communication systems and power-limited sensor networks), low-rate coding schemes play a critical role. Traditional low-rate channel coding schemes include Hadamard codes and super-orthogonal convolutional codes. These codes offer low coding gain and hence their performance is far away from the ultimate Shannon limit. The ultimate Shannon capacity of an Additive White Gaussian Noise (AWGN) channel in terms of SNR per information bit is about −1.6 dB for codes with rates approaching zero. Turbo-code-based, low-rate concatenated coding schemes have been proposed which offer higher performance but they also incur higher complexities due to the complex trellis structures that specify the codes. The low-density parity-check (LDPC) codes and the repeat-accumulate (RA) codes offer capacity-approaching capability for various code rates when the ensemble profiles are optimized. However, in the low-rate region, they both suffer from significant performance loss and extremely slow convergence with iterative decoding. On the other hand, Hadamard codes have been shown to be a useful tool for improving the code performance in the low-rate region. Constructed from Hadamard code arrays, low-rate turbo-Hadamard codes offer a bit-error-rate (BER) of 10 −5  at a signal to noise ratio E b /N 0 =−1.2 dB, which is only around 0.4 dB away from the Shannon limit. More recently, built on zigzag codes, parallel-concatenated zigzag-Hadamard (PCZH) codes and repeat-zigzag-Hadamard (RZH) codes have been proposed, both of which exhibit much simpler encoder and decoder structures while still offering a similar performance as that of the turbo-Hadamard codes.  
         [0004]     Similar to LDPC codes and RA codes, an RZH code can be represented by its Tanner graph, based on which iterative decoding algorithms can be derived. In two decoding schemes, namely the turbo-like serial decoding and the LDPC-like parallel decoding, it is clear that the parameters of an RZH code need to be chosen carefully for capacity-approaching performance, which leads to the irregular RZH (IRZH) code with optimized degree profile. The exact density evolution method for LDPC code design can be employed for the IRZH code optimization. However, the complexity is extremely high, even for the moderate rate LDPC codes. Density evolution with Gaussian approximation does not work for the design of low-rate RZH codes. Accordingly, there is a need for a design method for low-rate RZH codes.  
       SUMMARY OF THE INVENTION  
       [0005]     In accordance with the invention, there is provided a method to, with a given rate, design the irregular RZH code with minimum signal-to-noise ratio threshold or given a signal-to-noise ratio threshold, design a code ensemble to a maximizing rate. The signal-to-noise ratio threshold means that for any signal-to-noise ratio greater than this threshold, the BER of the code will go to zero or a very small value when the code length is enough long.  
         [0006]     In accordance with an aspect of the invention, a method for selecting a signal to noise ratio for a communications code includes obtaining extrinsic information transfer (EXIT) information for a repeat-zigzag Hadamard (RZH) code responsive to a Hadamard order and a signal to noise ratio, determining code parameters for an irregular repeat zigzag Hadamard (IRZH) code for a corresponding code rate in response to the obtained EXIT values, and repeating the step of obtaining the EXIT information for a different signal to noise ratio if the corresponding code rate is other than a selected rate. In a preferred embodiment, the step of obtaining EXIT information includes one of obtaining an EXIT curve for repeat-zigzag Hadamard code by Monte Carlo simulation using serial decoding or obtaining an EXIT function for parallel decoding of the repeat-zigzag Hadamard code by using equations.  
         [0007]     In yet another aspect of the invention, a method for selecting a signal to noise ratio for a communications code includes choosing a signal to noise ratio, selecting a Hadamard code order, obtaining extrinsic information transfer (EXIT) information for one of a serial decoding and a parallel decoding of a irregular repeat-zigzag Hadamard (IRZH) code responsive to the Hadamard order and the signal to noise ratio, determining a code ensemble for the irregular repeat zigzag Hadamard (IRZH) code for a related bit error rate in response to the obtained EXIT information, and changing the signal to noise ratio for repeated steps of obtaining the EXIT information and determining a code ensemble for a different signal to noise ratio if the related bit error rate is other than a target rate. Preferably, the EXIT information is a curve for the irregular repeat-zigzag Hadamard (IRZH) code obtained by Monte Carlo simulation using the serial decoding and the EXIT information is a function for parallel decoding the irregular repeat-zigzag Hadamard (IRZH) code using equations. 
     
    
     BRIEF DESCRIPTION OF DRAWINGS  
       [0008]     These and other advantages of the invention will be apparent to those of ordinary skill in the art by reference to the following detailed description and the accompanying drawings.  
         [0009]      FIG. 1  is a block diagram of a systematical repeat-zig-zag-Hadamard RZH encoder;  
         [0010]      FIG. 2  is a block diagram unpunctured, zig-zag-Hadamard RZH encoder;  
         [0011]      FIG. 3  is a tanner graph of an unpunctured (n,k) RZH code;  
         [0012]      FIG. 4  is a block diagram of turbo-like decoding of systematic RZH codes;  
         [0013]      FIG. 4A  is a flow chart of the method for code design for serial decoding in accordance with the invention;  
         [0014]      FIG. 5  is a block diagram of parallel decoding of systematic RZH codes;  
         [0015]      FIG. 5A  is a flow chart of the method for code design for parallel decoding in accordance with the invention;  
         [0016]      FIG. 6  is a graph of an extrinsic information transfer function (EXIT) of information bits in BIAWGN channel;  
         [0017]      FIG. 7  is a graph of an EXIT chart of un-punctured RZH codes with r=4 and R c =0.0179 in the case of serial decoding in accordance with the invention;  
         [0018]      FIG. 8  is a graph of bite error rates BERs for un-punctured RZG codes, with an information block length of 65536 and a maximum iteration number of 150, in the case of serial decoding in accordance with the invention;  
         [0019]      FIG. 9  is a graph of an EXIT chart of systematic RZH codes with r=4 and R c =0.05;  
         [0020]      FIG. 10  is a graph of bite error rates BERs for un-punctured IRZH codes, with an information block length of 65536 and a maximum iteration number of 150, in the case of serial decoding in accordance with the invention;  
         [0021]      FIG. 11  is a graph of BER performance of irregular RZH codes over BIAWGN channel, in the case of parallel decoding in accordance with the invention; and  
         [0022]      FIG. 12  is a graph of BER performance of irregular RZH codes over BIAWGN channel, in the case of parallel decoding in accordance with the invention. 
     
    
     DETAILED DESCRIPTION  
       [0023]     The inventive code design considers two decoding schemes, namely the turbo-like serial decoding and the LDPC-like parallel decoding. Parameters of an RZH code need to be chosen carefully for capacity-approaching performance, which leads to the irregular RZH (IRZH) code with optimized degree profile. The invention considers the design methods for IRZH codes. For turbo-like decoding, the extrinsic information transfer function (EXIT) chart technique can be employed to optimize the code profiles. EXIT functions characterize mutual information between the input and output of constituent decoders significantly facilitates performance analysis of iterative coding schemes. The design method for both decoding schemes is based on EXIT function/EXIT chart. One may always get the EXIT by Monte Carlo simulation for both decoding schemes. For parallel decoding, one obtains the EXIT function analytically, i.e., a mathematical formulation. With that one can calculate the EXIT value without using the simulation, which simplifies or reduces the complexity of the code design procedure significantly. Since in this case the inner decoder is a trellis-based zigzag-Hadamard (ZH) decoder, an analytical expression of its EXIT function is not available, and the inventive code design resorts to Monte Carlo simulations to obtain the EXIT functions of the inner code. For LDPC-like parallel decoding, the connection bits of the ZH code are treated as degree-2 variable nodes, and the inner constituent decoder becomes a Hadamard decoder, having the channel observations of the parity bits and the a priori probabilities about the information or connection bits as the input, and the extrinsic information for the information/connection bits as the output. EXIT functions with multiple inputs and outputs are difficult to obtain using Monte Carlo simulations. EXIT functions of Hadamard with multiple inputs and outputs in the context of low-rate RZH codes over BIAWGN channels are derived and applied to the analysis and design of RZH codes. With the EXIT functions, bit error rates (BERs) for a given communication code profile can be estimated and the differential evolution (DE) method can be employed to optimize the degree profile.  
         [0024]     The structure of a systematic, repeat-zigzag-Hadamard RZH code is shown by the diagram  10  in  FIG. 1 . The RZH code is an alternative code structure to parallel concatenated ZH codes and turbo-Hadamard codes. An information bit block  u  of length k is fed out directly on a channel  14  and also encoded by an outer repetition encoder E 1    11  of rate 1/d v  into a codeword  b  of length N=kd v , which is permuted by an interleaver Π,  12  of length N to form  d , then encoded by an inner systematic recursive ZH encoder E 2 ,  13  and out on channel  15 . Since the outer code is a repetition code and the inner ZH code is a systematic code, there are d v  repetitions in the resulting ZH codeword for every information bit. Since a repetition code has no coding gain, it is desirable to transmit the information bits only once. Also notice that the common bit of a ZH segment is the same as the last parity bit of the previous Hadamard segment and hence introduces a degree-2 repetition code. As a consequence, one can puncture the last parity bit and only transmit the common bit. After puncturing, the inner code is a punctured ZH code with which one can obtain the systematic RZH code as shown in  FIG. 1 , with the parity bits  p  being the output of the punctured ZH code. Let n be the length of the ultimate codeword  c ={ u ,  p }, then the overall code is an (n,k) linear block code and the overall coding rate is given by  
                 R   c     =     r         d   v     ⁡     (       2   r     -   r   -   1     )       +   r         ,           (   1   )             
 
 where r is the order of the Hadamard code for the inner encoder. 
 
         [0025]     In case that the inner code has no puncturing, one can have the un-punctured RZH codes output on a single channel  22  whose structure  20  is shown in  FIG. 2 . For the un-punctured code, the overall code rate is given by R c =R 1 R 2 , where R 1 =1/d v  is the rate of the outer repetition code and R 2  is the rate of the inner ZH code  21 . Since normally the first common bit of the ZH code is omitted, the overall rate of the un-punctured RZH code is given by  
               R   c     =       k         (       kd   v     r     )     ⁢     2   r       -   1       =       r         d   v     ⁢     2   r       -     r   /   k         .               (   2   )             
 
 With k→∞, then  
         R   c     -&gt;       r       d   v     ⁢     2   r         .         
 
 When the coding rate is very low, e.g., R c ≦0.01, the performance difference between the punctured one and the un-punctured code is relatively small; whereas in the range around R c =0.05, the punctured code offers a significant coding gain over the un-punctured one due to the elimination of the repetition bits embedded in the inner ZH codes. 
 
         [0026]     A RZH code can be represented by its Tanner graph  30 , as shown in  FIG. 3 , there are three sets of nodes in the Tanner graph of a RZH code: the variable nodes of information bits, corresponding to u, the variable nodes of common bits, corresponding to q, and the Hadamard check nodes, corresponding to the Hadamard code constraints. Note that in  FIG. 3 , the parity bits of Hadamard code words are embedded in their Hadamard check nodes. Those information bits that are repeated d v  times are represented by information bit variable nodes with degree d v , since they participate in d v  Hadamard code constraints, and the common bit variable notes can be viewed as degree-2 information bit variable nodes. Each Hadamard check node is connected to r information bit nodes and to two common bit nodes. The connections between Hadamard check nodes and information bit nodes are determined by the edge interleaver and are highly randomized, whereas the connections between Hadamard check nodes and common bit nodes are arranged in a highly-structured zigzag pattern.  
         [0027]     Based on the Tanner graph, iterative decoding algorithms can be derived. Two belief-propagation (BP) based decoding schemes for RZH codes can be employed. The turbo-like serial decoding  40  depicted in  FIG. 4  and the LDPC-like parallel decoding  50  depicted in  FIG. 5 . Both decoding schemes entail outer repetition decoders  44  and inner serial decoder  41 ,  51  or a Hadamard decoder  51  with interleavers Π −1    42  and Π  43 . Output from the repetition decoders is sent to a decision block  45 , tied to the sink output  46 . In general, the serial decoding takes less iteration number than the parallel one, whereas the latter enjoys the advantage of easy hardware implementation with parallel processing. There is no fundamental difference in terms of bit error rate (BER) performance.  
         [0000]     Design Methods for Turbo-Like Decoding  
         [0028]     The code design of IRZH codes with serial decoding where the outer code is a mixture of repetition codes with different rates is considered. The design approach closely follows those described for RA codes and LDPC codes where the EXIT chart technique is utilized as a design tool. EXIT functions of the component codes and code ensemble optimization are examined.  
         [0000]     EXIT Functions of the Component Codes  
         [0029]     Considering EXIT functions of the component codes, for an (n, k) IRZH codes, the outer code consists of k repetition codes with variable rates. As shown in  FIG. 3 , suppose the rate of the ith repetition code is 1/d v   (i) , the degree of the ith variable node of information bit is d v   (i) . For the outer repetition codes, the EXIT curve is obtained in a similar manner as for RA codes and LDPC codes. Specifically, consider first un-punctured RZH codes. As discussed in Section 3, an information bit variable node of degree d v  has d v  incoming messages from the edge interleaver, and the decoder outputs are given by  
                   L   rep   out     ⁡     (   i   )       =       L   ch     +       ∑     j   ≠   i       ⁢       L   rep   in     ⁡     (   j   )             ,           (   3   )             
 
 where L ch  is the LLR value about the information bit from the channel. For AWGN channel with noise variance  
           σ   2     =       N   0     2       ,       
 
 then  
         L   ch     =       2   ⁢           ⁢     x   u         σ   2           
 
 where x u  is the channel observation of the binary phase shift keying (BPSK) modulated information bit u. L rep   in (j) is modeled as the output LLR of an AWGN channel whose input is the jth interleaver bit transmitted using BPSK. The EXIT function of a degree-d v  variable node is then 
 
 I   E,VND ( I   A,VND   ,d   v )= J (√{square root over (( d   v −1))} J   −1 ( I   ,AVND ))  (4) 
 
 where  
         J   ⁡     (   σ   )       ⁢     =   •     ⁢     1   -       1       2   ⁢           ⁢   π   ⁢           ⁢     σ   2           ⁢       ∫     -   ∞     ∞     ⁢       ⅇ     -         (     ζ   -       σ   2     /   2       )     2       2   ⁢           ⁢     σ   2             ⁢       log   2     ⁡     [     1   +     ⅇ     -   ζ         ]       ⁢       ⅆ   ζ     .                 
 
 Since J(σ) is a monotonically increasing function of σ, it is invertible. 
 
         [0030]     Given the Hadamard code order r, the IRZH design involves specifying the variable node degrees d v   (i) , i=1, 2, . . . , k. Let D be the number of different variable node degrees, and denote these degrees by d v,i , i=1, 2, . . . , D. Then the degree profile of a code can be specified by a polynomial  
         f   ⁡     (   x   )       =       ∑     i   =   1     D     ⁢       a   i     ⁢     x     d     v   ,   i                 
 
 where a i ≧0 is the fraction of nodes having degree d v,i . Note that {a i } must satisfy  
           ∑   i     ⁢     a   i       =   1.       
 
 The average variable node degree is then given by  
           d   _     v     =       ∑     i   =   1     D     ⁢       a   i     ·       d     v   ,   i       .             
 
 Since for  
         k   →   ∞     ,       R   c     =     r         d   _     v     ⁢     2   r           ,       
 
 then  
           d   _     v     =       r       R   c     ⁢     2   r         .         
 
 Let b i  be the fraction of edges incident to variable nodes of degree d v,i . There are (ka i )d v,i  edges involved with such nodes, so then  
               b   i     =           ka   i     ⁢     d     v   ,   i           k   ⁢       d   _     v         =         d     v   ,   i           d   _     v       ·       a   i     .                 (   7   )             
 
 Note that {b i } must satisfy  
           ∑   i             ⁢           ⁢     b   i       =   1.       
 
 It has been shown that the EXIT function of a mixture of codes is an average of the component EXIT functions. With (4), (6) and (7), the effective transfer function of the outer mixture codes is thus given by  
               I     E   ,   VND       =       g   ⁡     (       I     A   ,   VND       ,     R   c     ,   r     )       ⁢           ⁢     (   8   )                           ⁢     =       ∑     i   =   1     D     ⁢           ⁢         b   i     ·       I     E   ,   VND       ⁡     (       I     A   ,   VND       ,     d     v   ,   i         )         ⁢           ⁢     (   9   )                               ⁢     =           R   c     ⁢     2   r       r     ⁢       ∑     i   =   1     D     ⁢       d     v   ,   i       ·     a   i     ·         I     E   ,   VND       ⁡     (       I     A   ,   VND       ,     d     v   ,   i         )       .           ⁢     (   10   )                         
 
 Since g(·) is a monotonically increasing function of I A,VND , it is invertible and then I A,VND =g −1 (I E,VND ,R c ,r). 
 
         [0031]     For systematic RZH codes, an information bit variable node of degree d v  has d v +1 incoming messages: d v  from the edge interleaver and one from the channel. The decoder outputs are given by (3). Then the EXIT function of a degree-d v  variable node is given by  
                 I     E   ,   VND       ⁡     (       I     A   ,   VND       ,     d   v     ,       E   s       N   0         )       =     J   ⁡     (             (       d   v     -   1     )     ⁡     [       J     -   1       ⁡     (     I     A   ,   VND       )       ]       2     +     σ   ch   2         )               (   11   )             
 
 where  
           σ   ch   2     =       4     σ   2       =     8   ·       E   s       N   0             ,       with   ⁢           ⁢       E   s       N   0         =       R   c     ·       E   b       N   0               
 
 being the symbol SNR. For systematic RZH codes, then  
           R   c     =     r           d   _     v     ⁡     (       2   r     -   r   -   1     )       +   r         ,       
 
 hence  
                 d   _     v     =       r         2   r     -   r   -   1     ⁢               ⁢       (       1     R   c       -   1     )     .               (   12   )             
 
 Then with (7), (11) and (12), one can have the effective transfer function of the outer mixture codes as follows  
               I     E   ,   VND       =     g   ⁡     (       I     A   ,   VND       ,       E   s       N   0       ,     R   c     ,   r     )               (   13   )             
 
             =       ∑     i   =   1     D     ⁢           ⁢       b   i     ·       I     E   ,   VND       ⁡     (       I     A   ,   VND       ,     d     v   ,   i       ,       E   s       N   0         )                   (   14   )               =             2   r     -   r   -   1     r     ·       R   c       1   -     R   c           ⁢       ∑     i   =   1     D     ⁢           ⁢       d     v   ,   i       ·     a   i     ·         I     E   ,   VND       ⁡     (       I     A   ,   VND       ,     d     v   ,   i       ,       E   s       N   0         )       .                   (   15   )             
 
 Again, g(·) is invertible, and one can have  
         I     A   ,   VND       =         g     -   1       ⁡     (       I     E   ,   VND       ,       E   s       N   0       ,     R   c     ,   r     )       .         
 
 In order to perform code ensemble optimization, the EXIT transfer function of the inner ZH decoder is needed. In general, there is no closed-form formula, hence the EXIT function is computed by simulation and denoted it by  
               I     E   ,   ZH       =       h   ⁡     (         I     A   ,   ZH       .       E   s       N   0         ,   r     )       .             (   16   )             
 
 Code Ensemble Optimization 
 
         [0032]     In the case of code ensemble optimization, for given r and  
           E   s       N   0       ,       
 
 the optimal IRZH ensemble parameters {a i } that maximize R c  subject to vanishing BER  
           P   b     ⁡     (       E   s       N   0       )       ,       
 
 are solution of the following optimization problem  
                 max   ⁢           ⁢     R   c     ⁢     s   .   t   .       ∑   i             ⁢           ⁢     a   i           =   1     ,       a   i     ≥   0     ,       ∀     i   ⁢           ⁢   and   ⁢           ⁢       P   b     ⁡     (       E   s       N   0       )           =   0.             (   17   )             
 
 EXIT charts can be used to analyze the convergence properties of RA codes and LDPC codes. The same principle can be applied to RZH codes. Specifically, if there is an open tunnel between the EXIT functions of the inner code and outer code for given r and  
           E   s       N   0       ,       
 
 the iterative decoding algorithm can asymptotically converge and then  
           P   b     ⁡     (       E   s       N   0       )       =   0       
 
 with a sufficient large number of iteration. Mathematically, the convergence condition is given by  
                 h   ⁡     (       I     A   ,   ZH       ,       E   s       N   0       ,   r     )       &gt;       g     -   1       ⁡     (       I     A   ,   ZH       ,     R   c     ,   r     )         ,       for   ⁢           ⁢     I     A   ,   ZH         ∈     [     0   ,   1     )       ,           (   18   )             
 
 for un-punctured RZH codes, and  
                 h   ⁡     (       I     A   ,   ZH       ,       E   s       N   0       ,   r     )       &gt;       g     -   1       ⁡     (       I     A   ,   ZH       ,       E   s       N   0       ,     R   c     ,   r     )         ,       for   ⁢             ⁢             ⁢     I     A   ,   ZH         ∈     [     0   ,   1     )       ,           (   19   )             
 
 for systematic codes. With the help of the EXIT chart analysis, one can simplify the above optimization problem by replacing the constraint  
           P   b     ⁡     (       E   s       N   0       )       =   0       
 
 in (17) with condition (18) or (19). To design an IRZH code for a particular rate R c , we simply choose proper Hadamard degree and change  
         E   s       N   0         
 
 in (17) until the resulting optimization result R c *=R c . 
 
 Design Method for LDPC-Like Decoding 
 
         [0033]     The design approach for IRZH codes with parallel decoding closely follows that for irregular LDPC codes using the deferential evolution (DE) technique. During the optimization, the BER for a given code profile has to be estimated, which can be done through mutual information evolution. The mutual information transfer function for the outer repetition code is similar to the case for serial decoding. Hence, obtaining the EXIT functions for Hadamard codes is needed.  
         [0000]     EXIT Functions Hadamard Components  
         [0034]     The EXIT functions for Hadamard codes with multiple inputs on BIAWGN channels are considered. Since it is difficult to directly compute the EXIT functions of the output from the MAP decoder, use is made of a pMAP decoder to derive an approximation for the extrinsic mutual information over binary-input additive white Gaussian noise BIAWGN channels. Basic properties of BIAWGN channel are introduced and the pMAP decoder, with which an approximate expression for the EXIT function over BIAWGN for general linear block codes and Hadamard codes is derived.  
         [0000]     Properties of BIAWGN Channels  
         [0035]     First the BIAWGN channel, its LLR and “soft bit” outputs are characterized. A BIAWGN channel is characterized by its variance σ 2  . Let Y denote the BIAWGN channel observation for a transmitted BPSK modulated bit X, and let  
         L   ⁢   ⁢     log   ⁢       Pr   ⁡     (     X   =       +   1     ❘   Y       )         Pr   ⁡     (     X   =       -   1     ❘   Y       )             ,     
     ⁢     T   ⁢     =   •     ⁢       Pr   ⁡     (     X   =       +   1     ❘   Y       )       -     Pr   ⁡     (     X   =       -   1     ❘   Y       )               
 
 denote the LLR and “soft bit” estimation of X based on the channel observation Y respectively. For a BIAWGN channel one can have  
       L   =           2   ⁢   Y       σ   2       ⁢           ⁢   and   ⁢           ⁢   T     =       tanh   (     L   2     )     .           
 
 Suppose that +1 is transmitted, then (L|X=+1)         N(m, 2m), where  
       m   =       2     σ   2       .         
 
 Hence (T|X=+1) has the following pdf  
                   f       T   ❘   X     =     +   1         ⁡     (   t   )       =       2     1   -     t   2         ⁢       f   L     ⁡     (     ln   ⁢       1   +   t       1   -   t         )           ,           (   20   )             
 
 where f L  denotes the pdf of (L|X=+1). With (20), the (2i)-th moment of (T|X=+1) as a function of m is given by  
                       Φ   i     ⁡     (   m   )       ⁢   ⁢       ⁢   E   ⁢     {         T     2   ⁢   i       ❘   X     =     +   1       }                 =       ⁢       ∫     -   1       +   1       ⁢         2   ⁢     t     2   ⁢   i             (     1   -     t   2       )     ⁢       4   ⁢   π   ⁢           ⁢   m           ⁢     exp   (     -         (       ln   ⁢       1   +   t       1   -   t         -   m     )     2       4   ⁢   m         )     ⁢           ⁢       ⅆ   t     .                       (   21   )             
 
 The mutual information between X and L as a function of m is given by [?]  
                     W   ⁡     (   m   )       ⁢   ⁢       ⁢     I   ⁡     (     X   ;   L     )                       ⁢         ∫   R             ⁢       1       4   ⁢   π   ⁢           ⁢   m         ⁢     exp   ⁡     (     -         (     ℓ   -   m     )     2       4   ⁢   m         )       ⁢           ⁢     (     1   -       log   2     ⁡     (     1   +     ⅇ     -   ℓ         )         )     ⁢     ⅆ   ℓ         ,                   (   22   )             
 
 which is invertible and hence has m=W −1 (I). 
 
 MAP and pMAP Decoders 
 
         [0036]     Now, turning to the output of the MAP decoder and the pMAP decoder. Given an (n,k) linear block code C over GF(2), the dual code C ⊥  is an (n,n−k) linear block code. Let  c   j   ⊥ =[c j,1   ⊥ ,c j,2   ⊥ , . . . ,c j,n   ⊥ ] T  denote the j-th codeword of the (n,n−k) dual code. Denote by I i,1   ⊥ ={j|c j,i   ⊥ =1} the set of indices of all codewords in the dual code with the i-th bit being 1 (or the set of indices of all parity-checks that the i-th bit participates in), and I i,0   ⊥ ={j|c j,i =0} the set of indices of all codewords in the dual code with the i-th bit being 0.  
         [0037]     The extrinsic MAP decoding can be implemented by using the dual code as follows  
                       T     EMAP   ,   i       ⁢   ⁢       ⁢     Pr   ⁡     (       X   i     =     1   ❘       Y   _       [   i   ]           )         -     Pr   ⁡     (       X   i     =       -   1     ❘       Y   _       [   i   ]           )                   =       ⁢           ∑     j   ∈     I     i   ,   1     ⊥                 ⁢           ⁢       ∏       ℓ   =   1     ,     ℓ   ≠   i       n     ⁢           ⁢     T   ℓ     c     j   ,   ℓ     ⊥               ∑     j   ∈     I     j   ,   0     ⊥                 ⁢           ⁢       ∏       ℓ   =   1     ,     ℓ   ≠   j       n     ⁢           ⁢     T   ℓ     c     j   ,   ℓ     ⊥             .                   (   23   )             
 
 Let D EMAP,i  be the extrinsic output of MAP decoder (23) after the following modification  
                       D     EMAP   ,   i       ⁢   ⁢       ⁢   1     +     T     EMAP   ,   i                   =       ⁢     2   ⁢     Pr   ⁡     (       X   i     =     1   ❘       Y   _       [   i   ]           )                     =       ⁢     1   +           ∑     j   ∈     I     i   ,   1     ⊥                 ⁢           ⁢       ∏       ℓ   =   1     ,     ℓ   ≠   j       n     ⁢           ⁢     T   ℓ     c       j   ,   ℓ     ⁢             ⊥               ∑     j   ∈     I     j   ,   0     ⊥                 ⁢           ⁢       ∏       ℓ   =   1     ,     ℓ   ≠   i       n     ⁢           ⁢     T   ℓ     c     j   ,   ℓ     ⊥             .                     (   24   )             
 
 The extrinsic output of a suboptimal decoder which one can call pMAP decoder [?] is defined as  
                 D             ⁢     EpMAP   ,           ⁢   i         ⁢     =   •     ⁢       ∏       SεP   ⁡     (     I     i   ,   1     ⊥     )       ⁢   \   ⁢   ϕ       ⁢       (     1   +       ∏       ℓ   =   1     ,     ℓ   ≠   i       n     ⁢           ⁢     T   ℓ     ⋁     jεS     (     c     j   ,   ℓ     ⊥     )               )         (     -   1     )            S        +   1             ,           (   25   )             
 
 where P(I i,1   ⊥ ) denotes the set of all subsets of I i,1   ⊥  and “         ” denotes logical “or” operation. In what follows, the pMAP decoder is employed to obtain an approximate expression for the EXIT functions of linear block codes over a BIAWGN channel. Since the basic idea is to decompose the EXIT function in the form of a series EXIT functions of multiple single parity-check codes, we will start from the EXIT function of single parity-check codes. 
 
 EXIT Functions for General Linear Block Codes 
 
         [0038]     Note that the goal is to find the extrinsic functions for different bits given that the a priori mutual information from the extrinsic and the communication channels for different bits is different. Keeping this in mind, we first compute the extrinsic information at the output of a single parity-check code.  
         [0039]     Theorem 4.1.  
         [0040]     The extrinsic information of the i-th bit at the output of MAP decoder of an (n,n−1) single parity-check code is given by:  
               I     E   ,   i       =       I   ⁡     (       X   i     ;     T     EMAP   ,   i         )       =       1     ln   ⁢           ⁢   2       ⁢       ∑     j   =   1     ∞     ⁢           ⁢       1       (     2   ⁢           ⁢   j     )     ⁢     (       2   ⁢           ⁢   j     -   1     )         ⁢       (       ∏       ℓ   =   1     ,     ℓ   ≠   i       n     ⁢           ⁢     E   ⁢     {     T   ℓ     2   ⁢   j       }         )     ·                     (   26   )             
 
         [0041]     Proof:  
         [0042]     The dual code of the (n,n−1) single parity-check code is the repetition code of length n. Hence from (23) it follows that  
           T     EMAP   ,   i       =       ∏       ℓ   =   1     ,     ℓ   ≠   i       n     ⁢     T   ℓ         ,       
 
 then using a known proposition 2.6, the extrinsic mutual information of the i-th bit at the output of MAP decoder is given by  
                     I   ⁡     (       X   i     ;     T     EMAP   ,           ⁢   i         )       ⁢           =           ⁢       E             ⁢       T     EMAP   ,           ⁢   i       |       c   _     0           ⁢           ⁢     {       log   2     ⁡     (     1   ⁢           +           ⁢     T     EMAP   ,           ⁢   i         )       }                           ⁢     =           ⁢       E       T     EMAP   ,   i       |       c   _     0         ⁢           ⁢     {           ⁢       log             ⁢   2       ⁢     (     1   ⁢           +       ∏       ℓ   =   1     ,           ⁢     ℓ   ⁢           ≠           ⁢   i                 ⁢   n       ⁢           ⁢     T   ℓ         )       }                     =       1             ⁢     ln   ⁢           ⁢   2         ⁢           ⁢       ∑             ⁢     j   =   1       ∞     ⁢           ⁢       1       (     2   ⁢           ⁢   j     )     ⁢           ⁢     (       2   ⁢           ⁢   j     ⁢           -           ⁢   1     )         ⁢           ⁢   E   ⁢     {           ⁢       ∏       ℓ   =   1     ,           ⁢     ℓ   ≠   i                 ⁢   n       ⁢           ⁢     T   ℓ     2   ⁢   j         }                               ⁢       =           ⁢       1             ⁢     ln   ⁢           ⁢   2         ⁢           ⁢       ∑     j   =   1     ∞     ⁢           ⁢       1       (     2   ⁢           ⁢   j     )     ⁢           ⁢     (       2   ⁢           ⁢   j     -   1     )         ⁢           ⁢     (           ⁢       ∏       ℓ   =   1     ,           ⁢     ℓ   ≠   j                 ⁢   n       ⁢           ⁢     E   ⁢           ⁢     {           ⁢     T   ℓ     2   ⁢           ⁢   j       }         )             ,     ⁢                       
 
 where the last equality holds since the channel is assumed to be memoryless. For the single parity-check codes, pMAP and MAP decoders are identical in any memoryless channel, and the Conjecture 4.1 also states that for other high rate codes, D EMAP ≅D EpMAP  when the all-zero codeword is transmitted over the BIAWGN channel. We have the following result. 
 
         [0043]     Theorem 4.2.  
         [0044]     Let C be an (n,k) linear block code such that in BIAWGN channel D EMAP =D EpMAP . Then the mutual information between X i  and T EMAP,i  is given by  
                 I     E   ,   i     BIAWGN     =       1     ln   ⁢           ⁢   2       ⁢       ∑       SεP   ⁡     (     I     i   ,   1     ⊥     )       ⁢   \   ⁢   ϕ       ⁢           ⁢         (     -   1     )            S        +   1       ⁢       ∑     j   =   1     ∞     ⁢           ⁢       1       (     2   ⁢   j     )     ⁢     (       2   ⁢           ⁢   j     -   1     )         ⁢     (       ∏       ℓε   ⁢           ⁢     V   ⁡     (   S   )         ,     ℓ   ≠   i         ⁢           ⁢       Φ   j     ⁡     (     m   ℓ     )         )                 ,           (   28   )             
 
 where V(S)={l∈{1, . . . ,n}|           j∈S c j,l   ⊥ −1}, and m l =W −1 (I A,l ) where I A,l  is the a priori mutual information about X l  from the channel given X l =+1 is transmitted. 
 
         [0045]     Proof:  
         [0046]     According to a known Theorem and (24), we have  
               I     E   i     BIAWGN     =     I   ⁡     (       X   i     ;     T     EMAP   ,   i         )                   =       E       T     EMAP   ,   i       |       c   _     0         ⁢     {       log   2     ⁡     (     1   +     T     EMAP   ,   i         )       }                   =       E       T     EMAP   ,   i       |       c   _     0         ⁢       {       log   2     ⁡     (     D     EMAP   ,   i       )       }     .                 
 
 Since D EMAP =D EpMAP , we further have  
               I     E   i     BIAWGN     =       E       T     EMAP   ,   i       |       c   _     0         ⁢     {       log   2     ⁡     (     D     EpMAP   ,   i       )       }                   =       E       T   _     |       c   _     0         ⁢     {       log   2     ⁡     (       ∏     S   ⁢           ⁢   ε   ⁢           ⁢       P   ⁡     (     I     i   ,   1     ⊥     )       ⁢   \   ⁢   ϕ         ⁢           ⁢       (     1   +       ∏       ℓ   =   1     ,           ⁢     ℓ   ≠   i                 ⁢   n       ⁢     T   ℓ               ⋁     jεS     (           ⁢     c     j   ,   ℓ     ⊥     )                 )         (     -   1     )       S   |     +   1             )       }                   =       E       T   _     |       c   _     0         ⁢     {       ∑       SεP   ⁡     (     I     i   ,   1     ⊥     )       ⁢   \   ⁢   ϕ       ⁢         (     -   1     )            S        +   1       ⁢       log   2     ⁡     (     1   +       ∏       ℓ   =   1     ,           ⁢     ℓ   ≠   i                 ⁢   n       ⁢     T   ℓ     ⋁     jεS     (     c     j   ,   ℓ     ⊥     )               )           }                 
 
             =       ∑       SεP   ⁢     (     I     i   ,   1     ⊥     )       ⁢   \   ⁢   ϕ       ⁢         (     -   1     )       S   |     +   1         ⁢     E       T   _     |       c   _     0         ⁢       {       log   2     ⁡     (     1   +       ∏       ℓ   =   1     ,           ⁢     ℓ   ≠   i                 ⁢   n       ⁢       T   ℓ       ⋁     jεS   ⁡     (     c     j   ,   ℓ     ⊥     )               )       }     .                 (   29   )             
 
 Define V(S)={l∈{1, . . . ,n}|           j∈S c j,l   ⊥ =1}, then the E{·} term in (29) is the extrinsic information of a (|V(S)|,|V(S)|−1) single parity-check code. Since all-zero codeword is transmitted, according to Theorem 4.5, we have  
             E       T   _     |       c   _     0         ⁢     {       log   2     ⁡     (     1   +       ∏       ℓ   =   1     ,           ⁢     ℓ   ≠   i                 ⁢   n       ⁢       T   ℓ       ⋁     jεS   ⁡     (     c     j   ,   ℓ     ⊥     )               )       }       =       1     ln   ⁢           ⁢   2       ⁢       ∑     j   =   1     ∞     ⁢           ⁢       1       (     2   ⁢   j     )     ⁢     (       2   ⁢   j     -   1     )         ⁢     (       ∏       ℓε   ⁢           ⁢     V   ⁡     (   S   )         ,     ℓ   ≠           ⁢   i         ⁢           ⁢     E   ⁢     {         T   ℓ     2   ⁢           ⁢   j       |     X   ℓ       =     +   1       }         )             ,       
 
 with which (29) becomes  
               I     E   ,   i     BIAWGN     =       ⁢       ∑       SεP   ⁢     (     I     i   ,   1     ⊥     )       ⁢   \   ⁢   ϕ       ⁢         (     -   1     )            S        +   1       ⁢           ⁢     1     ln   ⁢           ⁢   2       ⁢       ∑     j   =   1     ∞     ⁢     1       (     2   ⁢   j     )     ⁢     (       2   ⁢   j     -   1     )                               ⁢     (       ∏       ℓε   ⁢           ⁢     V   ⁡     (   S   )         ,     ℓ   ≠   i         ⁢     E   ⁢     {         T   ℓ     2   ⁢   j       |     X   ℓ       =     +   1       }         )                 =       ⁢       1     ln   ⁢           ⁢   2       ⁢       ∑       SεP   ⁢     (     I     i   ,   1     ⊥     )       ⁢   \   ⁢   ϕ       ⁢         (     -   1     )            S        +   1       ⁢       ∑     j   =   1     ∞     ⁢     1       (     2   ⁢   j     )     ⁢     (       2   ⁢   j     -   1     )                                 ⁢       (       ∏       ℓε   ⁢           ⁢     V   ⁡     (   S   )         ,     ℓ   ≠   1         ⁢       Φ   j     ⁡     (     m   ℓ     )         )     ,               
 
 where m l  is the mean of the “soft bit” estimation passed from the channel to the MAP decoder for X l  given that X=+1 is transmitted. Note that such a BIAWGN channel can either be a communication channel or an extrinsic channel. It is also noted that the EXIT functions in the form of multiple EXIT functions of the same code in BEC channel, cannot be expanded. 
 
         [0047]     For high rate codes, we have D EMP ≅D EpMAP  when the all-zero codeword is transmitted over the BIAWGN channel, and Theorem 4.2 can be used to approximately compute the extrinsic information at the output of the MAP decoder for a linear block code. Note that Hadamard codes are low rate codes. For a low rate code, the extrinsic information can be approximated by 
 
 I   E,i   BIAWGN ( I   A,1   , . . . ,I   A,n )≅1 −I   E,i   ⊥,BIAWGN (1− I   A,1 , . . . ,1− I   A,n ),  (30) 
 
 where I E,i   ⊥,BIAWGN (1−I A,1 , . . . ,1−I A,n ) is the extrinsic information of its high-rate dual code and can be computed by Theorem 4.2 with m l =W −1 (1−I A,l ). 
 
 EXIT Functions for Hadamard Codes over BIAWGN Channel 
 
         [0048]     Next we consider the EXIT functions of Hadamard codes in the context of RZH codes with parallel decoding. We first consider the average mutual information about the information bits  d  which is given by  
           I     E   ,   d     BIAWGN     =       1   r     ⁢       ∑     i   =   1     r     ⁢     I     E   ,     d   i       BIAWGN           ,       
 
 Where I E,d     i     BIAWGN  can be computed by (30). 
 
         [0049]     Let  c   j =[c j,1 ,c j,2 , . . . ,c j,n ] T  denote the j-th codeword of the Hadamard code over GF(2). For  c   j , we have c j,2     i−1     +1 =d j,i  for i=1, . . . ,r. Denote by I i,1   H,d ={j|c j,2     i−1     +1 =1}, for i=1, . . . ,r, the set of indices of all Hadamard codewords with the i-th systematic bit equal 1, and P(I i,1   H,d ) the set of all subsets of I i,1   H,d . Since a Hadamard codeword can be divided into systematic bits, parity bits and connection bits, we have  c   j ={ d   j , p   j,[m] ,q j ,p j,m } where  p   j,[m]  denotes the parity bits exclusive of p j,m . Let S∈P(I i,1   H,d ) . The following definitions will be used:  
               V   ⁡     (     S   ,     d   _       )       ⁢     =   •     ⁢     {         ℓ   ∈     {     1   ,   …   ⁢           ,   r     }       ❘       ⋁     j   ∈   S       ⁢     d     j   ,   ℓ           =   1     }             (   31   )                 V   ⁡     (     S   ,       p   _       [   m   ]         )       ⁢     =   •     ⁢     {         ℓ   ∈     {     1   ,   …   ⁢           ,     m   -   1       }       ❘       ⋁     j   ∈   S       ⁢     p     j   ,   ℓ           =   1     }             (   32   )                 V   ⁡     (     S   ,   q     )       ⁢     =   •     ⁢     {         ℓ   ∈     {   1   }       ❘       ⋁     j   ∈   S       ⁢     q     j   ,   ℓ           =   1     }             (   33   )                 V   ⁡     (     S   ,     p   m       )       ⁢     =   •     ⁢     {         ℓ   ∈     {   m   }       ❘       ⋁     j   ∈   S       ⁢     p     j   ,   ℓ           =   1     }             (   34   )             
 
 where “         ” is the logical “or” operation. It is clear that V(S,q) is either {1} or φ. Further define  
               A     g   ,   h   ,   j   ,   k         d   i     ,   odd       ⁢     =   •     ⁢       ⁢            {     S   ∈     P   ⁡     (     I     i   ,   1       H   ,   d       )              ⁢          V   ⁢     (     S   ,   q     )                              =       ⁢   g     ,          V   ⁢     (     S   ,     d   _       )                          =       ⁢   h     ,          V   ⁢     (     S   ,       p   _       [   m   ]         )                          =       ⁢   j     ,          V   ⁢     (     S   ,     p   m       )                              =       ⁢   k     ,          S        ⁢           ⁢   is   ⁢           ⁢   odd       }                  
     and     
               A     g   ,   h   ,   j   ,   k         d   i     ,   odd       ⁢     =   •     ⁢       ⁢            {     S   ∈     P   ⁡     (     I     i   ,   1       H   ,   d       )              ⁢          V   ⁢     (     S   ,   q     )                              =       ⁢   g     ,          V   ⁢     (     S   ,     d   _       )                          =       ⁢   h     ,          V   ⁢     (     S   ,       p   _       [   m   ]         )                          =       ⁢   j     ,          V   ⁢     (     S   ,     p   m       )                                =       ⁢   k     ,          S        ⁢           ⁢   is   ⁢           ⁢   even       }          .             
 
 Then we have the following results for Hadamard codes that will be subsequently used: 
 
         [0050]     Lemma 4.1.  
         [0051]     For Hadamard codes C with order r, we have  
           A     g   ,   h   ,   j   ,   k         d   1     ,   odd       =       A     g   ,   h   ,   j   ,   k         d   2     ,   odd       =     ⋯   =       A     g   ,   h   ,   j   ,   k         d   r     ,   odd       ⁢     =   •     ⁢     A     g   ,   h   ,   j   ,   k       d   ,   odd               ,     
     ⁢   and       
         A     g   ,   h   ,   j   ,   k         d   1     ,   even       =       A     g   ,   h   ,   j   ,   k         d   2     ,   even       =     ⋯   =       A     g   ,   h   ,   j   ,   k         d   r     ,   even       ⁢     =   •     ⁢       A     g   ,   h   ,   j   ,   k       d   ,   even       .               
 
         [0052]     Proof:  
         [0053]     Since A g,h,j,k   d     l     ,odd  and A g,h,j,k   d,     l     even  are based on the subcode C i ={ c   j |c j,2     i−1     +1 =1, c   j ∈C}, i=1, . . . ,r, we only need to show that for l≠i, there is a C l * which is constructed from C l  by only switching coded bits within the systematic bit positions and/or the parity bit positions, such that C i =C 1 *. Let the generation matrix of C in systematic form be  G   H,r  with  g   0  and  g   i  (i=1, . . . ,r) being the rows of  G   H,r  corresponding to the connection bit and the i-th information bit, respectively. Suppose that the input of the Hadamard encoder is  d =[d 0 =q,d 1 , . . . ,d r ] T , then the codewords belong to C i  are given by  
       {         g   _     i   T     +       ∑     ℓ   ≠   i       ⁢       d   ℓ     ⁢       g   _     ℓ   T           }       
 
 for all possible {d l } l≠i . Since  G   H,r  is in systematic form,  g   i  can be written as [ u   i , p   i ] where  u   i =[u 0 ,u 1 , . . . ,u r ] with u l =0 for l≠i and u i =1. By switching the rows  g   i  and  g   l , we obtain  G   H,r   (1)  with  g   (1) = g   l  and  g   l   (1) = g   i . It is clear that the subcode C i   (1)  generated by  G   H,r   (1)  is identical to C i . We further construct  G   H,r   (2)  from  G   H,r   (1)  by letting ( g   i   (2) = g   i   (1) +( g   l   (1) + g   i   (1) )= g   l   (1) = g   i , and  g   l   (2) = g   l   (1) +( g   l   (1) + g   i   (1) )= g   i   (1) = g   l , by which we have  G   H,r   (2) = G   H,r   (1)  and hence C i   (2) =C i . The effect of transforming  G   H,r   (1)  to  G   H,r   (2)  is only to change the order of the coded bits. Since both codes are systematic codes, there is one order change between systematic bit position i and l (note that there are only two l&#39;s in  u   i + u   l ), and all the other changes are happened between parity bit positions. It is clear that C i   (2) =C i  is the ·C l * we are looking for and this concludes the proof. 
 
         [0054]     In case that the size of the code book is not huge, it is easy to compute A g,h,j,k   d,even  and A g,h,j,k   d,odd  directly from their definitions given the codewords are known. With the above results, the average mutual information about the information bits  d  can be computed by the following result.  
         [0055]     Theorem 4.3.  
         [0056]     If the extrinsic and communication channels are AWGN channels with respective mutual information I A,d , I A,p , I A,q  and I A,p     m   , we have  
               I     E   ,   d     BIAWGN     ≅     1   -       1     ln   ⁢           ⁢   2       ⁢       ∑     g   =   0     1     ⁢       ∑     h   =   0     r     ⁢       ∑     j   =   0       m   -   1       ⁢       ∑     k   =   0     1     ⁢       (             A     g   ,   h   ,   j   ,   k       d   ,   odd       -               A     g   ,   h   ,   j   ,   k       d   ,   even             )     ⁢       ∑     i   =   1     ∞     ⁢       1       (     2   ⁢           ⁢   i     )     ⁢     (       2   ⁢   i     -   1     )         .                                                   Φ   i   g     ⁡     (     m   q     )       ⁢       Φ   i   h     ⁡     (     m   d     )       ⁢       Φ   i   j     ⁡     (     m   p     )       ⁢       Φ   i   k     ⁡     (     m     p   m       )         ,           (   35   )             
 
 where m q =W −1 (1−I A,q ), m d =W −1 (1−I A,d ), m p =W −1 (1−I A,p ) and M p     m   =W −1 (1−I A,P     m   ). Note that here for simplicity, I A,p     m    denotes the overall mutual information about p m  from both the communication channel and the extrinsic channel. 
 
         [0057]     Proof:  
         [0058]     Using Theorem 4.2, (30) and Theorem 4.1, we obtain the above result. Now consider the connection bit q. Similarly, we denote by I 1   H,q ={j|c j,1 =1} the set of indices of all Hadamard codewords with the connection bit equal 1, and P(I 1   H,q ) the set of all subsets of I 1   H,q . Let S∈P(I 1   H,q ), then we can obtain V(S, d ), V(S, p   [m] ), and V(S, p m ) as in (31), (32) and (34). Define  
               A     h   ,   j   ,   k       q   ,   odd       ⁢     =   •     ⁢       ⁢            {     S   ∈     P   ⁡     (     I   1     H   ,   d       )              ⁢          V   ⁡     (     S   ,     d   _       )                              =       ⁢   h     ,          V   ⁢     (     S   ,       p   _       [   m   ]         )                          =       ⁢   j     ,          V   ⁢     (     S   ,     p   m       )                              =       ⁢   k     ,          S        ⁢           ⁢   is   ⁢           ⁢   odd       }                  
     and     
               A     h   ,   j   ,   k       q   ,   odd       ⁢     =   •     ⁢       ⁢            {     S   ∈     P   ⁡     (     I   1     H   ,   d       )              ⁢          V   ⁡     (     S   ,     d   _       )                              =       ⁢   h     ,          V   ⁢     (     S   ,       p   _       [   m   ]         )                          =       ⁢   j     ,          V   ⁢     (     S   ,     p   m       )                                =       ⁢   k     ,          S        ⁢           ⁢   is   ⁢           ⁢   even       }          .             
 
 Then similar to Theorem 4.3, the mutual information of q can be computed by the following result. 
 
         [0059]     Theorem 4.4.  
         [0060]     If the extrinsic and communication channels are AWGN channels with respective mutual information I A,d , I A,p  and I A,p     m   , then we have  
                 I     E   ,   q     BIAWGN     ≅     1   -       1     ln   ⁢           ⁢   2       ⁢       ∑     h   =   0     r     ⁢       ∑     j   =   0       m   -   1       ⁢       ∑     k   =   0     1     ⁢       (       A     h   ,   j   ,   k       d   ,   odd       -     A     h   ,   j   ,   k       d   ,   even         )     ⁢       ∑     i   =   1     ∞     ⁢         1       (     2   ⁢   i     )     ⁢     (       2   ⁢   i     -   1     )         .     
     ⁢       Φ   i   h     ⁡     (     m   d     )         ⁢       Φ   i   j     ⁡     (     m   p     )       ⁢       Φ   i   k     ⁡     (     m     p   m       )                         ,           (   36   )             
 
 where m d =W −1 (1−I A,d ), m p =W −1 (1−I A,p ) and m p     m   =W −1 (1−I A,p     m   ). Again, here I A,p     m    represents the overall mutual information about p m  from both the communication channel and the extrinsic channel. 
 
         [0061]     Now consider the last parity bit p m . Since  p   m  has a channel observation y m , the EXIT function of the last parity bit p m  is different from that of q. Again, let C* be a new code formed by all pairs ( d ,  p , q, p m ) , then we can define I 1   H,p     m   ={j|p j,m =1} the set of indices of all codewords in C* with p j,m  equal 1, and P(I 1   H,p     m   ) the set of all subsets of I 1   H,p     m   . Let S∈P(I 1   H,p     m   ), then similar to the case for q, we can obtain V(S,q), V(S, d ), and V(S, p ), with which we can define  
               A     g   ,   h   ,   j         p   m     ,   odd       ⁢     =   •     ⁢       ⁢            {     S   ∈     P   ⁡     (     I   1     H   ,     p   m         )              ⁢          V   ⁢     (     S   ,   q     )                              =       ⁢   g     ,          V   ⁢     (     S   ,     d   _       )                          =       ⁢   h     ,          V   ⁡     (     S   ,     p   _       )                              =       ⁢   j     ,          S        ⁢           ⁢   is   ⁢           ⁢   odd       }                  
     and     
               A     g   ,   h   ,   j         p   m     ,   odd       ⁢     =   •     ⁢       ⁢            {     S   ∈     P   ⁡     (     I   1     H   ,     p   m         )              ⁢          V   ⁢     (     S   ,   q     )                              =       ⁢   g     ,          V   ⁢     (     S   ,     d   _       )                          =       ⁢   h     ,          V   ⁡     (     S   ,     p   _       )                                =       ⁢   j     ,          S        ⁢           ⁢   is   ⁢           ⁢   even       }          .             
 
 by which we can compute the EXIT function for p m  as follows. 
 
         [0062]     Theorem 4.5.  
         [0063]     If the extrinsic and communication channels are AWGN channels with respective mutual information I A,q , I A,d  and I A,p , then we have  
                 I     E   ,     p   m       BIAWGN     ≅     1   -       1     ln   ⁢           ⁢   2       ⁢       ∑     g   =   0     1     ⁢       ∑     h   =   0     r     ⁢       ∑     j   =   0     m     ⁢       (             A     g   ,   h   ,   j         p   m     ,   odd       -               A     g   ,   h   ,   j         p   m     ,   even             )     ⁢       ∑     i   =   1     ∞     ⁢         1       (     2   ⁢   i     )     ⁢     (       2   ⁢   i     -   1     )         .     
     ⁢       Φ   i   g     ⁡     (     m   q     )         ⁢       Φ   i   h     ⁡     (     m   d     )       ⁢       Φ   i   j     ⁡     (     m   p     )                         ,           (   37   )             
 
 where m q =W −1 (1−I A,q ), m d =W −1 (1−I A,d ) and m p =W −1 (1−I A,p ). 
 
       Numerical Example  
       [0064]     The following example demonstrates the computing of EXIT functions for Hadamard codes.  
       Example 1  
       [0065]     Consider a Hadamard code with r=4. The code book of C can be easily obtained, from which we are able to obtain A g,h,j,k   d,even  and A g,h,j,k   d,odd . Let I A,p =0.01, and I A,q =I A,p     m   ,=I A,d , then the EXIT function of the information bits has only one variable I A,d , and we are able to obtain I E,d  as a function of I A,d  by using Theorem 4.3 which is plotted  600  in  FIG. 6 . Also depicted in  FIG. 6  are the simulated EXIT curve with the same setting. It is seen that the EXIT function over BIAWGN channel provides an optimistic estimation of the simulated one.  
         [0000]     BER Estimation of RZH Codes with Parallel Decoding  
         [0066]     For an (n,k) IRZH codes, the outer code consists of k repetition codes with variable rates and the EXIT functions of repetition decoders are identical to the case where the serial decoding is employed. Also, since the connection bit nodes are viewed as variable nodes with degree 2, the corresponding EXIT functions for q and p m  are simply the EXIT functions for rate ½ repetition code without message from the channel. Now we have both the EXIT functions of the outer repetition decoder and the inner Hadamard decoder, we can then trace the mutual information exchanged between the two constituent components for a given degree profile and calculate the corresponding BER after a given number of iterations as in [?], with which we are able to perform degree profile optimization by using differential evolution (DE).  
         [0067]     Specifically, let I ch  be the mutual information about the LLRs of the coded bits transmitted from the communication channel. For a BIAWGN channel with  
             E   s       N   0       =       R   c     ·       E   b       N   0           ,       we   ⁢           ⁢   have   ⁢           ⁢     I   ch       =       W   ⁡     (     2   ⁢     σ   ch   2       )       =       W   ⁡     (       16   ⁢     E   s         N   0       )       .             
 
 Also let I A,a   H , I A,q   H , I A,p     m     H  be the mutual information about the a priori LLRs passing from the repetition decoder to the Hadamard decoder (the extrinsic channels) for the information bits, connection bit and the last parity bit, respectively, which are initialized to zero for the first iteration. With I ch , I A,a   H , I A,q   H  and I A,p     m     H , as the inputs, we are able to compute the output mutual information I E,a   H , I E,q   H  and I E,p     m     H  of the Hadamard decoder with the previously derived EXIT functions in BIAWGN channels. For BIAWGN channels, the mean of the “soft output” of the extrinsic channel is computed by m=W −1 (I A ). The output mutual information of the Hadamard decoder will then serve as the input I A,VND  for the EXIT functions of the corresponding repetition decoder, which will produce the corresponding I E,VND  and feed back to the EXIT functions of the Hadamard decoder as the new inputs for the next iteration. After a given number of iteration, the mutual information passed to the outer repetition decoder is I A,VND , then the BER is given by  
                 P   b     =       ∑     i   =   1     D     ⁢           ⁢       a   i     ⁢     Q   ⁡     (         1   2     ⁢     W   ⁡     (       1   2     ⁢     (       2   ⁢     d   v     ⁢       W     -   1       ⁡     (     I     A   ,   VND       )         +     σ   ch   2       )       )           )             ,           (   38   )             
 
 where  
           Q   ⁡     (   x   )       ⁢     ⁢     =   •     ⁢       1       2   ⁢   π         ⁢       ∫     -   ∞     x     ⁢       exp   ⁡     (       -     t   2       /   2     )       ⁢           ⁢       ⅆ   t     .               
 
 Code Ensemble Optimization 
 
         [0068]     For given r and R c , the optimal IRZH ensemble parameters {a i } are the one that minimize E b /N 0 , subject to a vanishing BER P b . In practice, the vanishing BER condition is often replaced by a BER threshold ε for a given iteration number N it , i.e., P b (N it )&lt;ε, which leads to the following optimization problem  
                 min   ⁢           ⁢       E   b     /     N   0       ⁢           ⁢     s   .   t   .       ∑   i             ⁢           ⁢     a   i           =   1     ,       a   i     ≥   0     ,     ∀       i   ⁢           ⁢   and   ⁢           ⁢       P   b     ⁡     (     N   it     )         &lt;     ɛ   .                 (   39   )             
 
 To solve (17) for irregular RZH codes with parallel decoding, we resort to the differential evolution (DE) algorithm, which is a powerful population-based genetic algorithm and was introduced for finding the optimal degree profile of the irregular LDPC codes. The essential idea behind DE is a self-organizing scheme to generate a trial parameter vector (which is {a i } in our case) by adding the weighted difference between two population vectors of the current generation to a third vector which is the target vector. If the trial vector has a smaller cost value (which is P b  in our case and can be estimated by using the EXIT functions of the component codes as discussed in Section 1) than the target vector, it survives into the next generation of the evolution. After a given number of evolutions, the vector with the smallest cost value among the population of current generation is the optimized parameter vector. Note that although there is no mathematical convergence proof of DE, it is believed to be a simple and reliable global optimization method. To find the solution to (17) for given R c  and r, we first choose an E b /N 0  and find a degree profile {a i } using DE that satisfies the BER constraint ε. If at least one {a i } exists, the E b /N 0  is reduced and the procedure is repeated until no such a vector {a i } exists. The smallest value of E b /N 0  for which a power profile {a i } satisfies the BER constraint is the desired minimum SNR and the corresponding {a i } is the optimized degree profile. 
 
 Numerical Results 
 
         [0069]     The following are several examples for RZH code optimization with the previously proposed design methods.  
       Examples with Serial Decoding  
       [0070]     An un-punctured regular RZH code with r=4 and d v =14 which results in a coding rate of around 0.018.  FIG. 7  plots the EXIT chart of this code, from which it can be seen that the corresponding SNR threshold is around −0.05 dB. Now consider the irregular code with  d   v =14. With code ensemble optimization, we are able to obtain an irregular code at  
           E   b       N   0       =       -   0.98     ⁢           ⁢   dB         
 
 where the degree profile polynomial is given by f(x)=0.323x 3 +0.175x 8 +0.026x 22 +0.476x 23 . The corresponding EXIT chart for  
         E   b       N   0         
 
 −0.98 dB is also plotted  700  in  FIG. 7 , where the solid line denotes the EXIT function of the outer mixture repetition codes with the optimized profile and diamond denotes the EXIT function of the inner ZH code. 
 
         [0071]     The graph  800  of  FIG. 8  plots the simulated BER results of the regular and irregular un-punctured RZH codes with an information block length of 65536 and a maximum iteration number of 150. It is seen that with r=4, the optimized un-punctured IRZH code has a gain of 0.71 dB (measured at P b =10 −4 ) over the regular code, whereas the gap to the capacity is around 0.8 dB. With larger r, better codes can be obtained. For instance, for r=6, we obtain a code which is optimized at  
           E   b       N   0       =       -   1.30     ⁢           ⁢   dB         
 
 with f(x)=0.363x 3 +0.338x 6 +0.299x 7 , and the simulated threshold (measured at P b =10 −4 ) is −1.13 dB, which is only 0.41 dB away from the capacity. 
 
         [0072]     Next is the ensemble optimization of the systematic IRZH codes. Since the repetition bits are punctured, much better performance can be expected. Indeed, for r=4 and R c =0.05, we are able to obtain an irregular code at  
           E   b       N   0       =       -   1.34     ⁢           ⁢   dB         
 
 with f(x)=0.467x 3 +0.375x 10 +0.158x 11 , which is only 0.1 dB away from the capacity. The EXIT chart of the curve-fitting result  900  is shown in  FIG. 9  and the BER performance is shown  1001  in  FIG. 10 . Results show that the simulated SNR threshold is −1.14 dB (only around 0.31 dB away from the capacity) which is much better than that of the optimized un-punctured code with the same r and a much lower (0.0179) coding rate. The graph  1001  of  FIG. 10  also depicts the BER performance of a lower rate code with r=4 and R c =0.018 which is optimized at  
           E   b       N   0       =       -   1.42     ⁢           ⁢   dB         
 
 with f(x)=0.364x 3 +0.014x 11 +0.192x 12 +0.074x 13 +0.095x 36 +0.136x 37 +0.1087x 38 +0.004x 39 +0.013x 200 , and the simulated SNR threshold is around −1.2 dB, which is 0.34 dB away from the capacity and around 0.8 dB better than the same rate un-punctured code with r=6. With r=6, a code is optimized at  
           E   b       N   0       =       -   1.43     ⁢           ⁢   dB         
 
 with f(x)=0.401x 3 +0.573x 7 +0.026x 20 , and the simulated SNR threshold is −1.24 dB, which is slightly better than that of r=4. 
 
       Examples with Parallel Decoding  
       [0073]     Next some design examples of IRZH codes with parallel decoding are provided. First the performance of the regular code with parallel decoding is considered. Consider a regular systematic RZH code with r=4 and  d   v =7 which corresponds to a rate of 0.0494. The graph  110  of  FIG. 11  depicts the simulated BER performance of this code. The simulated SNR threshold (measured at P b =10 −4 ) is around −0.66 dB which is 0.78 dB away from the Shannon capacity −1.44 dB. To obtain better performance, we resort to irregular codes. For the code design, we set the BER threshold ε=10 −4 . With AWGN EXIT function, we are able to optimize a code at −1.25 dB with f(x)=0.4353x 3 +0.0072x 4 +0.0016x 5 +0.0099x 8 +0.1759x 9 +0.1829x 10 +0.0800x 11 +0.1071x 12 , which is only 0.19 dB away from the capacity. The simulated SNR threshold for this code is −1.15 dB, which is only 0.29 dB away from the capacity and has a gain of 0.49 dB over the regular one. Next we provide another example of code design using EXIT functions over BIAWGN channel.  
       Example  
       [0074]     By setting r=4 and  d   v =8, the systematic RZH code has a rate of 0.0435. The Shannon limit for this code is −1.46 dB. Again, with EXIT functions over BIAWGN channel, we are able to optimize a code at −1.34 dB with f(x)=0.4044x 3 +0.0026x 4 +0.0048x 5 +0.0245x 6 +0.0453x 8 +0.0669x 9 +0.0296x 10 +0.0203x 11 +0.0985x 12 +0.3030x 13 , which is only 0.12 dB away from the capacity. BER performance of this code is depicted  120  in  FIG. 12 . It is seen that the simulated SNR threshold for this code is −1.2 dB, which is only 0.26 dB away from the capacity and 0.4 dB away from the ultimate Shannon limit. It is seen that the proposed EXIT functions in AWGN channel are a good approximation in the considered rate region and can be served as a practical tool for the low-rate IRZH code design.  
         [0075]     The method for code design for IRZH codes is detailed by flow chart  40 A in  FIG. 4A  for serial decoding and flow chart  50 A in  FIG. 5A  for parallel decoding. The method is a mutual-information-based code design for both the serial and parallel decoding schemes.  
         [0000]     Design for Serial Decoding  
         [0076]     The decoding of RZH code is based on its tanner graph  30  which is depicted in  FIG. 3 . For turbo-like serial decoding, the inner decoder utilizes the trellis structure of the zigzag-Hadamard code and the common bits participate in the two-way decoding of ZH codes. Extrinsic information about the information bits is exchanged between the inner ZH decoder and outer repetition decoder, see  FIG. 4 .  
         [0077]     Chart  40 A details the steps for IRZH code design for serial decoding. Step  1 : a small signal to noise ratio Es/N 0  is initially chosen  42 A. Step  2 : for a given Hadamard order r and Es/N 0 , the EXIT curve for ZH code is obtained by Monte Carlo simulation using serial decoding  43 A. Step  3 : with the obtained EXIT curve there is an attempt to find the optimal IRZH ensemble parameters {a i } that maximize coding rate subject to vanishing BER by solving the following optimization problem  
           max   ⁢           ⁢     R   c     ⁢           ⁢     s   .   t   .       ∑   i     ⁢           ⁢     a   i           =   1     ,       a   i     ≥   0     ,       ∀     i   ⁢           ⁢   and   ⁢           ⁢       P   b     ⁡     (       E   s     /     N   0       )           =   0.         
 
 This problem can be solved by any linear optimization program  44 A. The vanishing BER condition can be implemented by checking the existence of a decoding tunnel between the EXIT curve of the ZH code obtained in step  2  and that of outer repetition codes. Namely, the curve defined by a particular degree profile lies below the EXIT curve of ZH code in the EXIT chart. Step  4 : if the maximum rate obtained by step  3  is smaller than the target rate, the signal to noise ratio Es/N 0  is increased by a small amount and step  2  and  3  are repeated, until the obtained achievable rate equals to the target rate  45 A. 
 
 Design for Parallel Decoding 
 
         [0078]     As in  FIG. 3 , depicting the Tanner graph  30  of RZH codes, for LDPC-like parallel decoding the variable nodes of common bits are viewed as degree-2 information bit nodes and extrinsic LLRs about information bits and common bits are parallel exchanged between the outer repetition decoder and inner Hadamard decoder.  
         [0079]     Chart  50 A details the steps for IRZH code design for parallel decoding. Step  1 : a relatively large signal to noise ratio SNR E b /N 0  is initially chosen  52 A. Step  2 : for a given Hadamard order r coding rate R c  and SNR, a degree profile that has minimum BER by using deferential evolution (DE) is found  53 A. During the DE optimization, BER is computed, which can be done by a mutual information tracking scheme. EXIT functions of the Hadamard codes in AWGN channel are derived, with which the BER can be easily estimated  54 A. Specifically, the EXIT functions for the information bits are given by:  
           I     E   ,   d     BIAWGN     ≅     1   -       1     ln   ⁢           ⁢   2       ⁢       ∑     g   =   0     1     ⁢           ⁢       ∑     h   =   0     r     ⁢           ⁢       ∑     j   =   0       m   -   1       ⁢           ⁢       ∑     k   =   0     1     ⁢           ⁢       (       A     g   ,   h   ,   j   ,   k       d   ,   odd       -     A     g   ,   h   ,   j   ,   k       d   ,   even         )     ⁢       ∑     i   =   1     ∞     ⁢           ⁢         1       (     2   ⁢   i     )     ⁢     (       2   ⁢   i     -   1     )         ·       Φ   i   g     ⁡     (     m   q     )         ⁢       Φ   i   h     ⁡     (     m   d     )       ⁢       Φ   i   j     ⁡     (     m   p     )       ⁢       Φ   i   k     ⁡     (     m     p   m       )                           ,       
 
 similarly, the EXIT function for the connection bits can be computed by  
           I     E   ,   q     BIAWGN     ≅     1   -       1     ln   ⁢           ⁢   2       ⁢           ⁢       ∑     h   =   0     r     ⁢           ⁢       ∑     j   =   0       m   -   1       ⁢           ⁢       ∑     k   =   0     1     ⁢           ⁢       (       A     h   ,   j   ,   k       d   ,   odd       -     A     h   ,   j   ,   k       d   ,   even         )     ⁢       ∑     i   =   1     ∞     ⁢           ⁢         1       (     2   ⁢   i     )     ⁢     (       2   ⁢   i     -   1     )         ·       Φ   i   h     ⁡     (     m   d     )         ⁢       Φ   i   j     ⁡     (     m   p     )       ⁢       Φ   i   k     ⁡     (     m     p   m       )                         ,       
 
 and the EXIT function for the last parity bit is given by  
           I     E   ,     p   m       BIAWGN     ≅     1   -       1     ln   ⁢           ⁢   2       ⁢       ∑     g   =   0     1     ⁢           ⁢       ∑     h   =   0     r     ⁢           ⁢       ∑     j   =   0     m     ⁢           ⁢       (       A     g   ,   h   ,   j         p   m     ,   odd       -     A     g   ,   h   ,   j         p   m     ,   even         )     ⁢       ∑     i   =   1     ∞     ⁢           ⁢         1       (     2   ⁢   i     )     ⁢     (       2   ⁢   i     -   1     )         ·       Φ   i   g     ⁡     (     m   q     )         ⁢       Φ   i   h     ⁡     (     m   d     )       ⁢       Φ   i   j     ⁡     (     m   p     )                         ,       
 
 where the details of the variables in the above equations are explained elsewhere herein. Step  4 : if the minimum BER obtained by step  2  is smaller than the target BER requirement, the signal to noise ratio SNR E b /N 0  is reduced and step  2  is repeated, until the target BER requirement cannot be achieved  55 A. The least SNR that can still achieve the BER requirement is the minimum SNR and the corresponding degree profile is the optimized degree profile. 
 
         [0080]     In summary, the present code design method is optimized for IRZH codes with serial and parallel decoding schemes. For serial decoding, the EXIT functions are obtained via simulation; on the other hand, for parallel decoding, the EXIT functions of Hadamard codes in the context of RZH codes are derived. With these EXIT functions, BERs for a given code profile can be easily estimated and either curve fitting (for serial decoding) or differential evolution (DE) technique (for parallel decoding) can be employed to optimize the degree profile for the given design parameters, e.g., the coding rate and the Hadamard order. The techniques introduced in this report can also be easily extended to the design of general low-density parity-check codes where the check nodes are replaced by other linear block codes, e.g., Hadamard codes or Hamming codes.  
         [0081]     The present code design method for irregular repeat-zigzag-Hadamard (IRZH) codes to approach capacity with turbo-like serial decoding or LDPC-like parallel decoding is quite different from current techniques and provides significant advantages. With respect to current design methods for LDPC codes, a check node of a LDPC code is a single parity-check constraint. The design procedure for LDPC codes is similar to that of IRZH codes with parallel decoding. The difference is that with the present method it is a common practice to use the analytical EXIT function of the inner check node over BEC to approximate that over BIAWGN channel. Results show that such an approximation works very well for irregular LDPC code design. However, such a BEC approximation design method provides less satisfactory results for RZH code design with parallel decoding. For instance, for r=4 and d v =7, with BEC approximation, one is able to design an IRZH code with a simulated SNR threshold of −0.79 dB, whereas with the present method EXIT functions derived for AWGN channel, one can obtain a code with a simulated SNR threshold of −1.15 dB, which is only 0.29 dB away from the capacity. With respect to current design methods for LDPC-Hadamard codes, the EXIT functions of the Hadamard check nodes are obtained by Monte Carlo simulation, consequently, the optimization procedure is time-consuming. With the present design method based on the analytical EXIT functions, the optimization complexity can be significantly reduced.  
         [0082]     The present EXIT-function-based design method offers high quality design results whereas the optimization complexity is low. Note that although density-evolution can be used for the design of IRZH code, the complexity is very high.  
         [0083]     Although with the present turbo-like decoding, in which the inner decoder is a trellis-based zigzag-Hadamard (ZH) decoder, an analytical expression of its EXIT function is not available and there is use of Monte Carlo simulations to obtain the EXIT functions of the inner code, since the EXIT function of the inner code is a one dimension function for a given SNR the optimization complexity is still low.  
         [0084]     For LDPC-like parallel decoding, the connection bits of the ZH code are treated as degree-2 variable nodes, and the inner constituent decoder becomes a Hadamard decoder. Although simulation can still be utilized to obtain the EXIT function, the present method derives analytical EXIT functions of Hadamard codes with multiple inputs and outputs in the context of low-rate RZH codes over BIAWGN channels, and applies these results to the analysis and design of RZH codes. With analytical functions, the optimization procedure is further simplified.  
         [0085]     Test results show that the present design method works well and serves as practical tool for the low-rate IRZH code optimization. The present design method can also be extended to general LDPC codes where the single parity-check nodes are replaced by other linear codes, e.g., Hadamard codes or Hamming codes.  
         [0086]     The present invention has been shown and described in what are considered to be the most practical and preferred embodiments. That departures may be made there from and that obvious modifications will be implemented by those skilled in the art. It will be appreciated that those skilled in the art will be able to devise numerous arrangements and variations which, although not explicitly shown or described herein, embody the principles of the invention and are within their spirit and scope.