extended euclid algorithm

[MaheshKS]

Hiii all, am trying to do verilog coding for extended euclids algorithm.. i ve done the code but der is some problem in the code... it is not entering in to the else loop..(ie..if (B3!=1)).. plzzzz help me...

---

Code Verilog - [expand]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
module private_key(
   input rst,clk,
    input [7:0]e_in,n_in,
    output reg [7:0]d_out);
    
    reg [7:0]A1,A2,A3,B1,B2,B3,temp,temp1,temp2,temp3,quo,count,rem;
    
    always @(posedge clk)
    begin
    if(rst)
    begin
    A1<=1;A2<=0;A3<=n_in;
    B1<=0;B2<=1;B3<=e_in;
    end
    
        else 
            begin
                
            if(B3)
            d_out<=B2;
            
            else
                begin
                temp <= A3; 
                if (temp>=B3) 
                    begin
                    temp<=temp-B3;
                    count<= count+1;
                    end
                    
                    else
                    begin
                    rem <= temp;
                    quo <= count;
                    end
            
            
            temp1<=A1; temp2<=A2; temp3<=A3;
            
            A1<=B1; A2<=B2; A3<=B3;
            
            B1<=temp1-(quo*B1);
            B2<=temp2-(quo*B2);
            B3<=temp3-(quo*B3);
 
        end
        
        end
    end
endmodule

---

 

[FvM]

Did you check the algorithm in a testbench? You'll notice that several variables are undefined when they are used in the first iteration(s), e.g. quo.

The code doesn't look like a correct implementation of extended euclidian algorithm. https://en.wikipedia.org/wiki/Extended_Euclidean_algorithm

 

[MaheshKS]

am trying obtain multiplicative modulo inverse using extended euclids method

 

[ads-ee]

Only if B3 is 8'd0 will the else branch be taken, every other value will evaluate as logically true for the if compare.

To paraphrase FvM... Where is your testbench?

I'd appreciate if you would nicely format and use white between operations, so I don't have to do it (just to read the code).

compare the readability of the following reformatted code to your post above.

---

Code Verilog - [expand]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
module private_key(
    input             rst, clk,
    input      [7:0]  e_in, n_in,
    output reg [7:0]  d_out);
    
    reg [7:0] A1, A2, A3;
    reg [7:0] B1, B2, B3,
    reg [7:0] temp, temp1, temp2, temp3,
    reg [7:0] quo, count, rem;
    
    always @(posedge clk) begin
        if(rst) begin
            A1 <= 1;
            A2 <= 0;
            A3 <= n_in;
            B1 <= 0;
            B2 <= 1;
            B3 <= e_in;
        end else begin
            if (B3)
                d_out <= B2;
            else begin
                temp <= A3; 
                if (temp >= B3) begin
                    temp <= temp - B3;
                    count <= count +1;
                end else begin
                    rem <= temp;
                    quo <= count;
                end
                temp1 <= A1;
                temp2 <= A2;
                temp3 <= A3;
                A1 <= B1;
                A2 <= B2;
                A3 <= B3;
                B1 <= temp1 - (quo * B1);
                B2 <= temp2 - (quo * B2);
                B3 <= temp3 - (quo * B3);
            end
        end
    end
endmodule

---

 

[MaheshKS]

no.. if B3 is greater than one the else branch should take place....... yea, i could see lot of difference

 

[FvM]

The discussion seems pointless. Have a testbench, check the code, come back with the results and related questions.

I presume that the testbench will reveal uninitialized variables in a first order, so be prepared to make a few corrections.

 

[ads-ee]

it is not entering in to the else loop..(ie..if (B3!=1))

no.. if B3 is greater than one the else branch should take place.

If you know Verilog so well then why doesn't it do what you say it is supposed to do?

Even with 12+ years of Verilog FPGA design experience, I suppose I still don't know how an if statement works.
Guess I better hand in my resignation where I work now, I'm obviously not qualified to do my job. ;-)

All joking aside....

Your code defines B3 as a 8-bit wide reg.

---

Code Verilog - [expand]
1
reg [7:0]A1,A2,A3,B1,B2,B3,temp,temp1,temp2,temp3,quo,count,rem;

---

You then proceed to check if it's "true" i.e. 1, based on your question (ie..if (B3!=1)).

---

Code Verilog - [expand]
1
2
3
4
if(B3)
        // code you think only executes when B3 = 1         
    else
        // code you think only executes when B3 != 1

---

Unfortunately, that is NOT how Verilog interprets a 8-bit wide vector in an if statement. Instead a multi-bit vector is false only when the vector is all 0's or a combination of Z's, X's, and 0's.

But if you still don't believe me then run the following code in a simulator for 100 ns.

---

Code Verilog - [expand]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
`timescale 1ps/1ps
module test;
 
reg [7:0] B3;
initial begin
  B3 = 1; // you claim only this line should evaluate as "TRUE"
  # 10000;
  B3 = 0;
  # 10000;
  B3 = 8'b1000_0000;
  # 10000;
  B3 = 8'b0000_000Z;
  # 10000;
  B3 = 8'b0000_00X0;
  # 10000;
  B3 = 8'b0000_0001;
  # 10000;
  B3 = 5;
  # 10000;
  B3 = 8'b0000_0000;
  # 10000;
  B3 = 8'bzzzz_xxxx;
  # 10000;
  B3 = 8'b1111_1111;
  # 10000;
end
 
always @* begin
  if (B3) $display ("B3 is TRUE => %b", B3);
  else $display ("B3 is FALSE => %b", B3);
end
 
endmodule

---

 

[vGoodtimes]

The main issues that I see:
1.) it isn't clear if you expect an input-output per cycle, or after "a long enough time". You use reset to load inputs, which is uncommon, and have no "output is valid" indicator.
2.) ads_ee is right. I don't know any language where "if (B3)" would mean that B3 is specifically equal to 1.
3.) You clearly are expecting the non-blocking "<=" to have the blocking "=" semantics. I suggest you read up on this topic, as it is important and there are several posts and articles on the subject.

As secondary items:
1.) I avoid the "if (x) y;" with no begin/end. This is more of a style choice, but you can run into issues. ads_ee's coding style with "end else begin" might look odd (with "end" at the beginning of a line) at first, but I think it is the best choice possible.
2.) I don't do enough collaborative verilog designs to know the opinion on this: https://stackoverflow.com/questions...ables-be-given-local-scope-to-an-always-block . It seems like what you want -- VHDL-style variables -- but I get the feeling co-workers would become annoyed by this style.