Wireless communications systems and methods for direct memory access and buffering of digital signals for multiple user detection

[0001] This application claims the benefit of priority of (i) U.S. Provisional Application Ser. No. 60/275,846 filed Mar. 14, 2001, entitled “Improved Wireless Communications Systems and Methods”; (ii) U.S. Provisional Application Ser. No. 60/289,600 filed May 7, 2001, entitled “Improved Wireless Communications Systems and Methods Using Long-Code Multi-User Detection” and (iii) U.S. Provisional Application Ser. No. 60/295,060 filed Jun. 1, 2001 entitled “Improved Wireless Communications Systems and Methods for a Communications Computer,” the teachings all of which are incorporated herein by reference.

[0002] The invention pertains to wireless communications and, more particularly, by way of example, to methods and apparatus providing multiple user detection for use in code division multiple access (CDMA) communications. The invention has application, by way of non-limiting example, in improving the capacity of cellular phone base stations.

[0003] Code-division multiple access (CDMA) is used increasingly in wireless communications. It is a form of multiplexing communications, e.g., between cellular phones and base stations, based on distinct digital codes in the communication signals. This can be contrasted with other wireless protocols, such as frequency-division multiple access and time-division multiple access, in which multiplexing is based on the use of orthogonal frequency bands and orthogonal time-slots, respectively.

[0004] A limiting factor in CDMA communication and, particularly, in so-called direct sequence CDMA (DS-CDMA), is interference—both that wrought on individual transmissions by buildings and other “environmental” factors, as well that between multiple simultaneous communications, e.g., multiple cellular phone users in the same geographic area using their phones at the same time. The latter is referred to as multiple access interference (MAI). Along with environmental interference, it has effect of limiting the capacity of cellular phone base stations, driving service quality below acceptable levels when there are too many users.

[0005] A technique known as multi-user detection (MUD) is intended to reduce multiple access interference and, as a consequence, increases base station capacity. It can reduce interference not only between multiple transmissions of like strength, but also that caused by users so close to the base station as to otherwise overpower signals from other users (the so-called near/far problem). MUD generally functions on the principle that signals from multiple simultaneous users can be jointly used to improve detection of the signal from any single user. Many forms of MUD are discussed in the literature; surveys are provided in Moshavi, “Multi-User Detection for DS-CDMA Systems,” IEEE Communications Magazine (October, 1996) and Duel-Hallen et al, “Multiuser Detection for CDMA Systems,” IEEE Personal Communications (April 1995). Though a promising solution to increasing the capacity of cellular phone base stations, MUD techniques are typically so computationally intensive as to limit practical application.

[0006] An object of this invention is to provide improved methods and apparatus for wireless communications. A related object is to provide such methods and apparatus for multi-user detection or interference cancellation in code-division multiple access communications.

[0007] A further related object is to provide such methods and apparatus as provide improved short-code and/or long-code CDMA communications.

[0008] A further object of the invention is to provide such methods and apparatus as can be cost-effectively implemented and as require minimal changes in existing wireless communications infrastructure.

[0009] A still further object of the invention is to provide methods and apparatus for executing multi-user detection and related algorithms in real-time.

[0010] A still further object of the invention is to provide such methods and apparatus as manage faults for high-availability.

[0011] The foregoing and other objects are among those attained by the invention which provides methods and apparatus for multiple user detection (MUD) processing. These have application, for example, in improving the capacity CDMA and other wireless base stations

[0012] Wireless Communications Systems and Methods for Multiple Processor Based Multiple User Detection

[0013] One aspect of the invention provides a multiuser communications device for detecting user transmitted symbols in CDMA short-code spread spectrum waveforms. A first processing element generates a matrix (hereinafter, “gamma matrix”) that represents a correlation between a short-code associated with one user and those associated with one or more other users. A set of second processing elements generates, e.g., from the gamma matrix, a matrix (hereinafter, “R-matrix”) that represents cross-correlations among user waveforms based on their amplitudes and time lags. A third processing element produces estimates of the user transmitted symbols as a function of the R-matrix.

[0014] In related aspects, the invention provides a multiuser communications device in which a host controller performs a “partitioning function,” assigning to each second processing element within the aforementioned set a portion of the R-matrix to generate. This partitioning can be a function of the number of users and the number of processing elements available in the set. According to related aspects of the invention, as users are added or removed from the spread spectrum system, the host controller performs further partitioning, assigning each second processing element within the set a new portion of the R-matrix to generate.

[0015] Further related aspects of the invention provide a multiuser communications device as described above in which the host controller is coupled to the processing elements by way of a multi-port data switch. Still further related aspects of the invention provide such a device in which the first processing element transfers the gamma-matrix to the set of second processing elements via a memory element.

[0016] Similarly, the set of second processing elements place the respective portions of the R-matrix in memory accessible to the third processing element via the data switch. Further related aspects of the invention provide devices as described above in which the host controller effects data flow synchronization between the first processing element and the set of second processing elements, as well as between the set of second processing elements and the third processing element.

[0017] Wireless Communications Systems and Methods for Contiguously Addressable Memory Enabled Multiple Processor Based Multiple User Detection

[0018] Another aspect of the invention provides a multiuser communications device for detecting user transmitted symbols in CDMA short-code spread spectrum waveforms in which a set of first processing elements generates a matrix (hereinafter the “R-matrix”) that represents cross-correlations among user waveforms based on their amplitudes and time lags. The first processing elements store that matrix to contiguous locations of an associated memory.

[0019] Further aspects of the invention provide a device as described above in which a second processing element, which accesses the contiguously stored R-matrix, generates estimates of the user transmitted symbols.

[0020] Still further aspects of the invention provide such a device in which a third processing element generates a further matrix (hereinafter, “gamma-matrix”) that represents a correlation between a CDMA short-code associated with one user and those associated with one or more other users; this gamma-matrix used by the set of first processing elements in generating the R-matrix. In related aspects, the invention provides such a device in which the third processing element stores the gamma-matrix to contiguous locations of a further memory.

[0021] In other aspects, the invention provides a multiuser device as described above in which a host controller performs a “partitioning function” of the type described above that assigning to each processing element within the set a portion of the R-matrix to generate. Still further aspects provide such a device in which the host controller is coupled to the processing elements by way of a multi-port data switch.

[0022] Other aspects of the invention provide such a device in which the third processing element transfers the gamma-matrix to the set of first processing elements via a memory element.

[0023] Further aspects of the invention provide a multiuser communications device as described above with a direct memory access (DMA) engine that places elements of the R-matrix into the aforementioned contiguous memory locations.

[0024] Further aspects of the invention provide methods for operating a multiuser communications device paralleling the operations described above.

[0025] Wireless Communications Systems and Methods for Cache Enabled Multiple Processor Based Multiple User Detection

[0026] Other aspects of the invention provide a multiuser communications device that makes novel use of cache and random access memory for detecting user transmitted symbols in CDMA short-code spectrum waveforms. According to one such aspect, there is provided a processing element having a cache memory and a random access memory. A host controller places in the cache memory data representative of characteristics of the user waveforms. The processing element generates a matrix as a function of the data stored in the cache, and stores the matrix in either the cache or the random access memory.

[0027] Further aspects of the invention provide a device as described above in which the host controller stores in cache data representative of the user waveforms short-code sequences. The processing element generates the matrix as a function of that data, and stores the matrix in random access memory.

[0028] Still further aspects of the invention provide such a device in which the host controller stores in cache data representative of a correlation of time-lags between the user waveforms and data representative of a correlation of complex amplitudes of the user waveforms. The host controller further stores in random access memory data representing a correlation of short-code sequences for the users waveforms. The processing element generates the matrix as a function of the data and stores that matrix in RAM.

[0029] Further aspects of the invention provide a device as described above in which a host controller stores in cache an attribute representative of a user waveform, and stores in random access memory an attributes representing a cross-correlation among user waveforms based on time-lags and complex amplitudes. The processing element generates estimates of user transmitted symbols and stores those symbols in random access memory.

[0030] Other aspects of the invention provide such a device in which the host controller transmits the matrix stored in the cache or random access memory of a processing element to the cache or random access memory of a further processing element.

[0031] Further aspects of the invention provide a multiuser communications device as described above with a multi-port data switch coupled to a short-code waveform receiver system and also coupled to a host controller. The host controller routes data generated by the receiver system to the processing element via the data switch.

[0032] Further aspects of the invention provide methods for operating a multiuser communications device paralleling the operations described above.

[0033] Wireless Communications Systems and Methods for Nonvolatile Storage Of Operating Parameters For Multiple Processor Based Multiple User Detection

[0034] Another aspect of the invention provides a multiuser communications device for detecting user transmitted symbols in CDMA short-code spectrum waveforms in which fault and configuration information is stored to a nonvolatile memory. A processing element, e.g. that performs symbol detection, is coupled with random access and nonvolatile memories. A fault monitor periodically polls the processing element to determine its operational status. If the processing element is non-operational, the fault monitor stores information including configuration and fault records, as well at least a portion of data from the processing element's RAM, into the nonvolatile memory.

[0035] According to further aspects according to the invention, following detection of the non-operational status, the fault monitor sends to a host controller a reset-request interrupt together with the information stored in the nonvolatile RAM. In turn, the host controller selectively issues a reset command to the processing element. In related aspects, the processing element resets in response to the reset command and transfers (or copies) the data from the nonvolatile memory into the RAM, and therefrom continues processing the data in the normal course.

[0036] Further aspects of the invention provide a device as described above in which the processing element periodically signals the fault monitor and, in response, the fault monitor polls the processing element. If the fault monitor does not receive such signaling within a specified time period, it sets the operational status of the processing element to non-operational.

[0037] According to a related aspect of the invention, the fault monitor places the processing elements in a non-operational status while performing a reset. The fault monitor waits a time period to allow for normal resetting and subsequently polls the processor to determine its operational status.

[0038] Still further aspects of the invention provide a device as described above in which there are a plurality of processing elements, each with a respective fault monitor.

[0039] Yet still further related aspects of the invention provide for the fault monitoring a data bus coupled with the processing element.

[0040] Further aspects of the invention provide methods for operating a multiuser communications device paralleling the operations described above.

[0041] Wireless Communications Systems and Methods for Multiple Operating System Multiple User Detection

[0042] Another aspect of the invention provides a multiuser communications device for detecting user transmitted symbols in CDMA short-code spectrum waveforms in which a first process operating under a first operating system executes a first set of communication tasks for detecting the user transmitted symbols and a second process operating under a second operating system—that differs from the first operating system—executes a second set of tasks for like purpose. A protocol translator translates communications between the processes. According to one aspect of the invention, the first process generates instructions that determine how the translator performs such translation.

[0043] According to another aspect of the invention, the first process sends a set of instructions to the second process via the protocol translator. Those instructions define the set of tasks executed by the second process.

[0044] In a related aspect of the invention, the first process sends to the second process instructions for generating a matrix. That can be, for example, a matrix representing any of a correlation of short-code sequences for the user waveforms, a cross-correlation of the user waveforms based on time-lags and complex amplitudes, and estimates of user transmitted symbols embedded in the user waveforms.

[0045] Further aspects of the invention provide a device as described above in which the first process configures the second process, e.g., via data sent through the protocol translator. This can include, for example, sending a configuration map that defines where a matrix (or portion thereof) generated by the second process is stored or otherwise directed.

[0046] Still further aspects of the invention provide a device as described above in which the first process is coupled to a plurality of second processes via the protocol translator. Each of the latter processes can be configured and programmed by the first process to generate a respective portion of a common matrix, e.g., of the type described above. Further aspects of the invention provide methods for operating a multiuser communications device paralleling the operations described above.

[0047] Wireless Communications Systems and Methods for Direct Memory Access and Buffering of Digital Signals for Multiple User Detection

[0048] Another aspect of the invention provides a multiuser communications device for detecting user transmitted symbols in CDMA short-code spectrum waveforms in which a programmable logic device (hereinafter “PLD”) enables direct memory access of data stored in a digital signal processor (hereinafter “DSP”). The DSP has a memory coupled with a DMA controller that is programmed via a host port. The PLD programs the DMA controller via the host port to allow a buffer direct access to the memory.

[0049] In a related aspect according to the invention, the PLD programs the DMA controller to provide non-fragmented block mode data transfers to the buffer. From the buffer, the PLD moves the blocks to a data switch that is coupled to processing devices. In a further related aspects according to the invention, the PLD programs the DMA controller to provide fragmented block mode data transfers utilizing a protocol. The PLD provides the protocol which fragments and unfragments the blocks prior to moving them to the data switch.

[0050] In further aspects provided by a device as described above, the PLD is implemented as a field programmable gate array that is programmed by a host controller coupled with the data switch. In a related aspect, the PLD is implemented as a application specific integrated circuit which is programmed during manufacture. In still aspects, a device as described above provides for a buffer implemented as a set of registers, or as dual-ported random access memory.

[0051] Further aspects of the invention provide methods for operating a multiuser communications device paralleling the operations described above.

[0052] Improved Wireless Communications Systems and Methods for Short-code Multiple User Detection

[0053] Still further aspects of the invention provide methods for processing short code spread spectrum waveforms transmitted by one or more users including the step of generating a matrix indicative of cross correlations among the waveforms as a composition of (i) a first component that represents correlations among time lags and short codes associated with the waveforms transmitted by the users, and (ii) a second component that represents correlations among multipath signal amplitudes associated with the waveforms transmitted by the users. The method further includes generating detection statistics corresponding to the symbols as a function of the correlation matrix, and generating estimates of the symbols based on those detection statistics.

[0054] Related aspects of the invention provided methods as described above in which the first component is updated on a time scale that is commensurate with a rate of change of the time lags associated with the transmitted waveforms, and the second component is updated on a different time scale, i.e., one that is commensurate with a rate of change of the multipath amplitudes associated with these waveforms. In many embodiments, the updating of the second component, necessitated as a result of change in the multipath amplitudes, is executed on a shorter time scale than that of updating the first component.

[0055] Other aspects of the invention provide methods as described above in which the first component of the cross-correlation matrix is generated as a composition of a first matrix component that is indicative of correlations among the short codes associated with the respective users, and a second matrix component that is indicative of the waveforms transmitted by the users and the time lags associated with those waveforms.

[0056] In a related aspect, the invention provides methods as above in which the first matrix component is updated upon addition or removal of a user to the spread spectrum system. This first matrix component (referred to below as Γ-matrix) can be computed as a convolution of the short code sequence associated with each user with the short codes of other users.

[0057] According to further aspects of the invention, elements of the Γ-matrix are computed in accord with the relation:

[0058] ${\Gamma }_{\mathrm{lk}}\left[m\right]\equiv \frac{1}{2N_l}\sum _{n=0}^{N-1}{c}_l^{*}\left[n\right]·c_k\left[n-m\right]$

[0059] wherein

• • [0060] C*_l[n] represents the complex conjugate of a short code sequence associated with the l^th user,
  • [0061] C_k[n−m] represents a short code sequence associated with the k^th user,
  • [0062] N represents a length of the short code sequence, and
  • [0063] N_l represent a number of non-zero length of the short code sequence.

[0064] In further aspects, the invention provides a method as described above in which the first component of the cross-correlation matrix (referred to below as the C matrix) is obtained as a function of the aforementioned Γ-matrix in accord with the relation:

[0065] $C_{{\mathrm{lkqq}}^{\prime }}\left[m^{\prime }\right]=\sum _{m}g\left[{\mathrm{mN}}_c+\tau \right]·{\Gamma }_{\mathrm{lk}}\left[m\right]$

[0066] wherein

• • [0067] g is a pulse shape vector,
  • [0068] Nc is the number of samples per chip,
  • [0069] τ is a time lag, and
  • [0070] Γ represents the Γ matrix, e.g., defined above.

[0071] In a related aspect, the cross-correlation matrix (referred to below as the R-matrix) can be generated as a function of the C matrix in accord with the relation:

[0072] $r_{\mathrm{lk}}\left[m^{\prime }\right]=\sum _{q=1}^L\sum _{q^{\prime }=1}^L\mathrm{Re}\left\{{\hat{a}}_{\mathrm{lq}}^{*}{a}_{{\mathrm{kq}}^{\prime }}·C_{{\mathrm{lkqq}}^{\prime }}\left[m^{\prime }\right]\right\}=\mathrm{Re}\left\{a_l^H·C_{\mathrm{lk}}\left[m^{\prime }\right]·a_k\right\}$

[0073] wherein

• • [0074] â*_lq is an estimate of a*_lq the complex conjugate of one multipath amplitude component of the l^th user,
  • [0075] a_kq′ is one multipath amplitude component associated with the k^th user, and
  • [0076] C denotes the C matrix, e.g., as defined above.

[0077] In further aspects, the invention provides methods as described above in which the detection statistics are obtained as a function of the cross-correlation matrix (e.g., the R-matrix) in accord with the relation:

[0078] $y_l\left[m\right]=r_{\mathrm{ll}}\left[0\right]b_l\left[m\right]+\sum _{k=1}^{K_v}{r}_{\mathrm{lk}}\left[-1\right]b_k\left[m+1\right]+\sum _{k=1}^{K_v}\left[r_{\mathrm{lk}}\left[0\right]-r_{\mathrm{ll}}\left[0\right]{\delta }_{\mathrm{lk}}\right]b_k\left[m\right]+\sum _{k=1}^{K_v}{r}_{\mathrm{lk}}\left[1\right]b_k\left[m-1\right]+{\eta }_l\left[m\right]$

[0079] wherein

• • [0080] y_l[m] represents a detection statistic corresponding to m^th symbol transmitted by the l^th user,
  • [0081] r_ll[0]b_l[m] represents a signal of interest, and
  • [0082] remaining terms of the relation represent Multiple Access Interference (MAI) and noise.

[0083] In a related aspect, the invention provides methods as described above in which estimates of the symbols transmitted by the users and encoded in the short code spread spectrum waveforms are obtained based on the computed detection statistics by utilizing, for example, a multi-stage decision-feedback interference cancellation (MDFIC) method. Such a method can provide estimates of the symbols, for example, in accord with the relation:

[0084] ${\hat{b}}_l\left[m\right]=\mathrm{sign}\left\{y_l\left[m\right]-\sum _{k=1}^{K_v}{r}_{\mathrm{lk}}\left[-1\right]{\hat{b}}_k\left[m+1\right]-\sum _{k=1}^{K_v}\left[r_{\mathrm{lk}}\left[0\right]-r_{\mathrm{ll}}\left[0\right]{\delta }_{\mathrm{lk}}\right]{\hat{b}}_k\left[m\right]-\sum _{k=1}^{K_v}{r}_{\mathrm{lk}}\left[1\right]{\hat{b}}_k\left[m-1\right]\right\}$

[0085] wherein

• • [0086] {circumflex over (b)}_l[m] represents an estimate of the m^th symbol transmitted by the l^th user.

[0087] Further aspects of the invention provide logic carrying out operations paralleling the methods described above.

[0088] Load Balancing Computational Methods in a Short-code Spread-spectrum Communications System

[0089] In further aspects, the invention provides methods for computing the cross-correlation matrix described above by distributing among a plurality of logic units parallel tasks—each for computing a portion of the matrix. The distribution of tasks is preferably accomplished by partitioning the computation of the matrix such that the computational load is distributed substantially equally among the logic units.

[0090] In a related aspect, a metric is defined for each partition in accord with the relation below. The metric is utilized as a measure of the computational load associated with each logic unit to ensure that the computational load is distributed substantially equally among the logic units:
B_i=A_i−A_i−1

[0091] wherein

• • [0092] A_i represents an area of a portion of the cross-correlation matrix corresponding to the i^th partition, and
  • [0093] i represents an index corresponding to the number of logic units over which the computation is distributed.

[0094] In another aspect, the invention provides methods as described above in which the cross-correlation matrix is represented as a composition of a rectangular component and a triangular component. Each area, represented by A_l in the relation above, includes a first portion corresponding to the rectangular component and a second portion corresponding to the triangular component.

[0095] Further aspects of the invention provide logic carrying out operations paralleling the methods described above.

[0096] Hardware and Software for Performing Computations in a Short-code Spread-spectrum Communications System

[0097] In other aspects, the invention provides an apparatus for efficiently computing a Γ-matrix as described above, e.g., in hardware. The system includes two registers, one associated with each of l^th and k^th users. The registers hold elements of the short code sequences associated with the respective user such that alignment of the short code sequence loaded in one register can be shifted relative to that of the other register by m elements. Associated with each of the foregoing registers is one additional register storing mask sequences. Each element in those sequences is zero if a corresponding element of the short code sequence of the associated register is zero and, otherwise, is non-zero. The mask sequences loaded in these further registers are shifted relative to the other by m elements. A logic performs an arithmetic operation on the short code and mask sequences to generate, for m^th transmitted symbol, the (l, k) element of the Γ-matrix, i.e., Γ_lk[m]

[0098] In a related aspect, the invention provides an apparatus as described above in which the arithmetic operation performed by the logic unit includes, for any two aligned elements of the short code sequences of the l^th and k^th user and the corresponding elements of the mask sequences, (i) an XOR operation between the short code elements, (ii) an AND operation between the mask elements, (iii) an AND operation between results of the step (i) and step (ii). The result of step (iii) is a multiplier for the aligned elements, which the logic sums in order to generate the (l, k) element of the Γ-matrix.

[0099] Further aspects of the invention provide methods paralleling the operations described above.

[0100] Improved Computational Methods for Use in a Short-code Spread-spectrum Communications System

[0101] In still further aspects, the invention provides improved computational methods for calculating the aforesaid cross-correlation matrix by utilizing a symmetry property. Methods according to this aspect include computing a first one of two matrices that are related by a symmetry property, and calculating a second one of the two matrices as a function of the first component through application of the symmetry property.

[0102] According to related aspects of the invention, the symmetry property is defined in accord with the relation:
R_lk(m)=ξR_k,l(−m).

[0103] wherein

• • [0104] R_lk(m) and R_kl(m) refer to (l, k) and (k, l) elements of the cross-correlation matrix, respectively.

[0105] Further aspects of the invention provide methods as described above in which calculation of the cross-correlation matrix further includes determining a C matrix that represents correlations among time lags and short codes associated with the waveforms transmitted by the users, and an R-matrix that represents correlations among multipath signal amplitudes associated with the waveforms transmitted by the users. In related aspects the step of determining the C matrix includes generating a first of two C-matrix components related by a symmetry property. A second of the components is then generated by applying the symmetry property.

[0106] Related aspects of the invention provide a method as described above including the step of generating the Γ-matrix in accord with the relation:

[0107] ${\Gamma }_{\mathrm{lk}}\left[m\right]\equiv \frac{1}{2N_l}\sum _{n=0}^{N-1}{c}_l^{*}\left[n\right]·c_k\left[n-m\right]$

[0108] wherein

• • [0109] c*_l[n] represents complex conjugate of the short code sequence associated with the lth user,
  • [0110] C_k[n−m] represents the short code sequence associated with kth user,
  • [0111] N represents the length of the code, and
  • [0112] N_l represent the number of non-zero length of the code.

[0113] Further aspects of the invention provide logic carrying out operations paralleling the methods described above.

[0114] Wireless Communications Systems and Methods for Virtual User Based Multiple User Detection Utilizing Vector Processor Generated Mapped Cross-correlation Matrices

[0115] Still further aspects of the invention provide methods for detecting symbols encoded in physical user waveforms, e.g., those attributable to cellular phones, modems and other CDMA signal sources, by decomposing each of those waveforms into one or more respective virtual user waveforms. Each waveform of this latter type represents at least a portion of a symbol encoded in the respective physical user waveforms and, for example, can be deemed to “transmit” a single bit per symbol period. Methods according to this aspect of the invention determine cross-correlations among the virtual user waveforms as a function of one of more characteristics of the respective physical user waveforms. From those cross-correlations, the methods generate estimates of the symbols encoded in the physical user waveforms.

[0116] Related aspects of the invention provide methods as described above in which a physical user waveforms is decomposed into a virtual user waveform that represents one or more respective control or data bits of a symbol encoded in the respective physical user waveform.

[0117] Other related aspects provide for generating the cross-correlations in the form of a first matrix, e.g., an R-matrix for the virtual user waveforms. That matrix can, according to still further related aspects of the invention, be used to generate a second matrix representing cross-correlations of the physical user waveforms. This second matrix is generated, in part, as a function of a vector indicating the mapping of virtual user waveforms to physical user waveforms.

[0118] Further aspects of the invention provide a system for detecting symbols encoded in physical user waveforms that has multiple processors, e.g., each with an associated vector processor, that operates in accord with the foregoing methods to generate estimates of the symbols encoded in the physical user waveforms.

[0119] Still other aspects of the invention provide a system for detecting user transmitted symbols encoded in short-code spread spectrum waveforms that generates cross-correlations among the waveforms as a function of block-floating integer representations of one or more characteristics of those waveforms. Such a system, according to related aspects of the invention, utilizes a central processing unit to form floating-point representations of virtual user waveform characteristics into block-floating integer representations. A vector processor, according to further related aspects, generates the cross-correlations from the latter representations. The central processing unit can “reformat” the resulting block-floating point matrix into floating-point format, e.g., for use in generating symbol estimates.

[0120] Still further aspects of the invention provide methods and apparatus employing any and all combinations of the foregoing. These and other aspects of the invention, which includes combinations of the foregoing, are evident in the illustrations and in the text that follows.

[0140] Code-division multiple access (CDMA) waveforms or signals transmitted, e.g., from a user cellular phone, modem or other CDMA signal source, can become distorted by, and undergo amplitude fades and phase shifts due to phenomena such as scattering, diffraction and/or reflection off buildings and other natural and man-made structures. This includes CDMA, DS/CDMA, IS-95 CDMA, CDMAOne, CDMA2000 1X, CDMA2000 1xEV-DO, WCDMA (or UTMS), and other forms of CDMA, which are collectively referred to hereinafter as CDMA or WCDMA. Often the user or other source (collectively, “user”) is also moving, e.g., in a car or train, adding to the resulting signal distortion by alternately increasing and decreasing the distances to and numbers of building, structures and other distorting factors between the user and the base station.

[0141] In general, because each user signal can be distorted several different ways en route to the base station or other receiver (hereinafter, collectively, “base station”), the signal may be received in several components, each with a different time lag or phase shift. To maximize detection of a given user signal across multiple tag lags, a rake receiver is utilized. Such a receiver is coupled to one or more RF antennas (which serve as a collection point(s) for the time-lagged components) and includes multiple fingers, each designed to detect a different multipath component of the user signal. By combining the components, e.g., in power or amplitude, the receiver permits the original waveform to be discerned more readily, e.g., by downstream elements in the base station and/or communications path.

[0142] A base station must typically handle multiple user signals, and detect and differentiate among signals received from multiple simultaneous users, e.g., multiple cell phone users in the vicinity of the base station. Detection is typically accomplished through use of multiple rake receivers, one dedicated to each user. This strategy is referred to as single user detection (SUD). Alternately, one larger receiver can be assigned to demodulate the totality of users jointly. This strategy is referred to as multiple user detection (MUD). Multiple user detection can be accomplished through various techniques which aim to discern the individual user signals and to reduce signal outage probability or bit-error rates (BER) to acceptable levels.

[0143] However, the process has heretofore been limited due to computational complexities which can increase exponentially with respect to the number of simultaneous users. Described below are embodiments that overcome this, providing, for example, methods for multiple user detection wherein the computational complexity is linear with respect to the number of users and providing, by way of further example, apparatus for implementing those and other methods that improve the throughput of CDMA and other spread-spectrum receivers. The illustrated embodiments are implemented in connection with short-code CDMA transmitting and receiver apparatus; however those skilled in the art will appreciate that the methods and apparatus therein may be used in connection with long-code and other CDMA signalling protocols and receiving apparatus, as well as with other spread spectrum signalling protocols and receiving apparatus. In these regards and as used herein, the terms long-code and short-code are used in their conventional sense: the former referring to codes that exceed one symbol period; the latter, to codes that are a single symbol period or less.

[0144] FIG. 1 depicts components of a wireless base station 100 of the type in which the invention is practiced. The base station 100 includes an antenna array 114, radio frequency/intermediate frequency (RF/IF) analog-to-digital converter (ADC), multi-antenna receivers 110, rake modems 112, MUD processing logic 118 and symbol rate processing logic 120, coupled as shown.

[0145] Antenna array 114 and receivers 110 are conventional such devices of the type used in wireless base stations to receive wideband CDMA (hereinafter “WCDMA”) transmissions from multiple simultaneous users (here, identified by numbers 1 through K). Each RF/IF receiver (e.g., 110) is coupled to antenna or antennas 114 in the conventional manner known in the art, with one RF/IF receiver 110 allocated for each antenna 114. Moreover, the antennas are arranged per convention to receive components of the respective user waveforms along different lagged signal paths discussed above. Though only three antennas 114 and three receivers 110 are shown, the methods and systems taught herein may be used with any number of such devices, regardless of whether configured as a base station, a mobile unit or otherwise. Moreover, as noted above, they may be applied in processing other CDMA and wireless communications signals.

[0146] Each RF/IF receiver 110 routes digital data to each modem 112. Because there are multiple antennas, here, Q of them, there are typically Q separate channel signals communicated to each modem card 112.

[0147] Generally, each user generating a WCDMA signal (or other subject wireless communication signal) received and processed by the base station is assigned a unique short-code code sequence for purposes of differentiating between the multiple user waveforms received at the basestation, and each user is assigned a unique rake modem 112 for purposes of demodulating the user's received signal. Each modem 112 may be independent, or may share resources from a pool. The rake modems 112 process the received signal components along fingers, with each receiver discerning the signals associated with that receiver's respective user codes. The received signal components are denoted here as r_kq[t] denoting the channel signal (or wave-form) from the k^th user from the q^th antenna, or r_k[t] denoting all channel signals (or wave-forms) originating from the k^th user, in which case r_k[t] is understood to be a column vector with one element for each of the Q antennas. The modems 112 process the received signals r_k[t] to generate detection statistics y_k⁽⁰⁾[m] for the k^th user for the mth symbol period. To this end, the modems 122 can, for example, combine the components r_kq[t] by power, amplitude or otherwise, in the conventional manner to generate the respective detection statistics y_k⁽⁰⁾[m]. In the course of such processing, each modem 112 determines the amplitude (denoted herein as a) of and time lag (denoted herein as τ) between the multiple components of the respective user channel. The modems 112 can be constructed and operated in the conventional manner known in the art, optionally, as modified in accord with the teachings of some of the embodiments below.

[0148] The modems 112 route their respective user detection statistics y_k⁽⁰⁾[m], as well as the amplitudes and time lags, to common user detection (MUD) 118 logic constructed and operated as described in the sections that follow. The MUD logic 118 processes the received signals from each modem 112 to generate a refined output, y_k⁽ⁿ⁾[m], or more generally, y_k⁽¹⁾[m], where n is an index reflecting the number of times the detection statistics are iteratively or regeneratively processed by the logic 118. Thus, whereas the detection statistic produced by the modems is denoted as y_k⁽⁰⁾[m] indicating that there has been no refinement, those generated by processing the y_k⁽⁰⁾[m] detection statistics with logic 118 are denoted y_k⁽¹⁾[m], those generated by processing the y_k⁽¹⁾[m] detection statistics with logic 118 are denoted y_k⁽²⁾[m], and so forth. Further waveforms used and generated by logic 118 are similarly denoted, e.g., r⁽ⁿ⁾[t].

[0149] Though discussed below are embodiments in which the logic 118 is utilized only once, i.e., to generate y_k⁽¹⁾[m] from y_k⁽⁰⁾[m], other embodiments may employ that logic 118 multiple times to generate still more refined detection statistics, e.g., for wireless communications applications requiring lower bit error rates (BER). For example, in some implementations, a single logic stage 118 is used for voice applications, whereas two or more logic stages are used for data applications. Where multiple stages are employed, each may be carried out using the same hardware device (e.g., processor, co-processor or field programmable gate array) or with a successive series of such devices.

[0150] The refined user detection statistics, e.g., y_k⁽¹⁾[m] or more generally y_k⁽ⁿ⁾[M], are communicated by the MUD process 118 to a symbol process 120. This determines the digital information contained within the detection statistics, and processes (or otherwise directs) that information according to the type of user class for which the user belongs, e.g., voice or data user, all in the conventional manner.

[0151] Though the discussion herein focuses on use of MUD logic 118 in a wireless base station, those skilled in the art will appreciate that the teachings hereof are equally applicable to MUD detection in any other CDMA signal processing environment such as, by way of non-limiting example, cellular phones and modems. For convenience, such cellular base stations other environments are referred to herein as “base stations.” Multiple User Detection Processing Board

[0152] FIG. 2 depicts a multiple user detection (MUD) processing card according to the invention. The illustrated processing card 118 includes a host processor 202, an interface block 204, parallel processors 208, a front panel device 210, and a multi-channel cross-over device 206 (hereinafter “Crossbar”). Although these components are shown as separate entities, one skilled in the art can appreciate that different configurations are possible within the spirit of the invention. For example, the host processor 202 and the interface block 204 can be integrated into a single assemble, or multiple assemblies.

[0153] The processing card 118 processes waveform and waveform components received by a base station, e.g., from a modem card 112 or receiver 110 contained within the base station, or otherwise coupled with the base station. The waveform typically includes CDMA wave-forms, however the processing card 118 can also be configured for other protocols, such as TDMA and other multiple user communication techniques. The processing card 118 performs multiple user detection (MUD) on the waveform data, and generates a user signal corresponding to each user, with includes less interference than within the received signals.

[0154] The illustrated processing card 118 is a single board assembly and is manufactured to couple (e.g., electrically and physically mate) with a conventional base station (e.g., a modem card 112, receiver 110 or other component). The board assembly illustrated conforms to a ¾ form factor modem payload card of the type available in the marketplace. The processor card 118 is designed for retrofitting into existing base stations or for design into new station equipment. In other embodiments, the processing card can be either single or multiple assemblies.

[0155] The host processor 202 routes data from the interface block 204 to and among the parallel processors 208, as well as performs fault monitoring and automated resets, data transfer, and processor loading of the parallel processors 208. The host processor 202 also processes output received from the parallel processors 208, and communicates the processed output to the interface block 204 for subsequent return to the base station.

[0156] The parallel processors 202 process waveforms and waveform components routed from the host processor 206. Typically, the parallel processors 202 process the waveform components, and communicate the processed data back to the host processor 202 for further processing and subsequent transmission to the base station, however, the intermediate processed waveforms can be communicated to other parallel processors or directly to the base station.

[0157] The crossbar 206 is a communication switch which routes messages between multiple devices. It allows multiple connection data ports to be connection with other data ports. In the illustrated embodiment, the crossbar 206 provides eight ports, where a port can be “connected” to any other port (or to multiple ports) to provide communication between those two (or indeed, multiple) ports. Here, the crossbar 206 is a RACEway™ switch of the type commercially available from the assignee hereof. In other embodiments, other switching elements, whether utilizing the RACEway™ protocol or otherwise, may be used, e.g., PCI, I2C and so on. Indeed, in some embodiments, the components communicate along a common bus and/or are distributed via over a network.

[0158] A front panel 210 is used to monitor the processor card and can be used to apply software patches, as well as perform other maintenance operations. Additionally, the front panel 210 can be used to monitor fault status and interface connections through a series of LED indicators, or other indicators. Illustrated front panel interfaces with the board via the RACEway™ switch and protocol, though other interface techniques may be used as well.

[0159] FIG. 3 depicts further details of the processor card of FIG. 2. The illustrated processor card includes a host processor 202 in communication with an interface block 205 and a set of parallel processors 208 (hereinafter “compute elements”) as described above, as well as a crossbar 206 and a front panel 210. Further, a power status/control device 240 is assembled on the processor card 118. However, in other embodiments, the power status/control device 240 can be within the base station or elsewhere.

[0160] The host processor 202 includes a host controller 203 with an integrated processor containing a peripheral logic block and a 32-bit processor core. The host controller 203 is coupled with various memory devices 205, a real time clock 206, and a protocol translator 208. In the illustrated embodiment, the host controller 203 can be a Motorola PowerPC 8240 commercially available, but it will be appreciated by one skilled in the art that other integrated processors (or even non-integrated processors) can be used which satisfy the requirements herein.

[0161] The host controller 203 controls data movement within the processor card 118 and between the processor card and the base station. It controls the crossbar device 206 by assigning the connection between connection ports. Further, the host controller 203 applies functionality to the output generated by the parallel processors 208. The host controller 203 includes a monitor/watchdog sub-system which monitors the perform ace of the various components within the processor card, and can issue resets to the components. In some embodiments, these functions can be provided (or otherwise assisted) by application specific integrated circuits or field programmable gate arrays.

[0162] The host controller 203 integrates a PCI bus 211a, 211b for data movement with the memory devices 205 and the interface block 205, as well as other components. The PCI bus 211a, 211b is capable of 32-bit or 64-bit data transfers operating at 33 MHz, or alternatively 66 MHz speeds, and supports access to PCI memory address spaces using either (or both) little and/or big endian protocols.

[0163] Memory devices used by the host controller 203 include HA Registers 212, synchronous dynamic random access memory (SDRAM) 214, Flash memory 216, and Non-Volatile Ram (NVRAM) 218. As will be evident below, each type of memory is used for differing purposes.

[0164] The HA registers 212 store operating status (e.g., faults) for the parallel processors 208, the power status/control device 240, and other components. A fault monitoring sub-system “watchdog” writes both software and hardware status into the HA registers 212, from which the host controller 203 monitors the registers 212 to determine the operational status of the components. The HA registers 212 are mapped into banked memory locations, and are thereby addressable as direct access registers. In some embodiments, the HA registers 212 can be integrated with the host controller 203 and still perform the same function.

[0165] The SDRAM 214 stores temporary application and data. In the illustrated embodiment, there is 64 Kbytes of SDRAM 214 available to support transient data, e.g., intermediary results from processing and temporary data values. The SDRAM 214 is designed to be directly accessed by the host controller 203 allowing for fast DMA transfers.

[0166] The flash memory 216 includes two Intel StrataFlash devices, although equivalent memory devices are commercially available. It stores data related to component performance data, and intermediate data which can be used to continue operation after resets are issued. The flash memory is blocked at 8 Kbyte boundaries, but in other embodiments, the block size can vary depending on the addressing capabilities of the host controller 203 and method of communication with the memory devices. Further, because flash memory requires no power source to retain programmed memory data, its data can be used for diagnostic purposes even in the event of power-failures.

[0167] NVRAM is, to an extent, reserved for fault record data and configuration information. Data stored within the NVRAM 218, together with the flash memory 216 is sufficient to reproduce the data within the SDRAM 218 upon system (or board level, or even component level) reset. If a component is reset during operation, the host controller 203 can continue operation without the necessity of receiving additional information from the base station via the data stored in the NVRAM. The NVRAM 218 is coupled to the host controller 203 via a buffer which converts the voltage of the PCI bus 211a from 3.3v to 5v, as required by the NVRAM 218, however this conversion is not necessary in other embodiments with different memory configurations.

[0168] The interface block 205 includes a PCI bridge 222 in communication with an Ethernet interface 224 and a modem connection 226. The PCI bridge 222 translates data received from the PCI bus 211b into a protocol recognized by the base station modem card 112. Here, the modem connection 226 operates with a 32-bit interface operating at 66 MHz, however, in other embodiments the modem can operate with different characteristics. The Ethernet connection 224 can operate at either 10 Mbytes/Sec or 100 Mbytes/Sec, and is therefore suited for most Ethernet devices. Those skilled in the art can appreciate that these interface devices can be interchanged with other interface devices (e.g., LAN, WAN, SCSI and the like).

[0169] The real-time clock 206 supplies timing for the host controller 203 and the parallel processors 208, and thus, synchronizes data movement within the processing card. It is coupled with the host controller 203 via an integrated I2C bus (as established by Phillips Corporation, although in other embodiments the clock can be connected via other electrical coupling). The real-time clock 206 is implemented as a CMOS device for low power consumption. The clock generates signals which control address and data transfers within the host controller 203 and the multiple processors 208.

[0170] A protocol converter 208 (hereinafter “PXB”) converts PCI protocol used by the host controller 203 to RACEway™ protocol used by the parallel processors 208 and front panel 210. The PXB 208 contains a field programmable gate array (“FPGA”) and EEPROM which can be programmed from the PCI bus 211b. In some embodiments, the PXB 208 is programmed during manufacture of the processing card 118 to contain configuration information for the related protocols and/or components with which it communicates. In other embodiments, the PXB 208 can use other protocols as necessary to communicate with the multiple processors 208. Of course, if the host controller 203 and the multiple processors 208 use the same protocol, there is no protocol conversion necessary and therefore the PXB is not required.

[0171] The multiple-port communication device 206 (hereinafter “crossbar”) provides communication between all processing and input/output elements on the processing card 118. In the illustrated embodiment, the crossbar 206 is an EEPROM device which can be read and programmed by a RACEway™ compatible component (e.g., the front panel 210 or parallel processors 208), but it is typically programmed initially during manufacture. An embedded ASIC device controls the EEPROM programming, and hence, the function of the crossbar 206.

[0172] The crossbar 206 in the illustrated provides up to three simultaneous 266-Mbytes/Sec throughput data paths between elements for a total throughput of 798 Mbytes/Sec, however, in other embodiments the actual throughput varies according to processing speed. Here, two crossbar ports (e.g., ports 0 and 1) connect to a bridge FPGA which further connect to the front panel 210. Each of the multiple processors use an crossbar port (e.g., ports 2, 3, 5, and 6), and the interface block 224 and host controller 203 share one crossbar port (e.g., port 4) via the PXB 206. The number of ports on the crossbar 206 depends on the number of parallel processors and other components that are in communication.

[0173] The multiple processors 208 in the illustrated embodiment include four compute elements 220a–220d (hereinafter, reference to element 220 refers to a general compute element, also referred to herein as a “processing element” or “CE”). Each processing element 220 applies functionality on data, and generates processed date in the form of a matrix, vector, or waveform. The processing elements 220 can also generate scalar intermediate values. Generated data is passed to the host controller 208, or to other processing elements 220 for further processing. Further, individual processing elements can be partitioned to operate in series (e.g., as a pipeline) or in parallel with the other processing elements.

[0174] A processing element 220 includes a processor 228 coupled with a cache 230, a Joint Test Action Group (hereinafter “JTAG”) interface 232 with an integrated programming port, and an application specific integrated circuit 234 (hereinafter “ASIC”). Further, the ASIC 234 is coupled with a 128 Mbyte SDRAM device 236 and HA Registers 238. The HA Registers are coupled with 8 Kbytes of NVRAM 244. In the illustrated embodiment the compute elements 220 are on the same assembly as the host controller 203. In other embodiments, the compute nodes 220 can be separate from the host controller 203 depending on the physical and electrical characteristics of the target base station.

[0175] The compute node processors 228 illustrated are Motorola PowerPC 7400, however in other embodiments the processor can be other processor devices. Each processor 228 uses the ASIC 234 to interface with a RACEway™ bus 246. The ASIC 234 provides certain features of a compute node 220, e.g., a DMA engine, mail box interrupts, timers, page mapping registers, SDRAM interface and the like. In the illustrated embodiment the ASIC is programmed during manufacture, however, it can also be programmed in the field, or even at system reset in other embodiments.

[0176] The cache 230 for each compute node 220 stores matrices that are slow-changing or otherwise static in relation to other matrices. The cache 230 is pipelined, single-cycle deselect, synchronous burst static random access memory, although in other embodiments high-speed RAM or similar devices can be used. The cache 230 can be implemented using various devices, e.g., multiple 64 Kbyte devices, multiple 256 Kbyte devices, and so on.

[0177] Architecture Pairing of Processing Nodes with NVRAM and Watchdog; Majority Voter

[0178] The HA registers 238 store fault status for the software and/or hardware of the compute element 220. As such, it responds to the watchdog fault monitor which also monitors the host controller 203 and other components. The NVRAM 244 is, much like the NVRAM coupled with the host controller 203, stores data from which the current state of the compute element 220 can be recreated should a fault or reset occur. The SDRAM 236 is used for intermediate and temporary data storage, and is directly addressable from both the ASIC 234 and the processor 228. These memory devices can be other devices in other embodiments, depending on speed requirements, throughput and computational complexity of the multiple user detection algorithms.

[0179] NVRAM is also used to store computational variables and data such that upon reset of the processing element or host controller, execution can be re-started without the need to refresh the data. Further, the contents of NVRAM can be used to diagnose fault states and/or conditions, thus aiding to a determination of the cause of fault state.

[0180] As noted above, a “watchdog” monitors performance of the processing card 118. In the illustrated embodiment, there are five independent “watchdog” monitors on the processing card 118 (e.g., one for the host controller 203 and one each for each compute node 220a–220d, and so on). The watchdog also monitors performance of the PCI bus as well as the RaceWay bus connected with each processing element and the data switch. The RACEWay bus includes out-of-band fault management coupled with the watchdogs.

[0181] Each component periodically strobes its watchdog at least every 20 msec but not faster that 500 microseconds (these timing parameters vary among embodiments depending on over-all throughput of the components and clock speed). The watchdog is initially strobed approximately two seconds after the initialization of a board level reset, which allows for start-up sequencing of the components without cycling erroneous resets. Strobing the watchdog for the processing nodes is accomplished by writing a zero or a one sequence to a discrete word (e.g., within the HA Register 212) originating within each compute element 220a–220d, the host controller 203, and other components). The watchdog for the host controller 203 is serviced by writing to the memory mapped discrete location FFF_D027 which is contained within the HA Registers 212.

[0182] The watchdog uses five 8-bit status registers within the HA registers 212, and additional registers (e.g., HA registers 238) within each compute node 220. One register represents the host controller 203 status, and the other four represent each compute node 220a–220d status. Each register has a format as follows:

[0183]

Bit	Name	Description
0	CHECKSTOP_OUT	Checkstop state of CPU
		(0 = CPU in checkstop)
1	WDM_FAULT	WDM failed (0 = WDM failed,
		set high after reset and valid service)
2	SOFTWARE_FAULT	Software fault detected (Set to 0 when a
		software exception was detected)
		(R/W local)
3	RESETREQ_IN	Wrap status of the local CPU's reset request
4	WDM_INIT	WDM failed in initial 2 second window
		(0 = WDM failed)
5	Software definable 0	Software definable 0
6	Software definable 1	Software definable 1
7	Unused	Unused

[0184] The five registers reflect status information for all processors within the processing board 118, and allow the host controller 203 to obtain status of each without the need for polling the processor individually (which would degrade performance and throughput). Additionally, the host controller 203 and each compute node processor 228 has a fault control register which contains fault data according to the following format:

[0185]

Bit	Name	Description
0	RESETREQ_OUT_0	Request a reset event (0 => forces reset)
1	CHKSTOPOUT_0	Request that node 0 enter checkstop state
		(0 => request checkstop)
2	CHKSTOPOUT_1	Request that node 1 enter checkstop state
		(0 => request checkstop)
3	CHKSTOPOUT_2	Request that node 2 enter checkstop state
		(0 => request checkstop)
4	CHKSTOPOUT_3	Request that node 3 enter checkstop state
		(0 => request checkstop)
5	CHKSTOPOUT_8240	Request that the host controller enter
		checkstop state (0 => request checkstop)
6	Software definable 0	Software definable 0
7	Software definable 1	Software definable 1

[0186] A single write of any value will strobe the watchdog. Upon events such as power-up, the watchdogs are initialized to a fault state. Once a valid strobe is issued, the watchdog executes and, if all elements are properly operating, writes a no-fault state to the HA register 212. This occurs within the initial two-second period after board level reset. If a processor node fails to service the watchdog within the valid time frame, the watchdog records a fault state. A watchdog of a compute node 220 in fault triggers an interrupt to the host controller 203. If a fault is within the host controller 203, then the watchdog triggers a reset to the board. The watchdog then remains in a latched failed state until a CPU reset occurs followed by a valid service sequence.

[0187] Each processor node ASIC 234 accesses a DIAG3 signal that is wired to an HA register, and is used to strobe the compute element's hardware watchdog monitor. A DIAG2 signal is wired to the host processor's embedded programmable interrupt controller (EPIC) and is used by a compute element to generate a general purpose interrupt to the host controller 203.

[0188] A majority voter (hereinafter “voter”) is a dual software sub-system state machine that identifies faults within each of the processors (e.g., the host controller 230 and each compute node 220a–220d) and also of the processor board 118 itself. The local voter can reset individual processors (e.g., a compute node 220) by asserting a CHECKSTOP_IN to that processor. The board level voter can force a reset of the board by asserting a master reset, wherein all processors are reset. Both voters follow a rule set that the output will follow the majority of non-checkstopped processors. If there are more processors in a fault condition than a non-fault condition, the voter will force a board reset. Of course, other embodiments may use other rules, or can use a single sub-system to accomplish the same purpose.

[0189] A majority voter is illustrated in FIG. 4. Board level resets are initiated from a variety of sources. One such source is a voltage supervisor (e.g., the power status/control device 240) which can generate a 200 ms reset if the voltage (e.g., VCC) rises above a predetermined threshold, such as 4.38 volts (this is also used in the illustrated embodiment in a pushbutton reset switch 406, however, the push button can also be a separate signal). The board level voter will continue to drive a RESET_—0 408 until both the voltage supervisor 404 and the PCI_RESET_—0 410 are de-asserted. Either reset will generate the signal RESET_—0 412 which resets the card into a power-on state. RESET_—0 412 also generates HRESET_—0 414 and TRST 416 signals to each processor. Further, a HRESET_—0 and TRSTcan be generated by the JTAG ports using a JTAG_HRESET_—0 418 and JTAG_TRST 420 respectively. The host controller 203 can generate a reset request, a soft reset (C_SRESET_—0 422) to each processor, a check-stop request, and an ASIC reset (CE_RESET_—0 424) to each of the four compute element's ASIC. A discrete word from the 5v-powered reset PLD will generate the signal NPORESET_—1 (not a power on reset). This signal is fed into the host processor discrete input word. The host processor will read this signal as logic low only if it is coming out of reset due to either a power condition or an external reset from off board. Each compute element, as well as the host processor can request a board level reset. These requests are majority voted, and the result RESET-VOTE_—0 will generate a board level reset.

[0190] Each compute node processor 228 has a hard reset signal driven by three sources gated together: a HRESET_—0 pin 426 on each ASIC, a HRESET_—0 418 from the JTAG connector 232, and a HRESET_—0 412 from the majority voter. The HRESET_—0 pin 426 from the ASIC is set by the “node run” bit field (bit 0) of the ASIC Miscon_A register. Setting HRESET_—0 426 low causes the node processor to be held in reset. HRESET_—0 426 is low immediately after system reset or power-up, the node processor is held in reset until the HRESET_—0 line is pulled high by setting the node run bit to 1. The JTAG HRESET_—0 418 is controlled by software when a JTAG debugger module is connected to the card. The HRESET_—0 412 from the majority voter is generated by a majority vote from all healthy nodes to reset.

[0191] When a processor reset is asserted, the compute processor 228 is put into reset state. The compute processor 228 remains in a reset state until the RUN bit 0 of the Miscon_A register is set to 1 and the host processor has released the reset signals in the discrete output word. The RUN bit is set to 1 after the boot code has been loaded into the SDRAM starting at location 0x0000_—0100. The ASIC maps the reset vector 0xFFF0_—0100 generated by the MPC7400 to address 0x0000_—0100.

[0192] Turning now to discuss memory devices 205 coupled with the host controller 203, the memory devices are addressable by the host controller 203 as follows. The host controller 203 addresses the memory devices (e.g., the HA registers 212, SDRAM 214, Flash 216 and NVRAM 218) using two address mapping configurations designated as address map A and address map B, although other configurations are possible. Address map A conforms to the PowerPC reference platform (PreP) specification (however, if other host controllers are used, map A conforms with a native reference platform to that host controller). Address map B conforms to the host controller 203 common hardware reference platform (CHRP).

[0193] Support of map A is provided for backward compatibility, and further supports any retrofitting of existing base station configurations. The address space of map B is divided into four areas: system memory, PCI memory, PCI Input/Output (I/O), and system ROM space. When configured for map B, the host controller translates addresses across the internal peripheral logic bus and the external PCI bus as follows:

[0194]

Processor Core Address Range
Hex		Decimal		PCI Address Range	Definition
0000_0000	0009_FFFF	0	640K - 1	NO PCI CYCLE	System memory
000A_0000	000F_FFFF	640K	1M-1	000A_0000–000F_FFFF	Compatibility hole
0010_0000	3FFF_FFFF	1M	1G-1	NO PCI CYCLE	System memory
4000_0000	7FFF_FFFF	1G	2G-1	NO PCI CYCLE	Reserved
8000_0000	FCFF_FFFF	2G	4G-48M-1	8000_0000–FCFF_FFFF	PCI memory
FD00_0000	FDFF_FFFF	4G-48M	4G-32M-1	0000_0000–00FF_FFFF	PCI/ISA memory
FE00_0000	FE7F_FFFF	4G-32M	4G-24M-1	0000_0000–007F_FFFF	PCI/ISA I/O
FE80_0000	FEBF_FFFF	4G-24M	4G-20M-1	0080_0000–00BF_FFFF	PCI I/O
FEC0_0000	FEDF_FFFF	4G-20M	4G-18M-1	CONFIG_ADDR	PCI configuration address
FEE0_0000	FEEF_FFFF	4G-18M	4G-17M-1	CONFIG_DATA	PCI configuration data
FEF0_0000	FEFF_FFFF	4G-17M	4G-16M-1	FEF0_0000–FEFF_FFFF	PCI interrupt acknowledge
FF00_0000	FF7F_FFFF	4G-16M	4G-8M-1	FF00_0000–FF7F_FFFF	32/64-bit Flash/ROM
FF80_0000	FFFF_FFFF	4G-8M	4G-1	FF80_0000–FFFF_FFFF	8/32/64-bit Flash/ROM

[0195] In the illustrated embodiment, hex address FF00_—0000 through FF7F_FFFF is not used, and hence, that bank of Flash ROM is not used. The address of FF80_—0000 through FFFF_FFFF is used, as the Flash ROM is configured in 8-bit mode and is addressed as follows:

[0196]

Bank	Processor Core Address
Select	Range	Definition
11111	FFE0_0000	FFEF_FFFF	Accesses Bank 0
11110-	FFE0_0000	FFEF_FFFF	Application code (30 pages)
00001	FFE0_0000	FFEF_FFFF	Application/boot code
00000
XXXX	FFF0_0000	FFFF_CFFF	Application/boot code
	FFFF_D000	FFFF_D000	Discrete input word 0
	FFFF_D001	FFFF_D001	Discrete input word 1
	FFFF_D002	FFFF_D002	Discrete output word 0
	FFFF_D003	FFFF_D003	Discrete output word 1
	FFFF_D004	FFFF_D004	Discrete output word 2
	FFFF_D010	FFFF_D010	IC (Pending interrupt)
	FFFF_D011	FFFF_D011	IC (Interrupt mask low)
	FFFF_D012	FFFF_D012	IC (Interrupt clear low)
	FFFF_D013	FFFF_D013	IC (Unmasked, pending low)
	FFFF_D014	FFFF_D014	IC (Interrupt input low)
	FFFF_D015	FFFF_D015	Unused (read FF)
	FFFF_D016	FFFF_D016	Unused (read FF)
	FFFF_D017	FFFF_D017	Unused (read FF)
	FFFF_D018	FFFF_D018	Unused (read FF)
	FFFF_D019	FFFF_D019	Unused (read FF)
	FFFF_D020	FFFF_D020	HA (Local HA register)
	FFFF_D021	FFFF_D021	HA (Node 0 HA register)
	FFFF_D022	FFFF_D022	HA (Node 1 HA register)
	FFFF_D023	FFFF_D023	HA (Node 2 HA register)
	FFFF_D024	FFFF_D024	HA (Node 3 HA register)
	FFFF_D025	FFFF_D025	HA (8240 HA register)
	FFFF_D026	FFFF_D026	HA (Software Fail)
	FFFF_D027	FFFF_D027	HA (Watchdog Strobe)
	FFFF_D028	FFFF_DFFF	4068 Bytes Flash
	FFFF_E000	FFFF_FFFF	8K NVRAM

[0197] Address FFEF_—0000 through FFEF_FFFF contains 30 pages, and is used for application and boot code, as selected by the Flash bank bits. Further, there a 2 Mbyte block available after reset. Data movement occurs on the PCI 211a and/or a memory bus.

[0198] DMA Engine Supported by Host Controller and FPGA

[0199] Direct memory access (DMA) is performed by the host controller 203, and operates independently from the host processor 203 core, as illustrated in FIG. 5. The host controller 203 has an integrated DMA engine including a DMA command stack 502, a DMA state engine 504, an address decode block 506, and three FIFO interfaces 508, 510, 512. The DMA engine receives and sends information via the PXB 208 coupled with the crossbar 206.

[0200] The command stack 502 and state machine 504 processes DMA requests and transfers. The stack 502 and state machine 504 can initiate both cycle stealing and burst mode, along with host controller interupts. The address decode 506 sets the bus address, and triggers transmissions of the data.

[0201] The host controller 203 has two DMA I/O interfaces, each with a 64-byte queue to facilitate the gathering and sending of data. Both the local processor and PCI masters can initiate a DMA transfer. The DMA controller supports memory transfers between PCI to memory, between local and PCI memory, and between local memory devices. Further, the host controller 203 can transfer in either block mode or scatter mode within discontinuous memory. A receiving channel 510 buffers data that is to be received by the memory. A transmit channel 512 buffers data that is sent from memory. Of course, the buffers can also send/receive information from other devices, e.g., the compute nodes 220, or other devices capable of DMA transfers.

[0202] The host controller 203 contains an embedded programmable interrupt controller (EPIC) device. The interrupt controller implements the necessary functions to provide a flexible and general-purpose interrupt controller. Further, the interrupt controller can pool interrupts generated from the several external components (e.g., the compute elements), and deliver them to the processor core in a prioritized manner. In the illustrated embodiment, an OpenPIC architecture is used, although it can be appreciated by one skilled in the art that other such methods and techniques can be used. Here, the host controller 203 supports up to five external interrupts, four internal logic-driven interrupts, and four timers with interrupts.

[0203] Data transfers can also take effect via the FPGA program interface 508. This interface can program and/or accept data from various FPGAs, e.g., the compute note ASIC 234, crossbar 242, and other devices. Data transfers within the compute node processor 228 to its ASIC 234 and RACEway™ bus 246 are addressed as follows:

[0204]

From Address	To Address	Function
0x0000 0000	0x0FFF FFFF	Local SDRAM 256 Mb
0x1000 0000	0x1FFF FFFF	crossbar 256 Mb map window 1
0x2000 0000	0x2FFF FFFF	crossbar 256 MB map window 2
0x3000 0000	0x3FFF FFFF	crossbar 256 MB map window 3
0x4000 0000	0x4FFF FFFF	crossbar 256 MB map window 4
0x5000 0000	0x5FFF FFFF	crossbar 256 MB map window 5
0x6000 0000	0x6FFF FFFF	crossbar 256 MB map window 6
0x7000 0000	0x7FFF FFFF	crossbar 256 MB map window 7
0x8000 0000	0x8FFF FFFF	crossbar 256 MB map window 8
0x9000 0000	0x9FFF FFFF	crossbar 256 MB map window 9
0xA000 0000	0xAFFF FFFF	crossbar 256 MB map window A
0xB000 0000	0xBFFF FFFF	crossbar 256 MB map window B
0xC000 0000	0xCFFF FFFF	crossbar 256 MB map window C
0xD000 0000	0xDFFF FFFF	crossbar 256 MB map window D
0xE000 0000	0xEFFF FFFF	crossbar 256 MB map window E
0xF000 0000	0xFBFF FBFF	Not used (CE reg replicated mapping)
0xFBFF FC00	0xFBFF FDFF	Internal CN ASIC registers
0xFBFF FE00	0xFEFF FFFF	Pre-fetch control
0xFF00 0000	0xFFFF FFFF	16 MB boot FLASH memory area

[0205] The SDRAM 236 can be addressable in 8, 16, 32 or 64 bit addresses. The RACEway™ bus 246 supports locked read/write and locked read transactions for all data sizes. A 16 Mbyte boot flash area is further divided as follows:

[0206]

From Address	To Address	Function
0xFF00 2006	0xFF00 2006	Software Fail Register
0xFF00 2005	0xFF00 2005	MPC8240 HA Register
0xFF00 2004	0xFF00 2004	Node 3 HA Register
0xFF00 2003	0xFF00 2003	Node 2 HA Register
0xFF00 2002	0xFF00 2002	Node 1 HA Register
0xFF00 2001	0xFF00 2001	Node 0 HA Register
0xFF00 2000	0xFF00 2000	Local HA Register (status/control)
0xFF00 0000	0xFF00 1FFF	NVRAM

[0207] Slave accesses are accesses initiated by an external RACEway™ device directed toward the compute element processor 238. The ASIC 234 supports a 256 Mbyte address space which can be partitioned as follows:

[0208]

From Address	To Address	Function
0x0000 0000	0x0FFF FBFF	256 MB less 1 Kb hole SDRAM
0Xfff_FC00	0xFFF_FFFF	PCE133 internal registers

[0209] There are 16 discrete output signals directly controllable and readable by the host controller 203. The 16 discrete output signals are divided into two addressable 8-bit words. Writing to a discrete output register will cause the upper 8-bits of the data bus to be written to the discrete output latch. Reading a discrete output register will drive the 8-bit discrete output onto the upper 8-bits of the host processor data bus. The bits in the discrete output word are defined as follows:

[0210] There are 16 discrete input signals accessible by the host controller 203. Reads from the discrete input address space will latch the state of the signals, and return the latched state of the discrete input signals to the host processor. The bits in the discrete input word are as follows:

[0211]

DH(0:7)	Signal	Description
	Output Word 2
0	ND0_FLASH_EN_1	Enable the CE ASIC's FLASH port when 1
1	ND1_FLASH_EN_1	Enable the CE ASIC's FLASH port when 1
2	ND2_FLASH_EN_1	Enable the CE ASIC's FLASH port when 1
3	ND3_FLASH_EN_1	Enable the CE ASIC's FLASH port when 1
4	Wrap 1	Wrap to discrete input
5
6
7
	Output Word 1
0	WRAP0	Wrap to Discrete Input
1	I2C_RESET_0	Reset the I2C serial bus when 0
2	SWLED	Software controlled LED
3	FLASHSEL4	Flash bank select address bit 4
4	FLASHSEL3	Flash bank select address bit 3
5	FLASHSEL2	Flash bank select address bit 2
6	FLASHSEL1	Flash bank select address bit 1
7	FLASHSEL0	Flash bank select address bit 0
	Output Word 0
0	C_SRESET3_0	Issue a Soft Reset to CPU on Node 3 when 0
1	C_PRESET3_0	Reset PCE133 ASIC Node 3 when 0
2	C_SRESET2_0	Issue a Soft Reset to cpu on Node 2 when 0
3	C_PRESET2_0	Reset PCE133 ASIC Node 2 when 0
4	C_SRESET1_0	Issue a Soft Reset to cpu on Node 1 when 0
5	C_PRESET1_0	Reset PCE133 ASIC Node 1 when 0
6	C_SRESET0_0	Issue a Soft Reset to cpu on Node 0 when 0
7	C_PRESET0_0	Reset PCE133 ASIC Node 0 when 0
	Input Word 1
0	WRAP1	Wrap from discrete output word
1
2	V3.3_FAIL_0	Latched status of power supply since last reset
3	V2.5_FAIL_0	Latched status of power supply since last reset
4	VCORE1_FAIL_0	Latched status of power supply since last reset
5	VCORE0_FAIL_0	Latched status of power supply since last reset
6	RIOR_CNF_DONE_1	RIO/RACE++ FPGA configuration complete
7	PXB0_CNF_DONE_1	PXB++ FPGA configuration complete
	Input Word 0
0	WRAP0	Wrap from discrete output word
1	WDMSTATUS	MPC8240's watchdog monitor status (0 = failed)
2	NPORESET_1	Not a power on reset when high
3
4
5
6
7

[0212] The host controller 203 interfaces with an 8-input interrupt controller external from processor itself (although in other embodiments it can be contained within the processor). The interrupt inputs are wired, through the controller to interrupt zero of the host processor external interrupt inputs. The remaining four host processor interrupt inputs are unused.

[0213] The Interrupt Controller comprises the following five 8-bit registers:

[0214]

Resister	Description
Pending Register	A low bit indicates a falling edge was detected on that interrupt
	(read only);
Clear Register	Setting a bit low will clear the corresponding latched interrupt
	(write only);
Mask Register	Setting a bit low will mask the pending interrupt from generating
	a processor interrupt;
Unmasked Pending	A low bit indicates a pending interrupt that is not masked out
Register
Interrupt State Register	indicates the actual logic level of each interrupt input pin.

[0215] The interrupt input sources and their bit positions within each of the six registers are as follows:

[0216]

Bit	Signal	Description
0	SWFAIL_0	8240 Software Controlled Fail Discrete
1	RTC_INT_0	Real time clock event
2	NODE0_FAIL_0	WDFAIL_0 or IWDFAIL_0 or
		SWFAIL_0 active
3	NODE1_FAIL_0	WDFAIL_0 or IWDFAIL_0 or
		SWFAIL_0 active
4	NODE2_FAIL_0	WDFAIL_0 or IWDFAIL_0 or
		SWFAIL_0 active
5	NODE3_FAIL_0	WDFAIL_0 or IWDFAIL_0 or
		SWFAIL_0 active
6	PCI_INT_0	PCI interrupt
7	XB_SYS_ERR_0	crossbar internal error

[0217] A falling edge on an interrupt input will set the appropriate bit in the pending register low. The pending register is gated with the mask register and any unmasked pending interrupts will activate the interrupt output signal to the host processor external interrupt input pin. Soft-ware will then read the unmasked pending register to determine which interrupt(s) caused the exception. Software can then clear the interrupt(s) by writing a zero to the corresponding bit in the clear register. If multiple interrupts are pending, the software has the option of either servicing all pending interrupts at once and then clearing the pending register or servicing the highest priority interrupt (software priority scheme) and the clearing that single interrupt. If more interrupts are still latched, the interrupt controller will generate a second interrupt to the host processor for software to service. This will continue until all interrupts have been serviced.

[0218] An interrupt that is masked will show up in the pending register but not in the unmasked pending register and will not generate a processor interrupt. If the mask is then cleared, that pending interrupt will flow through the unmasked pending register and generate a processor interrupt.

[0219] The multiple components within the processor board 118 dictate various power requirements. The processor board 118 requires 3.3V, 2.5V, and 1.8V. In the illustrated embodiment, there are two processor core voltage supplies 302, 304 each driving two 1.8V cores for two processors (e.g., 228). There is also a 3.3V supply 306 and a 2.5V supply 308 which supply voltage to the remaining components (e.g., crossbar 206, interface block 205 and so on). To provide power to the board, the three voltages (e.g., the 1.8V, 3.3V and 2.5V) have separate switching supplies, and proper power sequencing. All three voltages are converted from 5.0V. The power to the processor card 118 is provided directly from the modem board 112 within the base station, however, in other embodiments there is a separate or otherwise integrated power supply. The power supply a preferred embodiment is rated as 12A, however, in other embodiments the rating varies according to the specific component requirements.

[0220] In the illustrated embodiment, for instance, the 3.3V power supply 306 is used to provide power to the NVRAM 218 core, SDRAM 214, PXB 208, and crossbar ASIC 206 (or FPGA is present). This power supply is rated as a function of the devices chosen for these functions.

[0221] A 2.5V power supply 308 is used to provide power to the compute node ASIC 234 and can also power the PXB 208 FPGA core. The host processor bus can run at 2.5V signaling. The host bus can operate at 2.5V signaling.

[0222] The power-on sequencing is necessary in multi-voltage digital boards. One skilled in the art can appreciate that power sequencing is necessary for long-term reliability. The right power supply sequencing can be accomplished by using inhibit signals. To provide fail-safe operation of the device, power should be supplied so that if the core supply fails during operation, the I/O supply is shut down as well.

[0223] Although in theory, the general rule is to ramp all power supplies up and down at the same time as illustrated in FIG. 6. The ramp up 602 and ramp down 604 show agreement with the power supplies 302, 304, 306, 308 over time. One skilled in the art realizes that in reality, voltage increases and decreases do not occur among multiple power supplies in such a simultaneous fashion.

[0224] FIG. 7 shown the actual voltage characteristics for the illustrated embodiment. As can be seen, ramp up 702a–702c and ramp down 704a–704c sequences depend on multiple factors, e.g., power supply, total board capacities that need to be charged, power supply load, and so on. For example, the ramp up for the 3.3V supply 702a occurs before the ramp up for the 2.5V supply 702c, which occurs before the ramp up of the 1.8V supplies 702b. Further, the ramp down for the 3.3V supply 704a occurs before the ramp down for the 2.5V supply 704c, which occurs before the ramp down for the 1.8V supplies 704c.

[0225] Also, The host processor requires the core supply to not exceed the I/O supply by more than 0.4 volts at all times. Also, the I/O supply must not exceed the core supply by more than 2 volts. Therefore, to achieve an acceptable power-up and power-down sequencing, e.g., to avoid damage to the components, a circuit containing diodes is used in conjunction with the power supplied within the base station.

[0226] The power status/control device 240 is designed from a programmable logic device (PLD). The PLD is used to monitor the voltage status signals from the on board supplies. It is powered up from +5V and monitors +3.3V, +2.5V, 1.8V_—1 and +1.8V_—2. This device monitors the power_good signals from each supply. In the case of a power failure in one or more supplies, the PLD will issue a restart to all supplies and a board level reset to the processor board. A latched power status signal will be available from each supply as part of the discrete input word. The latched discrete can indicate any power fault condition since the last off-board reset condition.

[0227] In operation, the processor board inputs raw antenna data from the base station modem card 112 (or other available location of that data), detects sources of interference within that data, and produces a new stream of data which has reduced interference subsequently transmitting that refined data back to the modem card (or other location) for further processing within the base station.

[0228] As can be appreciated by one skilled in the art, such interference reduction is computationally complex; hence, the hardware must support throughputs sufficient for multiple user processing. In a preferred embodiment, characteristics of processing are a latency of less than 300 microseconds handing data in the 110 Mbytes/Sec range, however, in other embodiments the latency and data load can vary.

[0229] In the illustrated embodiment, data from the modem board is supplied via the PCI bus 211b through the PCI bridge 222. From there, the data traverses the crossbar 206 and is loaded into the host controller memory 205. Output data flows in the opposite direction. Additionally, certain data flows between the host controller 203 and the compute elements 220.

[0230] Hybrid Operating System

[0231] The compute elements 220 operate, in some embodiments, under the MC/OS operating system available commercially from the assignee herein, although different configurations can run under different operating systems suited for such. Here, one aspect is to reduce the use of non-POSIX system calls which can increase portability of the multiple user detection software among different hardware environments and operating system environments. The host processor is operated by the VxWorks operating system, as is required by MC/OS and suitable for a Motorola 8240 PowerPC.

[0232] FIG. 8 shows a block diagram of various components within the hardware/software environment. An MC/OS subsystem 802 is used as an operating system for the compute elements 220. Further, a MC/OS DX 804 provides APIs acceptable overhead and latency access to the DMA engines which in turn provide suitable bandwidth transfers of data. DX 804 can be used to move data between the compute elements 220 during parallel processing, and also to move data between the compute elements 220, the host controller 203, and the modem card 112. As described above, each compute element 220 continues an application 806, and a watchdog 808. Further, the HA registers provide the bootstrap 810 necessary for start-up.

[0233] The host controller 203 runs under the VxWorks operating system 812. The host processor 202 contains a watchdog 814, application data 816, and a bootstrap 818. Further, the host processor 202 can perform TCP/IP stack processing 820 for communication through the Ethernet interface 224.

[0234] Input/output between the processor card 118 and the modem card 112 takes place by moving data between the Race++ Fabric and the PCI bus 211b via the PCI bridge 222. The application 806 will use DX to initialize the PXB++ bridge, and to cause input/output data to move as if it were regular DX IPC traffic. For example, there are several components which can initiate data transfers and choose PCI addresses to be involved with the transfers.

[0235] One approach to increasing available on the processor card 118 is to balance host-processing time against application execution. For example, when the system comes up, the application determines which processing resources are available, and the application determines a load mapping on the available resources and record certain parameters in NVRAM. Although briefs interruptions in service can occur, the application does not need to know how to continue execution across faults. For instance, the application can make an assumption that the hardware configuration will not change without the system first rebooting. If the application is in a state which needs to be preserved across reboots, the application checkpoints the data on a regular basis. The system software provides an API to a portion of the NVRAM for this purpose

[0236] The host controller 203 is attached to an amount of linear flash memory 216 as discussed above. This flash memory 216 serves several purposes. The first purpose the flash memory serves is as a source of instructions to execute when the host controller comes out of reset. Linear flash can be addressed much like normal RAM. Flash memories can be organized to look like disk controllers; however in that configuration they generally require a disk driver to provide access to the flash memory. Although such an organization has several benefits such as automatic reallocation of bad flash cells, and write wear leveling, it is not appropriate for initial bootstrap. The flash memory 216 also serves as a file system for the host and as a place to store permanent board information (e.g., such as a serial number).

[0237] When the host controller 203 first comes out of reset, memory is not turned on. Since high-level languages such as C assume some memory is present (e.g., for a stack) the initial bootstrap code must be coded in assembler. This assembler bootstrap contains a few hundred lines of code, sufficient to configure the memory controller, initialize memory, and initialize the configuration of the host processor internal registers.

[0238] After the assembler bootstrap has finished execution, control is passed to the processor HA code (which is also contained in boot flash memory). The purpose of the HA code is to attempt to configure the fabric, and load the compute element CPUs with HA code. Once this is complete, all the processors participate in the HA algorithm. The output of the algorithm is a configuration table which details which hardware is operational and which hardware is not. This is an input to the next stage of bootstrap, the multi-computer configuration.

[0239] MC/OS expects the host controller system to configure the multi-computer (e.g., compute elements 220). A configmc program reads a textual description of the computer system configuration, and produces a series of binary data structures that describe the system configuration. These data structures are used in MC/OS to describe the routing and configuration of the multi-computer.

[0240] The processor board 118 will use almost exactly the same sequence to configure the multi-computer. The major difference is that MC/OS expects configurations to be static, whereas the processor board configuration changes dynamically as faulty hardware cause various resources to be unavailable for use.

[0241] One embodiment of the invention uses binary data structures produced by configmc to modify flags that indicate whether a piece of hardware is usable. A modification to MC/OS prevents it from using hardware marked as broken. Another embodiment utilizes the output of the HA algorithm to produce a new configuration file input to configmc, the configmc execution is repeated with the new file, and MC/OS is configured and loaded with no knowledge of the broken hardware whatsoever. This embodiment can calculate an optimal routing table in the face of failed hardware, increasing the performance of the remaining operational components.

[0242] After the host controller has configured the compute elements 220, the runmc program loads the functional compute elements with a copy of MC/OS. Because access to the processor board 118 from a TCP/IP network is required, the host computer system acts as a connection to the TCP/IP network. The VxWorks operating system contains a fully functional TCP/IP stack. When compute elements access network resources, the host computer acts as proxy, exchanging information with the compute element utilizing DX transfers, and then making the appropriate TCP/IP calls on behalf of the compute element.

[0243] The host controller 203 needs a file system to store configuration files, executable programs, and MC/OS images. For this purpose, flash memory is utilized. Rather than have a separate flash memory from the host controller boot flash, the same flash is utilized for both bootstrap purposes and for holding file system data. The flash file system provides DOS file system semantics as well as write wear leveling.

[0244] There are in particular, two portions of code which can be remotely updated; the bootstrap code which is executed by the host controller 203 when it comes out of reset, and the rest of the code which resides on the flash file system as files.

[0245] When code is initially downloaded to the processor board 118, it is written as a group of files within a directory in the flash file system. A single top-level index tracks which directory tree is used for booting the system. This index continues to point at the existing directory tree until a download of new software is successfully completed. When a download has been completed and verified, the top-level index is updated to point to the new directory tree, the boot flash is rewritten, and the system can be rebooted.

[0246] Fault detection and reporting 820, 822 is performed by having each CPU in the system gather as much information about what it observed during a fault, and then comparing the information in order to detect which components could be the common cause of the symptoms. In some cases, it may take multiple faults before the algorithm can detect which component is at fault.

[0247] Failures within the processor board 118 can be a single point failure. Specifically, everything on the board is a single point of failure except for the compute elements. This means that the only hard failures that can be configured out are failures in the compute elements 220. However, many failures are transient or soft, and these can be recovered from with a reboot cycle.

[0248] In the case of hard failure of a compute element 220, the application executes with reduced demand for computing resources. For example, the application may work with a smaller number of interference sources, or perform interference cancellation iterations, but still within a tolerance.

[0249] Failure of more than a single compute element will cause the board to be inoperative. Therefore, the application only needs to handle two configurations: all compute elements functional and 1 compute element unavailable. Note that the single crossbar means that there are no issues as to which processes need to go on which processors—the bandwidth and latencies for any node to any other node are identical on the processor board, although other methods and techniques can be used.

[0250] DSP Connected to Processing Board

[0251] FIG. 9 shows an embodiment of the invention wherein a digital signal processor (DSP) 900 is connected with the processor board 118. Such configuration enables a DSP to communicate via DMA with processor board. One skilled in the art can appreciate that DMA transfers can be faster than bus transfers, and hence, throughput can be increased. Shown, is a DSP processor, a buffer, a FPGA and a crossbar.

[0252] The DSP 900 generates a digital signal corresponding to an analog input, e.g., a rake receiver. The DSP 900 operates in real-time, hence, the output is clocked to perform transfers of the digital output. In the illustrated embodiment, the DSP can be a Texas Instruments model TMS320C67XX series, however, other DSP processors are commercially available which can satisfy the methods and systems herein.

[0253] A buffer 902 is coupled with the DSP 900, and receives and send data in a First-In First-Out (e.g., queue) fashion, also referred to as a FIFO buffer. The buffer 902, in some embodiments, can be dual-ported RAM of sufficient size to capture data transfers. One skilled in the art can appreciate, however, that a protocol can be utilized to transfer the data where the buffer or dual-ported RAM is smaller that the data transfer size.

[0254] A FPGA 904 is coupled with both the buffer 902 and an crossbar 906 (which can be the same crossbar coupled with the compute elements 220 and host controller 203). The FPGA 904 moves data from the buffer 902 to the crossbar 906, which subsequently communicates the data to further devices, e.g., a RACEway™ or the host controller 203 or compute elements 220. The FPGA 904 also perform data transfers directly from the DSP 900 to the crossbar 906. This method is utilized in some embodiments where data transfer sizes can be accommodated without buffering, for instance, although either the buffer or direct transfers can be used.

[0255] The DSP 900 contains at least one external memory interface (EMIF) 908 device, which is connected to the buffer 902 or dual-ported RAM. RACEway™ transfers actually access the RAM, and then additional processing takes place within the DSP to move the data to the correct location in SDRAM within the DSP. In embodiments where the RAM is smaller that the data transfer size, then there is a massaging protocol between two endpoint DSPs exchanging messages, since the message will be fragmented to be contained within the buffer or RAM.

[0256] As more RACEway™ endpoints are added (for instance, to increase speed or throughput), the size of the dual-port RAM can be increased to a size of 2*F*N*P buffers of size F, where F is the fragment size, N is the number of RACEway™ endpoints in communication with the DSP, and P is the number of parallel transfers which can be active on an endpoint. The constant 2 represents double buffering so one buffer can be transferred to the RACEway™ simultaneously with a buffer being transferred to the DSP. One skilled in the art can appreciate that the constant can be four times rather than two times to emulate a full-duplex connection. With a 4 mode system, this could be, for example, 4*8K*4*4 or 512 Kbytes, plus a overhead factor for configuration and data tracking.

[0257] The FPGA 904 can program the DMA controller 910 within the DSP 900 to move data between the buffer 902 and the DSP/SDRAM 912 directly from a DSP host port 914. The host port 914 is a peripheral like the EMIF 908, but can master transfers into the DSP data-paths, e.g., it can read and write any location within the DSP. Hence, the host port 914 can access the DMA controller, 910 and can be used to initiate transfers via the DMA engine. One skilled in the art can appreciate that using this architecture, RACEway™ transfers can be initiated without the cooperation of the DSP, the thus, the DSP is free to continue processing while transfers take place and further, there is no need for protocol messaging within the buffer.

[0258] The FPGA 904 can also perform fragmentation of data. In embodiments where the buffer device is a dual-port RAM, the FPGA 904 an program the DMA controller within the DSP to move fragments into or out-of the DSP. This method can be used to match throughput of the external transfer bus, e.g., the RACEway™.

[0259] An example of the methods and systems described for a DSP, is as follows. In an embodiment where the RACEway™ reads date out of the DSP memory 912, this example assumes that another DSP is reading the SDRAM of the local DSP. The FPGA 904 detects a RACEway™ data packet arriving, and decodes the packet to determine that is contains instructions for a data-read at, for example, memory location 0x10000. The FPGA 904 writes over the host port interface 914 to program the DMA controller 910 to transfer data starting at memory location 0x10000, which refers to a location in the primary EMIF 908 corresponding to a location in the SDRAM 912, and to move that data to a location in the secondary EMIF (e.g., the buffer device) 902. As data arrives in the buffer 902, the FPGA 904 reads the data out of the buffer, and moves it onto the RACEway™ bus. When a predetermined block of data is moved, the DMA controller 910 finishes the transfer, and the FPGA 904 finishes moving the data from the buffer 902 to the RACEway™.

[0260] Another example assumes that another DSP is requesting a write instruction to the local DSP. Here, the FPGA 904 detects a data packet arriving, and determines that is it a write to location 0x20000, for instance. The FPGA 904 fills some amount of the buffer 902 with the data from the RACEway™ bus, and then writes over the host port 914 interface to program the DMA controller 910. The DMA controller 910 then transfers data from the buffer device 902 and writes that data to the primary EMIF 908 at address 0x20000. At the conclusion of the transfer, an interrupt can be sent to the DSP 900 to indicate that a data packet has arrived, or a polling of a location in the SDRAM 912 can accomplish the same requirement.

[0261] These two examples are non-limiting example, and other embodiments can utilize different methods and devices for the transfer of data between devices. For example, if the DSP 900 utilizes RapidIO interfaces, the buffer 902 and FPGA 904 can be modified to accommodate this protocol. Also, the crossbar 906 illustrated may be in common with a separate bus structure, or be in common with the processor board 118 described above. Even further, in some embodiments, the FPGA 904 can be directly coupled with the board processor, or be configured as a compute node 220.

[0262] Therefore, as can be understood by one skilled in the art, the methods and systems herein are suited for multiple user detection within base stations, and can be used to accommodate both short-code and long-code receivers.

[0263] Short-Code Processing

[0264] In one embodiment of the invention using short-code receivers, a possible mapping of matrices necessary for short-code mapping is now discussed. In order to perform MUD at the symbol rate, the correlation between the user channel-corrupted signature waveforms must be calculated. These correlations are stored as elements in matrices, here referred to as R-matrices. Because the channel is continually changing, the correlations need be updated in real-time.

[0265] The implementation of MUD at the symbol rate can be divided into two functions. The first function is the calculation of the R-matrix elements. The second function is interference cancellation, which relies on knowledge of the R-matrix elements. The calculation of these elements and the computational complexity are described in the following section. Computational complexity is expressed in Giga-Operations Per Second (GOPS). The subsequent section describes the MUD IC function. The method of interference cancellation employed is Multistage Decision Feedback IC (MDFIC).

[0266] The R-matrix calculations can be divided into three separate calculations, each with an associated time constant for real-time operation, as follows:

[0267] $\begin{array}{c}{r}_{\mathrm{lk}}\left[m^{\prime }\right]=\sum _{q=1}^L\sum _{q^{\prime }=1}^L\mathrm{Re}[a_{\mathrm{lq}}^{*}{a}_{\mathrm{kq}}·\frac{1}{2N_l}\sum _n\sum _{p}g\left[\left(n-p\right)N_c+m^{\prime }T+{\tau }_{\mathrm{lq}}-{\tau }_{{\mathrm{lq}}^{\prime }}\right]\\ c_k\left[p\right]·c_l^{*}\left[n\right]\\ =r_{\mathrm{lk}}\left[m^{\prime }\right]=\sum _{q=1}^L\sum _{q^{\prime }=1}^L\mathrm{Re}\left[a_{\mathrm{lq}}^{*}{a}_{\mathrm{kq}}·c_{{\mathrm{lkqq}}^{\prime }}\left[m^{\prime }\right]\right]\\ C_{{\mathrm{lkqq}}^{\prime }}\left[m^{\prime }\right]\equiv \frac{1}{2N_l}\sum _n\sum _{p}g\left[\left(n-p\right)N_c+m^{\prime }T+{\tau }_{\mathrm{lq}}-{\tau }_{{\mathrm{lq}}^{\prime }}\right]c_k\left[p\right]·c_l^{*}\left[n\right]\\ =\frac{1}{2N_l}\sum _n\sum _{p}g\left[{\mathrm{mN}}_c+m^{\prime }T+{\tau }_{\mathrm{lq}}-{\tau }_{{\mathrm{lq}}^{\prime }}\right]\sum _n{c}_k\left[n-m\right]·c_l^{*}\left[n\right]\\ =\frac{1}{2N_l}\sum _n\sum _{p}g\left[{\mathrm{mN}}_c+m^{\prime }T+{\tau }_{\mathrm{lq}}-{\tau }_{{\mathrm{lq}}^{\prime }}\right]{\Gamma }_{\mathrm{lk}}\left[m\right]\\ {\Gamma }_{\mathrm{lk}}\left[m\right]=\sum _n{c}_k\left[n-m\right]·c_l^{*}\left[n\right]\end{array}$

[0268] Where the hats are omitted otherwise indicating parameter estimates. Hence we must calculate the R-matrices, which depend on the C-matrices, which in turn, depend on the Γ-matrix. The Γ-matrix has the slowest time constant. This matrix represents the user code correlations for all values of offset m. For a case of 100 voice users the total memory requirement is 21 MBytes based on two bytes (real and imaginary parts) per element. This matrix is updated only when new codes (e.g., new users) are added to the system. Hence this is essentially a static matrix. The computational requirements are negligible.

[0269] The most efficient method of calculation depends on the non-zero length of the codes. For high data-rate users the non-zero length of the codes is only 4-chips long. For these codes, a direct convolution is the most efficient method to calculation the elements. For low data-rate users it is more efficient to calculation the elements using the FFT to perform the convolutions in the frequency domain. Further, as can be appreciated by one skilled in the art, cache memory can be used where the matrix is somewhat static compared with the update of other matrices.

[0270] The C-matrix is calculated from the Γ-matrix. These elements must be calculated whenever a user's delay lag changes. For now, assume that on average each multi-path component changes every 400 ms. The length of the g[ ] function is 48 samples. Since we are over sampling by 4, there are 12 multiply-accumulations (real × complex) to be performed per element, or 48 operations per element. When there are 100 low-rate users on the system (i.e., 200 virtual users) and a single multi path lag (of 4) changes for one user a total of (1.5)(2)KvLNv elements must be calculated. The factor of 1.5 comes from the 3 C-matrices (m′=−1, 0, 1), reduced by a factor of 2 due to a conjugate symmetry condition. The factor of 2 results because both rows and columns must be updated. The factor Nv is the number of virtual users per physical user, which for the lowest rate users is Nv=2. In total then this amounts to 230,400 operations per multi-path component per physical user. Assuming 100 physical users with 4 multi-path components per user, each changing once per 400 ms gives 230 MOPS.

[0271] The R-matrices are calculated from the C-matrices. From the equation above the R-matrix elements are

[0272] $r_{\mathrm{lk}}\left[m^{\prime }\right]=\sum _{q=1}^L\sum _{q^{\prime }=1}^L\mathrm{Re}\left[a_{\mathrm{lq}}^{*}{a}_{{\mathrm{kq}}^{\prime }}·c_{{\mathrm{lkqq}}^{\prime }}\left[m^{\prime }\right]\right]=\mathrm{Re}\left[a_l^H·C_{\mathrm{lk}}\left[m^{\prime }\right]·a_k\right]$

[0273] where a_k are L×l vectors, and C_lk[m′] are L×L matrices. The rate at which these calculations must be performed depends on the velocity of the users. The selected update rate is 1.33 ms. If the update rate is too slow such that the estimated R-matrix values deviate significantly from the actual R-matrix values then there is a degradation in the MUD efficiency.

[0274] From the above equation the calculation of the R-matrix elements can be calculated in terms of an X-matrix which represents amplitude-amplitude multiplies:

[0275] $\begin{array}{c}{r}_{\mathrm{lk}}\left[m^{\prime }\right]=\mathrm{Re}\left[\mathrm{tr}\left[a_l^H·C_{\mathrm{lk}}\left[m^{\prime }\right]·a_k\right]\right]=\mathrm{Re}\left[\mathrm{tr}\left[C_{\mathrm{lk}}\left[m^{\prime }\right]·a_k·a_l^H\right]\right]\\ =\mathrm{Re}\left[\mathrm{tr}\left[C_{\mathrm{lk}}\left[m^{\prime }\right]·X_{\mathrm{lk}}\right]\right]\\ =\mathrm{tr}\left[C_{\mathrm{lk}}^R\left[m^{\prime }\right]·X_{\mathrm{lk}}^R\right]-\mathrm{tr}\left[C_{\mathrm{lk}}^l·X_{\mathrm{lk}}^l\right]\\ X_{\mathrm{lk}}\equiv a_k·a_l^H\equiv X_{\mathrm{lk}}^R+{\mathrm{jX}}_{\mathrm{lk}}^l\\ C_{\mathrm{lk}}\left[m^{\prime }\right]\equiv C_{\mathrm{lk}}^R\left[m^{\prime }\right]+{\mathrm{jC}}_{\mathrm{lk}}^l\left[m^{\prime }\right]\end{array}$

[0276] The X-matrix multiplies can be reused for all virtual users associated with a physical user and for all m′ (i.e. m′=0, 1). Hence these calculations are negligible when amortized. The remaining calculations can be expressed as a single real dot product of length 2L 2=32. The calculations are performed in 16-bit fixed-point math. The total operations is thus 1.5(4)(KvL)2=3.84 Mops. The processing requirement is then 2.90 GOPS. The X-matrix multiplies when amortized amount to an additional 0.7 GOPS. The total processing requirement is then 3.60 GOPS.

[0277] From the equation above the matched-filter outputs are given by:

[0278] $y_l\left[m\right]=r_{\mathrm{ll}}\left[0\right]b_l\left[m\right]+\sum _{k=1}^{K_v}{r}_{\mathrm{lk}}\left[-1\right]b_k\left[m+1\right]+\sum _{k=1}^{K_v}\left[r_{\mathrm{lk}}\left[0\right]-r_{\mathrm{ll}}\left[0\right]{\delta }_{\mathrm{lk}}\right]b_k\left[m\right]+\sum _{k=1}^{K_v}{r}_{\mathrm{lk}}\left[1\right]b_k\left[m-1\right]+{\eta }_l\left[m\right]$

[0279] The first term represents the signal of interest. All the remaining terms represent Multiple Access Interference (MAI) and noise. The multiple-stage decision-feedback interference cancellation (DFIC) algorithm iteratively solves for the symbol estimates using

[0280] $\begin{array}{c}{\hat{b}}_l\left[m\right]=\mathrm{sign}\{y_l\left[m\right]-\sum _{k=1}^{K_v}{r}_{\mathrm{lk}}\left[-1\right]{\hat{b}}_k\left[m+1\right]-\\ \sum _{k=1}^{K_v}\left[r_{\mathrm{lk}}\left[0\right]-r_{\mathrm{ll}}\left[0\right]{\delta }_{\mathrm{lk}}\right]{\hat{b}}_k\left[m\right]-\sum _{k=1}^{K_v}{r}_{\mathrm{lk}}\left[1\right]{\hat{b}}_k\left[m-1\right]\}\end{array}$

[0281] with initial estimates given by hard decisions on the matched-filter detection statistics, {circumflex over (b)}_l[m]=sign{y_l[m]}. The MDFIC technique is closely related to the SIC and PIC technique. Notice that new estimates are immediately introduced back into the interference cancellation as they are calculated. Hence at any given cancellation step the best available symbol estimates are used. This idea is analogous to the Gauss-Siedel method for solving diagonally dominant linear systems.

[0282] The above iteration is performed on a block of 20 symbols, for all users. The 20-symbol block size represents two WCDMA time slots. The R-matrices are assumed to be constant over this period. Performance is improved under high input BER if the sign detector in is replaced by the hyperbolic tangent detector. This detector has a single slope parameter which is variable from iteration to iteration. Similarly, performance is improved if only a fraction of the total estimated interference is cancelled (e.g., partial interference cancellation), owing to channel and symbol estimation errors.

[0283] Multiple Processors Generating Complementary R-Matrices

[0284] The three R-matrices (R[−1], R[0] and R[1]) are each Kv×Kv in size. The total number of operation then is 6K_v² per iteration. The computational complexity of the multistage MDFIC algorithm depends on the total number of virtual users, which depends on the mix of users at the various spreading factors. For Kv=200 users (e.g. 100 low-rate users) this amounts to 240,000 operations. In the current implementation two iterations are used, requiring a total of 480,000 operations. For real-time operation these operations must be performed in 1/15 ms. The total processing requirement is then 7.2 GOPS. Computational complexity is markedly reduced if a threshold parameter is set such that IC is performed only for values |y_l[m]| below the threshold. The idea is that if |y_l[m]| is large there is little doubt as to the sign of b_l[m], and IC need not be performed. The value of the threshold parameter is variable from stage to stage.

[0285] Although three R matrices are output from the R matrix calculation function, only half of the elements are explicitly calculated. This is because of symmetry that exists between R matrices:
R_l,k=ξR_k,l(−m)

[0286] Therefore, only two matrices need to be calculated. The first one is a combination of R(1) and R(−1). The second is the R(0) matrix. In this case, the essential R(0) matrix elements have a triangular structure to them. The number of computations performed to generate the raw data for the R(1)/R(−1) and R(0) matrices are combined and optimized as a single number. This is due to the reuse of the X-matrix outer product values across the two R-matrices. Since the bulk of the computations involve combining the X-matrix and correlation values, they dominate the processor utilization. These computations are used as a cost metric in determining the optimum loading of each processor.

[0287] Processor Loading Optimization

[0288] The optimization problem is formulated as an equal area problem, where the solution results in each partition area to be equal. Since the major dimensions of the R-matrices are in terms of the number of active virtual users, the solution space for this problem is in terms of the number of virtual users per processor. By normalizing the solution space by the number of virtual users, the solution is applicable for an arbitrary number of virtual users.

[0289] FIG. 10 shows a model of the normalized optimization scenario. The computations for the R(1)/R(−1) matrix are represented by the square HJKM, while the computations for the R(0) matrix are represented by the triangle ABC. From geometry, the area of a rectangle of length b and height h is:
A_r=bh

[0290] For a triangle with a base width b and height h, the area is calculated by:

[0291] $A_t=\frac{1}{2}\mathrm{bh}$

[0292] When combined with a common height a, the formula for the area becomes:

[0293] $\begin{array}{c}{A}_i=A_{\mathrm{ri}}+A_{\mathrm{ti}}\\ =a_i{a}_e+\frac{1}{2}{a}_i^2\end{array}$

[0294] The formula for A gives the area for the total region below the partition line. For example, the formula for A2 gives the area within the rectangle HQRM plus the region within triangle AFG. For the cost function, the difference in successive areas is used. That is:

[0295] $\begin{array}{c}{B}_i=A_i-A_{i-1}\\ =\frac{1}{2}{a}_i^2+a_i-\frac{1}{2}{a}_{i-1}^2-a_{i-1}\end{array}$

[0296] For an optimum solution, the B must be equal for i=1, 2, . . . , N, where N is the number of processors performing the calculations. Because the total normalized load is equal to AN, the loading per processor load is equal to AN/N,

[0297] $B_i=\frac{A_N}{N}=\frac{A_3}{3}=\frac{3}{2N},\mathrm{for}i=1,2...,N.$

[0298] By combining the two equations for B, the solution for a_i is found by finding the roots of the equation:

[0299] $\frac{1}{2}{a}_i^2+a_i-\frac{1}{2}{a}_{i-1}^2-a_{i-1}-\frac{3}{2N}=0<$

[0300] The solution for a is:

[0301] $a_i=-1\pm \sqrt{1+a_{-1i}^2+2a_{i-1}+\frac{3}{N}},\mathrm{for}i-1,2,...,N$

[0302] Since the solution space must fall in the range [0,1], negative roots are not valid solutions to the problem. On the surface, it appears that the a must be solved by first solving for case where=1. However, by expanding the recursions of the a and using the fact that a0 equals zero, a solution that does not require previous a,=0, 1, . . . , n−1 exists. The solution is:

[0303] $a_i=-1+\sqrt{1+\frac{3i}{N}}$

[0304] As shown in the following table, the normalized partition values for two, three, and four processors. To calculate the actual partitioning values, the number of active virtual users is multiplied by the corresponding table entries. Since a fraction of a user cannot be allocated, a ceiling operation is performed that biases the number of virtual users per processor towards the processors whose loading function is less sensitive to perturbations in the number of users.

[0305]

Location	Two Processors	Three Processors	Four Processors
a1	- 1 + 5 2 ⁢ ( 0.5811 )	- 1 + 2 ⁢ ( 0.4142 )	- 1 + 7 4 ⁢ ( 0.3229 )
a2	—	- 1 + 3 ⁢ ( 0.7321 )	- 1 + 5 2 ⁢ ( 0.5811 )
a3	—	—	- 1 + 13 4 ⁢ ( 0.8028 )

[0306] One skilled in the art can appreciate that the load balancing for the R-matrix results in a non-uniform partitioning of the rows of the final matrices over a number of processors. The partition sizes increase as the partition starting user index increases. When the system is running at full capacity (e.g., all co-processors are functional, and the maximum number of users is processed while still within the bounds of real-time operation), and a co-processor fails, the impact can be significant.

[0307] This impact can be minimized by allocating the first user partition to the disabled node. Also the values that would have been calculated by that node are set to zero. This reduces the effects of the failed node. By changing which user data is set to zero (e.g., which users are assigned to the failed node) the overall errors due to the lack of non-zero output data for that node are averaged over all of the users, providing a “soft” degradation.

[0308] R,C Values Contiguous in MPIC Processor Memory

[0309] Further, via connection with the crossbar multi-port connector, the multi-processor elements calculating the R-matrix (which depends on the C-matrix, which in turn depends on the gamma-matrix) can place the results in a processor element performing the MPIC functions. For one optimal solution, the values can be placed in contiguous locations accessable (or local with) the MPIC processor. This method allows adjacent memory addresses for the R and C values, and increases throughput via simply incrementing memory pointers rather that using a random access approach.

[0310] As discussed above, the values of the Γ-matrix elements which are non-zero need to be determined for efficient storage of the Γ-matrix. For high data rate users, certain elements c_l[n] are zero, even within the interval n=0:N−1, N=256. These zero values reduce the interval over which Γ_lk[m] is non-zero. In order to determine the interval for non-zero values consider the following relations:

[0311] ${\Gamma }_{\mathrm{lk}}\left[m\right]\equiv \frac{1}{2N_l}\sum _{n=0}^{N-1}{c}_l^{*}\left[n\right]·c_k\left[n-m\right]$

[0312] The index j_l for the lth virtual user is defined such that c_l[n] is non-zero only over the interval n=j_lN_l:j_lN_l+N_l−1. Correspondingly, the vector c_k[n] is non-zero only over the interval n=j_kN_k:j_kN_k+N_k−1. Given these definitions, Γ_lk[m] can be rewritten as

[0313] ${\Gamma }_{\mathrm{lk}}\left[m\right]\equiv \frac{1}{2N_l}\sum _{n=0}^{N_l-1}{c}_l^{*}\left[n+j_l{N}_l\right]·c_k\left[n+j_l{N}_l-m\right]$

[0314] The minimum value of m for which Γ_lk[m] is non-zero is
m_{min 2}=−j_kN_k+j_lN_l−N_k+1

[0315] and the maximum value of m for which Γ_lk[m] is non-zero is
m_{max 2}=N_l−1−j_kN_k+j_lN_l

[0316] The total number of non-zero elements is then

[0317] $\begin{array}{c}{m}_{\mathrm{total}}\equiv m_{\max 2}-m_{\min 2}+1\\ =N_l+N_k-1\end{array}$

[0318] The table below provides a sample of the the number of bytes per l,k virtual-user pair based on 2 bytes per element—one byte for the real part and one byte for the imaginary part. In other embodiments, these values vary.

[0319]

	Nk = 256	128	64	32	16	8	4
Nl = 256	1022	766	638	574	542	526	518
128	766	510	382	318	286	270	262
64	638	382	254	190	158	142	134
32	574	318	190	126	94	78	70
16	542	286	158	94	62	46	38
8	526	270	142	78	46	30	22
4	518	262	134	70	38	22	14

[0320] The memory requirements for storing the Γ-matrix for a given number of users at each spreading factor can be determined as described below. For example, for K_q virtual users at spreading factor N_q≡2^8−q, q=0:6, where K_q is the qth element of the vector K (some elements of K may be zero), the storage requirement can be computed as follows. Let the table above be stored in matrix M with elements M_qq′For example, M₀₀=1022, and M₀₁=766. The total memory required by the Γ matrix in bytes is then given by the following relation

[0321] $\begin{array}{cc}\begin{array}{c}{M}_{\mathrm{bytes}}=\sum _{q=0}^6\left\{\frac{K_q\left(K_q+1\right)}{2}{M}_{\mathrm{qq}}+\sum _{q^{\prime }=q+1}^6{K}_q{K}_{q^{\prime }}{M}_{{\mathrm{qq}}^{\prime }}\right\}\\ =\frac{1}{2}\sum _{q=0}^6\left\{K_q{M}_{\mathrm{qq}}+\sum _{q^{\prime }=0}^6{K}_q{K}_{q^{\prime }}{M}_{{\mathrm{qq}}^{\prime }}\right\}\end{array}& \left(27\right)\end{array}$

[0322] Then, continuing the example, for 200 virtual users at spreading factor N₀=256, K_q=200δ_q0, which in turn results in M_bytes=½K₀(K₀+1)M₀₀=100(201)(1022)=20.5 MB. For 10 384 Kbps users, K_q=K₀δ_q0+K₆δ_q6 with K₀=10 and K₆=640, which results in a storage requirement that is given by the following relations:

[0323] $M_{\mathrm{bytes}}=\frac{1}{2}{K}_0\left(K_0+1\right)M_{00}+K_0{K}_6{M}_{06}+\frac{1}{2}{K}_6\left(K_6+1\right)M_{66}=5\left(11\right)\left(1022\right)+10\left(640\right)\left(518\right)+320\left(641\right)\left(14\right)=6.2\mathrm{MB}.$

[0324] The Γ-matrix data can be addressed, stored, and accessed as described below. In particular, for each pair (l,k), k>=l, there are 1 complex Γ_lk[m] values for each value of m, where m ranges from m_{min 2} to m_{max 2}, and the total number of non-zero elements is m_total=m_{max 2}−m_{min 2}+1. Hence, for each pair (l,k), k>=l, there exists 2m_total time-contiguous bytes.

[0325] In one embodiment, an array structure is created to access the data, as shown below:

[0326]

	struct {
	int m_min2;
	int m_max2;
	int m_total;
	char * Glk;
	} G_info[N_VU_MAX][N_VU_MAX];

[0327] The C-matrix data can then be retrieved by utilizing the following exemplary algorithm:

[0328]

	mmin2 = G_info[l][k].m_min2
	mmax2 = G_info[l][k].m_max2
	Ng = Lg/Nc
	NI = m'*N − Lg/(2Nc)
	for m' = 0:1
	for q = 0:L−1
	for q' = 0:L−1
	τ = m'T + τlq − τkq'
	mmin1 = N1 − nlq + nkq'
	mmax1 = mminl + Ng
	mmin = max[mmin1 , mmin2]
	mmax = min[mmax1 , mmax2]
	if mmax >= mmin
	mspan = mmax − mmin + 1
	sum1 = 0.0;
	ptr1 = &G_info[l][k].Glk[mmin]
	ptr2 = &g[mmin * Nc + τ]
	while mspan > 0
	sum1 += (*ptr1++) * (*ptr2++)
	mspan--
	end
	C[m'][l][k][q][q'] = sum1
	end
	end
	end
	end

[0329] A direct method for calculating the C-matrix (in symmetry) is performance of the following equation:

[0330] $C_{{\mathrm{klq}}^{\prime }q}\left[m^{\prime }\right]=\frac{N_l}{N_k}{C}_{{\mathrm{lkqq}}^{\prime }}^{*}\left[m^{\prime }\right]$

[0331] Due to symmetry, there are 1.5(K_VL)² elements to calculate. Assuming all users are at SF 256, each calculation requires 256 cmacs, or 2048 operations. The probability that a multipath changes in a 10 ms time period is approximately 10/200=0.05 if all users are at 120 kmph. Assuming a mix of user velocities, a reasonable probability is 0.025. Because the C-matrix represents the interaction between two users, the probability that C-matrix elements change in a 10 ms time period is approximately 0.10 for all users at 120 kmph, or 0.05 for a mix of users velocities. Hence, the GOPS are shown in the following table.

[0332]

	High velocity
KV	users	1.5(KVL)2	Gops	Percentage change	GOPS
200	100%	960,000	1.966	20	39.3
200	50%	960,000	1.966	15	29.5
128	100%	393,216	0.805	20	16.1
128	50%	393,216	0.805	15	12.1

[0333] One skilled in the art can appreciate that a fast fourier transform (FFT) can be used to calculate the correlations for a range of offsets, tau, using:

[0334] $\begin{array}{c}{C}_{{\mathrm{klq}}^{\prime }q}\left[m^{\prime }\right]=\frac{1}{2N_l}\sum _n{s}_k\left[{\mathrm{nN}}_c+m^{\prime }T+{\hat{\tau }}_{\mathrm{lq}}-{\hat{\tau }}_{{\mathrm{lq}}^{\prime }}\right]·c_l^{*}\left[n\right]\\ =C_{\mathrm{lk}}\left[{\tau }_{{\mathrm{lkqq}}^{\prime }}\left[m^{\prime }\right]\right]\\ C_{\mathrm{lk}}\left[\tau \right]\equiv \frac{1}{2N_l}\sum _n{s}_k\left[{\mathrm{nN}}_c+\tau \right]·c_l^{*}\left[n\right]\\ {\tau }_{{\mathrm{lkqq}}^{\prime }}\left[m^{\prime }\right]\equiv m^{\prime }T+{\hat{\tau }}_{\mathrm{lq}}-{\hat{\tau }}_{{\mathrm{lq}}^{\prime }}\end{array}$

[0335] The length of the waveform sk[t] is Lg+255N_C=1068 for L_g=48 and N_C=4. This is represented as N_C waveforms of length L_g/N_C+255=267. One advantage of this approach is that elements can be stored for a range of offsets tau so that calculations do not need to be performed when lags change. For delay spreads of about 4 micro-seconds 32 samples need to be stored for each m′.

[0336] The C-matrix elements need be updated when the spreading factor changes. The spreading factor can change du to AMR codec rate changes, multiplexing of the dedicated channels, or multiplexing of data services, to name a few reasons. It is reasonable to assume that 5% of the users, hence 10% of the elements, change every 10 ms.

[0337] Gamma-Matrix Generated in FPGA

[0338] The C-matrix elements can be represented in terms of the underlying code correlations using:

[0339] $\begin{array}{c}{C}_{{\mathrm{klq}}^{\prime }q}\left[m^{\prime }\right]=\frac{1}{2N_l}\sum _n{s}_k\left[{\mathrm{nN}}_c+m^{\prime }T+{\hat{\tau }}_{\mathrm{lq}}-{\hat{\tau }}_{{\mathrm{lq}}^{\prime }}\right]·c_l^{*}\left[n\right]\\ =\sum _{m}g\left[{\mathrm{mN}}_c+\tau \right]·{\Gamma }_{\mathrm{lk}}\left[m\right]\\ {\Gamma }_{\mathrm{lk}}\left[m\right]=\frac{1}{2N_l}\sum _n{c}_l^{*}\left[n\right]·c_k\left[n-m\right]\\ \tau \equiv m^{\prime }T+{\hat{\tau }}_{\mathrm{lq}}-{\hat{\tau }}_{{\mathrm{lq}}^{\prime }}\end{array}$

[0340] If the length of g[t] is Lg=48 and Nc=4, then the summation over m requires 48/4=12 macs for the real part and 12 macs for the imaginary part. The total ops is then 48 ops per element. (Compare with 2048 operations for the direct method.) Hence for the case where there are 200 virtual users and 20% of the C-matrix needs updating every 10 ms the required complexity is (960000 el)(48 ops/el)(0.20)/(0.010 sec)=921.6 MOPS. This is the required complexity to compute the C-matrix from the Tau-matrix. The cost of computing the Tau-matrix must also be considered. The Tau-matrix can be efficiently computed since the fundamental operation is a convolution of codes with elements constrained to be +/−1+/−j. Further, the Tau-matrix can be calculated using modulo-2 addition (e.g., XOR) using several method, e.g. register shifting, XOR logic gates, and so on.

[0341] The Gamma matrix (Γ) represents the correlation between the complex user codes.

[0342] The complex code for user l is assumed to be infinite in length, but with only N_l non-zero values. The non-zero values are constrained to be ±1±j. The Γ-matrix can be represented in terms of the real and imaginary parts of the complex user codes, and is based on the relationship:

[0343] ${\Gamma }_{\mathrm{lk}}^{\mathrm{XY}}\left[m\right]\equiv \frac{1}{2N_l}\left\{M_{\mathrm{lk}}^{\mathrm{XY}}\left[m\right]-2N_{\mathrm{lk}}^{\mathrm{XY}}\left[m\right]\right\}$ $M_{\mathrm{lk}}^{\mathrm{XY}}\left[m\right]\equiv \sum _n·m_l^X\left[n\right]·m_k^Y\left[n-m\right]$ $N_{\mathrm{lk}}^{\mathrm{XY}}\left[m\right]\equiv \sum _n\left({\gamma }_l^X\left[n\right]\oplus {\gamma }_k^Y\left[n-m\right]\right)·m_l^X\left[n\right]·m_k^Y\left[n-m\right]$

[0344] which can be performed using a dual-set of shift registers and a logical circuit containing modulo-2 (e.g., Exclusive-OR “XOR”) logic elements. Further, one skilled in the art can appreciate that such a logic device can be implemented in a field programmable gate array, which can be programmed via the host controller, a compute element, or other device including an application specific integrated circuit. Further, the FPGA can be programmed via the RACEway™ bus, for example.

[0345] The above shift registers together with a summation device calculates the functions M_lk^XY[m] and N_lk^XY[m]. The remaining calculations to form Γ_lk^XY[m] and subsequently Γ_lk[m] can be performed in software. Note that the four functions Γ_lk^XY[m] corresponding to X, Y=R,I which are components of can be calculated in parallel. For K_V=200 virtual users, and assuming that 10% of all (l,k) pairs must be calculated in 2 ms, then for real-time operation we must calculate 0.10(200)²=4000 elements (all shifts) in 2 ms, or about 2M elements (all shifts) per second. For K_V=128 virtual users the requirement drops to 0.8192M elements (all shifts) per second.

[0346] In what has been presented the elements are calculated for all 512 shifts. Not all of these shifts are needed, so it is possible to reduce the number of calculations per elements. The cost is increased design complexity.

[0347] Therefore, a possible loading scenario for performing short-code multiple user detection on the hardware described herein is illustrated in FIG. 11. A processor board 118 with four compute elements 220 can be used as shown. Three of the compute nodes (e.g., 220a–220c) can be used to calculate the C-matrix and R-matrix. One of the compute nodes (e.g., 220d) can be used for multiple-stage decision-feedback interference cancellation (MDFIC) techniques. The Tau-Matrix and R-Matrix is calculated using FPGA's that can be programmed by the host controller 203, or ASICs. Further, multiuser amplitude estimation is performed within the modem card 112.

[0348] Long-Code Processing

[0349] Therefore it can be appreciated by one skilled in the art that short-code MUD can be performed using the system architecture described herein. FIG. 12 shows a preferred embodiment for long-code MUD processing. In this embodiment, each frame of data is processed three times by the MUD processor, although it can be recognized that multiple processors can perform the iterative nature of the embodiment. During the first pass, only the control channels are respread which the maximum ratio combination (MRC) and MUD processing is performed on the data channels. During subsequent passes, data channels are processed exclusively. New y (i.e., soft decisions) and b (i.e., hard decisions) data are derived as shown in the diagram.

[0350] Amplitude ratios and amplitudes are determined via the DSP (e.g., element 900, or a DSP otherwise coupled with the processor board 118 and receiver 110), as well as certain waveform statistics. These values (e.g., matrices and vectors) are used by the MUD processor in various ways. The MUD processor is decomposed into four stages that closely match the structure of the software simulation: Alpha Calculation and Respread 1302, raised-cosine filtering 1304, de-spreading 1306, and MRC 1308. Each pass through the MUD processor is equivalent to one processing stage of the software implementation. The design is pipelined and “parallelized.” In the illustrated embodiment, the clock speed can be 132 MHz resulting in a throughput of 2.33 ms/frame, however, the clock rate and throughput varies depending on the requirements. The illustrated embodiment allows for three-pass MUD processing with additional overhead from external processing, resulting in a 4-times real-time processing throughput.

[0351] The alpha calculation and respread operations 1302 are carried out by a set of thirty-two processing elements arranged in parallel. These can be processing elements within an ASIC, FPGA, PLD or other such device, for example. Each processing element processes two users of four fingers each. Values for b are stored in a double-buffered lookup table. Values of a(hat) and ja(hat) are pre-multiplied with beta by an external processor and stored in a quad-buffered lookup table. The alpha calculation state generated the following values for each finger, where subscripts indicate antenna identifier:

[0352] $\begin{array}{c}{\alpha }_0={\beta }_0·\left(C·{\hat{a}}_0-\mathrm{jC}·j{\hat{a}}_0\right)\\ j{\alpha }_0={\beta }_0·\left(\mathrm{jC}·{\hat{a}}_0+C·j{\hat{a}}_0\right)\\ \mathrm{\alpha 1}={\beta }_1·\left(C·{\hat{a}}_1-\mathrm{jC}·j{\hat{a}}_1\right)\\ j{\alpha }_1={\beta }_1·\left(\mathrm{jC}·{\hat{a}}_1+C·j{\hat{a}}_1\right)\end{array}$

[0353] These values are accumulated during the serial processing cycle into four independent 8-times oversampling buffers. There are eight memory elements in each buffer and the element used is determined by the sub-chip delay setting for each finger.

[0354] Once eight fingers have been accumulated into the oversampling buffer, the data is passed into set of four independent adder-trees. These adder-trees each termination in a single output, completing the respread operation.

[0355] The four raised-cosine filters 1304 convolve the alpha data with a set of weights determined by the following equation:

[0356] $g_{\mathrm{rc}}\left(t\right)=\frac{\sin \left(\pi \frac{1}{t}\right)·\cos \left(\mathrm{\alpha \pi }\frac{1}{T}\right)}{\pi \frac{1}{t}\left(1-{\left(2\alpha \frac{1}{T}\right)}^2\right)}$

[0357] The filters can be implemented with 97 taps with odd symmetry. The filters illustrated run at 8-times the chip rate, however, other rates are possible. The filters can be implemented in a variety of compute elements 220, or other devices such as ASICs, FPGAs for example.

[0358] The despread function 1306 can be performed by a set of thirty-two processing elements arranged in parallel. Each processing element serially processes two users of four fingers each.

[0359] For each finger, one chip value out of eight, selected based on the sub-chip delay, is accepted from the output of the raised-cosine filter. The despread state performs the following calculations for each finger (subscripts indicate antenna):

[0360] $\begin{array}{c}{y}_0=\sum _0^{\mathrm{SF}-1}C·r_0+\mathrm{jC}·{\mathrm{jr}}_0\\ {\mathrm{jy}}_0=\sum _0^{\mathrm{SF}-1}C·{\mathrm{jr}}_0-\mathrm{jC}·r_0\\ y_1=\sum _0^{\mathrm{SF}-1}C·r_1+\mathrm{jC}·{\mathrm{jr}}_1\\ {\mathrm{jy}}_1=\sum _0^{\mathrm{SF}-1}C·{\mathrm{jr}}_1-\mathrm{jC}·r_1\end{array}$

[0361] The MRC operations are carried out by a set of four processing elements arranged in parallel, such as the compute elements 220 for example. Each processor is capable of serially processing eight users of four fingers each. Values for y are stored in a double-buffered lookup table. Values for b are derived from the MSB of the y data. Note that the b data used in the MUD stage is independent of the b data used in the respread stage. Values of â and j â<are pre-multiplied with β by an external processor and stored in a quad-buffered lookup table. Also, Σ(â²+j â²) for each channel is stored in a quad-buffered table.

[0362] The output stage contains a set of sequential destination buffer pointers for each channel. The data generated by each channel, on a slot basis, is transferred to the RACEway™ destination indicated by these buffers. The first word of each of these transfers will contain a counter in the lower sixteen bits indicating how many y values were generated. The upper sixteen bits will contain the constant value 0xAA55. This will allow the DSP to avoid interrupts by scanning the first word of each buffer.

[0363] In addition, the DSP_UPDATE register contains a pointer to single RACEway™ location. Each time a slot or channel data is transmitted, an internal counter is written to this location. The counter is limited to 10 bits and will wrap around with a terminal count value of 1023.

[0364] The method of operation for the long-code multiple user detection algorithm (LCMUD) is as follows. Spread factor for four-channels requires significant amount of data transfer. In order to limit the gate count of the hardware implementation, processing an SF4 channel can result in reduced capability.

[0365] A SF4 user can be processed on certain hardware channels. When one of these special channels is operating on an SF4 user, the next three channels are disabled and are therefore unavailable for processing. This relationship is as shown in the following table:

[0366]

SF4 Chan	Disabled Channels	SF4 Chan	Disabled Channels
0	1, 2, 3	32	33, 34, 35
4	5, 6, 7	36	37, 38, 39
8	9, 10, 11	40	41, 42, 43
12	12, 14, 15	44	45, 46, 47
16	17, 18, 19	48	49, 50, 51
20	21, 22, 23	52	53, 54, 55
24	25, 26, 27	56	57, 58, 59
28	29, 30, 31	60	61, 62, 63

[0367] The default y and b data buffers do not contain enough space for SF4 data. When a channel is operating on SF4 data, the y and b buffers extend into the space of the next channel in sequence. For example, if channel 0 is processing SF data, the channel 0 and channel 1 b buffers are merged into a single large buffer of 0x40 32-bit words. The y buffers are merged similarly.

[0368] In typical operation, the first pass of the LCMUD algorithm will respread the control channels in order to remove control interference. For this pass, the b data for the control channels should be loaded into BLUT while the y data for data channels should be loaded into YDEC. Each channel should be configured to operate at the spread factor of the data channel stored into the YDEC table.

[0369] Control channels are always operated at SF 256, so it is likely that the control data will need to be replicated to match the data channel spread factor. For example, each bit (b entry) of control data would be replicated 64 times if that control channel were associated with an SF4 data channel.

[0370] Each finger in a channel arrives at the receiver with a different delay. During the Respread operation, this skew among the fingers is recreated. During the MRC stage of MUD processing, it is necessary to remove this skew and realign the fingers of each channel.

[0371] This is accomplished in the MUD processor by determining the first bit available from the most delayed finger and discarding all previous bits from all other fingers. The number of bits to discard can be individually programmed for each finger with the Discard field of the MUDPARAM registers.

[0372] This operation will typically result in a ‘short’ first slot of data. This is unavoidable when the MUD processor is first initialized and should not create any significant problems. The entire first slot of data can be completely discarded if ‘short’ slots are undesirable.

[0373] A similar situation will arise each time processing is begun on a frame of data. To avoid losing data, it is recommended that a partial slot of data from the previous frame be overlapped with the new frame. Trimming any redundant bits created this way can be accomplished with the Discard register setting or in the system DSP. In order to limit memory requirements, the LCMUD FPGA processes one slot of data at a time. Doubling buffering is used for b and y data so that processing can continue as data is streamed in. Filling these buffers is complicated by the skew that exists among fingers in a channel.

[0374] FIG. 13 illustrates the skew relationship among fingers in a channel and among the channels themselves. The illustrated embodiment allows for 20 us (77.8 chips) of skew among fingers in a channel and certain skew among channels, however, in other embodiments these skew allowances vary.

[0375] There are three related problems that are introduced by skew: Identifying frame & slot boundaries, populating b and y tables and changing channel constants.

[0376] Because every finger of every channel can arrive at a different time, there are no universal frame and slot boundaries. The DSP must select an arbitrary reference point. The data stored in b & y tables is likely to come from two adjacent slots.

[0377] Because skew exists among fingers in a channel, it is not enough to populate the b & y tables with 2,560 sequential chips of data. There must be some data overlap between buffers to allow lagging channels to access “old” data. The amount of overlap can be calculated dynamically or fixed at some number greater than 78 and divisible by four (e.g. 80 chips). The starting point for each register is determined by the Chip Advance field of the MUDPARAM register.

[0378] A related problem is created by the significant skew among channels. As can be seen in FIG. 13, Channel 0 is receiving Slot 0 while Channel 1 is receiving Slot 2. The DSP must take this skew into account when generating the b and y tables and temporally align channel data.

[0379] Selecting an arbitrary “slot” of data from a channel implies that channel constants tied to the physical slot boundaries may change while processing the arbitrary slot. The Constant Advance field of the MUDPARAM register is used to indicate when these constants should change.

[0380] Registers affected this way are quad-buffered. Before data processing begins, at least two of these buffers should be initialized. During normal operation, one additional buffer is initialized for each slot processed. This system guarantees that valid constants data will always be available.

[0381] The following two tables shown the long-code MUD FPGA memory map and control/status register:

[0382]

Start Addr	End Addr	Name	Description
0000_0000	0000_0000	CSR	Control & Status Register
0000_0008	0000_000C	DSP_UPDATE	Route & Address for DSP updating
0001_0000	0001_FFFF	MUDPARAM	MUD Parameters
0002_0000	0002_FFFF	CODE	Spreading Codes
0003_0000	0004_FFFF	BLUT	Respread: b Lookup Table
0005_0000	0005_FFFF	BETA_A	Respread: Beta * a_hat Lookup Table
0006_0000	0007_FFFF	YDEC	MUD & MRC: y Lookup Table
0008_0000	0008_FFFF	ASQ	MUD & MRC: Sum a_hat squared LUT
000A_0000	000A_FFFF	OUTPUT	Output Routes & Addresses

[0383]

Bit	31	30	29	28	27	26	25	24	23	22	21	20	19	18	17	16
Name	Reserved
R/W	RO
Reset	X	X	X	X	X	X	X	X	X	X	X	X	X	X	X	X
Bit	15	14	13	12	11	10	9	8	7	6	5	4	3	2	1	0
Name	Reserved	YB	CBUF	A1	A0	R1	R0	Lst	Rst
R/W	RO	RO	RO	RO	RO	Rw	Rw	Rw	Rw
Reset	X	X	X	X	X	X	X	0	0	0	0	0	0	0	0	0

[0384] The register YB indicated which of two y and b buffers are in use. If the system is currently not processing, YB indicated the buffer that will be used when processing is initiated.

[0385] CBUF indicates which of four round-robin buffers for MUD constants (a^ beta) is currently in use. Finger skew will result in some fingers using a buffer one in advance of this indicator. To guarantee that valid data is always available, two full buffers should be initialized before operation begins.

[0386] If the system is currently not processing, CBUF indicates the buffer that will be used when processing is restarted. It is technically possible to indicate precisely which buffer is in use for each finger in both the Respread and Despread processing stages. However, this would require thirty-two 32-bit registers. Implementing these registers would be costly, and the information is of little value.

[0387] A1 and A0 indicate which y and b buffers are currently being processed. A1 and A0 will never indicate ‘1’ at the same time. An indication of ‘0’ for both A1 and A0 means that MUD processor is idle.

[0388] R1 and R0 are writable fields that indicate to the MUD processor that data is available. R1 corresponds to y and b buffer 1 and R0 corresponds to y and b buffer 0. Writing a ‘1’ into the correct register will initiate MUD processing. Note that these buffers follow strict round-robin ordering. The YB register indicates which buffer should be activated next.

[0389] These registers will be automatically reset to ‘0’ by the MUD hardware once processing is completed. It is not possible for the external processor to force a ‘0’ into these registers.

[0390] A ‘1’ in this bit indicates that this is the last slot of data in a frame. Once all available data for the slot has been processed, the output buffers will be flushed.

[0391] A ‘1’ in this bit will place the MUD processor into a reset state. The external processor must manually bring the MUD processor out of reset by writing a ‘0’ into this bit.

[0392] DSP_UPDATE is arranged as two 32-bit registers. A RACEway™ route to the MUD DSP is stored at address 0x0000_—0008. A pointer to a status memory buffer is located at address 0x0000_—000C.

[0393] Each time the MUD processor writes a slot of channel data to a completion buffer, an incrementing count value is written to this address. The counter is fixed at 10 bits and will wrap around after a terminal count of 1023.

[0394] A quad-buffered version of the MUD parameter control register exists for each finger to be processed. Execution begins with buffer 0 and continues in round-robin fashion. These buffers are used in synchronization with the MUD constants (Beta * a_hat, etc.) buffers. Each finger is provided with an independent register to allow independent switching of constant values at slot and frame boundaries. The following table shows offsets for each MUD channel:

[0395]

	Offset	User
	0x0000	0
	0x0040	1
	0x0080	2
	0x00C0	3
	0x0100	4
	0x0140	5
	0x0180	6
	0x01C0	7
	0x0200	8
	0x0240	9
	0x0280	10
	0x02C0	11
	0x0300	12
	0x0340	13
	0x0380	14
	0x03C0	15
	0x0400	16
	0x0440	17
	0x0480	18
	0x04C0	19
	0x0500	20
	0x0540	21
	0x0580	22
	0x05C0	23
	0x0600	24
	0x0640	25
	0x0680	26
	0x06C0	27
	0x0700	28
	0x0740	29
	0x0780	30
	0x07C0	31
	0x0800	32
	0x0840	33
	0x0880	34
	0x08C0	35
	0x0900	36
	0x0940	37
	0x0980	38
	0x09C0	39
	0x0A00	40
	0x0A40	41
	0x0A80	42
	0x0AC0	43
	0x0B00	44
	0x0B40	45
	0x0B80	46
	0x0BC0	47
	0x0C00	48
	0x0C40	49
	0x0C80	50
	0x0CC0	51
	0x0D00	52
	0x0D40	53
	0x0D80	54
	0x0DC0	55
	0x0E00	56
	0x0E40	57
	0x0E80	58
	0x0EC0	59
	0x0F00	60
	0x0F40	61
	0x0F80	62
	0x0FC0	63

[0396] The following table shows buffer offsets within each channel:

[0397]

	Offset	Finger	Buffer
	0x0000	0	0
	0x0004		1
	0x0008		2
	0x000C		3
	0x0010	1	0
	0x0014		1
	0x0018		2
	0x001C		3
	0x0020	2	0
	0x0024		1
	0x0028		2
	0x002C		3
	0x0030	3	0
	0x0034		1
	0x0038		2
	0x003C		3

[0398] The following table shown details of the control register:

[0399]

Bit	31	30	29	28	27	26	25	24	23	22	21	20	19	18	17	16
Name	Spread Factor	Subchip Delay	Discard
R/W	RW	RW	RW
Reset	X	X	X	X	X	X	X	X	X	X	X	X	X	X	X	X
Bit	15	14	13	12	11	10	9	8	7	6	5	4	3	2	1	0
Name	Chip Advance	Constant Advance
R/W	RW	RW
Reset	X	X	X	X	X	X	X	X	X	X	X	X	X	X	X	X

[0400] The spread factor field determines how many chip samples are used to generate a data bit. In the illustrated embodiment, all fingers in a channel have the same spread factor setting, however, it can be appreciated by one skilled in the art that such constant factor setting can be variable in other embodiments. The spread factor is encoded into a 3-bit value as shown in the following table:

[0401]

	SF Factor	Spread Factor
	000	256
	001	128
	010	64
	011	32
	100	16
	101	8
	110	4
	111	RESERVED

[0402] The field specifies the sub-chip delay for the finger. It is used to select one of eight accumulation buffers prior to summing all Alpha values and passing them into the raised-cosine filter.

[0403] Discard determines how many MUD-processed soft decisions (y values) to discard at the start of processing. This is done so that the first y value from each finger corresponds to the same bit. After the first slot of data is processed, the Discard field should be set to zero.

[0404] The behavior of the discard field is different than that of other register fields. Once a non-zero discard setting is detected, any new discard settings from switching to a new table entry are ignored until the current discard count reaches zero. After the count reaches zero, a new discard setting may be loaded the next time a new table entry is accessed.

[0405] All fingers within a channel will arrive at the receiver with different delays. Chip Advance is used to recreate this signal skew during the Respread operation. Y and b buffers are arranged with older data occupying lower memory addresses. Therefore, the finger with the earliest arrival time has the highest value of chip advance. Chip Advanced need not be a multiple of Spread Factor.

[0406] Constant advance indicates on which chip this finger should switch to a new set of constants (e.g. a^) and a new control register setting. Note that the new values take effect on the chip after the value stored here. For example, a value of 0x0 would cause the new constants to take effect on chip 1. A value of 0xFF would cause the new constants to take effect on chip 0 of the next slot. The b lookup tables are arranged as shown in the following table. B values each occupy two bits of memory, although only the LSB is utilized by LCMUD hardware.

[0407]

	Offset	Buffer
	0x0000	U0 B0
	0x0020	U1 B0
	0x0040	U0 B1
	0x0060	U1 B1
	0x0080	U2 B0
	0x00A0	U3 B0
	0x00C0	U2 B1
	0x00E0	U3 B1
	0x0100	U4 B0
	0x0120	U5 B0
	0x0140	U4 B1
	0x0160	U5 B1
	0x0180	U6 B0
	0x01A0	U7 B0
	0x01C0	U6 B1
	0x01E0	U7 B1
	0x0200	U8 B0
	0x0220	U9 B0
	0x0240	U8 B1
	0x0260	U9 B1
	0x0280	U10 B0
	0x02A0	U11 B0
	0x02C0	U10 B1
	0x02E0	U11 B1
	0x0300	U12 B0
	0x0320	U13 B0
	0x0340	U12 B1
	0x0360	U13 B1
	0x0380	U14 B0
	0x03A0	U15 B0
	0x03C0	U14 B1
	0x03E0	U15 B1
	0x0400	U16 B0
	0x0420	U17 B0
	0x0440	U16 B1
	0x0460	U17 B1
	0x0480	U18 B0
	0x04A0	U19 B0
	0x04C0	U18 B1
	0x04E0	U19 B1
	0x0500	U20 B0
	0x0520	U21 B0
	0x0540	U20 B1
	0x0560	U21 B1
	0x0580	U22 B0
	0x05A0	U23 B0
	0x05C0	U22 B1
	0x05E0	U23 B1
	0x0600	U24 B0
	0x0620	U25 B0
	0x0640	U24 B1
	0x0660	U25 B1
	0x0680	U26 B0
	0x06A0	U27 B0
	0x06C0	U26 B1
	0x06E0	U27 B1
	0x0700	U28 B0
	0x0720	U29 B0
	0x0740	U28 B1
	0x0760	U29 B1
	0x0780	U30 B0
	0x07A0	U31 B0
	0x07C0	U30 B1
	0x07E0	U31 B1
	0x0800	U32 B0
	0x0820	U33 B0
	0x0840	U32 B1
	0x0860	U33 B1
	0x0880	U34 B0
	0x08A0	U35 B0
	0x08C0	U34 B1
	0x08E0	U35 B1
	0x0900	U36 B0
	0x0920	U37 B0
	0x0940	U36 B1
	0x0960	U37 B1
	0x0980	U38 B0
	0x09A0	U39 B0
	0x09C0	U38 B1
	0x09E0	U39 B1
	0x0A00	U40 B0
	0x0A20	U41 B0
	0x0A40	U40 B1
	0x0A60	U41 B1
	0x0A80	U42 B0
	0x0AA0	U43 B0
	0x0AC0	U42 B1
	0x0AE0	U43 B1
	0x0B00	U44 B0
	0x0B20	U45 B0
	0x0B40	U44 B1
	0x0B60	U45 B1
	0x0B80	U46 B0
	0x0BA0	U47 B0
	0x0BC0	U46 B1
	0x0BE0	U47 B1
	0x0C00	U48 B0
	0x0C20	U49 B0
	0x0C40	U48 B1
	0x0C60	U49 B1
	0x0C80	U50 B0
	0x0CA0	U51 B0
	0x0CC0	U50 B1
	0x0CE0	U51 B1
	0x0D00	U52 B0
	0x0D20	U53 B0
	0x0D40	U52 B1
	0x0D60	U53 B1
	0x0D80	U54 B0
	0x0DA0	U55 B0
	0x0DC0	U54 B1
	0x0DE0	U55 B1
	0x0E00	U56 B0
	0x0E20	U57 B0
	0x0E40	U56 B1
	0x0E60	U57 B1
	0x0E80	U58 B0
	0x0EA0	U59 B0
	0x0EC0	U58 B1
	0x0EE0	U59 B1
	0x0F00	U60 B0
	0x0F20	U61 B0
	0x0F40	U60 B1
	0x0F60	U61 B1
	0x0F80	U62 B0
	0x0FA0	U63 B0
	0x0FC0	U62 B1
	0x0FE0	U63 B1