DE20217637U1

DE20217637U1 - Basisstation, die eine Arrayverarbeitung zur Datendetektion verwendet

Info

Publication number: DE20217637U1
Application number: DE20217637U
Authority: DE
Original assignee: InterDigital Technology Corp
Current assignee: InterDigital Technology Corp
Priority date: 2001-11-14
Filing date: 2002-11-14
Publication date: 2003-03-20
Anticipated expiration: 2012-11-15
Also published as: KR20040053297A; JP2008077682A; TWI268667B; KR20050090349A; CN2579091Y; NO20042407L; KR20040016941A; DE20217636U1; TWI263417B; TW200742284A; KR20070116287A; TWI325240B; KR20050090084A; CN2686248Y; JP2012150827A; MXPA04004486A; US20070206543A1; US7218624B2; TW200415862A; CN1582544A

Description

I81376GM

BASISSTATION, DIE EINE ARRAYVERARBEITUNG ZUR DATENDETEKTION

VERWENDET

HINTERGRUND

Diese Erfindung betrifft die Lösung linearer Systeme im Allgemeinen. Im Besonderen betrifft die Erfindung die Verwendung einer Arrayverarbeitung zur Lösung linearer Systeme.

Lösungen linearer Systeme werden zur Lösung vieler technischer Probleme eingesetzt. Ein solches Problem ist die Mehrteilnehmerdetektion von mehreren Benutzersignalen in einem Zeitduplex (TDD, time division duplex)-Kommunikationssystem, das Codemultiplex (CDMA, code division multiple access) verwendet. In einem solchen System senden mehrere Benutzer mehrere Kommunikationsbursts gleichzeitig in einem gleichen festgelegten Zeitdauerintervall (Zeitschlitz). Die mehrfachen Bursts werden unter Verwendung verschiedener Spreizcodes übertragen. Während der Übertragung erfährt jeder Burst eine Kanalantwort. Ein Ansatz zur Wiedergewinnung von Daten aus den übertragenen Bursts ist die Mehrteilnehmerdetektion, worin die Daten aller Benutzer gleichzeitig empfangen werden. Ein solches System ist in Figur 1 gezeigt. Der Empfanger mit Mehrteilnehmerdetektion kann in einer Benutzervorrichtung oder Basisstation verwendet werden.

Die mehrfachen Bursts 90 werden, nachdem sie ihre Kanalantwort erfahren haben, als ein kombiniertes empfangenes Signal an einer Antenne 92 oder einem Antennenarray empfangen. Das empfangene Signal wird auf das Basisband reduziert, wie zum Beispiel durch einen Demodulator 94, und bei einer Chiprate der Codes oder einem Vielfachen einer Chiprate der Codes, wie zum Beispiel durch einen Analog-Digital-Konverter (ADC) 96 oder mehrere ADCs abgetastet, um einen empfangenen Vektor, r, zu erzeugen. Eine Kanalabschätzungsvorrichtung 98 verwendet einen Trainings-Sequenzabschnitt der Kommunikationsbursts, um die Kanalantwort der Bursts 90 abzuschätzen. Eine Mehrteilnehmerdetektions-Vorrichtung 100 verwendet die geschätzten oder bekannten Spreizcodes der Bursts der Benutzer und die geschätzten

oder bekannten Kanalantworten, um die ursprünglich übertragenen Daten für alle Benutzer als einen Datenvektor, d, abzuschätzen.

Das Problem der Mehrteilnehmerdetektion wird typischerweise durch Gleichung 1 abgebildet.

Ad+ n = r Gleichung 1

d ist der übertragene Datenvektor; r ist der empfangene Vektor; &eegr; ist das additive weiße Gaußsche Rauschen (AWGN); und A ist eine M &khgr; N-Matrix, die durch Faltung der Kanalantworten mit den bekannten Spreizcodes konstruiert wird.

Zwei Ansätze zur Lösung der Gleichung 1 sind ein Ansatz der Nullstellenerzwingung (zero forcing, ZF) und ein Ansatz zur Minimierung des mittleren Fehlerquadrates (minimum mean square error, MMSE). Eine ZF (zero forcing, Nullstellenerzwingung)-Lösung, bei der &eegr; an Null angenähert wird, existiert nach Gleichung 2:

d= (A^H A)-¹A" r Gleichung 2

Ein MMSE-Ansatz existiert nach Gleichungen 3 und 4:

d = R-^!A^Hr Gleichung 3

R = A^HA + &sgr; ²I Gleichung 4

&sgr; ² ist die Rauschvarianz, n, und I ist die Einheitsmatrix.

Da die Spreizcodes, die Kanalantworten und der Mittelwert der Rauschvarianz geschätzt werden oder bekannt sind und der empfangene Vektor bekannt ist, ist der Datenvektor d die einzige unbekannte Variable. Eine Lösung nach Art sturer Berechnung, wie etwa eine direkte Matrixinvertierung, ist für jeden der beiden Ansätze extrem komplex. Eine Technik, um die Komplexität zu reduzieren, ist die Cholesky-Zerlegung. Der Cholesky-

Algorithmus zerlegt eine symmetrisch positiv definite Matrix, wie etwa Ä oder R₅ in

TT

eine untere Dreiecksmatrix G und eine obere Dreiecksmatrix G nach Gleichung 5:

Ä oder R=G G^H Gleichung 5

Eine symmetrisch positiv definite Matrix, Ä, kann durch Multiplikation von A mit ihrer konjugiert Transponierten (hermiteschen), A^H, nach Gleichung 6 aus A erzeugt werden:

Ä = A^H A Gleichung 6

Abgekürzt wird r nach Gleichung 7 definiert:

r=A^H r Gleichung 7

Aufgrund dessen wird die Gleichung 1 für ZF als Gleichung 8 oder Gleichung 9 für MMSE umformuliert:

Ä d = r Gleichung 8

Rd=? Gleichung 9

Um entweder Gleichung 8 oder 9 zu lösen, wird der Cholesky-Faktor nach Gleichung verwendet:

GG^Hd = r Gleichung

Eine Variable y wird wie nach Gleichung 11 definiert.

G d=y Gleichung 11

Unter Verwendung der Variablen y wird Gleichung 10 als Gleichung 12 umformuliert:

Gy = r Gleichung

Die Masse der Komplexität für das Erhalten des Datenvektors wird in drei Schritten durchgeführt. In dem ersten Schritt wird G aus der abgeleiteten symmetrisch positiv defmiten Matrix, wie etwa Ä oder R, geschaffen, wie durch Gleichung 13 illustriert:
5

G = CHOLESKY (A oder R) Gleichung 13

Unter Verwendung von G wird y unter Verwendung des Vorwärtseinsetzens von G in Gleichung 8 gelöst, wie durch Gleichung 14 illustriert:
10

y = FOR WARD SUB(G, r) Gleichung 14

Unter Verwendung der konjugierten Transponierten von G, G^H, wird d unter Verwendung des Rückwärtseinsetzens in Gleichung 11 gelöst, wie durch Gleichung 15 illustriert:

d = BACKWARD SUB(G^H,y) Gleichung 15

Ein Ansatz, um den Cholesky-Faktor, G, nach Gleichung 13 zu bestimmen, ist der folgende Algorithmus, wie er für Ä oder R gezeigt wird, obwohl ein analoger Ansatz auch für R verwendet wird:

for i = 1 : N

for j = max(l, i - P): i - 1
&lgr; = min(j + P, N)

^:&lgr;,i⁼a_i:x_;i-a ij · a_i:^j;
end for;

&lgr; = min(i + P, N)
ai: &lgr;, i = aj; _&lgr;> i / au;
end for

G = A oder R;

ad_;e bezeichnet das Element in der Matrix Ä oder R in Reihe d, Spalte e. ":" bezeichnet einen "nach"-Operator, wie etwa "von j nach N", und (·) bezeichnet einen konjugiert transponierten (hermiteschen) Operator.

Ein weiterer Ansatz zur Lösung für den Cholesky-Faktor verwendet N parallele vektorbasierte Prozessoren. Jeder Prozessor ist einer Spalte der Ä- oder R-Matrix zugeordnet. Die Spalte eines jeden Prozessors wird durch eine Variable &mgr; definiert, wobei &mgr; =1:N gilt. Das parallelprozessorbasierte Unterprogramm kann als das folgende Unterprogramm für &mgr; =1 :N betrachtet werden:
10

7=1

while j < &mgr;

recv(g_;./v, left)
&igr;&idiagr;&mgr;<&Ngr;

send(gy.w, right)

end

&bgr;&mgr;:&Ngr;,&mgr; ⁼ Cl&mgr;:N,&mgr; " g &mgr;&&mgr;:&Ngr;

end

^&agr;&mgr;:&Ngr;,&mgr; ^{= &agr;}&mgr;:&Ngr;,&mgr; ' ^ ^&uacgr; &mgr;&mgr;

end

TQCv(-,left) ist ein Empfangswert vom Operator des linken Prozessors; send(-,right) ist ein Sendewert an den Operator des rechten Prozessors, und ga,L ist ein Wert von einem benachbarten Prozessor.

Dieses Unterprogramm ist unter Verwendung der Figuren 2a - 2h illustriert. Figur 2a ist ein Blockschaltbild der Vektor-Prozessoren und der zugehörigen Speicherzellen der Vorrichtung zur Mehrteilnehmerdetektion. Jeder Prozessor 50] bis 50n (50) arbeitet auf

einer Spalte der Matrix. Da die G-Matrix die untere Dreieckmatrix ist und Ä oder R durch ihren unteren Dreiecksabschnitt vollständig definiert ist, werden nur die Elemente des unteren Dreiecks &agr;^,&khgr; verwendet.

Die Figuren 2b und 2c zeigen zwei mögliche Funktionen, die von den Prozessoren auf den Zellen unter ihnen durchgeführt werden. In Figur 2b führt die mit der Spitze nach unten weisende Dreiecksfunktion 52 die Gleichungen 16 und 17 auf den Zellen ^_&mgr;&mgr; bis a^) unter diesem &mgr;-Prozessor 50 durch.

Gleichung 16

&agr;_&mgr;:&Ngr;,&mgr;^{:=: v} Gleichung 17

"<—" bezeichnet eine gleichzeitige Zuweisung; ":=" bezeichnet eine sequentielle Zuweisung; und &ngr; ist ein Wert, der an den rechten Prozessor gesendet wird.
15

In Figur 2c führt die mit der Spitze nach rechts weisende Dreiecksfunktion 52 die Gleichungen 18 und 19 auf den Zellen unter diesem &mgr;-Prozessor 50 durch:

&ngr; <- u Gleichung 18

&agr;_&mgr;;&Ngr;,&mgr;-= &agr;_&mgr;:&Ngr; ,_&mgr; - &ngr;_&mgr; &ngr;_&mgr;:&Ngr; Gleichung 19

Vk bezeichnet einen Wert, der zu einem rechten Wert des k-ten Prozessors 50 gehört.

Die Figuren 2d - 2g illustrieren den Datenfluss und die durchgeführten Funktionen für eine 4x4 G-Matrix. Wie in den Figuren 2d - 2g für jede Stufe 1 bis 4 der Verarbeitung gezeigt, fällt der am weitesten links gelegene Prozessor 50 aus und die mit der Spitze nach unten weisende Dreiecksfunktion 52 bewegt sich von links nach rechts. Um die Figuren 2d - 2g zu implementieren, kann das mit der Spitze nach unten weisende Dreieck den Prozessor auf der rechten Seite physikalisch ersetzen oder den Prozessor

auf der rechten Seite virtuell ersetzen, indem es die Funktion des mit der Spitze nach unten weisenden Dreiecks übernimmt.

Diese Elemente können auf eine N &khgr; N-Matrix und N Prozessoren 50 erweitert werden, indem Prozessoren 50 (N - 4 an der Zahl) auf der rechten Seite des vierten Prozessors 5&Ogr;4 hinzugefügt werden, und indem Zellen der unteren Matrixdiagonale (N - 4 an der Zahl) zu jedem der Prozessoren 50, wie in Figur 2h für Stufe 1 gezeigt, hinzugefügt werden. Die Verarbeitung in einer solchen Anordnung erfolgt über N Stufen.

Die Implementierung einer solchen Cholesky-Zerlegung unter Verwendung von entweder Vektor-Prozessoren oder einer direkten Zerlegung in skalare Prozessoren ist ineffizient, da große Mengen der Verarbeitungressourcen nach jeder Stufe der Verarbeitung in den Ruhezustand gehen.

Dementsprechend ist es wünschenswert, alternative Ansätze zur Lösung linearer Systeme zu besitzen.

ZUSAMMENFASSUNG

Eine Basisstation gewinnt Daten aus einer Vielzahl von empfangenen Datensignalen zurück, die als ein empfangener Vektor empfangen wurden. In einer Ausführungsform werden die Daten des empfangenen Vektors unter Verwendung eines Cholesky-Faktors einer N &khgr; N-Matrix bestimmt. Die Basisstation umfasst ein Array von Verarbeitungselementen. Jedes Verarbeitungselement des Arrays empfängt Elemente einer Diagonale der N &khgr; N-Matrix und bestimmt Elemente einer entsprechenden Diagonale des Cholesky-Faktors. In einer weiteren Ausführungsform werden die Daten des empfangenen Vektors unter Verwendung eines Cholesky-Faktors einer NxN-Matrix und durch Vorwärts- und Rückwärtseinsetzen bestimmt. Die Basisstation umfasst ein Array von höchstens N skalaren Verarbeitungselementen. Das Array hat einen Eingang zum Empfangen von Elementen aus der N &khgr; N-Matrix und dem empfangenen Vektor. Jedes skalare Verarbeitungselement wird bei der Bestimmung des Cholesky-Faktors und der Durchführung des Vorwärts- und Rückwärtseinsetzens verwendet. Das Array gibt Daten des empfangenen Vektors aus. In einer weiteren

Ausführungsform werden die Daten des empfangenen Vektors unter Verwendung eines Cholesky-Faktors einer N &khgr; N-Matrix bestimmt. Die Basisstation umfasst ein Array von skalaren Verarbeitungselementen. Jedes Verarbeitungselement gehört zu einem Element der N &khgr; N-Matrix und bestimmt Elemente eines entsprechenden Elementes des Cholesky-Faktors.

KURZE BESCHREIBUNG DER ZEICHNUNG(En)

Figur 1 ist ein Prinzipbild eines Empfängers mit Mehrteilnehmerdetektion.
10

Figuren 2a - 2h sind Diagramme, welche die Bestimmung eines Cholesky-Faktors unter Verwendung von Vektor-Prozessoren illustrieren.

Figuren 3 a und 3b sind bevorzugte Ausführungsformen von N skalaren Prozessoren, welche die Cholesky-Zerlegung durchführen.

Figuren 4a - 4e sind Diagramme, die ein Beispiel für die Verwendung eines dreidimensionalen Graphen für die Cholesky-Zerlegung illustrieren.

Figuren 5a - 5e sind Diagramme, die ein Beispiel für die Abbildung von Vektor-Prozessoren, welche die Cholesky-Zerlegung durchführen, auf skalare Prozessoren illustrieren.

Figuren 6a - 6d für eine Nichtband- und Figuren 6e - 6j für eine Bandmatrix sind Diagramme, die den Verarbeitungsfluss des skalaren Arrays illustrieren.

Figur 7 ist ein Diagramm, welches eine Projektion von Figur 4a entlang der Achse k auf eine N &khgr; N-Matrix erweitert.

Figuren 8a - 8d sind Diagramme, welche den Verarbeitungsfluss unter Verwendung von Verzögerungselementen zwischen den skalaren Prozessoren in dem 2D skalaren Array illustrieren.

• t ff * 9 * ff 9 ff fft ff f ff ff ff · «ff

• t »·· · * ff * &phgr; · *·· ff ff ff ff f

• 9 ff · ff ff ■ t · ·· ff« ff * ff

• · ff ···« ff* ····* *9ff ··· ···· ···· ff ff ···* ffffff ff «ff «ff ff «ff · «·

9 »&idigr;« &Igr;

Figur 8e ist ein Diagramm eines Verzögerungselementes und seiner zugehörigen Gleichung.

Figur 9a illustriert die Projektion des Arrays skalarer Prozessoren der Figuren 8a - 8d auf ein ID-Array von vier skalaren Prozessoren.

Figur 9b illustriert die Projektion eines skalaren Verarbeitungsarrays mit Verzögerungselementen zwischen jedem zweiten Prozessor auf ein ID-Array von vier skalaren Prozessoren.
10

Figuren 9c - 9n sind Diagramme, welche den Verarbeitungsfluss für die Cholesky-Zerlegung einer Bandmatrix mit Verzögerungselementen zwischen jedem zweiten Prozessor illustrieren.

Figuren 9o - 9z illustrieren den Speicherzugriff fur eine lineare Arrayverarbeitung einer Bandmatrix.

Figuren 10a und 10b sind die projizierten Arrays der Figuren 9a und 9b, erweitert auf N skalare Prozessoren.
20

Figuren 11a und 11b illustrieren eine Trennung einer Divisions- / Quadratwurzel-Funktion von den Arrays aus den Figuren 10a und 10b.

Figur 12a ist eine Illustration der Projektion eines Vorwärtseinsetzungs-Arrays mit Verzögerungselementen zwischen jedem Prozessor auf vier skalare Prozessoren.

Figur 12b ist eine Illustration der Projektion eines Vorwärtseinsetzungs-Arrays mit Verzögerungselementen zwischen jedem zweiten Prozessor auf vier skalare Prozessoren.
30

Figuren 12c und 12d sind Diagramme, welche die Gleichungen zeigen, die für das Vorwärtseinsetzen von einer Stern- und Rautefunktion durchgeführt werden.

• ft ·*·· 94 ·· »ff ff··

Figur 12e ist ein Diagramm, welches den Verarbeitungsfluss für ein Vorwärtseinsetzen einer Bandmatrix mit gleichzeitigen Zuweisungen zwischen jedem zweiten Prozessor illustriert.

Figuren 12f - 12j sind Diagramme, welche den Verarbeitungsfluss für das Vorwärtseinsetzen einer Bandmatrix mit Verzögerungselementen zwischen jedem zweiten Prozessor illustrieren.

Figuren 12k - 12p sind Diagramme, welche den Speicherzugriff für eine lineare Arrayverarbeitung einer Bandmatrix durch Vorwärtseinsetzen illustrieren.

Figuren 13a und 13b sind die projizierten Arrays der Figuren 12a und 12b, erweitert auf N skalare Prozessoren.

Figuren 14a- 14d sind Diagramme, welche den Verarbeitungsfluss des projizierten Arrays von Figur 12b illustrieren.

Figur 15a ist eine Illustration der Projektion eines Rückwärtseinsetzungs-Arrays mit Verzögerungselementen zwischen jedem Prozessor auf vier skalare Prozessoren.
20

Figur 15b ist eine Illustration der Projektion eines Rückwärtseinsetzungs-Arrays mit Verzögerungselementen zwischen jedem zweiten Prozessor auf vier skalare Prozessoren.

Figur 15c und 15d sind Diagramme, welche die Gleichungen zeigen, die für das Rückwärtseinsetzen von einer Stern- und Rautefunktion durchgeführt werden.

Figur 15e ist ein Diagramm, welches den Verarbeitungsfluss für ein Rückwärtseinsetzen einer Bandmatrix mit gleichzeitigen Zuweisungen zwischen jedem zweiten Prozessor illustriert.

• 9 999 «99 « 9 · 999 « 9 99·

999 9999 99 99 99 999

999 9*99 99 99999 ·99

999 99*9 9999 99 9999 999 * 99 99 9 99 · ··

Figuren 15f - 15j sind Diagramme, welche den Verarbeitungsfluss für das Rückwärtseinsetzen einer Bandmatrix mit Verzögerungselementen zwischen jedem zweiten Prozessor illustrieren.

Figuren 15k - 15p sind Diagramme, welche den Speicherzugriff für eine lineare Arrayverarbeitung einer Bandmatrix durch Rückwärtseinsetzen illustrieren.

Figuren 16a und 16b sind die projizierten Arrays der Figuren 15a und 15b, erweitert auf N skalare Prozessoren.
10

Figuren 17a - 17d sind Diagramme, welche den Verarbeitungsfluss des projizierten Arrays von Figur 15b illustrieren.

Figuren 18a und 18b sind die Arrays der Figuren 13a, 13b, 16a und 16b, wobei die Divisionsfunktion getrennt ist.

Figuren 19a und 19b sind Diagramme eines rekonfigurierbaren Arrays zur Bestimmung von G, und für das Vorwärts- und Rückwärtseinsetzen.

Figuren 20a und 20b sind Illustrationen für das Heraustrennen der Divisions- und Quadratwurzel-Funktion aus dem rekonfigurierbaren Array.

Figur 21a illustriert eine bidirektionale Faltung.
Figur 21b illustriert eine unidirektionale Faltung.

Figur 22a ist eine Implementierung der bidirektionalen Faltung unter Verwendung von N Prozessoren.

Figur 22b ist eine Implementierung der unidirektionalen Faltung unter Verwendung von N Prozessoren.

9 ···· ·· 9909 ···· &phgr; &psgr;

9 · · 9 9 9 9

* · 999 Q · 9 9

9 0 · · t« 9 9

99 99999 9« 999 99 90 9 99

&iacgr; &diams;*&diams;»*! * *

Figur 23 ist eine bevorzugte Schicht eines einfachen rekonfigurierbaren Verarbeitungselements.

DETAILLIERTE BESCHREIBUNG DER BEVORZUGTEN
AUSFÜHRUNGSFORMEN

Die Figuren 3a und 3b sind bevorzugte Ausführungsformen der N skalaren Prozessoren 541 bis 54n (54), welche die Cholesky-Zerlegung durchführen, um G zu erhalten. Aus Gründen der Einfachheit werden die Erklärung und die Beschreibung für eine 4 &khgr; 4 G-Matrix gegeben, obwohl dieser Ansatz auf eine beliebige NxN G-Matrix erweitert werden kann, wie in den Figuren 3 a und 3b gezeigt.

Figur 4a illustriert einen dreidimensionalen Rechen-Abhängigkeitsgraphen für die Durchführung der vorstehenden Algorithmen. Aus Gründen der Einfachheit illustriert Figur 4a die Verarbeitung einer 5 &khgr; 5-Matrix mit einer Bandbreite von 3. Die Funktionen, die von jedem Knoten ausgeführt werden, sind in den Figuren 4b - 4e gezeigt. Die Fünfeckfunktion von Figur 4b führt die Gleichungen 20 und 21 aus:

Gleichung 20
20

^aou, <- y

Gleichung 21

<— bezeichnen eine gleichzeitige Zuweisung. a_in ist ein Eingang in den Knoten von einer unteren Ebene und a_out ist ein Ausgang zu einer höheren Ebene. Figur 4c ist eine Quadratfunktion, welche die Gleichungen 22 und 23 ausführt:

y <-z* Gleichung

22

^aout

2 Z

Gleichung 23
30

••••••I« · ·

• &diams; t t f · Ml

Figur 4d ist eine Achteckfunktion, welche die Gleichungen 24, 25 und 26 ausführt: y <- w Gleichung 24

&khgr; <-aJw Gleichung 25

a_out <-&khgr; Gleichung 26

Figur 4e ist eine Kreisfunktion, welche die Gleichungen 27, 28 und 29 ausführt: 10

y <-w Gleichung 27

x<-z Gleichung 28

a_out <-ain -w*z Gleichung 29

Figur 5a ist ein Diagramm, welches die Abbildung der ersten Stufe einer vektorbasierten Cholesky-Zerlegung für eine 4x4 G-Matrix auf die erste Stufe eines zweidimensionalen Ansatzes auf skalarer Basis zeigt. Jeder Vektor-Prozessor 52, 54 wird auf zumindest einen skalaren Prozessor 56, 58, 60, 62 abgebildet, wie in Figur 5a gezeigt,. Zu jedem skalaren Prozessor 56, 58, 60, 62 gehört eine Speicherzelle ay. Die Funktion, die von jedem Prozessor 56, 58, 60, 62 auszuführen ist, wird in den Figuren 5b - 5e gezeigt. Figur 5b illustriert eine Fünfeckfunktion 56, welche die Gleichungen 30 und 31 ausführt:

Gleichung 30 ay■: = y Gleichung 31

: = bezeichnet eine aufeinanderfolgende Zuweisung, y bezeichnet einen Wert, der an einen unteren Prozessor gesendet wird. Figur 5c illustriert eine Achteckfunktion 58, welche die Gleichungen 32, 33 und 34 ausführt:

y<-w Gleichung 32

&khgr; <^- &Lgr;,/w Gleichung 3 3 5

üif = &khgr; Gleichung 34

w bezeichnet einen Wert, der von einem oberen Prozessor gesendet wird. Figur 5d illustriert eine Quadratfunktion 60, welche die Gleichungen 35 und 36 ausfuhrt: 10

y <— &zgr; * Gleichung 3 5

Gleichung 36 15

&khgr; bezeichnet einen Wert, der an einen rechten Prozessor gesendet wird. Figur 5e illustriert eine Kreisfunktion 62, welche die Gleichungen 37, 38 und 39 ausfuhrt:

y <—w Gleichung 37

&khgr; <—z Gleichung 38

ay : = ay -w*z Gleichung 3 9

Die Figuren 6a - 6d illustrieren den Datenfluss durch die skalaren Prozessoren 56, 58, 60, 62 in vier aufeinander folgenden Stufen (Stufen 1 bis 4). Wie in den Figuren 6a - 6d gezeigt, fallt nach jeder Stufe eine Spalte von Prozessoren 56, 58 weg. Das Verfahren erfordert vier Verarbeitungszyklen oder N im Allgemeinen. Ein Verarbeitungszyklus für jede Stufe. Wie in Figur 5a gezeigt, sind zehn (10) skalare Prozessoren erforderlich, um eine 4x4 G-Matrix zu bestimmen. Für eine N &khgr; N-Matrix lautet die Anzahl der erforderlichen Prozessoren wie in Gleichung 40:

&Igr;*

Anzahl d. erforderl. skalaren Prozessoren =

N (N + 1) N ² + N

/Li

Gleichung 40

Figuren 6e - 6j illustrieren den Verarbeitungsfluss für eine 5 &khgr; 5-Bandmatrix. Aktive Prozessoren sind in durchgezogenen Linien dargestellt. Die Bandmatrix weist die unteren linken drei Einträge (a^, asu &n> in den Figuren 6e - 6j nicht dargestellt) als Nullen auf. Wie in Figur 6e gezeigt, sind in einer ersten Stufe die oberen sechs Prozessoren in Betrieb. Wie in Figur 6f gezeigt, haben die sechs aktiven Prozessoren der Stufe 1 gii, g2i und g3i und drei Zwischenresultate OC22, 0:32 und 0:33 zur Verwendung in Stufe 2 bestimmt.

In Stufe 2 sind sechs Prozessoren (0122, 032, 0:33, /42, ^43,^44) in Betrieb. Wie in Figur 6g (Stufe 3) gezeigt, wurden Werte für g22, g32 und g42 und Zwischenwerte für y?33, ^43, ^44 in Stufe 2 bestimmt. In Figur 6h (Stufe 4) wurden Werte für g₃₃, g₄₃ und g₅3 und Zwischenwerte für 744, /54 und 755 bestimmt. In Figur 6 (Stufe 5) wurden g44 und g54 und der Zwischenwert S₅s bestimmt. In Figur 6j (letzte Stufe) ist der verbleibende Wert g55 verfügbar. Wie in den Figuren gezeigt, sind auf Grund der Bandnatur der Matrix die unteren linken Prozessoren einer unbesetzten Matrix überflüssig und daher nicht dargestellt.

Die vereinfachten Illustrationen der Figuren 6a - 6d können zu einer N &khgr; N-Matrix wie in Figur 7 gezeigt erweitert werden. Wie in dieser Figur gezeigt, führt der oberste Prozessor 56 eine Fünfeckfunktion aus. Achteckfunktionsprozessoren 58 erstrecken sich die erste Spalte hinunter und Doppelzweck-Quadrat- / Fünfeck-Prozessoren 64 entlang der Hauptdiagonale, wie durch die zwei kombinierten Formen dargestellt. Die restlichen der Prozessoren 66 sind Doppelzweck-Achteck- / Kreis-Prozessoren 66, wie durch die zwei kombinierten Formen dargestellt. Diese Konfiguration bestimmt eine NxNG-Matrix in N Verarbeitungszyklen unter Verwendung von ausschließlich skalaren Prozessoren.

Wenn die Bandbreite der Matrix eine begrenzte Größe hat, wie etwa P, kann die Anzahl der Verarbeitungselemente reduziert werden. Wenn P zum Beispiel gleich N-I ist, fällt der linke untere Prozessor für a^ &igr; weg. Wenn P gleich N - 2 ist, fallen zwei weitere Prozessoren (aN-i &igr; und a_N2) weg.

Die Reduktion der Anzahl von skalaren Verarbeitungselementen wird des Weiteren anhand der Figuren 8a - 8e und 9a und 9b erklärt. Die Figuren 8a - 8e beschreiben eindimensionale Ausführungsebenen einer Implementierung mit vier (4) skalaren Prozessoren gemäß Figuren 6a - 6d. Ein Verzögerungselement 68 von Figur 8e ist zwischen jede gleichzeitige Verbindung eingefügt, wie in Figur 8a gezeigt. Das Verzögerungselement 68 von Figur 8e verzögert den Eingang y so, dass er ein sequenzieller Ausgang &khgr; wird, gemäß Gleichung 41:

y:=x Gleichung 41

Für jeden bei t] beginnenden Verarbeitungszyklus arbeiten die Prozessoren aufeinander folgend wie durch die Diagonalen, welche die Ausführungsebenen zeigen, dargestellt. Zum Beispiel arbeitet zum Zeitpunkt tj nur der Prozessor 56 von a\\. Bei t2 arbeitet nur der Prozessor 58 von ai\, und bei &Idigr;3 arbeiten die Prozessoren 58, 60 von &OHgr;31 und «22 und so weiter bis Stufe 4, ti6, wo nur der Prozessor 56 von a₄₄ arbeitet. Daher benötigt die gesamte Verarbeitung N² Taktzyklen über N Stufen.

Mehrere Matrizen können nacheinander durch das zweidimensionale skalare Verarbeitungsarray verarbeitet werden. Wie in den Figuren 8a - 8d gezeigt, sind auf einer bestimmten Ausführungsebene ti bis ti6 aktiv. Für eine gegebene Stufe kann bis zu einer Anzahl von Matrizen, die der Anzahl von Ausführungsebenen entspricht, zur selben Zeit verarbeitet werden. Zum Beispiel wird bei Stufe 1 eine erste Matrix entlang der Diagonale ti verarbeitet. Bei einem nächsten Taktzyklus geht die erste Matrix auf Ebene t2 über und Ebene ti wird für eine zweite Matrix verwendet. Die Pipeline-Verarbeitung kann für eine beliebige Anzahl von Matrizen weitergehen. Ein Nachteil der Pipeline- Verarbeitung ist, dass die Pipeline-Verarbeitung es notwendig macht, alle Daten für alle Matrizen zu speichern, es sei denn, der zeitliche Ablauf der Verfügbarkeit der Matrixdaten ist derart, dass er nicht stehen bleibt.

» t ttt »·

Nachdem eine Grappe von Matrizen sequenziell durch Stufe 1 abgearbeitet wurde, wird die Gruppe nach einander durch Stufe 2 geleitet und so weiter bis Stufe N. Unter Verwendung der Pipeline-Verarbeitung kann der Durchsatz des Arrays sowie die Prozessorauslastung drastisch erhöht werden.

Da die Prozessoren 56, 58, 60, 62 nicht alle während jedes Taktzyklus verwendet werden, wenn nur 1 Matrix verarbeitet wird, kann die Anzahl von Verarbeitungselementen 56, 58, 60, 62 reduziert werden, indem sie über die Ausfuhrungsebenen hinweg gemeinsam genutzt werden. Figuren 9a und 9b illustrieren zwei bevorzugte Implementierungen zur Verringerung der Verarbeitungselemente. Wie in Figur 9a dargestellt, wird eine zu den Ausführungsebenen (den Diagonalen der Matrix entlang) senkrechte Linie für jedes Verarbeitungselement 56, 58 der ersten Spalte gezeigt. Da alle der Prozessoren 56, 58, 60, 62 entlang jeder Senkrechten in verschiedenen Verarbeitungszyklen in Betrieb sind, können ihre Funktionen 56, 58, 60, 62 durch einen einzelnen Prozessor 66, 64, wie unten projiziert, ausgeführt werden. Die Verarbeitungsfunktionen 56 und 60 werden von einer neuen kombinierten Funktion 64 durchgeführt. Die Verarbeitungsfunktionen 58 und 62 werden von einer neuen kombinierten Funktion 66 durchgeführt. Die Verzögerungselemente 68 und Verbindungen zwischen den Prozessoren werden ebenfalls projiziert. Obwohl das am weitesten links stehende Verarbeitungselement unter Verwendung eines Doppelfunktionselementes 66 dargestellt ist, kann dieses Element vereinfacht werden, um nur die Achteckfunktion 58 durchzuführen, wenn dies bei einer Nichtband-Matrix zweckmäßig ist.

Figur 1 Oa ist eine Erweiterung von Figur 9a, um eine NxN G-Matrix unterzubringen. Wie in Figur 10a gezeigt, werden N Prozessoren 66, 64 verwendet, um die N &khgr; &Ngr; G-Matrix zu verarbeiten. Wie in Figur 3 a gezeigt, können die Verarbeitungsfunktionen von Figur 10a durch N skalare Prozessoren 54 durchgeführt werden. Dieselbe Anzahl von skalaren Prozessoren wie die Bandbreite P kann verwendet werden, um die G-Matrix im Fall einer Bandmatrix zu verarbeiten.

• t · t » V ft i · «

*· &diams; i I · * · t

In der Implementierung von Figur 3a wird jeder Prozessor in jedem zweiten Taktzyklus verwendet. Die geraden Prozessoren arbeiten in einem Zyklus und die ungeraden in dem nächsten. Zur Illustration verarbeitet Prozessor 2 (der zweite von rechts) von Figur 9a zu den Zeitpunkten tj, U und te und Prozessor 3 bei &Idigr;3 und &Idigr;5. Deshalb können zwei G-Matrizen durch das Verarbeitungsarray zur selben Zeit bestimmt werden, indem sie als Eingänge in das Array verschachtelt werden. Dieser Ansatz steigert die Prozessorauslastung im Vergleich zu der Implementierung von Figur 7 beträchtlich.

Um die Verarbeitungszeit eines einzelnen Arrays zu reduzieren, wird die Implementierung von Figur 9b verwendet. Die Verzögerungselemente zwischen jeder zweiten Prozessorverbindung wurden, wie in Figur 9b gezeigt, entfernt. Zum Zeitpunkt ti ist nur der Prozessor 56 von a\\ in Betrieb. Jedoch sind bei tj die Prozessoren 58, 60 bei &OHgr;21, #22 und 031 alle in Betrieb. Die Projektion dieses Arrays entlang der Senkrechten (den Diagonalen der ursprünglichen Matrix entlang) ist ebenfalls in Figur 9b gezeigt. Wie gezeigt, wird die Anzahl der Verzögerungselemente 68 auf die Hälfte reduziert. Unter Verwendung dieses Arrays ist die Verarbeitungszeit für eine NxN G-Matrix die Zelle (NP-(P² -P)/2). Dementsprechend wird die Verarbeitungszeit für eine einzelne G-Matrix beträchtlich reduziert.

Ein weiterer Vorteil der Implementierungen der Figuren 7, 3 a und 3 b besteht darin, dass jedes Verarbeitungsarray auf die Bandbreite der Matrix skalierbar ist. Für Matrizen mit geringeren Bandbreiten (wobei Elemente der unteren Diagonale Null sind) fallen die Prozessoren 58, 66 dieser Elemente in Figur 7 weg. Da mit Bezug auf die Figuren 3a und 3b die Elemente der unteren Diagonale den am weitesten links gelegenen senkrechten Linien der Figuren 9a und 9b entsprechen, fallen die Prozessoren, die durch diese senkrechten Linien projiziert werden, weg. Zur Illustration anhand der Figur 9a weist die Bandbreite der Matrix die Verarbeitungselemente 58, 62 von a«, d^\ und d^i als Nullen auf. Daher ist die Projektion auf die Prozessoren 66 (die zwei am weitesten links gelegenen) für die Verarbeitung nicht notwendig. Aufgrund dessen sind diese Implementierungen auf die Bandbreite der Matrix skalierbar.

Die Figuren 9c - 9n illustrieren die Zeitdiagramme für jeden Verarbeitungszyklus einer 5 &khgr; 5-Bandmatrix mit einer Bandbreite von 3 und Verzögerungselementen zwischen

jeder zweiten Verbindung. Zu jeder Zeitperiode wird der Wert gezeigt, der jedem Prozessor zugehört. Aktive Prozessoren sind in durchgezogenen Linien dargestellt. Wie in den Figuren gezeigt, setzt sich die Verarbeitung durch das Array fort, von dem linken oberen Prozessor in Figur 9c, Stufe 1, Zeitpunkt 0 (Au) zu dem rechten unteren Prozessor in Figur 9n, Stufe 5 (£55). Wie in den Figuren gezeigt, sind die linken unteren Prozessoren zur Verarbeitung einer Nichtband-Matrix auf Grund der Bandnatur der Matrix nicht erforderlich und nicht dargestellt.

Die Figuren 9o - 9z illustrieren die Zeitdiagramme und den Speicherzugriff für jeden Verarbeitungszyklus eines linearen Arrays, wie etwa jenes nach Figur 9b, das eine 5x5-Bandmatrix verarbeitet. Wie gezeigt, sind nur drei Prozessoren erforderlich, da die 5 &khgr; 5-Matrix eine Bandbreite von 3 hat. Die Figuren illustrieren, dass nur drei Prozessoren erforderlich sind, um die Bandmatrix zu verarbeiten. Wie ebenfalls gezeigt, weist jede Stufe eine relativ hohe Effizienz der Prozessorauslastung auf, die mit größer werdendem N/p zunimmt.

Um die Komplexität der Verarbeitungselemente zu reduzieren, werden die Divisionsund die Quadratwurzel-Funktion nicht von diesen Elementen durchgeführt (ausgenommen). Divisionen und Quadratwurzeln sind auf einem ASIC aufwändiger zu implementieren als Addierer, Subtrahierer und Multiplizierer.

Die einzigen zwei Funktionen, die eine Division durchführen oder eine Quadratwurzel ziehen, sind die Fünfeck- und Achteck-Funktionen 56, 58. Für eine gegebene Stufe werden, wie in den Figuren 6a - 6d gezeigt, die Fünfeck- und Achteck-Funktionen 56, 58 alle auf einer einzelnen Spalte während einer Stufe durchgeführt. Im Besonderen hat jede dieser Spalten oben ein Fünfeck 58 und Achtecke 58 darunter. Da jedes Achteck 58 gleichzeitig seinen w-Eingang an seinen y-Ausgang zuweist, läuft der Ausgang des Fünfecks 56 die gesamte Spalte hinunter, ohne dass der Wert für w direkt für irgendein a,j gespeichert wird. Das Achteck 58 verwendet den w-Eingang auch, um den x-Ausgang zu erzeugen, welcher ebenfalls an ay zurückgeführt wird. Der x-Ausgang wird von den Quadrat- und Kreisfunktionen 60, 62 in deren ay-Berechnungen verwendet. Daher muss nur der Wert für den x-Ausgang jedes Achtecks bestimmt werden. Der x-Ausgang des Achtecks ist der aij-Wert für dieses Achteck 58 dividiert durch den Wert

des w-Eingangs, welcher für jedes Achteck 58 derselbe ist und der y-Ausgang des Fünfecks 56 ist. Dementsprechend ist die einzige Divisions- / Quadratwurzel-Funktion, die ausgeführt werden muss, die Berechnung von &khgr; für das Achteck 58.

Nach den Gleichungen 34 und 30 ist der x-Ausgang jedes Achtecks der ay-Wert dieses Achtecks dividiert durch die Quadratwurzel des Fünfecks a^. Unter Verwendung eines Multiplizierers an Stelle eines Dividierers innerhalb jedes Achteck-Prozessors für eine gegebene Stufe muss nur der Reziprokwert der Quadratwurzel des Fünfecks a^ an Stelle der Quadratwurzel bestimmt werden, was die Divisionsfunktion auf den Fünfeck-Prozessor allein beschränkt und die allgemeine Komplexität des Array vereinfacht. Der Reziprokwert der Quadratwurzel wird dann als der ajj-Wert des dem Fünfeck zugehörigen Elementes der Matrix anstelle des Reziprokwertes gespeichert. Das wird auch später während des Vorwärts- und Rückwärtseinsetzens praktisch sein, da die Divisionsfunktionen in diesen Algorithmen durch diesen Reziprokwert zu Multiplikationen werden, was den Bedarf an Dividierern in anderen Verarbeitungselementen, d. h. den x-Ausgängen der Figuren 12d und 15d, weiter reduziert. Da die Fünfeck-Funktion 56, wie in den Figuren 9a und 9b gezeigt, von dem selben Prozessor 64 durchgeführt wird, können die Prozessoren 66, 64 unter Verwendung eines einzigen Reziprok- / Quadratwurzel-Schaltkreises 70 mit einem Eingang von dem Fünfeck- / Quadrat-Prozessor 64 und einem Ausgang zu diesen Prozessoren 64 implementiert werden, wie in den Figuren 10a und 10b gezeigt. Das Resultat des Reziprokwertes der Quadratwurzel durchläuft die Prozessoren 66. Die Figuren 11a und 11b entsprechen den Figuren 10a und 10b. Die Abtrennung der Reziprok- / Quadratwurzel-Funktion 70 vereinfacht die Komplexität des anderen Prozessors 66, 64. Obwohl der Divisions- / Quadratwurzel-Schaltkreis 70 unter Verwendung eines Reziprok- und eines Quadratwurzel-Schaltkreises implementiert werden kann, wird er vorzugsweise unter Verwendung einer Lookup-Tabelle implementiert, insbesondere für eine Implementierung als feldprogrammierbares Gate-Array (field programmable gate array, FPGA), in welcher der Speicher kostengünstig

• ·

Nachdem der Cholesky-Faktor, G₅ bestimmt worden ist, wird y unter Verwendung des Vorwärtseinsetzens, wie in den Figuren 12a und 12b gezeigt, bestimmt. Der Algorithmus für das Vorwärtseinsetzen sieht wie folgt aus:

for/= I: N

7-l·./ -&Sgr;

& jj V '=i

end

Für eine Bandmatrix sieht der Algorithmus wie folgt aus:

forj = I: N

for i =j + 1: min(/ + p, N)

Ti = &eegr; - Giff,
end for;
end for;
y = r_f,

gLK ist das entsprechende Element in Reihe L, Spalte K der Cholesky-Matrix, G.

Die Figuren 12a und 12b sind zwei Implementierungen des Vorwärtseinsetzens für eine 4x4 G-Matrix unter Verwendung skalarer Prozessoren. Zwei Funktionen werden von den Prozessoren 72, 74 durchgeführt, die Sternfunktion 72 von Figur 12c und die Rautefunktion 74 von Figur 12d. Der Stern 72 führt die Gleichungen 42 und 43 aus.

y <— w Gleichung 42

&khgr; <r- z - w * gy Gleichung 43

Die Rautefunktion 74 führt die Gleichungen 44 und 45 aus. &khgr; <-z/gij Gleichung 44

• ·

y <-x Gleichung 45

Das Einsetzen von Verzögerungselementen zwischen den gleichzeitigen Verbindungen der Verarbeitungselemente wie in Figur 12a und das Projizieren des Arrays senkrecht zu seinen Ausführungsebenen (ti bis \&eegr;) lässt es zu, dass das Array auf ein lineares Array projiziert wird. Die Werte des empfangenen Vektors von r, &eegr; - x\, werden in das Array geladen und yi - y4 von dem Array ausgegeben. Da die Rautefunktion 74 nur entlang der Hauptdiagonale ist, kann das Array aus vier (4) Verarbeitungselementen erweitert werden, um eine N &khgr; N-Matrix unter Verwendung der N Verarbeitungselemente nach Figur 13a zu verarbeiten. Die Verarbeitungszeit für dieses Array beträgt 2 N Zyklen.

Da jedes Verarbeitungselement in nur jedem zweiten Verarbeitungszyklus verwendet wird, kann die Hälfte der Verzögerungselemente, wie in Figur 12b gezeigt, entfernt werden. Dieses projizierte lineare Array kann auf eine beliebige N &khgr; N-Matrix, wie in Figur 13b gezeigt, erweitert werden. Die Verarbeitungszeit für dieses Array beträgt N Zyklen.

Die Operation pro Zyklus der Verarbeitungselemente des projizierten Arrays von Figur 13b ist in den Figuren 14a - 14d illustriert. In dem ersten Zyklus ti von Figur 13a, wird ri in den linken Prozessor 1 (74) geladen und yi wird unter Verwendung von ri und gi &igr; bestimmt. In dem zweiten Zyklus Xi von Figur 14b werden X2 und &Ggr;3 geladen, g3i, gn und g22 werden verarbeitet und y2 wird bestimmt. In dem dritten Zyklus &Idigr;3 von Figur 14c wird &Ggr;4 geladen, g₄i, g₄₂, g32, g33 werden geladen und y3 wird bestimmt. In dem vierten Zyklus &Idigr;4 von Figur 14d werden g43 und g44 verarbeitet und y4 wird bestimmt.

Die Figuren 12e - 12j illustrieren die Zeitdiagramme für jeden Verarbeitungszyklus einer 5 &khgr; 5-Bandmatrix. Figur 12e zeigt die Bandnatur der Matrix mit drei Nulleinträgen in der linken unteren Ecke (eine Bandbreite von 3).

Um zu zeigen, dass dieselben Verarbeitungselemente sowohl für das Vorwärtseinsetzen als auch für die Cholesky-Zerlegung verwendet werden können, beginnt Figur 12f in Stufe 6. Stufe 6 ist die Stufe nach der letzten Stufe der Figuren 9c - 9n.

In ähnlicher Weise illustrieren die Figuren 12k - 12p die Ausweitung der Prozessoren von Figuren 9o - 9z, um auch das Vorwärtseinsetzen durchzuführen. Diese Figuren beginnen auf Stufe 6, nach den 5 Stufen der Cholesky-Zerlegung. Die Verarbeitung wird für jeden Verarbeitungszyklus von Stufe 6, Zeitpimkt 0 (Figur 12k) bis zu den Endergebnissen (Figur 12p), nach Stufe 6, Zeitpunkt 4 (Figur 12o), durchgeführt.

Nachdem die y-Variable durch Vorwärtseinsetzen bestimmt wurde, kann der Datenvektor durch Rückwärtseinsetzen bestimmt werden. Das Rückwärtseinsetzen wird durch das folgende Unterprogramm ausgeführt:
10

for/ = JV:l

Si
end

Für eine Bandmatrix wird das folgende Unterprogramm verwendet:

foTj=N:l

yj=

for i = min(l J — P):j - 1

end for;

(·)* bezeichnet eine komplex konjugierte Funktion. g*LK ist die komplex Konjugierte des entsprechenden Elementes, das für den Cholesky-Faktor G bestimmt wurde. Yl ist das entsprechende Element von y.

Das Rückwärtseinsetzen ist ebenfalls unter Verwendung skalarer Prozessoren unter Verwendung der Stern- und Rautefunktionen 76, 78 implementiert, wie in den Figuren 15a und 15b für ein 4x4 Verarbeitungsarray gezeigt. Jedoch werden diese Funktionen, wie in den Figuren 15c und 15d gezeigt, unter Verwendung der komplex Konjugierten der G-Matrix-Werte durchgeführt. Dementsprechend werden die Gleichungen 42 bis 45 jeweils zu 46 bis 49.

y <—w Gleichung 46

Gleichung 47

Gleichung 48

y <-x Gleichung 49

Mit den Verzögerungselementen 68 an den gleichzeitigen Zuweisungen zwischen den Prozessoren 76, 78, wird das Array von Figur 15a über die Ausführungsebenen auf ein lineares Array projiziert. Dieses Array kann erweitert werden, um eine N &khgr; N-Matrix zu verarbeiten, wie in Figur 16a gezeigt. Die Werte des y_-Vektors werden in das Array von Figur 16a geladen und der Datenvektor d wird ausgegeben. Dieses Array benötigt N Taktzyklen zur Bestimmung von d. Da jeder zweite Prozessor in jedem zweiten Taktzyklus in Betrieb ist, können zwei ds zur selben Zeit bestimmt werden.

Da jeder Prozessor 76, 78 in 16a in jedem zweiten Taktzyklus in Betrieb ist, kann jedes zweite Verzögerungselement, wie in Figur 15b gezeigt, entfernt werden. Das projizierte Array von Figur 15b kann erweitert werden, um eine N &khgr; N-Matrix, wie in Figur 16b gezeigt, zu verarbeiten. Dieses Array benötigt N Taktzyklen zur Bestimmung von d.

Die Operationen pro Zyklus der Verarbeitungselemente 76, 78 des projizierten Arrays von Figur 16b sind in den Figuren 17a - 17d illustriert. In dem ersten Zyklus ti von Figur 17a, wird y4 geladen, g 44 wird verarbeitet und d4 wird bestimmt. In dem zweiten

Zyklus t2 von Figur 17b werden y2 und y3 geladen, g*43 und g*3₃ werden verarbeitet und d3 wird bestimmt. In dem dritten Zyklus t3 von Figur 17c wird yi geladen, g*4i, g*42, g*32 und g*22 werden verarbeitet und d2 wird bestimmt. In dem vierten Zyklus tt von Figur 17d, werden g*43 und g*44 verarbeitet und d4 wird bestimmt.
5

Die Figuren 15e - 15j illustrieren die Erweiterung der Prozessoren der Figuren 12e - 12j auf das Durchfuhren des Rückwärtseinsetzens bei einer Bandmatrix. Figur 15e zeigt die Bandnatur der Matrix mit drei Nulleinträgen in der linken unteren Ecke.

Die Zeitdiagramme beginnen auf Stufe 7, die nach Stufe 6 des Vorwärtseinsetzens liegt. Die Verarbeitung beginnt auf Stufe 7, Zeitpunkt 0 (Figur 15f) und wird auf Stufe 7, Zeitpunkt 4 (Figur 15j), abgeschlossen. Nach Stufe 7, Zeitpunkt 4 (Figur 15j), sind alle Daten, di bis d$, bestimmt.

In ähnlicher Weise illustrieren die Figuren 15k - 15p die Erweiterung der Prozessoren von Figuren 12k - 12p, um auch das Rückwärtseinsetzen durchzuführen. Diese Figuren beginnen auf Stufe 7, nach Stufe 6 des Vorwärtseinsetzens. Die Verarbeitung wird für jeden Verarbeitungszyklus von Stufe 7, Zeitpunkt 0 (Figur 15k), bis zu den Endergebnissen (Figur 15p) durchgeführt. Wie in den Figuren 9c - 9n, 12e - 12j und 15e - 15j gezeigt, kann die Anzahl von Prozessoren in einem zweidimensionalen Array für die Durchführung der Cholesky-Zerlegung und des Vorwärts- und Rückwärtseinsetzens für Bandmatrizen reduziert werden. Wie in den Figuren 9o - 9z, 12k - 12p gezeigt, wird die Anzahl der Prozessoren in einem linearen Array von der Dimension der Matrix auf die Bandbreite von Bandmatrizen reduziert.

Um die Komplexität der einzelnen Verarbeitungselemente 72, 74, 76, 78 für sowohl Vorwärts- als auch Rückwärtseinsetzen zu reduzieren, kann die Divisionsfunktion 80 wie in den Figuren 18a und 18b gezeigt von den Elementen 72, 74, 76, 78 abgetrennt werden. Die Figuren 18a und 18b entsprechen den Figuren 16a beziehungsweise 16b.

Obwohl die den Verarbeitungselementen 72, 74, 76, 78 zugehörigen Daten für das Vorwärts- und Rückwärtseinsetzen sich unterscheiden, ist die von den Elementen 72, 74, 76, 78 durchgeführte Funktion dieselbe. Der Dividierer 80 wird von dem am weitesten rechts liegenden Prozessor 74, 78 verwendet, um die Divisionsfunktion

durchzuführen. Der Dividierer 80 kann als eine Tabelle implementiert werden, um einen Reziprokwert zu bestimmen, der von dem am weitesten rechts liegenden Prozessor 74, 78 bei einer Multiplikation verwendet wird. Da während des Vorwärts- und Rückwärtseinsetzens der Reziprokwert aus der Cholesky-Ausführung bereits im Speicher existiert, kann die Multiplikation des Reziprokwertes für das Vorwärts- und Rückwärtseinsetzen den bereits im Speicher befindlichen Reziprokwert verwenden.

Da der Rechendatenfluss für alle drei Prozesse (Bestimmen von G, Vorwärts- und Rückwärtseinsetzen) derselbe, nämlich N oder die Bandbreite P ist, können alle drei Funktionen in dem selben rekonfigurierbaren Array durchgeführt werden. Jedes Verarbeitungselement 84, 82 des rekonfigurierbaren Arrays ist in der Lage, die Funktionen zur Bestimmung von G und zur Durchführung des Vorwärts- und Rückwärtseinsetzens durchzuführen, wie in den Figuren 19a und 19b gezeigt. Der am weitesten rechts gelegene Prozessor 82 ist in der Lage, eine Fünfeck- / Quadrat- und Rautefunktion 64, 74, 78 durchzuführen. Die anderen Prozessoren 84 sind in der Lage, eine Kreis- / Achteck- und Sternfunktion 66, 72, 76 durchzuführen. Bei der Durchführung der Cholesky-Zerlegung arbeitet der am weitesten rechts gelegene Prozessor 82 unter Verwendung der Fünfeck- / Quadratfunktion 64 und die anderen Prozessoren 84 arbeiten unter Verwendung der Kreis- / Achteckfunktion 66. Bei der Durchführung des Vorwärts- und Rückwärtseinsetzens, arbeitet der am weitesten rechts gelegene Prozessor 92 unter Verwendung der Rautefunktion 74, 78 und die anderen Prozessoren 84 arbeiten unter Verwendung der Sternfunktion 72, 76. Die Prozessoren 82, 84 können vorzugsweise konfiguriert werden, um die erforderlichen Funktionen durchzuführen. Unter Verwendung des rekonfigurierbaren Arrays führt jedes Verarbeitungselement 82, 84 die zwei arithmetischen Funktionen des Vorwärts- und Rückwärtseinsetzens und die vier Funktionen für die Cholesky-Zerlegung durch, insgesamt sechs arithmetische Funktionen je Verarbeitungselement 82, 84. Diese Funktionen können von einem Rechen- und Leitwerk (arithmetic logic unit, ALU) und einer geeigneten Steuerlogik oder durch andere Mittel durchgeführt werden.

Um die Komplexität der einzelnen Verarbeitungselemente 82, 84 in dem rekonfigurierbaren Array zu reduzieren, wird die Divisions- und Quadratwurzel-Funktionalität 86 vorzugsweise mittels einer Reziprok- und Quadratwurzel-Vorrichtung

86 aus dem Array herausgebrochen. Die Reziprok- und Quadratwurzel-Vorrichtung 86 bestimmt vorzugsweise den Reziprokwert, der in einer Multiplikation, wie in den Figuren 20a und 20b gezeigt, von dem am weitesten rechts gelegenen Prozessor 82 beim Vorwärts- und Rückwärtseinsetzen verwendet werden soll, und den Reziprokwert der Quadratwurzel, der in einer Multiplikation unter Verwendung der Daten des am weitesten rechts gelegenen Prozessors verwendet und durch die Prozessoren 84 durchgeleitet wird. Die Bestimmung des Reziprokwertes und des Reziprok- / Quadratwurzelwertes wird vorzugsweise unter Verwendung einer Lookup-Tabelle durchgeführt. Alternativ kann der Divisions- und Quadratwurzel-Funktionsblock 86 ein Divisions-Schaltkreis und ein Quadratwurzel-Schaltkreis sein.

Um die Anzahl der Prozessoren 82, 84 weiter zu reduzieren, wird Faltung verwendet. Die Figuren 21a und 21b illustrieren die Faltung. Bei der Faltung wird, anstatt P Verarbeitungselemente 82, 84 für die Lösung eines linearen Systems zu verwenden, eine kleinere Anzahl von Verarbeitungselementen, F, für Q Falten verwendet. Wenn zum Beispiel P gleich neun (9) Prozessoren 82, 84 ist, führen drei (3) Prozessoren 82, 84 die Funktion der neun (9) Prozessoren über drei (3) Falten durch. Ein Nachteil bei der Faltung besteht darin, dass die Verarbeitungszeit des reduzierten Arrays um ein Vielfaches Q erhöht wird. Ein Vorteil besteht darin, dass die Effizienz der

Prozessorauslastung typischerweise erhöht wird. Für drei Falten wird die Verarbeitungszeit verdreifacht. Dementsprechend basiert die Wahl der Anzahl von Falten auf einem Kompromiss zwischen der Minimierung der Anzahl von Prozessoren und der maximal zulässigen Verarbeitungszeit für die Verarbeitung der Daten.

Figur 21a illustriert die bidirektionale Faltung für vier Verarbeitungselemente 761, 762, 763, 764/78, welche die Funktion von zwölf Elementen über drei Falten des Arrays von Figur 11b durchführen. An Stelle von Verzögerungselementen zwischen den Verarbeitungselementen 76], 762, 763, 764/78 werden Dual-Port-Speicher 861, 862, 863, 864 (86) verwendet, um die Daten jeder Falte zu speichern. Obwohl Verzögerungselemente (Dual-Port-Speicher 86) für jede Verbindung von Verarbeitungselementen verwendet werden können, wie etwa für die Implementierung von Figur 12a, wird dies nur für jede zweite Verbindung illustriert, wie bei der

Implementierung von Figur 12b. An Stelle von Dual-Port-Speichern können zwei Sätze von Single-Port-Speichern verwendet werden.

Während der ersten Falte werden die Daten jedes Prozessors in dessen zugehörigem Dual-Port-Speicher 86 in einer Adresse für Falte 1 gespeichert. Daten aus der Matrix werden ebenfalls in die Prozessoren 76] - 763, 76V78 aus Speicherzellen 881 - 884 (88) eingegeben. Da zwischen dem Prozessor 764/78 der Falte 1 und dem Prozessor 761 der Falte 3 kein Datenumlauf stattfindet, wird zwischen diesen Prozessoren kein Dual-Port-Speicher 86 verwendet. Da jedoch eine einzige Adresse zwischen Falte 1 und Falte 2, Prozessor 76i und zwischen Falte 2 und Falte 3, Prozessor 764/78, erforderlich ist, wird ein Dual-Port-Speicher 86 als unterbrochene Linie dargestellt. Während der zweiten Falte werden die Daten jedes Prozessors in einer Speicheradresse für Falte 2 gespeichert. Daten aus der Matrix werden ebenfalls in die Prozessoren 76i - 763, 764/78 für Falte 2 eingegeben. Daten für Falte 2, Prozessor 76] kommen von Falte 1, Prozessor 76], was derselbe physikalische Prozessor 76i ist, so dass diese Verbindung (obwohl gezeigt) nicht notwendig ist. Während der dritten Falte werden die Daten jedes Prozessors in dessen Speicheradresse für Falte 3 gespeichert. Daten aus der Matrix werden ebenfalls in die Prozessoren 761-763, 764/78 für Falte 3 eingegeben. Die Daten für Falte 3, Prozessor 764/78, kommen von Falte 2, Prozessor 764/78, also ist diese Verbindung nicht notwendig. Für die nächste Verarbeitungsstufe wird das Verfahren für Falte 1 wiederholt.

Figur 22a ist eine Implementierung der bidirektionalen Faltung von Figur 21a, erweitert auf N Prozessoren 76i-76n-i, 76n/78. Die Prozessoren 76i-76n-i, 76n/78 sind funktionell in einem linearen Array angeordnet, wobei sie auf den Dual-Port-Speicher 86 oder zwei Sätze von Single-Port-Speichern zugreifen.

Figur 21b illustriert eine Version des Arrays von Figur 11b mit unidirektionaler Faltung. Während der ersten Falte werden die Daten jedes Prozessors in dessen zugehöriger Dual-Port-Speicheradresse für Falte 1 gespeichert. Obwohl Falte 1, Prozessor 764/78, und Falte 3, Prozessor 76j, physikalisch verbunden sind, werden im Betrieb keine Daten direkt zwischen diesen Prozessoren übertragen. Dementsprechend hat das Speicherport 864 zwischen ihnen Speicherplatz für eine Adresse weniger. Falte 2, Prozessor 764/78,

ist effektiv mit Falte 1, Prozessor 761 durch die ringartige Verbindung zwischen den Prozessoren gekoppelt. In ähnlicher Weise ist Falte 3, Prozessor 764/78, effektiv mit Falte 2, Prozessor 761, gekoppelt.

Figur 22b ist eine Implementierung der unidirektionalen Faltung von Figur 20b, erweitert auf N Prozessoren. Die Prozessoren 76i - 76n-i, 76n/78 sind funktionell als Ring um den Dual-Speicher angeordnet.

Zur Implementierung der Cholesky-Zerlegung und des Vorwärts- und Rückwärtseinsetzens auf gefaltete Prozessoren muss der Prozessor, wie etwa der Prozessor 764/78, in dem Array in der Lage sein, die Funktionen für die Prozessoren für die Cholesky-Zerlegung und das Vorwärts- und Rückwärtseinsetzen durchzuführen, aber auch für jede Falte, wie in den Figuren 20a und 20b für Prozessor 764/78 gezeigt. In Abhängigkeit von der Implementierung können die erforderlichen Fähigkeiten des hinzugefügten Prozessors die Komplexität dieser Implementierung erhöhen. Um die Faltung unter Verwendung von ALUs zu implementieren, führt ein Prozessor (wie etwa Prozessor 764/78) zwölf arithmetische Funktionen (vier für Vorwärts- und Rückwärtseinsetzen und acht für Cholesky) durch und die anderen Prozessoren nur sechs Funktionen.

Figur 23 illustriert eine Schicht eines bevorzugten einfachen rekonfigurierbaren Verarbeitungselementes, das zur Durchführung aller sechs der in der Cholesky-Zerlegung und dem Vorwärtseinsetzen und Rückwärtseinsetzen definierten Funktionen verwendet wird. Dieses Verarbeitungselement kommt zum Einsatz, nachdem die Divisionen auf eines der Verarbeitungselemente isoliert wurden (im Folgenden als PEl bezeichnet). Zwei Schichten werden vorzugsweise verwendet, eine zur Erzeugung der reellen x- und y-Komponenten, die andere zur Erzeugung ihrer imaginären Komponenten. Die unteren Indizes i bzw. r werden verwendet, um reelle bzw. imaginäre Komponenten zu bezeichnen.

Die Signale w, x, y, und &zgr; sind dieselben wie jene, die zuvor in den Funktionsdefinitionen der Verarbeitungselemente definiert wurden. Die Signale a^q bzw. a stellen jeweils den aktuellen Status bzw. den nächsten Status einer Speicherposition

eines Verarbeitungselementes dar, welche in einem bestimmten Zyklus der Verarbeitung geschrieben und/oder gelesen wird. Die Namen in Klammern bezeichnen die Signale, die für die zweite Schicht verwendet werden sollen.

Dieses bevorzugte Verarbeitungselement kann für ein beliebiges der Verarbeitungselemente verwendet werden, obwohl es wünschenswert ist, PEl zu optimieren, welches unabhängig von den anderen Verarbeitungselementen die Divisionsfunktion durchführt. Jeder Eingang zu den Multiplexern 941 bis 94s ist mit einer &Oacgr;' markiert, um anzuzeigen, dass er nur für PEl verwendet wird, mit einem '-', um anzuzeigen, dass er für jedes Verarbeitungselement außer PEl verwendet wird, oder mit einem '+', um anzuzeigen, dass er für alle Verarbeitungselemente verwendet wird. Der Eingang isqr ist außer für die reelle Schicht von PEl mit Null verbunden, wo er mit dem Ausgang einer Funktion verbunden ist, welche den Reziprokwert der Quadratwurzel des aVEingangs erzeugt. Eine solche Funktion könnte als eine Lookup-Tabelle (LUT) mit einem ROM für eine sinnvolle Festkomma-Wortgröße implementiert werden.

Wie in Figur 23 gezeigt, werden die Ausgänge der Multiplexer 941 und 942 durch den Multiplizierer 961 multipliziert. Die Ausgänge der Multiplexer 943 und 944 werden durch einen Multiplizierer 962 multipliziert. Die Ausgänge der Multiplizierer 961 und 962 werden durch einen Additions- / Subtraktions-Schaltkreis 98 kombiniert. Der Ausgang des Additions- / Subtraktions-Schaltkreises 98 wird mit dem Ausgang des Multiplexers 94s durch einen Subtrahierer 99 kombiniert. Der Ausgang des Subtrahierers 99 ist ein Eingang zu dem Multiplexer 94g.

Claims

1. Eine Basisstation zur Rückgewinnung von Daten aus einer Vielzahl von Datensignalen, die als ein empfangener Vektor empfangen werden, wobei die Basisstation Daten des empfangenen Vektors durch Bestimmung eines Cholesky- Faktors einer N × N-Matrix bestimmt, wobei die Basisstation umfasst:
ein Array von Verarbeitungselementen, wobei jedes Verarbeitungselement des Arrays Elemente einer Diagonale der N × N-Matrix empfängt und Elemente einer entsprechenden Diagonale des Cholesky-Faktors bestimmt.

2. Basisstation nach Anspruch 1, worin die Verarbeitungselemente skalare Verarbeitungselemente sind.

3. Basisstation nach Anspruch 1, worin die N × N-Matrix eine Bandbreite P besitzt und eine Anzahl von Verarbeitungselementen gleich P ist und P kleiner N ist.

4. Eine Basisstation zur Rückgewinnung von Daten aus einer Vielzahl von Datensignalen, die als ein empfangener Vektor empfangen werden, wobei die Basisstation Daten des empfangenen Vektors durch Bestimmung eines Cholesky- Faktors einer N × N-Matrix bestimmt und den bestimmten Cholesky-Faktor bei dem Vorwärts- und Rückwärtseinsetzen verwendet, um die Daten der empfangenen Datensignale zu bestimmen, wobei die Basisstation umfasst:
ein Array von höchstens N skalaren Verarbeitungselementen, wobei das Array einen Eingang zum Empfangen von Elementen aus der N × N-Matrix und dem empfangenen Vektor besitzt, jedes skalare Verarbeitungselement bei der Bestimmung des Cholesky-Faktors und der Durchführung des Vorwärts- und Rückwärtseinsetzens verwendet wird, und wobei das Array Daten des empfangenen Vektors ausgibt.

5. Basisstation nach Anspruch 4, worin jeder skalare Prozessor eine Diagonale einer Matrix verarbeitet, welche durch das Array bei der Bestimmung des Cholesky- Faktors und Durchführung des Vorwärts- und Rückwärtseinsetzens verarbeitet wird.

6. Basisstation nach Anspruch 4, worin die N × N-Matrix eine Bandbreite P aufweist und eine Anzahl der höchstens N skalaren Verarbeitungselemente gleich P ist und P kleiner N ist.

7. Basisstation nach Anspruch 4, des Weiteren umfassend eine Quadratwurzel- und Reziprok-Vorrichtung, worin die Quadratwurzel- und Reziprok-Vorrichtung an nur einen einzigen skalaren Prozessor des Arrays gekoppelt ist und keine skalaren Prozessoren des Arrays eine Quadratwurzel- und Reziprok-Funktion ausführen können.

8. Basisstation nach Anspruch 7, worin die Quadratwurzel- und Reziprok- Vorrichtung eine Lookup-Tabelle verwendet.

9. Basisstation nach Anspruch 4, worin jeder Prozessor die Verarbeitung für eine Vielzahl von Diagonalen der N × N-Matrix ausführt.

10. Basisstation nach Anspruch 9, worin für jede einer Vielzahl von Falten jeder skalare Prozessor Elemente von einer einzigen Diagonale der N × N-Matrix verarbeitet.

11. Basisstation nach Anspruch 10, worin eine Anzahl von Falten eine Anzahl der skalaren Prozessoren minimiert und ermöglicht, dass eine Verarbeitungszeit für die N × N-Matrix kleiner ist als ein zulässiges Maximum.

12. Basisstation nach Anspruch 11, worin die skalaren Prozessoren funktionell linear angeordnet sind, wobei Daten in zwei Richtungen durch das Array fließen.

13. Basisstation nach Anspruch 12, worin ein Verzögerungselement operativ zwischen jeden skalaren Prozessor und das Array gekoppelt ist, welches in der Lage ist, zwei N × N-Matrizen gleichzeitig zu verarbeiten.

14. Basisstation nach Anspruch 13, worin alle skalaren Prozessoren eine gemeinsame rekonfigurierbare Implementierung aufweisen.

15. Eine Basisstation zur Rückgewinnung von Daten aus einer Vielzahl von Datensignalen, die als ein empfangener Vektor empfangen werden, wobei die Basisstation Daten des empfangenen Vektors durch Bestimmung eines Cholesky- Faktors einer N × N-Matrix bestimmt, wobei die Basisstation umfasst:
ein Array von skalaren Verarbeitungselementen, wobei jedes Verarbeitungselement einem Element der N × N-Matrix zugehörig ist und Elemente eines entsprechenden Elementes des Cholesky-Faktors bestimmt.

16. Basisstation nach Anspruch 15, worin jedes skalare Verarbeitungselement eindeutig einem Element der N × N-Matrix zugehörig ist.

17. Basisstation nach Anspruch 15, des Weiteren umfassend Verzögerungselemente zwischen Verarbeitungselementen.

18. Basisstation nach Anspruch 17, worin mehrere N × N-Matrizen nacheinander durch das Array geleitet werden.

19. Basisstation nach Anspruch 18, worin das Array eine N × N-Matrix in einer Vielzahl von Stufen verarbeitet, wobei in jeder der Stufen kein Verarbeitungselement in mehr als einem Verarbeitungszyklus aktiv ist.

20. Basisstation nach Anspruch 19, worin alle mehrfachen N × N-Matrizen für eine Stufe der Vielzahl von Stufen verarbeitet werden, bevor auf einer nächsten Stufe fortgefahren wird.

21. Basisstation nach Anspruch 20, worin für jede N × N-Matrix der mehrfachen N × N-Matrizen ein Resultat der Verarbeitung für jede Stufe gespeichert wird, bevor auf einer nächsten Stufe fortgefahren wird.