Title of Invention  " A METHOD FOR DETERMINING PARAMETERS FOR AN INTERLEAVER IN A COMMUNICATION SYSTEM" 

Abstract  A PBRO interleaver and a method for optimizing parameters according to an interleaver size for the PBRO interleaver. The PBRO interleaver sequentially, by columns, arranges an input data stream of size N in a matrix having 2m rows and (Jl) columns, and R rows in a Jth column, PBRO interleaves the arranged data, and reads the interleaved data by rows. 
Full Text  Field of the Invention: The present invention relates generally to a method for determining parameter for an interleaver in a communication system, and in particular, to a method of optimizing parameters according to an interleaver size for partial bit reversal order. (PBRO) interleaving and an interleaver using the same. Description Of The Related Art: While a subblock channel interleaver designed in accordance with the IS2000 Release C(lx EVDV) F/L specification performs PBRO operation for row permutation similarly to an existing channel interleaver designed in accordance with the IS2000 Release A/B spec. , the subblock channel interleaver differes from the channel interleaver in that the former generates read addresses in a different manner and requires full consideration of the influence of a selected interleaver parameter on QuasiComplementary Turbo code (QCTC) symbol selection. Hence, there is a need for analyzing the operating principles of the subblock channel interleaver and the channel interleaver and creating criteria on which to generate optimal parameter for the channel interleavers. The optimal parameters will offer the best performance in channel interleavers built in accordance with the IS2000 Release A/B and IS2000 Release C. SUMMARY OF THE INVENTION An object of the present invention is to substantially solve at least the above problems and/or disadvantage and to provide at least the advantages described below. Accordingly, it is an object of the present invention to provide a method of optimizing parameters for PBRO interleaving and an interleaver using the optimizing parameters. It is another object of the present invention to provide a method of optimizing parameters m and j according to an interleaver size for PBRO interleaving and an interleaver using the same. To achieve the above and other objects, there are provided a PBRO interleaver and a method for optimizing parameters according to an interleaver size for the PBRO interleaver. The PBRO interleaver sequentially, by columns, arranges an input data stream of size N in a matrix having 2m rows, (Jl) columns, and R rows in a Jth column, The PBRO interleaver interleaves the arranged data, and reads the interleaved data by rows. Here, N, m, J and R are given as follows: (Table Removed) BRIEF DESCRIPTION OF THE DRAWINGS The above and other objects, features and advantages of the present invention will become more apparent from the following detailed description of preferred embodiments thereof when taken in conjunction with the accompanying drawings, in which: Fig. 1 illustrates PBRO interleaving when N=384, m=7 and J=3 according to an embodiment of the present invention; Fig. 2 illustrates distances between read addresses after PBRO interleaving when N=384, m=7 and J=3 according to an embodiment of the present invention; Fig. 3 illustrates PBRO interleaving when N=408, m=7, J=3 and R=24 according to an embodiment of the present invention; Fig. 4 illustrates the minimum intrarow distance after PBRO interleaving when N=408, m=7 and J=3 according to an embodiment of the present invention; Fig. 5 is a block diagram of an inter leaver to which an embodiment of the present invention is applied; Fig. 6 is a flowchart illustrating a first example of the optimal interleaver parameters determining operation according to an embodiment of the present invention; and Fig. 7 is a flowchart illustrating another example of the optimal interleaver parameters determining operation according to an embodiment of the present invention. DETAILED DESCRIPTION OF THE PREFERRED EMBODIMENTS Several preferred embodiments of the present invention will be described in detail with reference to the accompanying drawings. In the drawings, the same or similar elements are denoted by the same reference numerals, even though they are depicted in different drawings. In the following description, a detailed description of known functions or configurations incorporated herein have been omitted for conciseness. Hereinbelow, a description will be made of PBRO interleaving to which various embodiments of the present invention are applied, as well as the principle of determining parameters for optimal PBRO interleaving in accordance with embodiments of the present invention. Fig. 5 is a block diagram of a PBRO interleaver to which an embodiment of the present invention is applied. Referring to Fig. 5, an address generator 511 receives an interleaver size N, a first parameter m (i.e., Bit_Shift), a second parameter J (i.e., Up_Limit) and a clock signal Clock, and generates read addresses to read bit symbols from an interleaver memory 512. The parameters m and J are determined in an higherlayer controller (not shown) and provided to the address generator 511, or determined according to the interleaver size N in the address generator 511. The interleaver memory 512 sequentially stores input bit symbols at write addresses corresponding to count values of a counter 513 in a write mode, and outputs bit symbols from read addresses received from the address generator 511 in a read mode. The counter 513 receives the clock signal Clock, generates a count value, and provides it as a write address Write ADDR to the interleaver memory 512. As described above, the PBRO interleaver writes input data sequentially in the interleaver memory 512 in the write mode and reads data from the interleaver memory 512 according to read addresses generated from the address generator 511. For details of the PBRO interleaver, reference is made to Korea Patent Application No. 199854131, filed on December 10, 1998, the entire contents of which are expressly incorporated herein. In operation, the address generator 511 generates a read address A1 for symbol permutation by (Equation Removed) where i=0, 1,..., Nl and N=2mxJ. In Eq. (1), N denotes the size of an interleaver input sequence and m and J are interleaver parameters called Up_Limit and Bit_Shift, respectively. Fig. 1 illustrates PBRO interleaving when N=384, m=7 and J=3. Referring to Fig. 1, an interleaving matrix has 2m rows starting from index 0 and J columns starting from index 0. After step 101, the row index and column index of a symbol in the resulting matrix are expressed as [i/j] and (i mod J), respectively. Therefore, after 2m(i mod J)+ [i/j], an ith symbol in an input sequence has a number corresponding to an [i/]th row and an (I mod J) column as its read address. J symbols are in each row and the distance between symbols is 2m in the row. The row index [i/l] is BROoperated in step 102. If the distance between symbols in adjacent rows of the same column is row distance drow, the BRO operation of the row indexes results in a row permutation such that two minimum row distances d^ are 2m2 and 2m1, as illustrated in Fig. 2. Thus, after 2m(i mod J)+ BROm[i/J], the ith symbol in the input sequence has a number corresponding to a BROm[i/J]th row and an (i mod J)th column as its read address in the third matrix from the left. In summary, a read address sequence is generated by row permutations of a 2mxJ matrix in the PBRO interleaver. The rowpermuted matrix is read first by rows from the top to the bottom, then subsequently reading each row from the left to the right. For clarity of description, the distance between adjacent addresses in the same row is defined as "intrarow distance dintra". If J=l, dintra=2m. If J=l, there is no intrarow distance. The distance between adjacent addresses in different rows, that is, the distance between the last address in a row and the first address in the next row is defined as "interrow distance dinter". dinter is one of a plurality of values calculated from a function of the parameters m and J. When m and J are determined, the resulting minimum interrow distance dint(.r is defined as d™"er . Since two minimum rows distances drow are 2m2 and 2m1, (Equation Removed) The reason for computing dinter by Eq. (2) when J=l is apparent in Fig. 2. If J=l , which implies that the interleaving matrix has only one column, dinter is drow , that is, 2m2 As described above, the interleaver parameters m and J are used as the numbers of rows and columns in a read address sequence matrix and parameters for a function that determines distances between read addresses. Consequently, the characteristics of the PBRO channel interleaver depend on the interleaver parameters m and J. Before presenting a description of a method of determining subblock channel interleaver parameters that ensure the best interleaving performance according to an embodiment of the present invention, the purposes of channel interleavers in the IS2000 specifications, Releases A/B and C will first be described. Following that, the interleaver parameter determination will then be described separately in two cases: N=2mxJ; and N=2mxJ+R. The purpose of channel interleaving in the IS2000 specification, Release A/B, is to improve decoding performance, which is degraded when fading adversely influences successive code symbols, through error scattering resulting from symbol permutation. To improve decoding performance, interleaving must be performed such that the distance between adjacent addresses (interaddress distance) is maximized. Meanwhile, the purpose of subblock channel interleaving as described in the IS2000 specification, Release C, is to allow a QCTC symbol selector at the rear end of an interleaver to select appropriate code symbols according to a coding rate and thus ensure the best performance at the coding rate, as well as to scatter errors through symbol permutation. To achieve this purpose, interleaving must be performed such that interaddress distances are maximized and are uniform. Accordingly, to satisfy the requirements of the channel interleaver of the IS2000 specification, Release A/B, and the subblock channel interleaver of the IS2000 specification, Release C, an interleaver must be designed so that a read address sequence is uniformly permuted by interleaving. This is possible by determining the interleaver parameters m and j that maximize a minimum interaddress distance and minimize the difference between interaddress distances. As stated before, the interaddress distances are categorized into the intrarow distance dinter and the interrow distance dinter. The intrarow distance is a function of m and the interrow distance is a function of m and J. Since there are a plurality of interrow distances, a minimum interrow distance dinter is calculated. A minimum inter address distance is always 2m2 when J is 1, and the smaller of the minimum interrow distance dinter and the minimum intrarow distance dinter when J is not 1 . The difference between interaddress distances is 2m2 when J is 1, since the intrarow distance dinter is 0, and is equal to the difference between the intrarow distance dinter and the minimum interrow distance dinter when J is not 1 . This can be expressed as follows: (Equation Removed) Since N=2mxJ, 2m is replaced by N/J in Eq. (3), it follows that (Equation Removed) When J=3 in Eq. (4), the difference between interaddress distances is minimized. Thus Table 1 below illustrates changes in interread address distances as m increases when N=384. When J=3, a maximum difference between interaddress distances is minimized, 64 and a minimum interaddress distance dmin is maximized, 128. Table 1 (Table Removed) The method of determining optimal interleaver parameters when N=2n'xJ has been described above. Now, a method of determining optimal interleaver parameters when N=2mxJ+R will be described. Here, R is the remainder of dividing N by 2m. Thus R is a positive integer less than 2m. Fig. 3 illustrates PBRO interleaving when N=408, m=7, J=3 and R=0. Referring to Fig. 3, similarly to the case where R=0, numbers in a rowpermuted matrix after step 302 are read as read addresses by rows from the top to the bottom, reading each row from the left to the right, as described in step 303. Since R=0, the number of columns is J+l, and numbers are filled in only R rows of a (J+l)th column with no numbers in the other (2mR) rows. In summary, when R=0, a read address sequence is generated by a row permutation of a 2mxJ matrix, each row including J or J+l elements in the PBRO interleaver. The rowpermuted matrix is read by rows from the top to the bottom, reading each row from the left to the right. Furthermore, when R=0, the interleaver parameters m and J are determined such that a minimum interread address distance is maximized and the difference between interread address distances is minimized. An interrow distance dinter is a function of m, 2m irrespective of whether R=0 or R=O. However, while the minimum interrow distance dinterr is a function of m and J when R=0, it is a function of m, J and R when R=0. The minimum interrow distance is determined according to J by Eq. (5) and Eq. (6). (Equation Removed) When J = 1, (Equation Removed) Fig. 4 illustrates how Eq. (6) is derived when m=7 and J=3. Referring to Fig. 4, when O When 32m2 Table 2 below illustrates changes in the interleaver parameters J and R, the intrarow distance dinter, the minimum interrow distance dinter , and the minimum interread address distance dmin as m increases, with respect to six encoder packet (EP) sizes as described in the IS2000 specification, Release C. (Table Removed) As described above, similarly to the case where R=0, optimal interleaver parameters are selected which maximize a minimum interaddress distance and minimize the difference between interaddress distances. In Table 2, the minimum interread address distance dmin in the eighth column is the smaller of the intrarow distance dintraand the minimum interrow distance dmin Hence, parameters that maximize the minimum interread address distance dm'n can be obtained by selecting a row having the maximum value in the eighth column. For EP sizes of 2328 and 3864, three rows and Uvo rows satisfy this condition. In this case, rows that satisfy another condition of minimizing the difference between interread address dintra  dmin must be selected. They are shown in bold and underlined in Table 2. The tnlrn inter J validity of this condition is apparent by comparing the rows having the maximum dmin in terms of n(dmin) in the last column. Here, n(dmin) indicates the number of address pairs having a minimum interaddress distance dmin. Rows marked in bold and underlined in Table 2 satisfy the above two conditions for selecting optimal interleaver parameters. As noted, once the second condition is satisfied, the first condition is naturally satisfied. For reference, it is made clear that the intrarow distances dintra and the minimum interrow distances dmin listed in Table 2 are equal to those computed on PBROinterleaved read addresses. Table 2 covers both cases of dividing N by 2m or J with no remainder and of dividing N by 2m or J with a remainder R (i.e., N=2mxJ+R (0 (Table Removed) The above description has provided a method of selecting interleaver parameters expected to offer the best performance when, for example, a channel interleaver built in accordance with the IS2000 Release A/B specification, and a subblock channel interleaver built hi accordance with the IS2000 Release C specification are used. As described above, the optimal interleaver parameters are those that maximize an interaddress distance and at the same time, minimize the difference between interaddress distances when generating read addresses in a channel interleaver. Consequently, interleaver parameters for subblock channel interleaving in circumstances wherein a subblock channel interleaver is built in accordance with the IS2000 Release C specification are values in the rows in bold and underlined in Table 2. While interleaver parameters selection has been described for the subblock channel interleaver built in accordance with the IS2000 Release C specification, it is obvious that the same thing can also be applied to systems of other standards. Fig. 6 is a flowchart illustrating an optimal interleaver parameters determining operation according to an embodiment of the present invention. Particularly, this operation is concerned with the computation of dintra dmin,  An optimal (m, J) that minimizes dintra  dmin is selected by computing dintra  dmin , changing (m, J). Referring to Fig. 6, when an interleaver size N, and parameters m and J are given in step 601, a parameter R is calculated by subtracting 2mxJ from N in step 603. In step 605, it is determined whether J is 1. This is a determination, therefore, of whether an interleaving matrix has a single column or not. If J is 1, the procedure goes to step 607 ("Yes" path from decision step 605) and if J is not 1, the procedure goes to step 621 ("No" path from decision step 605). In step 607, it is determined whether R is 0(i.e., whether N is an integer multiple of 2m). On the contrary, if R is 0 (("Yes" path from decision step 607), an intrarow distance dintra is set to 0 in step 609. If R is not 0 ("No" path from decision step 607), dintra is set to 2m in step 617. After dintra is determined, it is determined whether R is less than 3x2m2 in step 611. If R is less than 3x2m2 ("Yes" path from decision step 61 1) a minimum interrow distance dmin is set to 2m2 in step 613. If R is equal to or greater than 3x2m2 ("No" path from decision step 611) dinter is set to 2m1 in step 619. After dinter is determined, dinlra  dmin is calculated in step 615. Meanwhile, if J is not 1 in step 605, dintra is set to 2m in step 621 and it is determined whether R is less than 2m1 in step 623. If R is less than 2m1 ("Yes" path from decision step 623) dinter is set to (2J3)x2m1 in step 625 and then the procedure goes to step 615. If R is equal to or greater than 2m1 ("No" path from decision step 623), it is determined whether R is less than 3x2m2 in step 627. If R is less than 3x2m2 ("Yes" path from decision step 627) , dinter is set to (4J3)x2m2 in step 629. If R is equal to or greater than 3x2m2 ("No" path from decision step 627) , dinter is set to (2Jl)x2m1 in step 631 and then the procedure goes to step 615. Optimal interleaver parameters m and J are achieved for a given N by computing dinlra dmin changing (m, J). If J is one of 1, 2 and 3, a logical formula that facilitates selection of J without the repealed computation can be derived. With a description of a logical equation deriving procedure omitted, the logical equation is (Equation Removed) From an optimal J from Eq. (7), an optimal m is calculated by (Equation Removed) The selection of optimal interleaver parameters by the simple logical equations is summarized below and illustrated in Fig. 7. 1. An optimal J is obtained by Eq. (7) for a given N; and 2. mis calculated by computing Eq. (8) using N and J. Fig. 7 is a flowchart illustrating an optimal interleaver parameters determining operation according to another embodiment of the present invention. Referring to Fig. 7, when N is given, a variable a is calculated by log2N [log, N] and a variable P is calculated by 2[kigmN] in step 701. Decision step 703, determines whether a is less than a first threshold, 0.5849625. If a is less than the first threshold ("Yes" path from decision step 703), another decision is made, whether N is less than P in decision step 705. If N is equal to or greater than P ("No" path from decision step 705), the procedure goes to step 707. On the contrary, if N is less than p ("Yes" path from decision step 705), J is determined to be 3 in step 713. Meanwhile, decision step 707 determines whether N is less than (3/2)xß. If N is less than (3/2)xp ("Yes" path from decision step 707), J is determined to be 2 in step 711. Otherwise, J is determined to be 1 in step 709 ("No" path from decision step 707). If a is equal to or greater than the first threshold in step 703 ("No" path from decision step 703), a decision is made whether N is less than (3/2)xp in decision step 717. If N is less than (3/2)xß ("Yes" path from decision step 717), J is determined to be 2 in step 721. Otherwise, decision step 719 determines whether N is less than (7/ 4)xp. If N is less than (7/4)xß ("Yes" path from decision step 719), J is determined to be 3 in step 723. Otherwise, J is determined to be 1 in step 725 ("No" path from decision step 719). As described above, optimal m and J can be calculated simply by the logical equations using N. The optimal m and J are equal to m and J resulting from repeated computation using different (m, J) values as illustrated in Table 2. This obviates the need for storing optimal m and J values according to N values. When N=2328, for example, optimal m and J values are calculated in the procedure illustrated in Fig. 7 or by Eq. (8) to Eq. (10), as follows. (Equation Removed) For reference, Eq. (7) is derived as follows. In each case depicted in Fig. 6, Eq. (5) and Eq. (6), dintra  d min is determined by (Equation Removed) Since N=2mJ+R and 0 Thus, m = Iog2(N/J) . Using m = log 2(N/J) , J can be expressed as a function of N for all the cases of A and B. A1. When J=l, since m = [log:N], R = N2m = N2[log,N]. Then the cases Al, A2 and A3 can be expressed as functions of N. It therefore follows that: (Equation Removed) Then the cases Bl, B2 and B3 can be expressed as functions of N instead of R. Therefore, (Equation Removed) B'". When J=3, since \\Jog, N\ 2, if log2N  [log, N] If J is 4 or more, this case is neglected because dinlra  dmin that intra  d min in any of the cases where J=l,2, and 3. cannot be less Eq. (7) is obtained by selecting a case having a minimum dintra  d min among the cases of A'l, A'2, A'3, B"l, B"2, B"3, B'"l', B'"2', and B"'3'. Similarly, Eq. (8) is obtained by selecting a case having a minimum dintra d min among the cases of AM, A'2, A'3, B"l, B"2, B"3, B'"l", B'"2", and B'"3". In accordance with the embodiments of the present invention as described above, interleaver parameters m and J are simply optimized according to an interleaver size N, for PBRO interleaving. While the invention has been shown and described with reference to certain preferred embodiments thereof, it will be understood by those skilled in the art that various changes in form and details may be made therein without departing from the spirit and scope of the invention as defined by the appended claims. We claim: 1. A method for determining parameters for an interleaver in a communication system, comprising: sequentially arranging by columns an input data stream of size N in a matrix having 2m rows, (Jl) columns and R rows in a (J+l)th column (0 calculating a first minimum distance between addresses indicating adjacent columns in the same row in the generated read addresses; calculating a second minimum distance between addresses indicating a last column of a row and an address indicating a first column of the next row in the generated read addresses; and repeating the steps of arranging, interleaving, generating read address, calculating the first minimum distance and calculating the second minimum distance until the m and J values, that minimize the difference between the first minimum distance and the second minimum distance, are determined . 2. The method as claimed in claim 1, wherein the parameters N, m, J and R are determined such as herein described in table 1. 3. The method as claimed in claim 1, wherein the second minimum distance is determined as herein described in the equation number 5 and 6. 4. A method of determining parameters for an interleaver in a communication system as claimed in claim 1, comprising: sequentially arranging by columns an input data stream of size N in a matrix having 2m rows, (Jl) columns and R rows in a last column (0 interleaving the arranged data, and generating read addresses for reading the interleaved data by rows; calculating a first minimum distance between addresses indicating adjacent columns in the same row in the generated read addresses; calculating a second minimum distance between addresses indicating a last column of a row and an address indicating a first column of the next row in the generated read addresses; and repeating the steps of arranging, interleaving, generating read address, calculating the first minimum distance and calculating the second minimum distance until the m and J values, that maximize one of the first minimum distance and the second minimum distance, are determined. 

1579delnp2003assignment.pdf
1579delnp2003correspondenceothers.pdf
1579delnp2003correspondencepo.pdf
1579delnp2003description (complete).pdf
1579delnp2003petition137.pdf
Patent Number  222599  

Indian Patent Application Number  1579/DELNP/2003  
PG Journal Number  44/2008  
Publication Date  31Oct2008  
Grant Date  19Aug2008  
Date of Filing  01Oct2003  
Name of Patentee  SAMSUNG ELECTRONICS CO., LTD.  
Applicant Address  416, MAETANDONG, PALDALGU, SUWONSHI, KYUNGKIDO, REPUBLIC OF KOREA.  
Inventors:


PCT International Classification Number  H03M 13/27  
PCT International Application Number  PCT/KR03/00261  
PCT International Filing date  20030206  
PCT Conventions:
