![18.7 DESIGN 2: DESIGN SPACE EXPLORATION WHEN s2 = [1 0]](https://imgdetail.ebookreading.net/cover/cover/software_development/EB9780470934630.jpg)
18.7 DESIGN 2: DESIGN SPACE EXPLORATION WHEN s2 = [1 0]
Figure 18.4 shows the DAG for the polynomial division algorithm based on our timing function choice s2. We note from the figure that the signals corresponding to the coefficients of B and the intermediate partial remainders corresponding to R and Q are all pipelined, as indicated by the arrows connecting the nodes. However, the estimated q output is broadcast among the nodes, as indicated by the horizontal lines without arrows. There are three simple projection vectors such that all of them satisfy Eq. 18.21 for the scheduling function in Eq. 18.18. The three projection vectors will produce three designs:
(18.31)
(18.32)
(18.33)
Figure 18.4 DAG for polynomial division algorithm when s2 = [1 0], n = 9, and m = 5.
The corresponding projection matrices are
(18.34)
(18.35)
(18.36)
Our multithreaded design space now allows for three configurations for each projection vector for the chosen timing function.
The different projection directions will produce identical designs through proper
relabeling of the nodes. The resulting 
will consist of m tasks that are all active
at each time step. The design will result in the well-known Galois (Type 2) LFSR. A point in the DAG given by the coordinates p = [i j]t will be mapped by the
projection matrix P2a into the point 
= P2ap. The 
corresponding to design 2
is shown in Fig. 18.5. The 
consists of m − 1 nodes. Input coefficients of A
are fed from the right and the partial remainders are pipelined to all nodes. Coefficient bj of B is stored in node Tj. The task details for hardware systolic implementation are shown in Fig. 18.5b, where D denotes a 1-bit register to store the partial output.
Figure 18.5 
for Galois (Type 2) LFSR when s1 = [1 0], d2a = [1 0]t, n = 9, and m = 5. (a) The resulting tasks at each SPA stage. (b) The task workload details.
Let ri, 0 ≤ i < m, be the present output of task Ti. The next state output 
is given by
(18.37)
And we identify the output and input of the Galois LFSR as
(18.38)
(18.39)
The above equations determine the operation of the Galois (Type 2) LFSR as follows:
1. Clear all the registers.
2. For time steps 0–4, the LFSR is working as a simple shift register moving the coefficients a9 to a5 between the stages.
3. At time step 4, the first quotient coefficient q4 is obtained and is available at the next time step to the leftmost node.
4. The coefficients of Q are obtained from the leftmost node at time steps 4–9.
5. At the end of time step 9, all the remainder polynomial R coefficients are stored in the shift register stages. They could be read off the LFSR in parallel if desired.
6. If it is desired to shift the R coefficients out, then the feedback path must be broken to selectively disable the LFSR action.