(12) United States Patent
`Tong et al.
`
`USOO6732316B1
`(10) Patent No.:
`US 6,732,316 B1
`(45) Date of Patent:
`May 4, 2004
`
`(54) DATA INTERLEAVER AND METHOD OF
`INTERLEAVING DATA
`
`(75) Inventors: Wen Tong, Ottawa (CA); Catherine
`Leretaille, Paris (FR)
`(73) Assignee: Nortel Networks Limited, St. Laurent
`(CA)
`Subject to any disclaimer, the term of this
`patent is extended or adjusted under 35
`U.S.C. 154(b) by 0 days.
`
`(*) Notice:
`
`(21) Appl. No.: 09/531,470
`(22) Filed:
`Mar 20, 2000
`(30)
`Foreign Application Priority Data
`Mar. 19, 1999
`(CA) ............................................. 2266283
`(51) Int. Cl. ............................................... H03M 13700
`(52) U.S. Cl. ........................................ 714/756; 714/701
`(58) Field of Search ................................. 714/756, 755,
`714/701, 702
`
`(56)
`
`References Cited
`U.S. PATENT DOCUMENTS
`
`9/2001 Lee et al. ................... 714/788
`6,289,486 B1
`6,304,991 B1 * 10/2001 Rowitch et al.
`... 714/755
`6,334,197 B1 12/2001 Eroz et al. ....................... 12/1
`6,442,728 B1
`8/2002 Cui et al. .......................... 8/2
`6.543,013 B1 * 4/2003 Li et al. .......
`... 714/701
`6,553,516 B1
`4/2003 Suda et al. ................. 714/702
`
`6,637,000 B2 * 10/2003 Rowitch et al. ............ 714/755
`* cited by examiner
`Primary Examiner Phung M. Chung
`(74) Attorney, Agent, or Firm Mintz, Levin, Cohn, Ferris,
`Glovsky and Popeo, P.C.
`(57)
`ABSTRACT
`Interleaving of data Symbols comprises permuting rows and
`columns of a matrix of N, rows and N. columns, in which
`data Symbols to be interleaved are represented row by row,
`in accordance with:
`
`Row Permutation
`Column Permutation
`
`I (k)
`(T)
`Ic
`
`ICl + f (k) modN.
`
`where I(k) represents a data Symbol with a row index k, k
`is an integer from 1 to NO, is an integer, f(1) is a non-zero
`function of a column index 1, 1 is an integer from 1 to N, I (1)
`represents a data Symbol with the column index 1, C is an
`integer, f(k) is Zero or a function of the row index k, and
`modn, and modn represent modulo-N, and modulo-N
`arithmetic respectively, interleaved data Symbols being
`derived from the matrix column by column. A data inter
`leaver comprises a memory for Sequentially Storing data
`symbols to be interleaved and a relatively simple circuit for
`determining read addresses for the interleaved data Symbols.
`The data interleaver is particularly Suited for channel inter
`leaving in a 3rd generation CDMA wireleSS communications
`System.
`
`37 Claims, 2 Drawing Sheets
`
`LINEAR
`ADDRESSED
`WRE-N
`
`
`
`
`
`
`
`COLUMN
`COUNTER
`
`ROW
`COUNER
`
`CLK
`
`

`

`U.S. Patent
`
`May 4, 2004
`
`Sheet 1 of 2
`
`US 6,732,316 B1
`
`14
`
`18
`
`2O
`
`22
`
`24
`
`26
`
`28
`
`3O
`
`32
`
`TRANSPORT CHANNEL
`MULTIPLEXER
`
`SEGMENTATION
`
`12
`
`22
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`MULTIPLEXER
`
`RATE MATCHING
`
`
`
`FIRST (INTER-FRAME OR
`CHANNEL) INTERLEAVER
`
`RADIO FRAME
`SEGMENTATION
`
`PHYSICAL CHANNEL
`SEGMENTATION
`
`T.
`
`OTHER
`SERVICES
`
`10
`
`34
`
`36
`
`Fig. 1
`PRIOR ART
`
`SERVICE MULTIPLEXER
`
`SECOND (NTRA-FRAME)
`NTERLEAVER
`
`SEGMENTATION & MAPPNG .
`
`

`

`U.S. Patent
`
`May 4, 2004
`
`Sheet 2 of 2
`
`US 6,732,316 B1
`
`LINEAR
`ADDRESSED
`WRITE-IN
`
`NTERLEAVED DATA
`
`40
`
`68
`
`CLK
`
`OUTPUT
`
`WORKING
`MEMORY
`
`
`
`a-Herra
`
`62
`
`READ ADDRESS
`COMBINER
`
`44
`
`COLUMN
`COUNTER
`
`ROW
`COUNTER
`
`CLK
`
`Fig. 2
`
`

`

`1
`DATA INTERLEAVER AND METHOD OF
`INTERLEAVING DATA
`
`US 6,732,316 B1
`
`2
`arithmetic respectively, interleaved data Symbols being
`derived from the matrix column by column.
`Preferably f(1)=ml where m is an integer; for example m
`is 1 or is approximately equal to N/N. If f(k) is not Zero,
`then preferably f(k)=nk where n is an integer, for example
`n=1. Conveniently C, is the largest prime number less than
`N/2, and C is the largest prime number less than N/2.
`The actual number of data symbols to be interleaved need
`not be exactly equal to N,N- but can be a little less than this,
`in which case preferably the method further comprises the
`Step of determining one or more matrix positions in which
`data Symbols to be interleaved are not represented, inter
`leaved data Symbols not being derived from Such determined
`matrix positions.
`The invention also provides a data symbol interleaver
`arranged for carrying out a method as recited above.
`Another aspect of the invention provides a data inter
`leaver comprising: a memory arranged to Sequentially Store
`up to NN data symbols to be interleaved at respective
`addresses, where N and N are integers greater than 1; a
`counter arranged to provide an index 1 from 1 to Nc, and a
`counter arranged to provide an indeX from 1 to Nr for each
`value of the indeX 1; a circuit arranged to determine a first
`value (Cl--nkmodN and a second value Clk+mlmodN,
`where C, C, and m are positive integers and n is a positive
`integer or Zero, and modn, and modN represent modulo-N,
`and modulo-N arithmetic respectively; and an address com
`biner arranged to combine the first value as a more signifi
`cant part and the Second value as a leSS Significant part of a
`read address for reading interleaved data Symbols from the
`memory.
`The data interleaver can further comprise an address
`decoder responsive to at least one read address produced by
`the address combiner at which a data symbol to be inter
`leaved is not stored in the memory for inhibiting reading
`from the memory from Such address. In this case conve
`niently the data interleaver further includes a first-in, first
`out buffer arranged to buffer interleaved data symbols read
`from the memory.
`The invention further provides a channel interleaver for a
`communications System including a data rate matching
`circuit which performs puncturing of data Symbols, com
`prising a data interleaver as recited above.
`BRIEF DESCRIPTION OF THE DRAWINGS
`
`The invention will be further understood from the fol
`lowing description with reference to the accompanying
`drawings, in which:
`FIG. 1 illustrates a known arrangement for Service mul
`tiplexing and channel interleaving in a 3rd generation
`CDMA communications system; and
`FIG. 2 illustrates an implementation of an interleaver in
`accordance with an embodiment of this invention.
`
`DETAILED DESCRIPTION
`Referring to FIG. 1, there is illustrated a known arrange
`ment for Service multiplexing and channel interleaving in a
`3rd generation CDMA radio communications system. The
`arrangement includes a Service multiplexer 10 which Serves
`to multipleX together a plurality of data Signal Streams,
`referred to as main stream services or QoS (Quality of
`Service) channels, which are Supplied via respective service
`blocks 12 only one of which is illustrated. Each service
`block 12 is supplied at inputs 14 with a plurality of con
`Stituent input signals, which may for example comprise any
`of various types of Signals. Such as voice, data, and multi
`
`5
`
`15
`
`This invention relates to data interleavers and to methods
`of interleaving data Symbols, and is particularly concerned
`with a So-called channel interleaver for interleaving data
`Symbols in a communications System.
`BACKGROUND
`It is well known to perform interleaving of data in a
`communications System using forward error correction
`(FEC) in order, on deinterleaving, to distribute errors to
`facilitate their correction. Typically, Such interleaving uses a
`block interleaver to interleave blocks of data. So-called
`turbo coding (parallel concatenated convolutional coding)
`uses an interleaver between inputs to two convolutional
`coders which produce respective parity bits from the input
`data before and after interleaving. With increasing attention
`being given to the use of turbo coding, particularly in
`wireleSS communications Systems, attention has also been
`given to the form of the interleaver.
`So-called 3rd generation CDMA (code division multiple
`access) wireless communications Systems are also being
`developed which require a channel or inter-frame interleaver
`which operates to interleave or permute data in blockS
`corresponding to the radio frame duration, typically 10 ms.
`For example, a multi-stage block interleaver (MIL) has been
`proposed for channel (inter-frame) interleaving and for
`intra-frame interleaving.
`However, in Such Systems the channel interleaver either
`precedes or follows a rate matching function which Serves to
`match various data rates to the radio frame rate, and which
`typically involves puncturing (omission) of data Symbols. It
`is necessary to avoid consecutive puncture of adjacent data
`symbols of coded blocks of data symbols, but the multi
`Stage interleaver Suffers from a problem in this respect. A
`So-called potential punturing grid (PPG) concept has been
`proposed to correct this problem, but the choice of an
`appropriate PPG depends on variables such as the frame
`size, number of frames, puncturing rate, and puncturing
`position.
`Accordingly, it would be desirable to provide an inter
`leaver which maximizes the distances by which adjacent
`punctured data Symbols are separated, for arbitrary punc
`turing rates and puncturing positions, without any PPG.
`An object of this invention is to provide an improved data
`interleaver and method of interleaving data Symbols.
`SUMMARY OF THE INVENTION
`According to one aspect, this invention provides a method
`of interleaving data Symbols comprising permuting rows and
`columns of a matrix of N, rows and N. columns, in which
`data Symbols to be interleaved are represented row by row,
`in accordance with:
`
`25
`
`35
`
`40
`
`45
`
`50
`
`55
`
`Row Permutation
`Column Permutation
`
`I (k)
`(T)
`Ic
`
`ICl + f (k) modN.
`
`where I(k) represents a data Symbol with a row index k, k
`is an integer from 1 to N, O, is an integer, f(1) is a non-zero
`function of a column index 1, 1 is an integer from 1 to N, (1)
`represents a data Symbol with the column indeX l, C is an
`integer, f(k) is Zero or a function of the row index k, and
`modn, and modn represent modulo-N, and modulo-N
`
`60
`
`65
`
`

`

`US 6,732,316 B1
`
`3
`media Signals. These input signals may have arbitrary trans
`mission rates, frame sizes, and other parameters. The input
`Signals have CRC (cyclic redundancy check) codes added in
`blocks 16 and are multiplexed together in a transport chan
`nel multiplexer 18. The multiplexed signals are Segmented,
`for encoding, in a Segmentation block 20, and the Segmented
`Signals are Subjected to FEC (forward error correction)
`coding in FEC blocks 22. The encoded signals are multi
`plexed in a multiplexer 24 and Subjected to rate matching
`(puncturing (deletion) of redundant symbols or repetition
`(stuffing) of additional symbols) in a block 26 to match the
`data rate to the radio communications rate (or So-called air
`rate) with frames of 10 ms duration. Primarily in order to
`Separate adjacent Symbols to reduce the adverse effects of
`errors due to fading in the radio channel, the data Symbols
`are interleaved in a first interleaver 28, which is referred to
`as a channel or inter-frame interleaver because it operates to
`permute blocks each of 10 ms of data symbols. Although in
`FIG. 1 the interleaver 28 is shown following the rate
`matching block 26, the positions of these functions may be
`interchanged. For example, these functions may be in the
`order shown in FIG. 1 for downlink transmission of signals
`from a central Station, and may be in the reversed order for
`uplink transmission of Signals to the central Station.
`Following the functions 26 and 28, the resulting rate
`matched and interleaved Signals are Segmented for radio
`frames and physical channels in Segmentation blockS 30 and
`32 respectively to produce the Signals for multiplexing by
`the multiplexer 10. Signals output by the multiplexer 10 are
`interleaved by a second interleaver 34 the outputs of which
`are Segmented and mapped to dedicated physical channels in
`a Segmentation and mapping block 36 for communications
`via a CDMA radio communications path in known manner.
`The present invention is directed to implementations of
`the first interleaver 28, and is particularly concerned with
`providing an implementation of the first interleaver 28 with
`a performance that is Sufficiently good to enable the Second
`interleaver 34 to be omitted or reduced to a simple shuffling
`operation. This is desirable in particular because the Second
`interleaver 34 has the potential to degrade the interleaving
`performed by each first interleaver 28, whereas each first
`interleaver 28 can be optimized for its particular rate
`matched data Stream and QoS. Alternatively, the Second
`interleaver 34 can also be implemented as an interleaver in
`accordance-with an embodiment of this invention, the
`parameters of both interleavers being chosen to provide an
`optimized performance of the Overall arrangement.
`Accordingly, the first interleaver 28 is implemented as an
`algebraic interleaver providing a good random Spreading
`property which facilitates Straightforward rate matching by
`puncturing and Symbol repetition. Accordingly, the multiple
`encoded Symbol blocks for each QoS channel are mapped
`into a 2-dimensional matrix and are Subjected to linear
`congruential rules to permute the rows and columns of the
`matrix to implement the interleaving function. A maximum
`interleaving depth and time span can be determined by
`Searching a set of best parameters. The interleaver conse
`quently has a relatively simple form without disadvantages
`of known interleavers, Such as requiring large memory sizes
`for look-up tables or inadequately accommodating the rate
`matching function.
`Although the following description refers to rows and
`columns of a matrix, it should be understood that this is for
`convenience and clarity, that the rows and columns can be
`interchanged without changing the function of the
`interleaver, and that in practice and as described below the
`interleaver can operate by equivalent control of read or write
`
`4
`addressing of memory locations of a linear memory in which
`data Symbols are Stored, without any actual movement of the
`Stored data Symbols among the memory locations.
`An interleaver in accordance with embodiments of this
`invention operates to implement the following Steps:
`1. Represent a number N of encoded blocks of data symbols
`each of length N data Symbols as a matrix of N. rows and
`N. columns.
`2. Permute the rows and columns of the matrix in accor
`dance with:
`
`Row Permutation
`Column Permutation
`
`I (k)
`I (T)
`
`IC, k + f (?) modN,
`ICl + f (k) modN.
`
`where I(k) represents a data symbol with a row index k,
`k is an integer from 1 to N, O, is a row permutation
`parameter and is an integer, f(1) is a positive function
`of a column index 1, 1 is an integer from 1 to N, I (1)
`represents a data Symbol with the column indeX l, C is
`a column permutation parameter and is an integer, f(k)
`is a positive function of the row indeX k, and modn, and
`modn represent modulo-N and modulo-N arithmetic
`respectively.
`3. Derive interleaved data symbols from the matrix column
`by column.
`In the row permutation of step 2, f(1) #0 to avoid punc
`turing of consecutive data Symbols due to the rate matching.
`For example, the function f(1)=ml where m is a constant
`integer, for example m=1 So that f(1)=l. The column per
`mutation of Step 2 can use bit reversal as is known in the art,
`or the function f(k) can be zero. Alternatively, for example,
`the function f(k)=nk where n is a constant integer, for
`example n=1 So that f(k)=k. It can be appreciated that the
`order in which the row and column permutations of Step 2
`are performed is arbitrary, i.e. either the row permutation or
`the column permutation can be performed first, or both
`permutations can be performed contemporaneously.
`In a first embodiment of the invention described below,
`for example the parameter C, is chosen to be the largest
`prime number less than LN/2, the parameter C is chosen
`to be the largest prime number less than LN/2, m=LN./NJ,
`and n=0. The symbols
`refer to rounding down to an
`integer.
`In this example, N=8, N=10, CL=3, C=3,m=1, and n=0.
`Thus, in step 1, 80 data symbols, identified by the numbers
`1 to 80 in the following tables, in eight 10 ms coded blocks
`each of 10 coded symbols, are represented row by row in a
`10 by 8 matrix with the row index k and the column index
`l, as shown by Table 1:
`
`TABLE 1.
`
`1.
`
`k
`
`1.
`
`2
`
`3
`
`1.
`2
`3
`4
`5
`6
`7
`8
`9
`10
`
`1.
`9
`17
`25
`33
`41
`49
`57
`65
`73
`
`2
`10
`18
`26
`34
`42
`50
`58
`66
`74
`
`3
`11
`19
`27
`35
`43
`51
`59
`67
`75
`
`4
`
`4
`12
`2O
`28
`36
`44
`52
`60
`68
`76
`
`5
`
`5
`13
`21
`29
`37
`45
`53
`61
`69
`77
`
`6
`
`7
`
`8
`
`6
`14
`22
`30
`38
`46
`54
`62
`7O
`78
`
`7
`15
`23
`31.
`39
`47
`55
`63
`71
`79
`
`8
`16
`24
`32
`40
`48
`56
`64
`72
`8O
`
`15
`
`25
`
`35
`
`40
`
`45
`
`50
`
`55
`
`60
`
`65
`
`

`

`S
`The row permutation I,(k)=3k+lmod 10 produces a
`result as shown by the following Table 2:
`
`6
`The row permutation I,(k)=3k+lmod10 then produces a
`result as shown by the following Table 5:
`
`US 6,732,316 B1
`
`TABLE 2
`
`1.
`
`TABLE 5
`
`1.
`
`k
`
`1.
`
`25
`49
`73
`17
`41
`65
`9
`33
`57
`1
`
`2
`
`34
`58
`2
`26
`50
`74
`18
`42
`66
`10
`
`3
`
`43
`67
`11
`35
`59
`3
`27
`51
`75
`19
`
`1
`2
`3
`4
`5
`6
`7
`8
`9
`1O
`
`4
`
`52
`76
`2O
`44
`68
`12
`36
`60
`4
`28
`
`5
`
`61
`5
`29
`53
`77
`21
`45
`69
`13
`37
`
`6
`
`7O
`14
`38
`62
`6
`3O
`54
`78
`22
`46
`
`7
`
`79
`23
`47
`71
`1S
`39
`63
`7
`31
`55
`
`8
`
`8
`32
`56
`8O
`24
`48
`72
`16
`40
`64
`
`The column permutation I(l)=31)mod8 then produces a
`result as shown by the following Table 3:
`
`TABLE 3
`
`1.
`
`k
`
`1.
`
`43
`67
`11
`35
`59
`3
`27
`S1
`75
`19
`
`2
`
`0
`14
`38
`62
`6
`3O
`54
`78
`22
`46
`
`3
`
`25
`49
`73
`17
`41
`65
`9
`33
`57
`1.
`
`1
`2
`3
`4
`5
`6
`7
`8
`9
`10
`
`4
`
`52
`76
`2O
`44
`68
`12
`36
`60
`4
`28
`
`5
`
`79
`23
`47
`71
`15
`39
`63
`7
`31
`55
`
`6
`
`34
`S8
`2
`26
`50
`74
`18
`42
`66
`10
`
`7
`
`61
`5
`29
`S3
`77
`21
`45
`69
`13
`37
`
`8
`
`8
`32
`56
`8O
`24
`48
`72
`16
`40
`64
`
`In Step 3, the data Symbols are derived column by column
`from Table 3, i.e., with the interleaved order 43, 67, ...,
`19, 70, 14, . . . , 40, 64.
`In a second embodiment of the invention, with Nis8 as
`is typically the case for an arrangement as described above
`with reference to FIG. 1, the parameter C is chosen to be 1
`if Ns3 and is chosen to be 3 if N is from 4 to 8, the
`parameter C, is chosen as above to be the largest prime
`number less than LN/2, the parameter m=N/8, and n=1.
`Thus with N=8 and N=10 as in Table 1 above, C=3, C=3,
`and m=1.
`The column permutation I (1)=31 +kmod8 produces
`from Table 1 a result as shown by the following Table 4:
`
`TABLE 4
`
`1.
`
`k
`
`1.
`
`2
`
`3
`
`4
`13
`22
`31
`40
`41
`50
`59
`68
`77
`
`7
`16
`17
`26
`35
`44
`53
`62
`71
`80.
`
`2
`11
`20
`29
`38
`47
`56
`57
`66
`75
`
`1.
`2
`3
`4
`S
`6
`7
`8
`9
`10
`
`4
`
`5
`14
`23
`32
`33
`42
`51
`60
`69
`78
`
`5
`
`8
`9
`18
`27
`36
`45
`54
`63
`72
`73
`
`6
`
`3
`12
`21
`30
`39
`48
`49
`58
`67
`76
`
`7
`
`6
`15
`24
`25
`34
`43
`52
`61
`7O
`79
`
`8
`
`1.
`10
`19
`28
`37
`46
`55
`64
`65
`74
`
`k
`
`1.
`
`31
`50
`77
`22
`41
`68
`13
`40
`59
`4
`
`2
`
`35
`62
`7
`26
`53
`8O
`17
`44
`71
`16
`
`3
`
`47
`66
`11
`38
`57
`2
`29
`56
`75
`2O
`
`1.
`2
`3
`4
`5
`6
`7
`8
`9
`1O
`
`4
`
`51
`78
`23
`42
`69
`14
`33
`60
`5
`32
`
`5
`
`63
`8
`27
`54
`73
`18
`45
`72
`9
`36
`
`6
`
`67
`12
`39
`58
`3
`3O
`49
`76
`21
`48
`
`7
`
`79
`24
`43
`70
`15
`34
`61
`6
`25
`52
`
`8
`
`1.
`28
`55
`74
`19
`46
`65
`1O
`37
`64
`
`In Step 3, the data Symbols are derived column by column
`from Table 5, i.e., with the interleaved order 31, 50, ...,
`4, 35, 62,..., 37, 64).
`Numerous other combinations of the parameters C, C,
`m, and n can be chosen to result in different interleaved
`results, for example the parameters C. and C, may have
`larger values Such as 5, 7, etc. and may be different from one
`another.
`FIG. 2 illustrates an implementation of an interleaver 28
`in accordance with an embodiment of this invention. AS
`illustrated in FIG. 2, the interleaver includes a working
`memory 40 with two halves, alternately used in known
`manner for writing into and reading from the memory, each
`for storing the NN data symbols represented in the matrix
`as described above, these data Symbols being written into the
`memory linearly corresponding to the row-by-row organi
`zation of the matrix illustrated by Table 1 above. A modulo
`N. row counter 42 is responsive to a clock signal CLK to
`provide a count representing the row index k, and a carry
`output of this counter 42 is Supplied to a modulo-N column
`counter 44 to provide a count representing the column index
`1. The count of the column counter 44 is supplied to
`multipliers 46 and 48 which are also supplied with the
`parameters C and m respectively to produce products
`representing Cl and ml respectively, and the count of the
`row counter 42 is supplied to multipliers 50 and 52 which
`are also Supplied with the parameters n and C, respectively
`to produce products representing nk and Clk respectively.
`An adder 54 adds the outputs of the multipliers 46 and 50,
`and an adder 56 adds the outputs of the multipliers 48 and
`52. The outputs of the adders 54 and 56 are reduced to
`modulo-N and modulo-N forms respectively by modulo
`functions 58 and 60 respectively, each of which can com
`prise comparison and Subtraction functions. Outputs of the
`functions 58 and 60 are combined in a combiner 62 to
`produce an address for reading the respective data Symbol in
`its interleaved sequence from the memory 40. As illustrated
`in FIG. 2, the read address is supplied to the memory 40 via
`a Switch 64 which is provided as described below.
`If the number of rows N is a power of two, then the
`combiner 62 can Simply combine the output of the function
`60 as the least significant bits, and the output of the function
`58 as the most significant bits, of the read address for the
`memory 40; equivalently the output of the function 60 is
`added by the combiner 62 to N times the output of the
`function 58. It can be appreciated that if m=1 then the
`multiplier 48 is not required, if n=1 then the multiplier 50 is
`not required, and if n=0 then neither the multiplier 50 nor the
`adder 54 is required. Accordingly, the implementation of the
`interleaver can be even simpler than that illustrated in FIG.
`2.
`
`1O
`
`15
`
`25
`
`35
`
`40
`
`45
`
`50
`
`55
`
`60
`
`65
`
`

`

`7
`It may be desired to interleave data symbols in arbitrary
`sized frames that are not an integer multiple of N. In this
`case, the number of rows of the matrix is Selected to
`accommodate all of the data symbols of the frame to be
`interleaved, and the last few (less than N) memory locations
`in the working memory 40 are not written into. In order to
`omit the data symbols of these memory locations from the
`interleaved data symbols, the interleaver of FIG. 2 also
`includes a decoder 66 which detects these memory locations
`in the read address output of the combiner 62, and upon Such
`detection opens the Switch 64 to prevent reading of data
`from the memory 40 in respect of these locations. In order
`to provide a constant data output rate within each frame of
`interleaved data symbols read out from the memory 40, the
`interleaver of FIG. 2 further includes a FIFO (first-in,
`first-out) memory 68 via which the interleaved data symbols
`are supplied to an output of the interleaver, the FIFO 68
`being pre-filled at the Start of each interleaved data Symbol
`frame and having a size (e.g. up to N.) Sufficient to allow for
`the non-read, and hence omitted, memory locations.
`AS can be appreciated from the above description, the
`interleaver has a relatively simple Structure So that it can be
`easily implemented, it does not require Significant memory
`other than the working memory 40, it can easily operate in
`real time, and it can accommodate arbitrary data frame sizes.
`In addition, a corresponding deinterleaver can have Substan
`tially the same Structure, So that it is also conveniently and
`easily implemented.
`Although particular embodiments and examples of the
`invention have been described above, it can be appreciated
`that numerous modifications., variations, and adaptations
`may be made without departing from the Scope of the
`invention as defined in the claims.
`What is claimed is:
`1. A method of interleaving data Symbols comprising the
`Steps of:
`Storing data Symbols to be interleaved in a memory
`having Storage locations representing rows and col
`umns of a matrix of N, rows and N columns, the data
`symbols to be interleaved being represented row by
`row in Said matrix;
`reading the Stored data Symbols from the Storage locations
`of the memory in an interleaved manner as interleaved
`data symbols by deriving the interleaved data symbols
`column by column of a permutation of the matrix So
`that the interleaved data Symbols are arranged in accor
`dance with:
`
`Row Permutation
`Column Permutation
`
`I (k) = C, k + f (?) modN,
`I (T) = Clel + f (k) modN.
`
`where 1,0k) represents a data Symbol with a row index k, k
`is an integer from 1 to N, O, is an integer, f(1) is a non-zero
`function of a column index I, I is an integer from 1 to N,
`55
`I(I) represents a data symbol with the column index I, C, is
`an integer, f(k) is Zero or a function of the row index k, and
`modN, and modN represent modulo-N, and module N.
`arithmetic respectively.
`2. A method as claimed in claim 1 wherein f(1)=ml where
`m is an integer.
`3. A method as claimed in claim 2 wherein f(k)=nk where
`n is an integer.
`4. A method as claimed in claim 3 wherein n=1.
`5. A method as claimed in claim 2 wherein m=1.
`6. A method as claimed in claim 2 wherein m is approxi
`mately equal to N,N.
`
`65
`
`60
`
`US 6,732,316 B1
`
`1O
`
`15
`
`25
`
`35
`
`40
`
`45
`
`50
`
`8
`7. A method as claimed in claim 1 wherein f(k) is zero.
`8. A method as claimed in claim 1 wherein C, is the largest
`prime number less than N/2.
`9. A method as claimed in claim 1 wherein C is the largest
`prime number less than N/2.
`10. A method as claimed in claim 1 wherein a number of
`data symbols to be interleaved is less than NN, the method
`further comprising the Step of determining one or more
`matrix positions in which data Symbols to be interleaved are
`not represented, interleaved data Symbols not being derived
`from Such determined matrix positions.
`11. A data Symbol interleaver arranged for carrying out a
`method as claimed in claim 1.
`12. A method of claim 1, further comprising puncturing
`the data Symbols to be interleaved, Separating adjacent ones
`of the punctured data Symbols in accordance with the
`interleaving.
`13. An apparatus of interleaving data Symbols, compris
`ing:
`a means for permuting rows and columns of a matrix of
`N. rows and N. columns, in which data symbols to be
`interleaved are presented row by row, in accordance
`with:
`
`row permutation (k) = alk + f(i)mod N,
`column permutation
`(i) = al+ f(k)mod N.
`
`where 1,0k) represents a data Symbol with a row index k, k
`is an integer from 1 to N, O, is an integer, f(1) is a non-zero
`function of a column index 1, I is an integer from 1 to N,
`l(l) represents a data Symbol with the column index 1, C is
`an integer, f(k) is a Zero or a function of the row index k,
`and modN, and modN represent modulo-N and modulo-N
`arithmetic respectively, interleaved data Symbols being
`derived from the matrix column by column.
`14. The apparatus of claim 13, wherein f(i)=ml, where m
`is an integer.
`15. The apparatus of claim 14, wherein m=1.
`16. The apparatus of claim 14, wherein m is approxi
`mately equal to N/N.
`17. The apparatus of claim 13, wherein f(k) is zero.
`18. The apparatus of claim 13, wherein f(k)=nk, where n
`is an integer.
`19. The apparatus of claim 18, wherein n=1.
`20. The apparatus of claim 13, wherein C, is the largest
`prime number less than N/2.
`21. The apparatus of claim 13, wherein C is the largest
`prime number less than N/2.
`22. The apparatus of claim 13, wherein a number of data
`symbols to be interleaved is less than N.N.
`23. The apparatus of claim 13 further comprising:
`a means for determining one or more matrix positions in
`which data symbols to be interleaved are not
`represented, interleaved data Symbols not being derived
`from Such determined matrix positions.
`24. A method for Symbol interleaving arranged to be
`carried by an apparatus of claim 13.
`25. An apparatus for interleaving data Symbols compris
`Ing:
`a memory arranged to Store data Symbols to be
`interleaved, the memory having Storage locations rep
`resenting rows and columns of a matrix of N, rows and
`N. columns, the data Symbols to be interleaved being
`represented row by row in Said matrix;
`an address circuit for reading the Stored data Symbols in
`an interleaved manner as interleaved data Symbols from
`
`

`

`US 6,732,316 B1
`
`the Storage locations of the memory So that the inter
`leaved data Symbols are derived column by column
`from a permutation of the matrix in accordance with:
`
`Row Permutation
`Column Permutation
`
`I (k)
`(T)
`Ic
`
`ICl + f (k) modN.
`
`where 1,0k) represents a data Symbol with a row index k, k
`is an integer from 1 to N, O, is an integer, f(1) is a non-zero
`function of a column index 1, I is an integer from 1 to N,
`l(l) represents a data Symbol with the column index 1, C.;
`is an integer, f(k) is Zero or a function of the row index k,
`and modN, and modN represent modulo-N and modulo-N
`arithmetic respectively.
`15
`26. The apparatus of claim 25, wherein f(1)=ml, where m
`is an integer.
`27. The apparatus of claim 26, wherein m=1.
`28. The apparatus of claim 26, wherein m is approxi
`mately equal to N/N.
`29. The apparatus of claim 25, wherein f(k) is zero.
`30. The apparatus of claim 25, wherein f(k)=nk, where n
`is an integer.
`
`10
`31. The apparatus of claim 30, wherein n=1.
`32. The apparatus of claim 25, wherein C, is the largest
`prime number less than N/2.
`33. The apparatus of claim 25, wherein C is the largest
`prime number less than N/2.
`34. The apparatus of claim 25, wherein a number of data
`symbols to be interleaved is less than N.N.
`35. The apparatus of claim 34 further comprising:
`a generator for determining of one or more matrix posi
`tions in which data symbols to be interleaved are not
`represented, interleaved data Symbols not being derived
`from Such determined matrix positions.
`36. A method for symbol interleaving arranged to be
`carried by an apparatus of claim 25.
`37. The apparatus of claim 25, wherein the memory
`includes Storage of adjacent data Symbols that are punctured,
`the interleaver being configured to Separate the adjacent data
`Symbols that are punctured by a distance in accordance with
`the interleave.
`
`

`

`UNITED STATES PATENT AND TRADEMARK OFFICE
`CERTIFICATE OF CORRECTION
`
`PATENT NO. : 6,732,316 B1
`DATED
`: May 4, 2004
`INVENTOR(S) : Wen Tong et al.
`
`Page 1 of 1
`
`It is certified that error appears in the above-identified patent and that said Letters Patent is
`hereby corrected as shown below:
`
`Column 8
`Line 47, “...Nf2...' Should be -- ...N/2... --.
`Line 52, "... 13...' Should be -- ...22... --.
`
`Column 10
`Line 3, “...Nf2...' Should be -- ...N/2... --.
`Line 7, "...N.N...' Should be -- ...N.N... --.
`
`Signed and Sealed this
`
`Seventeenth Day of August, 2004
`
`WDJ
`
`JON W. DUDAS
`Acting Director of the United States Patent and Trademark Office
`
`