Static information storage and retrieval – Addressing
Reexamination Certificate
2000-07-13
2002-03-26
Fears, Terrell W. (Department: 2824)
Static information storage and retrieval
Addressing
C365S185030, C365S231000
Reexamination Certificate
active
06363026
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention
The present invention relates generally to a multi-stage channel interleaver/deinterleaver for a radio communication system, and in particular, to an address generating device for use in a multi-stage channel interleaver/deinterleaver.
2. Description of the Related Art
Generally, a radio communication system in which there exists a channel fading effect, performs channel interleaving and deinterleaving for mitigating the channel fading effect in order to ensure stable communication of digital source data to be transmitted by wire or wirelessly. For example, an IMT-2000 (International Mobile Telecommunication-2000) radio communication system, i.e., UMTS (Universal Mobile Telecommunication System) or CDMA-2000 (Code Division Multiple Access-2000) radio communication system, includes channel interleaver and deinterleaver for mitigating the channel fading effect.
With regard to a fundamental radio frame structure of the 3GPP (3
rd
Generation Partnership Project), the radio frame has a length of 10 ms and is comprised of 16 time slots. Therefore, standardization for each part of the system tends to be carried out based on the above frame structure. A fixed size multi-stage interleaver (FS-MIL) which is determined as a working assumption of a 2
nd
interleaver is a 2-dimensional interleaver, in which the number of columns is fixed to 32. The MIL interleaver is designed to support a frame structure comprised of 16 time slots, and transmits data corresponding to 2 columns per time slot. Since the 1
st
interleaver and the 2
nd
interleaver both have a hardware structure supporting the number of columns which is a power of 2, it is possible to support both the 1
st
interleaver and the 2
nd
interleaver using one hardware module, thus reducing the hardware complexity.
In the meantime, harmonization of the CDMA-2000 system, which is North-American IMT-2000 system, and the European UMTS system is in progress. However, the CDMA-2000 system uses a radio frame structure comprised of 16 time slots per frame, and the UMTS uses a radio frame structure comprised of 15 time slots per frame. Therefore, it is not possible to use the existing CDMA-2000 channel interleaver, designed based on the 16 time slots per frame, for a UMTS channel interleaver. Thus, it is necessary to design the UMTS channel interleaver based on 15 time slots per frame.
FIG. 1
illustrates a fundamental MIL interleaving technique performed in the general 2
nd
interleaver. A 10 ms input sequence is interleaved in the manner shown in FIG.
1
. When the length of an input sequence is L≦F×B, the input sequence is stored in a 2-dimensional memory having a size of F×B, where F is the number of columns of the interleaver and B is the number of rows of the interleaver. Further, B is a minimum integer which satisfies L≦F×B for fixed F. At this point, the data is sequentially stored in the interleaver one row at a time. An other words, the data is stored in the first row and fill the first row before the data is stored in the second row and so on. Thus, the data is stored one row at a time starting from the top row with the data fills the bottom row. The sequentially stored input sequence are sequentially output as data corresponding to the respective rows of a given column in the order of the inter-column permutation pattern shown in Table 1 below. Table 1 shows a permutation pattern for F=32.
TABLE 1
Inter-column
Interleaving Span
Number of Columns (F)
Permutation Patterns
10 ms
1
C0
20 ms
2
C0,C1
30 ms
4
C0,C2,C1,C3
40 ms
8
C0,C4,C2,C6,C1,C5,C3,C7
FIG. 2
illustrates an address generating device for the MIL interleaver according to the prior art. In this address generating device, the number of columns is 32 which is a power of 2. Although a description of the address generating device will be made for the case where it is applied to the channel interleaver, it will be understood by those skilled in the art that the address generating device may be applied to the channel deinterleaver.
Referring to
FIG. 2
, the address generating device includes a row counter
210
, a column counter
230
, a mapper
240
, a 5-bit shifter
220
, and an adder
250
, which are the elements for generating an address to be used for the 2
nd
channel interleaver. The row counter
210
and the column counter
230
count rows and columns of an interleaving memory (not shown), respectively. In the memory, the input data is sequentially stored in the order of row and column. The mapper
240
maps the columns counted by the column counter
230
to permuted columns. For example, the mapper
240
outputs the columns counted by the column counter
230
as permuted columns according to the inter-column permutation pattern shown in Table 1. The bit shifter
220
bit-shifts the value counted by the row counter
210
. The adder
250
forms a new address by using the output of the bit shifter
220
as the most significant bits(MSB) of the new address and by using the output of the mapper
240
as the least significant bits(LSB) of the new address. Such an address is used to output the data which was sequentially stored in the memory in the order of row and column, as 2-dimensional interleaved data.
In the meantime, the conventional address generating device for the MIL interleaver includes the bit shifter
220
. Such a bit shifter
220
is implemented by a 5-bit shifter, when the number of the columns is 32 which is a power of 2.
As described above, when the number of the columns is 32 which is a power of 2, a bit shift operation is performed by the 5-bit shifter
220
in order to obtain an address from the row counter
210
. Here, the bit shifter
220
has a low hardware complexity.
However, if the number of time slots per frame is changed from 16 to 15, the number of the columns will also be changed, and there is a high probability that the new number of columns will not be a power of 2. For example, if it is assumed that the number of columns per time slot is 2 and the total number of the columns is 30, 30 multipliers are required and the hardware size of the multipliers will increase about twice the hardware size for the MIL 2
nd
interleaver. When the number of columns of the MIL interleaver is not a power of 2 as stated above, it is not possible to use the bit shift operation as in the MIL 1
st
interleaver for which the number of columns is 1, 2, 4 and 8. Therefore, there are required the multipliers, the number of which corresponds to the number of columns. In this case, the total hardware complexity of the interleaver increases about two times.
SUMMARY OF THE INVENTION
It is, therefore, an object of the present invention to provide an address generating device for implementing a MIL interleaver with the decreased hardware complexity.
It is another object of the present invention to provide an address generating device for performing an interleaving operation without an increase in the hardware complexity of an interleaver, even when the number of the columns of the MIL interleaver is not a power of 2.
It is further another object of the present invention to provide a device for generating an address for MIL 1
st
and 2
nd
interleavers using a single module.
To achieve the above and other objects, There is provided an address generating device for reading data from an interleaver memory having B rows by F columns, where the data from the memory are interleaved one column at a time by following predetermined column permutation rule. In addition the number of columns in the interleaver memory, F is not equal to an integer power of 2, i.e. F≠2
k
where k is a positive integer. An row counter responsive to B clock pulses, output offset values from 0 to (B−1)×F in increments of F, each offset value outputted with successive clock pulses, and generates a carry signal when the B clock pulses are completed. A column counter increases a count value in increments of one in response to the carry signal. A mapper permutates a signal sequence output from the column cou
Kim Beong-Jo
Su Sung-il
Dilworth & Barrese LLP
Fears Terrell W.
Samsung Electronics Co,. Ltd.
LandOfFree
Address generating device for use in multi-stage channel... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Address generating device for use in multi-stage channel..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Address generating device for use in multi-stage channel... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2887941