DE1249909B - Method and circuit arrangement for error correction of transmitted data words according to the type of similarity decoding with a code word supply - Google Patents

Description

FEDERAL REPUBLIC OF GERMANY

GERMAN ALS || ^ PATENT OFFICE

EDITORIAL

Int. Cl .:

H04b

H041
German class: 21 al - 7/06

Number: 1249 909

File number: T 30332 VIII a / 21 al

Filing date: January 27, 1966

Opened on September 14, 1967

The invention relates to a method for error correction of transmitted data words after Type of similarity decoding in which a code word changed by transmission interference that code word is assigned which differs from it the least.

In order to be able to examine transmitted information for errors, it must be redundant. By doing The extent to which the requirements for recognizability caused by errors or the reconstruction of destroyed information, the growth also increases redundancy to be added to the information. When correcting errors through reconstruction, everyone Code word assigned a certain environment of meaningless words, 'which upon receipt of this Code word. They form the correction area of the code word. Also can meaningless words remain that are not assigned to any correction area and are displayed as errors will.

One way of reconstructing disturbed information is to assume for a received meaningless word that code word that differs least from the received word. This type of decoding is called similarity decoding and is e.g. B. mentioned in US Pat. No. 3,164,804. Previously possible arrangements for carrying out this transmission method require a very large amount of circuitry because it is necessary to compare the respective received word with all permissible code words of the code. Furthermore, the code word that is most similar to the received word must be determined with a maximum detector. If a received word consists of mBits, 2 ^m comparison stages are necessary to carry out the actual comparison, and also the maximum detector mentioned above. One possibility of realizing the 2 ^m comparison levels including the maximum detector consists in the use of a learning matrix, as it is used for problems of writing or speech recognition. Such a learning matrix is e.g. B. described in the magazine Cybernetik 1, 1961, Issue 1, pp. 36 to 45. However, there are also many limits for the time being when it comes to using words with a large number of bits, e.g. B. more than ten to compare and detect.

On the other hand, many correction methods are known in which each information unit, e.g. B. each word, a correction information (redundancy) is calculated, by means of which a probable method and circuit arrangement after an information disturbance
to correct errors in transmitted
Data words according to the type of
Similarity decoding with a
Code word stock

Applicant:

Telephone

Patentverwertungsgesellschaft mb H.,
Ulm / Danube, Elisabethenstr. 3

Named as inventor:

Dipl.-Ing. Dr. Horst Ohnsorge, Ulm / Danube;

Peter Drescher, Constance

most error can be detected. Such methods require less circuit complexity, they deliver but also a significantly smaller reduction in the probability of errors than the method of Similarity decoding. Methods and arrangements for calculating correction information are e.g. described in the book by W.W. Peterson, "Efror Correcting Codes," 1961.

It is now the aim of the invention to find a method with which a similarity decoding can be carried out without great effort.

The invention relates to a method for correcting errors in transmitted data words according to Art the similarity decoding with a code word set, of which only some of the code words pass through Character assignment is defined and in the case of a code word received on the receiving side the one a defined code word is assigned that differs the least from it, characterized in that that between each received word and each of the defined code words of the code the respective Hamming distance is determined by comparison and that defined code word is selected

for which the determined Hamming distance kleiffor odd-numbered

less than or equal to the value ——

for even d , where the

,, d — 2

ges d or r—

the defined code words assigned to the characters have a minimum hammering distance d from one another which is greater than 2.

709 647/364

The invention takes advantage of the properties of the so-called close-packed codes. They allowed Code words within such a code have a minimum hamming distance that is probably exceeded but must not be undercut. Thus, the correction area, i.e. the environment, is more meaningless Words of a code word can be clearly described using the Hamming distance. That way is the Possibility given on the basis of the Hamming distance between a code word and a code word to determine whether the latter is a meaningless word from the correction area of the code word or another code word. In the latter case are then the Word juxtapose other code words one after the other until a clear positive decision is possible. In the case of densely packed codes, this clear decision will be made in any case, since there are no further meaningless words between the correction areas of the individual code words can. However, this is the case with certain codes which are similar to the densely packed codes. here a comparison of a word with all code words of this code could not bring a decision, and a data repetition would have to be initiated. Both types of codes mentioned here are the limit of the correction range around each code word

d- 1

of the ones output by the non-equivalence circuits 4 is used as a comparator with a Detector 6 formed threshold level is detected. When comparing the number of different Place between the two words under the

d— 1

for, code words odd

Minimum hamming distance and for such even-numbered minimum hamming distance at - = - · ^ ' ^st the

Minimum hamming distance of the code used.

Each received code word is sequentially with simultaneous determination of the respective Hamming distance contrasted with the code words of the code until a code word is found in whose correction area the opposite word is located. For this comparison there will be a Code word generator used, which successively generates all permitted code words of the code.

An exemplary embodiment for this is shown in FIG. 1. F i g. 2 shows a possible state diagram for the code generator of FIG. 1.

In Fig. 1, 1 represents a transmitter, one after the other Sends code words over a transmission line 2 to a receiver, which by all the remaining Parts of the FIG. 1 is characterized. The line 2 has interference properties, so that a transmitter 1 sent code word can also reach the recipient as a meaningless word. Out of uncertainty Whether a received word is a meaningless word or a code word is only known to the recipient by received Words spoken. A received word enters the shift register 3. All stages of this Shift registers are via non-equivalence circuits 4 with stages of a feedback shift register 5 tied together. This shift register 5 serves as a code word generator; will be in it after receiving of a word generates all permitted code words of the code. In each case after the generation of a code word the non-equivalence circuits are queried. With this query, each non-equivalence level returns a zero off if the content of their connected levels matches, or a one if the content does not matches. The number of mismatches between the respective code word in the code word generator and the shift register 3, so the number threshold that the correction limit

respectively.

is proportional to the code used in each case, the code word in the code word generator 5 becomes via a switch 7 to a data sink 8, because as soon as a word is within a correction range is encountered, it cannot be in any other correction area.

The receiver is controlled by a receiver control 9. This derives from the clock received words an own clock for storing the words in the shift register 3, for further switching of the code word generator 5 and for saving a code word from the code generator 5 into the depression. For this purpose, all clock and control lines are shown with dashed lines. Also the detector 6 outputs its threshold value pulse to the receiver control 9, whereupon this for the time of Withdrawal of the code word from the code word generator 5, the switch 7 closes and the corresponding Storing clocks to the data sink 8 emits. For the process of saving a code word the code word generator 5 this must be connected as a shift register. For this purpose, the To separate feedback points of the register, which is also done by the receiver control 9 is, in the F i g. 1 is not drawn for reasons of clarity.

The structure and mode of operation of code word generators are detailed in the book already mentioned described by W. W. Peterson. A rectangular ferrite core comparator can advantageously be used as the detector 6 use. This then has as many reset windings as there are no equivalence circuits are present, and a reset winding controlled by the receiver control 9, with the at the same time the magnetic bias is made to adjust the threshold value. Instead of Equivalence circuits 4 can also be used. This is then with the Take into account the design of the detector.

Is the one used to display information However, the code is not a tightly packed one, but rather one that is merely similar to it, i. i.e., it points between the correction areas individual code words on further meaningless words, the receiver control 9 is like this to set up that after a fruitless comparison of a received word with all code words a signal is emitted, either to initiate a data repetition or to further Switching or annotation criteria is used.

So far nothing has been said about the structure of a transferred word. A word can e.g. B. off consist of a plurality of characters, each of which represents a letter or a digit, or it can be identical to one character. For the following considerations, the identity between one sign and one word accepted. Since the comparison time is crucial for every word received for the transmission speed of the overall system, care must be taken to ensure this to keep it as short as possible. A first way to achieve

To achieve this goal, the code words should be divided into two groups. The division can now according to the criterion of the average frequency of transmission of a group of characters or according to the type of character take place. After its start, the switching mechanism runs through the starting position first the more important group and then the group subordinate to it, then becomes the mean comparison time with the condition that the code word generator immediately after a successful comparison in its initial state is switched back, become shorter.

This method can be used very effectively if, as is the case with the telex alphabet, for example, letters and digits shift characters are introduced, but while maintaining their own code words for letters and digits. 2 shows a sequence diagram according to the invention for the code word generator 5. Each of the small circles in this diagram represents a switching state of the code word generator 5. Starting from a state zero, it goes through a number of such states until it returns to the initial state zero. Starting from the initial switching position zero, the code word generator 5 first generates the code word for the digit changeover, then that for the letter changeover and, in the following switching states, letter code words. The digit code words lie between the letter code words and the initial position zero. The code word generator only runs through the word group announced by a preceding shift character. In addition, after a successful comparison, it can return to the initial state from any switching state, that is to say from any circuit, which is achieved by the action of the receiver control 9. Furthermore, the receiver control 9, in conjunction with a recognition circuit, may be able to recognize digit shift characters and letter shift characters received via the code word generator 5. Depending on this, in FIG. 2 two points B and Z controlled in such a way that the point B is permeable and the point Z is blocked if the last received and recognized shift character was a letter shift character. In this case, the code word generator, coming from its starting position zero, runs through the switching states Zi and Bu and then the letter code words. From the code word at which the detector 6 responds, it returns to the starting position. Of course, it is also possible to return there only after going through the entire group. If, on the other hand, the last shift character received was a digit shift character, then switch B is blocked and switch Z is open. If a word is now received, the code word generator runs via the positions Zi and Bu , bypassing all letter code words, directly to the first code word from which it runs through the code words. If you now calculate with 26 letters and about 30 digits including special characters in the entire code space, the code word generator only has to run through at most half of its total possible switching states, so that this measure saves a considerable amount of time when comparing the received words with all code words of the code can be achieved.

In addition, this leads to a further reduction in the probability of transmission errors performed. Because z. B. within a digit broadcast preceded by a digit shift character is, a digit during transmission due to strong interference in a letter code word converted, the comparison on the receiving side cannot lead to success, since only is compared with all digit code words and not with letter code words. Corresponding applies to the transmission of letters, since in this case the code word generator only contains the letter code words, but does not run through the digit code words.

That in connection with the F i g. The method shown in 2 is expedient for such transmission links are used on which preferably larger sequences of digits and letters and less mixed information is transmitted. In the latter case, however, the advantage of further reduction in the probability of transmission errors, the disadvantage that then occurs Frequently transmitted letters or digits shift characters predominate.

A time saving for the execution of the comparison can of course also be achieved by that all code words are broken down into several subsets and on the receiving side for each subset a decoder according to FIG. 1 provides. A received word is then temporally parallel with the code words of subsets compared.

Are all code words equally likely and z. B. two decoders provided, then the Receivers according to FIG. 1 only have to carry out half as many comparisons on average as code words in total available. The method is therefore fundamentally superior to the known method a saving of at least half the normal comparison time.

Claims (9)

Patent claims: 1. Method for error correction of transmitted data words according to the type of similarity decoding with a codeword stock, of which only a part of the codewords by character assignment is defined and in the case of a received code word on the receiving side that defined code word is assigned that differs least from him, characterized in that between each received word and each of the defined code words of the code by comparing the respective Hamming distance determined and that defined code word is selected for that the determined Hamming distance is smaller or equal to the value - χ - for odd-numbered ges d or rf-2 for even d , where the defined code words assigned to the characters have a minimum hammering distance d from one another which is greater than 2. 2. The method according to claim 1, characterized in that the comparison after the selection a defined code word is ended and that a signal is then emitted when the comparison of the respective received word with all defined code words does not ming distance that is less than or equal to u d-2 respectively. - is. 2 "" "'2 3. The method according to claims 1 and 2, characterized in that the defined Code words are divided into two groups, so that the code words of one group have a higher frequency of transmission than those of the other group, and that first the Code words of the group with the higher average transmission frequency are generated. 4. The method according to claims 1 to 3, characterized in that the defined code words be divided into a letter and a number special character group that follow words from both groups are announced by the sender using group shift characters and that with each comparison only the code words of the announced group in whole or in part be run through. ao 5. The method according to claim 4, characterized in that that generated group shift characters and after recognizing a group shift character for the subsequent code words received up to the next group shift character only the code words of the announced group are generated. 6. The method according to claims 1 to 4, characterized in that the defined code words are divided into groups and that for the code words of each group separately the respective Hamming distance is determined. 7. Circuit arrangement for performing the method according to claims 1 to 6, characterized through a register (3) for receiving the code word received in each case, through a Code word generator (5) which, in response to an external signal, generates all defined code words of the code generated by a comparison stage (4) for comparing the respective register content and code word generator content and by a detector (6) for determining the number of matching and non-matching bits. 8. Circuit arrangement according to claim 7, characterized in that the comparison stage (4) consists of a plurality of non-equivalence elements and the detector as a comparator with a Threshold level is formed and that the detector emits a signal when its input variable falls below the threshold. 9. Circuit arrangement according to claim 7, characterized in that the code word generator (5) is designed as a feedback shift register with mod-2 addition points. 1 sheet of drawings 709 647/384 9.67 © Bundesdruckerei Berlin