DE19722157A1 - Multiple input shift register for check-sum calculation - Google Patents

Abstract

The shift register (M2) forms a check-sum (Z (t) ) in dependence on n times m simultaneously supplied digital input signals (x1 (t). , xnm (t) ), a number of m shift registers (R1. ,Rm) are clocked with a first period t, and their contents (z1 (t). , zm (t) ) form the check-sum. A number of n of the input signals are respectively supplied to the shift register between each pair of the m registers. The architecture of the shift register is determined through a certain equation system, which is based on a recursive calculation of the check-sum.

Description

The invention relates to a multiple input shift register (MISR), also called Multiple Input Signature Register, for Creation of a checksum.

Fig. 1 shows a conventional MISR M1 of degree m = 5. It has m = 5 registers R1 ,. . ., R5, which form a shift register clocked with a period T of a clock CLKT, additional feedback branches being present. Between two of the registers R1 ,. . .., R5 is an XOR operation (Exclusive OR, Exclusive OR) with one input each, to which one of the five digital input signals x ₁ (T) ,. . ., x ₅ (T) of the MISR can be created. For each period T, the contents of the registers form a checksum Z (T) = (z ₁ (T), ..., z ₅ (T)).

The architecture of any MISR of degree m can be described by the following equation (see Daehn et al. Aliasing errors in linear automata used as multiple-input signature analyzers, in: IBM, Journal of Research and Development, Vol. 34, no. 2/3, March / May 1990, pp. 363ff.):

Z (T) = C.Z (T-1) ⊕ X (T-1).

C is a square coefficient matrix with the edge length m (so-called "next-state matrix"). For the example of the conventional MISR in Fig. 1, this equation is

In order to be able to check the functionality of integrated circuits on-chip, they are provided with an MISR. Digital output signals of the circuit to be checked are supplied to the MISR in every period T as its input signals. After k periods T in a conventional MISR of degree m with one input per register, the probability P _alias that incorrect input signals lead to the same checksum Z (T) as correct input signals

P _alias = (2 ^km -1) / (2 ^k -1),

how easy it is to derive. In practice one chooses k »m, so that approximately applies

P _alias = 2 ^-m .

For a sufficiently low probability P _alias for the non-detection of occurring errors of 1 ppm, the conventional MISR must therefore have a length of at least m = 20 registers. Since MISRs with one input per register (hereinafter referred to as "conventional MISRs") require more registers with more than 20 input signals, an unnecessarily low probability P _{alias is} achieved in these cases. At the same time, the space requirements of the MISR increase due to the additional registers.

For a larger number of input signals at a MISR It is possible to do this with a specified number of registers possible, XOR operations with more than one input between two of the registers. For this lets yourself a probability of occurrence more identical Checksums for different input signals however, determine only with great effort.

The invention is therefore based on the object of an MISR specify which has a larger number of inputs than  Has registers and in which the probability of Occurrence of "correct" checksums with wrong ones Input signals can be determined in a simple manner.

The object is achieved by an MISR according to claim 1. Further developments and refinements of the invention are in the Subclaims marked.

Accordingly, a MISR is used to form a checksum Z (t) as a function of n × m digital input signals x ₁ (t), which can be applied simultaneously to corresponding inputs. . ., x _nm (t) is provided,

• - Shift registers clocked with m <1 with a period t, the contents of which z ₁ (t) ,. . ., z _m (t) in the period t form the checksum Z (t) = (z ₁ (t),..., z _m (t)),
• - in which n = 2 ^a , a ≧ 1 of the inputs of the MISR are arranged between every two of the m registers,
• - whose architecture is determined by a system of equations, which is determined by a-fold recursive insertion of Z (ti), i = 1, 2 ,. . ., a, in the system of equations
  Z (t) = CZ (t-1) ⊕X (t-1)
  is formed
  • - where each vector X (ti) = (x _k (t-1), ..., x _{k + m} (t-1)), k = 1 ,. . ., n, of the input signals x ₁ (t), which can be applied to each m of the n × m inputs. . ., x _nm (t),
  • - where after the a recursions Z (ta) is replaced by Z (t-1),
  • - in which
    Z (T) = CZ (T-1) ⊕X (T-1)
    the architecture of a conventional MISR describes shift registers clocked with a period T,
    • in which at most one input is arranged between every two of the registers, so that at the same time a maximum of m input signals X (T) = (x ₁ (T),..., x _m (T)) can be applied to the MISR,
    • - where the content z ₁ (T) ,. . ., z _m (T) of the registers at time T form a checksum Z (T) = (z ₁ (T),..., z _m (T)),
    and for which C is a coefficient matrix of dimension m × m.

The invention offers the advantage that in the MISR according to the invention the same probability P _alias applies to the correctness of the checksum Z (T) even in the case of incorrect input signals as in a conventional MISR with only one input per register, whose next-state matrix C for determining the the equation describing MISR according to the invention is used. The proof of this is given below using the exemplary embodiment in FIG. 2.

The invention thus enables the construction of a MISR with more than one input per register, for which the probability P _alias can be specified without difficulty. This is because, as already mentioned, the probability P _alias can be determined in a simple manner for conventional MISR.

According to a development of the invention, it is provided that with the MISR, two of the registers each via an XOR link are connected to each other, the maximum of n inputs which are the inputs of the MISR.

According to another embodiment of the invention MISR for those input signals x (t) in each Period t low or high in each period t Have levels, no input of the corresponding XOR link intended. There are then fewer than n inputs per register of the MISR available for the n × m input signals.

The invention is based on a Embodiment explained in more detail. Show it:

Fig. 1, a conventional MISR after the above-described prior art,

Fig. 2 shows a first embodiment of a modern fiction, MISRs,

Fig. 3 shows a modification of the MISR of Fig. 1 with a multiplexer and

Fig. 4 shows a second embodiment according to the inven tion.

Fig. 2 shows an inventive MISR M2 of degree m = 5, which m = 5, with a period of a clock CLK t t clocked shift register R1 ,. . ., R5, whose contents z ₁ (t) ,. . ., z ₅ (t) in the period t form a checksum Z (t) = (z ₁ (t),..., z ₅ (t)). The MISR M2 has ten inputs for applying ten corresponding digital input signals x ₁ (t) ,. . ., x ₁₀ (t) on.

The architecture of the MISR M2 in FIG. 2 is determined by a system of equations, which is achieved by recursively inserting Z (T-1) into the system of equations

Z (T) = CZ (T-1) ⊕X (T-1) (1)

of the conventional MISR Ml from FIG. 1 is formed, in which between the two registers R1,. . ., R5 an input is arranged. The result of the recursion is:

Z (T) = C. (C.Z (T-2) ⊕X (T-2)) ⊕X (T-1).

By inserting

X (T-2) = Y (t-1) = (x ₁ (t-1), ..., x ₅ (t-1))
X (T-1) = X (t-1) = (x ₆ (t-1), ..., x ₁₀ (t-1))
Z (T) = Z (t) and
Z (T-2) = Z (t-1)

follows from this
Z (t) = C. (CZ (t-1) ⊕Y (t-1)) ⊕X (t-1) (2)
⇒ Z (t) = (CCZ (t-1)) ⊕ (CY (t-1)) ⊕X (t-1).

In this exemplary embodiment, the conventional MISR M1 from FIG. 1 is assumed. With the associated next-state matrix C (see equation (1)), this results for the MISR M2 according to the invention in FIG. 2

This equation gives the architecture of the MISR M2 of FIG. 2. They are obtained with just a few forming steps, using the next-state matrix C of a conventional MISR M1.

The invention offers the advantage that the same probability P _alias applies for the checksum Z (T) of the MISR M2 according to the invention as for the conventional MISR M1, whose next-state matrix C is used. This is because in both cases the same checksum also results if, in the MISR according to the invention, the input signals which are supplied to the conventional MISR M1 in two successive periods are applied simultaneously during each period t.

To prove this, Fig. 3 is considered, which shows the conventional union MISR M1 from Fig. 1 with one of its inputs upstream multiplexer MUX. By means of the multiplexer half as fast as the MISR M1 clocked multiplexer MUX, it is possible to consecutively n = S different input signals x ₁ (T), in two successive periods T. . ., x ₅ (T); x ₆ (T) ,. . ., x ₁₀ (T) to feed the MISR M1. . For the circuit of Figure 3 therefore applies for two successive clock periods T, T + 1:

Z (T + 1) = C. (CZ (T-1) ⊕X (T-1)) ⊕X (T)
⇒Z (T + 1) = ((CC) .Z (T-1) ⊕ (CX (T-1))) ⊕X (T)

The checksum Z (T) for the circuit in FIG. 3 is thus formed by recursion in the same way as the checksum Z (t) in the MISR M2 according to the invention from FIG. 2, without the above-mentioned substitutions being carried out. It is obvious that the probability P _{alias is} not affected, so that it agrees in both cases. In the invention, no multiplexer is necessary due to the substitutions made when performing the recursion, and it is possible to supply twice the number of input signals during the same clock period t to the MISR M2 according to the invention as the conventional MISR M1.

The MISR M2 according to the invention thus comes with either half as much many registers R1 ,. . ., Rm from the conventional MISR M1 or can be half as fast with the same number of registers are clocked to the same number of input signals to process.

FIG. 4 shows a second exemplary embodiment of the invention, which differs from that in FIG. 2 only in that two of the registers R1,. . ., R5 less than n = 2 inputs are assigned. The corresponding input signals have a high or low level for all periods T. In the present case, the following applies to all periods t (cf. FIG. 2): x ₉ (t) = 1, x ₁₀ (t) = 0.

It is emphasized that in this exemplary embodiment the conventional MISR M1 in FIG. 1 is assumed. However, it is of course possible to use the next-state matrix C of other conventional MISR. It is possible to freely select the number of registers and the type of feedback. Both only affect the next-state matrix C.

Furthermore, it is possible to include at least one in equation (2) use it recursively again in an analog way. Man he then holds the equation for a four in MISR output signals per register. One occurs with each recursion Doubling the number of inputs per register.

Claims (4)

1. Multiple input shift register (M2) to form a checksum Z (t) as a function of n × m simultaneously supplied digital input signals x ₁ (t). . ., x _nm (t),

• - With m <1 shift registers (R ₁ ,..., R _m ), which are clocked with a period t and whose contents z ₁ (t) ,. . ., z _m (t) in the period t form the checksum Z (t) = (z ₁ (t),..., z _m (t)),
• - between the two of the m registers (R ₁ ,..., R _m ) n = 2 ^a , a ≧ 1, the input signals x ₁ (t) ,. . ., x _nm (t) are supplied,
• - The architecture of which is determined by a system of equations, which by a-fold recursive insertion of the checksums Z (ti), i = 1, 2 ,. . ., a, in the system of equations
  Z (t) = CZ (t-1) ⊕X (t-1)
  is formed
• - being after performing the a recursions
  • - each X (ti) by X (t-1) = (x _k (t-1), ..., x ₁ (t-1)) with each m of the n × m input signals x ₁ (t), . . ., x _nm (t) is replaced
  • - and Z (ta) is replaced by Z (t-1),
• - in which
  Z (T) = CZ (T-1) ⊕X (T-1)
  the architecture of a multiple input shift register (M1) describes with m shift registers clocked with a period T,
  • in which at most one input signal is fed between every two of the registers, so that at the same time at most m input signals X (T) = (x ₁ (T),..., x _m (T)) are fed to it,
  • - where the content z ₁ (T) ,. . ., z _m (T) of the registers at time T form a checksum Z (T) = (z ₁ (T),..., z _m (T)),
• - and for which C is a coefficient matrix of dimension m × m.

2. Multiple input shift register according to claim 1, in which two of the registers are connected to one another via an XOR link, the input signals x ₁ (t). . ., x _nm (t) inputs of the XOR links are supplied. 3. Multiple input shift register according to claim 2, where for those input signals x (t) that in each Period t low or high in each period t Have levels, no input of the corresponding XOR link is provided. 4. Multiple input shift register according to one of the preceding claims,

• in which the number of recursions is a = 1, so that the number of input signals between two of the registers (R ₁ ,..., R _m ) is n = 2,
• - and its architecture is determined by
  Z (t) = C. (CZ (t-1) ⊕Y (t-1)) ⊕X (t-1),
  • - wherein Y (t), X (t) are vectors which each contain m of the 2 m input signals that can be applied to the inputs at time t.