---
title: 2006 FPGA
---
# Lab 0 Homework - 2006 IC Contest Preliminary FPGA Category
Group Member:
* E24066226 魏晉成
* E24066470 余采蓴

[TOC]

## Requirement
### Pinout

As above table shows, signal pins can be devided into three groups:
1. `reset`, `clk`: In this case, we use asynchronous `reset` along with posedge triggering `clk`.
2. `nt`, `xi`, `yi`: When `nt` is high, it is indicated that `xi` and `yi` signals are valid.
3. `busy`, `po`, `xo`, `yo`: `busy` needs to be pulled up to signal the test circuit that unit under test is resolving correct output and prevent new data from being inputted. `po` needs to be pulled up when `xo` and `yo` is generated.

### Function
As above figure shows, this circuit needs to generate (x, y) coordinate pairs starting from (`x1`, `y1`) and the generated points should move parallely to x axis until the last generated pair is out of bound of the triangle formed by (`x1`, `y1`), (`x2`, `y2`), (`x3`, `y3`). Then the generated point should move to (`x1`, y+1) as long as y < `y3`. When the last generated point has the same coordinate as (`x3`, `y3`), the circuit should pull down `busy` to indicate that all points are generated, and test circuit can move on to next test suite.

Because there is no address or number signals indicate which coordinate the test circuit is passing to unit under test, thus three coordinates would be passed in order of 1 ~ 3. More over, the constraints of three points are as follow,
$0 < x_1 = x_3 <= 7,$
$0 < y_1 = y_2 < y_3 <=7$.
As a result that there is no constraint on $x_2$, I tried considering two cases in which `x2` might be either greater or less than `x1`, but according to requirement description, coordinates must be generated in order from left to right. Yet, it's too hard to generate coordinate on hypotenuse; thus I gave up on that part. In fact, to pass the test data, you only need to consider the case that `x2` is greater than `x1`.

## Implementation
According to above requirement description, states and corresponding behaviors are defined to let the circuit operate in designated way. Moreover, block diagram is to help visualize what to make the interconnection inside this circuit.
Besides input and output signals, there are several internal signals to latch the state and the number. First is `cState` which is to store current state for sure. Second is `xVal[1:3]` and `yVal[1:3]`, which are to store three coordinate pairs of (x, y). Third is `nextX` and `nextY`, which would select from `xo + 1`, `xVal[1]` and `yVal[1]`, `yo + 1`, `yo` according to `cState`. Last is `multLHS` and `multRHS`, which are derived as below,
If (xo, yo) is on the left hand side of line formed by (x3, y3) and (x2, y2), then
$$
\frac{x_o - x_2}{y_o - y_2} < \frac{x_3-x_2}{y_3-y_2}
$$
which can be trasposed into
$$
(x_o - x_2)\cdot(y_3 - y_2) < (x_3 - x_2)\cdot(y_o - y_2)
$$
but in fact $x_o < x_2$ and $x_3 = x_1 < x_2$, to get rid of sign bit,
$$
(x_2 - x_o)\cdot(y_3 - y_2) > (x_2 - x_3)\cdot(y_o - y_2)
$$
Because there would be chance that (`xo`, `yo`) is on the line formed by (`x2`, `y2`) and (`x3`, `y3`); thus, the equality is needed to be considered.
So we take `multLHS` as `(xVal[2] - xNext) * (yVal[3] - yVal[2])` and `multRHS` as `(xVal[2] - xVal[3]) * (yNext - yVal[2])`, and need to check if `multLHS` is greater or equal to `multRHS`.

### State Diagram
There are 7 states including `init`, 3 `read`s, `output`, `reset`, and `final`.
* `sInit`
After reset, state would remain in `sInit` until first `nt` high-level signal input.
* `sReadx`
Then, with `sRead1`, `sRead2` and `sRead3`, three pairs on coordinate representing for x1~x3, and y1~y3 are gathered.
* `sX1onleftOutput`
Afterward, state machine would be most probably trapped in `sX1onLeftOutput`, and in this state, `xo` would be increased by 1 in each cycle until the condition, which is (`nextX` <= `xVal[2]` && `multLHS` >= `multRHS`), doesn't suffice anymore, state machine would jump to `sX1onLeftResetX`.
The reason why the condition is not formed by only comparison of `multLHS` and `multRHS` but with additional comparison between `nextX` and `xVal[2]` is that multLHS would overflow when `yNext` equal to `yVal[2]`, i.e., at the boundary condition of first row output. Thus, one additional condition needs to be considered.
* `sX1onLeftResetX`
In this state, `xo` would be reset to `xVal[1]` and `yo` would be increased by 1.
If the `yo` is greater than or equal to `yVal[3]`, which is upper bound of the triangle, then state machine goes to `sFinalOutput` to output (`xVal[3]`, `yVal[3]`). Otherwise, state machine would goes back to `sX1onLeftOutput`.
* `sFinalOutput`
In this state, only (`xVal[3]`, `yVal[3]`) pair would be output, and state goes unconditionally back to `sInit` for next set of input data.

## Simulation Result
* Receiving Inputs
In the very beginning, `xVal` and `yVal` are unknown, and with `xi` and `yi`, the register file is all set and can be used later.

* Generating Outputs and Increment on X Value
As above implementation description has mentioned, `xo` and `yo`would be first set as `xVal[1]` and `yVal[1]` and continuously increased along x axis. Along the output generation process, `po` would be all high level.

* Adding on Y Value
When (`xo`, `yo`) is no longer on the left hand side of the line formed by (`x2`, `y2`) and (`x3`, `y3`), `po` would be pulled down in case output wrong data to testfixture; moreover, `xo` would be set to `xVal[1]` and `yo` would increase by 1.

* Final and Back to Reset
At state `sX1onLeftResetX`, when finding that with increment on `yo`, the next output would be the same as `xVal[3]` and `yVal[3]`, state would go to final output, and set output as (`xVal[3]`, `yVal[3]`) and later go back to `sInit` waiting for more input.

* Next Set of Input
After reset by state machine, new inputs can be accepted by this circuit. As the change in register file of `xVal` and `yVal` can be seen by eye.

## Conclusion
Through this circuitry, the requirement can be resolved and it can pass testbench without any error.