Error detection/correction and fault detection/recovery – Pulse or data error handling – Error count or rate
Reexamination Certificate
1999-10-21
2003-05-06
Tu, Christine T. (Department: 2133)
Error detection/correction and fault detection/recovery
Pulse or data error handling
Error count or rate
Reexamination Certificate
active
06560727
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention
This invention relates to generation of linear recurring sequences and the utilization of such sequences.
2. Relevant Background
Definitions
Asynchronous Transfer Mode (ATM): a communications protocol with a 384 bit data frame (payload) size.
Bit Error Rate Test (BERT) equipment: tests for errors by outputting a long stream of pseudorandom bits onto the communication line. The communication line is looped back to the BERT so that the same bits that it sends out should return to it. The BERT then compares the return bits to find any bits that are altered while they traveled over the communication line.
Characteristic Polynomial: usually associated with the Galois form of LFSR. Inverse of the feedback polynomial.
Companion matrices: a linear algebraic characterization of an LFSR function that allows manipulation of linear feedback shift registers using matrix arithmetic.
Decimate: to replace an integer sequence, S={S
1
, S
2
, S
3
, . . . , S
2
n
−1
}, with the sequence S
k
={S
k1
, S
2k(mod 2
n
)
, S
3k(mod 2
n
)
, S
4k(mod 2
n
)
, . . . , S
k(2
n
−1)(mod 2
n
)
}, thereby producing a sequence of every K
th
element of the main sequence S. When all the decimations of a sequence are combined in proper order, the original sequence S can be reconstructed. If the decimations are in parallel, the amount of time it takes to generate S is reduced by a factor of k.
Decimation Matrix: is a companion matrix raised to a power k, corresponding to a “jump” in the number of states spanned by each multiplication mod
2
of the companion matrix.
Feedback Polynomial: inverse of characteristic polynomial. Usually associated with the Fibonacci form of LFSR.
Irreducible Polynomial: is a polynomial that cannot be expressed as the product of two other polynomials except for 1 and itself.
Linear Feedback Shift Register (LFSR): a type of shift register incorporating linear feedback of the present contents of the register to determine future contents of the register.
Linear Recurring Sequences (LRS): are pseudorandom sequences of digits derived from linear difference equations. A binary LRS is a sequence of 1's and 0's.
Linear Recurring Sequence Generator (LRSG): incorporates at least one linear feedback shift register or equivalent circuitry to produce a linear recurring sequence.
Modulo
2
(mod
2
) arithmetic: is base two arithmetic where a=b(mod
2
) if a=b−kn for k=some integer and n=2. Mod
2
addition can be represented in hardware by the XOR function; Mod
2
multiplication can be represented in hardware by the AND function.
Period: The period of a linear recurring sequence is the number of digits before the sequence begins to repeat itself.
Primitive Polynomial: is an irreducible polynomial that divides x
2
n
−1
+1 but not x
d
+1 for any d that divides 2
n
−1.
Pseudonoise Generator: outputs a pseudonoise signal. For digital spread spectrum communications, the pseudonoise signal is a pseudorandom sequence of 1's and 0's (in other words, the output of a binary LRS).
Pseudonoise Signal: is noise that appears to be random but is not truly random.
Pseudorandom Sequence: a sequence of numbers that appears to be random when viewed over a limited range but is not truly random. At some point, the sequence will repeat itself.
Stream Ciphers: a type of cipher that encrypts a message one bit at a time.
Linear Recurring Sequences
A linear recurring sequence is a pseudorandom sequence of length L with the property that every n successive bits (n<L) appears only once in the sequence. For example, the sequence 0111010, which is discussed in detail hereinafter, is an LRS for n≧3. It is not a LRS for n=2, as the 2 bit sequence “11” appears as both the second and third bits and the third and fourth bits.
FIG. 1
shows a circular representation of the aforementioned LRS. Every combination of bits covered by the 3 bit window is unique. This circular model is useful because it emphasizes that an LRS is a pseudorandom sequence and at some point will begin to repeat itself. If a linear feedback shift register (discussed below), or its equivalent, ever becomes loaded entirely with zeros, it will only output zeros.
Many applications require the ultra-fast generation of an LRS which does not repeat for a long time. One such application is in Bit Error Rate Test (BERT) equipment for testing error statistics of communication lines. Another use is in communications encryption. For example, a linear recurring sequence can be used to feed a nonlinear encryption function, creating a keystream which is used to encrypt plaintext. An LRS is also conventionally used as the pseudonoise source in spread spectrum communications.
Linear Feedback Shift Registers
Linear recurring sequences are often implemented in hardware through the use of Linear Feedback Shift Registers (LFSR). As is known in the art, an LFSR is typically implemented using either the Fibonacci (
FIG. 2
) or Galois (
FIG. 3
) model of LFSR. The Fibonacci model is characterized by the input to the first delay element being a linear combination of signal taps at various other cells in the register. The Galois model is characterized by the input to the various cells being a linear combination of the output of the last cell and the previous cell. Each of these models can produce binary sequences having a very large period and excellent pseudorandom properties. While the Fibonacci and Galois shift registers can implement the same recurrence relation, the same sequence is generated only if each is started in the appropriate initial state.
Each LFSR can be described advantageously by a companion matrix. Because LFSRs can be either right-shifting or left-shifting, a companion matrix will take one of two general forms.
[
C
n
-
1
⋯
⋯
C
1
C
0
1
0
⋯
0
0
0
1
0
⋯
0
⋯
⋯
⋯
⋯
⋯
0
⋯
⋯
1
0
]
Left Shifting Galois (M1)
[
0
⋯
⋯
0
A
0
1
0
⋯
0
A
1
0
1
0
⋯
⋯
⋯
⋯
⋯
⋯
⋯
0
⋯
⋯
1
A
n
-
1
]
Left Shifting Fibonacci (M2)
[
0
1
⋯
0
0
0
0
1
⋯
0
0
⋯
⋯
⋯
0
0
⋯
⋯
0
1
C
0
C
1
⋯
⋯
C
n
-
1
]
Right shifting Galois (M3)
[
A
n
-
1
1
⋯
0
0
⋯
⋯
⋯
⋯
⋯
⋯
⋯
0
1
0
A
1
0
⋯
0
1
A
0
0
0
0
0
]
Right Shifting Fibonacci (M4)
The general forms are differentiated by the location of a diagonal row of 1's. If the LFSR is right-shifting, the companion matrix will have a diagonal row of 1's above the main diagonal. A left-shifting LFSR has a companion matrix with a diagonal row of 1's below the main diagonal.
A companion matrix also incorporates coefficients of a polynomial. The feedback polynomial coefficients for a Fibonacci LPSR are incorporated at the rightmost column in the left-shifting companion matrix and at the leftmost column for the right-shifting companion matrix. The characteristic polynomial coefficients for a Galois LFSR are incorporated at the top row of the left-shifting companion matrix and at the bottom row of the right-shifting companion matrix. In the Fibonacci form of M
2
and M
4
, A
0
is the coefficient for the oldest shift register element. A characteristic polynomial will have the form C
n
x
n
+C
n−1
x
n−1
+ . . . +c
z
x
2
+c
1
x
7
+c
0
x
0
, while its inverse, the feedback polynomial will be of the form a
0
x
n
+a
1
x
n−1
+ . . . +a
n−2
x
2
+a
n−1
x
1
+a
n
x
0
, where c
n
=A
n
; C
n−1
=A
n−1
, etc.
It is well known that in order for an LFSR to have a maximal LRS period, the polynomial formed from the sequence of taps must be a primitive polynomial. A method commonly used is to choose a random polynomial and test whether it is primitive. This test is usually ac
Maestas Joseph H.
Pierson Lyndon G.
Witzke Edward L.
Abraham Esaw
Libman George H.
Sandia Corporation
Tu Christine T.
LandOfFree
Bit error rate tester using fast parallel generation of... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Bit error rate tester using fast parallel generation of..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Bit error rate tester using fast parallel generation of... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3054965