Quadratwurzelberechnung in VHDL mit Modelsim

[Adrian W. (wuethria)]

Hallo allerseits

Hat jemand eine Idee, wie ich folgenden Wurzelalgorithmus in VHDL 
übersetzen kann bzw. wie der "Data Path" hierzu aussehen sollte? Die 
Aufgabe war, sowohl den Datenpfad wie auch die Finite State Machine 
jeweils in einem vhd-File zu erstellen.

Hier der Code:
public static int sqrt (int num) {
  int op = num;
  int res = 0;
  int one = 1 << 6;

  while (one > op) {
    one >>=2;

  while (one != 0) {
    if (of >= res + one) {
      op -= res + one;
      res += 2 * one;
    }
    res >>= 1;
    one >>= 2;
  }
  return res;
}

[Lupo (Gast)]

ModelSim kann glaube ich Wurzel, aber um einen Code zu bekommen, must Du 
den Wizzard bemühen und einen Divider instanziieren. Bei Altera heisst 
der LPM_DIVIDE.

[Günter -. (guenter)]

Adrian Wüthrich wrote:
> Hallo allerseits
>
> Hat jemand eine Idee, wie ich folgenden Wurzelalgorithmus in VHDL
> übersetzen kann bzw. wie der "Data Path" hierzu aussehen sollte? Die
> Aufgabe war, sowohl den Datenpfad wie auch die Finite State Machine
> jeweils in einem vhd-File zu erstellen.
>
> Hier der Code:

Da scheint eine geschweifte Klammer (für eines der while()) zu fehlen. 
Ich bin mal davon ausgegangen das die zweite while()-Schleife innerhalb 
der ersten ist:

> public static int sqrt (int num) {
>   int op = num;
>   int res = 0;
>   int one = 1 << 6;
>
>   while (one > op) {

<DP>
>     one >>=2;
</DP>

>
>     while (one != 0) {
>       if (of >= res + one) {
>         op -= res + one;

<DP>
>         res += 2 * one;
</DP>

>       }

<DP>
>       res >>= 1;
>       one >>= 2;
</DP>

>   }
>   return res;
> }

Was ich mit <DP> </DP> gekennzeichnet habe würde ich in den Data Path 
stecken und alles andere in den Controller.

[Rick Dangerus (Gast)]

@lupo:

Wer lesen kann, ist klar im Vorteil.

> ModelSim kann glaube ich Wurzel, aber um einen Code zu bekommen, must Du
> den Wizzard bemühen und einen Divider instanziieren. Bei Altera heisst
> der LPM_DIVIDE.

Wo bitteschön wird in seinem Code wird ein Dividierer benötigt.

state_init:
>>  int op = num;
>>  int res = 0;
>>  int one = 1 << 6;

state_shift:
>>  while (one > op) {
>>    one >>=2;

state_check_ready:
>>  while (one != 0) {
...
>>    res >>= 1;
>>    one >>= 2;
>>  }

state_calc:
>>      op -= res + one;
>>      res += 2 * one;

Die Bedingungen zum Wechseln der Zustände darfst Du Dir selbst 
ausdenken.

Rick

[Jörg (Gast)]

Also zunächst, im Code fehlt eine geschweifte Klammer, ein
Variablenname war falsch, neuer Code:

public static int sqrt (int num) {
  int op = num;
  int res = 0;
  int one = 1 << 6;

  while (one > op) {
    one >>=2;
  } // << missing braket !!!!!!!!!!!!

  while (one != 0) {
    if (op >= res + one) {  // op instead of !!!!!!!!!!!
      op -= res + one;
      res += 2 * one;
    }
    res >>= 1;
    one >>= 2;
  }
  return res;
}


Dann zum Datapath:
==================
Läst sich schrittweise aus deinem Code extrahieren, du brauchtst mind.
3 Register, ich benutze im Folgenden aber 5, ein signed "tmpval" und
ein std_signal "tmpbool":

Dummy:

  Operation NOP: (dummy operation)
    op  <=op
    res <= res
    one <= one

Start:

  Operation 0a:
    op  <= num
    res <= 0
    one <= 1 << 6       (= 64 !!)


While1:

  Operation 1a:
    tmpbool <= '1' when one > op else '0';

  Operation 1b: (falls tmpbool = '1')
    one <= one(maxbit downto 2)


While2:

  Operation 2a:
     tmpbool <= '1' when one > 0 else '0'

  Operation 2b:
     tmpval <= res + one

  Operation 2c:
     tmpbool <= '1' when op > tmpval else '0';

  Operation 2d: (falls tmpbool = '1')
     op  <= op - res - one
     res <= res + (one & 0)

  Operation 2e: (falls tmpbool = '1')
     res <= "0"  & res(maxbit downto 1)
     res <= "00" & one(maxbit downto 2)

End:

Fehlt nur noch der Multiplexer (Abb. Code => Operation), ist aber
ganz einfach in VHDL..


Zum ControlPath: (TransitionTable inkl Statements)
================

S0a: S1a,Operation0a


S1a: if tmpbool='0' => S2a, OperationNOP
     if tmpbool='1' => S1b, Operation1a

S1b: S2a,Operation1b


S2a: S3b,Operation2a

S2b: if tmpbool='0' => S3a, OperationNOP
     if tmpbool='1' => S2c, Operation1b

S2c: S3b,Operation2b

S2c: if tmpbool='0' => S3c, OperationNOP
     if tmpbool='1' => S3c, Operation2c

S2d: S2a,Operation7

S3a: ende...

State-Logik in VHDL zu schreiben, dürfte dann ja kein Problem mehr
sein..


DataPath als auch ControlPath (StateMachine) sind so ziemlich 1:1
umgesetzt. Hoffe mal, habe keinen Fehler gemacht. Falls doch, dürfte
eine Korrektur kein Problem machen.


Gruss

Jörg

[Lupo (Gast)]

>> ModelSim kann glaube ich Wurzel, aber um einen Code zu bekommen, must Du
>> den Wizzard bemühen und einen Divider instanziieren. Bei Altera heisst
>> der LPM_DIVIDE.

>Wo bitteschön wird in seinem Code wird ein Dividierer benötigt.

Ja,,ja bin gestört worden - aber das Gesagte gilt analog! -> kleine 
gedankliche Transferleistung Deinerseits erforderlich.