DE20202361U1 - Device for coding / decoding channels in a mobile communication system - Google Patents

Description

GRÜNECKER KINKELDEY StCJCKMAlFt &.$CtöWANHÄUSSER

LAW FIRM

GKS & S MAXIMIUANSTRASSE 58 D-80538 MUNICH GERMANY LAWYERS

MUNICH

DR. HELMUT EICHMANN

GERHARD BARTH DR. ULRICH BLUMENRÖDER, LLM.

CHRISTA NIKLAS-FALTER DR. MAXIMILIAN KINKELDEY, LLM.

SONJA SCHAEFFLER

DR. KARSTEN BRANDT

MICHAEL J. FRANKE, LLM.

UTE STEPHANl

DR. BERND ALLEKOTTE, LLM.

DR. ELVIRA PFRANG, LLM.

PATENT ATTORNEYS PATENT ATTORNEYS EUROPEAN PATENT ATTORNEYS EUROPEAN !PATENT ATTORNEYS

MUNICH

DR. HERMANN KINKELDEY

PETER H. JAKOB

WOLFHARD MEISTER

HANS HILGERS

DR. HENNING MEYER-PLATH

ANNELLE EHNOLD

THOMAS SCHUSTER

DR. KLARA GOLDBACH

MARTIN AUEENANGER

GOTTFRIED KUTZSCH

DR. HEIKE VOGELSANG-WENKE

REINHARD KNAUER

DIETMAR KUHL

OR. FRANZ-JOSEF ZIMMER

BETTINA K. REICHELT

DR. ANTON K. PFAU

DR. UDO WEIGELT

RAINER BERTRAM

JENS KOCH, M.S. (U of PA) M.S.

BERND ROTHAEMEL

DR. DANIELA KINKELDEY

DR.

THOMAS W. UUBENTHAL

BERLIN

PROF. DR. MANFRED BÖNING

DR. PATRICK ERK, M.S. (MIT)·

•PATENT ATTORNEY

COLOGNE

DR. MARTIN .DROPMANN

CHEMNITZ MANFRED SCHNEIDER

OF COUNSEL PATENT ATTORNEYS

AUGUST GRÜNECKER DR. GUNTER BEZOLD DR. WALTER LANGHOFF

DR. WILFRIED STOCKMAIR (-1996)

YOUR REF.

OUR REF.

DATE

G4665-034/gr 15.02.02

SAMSUNG ELECTRONICS CO., LTD. 416, Maetan-dong, Paldal-gu, Suwon-city, Kyungki-do REPUBLIC OF KOREA

DEVICE FOR ENCODING/DECODING CHANNELS IN A MOBILE COMMUNICATIONS SYSTEM

GRÜNECKER KIN&ELDEy. TEL,. . + 4,9 8^.21 23 SO

STOCKMAIR &SCHV^lSttfUSSER"::;*::&zgr;&Agr;&KHgr;«&phgr; 3) +.49$. 22 92; 87 · MAXIMIUANSTR.S8 : : ,· : J ,· I fAXJGR^. + ^ ß? J1 BiJ 92 93;

D-80538 MUNICH* **** "* htt^WW^rtjneclfeVde *'" *

GERMANY ■ e-mail: postmaster@grunecker.de

DEUTSCHE BANK MUNICH No. 17 51734 BLZ 700 ,700 SWIFT: DEUT DE MM

The present invention relates generally to coding/decoding technology in a communication system, and more particularly to a coding/decoding apparatus for a CDMA (Code Division Multiple Access) mobile communication system using an error correction code.

In an IMT-2000 (International Mobile Telecommunication-2000) system, a future mobile communication system using CDMA, user data for a voice service, a picture service and a data service are transmitted along with control data for operating the services. It is important to minimize errors occurring during the transmission of such data in order to improve the quality of services. For this purpose, error correction codes are used to correct data bit errors in order to minimize the errors occurring during the transmission of the data. Since the use of error correction codes is intended to minimize the data bit errors of the transmitted data, it is important to use optimal error correction codes.

Usually, linear codes are used for the error correction codes because it is easy to analyze their performance. Hamming distance distribution for codewords of error correction codes serves as a measure that indicates the performance of linear codes. The "Hamming distance" is the consecutive number of non-zero symbols in a codeword. That is, for a certain codeword "0111", the consecutive number of "1"s contained in the codeword is 3, so the Hamming distance is 3. The smallest value among the values of the Hamming distance is called the "minimum distance", and an increase in the minimum distance of the codeword improves the error correction performance of the codeword. So the "optimal" code is a code with the optimal error correction performance.

In a paper An Updated Table of Minimum-Distance Bounds for Binary Linear Codes (AE Brouwer and Tom Verhoeff, IEEE Transactions on information Theory VOL 39, NO. 2, MARCH 1993) a minimum inter-code distance is disclosed that depends on the input and output values of the binary linear codes and produces optimal codes depending on the number of coded symbols generated by encoding input information bits.

The paper discloses a (12,5) linear code in which the number of input information bits is 5 and the number of output coded symbols is 12, and the minimum distance of its optimal code is 4. Therefore, when using the (12,5) linear code, consideration must be given to both using the optimal code whose minimum distance is 4 and generating the optimal code whose minimum distance is 4 while minimizing the complexity of the hardware.

In addition, the paper discloses a (24,6) linear code in which the number of input information bits is 6 and the number of output coded symbols is 24. The minimum distance of its optimal code is 10. Therefore, when using the (24,6) linear code, it is necessary to consider both the use of the optimal code whose minimum distance is 10 and the generation of the optimal code whose minimum distance is 10 while minimizing the complexity of the hardware.

Therefore, an object of the present invention is to provide a coding apparatus for generating an optimal (12,5) code word in a mobile communication system using an error correction code.

Another object of the present invention is to provide an apparatus for determining puncturing positions used in generating an optimal (12,5) code word by puncturing a first order Reed-Muller code word consisting of 16 encoded symbols.

Another object of the present invention is to provide an apparatus for decoding a received (12,5) code word in a mobile communication system using an error correction code.

Another object of the present invention is to provide a coding apparatus for generating an optimal (24,6) code word in a mobile communication system using an error correction code.

Another object of the present invention is to provide an apparatus for determining puncturing positions used in generating an optimal (24,6) code word by puncturing a first order Reed-Muller code word consisting of 32 encoded symbols.

Another object of the present invention is to provide an apparatus for decoding a received (24,6) code word in a mobile communication system using an error correction code.

According to a first aspect of the present invention, there is provided an apparatus for encoding a 5-bit input information bit stream into a (12,5) code word consisting of 12 coded symbols. The apparatus comprises a Reed-Muller encoder which receives the input information bit stream and generates a first order Reed-Muller code word consisting of 16 coded symbols, and a puncturing device which outputs an optimal (12,5) code word by puncturing four consecutive coded symbols from a stream of the 16 coded symbols forming the first order Reed-Muller code word starting with a coded symbol selected from the 1st, 3rd, 7th, 9th and 11th coded symbols.

According to a second aspect of the present invention, there is provided an apparatus for encoding a 5-bit input information bit stream into a (12,5) code word consisting of 12 coded symbols. The apparatus comprises a Reed-Muller encoder which receives the input information bit stream and generates a first-order Reed-Muller code word consisting of 16 coded symbols, and a puncturing device which outputs an optimal (12,5) code word by puncturing a coded symbol selected from the 2nd, 3rd, 6th and 7th coded symbols from a stream of the 16 coded symbols constituting the first-order Reed-Muller code word, and further puncturing three coded symbols at intervals of two symbols starting from the selected coded symbol.

According to a third aspect of the present invention, there is provided an apparatus for encoding a 5-bit input information bit stream into a (12,5) code word consisting of 12 coded symbols. The apparatus comprises a Reed-Muller encoder which receives the input information bit stream and generates a Reed-Muller

first-order code word consisting of 16 coded symbols, and a puncturing device which outputs an optimal (12,5) code word by puncturing a symbol selected from the 0th, 1st, 2nd, 4th, 5th and 6th coded symbols from a stream of the 16 coded symbols constituting the first-order Reed-Muller code word, and further puncturing three coded symbols at intervals of three symbols starting from the selected coded symbol.

According to a fourth aspect of the present invention, there is provided an apparatus for encoding a 6-bit input information stream into a (24,6) code word consisting of 24 encoded symbols. The apparatus comprises a Reed-Muller encoder that receives the input information bit stream and generates a first-order Reed-Muller code word consisting of 32 coded symbols, and a puncturing means that outputs an optimal (24,6) code word by selecting a coded symbol from the 2nd, 6th and 10th coded symbols from a stream of the 32 coded symbols constituting the first-order Reed-Muller code word, and puncturing the selected symbol, six coded symbols at intervals of three symbols starting from the selected coded symbol, and further puncturing a coded symbol at an interval of one symbol starting from a last symbol of the six punctured coded symbols.

The above and other objects, features and advantages of the present invention will become more apparent from the following detailed description when taken in conjunction with the accompanying drawings, in which:

Fig. 1 illustrates a structure of an encoding device according to a first embodiment of the present invention;

Fig. 2 illustrates in detail a structure of the Reed-Muller encoder shown in Fig. 1;

Fig. 3 illustrates a structure of a decoding apparatus according to the first embodiment of the present invention;

·

• · • *

Fig. 4 illustrates a structure of an encoding device according to a second embodiment of the present invention;

Fig. 5 shows in detail a structure of the Reed-Muller encoder shown in Fig. 4; and

Fig. 6 illustrates a structure of a decoding apparatus according to the second embodiment of the present invention.

A preferred embodiment of the present invention will be described below with reference to the accompanying drawings. In the following description, well-known functions or constructions are not described in detail since otherwise the invention would be obscured by unnecessary details.

The present invention provides two different embodiments. In a first embodiment, an encoding apparatus for generating an optimal (12,5) code word and a decoding apparatus for decoding the generated (12,5) code word in a mobile communication system using an error correction code are provided. In a second embodiment, an encoding apparatus for generating an optimal (24,6) code word and a decoding apparatus for decoding the generated (24,6) code word in a mobile communication system using an error correction code are provided. With the embodiments, an optimal code word is generated by puncturing symbols at certain positions from the encoded symbols that form a first order Reed-Muller code word. With the first embodiment, a first-order Reed-Muller code word consisting of 16 coded symbols is generated by receiving an information bit stream consisting of five bits and then generating a (12,5) code word by puncturing four coded symbols from the 16 coded symbols. With the second embodiment, a first-order Reed-Muller code word consisting of 32 coded symbols is generated by receiving an information bit stream consisting of six bits and then generating a (24,6) code word by puncturing eight coded symbols from the 32 coded symbols.

I »

First embodiment

The first embodiment of the present invention provides a system for generating a code word using a (12,5) linear code as an optimum error correction code for the CDMA mobile communication system and then decoding the generated (12,5) code word. In the first embodiment, as an error correction code, for example, a (12,5) first-order Reed-Muller code generated by puncturing four symbols out of 16 coded symbols constituting a first-order Reed-Muller code word having a length of 16 is used. Although there are countless ways to generate the (12,5) first-order Reed-Muller code, it is not only possible to minimize the complexity of the hardware but also to generate an optimal code word by using the method of generating a first-order Reed-Muller code and then puncturing the generated first-order Reed-Muller code as in the first embodiment of the present invention. Drastically reducing the length of the first-order Reed-Muller code contributes to minimizing the complexity of the hardware. Moreover, it is not only possible to minimize the complexity of the hardware but also to generate a code optimized in terms of error correction performance by puncturing the first-order Reed-Muller code word. In the embodiment of the present invention, as set forth above, the first-order Reed-Muller code is used as an error correction code, and a biorthogonal code word is used for the first-order Reed-Muller code.

The (12,5) code word is generated as stated above by puncturing four symbols out of 16 coded symbols (biorthogonal code symbols) forming a first-order Reed-Muller code word with a length of 16. A minimum distance d,∗, of the code word depends on the puncturing positions at which the four symbols are punctured by the 16 biorthogonal code symbols. The minimum distance of a code word is, as mentioned above, the smallest value among the values of the Hamming distance of the code word, and by increasing the minimum distance, the error correction performance of a linear error correction code improves. Therefore, it is important to determine appropriate puncturing positions in order to generate a biorthogonal (12,5) code word with excellent error correction performance in the first-order Reed-Muller code word with a length of 16.

&agr;«

Puncturing patterns for the four puncturing positions required to generate an optimal (12,5) codeword can be calculated experimentally. There are 16 typical punctuation patterns: {1, 2, 3, 4}, {3, 4, 5, 6}, {5, 6, 7, 8,}, {7, 8, 9,10}, {9, 10, 11, 12}, {11, 12, 13, 14}, {2, 4, 6, 8}, {3, 5, 7, 9}, {6, 8, 10, 12}, {7, 9, 11, 13}, {0, 3, 6, 9}, {1,4, 7, 10}, {2, 5, 8, 11}, {4, 7,10, 13}, {5, 8, 11, 14}, and {6, 9,12,15}. A first-order Reed-Muller codeword consists of 16 coded symbols from the 0th to the 15th coded symbol. For example, the puncturing pattern {1, 2, 3, 4} represents a puncturing pattern in which four consecutive coded symbols from the 16 coded symbols making up the first-order Reed-Muller codeword are punctured at an interval of one symbol starting with a first coded symbol. The puncturing pattern {2, 4, 6, 8} represents a puncturing pattern in which four coded symbols from the 16 coded symbols making up the first-order Reed-Muller codeword are punctured at intervals of two symbols starting with a second coded symbol. The puncturing pattern {0, 3, 6, 9} represents a puncturing pattern in which four coded symbols out of the 16 coded symbols that make up the first-order Reed-Muller codeword are punctured at intervals of three symbols starting from a zeroth coded symbol. Thus, the 16 puncturing patterns have their own regularities. For the six punctuation patterns {1, 2, 3, 4}, {3, 4, 5, 6}, (5, 6, 7, 8}, {7, 8, 9, 10}, {9, 10, 11, 12} and {11,12, 13,14} the punctuation positions of the coded symbols have an equal interval of 1. For the four punctuation patterns {2, 4, 6, 8}, {3, 5, 7, 9} {6, 8,10,12} and {7, 9, 11, 13} the punctuation positions of the coded symbols have an equal interval of 2. For the six punctuation patterns {0, 3, 6, 9}, [1,4, 7,10}, [2, 5, 8,11}, {4, 7,10, 13}, {5, 8,11,14} and {6, 9,12, 15}, the puncturing positions of the coded symbols have an equal interval of 3. When a transmitter of the mobile communication system uses the puncturing patterns with the regularities in encoding, a receiver connected to the transmitter should also use the puncturing patterns with the same regularities in decoding based on prior agreement. This agreement is generally prescribed by a communication protocol. However, it is also possible for the transmitter to inform the receiver of the puncturing positions.

Fig. 1 illustrates a structure of a coding device according to a first embodiment of the present invention. As can be seen with reference to Fig. 1,

an encoding apparatus according to an embodiment of the present invention uses a (12,5) encoder 100 which outputs 12 encoded symbols by receiving a 5-bit information bit stream. The (12,5) encoder 100 includes a (16,5) biorthogonal encoder 100 and a puncturing device 120. The biorthogonal encoder (Reed-Muller encoder) 110 in the (^^ encoding device 100 encodes a 5-bit input information bit stream of a0, a1, a2, a3, and a4 into a first-order Reed-Muller code word (a stream of coded symbols) with a length of 16. The puncturing device 120 receives the stream of coded symbols with the length of 16 output from the biorthogonal encoder 110 and punctures four coded symbols from the coded symbols with the length of 16 at the puncturing positions corresponding to a predetermined puncturing pattern. Thereby, the puncturing device outputs 120 produces a stream of 12 coded symbols, i.e. an optimal (12,5) code word.

For example, if a puncturing pattern is used in which the puncturing positions have an interval of 1, the puncturer 120 punctures four consecutive encoded symbols from the stream of 16 encoded symbols forming a first order Reed-Muller codeword, starting with a selected one of the 1st, 3rd, 5th, 7th, and 11th encoded symbols.

When the first coded symbol is selected from the stream of 16 coded symbols forming the first order Reed-Muller code word, the puncturing device 120 punctures the 1st, 2nd, 3rd and 4th coded symbols. When the third coded symbol is selected from the stream of 16 coded symbols forming the first order Reed-Muller code word, the puncturing device 120 punctures the 3rd, 4th, 5th and 6th coded symbols. When the fifth coded symbol is selected from the stream of 16 coded symbols forming the first order Reed-Muller code word, the puncturing device 120 punctures the 5th, 6th, 7th and 8th coded symbols. When the seventh coded symbol is selected from the stream of 16 coded symbols forming the first order Reed-Muller code word, the puncturing device 120 punctures the 7th, 8th, 9th and 10th coded symbols. When the ninth coded symbol is selected from the stream of 16 coded symbols forming the first order Reed-Muller code word, the puncturing device 120 punctures the 9th, 10th, 11th and 12th coded symbols. Finally, when the 11th coded symbol is selected from the stream of 16 coded symbols

which form the first order Reed-Muller code word, the puncturing device 120 punctures the 11th, 12th, 13th and 14th coded symbols.

Fig. 2 illustrates in detail a structure of the Reed-Muller encoder 110 shown in Fig. 1. The Reed-Muller encoder 110 includes, as seen in Fig. 2, an orthogonal codeword generator consisting of a Walsh code generator 210 and multipliers 230-260, a constant-one code generator 200 and a multiplier 220, and an adder 270. The orthogonal codeword generator generates orthogonal codewords each consisting of 16 coded symbols by multiplying four bits from the 5-bit input information bitstream by corresponding basic orthogonal codes W1, W2, W4 and W8. The orthogonal codeword generator consists of the Walsh code generator 210, which generates a Walsh code, a typical orthogonal code, and the multipliers 230-260. The code generator 200 generates the constant one code, and the constant one code is multiplied by the remaining one bit of the input information bit stream in the multiplier 200. The adder 270 outputs a phase-reversed codeword of the orthogonal codewords, i.e., a first-order Reed-Muller codeword, by performing EXOR of the codewords output from the multiplier 220 and the orthogonal codewords.

The five input information bits a0, a1, a2, a3 and a4 are fed to the multipliers 220, 230, 240, 250 and 260, respectively. The code generator 200 generates a constant one code and the Walsh code generator 210 simultaneously generates Walsh codes W1, W2, W4 and W8 of length 16. The constant one code and the Walsh codes W1, W2, W4 and W8 are also fed to the associated multipliers 200, 230, 240, 250 and 260, respectively. That is, the continuous one code is supplied to the multiplier 220, the Walsh code W1 to the multiplier 230, the Walsh code W2 to the multiplier 240, the Walsh code W4 to the multiplier 250, and the Walsh code W8 to the multiplier 260. The code generator 200 generates the continuous one code in order to generate a biorthogonal code by converting an orthogonal code into a phase-reversed orthogonal code. Other codes may also be used if they can be used to generate a biorthogonal code by converting the orthogonal code into a phase-reversed orthogonal code.

The multiplier 220 multiplies the input information bit aO by the permanent one code in one symbol unit. The multiplier 230 multiplies the input information bit a1 by the Walsh code W1 in one symbol unit. The multiplier 240 multiplies the input information bit a2 by the Walsh code W2 in one symbol unit. The multiplier 250 multiplies the input information bit a3 by the Walsh code W4 in one symbol unit. The multiplier 260 multiplies the input information bit a4 by the Walsh code W8 in one symbol unit.

The five code words each consisting of 16 coded symbols are supplied to the adder 270, including a code word which is the result of multiplying the remaining one bit of the input information bit stream by a 1 signal and four orthogonal code words output from the multipliers 220 and 260. The adder 270 performs EXOR of the five code words each consisting of 16 coded symbols output from the multipliers 220, 260 in a symbol unit, and outputs a code word of length 16, i.e., a first-order Reed-Muller code word.

Fig. 3 illustrates a structure of a decoding apparatus according to the first embodiment of the present invention. Referring to Fig. 3, a stream of coded symbols of length 12 received from the transmitter is supplied to a zero inserter 310 in a (12,5) decoder 300. The zero inserter 310 receiving the stream of coded symbols of length 12 inserts zero (O) bits at the puncturing positions used by the puncturing device 120 in the (12,5) encoder 100 of the transmitter and supplies the symbol stream after zero insertion to a fast inverse Hadamard transform element 320. For example, when the puncturing device 120 in the (12,5) encoder 100 has punctured the 0th, 3rd, 6th and 9th coded symbols, the zero inserter 310 in the (12,5) decoder 300 inserts the zero bits at the above-mentioned 4 puncturing positions of the stream of coded symbols of length 12 and then outputs a stream of coded symbols of length 16. In doing so, the zero inserter 310 must know the positions at which the zero bits are to be inserted, i.e., the puncturing positions used by the puncturing device 120. The information about the puncturing position is supplied to the zero inserter 310 from the transmitter in a predetermined procedure. The inverse Hadamard transform element 320 compares the stream of coded symbols of length 16 output by the zero inserter 310.

length 16 with the first-order Reed-Muller codeword to calculate reliabilities between them, and outputs the calculated reliabilities for the first-order Reed-Muller codewords and the input information bits for the first-order Reed-Muller codewords. All the Reed-Muller codewords here mean 32 codewords, which include codewords of the Walsh code of length 16 and 16 codewords calculated by inverting the codewords of the Walsh code of length 16. Thus, 32 reliabilities are calculated. The reliabilities and the input information bits for the first-order Reed-Muller codewords form pairs whose number corresponds to the number of the first-order Reed-Muller codewords. The pairs of the reliabilities and the input information bits output from the inverse Hadamard transform element 320 are fed to a comparator 330. The comparator 330 selects the highest reliability among the supplied reliabilities and then outputs the input information bits associated with the selected reliability as decoded bits.

The first embodiment allows 15 other puncturing patterns in addition to the above-mentioned puncturing pattern {0, 3, 6, 9} for the optimal puncturing positions. When the puncturing pattern is changed, the insertion positions of the zero inserter 310 in the decoder 300 in Fig. 3 are also changed. For example, when the puncturing device 120 in the (12,5) encoder 100 punctures four consecutive symbols from the 16 coded symbols starting with a coded symbol selected from the first, third, fifth, seventh, ninth and eleventh coded symbols and outputs an optimal code word (12,5), the zero inserter 310 in the (12,5) encoder, which decodes a 12-bit coded symbol stream and outputs a 5-bit coded stream, performs a zero insertion operation as follows. That is, the zero inserter outputs a 16-bit coded symbol stream by inserting zero (O) bits at the positions of the 12-bit coded symbol stream corresponding to positions of four consecutive coded symbols out of the 16 coded symbols starting from a coded symbol selected from the 1st, 3rd, 5th, 7th, 9th, and 11th coded symbols. Furthermore, the puncturing positions are determined so as to increase the performance of the encoder to a maximum and have simple regularity, so that the encoder in the transmitter and the decoder in the receiver can have low hardware complexity.

Second embodiment

The second embodiment of the invention provides a system for generating a code word using a (24,6) linear code as an optimum error correction code for the CDMA mobile communication system and then decoding the generated (24,6) code word. In the second embodiment, as an error correction code, for example, a (24,6) first-order Reed-Muller code generated by puncturing 8 symbols out of 32 coded symbols constituting a first-order Reed-Muller code word having a length of 32 is used. Although there are numerous ways to generate the (24,6) first-order Reed-Muller code, it is possible not only to minimize the complexity of the hardware but also to generate an optimal code word by using the method of generating a first-order Reed-Muller code and then puncturing the generated Reed-Muller code as described below in the second embodiment of the present invention. Drastically reducing the length of the first-order Reed-Muller code contributes to minimizing the complexity of the hardware. Moreover, it is possible not only to minimize the complexity of the hardware but also to generate a code optimized in terms of error correction performance by puncturing the first-order Reed-Muller code word. In the embodiment of the present invention, as set forth above, the first-order Reed-Muller code is used as an error correction code, and a biorthogonal code word is used for the first-order Reed-Muller code.

The (24,6) code word is generated, as explained above, by puncturing eight symbols out of 32 coded symbols (biorthogonal code symbols) that form a Reed-Muller code word with a length of 32. A minimum distance d _min of the code word depends on the puncturing positions at which the eight symbols are punctured by the 32 biorthogonal code symbols. The minimum distance of a code word is, as already mentioned, the smallest value among the values of the Hamming distance of the code word, and an increase in the minimum distance improves the error correction performance of a linear error correction code. Therefore, it is important to determine suitable puncturing positions in order to generate a biorthogonal (24,6) code word with

recorded error correction power in the first order Reed-Muller code word with a length of 32.

Puncturing patterns for determining the eight puncturing positions required to generate an optimal (24,6) codeword can be calculated experimentally. There are three typical puncturing patterns: {2, 5, 8,11,14,17, 20, 21}; {6, 9,12,15,18, 21, 24, 25} and {10,13,16, 22, 25, 28, 29}. A first-order Reed-Muller codeword consists of 32 encoded symbols from the 0th to the 31st encoded symbol. For example, the puncturing pattern {2, 5, 8, 11,14, 17, 20,21} represents a puncturing pattern in which a second encoded symbol is punctured from the stream of 32 encoded symbols forming the first order Reed-Muller codeword, six encoded symbols are punctured at intervals of three symbols starting with the second encoded symbol, and a further encoded symbol is punctured at an interval of one symbol starting with the last symbol of the six punctured encoded symbols. The puncturing pattern {6, 9,12, 15,18, 21, 24, 25} represents a puncturing pattern in which a sixth symbol is encoded from the stream of 32 encoded symbols constituting the first-order Reed-Muller codeword, six encoded symbols are punctured at intervals of three symbols starting from the sixth encoded symbol, and further one encoded symbol is punctured at an interval of one symbol starting from the last symbol of the 6 punctured encoded symbols. The puncturing pattern {10, 13, 16, 19, 22, 25, 28, 29} represents a puncturing pattern in which a tenth encoded symbol is punctured from the stream of 32 encoded symbols constituting the first-order Reed-Muller code word, six encoded symbols are punctured at intervals of three symbols starting with the tenth encoded symbol, and further one encoded symbol is punctured at an interval of one symbol starting with the last symbol of the six punctured encoded symbols. In summary, the puncturing patterns are used to select one of the 2nd, 6th and 10th coded symbols from the stream of 32 coded symbols forming the first order Reed-Muller code word, and then to puncture the selected coded symbol, six coded symbols at intervals of three symbols starting from the selected coded symbol and one coded symbol at an interval of one symbol starting from the last symbol of six punctured coded symbols. When a transmitter of the mobile communication system uses the puncturing patterns with the regularities in coding, a

Receivers connected to the sender may also use the puncturing patterns with the same regularities based on prior agreement. This agreement is generally prescribed by a communication protocol. However, it is also possible for the sender to inform the receiver about the puncturing positions.

Fig. 4 illustrates a structure of an encoding apparatus according to a second embodiment of the present invention. Referring to Fig. 4, an encoding apparatus according to the second embodiment of the present invention includes a (24,6) encoder 1100 that outputs 24 encoded symbols by receiving a 6-bit information bit stream. The (24,6) encoder 1100 includes a biorthogonal (32,6) encoder 1110 and a puncturing device 1120. The biorthogonal encoder (Reed-Muller encoder) 1110 in the ^^ encoder device 1100 encodes a 6-bit input information bit stream of a0, a1, a2, a3, a4, and a5 into a first-order Reed-Muller code word (a stream of coded symbols) of length 32. The puncturing device 1120 receives the stream of coded symbols of length 32 output from the biorthogonal encoder 1110 and punctures eight coded symbols from the stream of coded symbols of length 32 at the puncturing positions corresponding to a predetermined Puncturing pattern, Thus, the puncturing device 1120 outputs a stream of 24 coded symbols, i.e., an optimal (24,6) code word.

For example, the puncturing device 1120 selects the 2nd, 6th, or 10th encoded symbol from the stream of 32 encoded symbols forming the first order Reed-Muller code word and then punctures the selected encoded symbol, six encoded symbols at intervals of three symbols starting with the selected encoded symbol, and one encoded symbol at an interval of one symbol starting with the last symbol of the six punctured encoded symbols. When the second encoded symbol is selected from the stream of 32 encoded symbols forming the first order Reed-Muller code word, the puncturing device 1120 punctures the 2nd, 5th, 8th, 11th, 14th, 17th, 20th, and 21st encoded symbols. When the sixth coded symbol is selected from the stream of 32 coded symbols forming the first order Reed-Muller code word, the puncturing device 1120 punctures the 6th, 9th, 12th, 15th, 18th, 21st, 24th and 25th coded symbols. When the 10th coded symbol is selected from the stream of 32 coded symbols forming the Reed-Muller code word

first order, the puncturing device 1120 punctures the 10th, 13th, 16th, 19th, 22nd, 25th, 28th and 29th coded symbols

Fig. 5 details the structure of the Reed-Muller encoder 1110 shown in Fig. 4. The Reed-Muller encoder 1110 includes, as shown in Fig. 5, an orthogonal codeword generator consisting of an orthogonal code generator 1210 and multipliers 1220-1270, a constant-one code generator 1200, and an adder 1280. The orthogonal codeword generator generates orthogonal codewords each consisting of 32 encoded symbols by multiplying 5 bits from the 6-bit input information bitstream by corresponding basic orthogonal codes, a typical orthogonal code, Walsh code W1, W2, W4, W8, and W16, respectively. The orthogonal codeword generator consists of the Walsh code generator 1210, which generates a Walsh code, a typical orthogonal code, and the multipliers 1230-1270. The code generator 1200 generates a constant one code, and the constant one code is multiplied by the remaining one bit of the input information bit stream in the multiplier 1220. The adder 1280 outputs a phase-reversed codeword of the orthogonal codewords, a first order Reed-Muller codeword, by performing EXOR of the codewords output from the multiplier 1220 and the orthogonal codewords.

The six input information bits a0, a.1, a2, a3, a4 and a5 are fed to the multipliers 1220,1230, 1240, 1250, 1260 and 1270. The code generator 1200 generates a constant one code and the Walsh code generator 1210 simultaneously generates Walsh codes W1, W2, W4, W8 and W16 of length 32. The constant one code and the Walsh codes W1, W2, W4, W8 and W16 are also fed to the corresponding multipliers 1220, 1230, 1240, 1250, 1260 and 1270, respectively. That is, the continuous one code is supplied to the multiplier 1220, the Walsh code W1 to the multiplier 1230, the Walsh code W2 to the multiplier 1240, the Walsh code W4 to the multiplier 1250, the Walsh code W8 to the multiplier 1260, and the Walsh code W16 to the multiplier 1270. The code generator 1200 generates the continuous one code to generate a biorthogonal code by converting an orthogonal code into a phase-reversed orthogonal code. Other codes may also be used if they can be used to generate a biorthogonal code by converting the orthogonal code into a phase-reversed orthogonal code.

·

The multiplier 1220 multiplies the input information bit aO by the continuous one code in one symbol unit. The multiplier 1230 multiplies the input information bit a1 by the Walsh code W1 in one symbol unit. The multiplier 1240 multiplies the input information bit a2 by the Walsh code W2 in one symbol unit. The multiplier 1250 multiplies the input information bit a3 by the Walsh code W4 in one symbol unit. The multiplier 1260 multiplies the input information bit a4 by the Walsh code W8 in one symbol unit. The multiplier 1270 multiplies the input information bit a5 by the Walsh code WI6 in one symbol unit.

The six code words each consisting of 32 coded symbols are supplied to the adder 1280, including a code word which is the result of multiplying the remaining one bit of the input information bit stream by a 1 signal and five orthogonal code words output from the multipliers 1220-1270. The adder 1280 performs EXOR of the code words output from the multipliers 1220-1270 in one symbol unit and outputs a code word of length 32, i.e., a first-order Reed-Muller code word.

Fig. 6 illustrates a structure of a decoding apparatus according to the second embodiment of the present invention. Referring to Fig. 6, a stream of coded symbols of length 24 received from the transmitter is supplied to a zero inserter 1310 in a (24,6) decoder 1300. The zero inserter 1310, which receives the stream of coded symbols of length 24, inserts zero (O) bits at the puncturing positions used by the puncturing device 1120 in the (24,6) encoder 1100 of the transmitter, and passes the symbol stream after zero insertion to a fast inverse Hadamard transform element 1320. For example, if the puncturing device 1220 in the (24,6) encoder 1100 has punctured the 2nd, 5th, 8th, 11th, 14th, 17th, 20th, 21st coded symbols, the zero inserter 1310 in the (24,6) decoder 1300 inserts the zero bits at the above eight puncturing positions of the stream of coded symbols of length 24 and then outputs a stream of coded symbols of length 32. The zero inserter 1310 must know the positions at which the zero bits are to be inserted, i.e., the positions used by the puncturing device 1120.

ten puncturing positions. The puncturing position information is supplied to the null inserter 1310 from the transmitter in a predetermined procedure. The inverse Hadamard transform element 1320 compares the stream of coded symbols of length 32 output from the null inserter 1310 with the first-order Reed-Muller codeword to calculate reliabilities between them, and outputs the calculated reliabilities for the first-order Reed-Muller codewords and the input information bits for the first-order Reed-Muller codewords. All first-order Reed-Muller codewords mean 64 codewords, which include codewords of the Walsh code of length 32 and 32 codewords calculated by inverting the Walsh codewords of length 32. Thus, 64 reliabilities are calculated. The reliabilities and the input information bits for the first-order Reed-Muller code words form pairs whose number corresponds to the number of the first-order Reed-Muller code words. The pairs of the reliabilities and the input information bits output from the inverse Hadamard transform element 1320 are supplied to a comparator 1330. The comparator 1330 selects the highest reliability among the supplied reliabilities and then outputs the input information bits associated with the selected reliability as decoded bits.

The second embodiment allows two more puncturing patterns in addition to the above-listed puncturing pattern {2, 5, 8,11, 14,17, 20, 21} for the optimal puncturing positions. When the puncturing pattern is changed, the insertion positions of the zero inserter 1310 in the decoder 1300 in Fig. 6 are also changed. For example, when the puncturing means 1120 in the (24,6) encoder 1100 outputs an optimal (24,6) code word by selecting a coded symbol position from the 2nd, 6th, and 10th coded symbol positions from the stream of 32 coded symbols and puncturing the selected coded symbol, six coded symbols at intervals of 3 starting from the selected coded symbol, and the coded symbol at an interval of 1 starting from the last symbol from the six coded symbols, the zero inserter 1310 in the (24,6) decoder, which decodes a 24-bit coded symbol stream and outputs a 6-bit coded stream, performs a zero insertion operation as follows. That is, the zero inserter 1310 selects the position of an encoded symbol from the 2nd, 6th and 10th positions of encoded symbols from the stream of 32 encoded symbols that constitute the Reed-Muller code

first order word, and outputs a 32-bit coded symbol stream by inserting zero (O) bits at the positions of the 24-bit coded symbol stream corresponding to the selected coded symbol, six coded symbols at intervals of 3 starting from the selected coded symbol, and the coded symbol at the interval of 1 starting from the last symbol of the six coded symbols. Furthermore, the puncturing positions are determined to maximize the performance of the encoder and have a simple regularity, so that the encoder in the transmitter and the encoder in the receiver can have low hardware complexity.

As described above, with the CDMA mobile communication system according to the present invention, an optimal minimum distance can be achieved by optimally encoding/decoding the error correction codes, so that it becomes possible to improve the error correction performance. Furthermore, it is possible to simplify the hardware structure for encoding/decoding by determining the puncturing positions with regularity, which contributes to reducing the complexity of the hardware to a minimum.

Although the invention has been shown and described with reference to a certain preferred embodiment thereof, it will be apparent to those skilled in the art that various changes in form and details may be made therein without departing from the scope of the invention as defined by the appended claims.

Claims (14)

1. Apparatus for encoding a 5-bit input information bit stream into a ( 12 , 5 ) code word consisting of 12 coded symbols, comprising:
a Reed-Muller encoder that receives the 5-bit input information bit stream and generates a first-order Reed-Muller code word consisting of 16 encoded symbols; and
a puncturing device that outputs an optimal ( 12 , 5 ) code word by puncturing four consecutive coded symbols from a stream of the 16 coded symbols forming the first order Reed-Muller code word, starting with a coded symbol selected from the 1st, 3rd, 5th, 7th, 9th and 11th coded symbols. 2. The apparatus of claim 1, wherein the puncturing means punctures the 1st, 2nd, 3rd and 4th coded symbols. 3. The apparatus of claim 1, wherein the Reed-Muller encoder comprises:
an orthogonal codeword generator that generates orthogonal codewords each consisting of 16 encoded symbols by multiplying four bits from the 5-bit input information bitstream by corresponding basic orthogonal codes W1, W2, W4, and W8, respectively;
a code generator that generates a permanent one code; and
an adder that outputs the first order Reed-Muller codeword, wherein 16 encoded symbols represent the phase-reversed codeword of the orthogonal codewords, by performing EXOR of the orthogonal codewords and the result of multiplying a remaining bit of the input information bitstream by the constant-one code. 4. Apparatus for encoding a 5-bit input information bit stream into a ( 12 , 5 ) code word consisting of 12 coded symbols, comprising:
a Reed-Muller encoder that receives the 5-bit input information bit stream and generates a first-order Reed-Muller code word consisting of 16 coded symbols and
a puncturing device which outputs an optimal ( 12,5 ) code word by puncturing a coded symbol selected from the 2nd, 3rd, 6th and 7th coded symbols from a stream of the 16 coded symbols constituting the first order Reed-Muller code word and further puncturing three coded symbols at intervals of two symbols starting from the selected coded symbol. 5. The apparatus of claim 4, wherein the puncturing means punctures the 2nd, 4th, 6th and 8th coded symbols. 6. The apparatus of claim 4, wherein the Reed-Muller encoder comprises:
an orthogonal codeword generator that generates orthogonal codewords each consisting of 16 encoded symbols by multiplying four bits from the 5-bit input information bitstream by corresponding basic orthogonal codes W1, W2, W4, and W8, respectively;
a code generator that generates a permanent one code; and
an adder that outputs the first order Reed-Muller codeword, wherein 16 encoded symbols represent the phase-reversed codeword of the orthogonal codewords, by performing EXOR of the orthogonal codewords and the result of multiplying a remaining bit of the input information bitstream by the constant-one code. 7. Apparatus for encoding a 5-bit input information bit stream into a ( 12 , 5 ) code word consisting of 12 coded symbols, comprising:
a Reed-Muller encoder that receives the 5-bit input information bit stream and generates a first-order Reed-Muller code word consisting of 16 encoded symbols; and
a puncturing device that outputs an optimal ( 12 , 5 ) code word by puncturing a coded symbol selected from the 0th, 1st, 2nd, 4th, 5th and 6th coded symbols from a stream of the 16 coded symbols constituting the first order Reed-Muller code word and further puncturing three coded symbols at intervals of three symbols starting from the selected coded symbol. 8. The apparatus of claim 7, wherein the puncturing means punctures the 0th, 3rd, 6th and 9th encoded symbols. 9. The apparatus of claim 7, wherein the Reed-Muller encoder comprises:
an orthogonal codeword generator that generates orthogonal codewords each consisting of 16 encoded symbols by multiplying four bits from the 5-bit input information bitstream by corresponding basic orthogonal codes W1, W2, W4, and W8, respectively;
a code generator that generates a permanent one code; and
an adder that outputs the first order Reed-Muller codeword, wherein 16 encoded symbols represent the phase-reversed codeword of the orthogonal codewords, by performing EXOR operations of the orthogonal codewords and the result of multiplying a remaining bit of the input information bitstream by the constant-one code. 10. Apparatus for encoding a 6-bit input information bit stream into a 24.6 code word consisting of 24 coded symbols, comprising:
a Reed-Muller encoder that receives the 6-bit input information bit stream and generates a first-order Reed-Muller code word consisting of 32 encoded symbols; and
a puncturing device that outputs an optimal ( 24 , 6 ) code word by selecting a coded symbol from the 2nd, 6th and 10th coded symbols from a stream of the 32 coded symbols constituting the first order Reed-Muller code word and puncturing the selected coded symbol, six coded symbols at intervals of three symbols starting from the selected coded symbol and one coded symbol at an interval of one symbol starting from a last symbol from the six punctured coded symbols. 11. The apparatus of claim 10, wherein the puncturing means punctures the 2nd, 5th, 8th, 11th, 14th, 16th, 20th and 21st coded symbols. 12. The apparatus of claim 10, wherein the Reed-Muller encoder comprises:
an orthogonal codeword generator that generates orthogonal codewords each consisting of 32 encoded symbols by multiplying five bits from the 6-bit input information bitstream by corresponding basic orthogonal codes W1, W2, W4, W8, and W16, respectively;
a code generator that generates a permanent one code; and
an adder that outputs the first order Reed-Muller codeword, wherein 32 encoded symbols represent the phase-reversed codeword of the orthogonal codewords, by performing EXOR of the orthogonal codewords and the result of multiplying a remaining bit of the input information bitstream by the constant-one code. 13. ( 12,5 ) decoding apparatus for decoding a 12-bit stream of coded symbols to a decoded 5-bit bit stream, comprising:
a zero inserter that outputs a 16-bit encoded symbol stream by inserting zero (0) bits at positions of the 12-bit encoded symbol stream corresponding to positions of four consecutive decoded symbols starting with a coded symbol selected from the 1st, 3rd, 5th, 7th, 9th, and 11th coded symbols out of the 16 coded symbols forming a first order Reed-Muller code word;
an inverse Hadamard transform element that calculates reliabilities by comparing the 16-bit stream of encoded symbols with each first-order Reed-Muller codeword, each consisting of the 16-bit stream of encoded symbols, and outputting 5-bit information bitstreams corresponding to all Reed-Muller codewords, together with associated reliability values; and
a comparator that compares reliabilities for all first-order Reed-Muller codewords and outputs a 5-bit information bitstream corresponding to a first-order Reed-Muller codeword with a highest reliability as a decoded bitstream. 14. ( 24,6 ) decoding apparatus for decoding a 24-bit stream of coded symbols to a decoded 6-bit bit stream, comprising:
a zero inserter that outputs a 32-bit coded symbol stream by selecting a coded symbol from the 2nd, 6th and 10th coded symbols from a stream of 32 coded symbols forming the first order Reed-Muller code word and inserting zero (0) bits at positions of the 24-bit coded symbol stream corresponding to the position of the coded symbol at the selected position, the position of six coded symbols at the position with 3 intervals starting with the selected coded symbol, and the position of the coded symbol at the position with 1 interval starting with the last symbol of the six coded symbols;
an inverse Hadamard transform element that calculates reliabilities by comparing the 32-bit stream of encoded symbols with each first-order Reed-Muller codeword, each consisting of the 16-bit stream of encoded symbols, and outputting 6-bit information bitstreams corresponding to all Reed-Muller codewords, together with associated reliability values; and
a comparator that compares reliabilities for all first-order Reed-Muller codewords and outputs a 6-bit information bitstream corresponding to a Reed-Muller codeword with a highest reliability as a decoded bitstream.