Signal processing apparatus with stages in a signal path operating as LFSR of alternable type and method for processing signals

Abstract

According to the present invention, an LFSR (300) has a propagation path (30) of serially coupled stages (65) and gates (80-3, 80-4), a feedforward path (10) of gates (80-1) and a feedback path (20) of gates (80-2). Depending on control signals (P, B, M), the gates (80-1, 80-2, 80-3, 80-4) are either active gates and operate as xor-gates or passive gates and operate as transfer gates. Feedforward and feedback signals are derived from input and output signals and can be supplied to any stage (65), so that characteristic polynomials of the input-output function are variable. The LFSR can fully or partly operate as a TYPE 1 or TYPE 2 LFSR which enables the execution of different algorithms on one hardware base.

Claims

We claim:

1. A signal processing apparatus comprising:

a first path for propagating a first path signal A having components A.sub.k1, A.sub.k2, A.sub.k3 in a first direction;

a second path for propagating a second path signal R having components R.sub.k1, R.sub.k1+1 in the first direction;

a third path for propagating a third path signal L having components L.sub.k3, L.sub.k3-1 in a second, opposite, direction;

means for receiving first control signal C*.sub.1, second control signal C*.sub.2, third control signal C*.sub.3 and fourth control signal C*.sub.4 for modifying the characteristic of one or more of the first, second, and third paths;

in the first path, at least a first stage, a second stage, and a third stage, said first stage providing component A.sub.k1 to said second stage, said second stage providing component A.sub.k2 to said third stage, said third stage providing component A.sub.k3, a first logic arrangement modifying said component A.sub.k2 to A.sub.k2+1 =A.sub.k2 xor (R and C*.sub.3) xor (L and C*.sub.4);

in the second path, at least a second logic arrangement receiving component A.sub.k1 and modifying R.sub.k1 to R.sub.k1+1 =(A.sub.k1 and C*.sub.1) xor R.sub.k1 ; and

in the third path, at least a third logic arrangement receiving component A.sub.k3 and modifying L.sub.k3 to L.sub.k3-1 =(A.sub.i3 and C*.sub.2) xor L.sub.k3 ; wherein said control signals thereby activate said first and second stages to selectively operate as part of a TYPE 1 linear feedback shift register or of a TYPE 2 linear feedback shift register or both.

2. The apparatus of claim 1, wherein said first logic arrangement comprises at least a first

xor-gate, a second xor-gate, a first and-gate and a second and-gate,

said first and-gate receiving R and C.sub.3 and providing (R and C.sub.3),

said first xor-gate receiving A.sub.i * and (R and C.sub.3) and providing (A* xor (R and C.sub.3)),

said second and-gate receiving C.sub.4 and L and providing (L and C.sub.4),

said second xor-gate receiving (A* xor (R and C.sub.3)) and (L and C.sub.4) and providing A**=A* xor (R and C.sub.3) xor (L and C.sub.4).

3. The apparatus of claim 1, wherein said first logic arrangement comprises at least a least a

first xor-gate, a second xor-gate, a first and-gate and a second and-gate,

said first and-gate receiving R and C.sub.3 and providing (R and C.sub.3),

said second and-gate receiving C.sub.4 and L and providing (L and C.sub.4),

said first xor-gate receiving (R and C.sub.3) and (L and C.sub.4) and providing ((R and C.sub.3) xor (L and C.sub.4)),

said second xor-gate receiving A* and ((R and C.sub.3) xor (L and C.sub.4)) and providing A** =A* xor ((C.sub.3 and R) xor (C.sub.4 and L)).

4. The apparatus of claim 1 wherein said first, second, and third path signals are propagated in said first, second and third paths, respectively, substantially simultaneously.

5. The apparatus of claim 1 wherein said first path is selectively influenced by said first path signal R, and by said second path signal L.

6. A method for processing signals by a serial arrangement of cells k0 =1 to m with at least a first cell k1, a second cell k2, and a third cell k3, with k2.gtoreq.k1+1, k3.gtoreq.k2+1, the method comprising the steps of:

providing a first control signal C*.sub.1 to said first cell k1, a second control signal C*.sub.2 to said third cell k3, a third control signal C*.sub.3 to said second cell k2 and fourth control signal C*.sub.4 to said third cell k3 for modifying the characteristic of said first, second, and third cells;

propagating a first path signal A in a first path through the cells k1, k2 and k3 in a first direction;

propagating a second path signal R in a second path through the cells k1 and k2 in said first direction,

propagating a third path signal L in a third path through the cells k2 and k3 in a second, opposite direction.

7. The method of claim 6 wherein in said steps of propagating path signals A, R, L, cell k1 receives components A.sub.k1 and R.sub.k1 and provides components A.sub.k1+1 and R.sub.k1+1 ; cell k2 receives components A.sub.k2 and R.sub.k2 and L.sub.k2 and provides components A.sub.k2+1 and R.sub.k2+1 and L.sub.k2-1 and cell k3 receives components A.sub.k3 and L.sub.k3 and provides component L.sub.k3-1,

wherein in the step of propagating R, cell k1 modifies R.sub.k1 to R.sub.k1+1 =(A.sub.k1 /z and C*.sub.1) xor R.sub.k1, which is further propagated to R.sub.k2 ;

wherein in the step of propagating A, cell k2 modifies A.sub.k2 to A.sub.k2+1 =A.sub.k2 /z xor (R.sub.k2 and C*.sub.3) xor (L.sub.k2 and C*.sub.4) which is further propagated to A.sub.k3 ; and

wherein in the step of propagating L, cell k3 modifies Lk3 to L.sub.k3-1 =(A.sub.k3 /z and C*.sub.2) xor L.sub.k3 which is further propagated to L.sub.k2, output signals being selectively derived from any of the cells.

8. The method of claim 6 wherein said steps of propagating a second path signal R and propagating a third path signal L are performed substantially simultaneously.

9. The method of claim 6 wherein under the condition that third and fourth control signals C*.sub.3 and C.sub.4 are C*.sub.3 =C*.sub.4 ="0", a first sequence of an arrangement defined by cells k2 and k3 operates as a TYPE 2 LFSR and wherein under the condition that first and second control signals C*.sub.1 and C*.sub.2 are C*.sub.1 =C*.sub.2 ="0", said first sequence operates as a TYPE 1 LFSR.

10. The method of claim 6 wherein a first sequence of cells operates as a TYPE 1 LFSR and a second sequence of cells operates as a TYPE 2 LFSR.

11. The method of claim 6 wherein during said steps of propagating said first path signal A and propagating said second path signal R, an input signal sequence present at stage k1 is multiplied by a first characteristic polynomial function to an output signal sequence present at stage k3.

12. The method of claim 6 wherein during said steps of propagating said first path signal A and propagating said third path signal L, an input signal sequence present at stage k1 is divided by a second characteristic polynomial function to an output signal sequence present at stage k3.

Description

FIELD OF THE INVENTION

This invention relates to electronic devices, and especially to a linear feedback shift register (LFSR) as a device for processing codes and to a method used therein.

BACKGROUND OF THE INVENTION

Linear Feedback Shift Registers (LFSR) are used in digital communication and other systems for data processing such as, for example, ciphering, error detecting, error correcting, or for generating pseudo random sequences. In an LFSR, a plurality of stages is coupled for sequential propagation of signals through the stages. The signal propagation can be influenced by exclusive-or-gates (xor-gates) arranged according to characteristic polynomials of an input-output function.

The theoretical background for using LFSRs in, e.g., a message encoder, is explained in chapter 5.6. of Sklar, B.: Digital Communications, Fundamentals and Applications, Prentice Hall, Englewood Cliffs, N.J., ISBN 0-13-211939-0 [1].

LFSRs can be classified into TYPE 1 and TYPE 2. This classification has been explained U.S. Pat. No. 5,073,909 to Kotzin et. al. [2] in reference to LFSR which are used to generate random sequences. LFSRs which read input signal IN and provide output signal OUT are now explained by way of example in FIGS. 1-2. FIG. 1 shows prior art LFSR 100 of TYPE 1. LFSR 100 comprises stages 111, 112, 113, 114 and xor-gates 115 and 116. IN is supplied to xor-gate 115 and then propagated through stages 111-114. OUT is available at the output of stage 114. Signal T1, obtained from xor-gate 116 acting upon the outputs of stages 113 and 114. T1 is then fed back to the input of stage 111 through xor-gate 15. TYPE 1, as used herein, defines an LFSR wherein the various stages (e.g., 111-114) are cascaded together, input to output, without interruption by an intervening signal (e.g., T1). TYPE 1 LFSRs are commonly used to implement algorithms for, e.g., the generation of a mask set sequence for data ciphering.

FIG. 2 shows prior art LFSR 200 of TYPE 2. LFSR 200 comprises stages 221, 222, 223, 224, and xor-gates 225 and 226. IN is supplied to xor-gate 225 and then propagated through stage 221, xor-gate 226, and stages 222-224. OUT is available at the output of stage 224. Xor-gate 226 performs an exclusive-or operation on the outputs of stages 221 and 224. This operation is then used to determine the state of stage 222.

Finally, the output of stage 224 is fed back to xor-gate 225. TYPE 2, as used herein, defines an LFSR wherein the various stages (e.g., 221-224) are cascaded together, however, the shift path is interrupted by the introduction of a signal (e.g., T2). TYPE 2 LFSRs are commonly used to implement algorithms for e.g., for parity code generation, error detection and error correction.

As is used herein and only for the convenience of explanation, a first direction is defined for signals going from elements (stages or xor-gates) with low reference numbers (e.g., 111) to elements with higher reference numbers (e.g., 114). A second direction is defined in the opposite way. As shown in the figures, the first direction goes from left to right and the second direction goes from right to left. For example, in FIG. 1, IN goes in first direction to OUT, T1 goes in second direction from xor-gate 116 to xor-gate 115. T1 can therefore be considered as feedback signal. Although the term LFSR implies feeding "back" signals (e.g., T1, T2 of FIGS. 1-2), LFSRs as discussed here can also feed forward signals.

In LFSRs 100 and 200 as shown in FIGS. 1-2, the stages and xor-gates are hard wired so that the characteristic polynomials of the LFSR can not be changed. However, there are instances in circuit design where one application (e.g., a cellular phone) needs variable characteristic polynomials. Operators for phone systems may use their own proprietary polynomials for e.g., data ciphering. It is easier to market phones having similar hardware but different software than market phones having different hardware. Further, some applications require different data processing algorithms at different times. In view of hardware expenses and power consumption, it is not convenient to have separate LFSRs (TYPEs 1 and 2) for different algorithms. There is a need to design a LFSR able to provide both TYPE 1 and TYPE 2 features.

FIG. 4 of U.S. Pat. No. 5,446,683 to Mullen et. al. [1] shows an LFSR incorporating provisions for variation of the characteristic polynomial. However, the LFSR is of TYPE 1 and cannot be reconfigured to TYPE 2. The present invention seeks to provide a fully programmable LFSR with variable characteristic polynomials which is switchable between TYPE 1 and TYPE 2.

BRIEF DESCRIPTION OF THE DRAWINGS

FIG. 1 shows a simplified block diagram of a prior art linear feedback shift register (LFSR) of TYPE 1;

FIG. 2 shows a simplified block diagram of a prior art LFSR of TYPE 2;

FIG. 3 shows a simplified block diagram of an LFSR in a preferred embodiment of the present invention;

FIG. 4 shows a simplified block diagram of a cell as used in the LFSR of FIG. 3;

FIG. 5 shows a simplified block diagram of a gate as used in the cell of FIG. 4;

FIG. 6 shows simplified block diagrams of cells of FIG. 4 configured for operating the LFSR of FIG. 3 in a TYPE-1-MODE;

FIG. 7 shows simplified block diagrams of cells of FIG. 4 configured for operating the LFSR of FIG. 3 in a TYPE-2-MODE; and

FIG. 8 shows a logic arrangement as it can also be used in cell 40.

DETAILED DESCRIPTION OF A PREFERRED EMBODIMENT

The LFSR according to a preferred embodiment of the invention is illustrated by way of example in FIGS. 3-8. At first, the elements (e.g., cells, stages, gates) of the LFSR and their connections are explained in a top down view, from FIGS. 3 to 5. Second, the function of the LFSR is explained in a bottom up view, by FIGS. 5 to 3 and FIGS. 6-7. Third, it will be explained, how the LFSR can operate as LFSRs of FIGS. 1-2. FIG. 8 shows additional details.

For explanation and not intended to be limiting, signals are considered as binary signals having first and second logical states abbreviated as logical "1" and "0", respectively. In the text, signals are abbreviated by uppercase letters and acronyms (e.g., A, C, F, L, R, S, C, Y, R, PB, PF). Logical functions known in the art are given in lowercase bold italics (e.g., xor, and). The elements have arabic reference numbers (e.g., 40). Some elements (e.g., cells) and signals (e.g., of signal vectors) are, preferably, available in pluralities. A single element or signal is referenced by an index, wherein elements and signals of a plurality are collectively referred without index. For elements, indices are attached to the numbers by a hyphen (e.g., 40-i, 40-2). For signals, indices are written as subscripts (e.g., P.sub.i, PB.sub.2). Unless otherwise stated, index i can have any value between 1 and n. For convenience of explanation, a preferred embodiment of the present invention is illustrated in FIG. 4 wherein k=4, but other values are possible for other implementations. There is no need to have all elements or signals with all possible values of i or k. Optionally, elements and signals can be left out. Indices can include sums or differences (e.g., i-1, i+1). For simplicity, connections for carrying clock signals to the elements are not shown. Persons of skill in the art will understand how to provide clock signals.

FIG. 3 shows a simplified block diagram of linear feedback shift register 300 (dashed frame, hereinafter LFSR 300) in a preferred embodiment of the present invention. LFSR 300 comprises a plurality of cells 40, and optional xor-gate 70. For simplicity, in FIG. 3, only cells 40-1, 40-1, 40-i and 40-n are shown. Bus 50 at terminal 51 provides control signals to cells 40 at connections 52-1 to 52-n. Dashed connections in cells 40 illustrate a signal transfer through cells 40. As it will be explained in connection with FIGS. 4-5, cells 40 have gates which can be enabled or disabled by the control signals from bus 50 so that the signal transfer can be modified. Xor-gate 70 has inputs 71 and 72 and output 73 for relating signals by a xor-operation known in the art. Connections 30-i (i=0 to n+1) through xor-gate 70 and cells 40, preferably, couple, terminals 31 and 32. Connections 30 form thereby a propagation path for propagating data signals A.sub.i, (i=0 to n+1). Connections 10-i (i=1 to n=m+1) through cells 40, preferably, couple terminals 11 and 12 and form a feedforward path with data signals R.sub.i (i=1 to n). Connections 20-i (i=n down to 0) through cells 40, preferably, couple terminals 21 and 22 and form a feedback path with data signals L.sub.i (i=n down to 0). Arrows on connections 10, 20, 30 here and in other figures show the preferred direction of signal flow. The terms `forward` and `back` are convenient abbreviations for the above mentioned first direction (e.g., increasing i) and second direction (e.g., decreasing i), respectively, that is, for referring to opposed directions of signal propagation through the LFSR.

Having the paths implemented by connections 10, 20, 30 going over the full range of indices i, is convenient for explanation, but not necessary for the invention. Connections 10, 20, and 30 can be shorter, so that for example, terminals 11, and 12 can be coupled to connections 10-2 and 10-5, respectively. It will be explained later, how cells 40 couple connection 30 to connections 10 and 20. As shown in FIG. 3 only for convenience and not intended to be limiting, it is assumed that connection 20 is coupled to input 72 and that connection 30 is coupled to connection 20 via connection 35 going through terminals 32 and 21.

Preferably, LFSR 300 receives, e.g., A.sub.0 as input signal and sequentially propagates it in the first direction to e.g., A.sub.n+1 as an output signal. Thereby, feedforward and feedback signals (e.g., R.sub.i, L.sub.i) go through cells 40 in the first (increasing i) and second (decreasing i) directions. Output signals (e.g., R.sub.m, L.sub.1, and A.sub.n+1) can be obtained at any of connections 10, 20, or 30 having any index i. The input signal is related to the output signal by an input-output function which has variable characteristic polynomials. The input-output function is determined by a plurality of control signals in bus 50. Control signals can be e.g., polynom signals PB.sub.i, PF.sub.i (collectively P), mode signals M1, M2 (collectively M), where "F" and "B" in combination with "P" refer to forward and backward propagation directions. Polynom signals form a first polynom vector (PF with e.g., PF.sub.1 to PF.sub.m) and a second polynom vector (PB with e.g., PB.sub.1 to PB.sub.m). Sequences of LFSR 300 or the complete LFSR 300 can be switched between a TYPE-1-MODE and a TYPE-2-MODE by selectively activating and de-activating the gates in the propagation path.

FIG. 4 shows a simplified block diagram of cell 40 (dashed frame) as used in LFSR 300. Connections 10, 20 and 30 and connections 52 correspond in FIGS. 3-4. Cell 40 comprises stage 65 and gates 80-1, 80-2, 80-3, and 80-4. Stage 65 is a storage means for receiving a signal at input 66 and propagating it to output 67. Stage 65 can be implemented by, for example, a D-type flip-flop known in the art. Preferably, each gate 80 has inputs 81, 82, 83, 84 and output 86. Gate 80 is described further in connection with FIG. 5.

In the propagation path, connection 30-i is coupled to input 66. Output 67 is coupled to inputs 82-1, 82-2 and 81-3 forming connection 30*-i. Output 86-3 is coupled to input 81-4 forming connection 30**-i and output 86-4 is coupled to connection 30-(i+1). In the feedforward path, connection 10-i is coupled to input 81-1, and output 86-1 leading into connection 10-(i+1) is coupled to input 82-3. In the feedback path, connection 20-i is coupled to input 81-2 and to input 82-4. Output 86-2 leads to connection 20-(i-1). Connections 431, 432, 433 and 434 originate from connection 52 and carry control signals. Connection 431 is coupled to input 84-1 and to input 84-3. Connection 432 is coupled to input 84-2 and to input 84-4. Connection 433 is coupled to input 83-1 and to input 83-2. Connection 434 is coupled to input 83-3 and to input 83-4. As far as a logical xor-operation is commutative, gates 80-3 and 80-4 can be arranged in a different order. Gate 80-3 and 80-4 form logic arrangement 45 (dashed frame).

FIG. 5 shows a simplified block diagram of gate 80 (dashed frame) as used in cell 40 of FIG. 4. Reference numbers 81, 82, 83, 84 and 86 in FIG. 5 correspond to these of FIG. 4. Gate 80 comprises and-gate 75 and xor-gate 76. Xor-gate 76 has first data input 81. Xor-gate 76 has input 87 coupled to output 85 of and-gate 75. And-gate 75 has first control input 83, second control input 84, and second data input 82.

Gate 80 receives control signal M at input 83 and control signal P at input 84. Gate 80 receives first data signal F at input 81 and second data signal S at input 82. Gate 80 relates these signals to third data signal Y according to a logical function Y=f (M, P, S, F), as for example:

Y=(M and P and S) xor F. (1)

with `xor` standing for a logical exclusive disjunctive operation and `and` for a logical conjunctive operation. Gate 80 is in an active state ("active gate", "enabled gate") for (M and P)="1" and in a passive state ("passive gate", "disabled gate") for (M and P)="0". For convenience of explanation, control signals M and P can be combined to control signal C which is defined as:

C=M and P. (2)

Function (1) can be simplified to:

Y=(C and S) xor F. (3)

For active gate 80, equation (1) becomes:

Y=("1" and S) xor F.

Y=S xor F. (4)

For passive gate 80, equation (1) becomes:

Y=("0" and S) xor F

Y=F. (5)

Table 1 is a truth table for gate 80 showing the logical relation of control signals M, and P at inputs 83, 84 (columns 1-2), and data signals F and S at inputs 81, 82 (columns 3-4) to data signal Y at output 86 (column 5). The term "any" stands for either logical "1" or "0" states of the signals. Configurations for active gates 80 are shown in rows 1-4, when both M and P are at logical "1". Active gate 80 operates as a xor-gate (Y xor F). Configurations for passive gate 80 are shown in rows 5-8 when either M or P or both are at logical "0". Passive gate 80 behaves like a conductor (e.g., a transfer gate) transferring F to Y without changing the logical state and without influence from S. Having active and passive states, gate 80 can be considered as a conditional xor-gate.

                  TABLE 1
    ______________________________________
    Operation of gate 80
          1           2      3       4    5
            control signals
                         data signals
          M           P      F       S    Y
    ______________________________________
    1     "1"         "1"    "0"     "0"  "0"
    2     "1"         "1"    "0"     "1"  "1"
    3     "1"         "1"    "1"     "0"  "1"
    4     "1"         "1"    "1"     "1"  "0"
    5     0           any    "1"     any  "1"
    6                        "0"          "0"
    7     any         0      "1"     any  "1"
    8                        "0"          "0"
    ______________________________________

                  TABLE 2
    ______________________________________
    Operation of cells 40
    input side, index i
                   output side, index i+1 and i-1
    signals
           at      signals              at
    ______________________________________
    propagation path
    A.sub.i
           30-i    A.sub.i+1 =A.sub.i /z  30-(i+1)
                    xor (R.sub.i+1 and C.sub.3)
                    xor (L.sub.i and C.sub.4)
                                    (6)
                   (6) for C.sub.1 ="0", C.sub.2 ="0":
                    A.sub.i+1 =A.sub.i /z
                    xor (R.sub.i and C.sub.3)
                    xor (L.sub.i and C.sub.4)
                                    (7)
                   (6) for C.sub.3 ="0", C.sub.4 ="0":
                   A.sub.i+1 =A.sub.i /z
                                    (8)
    feedforward path
    R.sub.i
           10-i    R.sub.i+1 = (A.sub.i /z and C.sub.1) xor
                                    (9)ub.i
                                          10-(i-1)
    feedback path
    L.sub.i
           20-i    L.sub.i-1 = (A.sub.i /z and C.sub.2) xor
                                    (10)b.i
                                          20-(i+1)
    ______________________________________

                  TABLE 3
    ______________________________________
    Cell-configurations for TYPE-1-MODE
    configuration
                 #10      #11      #12    #13
    ______________________________________
    PF           "0"      "1"      "0"    "1"
    PB           "0"      "0"      "1"    "1"
    gate 80-1    equal    xor      equal  xor
    gate 80-2    equal    equal    xor    xor
    gate 80-3    equal    equal    equal  equal
    gate 80-4    equal    equal    equal  equal
    ______________________________________

                  TABLE 4
    ______________________________________
    Cell-configurations for TYPE-2-MODE
    configuration
                 #20      #21      #22    #23
    ______________________________________
    PF           "0"      "1"      "0"    "1"
    PB           "0"      "0"      "1"    "1"
    gate 80-1    equal    equal    equal  equal
    gate 80-2    equal    equal    equal  equal
    gate 80-3    equal    xor      equal  xor
    gate 80-4    equal    equal    xor    xor
    ______________________________________

    ______________________________________
    cell    k1     receives   A.sub.k1
                                    provides A.sub.k1+1
                   components R.sub.k1
                                    components
                                             R.sub.k1+1
            k2                A.sub.k2       A.sub.k2+1
                              R.sub.k2       R.sub.k2+2
                              L.sub.k2       L.sub.k2-1
            k3                A.sub.k3       L.sub.k3-1
                              L.sub.k3
    ______________________________________

• Inventors
  Tarrab, Moshe; Engel, Eytan; Borowitz, Eli; Belotserkovsky, Leonid;
• Assignee
  Motorola, Inc. (Schaumburg, IL)
• Published
  Aug-1-2000
• Current US Classes:
  377/72
  380/46
  712/1
• Application #
  880956
• International Classes
  G06F 015/00
• Field of Search
  380/44 380/46 381/71.1 377/72
• Examiner
  De Cady; Albert
• Agent
  Zahn; Mathas, Witek; Keith E.
• US Patent References:
  4225957
  4680539
  5073909
  5247525
  5369648
  5394405
  5446683
  5506520
  5589787
  5642362