DE1187265B

DE1187265B - Procedure for data transfer

Info

Publication number: DE1187265B
Application number: DET25299A
Authority: DE
Inventors: Dipl-Ing Horst Ohnsorge
Original assignee: Telefunken Patentverwertungs GmbH
Current assignee: Telefunken Patentverwertungs GmbH
Priority date: 1963-12-20
Filing date: 1963-12-20
Publication date: 1965-02-18

Description

Verfahren zur Datenübertragung Die Erfindung betrifft ein Verfahren zur Datenübertragung, in dem sendeseitig für jeweils einen Datenblock nach einem vereinbarten Kode eine Prüfzeichengruppe gebildet wird, die auf der Empfangsseite zur Erkennung und gegebenenfalls Korrektur von Ubertragungsfehlern ausgewertet wird.Method for data transmission The invention relates to a method for data transmission, in which on the sending side for one data block after one agreed code a group of test characters is formed on the receiving side is evaluated for the detection and, if necessary, correction of transmission errors.

Solche Systeme sind sowohl theoretisch durchleuchtet wie praktisch angewendet worden. Eine Zusammenfassung vieler bekannter Systeme ist in dem Buch von W. W. P e t e r s o n, »Error Correcting Codes«, 1961, zu finden. Die Sicherheit im Erkennen von Fehlern hängt im allgemeinen von der Redundanz ab, d. h. von dem Verhältnis der Größe der Prüfzeichengruppe zur Größe des Datenblocks. Je größer die Redundanz gewählt wird, um so besser ist zwar die Fehlersicherheit, um so geringer wird aber auch die nutzbare Ubertragungskapazität des Kanals. Außerdem steigt der Aufwand für die Prüfzeichenbildung dabei gewaltig an. Dieser Aufwand hängt weiterhin davon ab, wie groß die Prüfzeichengruppe absolut ist, d. h., bei gegebener Redundanz, wie groß ein Datenblock gewählt wird. An sich erscheint es vorteilhaft, Datenblöcke möglichst groß zu wählen, da man so systematische, in gewissen Abständen immer wiederkehrende Fehler am besten erkennt. Aus Aufwandgründen muß man aber sowohl die Redundanz als auch die Größe der Datenblöcke so weit beschränken, daß nur noch bestimmte Fehler, z. B. Einzelfehler, sicher erkannt werden. Treten in diesem Fall z. B. Doppelfehler auf, dann lassen sie sich entweder gar nicht entdecken oder aber nur, wenn sie sich in einer bestimmten Stellung im Datenblock befinden. Solche bevorzugte Stellungen sind kodeabhängig. Doppelfehler, die anderswo auftreten, bleiben also unentdeckt. Durch die Erfindung wird eine Verbesserung insoweit erzielt, als ohne wesentliche Aufwandsvergrößerung systematisch immer in derselben Stellung im Datenblock auftretende Fehler in vielen Fällen entdeckt werden können, auch wenn es Fehler sind, die an sich von dem verwendeten Kode nur in bestimmten Stellungen erkannt werden.Such systems are both theoretical and practical been applied. A summary of many known systems is in the book by W. W. P e t e r s o n, "Error Correcting Codes", 1961. The security in the detection of errors generally depends on the redundancy, i. H. of the Ratio of the size of the check character group to the size of the data block. The bigger the redundancy is selected, the better the fail-safe, the lower but also the usable transmission capacity of the channel. In addition, the The effort involved in creating the test mark is enormous. This effort still depends on how large the test character group is in absolute terms, d. i.e., given redundancy, how big a data block is chosen. In itself it appears advantageous to use data blocks To choose as large as possible, because one is so systematic, recurring at certain intervals Identifies errors best. For reasons of expense, however, both redundancy and also limit the size of the data blocks so that only certain errors z. B. individual errors, can be reliably detected. Occur in this case z. B. Double fault then they can either not be discovered at all or only when they are are in a certain position in the data block. Such preferred positions are code-dependent. Double faults that occur elsewhere therefore remain undetected. The invention achieves an improvement to the extent that it is not essential Systematic increase in effort always occurring in the same position in the data block Errors can be discovered in many cases, even if there are errors that are related to can only be recognized by the code used in certain positions.

Die Erfindung besteht darin, daß für aufeinanderfolgende Blöcke unterschiedliche Kodes verwendet werden.The invention consists in that for successive blocks different Codes are used.

Im folgenden wird die Erfindung zuerst an einem Zahlenbeispiel und anschließend an Hand eines Ausführungsbeispiels, das in der Figur dargestellt ist, im einzelnen erläutert.In the following the invention is first illustrated by a numerical example and then on the basis of an embodiment that is shown in the figure, explained in detail.

Ein einfacher Kode soll auf Blöcke von je fünf Informationsbits derart angewandt werden, daß drei Prüfbits als Prüfzeichengruppe entstehen. Der Kode ist durch eine Matrix gemäß Tabelle 1 gegeben. Entsprechend der geringen Redundanz sind mehrere Spalten dieser Matrix einander gleich, beispielsweise die erste und die fünfte. Ordnet man jedem Informationsbit eine Spalte dieser Matrix zu (also z. B. dem ersten Bit die erste Spalte usw.) und addiert vektoriell die Spalten, deren zugeordnetes Informationsbit eine Eins zeigt, so erhält man einen dreidimensionalen Prüfvektor, der als Prüfzeichengruppe dient. Man erkennt aus der Matrix, daß ein Einzelfehler des ersten Informationsbits zum selben Prüfvektor führt wie ein Einzelfehler des fünften Informationsbits, so daß ein solcher Fehler nicht eindeutig lokalisiert werden kann. Weiterhin erkennt man, daß z. B. ein Dreifachfehler in den ersten drei Informationsbits zu überhaupt keiner Fehlermeldung führt.A simple code is to be applied to blocks of five information bits each in such a way that three check bits are created as a group of check characters. The code is given by a matrix according to Table 1 . In accordance with the low redundancy, several columns of this matrix are identical to one another, for example the first and the fifth. If you assign a column of this matrix to each information bit (e.g. the first column, the first bit, etc.) and add vectorially the columns whose assigned information bit shows a one, you get a three-dimensional check vector that serves as a group of check characters. It can be seen from the matrix that an individual error in the first information bit leads to the same test vector as an individual error in the fifth information bit, so that such an error cannot be clearly localized. It can also be seen that, for. B. a triple error in the first three information bits leads to no error message at all.

Da auftretende Fehler nicht immer statistisch verteilt sind, sondern vielfach ihre Ursache in einer Fehlkalkulation der Anlage besitzen, die beliebig oft reproduzierbar ist, kann ein systematisch immer an der ersten Stelle auftretender Fehler mit der vorliegenden Matrix zwar entdeckt, aber nicht lokalisiert werden, dagegen kann man solche Fehler gemäß der Erfindung manchmal erkennen, wenn man für aufeinanderfolgende Informationsblöcke verschiedene Kodes benutzt, wobei der zweite Kode so gewählt ist, daß man gerade in den Stellen Fehler erkennen kann, für die sich im ersten Kode eine Zweideutigkeit ergibt. Auf diese Weise wird zwar nicht vermieden, daß ein Fehler in der ersten Stelle manchmal unkorrigierbar bleibt, aber es wird sichergestellt, daß er nicht immer unentdeckt bleibt. Die Tabelle 2 zeigt einen solchen zweiten Kode, bei den sich nun nicht die erste und die fünfte Spalte, sondern die zweite und die vierte Spalte gleichen. Tabelle 1 1 1 0 0 1 0 1 10 0 1 0 1 1 1 Tabelle 2 1 1 0 1 0 0 1 1 1 0 1 0 0 0 1 Durch Anwendung dieses Kodes auf den nächstfolgenden Block würde ein Einzelfehler des ersten Informationsbits also sicher lokalisiert sowie der erwähnte Dreifachfehler sicher erkannt. Treten solche Fehler mehrfach nur bei Anwendung des zweiten Kodes auf, dann ist die Wahrscheinlichkeit groß, daß auch in den dazwischenliegenden Blöcken, in denen dieser Fehler nicht erkennbar ist, ein Fehler vorlag. Eine hier nicht näher erläuterte Fehleranalysierschaltung könnte dies feststellen und anschließend beispielsweise den zueilt mit dem ersten Kode behandelten Block nochmals übertragen, diesmal unter Anwendung des anderen Kodes.Since errors that occur are not always statistically distributed, but often have their cause in a miscalculation of the system, which can be reproduced as often as required, an error that systematically always appears in the first place can be discovered with the present matrix, but cannot be localized According to the invention, such errors can sometimes be recognized if different codes are used for successive information blocks, the second code being chosen in such a way that errors can be recognized precisely in those places for which there is an ambiguity in the first code. In this way it is not avoided that an error in the first digit sometimes remains uncorrectable, but it is ensured that it does not always go undetected. Table 2 shows such a second code in which not the first and fifth columns, but the second and fourth columns are the same. Table 1 1 1 0 0 1 0 1 10 0 1 0 1 1 1 Table 2 1 1 0 1 0 0 1 1 1 0 1 0 0 0 1 By applying this code to the next block, an individual error in the first information bit would be reliably localized and the aforementioned triple error would be reliably recognized. If such errors occur several times only when the second code is used, then there is a high probability that an error was also present in the blocks in between, in which this error is not recognizable. An error analysis circuit, which is not explained in greater detail here, could determine this and then, for example, retransmit the block allocated with the first code, this time using the other code.

Die Realisierung verschiedener Kodes kann durch Umschaltung der den Kode bestimmenden Matrix (z. B. eines Zählers) oder durch Vergrößerung der Spaltenzahl der Matrix erfolgen. Ein Kodezähler, der normalerweise hei jedem Block seinen Zählzyklus einmal durchläuft, -soll gemäß der Erfindung also einen längeren oder kürzeren Zyklus besitzen, so daß Blockanfang und Zyklusanfang nicht immer zusammenfallen. Bei Verwendung sogenannter zyklischer Kodes (vgl. z. B: das erwähnte Buch von W. W. P e t e r s o n) ist ein Wechsel der Kodematrix besonders einfach durch Wechsel der Rückkopplungsstellen innerhalb des rückgekoppelten Schieberegisters zu erreichen.Different codes can be implemented by switching the Code-determining matrix (e.g. of a counter) or by increasing the number of columns the matrix. A code counter that normally has its counting cycle for each block runs once through, -soll according to the invention so a longer or shorter cycle so that the beginning of the block and the beginning of the cycle do not always coincide. Using so-called cyclic codes (cf. e.g .: the mentioned book by W. W. P e t e r s o n) a change in the code matrix is particularly easy by changing the feedback points within the feedback shift register.

Im folgenden Ausführungsbeispiel gemäß der Figur ist ein vollständiges Datenübertragungssystem gezeigt mit einem Datengeber 1, einer Kodiereinrichtung 2 zur Gewinnung da Prüfzeichengruppe, einer Ubertragungsstrrecke mit Modulator 3 und Demodulator 4, einer Dekodiereinrichtung 5 zur Gewinnung von Korrekturzeichen und einer Korrigiereinrichtung, bestehend aus einem Pufferspeicher 6 und einem Zuordner 7, der aus den Korrekturzeichen den Fehlerort des im Pufferspeicher stehenden Datenblocks ermittelt und den Fehler korrigiert.In the following exemplary embodiment according to the figure, a complete data transmission system is shown with a data transmitter 1, a coding device 2 for obtaining the check character group, a transmission link with modulator 3 and demodulator 4, a decoding device 5 for obtaining correction characters and a correcting device, consisting of a buffer memory 6 and an allocator 7 which uses the correction characters to determine the location of the error in the data block in the buffer memory and which corrects the error.

Das Kernstück der Kodiereinrichtung 2 ist ein Kodezähler 8, der nacheinander alle Spalten einer dreizeiligen Matrix an seinen drei Ausgängen liefert. Der Zähler besitzt einen achtzehntaktigen Zählzyklus gemäß den Spalten der nachfolgenden Tabelle 3. . Tabelle 3 1 1 0 0 1 1 1 0 0 1 1 0 1 0 1 1 0 0 0 1 1 0 0 0 1 1 0 0 1 1 1 0 1 0 1 0 1 0 1 1 1 0 1 0 0 1 0 0 0 1 1 0 1 0 Weiterhin ist in der Figur ein Stellenzähler 9 angedeutet, der nagt jedem Block von neuem zu zählen beginnt. Der Datengeber 1 liefert synchron mit den Taktimpulsen eines Taktgeherators 10 je Block fünf binäre Informationselemente sowohl an den Modulator 3 als auch an die Kodiereinrichtung 2. Zwischen zwei Blöcken liegen vier Takte Pause, die zur Übertragung der Prüfzeichen und zur Fehlerkorrektur benötigt werden, wie sich später zeigen wird.The core of the coding device 2 is a code counter 8 which successively supplies all columns of a three-line matrix at its three outputs. The counter has an eighteen-step counting cycle according to the columns in Table 3 below. . Table 3 1 1 0 0 1 1 1 0 0 1 1 0 1 0 1 1 0 0 0 1 1 0 0 0 1 1 0 0 1 1 1 0 1 0 1 0 1 0 1 1 1 0 1 0 0 1 0 0 0 1 1 0 1 0 Furthermore, a digit counter 9 is indicated in the figure, which gnaws every block and begins to count anew. The data generator 1 supplies five binary information elements per block to both the modulator 3 and the coding device 2 synchronously with the clock pulses of a clock generator 10 will show.

Der Stellenzähler beginnt also nach jeweils neun Takten von neuem zu zählen; er wird zur Ablaufsteuerung eingesetzt, indem er erst diejenigen Leitungen durchschaltet, über die die Prüfzeichen gebildet werden (Takte 1 bis 5) und anschließend (Takte 6 bis 8) die Übergabe der Prüfzeichengruppe an den Modulator veranlaßt. Die Prüfzeichengruppe wird durch vektorielle Addition modulo 2 aus den jeweiligen Spalten der Tabelle 3 gebildet, deren zugeordnetes Informationsbit eine Eins zeigt (Addiernetz 11). Zwischenergebnisse und die endgültige Prüfzeichengruppe werden in einem dreistelligen Register 12 abgesetzt. Der Inhalt dieses Registers wird während der Takte 6 bis 8 an den Modulator 3 in Serie abgegeben.The position counter thus begins to count again after every nine bars; it is used for sequence control by first switching those lines through which the check characters are formed (bars 1 to 5) and then (bars 6 to 8) initiates the transfer of the check character group to the modulator. The check character group is formed by vector addition modulo 2 from the respective columns of table 3, the associated information bit of which shows a one (adding network 11). Intermediate results and the final group of test characters are stored in a three-digit register 12. The content of this register is sent to the modulator 3 in series during bars 6 to 8.

Wie schon erwähnt, besitzt der Kodezähler einen achtzehntaktigen Zählzyklus, was bedeutet, daß während der Behandlung eines Blocks die ersten neun Zählzustände, während der Behandlung des nächsten Blocks aber die zweiten neuen Zustände durchlaufen werden. Für den Kodiervorgang werden nur die ersten fünf und die Zustände 10 bis 14 ausgewertet, so daß die übrigen Spalten der Tabelle 3 beliebig ausgebildet sein können.As already mentioned, the code counter has an eighteen-step counting cycle, which means that during the handling of a block the first nine counting states, but go through the second new states while handling the next block will. Only the first five and states 10 to 14 evaluated so that the remaining columns of table 3 can be designed as desired can.

Für den Dekodiervorgang aber benötigt man zweimal acht Spalten, da hier der ankommende Datenblock acht Bits umfaßt. Der Pufferspeicher 6 nimmt diese acht Bits kurzzeitig auf, während gleichzeitig in der Dekodiereinrichtung 5 eine Korrekturzeichengruppe auf dieselbe Weise wie die Prüfzeichengruppe gebildet wird. Diese Einrichtung enthält also ebenfalls einen Kodezähler 8, einen Blockstellenzähler 9, ein Addiernetz 11 und ein Register 12. Während der Blockübertragung, die acht Takte dauert, wird die Korrekturzeichengruppe im Register 12 gebildet. In der neunten Taktzeit wertet schließlich der Fehlerzuordner 7 den Registerinhalt zur Korrektur des Datenblocks aus. Gleichzeitig wird das Register 12 gelöscht und damit für den neuen Block vorbereitet. Der Taktgenerator 10 ist durch an sich bekannte und hier nicht näher zu beschreibende Mittel mit dem Taktgenerator der Kodiereinrichtung derart synchronisiert, daß bei Vorliegen des gleichen Datenbits jeweils gleiche Zählerstände auf der Kodier- und auf der Dekodierseite vorherrschen.For the decoding process, however, eight columns are required twice, since the incoming data block here comprises eight bits. The buffer memory 6 briefly stores these eight bits, while at the same time a correction character group is formed in the decoder 5 in the same way as the check character group. This device thus also contains a code counter 8, a block position counter 9, an adding network 11 and a register 12. During the block transfer, which lasts eight clocks, the group of correction characters is formed in register 12. Finally, in the ninth cycle time, the error allocator 7 evaluates the register content to correct the data block. At the same time, register 12 is cleared and thus prepared for the new block. The clock generator 10 is synchronized with the clock generator of the coding device by means which are known per se and will not be described in greater detail here, in such a way that when the same data bit is present, the same counter readings prevail on the coding and decoding sides.

Durch die Erfindung wird also eine Anpassung nicht vollkommener Kodes an die praktischen Erfordernisse der Fehlererkennung erzielt, wodurch systematisch Fehler auch dann erkannt und korrigiert werden können, wenn ihre Art und Stellung innerhalb des Informationsblocks bei Anwendung nur eines Kodes an sich keine Korrektur erlauben würde. Selbstverständlich ist die Erfindung nicht auf das erläuterte Zahlenbeispiel beschränkt, vielmehr muß nochmals betont werden, daß in der Praxis die Redundanz und die Zahl der Informationsbits in einem Block wesentlich größer ist.The invention therefore makes it possible to adapt imperfect codes to the practical requirements of error detection achieved, thereby systematically Errors can also be recognized and corrected if their nature and position No correction per se within the information block when only one code is used would allow. Of course, the invention is not limited to the numerical example explained limited, rather it must be emphasized again that in practice the redundancy and the number of information bits in a block is much larger.

Außerdem ist die Erfindung nicht insoweit auf das Ausführungsbeispiel beschränkt, als die Zyklusseiten der beiden Zähler 8 und 9 im Verhältnis 2: 1 stehen. Vielmehr ergibt sich der Vorteil der Erfindung auch bei anderen Verhältnissen, insbesondere auch bei einem Verhältnis von n : (n ± 1). In addition, the invention is not limited to the exemplary embodiment insofar as the cycle sides of the two counters 8 and 9 have a ratio of 2: 1. Rather, the advantage of the invention also results with other ratios, in particular also with a ratio of n: (n ± 1).

Claims

Claims: 1. Method for data transmission, in which on the transmitting side a group of test characters for each data block according to an agreed code is formed on the receiving side for recognition and, if necessary, correction of 1; transmission errors is evaluated, d a d u r c h indicated that for successive blocks different codes are used.

2. Procedure according to claim 1, characterized in that the logic elements defining the code, Counter or the like switched over on the sending and receiving side according to an agreed plan will.

3. The method according to claim 1 or 2, wherein the test character group by vectorial addition of different columns depending on the data content of the block Code matrices, which appear as the states of a code counter, are formed, characterized in that the code counter passes through more states in one cycle, than are required to form the check character group for a block, so that for successive blocks find different parts of the code matrix use.