DE3807596A1

DE3807596A1 - Method and arrangement for error recognition in binary data words

Info

Publication number: DE3807596A1
Application number: DE19883807596
Authority: DE
Inventors: Hans-Werner Knefel
Original assignee: Siemens AG
Current assignee: Siemens AG
Priority date: 1988-03-08
Filing date: 1988-03-08
Publication date: 1989-09-21

Abstract

The data words, which are provided with control bits which are derived by partial parity formation, are submitted on the receiving side to a pure parity check, for fast error recognition, while doing without the possibility of error correction which is given by evaluation of these control bits. This handling by groups enables all odd-numbered errors and a high percentage of even-numbered errors to be recognised.

Description

Die Erfindung betrifft ein Verfahren zur Fehlererkennung bei insbesondere in RAM-Speichersystemen von Datenverarbeitungs anlagen abgespeicherten binären Datenwörtern, denen jeweils Kontrollbits zugeordnet sind, die durch derartige Teilpari tätsbildungen entstanden sind, daß aus den beim Vergleich dieser Kontrollbits mit den bei erneuten gleichen Teilpari tätsbildungen entstehenden Kontrollbits im Falle von Bitver fälschungen der Datenwörter sich ergebenden Abweichungs mustern die verfälschten Bits erkannt und damit korrigiert werden können. Sie betrifft ferner eine Anordnung zur Durch führung dieses Verfahrens.The invention relates to a method for error detection especially in RAM memory systems for data processing attached binary data words, each of which Control bits are assigned by such partial pari factualizations have arisen that from the comparison of these control bits with the same partial pari again control bits in the case of bit ver falsifications of the data words resulting deviation pattern the corrupted bits recognized and thus corrected can be. It also relates to an arrangement for through implementation of this procedure.

Die obengenannte Datendarstellung wird auch als EDC-Codedar stellung (Error Detecting Code) bezeichnet. Die erwähnten Ab weichungsmuster werden auch Syndrome genannt.The above data representation is also called EDC code position (Error Detecting Code). The ab softening patterns are also called syndromes.

Die Fig. 1 zeigt ein Beispiel für einen solchen Zusammenhang von Datenbits und zugeordneten Kontrollbits. Wie dort ersicht lich, sind Datenwörter vorausgesetzt, die 16 Datenbits um fassen. Zu diesen Datenbits werden sechs Teilparitäten gebil det, die zu sechs Kontrollbits CX, CD, C1, C2, C4 und C8 führen. Die in den einzelnen Zeilen CX bis C8 angekreuzten Bitpositionen eines Datenworts geben dabei an, welche Bits jeweils in die Teilparitätsbildung des betreffenden Kon trollbits einbezogen sind. Aus der Figur ist ferner ersicht lich, welche Art von Parität der Teilparitätsbildung zugrunde liegt, so wird beispielsweise das Kontrollbit CX in der Weise gebildet, daß sein Binärwert die Bits 1, 2, 3, 5, 8, 9, 11 und 14 eines Datenworts auf eine geradzahlige Parität ergänzt. Das Kontrollbit C2 hingegen ergänzt die Bits 0, 1, 5, 6, 7, 11, 12 und 13 auf eine ungeradzahlige Parität usw. usw. Fig. 1 shows an example of such a connection of data bits and associated check bits. As can be seen there, data words are required that comprise 16 data bits. Six partial parities are formed for these data bits, which lead to six control bits CX, CD, C1, C2, C4 and C8. The bit positions of a data word ticked in the individual lines CX to C8 indicate which bits are included in the partial parity formation of the relevant control bit. The figure also shows what type of parity the partial parity is based on, for example the control bit CX is formed in such a way that its binary value contains bits 1, 2, 3, 5, 8, 9, 11 and 14 of a data word added to an even parity. Control bit C2, on the other hand, supplements bits 0, 1, 5, 6, 7, 11, 12 and 13 to an odd parity etc. etc.

Wenn Datenwörter mit solchen solcherart gebildeten Paritäts bits, die zusammen mit den Datenbits übertragen und abge speichert werden, geprüft und gegebenenfalls korrigiert werden sollen, werden erneut die erwähnten Teilparitäten ge bildet und die dabei entstehenden Kontrollbits mit den ur sprünglichen Kontrollbits verglichen. Aus den erwähnten Syn dromen läßt sich dann im Falle eines Einfachfehlers die ge störte Bitstelle ermitteln und durch Invertierung des Binär werts dieser Bitstelle korrigieren.If data words with such parity bits that are transmitted and stored together with the data bits saved, checked and corrected if necessary the partial parities mentioned are to be used again forms and the resulting control bits with the ur compared control bits. From the syn dromen can then in the case of a simple error the ge determine the disturbed bit position and by inverting the binary Correct the value of this bit position.

In der Praxis werden zur Durchführung einer solchen Fehler korrektur sogenannte EDC-Controller eingesetzt, das sind Bau steine, durch die die Funktionen der erneuten Bildung der Kontrollbits, des Vergleichs, der Dekodierung der dabei ent stehenden Syndrome und die Korrektur des gefundenen fehler haften Bits realisiert werden.In practice, such mistakes are made Correction so-called EDC controller used, that is construction stones through which the functions of the re-formation of the Control bits, the comparison, the decoding of the ent standing syndromes and the correction of the found error stick bits can be realized.

Es gibt Speichersysteme, bei denen zur Datensicherung zwei gleichartige Speicher vorgesehen sind, von denen jeweils einer im stand-by-Betrieb arbeitet und bei denen im Falle eines festgestellten Fehlers vom bisher ausgenutzten Speicher auf den stand-by-Speicher umgeschaltet wird. In einem solchen Falle ist es besonders wichtig, daß die Fehlererkennung schnell erfolgt, um z.B. durch Umschaltung zu verhindern, daß gefälschte Daten in das System gelangen, zu dem die gedoppelten Speicher gehören. Die vorerwähnten EDC-Controller sind wegen der genann ten Prozeduren, die sie abzuwickeln haben, in diesem Zusammen hang als Instrument zur Fehlererkennung häufig zu langsam. Hinzu kommt, daß bei der Auswertung des EDC-Codes ungeradzahlige Mehr fachfehler als korrigierbarer Einfachfehler interpretiert werden, so daß statt einer Korrektur weitere nicht erkennbare Verfälschungen zustande kommen.There are storage systems in which two are used for data backup Similar memories are provided, each of which one works in stand-by mode and with those in case a detected error from the previously used memory is switched to the stand-by memory. In one It is particularly important that the fault detection is fast to e.g. by switching to prevent fake Data enters the system to which the duplicated memory belong. The EDC controllers mentioned above are because of the procedures that they have to carry out in this context hang as a tool for error detection often too slow. In addition comes that when evaluating the EDC code odd more Technical errors interpreted as correctable single errors be, so that instead of a correction other not recognizable Falsifications occur.

Die Aufgabe der Erfindung besteht daher darin, ein Verfahren anzugeben, das unter der Voraussetzung von EDC-codierten Daten eine schnellere Fehlererkennung sowie auch eine Fehler erkennung bei sämtlichen ungeradzahligen Mehrfachfehlern ermöglicht. The object of the invention is therefore a method specify that under the condition of EDC-encoded Data a faster error detection as well as an error Detection of all odd multiple errors enables.

Erfindungsgemäß wird diese Aufgabe dadurch gelöst, daß bei einem Verfahren der eingangs genannten Art die Datenwörter und die ihnen zugeordneten Kontrollbits unter Verzicht auf die Korrekturmöglichkeit einer reinen Paritätsprüfung unterworfen werden.According to the invention this object is achieved in that a method of the type mentioned the data words and the control bits assigned to them without the Correction possibility subjected to a pure parity check will.

Der Erfindung liegt also die Erkenntnis zugrunde, daß EDC- codierte Daten die Voraussetzung dafür bieten, daß das Vorliegen ungeradzahliger Fehler und eines gewissen Teils geradzahliger Fehler durch einfache Partyprüfung entdeckt werden kann.The invention is based on the finding that EDC encoded data provide the prerequisite that the existence odd errors and some even numbers Errors can be discovered through simple party testing.

Gemäß einer weiteren Ausgestaltung der Erfindung wird unter der Voraussetzung von Teilparitätsbildungen, bei denen jedes Datenbit in die Bildung einer ungeradzahligen Anzahl von Kontrollbits einbezogen ist, die Paritätsprüfung gesondert für Gruppen durchgeführt, die aus den Datenbits und wenigstens einem Kontrollbit gebildet werden, und sich überlappen können, wobei jede Gruppe nur solche Datenbits umfaßt, die bei der Bildung einer ungeradzahligen Anzahl von Kontrollbits der Gruppe beteiligt waren, wobei ferner jedes Datenbit und Kontroll bit Mitglied einer ungeradzahligen Anzahl von Gruppen ist, und wobei bei den gruppenweisen Paritätsprüfungen auf geradzahlige oder ungeradzahlige Parität geprüft wird, je nachdem, aufgrund welcher Art von Parität das der Gruppe angehörende wenigstens ein Kontrollbit entstanden ist und im Falle mehrerer zu einer Gruppe gehörender Kontrollbits zu welcher Art von Parität diese sich aufgrund ihrer Entstehung ergänzen.According to a further embodiment of the invention, the requirement of partial parity formation, in which each Data bit in the formation of an odd number of Control bits is included, the parity check separately performed for groups consisting of the data bits and at least a control bit, and can overlap, where each group includes only those data bits that are in the Formation of an odd number of control bits of the Group were involved, with each data bit and control bit is a member of an odd number of groups, and with the group-wise parity checks for even numbers or odd parity is checked, depending on what kind of parity at least belongs to the group a control bit has arisen and in the case of several to one Group of control bits belonging to what type of parity it is complement each other because of their origin.

Zur Durchführung der Paritätsprüfung, wie sie erfindungsgemäß zur Fehlererkennung eingesetzt wird, kommen Paritätsnetzbau steine in Frage, die eine geringere Anzahl von Eingängen auf weisen, als die mit Kontrollbits versehenen zu überprüfenden Datenwörter umfassen. Es müssen daher unter Verwendung mehrerer solcher Paritätsnetzbausteine zumindest zweistufige Paritäts netzwerke gebildet werden, deren Gesamtlaufzeit unter Umständen nicht kurz genug ist. Aufgrund der obengenannten Gruppenbildung ist es möglich, Paritätsnetzwerke zu realisieren, die einstufig sind und die darüber hinaus auch einen gewissen Prozentsatz ge radzahliger Fehler zu erkennen vermögen. To carry out the parity check as it is according to the invention parity network construction is used for error detection stones in question that have a smaller number of inputs point as the check bits to be checked Include data words. It must therefore be used using several such parity network building blocks at least two-level parity networks are formed, the total duration of which may be is not short enough. Because of the group formation mentioned above it is possible to implement parity networks that are single-level are and also a certain percentage able to detect wheel-numbered errors.

Im Interesse der dadurch erzielten Laufzeitverringerung kann der Mehraufwand an Paritätsnetzwerkbausteinen hingenommen werden.In the interest of the resulting reduction in runtime the additional effort on parity network modules accepted will.

Nachstehend wird die Erfindung anhand von Ausführungsbeispielen unter Bezugnahme auf eine Zeichnung näher erläutert.The invention is described below using exemplary embodiments explained in more detail with reference to a drawing.

In der Zeichnung zeigen:The drawing shows:

Fig. 1 die schon erwähnte, die Systematik einer EDC-Codierung veranschaulichende Codetabelle. Fig. 1, the already mentioned, the systematic of an EDC coding illustrating the code table.

Fig. 2 das Ausführungsbeispiel eines Paritätsnetzwerkes zur Durchführung des erfindungsgemäßen Verfahrens. Fig. 2 shows the embodiment of a parity network for performing the method according to the invention.

Fig. 3 Codezeichentabellen zur Veranschaulichung der Gruppen bildung gemäß der weiteren Ausgestaltung des erfindungsgemäßen Verfahrens. Fig. 3 code character tables to illustrate the formation of groups according to the further embodiment of the inventive method.

Fig. 4 das Ausführungsbeispiel eines Paritätsnetzwerks zur Durchführung der vorerwähnten erfindungsgemäßen Verfahrens variante. Fig. 4 shows the embodiment of a parity network for performing the aforementioned method variant.

Fig. 5 eine Codezeichentabelle zur Veranschaulichung der Gruppenbildung gemäß der vorerwähnten Verfahrensvariante unter Zugrundelegung eines anderen Datenformats bzw. einer anderen EDC-Codierung. Fig. 5 is a code character table to illustrate the grouping in accordance with the aforementioned variant of the method on the basis of a different data format or another EDC coding.

Fig. 6 das Ausführungsbeispiel einer Schaltungsanordnung zur Durchführung der Verfahrensvariante des erfindungsgemäßen Ver fahrens bei Zugrundelegung der Verhältnisse gemäß Fig. 5. Fig. 6 shows the embodiment of a circuit arrangement for carrying out the process variant of the invention Ver driving at the conditions prevailing in FIG. 5.

Das Paritätsnetzwerk gemäß Fig. 2 besteht aus drei Paritäts netzwerksbausteinen B1, B2 und B3, die jeweils neun Eingänge aufweisen. Es dient der Überprüfung von Datenwörtern, die 16 Bits umfassen und entsprechend der Zuordnungstabelle in Fig. 1 mit sechs Kontrollbits CX, C0, C1, C2, C4 und C8 versehen sind. Die Bits 0 bis 8 eines zu überprüfenden Datenworts sind an die Eingänge des ersten Paritätsnetzwerkbausteins geführt, die Bits 13 bis 15 sowie die Kontrollbits CX bis C8 werden an die Eingänge des zweiten Bausteins B2 gelegt. Die Ausgänge dieser beiden Bausteine sowie die Bits 9 bis 12 eines zu überprüfenden Datenworts sind an Eingänge des dritten Bausteins B3 gelegt, dessen nichtausgenutzte Eingänge an Erdpotential liegen und über dessen Ausgang im Falle des Vorliegens eines ungerad zahligen Fehlers ein Alarmsignal abgegeben wird.The parity network of FIG. 2 consists of three network parity blocks B1, B2 and B3, each having nine inputs. It is used to check data words that comprise 16 bits and are provided with six control bits CX, C0, C1, C2, C4 and C8 in accordance with the assignment table in FIG. 1. Bits 0 to 8 of a data word to be checked are routed to the inputs of the first parity network module, bits 13 to 15 and control bits CX to C8 are routed to the inputs of the second module B2. The outputs of these two modules as well as bits 9 to 12 of a data word to be checked are connected to inputs of the third module B3, the unused inputs of which are connected to ground potential and via whose output an alarm signal is emitted in the event of an odd number of errors.

Da aufgrund der aus Fig. 1 ersichtlichen Art der Teilparitäts bildung die Kontrollbits immer zu einer geradzahligen Anzahl von Bits des Binärwerts 1 führen, unabhängig davon, wie die Parität beim zugehörigen Datenwort ist, sind als Paritätsnetz werksbausteine B1 bis B3 solche verwendet, die bei Vorliegen einer geraden Parität ein Signal des Binärwerts 0 abgeben mit der Folge, daß dann, wenn fehlerbedingt die Parität der Daten oder der Kontrollbits verändert wird, am Ausgang des Bausteins B3 ein Alarmsignal abgegeben wird, sofern ein Einfachfehler oder ein ungeradzahliger Mehrfachfehler vorliegt.Since, due to the type of partial parity formation shown in FIG. 1, the control bits always lead to an even number of bits of binary value 1, irrespective of how the parity of the associated data word is, the parity network modules B1 to B3 used are those which are present give an even parity signal of binary value 0 with the result that if the parity of the data or the control bits is changed due to an error, an alarm signal is output at the output of block B3 if there is a single error or an odd multiple error.

Wegen seiner Zweistufigkeit ist das Paritätsnetzwerk gemäß Fig. 2, wie angedeutet, laufzeitmäßig etwas ungünstig.Because of its two-stage structure, the parity network according to FIG. 2 is, as indicated, somewhat unfavorable in terms of runtime.

Fig. 4 zeigt nun ein anderes Paritätsnetzwerk, das demgegen über günstiger ist, da nur eine Stufe von Paritätsnetzwerks bausteinen vorliegt. Das in der zweiten Stufe dieses Netzwerks liegende ODER-Glied bedingt eine wesentlich geringere Laufzeit als ein Paritätsnetzwerksbaustein. FIG. 4 now shows another parity network, which, on the other hand, is cheaper because there is only one stage of parity network modules. The OR gate in the second stage of this network requires a significantly shorter runtime than a parity network block.

Dem Paritätsnetzwerk in Fig. 4 liegt die gemäß der vorer wähnten weiteren Ausgestaltung des erfindungsgemäßen Verfahrens vorgenommene Gruppenbildung zugrunde, die nachstehend anhand der Fig. 3 näher erläutert wird. Wie diese Figur zeigt, sind vier Paritätsgruppen gebildet. Zur Gruppe 1, siehe Fig. 3a, gehören das Kontrollbit C2 sowie die gemäß Fig. 1 aufgrund einer Teilparitätsbildung mit diesem Kontrollbit zusammenhängen den Bits 0, 1, 5, 6, 7, 11, 12 und 13. Jedes dieser Bits der Gruppe ist demnach bei der Bildung einer ungeraden Anzahl von Kontrollbits der Gruppe, nämlich bei der Bildung des einen Kon trollbits C2 beteiligt gewesen.The parity network in FIG. 4 is based on the group formation carried out in accordance with the aforementioned further embodiment of the method according to the invention, which is explained in more detail below with reference to FIG. 3. As this figure shows, four parity groups are formed. Group 1, see FIG. 3a, includes control bit C2 and bits 0, 1, 5, 6, 7, 11, 12 and 13 associated with this control bit in accordance with FIG therefore involved in the formation of an odd number of control bits of the group, namely in the formation of one control bit C2.

Die Gruppe 2, siehe Fig. 3b) umfaßt das Kontrollbit C0 sowie die Datenbits 0, 1, 2, 4, 6, 8, 10 und 12. Group 2, see FIG. 3b) comprises control bit C0 and data bits 0, 1, 2, 4, 6, 8, 10 and 12.

Auch hier handelt es sich bei den Datenbits wieder um sämtliche Bits, die bei der zum einen Kontrollbit C0 führenden Teilparitäts bildung gemäß Fig. 1 beteiligt waren.Here too, the data bits are again all the bits that were involved in the partial parity formation leading to a control bit C0 according to FIG. 1.

Wie die Fig. 3c zeigt, gehören zur dritten Gruppe die Kontroll bits C0, C2, C4 und C8, ferner bestimmte der Datenbits. Es sind dies die Datenbits 6, 9 und 12 und damit ein Teil derjenigen Bits, die bei den Teilparitätsbildungen, die zu den Kontrollbits C0, C2, C4 und C8 geführt haben, beteiligt waren. Wie man sieht, sind die Datenbits dieser Gruppe solche, die bei der Bildung von einem oder drei Kontrollbits der Gruppe (z.B. Bit 9 bei C8); Bit 6 bei C0, C2 und C4), also bei einer ungerad zahligen Anzahl von Kontrollbits beteiligt waren.As FIG. 3c shows, the third group includes the control bits C0, C2, C4 and C8, as well as certain of the data bits. These are the data bits 6, 9 and 12 and thus part of those bits that were involved in the partial parity formation that led to the control bits C0, C2, C4 and C8. As can be seen, the data bits of this group are those which are involved in the formation of one or three control bits of the group (eg bit 9 at C8); Bit 6 at C0, C2 and C4), i.e. an odd number of control bits were involved.

Die vierte Gruppe umfaßt, wie die Fig. 3d zeigt, die vier Kontrollbits CX, C0, C1 und C2 sowie die Datenbits 0, 1, 14 und 15 und damit ebenfalls solche Bits, die bei den betreffen den Teilparitätsbildungen beteiligt waren, die zu den genannten Kontrollbits geführt haben und zwar wiederum bei einer oder bei drei solcher Teilparitätsbildungen.The fourth group, as shown in FIG. 3d, comprises the four control bits CX, C0, C1 and C2 as well as the data bits 0, 1, 14 and 15 and thus also those bits which were involved in the relevant partial parity formations which correspond to the mentioned control bits, again with one or three such partial parity formations.

Aus der Fig. 1, die die Codedarstellung zeigt, die bei der Gruppenbildung gemäß Fig. 3 vorausgesetzt ist, sieht man, daß jedes Datenbit bei der Bildung einer ungeradzahligen An zahl von Kontrollbits, nämlich 3 Kontrollbits beteiligt war. Aus Fig. 3e, die das Zusammenwirken der anhand der Fig. 3a bis 3d erläuterten Gruppen veranschaulicht, ergibt sich, daß jede der Gruppen außer Datenbits wenigstens ein Kontrollbit umfaßt, daß die Gruppen der beteiligten Datenbits und Kontroll bits sich teilweise überlappen und daß jedes Datenbit und jedes Kontrollbit einer ungeradzahligen Anzahl von Gruppen, hier näm lich entweder einer Gruppe, wie z.B. das Datenbit 3 und das Kontrollbit C1 oder 3 Gruppen, wie z.B. das Datenbit 1 und das Kontrollbit C0 angehören.From Fig. 1, which shows the code representation, which is required in the formation of groups according to Fig. 3, it can be seen that each data bit was involved in the formation of an odd number of control bits, namely 3 control bits. From Fig. 3e, which illustrates the interaction of the groups explained with reference to Figs. 3a to 3d, it follows that each of the groups includes at least one control bit in addition to data bits, that the groups of data bits and control bits involved partially overlap and that each data bit and each control bit belongs to an odd number of groups, namely namely either a group such as data bit 3 and control bit C1 or 3 groups such as data bit 1 and control bit C0.

Das in Fig. 4 dargestellte Paritätsnetzwerk umfaßt entsprechend den vier Gruppen gemäß den Darstellungen in den Fig. 3a bis 3d vier Paritätsnetzwerksbausteine B1 und B4, an deren Eingänge die betreffenden Daten und Kontrollbits geführt sind, bzw. deren nichtausgenutzte Eingänge an Erdpotential gelegt sind, sowie ein ODER-Glied Od, das die Ausgänge dieser vier Bausteine zusammenfaßt und über dessen Ausgang ein Alarmsignal im Falle eines Fehlers abgegeben werden kann. Bei Bausteinen, denen nur ein Kontrollbit zugeführt wird, wie den Bausteinen B1 und B2 hängt deren Natur davon ab, aus welcher Art von Teilparitätsbildung das betreffende Kontrollbit hervorge gangen ist, bzw. welche Art von Parität durch es hergestellt wird. So prüft der Paritätsnetzwerksbaustein B1 auf gerade Parität, da das Kontrollbit C2 gemäß Fig. 1 auf ungeradzahlige Parität ergänzt und da im fehlerfreien Fall der Baustein ein Signal des Binärwerts 0 abgeben soll. Umgekehrt ist es beim Baustein B2, der auf ungeradzahlige Parität prüft, da das Kontrollbit C0 auf geradzahlige Parität ergänzt. Bei den Bau steinen B3 und B4, denen jeweils vier Kontrollbits zugeführt werden, hängt die Art der durch sie durchzuführenden Paritäts prüfung davon ab, ob aufgrund des durch die Fig. 1 gegebenen Zusammenhangs die Summe von Bits des Binärwerts 1, den diese Kontrollbits repräsentieren können, immer geradzahlig oder immer ungeradzahlig ist. Im Falle des Bausteins B3 handelt es sich demnach um einen auf geradzahlige Parität prüfenden Baustein und im Falle des Bausteins B4 um einen auf ungeradzahlige Parität prüfenden Baustein.The parity network shown in Fig. 4 comprises, according to the four groups as shown in Figs. 3a to 3d, four parity network blocks B1 and B4, at the inputs of which the relevant data and control bits are routed, or whose unused inputs are connected to ground potential, and an OR gate Od, which combines the outputs of these four components and via whose output an alarm signal can be issued in the event of an error. In the case of blocks to which only one control bit is fed, such as the blocks B1 and B2, the nature of these depends on the type of partial parity formation from which the control bit in question originated or the type of parity it produces. Thus, the parity network block B1 checks for even parity, since the control bit C2 complements odd-numbered parity in accordance with FIG. 1 and since the block is intended to emit a signal of the binary value 0 in the event of an error. The reverse is the case for block B2, which checks for odd-numbered parity, since control bit C0 supplements for even-numbered parity. In the building blocks B3 and B4, each of which four control bits are supplied, the type of parity check to be carried out by them depends on whether, based on the relationship given by FIG. 1, the sum of bits of binary value 1, which these control bits can represent , is always even or always odd. In the case of module B3, it is therefore a module that checks for even parity, and in the case of module B4 it is a module that checks for odd parity.

Das Paritätsnetzwerk gemäß Fig. 4 kann sämtliche ungeradzahlige Bitfehler erkennen, die Wahrscheinlichkeit, daß ein geradzahli ger Fehler nicht erkannt wird, beträgt 1/(2^(N-1)), wobei N=4 ist.The parity network of FIG. 4 can all odd bit errors seen, the probability that a geradzahli ger error is not detected is 1 / (2 ^(N-1)), where N = 4.

Im Ausführungsbeispiel gemäß Fig. 6 liegen ein 32-Bitcode sowie Teilparitätsbildungen und Gruppenbildungen zugrunde, wie sie der Fig. 5 zu entnehmen sind. Es sind demnach 7 Kontrollbits CX, C0, C1, C2, C4, C8 und C16 gebildet sowie eine Einteilung in drei Gruppen vorgenommen. Auch hier gilt wieder, daß jedes Bit in eine geradzahlige Anzahl von Teilparitätsbildungen bzw. Bildungen von Kontrollbits einbezogen ist, beispielsweise das Datenbit 0 in 5 Teilparitätsbildungen und das Datenbit 1 in 3 Paritätsbildungen. Es gilt ferner, daß jedes Daten- und Kontrollbit Mitglied einer ungeradzahligen Anzahl von Gruppen ist, nämlich einer Gruppe angehört, wie hier sämtliche Daten bits und die Kontrollbits CX, C1, C4, C8 und C16 oder 3 Gruppen angehört, wie die Kontrollbits 0 und C2.In the exemplary embodiment of FIG. 6 are a 32-bit code and parity part of and formation of groups based on how they are taken from the Fig. 5. Accordingly, 7 control bits CX, C0, C1, C2, C4, C8 and C16 are formed and a division into three groups is made. Here, too, it applies again that each bit is included in an even number of partial parity formations or formations of control bits, for example data bit 0 in 5 partial parity formations and data bit 1 in 3 parity formations. It also applies that each data and control bit is a member of an odd number of groups, namely belongs to a group, as all data bits belong here and the control bits CX, C1, C4, C8 and C16 or 3 groups, such as control bits 0 and C2.

Bei der Realisierung gemäß Fig. 6 dienen zur Paritätsprüfung der zur Gruppe 1 gehörigen Datenbits 0, 1, 14, 15, 16, 17, 30 und 31 sowie Kontrollbits CX, C0, C1, C2 und C16 die Exclusiv- Oder-Glieder EO1, EO2, EO3, der Paritätsbaustein B 1 sowie das Exclusiv-Oder-Glied EO5. Die drei ersterwähnten Exclusiv-Oder- Glieder, deren ersten beiden EO1 und EO3 die Kontrollbits C1, C16, C0 und C2 zugeführt werden und deren Ausgangssignale die Ein gangssignale des dritten Exclusiv-Oder-Gliedes EO2 bilden, wirken zusammen wie ein Paritätsbaustein für ungerade Parität. Durch Zusammenfassung dieser drei Exclusiv-Oder-Glieder und des Bausteins B 1 durch das Exclusiv-Oder-Glied EO5 ergibt sich schließlich die Wirkung eines Paritätsbausteins für ungerade Parität, der sämtliche der erwähnten Daten- und Kontrollbits der ersten Gruppe zugeführt werden.In the implementation according to FIG. 6, the exclusive-or elements EO1 are used to check the parity of the data bits 0, 1, 14, 15, 16, 17, 30 and 31 belonging to group 1 and control bits CX, C0, C1, C2 and C16. EO2, EO3, the parity block B 1 and the exclusive-or gate EO5. The first three mentioned exclusive-or gates, the first two EO1 and EO3 of which are supplied with the control bits C1, C16, C0 and C2 and whose output signals form the input signals of the third exclusive-or gate EO2, act together as a parity module for odd parity . By combining these three exclusive-or elements and the block B 1 by the exclusive-or element EO5, the effect of a parity block for odd parity results, to which all of the data and control bits mentioned in the first group are supplied.

Der Paritätsprüfung für die weitere Gruppe, der die Datenbits 3, 6, 9, 12, 19, 22, 25 und 28 sowie die Kontrollbits C0, C2, C4 und C8 angehören, dienen das schon erwähnte Exclusiv- Oder-Glied EO3, an dessen Eingänge die Kontrollbits C0 und C2 liegen, ein Exclusiv-Oder-Glied EO4, dessen einen Eingang das Ausgangssignal des Exclusiv-Oder-Gliedes EO3 und dessen anderem Eingang das Kontrollbit C8 zugeführt wird, ferner ein Paritätsbaustein B 2 für die Ermittlung geradzahliger Pari tät, dem sämtliche Datenbits der Gruppe sowie das Kontrollbit C4 zugeführt werden, sowie ein weiteres Exclusiv-Oder-Glied EO6, das die Ausgänge des Exclusiv-Oder-Gliedes EO4 und des Paritätsnetzwerksbausteins B2 zusammenfaßt. Die Exclusiv- Oder-Glieder EO3 und EO4 wirken zusammen wie ein Paritätsnetz werk für ungerade Parität zur Überprüfung der Eingangsgrößen C0, C2 und C8, die Verknüpfung der Ausgänge des Exclusiv-Oder- Gliedes EO4 und des Paritätsnetzwerksbausteins B2 durch das Exclusiv-Oder-Glied EO6 führt zur Wirkung eines Paritätsnetz werksbausteins für geradzahlige Parität, dem sämtliche Daten- und Kontrollbits der Gruppe zugeführt werden.The parity check for the further group that the data bits 3, 6, 9, 12, 19, 22, 25 and 28 as well as the control bits C0, Belong to C2, C4 and C8, serve the aforementioned Or element EO3, at whose inputs the control bits C0 and C2 lie, an exclusive-or-link EO4, one input the output signal of the exclusive-or gate EO3 and its control bit C8 is fed to another input, further a parity block B 2 for the determination of even pari act, the all data bits of the group and the control bit C4 are fed, as well as another exclusive-OR link EO6, which the outputs of the exclusive-or-element EO4 and the Parity network block B2 summarized. The exclusive Or gates EO3 and EO4 work together like a parity network odd parity calculator to check input variables C0, C2 and C8, linking the outputs of the exclusive-or Link EO4 and parity network block B2 through the Exclusive-OR element EO6 leads to the effect of a parity network factory block for even parity, to which all data and control bits are supplied to the group.

Zur Gruppe 3 gehören die Datenbits 2, 4, 5, 7, 8, 10, 11, 13, 18, 20, 21, 23, 24, 26, 27 und 29 sowie die Kontrollbits C0 und C2. Zur Paritätsprüfung dieser Bits sind ein Paritätsnetz werksbaustein B3 zur Prüfung auf geradzahlige Parität, dem die Datenbits 2, 4, 5, 7, 8, 10, 11, 13 sowie das Kontroll bit C0 zugeführt werden, ferner ein Paritätsnetzwerksbaustein B 4 für die Ermittlung ungeradzahliger Parität, dem die Daten bits 18, 20, 21, 23, 24, 26, 27, 29 sowie das Kontrollbit C2 zugeführt werden, sowie ein Exclusiv-Oder-Glied E07 vorgesehen, das die Ausgänge dieser beiden Bausteine zusammenfaßt. Die drei Bausteine wirken insgesamt wie ein Paritätsnetzwerk zur Ermitt lung geradzahliger Parität unter Berücksichtigung sämtlicher Bits der Gruppe.Group 3 includes data bits 2, 4, 5, 7, 8, 10, 11, 13, 18, 20, 21, 23, 24, 26, 27 and 29 as well as the control bits C0 and C2. A parity network is used to check the parity of these bits plant module B3 for checking for even parity, the the data bits 2, 4, 5, 7, 8, 10, 11, 13 and the control bit C0 are supplied, also a parity network block B 4 for the determination of odd parity to which the data bits 18, 20, 21, 23, 24, 26, 27, 29 and control bit C2 be supplied, as well as an exclusive-or-link E07 provided, that combines the outputs of these two components. The three All in all, blocks act like a parity network for identifying even parity taking into account all Bits of the group.

Die Ausgänge der Exclusiv-Oder-Glieder EO5, EO6 und EO7 sind durch ein Oder-Glied Od zusammengefaßt, über dessen Ausgang ein Alarmsignal im Falle eines Codefehlers abgegeben wird.The outputs of the exclusive-OR elements EO5, EO6 and EO7 are summarized by an OR gate Od, over the exit an alarm signal is given in the event of a code error.

Das in Fig. 6 dargestellte Paritätsnetzwerk ist in der Lage, alle ungeradzahligen Fehler zu erkennen und darüber hinaus 75% der geradzahligen Mehrfachfehler.The parity network shown in FIG. 6 is able to recognize all odd errors and also 75% of the even multiple errors.

Claims

1. Method for error detection in binary data words stored in particular in RAM memory systems of data processing systems, to which control bits are assigned in each case, which have arisen as a result of partial parity formation such that the control bits are formed in the comparison of these control bits with the partial parity formations which are the same again In the event of bit falsifications of the data words resulting deviation patterns, the falsified bits can be recognized and thus corrected, characterized in that the data words (bits 0 to 15 or bits 0 to 31) and the control bits assigned to them (CX, C0, C1, C2 , C4, C8; C16) are subjected to a pure parity check without the possibility of correction.

2. The method according to claim 1, provided that Partial parity formations, in which each data bit in the formation an odd number of control bits is included, characterized, that the parity check is carried out separately for groups consisting of the data bits (0 to 15; 0 to 31 and at least one control bit (CX, C0, C1, C2, C4, C8; C16) are formed and overlap can, with each group comprising only those data bits that at the formation of an odd number of control bits of the Group were involved, with each data bit and control bit is a member of an odd number of groups, and with the group-wise parity checks for even numbers or odd parity is checked, depending on what kind of parity at least belongs to the group a control bit has arisen and in the case of several to one Group of control bits belonging to what kind of parity it is complement each other because of their origin.

3. The method according to claim 2, characterized, that the groups are so large that those involved in the implementation of the Parity network building blocks (B1 to B4) as many of the inputs as possible have been used.

4. Circuit arrangement for performing the method according to one of claims 2 or 3, characterized, that it per group of data and control bits (0 to 15; 0 to 31, CX to C16) at least one, optionally several Component network (EO, B) has extensive parity network, and that the outputs of the parity networks by an OR gate (Od) are summarized for issuing an error alarm.