Consider a system $$y_{n+2} = ay_{n+1} + by_n$$
It is not surprising there for that the system has state representation
You see how every next value of y is computed by summing two previous states. This means that we do not need to store all previous values to compute the next. Two is sufficient. Therefore, we can allocate two numeric registers for two state variables That is, we initialize registers with $a_0$ and $a_1$. At every clock we update the values. Instead of writing result of $new_value(a_0, a_1)$ into $a_2$, we store it into second register. Value $a_1$ is shifted into the first register, overwriting $a_0$ there. We can do this since we do not need $a_0$ anymore (neither for computing $a_3$, nor $a_4$ and so on), and must do it since $a_1$ is needed for computing $a_3$. Effectively, register values $(a_n, a_{n+1})$ are updated with $(a_{n+1}, a_{n+2})$ at every clock cycle. The order of the system is the number of variables/registers that we need. It is also known as space complexity. Since transition function is linear, it may be represented in matrix form $$\begin{bmatrix}y_{n+2} \\ y_{n+1}\end{bmatrix} = \begin{bmatrix} a & b \\ 1 & 0 \end{bmatrix}\, \begin{bmatrix}y_{n+1} \\ y_{n}\end{bmatrix}$$ Space complexity is reduced from n to two. At every clock cycle, newly computed value is written into the most significant register. The less significant registers take their values from the more significant ones (we slide the window: head is computed, tail is discarded). In this example we have only two state registers. They are initialized with initial values, $y_0$ and $y_1$ and we say that "the system has order 2."
You see how every next value of y is computed by summing two previous states. This means that we do not need to store all previous values to compute the next. Two is sufficient. Therefore, we can allocate two numeric registers for two state variables That is, we initialize registers with $a_0$ and $a_1$. At every clock we update the values. Instead of writing result of $new_value(a_0, a_1)$ into $a_2$, we store it into second register. Value $a_1$ is shifted into the first register, overwriting $a_0$ there. We can do this since we do not need $a_0$ anymore (neither for computing $a_3$, nor $a_4$ and so on), and must do it since $a_1$ is needed for computing $a_3$. Effectively, register values $(a_n, a_{n+1})$ are updated with $(a_{n+1}, a_{n+2})$ at every clock cycle. The order of the system is the number of variables/registers that we need. It is also known as space complexity. Since transition function is linear, it may be represented in matrix form $$\begin{bmatrix}y_{n+2} \\ y_{n+1}\end{bmatrix} = \begin{bmatrix} a & b \\ 1 & 0 \end{bmatrix}\, \begin{bmatrix}y_{n+1} \\ y_{n}\end{bmatrix}$$ Space complexity is reduced from n to two. At every clock cycle, newly computed value is written into the most significant register. The less significant registers take their values from the more significant ones (we slide the window: head is computed, tail is discarded). In this example we have only two state registers. They are initialized with initial values, $y_0$ and $y_1$ and we say that "the system has order 2."
No comments:
Post a Comment