Underconstruction: 2012

2012年9月20日木曜日

週刊 TD4をFPGAで創る第５号「命令デコーダを創る」

第９章からです。
ついにシミュレーション編完結！！

命令デコーダがどのような経緯でIC２つに収まったかは渡波(2003)をご参照くださいな。

Amazon.co.jp - 渡波郁「CPUの創りかた」毎日コミュニケーションズ (2003)

１．74HC10

まずは3入力NAND3つ入り！

module LOGIC_74HC10(A1, B1, C1, Y1, A2, B2, C2, Y2, A3, B3, C3, Y3);
 input A1, B1, C1, A2, B2, C2, A3, B3, C3;
 output Y1, Y2, Y3;
 
 assign Y1 = ~(A1 & B1 & C1);
 assign Y2 = ~(A2 & B2 & C2);
 assign Y3 = ~(A3 & B3 & C3);
endmodule

テストベンチはいらないよね？

２．74HC32

次に2入力OR4つ入り！

module LOGIC_74HC32(A1, B1, Y1, A2, B2, Y2, A3, B3, Y3, A4, B4, Y4);
 input A1, B1, A2, B2, A3, B3, A4, B4;
 output Y1, Y2, Y3, Y4;
 
 assign Y1 = A1 | B1;
 assign Y2 = A2 | B2;
 assign Y3 = A3 | B3;
 assign Y4 = A4 | B4;
endmodule

これもテストベンチはいらないよね？

３．命令デコーダ

いよいよ命令デコーダづくり！
気合入れていきましょう。

module InstructionDecoder(OPERATION_CODE, C_FLAG_BAR, LOAD_0, LOAD_1, LOAD_2, LOAD_3, SELECT_A, SELECT_B);
 input [3:0] OPERATION_CODE;
 input C_FLAG_BAR;
 output LOAD_0, LOAD_1, LOAD_2, LOAD_3, SELECT_A, SELECT_B;
 
 reg Vcc = 1;
 reg GND = 0;
 
 wire [1:0] w;
 
 assign SELECT_B = OPERATION_CODE[1];
 
 LOGIC_74HC32 logic_74hc32 (
  OPERATION_CODE[2], OPERATION_CODE[3], LOAD_0, 
  w[0], OPERATION_CODE[3], LOAD_1, 
  OPERATION_CODE[0], OPERATION_CODE[3], SELECT_A, 
  OPERATION_CODE[0], C_FLAG_BAR, w[1]
  );
 
 LOGIC_74HC10 logic_74hc10 (
  OPERATION_CODE[2], Vcc, Vcc, w[0], 
  Vcc, w[0], OPERATION_CODE[3], LOAD_2, 
  OPERATION_CODE[2], OPERATION_CODE[3], w[1], LOAD_3
  );
endmodule

はい！出来上がり！

テストベンチはこんな感じ！

module instruction_decoder_test;
 reg  [3:0] OPCODE;
 reg  C_FLAG_BAR;
 wire LOAD_0, LOAD_1, LOAD_2, LOAD_3, SELECT_A, SELECT_B;
 
 InstructionDecoder decoder(OPCODE, C_FLAG_BAR, LOAD_0, LOAD_1, LOAD_2, LOAD_3, SELECT_A, SELECT_B);
 
 initial begin
  $dumpfile("instruction_decoder_test.vcd");
  $dumpvars(0, instruction_decoder_test);
  $monitor ("%t: OPCODE = %b%b%b%b, C_FLAG_BAR = %b, (SELECT_B, A, LOAD_0, 1, 2, 3) = %b %b %b %b %b %b", 
   $time, OPCODE[3], OPCODE[2], OPCODE[1], OPCODE[0], C_FLAG_BAR, 
   SELECT_B, SELECT_A, LOAD_0, LOAD_1, LOAD_2, LOAD_3);

   OPCODE = 4'b0000; C_FLAG_BAR = 1'b0;
  #10 OPCODE = 4'b0001; C_FLAG_BAR = 1'b0;
  #10 OPCODE = 4'b0010; C_FLAG_BAR = 1'b0;
  #10 OPCODE = 4'b0011; C_FLAG_BAR = 1'b0;
  #10 OPCODE = 4'b0100; C_FLAG_BAR = 1'b0;
  #10 OPCODE = 4'b0101; C_FLAG_BAR = 1'b0;
  #10 OPCODE = 4'b0110; C_FLAG_BAR = 1'b0;
  #10 OPCODE = 4'b0111; C_FLAG_BAR = 1'b0;
  #10 OPCODE = 4'b1001; C_FLAG_BAR = 1'b0;
  #10 OPCODE = 4'b1011; C_FLAG_BAR = 1'b0;
  #10 OPCODE = 4'b1110; C_FLAG_BAR = 1'b0;
  #10 OPCODE = 4'b1110; C_FLAG_BAR = 1'b1;
  #10 OPCODE = 4'b1111; C_FLAG_BAR = 1'b0;
  #10 $finish;
 end
endmodule

出力結果をよーく本と見比べてね！

４．そして，完成へ…

長かったCPUづくりもいよいよ一段落です。
すべてのパーツを組み合わせましょう。

module Processor(RESET, CLOCK, INPUT, OUTPUT);
 input RESET, CLOCK;
 input [3:0] INPUT;
 output [3:0] OUTPUT;
 
 reg  Vcc = 1'b1;
 reg  GND = 1'b0;
 wire [5:0] NOT_IN_USE;
 
 wire [3:0] ROM_ADDRESS;
 wire [7:0] ROM_DATA;
 wire [3:0] OPERATION_CODE;
 wire [3:0] IMEEDIATE_DATA;
 
 wire LOAD_0, LOAD_1, LOAD_2, LOAD_3, SELECT_A, SELECT_B;
 
 wire [3:0] REGISTER_IN;
 wire [3:0] REGISTER_A_OUT;
 wire [3:0] REGISTER_B_OUT;
 wire [3:0] REGISTER_C_OUT;
 wire [3:0] REGISTER_D_OUT;
 wire [3:0] ALU_IN_A;
 wire [3:0] ALU_IN_B;
 wire CARRY_OUT, C_FLAG, C_FLAG_BAR;
 
 assign ROM_ADDRESS = REGISTER_D_OUT;
 assign OPERATION_CODE = ROM_DATA[7:4];
 assign IMEEDIATE_DATA = ROM_DATA[3:0];
 assign ALU_IN_B = IMEEDIATE_DATA;
 assign OUTPUT = REGISTER_C_OUT;
 
 ROM_16WORD  ROM(ROM_ADDRESS, ROM_DATA);
 
 InstructionDecoder Instruction_Decoder (OPERATION_CODE, C_FLAG_BAR, 
  LOAD_0, LOAD_1, LOAD_2, LOAD_3, SELECT_A, SELECT_B);
 
 LOGIC_74HC161 Register_A (RESET, CLOCK, 
  REGISTER_IN[0], REGISTER_IN[1], REGISTER_IN[2], REGISTER_IN[3], 
  GND, LOAD_0, GND, 
  REGISTER_A_OUT[0], REGISTER_A_OUT[1], REGISTER_A_OUT[2], REGISTER_A_OUT[3], 
  NOT_IN_USE[0]);
  
 LOGIC_74HC161 Register_B (RESET, CLOCK, 
  REGISTER_IN[0], REGISTER_IN[1], REGISTER_IN[2], REGISTER_IN[3], 
  GND, LOAD_1, GND, 
  REGISTER_B_OUT[0], REGISTER_B_OUT[1], REGISTER_B_OUT[2], REGISTER_B_OUT[3], 
  NOT_IN_USE[1]);
  
 LOGIC_74HC161 Register_C (RESET, CLOCK, 
  REGISTER_IN[0], REGISTER_IN[1], REGISTER_IN[2], REGISTER_IN[3], 
  GND, LOAD_2, GND, 
  REGISTER_C_OUT[0], REGISTER_C_OUT[1], REGISTER_C_OUT[2], REGISTER_C_OUT[3], 
  NOT_IN_USE[2]);
  
 LOGIC_74HC161 Register_D (RESET, CLOCK, 
  REGISTER_IN[0], REGISTER_IN[1], REGISTER_IN[2], REGISTER_IN[3], 
  Vcc, LOAD_3, Vcc, 
  REGISTER_D_OUT[0], REGISTER_D_OUT[1], REGISTER_D_OUT[2], REGISTER_D_OUT[3], 
  NOT_IN_USE[3]);
 
 LOGIC_74HC153 Register_Selector_0 (SELECT_A, SELECT_B, GND, GND, 
  REGISTER_A_OUT[0], REGISTER_B_OUT[0], REGISTER_C_OUT[0], GND, 
  REGISTER_A_OUT[1], REGISTER_B_OUT[1], REGISTER_C_OUT[1], GND,
  ALU_IN_A[0], ALU_IN_A[1]);
  
 LOGIC_74HC153 Register_Selector_1 (SELECT_A, SELECT_B, GND, GND, 
  REGISTER_A_OUT[2], REGISTER_B_OUT[2], REGISTER_C_OUT[2], GND, 
  REGISTER_A_OUT[3], REGISTER_B_OUT[3], REGISTER_C_OUT[3], GND, 
  ALU_IN_A[2], ALU_IN_A[3]);
 
 LOGIC_74HC283 ALU (GND, 
  ALU_IN_A[0], ALU_IN_A[1], ALU_IN_A[2], ALU_IN_A[3], 
  ALU_IN_B[0], ALU_IN_B[1], ALU_IN_B[2], ALU_IN_B[3], 
  REGISTER_IN[0], REGISTER_IN[1], REGISTER_IN[2], REGISTER_IN[3], 
  CARRY_OUT);
 
 LOGIC_74HC74 C_Flag (RESET, CARRY_OUT, CLOCK, Vcc, C_FLAG, C_FLAG_BAR, 
  GND, GND, GND, GND, NOT_IN_USE[4], NOT_IN_USE[5]);
 
endmodule

完成！！！！！！！！！

実際に動かしてみよう！
テストベンチは次の通り。

module processor_test;
 reg  RESET, CLOCK;
 reg  [3:0] INPUT;
 wire [3:0] OUTPUT;
 
 Processor processor(RESET, CLOCK, INPUT, OUTPUT);
 
 initial begin
  $dumpfile("processor_test.vcd");
  $dumpvars(0, processor_test);
  $monitor ("%t: CLOCK = %b, RESET = %b, INPUT = %b%b%b%b, OUTPUT = %b%b%b%b", 
   $time, CLOCK, RESET, 
   INPUT[3], INPUT[2], INPUT[1], INPUT[0], 
   OUTPUT[3], OUTPUT[2], OUTPUT[1], OUTPUT[0]);
  
  CLOCK = 0;
  RESET = 1;
  INPUT = 4'b0000;
  #400 $finish;
 end
 
 always #1
  CLOCK = ~CLOCK;
endmodule

LEDチカチカとラーメンタイマーそれぞれ動いたでしょうか？
これにて一段落。

次回予告

次回は実際にFPGAに実装してみたいと思います。（多分）

Amazon.co.jp - 渡波郁「CPUの創りかた」毎日コミュニケーションズ (2003)

2012年9月13日木曜日

１．74HC283

というわけで4bit Full-Adder。
P信号，G信号を使ってCarry-LookaheadなAdderにするって奴はテストによく出るよ！

module LOGIC_74HC283(CIN, A1, A2, A3, A4, B1, B2, B3, B4, S1, S2, S3, S4, COUT);
 input CIN, A1, A2, A3, A4, B1, B2, B3, B4;
 output S1, S2, S3, S4, COUT;
 
 wire [3:0] G;
 wire [3:0] P;
 wire [3:0] C;
 
 assign G[0] = ~(A1 & B1);
 assign G[1] = ~(A2 & B2);
 assign G[2] = ~(A3 & B3);
 assign G[3] = ~(A4 & B4);
 
 assign P[0] = ~(A1 | B1);
 assign P[1] = ~(A2 | B2);
 assign P[2] = ~(A3 | B3);
 assign P[3] = ~(A4 | B4);
 
 assign C[0] = CIN;
 assign C[1] = ~((~CIN & G[0]) | P[0]);
 assign C[2] = ~((~CIN & G[0] & G[1]) | (G[1] & P[0]) | P[1]);
 assign C[3] = ~((~CIN & G[0] & G[1] & G[2]) | (G[1] & G[2] & P[0]) | (G[2] & P[1]) | P[2]);
 assign COUT = ~((~CIN & G[0] & G[1] & G[2] & G[3]) | (G[1] & G[2] & G[3] & P[0]) | (G[2] & G[3] & P[1]) | (G[3] & P[2]) | P[3]);
 
 assign S1 = (C[0] ^ (~P[0] & G[0]));
 assign S2 = (C[1] ^ (~P[1] & G[1]));
 assign S3 = (C[2] ^ (~P[2] & G[2]));
 assign S4 = (C[3] ^ (~P[3] & G[3]));
endmodule

テストベンチはこんな感じ？

module logic_74hc283_test;
 reg  CIN;
 reg  [3:0] A;
 reg  [3:0] B;
 wire [3:0] S;
 wire COUT;
 
 LOGIC_74HC283 logic_74hc283(CIN, 
  A[0], A[1], A[2], A[3], 
  B[0], B[1], B[2], B[3], 
  S[0], S[1], S[2], S[3], 
  COUT);
 
 initial begin
  $dumpfile("logic_74hc283_test.vcd");
  $dumpvars(0, logic_74hc283_test);
  $monitor ("%t: A = %d, B = %d, CIN = %b, S = %d, COUT = %b", 
   $time, A, B, CIN, S, COUT);
   
   CIN = 0;
   A = 0; B = 0;
  #10 A = 1; B = 1;
  #10 A = 1; B = 2;
  #10 A = 2; B = 3;
  #10 A = 4; B = 2;
  #10 A = 4; B = 3;
  #10 A = 4; B = 5;
  #10 A = 8; B = 10;
  #10 A = 6; B = 7;
  #10 A = 12; B = 9;
  #10 $finish;
 end
endmodule

番外編

２．74HC181

物理的になくても，Verilogで書くことならできちゃうんです。簡単にね！

回路図はこんな感じです。

まったく，わけがわからないよ。
でも，なんとなーく，左右にわかれてますよね？よね？

色をつけるとわかりやすい！
それじゃあ元気よく実装しましょう！（半泣）

module LOGIC_74HC181(CIN, S0, S1, S2, S3, M, A0, A1, A2, A3, B0, B1, B2, B3, F0, F1, F2, F3, COUT, COMP, G, P);
 input CIN, S0, S1, S2, S3, M, A0, A1, A2, A3, B0, B1, B2, B3;
 output F0, F1, F2, F3, COUT, COMP, G, P;
 
 wire [3:0] D;
 wire [3:0] E;
 wire [3:0] F;
 
 assign D[0] = ~((~B0 & S1) | (B0 & S0) | A0);
 assign D[1] = ~((~B1 & S1) | (B1 & S0) | A1);
 assign D[2] = ~((~B2 & S1) | (B2 & S0) | A2);
 assign D[3] = ~((~B3 & S1) | (B3 & S0) | A3);
 assign E[0] = ~((B0 & S3 & A0) | (A0 & S2 & ~B0));
 assign E[1] = ~((B1 & S3 & A1) | (A1 & S2 & ~B1));
 assign E[2] = ~((B2 & S3 & A2) | (A2 & S2 & ~B2));
 assign E[3] = ~((B3 & S3 & A3) | (A3 & S2 & ~B3));
 
 assign F0 = ((D[0] ^ E[0]) ^ ~(CIN & ~M));
 assign F1 = ((D[1] ^ E[1]) ^ ~((CIN & E[0] & ~M) | (D[0] & ~M)));
 assign F2 = ((D[2] ^ E[2]) ^ ~((CIN & E[0] & E[1] & ~M) | (E[1] & D[0] & ~M) | (D[1] & ~M)));
 assign F3 = ((D[3] ^ E[3]) ^ ~((CIN & E[0] & E[1] & E[2] & ~M) | (E[1] & E[2] & D[0] & ~M) | (E[2] & D[1] & ~M) | (D[2] & ~M)));
 
 assign P = ~(E[0] & E[1] & E[2] & E[3]);
 assign G = ~(D[3] | (E[3] & D[2]) | (E[3] & E[2] & D[1]) | (E[3] & E[2] & E[1] & D[0]));
 assign COMP = F0 & F1 & F2 & F3;
 assign COUT = ~G | (E[3] & E[2] & E[1] & E[0] & CIN);
endmodule

網羅テストを実行するのはさすがに無理だと思うので，適当にテストベンチ書いてテストしてみるといいよ！
あと，このICはActive-LowとActive-Highで挙動が違うから注意してね！
詳しいことはデータシート読め！

番外編終わり

３．74HC74

フラグレジスタ用のフリップフロップ回路です。
奥さん！二個入りニコニコ大特価だよ！

module LOGIC_74HC74(CLR1, D1, CK1, PR1, Q1, Qb1, CLR2, D2, CK2, PR2, Q2, Qb2);
 input CLR1, D1, CK1, PR1, CLR2, D2, CK2, PR2;
 output Q1, Qb1, Q2, Qb2;
 reg  Q1, Q2;
 
 assign Qb1 = ~Q1;
 assign Qb2 = ~Q2;
 
 initial begin
  Q1 <= 1'b0;
  Q2 <= 1'b0;
 end
 
 always @(CLR1, CK1, PR1, CLR2, CK2, PR2) begin
  if(~CLR1) begin
   Q1 <= 1'b0;
  end else if(~PR1) begin
   Q1 <= 1'b1;
  end else if(CK1) begin
   Q1 <= D1;
  end
  
  if(~CLR2) begin
   Q2 <= 1'b0;
  end else if(~PR2) begin
   Q2 <= 1'b1;
  end else if(CK2) begin
   Q2 <= D2;
  end
 end
endmodule

テストベンチはこんな感じ？

module logic_74hc74_test;
 reg  CLR1, D1, CK1, PR1, CLR2, D2, CK2, PR2;
 wire Q1, Qb1, Q2, Qb2;
 
 LOGIC_74HC74 logic_74hc74(CLR1, D1, CK1, PR1, Q1, Qb1, CLR2, D2, CK2, PR2, Q2, Qb2);
 
 initial begin
  $dumpfile("logic_74hc74_test.vcd");
  $dumpvars(0, logic_74hc74_test);
  $monitor ("%t: CK1 = %b, (CLR1, PR1) = (%b, %b), D1 = %b, Q1 = %b | CK2 = %b, (CLR2, PR2) = (%b, %b), D2 = %b, Q2 = %b",
   $time, CK1, CLR1, PR1, D1, Q1, CK2, CLR2, PR2, D2, Q2);
  
  CK1 = 0; CK2 = 0;
  CLR1 = 1; CLR2 = 1;
  PR1 = 1; PR2 = 1;
  D1 = 0;  D2 = 0;
  
  #3 D1 = 1; D2 = 1;
  #1 D1 = 0; D2 = 0;
  #30 $finish;
 end
 
 always #3 CK1 = ~CK1;
 always #5 CK2 = ~CK2;
endmodule

４．8.2節までの回路

というわけで，8.2節までの回路（つまり，I/Oポートなし）を書いてみます。

module CHAPTER_8_2(CLOCK, RESET, SELECT_A, SELECT_B, LOAD_0, LOAD_1, LOAD_2, LOAD_3, ROM_DATA, ROM_ADDRESS);
 input CLOCK, RESET;
 input SELECT_A, SELECT_B, LOAD_0, LOAD_1, LOAD_2, LOAD_3;
 input [7:0] ROM_DATA;
 output [3:0] ROM_ADDRESS;
 
 reg Vcc = 1'b1;
 reg GND = 1'b0;
 wire [6:0] NOT_IN_USE;
 
 wire [3:0] REGISTER_IN;
 
 wire [3:0] REGISTER_A_OUT;
 wire [3:0] REGISTER_B_OUT;
 wire [3:0] REGISTER_C_OUT;
 wire [3:0] REGISTER_D_OUT;
 
 wire [3:0] ALU_IN_A;
 wire [3:0] ALU_IN_B;
 wire CARRY_OUT, C_FLAG;
 
 wire [3:0] OPERATION_CODE;
 wire [3:0] IMEEDIATE_DATA;
 
 assign ROM_ADDRESS = REGISTER_D_OUT;
 assign OPERATION_CODE = ROM_DATA[7:4];
 assign IMEEDIATE_DATA = ROM_DATA[3:0];
 assign ALU_IN_B = IMEEDIATE_DATA;
 
 LOGIC_74HC161 Register_A (RESET, CLOCK, 
  REGISTER_IN[0], REGISTER_IN[1], REGISTER_IN[2], REGISTER_IN[3], 
  GND, LOAD_0, GND, 
  REGISTER_A_OUT[0], REGISTER_A_OUT[1], REGISTER_A_OUT[2], REGISTER_A_OUT[3], 
  NOT_IN_USE[0]);
 
 LOGIC_74HC161 Register_B (RESET, CLOCK, 
  REGISTER_IN[0], REGISTER_IN[1], REGISTER_IN[2], REGISTER_IN[3], 
  GND, LOAD_1, GND, 
  REGISTER_B_OUT[0], REGISTER_B_OUT[1], REGISTER_B_OUT[2], REGISTER_B_OUT[3], 
  NOT_IN_USE[1]);
 
 LOGIC_74HC161 Register_C (RESET, CLOCK, 
  REGISTER_IN[0], REGISTER_IN[1], REGISTER_IN[2], REGISTER_IN[3], 
  GND, LOAD_2, GND, 
  REGISTER_C_OUT[0], REGISTER_C_OUT[1], REGISTER_C_OUT[2], REGISTER_C_OUT[3], 
  NOT_IN_USE[2]);
 
 LOGIC_74HC161 Register_D (RESET, CLOCK, 
  REGISTER_IN[0], REGISTER_IN[1], REGISTER_IN[2], REGISTER_IN[3], 
  Vcc, LOAD_3, Vcc, 
  REGISTER_D_OUT[0], REGISTER_D_OUT[1], REGISTER_D_OUT[2], REGISTER_D_OUT[3], 
  NOT_IN_USE[3]);
 
 LOGIC_74HC153 Register_Selector_0 (SELECT_A, SELECT_B, GND, GND, 
  REGISTER_A_OUT[0], REGISTER_B_OUT[0], REGISTER_C_OUT[0], GND, 
  REGISTER_A_OUT[1], REGISTER_B_OUT[1], REGISTER_C_OUT[1], GND,
  ALU_IN_A[0], ALU_IN_A[1]);
 
 LOGIC_74HC153 Register_Selector_1 (SELECT_A, SELECT_B, GND, GND, 
  REGISTER_A_OUT[2], REGISTER_B_OUT[2], REGISTER_C_OUT[2], GND, 
  REGISTER_A_OUT[3], REGISTER_B_OUT[3], REGISTER_C_OUT[3], GND, 
  ALU_IN_A[2], ALU_IN_A[3]);
 
 LOGIC_74HC283 ALU (GND, 
  ALU_IN_A[0], ALU_IN_A[1], ALU_IN_A[2], ALU_IN_A[3], 
  ALU_IN_B[0], ALU_IN_B[1], ALU_IN_B[2], ALU_IN_B[3], 
  REGISTER_IN[0], REGISTER_IN[1], REGISTER_IN[2], REGISTER_IN[3], 
  CARRY_OUT);
 
 LOGIC_74HC74 C_Flag (RESET, CARRY_OUT, CLOCK, Vcc, C_FLAG, NOT_IN_USE[4], 
  GND, GND, GND, GND, NOT_IN_USE[5], NOT_IN_USE[6]);
endmodule

だいぶCPUっぽくなってきましたね！

４．8.3節までの回路

どんどんいってみましょう！
8.3節までの回路（つまり，I/Oポートつき）を書いてみます。

module CHAPTER_8_3(CLOCK, RESET, SELECT_A, SELECT_B, LOAD_0, LOAD_1, LOAD_2, LOAD_3, ROM_DATA, ROM_ADDRESS);
 input CLOCK, RESET;
 input SELECT_A, SELECT_B, LOAD_0, LOAD_1, LOAD_2, LOAD_3;
 input [7:0] ROM_DATA;
 output [3:0] ROM_ADDRESS;
 
 reg Vcc = 1'b1;
 reg GND = 1'b0;
 wire [6:0] NOT_IN_USE;
 
 wire [3:0] REGISTER_IN;
 
 wire [3:0] REGISTER_A_OUT;
 wire [3:0] REGISTER_B_OUT;
 wire [3:0] REGISTER_C_OUT;
 wire [3:0] REGISTER_D_OUT;
 
 wire [3:0] ALU_IN_A;
 wire [3:0] ALU_IN_B;
 wire CARRY_OUT, C_FLAG;
 
 wire [3:0] OPERATION_CODE;
 wire [3:0] IMEEDIATE_DATA;
 
 assign ROM_ADDRESS = REGISTER_D_OUT;
 assign OPERATION_CODE = ROM_DATA[7:4];
 assign IMEEDIATE_DATA = ROM_DATA[3:0];
 assign ALU_IN_B = IMEEDIATE_DATA;
 assign OUTPUT = REGISTER_C_OUT;
 
 LOGIC_74HC161 Register_A (RESET, CLOCK, 
  REGISTER_IN[0], REGISTER_IN[1], REGISTER_IN[2], REGISTER_IN[3], 
  GND, LOAD_0, GND, 
  REGISTER_A_OUT[0], REGISTER_A_OUT[1], REGISTER_A_OUT[2], REGISTER_A_OUT[3], 
  NOT_IN_USE[0]);
  
 LOGIC_74HC161 Register_B (RESET, CLOCK, 
  REGISTER_IN[0], REGISTER_IN[1], REGISTER_IN[2], REGISTER_IN[3], 
  GND, LOAD_1, GND, 
  REGISTER_B_OUT[0], REGISTER_B_OUT[1], REGISTER_B_OUT[2], REGISTER_B_OUT[3], 
  NOT_IN_USE[1]);
  
 LOGIC_74HC161 Register_C (RESET, CLOCK, 
  REGISTER_IN[0], REGISTER_IN[1], REGISTER_IN[2], REGISTER_IN[3], 
  GND, LOAD_2, GND, 
  REGISTER_C_OUT[0], REGISTER_C_OUT[1], REGISTER_C_OUT[2], REGISTER_C_OUT[3], 
  NOT_IN_USE[2]);
  
 LOGIC_74HC161 Register_D (RESET, CLOCK, 
  REGISTER_IN[0], REGISTER_IN[1], REGISTER_IN[2], REGISTER_IN[3], 
  Vcc, LOAD_3, Vcc, 
  REGISTER_D_OUT[0], REGISTER_D_OUT[1], REGISTER_D_OUT[2], REGISTER_D_OUT[3], 
  NOT_IN_USE[3]);
 
 LOGIC_74HC153 Register_Selector_0 (SELECT_A, SELECT_B, GND, GND, 
  REGISTER_A_OUT[0], REGISTER_B_OUT[0], REGISTER_C_OUT[0], GND, 
  REGISTER_A_OUT[1], REGISTER_B_OUT[1], REGISTER_C_OUT[1], GND,
  ALU_IN_A[0], ALU_IN_A[1]);
  
 LOGIC_74HC153 Register_Selector_1 (SELECT_A, SELECT_B, GND, GND, 
  REGISTER_A_OUT[2], REGISTER_B_OUT[2], REGISTER_C_OUT[2], GND, 
  REGISTER_A_OUT[3], REGISTER_B_OUT[3], REGISTER_C_OUT[3], GND, 
  ALU_IN_A[2], ALU_IN_A[3]);
 
 LOGIC_74HC283 ALU (GND, 
  ALU_IN_A[0], ALU_IN_A[1], ALU_IN_A[2], ALU_IN_A[3], 
  ALU_IN_B[0], ALU_IN_B[1], ALU_IN_B[2], ALU_IN_B[3], 
  REGISTER_IN[0], REGISTER_IN[1], REGISTER_IN[2], REGISTER_IN[3], 
  CARRY_OUT);
 
 LOGIC_74HC74 C_Flag (RESET, CARRY_OUT, CLOCK, Vcc, C_FLAG, NOT_IN_USE[4], 
  GND, GND, GND, GND, NOT_IN_USE[5], NOT_IN_USE[6]);
endmodule

次回予告

ついにシミュレーション編最終回！
命令デコーダを完成させます！
そして，全てを結合させCPU全体の完成です！

乞うご期待！！！

Amazon.co.jp - 渡波郁「CPUの創りかた」毎日コミュニケーションズ (2003)

2012年9月6日木曜日

週刊 TD4をFPGAで創る第3号「レジスタを創る」

第７章からです。
え，第６章？　ちゃんと読んでおいてね！

１．74HC153

４チャネルのデータセレクタですね。
真理表はデータシートでも参照してくださいな。

module LOGIC_74HC153(A, B, G1, G2, C10, C11, C12, C13, C20, C21, C22, C23, Y1, Y2);
 input A, B, G1, G2, C10, C11, C12, C13, C20, C21, C22, C23;
 output Y1, Y2;
 
 wire [3:0] temp [0:1];
 
 assign temp[0][0] = C10 & (~B) & (~A) & (~G1);
 assign temp[0][1] = C11 & (~B) & A & (~G1);
 assign temp[0][2] = C12 & B & (~A) & (~G1);
 assign temp[0][3] = C13 & B & A & (~G1);
 
 assign temp[1][0] = C20 & (~B) & (~A) & (~G2);
 assign temp[1][1] = C21 & (~B) & A & (~G2);
 assign temp[1][2] = C22 & B & (~A) & (~G2);
 assign temp[1][3] = C23 & B & A & (~G2);
 
 assign Y1 = temp[0][0] | temp[0][1] | temp[0][2] | temp[0][3];
 assign Y2 = temp[1][0] | temp[1][1] | temp[1][2] | temp[1][3];
endmodule

テストベンチはこんな感じ？

module logic_74hc153_test;
 reg  A, B;
 reg  [1:0] G;
 reg  [3:0] C0;
 reg  [3:0] C1;
 wire [1:0] Y;
 
 LOGIC_74HC153 logic_74hc153(A, B, G[0], G[1], 
  C0[0], C0[1], C0[2], C0[3], C1[0], C1[1], C1[2], C1[3], Y[0], Y[1]);
 
 initial begin
  $dumpfile("logic_74hc153_test.vcd");
  $dumpvars(0, logic_74hc153_test);
  $monitor ("%t: (B, A) = (%b, %b), G = (%b, %b), C0 = %b%b%b%b, C1 = %b%b%b%b, Y = (%b, %b)",
   $time, B, A, G[0], G[1], C0[0], C0[1], C0[2], C0[3], C1[0], C1[1], C1[2], C1[3], Y[0], Y[1]);
   
   G = 3;
   B = 0; A = 0;
   C0 = 4'b1100;
   C1 = 4'b0101;
  #10 B = 0; A = 0;
  #10 B = 0; A = 1;
  #10 B = 1; A = 0;
  #10 B = 1; A = 1;
  #10 $finish;
 end
endmodule

２．74HC161

４ビットカウンタです。
こいつをレジスタとして使います。

module LOGIC_74HC161(CLR, CK, A, B, C, D, ENP, LOAD, ENT, QA, QB, QC, QD, CO);
 input CLR, CK, A, B, C, D, ENP, LOAD, ENT;
 output QA, QB, QC, QD, CO;
 
 wire [3:0] DATA = {D, C, B, A};
 reg  [3:0] FLIPFLOP;
 
 assign QA = FLIPFLOP[0];
 assign QB = FLIPFLOP[1];
 assign QC = FLIPFLOP[2];
 assign QD = FLIPFLOP[3];
 assign CO = ENT & QA & QB & QC & QD;
 
 initial begin
  FLIPFLOP <= 4'b0000;
 end
 
 always @(CLR or posedge CK) begin
  if(~CLR) begin
   FLIPFLOP <= 4'b0000;
  end
  else if(CK) begin
   if(~LOAD) begin
    FLIPFLOP <= DATA;
   end else if(ENP & ENT) begin
    if(FLIPFLOP == 4'b1111) begin
     FLIPFLOP <= 4'b0000;
    end else begin
     FLIPFLOP <= FLIPFLOP + 1;
    end
   end
  end
 end
endmodule

テストベンチはこんな感じ？

module logic_74hc161_test;
 reg  CLR, CK, ENP, LOAD, ENT;
 reg  [3:0] DATA;
 wire A, B, C, D, QA, QB, QC, QD, CO;
 wire [3:0] Q;
 
 assign A = DATA[0];
 assign B = DATA[1];
 assign C = DATA[2];
 assign D = DATA[3];
 assign Q = {QD, QC, QB, QA};
 
 LOGIC_74HC161 logic_74hc161(CLR, CK, A, B, C, D, ENP, LOAD, ENT, QA, QB, QC, QD, CO);
 
 initial begin
  $dumpfile("a.vcd");
  $dumpvars(0, logic_74hc161_test);
  $monitor ("%t: CK = %b, (CLR, LOAD, ENP, ENT) = (%b %b %b %b), DATA = %d(%b%b%b%b), Q = %d(%b%b%b%b), CO = %b",
   $time, CK, CLR, LOAD, ENP, ENT, DATA, D, C, B, A, Q, QD, QC, QB, QA, CO);
  
   CK = 0;
   CLR = 1; ENP = 1; LOAD = 1; ENT = 1;
   DATA = 0;
  #60 
  #10  CLR = 0;
  #10  CLR = 1;
  #60  DATA = 0;
  #10  DATA = 7; LOAD = 0;
  #10  DATA = 0; LOAD = 1;
  #10  DATA = 0;
  #40  ENP = 0;
  #30  ENP = 1;
  #210
  #10  $finish;
 end
 
 always #10 CK = ~CK;
endmodule

３．第７章の章末の回路

第７章の章末の回路を実装してみましょう！

module CHAPTER_7(CLOCK, RESET, SELECT_A, SELECT_B, LOAD_0, LOAD_1, LOAD_2, LOAD_3);
 input CLOCK, RESET;
 input SELECT_A, SELECT_B, LOAD_0, LOAD_1, LOAD_2, LOAD_3;
 
 reg GND = 1'b0;
 
 wire [3:0] REGISTER_IN;
 
 wire [3:0] REGISTER_A_OUT;
 wire [3:0] REGISTER_B_OUT;
 wire [3:0] REGISTER_C_OUT;
 wire [3:0] REGISTER_D_OUT;
 
 wire [3:0] NOT_IN_USE;
 
 LOGIC_74HC161 Register_A (RESET, CLOCK, 
  REGISTER_IN[0], REGISTER_IN[1], REGISTER_IN[2], REGISTER_IN[3], 
  GND, LOAD_0, GND, 
  REGISTER_A_OUT[0], REGISTER_A_OUT[1], REGISTER_A_OUT[2], REGISTER_A_OUT[3], 
  NOT_IN_USE[0]);
 
 LOGIC_74HC161 Register_B (RESET, CLOCK, 
  REGISTER_IN[0], REGISTER_IN[1], REGISTER_IN[2], REGISTER_IN[3], 
  GND, LOAD_0, GND, 
  REGISTER_B_OUT[0], REGISTER_B_OUT[1], REGISTER_B_OUT[2], REGISTER_B_OUT[3], 
  NOT_IN_USE[1]);
 
 LOGIC_74HC161 Register_C (RESET, CLOCK, 
  REGISTER_IN[0], REGISTER_IN[1], REGISTER_IN[2], REGISTER_IN[3], 
  GND, LOAD_0, GND, 
  REGISTER_C_OUT[0], REGISTER_C_OUT[1], REGISTER_C_OUT[2], REGISTER_C_OUT[3], 
  NOT_IN_USE[2]);
 
 LOGIC_74HC161 Register_D (RESET, CLOCK, 
  REGISTER_IN[0], REGISTER_IN[1], REGISTER_IN[2], REGISTER_IN[3], 
  GND, LOAD_0, GND, 
  REGISTER_D_OUT[0], REGISTER_D_OUT[1], REGISTER_D_OUT[2], REGISTER_D_OUT[3], 
  NOT_IN_USE[3]);
 
 LOGIC_74HC153 Register_Selector_0 (SELECT_A, SELECT_B, GND, GND, 
  REGISTER_A_OUT[0], REGISTER_B_OUT[0], REGISTER_C_OUT[0], REGISTER_D_OUT[0], 
  REGISTER_A_OUT[1], REGISTER_B_OUT[1], REGISTER_C_OUT[1], REGISTER_D_OUT[1],
  REGISTER_IN[0], REGISTER_IN[1]);
 
 LOGIC_74HC153 Register_Selector_1 (SELECT_A, SELECT_B, GND, GND, 
  REGISTER_A_OUT[2], REGISTER_B_OUT[2], REGISTER_C_OUT[2], REGISTER_D_OUT[2], 
  REGISTER_A_OUT[3], REGISTER_B_OUT[3], REGISTER_C_OUT[3], REGISTER_D_OUT[3], 
  REGISTER_IN[2], REGISTER_IN[3]);
endmodule

こいつは，outputがないのでテストのしようがないですねぇ。。。
まぁ，REGISTER_A_OUTとかを無理やり出力に引っ張ればいいんですけど。
面倒なんで，テストしたい人はやって見るといいと思います。

次回予告

次はいよいよALUだよ！
演算回路だよ！
CPUっぽいよ！

Amazon.co.jp - 渡波郁「CPUの創りかた」毎日コミュニケーションズ (2003)

2012年8月30日木曜日

週刊 TD4をFPGAで創る第２号「ROMを創る」

さぁ，実装するでございます。

第５章からです。
え，ROMって作れないんじゃなかったのって気がしますが，
実はこの時点では機械スイッチを使ってることをすっかり忘れていてまして。
74HC540と74HC154作っちゃたので載せます。

下の方にある「３．ROM」の部分までは読み飛ばしてOKですよ？

１．74HC540

バスバッファ８個入り！
Gの値によってはハイ・インピーダンスになるのですが，その場合は「1'hz」と書きます。

module LOGIC_74HC540(G1, G2, A1, A2, A3, A4, A5, A6, A7, A8, Y1, Y2, Y3, Y4, Y5, Y6, Y7, Y8);
	input	G1, G2;
	input	A1, A2, A3, A4, A5, A6, A7, A8;
	output	Y1, Y2, Y3, Y4, Y5, Y6, Y7, Y8;
	
	wire	G = G1 | G2;
	
	assign	Y1 = (G == 1'b0) ? ~A1 : 1'hz;
	assign	Y2 = (G == 1'b0) ? ~A2 : 1'hz;
	assign	Y3 = (G == 1'b0) ? ~A3 : 1'hz;
	assign	Y4 = (G == 1'b0) ? ~A4 : 1'hz;
	assign	Y5 = (G == 1'b0) ? ~A5 : 1'hz;
	assign	Y6 = (G == 1'b0) ? ~A6 : 1'hz;
	assign	Y7 = (G == 1'b0) ? ~A7 : 1'hz;
	assign	Y8 = (G == 1'b0) ? ~A8 : 1'hz;
endmodule

テストベンチはこんな感じ？

module logic_74hc540_test;
	reg	[1:0] G;
	reg	[7:0] A;
	wire	[7:0] Y;
	
	LOGIC_74HC540	logic_74hc540(G[0], G[1], 
		A[0], A[1], A[2], A[3], A[4], A[5], A[6], A[7], 
		Y[0], Y[1], Y[2], Y[3], Y[4], Y[5], Y[6], Y[7]);
	
	initial begin
		$dumpfile("logic_74hc540_test.vcd");
		$dumpvars(0, logic_74hc540_test);
		$monitor ("%t: (G[1], G[0]) = (%b, %b), A = %b%b%b%b%b%b%b%b, Y = %b%b%b%b%b%b%b%b",
			$time, G[0], G[1], 
			A[7], A[6], A[5], A[4], A[3], A[2], A[1], A[0], 
			Y[7], Y[6], Y[5], Y[4], Y[3], Y[2], Y[1], Y[0]);
			

			A = 8'b00000000;	G = 0;
		#10	A = 8'b10101010;
		#10	A = 8'b11001100;
		#10	A = 8'b11110000;
		#10	A = 8'b00111100;
		#10	A = 8'b00000000;	G = 1;
		#10	A = 8'b10101010;	
		#10	A = 8'b11001100;
		#10	A = 8'b11110000;
		#10	A = 8'b00111100;
		#10	A = 8'b00000000;	G = 2;
		#10	A = 8'b10101010;	
		#10	A = 8'b11001100;
		#10	A = 8'b11110000;
		#10	A = 8'b00111100;
		#10	A = 8'b00000000;	G = 3;
		#10	A = 8'b10101010;	
		#10	A = 8'b11001100;
		#10	A = 8'b11110000;
		#10	A = 8'b00111100;
		#10	$finish;
	end
endmodule

２．74HC154

４ビットの２進数を１６ビットの信号線にバラします。
ギョーカイヨーゴでは4-16デコーダって言います。

module LOGIC_74HC154(G1, G2, A, B, C, D, Y0, Y1, Y2, Y3, Y4, Y5, Y6, Y7, Y8, Y9, Y10, Y11, Y12, Y13, Y14, Y15);
	input	G1, G2, A, B, C, D;
	output	Y0, Y1, Y2, Y3, Y4, Y5, Y6, Y7, Y8, Y9, Y10, Y11, Y12, Y13, Y14, Y15;
	wire	G = (~G1) & (~G2);
	
	assign	Y0  = ~(G & ~A & ~B & ~C & ~D);
	assign	Y1  = ~(G &  A & ~B & ~C & ~D);
	assign	Y2  = ~(G & ~A &  B & ~C & ~D);
	assign	Y3  = ~(G &  A &  B & ~C & ~D);
	assign	Y4  = ~(G & ~A & ~B &  C & ~D);
	assign	Y5  = ~(G &  A & ~B &  C & ~D);
	assign	Y6  = ~(G & ~A &  B &  C & ~D);
	assign	Y7  = ~(G &  A &  B &  C & ~D);
	assign	Y8  = ~(G & ~A & ~B & ~C &  D);
	assign	Y9  = ~(G &  A & ~B & ~C &  D);
	assign	Y10 = ~(G & ~A &  B & ~C &  D);
	assign	Y11 = ~(G &  A &  B & ~C &  D);
	assign	Y12 = ~(G & ~A & ~B &  C &  D);
	assign	Y13 = ~(G &  A & ~B &  C &  D);
	assign	Y14 = ~(G & ~A &  B &  C &  D);
	assign	Y15 = ~(G &  A &  B &  C &  D);
endmodule

テストベンチはこんな感じ？

module logic_74hc154_test;
	reg		[1:0] G;
	reg		[3:0] A;
	wire	[15:0] Y;
	
	LOGIC_74HC154	logic_74hc154(G[0], G[1], A[0], A[1], A[2], A[3], 
		Y[0], Y[1], Y[2], Y[3], Y[4], Y[5], Y[6], Y[7], 
		Y[8], Y[9], Y[10], Y[11], Y[12], Y[13], Y[14], Y[15]);
	
	initial begin
		$dumpfile("logic_74hc154_test.vcd");
		$dumpvars(0, logic_74hc154_test);
		$monitor ("%t: G = %b%b, A = %b%b%b%b, Y = %b%b%b%b%b%b%b%b%b%b%b%b%b%b%b%b",
			$time, G[1], G[0], A[3], A[2], A[1], A[0], 
			Y[15], Y[14], Y[13], Y[12], Y[11], Y[10], Y[9], Y[8], 
			Y[7], Y[6], Y[5], Y[4], Y[3], Y[2], Y[1], Y[0]);
			
			A = 4'b0000;	G = 0;
		#10	A = 4'b0001;
		#10	A = 4'b0011;
		#10	A = 4'b0100;
		#10	A = 4'b0101;
		#10	A = 4'b0110;
		#10	A = 4'b0111;
		#10	A = 4'b1000;
		#10	A = 4'b1001;
		#10	A = 4'b1011;
		#10	A = 4'b1100;
		#10	A = 4'b1101;
		#10	A = 4'b1110;
		#10	A = 4'b1111;
		#10	A = 4'b0000;	G = 1;
		#10	A = 4'b0001;
		#10	A = 4'b0011;
		#10	A = 4'b0100;
		#10	A = 4'b0101;
		#10	A = 4'b0110;
		#10	A = 4'b0111;
		#10	A = 4'b1000;
		#10	A = 4'b1001;
		#10	A = 4'b1011;
		#10	A = 4'b1100;
		#10	A = 4'b1101;
		#10	A = 4'b1110;
		#10	A = 4'b1111;
		#10	A = 4'b0000;	G = 2;
		#10	A = 4'b0001;
		#10	A = 4'b0011;
		#10	A = 4'b0100;
		#10	A = 4'b0101;
		#10	A = 4'b0110;
		#10	A = 4'b0111;
		#10	A = 4'b1000;
		#10	A = 4'b1001;
		#10	A = 4'b1011;
		#10	A = 4'b1100;
		#10	A = 4'b1101;
		#10	A = 4'b1110;
		#10	A = 4'b1111;
		#10	A = 4'b0000;	G = 3;
		#10	A = 4'b0001;
		#10	A = 4'b0011;
		#10	A = 4'b0100;
		#10	A = 4'b0101;
		#10	A = 4'b0110;
		#10	A = 4'b0111;
		#10	A = 4'b1000;
		#10	A = 4'b1001;
		#10	A = 4'b1011;
		#10	A = 4'b1100;
		#10	A = 4'b1101;
		#10	A = 4'b1110;
		#10	A = 4'b1111;
		#10	$finish;
	end

ここからは本題です。

３．ROM

さて，ここでROMモジュールを作ろうとして頓挫したわけです。

で，結局Verilog様の偉大なる力に頼ることにします。
今だけはVerilogのことを偉大なる指導者と読んでもバチは当たらない！

こんな感じになりました。
実際に本に乗っているコードをのっけてあります。
コメントアウトしたりしながら楽しんでね！

module ROM_16WORD(ROM_ADDRESS, ROM_DATA);
	input	[3:0] ROM_ADDRESS;
	output	[7:0] ROM_DATA;
	
	reg	[7:0] ROM [0:15];
	
	assign	ROM_DATA = ROM[ROM_ADDRESS];
	
	initial begin
		// BLANK
		/*
		ROM[0]  <= 8'b00000000;	// NOP
		ROM[1]  <= 8'b00000000;	// NOP
		ROM[2]  <= 8'b00000000;	// NOP
		ROM[3]  <= 8'b00000000;	// NOP
		ROM[4]  <= 8'b00000000;	// NOP
		ROM[5]  <= 8'b00000000;	// NOP
		ROM[6]  <= 8'b00000000;	// NOP
		ROM[7]  <= 8'b00000000;	// NOP
		ROM[8]  <= 8'b00000000;	// NOP
		ROM[9]  <= 8'b00000000;	// NOP
		ROM[10] <= 8'b00000000;	// NOP
		ROM[11] <= 8'b00000000;	// NOP
		ROM[12] <= 8'b00000000;	// NOP
		ROM[13] <= 8'b00000000;	// NOP
		ROM[14] <= 8'b00000000;	// NOP
		ROM[15] <= 8'b00000000;	// NOP
		*/
		
		// LED NIGHT RIDER
		/*
		ROM[0]  <= 8'b10110011;	// OUT 0011
		ROM[1]  <= 8'b10110110;	// OUT 0110
		ROM[2]  <= 8'b10111100;	// OUT 1100
		ROM[3]  <= 8'b10111000;	// OUT 1000
		ROM[4]  <= 8'b10111000;	// OUT 1000
		ROM[5]  <= 8'b10111100;	// OUT 1100
		ROM[6]  <= 8'b10110110;	// OUT 0110
		ROM[7]  <= 8'b10110011;	// OUT 0011
		ROM[8]  <= 8'b10110001;	// OUT 0001
		ROM[9]  <= 8'b11110000;	// JMP 0000
		ROM[10] <= 8'b00000000;	// NOP
		ROM[11] <= 8'b00000000;	// NOP
		ROM[12] <= 8'b00000000;	// NOP
		ROM[13] <= 8'b00000000;	// NOP
		ROM[14] <= 8'b00000000;	// NOP
		ROM[15] <= 8'b00000000;	// NOP
		*/
		
		// RAMEN TIMER (For 1Hz CLOCK)
		ROM[0]  <= 8'b10110111;	// OUT 0111
		ROM[1]  <= 8'b00000001;	// ADD A, 0001
		ROM[2]  <= 8'b11100001;	// JNC 0001
		ROM[3]  <= 8'b00000001;	// ADD A, 0001
		ROM[4]  <= 8'b11100011;	// JNC 0011
		ROM[5]  <= 8'b10110110;	// OUT 0110
		ROM[6]  <= 8'b00000001;	// ADD A, 0001
		ROM[7]  <= 8'b11100110;	// JNC 0110
		ROM[8]  <= 8'b00000001;	// ADD A, 0001
		ROM[9]  <= 8'b11101000;	// JNC 1000
		ROM[10] <= 8'b10110000;	// OUT 0000
		ROM[11] <= 8'b10110100;	// OUT 0100
		ROM[12] <= 8'b00000001;	// ADD A, 0001
		ROM[13] <= 8'b11101010;	// JNC 1010
		ROM[14] <= 8'b10111000;	// OUT 1000
		ROM[15] <= 8'b11111111;	// JMP 1111
	end
endmodule

コメントで命令をNOPって書いてますけど，実際には「8'b00000000」は「ADD A, 0」だったりします。
まぁ，要するにNOPなんですけどね。

テストベンチはこんな感じ？

module test_rom;
	reg	[3:0] ROM_ADDRESS;
	wire	[7:0] ROM_DATA;
	
	ROM_16WORD	ROM(ROM_ADDRESS, ROM_DATA);
	
	initial begin
		$dumpfile("test_rom.vcd");
		$dumpvars(0, test_rom);
		$monitor ("%t: ROM_ADDRESS = %b%b%b%b, ROM_DATA = %b%b%b%b%b%b%b%b", $time,
			ROM_ADDRESS[3], ROM_ADDRESS[2], ROM_ADDRESS[1], ROM_ADDRESS[0],
			ROM_DATA[7], ROM_DATA[6], ROM_DATA[5], ROM_DATA[4], 
			ROM_DATA[3], ROM_DATA[2], ROM_DATA[1], ROM_DATA[0]
		);
		
			ROM_ADDRESS = 4'b0000;
		#10	ROM_ADDRESS = 4'b0001;
		#10	ROM_ADDRESS = 4'b0010;
		#10	ROM_ADDRESS = 4'b0011;
		#10	ROM_ADDRESS = 4'b0100;
		#10	ROM_ADDRESS = 4'b0101;
		#10	ROM_ADDRESS = 4'b0110;
		#10	ROM_ADDRESS = 4'b0111;
		#10	ROM_ADDRESS = 4'b1000;
		#10	ROM_ADDRESS = 4'b1001;
		#10	ROM_ADDRESS = 4'b1010;
		#10	ROM_ADDRESS = 4'b1011;
		#10	ROM_ADDRESS = 4'b1100;
		#10	ROM_ADDRESS = 4'b1101;
		#10	ROM_ADDRESS = 4'b1110;
		#10	ROM_ADDRESS = 4'b1111;
		#10	$finish;
	end
endmodule

次回予告

次は何だっけ？

えーと，レジスタファイルの話っぽいよ！

Amazon.co.jp - 渡波郁「CPUの創りかた」毎日コミュニケーションズ (2003)

2012年8月23日木曜日

１．TD4

TD4って知ってますか？

この世の中には日本語に限定しても数多の電子工作本が出版されているのですが，
その中でも異彩を放っているのが「CPUの創りかた」っていう本でございます。

Amazon.co.jp - 渡波郁「CPUの創りかた」毎日コミュニケーションズ (2003)

この本が市井でどんな評価を受けているかは上のAmazonレビューなんかをご参照してくださいな。
実際，書店で現物を見られると「感動モノ」だと思いますよ？

TD4っていうのは渡波(2003)の中で実際に制作されている4bit CPUでありまして，
なんと10個のLogic ICで構成されているという驚きのプロセッサでございます。

ICといっても別にマイコン持ってくるとかそんなトンチのきいた話をしているわけではなく，
74 Logicシリーズ（Hi-speed CMOS）だけで構成されちゃってたりします。

いわゆるTTLで5V動作するのでハンダゴテをニギニギしながら作業しても作れちゃいますし，
実際に渡波(2003)の中で制作されています。

というか，実装部分の話もかなり載っていて，電子工作初心者に向けたいくらいです。

ちなみに，TD4の名前の意味は……。本を読んでみるとわかります（笑）

そんでもって，次のようなISA（命令セットアーキテクチャ）を持っています。

MOV A, Im
MOV B, Im
MOV A, B
MOV B, A
ADD A, Im
ADD B, Im
IN A
IN B
OUT Im
OUT B
JMP Im
JNC Im

２．FPGAで作る

いやね，はじめはディスクリートで作ろうと思ったんですよ？
でもね，さすがに大変じゃないですか。
本にも書いてありますが，配線量が半端じゃ無いんですよ。とくにROM。

その点HDLって！！
便利だし！
拡張も簡単だし！

実際に物理的に作ろうと思えばFPGAに実装しちゃえばいいわけですしね！

といわけで，まずはVerilog HDLで書いてシミュレーションします。
んで，うまく行ったらネットリスト書いてFPGA上に論理合成の結果を書き込んで完成です！

３．必要なもの

１．本
買いましょう！
絶対に買いましょう！
大事なことなので二度言いました。

２．Verilog HDLの開発環境
Icarus Verilogとか使えばいいんじゃね？
gtkwaveがあれば見やすいかもしれないけど，個人的にはずっとコンソールからvvpしてます。
詳細はググレカス。

３．FPGAボード＆開発環境
実際にあれば現物が見れます。
必須ってわけではないけどね。

個人的には研究室に~~転がってる~~お借りしたXilinx ML501を使う予定です。

え，なんで予定かって？
この記事書いてる時点じゃまだ実装してないんですよ。

４．元気！ヤル気！シャカリキ！
これ大事！

４．お約束

あのー。
Verilogとかちょっち齧ったことある人は知ってると思うんですけど，別に中で74Logicを再現する必要はないんですよね。

でも，今回はできるだけ再現します。
しかも，assignとか使いまくって再現します。
本来はお行儀が悪いから，ちゃんとRTLで再現するんですけどね。

ただし，ROMとクロックジェネレータは再現できないので，Verilog様の偉大なる力をお借りしちゃいます。
（ROMって再現できないんですかね？メカニカルスイッチはだめかなぁ？）

以上お約束でした。
（意味がわからなかった人は，読み飛ばしちゃえ！）

次回予告

いよいよ実装するよ！

2012年5月20日日曜日

ガウスの消去法（理論）

ガウスの消去法

ガウスの消去法（ガウスのしょうきょほう）あるいは掃き出し法（はきだしほう）とは、変数の数と方程式の本数が一致した連立一次方程式（線形方程式系）を解く為の解法である。
出典：ガウスの消去法 - Wikipedia(http://ja.wikipedia.org/wiki/ガウスの消去法)

以下，本稿では$n$元線型連立方程式について扱い，$n$本の等式が存在して，解は一意に定まるものとして議論を進める。

１．連立方程式を行列を用いて表す～拡大係数行列～

線型連立方程式 \[ \left\{\begin{array}{l} a_{11} x_1 + a_{12} x_2 + \cdots + a_{1n} x_n = b_1 \\ a_{21} x_1 + a_{22} x_2 + \cdots + a_{2n} x_n = b_2 \\ \qquad\vdots \\ a_{n1} x_1 + a_{n2} x_2 + \cdots + a_{nn} x_n = b_n \end{array}\right. \qquad\cdots\cdots\cdots (*) \] を考える。このとき，$n$次正方行列A，$n$次元縦ベクトル$x$，$b$をそれぞれ次のように定義する。 \[ A = \begin{pmatrix} a_{11} & a_{12} & \cdots & a_{1n} \\ a_{21} & a_{22} & \cdots & a_{2n} \\ \vdots & \vdots & \ddots & \vdots \\ a_{n1} & n_{n2} & \cdots & a_{nn} \end{pmatrix} \quad , \qquad x = \begin{pmatrix} x_1 \\ x_2 \\ \vdots \\ x_n \end{pmatrix} \quad , \qquad b = \begin{pmatrix} b_1 \\ b_2 \\ \vdots \\ b_n \end{pmatrix} \] すると，初めの線型連立方程式$(*)$は \[ A x = b \] と表すことができる。
初めの線型連立方程式$(*)$に対して，行列$A$を係数行列といい， \[ (A \mid b) = \begin{pmatrix} a_{11} & a_{12} & \cdots & a_{1n} & \mid & b_1 \\ a_{21} & a_{22} & \cdots & a_{2n} & \mid & b_2 \\ \vdots & \vdots & \ddots & \vdots & \mid & \vdots \\ a_{n1} & n_{n2} & \cdots & a_{nn} & \mid & b_n \end{pmatrix}\] によって定義した$(A \mid b)$を拡大係数行列という。
さて，線型連立方程式$(*)$の解が$x_i = c_i ~ (\forall i \in \mathbb{N}, 1 \leq i \leq n)$であるとしよう。
これを言い換えれば，$n$次単位行列$I_n$を用いて， \[ I_n x = c \qquad \left( ただし，c = \begin{pmatrix} c_1 \\ c_2 \\ \vdots \\ c_n \end{pmatrix} とする。 \right) \] といえる。

２．行列の基本変形と基本行列

ところで，行に関する基本変形を用いて$A \to I_n$と変形することを考えよう。
行に関する基本変形とは以下にあげる3つの変形である。

2つの行を入れ替える
ある行を0でない定数倍する
ある行に、他のある行の定数倍を加える

$n$次正方行列$P_{ij}$を \[ P_{ij} = \begin{pmatrix} 1 & ~ & ~ & ~ & ~ & ~ & O \\ ~ & \ddots & ~ & ~ & ~ & ~ & ~ \\ ~ & ~ & 0 & ~ & 1 & ~ & ~ \\ ~ & ~ & ~ & \ddots & ~ & ~ & ~ \\ ~ & ~ & 1 & ~ & 0 & ~ & ~ \\ ~ & ~ & ~ & ~ & ~ & \ddots & ~ \\ O & ~ & ~ & ~ & ~ & ~ & 1 \end{pmatrix} \begin{matrix} ~ \\ ~ \\[.5em] \leftarrow i\textrm{行目} \\ ~ \\[.75em] \leftarrow j\textrm{行目} \\ ~ \\ ~ \end{matrix} \] と定義する。これはもちろん$n$次単位行列$I_n$の$i$行目と$j$行目を入れ替えたものに等しい。
ある$n$次正方行列$X$に，左から$P_{ij}$をかけた行列$P_{ij}X$は行列$X$の$i$行目と$j$行目を入れ替えたものに等しくなる。

同様に他の2つの変形についても行列を定義できる。
$n$次正方行列$Q_{i}(c)$を \[ Q_{i}(c) = \begin{pmatrix} 1 & ~ & ~ & ~ & ~ & ~ & ~ & O \\ ~ & \ddots & ~ & ~ & ~ & ~ & ~ \\ ~ & ~ & 1 & ~ & ~ & ~ & ~ \\ ~ & ~ & ~ & c & ~ & ~ & ~ \\ ~ & ~ & ~ & ~ & 1 & ~ & ~ \\ ~ & ~ & ~ & ~ & ~ & \ddots & ~ \\ O & ~ & ~ & ~ & ~ & ~ & 1 \end{pmatrix} \begin{matrix} ~ \\ ~ \\ ~ \\[.5em] \leftarrow i行目 \\ ~ \\ ~ \\ ~ \end{matrix} \] と定義する。これはもちろん$n$単位方行列$I_n$の$i$行$i$列の成分$I(i, i)$を$c$にしたものに等しい。
ある$n$次正方行列$X$に，左から$Q_{i}(c)$をかけた行列$Q_{i}(c)X$は行列$X$の$i$行目を$c$倍したものに等しくなる。

$n$次正方行列$R_{ij}(c)$を \[ R_{ij}(c) = \begin{pmatrix} 1 & ~ & ~ & ~ & ~ & ~ & ~ & O \\ ~ & \ddots & ~ & ~ & ~ & ~ & ~ \\ ~ & ~ & 1 & \cdots & c & ~ & ~ \\ ~ & ~ & ~ & \ddots & \vdots & ~ & ~ \\ ~ & ~ & ~ & ~ & 1 & ~ & ~ \\ ~ & ~ & ~ & ~ & ~ & \ddots & ~ \\ O & ~ & ~ & ~ & ~ & ~ & 1 \end{pmatrix} \begin{matrix} ~ \\ ~ \\[.5em] \leftarrow i\textrm{行目} \\ ~ \\[.75em] \leftarrow j\textrm{行目} \\ ~ \\ ~ \end{matrix} \] と定義する。これはもちろん$n$単位方行列$I_n$の$i$行$j$列の成分$I(i, j)$を$c$にしたものに等しい。
ある$n$次正方行列$X$に，左から$R_{ij}(c)$をかけた行列$R_{ij}(c)X$は行列$X$の$i$行目を$c$倍したものに等しくなる。

以上の用ように$n$次正方行列$X$に左から$P_{ij}$，$Q_{i}(c)$，$R_{ij}(c)$（この3つの行列を総称して基本行列とよぶ。）をかけることで行に関する基本変形を行うことができる。この性質から行に関する基本変形を左基本変形ともいう。
（ちなみに，$n$次正方行列$X$に，右から$P_{ij}$，$Q_{i}(c)$，$R_{ij}(c)$をかけることで列に関する基本変形を行うことができる。この性質から列に関する基本変形を右基本変形ともいう。列に関する基本変形は行に関する基本変形の3つそれぞれについて，行を列と読み替えたものである。）

以上の議論より，当初の目的であった$A \to I_n$の変形は，行に関する基本変形は基本行列を左からかける操作を有限回行うことで達成できる。（再度述べるが，これはあくまで解が一意に定まるという仮定の下で成り立つ。一般的にはいえない。）

３．ガウスの消去法（掃き出し法）

ガウスの消去法のアルゴリズムは前進消去(forward elimination)と後退代入(backward substitution)と呼ばれる2つのステップよりなる。
以下の疑似コードでは，$a_{i,j}$は$(n ,n+1)$型の拡大係数行列$(A \mid b)$の$i$行$j$列の要素を示す。

３－１．前進消去のアルゴリズム

/* $i$行目の前進消去を行う */
■$Proceduer$ 前進消去($i$: 整数)
｜　　/* 必要に応じてピボット選択 */
｜　　□$If$ $a_{i,i} = 0$ $Then$
｜　　｜　　$j \leftarrow a_{i,p} \neq 0$なる最小のp
｜　　｜　　/* もしそのようなpが存在しなければ，解が一意に定まらないのでエラーとなる */
｜　　｜　　行列$A$の$i$行目と$j$行目を入れ替える
｜　　□$End If$
｜　　$D \leftarrow a_{i,i}$
｜　　/* $i$行目の各要素を$D$で割る */
｜　　□$Loop$ $1 \leq j \leq n$
｜　　｜　　$a_{i,j} \leftarrow \dfrac{a_{i,j}}{D}$
｜　　□$EndLoop$
｜　　/* $i$行目以降の全ての行から$i$行目を引く */
｜　　□$Loop$ $i+1 \leq j \leq n$
｜　　｜　　□$Loop$ $1 \leq k \leq n+1$
｜　　｜　　｜　　$a_{j,k} \leftarrow a_{j,k} - a_{i,k}$
｜　　｜　　□$EndLoop$
｜　　□$EndLoop$
■$EndProceduer$

前進消去では拡大係数行列の下三角の要素を0にし，さらに対角要素を1にすることを行う。
もし，対角要素が行の入れ替えによっても0にしかならないならば，解は一意に定まることができない。

３－２．後退代入のアルゴリズム

/* $i$行目の後退代入を行う */
■$Proceduer$ 後退代入($i$: 整数)
｜　　/* 1ステップ前の解を代入 */
｜　　□$Loop$ $i \geq j \geq 0$
｜　　｜　　$a_{j,n+1} \leftarrow a_{j,n+1} - c_{i+1} \times a_{j,i+1}$
｜　　｜　　$a_{j,i+1} \leftarrow 0$
｜　　□$EndLoop$
｜　　/* $i$行目を用いて1文字消去 */
｜　　□$If$ $a_{i,i} \neq 0$ $Then$
｜　　｜　　$a_{i,n+1} \leftarrow \dfrac{a_{i,n+1}}{a_{i,i}}$
｜　　□$EndIf$
｜　　/* 解を$c_i$とする */
｜　　$c_i \leftarrow a_{i, n+1}$
■$EndProceduer$

３－３．ガウスの消去法全体のアルゴリズム

/* 初期値 */
$a_{i,j} \leftarrow$ 拡大係数行列$(A \mid b)$の$(i, j)$要素
$n \leftarrow $次数
/* 解 */ $c_{i}$ /* 解を入れるベクトル */

/* ガウスの消去法 */
■$Proceduer$ ガウスの消去法
｜　　/* 前進消去 */
｜　　□$Loop$ $1 \leq i \leq n$
｜　　｜　　前進消去$(i)$
｜　　□$EndLoop$
｜　　/* 後退代入 */
｜　　□$Loop$ $n \geq i \geq 1$
｜　　｜　　後退代入$(i)$
｜　　□$EndLoop$
■$EndProceduer$

2012年5月19日土曜日

ガウスの消去法（実装）

ガウスの消去法の実装を行う。

コードは次のようになる。

#include <stdio.h>
#include <stdlib.h>
#include <memory.h>

/************************************************************
 * ガウスの消去法による線形方程式の数値計算
 * 
 * (C) 2012- Gofer.
 ************************************************************/

// 方程式の表示
void display_equtation(int N, double *A) {
 int i, j;
 
 for(i=0; i<N; ++i) {
  for(j=0; j<N; ++j) {
   printf("%f x[%d]", A[i*(N+1) + j], j);
   if(j < N-1) printf(" + ");
  }
  printf(" = %f\n", A[i*(N+1) + N]);
 }
 putchar('\n');
 
 return;
}

// n行目とm行目を入れ替える
double* replace_row(int n, int m, int N, double* A) {
 double* line_temp = (double*)malloc(sizeof(double)*(N+1));
 memmove(line_temp,   &A[n*(N+1)], sizeof(double)*(N+1));
 memmove(&A[n*(N+1)], &A[m*(N+1)], sizeof(double)*(N+1));
 memmove(&A[m*(N+1)], line_temp,  sizeof(double)*(N+1));
 free(line_temp);
 return A;
}
 
// i行目の前進消去を行う
double* forward_elimination(int i, int N, double *A) {
 int j, k, J = -1;
 double divide;
 
 // 対角要素が0ならピボット選択を行う
 if(A[i*(N+1) + i] == 0) {
  for(j=i+1; j<N; ++j) {
   if(A[j*(N+1) + i] != 0) {
    J = j;
    break;
   }
  }
  if(J == -1) return NULL;
  replace_row(i, J, N, A);
 }
 
 // 割算する係数を決定
 divide = A[i*(N+1) + i];
 
 // 標準化
 for(j=0; j<(N+1); ++j)
  A[i*(N+1) + j] /= divide;
 
 // i行目以外の行から引く
 for(k=i+1; k<N; ++k) {
  for(j=(N+1)-1; j>=0; --j)
   A[k*(N+1) + j] -= A[k*(N+1) + i] * A[i*(N+1) + j];
 }
 
 return A;
}

// i行目の後退代入
double* backward_substitution(int i, int N, double *A, double *x) {
 // (N-1)-i個の解は決定済み
 int j, k;
 
 // 1ステップ前に求めた解を代入
 k = i+1;
 if(k < N) { 
  for(j=k-1; j>=0; --j) {
   A[j*(N+1) + N] -= x[k] * A[j*(N+1) + k];
   A[j*(N+1) + k] = 0;
  }
 }
 
 // 第i行を用いて1文字消去
 if(A[i*(N+1) + i] != 0) {
  A[i*(N+1) + N] /= A[i*(N+1) + i];
  A[i*(N+1) + i] = 1;
 }
 
 // xベクタに代入
 x[i] = A[i*(N+1) + N];
 
 return A;
}

int main(void) {
 //int N = 2;
 /*
 double A[2][3] = { {1, 2, 5}, 
      {2, 3, 8}};
 */

 //int N = 3;
 /*
 double A[3][4] = { {2, 4, 2, 8}, 
      {4, 10, 3, 17}, 
      {3, 7, 1, 11}};
 */

 //int N = 4;
 /*
 double A[4][5] = { {1, 1, 2, 1, 1}, 
      {1, 1, 3, 2, -2}, 
      {2, -2, 2, -1, 1}, 
      {-1, 1, 0, 1, -1}};
 */
 
 int N = 4;      
 double A[4][5] = { {1, -1, 2, -1, -8}, 
      {2, -2, 3, -3, -20}, 
      {1, 1, 1, 0, -2}, 
      {1, -1, 4, 3, 4}};
 
 int i;
 double* x = (double*)malloc(sizeof(double) * N);
 
 display_equtation(N, (double*)A);
 
 // 前進消去
 for(i=0; i<N; ++i) {
  if(forward_elimination(i, N, (double*)A) == NULL) {
   fprintf(stderr, "Error!\n");
   free(x);
   return -1;
  }
 }
 
 // 後退代入
 for(i=N-1; i>=0; --i)
  backward_substitution(i, N, (double*)A, x);
 
 for(i=0; i<N; ++i)
  printf("x[%d] = %f\n", i, x[i]);
 
 free(x);
 
 return 0;
}

2012年4月28日土曜日

GoogleCodeJam 2012 - Qualification Round / Problem C

Problem C. Recycled Numbers
さて、Preblem C。ここまでは余裕だったが、これはどうだろう。

問題文曰く、

Do you ever become frustrated with television because you keep seeing the same things, recycled over and over again? Well I personally don't care about television, but I do sometimes feel that way about numbers.

だそうだが、個人的には筆者の方が変態だと思う。

C++のSTLからsetを使う。Pair型の<演算子も定義する。(n, m)でnの方が優先。
recycleはnのstartから後ろを前に持ってきた数字を返す。
あとはひたすら全通り試していく。
ひたすらsetにinsertしても重複しないから便利。
でもって表示はsize()メソッドで表示すればfor文カウントもせずに終了できる。

コード全文は以下。

#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <set>

#define IN_RANGE(x, A, B)    ((A <= x)&&(x <= B))

typedef struct _pair{
    unsigned int n;
    unsigned int m;
} Pair;

bool operator<(const Pair& a, const Pair& b) {
    if(a.n == b.n) return a.m < b.m;
    else return a.n < b.n;
}

unsigned int NUMBER_OF_DIGITS;

int recycle(const unsigned int n, const unsigned int start) {
    unsigned int div_base = pow(10, start), temp = n % div_base;
    return (n / div_base) + (temp * pow(10, NUMBER_OF_DIGITS - start));
}

int main(int argc, char** argv) {
    unsigned int T, A, B, i, n, k, m;
    
    //FILE *fp = fopen("input.txt", "r");
    //FILE *fp = fopen("C-small-attempt0.in", "r");
    FILE *fp = fopen("C-large.in", "r");
    fscanf(fp, "%d", &T);
    
    for(i=0; i<T; ++i) {
        fscanf(fp, "%d %d", &A, &B);
        NUMBER_OF_DIGITS = log10(A)+1;
        if(NUMBER_OF_DIGITS == 1) {
            printf("Case #%d: %d\n", i+1, 0);
            continue;
        }
        
        std::set<Pair> pairs;
        
        for(n=A; n<=B; ++n) {
            for(k=1; k<NUMBER_OF_DIGITS; ++k) {
                m = recycle(n, k);
                if(n == m) continue;
                Pair new_pair = ((n < m) ? (Pair){n, m} : (Pair){m, n});
                if(IN_RANGE(m, A, B))
                    pairs.insert(new_pair);
            }
        }
        
        printf("Case #%d: %d\n", i+1, pairs.size());
    }
    
    fclose(fp);
    
    return EXIT_SUCCESS;
}

意外と楽だったかな。

2012年4月27日金曜日

GoogleCodeJam 2012 - Qualification Round / Problem B

Problem B. Dancing With the Googlers

このあたりから本番かな。small/large両方あるしね。

Google社員とダンスをするというシャレ乙な問題。
ただ、一般人がダンスするだけなのにスコア付けされるのかよ。

さてさて。
入力は3人の審査委員の点数の合計なのですが、3人の意見はいつも均衡に近い状況で、点差が3以上になることはないんだそうです。
つまり、合計点が15点なら(5,5,5)または(4,5,6)な感じで点数の組が分かれます。
もし、2点以上というか2点の差があれば"surprise"な組だと。
これって審査員談合してね？

surpriseな組の点数は合計をnとして、
n ≡ 0 (mod 3)なら: (floor(n/3)-1, floor(n/3), floor(n/3)+1)
n ≡ 2 (mod 3)なら: (floor(n/3), floor(n/3), floor(n/3)+2)
である。 n ≡ 1 (mod 3)ならsurpriseになりえない。
surpriseじゃない組も同じ感じで静的に求められる。
それぞれ、 make_triplet_surprise()と make_triplet_not_surprise()である。

main()の動きとしては、

はじめ全ての点数を"not surprise"な組にしておく。
合計点の高いほうから順にS個を"surprise"な組にし直す。（"surprise"にできないならほっとく。）
is_above_p()を使って組の点数全てがpを超えている組をカウントする。

といった流れ。

コード全文は以下のような感じで。

#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <list>
#include <algorithm>
#include <functional>

#define CAN_SURPRISE(t)    ((t) ? (((t - ((t/3)*3))-1) ? 1 : 0) : 0)

typedef struct _Triplet{
    unsigned int t;
    unsigned int triplet[3];
} Triplet;

bool compareTriplet(Triplet &a, Triplet &b) {
    return a.t > b.t;
}

void make_triplet_not_surprise(unsigned int t, unsigned int* triplet) {
    unsigned int avg = t / 3;
    
    switch(t - (avg * 3)) {
    case 0:
        triplet[0] = triplet[1] = triplet[2] = avg;
        break;
    case 1:
        triplet[0] = avg+1;
        triplet[1] = triplet[2] = avg;
        break;
    case 2:
        triplet[0] = triplet[1] = avg+1;
        triplet[2] = avg;
        break;
    }
}

void make_triplet_surprise(unsigned int t, unsigned int* triplet) {
    int avg = t / 3;
    switch(t - (avg * 3)) {
    case 0:
        triplet[0] = avg+1;
        triplet[1] = avg;
        triplet[2] = avg-1;
        break;
    case 2:
        triplet[0] = avg+2;
        triplet[1] = triplet[2] = avg;
        break;
    }
}

int is_above_p(unsigned int p, unsigned int *triplet) {
    return ((triplet[0] >= p) || (triplet[1] >= p) || (triplet[2] >= p)) ? 1 : 0;
}

int main(int argc, char** argv) {
    unsigned int T, N, S, p, i, j, temp;
    unsigned int trip[3];
    
    //FILE *fp = fopen("input.txt","r");
    //FILE *fp = fopen("B-small-attempt0.in","r");
    FILE *fp = fopen("B-large.in","r");
    
    fscanf(fp, "%d\r\n", &T);
    
    for(j=0; j<T; ++j) {
        std::list<Triplet> t;
        std::list<Triplet>::iterator t_itr;
        
        fscanf(fp, "%d %d %d", &N, &S, &p);
        
        for(i=0; i<N; ++i) {
            fscanf(fp, "%d", &temp);
            make_triplet_not_surprise(temp, trip);
            Triplet tr;
            tr.t = temp;
            memmove(tr.triplet, trip, 3*sizeof(unsigned int));
            t.push_back(tr);
        }
        t.sort(compareTriplet);
        
        for(t_itr=t.begin(); t_itr!=t.end(); ++t_itr) {
            if(!is_above_p(p, t_itr->triplet) && CAN_SURPRISE(t_itr->t)) {
                if(S == 0) break;
                make_triplet_surprise(t_itr->t, t_itr->triplet);
                --S;
            }
        }
        
        temp = 0;
        for(t_itr=t.begin(); t_itr!=t.end(); ++t_itr) {
            if(is_above_p(p, t_itr->triplet)) ++temp;
        }
        
        printf("Case #%d: %d\n", j+1, temp);
    }
    fclose(fp);
    
    return EXIT_SUCCESS;
}

まぁこれもそんな難しくはないかな。

GoogleCodeJam 2012 - Qualification Round / Problem A

Problem A. Speaking in Tongues

肩慣らし。

簡単な文字列置換のはなし。
テーブル作って1文字ずつ置換する。

問題文曰く、

Googlerese is based on the best possible replacement mapping, and we will never change it. It will always be the same. In every test case. We will not tell you the rest of our mapping because that would make the problem too easy, but there are a few examples below that may help.

だそうで、テーブルはSampleのInputとOutputを照らし合わせればOKで、足りない2文字もswapして突っ込めばいい。

ちなみに、

char table[26] = {'y', 'h', 'e', 's', 'o', 'c', 'v', 'x', 'd', 'u', 'i', 'g', 'l', 'b', 'k', 'r', 'z', 't', 'n', 'w', 'j', 'p', 'f', 'm', 'a', 'q'};

こんな感じになるはず。

C言語で書くことにする。

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

char table[26] = {'y', 'h', 'e', 's', 'o', 'c', 'v', 'x', 'd', 'u', 'i', 'g', 'l', 'b', 'k', 'r', 'z', 't', 'n', 'w', 'j', 'p', 'f', 'm', 'a', 'q'};

void make_table() {
    unsigned int T, i, j;
    char ans[100];
    char str[100];
    
    FILE *fp = fopen("input.txt","r");
    FILE* fpA = fopen("ans.txt", "r");
    
    fscanf(fp, "%d\r\n", &T);
    for(i=0; i<T; ++i) {
        for(j=0; 1; ++j) {
            fscanf(fp, "%c", &str[j]);
            if(str[j] == '\n') break;
        }
        str[j] = '\0';
        
        for(j=0; 1; ++j) {
            fscanf(fpA, "%c", &ans[j]);
            if(ans[j] == '\n') break;
        }
        ans[j] = '\0';
        
        for(j=0; str[j] != '\0'; ++j) {
            table[(str[j] - 'a')] = ans[j];
        }
        printf("%s\n%s\n", str, ans);
    }
    
    fclose(fp);
    fclose(fpA);
    
    for(i=0; i<26; ++i) {
        printf("%c -> %c\t", i+'a', table[i]);
        //printf("\'%c\', ", table[i]);
        if((i+1) % 7 == 0) putchar('\n');
    }
}

void translate(char* buf, const char* str) {
    unsigned int i;
    
    for(i=0; str[i] != '\0'; ++i) {
        if(str[i] == ' ') buf[i] = ' ';
        else buf[i] = table[(str[i] - 'a')];
    }
    buf[i] = '\0';
}

int main(int argc, char** argv) {
    unsigned int T, i, j;
    //char str[100], buf[100];
    char *str = (char*)malloc(100);
    char *buf = (char*)malloc(100);
    
    //FILE *fp = fopen("input.txt","r");
    FILE *fp = fopen("A-small-attempt0.in","r");
    fscanf(fp, "%d\r\n", &T);
    for(i=0; i<T; ++i) {
        for(j=0; 1; ++j) {
            fscanf(fp, "%c", &str[j]);
            if(str[j] == '\n') break;
        }
        str[j] = '\0';
        translate(buf, str);
        printf("Case #%d: %s\n", i+1, buf);
    }
    fclose(fp);
    
    return EXIT_SUCCESS;
}

make_table()は初めにchar teble[];をつくるときにつかったもの。
main()とは別に用いていて、呼び出しはしていない。

ほかにコメントすることはないなぁ。。。

登録: 投稿 (Atom)

2012年9月20日木曜日

週刊 TD4をFPGAで創る 第５号 「命令デコーダを創る」

１．74HC10

２．74HC32

３．命令デコーダ

４．そして，完成へ…

次回予告

2012年9月13日木曜日

週刊 TD4をFPGAで創る 第４号 「ALUを創る」

１．74HC283

２．74HC181

３．74HC74

４．8.2節までの回路

４．8.3節までの回路

次回予告

2012年9月6日木曜日

週刊 TD4をFPGAで創る 第3号 「レジスタを創る」

１．74HC153

２．74HC161

３．第７章の章末の回路

次回予告

2012年8月30日木曜日

週刊 TD4をFPGAで創る 第２号 「ROMを創る」

１．74HC540

２．74HC154

３．ROM

次回予告

2012年8月23日木曜日

週刊 TD4をFPGAで創る 創刊号

１．TD4

２．FPGAで作る

３．必要なもの

４．お約束

次回予告

2012年5月20日日曜日

ガウスの消去法

１．連立方程式を行列を用いて表す ～拡大係数行列～

２．行列の基本変形と基本行列

３．ガウスの消去法（掃き出し法）

３－１．前進消去のアルゴリズム

３－２．後退代入のアルゴリズム

３－３．ガウスの消去法全体のアルゴリズム

2012年5月19日土曜日

2012年4月28日土曜日

2012年4月27日金曜日

週刊 TD4をFPGAで創る第５号「命令デコーダを創る」

週刊 TD4をFPGAで創る第４号「ALUを創る」

週刊 TD4をFPGAで創る第3号「レジスタを創る」

週刊 TD4をFPGAで創る第２号「ROMを創る」

週刊 TD4をFPGAで創る創刊号

１．連立方程式を行列を用いて表す～拡大係数行列～