Convolutional encoding using a modified multiplier

A wireless communications device is disclosed, in which certain digital coding functions are realized according to a modified multiplier architecture. The device includes an encode and modulate function within which convolutional coding function is provided. The convolutional coding function may be realized as a modified parallel multiplier, in which carries among adder units are ignored or not generated. The datastream is applied to the multiplier as the multiplicand, while successive sets of code generator polynomial coefficients are applied as a multiplier. Carry-in and carry-out bits among the adder units are blocked in a coding mode, but passed in a multiplier mode. A similar arrangement of a modified parallel multiplier circuit may be used in generating a scrambling code that is applied prior to transmission.

CROSS-REFERENCE TO RELATED APPLICATIONS

Not applicable.

Not applicable.

BACKGROUND OF THE INVENTION

This invention is in the field of wireless communications, and is more specifically directed to the digital coding and modulation of broadband signals in such communications.

The popularity of mobile wireless communications has increased dramatically over recent years. It is expected that this technology will become even more popular in the foreseeable future, both in modem urban settings and also in rural or developing regions that are not well served by line-based telephone systems. This increasing wireless traffic strains the available communications bandwidth for a given level of system infrastructure. As a result, there is substantial interest in increasing bandwidth utilization of wireless communications system to handle this growth in traffic.

This trend toward heavier usage of wireless technologies for communications, in combination with the advent of so-called third-generation, or “3G”, wireless communications to carry not only voice, but also data, video, and other high data rate payloads, will require continuing improvements in the processing capabilities of the communications equipment. In particular, the higher required data rates will require corresponding increases in the digital processing of the communications payloads.

Modern digital communications technology utilizes multiple-access techniques to increase bandwidth utilization, and thus to carry more wireless traffic. Under current approaches, both time division multiple access (TDMA) and code division multiple access (CDMA) techniques are used in the art to enable the simultaneous operation of multiple communication sessions, or wireless “connections”, each involving voice communications, data communications, or any type of digital payload. As evident from the name, TDMA communications are performed by the assignment of time slots to each of multiple communications, with each conversation transmitted alternately over short time periods. CDMA technology, on the other hand, permits multiple communication sessions to be transmitted simultaneously in both time and frequency, by modulating the signal with a specified code. On receipt, application of the code will recover the corresponding conversation, to the exclusion of the other simultaneously received conversations.

In both TDMA and CDMA communications, according to conventional and expected next-generation approaches, digital coding is applied for various purposes. An example of a typical digital code is convolutional coding, which inserts redundancy into the digital word stream being transmitted. In broadband communications, successive digital words in the transmitted digital datastream are effectively split into multiple subchannels, each subchannel being separately spread and encoded. Convolutional coding is applied to each subchannel, with the inserted redundancy providing the ability of forward error correction at the receiver. This convolutional coding thus effectively increases the signal-to-noise ratio of the wireless transmission.

FIG. 1illustrates convolutional coder5, constructed according to conventional techniques, and which in this example is based on the 3GPP 25.212 third-generation standard. In convolutional coder5ofFIG. 1, the code rate is 1/3, considering that the input bitstream x(k) applies single bits, and that three output bitstreams y0(k), y1(k), y2(k) are generated. The constraint length of this example is nine, considering the eight delay stages27through20. The current state of input x(k) and the eight previous states of input x(k) are used to produce the output bitstreams y0(k), y1(k), y2(k). As shown inFIG. 1, convolutional coder5also includes exclusive-OR functions4, arranged to implement the desired convolutional code. Each exclusive-OR function4has an input from one of delay stages2, and an input from a previous exclusive-OR function4(or directly from input x(k)).

The positions of the exclusive-OR functions4determine the code generator polynomials G0, G1, G2that generate the outputs y0(k), y1(k), y2(k), respectively. According to the conventional nomenclature, the convolutional code ofFIG. 1is referred to as K=9, (5578, 6638, 7118), with generator polynomials G0=5578, G1=6638, and G2=7118. Outputs y0(k), y1(k), y2(k) are presented once per cycle, and thus produce a three bit sequence that is representative of a corresponding input bit x(k), and that includes redundant information from which forward error correction techniques can recover the true signal from a corrupted received transmission.

As shown inFIG. 1, convolutional coder5can be implemented by way of a shift register containing delay stages2, and combinatorial logic for realizing exclusive-OR functions4. However, in such an implementation, either the convolutional code must be hard-wired into convolutional coder5, or alternatively the placement of a selectable exclusive-OR function4for each delay stage output and each generator polynomial (e.g., twenty-four functions4in convolutional coder5ofFIG. 1), must be implemented. Such an architecture may turn out to be costly, yet with limited performance.

Another type of coding performed in conventional digital wireless communications is the application of a scrambling code. As currently used, this scrambling code is a cell-specific sequence that is applied to the encoded data stream in a wireless communication. The receiving element, with knowledge of the cell-specific code, can thus distinguish communications in its cell from those that are received from wireless units in physically neighboring cells.

By way of further background,FIG. 2illustrates a conventional scrambling code generator10. As mentioned above and as known in the art, the application of a scrambling code enables a wireless receiver to resolve those communications received from its own physical cell from those communications received from other cells, and unintended for receipt by that wireless element. As known in the art, scrambling code generator10generates in-phase and quadrature components Ic(k), Qc(k), respectively, of a cell-specific scrambling code. These components are applied to respective in-phase and quadrature components of a datastream, modulated according to a quadrature amplitude modulation (QAM) constellation.

Scrambling code generator10ofFIG. 2includes delay stage sequence15I and delay stage sequence15Q, each sequence having eighteen delay stages numbered from 0 to 17 in this example. A sample of in-phase code component Ic(k) is generated by exclusive-OR function19I, which receives the outputs of the final delay stages, numbered 0, in delay stage sequences15I,15Q. A corresponding sample of quadrature code component Qc(k) is generated by exclusive-OR function19Q, which receives the outputs of feed-forward exclusive-OR functions 12, 16, each of which receive the contents of delay stages15I,15Q in the corresponding sequences, selected according to the particular scrambling code polynomial. In this example, feed-forward exclusive-OR function 12 receives the outputs of the delay stages numbered 4, 6, and 15 in delay stage sequence15I4; feed-forward exclusive OR function16receives the outputs of the delay stages numbered5and15in delay stage sequence15Q. The contents of delay stages15I,15Q are regenerated by feedback exclusive-OR functions 14, 18. In this example, feedback exclusive-OR function 14 receives inputs from the final delay stage (numbered 0) and the delay stage numbered 7 in delay stage sequence15I, and forwards its output to the input of the first delay stage, numbered 17, in delay stage sequence15I. Also in this example, feedback exclusive-OR function18 receives inputs from the final delay stage15Q and from the delay stages numbered 5 and 7 in delay stage sequence15Q, and has its output connected to the input of the first delay stage, numbered 17, in delay stage sequence15Q.

Similarly as in the case of convolutional coder5, scrambling code generator10may be realized by way of shift registers and combinatorial logic. However, in order to provide variations in the scrambling code to be applied, the exclusive-OR functions12through18must be selectable according to the code generating polynomial. Such flexibility requires a large number of potential connections both in and out of exclusive-OR functions, as well as circuitry for selectably enabling and disabling these potential connections.

By way of further background, conventional integer multiplier circuits, such as used in microprocessors and digital signal processors, are arranged to perform successive addition. For example, a typical conventional integer multiplier adds selected left-shifted replications of the multiplicand, with the summed shifted multiplicands being those corresponding to “1” bits in the multiplier; “0” bits of the multiplier block the addition of corresponding shift positions of the multiplicand from being included in the product. The additions include the use of carry-in and carry-out signals.

FIG. 3illustrates conventional parallel multiplier20, for multiplying two four-bit digital values X, Y. This construction is disclosed in U.S. Pat. No. 4,598,382. Multiplier20includes an array of sixteen full two-bit adder units U1through U16. Adder units U are arranged in four rows of four, each row associated with one bit of multiplier Y. For example, adder units U1through U4are associated with multiplier bit Y1, adder units U5through U8are associated with multiplier bit Y2, and so on. Each row of adder units U receive the four bits X1through X4of the multiplicand, and the associated bit of multiplier Y for that row. In operation, multiplicand X is added to itself, left-shifted (i.e., multiplied by two), depending upon the state of the ascending bits of multiplier Y, with carries propagating accordingly. The resulting product word P is thus the binary integer product of multiplicand X and multiplier Y.

The construction of each adder unit U in multiplier20is illustrated with respect to adder unit U16. As shown inFIG. 3, adder unit U16includes full two-bit adder22, and AND gate24. AND gate24receives a bit of multiplicand X (bit X4in this example, for adder unit U16) and a bit of multiplier Y (bit Y4in this example, for adder unit U16), and outputs addend A corresponding to the logical AND of these multiplier and multiplicand bits. In this way, the state of multiplier bit Y determines whether the corresponding multiplicand bit X is included in the sum performed by full adder22. Addend B, presented to full adder22, depends upon the particular position of adder unit U within multiplier20. Adder units U1through U4, in the top row of multiplier20, simply receive a “0” bit for their addends B. Later rows of adder units U in multiplier20receive the results of earlier rows. For example, adder units U5through U7, left-shifted by one position in the second row, receive sum bits S from a corresponding adder U2through U4in the first row; specifically, adder unit U5receives the sum output S of adder unit U2, adder unit U6receives the sum output S of adder unit U3, and adder unit U7receives the sum output S of adder unit U4. The most significant adder unit U in each of the later rows receives, as its addend B, the carry output C of the most significant adder unit U in the previous row; for example, adder unit U8receives the carry out bit C from adder unit U4. Each adder unit U other than the least significant position receives carry in bit C′, corresponding to the carry out C bit of its least significant neighbor, and applies this carry in C′ to its full adder22.

The sum output bits of the least significant adder units U1, U5, U9in earlier rows are presented as product bits P1, P2, P3, respectively. The sum output bits S from adder units U in the last row are presented as the higher order product bits. In the example of multiplier20inFIG. 3, the sum output bits S from adder units U13through U16correspond to product bits P4through P7, respectively. The carry out bit C from the most significant adder unit U in the last row, adder unit U16in this example, becomes the most significant product bit, P8in this example.

BRIEF SUMMARY OF THE INVENTION

It is an object of the present invention to provide circuitry for efficiently encoding communicated datastreams.

It is a further object of the present invention to provide such circuitry that provide flexibility in the code generating polynomial coefficients.

It is a further object of this invention to provide such circuitry that can be readily implemented by the modification of known architectures.

It is a further object of this invention to provide such circuitry that is readily suited for implementation on a programmable device such as a digital signal processor.

It is a further object of this invention to provide such circuitry in the form of convolutional coding circuitry for encoding a datastream for wireless transmission.

It is a further object of this invention to provide such circuitry in the form of a code generator, such as for generating a scrambling code for wireless transmission.

Other objects and advantages of the present invention will be apparent to those of ordinary skill in the art having reference to the following specification together with its drawings.

The present invention may be implemented in a circuit for generating or applying a code, by way of a modified multiplier circuit. The multiplier circuit includes an array of gated exclusive-OR functions, for performing cumulative exclusive-OR operations upon shifted delayed bitstream data. The gating of the exclusive-OR operations are controlled responsive to coefficients of the code generator polynomials. The circuit is implemented by a parallel multiplier array of adders, with carry propagation blocked, and may be used for convolutional coding or scrambling code generation in a wireless communications unit.

DETAILED DESCRIPTION OF THE INVENTION

The present invention will be described in connection with a wireless voice and data communications system, such as a wireless telephone base station. It is contemplated, however, that the present invention may also be used with other communications systems, including other types of mobile wireless communications applications, other spread spectrum or broadband technologies, and other applications in the field of digital radio. It is to be understood, therefore, that the following description is presented by way of example only, and is not intended to limit the scope of the present invention as claimed.

Referring now toFIG. 4, wireless unit30constructed according to the preferred embodiment of the invention will now be described in detail. Wireless unit30ofFIG. 4corresponds to a wireless base station, for example according to at least the so-called “second generation”, or “2G” capability, such as is typically used to carry out TDMA and CDMA broadband communication; it is further contemplated that wireless unit30may also be constructed to provide the so-called “third generation” or “3G” communications, which include data and video services. Of course, it is contemplated that the present invention may also be implemented in wireless handsets and other digital radio applications, for similar benefits from this invention. The architecture of the construction of wireless unit32shown inFIG. 4is provided by way of example only, it being understood that such other alternative architectures may also be used in connection with the present invention.

Radio subsystem26of wireless base station30is directly connected to base station antenna BSA, and handles the power amplification and analog processing of signals transmitted and received over antenna A. On the transmit side, modulator27in radio subsystem26receives the signals to be transmitted from RF (radio frequency) interface circuitry32, and generates a broadband modulated analog signal, under the control of synthesizer25. Power amplifier21amplifies the output of modulator27for transmission via antenna BSA. On the receive side, incoming signals from antenna BSA are received by receiver23, filtered and processed under the control of synthesizer25, and forwarded to RF interface circuitry32, which in turn forwards the signals to digital signal processor (DSP)40.

DSP40preferably has a significant amount of processing capacity to handle the digital processing necessary for both the transmit and receive operations. An example of a suitable digital signal processor for use as DSP40is the TMS320c6x family of digital signal processors available from Texas Instruments Incorporated, a preferred example of which is the TMS320C6416 DSP.

RF interface circuitry32processes both incoming and outgoing signals within the analog baseband of wireless base station30. On the transmit side, RF interface circuitry32receives digital signals from DSP40, and performs the appropriate filtering and phase modulation appropriate for the particular transmission protocol. For example, multiple channels of encoded digital bitstreams, corresponding to the combination of both in-phase (I) and quadrature (Q) components, are forwarded to RF interface circuitry32by DSP40. RF interface circuitry32converts these digital data into analog signals, phase-shifts the selected converted bitstreams to provide both in-phase (I) and quadrature (Q) analog signal components, and applies analog filtering as appropriate to the signals to be handed off to modulator27in radio subsystem26.

On the receive side, RF interface circuitry32converts the analog signal received by receiver23of radio subsystem26into the appropriate digital format for processing by DSP40. For example, in-phase (I) and quadrature (Q) components of the received signal are separated and filtered. Analog to digital conversion is then carried out by RF interface circuitry32, so that digital bitstreams corresponding to the separated and filtered components of the received signal may be received by DSP40.

DSP40executes the appropriate digital signal processing upon both the signals to be transmitted and those received. In this regard, DSP40is coupled to network interface34, which in turn couples base station30to the computer and communications network, including the Public Switched Telephone Network (PSTN). Network interface34is a conventional subsystem, including such functions as a physical layer interface and a network interface adapter, and selected according to the type of network and corresponding interface desired for base station30.

The digital functions performed by DSP40will depend, of course, upon the communications protocol used by wireless base station30. The functions shown inFIG. 4for DSP40correspond to those functions as performed for each user currently communicating with base station30; the functionality for only one user is shown inFIG. 4, for clarity. On the receive side, DSP40will digitally perform such functions as a rake receive function, identifying the user associated with each communication, channel decoding of the data from RF interface circuitry32to retrieve a data signal from the received digitally spread signal, followed by the decoding of the speech symbols from the channel decoded data using techniques such as inverse discrete Fourier transforms (IDFT) and the like, as illustrated inFIG. 4by user and symbol detection and decode circuitry50. Equalization, error correction, and decryption processes are also performed upon the received signal as appropriate. The resulting signal processed by DSP40on the receive side is then forwarded to network interface34, to be forwarded to the appropriate network destination.

On the transmit side, the incoming voice communications, or other incoming data in the 3G sense, from the PSTN network, are forwarded to DSP40by network interface34. Encode and modulate function54performs the appropriate digital processing functions for the particular protocol. For example, encode and modulate function54may first encode the received digital data into symbols, for example by way of a DFT operation. These symbols are then spread, by way of a spreading code, into a sequence of chips according to a selected chip rate; the spreading may also include the spreading of the symbols into multiple subchannels. According to the preferred embodiment of the invention, which will be described in further detail below, a cell-specific scrambling code is then applied to the spread symbols, and the scrambled spread symbols are modulated. In general, this modulation splits the subchannels into in-phase (I) and quadrature (Q) groups, so that the eventual modulated signal includes both components. The spread spectrum sequence is converted into an analog signal by RF interface32, with the desired filtering and pre-equalization to compensate for channel distortion, and is then transmitted over antenna BSA by radio subsystem26.

Other support circuitry is also provided within wireless base station30as shown inFIG. 4. In this example, controller36handles the control of wireless base station30other than the data path. Such control functions include resource management, operating system control, and control of the human interface; in this regard, controller36operates with such functions as memory33(for storage of the operating system and user preferences), keyboard37, and user display38.

Referring now toFIG. 5, the functional construction and operation of encode and modulate function54will now be described. In the example ofFIG. 4, in which encode and modulate function54is illustrated as contained within DSP40, it is contemplated that many of these operations within encode and modulate function54can be carried out by the execution of software routines by DSP40. It is also contemplated that some or all of these functions illustrated inFIG. 5can be performed by dedicated hardware, such as custom or semi-custom logic circuits. The tradeoff between hardware and software realizations of these functions is contemplated to be within the skill and discretion of the artisan having reference to this specification.

Multiple datastreams X(k) are received by encode and modulate function54, each datastream X(k) corresponding to one of multiple subchannels, each of which will be separately spread and encoded as typical for broadband communications. Each data stream X(k) is applied to convolution coding function60to insert redundancy into that subchannel for purposes of forward error correction. The construction of convolutional coding function60according to the preferred embodiment of the invention will be described in detail below. These streams are then multiplexed by interleaver61, and then demultiplexed by demultiplexer62prior to application to Walsh coding function64. As known in the art, Walsh coding function64, as known in the art, multiplies the data stream by a spreading code (e.g., a Walsh code, or Walsh-Hadamard code) to spread each bit of bitstream X(k) into a modulated sequence of multiple “chips”. In effect, Walsh coding function64converts each bit of its received data stream into a series of samples, or chips, modulated by the spreading code, so that the chip rate out of function64is a modulated multiple of the data rate of the input datastream, for each subchannel.

As shown inFIG. 5, the subchannel outputs of Walsh coding function64are then applied to separate spread and modulate functions55lthrough55n. In each of spread and modulate functions55lthrough55n, a so-called “long” modulation code is then applied to the datastream by long code spreader68. As known in the art, the “long” code is a modulation code that is selected in a pseudo-random manner, to greatly reduce the probability of a collision among multiple wireless units in a given coverage area. The spreading long code applied in function68is a “long” code, to ensure that multiple orthogonal communications can be carried out simultaneously within the cell.

The output of long code spreader function68is a sequence of digital words. This output sequence is applied to in-phase spread function70I and to quadrature spread function70Q, assigning some of the multiplexed data words to an in-phase (I) channel and some to a quadrature (Q) channel, as precursors to I and Q components, respectively, of a complex analog output signal. Often, specific subchannels are assigned to the I and Q components; for example, in a simple system, a data channel may be assigned to the in-phase component, while a control channel may be assigned to the quadrature component. More typically, multiple data subchannels are assigned to each of the I and Q channels. At this point in the encoding and modulation process, the I and Q channels are still sequences of digital words.

Data sequences I(k), Q(k), from the outputs of spread functions70I,70Q, respectively, are then applied to bit modulator72. Bit modulator function72is either a software routine executable by DSP40, or alternatively is dedicated logic circuitry, that combines these data sequences I(k), Q(k) with a cell-specific scrambling code c(k) that is generated by scrambling code generator75to produce a modulated output sequence Y(k). The construction of scrambling code generator75according to the preferred embodiment of the invention will be described in further detail below. The scrambled output sequence Y(k) can be resolved by the receiving element to distinguish these communications from those that may have been received from wireless units in other physical cells. Alternatively, the preferred embodiment of the invention may be used in connection with the modulation of complex digital words with other types of scrambling codes, and with other complex codes in general.

The output of the spread and modulate functions55are then recombined by multiplexer74into an output datastream Y(k), and forwarded to RF interface32(FIG. 4) for transmission.

As discussed above in the Background of the Invention, conventional convolutional coding circuits and code generator circuits typically involve delay stages or shift registers, in combination with exclusive-OR functions, but with a significant amount of complexity required for programmability. In connection with this invention, it has been discovered that one may compare the truth table of the exclusive-OR function with that of a full adder with carries. The full adder truth table, for one-bit addends A, B, is:

Input AInput BA ⊕ B000011101110
This exclusive-OR truth table corresponds exactly to the full adder truth table, if carries (both in and out) are blocked or ignored. As will become apparent from the following description of the preferred embodiment of the invention, this exact correspondence is used to advantage in an architecture for convolutional and other digital coding.

Referring now toFIGS. 6aand6b, the data flow in convolutional coding function60according to the preferred embodiment of the invention will now be described, for one subchannel; the architecture and construction of convolutional coding function60according to the preferred embodiment of the invention will be described in detail below relative toFIGS. 8 and 9. As noted above, encode and modulate function54can operate on multiple subchannels in parallel, and as such convolutional coding function60is typically embodied in multiple instances, one instance for each of the subchannels being encoded. In the example ofFIGS. 6aand6b, the code generator polynomial Giis ninth-order, such that nine (one-bit) coefficients Gi,0through Gi,8are used, coefficient Gi,8being the most significant coefficient. Also in this example, nine coded bits R0through R8are generated at a time. In convolutional coding function60, one row80of delay stages D is provided for each bit of the code generator polynomial. Accordingly, in the example ofFIGS. 6aand6b, convolutional coding function60includes nine delay stage rows800through808. Each row80includes seventeen delay stages D in this example, which corresponds to the convolution length (nine) plus the number of output bits (eight) presented.

Of course, the particular construction of convolutional coding function60can vary widely. For example, it is contemplated that a 32×16 arrangement, generating sixteen code bits at a time, will be attractive in many applications. The particular size and organization will thus depend upon the particular design and application.

In the data flow through convolutional coding function60according to this embodiment of the invention, each delay stage D has an output that is forwarded to the input of the next delay stage in its same row80, and that is also forwarded to be combined to the next row, in the least significant direction of code generator polynomial Gi, by an exclusive-OR function. InFIGS. 6aand6b, the solid horizontal lines thus represent the temporal shifting of the state of each of delay stages D along common rows80, while the dashed vertical lines represent exclusive-OR combinations toward result bits R. According to this embodiment of the invention, the outputs of delay stages D in a common column (i.e., those delay stages D aligned with one another in each of rows80) are exclusive-ORed depending upon the state of the corresponding coefficient bit G. This exclusive-OR gating is implemented by blocking the forwarding of carry bits within a parallel multiplier as will now be described relative toFIG. 7.

FIG. 7illustrates delay stage Dj,k, which is the kth delay stage in the jth row80j. The output of delay stage Dj,kis applied to one input of AND gate62j,kand is also forwarded to the input of the next delay stage Dj,k+1in row80j. The other input to AND gate62j,kis the code generator coefficient Gjfor row80j. The output of AND gate62j,kis applied to one input of full adder64j,k, which receives the output of a corresponding full adder64j−1,kin the previous row at its other input. In this way, if the code generator bit Gjis a “1”, the state of delay stage Dj,kis applied to full adder64j,kalong with the output of the previous full adder64j−1,kis to derive the state to be applied to full adder64j+1,kin the next row80j+1. If the code generator bit Gjis “0”, the output of the previous full adder64j−1,kis simply passed along to full adder64j+1,kin the next row80j+1without change.

AND gate65j,kreceives carry-out bit C_OUTj,k+1from previous full adder64j,k+1at one input, and control signal MPY/ENCODE_ at another input. In an encode mode, control signal MPY/ENCODE_ is at a low logic level, which blocks carry-out bit C_OUTj,k+1, from being applied to full adder64j,kand thus from being incorporated into the addition. A corresponding AND gate65is included at each exclusive-OR location in convolutional coding function60, and therefore carry-out bit C_OUTj,kfrom full adder64j,kis blocked from being applied to the next full adder64j,k+1. This blocking of carry bits by AND gate65causes full adder64j,kto have the identical truth table as an exclusive-OR gate, as discussed above. In a multiply mode, however, with control signal MPY/ENCODE_ at a high level, carry bits are applied to each full adder64, permitting the same circuitry to be used as a multiplier when desired.

Referring back toFIGS. 6aand6b, convolutional coding function60is thus operable to generate code output bits based upon the exclusive-OR of a current input bit x(k) and selected ones of its eight previous values. The current input bit x(k) is applied to the input of the first delay stage D in each of rows80. Rows80of delay stages D effectively operate as shift registers, such that the receipt of each successive input bit x(k) with each clock cycle will advance the contents of delay stages D along rows80. As a result, result bits R0through R8correspond to nine combinations of input bit x(k) sequences. For example, result bit R0is generated from the exclusive-OR combination of one or more of input bits x(k), x(k−1), x(k−2), . . . x(k−8). Similarly, result bit R1is generated from the exclusive-OR combination of one or more of input bits x(k−1) through x(k−9), and so on, with last result bit R8generated from the exclusive-OR combination of one or more of input bits x(k−8) through x(k−16). The selection of those input bits x to be combined in exclusive-OR fashion depend upon the states of the code generator coefficients Gi,kinFIGS. 6aand6b; the same coefficient bit Gi,kis applied along the entire row80j.

The length of rows80are equal, for purposes of data consistency. As a result, as shown inFIGS. 6aand6b, invalid result bits IDMSBand IDLSBare generated but ignored; these result bits being invalid because they do not include a possible bit from each row80.

In operation, convolutional coding function60receives a sequence of input data bits x(k) of a length corresponding to the length of the convolution to be performed. In the example ofFIGS. 6aand6b, in which the convolution length is nine, nine input data bits x(k) through x(k−8) are applied in sequence to convolutional coding function60. The previous contents x(k−9) through x(k−16) of delay stages D in rows80are shifted accordingly, with older data bits x(k−17) et seq. shifted out of convolutional coding function60. Each row80of convolutional coding function60thus contains data bits x(k) through x(k−16), with input data bit x(k) at the input to its first delay stages, and input data bits x(k−1) through x(k−16) at the outputs of its sixteen delay stages D.

The coefficients G1,0through G1,8of a first convolutional code are then applied to convolutional coding function60, in this example. As described above, the most significant bit G1,8is applied to the right-most shifted (top) row808, and the least significant bit G1,0is applied to the left-most shifted (bottom) row800. The state of the coefficients G1,jdetermine the exclusive-OR operations to be performed by each column of convolutional coding function60, in the manner described above relative toFIG. 7. The exclusive-OR operation generates nine useful result bits R0through R8, which are then forwarded along in encode and modulate function54, for example to interleaver61(FIG. 5).

A next set of coefficients G2,0through G2,8are then applied to convolutional coding function60, for the set of input data bits x(k) through x(k−16) retained by rows80. These coefficients G2,jagain control the exclusive-ORing of input data bits x(k) through x(k−16), producing another set of result bits R0through R8for this convolutional code. The code rate of convolutional coding function60determines the number of sets of coefficients Gi,jthat are applied. For example, a code rate of 1/3 will be effected by applying three sets of coefficients Gi,jto rows80of convolutional coding function60. After the last set of coefficients Gi,jare applied and the result bits R generated, the next sequence of input bits x can then be shifted into convolutional coding function60and the process repeated.

According to the preferred embodiment of the invention, convolutional coding function60is implemented by way of a modified multiplier circuit.FIG. 8illustrates an example of convolutional coding function60, including modified multiplier circuit90constructed according to this embodiment of the invention.

The inputs to modified multiplier circuit90include input data bits x(k), which is applied to the first of a sequence of delay stages D0through Dm−1. Delay stages D0through Dm−1may be realized by way of a shift register, if desired. Input data bit x(k) is also applied to an input of modified multiplier circuit90, along with the outputs of each of delay stages D0through Dm−1, representing data bits x(k−1) through x(k−m). Input data bits x(k) through x(k−m) thus take the place of the multiplicand to be applied to modified multiplier circuit90.

The other input to modified multiplier circuit90is a selected one of a set of coefficients Gi,corresponding to the code generator polynomial. In this example, in which the code rate is 1/3, three registers940,941,942, are provided for storing coefficients G1, G2, G3, respectively. The outputs of registers94are applied to multiplexer92, which selects one set of coefficients Gito be applied to modified multiplier circuit90as the multiplier. It is contemplated that the contents of register94, and thus the code generator coefficients Gi, can be readily rewritten by digital circuitry as desired, via the operation of programmable logic such as a digital signal processor or microprocessor. Great flexibility in the operation of convolutional coding circuit60according to this embodiment of the invention is therefore attained.

In addition, as shown inFIG. 8, modified multiplier circuit9baccording to this embodiment of the invention also includes receives a control input on line MPY/ENCODE_. The control input on line MPY/ENCODE permits selective control of the operation of modified multiplier circuit90so that it operates as a conventional multiplier in a multiply mode, but as an exclusive-OR function as described above relative toFIGS. 6 and 7in an encoding mode. This dual function of modified multiplier circuit90enables its efficient use in conventional integrated circuits, such as a microprocessor or digital signal processor.

The output of modified multiplier circuit90are result bits R. As described above relative toFIGS. 6aand6b, the number of result bits R matches the convolution length of the code generator polynomials, and thus the number of coefficients in each set of coefficients Gi,j. As described above relative toFIGS. 6aand6b, other data bits are also generated by modified multiplier circuit90, but are invalid and thus ignored.

The example of convolutional coding circuit60illustrated inFIG. 8operates upon single-bit input data bits x and single-bit coefficients Gi,j. It is contemplated, in connection with this invention, that the present invention may alternatively be applied to multiple bit data input samples, and multiple bit coefficient values, by straightforward extension of the architecture of modified multiplier90and the rest of convolutional coder circuit60.

Referring now toFIG. 9, the construction of modified multiplier90will now be described in further detail, with reference to a detailed description of a representative portion. As described above, the logical truth table of an exclusive-OR function is equal to the logical truth table of an adder, if carry-in and carry-out bits are ignored or blocked.

In the portion of modified multiplier90illustrated inFIG. 9, an array of sixteen adder units U are illustrated, for performing the exclusive-OR functions involving input data bits x(n) through x(n−3), which are a subset of input data bits x(k) through x(k−m) applied to modified multiplier90. The exclusive-OR functions are controlled by code generator polynomial coefficients Gi,jthrough Gi,j+3, which are a subset of coefficients Gi, through Giapplied by multiplexer92to modified multiplier90. Of course, the number of adder units U within modified multiplier circuit90will be the product of the number of coefficient bits Gitimes the number m+1 of input data bits x(k) through x(k−m) applied to modified multiplier circuit90.

As shown inFIG. 9, with reference to adder unit U16, each adder unit U includes adder102and AND gate100. Adder102is constructed in the conventional manner as a full adder, except that it receives no carry-in bit and produces no carry-out bit. AND gate100in each adder unit U receives the corresponding code generator polynomial coefficient Gi,jat one input, and the corresponding input data bit x at its other input; the output of AND gate100is forwarded as one addend (A) to adder102. The other addend (B) applied to adder102is the sum bit S from the adder unit U in the adjacent higher order row. Each adder unit U then produces a sum bit S responsive to the binary sum, without carry, of the bits at its addend A and B inputs. For example, with reference to adder unit U16ofFIG. 9, which is in the lthcolumn and jthrow, sum bit Si,j+1is received at one addend input (B) of full adder102, and its other addend input (A) receives the logical AND (performed by AND gate100) of input data bit x(n) and coefficient bit Gi,j. The output of adder unit U16is sum bit Si,j, which is forwarded to the aligned adder unit in the next least significant row.

According to this embodiment of the invention, each adder unit U also includes AND gate104, which receives the carry-out bit from a preceding adder unit in the same row at one input, and which receives a control signal MPY/ENCODE_at another input. In the example ofFIG. 9, AND gate104in adder unit U16receives the carry-out bit from adder unit U15at that input. Control signal MPY/ENCODE_ is applied to each adder unit U in modified multiplier90, as shown inFIG. 9, to permit modified multiplier90to selectably operate either as a conventional parallel multiplier in a multiply mode (line MPY/ENCODE_ at a high level), or as an exclusive-OR “engine” as used in the coding functions such as convolutional coding function60in an encoding mode (line MPY/ENCODE_ at a low level). As described above relative toFIG. 7, carry bits are blocked by line MPY/ENCODE_ at a low level, which forces the output of each AND gate104low, regardless of the state of its corresponding carry-out bit. In this state, full adder102performs the exclusive-OR of their respective addends, because the truth table of an adder equates to that of an exclusive-OR gate when carries are ignored.

Modified multiplier circuit90according to this embodiment of the invention can also operate as a conventional multiplier in multiply mode (fine MPY/ENCODE_ at a high level), because in this state each AND gate104in each adder unit U will pass the carry-out bit from the previous adder unit U in the same row to its full adder102. This dual function capability enables modified multiplier circuit90to function as a conventional multiplier, for example as often included within programmable logic circuits such as microprocessors and digital signal processors.

Alternatively, the present invention can be implemented without modified multiplier circuit90having this dual function. In this alternative implementation, AND gates104can be eliminated so long as none of adder units U have either a carry-out output or a carry-in input. The coding function described in this specification will be performed identically by such an alternative implementation, but of course the multiplier will not be capable of performing a conventional parallel multiplication and therefore will not be available outside of the coding functions described in this specification.

As shown inFIG. 9, those adder units U at the edges of modified multiplier circuit90, and that have no aligned adder unit U in a more significant bit position and therefore receive no previous sum bit, simply receive a “0” at their addend (B) input; alternatively, full adder102need not be provided in those adder units U. Those adder units U in the least significant (bottom) row of modified multiplier circuit90produce a result bit R at their sum output. According to the data flow arrangement ofFIGS. 6aand6b, some of these sum results will be ignored, because the exclusive-ORs along those columns are invalid.

According to the preferred embodiment of the invention, therefore, an efficient architecture for convolutional coding is provided. The architecture is implemented by way of a simple modification of the known parallel multiplier, with the modification merely involving eliminating carry-in and carry-out bits in the parallel adders in the multiplier. The convolutional code can be readily modified, for example by writing new coefficients Giinto registers94. Additionally, the code rate can be modified by varying the number of coefficient sets applied to modified multiplier90. These and other advantages will be apparent to those skilled in the art having reference to this specification.

Referring now toFIG. 10, another application of the modified multiplier circuit according to the present invention, directed to the generation of a scrambling code for wireless communications, will now be described. Referring back toFIG. 5, encode and modulate function54includes scrambling code generator75, which generates in-phase and quadrature components Ic(k), Qc(k), respectively, of the scrambling code that is applied to the modulated datastream. As shown inFIG. 10, scrambling code generator75generates scrambling code components Ic(k), Qc(k) which are applied to in-phase and quadrature data components I(k), Q(k), respectively, by bit modulator function72.

FIG. 10illustrates the data flow of bit modulator function72, according to a conventional modulation approach. The operations shown inFIG. 10for bit modulator function72are conventionally carried out by digital signal processing operations, such as may be carried out by a high performance digital signal processor (DSP), such as the TMS 320c5x or 320c6x families of digital signal processors available from Texas Instruments Incorporated.

In the operation of bit modulator function72, the spread data stream is represented inFIG. 10as having an-phase component I(k) and a quadrature component Q(k). Multiplier123effectively shifts each digital word in the sequence of quadrature component Q(k) by 90° (indicated by multiplication by square root of −1, represented in the art as imaginary operator “j”). Adder122then combines this phase-shifted quadrature component jQ(k) with its corresponding digital word in the sequence of in-phase component I(k). The combined I and Q components from adder1222are then scrambled by a scrambling code c(k) prior to its transmission.

As described above, and as conventional in the cellular telephone art, the scrambling code generated by scrambling code generator75is cell-specific in the downlink case, in that all transmissions from a central office that take place in the same physical cell use the same scrambling code. The scrambling code thus allows each remote system element to resolve incoming communications for its cell from those that may be received from other cells. Conversely, in the uplink case, the scrambling code is user-specific, dedicated to the particular transmitting wireless unit. Typically, the scrambling code is a “long” code, for example 4096 chips in length. According to this embodiment of the invention, scrambling code generator produces both an in-phase component Ic(k) and a quadrature component Qc(k) The construction of scrambling code generator75according to this embodiment of the invention will be described in further detail below.

Similarly as for the data bitstream, in-phase scrambling code component Ic(k) is added, by adder124, with quadrature scrambling code component Qc(k) after application of a 90° phase-shift by multiplier125. The combined in-phase and quadrature data signal from adder2is mixed with the combined in-phase and quadrature scrambling code signal from adder124, at mixer126. In the digital context, mixer126is a complex multiplier function or circuit. Signal Y(k), at the output of mixer126, is the complex modulated output of these operations, and includes in-phase and quadrature components. These components are then filtered and used to modulate in-phase (cosine wave) and quadrature (sine wave) analog signals at the appropriate carrier frequency.

Other bit modulation techniques may alternatively be used, in place of bit modulator function74. An example of such another bit modulation technique is described in copending application Ser. No. 10/135,658, filed Apr. 29, 2002, entitled “Multiple Bit Complex Bit Modulation”, commonly assigned with this application to Texas Instruments Incorporated and incorporated herein by this reference. According to this alternative technique, the bit modulator architecture corresponds to a split adder that performs a Gray Code addition of corresponding bits of the in-phase and quadrature data components with corresponding bits of the in-phase and quadrature scrambling code components. The result is a combined in-phase bit and a combined quadrature bit for each bit position in the datastream. The split adder operation inserts a −45° phase shift into the sum, as compared to the conventional mixer, and a reduction in amplitude by a factor of 1/√{square root over (2)}. However, the phase shift is not relevant to the transmission, and the attenuation can be readily compensated, if desired. In this alternative bit modulation approach, the Gray Code addition takes the place of a complex multiplication, thus saving significant processing capacity and reducing circuit complexity.

Referring now toFIG. 11, the construction of scrambling code generator75according to this embodiment of the invention will now be described in detail. The function of scrambling code generator75is to produce a scrambling code in the same conventional way, from a data flow standpoint, as that shown inFIG. 2and discussed above in the Background of the Invention. According to this embodiment of the invention, however, this code generation is performed using modified multiplier circuit90′, and thus attains important improvement in chip area efficiency and in performance.

Modified multiplier circuit90′ in scrambling code generator75according to this embodiment of the invention is constructed similarly as described above for modified multiplier circuit90of convolutional coding function60. As shown inFIG. 11, modified multiplier circuit90′ has a control input coupled to line MPY/ENCODE_, which controls the selection of either a conventional multiplier mode in which carries are used, or a coding mode as described above in which each adder is blocked from considering carries, and thus executes exclusive-OR functions as required in the code generating algorithm of scrambling code generator75. Because of the difference in function, however, it is contemplated that the dimensions of modified multiplier circuit90′ will differ from those in convolutional coding function60. An example of the size of modified multiplier circuit90′ in scrambling code generator75is contemplated to be sixteen rows by thirty-two columns, at a minimum.

As shown inFIG. 11, upper shift register132U and lower shift register132L provide inputs to modified multiplier circuit90′. Shift registers132each correspond to a sequence of shift register stages, corresponding to delay stages D described above, with an output produced from the input to the first stage, and from the output of each of the other stages. Referring toFIG. 11in combination withFIG. 2, upper shift register132U of scrambling code generator75corresponds to delay stage sequence15I of scrambling code generator10ofFIG. 2, and lower shift register132L corresponds to delay stage sequence15Q.

Modified multiplier circuit90′ performs the feedback and feedforward exclusive-OR operations used in generating the scrambling code according to this embodiment of the invention. These operations performed by modified multiplier circuit90′ correspond to exclusive-OR functions12,14,16,18in scrambling code generator10ofFIG. 2. According to this implementation, a single modified multiplier circuit90′ is provided that will serially perform these four operations. Four sets of coefficients for controlling the selection of the shift register stages to be exclusive-ORed, and the routing of the four results, must therefore be controlled to use this single modified multiplier circuit90′, as will be described below. Alternatively, however, it is contemplated that multiple modified multiplier circuits90′ may be provided to perform these operations in parallel, rather than in sequence, to attain higher performance but at a cost of additional circuitry and chip area. It is contemplated that those skilled in the art having reference to this specification will be readily able to optimize the selection of the number of modified multiplier circuits90′ for each particular application.

The use of modified multiplier circuit90′ to effect the feedback exclusive-OR functions14,18ofFIG. 2is limited, in that output bits are not reused in the same cycle within the multiplier array and therefore require multiple cycles as they are calculated to produce the full result. If this constraint cannot be met for the feedback operations, one may use a modified multiplier architecture according to this invention for the feed-forward direction only, with conventional combinatorial logic used for the feedback operations.

Returning toFIG. 11, four coefficient registers134are provided for storing the coefficients selecting the shift register stages to be exclusive-ORed in each operation. Coefficient register134UFF stores the feed-forward coefficients operating upon the contents of upper shift register132U, coefficient register134UFB stores the feedback coefficients operating upon the contents of upper shift register132U; similarly, coefficient registers134LFF,134LFB store the feed-forward and feedback coefficients, respectively, that operate upon the contents of lower shift register132L. In this example, the control of the application of the sets of coefficients is effected by multiplexer136, which is controlled by a control signal on lines SEL from timing circuit139according to the timing of the scrambling code generation.

As shown inFIG. 2, four result bits are generated by exclusive-OR functions12,14,16,18in the producing of a scrambling code. The four operations of modified multiplier circuit90′ similarly produce four result bits, one for each of the feed-forward and feedback operations for each of upper and lower shift registers132U,132L. Demultiplexer136forwards these four results to the appropriate destination for the operation, under the control of timing circuit139via control lines SEL. In this example, which corresponds to the example ofFIG. 2, the results of the feed-forward exclusive-ORs of the contents of each of upper and lower shift registers132U,132L are applied to corresponding inputs of exclusive-OR function140Q to produce quadrature code component Qc(k). The result of the feedback exclusive-OR of the contents of upper shift register132U is applied to the input of upper shift register132U, and the result of the feedback exclusive-OR of lower shift register is applied to the input of lower shift register132L. In-phase scrambling code component Ic(k) is produced, as before, by the exclusive-OR of the last stages of upper and lower shift registers132U,132L. It is contemplated that each of the inputs to exclusive-OR functions140I,140Q, and perhaps also to upper and lower shift registers132U,132L, are latched, considering that the results of the exclusive-OR operations performed by modified multiplier circuitry90′ are obtained sequentially rather than simultaneously.

In an example of the operation of scrambling code generator75, the states of the last stages of upper and lower shift registers132U,132L are applied to exclusive-OR function1401, to produce the current in-phase scrambling code component Ic(k). This operation may take place at any time during the current sequence of operations, prior to the shifting of the contents of shift registers132. The sequence of exclusive-OR operations begins with the presentation of the contents of upper shift register132U to modified multiplier circuit90′. Under the control of timing circuit139, multiplexer136applies the contents of register134UFF to modified multiplier circuit90′, and demultiplexer138couples the output of modified multiplier circuit90′ to an input of exclusive-OR function140Q. Modified multiplier circuit90′ performs the selected exclusive-ORs of the contents of upper shift register132U, with the result forwarded to an input of exclusive-OR function140Q.

Next, feedback coefficients from register134UFB are presented to modified multiplier circuit90′ by multiplexer136; demultiplexer138also couples the output of modified multiplier circuit90′ to the input of the first stage of upper shift register132U. The contents of upper shift register132U remain applied to modified multiplier circuit90′. Modified multiplier circuit90′ generates the result bit according to the exclusive-OR functions indicated by the coefficients in register134UFB, and applies this result to upper shift register132U.

Operations using the contents of lower shift register132L are now performed. Multiplexer136selects register134LFF for application to modified multiplier circuit90′, and demultiplexer138couples the output of modified multiplier circuit90′ to the corresponding input of exclusive-OR function140Q. Modified multiplier circuit90′ performs the exclusive-OR operation indicated by the coefficients of register134LFF, to generate the corresponding input to the generation of quadrature scrambling code component Qc(k). Following this operation, multiplexer136selects register134LFB for application to modified multiplier circuit90′, and demultiplexer138couples the output of modified multiplier circuit90′ to the input of the first stage of lower shift register132L. The contents of lower shift register132L remain applied to modified multiplier circuit90′, which then generates the next bit in the sequence from the exclusive-OR operation indicated by register134LFB.

Once all four of the operations of modified multiplier circuit90′ are complete, exclusive-OR functions140I,140Q can then produce and forward the current values of the in-phase and quadrature scrambling code components Ic(k), Qc(k), for application to the current data components I(k), Q(k) by bit modulator circuitry72(FIG. 10). Execution of the operations can then be repeated for the next set of values.

Referring back toFIG. 5, the outputs of bit modulator circuitry72in each of encode and modulate functions55are then forwarded for transmission, for example as a single multiplexed datastream after multiplexing by multiplexer74.

According to this embodiment of the invention, therefore, the modified multiplier architecture can be used in the exclusive-OR functions applied in the generation of conventional scrambling codes, such as those cell-specific codes used in modern wireless voice and data communications. This architecture provides the important benefits of great flexibility in the selection of the particular code, for example simply by reloading the registers storing the sets of coefficients, while providing efficient circuitry for carrying out the exclusive-OR operations, both in performance and in chip area. In addition, the modified multiplier architecture can be implemented in such a way that the same circuit can be used, in one mode, to execute a conventional digital multiplication, and in another mode to perform the exclusive-OR operations used in the encoding and code generation operations. This dual function provides the additional advantage of further chip efficiency, in that the same relatively large logic circuit can be used for multiple functions.

While the present invention has been described according to its preferred embodiments, it is of course contemplated that modifications of, and alternatives to, these embodiments, such modifications and alternatives obtaining the advantages and benefits of this invention, will be apparent to those of ordinary skill in the art having reference to this specification and its drawings. It is contemplated that such modifications and alternatives are within the scope of this invention as subsequently claimed herein.