Detailed Description
The present invention relates to improvements in techniques for transferring electronic information. The following description is presented to enable one of ordinary skill in the art to make and use the invention and is provided in the context of a patent application and its requirements. Various modifications to the disclosed embodiments will be readily apparent to those skilled in the art, and the generic principles herein may be applied to other embodiments. Thus, the present invention is not intended to be limited to the embodiments shown, but is to be accorded the widest scope consistent with the principles and features described herein.
The present invention includes a system and method for efficiently transmitting electronic information and includes a transmitter having an encoder that performs a parity encoding process. The encoder creates a parity block for embedding in a transmission packet (transmission packet). The parity block may be based on data segments from one or more transport packets. The system also includes a receiver having a decoder that performs a packet verification process using the parity blocks to identify corrupted packets from among the transmitted packets. The decoder advantageously performs a packet reconstruction process using selected ones of the data segments and parity blocks to produce reconstructed data segments for the corrupted packets.
Referring now to fig. 1, shown is a block diagram of a data transmission system 110 in accordance with one embodiment of the present invention. In the embodiment of FIG. 1, the data transmission system 110 includes, but is not limited to, a transmitter 118 and a receiver 126. In alternative embodiments, the data transmission system 110 may be implemented with components and configurations in addition to, or instead of, certain of those components and configurations discussed in conjunction with the FIG. 1 embodiment.
In the embodiment of the data transmission system 110 of fig. 1, the transmitter 118 receives the initial data 116 from any suitable data source. For example, the initial data may be provided as packets of digital information from the source memory device. In some embodiments, the data transmission system 110 may be implemented as a one-way wireless or wired (hard-wired) television broadcast system. The transmitter 118 modulates the initial data 116 and then outputs the modulated initial data 116 as transmission data 120 through any suitable type of transmission channel. Receiver 126 of data transmission system 110 then receives, demodulates, and processes transmitted data 120 to provide final data 138 to any suitable data destination, such as a destination memory device.
In some circumstances, the transmitted data 120 may become corrupted during the aforementioned transmission. However, in the case of certain types of transmitted data 120, loss of digital information is unacceptable. For example, if transmission data 120 is a binary file, such as a software instruction, any corrupted digital information may render transmission data 120 unusable. This problem becomes even more pronounced when the transmission path between the transmitter 118 and the receiver 126 is unidirectional, since the receiver 126 is then unable to notify the transmitter 118 of any errors and is also unable to request retransmission of the corrupted transmitted data 120.
Transmitter 118 thus encodes the appropriate parity information into transmitted data 120 in accordance with the present invention. The receiver 126 may thus utilize the encoded parity information to validate the transmitted data 120. In addition, receiver 126 may also perform a reconstruction process using the encoded parity information to advantageously reconstruct any corrupted elements of transmitted data 120. Further details regarding the implementation and utilization of the transmitter 118 and receiver 126 are discussed further below in conjunction with fig. 2-9B.
Referring now to FIG. 2, a block diagram for one embodiment of the FIG. 1 transmitter 118 is shown, in accordance with the present invention. In the FIG. 2 embodiment, transmitter 118 includes, but is not limited to, a transmit central processing unit (transmit CPU)212, a modulator 214, an amplifier 216, a transmit memory 220, and one or more transmit input/output receive ((one or more) transmit I/O interfaces) 224. In alternative embodiments, the transmitter 118 may also be implemented with components and configurations in addition to, or instead of, certain of those components and configurations discussed in conjunction with the FIG. 2 embodiment.
In the fig. 2 embodiment, transmission CPU 212 may be implemented to include any appropriate and compatible microprocessor device that preferably executes software instructions to thereby control and manage the operation of transmitter 118. In the FIG. 2 embodiment, transmit memory 220 may be implemented to include any combination of desired storage devices, including, but not limited to, read-only memory (ROM), random-access memory (RAM), and various types of non-volatile memory, such as floppy disks, memory sticks, compact disks, or hard disks. The contents and functionality of transmit memory 220 are further discussed below in conjunction with FIG. 3.
In the FIG. 2 embodiment, transmit I/O interface(s) 224 may include one or more input and/or output interfaces to receive and/or transmit any required types of information by transmitter 118. In the fig. 2 embodiment, modulator 214 may modulate initial data 116 (fig. 1) to generate modulated data, amplifier 216 may amplify the modulated data to generate transmit data 120 (fig. 1), and transmit data 120 may be provided to receiver 126 (fig. 1) via transmit I/O interface 224 using any effective means. For example, in some embodiments, the amplified transmission data 120 may be wirelessly broadcast from a transmit antenna coupled to the appropriate transmit I/O interface 224. The implementation and utilization of transmitter 118 is further discussed below in conjunction with fig. 3, 7, and 8A-8B.
Referring now to FIG. 3, a block diagram for one embodiment of the FIG. 2 transmit memory 220 is shown, in accordance with the present invention. In the FIG. 3 embodiment, transmit memory 220 may include, but is not limited to, a transmitter application 312, an encoder 316, a transmit buffer 320, and miscellaneous storage 324. In alternative embodiments, the transmit memory 220 may include various other components and functionality in addition to, or instead of, certain of those components and functionality discussed in conjunction with the FIG. 3 embodiment.
In the FIG. 3 embodiment, transmitter application 312 may include program instructions that are preferably executed by transmit CPU 212 (FIG. 2) to perform various functions and operations for transmitter 118. The particular nature and functionality of the transmitter application 312 typically varies depending on factors such as the specific type and particular functionality of the corresponding transmitter 118. In the fig. 3 embodiment, transmitter 118 may utilize encoder 316 to perform a parity encoding process by utilizing any effective techniques to create a parity block of parity information.
For example, in some embodiments, encoder 316 encodes parity blocks for a given packet by utilizing digital information from one or more surrounding packets (surrouding packets), thereby allowing for verification and reconstruction in the event that the given packet is corrupted during transmission. One particular technique for encoding parity information is discussed below in conjunction with fig. 7 and 8A-8B. In the embodiment of fig. 3, encoder 316 may utilize transmit buffer 320 to temporarily store packets during the parity encoding process. In the FIG. 3 embodiment, transmitter 118 may utilize miscellaneous storage 324 to store any desired type of other information.
In the embodiment of fig. 3, the encoder 316 is shown implemented as software program instructions. However, in some embodiments, the encoder 316 may also be implemented as a hardware component that performs an equivalent function. Additional details regarding the operation and implementation of encoder 316 are discussed further below in conjunction with fig. 7 and 8A-8B.
Referring now to FIG. 4, a diagram for one embodiment of a packet 410 is shown, in accordance with the present invention. In the FIG. 4 embodiment, packet 410 may include, but is not limited to, a header 412, data 416, and parity block 420. In alternative embodiments, the grouping 410 may include other elements and configurations in addition to, or instead of, certain of those elements and configurations discussed in conjunction with the fig. 4 embodiment.
In the FIG. 4 embodiment, packet 410 includes a header 412, and header 412 may include any relevant type of information. For example, the header 412 may describe the specific content and size of the remaining elements of the packet 410. In the FIG. 4 embodiment, data 416 may include any suitable type of information for transmission to receiver 126 (FIG. 1). For example, data 416 may include video information, audio information, software instructions, digital files, text, graphics, and any other type of electronic content. In the fig. 4 embodiment, parity block 420 may include any suitable type of information for receiver 126 to effectively verify and potentially reconstruct any corrupted or damaged packets 410. The creation and utilization of parity block 420 is further discussed below in conjunction with fig. 7-9B.
Referring now to FIG. 5, a block diagram for one embodiment of the FIG. 1 receiver 126 is shown, in accordance with the present invention. In the fig. 5 embodiment, receiver 126 may include, but is not limited to, a receiver central processing unit (receiver CPU)512, a demodulator 516, a receiver memory 520, and one or more receiver input/output interfaces (receiver I/O interface (s)) 524.
In alternative embodiments, the receiver 126 may be readily implemented with various components and configurations in addition to, or instead of, certain of those components and configurations discussed in conjunction with the fig. 5 embodiment. Further, in the FIG. 5 embodiment, receiver 126 may be implemented as part of any suitable type of electronic device. For example, in certain embodiments, the receiver 126 may be implemented in a fixed or portable consumer electronics device, such as a television, a personal computer, a set-top box, an audio-visual entertainment device, a cellular telephone, or a Personal Digital Assistant (PDA).
In the fig. 5 embodiment, receiver CPU 512 may be implemented to include any appropriate and compatible microprocessor device that preferably executes software instructions to thereby control and manage the operation of receiver 126. In the FIG. 5 embodiment, receiver memory 520 may be implemented to include any combination of desired storage devices, including, but not limited to, read-only memory (ROM), random-access memory (RAM), and various types of non-volatile memory, such as floppy disks, memory sticks, compact disks, or hard disks. The contents and functionality of the receiver memory 520 are further discussed below in conjunction with fig. 6.
In the FIG. 5 embodiment, receiver I/O interface(s) 524 may include one or more input and/or output interfaces to receive and/or transmit any required types of information by receiver 126. In the fig. 5 embodiment, demodulator 516 may demodulate transmit data 120 to generate final data 138 (fig. 1), which final data 138 may then be provided to an appropriate data destination via receiver I/O interface 524 using any effective means. In accordance with the present invention, receiver 126 can verify and potentially reconstruct any corrupted packets 410 in transmitted data 120. The packet verification and reconstruction process of the receiver 126 is further discussed below in conjunction with fig. 7 and 9A-9B.
Referring now to FIG. 6, a block diagram for one embodiment of the FIG. 5 receiver memory 520 is shown, in accordance with the present invention. In the FIG. 6 embodiment, receiver memory 520 includes, but is not limited to, a receiver application 612, a decoder 616, a receiver buffer 618, and miscellaneous storage 624. In alternative embodiments, receiver memory 520 may include various other components and functionality in addition to, or instead of, certain of those components and functionality discussed in conjunction with the fig. 6 embodiment.
In the fig. 6 embodiment, receiver application 612 may include program instructions that are preferably executed by receiver CPU 512 (fig. 5) to perform various functions and operations for receiver 126. The particular nature and functionality of the receiver application 612 typically varies depending on factors such as the specific type and particular functionality of the corresponding receiver 126. In the fig. 6 embodiment, receiver 126 may utilize decoder 616 to perform a packet verification process by analyzing parity blocks 420 (fig. 4) of received packet 410 using any effective techniques. In addition, the decoder 616 may also utilize the parity block 420 to perform a packet reconstruction process if any of the transmitted packets 410 are corrupted or otherwise invalid.
For example, in some embodiments, parity blocks 420 from a given packet 410 may be encoded by utilizing digital information from one or more surrounding packets, allowing for verification and reconstruction in the event that a given packet is corrupted during transmission. One particular technique for validating and reconstructing the packet 410 using the parity block 420 is discussed below in connection with fig. 7 and 9A-9B. In the fig. 6 embodiment, decoder 616 may utilize receiver buffer 618 to temporarily store packet 410 during the aforementioned verification and reconstruction process. The decoder 616 can thus look slightly forward and backward in time to perform the verification and reconstruction process in real time. In the FIG. 6 embodiment, receiver 126 may utilize miscellaneous storage 624 to store any desired type of other information.
In the embodiment of fig. 6, the decoder 616 is shown implemented as software program instructions. However, in some embodiments, the decoder 616 may also be implemented as a hardware component that performs an equivalent function. Additional details regarding the operation and implementation of decoder 616 are discussed further below in conjunction with fig. 7 and 9A-9B.
Referring now to FIG. 7, shown is a block diagram illustrating a multi-packet parity technique in accordance with one embodiment of the present invention. The embodiment of FIG. 7 is presented for illustrative purposes, and in alternate embodiments, the present invention may utilize the following parity technique: these parity techniques include components, functions, and information in addition to or in place of some of those components, functions, and information discussed in conjunction with the fig. 7 embodiment. For example, in the embodiment of FIG. 7, three consecutive packets 410 are utilized to illustrate the multi-packet parity technique. However, in alternate embodiments, any effective number of consecutive or non-consecutive packets 410 may be utilized.
In the embodiment of fig. 7, packet 10(410(a)), packet 11(410(b)), and packet 12(410(c)) are shown. As shown above in fig. 4, each packet 410 includes a header, data, and parity block. In the example of fig. 7, the packet size is shown to be equal to 128K (eight bits of binary data). In the fig. 7 embodiment, encoder 316 (fig. 3) encodes and embeds the parity blocks based on the binary eight-bit data values of the current packet and the immediately preceding packet. For example, a parity block of the packet 11(410(b)) is formed from the data values of the previous packet 10(410(a)) and the current packet 11(410 (b)).
In some embodiments, encoder 316 may thus perform a parity encoding process for each packet 410 by temporarily storing the required input packets 410 in transmit buffer 320. The encoder 316 may then perform an exclusive OR (exclusive OR) operation on each pair of corresponding bit positions of the data segments from the current packet and the immediately preceding packet. For example, assume that data from packet 11 (D11) equals 00110110 in binary, and data from packet 12 (D12) equals 11001010 in binary. In the embodiment of fig. 7, to encode the parity block of packet 12(410(c)), encoder 316 may perform an exclusive-or operation on the corresponding bits of D11 and D12 to obtain a parity block (P12) of packet 12, the parity block of packet 12 being equal to 11111100 in binary.
Decoder 616 (fig. 6) may then perform a packet verification process to determine whether a given packet 410 is corrupted, in accordance with the present invention. In the fig. 7 embodiment, decoder 616 may perform an exclusive-or operation on each pair of corresponding bit positions of the data segments from the current packet and the immediately preceding packet. As in the previous example, assume that the data from packet 11 (D11) is equal to 00110110 in binary, and the data from packet 12 (D12) is equal to 11001010 in binary. In the embodiment of fig. 7, to verify the packet 12(410(c)), the encoder 316 may perform an exclusive-or operation on the corresponding bits of D11 and D12 to obtain a check value (equal to 11111100 in binary) to compare with the parity block (P12) of the packet 12. If the check value matches the parity block P12, the packet 12 is intact and uncorrupted.
However, in the embodiment of fig. 7, if the check value does not match the parity block, the decoder 616 may perform a packet reconstruction process for the current packet 410 based on the binary data value and the binary parity block of the immediately following packet 410. For example, assume that packet 11(410(b)) is corrupted or missing. Also assume, as in the previous example, that the parity block (P12) from packet 12 equals 11111100 in binary, and that the data from packet 12 equals 11001010 in binary. To reconstruct the corrupted binary data from packet 11, decoder 616 may perform an exclusive-or operation on the corresponding bits of P12 and D12 to reconstruct the corrupted binary data from packet 11(410(b)) which is equal to 00110110 in binary. The present invention thus utilizes multi-packet parity techniques to validate and potentially reconstruct the corrupted packet 410.
Referring now to fig. 8A-8B, a flowchart of method steps for performing a block encoding process is shown, in accordance with one embodiment of the present invention. The flow diagrams of fig. 8A-8B are presented for purposes of illustration, and in alternative embodiments, the present invention may utilize steps and sequences other than those steps and sequences discussed in conjunction with the embodiments of fig. 8A-8B.
In the fig. 8 embodiment, encoder 316 of transmitter 118 first accesses incoming packet 410 from any suitable source device at step 812. At step 814, the encoder 316 analyzes the data 416 from the input packet 410. At step 816, encoder 316 generates parity block 420 for input packet 410 by utilizing any suitable technique. For example, in some embodiments, encoder 316 generates parity block 420 based on the binary data values of input packet 410 and the binary data values of one or more adjacent packets 410.
In step 818, the encoder 316 embeds the parity block 420 in the input packet 410. The transmitter 118 may then transmit the encoded packet 410 to the receiver 126 at step 820 by utilizing any suitable means. In step 822, the encoder 316 determines whether there are any more packets 410 to be encoded. If there are more packets 410, the process of FIG. 8 returns to step 812, previously described, to encode and transmit the remaining packets 410. If there are no other packets 410, the process of FIG. 8 may terminate.
Referring now to fig. 9A-9B, a flowchart of method steps for performing a packet reconstruction process is shown, in accordance with one embodiment of the present invention. The flow diagrams of fig. 9A-9B are presented for purposes of illustration, and in alternative embodiments, the present invention may utilize steps and sequences other than those steps and sequences discussed in conjunction with the embodiments of fig. 9A-9B.
In the fig. 9 embodiment, receiver 126 may receive transmitted packet 410 at step 912 by utilizing any suitable technique. In step 914, the receiver 126 stores the received packet 410 in the receiver buffer 618. At step 916, the decoder 616 performs a packet verification process on the received packet 410 by utilizing any effective techniques. For example, in some embodiments, decoder 616 may validate packet 410 by utilizing embedded parity block 420.
At step 920, if the current packet 410 is valid (not corrupted), the receiver 126 may output the verified packet 410 to any appropriate destination device at step 928. However, if the current packet 410 is not valid (corrupted), the decoder 616 may perform a packet reconstruction process by utilizing any suitable technique, as shown in step 924. For example, in some embodiments, the decoder 616 may reconstruct the corrupted packet 410 by utilizing data and parity block information from one or more neighboring packets 410.
Once the corrupted packet 410 is reconstructed, the receiver 126 may output the reconstructed packet 410 to any appropriate destination device at step 928. At step 932, the decoder 616 determines whether there are additional packets 410 to be validated and potentially reconstructed. If there are additional packets 410, the process of FIG. 9 returns to step 912 previously described to verify, reconstruct, and output any additional packets 410. However, if there are no other packets 410, the process of FIG. 9 may terminate. For at least the foregoing reasons, the present invention therefore provides an improved system and method for efficiently transferring electronic information.
The invention has been described above with reference to certain embodiments. Other embodiments will be apparent to those skilled in the art in view of this disclosure. For example, the present invention may readily be implemented using certain configurations and techniques other than those discussed in the specific embodiments above. In addition, the present invention may be effectively used in conjunction with systems other than those described above. Accordingly, these and other variations upon the discussed embodiments are intended to be covered by the present invention, which is limited only by the appended claims.