# Patent

## Title
Multi-user interference resilient ultra wideband (UWB) communication

## Abstract

Techniques are described for maintaining the orthogonality of waveforms transmitted in ultra wideband (UWB) multi-user wireless communication systems. The multi-stage block-spreading (MS-BS) techniques described herein deterministically eliminate multiple user interference (MUI) in the presence of frequency-selective fading channels. A transmitter includes a block-spreading unit to generate a stream of frames from a block of information bearing symbols by applying an orthogonal set of spreading codes, such as direct sequence cod& division multiple access (CDMA) codes or digital carrier frequency multiple access codes, such that the frames corresponding to different blocks of the symbols are interleaved. The transmitter further includes a time-hopping spreading unit to generate a stream of chips from the stream of frames by applying an orthogonal set of time-hopping (TH) spreading codes such that chips corresponding to different frames are interleaved.

## Background
This application claims priority from U.S. Provisional Application Ser. No. 60/453,809, filed Mar. 8, 2003, the entire content of which is incorporated herein by reference.


STATEMENT REGARDING FEDERALLY SPONSORED RESEARCH OR DEVELOPMENT
This invention was made with Government support under Subcontract #497420 awarded by the University of Delaware (Army Prime #DAAD19-01-2-011). The Government may have certain rights in the invention.


TECHNICAL FIELD
The invention relates to communication systems and, more particularly, transmitters and receivers for use in multi-user ultra wideband (UWB) communication systems.
BACKGROUND
In multi-user wireless communication systems, such as wireless local area networks, satellite communications and mobile phone networks, multiple transmitters and receivers may communicate simultaneously through a common wireless communication medium. One communication format with attractive features for high data rates and low power consumption is ultra wideband (UWB), also known as impulse radio (IR), in which the transmitter generates a train of ultra short pulses spreading the energy of the transmitted signal across an ultra wide bandwidth. IR technology employing time-hopping (TH) codes pseudo randomly spreads pulses in time, and is often referred to IR multiple access (IRMA).
In general, IRMA applies a TH code chosen from a set of orthogonal “spreading codes” to an outbound stream of “symbols.” Each IRMA pulse transmits a “symbol” representing a discrete information bearing value selected from a finite set (“alphabet”). For example, simple alphabets used by transmitters may be {+1, −1} or {−3, −1, +1, +3}. TH codes apply a finite set of integer values to time shift a sequence of transmitted pulses and produce a set of “chips” for each value to be transmitted. Each TH code has a sequence, resulting in each IRMA pulse train having a defined time period. The resulting chips are transmitted according to some modulation scheme, such as pulse position modulation (PPM). In order to separate signals from multiple users, the receivers isolate the signal of the desired user by matching the user's signal to the corresponding orthogonal spreading code associated with that user.
IRMA systems often operate in dense multi-path environments. IR signaling provides resolvable multi-path components and enables collecting energy from multi-path propagation with appropriate receiver design. However, when multiple users are present, the multi-path propagation also induces multi-user interference (MUI). In addition, the communication channel between the transmitter and the receiver can also become “frequency selective” in that certain frequencies exhibit fading, i.e. significant loss of signal. Consequently, inter-symbol interference (ISI) in which the transmitted symbols interfere with each other destroys the orthogonality of the waveforms at the receiver. MUI, together with ISI, can cause the receiver to be unable to correctly separate the multi-user waveforms, eventually leading to data loss and/or bandwidth and power inefficiencies.
Various “multi-user detectors” have been developed for separating non-orthogonal UWB multi-user waveforms. These multi-user detectors, however, are often complex and expensive to implement in typical mobile communication devices, and typically require knowledge of the characteristics of the current communication channel. For example, linear detectors, such as decorrelating and minimum mean-squared error (MMSE) detectors, often require inversion of large matrices with size increasing in proportion to the square of the number of users, while optimum maximum likelihood (ML) detectors entail exponential complexity. In addition, some analog IRMA systems approximate MUI as Gaussian noise and attempt to suppress it statistically. Such systems require successful application of strict power control and rely on the Gaussian approximation. However, when the number of users is not sufficiently large, the Gaussian approximation is not valid.
SUMMARY
In general, techniques are described for deterministically substantially eliminating multi-user interference (MUI) in multi-user wireless communication systems, such as ultra wideband (UWB) systems Unlike conventional IRMA systems in which MUI is approximated as Gaussian noise and rely on time-hopping (TH) spreading codes to statistically suppress MUI, “multi-stage block-spreading” (MS-BS) techniques are described that eliminate MUI deterministically at the receiver by preserving the orthogonality between different users waveforms through multi-path channels. Furthermore, the techniques described herein allow a larger number of users than conventional IRMA systems and can provide different users with variable transmission rates.
In one embodiment, the invention is directed to a method which generates a stream of frames from blocks of information bearing symbols wherein the frames corresponding to different blocks of the symbols are interleaved and generates a stream of chips from the stream of frames, wherein the chips corresponding to different frames are interleaved. An ultra wideband (UWB) transmission signal is output from the stream of chips. The stream of frames is generated by parsing the symbols into blocks of K symbols, applying an orthogonal set of spreading codes to the blocks of K symbols to form Q frames, and interleaving the Q frames to form the stream of frames. The stream of chips is generated by applying an orthogonal set of time-hopping spreading codes to the interleaved frames to generate a plurality of chips for each frame, and interleaving each of the plurality of chips to form the output stream of chips.
The method may further assign each of the set of spreading codes to a different user of a group of users and assign each user of the group a common one of the time-hopping spreading codes. Unique addresses are assigned to users as unique pair-wise combinations of the set of orthogonal spreading codes and the set of time-hopping spreading codes.
In additional embodiments, the method receives the output signal and outputs a stream of estimate symbols from the signal using a two-stage de-spreading unit having a time-hopping de-spreading module and a multi-user de-spreading module.
In another embodiment, the invention is directed to a wireless communication device having a multiple-user block-spreading unit that generates a set of frames for respective blocks of information bearing symbols and produces a stream of frames in which the frames from different sets are interleaved, a time-hopping block-spreading unit that generates a set of chips for each frame and outputs a stream of chips in which the chips generated from different frames are interleaved, and a pulse shaping unit to output an UWB transmission signal from the stream of interleaved chips.
In yet another embodiment, the invention is directed to a wireless communication device having a two-stage de-spreading unit that processes a received ultra wideband (UWB) transmission signal to produce estimate symbols, wherein the received UWB signal comprises a multi-user block-spread UWB signal formed from interleaved symbol frames and interleaved chips within the symbol frames.
In additional embodiments, the invention is directed to a system having a wireless transmitter to transmit an ultra wideband (UWB) signal according to interleaved chips generated from interleaved frames produced by blocks of information bearing symbols and wireless receiver to receive the UWB signal and de-interleave the chips and frames to produce estimate symbols.
In another embodiment, the invention is directed to a computer-readable medium containing instructions. The instructions cause a programmable processor of a wireless communication device to generate a stream of frames from blocks of information bearing symbols, wherein the frames corresponding to different blocks of the symbols are interleaved, generate a stream of chips from the stream of frames, wherein the chips corresponding to different frames are interleaved, and output an UWB transmission signal from the stream of chips.
The multi-stage block-spreading techniques described herein may offer one or more advantages. For example, MS-BS preserves the orthogonality of a transmitted UWB signal through a multi-user communication channel. Consequently, transmitted signals are resistant to MUI regardless of the underlying frequency selective nature of the multi-path communication channel without using adaptive power control to dynamically adjust the usage of power by transmitter. As a result, the techniques render the multiple access communication channel equivalent to a set of independent parallel single-user frequency-selective channels with additive white Gaussian noise (AWGN). In other words, because the transmitted signals remain orthogonal, IRMA receivers may be implemented with single-user detectors, which are less complex than multi-user detectors. Furthermore, the receiver can be implemented in favor of low complexity or high performance.
Other advantages of the described techniques may include improved bandwidth efficiency, which implies that information can be transmitted at higher rates and that the maximum allowable number of simultaneous users increases. Furthermore, as the number of users increases, an IRMA system that incorporates the described techniques may be more resilient to degradation in bit-error-rate (BER) performance than conventional IRMA systems.
The details of one or more embodiments of the invention are set forth in the accompanying drawings and the description below. Other features, objects, and advantages of the invention will be apparent from the description and drawings, and from the claims.



BRIEF DESCRIPTION OF DRAWINGS
FIG. 1 is a timing diagram illustrating an example time-hopping (TH) pulse position modulation (PPM) scheme in an impulse radio multiple access (IRMA) system.
FIG. 2 is a block diagram illustrating a wireless system impulse radio multiple access (IRMA) format in which multiple transmitters communicate with multiple receivers through a channel.
FIG. 3 is a block diagram illustrating in further detail the multi-user UWB communication system of FIG. 2.
FIG. 4 illustrates an example assignment of multiple users (MU) and time-hopping (TH) addresses.
FIG. 5 is a block diagram illustrating an example transmission of a symbol using PPM in an IRMA system.
FIG. 6 illustrates an example data stream generated by a multi-user block-spreading unit within a UWB transmitter of FIG. 3.
FIG. 7 illustrates an example data stream generated by a TH block-spreading unit within the transmitter of FIG. 3.
FIG. 8 is a flowchart illustrating an example mode of operation of a transmitter in the UWB communication system of FIG. 3.
FIG. 9 is a flowchart illustrating an example mode of operation of a receiver in the UWB communication system of FIG. 3.
FIGS. 10-13 are graphs illustrating modeled performance estimates of the techniques described herein.



DETAILED DESCRIPTION
The techniques described herein use notation defined as follows. Bold upper case letters and lower case letters denote matrices and column vectors respectively. ( )T and ( )H denote transpose and Hermitian transpose respectively. δ( ) and  stand for Kroenecker's delta and Kronecker's product respectively. E { } denotes expectation. └ ┘ and ┌ ┐ denote integer floor and integer ceiling respectively. IK denotes the identity matrix of size K and 0M×N denotes an all zero matrix of size M×N.
FIG. 1 is a timing diagram that illustrates an example transmission of two separate symbols, 1(1A) and 0(1B), using binary pulse position modulation (PPM) in an impulse radio multiple access (IRMA) format. Generally, the PPM-IRMA format described herein is designed such that the PPM delays are sufficiently large to ensure orthogonal modulation using M-ary PPM. As a result, a nonlinear PPM-IRMA format can be viewed as a linearly modulated code-division multiple access (CDMA) format.
Each symbol 1A, 1B represents a discrete information bearing value selected from a finite set (“alphabet”), e.g. {1, 0}. Symbols 1A, 1B are repeated over Nf frames, e.g. Nf=5, with each frame 2 having duration Tf4. During signaling interval Ts 6 of duration T, =NfTf seconds, kb=log2 M message bits having bit rate Rb may be loaded into a kb-bit buffer. The resulting kb-bit output symbol rate is Rs=Rb/kb. For example, the uth user's information bearing symbol transmitted during the kth frame is denoted Iu(└k/Nf┘) where Iu(└k/Nf┘)ε[M−1].
The application of a time-hopping (TH) spreading code to the information bearing symbols produces a set of “chips” over which each symbol 1A, 1B is transmitted. Each frame 2 comprises Nc, e.g. Nc=3, chips with each chip 8 having chip duration Tc9. Frame duration Tf is then equivalent to NcTc+Tg, where Tg is a guard time to account for processing delay at the receiver between two successively received frames. For simplicity Tg is set to zero for all following equations. A nonzero value for Tg does not impose any limiting consequences. The uth user's transmitted waveform vu(t)is given in accordance with equation (1):




  
    
      
        
          
            v
            u
          
          ⁡
          
            (
            t
            )
          
        
        =
        
          
            P
            u
          
          ⁢
          
            
              ∑
              
                -
                ∞
              
              
                +
                ∞
              
            
            ⁢
            
              w
              ⁡
              
                (
                
                  t
                  -
                  
                    k
                    ⁢
                    
                      
                    
                    ⁢
                    
                      T
                      f
                    
                  
                  -
                  
                    
                      c
                      ⁡
                      
                        (
                        k
                        )
                      
                    
                    ⁢
                    
                      T
                      c
                    
                  
                  -
                  
                    τ
                    
                      
                        j
                        u
                      
                      ⁡
                      
                        (
                        
                          ⌊
                          
                            k
                            /
                            
                              N
                              f
                            
                          
                          ⌋
                        
                        )
                      
                    
                  
                
                )
              
            
          
        
      
    
    
      
        (
        1
        )
      
    
  




where Pu is the uth user's transmission power, w(t) denotes the ultra-short pulse 7 and ċu(k)ε[0, Nc−1] 3 is a periodic pseudo random sequence with period Pċ equal to Nf. Ultra-short pulse 7 typically has a duration between 0.20 and 2.0 nanoseconds and may be selected as a Gaussian monocycle, a Gaussian biphase monocycle, a doublet consisting of a positive Gaussian pulse followed by its negative, and the like. The role of ċu(k) 3 is to enable both multiple users over a communication channel and security.

Each signaling interval Ts6 of the transmitted waveform in equation (1) includes Nf copies of a single symbol 1A, 1B, i.e. one per frame 2, with pulse 7 time-shifted in each frame 2 according to the symbol value, e.g. it is shifted by τm for Iu(└κ/Nf┘)=m where m ε[0, 1, . . . , M−1]. In order to ensure orthogonal modulation, PPM modulation delays τm must satisfy τm−τm−≧Tw for ∀mε[1, 2, . . . , M−1]. Thus, chip duration Tc9 should be chosen to satisfy Tc≧τm−1+Tw≧MTw.
The orthogonal M-ary PPM of the uth user can be viewed as having M parallel branches with each parallel branch realizing a shifted version of the pulse stream. Consequently, in order to generate the waveform vu(t) as given in equation (1), only one branch out of the M parallel branches needs to be selected depending on the symbol value. Summing the M parallel branches, waveform vu(t) can be rewritten in terms of waveform vu,m(t) as given in equations (2) and (3) respectively.




  
    
      
        
          
            v
            u
          
          ⁡
          
            (
            t
            )
          
        
        =
        
          
            ∑
            
              m
              =
              0
            
            
              m
              =
              
                M
                -
                1
              
            
          
          ⁢
          
            
              v
              
                u
                ,
                m
              
            
            ⁡
            
              (
              t
              )
            
          
        
      
    
    
      
        (
        2
        )
      
    
  
  
    
      
        
          
            v
            
              u
              ,
              m
            
          
          ⁡
          
            (
            t
            )
          
        
        =
        
          
            P
            u
          
          ⁢
          
            
              ∑
              
                k
                =
                
                  -
                  ∞
                
              
              
                k
                =
                
                  +
                  ∞
                
              
            
            ⁢
            
              
                
                  s
                  
                    u
                    ,
                    m
                  
                
                ⁡
                
                  (
                  
                    ⌊
                    
                      k
                      /
                      
                        N
                        f
                      
                    
                    ⌋
                  
                  )
                
              
              ⁢
              
                w
                ⁡
                
                  (
                  
                    t
                    -
                    
                      k
                      ⁢
                      
                        
                      
                      ⁢
                      
                        T
                        f
                      
                    
                    -
                    
                      
                        c
                        ⁡
                        
                          (
                          k
                          )
                        
                      
                      ⁢
                      
                        T
                        c
                      
                    
                    -
                    
                      τ
                      m
                    
                  
                  )
                
              
            
          
        
      
    
    
      
        (
        3
        )
      
    
  




The waveform su,m(└k/Nf┘):=δ(Iu(└k/Nf┘)−m), ∀ m ε[0, M−1] (12). Equation (3) can be rewritten as equation (4) by defining monocycles 7 as pulse functions wm(t):=w(t−τm) and using the substitution Tf=NcTc.





  
    
      
        
          
            v
            
              u
              ,
              m
            
          
          ⁡
          
            (
            t
            )
          
        
        =
        
          
            P
            u
          
          ⁢
          
            
              ∑
              
                k
                =
                
                  -
                  ∞
                
              
              
                k
                =
                
                  +
                  ∞
                
              
            
            ⁢
            
              
                
                  s
                  
                    u
                    ,
                    m
                  
                
                ⁡
                
                  (
                  
                    ⌊
                    
                      k
                      /
                      
                        N
                        f
                      
                    
                    ⌋
                  
                  )
                
              
              ⁢
              
                
                  w
                  m
                
                ⁡
                
                  (
                  
                    t
                    -
                    
                      
                        (
                        
                          
                            k
                            ⁢
                            
                              
                            
                            ⁢
                            
                              N
                              c
                            
                          
                          +
                          
                            c
                            ⁡
                            
                              (
                              k
                              )
                            
                          
                        
                        )
                      
                      ⁢
                      
                        T
                        c
                      
                    
                  
                  )
                
              
            
          
        
      
    
    
      
        (
        4
        )
      
    
  




Because ċu(k)ε[0, Nc−1] 3 is an integer, wm(t) is shifted by an integer multiple of Tc 9. As a result waveform vu,m(t) can be written in equation (5) accordingly. Equation (5) can be viewed as a linearly modulated waveform with symbol rate Rs=1/Tc while equation (2) can be viewed as the superposition of M linear modulators, each with a different pulse function wm(t).




  
    
      
        
          
            v
            
              u
              ,
              m
            
          
          ⁡
          
            (
            t
            )
          
        
        =
        
          
            P
            u
          
          ⁢
          
            
              ∑
              
                k
                =
                
                  -
                  ∞
                
              
              
                k
                =
                
                  +
                  ∞
                
              
            
            ⁢
            
              
                
                  v
                  
                    u
                    ,
                    m
                  
                
                ⁡
                
                  (
                  n
                  )
                
              
              ⁢
              
                
                  w
                  m
                
                ⁡
                
                  (
                  
                    t
                    -
                    
                      n
                      ⁢
                      
                        
                      
                      ⁢
                      
                        T
                        c
                      
                    
                  
                  )
                
              
            
          
        
      
    
    
      
        (
        5
        )
      
    
  




Sequence vu,m(n) is dependent on su,m(k) and ċu(k) 3. Chip-rate code sequence cu(n) 5 with period Pc=NcPċ is defined via ċu(k) 3 as given in equation (6).

cu(n):=δ(└n/Nc┘Nc+cu(└n/Nc┘)−n)  (6)

The relation between ċu(k) 3 and cu(n) 5 is given by the mapping between chip index n and frame index k. As a result, the uth user's chip sequence on the mth branch vu,m(n) can be expressed according to equation (7).

vu,m(n)=su,m(└n/NcNf┘)cu(n)  (7)

Sequence su,m(└n/(NcNf)┘) does not change over the duration of NfNc chips (NfTf seconds) and is spread by cu(n) 5 in equation (2) to generate chip sequence vu,m(n) in equation (7). From this chip-rate sampled model, the nonlinearly modulated PPM-IRMA format can be viewed as a linearly modulated code-division multiple access (CDMA) format.
Although Tg was set equal to zero, the model can also include Tg as nonzero. This can be accomplished by setting Tg=NgTc with Ng being an integer and restricting ċ(k) 3_ to take on values [0, Nc′−1], where Nc′:=Nc−Ng. Hereafter, all equations and derivations will assume Tg=0.
FIG. 2 is a block diagram illustrating multi-user wireless communication system 10 in which multiple transmitters 12 communicate with receivers 14 through wireless channel 16 via the M-ary PPM-IRMA format described in FIG. 1. In general, the invention provides techniques for deterministically substantially eliminating multi-user interference (MUI) 18 in communication system 10 that could be introduced in waveforms produced by transmitters 12 during transmission through communication channel 16.
Transmitters 12 transmit information using techniques referred to herein as “multi-stage block-spreading” (MS-BS). MS-BS generates a stream of frames from blocks of information symbols wherein the frames corresponding to different blocks of the symbols are interleaved and a stream of chips is generated from the stream of frames wherein the chips corresponding to different frames are interleaved. Transmitters 12 output a UWB transmission signal from the stream of chips.
The stream of frames is generated by applying an orthogonal set of spreading codes, such as direct sequence CDMA codes, TDMA codes, or FDMA codes, while the stream of chips is generated by applying an orthogonal set of TH spreading codes. The stream of chips may be padded with a number of guard chips determined as a function of length of channel 16. The set of spreading codes and the set of TH spreading codes are mutually exclusive so that the interleaved and padded chips retain their orthogonality after passing through channel 16. Each user of a group of users is assigned a spreading code from the set of spreading codes and is also assigned a common TH spreading code from the set of TH spreading codes. System 10 supports a total number of users determined by the product of the number of frames over which an information symbol is repeated Nf and the number of chips in each frame Nc.
MS-BS techniques preserve the orthogonality between different users signals through communication channel 16 regardless of the underlying frequency selective nature of the multi-path communication channel thereby rendering channel 16 equivalent to a set of independent parallel single-user frequency-selective channels with additive white Gaussian noise (AWGN).
Receivers 14 receive the UWB transmission signal output by transmitters 12 and output a stream of estimate symbols from the received signal using a two-stage de-spreading unit having a TH de-spreading module and a multi-user de-spreading module. The stream of output symbols is generated by converting the received signal to a stream of chips and applying a first de-spreading matrix with the TH de-spreading module to de-interleave the chips into blocks of frames. The multi-user de-spreading module applies a second de-spreading matrix to the blocks of frames to de-interleave the frames and produce blocks of estimate symbols. A single user detection scheme is applied to the blocks of estimates symbols to output the stream of the estimate symbols.
These techniques work with existing communication systems using IRMA with orthogonal M-ary pulse position modulation (PPM) to eliminate MUI 18 deterministically at receivers 14 and apply to uplink and downlink transmissions, i.e., transmissions from a base station to a mobile device and vice versa. Transmitters 12 and receivers 14 may be any device configured to communicate using a multi-user wireless transmission including a hub for a wireless local area network, a cellular phone, a laptop, handheld computing device, a personal digital assistant (PDA), or a cellular distribution station, and the like.
The techniques described herein may be applied to uplink and/or downlink transmissions, i.e., transmissions from a base station to a mobile device and vice versa. Consequently, transmitter 12 and receiver 14 may be any device configured to communicate using a multi-user ultra wideband wireless transmission including a distribution station, a hub for a wireless local area network, a mobile phone, a laptop or handheld computing device, a personal digital assistant (PDA), a device within a wireless personal area network, a device within a sensor network, or other device.
FIG. 3 is a block diagram illustrating in further detail multi-user communication system 10 of FIG. 2 using multi-stage block-spreading (MS-BS). For simplicity, the mth branch of a transmitter 12 and the m′th branch at a receiver 14 are given in detail for the uth user. Transmitter 12 applies MS-BS techniques and pulse shaping to chip-rate information bearing symbols su,m(n) 20 and transmits the MS-BS M-ary pulse position modulated (PPM) IRMA waveform vu,m(t) 28. Receiver 14 receives chip-rate sampled sequence xm′(n) 38 and outputs symbol estimates 49.
Generally, multiple transmitters 12 corresponding to different users assign each user a unique spreading code from a set of orthogonal spreading codes, such as direct sequence CDMA codes TDMA codes, or FDMA codes. Additionally each user is assigned a TH spreading code from a set of orthogonal spreading codes such that within a group of users, each user with a unique orthogonal spreading code is also assigned a common TH spreading code. Therefore, a unique address {uA, UB} can be assigned to each user with the first index of the address indicating the TH code assigned to the uth user and the second index indicating the orthogonal spreading code assigned to the uth user.
Serial to parallel (S/P) converter 21 of transmitter 12 parses serial chip-rate data stream su,m(n) 20 into blocks of K symbols 22, each symbol representing a discrete information bearing value, as defined in equation (8).

su,m(i):=[su,m(iK), . . . , su,m(iK+K−1)]T  (8)

As described in detail below, multi-user block-spreading unit 23 applies an orthogonal spreading code according to the address assigned to the uth that generates a stream of Q frames from blocks of K information bearing symbols and interleaves the frames corresponding to different blocks of the symbols. Each block of K symbols is spread into NfK×1, where NfK=Q, output vectors 24 according to equation (9) via Q×K spreading matrix DuB given in equation (10).

{hacek over (s)}u,m(i)=DuBsu,m(i), where {hacek over (s)}u,m(i):=[{tilde over (s)}u,m(iQ), . . . , {tilde over (s)}u,m(iQ+Q−1)]T  (9)

DuB:=duBIK  (10)

In other words, the K symbol blocks are symbol-spread into Q frame-rate signals and then frame-interleaved to provide data stream 24 according to equation (9). In rewriting equation (9), it can be seen multi-user block-spreading unit 23 implements a multi-code transmitter with K codes per user as given in equation (11).




  
    
      
        
          
            
              s
              ˇ
            
            
              u
              ,
              m
            
          
          ⁡
          
            (
            i
            )
          
        
        =
        
          
            ∑
            
              k
              =
              0
            
            
              k
              =
              
                K
                -
                1
              
            
          
          ⁢
          
            
              
                s
                
                  u
                  ,
                  m
                
              
              ⁡
              
                (
                
                  
                    i
                    ⁢
                    
                      
                    
                    ⁢
                    K
                  
                  +
                  k
                
                )
              
            
            ⁢
            
              d
              
                u
                ⁢
                
                  
                
                ⁢
                B
              
              
                (
                k
                )
              
            
          
        
      
    
    
      
        (
        11
        )
      
    
  




Each column of spreading matrix DuB can be viewed as a separate spreading code for the uth user, with the (k+1)st column denoted by duB(k).

Similarly, TH spreading unit 25 applies a TH spreading code selected from a set of mutually orthogonal TH spreading codes according to the address assigned to the uth user. Each block of Q frame-rate signals of data stream 24 is spread into a stream of P chips wherein the chips corresponding to different frames are interleaved. In other words, TH block-spreading unit 25 spreads a block of Q frame-rate signals into P chip-rate signals followed by chip interleaving and zero padding via spreading matrix CuA according to equation (12).

vu,m(i)=CuA{hacek over (s)}u,m(i)  (12)

TH spreading matrix CuA is derived from equations (13, 14) and defined in equation (15).

cuA(q):=[cu.A(qNc), CuA(qNc+1), . . . , cuA(qNc+Nc−1)]T, for qε[0, Nf−1]  (13)

Recall that CuA is given by equation (6). Matrix CuA(q) is defined in equation (14).

CuA(q):=cuA(q)Tzp, where Tzp:=[IK, 0K×L]T for  (14)

Zero-padding matrix Tzp is a (K+L)×K matrix and appends L zeros at the end of each column upon multiplication. The guard chips may be null values as implemented here with zero padding via matrix multiplication. TH spreading matrix CuA can then be written as in equation (16).

CuA:=diag{CuA(0), CuA(1), . . . , CuANf−1)}  (15)

TH spreading matrix CuA is of size P×Q, where P=Nf Nc(K+L). The parameter L is determined by the effective length of channel 16 in discrete time and is calculated below. As a result, data stream 26 at the output of TH block-spreading unit 25 is given by the P×1 vector on the mth branch in equation (16) and is given in matrix-vector form according to equation (17).

vu,m(i):=[vu,m(iP), . . . , vu,m(iP+P−1)]T  (16)

vu,m(i)=CuADuBsu,m(i)  (17)

At the output of the two-stage MS_BS parallel to serial (P/S) converter 27 parses blocks of P chips into serial data stream vu,m(n) 28. MS-BS techniques may also offer different users variable transmission rates. Assigning the uth user a set of Au MU and TH address pairs denoted by ωu allows equation (17) to be rewritten as equation (18).




  
    
      
        
          
            v
            
              u
              ,
              m
            
          
          ⁡
          
            (
            i
            )
          
        
        =
        
          
            ∑
            
              
                {
                
                  
                    ω
                    A
                  
                  ,
                  
                    ω
                    B
                  
                
                }
              
              ∈
              
                Ω
                u
              
            
          
          ⁢
          
            
              C
              
                ω
                ⁢
                
                  
                
                ⁢
                A
              
            
            ⁢
            
              D
              
                ω
                ⁢
                
                  
                
                ⁢
                B
              
            
            ⁢
            
              
                
                  s
                  ˇ
                
                
                  u
                  ,
                  m
                
                
                  {
                   
                  ⁢
                  
                    
                      ω
                      A
                    
                    ,
                    
                      ω
                      B
                    
                  
                  }
                
              
              ⁡
              
                (
                i
                )
              
            
          
        
      
    
    
      
        (
        18
        )
      
    
  




In other words, the uth user can transmit Au symbol blocks of length K simultaneously, each carried on a distinct address pair {ωA, ωB}εωu. Consequently, the uth user can transmit a total number of Ku=Au K symbols during each burst of PTc seconds with a corresponding transmission rate Ru=Ku/(PTc). In order to avoid address collisions and guarantee deterministic symbol block separation, the address must be assigned such that additional conditions (19, 20) are satisfied.





  
    
      
        
          
            
              ⋃
              u
            
            ⁢
            
              Ω
              u
            
          
          ∈
          Ω
        
        ,
        
          ∀
          
            u
            ∈
            
              [
              
                0
                ,
                
                  
                    N
                    u
                  
                  -
                  1
                
              
              ]
            
          
        
      
    
    
      
        (
        19
        )
      
    
  
  
    
      
        
          
            
              Ω
              u
            
            ⋂
            
              Ω
              μ
            
          
          =
          ∅
        
        ,
        
          ∀
          u
        
        ,
        
          μ
          ∈
          
            [
            
              0
              ,
              
                
                  N
                  u
                
                -
                1
              
            
            ]
          
        
        ,
        
          
            and
            ⁢
            
              
            
            ⁢
            u
          
          ≠
          μ
        
      
    
    
      
        (
        20
        )
      
    
  




Data stream 28 propagates through equivalent channel 30 which includes pulse shaper 32, physical channel 16, AWGN noise 34, and matched filter 36. Pulse shaper 32 converts serial data stream 28 to the analog transmitted signal 31 vu,m(t) by varying the interval between pulses according to the data being modulated and according to the assigned TH spreading code by applying previously defined pulse shaping functions, wm(t):=w(t−τm). Analog signal 31 propagates through multi-path frequency selective physical channel 16, denoted gu(t) in which AWGN 34 is added to the signal and is filtered by matched filter 36 on the m′th branch, wm′(t), matched to wm′(t) where m′ε[0, M−1].
The chip-sampled discrete time equivalent finite impulse response (FIR) channel can be represented according to equation (21) where * denotes convolution.

hu,m′,m(l):=(wm*gu*wm)(t)|t=lTc  (21)

Equivalent FIR channel of equation (21) of order Lu includes the uth user's asynchronism in the form of delay factors as well as transmit-receive filters, and the multi-path effects. AWGN 34, denoted η(t), is effectively sampled at chip-rate, t=nTc, and can be represented as sampled AWGN noise according to equation (22).

ηm′(n):=(η* wm′)(t)|t=nTc  (22)

Receiver 14 receives the chip-sampled matched filter output 38 from matched filter 36 as given in equation (23).





  
    
      
        
          x
          
            
              m
              ′
            
            ⁢
            
              
            
            ⁢
            
              (
              n
              )
            
          
        
        =
        
          
            
              ∑
              
                u
                =
                0
              
              
                
                  N
                  u
                
                -
                1
              
            
            ⁢
            
              
                ∑
                
                  m
                  =
                  0
                
                
                  M
                  -
                  1
                
              
              ⁢
              
                
                  ∑
                  
                    l
                    =
                    0
                  
                  L
                
                ⁢
                
                  
                    P
                    u
                  
                  ⁢
                  
                    
                      h
                      
                        u
                        ,
                        
                          m
                          ′
                        
                        ,
                        m
                      
                    
                    ⁡
                    
                      (
                      l
                      )
                    
                  
                  ⁢
                  
                    
                      v
                      
                        u
                        ,
                        m
                      
                    
                    ⁡
                    
                      (
                      
                        n
                        -
                        l
                      
                      )
                    
                  
                
              
            
          
          +
          
            
              η
              
                m
                ′
              
            
            ⁡
            
              (
              n
              )
            
          
        
      
    
    
      
        (
        23
        )
      
    
  




Nu is the number of users, L is the maximum length of communication channel 16 in discrete time for the uth user, and M is the number of PPM pulse shapers.

Asynchronism among users in the uplink of a quasi-synchronous system, i.e. a system in which there is a coarse timing reference, is limited to a few chip intervals. The maximum asynchronism, τcmax,a, arises between the nearest and the farthest mobile users and the maximum multi-path spread, τmax,s, can be found using field measurements from the operational environment. The maximum channel order can then be determined by equation (24).

L=┌(τmax,s+τmax,a)/Tc┐  (24)

The downlink model, e.g. from the base station to user of interest μ, is subsumed by the uplink model presented above by setting hu,m′,l(l)=hu,m′,l(l), ∀uε[0, Nu−1], since the latter allows for distinct user channels. Downlink transmissions are synchronous with τmax,a=0 and maximum channel order L depends only on τmax,s through L=┌(τmax,s/Tc┐. The only channel knowledge assumed at transmitters 12 in the uplink or downlink model is L.

At receiver 14, serial to parallel unit 40 converts chip-rate sampled sequence 38 into P×1 blocks 41 as given in equation (25).

xm′(i):=[xm′(iP), xm′(iP+1), . . . , xm′(iP+P−1)]T  (25)

Chip-rate sampled blocks 41 are received in the presence of P×1 noise blocks given in equation (26).

ηm′(i):=[ηm′(iP), ηm′(iP+1), . . . , ηm′(iP+P−1)]T  (26)

Allowing Hu,m′,m,0 to be the P×P lower triangular Toeplitz matrix with first column [hu,m′,m(0), . . . , hu,m′,m(L), 0, . . . , 0]T and Hu,m′,m,1 be the P×P upper triangular Toeplitz matrix with first row [0, . . . , 0, hu,m′,m(L), . . . , hu,m′,m(1)]T the input-output block relationship through equivalent channel 30 can be described in matrix form according to equation (27).





  
    
      
        
          
            
              
                
                  x
                  
                    m
                    ′
                  
                
                ⁡
                
                  (
                  i
                  )
                
              
              =
              
              ⁢
              
                
                  ∑
                  
                    u
                    =
                    0
                  
                  
                    
                      N
                      u
                    
                    -
                    1
                  
                
                ⁢
                
                  
                    ∑
                    
                      m
                      =
                      0
                    
                    
                      M
                      -
                      1
                    
                  
                  ⁢
                  
                    
                      P
                      u
                    
                    [
                    
                      
                        
                          H
                          
                            u
                            ,
                            
                              m
                              ′
                            
                            ,
                            m
                            ,
                            0
                          
                        
                        ⁢
                        
                          
                            v
                            
                              u
                              ,
                              m
                            
                          
                          ⁡
                          
                            (
                            i
                            )
                          
                        
                      
                      +
                    
                  
                
              
            
          
        
        
          
            
              
              ⁢
              
                
                  
                    H
                    
                      u
                      ,
                      
                        m
                        ′
                      
                      ,
                      m
                      ,
                      1
                    
                  
                  ⁢
                  
                    
                      v
                      
                        u
                        ,
                        m
                      
                    
                    ⁡
                    
                      (
                      
                        i
                        -
                        1
                      
                      )
                    
                  
                
                +
                
                  
                    η
                    
                      m
                      ′
                    
                  
                  ⁡
                  
                    (
                    i
                    )
                  
                
              
            
          
        
      
    
    
      
        (
        27
        )
      
    
  




With vu,m(i) as defined in equation (17) and making use of the mathematical address assigning rules defined below, equation (27) can be rewritten as given in equation (28).





  
    
      
        
          
            x
            
              m
              ′
            
          
          ⁡
          
            (
            i
            )
          
        
        =
        
          
            ∑
            
              
                u
                A
              
              =
              0
            
            
              
                N
                c
              
              -
              1
            
          
          ⁢
          
            
              ∑
              
                
                  u
                  B
                
                =
                0
              
              
                
                  N
                  f
                
                -
                1
              
            
            ⁢
            
              
                ∑
                
                  m
                  =
                  0
                
                
                  M
                  -
                  1
                
              
              ⁢
              
                
                  P
                  u
                
                ⁢
                
                   
                  
                    [
                    
                       
                      
                         
                        
                          
                            
                              H
                              
                                u
                                ,
                                
                                  m
                                  ′
                                
                                ,
                                m
                                ,
                                0
                              
                            
                            ⁢
                            
                              C
                              
                                u
                                ⁢
                                
                                  
                                
                                ⁢
                                A
                              
                            
                            ⁢
                            
                              D
                              
                                u
                                ⁢
                                
                                  
                                
                                ⁢
                                B
                              
                            
                            ⁢
                            
                              
                                s
                                
                                  u
                                  ,
                                  m
                                
                              
                              ⁡
                              
                                (
                                i
                                )
                              
                            
                          
                          +
                          
                            

                          
                          ⁢
                          
                            
                          
                          ⁢
                          
                            
                              H
                              
                                u
                                ,
                                
                                  m
                                  ′
                                
                                ,
                                m
                                ,
                                1
                              
                            
                            ⁢
                            
                              C
                              
                                u
                                ⁢
                                
                                  
                                
                                ⁢
                                A
                              
                            
                            ⁢
                            
                              D
                              
                                u
                                ⁢
                                
                                  
                                
                                ⁢
                                B
                              
                            
                            ⁢
                            
                              s
                              
                                u
                                ,
                                m
                              
                            
                            ⁢
                            
                               
                              
                                
                                  (
                                  
                                    i
                                    -
                                    1
                                  
                                  )
                                
                                +
                                
                                  
                                    η
                                    
                                      m
                                      ′
                                    
                                  
                                  ⁡
                                  
                                    (
                                    i
                                    )
                                  
                                
                              
                            
                          
                        
                      
                    
                  
                
              
            
          
        
      
    
    
      
        (
        28
        )
      
    
  




The su,m(i-1) dependent term in equation (28) accounts for inter-block interference (IBI) and will be shown to equal a 0P×1 matrix.

Receiver 14 performs multi-user separation on the P×1 chip rate sampled blocks 41 by applying de-spreading matrices {hacek over (C)}uA and {hacek over (D)}uB in TH de-spreading unit 42 and multi-user de-spreading unit 44 respectively. P×Nf(K+L) TH de-spreading matrix {hacek over (C)}uA and Nf(K+L)×(K+L) multi-user de-spreading matrix {hacek over (D)}uB are given in equations (29, 30) respectively.

{hacek over (C)}uA:=diag{{hacek over (C)}uA(0), {hacek over (C)}uA(1), . . . , {hacek over (C)}uANf−1}  (29)

{hacek over (D)}uB:=duBIK+L  (30)

TH de-spreading matrix {hacek over (C)}uA is similarly derived as CuA from equations (6, 13) and equation (31).

{hacek over (C)}uA(q):=cuA(q)IK+L  (31)

TH de-spreading unit 42 and MU de-spreading unit 44 perform multi-stage block-de-spreading and enable separation of the μth user's signal from superimposed multi-user signals deterministically. TH de-spreading matrix {hacek over (C)}uA can be viewed as chip-de-interleaving followed by block-de-spreading. Similarly, multi-user de-spreading matrix {hacek over (D)}uB can be viewed as frame-de-interlaving followed by block-de-spreading.

Transceiver pairs {CuA, {hacek over (C)}uA}uA=0Ne−1 and {DuB{hacek over (D)}uB}uB=0Nf−1 are designed such that superimposed multi-user signals can be separated deterministically regardless of multi-path propagation through frequency selective ISI channels of order L. The properties of the Kronecker product can be used to verify the following mutual orthogonality relationships between any two users u and μ as given in equations (32-35).

CμAHCuA=δ(μA−uA)INfK  (32)

{hacek over (C)}uAH{hacek over (C)}uA=δ(μA−uA)INf(K+L)  (33)

DμBHDuB=Nfδ(μB−uB)IK  (34)

{hacek over (D)}μBH{hacek over (D)}uB=Nfδ(μB−uB)IK+L  (35)

The multiple-stage block-de-spreading performed by TH de-spreading unit 42 and multi-user de-spreading unit 44 separate the μth user's signal from 41 and output MUI free block according to equation (36)

yμ,m′(i)={hacek over (D)}Hμ{hacek over (C)}HμAxm′(i), ∀m′ε[0, M−1]  (36)

MUI free output 45 given by equation (37) can then be input into any single-user detector 46 to eliminate channel effects and output symbol block estimates.

yμ(i):=[yTμ,0(i), yTμ,1(i), . . . , yTμ,M−1(i)]T  (37)

Equations (36, 37) can be rewritten to explicitly show that the superimposed received signals from multiple users can be separated deterministically regardless of the FIR multi-path channel when choosing transceiver pairs {CuA, {hacek over (C)}uA}uA=0Ne−1 and {DuB{hacek over (D)}uB}uB=0Nf−1. By design, the last L rows of TH spreading matrix CuA are zeros while the nonzero elements of Hu,m′,m,1 appear only in its last L columns. Equations (38, 39) prove IBI interference is deterministically eliminated.

Hu,m′,m,1CuA=0PxNfK  (38)

Hu,m′,m,1CuADuBSu,m(i−1)=0P×1  (39)

Further, equations (43, 44) derived from following equations (40-42) explicitly show that the superimposed received signals from multiple users can be separated deterministically after propagation through FIR multi-path channels. This is due to the design of mutually orthogonal transceiver pairs {CuA, {hacek over (C)}uA}uA=0Ne−1 and {DuB{hacek over (D)}uB}uB=0Nf−1 given in equations (32-35) which preserves the code orthogonality among users. In the following equations Ĥu,m′,m is a tall Toeplitz matrix of dimension (K+L)×K.

Ĥu,m′,mCuADuBsu,m(i)={hacek over (C)}uA{hacek over (D)}uBĤu,m′,msu,m(i)  (40)





  
    
      
        
          
            x
            
              m
              ′
            
          
          ⁡
          
            (
            i
            )
          
        
        =
        
          
            ∑
            
              
                u
                A
              
              =
              0
            
            
              
                N
                c
              
              -
              1
            
          
          ⁢
          
            
              
                C
                ˇ
              
              
                u
                ⁢
                
                  
                
                ⁢
                A
              
            
            ⁢
            
              
                ∑
                
                  
                    u
                    ⁢
                    
                      
                    
                    ⁢
                    B
                  
                  =
                  0
                
                
                  
                    N
                    f
                  
                  -
                  1
                
              
              ⁢
              
                
                  
                    
                      D
                      ⁢
                      
                        
                      
                    
                    ˇ
                  
                  
                    u
                    ⁢
                    
                      
                    
                    ⁢
                    B
                  
                
                ⁢
                
                  
                    ∑
                    
                      m
                      =
                      0
                    
                    
                      M
                      -
                      1
                    
                  
                  ⁢
                  
                    
                      P
                      u
                    
                    [
                    
                      
                        
                          
                            H
                            ^
                          
                          
                            u
                            ,
                            
                              m
                              ′
                            
                            ,
                            m
                          
                        
                        ⁢
                        
                          
                            s
                            
                              u
                              ,
                              m
                            
                          
                          ⁡
                          
                            (
                            i
                            )
                          
                        
                      
                      +
                      
                        
                          η
                          
                            m
                            ′
                          
                        
                        ⁡
                        
                          (
                          i
                          )
                        
                      
                    
                  
                
              
            
          
        
      
    
    
      
        (
        41
        )
      
    
  




Equation (41) is derived by substituting equation (39) into equation (28) and using the equality in equation (40) which shows channel matrix Hu,m′,m,0 commutes with TH and MU spreading matrices CuA and DuB. Using equations (32-35) and equation (41), equation (36) can be rewritten according to equation (42).





  
    
      
        
          
            
              
                
                  y
                  
                    μ
                    ,
                    
                      m
                      '
                    
                  
                
                ⁡
                
                  (
                  i
                  )
                
              
              =
              
              ⁢
              
                
                  
                    D
                    ⋁
                  
                  
                    μ
                    ⁢
                    
                      
                    
                    ⁢
                    B
                  
                  H
                
                ⁢
                
                  
                    C
                    ⋁
                  
                  
                    μ
                    ⁢
                    
                      
                    
                    ⁢
                    A
                  
                  H
                
                ⁢
                
                  
                    ∑
                    
                      
                        u
                        A
                      
                      =
                      0
                    
                    
                      
                        N
                        c
                      
                      -
                      1
                    
                  
                  ⁢
                  
                    
                      ∑
                      
                        
                          u
                          ⁢
                          
                            
                          
                          ⁢
                          B
                        
                        =
                        0
                      
                      
                        
                          N
                          f
                        
                        -
                        1
                      
                    
                    ⁢
                    
                      
                        
                          C
                          ⋁
                        
                        
                          u
                          ⁢
                          
                            
                          
                          ⁢
                          A
                        
                      
                      ⁢
                      
                        
                          D
                          ⋁
                        
                        
                          u
                          ⁢
                          
                            
                          
                          ⁢
                          B
                        
                      
                      ⁢
                      
                        
                          ∑
                          
                            m
                            =
                            0
                          
                          
                            M
                            -
                            1
                          
                        
                        ⁢
                        
                          
                        
                        ⁢
                        
                          
                            P
                            u
                          
                          [
                          
                            
                              
                                
                                  H
                                  ^
                                
                                
                                  u
                                  ,
                                  
                                    m
                                    '
                                  
                                  ,
                                  m
                                
                              
                              ⁢
                              
                                
                                  s
                                  
                                    u
                                    ,
                                    m
                                  
                                
                                ⁡
                                
                                  (
                                  i
                                  )
                                
                              
                            
                            +
                          
                        
                      
                    
                  
                
              
            
          
        
        
          
            
              
              ⁢
              
                
                  
                    D
                    ⋁
                  
                  
                    μ
                    ⁢
                    
                      
                    
                    ⁢
                    B
                  
                  H
                
                ⁢
                
                  
                    C
                    ⋁
                  
                  
                    μ
                    ⁢
                    
                      
                    
                    ⁢
                    A
                  
                  H
                
                ⁢
                
                  
                    η
                    
                      m
                      '
                    
                  
                  ⁡
                  
                    (
                    i
                    )
                  
                
              
            
          
        
      
    
    
      
        (
        42
        )
      
    
  




With the substitution {acute over (η)}m′(i):={hacek over (D)}uBH{hacek over (C)}μAHηm, (i) equation (42) can be rewritten as equation (43) which shows the specified user, μ, is separated from MUI via multi-stage block-de-spreading {hacek over (D)}μBH{hacek over (C)}μAH.

yμm′(i)=NfPuĤμm′,msμ,m(i)+{acute over (η)}m′(i)  (43)

Multi-stage block-de-spreading output can be written in equation (44) using MK×1 blocks sμ(i):=[sμ,0T(i), sμ,1T(i), . . . , sμ,M−1T(i)]T. Multi-stage block-de-spreading output yμ,m′(i) and noise {acute over (η)}(i) are M(K+L)×1 vectors generated by concatenating the output blocks from the receiver filters matched to the M waveforms and Ĥμ is the M(K+L)×MK matrix given by equation (45).

yu(i)=NfPuĤμsμ(i)+{acute over (η)}(i)  (44)





  
    
      
        
          
            H
            ⋁
          
          μ
        
        :=
        
          [
          
            
              
                
                  
                    H
                    ⋁
                  
                  
                    μ
                    ,
                    0
                    ,
                    0
                  
                
              
              
                
                  
                    H
                    ⋁
                  
                  
                    μ
                    ,
                    0
                    ,
                    1
                  
                
              
              
                ⋯
              
              
                
                  
                    H
                    ⋁
                  
                  
                    μ
                    ,
                    0
                    ,
                    
                      M
                      -
                      1
                    
                  
                
              
            
            
              
                
                  
                    H
                    ⋁
                  
                  
                    μ
                    ,
                    1
                    ,
                    0
                  
                
              
              
                
                  
                    H
                    ⋁
                  
                  
                    μ
                    ,
                    1
                    ,
                    1
                  
                
              
              
                ⋯
              
              
                
                  
                    H
                    ⋁
                  
                  
                    μ
                    ,
                    1
                    ,
                    
                      M
                      -
                      1
                    
                  
                
              
            
            
              
                ⋮
              
              
                ⋮
              
              
                ⋰
              
              
                ⋮
              
            
            
              
                
                  
                    H
                    ⋁
                  
                  
                    μ
                    ,
                    
                      M
                      -
                      1
                    
                    ,
                    0
                  
                
              
              
                
                  
                    H
                    ⋁
                  
                  
                    μ
                    ,
                    
                      M
                      -
                      1
                    
                    ,
                    1
                  
                
              
              
                ⋯
              
              
                
                  
                    H
                    ⋁
                  
                  
                    μ
                    ,
                    
                      M
                      -
                      1
                    
                    ,
                    
                      M
                      -
                      1
                    
                  
                
              
            
          
          ]
        
      
    
    
      
        (
        45
        )
      
    
  




MS-BS accomplished by spreading matrix DuB, which is formed by symbol-spreading followed by frame-interleaving, and spreading matrix CuA, which is formed by symbol-spreading followed by chip-interleaving and zero padding convert the conventional multi-user detection problem into an equivalent set of single user equalization problems. Similar to multi-path channels with CIBS transmissions, MS-BS cause ISI with each symbol block, but does not cause ICI within the code vector, i.e. ICI is replaced by ISI. Zero padding in the second block-spreading stage eliminates ICI and maintains the orthogonality among the MU and TH spreading stages.

Further, the mutli-user separating front end of receiver 14, i.e. TH and MU de-spreading units 42 and 44 respectively, preserve the maximum-likelihood (ML) optimality. This is shown through equations (46-48) given below.

{hacek over (G)}:=(IM{hacek over (C)}uA)(IM{hacek over (D)}uB) where {hacek over (G)}:=[{hacek over (G)}0, {hacek over (G)}1, . . . , {hacek over (G)}Nf−1]  (46)

{hacek over (G)}H{hacek over (G)}=NfIM(K+L)  (47)





  
    
      
        
          Pr
          [
          
            
              x
              ⁡
              
                (
                i
                )
              
            
            |
            
              
                {
                
                  
                    s
                    u
                  
                  ⁡
                  
                    (
                    i
                    )
                  
                
                }
              
              
                u
                =
                0
              
              
                
                  N
                  u
                
                -
                1
              
            
          
          ]
        
        =
        
          
            ∏
            
              u
              =
              0
            
            
              
                N
                u
              
              -
              1
            
          
          ⁢
          
            
          
          ⁢
          
            Pr
            ⁡
            
              [
              
                
                  
                    y
                    u
                  
                  ⁡
                  
                    (
                    i
                    )
                  
                
                |
                
                  
                    s
                    u
                  
                  ⁡
                  
                    (
                    i
                    )
                  
                
              
              ]
            
          
        
      
    
    
      
        (
        48
        )
      
    
  




Equation (47) implies that if η(i) is white, then η′(i) remains white and the probability of receiving x(i), where x(i):=[x0T(i), x1T(i), . . . , xM−1T(i)]T, given that su(i) is transmitted for each user equals the product of the probabilities of generating yu(i) given that that su(i) is transmitted. In other words, de-spreading matrices {hacek over (C)}uA and {hacek over (D)}uB reduce a multi-user detection problem, which operates on MUI and ISI in the presence of frequency selective channels, to an equivalent set of single user equalization problems without loss of ML optimality. As a result, if the Nu single user ISI problems in equation (44) are demodulated in the ML sense using for example, Viterbi's decoding, then computationally demanding multi-user detection is not needed when spreading and despreading matrices, DuB, CuA and {hacek over (C)}uA, {hacek over (D)}uB, are chosen according to equations (10, 15, 29, 30) respectively.

Single-user detector 46 removes channel effects from output blocks 45 and generates symbol block estimates given in equation (44). For example, linear equalizer Γμ outputs symbol block estimates in equation (44) according to equation (49).

ŝμ(i)=Γμyμ(i) where ŝμ(i):=[ŝTμ,0(i), ŝTμ,1(i), . . . , ŝTμ,M−1(i)]T  (49)

Single-user detector 46 performs symbol detection on soft estimates given by equation (49) and outputs the μth user's K×1 symbol block estimate 49 given by equation (50) according to decisions made by equation (51).

{hacek over (I)}μ:=[{hacek over (I)}μ(iK), {hacek over (I)}μ(iK+1), . . . , {hacek over (I)}μ(iK+K−1)]T  (50)





  
    
      
        
          
            
              
                
                  I
                  ⋁
                
                μ
              
              ⁡
              
                (
                
                  
                    i
                    ⁢
                    
                      
                    
                    ⁢
                    K
                  
                  +
                  k
                
                )
              
            
            =
            
              arg
              ⁢
              
                
              
              ⁢
              
                
                  max
                  m
                
                ⁢
                
                  {
                  
                    
                      
                        s
                        ^
                      
                      
                        μ
                        ,
                        m
                      
                    
                    ⁡
                    
                      (
                      
                        
                          i
                          ⁢
                          
                            
                          
                          ⁢
                          K
                        
                        +
                        k
                      
                      )
                    
                  
                  }
                
              
            
          
          ,
          
            
              for
              ⁢
              
                
              
              ⁢
              all
              ⁢
              
                
              
              ⁢
              m
            
            ∈
            
              [
              
                0
                ,
                
                  M
                  -
                  1
                
              
              ]
            
          
        
        ⁢
        
          

        
        ⁢
        
          
            and
            ⁢
            
              
            
            ⁢
            k
          
          ∈
          
            [
            
              0
              ,
              
                K
                -
                1
              
            
            ]
          
        
      
    
    
      
        (
        51
        )
      
    
  




Trading off performance for complexity, any other detector may replace the maximum likelihood (ML) Viterbi equalizer, given in equation (44), typically used in multiple user detection. The complexity of ML sequence estimation (MLSE) for M-ary PPM modulation is O(KMLu) per symbol block of size K. Consequently, the per-symbol decoding complexity is O(MLu) regardless of the block size K and the maximum channel order. Depending on how Γμ is selected, the linear receivers including a matched filter (MF) receiver, zero-forcing (ZF) receiver, and minimum mean-square error (MMSE) receiver are given in equations (52-54) respectively.

ΓμMF:=ĤμH/Nf  (52)

γμZF:=(ĤμHĤμ)−1ĤμH/Nf  (53)

ΓμMMSE:=NfRμĤμH[Rη′+(Nf)2ĤμĤμH]−1  (54)

Equation 54 can be expanded using substitutions according to equations (55, 56).

Rμ:=E{sμ(i)sHμ(i)}  (55)

R{acute over (η)}:=E{{acute over (η)}(i){acute over (η)}H(i)}  (56)

In this manner, the techniques allow transceivers to be configured with receivers in favor of low complexity or high performance.

FIG. 4 illustrates an example Nc×Nf matrix 50 for assigning the address {uA, uB} to the uth user with Nc=4 and Nf=8 of system 10. In order to facilitate separation of multiple users over a multi-path communication channel each user is assigned a TH address and a user-signature pattern that will herein be referred to as a (multi-user) MU address corresponding to a TH spreading code and an orthogonal spreading code respectively. Because communication system 10 uses an M-ary PPM-IRMA format, identical information bearing symbols are transmitted over Nf frames. Consequently, each symbol can be viewed as being encoded with a repetition code. Replacing the repetition code with an orthogonal spreading code specified by a MU address enables Nu users to be uniquely identified. The number of users that can be uniquely identified in an M-ary PPM-IRMA format communication system is given in equation (57).

Nu=NcNf  (57)

Matrix 50, therefore, illustrates TH and MU address assignments for a fully loaded system with 32 users. Each user is assigned a TH address vector of length Pc=Nf according to equation (58).

ĊuA:=[cuA(0), . . . , cuA(Nc−1)]T, cuA(n)ε[0, Pċ−1]  (58)

For any two users, u and μ, ċuA(n):≠ċμA(n), ∀nε[0, Pċ−1]. The number of TH address vectors can at most be Nc, i.e. the number of chips in a frame. If the number of active users, Nu, is less than Nc then Nu of the Nc TH address vectors can be uniquely assigned to the Nu users. TH spreading codes are specified by a TH address, e.g. the uAth, and defined according to equation (59) with cuA(n) as defined in equation (6).

cuA:=[cuA(0), cuA(1), . . . , cuA(Pc−1)]T, cuA(n)ε[0,1]  (59)

These TH spreading codes are mutually orthogonal, i.e. cuAHcμA=Nfδ(uA−μA), ∀uA,μAε[0,Nc−1]. Replacing the repetition code with a set of spreading codes orthogonal to the set of orthogonal TH spreading codes allows a group of users with identical TH spreading codes to be uniquely identified. MU spreading codes given by a specific MU address, e.g. the uBth, can be expressed as given in equation (60).

duB:=[duB(0), . . . , duB(Nf−1)]T, duB(n)ε[1,−1]  (60)

MU spreading codes are also designed to be mutually orthogonal. Equation (60) is designed such that duBMdμB=Nfδ(uB−μB), ∀uB,μBε[0,Nf−1]. The repetition encoding of a standard IRMA system can be achieved by setting duB=[1,1, . . . 1].
If the number of Nu users satisfies Nu≦:NcNf, then a given TH address is assigned to a group of └Nu/Nc┘ or ┌Nu/Nc┐ users. An additional set of MU addresses are assigned to be able to resolve users in the same group by employing a unique mapping to each of the └Nu/Nc┘ or ┌Nu/Nc┐ users in the same group. As a result, the same MU address can be assigned to several users that belong to different groups since groups are differentiated via their TH address. For example, the uth user may be assigned TH address and MU address with index given by its {uA, uB} pair according to equations (61, 62) respectively.

uA=u(mod Nc)  (61)

uB=└u/Nc┘, uε┌0, NcNf−1┐  (62)

FIG. 5 is a block diagram that illustrates an example transmission of a M-ary PPM-IRMA signal of the uth user's information bearing symbols during the nth chip duration in an IRMA system 60. The uth user's transmitted symbol during the nth chip duration is Iu(└n/NcNf┘) 61. The orthogonal M-ary PPM of the uth user in FIG. 1 can be viewed as having M parallel branches 62 with each parallel branch realizing a shifted version of the pulse stream. However, one branch out of the M parallel branches can be sufficiently selected depending on the symbol value.
The information stream, and thus su,m(└n/(NcNf)┘) 63, does not change over the duration of NfNc chips (NfTf seconds) and is spread by TH chip-rate sequence 5 as defined in equation (6) to generate chip sequence 64 in equation (7). From this chip-rate sampled model, the nonlinearly modulated PPM-IRMA format can be viewed as a linearly modulated multiple access format such as CDMA, TDMA, or FDMA. The chip-rate sampled signal 64 is pulse shaped and converted to an analog signal 68 by functions 66. The sum of the M branches of the nonlinearly modulated PPM-IRMA signal are summed together to form signal 69.
FIG. 6 illustrates the multi-user block-spreading stage with MU address matrices DuB as given in equation (10). Data stream 24 is generated from data stream 22 by multi-user block-spreading unit 23 within transmitter 12 of FIG. 3. Data stream 22 represents the data stream on the mth branch of the uth user with blocks of symbols of length K. Multi-user block-spreading unit 23 applies Q×K block-spreading matrix DuB to obtain data stream 24 given by the Q×1 output vectors in equation (9). Multi-user block-spreading unit 23 can be viewed as first symbol-spreading each of the K symbols into Q frame-rate blocks followed by frame-interleaving the Q frame-rate blocks.
FIG. 7 illustrates a sub-block of the TH block-spreading stage with TH address sub-matrix CuA(0) as given in equation (14). Data stream 26 is generated from data stream 24 by TH block-spreading unit 25 within transmitter 12 of FIG. 3. Data stream 26 represents the single block to be transmitted on the mth branch of the uth user and is given by equation (16). Each block of Q frames is spread into P chips with L zeros padded between blocks of P chips. TH spreading unit 25 can be viewed as first symbol-spreading frame-rate blocks into P chips followed by chip-interleaving and zero padding.
FIG. 8 is a flowchart illustrating an example mode of operation of a transmitter 12 in communication system 10 in which MS-BS preserves the orthogonality of transmitted waveforms through communication channel 16 thereby deterministically eliminating MUI 18 at receiver 14. Generally, transmitter 12 parses an outbound serial data stream into blocks of K symbols (70) and subsequently applies Q×K MU block-spreading matrix DuB (71) corresponding to the specified user's assigned MU address. This spreads blocks of K symbols into Q frames (72) and interleaves the frames for the K symbols (73).
TH spreading matrix CuA of size P×Q is applied (74) according to the specified use's assigned TH address. TH spreading matrix CuA spreads blocks of Q frames into blocks of P chips (75) and interleaves the chips for the Q frames (76). Zeros are padded between each block of P chips (77). The chips that are generated from the same block of symbols are, therefore, temporally spaced and zero padded. In this manner, each block of K symbols produces NfNc(K+L) interleaved chips, where L represents the number of zeros, Nf represents the number of frames over which an identical information bearing symbol is repeated, and Nc represents the number of chips per frame. Transmitter 12 converts the interleaved multi-stage block-spread chips into a serial bit stream (78) and generates a transmission waveform for carrying the data through communication channel 16 to receiver 14 (79).
FIG. 9 is a flowchart illustrating an example mode of operation of a receiver 14 in communication system 10. Receiver 14 serial to parallel converts the received chip-rate sampled sequence P×1 blocks (80). TH de-spreading matrix {hacek over (C)}uA of size P×Nf(K+L) is applied to the P×1 blocks (81) reading subsets of Nf(K+L) chips, each subset having P chips that were generated from the same symbol, thereby de-interleaving the chips (82). The de-interleaved chips are then de-spread into blocks of frames (83) to which MU de-spreading matrix {hacek over (D)}uB of size Nf(K+L)×(K+L) is applied (84). K+L subsets of the stored frames, each subset having NfK frames that were generated from the same block of symbols are de-interleaved (85) and de-spread into blocks symbols (86). Receiver 12 then applies a single user detector to eliminate channel effects and output symbols based on the soft estimates (87).
FIGS. 10 and 11 are graphs illustrating the BER performance of a matched filter (MF), RAKE, receiver of a conventional IRMA system against the MS-BS IMRA technique in the presence of frequency selective channels. A filter matched to the desired user's TH code and the number of users is confined to Nu≦Nc in the conventional IRMA system. For both systems, parameters are adjusted to avoid ISI and symbol by symbol reception is performed at the receiver.
FIG. 10 illustrates BER performance of the conventional IRMA system with one, two, three, and four users compared to an MS-BS IRMA system with the active number of users in the range of 1≦Nu≦32 in an uplink scenario with perfect power control, i.e. Pu for all users. In particular, FIG. 10 illustrates how the BER performance of a conventional IRMA system degrades as the number of users increases while the BER performance of the MS-BS IRMA system remains invariant as the number of active users changes in the specified range.
FIG. 11 illustrates BER performance of the conventional IRMA system compared to an MS-BS IRMA system in an uplink scenario with two active users, user 1 being the desired user, and the effective transmission power of user 2 twice that of user 1. In particular, FIG. 11 illustrates that the imperfect power control has no effect on the BER performance of the MS-BS IRMA system while the conventional IRMA system encounters degradation in BER performance.
FIGS. 12 and 13 illustrate the BER performance over 1,000 channel realizations of the MS-BS IMRA technique compared to the MUD IRMA technique, which is applies only to the downlink scenario. FIG. 12 illustrates the MS-BS IMRA technique compared to the MUD IRMA technique with a zero-forcing (ZF) linear receiver. FIG. 13 illustrates the MS-BS IMRA technique compared to the MUD IRMA technique with a minimum mean-square error (MMSE) linear receiver.
Various embodiments of the invention have been described. The described techniques may provide advantages in multi-user communication systems. Conventional IRMA systems approximate MUI as Gaussian noise and use TH codes with strict power control to statistically suppress MUI. Applying a first and a second block-spreading code selected from a first and a second set of mutually orthogonal block-spreading codes in which the first and the second set of mutually orthogonal block-spreading codes are also orthogonal preserves the orthogonality of transmitted waveforms through frequency selective communications. As a result, MUI and ISI can be eliminated deterministically. Such systems allow each user to use a different detector that can be chosen in favor for low complexity or high performance without interfering with other users.
“Multi-stage block-spreading” may use a first set of mutually orthogonal MU spreading codes, e.g. direct sequence CDMA codes or digital carrier frequency multiple access codes, and a second set of mutually orthogonal TH codes. The number of orthogonal mutually orthogonal MU spreading codes and TH spreading codes may be equal to the number of frames over which identical information bearing symbols, Nf, are transmitted and the number of chips per frame, Nc, respectively. As a result, a group of users may be assigned the same TH code with each user in the group uniquely identified by a different MU code. The maximum number of uniquely identified users in a MS-BS IRMA system is, therefore, NcNf, with each user identified by a MU address and TH address corresponding to a specific MU and TH code respectively.
Further, such systems do not exhibit BER degradation as the number of users increases and requires no additional power to achieve a specified BER regardless of the multi-path channel. Different users may also be provided with variable transmission rates by assigning a single user more than one set of MU and TH addresses.
The described techniques can be embodied in a variety of devices that communicate using ultra wideband communication, including base stations, mobile phones, laptop computers, handheld computing devices, personal digital assistants (PDA's), a device within a personal area network, a device within a sensor network, and the like. The devices may include a digital signal processor (DSP), field programmable gate array (FPGA), application specific integrated circuit (ASIC) or similar hardware, firmware and/or software for implementing the techniques. If implemented in software, a computer-readable medium may store computer readable instructions, i.e., program code, that can be executed by a processor or DSP to carry out one of more of the techniques described above. For example, the computer-readable medium may comprise random access memory (RAM), read-only memory (ROM), non-volatile random access memory (NVRAM), electrically erasable programmable read-only memory (EEPROM), flash memory, or the like. The computer-readable medium may comprise computer readable instructions that when executed in a wireless communication device, cause the wireless communication device to carry out one or more of the techniques described herein. These and other embodiments are within the scope of the following claims.

## Claims

1. A method comprising:
generating a stream of frames from blocks of information bearing symbols by applying an orthogonal set of spreading codes to the block of information bearing symbols to form frames and interleaving the frames corresponding to different block of information bearing symbols to form the stream of frames;
generating a stream of chips from the stream of frames by applying an orthogonal set of time-hopping spreading codes to the stream of frames to form chips and interleaving the chips corresponding to different frames to form the stream of chips; and
outputting an ultra wideband (UWB) transmission signal from the stream of chips.

2. The method of claim 1, wherein applying an orthogonal set of spreading codes comprises applying direct sequence code-division multiple access codes or digital carrier frequency division multiple access codes.

3. The method of claim 1, wherein generating a stream of chips further comprises:
storing the chips in an array having M columns and K+L rows, where L is a function of a communication channel length; and
padding each column of the array with L guard chips.

4. The method of claim 3, wherein the L guard chips comprise null values.

5. The method of claim 3, wherein outputting the UWB transmission signal comprises by reading the chips from the array in column-wise fashion.

6. The method of claim 3, wherein the set of spreading codes and the set of time-hopping spreading codes are mutually orthogonal so that the interleaved and padded chips retain their orthogonality after passing through a multi-path communication channel.

7. The method of claim 3, further comprising:
assigning each of the set of spreading codes to a different user of a group of users; and
assigning each user of the group a common one of the set of time-hopping spreading codes.

8. The method of claim 3, further comprising assigning unique addresses to users as unique pair-wise combinations of the set of orthogonal spreading codes and the set of time hopping spreading codes.

9. The method of claim 8, wherein the total number of users Nu supported by the wireless communication devices equals Nc*Nf, where each of the information bearing symbols is repeated over Nf frames and each frame includes Nc chips, wherein Nf and Nc are integers.

10. The method of claim 9, wherein each of the unique addresses comprises a unique multiple user address (uB) selected from set of spreading codes in combination with a unique time-hopping address (uA) selected from the set of time-hopping codes.

11. The method of claim 10, further comprising selecting the unique multiple addresses and the unique time-hopping addresses in accordance with:


uA=u(mod NC), and



uB=└u/Nc┘, wherein u ε[0, NcNf−1].

12. The method of claim 1, further comprising:
receiving the UWB transmission signal; and
outputting a stream of estimate symbols from the signal using a two-stage de-spreading unit having a time-hopping de-spreading module and a multi-user de-spreading module.

13. The method of claim 12, wherein outputting a stream of estimate symbols comprise:
converting the UWB transmission signal to a stream of chips;
applying a first de-spreading matrix with the time-hopping dc-spreading module to de-interleave the chips into blocks of frames;
applying a second dc-spreading matrix to the blocks of frames with the multi-user de-spreading module to de-interleave the frames and produce blocks of estimate symbols; and
applying a single user detection scheme to the blocks of estimate symbols to output the stream of estimate symbols.

14. The method of claim 13, wherein applying first and second de-spreading matrices deterministically eliminates multiple user interference.

15. The method of claim 13, wherein applying a first de-spreading matrix comprises:
parsing the chips into blocks of P chips; and
applying a time-hopping de-spreading matrix of size P×Nf(K+L) to the blocks, where each of the information bearing symbols is repeated over Nf frames, L is a function of the communication channel length, and the stream of frames was generated during transmission using blocks of K symbols.

16. The method of claim 13, wherein applying a second de-spreading matrix comprises applying a second de-spreading matrix of size Nf(K+L)×(K+L) matrix, where each of the information bearing symbols is repeated over Nf frames, L is a function of the communication channel length, and the stream of frames was generated during transmission using blocks of K symbols.

17. A wireless communication device comprising:
a multiple-user block-spreading unit that generates a set of frames for respective blocks of information bearing symbols by applying an orthogonal set of spreading codes to the block of information symbols and produces a stream of frames in which the frames from different sets are interleaved;
a time-hopping block-spreading unit that generates a set of chips for each frame by applying an orthogonal set of time-hopping spreading codes to the stream of frames and outputs a stream of chips in which the chips generated from different frames are interleaved; and
a pulse shaping unit to output an ultra wideband (UWB) transmission signal from the stream of chips.

18. The wireless communication device of claim 17, wherein the set of spreading codes comprises direct sequence code-division multiple access codes.

19. The wireless communication device of claim 17,
wherein the time-hopping block spreading unit comprises memory to store the chips in an array having columns and rows, where the number of rows in the array is a function of a communication channel length, and
wherein the time-hopping block spreading unit pads each column of the array with guard chips, and outputs the transmission signal by reading the chips from the array in column-wise fashion.

20. The wireless communication device of claim 19, wherein the set of spreading codes and the set of time-hopping spreading codes are mutually orthogonal so that the interleaved and padded chips retain their orthogonality after passing through a multi-path communication channel.

21. The wireless communication device of claim 20, wherein the wireless communication device stores a unique address assigned to one of a plurality of users, and the unique address is formed from a pair-wise combination of one of the set of orthogonal spreading codes and one of the set of time hopping spreading codes.

22. The wireless communication device of claim 17, wherein the wireless communication device comprises one of a base station and a mobile device, a device within a personal area network, or a device within a sensor network.

23. A wireless communication device comprising a two-stage despreading unit that processes a received ultra wideband (UWB) transmission signal to produce estimate symbols, wherein the received UWB signal comprises a multi-user block-spread UWB signal formed from interleaved symbol frames and interleaved chips within the symbol frames, and wherein the two-stage despreading unit comprises:
a time-hopping de-spreading module that applies a first de-spreading matrix to de-interleave the chips into blocks of frames; and
a multi-user de-spreading module that applies a second de-spreading matrix to de-interleave the frames and produce blocks of estimate symbols.

24. The wireless communication device of claim 23, wherein the wireless communication device comprises one of a base station and a mobile device.

25. A system comprising:
a wireless transmitter to transmit an ultra wideband (UWB) signal according to interleaved chips generated from interleaved frames produced by blocks of information bearing symbols, wherein the transmitter comprises:
a multiple-user block-spreading unit that generates a set of frames for respective blocks of information bearing symbols by applying an orthogonal set of spreading codes to the block of information bearing symbols and produces a stream of frames in which the frames from different sets are interleaved;
a time-hopping block-spreading unit that generates a set of chips for each of the frames by applying an orthogonal set of time-hopping spreading codes to the interleaved frames and outputs a stream of chips in which the chips generated from different frames are interleaved; and
a pulse shaping unit to output the UWB transmission signal from the stream of interleaved chips; and

a wireless receiver to receive the UWB signal and de-interleave the chips and frames to produce estimate symbols.

26. A system comprising:
a wireless transmitter to transmit an ultra wideband (UWB) signal according to interleaved chips generated from interleaved frames produced by blocks of information bearing symbols; and
a wireless receiver to receive the UWB signal and dc-interleave the chips and frames to produce estimate symbols, wherein the receiver comprises:
a time-hopping de-spreading module that applies a first de-spreading matrix to the UWB signal to de-interleave chips into blocks of frames; and
a multi-user de-spreading module that applies a second de-spreading matrix to de-interleave the frames and produce blocks of estimate symbols.

27. A computer-readable medium comprising instructions to cause a programmable processor of a wireless communication device to:
generate a stream of frames from blocks of information bearing symbols by applying an orthogonal set of spreading codes to the block of information bearing symbols to form the frames and interleaving the frames corresponding to different block of information bearing symbols to form frames;
generate a stream of chips from the stream of frames by applying an orthogonal set of time-hopping spreading codes to the stream of frames to form chips and interleaving the chips corresponding to different frames to form the stream of chips; and
output an ultra wideband (UWB) transmission signal from the stream of chips.