TensorFlowで学ぶディープラーニング入門備忘録【第1章】
TensorFlowで学ぶディープラーニング入門 ~畳み込みニューラルネットワーク徹底解説~
- 作者: 中井悦司
- 出版社/メーカー: マイナビ出版
- 発売日: 2016/09/27
- メディア: 単行本(ソフトカバー)
- この商品を含むブログを見る
上記TensorFlowで学ぶディープラーニング入門という本を買ったので、その備忘録。
第1章 TensorFlow入門
1.1 ディープラーニングとTensorFlow
1.1.1 機械学習の考え方
月々の平均気温を予測する場合、月々の平均気温の測定値(データ)になめらかな曲線を描く。与えられたデータの数値をそのまま受け取るのではなく、その背後にある仕組みを考える→データのモデル化
今回の場合、平均気温の測定値を次の四次関数で表すとする。
予想したモデルの正確性の評価にはモデルから予測される値と実際のデータの誤差で判断する。 すなわち、モデル式にx=1,2,...12を代入して得られる予想平均気温をy1,y2,...y12とすれば、
として二乗誤差は表され、これが、月々の予測値と実データの差の二乗を計算した値となっている。(1.2)式の係数w0〜w4を調整することで、それらしい曲線を得られる。(1.2)は係数w0〜w4の関数とみなせるので、誤差関数と呼ぶ。
ここまでを整理すると、
- 与えられたデータをもとにして、未知のデータを予測する数式を考える
- 数式に含まれるパラメータの良し悪しを判断する誤差関数を用意する
- 誤差関数を最小にするようにパラメータの値を決定する
ということになる。これを本書では機械学習モデルの3ステップと呼ぶ。
1.1.2ニューラルネットワークの必要性
あるウイルスに感染しているかしていないかというデータの分類問題を考える。検査結果は2種類の数値(x1,x2)で与えられるものとし、この2つの数値をもとにしてウイルスに感染している確率を求める。本書中の散布図データを見ると、検査結果は大きく直線で分類できそうで、
という数式で表現できそうである。平面上の直線というと、y=ax+bという形式が有名だが、ここではx1とx2を対称に扱うためにこのような形式を用いている。また、この形式の利点として、f(x1,x2)=0が境界となる他に境界から離れるほどに、f(x1,x2)の値が±∞にむかって増加していくという性質がある。 そこで、0から1に向かってなめらかに値が変化するシグモイド関数σ(x)を用意して、これにf(x1,x2)の値を代入すると、検査結果(x1,x2)から感染確率P(x1,x2)を求める関数を作ることができる。ここでシグモイド関数を使う利点としては入力する値がどんなに大きくても小さくても、0〜1の間に出力が収まることである。
ところで、今回与えられたデータは直線で分類できる前提条件に従っていたが、これが、折れ曲がった直線あるいは曲線を用いて分類する必要があるデータであったらどうだろう。単純にはより複雑な数式に置き換えれば良さそうだが、現実には難しい。今回は数値が2種類であったが、これが全部で20種類だったらどうだろう。20次元のグラフが必要になってしまう。
そんな中、より柔軟性が高く様々なデータに対応できる数式を考え出す努力が行われてきたが、それの一つがニューラルネットワークになる。
まず最もシンプルなニューラルネットワークを示す。
左から(x1,x2)という値のペアを入力すると、内部でf(x1,x2)の値が計算されて、それをシグモイド関数σ(x)で0〜1の値に変換したものが、変数zとして出力される。これはニューラルネットワークを構成する最小のユニットでノードと呼ばれる。
このノードを多層に重ねることで、より複雑なニューラルネットワークが得られる。2層のノードからなるニューラルネットワークを以下に示す。
このニューラルネットワークにはw10,w11,w12,w20,w21,w22,w0,w1,w2の9つのパラメータが含まれており、これらの値を調整することで、単なる直線でない、より複雑な境界線が表現できる。 原理的にはノードの数を増やしていけば、どんな複雑な境界線でも書くことが可能だ。しかしながら、パラメータの数が膨大になってそれではパラメータの最適化が終わらない。機械学習におけるニューラルネットワークの挑戦は実際に計算が可能で、かつデータの特性にあった、ニューラルネットワークを構成するという点にある。この挑戦を続ける中で、出てきた特別な形のニューラルネットワークがディープラーニングだ。
1.1.3 ディープラーニングの特徴
ディープラーニングは基本的には多層ニューラルネットワークを用いた機械学習に過ぎないが、単純に層を増やして複雑化するのではなく、解くべき問題に応じて、それぞれのノードに特別な役割を与えたり、ノード間の接続を工夫したりということを行う。
例えば、先程のニューラルネットワークではそれぞれのノードは単純な1次関数とシグモイド関数の組み合わせになっていたが、CNN(畳み込みニューラルネットワーク)では1層目のノードには1次関数ではなく、畳込みフィルターなる関数を用いている。また、その後ろのプーリング層では画像の解像度を落とす処理を行う。これは画像の詳細をあえて消し去り、描かれている物体の本質的な特徴のみを抽出しようとする発想による。このような前処理を行ったデータを更に後段のノードが解析し、なんの画像なのかを判断する。 あるいはRNN(リカレントニューラルネットワーク)という例もある。一般には時系列データを取り扱うものだが、一例として、単語が並んだ文章などの自然言語処理に応用される。
これはある文章が自然な文章か不自然な文章かを見分ける。This is a penという文章に対して、Thisのあとにisが来る確率、isのあとにaが来る確率などを順番に見ていき、全てが高確率になっていれば自然な文章だと判断する。この時、はじめにThisを入力して、次にisを入力する際、その前にThisを入力した際の中間層の出力値もあわせて入力する。先程の中間層にはその前にThisを入力した際の中間層の出力値も合わせて入力する。中間層には最初の単語がThisであったという情報が、isであるという情報だけよりもさらに自然な予測ができる。このように、上図の仕組みでは、過去の入力値の情報が中間層に蓄積されていくことで、より長い単語列に基づいた判断ができる、つまり過去の中間層の値を次の入力に再利用するニューラルネットワークがRNNだ。
1.1.4 TensorFlowによるパラメータの最適化
これからTensorFlowが何をしているか、を(1.2)の誤差関数Eを例に評価する。 (1.2)式に含まれるynはn月の気温を(1.1)式で予測した結果を表す。つまり、
(1.7)式を(1.2)式に代入すると、次式が得られる。
これで誤差関数がわかったので、(1.8)を最小にするw0〜w4を決定する。つまり、(1.8)をw0〜w4のそれぞれで偏微分した値を0とした、次の連立方程式を解くことになる。
ここで、話を簡単にするために、次の2変数関数を用いて、なぜ上式の条件で、Eが最小になるかを説明する。
これの偏微分は、
またこれらを並べたベクトルを次の記号で表して、関数h(x1,x2)の勾配ベクトルと呼ぶ。
勾配ベクトルはすり鉢の壁を登っていく方向に一致し、勾配ベクトルの大きさは壁を登る傾きに一致する。壁の傾きが大きいほど、勾配ベクトルも長くなる。すり鉢の壁を降りていくに従い、傾きは小さくなるので、勾配ベクトルの大きさもだんだん小さくなる。この例の場合、最終的に原点(0,0)に達したところで、h(x1,x2)は最小となるので、勾配ベクトルの大きさも0になる。つまり、h(x1,x2)を最小にする(x1,x2)は∇h(x1,x2)=0という条件で決まることになる。現在の位置をx=(x1,x2)T(注:Tは転置の意味)とすれば、新しい位置は
として表され、これを何度も繰り返すと、どこから出発したとしても、次第に原点に近づいていく。このように勾配ベクトルを計算して、反対方向にパラメータを修正するアルゴリズムを勾配降下法と呼ぶ。気をつけならないのが、パラメータを修正する分量だ。例として以下の例に適用してみよう。
それぞれの勾配ベクトルは
例えば、式(1.17)を適用しながら移動すると始点を(1,-1)と仮定し、(1,-1)-3/2(1,-1)=(-1/2,1/2)→(-1/2,1/2)-3/2(-1/2,1/2)=(1/4,-1/4)→(1/4,-1/4)-3/2(1/4,-1/4)=(-1/8,1/8)などと、0に漸近していくことが分かる。一方、式(1.18)を適用していくと、始点を(1,-1)として、(1,-1)-5/2(1,-1)=(-3/2,3/2)→(-3/2,3/2)-5/2(-3/2,3/2)=(3,-3)などと、原点から離れていってしまうことが分かる。このように、うまくパラメータが原点にうまく近づくことを収束する、逆に最小値から遠ざかってしまうことを発散するという。そして、この移動量は学習率εとして表現され、式(1.14)は
に変形できる。この学習率は一回の更新でパラメータをどの程度修正するかのパラメータになり、小さすぎると最小値に達するまでの時間がかかる一方、大きすぎると、パラメータが発散して最適化ができない。
なお、今回は2変数関数で考えたが、当然、変数が増えても同様の考え方が適用可能だ。式(1.8)の二乗誤差Eを最小にするパラメータw0〜w4を決定する場合であれば、これを並べたベクトルw=(w0,w1,w2,w3)Tとして、
を計算すれば良い。この時(1.20)でパラメータを更新するたびに、その点における勾配ベクトルの値を(1.21)で計算し直す事が必要だ。
1.2 環境準備
TensorFlowの環境準備をCentOS7のDockerコンテナでJupyterを起動して、外部のwebブラウザからアクセスして使用するまでの環境準備が説明されている。私の場合、MacOS(El Capitan)なので、巻末付録を参考に環境構築した。
Macの場合も、DockerコンテナでJupyterを起動して、ローカルのwebブラウザからアクセスして使用する。 ①まず以下の、Docker HPよりDocker for Macをダウンロードする。
②インストールは特に難しくないはずなので、設定へ
上部メニューバーのクジラのアイコンからPreferences→MemoryとCPUの使用率をそれぞれ4GB、4個以上にして、再起動する。
③Macのターミナルより、以下を打つ。
$ mkdir $HOME/data $ docker run -itd --name jupyter -p 8888:8888 -p 6006:6006 \ -v $HOME/data:/root/notebook -e PASSWORD=passw0rd \ enakai00/jupyter_tensorflow:0.9.0-cp27
実際にうってみた感じは以下のよう。
-e PASSWORDオプションはブラウザからJupyterにアクセスする際の認証パスワードである。この手順でコンテナを起動した場合、Jupyterで作成したノートブックのファイルは、ユーザのホームディレクトリーの下のdataディレクトリに保存される。ブラウザからJupyterに接続する場合、http://localhost:8888にアクセスし、TensorBoardの画面のアクセスにはhttp://localhost:6006からアクセスする。
1.2.2 Jupyterの使いかた
Jupyterではノートブックと呼ばれるファイルを開いて、その中でPythonのコマンドやプログラムを対話的に実行していく。①つのノートブックは複数のセルに分かれており、1つのセルには実行するべきコマンドとその実行結果がセットで記録される。 早速、http://localhost:8888にアクセスし、ノートブックを作ってみる。
このあたりは本を買っていればサッと飛ばせる話なので省略する。
1.3 TensorFlowクイックツアー
まずは月々の平均気温を予測する問題をTensorFlowを用いて解いていく。
1.3.1 多次元配列によるモデルの実現
TensorFlowでは計算に用いるデータはすべて多次元配列として表現する。例えば、n月の予測気温ynは式(1.7)を行列を用いると、
として表される。さらに12ヶ月分のデータは
として表される。Xはトレーニングセットとして与えられたデータから構成される。TensorFlowではこのようなトレーニングセットを保存する変数をPlaceholderと呼ぶ。次に、wはこれから最適化を実施するパラメータでありVariableと呼ぶ。そして、yはPlaceholderとVariableから計算される値になる。 パラメータの最適化を実施するには二乗誤差を求める必要があるが、これは予測値yとトレーニングセットのデータtから計算されるものである。tは次のようにn月の平均気温を縦に並べたベクトルである。
ただし、このままでは(1.6)を行列形式にはできないので新しい演算を定義する。一般のベクトルv=(v1,v2,...,v_N)Tに対して、次の演算を定義する。
squareは、ベクトルの各成分を二乗するもので、reduce_sumはベクトルの各成分の和を計算する。これらの演算を利用すると、(1.6)は
と表される。これで、誤差関数を行列方式、多次元配列方式で表現できた。
1.3.2 TensorFlowのコードによる表現
ここからは、実際にJupyter上でTensorFlowのコードを実行する。
import tensorflow as tf import numpy as np import matplotlib.pyplot as plt
これはライブラリのインポートなので、問題ないと思う。
x = tf.placeholder(tf.float32, [None, 5]) w = tf.Variable(tf.zeros([5, 1])) y = tf.matmul(x, w)
トレーニングセットのデータを保持するXを用意するが、[None, 5]と引数を指定している。これは任意の行数と5列の行列で初期化することを意味する。
次に、誤差関数を表現する。
t = tf.placeholder(tf.float32, [None, 1]) loss = tf.reduce_sum(tf.square(y-t))
tは12×1行列に相当するが、データ数の部分を任意に取れるようにするため、[None, 1]というサイズ指定を行っている。 次に、トレーニングアルゴリズムを選択する。
train_step = tf.train.AdamOptimizer().minimize(loss)
tf.train.AdamOptimizer()は与えられたトレーニングセットのデータから誤差関数を計算して、その勾配ベクトルの反対方向にパラメータを修正するものだ。学習率は自動的に調整する機能を持っている。
sess = tf.Session() sess.run(tf.initialize_all_variables())
まずは実行環境となるセッションを用意する。 次に、トレーニングアルゴリズムの実行をセッション内で行う。
train_t = np.array([5.2, 5.7, 8.6, 14.9, 18.2, 20.4, 25.5, 26.4, 22.8, 17.5, 11.1, 6.6]) train_t = train_t.reshape([12,1]) train_x = np.zeros([12, 5]) for row, month in enumerate(range(1, 13)): for col, n in enumerate(range(0, 5)): train_x[row][col] = month**n
ここでは、tとXをarrayオブジェクトとして用意した。
i = 0 for _ in range(100000): i += 1 sess.run(train_step, feed_dict={x:train_x, train_t}) if i % 10000 == 0: loss_val = sess.run(loss, feed_dict={x:train_x, train_t}) print ('Step: %d, Loss: %f' % (i, loss_val))
ここでは、勾配降下法によるパラメータの最適化を実施している。
for _ in range(100000): i += 1 sess.run(train_step, feed_dict={x:train_x, t:train_t}) if i % 10000 == 0: loss_val = sess.run(loss, feed_dict={x:train_x, t:train_t}) print ('Step: %d, Loss: %f' % (i, loss_val))
更に100000回だけトレーニングを実施している。すると、Lossがあるところから増加に転じる。そこでトレーニングを打ち切って、その時点でのパラメータの値を確認する。
w_val = sess.run(w)
print w_val
続いて、この結果を用いて、予測気温を表す関数を定義する。
def predict(x): result = 0.0 for n in range(0, 5): result += w_val[n][0] * x**n return result fig = plt.figure() subplot = fig.add_subplot(1,1,1) subplot.set_xlim(1,12) subplot.scatter(range(1,13), train_t) linex = np.linspace(1,12,100) liney = predict(linex) subplot.plot(linex, liney)
上のコードには関数をプロットするものも入っており、これを実行すると、以下のグラフが得られる。
ここまでで、第1章は終わりになる。
正規表現技術入門 備忘録(第1章)
業務アプリでオートコンプリートとかその辺りを触っている関係で正規表現技術入門という本を読んでいる。正規表現は全くの未経験なので、まずは深いところはスキップして、基本的なところを抑えていこうと思う。なお、現時点で正規表現の専門的な知識は必要としていないので、第1章だけの備忘録になる。
正規表現技術入門 ――最新エンジン実装と理論的背景 (WEB+DB PRESS plus)
- 作者: 新屋良磨,鈴木勇介,高田謙
- 出版社/メーカー: 技術評論社
- 発売日: 2015/04/14
- メディア: 単行本(ソフトカバー)
- この商品を含むブログ (1件) を見る
正規表現とは何か
正規表現は英語で「regular expression」と言い、一種の表現(ものの書き方)である。 例えば、
0|1|2|3|4|5|6|7|8|9
というのも一種の正規表現で、0から9までの数字という意味を表している。 同様に、
1(0|1|2|3|4|5|6|7|8|9)
と書けば、10から19までの2桁の数字を意味する。このように丸括弧は正規表現を部品ごとに区切るために使われる。
もう少し複雑な例を見てみる。
03-[0-9][0-9][0-9][0-9]-[0-9][0-9][0-9][0-9]
という正規表現は03から始まる電話番号を表している。さらに、数学でx+x+x+xを4xと記述できるように、正規表現[0-9][0-9][0-9][0-9]は[0-9]{4}と短く書くことができる。{4}が4回繰り返すことを示していて、これを量指定子(quantifier)などとよんだりする。よって、上の例は、
03-[0-9]{4}-[0-9]{4}
さらには、
03(-[0-9]{4}){2}
[0-9]は\dとも書けるので最終的には
03(-\d{4}){2}
とかける。
正規表現において、特別な意味を持ったメタ文字と意味を持たないリテラルが存在する。上の例で言うと、[]-\dなどがメタ文字、0や9がリテラルだ。
さて、このような正規表現は実際にはどのように使われているのだろうか。身近なところではHTML5でメールアドレスを入力するフォームに
^[a-zA-Z0-9.!#$%&'*+/=?^_`{|}~-]+@[a-zA-Z0-9](?:[a-zA-Z0-9-]{0,61}[a-zA-Z0-9])?(?:\.[a-zA-Z0-9](?:[a-zA-Z0-9-]{0,61}[a-zA-Z0-9])?)*$
という正規表現が使われている。
正規表現の演算
正規表現の基本演算は
- 連接
- 選択
- 繰り返し
である。上のHTML5の正規表現のように[a-zA-Z0-9]と[a-zA-Z0-9-]{0,61}などとつなげて構成する。このつなげる演算を連接と呼ぶ。連接には特に演算子として特別な記号はない。hatenaという文字はhとaとtと、、を連接し成り立っているが、当たり前なため記号はないということだ。 正規表現A|BはAもしくはBという意味を表す。この|で並べる演算を選択もしくは和と呼ぶ。 次に繰り返しだが、正規表現\dは任意の長さの数字列を表現している。は0回以上、いくらでも繰り返されているパターンを表現する。
演算子の結合順位
四則演算で、掛け算の優先順位が高いように演算子にも順位があり、それは
繰り返し > 連接 > 選択
というものだ。
正規表現のシンタックスシュガー
本来、正規表現には上記の3演算だけで事足りるはずだが、3演算だけで書くと複雑になってしまう場合がある。その場合に、簡単に書くための構文が追加されている。それがシンタックスシュガーだ。
プラス演算
+は1回以上の任意回の繰り返しを意味する。ab+cという正規表現があった時、acは該当せず、abcやabbbcなどのように少なくとも1文字以上のbを含んだ文字列を表現する。ab*cという正規表現は0回の繰り返しも含まれ、acという文字列にもマッチする。
疑問符演算
?をパターンの後ろにつけることで、パターンの0回か1回の繰り返しを表す。0回か1回の繰り返しというのは現れるか現れないかとも言い換えられる。例えば、https?://hogehoge.jpはHTTPとHTTPSのどちらもマッチする。s?となっておりあってもなくても良いからだ。
範囲量指定子
演算子{n,m}はn回からm回までの繰り返しを実現する演算子である。例えば、x{1,5}はxの1から5回の繰り返しを表し、x|xx|xxx|xxxx|xxxxxという正規表現と同様の表現になる。x{3,3}のように最小と最大の数字を同じ数字に揃えれば、ピッタリ3回の繰り返しを表現する。この場合、x{3}ともかける。範囲量指定子には{1, 3}のようにスペースを入れたり、{3,1}などと最大最小を逆転した書き方をしてはならない。
ドット
ドットは任意の一文字を表す。たとえばr.*eはrで始まり、eで終わる全部の文字列がマッチする。
文字クラス
0から9までの数字は[0-9]、小文字のみのアルファベットは[a-z]、大文字のみのアルファベットは[A-Z]、大文字も小文字も含むアルファベットは[a-zA-Z]と表す。文字クラスにおける[]の内部では-は範囲指定の記号として特別扱いされる。[a-z]のようにハイフンの前後に表現したい文字範囲の先頭と末尾の文字を記述することで文字範囲を表現する。^は否定を意味する。[^0-9A-Za-z]と書けば、数字やアルファベット以外の文字にマッチする。
エスケープシーケンス
エスケープシーケンスは\を用いて表す。
- \a … ベル文字
- \f … 改ページ
- \t … タブ
- \n … 改行
- \r … 復帰
- \v … 垂直タブ
- \d … 数字
- \D … 数字以外
- \w … 文字列記号
- \W … 文字列記号以外
- \s … スペース
- \S … スペース以外
アンカー
位置を表すアンカーは以下の様なものがある。Sublimeの置換などでもこれは使えるので便利。
- ^ … 行頭
- $ … 行末
- \A … テキスト先頭
- \b … 文字列の間
- \B … 文字列の間以外
- \z … テキスト終端
キャプチャと置換
「文字列がどのようにパターンにマッチするか」という情報を使って文字列を操作するキャプチャと置換を扱う。 キャプチャの前に、正規表現マッチングについており細かい点を解説する。
文字列の部位
文字列には部位がある。接頭辞(prefix)、接尾辞(suffix)、部分文字列(substring)だ。文字列sについて文字列tがsの
- 接頭辞であるとは、tがsの先頭の文字列であること
- 接尾辞であるとは、tがsの末尾の文字列であること
- 部分文字列であるとは、sがtを含むこと
を意味する。
マッチングの種類
正規表現によるマッチングには大きく分けて、以下の4種類がある。
- 完全一致:正規表現が与えられた文字列の全体にマッチ
- 前方一致:正規表現が与えられた文字列の接頭辞にマッチ
- 後方一致:正規表現が与えられた文字列の接尾辞にマッチ
- 部分一致:正規表現が与えられた文字列の部分文字列にマッチ
例えば、PythonやJavaScriptの標準の正規表現では、前方一致にmatch()メソッド、部分一致にsearch()メソッドを提供している。
丸括弧を使って正規表現を部分的に括ることができるが、丸括弧でまとめられた正規表現の一部はサブパターンと呼ぶ。サブパターンにマッチした部分文字列をサブマッチと呼ぶ。
- 部分一致がデフォルトな状況でのマッチングの種類の明示
マッチングの種類 | 正規表現 |
---|---|
部分一致 | regex |
完全一致 | ^regex$ |
前方一致 | ^regex |
後方一致 | regex$ |
- 完全一致がデフォルトな状況でのマッチングの種類の明示
マッチングの種類 | 正規表現 |
---|---|
部分一致 | regex |
完全一致 | .regex. |
前方一致 | regex.* |
後方一致 | .*regex |
例えば、(\d+): (\w+) prime.という正規表現には(\d+)と(\w+)の2つのサブパターンが含まれている。この正規表現に対して、57: Grothendieck prime.という文字列はマッチする。このとき、(\d+)に対しては57が、(\w+)にはGrothendieckが部分文字列としてマッチしている。よって、57とGrothendieckはそれぞれ(\d+)と(\w+)に対応するサブマッチとなる。
キャプチャ
正規表現と文字列からサブマッチを抜き出すことをキャプチャという。 正規表現のあるサブパターンに対するサブマッチを取得するためには明示的に、特定のサブパターンに対するサブマッチを指定する必要がある。これには、
- 順番で指定する方法
- 名前で指定する方法
がある。
順番で指定する方法
サブパターンには自然な順番というものが存在する。1から順に開き括弧が左側にあるほど小さい番号を付けるという順序付けだ。たとえば、日/月/年を表す正規表現(\d{2})/(\d{2})/(\d{4})には日の2桁が1番、月の2桁が2番、年の4桁に3番という順番がつけられている。
名前で指定する方法
順番で指定する方法は、単純な一方、正規表現の変更に弱い。そこで、名前付きキャプチャを使う。名前付きキャプチャでは、サブパターンに好きな名前をつけて、その名前経由でサブマッチを取得することができる。PerlやRubyでは(?
$day = '14/11/1988'; if ($day =~ /(?<d>\d{2})\/(?<m>\d{2}\/(?<y>\d{4})/) { print "$+{y} 年 $+{m} 月 $+{d} 日"; #=> 1988年 11 月 14 日
正規表現の拡張機能
先読み
先読みとは、「与えられた正規表現がマッチする文字列が直後に来る位置」と正規表現を使って位置を指定することができる機能である。 マッチング対象文字列が「abracadabra」だったとして、「a(?=..a)」はどの部分文字列にマッチし得るのか。実は「a(?=..a)」という正規表現は2箇所の「a」にしかマッチしない。先読み部分の正規表現「(?=..a)」はあくまで3文字先にaが来るという位置にマッチするためだ。
再帰
- A(?R)|B
- A(A(?R)|B)|B
- A(A(A(A(A(...)|B)|B)|B)|B)|B
- A*B
上記再帰表現を展開しているとAが0回以上続いて、Bで終わるというパターンを表現している事がわかる。
後方参照
後方参照とはキャプチャによって取得した部分文字列をその正規表現の中で参照する機能だ。 (.) \1 は任意の文字列をスペースを挟んで2回繰り返した文字列にマッチする正規表現だ。 つまり\1の部分が(.)を参照しており、 (.) (.) と等価に置き換えられる。
以上で、大体の1章の内容になる。2章以降は
- 第2章 正規表現の歴史
- 第3章 プログラマのための一歩進んだ正規表現
- 第4章 DFA型エンジン
- 第5章 VM型エンジン
- 第6章 正規表現エンジンの三大技術動向
- 第7章 正規表現の落とし穴
- 第8章 正規表現を超えて
といった進み方をするが、今回は一般教養として正規表現を使えるようになるのが目的だったので、一旦閉める。検索エンジンやコンパイラやプログラミング言語を作りたい方などは第2章以降も役に立つだろう。
FPGA入門 備忘録④ 〜順序回路編〜
備忘録③の続きになる。
RSフリップフロップ
上図はORゲートを用いた状態記憶回路である。ORゲートの出力Qが一方の入力に帰還しているため入力Sが一度1になると、出力Qはその後、入力Sの状態にかかわらず1を保持し続ける。
上図は、最初の回路にリセット入力Rを追加したもので、これにより出力Qを0に戻すことが可能になる。 以下にRSフリップフロップの真理値表を示す。入力SとRが共に0の時は共に0となる直前の出力Qが保持される。ただし、直前の入力が共に0の時は、いずれの値が保持されるかは分からない。 Rが0でSが1の時、Q=1、Rが1でSが0の時はQ=0となる。R=1、S=1の時、Q=1となるが、この状態からR=0、S=0となった場合に、Q=1の保持が確実でないのは各ゲートの遅延などでR=1、S=0となってからR=0、S=0となる可能性があるためだ。そのため、R=1、S=1は一般に使わない。
入力 | 出力 | |
---|---|---|
R | S | Q |
0 | 0 | 前の状態 |
0 | 1 | 1 |
1 | 0 | 0 |
1 | 1 | 1(使用禁止) |
上に簡略化の流れを示す。まずひとつ目の図はORゲートをNORゲートに変更して、ふたつ目の図のように書ける。次に、ふたつ目の図のANDゲートはNOTゲートと組み合わせて、3つめの図のようにNORゲートに置き換え可能だ。ここで、各NORゲートの出力をそれぞれQ、Q_とすると、4つ目の図のようになる。
4つ目の図の真理値表を書くと、
入力 | 出力 | ||
---|---|---|---|
R | S | Q | Q'|Q_ |
0 | 0 | 前の状態 | 前の状態|前の状態 |
0 | 1 | 1 | 1|0 |
1 | 0 | 0 | 0|1 |
1 | 1 | 1 | 0|0 |
ここで、前述のようにRとSが共に1の時に使わないのであれば、Q=Q'として更に、5つ目の図のように簡略化できる。
入力 | 出力 | ||
---|---|---|---|
R | S | Q | Q_ |
0 | 1 | 1 | 0 |
1 | 0 | 0 | 1 |
1 | 1 | 0(使用禁止) | 0(使用禁止) |
最後に、5つ目の図は6つ目のよく見る図のように簡略化できる。 簡略化しNORゲートのみを使って表すことで、回路規模が小さくできる。XilinxのFPGAではプリミティブとして、後述のDフリップフロップと同期セット・リセット入力付きDフリップフロップなどが用意されている。 ただ、これらのプリミティブを用いずに基本ゲート(Look Up Table)のみを用いて、フリップフロップを構成することができる。
module RSFF_VERILOG(SW0, SW1, LED0, LED1); input SW0; input SW1; output LED0; output LED1; assign LED0 = ~(SW0 | LED1); assign LED1 = ~(SW1 | LED0); endmodule
Dフリップフロップ
RSフリップフロップはSにセットした値、もしくはRでリセットした値を時間経過に関係なく保持することができる1bitのメモリだ。しかし、その値を保持するためにはS=0、R=0という状態を保持する必要がある。これではまだ使い勝手が悪い。つまり実際の回路ではある瞬間のみに値の書き込みを行い、それ以降はSおよびRの状態と無関係に値を保持する動作を求められる。そのような動作を実現するために書き込む値を入力する端子と書き込み制御を行う端子を分離したフリップフロップの一つがDフリップフロップだ。このDフリップフロップと後で説明するクロックイネーブル入力付きDフリップフロップ、及び基本ゲートがあればほとんどの完全同期式回路を記述できる。
以下にDフリップフロップの回路シンボルと真理値表を示す。
入力 | 出力 | ||
---|---|---|---|
D | CLK | Q | |
0 | ↑ | 0 | |
1 | ↑ | 1 | |
0 | - | 直前の値 | |
1 | - | 直前の値 |
DフリップフロップはDの入力状態をCLKから入力される信号の立ち上がりエッジで取り込み、Qに出力する。Qの出力は次のCLKの立ち上がりエッジが来るまで、変化しない。特に断りがなければ、立ち上がりエッジで取り込むポジティブエッジタイプを使う。立ち下がりで取り込むネガティブエッジタイプのシンボルを参考までに以下に示す。
RSフリップフロップはRとSを用いて、書き込むデータを表すとともに書き込むか、保持するかの動作の制御も行っていた。これに対し、Dフリップフロップではデータを入力するDと書き込み制御を行うCLKという風にデータ入力と制御入力を分離している。このデータと制御の分離は非常に重要で、大きな回路規模の設計を行うときには、データパスの設計なのか、制御パスの設計なのかを常に意識する必要がある。
module DFF_VERILOG(SW0, SW1, LED0); input SW0; input SW1; output LED0; reg LED0; always @(posedge SW1) begin LED0 <= SW0; end endmodule
always文のところで、DFFの制御を書いている。SW1の立ち上がりエッジで、SW0の値が取り込まれ、LED0に出力される。
セットアップ時間とホールド時間
DフリップフロップはCLKに入力される信号の立ち上がりエッジでデータを取り込む。したがって、データ入力はCLKの立ち上がりエッジ以前に確定している必要がある。このCLKの立ち上がりエッジからデータが確定していなければならない時間がセットアップ時間tsである。 また、内部のRS-FFが安定し、入力データがDフリップフロップに取り込まれるまでには時間を要する。したがって、入力データはCLKの立ち上がりエッジから特定の時間以上保持する必要があり、この時間がホールド時間thである。よって、ts+thの期間はデータ入力は0または1のいずれかに保持しなければならない。
トグルフリップフロップ
トグルフリップフロップの回路図を示す。Dフリップフロップの出力Qが自己のデータ自己DにNOTゲート経由で帰還されている。
Dフリップフロップの初期状態Q=0とすれば、Qは1となる。最初のクロックの立ち上がりで、Q=1が取り込まれ、直後にQ=1、Q=0となる。次のクロックの立ち上がりで、Q=0が取り込まれるので、直後にQ=0、Q=1となる。出力Qから出力される信号は、入力されるクロック周波数の半分の周波数となるため、この回路を2分周回路という。
上の回路は常にクロック信号の1/2の周波数の信号を生成するが、これを以下のように変更すると、制御信号T=1の間だけ1/2の周波数の信号を出力し、T=0のときは前の値を保持することができる。
この回路をシンボルで書くと以下のようになる。
module TFF_VERILOG(PSW0, LED0); input PSW0; output LED0; reg LED0; always @ (posed PSW0) begin LED0 <= ~LED0; end endmodule
クロックイネーブル
前述のDフリップフロップでは次のクロックの立ち上がりまでの期間、データの記憶が可能だが、もっと長い期間データを記憶しておくことが必要だ。そこで、次のクロックが来ても、データを更新しないような制御入力端子を追加したものが、クロックイネーブルだ。
クロックイネーブル付きDフリップフロップではCE入力が0のときにはいくらエッジが来ても出力Qは変化しない。CEが1の時のクロックの立ち上がりエッジでD入力からのデータを取り込み、出力Qへ反映する。
内部回路を以下に示す。クロック入力を抑制するにはCLKにANDゲートを挿入する方法もあるが、完全同期式回路ではフリップフロップのCLKにゲートを挿入することは禁止される。
代わりに、以下の図のようにフリップフロップの入力Dの前に幾つかのゲートを挿入する。
外部入力CEにより、現在のQの出力値を保持するか、外部入力Dからの値を取り込むか選択するようになっている。マルチプレクサはS0=0のとき、Q=D0、S0=1の時はQ=D1となる。 以下にverilogのコードを示す。
module DFFE_VERILOG(SW0, SW1, SW2, LED0); input SW0; input SW1; input SW2; output LED0; reg LED0; always @(posedge SW0) begin if (SW1 == 1'b1) begin LED0 <= SW2; end end endmodule
セットリセット
フリップフロップに保持されている値を強制的に1あるいは0にするための制御入力がそれぞれセット、リセットである。Dフリップフロップを例にセット入力端子Sとリセット入力端子Rを追加した回路シンボルと内部回路を以下に示す。
verilogのコードを以下に示す。
module DFFERS_VERILOG(SW0, SW1, SW2, SW3, SW4, LED0); input SW0; input SW1; input SW2; input SW3; input SW4; output LED0; reg LED0; always @(posedge SW0) begin if (SW == 1'b1) begin LED0 <= 1'b0; end else if (SW2 == 1'b1) begin LED0 <= 1'b1; end else if (SW3 == 1'b1) begin LED0 <= SW4; end end endmodule
クロックイネーブル/セットリセット付きトグルフリップフロップ
クロックイネーブルやセットリセットの機能についてはDフリップフロップに限られず、他のフリップフロップにも追加できる。また、クロックイネーブル機能とセットリセット機能は同時に追加できる。以下はクロックイネーブル/セットリセット付きトグルフリップフロップの回路シンボルと内部回路である。
verilogのコードを示す。
module TFFERS_VERILOG(SW0, SW1, SW2, SW3, LED0); input SW0; input SW1; input SW2; input SW3; output LED0; reg LED0; always @(posed SW0) begin if (SW1 == 1'b1) begin LED0 <= 1'b0; end else if (SW2 == 1'b1) begin LED0 <= 1'b1; else if (SW3 == 1'b1) begin LED0 <= ~LED0; end end endmodule
制御端子の優先順位はリセットが最優先で、次にセット、クロックイネーブルと続き、トグル入力は最も優先順位が低くなっている。
完全同期式回路
複数のフリップフロップを用いる場合、気をつけなければならないのが、クロックスキューだ。以下の回路のようにすべての順序回路の状態変化が同時に起こる回路を完全同期式回路という。こうすることで、すべての回路の0,1の変化がクロックに同期して起こるため、1クロックを単位とした時間の概念を回路設計に取り入れることができる。
2つのDフリップフロップの例
以下に2つのDフリップフロップを直列接続した回路を示す。
D1に入力される信号は1クロック遅れてD2に入力され、さらに1クロック遅れた信号がQ2から出力される。 D1に入力されるパルスは2番めのパルスの立ち上がりで最初のDフリップフロップに取り込まれる。FD1の出力であるD2は直後に1を立ち上がる。この時後段のフリップフロップは2番めのクロックの立ち上がりで、D2の状態を取り込むが、このとき D2はまだ0であるため、FD2には0が取り込まれ、出力Q2は0のままだ。 FD2に1が取り込まれるのは3番めのクロックの立ち上がりで、3番めのクロックが立ち上がるとき、D1は0となっているので、FD1には0が取り込まれ、直後にD2は0に立ち下がる。しかし、同時にFD2がD2の状態1を取り込むので、直後に出力Q2が1となる。
ここで、注意すべきはD2の信号で、特性が同一の2つのDフリップフロップに全く同じタイミングで立ち上がるクロック信号が入力されているため、状態が変わる直前の状態が取り込まれている。
しかし、この動作が保証されるためには2つの条件があり、1つはセットアップ時間を満たしているかということ。前段のDフリップフロップの出力は必ずクロックの立ち上がりで、遷移するので、後段のDフリップフロップに入力される信号は1つ前のクロックの立ち上がりから、遷移するまでの遅れ時間TCKO経過してから確定している。
もう一つはホールド時間を満たしているかということで、前段のDフリップフロップの出力は、クロックの立ち上がりから、状態遷移するまでに遅れ時間がある。この遅れ時間が、後段のDフリップフロップの入力のホールド時間より長くなければならない。
FPGAにはクロック供給用にスキューが小さくなるように設計されたグローバルラインと呼ばれる専用配線がある。XilinxのFPGAではBUFGというプリミティブで使用できる。また、外部のオシレータ等をこのグローバルラインに接続するには、専用のGCLKというピンと、IBUFGというプリミティブを使用する必要がある。
カウンタ
2bitバイナリカウンタの内部回路を以下に示す。最初のトグルフリップフロップは2分周回路となり、後段のトグルフリップフロップはQ0=1の時にクロックの立ち上がりで値を反転させるので、出力Q1の信号周波数はQ0の更に1/2、つまり入力クロックの1/4の周波数となる。結果、入力をCLK、出力をQ1とした時、本回路は4分周回路となる。
更にトグルフリップフロップを追加して、以下の様な回路を作ると、出力Q2はクロック信号の1/8、出力Q3は1/16の周波数となる。 ここで、出力Q0をLSB、Q3をMSBとして、Q0〜Q3を4bitのデータとして捉えると、0000b〜1111bまでクロックの立ち上がりが来るごとにインクリメントしていることがわかり、このように出力が2進数となっているカウンタをバイナリカウンタという。
最後に、2bitバイナリカウンタ、4bitバイナリカウンタのverilogコードを示す。
module CB2_VERILOG(CLK, Q); input CLK; output [1:0] Q; reg [1:0] Q; always @(posedge CLK) begin Q <= Q + 1'b1; end endmodule
module CB4_VERILOG(CLK, R, CE, Q, TC, CEO); input CLK; input R; input CE; output [3:0] Q; output TC; output CEO; reg [3:0] Q; always @(posedge CLK) begin if (R == 1'b1) begin Q <= 4'd0; end else if (CE == 1'b1) begin Q <= Q + 1'b1; end end assign TC = &Q; assign CEO = &Q & CE; endmodule
FPGA入門 備忘録③ ~組み合わせ回路編~
備忘録②の続き。
加算回路
半加算器
2進数の足し算は、
0 + 0 = 0 0 + 1 = 1 1 + 0 = 1 1 + 1 = 10
と書ける。これの足される数を入力A、足す数を入力B、その桁の加算結果を出力S、桁上りを出力COとして真理値表で示すと、以下のようになる。COは桁上りが生じたかどうかを表すビットである。
A | B | S | CO |
---|---|---|---|
0 | 0 | 0 | 0 |
0 | 1 | 1 | 0 |
1 | 0 | 1 | 0 |
1 | 1 | 0 | 1 |
この真理値表から回路を構成すると以下のようになる。
この加算回路は下の桁からの桁上りを考慮しておらず、下からの桁上りがない最下位ビットのみにしか使えない。これを半加算器という。
全加算器
桁上りが生じたかどうかを表す出力COは2桁目以降、そのまま加算すればよい。この下からの桁上りを考慮して半加算器に、ビットの入力を追加した加算回路を全加算器と呼ぶ。以下に全加算器の真理値表と回路図を示す。
A | B | CI | S | CO |
---|---|---|---|---|
0 | 0 | 0 | 0 | 0 |
0 | 0 | 1 | 1 | 0 |
0 | 1 | 0 | 1 | 0 |
0 | 1 | 1 | 0 | 1 |
1 | 0 | 0 | 1 | 0 |
1 | 0 | 1 | 0 | 1 |
1 | 1 | 0 | 0 | 1 |
1 | 1 | 1 | 1 | 1 |
次に、全加算器を用いた3bit加算回路の回路図を見てみよう。
変数 | 変数の各ビット | 信号名 |
---|---|---|
被加数 | A0 (LSB) | SW0 |
A1 | SW1 | |
A2 (MSB) | SW2 | |
加数 | B0 (LSB) | SW3 |
B1 | SW4 | |
B2 (MSB) | SW5 | |
演算結果 | S0 (LSB) | LED0 |
S1 | LED1 | |
S2 (MSB) | LED2 | |
桁上げ出力 | CO | LED3 |
AとBを加算し、LEDに出力する回路になっている。これをverilogで書くと、
module FA3_VERILOG(CO, S, A, B); input [2:0] A; input [2:0] B; output CO; output [2:0] S; assign {CO, S} = A + B; endmodule
assign {CO, S} = A + Bのところだが、まず左辺はCOは1bitで、Sは3bit、合計で4bitである。右辺は3bit同士の論理和で4bitになる。
減算回路
半減算器
2進数の引き算は、
0 - 0 = 0 0 - 1 = 11 1 - 0 = 1 1 - 1 = 0
と書ける。これの足される数を入力A、足す数を入力B、その桁の加算結果を出力S、桁上りを出力COとして真理値表で示すと、以下のようになる。BOは桁借りが生じたかどうかを表すビットである。
A | B | D | BO |
---|---|---|---|
0 | 0 | 0 | 0 |
0 | 1 | 1 | 1 |
1 | 0 | 1 | 0 |
1 | 1 | 0 | 0 |
この真理値表から回路を構成すると以下のようになる。
この減算回路は下の桁への桁下がりを考慮しておらず、下への桁下がりがない最下位ビットのみにしか使えない。これを半減算器という。
全減算器
以下に全減算器の真理値表と回路図を示す。
A | B | BI | D | BO |
---|---|---|---|---|
0 | 0 | 0 | 0 | 0 |
0 | 0 | 1 | 1 | 1 |
0 | 1 | 0 | 1 | 1 |
0 | 1 | 1 | 0 | 1 |
1 | 0 | 0 | 1 | 0 |
1 | 0 | 1 | 0 | 0 |
1 | 1 | 0 | 0 | 0 |
1 | 1 | 1 | 1 | 1 |
図は省略するが、加算器と同様に3bit減算回路のverilogは
module FS3_VERILOG(A, B, BO, D); input [2:0] A; input [2:0] B; output BO; output [2:0] D; assign {BO, D} = A - B; endmodule
と書ける。
負の数
減算結果の負の数を2進数で表す場合、最も単純なのは符号を表すビットを追加して、符号ビット+絶対値として表す方法だ。符号ビットは正の時に0、負の時に1とする。つまり、-2dは値を3bitとすれば、1010bと表せる。3bitの絶対値に符号ビットを追加して表現した例を以下に示す。
10進数 | 符号なし2進数 | 符号付き2進数 |
---|---|---|
15 | 1111 | - |
14 | 1110 | - |
13 | 1101 | - |
12 | 1100 | - |
11 | 1011 | - |
10 | 1010 | - |
9 | 1001 | - |
8 | 1000 | - |
7 | 0111 | 0111 |
6 | 0110 | 0110 |
5 | 0101 | 0101 |
4 | 0100 | 0100 |
3 | 0011 | 0011 |
2 | 0010 | 0010 |
1 | 0001 | 0001 |
0 | 0000 | 0000 or 1000 |
-1 | - | 1001 |
-2 | - | 1010 |
-3 | - | 1011 |
-4 | - | 1100 |
-5 | - | 1101 |
-6 | - | 1110 |
-7 | - | 1111 |
先ほどの3bit減算回路の演算結果出力と比べてみる。
減算結果(10進数) | 出力パターン | 符号付き2進数 |
---|---|---|
BO,D2,D1,D0 | 符号1bit,絶対値3bit | |
7 | 0111 | 0111 |
6 | 0110 | 0110 |
5 | 0101 | 0101 |
4 | 0100 | 0100 |
3 | 0011 | 0011 |
2 | 0010 | 0010 |
1 | 0001 | 0001 |
0 | 0000 | 0000 or 1000 |
-1 | 1111 | 1001 |
-2 | 1110 | 1010 |
-3 | 1101 | 1011 |
-4 | 1100 | 1100 |
-5 | 1011 | 1101 |
-6 | 1010 | 1110 |
-7 | 1001 | 1111 |
3bit減算回路の出力パターンと符号付き2進数を比較すると、減算結果が正の時は一致しており、また負の時もBOと符号ビットは一致している。つまり、減算結果が負となる時のD2,D1,D0の3bitの絶対値部分を変換すれば良い。この変換には補数を用いる。具体的には、
-まず、D0〜D2の各ビットを反転 -次に反転した3bitのDに1bを加算
のように行う。表で変換過程を示すと以下のようになる。
減算結果 | 出力パターン | D0〜D2を反転 | さらに1を加算 |
---|---|---|---|
(10進数) | BO, D2, D1, D0 | BO, ~D2, ~D1, ~D0 | BO, (~D2, ~D1, ~D0)+001b |
-1 | 1111 | 1000 | 1001 |
-2 | 1110 | 1001 | 1010 |
-3 | 1101 | 1010 | 1011 |
-4 | 1100 | 1011 | 1100 |
-5 | 1011 | 1100 | 1101 |
-6 | 1010 | 1101 | 1110 |
-7 | 1001 | 1110 | 1111 |
各ビットを反転して1bを加算する回路は補数機と呼ばれており、以下の様な回路で示される。
本では最後に、補数機を3bit減算器に組み合わせ符号付き2進数3bit減算回路を示している。回路図は省略するが、verilogだけ書いておく。
module FS3_SIGN_VERILOG(A, B, BO, D); input [2:0] A; input [2:0] B; output BO; output [2:0] D; wire [3:0] sub; assign sub = {1'b0, A} - {1'b0, B}; assign BO = sub[3]; assign D = sub[3] ? (~sub[2:0] + 1'b1) : sub[2:0]; endmodule
今回はここまで。次回は順序回路から。
FPGA入門 備忘録② ~基本回路、組み合わせ回路編~
備忘録①からの続きになる。なお本では前回と今回の間にXilinxのISEのインストール方法、回路図エディタの使用方法などが記されている。
論理素子
まずは基本的なところから、VHDLとverilogの記法の違い。
名称 | 機能 | VHDL | Verilog HDL |
---|---|---|---|
NOTゲート(インバータ) | 論理反転 | not | ~ |
ANDゲート | 論理積 | and | & |
ORゲート | 論理和 | or | | |
XORゲート | 排他的論理和 | xor | ^ |
NANDゲート | 否定論理積 | nand | なし |
NORゲート | 否定論理和 | nor | なし |
XNORゲート | 否定排他的論理和 | xnor | ~^ |
自分の目的はVerilog HDLを使いこなせるようになることなので、VHDLについては以後触れない。 さて、本の中では以下の様な回路を回路図エディタ、VHDL、Verilog HDLの3種類で作成することを試みている。
module INV_VERILOG(PSW0, LED0); input PSW0; output LED0; assign LED0 = ~PSW0; endmodule
assign LED0 = ~PSW0;という記述の~がNOTゲートを表している。LED0が出力で、PSW0が入力で、PSW0をインバートしたものがLED0に接続されているということだ。
ANDゲート
VerilogではANDゲートを
assign Q = A & B;
と表し、VHDLでは、
Q <= A and B;
と表す。 これを踏まえて、SW1とSW2の両者が入力されると、LED0が点灯するようなverilog のコードを書いてみよう。
module AND_VERILOG(SW0, SW1, LED0); input SW0; input SW1; output LED0; assign LED0 = SW0 & SW1; endmodule
ORゲート
VerilogではORゲートを
assign Q = A | B;
と表し、VHDLでは、
Q <= A or B;
と表す。
XORゲート
VerilogではXORゲートを
assign Q = A ^ B;
と表し、VHDLでは、
Q <= A xor B;
と表す。
NANDゲート
VerilogではNANDゲートを
assign Q = ~(A & B);
と表し、VHDLでは
Q <= A band B
と表す。verilogではAとBのANDを括弧でくくりそれをNOTすることでNANDを表現している。
NORゲート
VerilogではNORゲートを
assign Q = ~(A | B);
と表し、VHDLでは
Q <= A nor B;
と表す。verilogではAとBのORを括弧でくくりそれをNOTすることでNORを表現している。
XNORゲート
VerilogではXNORゲートを
assign Q = A ~^ B;
と表し、VHDLでは
Q <= A xnor B;
と表す。
組み合わせ回路
上でも示したように、NANDゲートはANDゲートとNOTゲートを接続して作成できる。つまり、ANDゲートとNOTゲートによる組み合わせ回路といえる。NORゲートも同様にORゲートとNOTゲートの組み合わせで作成できる。では、ANDやOR、NOTゲートはどうだろう。実はこれもNANDゲートで作ることが可能だ。以下の図はそれぞれNANDゲートのみで構成したNOTゲート、 ANDゲート、ORゲートだ。
また、XORはAND、OR、NOTを組み合わせれば構成できるので、NANDで置き換えることが可能だ。
HDLの3つの記述方法
HDLにはいくつかの記述方法があり、回路によって記述しやすいものを使用する。記述方法は大きく3つあり、
- 論理演算子を組み合わせて記述する方法
- テーブルを用いる方法
- プリミティブを直接指定する方法
にわけられる。それぞれXOR回路を例に順に見ていく。
論理演算子を組み合わせて記述する方法
module XOR1_VERILOG(A, B, C); input A; input B; output C; assign C = ~(~A & ~(B & B)) & (~(~A & A) & B))); endmodule
上の回路図と合わせて見ると理解できると思う。
テーブルを用いる方法
テーブルとは真理値表のことで、より複雑な論理を記述するのに向いている。テーブルの記述にはいくつかの方法があり、VHDLではwith select、case文を用いて、Verilogではassign、case文を用いて書く方法がある。 まずはassignを用いて書いた場合を見てみよう。
module XOR2_VERILOG(A, B, C); input A; input B; output C; wire [1:0] Q; assign Q = {A, B}; assign C = (Q == 2'b00) ? 1'b0 : assign C = (Q == 2'b01) ? 1'b1 : assign C = (Q == 2'b10) ? 1'b1 : assign C = (Q == 2'b11) ? 1'b0 : 1'b0; endmodule
まずwire宣言から。これは2bit幅のバスラインQを宣言している。 assign Q = {A, B}でQの上位ビットをAに、下位ビットをBに接続している。 次に、assign C = (Q==2b'00) ? 1'b0 :で、Qの値が00であれば、Cに0を出力する事を指定している。最後の1'b0はCのデフォルト値で、Qの値が未指定の場合の出力値を0としている。
次に、case文で記述したものを見てみる。
module XOR3_VERILOG(A, B, C); input A; input B; output C; reg C; wire [1:0] Q; assign Q = {A, B}; always @(Q) begin case (Q) 2'b00: C = 1'b0; 2'b01: C = 1'b1; 2'b10: C = 1'b0; 2'b11: C = 1'b0; default: C = 1'b0; endcase end endmodule
Cはalways文の中で使用するので、reg C;と宣言する必要がある。always文については長くなるので後回し。
プリミティブを直接指定する方法
各デバイス特有の回路を、直接指定する際に使用する。したがって、指定できるプリミティブはデバイスによって異なる。FPGAごとに使えるライブラリのガイド一覧はXIlinxのHPで公開されている。 verilogでXOR2プリミティブを直接呼ぶ例を見てみよう。
module XOR4_VERILOG_TOP(A, B, C); input A; input B; output C; XOR2 instance1(.O(C), .IO(A), .I1(B)); endmodule
instance1という名前のXOR2に各信号を接続している。カッコ内の.O(C)という記述はXOR2の出力ピンOと外部出力ピンCが接続されることを意味する。ここの信号名OやIOなどはライブラリガイドに則った名称である必要がある。
マルチプレクサ
実用的な組み合わせ回路の一例としてマルチプレクサを取り上げる。マルチプレクサの真理値表は、
D0 | D1 | S0 | O |
---|---|---|---|
0 | 0 | 0 | 0 |
0 | 1 | 0 | 0 |
1 | 0 | 0 | 1 |
1 | 1 | 0 | 1 |
0 | 0 | 1 | 0 |
0 | 1 | 1 | 1 |
1 | 0 | 1 | 0 |
1 | 1 | 1 | 1 |
右図で示すようにマルチプレクサはS0が0の時はO=D0となり、1の時はO=D1となる。つまり、Oに出力するデータを、S0によって選択する回路となっている。
1bit2入力マルチプレクサの内部回路を見てみよう。
S0=0の時は、D0側のANDゲートがアサート(EN)され、D1側はネゲート(Disable)される。逆に、S0=1の時はD0側のANDゲートがネゲートされ、D1側のANDゲートがアサートされる。
これは、S=1の時にスイッチが押されて、DOにDINの値が出力され、S=0の時はスイッチが切り離され、DOが0となると考えられる。verilogでは以下のように書ける。
module M2_1_VERILOG(D0, D1, S0, 0); input D0; input D1; input S0; output O; wire d0_sel; wire d1_sel; assign d0_sel = D0 & ~S0; assign d1_sel = D1 & S0; assign O = d0_sel | d1_sel; endmodule
デコーダ(デマルチプレクサ)
マルチプレクサの対になるのが、デマルチプレクサである。デマルチプレクサは一般にデコーダとして使われることが多く、ここでは2進数のデータを10進数に戻すバイナリデシマルデコーダを指している。 2bitバイナリデシマルデコーダの真理値表を以下に示す。
A1 | A0 | E | D3 | D2 | D1 | D0 |
---|---|---|---|---|---|---|
- | - | 0 | 0 | 0 | 0 | 0 |
0 | 0 | 1 | 0 | 0 | 0 | 1 |
0 | 1 | 1 | 0 | 0 | 1 | 0 |
1 | 0 | 1 | 0 | 1 | 0 | 0 |
1 | 1 | 1 | 1 | 0 | 0 | 0 |
E=1の時、Aに入力されるバイナリコードに応じて、出力Dのいずれかが1となる。出力Dは最下位ビットから順にD0=1、D1=2、D2=3、D3=4という形で、10進数を表している。 ここで、E=0の時は入力Aに関わらず、出力D0〜D3はすべて0になる。したがって、Aで選択した出力先のDの値はEの入力値に等しくなる。Eをデータ入力、Aを制御入力と考えると、Eの出力先を切り替える回路として利用できる。これはマルチプレクサと逆の動きなので、デマルチプレクサと呼ぶ。
Eをデータ入力として、Aを制御入力として使うものがデマルチプレクサで、Aをデータ入力とし、Eは制御入力(EN端子)として使うものがデコーダとなる。
2bitバイナリデシマルデコーダの内部回路は以下のようになっている。
Eをデータ入力とした時、A0及びA1で4つのANDゲートのいずれかをアサートする選択回路となっていることが分かる。verilogのコードも示す。
module D2_4E_VERILOG(A0, A1, E, D0, D1, D2, D3); input A0; input A1; input E; output D0; output D1; output D2; output D3; assign D0 = E & ~A0 & ~A1; assign D1 = E & A0 & ~A1; assign D2 = E & ~A0 & A1; assign D3 = E & A0 & A1; endmodule
とりあえずは、ここで今回は終わり。備忘録③は加算回路から。
鮨ます田に行ってきた
STARTUP HARDTHINGS@ASACに行ってきた
STARTUP HARDTHINGSというスタートアップ系の勉強会に行ってきた。 会場は青山にあるASAC(Aoyama Startup Acceleration Center)という場所。 なんでも東京都が借り上げている施設で、施設運営を監査法人のトーマツが行っているらしい。
会場の写真は撮影しなかったのだが、イベントを催した場所の広さは大きめの会議室程度。 定員50名に対し、申し込みが75名ほど。実際に来たのは40名といったところか。
講演内容
トーマツの方が司会進行を務め、それに対し、座談会形式で話していくスタイルで行われた。 まずは登壇者3名のプロフィールから。
登壇者紹介
- 真子就有氏(株式会社div 代表取締役) プログラミング教育事業TECH::CAMPが主な事業
- 浅枝大志氏(Beatrobo Inc. CEO) スマホのイヤホンジャックに挿すだけで音楽や動画が楽しめるPlugAirが主な事業
- 天沼聰氏(株式会社エアークロゼット 代表取締役CEO) 洋服のシェアリングサービスAirClosetが主な事業
トークセッション
〜立ち上げ時の苦労に関して〜
(真子氏)自分は学生時代からITベンチャーで働いていた。大学4年の時に「じげん」という会社で人事をやっていた。5名内定者出した時点で自分が起業したくなった。社長には怒られた。やめる時が大変だった。やめる時がHARD THINGSだった。
-皆さん会社のやめ方は?
(真子氏)Gmailで上長に3日間ぐらい推敲したメールを送った。Bccに地元の友達入れてたw 上長とは普通に面談。社長に怒られた。
(浅枝氏)もともと就職したことない。ちなみに就活では電通と任天堂だけ受けた。電通は面接で第二希望です!と正直に行ったら落ちた。任天堂は大学院に生きながら働けますか?京都に行くのは嫌です、と言ったら落ちたw
(天沼氏)前職は楽天だった。やめるときは上司呼んで話した。もともと上司には起業志望であること話していたのでスムーズにやめられた。 楽天に移ってからは新規プロジェクトをワンサイクル回して、後継のマネージャ採用まで行ったので、引き継ぎはしっかりした。
-在職中に準備していた?
(天沼氏)在職中は楽天からお金をもらっているので、片手間でやることはしなかった。 楽天をやめた時点でairclosetのビジネスモデルはまだ概念レベル。
-皆さんサービス作る時の最初の構想は?
(浅枝氏)世界で俺しかこのサービス作れないというのが自分の基準。他の誰かが既にやっているものには興味が無い。VRとかみんなやってるから俺はいいやという感じ。 (真子氏)ひとつ目のサービスはlogというサービスをやっていた。Facebookは人間関係を可視化したから、興味を可視化したいと思った。しかし、実際にはただの記録ツールで、コミュニケーションが生まれておらず想定の使い方と違った。 そこでコミュニケーションの機能をつけた(logcomm)。チーム全員行けると思っていたけど、1ヶ月後キャッシュアウト。 Classというサービスもバズった。意外とやってみると、めっちゃ緊張する。青春時代の思い出補正で勘違い→なんか違うで怒ってる人が多かったw あとはActiveUser1000人くらいの時にiOSアプリでバグ、炎上。
-こういう世の中になる、その確信は?
(浅枝さん)なかなかそういう時は来ない。セカンドライフが3Dインターネットの走りでそういう世の中になると思った。 VRのなかで、空間の中で人に合う時代が来る。アバターの時代が来る。
-未来予想図はどう立ててる?
(浅枝さん)映画とか参考にしてる。攻殻機動隊、サマーウォーズ、ドラえもん、、、等々。
-未来予測はできる?
(天沼さん)できないと思う。シェアリングエコノミー、ライフスタイルに浸透、インターネットが好き、その軸。 コンサル3人で起業したので、評価軸とかで100個ぐらいのビジネスモデル比較して、、、最終的には感情で決めた。 今の課題を5年10年先で、どうしたいか。具体的なビジネスモデルは手前のもの。
(浅枝さん)CEOは2種類いるとおもう。事業家か芸術家。真子さんは芸術家、天沼さんは事業家。
(真子さん)うまくハイブリッドさせたいとは思ってるんですけどね。
~チーム作りについて~
(真子さん)共同創業者は二人。俺は一人でもやるけど、お前やるならやってもいいよ。普通株式も9割社長が鉄板だが、55%、45%とかにした。共同創業者は株主間契約をしておいたほうがいい。
(天沼さん)自分はやっている
(浅枝さん)自分もやった。資本政策は一番躓くところ。
-浅枝さんはチーム作りどう?
(浅枝さん)自分はロマンを求めた。セカンドライフの会社は一人でやってた。次は3人で33.3%としてたけど、金が入る前に50.1%を俺にくれと交渉。株主間契約やった。結婚みたいなもの。
(真子さん)つい渡したくなる気持ちは出てくる。不公平だから、こいつは俺より優秀だし、、等々 1000億とかの会社を作るのなら、2割でも5割でも関係ないと思う。
(浅枝さん)芸術家はお金を気にしない。
(天沼さん)株主比率にこだわって、資金調達が遅れるぐらいなら、下がっても良いと思っている。 あと、仲間の二人には役員報酬がゼロだったとしてもできるかを聞いた。 丸一年だったらできるとの返答。全面的に信頼できるメンバー、かつ金銭的に答えが返ってきたので一緒にやることにした。 創業メンバーは3人にこだわる。二人だと対立する。第3社的な視点が必要。
(真子さん)二人はまずい。上下関係もできたりする。
質疑応答
-外注と内製等何を優先すべきか?
(天沼さん)いまは全部内製。
(真子さん)優位性がなにか、という点。toCの場合、使い方。toBの場合、まずは外注。そのほかは営業に回るなど。
(天沼さん)改善を繰り返す必要があったので、サービスの質、スピードのどちらを重視するか?
(天沼さん)スピードをとる。やってみないとわからない。外注していると改善のスピードを高められない
(真子さん)作りこんでリリース、ドンズべりはある。以下に作らないかが勝負。
(天沼さん)最初はファッション業界の知り合いゼロだった。Facebookに投稿して、ファッション業界の知り合い紹介して、ってお願いして一人づつ増やしていった。
(天沼さん)組織づくりは企業に入っていると参考になる。
-採用に関して、一緒に働きたい以外の軸はあるか?
(天沼さん)グループ長の人が採るといったら基本的には採る。ほかは、キャラがチームに合うか、地頭ロジカルか、情熱があるか どういう人間になりたいか、も自分は聞く。
(浅枝さん)うちをやめたらあなたはどうなっていますか?という質問をする。
-自分より優秀な人を採用するのはどうやる?
(天沼さん)優秀かどうかって難しい。会社って役割がそれぞれあって、優秀さの判断をしない。
(浅枝さん)その人の部下になっても良いかを聞く
(真子さん)リファレンスは必ず取るようにしてる
(浅枝さん)あえて短所は?などと聞く
(真子さん)ここで働くこと自体が最高なんだ、そこがぶれない事が大事。
(天沼さん)伝え続けること大事
-一緒にできるか、の基準は何か?
(天沼さん)金銭的な部分をきちんとくぐり抜けられるか。ディスカッションを夜通しやっていても疲れないか。
-サービスが立ち上がらない。
(天沼さん)サービス価値が何か、言えることが重要。あれも解決できるし、これも、、となっている。できるかぎりシンプルに答えられることが重要。誰のために、は重要。 会議もSlackもお客さんが一人聞いていると思え、と言っている。slackでも顧客は呼び捨てにしない。
-資金調達を決断するタイミングは?
(天沼さん)株主になると一定の権利が生まれる。エンジェルの場合、VCに比べ、感情がかなり入る。
(浅枝さん)出資を受けずに上場するのが一番良い。リブセンスの例もある。
感想
登壇者の皆さんについて多くは知らなかったが、参考になることは多かった。やっぱり実務をやっている人の話は面白い。Slackはお客さんが見てると思って書き込めはいいな。