Method and apparatus for using orthogonal coding in a communication system

Claims

What is claimed is:

1. An apparatus comprising a signal encoder, the signal encoder comprising:

(a) encoding means for encoding input data bits of a signal into data symbols and grouping the data symbols, the data symbols being encoded with an encoding algorithm, wherein the encoding algorithm produces data symbols which are subsequently decoded into data signal bits using maximum likelihood decoding; and

(b) translating means, operatively coupled to the encoding means, for translating the groups of data symbols according to an algorithm selected from the group consisting essentially of (i) interleaving by group each group of data symbols within a predetermined size block and subsequently deriving an orthogonal code from each group of interleaved data symbols and (ii) deriving an orthogonal code from each group of data symbols and subsequently interleaving by orthogonal code each orthogonal code within a predetermined size block.

2. The apparatus of claim 1 wherein the encoding algorithm comprises an algorithm selected from the group consisting essentially of a block coding algorithm and a convolutional coding algorithm.

3. The apparatus of claim 1 wherein the predetermined block size of the signal encoder translating means is derived from the maximum number of data symbols which can be transmitted at a predetermined chip rate within a predetermined length signal transmission block.

4. The apparatus of claim 1 further comprising a signal transmitting means, operatively coupled to the signal encoder, for transmitting the translated groups of data symbols over a communication channel.

5. The apparatus of claim 4 wherein the signal transmitting means comprises means for preparing the translated groups of data symbols for transmission over the communication channel by spreading the translated groups of data symbols with a spreading code prior to transmission over the communication channel.

6. The apparatus of claim 4 wherein the communication channel is selected from the group consisting essentially of an electronic data bus, radio communication link, wireline and optical fiber link.

7. The apparatus of claim 4 further comprising:

(a) signal receiving means for sampling a signal received from over the communication channel into data samples; and

(b) a signal decoder, operatively coupled to the signal receiving means, the signal decoder comprising:

(i) grouping means for grouping received data samples;

(ii) transforming means, operatively coupled to the grouping means, for transforming the groups of data samples according to an algorithm selected from the group consisting essentially of (1) generating a plurality of soft decision similarity metrics and index data symbols for each group of data samples such that one index data symbol is associated with each soft decision metric and subsequently deinterleaving by group each group of soft decision metrics within a predetermined size block and (2) deinterleaving by group each group of data samples within a predetermined size block and subsequently generating a plurality of soft decision similarity metrics and index data symbols for each deinterleaved group of data samples such that one index data symbol is associated with each soft decision metric, each soft decision metric corresponding to a measure of confidence that a particular group of data samples is substantially similar to a particular orthogonal code from within a set of mutually orthogonal codes; and

(iii) decoding means, operatively coupled to the transforming means, for generating at least one estimated data bit by utilizing maximum likelihood decoding techniques to derive the at least one estimated data bit from the soft decision metrics and associated index data symbols.

8. The apparatus of claim 7 wherein:

(a) the signal encoder encoding means comprises means for convolutionally encoding two input data bits of the signal into six data symbols and grouping the six data symbols derived from the two input data bits;

(b) the signal encoder translating means comprises means for translating the groups of data symbols according to an algorithm selected from the group consisting essentially of (i) interleaving as a group each group of six data symbols within the predetermined size block and subsequently deriving a 64 bit length orthogonal code from each group of six data symbols and (ii) deriving a 64 bit length orthogonal code from each group of six data symbols and subsequently interleaving as a group each 64 bit length orthogonal code within the predetermined size block;

(c) the signal transmitting means comprises means for spreading each 64 bit length orthogonal code with a predetermined spreading code such that 256 bit length sequences are formed which represent each 64 bit length orthogonal code and subsequently transmitting the 256 bit length sequences over the communication channel whereby each two input data bits are represented by a 256 bit length transmitted sequence;

(d) the signal receiving means comprises means for despreading the received signal with the predetermined spreading code to derive data samples such that each data sample represents a 4 bit length sequence of the received signal;

(e) the signal decoder grouping means comprises means for grouping the data samples into 64 bit length groups;

(f) the signal decoder transforming means comprises means for transforming the groups of data samples according to an algorithm selected from the groups consisting essentially of (i) generating 64 soft decision metrics and index data symbols for each 64 bit length group of data samples such that one index data symbol having at least a 6 bit length is associated with each soft decision metric and subsequently deinterleaving as a group each group of 64 soft decision metrics within the predetermined size block and (ii) deinterleaving as a group each 64 bit length group of data samples within the predetermined size block and subsequently generating 64 soft decision metrics and index data symbols for each deinterleaved 64 bit length group of data samples such that one index data symbol having at least a 6 bit length is associated with each soft decision metric, each soft decision metric corresponding to a measure of confidence that a particular group of data samples is substantially similar to a particular 64 bit length orthogonal code from within a set of 64 mutually orthogonal 64 bit length codes; and

(g) the signal decoder decoding means comprises means for generating at least one estimated data bit by utilizing maximum likelihood decoding techniques including using the at least 6 bit length index data symbols and associated soft decision metrics.

9. The apparatus of claim 7 wherein the predetermined block size of the signal decoder transforming means is derived from the number of soft decision metrics generated for each group of data samples, the number of data samples in each group of data samples and the maximum number of data samples which can be sampled from a received signal transmission block.

10. The apparatus of claim 7 wherein the signal receiving means comprises means for despreading the received signal with a spreading code to derive data samples.

11. The apparatus of claim 7 wherein the signal decoder data sample transforming means comprises means for generating soft decision similarity metrics by utilizing a Hadamard transform matrix algorithm on a group of data samples.

12. The apparatus of claim 7 wherein the signal decoder decoding means comprises means for generating at least one estimated data bit by utilizing maximum likelihood decoding techniques which are substantially similar to the Viterbi decoding algorithm.

13. The apparatus claim 7 wherein:

(a) the signal decoder transforming means comprises:

(i) means for determining each index data symbol such that each index data symbol corresponds to a possible transition within a maximum likelihood decoding trellis; and

(ii) means for storing each soft decision metric in a particular address of a memory based lookup table such that the associated index data symbol comprises a portion of the particular address in the lookup table; and

(b) the signal decoder decoding means comprises means for generating at least one estimated data bit by utilizing maximum likelihood decoding techniques in which such transition corresponding index data symbols are used to address and retrieve at least one soft decision metric from the memory based lookup table.

14. An apparatus comprising a signal decoder, the signal decoder comprising:

(a) grouping means for grouping received data samples of a signal;

(b) transforming means, operatively coupled to the grouping means, for transforming the groups of data samples into index data symbols and associated deinterleaved soft decision metrics according to an algorithm selected from the group consisting essentially of (i) generating a plurality of soft decision similarity metrics and index data symbols for each group of data samples such that one index data symbol is associated with each soft decision metric and subsequently deinterleaving by group each group of soft decision metrics within a predetermined size block and (ii) deinterleaving by group each group of data samples within a predetermined size block and subsequently generating a plurality of soft decision similarity metrics and index data symbols for each deinterleaved group of data samples such that one index data symbol is associated with each soft decision metric, each soft decision metric corresponding to a measure of confidence that a particular group of data samples is substantially similar to a particular orthogonal code from within a set of mutually orthogonal codes; and

(c) decoding means, operatively coupled to the transforming means, for generating at least one estimated data bit by utilizing maximum likelihood decoding techniques to derive the at least one estimated data bit from the index data symbols and associated soft decision metrics.

15. The apparatus of claim 14 wherein the predetermined block size of the signal decoder transforming means is derived from the number of soft decision metrics generated for each group of data samples, the number of data samples in each group of data samples and the maximum number of data samples which can be sampled from a received signal transmission block.

16. The apparatus of claim 14 further comprising signal receiving means, operatively coupled to the signal decoder, for sampling a signal received from over a communication channel into data samples.

17. The apparatus of claim 16 wherein the communication channel is selected from the group consisting essentially of an electronic data bus, radio communication link, wireline and optical fiber link.

18. The apparatus of claim 16 wherein the signal receiving means comprises means for despreading the received signal with a spreading code to derive data samples.

19. The apparatus of claim 14 wherein the signal decoder data sample transforming means comprises means for generating soft decision similarity metrics by utilizing a Hadamard transform matrix algorithm on a group of data samples.

20. The apparatus of claim 14 wherein the signal decoder decoding means comprises means for generating at least one estimated data bit by utilizing maximum likelihood decoding techniques which are substantially similar to the Viterbi decoding algorithm.

21. The apparatus claim 14 wherein:

(a) the signal decoder transforming means comprises:

(i) means for determining each index data symbol such that each index data symbol corresponds to a possible transition within a maximum likelihood decoding trellis; and

(ii) means for storing each soft decision metric in a particular address of a memory based lookup table such that the associated index data symbol comprises a portion of the particular address in the lookup table; and

(b) the signal decoder decoding means comprises means for generating at least one estimated data bit by utilizing maximum likelihood decoding techniques in which such transition corresponding index data symbols are used to address and retrieve at least one soft decision metric from the memory based lookup table.

22. A method of convolutionally encoding data bits of a signal for transmission, comprising:

(a) convolutionally encoding input data bits of the signal into data symbols, the data symbols being encoded with an encoding algorithm, wherein the encoding algorithm produces data symbols which are subsequently decoded into data signal bits using maximum likelihood decoding;

(b) grouping the data symbols;

(c) translating the groups of data symbols according to an algorithm selected from the group consisting essentially of (i) interleaving by group each group of data symbols within a predetermined size block and subsequently deriving an orthogonal code from each group of interleaved data symbols and (ii) deriving an orthogonal code from each group of data symbols and subsequently interleaving by orthogonal code each orthogonal code within a predetermined size block; and

(d) transmitting the translated groups of data symbols over a communication channel.

23. The method of claim 22 wherein the encoding algorithm comprises an algorithm selected from the group consisting essentially of a block coding algorithm and a convolutional coding algorithm.

24. The method of claim 22 wherein the predetermined block size is derived from the maximum number of data symbols which can be transmitted at a predetermined chip rate within a predetermined length transmission block.

25. The method of claim 22 further comprising the step of, prior to the step of transmitting, preparing the translated groups of data symbols for transmission over the communication channel by spreading the translated groups of data symbols with a spreading code.

26. The method of claim 22 further comprising the steps of:

(a) sampling a signal received from over a communication channel into data samples;

(b) grouping the data samples;

(c) transforming the groups of data samples according to an algorithm selected from the group consisting essentially of (i) generating a plurality of soft decision similarity metrics and index data symbols for each group of data samples such that one index data symbol is associated with each soft decision metric and subsequently deinterleaving by group each group of soft decision metrics within a predetermined size block and (ii) deinterleaving by group each group of data samples within a predetermined size block and subsequently generating a plurality of soft decision similarity metrics and index data symbols for each deinterleaved group of data samples such that one index data symbol is associated with each soft decision metric, each soft decision metric corresponding to a measure of confidence that a particular group of data samples is substantially similar to a particular orthogonal code from within a set of mutually orthogonal codes; and

(d) generating at least one estimated data bit by utilizing maximum likelihood decoding techniques to derive the at least one estimated data bit from the index data symbols and associated deinterleaved soft decision metrics.

27. The method of claim 26 wherein the step of:

(a) encoding comprises convolutionally encoding two input data bits of the signal into six data symbols and grouping the six data symbols derived from the two input data bits;

(b) translating comprises translating the groups of data symbols according to an algorithm selected from the group consisting essentially of (i) interleaving as a group each group of six data symbols within the predetermined size block and subsequently deriving a 64 bit length orthogonal code from each group of six data symbols and (ii) deriving a 64 bit length orthogonal code from each group of six data symbols and subsequently interleaving as a group each 64 bit length orthogonal code within the predetermined size block;

(c) transmitting comprises spreading each 64 bit length orthogonal code with a predetermined spreading code such that 256 bit length sequences are formed which represent each 64 bit length orthogonal code and subsequently transmitting the 256 bit length sequences over the communication channel whereby each two input data bits are represented by a 256 bit length transmitted sequence;

(d) sampling comprises despreading the received signal with the predetermined spreading code to derive data samples such that each data sample represents a 4 bit length sequence of the received signal;

(e) grouping comprises grouping the data samples into 64 bit length groups;

(f) transforming comprises transforming the groups of data samples according to an algorithm selected from the groups consisting essentially of (i) generating 64 soft decision metrics and index data symbols for each 64 bit length group of data samples such that one index data symbol having at least a 6 bit length is associated with each soft decision metric and subsequently deinterleaving as a group each group of 64 soft decision metrics within the predetermined size block and (ii) deinterleaving as a group each 64 bit length group of data samples within the predetermined size block and subsequently generating 64 soft decision metrics and index data symbols for each deinterleaved 64 bit length group of data samples such that one index data symbol having at least a 6 bit length is associated with each soft decision metric, each soft decision metric corresponding to a measure of confidence that a particular group of data symbols is substantially similar to a particular 64 bit length orthogonal code from within a set of 64 mutually orthogonal 64 bit length codes; and

(g) generating comprises generating at least one estimated data bit by utilizing maximum likelihood decoding techniques including using the at least 6 bit length index data symbols and associated soft decision metrics.

28. The method of claim 26 wherein the predetermined block size is derived from the number of soft decision metrics generated for each group of data samples, the number of data samples in each group of data samples and the maximum number of data samples which can be sampled from a received signal transmission block.

29. The method of claim 26 wherein the step of sampling comprises despreading the received signal with a spreading code to derive data samples.

30. The method of claim 26 wherein the step of transforming comprises generating soft decision similarity metrics by utilizing a Hadamard transform matrix algorithm on a group of data samples.

31. The method of claim 26 wherein the step of decoding comprises generating at least one estimated data bit by utilizing maximum likelihood decoding techniques which are substantially similar to the Viterbi decoding algorithm.

32. The method of claim 26 wherein:

(a) each algorithm of the step of transforming comprises:

(i) determining each index data symbol such that each index data symbol corresponds to a possible transition within a maximum likelihood decoding trellis; and

(ii) storing each generated soft decision metric in a particular address of a memory based lookup table such that the associated index data symbol comprises a portion of the particular address in the lookup table; and

(b) the step of generating comprises generating at least one estimated data bit by utilizing maximum likelihood decoding techniques in which such transition corresponding index data symbols are used to address and retrieve at least one soft decision metric from the memory based lookup table.

33. The method of claim 26 wherein the communication channel is selected from the group consisting essentially of an electronic data bus, radio communication link, wireline and optical fiber link.

34. A method of decoding data samples of a received signal comprising:

(a) grouping data samples of a received signal;

(b) transforming the groups of data samples into index data symbols and associated deinterleaved soft decision metrics according to an algorithm selected from the group consisting essentially of (i) generating a plurality of soft decision similarity metrics and index data symbols for each group of data samples such that one index data symbol is associated with each soft decision metric and subsequently deinterleaving by group each group of soft decision metrics within a predetermined size block and (ii) deinterleaving by group each group of data samples within a predetermined size block and subsequently generating a plurality of soft decision similarity metrics and index data symbols for each deinterleaved group of data samples such that one index data symbol is associated with each soft decision metric, each soft decision metric corresponding to a measure of confidence that a particular group of data samples is substantially similar to a particular orthogonal code from within a set of mutually orthogonal codes; and

(c) generating at least one estimated data bit by utilizing maximum likelihood decoding techniques to derive the at least one estimated data bit from the index data symbols and associated deinterleaved soft decision metrics.

35. The method of claim 34 wherein the predetermined block size is derived from the number of soft decision metrics generated for each group of data samples, the number of data samples in each group of data samples and the maximum number of data samples which can be sampled from a received signal transmission block.

36. The method of claim 34 further comprising the step of sampling a signal received from over a communication channel into data samples.

37. The method of claim 36 wherein the step of sampling comprises despreading the received signal with a spreading code to derive data samples.

38. The method of claim 34 wherein the step of transforming comprises generating soft decision similarity metrics by utilizing a Hadamard transform matrix algorithm on a group of data samples.

39. The method of claim 34 wherein the step of decoding comprises generating at least one estimated data bit by utilizing maximum likelihood decoding techniques which are substantially similar to the Viterbi decoding algorithm.

40. The method of claim 34 wherein:

(a) each algorithm of the step of transforming comprises:

(i) determining each index data symbol such that each index data symbol corresponds to a possible transition within a maximum likelihood decoding trellis; and

(ii) storing each generated soft decision metric in a particular address of a memory based lookup table such that the associated index data symbol comprises a portion of the particular address in the lookup table; and

(b) the step of generating comprises generating at least one estimated data bit by utilizing maximum likelihood decoding techniques in which such transition corresponding index data symbols are used to address and retrieve at least one soft decision metric from the memory based lookup table.

41. The method of claim 36 wherein the communication channel is selected from the group consisting essentially of an electronic data bus, radio communication link, wireline and optical fiber link.

FIELD OF THE INVENTION

The present invention relates to communication systems which employ spread-spectrum signals and, more particularly, to a method and apparatus for convolutional orthogonal coding in a spread spectrum communication system.

BACKGROUND OF THE INVENTION

Communication systems take many forms. In general, the purpose of a communication system is to transmit information-bearing signals from a source, located at one point, to a user destination, located at another point some distance away. A communication system generally consists of three basic components: transmitter, channel, and receiver. The transmitter has the function of processing the message signal into a form suitable for transmission over the channel. This processing of the message signal is referred to as modulation. The function of the channel is to provide a physical connection between the transmitter output and the receiver input. The function of the receiver is to process the received signal so as to produce an estimate of the original message signal. This processing of the received signal is referred to as demodulation.

Two types of two-way communication channels exist, namely, point-to-point channels and point-to-multipoint channels. Examples of point-to-point channels include wirelines (e.g., local telephone transmission), microwave links, and optical fibers. In contrast, point-to-multipoint channels provide a capability where many receiving stations may be reached simultaneously from a single transmitter (e.g. cellular radio telephone communication systems). These point-to-multipoint systems are also termed Multiple Address Systems (MAS).

Analog and digital transmission methods are used to transmit a message signal over a communication channel. The use of digital methods offers several operational advantages over analog methods, including but not limited to: increased immunity to channel noise and interference, flexible operation of the system, common format for the transmission of different kinds of message signals, improved security of communication through the use of encryption, and increased capacity.

These advantages are attained at the cost of increased system complexity. However, through the use of very large-scale integration (VLSI) technology a cost-effective way of building the hardware has been developed.

To transmit a message signal (either analog or digital) over a bandpass communication channel, the message signal must be manipulated into a form suitable for efficient transmission over the channel. Modification of the message signal is achieved by means of a process termed modulation. This process involves varying some parameter of a carrier wave in accordance with the message signal in such a way that the spectrum of the modulated wave matches the assigned channel bandwidth. Correspondingly, the receiver is required to recreate the original message signal from a degraded version of the transmitted signal after propagation through the channel. The re-creation is accomplished by using a process known as demodulation, which is the inverse of the modulation process used in the transmitter.

In addition to providing efficient transmission, there are other reasons for performing modulation. In particular, the use of modulation permits multiplexing, that is, the simultaneous transmission of signals from several message sources over a common channel. Also, modulation may be used to convert the message signal into a form less susceptible to noise and interference.

For multiplexed communication systems, the system typically consists of many remote units (i.e. subscriber units) which require active service over a communication channel for a short or discrete portion of the communication channel resource rather than continuous use of the resources on a communication channel. Therefore, communication systems have been designed to incorporate the characteristic of communicating with many remote units for brief intervals on the same communication channel. These systems are termed multiple access communication systems.

One type of multiple access communication system is a spread spectrum system. In a spread spectrum system, a modulation technique is utilized in which a transmitted signal is spread over a wide frequency band within the communication channel. The frequency band is much wider than the minimum bandwidth required to transmit the information being sent. A voice signal, for example, can be sent with amplitude modulation (AM) in a bandwidth only twice that of the information itself. Other forms of modulation, such as low deviation frequency modulation (FM) or single sideband AM, also permit information to be transmitted in a bandwidth comparable to the bandwidth of the information itself. However, in a spread spectrum system, the modulation of a signal to be transmitted often includes taking a baseband signal (e.g., a voice channel) with a bandwidth of only a few kilohertz, and distributing the signal to be transmitted over a frequency band that may be many megahertz wide. This is accomplished by modulating the signal to be transmitted with the information to be sent and with a wideband encoding signal.

Three general types of spread spectrum communication techniques exist, including:

Direct Sequence

The modulation of a carrier by a digital code sequence whose bit rate is much higher than the information signal bandwidth. Such systems are referred to as "direct sequence" modulated systems.

Hopping

Carrier frequency shifting in discrete increments in a pattern dictated by a code sequence. These systems are called "frequency hoppers." The transmitter jumps from frequency to frequency within some predetermined set; the order of frequency usage is determined by a code sequence. Similarly "time hopping" and "time-frequency hopping" have times of transmission which are regulated by a code sequence.

Chirp

Pulse-FM or "chirp" modulation in which a carrier is swept over a wide band during a given pulse interval.

Information (i.e. the message signal) can be embedded in the spread spectrum signal by several methods. One method is to add the information to the spreading code before it is used for spreading modulation. This technique can be used in direct sequence and frequency hopping systems. It will be noted that the information being sent must be in a digital form prior to adding it to the spreading code, because the combination of the spreading code and the information typically a binary code involves module-2 addition. Alternatively, the information or message signal may be used to modulate a carrier before spreading it.

Thus, a spread spectrum system must have two properties: (1) the transmitted bandwidth should be much greater than the bandwidth or rate of the information being sent and (2) some function other than the information being sent is employed to determine the resulting modulated channel bandwidth.

Spread spectrum communication systems can be multiple access systems communication systems. One type of multiple access spread spectrum system is a code division multiple access (CDMA) system. In a CDMA system, communication between two communication units is accomplished by spreading each transmitted signal over the frequency band of the communication channel with a unique user spreading code. As a result, transmitted signals are in the same frequency band of the communication channel and are separated only by unique user spreading codes. These unique user spreading codes preferably are orthogonal to one another such that the cross-correlation between the spreading codes is approximately zero. CDMA systems may use direct sequence or frequency hopping spreading techniques. Particular transmitted signals can be retrieved from the communication channel by despreading a signal representative of the sum of signals in the communication channel with a user spreading code related to the particular transmitted signal which is to be retrieved from the communication channel. Further, when the user spreading codes are orthogonal to one another, the received signal can be correlated with a particular user spreading code such that only the desired user signal related to the particular spreading code is enhanced while the other signals for all of the other users are not enhanced.

It will be appreciated by those skilled in the art that several different spreading codes exist which can be used to separate data signals from one another in a CDMA communication system. These spreading codes include but are not limited to pseudonoise (PN) codes and Walsh codes. A Walsh code corresponds to a single row or column of the Hadamard matrix. For example, in a 64 channel CDMA spread spectrum system, particular mutually orthogonal Walsh codes can be selected from the set of 64 Walsh codes within a 64 by 64 Hadamard matrix. Also, a particular data signal can be separated from the other data signals by using a particular Walsh code to spread the particular data signal.

Further it will be appreciated by those skilled in the art that spreading codes can be used to channel code data signals. The data signals are channel coded to improve performance of the communication system by enabling transmitted signals to better withstand the effects of various channel impairments, such as noise, fading, and jamming. Typically, channel coding reduces the probability of bit error, and/or reduces the required signal to noise ratio usually expressed as error bits per noise density (E.sub.b /N.sub.0), to recover the signal at the cost of expending more bandwidth than would otherwise be necessary to transmit the data signal. For example, Walsh codes can be used to channel code a data signal prior to modulation of the data signal for subsequent transmission. Similarly PN spreading codes can be used to channel code a data signal.

A typical spread spectrum transmission involves expanding the bandwidth of an information signal, transmitting the expanded signal and recovering the desired information signal by remapping the received spread spectrum into the original information signals bandwidth. This series of bandwidth trades used in spread spectrum signaling techniques allows a communication system to deliver a relatively error-free information signal in a noisy signal environment or communication channel. The quality of recovery of the transmitted information signal from the communication channel is measured by the error rate (i.e., the number of errors in the recovery of the transmitted signal over a particular time span or received bit span) for some E.sub.b /N.sub.0. As the error rate increases the quality of the signal received by the receiving party decreases. As a result, communication systems typically are designed to limit the error rate to an upper bound or maximum so that the degradation in the quality of the received signal is limited. In CDMA spread spectrum communication systems, the error rate is related to the noise interference level in the communication channel which is directly related to number of simultaneous but code divided users within the communication channel. Thus, in order to limit the maximum error rate, the number of simultaneous code divided users in the communication channel is limited. However, the error rate can be reduced by using channel coding schemes. Therefore, by using channel coding schemes the number of simultaneous users in a communication channel can be increased while still maintaining the same maximum error rate limit.

As discussed in Digital Communications; Fundamentals and Applications by Bernard Sklar, published by Prentice Hall, Englewood Cliffs, N.J. in 1988, especially chapters 5 and 6 entitled "Channel Coding" found on pages 245-380, several of these channel coding schemes have been developed for use in communication systems. However, a need exists for these channel coding schemes to be specifically optimized for use in CDMA spread spectrum communication systems. Through the use of these optimized channel coding schemes, the number of simultaneous users in a communication channel can be increased over the number of simultaneous users in a communication channel using non-optimized channel coding while maintaining the same maximum error rate limit.

Summary of the Invention

A method and apparatus is provided for using orthogonal codes in encoding and decoding in a communication system. In encoding, input bits of a data signal are encoded into data symbols and the data symbols are grouped. The data symbols are encoded with an encoding algorithm (e.g., a block coding algorithm or a convolutional coding algorithm) which facilitates subsequent maximum likelihood decoding of the data symbols into estimated data bits. The groups of data symbols are translated according to either one of two algorithms. The first algorithm consists of interleaving by group each group of data symbols within a predetermined size block and subsequently deriving an orthogonal code from each group of interleaved data symbols. The alternative second algorithm consists of deriving an orthogonal code from each group of data symbols and subsequently interleaving by orthogonal code each orthogonal code within a predetermined size block.

In decoding, received data samples are grouped. The groups of data samples are transformed according to either one of two algorithms. The first algorithm consists of generating a plurality of soft decision similarity metrics and index data symbols for each group of data samples such that one soft decision metric is associated with each index data symbol and subsequently deinterleaving by group each group of soft decision metrics within a predetermined size block. The alternative second algorithm consists of deinterleaving by group each group of data samples within a predetermined size block and subsequently generating a plurality of soft decision similarity metrics and index data symbols for each deinterleaved group of data samples such that one soft decision metric is associated with each index data symbol. Each soft decision metric corresponds to a measure of confidence that a particular group of data samples is substantially similar to a particular orthogonal code from within a set of mutually orthogonal codes. After the grouped samples are transformed, at least one estimated data bit is generated by utilizing maximum likelihood decoding techniques to derive the at least one estimated data bit from the index data symbols and associated soft decision metrics.

BRIEF DESCRIPTION OF THE DRAWINGS

FIG. 1 is a block diagram showing a prior art communication system which uses orthogonal coding.

FIG. 2 is a block diagram showing a preferred embodiment communication system which uses orthogonal coding.

FIG. 3 is a block diagram showing a preferred embodiment decoding apparatus which uses a memory based lookup table.

FIG. 4 is block diagram showing a preferred embodiment matrix representation of an interleaver loaded with encoded data bits.

DETAILED DESCRIPTION

Referring now to FIG. 1, a prior art system for using orthogonal codes in encoding and decoding in a communication system is shown. In the encoding portion 100 of the communication system, traffic channel data bits 102 are input to an encoder 104 at a particular bit rate (e.g., 9.6 kbit/second). The input traffic channel data bits can include either voice converted to data by a vocoder, pure data, or a combination of the two types of data. Encoder 104 encodes the input data bits 102 into data symbols at a fixed encoding rate with an encoding algorithm which facilitates subsequent maximum likelihood decoding of the data symbols into data bits (e.g. convolutional or block coding algorithms). For example, encoder 104 encodes input data bits 102 (received at a rate of 9.6 kbits/second) at a fixed encoding rate of one data bit to three data symbols (i.e., 1/3) such that the encoder 102 outputs data symbols 106 at a 28.8 ksymbols/second rate.

The data symbols 106 are then input into an interleaver 108. Interleaver 108 block interleaves the input data symbols 106 at the symbol level. In the interleaver 108, the data symbols are individually input into a matrix which defines a predetermined size block of data symbols. The data symbols are input into locations within the matrix so that the matrix is filled in a column by column manner. The data symbols are individually output from locations within the matrix so that the matrix is emptied in a row by row manner. Typically, the matrix is a square matrix having a number of rows equal to the number of columns; however, other matrix forms can be chosen to increase the output interleaving distance between the consecutively input non-interleaved data symbols. The interleaved data symbols 110 are output by the interleaver 108 at the same data symbol rate that they were input (e.g., 28.8 ksymbols/second). The predetermined size of the block of data symbols defined by the matrix is derived from the maximum number of data symbols which can be transmitted at a predetermined chip rate within a predetermined length transmission block. For example, if data symbols 106 are output from the encoder 104 at a 28.8 ksymbols/second rate, then the maximum predetermined chip rate for transmitting those data symbols 106 is 28.8 ksymbols/second. Further, for example if the predetermined length of the transmission block is 20 milliseconds, then the predetermined size of the block of data symbols is 28.8 ksymbols/second times 20 milliseconds which equals 576 data symbols which defines a 18 by 32 matrix.

The interleaved data symbols 110 are then input to a mapper 112. The mapper 112 derives a sequence of fixed length orthogonal codes 114 (e.g., 64-ary Walsh codes) from the interleaved data symbols 110. In for example 64-ary orthogonal code signaling, the interleaved data symbols 110 are grouped into sets of six to select one out of the 64 orthogonal codes to represent the set of six data symbols. These 64 orthogonal codes preferably correspond to Walsh codes from a 64 by 64 Hadamard matrix wherein a Walsh code is a single row or column of the matrix. The mapper 112 outputs a sequence of Walsh codes 114 which correspond to the input data symbols 110 at a fixed symbol rate (e.g., 307.2 ksymbols/second).

The sequence of Walsh codes 114 is output from encoding portion 100 of the communication system and input to a transmitting portion 116 of the communication system. The sequence 114 is prepared for transmission over a communication channel by a modulator 117. Subsequently, the modulated sequence is provided to an antenna 118 for transmission over the communication channel 120.

The modulator 117 preferably prepares the sequence 114 for direct sequence code divided spread spectrum transmission by spreading the sequence 114 with a long spreading code (e.g. PN code). The spreading code is a user specific sequence of symbols or unique user code which is output at a fixed chip rate (e.g., 1.228 Mchips/second). In addition to providing an identification as to which user sent the encoded traffic channel data bits 102 over the communication channel 120, the unique user code enhances the security of the communication in the communication channel by scrambling the encoded traffic channel data bits 102. In addition, the user code spread encoded data bits (i.e. data symbols) are spread by a pair of short spreading codes (i.e. short when compared to the long spreading code) to generate an I-channel and Q-channel code spread sequence. The I-channel and Q-channel code spread sequences are used to bi-phase modulate a quadrature pair of sinusoids by driving the power level controls of the pair of sinusoids. The sinusoids output signals are summed, bandpass filtered, translated to an RF frequency, amplified, filtered and radiated by an antenna 118 to complete transmission of the traffic channel data bits 102 in a communication channel 120.

A receiving portion 122 of the communication system receives the transmitted spread spectrum signal from over the communication channel 120 through antenna 124. The