/* permsums: Coded by Antti Karttunen, Jan 30-31 & Jun 21-... 2005. (Continued 27. February 2006.) Generate all permutations of the set {1..n} for successive n's 1, 2, 3, ..., 18, and collect the minimum and maximum of the sum p(1)*p(2) + p(2)*p(3) + p(3)*p(4) +... + p(n-1)*p(n) + p(n)*p(1). and show them on the 4x7-segment display. The meaning of the slide switches: SW_IN[1] (The second from the right) - if this is on (i.e. up) then pause after each permutation, and then, depending on SW_IN[0] (The rightmost slide switch) - if sw_in[0] is down, show the associated factorial expansion, its four most significant digits. - if sw_in[0] is up, show the associated permutation, its five lowermost digits. - otherwise, iterate over the set of all permutations of {1..n} (and show the associated f.ex or permutation of each, like above) and after that, pause, and depending on SW_IN[0] (The rightmost slide switch) - if sw_in[0] is down, show the minimum of the sums collected. - if sw_in[0] is up, show the maximum of the sums collected. The five rightmost leds will show the value nminus+1, i.e. the value of n whose permutations are currently iterated over as a binary expansion. Any time PB_IN2 (the leftmost push button) is pressed, the four-segment display will also show the same value. */ module permsums(CLK,PB_IN,SW_IN,SEG_OUT,DIGIT_OUT,LED_OUT); input CLK; input [2:0] PB_IN; input [2:0] SW_IN; output [7:0] SEG_OUT; output [3:0] DIGIT_OUT; output [7:0] LED_OUT; // n starts from 2, grows up to 18. reg [4:0] n = 2; // (1-18). reg [4:0] nplus1 = 3; // (2-19). reg [1:0] wait_state = 2'b01; wire valid_perm_out; // Registers for 17-digit factorial expansion // (from 00000000000000000 to HGFEDCBA987654321, where H=17, G=16, F=15, etc.) reg f1 = 0; // 0-1 reg [1:0] f2 = 0; // 0-2 reg [1:0] f3 = 0; // 0-3 reg [2:0] f4 = 0; // 0-4 reg [2:0] f5 = 0; // 0-5 reg [2:0] f6 = 0; // 0-6 reg [2:0] f7 = 0; // 0-7 reg [3:0] f8 = 0; // 0-8 reg [3:0] f9 = 0; // 0-9 reg [3:0] f10 = 0; // 0-10 reg [3:0] f11 = 0; // 0-11 reg [3:0] f12 = 0; // 0-12 reg [3:0] f13 = 0; // 0-13 reg [3:0] f14 = 0; // 0-14 reg [3:0] f15 = 0; // 0-15 reg [4:0] f16 = 0; // 0-16 reg [4:0] f17 = 0; // 0-17 // Wires out of the factorial expansion incrementer: wire g1; wire [1:0] g2; wire [1:0] g3; wire [2:0] g4; wire [2:0] g5; wire [2:0] g6; wire [2:0] g7; wire [3:0] g8; wire [3:0] g9; wire [3:0] g10; wire [3:0] g11; wire [3:0] g12; wire [3:0] g13; wire [3:0] g14; wire [3:0] g15; wire [4:0] g16; wire [4:0] g17; // Eighteen five-bit digits to hold a permutation of {1..18}. reg [4:0] p [17:0]; wire [4:0] wp [17:0]; // Same as wires. // The sum of such permutation computed in cyclical Quet-Deutsch manner. reg [13:0] psum = 0; wire [13:0] wpsum; wire round_finished = ((wp[n] != nplus1) && !wait_state); // With pipelined fexNperm we need this one: // wire round_finished = ((wp[n] != nplus1) && valid_perm_out && !wait_state); // fexmsb1 is the most significant digit of the factorial expansion, // fexmsb4 is the fourthmost significant digit. wire [4:0] fexmsb1 = ((n < 6) ? {2'b00,f4} : (6 == n) ? {2'b00,f5} : (7 == n) ? {2'b00,f6} : (8 == n) ? {2'b00,f7} : (9 == n) ? {1'b0,f8} : (10 == n) ? {1'b0,f9} : (11 == n) ? {1'b0,f10} : (12 == n) ? {1'b0,f11} : (13 == n) ? {1'b0,f12} : (14 == n) ? {1'b0,f13} : (15 == n) ? {1'b0,f14} : (16 == n) ? {1'b0,f15} : (17 == n) ? f16 : f17); wire [4:0] fexmsb2 = ((n < 6) ? {3'b000,f3} : (6 == n) ? {2'b00,f4} : (7 == n) ? {2'b00,f5} : (8 == n) ? {2'b00,f6} : (9 == n) ? {2'b00,f7} : (10 == n) ? {1'b0,f8} : (11 == n) ? {1'b0,f9} : (12 == n) ? {1'b0,f10} : (13 == n) ? {1'b0,f11} : (14 == n) ? {1'b0,f12} : (15 == n) ? {1'b0,f13} : (16 == n) ? {1'b0,f14} : (17 == n) ? {1'b0,f15} : f16); wire [4:0] fexmsb3 = ((n < 6) ? {3'b000,f2} : (6 == n) ? {3'b000,f3} : (7 == n) ? {2'b00,f4} : (8 == n) ? {2'b00,f5} : (9 == n) ? {2'b00,f6} : (10 == n) ? {2'b00,f7} : (11 == n) ? {1'b0,f8} : (12 == n) ? {1'b0,f9} : (13 == n) ? {1'b0,f10} : (14 == n) ? {1'b0,f11} : (15 == n) ? {1'b0,f12} : (16 == n) ? {1'b0,f13} : (17 == n) ? {1'b0,f14} : {1'b0,f15}); wire [4:0] fexmsb4 = ((n < 6) ? {4'b0000,f1} : (6 == n) ? {3'b000,f2} : (7 == n) ? {3'b000,f3} : (8 == n) ? {2'b00,f4} : (9 == n) ? {2'b00,f5} : (10 == n) ? {2'b00,f6} : (11 == n) ? {2'b00,f7} : (12 == n) ? {1'b0,f8} : (13 == n) ? {1'b0,f9} : (14 == n) ? {1'b0,f10} : (15 == n) ? {1'b0,f11} : (16 == n) ? {1'b0,f12} : (17 == n) ? {1'b0,f13} : {1'b0,f14}); wire GND = 1'b0; wire CLK_USED; wire CLK_LOCKED; wire CLK0; puolita PUOLITAS(.CLKIN_IN(CLK), .RST_IN(GND), .CLKDV_OUT(CLK_USED), .CLKIN_IBUFG_OUT(), .CLK0_OUT(CLK0), .LOCKED_OUT(CLK_LOCKED)); shw5spec DIGDISPLAY(CLK_USED, /* p[3],p[2],p[1],p[0], */ (SW_IN[0] ? p[3] : (SW_IN[1] ? psum[11:8] : fexmsb1)), (SW_IN[0] ? p[2] : (SW_IN[1] ? psum[7:4] : fexmsb2)), (SW_IN[0] ? p[1] : (SW_IN[1] ? psum[3:0] : fexmsb3)), (SW_IN[0] ? p[0] : (SW_IN[1] ? n : fexmsb4)), 1'b1,1'b1,1'b1,1'b1, SEG_OUT,DIGIT_OUT); assign LED_OUT = {round_finished,valid_perm_out,wait_state[1],wait_state[0],n[3:0]}; // assign LED_OUT = (~SW_IN[0] ? {1,CLK_LOCKED,CLK_USED,n[4:0]} : psum[7:0]); inc17fexb INCFEX(f1,f2,f3,f4,f5,f6,f7,f8,f9,f10, f11,f12,f13,f14,f15,f16,f17, g1,g2,g3,g4,g5,g6,g7,g8,g9,g10, g11,g12,g13,g14,g15,g16,g17); fex17perm FEXPERM(CLK_USED,~round_finished, f1,f2,f3,f4,f5,f6,f7,f8,f9,f10, f11,f12,f13,f14,f15,f16,f17, valid_perm_out, wp[0],wp[1],wp[2],wp[3],wp[4],wp[5],wp[6],wp[7],wp[8],wp[9], wp[10],wp[11],wp[12],wp[13],wp[14],wp[15],wp[16],wp[17]); // The highest non-zero term is "extra", not included among the permuted digits. perm19sum PERMSUM(wpsum, p[0], (n > 1 ? p[1] : (1 == n ? nplus1 : 5'b00000)), (n > 2 ? p[2] : (2 == n ? nplus1 : 5'b00000)), (n > 3 ? p[3] : (3 == n ? nplus1 : 5'b00000)), (n > 4 ? p[4] : (4 == n ? nplus1 : 5'b00000)), (n > 5 ? p[5] : (5 == n ? nplus1 : 5'b00000)), (n > 6 ? p[6] : (6 == n ? nplus1 : 5'b00000)), (n > 7 ? p[7] : (7 == n ? nplus1 : 5'b00000)), (n > 8 ? p[8] : (8 == n ? nplus1 : 5'b00000)), (n > 9 ? p[9] : (9 == n ? nplus1 : 5'b00000)), (n > 10 ? p[10] : (10 == n ? nplus1 : 5'b00000)), (n > 11 ? p[11] : (11 == n ? nplus1 : 5'b00000)), (n > 12 ? p[12] : (12 == n ? nplus1 : 5'b00000)), (n > 13 ? p[13] : (13 == n ? nplus1 : 5'b00000)), (n > 14 ? p[14] : (14 == n ? nplus1 : 5'b00000)), (n > 15 ? p[15] : (15 == n ? nplus1 : 5'b00000)), (n > 16 ? p[16] : (16 == n ? nplus1 : 5'b00000)), (n > 17 ? p[17] : (17 == n ? nplus1 : 5'b00000)), ((18 == n) ? nplus1 : 5'b00000), ((18 == n) ? 5'b00000 : nplus1)); wire PB_IN0; // State of the debounced push button for incrementing. reg pb_in0_prev = 0; // is saved here also. debounced_button DBB0(CLK_USED,PB_IN[0],PB_IN0); wire PB_IN1; // State of the debounced push button for incrementing. reg pb_in1_prev = 1; // is saved here also. debounced_button DBB1(CLK_USED,PB_IN[1],PB_IN1); wire single_step = SW_IN[2]; wire pb_in0_pressed = (PB_IN0 && ~pb_in0_prev); wire compute_next_permutation = (!single_step || pb_in0_pressed); /* ======================================================================== Here L = latency of fexNperm module in cycles. +-- f1 - fN contain an incorrect value, and have | already been for L cycles before this one. | Here p[0] - p[N] contain the last valid perm | of the finished round. | | +- In the next cycle f1 - fN already contain | | a correct value (all zeros). | | v v _ round_finished _____| |___________________ (fed as inverted to input_valid of fexNperm) +---- At this cycle (one cycle | after valid_perm_out | dipped for a single cycle) | wp's are correct again. | | +-- On the next cycle also <-- L cycles --> v v p's are correct. ______________________ _______ valid_perm_out |_| ________________ | |_ wait_state ___________________| |_____ Register wait_state is 2'b11 as long as wp's are not correct, and 2'b01 as long as p's are not correct. It's height in above diagram is coded as a Gray code in two bits. wait_state should go to level one at the same moment valid_perm_out rises up. (stays on level one as long as valid_perm_out is low) wait_state should go zero, if wait_state is at level one. otherwise, wait_state should go to max. used level (now 2) on the next cycle after round_finished has been raised up. ======================================================================== At the start-up, valid_perm_out stays low for L cycles: When starting with n == 2: id perm in wp's -----+ +---- id perm in p's, "...654312" in wp's (n == 2) | | | | | | +-- "654231" in wp's, round_finished raised | | | | | | | | | <-- L cycles -> v v v __________________ _________ valid_perm_out _______________| |_| ^ +--- wp = "...653421" _ _ round_finished ___________________| |____________________| |_____ <-- L cycles -> <-- L cycles -> <-- L cycles -> _____________ ______________ ______________ | |_ | |_ | |_ wait_state _| |___| |_____| |__ ======================================================================== Note that if fexNperm is implemented wholly combinationally (not pipelined) then L = 0, and valid_perm_out goes low at the same cycle as round_finished goes up (as the signal output_valid and input_valid are cimply connected with the assign statement in fexNperm). Then the diagram looks like this: _ round_finished _____| |___________________ _____ ___________________ valid_perm_out |_| +------- f1 - fN correct again (all zeros). | (wp's correct before the next edge) | | | v +--- p's correct again. | _ v wait_state ___________________| |_____ */ integer i; reg pause_between_rounds = 1; always @(posedge CLK_USED) begin pb_in0_prev <= PB_IN0; pb_in1_prev <= PB_IN1; if(pb_in0_pressed) pause_between_rounds <= 0; if(compute_next_permutation && !pause_between_rounds) begin f1 <= (round_finished ? 0 : g1); f2 <= (round_finished ? 0 : g2); f3 <= (round_finished ? 0 : g3); f4 <= (round_finished ? 0 : g4); f5 <= (round_finished ? 0 : g5); f6 <= (round_finished ? 0 : g6); f7 <= (round_finished ? 0 : g7); f8 <= (round_finished ? 0 : g8); f9 <= (round_finished ? 0 : g9); f10 <= (round_finished ? 0 : g10); f11 <= (round_finished ? 0 : g11); f12 <= (round_finished ? 0 : g12); f13 <= (round_finished ? 0 : g13); f14 <= (round_finished ? 0 : g14); f15 <= (round_finished ? 0 : g15); f16 <= (round_finished ? 0 : g16); f17 <= (round_finished ? 0 : g17); if(round_finished) begin n <= nplus1; nplus1 <= nplus1+1; pause_between_rounds <= 1; end wait_state <= ((round_finished|~valid_perm_out) ? {valid_perm_out,1} : ((2'b01 == wait_state) ? 2'b00 : wait_state)); for(i=0; i<=17; i=i+1) p[i] <= wp[i]; psum <= wpsum; end end endmodule