WO1999063704A1

WO1999063704A1 - Verfahren und vorrichtung zur erfassung eines empfangssignals durch korrelation mit einer vorgegeben diskreten signalfolge

Info

Publication number: WO1999063704A1
Application number: PCT/DE1999/001319
Authority: WO
Inventors: Bernhard Raaf
Original assignee: Siemens AG; Siemens Corp
Current assignee: Siemens AG; Siemens Corp
Priority date: 1998-05-29
Filing date: 1999-05-03
Publication date: 1999-12-09
Anticipated expiration: 2000-11-29

Abstract

Ein Verfahren zur Erfassung eines Empfangssignals durch Korrelation mit wenigstens einer diskreten vorgegebenen Signalfolge c(i), wobei i eine ganze Zahl </=n ist, welche Signalfolge c(i) eine endliche Anzahl diskreter Werte annehmen kann, weist die Verfahrensschritte auf: (a) Ableitung von Signalfolgen a(i) aus dem Empfangssignal, (b) Vergleich von Wertepaaren c(i), c(j) der vorgegebenen diskreten Signalfolge, (c) Bildung von Teilsummen T der Produkte zweier oder mehrerer Werte einer Empfangssignalfolge a(i) mit einer entsprechenden Anzahl von Werten c(i) der wenigstens einen vorgegebenen diskreten Signalfolge, (d) Ermittlung von Korrelationssummen S mehrerer Signalfolgen a(i) mit der wenigstens einen vorgegebenen diskreten Signalfolge c(i) durch Kombination der in Schritt (c) gebildeten Teilsummen T in Abhängigkeit von dem Vergleichsresultat aus Schritt (b), (e) Weiterverarbeitung der in Schritt (d) ermittelten Korrelationssummen. Das erfindungsgemässe Verfahren ermöglicht eine Verringerung des Rechenaufwandes und damit der erforderlichen Zeit zur Erfassung eines Empfangssignals, beispielsweise zur Detektion von spezifischen Signal-Bursts bei Mobilfunksystemen.

Description

Beschreibung

Verfahren und Vorrichtung zur Erfassung eines Empfangssignals durch Korrelation mit einer vorgegebenen diskreten Signalfolge.

Bei Signalübertragungssystemen wie beispielsweise Mobilfunksystemen ist es erforderlich, daß einer der Kommunikations- partner bestimmte festgelegte Signale erkennt, die von einem anderen Kommunikationspartner ausgesandt werden. Dabei kann es sich beispielsweise um sogenannte Synchronisierungs-Bursts zur Synchronisierung zweier Kommunikationspartner oder um sogenannte Access-Bursts handeln.

Um derartige Empfangssignale gegenüber dem Umgebungsrauschen zuverlässig zu erfassen bzw. zu identifizieren ist es bekannt, das Empfangssignal fortlaufend über eine festgelegte Zeitdauer mit einer vorgegebenen Signalfolge zu korrelieren und die Korrelationssumme über die Zeitdauer der vorgegebenen Signalfolge zu bilden. Der Bereich des EmpfangsSignals, der eine maximale Korrelationssumme ergibt, entspricht dem gesuchten Signal. Dem Synchronisationssignal von der Basisstation eines digitalen Mobilfunksystems ist beispielsweise eine sogenannte Trainingssequenz vorgeschaltet, die auf die eben beschriebene Weise in der Mobileinheit durch Korrelation mit der abgespeicherten Signalfolge erfaßt wird. So können die Mobileinheiten mit der Basisstation synchronisiert werden.

Auch in der Basisstation sind derartige Korrelationsberech- nungen beispielsweise bei der Random-Access-Channel (RÄCH) - Detektion erforderlich. Außerdem wird eine Korrelationsberechnung auch zur Bestimmung der Kanalimpulsantwort und der Signallaufzeiten empfangener Signalbursts durchgeführt.

Die Korrelationssumme wird dabei wie folgt berechnet: S_m = ∑_l (i + m)-c(i) , i=l

wobei a(i) eine aus dem Empfangssignal abgeleitete Empfangssignalfolge und c(i) die vorgegebene diskrete Signalfolge ist, wobei i von 1 bis n läuft. Die Korrelationssumme S_m wird aufeinanderfolgend für mehrere zeitlich versetzte, aus dem Empfangssignal gewonnene Signalfolgen a(i) berechnet, und dann der maximale Wert S_m bestimmt. Sollen k aufeinanderfolgende Korrelationssummen berechnet werden, so beträgt der Be- rechnungsaufwand k^*n Operationen, wobei eine binäre Multiplikation und Addition als eine Operation gezählt wird.

Die Berechnung der Korrelationssummen ist daher sehr aufwendig und erfordert, insbesondere für Real-Time-Anwendungen wie Sprachkommunikation oder Bildtelefon leistungsfähige und daher teure Prozessoren.

Zur Verringerung des Rechenaufwandes ist es bekannt, eine Fast-Fourier-Transformation einzusetzen, durch welche die Faltung durch eine Multiplikation ersetzt wird (siehe M.M. Naßhan: Realitätsnahe Modellierung und Simulation nachrichtentechnischer Systeme, gezeigt am Beispiel des CDMA-Mobilfunksystems, VDI-Verlag, Düsseldorf 1995) . Der Rechenaufwand beträgt in diesem Falle ( (2-log (n+k) ) +1) * (n+k) Operationen. Dies ist für sehr große k ein günstiger Wert, wenn über einen weiten Bereich korreliert werden soll und

2^*log(n+k) +l*«min (n, k) ist und der Korrelationsbereich nicht viel größer als die vorgegebene Folge c(i) ist. Für kleine Anzahlen k von Korrelationssummen ist dieses Verfahren jedoch weniger effektiv. Ein weiterer Nachteil ist, daß für die Fast-Fourier-Transformation der Signalfolge c zusätzlicher Speicherplatz benötigt wird, das Programm für die FFT aufwendig ist und die Multiplikationen 2-fach-komplexe Multiplikationen sind, die doppelt so aufwendig sind wie ein Multipli- kation der komplexen Werte der Empfangssignalfolge a(i) mit . reellen Werten c(i) der vorgegebenen Signalfolge. Der vorliegenden Erfindung liegt daher die Aufgabe zugrunde, ein verbessertes Verfahren zur Erfassung eines Empfangs-si^¬ gnals durch Korrelation mit einer vorgegebenen diskreten Si- gnalfolge vorzuschlagen, bei der der Rechenaufwand verringert ist .

Gelöst wird die Aufgabe durch das in Anspruch 1 definierte Verfahren und die in Anspruch 15 definierte Vorrichtung. Die Unteransprüche beschreiben vorteilhafte Weiterbildungen des erfindungsgemäßen Verfahrens bzw. der erfindungsgemäßen Vorrichtung.

Das erfindungsgemäße Verfahren enthält die Verfahrens- schritte:

(a) Ableitung von zeitlich zueinander versetzten Signalfolgen aus einem Empfangssignal,

(b) Vergleich von Wertepaaren c(i), c(j) der vorgegebenen diskreten Signalfolge,

(c) Bildung von Teilsummen T der Produkte zweier oder mehrerer Werte einer Empfangssignalfolge a(i) mit einer entspre- chenden Anzahl von Werten c(i) der vorgegebenen diskreten Signalfolge,

(d) Ermittlung von Korrelationssummen S mehrerer zeitlich zueinander versetzter Signalfolgen a(i) mit der vorgegebenen diskreten Signalfolge c(i) durch Kombination der in Schritt (c) gebildeten Teilsummen T in Abhängigkeit von dem Vergleichsresultat aus Schritt (b) ,

(e) Vergleich der in Schritt (d) ermittelten Korrelationssum- men . Dabei können die einzelnen Verfahrensschritte in der oben angegebenen Reihenfolge ausgeführt werden oder in einer anderen für einen Fachmann leicht als vorteilhaft zu erkennenden Reihenfolge durchgeführt werden, wie beispielsweise: • (b) (a) (c) (d) (e) oder

• (b) (c integriert mit a) (d) (e)

Unter Ableitung von Signalfolgen aus einem Empfangssignal versteht ein Fachmann auch eine Demodulation, Filterung, De- rotation, Skalierung oder Analog/Digtalwandlung der Empfangssignale .

Bei der Bildung aufeinanderfolgender Korrelationssummen S_n gehen bis auf neu hinzukommende bzw. wegfallende Randterme die gleichen Werte a(i) der Empfangssignalfolge in die Berechnung ein. Da die diskrete Signalfolge c(i) nur eine endliche Anzahl diskreter Werte, beispielsweise die Werte ±1, annehmen kann, läßt sich die Berechnung der Korrelationssummen durch Bildung von Teilsummen, die in die Berechnung von zwei oder mehreren aufeinanderfolgenden Korrelationssummen S_n eingehen, vereinfachen. Ist beispielsweise der Wert c(i) der vorgegebenen diskreten Signalfolge +1 und der Wert c(i-l) oder auch c(i-2) = -1, so kann das Ergebnis der einmal ausgeführten Multiplikation a(i)* c(i) für aufeinanderfolgende Korrelationssummen, in denen die Signalfolgen a(i) und c(i) sukzessive zueinander verschoben werden, mehrfach benutzt werden. So verringert sich der erforderliche Gesamtrechenaufwand erheblich. Je nach Länge des zu erfassenden Signals bzw. der vorgegebenen Signalfolge c(i) und den vorhandenen Hard- ware-Strukturen können Teilsummen von zwei oder mehreren benachbarten Termen der Empfangssignalfolge a(i) gebildet werden.

Vorzugsweise kann die vorgegebene diskrete Signalfolge die Werte c(i) = +1, -1 annehmen, so daß in Schritt (d) die Korrelationssummen S durch Addition bzw. Subtraktion der in Schritt (c) gebildeten Teilsummen T ermittelt werden können. Die Werte c(i) der vorgegebenen diskreten Signalfolge können eine endliche Menge M mit m Elementen oci, α₂, ..., ot_m bilden, für die gilt, daß das Produkt zweier Werte aus M wieder ein Element aus M ist. Ein Beispiel für eine solche Menge ist die Menge der Elemente { +1, -1, i , X } ' wobei i. = V-l ist. Ein Wert c(i) der vorgegebenen diskreten Signalfolge ist daher durch Produkt aus einem anderen Wert c(j) erhältlich. Entsprechend werden die Korrelationssummen durch Addition der Teilsummen, multipliziert mit dem zugehörigen Wert (beispielsweise +1, -1, i, -i) ermittelt.

Gemäß einer Variante des erfindungsgemäßen Verfahrens wird in Schritt (c) eine erste Teilsumme Tl aller Produkte a(i)^* c(i) gebildet für die gilt c (i) =c (i-1 ) , und eine zweite Teilsumme T2 aller Produkte a(i) ^* c(i) gebildet, für die gilt: c(i)=- c(i-l), und in Schritt (d) eine erste Korrelationssumme S(0) als Summe der Teilsummen Tl und T2 und eine zweite Korrelationssumme S(l) als Differenz der Teilsummen Tl und T2 ermit- telt. Zur weiteren Verringerung des Rechenaufwandes werden bei der Berechnung der Teilsummen Tl und T2 vorzugsweise jeweils zunächst alle Werte a(i) aufsummiert, die mit c(i) = -1 zu multiplizieren sind, die so gebildete Summe invertiert und dann alle Werte a(i) hinzuaddiert, die mit c(i) = +1 zu mul- tiplizieren sind. Vorzugsweise werden bei der Berechnung der Korrelationssummen S(0) und S(l) noch die Randterme c(0)^* a(0) und c(n)* a(n) berücksichtigt.

Bei einer weiteren Variante des erfindungsgemäßen Verfahrens werden in Schritt (c) Summen und Differenzen jeweils benachbarter Wertepaare a(i), a(i+l) der Empfangssignalfolge gebildet und ein korrespondierender Wert c(i) der vorgegebenen diskreten Folge mit der Wertesumme a (i) +a (i+1) multipliziert, falls c(i) = c(i+l) ist und mit der Wertepaardifferenz a(i)- a(i-l) multipliziert, falls c(i) = c(i+l) ist. In Schritt (d) werden Korrelationssummen S(0) und S(l) durch Addition der in Schritt (c) erhaltenen Teilsummen ermittelt. Bei dieser Ver- fahrensvariante werden in Schritt (c) erst viele Teilsummen aus je zwei Termen berechnet und diese dann in Schritt (d) passend kombiniert, um die Korrelationssummen zu erhalten.

Die Werte der Empfangssignalfolge a(i) können beliebige komplexe oder reelle Werte annehmen.

Um eine möglichst effiziente Berechnung zu ermöglichen, werden die in Schritt (b) erhaltenen Vergleichsresultate vor- zugsweise als Tabelle abgespeichert.

Im folgenden wird die Erfindung anhand verschiedener Ausführungsbeispiele und unter Bezugnahme auf die beiliegende Zeichnung erläutert, in der

Fig. 1 eine schematische Illustration von Signalfolgen zur Erläuterung eines Ausführungsbeispiels des erfindungsgemäßen Verfahrens ist;

Fig. 2 eine weitere schematische Darstellung von Signalfolgen zur Erläuterung eines Ausführungsbeispiels des erfindungsgemäßen Verfahrens ist;

Fig. 3 ein Blockschaltbild ist, das schematisch den Aufbau eines Ausführungsbeispiels einer erfindungsgemäßen Vorrichtung zur Erfassung eines Empfangssignals zeigt; und

Fig. 4 ein Blockschaltbild eines weiteren Ausführungsbei- spiels der erfindungsgemäßen Vorrichtung zur Erfassung eines Empfangssignals ist.

1. Ausführungsbeispiel

Es sollen Korrelationssummen S einer festgelegten diskreten Signalfolge c(i) mit n Werten mit aus einem Empfangssignal abgeleiteten, zeitlich zueinander versetzten Empfangssignalfolgen a(i) gemäß Formel (1) gebildet werden und die erhalte- nen Korrelationssummen verglichen werden. Das Empfangssignal, das die höchste Korrelationssumme S_n hervorruft, d.h. das die größte Übereinstimmung mit der vorgegebenen Signalfolge c(i) hat, wird als gesuchtes Empfangssignal identifiziert.

Die vorgegebene diskrete Signalfolge hat in diesem Ausführungsbeispiel die Eigenschaft, daß die Werte c(i) entweder +1 oder -1 sind. Diese Tatsache wird ausgenutzt, um die Berechnung aufeinanderfolgender Korrelationssummen zu vereinfachen. In zwei aufeinanderfolgenden Korrelationssummen S(0) und S(l) gehen mit Ausnahme zweier Randterme a(0) und a (n) alle Terme a(i) in beide Korrelationssummen ein, teils mit gleichem, teils mit unterschiedlichem Vorzeichen. Bei dem ersten Ausführungsbeispiel des erfindungsgemäßen Verfahrens werden zwei Teilsummen Tl und T2 gebildet. Die Teilsumme Tl enthält alle Terme a(i)* c(i), die in die aufeinanderfolgenden Korrelationssummen S(0) und S(l) mit gleichem Vorzeichen eingehen, d.h. bei denen c(i) = c(i-l) ist, während die zweite Teilsumme T2 die Terme a(i) * c(i) enthält, die in die beiden aufeinanderfolgenden Korrelationssummen S(0) und S(l) mit unterschiedlichem Vorzeichen eingehen, d.h. für die c(i) = - c(i-l) ist.

Zunächst werden jeweils benachbarte Werte c(i), c(i-l) der vorgegebenen diskreten Signalfolge miteinander verglichen, wobei Cl(i) := 1 gesetzt wird, wenn c(i) = c(i-l) und Cl(i) = -1 gesetzt wird, wenn c(i) = c(i-l) ist.

Dann werden die Teilsummen Tl und T2 wie folgt berechnet:

T2 = ∑a(i) - c(i) |C1( = -1 (3; i=2

Die Korrelationssummen S(0) und S(l) berechnen sich dann wie folgt: S(0) = c(T) -a(l) + Tl + T2 (4)

S(V) = T\ - T2 + c(n) -a(n) (5)

Für die Berechnung der dann folgenden Korrelationssummen S(2) und S(3) wird mit dem gleichen Verfahren erneut begonnen.

Bei dem beschriebenen Verfahren benötigt man zur Berechnung der Teilsummen Tl und T2 n-1 Operationen und anschließend vier weitere Operationen, um die zwei Korrelationssummen S(0) und S(l) zu berechnen, insgesamt also n+3 Operationen statt 2n Operationen bei direkter Berechnung der Korrelationssummen nach Gleichung (1) . Dies entspricht für größere n fast einer Halbierung des Rechenaufwandes. Bei der Implementierung des Verfahrens in einem digitalen Signalprozessor ist jedoch noch zu berücksichtigen, daß das Aufsammeln der Werte a(i) der Empfangssignalfolge in zwei Summen wegen der erforderlichen indirekten Adressierung auch Zeit erfordert. Dazu ist es vor- teilhaft, bei der Berechnung der Teilsummen jeweils zunächst alle Werte a(i) aufzusummieren, die negativ eingehen, d.h. mit c(i) = -1 zu multiplizieren sind, die so gebildete Summe zu invertieren und dann alle Werte a(i) hinzuzuaddieren, die positiv eingehen, d.h. mit c(i) = +1 zu multiplizieren sind. Eine andere Möglichkeit ist, erst alle Terme für die Teilsumme Tl und dann diejenigen für die Teilsu me T2 aufzusammeln.

Vorteilhaft ist es in jedem Fall, die Werte Cl(i) abzuspei- ehern und für die Berechnung mehrerer Korrelationssummen zu verwenden.

2. Ausführungsbeispiel

Das zweite Ausführungsbeispiel stellt eine Verallgemeinerung des ersten Ausführungsbeispiels dar, bei dem statt zwei m+1 Korrelationssummen gleichzeitig berechnet werden. Dazu bildet man 2^m Teilsummen, die dann mit folgenden Vorzeichen in die jeweiligen Korrelationssummen eingehen:

k: 1 2 3 4

Tl + + + +

T2 + + +

T3 + + - +

T4 + + - -

T5 + - + +

T6 + - + -

T7 + - - +

T8 + - - -

In der Tabelle sind Randterme, die nicht in alle Korrella- tionssummen eingehen, nicht berücksichtigt. Wie aus der Tabelle ersichtlich ist, bestimmt somit eine Binärdarstellung des Index k der Teilsumme, in welche der Korrelationssummen die Teilsumme mit positiven bzw. negativen Vorzeichen eingeht. Nach Berechnung der Teilsummen müssen dann nur 2^m Terme statt n Terme plus zusätzlich die Randterme addiert werden.

Durch schrittweises Zusammenfassen der Teilsummen T läßt sich weiterer Rechenaufwand sparen.

Zunächst werden nach dem folgenden Schema 2^m Teilprodukte gebildet. Der Autokorrelationskoeffizient K(i, j) wird definiert als K(i, j) = 0, wenn c(i) = c(j) und K(i, j)= 1, wenn c(i) = -c(j) .

Anschließend wird

index (i) = K(i, i-1) +2* K (i, i-2) + ...+2^m_1*K (i, i-m) (6)

berechnet und abgespeichert. Anschließend werden die Teilsummen für i = m bis n-l+n berechnet: T ( index ( i ) ) = __ (i)-c(i)

Schließlich wird die m+l-te Korrelationssummen S (m) berechnet :

2(m-l)_ι _^m — \

S(m) = ∑ T(k)- ∑T(k) (! i=0 k=2^m~^l

Dann müssen noch die Randwerte dazuaddiert werden. Danach werden je zwei Teilsummen zusammengefaßt. Dies läßt sich als Schleife in Pseudo-Programmiercode wie folgt ausdrücken.

for i=0 to 2^m_1-l T(i)+=T(i+2^m_1) end i

Danach wiederholt man die letzten beiden Schritte nach Substitution von m durch m-1 und erhält so S(m-l) bis S(0).

Der Rechenaufwand beträgt n Index-Operationen für die Berechnung von Gleichung (7) plus 2^m_1 Operationen für die Berechnung von Gleichung (8) plus 2^n_1+2 Index-Operationen für die Zusammenfassung von je zwei Ter en. Der Rechenaufwand für einen Schritt beträgt daher 2^m+2 Index-Operationen und der Ge- samt-Rechenaufwand dann n Index-Operationen + (2m+l) Index- Operationen + 2^m+1~1 gewöhnliche Rechenoperationen. Eine Index-Operation ist im allgemeinen aufwendiger als ein direkter Zugriff. Für die Abschätzung der benötigten Rechenzeit wird eine Index-Operation als 3/2 gewöhnliche Operationen gewer- tet.

In den folgenden Tabellen 2 und 3 wird der Rechenaufwand des Verfahrens des zweiten Ausführungsbeispiels der Erfindung mit der direkten Berechnung der Korrelationssummen nach Gleichung (1) und mit einem Fast-Fourier-Transformations (FFT) -Verfah- ren mit Signalfolgenlängen (Trainingssequenzlängen) von n = 41 bzw. n = 64 Werten, was der Trainingssequenz eines Syn- chronisierungs-Bursts bzw. eines Access-Bursts entspricht, verglichen. In den Tabellen wird der Rechenaufwand in Opera- tionen für verschiedene Werte k jeweils gleichzeitig berechneter Korrelationssummen verglichen. Ein Wert k = 1 entspricht daher dem ersten Ausführungsbeispiel und die höheren Werte für k dem zweiten Ausführungsbeispiel der Erfindung. Die Spalte "relativ" gibt den relativen Rechenaufwand im Ver- gleich zur direkten Berechnung der Korrelationssummen an. Dabei wird in den beiden linken Spalten eine Index-Operation wie eine gewöhnliche Rechenoperation gezählt und in den beiden rechten Spalten wie 1,5 gewöhnliche Rechenoperationen ge- wichtet . Tabelle 2

Index param. 1 1

Burs typ access Burst sync Burst n 41 64 k Erfindg normal relativ Erfindg normal relativ

1 1 45 41 68 64

2 49 82 0.6 72 128 0.56

3 55 123 0.45 78 192 0.41

4 65 164 0.4 88 256 0,34

5 83 205 0.4 106 320 0.33

6 117 246 0,48 140 384 0.36

7 183 287 0.64 206 448 0.46 5 8 313 328 0.95 336 512 0.66

9 571 369 1.55 594 576 1.03

10 1085 410 2.65 1108 640 1.73

1.5 1.5 access Burst sync Burst

41 64 o Erfindg normal relativ Erfindg normal relativ

67 41 101.5 64

72 82 0.88 106.5 128 0.83

79 123 0.64 113.5 192 0.59

90 164 0.55 124,5 256 0,49

109 205 0.53 143.5 320 0.45 5 144 246 0.59 178.5 384 0.46

21 287 0.74 245.5 448 0.55

342 328 1,04 376.5 512 0.74

601 369 1.63 635.5 576 1.1

1116 410 2.72 1151 640 1.8 Tabeile 3

Index param. 1 1

Bursttyp > access Burst sync Burst n 41 64 k 1 ⁼FT normal relativ FFT normal relativ

1 832 41 1920 64

2 832 82 10.1 1920 128 15

4 832 164 5,07 1920 256 7.5

8 832 328 2.54 1920 512 3.75

16 832 656 1.27 1920 1024 1.88

32 1920 1312 1.46 1920 2048 0,94

64 1920 2624 0,73 1920 4096 0,47

128 4352 5248 0.83 4352 8192 0.53

256 9728 10496 0.93 9728. 16384 0.59

960 21504 39360 0.55 21504 61440 0.35

156 4352 6396 0.68 4352 9984 0.44

1250 47104 51250 0.92 47104 80000 0.59

1408 47104 57728 0.82 47104 90112 0.52

13750 475136 6E+05 0,84 5E+05880000 0.54

1.5 1.5 access Burst sync Burst

41 64

FFT normal relativ FFT normal relativ

1248 41 2880 64

1248 82 15.2 2880 128 22.5

1248 164 7.61 2880 256 11,3

1248 328 3.8 2880 512 5.63

1248 656 1.9 2880 1024 2.81

2880 1312 2.2 2880 2048 1.41

2880 2624 1.1 2880 4096 0.7

6528 5248 1.24 6528 8192 0.8

14592 10496 1.39 14592 16384 0.89

32256 39360 0.82 32256 61440 0.53

6528 6396 1.02 6528 9984 0.651 TS

70656 51250 1.38 70656 80000 0,888 TS

70656 57728 1.22 70656 90112 0.789 TS

7127046E+05 1.26 7E+05 9E-HD5 0,8111 Fra

Bei Berücksichtigung der höheren Gewichtung für Index-Operationen läßt sich für k = 5 eine maximale Rechenzeiteinsparunσ von 47 % für n = 41 und von 55 % für n = 64 erreichen. Bei normalen Bursts mit einer Trainingssequenz von nur 26 Bit ■ läßt sich eine Einsparung von noch 35 % erzielen. Für Anwendungen mit längeren Trainingssequenzen (d.h. größerem n) wer- 12a den die möglichen Rechenzeiteinsparungen noch größer. Für größere k dominiert der exponentielle Term, so daß der Rechenaufwand wieder zunimmt. Mit Fast-Fourier-Transformation lassen sich vergleichbare Rechenzeiteinsparungen erst bei we- sentlich höheren Werten von k erzielen.

3. Ausführungsbeispiel

Bei dem oben beschriebenen ersten erfindungsgemäßen Ausfüh- rungsbeispiel wurden zunächst zwei Teilsummen über viele a(i) gebildet und dann die beiden Teilsummen Tl und T2 additiv oder substraktiv kombiniert. Diese Reihenfolge läßt sich auch umkehren, also erst viele Teilsummen aus je zwei Termen berechnen und diese Teilsummen dann passend kombinieren.

Zunächst werden für k = 2i die Summen T(0, k) = a(i)+a(i+l) und T(l, k) = a(i)-a(i+l) gebildet. Die erste Korrelations- summe S(0) wird dann wie folgt berechnet (Pseudo-Code-Dar- Stellung, n sei gerade) :

for i=0 to (n-2) step 2 if c(i) = c(i+l) then S(0) += T(0,i) ^* c(i) eise S(0) += T(l,i) ^* c(i) end if end i

Die zweite Korrelationssumme S(l) wird ähnlich berechnet, wo- bei hier auch zwei Randterme auftreten:

S (1) = a(l) ^* c(0)+ a(n) ^■ c(n-l) for i=2 to (n-^**2) step 2 if c(i-l) = c(i) then S(l) += T(0, i) ^* c(i-l) eise S (1) += T(l, i) ^* c(i-l) end if end i

Es werden bei diesem Ausführungsbeispiel also zunächst zwei aufeinanderfolgende Terme der Empfangssignalfolge addiert bzw. subtrahiert und jeweils mit einem Wert c(i) multipliziert und die so gebildeten Teilsummen dann zu den Korrelationssummen S(0) und s(l) zusammengefaßt.

Statt einer Summe über n Terme wie beim ersten Ausführungsbeispiel muß nur eine Summe von n/2 Termen berechnet werden. Die Berechnung der Terme T(0,i) bzw. T(l,i) benötigt n Additionen, kann aber für mehrere Korrelationssummen verwendet werden. Berechnet man zwei Korrelationssummen, so benötigt man n+2 ^• (n/2) +1 = 2n+l Operationen, d.h. eine Operation mehr als bei der direkten Berechnung der Korrelationssummen nach Gleichung (1). Bei der Berechnung einer größeren Anzahl von j Korrelationssummen benötigt man (n+j ) [Vorberechnung der Terme T] + j*(n/2) [Summe der T] + j/2 (Mehraufwand für Randterme) = j-n/2 + n + j-3/2 Operationen, was etwas mehr als die Hälfte des konventionellen Aufwandes von n*j Operationen ist.

Ähnlich wie beim zweiten Ausführungsbeispiel können auch bei dem dritten Ausführungsbeispiel weitere Effizienz-Steigerungen durch Zusammenfassung von Rechenoperationen erzielen.

4. Ausführungsbeispiel

Bei der Suche eines SC-Bursts oder eines RACH-Bursts sucht man über einen gewissen Bereich das Maximum der Korrelation des Empfangssignals mit dem abgespeicherten vorgegebenen Signal. Dabei kann man das erfindungsgemäße Verfahren wie folgt optimieren. In einem ersten Schritt wird nicht die Korrelation über die gesamte Trainingssequenz des gespeicherten Signals, sondern nur über einen Teil davon berechnet. Nur wenn die Korrelationssumme dabei einen gewissen Schwellenwert überschreitet, wird der betreffende Signalabschnitt des Empfangssignals als Kandidat betrachtet und die vollständige Korrelation berechnet. Dieses Verfahren ist schematisch in Figur 1 illustriert. Das schraffierte Band (oben) stellt da- bei das Empfangssignal auf der horizontalen Zeitachse dar.

Darunter ist als weißer Balken die abgespeicherte festgelegte Signalfolge (Trainingssequenz mit drei verschiedenen Zeitversätzen dargestellt. Für die Berechnung der Korrelationssummen mit dem Empfangssignal wird zunächst nur der durch Querlinien bezeichnete Teil der gespeicherten Signalfolge verwendet. Ist die Korrelation dann so gering, daß eine weitere Berechnung keinen Erfolg erwarten läßt, wird die Berechnung abgebrochen.

Dieses Verfahren bietet folgende zwei Vorteile:

1. Es muß nicht für alle möglichen Positionen, sondern nur für die potentiell interessanten Signalsequenzen die gesamte Korrelationsberechnung ausgeführt werden. Da die Korrela^¬ tionssummen gute Autokorrelationseigenschaften haben, ist es extrem unwahrscheinlich, daß für mehrere benachbarte Zeitver^¬ sätze die komplette Korrelationssumme berechnet werden muß. Das Verfahren besitzt somit auch gute "Worst-Case"-Eigen- schaften.

Zur Berechnung der verkürzten Korrelation von k aufeinanderfolgenden Zeiten muß nicht unbedingt der gleiche Anteil der gespeicherten Signalfolge verwendet werden. Man kann statt^¬ dessen auch den gleichen Anteil des Empfangssignals verwenden, wie dies in Fig. 1 illustriert ist.

Verwendung gleicher Anteile der gespeicherten Signalfolge entspricht der folgenden Formel, wobei Kn die Länge des be- rechneten Anteils ist.

S_mj = ∑a(i + l₀ +m) - c(i) , (9)

1=1

Verwendung gleicher Anteil des Empfangssignals entspricht der folgenden Formel:

^S _m ^' , = ∑a(i)- c(i + l₀ -m) _f :ιo:

1=1

Dadurch ist eine gesonderte Behandlung der Randterme nicht erforderlich, da alle Summen, unabhängig von m die gleiche Menge der a(i) verwenden.

Anwendungsbeispiel: Anwendung in einem Rake-Receiver

In einem sogenannten Rake-Receiver werden Korrelationen des Empfangssignals mit der meist binären vorgegebenen Signalfolge, hier Spreizfolge genannt, berechnet.

Jedoch wird nicht für jeden möglichen Zeitversatz eine Korrelationssumme berechnet, sondern nur für diejenigen Zeitverzögerungen, die einem verzögerten Echo des Übertragungskanals entsprechen. Nach dem bekannten Stand der Technik wird je- weils ein Korrelator mit den übrigen für einen Rake-Finger nötigen Funktionen zu einem Modul, einem sogenannten Rake- Finger, zusammengefaßt.

Auch bei diesen Korrelatoren in den Rake-Receivern läßt sich das erfindungsgemäße Verfahren anwenden. Da die Korrelatoren den Großteil der Rechenleistung eines Rake-Receivers ausma^¬ chen, ist die mögliche Einsparung daher entsprechend hoch.

In einem Rake-Receiver müssen mehrere Korrelationssummen für verschiedene diskrete Verzögerungszeiten j, das heißt,

∑a(i + j)- C(i) ι=l

berechnet werden, wobei n hier Spreading-Faktor heißt. Zu- sätzlich müssen in der Mobilstation im Falle des sogenannten Soft-Handover und generell in der Basisstation auch Korrelationen mit einer anderen Spreizfolge berechnet werden.

In Fig. 2 stellt der obere Balken schematisch das Empfangs- signal im Zeitablauf dar. Darunter ist die Spreizfolge 1

(vorgegebene diskrete Signalfolge) mit den verschiedenen Verzögerungszeiten 1, 2 und 3 sowie eine zweite Spreizfolge 2 mit einer Verzögerungszeit 1 dargestellt. Mit dem erfindungsgemäßen Verfahren läßt sich die Korrelation der Spreizfolge 1 mit verschiedenen Zeitverschiebungen berechnen. Durch die großen Zeitverschiebungen der Spreizfolgen untereinander werden die einzeln zu addierenden Randterme jedoch einen relativ großen Effekt ausmachen. In diesem Fall kann man auf das in- krementelle Zusammenfassen der Teilsummen verzichten. Statt dessen berechnet man am Ende des jeweiligen Korrelationsintervalls aus den 2^m Teilsummen die Korrelationssumme. Als weitere Verfeinerung des Verfahrens kann man anschließend die Teilsummen T(i) nicht löschen, sondern weiter akkumulieren. Dann berechnet man nicht einzelne Korrelationssummen, sondern die Summe aller aufgelaufenen Korrelationssummen. Dadurch läßt sich dann durch Differenzbildung die gewünschte Korrela^¬ tionssumme bilden.

1. Ausführungsbeispiel der erfindungsgemäßen Empfangssignal- fassungsVorrichtung

Fig. 3 zeigt ein erstes Ausführungsbeispiel der erfindungsgemäßen Vorrichtung zur Erfassung eines Empfangssignals durch Korrelation mit einer vorgegebenen diskreten Signalfolge.

Durch die arithmetische Logikeinheit ALU 5 auf der linken Seite in Fig. 3 werden die Teilsummen berechnet und von der arithmetischen Logikeinheit ALU 7 auf der rechten Seite die Teilsummen zusammengefaßt. Beide ALUs (Akkumulatoren) können auch zweckmäßigerweise durch ein Bauelement ausgebildet werden. Die Akkumulatoren können bei genügender Bitbreite zur weiteren Einsparung von Rechenzeit auch für die gleichzeitige Abspeicherung zweier Teilsummen verwendet werden. Die gesamte Vorrichtung kann auch in die Architektur eines digitalen Si- gnalprozessors DSP integriert werden.

Die Eingangsssignalfolge wird am Dateneingang 2 empfangen und dem Akkumulator 5 zugeführt. Der Generator 1 gibt die vorgegebene diskrete Signalfolge aus, wobei das jeweils aktuelle Bit der diskreten Signalfolge den Addierer/Subtrahierer 4 steuert, so daß der entsprechende Wert der Empfangssignalfolge im Akkumulator 5 entweder addiert oder subtrahiert wird. Die so erzeugten Teilsummen werden im Speicher 3 abgespeichert. Die Adresse der Teilsumme ergibt sich als Exklu- siv-Oder-Verknüpfung der Bits der diskreten Signalfolge mit dem jeweils aktuellen Bit dieser Signalfolge.

Sobald alle Terme der Empfangssignalfolge für eine diskrete Signalfolge akkumuliert sind, wird die weitere Akkumulation unterbrochen und mittels des Akkumulators 7 aus den Teilsummen das Ergebnis berechnet. Bei der Zusammenfassung der Teilsummen werden diese linear adressiert. Die Steuerung des Ad- dierers 6 erfolgt durch dasjenige Bit des Zählers 9, das der Nummer der diskreten Signalfolge entspricht. Bei der Berech^¬ nung der ersten Korrelationssumme S(0) wird immer addiert, bei der Berechnung der zweiten Korrelationssumme S(l) im er^¬ sten Ausführungsbeispiel des erfindungsgemäßen Verfahrens wird durch den Addierer/Subtrahierer 6 eine Subtraktion der zwei im Speicher 3 gespeicherten Teilsummen durchgeführt. Das Ergebnis wird von dem Akkumulator 7 an der Anzeige 13 ausgegeben.

2. Ausfü rungsbeispiel der erfindungsgemäßen Empfangssignal- fassungsVorrichtung

Bei dem erfindungsgemäßen Verfahren besteht die Notwendigkeit von Index-Operationen, die zusätzlichen Rechenaufwand verursachen. Der damit verbundene Aufwand läßt sich dadurch minimieren, daß der Befehlssatz eines spezialisierten digitalen Signalprozessors DSP für die Ausführung des erfindungsgemäßen Verfahrens optimiert wird und trotz der notwendigen Indexope- rationen eine Akkumulation pro Befehlszyklus ausgeführt werden kann.

Der in Fig. 3 dargestellte digitale Signalprozessor enthält zwei Akkumulatoren 5, 7, die wahlweise bei allen Akkumula- tionsoperationen verwendet werden können. Wenn die Auswahl des Akkumulators nicht nur im OP-Code des Befehls durchgeführt werden kann, und wenn zusätzlich auch die Betriebsweise Addition und Subtraktion durch Signale aus dem Schieberegister ausgewählt werden kann, dann kann der digitale Signal- prozessor die verallgemeinerte Akkumulation des im ersten Ausführungsbeispiel beschriebenen Verfahrens in einem Betriebszyklus durchführen.

Fig. 4 zeigt ein Ausführungsbeispiel eines derartigen digita- len Signalprozessors zur effektiven Implementierung des erfindungsgemäßen Verfahrens. In dem digitalen Signalprozessor DSP ist zusätzlich ein Schieberegister 21 vorgesehen, dessen Inhalt pro Zyklus um eine Stelle weitergeschoben wird. Alter^¬ nativ können auch zwei Schieberegister verwendet werden. Erstes und zweites Bit des Schieberegisters sind mit dem Eingang eines Exklusiv-Oder-Gatters verbunden und steuern die Akkumulation im Akkumulator 23. Gleichzeitig wird wie bei dem Ausführungsbeispiel von Fig. 3 durch das erste Bit die Addition bzw. Subtraktion in die Arithmetik-Logik-Einheit 27 gesteuert .

Die Erfindung ist jedoch nicht auf binäre vorgegebene diskrete Signalfolgen c(i) beschränkt. Die vorgegebene diskrete Signalfolge kann eine endliche Anzahl unterschiedlicher diskreter Werte annehmen, wobei die Multiplikation zweier Werte der diskreten Signalfolge wieder einen möglichen Wert von c(i) ergibt. Ein Beispiel sind die gleichmäßig auf dem komplexen Einheitskreis angeordneten Werte 1, -1, i., X ' °bei sji = -1 ist. In diesem Fall müssen m^k_1 Teilsummen berechnet werden.

Claims

Patentansprüche

1.Verfahren zur Erfassung eines Empfangssignals durch Korre- lation mit wenigstens einer diskreten vorgegebenen Signalfolge c(i), wobei i eine ganze Zahl < n ist, welche wenigstens eine Signalfolge c(i) eine endliche Anzahl diskreter Werte annehmen kann, aufweisend die Verfahrensschritte:

(a) Ableitung von mehreren Signalfolgen a(i) aus dem Empfangssignal,

(b) Vergleich von Wertepaaren c(i), c(j) der wenigstens einen vorgegebenen diskreten Signalfolge,

(c) Bildung von Teilsummen T der Produkte zweier oder mehrerer Werte einer Empfangssignalfolge a(i) mit einer entsprechenden Anzahl von Werten c_k(i) der vorgegebenen wenigstens einen diskreten Signalfolge,

(d) Ermittlung von Korrelationssummen S mehrerer Signalfolgen a(i) mit der vorgegebenen wenigstens einen diskreten Signalfolge c(i) durch Kombination der in Schritt (c) gebildeten Teilsummen T in Abhängigkeit von dem Vergleichsre- sultat aus Schritt (b) ,

(e) Weiterverarbeitung der in Schritt (d) ermittelten Korrelationssummen S.

2. Verfahren nach Anspruch 1, d a d u r c h g e k e n n z e i c h n e t, daß nur eine Korrelationsfolge c(i) verwendet wird, die in Schritt (d) mit zeitlich zueinander versetzten Signalfolgen a(i) korreliert wird.

3. Verfahren nach Anspruch 1 oder 2, d a d u r c h g e k e n n z e i c h n e t, daß in Schritt (e) die in Schritt (d) ermittelten Korrela^¬ tionssummen S miteinander verglichen werden.

4. Verfahren nach Anspruch 1, 2 oder 3, d a d u r c h g e k e n n z e i c h n e t, daß die vorgegebene diskrete Signalfolge c(i) die Werte +1, -1 annehmen kann, und daß die Korrelationssummen in Schritt (d) durch Addition und/oder Subtraktion der in Schritt (c) gebildeten Teilsummen T ermittelt werden.

5. Verfahren nach Anspruch 1, 2 oder 3, d a d u r c h g e k e n n z e i c h n e t, daß die Werte c(i) der vorgegebenen diskreten Signalfolge eine endliche Menge M mit m Elementen αi, α₂, ..., α_m bilden, für die gilt, daß das Produkt zweier Werte aus M wieder ein Element aus M ist, und daß im Schritt (b) Produkte der Wertepaare c(i), c(j) der vorgegebenen diskreten Signalfolge gebildet werden.

6. Verfahren nach Anspruch 5, d a d u r c h g e k e n n z e i c h n e t, daß die Menge M die Elemente {1, -1, i, -i} enthält, wobei i_ = v-1 ist.

7. Verfahren nach einem der Ansprüche 1 bis 6, d a d u r c h g e k e n n z e i c h n e t, daß in Schritt (b) jeweils zwei aufeinanderfolgende Werte c(i), c(i-l) der vorgegebenen diskreten Signalfolge verglichen werden, und daß in Schritt (c) zwei Teilsummen Tl, T2 ermittelt werden.

8. Verfahren nach Anspruch 7, d a d u r c h g e k e n n z e i c h n e t, daß in Schritt (c) eine erste Teilsumme Tl aller Produkte a(i) ^' c(i) gebildet wird, für die gilt: c(i) = c(i-l), und eine zweite Teilsumme T2 aller Produkte a(i) ' c (i) gebildet wird, für die gilt c(i) = -c(i-l), und in Schritt (d) eine erste Korrelationssumme S(0) als Summe der Teilsummen Tl und T2 oder eine zweite Korrelationssumme S(l) als Differenz der Teilsummen Tl und T2 ermittelt wird.

9. Verfahren nach Anspruch 8, d a d u r c h g e k e n n z e i c h n e t, daß bei der Berechnung der Teilsummen Tl und T2 jeweils zunächst alle Werte a(i) der Empfangssignalfolge aufsummiert werden, die mit einem Wert c(i) = -1 der vorgegebenen dis- kreten Signalfolge zu multiplizieren sind, die so gebildete Summe invertiert wird und dann alle Werte a(i) der Empfangssignalfolge hinzuaddiert werden, die mit Werten c(i) = +1 der vorgegebenen diskreten Signalfolge zu multiplizieren sind.

10. Verfahren nach Anspruch 8 oder 9, d a d u r c h g e k e n n z e i c h n e t, daß die erste Korrelationssumme S (0) =c (0) -a (0) + Tl + T2 und die zweite Korrelationssumme S (1) =c (n) "a (n) + Tl - T2 ist.

11. Verfahren nach einem der Ansprüche 1 bis 7, d a d u r c h g e k e n n z e i c h n e t, daß in Schritt (c) Summen und Differenzen jeweils benach- barter Werte a(i), a(i+l) der Empfangssignalfolge gebildet werden und ein korrespondierender Wert c(i) der vorgegebenen diskreten Folge mit der Wertesumme a (i) +a (i+1) multipliziert, falls c(i) = c(i+l) ist und mit der Wertepaardif- ferenz a(i)-a(i-l) multipliziert, falls c(i) = c(i+l); und in Schritt (d) zwei Korrelationssummen S(0) und S(l) durch Addition der in Schritt (c) erhaltenen Teilsummen ermittelt werden.

12. Verfahren nach einem der Ansprüche 1 bis 10, d a d u r c h g e k e n n z e i c h n e t, daß die Werte der Signalfolgen a(i) komplexe Zahlen anneh- men.

13. Verfahren nach einem der Ansprüche 1 bis 12, d a d u r c h g e k e n n z e i c h n e t, daß die in Schritt (b) enthaltenen Vergleichsresultate als Tabelle abgespeichert werden.

14. Verfahren nach einem der Ansprüche 1 bis 13, d a d u r c h g e k e n n z e i c h n e t, daß zur Berechnung der verkürzten Korrelation von k aufeinanderfolgenden Zeiten nicht der gleiche Anteil der gespeicherten Signalfolge verwendet wird, sondern stattdessen der gleiche Anteil des Signals verwendet wird.

15. Vorrichtung zur Erfassung eines Empfangssignals durch Korrelation mit einer vorgegebenen diskreten Signalfolge c(i), wobei i eine ganze Zahl < n ist, welche diskrete Signalfolge eine endliche Anzahl diskreter Werte annehmen kann, aufweisend:

eine Einrichtung zum Empfang des Empfangssignals,

eine Einrichtung zur Ableitung mehrerer zeitlich zueinander versetzter Signalfolgen a(i) aus dem Empfangssignal,

eine Einrichtung zur Speicherung der Werte c(i) der vorgegebenen diskreten Signalfolge,

eine Einrichtung zum Vergleich von Wertepaaren c(i), c(j) der gespeicherten vorgegebenen diskreten Signalfolge,

eine Einrichtung zur Bildung von Teilsummen der Produkte zweier oder mehrerer Werte a(i) der Empfangssignalfolge mit einer entsprechenden Anzahl von Werten c(i) der vorgegebe- nen diskreten Signalfolge,

eine Einrichtung zur Ermittlung von Korrelationssummen S mehrerer zeitlich zueinander versetzter Signalfolgen a(i) mit der vorgegebenen diskreten Signalfolge c(i) durch Kom^¬ bination der gebildeten Teilsummen T in Abhängigkeit von den durch die Vergleichseinrichtung gelieferten Vergleichs- resultaten,

eine Einrichtung zum Vergleich der ermittelten Korrelationssummen.

16. Vorrichtung nach Anspruch 15, d a d u r c h g e k e n n z e i c h n e t, daß die Einrichtung zur Bildung der Teilsummen wenigstens eine Akkumulatoreinrichtung zur gleichzeitigen Speicherung von zwei Teilsummen aufweist.

17. Vorrichtung nach einem der Ansprüche 15 bis 16, d a d u r c h g e k e n n z e i c h n e t, daß die Einrichtung zur Bildung der Teilsummen wenigstens eine Auswahleinrichtung zur Auswahl von einem aus wenig- stens zwei Akkumulatoreinrichtung in Abhängigkeit von einer vorgegebenen diskreten Signalfolge aufweist.

18. Vorrichtung nach einem der Ansprüche 15 bis 17, d a d u r c h g e k e n n z e i c h n e t, daß eine Einrichtung zur Ermittlung von Korrelationssummen aus bereits berechneten Teilsummen vorgesehen ist, wobei die Teilsummen in Abhängigkeit von einer vorgegebenen diskreten Signalfolge weiterverarbeitet werden.

19. Vorrichtung nach einem der Ansprüche 15 bis 18, d a d u r c h g e k e n n z e i c h n e t, daß zur Berechnung der verkürzten Korrelation von k aufeinanderfolgenden Zeiten nicht der gleiche Anteil der gespeicherten Signalfolge verwendet wird, sondern stattdessen der gleiche Anteil des Signals verwendet wird.