CODING SCHEME FOR SERIAL DATA COMMUNICATIONS

This invention relates to a coding scheme, and in particular to a coding scheme that can be used when transmitting data and embedded information in a single data stream.

There are many situations in which it is necessary to transmit data from one electronic device to another. It may be advantageous to use a serial interface, in which the data for transmission is converted into a sequence of binary values, which are then transmitted over the interface.

In such situations, the use of a coding scheme can allow additional features into the data stream during transmission.

Various coding schemes are already known. Based on the fact that the original user data is provided in data bytes, each containing 8 data bits, coding schemes are known in which the data bits from one or more data bytes are manipulated in some way to produce encoded data containing one or more additional data bits. For example, US Patent No. 6,229,458 describes a coding scheme in which a data word made up of four data bytes (that is, 32 data bits) is encoded to form an encoded data word made up of 34 data bits.

According to a first aspect of the present invention, there is provided a method of encoding data, as defined in the attached claims. According to a second aspect of the invention, there is provided a method of decoding received encoded data. According to a third aspect of the invention, there is provided a transmitter for encoding data in accordance with the encoding method of the invention. According to a fourth aspect of the invention, there is provided a receiver for decoding data in accordance with the decoding method of the invention.

For a better understanding of the present invention, and to show how it may be put into effect, reference will now be made, by way of example, to the accompanying drawings, in which:

Figure 1 is a block schematic diagram of a communications system embodying the present invention.

Figure 2 illustrates the coding scheme according to an aspect of the present invention.

Figure 1 is a block schematic diagram of a communications system 10, in which a transmitter 12 is connected to a receiver 14 by means of a connection 16. For example, the transmitter 12 and the receiver 14 may be separate devices located within a larger device. As one specific example, the transmitter may be an application engine or a baseband processor within a mobile device, while the receiver 14 may be a graphics processor or another application specific device, although it will be appreciated that the coding scheme of the invention may be used regardless of the types of device involved.

In the transmitter 12, user data may be obtained from any process or application, for transmission to the receiver 14. The user data is passed to an encoder 18 for encoding, as described in more detail below, and the encoded data is passed to a transmit interface 20, which performs any processes required to put the encoded data into the form desired for transmission over the connection 16.

The encoder 18 also receives control information, for example in the form of control flags, that is intended to be embedded in the stream of data for transmission. Again, this will be described in more detail below.

In the receiver 14, the data is received at an interface 22, and passed to a decoder 24 for decoding. The interface 22 performs any processes required to retrieve the encoded data, and the decoder extracts the control information embedded in the transmitted data stream, and recreates the original user data from the encoded data, so that the recreated original user data can be passed to any subsequent process or application, for further processing.

As described in more detail below, the user data is received in the form of data bytes, each containing eight data bits. Each of these data bytes is converted into a sequence of nine encoded data bits.

Figure 2 illustrates the encoding scheme in more detail.

Specifically, as shown in Figure 2, the eight data bits of a byte 50 of user data are identified as [B1 , B2, B3, X1 , X2, Q1 , Q2, Q3]. In fact, this can be obtained by means of any arbitrary bijective (eight bits to eight bits) logical transformation of the input data byte, provided that the inverse function is available at the receiver side. For example, the eight data bits of the byte 50 can be an arbitrary permutation of the input data byte, where additionally each bit position can be inverted or not, compared to its source bit in the data byte, provided that the permutation and the inversions are known in advance, and can be reversed in the receiver. However, other bijective, reversible, transformations are also possible.

In the encoding process according to one embodiment of the invention, three of the bits of the input data byte appear unchanged in the encoded data word. The other six bits of the encoded data word form two blocks of three bits, separated by two of these unchanged bits. More specifically, in the encoding process as shown in Figure 2, three of the bits of the input data byte, namely the bits identified as B1 , B2 and B3, appear unchanged in the first, fifth and sixth bit positions respectively of the encoded data word 60. Two further bits of the input data byte, namely the bits identified as X1 and X2, appear unchanged in the second and ninth bit positions respectively of the encoded data word 60.

Further, in the encoding process, as shown in Figure 2, the bits Q1 , Q2 and Q3 of the input data byte are encoded in a logic block 30, also using the bits X1 and X2 of the input data byte, to form the bits Y1 , Y2, Y3 and Y4 appearing in the third, fourth, seventh and eighth bit positions respectively of the encoded data word.

As mentioned previously, one of the purposes of such an encoding technique is to ensure that the encoded data words have certain desirable properties.

For example, it can be advantageous to provide a coding scheme in which is guaranteed that there will be a certain minimum number of polarity transitions in each encoded data word.

Further, it can be advantageous to provide a coding scheme in which there is a guaranteed maximum run length, that is, a guarantee that there will not be more than a predetermined number of identical bits, either within an encoded data word, or extending across two or more consecutive encoded data words.

According to the preferred embodiment of the present invention, the coding scheme operates such that there is guaranteed to be a first polarity change either between the second and third bits of the encoded data word, or between the third and fourth bits of the encoded data word, and such that there is guaranteed to be a second polarity change either between the seventh and eighth bits of the encoded data word, or between the eighth and ninth bits of the encoded data word, while excluding the possibility that the first polarity change is between the second and third bits of the encoded data word while the second polarity change is between the eighth and ninth bits of the encoded data word.

This guarantees that there are at least two polarity changes in each encoded data word, and also guarantees that every serialized stream of encoded data words has a maximum run length of five bits.

This could also be achieved in an equivalent manner by guaranteeing that there is a first polarity change either between the first and second bits of the encoded data word, or between the second and third bits of the encoded data word, and guaranteeing that there is a second polarity change either between the sixth and seventh bits of the encoded data word, or between the seventh and eighth bits of the encoded data word, while excluding the possibility that the first polarity change is between the first and second bits of the encoded data word while the second polarity change is between the seventh and eighth bits of the encoded data word. For example, this can be achieved by shifting the bit identified as B1 to the ninth bit position of the encoded data word 60, and shifting each of the other bits in the encoded data word 60 one position to the left.

The stated guarantees can be obtained by using the following coding table:

As a result, in the preferred embodiment, the logic block 30 applies the following logical relationships to obtain the required bits of the output data word:

Y1 = (~Q1 &~Q2&~X1 ) I (Q1 &Q3) | (Q2&Q3)

Y2 = (~Q1 &-Q2&-X1 ) I (Q1 &~Q3) | (Q2&-Q3)

Y3 = (Q1 &~Q2) I (Q1 &Q2&-X2) | (-Q2&Q3)

Y4 = (~Q1 &Q2) I (Q1 &Q2&-X2) | (~Q1 &~Q3),

where AND='&', OR=T, and NOT='-'.

Thus, the logic block 30 only requires a relatively small number of simple logic functions, and does not require any complex calculations.

This encoding scheme therefore provides encoded data words having desirable properties.

Moreover, it allows various unique exception/escape codes to be defined. These codes can be inserted into the data stream, as described above, to embed control information into the transmitted data.

In particular, a first group of these exception codes are referred to as "comma codes". As described above, the 9 bit encoded data words obtained from all of the possible 8 bit input data words can be guaranteed to have a maximum run length of five bits. However, 9 bit code words with longer run lengths can be defined, and these can be inserted into a data stream for special purposes, that is, not representing data. For example, as is known to the person skilled in the art, these 9 bit code words with longer run lengths can be used for performing synchronization, for synchronization checks, to identify the beginning and end of data packets, to insert skip and/or idle codes, and some error checking capabilities.

In particular, it is possible to define a number of 9 bit code words that contain specific bit sequences that can be guaranteed not to appear anywhere within any serialized sequence of encoded data words obtained from possible 8 bit input data words. Codes with this property are referred to as "comma codes". This has the effect that, even if the receiver has not been synchronized with the transmitter, meaning that the receiver has not yet identified the beginning and end of each transmitted 9 bit word, the receiver is able to identify these specific bit sequences,

and then use its knowledge about these specific bit sequences to achieve synchronization.

In fact, based on the coding scheme described above, where the bit identified as B1 appears as the first bit in the encoded data word, and there is guaranteed to be a first polarity change either between the second and third bits of the encoded data word, or between the third and fourth bits of the encoded data word, and there is guaranteed to be a second polarity change either between the seventh and eighth bits of the encoded data word, or between the eighth and ninth bits of the encoded data word, while excluding the possibility that the first polarity change is between the second and third bits of the encoded data word while the second polarity change is between the eighth and ninth bits of the encoded data word, there are at least four ways to define four unique exception codes with a runlength of 6 bits. There are also two exception codes with a runlength of 7 bits and two exception codes that can be combined with subsequent valid codewords to produce bit sequences with a runlength of at least 8 bits, but may result in bit sequences with a runlength of up to 1 1 bits, depending on the subsequent code word.

The four ways of defining four unique exception codes with a runlength of 6 bits are listed in the following table, identified as Options 1 -4:

It should be noted that the exception codes in the last of these three categories can be flipped; that is, the code 100000000 can be replaced by 000000001 , and 01 1 1 1 1 1 1 1 can be replaced by 1 1 1 1 1 1 1 10. In that case, sequences with a runlength of up to 10 bits may be obtained, depending on the preceding code word, in the case where the bit identified as B1 appears as the first bit in the encoded data word.

In the alternative described above, where the bit identified as B1 appears as the ninth bit in the encoded data word, and there is guaranteed to be a first polarity change either between the first and second bits of the encoded data word, or between the second and third bits of the encoded data word, and there is also guaranteed to be a second polarity change either between the sixth and seventh bits of the encoded data word, or between the seventh and eighth bits of the encoded data word, while excluding the possibility that the first polarity change is between the first and second bits of the encoded data word while the second polarity change is between the seventh and eighth bits of the encoded data word, the exception codes in the last of these three categories may result in bit sequences with a runlength of up to 10 bits, depending on the subsequent code word. Again, however, the exception codes in the last of these three categories can be flipped, as described above, and, in that case, sequences with a runlength of up to 1 1 bits may be obtained, depending on the preceding code word.

If the exception codes can be guaranteed to have a polarity transition between the first and second bits, then it becomes easy to achieve alignment based on the exception codes, which means that option 1 is the preferred solution. That is, if the exception codes listed in the table as Option 1 are used, then, when the receiver detects six consecutive bits with the same bit value, it will know that this indicates that one of the exception codes has been transmitted. Moreover, since each of the exception codes has a polarity transition between the first and second bits, (and each of the exception codes with a runlength of 6 also has a polarity transition between the seventh and eighth bits), the receiver can identify the start and the end of the exception code word, and can then use this to identify the start and the end of each subsequent received code word.

Because the two codes in the last runlength category can cause a significantly higher maximum possible runlength, it is attractive to limit usage of exception codes to the first two runlength categories with maximum runlengths of 6 and 7 respectively. If four exception codes are sufficient, the overall maximum runlength can be limited to 6.

A further category of exception codes can be defined. Specifically, these are the code words where there is a first polarity change between the second and third bits of the encoded data word, and a second polarity change between the eighth and ninth bits of the encoded data word, but the third and fourth bits are equal, as are

the seventh and eighth bits, while the third and eighth bits (and hence also the fourth and seventh bits) have opposite polarities.

These code words therefore have the form:

61 , 1 , 0, 0, -32, .33, 1 , 1 , 0 Or

61 , 0, 1 , 1 , 62, 63, 0, 0, 1 .

It can be seen that there are two possible forms for these code words and, in each case, B1 , B2 and B3 can take any values, giving eight possible combinations, leading to 16 of these code words in total.

Again, these exception codes can be used to embed control information into the data stream, as required. However, the exception codes of this category are not unique, as the bit sequences can also appear in a sliding window across the boundary between two consecutive encoded data words, and so these code words can only be used once synchronization has been achieved, that is, once the receiver knows where each received code word begins and ends.

The exception codes can be stored in the encoder 18, or elsewhere, and can then simply be inserted complete into the data stream for transmission. Alternatively, encoding logic can be provided for generating the exception codes from received control information. After encoding, and insertion of any required exception codes, the data stream can be transmitted to the decoder 24. In the decoder 24, it is first necessary to recognize and remove any exception codes that were inserted into the data stream.

For example, exception codes with runlengths greater than 5 can be identified simply by the presence of these runlengths. The regular exception codes can for example be recognized by identifying that the third and fourth bits are equal, as are the seventh and eighth bits, while the third and eight bits (and hence also the fourth and seventh bits) have opposite polarities. The control information corresponding to any extracted exception codes can then be passed on to a further control process.

Any other code words, representing encoded data words, can be decoded. It is clear from the discussion of the encoder 18 above that the bits B1 , B2, B3, X1 and X2 appearing in the encoded data word do not need to be decoded, as they were unchanged by the encoding process.

It should also be noted that, although the bits Y1 , Y2, Y3 and Y4 of the encoded data word were obtained from the bits Q1 , Q2 and Q3 of the input data byte, also using the bits X1 and X2 of the input data byte, it is possible to decode the bits Y1 , Y2, Y3 and Y4 of the encoded data word to the required bits Q1 , Q2 and Q3 of the decoded data byte, without also using the bits X1 and X2.

The received nine bit code word is therefore divided into a first group, containing the five bits B1 , B2, B3, X1 and X2 that do not need to be decoded, and a second group, containing the four bits Y1 , Y2, Y3 and Y4, it being noted that the first group of bits are not the first five bits in the received code word, and the second group of bits are not the last four bits in the received code word.

Specifically, the logical relation for decoding is:

Q1 = EXOR(YI ,Y2)&~(~Y3&Y4) Q2 = EXOR(YI ,Y2)&~(Y3&~Y4) Q3 = (Y1 &~Y2) I (Y1 &Y2&Y3) | (~Y1 &-Y2&Y3) = (Y1 &-Y2) I (~EXOR(Y1 ,Y2)&Y3)

where AND='&\ OR=T, and NOT='-'.

Thus, the decoder 24 only requires a relatively small number of simple logic functions, and does not require any complex calculations.

Finally, in order to obtain the output data byte, this decoded data word must undergo a process to reverse any bijective transformation, such as any permutation and/or inversions that were applied to the input data byte before encoding.

There is therefore described a method for encoding data, which can provide encoded data having desirable properties, while also providing the possibility of useful exception codes, without causing an undesirably large increase in the amount of data to be transmitted.