DE2262002A1 - PROCEDURE FOR CHECKING LOGICAL OPERATIONS BASED ON A PARITY CHECK - Google Patents

Description

Applicant: IBM Deutschland GmbH

Pascalstrasse 100 7000 Stuttgart 80

Official file number: New registration File number of the applicant: GE 972 028

Method for checking logical operations on the basis of a parity check

The invention relates to a method for checking logical and arithmetic, in particular, to be carried out in a computer Operations in which the operands are binary words with several bit positions, each with a supplementary parity bit position are present and the operands are subjected to the respective operation bit-by-bit =

When developing powerful computers, the Possibility of error checking, i.e. error detection and / or error correction, has always been of great importance. The most widely used error checking method consists in the relatively simple, cheap and fast so-? called parity check. The binary represented data to be processed in the computer is each supplemented by a so-called Parity bit added so that the modulo 2 sum of all digits of the data word represented as a binary number Is 0 (or 1). In other words, the parity bit, for example, always makes the "1" digits in a binary word one even or odd number added «This parity bit is usually added directly to the data word to be saved, to ~

409826/0518

sairmen stored with him and with each data transfer moved along. After every data movement, a simple parity check can be used to determine whether in the meantime a bit position of the data word has been corrupted.

In a computer, data words are now not only stored and moved, but also to carry out logical and arithmetic operations also linked with other data words. Except for a few special basic arithmetic operations in this case, however, can no longer divide the parity bits of the operands in the same way as the data bit parts be subjected to the particular logical operation concerned with the aim, in this way equal to the parity bit for the "new" data word representing the link result. The following example is given:

= A + A. 1 O 1 O P. (A) + P (B) O i. Ggs. to P. (C) O = A. B. 1 1 O 1 P. (B) . P. (B) 1 i. Ggs. to P. (D) 1 C. B. 1 1 1 1 P. (A) 1 D. B. 1 O O O P. (A) O

A and B represent the operands consisting of four bit positions (Data words). With P (A) or P (B), the parity bits supplement the operands to an even number of "1" places designated. C is the link result calculated bit by bit in the case of an OR link. It can be seen that the Incorrect parity for the result word calculated from the parity bits of the operands using the same logical OR function is. The applicable parity is given for comparison with P (C). Correspondingly, the bottom line shows the Case of a logical AND operation of A and B.

From the above example it follows that the parity for the (new) result words is recalculated in each case

GE 972 028 40 9826/0518

must and this binary word only makes sense until its next logical connection can be assigned. However, this means that the and Easily testable connection data word parity interrupted precisely at the error-prone points of a logical link. Since, following a nontrivial logical operation, the parity of the result word is recalculated in each case becomes, the disadvantageous situation arises that the check is based on correct execution of the logical operation the simple parity check is no longer possible.

On the other hand, efforts are made to include such logical and arithmetic operations in the computer To make it error-verifiable, see e.g. the article by Rao "Error Correction in Adders Using Systematic Subcodes" in IEEE Trans. C-21, No. 3, March 1972, pages 254-259 with others Clues. After that it seems that this task can be partly (mostly only for arithmetic operations) can solve by using special verification codes; however, the solutions that have become known are in comparison for parity check incomparably more complex and require complicated check codes.

The present invention also assumes that in the conventional Arithmetic units (usually called ALU = Arithmetic and Logical Unit) are the circuits for implementing several logical units Links, e.g. for the OR, AND and XOR (equal to EXCLUSIVE OR) -Functions with two operands are usually provided at the same time. For the operation required in each individual case an associated gate control for outputting the result word is then only activated. Other arithmetic units are for the calculation of the NOR, NAND and XOR functions. It should be noted that the XOR function may be off the simultaneously available OR, AND or NOR, NAND functions can be derived, so that an error in the XOR operation always together with a mistake in one of the others

GE 972 028 409826/06 18

Shortcuts shows up. With the ones provided in the respective calculator Functions are then all other links occurring in the system through a corresponding combination of these Basic links can be represented.

The object of the invention is to provide a new one Test method that allows the testing of logical operations in particular and without additional and complicated ones Check codes comes from. The test procedure should be based on the conventional parity check and a have comparable simplicity and speed.

Based on a method for testing logical and arithmetic operations in which the operands are considered several Binary words with bit positions, each with a supplementary parity bit position, and the operands for each bit position are subjected to the respective operation, the invention is characterized in that the operands are in addition to the required Linking are subjected to at least one further linking operation which is determined in that the at least two combination results obtained in this way with the respective XOR operation of their corresponding bit positions result in a logical constant that the parity bits attached to the operands at least one of the logic operations are subjected and / or the associated parity bit is recalculated for at least one of the link results, and that the XOR operation via at least one modified "parity bit" obtained from the parity bits of the operands and / or via at least one to the link results newly calculated parity bit is checked for the presence of a predetermined logical constancy. More beneficial Refinements of the invention are characterized in the subclaims. In particular, it should be emphasized that according to a preferred development of the invention with combined vertical and horizontal testing in addition to testing the logical Operations, the origin of the data can also be checked.

GE 972 028 409826/0518

w C _

The invention is illustrated below with reference to embodiments and Application examples explained in more detail with the aid of the drawings.

In Fig. 1, the two operands A and B are shown, the OR operation of which is required, for example. The operands A and B are in binary form; their respective data bit parts are with a. or b. denotes, with e.g. eight Operands i = O, 1, ... 7 comprising bit positions. Everyone Operand A or B is supplemented in the ninth bit position by a parity bit PA or PB. In the following examples an "odd parity" is used in each case, i.e. the parity bit supplements the "1" digits of the data word to a total of odd Number. The parity bit A results, for example, as follows:

PA = 1 V a _Q V a _x V a ₂ .,. V a _?

The character V means an EXCLUSIVE-OR link (hereinafter referred to as XOR). The odd parity PB results in a corresponding manner.

The operands A and B to be subjected to the logical operation are fed to an arithmetic unit with their parity bits, in to which the operands are subjected to the desired OR function for each bit position and also to the AND and XOR function. The result words are Ω for the OR function, α for the ÜND function and X for the XOR function.

in the individual applies: . ω_) with (O ₁ = ^a i ^{+ b} i (i = 0, 1/ ·. 7) Ω = A + B = . α-) with ^α χ. ⁼ a. * ^b i (i = O, I / .. 7) α = A. B = . X ₇ ) with ^X i - ^a i V b. (i = O, 1/ ·. 7) X = AVB = ■ (ω _ο ; Cu ₁ ; .. - (o _o , O ₁ ; .. - (x _o ; X ₁ ; ..

It should be noted that performing these three functions does not mean any increased effort, even if only ultimately

GE 972 028 40 9826/0518

the result is required for the OR function. Rather, the arithmetic units customary today usually form the input operands at the same time the different operation results provided in the calculated value, although so far the Linking results that are not required (here α and X) are suppressed by output gate circuits. Finally were So-called logical memories (CLIM = Cellular Logic-In-Memory) have also already been proposed, which are different when read out provide logical links to the storage data, see e.g. IEEE Transactions on Computers, Vol. C-I8, Kr. 8, August 1969, pages 719-727. The one used in this example Function triple of AND, OR and XOR functions represents a typical set of functions from which all the others special functions required in the computer can be formed by combination. In the context of the invention, it is essential that the values ω., α. and X (i = O, 1, 2, ..) at the same time are available and this function triple XORed with each other results in a logical constant according to the relationship:

ω ₁ VQ ₁ VX ₁ = O

However, this property also has other function groups, such as NOR, NAND and XOR. A more detailed compilation of those in F:
given.

the relevant function / is in the table according to FIG. 3

While in the known method for performing logical operations at the input of the arithmetic unit, the respective parity bits are separated from the operands and only the operands themselves are linked bit by bit, in the present invention the parity bits PA and PB are also the OR, AND and XOR -Linking in the arithmetic unit. In addition to the ω, α and values, Qie modified "parity bits" 0.Ω, Qa and QX are available at the same time at the output. The following applies:

GE 972 028 409826/0518

_ "7 mm.

ΟΩ = PA + PB

Qa * PA. PB.

QX = PA V PB

Furthermore, as can be seen from FIG. 1, the respectively applicable results for the combination results Ω, α and X become "new" odd parities ΡΩ, Pa and PX are calculated according to the following relationships:

P Ω = 1 νω
ο νω ₁ . . . V (D ₇ Pa = 1 ^Va o Va ₁ ... Va ₇ PX = 1 ^VX or similar VX ₁ ... VX-

The test method according to the invention can be carried out on the basis of the values that are now simultaneously present in accordance with FIG. 1. To check for errors that may have occurred when reading out the operands or during their OR, AND or XOR operation, the relationships can be used:

ω. Va. VX. = O or

Q! L V Qa V QX = O

This "vertical test" points to the logical constancy "O" in the event of a deviating result "1" directly to a corresponding one Errors of the kind shown above. The relationships given last are because of the underlying Boolean relationship

(a + b) V (a. b) V (a V b) = O

always valid. The associated test circuit can be implemented in a simple manner with a few standard XOR gates.

The test methods described above can therefore be used

GE 972 028 409826/051 8

Check readout errors and errors in logical operations. These methods can be further advantageous Way according to the invention so that the simultaneous Checking the origin of the data is also enabled, so that an incorrectly stored bit position (memory error) can be detected with a corresponding parity error. The inventive expansion of the test method described In the form of an additional "horizontal check", such memory errors can also be checked at the same time.

It. refer again to the educational formula for PX taken. It read:

PX »1 VX _o VX ₁ ... X ₇
The following applies to QX:

QX = PA V PB = (1 V a _Q Va ₁ ... Va ₇ ) V (l V b V b .. 'V b _? ) But that can be transformed

QX = (a _Q V b _Q ) VU ₁ V b _x ) ... V (a _? V b _? )

^Ä Ä VA, ... V λ>
Ol 7

However, the relationship between PX and QX therefore applies:

PX = 1 V QX
or also PX = QX

This "horizontal" test relationship enables the test for memory errors and is particularly illustrated in FIG.

Finally, in an extremely advantageous manner combine the "vertical" and "horizontal" tests, so that a complete test for memory

GE 972 028 A09826 / 0518

and readout and link errors are present. On the other hand, it is true:

PflVPaVPX = l
By inserting

PX = 1 ¥ QX or PX = QX

the test equation according to the invention results:

PfiVPaVQX = O (1)

which is also particularly illustrated in Fig. 1 and its circuit implementation also only a few standard XOR elements demands.

The alternative test equation results in a corresponding manner :

Q Ω V Q α V PX = 1 (2)

which is illustrated in Fig. 1 in broken lines.

A comparison of equations (1) and (2) makes it clear that the test according to equation (1) in most cases is more advantageous. As for the further data processing after the logical operation anyway for the result words the new parities have to be determined, the calculation of ΡΩ and Pa does not mean any additional effort. On the other On the other hand, the application of the logical XOR operation to the operand parities PA and PB, i.e. the calculation of QX, is completely sufficient the end. 0Ω and Qa do not need to be calculated. But it is in another exemplary embodiment instead of the

GE 972 028 409826/0518

The OR function required by the example requires the XOR link, the alternative would have to be to detect link errors Equation (2) can be used. In general, it can be said that for the detection of data origin and link errors, the respective link to the desired link result associated new parity must be included in the check.

In Figs. 2a-2d are some examples of the invention Test methods shown above the line are respectively two 8-digit operands A, B with the additional parities specified. Below that are the link results for the operand bit positions, the newly calculated parities and the modified operand parities are listed. The test relationship according to the invention is framed in solid lines.

In the example of Fig. 2a is no memory, readout or Linkage errors detectable; rather, the test equation is Fulfills. The alternative test relationship framed in broken lines is also fulfilled.

In the example according to FIG. 2b, the same operand A from FIG. 2a is combined with another operand B ¹ . The bit positions that differ from B are underlined. Here, too, there is no error, as can be seen from the fulfillment of the test equation (s).

In the example according to FIG. 2c, the operand B has a memory error, the parity is correct for B (cf. FIG. 2a); the However, the second bit position of the operand B is corrupted, so that the operand B is the same as the operand B ″ of FIG. 2b the test equation yields a "1" instead of an expected one "0". It can also be seen from FIG. 2c that not all values from FIG. 1 are required. It's just the one test equation used. Finally, in Fig. 2d for the OR function of A and B in the first bit position there is a link

409826/0518

GE 972 028

error assumed, which was also recognized with the test equation will.

The proposed test method can also be used to test arithmetic operations, e.g. the adding operation will. As is well known, the following applies to the empirical formula:

where c. means the carryover from the next lower position. It is only necessary to form the odd parity PC for the transfers of all bit positions, i.e.

PC - IVc ₀ Vc ₁ ... Vc ₇

and with (PAVPB) equals QX to XORs. The odd parity for the sum word results in

PS = IVs ₀ Vs ₁ ... Vs ₇
and after appropriate reshaping

PS = (X ₀ Vx _{1 - ^ Vx 7} ) V PC = QX V PC This test equation must be fulfilled if there are no errors.

The invention described above with the aid of specific exemplary embodiments can readily be implemented in a byte-wise manner, i. E. Use data words having a plurality of bit positions as a unit, if the possible transfers are taken into account. Farther can also be selected instead of odd even parities and other function groups can be used as a basis. In the table according to Fig. 3, the possible function groups are compiled, which are used instead of the OR, AND and XOR functions used in the exemplary embodiments (column 1 in FIG. 3) can be without departing from the scope of the present invention.

GE 972 028 409826/0518

Claims (11)

PATENT CLAIMS Method for checking logical and arithmetic operations to be carried out, in particular, in a computer, in which the operands are binary words with several bit positions, each with a supplementary parity bit position are present and the operands are subjected to the respective operation bit-by-bit, characterized in that that the operands, in addition to the required link, are subjected to at least one further link operation, which is determined by that the at least two combination results obtained in this way with the respective XOR operation of their respective ones Bit positions result in a logical constant that the parity bits attached to the operands are at least be subjected to one of the linking operations and / or for at least one of the linking results associated parity bit is recalculated, and that the XOR link is via at least one of the parity bits the modified "parity bit" received from the operands and / or via at least one to the connection results newly calculated parity bit is checked for the presence of the predetermined logical constancy. 2. The method according to claim 1, characterized in that the OR-, AND- and XOR functions can be used. 3. The method according to claims 1 or 2, characterized in that that at least one vertical check on the corresponding bit positions (ω., α ,, χ.) in the respective Result words by XORing these bit position contents and checking this connection result is made to the predetermined logical constancy (Fig. 1). ge 972 028 409826/0518 4. The method according to any one of the preceding claims, characterized in that a vertical check is carried out on the parity bits recalculated for the result words (ΡΩ, Pa, PX) by XORing these parity bits and checking this combination result is made to the predetermined logical constancy (Fig. 1). 5. The method according to any one of the preceding claims, characterized in that a vertical check of the modified "parity bits ¹¹ (Qfi, Qa, QX ) is carried out by XORing these "parity bits" and checking this combination result for the predetermined logical constancy (FIG. 1). 6. The method according to any one of the preceding claims, characterized in that a horizontal check for the recalculated parity bit (PX) of the result word resulting from the XOR link and of the associated modified parity bits ¹¹ (QX) formed from the parity bits of the operands by XOR Linking of these parity bits (PX, QX) carried out and the link result is checked for the predetermined logical constancy (Fig. 1). 7. The method in particular according to claims 4 to 6, characterized in that one of the vertical and horizontal test composite test is made (Fig. 1). 8. The method at least according to claim 1, characterized in that the operands (A, B) one bit position Subject to AND, OR and XOR operation GE 972 028 409826/0518 be that for the operands (A, B) attached parity bits (PA, PB) at least the XOR operation to obtain a modified "parity bit" (QX) is carried out that at least for the AND and OR operations of the Operands received result _{words (Ω #} α) the respectively applicable new parity (ΡΩ, Pa) is calculated, and that the XOR operation via the two newly calculated parity bits ΡΩ and Pa and the modified parity bit QX on fulfillment of the condition ΡΩ V Pa V QX = 0
is checked. 9. The method at least according to claim 1, characterized in that the operands (A, B) are subjected to an AND, OR and XOR operation in bit positions that the parity bits (P, A) attached to the operands (A, B) at least the AND and OR operations to obtain the modified "parity bits" (Qfi, Qa) are carried out so that the applicable new parity (PX) is calculated at least for the result word (X) obtained from the XOR operation of the operands, and that the XOR link via the recalculated parity bit PX and the modified parity bits QSl and Qa on fulfillment of the condition QiI V Qa V PX = 1
is checked. 10. The method according to any one of the preceding claims, characterized in that the relevant parity bits add an odd number to the "1" bit positions of the associated binary word. GE 972 028 409826/0518 11. The method at least according to claim 1, characterized in that for testing the algebraic .Addierfunktion S ₁ = a _± V b _± V c _{i + 1} with -S ₁ -, a _± , b _± and c _{± + 1} as sum word, operand and carry bit positions for the fulfillment of the equation. PS = QX V PC is checked, with PS or PC the odd parities of the sum word or the carries of all bit positions represent and QX from the XOP linkage of all x. positions with x. = a. Vb results. GE 972 028 4 0 9 8 2 6/0518