Method and apparatus for efficient synchronization in spread spectrum communications

The present invention relates to telecommunications, specifically to the synchronization of transceivers in a direct spread spectrum radio communication system.

In modern communication systems such as cellular and satellite radio systems, different modes of operation (analog, digital, and hybrid) and frequency division multiple access (FDMA), time division multiple access (TDMA), and code division multiple access Access techniques such as (CDMA) and hybrids of these techniques are used.

Digital cellular communication systems have optimized system capacity and expanded functionality to support hierarchical cell structures such as macrocells, microcells, and picocells. The term "macrocell" generally refers to a cell having a size comparable to the cell size of a normal cellular telephone system (eg, a radius of at least about 1 km), and the terms "microcell" and "picocell" are generally smaller. Point to a cell. For example, a microcell can cover a public indoor or outdoor area, such as a conference center or downtown, and a picocell can cover an office corridor or the first floor of a high-rise building. From a wireless coverage perspective, macrocells, microcells, and picocells can be separate from each other or overlap each other to handle different traffic patterns or wireless environments.

A typical cellular mobile radiotelephone system includes one or more base stations (BS) and multiple mobile stations (MS). Base stations typically include control processing units connected to core network type nodes such as mobile switching centers (MSCs), and MSCs are connected to the public switched telephone network (PSTN). .. General aspects of such cellular radiotelephone systems are known in the art. The base station processes multiple voice or data channels through a traffic channel transceiver controlled by a control processing unit. Each base station also includes a control channel transceiver that may be capable of processing multiple control channels, also controlled by the control processing unit. The control channel transceiver broadcasts control information through the base station's control channel to a mobile that is tuned (or locked) to that control channel.

The mobile receives the information broadcast on the control channel on its voice and control channel transceivers. The mobile processing unit evaluates the received control channel information, including the characteristics of the cell that the mobile is a candidate for locking, and determines which cell the mobile must lock. Advantageously, the received control channel information includes not only absolute information about the cell associated with it, but also relative information about other cells adjacent to the cell associated with that control channel.

In North America, digital cellular wireless telephone systems that use TDMA are referred to as the digital advanced mobile phone service (D-AMPS), some of which have been published by the Telecommunications Industry Association and the Electronic Industries Alliance (TIA / EIA). The specifications are defined by the TIA / EIA / IS-136 standard. Another digital communication system that uses direct sequence spread CDMA (DS-CDMA) is specified by the TIA / EIA / IS-95 standard, and the frequency hopping CDMA communication system is the EIA SP 3389 standard (PCS). The specifications are defined in 1900). The PCS 1900 standard is an implementation of the GSM system, which is common outside of North America and has been introduced for personal communication services (PCS) systems.

Several proposals for next-generation digital cellular communication systems are currently being discussed by various standards-making organizations, including the International Telecommunication Union (ITU), the European Telecommunications Standards Institute (ETSI), and the Association of Radio Industries and Businesses (ARIB) in Japan. Has been done. The third example standard currently proposed by ETSI is the Universal Mobile Telecommunications System (UMTS) Terrestrial Radio Access (UTRA). In addition to transmitting voice information, next-generation systems carry packet data, usually in the Open Systems Interconnection (OSI) model or transmission control protocol / Internet. It is designed on industry-wide data standards such as the protocol (TCP / IP) stack and can be expected to interoperate with packet data networks based on it. These standards, whether formal or de facto, have been developed over the years and applications using these protocols are readily available.

In most of these digital communication systems, the communication channel is implemented by frequency-modulated radio carrier signals with frequencies near 800MHz, 900MHz, 1800MHz, and 1900MHz. To a different extent in TDMA and CDMA systems, each radio channel is divided into a series of time slots, each time slot containing a block of information from the user. Time slots are grouped into contiguous frames, each of which has a predetermined duration, and the contiguous frames can be grouped into a series of, usually referred to as superframes. The type of access technique used by the communication system (eg TDMA or CDMA) affects how user information is represented in slots and frames, but in all current access techniques, slots / frames. The structure is used.

Time slots assigned to the same mobile user may not be contiguous time slots on the radio carrier, but can be considered as logical channels assigned to that mobile user. During each time slot, a predetermined number of digital bits are transmitted according to the particular access technique used by the system (eg, CDMA). In addition to logical channels for voice or data traffic, cellular radio communication systems are provided by paging / access channels for call setup messages exchanged between base stations and mobile stations, and by mobile stations or other remote terminals. It also provides logical channels for control messages, such as the synchronization channel for broadcast messages used to synchronize those transceivers to the frame / slot / bit structure of the base station. In general, the transmit bit rates of these different channels do not have to match, and the slot lengths of the different channels do not have to be uniform. In addition, the 3rd generation cellular communication systems under consideration in Europe and Japan are asynchronous, which means that the structure of one base station is not temporally related to the structure of another base station and is mobile. Means that we do not know any of those structures in advance.

In such a digital communication system, the receiving terminal must find the timing reference of the transmitting terminal before transferring information. In communication systems using DS-CDMA, timing reference discovery corresponds to the discovery of downlink (eg BS to MS) chip, symbol, and frame boundaries. These may be referred to as downlink chip synchronization, downlink symbol synchronization, and downlink frame synchronization, respectively. In this regard, a frame is simply a block of data that can be independently detected and decoded. Frame tuning in current systems, typically in the range of 10 milliseconds (ms) to 20 ms. This BS timing search is sometimes referred to as a "cell search," which includes the identification of BS-specific downlink scrambling codes that are characteristic of current DS-CDMA communication systems.

The mobile or other remote terminal typically receives a signal that is a superposition (total) of attenuated, faded, and disturbed versions of the signal transmitted by the BS. The slot and frame boundaries of the received signal are initially unknown to the MS, as are the BS-specific scrambling codes. Therefore, the mobile must detect and identify one or more BSs in the noise-like (in the case of DS-CDMA) received signal to identify the scrambling code used. It doesn't become. To help remote terminals synchronize to BS and identify BS-specific scrambling codes, in some communication systems, each BS signal is sometimes referred to as a synchronization channel (SCH), which is locked by the MS. , Contains non-scrambled parts that can perform a "cell search".

Even after achieving downlink synchronization, synchronization must also be achieved for uplink communications (eg, from MS to BS). This is due to the rapidly changing radio interface between the base station and the mobile station as well as the "round trip" propagation delay between the base stations. When the mobile wants to transmit to the base station, it sends the first transmission over an uplink channel (eg, a random access channel (RACH)). Due to the already achieved downlink synchronization between the base station and the mobile station, the uplink transmissions are roughly or roughly synchronized, for example, usually within one time / access slot. For example, a base station may only allow uplink transmissions from mobiles in eight separate time / access slots. The mobile generally knows when these time slots begin when it synchronizes with the downlink signal broadcast by the base station. Therefore, it can be assumed that the mover is not out of sync beyond one such time / access slot. In a direct spread spectrum system, such time / access slots correspond to a given number of chips, eg 256 chips. In this example, it is assumed that the maximum round trip propagation delay, that is, the amount by which the mobile is out of sync with the base station, is 255 chips.

To achieve synchronization, the transmission of one station contains several known signals (ie, known to other stations). In the downlink direction, this known signal may be referred to as a synchronization sequence, synchronization code, main synchronization sequence, or main synchronization code. In the uplink direction, this known signal may be referred to as a preamble sequence. With random access, the mobile station sends an uplink random access burst. A random access burst consists of a preamble (or preamble sequence) part and a message part. The base station's RACH receiver correlates the received signal sample with a known preamble sequence. After the maximum preamble correlation is detected by the base station RACH receiver, the base station is in sync and is able to accurately decode the substantial message from the mobile contained in the message portion of the RACH burst. Only one random access sync code / preamble is required per base station, but different sync codes / preambles associated with the base station are used to minimize cross-correlation between uplink transmissions from different mobile stations. Can be.

In all cases, the synchronization code / preamble used for downlink cell search or uplink random access synchronization must have minimal out-of-phase aperiodic autocorrelation. Autocorrelation is a property that describes how well a code or sequence correlates with itself. The smallest out-of-phase aperiodic autocorrelation is that the autocorrelation value of the non-zero time shift (that is, the base station and the mobile station are out of sync by one chip or more) is the zero time shift autocorrelation value (base station). And mobile stations are chip-synchronized), which means less. The non-zero time-shift autocorrelation value is referred to as the autocorrelation sublobe. The 0 time-shift autocorrelation value is called the autocorrelation main lobe.

One possible source of synchronization code with a unit envelope is a binary or polyphasic Barker code. The barker cord's primary lobe to maximum sublobe ratio is equal to L, where L is the cord length. Unfortunately, binary barker codes exist only for lengths 2, 3, 4, 5, 7, 11, and 13, and polyphasic barker codes are now known for lengths up to 45. As a result, when longer preamble sync code is needed, suboptimal code must be used. For example, the random access burst signal preamble proposed for the Third Generation Mobile Communication Standard (UTRA) has a length of 4096 code chips.

<p> In addition to the minimum aperiodic autocorrelation and longer code length, it is also important to efficiently generate and correlate synchronous codes. There are several different sync preambles / codes that can be used randomly for correlation at the base station, so that the base station random access channel receiver receives all possible syncs / preambles of the composite signal. Efficiency is even more important when it must be correlated with the code. In this situation, the base station receiver uses a bank of random access preamble correlators, each performing a large amount of data processing operations, especially if the code length is long. Similar in terms of design and detection of downlink synchronization code transmitted by the base station to allow the mobile to identify base station timing and obtain frame synchronization, symbol synchronization, and chip synchronization (ie cell search). There is a problem.</p><p> To achieve efficiency, the proposed UTRA Random Access Burst Preamble is generated using a serial (or hierarchical) code concatenation procedure that has the advantage of reducing the number of correlation operations. The preamble is generated using a "signature" with 16 complex symbols. By multiplying each binary sequence by the constant complex number C = (1 + j) / 2, (where j = -1), it is obtained from the orthogonal set of binary orthogonal gold sequences of length 16. There are 16 different signatures. Each signature symbol 256 is selected to be orthogonal Gold sequences of chips long, they have are spread using the so-called preamble spreading code. Therefore, the resulting preamble sequence has a length of 4096 chips, i.e. 16 × 256 = 4096. The preamble spread code is cell-specific and is broadcast by the base station with information about the signatures allowed within that cell.</p><p> Unfortunately, the aperiodic autocorrelation characteristics of preambles based on series-connected orthogonal gold sequences are suboptimal, i.e., large autocorrelation sublobes are produced. A large autocorrelation sublobe means that the receiver incorrectly synchronizes with one of these sublobes, resulting in incorrect reception of the transmitted message.</p><p> Therefore, it is desirable to provide one or more synchronization sequences that provide the least aperiodic autocorrelation properties for longer lengths and can be efficiently generated and conducted. Such synchronization sequences can be advantageously used in many types of spread spectrum communication applications such as downlink cell retrieval and uplink random access.</p>

<p> To meet these and other objectives, the present invention provides correlators that can be included in the first transceiver used to correlate the received signal transmitted by the second transceiver. The correlator includes a matched filter that corresponds to the complementary pair of the sequence to correlate the received signal with one of the complementary pairs of the sequence. The detector detects the peak output from the matched filter and the timing circuit uses the detected peak output to generate a timing estimate for the synchronization of the transmission between the first and second transceivers. To do. Each of the complementary sequences has a very low aperiodic autocorrelation sublobe value for all nonzero delays of the complementary sequence and a maximum autocorrelation primary lobe value for the 0 delay of the complementary sequence.</p><p> In one example application, the first transceiver can be a base station and the second transceiver can be a mobile station. One sequence can be used as the preamble portion of a random access burst transmitted by a mobile station to a base station via a random access channel. Instead, the first transceiver can be the mobile station and the second transceiver can be the base station. One sequence can be used as a synchronization sequence transmitted by a base station over a synchronization channel or other broadcast type channel.</p><p> Multiple such matched filters can be used as a bank of correlators on the first transceiver side, and each matched filter corresponds to a complementary pair of sequences with minimal aperiodic autocorrelation sublobe characteristics. This is especially advantageous when multiple sequences from orthogonal pairs need to be used in the same cell, for example when multiple random access channels need to be used to increase capacity, for example. .. In a preferred example embodiment, the complementary pair of sequences is of length L = 2^NIs a complementary pair of binary sequences of, where N is a positive integer. Complementary pairs of binary sequences are usually referred to as Golay complementary pairs, and sequences that form such pairs are referred to as Golay complementary sequences. The Golay complementary pair of sequences preferably has a relatively long length, eg L = 4096 chips.</p><p> The present invention requires only N memory means, length L = 2^NAlso provided is a sequence generator that efficiently generates pairs of Goray complementary sequences. Modulo 2 with N memory means^NThe counter is 0 to 2^N-1Count cyclically up to. A permuter that takes N parallel outputs from a counter and replaces them according to a permutation with an integer in the range 1 through N. The first set of N logical AND arithmetic units produces N parallel outputs from adjacent pairs of replaced counter outputs. These outputs are summed in modulo 2 in the first summer. The second set of N logical AND operators acts on each of the replaced counter outputs and one of the set of N weighting coefficients to produce N parallel outputs. The second summer sums the outputs produced by the second set of N logical AND operators, modulo 2. The third summer takes the sum modulo 2 of the outputs of the first and second summarizers to create the first binary sequence of complementary pairs of binary sequences. The 4th summer takes the sum of the output of the 3rd summer and the top-level output from the permuter, modulo 2, to create a second binary sequence of complementary pairs of binary sequences.</p><p> In addition to an efficient synchronous sequence generator, the present invention presents a received spread spectrum signal with a length of L = 2.^NAlso provided is an efficient sequence correlator that efficiently correlates with a pair of binary (Gorley) complementary sequences or polymorphic complementary sequences. Such a correlator is sometimes referred to as an efficient Goray correlator (EGC). An efficient sequence correlator contains N serially linked processing stages, each stage having a first and second parallel processing branch. Each stage of the first processing branch contains a delay line coupled to the corresponding adder. Each stage of the second processing branch contains a multiplier coupled to the subtractor. The input signal supplied to the first processing branch at a specific processing stage is stored in multiple memory means of the corresponding delay line, and the content of the last memory means of the same delay line is an adder (in the first branch). ) And the subtractor (in the second branch) of the same stage. The input signals fed to the second processing branch in the same stage are multiplied by the corresponding weighting factors within the multiplier. The output of the multiplier is fed to the negative input of the subtractor (in the second branch) and the adder (in the first branch). The output of the adder is input to the delay line of the next consecutive stage. The output of the subtractor is input to the multiplier for the next consecutive stage. The input signals of the first processing branch and the second processing branch of the first processing stage correspond to the received spread spectrum signal.</p><p> The output of the first processing branch of the Nth processing stage is a cross-correlation between the received spread spectrum signal and the first sequence of the complementary pair of sequences. The output of the second processing branch of the Nth processing stage is a cross-correlation between the received spread spectrum signal and the second sequence of the complementary pair of sequences. In a preferred embodiment, the complementary sequence is a binary complementary sequence or a Goray complementary sequence.</p><p> In the present invention, L = 2^NAlso provided is a memory efficient Goray correlator with substantially reduced memory for correlation of received signals using one of the sequences from a pair of complementary sequences of. One sequence from a complementary pair is represented as a concatenation of two shorter component complementary sequences of length X. Each component sequence is repeated L / X times and modulated by +1 or -1 according to a signature sequence of length Y = L / X. The first correlator of length X receives the spread spectrum signal and produces an intermediate pair of correlation values corresponding to the component complementary sequence. The first selector is an intermediate pair of correlation values between each of the successive time windows, based on the current value of the interleaving sequence of length Y = L / X whose elements belong to the set {0,1}. Supply one alternately. The order of concatenation of component sequences is determined by the interleaving sequence. The multiplier multiplies the selected intermediate correlation value by the corresponding bit of the signature sequence to produce a multiplied correlation output. The multiplied correlation output is summed with the feedback output produced by the delay line with X memory means, and the sum of the results itself is fed back to the input of the delay line. The final correlation value corresponds to the sum of the results after Y consecutive time windows have occurred. In a preferred embodiment embodiment, N = 12, L = 4096, X = 256, and Y = 16, and the final correlator is an efficient Goray correlator, such as that described above.</p><p> In another embodiment, the memory efficient correlator correlates the received spread spectrum signal with a plurality of orthogonal sequences generated using the plurality of signatures. Each of the multipliers multiplies the selected intermediate correlation values over elements of different signature sequences to produce the corresponding multiplied correlation output. A plurality of summers are provided, each of which corresponds to one of the multipliers and sums the multiplied correlation output with the corresponding delay line feedback output. After processing all the elements in the signature sequence, a final correlation value is generated for each of the orthogonal sequences. One example embodiment is disclosed in which 16 signatures are used to generate 16 orthogonal goray sequences. In another example embodiment, 32 signatures are used to generate 32 orthogonal goray sequences.</p><p> As a result of the present invention, a single synchronous sequence or an orthogonal set of synchronous sequences is provided that has excellent aperiodic autocorrelation properties for relatively long sequence lengths. Equally importantly, the present invention provides efficient generation and correlation of one synchronization sequence or an orthogonal set of such synchronization sequences. These synchronization sequences can advantageously be used for uplink synchronization over a random access channel and downlink synchronization over a broadcast synchronization channel in one example application.</p><p> The aforementioned and other objects, features, and advantages of the present invention are apparent from the following description of preferred embodiments and are also shown in the accompanying drawings, in which the reference numerals refer to the same parts throughout. Although the individual functional blocks and components are shown in many of the figures, those skilled in the art can perform these functions in application-specific integrated circuits by means of individual hardware circuits and by appropriately programmed digital microprocessors. You will understand that it can be done by (ASIC), by one or more digital signal processors (DSPs), or by a combination of these.</p>

<figref num="1">It is a functional block diagram of an example mobile communication system in which the present invention can be used advantageously.</figref><figref num="2">It is a functional block diagram of an example radio station transceiver in which the present invention can be used advantageously.</figref><figref num="3">FIG. 2 is a functional block diagram showing additional details of a baseband processing block in the receiver chain of the radio station transceiver of FIG.</figref><figref num="4">It is a figure of a recursive Goray sequence generator.</figref><figref num="5">It is a figure of a direct Goray sequence generator.</figref><figref num="6">It is a figure of a general type correlator.</figref><figref num="7">It is a figure of an efficient Goray correlator.</figref><figref num="8A">It is a figure which shows the signaling format of a random access burst through a random access channel.</figref><figref num="8B">It is a figure which shows the signaling format of a random access burst through a random access channel.</figref><figref num="9">It is a flow chart which shows the procedure of the random access routine executed by a mobile station.</figref><figref num="10">It is a flow chart which shows the random access routine executed by a base station.</figref><figref num="11">FIG. 5 is a diagram of a particular random access channel preamble correlator based on a concatenated sequence.</figref><figref num="12">It is a figure which shows the random access preamble correlator which also based on the concatenated sequence which incorporated the embodiment of the example of this invention.</figref><figref num="13">It is a figure which shows the bank of the random access preamble correlator using the embodiment of the example of this invention.</figref><figref num="14">FIG. 6 is a block diagram of another embodiment of the present invention that implements a factorized and efficient Goray correlator.</figref><figref num="15">It is a graph which shows the autocorrelation value with respect to the delay of a random access preamble correlator.</figref><figref num="16">It is a graph which shows the autocorrelation value with respect to the delay of the random access preamble correlator which carries out the embodiment of the example of this invention.</figref>

In the following description, for illustration purposes rather than limitations, specific details such as specific embodiments, procedures, techniques, etc. are provided to provide a complete understanding of the present invention. However, it will be apparent to those skilled in the art that the present invention can be practiced in other embodiments that deviate from these particular details. For example, the present invention will sometimes describe mobile radio stations that use uplink spread codes, but the invention is equally applicable to other radio stations, such as radio base stations, and in fact all. It is equally applicable to the spread spectrum communication system of. In other cases, detailed descriptions of well-known methods, interfaces, devices, and signaling techniques have been omitted so as not to obscure the description of the invention with unnecessary details.

The present invention is described in Universal Mobile Telecommunications as shown in FIG. Described in the context of a non-restrictive example of System (UMTS) 10. A typical connection-oriented external core network, designated as cloud 12, can be, for example, a public switched telephone network (PSTN) and / or integrated services digital network (ISDN). A typical connectionless oriented external core network, shown as cloud 14, could be, for example, the Internet. Both core networks are joined to the corresponding service node 16. The PSTN / ISDN connection-oriented network 12 is connected to a connection-oriented service node, which is designated as a mobile switching center (MSC) node 18 that provides circuit switching services. In the existing GSM model, MSC18 is connected to Base Station Subsystem (BSS) 22 via Interface A and BSS22 is connected to Radio Base Station 23 via Interface A'. The Internet connectionless oriented network 14 is a General Packet Radio tuned to provide packet-switched services. Connected to Service (GPRS) node 20. Each of the core network service nodes 18 and 20 is connected to the UMTS Radio Access Network (URAN) 24 via a radio access network (RAN) interface. URAN24 includes one or more wireless network controllers 26. Each RNC26 is connected to a plurality of base stations (BS) 28 and other RNCs within the URAN24.

In a preferred embodiment, radio access is based on wideband code division multiple access (WCDMA) and individual radio channels are allocated using CDMA spread codes. WCDMA offers wide bandwidth for multimedia services and other high-speed demands, as well as robust features such as diversity handoff and RAKE receivers to ensure high quality. Each mobile station 24 is from a base station assigned to the mobile station by the base station 20 to identify transmissions from that particular mobile station, as well as from other transmissions and noise in which the mobile station is located in the same area. It is assigned its own scrambling code to identify the transmission. Downlink (BS to MS) broadcast channels and uplink (MS to BS) random access channels are illustrated.

A CDMA radio station transceiver 30 capable of using the present invention is shown in FIG. 2 in functional block diagram format. Those skilled in the art will appreciate that other radio transceiver features used in CDMA transceivers that are not relevant to the present invention are not shown. In the transmit branch, the transmitted information bits are received by the spreader 32, which spreads these information bits on the available frequency spectrum according to the spread code generated by the spread code generator 40. (For broadband CDMA, this frequency band is, for example, 5MHz, 10MHz, 15MHz, or higher). The controller 44 determines which of the spread codes supplied by the code generator 40 is supplied to the spreader 32. The spread code supplied by the code generator 40 corresponds to the radio channel of the CMDA communication system. Since each information bit can be encoded using a large number of code symbols (sometimes referred to as "chips") (current data in variable data rate systems such as WCDMA systems). The rate-dependent), spreading operation significantly increases the data rate, which increases the signal bandwidth. The spread signal is supplied to the modulator 34, which modulates the RF carrier with the spread signal. Oscillator 42 produces a suitable radio frequency carrier at the frequency selected by controller 44. The modulated RF signal is filtered and amplified within the RF processing block 36 before being transmitted by the antenna 38 over the radio interface.

A similar but reverse operation is performed on the receive branch of transceiver 30. The RF signal is received by antenna 38 and filtered by RF processing block 150. The processed signal is RF demodulated in the RF demodulator 48 using the appropriate RF carrier signal supplied by the oscillator 44 to extract the complex baseband signal from the RF carrier. Orthogonal downconverters are typically used in RF demodulators to decompose the received signal into real (I) quadrature and imaginary (Q) quadrature components. In this way, the phase shift of the incoming signal due to channel fading or phase asynchronization between the transmitter and receiver oscillators can be detected and compensated for. The RF demodulated complex baseband signal is correlated with the preamble sequence for synchronization and then despread within the baseband receiver 46 according to the despread code.

With reference to FIG. 3, the baseband receiver 46 is shown in detail. A synchronous preamble is a binary sequence in which the preamble matched filter / correlator 51 contains two identical binary preamble correlators, one of which (52) correlates the I branch of the received baseband signal. , The other (53) correlates the Q branch of the same signal. The preamble sequence is incorporated into the preamble matched filter 51, and the despread code is generated by the code generator 40.

The received complex baseband preamble signal is used in the baseband (RAKE) demodulator 57 to achieve accurate synchronization with the incoming signal and to obtain an initial value of the fading channel coefficient that will be tracked later. Is correlated within the corresponding synchronous preamble correlator 51. Timing information is obtained within the peak detector 54 by comparing the absolute correlation values from the real and imaginary correlators 53 with the thresholds. The peak detector 54 provides delays (relative to receiver timing) for the various multipath components of the received signal. The timing unit 56 uses this information to compensate for the combination of multipath components and the mutual delay of the multipath components prior to demodulation in the baseband (RAKE) demodulator. The complex correlation value corresponding to the detected correlation peak is stored in the initial channel estimator 55 and used in the baseband demodulator 57 as the initial fading channel coefficient to be canceled out.

In the present invention, it is used as one or more synchronization patterns from complementary pairs of sequences. The basic characteristic of complementary pairs in a sequence is that the sum of their aperiodic autocorrelation functions is zero for all non-zero time shifts. In a preferred embodiment, the synchronization sequence is based on a binary complementary sequence or Goray complementary sequence. Advantageously, the Goray complementary sequence is all length L = 2^NIt can be configured for (N is any positive integer), it can be configured for lengths 10 and 26, and it can be configured for any combination of these lengths. In addition to having the potential for long sequence lengths, many Goray complementary sequences have a low aperiodic autocorrelation sublobe. Although the text below focuses on Gorey complementary sequences for illustration purposes only, many aspects of the invention include all sequences that belong to any pair of complementary sequences.

Sequence length is L = 2^NThere is a general way to construct a polymorphic complementary pair of a sequence, where the Goray complementary pair of a sequence is a special binary case, i.e. two-phase. Its general configuration is defined by the following recursive relationship:

a₀(k) = δ (k) b b₀(k) = δ (k) a_n(k) = a_n-1(k) + W_n B_n-1(kD_n) b b_n(k) = a_n-1(k) -W_n B_n-1(kD_n) (1) here, k = 0,1,2, ..., 2^N-1 n = 1,2, ..., N D_n=2^PnAnd a_n(k) and b_n(k) is length 2^NTwo complementary sequences of δ (k) is the Kronecker delta function k is an integer that represents the time scale n is the number of iterations D_nIs a delay P_n, N = 1,2, ..., N is any permutation of the number {0,1,2, ..., N-1}, W_nIs any complex number of unit size.

W_nA binary (goray) complementary sequence is obtained if has a value of +1 or -1. All possible replacements P_nAnd all 2^NDifferent vectors W_n, (N = 1,2, ..., N), N! 2^NIt is possible to construct different complementary pairs. But length 2^NThe number of different Goray sequences is N! 2^N-1Is.

If the delay is not a power of 2 as defined in Eq. (1), or all weighting factors W_nIf they do not have the same size, the configuration of equation (1) creates a multi-level complementary pair. However, many aspects of the invention also apply to multi-level complementary pairs.

Both sequences from complementary pairs a_n(k) and b_nFigure 4 shows a general recursive method for simultaneous generation of (k). The recursive goray sequence generator 60 shown in FIG. 4 has the complementary goray sequence a defined by Eq. (1)._n(k) and b_nMake a pair of (k), but require a lot of memory means, especially for long code. For example, for a sequence of length L = 4096 and N = 12, 12 delay lines (D)₁Or D₁₂) Is required and the first delay line is D₁It has two memory means, and the second delay line is D₂It has a number of memory means, and so on. Therefore, the total number of memory means is L-1 = 2^NBecome -1. Because, according to equation (1) D₁+ D₂+ ... + D_n=1+2+4+...+2^N-1=2^N-1 Because it becomes. More efficient (and therefore preferred but not necessary) means for generating Goray complementary sequences will be described below.

The direct Golay complementary sequence generator shown in FIG. 5 makes exactly the same Goray complementary sequence pair as the recursive Goray sequence generator 60 shown in FIG. Direct Goray Sequence Generator 70 from 0 to 2^NModulo 2 containing only N memory means that allows circular counting up to -1^NIncludes counter 72. The counter 72 parallel output corresponds to the binary representation of the positive integer variable k, where,

<maths num="1"><img file="JP5114585B2_D0001.tif" /></maths>

Is. Substitute 74 has N parallel outputs B₁(k) or B_nCombined to receive (k), these N parallel outputs are replaced according to some permutation of integers in the range 1-N. The substitution vector used in the substitution device 74 is obtained by adding 1 to all the numbers of substitutions used in equation (1). The first set 76 of N-1 AND gates produces N-1 parallel outputs from adjacent pairs of outputs of the substituent 74. The first summarizer 80 takes a sum modulo 2 of the output produced by the first set 76 of the AND gate. The second set 78 of the AND gate is each of the outputs of the substitute 74 and the binary vector W used in equation (1)._nN weighting coefficients W obtained by mapping 1 to 0 and -1 to 1 using₁^’Or W_n^’It takes a logical product with one of the pairs of. The second summer 82 takes a sum modulo 2 of the output produced by the second set 78 of the AND gate. The third adder 84 takes the sum of the outputs of the first adder and the second adder, modulo 2, to create the first binary sequence of the complementary pair of binary sequences. The fourth adder 86 is the top output of the third adder 84 and the substitution device 74, that is, B._{P (N)}Take the sum modulo 2 in (k) to create a second binary sequence of complementary pairs of sequences. The projector 88 transforms the first and second binary sequences, which have elements from the alphabet {0,1}, into the corresponding elements from the alphabet {-1,1}.

The direct Golay complementary sequence generator 70 is memory efficient and has a fairly low complexity, i.e., a complexity similar to that of a conventional linear feedback shift register sequence (m sequence) generator. These features make the generator 70 particularly attractive as a sequence generator in random access burst transmitters and base station transmitters in mobile terminals.

On the receiver side, the received spread spectrum signal must be correlated with the transmitted Goray complementary sequence in order to accurately detect when the complete sequence is received. Since the transmitted Goray complementary sequence is selected to have the least aperiodic autocorrelation, the probability that the maximum detected correlation value corresponds to the autocorrelation main lobe is very high. A general simple embodiment of the correlator 90 matched to any synchronization sequence is shown in FIG.

The received signal r (k) is supplied to a delay line having L-1 memory means. Because each input signal and each memory means stage correlates with the sequence represented by a (L-1), a (L-2), a (L-3), ..., a (0) , Provides inputs to L multipliers. The outputs of the multipliers are summed to supply the correlation output signal R (τ). The Goray Correlator 90 is satisfactory for performing correlations, but it is very costly in terms of memory and data processing. For example, for L = 4096, we need 4095 memory means, 4096 multipliers, and 4095 summers.

Therefore, in a preferred embodiment of the invention, the efficient Goray Correlator (EGC) 100 shown in FIG. 7 is used. Functionally, the efficient Goray correlator 100 is a complementary sequence a defined by Eq. (1)._N(k) and b_NA matched filter that directly corresponds to (k). What makes this correlator 100 particularly attractive is that it uses significantly less memory and data processing operations than is required for the general correlator 90 shown in FIG.

The efficient Goray correlator 100 has two complementary sequences a of the input signal r (k)._N(k) and b_NPerform correlation with (k) at the same time. Two matched filter correlator outputs R_ra(τ) and R_rb(τ) is the corresponding aperiodic cross-correlation function, that is, the received signal r (k) is two sequences a_N(k) and b_NIt is a value indicating the degree of agreement with (k). The matched filter / correlator 100 has a weighting coefficient W defined in Eq. (1)._nComplex conjugate of W_n^*To use.

Therefore, the efficient Goray correlator 100 uses N series-connected processing stages, each stage having a first and second parallel processing branch, to capture the received spread spectrum signal r (k). Length L = 2^NCorrelate with a pair of Goray complementary sequences. Input signal R supplied to the first processing branch of each processing stage_a^(n-1)(k) is the corresponding delay line D_nStored in the first memory means of (n = 1, ..., N) and the same delay line D_nThe contents of the last memory means of are input to the adder (in the first branch) and subtractor (in the second branch) of the same processing stage. Input signal R supplied to the second processing branch of the same stage_{b b}^(n-1)(k) is the corresponding weighting factor W in the multiplier_n^*Can be multiplied by, but this weighting factor W_n^*Is the weighting coefficient W defined in Eq. (1)_nIs the complex conjugate of. The output of the multiplier is input to the negative input of the subtractor and the adder of the first branch. Adder output R_a⁽ⁿ⁾(k) is input to the delay line of the next consecutive stage. Subtractor output R_{b b}⁽ⁿ⁾(k) is input to the multiplier for the next consecutive stage. Input signal R to the first processing branch and the second processing branch of the first processing stage_a⁽⁰⁾(k) and R_{b b}⁽⁰⁾(k) corresponds to the received spread spectrum signal r (k).

First sequence a of the Goray complementary pair of received spread spectrum signal and sequence by the output of the first processing branch of the Nth processing stage._nCross-correlation with (k) R_ra(k) is created. The second sequence b of the Goray complementary pair of the received spread spectrum signal and sequence by the output of the second processing branch of the Nth processing stage._nCross-correlation with (k) R_rb(k) is created.

The number of multiplications in EGC is log₂Equal to (L). In contrast, the simple matched filter embodiment 90 of the Goray sequence correlator shown in FIG. 6 requires a much larger number of multiplications corresponding to 2 · L. Note that the simple embodiment 90 requires two correlators to correlate complementary pairs, but the efficient Goray correlator 100 correlates complementary pairs simultaneously. The number of additions with the efficient Goray correlator 100 is 2. log₂It is (L), which is less than that in the case of the simple matched filter embodiment 90 (2. (L-1)). The number of memory means required for an efficient Goray correlator 100 is L-1, while the general correlator 90 shown in Figure 6 is for sequence pair correlation (2 (L-). 1)) Two sets of memory means are required. Therefore, in the efficient Goray Correlator 100, IC space is saved, processing operations are reduced, power is saved, and cost is reduced.

The present invention has a particularly advantageous non-restrictive application of providing synchronization between a mobile station and a base station when the mobile station transmits a message over a random access channel corresponding to the base station. The format of one example of such a random access channel is described with respect to FIGS. 8A and 8B. The random access channel format allows mobile stations to transmit on random access channels with multiple well-defined time offsets to a particular frame boundary, slotted. Based on the ALOHA) method. Different time offsets are illustrated as access slots, separated by 1.25 ms. Information about which access slots are available in the current cell is broadcast by the base station on the downlink broadcast channel. Frame boundaries are also defined by the broadcast channel of the current cell. The random access burst contains two parts, a preamble part with a length of 1 ms and a message part with a length of 10 ms. There can be an idle time period of, for example, 0.25 ms between the preamble and the message, which allows preamble detection (correlation) and subsequent online processing of the message.

The random access procedure performed by the mobile station is described for the random access (MS) routine (block 200) shown in FIG. Initially, the mobile station must acquire synchronization for a particular base station call (block 210). As explained in the background, the mobile station performs this initial synchronization during cell retrieval of the base station with the lowest path loss. The mobile station tunes to the base station broadcast channel, processes the broadcast signal, and detects the synchronization sequence. In one example embodiment, synchronization is broken down into two steps. In the first step, the mobile discovers a main synchronization sequence that is common to all base stations. After detecting the strongest or largest correlation, the mobile station performs a second step, in which the mobile station correlates a second synchronization sequence specific to this base station.

After gaining synchronization to a particular cell, the mobile station uses information about the random access preamble spread code and message scrambling code used in this particular cell from the downlink broadcast channel. Acquired with information about possible preamble signatures, available random access channel access slots, and other information (block 220). The mobile station then selects an access time slot and signature from the available ones (block 230). The mobile station then uses the signature and preamble spread code to generate a random access burst during the selected access time slot (block 240).

Random access bursts transmitted by the mobile station must be received at the base station and correlated correctly, as described with the Random Access (BS) routine (block 300) shown in flow diagram format in Figure 10. It doesn't become. The base station receives the composite RF signal, converts it to baseband, and correlates the baseband signal with one or more preamble sequences (block 310). Specifically, the base station uses a matched filter type correlator to correlate the baseband composite signal with the preamble sequence (block 320). The maximum correlation peak is then detected and used to estimate frame, slot, and chip synchronization timing information. A peak detector (eg 54) provides a relative (relative to receiver timing) delay for the various multipath components of the received signal (block 330). The estimated timing information is supplied to the RAKE combiner (eg 57) for demodulation of the message portion of the random access channel burst (block 340). A timing unit (eg 56) compensates for the mutual delay of the multipath components prior to combination and demodulation with a RAKE demodulator (eg 57). The complex correlation value corresponding to the detected correlation peak is used as the initial fading channel coefficient canceled by the RAKE demodulator.

The Random Access Channel (RACH) Preamble Correlator 400 shown in Figure 11 is particularly efficient with respect to the amount of memory used. Efficiency is achieved by concatenating the signature binary sequence and the preamble spread code in series (hierarchically). That is, each binary bit in the signature sequence is spread by the same preamble spread code. The received signal is in the matched filter 410, for example T_maxCorrelated with a preamble spread code with a length of = 256 chips. The intermediate correlation value created by the matched filter 410 is multiplied by the multiplier 420, for example, an element of a signature sequence having a length of 16 (supplied by the base station via a broadcast channel). The summarizer 430 sums the output of the multiplier 420 with the length of the matched filter, eg, the output of the delay line 420 having the same number of elements as 256. The output of the totalizer 430 is input to the delay line 440 and supplied to the peak detector 450. In the preamble correlator 400, the expected delay τ of the received signal r (k) is | τ | &lt;T._maxLimited to T_maxHowever, it works as desired, provided that it is the length of the preamble spread code.

Correlation operations are synchronized with the time window in which random access bursts are expected to be received, such as 256 chips. The length of this time window assumes that the mobile station has already achieved downlink synchronization or main synchronization with the base station. For each of the 256 chip windows in a row, multiply the 256 correlation values generated by the matched filter 410 for that window by one symbol of a 16-symbol length signature sequence. The next symbol in the signature sequence is then selected at the start of the next 256 chip time window. Sum the multiplied correlation value with the result of the previous sum performed at the same relative time position in the previous time window. The result of the previous total is obtained from the output of delay line 440, after which the result of the current total is stored in delay line 440. The final correlation value output to the peak detector 450 is supplied after a total of 16 iterations at each time position within the 16 time windows, ie the 256 chip time windows. Therefore, at each iteration, an intermediate correlation peak with a value of 256 is integrated so that the perfect correlation peak is equal to 4096. The peak detector 450 receives the correlation value from both the I receiver branch and the Q receiver branch and calculates the absolute correlation value or the square absolute correlation value. The peak detector 450 is connected to, for example, the rest of the RACH receiver shown in FIG.

The RACH preamble correlator 400 is particularly efficient as it requires significantly less memory than traditional correlators. For example, for L = 4096, the RACH preamble correlator 400 requires only 511 memory means, while the general correlator 90 shown in FIG. 6 requires 4095 memory means. ..

The memory reduction benefit of the structure of the preamble correlator 400 is used in favor of implementing the memory efficient Goray sequence correlator 500, which has a structure similar to that shown in FIG. 11, as shown in FIG. To. Correlator 500 reduces the number of additions and multiplications required. The efficient Goray correlator 500 shown in Figure 12 has a length L = 2^N= J T_maxTwo shorter lengths of the Goray sequence of T_maxBased on the functional representation of the component complementary sequences A (k) and B (k) of. This function is the result of a general recursive configuration in equation (1) for a complementary pair of sequences. That is, if a general recursive configuration starts with any pair of complementary sequences, i.e. the initial vector a₀(k) and b₀(k) is a₀(k) = A (k) b b₀(k) = B (k), k = 0,1,2, ..., T_max-1 Selected to be A (k) and B (k) of length T_maxResult length L = 2 if there are two complementary sequences of^N= J T_maxA pair of complementary sequences of is generated after J iterations. All delays in Eq. (1) D_nIs the length of the component sequence (T)_max) Can be applied.

The received signal r (k) is preferably received by the efficient Goray correlator 510 shown in FIG. 7, for example having a chip L = 256 in length. The efficient Goray correlator 510 has two cross-correlation values R corresponding to Goray complementary pairs in the sequence._rA(τ) and R_rBGenerate (τ). The switch or selector 520 receives the two correlation values. A control signal called an "interleaving signal" controls the selector 520, and when "0" is supplied, R_rA(τ) Correlation value, R if "1" is supplied_rB(τ) Select the correlation. This causes the selector 520 to alternately supply one of the intermediate pairs of correlation values between each of the successive time windows, based on the current value of the interleaving sequence. The order of concatenation of shorter component sequences is determined by the interleaving sequence. The interleaving sequence in this example, whose signature has a length of 16, also has a length equal to 16. The output of selector 520 is the multiplier 420, which is multiplied by one of the signature symbols corresponding to the current 256 chip timing window in the multiplier 420. The operations performed by the multiplier 420, the summer 430, the delay line 440, and the peak detector 450 are similar to those described with respect to FIG. As in the case of the method shown in FIG. 11, in the memory-efficient Goray correlator 400, the expected delay τ of the received signal r (k) is | τ | &lt;T._maxLimited to T_maxWorks as desired, provided that it is the length of the component complementary sequence.

The correlator 500 has the same number of memory means as the correlator 400 of FIG. 11, but the number of multipliers and adders is considerably smaller. The overall efficiency is improved due to the higher efficiency of the EGC510 used in place of the matched filter preamble spread code correlator 410 in Figure 11.

For cells where higher capacity is desired, it is useful to construct multiple sets of synchronization sequences. More synchronization sequences offer more capacity potential. Such sets of sequences are preferably orthogonal to minimize cross-correlation. The present invention provides efficient generation of orthogonal pairs of Golay sequences from the recursive configuration of Eq. (1).

A set of orthogonal goray sequences is a permutation P_nFor each of the, i.e. delay D_nL / 2 = 2 of length N for each of the pairs^N-1An appropriate set of vectors W (v, n), ie v = 0,1, ..., 2^N-1It can be generated from Eq. (1) by selecting -1 and n = 1,2,3, ..., N. Each vector W (v, n) creates a pair of complementary goray sequences. As a result, a total of 2^NThe sequence is 2 in length^NProvided as an orthogonal set of Goray sequences.

Make an orthogonal pair of Golay tuples from equation (1) 2 of length N^N-1A pair of vectors W (v, n) can be generated, for example, in two different forms. The first algorithm is

<maths num="2"><img file="JP5114585B2_D0002.tif" /></maths>

And here, B_n(x) is the nth bit of the N-bit length binary representation of a positive integer x, that is,

<maths num="3"><img file="JP5114585B2_D0003.tif" /></maths>

Is. The second algorithm is given by the following equation.

<maths num="4"><img file="JP5114585B2_D0004.tif" /></maths>

Consider the following exemplary example. Length L = 8 = 2³Suppose that an orthogonal set of Goray sequences with N = 3 is obtained using Eq. (1). Arbitrary permutation of the number {0,1,2} P = {P₀, P₁, P₂} And assume that P = {0,2,1}. The required weighting vector W (v, n) of length 3 is obtained from Eq. (2a), which is shown in Table 1 below.

<tables num="1"><img file="JP5114585B2_D0005.tif" /></tables>

The resulting set S (u, k) of orthogonal length 8 Goray sequences is shown in Table 2.

<tables num="2"><img file="JP5114585B2_D0006.tif" /></tables>

Each Golay sequence can be multiplied by a constant complex number (1 + j) / 2, (where j = -1) to obtain the corresponding 4-phase code.

A particular advantageous application of the orthogonal goray sequence to the RACH preamble will be described for the memory efficient goray correlator shown in FIG. FIG. 13 shows a preferred embodiment of the invention that implements the RACH preamble correlator 600, which can use multiple preamble sequences. Each of the 32 correlators shown in the correlator bank of FIG. 13 operates in a manner similar to the correlator 500 shown in FIG. The component sequence is T_max= 256 length and substitution vector P_n, And the weighting vector W_nHowever, when the length is 16, the total length of the result of each sequence of the complementary pair is 4096. The resulting goray sequence consisting of sequences A (k) and B (k) is repeated eight times, which is the permutation vector P._nMultiplexed by selector 520 using an "interleaving" function that depends on. Interleaving function I₀(k) is common to the first 16 orthogonal preambles and the interleaving function I₁(k) is common to the remaining 16 orthogonal preambles. Each preamble has its own "signature" sequence, which is the weighting function W._nAnd substitution vector P_nDepends on. The interleaving function selects one or the other output of the EGC according to the structure of the transmitted preamble.

The first orthogonal pair of 16 goray sequences of length 4096 with common component sequences A (k) and B (k) (and common interleaving functions) of length 256 is of length. It is obtained by selecting 16 single substitution vectors with 8 weighted vectors according to Eq. (2). All delays in Eq. (1) D_nIn addition, the length of the component sequence (T_max= 256) is multiplied.

It has the same component sequences A (k) and B (k), but another interleaving function I₁An additional 16 orthogonal goray sequences of length 4096, interleaved by another selector 610 according to (k), are obtained by:

a₀(k) = B (k) b b₀(k) = A (k), k = 0,1,2, ..., T_max-1 The substitution and weighting vectors used in Eq. (1) to obtain an additional set of orthogonal goray sequences are the same as the first set of orthogonal goray sequences. In total, there are 32 orthogonal goray sequences of length 4096 with a common component sequence of length 256. Generally, J = L / T_maxAs such, it is possible to generate 2J such orthogonal goray sequences.

These interleaving and signature functions are shown by an orthogonal set of 8 length Goray sequences using the same examples given in Tables 1 and 2 above. T_maxTable 3 shows the set of sequences given in Table 2 when = 2 and the component sequences are A (k) = {1,1} and B (k) = {1, -1}. Can be represented as shown.

<tables num="3"><img file="JP5114585B2_D0007.tif" /></tables>

Interleaving function I₀(k) and I₁(k) is I₀(k) = {0,0,1,1} and I₁(k) = {1,1,0,0} Here, the value of "0" selects the cross-correlation with sequence A (k), and the value of "1" selects the cross-correlation with sequence B (k). Therefore, the interleaving function I₁(k) is I₀This is the inverted version of (k). The first four "signature" functions are shown below.

Signature 0 = {1,1,1, -1}, Signature 1 = {1, -1,1,1}, Signature 2 = {1,1, -1,1}, Signature 3 = {1, -1, -1, -1} The values of the other four signature functions are the same: signature 4 = signature 0, signature 5 = signature 1, signature 6 = signature 2, and signature 7 = signature 3.

An application of the previous example of the present invention is for one or more correlators used by the base station to receive and synchronize random access bursts transmitted by the mobile station. An advantageous application of another example of the invention previously mentioned is for a cell search correlator used within a mobile station. During the initial cell search, the mobile station searches for the base station with the lowest path loss. The mobile station then determines the base station's time slot and frame synchronization and the downlink scrambling code associated with the base station. The initial cell search is performed in three steps: (1) slot synchronization, (2) frame synchronization and code group identification, and (3) scrambling code identification. Applications of this other non-limiting example of the present invention relate to first and second steps (1) and (2).

The slot synchronization procedure at a mobile station uses a primary synchronization code that is broadcast by all base stations at the beginning of each time slot and is common to all base stations. The synchronization procedure consists of correlating the incoming signal with the main synchronization code. The output of the correlator produces a peak for each radiation from each base station within the range of the mobile station. By detecting the position of the strongest peak, the timing of making the time slot length of the strongest base station "law" is given.

Slot synchronization is a critical step from a mobile station perspective. This is because this operation is always performed, even if the mobile station already has a link to another base station. Therefore, the complexity of implementing a mobile station correlator with respect to the main synchronization code should be minimized if possible. Such minimization can be achieved by taking advantage of the special structure of the main sync code. On the other hand, the main synchronization code must have a minimum aperiodic autocorrelation sublobe to minimize the possibility that the mobile station will synchronize to the sublobe instead of the desired primary lobe.

This latter requirement for cell searcher synchronization codes is that the disclosure is incorporated herein by reference in U.S. Patent Application No. 09/135247, entitled "Communication Methods and MFP Based," which was assigned to the assignee of the present application. On Orthogonal Hadamard-Based Sequences Having Selected Autocorrelation Properties , as proposed in the August 17, 1998 application, can be met by using Goray complementary sequences. The patent application does not specify an efficient method of matched filtering of the main synchronization code based on the Goray complementary sequence for use in the first cell search step. Fortunately, the present invention provides an efficient embodiment using a Goray complementary sequence as the primary synchronization code.

An efficient Goray correlator similar to the EGC100 shown in Figure 7 is shown in Figure 11, for example, matched to a hierarchical primary sync code by using it as the primary sync code correlator in the first step of cell search. It provides greater implementation benefits than the Hierarchical Correlator (HC), which is similar to Correlator 400. The 256-length hierarchical code is obtained by serial or hierarchical concatenation of two component sequences of 16 length, as included in one proposal for the UTRA system. In a preferred embodiment, the length of the main sync cord is 256 chips. The 256-length Goray complementary sequence has the smallest maximum absolute aperiodic autocorrelation sublobe (MAS) value, making it ideal for application as a main cell search code. The minimum MAS value obtained for all Goray complementary sequences of length 256 is 12. One of the pairs of Goray sequences with MAS = 12 is defined by the following equation.

P_n= {6,3,7,2,1,4,0,5} and W_n= {1, -1, -1,1,1, -1,1,1} (3) EGC memory bits N_memCan be calculated by taking into account the number of memory cells in each delay line and the fact that after the first delay line, the memory cell word length increases by one for each new delay line. Assuming 1-bit quantization of the received signal, it is as follows.

N_mem^(EGC)=1・2⁶+2・2³+3・2⁷+4・2²+5・2¹+6・2⁴+7・2⁰+8・2⁵= 849 Hierarchical correlators (HCs) require one simple correlator of length 16 and 15 delay lines of length 16. The memory cell word length of each such delay line is 5 bits. Therefore, for this HC, N_mem^(HC)= 1 16 + (5 16) 15 = 1216.

Goray complementary sequences correlated by EGC provide the following advantages over hierarchical sequences: -The number of adders is 16 for EGC compared to 30 for HC. -The number of multipliers is 8 in EGC compared to 32 in HC. -The number of memory bits is 30% less in EGC than in HC. -In the Goray complementary sequence, the maximum absolute value of the aperiodic autocorrelation sublobe is 1/3 of the hierarchical sequence.

An embodiment of another example of the present invention provides an efficient factorized Goray correlator. Such a correlator of length 256 is shown in FIG. The factorized Goray sequence can be configured as a concatenation of two shorter component (complementary) sequences, for example 64 in length. In that case, the correlator 700 has an efficient Goray correlator 710 with length 64, delay lines 720, 730, 740, and 750 with length 64, and a multiplier 790, similar to those shown in FIG. , And adders 760, 770, and 780. The total number of multipliers is at most 10, and the total number of adders is equal to 15. Note that the number of adders is one less than for an EGC with a length of 256. The actual number of delay lines depends on the interleaving sequence.

The correlator 700 can be useful when the interfering time of the receiver local oscillator is shorter than the sequence length (eg, at most 64 chips). As a result, a non-coherent integral of the optimal lower limit of the intermediate correlation value is required. In other words, the correlator 700 allows for both coherent and non-coherent integration of intermediate correlation values. The correlator 700 in the example of FIG. 14 is coherent. In this example, a Gorey sequence of length 256 is represented as {-B, B, A, A}, where A and B are complementary sequences of length 64.

In the second step of cell search, a set of 17 second sync codes (SSCs) with 256 chips in length can be used. The SSC must be orthogonal to the main sync code (PSC). Assuming that the principal synchronization code is a Goray complementary sequence according to an application of one example of the invention, one method of generating a set of 17 orthogonal SSCs is incorporated herein by reference with its disclosure. , U.S. Patent Application No. 09/135247 transferred to the assignee of the present application, entitled "Communication Methods and MFP Based on Orthogonal Hadamard-Based Sequences Having Selected Autocorrelation" Properties , proposed in an application filed August 17, 1998. Orthogonal pairs of SSCs are generated by multiplying the PSC by 17 different Walsh functions of the same length. Such a set of SSCs allows the use of a fast Hadamard transform (FHT) processor in the second step of cell search to reduce implementation complexity. Furthermore, when the PSC is a Goray complementary sequence, the set of sequences obtained by multiplying the Goray PSC by a different Walsh function results in an orthogonal set of Goray sequences. In this case, these SSCs can also be detected using a bank of EGCs similar to the main synchronization code correlation procedure described above. Banks of such EGCs according to the invention are more efficient than FHT-based correlations in terms of the number of operations required.

An additional requirement for SSCs is to reduce the aperiodic cross-correlation between the PSC and each of the 17 SSCs in order to minimize interference from the second sync code to the main sync code correlator. In this case, equation (2) is used to generate the complete set of 256 orthogonal goray sequences of 256 chips in length, selecting one of these goray sequences as the main sync code, and then It is advantageous to select 17 second sync codes, each with a maximum absolute aperiodic cross-correlation with the primary sync code below a reasonable threshold. For example, assuming that the PSCs are the a (k) sequences generated by equations (1) and (3), there are 17 SSCs with maximum absolute aperiodic cross-correlation with PSCs below the 42 threshold. The set is defined by the same substitution vector as in Eq. (3) and the following weighting vector.

W_SSC1= {1 1 1 -1 1 1 -1 1}, (a) W_SSC2= {1 -1 1 -1 -1 -1 1 1}, (b) W_SSC3= {-1 1 1 -1 -1 1 1 1}, (b) W_SSC4= {-1 1 1 -1 -1 -1 -1 1}, (a) W_SSC5= {-1 1 -1 1 1 1 -1 1 1}, (b) W_SSC6= {-1 -1 1 -1 -1 1 1 1}, (b) W_SSC7= {-1 -1 1 -1 -1 -1 -1 1}, (a) W_SSC8= {-1 -1 -1 1 1 1 1 1}, (b) W_SSC9= {-1 -1 -1 1 1 -1 1 1}, (a) W_SSC10= {-1 -1 -1 1 1 -1 -1 1}, (a) W_SSC11= {-1 -1 -1 1 -1 -1 1 1}, (b) W_SSC12= {-1 -1 -1 1 -1 -1 -1 1}, (a) W_SSC13= {-1 -1 -1 1 -1 -1 -1 1}, (b) W_SSC14= {-1 -1 -1 -1 1 1 1 1}, (a) W_SSC15= {-1 -1 -1 -1 1 1 -1 1}, (a) W_SSC16= {-1 -1 -1 -1 -1 1 1 1}, (a) W_SSC17= {-1 -1 -1 -1 -1 1 -1 1}, (a) (Four) The corresponding sequence SSCn is the weighting vector W_SSCnIs equal to the Goray sequence a (k) or b (k) when is replaced by (1) (in (4), it is shown in parentheses attached to each vector). SSCs can be detected using the corresponding banks of 17 (or less) EGCs, as in the case of PSCs.

In addition to improved implementation efficiency, synchronization codes based on Goray complementary pair sequences are superior in terms of maximum absolute aperiodic autocorrelation sublobes (MAS) compared to, for example, synchronous sequences based on concatenated orthogonal gold sequences. Provides good performance. This comparison is shown by the graphs in FIGS. 15 and 16. FIG. 15 is a graph of the aperiodic autocorrelation function of the orthogonal gold sequences connected in series. Note that while the samples corresponding to the 0 delay have a substantial maximum, the various non-zero delays also have a significant maximum peak that can cause false correlation detection. In contrast, in the graph of Figure 16, for synchronization codes based on the Goray complementary pair sequence, the sublobe is much lower and within the critical range for random access detection (ie, ± 255 chips from the main lobe). Is shown to be even lower than the other parts.

For the application of the orthogonal Goray complementary sequence as a random access preamble, its aperiodic autocorrelation characteristics are compared to that of another set of orthogonal preambles obtained by serial concatenation of orthogonal signatures using a common preamble diffusion code. This is very important. The parameter of comparison is the maximum absolute aperiodic autocorrelation sublobe (MAS) of each of the preambles in the set. In a comparison of this example for a UTRA system currently under development, a set of 16 orthogonal Golay sequences of length 4096 according to the present invention is combined with another UTRA proposal for a RACH preamble based on an orthogonal gold sequence. Compare. Table 4 shows 16 Goray sequences as a function of two shorter component complementary sequences A (k) and B (k) of length 256.

<tables num="4"><img file="JP5114585B2_D0008.tif" /></tables>

This component Goray sequences A (k) and B (k) are permuted P_n= {0,2,1,5,6,4,7,3} And weighting W_n= {1, -1,1, -1,1, -1, -1,1} Is obtained from Eq. (1) using.

The MAS value of the set of 16 orthogonal goray sequences defined above and the 16 spread by the general preamble spread code (preamble spread code number n = 1) described in another proposal for UTRA. Table 5 shows the MAS values for a set of 16 concatenated orthogonal gold sequences obtained from the orthogonal signatures.

<tables num="5"><img file="JP5114585B2_D0009.tif" /></tables>

As explained earlier, the random access preamble is not completely asynchronous to the base station receiver because the mobile terminal already has basic information about the base station timing, but between the base station and the mobile terminal. There is uncertainty introduced by the round trip propagation delay. One reasonable assumption is that the round trip delay is at most 255 chips, so the aperiodic autocorrelation function of the random access preamble is actually only important in the area ± 255 chips from the main lobe. It means that there is. The maximum absolute values of the aperiodic autocorrelation sublobes within the region ± 255 chips from the main lobe are shown in Table 6 for the 4096-length orthogonal Golay sequence and the concatenated orthogonal gold sequences described above.

<tables num="6"><img file="JP5114585B2_D0010.tif" /></tables>

Table 6 shows that the orthogonal goray sequence has an autocorrelation sublobe 25 times lower than the concatenated orthogonal gold sequence in the region ± 255 chips from the primary lobe.

Having described the invention with respect to specific embodiments, one of ordinary skill in the art will appreciate that the invention is not limited to the particular embodiments described and illustrated herein. The present invention may also be practiced using different formats, embodiments, and adaptations other than those illustrated and described, as well as numerous modifications, modifications, and equivalent arrangements. Therefore, although the present invention has been described with respect to its preferred embodiments, it should be understood that this disclosure is merely exemplary, not restrictive, and merely exemplary of the invention.