State-of-the-Ars

知識蓄積備忘録

ACM 登録手順

読みたい論文が色々あるので,ACM学生会員+Digital Libraryを登録することにした.

今後,また登録することがあるかもしれないので, その時の備忘録としてここに記す.

登録は,以下のURLからアクセスされたし.

Student Membership — Association for Computing Machinery

*のある箇所は必須記入箇所です. それ以外は,恐らく記入が無くとも問題ないと思います.

また,本サイトを参考にして,登録を行い, 何か問題が発生したとしても, 筆者らは一切責任を負いません.

Name

f:id:zigzackey:20161125142211j:plain

Prefix(Mr. Ms. Dr.)やMiddle(ミドルネーム),Suffix(Jr. Sr. I)などがあるのであれば, 記入しましょう.

ないのであれば,First(名)とLast(姓)だけでいいでしょう.

Address

f:id:zigzackey:20161125142716j:plain

Streetは番地以下の情報, cityは市町村, stateは都道府県(日本の情報は打ち込めない模様), Postal Code(Zip)は郵便番号, Countries/Dependencies/Areas of Special Sovereigntyは国名 のことを指しています.

不安であれば,以下のサイトを使用してみると良いかもしれません.

JuDress | 住所→Address変換

Permanent Address

f:id:zigzackey:20161125143810j:plain 普段住居おいているところを書きます.

多くの場合,上記のAddressと同じだと思いますので,

下にある

Same as above

チェックボックスにチェックを入れておきましょう.

Contact Information

f:id:zigzackey:20161125144508j:plain

Phoneは普段連絡がとれる電話番号, Faxはファクシミリの番号, Email address of applicantはACMに登録する方のE-mailアドレス のことを指しています.

Phone・Faxは,国番号(日本ですと,+81)から書き始めるようにしてください. 詳しい書き方は各自でお調べください.

Student Profile

f:id:zigzackey:20161125145112j:plain

Name of Schoolは英語での学校名, Year in School [or equivalent]は学年, Expected Month of Graduationは卒業予定の月, Expected Year of Graduationは卒業予定の年, My degree will be in the following areaは授与している(される)学位の専攻, Expected Degree [or equivalent]は授与している(される)学位, Age Rangeは該当する年齢層, Genderは社会的・文化的な性別, Ethnicity-US Residents Onlyはアメリカ在住でなければ選択しなくてよい, Do you belong to an ACM Student Chapter?は,ACM Student Chapterに登録されているのであればYes・そうでなければNoを選択 のことを指しています.

How did you hear about ACM Membership?/Student Membership Options/Join ACM-W

省略します.

ATC001-A:深さ優先探索

A: 深さ優先探索 - AtCoder Typical Contest 001 | AtCoderの問題を解きました.

AtCoder Typical Contestなので,解説は詳しく書かれており

深さ優先探索による塗りつぶしを見ればある程度わかると思います.

それでは,以下にソースコードを示します.

#define _CRT_SECURE_NO_WARNINGS

#include<cstdio>
#include<iostream>

using namespace std;

const int MAX_W = 500;
const int MAX_H = 500;

void search(int x, int y);

int W, H; // 横幅(Width)と縦幅(Height)
char maze[MAX_W][MAX_H]; // 迷路
bool reached[MAX_W][MAX_H] = {false}; // 到達できるかどうか?

int main()
{
    int sX, sY;    // スタート('s')座標
    int gX, gY; // ゴール('g')座標

    scanf("%d %d", &H, &W);
    for (int i = 0; i < H; i++) // 縦幅(Height)
    {
        for (int j = 0; j < W; j++) // 横幅(Wigth)
        {
            cin >> maze[i][j];
            if (maze[i][j] == 's')
            {
                sX = j; sY = i;
            }
            if (maze[i][j] == 'g')
            {
                gX = j; gY = i;
            }
        }
    }

    search(sX, sY);

    if (reached[gY][gX])
        printf("Yes\n");
    else
        printf("No\n");
}

// スタート座標を(x, y)として関数searchを呼び出す
void search(int x, int y)
{
    // 迷路の外側の場合,何もしない
    if (x < 0 || W <= x || y < 0 || H <= y)
        return;

    // 壁(#)の場合,何もしない
    if (maze[y][x] == '#')
        return;

    // 以前に到達したことがある場合,何もしない
    if (reached[y][x])
        return;

    // 到達した
    reached[y][x] = true;

    // 上下左右4方向に対し,探索を行う
    search(x + 1, y); // 右
    search(x - 1, y); // 左 
    search(x, y + 1); // 下
    search(x, y - 1); // 上
}

注意する点があるといえば,配列の設定の仕方です.

今回は2次元配列で格子状の区画を再現しています.

そのとき,縦幅×横幅[y]xで行っています.

解説のままに書くと,だめなので気をつけてください.

【VHDL】7セグメントLEDディスプレイ×4に対応した10進数カウンタ

VHDLによる設計

チャタリング除去回路<ELIMINATOR.vhdl>

library IEEE;
use IEEE.std_logic_1164.all;
use IEEE.std_logic_unsigned.all;
use IEEE.std_logic_arith.all;
use IEEE.numeric_std.all;

entity ELIMINATOR is
    port (
        CLK : in std_logic;
        SW : in std_logic;
        SOUT : out std_logic := '1'
    );
end ELIMINATOR;

architecture RTL of ELIMINATOR is
    signal F1 : std_logic := '0';
    signal F2 : std_logic := '0';
    signal TP : std_logic := '1';

    begin
        process(CLK)
        begin
            if (rising_edge(CLK)) then
                F2 <= F1;
                F1 <= SW;
            end if;
        end process;

        TP <= F1 or not F2;

        process(CLK)
        begin
            if (falling_edge(CLK)) then
                SOUT <= TP;
            end if;
        end process;
end RTL;

7セグメントデコーダ点灯回路<SSD_DECODER.vhdl>

表示させたい数字を入力し,どのセグメントを点灯させるかを出力する. 記憶の限りでは,カソードコモンダイナミックタイプだったと思う.

library IEEE;
use IEEE.std_logic_1164.all;
use IEEE.std_logic_unsigned.all;

entity SSD_DECODER is
    port (
        BIN : in std_logic_vector(3 downto 0);
        SSD : out std_logic_vector(7 downto 0)
    );
end SSD_DECODER;

architecture RTL of SSD_DECODER is

    begin
        DECORD : process(BIN)
            begin
                case BIN is
                    when X"0" => SSD <= X"03";
                    when X"1" => SSD <= X"9F";
                    when X"2" => SSD <= X"25";
                    when X"3" => SSD <= X"0D";
                    when X"4" => SSD <= X"99";
                    when X"5" => SSD <= X"49";
                    when X"6" => SSD <= X"41";
                    when X"7" => SSD <= X"1B";
                    when X"8" => SSD <= X"01";
                    when X"9" => SSD <= X"09";
                    when X"A" => SSD <= X"11";
                    when X"B" => SSD <= X"C1";
                    when X"C" => SSD <= X"63";
                    when X"D" => SSD <= X"85";
                    when X"E" => SSD <= X"61";
                    when X"F" => SSD <= X"71";
                    when others => SSD <= "XXXXXXXX";
                end case;
        end process;
end RTL;

マルチプレクサ回路<MULTIPLEXER.vhdl>

今回使用する7セグメントLEDは,ダイナミックタイプのため,複数行を表示させるとき,高速に出力するポートを切り替える必要がある.マルチプレクサ回路では,どのポートに出力するかを決定する.

library IEEE;
use IEEE.std_logic_1164.all;
use IEEE.std_logic_unsigned.all;

entity MULTIPLEXER is
    port (
        INA : in std_logic_vector(3 downto 0);
        INB : in std_logic_vector(3 downto 0);
        INC : in std_logic_vector(3 downto 0);
        IND : in std_logic_vector(3 downto 0);
        SEL : in std_logic_vector(3 downto 0);
        DOUT : out std_logic_vector(3 downto 0)
    );
end MULTIPLEXER;

architecture RTL of MULTIPLEXER is
    begin
        MUX : process(INA, INB, INC, IND, SEL)
            begin
                case SEL is
                    when "1110" => DOUT <= INA;
                    when "1101" => DOUT <= INB;
                    when "1011" => DOUT <= INC;
                    when "0111" => DOUT <= IND;
                    when others => DOUT <= "1110";
                end case;
        end process;
end RTL;

シフトレジスタ回路<Shift_reg.vhdl>

ダイナミックタイプの7セグメントLEDにおいて,シフトレジスタ回路では 出力したいポートが'1'である4bitの数値をマルチプレクサ回路のセレクトポートに出力している.

library IEEE;
use IEEE.std_logic_1164.all;
use IEEE.std_logic_arith.all;
use IEEE.std_logic_unsigned.all;

entity SHIFT_REG is
    port (
        CLK : in std_logic;
        RST : in std_logic;
        SR : out std_logic_vector(3 downto 0)
    );
end SHIFT_REG;

architecture RTL of SHIFT_REG is
    signal srs : std_logic_vector(3 downto 0) := "1110";

    begin
        SR <= srs;


        SHIFTER : process(CLK)
        begin
            if (CLK'event and CLK = '1') then
                if (RST = '0') then
                    srs<="1110";
                end if;
                srs(3) <= srs(2);
                srs(2) <= srs(1);
                srs(1) <= srs(0);
                srs(0) <= srs(3);
            end if;
        end process;
end RTL;

カウンタ回路<Counter.vhdl>

カウンタ回路では,入力された周波数のカウントを行い, 秒数へと変換を行うための回路である.

library IEEE;
use IEEE.std_logic_1164.all;
use IEEE.std_logic_unsigned.all;
use IEEE.std_logic_arith.all;

entity Counter is

    generic (N : integer := 25000);

    port (
        CLK : in std_logic;
        RST : in std_logic;
        CO : out std_logic
    );
end Counter;

architecture RTL of Counter is

    signal CNT : integer:=0;

    begin
        CO <= '1' when (CNT=N) else
              '0';

        COUNT : process(CLK)
        begin


            if (CLK'event and CLK = '1') then
                if (CNT = N) then
                    CNT <= 0;
                else
                    CNT <= CNT + 1;
                end if;
            end if;
        end process;
end RTL;

メイン回路<Watch.vhdl>

メイン回路では,ボタンの入力や1/100秒カウントや1秒カウント,カウントの総数を管理している.

library IEEE;
use IEEE.std_logic_1164.all;
use IEEE.std_logic_unsigned.all;

entity Watch is

    port (
        CLK : in std_logic;
        RST : in std_logic; -- reset
        SAT : in std_logic; -- start
        STP : in std_logic; -- stop
        SEG : out std_logic_vector(7 downto 0);
        SEL : out std_logic_vector(3 downto 0)
    );

end Watch;

architecture RTL of Watch is
    -- component
    component SSD_DECODER is
        port (
            BIN : in std_logic_vector(3 downto 0);
            SSD : out std_logic_vector(7 downto 0)
        );
    end component;

    component MULTIPLEXER is
        port (
            INA : in std_logic_vector(3 downto 0);
            INB : in std_logic_vector(3 downto 0);
            INC : in std_logic_vector(3 downto 0);
            IND : in std_logic_vector(3 downto 0);
            SEL : in std_logic_vector(3 downto 0);
            DOUT : out std_logic_vector(3 downto 0)
        );
    end component;

    component Counter is
        generic (N : integer);
        port (
            CLK : in std_logic;
            RST : in std_logic;
            CO : out std_logic
        );
    end component;

    component SHIFT_REG is
        port (
            CLK : in std_logic;
            RST : in std_logic;
            SR : out std_logic_vector(3 downto 0)
        );
    end component;

    component ELIMINATOR is
        port (
            CLK : in std_logic;
            SW : in std_logic;
            SOUT : out std_logic := '1'
        );
    end component;

    -- signal
    signal co25000 : std_logic;
    signal co1000 : std_logic;
    signal act : std_logic := '0'; -- active or not active
    signal segment : std_logic_vector(15 downto 0) := X"0000";
    signal sr : std_logic_vector(3 downto 0);
    signal dout : std_logic_vector(3 downto 0);
    signal flag : boolean;

    signal ERST : std_logic;
    signal ESAT : std_logic;
    signal ESTP : std_logic;

    begin
        SW_CNT01 : Counter generic map (25000) port map (CLK, RST, co25000);
        SW_CNT1s : Counter generic map (1000) port map (co25000, RST, co1000);
        SW_SHIFT : SHIFT_REG port map (co25000, RST, sr);
        --SW_MUX : MULTIPLEXER port map (INA=>segment(15 downto 12), INB=>segment(11 downto 8),
        --                               INC=>segment(7 downto 4), IND=>segment(3 downto 0),
        --                               SEL=>sr, DOUT=>dout);
        SW_MUX : MULTIPLEXER port map (INA=>segment(3 downto 0), INB=>segment(7 downto 4),
                                       INC=>segment(11 downto 8), IND=>segment(15 downto 12),
                                       SEL=>sr, DOUT=>dout);
        SW_SSD : SSD_DECODER port map (dout, SEG);
        SW_SW1 : ELIMINATOR port map (co25000, RST, ERST);
        SW_SW2 : ELIMINATOR port map (co25000, SAT, ESAT);
        SW_SW3 : ELIMINATOR port map (co25000, STP, ESTP);

        SEL <= sr;

        --process(CLK)
        --begin
        --    if (RST = '0') then
        --        segment <= X"0000";
        --    end if;
        --end process;

        process(co25000)
        begin
            --if (rising_edge(co1000)) then
            if (ERST = '0') then
                segment <= X"0000";
                flag <= False;
            elsif (ESTP = '0') then
                flag <= False;
            elsif (ESAT = '0') then
                flag <= True;
            elsif (rising_edge(co1000) and flag = True) then
                --if (co1000 = '1') then
                    if (segment = X"9999") then
                        segment <= X"0000";
                    elsif ((segment and X"0FFF") = X"0999") then
                        segment(15 downto 12) <= segment(15 downto 12) + '1';
                        segment(11 downto 0) <= X"000";
                    elsif ((segment and X"00FF") = X"0099") then
                        segment(15 downto 8) <= segment(15 downto 8) + '1';
                        segment(7 downto 0) <= X"00";
                    elsif ((segment and X"000F") = X"0009") then
                        segment(15 downto 4) <= segment(15 downto 4) + '1';
                        segment(3 downto 0) <= X"0";
                    else
                        segment <= segment + X"0001";
                        --segment <= segment;
                    end if;
                --end if;
            end if;
        end process;
end RTL;

動作環境など

Quartus II 11.1 sp.1,USB-Blaster,MAXVを使用した. ピンアサインの設定を以下に示す. f:id:zigzackey:20161124132236p:plain 一応,動作確認済みですが,何かの手違いにより, うまく動作しないかもしれません.

【VHDL】Mealy型状態遷移回路を用いた30円の自動販売機の設計

Mealy型状態遷移回路を用いた30円の自動販売機の設計

以下に,Mealy型状態遷移回路を用いた30円の自動販売機のVHDLソースコードを表示する.

-- Vending Machine of Mealy State

library IEEE;
use IEEE.std_logic_1164.all;

entity MealyState30 is
    port (
        CLK, RESET : in std_logic;
        A, B : in std_logic;
        X, Y : out std_logic;
        Z : out std_logic_vector(2 downto 0)
    );
end MealyState30;

architecture RTL of MealyState30 is
    -- type statement
    type type_state is (S0, S1, S2, S3, S4, S5, S6, S7);

    signal state : type_state;
begin
    process(CLK)
    begin
        if (CLK'event and CLK = '1') then
            if (RESET = '0') then
                state <= S0;
            else
                case state is
                    when S0 =>
                        if (A = '1') then
                            state <= S1;
                        elsif (B = '1') then
                            state <= S5;
                        end if;
                    when S1 =>
                        if (A = '1') then
                            state <= S2;
                        elsif (B = '1') then
                            state <= S6;
                        end if;
                    when S2 =>
                        if (A = '1') then
                            state <= S3;
                        elsif (B = '1') then
                            state <= S7;
                        end if;
                    when S3 | S4 | S5 | S6 | S7 =>
                        state <= S0;
                end case;
            end if;
        end if;
    end process;

    -- Output Signal of Mealy State
    X <= '1' when (state = S2 and A = '1') or
                  (state = S0 and B = '1') or
                  (state = S1 and B = '1') or
                  (state = S2 and B = '1') else
         '0';

    Y <= '1' when (state = S2 and A = '1') or
                  (state = S0 and B = '1') or
                  (state = S1 and B = '1') or
                  (state = S2 and B = '1') else
         '0';

    Z <= "010" when (state = S0 and B = '1') else
         "011" when (state = S1 and B = '1') else
         "100" when (state = S2 and B = '1') else
         "000";

end RTL;

今回の状態遷移回路を以下に示す. f:id:zigzackey:20160615170234p:plain

テストベンチ

以下に,テストベンチのVHDLソースコードを示す.

-- TestBench : Vending Machine of Mealy State

library IEEE, STD;
use IEEE.std_logic_1164.all;
-- file input
use STD.textio.all;
use IEEE.std_logic_textio.all;

entity TestBench_MealyState30 is
end TestBench_MealyState30;

architecture TestBench of TestBench_MealyState30 is
    -- component
    component MealyState30
        port (
            CLK, RESET : in std_logic;
            A, B : in std_logic;
            X, Y : out std_logic;
            Z : out std_logic_vector(2 downto 0)
        );
    end component;

    -- signal
    signal CLKt, RESETt : std_logic;
    signal At, Bt, Xt, Yt : std_logic;
    signal Zt : std_logic_vector(2 downto 0);
    -- constant
    constant CLK_PERIOD : time := 50 ns;
    constant RESET_TIME : time := 5 ns;

begin
    DUT : MealyState30 port map (CLKt, RESETt, At, Bt, Xt, Yt, Zt);
    process
    -- file input / output
    file FILEin : TEXT open READ_MODE is "MealyState30.dat";
    file FILEout : TEXT open WRITE_MODE is "MealyState30.out";
    -- variable
    variable LINEin, LINEout : LINE;
    variable CLOCKen, RESETin : std_logic;
    variable Ain, Bin, Xin, Yin : std_logic;
    variable Zin : std_logic_vector(2 downto 0);
    variable colon : string(1 to 2) := " :";
        begin
            readline(FILEin, LINEin);
            read(LINEin, CLOCKen);
            read(LINEin, RESETin);
            read(LINEin, Ain);
            read(LINEin, Bin);
            CLKt <= '0';
            if (CLOCKen = '1') then
                CLKt <= '1' after RESET_TIME,
                        '0' after RESET_TIME + CLK_PERIOD / 2;
            end if;
            RESETt <= RESETin;
            At <= Ain;
            Bt <= Bin;
            read(LINEin, Xin);
            read(LINEin, Yin);
            read(LINEin, Zin);
            wait for CLK_PERIOD;

            write(LINEout, NOW, right, 4);
            write(LINEout, colon, right, 2);
            write(LINEout, Ain, right, 2);
            write(LINEout, Bin, right, 2);
            write(LINEout, Xin, right, 2);
            write(LINEout, Yin, right, 2);
            write(LINEout, Zin, right, 4);

            if ((Xt /= Xin) or (Yt /= Yin) or (Zt /= Zin)) then
                write(LINEout, Xt, right, 3);
                write(LINEout, Yt, right, 2);
                write(LINEout, Zt, right, 4);
            end if;
            writeline(FILEout, LINEout);

            if (endfile(FILEin)) then
                wait;
            end if;
    end process;
end TestBench;

入力情報である「MealyState30.dat」を以下に示す.

0 0 0 0 0 0 000
1 0 0 0 0 0 000
1 1 0 0 0 0 000
1 1 1 0 0 0 000
1 1 1 0 1 0 000
1 1 1 0 0 1 000
1 1 0 0 0 0 000
1 1 0 1 0 1 010
1 1 0 0 0 0 000
1 1 1 0 0 0 000
1 1 1 0 1 0 000
1 1 0 1 0 1 100
1 1 0 0 0 0 000

出力結果である「MealyState30.out」を以下に示す.

50 ns : 0 0 0 0 000
100 ns : 0 0 0 0 000
150 ns : 0 0 0 0 000
200 ns : 1 0 0 0 000
250 ns : 1 0 1 0 000  1 1 000
300 ns : 1 0 0 1 000  0 0 000
350 ns : 0 0 0 0 000
400 ns : 0 1 0 1 010  0 0 000
450 ns : 0 0 0 0 000
500 ns : 1 0 0 0 000
550 ns : 1 0 1 0 000  1 1 000
600 ns : 0 1 0 1 100  0 0 000
650 ns : 0 0 0 0 000

【VHDL】デコーダ回路

3to8デコーダ回路

以下に,3to8デコーダ回路のVHDLソースコードを表示する.

-- Barrel Shifter used Decoder

library IEEE;
use IEEE.std_logic_1164.all;

entity Decoder3to8 is
    port (
        CBA : in std_logic_vector(2 downto 0);
        D : out std_logic_vector(7 downto 0)
    );
end Decoder3to8;

architecture RTL of Decoder3to8 is
    component BShifterNbit
        generic (N : integer);
        port (
            A : in std_logic_vector((2**N) - 1 downto 0);
            S : in std_logic_vector(N - 1 downto 0);
            Z : out std_logic_vector((2**N) - 1 downto 0)
        );
    end component;

    constant N : integer := 3;
    signal tA : std_logic_vector((2**N) - 1 downto 0);

    begin
        tA <= "00000001";

        SHIFTER : BShifterNbit generic map (N) port map (tA, CBA, D);
end RTL;

バレルシフタを使用して,デコーダ回路を作成しています.

バレル・シフト回路&パリティ回路&デコーダ回路のテストベンチ

以下に,3つの回路をテストするテストベンチを示す.

library IEEE;
use IEEE.std_logic_1164.all;
use IEEE.std_logic_arith.all;
use IEEE.std_logic_unsigned.all;

entity TestBench_Parity is
end TestBench_Parity;

architecture TestBench of TestBench_Parity is
    component Decoder3to8
        port (
            CBA : in std_logic_vector(2 downto 0);
            D : out std_logic_vector(7 downto 0)
            );
    end component;

    component ParityNbit
        generic (N : integer);
        port (
            A : in std_logic_vector(N - 1 downto 0);
            P : out std_logic
        );
    end component;

    constant N : integer := 8;
    signal CBAin : std_logic_vector(2 downto 0);
    signal Dout : std_logic_vector(7 downto 0);
    signal Pout : std_logic;

    begin
        DUT0 : Decoder3to8 port map (CBAin, Dout);
        DUT1 : ParityNbit generic map (N) port map (Dout, Pout);

        generator : process
            begin
                CBAin <= "000";
                wait for 10 ns;

                for I in 1 to 100 loop
                    CBAin <= CBAin + 1;
                    wait for 10 ns;
                end loop;
        end process;
end TestBench;

テストベンチの真理値表

以下の真理値表に基づき,テストベンチを作成した. f:id:zigzackey:20160601142859p:plain