Patent Description:
When transferring information between functional blocks in a semiconductor chip, electrical signals are sent on multiple, parallel metal traces. A transmitter sends the electrical signals across the parallel metal traces. A receiver receives the electrical signals. The metal traces have transmission line effects such as distributed inductance, capacitance and resistance throughout its length. For modern integrated circuits, the interconnect capacitance reduces signal integrity and signal transfer rate more so than gate capacitance of semiconductor devices. The interconnect capacitance per unit length includes both sidewall fringing capacitance and cross-coupling capacitance. For example, the electromagnetic fields for the metal traces conducting signals and the return current on the ground plane create electrical interference on neighboring metal traces and on adjacent devices. As the operating voltage continue to decrease to reduce power consumption and short channel effects, the signal swing used for Boolean logic decreases as well as the noise margin.

A simultaneous switching of a wide bus may cause a significant voltage drop if a supply pin served all of the line buffers on the bus. Parasitic inductance increases transmission line effects on a chip such as ringing and reduced propagation delays. The resulting voltage drop is proportional to the expression L di/dt, wherein L is the parasitic inductance and di/dt is the time rate of change of the current consumption. Now a node that holds a logic high value may experience a voltage drop that reduces its voltage value below a minimum threshold. For memories and latches without recovery circuitry, stored values may be lost. Power supply currents flowing through non-zero resistance wires also create an IR (current-resistance) voltage drop, which contributes to data retention corruption and timing failures in critical paths.

<CIT> discloses a system wherein frames are transmitted over a parallel data bus, a synchronization symbol in the frame is used for indicating the type of the frame, wherein the frame has a fixed length which is an integer multiple of the bus width, and wherein when header metadata has not changed, said header metadata is not included in the frame, and wherein when header metadata has changed, the frame is transmitted with high priority.

In view of the above, methods and mechanisms for efficiently transmitting data are desired.

While the invention is susceptible to various modifications and alternative forms, specific embodiments are shown by way of example in the drawings and are herein described in detail. It should be understood, however, that drawings and detailed description thereto are not intended to limit the invention to the particular form disclosed, but on the contrary, the invention is to cover all modifications, equivalents and alternatives falling within the scope of the present invention as defined by the appended claims.

In the following description, numerous specific details are set forth to provide a thorough understanding of the present invention. However, one having ordinary skill in the art should recognize that the invention might be practiced without these specific details. In some instances, well-known circuits, structures, and techniques have not been shown in detail to avoid obscuring the present invention. Further, it will be appreciated that for simplicity and clarity of illustration, elements shown in the figures have not necessarily been drawn to scale.

Systems and methods for efficiently transmitting data are contemplated. In various embodiments, a computing system includes a transmitter sending data to a receiver. The transmitter and the receiver are components used on a communication bus between varieties of functional blocks used to process a variety of applications. In some examples, the communication bus is located between a memory controller and a memory device. In other examples, the communication bus is located between processing units located on a same die, located on separate dies in a system on a chip (SoC) package, or located on separate chips on a motherboard. The transmitter includes an encoder with at least a control unit and an error correction unit. The error correction unit is capable of selecting one of multiple error correction schemes. The error correction schemes generate security data corresponding to data to transmit. This security data is used to both identify and correct any errors in received payload data, rather than simply detect errors in the received payload data. In some embodiments, the error correction schemes are error code correction (ECC) schemes and the security data is an error correction code. Examples of the ECC schemes are a Hamming code scheme, a binary convolution code scheme, a Reed-Solomon code scheme, and a low-density parity check code scheme.

The encoder of the transmitter receives a first block of data to transmit. This first block of data includes any packet header and other metadata in addition to the payload data to send to the receiver. The encoder divides the received first block of data into multiple sub-blocks of data. Afterward, the encoder selects a portion of each sub-block to compare to one another. In various implementations, the portion selected in a particular sub-block has a same offset and a same size as other portions of other sub-blocks. After comparing, if the encoder determines the multiple portions from the multiple sub-blocks match one another, the encoder sends, to the receiver, a second block of data corresponding to the first block of data. The second block of data has a same size as a size of the received first block of data, and the second block of data includes security data from one of the multiple error correction schemes. Additionally, the second block of data includes a same number of sub-blocks as the first block of data. Therefore, the second block of data provides security without increasing an amount of data to transmit. The steps for generating the second block of data are further described in the following discussion.

Turning to <FIG>, a generalized block diagram of one embodiment of a communication bus <NUM> is shown. As shown, communication bus <NUM> includes a transmitter <NUM> capable of sending information as electrical signals, transmission lines <NUM>-<NUM> for transferring the electrical signals, and receiver <NUM> capable of receiving the signals. The number of transmission lines <NUM>-<NUM> can be any number and the number is based on design requirements. Although not shown for ease of illustration, each of the transmitter <NUM> and the receiver <NUM> includes circuitry for each of the transmission lines <NUM>-<NUM> for driving the electrical signals and for receiving the electrical signals, respectively. For example, both active devices, such as transistors, and passive devices, such as resistors, capacitors and inductors, are used one either end of the transmission lines <NUM>-<NUM>. This circuitry provides termination and sampling capabilities for the receiver <NUM> and this circuitry supports a particular communication protocol. The communication protocol determines values used for information transfer such as a number of data transfers per clock cycle, signal voltage levels, signal timings, signal and clock phases and clock frequencies.

It is noted that the term "bus" may also be referred to as a "channel," and each "transmission line" is a "lane" or a "trace" or a "wire. " In various embodiments, transmission lines <NUM>-<NUM> are constructed from a variety of suitable metal sources during semiconductor fabrication and surrounded by a variety of any suitable insulating material. It is also noted that the terms "pin," "port," "terminal," and "node" are used interchangeably herein. Depending on the design, the transmission lines <NUM>-<NUM> are placed between a memory controller and a memory device, or between processing units located on a same die, or between processing units located on separate dies in a system on a chip (SoC) package, or between processing units located on separate chips on a motherboard, or between clusters in a communication fabric. Other designs and placement of the transmission lines <NUM>-<NUM> are possible and contemplated. Although one transmitter <NUM> and one receiver <NUM> is shown, in other embodiments, any number of these components is used as well as any number of subcomponents within the transmitter <NUM> and the receiver <NUM>.

The transmitter <NUM> receives data to send on the transmission lines <NUM>-<NUM> via the interface <NUM>, and stores the data in one of the queues <NUM>-<NUM>. In some embodiments, the interface <NUM> selects one of the queues <NUM>-<NUM> for storing received data based on criteria such as a source of the data, a type of request or command associated with the data, a priority level of the data, and so forth. Arbitrator <NUM> includes circuitry for selecting data to retrieve from the queues <NUM>-<NUM> and send to the encoder <NUM>. The arbitrator <NUM> selects data from the queues <NUM>-<NUM> based on a variety of factors such as priority levels, a quality of service (QoS) parameter, an age of the data, a source of the data, a round robin selection scheme, and so forth.

The encoder <NUM> includes at least a control unit <NUM> and an error correction unit <NUM>. In some embodiments, the error correction unit <NUM> includes circuitry for performing a variety of error correction schemes used for both detecting errors in transmitted data and correcting one or more errors in the transmitted data. Examples of the error correction schemes are a Hamming code scheme, a binary convolution code scheme, a Reed-Solomon code scheme, and a low-density parity check code scheme. In other embodiments, the error correction unit <NUM> uses a table or other memory for storing indications of available error correction schemes, and sends a command to an external unit with an indication of a selected one of the multiple available error correction schemes and a copy of data to protect. Later, the error correction unit <NUM> receives the results, which are used to send data across the transmission lines <NUM>-<NUM>.

The control unit <NUM> attempts to send an output block of data corresponding to a received block of data with a same size as the received block of data while also including security data. To do this, the control unit <NUM> divides a received block of data into multiple sub-blocks of data. In one example, the first block of data includes <NUM> bytes, and the encoder of the transmitter divides this <NUM>-byte first block of data into <NUM><NUM>-byte sub-blocks. In one implementation, the encoder selects a most significant byte of the sub-blocks as portions to compare. In this case, for each portion, the offset is zero within a corresponding sub-block and the size is one byte. If the control unit <NUM> determines that the <NUM><NUM>-byte portions of the <NUM> sub-blocks match one another, then the encoder determines an amount of security data to send. To do so, the control unit <NUM> prevents including one or more copies of the portion in an output block of data to send on the transmission lines <NUM>-<NUM>. For example, the control unit <NUM> prevents including <NUM> of the copies of the portion in the output block of data, which provides <NUM> bits ((<NUM> bytes - <NUM> bytes) / <NUM> sub-blocks) per <NUM>-byte sub-block for storing security data.

The encoder <NUM> selects one of the available error correction schemes based on matching the <NUM> bits per <NUM>-byte sub-block and an input data size of one of the available error correction schemes. In an embodiment, the encoder selects a Hamming code (<NUM>, <NUM>, <NUM>) scheme as a selected error correction scheme. The first parameter of the Hamming code scheme includes a code word size, such as <NUM> bits, that includes the original data in addition to the security data. The second parameter of the Hamming code scheme includes an input data size, such as <NUM> bits, that includes the original data to transmit. The third parameter of the Hamming code scheme includes a size of the security data such as <NUM> bits. It is noted that the terms "security data," "security bits," "auxiliary data," "auxiliary bits," "redundant data," "redundant bits," are used interchangeably herein.

For each sub-block of the output block of data, the encoder <NUM> generates and inserts <NUM> generated redundant bits based on the Hamming code (<NUM>, <NUM>, <NUM>) scheme, which are the security data. Therefore, each sub-block of the output block of data includes <NUM> bits of original data from the received <NUM>-byte block of data and corresponding <NUM> redundant bits using the Hamming code (<NUM>, <NUM>, <NUM>) scheme. Accordingly, each sub-block of the output block of data has a size of <NUM> bytes. With <NUM> sub-blocks, the output block of data has a total size of <NUM> bytes (<NUM> sub-blocks x <NUM> bytes/sub-block). Therefore, the output block of data has a same size as the received block of data despite additionally storing security data used to both detect and correct one or more bit errors that occur during data transmission. The encoder also inserts an indication in the metadata of the output block of data specifying the selected error correction scheme such as the Hamming code (<NUM>, <NUM>, <NUM>) scheme.

The queue <NUM> receives the block of data sent by the transmitter <NUM>. The decoder <NUM> of the receiver <NUM> inspects a particular field of the header or other metadata to search for the indication of the selected error correction scheme. The decoder <NUM> uses the error correction scheme specified by the indication for verifying and possibly correcting the received block of data. The decoder <NUM> is also capable of retrieving a copy of a portion of data that is invariant across sub-blocks. For example, when the portions are the most significant bytes of the sub-blocks, at least one of the sub-blocks still includes a copy of the portion. The decoder <NUM> generates the original block of data from the retrieved portion and the verified (and corrected) data. Afterward, the decoder <NUM> sends the generated data to other processing circuitry. It is noted that the subcomponents, such as the control unit <NUM>, the decoder <NUM>, and so on, are implemented with hardware, such as circuitry, to perform the above steps to transmit data from the transmitter <NUM> to the receiver <NUM>.

Turning now to <FIG>, a generalized block diagram of one embodiment of data for transmission <NUM> is shown. Processing circuitry generates the block of data <NUM> and a transmitter receives the block of data <NUM> to further process before sending to a receiver. In the illustrated embodiment, the block of data <NUM> has a size of <NUM> bytes although other data sizes are possible and contemplated. It is noted that the block of data <NUM>, in some examples, is payload data, and a command or a message or a header associated with the payload data can be sent separately from the payload data. The contents of the block of data <NUM> is shown with hexadecimal numerals. Each of the hexadecimal numerals represents <NUM> bits. Although other configurations are possible, the block of data <NUM> has the most significant bytes located on the left.

An encoder of a transmitter divides the block of data <NUM> into multiple sub-blocks. Here, the block of data <NUM> is divided into eight <NUM>-byte sub-blocks shown as sub-blocks <NUM>, <NUM> and <NUM>. The encoder of the transmitter compares a portion of each of two or more sub-blocks of data <NUM>-<NUM> to one another. In one example, the encoder of the transmitter selects a most significant byte of each of the sub-blocks <NUM>-<NUM> to compare (e.g., portions <NUM>, <NUM>,. The most significant byte of sub-blocks <NUM>-<NUM> is illustrated as portion <NUM>. For this example, the offset is zero within a corresponding sub-block and the size of the portion is one byte. In other examples, the offset and size may be different. As can be seen in the illustrated example, each of these bytes has the same value of 3f.

It is noted that particular workloads using blocks of data of a same data type tend to have similarity across the blocks of data. For example, double precision Floating Point (FP) workloads include high bit similarity across blocks of data such as <NUM>-bit words. The main reason for high similarity is that one sign bit and <NUM> exponent bits change slightly across <NUM>-bit words. Therefore, the transmitter is able to prevent including one or more of the bytes of the portion of data <NUM> in an output block of data to send to a receiver. The transmitter is also able to insert security data in the output block of data, which has a same <NUM>-byte size as the original block of data <NUM>. Therefore, power consumption is reduced with less data being transmitted despite utilizing security data to increase reliability.

Referring to <FIG>, a generalized block diagram of one embodiment of data for transmission <NUM> is shown. Similar to the block of data <NUM> (of <FIG>), processing circuitry generates the block of data <NUM> and the block of data <NUM>, and a transmitter receives the blocks of data <NUM> and <NUM> to further process before sending to a receiver. In the illustrated embodiment, the blocks of data <NUM> and <NUM> have a size of <NUM> bytes although other data sizes are possible and contemplated. An encoder of a transmitter divides the blocks of data <NUM> and <NUM> into <NUM><NUM>-byte sub-blocks shown as sub-blocks <NUM>, <NUM> and <NUM>, and sub-blocks <NUM>, <NUM> and <NUM>. In some embodiments, the encoder of the transmitter selects a most significant byte of the sub-blocks as portions to compare. The most significant byte of the sub-blocks <NUM>-<NUM> are shown as portion <NUM>. Similarly, the most significant byte of the sub-blocks <NUM>-<NUM> are shown as portion <NUM>. In this case, the bytes located on the left of the sub-blocks <NUM>-<NUM> are the selected portions (i.e., <NUM>, <NUM>,. Similarly, the bytes located on the left of the sub-blocks <NUM>-<NUM> are the selected portions (i.e., <NUM>, <NUM>,.

Each of the portions of block of data <NUM> and the portions of block of data <NUM> is selected in a manner similar to that described earlier in <FIG>. As can be seen, each of these bytes of the block of data <NUM> has the same value 0d. Similarly, each of these bytes of the block of data <NUM> has the same value 0d. The encoder of the transmitter compares two or more portions of sub-blocks of data <NUM>-<NUM> to one another. Similarly, the encoder of the transmitter compares two or more portions of sub-blocks of data <NUM>-<NUM> to one another.

As noted earlier, particular workloads using blocks of data of a same data type tend to have similarity across the blocks of data. For example, one sign bit and <NUM> exponent bits for single precision floating-point workloads tend to remain unchanged across <NUM>-bit words as shown for block of data <NUM>. Additionally, the most significant bytes of integer workloads tend to remain unchanged across <NUM>-bit words as shown for block of data <NUM>. The high similarity across data words provides an opportunity to prevent including one or more copies of the similar data in an output block of data and instead include security data. Therefore, the output block of data does not have a greater data size than the data size of the original block of data despite storing security data. Therefore, power consumption due to data transmission reduces while data reliability increases.

As described earlier, data, such as blocks of data <NUM> and <NUM>, are transmitted over a communication bus between varieties of types of components. In some embodiments, the communication bus is between a memory controller and a memory device and the memory device supports error correction schemes due to a demand for high reliability. The memory device includes one of a variety of random access memory (RAM), such as a variety of dynamic random access memory (DRAM), one of a variety of non-volatile (NV) dual in-line memory modules (DIMMs) such as NVDIMM-P, one of another type of data storage technologies such as phase-change memories (PCM), ferroelectric memories (FeRAM), magnetoresistive memories (MRAM), resistive memories (ReRAM or RRAM), three dimensional (3D) cross-point (XPoint) memories, and so forth. When the memory device is used in a computing system processing applications for the medicine field, finance and banking field, science field, and so forth, the error correction schemes are used to increase reliability despite these schemes consuming more power. However, as described earlier, it is possible to receive input data and generate output data to transmit on a communication bus without increasing the data size despite adding security data. Additionally, such steps are performed for other interfaces besides between a memory controller and a memory device.

Turning now to <FIG>, a generalized block diagram of one embodiment of a control unit <NUM> of a transmitter is shown. In the illustrated embodiment, the control unit <NUM> includes a data translator <NUM> that receives input data <NUM> and generates the output data <NUM> to send on a communication bus. Circuitry, such as hardware circuits, are used to implement the data translator <NUM>. The data translator <NUM> uses information from tables <NUM>-<NUM> and an external error correction unit when generating the output data <NUM>. Access circuitry of the tables <NUM>-<NUM> is not shown for ease of illustration. Tables <NUM>-<NUM> use circuitry to store information, and this circuitry is used to implement any of a variety of memories. For example, the circuitry implements one or more of a random access memory, registers, flip-flop circuits, a queue, a content addressable memory (CAM), and so forth.

Table <NUM> uses multiple fields such as fields <NUM>-<NUM>. Other fields not shown are also possible and contemplated such as a status field with a valid bit, an index field to identify a row in table <NUM>, another index field that is later mapped to a corresponding error correction scheme to use, and so forth. Field <NUM> stores an indication of an error correction scheme. As described earlier, examples of error correction schemes are a Hamming code scheme, a binary convolution code scheme, a Reed-Solomon code scheme, and a low-density parity check code scheme. One or more of these schemes include a variety of types. For example, supported Hamming code schemes include one or more of a Hamming code (<NUM>, <NUM>, <NUM>) scheme, a Hamming code (<NUM>, <NUM>, <NUM>) scheme, a Hamming code (<NUM>, <NUM>, <NUM>) scheme, and a Hamming code (<NUM>, <NUM>, <NUM>) scheme.

Field <NUM> stores an input data size of the available error correction scheme. For example, the input data size of the Hamming code (<NUM>, <NUM>, <NUM>) scheme is <NUM> bits. Field <NUM> stores a priority level of a corresponding error correction scheme. When two or more available error correction schemes are capable of providing security data for data to transmit, the control unit <NUM> selects the error correction scheme with the highest priority level. In some cases, the priority level increases with increasing input data size. In other cases, the priority level is set based on other criteria.

Table <NUM> stores at least fields <NUM>-<NUM>. Similar to table <NUM>, it is possible and contemplated that table <NUM> includes other fields not shown such as a status field with a valid bit to indicate a valid entry or row in the table. Field <NUM> stores one of the supported sizes of a sub-block. For example, when a block of data to be transmitted has a size of <NUM> bytes, it is possible to divide the block of data into <NUM><NUM>-byte sub-blocks, <NUM><NUM>-byte sub-blocks, or other. Field <NUM> stores a number of sub-blocks included in the block of data. Field <NUM> stores an amount of reclaimed data to use for an output block of data once the number and size of sub-blocks is known. This is the amount of data prevented from being included in the output block of data.

Field <NUM> stores the amount of the original data to include in the output block of data once it is known how much data to prevent including in the output block of data. For example, for a received block of data with a size of <NUM> bytes, when the control unit <NUM> divides the block of data into <NUM><NUM>-byte sub-blocks, and determines a most significant <NUM>-byte portion of data in each of the sub-blocks match one another, the control unit <NUM> prevents including <NUM> of the <NUM><NUM>-byte portions in the output block of data. The determination of preventing <NUM> portions, rather than <NUM> portions or <NUM> portions or another number of portions, is further described in method <NUM> (of <FIG>). With <NUM><NUM>-byte portions prevented from being included in the output block of data, the amount of the original <NUM> bytes of data placed in the output block of data is <NUM> bytes or <NUM> bits.

Field <NUM> stores a size of remaining data per sub-block. For example, dividing the <NUM> bits by the <NUM> sub-blocks provides <NUM> bits per sub-block to use for storing original data of the received block of data. Since the size of the sub-block is <NUM> bytes, which is stored in field <NUM>, there are <NUM> remaining bits for storing security data in the sub-block. It is noted that the control unit <NUM> compares the information stored in field <NUM> of table <NUM> to the information stored in field <NUM> of table <NUM> to determine which error correction scheme to select.

It is noted that table <NUM> stores information of non-default error correction schemes. When the received data <NUM> is divided into sub-blocks with portions that match across the sub-blocks, the control unit <NUM> uses a non-default error correction scheme to generate output data <NUM>. In some implementations, the size of the output data <NUM> is no greater than the combined size of the input data <NUM> and the security data. In some embodiments, the control unit <NUM> uses a non-default error correction scheme to generate the output data <NUM> with a same size as the input data <NUM> despite placing security data in the output data <NUM>. For example, each of the input data <NUM> and the output data <NUM> has a size of <NUM> bytes.

When the input data <NUM> does not have matching portions across sub-blocks, the control unit uses a default error correction scheme to generate the output data <NUM>, which has a size larger than the input data <NUM> due to placing security data in the output data <NUM>. For example, when the default type of error correction scheme is the Hamming code (<NUM>, <NUM>, <NUM>) scheme, and the input data <NUM> has a size of <NUM> bytes, and each of <NUM> sub-blocks has a size of <NUM> bytes (<NUM> bits) with no matching portion across sub-blocks, the size of the output data <NUM> is greater than <NUM> bytes. The output data <NUM> has <NUM> bits per sub-block with <NUM> bits of original data from the input data <NUM> and <NUM> bits of redundant bits for the security data generated by the Hamming code (<NUM>, <NUM>, <NUM>) scheme. With <NUM> bits per sub-block and <NUM> sub-blocks, the total size of the output data <NUM> is <NUM> bits, or <NUM> bytes with <NUM> bits of generated redundant bits as security data.

Referring now to <FIG>, one embodiment of a method <NUM> for efficiently transmitting data is shown. For purposes of discussion, the steps in this embodiment (as well as in <FIG>) are shown in sequential order. However, in other embodiments some steps occur in a different order than shown, some steps are performed concurrently, some steps are combined with other steps, and some steps are absent.

An encoder of a transmitter receives an input block of data to transmit to a receiver (block <NUM>). The encoder selects a number of sub-blocks for the received input block of data (block <NUM>), and divides the block of data into the selected number of sub-blocks (block <NUM>). The encoder compares a portion of each of two or more sub-blocks of the selected number of sub-blocks of data to one another (block <NUM>). In some embodiments, a portion is selected for comparison from all of the sub-blocks. The selected portions have a same offset and size within a corresponding sub-block. In an example, the encoder selects a most significant byte of the two or more sub-blocks for comparison. In such an example, for each portion to compare, the offset is zero and the size is one byte. However, in other examples, the number of sub-blocks from which to select a portion has a different value. Similarly, in other examples, the offset and the size of the portion have different values.

If the encoder determines the compared portions do not match one another ("no" branch of the conditional block <NUM>), and if the encoder has not reached the last available number of sub-blocks to compare ("no" branch of the conditional block <NUM>), then control flow of method <NUM> returns to block <NUM> where the encoder selects another number of sub-blocks for the received block of data. As noted earlier, in some embodiments, the steps performed in blocks <NUM>-<NUM> are performed concurrently, rather than serially. In such embodiments, the encoder concurrently performs the steps of blocks <NUM>-<NUM> for multiple selected numbers of sub-blocks.

In one example, the encoder selects a number of <NUM> sub-blocks and concurrently selects another number of <NUM> sub-blocks. When the received input block of data has a size of <NUM> bytes, there are eight <NUM>-byte sub-blocks for the first choice of the number of sub-blocks and there are <NUM><NUM>-byte sub-blocks for the second choice. Therefore, in one example, the encoder compares the most significant byte of each of the eight <NUM>-byte sub-blocks with one another, and concurrently, compares the most significant byte of each of the <NUM><NUM>-byte sub-blocks with one another. Although the comparisons are performed concurrently, in some designs, the choice of <NUM> sub-blocks has a higher priority than the choice of <NUM> sub-blocks. The priority is used when there are matches found for all of the portions of the eight <NUM>-byte sub-blocks and there are matches found for all of the portions of the <NUM><NUM>-byte sub-blocks.

Returning to the conditional block <NUM>, if the encoder determines the portions compared do not match one another ("no" branch of the conditional block <NUM>), and if the encoder has reached the last available number of sub-blocks to compare ("yes" branch of the conditional block <NUM>), then the encoder uses a default type of error correction scheme for transmitting the block of data (block <NUM>). When the encoder uses the default type of error correction scheme, the total size of the output block of data is greater than the size of the received input block of data, since security data is added to the received input block of data to generate the output block of data.

Selection of the error correction scheme is based on the size of the output block of data. In various embodiments, the output block of data is divided into a same number of sub-blocks as the input block of data. The size of the output block of data and the data size per sub-block of the output block of data are dependent upon one another and they are used to select the error correction scheme. If the encoder determines the portions to compare of the input block of data match one another ("yes" branch of the conditional block <NUM>), then the encoder determines the data size per sub-block of the output block of data (block <NUM>).

In some embodiments, determining the data size per sub-block of the output block of data in block <NUM> is done by initially searching a table or other memory such as the table <NUM> with field <NUM> (of <FIG>). Determining the data size per sub-block of the output block of data also determines a size of reclaimed data. An example of the size of the reclaimed data is field <NUM> of table <NUM> (of <FIG>). The size of reclaimed data is the amount of data to remove from the input block of data to generate an intermediate block of data. The encoder generates this intermediate block of data by removing, from the input block of data, one or more portions of the two or more compared portions that match one another. Later, the encoder generates the output block of data by inserting security data into the intermediate block of data. The encoder uses a selected error correction scheme to generate the security data as further described in the below discussion.

In other embodiments, a table or memory, such as table <NUM> (of <FIG>), does not yet store such information. Therefore, an iterative process is performed to determine the number of copies of the portion to remove from the input block of data to generate the intermediate block of data. The steps of the upcoming method <NUM> (of <FIG>) describe such an iterative process. Once the number of copies of the portion to remove from the input block of data to generate the intermediate block of data block of data is known (from a table search or from a previous iterative process), then the steps of block <NUM> are performed. In yet other embodiments, a preferred error correction scheme is initially selected, and the input data size of this preferred error correction scheme is used to determine the data size per sub-block of the output block of data. Following, the number of copies of the portion to remove from the input block of data to generate the intermediate block of data block of data is determined. The choice of which steps to prioritize and initially perform is based on what information is already readily available.

When the number of copies of the portion to remove from the input block of data to generate the intermediate block of data block of data is known, such as reading field <NUM> of table <NUM> (of <FIG>), In one example, the received input block of data has a size of <NUM> bytes, there are eight <NUM>-byte sub-blocks, and the selected portions to compare are the most significant bytes of the eight sub-blocks. In the example, all eight portions match one another, and the encoder determines to remove <NUM> of the <NUM> portions from the input block of data to generate the intermediate block of data block of data. Later, the encoder inserts security data into the intermediate block of data to generate the output block of data. Therefore, the output block of data includes <NUM> bytes of the received input block of data (<NUM> - <NUM> = <NUM>). The encoder distributes the <NUM> bytes, or <NUM> bits, into the eight sub-blocks. Therefore, each sub-block of the output block of data includes <NUM> bits (<NUM> / <NUM> = <NUM>) of original input data from the received <NUM>-byte input block of data.

The encoder compares the determined data size to an input data size of an available types of error correction schemes (block <NUM>). Using the above example, the encoder compares the <NUM> bit determined data size per sub-block to input data sizes of multiple available types of error correcting schemes. If the determined data size does not match any data sizes of the available types of error correction schemes ("no" branch of the conditional block <NUM>), then control flow of method <NUM> moves to block <NUM> where the encoder uses a default type of error correction scheme for transmitting the block of data (block <NUM>).

If the determined data size matches a data size of an available type of error correction schemes ("yes" branch of the conditional block <NUM>), then the encoder uses the matching type of error correction scheme for transmitting the block of data (block <NUM>). For example, the encoder uses the matching type of error correction scheme for generating security data to insert in the intermediate block of data. When the encoder uses the matching type of error correction scheme, the total size of the output block data is no greater than the combined size of the input block of data and the security data. In some embodiments, the total size of the output block data is the same as the size of the received input block of data, since security data consumes data storage space made available by preventing including one or more copies of the portion to compare in the output block of data.

Continuing with the above example, the determined data size of <NUM> bits matches the input data size of <NUM> bits for a Hamming code (<NUM>, <NUM>, <NUM>). For each sub-block of the output block of data, the encoder generates and inserts <NUM> generated redundant bits based on the Hamming code, which are the security data. Therefore, each sub-block of the output block of data includes <NUM> bits of original input data from the received <NUM>-byte input block of data and corresponding <NUM> redundant bits generated using the Hamming code (<NUM>, <NUM>, <NUM>). Accordingly, each sub-block of the output block of data has a size of <NUM> bytes. With <NUM> sub-blocks, the output block of data has a total size of <NUM> bytes (<NUM> sub-blocks x <NUM> bytes/sub-block), which is the same size as the received input block of data. The encoder also inserts an indication in the metadata of the output block of data specifying the matching error correction scheme such as the Hamming code (<NUM>, <NUM>, <NUM>). Therefore, a decoder in the receiver is capable of receiving the output block of data, and using at least this indication, generating the original block of data from the received block of data with the security data.

Turning now to <FIG>, one embodiment of a method <NUM> for efficiently transmitting data is shown. An encoder of a transmitter has already received a block of data to transmit to a receiver. The encoder has also already divided the received block of data into sub-blocks and compared portions across the sub-blocks. For example, the encoder has already performed the steps of moving control flow of method <NUM> from block <NUM> to block <NUM> (of <FIG>). The encoder determines portions of multiple sub-blocks of a block of data match one another (block <NUM>). The encoder selects an integer (block <NUM>). The range of integers is <NUM> to the number of portions less one. For example, when the received block of data has a size of <NUM> bytes and the encoder divided the block of data into eight <NUM>-byte sub-blocks, there are <NUM> portions with each portion being a most significant byte of each sub-block in an example. Therefore, the set of integers from which to choose ranges from <NUM> to <NUM>. The encoder calculates an input data size of sub-blocks by dividing the block of data less the integer number of copies of the portion by the number of sub-blocks (block <NUM>). For example, when the block of data has a size of <NUM> bytes, the encoder divided the block of data into eight <NUM>-byte sub-blocks, the portions are the most significant bytes of the sub-blocks, and the selected integer is <NUM>, the encoder calculates the input data size of sub-blocks to be <NUM> bytes less <NUM> bytes (<NUM> copies of the matching portion) divided by the sub-block size of <NUM> bytes. In this calculation, the input data size of sub-blocks is (<NUM> bytes - <NUM> bytes)/<NUM> bytes = <NUM>. No available error correction scheme has an input data size that is a non-integer such as <NUM>. Therefore, the encoder needs to select another integer and reiterate the steps.

If the calculated data size of sub-blocks does not match any input data size of available types of error correction schemes ("no" branch of the conditional block <NUM>), and the encoder has not reached a last integer ("no" branch of the conditional block <NUM>), then control flow of method <NUM> returns to block <NUM> where the encoder selects another integer. As described above, the set of integers from which to choose ranges from <NUM> to the number of portions less one. When there are <NUM> portions, the set of integers from which to choose ranges from <NUM> to <NUM>.

If the calculated data size of sub-blocks does not match any input data size of available types of error correction schemes ("no" branch of the conditional block <NUM>), and the encoder has reached a last integer ("yes" branch of the conditional block <NUM>), then the encoder uses a default type of error correction scheme for transmitting the block of data (block <NUM>). When the encoder uses the default type of error correction scheme, the total size of the output data is greater than the size of the received input block of data, since security data is added to the received input block of data. If the calculated data size of sub-blocks does match an input data size of an available type of error correction scheme ("yes" branch of the conditional block <NUM>), then the encoder uses the matching type of error correction scheme for transmitting the block of data (block <NUM>). When the encoder uses the matching type of error correction scheme, in some implementations, the size of the output block of data is no greater than the combined size of the input block of data and the security data. In some embodiments, the size of the output block of data is the same as the size of the received input block of data. The security data consumes data storage space made available by preventing to include, in the output block of data, one or more copies of the portion found in the input block of data.

It is noted, in some embodiments, the steps performed for methods <NUM> and <NUM> are used to generate a table similar to table <NUM> (of <FIG>). Therefore, the iterative steps of method <NUM> and <NUM> are not continually performed over time. For example, the second row (entry) of table <NUM> shows that <NUM> bytes of original data are prevented from being included in the output block of data when matching portions are found across sub-blocks. For the parameters of a received block of data of <NUM> bytes, and dividing into <NUM><NUM>-byte sub-blocks, the size of <NUM> bytes in field <NUM> is always true. Therefore, once this value is found, this value can be stored and retrieved for quick access, rather than recalculated again. Therefore, as available error correction schemes are added and removed from the transmitter, the tables are updated and generation of the stored information is possible.

Referring now to <FIG>, one embodiment of a method <NUM> for efficiently transmitting data is shown. A decoder at a receiver receives a block of data from a transmitter (block <NUM>). The decoder inspects an indication specifying a type of error correction scheme used for transmission (block <NUM>). In some embodiments, the indication is a multi-bit value stored in a particular field of a header or other metadata of the received block of data. The multi-bit value is decoded to determine the specified type of error correction scheme used for transmitting the block of data.

If the indication specifies a default type of error correction scheme ("yes" branch of the conditional block <NUM>), then the decoder uses the default type of error correction scheme for verifying the received block of data (block <NUM>). In such a case, the received block of data has a larger data size than the original block of data, since security data was added to the copy of the original block of data. After decoding, the resulting block of data will have a smaller size than the received block of data. For example, when the default type of error correction scheme is the Hamming code (<NUM>, <NUM>, <NUM>) scheme, the original block of data has a size of <NUM> bytes and each of <NUM> sub-blocks has a size of <NUM> bytes (<NUM> bits). However, the encoder transmitted <NUM> bits per sub-block with <NUM> bits of original data and <NUM> bits of generated redundant bits for the security data. With <NUM> bits per sub-block and <NUM> sub-blocks, the total size of the transmitted block of data is <NUM> bits, or <NUM> bytes with <NUM> bits of generated redundant bits as security data.

If the indication specifies a non-default type of error correction scheme ("no" branch of the conditional block <NUM>), then the decoder uses the non-default type of error correction scheme for verifying and possibly correcting the received block of data (block <NUM>). In such a case, the received block of data has a same data size as the original block of data, since security data was added to the copy of the original block of data less one or more copies of the portions used in comparisons. The decoder retrieves a copy of a portion of data that is invariant across sub-blocks (block <NUM>). For example, when the portions are the most significant bytes of the sub-blocks, at least one of the sub-blocks still includes a copy of the portion. The decoder generates the original block of data from the retrieved portion and the verified data (block <NUM>).

It is noted that one or more of the above-described embodiments include software. In such embodiments, the program instructions that implement the methods and/or mechanisms are conveyed or stored on a computer readable medium. Numerous types of media which are configured to store program instructions are available and include hard disks, floppy disks, CD-ROM, DVD, flash memory, Programmable ROMs (PROM), random access memory (RAM), and various other forms of volatile or non-volatile storage. Generally speaking, a computer accessible storage medium includes any storage media accessible by a computer during use to provide instructions and/or data to the computer. For example, a computer accessible storage medium includes storage media such as magnetic or optical media, e.g., disk (fixed or removable), tape, CD-ROM, or DVD-ROM, CD-R, CD-RW, DVD-R, DVD-RW, or Blu-Ray. Storage media further includes volatile or non-volatile memory media such as RAM (e.g. synchronous dynamic RAM (SDRAM), double data rate (DDR, DDR2, DDR3, etc.) SDRAM, low-power DDR (LPDDR2, etc.) SDRAM, Rambus DRAM (RDRAM), static RAM (SRAM), etc.), ROM, Flash memory, non-volatile memory (e.g. Flash memory) accessible via a peripheral interface such as the Universal Serial Bus (USB) interface, etc. Storage media includes microelectromechanical systems (MEMS), as well as storage media accessible via a communication medium such as a network and/or a wireless link.

Additionally, in various embodiments, program instructions include behavioral-level descriptions or register-transfer level (RTL) descriptions of the hardware functionality in a high level programming language such as C, or a design language (HDL) such as Verilog, VHDL, or database format such as GDS II stream format (GDSII). In some cases the description is read by a synthesis tool, which synthesizes the description to produce a netlist including a list of gates from a synthesis library. The netlist includes a set of gates, which also represent the functionality of the hardware including the system. The netlist is then placed and routed to produce a data set describing geometric shapes to be applied to masks. The masks are then used in various semiconductor fabrication steps to produce a semiconductor circuit or circuits corresponding to the system. Alternatively, the instructions on the computer accessible storage medium are the netlist (with or without the synthesis library) or the data set, as desired. Additionally, the instructions are utilized for purposes of emulation by a hardware based type emulator from such vendors as Cadence®, EVE®, and Mentor Graphics®.

Claim 1:
A circuit comprising:
an interface configured to receive a first block of data (<NUM>);
an error correction unit (<NUM>) configured to perform a plurality of error correction schemes; and
circuitry (<NUM>) configured to:
divide the first block of data (<NUM>) into a first plurality of sub-blocks of data (<NUM>, <NUM>, <NUM>);
compare a portion of each of two or more sub-blocks of the first plurality of sub-blocks of data to one another;
based at least in part on a determination that two or more compared portions of the two or more sub-blocks comprise the same data, generate a second block of data (<NUM>) comprising a separate sub-block for each of the first plurality of sub-blocks of data of the first block of data, wherein the second block of data:
comprises error correction data corresponding to one of the plurality of error correction schemes, wherein the error correction data is inserted to replace data removed from at least one of the two or more compared portions of the two or more sub-blocks that comprise the same data; and
has a size that is no greater than a size of the first block of data; and
convey the second block of data via an interface.