Method of detecting synchronization errors in a data transmission system using a linear block code

In a data transmission system messages can be transmitted in the form of sequentially linked modified code words of a linear block code, the modified code words being produced by combining the code words formed from the data with a protection word. When such modified code words are interleaved bit-wise in order to recognize random errors, the sequence of code words of the transmitted message may be changed after de-interleaving at the receiver, by bit shift, due to faulty synchronization of the transmitter and receiver. In order to recognize this, each code word is linked to a protection word which identifies its position within the message. The modified code words thus obtained are interleaved bit-wise, transmitted and de-interleaved again at the receiver. Each word thus obtained at the receiver is combined with a check word identifying its position within the message. The protection words and the check words are chosen so that the key words produced by combining them are in code word sub-classes which are not used for decoding.

BACKGROUND OF THE INVENTION 
1. Field of the Invention 
The invention relates to a method of detecting and possibly correcting 
errors caused by loss of synchronization of a data sink with a data source 
in a data transmission system using a linear block code. 
2. Description of the Related Art 
In a data transmission system having a data sink and a data source messages 
are exchanged between the sink and the sources over transmission channels. 
Such messages may have a word structure and consist, for example, of 
linked code words in a linear block code. A block code is a code in which 
all code words are of equal lengths, a sequence of symbols (or source 
words) to be encoded being divided into blocks of equal lengths. A 
systematic code is one in which a particular code word is assigned to each 
of the symbols or source words provided by the data source. In a linear 
systematic block code each linear combination of code words also 
constitutes a code word. 
Consecutive code words are linked and transmitted in a continuous sequence 
over the transmission channel. In order to be separated at the receiver, 
it is necessary to synchronize the decoder therein with the encoding 
effected at the transmitter. This is denoted word synchronization. 
In "Fehlerkorrigierende Block-Codierung fur die Datenubertragung" by F. J. 
Furrer, Birkhauser Verlag, 1981, pages 238 to 250, a description is given 
of methods of word synchronization for consecutively transmitted code 
words using synchronization samples, codes with binary prefixes, separable 
codes and synchronizable codes. Which synchronization method is chosen, as 
well as the method of encoding, depends on the properties of the 
transmission channel. For the purpose of synchronization, a 
synchronization sample can be used which is a fixed bit sequence of a 
predetermined length and which is known to the receiver (see, for example, 
ISO recommendation 3309-1979). However, including a synchronization sample 
at the beginning of a message and repeating it at predetermined distances 
(numbers of bits) within the message reduces the effective data 
transmission speed of the transmission channel. 
A further method of word synchronization is disclosed in "Error-Correcting 
Codes" by Peterson/Weldon, 2nd Edition 1972 at pages 374 to 390. In this 
method all the sequentially transmitted code words are linked to the same 
error protection word, whereby a bit-wise shift of the code words of a 
message can be recognized. The protection word, which is not a code word, 
is added at the transmitter and subtracted at the receiver. On page 379 an 
example is described in which the protection word for a binary code is 
chosen to be equal to "1", as a result of which the last bit of each of 
the code words is inverted. If the code words are shifted through one or 
more bit positions, then, because of the fact that the encoding 
instruction is violated, this bit shift can be recognized and possibly 
corrected at the receiver. 
So as to render it possible to use codes which recognize or correct 
randomly occurring errors, which may occur in transmission over channels 
which are susceptible to interference and have error bursts, for example 
radio transmission channels, the individual code words can be interleaved 
bit-wise prior to transmission. For the purpose of bit-sequential 
interleaving the first bit of each of the code words is transmitted, then 
the second bit of each of the code words, and so on until the last bits of 
all the coce words of the messages are joined together. Such interleaving 
is described in the article by B. Dorsch "Performance and Limits of Coding 
for Simple Time Varying Channels", 1980, International Zurich Seminar on 
Digital Communications, Proceedings IEEE Catalog No. 80 CH 1521-4, 
left-hand column of page G 1.1). 
SUMMARY OF THE INVENTION 
The invention is based on recognition that faulty synchronization in 
bit-wise interleaved code words of message evidences itself as a change in 
the sequence of the interleaved code words at the receiver, and provides a 
method of word synchronization by which such changes in sequence of 
received code words of a message can be recognized. 
If the code words of a message in linear block code are bit-wise 
interleaved and transmitted over a disturbed transmission channel, then a 
change in the sequence of the received code words as compared with the 
transmitted sequence may occur. By linking the code words with protection 
words or check words which identify the position of the code words within 
the message, such a change in sequence can be recognized unambiguously. 
Taking account of the predetermined encoding instructions, appropriate 
protection words or the check words can readily be selected. During 
transmission over a disturbed transmission channel an error burst may 
occur in a code word. By bit-wise interleaving the code words, the error 
burst is distributed over several code words. Consequently, the word error 
probability and the residual error probability are less than in 
block-sequential transmission of successive code words. 
If a linear systematic code is used the length of the protection or check 
words may be limited to a particular portion ("check portion") of the code 
words. This renders it possible to reduce the cost and complexity of the 
circuitry at the receiver and at the transmitter for putting the method 
into effect. 
The check words and protection words are respectively stored at the 
receiving and the transmitting ends. For duplex transmission systems, the 
required storage capacity can be reduced to 50% if the protection words 
are at the same time employed as the check words. The required storage 
capacity can be further reduced if the protection words and check words 
are code words of a linear code, the matrix for identifying them being 
stored in a memory. 
Linking of code words with protection words or check words may be effected 
by bit-sequential module-2 addition, which is simple to effect and reduces 
the cost of the required circuits.

DESCRIPTION OF THE PREFERRED EMBODIMENTS 
In the data transmission system shown in FIG. 1 for the transmission of 
messages M, a data source 1 is connected to a data sink 3 by a 
transmission channel 2. The transmitter comprises an encoder 4, an adder 6 
and a circuit 8 for the bit-wise interleaving of modified code words 
c'.sub.L produced by adder circuit 6 from code words c.sub.L provided by 
encoder 4 from the data words provided by data source 1. The receiver 
comprises a circuit 9 for de-interleaving the modified code words c'.sub.L 
received from the transmission channel 2, a subtraction circuit 7 and a 
decoder 5. In accordance with stored encoding instructions, encoder 4 
assigns code words c.sub.L to each of the symbols (data words) produced by 
the data source 1. In the adder circuit 6 a protection word w.sub.L, which 
is characteristic of the position of the code word within the message N, 
is linked to each code word c.sub.L. The protection words w.sub.L are 
obtained from a memory 10 in which they are stored. The modified code 
words c'L thus formed are interleaved bit-wise by interleaving circuit 8 
and are transmitted. At the receiver they are first de-interleaved by 
circuit 9, and each of the de-interleaved received code words c.sub.K is 
linked in a subtraction circuit 7 to a check word w.sub.K which is 
characteristic of the position of the de-interleaved word within the 
message M. The ckeck words w.sub.K are obtained from a memory 11 in which 
they are stored. 
When the data source 1 and the data sink 3 are in synchronization with each 
other, the code word c.sub.K produced at the output of the subtraction 
circuit 7 in the receiver will be identical to the transmitted code word 
c.sub.L. The code word c.sub.K is converted into the corresponding data 
word in the decoder 5, and then applied to the data sink 3 for message 
evaluation. Any error in word block synchronization will result in faulty 
message evaluation in data sink 3. 
The system in FIG. 1 may represent a radio transmission system, numbers 
identifying the various radio subscribers being transmitted, for example, 
as messages M over the transmission channel 2 between a mobile subscriber 
station (such as data source 1) and a fixed radio station (such as data 
sink 3). In the direction from the mobile subscriber station to the fixed 
radio station a message M may comprise for example, ten code words; and in 
the opposite direction a message may comprise eight code words. A faulty 
message evaluation could, for example, result in a call being charged to 
the wrong account. 
FIG. 2 shows in the form of a Table the bit-wise interleaving of the 
transmitted modified code words C'.sub.L and the bit-wise de-interleaving 
of the received modified words c.sub.K. In the event of faulty 
synchronization, for example when the transmitted modified code words 
c'.sub.L are shifted through two bit positions at the receiver, an 
interchanging of code words occurs. The Table shows a message M consisting 
of sixteen code elements, to which four code words (c'.sub.L, c.sub.K) 
with a number of positions equal to four are assigned. The sixteen 
positions of the bit sequence of the transmitted and received code words 
of the message M are indicated at the head of the Table. In the column on 
the left in the Table the transmitted modified code words c'.sub.L and 
also the received modified code words c.sub.K are arranged according to 
their sequence in the message M. The Table illustrates case of faulty 
synchronization by two bit positions, whereby the sequence of the 
transmitted words (c'.sub.1, c'.sub.2, c'.sub.3, c'.sub.4) is 
interchanged; that is to say, the received code words c.sub.K are in a 
difference sequence (c'.sub.3, c'.sub.4, c'.sub.1, c'.sub.2). The code 
elements in the Table are identified by indices, for example c'.sub.2,4, 
indicating that this particular code element is in the fourth position of 
the second modified code word c'.sub.L. The crosses (x) in the fifteenth 
and sixteenth bit positions within the received message M indicate that 
elements in these positions do not correspond to any code elements of code 
words in the transmitted message M. A shift through two bit positions 
causes a change by two positions in the sequence of the received word 
c.sub.K. 
The Table in FIG. 3 shows the possible sequences of the four received code 
words c.sub.K resulting from a shift through a number of bit positions of 
a message M comprising four transmitted code words c.sub.L. In the Table 
the left-hand column signifies such shifts through up to three bit 
positions, the sign indicating the direction of shift. A negative sign 
signifies that the word c.sub.K is received too late, and a positive sign 
that it was received too early, relative to the transmitted sequence of 
the code words c.sub.L (or the modified code words c'.sub.L). 
Because of such faulty synchronization, the sequence of the received code 
words c.sub.K is cyclically changed relative to the sequences of the 
transmitted code words c.sub.L, and additional shifts occur in the last f 
or first f of the words c.sub.K. In the Table in FIG. 3 the words c.sub.K 
in which such additional shifts occur are indicated by an asterisk. 
The probability that a message M is evaluated incorrectly because of faulty 
synchronization is very great even from a shift through only a few bit 
positions. In a linear code it is possible that owing to the bit shift in 
each of the words c.sub.K a binary sample will be produced which is one of 
the stored code words, thereby signifying nonexistent data. 
To recognize faulty synchronization, the sequence of the code words c.sub.L 
to be transmitted is identified in accordance with the invention by 
linking each such code word to a protection word w.sub.L in accordance 
with the linking instruction 
EQU c'.sub.L =c.sub.L .sym.w.sub.L 
A bit-wise modulo-2 addition is preferably used to carry out this linking 
instruction. 
After bit-wise interleaving, transmission and de-interleaving, each 
received modified code word c.sub.K is linked to a check word w.sub.K to 
derive a code word c.sub.K in accordance with the linking instruction 
EQU c.sub.K =c.sub.K .sym.w.sub.K. 
This instruction is also preferably effected by means of modulo-2 addition. 
This results in formation of a key word w.sub.KL in accordance with the 
linking instruction 
EQU w.sub.KL =w.sub.K .sym.w.sub.L, 
the key word w.sub.KL being obtained at the receiver. 
If the data sink 3 at the receiver is in synchronizm with data source 1 at 
the transmitter, then the sequence of the transmitted modified code words 
c'.sub.L will correspond to the sequence of the received modified code 
words c.sub.K. That is to say, K=L. The code modification introduced at 
the transmitter by the addition to each code word of the protection word 
w.sub.L will therefor be eliminated at the receiver by the addition of a 
check word w.sub.K which is the same as the protection word W.sub.L. 
To ensure unambiguous recognition of faulty synchronization of a linear 
block code having a level e of error correction (as explained 
hereinafter), the protection or check words w.sub.L or w.sub.K must be 
chosen such that the resulting key words w.sub.KL are in a secondary class 
of code words which are not used for decoding. Such a secondary class can 
be determined, for example, by syndrome formation. 
Using a linear, systematic (16, 8, 5) block code, code words may be 
generated in accordance with the polynomial g(x)=x.sup.8 +x.sup.7 +x.sup.6 
+x.sup.4 +x.sup.2 +x+1. This is capable of correcting up to two errors. 
The Table in FIG. 4 shows, for a message M having ten such code words L, 
the selected protection words w.sub.L (which are the same as the check 
words w.sub.K) to be associated with them. The decimal values z.sub.L of 
the bit samples of the associated protection words w.sub.L (and check 
words w.sub.K) and the positions of the bit samples are indicated in the 
Table. 
The bit samples of the protection words w.sub.L or check words w.sub.K are 
then chosen so that when those words are linked a key word w.sub.KL is 
obtined which has a greater Hamming distance than the number e of the 
corrected errors of each code word. In addition, the bit samples should be 
such that the key word w.sub.KL produced for K=L is not a code word used 
for decoding. It can be demonstrated that this means that the bit samples 
searched for must be elements such that the key words w.sub.KL produced 
for K=L will be in a secondary class of code words which are not used for 
decoding. 
In event of faulty synchronization the bit samples of w.sub.L and w.sub.K 
will not agree. In addition to the code violation caused at the 
transmitter by adding to the code words c.sub.L the bit samples of the 
protection word w.sub.L, there will be further code violations caused at 
the receiver by adding the bit samples of the check words w.sub.K to the 
received code words. The sum of the binary positions (code elements) thus 
invalidated in a received code word c.sub.K may therefore exceed the 
number e of correctable errors. 
FIG. 5 shows, for a linear systematic (16, 8, 5) block code having an 
error-correction level e=2, the matrix of key words w.sub.KL which is 
obtained by linking the bit samples of the protection words w.sub.K with 
the bit samples of the check words w.sub.L of FIG. 4. From the specified 
secondary class conditions a quadrapole (25, 44, 138, 201) can be 
determined as a bit sample, which quadrapole covers a sub-storage area 
having sixteen bit samples. From these sixteen bit samples ten are chosen 
which are indicated in the Table of FIG. 4. The Table of FIG. 5 shows all 
the possible combinations of these ten bit samples. 
The key words w.sub.KL obtained by such linking and having the decimal 
representations 111 and 118 are elements of a secondary class N.sub.t of 
code words of a code having a minimum Hamming distance equal to two. For 
example, as a result of the faulty synchronization, the key word w.sub.KL 
having the decimal number 25 is combined with check word w.sub.L having 
the decimal number 111. The key word w.sub.KL which is obtained as the 
result of a bit shift through seven positions and which has the decimal 
number 118 (code word) contains two errors and is consequently capable of 
error correction. Key words w.sub.KL of such secondary classes N.sub.t are 
identified by a negative sign in FIG. 5. Such key words w.sub.KL occur 
only if there is a shift through more than seven bit positions, the 
probability of such a shift being very small. 
From the above descriptions, it will be evident that the probability that 
faulty synchronization is not recognized can be reduced by a method in 
accordance with the invention. Thus, distortion of messages caused by 
faulty synchronization can be avoided.