GB2029170A - Error detection and correction system - Google Patents

Abstract

An error detection and correction system for a data transmission system subject to high error rates, e.g. as bad as 1 in 10<2> of the data bits, is described, in which both majority decision techniques and forward error correction are used. The data D is coded into blocks with parity bits P, Q generated in two-dimensional manner from the data bits, the parity bits being distributed throughout the block instead of all grouped together. Each data block is sent four times, and on reception each block is checked using parity techniques and the errors counted. The worst block is discarded and the other three blocks are subjected to majority de cision votes on a bit-by-bit basis. The block thus derived is then subjected to error detection techniques with block repetition if needed. The reply bits R used to advise the source terminal as to whether a block has been correctly received or not are distributed throughout the block to minimize their vulnerability to burst error conditions. Control bits C and address bits A have their own parity in addition to the overall two-dimensional parity. <IMAGE>

Description

SPECIFICATION Error detection and correction system This invention relates to data transmission systems of the type in which error detection and correction facilities are provided.

The basic principles of an ARQ system for transmitting data between two equipments involves encoding the data into multi-bit blocks at the source equipment, each such block including an error detecting portion.

This latter portion is derived from the data bits by the operation thereon of a preset logical process. The destination equipment, often known as the sink equipment, checks each block for correct transmission, and if the check indicates that the block has been correctly received the data content is accepted. If the check shows that the block has been erroneously received, the block is rejected and a request is made for a repeat transmission of that block.

An object of the present invention is to produce an error detection and correction system for use in a high error rate environment.

According to the present invention there is provided a data transmission system, in which the data to be conveyed is transmitted in digital form in multi-bit blocks each of which includes data bits and checking bits derived as a result of processing operations on the data bits, in which each block of data to be conveyed is transmitted an even number N of times, where N is at least four, in which on reception each block is checked to ascertain the number of errors in that block and for each block which is thus received N times the block with the highest number of errors is discarded, in which if two or more blocks have the same number of errors and that number is the highest number of such errors only one of those blocks is discarded, and in which the other (N-l) versions of the same block are subjected on a bit-by-bit basis to a majority decision vote to produce a usable version of the original block.

Such a forward error correction arrangement can be used alone, or it can be used in conjunction with a so-called adaptive error correction arrangement. Therefore according to the present invention, there is further provided a data transmission system, in which the data to be conveyed is transmitted in digital form in multi-bit blocks each of which includes data bits and checking bits derived as a result of processing operations on the data bits, in which each block of data to be conveyed is transmitted four times, in which on reception each block is checked to ascertain the number of errors in that block and for each block which is thus received four times the block with the highest number of errors is discarded, in which if two or more blocks have the same number of errors and that number is the highest number of such errors only one of those blocks is discarded, in which the other three versions of the same block are subjected on a bit-by-bit basis to a majority decision vote, to produce a usable version of the original block in which the usable version thus obtained is further checked for errors not eliminated by the preceding operations, in which if the result of said further check indicates that no errors are present, then the block is accepted as valid, and in which if the further check indicates that the block still contains errors that block is rejected as invalid and a repeat request signal is sent to the originating data terminal, the reception of the repeat request signal at the originating terminal causing the rejected block to be repeated, which repeated block is checked again on reception thereof at the receiving data terminal.

The arrangement to be described herein was designed for use in a system in which the bearer circuit has a transmission speed of 1 6 Kbits/second over a channel which may include a satellite link and is subject to error rates of 1 in 102 and 1 in 103. The required overall data rate was up to 9.6 Kbit/second with a residual error rate of better than 1 in 108.

An embodiment of the invention will now be described with reference to the accompanying drawing in which Fig. 1 represents schematically the data bit block structure, and Fig. 2 is a block diagram of error detection and correction equipment embodying the present invention.

First we describe the block structure, see Fig. 1, with special reference to operations at which the error rate is less than 1 in 103, the other parameters being as indicated above.

At each end of the system we have a data terminal equipment DTE connected via a data circuit terminating equipment DCE to the digital transmission channel, which may be a wire or radio link, in the latter case possibly including a satellite link.

When a message is to be sent, the DCE at the sending end receives that message from the DTE, and it assembies the data into blocks for onward transmission to the "sink" DCE.

The blocks thus assembled are stored in the source DCE until a reply is received from the sink DCE to the effect that the block has been correctly received (ACK). The block to which the ACK signal relates can then be deleted from the store. However, if the block is not correctly received at the sink DCE, the latter sends back a signal (NACK) to that effect as a result of which the normal data transmission is stopped and the queried block is retransmitted. The source DCE "knows" which block is referred to by the received ACK or NACK as it "knows" the loop delay, the determination of which will be described later.

Storage at the DCE for the above purpose is 32 blocks, or 256 blocks for connections which may be set up via a satellite link, since loop delay is greater in such a case. If the error rate is such that the limit of the storage is reached, this is indicated to the DTE via a connection extending from the DCE to the DTE. This indication stops transmission until storage becomes available once more.

If no data is available for transmission, the DCE transmits a dummy block.

The sink DCE checks the blocks which it receives for correct transmission: if a block is correctly received it is stored for onward transmission to the associated DTE and an ACK signal is sent back to the source DCE. If the block is erroneously received, it is discarded and a NACK reply is sent to the source DCE where it, as already mentioned, causes the discarded block to be repeated.

Data accepted as correct is passed from the sink DCE to the associated DTE in the order defined by the block address bits via an output connection. If continuous transmission is not possible due to the non-correct receipt of a block or blocks, an additional connection is set to an OFF state until a block is correctly received.

Each block as transmitted consists of 256 bits, as follows: (i) 5 Reply bits (R1-R5) (ii) 3 Control bits (C1-C3) (iii) 9 Address bits (A1-A9) (iv) 208 data bits (D1-D208) (v) 30 checking bits (P and Q bits) (vi) 1 framing bit (F) The block is shown in Fig. 1 arranged as a 16 x 16 array from which it will be seen that the five reply bits are distributed throughout the array. Of the checking bits, P1 to Pal 5 are odd parity bits for the data rows and Q1 to Q15 are odd parity bits for the data columns.

Such a block is sent to the DCE in row order.

To generate the checking bits, the reply, control, address and data bits are arranged in a 15 X 1 5 array. Then a checking bit is added to each row and column, each such checking bit being so chosen as to maintain odd parity over the 1 6 bits of the row or column. Such a checking pattern detects the following combinations of errors: (a) all odd numbers of errors within the block.

(b) all combinations of double errors.

(c) any error burst not exceeding 1 7 bits.

(d) a large percentage of other errors.

In the presence of a channel error rate of less than 1 in 103, the theoretical undetected error rate, assuming a random distribution of error, is less than 2 in 10'0.

The framing bit F is added in, and its significance will be referred to later.

We now consider the reply bits R1 to R5, which, as can be seen from Fig. 1 are separated. Thus R1 is the first bit of the block and the others appear respectively at the beginnings of the fourth, seventh, tenth and thirteenth row. Such a distribution of the reply bits gives a measure of protection against error bursts of long duration. Their usage is subject to the following: (a) The probability that a transmitted NACK will be translated into a received ACK by error on the bearer circuit must be negliglible, otherwise data element integr ty cannot be guaranteed since if such an error should occur data bits could be lost.

(b) Similarly the probability that a transmitted ACK will be thus converted into a received NACK must be low, or the system throughput will be reduced due to unneccessary block repetition thus caused.

To meet the above considerations the sink DCE sets R1-R5 to 01100 for ACK, and to 10011 for NACK.

On reception of a reply block from the sink DCE, the source DCE assumes the reply to be ACK if R1-R5 are 01100 and if no more than six of the block checking bits of that reply bit are in error. The source DCE assumes the reply to be NACK if R1-R5 are received as 01100 (which would normally mean ACK) if the number of errors in the block checking bits was seven or more. In such case the channel would be assumed to be sufficiently bad not to trust the ACK signal. Note that relatively small numbers of errors in the reply block do not invalidate ACK, since if an ACK was taken to be a NACK with such small number of errors, then again the system throughput would be too low.

Note that if R1-R5 are received as other then 01100 it is accepted by the source DCE as NACK.

The control bits C1-C3 are used, inter-alia, to indicate the functions of the block, as follows: C1-C3 Function 001 Loop delay measurement 010 End loop delay measurement 100 Dummy block 111 Data block The "intelligence conveying" portion of C1-C3 is the first two bits, C3 being set to give odd parity for the control bits. Hence the block is rejected by the sink DCE if it finds a parity failure in C1-C3. This additional security over the row and column check bits is provided, as an undetected error in C1-C3 could destroy data element integrity.

In the address bits Al -A9, A9 is set to give odd parity for these bits, a block being rejected by the sink DCE if there is a parity failure in these bits. Again an undetected error could cause data element integrity to be destroyed. The contents of the address bits according to function are: (i) Loop delay measurement: Al to A8 are used, in effect, as a counter, with Al to A8 incremented by 1 each time a block is sent by the source address.

(ii) End loop delay measurement: received address (see below).

(iii) Dummy block: Al to A8 are 00000000 (iv) Data block: Al to A8 are the address appropriate to the data bits.

Each block contains 208 data bits, which coantain DTE data when the control bits are set to 111, and are set to 0 for all other functions. Note that if a data block with less than 208 data bits has to be sent, the "vancant" places use 0 stuffing bits.

The last bit of the block, bit F in Fig. 1, is used for framing and synchronisation on a master-slave basis, the calling DCE being master.

A data frame is 8 blocks, one framing bit per block, and the frame sync pattern is 10110010. Frame sync is deemed to have been obtained when three successive sync patterns (or their inverse) have been received correctly. In almost all cases, sync will be attained in not more than five frame periods, excluding propagation delay, for a bearer channel error rate less than 1 in 103.

Frame sync is deemed to be lost at the beginning of a connection, or during a connection when seven successive sync patterns are received in error. When a DCE deems that received sync is lost it signals this state to the other DCE by inverting its sync patterns, which thus becomes 01001101. To ensure that data bits do not simulate a sync-pattern during resynchronisation, all other bits in the frame are set to 0, which should cause all error checks to fail. Transition in either direction between a normal and an inverted syncpattern only occurs at the beginning of a frame.

When a DCE receives an inverted syncpattern it sets all bits exceptthe sync bits in the frame which it is going to send to 0.

When, after a period of loss of sync by either DCE, sync is attained by both DCE's, the master DCE initiates loop delay measurement. To do this it sets C1-C3 to 001, and increments A1-A8 for each block transmitted.

On receipt of this 001 code, the slave DCE retransmits the received address back to the master DCE with the control bits at 010.

The master DCE measures loop delay by calculating the difference in value between bits A1-A8 of the address bits between the received address and that currently being transmitted. It contains this measurement until it has calculated two values which agree, when it signals "end of loop delay measurement", i.e. C1-C3 = 010, to the slave DCE.

When it receives C1-C3 = 010, the slave DCE measures loop delay in the same way as above but with the roles of master and slave reversed. When the slave DCE has completed the measurement it sends C1-C3 = 010 to the master, and when the latter receives this signal it commences information transfer.

On receipt of a dummy block or a data block, the slave DCE commences information transfer.

Fig. 2 is a block diagram of the error detection and correction equipment at a DCE.

Transmission speed between DCE's is 1 6 Kbit/sec., and for channel error rates of 1 in 102, the information rate is 2.4 Kbit/sec. For such error rates, the residual undected error rate is better than 1 in 108.

During data transfer and loop delay measurement, each block (excluding the framing bit) is transmitted in four successive block positions, i.e. positions 1, 2, 3 and 4 or positions 5, 6, 7 and 8 of the frame. The sink DCE counts the number of errors in the block checking code for each of the four versions of the same block, and the block with the most errors is discarded. This reduces the risk that a block affected by an error burst will interfere with the majority voting which follows. If two blocks have the most errors, choice as to which to reject is random.

After rejection of the worsft block, forward error correction using majority vote error detection and correction on a per-bit basis is then applied to the remaining three blocks, excluding the framing bit but including the checking bits. The resultant corrected block has a mean error rate of less than 1 in 103, and is used for the so-called adaptive error correction, in which the method already briefly described and using the ACK and NACK signals, with repeats of queried blocks is used.

In the block diagram of Fig. 2, the error detection and correction circuitry is between an interface 1, which gives access to the DTE, and a modem 2, which is the interface with the bearer channel.

Data blocks from the DTE pass via the interface 1 to a store 3, via its input/output equipment 4, and this latter equipment passes the data on to a block encoding unit 5 from which it passes via a sync insertion unit 6 to the modem 2. Sync control is effected from the block 7, which also controls the loop delay measurement unit 8, whose output goes via a gate 9 to the block 6.

Overall control of opeations, including preventing the receipt of data from the DTE when the store 3 is full is effected by the ARQ control unit 1 0. This also stops data transfer to the DTE under error conditions.

We now consider data coming into the equipment via the modem 2. This goes initially to a clock circuit 11 to make sure that the bit sync between the equipments involved in the connection is maintained, and to a sync pattern detector 1 2 used to maintain and reestablish if necessary frame sync in the manner already described briefly.

The received data passes via a majority voting circuit 13, whose output passes to a block decoding circuit 14 when the block is found valid. Note that some block decoding is needed to establish block validity. These decoded blocks then pass to the store 15, with its input/output equipment 1 6 from which the blocks reach the interface.

The system described has been optimised for operation with a transmission channel error rate of 1 in 103, and the block length and structure were chosen to give maximum information throughput at this error rate, within practical constraints. The system is also required to operate with an error rate of 1 in 102, and it is for this reason that the combination of majority voting and forward error correction was chosen. This gives an information throughput of 2 4 K/bs, with a theoretical residual undetected error rate of better than 1 in 1011, for a transmission channel error rate of 1 in 102. This assures that the speed between DCE's is 16 Kb/sec.

The most vulnerable part of the system is the reply as the effect of an erroneously received ACK would be that the source equipment ceases attempting to transmit the related block, and data element integrity would be violated.The dispersal of the reply bits, plus the actual codes used for ACK and NACK provide security in this respect.

The error detection code used, i.e. twodimensional parity, has a higher immunity to burst error conditions than to random error conditions, which is valuable when the channel is subject to error bursts.

The control and address bits have been afforded additional security by virtue of their own parity bits since an error in such bits could cause multiple errors and could cause data element integrity to be violated. By contrast, an undetected error in the data portion would only result in one error in the decoded information.

Claims (12)

1. A data transmission system, in which the data to be conveyed is transmitted in digital form in multi-bit blocks each of which includes data bits and checking bits derived as a result of processing operations on the data bits, in which each block of data to be conveyed is transmitted an even number N of times, where N is at least four, in which on reception each block is checked to ascertain the number of errors in that block and for each block which is thus received N times the block with the highest number of errors is discarded, in which if two or more blocks have the same number of errors and that number is the highest number of such errors only one of those blocks is discarded, and in which the other (N-l) versions of the same block are subjected on a bit-by-bit basis to a majority decision vote to produce a usable version of the original block.

2. A data transmission systems, in which the data to be conveyed is transmitted in digital form in multi-bit blocks each of which includes data links and checking bits derived as a result of processing operations on the data bits, in which each block of data to be conveyed is transmitted a number of times, in which the versions of the blocks as received are subjected on a bit-by-bit basis to a major ity decision vote to produce a usable version of the original block, in which the usable version thus obtained is further checked for errors not eliminated as a result of the preced ing operations, in which if the result of said further check indicates that no errors are pre sent, then the block is accepted as valid, and in which if the further check indicates that the block still contains errors that block is rejected as invalid and a repeat request signal is set to the originating data terminal, the reception of the repeat request signal at the originating terminal causing the rejected block to be repeated, which repeated block is checked again on reception thereof at the receiving data terminal.

3. A data transmission system, in which the data to be conveyed is transmitted in digital form in multi-bit blocks each of which includes data bits and checking bits derived as a result of processing operations on the data bits, in which each block of data to be conveyed is transmitted four times, in which on reception each block is checked to ascer tain the number of errors in that block and for each block which is thus received four times the block with the highest number of errors is discarded, in which if two or more blocks have the same number of errors and that number is the highest number of such errors only one of those blocks is discarded, in which the other three versions of the same block are subjected on a bit-by-bit basis to a majority decision vote, to produce a usable version of the original block, in which the usable version thus obtained is further checked for errors not eliminated by the pre ceding operations, in which if the result of said further check indicates that no errors are present, then the block is accepted as valid, and in which if the further check indicates that the block still contains errors that block is rejected as invalid and a repeat request signal is sent to the originating data terminal, the reception of the repeat request signal at the originating terminal causing the rejected block to be repeated, which repeated block is checked again on reception thereof at the receiving data terminal.

4. A data transmission system as claimed in claim 2 or 3 in which each block to be conveyed also includes address data indicative of the intended destination of the block to which it relates and control data appropriate to the function of the block to which it relates, and in which the group of bits which conveys the address data and the control data are each provided with their own parity.

5. A data transmission system as claimed in claim 4, and in which the block functions specifiable by said control data include loop delay measurement.

6. A data transmisssion system as claimed in claim 5, and in which for loop delay measurement repeated transmission of a block is effected from one terminal to another, with the address data bits used as a counter to count the number of blocks sent before a first of those blocks is returned to said one terminal.

7. A data transmission system as claimed in claim 6, and in which when loop delay measurement is effected said measurement is effected twice, once from each end of the link.

8. A data transmission system as claimed in claims 2, 3, 4, 5, 6 or 7, and in which the repeat request signal is conveyed by a set of bits which is distributed at intervals throughout the data block, and in which if said further checks indicated that no error was present the bits usable to convey repeat request signals are used to convey an acknowledge signal.

9. A data transmission system as claimed in any one of the proceding claims, in which the parity bits are derived by temporarily storing the data bits in a two-dimensional coordinate array whereafter for each row and for each column there is derived a single parity bit.

10. A data transmission system as claimed in claim 9 and in which said parity bits are distributed throughout the block.

11. A data transmitting terminal for use in a system as claimed in any one of claims 1 to 10.

12. A data receiving terminal for use in a system as claimed in any one of claims 1 to 10.

1 3. A data transmission system, as described with reference to the accompanying drawings.