Transmission system via communications protected by an error management code

A data transmission system wherein data to be transmitted is supplied to an encoding device (5) which comprises a data analysis circuit (35) for producing a parity code and an output circuit (32) for assigning the parity code to the input data so as to convert it into protected data for transmission. The data analysis circuit includes: (i) a serial-to-parallel converter (30) for converting the input data into "n" parallel data streams, the bits in each stream being at instants which are multiples of n.times.T, where T is the bit period of the input data; (ii) "n" cascade combinations of delay elements, each cascade delaying one of the "n" parallel-converted data streams by time periods which are multiples of n.times.T, each cascade having tapping points following certain ones of the delay elements therein; and (iii) combining circuits (GR1, GR2, OE) having inputs connected to tapping points of each of the cascade combinations and which derive the parity code.

FIELD OF THE INVENTION 
The present invention relates to a data transmission system wherein bit 
strings are protected by an error management code which takes into 
account, at least twice, the value of each bit. Such system comprises an 
encoding device which includes a data analysis circuit for producing an 
error management code on an output, and an output circuit for producing 
protected data on an output access by assigning said error management code 
to the input data. The system further comprises a decoding device which 
has a receiving access for receiving the transmitted protected data, an 
error processing circuit, and an output access for producing recovered 
data. 
Such a system finds important applications, particularly in the field of 
data transmission and also in the field of data recording, wherein the 
recording medium, for example, magnetic tape or compact disc, is then 
considered a transmitting means. 
The present invention also relates to an encoding device and a decoding 
device suitable for such a system. 
BACKGROUND OF THE INVENTION 
A means for error protection of transmitted information streams is 
described in U.S. Pat. No. 4,796,260. Therein an error correction code is 
described which applies to blocks of bits. However, that is a disadvantage 
when one wishes to process the data at a high rate, as a block cannot be 
processed until the entire block has been received. 
SUMMARY OF THE INVENTION 
The present invention provides a system of the aforesaid type in which the 
processing is performed continuously an successive string of bits. 
Therefore, such a system is characterized in that the data analysis circuit 
comprises: 
serial-to-parallel converting means, which have an input for receiving data 
and "n" outputs for producing the data at instants which are multiples of 
n.times.T, where T is the bit period; 
"n" cascade combinations of delay elements for delaying the 
parallel-converted data by time periods which are multiples of n.times.T, 
which cascade combinations have tapping points at each of the delay 
elements; and 
combining circuits which have inputs connected to at least two tapping 
points of all the cascade combinations to produce said error management 
code. 
These and other aspects of the invention will be apparent from and 
elucidated with reference to the embodiments described hereinafter.

DESCRIPTION OF PREFERRED EMBODIMENTS 
In FIG. 1, which shows a transmission system according to the invention, 
reference 1 indicates an input access for a bit string. This string is 
processed by an encoding device 5 to produce, on an output access 10, 
another bit string in which are inserted bits of an error management code. 
This string forms the protected data. A transmission means 12 (not shown 
because it is unimportant for the measures of the invention), transmits 
these protected data to the receiving access 15 of a decoding device 20 
which produces the recovered data on an output access 22. 
Within the framework of the described example, the error management code is 
a simple parity code. Each bit of the bit string will at least twice be 
involved in a parity calculation, so that it becomes possible to correct 
some transmission errors. 
FIG. 2 shows an embodiment for an encoding device according to the 
invention. It comprises first of all a serial-to-parallel converting 
circuit 30 which converts the series of bits received on access 1, which 
have a frequency equal to 1/T, into "n" bit strings. To simplify the 
explanation, the number "n" has been taken equal to "4". These four 
strings are rendered available on wires F1, F2, F3 and F4 branching off 
from the outputs of circuit 30. Each of these wires is connected to an 
input of an output circuit 32 via a data analysis circuit 35. The data 
analysis circuit 35 is formed by four cascade combinations of delay 
elements connected each to the first of the wires F1 to F4: one cascade 
combination comprises the delay elements T1,1 to T1,7 and is connected to 
wire F1, the second combination is of elements T2,1 to T2,7 and is 
connected to wire F2, the third cascade combination is of elements T3,1 to 
T3,7 and is connected to wire F3, and the fourth cascade combination is of 
elements T4,1 to T4,7 and is connected to wire F4. Each of these delay 
elements causes a delay equal to n.times.T. The output circuit 32 
transforms the signals on its inputs so as to produce them on the output 
access 10 by appropriately processing them to adapt them to the 
transmission medium 12. 
To perform the parity calculation in accordance with the invention, the 
analysis circuit 35 comprises combining circuits. They are formed by two 
groups of "EXCLUSIVE-OR" operators GR1 and GR2 and an "EXCLUSIVE-OR" gate 
OE. The first group GR1 is formed by three EXCLUSIVE-OR gates 01,1 01,2 
and 01,3. The inputs of gate 01,1 are connected to the output of delay 
element T1,3 and that of delay element T2,2, which in practice represents 
the middle of the cascade combination; the inputs of gate 01,2 are 
connected to the output of gate 01,1 and that of delay element T3,1, and 
the inputs of gate 01,3 are connected to the output of gate 01,2 and the 
input of element T4,1. The second group is formed by three "EXCLUSIVE-OR" 
gates 02,1, 02,2 and 02,3. The inputs of gate 02,1 are connected to the 
output of delay element T1,4 and that of T2,5, the inputs of gate 02,2 to 
the output of gate 02,1 and that of element T3,6 and the inputs of gate 
02,3 to the output of gate 02,2 and that of element T4,7. The gate OE 
produces the combined parity according to the invention. Therefore, its 
inputs are connected to the output of the gate 01,3 and that of gate 02,3. 
The output circuit 32 also provides the transmission of this parity 
information. 
Thus for each successive cascade combination, the gate input connections 
are shifted one delay element forward and one delay element back. 
FIG. 3 shows an embodiment of a decoding device according to the invention. 
It is formed first of all by a distributing circuit 40 for distributing 
the transmitted data received at access 15. This circuit produces on wires 
G1 to G4 the transmitted information streams and on a wire Pt the 
transmitted parity code processed by the analysis circuit 35 of the 
encoding device 5. A second analysis circuit 42, which has the same 
structure as the circuit 35, produces a local parity P1 which is compared 
with the transmitted parity Pt and relates to the same bits. The result of 
this comparison is applied to an error correction circuit 45 which then 
corrects the errors in the bits coming from the wires G1 to G4. An output 
circuit 50 then produces on the access 22 the information streams for the 
user. 
The error correction circuit 45 is formed by four cascade combinations of 
delay elements which combinations comprise each the following delay 
elements: TT1,1 to TT1,5 for the first combination, TT2,1 to TT2,5 for the 
second combination, TT3,1 to TT3,5 for the third combination and TT4,1 to 
TT4,5 for the fourth combination. Various EXCLUSIVE-OR gates P1 to P4 are 
inserted into the cascade combinations to change the value of the bits. 
Therefore, gate P1 has one of its inputs connected to the output of 
element TT1,5 and its output is connected to circuit 50, gate P2 has one 
of its inputs connected to the output of element TT2,4 and its output to 
the input of element TT2,5, gate P3 has one of its inputs connected to the 
output of element TT3,3 and its output to the input of element TT3,4 and 
gate P4 has one of its inputs connected to the output of element TT4,2 and 
its output to the input of element TT4,3. The other inputs of gates P1 to 
P4 are connected to the outputs of the AND gates A4 to A1, respectively. 
One input of all these gates is connected to the output of a delay element 
TU8 which is the last of a series combination of delay elements TU1 to TU8 
connected to the output of an EXCLUSIVE-OR gate Pc which compares parities 
on the output P1 with the parity Pt produced in circuit 35. 
Thus, the gates A1 to A4 produce a "1" on their output when two faulty 
parity codes are applied to their input; it is thus possible to correct 
the bit that has generated these two faulty parities. 
THEORETICAL CONSIDERATIONS ON THE INVENTION 
The data to be encoded, which are supposed to be available in serial form 
are converted to parallel form in n strings available on the wires F1 to 
Fn, which is shown in FIG. 4, in which the bits of the n parallel strings 
are shown by small circles. Thereafter, a simple parity calculation is 
made of the words of 2n bits defined in the paths Tr1 to Tr5 shown. The 
parity bits Pr1 to Pr5 obtained are symbolized by small squares. 
An arbitrary bit of the data is always at the intersection of two "paths", 
and of two paths only. This means that in the case of erroneous 
transmission of an information bit, there will be a divergence called 
parity (obtained when the transmitted redundancy bits are compared with 
those which will be recalculated on reception according to the same 
principle), of two parity bits (redundancy). The "paths" associated with 
these two parity bits, which paths are known in principle, make it 
possible to localize the faulty data bit at their intersection and to make 
the correction by inverting its value. This is the case, for example, for 
the parity bits Pr4 and Pr5 which are represented in black squares and do 
not correspond to those that have been transmitted (after calculation on 
reception). The result will be that the bit "B" located at the 
intersection of 2 paths Tr4 and Tr5 connected to Pr4 and Pr5 has been 
subject to a transmission error. 
CODE PROPERTIES 
a This code strongly looks like the block codes, although it is not 
possible to actually define the block (the blocks are interleaved). 
b The limit of the code is reached when 2 bits belonging to a same "path" 
are faulty. This makes it possible to estimate the approximate value of 
the effectiveness of the correction. 
If the data are divided into "n" strings, the redundancy is 1 bit for n 
data bits (overhead of n+1/n-1)100 in %). 
When there is a transmission error ratio of P (bit error probability before 
correction), the probability of having 2 faulty bits belonging to one and 
the same path is about 2nP.sup.2 (with low P). 
Compared with the Hamming code for which m redundancy bits are added to 
blocks of 2.sup.m -1 information bits and for which the correction limit 
corresponds to about 2.sup.m P.sup.2 (for large m), a same error ratio 
after correction is supposed for the two codes: 
Hamming: 2.sup.m P.sup.2 .fwdarw.redundancy.apprxeq.100 m/2.sup.m in % 
interleaved parity: 2nP.sup.2 redundancy.apprxeq.100/n in % 
if 2.sup.m P.sup.2 =2nP.sup.2 n=2.sup.m-1 : 
redundancy of the Hamming code: 100 m/2.sup.m =R.sub.H 
redundancy of the interleaved parity code: 100/2.sup.m-1 =R.sub.p 
R.sub.H /R.sub.p =m/2. 
In general, the parameter m for a Hamming code is selected large enough 
(m.gtoreq.5) and the equation R.sub.H /R.sub.p =m/2 shows that the 
redundancy of an interleaved parity code as proposed is clearly lower with 
an equivalent correction effectiveness. Conversely, with equivalent 
redundancy: 
EQU 100 m/2.sup.m =100/nn=2.sup.m /m 
the error ratios after correction are respectively: 
P.sub.H =2.sup.m P.sup.2 (Hamming) 
P.sub.p =2nP.sup.2 =2.sup.m+1 /m P.sub.2 (interleaved parity) 
P.sub.H /P.sub.p =m/2 
Thus, there may be deduced herefrom that with equivalent redundancies the 
error ratio after correction by a Hamming code is m/2 times higher than 
for an interleaved parity code. 
VARIANT 
There exists another class of paths which have identical properties: see 
FIG. 5A and 5B, which show two types of paths TrA and TrB which make it 
possible to obtain two parity bits PrA and PrB. These paths need a small 
memory. 
OBSERVATION 
There is shown in FIG. 6 that the paths of the type shown in FIG. 4 are 
favourable for the correction of error "packets". Thus, divergencies of 
parity PPr1 to PPr8 relating to paths TrP1 to TrP8 make it possible to 
correct the packet B.sub.1 to B.sub.4 of successive erroneous bits. 
Without complex computation, this property is not satisfactory for a block 
code. It will become more effective as n is greater.