Base-Band Interleaver for Code Division Multiple Access Mobile Telecommunication System

1. Technical Field

The present invention relates to an interleaving apparatus or interleaver for a Code Division Multiple Access (CDMA) mobile telecommunication system and, more particularly, to a base-band interleaver for forward traffic and paging channels preferably applicable to an IS-95 CDMA specification of telecommunication system.

2. Related Art

Common air interface (IS-95) standard is a mobile telecommunication standard which uses Code Division Multiple Access (CDMA) for signal transmission over communication channels. CDMA is a form of modulation technique for spread-spectrum multiple-access digital communications. In CDMA, a wide-band frequency channel is shared between several overlapping signals, each characterized by a specific pseudo random binary sequence that spreads the initial spectrum of the data to be transmitted.

In a mobile telecommunication environment, signal strength varies with location and movement of the mobile transmitter/receiver. Signal strength can significantly affect error rates which in turn effect the quality of communication. Due to varying signal strength, mobile telecommunication systems are susceptible to burst errors. Burst errors are groupings of errors that occur in adjacent bits of a data block as compared to errors that are dispersed over an entire block of data. A solution to varying signal strength and burst errors is to utilize an error correction scheme based on encoding and interleaving.

Generally, interleaving is used in conjunction with encoding (e.g., error-correcting codes) in order to lower the error rates of communication channels that are susceptible to burst errors. Interleaving is a technique in which encoded digital data is reordered before transmission in such a manner that any two successive digital data bits in the original data stream are separated by a predetermined distance in the transmitted data stream. Deinterleaving is the reverse of interleaving where data bits are reordered back to their original positions. According to the IS-95 standard, data is encoded and interleaved prior to transmission and decoded and deinterleaved after reception. Such deinterleaving disperses burst errors, which can occur during transmission throughout the data block. This dispersal of bit errors enables the decode to treat the burst errors as if they weie random errors, and maximize the capability of the decoder to correct the errors.

One class of interleavers is known as periodic interleavers, for which the interleaving permutation is a periodic function of time. Examples are block interleavers, which accept data in blocks and perform identical permutations over each data block, and convolutional interleavers have no fixed block structure, but perform a periodic permutation over a semi-infinite sequence of coded symbols. A block interleaver typically takes the coded symbols and writes them by columns into a matrix with rows and columns. The permutation consists of reading these symbols out of the matrix by rows prior to transmission. The deinterleaver then performs the inverse operation. Symbols are written into the deinterleaver by rows and read out by columns. In contrast to block interleavers, convolutional interleavers requires the coded symbols to shift sequentially into a bank of registers with increasing length. With each new code symbol, a commutator switches to a new register and the new code symbol is shifted in while the oldest code symbol in that register is shifted out to the communication channel. The deinterleaver has a similar structure and performs the inverse operation. Exemplars of contemporary block and convolutional interleavers are disclosed in U.S. Pat. No. 4,394,642 for Apparatus For Interleaving And De-Interleaving Data issued to Currie et al., U.S. Pat. No. 4,559,625 for Interleavers For Digital Communications issued to Berlekamp et al., U.S. Pat. No. 4,742,517 for Interleaving Circuit issued to Takagi et al., U.S. Pat. No. 5,042,033 for RAM-hnplemented Convolutional Interleaver issued to Costa, U.S. Pat. No. 5,056,112 for Interleaving In Coded Modulation for Mobile Radio issued to Wei, U.S. Pat. No. 5,136,588 for Interleaving Method And Apparatus issued to Ishijima, U.S. Pat. No. 5,241,563 for Method And Apparatus For Communicating Interleaved Data issued to Paik et al., U.S. Pat. No. 5,276,827 for Data Buffer For The Duration Of Cyclicaly Recurrent Buffer Periods issued to Delaruelle et al., U.S. Pat. No. 5,535,220 for Forward Error Correcting Transmitter And Receiver issued to Kanno et al., U.S. Pat. No. 5,537,420 for Convolutional Interleaver With Reduced Memory Requirements And Address Generator Therefor issued to Huang, U.S. Pat. No. 5,636,224 for Method And Apparatus For Interleave/Deinterleave Addressing In Data Communication Circuits issued to Voith et al., and U.S. Pat. No. 5,659,580 for Data Interleaver For Use With Mobile Communication Systems And Having A Contiguous Counter And An Address Twister issued to Partyka.

Many contemporary interleavers utilize a memory look-up table to determine the proper interleaving address. While the use of look-up table minimizes the processing capability required to generate interleaving addresses. However, the look-up table requires a significant amount of memory and memory space for implementation. Moreover, most contemporary interleavers for forward traffic channel and paging channel in a base-band defined in accordance with the IS-95 CDMA standard require a general-purpose memory of 512 bytes for the look-up table. However, I have noted that the look-up table usually requires only 384 bytes of the 512-byte memory chip, the remaining 128 bytes of memory may become wasteful.

Accordingly, it is therefore an object of the present invention to provide an improved base-band interleaver for CDMA mobile telecommunication system.

It is also object to provide an improved base-band interleaver for forward traffic channel and paging channel with a simplified circuit construction.

It is another object to provide a base-band interleaver for forward traffic channel and paging channel with reduced interleaving memory capacity.

The above and other objects of the present invention can be achieved by a base-band interleaver for a CDMA mobile telecommunication system provided with a modulo-16 circuit connected to receive an index selected from successive indexes 0 to 383 corresponding to input data to divide the index by a numeral 16, and provide a remainder of the divided index. A bit invertor is connected to the modulo-16 circuit to perform bit inversion of an output from the modulo-16 circuit and determine a column position to write in the data with interleaving taken. A quotient-16 circuit is connected to receive the index to produce a quotient of dividing of the index by the numeral 16. A code converter having a row table by which the quotient is respectively matched to a row position to be written with interleaving taken, to generate a row position corresponding to the quotient. A 24-based counter counts a data read clock to provide a 24-based counted value corresponding to a selected row of output data to read out so as to output the interleaved written data selectively. A 16-based counter receives a carry of the 24-based counter to provide a 16-based counted value corresponding to a selected column of output data to read out. A memory having therein an interleaving table inclusive of 32 rows and 16 columns, is used to store input data written to a selected position of the interleaving table according to the outputs of the bit invertor and the code converter, and to provide therefrom output data read out from the position corresponding to the output of the 16-based counter and the output of the 24-based counter.

The present invention is more specifically described in the following paragraphs by reference to the drawings attached only by way of example.

A more complete appreciation of the present invention, and many of the attendant advantages thereof, will become readily apparent as the same becomes better understood by reference to the following detailed description when considered in conjunction with the accompanying drawings in which like reference symbols indicate the same or similar components, wherein:

FIG. 1 illustrates an exemplary input table of 14400 Bps, 9600 Bps, 7200 Bps, 3600 Bps and 1800 Bps for the forward traffic and paging channel interleaver;

FIG. 2 illustrates an exemplary interleaving table of 14400 Bps, 9600 Bps, 7200 Bps, 3600 Bps and 1800 Bps for the forward traffic and paging channel interleaver;

FIG. 3 illustrates an exemplary input table of 4800 Bps for the forward traffic and paging channel interleaver;

FIG. 4 illustrates an exemplary interleaving table of 4800 Bps for the forward traffic and paging channel interleaver;

FIG. 5 illustrates an exemplary input table of 2400 Bps for the forward traffic and paging channel interleaver;

FIG. 6 illustrates an exemplary interleaving table of 2400 Bps for the forward traffic and paging channel interleaver;

FIG. 7 illustrates an exemplary input table of 1200 Bps for the forward traffic and paging channel interleaver;

FIG. 8 illustrates an exemplary interleaving table of 1200 Bps for the forward traffic and paging channel interleaver;

FIG. 9 illustrates an input table of the input data according to a preferred embodiment of the present invention;

FIG. 10 illustrates an interleaving table according to a preferred embodiment of the present invention;

FIG. 11 illustrates a table indicative of the relationship between columns of FIGS. 9 and 10;

FIG. 12 illustrates a table indicative of the relationship between rows of FIGS. 9 and 10;

FIG. 13 is a schematic block diagram for a base-band interleaver constructed according to a preferred embodiment of the present invention; and

FIG. 14 is a schematic block diagram of a CDMA mobile telecommunication system utilizing the base-band interleaver constructed according to the preferred embodiment of the present invention.

Referring now to the drawings and particularly to FIG. 1, which illustrates an exemplary input table of 14400 Bps, 9600 Bps, 7200 Bps, 3600 Bps and 1800 Bps for a forward traffic and paging channel interleaver for use in a CDMA mobile telecommunication system defined in accordance with the IS-95 standard.

As shown in FIG. 1, the input table consists of 24 rows and 16 columns in matrix, fixing the data transmission speed inputted to the input table to 9600 Bps. Therefore, a sequential input of data in 9600 Bps of transmission speed is carried out from a first position, row 1 and column 1, of the matrix to its last position, row 24 and column 16, in which a respective index is assigned according to the order of the input data. For example, an index 1 represents a first input data to the input table and an index 2 represents its second input data. Likewise, it is noted in the input table that an address of index 1 corresponds to row 1 and column 1, an address of index 2 to row 2 and column 1, an address of index 3 to row 3 and column 1, and an address of index 4 to row 4 and column 1. Data recorded in these addresses are delivered to the interleaver according to the index order, in which the interleaver interleaves the input data to be written into a memory.

FIG. 2 illustrates an exemplary interleaving table, written in the memory, of 14400 Bps, 9600 Bps, 7200 Bps, 3600 Bps and 1800 Bps for the forward traffic and paging channel interleaver. The interleaving table has the same structure as that of the input table of FIG. 1, and consists of 24 rows and 16 columns of matrix table, setting its data transmission speed to 9600 Bps. In the interleaving table, data index is arranged so that an index 1 is positioned in row 1 and column 1, an index 2 in row 1 and column 9, and an index 3 in row 1 and column 5, in which arrangement the data indexing of the interleaving table is carried out dispersedly rather than sequentially.

FIG. 3 illustrates an exemplary input table of 4800 Bps for the forward traffic and paging channel interleaver, which has a transmission speed twice lower than that of 9600 Bps, but has been designed so as to be applicable to the data of 9600 Bps of transmission speed. Thus, a single 4800 Bps data is positioned in two successive addresses of the input table, so that these two indexes make one data index. For example, as seen in FIG. 3, the index of the first data is represented in two indexes "1". Therefore, the interleaver makes interleaving of the data positioned in the input table at 9600 Bps transmission speed, during which time the interleaver separately recognizes those two successive indexes representing one data.

FIG. 4 illustrates an exemplary interleaving table of 4800 Bps for the forward traffic and paging channel interleaver as an interleaving output of the interleaver of FIG. 3. As shown in FIG. 4, two distant indexes are separately interleaved. For example, the first index 1 is interleaved into a position of row 1 and column 1 and the second index 1 is then interleaved to another position of row 1 and column 9 by the interleaver.

FIG. 5 illustrates an exemplary input table of 2400 Bps for the forward traffic and paging channel interleaver, which has a transmission speed four times lower than that of 9600 Bps, but has been designed so as to be applicable to the data of 9600 Bps of transmission speed. Thus, one 2400 Bps data extends through four successive addresses of the input table, so that these four sequential indexes make one data index. For example, as seen in FIG. 5, the index of the first data is represented in four indexes "1". Therefore, the interleaver makes interleaving of the data positioned in the input table at 9600 Bps transmission speed, during which time the interleaver separately recognizes those four successive indexes representing one data.

FIG. 6 illustrates an exemplary interleaving table of 2400 Bps for the forward traffic and paging channel interleaver as an interleaving output of the interleaver of FIG. 5. As shown in FIG. 6, four successive indexes are separately interleaved. For example, the first index 1 is interleaved to the position of row 1 and column 1, the second index 1 to the position of row 1 and column 9, the third index 1 to the position of row 1 and column 5, and the fourth index 1 to the position of row 1 and column 13 by means of the interleaver.

FIG. 7 illustrates an exemplary input table of 1200 Bps for the forward traffic and paging channel interleaver, which has a transmission eight times lower than that of 9600 Bps, but has been designed so as to be applicable to the data of 9600 Bps of transmission speed. Thus, one 1200 Bps data extends through eight successive addresses of the input table, so that these eight sequential indexes make one data index. Hence, for example, as seen in FIG. 7, the index of the first data may be represented in eight indexes "1". Therefore, the interleaver makes interleaving of the data positioned in the input table at 9600 Bps transmission speed, during which time the interleaver separately recognizes those eight successive indexes representing one data.

FIG. 8 illustrates an exemplary interleaving table of 1200 Bps for the forward traffic and paging channel interleaver as an interleaving output of the interleaver of FIG. 7. As shown in FIG. 8, eight successive indexes are separately interleaved. For example, the first index 1 is interleaved to the position of row 1 and column 1, the second index 1 to the position of row 1 and column 9, the third index 1 to the position of row 1 and column 5, the fourth index 1 to the position of row 1 and column 13, the fifth index 1 to the position of row 1 and column 3, the sixth index 1 to the position of row 1 and column 11 index 1 to the position of row 1 and column 7, and the eighth index 1 to the position of row 1 and column 15 by means of the interleaver.

As described, the interleaving operation is carried out at a fixed 9600 Bps transmission speed in spite of difference of data transmission speeds. Therefore, it is noted that the index is not generated in data unit, but generated in 9600 Bps data unit for all the data. If the input data having the above indexes are inputted to the interleaver capable of interleaving at the 9600 Bps transmission speed, then the various transmission speeds of data could be interleaved by using a single interleaver.

Typical interleavers for forward traffic and paging channel in a base-band defined in accordance with the IS-95 CDMA standard utilize a memory look-up table, which is a reference table by which each index of the input data is interleaved to its corresponding address on the interleaving table. Therefore, as an index of one input data to interleave is provided to the interleaver, the interleaver reads the corresponding address on the interleaving table to thereby store the read data onto the address. For example, if the data of index 1 is inputted, then the position of row 1 and column 1 of the interleaving table corresponding to the index 1 is read out to thereby store the data of the index 1 in the same position. This kind of interleaving method generally does not require complicated operation, but requires memories to store therein such a look-up table for interleaving.

Moreover, most interleavers for forward traffic and paging channel in a base-band defined in accordance with the IS-95 CDMA standard are preferably provided with a general-purpose memory of 512 bytes for the look-up table. However, as I have described earlier, the look-up table usually requires only 384 bytes of the 512-byte memory chip, the remaining 128 bytes of memory may become wasteful.

Turning now to an interleaver for forward traffic and paging channel in a base-band for use in an IS-95 CDMA mobile telecommunication system as contemplated by the present invention. The interleaver is intended to perform interleaving on basis of 9600 Bps input data. Thus, an interleaver of a preferred embodiment of the present invention is adopting an input table and an interleaving table generated on basis of the above 9600 Bps signal.

FIG. 9 illustrates an input table of the input data according to the preferred embodiment of the present invention, while FIG. 10 illustrates an interleaving table according to the preferred embodiment. Both input table and interleaving table are provided 384 bits, indexes of which are referred to as index 0 to index 383. Further, rows and columns of the input table and interleaving table are referred to as row 0 to row 23 and column 0 to 15, respectively. The input table is provided with 384 indexes which are arranged in sequence from an index 0 of row 0 and column 0 up to an index 383 of row 23 and column 15, as shown in FIG. 9. Likewise, the interleaving table is provided with 384 indexes which are arranged in sequence from an index 0 of row 0 and column 0 up to an index 383 of row 23 and column 15, as shown in FIG. 10.

Referring to the input table as shown in FIG. 9, and interleaving table as shown in FIG. 10, the following relation can be appreciated. That is to say, if any index of the output table is to be divided by a numeral 16, its remainder is then represented in four bits, and these four bits are taken by bit-inversion, then it corresponds to a particular column where the above index is positioned in the interleaving table. Here, the bit-inversion could be usually provided by conversion of the bit position as indicated in the following table.

Referring to the table, the bit-inversion is performed such that bit 0 is replaced by bit 3, bit 1 by bit 2, bit 2 by bit 1, and bit 3 by bit 0.

FIG. 11 illustrates the exemplary way of obtaining columns of the interleaving table by using the above-mentioned index, in which the columns of index 0 through index 15 obtained are set forth. As this index is divided by a numeral 16, its remainder can be taken as modulo-16, which can be then represented in four bit format, thereby making modulo bits. The modulo bits are then inverted according to the above table to perform the bit-inversion, by which a column indicated by the inverted bit corresponds to a selected column of the interleaving table. For example, if the modulo-16 of the index 0 is zero, then the modulo bit is 0000, the bit inversion is 0000, and a column of the interleaving table is 0. This means that when data of index 0 of the input table is interleaved, the data of index 0 is positioned in column 0 of the interleaving table. Similarly, it will be appreciated that the modulo-16 of the index 1 is 1, the modulo bit is 0001, the bit inversion is 1000, and a column of the index 1 in the interleaving table is column 8. Thus, it means that when data of index 1 of the input table is interleaved, the data of index 1 is positioned in column 8 of the interleaving table. As a result, it is noted that respective columns of those indexes of the input table and the interleaving table are matched to each other one by one by a simple operation.

In the meanwhile, the relation between indexes of the input table and rows of the interleaving table is described hereinafter, with reference to FIGS. 9 and 10. When the index is divided by 16, its quotient is taken as a quotient-16. In order to obtain a row from the above quotient-16, the present invention uses a row table as set forth in FIG. 12 since it is not possible to find any relationship between the quotient-16 and the rows by using any simple operation. For example, the row table of FIG. 12 is arranged such that if the quotient-16 is zero, then the row becomes row 0, if the quotient-16 is 1, then the row becomes row 12 , if the quotient-16 is 2, then the row becomes row 6, and likewise, if the quotient-16 is 23, then the row becomes row 23.

Accordingly, in case that the quotient-16 is zero, the indexes will be 0, 1, 2, - - - 14, 15, which are located in row 0 as shown in the interleaving table of FIG. 10. Further, in case that the quotient-16 is 1, the indexes will be 16, 17, 18 - - - 30, 31. As above described, those rows of the row table of FIG. 12 and the rows corresponding to the quotient-16 are identical to each other. Here, the row table can be embodied by much smaller size of memory, for example, 24 bytes, as compared to a larger size of memory, for example, 512 bytes needed upon using a general purpose memory.

Refer now to FIG. 13 which illustrates a base-band interleaver constructed according to a preferred embodiment of the present invention with correlation of indexes. As shown in FIG. 13, the base-band interleaver includes a modulo-16 10, a bit inverter 12, a memory 14, a quotient-16 16, a code converter 18, a 16-based counter 20, a 24-based counter 22.

Modulo-16 circuit 10 of the interleaver receives the index, which is divided by 16, and then provides its remainder to a bit invertor 12. This bit invertor makes bit-inversion of an input modulo-16 value from the modulo-16 circuit, which bit inverted value corresponds to a given column on the interleaving table. This column is inputted to a memory 14 having therein the interleaving table as shown in FIG. 10.

Quotient-16 circuit 16 of the interleaver also receives the index, which is divided by 16, and then provides its divided quotient to a code converter 18 having the column table as shown in FIG. 11. Accordingly, the code converter 18 reads out a column corresponding to the above quotient from the column table and then provides the read column to the memory 14. Thus, the memory receives both of the column and the row, by which the memory writes the input data into a particular position according to these row and column.

In the meantime, a main system (not shown) provides a data read clock, which is delivered to a 24-based counter 22, when it requires to output the data written in the memory by the above interleaving operation. The 24-based counter 22 makes count of the input data clock to therefrom provide a counted value, which indicates a selected row of the interleaving table in the memory 14.

Further, a carry provided from the 24-based counter is then delivered to a 16-based counter 20, which makes a count of the carry and provides the counted value to the memory 14. This counted value represents a selected column of the interleaving table. Therefore, the memory 14 receives the above row and column and in response thereto, provides data of a corresponding position as an output.

As apparent from the foregoing description, the present invention provides a base-band interleaver utilizing the correlation between index positions of the interleaving table in case the indexes of data are written by interleaving. Further, in case of being written by interleaving with the indexes of data having no correlation, the position in the interleaving table is sought by using a simple small-capacity code converter. As a result, the present invention requires a much smaller capacity of memory, for example, only 24 bytes or so, for a base-band interleaver, as compared to contemporary interleavers which usually require at least 384 bytes of memory capacity. Hence, the base-band interleaver can be constructed with lower production cost than that of any contemporary interleavers.

FIG. 14 is a schematic block diagram of a CDMA mobile telecommunication system utilizing the base-band interleaver constructed according to the preferred embodiment of the present invention. That is, the base-band interleaver as shown in FIG. 13 may be incorporated into the CDMA mobile telecommunication system 100 which includes a base station 110 and one or more mobile stations 120. Base station 110 includes an encoder 111, a base-base interleaver 112 as shown in FIG. 13, a modulator 113, a demodulator 114, a deinterleaver 115 which is constructed similarly to the interleaver as shown in FIG. 13 only to perform the inverse operation, and a decoder 116. Mobile station 120 includes a demodulator 121, a deinterleaver 122 similar to that of the base station 110, a decoder 123, an encoder 124, an interleaver 125 similar to that of the base station 110, and a modulator 126.

Base station 110 receives data from a telephone network 130. The network data is encoded by encoder 111, and then interleaved by interleaver 112 by operations as described with reference to FIG. 13 in accordance with IS-95 standard. Such interleaving provides protection against burst errors by spreading out, or randomizing, errors that occur in short burst of time. The interleaved data from interleaver 112 is then modulated in a conventional modulator 113 and transmitted via an antenna 132 in the radio frequency (RF) domain. Mobile station 120 receives the transmitted data from the base station 110 via an antenna 134. The received data is demodulated by a conventional demodulator 121, and is deinterleaved by deinterleaver 122 and decoded by decoder 123. The decoded and deinterleaved data is output to a user 136.

Transmission from mobile station 120 to base station 110 occurs in the same fashion. Mobile station 120 receives data from the user 136 for encoding via encoder 124, interleaving via interleaver 125, and then modulation via modulator 126 for transmission via antenna 134. Base station 110, in turns, receives the transmitted data from the mobile station 120 for demodulation via demodulator 114, deinterleaving via deinterleaver 115, and then decoding via decoder 116. The decoded and interleaved data is output to telephone network 130.

As contemplated by the present invention, the interleaving process performed by those base-band interleavers in the manner described with reference to FIG. 13 which utilize the correlation between index positions of the interleaving table in case the indexes of data are written by interleaving. When the indexes of data having no correlation, the position in the interleaving table is sought by using a simple small-capacity code converter. As a result, a much smaller capacity of memory, for example, only 24 bytes or so, is required for a base-band interleaver, and a simpler circuit construction is provided to minimize production cost.

While there have been illustrated and described what are considered to be preferred embodiments of the present invention, it will be understood by those skilled in the art that various changes and modifications may be made, and equivalents may be substituted for elements thereof without departing from the true scope of the present invention. In addition, many modifications may be made to adapt a particular situation to the teaching of the present invention without departing from the central scope thereof. Therefore, it is intended that the present invention not be limited to the particular embodiment disclosed as the best mode contemplated for carrying out the present invention, but that the present invention includes all embodiments falling within the scope of the appended claims.