WO2006027742A1

WO2006027742A1 - Fault tolerant bus

Info

Publication number: WO2006027742A1
Application number: PCT/IB2005/052902
Authority: WO
Inventors: Atul Katoch; Andre K. Nieuwland
Original assignee: Koninklijke Philips Electronics N.V.
Priority date: 2004-09-08
Filing date: 2005-09-06
Publication date: 2006-03-16
Also published as: GB0419871D0

Abstract

A module comprises a bus invert encoder (24) for determining whether a set of data bits should be inverted prior to transmission over a communication bus. The bus invert encoder (24) produces a bus invert signal BI which controls a selective inversion means (28), for example a multiplexer. A partial fault detection encoder (32) determines one or more temporary check bits from the set of data bits, substantially in parallel with the bus invert encoder (24). Thus, the one or more temporary check bits are determined based on the assumption that the set of data bits are to be transmitted without inversion from the selective inversion means (28). A logic unit (34) is provided for correcting the one or more temporary check bits, if necessary, based on the bus invert signal produced by the bus invert encoder (24). The module has the advantage of enabling the temporary check bits to be determined in parallel with the bus invert encoding, thereby reducing latency, with the logic unit being used to correct the check bits, if necessary, prior to transmission over the communication bus.

Description

DESCRIPTION

FAULT TOLERANT BUS

Technical Field of the Invention

The invention relates to a system including a communication bus, and in particular to reducing the processing delay in systems that use fault tolerant coding and bus inversion.

Background to the Invention

Technology scaling allows more and more functionality to be placed on a microchip. At the same time, reducing the on -chip power supply and increasing variation in the manufacturing process for very deep-sub micron technologies is resulting in reduced signal integrity.

On-chip buses and inter-chip buses can be significantly affected by this reduced signal integrity. In addition, these buses can also be a major contributor to the electrical noise that leads to drops in the power supply and to electromagnetic interference.

The buses are usually heavily loaded (i.e. they have a large capacitance), which means that if all of the lines in the bus switch together, then a large amount of current is drawn from the power supply. This can cause dips in the power supply, which may affect the integrity of the data, as well as the functionality of the logic blocks, and may even lead to a complete failure.

Special measures can be taken to avoid, or at least to reduce, the number of simultaneous switching outputs (SSO) in the bus. One example of a technique used to reduce SSO is bus invert coding. This technique restricts the number of simultaneously switching outputs to half (plus one bus invert signal) of the number of lines in the bus, and is known to reduce the power consumption of buses. From a technology perspective, the yield targets in very deep sub -micron technologies are hard to meet. This, coupled with maintaining signal integrity, poses major problems, and design measures like fault tolerant coding are used to overcome them.

One example of a fault tolerant coding scheme is Hamming coding. The Hamming codes are a special class of codes that are used for single -bit error correction. Check bits are generated from the set of data bits, a nd these check bits are transmitted across the communication bus with the data bits to the receiving module. The receiving module can then generate a syndrome from the received check and data bits to determine whether any errors have occurred during trans mission.

According to the Hamming coding scheme, the number of check bits required, m, is selected to satisfy the following equation:

2^m ≥ n + m + 1 (1)

where n is the number of data bits in a data word. This results in a (n,m) hamming code. The check bits can be generated using an exclusive -or tree.

Each check bit is calculated by counting the number of bits that are a logical 'one' in a subset of the set of data bits. If the number of logical 'ones' is an even number, the parity is said to be even and the check bit is assigned a value of logical 'zero'. If the number of logical 'ones' is an odd number, the parity is said to be odd and the check bit is assigned a value of logical 'one'. It should be noted that other definitions of parity are possible. The exact bits of the data word in the subset that is considered for each check bit is determined in accordance with the rule s associated with Hamming coding, which are well known in the art.

The check bits are transmitted to the receiving module with the data bits. The receiving module can then count the number of logical 'ones' received in each of the subsets of data bits and determine whether there are any single bit errors in the received data.

For buses with a large bit width, such as a 64 or a 128 -bit bus, the number of exclusive-or gates required can be very large and therefore the encoding procedure can introduce a large latency into the system. Furthermore, for very wide busses, counting the number of bits switching can also introduce a large latency into the system.

Another example of a fault tolerant code that can be used on a communication bus uses a parity bit to identify single bit errors in the received data. The parity bit is calculated by counting the number of bits that are a logical 'one'. If the number of logical 'ones' is an even number, the parity is said to be even and is assigned a value of logical 'zero'. If the number of logical 'ones' is an odd number, the parity is said to be odd and is assigned a value of logical 'one'. The parity bit is transmitted to the receiving module with the data bits. The receiving module can then count the number of logical 'ones' received and determine whether there are any single bit errors in the received data.

Again, the parity bit is calculated using an exclusive-or tree, and this can introduce a large latency into the system when the bus is very wide.

In order to meet demands for time-to-market, low-power operation, signal integrity, high yield and reduced costs, the above-mentioned techniques are used together. That is, a transmitting module uses bus invert coding to reduce the number of outputs that switch simultaneously on the communications bus, and uses a fault tolerant coding scheme to allow an error or errors in the received data to be detected.

Figure 1 shows such a system. In Figure 1 , a first module 2 is shown which receives a set of data bits on line 4. The set of data bits are provided to a bus invert encoder 6 which determines the number of transitions required to transmit the set of data bits across the bus 8. To determine the number of transitions required, the bus invert encoder 6 compares the present set of data bits to the previous set of transmitted data bits.

If the number of transitions required to transmit the set of data bits after the previous transmitted set is greater than half the number of bits in the set of data bits, then the set of data bits should be inverted prior to transmission to minimise switching on the bus 8. If the number of transitions required to transmit the set of data bits after the previous transmitted set is equal to, or less than half the number of bits in the set of data bits, then the set of data bits should be transmitted as it stands to minimise the switching on the bus 8.

Once the bus invert encoder 6 has determined whether or not the set of data bits should be inverted, a bus invert signal BI is passed to a multiplexer 10 and a fault detection encoder 12.

The multiplexer 10 receives the set of data bits at one input, and an inverted set of the data bits (inverted by an inverter 14) at the other input. The bus invert signal BI selects the output of the multiplexer 10 to be the set of data bits (ie non -inverted) if the data on the bus 8 should not be inverted to minimise transitions, and selects the output of the multiplexer 10 to be the inverted set of data bits if the data on the bus 8 should be inverted to minimise transitions.

After the bus invert encoder 6 has completed its processing of the set of data bits, the fault detection encoder 12 receives the bus invert signal and the output of the multiplexer 10, which will be the set of data bits or the inverted set of data bits.

The fault detection encoder 12 then analyses the set of data bits (inverted or not - inverted) and the bus invert signal according to a predetermined fault detection encoding scheme to determine one or more check bits. As mentioned ab ove, this scheme might be a Hamming coding scheme, or might involve generating a parity signal for the bits. Other types of codes are also feasible.

After the fault detection encoder 12 has determined the check bits, the check bits are transmitted across the bus 8, along with the inverted/non -inverted data bits and the bus invert signal Bl.

A receiving module 16 connected to the bus 8 receives the check bits, the inverted/non-inverted data bits and the bus invert signal Bl. The receiving module 16 then uses the received check bits to determine whether the received data bits (including the bus invert signal) contain any errors, and uses the bus invert signal to determine whether the received data bits should be inverted to obtain the correct data bits.

As the bus invert signal BI should be protected against errors, and as the fault detection encoder 12 uses the bus invert signal BI and the inverted or non -inverted data bits to calculate the check bits, the operations must be performed sequentially, and this compounds the latency of the bus invert and fault detection encoders.

Therefore, there is a need for a technique that allows data to be protected against errors and transmitted over a communications bus with minimum line switching, but which does not introduce unnecessary delay into the system.

Summary of the Invention

According to a first aspect of the present invention, there is provided a module for performing fault detection encoding and bus invert encoding on a set of data bits prior to transmission over a communication bus, the module comprising: bus invert encoding means for providing a bus invert signal to indicate whether the set of data bits should be inverted prior to transmission; selective inversion means for inverting the set of data bits in response to the bus invert signal; fault detection encoding means adapted to determine one or more check bits from the set of data bits according to a predetermined fault detection encoding scheme; wherein the fault detection encoding means is operable substantially in parallel with the bus invert encoding means.

According to another aspect of the invention, there is provided a method of performing fault detection encoding and bus invert encoding on a set of data bits to be transmitted over a communications bus, the method comprising the steps of: performing the bus invert encoding step to determine whether the set of data bits is to be inverted prior to transmission, and generating a bus invert signal indicative of whether the set of data bits is to be inverted; performing a partial fault detection encoding step on the set of data bits to determine one or more temporary check bits according to a predetermined fault detection encoding scheme; wherein the partial fault detection encoding step is carried out substantially in parallel with the bus invert encoding step. The invention has the advantage of allowing data to be protected against errors and transmitted over a communications bus with minimum line switching, but without introducing unnecessary delays into the system.

Brief Description of the Drawings

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

Figure 1 is a block diagram of a prior art system that uses bus invert and fault tolerant coding;

Figure 2 is a block diagram of a system that uses bus invert and fault tolerant coding according to the present invention;

Figure 3 is a flow chart illustrating the steps in the method according to the present invention;

Figure 4 is a block diagram of a Hamming encoder according to the invention;

Figure 5 is a block diagram of a Parity tree for a seven -bit wide data word; and

Figure 6 is a flow chart illustrating the design steps to be followed for implementing the calculation of the final check bits in a system according to the present invention.

Detailed Description of the Preferred Embodiments

As indicated above, it is not possible for the bus invert enc oder and fault detection encoder to operate completely in parallel as the fault detection encoder must encode the data bits that are to be transmitted (i.e. the inverted or non -inverted data bits) and the bus invert signal, to protect both the data and bus invert signal from errors. However, in accordance with the invention, the fault detection encoder is 'split' into two parts. The first part determines the check bits for the data as received by the transmitting module. To reduce latency in the system, this first part operates at the same time as the bus invert encoder determines whether the data should be inverted before transmission. The second part combines the bus invert signal with the check bits to determine a set of final check bits.

As the second part of the encoder performs a simple logic operation to combine the bus invert signal with the check bits, the latency of the system is significantly reduced relative to the prior art system that performs full bus invert coding and full fault detection coding sequentially.

Figure 2 is a block diagram of a system that uses bus invert and fault tolerant coding according to the present invention. In Figure 2, a first module 20 is shown which receives a set of data bits on line 22. The set of data bits wi Il comprise a plurality of bits that together form a data word. Although line 22 is shown as a single line, it will be appreciated that line 22 may actually comprise a number of parallel lines. As the module 20 operates, data words will be received on Ii ne 22 consecutively.

The set of data bits are provided to a bus invert encoder 24 which determines a signal indicating whether the data bits should be inverted to reduce the number of transitions on the bus 26. Although the bus 26 is shown as having three lines, it will be appreciated that the bus 26 will have many more than three lines, and the exact number depends on the number of bits in a data word, the number of bits used for the bus invert signal and the number of check bits.

A 'transition' is defined as a line switching from a logical 'zero' to a logical 'one', and vice versa. The bus invert encoder 24 determines the signal indicating whether the data bits should be inverted prior to transmission by examining the number of transitions that would otherwise be required to transmit the set of data bits after a preceding set of data bits across the bus 26. Specifically, the signal is determined by comparing the present set of data bits to the preceding set of transmitted data bits. For example, if the preceding data word was 01001110 and the next data word is 10111000, the number of transitions to transmit the next data word is six (the first, second, third, fourth, sixth and seventh lines will need to switch).

If the number of transitions required to transmit the present set of data bits after the previous set is greater than half the number of bits in the set of data bits, then the set of data bits should be inverted prior to transmission to minimise switching on the bus 26. If the number of transitions required to transmit the set of data bits after the previous set is equal to or less than half the number of bits in the set of data bits, then the set of data bits should be transmitted to minimise the switching on the bus 26.

The bus invert encoder 24 may determine the exact number of transitions required to transmit the next set of data bits, or may simply determine whether more than half the number of lines in the bus 26 will need to switch.

Once the bus invert encoder 24 has determined the number of transitions and whether or not the set of data bits should be inverted, the bus invert signal Bl, which indicates whether the next set of data bits should be inverted, is passed to a set of multiplexers 28. The bus invert signal BI will usually comprise a single bit (e.g. 0 for non -inversion, 1 for inversion, or vice versa).

Although a single multiplexer 28 is shown in Figure 2, it will be appreciated by a person skilled in the art that, as line 22 represents several lines, there will need to be a multiplexer 28 for each bit of the data word.

Each multiplexer 28 receives one of the bits in the set of data bits at one input, and an inverted copy of the bit (inverted by an inverter 30) at the other input. The bus invert signal BI selects the output of the multiplexer 28 to be the data bit if the data on the bus 26 should not be inverted to minimise transitions, and selects the output of the multiplexer 28 to be the inverted data bit if the data on the bus 26 should be inverted to minimise transitions.

Referring to the example above, as the number of bits in the set is eight, and the number of transitions required to transmit the next data word is six, the next data word should be inverted prior to transmission. This means that the next data word will be transmitted across the bus 26 as 01000111 (which only requires two transitions - the fifth and eighth bits).

It will be further appreciated by a person skilled in the art that the multiplexer 28 and inverter 30 can be replaced by alternative logic circuitry that performs the same function. Furthermore, the multiplexer 28 may be followed by a latch or a synchronising element which ensures that the transitions on the bus occur only during specified times.

For example, if the bus invert signal BI is a logical 'zero' when the data should not be inverted and a logical 'one' when the data should be inverted, the multiplexer 28 and inverter 30 can be replaced with a dual -input exclusive-or gate which receives a data bit at one input and the bus invert signal BI at the other. Alternatively, if the bus invert signal BI is a logical 'one' when the data should not be inverted and a logical 'zero' when the data should be inverted, the multiplexer 28 and inverter 30 can be replaced with a dual-input exclusive-or gate which receives a data bit at one input and the inverse of the bus invert signal BI at the other. A person skilled in the art will appreciate that there are many other ways to implement this aspect of the invention using standard logic processing compo nents.

In accordance with the invention, a partial fault detection encoder 32 is provided that determines one or more check bits for the set of data bits according to a predetermined fault detection encoding scheme.

In order for the check bits to be able to indicate errors in the received data bits and the received bus invert signal, the partial fault detection encoder 32 will ensure that there are a sufficient number of check bits to enable this to be carried out.

As the encoder 32 determines the one o r more check bits using the original set of data bits, the encoder 32 can operate independently of the bus invert encoder 24. In other words, the encoder 32 operates independently on the assumption that the data bits will not be inverted during transmission, and that the bus invert signal BI will therefore be a zero. Thus, in a preferred embodiment of the invention, the latency of a system using both bus invert coding and fault detection encoding is reduced significantly by operating the bus invert encoder 24 and fault detection encoder 32 at substantially the same time.

After the partial fault detection encoder 32 has determined the one or more check bits according to the encoding scheme, the check bits are passed to a logic unit 34. The logic unit 34 also receives the bus invert signal Bl, once it has been determined by the bus invert encoder 24.

The logic unit 34 operates to correct the one or more check bits determined by the partial fault detection encoder 32 in view of the bus invert signal Bl. As the one or more check bits are determined from the non -inverted data bits, it may be necessary to correct one or more of the one or more check bits if the data bits will be inverted for transmission.

The exact operation of the logic unit 34 will depend on the fault detection encoding scheme in use within the module 20, as described further below.

After the logic unit 34 has corrected one or more of the one or more check bits (if necessary in view of the bus invert signal Bl), the set of data bits (in th e determined normal or inverted state), the bus invert signal BI and the one or more check bits are transmitted across the communication bus 26 to a receiving module 36.

The receiving module 36 receives the one or more check bits, the inverted/non -inverted data bits and the bus invert signal Bl. The receiving module 36 then uses the received one or more check bits to determine whether the received data bits (including the bus invert signal) contain any errors, and uses the bus invert signal to determine w hether the received data bits should be inverted to obtain the correct data bits.

Figure 3 shows a flow chart illustrating the steps performed in the transmitting module according to the present invention. In step 101 , a set of data bits is received in the transmitting module. In step 103, one or more check bits are calculated from the set of data bits to allow any errors that occur during transmission to be detected and corrected in a receiving module. When calculating the one or more check bits, it will be noted that the check bit or bits are also required to protect the bus invert signal against errors. Therefore, it should be ensured that there are a sufficient number of check bits to allow errors to be detected in the set of data bits and the bus invert signal.

In step 105, a bus invert signal is calculated for the set of data bits. As described above, the bus invert signal is determined by comparing the present set of data bits with the preceding set of transmitted data bits.

In accordance with the invention, steps 103 and 105 are performed substantially in parallel within the transmitting module architecture. This allows the latency caused by performing these two calculations sequentially to be reduced.

Once the bus invert signal and one or more check bits have been calculated, the method moves to step 107 where the one or more final check bits are computed. The final check bit or bits are computed by combining the check bit or bits calculated in step 103 with the bus invert signal calculated in step 105. This step of the method corrects the check bit or bits to allow for the fact that the data bits may be inverted prior to transmission (depending on the bus invert signal), and to allow for the exact value of the bus invert signal.

In step 109, the set of data bits (inverted or non -inverted depending on the bus invert signal), the bus invert signal and the one or more final check bits are transmitted to the receiving module.

In a preferred embodiment of the invention, the fault detection coding scheme is a Hamming coding scheme. In a conventional Hamming encoder, the number m of Hamming check bits required to protect a set of n bits is given by Equation 1 above.

In the present invention, the Hamming check bits are generated from the set of data bits, but are also required to protect the bus invert signal Bl. Therefore, when determining the number m of check bits required, the number of bits n is equal to the number of bits in the set of data bits, plus one for the bus invert signal Bl.

For example, if the number of bits in the set of data bits is 8, the number of Hamming check bits m will be calculated using Equation 1, taking n as 9 (8 data bits plus 1 bus invert signal).

As an alternative example, when the number of bits in the data word is 4, the number of Hamming check bits m will be calculated conventionally to be 3. However, as the bus invert signal will also need to be protected against errors, the number of Hamming check bits m will be calculated from Equation 1 using n as 4+1 (four data bits and one bus invert signal), giving 4 check bits.

Figure 4 shows a Hamming encoder logic gate tree 40 in accordance with the invention for determining the initial check bits. The tree 40 comprises a number of exclusive -or gates 42. The data word in this illustrated example comprises seven data bits (D i, D₂, D₃, D₄, D₅, Ds, D₇). Therefore, four check bits will be required to protect the seven data bits and the bus invert signal BI according to Equation 1.

As described above, each check bit is calculated by counting the number of bits that are a logical 'one' in a subset of the set of data bits. If the number of logical 'ones' is an even number, the parity is said to be even and the check bit is assigned a value of logical 'zero'. If the number of logical 'ones' is an odd number, the parity is said to be odd and the check bit is assigned a value of logical 'one'. The exact bits of the data word in the subset that is considered for each check bit is determined in accordance with the rules associated with Hamming coding, which are well known in the art.

As shown in Figure 4, for a data word comprising seven data bits, the first check bit, C i, is calculated from data bits Di, D₂, D₄, Ds and D₇, the second check bit, C₂, is calculated from data bits D₁, D₃, D₄, D₆ and D₇, the third check bit, C₃, is calculated from data bits D₂, D₃ and D₄ and the fourth check bit, C₄, is calculated from data bits D₅, D₆ and D₇. It will be noted that, for a conventional circuit shown in Figure 1 , the bus invert s ignal BI would be included as an input to the tree 40, and there would be an extra exclusive -or gate 46 in each of the third and fourth check bit sub -trees (as indicated by the rules of Hamming encoding). However, for reasons explained by Figure 6 below, as the third and fourth check bit sub-trees would have an even number of inputs (including the bus invert signal Bl) these gates can be omitted.

In an alternative preferred embodiment of the present invention the fault detection coding scheme generates a parity signal for the set of data bits.

As described above, a parity bit is calculated by counting the number of bits that are a logical 'one'. If the number of logical 'ones' is an even number, the parity is said to be even and is assigned a value of logical 'zero'. If the number of logical 'ones' is an odd number, the parity is said to be odd and is assigned a value of logical One'.

It will be appreciated by a person skilled in the art that the parity may alternatively be calculated by counting the number of logical 'zeros', or may assign a parity of logical 'zero' when the number of bits having the particular value is odd, and vice versa.

Figure 5 shows a parity tree for a seven bit data word in accordance with the invention. The parity tree 44 comprises a plurality of exclusive-or gates 46, having the bits in the data word (D-i, D₂, D₃, D₄, D₅, D₈, D₇) received into the transmitting module 20 on line 22 as inputs to the tree 44. The output of the tree 44 is denoted P i .

It will be noted that, in a conventional circuit shown in Figure 1, the bus invert signal BI would be included as an input to the tree 44, and there would be an extra exclusive -or gate 46. However, for reasons explained by Figure 6 below, as the parity tree 44 would have an even number of inputs (including the bus invert signal Bl) this gate can be omitted.

As described above, as the one or more initial check bits (i.e. the Hamming check bits or parity bit) are calculated from the data as received by the transmitting module 20, and therefore the actual state of the data word to be transmitted is not known, the one or more initial check bits may need to be corrected by logic unit 34 after the bus invert signal has been determined. In other words, the initial check bit or bits are calc ulated from the non -inverted data bits, and the check bit or bits may need to be corrected later to produce final check bits based on the determined bus invert signal.

In the description of the logic unit 34 below, it is assumed that a bus invert signal o f logical 'zero' indicates that the data is not to be inverted, and a logical 'one' indicates that the data is to be inverted. When the opposite situation applies (i.e. logical 'zero' indicates inversion), the operation of the logic unit 34 will need to b e modified from the description below. This modification will be readily apparent to a person skilled in the art.

Figure 6 shows a flow chart illustrating the design steps to be followed for implementing the calculation of the final check bits in a system according to the present invention. As the number of bits in a data word and the number of bits used to calculate the check bit or bits are determined when a system is constructed, the decision logic required in the logic means 34 is minimal, and is given by the appropriate branch or branches of the flow chart in Figure 6. The steps in Figure 6 are not performed by the logic means 34 for each set of data bits.

As described above, the logic unit 34 corrects the one or more check bits determined by the partial fault detection encoder 32 in view of the bus invert signal Bl. As the one or more initial check bits are determined from the non -inverted data bits (and may conventionally have also included the bus invert signal in the calculation), it may be necessary to correct one or more of the one or more check bits if the data bits will be inverted for transmission.

The method starts at step 201 where the number of bits used to calculate a check bit C , is determined. It should be noted that this determination considers how many bits would be used to calculate the check bit in a conventional system, which includes the bus invert signal Bl, if appropriate.

For example, in a conventional Hamming encoder corresponding to the Hamming encoder 40 shown in Figure 4, the first and second check bits would be calculated using an odd number of bits (as shown), whilst the third and fourth check bits would be calculated using an even number of bits (because the bus invert signal BI would also be an input).

If the number of bits used to calculate check bit Ci in a conventional system is even, the method moves to step 203. In step 203, it is determined whether or not that even number of bits includes the bus invert signal Bl. If the bus invert signal BI is not conventionally one of the bits used to calculate that check bit d, then the method moves to step 205, and the check bit is unchanged and is used as a final check bit.

Therefore, the logic means 34 is not required to modify the check bit to produce the final check bit.

If the bus invert signal BI is conventionally one of the bits used to calculate that check bit Ci, then the method moves to step 207, in which the designer of the system should remove the exclusive-OR gate from the conventional check bit tree which receives the bus invert signal Bl.

For example, in a conventional Hamming encoder corresponding to the Hamming encoder 40 shown in Figure 4, the third and fourth check bits would be calculated using three data bits and the bus invert signal Bl, and would therefore comprise three exclusive-OR gates. However (and as shown in Figure 4), the exclusive -OR gate which receives the bus invert signal BI can be removed from the check bit sub -tree.

As a result of this modification to the conventional check bit su b-tree, the check bit produced by the sub-tree will be correct, regardless of whether the data is to be inverted for transmission. Therefore, the logic means 34 is not required to modify the check bit in view of the bus invert signal Bl.

If the number of bits used to calculate check bit Ci in a conventional system determined in step 201 is odd, the method moves to step 209. In step 209, it is determined whether or not that odd number of bits includes the bus invert signal Bl. If the bus invert signal BI is not conventionally one of the bits used to calculate that check bit Ci, then the method moves to step 211 , in which the check bit is combined with the bus invert signal BI using an exclusive-OR gate in the logic means 34. Therefore, if the bus invert signal Bi indicates that no inversion is to occur (Bl is a ¹O') then the check bit will be unchanged. However, if the bus invert signal BI indicates that inversion of the data will occur before transmission (Bl is a 'T) then the check bit will be inverted.

In step 209, if the bus invert signal BI is conventionally one of the bits used to calculate that check bit C₁, then the method moves to step 213. In step 213, the system is designed so that the exclusive-OR gate tree used in a conventional system is used to calculate the check bit in the system according to the invention, except that the addition of the bus invert signal BI to the tree is performed after the rest of the tree has calculated the partial check bit. Therefore, this has the effect of perf orming an exclusive-OR operation between the bus invert signal BI and the partial check bit.

Alternatively, the conventional exclusive-OR tree can be modified as described in step 207 above, and the logic means can comprise an exclusive -OR gate for comparing the bus invert signal BI and the partial check bit.

As mentioned above, in a real system, the number of bits in a data word will be fixed and therefore the decision process detailed above should not be performed on a word - by-word basis, as the appropriate functionality is built into the system. The flow chart in Figure 6 merely provides a system designer with the steps required to implement check bit correction in any system, once the number of bits used to calculate each check bit is known.

The invention described above has the advantage of reducing latency by determining an initial set of check bits while a bus invert coder determines whether or not the data bits are to be inverted for transmission, with a logic unit being provided to produce a final set of check bits that a re corrected, if necessary, depending on the assumptions made during the determining of the initial check bits.

It will be noted that, although the preferred embodiment describes the initial check bits being determined on the basis that the data bits are not being inverted during transmission, a person skilled in the art will readily appreciate that the invention could equally be used with a system where the initial assumption is reverse, ie that the set of data bits are to be inverted during transmission. In such a situation, the logic unit would be adapted accordingly.

Furthermore, it will be appreciated that, in certain situations, the logic unit will not need to perform any corrections, since the check bits will remain the same regardless of whether or not the initial assumption was correct.

It should be noted that the above-mentioned embodiments illustrate rather than limit the invention, and that those skilled in the art will be able to design many alternative embodiments without departing from the scope of the appended claims. The word "comprising" does not exclude the presence of elements or steps other than those listed in a claim, "a" or "an" does not exclude a plurality, and a single processor or other unit may fulfil the functions of several units recited in the claims. Any reference signs in the claims shall not be construed so as to limit their scope.

Claims

1. A module for performing fault detection encoding and bus invert encoding on a set of data bits prior to transmission over a communication bus, the module comprising: bus invert encoding means for providing a bus invert signal to indicate whether the set of data bits should be inverted prior to transmission; selective inversion means for inverting the set of data bits in response to the bus invert signal; fault detection encoding means adapted to determine one or more check bits from the set of data bits according to a predetermined fault detection encoding scheme; wherein the fault detection encoding means is operable substantially in parallel with the bus invert encoding means.

2. A module as claimed in claim 1 , further comprising logic means for combining the one or more check bits with the bus invert signal to determine one or more final check bits for transmission over the communication bus.

3. A module as claimed in claim 2, wherein the logic means is adapted to correct a check bit according to the number of bits in the set of data bits, the type of fault detection encoding scheme being used, and the status of the bus invert signal.

4. A module as claimed in one of claims 1 to 3, wherein the fault detection encoding means is adapted to carry out a Hamming coding scheme.

5. A module as claimed in one of claims 1 to 3, wherein the fault detection en coding means is adapted to carry out a parity calculation.

6. A module as claimed in any preceding claim, wherein the fault detection encoding means comprises one or more exclusive OR gates.

7. A module as claimed in claim 2, further comprising means adapted to provide the output of the selective inversion means, the bus invert signal and the one or more final check bits to the communication bus.

8. A method of performing fault detection encoding and bus invert encoding on a set of data bits to be transmitted over a communications bus, the method comprising the steps of: performing the bus invert encoding step to determine whether the set of data bits is to be inverted prior to transmission, and generating a bus invert signal indicative of whether the set of data bits is to be inverted; performing a partial fault detection encoding step on the set of data bits to determine one or more temporary check bits according to a predetermined fault detection encoding scheme; wherein the partial fault detection encoding step is carried out substantially in parallel with the bus invert encoding step.

9. A method as claimed in claim 8, further comprising the step of correcting the one or more temporary check bits, if necessary, to produce a final set of check bit s in accordance with the bus invert signal determined from the bus invert encoding step.

10. A method as claimed in claim 8 or 9, wherein the partial fault detection encoding step determines the one or more temporary check bits based on an assumption a bout how the set of data bits are to be transmitted over the communication bus.

11. A method as claimed in any one of claims 8 to 10, wherein the partial fault detection encoding scheme is a Hamming coding scheme.

12. A method as claimed in any one of claims 8 to 10, wherein the partial fault detection encoding scheme is a parity calculation.

13. A method as claimed in claim 11 or 12, wherein the partial fault detection encoding scheme involves one or more exclusive OR operations.

14. A method as claimed in claim 9, further comprising the step of providing the output of the selective inversion means, the bus invert signal and the one or more final check bits to the communication bus.