Data communications system and hybrid time-code multiplexing method

[0002] This application is a continuation-in-part of U.S. patent application Ser. No. 08/909,266, filed Aug. 11, 1997, which is hereby incorporated by reference.

[0003] The present invention relates to digital data communications, and more particularly, to systems and methods for accommodating terminals of different throughput capabilities.

[0004] Current systems use a variety of schemes for encoding and multiplexing digital data streams for communications between terminals including frequency division multiple access (FDMA), time division multiple access (TDMA), and code division multiple access (CDMA). Some systems have also been devised which use various combinations of FDMA, TDMA, and CDMA.

[0005] One problem with known prior art systems, however, is that they do not readily accommodate terminals having different throughput capabilities in an integrated digital network. In particular, data communications systems using TDMA and satellite relay typically expect or require that all terminals interconnected in the network have similar throughput capabilities and use a common modulation. In addition, these conventional systems cannot accommodate terminals that transmit at significantly different burst rates, and thus require all the terminals to use antennas of approximately the same diameter.

[0006] Conventional communications systems using FDMA and satellite relay, or any other form of radio relay, can accommodate multiple isolated point-to-point channels of differing throughput in configurations normally referred to as stove-pipe architectures, where integrated digital networking is not practically feasible.

[0007] Conventional TDMA systems that use variable rate burst modems can accommodate channels of differing throughputs. These systems, however, inefficiently use equipment at sites with relatively large antenna diameters by requiring a large number of modems to handle communications with smaller terminals.

[0008] Conventional satellite, or any other form of radio relay, systems using CDMA typically cannot handle reception of signals at varying power levels from different terminals, a problem normally referred as the “near-far problem.”

[0009] Therefore, there exists a need to overcome the above described problems of the prior art and thus permit a system that accommodates terminals of different throughput capabilities in an integrated digital network.

[0010] Accordingly, the present invention is directed to methods and systems for communicating between nodes that substantially obviates the problems of prior art communications systems.

[0011] In accordance with the purposes of the invention, as embodied and broadly described herein, the invention comprises a method for communicating over a network having a plurality of nodes. The method comprises the steps of generating a plurality of codes each being orthogonal to and a circular shifted version of every other one of the codes, assigning a subset of the codes to a first node, and transmitting information from the first node to a second node using the subset of codes.

[0012] In another aspect, the invention comprises a node for communicating over a network including means for storing a subset of codes, and means for transmitting information from a first node to a second node using the subset of codes. The subset of codes is derived from a set of codes and each code in the set of codes is orthogonal to and a circular shift of every other code in the set of codes.

[0013] In still another aspect, the invention comprises methods for modulating end-user information in symbols wherein each symbol is capable of carrying multiple bits of information.

[0014] In still another aspect, the invention comprises systems and methods for communicating between nodes using circulant-unitary matrices.

[0015] This summary of the invention and the following detailed description should not restrict the scope of the claimed invention. Both provide examples and explanations to enable others to practice the invention. The accompanying drawings, which form part of the description for carrying out a best mode of the invention, show several embodiments of the invention, and together with the description, explain the principles of the invention.

[0016] FIG. 1 is a diagram illustrating a digital network, consistent with the present invention, including a plurality of terminals communicating via a satellite relay;

[0017] FIG. 2 is a diagram illustrating a digital network, consistent with the present invention, including a plurality of terminals communicating via terrestrial radio relay;

[0018] FIG. 3 is a diagram illustrating a container for carrying information, consistent with the present invention;

[0019] FIG. 4 is a diagram illustrating a method for generating containers from information packets, consistent with the present invention;

[0020] FIG. 5 is a graphical representation of 45 degree offset Binary Phase Shift Key (BPSK), or 2^m-ary Quadrature Amplitude Modulation (QAM) for m=1, consistent with the present invention;

[0021] FIG. 6 is a graphical representation of 2^m-ary QAM for m=2, consistent with the present invention;

[0022] FIG. 7 is a graphical representation of 2^m-ary QAM for m=3, consistent with the present invention;

[0023] FIG. 8 is a graphical representation of the upper right hand quadrant of 2^m-ary QAM for m=4, consistent with the present invention;

[0024] FIG. 9 is a graphical representation of the upper right hand quadrant of 2^m-ary QAM for m=5, consistent with the present invention;

[0025] FIG. 10 is a graphical representation of the upper right hand quadrant of 2^m-ary QAM for m=6, consistent with the present invention;

[0026] FIG. 11 is a graphical representation of the upper right hand quadrant of 2^m-ary QAM for m=7, consistent with the present invention;

[0027] FIG. 12 is a graphical representation of the upper right hand quadrant of 2^m-ary QAM for m=8, consistent with the present invention;

[0028] FIG. 13 is an illustration, consistent with the present invention, of using Synchronization-blocks and Data-blocks in a time-division duplex transmission scheme;

[0029] FIG. 14 is an illustration of container structure for use in a terminal assigned 8 shifts of the code, consistent with the present invention;

[0030] FIG. 15 illustrates code assignments to terminals and their respective guard bands, consistent with the present invention;

[0031] FIG. 16 illustrates a method, consistent with the invention, for subtracting M-sequences in order to generate a ternary sequence;

[0032] FIG. 17 illustrates steps for generating a circulant-unitary matrix, consistent with the present invention;

[0033] FIG. 18 illustrates a circularly padded code, consistent with the present invention;

[0034] FIG. 19 illustrates steps for converting a signal from baseband to intermediate frequency, consistent with the present invention;

[0035] FIG. 20 provides an illustration, consistent with the invention, of correlating received signals with match waveforms; and

[0036] FIG. 21 illustrates a rotating correlator, consistent with the present invention.

[0037] Reference will now be made in detail to embodiments of the invention, examples of which are illustrated in the accompanying drawings. Wherever possible, the same reference numbers will be used throughout the drawings to refer to the same or like parts.

[0038] FIG. 1 is a diagram of a digital network 100, including terminals 21-26 with different throughput capabilities that communicate with each other through a HUB 31. In one embodiment, HUB 31 includes a relay satellite. In this embodiment, terminals 21-26 are satellite terminals and typically include, for example, an antenna, a power amplifier, and a modem.

[0039] FIG. 2 is a diagram of a digital network of another embodiment in which the HUB 31 includes an antenna for a terrestrial network operating over radio frequency (RF). In this embodiment, terminals 21-26 are RF terminals and typically include, for example, an antenna, a power amplifier and a modem. Terminals 21-26 are located at arbitrary distances from the HUB 31, and have line-of-sight (LOS) view of the HUB 31, but do not necessarily have LOS view of each other. In other embodiments, the network may be a mobile packet radio network or any wireless or wireline network with shared channels.

[0040] In accordance with one aspect of the invention, the networks of FIGS. 1 and 2 use Direct Sequence Spread Spectrum (DSSS) encoding techniques in a particular manner so as to enable flexible allocation of channel capability or bandwidth. As is understood in the art, in DSSS, a pseudo-noise (P/N) code comprising a predefined number of chips, such as 512 chips, for example, can be used to spread an information symbol for transmission over the network. A receiver then detects the code using a correlator or matched filter to despread and recover the original information symbol.

[0041] Rather than using a plurality of different and non-orthogonal codes, a network consistent with the present invention uses a single or common code and implements multiple access by using cyclic rotations (sometimes referred to as cyclic shifts) of the code, which are orthogonal with one another. This code will hereinafter be referred to as a “cyclically orthogonal code”. Each cyclic shift of the code by one chip is considered a separate phase. For a code with 512 chips, for example, there may be up to 512 phases or possible distinguishable rotations of the code, available for use in the system. In one embodiment, the receivers use a rotating correlator to search through or examine relevant phases of the cyclically orthogonal code sequence during each symbol interval. An advantage of this scheme is that a single rotating correlator can detect the data in several channels, transmitted from different terminals. Thus, multiple modems, one for each channel, may be avoided. In another embodiment, a technique using Fast Fourier Transforms (FFTs) is used to despread and recover the received information symbols by examining all relevant phases of the cyclically orthogonal code. This technique will be described in greater detail later.

[0042] Depending on the terminals' capabilities and needs, each terminal is allocated one or more consecutive cyclic shifts of this code. For example, one terminal may require 8 consecutive shifts of the code, while other terminals may require less or more than this amount. Thus, through this mechanism, the terminals can achieve different throughputs depending on their needs and capabilities by assigning to them a different number of consecutive shifts of the code.

[0043] In addition, by assigning to a terminal a subset of the total number of shifts, a coding gain of 10 log₁₀[N/A] dB can be achieved where N is the number of chips in the cyclically orthogonal code sequence and A is the number of code shifts assigned to the terminal. This coding gain improves the Symbol Energy to Noise Density Ratio (E_s/N_o). Thus, if a terminal uses a smaller number of shifts of the code, the E_s/N_ocan be improved. As such, a terminal can achieve an improved Bit Error Rate (BER) while maintaining the same throughput data rate, or achieve a higher throughput data rate (assigning a greater number of bits to each symbol) while maintaining the BER.

[0044] Preferably, the terminals 21-26 coordinate their transmissions such that their RF signals (which are superimposed because they occupy the same portion of the frequency spectrum at the same time) arrive with near time alignment at the HUB 31.

[0045] In an embodiment, containers are used for transmitting information. FIG. 3 illustrates a block diagram of a container 300. The container 300 includes a header 302 and a payload 304. The header 302 preferably consists of 96 symbols and the payload 304 preferably consists of 672 symbols. The header 302 is preferably further divided into two areas: a synchronization and channel characterization (SCC) area 310 of 64 symbols and a segmentation and re-assembly (SAR) area 312 of 32 symbols. The information in the SAR area 312 is used to reassemble the packets at the receiving end. SAR information preferably includes a packet identification, a container sequence number, the number of Quadrature Amplitude Modulation (QAM) cells in the packet, and the modulation level (m). The use of QAM cells and their modulation level will be discussed in greater detail later.

[0046] The SCC information preferably contains, among other things, a “unique word” consisting of a sequence of symbols intended to help the receiver identify the time instant and code-phase associated with the beginning of the container, a sequence of symbols intended to facilitate measurement of received signal and noise power levels, and a sequence of symbols intended to facilitate measurement of the channel impulse response.

[0047] FIG. 4 provides an illustration of how information packets at a terminal are packaged into containers for transmission and how they are retrieved from the containers by a receiver. As shown in the figure, a terminal, of a preferred embodiment, includes a Forward Error Correction (FEC) encoder 406, a quadrature amplitude modulation (QAM) encoder 410 and a container assembler 414. When a terminal has a packet of information 402 to transmit, it first breaks the packet into 64 byte info-cells 404. The FEC encoder 406 then encodes the info-cells, into 80 byte turbo-cells 408. In a preferred embodiment, FEC encoder 406 is a turbo encoder. In another embodiment, encoder 406 is a Reed-Solomon encoder.

[0048] The QAM encoder 410 then modulates the turbo-cells 408 by compressing each turbo-cell into a QAM cell 412 of 2^m-ary QAM symbols, each symbol carrying m bits of FEC encoded information. The QAM encoder 410 preferably uses the same modulation level, that is the same value of m, for all turbo-cells associated with a given information packet. In order to ensure that a QAM cell has an integer number of symbols, it is necessary, for certain values of m, to pad the bit sequence in the turbo-cell. FIGS. 5-12 illustrate 2^m-ary QAM constellations for m=1-8. In FIGS. 8-12, only the upper right hand quadrant of the constellation is shown, as the other three quadrants are merely mirror images of this quadrant. As illustrated in FIGS. 7, 9, and 11, these 2^m-ary QAM constellations are preferably obtained from punctured N²-ary QAM constellations.

[0049] The container assembler 414 (FIG. 4) then packages the QAM cells into the payload of a container 416. Payloads are preferably 672 symbols long, and exactly “m” QAM-cells are concatenated, scrambled, and loaded into the payload. A header is then assembled for the payload, preferably containing, along with other information, information on the modulation level used for encoding the payload. Unlike the payload, the header is preferably modulated using 45 degree offset Binary Phase Shift Key (BPSK).

[0050] The terminal then transmits the container over a channel to a receiver where the information is extracted using the same steps, but in reverse order, as shown in FIG. 4. Prior to transmission over the channel, a precoder (not shown) may be used to minimize the channel's effects on the transmitted signal.

[0051] At the receiver, after the containers are separated from each other, or alternatively, after the containers received from each transmitter are grouped together, an equalizer (not shown) may be used to further reduce the channel's effects on the transmitted signal.

[0052] The receiver preferably processes containers independently from each other. The containers preferably only carry an integer number of cells. Containers originating from a single information packet are preferably transmitted in sequence to simplify reassembly at the receiver.

[0053] FIG. 13 illustrates a transmission scheme of an embodiment in which transmission between the terminals 21-26 and HUB 31 is time-division-duplex alternating between terminals 21-26 transmitting to the HUB 31 and the HUB 31 transmitting to the terminals 21-26. In another embodiment, transmission is frequency-division-duplex.

[0054] As shown in FIG. 13, information is preferably transmitted over the channel in frames 1302, and 8 frames 1302 comprise a superframe 1304. Each frame 1302 consists of one synchronization block (S-block) 1306 and 24 data blocks (D-blocks) 1308. In this embodiment, the S-block and 12 of the 24 D-blocks are used for transmission from the HUB, while the remaining 12 D-blocks are used for transmission from the terminals. As will be described in greater detail later, S-blocks are used for transmitting synchronization and frame number information, while D-blocks are used for transmitting containers. Preferably, each block is 24 milliseconds, each frame is 600 milliseconds, and each superframe is 4800 milliseconds in length. As will be obvious to one of skill in the art, the time lengths of these structures is not material to the invention, and different time lengths may be used without altering the scope of the invention. In addition, although FIG. 13 shows a time-division duplex implementation, as will be obvious to one of skill in the art, other embodiments may be used such as a frequency-division duplex implementation.

[0055] As previously indicated, a container 300 (FIG. 3) preferably includes both a header 302 and a payload 304, where the header 302 comprises 96 header symbols modulated with 45 degree offset BPSK and the payload comprises 672 info-symbols modulated with 2^m-ary QAM. Collectively, the header-symbols and info-symbols may be referred to as data-symbols. The modulation level is preferably the same for all info-symbols of all payloads of an information packet, but may be different for payloads of different information packets.

[0056] FIG. 14 illustrates a preferred container structure for a terminal that is assigned 8 consecutive shifts of a cyclically-orthogonal code having 512 chips. In this illustration, the terminal transmits a container 300 using the 12 D-blocks of a frame allocated for transmission. In this illustration, containers 300 are transmitted using the above described D-blocks 1308. As such, each 24 millisecond time interval 1404, is preferably a D-block 1308. As shown in FIG. 14, 8 symbols 1408 per assigned shift are preferably transmitted per 24 millisecond time interval 1404. Thus, as there are 8 assigned consecutive shifts 1406, the terminal of this illustration transmits 8*8=64 (# of assigned code shifts * # symbols per assigned shift per 24 millisecond interval) symbols per 24 millisecond D-block. Accordingly, the terminal of this embodiment transmits 768 data-symbols, including 672 info-symbols plus 96 header-symbols per container. Thus, in this illustration, 768÷64=12 D-blocks are used to transmit each container.

[0057] As will be discussed later, each circular shift of the cyclically-orthogonal code is preferably circularly padded by 32 chips at the beginning and 32 chips at the end to create a code referred to as a circularly padded code 1410. These codes 1410 are then used to spread each symbol 1408, as shown in FIG. 14. As such, in this example, each symbol is spread by a 576 chip code, and a symbol is transmitted over 3 milliseconds. Accordingly, in this example, the chip rate is 192 Kchips/second.

[0058] As previously indicated, the payload is preferably modulated using 2^m-ary QAM constellations that are obtained from N²-ary QAM constellations. When m is odd, these 2^m-ary QAM constellations are obtained by puncturing an N²-ary QAM constellation. The same level of modulation (m) is preferably used for modulating all symbols in the payload. It is possible, however, to modulate the payloads of different containers with different levels of modulation. The header, however, is preferably modulated using 45 degree offset BPSK.

[0059] The loading of data symbols and QAM cells into containers is illustrated in the table below. Padding (e.g., for m=3,6, and 7) is used as necessary within the QAM cell and within the payload.

[0060] The payload of each container carries “m” QAM cells, with the exception of the payload of the last container that may carry fewer than m QAM cells. The actual number of QAM cells contained in the last container depends on the length of the packet and on the selected modulation level. The modulation level is preferably kept constant for all payloads originating from a single information packet. The modulation level may vary from packet to packet and is preferably selected as a function of a target bit error rate (BER), or Quality of Service (QOS), for the packet and an available (SNR). As such, it is possible to independently select the modulation level m to be used with a particular packet or channel. In addition to selecting the modulation level m based on the BER or QOS for the information and the available SNR, a power level for transmitting the packet may also be determined based on this information.

[0061] The network preferably synchronizes terminals 21-26 to the HUB 31 by frequency locking a local reference clock at each terminal to a master reference clock at the HUB 31. Frequency locking is performed during terminal initialization, maintained during steady-state operation, and achieved through an over-the-air phase-locked-loop (PLL). Phase error tracking information used by this PLL may be derived from differences between a locally generated clock and a received signal.

[0062] As previously indicated, the network preferably uses two types of blocks: synchronization blocks (S-blocks) and data blocks (D-blocks), as shown in FIG. 13. S-blocks are transmitted by the HUB 31 and are used by the terminals 21-26 for synchronization. S-blocks are preferably sent in a manner such that all terminals, regardless of distance to the HUB 31, may reliably extract the following information: the HUB's clock frequency, carrier phase offset, the start of a frame, and the frame number (within a super frame).

[0063] In a preferred embodiment, a fixed number of consecutive shifts of the code are assigned to a particular terminal. Although synchronization is used so that transmissions from different terminals arrive at the HUB at approximately the same time, complete synchronization may not be possible. Thus, a guard band is established between each set of consecutive shifts of codes assigned to a terminal, such as is illustrated in FIG. 15. A guard band is a group of unassigned consecutive shifts of the code 1500.

[0064] As illustrated in FIG. 15, 8 consecutive shifts of the code 1502 may be assigned to terminal-1 with 8 guard codes 1500 on each side. In addition, 16 consecutive codes 1504 may be assigned to terminal-2, also with 8 guard codes 1500 on each side. Also, 32 consecutive codes 1506 may be assigned terminal-3, with 8 guard codes 1500 on each side. Thus, if for example, there are 512 codes, each terminal in the system can be assigned a particular group of consecutive codes out of these 512 codes depending on its needs with two unassigned groups of 8 guard codes (16 guard codes altogether) between one assigned group of codes and the next assigned group of codes.

[0065] The number of guard codes is preferably determined according to the relative synchronization accuracy. For example, one guard code can be assigned to terminals synchronized within +/− one-half chip interval and transmitting simultaneously, two guard codes may be assigned to terminals synchronized within +/− one chip interval, and so on.

[0066] As will be understood by one of skill in the art, the above guard codes will not be enough by themselves to eliminate partial cross-correlations caused by misalignments among the received signals and/or between these signals and timing events derived from a local reference clock. These misalignments will generally manifest themselves as a combination of an integer number chip times plus a fraction of a chip time. In other direct sequence spread spectrum (DSSS)-based communication systems, such integer and fractional chip-time misalignments result in undesirable cross-correlations and mutual interference between signals from multiple transmitters. These undesirable cross-correlations and mutual interference can be particularly troublesome when the transmitted signals are received with different power levels. Such undesirable cross-correlations and mutual interference is normally referred as the near-far effect and, to help manage this effect, other DSSS-based communications systems commonly incorporate costly interference-reduction methods such as transmitter power control. However, as will be described later, in an embodiment of the invention the codes are circularly padded in a manner that maintains the orthogonality of the codes despite these misalignments. As such, the present invention practically eliminates the undesirable cross-correlations, the mutual interferences, and the near far effect along with the need for costly interference-reduction methods such as transmitter power control.

[0067] The network preferably uses a technique that combines the advantages of DSSS techniques and time division multiple access (TDMA) techniques for transmitting containers over a channel.

[0068] In an embodiment, the network uses DSSS techniques with orthogonal codes that are robust to arbitrary time offsets. These codes are preferably derived from a family of codes obtained from a base code (of arbitrary length N) and circularly-shifted versions of it. Any consecutive number of these codes (up to a maximum of N) can be assigned to any terminal in the network.

[0069] In an embodiment, QAM symbols are spread with orthogonal codes. If the terminal is assigned more than one code, the resulting spread symbols corresponding to the same symbol time are then summed. This allows transforming any spread spectrum processing gain directly into Es/No gain and enabling, therefore, transmission of multiple bits per symbol with multiple level modulation (e.g., 2^m-ary QAM).

[0070] In one embodiment, a ternary sequence is used to spread the signal. The ternary sequence is preferably determined by first selecting an M-sequence (maximal-length), which may be generated by a linear feedback shift register that generates N=2^M−1 binary elements before the sequence repeats. This M-sequence can be represented as q₁,q₂,q₃, . . . , q_N. Then a circular shift of this original M-sequence is determined. This circular shift can be represented as, for example, q_kq_k+1,q_k+2, . . . ,q_N,q₁,q₂, . . . q_k−1. Because these are binary M-sequences, $\sum _{n=1}^N{q}_n{q}_{n\oplus k-1}=\{\begin{array}{cc}N& k=1\\ -1& k\ne 1\end{array},\mathrm{where}{q}_n=\text{+/-1}$

[0071] Thus, let Q_k(n)=q_n⊕k−1, where Q_k(n) is the original code if k=1 and Q_k(n) is a circular shift of the original code if 1<k≦N.

[0072] Next, one shift of a code is subtracted from another shift of a code. The resulting code is therefore $R_k\left(n\right)=Q_k\left(n\right)-Q_{k\oplus L}\left(n\right)=\{\begin{array}{c}+2\\ 0\\ -2\end{array}$

[0073] where L=(N−1)/2. Thus, for each k (where k=1,2, . . . , L), R_k(n) is a sequence of N=2^M−1 ternary elements, and for each k=1,2, . . . L−1 the sequence R_k+1,(n) is a circular shift of R_k(n). Every one of these L sequences is orthogonal to every other one of these L sequences.

[0074] FIG. 16 provides an illustration of a process, consistent with the invention, for performing this subtraction. As shown, the L^thshift of the original sequence, q_L+1,q_L+2, . . . q_L, 1604 is subtracted from the original sequence, q₁,q₂,q₃, . . . ,q_N1602 to produce a sequence R₁(n), where R₁(n) is a ternary sequence with elements having a value of either +2,0, or −2. The (L+1)^thshift of the original sequence, q_L+2,q_L+3, . . . ,q_L+1, 1608 is then subtracted from first shift of the original sequence, q₂,q₃, . . . ,q₁, 1606 to produce a ternary sequence R₂(n). This method is then continued to yield the L=(N−1)/2 ternary sequences.

[0075] In another embodiment, the network uses rows of a circulant-unitary (CU) matrix for communications. CU matrices are useful in that each row is not only a circular shift of every other row, but is also orthogonal to every other row. In order for a matrix, C, to be a CU matrix it must possess two properties:

[0076] 1. C is a circulant. That is, C satisfies the following: $C=\left[\begin{array}{ccccc}{c}_1& c_2& c_3& \dots & c_N\\ c_N& c_1& c_2& \dots & c_{N-1}\\ c_{N-1}& c_N& c_1& \dots & c_{N-2}\\ ⋮& ⋮& ⋮& \dots & ⋮\\ c_2& c_3& c_4& \dots & c_1\end{array}\right]$

[0077] 2. C is unitary. For C to be unitary it is necessary that: ${\mathrm{CC}}^H=I=\left[\begin{array}{ccccc}1& 0& 0& \dots & 0\\ 0& 1& 0& ⋮& ⋮\\ 0& 0& ⋰& 0& 0\\ ⋮& ⋮& 0& 1& 0\\ 0& \dots & 0& 0& 1\end{array}\right]$

[0078] where C^His the conjugate transpose of C, and I is the identity matrix. Thus, if C satisfies both requirements, it is a CU matrix.

[0079] In order to generate a CU matrix, it is first necessary to recognize that $\tilde{C}={\mathrm{ZCZ}}^H=\left[\begin{array}{ccccc}{\tilde{c}}_1& 0& 0& \dots & 0\\ 0& {\tilde{c}}_2& 0& \dots & 0\\ 0& 0& {\tilde{c}}_3& \dots & 0\\ ⋮& ⋮& ⋮& ⋰& 0\\ 0& 0& 0& \dots & {\tilde{c}}_N\end{array}\right]$

[0080] where Z is a Discrete Fourier Transform (DFT) matrix and Z^His its conjugate transpose. Thus, because Z^HZ=I and ZZ^H=I any circulant matrix C can be expressed as

[0081] C=Z^H{tilde over (C)}Z

[0082] and

[0083] CC^H=Z^H{tilde over (C)}ZZ^H{tilde over (C)}^HZ=Z^H{tilde over (CC)}^HZ

[0084] where, C^H=(Z^H{tilde over (C)}Z)^H=Z^H{tilde over (C)}^HZ. Thus, if and only if

[0085] {tilde over (CC)}^H=I

[0086] will the circulant matrix C be unitary.

[0087] Thus, the following must be satisfied for C to be a CU matrix: $\tilde{C}{\tilde{C}}^H=I=\left[\begin{array}{cccc}{\tilde{c}}_1& 0& \dots & 0\\ 0& {\tilde{c}}_2& \dots & ⋮\\ ⋮& ⋮& ⋰& 0\\ 0& \dots & 0& {\tilde{c}}_N\end{array}\right]\left[\begin{array}{cccc}{\tilde{c}}_1^{*}& 0& \dots & 0\\ 0& {\tilde{c}}_2^{*}& \dots & ⋮\\ ⋮& ⋮& ⋰& 0\\ 0& \dots & 0& {\tilde{c}}_N^{*}\end{array}\right]=\left[\begin{array}{cccc}1& 0& \dots & 0\\ 0& 1& \dots & ⋮\\ ⋮& ⋮& ⋰& 0\\ 0& \dots & 0& 1\end{array}\right]$

[0088] Therefore, the above will be true if and only if

[0089] {tilde over (c)}_n{tilde over (c)}_n=|{tilde over (c)}_n|²=1

[0090] for n=1,2, . . . , N and this will be true if and only if {tilde over (c)}_n=exp(iθ_n).

[0091] As such, in a preferred embodiment a CU matrix may be determined by the following steps. FIG. 17 provides a flow chart for performing these steps.

[0092] 1. Determining the number of rows desired in the matrix, N. (S1702).

[0093] 2. Choosing a θ_nfor n=1 . . . N. (S1704).

[0094] 3. Calculating {tilde over (c)}_n=exp(iθ_n) for n=1 . . . N. (S1706)

[0095] 4. Forming {tilde over (C)}=diag[{tilde over (c)}₁,{tilde over (c)}₂,{tilde over (c)}₃, . . . {tilde over (c)}_N] (S1708)

[0096] 5. Calculating C=Z^H{tilde over (C)}Z, where C is the desired matrix. (S1710)

[0097] This method yields N sequences each consisting of N elements, such that each of these N sequences is orthogonal to every other one of these N sequences. In a preferred embodiment, N is equal to 512 chips.

[0098] In another embodiment, scaled versions of the rows of a circulant-unitary matrix are used for transmitting the signals.

[0099] As will be familiar to one of skill in the art, the elements of the above described sequences are commonly referred to as chips, and there are other sequence design techniques that can be used for generating the orthogonal codes.

[0100] FIG. 18 provides an illustration of a process for circularly padding the code sequences. After determining the cyclically-orthogonal codes that will be used for spreading the signals, it is preferable to circularly pad the code to improve the code's tolerance for arbitrary time shifts. As shown in FIG. 18, in a preferred embodiment, K chips from the end of the code 1802 are copied and placed at the front of the code 1804 and J chips from the front of the code 1806 are copied and placed at the end 1808. As will be obvious to one of skill in the art, the number of chips padded to the front and end of the code may vary and may be adjusted to fit the needs of the particular implementation. In a preferred embodiment, J and K are both 32 chips.

[0101] By using the aforementioned cyclically orthogonal codes together with the above circular padding, code sequences may be obtained that possess a shift-orthogonality property, as will be presently described, thus achieving a desired system tolerance to time shifts. To understand the shift-orthogonality property, suppose that a_mfor m=1, 2, . . . , N, is one of the family of L≦N cyclically-orthogonal code sequences, and that, prior to its use for symbol spreading and transmission, it has been extended by circular-padding as described above so that a_mis also defined for m=1−K, . . . ,−1, 0 and for m=N+1, N+2, . . . , N+J. Also observe that, for any fixed v=−K, . . . J, the subsequence, a_m+v, for m=1, 2, . . . , N, is one of the family of L≦N cyclically-orthogonal code sequences. Now suppose that another code sequence, b_mfor m=1, 2, . . . , N, in this family is not one of the aforementioned subsequences, a_m+v. Because these sequences are orthogonal, they satisfy the following relationship: $\sum _{m=1}^N{b}_m{a}_{m+v}^{*}=0\mathrm{for}v=-K,\dots ,J.$

[0102] This equation describes a correlation, or matched-filter, operation, and shows that the sequence orthogonality is maintained even over a range of integral time-shifts, vT_c, where T_c, is the chip time.

[0103] In an embodiment, circular padding of cyclically orthogonal sequences is used along with guard codes. Through this technique a number, G, of sequence set pairs may be generated, wherein each sequence set pair consists of a “transmit sequence set” and a “match sequence set.” A “transmit sequence set” consists of P(g) code sequences each consisting of K+N+J chips, where g=1, . . . G. Each match sequence set corresponding to a transmit sequence set consists of K+P(g)+J code sequences each consisting of N chips. The individual elements, or chips, of the various transmit sequence sets can be represented by a_{m+v}(g,p) where g=1,2, . . . G; p=1, . . . ,P(g); m=1,2. . . N; and v=−K, . . . J. The individual elements, or chips, of the various match sequence sets can be represented by b_m(g,q), where g=1, . . . G; q=1−K, . . . ,P(g)+J; and m=1,2. . . N. Furthermore, these G sequence set pairs are preferably designed such that $\sum _{m=1}^N{b}_m\left(g,q\right)a_{m+v}^{*}\left(h,p\right)=0\mathrm{if}g\ne h$

[0104] for p=1,2, . . . ,P(h) and q=1−K, . . . ,P(g)+J and v=−K, . . . ,J while $\sum _{m=1}^N{b}_m\left(g,q\right)a_{m+v}^{*}\left(g,p\right)=\{\begin{array}{ccc}N& \mathrm{if}& q=p+v\\ 0& \mathrm{if}& q\ne p+v\end{array}$

[0105] for p=1,2, . . . ,P(g), q=1−K, . . . ,P(g)+J, and v=−K, . . . ,J. The first of these last two equations expresses the fact that, if g≠h, each sequence from match sequence set g is orthogonal to every subsequence, v, of every sequence, p, of transmit sequence set h. The second of these last two equations expresses the fact that, the q^thsequence of match sequence set g is orthogonal to the v^thsubsequence of the p^thsequence of transmit sequence set g if q≠p+v but is not orthogonal if q=p+v. Together, the properties expressed by these last two equations is called the “shift-orthogonality property.”

[0106] The transmit sequence sets may be composed of longer, or extended, sequences without detracting from the shift orthogonality property. In an embodiment, K=J=8 guard codes are used with cyclically-orthogonal sequences composed of N=512 chips but the transmit sequence sets are generated by circular padding 32 chips at the front and 32 chips at the end of various phases of the cyclically-orthogonal sequence so that each sequence, in each transmit sequence set, is composed of 576 chips. Nonetheless, the resulting sequence set pairs satisfy the aforementioned shift-orthogonality property for K=J=8.

[0107] An embodiment of this invention generates, for g=1,2, . . . , G, transmit sequence sets and corresponding match sequence sets with the aforementioned shift-orthogonality property and assigns, to each of several terminals, one or more of the transmit sequence sets such that no two terminals are assigned the same transmit sequence set. Each such terminal of the embodiment uses its assigned transmit sequence set to spread data symbols and, if the assigned transmit sequence set includes more than one sequence, the spread symbols corresponding to the same symbol time are then summed to create a digital baseband signal. A receiver of the embodiment then uses the match sequence sets corresponding to all assigned transmit sequence sets to recover, or despread, the data symbols by computing all relevant correlations. Because the transmit sequence sets and corresponding match sequence sets satisfy the aforementioned shift-orthogonality property, such correlations will not include any undesirable cross-correlations or mutual interference due to an integral time-shift, or misalignment, vT_c.

[0108] In another embodiment, more than one terminal may be assigned and share the use of one transmit sequence set by using some multiple access scheme, such as TDMA or ALOHA.

[0109] As will be obvious to one of skill in the art, such sequence orthogonality over integral time-shifts is, by itself, inadequate to assure that the corresponding analog waveforms will be orthogonal over time-shifts, τ, which may include both integral and fractional multiples of the chip time, T_c. That waveform orthogonality over time-shifts, τ can practically be achieved is described below.

[0110] FIG. 19 provides an illustration of a process for converting the digital baseband signal to intermediate frequency (IF) prior to transmission over the air. To accomplish this, a terminal uses an upsampling digital filter 1902, a multiplier 1904, a digital-to-analog converter (DAC) 1906, and an analog filter 1908. The upsampling digital filter 1902 first upsamples the arriving symbols, and is preferably a finite impulse response (FIR) lowpass filter whose design characteristics are chosen in part to minimize intersymbol interference. Multiplier 1804 then multiplies the output of the upsampling digital filter 1902 by a complex exponential time sequence exp(i2Πfn).

[0111] DAC 1906 then converts the real part of the output of multiplier 1902 to an analog signal and analog filter 1908 then filters it. Although, the analog filter 1902 may be an infinite impulse response (IIR) filter, preferably it may be modeled as a FIR filter. The resulting IF signal is then upconverted to RF, transmitted over the channel and then converted back to baseband using these same steps, but in reverse order, as the above described conversion from baseband to RF. That is, the received signal is downconverted from RF to IF, filtered by an analog filter, converted to digital by an analog-to-digital converter (ADC), multiplied using a multiplier, and then downsampled by a downsampling digital filter. Like the upsampling digital filter, the downsampling digital filter is preferably a FIR lowpass filter.

[0112] The FIR upsampling and downsampling digital filters together with the analog filters, preferably, dominate over the channel itself. As such, the channel, if assumed to include the baseband-to-RF conversion along with the RF-to-baseband conversion, can be modeled as a FIR channel whose impulse response s(t) equals zero for t<0 and t≧T.

[0113] If the channel is modeled as a FIR channel, the impulse response, s(t), of the channel can be assumed to satisfy s(t)=0 for t<0 and t≧T. Because of this property and the above-described shift orthogonality property of the codes, the following proof holds, where the received waveform is $f\left(t\right)=\sum _{n=1-K}^{N+J}{a}_{n}s\left(t-n{T}_c\right)$

[0114] and the match waveform used at the receiver is: $g\left(t\right)=\sum _{m=1}^N{b}_{m}s\left(t-m{T}_c\right)$

[0115] Thus, the cross correlation of the two signals is $r\left(\tau \right)={\int }_0^{\infty }g\left(t\right)f^{*}\left(t+\tau \right)dt=r_1\left(\tau \right)+r_2\left(\tau \right)+r_3\left(\tau \right)$

[0116] where $r_1\left(\tau \right)\equiv \sum _{m=2}^N\sum _{n=1-K}^{m-K-1}{b}_m{a}_n^{*}p\left(\tau +m{T}_c-n{T}_c\right)$ $r_2\left(\tau \right)\equiv \sum _{m=1}^N\sum _{n=m-K}^{m+J}{b}_m{a}_n^{*}p\left(\tau +m{T}_c-n{T}_c\right)$ $r_3\left(\tau \right)\equiv \sum _{m=1}^{N-1}\sum _{n=m+J+1}^{N+J}{b}_m{a}_n^{*}p\left(\tau +m{T}_c-n{T}_c\right)$

[0117] where $p\left(\tau \right)={\int }_0^{T}s\left(t\right)s^{*}\left(t+\tau \right)dt$

[0118] and p(τ)=0 for τ<−T and τ≧T.

[0119] Now, as will be obvious to one of skill in the art, r₁(τ)=0 for τ≧T−KT_c−T_cand r₃(τ)=0 for τ≧T_c+JT_c−T. Furthermore, $\begin{array}{c}{r}_2\left(\tau \right)=\sum _{m=1}^N\sum _{\nu =-K}^J{b}_m{a}_{m+\nu }^{*}p\left(\tau -\nu T_c\right)\\ =\sum _{\nu =-K}^J\left[\sum _{m=1}^N{b}_m{a}_{m+\nu }^{*}\right]p\left(\tau -\nu T_c\right)\end{array}$

[0120] and, because the shift orthogonality property ensures that the term in brackets is zero for v=−K, . . . ,J it is obvious that r₂(τ)=1 for all τ. Together these statements imply that

[0121] r(τ)=0 for T−KT_c−T_c≦τ≦T_c+JT_c−T.

[0122] and we can make this orthogonality interval large simply by choosing K and J to be large.

[0123] Thus, it is possible to increase the systems tolerance for arbitrary time shifts and maintain orthogonality by simply increasing the circular padding, J and K.

[0124] FIG. 20 provides an illustration of correlating received signals with match waveforms for explaining how the system's increased tolerance for arbitrary, but bounded, time shifts is manifest as a practically zero mutual interference between signals from different transmitters. The figure assumes that three terminals are each assigned a single shift of the cyclically orthogonal code sequence and that these assigned shifts are separated by a minimum number of unassigned shifts, called guard codes. In this embodiment, each terminal circularly pads its assigned code to create a sequence with the above described shift-orthogonality property.

[0125] Each terminal uses its assigned circularly padded code to spread a data-symbol and then transmit the resulting spread data symbol so that it arrives at the HUB 31 at a given time, t₀. Thus, the spread data symbols from the three terminals arrive at the HUB 31 nearly simultaneously and are physically combined in a time-aligned fashion prior to conversion to baseband.

[0126] As illustrated in the figure, and as will be understood by one of skill in the art, although this time alignment can be achieved with reasonable precision there will always remain some small misalignment, τ. Thus, as illustrated, the received baseband signal f(t−t₀) is composed of several portions including a portion f₁(t−t₀−τ₁) corresponding to a spread symbol 2001 transmitted by the first terminal which has arrived at time t₀+τ₁, a portion f₂(t−t₀−τ₂) corresponding to the spread symbol 2002 transmitted by the second terminal which has arrived at time t₀+τ₂, and a portion f₃(t−t₀−τ₃) corresponding to the spread symbol 2003 transmitted by the third terminal which has arrived at time t₀+τ₃.

[0127] To recover the information from the second terminal, the cross-correlator 2006 computes $R_2={\int }_{t_0}^{\infty }{g}_2\left(t-t_0\right)f\left(t-t_0\right)dt$

[0128] where g₂(t) is the match waveform for the spread symbol 2002 transmitted by the second terminal and where

[0129] f(t−t₀)=f₁(t−t₀−τ₁)+f₂(t−t₀−τ₂)+f₃(t−t₀−τ₃)

[0130] This computed cross-correlation will be composed of three components

[0131] R₂=R_{2,1}+R_{2,2}+R_{2,3}

[0132] where, for k=1,2,3, these components are $R_{\left\{2,k\right\}}={\int }_{t_0}^{\infty }{g}_2\left(t-t_0\right)f_k\left(t-t_0-{\tau }_k\right)dt$

[0133] and, because the sequence underlying g₂(t) is shift-orthogonal to the sequences underlying f₁(t) and f₃(t), we will have R_{{2,1 }}=R_{{2,3 }}=0 so long as the misalignments, τ₁and τ₃, are within the bounds:

[0134] T−KT_c−T_c<τ₁,τ₃,<T_c+JT_c−T

[0135] Consequently, R₂=R_{2,2} and there is, for all practical purposes, zero interference from the first and third terminals when the HUB 31 is recovering information from second terminal. Similarly, when the receiver uses the rotating correlator to recover the information from the first terminal by computing the cross-correlation

[0136] R₁=R_{1,1}+R_{1,2}+R_{1,3}

[0137] the components from the second and third terminals, which respectively are R_{1,2} and R_{1,3}, will be zero so long as the misalignments are within the bounds:

[0138] T−KT_c−T_c<τ₂,τ₃<T_c+JT_c−T

[0139] Consequently, R₁=R_{1,1} and again there is, for all practical purposes, zero interference from the second and third terminals when the HUB 31 is recovering information from the first terminal.

[0140] FIG. 21 is a diagram of a rotating correlator 2100 in a receiver for despreading the received spread symbols. Because each code is a circular shift of every other code, the rotating correlator 2100 can despread a symbol that was spread by any of the codes. Thus, when receiving spread symbols from one or more terminals using multiple codes, the same rotating correlator can despread all of the received spread symbols from all of the terminals.

[0141] The rotating correlator 2100 preferably operates by shifting a sampled segment of the received baseband signal into registers 2102. This segment is then combined with a code stored in registers 2104. After which, the last element in registers 2104 is rotated to the first register of registers 2104, each element in registers 2104 is then shifted by one register, and the segment stored in registers 2102 is again combined with the now circularly-shifted code stored in registers 2104. Through this mechanism the segment stored in registers 2102 may be correlated with any or all circular shifts of the code, so the proper shifts can be determined and the received spread symbol can be despread.

[0142] In another embodiment, a Fast Fourier Transform (FFT) may be used to despread the received baseband signal segment. This despreading is accomplished by combining the N samples of the received signal segment with N stored values, designated {tilde over (c)}_nfor n=1, 2, . . . , N. Preferably, {tilde over (c)}_nis a previously computed length-N FFT of the base code of the cyclically orthogonal family of codes. This combining process is accomplished in three steps:

[0143] 1. The length-N FFT of the N received signal samples is computed, thereby generating N transformed signal samples designated {tilde over (r)}_nfor n=1, 2, . . . , N.

[0144] 2. Each transformed signal sample, {tilde over (r)}_n,is multiplied by its corresponding stored value, {tilde over (c)}_n, thereby generating N transformed despread values, {tilde over (e)}_n={tilde over (r)}_n{tilde over (c)}_nfor n=1, 2, . . . , N, and

[0145] 3. The length-N inverse FFT of the N transformed despread values is computed thereby generating N despread values, e_nfor n=1, 2, . . . , N.

[0146] As will be obvious to one of skill in the art, the above process computes all N values of the circular correlation of the base code sequence with the N samples of the received signal segment.

[0147] In addition, as will be understood by one of skill in the art, the direct circular correlation performed by the rotating correlator may be less costly and thereby preferred to the transform domain circular correlation performed by the above-described process using FFT's in certain circumstances. For example, when the circular correlation requires only a small number of values or when the elements of the code sequence can be represented by a small number of bits, permitting the rotating correlator to use low-cost specially designed hardware multipliers, it may be less costly to use a rotating correlator. Thus, a rotating correlator may be preferred for terminals assigned a small number of code shifts or for terminals using a ternary code sequence.

[0148] As will also be understood by one of skill in the art, the transform domain circular correlation process may be less costly and thereby preferred to the rotating correlator when a large number of values of the circular correlation are required or when the elements of the code sequence cannot be readily represented by a small number of bits. Thus, for example, the transform domain circular correlation process may be preferred for despreading the signal in a hub, in a terminal that has been assigned a large number of code shifts, or in the case that the base code sequence is a row of a circulant-unitary matrix.

[0149] Another embodiment of the invention incorporates both the rotating correlator and the transform domain circular correlation process as software elements and selects the despreading technique that requires less computational resources for the circular correlation. Thus, for example, in a terminal that may be assigned a small number of code shifts at one point in time but may be assigned a large number of code shifts at another point in time, the terminal may select to use the rotating correlator at some times and the transform domain circular correlation process at other times to help minimize the cost of the computational resources required by the terminal or to best utilize the available computational resources of the terminal.

[0150] As will be understood by one of skill in the art, the FFT is just one example of a transform with the circular correlation property and that other transforms with the circular correlation property, such as Number Theoretic Transforms (NTT) or Van Der Monde Transforms, may be used to implement the transform domain circular correlation process.

[0151] In addition to signal recovery, as will be obvious to one of skill in the art, both the above described rotating correlator and FFT transform domain circular correlation process can be used at the transmitter for spreading the signals

[0152] While it has been illustrated and described what is at present considered to be the preferred embodiment and methods of the present invention, it will be understood by those skilled in the art that various changes and modifications may be made, and equivalents may be substituted for elements thereof without departing from the true scope of the invention.

[0153] In addition, many modifications may be made to adapt a particular element, technique or, implementation to the teachings of the present invention without departing from the central scope of the invention. Therefore, it is intended that this invention not be limited to the particular embodiment and methods disclosed herein, but that the invention includes all embodiments falling within the scope of the appended claims.