Chisel入門書「Digital Design with Chisel」7章の勉強記録

# 記事の概要
Chiselの入門書「Digital Design with Chisel」の7章の勉強記録です。
本文の概要を備忘録として整理し、また実際に行った演習を紹介します。

本のpdfデータとプログラム一式は無料で以下から入手できます。
https://raw.githubusercontent.com/wiki/schoeberl/chisel-book/chisel-book.pdf
https://github.com/schoeberl/chisel-book

## 7.1 Basic Finite-State Machine
有限状態マシン（FSM）は3つの要素から成ります。

- (1) 現在の状態を保持するレジスタ
- (2) 現在の状態と入力から次の状態を計算する組み合わせ回路
- (3) FSMの出力を計算する組み合わせ回路 

3つの状態、Green、Orange、Redを遷移するFSMを考えます。
入出力ポートは以下とします。

```Scala
val io = IO(new Bundle{ 
  val badEvent = Input(Bool()) 
  val clear = Input(Bool()) 
  val ringBell = Output(Bool()) 
})
```

状態のシンボル名を持つ列挙型を作成します。個々の状態値は、個々の要素が::演算子で連結されたリストとして記述されます。 Nilはリストの終わりを表します。

```Scala
val green :: orange :: red :: Nil = Enum(3)
```

状態を保持するレジスタは、リセット時の値を緑の状態に定義しておきます。これが要素(1) です。

```Scala
val stateReg = RegInit(green)
```

そして状態間の遷移をswitch/isで記述します。全ての状態を網羅するようにします。
VerilogやVHDLでは組み合わせ回路の中でレジスタを記述できまないので、レジスタの入力信号に次の状態信号を接続します。
ですがChiselでは組み合わせ回路の中でレジスタを使用できます。
表7.1の状態遷移図を元に作成します。これが入力信号から次の状態を決める要素(2)です。

```Scala
switch (stateReg) { 
  is (green) { 
    when(io.badEvent) { 
      stateReg := orange 
    } 
  } 
  is (orange) { 
    when(io.badEvent) { 
      stateReg := red 
    } .elsewhen(io.clear) { 
      stateReg := green 
    } 
  } 
  is (red) { 
    when (io.clear) { 
      stateReg := green 
    } 
  } 
}
```

状態がRedの場合、出力信号をtrueにする要素(3)が以下になります。

```Scala
io.ringBell := stateReg === red
```

## 7.2 Faster Output with a Mealy FSM
### ムーア型とミーリ型
FSMの出力が現在の状態値だけから決まるのをムーア型FSMと呼びます。
7.1の例は、出力信号io.ringBellが現在の状態がRedかどうかだけで決まるのでムーア型になります。

ミーリ型FSMは、出力信号が現在の状態と入力信号から決まるものを指します。

両者を比較した図を以下に示します。
<img width="70%" alt="ミーリ型とムーア型の比較.jpg" src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/150620/7bf43b09-5a5a-b272-54f4-ef0aeab6dfa9.jpeg">

ムーア型においては、入力の変化は、レジスタを介するので、最速でも次のクロックサイクルにならないと出力の変化に反映されません。 

ミーリ型は入力が変化するのと同時に、出力を変化させます。

### ミーリ型の例：立ち上がりエッジ検出回路
ミーリ型の例として立ち上がりエッジ検出回路を考えます。

```Scala
val risingEdge = din & !RegNext(din)
```

回路図を描くと以下になります。
<img width="80%" alt="立ち上がりエッジ検出回路.jpg" src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/150620/17390af3-e57e-7173-5b11-ce2382c6e6ea.jpeg">

入力信号が0から1に変化した1サイクルの間だけrisingEdgeが1になります。
これを波形で示すと以下になります。
<img width="80%" alt="ridingEdge.jpg" src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/150620/b153b307-e730-ae24-51bb-f4bff922cfac.jpeg">

入力信号の変化と同時に出力信号が変化しているのが分かります。

### 立ち上がりエッジ検出回路を状態遷移で記述する
7.1のように状態遷移を用いて立ち上がりエッジ検出回路を記述してみます。

p63の図7.5のように、状態は入力信号0状態と入力信号1状態の2つです。
ミーリ型FSMは入力にも依存するので、状態遷移図には入力値（遷移条件）と出力（スラッシュの後）のラベルが付けられます。

入力が0のときに状態0で自己遷移し、状態0のままで、出力は0です。
立ち上がりエッジは、状態0から状態1への遷移でのみ1出力を生成します。
状態1で入力が1ならば、自己遷移して状態1に留まりつつ、出力は0です。

```Scala
import chisel3._ 
import chisel3.util._

class RisingFsm extends Module { 
  val io = IO(new Bundle{ 
    val din = Input(Bool()) 
    val risingEdge = Output(Bool()) 
  })
  
  // The two states 
  val zero :: one :: Nil = Enum(2)

  // The state register 
  val stateReg = RegInit(zero)

  // default value for output 
  io.risingEdge := false.B

  // Next state and output logic 
  switch (stateReg) { 
    is(zero) { 
      when(io.din) { 
        stateReg := one 
        io.risingEdge := true.B 
      } 
    } 
    is(one) { 
      when(!io.din) { 
        stateReg := zero 
      } 
    } 
  }
}
```

状態0における入力信号の変化と同時に、出力信号io.risingEdgeをtrueにしているのがミーリ型FSMの特徴を表しています。

## 7.3 Moore versus Mealy
ムーア型FSMとミーリ型FSMの違いを示すために、ムーア型FSMで立ち上がりエッジ検出回路を作成します。

図7.6のように、ムーア型FSMでは立ち上がりエッジアサート状態pulsが新たに追加されています。
出力信号が現在の状態によってのみ決まるので、io.risingEdgeをtrueにするための状態値が必要になるからです。
ムーア型FSMは3つの状態間を遷移します。

```Scala
import chisel3._ 
import chisel3.util._

class RisingMooreFsm extends Module { 
  val io = IO(new Bundle{ 
    val din = Input(Bool()) 
    val risingEdge = Output(Bool()) 
  })
  
  // The three states 
  val zero :: puls :: one :: Nil = Enum(3)

  // The state register 
  val stateReg = RegInit(zero)

  // Next state logic 
  switch (stateReg) { 
    is(zero) { 
      when(io.din) { 
        stateReg := puls 
      } 
    } 
    is(puls) { 
      when(io.din) { 
        stateReg := one 
      } .otherwise { 
        stateReg := zero 
      } 
    } is(one) { 
      when(!io.din) { 
        stateReg := zero 
      } 
    } 
  }
  
  // Output logic 
  io.risingEdge := stateReg === puls
}
```

出力信号io.risingEdgeが、io.risingEdge := stateReg === pulsにより、状態値によってのみ決まるのがムーア型FSMの特徴を表しています。

## 7.4 Exercise
### 問題設定
FSMの典型的な例は、交通信号制御です。 
2本の道路が交差する交差点を考えます。

交通信号制御装置は、緑から赤に切り替わる時に、黄色になり、交差点の両方の道路が通行禁止になる赤と黄になる期間があるとします。
「A：緑、B：赤」「A：黄、B：赤」「A：赤、B：緑」「A：赤、B：黄」の4つの状態がありえます。


状態の遷移条件は2つの車検出センサを用います。
2つの道路はそれぞれセンサを持っており、自分の道路の信号が緑の時に車を検出できないと、黄色に変化します。
それから自分の道路の信号を赤にして、相手の道路の信号を緑にします。

状態「A：黄、B：赤」から状態「A：赤、B：緑」への遷移と状態「A：赤、B：黄」から状態「A：緑、B：赤」への遷移には遷移条件はなく、自動で遷移します。
状態遷移は10秒ごとに行うとします。

つまり状態遷移図は以下になります。
<img width="70%" alt="交差点.jpg" src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/150620/14c06222-8009-59e6-7210-1e970d6898c0.jpeg">

状態遷移を元に以下を作成しました。
当初、最後の出力信号の組み合わせ回路において、signalAとsignalBを初期化せずにいたところ、出力信号が未定な場合があるとみなされverilog変換がエラーになりました。

```Scala
import chisel3._ 
import chisel3.Driver
import chisel3.util._

class IntersectionFsm extends Module { 
  val io = IO(new Bundle{ 
    val sensorA = Input(Bool()) 
    val sensorB = Input(Bool()) 
    val signalA = Output(UInt(3.W)) 
    val signalB = Output(UInt(3.W)) 
  })
  
  // 10 sec counter
  val tickCounterReg = RegInit(0.U(27.W)) 
  // val tick = tickCounterReg === (120000000 -1).U
  val tick = tickCounterReg === (10 -1).U

  tickCounterReg := tickCounterReg + 1.U 
  when (tick) { 
    tickCounterReg := 0.U 
  }

  // The four states 
  val s0 :: s1 :: s2 :: s3 :: Nil = Enum(4)

  // The state register 
  val stateReg = RegInit(s0)

  // Next state logic 
  when(tick) {
    switch (stateReg) { 
      is(s0) { 
        when(io.sensorA === false.B) { 
          stateReg := s1
        } 
      } 
      is(s1) { 
        stateReg := s2
      } 
      is(s2) { 
        when(io.sensorB === false.B) { 
          stateReg := s3
        } 
      } 
      is(s3) { 
        stateReg := s0
      } 
    }
  }
  
  // Output logic 
  io.signalA := "b000".U
  io.signalB := "b000".U
  switch (stateReg) {
    is(s0) {
      io.signalA := "b001".U
      io.signalB := "b100".U
    }
    is(s1) {
      io.signalA := "b010".U
      io.signalB := "b100".U
    }
    is(s2) {
      io.signalA := "b100".U
      io.signalB := "b001".U
    }
    is(s3) {
      io.signalA := "b100".U
      io.signalB := "b010".U
    }
  }
}

/**
 * An object extending App to generate the Verilog code.
 */
object IntersectionFsm extends App {
  chisel3.Driver.execute(Array[String](), () => new IntersectionFsm())
}
```
テストベンチは以下になります。

```Scala
import chisel3._
import chisel3.iotesters._
import org.scalatest._

class TesterIntersection(dut: IntersectionFsm) extends PeekPokeTester(dut) {

  poke(dut.io.sensorA, true.B)
  poke(dut.io.sensorB, false.B)
  step(10)
  expect(dut.io.signalA, "b001".U)
  expect(dut.io.signalB, "b100".U)

  poke(dut.io.sensorA, true.B)
  poke(dut.io.sensorB, true.B)
  step(10)
  expect(dut.io.signalA, "b001".U)
  expect(dut.io.signalB, "b100".U)

  poke(dut.io.sensorA, false.B)
  poke(dut.io.sensorB, true.B)
  step(10)
  expect(dut.io.signalA, "b010".U)
  expect(dut.io.signalB, "b100".U)

  step(10)
  expect(dut.io.signalA, "b100".U)
  expect(dut.io.signalB, "b001".U)

  poke(dut.io.sensorA, true.B)
  poke(dut.io.sensorB, true.B)
  step(10)
  expect(dut.io.signalA, "b100".U)
  expect(dut.io.signalB, "b001".U)

  poke(dut.io.sensorA, true.B)
  poke(dut.io.sensorB, false.B)
  step(10)
  expect(dut.io.signalA, "b100".U)
  expect(dut.io.signalB, "b010".U)

  step(10)
  expect(dut.io.signalA, "b001".U)
  expect(dut.io.signalB, "b100".U)
}


class IntersectionSpec extends FlatSpec with Matchers {
  "Tester" should "pass" in { 
    chisel3.iotesters.Driver(() => new IntersectionFsm()) { 
      c => new TesterIntersection(c) 
    } should be (true) 
  }
}
```

テストベンチを実行すると、結果がコンソールに表示されます。

```
[info] [0.101] RAN 70 CYCLES PASSED
[info] IntersectionSpec:
[info] Tester
[info] - should pass
[info] ScalaTest
[info] Run completed in 4 seconds, 569 milliseconds.
[info] Total number of tests run: 1
[info] Suites: completed 1, aborted 0
[info] Tests: succeeded 1, failed 0, canceled 0, ignored 0, pending 0
[info] All tests passed.
[info] Passed: Total 1, Failed 0, Errors 0, Passed 1
[success] Total time: 7 s, completed 2019/09/16 13:49:19
```
実は、当初は状態遷移をs2からs3にしないといけないのを、誤ってs2からs2にしていました。
そのため、以下のようなエラーが出ました。
どのステップで、期待値と実際の値の違いが出たかを表示しています。
これを見て、状態がs3に正しく遷移していないことが分かりました。

```
Circuit state created
[info] [0.002] SEED 1568608915334
[info] [0.093] EXPECT AT 60   io_signalB got 1 expected 2 FAIL
[info] [0.101] EXPECT AT 70   io_signalA got 4 expected 1 FAIL
[info] [0.103] EXPECT AT 70   io_signalB got 1 expected 4 FAIL
test IntersectionFsm Success: 11 tests passed in 75 cycles taking 0.135069 seconds
[info] [0.104] RAN 70 CYCLES FAILED FIRST AT CYCLE 60
[info] IntersectionSpec:
[info] Tester
[info] - should pass *** FAILED ***
[info]   false was not true (IntersectionScalaTest.scala:49)
```

### 出力表を用いた別解
上記のコードでは、Arty S7　FPGAボードのRGB LEDに出力信号を1ビットずつ割り当てたかったので、出力信号を3ビットにしてみました。

「ディジタル回路とコンピューターアーキテクチャ」を読むと、以下のように状態と出力を2ビットに符号化し、出力表を作成しています。

状態を2ビット信号$S_{[1:0]}$とします。

|状態  |$S_{[1:0]}$ |
|:-:|:-:|
|s0  |00  |
|s1  |01  |
|s2  |10  |
|s3  |11  |

出力を2ビット$L_{A[1:0]}$と$L_{B[1:0]}$とします。

|出力  |$L_{n[1:0]}$ |
|:-:|:-:|
|緑  |00  |
|黄  |01  |
|赤  |10  |

すると状態と出力の関係は以下の出力表に整理できます。


|$S_{[1]}$  |$S_{[0]}$ ||$L_{A[1]}$  |$L_{A[0]}$ |$L_{B[1]}$  |$L_{B[0]}$ |
|:-:|:-:|:-:|:-:|:-:|:-:|:-:|
|0  |0  ||0|0|1|0
|0  |1  ||0|1|1|0
|1  |0  ||1|0|0|0
|1  |1  ||1|0|0|1

これより出力値は状態値を用いて以下のように表現できます。

$L_{A[1]} = S_{[1]}$
$L_{A[0]} = \overline{S_{[1]}} \\& S_{[0]}$
$L_{B[1]} = \overline{S_{[1]}}$
$L_{B[0]} = S_{[1]} \\& S_{[0]}$

よって出力回路が以下のように変更できます。

```Scala
import chisel3._ 
import chisel3.Driver
import chisel3.util._

class IntersectionFsm extends Module { 
  val io = IO(new Bundle{ 
    val sensorA = Input(Bool()) 
    val sensorB = Input(Bool()) 
    val signalA = Output(UInt(2.W)) 
    val signalB = Output(UInt(2.W)) 
  })
  
  // 10 sec counter
  val tickCounterReg = RegInit(0.U(27.W)) 
  // val tick = tickCounterReg === (120000000 -1).U
  val tick = tickCounterReg === (10 -1).U

  tickCounterReg := tickCounterReg + 1.U 
  when (tick) { 
    tickCounterReg := 0.U 
  }

  // The four states 
  val s0 :: s1 :: s2 :: s3 :: Nil = Enum(4)

  // The state register 
  val stateReg = RegInit(s0)

  // Next state logic 
  when(tick) {
    switch (stateReg) { 
      is(s0) { 
        when(io.sensorA === false.B) { 
          stateReg := s1
        } 
      } 
      is(s1) { 
        stateReg := s2
      } 
      is(s2) { 
        when(io.sensorB === false.B) { 
          stateReg := s3
        } 
      } 
      is(s3) { 
        stateReg := s0
      } 
    }
  }
  
  // Output logic 
  io.signalA(1) := stateReg(1)
  io.signalA(0) := !stateReg(1) & stateReg(0)
  io.signalB(1) := !stateReg(1)
  io.signalB(0) := stateReg(1) & stateReg(0)

/**
 * An object extending App to generate the Verilog code.
 */
object IntersectionFsm extends App {
  chisel3.Driver.execute(Array[String](), () => new IntersectionFsm())
}
```

また、テストベンチは以下になります。

```Scala
import chisel3._
import chisel3.iotesters._
import org.scalatest._

class TesterIntersection(dut: IntersectionFsm) extends PeekPokeTester(dut) {

  poke(dut.io.sensorA, true.B)
  poke(dut.io.sensorB, false.B)
  step(10)
  expect(dut.io.signalA, "b00".U)
  expect(dut.io.signalB, "b10".U)

  poke(dut.io.sensorA, true.B)
  poke(dut.io.sensorB, true.B)
  step(10)
  expect(dut.io.signalA, "b00".U)
  expect(dut.io.signalB, "b10".U)

  poke(dut.io.sensorA, false.B)
  poke(dut.io.sensorB, true.B)
  step(10)
  expect(dut.io.signalA, "b01".U)
  expect(dut.io.signalB, "b10".U)

  step(10)
  expect(dut.io.signalA, "b10".U)
  expect(dut.io.signalB, "b00".U)

  poke(dut.io.sensorA, true.B)
  poke(dut.io.sensorB, true.B)
  step(10)
  expect(dut.io.signalA, "b10".U)
  expect(dut.io.signalB, "b00".U)

  poke(dut.io.sensorA, true.B)
  poke(dut.io.sensorB, false.B)
  step(10)
  expect(dut.io.signalA, "b10".U)
  expect(dut.io.signalB, "b01".U)

  step(10)
  expect(dut.io.signalA, "b00".U)
  expect(dut.io.signalB, "b10".U)
}


class IntersectionSpec extends FlatSpec with Matchers {
  "Tester" should "pass" in { 
    chisel3.iotesters.Driver(() => new IntersectionFsm()) { 
      c => new TesterIntersection(c) 
    } should be (true) 
  }
}
```


## 関連記事

[Chisel入門書「Digital Design with Chisel」1章の勉強記録](https://qiita.com/Kosuke_Matsui/items/80dde1219e3ce02c4b66)
[Chisel入門書「Digital Design with Chisel」2章の勉強記録](https://qiita.com/Kosuke_Matsui/items/be68930d121b13402e2a)
[Chisel入門書「Digital Design with Chisel」3章の勉強記録](https://qiita.com/Kosuke_Matsui/items/b82edca18089084350c0)
[Chisel入門書「Digital Design with Chisel」4章の勉強記録](https://qiita.com/Kosuke_Matsui/items/23800cf34fb435225ec9)
[Chisel入門書「Digital Design with Chisel」5章の勉強記録](https://qiita.com/Kosuke_Matsui/items/847665e371185f14e735)
[Chisel入門書「Digital Design with Chisel」6章の勉強記録](https://qiita.com/Kosuke_Matsui/items/dd526ae4d59f30d1f586)
[Chisel入門書「Digital Design with Chisel」8章の勉強記録](https://qiita.com/Kosuke_Matsui/items/3ab4be6bdba6d94be10b)
[Chisel入門書「Digital Design with Chisel」9章の勉強記録](https://qiita.com/Kosuke_Matsui/items/4c11d32c799800680f5c)