Shift register

In data-processing electronics and , a shift register is a register of fixed size in which the bits are shifted with each blow of clock (in the case of a synchronous system on the clock).

A shift register in general consists of a chaining of rockers synchronized on the clock, the exit of a rocker being connected to the entry of the following one. It is declined in several alternatives:

• SIPO ( Serial In - Parallel Out )

• SISO ( Serial In - Serial Out )
• PISO ( Parallel In - Serial Out )
• PIPO ( Parallel In - Parallel Out )

The entries or exits in parallel make it possible to insert and recover several bits at the same time. Let us take example of information of 4 bits (ex: 1001).

• Parallèle refers to 4 wire which return each one a bit. Therefore, the first wire reference " 1" at the same time as the second reference " 0" thus of suite.à
• Série to 1 wire refers which sending " 1" follow-up of " 0" and of " 0" and finally of " 1". The system series thus takes less wire but more time.

Also let us announce the existence of reversible shift registers, càd. registers where the shift is carried out towards the right-hand side or the left according to the logical level applied to the entry " Direction of décalage".

Examples of applications

• SISO : The information which one wants to introduce into the register is presented to the entry of the first rocker. At the time of a clock pulse, the bit of information is introduced into the register, and all the other bits are shifted. The bit which was memorized in the last rocker is lost if it is not stored or is not reintegrated in the structure in an unspecified way. Registers SISO are used to carry out numerical delay lines. The time between the entry of information in the register and its exit depends on the number of rockers and the frequency of clock.

• PIPO : Into shifting all the bits of a binary number towards the right-hand side or the left, one divides or one multiplies the number by 2. A register PIPO can thus be used to carry out calculations (multiplication or division by a power of 2). It is enough to operate the adequate number of shifts towards the left or the right-hand side between the moment when one introduces the bits into the register and the moment when they are recovered.

• PISO and SIPO: These two types of registers are used in the connections series; they form the base of UART and of the Modem S. Imaginons that one wants to transmit information between two distant computers of a few meters or tens of meters. To transmit information in form " parallèle" would require at least 9 wire (8 for the 8 bits, for the mass), without counting additional wire for the dialog between the computers. It is simpler to employ a register PISO to send the bits constituting each byte than one wishes to transmit in a succession of 8 bits appearing one after the other on only one line. At the end of the line, a register SIPO receives the bits which arrive at the tail-leu-leu and reconstitutes bytes which are transmitted to the computer of destination.

• reversible Registers SISO: They make it possible for example to carry out what one calls of piles LIFO ( Last In, First Out ): one charges the bits in the register; then the direction of the shift is reversed. The bits appear at the exit of the first rocker in the inverse order of their entry.

Shift register with linear feedback

It is about an alternative with a logical or arithmetic unit ( Linear Feedback Shift Register or LFSR in English). The bit (S) at exit of the register undergo a series of operations and transformations to be reintegrated in the register. This type of register is used in Cryptographie for the material implementations of certain algorithms of Chiffrement of flood. One also finds them in certain microprocessors dedicated to the signal processing (DSP), in particular for filtering. This type of circuit is also used at the time of the phase of test of the integrated circuits by allowing the automatic generation of entries (vectors of tests).

Mathematical description

Representation by the continuations

Continuations of bits being able to be produced by a shift register with linear feedback are simple to describe mathematically: they are them linear recurring continuations. In other words, one can obtain the term $t+n~$ starting from the $t\; terms,\dots ,\; t+n-1~$ by an equation linear of the type

$u\_\; \{t+n\}\; =\; \backslash \; alpha\_n\; u\_\; \{T\}\; +\; \backslash \; alpha\_\; \{n-1\}\; u\_\; \{t+1\}\; +\dots \; +\; \backslash \; alpha\_\; \{1\}\; u\_\; \{t+n-1\}\; ~$

where the $\backslash \; alpha\_i~$ are worth $0$ or $1$.

Polynomial representation

It is also possible to describe them by using the formal series:

so with a continuation $U=\; (u\_i)\; ~$ one associates the series $U\; (X)\; =\; \backslash \; sum\_\; \{i=0\}\; ^\; \{\backslash \; infty\}\; u\_iX^i~$ then the equation above can be put in the following form:

$U\; (X)\; P\; (X)\; =\; T\; (X)\; ~$

where

• $T\; (X)\; =\; \backslash \; sum\_\; \{i=0\}\; ^\; \{n-1\}\; u\_iX^i$

• $P\; (X)\; =1+\; \backslash \; alpha\_1\; X+\dots \; +\; \backslash \; alpha\_n\; X^n~$

The polynomial $T~$ corresponds to the initialization of the register, whereas the Polynôme $P$, called polynomial of feedback , characterizes it register.

Periodicity

It is easy to see that a continuation produced by such a register is necessarily periodic: the number of possibility for one $n$-uplet is with more $2^n$, therefore $f:\; T\; \backslash \; mapsto\; (u\_\; \{T\},\dots ,\; u\_\; \{t+n-1\})$ is surjective, that is to say $\backslash \; exists\; t\_0,\; t\_1,\; F\; (t\_0)\; =f\; (t\_1)$. But, clearly there is $\backslash \; forall\; X,\; y$ and $i$, $f\; (X)\; =f\; (there)\; \backslash \; Rightarrow\; F\; (x+i)\; =f\; (y+i)$. While taking $i=\; \backslash \; max\; (t\_0-t\_1,\; t\_1-t\_0)$ one thus has a multiple of the period of continuation.

The maximum period is $2^n-1$ because if the $n$-uplet all to zero is reached, the continuation is necessarily constant equal to zero. One can envisage when this value reached, a requirement and sufficient being that the polynomial of feedback is primitive -- i.e is irreducible and such as, in the ring $F\_2$ of the polynomials with binary coefficients, smallest T such as this polynomial divides $X^t-1$ is $2^n\; -1$ (it is the minimal polynomial of an element of a multiplicative nature $2^n\; -1$ in the body with $2^n$ elements).

A continuation of maximum period is called m-sequence in the Anglo-Saxon terminology.

Concept of complexity linear

All $m$-uplet of bits can be generated by a LFSR. More precisely, there exists always a LFSR -- i.e a polynomial of feedback as well as an initialization -- such as the $m$ first exits of this LFSR correspond to the $m$-uplet. In the worst of the cases one takes a register length $m$, the important polynomial of feedback little under these conditions.

This gives place to the definition of the linear complexity of a continuation (finished) like the minimal length of a LFSR generated this continuation. As the remark proves it above this complexity is limited supérieurement by the length of the continuation.

This concept intervenes in particular in cryptography because of the existence of the algorithm of Berlekamp-Massey.

Shift register and cryptography

Generation of pseudo-random

Fundamental problems in Cryptologie are the production of continuations of bits “as random as possible”. An obvious example being the generation of the keys of coding (symmetrical or asymmetrical).

This problem breaks up in fact in two parts: on the one hand the generation of bits by physical processes -- measure time between type keys on a keyboard, displacement of the mouse,… --, and in addition the expansion of a short random succession of bits in a continuation much larger. In this last case, one speaks about pseudo-random continuation . Coding by disposable Masque illustrates the stakes well. In this coding, the quantified text is produced by bit addition with bit (modulo 2) of the key of coding. The deciphering is also carried out by bit addition with bit of the key. The problem is that it is then necessary to share a secret data, namely the key, same size as the message to be exchanged. It is very often impracticable. Then the idea has just generated the key starting from a deterministic process -- it is necessary to be able to do it with coding and the deciphering -- using a smaller secret data. It is probably a little from there the origin of the Chiffrement by flood.

A first possibility consists in choosing a LFSR and using the secret data shared like initialization of the register. However, the algorithm of Berlekamp-Massey puts quickly fine at this attempt: a knowledge even very partial of the produced continuation makes it possible to find all desired information.

In practice, LFSRs are thus not used in an isolated way, but primarily in the form of the combined or filtered registers.

Algorithm of Berlekamp-Massey

A LFSR of size $n$ producing linear recurring continuations of order $n$, the knowledge of $n$ consecutive terms of a continuation and linear equation -- or in an equivalent way the polynomial of feedback -- determine all the continuation.

So now one known any more the polynomial of feedback, only can one does not suppose deduce from the observation of part of the exit of the LFSR, for example the terms $u\_\; \{t\_0\},\; u\_\; \{t\_0+1\},\dots ,\; u\_\; \{t\_0+L-1\}$? The algorithm of Berlekamp-Massey answers this question in the following way: if $L$ is higher where equal to twice the size of the smallest LFSR generating the continuation $(u\_i)$ then one can find the polynomial of feedback and the initialization of the register. In summary: touy. One thus sees appearing linear complexity like the parameter allowing to estimate the quantity of necessary information to recreate a continuation in the form of LFSR.

The algorithm of Berlekamp-Massey was introduced in 1969 by James Massey (Massey, J.L. " Shift-Register Synthesis and BCH Decoding." Trans IEEE. Information Th. 15,122-127, 1969.). It is an adaptation of an algorithm, with Elwyn Berlekamp, of decoding of correct codes -- codes of Bump-Chaudhuri-Hocquenghem.

Use

• Coding by flood in cryptology

• division by a power of two (shift towards the left or the right-hand side)
• plugs for the reception of data (FIFO: first in - first out )
• meter, timer

See too

External bonds

• shift registers with an instructive applet (dead bond?)

• Registers with linear feedback
• Shift generator

Random links:

Rioux (Charente-Maritime) | Friedrich Wilhelm Murnau | Charmoille (Doubs) | Türkisch für Anfänger | Russia-Trinity-and-Tobago in football | Pwd

© 2007-2008 speedlook.com; article text available under the terms of GFDL, from fr.wikipedia.org