EP1 REFRACT
Light Refraction Notes光線折射整理光線屈折まとめ

The scene: light through curved glass問題情境：光線穿過曲面玻璃問題の場面：曲面ガラスを透過する光

A square tile of glass: the top surface bulges into a curve, the bottom is the flat plane $Z=0$. Light shines straight down from above, refracts at the curved surface and finally lands on the bottom face. The task is to compute the landing point $(zx, zy)$ of every ray.一塊像方形馬賽克磚的玻璃，上表面是凸起曲面，底面是 $Z=0$ 的平面。光線從正上方垂直往下照，在曲面上折射，最後落在底面。要求算出每條光線的落點 $(zx, zy)$。正方形のモザイクタイルのようなガラスで、上面は盛り上がった曲面、底面は $Z=0$ の平面である。光は真上から垂直に入射し、曲面で屈折して最後に底面に達する。各光線の落下点 $(zx, zy)$ を求めるのが課題である。

The black dashed lines are the rays coming straight down from above; the red lines are their paths after refraction inside the glass. The surface is flat in the middle at a height of about 6, falls away ever more steeply towards the edges, and drops to about 2 at the corners.黑色虛線是從上方垂直入射的光線，紅線是進入玻璃後折射的路徑。曲面中央平坦、高度約 6，越靠近邊緣下降越陡，角落掉到約 2。黒い破線は上方から垂直に入射する光線、赤線はガラスに入って屈折した後の経路である。曲面は中央が平坦で高さは約 6、縁に近づくほど急に下がり、角では約 2 まで落ちる。

Right (YZ projection): the rays at $Y = 5 \sim 11$ hit the flat region and fall almost straight down; $Y=3$ and $13$ tilt slightly; the outermost rays at $Y=1$ and $15$ land on the steep slope and bend strongly towards the centre.右圖（YZ 投影）：$Y = 5 \sim 11$ 的光線打在平坦區，幾乎直直落下；$Y=3$、$13$ 略微偏斜；最外側的 $Y=1$、$15$ 打在陡坡上，大幅往中心方向偏折。右図（YZ 投影）：$Y = 5 \sim 11$ の光線は平坦な領域に当たるため、ほぼ真下に落ちる。$Y=3$ と $13$ はわずかに傾き、最も外側の $Y=1$ と $15$ は急斜面に当たって中心方向へ大きく曲がる。

Left (XZ projection): all of these rays have $X$ = 15, hit the right-hand slope and likewise bend inwards. Only two red lines are visible on the left; Section 8 explains why.左圖（XZ 投影）：這些光線的 $X$ 都是 15，打在右側斜坡上，同樣往內偏。左圖只看得到兩條紅線，原因在第 8 節說明。左図（XZ 投影）：これらの光線は $X$ がすべて 15 で、右側の斜面に当たり、同じく内側へ曲がる。左図では赤線が 2 本しか見えないが、その理由は第 8 節で説明する。

The surface formula曲面公式曲面の式

Let $u = \dfrac{X-8}{8}$, which ranges from $-1$ to $\tfrac{7}{8}$. Because the exponent is 8, any $|u|<1$ is squashed to almost nothing, so the middle is essentially flat and the height only drops sharply near the edges — a flat-topped, steep-sided shape.令 $u = \dfrac{X-8}{8}$，範圍是 $-1$ 到 $\tfrac{7}{8}$。因為是 8 次方，$|u|<1$ 時數值被壓得非常小，所以中央幾乎完全平坦，只有接近邊緣才急速下降，形成「平頂、陡邊」的形狀。$u = \dfrac{X-8}{8}$ とおくと、範囲は $-1$ から $\tfrac{7}{8}$ までになる。8 乗なので $|u|<1$ の値は極端に小さく押しつぶされ、中央はほぼ完全に平坦で、縁に近づいたところだけ急激に下がる。つまり「平らな頂面と急な側面」という形になる。

Three things follow from the table and the plot. First, the height is 6 in the middle, 4 at an edge such as $X=0, Y=8$, and $6-2-2=2$ at the corner $(0,0)$. Second, the range is not symmetric: $u=-1$ at $X=0$ but only $7/8$ at $X=15$, so the $X=0$ side is the steepest ($g_x=-2$) while the $X=15$ side is much gentler ($g_x \approx 0.785$). Third, the X term depends only on $X$ and the Y term only on $Y$, so the two directions can be treated separately.從圖表可以看出三件事。第一，中央高度 6，邊緣（如 $X=0, Y=8$）高度 4，角落 $(0,0)$ 高度 $6-2-2=2$。第二，範圍不對稱：$X=0$ 時 $u=-1$，$X=15$ 時 $u$ 只有 $7/8$，所以 $X=0$ 那側最陡（$g_x=-2$），$X=15$ 那側緩和得多（$g_x \approx 0.785$）。第三，X 部分只跟 $X$ 有關、Y 部分只跟 $Y$ 有關，兩個方向可以分開看。図と表から三つのことが読み取れる。第一に、中央の高さは 6、縁（例えば $X=0, Y=8$）では 4、角 $(0,0)$ では $6-2-2=2$ である。第二に、範囲は非対称で、$X=0$ では $u=-1$ だが $X=15$ では $u$ は $7/8$ にしかならない。したがって $X=0$ 側が最も急（$g_x=-2$）で、$X=15$ 側はかなり緩やかである（$g_x \approx 0.785$）。第三に、X の項は $X$ だけ、Y の項は $Y$ だけに依存するので、二つの方向を分けて考えてよい。

System block diagram and I/O系統方塊圖與輸入/輸出システムブロック図と入出力

The host supplies the clock, the reset and the refractive index RI. When REFRACT has finished computing it writes 512 words into the host's SRAM through the SRAM interface, and finally raises DONE.Host 提供時脈、reset 和折射率 RI；REFRACT 算完後透過 SRAM 介面把 512 筆資料寫進 Host 的 SRAM，最後拉高 DONE。Host がクロック、reset、屈折率 RI を供給する。REFRACT は計算が終わると SRAM インタフェース経由で 512 ワードを Host の SRAM に書き込み、最後に DONE を立てる。

Input and output timing資料輸入與輸出時序データ入出力のタイミング

When RST goes high, RI is presented at the same time and then stays unchanged for the whole computation.RST 拉高時，RI 同時送入，之後整個運算期間保持不變。RST が立ち上がるときに RI も同時に与えられ、以後は計算が終わるまで変化しない。

When the results are written SRAM_WE goes high. Each ray produces two consecutive words: zx at address 0, zy at address 1, and so on — zx first, then zy. The "⋯⋯" between two write bursts means any number of cycles may pass between one ray and the next.寫入結果時 SRAM_WE 拉高，每條光線連續寫兩筆：位址 0 寫 zx、位址 1 寫 zy，依此類推，先 zx 後 zy。兩組寫入之間的「⋯⋯」代表不同光線之間可以間隔任意多個 cycle。結果を書き込むときに SRAM_WE を立てる。光線 1 本につき連続して 2 ワードを書き、アドレス 0 に zx、アドレス 1 に zy、以下同様に、zx が先、zy が後である。書き込みの間にある「⋯⋯」は、光線と光線の間に何サイクル空けてもよいことを表す。

Only after all 256 rays have been written is DONE raised; the host then starts checking the contents of the SRAM.256 條光線全部寫完後拉高 DONE，Host 才開始比對 SRAM 內容。256 本の光線をすべて書き終えてから DONE を立てる。Host はそれを受けて SRAM の内容の照合を始める。

The law of refraction折射定律屈折の法則

$\theta_1$ and $\theta_2$ are the angles that the incident and the refracted ray make with the normal (the handout mislabels the second one as θ1). Glass has a larger refractive index than air, so the refracted ray leans towards the normal. Trigonometric functions are awkward in hardware, so the vector form is used instead:$\theta_1$、$\theta_2$ 分別是入射光、折射光和法線的夾角（題目文件中第二個符號誤植為 θ1）。玻璃折射率比空氣大，折射光會往法線方向靠攏。三角函數不利硬體實現，所以改用向量形式：$\theta_1$、$\theta_2$ はそれぞれ入射光、屈折光が法線となす角である（課題資料では二つ目の記号が θ1 と誤記されている）。ガラスの屈折率は空気より大きいので、屈折光は法線の方向に寄る。三角関数はハードウェア化に向かないため、ベクトル形式に書き換える。

Deriving the refraction formula for the surface曲面折射公式推導曲面屈折の式の導出

The plan: find the normal vector at the point of incidence, substitute it into the vector refraction formula to get the refracted direction, then intersect that ray with the plane $Z=0$.思路：先求入射點的法向量，代入向量折射公式求折射方向，再求折射光與 $Z=0$ 平面的交點。方針：まず入射点の法線ベクトルを求め、ベクトル形式の屈折公式に代入して屈折方向を得る。次にその屈折光と $Z=0$ 平面との交点を求める。

The gradient $\nabla f$ of an implicit function is perpendicular to the surface, so it gives the direction of the normal.隱函數的梯度 $\nabla f$ 垂直於曲面，就是法向量方向。陰関数の勾配 $\nabla f$ は曲面に垂直であり、そのまま法線の向きを与える。

The factor 8 from differentiating the eighth power cancels the $\tfrac{1}{8}$ from the chain rule. The unit normal is $\mathbf{N} = \mathbf{g}/\sqrt{g^2}$, where $g^2 = g_x^2 + g_y^2 + 1$.8 次方微分產生的係數 8 和連鎖律的 $\tfrac{1}{8}$ 抵銷。單位法向量 $\mathbf{N} = \mathbf{g}/\sqrt{g^2}$，其中 $g^2 = g_x^2 + g_y^2 + 1$。8 乗の微分で出る係数 8 と、連鎖律の $\tfrac{1}{8}$ が打ち消し合う。単位法線ベクトルは $\mathbf{N} = \mathbf{g}/\sqrt{g^2}$ であり、ここで $g^2 = g_x^2 + g_y^2 + 1$ である。

Since $\sqrt{k}\cdot\tfrac{1}{\sqrt{g^2}} = \tfrac{\sqrt{k\,g^2}}{g^2}$, what used to need two square roots now needs only one:$\sqrt{k}\cdot\tfrac{1}{\sqrt{g^2}} = \tfrac{\sqrt{k\,g^2}}{g^2}$，原本要開兩次根號，現在只需要一次：$\sqrt{k}\cdot\tfrac{1}{\sqrt{g^2}} = \tfrac{\sqrt{k\,g^2}}{g^2}$ であるから、もともと 2 回必要だった平方根が 1 回で済む。

A worked example and the effect of RI數值驗算與 RI 的影響数値検算と RI の影響

Take $(X, Y) = (15, 8)$ with $RI = 5$ (so $\eta = 0.2$) and follow the steps above:以 $(X, Y) = (15, 8)$、$RI = 5$（$\eta = 0.2$）為例，依上面的步驟計算：$(X, Y) = (15, 8)$、$RI = 5$（$\eta = 0.2$）を例に、上の手順どおりに計算する。

The larger RI is, the more the ray bends. A higher refractive index pulls the refracted ray closer to the normal, and here the normal leans towards the centre, so the landing point moves inwards: for $(15,8)$, $zx \approx 13.05$ at RI = 2, 11.80 at RI = 5 and about 11.17 at RI = 15. The right-hand plot also shows that in the central region the landing points almost coincide with the entry points, the displacement being concentrated in the outer two rings.RI 越大，偏折越多。折射率越大，光線越往法線靠攏，而這裡的法線往中心傾斜，所以落點更靠近中心：$(15,8)$ 在 RI = 2 時 $zx \approx 13.05$，RI = 5 時 11.80，RI = 15 時約 11.17。右圖也可以看到中央區域的落點幾乎與入射點重合，偏移集中在外圍兩圈。RI が大きいほど曲がりも大きい。屈折率が大きいほど光線は法線に寄り、ここでの法線は中心へ傾いているので、落下点はより中心に近づく。$(15,8)$ の場合、RI = 2 で $zx \approx 13.05$、RI = 5 で 11.80、RI = 15 で約 11.17 となる。右図を見ると、中央付近では落下点が入射点とほぼ重なり、ずれは外側 2 周に集中していることも分かる。

Working through all 14 values of RI and all 256 rays, the landing points lie roughly between 1.29 and 14.05, comfortably inside the 0 ~ 16 range that Q4.12 can represent.14 種 RI、256 條光線全部算過，落點約在 1.29 到 14.05 之間，都在 Q4.12 可表示的 0 ~ 16 以內。14 種類の RI と 256 本の光線をすべて計算すると、落下点はおよそ 1.29 から 14.05 の範囲に収まり、いずれも Q4.12 で表現できる 0 ~ 16 の中に入る。

Interactive 3-D view互動式 3D 視圖インタラクティブ 3D ビュー

An interactive version of the figures above. Drag to rotate and scroll to zoom; moving the RI slider recomputes all 256 rays live. Colour encodes how far the landing point has moved from the entry point, with the top of the scale fixed at 7 cm (the largest value over RI 2 ~ 15), so colours can be compared directly between different values of RI.上面幾張圖的互動版。拖曳可旋轉、滾輪縮放，拉動 RI 會即時重算 256 條光線；顏色代表落點相對入射點的偏移量，色階上限固定在 7 cm（RI 2 ~ 15 之間的最大值），所以不同 RI 之間可以直接比顏色。上の図のインタラクティブ版である。ドラッグで回転、ホイールで拡大縮小でき、RI を動かすと 256 本の光線がその場で再計算される。色は落下点が入射点からどれだけずれたかを表し、色スケールの上限は 7 cm（RI 2 ~ 15 の範囲での最大値）に固定してあるので、RI が違っても色をそのまま比較できる。

Hovering over any point in the landing-point plots shows its zx / zy, its displacement, and the SRAM address and Q4.12 encoding from Section 10. Switching "Surface" to Symmetric moves both the centre and the normalising half-width to 7.5 (the midpoint of the 0 ~ 15 sampling range), which makes all four edges 4 high and all four corners 2. The version in the handout puts the centre at 8, half a grid step off, which is why the X = 0 side reaches u = −1 and is the steepest while the X = 15 side only reaches u = 7/8. The answers to be submitted follow the version in the handout.落點圖上滑過任一點，會顯示它的 zx / zy、偏移量，以及第 10 節的 SRAM 位址與 Q4.12 編碼。「曲面」切到四邊對稱是把中心與正規化半寬都改成 7.5（取樣範圍 0 ~ 15 的中點），四個邊高度全變成 4、四角全是 2；題目原版的中心在 8，偏了半格，所以 X = 0 那側 u = −1 最陡、X = 15 那側只有 u = 7/8。作業答案以題目原版為準。落下点の図で任意の点にマウスを乗せると、その zx / zy、ずれの大きさ、さらに第 10 節の SRAM アドレスと Q4.12 符号が表示される。「曲面」を四辺対称に切り替えると、中心と正規化半幅をどちらも 7.5（サンプリング範囲 0 ~ 15 の中点）に変え、四辺の高さはすべて 4、四隅はすべて 2 になる。課題どおりの版は中心が 8 で半目盛ずれているため、X = 0 側は u = −1 で最も急、X = 15 側は u = 7/8 にしかならない。提出する答えは課題どおりの版を基準とする。

Why the projection shows only two refracted rays投影圖為何只有兩條折射線投影図に屈折光が 2 本しかない理由

On the way in, all eight rays have X = 15, so the black dashed lines coincide exactly into one.入射時，8 條光線的 X 都是 15，所以黑色虛線完全重疊成一條。入射時は 8 本とも X = 15 なので、黒い破線は完全に重なって 1 本になる。

After refraction, the six rays at Y = 3 ~ 13 sit in the flat region in the Y direction, where $2\left(\frac{Y-8}{8}\right)^8$ is almost 0; their entry heights and their deflections are nearly identical, so they pile up into one line. The rays at Y = 1 and 15 land on the slope in the Y direction too, so an extra $2(7/8)^8 \approx 0.687$ is subtracted from Z; they start lower, closer to the bottom face, and reach it before bending as far inwards, which makes zx larger. The two are exact mirror images, so they pile up into a second line.折射後，Y = 3 ~ 13 這 6 條在 Y 方向位於平坦區，$2\left(\frac{Y-8}{8}\right)^8$ 幾乎為 0，入射高度和偏折量幾乎一樣，疊成一條；Y = 1、15 在 Y 方向也打在斜坡上，Z 多扣了 $2(7/8)^8 \approx 0.687$，起點較低、離底面較近，還沒往內偏那麼多就落地，zx 較大，兩者又剛好對稱，疊成另一條。屈折後は、Y = 3 ~ 13 の 6 本が Y 方向で平坦な領域にあり、$2\left(\frac{Y-8}{8}\right)^8$ がほぼ 0 になる。入射高さも曲がり方もほとんど同じなので、重なって1 本に見える。Y = 1、15 は Y 方向でも斜面に当たるため、Z から $2(7/8)^8 \approx 0.687$ だけ余分に引かれる。出発点が低く底面に近いので、内側へそれほど曲がらないうちに底面に達し、zx が大きくなる。この 2 本はちょうど対称なので、重なってもう 1 本になる。

Seen from the YZ plane the Y coordinate is unfolded and the eight rays separate. The landing points at X = 15 therefore fall into two groups, around 11.8 and 12.3 (RI = 5).改從 YZ 面看，Y 座標展開，8 條光線就各自分開了。所以 X = 15 的落點其實分成兩群：約 11.8 和 12.3（RI = 5）。YZ 面から見れば Y 座標が展開され、8 本の光線はそれぞれ分かれる。つまり X = 15 の落下点は、約 11.8 と 12.3（RI = 5）の 2 つのグループに分かれている。

Is curvature data for the glass surface needed?需要玻璃曲面的曲度資料嗎ガラス曲面の曲率データは必要か

The height Z: because the ray travels straight down, the point of entry is simply $(X, Y, Z(X,Y))$ — substitute into the formula, with no ray-surface intersection to solve. Z fixes how far the ray is from the bottom face.高度 Z：光線垂直往下，入射點就是 $(X, Y, Z(X,Y))$，直接代公式即可，不用解光線與曲面的交點。Z 決定光線離底面多遠。高さ Z：光線は垂直に下りるので、入射点はそのまま $(X, Y, Z(X,Y))$ である。式に代入するだけでよく、光線と曲面の交点を解く必要はない。Z は光線が底面からどれだけ離れているかを決める。

The normal $(g_x, g_y, 1)$: the direction of refraction depends only on how the tangent plane at the entry point is tilted, that is, on the first derivative (the slope).法向量 $(g_x, g_y, 1)$：折射方向只取決於入射點的切平面傾斜程度，也就是一次微分（斜率）。法線ベクトル $(g_x, g_y, 1)$：屈折方向は入射点における接平面の傾き、すなわち 1 階微分（傾き）だけで決まる。

Curvature in the usual sense is a second derivative and describes how sharply the surface bends; the law of refraction only looks at the local direction of the normal, which has nothing to do with that bending, so it is never needed. Besides, X and Y are integers from 0 to 15, only 16 cases per direction, and every height and slope required can be computed straight from the formula.一般說的曲度（curvature）是二次微分，描述曲面彎曲的程度；但折射定律只看局部法線方向，跟曲面怎麼彎無關，所以用不到。另外 X、Y 都是 0 ~ 15 的整數，每個方向只有 16 種情況，所需的高度和斜率都能直接從公式算出。一般にいう曲率（curvature）は 2 階微分であり、曲面の曲がり具合を表す。しかし屈折の法則が見るのは局所的な法線の向きだけで、曲面がどう曲がっているかとは無関係なので、曲率は使わない。さらに X、Y はいずれも 0 ~ 15 の整数で各方向 16 通りしかなく、必要な高さと傾きはすべて式から直接計算できる。

SRAM contents and formatSRAM 內容與格式SRAM の内容とフォーマット

The SRAM holds 512 words of 16 bits each, in unsigned Q4.12: the top 4 bits are the integer part and the lower 12 bits the fraction. The real value is the stored integer ÷ 4096 — for example $11.80148$ is stored as $\lfloor 11.80148 \times 4096 \rfloor = 48338$ (0xBCD2).SRAM 共 512 個 word，每個 16 bits，採無號 Q4.12：最高 4 bits 是整數部分，後 12 bits 是小數部分。實際數值 = 存入的整數 ÷ 4096，例如 $11.80148$ 約存成 $\lfloor 11.80148 \times 4096 \rfloor = 48338$（0xBCD2）。SRAM は 16 bit の word を 512 個もち、符号なし Q4.12 を用いる。上位 4 bit が整数部、下位 12 bit が小数部である。実際の値は格納された整数 ÷ 4096 で、例えば $11.80148$ は $\lfloor 11.80148 \times 4096 \rfloor = 48338$（0xBCD2）として格納される。

Each ray occupies two words, zx first and zy second. Within one row $Y$ the entries run $X = 0 \sim 15$ in order, then the next row follows:每條光線佔兩個 word，先 zx 後 zy；同一列 $Y$ 依序排 $X = 0 \sim 15$，再換下一列：光線 1 本につき 2 word を使い、zx が先、zy が後である。同じ行 $Y$ の中では $X = 0 \sim 15$ の順に並び、その後に次の行が続く。

Checking the example in the figure: for $X=1, Y=15$ the zx address is $32\times15 + 2 = 482$.驗證圖中的例子：$X=1, Y=15$ 時，zx 位址 $= 32\times15 + 2 = 482$。図中の例で確認すると、$X=1, Y=15$ のとき zx のアドレスは $32\times15 + 2 = 482$ である。

Error tolerance誤差容忍誤差の許容範囲

A landing point counts as correct if it is within 1/256 of the reference answer. The least significant step of Q4.12 is 1/4096, sixteen times finer than that tolerance, but if the intermediate operations (the eighth power, the division, the square root) are truncated to too few bits the accumulated error can still exceed it.落點與標準答案的距離小於 1/256 即算正確。Q4.12 的最小刻度是 1/4096，比容忍範圍細 16 倍，但中間運算（8 次方、除法、開根號）的位元數截得太短，誤差累積起來仍可能超標。落下点と模範解答との距離が 1/256 未満であれば正解とみなされる。Q4.12 の最小刻みは 1/4096 で許容範囲より 16 倍細かいが、途中の演算（8 乗、除算、平方根）のビット幅を切り詰めすぎると、誤差が積み重なって許容範囲を超えることがある。

Implementing the square root in hardware開根號的硬體實作平方根のハードウェア実装

After the rearrangement in Section 6, $coef = \dfrac{\eta - \sqrt{k\,g^2}}{g^2}$ leaves just one square root per ray — but Verilog has no built-in square root. The sqrt_seq below uses the restoring, digit-by-digit method: one result bit per cycle, with only a comparison and a subtraction on the datapath and no multiplier, so it is small and easy to meet timing with. The latency is $W/2$ cycles after start.第 6 節整理後的 $coef = \dfrac{\eta - \sqrt{k\,g^2}}{g^2}$，每條光線只剩下一次開根號，但 Verilog 沒有內建的平方根。下面這個 sqrt_seq 採逐位還原法（restoring, digit-by-digit），一個 cycle 決定一個結果 bit，資料路徑上只有比較與減法、沒有乘法器，面積小也容易過時序。延遲是 start 之後 $W/2$ 個 cycle。第 6 節で整理した $coef = \dfrac{\eta - \sqrt{k\,g^2}}{g^2}$ では、光線 1 本あたり平方根が 1 回だけ残る。しかし Verilog に平方根は組み込まれていない。次の sqrt_seq は復元型の逐次桁計算（restoring, digit-by-digit）を使い、1 サイクルで結果を 1 bit 決める。データパスには比較と減算しかなく乗算器が要らないので、面積が小さくタイミングも通しやすい。レイテンシは start から $W/2$ サイクルである。

sqrt_seq.v

// Generic bit-serial square root (restoring, digit-by-digit)
// root = floor( sqrt(radicand) ), one result bit per clock cycle
// Latency: W/2 cycles after start
module sqrt_seq #(
    parameter W = 16                     // radicand width (must be even)
)(
    input  wire           clk,
    input  wire           rst,           // active-high asynchronous reset
    input  wire           start,         // pulse to begin
    input  wire [W-1:0]   radicand,
    output reg  [W/2-1:0] root,
    output reg            done
);
    localparam N = W / 2;

    reg [W-1:0]   x;                     // remaining radicand bits (shifted out 2 at a time)
    reg [N+1:0]   rem;                   // partial remainder
    reg [$clog2(N+1)-1:0] cnt;
    reg           busy;

    wire [N+1:0] rem_sh = {rem[N-1:0], x[W-1:W-2]};   // bring down next 2 bits
    wire [N+1:0] trial  = {root, 2'b01};              // 4*root + 1
    wire         ge     = (rem_sh >= trial);

    always @(posedge clk or posedge rst) begin
        if (rst) begin
            x <= 0; rem <= 0; root <= 0; cnt <= 0; busy <= 0; done <= 0;
        end else begin
            done <= 0;
            if (start && !busy) begin
                x <= radicand; rem <= 0; root <= 0; cnt <= N; busy <= 1;
            end else if (busy) begin
                rem  <= ge ? rem_sh - trial : rem_sh;
                root <= {root[N-2:0], ge};
                x    <= x << 2;
                cnt  <= cnt - 1;
                if (cnt == 1) begin busy <= 0; done <= 1; end
            end
        end
    end
endmodule

How the code maps onto the algorithm程式碼對應演算法步驟コードとアルゴリズムの対応

Why the trial value is $4 \times root + 1$為什麼試算值是 $4 \times root + 1$試行値が $4 \times root + 1$ である理由

Suppose the result obtained so far is $r$ and the next bit is tried as a 1, making the new result $2r+1$. The difference between the squares of the new and the old result, after the two-place left shift that aligns them, is:假設目前已求出的結果是 $r$，下一個 bit 想試試看放 1，新的結果就是 $2r+1$。新結果的平方與舊結果平方的差（左移 2 位對齊後）是：これまでに求めた結果を $r$ とし、次の bit に 1 を置いてみると、新しい結果は $2r+1$ になる。新旧の結果の平方の差（2 bit 左シフトで桁を合わせた後）は次のようになる。

So asking whether the remainder is $\ge 4r+1$ is enough to decide whether that bit can be a 1 — no multiplication at all.所以只要比較「餘數是否 $\ge 4r+1$」，就知道這個 bit 能不能放 1，完全不需要乘法。したがって「余りが $\ge 4r+1$ かどうか」を比べるだけでその bit に 1 を置けるかが分かり、乗算は一切要らない。

Worked by hand: $\sqrt{10}$手算範例：$\sqrt{10}$手計算の例：$\sqrt{10}$

10 in binary is 00 00 10 10 (with $W=8$, $N=4$):10 的二進位是 00 00 10 10（$W=8$、$N=4$）：10 の 2 進表現は 00 00 10 10 である（$W=8$、$N=4$）。

The result is root = 3 with remainder 1, that is $3^2 + 1 = 10$, so $\lfloor\sqrt{10}\rfloor = 3$.結果 root = 3、餘數 1，也就是 $3^2 + 1 = 10$，$\lfloor\sqrt{10}\rfloor = 3$。結果は root = 3、余り 1、すなわち $3^2 + 1 = 10$ であり、$\lfloor\sqrt{10}\rfloor = 3$ となる。

Testbench tb_sqrt_seq.v測試檔 tb_sqrt_seq.vテストベンチ tb_sqrt_seq.v

module tb;
  reg clk=0,rst=1,start=0; reg [15:0] a; wire [7:0] r; wire d;
  sqrt_seq #(16) u(clk,rst,start,a,r,d);
  always #5 clk=~clk;
  integer i,err=0,expv;
  initial begin
    #12 rst=0;
    for(i=0;i<65536;i=i+1) begin
      @(negedge clk) a=i; start=1; @(negedge clk) start=0;
      wait(d); expv=$floor($sqrt(i)); if(r!==expv) begin err=err+1; if(err<5)$display("ERR %d %d %d",i,r,expv); end
    end
    $display("errors=%0d",err); $finish;
  end
endmodule

The command below runs every input from 0 to 65535 and prints errors=0.用以下指令跑完 0 ~ 65535 全部輸入，輸出 errors=0。次のコマンドで 0 ~ 65535 のすべての入力を通すと、errors=0 と出力される。

iverilog -g2012 -o t tb_sqrt_seq.v sqrt_seq.v && vvp t

Process setup製程設定プロセスの設定

EP1 must be synthesised with the ADFP_n16 process (the TSMC 16 nm academic process kit). Before starting Design Compiler, type the command below in the terminal and then pick ADFP_n16 from the menu.EP1 必須使用 ADFP_n16 製程（TSMC 16nm 學術用製程套件）合成。啟動 Design Compiler 前，先在終端機輸入以下指令，再於選單中選擇 ADFP_n16。EP1 は ADFP_n16 プロセス（TSMC 16nm のアカデミック向けプロセスキット）で合成しなければならない。Design Compiler を起動する前に、端末で次のコマンドを入力し、メニューから ADFP_n16 を選ぶ。

snsd

Simulation commands模擬指令シミュレーションコマンド

Every xrun below may be replaced by ncverilog.以下 xrun 皆可替換成 ncverilog。以下の xrun はいずれも ncverilog に置き換えてよい。

RTL simulationRTL 模擬RTL シミュレーション

xrun tb.v REFRACT.v +define+RI=5 +access+r -clean -createdebugdb \
     -input xrun.tcl \
     +incdir+/cad/synopsys/synthesis/cur/dw/sim_ver/ +libext+.v

Gate-level simulationGate-level 模擬ゲートレベルシミュレーション

xrun tb.v REFRACT_syn.v +define+SDF+RI=5 +access+r -clean -createdebugdb \
     -input xrun.tcl -v N16ADFP_StdCell.v

Timing requirement時序要求タイミング要件

The gate-level simulation must not report any timing violation (setup / hold violation warnings); otherwise the design is treated as failing.Gate-level 模擬結果不能出現任何 timing violation（setup / hold violation 警告），否則視為未通過。ゲートレベルシミュレーションの結果に timing violation が一つも出てはならない（setup / hold violation の警告）。出た場合は不合格とみなされる。

Filling in the Excel sheet填寫 ExcelExcel の記入

Enter the circuit figures of your best version into Summary_Table_for_EP1.xlsx: Area (after synthesis), Period (the clock period), Power, Latency (the time or number of cycles from input to output), and whether the simulation passed.將最佳版本設計的電路資訊填入 Summary_Table_for_EP1.xlsx：Area（合成後面積）、Period（時脈週期）、Power（功耗）、Latency（輸入到輸出所需時間或 cycle 數），以及模擬是否通過。最良の版の回路情報を Summary_Table_for_EP1.xlsx に記入する。Area（合成後の面積）、Period（クロック周期）、Power（消費電力）、Latency（入力から出力までの時間またはサイクル数）、そしてシミュレーションに合格したかどうかである。

Change the period in both files at once修改 Period 時要同步兩個檔案Period を変更するときは 2 つのファイルを揃える

The two must agree, or the timing target used for synthesis will not match the clock the simulation actually runs at.兩邊必須一致，否則合成的時序目標和模擬實際使用的時脈會對不上。両者は一致していなければならない。さもないと合成のタイミング目標と、シミュレーションで実際に使うクロックが食い違う。

Files to submit繳交檔案提出ファイル

G01_[驗證碼]/
├── EP1_G01.ppt                  簡報
├── Summary_Table_for_EP1.xlsx   電路資訊表
├── REFRACT_syn.ddc              合成後的資料庫檔
└── REFRACT.v                    RTL 原始碼

Checklist before submitting繳交前檢查提出前のチェック

✓ Synthesised with the ADFP_n16 process✓ 使用 ADFP_n16 製程合成✓ ADFP_n16 プロセスで合成した
✓ Both the RTL and the gate-level simulation pass✓ RTL 與 gate-level 模擬皆通過✓ RTL とゲートレベルのシミュレーションがどちらも通った
✓ No timing violation in the gate-level simulation✓ gate-level 模擬無任何 timing violation✓ ゲートレベルシミュレーションに timing violation がない
✓ The period in REFRACT.sdc matches the one in tb.v✓ REFRACT.sdc 與 tb.v 的 period 一致✓ REFRACT.sdc と tb.v の period が一致している
✓ The Excel sheet holds the figures of the best version✓ Excel 已填入最佳版本的數據✓ Excel に最良の版のデータを記入した
✓ The RTL is merged into a single REFRACT.v✓ RTL 已合併為單一 REFRACT.v✓ RTL を単一の REFRACT.v にまとめた
✓ The folder and file names follow the required format✓ 資料夾與檔名依規定格式命名✓ フォルダ名とファイル名が規定の形式に従っている