MAXIMUM LENGTH PULSE SEQUENCE GENERATORS
First Claim
Patent Images
1. A machine implemented method for selecting which of the n stages of a shift register generator should be summed modulo-2 (in addition to the last stage) to produce a feedback signal to the first stage of the shift register to produce an output pulse sequence of maximum length of 2n-1 bits when one such feedback combination of stages is known, comprising the steps of:
- deriving a characteristic equation, a polynomial of degree n-1, the variable of which is the response matrix of the known feedback combination and the coefficients of whch are 1 or 0 depending on whether the stage represented by the exponent of the variable is summed or not, the zero power of the variable being an identity matrix with a coefficient of one;
generating a first matrix having n columns and 2n-1 rows, the columns representing the exponents of a polynomial of degree n1 and the rows representing successive powers of the response matrix of the known combination, the elements of which are 1 or 0 depending on whether the powers of the variable corresponding to the column number is summed or not to equal the power of the variable corresponding to the row number, where the characteristic equation is substituted for the n-th power of the variable where it appears;
generating a second matrix of n rows and n-1 columns, the successive rows of which are every k mod (2n-1)-th row of the first matrix with the column corresponding to the zero power of the variable eliminated, where k is an odd prime number that is also prime to 2n-1;
the known solution, all the solutions have been found. This is also known because which is Euler'"'"''"'"'s Function. reducing the second matrix by adding modulo-2 one column to another so that each row except the last has only one element with a value of one and each such element in a differeent column for each row; and
selecting as the feedback stages, in addition to the last stage, those stages corresponding to the row number having an element with a value of one in a column in which the last row has an element with a value of one.
0 Assignments
0 Petitions
Accused Products
Abstract
An n stage shift register can be operated as a digital pulse sequence generator by feeding back to the first stage the modulo 2 sum of the signals produced by at least two stages of the register. By properly selecting the stages from which the modulo 2 sum feedback signal is derived, the register can be made to produce a pseudo random sequence of 2n-1 digits (the maximum length sequence possible for n stages). This application relates to a machine implemented process for calculating from a specific feedback connection producing a maximum length sequence all other feedback connections that will produce a maximum length sequence.
48 Citations
2 Claims
-
1. A machine implemented method for selecting which of the n stages of a shift register generator should be summed modulo-2 (in addition to the last stage) to produce a feedback signal to the first stage of the shift register to produce an output pulse sequence of maximum length of 2n-1 bits when one such feedback combination of stages is known, comprising the steps of:
- deriving a characteristic equation, a polynomial of degree n-1, the variable of which is the response matrix of the known feedback combination and the coefficients of whch are 1 or 0 depending on whether the stage represented by the exponent of the variable is summed or not, the zero power of the variable being an identity matrix with a coefficient of one;
generating a first matrix having n columns and 2n-1 rows, the columns representing the exponents of a polynomial of degree n1 and the rows representing successive powers of the response matrix of the known combination, the elements of which are 1 or 0 depending on whether the powers of the variable corresponding to the column number is summed or not to equal the power of the variable corresponding to the row number, where the characteristic equation is substituted for the n-th power of the variable where it appears;
generating a second matrix of n rows and n-1 columns, the successive rows of which are every k mod (2n-1)-th row of the first matrix with the column corresponding to the zero power of the variable eliminated, where k is an odd prime number that is also prime to 2n-1;
the known solution, all the solutions have been found. This is also known because which is Euler'"'"''"'"'s Function. reducing the second matrix by adding modulo-2 one column to another so that each row except the last has only one element with a value of one and each such element in a differeent column for each row; and
selecting as the feedback stages, in addition to the last stage, those stages corresponding to the row number having an element with a value of one in a column in which the last row has an element with a value of one.
- deriving a characteristic equation, a polynomial of degree n-1, the variable of which is the response matrix of the known feedback combination and the coefficients of whch are 1 or 0 depending on whether the stage represented by the exponent of the variable is summed or not, the zero power of the variable being an identity matrix with a coefficient of one;
-
2. A machine implemented method for finding which of n stages in a shift register should be summed modulo-2 to the last stage to provide a feedback signal to the first stage of the shift register to generate an output from one stage of a maximum length sequence of 2n-1 bits when one such feedback combination of stages is known, comprising the steps of:
- deriving a characteristic equation vector having elements aj such that
Specification
-
- Resources
Litigation Campaign Assessment
Thank you for your request. You will receive a custom alert email when the Litigation Campaign Assessment is available.
×
-
Current AssigneeEdward Charles Farnett, Lee Oliver Jr. Upton
-
Original AssigneeEdward Charles Farnett, Lee Oliver Jr. Upton
-
InventorsFarnett, Edward Charles, Upton, Lee Oliver Jr.
-
Primary Examiner(s)Atkinson, Charles E.
-
Application NumberUS04/880,028Time in Patent Office692 DaysField of Search235/152,153 340/146.1,348 331/78US Class Current708/252CPC Class CodesG06F 2207/581 Generating an LFSR sequence...G06F 2207/583 Serial finite field impleme...G06F 7/584 using finite field arithmet...
