BINOMIAL COEFFICIENTS GENERATOR

The newton circuit generates the sequence of

binomial coefficients for any $5-$bit integer power.

Whenever the en input is active the circuit reads the

input integer $n$ at din, and starts outputting, cycle by

cycle, the binomial coefficients of the polynomial

expansion for the binomial power $(a+b{)}^n.$

When no sequence is output, the dout value should

be zero. The sequence generated for $n$ lasts $n+1$

clock cycles, the first cycle for the first coefficient

$0),$ the second cycle for $k=1,$ a$.$s$.$o$.$ until the last cycle for $k=n.$

The $k$ term of the polynomial expansion is $(\frac{n}{k})=\frac{n!}{k!(n-k)!}$

To speed up the binomial coefficients generation and use less computational resources, a

recurrence relation is used, $(\frac{n}{k+1})=\frac{n-k}{k+1}(\frac{n}{k}),$ the very first term of any expansion being $(\frac{n}{0})=1.$

For $5-$bit input numbers, the biggest coefficient is $(\frac{31}{15})=(\frac{31}{16})=300,540,195.$ Even if the output

coefficient is always in the range of $32-$bit integer values, to avoid overflow during computations,

the internal register used in recurrence relation should have $33$ bits

$4,808,643,120>2^{32}.$ Be careful to arrange the multiplication before division in the recurrence

relation, to avoid errors due to inexact division.

Requirements:

Design the newton module, considering the rst and en inputs active high $($if logic $1),$ and positive

clock edges to be the active edges.

Write a testbench module, newton$\_$tb$,$ that instantiates the newton module with the instance

name dut and generates the en and din inputs as shown in Figure $2.$

Strictly obey the newton module name and its interface pin names indicated in Figure $1,$ and the

name of the testbench module should be newton$\_$tb$.$ All names are lowercase.