Welcome to EDAboard.com

Welcome to our site! EDAboard.com is an international Electronic Discussion Forum focused on EDA software, circuits, schematics, books, theory, papers, asic, pld, 8051, DSP, Network, RF, Analog Design, PCB, Service Manuals... and a whole lot more! To participate you need to register. Registration is free. Click here to register now.

Register Log in

extended euclid algorithm

Status
Not open for further replies.

MaheshKS

Newbie level 3
Joined
Apr 3, 2015
Messages
4
Helped
0
Reputation
0
Reaction score
0
Trophy points
1
Activity points
25
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

 
Last edited by a moderator:

FvM

Super Moderator
Staff member
Joined
Jan 22, 2008
Messages
47,493
Helped
14,051
Reputation
28,357
Reaction score
12,708
Trophy points
1,393
Location
Bochum, Germany
Activity points
276,184
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. http://en.wikipedia.org/wiki/Extended_Euclidean_algorithm
 

MaheshKS

Newbie level 3
Joined
Apr 3, 2015
Messages
4
Helped
0
Reputation
0
Reaction score
0
Trophy points
1
Activity points
25
am trying obtain multiplicative modulo inverse using extended euclids method
 

ads-ee

Super Moderator
Staff member
Joined
Sep 10, 2013
Messages
7,655
Helped
1,774
Reputation
3,556
Reaction score
1,724
Trophy points
1,393
Location
USA
Activity points
57,835
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

Newbie level 3
Joined
Apr 3, 2015
Messages
4
Helped
0
Reputation
0
Reaction score
0
Trophy points
1
Activity points
25
no.. if B3 is greater than one the else branch should take place....... yea, i could see lot of difference
 

FvM

Super Moderator
Staff member
Joined
Jan 22, 2008
Messages
47,493
Helped
14,051
Reputation
28,357
Reaction score
12,708
Trophy points
1,393
Location
Bochum, Germany
Activity points
276,184
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

Super Moderator
Staff member
Joined
Sep 10, 2013
Messages
7,655
Helped
1,774
Reputation
3,556
Reaction score
1,724
Trophy points
1,393
Location
USA
Activity points
57,835
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. :cry:
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

Advanced Member level 4
Joined
Feb 16, 2015
Messages
1,087
Helped
306
Reputation
612
Reaction score
302
Trophy points
83
Activity points
8,699
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: http://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.
 

Status
Not open for further replies.
Toggle Sidebar

Part and Inventory Search

Welcome to EDABoard.com

Sponsor

Top