LFSR based scramblers
Please note that USA patent protected
Intellectual Property is contained within this document.
The LFSR may come in two basic configurations:
This configuration has a binary shift register with 4 shift register elements. Each shift register element can store one bit. Not shown, but assumed, is a clock signal. At the occurrence of the clock signal each shift element takes the signal at its input to be stored and replaces the existing content with the content at the input. The content of the shift register is thus shifted from left to right.
The first, the third and the fourth shift register
element have a tap or a connection into a logic function that is in this
case a binary XOR function. A XOR function can have in this example two
inputs and one output.
One may also use the EQUAL function in the LFSR. The truth table for the EQUAL function is provided below.
2. The Galois configuration is shown below
The Galois configuration looks a bit like the Fibonacci configuration. The difference with the Fibonacci configuration is that the XOR functions are placed inside the shift register, instead of in the feedback loop in the Fibonacci configuration. There are some differences between the two configurations. An important difference is that in the Fibonacci configuration the signal path has (in the example) two XOR functions, which have to process the signals within a single clock pulse. This means that one has the clock frequency at such a speed that it allows for the signals to be processed by two XOR functions. The Galois configuration does not have such a limitation. The clock speed is here determined by the processing speed of a single XOR function.
3. Self-synchronizing descramblers
Fracassi and Tammaru of Bell Labs filed a patent application for a Linear Feedback Shift Register (LFSR) based scrambler with a self-synchronizing descrambler in 1965. U.S. Patent serial number 4,304,962 assigned to Bell Labs was issued in 1981. The patent discloses the standard binary scrambler in Fibonacci configuration with a corresponding self-synchronizing descrambler. The following diagram shows a binary scrambler and a corresponding descrambler in accordance with the Bell Labs patent.
One can see that the shift register in the descrambler receives a sequence without feedback. That means that a symbol in error may influence the descrambled sequence Sig_descram as long as it resides in a shift register element. However, once the error symbol has left the shift register, correct descrambling will take place again.
The above configuration has the unfortunate property that all symbols (or signals) have to be processed by the XOR functions before the shift register can accept a newly generated symbol. The above example has a fairly short shift register. One may create scramblers with a stronger pseudo-random "scrambling" capacity and less predictable, when the shift register is longer and with additional taps. The more taps, the longer it will take a signal to be processed, because every tap is associated with a XOR function.
The solution to the above problem is an LFSR in Galois configuration. The following diagram shows an LFSR scrambler in Galois configuration and a corresponding self-synchronizing descrambler. This configuration is believed to be novel and is protected by U.S. Patent 7,487,194. The disclosure shows that one can create a Galois configuration that is substantially backward compatible with a Fibonacci configuration.
One can see that the descrambler in Galois configuration has a shift register that has no feedback. This means that an error will be flushed, and the descrambler is self-synchronizing.
4. A demonstration of a working n-state scrambler/descrambler in Galois LFSR configuration
The following MS Powerpoint presentation has embedded Fibonacci and Galois LFSR based scramblers and descramblers. The following image provides a picture of such a configuration.
The presentation is zipped. Unzip the file, and enable macros for playing the program in Slide Show Mode. Please keep in mind that scramblers and descramblers that are marked are protected by U.S. Patents. You are allowed to use the presentation with the embedded programs "as is". The presentation is provided for educational purposes only. No license for implementing and/or using the protected scramblers and/or descramblers is provided or applied. Contact Ternarylogic LLC to obtain a license. You are not allowed, nor are you licensed to use, modify, copy, implement, sell or distribute any of the protected Intellectual Property disclosed herein.
5. A demonstration of a working n-state scrambler/descrambler in Fibonacci LFSR configuration
The following MS Powerpoint presentation has embedded a working Fibonacci LFSR based scrambler and descrambler. The following image provides a picture of such a configuration.
The above n-state LFSR based scrambler/descrambler in Fibonacci configuration, having at least one function not being a modulo-n adder, with n>2 is covered by US Patent 7,643,632. No permission to implement, sell or use any of the covered n-state scramblers/descramblers covered by patents is provided or implied.
You are allowed to use the presentation with the embedded programsprovided herein "as is". The presentation is provided for educational purposes only. No license for implementing and/or using the protected scramblers and/or descramblers or sequence generators is provided or implied. Contact Ternarylogic LLC to obtain a license. You are not allowed, nor are you licensed to use, modify, copy, implement, sell or distribute any of the protected Intellectual Property disclosed herein.
6. Other novel LFSR based inventions
An Escher-esque Linear Feedback Shift Register?
They are called "impossible" figures, which show drawings that appear to be physically impossible.
The Escher drawings appear to be more impossible because of the depiction of a pseudo-physical environment.
Feedback in some cases appear to represent an impossible situation. The following diagram shows a Linear Feedback Shift Register scrambler with a corresponding descrambler. (taken from US Patent Application Publication Ser. No. 20090138535.
It shows in the bottom figure that a correctly descrambled symbol is required on the output of 'ds4' to generate correctly descrambled symbols in 'sig_out'.
Yes, that is correct: you need to correctly descramble symbols to correctly descramble. An impossible figure?
Not at all. It actually works beautifully, as is demonstrated in the following Matlab/Freemat program. The delay formed by the shift register makes this work.
The LFSR (which may be binary or non-binary) in this case is in Galois configuration and is not self-synchronizing. This requires that the initial state of the shift register in the descrambler is identical to the initial state of the shift register of the scrambler.
In the following programs sc1, sc3, sc4 and ds4 are considered.
d) for the 4-state case first run the scrambler 'novscramlfsr4gala' to
Another feature of the above scrambler/descrambler is its public/private mode.
In the binary case the function sc4 can be a XOR function whereon an all zero ([0 0 0 0 ...0]) sig_key sequence is provided. This makes sc4 transparent as the output of sc4 provides the same symbols as it received from sc1. For instance it makes the inclusion of sc4 in the descrambler unnecessary.
By modifying sig_key to for instance a pseudo-noise sequence, the descrambler, if it did not apply sc4, is no longer able to correctly descramble the scrambled sequence.
The same approach can be applied in non-binary or n-state scramblers/descramblers, for instance by using as sc4 a function represented by a standard addition over GF(n).
Feel free to play with the attached programs for educational purposes only. Please keep in mind that a patent is pending on this subject.
No license to use any of the inventions assigned to
Ternarylogic LLC is provided or implied. Explicit permission in writing
by Ternarylogic LLC is required to use any of the inventions in the U.S.A.
Intellectual Property Rights
You may not implement or use the LFSR descrambler/scrambler combination as covered by US Patents7,487,194 and 7,643,632 in any circuit, software, system or computing device in the U.S.A. without a written license from Ternarylogic LLC. No license is provided or implied in this website for use of any of the inventions assigned to Ternarylogic LLC. Such a license for use of said inventions in the U.S.A. can only be provided in writing by Ternarylogic LLC.
Commercial use of all or any of the content of this site is strictly prohibited. For educational and commercial use please contact admin at ternarylogic dot ignore dot com.
A trial license or a limited license on a named basis
for educational or evaluation purposes may be provided. Such a license
will only be provided in response to a written request to Ternarylogic