Abstract:
The performance of concatenated codes are improved by generating check bits from information bits, which are represented by an information matrix, by an outer code. The information bits and the check bits are cyclically shifted to obtain an interleaved code matrix. Then, the bits of the interleaved code matrix are coded by an inner code, where at least the outer code, or the inner code, is a product code.

Description:
BACKGROUND OF THE INVENTION  
         [0001]    The capacity of optical transmission systems has rapidly increased in the last several years. The ability to upgrade a low bit-rate system to a higher bit-rate system by improving the optical components and compensating the limiting physical effects was the key for achieving system evolution.  
           [0002]    The introduction of error control coding (ECC) was a very efficient tool that successfully improved the performance and reliability of digital data transmission. Adding redundancy check bits to the information bits and advanced decoding provided the possibility of increasing the transmission distance and further made the system more robust to adverse conditions that had impaired transmission performance, such as temperature variations and acoustic vibrations. Due to reasons of complexity, hard decoding was preferred to soft decoding. Codes such as Bose-Chaudhuri-Hocquenghem codes (BCH) or extended BCH codes, which can be implemented relatively easily, were preferred.  
           [0003]    To improve coding gain, concatenated codes were introduced. However, this group of codes tends to be very sensitive when certain error patterns are received. Such error patterns cannot be corrected and, thus, lead to an insufficient bit error rate, which is also known as error flaring. This will be explained later in detail although a basic understanding of product coding may be surmised from the book “Prüfbare und korrigierbare Codes” W. Wesley Peterson, Oldenburg Verlag 1967, pages 117-123 or its English edition.  
           [0004]    What is needed is a technique for improving the performance of concatenated codes while at the same time alleviating the problem of error flaring.  
         SUMMARY OF THE INVENTION  
         [0005]    Accordingly, the present invention provides a method for improving the bit error rate (BER) and, therefore, the coding gain. This is achieved according to one embodiment of the present invention by applying an outer encoding procedure, then interleaving the information bits and at least a group of check bits. Next, the present invention applies an inner encoding procedure, wherein at least one of the outer or inner code is a product code.  
           [0006]    In another embodiment of the present invention, the interleaver is provided with a relatively low design complexity and memory requirements. A manner in which this is achieved by the present invention is that the first column of a two dimensional product code remains unchanged while the bits of the following columns are cyclically shifted by one, two, three, etc. positions, so that the bits of the first row are translated into diagonal bits by the interleaver.  
           [0007]    Applying the described interleaving procedure both on columns and rows of a two dimensional product code breaks the error bursts in rows and in columns, with which the present invention further improves the coding gain.  
           [0008]    Additional features and advantages of the present invention are described in, and will be apparent from, the following Detailed Description of the Invention and the Figures. 
       
    
    
     BRIEF DESCRIPTION OF THE FIGURES  
       [0009]    [0009]FIG. 1 is a schematic of a concatenated coding system.  
         [0010]    [0010]FIG. 2 is a schematic of a two-dimensional product code.  
         [0011]    [0011]FIG. 3 shows a permanent error-pattern.  
         [0012]    [0012]FIG. 4 shows a two-dimensional code matrix;  
         [0013]    [0013]FIG. 5 shows exemplary bits of a code matrix.  
         [0014]    [0014]FIG. 6 shows exemplary bits of an interleaved code matrix.  
         [0015]    [0015]FIG. 7 shows a final code matrix.  
         [0016]    [0016]FIG. 8 shows an iterative decoding scheme.  
         [0017]    [0017]FIG. 9 shows an error probability of an enhanced product code.  
         [0018]    [0018]FIG. 10 is a schematic of the resulting matrix after two dimensional interleaving. 
     
    
     DETAILED DESCRIPTION OF THE INVENTION  
       [0019]    [0019]FIG. 1 shows a schematic of a transmission system with a concatenated code implementation. The information bits “a” are fed to the input  1  of an outer encoder  2 , which is the first element of a serial concatenation including an interleaver  3  and an inner encoder  4 . At least one of the codes is a product code, whereas the other code may be either a simple code or a concatenated code itself. The information bits “a” and the generated check bits “c” are fed to a modulator  5 , which converts the bits into physical signals “s”, which are then transmitted over the transmission path  6  to a demodulator  7  at the receiving side.  
         [0020]    Because of the non-ideal transmission path, the signals have a tendency to be disturbed by signal impairments SI; e.g., external perturbations or physical effects of the transmission path.  
         [0021]    Thus, when the demodulator  7  converts the received signals into (binary) bits “r”, some of the resulting bit signal would be erroneous. The bits “r” are fed to a serial concatenation of an inner decoder  8 , a deinterleaver (inverse interleaver)  9  and an outer decoder  10 . The corrected information bits a COR  are emitted at the output  11 .  
         [0022]    Before turning to details of the present invention, it is useful to consider the construction of the matrices regarding the product code. In FIG. 2, a code word of a two-dimensional product code is shown. This may be generated by the outer encoder  2 . The code word matrix has the dimension of n×n bits and contains k×k information bits in section I, the generated column check bits C C  in section IV and row check bits C R  in section II allow the correction of at least one error for each column or row. Checks on check-bits CC arranged in section V can be used for checking the check-bits C C  and C R . Of course, a non-square code word matrix and different codes can be used for rows and columns.  
         [0023]    In FIG. 3, an example of a permanent 4-error-event for a 2D (two dimensional) product code with one-error-correcting codes as component codes is shown. FIG. 3 shows the case in which two errors occur in a row or column. If this occurs, a component one-error-correcting code would become overloaded and its decoder would, with high probability, add new errors. If that happens, the product code also would be overloaded because all of the errors occur in exactly two columns and two rows. Hence, the errors would never be corrected by the product code alone, no matter how many iterations are used. The error pattern would be permanent and would lead to error flaring. For component codes that can correct two or more errors, corresponding permanent error patterns exist.  
         [0024]    However, such error patterns, which are permanent with regard to the product code alone, may be resolved in the overall concatenation thanks to the interleaver and the inner coding and decoding stages of the present invention. We consider the product code word in the general form of FIG. 4. The bits a 11  . . . a ij  . . . a nn  form a 2-dimensional code word or code word matrix. As will be explained, the interleaver  3  shown in FIG. 1 maps the matrix A into a matrix B defined by the equation,  
           b ( i,j )= a (( n+i−j ) modn+ 1, j ).   (1)  
         [0025]    Now, in more detail, FIG. 5 shows the original matrix A and FIG. 6 the “interleaved” matrix B with exemplary bits, which may help to understand this operation. All binary bits a ij  in FIG. 5 and b ij  in FIG. 6 are represented by natural numbers, representing their original bit sequence. In the interleaving process, regarding matrix A, the bits  1 ,  6 ,  11 ,  16 ,  21  of the first column remain in their positions; the bits  2 ,  7 ,  12 ,  17 ,  22  of the second column are shifted downwards cyclically by one position; the bits of the third column are cyclically shifted by two positions and so on. Matrix A is translated to matrix B as shown in FIG. 6. An interleaver performing this procedure is encompassed by the present invention.  
         [0026]    The corresponding deinterleaver is described by the equation  
           a ( i,j )= b (( i+j− 2) modn+ 1, j ).   (2)  
         [0027]    After interleaving, an additional inner code is used for encoding matrix B.  
         [0028]    The resulting code matrix FM in more general form is shown in FIG. 7, for the case that the outer code is a product code and the inner code is a simple (non-concatenated) block code. To show the coding scheme more clearly, the result of the interleaving procedure is not shown. The overall encoding procedure is described in more detail in the following.  
         [0029]    According to FIG. 1, the information bits a ij , that are organized in the matrix A (FIG. 2), are fed to the outer encoder  2 , which is an encoder for a 2D (two dimensional) product code. The component code for the realization of the outer product code is obtained by extending a base cyclic code. Check bits associated with the base code are denoted in FIG. 7 by C, whereas additional check bits (e.g. parity) of the extended code are denoted by P.  
         [0030]    Corresponding to FIG. 7, the row check bits C RO , separately generated for each row of information matrix A by the outer code, are represented in section II. Further, the column check bits C CO  of the columns, separately generated for each column by the outer code, are represented in section IV. Additional parity bits P RO , P CO  are generated for rows and columns to improve the error detecting capability of the code. The column parity bits P CO  are presented in a separate section VII. The row parity bits P RO  are embedded in sections II and V.  
         [0031]    Check on check-bits CC O  (inclusive associated parity bits P RO ) are generated and positioned in section V (because of linearity, the check on check bits in section V are also check on check bits of section IV). The column parity bits PCR of sections II and V are presented in section VIII.  
         [0032]    After the outer encoding, wherein the sections II, IV, V, VII and VIII are generated, the sections I and IV are interleaved according to equation (1) by, for example, interleaver  3  of FIG. 1. The “A, C C ” matrix shown in FIG. 2 at the input of the interleaver  3  has the dimension (n−p)×k according to sections I and IV of FIG. 7. By shifting the columns of sections I and IV, an “interleaved” code-matrix B, C CO  (FIG. 7) is obtained.  
         [0033]    Contrary to the reality, the interleaver did not alter the bits in section I and IV as shown in FIG. 7. Therefore, FIG. 7 still shows the information bits and check bits in their former sections, but the bits as are renamed into bits b ij . Further, also the “interleaved” column check bits C CO  are still shown in form in section IV to avoid the confusing sequence of information and check bits as shown in FIG. 6.  
         [0034]    In this example, the interleaver does not alter the remaining sections II, V, VII and VIII.  
         [0035]    After interleaving sections I and IV, the inner encoder  4  of FIG. 1 encodes row-wise the bits of sections I and IV. The generated inner code check bits C RI  and check on check bits CC I  are represented in sections III and VI. The additional parity bits of the encoded rows P RI  are represented also in sections III and VI. Additional column check (parity) bits P CI , derived from sections III and VI, are mapped into section IX. This encoding procedure assures that every bit of the code words, except the (n−k)×p bits of section IX, is encoded at least twice.  
         [0036]    Thus, according to the present invention, wherein extended cyclic codes are used as component codes, the columns in section I and IV represent valid code words of the base code before and after interleaving. After the inner encoding stage, the rows of the combined sections I and III and the rows of the combined sections IV and VI similarly represent valid code words. Hence, due to the linearity, the columns of section III and VI are also valid code words. Because of the linearity of the codes, this coding scheme requires a moderate amount of redundant check bits.  
         [0037]    The described coding scheme is only an example of the present invention. Of course, rows and columns of the code matrix can be interchanged and the outer and the inner code can be interchanged. The sequence of the transmitted bits should always be considered. If burst errors occur in an example according to FIG. 7, then either the transmitted bits should be transmitted in the following sequence b 11 , b 21 , . . . b k1 ; b 12 , b 22 , . . . ,b k2 ; . . . , or, instead of the rows, the columns should be protected by the inner code.  
         [0038]    Several iterative decoding strategies can be devised according to the present invention. An example is shown in FIG. 8, wherein the decoding procedure provides good suppression of error flaring. The decoding device is the serial connection of the “inner row decoder” (DRI)  8 , the deinterleaver  9 , and an outer decoder  10 , which is separated in an “outer column decoder” DCO and an “outer row decoder” DRO.  
         [0039]    At the beginning of the decoding process, the inner decoder, the row decoder DRI, after receiving the final code matrix FM decodes n-p interleaved rows (sections I and III, II, V; IV and VI). The last p rows PCI are not valid code words, and hence are not processed. Thereafter, sections I and IV are deinterleaved (function I −1 ).  
         [0040]    The outer column decoder DCO (first section of the outer decoder  10 ) decodes all n columns in sections I, IV, and VII, in sections II, V, and VIII, and in sections III, VI, and IX.  
         [0041]    The outer row decoder DRO (second section of the outer decoder  10 ) decodes all n rows; namely, the combined rows of sections I and II, IV and V, and VII and VIII. Herewith, the first iteration is finished.  
         [0042]    After each decoding iteration, the corrected bits are transformed into the form of the final code matrix FM by an additional interleaver  12  (function I) and fed to the inner row decoder  2  again. After several iterations, the decoding process is stopped.  
         [0043]    As an example, an extended BCH code (n=256, k=239, d=6) is used both as component code for the outer product code and as inner code. The base BCH code (255, 239) is extended by one additional parity bit, hence p=1 in this case. The simulated bit error rate BER is shown in FIG. 9 for consecutive iterations  1 - 6 .  
         [0044]    For breaking error bursts in rows and in columns, a second interleaver, respectively a two-dimensional interleaver, can be used between the inner and outer encoding stages. After being shifted cyclically, the resulting columns are shown in the example of FIG. 6, wherein all rows are shifted by 0, 1, 2, 3, etc., positions. The resulting matrix C is shown in FIG. 10, with the operation of the row-interleaver being described by the following equation:  
           c ( i,j )= b ( i ,( n+i−j ) modn+ 1).   (3)  
         [0045]    The function of a deinterleaver is described by the equation:  
           b ( i,j )= c ( i ,( i+j− 2) modn+ 1).   (4)  
         [0046]    The function of the two-dimensional interleaver can be described by the equation:  
           c ( i,j )= a (( n+ 2 i−j−i ) modn+ 1,( n+−i ) modn+ 1)   (5)  
         [0047]    The function of the two-dimensional deinterleaver can be described by the function:  
           a ( i,j )= c (( i+j− 2) modn+ 1,( i+ 2 j− 3) modn+ 1).  
         [0048]    In the case of a combined two dimensional interleaver, n should be an odd number.  
         [0049]    While the present invention according to FIG. 10 has been described with reference to specific equations, it goes without saying that the present invention encompasses the more general concept of a concatenated code that alleviates a burst error, and encompasses other equations that fulfil the aforementioned steps and operations.  
         [0050]    As will be appreciated from the foregoing, the present invention provides a concatenated code that alleviates the effect of a burst error. Further, the present invention provides a system for encoding and a code therefor that is redundant and, therefore, minimizes the structure needed for encoding and decoding.  
         [0051]    Although the present invention has been described with reference to specific embodiments, those of skill in the art will recognize that changes may be made thereto without departing from the spirit and scope of the present invention as set forth in the hereafter appended claims.