Bit-Vektor Sortierproblem

Wolle Gast #688385
Lesenswert?
• ▲
▼ 
Hallo,
ich bin noch etwas neu bei den FPGA's und finde für eine Umsortierung 
eines Vektors mit 128 Bit keine zufriedenstellende Lösung.
Aufgabe ist es den 128 Bit Eingangsvektor entsprechend den im RAM 
abgelegten Bitadressen in einen 128 Bit Ausgangsvektor umzusortieren. 
Und das nach Möglichkeit zeitoptimiert. Läßt sich wohl über 
"case"-Tabellen realisieren, aber auch nicht unbedingt elegant.
Hat jemand vielleicht 'ne geniale Idee ?? Eine praktische flotte Lösung 
wäre aber auch o.K. ! ;-)
Antwort Zitieren Bearbeiten Thread verschieben Thread sperren Anmeldepflicht aktivieren Anpinnen Thread löschen Thread mit anderem zusammenführen Beitrag melden
Nobody Gast #688451
Lesenswert?
• ▲
▼ 
wieviel Zeit hast Du denn? Soll jedes Bit des Input-Vektors auf ein
beliebiges Bit am Ausgang gemappt werden können?
Steht die Ziel-Adresse in einem 7 bit breiten RAM mit 7 bit Adresse oder 
wie sieht das aus ?
Antwort Zitieren Bearbeiten Löschen Beitrag melden
Wolle Gast #688552
Lesenswert?
• ▲
▼ 
Wäre mit ca. 200..300ns schon zufrieden. Ja, aber nur 1 zu 1, keine 
Mehrfachbelegungen (falls das hilft).Hatte gedacht die Ziel-Adressen im 
Block-RAM zu speichern, da es rekonfigurierbar sein soll. Wichtig ist 
allerdings nur, daß ich die Zuordnung durch's einspielen neuer Daten 
wechseln kann. Probiere z.Z. mit VHDL auf einem XC3S200 mit 200MHz 
herum.
Klingt doch eigentlich ganz einfach, aber leider kann ich die 
Bit-Adressierung innerhalb des Vektors nicht durch eine Variable 
ausdrücken und somit war meine erste 'naive' Idee dahin. :-(
Antwort Zitieren Bearbeiten Löschen Beitrag melden
Falk B. #688656
Lesenswert?
• ▲
▼ 
@ Wolle (Gast)

>Wäre mit ca. 200..300ns schon zufrieden.

Mal gerechnet?

Wenn 128 Bit per Adresse an 128 andere Stelln verlagert werden sollen, 
dann gibt es zwei Extreme

1.) Vollkommen parallele Struktur, die 128 Adressen steuern 128 128:1 
MUXE. Es sollte klar werden, dass das selbst ein GROSSES FPGA schnell 
überfordert.

2.) Vollkommen serielle Struktur. Auf einen RAM müssen 128 Lesezugriffe 
gemacht werden und die Bits umcodiert werden. Braucht halt 128 Takte + 
eine handvoll um das notwendige Pipelinig abzuschliessen. 
Ressourcenaufwand minimal.  Bei 200 MHz sind das dann 1000ns.

Als Zwischenlösung kann man mehrere kleine serielle Vertauscherblöcke 
realisieren, wenn gleich man dann ggf. mit gewissen Einschränkungen 
leben muss.

>Mehrfachbelegungen (falls das hilft).Hatte gedacht die Ziel-Adressen im
>Block-RAM zu speichern, da es rekonfigurierbar sein soll. Wichtig ist

Ja.

>Bit-Adressierung innerhalb des Vektors nicht durch eine Variable

Das ist ein einfacher Multiplexer, wenn gelesen werden soll. Beim 
schreiben ist es ein DeMUX, oder man macht es über ein Schieberegister, 
das ist ausserdem schneller und resourcenschonender.

MFG
Falk
Antwort Zitieren Bearbeiten Löschen Beitrag melden
Wolle Gast #688663
Lesenswert?
• ▲
▼ 
Sorry, nochmal einen Nachtrag.
Es muß doch die Möglichkeit geben mit der aus dem RAM gelesenen 
Bit-Adresse die Position im Zielvektor anzusprechen !? Wenn mir da 
jemand weiterhelfen könnte, habe ich die Sache im Griff.
Vielleicht hat aber auch jemand eine schöne Lösung die Sache ohne 
RAM-Lesezyklen umzusetzen (z.B. vorher in einen langen Vector lesen oder 
über distributed RAM ???)
Geht doch bestimmt !? Bin nur noch zu grün hinter den Ohren !! :(
Antwort Zitieren Bearbeiten Löschen Beitrag melden
Falk B. #688699
Lesenswert?
• ▲
▼ 
@ Wolle (Gast)

>Es muß doch die Möglichkeit geben mit der aus dem RAM gelesenen
>Bit-Adresse die Position im Zielvektor anzusprechen !?

Klar. Entweder direkt über den Index oder, wenn das Synthesetool bissel 
dämlich ist, über einen MUX.

1
-- Arrayzugriff über Index, für schlaue Compiler

2


3
process(ram_out, my_bit_vector)

4
variable index: integer range 0 to 127;

5
begin

6
  index := conv_integer(ram_out);

7
  sel_bit <= my_bit_vector(index);

8
end process

9


10
-- Arrayzugriff über MUX, für nicht ganz so schlaue Compiler

11
-- Scheiss Tipparbeit

12


13
process(ram_out, my_bit_vector)

14


15
begin

16
  case ram_out is

17
    when "0000000" => sel_bit <= my_bit_vector(0);

18
    when "0000001" => sel_bit <= my_bit_vector(0);

19
    . . . 

20
    when "1111111" => sel_bit <= my_bit_vector(127);

21
    when others => null;

22
end process


>Vielleicht hat aber auch jemand eine schöne Lösung die Sache ohne
>RAM-Lesezyklen umzusetzen

Das dürfte schwierig werden.

MFG
Falk
Antwort Zitieren Bearbeiten Löschen Beitrag melden
Mark Gast #688753
Lesenswert?
• ▲
▼ 
Hallo Wolle,

Falk hat das schon super geschildert. Ich würde hier eine Mischung
aus seriell und parallel probieren, also die seriellen 
Vertauscherblöcke.

1) Schieberegister, 8 bit breit, 16 Stufen, hier werden Deine
128 bit Input-Daten byteweise rotiert.

2) Ein identisches Register, welches parallel geladen und dann geschoben
werden kann.

3) Jedes Bit eines Bytes vom 2. Register ist über einen 8-zu-1 MUX mit
dem entspr. Register von 1) verbunden.

Es gibt also 128 8:1 MUXe, immer noch viel Holz, aber beherrschbar denke 
ich.

Wenn Register 1) gefüllt ist, rotierst Du das komplette Register mit 16 
Takten 1 mal im Kreis, so dass jedes Byte 1 mal an jedem Byte von Reg 2) 
vorbeigekommen ist. Nach 16 Takten ist das Umschaufeln fertig, bei
50 MHz z.B. nach 320 ns.
Du brauchst nur noch eine Ansteuerlogik, welche die 128 MUXe in jedem 
Takt entsprechend steuert.
Sicher nicht die eleganteste Lösung aber die erste die mir eingefallen 
ist.
Antwort Zitieren Bearbeiten Löschen Beitrag melden
Wolle Gast #689073
Lesenswert?
• ▲
▼ 
Super! Danke Jungs!
Die Konvertierung der RAM Daten in die Index Variable war das Bindeglied 
was mir gefehlt hat. Hab es noch nicht wirklich getestet aber der 
Compiler frist es erstmal. Wenn ich die Daten aus einem 64bit breitem 
RAM lese und anschließend 8 Eingangsbits parallel umschaufle, paßt es 
auch zeitlich ohne Probleme.
Über Mark's Lösung muß ich in 'ner ruhigen Minute nochmal nachdenken. So 
aus dem ersten Überfliegen hab ich die Logik noch nicht durchdringen 
können. Aber keine Sorge, die Zeit nehme ich mir noch.
Besten Dank jedenfalls nochmal! Superschneller Support, mehr kann man 
sich nicht wünschen !!! :-))
Antwort Zitieren Bearbeiten Löschen Beitrag melden
Thread beobachten

Antwort schreiben

Bitte melde dich an, um einen Beitrag zu schreiben.

Bestehender Account

oder

Mit Google-Account einloggen

Noch kein Account?

Die Registrierung ist kostenlos und dauert nur eine Minute.

Jetzt registrieren