Bit-Vektor Sortierproblem

[Wolle (Gast)]

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. ! ;-)

[Nobody (Gast)]

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 ?

[Wolle (Gast)]

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. :-(

[Falk B. (falk)]

@ 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

[Wolle (Gast)]

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 !! :(

[Falk B. (falk)]

@ 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.

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

process(ram_out, my_bit_vector)
variable index: integer range 0 to 127;
begin
  index := conv_integer(ram_out);
  sel_bit <= my_bit_vector(index);
end process

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

process(ram_out, my_bit_vector)

begin
  case ram_out is
    when "0000000" => sel_bit <= my_bit_vector(0);
    when "0000001" => sel_bit <= my_bit_vector(0);
    . . . 
    when "1111111" => sel_bit <= my_bit_vector(127);
    when others => null;
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

[Mark (Gast)]

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.

[Wolle (Gast)]

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 !!! :-))