Eq 2_2_4 derivation REVD
DOCX · 18.6 KB
Open DOCX file
A short note dated 3.26.05 by Phil, correcting an error in the original steps leading to Eq. (2.2.4) of his Scrambler write-up. It encodes the k register states of the Figure 2 shift register as a polynomial q(x), then proves q'(x) = x q(x) - o h(x) + i by manipulating the sums term by term and re-indexing. The register update rule q'_{j+1} = q_j - h_j o is the starting point.
AI-written summary; may contain errors.
Extracted text (machine-read; may contain errors)
This is the Title PhL 3.26.05
I had something wrong in my original set of lines resulting in (2.2.4). Here I correct them, and in the doc there is even more detail supplied. This was a non-obvious set of steps that only became non-obvious after I tried to follow them from the original doc!
The Figure 2 Iteration Equation
Figure 2 shows k registers q1 through qk. Construct the following polynomial:
q(x) = q1 + q2 x + q3 x2 + .... qk xk-1 = Σi=0k-1 qi+1xi (2.2.1)
One can regard q(x) as a representation of the state vector of the shift register generator.
As shown in (1.4.1), the equation which determines the behavior of a register qj in Figure 2 is
qj+1(s+1) = qj(s) - hj o(s)
where the subscript denotes a register stage, and the argument s is a time index. We have changed this time index from n to s, because we have another use for symbol n below. We now simplify this as:
q'j+1= qj - hj o (2.2.2)
where prime means one clock after no-prime. Thus, q(x) above records the register state before a clock, and q'(x) records the state after one clock,
q'(x) = q'1 + q'2 x + q'3 x2 + ... q'k xk-1 = Σi=0k-1 q'i+1xi . (2.2.3)
I now claim the following is true:
q'(x) = x q(x) - o h(x) + i (2.2.4)
Proof: Start with the right side using i = q0:
RHS = x q(x) - o h(x) + i
= x Σi=0k-1 qi+1xi - o Σi=0k hixi + q0
= Σi=0k-1 qi+1xi+1 - o Σi=0k hixi + q0 // now let i+1 = j
= Σj=1k qjxj - o Σi=0k hixi + q0
= Σj=0k qjxj - o Σi=0k hixi
= Σi=0k qixi - o Σi=0k hixi
= Σi=0k [qi - ohi] xi
= Σi=0k q'i+1 xi
= Σi=0k-1 q'i+1 xi + q'k+1 xk
= Σi=0k-1 q'i+1 x // since q'k+1 = qk+1(s+1)
= q'(x)