GB2124807A - Data transmission - Google Patents

Abstract

Individual data items (lines) in an ordered block (a field) of data, the block comprising a plurality of i digital data items, are labelled by transmitting with each data item a single bit which is the respective bit of a chain code having not less than i bits. At the receiver the chain code bits of n successive data items are detected, where 2<n>-1>/=i and these n bits compared with the bits of the chain code. These n bits will uniquely identify one position in the sequence. The data rate is reduced from the n bits required to transmit a serial number with each data item to only one bit. The bit can be transmitted in the form of selective complementing (inversion) of part of the data.

Description

SPECIFICATION Data transmission This invention relates to the transmission of individually-labelled data items in an ordered block of data comprising a plurality of digital data items.

Where such a block of data items is to be transmitted it is common practice to number the items sequentially with a code indicating the serial number of that item in the block. If for example, the block consists of 60 items, then six bit positions are required uniquely to identify the 60 items by means of an individual serial number. Where, however, there are constraints on the available data rate it would be highly desirable to provide a labelling system which did not require such a large number of bits to specify the individual items.

British Patent 1,299,602 and 1,299,427 together describe a system for use in an aircraft in which a plurality of receivers can be addressed from a central station over a common multiplex channel. The central station transmits over the channel a succession of bits of a chain code, each series of (say) six bits identifying an individual receiver. When a receiver detects its individual code being transmitted in this way it responds by transmitting back over the same channel certain data which it is storing representative of the positions of several manuallyoperable switches.

The present invention is defined in the appended claims to which reference should now be made.

The invention will be described by way of example with reference to the drawing, in which: Figure 1 is a block circuit diagram of a chain code generator in a labelling system embodying the invention, Figure 2 is a block circuit diagram of the corresponding part of an identification system embodying the invention using a chain code of 60 bits in length, and Figure 3 is a similar block circuit diagram for a system using a chain code of 625 bits in length.

A proposal has been made for a structured and ordered multiplex of data, primarily intended for carrying several digital sound channels on a subcarrier associated with a direct broadcasting by satellite television signal. The information transmitted is grouped into 'lines' and 'fields'. The data rate is 2,048 Mbit/s and each line contains 2048 bits and occupies 1 ms. A 'field' comprises 60 lines of data and occupies 60 ms. In order to allow line synchronisation ("framing") on start-up, on channel change, or following a disturbance, each line contains a fixed "framing word" pattern, provisionally a ten-bit sequence; identifying the beginning of a line. In order to establish the position of the lines within a field each line also contains a six-bit binary count which is incremented from line to line and is reset at a field boundary.As well as giving the field 'phasing' information, which is necessary for the recovery of auxiliary and control data, this six-bit count can be considered as an augmentation of the framing word. This 16-bit augmented framing word changes systematically from line to line so it is very unlikely to be imitated by any fixed or systematic variation in the data itself. It is, therefore, less susceptible to "false lock" than a conventional framing sequence.

Because of a requirement to provide six high-quality sound channels (each requiring 336 kbit/s), together with auxiliary data capacity of 1 200 bit/s per channel and supplementary control and labelling signals, only 1 6 bits per line are available for the line framing and field phasing information. However, a requirement has recently been expressed for this 16-bit group to include a fixed pattern containing at least 9 or 10 data transitions in order to facilitate a particular type of clock recovery technique. This implies a framing word longer than ten bits, and consequentially there is no longer room for a 6-bit line count.

This is therefore one example of the more general problem where digital data items in an ordered block or sequence of data require to be individually identified but due to data rate constraints there is insufficient room to give them separate serial numbers.

Fig. 1 illustrates apparatus 10 for providing a labelling sequence in accordance with this invention. The apparatus comprises a 6-bit shift register 1 2 and four logic gates connected as shown. The shift register has six stages A to F which at any instant each provide either a positive output (e.g. A) or a negative output (e.g. A) as is well known. An exclusive-OR gate 1 4 combines the outputs A and F so as to provide an output if one (but only one) of the A and F outputs is high. An AND gate 1 6 combines the logical functions ABCDEF for purposes to be described below. An AND gate 1 8 combines the logical functions ABCDEF so as to produce an output in the event that all six shift register stages should be zero (an abnormal occurrence).

Finally a three-input OR gate 20 combines the outputs of gates 14, 1 6 and 1 8 for application to the input or first stage of the shift register 1 2.

The labelling output 22 of the circuit can in principle be taken from any convenient point in the loop comprising the shift register 1 2 and gates 1 4 and 20, and as shown is taken from the first stage of the shift register. The output of gate 1 6 also provides a field sync. output 24 indicating the end of each block of data items, in this case each field of 60 lines.

The apparatus is based on the principles of a chaincode generator. These are well known but one useful work of reference is an IEE Monograph 392M by Heath, F.G. and Gribble, M.W.

entitled "Chain Codes and their Electronic Applications", July 1 960, (alternatively Proc. IEE, Vol. 108 C, pp 50-57, March 1961).

A chain-code generator consists in principle of n shift register stages the input to which is formed by logically combining two (or more) of its stages, one of these being the last stage. The generator can then be made continuously to produce a sequence of bits the length of which is 2"-1 bits, and in which all consecutive groups of n bits are different. (If they were not, the shift register would have an ambiguity as to which point it was at in the sequence).Because with a relatively small number of shift register stages it is possible to produce very long chains of bits before they repeat, such generators are commonly termed 'pseudo-random generators' A six-bit shift register will in this way produce a chain code of length 63 bits (2e1). To produce a sequence which occurs every 60 bits it is necessary to recognise the 60th state attained by the register and cause it at that point to revert to its first state. There is only one place at which the sequence can properly be broken to give a chain code of less then full length, (see the IEE Monograph referred to above). In the present case gate 1 6 recognises the state 100101 in the shift register.Gate 14 would normally provide a zero input to the shift register, but gate 1 6 provides an output so that the shift register skips part of its normal sequence. More generally, the gate 1 6 has the effect of complementing the output of gate 1 4 at the required state of the shift register. By appropriate alteration of the logical states applied to the input of gate 16, the sequence length can be altered to any other desired value less than 63.

Thus the apparatus of Fig. 1 provides a single-bit signal at the output 22. The sequence of 60 bits provided at the output will be as follows: ..11000 10111 10010 10001 10000 10000 01111 11010 10110 01101 11011 01001.

As can be seen on close inspection, each consecutive group of 6 digits (of which there are 60 groups in the repeated sequence) is different, i.e. each consecutive group of 6 digits occurs only once in the sequence.

In accordance with this invention, therefore, one bit from this sequence is transmitted for each line of the field. Given these labelling bits from any six consecutive lines, it is then immediately possible to tell at what point you are in the sequence. Thus a single bit serves to replace the six bits previously required, the consequential disadvantage being that at the receiver six lines must first be received before the line numbers are identifiable. This only increases the initial locking time by 5 ms in, at worst, 60 ms.

The single bit per line of the chain code may be appended to the framing word, which would then be of length 1 5 bits in the above example of the satellite multiplex proposal. For example the 16-bit group might be 1010 1011 0011 1 OOX, where Xis the chain code bit. This example has the desired nine transitions in the fixed data. Alternatively the chain code bit and its complement could be used, giving some redundancy and another transition, 1010 1011 0011 1 OXX.

Fig. 2 illustrates the part of a receiver 30 required to lock on to the chain code sequence. An input 32 is connected through a selector switch 34 to the first stage of a 6-stage shift register.

The shift register and other circuitry within the box S' on Fig. 2 are identical with the circuitry shown within the box S in Fig. 1, and are given the same references with primes added. The detailed interconnection of the gates is not shown in Fig. 2. The gates 14', 16' and 18' have their outputs combined by an OR gate 20', the output of which is applied as the other input to the switch 34. An exciusive-OR gate 36 receives the input signal and also the output of the gate 20'.

Initially the switch 34 is in the upper position shown. The labelling bits from the lines of a received signal are applied sequentially to the input 32, whence they are applied to the shift register 1 2'. After six bits have been received, the output of OR gate 20' should accurately predict the next incoming bit. Thus, after the register is full the inputs to the exclusive-OR gate 36 should always be the same and hence its output should be zero. When the correct locking of the sequence has been assured the switch 34 is moved to its lower position. Now the shift register runs independently of the incoming signal although the gate 36 checks that the two remain in step. If the gate 36 starts producing outputs, then the shift register has somehow become unlocked and the switch 34 is moved back to its upper position until the sequence is properly re-established. The shift register contents at any instant uniquely identify which line in the 60-line field has just been received. The line number can be decoded by use of a simple look-up table embodied in a read-only memory. The arrival of the last line in the sequence initiates a field sync. signal on the output 24'.

As the shift register 12' "flywheels", once it has been locked, independently of the input, a degree of immunity is provided against isolated transmission errors in the line count bit.

In this specification the term 'transmit' is used in a general sense to include storage and other signal processing which may not involve sending the signal over long distances.

In transmission systems such as that envisaged in the above example for satellite multiplexing, the data may be decoded consistently of inverted polarity (i.e. with 0's and 1's transposed) due to an ambiguity in the carrier phase recovery. Commonly therefore the system is constructed so as to respond equally well to complemented line framing and field phasing information, and this information must be formulated accordingly.

With such an arrangement a particularly efficient and rugged method of signalling the chain code bit is to complement the entire 16-bit framing word for any line when the corresponding chain code bit is set to 1. The circuitry needed to recognise and respond to this method of signallling would, in general, represent an additional complication but, as just noted, this particular application requires the ability to respond to a complemented framing code in order to resolve ambiguity in the data demodulator. When using this method, the chain code must be such that it is not imitated by its complemented sequence. This is equivalent to saying that in the circuit of Fig. 2, with the switch 34 in the upper position, will indicate mostly 'errors' when presented with the complemented sequence. The 60 bit code given above generated by the circuit of Fig. 1 satisfies this requirement.In steady-state operations the 'locked slave' generator at the receiver may be used to restore the conventional polarity of the 16-bit framing word in order to simplify subsequent operations dependent on a regular framing pattern.

By encoding the chain code or line count bit as a reversal of the framing word, all 1 6 available bits can be used for the framing word, in place of a 10 bit code in the conventional system. This then allows the requirement of 9 data transitions in the framing sequence to be met.

While the description has been given in terms of fields of 60 lines, other numbers are, of course, possible. In particular an 80-line field may be of interest. This would require 7-bit shift registers. A letter in IRE Transactions on Electronic Computers April 1 962 pages 285-6 by BRYANT, HEATH and KILLICK entitled "Counting with Feedback shift Registers by Means of a Jump Technique" supplements the IEE Monograph mentioned above in providing further details including a general method for determining how a chain code may properly be shortened from its maximal length.

The system could possibly be used to label the lines of a television field, but for normal purposes the bandwidth saving would not be significant in that instant. However, an example of a 625-bit chain code is as follows:1100000101 0110110011 0000110101 1011101000 1010111111 0100011100 1101110010 1000110100 0000110010 0100010000 0100110110 1001111001 1010101100 0010111011 0100011000 0100111111 1011100011 1100000011 1011011000 1010001001 1001000001 1010010011 1101111100 0101010110 1000010100 0000010110 1101111001 1110001000 1111110110 0011101011 0101000011 0011011000 0011000000 0011011011 0101110101 1110000101 0100100001 0110010011 0000010001 0010000001 0000000001 0010010011 0100110101 1111001100 0111110010 0011101111 1100001110 0000001111 1111110001 1100010011 1011001010 1110111101 0100011110 1001010100 0001011111 1110101010 1011110100 0011101001 0001100101 1010110011 1101011000 1100111111 00101 The sequence is read left to right, top to bottom. Every bit is the module-two sum of the third and tenth previous bits, except the very first bit which is complemented. Every ten-bit combination which appears in the sequence appears once only, so it can be used to specify a point in the sequence. The division into blocks of ten is only to assist counting through the sequence.

A logic circuit to generate the above chain code is shown in Fig. 3. A ten-bit register 12" is needed in any case to store a count of 625, and the additional logic gates are fewer than in a conventional counter. Delayed versions of the output are available from later stages of the shift register. The gate 18" is only required if the register may start in the all-zero state, which otherwise is self-perpetuating.

As with Fig. 2, the chain-code generator is synchronised to an incoming chain-code by, in the first instance, aplying the input directly to the shift register using the switch 34. If the code is correctly received, and the same as that programmed by the generator feedback function, the error monitor, which compares the feedback with the incoming signal, will show continuous identity after, at most, ten clock periods. Left in this mode isolated incoming errors will produce three outputs from the error monitor, and a false 'count' for ten clock periods. But as soon as 'confidence' is established the switch 34 is used to close the feedback loop whereupon the generator 'flywheels' and the error monitor gives a one-for-one indication of incoming errors.

Because of the near-ideal autocorrelation function of a chain code it is straightforward to devise a control strategy to distinguish between poor reception while locked (even say, with a 1 in 4 error rate) and loss of lock.

As the information about the position within the chain code is complete as soon as ten consecutive bits are known this approach gives a fast a nearly constant lock-up time, on a good signal. In comparison with a 625-bit sequence where there is a unique event only for a brief part of the period, the chain code offers a lock-up which is on average about thirty times faster and more than fifty times faster in the worst-case starting conditions.

Although it may be argued that the response time of r.f. and i.f. circuits to channel change is the dominant delay in signal recovery, this will not always be so. The techniques of frequencyagile communications depend on lightweight low-power semiconductor technology and these can be expected to appear in domestic equipment in due course. The critical delay in a 'searching' receiver will then be the lock-up time of the multiplex.

One benefit of chain-code synchronisation is that the information is scattered, but any portion contains information about the whole. The fast and constant lock-up time is ideally matched to data multiplex systems where the 'service' information is spread uniformly with time. It will also be of value when solid-state displays or intermediate frame buffers, are used in television receivers, since an accompanying television signal can then be used immediately without waiting for the next frame interval.

Claims (11)

1. A method of transmitting individually-labelled data items in an ordered block of data containing a plurality of i digital data items, the method comprising transmitting together with each data item an indication of the value of a respective element of a chain code having not less than ielements.

2. A method according to claim 1, in which one bit of the chain code is transmitted with each data item.

3. A method according to claim 1, in which at least a portion of the data item is selectively complemented in accordance with the value of a respective bit of the chain code to provide an indication thereof.

4. Apparatus for transmitting individually-labelled data items in an ordered block of data containing a plurality of i digital data items, the apparatus comprising a chain code generator for generating a chain code having not less than i elements, and means for transmitting together with each data item an indication of the value of a respective element of the chain code.

5. Apparatus according to claim 4, in which the associating means transmits one bit of the chain code with each data item.

6. Apparatus according to claim 4, in which the associating means selectively complements at least a portion of the data item in accordance with the value of a respective bit of the chain code to provide an indication thereof.

7. Apparatus according to claim 4, 5 or 6, in which the chain code generator'provides a further output which recurs once on each cycle of the chain code.

8. A method of identifying individual data items transmitted in an ordered block of data comprising a plurality of i digital data items and labelled by the method of claim 1, comprising detecting at least n transmitted elements of the chain code, where 2"-1 is not less then i, and comparing the n detected elements with the elements of the appropriate known chain code.

9. Apparatus for identifying individual data items transmitted in an ordered block of data comprising a plurality of i digital data items and labelled by the method of claim 1, comprising detection means for detecting at least n transmitted elements of the chain code, where 2"-1 is not less than i, and comparison means for comparing the n detected elements with the elements of an appropriate stored chain code.

10. Apparatus according to claim 9, in which the detection means comprises a chain code generator having shift register means which can be fed selectively with incoming data or with the output of a logic gate which combines the outputs of at least two stages of the register means, and further comparison means for comparing the incoming data with the output of the logic gate.

11. A method of transmitting data items in an ordered block of data, substantially as herein described with reference to Fig. 1.

1 2. Apparatus for transmitting data items in an ordered block of data, substantially as herein described with reference to Fig. 1.

1 3. A method of identifying data items in an ordered block of data, substantially as herein described with reference to Fig. 2.

1 4. Apparatus for identifying data items in an ordered block of data, substantially as herein described with reference to Fig. 2.