LFSR based scramblers
and descramblers
© 2013 Peter Lablans, all rights reserved
Please note that USA patent protected
Intellectual Property is contained within this document.
Introduction
Linear Feedback Shift Registers (LFSRs) in binary form are the workhorse
circuits in present day electronic appliances and systems. While relatively
unknown to the general public, LFSRs appear in virtually any communication
and storage device. They play a critical role in generating sequences,
error-correction and error detection and in scrambling and descrambling
applications. You may find them in mobile phones, CD and DVD players,
modems and almost any coding application.
The LFSR may come in two basic configurations:
1. The Fibonacci configuration is shown below
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.
The relationship between A, B and C may be provided in an expression (A
XOR B) = C. Another and more commonly used way is to provide a truth table
of the XOR function. This truth table is provided below.
The inputs A and B can each assume one of two states: 0 or 1. For each
combination of A and B the AND function will generate a state for C. The
state of C is shown under the horizontal line and right to the vertical
line in the truth table. One can see for instance that for A=1 and
B=1 that C=0. The values above the horizontal line and left
of the vertical line only serve as a reference to the input states.
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.
To Run:
a) Open the zip files and store '.m' files in a directory which is in
the path of Matlab or Freemat.
b) for the binary case first run the scrambler 'novscramlfsrbingala' to
scramble and
'novdscramlfsrbingala' to descramble. Modify programs with Freemat/Matlab
editor for instance in initial state of the shift register.
c) compare input sequence 'sin1' with scrambled sequence 'outb' and descrambled
sequence 'res1'.
d) for the 4-state case first run the scrambler 'novscramlfsr4gala' to
scramble and
'novdscramlfsr4gala' to descramble. Modify programs with Freemat/Matlab
editor for instance in initial state of the shift register.
e) compare input sequence 'sin4' with scrambled sequence 'out4' and descrambled
sequence 'res4'.
Public/Private Mode
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).
Examples
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.
©2013, Peter Lablans. All rights reserved.
Intellectual Property Rights
You may use text and drawings of this site for private or educational
use only. You may use the figure and slides of the LFSR descrambler/scrambler
in Galois or in Fibonacci configuration provided you include the marking
of patent rights. A drawing of a descrambler is not a descrambler. However
copyright applies. If you use any text or drawing of this site's content
you have to acknowledge each page or occurrence with: Source:Ternarylogic
LLC, author Peter Lablans. You will have to get permission in
writing to include any of the drawings or text of this site in any written,
printed, paper or electronic document intended for distribution.
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
LLC.
Further information on Ternarylogic LLC and its portfolio can be found
at www.ternarylogic.com/portfolio.pdf
[TOP]
