Distributed burst error protection

A method of protecting digital words traversing multiple data paths is presented. The method identifies a number of bits for a header of a digital word and determines a number of protection bits for the header. A bit value for each of the protection bits is computed, and the computed bit values of the protection bits are transmitted through one or more data paths.

BACKGROUND

Many communication protocols employ encoding techniques that incorporate header bits before a payload in a digital word. Exemplary encoding schemes include Ethernet, Interlaken, and peripheral component interconnect express (PCIe) gen3, each of which includes a two or three bit header with a payload. Typically, error detection/correction codes may be used to detect or correct payload errors and not the header bits that occur during data transmission. Error detection/correction codes include cyclic redundancy checks (CRC), along with error-correcting code (ECC), such as forward error correction (FEC). The error correction code can ensure that errors in consecutive bits of the payload, i.e., a burst error, will be detected or corrected.

Header bits are used to interpret the payload associated therewith. Accordingly, misinterpretation or corruption of the header bits can cause the associated payload to be interpreted incorrectly. In other words, corruption of the header bits can lead to misinterpretation of the payload bits even in presence of the error correction code. Therefore, if the integrity of the header associated with the payload is not maintained, there is no guarantee that the error detection code can detect or correct an error in the payload.

SUMMARY

According to embodiments herein, a method and apparatus provide distributed redundancy bits, also referred to protection bits, for header bits in order to protect the header from error corruption. In one embodiment, protection bits are distributed in a location different than the header location. It should be appreciated that the embodiments can be implemented in numerous ways, including as a method, a system, or a device. Several exemplary embodiments are described below.

In accordance with one exemplary embodiment, a method of protecting digital words traversing multiple data paths is described. The method identifies a number of header bits for a header of a digital word and determines a number of protection bits for the header. A bit value for each of the protection bits is computed, and the computed bit values of the protection bits are distributed among the data paths.

In accordance with another exemplary embodiment, a method for protecting header bits of a digital word along with the word itself using a parity bit is provided. The method identifies a bit error rate for each data path. A parity bit, enabling detection of an unintended change in a header, is received. The bit in the header is compared to a the parity bit. In response to a mismatch between at least one of the header bits and the parity bit, adjusting a bit value associated with the at least one of the header bits in the data path with a highest bit error rate is performed.

Other aspects and advantages of the embodiments will become apparent from the following detailed description, taken in conjunction with the accompanying drawings, illustrating by way of example the principles of the embodiments.

DETAILED DESCRIPTION

The following embodiments describe exemplary apparatus and method for distributing protection bits in a digital word in order to protect header bits from unrecoverable error corruption. It will be obvious, however, to one skilled in the art, that the embodiments may be practiced without some or all of these specific details. In other instances, well known process operations have not been described in detail in order not to unnecessarily obscure the embodiments.

Embodiments described below provide protection for header bits from unrecoverable error corruption in any suitable communication protocol. The header bits are used in interpreting a payload of a digital word. The embodiments described below may be implemented by adding protection bits for recovery of the header of a digital word should an error in the header occur. Ability to recover header bits from burst errors may be further enhanced by separating the protection bits from the associated header. It should be appreciated that the embodiments described below are generally applicable irrespective of the method used to calculate the number of the protection bits and values thereof, so long as the protection bits are distributed in a manner that separates the protection bits from the associated header. Any error correction code (ECC) code can be used to implement the embodiments described below. As such, using Hamming codes is exemplary and is not intended to limit the scope of the present invention

FIG. 1illustrates an exemplary diagram of a digital word with a protection bit in accordance with one exemplary embodiment. Digital word10includes a sequence of data bits or a payload12with associated header14. The associated header14may be used to convey information about the payload12to the receiving circuit. For example, the header14bit values can indicate if the payload12is either a control payload or data payload depending on the communication protocol governing the data transmission. In one embodiment, the data path can be a data path that traverses through a high speed serial interface (HSSI) of an integrated circuit.

In one embodiment, the header14bit values may be correctly recovered, even in presence of one or more errors, by introducing added protection for the recovery for the header bits. For example, protection bits16may be added to the digital word10in order to provide added protection for the recovery that may be used to detect and correct errors in the header14bits. The protection bits16may be a result of combining one or more of the header14bits. It should be appreciated that depending on the protection scheme, protecting the individual bit values of the header14is not essential, so long as the combined state of the header14bits is preserved. For example, instead of protecting each bit in isolation, a combination of header14bits may be protected, thereby improving efficiency. In another embodiment, since a burst error may affect consecutive bits of the digital word10, placing the protection bits16and the header14on opposite ends of the digital word10improves the ability to recover the header bits14even in presence of a burst error affecting both the protection bits16and the header14bits. It should be appreciated that the protection bits16may be positioned in any position of the digital word10as long as the manner in which the protection bits16that introduce redundancy to the header14bits is maintained.

A number of bits between the header14bits and the protection bits16are referred to as the distance between the two. The distance provides protection against the number of error bits that define the distance. For example, if the distance between the header14bits and the protection bits16is 10 bits, then the scheme enables header bits to be successfully recovered even in presence of a burst error of up to 10 bits.

FIG. 2illustrates an exemplary diagram of a header protection schemes in multiple data paths in accordance with exemplary embodiments. Often digital data is transmitted over a number of parallel data paths20A-D. However, a burst error typically does not occur in more than one data path20A-D contemporaneously. In one embodiment, the protection bits16and the header14bits are positioned on opposite ends of the payload12and the protection bits16can be distributed among multiple data paths20A-D. In one embodiment, data being transmitted in at least one data path, e.g., data path 420D, of multiple paths may not have a corresponding protection bit associated therewith. In one embodiment, each of the multiple data paths is a differential serial data path

A minimum number of protection bits16that can be used to protect the bits of the header14can be determined based on the total number of bits of the header14across all lanes. In an exemplary embodiment, an error correction code such as the Hamming code can be used to calculate and compute the value of each of the three bits (protection1, protection2, and protection3) of the protection bits16protecting the four bits of the header14associated with payload12transmitted over multiple data paths20A-D. It is appreciated that the number of header bits, the number of protection bits, the number of data paths, etc., are exemplary and not intended to limit the scope of the present invention. It should be appreciated that Hamming code can detect up to two simultaneous bit errors and correct single-bit errors. Hamming distance is referred to as the number of bit positions in two bit sequences with different bit values. Therefore, a burst error corrupting two bits of a bit sequence would have a Hamming distance of 2. Hamming code facilitates reliable communication when the Hamming distance between a transmitted and received sequence of bits is less than or equal to one. A Hamming code is one exemplary error correcting code and is not intended to be construed as limiting the scope of the present invention. For example, other error correcting codes such as BCH, Reed-Solomon, Turbo codes, etc., may be used instead.

For example, using the Hamming code, it may be determined that three protection bits16(protection1, protection2, and protection3) provides protection to detect and correct an error in the four bits of the header14(header1, header2, header3, and header4) in the data paths20A-D. This Hamming code is commonly referred to as a Hamming (7,4) code. In one embodiment, the header14bits of all the data paths20A-D are aggregated together and the protection bits16are computed. In another embodiment, the protection bits16are added to the end of the payload of the digital word10opposite the header14. Still further, the protection bits16are distributed such that there is one protection bit per data path20A-C, except for the last data path20D. It should be appreciated that the protection bits16can be arbitrarily distributed among the data paths20A-D as opposed to being on the same data path as the payload or header for which the protection bits are providing the added recovery. In one embodiment, the protection bits16and the header bits14for a single data lane are spread apart within the data lane so that a single burst error impacts as few of the header bits and the protection bits as possible. It should be further appreciated that any ECC can be used to calculate the number and the values of the protection bits16.

The protection bits may be distributed if the number of header14bits is greater than the number of data paths20A-D. For example, if more than four header14bits are associated with the payloads12in data paths20A-D, these bits of the header14can be protected using four protection bits16, where the number of protection bits in this instance (4) are determined by the Hamming Code. That is, a Hamming (11,7) code may be used where seven header14bits are protected by using four protection bits16.

FIG. 3illustrates an exemplary diagram of a header protection scheme using grouped protection bits in multiple data paths in accordance with exemplary embodiments. For data that is transmitted over a large number of data paths20A-F, the protection bits16and the header14bits can be formed into groups. For example, for six data paths20A-F, the digital words10can be divided into two groups, Group 1 and Group 2. In one embodiment, a group of protection bits16associated with their corresponding header14bits are transmitted through different data paths. For example, the protection bits 4-6 associated with the header bits 4-6 may be transmitted along with header bits 1-3 in Group 1 on data paths20A-C. Similarly, protection bits 1-3 associated with the header bits 1-3 may be transmitted along with the header bits 4-6 in Group 2 on data paths20D-F, as depicted inFIG. 3.

In another embodiment, the protection bits 4-6 can be placed adjacent to the header bits 1-3 in group 1 since protection bits 4-6 associated with the header bits 4-6 are transmitted on different data paths. It should be appreciated that locating the protection bits16closer to the front of a digital word10reduces the latency in decoding the message, since the header14is more readily available, i.e., accessible to the decoding apparatus as opposed to the header being located at the end of the digital word. The location of the protection bits16relative to the header14bits is for illustrative purposes and not intended to limit the scope of the present invention. In one embodiment the protection bits16can be located in any position of the digital word10, so long as the protection bits16are transmitted in a data path different from header14bits associated therewith. For example, protection bits 4 may be positioned in data path other than data path 4 because header bits 4 are being transmitted on data path 4. The distributed group protection scheme can also be applied in situations where the number of data paths20A-F is such that equally sized groups cannot be formed. For example, in a case where seven data path are employed, bits of the header14associated with the payload12in the seventh data path can be protected using the protection bits16of Group 2 where the seventh data path may not have a protection bit if the number of protection bits16is less than the number of data paths20A-F, as illustrated inFIG. 2.

FIG. 4illustrates an exemplary diagram of a parity bit protection scheme in multiple data paths in accordance with one exemplary embodiment. The header14bits associated with the payload12of the digital word10are transmitted on data paths20A-D. The header14bits and the payloads12are transmitted on data paths20A-D while a parity bit22for protecting the header14bits is transmitted on data path20E. In one embodiment, the number of parity bits22is the same as the number of header14bits. It should be appreciated that digital paths20A-E can have differing error rates. Burst error impacts the data path20A-D with the highest error rate. The parity bit22may be used to correct the bit values of the header14and the payload12in the data path20A-D with the highest error rate. Transmitting the parity bit22in the same data paths20A-D as the header14bits may expose the parity bit22along with the header14and payload12to a burst error. Accordingly, transmitting the parity bit22in a data path, e.g., data path20E, separate from the transmission data paths, e.g., data paths20A-D, of the header14bits and the payload reduces the likelihood of corruption of the parity bit22, the payload12, and the header14by a burst error at the same time.

FIGS. 5A-Billustrate exemplary header protection using a parity bit protection scheme in multiple data paths in accordance with one exemplary embodiment. Prior to transmission, bit sequences in the respective data paths20A-E are shownFIG. 5A. The bit sequences of data paths20A-20D represent header bit sequences in one embodiment. In one embodiment, the value of each parity bit is calculated based on the bit values of its corresponding header bits in each data path20A-D. For example, to calculate the value of the first parity bit, the first header bit in each of the data paths20A-D with a value of “1” is summed. In the first bit in the data paths20A-D, the number of bits with a value of “1” is 2, which is an even number, resulting in a corresponding value of the first parity bit of “0”. In another example, to calculate the value of the second parity bit, the number of header bits in the second position with a value of “1” is 1, which is odd, resulting in a corresponding value of the second parity bit of “1”. The remaining parity bits are calculated in a similar fashion. It is, however, appreciated that the values of the parity bits may be calculated based on other values, e.g., “0” value. As such, calculating the parity bits based on the number of header bits with a value of “1” is exemplary and not intended to limit the scope of the present invention.

FIG. 5Billustrates exemplary bit patterns in data paths20A-E after an unintended change in the bit values. Comparing the bit sequences in FIGS.5A and5B, it should be noted that the value of the fifth bit in the bit sequence in data path 320C has “flipped” from “0” to “1”. To detect this error in the header bit sequences in the data paths20A-D, the number of header bits with a value of “1” at each position is compared with the value of the corresponding parity bit22in data path20E. In this example, for the fifth bit position from the left in the header bit sequences of data paths20A-D with a value “1” is 2 after the error. The number of header bits in the fifth position with a value of “1” is inconsistent with the value of the corresponding parity bit22as discussed above, thereby indicating that an error has occurred in the fifth header bit position. In one embodiment, the bit in the data path20A-D that has the highest error rate, e.g., data path20C, is adjusted or modified to be consistent with the value of the parity bit22in that position. For example, referring toFIG. 5Band assuming that data path 320C has the highest error rate, the value of the fifth bit in the header bit sequence in data path 320C would be adjusted from “1” to “0”, thereby correcting the error. It should be appreciated that unlike the protection bit schemes discussed above with respect toFIGS. 1-3, the parity protection scheme described in FIGS.4and5A-B protects the state of each bit of the header, and not the aggregated state of the header bits. It should be further appreciated that the parity protection scheme can be employed to protect the header bits as well as the payload transmitted on the data paths20A-D.

FIG. 6illustrates an exemplary diagram of multiple header protection schemes in a single data path in accordance with one exemplary embodiment. The integrity of the payload12can be further enhanced by distributing identical copies of the header14A-C to different locations within the digital word10, e.g., header14A at the beginning, header14B in the middle, and header14C at the end of the digital word10. Distributing the identical copies of the header14A-C throughout the digital word10increases the probability that at least the majority of the copy of the header14A-C would be unaffected by a burst error. In one embodiment, the minimum distance between adjacent copies of the header14A-B and14B-C is defined by the maximum burst length that protection is desired.

After the digital word10is transmitted over the data path, the headers14A-C associated with the payload12are evaluated or “polled.” By positioning each copy of the header14A-C at the maximum burst length from one another, the majority of the copies of the header14A-C would be unaffected by a burst error. For instance, at most one copy of the header14A-C, for instance14A, can be corrupted by a burst error, while the other copies of the header14B-C should be unaffected in this embodiment. Analyzing the bits of the header14A-C of the digital word10would determine that the first copy of the header14A is different than the other two copies of the header14B-C as a result of the burst error. In one embodiment, the values of the header bits are determined based on the majority of the copies of the header bits. For example, if two headers, e.g., headers14B and14C, have the same values but differ from a third header14A value, then the header values are selected as indicated by either of the two headers having the same values, e.g., either header14B or header14C.

FIG. 7is an exemplary flow diagram for protecting a header using distributed protection bits in accordance with one exemplary embodiment. At step150, a number of header bits is identified. At step152, a number of protection bits is determined. In one embodiment, the number of protection bits is determined based on the number of header bits, as determined in step150. For example, four header bits can be protected with three protection bits using an ECC, e.g., a Hamming (7,4) code. In operation154, the bit value for each of the protection bits is computed. In one embodiment, the values of the protection bits are calculated by combining the header bits using an ECC, e.g., Hamming code. As discussed inFIG. 2, in the case where there are four bits of the header, a Hamming (7,4) code can be used. The Hamming (7,4) code calculates the value of three protection bits to protect four header bits. It should be appreciated that the distributed protection bit scheme can be implemented using any ECC. As such, using a Hamming code is for illustrative purposes only and not intended to limit the scope of the present invention.

The computed protection bit values are distributed among the data paths, in operation156. In one embodiment, the computed protection bit values and the corresponding header are placed in different locations within the data path, i.e., the header may be at the beginning of the word being transmitted and the protection bits are placed at the end of the word being transmitted over the same data path. Still further as illustrated inFIG. 2, the headers and the computed protection bits may be separated by the width of the payload in the same data path, in one embodiment. As a result, a receiving component can correct one or more errors in the headers by using the transmitted protection bits.

FIG. 8is an exemplary flow diagram for protecting a header using parity bits in accordance with one exemplary embodiment. At step160, a bit error rate for each data path is determined. In operation162, one or more parity bits are received by a receiving component through the data paths. In one embodiment, the parity bit enables the receiving component to detect and correct an error that has occurred in one or more header bits during transmission, as illustrated inFIGS. 5A-B. In one embodiment, the parity bit is computed by combining header bits. For example, in one embodiment as illustrated inFIGS. 5A-B, the value of the parity bit for each position depends on the number of associated header bits with a value of “1”.

In one embodiment, digital words and one or more parity bits that are transmitted over the data paths are received by a receiving source. During data transmission, one or more header bits of one or more of the digital words being transmitted through multiple data paths may change values due to a burst error in one of the multiple data paths, causing an error in one or more header bits.

At step164, each header bit is compared to the received parity bit. In one embodiment, the receiving source can analyze the header bits to determine if the header bit values are consistent with the parity bit values, as illustrated inFIGS. 5A-B. At step166, one or more bits of the header bits received through the data path with the highest bit error rate is changed in response to a mismatch between a calculated parity bit value at the receiving end and the received parity bit value that was calculated by the transmitting component, as illustrated inFIGS. 5A-5B. In one embodiment, the bit error rate for the data paths are compared and periodically monitored. It should be appreciated that the data path with the historically highest error rate can change due to a variety of factors, such as variation in temperature.

FIG. 9is an exemplary flow diagram illustrating a multiple header protection scheme in accordance with one exemplary embodiment. At step170, multiple identical copies of the header bits associated with a payload are generated, as illustrated inFIG. 6. In operation172, each copy of the header is distributed to a different location within the word containing the payload to be transmitted over a data path. For example, one identical copy of the header may be positioned at each of the beginning, one in the middle, and one in the end of the word to be transmitted, as illustrated inFIG. 6. In operation174, the headers and the payload are transmitted on a data path from a transmitting component to a receiving component. In one embodiment, each header is analyzed by the receiving component. The bit values of each of the received header copies are compared to one another. The bit values as identified by the majority of the copies of the header bits are selected as the header bit values. For example, as discussed inFIG. 6, each header of a payload with three copies of the header is analyzed. If one copy of the header has been affected by a burst error, the copy of the header that differs from the rest of the copies is disregarded. The remaining copies of the header are used to interpret the payload.

FIG. 10illustrates an exemplary diagram of an integrated circuit used for implementing header protection schemes in accordance with one exemplary embodiment. An integrated circuit (IC)100includes an input/output (I/O) ring108with contains circuits which transmit and receive signals between a core logic104and a high speed serial interface (HSSI)102, and the rest of the system. The exemplary ICs100can include processors, application specific integrated circuits (ASICs) or programmable logic devices. It should be appreciated that any known I/O standards, whether single ended or differential, may be supported by the input/output circuitry of the I/O ring108, such as low-voltage differential signaling (LVDS), transistor-transistor logic (TTL), etc., standards. In one embodiment, the HSSI102of the IC108includes several data paths20or lanes, which can be used to transmit bit sequences in the form of digital words. In one embodiment, the data paths20are serial data paths. Still further, the serial data paths20are high speed optical links, in one embodiment.

The core logic104of the integrated circuit100may include a calculation engine106and a generation engine110. In one embodiment, the calculation engine106includes logic to determine a number of protection bits, where the number of protection bits corresponds to the number of bits of the header of the payloads in the data paths. Still further, the calculation engine106functions to combine the bits of the header, in one embodiment. In another embodiment, the generation engine110includes logic that computes a bit value for each of the number of protection bits using the combined bits of the header from the calculation engine106. The generation engine110is also capable of distributing the computed values of the protection bits among the data paths20.

The method and apparatus described herein may be incorporated into any suitable circuit, including processors and programmable logic devices (PLDs). The PLDs can include programmable array logic (PAL), programmable logic arrays (PLAs), field programmable logic array (FPLAs), electrically programmable logic devices (EPLDs), electrically erasable programmable logic devices (EEPLDs), logic cell arrays (LCAs), field programmable gate arrays (FPGAs), just to name a few.

The embodiments can also be defined as a machine that transforms data from one state to another state. The transformed data can be saved to storage and then manipulated by a processor or through hardware logic of a PLD configured to perform or execute functionality as mentioned with reference toFIG. 10. The processor or hardware logic thus transforms the data from one thing to another. Still further, the methods can be processed by one or more machines or processors that can be connected over a network. Each machine can transform data from one state or thing to another, and can also process data, save data to storage, transmit data over a network, display the result, or communicate the result to another machine.

Although the foregoing embodiments have been described in some detail for purposes of clarity of understanding, it will be apparent that certain changes and modifications can be practiced within the scope of the appended claims. Accordingly, the embodiments are to be considered as illustrative and not restrictive, and the embodiments are not to be limited to the details given herein, but may be modified within the scope and equivalents of the appended claims.